# Self-Concordant Perturbations for Linear Bandits

arXiv: https://arxiv.org/abs/2510.24187 · HTML: https://mlsanity.com/paper/2510.24187/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 28 Oct 2025.

## Builds on (most cited first, 10 of 10)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems](https://mlsanity.com/paper/1902.00610/) (2019)
- [Universal Barrier is n-Self-Concordant](https://mlsanity.com/paper/1809.03011/) (2018)
- [The entropic barrier is n-self-concordant](https://mlsanity.com/paper/2112.10947/) (2021)
- [Projected Normal Distribution: Moment Approximations and Generalizations](https://mlsanity.com/paper/2506.17461/) (2025)

## Built on by (most cited first, 1 of 1)

- [Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets](https://mlsanity.com/paper/2610.17818/) (2026)

## Abstract (arXiv)

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(d√n ln n) on both the d-dimensional hypercube and the ℓ2 ball. On the ℓ2 ball, this matches the rate attained by SCRiBLe. For the hypercube, this represents a √d improvement over these methods and matches the optimal bound up to logarithmic factors.