线性赌博机中的自协调扰动方法 (Self-Concordant Perturbations for Linear Bandits)

We study the adversarial linear bandits problem and present a unified algorithmic framework that bridges Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FTPL) methods, extending the known connection between them from the full-information setting. Within this framework, we introduce self-concordant perturbations, a family of probability distributions that mirror the role of self-concordant barriers previously employed in the FTRL-based SCRiBLe algorithm. Using this idea, we design a novel FTPL-based algorithm that combines self-concordant regularization with efficient stochastic exploration. Our approach achieves a regret of $O(d\sqrt{n \ln n})$ on both the $d$-dimensional hypercube and the Euclidean ball. On the Euclidean ball, this matches the rate attained by existing self-concordant FTRL methods. For the hypercube, this represents a $\sqrt{d}$ improvement over these methods and matches the optimal bound up to logarithmic factors.

翻译：本文研究对抗性线性赌博机问题，提出一个统一的算法框架，该框架连接了跟随正则化领导者（FTRL）与跟随扰动领导者（FTPL）方法，将二者在完全信息设定下的已知关联扩展至当前场景。在此框架内，我们引入了自协调扰动——一类概率分布族，其作用类似于先前在基于FTRL的SCRiBLe算法中使用的自协调障碍函数。基于这一思想，我们设计了一种新颖的基于FTPL的算法，将自协调正则化与高效随机探索相结合。我们的方法在$d$维超立方体和欧几里得球上均实现了$O(d\sqrt{n \ln n})$的遗憾界。在欧几里得球上，该结果与现有自协调FTRL方法达到的速率一致；在超立方体上，则相比这些方法实现了$\sqrt{d}$的改进，且在对数因子范围内达到最优界。