# Learning Non-Markovian Reward Models in MDPs

arXiv: https://arxiv.org/abs/2001.09293 · HTML: https://mlsanity.com/paper/2001.09293/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 3 of its 21 references that are in the map.
- First posted on arXiv 25 Jan 2020.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 3 of 3)

- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints](https://mlsanity.com/paper/1804.08924/) (2018)

## Built on by (most cited first, 11 of 11)

- [Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic](https://mlsanity.com/paper/2102.12855/) (2021)
- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Decentralized Graph-Based Multi-Agent Reinforcement Learning Using Reward Machines](https://mlsanity.com/paper/2110.00096/) (2021)
- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (2024)
- [Multi-Agent Reinforcement Learning with a Hierarchy of Reward Machines](https://mlsanity.com/paper/2403.07005/) (2024)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling](https://mlsanity.com/paper/2508.04282/) (2025)
- [Reinforcement Learning With Reward Machines in Stochastic Games](https://mlsanity.com/paper/2305.17372/) (2023)
- [Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2508.01947/) (2025)
- [Physics-Informed Reward Machines](https://mlsanity.com/paper/2508.14093/) (2025)

## Abstract (arXiv)

There are situations in which an agent should receive rewards only after having accomplished a series of previous tasks. In other words, the reward that the agent receives is non-Markovian. One natural and quite general way to represent history-dependent rewards is via a Mealy machine; a finite state automaton that produces output sequences (rewards in our case) from input sequences (state/action observations in our case). In our formal setting, we consider a Markov decision process (MDP) that models the dynamic of the environment in which the agent evolves and a Mealy machine synchronised with this MDP to formalise the non-Markovian reward function. While the MDP is known by the agent, the reward function is unknown from the agent and must be learnt. Learning non-Markov reward functions is a challenge. Our approach to overcome this challenging problem is a careful combination of the Angluin's L* active learning algorithm to learn finite automata, testing techniques for establishing conformance of finite model hypothesis and optimisation techniques for computing optimal strategies in Markovian (immediate) reward MDPs. We also show how our framework can be combined with classical heuristics such as Monte Carlo Tree Search. We illustrate our algorithms and a preliminary implementation on two typical examples for AI.