Sparsity-Agnostic Lasso Bandit

Min-Hwan Oh, Garud Iyengar, Assaf Zeevi
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:8271-8280, 2021.

Abstract

We consider a stochastic contextual bandit problem where the dimension $d$ of the feature vectors is potentially large, however, only a sparse subset of features of cardinality $s_0 \ll d$ affect the reward function. Essentially all existing algorithms for sparse bandits require a priori knowledge of the value of the sparsity index $s_0$. This knowledge is almost never available in practice, and misspecification of this parameter can lead to severe deterioration in the performance of existing methods. The main contribution of this paper is to propose an algorithm that does not require prior knowledge of the sparsity index $s_0$ and establish tight regret bounds on its performance under mild conditions. We also comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms existing methods, even when the correct sparsity index is revealed to them but is kept hidden from our algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-oh21a, title = {Sparsity-Agnostic Lasso Bandit}, author = {Oh, Min-Hwan and Iyengar, Garud and Zeevi, Assaf}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {8271--8280}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/oh21a/oh21a.pdf}, url = {https://proceedings.mlr.press/v139/oh21a.html}, abstract = {We consider a stochastic contextual bandit problem where the dimension $d$ of the feature vectors is potentially large, however, only a sparse subset of features of cardinality $s_0 \ll d$ affect the reward function. Essentially all existing algorithms for sparse bandits require a priori knowledge of the value of the sparsity index $s_0$. This knowledge is almost never available in practice, and misspecification of this parameter can lead to severe deterioration in the performance of existing methods. The main contribution of this paper is to propose an algorithm that does not require prior knowledge of the sparsity index $s_0$ and establish tight regret bounds on its performance under mild conditions. We also comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms existing methods, even when the correct sparsity index is revealed to them but is kept hidden from our algorithm.} }
Endnote
%0 Conference Paper %T Sparsity-Agnostic Lasso Bandit %A Min-Hwan Oh %A Garud Iyengar %A Assaf Zeevi %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-oh21a %I PMLR %P 8271--8280 %U https://proceedings.mlr.press/v139/oh21a.html %V 139 %X We consider a stochastic contextual bandit problem where the dimension $d$ of the feature vectors is potentially large, however, only a sparse subset of features of cardinality $s_0 \ll d$ affect the reward function. Essentially all existing algorithms for sparse bandits require a priori knowledge of the value of the sparsity index $s_0$. This knowledge is almost never available in practice, and misspecification of this parameter can lead to severe deterioration in the performance of existing methods. The main contribution of this paper is to propose an algorithm that does not require prior knowledge of the sparsity index $s_0$ and establish tight regret bounds on its performance under mild conditions. We also comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms existing methods, even when the correct sparsity index is revealed to them but is kept hidden from our algorithm.
APA
Oh, M., Iyengar, G. & Zeevi, A.. (2021). Sparsity-Agnostic Lasso Bandit. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:8271-8280 Available from https://proceedings.mlr.press/v139/oh21a.html.

Related Material