Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs

Ian A. Kash, Lev Reyzin, Zishun Yu
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:683-718, 2024.

Abstract

Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon tabular reinforcement learning to multi-armed bandits, where, specifically, an independent bandit learner is placed in each state. We show that, under ergodicity and fast mixing assumptions, any slowly changing adversarial bandit algorithm achieving optimal regret in the adversarial bandit setting can also attain optimal expected regret in infinite-horizon discounted Markov decision processes, with respect to the number of rounds $T$. Furthermore, we examine our reduction using a specific instance of the exponential-weight algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v237-kash24a, title = {Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs}, author = {Kash, Ian A. and Reyzin, Lev and Yu, Zishun}, booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory}, pages = {683--718}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/kash24a/kash24a.pdf}, url = {https://proceedings.mlr.press/v237/kash24a.html}, abstract = {Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon tabular reinforcement learning to multi-armed bandits, where, specifically, an independent bandit learner is placed in each state. We show that, under ergodicity and fast mixing assumptions, any slowly changing adversarial bandit algorithm achieving optimal regret in the adversarial bandit setting can also attain optimal expected regret in infinite-horizon discounted Markov decision processes, with respect to the number of rounds $T$. Furthermore, we examine our reduction using a specific instance of the exponential-weight algorithm.} }
Endnote
%0 Conference Paper %T Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs %A Ian A. Kash %A Lev Reyzin %A Zishun Yu %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-kash24a %I PMLR %P 683--718 %U https://proceedings.mlr.press/v237/kash24a.html %V 237 %X Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon tabular reinforcement learning to multi-armed bandits, where, specifically, an independent bandit learner is placed in each state. We show that, under ergodicity and fast mixing assumptions, any slowly changing adversarial bandit algorithm achieving optimal regret in the adversarial bandit setting can also attain optimal expected regret in infinite-horizon discounted Markov decision processes, with respect to the number of rounds $T$. Furthermore, we examine our reduction using a specific instance of the exponential-weight algorithm.
APA
Kash, I.A., Reyzin, L. & Yu, Z.. (2024). Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:683-718 Available from https://proceedings.mlr.press/v237/kash24a.html.

Related Material