Research map / Bandits and online learning / Multi-armed bandits
Near Optimal Best Arm Identification for Clustered Bandits
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.
Proposes two successive-elimination based fixed-confidence algorithms (Cl-BAI and BAI-Cl, plus BAI-Cl++) that jointly cluster agents by the bandit they face and identify each cluster's best arm, with sample complexity bounds and a matching-order lower bound for constant M.
Problem
Best arm identification for N agents grouped into M unknown clusters, each cluster facing a different stochastic K-armed bandit, under a delta-PC guarantee while minimizing sample and communication cost.
Approach
Two-phase successive-elimination schemes: Cl-BAI clusters agents first (using a separability assumption that best arms differ by at least eta across bandits) and then runs BAI per cluster; BAI-Cl first finds the M best arms via coupon-collector-style sampling and then assigns remaining agents to them, with BAI-Cl++ adding a second separability gap eta_1 to speed up the second phase.
Key results
- On a MovieLens-1M setup with 100 users in 6 age-group clusters, BAI-Cl++ reduces sample complexity by about 72% relative to a cluster-oblivious naive scheme.
- Lower bound of order max{M(K-M), N} log(1/delta)/Delta^2 is derived; BAI-Cl++ matches it order-wise when M is constant and N dominates.
- BAI-Cl and BAI-Cl++ consistently use fewer pulls than Cl-BAI and the naive scheme on synthetic instances, with a 65% improvement reported on Yelp.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BAI-Cl++ instead of the naive cluster-oblivious scheme | 100-user MovieLens-derived setup with 6 age-group clusters · MovieLens-derived setup | sample complexity: 72% | Helped |
| Use BAI-Cl++ instead of the naive cluster-oblivious scheme | Yelp clustered-bandit experiment · Yelp | sample complexity: 65% | Helped |
| Use BAI-Cl++ instead of BAI-Cl | MovieLens-1M age-group setup · MovieLens-1M | sample complexity | Helped |
| Increase the cluster-separation parameter η | Synthetic dataset 3 · Synthetic dataset 3 | sample complexity | Helped |
| Increase cluster-size skewness | BAI-Cl and BAI-Cl++ · Synthetic dataset 3, N=500, M=100 | sample complexity | Hurt |
| Increase cluster-size skewness | Naive scheme and Cl-BAI · Synthetic dataset 3, N=500, M=100 | sample complexity | No clear effect |
Surprising findings
- BAI-Cl-style schemes degrade as cluster sizes become more skewed, while the naive scheme and Cl-BAI are invariant to skew.
Limitations
- Requires a separability assumption (eta, and eta_1 for BAI-Cl++) across bandits that may not hold in practice.
- BAI-Cl performance worsens under highly skewed cluster sizes.
- Assumes known or lower-bounded separation parameters and unit-variance sub-Gaussian rewards.
Experimental setup
Datasets: MovieLens-1M synthetic bandit instances
Benchmarks: MovieLens-1M (derived clustered bandit setup) synthetic bandit instances
Metrics: number of arm pulls (sample complexity)
Baselines: naive per-agent successive elimination Cl-BAI BAI-Cl
Builds on: successive elimination coupon collector
Closest papers by meaning
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.91)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.90)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.90)
- Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.90)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.89)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.