Sparse Linear Bandits with Blocking Constraints

Adit Jain, Soumyabrata Pal, Sunav Choudhary, Ramasuri Narayanam, Harshita Chopra, Vikram Krishnamurthy
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1108-1116, 2026.

Abstract

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 \textit{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 datapoints to improve annotation efficiency for complex learning tasks. With mild assumptions on the arms, our proposed online algorithm (\texttt{BSLB}) achieves a regret guarantee of $\widetilde{\mathsf{O}}((1+\beta_k)^2k^{\frac{2}{3}} \mathsf{T}^{\frac{2}{3}})$ where the parameter vector has an (unknown) relative tail $\beta_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 (\texttt{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-jain26b, title = { Sparse Linear Bandits with Blocking Constraints }, author = {Jain, Adit and Pal, Soumyabrata and Choudhary, Sunav and Narayanam, Ramasuri and Chopra, Harshita and Krishnamurthy, Vikram}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1108--1116}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/jain26b/jain26b.pdf}, url = {https://proceedings.mlr.press/v300/jain26b.html}, abstract = { 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 \textit{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 datapoints to improve annotation efficiency for complex learning tasks. With mild assumptions on the arms, our proposed online algorithm (\texttt{BSLB}) achieves a regret guarantee of $\widetilde{\mathsf{O}}((1+\beta_k)^2k^{\frac{2}{3}} \mathsf{T}^{\frac{2}{3}})$ where the parameter vector has an (unknown) relative tail $\beta_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 (\texttt{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. } }
Endnote
%0 Conference Paper %T Sparse Linear Bandits with Blocking Constraints %A Adit Jain %A Soumyabrata Pal %A Sunav Choudhary %A Ramasuri Narayanam %A Harshita Chopra %A Vikram Krishnamurthy %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-jain26b %I PMLR %P 1108--1116 %U https://proceedings.mlr.press/v300/jain26b.html %V 300 %X 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 \textit{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 datapoints to improve annotation efficiency for complex learning tasks. With mild assumptions on the arms, our proposed online algorithm (\texttt{BSLB}) achieves a regret guarantee of $\widetilde{\mathsf{O}}((1+\beta_k)^2k^{\frac{2}{3}} \mathsf{T}^{\frac{2}{3}})$ where the parameter vector has an (unknown) relative tail $\beta_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 (\texttt{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.
APA
Jain, A., Pal, S., Choudhary, S., Narayanam, R., Chopra, H. & Krishnamurthy, V.. (2026). Sparse Linear Bandits with Blocking Constraints . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1108-1116 Available from https://proceedings.mlr.press/v300/jain26b.html.

Related Material