On Semi-Markov Suboptimality in Hierarchical Reinforcement Learning

Bingyun Liu; Yuheng Jing

cs.LGOct 4, 2026

On Semi-Markov Suboptimality in Hierarchical Reinforcement Learning

Authors: Bingyun Liu, Yuheng Jing

Organizations: Institute of Automation Chinese Academy of Sciences

Abstract

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.

Figures & tables

Figure 1: Decision state is not the task whose return is evaluated. The extended-state coordinate records the current decision position; the condition specifies the reward objective and exit boundary. Decision authority moves down the tree within a frame while the environment state and conditioning task stay fixed. The two node labels can coincide, but their roles are distinct.

Figure 2: GHBOE separates optimization, task exit, and decision interruption. Only

\hat{\pi}_{n(h)}

is optimized; the other node policies are fixed. Termination adds the weighted survival and exit contributions, but only survival continues through preparation. The fixed condition

\tau_{n(h)}

and execution-subtree subscript, shared by all four stages, are suppressed inside the boxes; transition probabilities are evaluated at

s^{\prime}

Figure 3: PSIF-2S matches behavior and target execution as training progresses up the tree. In this mixed-stage snapshot, the highlighted node is in Stage 2 and its children are fixed, while its parent remains in Stage 1. Each caller’s stage sets its outgoing calls. Deployment uses ME after training is complete.

Figure 5: Learning behavior with eight options: local slip (

p=1/3

) and global teleportation (

p=1/2

). Lines use a trailing 20-episode mean; bands show one SD across saved 35-seed batch curves (ten batches; nine for teleportation NaiveME). The dotted line marks the two-stage switch. Off-scale NaiveME reports its episode-901–1000 mean

\pm

SD across batch-window means. Initial transients may exceed the focused vertical range.

Figure 6: Execution and policy savings depend on the transition kernel. Positive values mean fewer steps: baseline SME minus ME (execution), or Baseline(ESIF) minus PSIF under ME (policy). Means use checkpoints 910–1000; bands show one SEM across ten policy indices, each evaluated for 35 episodes per checkpoint. These are empirical step differences, not discounted optimal-value gaps.

Algorithm / environment	Change	Reference	Modified	Effect
OC / Slip (4 opts.) $\downarrow$	PSIF-1S	$41.8\pm 35.1$	$16.5\pm 1.8$	$-60.6\%$
OC / Slip (8 opts.) $\downarrow$	PSIF-1S	$23.4\pm 3.2$	$16.8\pm 2.1$	$-28.4\%$
OC / Teleport (4 opts.) $\downarrow$	PSIF-1S	$110.2\pm 29.9$	$72.7\pm 17.3$	$-34.0\%$
OC / Teleport (8 opts.) $\downarrow$	PSIF-1S	$104.8\pm 18.5$	$69.1\pm 11.6$	$-34.1\%$
HAC / random AntReacher $\uparrow$	ESIF	$49.1\pm 5.9$	$72.1\pm 2.9$	$+46.7\%$
HAC / UR5 $\uparrow$	ESIF	$73.1\pm 4.4$	$76.3\pm 4.1$	$+4.3\%$

Table 1: Effects across algorithm families; arrows mark the preferred direction. OC: ME steps (

p=1/3

, 910–1000 ep), mean

\pm

SD over ten policy-window means. HAC: success rate (%), mean

\pm

SD across 10 seeds, averaged over the final five plotted checkpoints. DAC: final

0.1

M-step return, mean

\pm

SD over 50 seeds; full second-stage comparison in Appendix B.3 . Effects are relative changes (%).

Appendix figures & tables29 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: OC on Fourrooms: all six local-slip learning curves, with four options in the upper row and eight in the lower row. Curves apply a trailing 20-episode mean to each saved worker-batch trajectory; bands are one sample standard deviation across the smoothed batch trajectories. The dotted line marks the two-stage switch at episode 500. Focused vertical scales can clip the initial transient. Off-scale NaiveME labels report the unsmoothed episode-901–1000 mean $\pm$ SD across worker-batch window means. Legends and off-scale labels are outside the plotting areas.

Figure 8: OC on Fourrooms: all six global-teleportation learning curves, with the same conventions as Figure 7 . At $p=1/2$ , NaiveME is included directly in the plotting range; its nine saved worker batches are retained without imputation.

Environment	Opts.	$p$	Baseline SME	Baseline ME	1Stage ME	2Stage ME
Slip	4	$1/6$	$31.4\pm 24.6$	$22.7\pm 14.7$	$20.5\pm 16.6$	$20.3\pm 13.5$
Slip	4	$1/3$	$48.8\pm 38.8$	$41.8\pm 35.1$	$16.5\pm 1.8$	$34.0\pm 27.2$
Slip	4	$1/2$	$57.0\pm 16.8$	$47.7\pm 14.1$	$32.3\pm 21.5$	$40.9\pm 13.7$
Slip	8	$1/6$	$17.5\pm 3.0$	$15.2\pm 2.5$	$11.9\pm 0.5$	$12.6\pm 0.7$
Slip	8	$1/3$	$28.9\pm 4.4$	$23.4\pm 3.2$	$16.8\pm 2.1$	$18.0\pm 2.2$
Slip	8	$1/2$	$47.8\pm 12.2$	$38.1\pm 7.9$	$34.1\pm 17.9$	$30.0\pm 5.7$

Appendix

Table 2: Complete OC checkpoint evaluation on Fourrooms at episodes 910–1000: mean

\pm

sample SD of the ten policy-window means (steps, lower is better). Within each checkpoint, each saved policy is evaluated for 35 episodes.

Figure 9: Second-stage DAC comparison with two and eight options. Learned-termination and ME continuations start from the shared

3

M-step checkpoint. Curves show the observed

3

M–

4

M segment in 20,000-step bins; bands are one standard error across 50 runs. Their summary statistics are given in Table 3 .

Options	SME return $\uparrow$	ME return $\uparrow$	Effect
2	$2257\pm 506$	$2269\pm 607$	$+0.54\%$
8	$2111\pm 698$	$2268\pm 636$	$+7.41\%$

Appendix

Table 3: DAC second-stage comparison on HalfCheetah for the valid two- and eight-option settings. Returns use the final

0.1

M steps: mean

\pm

sample SD over 50 paired seeds. Effects are relative changes (%).

Figure 10: PSIF-2S changes the training schedule; PSIF-1S separates behavior from the target. In PSIF-2S, behavior and target modes describe the current node’s calls to its children, not a global switch. The schedule propagates bottom-up. PSIF-1S keeps SME behavior and updates node-local ME targets throughout training. Both apply at arbitrary depth and deploy with ME.

Framework	Behavior	Target	Deployment	Endpoint
Baseline	SME throughout	SME throughout	SME	$J_{\mathcal{C}}$
ESIF	SME throughout	SME throughout	ME	$J_{\mathcal{B}}$
PSIF-2S	Node-local SME $\to$ ME	Same node-local modes as behavior	ME	$J_{\mathcal{A}}$
PSIF-1S	SME throughout	ME within the updated subtree; SME outside it	ME	$J_{\mathcal{A}}$

Appendix

Table 4: Execution rules for hierarchies of arbitrary depth. In PSIF-2S, the stage is local to each task node. In PSIF-1S, the target is specific to the node being optimized. Endpoints denote the conditional idealized comparisons, not finite-training guarantees.

Figure 11: Differences between MDP and SMDP: calling actions vs. calling subtasks. The superscript of

\tau

denotes its hierarchical level, while the subscript denotes its called index

\hat{t}

. The subscript of actions

a

indicates the timestep index

t

Figure 12: Interaction differences between SME and ME: calling subtasks in full vs. calling subtasks in one timestep. Task

\tau

has a 4-timestep subtask

\tau 0

and a 2-timestep subtask

\tau 1

. Both

\tau 0

and

\tau 1

directly call actions. The subtask

\tau 0

and the actions it decides are represented in blue, while

\tau 1

and its actions are represented in yellow.

Panel of Figure 13 — Figure 13: Trajectories of the agent in the GridWorld under different policies and execution modes. The agent needs to reach $G$ at $(0,8)$ from $S$ at $(4,0)$ in the minimum number of frames, receiving a reward of $-1$ per frame. After reaching the position marked $\otimes$ , there is a 50% chance of an additional state transition along the dashed line. The trajectories of the SMDP-optimal policy $\hat{\pi}_{hi}^{-}$ under SME and ME are shown in blue and red, with their expected returns denoted by $J_{\mathcal{C}}$ and $J_{\mathcal{B}}$ respectively. The trajectories of the MDP-optimal policy $\hat{\pi}_{hi}^{*}$ under SME and ME are shown in purple and orange, with their expected returns denoted by $J_{\mathcal{D}}$ and $J_{\mathcal{A}}$ respectively. The detailed descriptions of the policies and execution modes, as well as the related numerical computations, are provided in the Appendix K

Expected return	SME	ME
SMDP-optimal policies	$J_{\mathcal{C}}$	$J_{\mathcal{B}}$
MDP-optimal policies	$J_{\mathcal{D}}$	$J_{\mathcal{A}}$

Appendix

Table 5: Optimality comparison table.

Figure 14: Subtask off-policy issue under ME. Following the example in Figure 1, the bottom row of the action sequence represents the agent’s interaction trajectory with the environment, where blue and yellow colors are used to distinguish whether an action is decided by the node policy of subtask

\tau 0

\tau 1

respectively. Within each subtask box, the action sequence corresponds to the truncated trajectory used for training that subtask. Whenever the truncated trajectory contains data that is not decided by the node policy of the corresponding subtask, or when trajectory data is missing, these actions are highlighted in red, indicating the occurrence of an off-policy issue.

Panel of Figure 15 — Figure 15: Results of the improvement frameworks. (a) Verification of execution suboptimality. (b) Verification of policy suboptimality. The shaded regions represent one standard deviation over results obtained with multiple random seeds. Higher success rates and fewer steps are better.

Symbol	Description
$\mathcal{S}$	State space
$\mathcal{A}$	Action space
$T:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$	Transition kernel of MDP
$R_{\tau}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$	Per-frame reward function of task $\tau$
$\hat{R}_{\tau}:\mathcal{S}\times\mathcal{T}^{\prime}_{\tau}\to\mathbb{R}$	Exit reward function of task $\tau$
$\alpha_{\tau}\in\Delta(\mathcal{S})$	Initial state distribution of task $\tau$

Appendix

Table 6: Notations used in this paper.

Figure 16: GridWorld.

Figure 17: Execution Suboptimality.

$s$	(4,0)	(3,0)	(2,0)	(1,0)	(0,0)	(0,1)
$g$	(0,1)	(0,2)	(0,3)	(0,4)	(0,5)	(0,6)
$V(s)$	-11	-10	-9	-8	-8	-7
$s$	(0,2)	(0,3)	(0,4)	(0,5)	(0,6)	(0,7)
$g$	(0,7)	(0,8)	(1,8)	(2,8)	(3.8)	(4,8)
$V(s)$	-6	-5	-4	-3	-2	-1

Appendix

Table 7: The mapping of

\hat{\pi}_{hi}

and its value estimation under ME.

Figure 18: Policy Suboptimality.

$s$	(4,0)	(5,0)	(5,1)	(5,2)	(5,3)	(5,4)	(5,5)
$g$	(5,4)	(5,5)	(1,0)	(2,0)	(5,8)	(4,8)	(3,8)
$V(s)$	-8	-9	-8	-9	-10	-9	-8
$s$	(5,6)	(5,7)	(5,8)	(4,8)	(3,8)	(2,8)	(1,8)
$g$	(2,8)	(1,8)	(0,8)	(0,7)	(0,6)	(0,5)	(0,4)
$V(s)$	-7	-6	-5	-4	-3	-2	-1

Appendix

Table 8: The mapping of

\hat{\pi}^{*}_{hi}

and its value estimation under ME (right-hand path).

$s$	(4,0)	(3,0)	(2,0)	(1,0)	(0,0)	(0,1)
$g$	(5,4)	(5,3)	(0,3)	(0,4)	(0,5)	(0,6)
$V(s)$	-8	-9	-9	-8	-8	-7
$s$	(0,2)	(0,3)	(0,4)	(0,5)	(0,6)	(0,7)
$g$	(0,7)	(0,8)	(1,8)	(2,8)	(3.8)	(4,8)
$V(s)$	-6	-5	-4	-3	-2	-1

Appendix

Table 9: The mapping of

\hat{\pi}^{*}_{hi}

and its value estimation under ME (left-hand path).

Figure 19: SME interaction process.

Figure 20: ME interaction process.

Figure 21: Off-policy issue in subtask node policy learning under ME.

Figure 22: Counterexample: The red and blue colored arrows represent the SMDP-optimal policies for each task node, while the numbers inside the circles indicate the state-task values at the current frame when SME executes

\tau_{n(h)}

. In this example, no task termination events occur. Gray nodes denote the actions taken by the agent in the previous frame; the blue nodes form the decision path of the current frame if SME is used, and the red nodes form the decision path of the current frame if ME is used.

Frame- work	Execution Mode (Deployment)	Execution Mode of Behavior Policy (Training)	Execution Mode of Target Policy (Training)	Training Requirement	$J$	Limitation
HRL Baseline	SME	All node policies called by SME	All node policies called by SME	On-policy	$J_{\mathcal{C}}$	Execution and policy suboptimality exist
ESIF	ME	All node policies called by SME	All node policies called by SME	On-policy	$J_{\mathcal{B}}$	Policy suboptimality exists
PSIF-2S	ME	Each node calls children by SME in its Stage 1, by ME in its Stage 2	Same node-local execution modes as behavior; completed nodes retain ME	On-policy	$J_{\mathcal{A}}$	Subtask support problem exists
PSIF-1S	ME	All node policies called by SME	For each optimi- zed node policy, its descendants called by ME, others by SME	Off-policy	$J_{\mathcal{A}}$	Off-policy issue exists

Appendix

Table 10: Comparison of HRL Improvement Frameworks

V(s_{t},a_{t}|\tau_{n(h^{\prime})})\leftarrow r_{t+1}+\mathbb{I}_{-1\leq j<h^{\prime}}\hat{R}_{n(h^{\prime})}(s_{t},\tau_{n(j)})+\mathbb{I}_{h^{\prime}\leq j}V(s_{t},\tau_{n(j)}|\tau_{n(h^{\prime})})

Appendix

Algorithm 2 ESIF Training Pseudocode

V(s_{t},a_{t}|\tau_{n(h^{\prime})})\leftarrow r_{t+1}+\mathbb{I}_{-1\leq j<h^{\prime}}\hat{R}_{n(h^{\prime})}(s_{t+1},\tau_{n(j)})+\mathbb{I}_{h^{\prime}\leq j}V(s_{t+1},\tau_{n(k)}|\tau_{n(h^{\prime})})

Appendix

Algorithm 4 PSIF-1S pseudocode

Figure 23: The ant robot navigates from a random starting position to a random ending position in the AntReacher environment. The yellow sphere on the map refers to the ending position, the red sphere refers to the subgoal proposed by the agent’s higher-level policy, and the lower-level policy directly controls the ant’s joints for moving towards this subgoal.

Panel of Figure 24 — Figure 24: Comparisons for HAC under SME and ME: (a) UR5 (top), (b) AntReacher (middle), and (c) AntFourrooms (bottom).

Explore similar work

Jul 31, 2026cs.LG

Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification

We present HBPI-UCRL, a model-based algorithm for hierarchical reinforcement learning (HRL) that learns high-level and low-level policies in parallel. HBPI-UCRL exploits the fact that a high-level transition corresponds to a multi-step transition at the low level. We introduce two conditions on the low-level dynamics that are sufficient to make parallel HRL learnable. When these conditions hold, we prove that HBPI-UCRL has a polynomial sample complexity in the problem parameters. In the sparse-reward, goal-directed setting, our sample complexity upper bound for HBPI-UCRL is strictly lower than that of its non-hierarchical counterpart, providing theoretical justification for the empirical success of HRL.

Anders Jonsson, Emilie Kaufmann, Gianmarco Tedeschi +1

Department of Engineering Universitat Pompeu Fabra · Univ. Lille, CNRS, Inria Centrale Lille, UMR 9189-CRIStAL · Dept. Electronics, Information, and Bioengineering Politecnico di Milano

Hierarchical Reinforcement Learning Optimal Sample Complexity

Ask PDF

May 16, 2026cs.LG

Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning

The combination of exponentially large action spaces, stochastic dynamics, and long-horizon decision-making under limited resources makes Sequential Stochastic Combinatorial Optimization (SSCO) particularly challenging for reinforcement learning. Hierarchical Reinforcement Learning (HRL) offers a natural decomposition, but it places the high-level policy in a Semi-Markov Decision Process (SMDP) where actions have variable durations, making it difficult to learn a world model that is suitable for planning. We introduce a model-based hierarchical framework for sequential stochastic combinatorial decision-making that directly addresses this issue. Our method combines a latent-space tree-search planner with an SMDP-aware world model for variable-duration decisions. A multi-timescale objective structures the latent dynamics so that transition magnitudes reflect the effective temporal scales of abstract actions, enabling efficient lookahead under adaptive temporal abstraction. We further learn a subgoal-conditioned budget policy jointly with the world model to support context-aware resource allocation. Across challenging SSCO benchmarks, our method outperforms strong baselines.

Vivienne Huiling Wang, Tinghuai Wang, Joni Pajarinen

Department of Electrical Engineering and Automation, Aalto University, Finland · Qutwo, Finland

Hierarchical Reinforcement Learning Low-Latency Latent Planning Classical Planning Timescale

Ask PDF

Jul 21, 2026cs.LG

S3: Stable Subgoal Selection by Constraining Uncertainty of Coarse Dynamics in Hierarchical Reinforcement Learning

Hierarchical Reinforcement Learning (HRL) intends to separate strategic planning from primitive execution. It has been widely successful in solving long-horizon and complex tasks, where flat-RL algorithms have difficulty in learning. However, while the low-level agent in HRL benefits from dense feedback and abundant trial opportunities, the high-level agent receives sparse, delayed feedback from the environment and its performance depends on the low-level execution capability. In this paper, we study whether subgoal selection by the high-level agent can be performed more strategically, by providing it with dynamics-aware intrinsic motivation. Since motivation based on primitive transition dynamics would require broad coverage of the state-action space, we propose to use coarse dynamics, i.e., environment transitions aggregated over multiple steps at the temporal scale at which the high-level agent operates. This approach stabilizes the high-level policy by learning to minimize the predictive uncertainty associated with the coarse dynamics, and provides a guided structure for navigation. We model the predictive uncertainty by evaluating different dispersion metrics as approximated by a Mixture Density Network (MDN). Empirically, we observe that a dense, dynamics-aware intrinsic reward leads to risk-averse subgoal selection, enabling it to outperform state-of-the-art HRL methods in non-stationary long-horizon environments.

Kshitij Kumar Srivastava, Kshitij Jerath

University of Massachusetts, Lowell United States

Hierarchical Reinforcement Learning High-Level Subgoal Generation Non-Stationarity

Ask PDF