Research map / Bandits and online learning / Multi-armed bandits

The Batch Complexity of Bandit Pure Exploration

ICML 2025 · Bandits and online learning › Multi-armed bandits · approach: Pure exploration algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives an instance-dependent lower bound on batch complexity for fixed-confidence pure exploration and a general batched algorithm (PET) with near-matching batch and sample complexity guarantees for Top-k and thresholding bandits.

Problem

Fixed-confidence pure exploration in stochastic multi-armed bandits with few batches: how many batches are needed to keep sample complexity close to fully sequential algorithms.

Approach

Derives a batch-count lower bound from sequences of increasingly hard Gaussian instances linked by affine interpolation, and proposes Phased Explore then Track (PET), which explores uniformly until a worst-case confidence-set complexity matches the phase budget, then samples Track-and-Stop-like in at most two batches per phase.

Key results

• PET achieves batch complexity bounded by log2(T*_b/T0)+5 and expected sample complexity with dominant term 48K T* ln T*, matching the log(T*/T_min) batch lower bound up to constants.
• In 10-arm BAI experiments with delta=0.05 over 1000 runs, PET uses similarly few batches as Opt-BBAI but has lower sample complexity.
• Batched Track-and-Stop shows high average sample complexity on a two-arm thresholding instance, while PET does not.

Measured effects reported in the paper

Surprising findings

• Batched Track-and-Stop performs sub-optimally on some thresholding instances, despite good performance on BAI.

Limitations

• Uniform exploration costs K T* samples, losing a factor K in sample complexity versus optimal.
• Lower bound depends on T_min and constants; it vanishes when T* is known exactly.
• Assumptions needed for the analysis hold on Top-k and thresholding but not generally shown for all pure exploration problems.

Experimental setup

Benchmarks: 10-arm best arm identification with Gaussian rewards two-arm thresholding bandit (threshold 0.6, means 0.5 and 0.6)

Metrics: sample complexity batch complexity

Baselines: Round Robin Track-and-Stop (batched modification) Opt-BBAI

Builds on: Track-and-Stop Opt-BBAI collaborative bandit lower bounds

Closest papers by meaning

• Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.92)
• Robust Pure Exploration in Linear Bandits with Limited Budget (ICML 2021 · similarity 0.92)
• Fast Pure Exploration via Frank-Wolfe (NeurIPS 2021 · similarity 0.91)
• Near Optimal Non-asymptotic Sample Complexity of 1-Identification (ICML 2025 · similarity 0.90)
• Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap (AAAI 2025 · similarity 0.89)
• Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms (ICML 2025 · similarity 0.89)