# A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits

arXiv: https://arxiv.org/abs/2205.00984 · HTML: https://mlsanity.com/paper/2205.00984/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 2 May 2022.

## Builds on (most cited first, 8 of 8)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits](https://mlsanity.com/paper/2004.04666/) (2020)
- [Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory](https://mlsanity.com/paper/1901.08387/) (2019)
- [Streaming Algorithms for Stochastic Multi-armed Bandits](https://mlsanity.com/paper/2012.05142/) (2020)
- [On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck](https://mlsanity.com/paper/2112.06130/) (2021)

## Built on by (most cited first, 12 of 12)

- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2309.03145/) (2023)
- [Tight Memory-Regret Lower Bounds for Streaming Bandits](https://mlsanity.com/paper/2306.07903/) (2023)
- [Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2405.19752/) (2024)
- [Near-Optimal Online Deployment and Routing for Streaming LLMs](https://mlsanity.com/paper/2506.17254/) (2025)
- [Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2503.02428/) (2025)
- [Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits](https://mlsanity.com/paper/2603.13742/) (2026)
- [Lookahead identification in adversarial bandits: accuracy and memory bounds](https://mlsanity.com/paper/2603.00803/) (2026)
- [Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits](https://mlsanity.com/paper/2606.08977/) (2026)
- [Memory--Batch Tradeoffs in Lipschitz Bandits](https://mlsanity.com/paper/2608.07922/) (2026)

## Abstract (arXiv)

The stochastic K-armed bandit problem has been studied extensively due to its applications in various domains ranging from online advertising to clinical trials. In practice however, the number of arms can be very large resulting in large memory requirements for simultaneously processing them. In this paper we consider a streaming setting where the arms are presented in a stream and the algorithm uses limited memory to process these arms. Here, the goal is not only to minimize regret, but also to do so in minimal memory. Previous algorithms for this problem operate in one of the two settings: they either use Omega(log log T) passes over the stream (Rathod, 2021; Chaudhuri and Kalyanakrishnan, 2020; Liau et al., 2018), or just a single pass (Maiti et al., 2021). In this paper we study the trade-off between memory and regret when B passes over the stream are allowed, for any B ≥ 1, and establish tight regret upper and lower bounds for any B-pass algorithm. Our results uncover a surprising *sharp transition phenomenon*: O(1) memory is sufficient to achieve widetildeThetaBig(T^frac12 + frac12B+2-2Big) regret in B passes, and increasing the memory to any quantity that is o(K) has almost no impact on further reducing this regret, unless we use Omega(K) memory. Our main technical contribution is our lower bound which requires the use of information-theoretic techniques as well as ideas from round elimination to show that the *residual problem* remains challenging over subsequent passes.