mlsanityData to 14 Oct 2026

Constructing Non-Markovian Decision Process via History Aggregator

arXiv 2506.24026 ↗First posted 30 Jun 2025cs.AIcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

Key facts. Cited by 1 paper 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.

Builds on

10 of 20 references.

References · 10

  1. 2019Reinforcement Learning with Non-Markovian Rewardscited by 45
  2. 2013The Sample-Complexity of General Reinforcement Learningcited by 18
  3. 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
  4. 2020Learning Non-Markovian Reward Models in MDPscited by 11
  5. 2020Learning and Solving Regular Decision Processescited by 11
  6. 2022Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processescited by 10
  7. 2022Reinforcement Learning in Non-Markovian Environmentscited by 10
  8. 2013Selecting the State-Representation in Reinforcement Learningcited by 6
  9. 2023Learning non-Markovian Decision-Making from State-only Sequencescited by 6
  10. 2021Non-Markovian Reinforcement Learning using Fractional Dynamicscited by 5

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modelingcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
  2. 2025Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning
  3. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet
  4. 2024Tackling Decision Processes with Non-Cumulative Objectives using Reinforcement Learning
  5. 2025Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis
  6. 2026Learning in Markov Decision Processes with Exogenous Dynamics
  7. 2024Harnessing Causality in Reinforcement Learning With Bagged Decision Times
  8. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes