# Online Learning of Non-Markovian Reward Models

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

## Key facts

- Cited by 9 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 7 of its 30 references that are in the map.
- First posted on arXiv 26 Sep 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, 7 of 7)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks](https://mlsanity.com/paper/1903.08792/) (2019)
- [Safe Exploration in Finite Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/1606.04753/) (2016)
- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [Logically-Constrained Neural Fitted Q-Iteration](https://mlsanity.com/paper/1809.07823/) (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, 9 of 9)

- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards](https://mlsanity.com/paper/2310.00435/) (2023)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (2024)
- [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)
- [Exact Distinguishability in Non-Markovian Decision Processes](https://mlsanity.com/paper/2610.01527/) (2026)

## Abstract (arXiv)

There are situations in which an agent should receive rewards only after having accomplished a series of previous tasks, that is, rewards are 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 from input sequences. In our formal setting, we consider a Markov decision process (MDP) that models the dynamics of the environment in which the agent evolves and a Mealy machine synchronized with this MDP to formalize the non-Markovian reward function. While the MDP is known by the agent, the reward function is unknown to the agent and must be learned. Our approach to overcome this challenge is to use Angluin's L^* active learning algorithm to learn a Mealy machine representing the underlying non-Markovian reward machine (MRM). Formal methods are used to determine the optimal strategy for answering so-called membership queries posed by L^*. Moreover, we prove that the expected reward achieved will eventually be at least as much as a given, reasonable value provided by a domain expert. We evaluate our framework on three problems. The results show that using L^* to learn an MRM in a non-Markovian reward decision process is effective.