mlsanityData to 14 Oct 2026

An Information-Theoretic Analysis of Nonstationary Bandit Learning

arXiv 2302.04452 ↗First posted 9 Feb 2023cs.LG cs.IT math.ITcited by 11

Not on the map. Why?

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.

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

23 of 47 references.

References · 23

  1. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  2. 2013Non-stationary Stochastic Optimizationcited by 175
  3. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  4. 2018Learning to Optimize under Non-Stationaritycited by 85
  5. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  6. 2020Mirror Descent and the Information Ratiocited by 40
  7. 2018Satisficing in Time-Sensitive Bandit Learningcited by 39
  8. 2019Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problemscited by 34
  9. 2020Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisationcited by 33
  10. 2022On the Complexity of Adversarial Decision Makingcited by 33
  11. 2017Taming Non-stationary Bandits: A Bayesian Approachcited by 32
  12. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
11 more
  1. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  2. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  3. 2017Information Directed Sampling for Stochastic Bandits with Graph Feedbackcited by 24
  4. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  5. 2015Multi-scale exploration of convex functions and bandit convex optimizationcited by 20
  6. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  7. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  8. 2022Contextual Information-Directed Samplingcited by 16
  9. 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 14
  10. 2020A Change-Detection Based Thompson Sampling Framework for Non-Stationary Banditscited by 10
  11. 2013Thompson Sampling in Switching Environments with Bayesian Online Change Point Detectioncited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 2; 2026: 5.

11 papers.

  1. 2023A Stability Principle for Learning under Non-Stationaritycited by 10
  2. 2023A Definition of Non-Stationary Banditscited by 9
  3. 2024Optimistic Information Directed Samplingcited by 7
  4. 2025Contextual Thompson Sampling via Generation of Missing Datacited by 6
  5. 2026Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Modelscited by 6
  6. 2024On Bits and Bandits: Quantifying the Regret-Information Trade-offcited by 3
  7. 2025Information-directed sampling for bandits: a primercited by 0
  8. 2026On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimizationcited by 0
  9. 2026Bandit Learning in General Open Multi-agent Systemscited by 0
  10. 2026Experimentation and Commitment under Reward Shiftscited by 0
  11. 2026Future Information-Directed Sampling for Bayesian Nonstationary Banditscited by 0