提出新型扰动方法，显著提升线性带宽问题的决策效率。
Self-Concordant Perturbations for Linear Bandits
- 用自洽扰动统一FTRL与FTPL算法框架
- 在超立方体上实现d√(n ln n)的最优后悔率
- 适合关注在线学习与优化理论的研究者
我们研究对抗性线性带宽问题，提出一个统一的算法框架，连接了基于正则化的追随领导者（FTRL）与追随扰动领导者（FTPL）方法，将二者在完整信息设置中的关联扩展至带宽场景。在此框架中，我们引入自洽扰动，一类概率分布家族，其作用类似于先前SCRiBLe算法中使用的自洽障碍函数。基于此，设计了一种新的基于FTPL的算法，结合自洽正则化与高效的随机探索。该方法在d维超立方体和ℓ₂球上均达到$/mathcal{O}(d oot{n} m{ln}n)$的后悔率。在ℓ₂球上，该结果与SCRiBLe算法一致；在超立方体上，则相比以往方法有√d的改进，并达到最优边界，仅差对数因子。
原文摘要 · Abstract (English)
We consider the adversarial linear bandits setting 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 $\mathcal{O}(d\sqrt{n \ln n})$ on both the $d$-dimensional hypercube and the $\ell_2$ ball. On the $\ell_2$ ball, this matches the rate attained by SCRiBLe. For the hypercube, this represents a $\sqrt{d}$ improvement over these methods and matches the optimal bound up to logarithmic factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。