将扰动法用于无约束线性强化学习，实现更优的后悔率控制。
A Perturbation Approach to Unconstrained Linear Bandits
- 用扰动法把无约束线性Bandit转化为标准在线线性优化问题。
- 首次获得无需预知路径长度的动态后悔率最优√PT依赖关系。
- 给出静态与动态后悔率的高概率保证，适合关注理论性能的研究者。
我们重新审视Abernethy等（2008）提出的经典扰动方法在无约束线性强化学习（uBLO）中的应用。发现该方法在无约束设定下，能将带宽线性优化（BLO）问题转化为标准在线线性优化（OLO）问题。在此框架下，结合自适应比较器的OLO算法，我们推导出期望后悔率的上界，揭示了不同对抗模型对自适应率的影响。同时，我们将分析扩展至动态后悔率，首次获得不依赖于路径长度PT的最优√PT依赖关系，且无需预先知晓PT。进一步，我们建立了uBLO中静态与动态后悔率的首个高概率保证。最后，我们讨论静态后悔率的下界，证明了欧氏球上对抗性线性带宽的常识性Ω(√dT)率，具有独立研究价值。
原文摘要 · Abstract (English)
We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem. Our framework improves on prior work in several ways. First, we derive expected-regret guarantees when our perturbation scheme is combined with comparator-adaptive OLO algorithms, leading to new insights about the impact of different adversarial models on the resulting comparator-adaptive rates. We also extend our analysis to dynamic regret, obtaining the first guarantees with optimal $\sqrt{P_T}$ path-length dependencies without prior knowledge of $P_T$. We then develop the first high-probability guarantees for both static and dynamic regret in uBLO. Finally, we discuss lower bounds on the static regret, and prove the folklore $Ω(\sqrt{dT})$ rate for adversarial linear bandits on the Euclidean ball, which is of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。