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