# Constructing Non-Markovian Decision Process via History Aggregator

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 20 references that are in the map.
- First posted on arXiv 30 Jun 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [The Sample-Complexity of General Reinforcement Learning](https://mlsanity.com/paper/1308.4828/) (2013)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Learning Non-Markovian Reward Models in MDPs](https://mlsanity.com/paper/2001.09293/) (2020)
- [Learning and Solving Regular Decision Processes](https://mlsanity.com/paper/2003.01008/) (2020)
- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [Selecting the State-Representation in Reinforcement Learning](https://mlsanity.com/paper/1302.2552/) (2013)
- [Learning non-Markovian Decision-Making from State-only Sequences](https://mlsanity.com/paper/2306.15156/) (2023)
- [Non-Markovian Reinforcement Learning using Fractional Dynamics](https://mlsanity.com/paper/2107.13790/) (2021)

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

- [Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling](https://mlsanity.com/paper/2508.04282/) (2025)

## Abstract (arXiv)

In the domain of algorithmic decision-making, non-Markovian dynamics manifest as a significant impediment, especially for paradigms such as Reinforcement Learning (RL), thereby exerting far-reaching consequences on the advancement and effectiveness of the associated systems. Nevertheless, the existing benchmarks are deficient in comprehensively assessing the capacity of decision algorithms to handle non-Markovian dynamics. To address this deficiency, we have devised a generalized methodology grounded in category theory. Notably, we established the category of Markov Decision Processes (MDP) and the category of non-Markovian Decision Processes (NMDP), and proved the equivalence relationship between them. This theoretical foundation provides a novel perspective for understanding and addressing non-Markovian dynamics. We further introduced non-Markovianity into decision-making problem settings via the History Aggregator for State (HAS). With HAS, we can precisely control the state dependency structure of decision-making problems in the time series. Our analysis demonstrates the effectiveness of our method in representing a broad range of non-Markovian dynamics. This approach facilitates a more rigorous and flexible evaluation of decision algorithms by testing them in problem settings where non-Markovian dynamics are explicitly constructed.