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

In many real-world scenarios, the success of decision-making tasks relies on the entire history of actions taken, making traditional Markovian Reinforcement Learning (RL) approaches inadequate. To address this, QR-MAX was developed as a model-based algorithm specifically for discrete non-Markovian reward decision processes (NMRDPs).

It innovatively factorizes the learning of state transitions from the management of non-Markovian rewards using reward machines. This approach allows QR-MAX to achieve Probably Approximately Correct (PAC) convergence to near-optimal policies with polynomial sample complexity.

Additionally, the method was extended to continuous state spaces through Bucket-QR-MAX, which utilizes a SimHash-based discretizer to maintain the factorized structure while enabling efficient learning. Experimental comparisons demonstrate that QR-MAX outperforms state-of-the-art model-based RL methods in terms of sample efficiency and robustness, particularly in complex environments.

These advancements suggest significant potential for improving decision-making in various applications.