# Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes

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

## 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 13 of its 34 references that are in the map.
- First posted on arXiv 16 Dec 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, 13 of 13)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [Reward Machines for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2007.01962/) (2020)
- [Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guarantees](https://mlsanity.com/paper/2305.01381/) (2023)
- [Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees](https://mlsanity.com/paper/2209.14414/) (2022)
- [Reinforcement Learning with Stochastic Reward Machines](https://mlsanity.com/paper/2510.14837/) (2025)
- [Non-Markovian Reinforcement Learning using Fractional Dynamics](https://mlsanity.com/paper/2107.13790/) (2021)
- [Efficient Reinforcement Learning in Probabilistic Reward Machines](https://mlsanity.com/paper/2408.10381/) (2024)
- [Provably Efficient Exploration in Reward Machines with Low Regret](https://mlsanity.com/paper/2412.19194/) (2024)

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

- [Theoretical Foundations of max@k Reinforcement Learning](https://mlsanity.com/paper/2607.17823/) (2026)

## Abstract (arXiv)

Many practical decision-making problems involve tasks whose success depends on the entire system history, rather than on achieving a state with desired properties. Markovian Reinforcement Learning (RL) approaches are not suitable for such tasks, while RL with non-Markovian reward decision processes (NMRDPs) enables agents to tackle temporal-dependency tasks. This approach has long been known to lack formal guarantees on both (near-)optimality and sample efficiency. We contribute to solving both issues with QR-MAX, a novel model-based algorithm for discrete NMRDPs that factorizes Markovian transition learning from non-Markovian reward handling via reward machines. To the best of our knowledge, this is the first model-based RL algorithm for discrete-action NMRDPs that exploits this factorization to obtain PAC convergence to varepsilon-optimal policies with polynomial sample complexity. We then extend QR-MAX to continuous state spaces with Bucket-QR-MAX, a SimHash-based discretiser that preserves the same factorized structure and achieves fast and stable learning without manual gridding or function approximation. We experimentally compare our method with modern state-of-the-art model-based RL approaches on environments of increasing complexity, showing a significant improvement in sample efficiency and increased robustness in finding optimal policies.