Ruiyuan Huang, Zicheng Lyu, Xiaoyi Zhu, Zengfeng Huang
9 min
Abstract
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 $\widetilde{O}(\sqrt{KT})$ is achievable with $O(\log T)$ bits of memory under fully adaptive interaction, and with a $K$-independent $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$-bit memory constraint must use at least $Ω(K/W)$ batches to achieve near-minimax regret $\widetilde{O}(\sqrt{KT})$, even under adaptive grids. In particular, logarithmic memory rules out $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)$ 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 $Ω(\log T) \le W \le O(K\log T)$, uses at most $W$ bits of memory and $\widetilde{O}(K/W)$ batches while achieving regret $\widetilde{O}(\sqrt{KT})$, nearly matching our lower bound up to polylogarithmic factors.
Sam: The proof hinges on tracking how often each arm gets pulled. They define a simple summary: for each arm, mark it as "explored" if it's sampled about its fair share of times—roughly even across all arms to learn everything. This marker, called the thresholded profile Y, acts like a rough sketch of which arms you checked deeply enough. Low regret forces Y to reveal a lot about which arms are actually good, carrying at least on the order of K bits of key info.
Alex: Okay, so Y flags arms you poked enough times. But why does regret make sure it catches the good ones reliably?
Sam: Bad arms rarely hit that threshold because sampling them a lot already costs regret—you're wasting turns on losers. For good arms, it's trickier: imagine tweaking just one good arm to be the absolute best in a nearby scenario; if you ignore it in the original, you'd rack up huge regret there. To avoid that across all possible worlds, each good arm must cross the threshold with steady probability. They use a smart probability trick, comparing only the first bunch of pulls on that arm, to show this holds without extra costs.
Alex: Huh. So Y ends up as a noisy but informative map of the good arms... like a blurry photo that still identifies the suspects.
Sam: Precisely. That turns Y into something that predicts good-arm status better than a coin flip, forcing at least Ω(K) bits of mutual information about the hidden good set. But in batched setups, Y depends only on the seed and the memory states at batch ends—each carrying W bits max. With B batches, that's at most O(B W) bits total flowing across boundaries, so you need B at least Ω(K over W) to carry the info.
Alex: Right—like a narrow pipe needing many trips to shift a big load of dirt. But how do batches and tiny memory cap the info in that profile Y at just B times W bits?
Sam: Under batching, once a batch starts, the plan for pulls inside it is locked in—using only the clock, the seed randomness, and the memory from the prior batch end. Rewards seen mid-batch can't change later pulls in that batch, so they only influence future via the next memory state, which holds W bits max. The full pull counts—and thus Y—end up fixed by the seed plus the sequence of those boundary memories across B batches.
Alex: So Y doesn't see inside-batch feedback directly... it's just pieced from what crosses those narrow memory gates between batches.
Sam: Right. That makes a chain: the true arm qualities affect the memories, which then set Y. A data-processing rule says info about arm qualities can't increase along that chain, so mutual info between them and Y is at most the uncertainty in the memories given the seed. And the memories' total uncertainty is at most B times W bits.
Alex: Ah—so even if Y needs a lot of bits on good arms for low regret, the pipeline squeezes it to B W bits total. Forces B at least Ω(K over W).
Sam: Exactly. The proof wraps there: low regret demands that much info flow, but structure caps it, proving the bound even for adaptive batch sizes that shift based on memories.
Alex: And logarithmic W—like log T bits for counters—means nearly K over log T batches, no dodging it. So that matching algorithm you mentioned—scanning in blocks and testing challengers—how does it actually fit the memory limit without more batches?
Sam: It divides the K arms into groups of size S, like sorting a big pile of cards into small stacks. For each stack, it runs tests where new arms compete against the current best one so far, using multiple rounds of pulls to decide if a challenger pulls ahead reliably. If one wins, it becomes the new benchmark for the next stacks; otherwise, discard the stack. This "block elimination" keeps memory to about S times log T bits—pick S around W over log T to stay under budget—and needs roughly K over S batches to cover everything.
Alex: Okay, so smaller stacks mean more batches but fit tiny memory... but is this planning batches ahead or adjusting on the fly?
Sam: Their matching algorithm uses a fixed schedule upfront, a simpler static grid, yet still hits about K over W batches for near-optimal regret. This shows the tradeoff is tight: no clever adaptivity sneaks around the barrier when memory is logarithmic, like just a few dozen bits. The lower bound holds even for the flexible adaptive case.
Alex: Right, logarithmic meaning growing slowly with problem size, not enough to track everything. But in ads with millions of creatives, daily batches, and tight memory for fast serving—does this mean we can't get close to best without hundreds of days?
Sam: Yes, the joint squeeze of small persistent memory—those W bits carried strictly between batches—and few batches creates a stricter limit than either alone. Log memory forces nearly linear-in-K/W batches to compensate, preventing the near-minimax regret you can get separately. For ads, it highlights why storing full stats per creative isn't feasible; you need either more memory or way more batches to identify winners reliably.
Alex: Huh... so no shortcut when both resources are scarce. That's a meaningful constraint for real systems. Right, so the lower bound covers the flexible adaptive case, upper bound the simpler static one—pretty aligned. But are there any caveats in the results?
Sam: Yes, a few. The matching leaves a polylogarithmic gap between bounds, so tightening that remains open. It focuses on the large horizon regime where T is huge, and the lower bound applies specifically to Bernoulli rewards, though the intuition likely extends. Still, the core message stands: persistent memory of W bits between batches creates an information bottleneck that low regret must overcome.
Alex: Huh... so in practice, for systems like ad testing with millions of creatives, daily batches, and tight memory, you either expand storage or accept more days to find winners reliably.
Sam: Exactly. This memory-adaptivity tradeoff reshapes thinking in contextual bandits, streaming data, and reinforcement learning with asynchronous feedback—highlighting that info retention across updates is as crucial as gathering it.
Alex: That's a grounded insight—no substitutes when both resources pinch. Makes real-world designs more thoughtful. Thanks for joining this discussion on ResearchPod.