Self-Concordant Perturbations for Linear Bandits

arXiv:2510.24187v3 Announce Type: replace-cross Abstract: 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 O(dsqrt{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.

Source: arXiv cs.LG | 2026-06-29