# Non-Stationary Bandits with Auto-Regressive Temporal Dependency

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 51 references that are in the map.
- First posted on arXiv 28 Oct 2022.

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

- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Learning and Optimization with Seasonal Patterns](https://mlsanity.com/paper/2005.08088/) (2020)
- [Approximations of the Restless Bandit Problem](https://mlsanity.com/paper/1702.06972/) (2017)

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

- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [Survey: Multi-Armed Bandits Meet Large Language Models](https://mlsanity.com/paper/2505.13355/) (2025)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Autoregressive Bandits](https://mlsanity.com/paper/2212.06251/) (2022)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Non-Stationary Latent Auto-Regressive Bandits](https://mlsanity.com/paper/2402.03110/) (2024)
- [Restless Linear Bandits](https://mlsanity.com/paper/2405.10817/) (2024)
- [Restless Bandit Problem with Rewards Generated by a Linear Gaussian Dynamical System](https://mlsanity.com/paper/2405.09584/) (2024)
- [An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical System](https://mlsanity.com/paper/2504.03926/) (2025)
- [Constrained user-item allocation for e-commerce marketing campaigns](https://mlsanity.com/paper/2606.09623/) (2026)

## Abstract (arXiv)

Traditional multi-armed bandit (MAB) frameworks, predominantly examined under stochastic or adversarial settings, often overlook the temporal dynamics inherent in many real-world applications such as recommendation systems and online advertising. This paper introduces a novel non-stationary MAB framework that captures the temporal structure of these real-world dynamics through an auto-regressive (AR) reward structure. We propose an algorithm that integrates two key mechanisms: (i) an alternation mechanism adept at leveraging temporal dependencies to dynamically balance exploration and exploitation, and (ii) a restarting mechanism designed to discard out-of-date information. Our algorithm achieves a regret upper bound that nearly matches the lower bound, with regret measured against a robust dynamic benchmark. Finally, via a real-world case study on tourism demand prediction, we demonstrate both the efficacy of our algorithm and the broader applicability of our techniques to more complex, rapidly evolving time series.