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.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
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
Cited by top-tier papers2
Builds on10
- Regret Minimisation in Multi-Armed Bandits Using Bounded Arm MemoryArghya Roy Chaudhuri, Shivaram KalyanakrishnanAAAI 2020 · 21 citations
- 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
- Optimal Streaming Algorithms for Multi-Armed BanditsTianyuan Jin, Keke Huang, Jing Tang, Xiaokui XiaoICML 2021 · 16 citations
- Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample ComplexitySepehr Assadi, Chen WangNeurIPS 2022 · 10 citations
- Tight Regret Bounds for Single-pass Streaming Multi-armed BanditsChen WangICML 2023 · 8 citations
Related papers
- Linear Streaming Bandit: Regret Minimization and Fixed-Budget Epsilon-Best Arm IdentificationYuming Shao, Zhixuan FangAAAI 2025 · 2 citations
- Regret Bounds for Batched BanditsHossein Esfandiari, Amin Karbasi, Abbas Mehrabian, Vahab S. MirrokniAAAI 2021 · 74 citations
- Lipschitz Bandits in Optimal SpaceXiaoyi Zhu, Zengfeng HuangICLR 2025
- Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed banditsSepehr Assadi, Chen WangSTOC 2020 · 6 citations
- Bandits with many optimal armsRianne de Heide, James Cheshire, Pierre Ménard, Alexandra CarpentierNeurIPS 2021 · 28 citations
