IAFTRL

IAFTRL (information-acquisition follow-the-regularized-leader) is claimed by the paper to be the first linear bandit algorithm that achieves both adversarial-optimal (~O(√T) regret) and stochastic instance-dependent optimal (~O(C* log T) regret) performance within a pure FTRL framework.

IAFTRL's regret upper bound in stochastic environments is ~O(C* log T), where C* is the information-acquisition complexity.

IAFTRL's regret upper bound in adversarial environments is ~O(√T), of the same order as the optimal bound for purely adversarial linear bandit algorithms.

In the presence of corruption, IAFTRL's regret upper bound is on the order of ~O(C* log T + √(C T)), where C is the total corruption.

IAFTRL dynamically adjusts the regularization strength, incorporating information-acquisition complexity into the design of the FTRL regularization term, thereby automatically adapting to instance difficulty.

Prior work (Lee et al. 2021, Kong & Zhou 2023, Ito et al. 2023, Zhao et al. 2025) failed to provide a BOBW algorithm within a pure FTRL framework that achieves instance-dependent optimal regret in stochastic environments; IAFTRL solves this open problem.

In stochastic linear bandits, the instance-dependent optimal regret lower bound can usually be expressed in the form Ω(C* log T), matching IAFTRL's upper bound (up to logarithmic factors).

IAFTRL's analysis combines the stability of FTRL with the instance-dependent lower bound of information acquisition, providing a new tool for subsequent research.

The paper currently focuses on linear bandits with finite action sets, and extension to infinite action sets or nonlinear models remains an open direction.

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.