mlsanityData to 14 Oct 2026

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

arXiv 2512.14617 ↗First posted 16 Dec 2025cs.LG cs.AIcited by 1

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

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.

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

Builds on

13 of 34 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Provably Efficient Exploration in Reward Machines with Low Regret26 Dec
  2. 2024Efficient Reinforcement Learning in Probabilistic Reward Machines19 Aug

Other references · 11

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2016The Option-Critic Architecturecited by 448
  3. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  4. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  5. 2019Reinforcement Learning with Non-Markovian Rewardscited by 45
  6. 2014Near-optimal Reinforcement Learning in Factored MDPscited by 41
  7. 2020Reward Machines for Cooperative Multi-Agent Reinforcement Learningcited by 35
  8. 2023Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guaranteescited by 18
  9. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  10. 2025Reinforcement Learning with Stochastic Reward Machinescited by 7
  11. 2021Non-Markovian Reinforcement Learning using Fractional Dynamicscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Theoretical Foundations of max@k Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning
  2. 2026Optimal Multi-Reward Reinforcement Learning
  3. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
  4. 2024Constrained Reinforcement Learning with Average Reward Objective: Model-Based and Model-Free Algorithms
  5. 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
  6. 2026Q-Learning for Reachability in MEC-Free MDPs
  7. 2020Learning Non-Markovian Reward Models in MDPs
  8. 2024On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks