PaperlayerView exact revision on arXiv

Source-linked AI summary

On Semi-Markov Suboptimality in Hierarchical Reinforcement Learning

Bingyun Liu, Yuheng Jing

arXiv:2610.05338v1cs.LGcs.AI

TL;DR

Hierarchical reinforcement learning can use temporally extended subtasks for exploration, but execution choices affect both deployment and policy learning. This paper separates those losses with a unified value and Bellman framework, then develops independent execution choices for behavior, targets, and deployment. Its comparisons connect execution improvement and ME-targeted training to option-based, goal-conditioned, and continuous-control learning.

  • Problem

    The paper addresses how to distinguish losses from when a learned hierarchy reselects subtasks and from which execution process its training objective optimizes.

    Source: §1 · pp. 1–2

  • Method

    Task and execution trees, a Unified Value Function, and a four-stage Bellman analysis support improvement procedures that specify behavior, target, and deployment execution separately.

    Source: §1 · pp. 1–2, §2 · p. 2

  • Results

    Comparisons connect execution improvement and ME-targeted training to option-based, goal-conditioned, and continuous-control learning.

    Source: §4.2 · p. 9, §5 · p. 9

  • Takeaways & Limitations

    The framework treats execution design as an explicit component of hierarchical policy optimization.

    Source: §5 · p. 9

    The evaluation results rely on bounded per-frame and exit rewards and uniform termination.

    Source: §2 · p. 4

Abstract

from arXiv · show

Hierarchical reinforcement learning uses temporally extended subtasks for exploration, yet committing to their execution can restrict both deployment and policy learning. We identify and separate the resulting execution and policy suboptimality. Task and execution trees distinguish reward objectives from policy choices and decision interruption. A Unified Value Function for HRL and a four-stage Generalized Hierarchical Bellman Equation then support a common analysis of both losses. Under bounded rewards and uniform termination, we establish hierarchical policy and execution improvement results. With the remaining node policies fixed, task-subtree compatibility and node-policy optimality under the original execution mode establish when Markov execution is optimal. The resulting decomposition leads to independent execution choices for behavior, targets, and deployment. We instantiate this principle through execution improvement and one-stage or two-stage policy improvement at arbitrary hierarchy depth. Option-based and goal-conditioned experiments demonstrate complementary gains from changing execution and changing the learning target. Controlled stochastic environments show how these gains depend on stochastic transition strength and spatial structure. This framework makes execution design an explicit component of hierarchical policy optimization.

1 INTRODUCTION

The introduction separates the execution choices made when a learned hierarchy is deployed from the execution process its policies were trained to optimize. It presents a unified theory and improvement procedures that keep task objectives, policy choices, and decision interruption distinct.

1 INTRODUCTION

  • The paper distinguishes execution suboptimality—when a policy reselects subtasks—from policy suboptimality— which execution process its training objective optimizes.Deployment execution and policy optimization are separate interventions within a fixed task hierarchy.Source: §1 · p. 1
  • Task and execution trees separate nested reward objectives and termination boundaries from policy choices and decision interruption.The Unified Value Function for HRL distinguishes the evaluated task from the node holding decision authority.Source: §1 · p. 1
  • ESIF changes deployment execution, while PSIF changes the execution process optimized during learning; both PSIF procedures apply at arbitrary hierarchy depth.PSIF-2S changes behavior and target execution through bottom-up node-wise stages; PSIF-1S preserves SME behavior and forms local ME targets.Source: §1 · p. 2
  • The evaluation spans tabular option-critic, goal-conditioned HAC, option-based DAC, and controlled local-slip and global-teleportation settings.The controlled experiments vary random-transition probability and type.Source: §1 · p. 2
  • The paper’s analysis uses a task-based MDP formalization in which node policies select child tasks and successive choices induce primitive-action policies.Comparisons keep the available task hierarchy explicit.Source: §1 · p. 2

2 A UNIFIED THEORY OF TASK OBJECTIVES AND EXECUTION

This section separates task objectives from execution choices and analyzes both with a unified value model and a four-stage Bellman recursion. It gives conditions for policy and execution improvement, including when Markov execution is optimal, and decomposes the losses into policy and execution components.

2 A UNIFIED THEORY OF TASK OBJECTIVES AND EXECUTION

  • The task tree encodes nested objectives and termination boundaries, while the execution tree specifies child-task calls and when decision authority returns to an ancestor.SME couples interruption to task termination; ME restarts decisions at the executing subtree’s root each frame without redefining the evaluated task’s reward or boundary.Source: §2 · p. 2
  • The unified value distinguishes the decision position from the conditioning task: one records who chooses next, while the other determines the reward objective and exit boundary.Several decision states may be visited at the same environment state while evaluating the same task.Source: Figure 1 · p. 3, §2 · p. 3
  • The GHBE divides one environment frame into decision descent, action and transition, task termination, and decision interruption; GHBOE replaces the optimized node’s decision expectation with a maximum.Other node policies remain fixed, and only survival continues through preparation after termination’s weighted survival and exit contributions.Source: §2 · pp. 3–4, Figure 2 · p. 4
  • Policy evaluation and improvement results assume bounded per-frame and exit rewards and uniform termination, which make the GHBE operator a contraction with a unique fixed point.The stated contraction factor is 1 −ϵ, and repeated evaluation converges to the fixed point.Source: §2 · p. 4
  • The optimal-execution result makes ME optimal when task-subtree compatibility holds and the node policy is optimal for its original execution mode, with other node policies fixed.The comparison concerns an arbitrary interruption subtree; compatibility matters because descendants may optimize rewards different from their ancestors’.Source: §2 · p. 5
  • In the two-level compatible setting, the returns satisfy JA ≥JB ≥JC ≥JD; the general result gives JA ≥JB and JC ≥JD, with JB ≥JC under compatibility.The comparison fixes the task tree and all node policies except the one being optimized.Source: §2 · p. 5
  • The theory separates policy suboptimality, JA −JB, from execution suboptimality, JB −JC, within a fixed task hierarchy.The former is the loss from optimizing for SME and deploying with ME; the latter is the loss from retaining SME at deployment.Source: §2 · p. 5
  • In the GridWorld example, JA = −8, JB = −11, JC = −12, and JD = −14: reselecting subtasks saves one frame in expectation, while optimizing for ME saves three more.The example uses a reward of −1 per frame and finite-trajectory calculations.Source: §2 · p. 5

3 DECOUPLING BEHAVIOR, TARGETS, AND DEPLOYMENT

This section specifies behavior, target, and deployment execution independently, retaining SME for exploration while allowing ME-targeted learning and deployment. It presents ESIF and two PSIF procedures that apply across hierarchy depth.

3 DECOUPLING BEHAVIOR, TARGETS, AND DEPLOYMENT

  • The design separates behavior execution for collecting trajectories, target execution for policy optimization, and deployment execution for acting with the learned policy tree.The task tree fixes reward objectives and exit boundaries; interruption functions specify execution separately for each role.Source: §3 · pp. 5–6
  • PSIF-2S progresses up the tree as each caller’s stage determines outgoing calls; PSIF-1S illustrates distinct SME behavior, local ME target execution, and ME deployment.The PSIF-1S target uses ME inside the optimized task’s subtree and SME outside it, including the incoming call.Source: Figure 3 · p. 6, Figure 4 · p. 6
  • ESIF keeps SME training and deploys the learned policy tree with ME, changing execution while retaining the node policies’ SME optimization objectives.Its idealized comparison is JC →JB, with the ME guarantee subject to optimal-node-policy and compatibility conditions.Source: §3 · p. 6
  • PSIF-2S trains nodes bottom-up: after its children complete Stage 2 and are fixed, a node calls them with ME and optimizes its MDP node policy on-policy.Lower primitive-action nodes start in Stage 2 because their SME and ME objectives coincide; the completed policy tree is deployed with ME.Source: §3 · pp. 6–7
  • PSIF-1S collects data with SME but gives each optimized node an ME target inside its subtree and SME execution outside it.The local target applies recursively at arbitrary depth, and the full policy tree uses ME at deployment.Source: §3 · p. 7
  • For PSIF-1S, option termination still determines the exit reward even though the option’s action lasts one frame.The option-exit boundary uses the upper ME value.Source: §3 · p. 7

4 EXPERIMENTAL ANALYSIS

Across option-based, goal-conditioned, and continuous-control comparisons, execution improvement and ME-targeted learning show complementary effects. In Fourrooms, the observed benefit of ME-targeted learning depends on both random-transition strength and spatial structure.

4 EXPERIMENTAL ANALYSIS

  • The experiments compare ESIF, PSIF-1S, and PSIF-2S in shared OC hierarchies, test execution improvement in goal-conditioned HAC, and evaluate a second-stage ME switch in DAC.The controlled transition sweep varies transition family and probability, and uses four or eight options.Source: §4 · p. 7, §4.2 · p. 8

4.1 LEARNING BEHAVIOR UNDER DECOUPLED EXECUTION

  • After the episode-500 switch, 2Stage(PSIF) reduced recorded training steps and finished below Baseline(ESIF), while 1Stage(PSIF) improved before the switch.NaiveME from initialization was less effective in both displayed settings; checkpoint comparisons separately assessed execution and policy effects after finite training.Source: §4.1 · p. 7, Figure 5 · p. 8

4.2 STOCHASTICITY SEPARATES EXECUTION AND POLICY EFFECTS

  • In global teleportation, PSIF-1S savings rose with p from 18.6 to 37.4 to 48.5 steps with four options, and from 23.4 to 35.7 to 36.9 with eight.Local-slip and execution-only curves were not uniformly monotone, so gains depended on transition strength and spatial structure.Source: §4.2 · p. 8
  • DAC return changes were +0.54% with two options and +7.41% with eight, while ESIF raised HAC success rates and PSIF-1S reduced OC evaluation steps in both transition families.These comparisons connect execution improvement and ME-targeted training across option-based, goal-conditioned, and continuous-control learning.Source: §4.2 · p. 9

5 SUMMARY AND FUTURE WORK

The paper separates execution and policy suboptimality within a fixed task hierarchy, using a unified value model and Bellman recursion to derive improvement criteria and multilevel procedures. It identifies future work on learning interruption rules, adapting to visitation shifts, and improving off-policy estimation for local ME targets.

5 SUMMARY AND FUTURE WORK

  • UVFH and a four-stage Bellman recursion distinguish task objectives, policy choice, and decision timing, supporting improvement criteria and a decomposition into execution and policy suboptimality.The resulting ESIF and two PSIF procedures specify behavior, target, and deployment execution independently.Source: §5 · p. 9

Appendix C.2 relates this execution-centered view to existing HRL approaches.

  • Future work includes learning interruption rules alongside node policies, adapting to parent-induced state–task visitation changes, and improving off-policy estimation for PSIF-1S local ME targets.The paper identifies these directions as following from its separation of execution and policy suboptimality.Source: Appendix C.2 · p. 9

REPRODUCIBILITY STATEMENT

  • The appendix provides formal definitions, theorem proofs, framework algorithms, instantiations, and experimental protocols and statistical aggregation procedures for reproducing the results.It also documents environments and hyperparameter settings.Source: REPRODUCIBILITY STATEMENT · p. 10

ETHICS STATEMENT

  • The study reports no human subjects, personal data, or real-world deployment, and states no ethical concerns beyond substantiating empirical claims.Generative AI was used for readability editing, not for methodology, experiments, results interpretation, mathematical claims, or proofs.Source: ETHICS STATEMENT · p. 10, AI USE STATEMENT · p. 10

A GUIDE TO THE SUPPLEMENTARY MATERIAL

  • Supplementary materials cover stochastic-environment and DAC experiments, interpretation and technical development, algorithms and instantiations, and environments, hyperparameters, and visualizations.Appendices K–N contain these materials.Source: A GUIDE TO THE SUPPLEMENTARY MATERIAL · p. 13

B.1 OC TRANSITION FAMILIES AND MEASUREMENT PROTOCOL

The supplementary sections specify the controlled OC transition experiments and checkpoint measurements, then elaborate the formalization, algorithmic procedures, and examples. They also distinguish execution-mode losses and describe the conditions and learning caveats around the idealized guarantees.

B.1 OC TRANSITION FAMILIES AND MEASUREMENT PROTOCOL

  • The Fourrooms OC sweep varies local-slip or global-teleportation probability across 1/6, 1/3, and 1/2 with four or eight options, using 2,000-episode runs capped at 1,000 steps.Checkpoint tests evaluate ten policy indices every ten episodes, test each for 35 episodes, and summarize episodes 910–1000 using matched policy indices.Source: §B.1 · p. 13

B.2 ALL TWELVE OC BEHAVIOR-POLICY LEARNING CURVES

  • The OC learning curves cover local slip and global teleportation; controlled checkpoint comparisons evaluate shared baselines under SME and ME and staged policies under ME.Table 2 reports episode 910–1000 step means and sample standard deviations across ten policy-window means; lower steps are better.Source: §B.2 · p. 13, Figure 7 · p. 14, Figure 8 · p. 15

B.3 SECOND-STAGE DAC COMPARISON ON HALFCHEETAH

  • The DAC comparison branches from matched 3 × 10^6-step checkpoints into learned-termination and ME continuations, reporting training return over the 3M–4M-step segment.The study uses 50 paired runs per option count; Table 3 summarizes the final 0.1M steps for valid two- and eight-option settings.Source: §B.3 · p. 16, Figure 9 · p. 16, Table 3 · p. 16

C ADDITIONAL INTERPRETATION OF THE UNIFIED FORMALIZATION

  • The unified formalization separates task reward objectives and termination boundaries from policy choice and decision interruption, with a four-stage recursion distinguishing task termination from authority transitions.The value-evaluation proof assumes bounded rewards and uniform positive termination; optimal execution additionally requires task-subtree compatibility and node-policy optimality under the original interruption tree.Source: C ADDITIONAL INTERPRETATION OF THE… · pp. 16, 18
  • PSIF-2S advances node-local stages bottom-up, while PSIF-1S keeps SME behavior and forms local ME targets for the optimized node’s subtree; both procedures apply at arbitrary depth.The idealized comparisons do not assert finite-training convergence; PSIF-2S and PSIF-1S also face visitation shift, off-policy, or approximation-error concerns.Source: Figure 10 · p. 17, C ADDITIONAL INTERPRETATION OF THE… · pp. 18–19

C.1 COMPLETE PSIF-1S UPDATES FOR OPTION-CRITIC

  • In the Option-Critic PSIF-1S instantiation, SME trajectories support ME targets, while the Fourrooms 1Stage termination update uses upper values distinct from the framework’s lower-value update.The termination baseline and option-exit reward are distinct quantities with distinct roles.Source: §C.1 · p. 19

C.2 CONTEXT WITHIN HIERARCHICAL REINFORCEMENT LEARNING

  • The paper distinguishes its execution analysis from complementary work on representation restrictions, temporal-abstraction sample efficiency, UVFA goal conditioning, and option-induced MDPs.It notes that UVFH additionally records decision authority and an independently chosen execution tree.Source: §C.2 · p. 19

E DETAILED PROBLEM FORMULATION

  • Calling subtasks yields variable-duration SMDP transitions, while ME permits frame-by-frame reselection and SME runs a selected subtask to termination; their different trajectories can create execution and policy suboptimality.In the GridWorld example, ME yields −11 versus SME’s −12 for a fixed policy; under ME, the optimal policy yields −8 versus −11 for the SMDP-optimal policy.Source: §D.2 · p. 20, E DETAILED PROBLEM FORMULATION · p. 21, §E.1 · p. 21

F.1 LIMITATIONS OF SME

The section analyzes how execution mode and policy objectives create distinct sources of hierarchical suboptimality. It derives conditions for improvement and explains the exploration–exploitation tradeoff that constrains training and deployment choices.

F.1 LIMITATIONS OF SME

  • The generalized suboptimality theory extends beyond the two-level narrow result to more-than-two-level hierarchies and arbitrary execution modes.The narrow theory is proven as a special case of the generalized theorem.Source: §F.1 · p. 23
  • Under suitable subtask conditions, ME is at least as good as other execution modes; without those conditions in deeper hierarchies, its optimality is not evident.The optimal-execution result assumes task-subtree compatibility and node-policy optimality under the original execution mode; two-level HRL satisfies the stated subtask conditions.Source: §F.1 · pp. 23–24
  • With execution trees fixed, replacing a node policy by one with better expected child-task value improves the value of the hierarchy.The theorem compares the node policies at a state while holding the rest of the execution tree unchanged.Source: §F.1 · p. 24
  • Changing only decision-interruption functions yields an execution-improvement guarantee when the resulting decision-transition values satisfy the stated comparison.The theorem derives decision-transition mechanisms from the two interruption functions.Source: §F.1 · p. 24

F.2 LIMITATIONS OF ME

  • ME training can create severe off-policy issues for subtasks, so the section recommends retaining SME for behavior-policy data collection.Under ME, higher-level interruptions can make target and behavior trajectories diverge, complicating propagation of task-termination boundary conditions; Figure 14 marks off-policy or missing trajectory actions in red.Source: §F.2 · p. 24, Figure 14 · p. 25

F.3 THE EXPLORATION–EXPLOITATION TRADEOFF INDUCED BY EXECUTION MODES

  • Using SME for both behavior and targets creates a tradeoff: SME supports subtask sampling, while its SMDP objective can be policy-suboptimal and ME is preferred for deployment.The section frames a reasonable design as collecting data through SME while learning the MDP-optimal policy set by some means.Source: §F.3 · p. 24, §F.1 · p. 24

G FRAMEWORK IMPLEMENTATIONS

The frameworks separate behavior, target, and deployment execution to address execution and policy suboptimality. They offer distinct training and deployment procedures, including option-based instances of two-stage improvement.

G FRAMEWORK IMPLEMENTATIONS

  • The three frameworks independently specify behavior, target, and deployment execution to balance exploration and exploitation and mitigate original algorithms’ SMDP suboptimality.The frameworks are ESIF, PSIF-2S, and PSIF-1S.Source: G FRAMEWORK IMPLEMENTATIONS · p. 25

G.1 FRAMEWORKS

  • ESIF leaves training unchanged and uses ME at deployment; PSIF-2S trains nodes first for SME objectives and then for ME objectives, while PSIF-1S collects SME data but forms ME targets.Both PSIF procedures apply at arbitrary hierarchy depth; PSIF-2S stages propagate bottom-up, while PSIF-1S uses ME targets within the node being optimized.Source: §G.1 · p. 25, G FRAMEWORK IMPLEMENTATIONS · p. 25

G.2 ALGORITHM IMPROVEMENT INSTANCES

  • In the option-based PSIF-2S instance, the root first calls options using SME, then calls completed options using ME with option policies and termination functions fixed.The lowest task nodes learn option policies during the first stage; the upper-level value update in the second stage follows the ME optimality equation.Source: §G.2 · p. 26
  • The option-based PSIF-1S instance collects data under SME while updating higher-level values off-policy with the ME optimality equation.At option exit, this instance uses the upper ME value as the target.Source: §G.2 · p. 26

H ADDITIONAL EXPERIMENTAL ANALYSIS

The appendix tests execution and policy suboptimality in hierarchical control, then uses a stochastic GridWorld to illustrate how execution choices can change outcomes. It also situates the framework among related work and lists its notation.

H ADDITIONAL EXPERIMENTAL ANALYSIS

  • On stochastic AntReacher, HAC showed an execution-suboptimality performance gap above 20%; flat RL baselines also failed to train effectively on these long-horizon tasks.The experiments also validated execution suboptimality for OC on Fourrooms.Source: H ADDITIONAL EXPERIMENTAL ANALYSIS · p. 26, Figure 15 · p. 27
  • OC-PSIF-2S completed Fourrooms in over 30% fewer steps with 8 options and over 50% fewer with 4 options than the OC baseline.Figure 15b compares OC, OC-PSIF-2S, and OC-PSIF-1S under ME deployment.Source: Figure 15 · p. 27, H ADDITIONAL EXPERIMENTAL ANALYSIS · p. 28
  • PSIF-1S achieved better final performance than PSIF-2S, whose fixed child policies can degrade under state-task distribution shift during second-stage training.PSIF-1S avoids manually deciding when to fix child policies and can learn subtask support without being constrained by the earlier policy’s support.Source: H ADDITIONAL EXPERIMENTAL ANALYSIS · p. 28
  • ESIF addresses execution suboptimality but not policy suboptimality; PSIF-2S can face distribution shift, while PSIF-1S faces off-policy mismatch between SME behavior and ME targets.Efficiently computing decoupled execution objectives for different algorithms remains open, and extending the frameworks to policy-gradient HRL is future work.Source: H ADDITIONAL EXPERIMENTAL ANALYSIS · p. 28

I EXTENDED RELATED WORK

  • Prior work studied planning optimality, subtask representations, and option execution suboptimality, while this paper also treats policy suboptimality and distinguishes behavior, target, and deployment execution.The cited work includes Sutton et al. (1999), Wen et al. (2020), and Nachum et al. (2019).Source: I EXTENDED RELATED WORK · pp. 28–29

J NOTATIONS

  • Table 6 lists the symbols used in the paper’s detailed formalization and proofs.The supplied notation passage identifies the table’s purpose but does not enumerate its symbols.Source: J NOTATIONS · p. 29, Table 6 · p. 29

K NAIVE CASE STUDY: GRIDWORLD

  • The 6 × 8 GridWorld has a central 4 × 6 obstacle, two corridors to the goal, and a 50% chance of an additional transition at the marked region.Each transition costs −1, and subgoals are states at L1 distance exactly 5.Source: K NAIVE CASE STUDY: GRIDWORLD · p. 30

K.1 EXECUTION SUBOPTIMALITY

  • In the GridWorld execution example, ME yields −11 expected return versus −12 for SME when the stochastic transition occurs with probability 0.5.After teleportation, ME can reselect a subgoal, while SME continues the unfinished subtask.Source: §K.1 · p. 30

K.2 POLICY SUBOPTIMALITY

The GridWorld case study contrasts policies optimal under SME and ME. The example shows that a policy set optimal under one execution mode need not be optimal under the other.

K.2 POLICY SUBOPTIMALITY

  • The illustrated π* trajectory under SME uses three sequential subtasks, whereas ME selects a new subtask at each frame.The ME choices include (5, 4), (5, 5), and (0, 8).Source: §K.2 · p. 30
  • Only a subset of the possible high-level node policies has finite expected returns in the example; π− is optimal under SME.The passage states there are 25 = 32 possible node policies.Source: §K.2 · p. 32
  • In GridWorld, the SME-optimal policy set π− returns −12 under SME, while the ME-optimal π* returns −8 under ME; cross-mode returns are −14 and −11, respectively.The passage identifies π− as SMDP-optimal and π* as MDP-optimal.Source: §K.2 · p. 32, Figure 18 · p. 32

L FORMALIZATION AND THEORETICAL PROOF

This section formalizes task termination and reward objectives separately from execution interruption and policy calling, and develops a unified value function and hierarchical Bellman equations to analyze execution and policy optimality. It distinguishes SMDP- and MDP-optimal node policies, gives conditions for comparing their returns, and shows that the generalized operator for a fixed execution tree is contractive with a unique fixed point reached from any initial value.

L.1 TASK TREE AND EXECUTION TREE

  • Task trees specify nested task objectives and reward boundaries, while execution trees separately specify how node policies are called and interrupted.Task termination and decision interruption are distinct functions; existing HRL often ties them together, which the framework identifies as unreasonable.Source: §L.1 · p. 33, §L.1.2 · p. 35

L.1.1 TASK TREE

  • A task tree represents nested task objectives, with hierarchical termination ending descendant tasks and assigning exit rewards at task boundaries.The highest-level ancestor termination takes effect, terminating descendants and returning them to the ancestor above it.Source: §L.1.1 · pp. 33–34

L.1.2 EXECUTION TREE

  • Execution trees grant decision authority to active nodes, while SME binds interruption to task termination and ME makes interruption independent, potentially creating off-policy discrepancy.Under ME, authority can leave a task subtree without terminating the task, so subsequent behavior and target decisions can diverge.Source: §L.1.2 · p. 35, §L.1.3 · pp. 36–37

L.2.1 UNIFIED VALUE FUNCTION IN HRL

  • The unified value function evaluates expected return across arbitrary execution mechanisms and turns HRL into an extended Markov process over decision-stage state and authority.It also places goal-based and option frameworks under the same task-node representation.Source: §L.2.1 · pp. 37, 39

L.2.2 GENERALIZED HIERARCHICAL BELLMAN EQUATION

  • The generalized hierarchical Bellman equations evaluate values under arbitrary execution subtrees and optimize node policies for the return of their own or an ancestor task.The preparation-stage equation accounts for decision-authority jumps caused by interruption events.Source: §L.2.2 · p. 39
  • SME and ME produce distinct Bellman equation sets, HBE-SMDP and HBE-MDP, because execution mode changes the preparation stage.The framework defines policy trees from the corresponding HBOE-SMDP and HBOE-MDP solutions for comparing expected returns.Source: §L.2.2 · p. 40

L.3 GENERALIZED SMDP SUBOPTIMALITY THEORY

  • With other node policies fixed, HBOE-SMDP and HBOE-MDP yield SMDP- and MDP-optimal node policies; their returns satisfy JA ≥ JB and JC ≥ JD, with JB ≥ JC under task-subtree compatibility.Compatibility holds when the subtree has two levels or its descendant task nodes have the specified matching child-task sets; the passage’s condition is truncated.Source: §L.3 · p. 40
  • Uniform termination bounded away from zero gives the GHBE a unique fixed point, and bounded per-frame and exit rewards bound its value by 2M.The termination condition is 1 − γ_n(h)(s) ≥ ϵ > 0, and both reward magnitudes are bounded by M.Source: §L.3 · p. 40
  • The value-function space uses the maximum absolute difference over states and tasks as its metric.The functions are bounded and defined on the state space and the complete task space.Source: §L.3 · p. 41
  • Under Theorem 5.2’s conditions, the generalized operator is a contraction for each fixed execution tree.The proof applies the contraction result to the operator associated with the given execution choice.Source: §L.3 · p. 41
  • For any state and task, the difference between two values is bounded above by their metric distance.This inequality is used in the fixed-point argument.Source: §L.3 · p. 41
  • Successive iterations from any initial value converge to the operator’s unique fixed point.Corollary L.17 states convergence under Theorem L.16’s conditions.Source: §L.3 · p. 41
  • That fixed point is the unified HRL value for the given execution tree.The proof identifies the limit with the value of the corresponding execution subtree.Source: §L.3 · pp. 41–42
  • The fixed point satisfies the generalized hierarchical Bellman equation for executing the specified task with its execution subtree.The proof invokes Theorem L.13 to identify this fixed point with the unified value.Source: §L.3 · p. 42

L.3.1 STEP 1: HIERARCHICAL POLICY IMPROVEMENT THEOREM

The hierarchical policy improvement theorem shows that replacing a node policy with one whose expected child value is no lower improves the evaluated task value. Iterative node-policy updates converge to a unique GHBOE solution, with SME and ME hierarchical policy improvement as special cases.

L.3.1 STEP 1: HIERARCHICAL POLICY IMPROVEMENT THEOREM

  • A node-policy change that raises expected child value at a state weakly improves the evaluated task value at every state.The theorem compares execution trees differing only in that node policy, with other policies fixed.Source: §L.3.1 · p. 42
  • The policy-improvement result has separate SME and ME corollaries for policy trees that differ at one node and state.The two corollaries evaluate expected child values under their respective execution modes.Source: §L.3.1 · p. 42
  • Repeated updates to one node policy produce a monotonically nondecreasing, uniformly bounded value sequence that converges to a unique GHBOE solution.The resulting execution tree is unchanged by further GHBOE updates.Source: §L.3.1 · p. 43

L.3.2 STEP 2: HIERARCHICAL EXECUTION IMPROVEMENT THEOREM AND OPTIMAL EXECUTION THEOREM

The section proves that execution changes can improve hierarchical value and establishes conditions under which ME is optimal. It then specifies execution and policy-improvement procedures, including option- and goal-based implementations.

L.3.2 STEP 2: HIERARCHICAL EXECUTION IMPROVEMENT THEOREM AND OPTIMAL EXECUTION THEOREM

  • Changing only interruption functions improves value when the new decision-transition expectations satisfy the theorem’s pointwise dominance condition.Under Claim L.1, ME is optimal when the node policy is optimal for its original interruption subtree.Source: §L.3.2 · p. 44
  • The optimal-execution guarantee requires task-subtree compatibility; without it, ME can reduce value when descendant policies optimize rewards that conflict with the evaluated task.The text identifies Claim L.1 as a sufficient condition and describes counterexamples when it fails.Source: §L.3.2 · p. 45

M.1.2 PSIF-2S PSEUDOCODE

  • PSIF-2S changes behavior and target execution together in bottom-up stages, moving nodes from SME to ME as child policies are completed.The sampled task-exit boundary remains fixed while decision authority changes.Source: §M.1.2 · pp. 49–50

M.1.3 PSIF-1S PSEUDOCODE

  • PSIF-1S keeps SME behavior but uses ME targets within each optimized node’s subtree and SME targets outside it.The method keeps the task-exit index fixed and changes only the next decision authority; the paper says this helps mitigate off-policy issues.Source: §M.1.3 · p. 50

M.2.1 OPTION FRAMEWORK ALGORITHM

  • For options, PSIF-2S fixes completed option policies before the root enters its second stage and calls options using ME.PSIF-1S instead maintains separate upper and lower values; option termination uses an upper ME exit value while data collection remains SME.Source: §M.2.1 · p. 51

M.2.2 GOAL-BASED FRAMEWORK ALGORITHM

  • For goal-based methods with fixed-duration subgoals, augmenting each subgoal with elapsed time represents the remaining transitions during execution.The paper notes that upper-level estimates otherwise account only for a subgoal after full execution.Source: §M.2.2 · p. 52

N EXPERIMENT DETAILS AND ANALYSIS

The appendix describes stochastic Fourrooms and continuous-control settings, then compares HAC execution modes and reports experimental averaging details.

N.1 ENVIRONMENT SETTINGS

  • Fourrooms uses stochastic movement, while randomized AntReacher adds a 10% whole-map coordinate transition every 10 timesteps.In Fourrooms, the agent moves in its requested direction with probability 2/3 and otherwise moves in one of the other directions, each with probability 1/9.Source: §N.1 · p. 52

N.2 ALGORITHMS USED

  • ME performed at least as well as SME in same-policy HAC comparisons across UR5, AntReacher, and AntFourrooms without random transition events.The appendix cautions that other algorithms may not improve when switched to ME, particularly with a suboptimal, unconverged higher-level policy.Source: §N.2 · p. 54, Figure 24 · p. 54

N.3 HYPERPARAMETERS

  • HAC results are averaged over 10 random seeds, whereas OC results are averaged over 350 random seeds.The passage introduces these figures as the experimental averaging protocol.Source: §N.3 · p. 55

N.4 EXTRA RESULTS AND LIMITATIONS

In randomized AntReacher, SME can stall after a large coordinate shift, while ME can adjust the subgoal toward one the lower-level policy can reach.

N.4 EXTRA RESULTS AND LIMITATIONS

  • After a random transition at t = 10, the ant remained stagnant until t = 23 under SME; under ME, the higher-level policy adjusted the subgoal.The authors suggest the large coordinate offset may prevent effective lower-level actions toward the previous subgoal.Source: §N.4 · p. 55
Loading 2610.05338v1…