Beyond Markov: A Unified RL Framework for Non-Markovian World Modeling and Policy Induction

Papers by Tang et al. (2024), Miao et al. (2024), Wang (2025), and Gupta et al. (2021) each address RL under non-Markovian assumptions, but from fragmented perspectives: delayed composite rewards, modularization via temporal logic, offline RL with reward machines, and fractional dynamics. This idea proposes synthesizing these strands into a unified RL formalism for non-Markovian environments. The framework would define policies, value functions, and learning objectives in terms of history-dependent (not state-dependent) functions, using automata, attention-based neural architectures, and fractional calculus. It would provide theoretical guarantees (e.g., sample complexity, convergence) for learning in environments where both transitions and rewards depend on extended histories—far beyond current MDP limitations. This synthesis could revolutionize RL’s applicability to real-world problems with memory, context, or delayed evaluative feedback, serving as a new theoretical bedrock for RL research.

References:

1. Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning. Yuting Tang, Xin-Qiang Cai, Jing-Cheng Pang, Qiyu Wu, Yao-Xiang Ding, Masashi Sugiyama (2024). arXiv.org.
2. ParMod: A Parallel and Modular Framework for Learning Non-Markovian Tasks. Ruixuan Miao, Xu Lu, Cong Tian, Bin Yu, Zhenhua Duan (2024). arXiv.org.
3. Using Reward Machines for Offline Reinforcement Learning With Non-Markovian Reward Functions. Yanze Wang (2025). Scientific Insights.
4. Non-Markovian Reinforcement Learning using Fractional Dynamics. Gaurav Gupta, Chenzhong Yin, Jyotirmoy V. Deshmukh, P. Bogdan (2021). IEEE Conference on Decision and Control.