mlsanityData to 14 Oct 2026

Learning Non-Markovian Reward Models in MDPs

arXiv 2001.09293 ↗First posted 25 Jan 2020cs.AIcited by 11

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

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.

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.

Builds on

3 of 21 references.

References · 3

  1. 2017Safe Reinforcement Learning via Shieldingcited by 449
  2. 2018Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specificationscited by 72
  3. 2018Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraintscited by 8

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 1; 2023: 1; 2024: 3; 2025: 4.

11 papers.

  1. 2021Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logiccited by 39
  2. 2024Reward Machines for Deep RL in Noisy and Uncertain Environmentscited by 11
  3. 2022Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machinescited by 10
  4. 2021Decentralized Graph-Based Multi-Agent Reinforcement Learning Using Reward Machinescited by 7
  5. 2024Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markovcited by 5
  6. 2024Multi-Agent Reinforcement Learning with a Hierarchy of Reward Machinescited by 3
  7. 2025Constructing Non-Markovian Decision Process via History Aggregatorcited by 1
  8. 2025Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modelingcited by 1
  9. 2023Reinforcement Learning With Reward Machines in Stochastic Gamescited by 0
  10. 2025Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processescited by 0
  11. 2025Physics-Informed Reward Machinescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2020Online Learning of Non-Markovian Reward Models
  2. 2019Reinforcement Learning with Non-Markovian Rewards
  3. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes
  4. 2024Neural Reward Machines
  5. 2025Fully Learnable Neural Reward Machines
  6. 2021Reinforcement Learning in Reward-Mixing MDPs
  7. 2026Learning in Markov Decision Processes with Exogenous Dynamics
  8. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning