Fundamental Limits of Memory Constrained Online Learning

70 concepts37 papers1 proposal

In classical online learning, algorithms are typically granted an implicit luxury: unlimited or linear memory. Whether tracking the performance of $N$ experts or maintaining historical statistics for $K$ arms in a multi-armed bandit (MAB) problem, standard paradigms assume the learner can store state information for every available option. Under these unconstrained conditions, we can achieve optimal, slowly growing regret (often logarithmic $\mathcal{O}(\log T)$ for stochastic bandits).

However, when deploying algorithms in large-scale streaming environments, edge devices, or privacy-restricted domains, this assumption collapses. What happens when memory is strictly bounded? A growing body of research reveals that memory constraints do not merely cause a graceful degradation in performance. Instead, they introduce sharp phase transitions and fundamental lower bounds, fundamentally altering the complexity of the learning task.

The Streaming Bottleneck and Sharp Phase Transitions

Consider a single-pass streaming multi-armed bandit problem where $N$ arms arrive sequentially, but the learner's memory can only hold statistics for $M < N$ arms at a time. If an arm is discarded from memory, it cannot be revisited.

As shown by Arnab Maiti et al. in Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization, dropping memory even a single slot below the total number of arms ($M = N-1$) causes a catastrophic jump in cumulative regret. Instead of the standard logarithmic regret, the system is forced into a square-root regret regime ($\mathcal{O}(\sqrt{T})$ or $\mathcal{O}(T^{2/3})$).

Why does this happen? In a standard MAB algorithm, the learner maintains a global view, allowing it to continuously refine its confidence intervals for all options. In a streaming setting with $M < N$, the learner must make irreversible decisions to evict arms to free up slots. Yuchen He et al. demonstrate in Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits that the difficulty of the problem is governed by the precise gap between the total candidate pool and available memory slots ($N - M$).

When memory is highly constrained, the inability to compare a current candidate with previously discarded options forces a linear or high sublinear regret unless specific phased exploration strategies are used. For instance, Arghya Roy Chaudhuri et al. in Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory prove that a minimum capacity of $M \ge 2$ arms is required to avoid trivial linear regret, as an agent needs at least one slot to hold the current "champion" and another to sample incoming challengers. Furthermore, Chihao Zhang et al. in Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits map this non-smooth phase transition, showing that the regret scales inversely with the available memory slots relative to the sum of the inverse reward gaps of the arms.

The Adversarial Barrier: Sublinear Space vs. Adaptive Opponents

The memory-regret trade-off becomes even harsher when moving from stochastic environments to adversarial ones. In the classic "prediction with expert advice" problem, we want to minimize regret against an adversary.

If the adversary is oblivious (choosing losses beforehand), Binghui Peng et al. show in Online Prediction in Sub-linear Space that it is possible to break the memory barrier and achieve sublinear regret with sublinear space. However, if the adversary is adaptive (changing its strategy based on the learner's past actions), the landscape shifts completely.

In Near Optimal Memory-Regret Tradeoff for Online Learning, Binghui Peng et al. establish a critical memory threshold at approximately $\sqrt{N}$, where $N$ is the number of experts. If the learner's memory capacity falls below $\sqrt{N}$, an adaptive adversary can exploit this information gap to hide optimal strategies or punish the learner's history, forcing linear regret. This means vanishing regret becomes mathematically impossible.

This dynamic highlights a fundamental duality: an adversary with even a small memory window can simulate bandit-like information constraints for a full-information learner, as observed by Nicolò Cesa-Bianchi et al. in Online Learning with Switching Costs and Other Adaptive Adversaries. Conversely, when the adversary's memory is bounded to a finite window, the learner can recover sublinear policy regret using mini-batching techniques to neutralize the adversary's historical influence, a mechanism detailed by Ambuj Tewari et al. in Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret and extended to delayed feedback settings by Zongqi Wan et al. in Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback.

Bounded Recall and Sliding Windows

Another facet of this research direction examines constraints on temporal history, known as bounded recall. Here, the learner can only base its current decision on a fixed window of the most recent $M$ rounds.

Jon Schneider et al. in Online Learning with Bounded Recall demonstrate that the optimal per-round regret in bounded-recall settings scales with the ratio of the action space complexity to the memory window size. Restricting the learner to a rigid historical window introduces a permanent mathematical penalty. For instance, in selective learning tasks, Gregory Valiant et al. show in Exponential Weights Algorithms for Selective Learning that bounded-recall strategies degrade the achievable error rate from a double-logarithmic dependence on the model class size to a much worse square-root logarithmic dependence.

This boundary is also visible in sliding-window streaming environments. As explored by Vladimir Braverman et al. in Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits, if the available memory is even slightly smaller than the active sliding window size, a sharp phase transition occurs where cumulative regret shifts from sublinear to strictly linear growth over time.

The Space-Adaptivity Trade-off

Can we compensate for low memory by changing how frequently we update our strategies? This question uncovers a "no-free-lunch" theorem between space and adaptivity.

In Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits, Ruiyuan Huang et al. prove that a learner cannot simultaneously optimize both memory footprint and interaction frequency. If an algorithm is restricted to logarithmic memory relative to the time horizon, it is mathematically forced to update its strategy across a number of discrete batches that scales linearly with the number of arms ($\Omega(K/W)$ batches for $W$ bits of memory). To maintain near-optimal regret, a memory-starved agent must interact with its environment far more frequently, trading temporal adaptivity for spatial constraints.

Summary of Intuition

Ultimately, this research direction reframes memory not as a mere hardware variable, but as a fundamental information-theoretic currency in online optimization. Whether dealing with streaming candidates, sliding windows, or reactive adversaries, restricting memory cuts off the historical context required to build tight confidence bounds or uncover hidden adversarial patterns. The resulting phase transitions show that below critical storage thresholds, learning algorithms undergo a fundamental shift in complexity, transforming tractable sublinear regret problems into highly penalized or entirely unlearnable regimes.

Key Foundational Work

Online Learning with Switching Costs and Other Adaptive Adversaries (2013) — contributed 2 concept elements to this direction.
Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_memory_regret_phase_transition_44594fd6,
  title = {memory-regret phase transition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-regret-phase-transition/rdr_44594fd69e94497981577e54dfb98e02},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_memory_regret_phase_transition_44594fd6_v1,
  title = {memory-regret phase transition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-regret-phase-transition/rdr_44594fd69e94497981577e54dfb98e02/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake