# Learning and Solving Regular Decision Processes

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2020.

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

- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Efficient PAC Reinforcement Learning in Regular Decision Processes](https://mlsanity.com/paper/2105.06784/) (2021)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [Regular Decision Processes for Grid Worlds](https://mlsanity.com/paper/2111.03647/) (2021)
- [Automata Cascades: Expressivity and Sample Complexity](https://mlsanity.com/paper/2211.14028/) (2022)
- [Integrating Explanations in Learning LTL Specifications from Demonstrations](https://mlsanity.com/paper/2404.02872/) (2024)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Temporal-Causal Inference for Reinforcement Learning via Automata Learning](https://mlsanity.com/paper/2609.07461/) (2026)
- [Exact Distinguishability in Non-Markovian Decision Processes](https://mlsanity.com/paper/2610.01527/) (2026)

## Abstract (arXiv)

Regular Decision Processes (RDPs) are a recently introduced model that extends MDPs with non-Markovian dynamics and rewards. The non-Markovian behavior is restricted to depend on regular properties of the history. These can be specified using regular expressions or formulas in linear dynamic logic over finite traces. Fully specified RDPs can be solved by compiling them into an appropriate MDP. Learning RDPs from data is a challenging problem that has yet to be addressed, on which we focus in this paper. Our approach rests on a new representation for RDPs using Mealy Machines that emit a distribution and an expected reward for each state-action pair. Building on this representation, we combine automata learning techniques with history clustering to learn such a Mealy machine and solve it by adapting MCTS to it. We empirically evaluate this approach, demonstrating its feasibility.