Linear Bandit Algorithms with Sublinear Time Complexity
Authors: Shuo Yang, Tongzheng Ren, Sanjay Shakkottai, Eric Price, Inderjit S. Dhillon, Sujay Sanghavi
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate our algorithms in a synthetic environment and a real-world movie recommendation problem. Compared with the linear time complexity baselines, our algorithms can offer a 72 times speedup when there are 100,000 arms while obtaining similar regret. In this section, we empirically evaluate the performance of our proposed algorithms in a synthetic environment and a real-world problem on movie recommendation. |
| Researcher Affiliation | Academia | Shuo Yang 1 Tongzheng Ren 1 Sanjay Shakkottai 2 Eric Price 1 Inderjit S. Dhillon 1 Sujay Sanghavi 2 1Department of CS, The University of Texas at Austin, TX, USA. 2Department of ECE, The University of Texas at Austin, TX, USA. |
| Pseudocode | Yes | Algorithm 1 ADAPTIVE MIPS SOLVER M(c, r, ϵ, δ), Algorithm 2 HEAP AUGMENTED ARM SET Ψs, Algorithm 3 SUBLINEAR TIME ELIMINATION, Algorithm 4 SUBLINEAR TIME THOMPSON SAMPLING |
| Open Source Code | No | The information is insufficient. The paper does not provide an explicit statement about releasing source code for their methodology or a link to a code repository. |
| Open Datasets | Yes | The testing environment is derived from a popular recommendation dataset: Movielens1M (Harper & Konstan, 2015). The dataset contains over 1 million ratings of 3,952 movies by more than 6,000 users. ... With the ratings of more than 5,700 remaining users, we create a 16-dimensional feature for each of the movies by matrix factorization. |
| Dataset Splits | No | The information is insufficient. The paper specifies a test set (300 users) and uses the remaining data for feature creation, implying a training set. However, it does not provide explicit details about a separate validation split or its methodology. |
| Hardware Specification | No | The information is insufficient. The paper does not specify any particular hardware (e.g., CPU, GPU models, or cloud instance types) used for running the experiments. |
| Software Dependencies | No | The information is insufficient. The paper mentions using the 'HNSW algorithm' but does not specify its version number or provide version numbers for any other software dependencies used in the experiments. |
| Experiment Setup | Yes | For the synthetic experiment, we first randomly generated a 16-dimensional vector θ from a Gaussian distribution N(0, I16). The arms A are generated from the same distribution. The reward noise is unit Gaussian. Further, over the time horizon T = 20, 000, a batch of Cchange = 2 arms are generated and included into the arm set A every 20 steps. The final arm set size is K. ... To control the tradeoff between MIPS accuracy and time complexity, we construct the MIPS solver in the following way: We first use the HNSW algorithm to retrieve a shortlist of p arms, then linearly scan the retrieved p arms for the one with the largest inner product. A larger p gives higher accuracy but slower speed. We take p from {10, 30, 100} for our experiments. |