# An Information-Theoretic Analysis of Nonstationary Bandit Learning

arXiv: https://arxiv.org/abs/2302.04452 · HTML: https://mlsanity.com/paper/2302.04452/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 9 Feb 2023.

## Builds on (most cited first, 23 of 23)

- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Taming Non-stationary Bandits: A Bayesian Approach](https://mlsanity.com/paper/1707.09727/) (2017)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Information Directed Sampling for Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1711.03198/) (2017)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret](https://mlsanity.com/paper/2202.10997/) (2022)
- [A Change-Detection Based Thompson Sampling Framework for Non-Stationary Bandits](https://mlsanity.com/paper/2009.02791/) (2020)
- [Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection](https://mlsanity.com/paper/1302.3721/) (2013)

## Built on by (most cited first, 11 of 11)

- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Contextual Thompson Sampling via Generation of Missing Data](https://mlsanity.com/paper/2502.07064/) (2025)
- [Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Models](https://mlsanity.com/paper/2601.22538/) (2026)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Information-directed sampling for bandits: a primer](https://mlsanity.com/paper/2512.20096/) (2025)
- [On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization](https://mlsanity.com/paper/2603.18514/) (2026)
- [Bandit Learning in General Open Multi-agent Systems](https://mlsanity.com/paper/2605.06202/) (2026)
- [Experimentation and Commitment under Reward Shifts](https://mlsanity.com/paper/2607.23432/) (2026)
- [Future Information-Directed Sampling for Bayesian Nonstationary Bandits](https://mlsanity.com/paper/2609.33981/) (2026)

## Abstract (arXiv)

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.