统一解释多种强化学习算法的后悔上界分析逻辑。
Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem
- 仅需一个概率集中条件，即可推导出对数后悔上界。
- 通过确定性引理证明估计误差收敛与乐观偏差。
- 适用于经典及现代多臂赌博机算法，分析更简洁。
多种基于乐观策略的随机多臂赌博机算法（如UCB、UCB-V、线性UCB、有限臂高斯过程UCB）均能实现对数后悔率，尽管证明表面差异明显，但其分析结构本质相同。本文提炼出分析的核心要素：仅需一个关于估计器的概率集中条件，随后通过两个简短的确定性引理（半径收缩与乐观强制偏差）即可推出对数后悔结果。该框架为经典算法提供了统一且近乎最小化的证明，并可自然扩展至众多现代赌博机变体。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。