{"ID":2826779,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.18409","arxiv_id":"2512.18409","title":"Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem","abstract":"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.","short_abstract":"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-probabil...","url_abs":"https://arxiv.org/abs/2512.18409","url_pdf":"https://arxiv.org/pdf/2512.18409v1","authors":"[\"Vikram Krishnamurthy\"]","published":"2025-12-20T16:11:55Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"eess.SY\",\"stat.ML\"]","methods":"[]","has_code":false}