Online Learning of Non-Markovian Reward Models
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, 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.
Key facts. Cited by 9 papers in the map (data through 7 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.
Builds on
7 of 30 references.
References · 7
- 2014Adam: A Method for Stochastic Optimizationcited by 36,960
- 2017Safe Reinforcement Learning via Shieldingcited by 427
- 2019End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Taskscited by 256
- 2016Safe Exploration in Finite Markov Decision Processes with Gaussian Processescited by 72
- 2018Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specificationscited by 69
- 2018Logically-Constrained Neural Fitted Q-Iterationcited by 17
- 2018Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraintscited by 8
Built on by
Citing papers per year: 2021: 2; 2022: 2; 2023: 2; 2024: 1; 2025: 1; 2026: 1.
9 papers.
- 2021Learning Reward Machines: A Study in Partially Observable Reinforcement Learningcited by 16
- 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
- 2022Joint Learning of Reward Machines and Policies in Environments with Partially Known Semanticscited by 12
- 2023Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewardscited by 8
- 2022Learning Task Automata for Reinforcement Learning using Hidden Markov Modelscited by 7
- 2024Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markovcited by 5
- 2023Reinforcement Learning With Reward Machines in Stochastic Gamescited by 0
- 2025Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processescited by 0
- 2026Exact Distinguishability in Non-Markovian Decision Processescited by 0
- 2026Exact Distinguishability in Non-Markovian Decision Processes1 Oct 2026
- 2025Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processes3 Aug 2025
- 2024Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov20 Jan 2024
- 2023Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards30 Sep 2023
- 2023Reinforcement Learning With Reward Machines in Stochastic Games27 May 2023
- 2022Learning Task Automata for Reinforcement Learning using Hidden Markov Models25 Aug 2022
- 2022Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics20 Apr 2022
- 2021Learning Reward Machines: A Study in Partially Observable Reinforcement Learning17 Dec 2021
- 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning9 Jul 2021
Similar, not cited
Close in wording, no citation either way
- 2020Learning Non-Markovian Reward Models in MDPs
- 2019Reinforcement Learning with Non-Markovian Rewards
- 2024Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning
- 2022Non-Markovian Reward Modelling from Trajectory Labels via Interpretable Multiple Instance Learning
- 2024Bayesian Inverse Reinforcement Learning for Non-Markovian Rewards
- 2021Reinforcement Learning in Reward-Mixing MDPs
- 2025Learning Reward Machines from Partially Observed Policies
- 2024Tractable Offline Learning of Regular Decision Processes