Reward Machines
Definition
Reward machines are finite-state representations of reward functions over high-level event traces. Instead of treating reward as an opaque scalar emitted by the environment, an RM tracks task progress through automaton states and labels transitions with event formulas and rewards.
Why It Matters
RMs make temporal reward structure explicit. That structure can improve sample efficiency, decompose sparse long-horizon tasks, support counterfactual or off-policy updates, and connect RL objectives to formal-language specifications.
Formalism / Key Objects
- Toro Icarte et al.’s general RM schema is
where U is the finite RM state set, u_0 is initial, F is a set of terminal RM states, delta_u: U x 2^P -> U union F updates RM state from event labels, and delta_r: U -> [S x A x S -> R] returns the reward function used at that RM state.
- A common simple reward-machine schema is
where U is a finite set of RM states, P is a finite proposition set, phi(u,u') is a DNF formula over P, r(u,u') is a transition reward, u_0 is the initial RM state, and U^A, U^R mark accepting and rejecting task states.
- Given an environment state-labeling function
l:S -> 2^P, an RM reads the trace of labels rather than raw states. If no outgoing transition formula is satisfied, the RM state remains unchanged. - Combining an environment state with an RM state gives a product-like state that can make history-dependent reward Markovian for planning or learning.
- In an MDPRM, the labeling function
L:S x A x S -> 2^Pfeeds transition events into the RM, and the augmented state(s,u)supports ordinary RL over the cross product. - Reward Machine Learning Methods records CRM counterfactual updates, QRM/HRM variants, and potential-based RM reward shaping.
- Furelos-Blanco2023 - Hierarchies of Reward Machines extends the transition function to
phi: U x U x M -> DNF_P, allowing an edge to call another RM under a context. The resulting HRM formalism is summarized in Hierarchical Reward Machine Semantics. - Cooperative reward-machine synthesis can search for individual RMs such that the induced multi-agent system satisfies an Alternating-Time Temporal Logic objective; see Cooperative Reward Machine Synthesis.
Connections
- Non-Markovian Reinforcement Learning uses RMs when reward or termination depends on event histories.
- Automata Learning can infer RMs from traces when the temporal reward specification is not supplied by a designer.
- Linear Temporal Logic and related specification languages can be compiled into automata-like reward/task structures.
- Safe Reinforcement Learning uses RM-style structure when temporal ordering, dead-ends, or forbidden prefixes define constraint satisfaction.
- Reward Machine Learning Methods summarizes how CRM, QRM, HRM, and reward shaping exploit RM structure during policy learning.
- Hierarchical Reward Machine Semantics records the HRM-specific call-stack semantics and flat-equivalence result.
- Alternating-Time Temporal Logic can express coalition objectives that guide the synthesis of agent-local reward machines.
- Compositional Reinforcement Learning is adjacent because reward machines and pMDP subsystem interfaces both expose task structure for decomposed learning, but they verify different objects.
Common Confusions
- An RM is not an environment dynamics model; it represents reward/task progress over labels.
- A reward machine can be hand-specified, compiled from a formal specification, or learned from traces. These are distinct workflows.
- Flattening a hierarchical or compositional reward representation can preserve behavior while destroying the compact structure that made learning tractable.