---
title: "Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes"
authors:
  - "Alessandro Trapasso"
  - "Luca Iocchi"
  - "Fabio Patrizi"
doi: "10.24963/ijcai.2026/546"
url: "https://ijcai.org/proceedings/2026/546"
pdf: "https://ijcai.org/proceedings/2026/0546.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "4903-4911"
track: "Main Track"
keywords:
  - "Machine Learning: Model-based and model learning reinforcement learning"
  - "Machine Learning: Reinforcement learning"
  - "Machine Learning: Learning theory"
---

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

Alessandro Trapasso, Luca Iocchi, Fabio Patrizi

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 4903-4911. DOI: [10.24963/ijcai.2026/546](https://doi.org/10.24963/ijcai.2026/546)

## Abstract

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) can be inadequate for such tasks, while modeling them as non-Markovian reward decision processes (NMRDPs) enables agents to handle temporal dependencies.
Existing approaches offer limited formal guarantees on both (near-)optimality and sample efficiency. We address both issues with QR-max, a novel model-based algorithm for NMRDPs with discrete actions that factorizes Markovian transition learning from non-Markovian reward handling via reward machines. To our knowledge, this is the first model-based RL algorithm for discrete-action NMRDPs that leverages this factorization to obtain PAC convergence to ε-optimal policies with polynomial sample complexity.
We then extend QR-max to continuous state spaces with Bucket-QR-max, a SimHash-based discretizer that preserves the same factorized structure and achieves fast and stable learning without manual gridding or function approximation. We experimentally compare our method with state-of-the-art model-based RL approaches on environments of increasing complexity, showing substantially improved sample efficiency and greater robustness in finding optimal policies.