Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

Abstract

Reinforcement learning (RL) methods usually treat reward functions as black boxes. As such, these methods must extensively interact with the environment in order to discover rewards and optimal policies. In most RL applications, however, users have to program the reward function and, hence, there is the opportunity to make the reward function visible -- to show the reward function's code to the RL agent so it can exploit the function's internal structure to learn optimal policies in a more sample efficient manner. In this paper, we show how to accomplish this idea in two steps. First, we propose reward machines, a type of finite state machine that supports the specification of reward functions while exposing reward function structure. We then describe different methodologies to exploit this structure to support learning, including automated reward shaping, task decomposition, and counterfactual reasoning with off-policy learning. Experiments on tabular and continuous domains, across different tasks and RL agents, show the benefits of exploiting reward structure with respect to sample efficiency and the quality of resultant policies. Finally, by virtue of being a form of finite state machine, reward machines have the expressive power of a regular language and as such support loops, sequences and conditionals, as well as the expression of temporally extended properties typical of linear temporal logic and non-Markovian reward specification.

References in corpus (35)

• Continuous control with deep reinforcement learning
• Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation
• Deep reinforcement learning from human preferences
• Hindsight Experience Replay
• Modular Multitask Reinforcement Learning with Policy Sketches
• Interactive Learning from Policy-Dependent Human Feedback
• Environment-Independent Task Specifications via GLTL
• Logically-Constrained Reinforcement Learning
• Temporal Logic Guided Safe Reinforcement Learning Using Control Barrier Functions
• Temporal-Logic-Based Reward Shaping for Continuing Reinforcement Learning Tasks
• Modular Deep Reinforcement Learning with Temporal Logic Specifications
• A Composable Specification Language for Reinforcement Learning Tasks
• LTL2Action: Generalizing LTL Instructions for Multi-Task RL
• Cautious Reinforcement Learning with Logical Constraints
• Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications
• Planning With Uncertain Specifications (PUnS)
• Certified Reinforcement Learning with Logic Guidance
• Reinforcement Learning-Driven Test Generation for Android GUI Applications using Formal Specifications
• Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning
• Joint Inference of Reward Machines and Policies for Reinforcement Learning
• Counterfactual Data Augmentation using Locally Factored Dynamics
• Systematic Generalisation through Task Temporal Logic and Deep Reinforcement Learning
• Learning Non-Markovian Reward Models in MDPs
• Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples
• Learning Optimal Strategies for Temporal Tasks in Stochastic Games
• Interactive Robot Training for Non-Markov Tasks
• The Logical Options Framework
• Temporal Logic Task Allocation in Heterogeneous Multi-Robot Systems
• Formal Language Constraints for Markov Decision Processes
• Disentangled Planning and Control in Vision Based Robotics via Reward Machines
• Constraint Satisfaction Propagation: Non-stationary Policy Synthesis for Temporal Logic Planning
• A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks
• Learning Reward Machines: A Study in Partially Observable Reinforcement Learning
• Fast Online Exact Solutions for Deterministic MDPs with Sparse Rewards
• Lifelong Reinforcement Learning with Temporal Logic Formulas and Reward Machines

Cited by in corpus (18)

• Overcoming Exploration: Deep Reinforcement Learning for Continuous Control in Cluttered Environments from Temporal Logic Specifications
• Beyond Preferences in AI Alignment
• LTL2Action: Generalizing LTL Instructions for Multi-Task RL
• Structure in Deep Reinforcement Learning: A Survey and Open Problems
• Reinforcement Learning with Stochastic Reward Machines
• A Survey of Knowledge-based Sequential Decision Making under Uncertainty
• Exploiting Transformer in Sparse Reward Reinforcement Learning for Interpretable Temporal Logic Motion Planning
• Compositional Reinforcement Learning from Logical Specifications
• Goals as Reward-Producing Programs
• Formal Methods for Autonomous Systems
• Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives
• Learning Reward Machines in Cooperative Multi-Agent Tasks
• Lifelong Reinforcement Learning with Temporal Logic Formulas and Reward Machines
• Automata Learning from Preference and Equivalence Queries
• Reward Augmentation in Reinforcement Learning for Testing Distributed Systems
• Multi-agent Path Finding for Timed Tasks using Evolutionary Games
• Model Checking for Reinforcement Learning in Autonomous Driving: One Can Do More Than You Think!
• Designing Equilibria in Concurrent Games with Social Welfare and Temporal Logic Constraints