mlsanityData to 14 Oct 2026

Memory--Batch Tradeoffs in Lipschitz Bandits

arXiv 2608.07922 ↗First posted 8 Aug 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

Lipschitz bandits admit near-optimal regret widetilde Od(T(d+1)/(d+2)) with little memory under full adaptivity, or with few batches under unrestricted memory. We characterize the minimax expected pseudo-regret over T rounds with W bits of memory and at most B batches in dimension d. For every memory budget W, we prove a lower bound of order T^fracd+2d+3 (1+(B-1)W)^-frac1d(d+3). When Wgtrsimdlog(eT), algorithms with fixed batch boundaries attain, up to logarithmic factors, the larger of this bound and the optimal B-batch regret with unrestricted memory. The analysis separates fine-scale comparisons from the regional information needed to allocate their samples at low regret. Attaining widetilde Od(T(d+1)/(d+2)) regret requires both B=Omegad(loglog T) and (B-1)W=widetildeOmegad(Td/(d+2)). With one bit of memory, minimax regret is widetildeThetad(TB-1/(d+2)) under adaptive batch boundaries while Thetad(T) under fixed boundaries.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 42 references that are in the map. First posted on arXiv 8 Aug 2026.

Builds on

23 of 42 references.

References · 23

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  2. 2019Batched Multi-armed Bandits Problemcited by 98
  3. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 60
  4. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  5. 2019Regret Bounds for Batched Banditscited by 49
  6. 2017The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regimecited by 31
  7. 2014Bandit Algorithms for Tree Searchcited by 25
  8. 2017Stochastic Multi-armed Bandits in Constant Spacecited by 22
  9. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  10. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  11. 2022Memory Bounds for the Experts Problemcited by 20
  12. 2020Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Banditscited by 18
11 more
  1. 2022Online Prediction in Sub-linear Spacecited by 16
  2. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  3. 2019Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memorycited by 13
  4. 2022A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Banditscited by 12
  5. 2023Tight Regret Bounds for Single-pass Streaming Multi-armed Banditscited by 9
  6. 2020Memory-Constrained No-Regret Learning in Adversarial Banditscited by 5
  7. 2023The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Banditscited by 5
  8. 2024Optimal Streaming Algorithms for Multi-Armed Banditscited by 5
  9. 2023Tight Memory-Regret Lower Bounds for Streaming Banditscited by 4
  10. 2026Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Banditscited by 1
  11. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1

Built on by

Not cited yet.