# Smoothness-Adaptive Contextual Bandits

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

## Key facts

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

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

- [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)
- [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)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [Utility Fairness in Contextual Dynamic Pricing with Demand Learning](https://mlsanity.com/paper/2311.16528/) (2023)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)
- [Optimal subgroup selection](https://mlsanity.com/paper/2109.01077/) (2021)
- [Flexible and Efficient Contextual Bandits with Heterogeneous Treatment Effect Oracles](https://mlsanity.com/paper/2203.16668/) (2022)
- [Smoothness-Adaptive Dynamic Pricing with Nonparametric Demand Learning](https://mlsanity.com/paper/2310.07558/) (2023)
- [Parameter-Adaptive Dynamic Pricing](https://mlsanity.com/paper/2503.00929/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)
- [Nonparametric Contextual Pricing and Inventory Learning under Censored Demand](https://mlsanity.com/paper/2608.30944/) (2026)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)

## Abstract (arXiv)

We study a non-parametric multi-armed bandit problem with stochastic covariates, where a key complexity driver is the smoothness of payoff functions with respect to covariates. Previous studies have focused on deriving minimax-optimal algorithms in cases where it is a priori known how smooth the payoff functions are. In practice, however, the smoothness of payoff functions is typically not known in advance, and misspecification of smoothness may severely deteriorate the performance of existing methods. In this work, we consider a framework where the smoothness of payoff functions is not known, and study when and how algorithms may adapt to unknown smoothness. First, we establish that designing algorithms that adapt to unknown smoothness of payoff functions is, in general, impossible. However, under a self-similarity condition (which does not reduce the minimax complexity of the dynamic optimization problem at hand), we establish that adapting to unknown smoothness is possible, and further devise a general policy for achieving smoothness-adaptive performance. Our policy infers the smoothness of payoffs throughout the decision-making process, while leveraging the structure of off-the-shelf non-adaptive policies. We establish that for problem settings with either differentiable or non-differentiable payoff functions, this policy matches (up to a logarithmic scale) the regret rate that is achievable when the smoothness of payoffs is known a priori.