# Batched Stochastic Bandit for Nondegenerate Functions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 74 references that are in the map.
- First posted on arXiv 9 May 2024.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [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)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [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)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (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)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing](https://mlsanity.com/paper/1801.10242/) (2018)
- [A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization](https://mlsanity.com/paper/2001.10669/) (2020)
- [Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates](https://mlsanity.com/paper/1803.08586/) (2018)
- [Gaussian Process Optimization with Mutual Information](https://mlsanity.com/paper/1311.4825/) (2013)
- [Batched Dueling Bandits](https://mlsanity.com/paper/2202.10660/) (2022)
- [Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization](https://mlsanity.com/paper/2310.06689/) (2023)
- [Riemannian Optimization on the Symplectic Stiefel Manifold](https://mlsanity.com/paper/2006.15226/) (2020)
- [Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms](https://mlsanity.com/paper/2309.14506/) (2023)
- [Parallel Best Arm Identification in Heterogeneous Environments](https://mlsanity.com/paper/2207.08015/) (2022)

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

- [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)

## Abstract (arXiv)

This paper studies batched bandit learning problems for nondegenerate functions. We introduce an algorithm that solves the batched bandit problem for nondegenerate functions near-optimally. More specifically, we introduce an algorithm, called Geometric Narrowing (GN), whose regret bound is of order widetildeO ( A+d √T ). In addition, GN only needs O (log log T) batches to achieve this regret. We also provide lower bound analysis for this problem. More specifically, we prove that over some (compact) doubling metric space of doubling dimension d: 1. For any policy π, there exists a problem instance on which π admits a regret of order Omega ( A_-d √T); 2. No policy can achieve a regret of order  A_-d √T  over all problem instances, using less than  Omega ( log log T )  rounds of communications. Our lower bound analysis shows that the GN algorithm achieves near optimal regret with minimal number of batches.