In the world of online machine learning, the "Linear Bandit" problem is a classic. A learner must repeatedly choose actions from a set, observing a loss for each choice. The goal is to minimize regret—the difference between the learner's total loss and the loss they would have incurred by picking the single best action from the start.
Traditionally, algorithms are designed for one of two environments: stochastic (where losses follow a fixed, predictable distribution) or adversarial (where an opponent can change losses to trick the learner). Recently, researchers have sought "Best-of-Both-Worlds" (BOBW) algorithms that perform optimally in both.
This paper, "Best-of-Both-Worlds FTRL for Linear Bandits," makes a significant leap forward by showing that a single, elegant framework can achieve state-of-the-art performance across these regimes and even handle data corruption.
TL;DR
The authors introduce IA-FTRL, the first algorithm based purely on the "Follow-the-Regularized-Leader" framework that achieves optimal instance-dependent regret in stochastic linear bandits while remaining robust in adversarial settings. They also extend these guarantees to infinite action sets by identifying a geometric property called "sharpness," resolving several long-standing open problems in the field.
What Problem Does This Paper Address?
The core challenge in BOBW linear bandits is the "information acquisition" cost. In a stochastic setting, some actions are more "informative" than others—they help you learn the underlying loss vector faster, even if they have a higher immediate cost. The optimal regret is characterized by a value called $c^*$, the information-acquisition complexity.
Until now, BOBW algorithms for linear bandits either relied on clunky "detect-and-switch" mechanisms (which try to guess which regime they are in) or used purely FTRL approaches that failed to reach the fine-grained $c^*$ bound, instead settling for a coarser dependence on the "minimum gap" between actions ($\Delta_{min}$). Furthermore, most existing work struggled with infinite action sets, where actions can be infinitely close to the optimal one.
Methods
The authors propose two main algorithms:
- IA-FTRL (Information-Acquisition FTRL): Designed for finite action sets. It uses standard FTRL with Shannon entropy but introduces a novel Gap-Calibrated Exploration (GCE) mechanism. Instead of just picking the "best" action, it solves an optimization problem each round to find a sampling distribution that minimizes exploration cost while satisfying constraints that ensure the algorithm stays stable and learns enough about suboptimal actions.
- GIA-FTRL (Geometric IA-FTRL): Designed for infinite action sets. It uses a "mixture reference measure"—combining a discrete set of candidate actions with a continuous volume measure. This allows the algorithm to "cover" the entire action space for adversarial robustness while quickly concentrating on the best action in stochastic settings.
A key theoretical contribution is the definition of Sharpness. An instance is "sharp" if the loss gap of a suboptimal action grows at least proportionally to its distance from the optimal action.
Datasets
As a theoretical paper, it does not use real-world datasets. Instead, the authors evaluate their algorithms through rigorous mathematical proofs and by constructing specific "hard" synthetic instances (like the "arch" and "curve" action sets) to prove lower bounds and demonstrate the necessity of their geometric assumptions.
Key Insights and Ideas
- Pure FTRL is Sufficient: The paper proves that you don't need explicit regime detection to be instance-optimal. A well-constrained FTRL objective naturally balances the need to exploit known good actions and explore informative ones.
- The Geometry of Learning: For infinite action sets, the "shape" of the action set near the optimum determines if logarithmic regret is even possible. The authors show that "sharpness" is the necessary and sufficient condition for finite information-acquisition complexity ($c^*_{ctr} < \infty$).
- The Limits of Corruption Robustness: The paper explores the "corrupted stochastic" regime, where a small amount of adversarial noise is added to a stochastic environment. They find that while their algorithms are robust, the regret must sometimes depend on the minimum gap ($\Delta_{min}$), proving that a pure $c^*$-based bound is impossible when corruption is present.
Key Results
The paper provides impressive theoretical guarantees, summarized in the comparison table below:
- Finite Sets: IA-FTRL achieves $O(c^* \log K \log T)$ regret in stochastic regimes and $O(\sqrt{dT \log K})$ in adversarial regimes. This is the first time the $c^*$ bound has been hit by a pure FTRL algorithm.
- Infinite Sets: For "sharp" instances, GIA-FTRL achieves $O(d c^*_{ctr} \log T)$ stochastic regret.
- Corruption: Both algorithms handle a corruption budget $C$ with an additional $O(\sqrt{C})$ regret term, which is the gold standard for robustness.
Limitations and Future Work
The authors identify several areas for further exploration:
- Uniqueness: The current analysis assumes there is a single unique optimal action $a^*$. Lifting this assumption remains a difficult open problem for linear bandits.
- Multiplicative Factors: The bounds include factors like $d$ (dimension) and $\log K$ (number of actions) that might be improvable.
- Beyond Sharpness: While the paper proves that $O(\sqrt{C})$ corruption bounds are impossible for non-sharp instances, it remains an open question whether any logarithmic stochastic regret can be achieved for a broader class of "non-sharp" infinite action sets.
Summary updated