# Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2020.

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

- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [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)
- [A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits](https://mlsanity.com/paper/2205.00984/) (2022)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Approximate Top-m Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2204.05245/) (2022)
- [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (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)
- [Optimal Streaming Algorithms for Multi-Armed Bandits](https://mlsanity.com/paper/2410.17835/) (2024)
- [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)
- [Kadabra: Adapting Kademlia for the Decentralized Web](https://mlsanity.com/paper/2210.12858/) (2022)
- [Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits](https://mlsanity.com/paper/2603.13742/) (2026)
- [Better Bounds for the Distributed Experts Problem](https://mlsanity.com/paper/2603.09168/) (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)

Consider the following abstract coin tossing problem: Given a set of n coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point -- any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only O(logn) coins and then iteratively refine it further and further, leading to algorithms with O(loglog(n)) memory, O(log^*(n)) memory, and finally a one that only stores a single extra coin in memory -- the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the k most biased coins as well as other exploration problems such as finding top-k elements using noisy comparisons or finding an ε-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.