# Lipschitz Bandits with Batched Feedback

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

## Key facts

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

## Builds on (most cited first, 16 of 16)

- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (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)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [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 Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [Efficient Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2006.06040/) (2020)
- [Collaborative Top Distribution Identifications with Limited Interaction](https://mlsanity.com/paper/2004.09454/) (2020)
- [Adaptive Discretization for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2007.00717/) (2020)
- [Nonparametric Contextual Bandits in an Unknown Metric Space](https://mlsanity.com/paper/1908.01228/) (2019)
- [Bandits for BMO Functions](https://mlsanity.com/paper/2007.08703/) (2020)

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

- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [A Lipschitz Bandits Approach for Continuous Hyperparameter Optimization](https://mlsanity.com/paper/2302.01539/) (2023)
- [Federated X-Armed Bandit](https://mlsanity.com/paper/2205.15268/) (2022)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)
- [Multiplayer Information Asymmetric Bandits in Metric Spaces](https://mlsanity.com/paper/2503.08004/) (2025)
- [Batched Stochastic Bandit for Nondegenerate Functions](https://mlsanity.com/paper/2405.05733/) (2024)
- [A Complete Characterization of Learnability for Stochastic Noisy Bandits](https://mlsanity.com/paper/2410.09597/) (2024)
- [Batched Nonparametric Bandits via k-Nearest Neighbor UCB](https://mlsanity.com/paper/2505.10498/) (2025)
- [Lipschitz Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2510.00309/) (2025)
- [Lipschitz Dueling Bandits over Continuous Action Spaces](https://mlsanity.com/paper/2604.00523/) (2026)
- [From Random Search to Bandit Learning in Metric Measure Spaces](https://mlsanity.com/paper/2305.11509/) (2023)
- [Personalized Federated X -armed Bandit](https://mlsanity.com/paper/2310.16323/) (2023)
- [The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs](https://mlsanity.com/paper/2410.14533/) (2024)
- [Batched Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2510.03798/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)
- [Memory--Batch Tradeoffs in Lipschitz Bandits](https://mlsanity.com/paper/2608.07922/) (2026)
- [Lipschitz Bandits with Arbitrary Feedback Delays](https://mlsanity.com/paper/2608.15036/) (2026)
- [Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension](https://mlsanity.com/paper/2609.05214/) (2026)
- [Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs](https://mlsanity.com/paper/2609.23127/) (2026)

## 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.