Contextual bandits with surrogate losses: Margin bounds and efficient algorithms

Dylan J. Foster, Akshay Krishnamurthy

Bridging a significant gap between supervised learning and contextual bandits, this paper introduces a theoretical framework and practical algorithms that leverage surrogate losses (such as the hinge and ramp loss) to achieve better statistical efficiency and computational tractability in sequential decision-making problems.

The authors provide a comprehensive treatment of margin-based learning for contextual bandits. They derive new dimension-independent regret bounds using sequential complexity measures and introduce HINGE-LMC, the first computationally efficient algorithm to achieve a $\sqrt{dT}$ mistake bound for bandit multiclass prediction using a non-curved surrogate loss.

The Challenge of Contextual Bandits

In contextual bandits, a learner must repeatedly choose an action based on a "context" (like user data) and only receives feedback for the chosen action (partial feedback). The goal is to minimize regret—the difference between the learner's total loss and the loss of the best fixed policy in a benchmark class.

Traditionally, contextual bandit algorithms face two major hurdles:

  1. Statistical Complexity: Regret bounds often depend heavily on the dimension ($d$) of the policy class. In supervised learning, "margin bounds" allow for dimension-independent analysis, but this had not been fully realized for the bandit setting.
  2. Computational Intractability: Many optimal bandit algorithms require solving NP-hard optimization problems at every step. While surrogate losses (like the hinge loss used in Support Vector Machines) make supervised learning tractable by turning discrete problems into convex ones, their use in bandits was previously limited and poorly understood.

Methods and Algorithmic Innovations

The paper attacks these problems from both a statistical and an algorithmic perspective:

  • Surrogate Loss Translation: The authors use the ramp loss and hinge loss as surrogates for the standard 0/1 or cost-sensitive multiclass loss. They prove a "translation lemma" showing that minimizing these surrogates effectively bounds the true loss.
  • Sequential Complexity: To handle infinite policy classes, they use sequential metric entropy and sequential Rademacher complexity. This allows them to derive "Dudley-type" entropy integrals for bandits, which are standard in statistical learning but novel in this context.
  • HINGE-LMC Algorithm: For parametric settings, they propose an algorithm that uses the hinge loss (a convex surrogate). To handle the sampling required by bandit feedback, they employ Langevin Monte Carlo (LMC)—a tool for sampling from log-concave distributions—combined with a "geometric resampling" technique to estimate the importance weights of actions.
Pseudocode for the HINGE-LMC algorithm and the Langevin Monte Carlo subroutine.
  • SMOOTHFTL Algorithm: For stochastic, non-parametric settings, they introduce a "Follow-The-Leader" approach with uniform smoothing and epoch-based updates.

(Note: As a theoretical paper focused on proving regret bounds and algorithmic complexity, no empirical datasets were used for training or evaluation. The "benchmarks" discussed are mathematical policy classes, such as $d$-dimensional regressors, Lipschitz functions, and linear predictors in smooth Banach spaces.)

Key Insights and Ideas

  • The "Margin" Advantage: Just as in supervised learning, if there is a "margin" (a clear gap between the best action and others), the learner can achieve regret bounds that don't explicitly depend on the dimension $d$, but rather on the "sequential complexity" of the function class.
  • Solving the "Curvature" Problem: Previous efficient bandit algorithms often required "curved" losses (like squared loss or logistic loss) to work. This paper solves a long-standing open problem by showing how to achieve optimal $\sqrt{dT}$ regret using the hinge loss, which has no curvature (it is piecewise linear).
  • Phase Change in Regret: The authors identify a "phase change" in how regret grows. For "moderate complexity" classes, the regret scales differently than for "high complexity" classes. This is visualized as a distinct kink in the regret exponent curve.
Regret exponent vs. metric entropy, illustrating the phase change (kink) in the regret exponent curve for the bandit ramp loss.
  • Information-Theoretic Benchmarks: By using non-constructive minimax analysis, the paper establishes the "limit of the possible" for contextual bandit learnability, providing a target for future algorithm designers.

Key Results

  • Improved Lipschitz Regret: For Lipschitz contextual bandits in $d$-dimensional spaces, they achieve a regret bound of $\tilde{O}(T^{\frac{d}{d+1}})$, improving upon previous state-of-the-art results.
  • Dimension-Independent Bounds: They demonstrate that for linear classes in smooth Banach spaces, one can achieve $O(T^{2/3})$ mistake bounds that do not depend on the dimension of the space.
  • Efficiency: The authors prove that HINGE-LMC runs in polynomial time relative to the number of rounds $T$ and dimension $d$, while maintaining a $\sqrt{dT}$-type mistake bound against the hinge loss benchmark.

Limitations and Future Work

While the theoretical contributions are robust, the authors note a few limitations. First, their bounds might be suboptimal regarding the number of actions ($K$); improving the scaling with respect to $K$ is a suggested area for future research. Second, the current theory requires the margin parameter ($\gamma$) to be chosen in advance. In practice, the optimal margin is rarely known, and "tuning" it online remains a difficult open challenge. Finally, while HINGE-LMC is provably efficient, the authors did not implement it empirically. Future work should explore how these surrogate-based algorithms perform on real-world recommendation or mobile health datasets.

Summary updated

Abstract

We use surrogate losses to obtain several new regret bounds and new algorithms for contextual bandit learning. Using the ramp loss, we derive a new margin-based regret bound in terms of standard sequential complexity measures of a benchmark class of real-valued regression functions. Using the hinge loss, we derive an efficient algorithm with a $\sqrt{dT}$-type mistake bound against benchmark policies induced by $d$-dimensional regressors. Under realizability assumptions, our results also yield classical regret bounds.
BibTeX
@inproceedings{foster2018contextual,
  author = {Dylan J. Foster and Akshay Krishnamurthy},
  title = {{Contextual bandits with surrogate losses: Margin bounds and efficient algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HJbF0uW_WS},
}
Figure