New Breakthrough in Linear Bandits: IAFTRL Achieves Dual Optimality in Stochastic and Adversarial Environments

Title

New Breakthrough in Linear Bandits: IAFTRL Achieves Dual Optimality in Stochastic and Adversarial Environments

Meta Description

This paper proposes IAFTRL, the first pure FTRL framework algorithm for linear bandits that achieves best-of-both-worlds, attaining information-acquisition complexity-dependent logarithmic regret in stochastic environments while maintaining square-root regret in adversarial environments, resolving multiple open problems.

Article Content

One of the core challenges in linear bandit problems is designing an algorithm that performs optimally in both adversarial and stochastic environments—the so-called "best-of-both-worlds" (BOBW) guarantee. A recent paper proposes IAFTRL (information-acquisition follow-the-regularized-leader), claiming it to be the first algorithm under a pure FTRL framework to achieve this goal, resolving several open problems left by prior work.

Why is BOBW so difficult in linear bandits?

In linear bandits with finite action sets, adversarial environments require algorithms to guarantee $\tilde{O}(\sqrt{T})$ regret, while stochastic environments expect $O(\log T)$-level regret. Traditionally, these two types of guarantees require fundamentally different algorithm designs: adversarial algorithms are typically based on FTRL or mirror descent, while stochastic algorithms rely on optimistic estimation or confidence intervals. The goal of BOBW is to let a single algorithm automatically adapt to the environment without prior knowledge of the environment type.

Previously, for finite action sets, works such as Lee et al. 2021, Kong & Zhou 2023, Ito et al. 2023, and Zhao et al. 2025 made progress under specific conditions, but never provided a BOBW algorithm under a pure FTRL framework that achieves instance-dependent optimal regret in stochastic environments. IAFTRL fills this gap.

Linear Bandit is an important generalization of the multi-armed bandit problem: at each round, the algorithm selects an action $a_t$ from an action set $\mathcal{A} \subset \mathbb{R}^d$, and the observed reward is $r_t = \langle a_t, \theta^* \rangle + \eta_t$, where $\theta^$ is an unknown parameter vector and $\eta_t$ is noise. Unlike finite-armed bandits (where each arm is independent), in linear bandits there is a linear structural relationship between actions, and the algorithm needs to exploit this structure to infer $\theta^$ from partial feedback. This setting is widely used in recommender systems, clinical trials, and advertising. The difficulty of linear bandits lies in the fact that the action set may be continuous or enormous, and the algorithm can only observe the reward of the chosen action (bandit feedback), thus requiring carefully designed exploration strategies to estimate $\theta^$. The difference between adversarial and stochastic environments lies in the reward generation mechanism: in stochastic environments, $\eta_t$ is zero-mean noise and $\theta^$ is fixed; in adversarial environments, rewards may be adaptively chosen by an adversary, possibly depending on history. BOBW requires the algorithm to be near-optimal in both types of environments, placing higher demands on the exploration-exploitation trade-off.

IAFTRL's Core Idea: Information Acquisition and Regularization Game

The full name of IAFTRL is information-acquisition follow-the-regularized-leader. It continues the FTRL framework but explicitly incorporates "information-acquisition complexity" (denoted $\cstar$) into the design of the regularization term. This quantity characterizes instance-dependent optimality in linear bandits—intuitively, it measures the cost required to acquire sufficient information to distinguish the optimal action given the action set and unknown parameters.

The algorithm dynamically adjusts the regularization strength so that regret grows as $\tilde{O}(\cstar \log T)$ in stochastic environments while maintaining $\tilde{O}(\sqrt{T})$ guarantees in adversarial environments. The key is that the regularization term design simultaneously accounts for the geometric structure of information acquisition and robustness to corruption, which is precisely what "the interplay of information acquisition, corruption, and geometry" in the title refers to.

FTRL (Follow-The-Regularized-Leader) is a classic framework in online learning: at each round, the algorithm chooses the decision that minimizes the cumulative linear loss plus a regularization term, i.e., $x_{t+1} = \arg\min_x \left{ \sum_{s=1}^t \langle \ell_s, x \rangle + R_t(x) \right}$, where $R_t$ is the regularization term. The unity of FTRL makes it a natural choice for designing BOBW algorithms, because adjusting the regularization term allows flexible control of the algorithm's stability and adaptability. Under bandit feedback, loss gradients cannot be directly observed, and importance-weighted estimation (such as inverse probability weighting) is typically used to construct unbiased gradient estimates. IAFTRL's innovation lies in incorporating information-acquisition complexity into the regularization term design, making the regularization strength adapt to the instance's "information-acquisition difficulty": stronger regularization is used on instances where information acquisition is easy to accelerate convergence, while regularization is relaxed on difficult instances to maintain exploration. This design requires careful analysis of the relationship between the geometric properties of the regularization term (such as strong convexity and self-concordance) and information-acquisition complexity, thereby achieving optimal regret bounds in both stochastic and adversarial environments simultaneously.

Theoretical Guarantees and Resolution of Open Problems

The paper proves that IAFTRL's regret upper bound in stochastic environments is of the form $\tilde{O}(\cstar \log T)$, where $\cstar$ is the information-acquisition complexity. This bound is instance-dependent optimal, meaning that for "easy" instances (where information acquisition is easy), regret is smaller; for "hard" instances, regret is correspondingly larger. Meanwhile, in adversarial environments, the algorithm guarantees $\tilde{O}(\sqrt{T})$ regret, on the same order as the optimal bound for purely adversarial algorithms.

This result directly answers the open problems raised in Lee et al. (2021), Kong & Zhou (2023), Ito et al. (2023), and Zhao et al. (2025): whether a pure FTRL BOBW algorithm can achieve instance-dependent optimal stochastic regret. IAFTRL gives an affirmative answer.

Geometry and Corruption: The Source of Algorithmic Robustness

The "geometry" and "corruption" in the title are not mere modifiers. The action set of linear bandits has geometric structure (such as polytopes, spheres), and the FTRL regularization term needs to be compatible with this geometry to ensure that the regret bound does not deteriorate due to the shape of the action set. In addition, the algorithm must handle "corruption"—that is, some observations in the stochastic environment being maliciously tampered with. IAFTRL maintains near-optimal regret even in the presence of corruption through adaptive adjustment of information-acquisition complexity.

According to the paper, IAFTRL is the first BOBW algorithm under a pure FTRL framework that simultaneously handles information acquisition, corruption, and geometric structure. Its analysis integrates the stability of FTRL with the instance-dependent lower bounds of information acquisition, providing new tools for future research.

Information-acquisition complexity ($\cstar$) is a key quantity characterizing instance-dependent optimal regret in linear bandits. Intuitively, it measures the minimum amount of information required to distinguish the optimal action given the action set and unknown parameters. Formally, $\cstar$ is typically related to the geometric structure of the action set (such as the gap between the optimal action and suboptimal actions) and the variance of parameter estimation. In stochastic linear bandits, the instance-dependent optimal regret lower bound can usually be expressed as $\Omega(\cstar \log T)$, where $\cstar$ reflects the "difficulty" of the problem: if the optimal action is easy to identify (large gap, good action set geometry), then $\cstar$ is small; otherwise it is large. IAFTRL incorporates $\cstar$ into the regularization term, enabling the algorithm to automatically adapt to instance difficulty, thereby achieving a regret upper bound of $\tilde{O}(\cstar \log T)$ in stochastic environments. This bound matches known lower bounds (up to logarithmic factors) and is therefore instance-dependent optimal. Understanding $\cstar$ requires some background in linear algebra and convex geometry, but the core idea is: it quantifies the statistical cost of "learning the unknown parameters to find the optimal action."

Significance for Bandit Learners

For researchers and engineers focused on online learning and bandit algorithms, the value of IAFTRL lies in its unification of two seemingly contradictory goals. In practical applications, environments often oscillate between stochastic and adversarial (e.g., user behavior in recommender systems), and BOBW algorithms can adapt automatically without manual switching. IAFTRL's pure FTRL structure also means it is easy to implement and extend, potentially driving the adoption of BOBW ideas in more complex models (such as contextual bandits and reinforcement learning).

Of course, the paper currently focuses on linear bandits with finite action sets, and generalization to infinite action sets or nonlinear models remains an open direction. But for finite action sets, IAFTRL has already taken a key step.

Corruption in the online learning literature typically refers to a portion of observations in a stochastic environment being maliciously tampered with or subjected to adversarial interference. Specifically in the bandit setting, each round's reward may be modified by an adversary with some probability, or there may be an adversarial perturbation with a total budget constraint. The corruption model bridges pure stochastic and pure adversarial environments: when corruption is zero, the environment is purely stochastic; when corruption is sufficiently large, the environment can be regarded as adversarial. If a BOBW algorithm can maintain near-optimal regret in the presence of corruption, it indicates stronger robustness. IAFTRL handles corruption through adaptive adjustment of information-acquisition complexity: upon detecting anomalous observations, the algorithm adjusts the regularization strength to reduce sensitivity to corrupted data. Theoretical analysis shows that even with a certain degree of corruption, IAFTRL's regret remains on the order of $\tilde{O}(\cstar \log T + \sqrt{C T})$, where $C$ is the total corruption. This result unifies stochastic and adversarial settings and provides a smooth trade-off between corruption and regret.

One-line Summary

IAFTRL is the first algorithm under a pure FTRL framework to achieve best-of-both-worlds (BOBW) for linear bandits, simultaneously attaining instance-dependent optimality in stochastic environments and optimal regret in adversarial environments.

Paragraph Summary

This article introduces IAFTRL (information-acquisition follow-the-regularized-leader), the first algorithm under a pure FTRL framework to achieve best-of-both-worlds (BOBW) for linear bandits. The article first explains the BOBW challenge: adversarial environments require $\tilde{O}(\sqrt{T})$ regret, while stochastic environments expect $O(\log T)$-level regret, traditionally requiring different algorithm designs. IAFTRL's core innovation is explicitly incorporating information-acquisition complexity $\cstar$ into the regularization term, dynamically adjusting regularization strength to achieve $\tilde{O}(\cstar \log T)$ instance-dependent optimal regret in stochastic environments while maintaining $\tilde{O}(\sqrt{T})$ regret in adversarial environments. The algorithm also accounts for geometric structure and corruption robustness. This result resolves open problems raised by Lee et al. 2021, Kong & Zhou 2023, Ito et al. 2023, and Zhao et al. 2025. The article concludes by discussing the significance of IAFTRL for bandit learners and future directions.