An Information-Theoretic Analysis of Nonstationary Bandit Learning
This provides a theoretical framework for understanding regret in nonstationary environments, which is incremental but foundational for bandit learning research.
The paper tackles the problem of nonstationary bandit learning by analyzing attainable performance through an information-theoretic approach, bounding limiting per-period regret in terms of the entropy rate of the optimal action process.
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 limiting 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.