# Autoregressive Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 42 references that are in the map.
- First posted on arXiv 12 Dec 2022.

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

- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [Dynamic Pricing with Volume Discounts in Online Settings](https://mlsanity.com/paper/2211.09612/) (2022)

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

- [Non-Stationary Latent Auto-Regressive Bandits](https://mlsanity.com/paper/2402.03110/) (2024)
- [Long-Context Linear System Identification](https://mlsanity.com/paper/2410.05690/) (2024)
- [Fixed-Confidence Best Arm Identification with Decreasing Variance](https://mlsanity.com/paper/2502.07199/) (2025)

## Abstract (arXiv)

Autoregressive processes naturally arise in a large variety of real-world scenarios, including stock markets, sales forecasting, weather prediction, advertising, and pricing. When facing a sequential decision-making problem in such a context, the temporal dependence between consecutive observations should be properly accounted for guaranteeing convergence to the optimal policy. In this work, we propose a novel online learning setting, namely, Autoregressive Bandits (ARBs), in which the observed reward is governed by an autoregressive process of order k, whose parameters depend on the chosen action. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. Then, we devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order widetildeO left( frac(k+1)3/2√nT(1-Gamma)2right), where T is the optimization horizon, n is the number of actions, and Gamma < 1 is a stability index of the process. Finally, we empirically validate our algorithm, illustrating its advantages w.r.t. bandit baselines and its robustness to misspecification of key parameters.