Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environments
Not on the map. Why?
Abstract (arXiv)
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
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 82 of its 121 references that are in the map. First posted on arXiv 22 Dec 2025.
Builds on
82 of 121 references.
References · 82
- 2017Attention Is All You Needcited by 59,932
- 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
- 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,383
- 2020Longformer: The Long-Document Transformercited by 3,362
- 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
- 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
- 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
- 2019Generating Long Sequences with Sparse Transformerscited by 1,523
- 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,270
- 2018Recurrent World Models Facilitate Policy Evolutioncited by 761
- 2019Compressive Transformers for Long-Range Sequence Modellingcited by 699
- 2014Neural Turing Machinescited by 630
38 more
- 2021Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LMcited by 621
- 2018Learning to Learn without Forgetting by Maximizing Transfer and Minimizing Interferencecited by 511
- 2017A Brief Survey of Deep Reinforcement Learningcited by 466
- 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 457
- 2016The Option-Critic Architecturecited by 433
- 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 424
- 2014Memory Networkscited by 354
- 2024Hallucination is Inevitable: An Innate Limitation of Large Language Modelscited by 329
- 2024The Power of Noise: Redefining Retrieval for RAG Systemscited by 275
- 2020Towards Continual Reinforcement Learning: A Review and Perspectivescited by 268
- 2019Stabilizing Transformers for Reinforcement Learningcited by 262
- 2018Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Researchcited by 256
- 2017Learning with Opponent-Learning Awarenesscited by 218
- 2024BABILong: Testing the Limits of LLMs with Long Context Reasoning-in-a-Haystackcited by 211
- 2024Leave No Context Behind: Efficient Infinite Context Transformers with Infini-attentioncited by 194
- 2023In-context Autoencoder for Context Compression in a Large Language Modelcited by 190
- 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 183
- 2019Behaviour Suite for Reinforcement Learningcited by 129
- 2017Routing Networks: Adaptive Selection of Non-linear Functions for Multi-Task Learningcited by 125
- 2024Retrieval Augmented Generation or Long-Context LLMs? A Comprehensive Study and Hybrid Approachcited by 117
- 2021Recurrent Model-Free RL Can Be a Strong Baseline for Many POMDPscited by 115
- 2024Survey on Large Language Model-Enhanced Reinforcement Learning: Concept, Taxonomy, and Methodscited by 114
- 2023Structured State Space Models for In-Context Reinforcement Learningcited by 109
- 2023Attention Sorting Combats Recency Bias In Long Context Language Modelscited by 89
- 2021LTL2Action: Generalizing LTL Instructions for Multi-Task RLcited by 72
- 2021On the Expressivity of Markov Rewardcited by 71
- 2023When Do Transformers Shine in RL? Decoupling Memory from Credit Assignmentcited by 62
- 2024Eliminating Position Bias of Language Models: A Mechanistic Approachcited by 61
- 2023POPGym: Benchmarking Partially Observable Reinforcement Learningcited by 59
- 2018Optimizing Agent Behavior over Long Time Scales by Transporting Valuecited by 57
- 2020Learning Associative Inference Using Fast Weight Memorycited by 51
- 2019Routing Networks and the Challenges of Modular and Compositional Computationcited by 49
- 2019Metalearned Neural Memorycited by 44
- 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
- 2022Evaluating Long-Term Memory in 3D Mazescited by 41
- 2020A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learningcited by 40
- 2021Towards mental time travel: a hierarchical memory for reinforcement learning agentscited by 38
- 2024Mastering Memory Tasks with World Modelscited by 38
50 most cited of 82 All 82 (JSON)
Built on by
Citing papers per year: 2026: 3.
3 papers.