Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

Summary

This partial ingest is based on the extracted full PDF text. Toro Icarte et al. give the core Reward Machines treatment for exposing reward-function structure to reinforcement learners. They define RMs as finite-state machines over high-level event labels, show how an MDP with an RM can be treated as a product MDP over environment and RM states, and evaluate several ways to exploit RM structure: counterfactual experiences (CRM), Q-learning for RMs (QRM), hierarchical RL for RMs (HRM), and automated potential-based reward shaping.

Key Claims

• RL often hides reward functions behind a scalar black box even though many reward functions are hand-programmed and contain useful temporal structure.
• Reward machines expose that structure as a finite-state reward process over detected events, making history-dependent reward Markovian once RM state is added to environment state.
• RMs can represent regular-language reward structure including loops, sequences, conditionals, and many temporally extended constraints.
• Counterfactual experiences reuse one transition across all RM states and preserve tabular Q-learning convergence under standard visitation conditions.
• HRM-style decomposition can speed early learning but may converge to suboptimal behavior when the decomposition does not preserve globally optimal policies.
• Potential-based reward shaping over RM states can make sparse tasks easier without changing the optimal-policy set, though the paper notes caveats for terminal-state potentials and continuous-control settings.
• Experiments across tabular, deep, multitask, and continuous domains show consistent sample-efficiency benefits from exploiting RM structure, especially with CRM.

Methods / Formalism

• A reward machine over propositions P, environment states S, and actions A is

$$R_{P,S,A}=⟨U,u_0,F,{\delta }_u,{\delta }_r⟩,$$

where U is the RM state set, u_0 is initial, F is a finite set of terminal RM states, delta_u: U x 2^P -> U union F, and delta_r: U -> [S x A x S -> R].

• A simple RM replaces the reward-function output with a numeric reward delta_r: U x 2^P -> R.
• An MDPRM combines an MDP with propositions and a labeling function:

$$T=⟨S,A,p,\gamma ,P,L,U,u_0,F,{\delta }_u,{\delta }_r⟩,$$

where L:S x A x S -> 2^P feeds events into the RM.

• The induced decision state is (s,u): rewards may be non-Markovian relative to S alone but Markovian over S x U.
• Reward Machine Learning Methods records the reusable formal details for CRM, QRM/HRM, and potential-based reward shaping.

Evidence / Experiments

• Domains include tabular OfficeWorld and CraftWorld tasks, multitask variants, WaterWorld with deep RL, and continuous-control HalfCheetah tasks.
• Compared methods include cross-product baselines, Q-learning or DDQN with RM reward shaping, CRM, HRM, CRM plus shaping, and HRM plus shaping.
• The paper reports that CRM usually converges to the best policies, HRM often learns useful behavior faster but can settle at suboptimal policies, and reward shaping helps in some discrete settings but not consistently in continuous control.
• The authors also discuss computational overhead: CRM and HRM perform extra updates or generate extra replay data, but those updates are parallelizable.

Connections

• Core source for Reward Machines and Non-Markovian Reinforcement Learning.
• Provides the product-state bridge between automata-like reward specifications and ordinary RL algorithms.
• Complements Furelos-Blanco2023 - Hierarchies of Reward Machines, which adds reusable hierarchical calls, and Varricchione2023 - Synthesising Reward Machines for Cooperative MARL, which synthesizes RMs from ATL specifications.
• Connects to Automata Learning because the paper surveys work on learning RMs from traces and highlights the dependence on correct labeling functions.
• Connects to Safe Reinforcement Learning when the RM encodes forbidden prefixes or temporally extended constraints.

Open Questions

• Existing RM-learning methods generally assume a correct labeling function; jointly learning event detectors and RMs remains open.
• Noisy labels, partial observability, and real-world event detectors complicate RM state updates.
• CRM’s benefits depend on whether one transition is informative for multiple RM states; HRM’s benefits depend on whether the decomposition preserves good policies.
• The paper suggests differentiable RMs and richer grammar classes as future directions for tasks beyond regular-language memory.

Citation

Toro Icarte, R., Klassen, T. Q., Valenzano, R., and McIlraith, S. A. (2022). Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research, 73, 173-208.