# Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 3 Jun 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Collaborative Top Distribution Identifications with Limited Interaction](https://mlsanity.com/paper/2004.09454/) (2020)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Bridging the gap between regret minimization and best arm identification, with application to A/B tests](https://mlsanity.com/paper/1810.04088/) (2018)
- [Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits](https://mlsanity.com/paper/2004.04666/) (2020)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory](https://mlsanity.com/paper/1901.08387/) (2019)
- [A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits](https://mlsanity.com/paper/2205.00984/) (2022)

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

- [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)

Regret minimization in streaming multi-armed bandits (MABs) has been studied extensively in recent years. In the single-pass setting with K arms and T trials, a regret lower bound of Omega(T2/3) has been proved for any algorithm with o(K) memory (Maiti et al. [NeurIPS'21]; Agarwal at al. [COLT'22]). On the other hand, however, the previous best regret upper bound is still O(K1/3 T2/3log1/3(T)), which is achieved by the streaming implementation of the simple uniform exploration. The O(K1/3log1/3(T)) gap leaves the open question of the tight regret bound in the single-pass MABs with sublinear arm memory. In this paper, we answer this open problem and complete the picture of regret minimization in single-pass streaming MABs. We first improve the regret lower bound to Omega(K1/3T2/3) for algorithms with o(K) memory, which matches the uniform exploration regret up to a logarithm factor in T. We then show that the log1/3(T) factor is not necessary, and we can achieve O(K1/3T2/3) regret by finding an varepsilon-best arm and committing to it in the rest of the trials. For regret minimization with high constant probability, we can apply the single-memory varepsilon-best arm algorithms in Jin et al. [ICML'21] to obtain the optimal bound. Furthermore, for the expected regret minimization, we design an algorithm with a single-arm memory that achieves O(K1/3 T2/3log(K)) regret, and an algorithm with O(log*(n))-memory with the optimal O(K1/3 T2/3) regret following the varepsilon-best arm algorithm in Assadi and Wang [STOC'20]. We further tested the empirical performances of our algorithms. The simulation results show that the proposed algorithms consistently outperform the benchmark uniform exploration algorithm by a large margin, and on occasion, reduce the regret by up to 70%.