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

Dylan J. Foster, Akshay Krishnamurthy

Introduction

In the contextual bandit problem, an agent must repeatedly choose actions based on observed contexts to minimize its cumulative loss. Standard algorithms typically offer "worst-case" guarantees, where the regret—the difference between the agent's loss and the best possible policy's loss—scales with the square root of time ($\sqrt{T}$).

However, in many real-world scenarios, the environment exhibits "low noise," meaning the optimal policy has a very low total loss ($L^*$). In supervised learning, algorithms can exploit this low noise to achieve much faster convergence, yielding what are known as first-order guarantees (scaling with $\sqrt{L^*}$ instead of $\sqrt{T}$). Achieving this in the bandit setting, where the agent only observes the loss for the specific action it chose, is significantly harder. A prominent 2017 open problem asked if an algorithm could be both first-order optimal and computationally efficient. This paper provides the resolution by introducing FastCB, the first efficient algorithm for contextual bandits that achieves optimal first-order regret guarantees.

The FastCB Framework

Rather than building a bandit algorithm from scratch, the authors propose a reduction-based framework that leverages an online regression oracle.

The Necessity of Logarithmic Loss

Previous state-of-the-art reductions, such as SquareCB, rely on square loss. A key insight of this paper is the mathematical proof that plug-in classifiers based on least-squares regression are fundamentally incapable of achieving first-order rates for this problem. To overcome this, FastCB requires an oracle that minimizes logarithmic (cross-entropy) loss. Logarithmic loss possesses a "mixable" property, making it the natural choice for adapting to low-noise environments.

Triangular Discrimination

The theoretical "secret sauce" of FastCB is the use of triangular discrimination ($D_\Delta$). This information-theoretic divergence measure serves as the fundamental bridge between prediction error and decision-making regret. The authors identify it as the "just right" metric—stronger than the standard $\chi^2$-divergence, yet easier to control via logarithmic loss.

Reweighted Inverse Gap Weighting

To translate predictions into actions, FastCB employs a novel action-selection strategy called Reweighted Inverse Gap Weighting. It takes the loss predictions from the regression oracle and converts them into a probability distribution over actions. Crucially, this scheme is "scale-sensitive": it explores less aggressively when the estimated losses are small, directly enabling the $\sqrt{L^*}$ scaling.

Empirical Evaluation and Results

The authors evaluated FastCB using the "Contextual Bandit Bake-off" suite, a large-scale benchmark comprising over 500 datasets from OpenML, including multiclass, multilabel, and cost-sensitive classification tasks converted into bandit problems.

The results demonstrate both theoretical optimality and empirical superiority:

  • Theoretical Optimality: FastCB achieves a regret bound of $\mathbb{E}[\text{Reg}_{CB}(T)] \le \tilde{O}(\sqrt{L^* \cdot A \cdot \text{Reg}_{KL}(T)})$, perfectly matching the information-theoretic lower bounds for this setting.
  • Empirical Performance: In head-to-head tests across the benchmark datasets, FastCB (using a logistic loss oracle) significantly outperformed SquareCB.
  • The "Small-Loss" Advantage: Experiments confirmed that the most substantial performance gains occurred on datasets where the optimal loss $L^*$ was small (specifically $L^* \le 0.2$), validating the core "first-order" theory.

Limitations and Future Directions

While FastCB resolves a major open problem, the authors note a few limitations. First, the constant factors in their "per-round inequality" are currently larger than those for SquareCB. Consequently, if the problem is not low-noise (i.e., $L^*$ is large), FastCB might slightly underperform simpler methods; optimizing these constants remains an open area. Second, the current work focuses on finite action spaces ($A$), and while extensions to infinite action spaces are suggested, they require further development. Finally, the algorithm's efficiency is inherently tied to the efficiency of the log-loss regression oracle, which could pose computational challenges for certain complex function classes.

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 (2020). 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