Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces

Yinglun Zhu, Paul Mineiro

Introduction

Designing efficient general-purpose contextual bandit algorithms that work with large—or even infinite—action spaces is critical for applications like information retrieval, recommendation systems, and continuous control. This paper introduces Smooth Regret, a new benchmark for contextual bandits that makes learning in these massive action spaces mathematically tractable and computationally efficient. By competing against the best "smoothed" distribution of actions rather than a single "needle-in-a-haystack" optimal action, the authors develop algorithms that achieve minimax optimal performance while remaining highly practical.

The "Needle in a Haystack" Problem

In a standard contextual bandit problem, an agent observes a context (e.g., a user profile), chooses an action (e.g., an ad), and receives a reward. The goal is to minimize regret—the difference between the agent's total reward and the reward of the best possible action.

However, when the action space is massive or continuous, finding the single best action is often impossible. If the optimal action is extremely rare and the reward function lacks specific structure (like linearity), an agent might have to try every single action to find it. In these settings, standard regret guarantees become vacuous.

To bypass this, researchers typically assume the reward function is very smooth (e.g., Lipschitz) or change the benchmark entirely. This paper takes the latter route, proposing a benchmark that is "harder" than previous alternatives but still "fair" enough to allow for efficient learning. By defining regret against an $h$-smoothed kernel (where the probability density is capped), the benchmark automatically ignores "freak" optimal actions that are too hard to find. If a good action is rare, the smoothed benchmark is forced to be lower, making it a more realistic target.

Methodology: SmoothIGW and SmoothCB

The authors introduce two primary algorithmic contributions:

  1. SmoothIGW (Smooth Inverse Gap Weighting): This algorithm operates when the desired "smoothness" level ($h$) is known. It utilizes two oracle tools:
  2. Online Regression Oracle: A black-box tool predicting the loss of a context-action pair based on past data.
  3. Sampling Oracle: A tool providing a random action from a base distribution.

The core innovation is a smoothed variant of IGW. Instead of merely picking the predicted best action, it creates a probability distribution that balances exploration and exploitation. A clever rejection sampling trick ensures the algorithm only needs a single call to the sampling oracle per round, making it highly efficient.

  1. SmoothCB: Because the "correct" smoothness level is rarely known in advance, the authors employ a master-algorithm framework called CORRAL. SmoothCB runs multiple instances of SmoothIGW in parallel—each with a different smoothness setting—and dynamically shifts resources toward the best-performing instance.

Empirical Results

The authors evaluated their approach on both discrete (large action space) and continuous (infinite action space) problems. The discrete tests utilized the New Yorker Magazine Cartoon Caption Contest dataset (10,025 possible actions). The continuous tests used five large-scale regression datasets from OpenML (Cpu, Fri, Price, Wis, Zur), converted into continuous bandit problems.

Cumulative regret comparison over time.

The proposed methods demonstrated significant empirical superiority. Theoretically, the authors proved their algorithm achieves a statistically optimal regret of $O(\sqrt{T/h})$, meaning you cannot do better without making more assumptions about the reward function. Empirically, their algorithm consistently outperformed baselines.

Performance comparison on continuous action datasets.

In continuous action tests, their algorithm (Ours-RFF) consistently outperformed CATS, a state-of-the-art method for continuous contextual bandits. As shown in the results table, on the "Price" dataset, their method achieved a significantly lower average loss (66.1–66.3) compared to CATS (108–110). Furthermore, the master algorithm successfully adapted to unknown smoothness levels, matching the performance of the best-tuned fixed-smoothness version.

Limitations and Future Work

  • Structural Blind Spots: The "no needle in a haystack" principle might be overly pessimistic for certain structured problems. For instance, in a linear bandit problem where the best action is isolated but the reward function is globally linear, a specialized linear bandit algorithm would outperform this smooth approach.
  • Data Reuse: The algorithm's current sampling method makes it difficult to reuse all generated data for "offline" evaluation. Refining the sampling distribution to improve data efficiency for offline logging is a key area for future work.
  • Benchmark Strength: While smooth regret is stronger than previous benchmarks (like Quantile Regret), the authors speculate that even stronger benchmarks might exist that still allow for $\sqrt{T}$-type regret guarantees.

Summary updated

Abstract

Designing efficient general-purpose contextual bandit algorithms that work with large—or even infinite—action spaces would facilitate application to important scenarios such as information retrieva...
BibTeX
@inproceedings{zhu2022contextual,
  author = {Yinglun Zhu and Paul Mineiro},
  title = {{Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=7wWaXx6FYNN},
}
Figure