Reward Machine Learning Methods

Context

Toro Icarte2022 - Reward Machines defines reward machines as finite-state reward specifications and studies how RL agents can exploit their exposed structure. This annex collects the reusable method-level details for cross-product learning, counterfactual experience generation, hierarchical decomposition, and reward shaping.

Formal Statement

An MDPRM is

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

where L:S x A x S -> 2^P labels environment transitions, delta_u updates the RM state, and delta_r returns the reward function or numeric reward associated with the current RM state.

The cross-product state (s,u) makes RM-mediated reward Markovian. A transition from (s,u) under action a reaches (s',u') with

$$u^{\prime }={\delta }_u(u,L(s,a,s^{\prime })).$$

Counterfactual experiences for reward machines (CRM) replace one observed transition with one synthetic experience for every RM state:

$$\{(s,\bar{u},a,{\delta }_r(\bar{u})(s,a,s^{\prime }),s^{\prime },{\delta }_u(\bar{u},L(s,a,s^{\prime })))\mid \bar{u}\in U\}.$$

For tabular Q-learning, CRM converges to an optimal MDPRM policy as long as every state-action pair is visited infinitely often.

Potential-based RM reward shaping uses a potential Phi over RM states and replaces the reward by

$$r^{\prime }(s,a,s^{\prime })=r(s,a,s^{\prime })+\gamma \Phi (s^{\prime })-\Phi (s),$$

which preserves the optimal-policy set under the standard potential-shaping conditions.

Derivation / Construction

• Cross-product learning treats S x U as the state space and applies ordinary RL to q(s,u,a).
• CRM observes that the environment transition (s,a,s') would have generated a well-defined RM update from every possible RM state, so one transition can train all RM-state-conditioned values in an off-policy learner.
• QRM partitions the cross-product value function by RM state, learning a separate q_u(s,a) for each u; in the tabular case it is equivalent to Q-learning with CRM.
• HRM builds options from RM edges or subgoals, giving a decomposition that can accelerate learning when the decomposition preserves good global policies.
• Automated reward shaping treats a simple RM as a deterministic MDP over RM states, computes state values by value iteration, and uses their negation as a shaping potential.

Implications

• RM structure can reduce reward sparsity and reuse experience across temporal contexts.
• CRM is especially attractive because it is easy to add to off-policy learners and keeps a convergence guarantee in the tabular setting.
• HRM trades global optimality risk for faster local subtask learning; it is useful when the RM decomposition matches the task’s optimal structure.
• Reward shaping preserves optimal policies in theory, but its practical usefulness depends on the domain and on terminal-state conventions.

Links

• Source: Toro Icarte2022 - Reward Machines
• Concept: Reward Machines
• Related concepts: Non-Markovian Reinforcement Learning, Automata Learning