mlsanityData to 14 Oct 2026

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

arXiv 2401.11325 ↗First posted 20 Jan 2024cs.LG cs.AIcited by 5

On the map: Deep reinforcement learning methods → Interpretable and logic-guided RL

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.

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.

Builds on

15 of 35 references.

References · 15

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 465
  3. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  4. 2016Reinforcement Learning With Temporal Logic Rewardscited by 117
  5. 2021On the Expressivity of Markov Rewardcited by 71
  6. 2017Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamplescited by 66
  7. 2019Joint Inference of Reward Machines and Policies for Reinforcement Learningcited by 56
  8. 2019Reinforcement Learning with Non-Markovian Rewardscited by 45
  9. 2020Induction and Exploitation of Subgoal Automata for Reinforcement Learningcited by 26
  10. 2020Interpretable Sequence Classification via Discrete Optimizationcited by 19
  11. 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
  12. 2022Non-Markovian Reward Modelling from Trajectory Labels via Interpretable Multiple Instance Learningcited by 13
3 more
  1. 2020Learning Non-Markovian Reward Models in MDPscited by 11
  2. 2020Online Learning of Non-Markovian Reward Modelscited by 9
  3. 2023Learning Symbolic Representations for Reinforcement Learning of Non-Markovian Behaviorcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 1.

5 papers.

  1. 2025Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Datacited by 5
  2. 2025Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modelingcited by 1
  3. 2025Fully Learnable Neural Reward Machinescited by 1
  4. 2025Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processescited by 0
  5. 2026DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applicationscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Expressive Reward Synthesis with the Runtime Monitoring Language
  2. 2025About Time: Model-free Reinforcement Learning with Timed Reward Machines
  3. 2025Pushdown Reward Machines for Reinforcement Learning
  4. 2025Physics-Informed Reward Machines
  5. 2026Active Reward Machine Inference From Raw State Trajectories
  6. 2024Neural Reward Machines
  7. 2024Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning
  8. 2025RLAF: Reinforcement Learning from Automaton Feedback