Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination

Dylan J. Foster, Akshay Krishnamurthy

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

Abstract

A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise, often quantified by the performance of the best hypothesis; such results are known as first-order or small-loss guarantees. While first-order guarantees are relatively well understood in statistical and online learning, adapting to low noise in contextual bandits (and more broadly, decision making) presents major algorithmic challenges. In a COLT 2017 open problem, Agarwal, Krishnamurthy, Langford, Luo, and Schapire asked whether first-order guarantees are even possible for contextual bandits and -- if so -- whether they can be attained by efficient algorithms. We give a resolution to this question by providing an optimal and efficient reduction from contextual bandits to online regression with the logarithmic (or, cross-entropy) loss. Our algorithm is simple and practical, readily accommodates rich function classes, and requires no distributional assumptions beyond realizability. In a large-scale empirical evaluation, we find that our approach typically outperforms comparable non-first-order methods. On the technical side, we show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees, and we combine this observation with new refinements to the regression oracle reduction framework of Foster and Rakhlin. The use of triangular discrimination yields novel results even for the classical statistical learning model, and we anticipate that it will find broader use.
BibTeX
@inproceedings{foster2021efficient,
  author = {Dylan J. Foster and Akshay Krishnamurthy},
  title = {{Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=_MTppmAS_J1},
}
Figure