Introduction
Contextual bandits (CB) represent a critical framework for sequential decision-making under uncertainty, with applications ranging from personalized recommendation systems to clinical trials. In this setting, an agent observes a context, chooses an action, and receives a loss. The goal is to minimize regret—the difference between the agent's total loss and that of the best fixed policy in hindsight.
Traditionally, regret bounds for efficient contextual bandit algorithms scale with $\sqrt{T}$, where $T$ is the number of rounds. However, in many real-world scenarios, the environment is not "worst-case"; the best policy may have a very small cumulative loss ($L^*$). "First-order" algorithms aim to achieve regret scaling with $\sqrt{L^*}$, which is significantly smaller than $\sqrt{T}$ in low-noise settings. This paper introduces FastCB, the first computationally efficient algorithm to achieve these optimal first-order guarantees, resolving a prominent open problem posed at COLT 2017.
The Challenge of First-Order Efficiency
Prior to this work, achieving first-order regret in contextual bandits required either computationally inefficient methods (such as those with complexity exponential in the number of actions) or restrictive assumptions about the data distribution. A major hurdle was the reliance on least-squares regression. While square-loss oracles are common in bandit algorithms (e.g., SquareCB), they are fundamentally limited by their sensitivity to varying noise levels (heteroscedasticity), making them incapable of reaching first-order rates.
The FastCB Framework
FastCB (Fast Rates for Contextual Bandits) overcomes these limitations through three primary innovations:
1. Logarithmic Loss Regression
FastCB replaces the standard least-squares regression oracle with an online regression oracle using logarithmic (cross-entropy) loss. The authors demonstrate that log-loss is naturally suited for first-order bounds because its regret is tied to KL-divergence, which provides a more robust foundation for handling low-loss environments than square loss.
2. Triangular Discrimination
To bridge the gap between regression error and bandit regret, the authors employ an information-theoretic quantity known as triangular discrimination. This metric serves as a "just right" distance measure—stronger than the Hellinger distance but more manageable than $\chi^2$-divergence. By leveraging the self-bounding properties of triangular discrimination, the algorithm can bound regret more tightly, as the error in predictions is naturally controlled by the magnitude of the losses themselves.
3. Reweighted Inverse Gap Weighting
FastCB introduces a new action-selection mechanism. While standard methods explore based on the "gap" between an action's predicted loss and the best action's loss, FastCB’s rule is scale-sensitive. It reduces exploration more aggressively when the predicted loss of the best action is small. This allows the algorithm to convert "low noise" directly into faster convergence rates.
Empirical Evaluation
The authors evaluated FastCB using the Contextual Bandit Bake-off suite, one of the most extensive empirical benchmarks in the field. The suite consists of over 500 multiclass classification datasets from the OpenML platform, converted into bandit problems where the agent receives a loss of 0 for a correct label and 1 for an incorrect one.
Key Findings
- Theoretical Optimality: FastCB is the first algorithm to achieve the optimal first-order regret bound of $\tilde{O}(\sqrt{L^* \cdot A \cdot \text{Reg}_{\text{KL}}(T)})$ while remaining computationally efficient.
- Practical Performance: In head-to-head comparisons, FastCB.L (the log-loss variant) significantly outperformed the square-loss baseline (SquareCB.S). Specifically, FastCB.L won on 66 more datasets than it lost to.
- Low-Loss Advantage: The performance gains were most pronounced on datasets where the optimal loss $L^*$ was small (e.g., $L^* \le 0.2$), confirming the theoretical intuition that the log-loss approach excels in low-noise regimes.
Conclusion
FastCB represents a significant theoretical and practical advancement in contextual bandits. By shifting the underlying primitive from square loss to log loss and utilizing triangular discrimination, the authors provide a simple, efficient, and robust solution to the first-order regret problem. While future work remains to tighten theoretical constants and extend the framework to infinite action spaces, FastCB sets a new standard for adaptive learning in real-world, low-noise environments.
Summary updated