Abstract
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 σ_max² log T / Δ and gap-independent regret of order √K T log T. RAVEN-UCB incorporates three innovations: (1) variance-driven exploration using √σ_k² / (N_k + 1) in confidence bounds, (2) adaptive control via α_t = α₀ / 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.