Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environments

Geraud Nangue Tasse, Matthew Riemer, Benjamin Rosman, Tim Klinger · 2025

Read Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environments by Geraud Nangue Tasse, Matthew Riemer, Benjamin Rosman, Tim Klinger (2025) 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-2512-19154.txt.

Introduction

Geraud Nangue Tasse, Matthew Riemer, Benjamin Rosman, and Tim Klinger teach agents to remember only what matters in worlds where the distant past can matter again. The common fix, stacking recent frames, grows costly as the needed history lengthens. Yet most old observations, they note, have no effect on what happens next.

Their meta-algorithms keep a small, adaptive stack of chosen memories instead of a fixed window. The stack can still express deep dependencies on a few key moments. That design cuts the memory and compute burden for both acting and learning. The work targets sequence-model agents being pushed toward messy, real-world tasks.

Catalog record

CREATORGeraud Nangue Tasse, Matthew Riemer, Benjamin Rosman, Tim Klinger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE158 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-19154

Browse the full library · About the Tower of Babel

Full text

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

Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environments Geraud Nangue Tasse, Matthew Riemer, Benjamin Rosman, Tim Klinger Abstract Recent success in developing increasingly general purpose agents based on sequence models has led to increased focus on the problem of deploying computationally limited agents within the vastly more complex real-world. A key challenge experienced in these more realistic domains is highly non-Markovian dependencies with respect to the agent’s observations, which are less common in small controlled domains. The predominant approach for dealing with this in the literature is to stack together a window of the most recent observations ( Frame Stacking ), but this window size must grow with the degree of non-Markovian dependencies, which results in prohibitive computational and memory requirements for both action inference and learning. In this paper, we are motivated by the insight that in many environments that are highly non-Markovian with respect to time, the environment only causally depends on a relatively small number of observations over that time-scale. A natural direction would then be to consider meta-algorithms that maintain relatively small adaptive stacks of memories such that it is possible to express highly non-Markovian dependencies with respect to time while considering fewer observations at each step and thus experience substantial savings in both compute and memory requirements. Hence, we propose a meta-algorithm ( Adaptive Stacking ) for achieving exactly that with convergence guarantees and quantify the reduced computation and memory constraints for MLP, LSTM, and Transformer-based agents. Our experiments utilize popular memory tasks, which give us control over the degree of non-Markovian dependencies. This allows us to demonstrate that an appropriate meta-algorithm can learn the removal of memories not predictive of future rewards without excessive removal of important experiences. Code: https://github.com/geraudnt/adaptive-stacking Figure 1: Learning what to remember using Adaptive Stacking. (left) Modification to the standard RL loop. (right) PPO trained for 10 6 10^{6} timesteps in a Passive-TMaze of length 16 16 and tested on length 10 6 10^{6} . The episode lengths are equal to the maze lengths ( L + 2 L+2 ). FS needs a stack size (context window) of k ∗ = 16 k^{*}=16 , which not only requires oracle knowledge of the environment, but also scales with the maze length. In contrast, only κ = 2 \kappa=2 is needed irrespective of maze length and architecture. 1 Introduction Reinforcement learning (RL) agents are typically formulated under the Markov assumption: the agent’s current observation contains all information needed for optimal decision-making ( Puterman 2014 ) . In practice, however, real-world environments are often partially observable – the agent’s immediate observation is an incomplete snapshot of the true state. This leads to non-Markovian dependencies over time, where past observations contain critical context for future decisions. Notably, Abel et al. 2021 proved that there exist certain tasks (for example expressed as desired behaviour specifications) that cannot be captured by any Markovian reward function. In other words, no memoryless reward can incentivise the correct behaviour for those tasks and agents must rely on histories of observations to infer hidden state information to resolve non-Markovian dependencies. This theoretical insight underlines that non-Markovian tasks are not just harder, but sometimes fundamentally require memory beyond the scope of standard Markov formulations. We are interested in such settings in big worlds ( Javed & Sutton 2024 ) , where only a relatively small subset of past observations are relevant for optimal decision-making, but they are separated by large spans of time. While RL has shown great success in a variety domains ( Arulkumaran et al. 2017 ; Cao et al. 2024 ) , handling such temporal dependencies remains a challenge especially for computationally limited agents operating in big worlds ( Javed & Sutton 2024 ) . In practice, the most common approach to address this problem is Frame Stacking (FS), which is a FIFO short-term memory wherein a fixed context window of the most recent k^{*} observations (and actions) are concatenated. This is then used directly as policy input, or first used to infer hidden states typically using active inference ( Friston 2009 ; Sajid et al. 2021 ) or sequence models like recurrent neural networks ( Hochreiter & Schmidhuber 1997 ; Hausknecht & Stone 2015 ) , Transformers ( Vaswani et al. 2017 ; Chen et al. 2021 ) , and state space models ( Gu et al. 2021 ; Samsami et al. 2024 ) . Given knowledge of the nature of the temporal dependencies, for example when they are expressible as reward machines ( Icarte et al. 2022 ; Bester et al. 2023 ) , prior works also use such histories of observations and program synthesis to learn abstract state machines that compactly represent the memory and temporal dependencies ( Toro Icarte et al. 2019 ; Hasanbeig et al. 2024 ) . While such approaches based on FS are very effective in domains with short-term dependencies, such as in Atari games ( Mnih et al. 2013 ) where 4 frames are enough to capture the motion of objects, they quickly become impractical in domains where relevant information may have occurred in an unknown large number of steps ( Ni et al. 2023 ) . Importantly, increasing k^{*} causes an exponential increase in the dimensionality of the observation space, leading to both a severe increase in compute and storage, and potentially poor sample efficiency and generalisation. However, many tasks may not actually require remembering everything. Often only a sparse subset of past observations is truly relevant for making optimal decisions. This insight aligns with findings in cognitive neuroscience: working memory in humans is known to have limited capacity and is thought to employ a selective gating mechanism that retains task-relevant information while filtering out irrelevant inputs ( Unger et al. 2016 ) . For example, a driver listening to a traffic report will update only the few road incidents relevant to her route into memory and ignore other trivial reports. Similarly, an RL agent with constrained memory should learn what to remember and what to forget. If the agent can identify which observations carry information critical for future reward, it could store just those and safely discard others, drastically reducing the burden on its memory and computation. Ideally, this is possible without sacrificing performance, but instead while actually improving generalisation. Driven by this insight, we make the following main contributions: 1. Adaptive Stacking : We propose Adaptive Stacking (AS), a general meta-algorithm that learns to selectively retain observations in a working memory of fixed size \kappa (Figure 1 ). When \kappa\ll k^{*} , this significantly improves compute and memory efficiency. It also leads to an exponential reduction in the size of the search space, which has implications for sample efficiency and generalisation. 2. Theoretical analysis : We then prove that agents using this approach are guaranteed to converge to an optimal policy in general when using unbiased value estimates, and in particular when using TD-learning under general assumptions. This enables practical trade-offs under the same resource constraints, such as the use of smaller memory to enable larger policy networks and the use of partial, instead of full, observations for better generalisation. 3. Empirical analysis : We run comprehensive experiments on memory intensive tasks using standard algorithms

Read the complete text