Source-linked AI summary
Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning
Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, Sheila A. McIlraith
TL;DR
RL methods usually treat programmed reward functions as black boxes, forcing agents to discover reward structure through environmental interaction. The paper introduces reward machines and learning methods that exploit their structure through shaping, decomposition, and counterfactual reasoning. Experiments report improved sample efficiency and policy quality across tabular and continuous domains, while the approach has limitations involving HRM optimality, reward-shaping terminal states, and imperfect event detectors.
Problem
RL agents typically receive programmed reward functions as black boxes, despite the possibility that exposing their structure could support more sample-efficient learning.
Method
The paper represents reward functions with finite-state reward machines and exploits their structure through automated shaping, task decomposition, and counterfactual off-policy learning.
Results
Experiments across tabular and continuous domains show that exploiting reward-machine structure improves sample efficiency and the quality of resultant policies.
Takeaways & Limitations
Reward machines provide a structured representation supporting loops, sequences, conditionals, temporally extended properties, and some non-Markovian reward specifications.
Takeaways & Limitations
The approach assumes perfect event detectors, while HRM can converge to suboptimal solutions and potential-based shaping rewards bad terminal states under non-negative rewards.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper argues that reward functions are unnecessarily hidden from RL agents even though users usually program them, and proposes exposing their structure to accelerate learning. It introduces reward machines and learning methods that exploit them through decomposition, shaping, and counterfactual reasoning.
- Programmed reward functions are typically presented to RL agents as black boxes, requiring interaction to discover rewards and optimal behaviour.
- Reward machines are finite state machines that compose reward functions using concatenation, loops, and conditional rules while exposing task structure.
- Reward-machine states track high-level environmental events and output the reward function appropriate to the current stage of the task.
- The proposed learning methods exploit reward-machine structure through task decomposition, reward shaping, and counterfactual reasoning with off-policy learning.
- The paper reports convergence conditions and empirical evaluations in discrete and continuous domains, including single-task and multitask problems.
- Reward functions specified in other languages can be translated into reward machines, which can also be learned from data and demonstrations.
2. Reinforcement Learning
This section formulates RL as interaction with an unknown Markov decision process and reviews value-based and actor-critic methods. It covers tabular and neural off-policy algorithms for discrete and continuous action spaces.
- An MDP specifies states, actions, rewards, transition probabilities, and a discount factor, while the agent interacts without knowing the environment model.
- The agent seeks a policy maximizing expected discounted return, and an optimal policy selects actions with the highest optimal Q-value.
- Tabular Q-learning estimates the optimal Q-function from experience using exploratory action selection and is off-policy.
- Tabular Q-learning converges to an optimal policy in the limit when every state-action pair is visited infinitely often, but is impractical for large state spaces.
- DQN approximates Q-values with a neural network trained from replayed experience, while Double DQN separates action selection from value estimation to reduce overestimation bias.
- DDPG extends off-policy actor-critic learning to continuous actions using neural approximations for the Q-value and policy.
3. Reward Machines
Reward machines map high-level environmental events to machine-state transitions and reward functions, making temporally extended reward structure explicit. They represent Markovian rewards and regular-language classes of non-Markovian rewards, but not arbitrary history-dependent rewards.
- Reward machines expose temporally extended and non-Markovian reward structure by returning different reward functions at different machine states.
- The office-gridworld example represents staged behaviour such as collecting coffee or mail, delivering items, and avoiding decorations through event-labelled transitions.
- A reward machine is a finite-state model with an initial state, terminal states, event-driven transitions, and state-dependent reward functions.
- At each step, a labelling function converts an environment transition into true propositions that update the reward-machine state and determine the reward.
- An MDPRM can be viewed as an MDP over environment–machine state pairs, preserving expected discounted returns between the two representations.
- Reward machines express every Markovian reward function and non-Markovian rewards whose relevant histories are distinguishable by a finite set of regular expressions.
- Non-Markovian rewards that distinguish histories by non-regular properties, such as counting state visits, cannot be expressed by reward machines.
4. Exploiting the RM Structure in Reinforcement Learning
The paper develops RL methods that exploit reward-machine structure, including cross-product learning, counterfactual experience reuse, and hierarchical options. These methods can improve sample efficiency, although HRM may converge to sub-optimal policies and reward shaping has terminal-state limitations.
- Cross-product learning: Standard RL can learn MDPRMs by treating the environment and reward-machine states as a cross-product state.Any RL algorithm can learn π(a|s, u); convergence guarantees carry over to the MDPRM.
- Counterfactual experiences: CRM generates counterfactual experiences for every reward-machine state and feeds them to off-policy learners such as Q-learning, DQN, or DDPG.The method reuses one observed environment transition under alternative reward-machine states.
- Counterfactual experiences: CRM with tabular Q-learning converges to an optimal MDPRM policy when every state-action pair is visited infinitely often.The convergence argument follows from tabular Q-learning because counterfactual experiences preserve the environment transition probabilities.
- QRM and CRM: In the tabular case, QRM and CRM behave identically because CRM’s joint Q-function can be partitioned by reward-machine state.With function approximation, QRM may require separate networks, whereas CRM uses one network covering all reward-machine states.
- Hierarchical reinforcement learning: HRM decomposes reward-machine learning into options and learns option policies simultaneously through off-policy learning.Each option is associated with a reward-machine transition and aims to reach its target state quickly.
- Hierarchical reinforcement learning: HRM can learn good policies quickly but may converge to sub-optimal solutions because its option policies greedily prioritize rapid reward-machine transitions.The coffee-delivery example shows that locally fastest subgoals can produce a globally inferior policy.
5. Experimental Evaluation
Across tabular, continuous-state, and continuous-control tasks, methods exploiting reward-machine structure generally outperform cross-product baselines and can learn faster, although some approaches converge suboptimally or depend on suitable experience sharing.
- Overall findings: CRM and HRM outperform cross-product baselines in all experiments, with the advantage increasing in multitask settings.The reported gap is especially large in the more complex, sparser-reward Minecraft domain.
- Overall findings: CRM converges to the best policies in all but one experiment, while HRM often learns faster initially but converges to suboptimal policies.This pattern is reported across the evaluated domains and task settings.
- Tabular domains: In the office world, CRM and CRM+RS quickly learn optimal multitask policies, and CRM remains strongest in the hardest single-task experiment.HRM initially learns faster without shaping but is eventually overtaken because it converges to a suboptimal policy.
- Continuous-state domains: In the water world, CRM performs best in multitask learning and converges to better policies than the other approaches on the evaluated single task.Adding reward shaping decreased the performance of all approaches in the multitask experiments.
- Continuous control tasks: In HalfCheetah, CRM completes 9 laps on average by the end of learning, whereas HRM completes around 6 laps per episode.HRM's myopic subgoal optimization prevents it from accounting for the control needed after reaching intermediate points.
- Continuous control tasks: HRM performs best on the sparse-reward task of reaching F, doing so in less than 90 steps, while CRM reaches F in 120 steps in some runs but unreliably.The task's decomposition preserves the conditions under which HRM is effective.
6. Related Work
The paper situates reward machines among reward-specification languages and methods for exploiting prior knowledge in reinforcement learning. It also discusses extensions, empirical improvements, and limitations of manually designed reward functions.
- Reward Machine Research: Reward-machine research builds on finite-state and formal-language approaches for specifying tasks, constraints, and rewards in reinforcement learning.Related work includes linear temporal logic and other formal languages translated into finite-state representations.
- Reward Machine Research: This paper extends earlier reward-machine work by simplifying the formulation, adding terminal states, introducing CRM and HRM, and broadening the experiments.The evaluation adds average reward per step, continuous-control domains, and single-task experiments.
- Reward Specification: Manually designed reward functions may produce unintended behavior because designers can omit penalties or agents can discover unintended reward-maximizing strategies.Reward machines do not solve this reward-design problem, although they may simplify specification of temporally extended behaviors.
- Exploiting Prior Knowledge: Prior knowledge can support decomposition, data augmentation, and reward shaping, while hierarchical methods trade faster learning against possible convergence to suboptimal policies.Reward machines can define methods such as QRM, CRM, and reward shaping that retain optimal-policy convergence guarantees, whereas HRM inherits option-based limitations.
- Reward Specification: Reward machines expose compositional structure, including loops, conditionals, interleavings, and temporally extended behavioral constraints, beyond sub-goal sequences and sketches.Their finite-state structure supports reward specifications that can represent regular-language behaviors.
- Exploiting Prior Knowledge: CRM relabels experiences using reward-machine states, extending counterfactual learning beyond goal-state relabeling to temporally extended behaviors.The paper contrasts CRM with HER and CoDA and identifies their combination as a direction for future work.
7. Concluding Remarks
Reward machines specify arbitrary and temporally extended rewards while exposing reward structure that learning methods can exploit for greater sample efficiency. The paper also identifies unresolved challenges involving labelling functions and broader formal-language extensions.
- Reward machines are finite state machines for specifying arbitrary rewards, including sparse rewards and temporally extended behaviors.
- Exposing reward structure can significantly improve learning sample complexity, enabling faster solutions and some problems otherwise unsolvable under limited interaction.
- Three methodologies exploit reward-machine structure: automated reward shaping, counterfactual reasoning, and a third approach described alongside them in the paper.
- Learning reward machines and their labelling functions jointly remains unresolved, and noisy event detectors create uncertainty about the appropriate reward-machine transition.
- Future work includes formal-language extensions beyond regular-language reward machines and methods enabling agents to use human instructions more effectively.