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

Researchers introduce QR-MAX, a model-based reinforcement learning algorithm designed for non-Markovian reward decision processes that depend on complete system history rather than current state alone. The algorithm provides formal PAC convergence guarantees with polynomial sample complexity, advancing a previously under-theorized area of RL with practical applications to temporal-dependency tasks.

QR-MAX addresses a fundamental limitation in reinforcement learning: most practical RL algorithms assume Markovian properties where optimal decisions depend only on current state, but many real-world problems require agents to consider full historical context. The research factorizes learning into two components—Markovian transition dynamics and non-Markovian reward handling via reward machines—enabling theoretical guarantees previously unavailable for this problem class.

The advancement fills a gap between theoretical rigor and practical applicability. Prior non-Markovian RL approaches lacked formal optimality or sample efficiency guarantees, limiting their adoption in safety-critical domains. QR-MAX achieves PAC convergence to epsilon-optimal policies with polynomial sample complexity, providing both theoretical justification and computational efficiency. The extension to continuous state spaces through Bucket-QR-MAX demonstrates scalability without requiring manual feature engineering or function approximation.

This development impacts AI systems requiring temporal reasoning—scheduling algorithms, robotics with sequential dependencies, and autonomous systems where decisions depend on accumulated context rather than instantaneous observations. The polynomial sample complexity improvement directly translates to faster training and reduced computational costs for practitioners.

The research establishes foundational theory for handling real-world decision processes with temporal dependencies, potentially catalyzing broader adoption of non-Markovian RL in production systems. Future work likely focuses on scaling to higher-dimensional problems and integrating with existing deep RL frameworks. The factorized approach may inspire parallel advances in other RL subfields where Markovian assumptions prove limiting.

• →QR-MAX is the first model-based RL algorithm for discrete non-Markovian reward processes with PAC optimality and polynomial sample complexity guarantees
• →The algorithm factorizes Markovian transition learning from non-Markovian reward handling using reward machines, improving both theoretical and practical performance
• →Bucket-QR-MAX extends the approach to continuous state spaces without manual gridding or function approximation, maintaining algorithmic efficiency
• →Non-Markovian RL handles temporal-dependency tasks where success depends on complete system history, expanding RL applicability beyond standard Markovian settings
• →Experimental results demonstrate significant improvements in sample efficiency and robustness compared to state-of-the-art model-based RL approaches