An Information-Theoretic Analysis of Nonstationary Bandit Learning
Abstract
In nonstationary bandit learning problems, the decision-maker must continually gather information and adapt their action selection as the latent state of the environment evolves. In each time period, some latent optimal action maximizes expected reward under the environment state. We view the optimal action sequence as a stochastic process, and take an information-theoretic approach to analyze attainable performance. We bound per-period regret in terms of the entropy rate of the optimal action process. The bound applies to a wide array of problems studied in the literature and reflects the problem’s information structure through its information-ratio.
Cite
Text
Min and Russo. "An Information-Theoretic Analysis of Nonstationary Bandit Learning." International Conference on Machine Learning, 2023.Markdown
[Min and Russo. "An Information-Theoretic Analysis of Nonstationary Bandit Learning." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/min2023icml-informationtheoretic/)BibTeX
@inproceedings{min2023icml-informationtheoretic,
title = {{An Information-Theoretic Analysis of Nonstationary Bandit Learning}},
author = {Min, Seungki and Russo, Daniel},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {24831-24849},
volume = {202},
url = {https://mlanthology.org/icml/2023/min2023icml-informationtheoretic/}
}