# Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 43 references that are in the map.
- First posted on arXiv 14 Mar 2026.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Generalized Linear Bandits with Limited Adaptivity](https://mlsanity.com/paper/2404.06831/) (2024)
- [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017)
- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [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)
- [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)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Memory-Constrained No-Regret Learning in Adversarial Bandits](https://mlsanity.com/paper/2002.11804/) (2020)
- [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)
- [A General Memory-Bounded Learning Algorithm](https://mlsanity.com/paper/1712.03524/) (2017)

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

- [Memory--Batch Tradeoffs in Lipschitz Bandits](https://mlsanity.com/paper/2608.07922/) (2026)

## Abstract (arXiv)

We study stochastic multi-armed bandits under simultaneous constraints on space and adaptivity: the learner interacts with the environment in B batches and has only W bits of persistent memory. Prior work shows that each constraint alone is surprisingly mild: near-minimax regret widetildeO(√KT) is achievable with O(log T) bits of memory under fully adaptive interaction, and with a K-independent O(loglog T)-type number of batches when memory is unrestricted. We show that this picture breaks down in the simultaneously constrained regime. We prove that any algorithm with a W-bit memory constraint must use at least Omega(K/W) batches to achieve near-minimax regret widetildeO(√KT), even under adaptive grids. In particular, logarithmic memory rules out O(K1-varepsilon) batch complexity. Our proof is based on an information bottleneck. We show that near-minimax regret forces the learner to acquire Omega(K) bits of information about the hidden set of good arms under a suitable hard prior, whereas an algorithm with B batches and W bits of memory allows only O(BW) bits of information. A key ingredient is a localized change-of-measure lemma that yields probability-level arm exploration guarantees, which is of independent interest. We also give an algorithm that, for any bit budget W with Omega(log T) ≤ W ≤ O(Klog T), uses at most W bits of memory and widetildeO(K/W) batches while achieving regret widetildeO(√KT), nearly matching our lower bound up to polylogarithmic factors.