# Stochastic Multi-armed Bandits in Constant Space

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Dec 2017.

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

- [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)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [Towards a Pretrained Model for Restless Bandits via Multi-arm Generalization](https://mlsanity.com/paper/2310.14526/) (2023)
- [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (2023)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (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)
- [On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck](https://mlsanity.com/paper/2112.06130/) (2021)
- [Hypothesis Transfer in Bandits by Weighted Models](https://mlsanity.com/paper/2211.07387/) (2022)
- [Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2503.02428/) (2025)
- [HELLINGER-UCB: A novel algorithm for stochastic multi-armed bandit problem and cold start problem in recommender system](https://mlsanity.com/paper/2404.10207/) (2024)
- [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)
- [From Suboptimal to Optimal: One-Step Latent Flow Policies for Offline Reinforcement Learning](https://mlsanity.com/paper/2610.16984/) (2026)

## Abstract (arXiv)

We consider the stochastic bandit problem in the sublinear space setting, where one cannot record the win-loss record for all K arms. We give an algorithm using O(1) words of space with regret [ sumi=1Kfrac1Deltailog fracDeltaiDeltalog T ] where Deltai is the gap between the best arm and arm i and Delta is the gap between the best and the second-best arms. If the rewards are bounded away from 0 and 1, this is within an O(log 1/Delta) factor of the optimum regret possible without space constraints.