# From Theory to Practice with RAVEN-UCB: Addressing Non-Stationarity in Multi-Armed Bandits through Variance Adaptation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2025.

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

- [BALLAST: Bandit-Assisted Learning for Latency-Aware Stable Timeouts in Raft](https://mlsanity.com/paper/2512.21165/) (2025)

## Abstract (arXiv)

The Multi-Armed Bandit (MAB) problem is challenging in non-stationary environments where reward distributions evolve dynamically. We introduce RAVEN-UCB, a novel algorithm that combines theoretical rigor with practical efficiency via variance-aware adaptation. It achieves tighter regret bounds than UCB1 and UCB-V, with gap-dependent regret of order K σmax2 log T / Delta and gap-independent regret of order √K T log T. RAVEN-UCB incorporates three innovations: (1) variance-driven exploration using √hatσk2 / (Nk + 1) in confidence bounds, (2) adaptive control via αt = α0 / log(t + ε), and (3) constant-time recursive updates for efficiency. Experiments across non-stationary patterns - distributional changes, periodic shifts, and temporary fluctuations - in synthetic and logistics scenarios demonstrate its superiority over state-of-the-art baselines, confirming theoretical and practical robustness.