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:
- 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.
- 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.
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.
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