Fixed-Budget Best-Arm Identification in Sparse Linear Bandits
Authors: Recep Can Yavas, Vincent Y. F. Tan
TMLR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we provide numerical examples to demonstrate the significant performance improvement over the existing algorithms for non-sparse linear bandits such as OD-Lin BAI, Bayes Gap, Peace, Linear Exploration, and GSE. We empirically compare the identification error of Lasso-OD with that of other existing algorithms in the literature on several synthetic datasets, including one that is a sparsity-based version of examples used in other papers (Jedra & Proutiere, 2020). The empirical results support our theoretical result that claims that the scaling of the error probability of Lasso-OD is characterized by the sparsity s while the performances of other algorithms significantly depend on d. |
| Researcher Affiliation | Academia | Recep Can Yavas EMAIL CNRS at CREATE, Singapore Vincent Y. F. Tan EMAIL Department of Mathematics, Department of Electrical and Computer Engineering, National University of Singapore |
| Pseudocode | Yes | Algorithm 1 Thresholded Lasso (TL) Algorithm 2 Lasso and Optimal-Design Based Linear Best Arm Identification (Lasso-OD) Algorithm 3 ROUND(π, T) Algorithm 4 Optimal Design-Based Linear Best Arm Identification (OD-Lin BAI) Algorithm 5 Pop Art-OD |
| Open Source Code | Yes | Our code is available at https://github.com/recepcyavas/TMLR_sparse_linear_bandit. |
| Open Datasets | Yes | We conduct an experiment on an online news popularity dataset published by Mashable (Fernandes et al., 2015), which includes 39,797 news articles, each having 58 attributes. In the first example, we draw K arms independently from the uniform distribution on the d-dimensional sphere of radius p d/s, i.e., x Rd : x 2 2 = d s , and the sparse unknown parameter is taken as θ = (1, 1, 0, . . . , 0), i.e., s = 2. |
| Dataset Splits | No | In each setting, we report the empirical error probabilities for Lasso-OD, Bayes Gap, and GSE over 4000 independent trials and for Peace and Linear Exploration over 100 independent trials. The paper does not provide traditional train/test/validation dataset splits. The experimental setup involves sequential data collection (arm pulls) within a bandit framework and reporting results over multiple independent trials, not pre-split datasets for model training and evaluation. |
| Hardware Specification | Yes | All experiments are implemented on MATLAB 2023a on an Intel(R) Core(TM) i9-12900H processor. |
| Software Dependencies | Yes | All experiments are implemented on MATLAB 2023a on an Intel(R) Core(TM) i9-12900H processor. |
| Experiment Setup | Yes | Lasso-OD-CV sets the budgets for phase 1 and phase 2 as T1 = T/5 and T2 = 4T/5 and tunes the Lasso parameters λinit and λthres using a K-fold cross-validation procedure that uses the value of s in its loss function. See Appendix F for the details of the cross-validation procedure. In each cross-validation round, the objective is to minimize the loss function T1 E[y - Xˆθthres 2] + c1P[ˆθthres 0 < s] + c2E[1/n ˆθthres 0 > s]ˆθthres 0 where c1 and c2 are ℓ0-norm regularization parameters. Here, the first term in (71) is the mean-squared error; the second and the third terms penalize the ℓ0-norm error and force the hyperparameters to output an estimate with s variables. In application, we set c1 = 200 and c2 = 5, giving more importance to detecting at least s variables. |