Lune

SODA2025Top-tier venue

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits

Yuchen He, Zichun Ye, Chihao Zhang

Abstract

We study the stochastic multi-armed bandit problem in the -pass streaming model. In this problem, the arms are present in a stream and at most < arms and their statistics can be stored in the memory. We give a complete characterization of the optimal regret in terms of , and . Specifically, we design an algorithm with ˜ ( -)

regret and complement it with an Ω ( -)

bound when the number of rounds is sufficiently large. Our results are tight up to a logarithmic factor in and . 1 In this article, the notations ˜ (•), Ω (•) and Θ(•) subsume a logarithmic factor in and .

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Optimal Streaming Algorithms for Multi-Armed Bandits cites Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory
  • Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits cites Optimal Streaming Algorithms for Multi-Armed Bandits
  • Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits cites Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization
  • Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits cites Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap
  • Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits cites Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits
  • Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits cites Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity
  • Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization cites Optimal Streaming Algorithms for Multi-Armed Bandits
  • Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization cites Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory
  • Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap cites Optimal Streaming Algorithms for Multi-Armed Bandits
  • Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap cites Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization
  • Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap cites Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits
  • Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap cites Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity
  • Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits cites Optimal Streaming Algorithms for Multi-Armed Bandits
  • Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits cites Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory
  • Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits cites Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization
  • Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits cites Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity
  • Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity cites Optimal Streaming Algorithms for Multi-Armed Bandits
  • Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity cites Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory
  • Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity cites Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality GapNikolai Karpov, Chen WangAAAI 2025 · 1 citation
  2. Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed BanditsVladimir Braverman, Chen Wang, Liudeng Wang, Samson ZhouICML 2026

Builds on10

  1. Regret Minimisation in Multi-Armed Bandits Using Bounded Arm MemoryArghya Roy Chaudhuri, Shivaram KalyanakrishnanAAAI 2020 · 21 citations
  2. Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret MinimizationArnab Maiti, Vishakha Patil, Arindam KhanNeurIPS 2021 · 19 citations
  3. Optimal Streaming Algorithms for Multi-Armed BanditsTianyuan Jin, Keke Huang, Jing Tang, Xiaokui XiaoICML 2021 · 16 citations
  4. Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample ComplexitySepehr Assadi, Chen WangNeurIPS 2022 · 10 citations
  5. Tight Regret Bounds for Single-pass Streaming Multi-armed BanditsChen WangICML 2023 · 8 citations

Related papers

  1. Linear Streaming Bandit: Regret Minimization and Fixed-Budget Epsilon-Best Arm IdentificationYuming Shao, Zhixuan FangAAAI 2025 · 2 citations
  2. Regret Bounds for Batched BanditsHossein Esfandiari, Amin Karbasi, Abbas Mehrabian, Vahab S. MirrokniAAAI 2021 · 74 citations
  3. Lipschitz Bandits in Optimal SpaceXiaoyi Zhu, Zengfeng HuangICLR 2025
  4. Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed banditsSepehr Assadi, Chen WangSTOC 2020 · 6 citations
  5. Bandits with many optimal armsRianne de Heide, James Cheshire, Pierre Ménard, Alexandra CarpentierNeurIPS 2021 · 28 citations
Dusk over the sea between two cliffs drawn in fine vertical lines