# Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling

arXiv: https://arxiv.org/abs/2508.04282 · HTML: https://mlsanity.com/paper/2508.04282/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 36 references that are in the map.
- First posted on arXiv 6 Aug 2025.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 17 of 17)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [Benchmarking the Spectrum of Agent Capabilities](https://mlsanity.com/paper/2109.06780/) (2021)
- [The NetHack Learning Environment](https://mlsanity.com/paper/2006.13760/) (2020)
- [RUDDER: Return Decomposition for Delayed Rewards](https://mlsanity.com/paper/1806.07857/) (2018)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [Variational Recurrent Models for Solving Partially Observable Control Tasks](https://mlsanity.com/paper/1912.10703/) (2019)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Acting in Delayed Environments with Non-Stationary Markov Policies](https://mlsanity.com/paper/2101.11992/) (2021)
- [Off-Policy Reinforcement Learning with Delayed Rewards](https://mlsanity.com/paper/2106.11854/) (2021)
- [Learning Non-Markovian Reward Models in MDPs](https://mlsanity.com/paper/2001.09293/) (2020)
- [Benchmarking Partial Observability in Reinforcement Learning with a Suite of Memory-Improvable Domains](https://mlsanity.com/paper/2508.00046/) (2025)
- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (2024)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)

## Built on by (most cited first, 1 of 1)

- [ELMUR: External Layer Memory with Update/Rewrite for Long-Horizon RL Problems](https://mlsanity.com/paper/2510.07151/) (2025)

## Abstract (arXiv)

Recent benchmarks for memory-augmented reinforcement learning (RL) have introduced partially observable Markov decision process (POMDP) environments in which agents must use historical observations to make decisions. However, these benchmarks often lack fine-grained control over the challenges posed to memory models. Synthetic environments offer a solution, enabling precise manipulation of environment dynamics for rigorous and interpretable evaluation of memory-augmented RL. This paper advances the design of such customizable POMDPs with three key contributions: (1) a theoretical framework for analyzing POMDPs based on Memory Demand Structure (MDS) and related concepts; (2) a methodology using linear dynamics, state aggregation, and reward redistribution to construct POMDPs with predefined MDS; and (3) a suite of lightweight, scalable POMDP environments with tunable difficulty, grounded in our theoretical insights. Overall, our work clarifies core challenges in partially observable RL, offers principled guidelines for POMDP design, and aids in selecting and developing suitable memory architectures for RL tasks.