# Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 29 Apr 2022.

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

- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [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)
- [Learning and Solving Regular Decision Processes](https://mlsanity.com/paper/2003.01008/) (2020)
- [Efficient PAC Reinforcement Learning in Regular Decision Processes](https://mlsanity.com/paper/2105.06784/) (2021)
- [Selecting the State-Representation in Reinforcement Learning](https://mlsanity.com/paper/1302.2552/) (2013)

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

- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Neural Reward Machines](https://mlsanity.com/paper/2408.08677/) (2024)
- [Learning non-Markovian Decision-Making from State-only Sequences](https://mlsanity.com/paper/2306.15156/) (2023)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [Multi-Agent Reinforcement Learning in Intelligent Transportation Systems: A Comprehensive Survey](https://mlsanity.com/paper/2508.20315/) (2025)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Fully Learnable Neural Reward Machines](https://mlsanity.com/paper/2509.19017/) (2025)
- [Toward Learning POMDPs Beyond Full-Rank Actions and State Observability](https://mlsanity.com/paper/2601.18930/) (2026)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Exact Distinguishability in Non-Markovian Decision Processes](https://mlsanity.com/paper/2610.01527/) (2026)

## Abstract (arXiv)

Our work aims at developing reinforcement learning algorithms that do not rely on the Markov assumption. We consider the class of Non-Markov Decision Processes where histories can be abstracted into a finite set of states while preserving the dynamics. We call it a Markov abstraction since it induces a Markov Decision Process over a set of states that encode the non-Markov dynamics. This phenomenon underlies the recently introduced Regular Decision Processes (as well as POMDPs where only a finite number of belief states is reachable). In all such kinds of decision process, an agent that uses a Markov abstraction can rely on the Markov property to achieve optimal behaviour. We show that Markov abstractions can be learned during reinforcement learning. Our approach combines automata learning and classic reinforcement learning. For these two tasks, standard algorithms can be employed. We show that our approach has PAC guarantees when the employed algorithms have PAC guarantees, and we also provide an experimental evaluation.