mlsanityData to 7 Oct 2026

Learning Reward Machines: A Study in Partially Observable Reinforcement Learning

arXiv 2112.09477 ↗First posted 17 Dec 2021cs.LG cs.AIcited by 16

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning (RL) is a central problem in artificial intelligence. This problem consists of defining artificial agents that can learn optimal behaviour by interacting with an environment -- where the optimal behaviour is defined with respect to a reward signal that the agent seeks to maximize. Reward machines (RMs) provide a structured, automata-based representation of a reward function that enables an RL agent to decompose an RL problem into structured subproblems that can be efficiently learned via off-policy learning. Here we show that RMs can be learned from experience, instead of being specified by the user, and that the resulting problem decomposition can be used to effectively solve partially observable RL problems. We pose the task of learning RMs as a discrete optimization problem where the objective is to find an RM that decomposes the problem into a set of subproblems such that the combination of their optimal memoryless policies is an optimal policy for the original problem. We show the effectiveness of this approach on three partially observable domains, where it significantly outperforms A3C, PPO, and ACER, and discuss its advantages, limitations, and broader potential.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 22 of its 55 references that are in the map. First posted on arXiv 17 Dec 2021.

Builds on

22 of 55 references.

References · 22

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  3. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  4. 2018Learning Dexterous In-Hand Manipulationcited by 643
  5. 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 457
  6. 2016Reinforcement Learning with Unsupervised Auxiliary Taskscited by 400
  7. 2019Challenges of Real-World Reinforcement Learningcited by 282
  8. 2016Sample Efficient Actor-Critic with Experience Replaycited by 185
  9. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 183
  10. 2016Control of Memory, Active Perception, and Action in Minecraftcited by 61
  11. 2018Optimizing Agent Behavior over Long Time Scales by Transporting Valuecited by 57
  12. 2019Joint Inference of Reward Machines and Policies for Reinforcement Learningcited by 56
10 more
  1. 2019Reinforcement Learning with Non-Markovian Rewardscited by 45
  2. 2020Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamplescited by 23
  3. 2020Interpretable Sequence Classification via Discrete Optimizationcited by 19
  4. 2013Learning Finite-State Controllers for Partially Observable Environmentscited by 18
  5. 2019Induction of Subgoal Automata for Reinforcement Learningcited by 17
  6. 2020Active Task-Inference-Guided Deep Inverse Reinforcement Learningcited by 17
  7. 2017Memory Augmented Control Networkscited by 13
  8. 2020The act of remembering: a study in partially observable reinforcement learningcited by 11
  9. 2020Online Learning of Non-Markovian Reward Modelscited by 9
  10. 2016Learning Moore Machines from Input-Output Tracescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 6; 2025: 3; 2026: 5.

16 papers.

Sort:

By area:

  1. 2023f-Policy Gradients: A General Framework for Goal Conditioned RL using f-Divergencescited by 14
  2. 2024Adaptive Layer Splitting for Wireless LLM Inference in Edge Computing: A Model-Based Reinforcement Learning Approachcited by 12
  3. 2024Reward Machines for Deep RL in Noisy and Uncertain Environmentscited by 11
  4. 2024Learning Robust Reward Machines from Noisy Labelscited by 7
  5. 2023Reinforcement Learning with Knowledge Representation and Reasoning: A Brief Surveycited by 5
  6. 2025Pushdown Reward Machines for Reinforcement Learningcited by 4
  7. 2024Knowledge-Informed Auto-Penetration Testing Based on Reinforcement Learning with Reward Machinecited by 3
  8. 2025Learning Reward Machines from Partially Observed Policiescited by 3
  9. 2024Bayesian Inverse Reinforcement Learning for Non-Markovian Rewardscited by 1
  10. 2026Toward Learning POMDPs Beyond Full-Rank Actions and State Observabilitycited by 1
  11. 2024A Method for Fast Autonomy Transfer in Reinforcement Learningcited by 0
  12. 2025Active Learning of Symbolic Automata Over Rational Numberscited by 0
4 more
  1. 2026Active Reward Machine Inference From Raw State Trajectoriescited by 0
  2. 2026The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processescited by 0
  3. 2026When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signalcited by 0
  4. 2026Reward Structure Shapes the Interaction Between Episodic Exploration and Neural Memory in Reinforcement Learningcited by 0