Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908725337391104 |
|---|---|
| author | Krishnamurthy, Vikram |
| author_facet | Krishnamurthy, Vikram |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18409 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem Krishnamurthy, Vikram Machine Learning Systems and Control 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. |
| title | Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem |
| topic | Machine Learning Systems and Control |
| url | https://arxiv.org/abs/2512.18409 |