Abstract: We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter θ*. Since we do not place any restrictions on these functions, the problem setting subsumes several previously studied frameworks that assume linear or invertible reward functions. We propose a novel approach to gradually estimate the hidden θ* and use the estimate together with the mean reward functions to substantially reduce exploration of sub-optimal arms. This approach enables us to fundamentally generalize any classical bandit algorithm including UCB and Thompson Sampling to the structured bandit setting. We prove via regret analysis that our proposed UCB-C algorithm (structured bandit versions of UCB) pulls only a subset of the sub-optimal arms O(log T) times while the other sub-optimal arms (referred to as non-competitive arms) are pulled O(1) times. As a result, in cases where all sub-optimal arms are non-competitive, which can happen in many practical scenarios, the proposed algorithm achieves bounded regret. We also conduct simulations on the Movielens recommendations dataset to demonstrate the improvement of the proposed algorithms over existing structured bandit algorithms.
All required modules are listed in requirements.txt and can be installed by:
pip3 install -U -r requirements.txt
The datasets can be downloaded as follows:
cd data
source download_data.sh
This will download the MovieLens 1M Dataset. You may edit download_data.sh to download different datasets and add necessary preprocessing functions to preproc/preproc.py.
Pre-processing as described in the paper can be done with preproc/preproc.py. As an example:
python preproc.py --movielens --train_test_ratio=0.5
will process the MovieLens Dataset with a train-test split of 50:50. For a different dataset, any preprocessing steps may be included in this file.
Bandit algorithms - UCB, TS, UCB-C, TS-C, UCB-S - can be run from algos.py. The description of the arguments is:
num_iterations : Number of iterations of each run
T : Number of rounds (horizon)
Example:
python3 c_algos.py --num_iterations 20 --T 5000
The script saves plots of the generated results in a folder data/plot_arrays.
Below are some results for the MovieLens dataset. For details about the experiments, kindly refer to Section 7 of the paper.
