Sparse Linear Bandits with Fixed Sparsity Support: Adversarial and Stochastic Regimes

Kyoungseok Jang, Nam Phuong Tran, Nicolò Cesa-Bianchi
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1477-1485, 2026.

Abstract

We study sparse linear bandits in both adversarial and stochastic settings. While existing literature has extensively explored sparse linear bandits in the stochastic regime, the adversarial setting, particularly for general $l_p$-ball action sets $(p>1)$, remains poorly understood. Our work addresses this gap by showing that the curse of dimensionality in adversarial linear bandits can be broken under a natural fixed sparsity support assumption. Specifically, we design algorithms for the $l_\infty$- and $l_2$-balls that integrate sparsity support identification with the OSMD algorithm, achieving regret bounds $O(s\sqrt{T}\log T )$ and $O(\sqrt{sT}\log T )$, respectively. These results nearly match the optimal results when the sparsity support is known, and significantly improve upon the $ O(d\sqrt{T}) $ regret of algorithms ignoring sparsity. Furthermore, in the stochastic setting, we show how the geometry of the $l_p$-ball action set influences both exploration and regret. Our work highlights fundamental contrasts between adversarial and stochastic regimes, and establishes the first regret guarantees for sparse adversarial linear bandits beyond the $l_1$-ball action set.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-jang26a, title = { Sparse Linear Bandits with Fixed Sparsity Support: Adversarial and Stochastic Regimes }, author = {Jang, Kyoungseok and Tran, Nam Phuong and Cesa-Bianchi, Nicol\`{o}}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1477--1485}, 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/jang26a/jang26a.pdf}, url = {https://proceedings.mlr.press/v300/jang26a.html}, abstract = { We study sparse linear bandits in both adversarial and stochastic settings. While existing literature has extensively explored sparse linear bandits in the stochastic regime, the adversarial setting, particularly for general $l_p$-ball action sets $(p>1)$, remains poorly understood. Our work addresses this gap by showing that the curse of dimensionality in adversarial linear bandits can be broken under a natural fixed sparsity support assumption. Specifically, we design algorithms for the $l_\infty$- and $l_2$-balls that integrate sparsity support identification with the OSMD algorithm, achieving regret bounds $O(s\sqrt{T}\log T )$ and $O(\sqrt{sT}\log T )$, respectively. These results nearly match the optimal results when the sparsity support is known, and significantly improve upon the $ O(d\sqrt{T}) $ regret of algorithms ignoring sparsity. Furthermore, in the stochastic setting, we show how the geometry of the $l_p$-ball action set influences both exploration and regret. Our work highlights fundamental contrasts between adversarial and stochastic regimes, and establishes the first regret guarantees for sparse adversarial linear bandits beyond the $l_1$-ball action set. } }
Endnote
%0 Conference Paper %T Sparse Linear Bandits with Fixed Sparsity Support: Adversarial and Stochastic Regimes %A Kyoungseok Jang %A Nam Phuong Tran %A Nicolò Cesa-Bianchi %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-jang26a %I PMLR %P 1477--1485 %U https://proceedings.mlr.press/v300/jang26a.html %V 300 %X We study sparse linear bandits in both adversarial and stochastic settings. While existing literature has extensively explored sparse linear bandits in the stochastic regime, the adversarial setting, particularly for general $l_p$-ball action sets $(p>1)$, remains poorly understood. Our work addresses this gap by showing that the curse of dimensionality in adversarial linear bandits can be broken under a natural fixed sparsity support assumption. Specifically, we design algorithms for the $l_\infty$- and $l_2$-balls that integrate sparsity support identification with the OSMD algorithm, achieving regret bounds $O(s\sqrt{T}\log T )$ and $O(\sqrt{sT}\log T )$, respectively. These results nearly match the optimal results when the sparsity support is known, and significantly improve upon the $ O(d\sqrt{T}) $ regret of algorithms ignoring sparsity. Furthermore, in the stochastic setting, we show how the geometry of the $l_p$-ball action set influences both exploration and regret. Our work highlights fundamental contrasts between adversarial and stochastic regimes, and establishes the first regret guarantees for sparse adversarial linear bandits beyond the $l_1$-ball action set.
APA
Jang, K., Tran, N.P. & Cesa-Bianchi, N.. (2026). Sparse Linear Bandits with Fixed Sparsity Support: Adversarial and Stochastic Regimes . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1477-1485 Available from https://proceedings.mlr.press/v300/jang26a.html.

Related Material