mlsanityData to 7 Oct 2026

Lipschitz Bandits with Batched Feedback

arXiv 2110.09722 ↗First posted 19 Oct 2021cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for a T-step problem with Lipschitz reward of zooming dimension dz, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate widetildeOleft(T^fracdz+1dz+2right) using only O left( loglog Tright) batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that Omega(loglog T) batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate (up to logarithmic factors) using minimal communication.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 16 of its 60 references that are in the map. First posted on arXiv 19 Oct 2021.

Builds on

16 of 60 references.

References · 16

  1. 2019Batched Multi-armed Bandits Problemcited by 97
  2. 2020Inference for Batched Banditscited by 63
  3. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  4. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 60
  5. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 59
  6. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  7. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  8. 2019Regret Bounds for Batched Banditscited by 49
  9. 2019Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adaptingcited by 42
  10. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  11. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  12. 2020Efficient Contextual Bandits with Continuous Actionscited by 24
4 more
  1. 2020Collaborative Top Distribution Identifications with Limited Interactioncited by 21
  2. 2020Adaptive Discretization for Model-Based Reinforcement Learningcited by 13
  3. 2019Nonparametric Contextual Bandits in an Unknown Metric Spacecited by 5
  4. 2020Bandits for BMO Functionscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 4; 2025: 6; 2026: 6.

21 papers.

Sort:

  1. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  2. 2023A Lipschitz Bandits Approach for Continuous Hyperparameter Optimizationcited by 9
  3. 2022Federated X-Armed Banditcited by 5
  4. 2025Quantum Lipschitz Banditscited by 4
  5. 2024Batched Nonparametric Contextual Banditscited by 3
  6. 2025Multiplayer Information Asymmetric Bandits in Metric Spacescited by 3
  7. 2024Batched Stochastic Bandit for Nondegenerate Functionscited by 2
  8. 2024A Complete Characterization of Learnability for Stochastic Noisy Banditscited by 2
  9. 2025Batched Nonparametric Bandits via k-Nearest Neighbor UCBcited by 1
  10. 2025Lipschitz Bandits with Stochastic Delayed Feedbackcited by 1
  11. 2026Lipschitz Dueling Bandits over Continuous Action Spacescited by 1
  12. 2023From Random Search to Bandit Learning in Metric Measure Spacescited by 0
9 more
  1. 2023Personalized Federated X -armed Banditcited by 0
  2. 2024The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costscited by 0
  3. 2025Batched Bandits with Heavy-Tailed Rewardscited by 0
  4. 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margincited by 0
  5. 2026Instance-dependent Stochastic Lipschitz banditcited by 0
  6. 2026Memory--Batch Tradeoffs in Lipschitz Banditscited by 0
  7. 2026Lipschitz Bandits with Arbitrary Feedback Delayscited by 0
  8. 2026Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimensioncited by 0
  9. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochscited by 0