Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes

Yichun Hu, Nathan Kallus, Xiaojie Mao

Abstract

We study a nonparametric contextual bandit problem where the expected reward functions belong to a Hölder class with smoothness parameter $\beta$. We show how this interpolates between two extremes that were previously studied in isolation: non-differentiable bandits ($\beta \le 1$), where rate-optimal regret is achieved by running separate non-contextual bandits in different context regions, and parametric-response bandits (satisfying $\beta = \infty$), where rate-optimal regret can be achieved with minimal or no exploration due to infinite extrapolatability. We develop a novel algorithm that carefully adjusts to all smoothness settings and we prove its regret is rate-optimal by establishing matching upper and lower bounds, recovering the existing results at the two extremes.

Introduction

In contextual bandit problems, an agent makes sequential decisions based on observed features (contexts) to maximize cumulative rewards. The efficiency of learning is typically measured by "regret"—the difference between the reward of an optimal policy and the agent's actual reward. Historically, research has focused on two distinct regimes:

  1. The Non-differentiable Regime ($\beta \le 1$): Reward functions are "rough" (e.g., Lipschitz). Learning is local; information from one context region provides little insight into others, requiring dense exploration.
  2. The Parametric Regime ($\beta = \infty$): Reward functions follow a rigid global structure (e.g., linear models). Learning is global; a few samples can characterize the entire reward surface, allowing for very low regret.

This work bridges these regimes by considering reward functions in the Hölder class $\Sigma(\beta, L)$, where $\beta$ represents the degree of smoothness.

Positioning in the Literature

The problem difficulty is governed by two main parameters: the smoothness $\beta$ and the margin sharpness $\alpha$. The margin parameter $\alpha$ describes how quickly the reward gap between the best and second-best arm grows near the decision boundary.

The landscape of contextual bandit research across smoothness (β) and margin sharpness (α). This work fills the gap for intermediate smoothness levels.

As shown in the table above, prior work focused on the boundaries of this space. This paper provides a unified analysis for the entire spectrum of $1 \le \beta < \infty$, showing that the transition between regimes is continuous.

The SmoothBandit Algorithm

To achieve optimality across this spectrum, we propose the SmoothBandit algorithm. Its design centers on three key innovations:

  • Local Polynomial Regression (LPR): Unlike simple averaging, LPR fits a degree $\lfloor \beta \rfloor$ polynomial to local data. This allows the algorithm to exploit higher-order derivatives for better extrapolation as $\beta$ increases.
  • Adaptive Decision Regions: The context space is partitioned into hypercubes. In each epoch, cubes are classified as Exploitation (one arm is clearly better), Exploration (arms are similar), or Inestimable (insufficient data).
  • Global-to-Local Information Transfer: Smoothness allows the algorithm to use data from neighboring regions to estimate rewards within a specific cube, significantly reducing the need for forced exploration in well-behaved regions.

Theoretical Results and Regret Regimes

We establish that the minimax-optimal regret $R_T$ follows the rate: $$\tilde{\Theta}\left(T^{\frac{\beta+d-\alpha\beta}{2\beta+d}}\right)$$ where $d$ is the context dimension. This result is significant because it provides a continuous transition between the previously disconnected regimes.

Regret rate exponents as a function of smoothness β for different margin parameters α. The plots show how the regret transitions from the nonparametric regime toward the parametric limit.

As $\beta \to \infty$, the regret rate exponent decreases, approaching the logarithmic or constant rates characteristic of parametric models. Conversely, at $\beta=1$, we recover the standard nonparametric rates. Our work proves that higher-order smoothness directly dictates how much "global" information can be extracted from "local" samples.

Conclusion

By treating smoothness as a continuous parameter, we provide a unified framework for contextual bandits. Our SmoothBandit algorithm and the corresponding minimax bounds demonstrate that the transition from local to global learning is not a jump but a smooth progression dictated by the underlying complexity of the reward function. This work sheds light on the fundamental interplay between function smoothness, margin sharpness, and the achievable regret in sequential decision-making.

Summary updated

Abstract

We study a nonparametric contextual bandit problem where the expected reward functions belong to a H\"older class with smoothness parameter $\beta$. We show how this interpolates between two extremes that were previously studied in isolation: non-differentiable bandits ($\beta\leq1$), where rate-optimal regret is achieved by running separate non-contextual bandits in different context regions, and parametric-response bandits (satisfying $\beta=\infty$), where rate-optimal regret can be achieved with minimal or no exploration due to infinite extrapolatability. We develop a novel algorithm that carefully adjusts to all smoothness settings and we prove its regret is rate-optimal by establishing matching upper and lower bounds, recovering the existing results at the two extremes. In this sense, our work bridges the gap between the existing literature on parametric and non-differentiable contextual bandit problems and between bandit algorithms that exclusively use global or local information, shedding light on the crucial interplay of complexity and regret in contextual bandits.
BibTeX
@article{hu2022smooth,
  author = {Yichun Hu and Nathan Kallus and Xiaojie Mao},
  title = {{Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes}},
  journal = {Oper. Res.},
  year = {2022},
  doi = {10.1287/opre.2021.2237},
}
Figure