# Restless Linear Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 14 references that are in the map.
- First posted on arXiv 17 May 2024.

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

- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Approximations of the Restless Bandit Problem](https://mlsanity.com/paper/1702.06972/) (2017)
- [Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processes](https://mlsanity.com/paper/2402.07296/) (2024)

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

- [Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds](https://mlsanity.com/paper/2610.20007/) (2026)

## Abstract (arXiv)

A more general formulation of the linear bandit problem is considered to allow for dependencies over time. Specifically, it is assumed that there exists an unknown ℝd-valued stationary varphi-mixing sequence of parameters (θt,~t ∈ mathbbN) which gives rise to pay-offs. This instance of the problem can be viewed as a generalization of both the classical linear bandits with iid noise, and the finite-armed restless bandits. In light of the well-known computational hardness of optimal policies for restless bandits, an approximation is proposed whose error is shown to be controlled by the varphi-dependence between consecutive θt. An optimistic algorithm, called LinMix-UCB, is proposed for the case where θt has an exponential mixing rate. The proposed algorithm is shown to incur a sub-linear regret of Oleft(√d npolylog(n) right) with respect to an oracle that always plays a multiple of mathbbEθt. The main challenge in this setting is to ensure that the exploration-exploitation strategy is robust against long-range dependencies. The proposed method relies on Berbee's coupling lemma to carefully select near-independent samples and construct confidence ellipsoids around empirical estimates of mathbbEθt.