2025/06/03 by Fang, Junyi, Chen, Yuxun, Chen, Yuxin +1 · 1 citation
#FOS: Computer and information sciences #G.3 #I.2.6 #I.2.8 #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2506.02933
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 / Δ and gap-independent regret of order √(K T log T). RAVEN-UCB incorporates three innovations: (1) variance-driven exploration using √(σ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.