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 \leq 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. 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.
Introduction
In the contextual bandit framework, an agent observes a "context" (such as user demographics or browsing history), selects an action (such as an advertisement), and receives a reward. The goal is to maximize cumulative rewards over time, which requires learning the underlying relationship between contexts and rewards. Historically, theoretical research has bifurcated into two distinct regimes:
- Parametric Models (Global Learning): These assume reward functions are highly structured, such as linear models. In this regime, every observation provides "global" information; learning about a user in one region of the context space allows for accurate predictions in distant regions. This leads to very low regret, typically logarithmic in time.
- Non-differentiable Nonparametric Models (Local Learning): These assume reward functions are "jagged" or only minimally continuous. Here, information is strictly "local." To learn the optimal action for a specific context, the agent must explore that specific neighborhood. This results in much higher regret, following a power law.
This paper identifies and fills the "missing middle": the regime of smooth functions that are neither perfectly linear nor entirely jagged. By introducing a smoothness parameter $\beta$, the authors provide a unified framework that spans the entire spectrum of function complexity.
The Smoothness Bridge
The core contribution of this work is the use of the Hölder smoothness parameter $\beta$ as an interpolator. When $\beta$ is small ($\beta \le 1$), the environment is complex and requires intensive local exploration. As $\beta$ increases, the functions become smoother (possessing continuous derivatives), allowing the agent to extrapolate information more effectively. As $\beta \to \infty$, the problem simplifies to the parametric case.
Methodology: Local Polynomial Regression
To handle this spectrum of smoothness, the authors propose a novel algorithm that moves beyond simple nearest-neighbor or global linear fits. The key technical components include:
- Local Polynomial Regression: Instead of assuming a global shape, the algorithm fits polynomials to local neighborhoods. As the smoothness $\beta$ increases, the algorithm can utilize data from larger neighborhoods to improve its estimates without introducing excessive bias.
- Shrinking Margin Exploration: The algorithm focuses exploration on the "margin"—regions where the predicted rewards for the top actions are nearly identical. As the model's confidence grows, this margin shrinks, allowing for more aggressive exploitation.
- Adaptive Information Leveraging: The algorithm balances global and local information based on the assumed smoothness, ensuring that it uses the maximum amount of available information for any given $\beta$.
Key Results and Theoretical Landscape
The authors establish that a single regret rate formula, $\tilde{\Theta}(T^{\frac{\beta+d-\alpha\beta}{2\beta+d}})$, governs all regimes (where $d$ is the dimension and $\alpha$ is the margin sharpness). This unified rate is a significant theoretical milestone, as it recovers disparate results from previous literature as special cases.
By proving matching upper and lower bounds, the authors demonstrate that their algorithm is minimax optimal. This means it achieves the best possible theoretical performance for any given level of environmental complexity. For highly smooth functions, the algorithm achieves near-optimal rewards with minimal forced exploration, effectively "extrapolating" knowledge across the context space.
Conclusion and Future Directions
This research provides a comprehensive map of the complexity-regret interplay in contextual bandits. It shows that the trade-off between exploration and exploitation is not a binary choice but a sliding scale determined by the smoothness of the environment.
While the current work assumes the smoothness parameter $\beta$ is known, future research could focus on "adaptive" algorithms that can automatically detect the smoothness of the reward functions. Additionally, addressing the "curse of dimensionality"—where regret grows exponentially with the number of features ($d$)—remains a critical challenge for applying these nonparametric methods to high-dimensional real-world data.
Summary updated