# Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 18 references that are in the map.
- First posted on arXiv 4 Mar 2025.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [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)
- [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)
- [Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2405.19752/) (2024)
- [Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap](https://mlsanity.com/paper/2502.01067/) (2025)

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

- [On the Problem of Best Arm Retention](https://mlsanity.com/paper/2504.11866/) (2025)
- [Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits](https://mlsanity.com/paper/2606.08977/) (2026)

## Abstract (arXiv)

We study the problem of minimizing gap-dependent regret for single-pass streaming stochastic multi-armed bandits (MAB). In this problem, the n arms are present in a stream, and at most m<n arms and their statistics can be stored in the memory. We establish tight non-asymptotic regret bounds regarding all relevant parameters, including the number of arms n, the memory size m, the number of rounds T and (Deltai)i∈ [n] where Deltai is the reward mean gap between the best arm and the i-th arm. These gaps are not known in advance by the player. Specifically, for any constant α ≥ 1, we present two algorithms: one applicable for m≥ frac23n with regret at most OαBig(frac(n-m)T^frac1α + 1n^1 + frac1α + 1displaystylesumi:Deltai > 0Deltai1 - 2αBig) and another applicable for m<frac23n with regret at most OαBig(fracT^frac1α+1m^frac1α+1displaystylesumi:Deltai > 0Deltai1 - 2αBig). We also prove matching lower bounds for both cases by showing that for any constant α≥ 1 and any m≤ k < n, there exists a set of hard instances on which the regret of any algorithm is OmegaαBig(frac(k-m+1) T^frac1α+1k^1 + frac1α+1 sumi:Deltai > 0Deltai1-2αBig). This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an OBig(sumicolonDelta>0 frac√Tlog TDeltaiBig) upper bound for the special case of α=1 and m=O(1) was established by Agarwal, Khanna and Patil (COLT'22). In contrast, our results provide the correct order of regret as ThetaBig(frac1√msumicolonDelta>0frac√TDeltaiBig).