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

arXiv: https://arxiv.org/abs/1909.02553 · HTML: https://mlsanity.com/paper/1909.02553/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2019.

## Built on by (most cited first, 25 of 25)

- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [Transfer Learning for Contextual Multi-armed Bandits](https://mlsanity.com/paper/2211.12612/) (2022)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning](https://mlsanity.com/paper/2106.01723/) (2021)
- [Analysis of Thompson Sampling for Partially Observable Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2110.12175/) (2021)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates](https://mlsanity.com/paper/2102.01977/) (2021)
- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Multi-armed Bandit Requiring Monotone Arm Sequences](https://mlsanity.com/paper/2106.03790/) (2021)
- [Optimal Adaptive Experimental Design for Estimating Treatment Effect](https://mlsanity.com/paper/2410.05552/) (2024)
- [Low-Rank MDPs with Continuous Action Spaces](https://mlsanity.com/paper/2311.03564/) (2023)
- [Utility Fairness in Contextual Dynamic Pricing with Demand Learning](https://mlsanity.com/paper/2311.16528/) (2023)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)
- [Flexible and Efficient Contextual Bandits with Heterogeneous Treatment Effect Oracles](https://mlsanity.com/paper/2203.16668/) (2022)
- [Batched Nonparametric Bandits via k-Nearest Neighbor UCB](https://mlsanity.com/paper/2505.10498/) (2025)
- [Kernel ε-Greedy for Multi-Armed Bandits with Covariates](https://mlsanity.com/paper/2306.17329/) (2023)
- [Vector preference-based contextual bandits under distributional shifts](https://mlsanity.com/paper/2508.15966/) (2025)
- [Beyond ATE: Multi-Criteria Design for A/B Testing](https://mlsanity.com/paper/2509.05864/) (2025)
- [Fast Best-in-Class Regret for Contextual Bandits](https://mlsanity.com/paper/2510.15483/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)

## Abstract (arXiv)

We study a nonparametric contextual bandit problem where the expected reward functions belong to a H"older class with smoothness parameter β. We show how this interpolates between two extremes that were previously studied in isolation: non-differentiable bandits (β≤1), where rate-optimal regret is achieved by running separate non-contextual bandits in different context regions, and parametric-response bandits (satisfying β=∞), 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.