# Optimal Streaming Algorithms for Multi-Armed Bandits

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 23 Oct 2024.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [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)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [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)
- [An Optimal Elimination Algorithm for Learning a Best Arm](https://mlsanity.com/paper/2006.11647/) (2020)
- [Adaptive Multiple-Arm Identification](https://mlsanity.com/paper/1706.01026/) (2017)
- [Streaming Algorithms for Stochastic Multi-armed Bandits](https://mlsanity.com/paper/2012.05142/) (2020)

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

- [Near-Optimal Online Deployment and Routing for Streaming LLMs](https://mlsanity.com/paper/2506.17254/) (2025)
- [Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits](https://mlsanity.com/paper/2603.13742/) (2026)
- [Locally Differentially Private Thresholding Bandits](https://mlsanity.com/paper/2507.23073/) (2025)
- [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)

This paper studies two variants of the best arm identification (BAI) problem under the streaming model, where we have a stream of n arms with reward distributions supported on [0,1] with unknown means. The arms in the stream are arriving one by one, and the algorithm cannot access an arm unless it is stored in a limited size memory. We first study the streaming eps-top-k arms identification problem, which asks for k arms whose reward means are lower than that of the k-th best arm by at most eps with probability at least 1-δ. For general eps ∈ (0,1), the existing solution for this problem assumes k = 1 and achieves the optimal sample complexity O(fracneps2 log frac1δ) using O(log^*(n)) (log^*(n) equals the number of times that we need to apply the logarithm function on n before the results is no more than 1.) memory and a single pass of the stream. We propose an algorithm that works for any k and achieves the optimal sample complexity O(fracneps2 logfrackδ) using a single-arm memory and a single pass of the stream. Second, we study the streaming BAI problem, where the objective is to identify the arm with the maximum reward mean with at least 1-δ probability, using a single-arm memory and as few passes of the input stream as possible. We present a single-arm-memory algorithm that achieves a near instance-dependent optimal sample complexity within O(log Delta2-1) passes, where Delta2 is the gap between the mean of the best arm and that of the second best arm.