Adaptive Algorithm for Multi-Armed Bandit Problem with High-Dimensional Covariates

Abstract

This article studies an important sequential decision making problem known as the multi-armed stochastic bandit problem with covariates. Under a linear bandit framework with high-dimensional covariates, we propose a general multi-stage arm allocation algorithm that integrates both arm elimination and randomized assignment strategies. By employing a class of high-dimensional regression methods for coefficient estimation, the proposed algorithm is shown to have near optimal finite-time regret performance under a new study scope that requires neither a margin condition nor a reward gap condition for competitive arms. Based on the synergistically verified benefit of the margin, our algorithm exhibits adaptive performance that automatically adapts to the margin and gap conditions, and attains optimal regret rates simultaneously for both study scopes, without or with the margin, up to a logarithmic factor. Besides the desirable regret performance, the proposed algorithm simultaneously generates useful coefficient estimation output for competitive arms and is shown to achieve both estimation consistency and variable selection consistency. Promising empirical performance is demonstrated through extensive simulation and two real data evaluation examples. Supplementary materials for this article are available online.

KEYWORDS:

• Contextual bandits
• Exploration-exploitation tradeoff
• High-dimensional regression model
• Sequential decision making
• Stepwise regression procedure

Supplementary Materials

Supplement to “Adaptive Algorithm for Multi-armed Bandit Problem with High-dimensional Covariates” (supplement.pdf): Supplement A provides the proofs of the propositions and the main theorems. The technical ancillary lemmas for the theorems are relegated to Supplement B. Our simulation studies are given in Supplement C.

Acknowledgments

The authors sincerely thank the Editor, the Associate Editor, and three anonymous referees for their valuable comments that helped improve this manuscript significantly.

Data Availability Statement

MATLAB package for the IGA method is available at https://github.com/weiqian1/IGA.

Disclosure Statement

The authors report there are no competing interests to declare.

Additional information

Funding

Ching-Kang Ing is partially supported by the Science Vanguard Research Program of the Ministry of Science and Technology, Taiwan. Wei Qian is partially supported by NSF DMS-1916376, NIH R21NS122033A, and JPMC Faculty Fellowship.