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

Ruiyuan HuangSchool of Data Science, Fudan [email protected], Zicheng LyuSchool of Data Science, Fudan [email protected] ZhuSchool of Data Science, Fudan [email protected], Zengfeng HuangSchool of Data Science, Fudan UniversityShanghai Innovation [email protected] · 2026

Read Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits by Ruiyuan HuangSchool of Data Science, Fudan [email protected], Zicheng LyuSchool of Data Science, Fudan [email protected] ZhuSchool of Data Science, Fudan [email protected], Zengfeng HuangSchool of Data Science, Fudan UniversityShanghai Innovation [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13742.txt.

Introduction

Ruiyuan Huang, Zicheng Lyu, Xiaoyi Zhu, and Zengfeng Huang study stochastic bandits under joint space and adaptivity constraints. The learner interacts in B batches and holds only W bits of persistent memory. Each constraint alone is mild, with near-minimax regret achievable under either one, prior work shows. Together they bite: any W-bit memory algorithm needs at least on the order of K over W batches for near-minimax regret. The proof rests on an information bottleneck and a localized change-of-measure lemma.

Catalog record

CREATORRuiyuan HuangSchool of Data Science, Fudan [email protected], Zicheng LyuSchool of Data Science, Fudan [email protected] ZhuSchool of Data Science, Fudan [email protected], Zengfeng HuangSchool of Data Science, Fudan UniversityShanghai Innovation [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95773
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13742

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits Ruiyuan HuangSchool of Data Science, Fudan [email protected], Zicheng LyuSchool of Data Science, Fudan [email protected] ZhuSchool of Data Science, Fudan [email protected], Zengfeng HuangSchool of Data Science, Fudan UniversityShanghai Innovation [email protected] Abstract We study stochastic multi-armed bandits under simultaneous constraints on space and adaptivity: the learner interacts with the environment in B B batches and has only W W bits of persistent memory. Prior work shows that each constraint alone is surprisingly mild: near-minimax regret O ~ ​ ( K ​ T ) \widetilde{O}(\sqrt{KT}) is achievable with O ⁡ ( log ⁡ T ) O(\log T) bits of memory under fully adaptive interaction, and with a K K -independent O ⁡ ( log ⁡ log ⁡ T ) O(\log\log 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 W -bit memory constraint must use at least Ω ⁡ ( K / W ) \Omega(K/W) batches to achieve near-minimax regret O ~ ​ ( K ​ T ) \widetilde{O}(\sqrt{KT}) , even under adaptive grids. In particular, logarithmic memory rules out O ⁡ ( K 1 − ε ) O(K^{1-\varepsilon}) batch complexity. Our proof is based on an information bottleneck. We show that near-minimax regret forces the learner to acquire Ω ⁡ ( K ) \Omega(K) bits of information about the hidden set of good arms under a suitable hard prior, whereas an algorithm with B B batches and W W bits of memory allows only O ⁡ ( B ​ W ) 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 W with Ω ⁡ ( log ⁡ T ) ≤ W ≤ O ⁡ ( K ​ log ⁡ T ) \Omega(\log T)\leq W\leq O(K\log T) , uses at most W W bits of memory and O ~ ​ ( K / W ) \widetilde{O}(K/W) batches while achieving regret O ~ ​ ( K ​ T ) \widetilde{O}(\sqrt{KT}) , nearly matching our lower bound up to polylogarithmic factors. † † footnotetext: ∗ Equal contribution. † Corresponding author. 1 Introduction The stochastic multi-armed bandit (MAB) problem is a standard model for sequential decision making. At each round t\in[T] , a learner chooses an arm A_{t}\in[K] and observes a stochastic reward with mean \mu_{A_{t}} . The goal is to minimize the expected pseudo-regret \mathbb{E}[\mathrm{Reg}_{T}]:=\mathbb{E}\!\left[\sum_{t=1}^{T}\bigl(\mu^{\star}-\mu_{A_{t}}\bigr)\right],\qquad\mu^{\star}:=\max_{i\in[K]}\mu_{i}. Classical algorithms such as UCB [ 8 ] and Thompson sampling [ 40 , 3 ] achieve the minimax rate \widetilde{O}(\sqrt{KT}) . These guarantees are typically established in an idealized model that implicitly grants two resources: enough memory to maintain rich per-arm statistics, and full adaptivity, meaning that the learner may update its policy after every observation. In many large-scale experimentation systems such as online advertising and recommendation systems, neither resource is always abundant. When K is large, storing per-arm state in fast memory can be costly. At the same time, feedback is often processed asynchronously in system pipelines, so policy updates occur only periodically rather than after every interaction. From a theoretical perspective, these two limitations correspond to constraints on two canonical computational resources: space and adaptivity. A space constraint limits how many bits of memory a learner can use, while an adaptivity constraint limits how frequently a learner may adapt its interaction with the environment based on past feedback. Understanding how statistical performance depends on these resources, and whether one resource can compensate for the other, is therefore of fundamental interest. In this paper, we study stochastic bandits under simultaneous constraints on both resources. Space constraint. We model the space constraint by restricting the learner to W bits of persistent memory, meaning that the state carried from one round to the next can take at most 2^{W} values. Computation within a round is unrestricted; only the state retained between rounds is limited. This is a natural model of space-constrained computation. In bandit theory, it dates back to the finite-memory bandit formulations of [ 14 , 13 ] , and is also consistent with the modern sublinear-space viewpoint of [ 29 ] . Under the standard word-RAM convention with word size \Theta(\log T) , W=\Theta(\log T) corresponds to O(1) machine words. Adaptivity constraint. We consider the batched bandit model [ 33 , 16 ] , in which the horizon is partitioned into B batches and outcomes are only incorporated between batches. At the beginning of each batch, the learner must commit to the action-generation rule for that batch using only information available at the previous batch boundary. Equivalently, feedback observed within a batch cannot affect later actions in the same batch. Following [ 16 ] , we consider both the static-grid and the adaptive-grid variants. The static grid assumes that the batch boundaries are predetermined and fixed in advance, while the adaptive grid allows the learner to choose the next batch boundary using information available at the previous boundary. Viewed separately, each constraint appears surprisingly mild. Stochastic bandits admit near-optimal algorithms using only O(\log T) bits of memory under fully adaptive interaction [ 13 , 29 ] , while batched bandits attain near-minimax regret with only O(\log\log T) batches when memory is unrestricted [ 33 , 16 , 22 , 15 ] . These positive results rely on the other resource being abundant: space-bounded algorithms exploit frequent updates, whereas few-batch algorithms retain rich statistics across batch boundaries. We consider the joint regime where the learner has a W -bit memory budget and interacts with the environment in B batches. Our results show that this regime is qualitatively different from either constraint in isolation: once the space budget is logarithmic, near-minimax regret is no longer compatible with an O(K^{1-\varepsilon}) number of batches. Theorem 1 (Informal) . For sufficiently large T , any B -batch stochastic bandit algorithm with W bits of persistent memory and near-minimax regret \widetilde{O}(\sqrt{KT}) must satisfy B=\Omega(K/W), even if the batch grid is allowed to be adaptive. A formal version of Theorem 1 is given in Section 4 . At a high level, the lower bound comes from an information bottleneck at batch boundaries. All information gathered within a batch can influence future batches only through the W -bit state retained at the batch boundary. With frequent feedback, a learner can recycle a small amount of memory over time; with abundant memory, it can compensate for few updates by storing accurate per-arm summaries. Under simultaneous constraints, neither mechanism is available. The learner must either explore many arms and retain only a coarse summary, or keep precise information about only a small subset of arms and therefore require many batches before covering all K arms. Our results show that this bottleneck fundamentally reshapes the batch–regret trade-off. We also show that this lower bound is essentially tight. Theorem 2 (Informal) . For every bit budget \Omega(\log T)\leq W\leq O(K\log T) , there exists a stochastic static-grid bandit algorithm using at most W bits of persistent memory and \widetilde{O}(K/W) batches that achieves near-minimax regret \widetilde{O}(\sqrt{KT}) . A formal version

Read the complete text