提出新方法实现多臂老虎机问题的最优自适应后悔界。
Data-dependent Bounds with $T$-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits using Stability-Penalty Matching
- 基于实时稳定性惩罚匹配调节学习率
- 对抗与随机场景下均达O(√T)和O(ln T)最优边界
- 适合追求理论最优与数据自适应的算法研究者
现有适用于多臂老虎机问题的数据依赖型与最佳双世界（BOBW）后悔界存在适应性不足的问题：要么仅数据依赖但非BOBW，要么是BOBW但非数据依赖，或在对抗情形下最坏情况保证为次优的O(√T ln T)。为克服这些局限，我们提出实时稳定性惩罚匹配（SPM）方法，首次实现同时具备数据依赖性、最佳双世界特性及在多臂老虎机问题中对T最优的后悔界。具体而言，实时SPM在对抗环境中达到O(√T)最坏情况保证，在随机环境中达到O(ln T)，且同时能自适应数据相关量，如稀疏性、变化度和小损失。该成果通过扩展SPM技术以调制跟随正则化领导者（FTRL）框架中的学习率获得，进一步表明SPM与FTRL结合是证明在线学习中新自适应边界的一种有前景的方法。
原文摘要 · Abstract (English)
Existing data-dependent and best-of-both-worlds regret bounds for multi-armed bandits problems have limited adaptivity as they are either data-dependent but not best-of-both-worlds (BOBW), BOBW but not data-dependent or have sub-optimal $O(\sqrt{T\ln{T}})$ worst-case guarantee in the adversarial regime. To overcome these limitations, we propose real-time stability-penalty matching (SPM), a new method for obtaining regret bounds that are simultaneously data-dependent, best-of-both-worlds and $T$-optimal for multi-armed bandits problems. In particular, we show that real-time SPM obtains bounds with worst-case guarantees of order $O(\sqrt{T})$ in the adversarial regime and $O(\ln{T})$ in the stochastic regime while simultaneously being adaptive to data-dependent quantities such as sparsity, variations, and small losses. Our results are obtained by extending the SPM technique for tuning the learning rates in the follow-the-regularized-leader (FTRL) framework, which further indicates that the combination of SPM and FTRL is a promising approach for proving new adaptive bounds in online learning problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。