wiki

Hierarchical Reward Machine Semantics

3 min read

Hierarchical Reward Machine Semantics

Context

Furelos-Blanco2023 - Hierarchies of Reward Machines extends flat Reward Machines so that one RM can call another. The core technical point is that hierarchical calls can compactly represent reusable temporal subtasks while preserving a well-defined trace semantics.

Formal Statement

An HRM is

where \mathcal M={M_0,\ldots,M_{m-1}} \cup {M_top} is a finite set of constituent RMs plus a leaf RM, M_r is the root, and all machines share proposition set P.

Each non-leaf RM has transitions of the form

so a transition from u to v can call machine M_j under context formula phi_i(u,v,M_j).

The paper assumes:

  • no circular dependencies among calls;
  • rejecting states are global;
  • accepting and rejecting states have no outgoing transitions;
  • the root RM’s reward matches the underlying MDP reward.

A hierarchy state is

where M_i is the current RM, u is its current state, \Phi is an accumulated context, and \Gamma is a call stack. A stack item <u,v,M_i,M_j,varphi,Phi> records the calling state, return state, caller, callee, satisfied disjunct/context, and accumulated context.

For a hierarchy state <M_i,u,Phi,Gamma>, the exit condition xi_{i,u,Phi} is the DNF condition under which that state can be left. For the leaf, it is just Phi; otherwise it recursively disjoins the exit conditions of callable machines reached by outgoing transitions.

The hierarchy traversal H(lambda) is the unique sequence of hierarchy states produced by repeatedly applying the hierarchical transition function delta_H to the labels in trace lambda. The HRM accepts a trace when the traversal ends at an accepting state of the root with an empty stack, and rejects a trace when any constituent RM reaches a rejecting state.

Two central results are:

  • Flat equivalence: every HRM has an equivalent flat HRM that accepts, rejects, or leaves incomplete exactly the same traces.
  • Exponential blow-up: the equivalent flat HRM can require exponentially many states and edges in the height of the root RM.

Derivation / Construction

  • Calls are encoded by extending flat RM transitions from phi(u,v) to phi(u,v,M_j).
  • Contexts make outgoing calls mutually exclusive enough for deterministic traversal. A label must satisfy both the call context and the callee’s exit condition before the call starts.
  • delta_H has three core cases:
    • if the current RM is accepting and the stack is nonempty, pop the stack and return control to the caller;
    • if the current label satisfies a valid call context and callee exit condition, push a stack item and recursively enter the callee;
    • otherwise keep the hierarchy state unchanged.
  • Flattening is behavior-preserving because the flat machine can encode the reachable combinations of RM states, contexts, and stack information needed to reproduce delta_H.
  • The same encoding explains the blow-up: repeated reuse of lower-level RMs can keep the HRM compact while forcing the flat machine to materialize many combinations of hierarchical progress.
  • Policy learning derives two option families from the HRM: formula options that reach primitive label formulas, and call options that reach accepting states of called RMs.

Implications

  • HRMs preserve the formal trace semantics of RMs while adding compositional reuse.
  • The flat-equivalence theorem says hierarchy is not extra trace-language expressivity; its value is representational compactness and reusable learning structure.
  • The exponential blow-up result explains why learning the non-flat structure can be feasible when learning an equivalent flat RM is not.
  • The assumptions matter: acyclic calls, global rejection, and known propositions simplify semantics and learning.

Graph View

Backlinks