# Efficient PAC Reinforcement Learning in Regular Decision Processes

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 41 references that are in the map.
- First posted on arXiv 14 May 2021.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Learning and Solving Regular Decision Processes](https://mlsanity.com/paper/2003.01008/) (2020)

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

- [Computably Continuous Reinforcement-Learning Objectives are PAC-learnable](https://mlsanity.com/paper/2303.05518/) (2023)
- [Reinforcement Learning with History-Dependent Dynamic Contexts](https://mlsanity.com/paper/2302.02061/) (2023)
- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes](https://mlsanity.com/paper/2607.27132/) (2026)
- [Automata Cascades: Expressivity and Sample Complexity](https://mlsanity.com/paper/2211.14028/) (2022)
- [Reinforcement Causal Structure Learning on Order Graph](https://mlsanity.com/paper/2211.12151/) (2022)

## Abstract (arXiv)

Recently regular decision processes have been proposed as a well-behaved form of non-Markov decision process. Regular decision processes are characterised by a transition function and a reward function that depend on the whole history, though regularly (as in regular languages). In practice both the transition and the reward functions can be seen as finite transducers. We study reinforcement learning in regular decision processes. Our main contribution is to show that a near-optimal policy can be PAC-learned in polynomial time in a set of parameters that describe the underlying decision process. We argue that the identified set of parameters is minimal and it reasonably captures the difficulty of a regular decision process.