mlsanityData to 7 Oct 2026

Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics

arXiv 2204.11833 ↗First posted 20 Apr 2022cs.LG cs.AI cs.SYcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the problem of reinforcement learning for a task encoded by a reward machine. The task is defined over a set of properties in the environment, called atomic propositions, and represented by Boolean variables. One unrealistic assumption commonly used in the literature is that the truth values of these propositions are accurately known. In real situations, however, these truth values are uncertain since they come from sensors that suffer from imperfections. At the same time, reward machines can be difficult to model explicitly, especially when they encode complicated tasks. We develop a reinforcement-learning algorithm that infers a reward machine that encodes the underlying task while learning how to execute it, despite the uncertainties of the propositions' truth values. In order to address such uncertainties, the algorithm maintains a probabilistic estimate about the truth value of the atomic propositions; it updates this estimate according to new sensory measurements that arrive from the exploration of the environment. Additionally, the algorithm maintains a hypothesis reward machine, which acts as an estimate of the reward machine that encodes the task to be learned. As the agent explores the environment, the algorithm updates the hypothesis reward machine according to the obtained rewards and the estimate of the atomic propositions' truth value. Finally, the algorithm uses a Q-learning procedure for the states of the hypothesis reward machine to determine the policy that accomplishes the task. We prove that the algorithm successfully infers the reward machine and asymptotically learns a policy that accomplishes the respective task.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 24 of its 64 references that are in the map. First posted on arXiv 20 Apr 2022.

Builds on

24 of 64 references.

References · 24

  1. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  2. 2016Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivationcited by 282
  3. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 200
  4. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 183
  5. 2018Flipout: Efficient Pseudo-Independent Weight Perturbations on Mini-Batchescited by 133
  6. 2016Reinforcement Learning With Temporal Logic Rewardscited by 114
  7. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 74
  8. 2019Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learningcited by 74
  9. 2016Q-Learning for Robust Satisfaction of Signal Temporal Logic Specificationscited by 65
  10. 2019Joint Inference of Reward Machines and Policies for Reinforcement Learningcited by 56
  11. 2018Logically-Constrained Reinforcement Learningcited by 50
  12. 2014A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specificationscited by 49
12 more
  1. 2019HouseExpo: A Large-scale 2D Indoor Layout Dataset for Learning-based Algorithms on Mobile Robotscited by 23
  2. 2019Induction of Subgoal Automata for Reinforcement Learningcited by 17
  3. 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
  4. 2020Stochastic Finite State Control of POMDPs with LTL Specificationscited by 11
  5. 2015Correct-by-synthesis reinforcement learning with temporal logic constraintscited by 10
  6. 2020Online Learning of Non-Markovian Reward Modelscited by 9
  7. 2014Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applicationscited by 8
  8. 2019Active Perception and Control from Temporal Logic Specificationscited by 4
  9. 2021Reinforcement Learning with Temporal Logic Constraints for Partially-Observable Markov Decision Processescited by 4
  10. 2015Optimal Temporal Logic Planning in Probabilistic Semantic Mapscited by 3
  11. 2020Barrier Functions for Multiagent-POMDPs with DTL Specificationscited by 2
  12. 2019Secure Control under Partial Observability with Temporal Logic Constraintscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 0; 2024: 4; 2025: 2; 2026: 3.

12 papers.

  1. 2024Reward Machines for Deep RL in Noisy and Uncertain Environmentscited by 11
  2. 2022Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machinescited by 10
  3. 2022Learning Task Automata for Reinforcement Learning using Hidden Markov Modelscited by 7
  4. 2024Learning Robust Reward Machines from Noisy Labelscited by 7
  5. 2024Neural Reward Machinescited by 6
  6. 2022Hierarchies of Reward Machinescited by 4
  7. 2024Provably Efficient Exploration in Reward Machines with Low Regretcited by 1
  8. 2025Accelerated Learning with Linear Temporal Logic using Differentiable Simulationcited by 1
  9. 2025Fully Learnable Neural Reward Machinescited by 1
  10. 2026Grounding LTL Tasks in Sub-Symbolic RL Environments for Zero-Shot Generalizationcited by 1
  11. 2026DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applicationscited by 0
  12. 2026Active Reward Machine Inference From Raw State Trajectoriescited by 0