Research map / Bandits and online learning / Multi-armed bandits
Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap
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.
Shows that with known second-best optimality gap, Theta(log n) passes (up to log log n) are necessary and sufficient for near-instance-optimal pure exploration in streaming MABs with sublinear memory, via a matching lower bound and a single-arm-memory elimination algorithm.
Problem
Pure exploration in multi-pass streaming multi-armed bandits when the optimality gap Delta_[2] is known: how many passes are needed to find the best arm with near-instance-optimal sample complexity sum_i 1/Delta_[i]^2 under sublinear memory.
Approach
Lower-bound construction with two special arms per batch whose gap is fixed at gamma so Delta_[2] reveals nothing about the realization, plus an elimination algorithm that uses geometrically decreasing gaps eps_p = Delta_[2] * n^(1-p/P) so that P passes give n^(2/P) overhead, yielding log n passes with single-arm memory.
Key results
- Lower bound: any algorithm with known Delta_[2], o(n/polylog n) arm memory and O(sum 1/Delta_[i]^2 * log n) pulls needs Omega(log n / log log n) passes.
- Upper bound: a (P+1)-pass algorithm with single-arm memory uses O(log(nP/delta) * sum n^(2/P)/Delta_[i]^2) pulls; with P=Theta(log n) this gives O(sum 1/Delta_[i]^2 * log n) pulls.
- Experiments on synthetic streaming MAB instances show the algorithm has the best sample efficiency among compared methods while using far fewer passes than the O(log(1/Delta_[2]))-pass baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Provide the known optimality gap Δ_[2] to the streaming algorithm | Streaming pure-exploration MAB algorithm · Streaming MABs, instance-sensitive arm-pull complexity | passes: O(\log(1/\Delta_{[2]})) -> O(\log{n}) | Helped |
| Use the proposed elimination algorithm with known Δ_[2] and P passes | Streaming pure-exploration MAB algorithm · Streaming MABs, known Δ_[2] | arm pulls: O\left(\log \left(\frac{n P}{\delta}\right) \sum_{i = 2}^n \frac{n^{2/P}}{\Delta^2_{[i]}}\right) | Helped |
| Restrict memory to o(n/log^3 n) arms while targeting instance-sensitive sample complexity | Streaming MAB algorithms with known Δ_[2] · Streaming MABs | passes: \Omega\paren{\frac{\log(n)}{\log\log(n)}} | Hurt |
Surprising findings
- Knowing Delta_[2] allows the pass complexity to be independent of Delta_[2] (log n passes instead of log(1/Delta_[2])), with a sample bound that has a log n factor rather than log log(1/Delta_[i]).
Limitations
- Sample complexity has a log n multiplicative factor rather than the classical log log(1/Delta_[i]) instance-optimal factor.
- Lower bound holds only up to log log n terms in pass count and polylog n factors in memory/sample bounds.
Experimental setup
Metrics: sample complexity (arm pulls) pass complexity memory (arms stored) success probability
Baselines: single-pass algorithm with known Delta_[2] (Assadi and Wang 2020 style) O(log(1/Delta_[2]))-pass algorithm (Jin et al. ICML'21)
Builds on: Jin et al. ICML'21 multi-pass streaming bandits Assadi and Wang COLT'24 multi-pass lower bound successive elimination
Closest papers by meaning
- Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity (NeurIPS 2022 · similarity 0.94)
- Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits (ICML 2023 · similarity 0.93)
- Optimal Streaming Algorithms for Multi-Armed Bandits (ICML 2021 · similarity 0.92)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.89)
- Near Optimal Non-asymptotic Sample Complexity of 1-Identification (ICML 2025 · similarity 0.88)
- Linear Streaming Bandit: Regret Minimization and Fixed-Budget Epsilon-Best Arm Identification (AAAI 2025 · similarity 0.88)
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.