# Linear Bandits with Non-i.i.d. Noise

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 26 May 2025.

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

- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures](https://mlsanity.com/paper/2309.14298/) (2023)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)

## Abstract (arXiv)

We study the linear stochastic bandit problem, relaxing the standard i.i.d. assumption on the observation noise. As an alternative to this restrictive assumption, we allow the noise terms across rounds to be sub-Gaussian but interdependent, with dependencies that decay over time. To address this setting, we develop new confidence sequences using a recently introduced reduction scheme to sequential probability assignment, and use these to derive a bandit algorithm based on the principle of optimism in the face of uncertainty. We provide regret bounds for the resulting algorithm, expressed in terms of the decay rate of the strength of dependence between observations. Among other results, we show that our bounds recover the standard rates up to a factor of the mixing time for geometrically mixing observation noise.