首次给出KL正则化老虎机问题的近最优后悔上界，揭示正则强度影响规律。
Near-Optimal Regret for KL-Regularized Multi-Armed Bandits
- 用新颖的分层论证分析KL-UCB算法，获得线性依赖臂数K的上界。
- 首次证明Ω(ηK log T)下界，验证上界几乎紧致。
- 覆盖所有正则强度范围，适合关注在线学习理论的研究者。
近期研究显示，带有KL正则化的强化学习可实现更快收敛速度或对数后悔，优于经典无正则设置下的√T型后悔。然而，针对多臂老虎机（MAB）的KL正则化在线学习的统计效率仍不明确。本文通过新颖的分层论证，对KL-UCB进行精确分析，得到一个˜O(ηK log²T)的高概率后悔上界：首个关于K呈线性依赖的上界。其中，T为时间范围，K为臂的数量，η⁻¹为正则强度。该分析的近紧性由首个非恒定下界Ω(ηK log T)证实，源于精细的困难实例构造与贝叶斯先验的定制分解。此外，在低正则化区间（即大η值），我们证明了后悔量与η无关，其规模为˜Θ(√KT)。整体结果在η、K、T三个参数上提供了近乎最优的界限，全面刻画了各正则强度下的行为。
原文摘要 · Abstract (English)
Recent studies have shown that reinforcement learning with KL-regularized objectives can enjoy faster rates of convergence or logarithmic regret, in contrast to the classical $\sqrt{T}$-type regret in the unregularized setting. However, the statistical efficiency of online learning with respect to KL-regularized objectives remains far from completely characterized, even when specialized to multi-armed bandits (MABs). We address this problem for MABs via a sharp analysis of KL-UCB using a novel peeling argument, which yields a $\tilde{O}(ηK\log^2T)$ upper bound: the first high-probability regret bound with linear dependence on $K$. Here, $T$ is the time horizon, $K$ is the number of arms, $η^{-1}$ is the regularization intensity, and $\tilde{O}$ hides all logarithmic factors except those involving $\log T$. The near-tightness of our analysis is certified by the first non-constant lower bound $Ω(ηK \log T)$, which follows from subtle hard-instance constructions and a tailored decomposition of the Bayes prior. Moreover, in the low-regularization regime (i.e., large $η$), we show that the KL-regularized regret for MABs is $η$-independent and scales as $\tildeΘ(\sqrt{KT})$. Overall, our results provide a thorough understanding of KL-regularized MABs across all regimes of $η$ and yield nearly optimal bounds in terms of $K$, $η$, and $T$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。