# Tight Memory-Regret Lower Bounds for Streaming Bandits

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

## Key facts

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

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

- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [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)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (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)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Estimating Entropy of Distributions in Constant Space](https://mlsanity.com/paper/1911.07976/) (2019)
- [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, 4 of 4)

- [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)
- [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)
- [Memory--Batch Tradeoffs in Lipschitz Bandits](https://mlsanity.com/paper/2608.07922/) (2026)

## Abstract (arXiv)

In this paper, we investigate the streaming bandits problem, wherein the learner aims to minimize regret by dealing with online arriving arms and sublinear arm memory. We establish the tight worst-case regret lower bound of Omega left( (TB)α K1-αright), α = 2B / (2B+1-1) for any algorithm with a time horizon T, number of arms K, and number of passes B. The result reveals a separation between the stochastic bandits problem in the classical centralized setting and the streaming setting with bounded arm memory. Notably, in comparison to the well-known Omega(√KT) lower bound, an additional double logarithmic factor is unavoidable for any streaming bandits algorithm with sublinear memory permitted. Furthermore, we establish the first instance-dependent lower bound of Omega left(T1/(B+1) sumDeltax>0 fracμ^*Deltaxright) for streaming bandits. These lower bounds are derived through a unique reduction from the regret-minimization setting to the sample complexity analysis for a sequence of ε-optimal arms identification tasks, which maybe of independent interest. To complement the lower bound, we also provide a multi-pass algorithm that achieves a regret upper bound of tildeO left( (TB)α K1 - αright) using constant arm memory.