2025/12/20 by Vikram Krishnamurthy, Krishnamurthy, Vikram
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.2512.18409
openalex publication_date 2025/12/20 · openalex created_date 2025/12/24 · openalex updated_date 2026/07/28
Several optimism-based stochastic bandit algorithms -- including UCB, UCB-V, linear UCB, and finite-arm GP-UCB -- achieve logarithmic regret using proofs that, despite superficial differences, follow essentially the same structure. This note isolates the minimal ingredients behind these analyses: a single high-probability concentration condition on the estimators, after which logarithmic regret follows from two short deterministic lemmas describing radius collapse and optimism-forced deviations. The framework yields unified, near-minimal proofs for these classical algorithms and extends naturally to many contemporary bandit variants.