Sparse Linear Bandits with Blocking Constraints
This addresses challenges in personalized content recommendation and data annotation efficiency, but is incremental as it builds on existing sparse linear bandits with a new constraint.
The paper tackles the high-dimensional sparse linear bandits problem in a data-poor regime with blocking constraints, where each arm can be pulled only once, and proposes algorithms (BSLB and C-BSLB) that achieve a regret guarantee of ̃O((1+β_k)^2k^{2/3}T^{2/3}) and demonstrate effectiveness on real-world datasets.
We investigate the high-dimensional sparse linear bandits problem in a data-poor regime where the time horizon is much smaller than the ambient dimension and number of arms. We study the setting under the additional blocking constraint where each unique arm can be pulled only once. The blocking constraint is motivated by practical applications in personalized content recommendation and identification of data points to improve annotation efficiency for complex learning tasks. With mild assumptions on the arms, our proposed online algorithm (BSLB) achieves a regret guarantee of $\widetilde{\mathsf{O}}((1+β_k)^2k^{\frac{2}{3}} \mathsf{T}^{\frac{2}{3}})$ where the parameter vector has an (unknown) relative tail $β_k$ -- the ratio of $\ell_1$ norm of the top-$k$ and remaining entries of the parameter vector. To this end, we show novel offline statistical guarantees of the lasso estimator for the linear model that is robust to the sparsity modeling assumption. Finally, we propose a meta-algorithm (C-BSLB) based on corralling that does not need knowledge of optimal sparsity parameter $k$ at minimal cost to regret. Our experiments on multiple real-world datasets demonstrate the validity of our algorithms and theoretical framework.