📊 statistics

Self-Concordant Perturbations for Linear Bandits

This paper introduces a unified framework bridging FTRL and FTPL methods for adversarial linear bandits by utilizing self-concordant perturbations, resulting in a novel algorithm that achieves an optimal $\mathcal{O}(d\sqrt{n \ln n})$ regret bound on both the hypercube and $\ell_2$ ball.

Original authors: Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini

Published 2026-06-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a high-stakes game of "Guess the Best Move" against a cunning opponent. You have a giant box of possible moves (the action set), but you don't know which one is the best. Every time you pick a move, the opponent tells you only how bad that specific move was, but they keep the scores of all the other moves a secret. Your goal is to pick the best moves over time so that your total score is as close as possible to the score you would have gotten if you had known the best move from the very beginning. This difference is called regret.

This paper introduces a new, smarter way to play this game, specifically when the "moves" are mathematical points in a multi-dimensional space (like a giant hypercube or a ball).

Here is the breakdown of their discovery, explained simply:

The Two Old Ways of Playing

Before this paper, there were two main strategies for this game:

The "Regularized Leader" (FTRL): Imagine you are a cautious planner. You keep a running tally of past mistakes and add a "penalty" for being too risky. You calculate the best move based on this penalty. To learn about the hidden moves, you have to deliberately pick a "safe" but slightly random move just to gather information. This is like a chef tasting a tiny bit of every ingredient to see if it's good, even if it slows down the cooking.
The "Perturbed Leader" (FTPL): Imagine you are a chaotic improviser. You take your running tally of mistakes, but before you pick a move, you add a little bit of "noise" or "static" to your brain (a random perturbation). This noise makes you pick a different move than you normally would. Because you are naturally jittery, you explore the board without needing a special "tasting" step.

The Problem

The "chaotic" FTPL method is great at exploring, but it was hard to prove it was mathematically perfect for complex shapes (like a ball or a cube). The "cautious" FTRL method was mathematically solid but sometimes explored too slowly, leading to a higher "regret" (more mistakes) on certain shapes.

The New Solution: "Self-Concordant Perturbations"

The authors created a bridge between these two worlds. They invented a new type of "noise" (perturbation) that acts like a magic compass.

The Analogy: Think of the "action set" as a room with walls. In the old methods, the noise was like throwing darts randomly; sometimes they hit the wall, sometimes the floor.
The Innovation: The authors designed a specific type of noise that knows the shape of the room perfectly. They call this "Self-Concordant Perturbation."
- It mimics the mathematical properties of the "cautious" method (FTRL), ensuring the player stays safe and doesn't make huge errors.
- But, it keeps the "chaotic" nature of the FTPL method, meaning the player naturally explores the corners and edges of the room without needing a separate, clumsy exploration step.

The Results: Two Different Rooms

The team tested their new algorithm (called SC-FTPL) in two specific "rooms":

The Hypercube (A giant, multi-dimensional box):
- The Old Way: The cautious method was slow here, making a mistake factor of $\sqrt{d}$ (where $d$ is the number of dimensions).
- The New Way: SC-FTPL was much faster. It reduced the mistakes by a factor of $\sqrt{d}$ . It essentially matched the theoretical "best possible" performance for this shape. It's like the player suddenly realizing they can run through the box much more efficiently because they aren't wasting time checking every single corner manually.
The $\ell_2$ Ball (A perfect sphere):
- The Old Way: The cautious method was already quite good here.
- The New Way: SC-FTPL performed just as well as the best existing method. It didn't beat the record, but it proved that the "chaotic" approach could be just as mathematically perfect as the "cautious" one, without needing complex extra steps.

Why This Matters

The paper shows that you don't have to choose between being a cautious planner or a chaotic explorer. By using this new "magic noise" (self-concordant perturbations), you can be a chaotic explorer who naturally learns the shape of the game board perfectly.

For the Box: They found a way to play perfectly efficiently.
For the Ball: They proved the chaotic method works just as well as the best cautious method.

In short, they built a unified framework that makes the "chaotic" strategy just as powerful and mathematically sound as the "cautious" one, leading to fewer mistakes and faster learning in these complex games.

Technical Summary: Self-Concordant Perturbations for Linear Bandits

Problem Setting
The paper addresses the problem of adversarial linear bandits, an online optimization setting where an agent sequentially selects actions $a_t$ from a convex body $K \subset \mathbb{R}^d$ . At each round, the agent suffers a loss $\langle y_t, a_t \rangle$ determined by an unknown loss vector $y_t$ , receiving only this scalar feedback. The objective is to minimize regret, defined as the difference between the agent's cumulative loss and the cumulative loss of the best fixed action in hindsight.

Two primary algorithmic families exist for this setting: Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FTPL). While a unified framework (GBPA) connects these in the full-information setting, the distinction is critical in bandits: FTRL requires explicit stochastic exploration mechanisms, whereas FTPL is inherently stochastic, selecting actions from the extreme points of the action set. Existing optimal-rate algorithms often rely on complex, domain-specific preprocessing or exploration schemes (e.g., spanning ellipsoids) rather than arising naturally from the self-concordant barrier framework used in the SCRIBLE algorithm. SCRIBLE achieves a regret of $O(d^{3/2}\sqrt{n \ln n})$ on general convex bodies and $O(d\sqrt{n \ln n})$ on the $\ell_2$ ball, but suffers from suboptimal exploration variance on the hypercube.

Methodology: The SC-FTPL Framework
The authors introduce BANDITS-GBPA, a unifying framework extending the full-information GBPA to the bandit setting. This framework separates the algorithm into a potential function $\Phi$ , a sampling scheme $S$ , and an estimation scheme $E$ .

Within this framework, the paper proposes the Self-Concordant Follow-the-Perturbed-Leader (SC-FTPL) algorithm. The core innovation is the introduction of self-concordant perturbations.

Definition: A probability distribution $D$ on $\mathbb{R}^d$ is a $\vartheta$ -self-concordant perturbation for a convex body $K$ if there exists a $\vartheta$ -self-concordant barrier $R$ on $K$ such that the gradient of the Fenchel conjugate of $R$ equals the expectation of the gradient of the support function of $K$ under the perturbation:
$\nabla R^*(\theta) = \mathbb{E}_{\xi \sim D}[\nabla \phi_K(\theta + \xi)]$
This definition ensures that the perturbation distribution $D$ "replicates" the geometric properties of the self-concordant barrier $R$ within an FTPL context.
Algorithm: SC-FTPL maintains a cumulative estimate of losses $\hat{Y}_{t-1}$ . At each step, it samples a perturbation $\xi_t \sim D$ and selects the action:
$a_t = \arg \min_{a \in K} \langle a, \eta \hat{Y}_{t-1} - \xi_t \rangle$
The loss vector is estimated using the standard inverse second-moment matrix estimator $\hat{y}_t = Q_t^{-1} a_t \langle y_t, a_t \rangle$ , where $Q_t = \mathbb{E}_{t-1}[a_t a_t^\top]$ .

Key Contributions

Unified Framework (BANDITS-GBPA): The authors formalize a framework that encompasses both FTRL and FTPL approaches for linear bandits, extending the GBPA analysis from full-information to bandit feedback. Unlike the full-information setting, FTPL is not strictly a subset of FTRL here, but the framework allows for a common analytical structure.
Self-Concordant Perturbations: The paper identifies and analyzes a family of perturbation distributions that replicate the properties of self-concordant barriers. This bridges the gap between the regularization properties of SCRIBLE and the inherent exploration of FTPL.
Explicit Constructions: The authors construct specific self-concordant perturbations for two canonical action sets:
- Hypercube $[-1, 1]^d$ : Using the entropic barrier, they derive a perturbation with independent marginals.
- $\ell_2$ Ball $B_d$ : Using the log-barrier, they construct a perturbation based on a scaled multivariate $t$ -distribution.

Results and Regret Bounds
The paper provides regret guarantees for SC-FTPL on the hypercube and the $\ell_2$ ball, assuming appropriate learning rates and horizon conditions ( $n/\ln n$ sufficiently large relative to dimension).

Hypercube: SC-FTPL achieves a regret bound of $O(d\sqrt{n \ln n})$ .
- This matches the minimax lower bound established by Dani et al. (2007) up to logarithmic factors.
- It represents a $\sqrt{d}$ improvement over the SCRIBLE algorithm (which achieves $O(d^{3/2}\sqrt{n \ln n})$ on the hypercube).
- The improvement stems from the FTPL sampling scheme concentrating on extreme points, which reduces the variance of the loss vector estimator in the local norm compared to the Dikin ellipsoid sampling used by SCRIBLE.
- The per-round computational complexity is $O(d)$ .
$\ell_2$ Ball: SC-FTPL achieves a regret bound of $O(d\sqrt{n \ln n})$ .
- This matches the performance of SCRIBLE on the $\ell_2$ ball.
- The analysis for this case is more complex because the local norm of the estimator does not admit a uniform almost-sure bound independent of the cumulative loss estimate. The authors employ a novel argument involving a supermartingale and stopping time arguments (using Ville's inequality) to control the growth of the cumulative estimator and handle the lack of uniform bounds.
- The per-round computational complexity is also $O(d)$ .

Significance and Claims
The paper claims that SC-FTPL provides a unified, perturbation-based approach to linear bandits that recovers the benefits of self-concordant regularization without requiring the explicit, often complex, exploration mechanisms of FTRL-based methods.

Optimality on the Hypercube: The primary significance lies in achieving the optimal rate on the hypercube without domain-specific sampling schemes, improving upon the state-of-the-art SCRIBLE algorithm by a factor of $\sqrt{d}$ .
Theoretical Bridge: The work demonstrates that FTPL can be rigorously analyzed using the machinery of self-concordant barriers, provided the perturbations are chosen to replicate the barrier's geometry.
Modesty on Generalization: The authors note that while they construct perturbations for the hypercube and $\ell_2$ ball, the existence of self-concordant perturbations for general convex bodies remains an open question. They also acknowledge that the regret bound on the $\ell_2$ ball matches SCRIBLE but does not improve upon it, and the analysis required additional technical machinery (stopping times) not needed for the hypercube case.

The paper concludes by identifying open directions, including determining if the $O(d\sqrt{n \ln n})$ rate is tight for FTPL on the $\ell_2$ ball for any perturbation scheme, and investigating whether the entropic barrier (a universal self-concordant barrier) admits a corresponding perturbation distribution for general convex bodies.