{"ID":2848983,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.24187","arxiv_id":"2510.24187","title":"Self-Concordant Perturbations for Linear Bandits","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 $\\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.","short_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-concord...","url_abs":"https://arxiv.org/abs/2510.24187","url_pdf":"https://arxiv.org/pdf/2510.24187v2","authors":"[\"Lucas Lévy\",\"Jean-Lou Valeau\",\"Arya Akhavan\",\"Patrick Rebeschini\"]","published":"2025-10-28T08:47:15Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\"]","methods":"[\"LoRA\"]","has_code":false}