A Simple Unified Framework for High Dimensional Bandit Problems

Wenjie Li, Adarsh Barik, Jean Honorio
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:12619-12655, 2022.

Abstract

Stochastic high dimensional bandit problems with low dimensional structures are useful in different applications such as online advertising and drug discovery. In this work, we propose a simple unified algorithm for such problems and present a general analysis framework for the regret upper bound of our algorithm. We show that under some mild unified assumptions, our algorithm can be applied to different high-dimensional bandit problems. Our framework utilizes the low dimensional structure to guide the parameter estimation in the problem, therefore our algorithm achieves the comparable regret bounds in the LASSO bandit as a sanity check, as well as novel bounds that depend logarithmically on dimensions in the low-rank matrix bandit, the group sparse matrix bandit, and in a new problem: the multi-agent LASSO bandit.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-li22a, title = {A Simple Unified Framework for High Dimensional Bandit Problems}, author = {Li, Wenjie and Barik, Adarsh and Honorio, Jean}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {12619--12655}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/li22a/li22a.pdf}, url = {https://proceedings.mlr.press/v162/li22a.html}, abstract = {Stochastic high dimensional bandit problems with low dimensional structures are useful in different applications such as online advertising and drug discovery. In this work, we propose a simple unified algorithm for such problems and present a general analysis framework for the regret upper bound of our algorithm. We show that under some mild unified assumptions, our algorithm can be applied to different high-dimensional bandit problems. Our framework utilizes the low dimensional structure to guide the parameter estimation in the problem, therefore our algorithm achieves the comparable regret bounds in the LASSO bandit as a sanity check, as well as novel bounds that depend logarithmically on dimensions in the low-rank matrix bandit, the group sparse matrix bandit, and in a new problem: the multi-agent LASSO bandit.} }
Endnote
%0 Conference Paper %T A Simple Unified Framework for High Dimensional Bandit Problems %A Wenjie Li %A Adarsh Barik %A Jean Honorio %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-li22a %I PMLR %P 12619--12655 %U https://proceedings.mlr.press/v162/li22a.html %V 162 %X Stochastic high dimensional bandit problems with low dimensional structures are useful in different applications such as online advertising and drug discovery. In this work, we propose a simple unified algorithm for such problems and present a general analysis framework for the regret upper bound of our algorithm. We show that under some mild unified assumptions, our algorithm can be applied to different high-dimensional bandit problems. Our framework utilizes the low dimensional structure to guide the parameter estimation in the problem, therefore our algorithm achieves the comparable regret bounds in the LASSO bandit as a sanity check, as well as novel bounds that depend logarithmically on dimensions in the low-rank matrix bandit, the group sparse matrix bandit, and in a new problem: the multi-agent LASSO bandit.
APA
Li, W., Barik, A. & Honorio, J.. (2022). A Simple Unified Framework for High Dimensional Bandit Problems. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:12619-12655 Available from https://proceedings.mlr.press/v162/li22a.html.

Related Material