# Batched Nonparametric Contextual Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 70 references that are in the map.
- First posted on arXiv 27 Feb 2024.

## Builds on (most cited first, 30 of 32)

- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Inference for Batched Bandits](https://mlsanity.com/paper/2002.03217/) (2020)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)
- [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [Transfer Learning for Contextual Multi-armed Bandits](https://mlsanity.com/paper/2211.12612/) (2022)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [Nonparametric Stochastic Contextual Bandits](https://mlsanity.com/paper/1801.01750/) (2018)
- [The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates](https://mlsanity.com/paper/1803.00316/) (2018)
- [Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards](https://mlsanity.com/paper/1902.00819/) (2019)
- [Smoothness-Adaptive Contextual Bandits](https://mlsanity.com/paper/1910.09714/) (2019)
- [Self-Tuning Bandits over Unknown Covariate-Shifts](https://mlsanity.com/paper/2007.08584/) (2020)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Online Batch Decision-Making with High-Dimensional Covariates](https://mlsanity.com/paper/2002.09438/) (2020)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)

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

- [Batched Nonparametric Bandits via k-Nearest Neighbor UCB](https://mlsanity.com/paper/2505.10498/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)
- [Demystifying Design Choices of Reinforcement Fine-tuning: A Batched Contextual Bandit Learning Perspective](https://mlsanity.com/paper/2601.22532/) (2026)

## Abstract (arXiv)

We study nonparametric contextual bandits under batch constraints, where the expected reward for each action is modeled as a smooth function of covariates, and the policy updates are made at the end of each batch of observations. We establish a minimax regret lower bound for this setting and propose a novel batch learning algorithm that achieves the optimal regret (up to logarithmic factors). In essence, our procedure dynamically splits the covariate space into smaller bins, carefully aligning their widths with the batch size. Our theoretical results suggest that for nonparametric contextual bandits, a nearly constant number of policy updates can attain optimal regret in the fully online setting.