mlsanityData to 14 Oct 2026

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits

arXiv 2309.03145 ↗First posted 6 Sep 2023cs.LG cs.DScited by 5

Not on the map. Why?

Abstract (arXiv)

We give a near-optimal sample-pass trade-off for pure exploration in multi-armed bandits (MABs) via multi-pass streaming algorithms: any streaming algorithm with sublinear memory that uses the optimal sample complexity of O(fracnDelta2) requires Omega(fraclog(1/Delta)loglog(1/Delta)) passes. Here, n is the number of arms and Delta is the reward gap between the best and the second-best arms. Our result matches the O(log(frac1Delta))-pass algorithm of Jin et al. [ICML'21] (up to lower order terms) that only uses O(1) memory and answers an open question posed by Assadi and Wang [STOC'20].

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 16 of its 35 references that are in the map. First posted on arXiv 6 Sep 2023.

Builds on

16 of 35 references.

References · 16

  1. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 149
  2. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  3. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  4. 2019On Multi-Armed Bandit Designs for Dose-Finding Clinical Trialscited by 32
  5. 2017Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selectioncited by 28
  6. 2017Stochastic Multi-armed Bandits in Constant Spacecited by 22
  7. 2020Collaborative Top Distribution Identifications with Limited Interactioncited by 21
  8. 2022Memory Bounds for the Experts Problemcited by 20
  9. 2020Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Banditscited by 18
  10. 2022Online Prediction in Sub-linear Spacecited by 16
  11. 2019Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memorycited by 13
  12. 2022A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Banditscited by 12
4 more
  1. 2023Tight Regret Bounds for Single-pass Streaming Multi-armed Banditscited by 9
  2. 2022Communication-Efficient Collaborative Best Arm Identificationcited by 5
  3. 2023Improved Space Bounds for Learning with Expertscited by 5
  4. 2023Tight Memory-Regret Lower Bounds for Streaming Banditscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 3.

5 papers.

  1. 2024Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Banditscited by 4
  2. 2025Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Banditscited by 2
  3. 2026Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Banditscited by 1
  4. 2026Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Banditscited by 0
  5. 2026Memory--Batch Tradeoffs in Lipschitz Banditscited by 0