Abstract
Designing efficient general-purpose contextual bandit algorithms that work with large—or even continuous—action spaces would facilitate application to important scenarios such as information retrieval, recommendation systems, and continuous control. While obtaining standard regret guarantees can be hopeless, alternative regret notions have been proposed to tackle the large action setting. We propose a smooth regret notion for contextual bandits, which dominates previously proposed alternatives. We design a statistically and computationally efficient algorithm—for the proposed smooth regret—that works with general function approximation under standard supervised oracles. We also present an adaptive algorithm that automatically adapts to any smoothness level. Our algorithms can be used to recover the previous minimax/Pareto optimal guarantees under the standard regret, e.g., in bandit problems with multiple best arms and Lipschitz/Hölder bandits. We conduct large-scale empirical evaluations demonstrating the efficacy of our proposed algorithms.
Introduction
Contextual bandits serve as a fundamental framework for sequential decision-making, where an agent observes a context, selects an action, and receives a reward. While this framework is well-understood for small, discrete action sets, extending it to large or continuous action spaces introduces significant statistical and computational challenges. In such settings, finding the single optimal action can be akin to finding a "needle in a haystack." Without restrictive assumptions on the reward function (such as linearity or high-order smoothness), standard regret—which measures performance against the absolute best possible action—often leads to vacuous guarantees.
To bridge this gap, this research introduces smooth regret, a novel benchmark that makes learning in infinite action spaces tractable. By competing against the best smoothed distribution of actions rather than a single point, the learner can achieve meaningful performance guarantees while maintaining computational efficiency.
The Smooth Regret Benchmark
The core innovation of this work is the definition of smooth regret. In continuous spaces, the probability of hitting a single optimal point is zero. Previous attempts to solve this, such as "quantile regret," compared the learner to the top $\tau$-percentile of actions. However, the authors demonstrate that smooth regret is a more robust and challenging benchmark that dominates these previous notions.
By utilizing a smoothing kernel of size $h$, the algorithm effectively treats a continuous space as having $1/h$ "effective" actions. This allows the learner to achieve a regret bound of $O(\sqrt{T/h})$, providing a statistically sound way to handle the complexity of continuous decision-making without requiring the rigid assumptions of Lipschitz or Hölder continuity, though it can recover optimal rates for those specific cases when they do exist.
Algorithmic Framework
The paper proposes two primary algorithmic contributions to address smooth regret:
1. SmoothIGW (Smooth Inverse Gap Weighting)
SmoothIGW extends the popular Inverse Gap Weighting (IGW) technique from discrete to continuous spaces. The algorithm is oracle-efficient, meaning it relies on two standard "black boxes":
- Regression Oracle: Used to predict losses based on context and action.
- Sampling Oracle: Used to explore the action space.
To define the sampling distribution in continuous space, the algorithm employs Radon-Nikodym derivatives, balancing exploration and exploitation. Furthermore, the authors provide a practical rejection sampling scheme that allows for $O(1)$ sampling per round, making the algorithm computationally viable for real-world applications.
2. Adaptive Master Algorithm
A significant challenge in applying smooth regret is that the optimal smoothness level ($h$) is typically unknown. To solve this, the authors developed an adaptive framework based on the CORRAL meta-algorithm. This master algorithm runs multiple instances of SmoothIGW with varying $h$ values in parallel, learning online which smoothness level is most appropriate for the specific problem instance.
Empirical Evaluation
The researchers conducted large-scale evaluations across both discrete and continuous domains to validate the efficacy of SmoothIGW.
- Continuous Action Spaces: Using five large-scale regression datasets from OpenML (Cpu, Fri, Price, Wis, and Zur), the team converted regression tasks into continuous bandit problems. SmoothIGW, utilizing both linear and non-linear predictors, consistently outperformed CATS, the current state-of-the-art algorithm for continuous actions.
- Large Discrete Action Spaces: The algorithm was tested on the New Yorker Cartoon Caption Contest dataset, which contains over 10,000 possible actions (captions). Despite being designed for continuous spaces, SmoothIGW performed as well as empMOSS++, an algorithm specifically optimized for discrete bandits with many arms. This demonstrates the versatility of the smooth regret framework.
Conclusion and Future Work
This work provides a unified approach to contextual bandits in large action spaces by introducing a benchmark that is both theoretically sound and practically achievable. While SmoothIGW excels as a general-purpose learner, the authors note that specialized algorithms may still outperform it in scenarios with very rigid structures, such as purely linear rewards where the optimum lies at a boundary.
Future research directions include improving the sampling distribution to enhance data reusability for offline policy evaluation and exploring whether even stronger benchmarks exist that still permit $\sqrt{T}$ regret in infinite action spaces. By bridging the gap between discrete and continuous bandit theory, this research opens new doors for applying sequential decision-making to complex, real-world control and recommendation problems.
Summary updated