mlsanityData to 14 Oct 2026

Batched Nonparametric Contextual Bandits

arXiv 2402.17732 ↗First posted 27 Feb 2024math.ST cs.LG stat.MLcited by 3

Not on the map. Why?

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.

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

32 of 70 references.

References · 32

  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  3. 2019Batched Multi-armed Bandits Problemcited by 98
  4. 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
  5. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  6. 2020Inference for Batched Banditscited by 63
  7. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  8. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
  9. 2017Stochastic Bandit Models for Delayed Conversionscited by 54
  10. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  11. 2019Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adaptingcited by 42
  12. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
20 more
  1. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  2. 2020Stochastic bandits with arm-dependent delayscited by 36
  3. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  4. 2020Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Banditscited by 28
  5. 2019Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimescited by 25
  6. 2020Double Explore-then-Commit: Asymptotic Optimality and Beyondcited by 24
  7. 2022Transfer Learning for Contextual Multi-armed Banditscited by 24
  8. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  9. 2021Parallelizing Thompson Samplingcited by 20
  10. 2021Batched Thompson Samplingcited by 19
  11. 2018Nonparametric Stochastic Contextual Banditscited by 17
  12. 2018The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariatescited by 16
  13. 2019Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewardscited by 15
  14. 2019Smoothness-Adaptive Contextual Banditscited by 15
  15. 2020Self-Tuning Bandits over Unknown Covariate-Shiftscited by 12
  16. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  17. 2020Online Batch Decision-Making with High-Dimensional Covariatescited by 7
  18. 2023Adversarial Rewards in Universal Learning for Contextual Banditscited by 5
  19. 2023Provably Efficient High-Dimensional Bandit Learning with Batched Feedbackscited by 3
  20. 2017Optimal sequential treatment allocationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Batched Nonparametric Bandits via k-Nearest Neighbor UCBcited by 1
  2. 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margincited by 0
  3. 2026Demystifying Design Choices of Reinforcement Fine-tuning: A Batched Contextual Bandit Learning Perspectivecited by 0