Online Learning with Limited Memory and Bounded Recall

This direction is merged into another direction: memory-regret phase transition. Its last version stays readable and citable here.

Version 1 of 115 papers21 conceptsfrozen 2026-10-04

In the classical formulation of online learning, an agent makes a sequence of decisions, observes outcomes, and updates its internal state to minimize "regret"—the gap between its performance and that of the best possible fixed strategy. Traditionally, we assume the agent has enough memory to store the entire history of actions or at least a comprehensive set of statistics for every available option.

However, real-world systems—from high-speed network routers to privacy-preserving recommendation engines—operate under strict memory constraints. Recent research has converged on a fundamental question: How much can an agent forget while still learning effectively?

The Space Regret Frontier

The most direct constraint is physical memory. In a multi-armed bandit (MAB) problem with $K$ arms, standard algorithms like UCB require $O(K)$ space to track the performance of every arm. When $K$ is massive, this becomes a bottleneck.

David Liau, Eric Price, and Zhao Song demonstrated in Stochastic Multi-armed Bandits in Constant Space that this linear dependency is not strictly necessary. They introduced UCBConstSpace, which achieves sublinear regret using only $O(1)$ words of memory. This suggests that we don't need to remember the performance of every arm simultaneously; we only need enough memory to compare a small subset of "contender" arms at any given time.

This relationship is not free. David Woodruff and Samson Zhou show in Streaming Algorithms for Learning with Experts: Deterministic Versus Robust that memory and regret exist on a smooth trade-off curve. If you want lower regret, you must pay with more memory. In continuous spaces, such as Lipschitz bandits, Xiaoyi Zhu and Zengfeng Huang found that the absolute theoretical minimum memory required to maintain optimal performance is $O(\log T)$ bits, as detailed in Lipschitz Bandits in Optimal Space.

Forgetting by Design

Sometimes, memory is limited not by hardware, but by the nature of the task. In bounded recall or sliding-window settings, the learner is forced to ignore old data, either because the environment is changing or because of data retention policies.

Jon Schneider and Kiran Vodrahalli explored this in Online Learning with Bounded Recall, showing that the optimal regret in these settings is fundamentally tied to the ratio between the complexity of the action space and the size of the "memory window" $M$.

A critical discovery in this area is the phase transition in regret. Vladimir Braverman and Samson Zhou argue in Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits that if the available memory is even slightly smaller than the required window size, the learner's performance collapses, leading to linear regret. Learning is only possible when memory crosses a specific threshold relative to the window of relevant data.

When the Environment Remembers

The problem becomes even more complex when the environment has memory. In many real-world scenarios, the reward for an action depends on what the agent did in the past—think of a user becoming bored with repeated recommendations.

In Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality, Dhruv Malik, Yuanzhi Li, and Aarti Singh identify a "hard" limit: it is theoretically impossible to achieve sublinear regret in history-dependent environments unless the learner knows an upper bound on the environment's memory window. Without knowing how far back the influence of an action stretches, an algorithm cannot distinguish between a temporary fluctuation and a long-term trend.

Stability through Laziness

If memory is scarce, standard algorithms like Multiplicative Weights often fail because they are too "jittery"—small updates to weights require high-precision storage.

To solve this, Robi Bhattacharjee and Gaurav Mahajan propose a strategy of "laziness" in Learning what to remember. Their Lazy Weights algorithm updates expert weights infrequently. By only changing the internal state when absolutely necessary, the learner maintains stability despite having a very small "sketch" of the past. This infrequent updating acts as a form of compression, allowing the learner to focus its limited memory on the most significant shifts in the environment.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_online_learning_with_limited_memory_and__b7cf86c3,
  title = {Online Learning with Limited Memory and Bounded Recall},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-with-limited-memory-and-bounded-recall/rdr_b7cf86c37dfb403c99c3da877a63aa23},
  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_online_learning_with_limited_memory_and__b7cf86c3_v1,
  title = {Online Learning with Limited Memory and Bounded Recall},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-with-limited-memory-and-bounded-recall/rdr_b7cf86c37dfb403c99c3da877a63aa23/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}