# Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 20 Jan 2024.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Induction and Exploitation of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/2009.03855/) (2020)
- [Interpretable Sequence Classification via Discrete Optimization](https://mlsanity.com/paper/2010.02819/) (2020)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Non-Markovian Reward Modelling from Trajectory Labels via Interpretable Multiple Instance Learning](https://mlsanity.com/paper/2205.15367/) (2022)
- [Learning Non-Markovian Reward Models in MDPs](https://mlsanity.com/paper/2001.09293/) (2020)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)
- [Learning Symbolic Representations for Reinforcement Learning of Non-Markovian Behavior](https://mlsanity.com/paper/2301.02952/) (2023)

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

- [Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data](https://mlsanity.com/paper/2507.10741/) (2025)
- [Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling](https://mlsanity.com/paper/2508.04282/) (2025)
- [Fully Learnable Neural Reward Machines](https://mlsanity.com/paper/2509.19017/) (2025)
- [Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2508.01947/) (2025)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)

## Abstract (arXiv)

Many Reinforcement Learning algorithms assume a Markov reward function to guarantee optimality. However, not all reward functions are Markov. This paper proposes a framework for mapping non-Markov reward functions into equivalent Markov ones by learning specialized reward automata, Reward Machines. Unlike the general practice of learning Reward Machines, we do not require a set of high-level propositional symbols from which to learn. Rather, we learn hidden triggers, directly from data, that construct them. We demonstrate the importance of learning Reward Machines over their Deterministic Finite-State Automata counterparts given their ability to model reward dependencies. We formalize this distinction in our learning objective. Our mapping process is constructed as an Integer Linear Programming problem. We prove that our mappings form a suitable proxy for maximizing reward expectations. We empirically validate our approach by learning black-box, non-Markov reward functions in the Officeworld domain. Additionally, we demonstrate the effectiveness of learning reward dependencies in a new domain, Breakfastworld.