mlsanityData to 14 Oct 2026

The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin

arXiv 2511.03708 ↗First posted 5 Nov 2025math.ST cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study batched nonparametric contextual bandits under a margin condition when the margin parameter α is unknown. To capture the statistical cost of this ignorance, we introduce the regret inflation criterion, defined as the ratio between the regret of an adaptive algorithm and that of an oracle knowing α. We show that the optimal regret inflation grows polynomially with the horizon T, with exponent given by the value of a convex optimization problem that depends on the dimension, smoothness, and number of batches M. Moreover, the minimizer of this optimization problem directly prescribes the batch allocation and exploration strategy of a rate-optimal algorithm. Building on this principle, we develop RoBIN (RObust batched algorithm with adaptive BINning), which achieves the optimal regret inflation up to polylogarithmic factors. These results reveal a new adaptivity barrier: under batching, adaptation to an unknown margin parameter inevitably incurs a polynomial penalty, sharply characterized by a variational problem. Remarkably, this barrier vanishes once the number of batches exceeds order log log T; with only a doubly logarithmic number of updates, one can recover the oracle regret rate up to polylogarithmic factors.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 27 of its 52 references that are in the map. First posted on arXiv 5 Nov 2025.

Builds on

27 of 52 references.

References · 27

  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. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  5. 2020Inference for Batched Banditscited by 63
  6. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  7. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
  8. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  9. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  10. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  11. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  12. 2020Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Banditscited by 28
15 more
  1. 2019Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimescited by 25
  2. 2020Double Explore-then-Commit: Asymptotic Optimality and Beyondcited by 24
  3. 2022Transfer Learning for Contextual Multi-armed Banditscited by 24
  4. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  5. 2021Parallelizing Thompson Samplingcited by 20
  6. 2021Batched Thompson Samplingcited by 19
  7. 2018Nonparametric Stochastic Contextual Banditscited by 17
  8. 2018The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariatescited by 16
  9. 2019Smoothness-Adaptive Contextual Banditscited by 15
  10. 2020Self-Tuning Bandits over Unknown Covariate-Shiftscited by 12
  11. 2020Online Batch Decision-Making with High-Dimensional Covariatescited by 7
  12. 2023Provably Efficient High-Dimensional Bandit Learning with Batched Feedbackscited by 3
  13. 2024Batched Nonparametric Contextual Banditscited by 3
  14. 2024Batched Stochastic Bandit for Nondegenerate Functionscited by 2
  15. 2025Batched Nonparametric Bandits via k-Nearest Neighbor UCBcited by 1

Built on by

Not cited yet.