Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning (2020-10-06T00:00:00.000000Z)

TL;DR

This paper proposes reward machines, a type of finite state machine that supports the specification of reward functions while exposing reward function structure, and describes different methodologies to exploit this structure to support learning, including automated reward shaping, task decomposition, and counterfactual reasoning with off-policy 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.

Authors

Rodrigo Toro Icarte

3 papers

Toryn Q. Klassen

2 papers

R. Valenzano

2 papers

TL;DR

Abstract

Authors

References103 items

Temporal Logic Task Allocation in Heterogeneous Multirobot Systems

Learning Reward Machines: A Study in Partially Observable Reinforcement Learning

Lifelong Reinforcement Learning with Temporal Logic Formulas and Reward Machines

Non-Markovian Rewards Expressed in LTL: Guiding Search Via Reward Shaping

Reward Machines for Vision-Based Robotic Manipulation

DeepSynth: Automata Synthesis for Automatic Task Segmentation in Deep Reinforcement Learning

The Logical Options Framework

Modular Deep Reinforcement Learning for Continuous Motion Planning With Temporal Logic

LTL2Action: Generalizing LTL Instructions for Multi-Task RL

Learning Optimal Strategies for Temporal Tasks in Stochastic Games

Multi-Agent Reinforcement Learning with Temporal Logic Specifications

Disentangled Planning and Control in Vision Based Robotics via Reward Machines

Induction and Exploitation of Subgoal Automata for Reinforcement Learning

Deep Reinforcement Learning with Temporal Logics

A Composable Specification Language for Reinforcement Learning Tasks

Task-Oriented Active Perception and Planning in Environments with Partially Known Semantics

Counterfactual Data Augmentation using Locally Factored Dynamics

Reward Machines for Cooperative Multi-Agent Reinforcement Learning

Temporal-Logic-Based Reward Shaping for Continuing Reinforcement Learning Tasks

Temporal-Logic-Based Reward Shaping for Continuing Learning Tasks

Temporal Logic Monitoring Rewards via Transducers

Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples

Systematic Generalisation through Task Temporal Logic and Deep Reinforcement Learning

Symbolic Plans as High-Level Instructions for Reinforcement Learning

Restraining Bolts for Reinforcement Learning Agents

Interactive Robot Training for Non-Markov Tasks

Cautious Reinforcement Learning with Logical Constraints

Learning Non-Markovian Reward Models in MDPs

A formal methods approach to interpretable reinforcement learning for robotic planning

Reinforcement Learning with Non-Markovian Rewards.

Induction of Subgoal Automata for Reinforcement Learning

Reinforcement Learning-Driven Test Generation for Android GUI Applications using Formal Specifications

Formal Language Constraints for Markov Decision Processes

Modular Deep Reinforcement Learning with Temporal Logic Specifications

Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning

Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees

Learning Reward Machines for Partially Observable Reinforcement Learning

Joint Inference of Reward Machines and Policies for Reinforcement Learning

LTL and Beyond: Formal Languages for Reward Function Specification in Reinforcement Learning

Planning With Uncertain Specifications (PUnS)

Temporal Logic Guided Safe Reinforcement Learning Using Control Barrier Functions

Certified Reinforcement Learning with Logic Guidance

Constraint Satisfaction Propagation: Non-stationary Policy Synthesis for Temporal Logic Planning

Logically-Constrained Neural Fitted Q-Iteration

Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf Restraining Specifications

Teaching Multiple Tasks to an RL Agent using LTL

Using Reward Machines for High-Level Task Specification and Decomposition in Reinforcement Learning

Learning to Parse Natural Language to Grounded Reward Functions with Weak Supervision

Advice-Based Exploration in Model-Based Reinforcement Learning

Fast Online Exact Solutions for Deterministic MDPs with Sparse Rewards

LTLf/LDLf Non-Markovian Rewards

Logically-Constrained Reinforcement Learning

Inverse Reward Design

Learning Robust Rewards with Adversarial Inverse Reinforcement Learning

A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks

Hindsight Experience Replay

Deep Reinforcement Learning from Human Preferences

Environment-Independent Task Specifications via GLTL

Interactive Learning from Policy-Dependent Human Feedback

CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning

Reinforcement learning with temporal logic rewards

Modular Multitask Reinforcement Learning with Policy Sketches

Q-Learning for robust satisfaction of signal temporal logic specifications

Concrete Problems in AI Safety

OpenAI Gym

Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation

Deep Reinforcement Learning with Double Q-Learning

Continuous control with deep reinforcement learning

Optimal Policy Generation for Partially Satisfiable Co-Safe LTL Specifications

Human-level control through deep reinforcement learning

Adam: A Method for Stochastic Optimization

Optimal and dynamic planning for Markov decision processes with co-safe LTL specifications

The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes

APRIL: Active Preference-learning based Reinforcement Learning

A Task Specification Language for Bootstrap Learning

TAMER: Training an Agent Manually via Evaluative Reinforcement