Multiplier Bootstrap-based Exploration

Runzhe Wan, Haoyu Wei, Branislav Kveton, Rui Song
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:35444-35490, 2023.

Abstract

Despite the great interest in the bandit problem, designing efficient algorithms for complex models remains challenging, as there is typically no analytical way to quantify uncertainty. In this paper, we propose Multiplier Bootstrap-based Exploration (MBE), a novel exploration strategy that is applicable to any reward model amenable to weighted loss minimization. We prove both instance-dependent and instance-independent rate-optimal regret bounds for MBE in sub-Gaussian multi-armed bandits. With extensive simulation and real-data experiments, we show the generality and adaptivity of MBE.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-wan23d, title = {Multiplier Bootstrap-based Exploration}, author = {Wan, Runzhe and Wei, Haoyu and Kveton, Branislav and Song, Rui}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {35444--35490}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/wan23d/wan23d.pdf}, url = {https://proceedings.mlr.press/v202/wan23d.html}, abstract = {Despite the great interest in the bandit problem, designing efficient algorithms for complex models remains challenging, as there is typically no analytical way to quantify uncertainty. In this paper, we propose Multiplier Bootstrap-based Exploration (MBE), a novel exploration strategy that is applicable to any reward model amenable to weighted loss minimization. We prove both instance-dependent and instance-independent rate-optimal regret bounds for MBE in sub-Gaussian multi-armed bandits. With extensive simulation and real-data experiments, we show the generality and adaptivity of MBE.} }
Endnote
%0 Conference Paper %T Multiplier Bootstrap-based Exploration %A Runzhe Wan %A Haoyu Wei %A Branislav Kveton %A Rui Song %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-wan23d %I PMLR %P 35444--35490 %U https://proceedings.mlr.press/v202/wan23d.html %V 202 %X Despite the great interest in the bandit problem, designing efficient algorithms for complex models remains challenging, as there is typically no analytical way to quantify uncertainty. In this paper, we propose Multiplier Bootstrap-based Exploration (MBE), a novel exploration strategy that is applicable to any reward model amenable to weighted loss minimization. We prove both instance-dependent and instance-independent rate-optimal regret bounds for MBE in sub-Gaussian multi-armed bandits. With extensive simulation and real-data experiments, we show the generality and adaptivity of MBE.
APA
Wan, R., Wei, H., Kveton, B. & Song, R.. (2023). Multiplier Bootstrap-based Exploration. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:35444-35490 Available from https://proceedings.mlr.press/v202/wan23d.html.

Related Material