acceptodds
Withdrawn from ICLR 2027

On the Suboptimality of Semi-Markov Decision Process in Hierarchical Reinforcement Learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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.

Primary area:
learning theory
Keywords:
Hierarchical Reinforcement Learning, Reinforcement Learning Theory, Suboptimality, Semi-Markov Process

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_PH3AOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper argues that hierarchical RL bundles two separate things into one rule: what a subtask is trying to achieve, and how long a parent stays committed to it. Committing until a subtask ends helps exploration but loses performance. The authors split the loss into two parts. Execution suboptimality is failing to re-select subtasks at deployment. Policy suboptimality is having trained the policy for committed execution in the first place.

Contributions of the paper include (1) separate trees for task objectives and for execution, plus a unified value function and a four-stage Bellman recursion covering any hierarchy depth and execution mode, (2) policy- and execution-improvement theorems. Under a compatibility condition, an optimal-execution result shows that re-deciding every frame is best, and (3) three frameworks that set behavior, learning target, and deployment execution independently. ESIF changes deployment only. PSIF-2S trains bottom-up in stages. PSIF-1S keeps committed exploration while learning frame-wise targets.

The paper validated its claims: (1) a small GridWorld shows both losses exactly, (2) Option-Critic on Fourrooms, with controlled stochasticity, shows step reductions that depend on randomness strength and type, (3) HAC shows success-rate gains from ESIF, (4) a DAC continuation on HalfCheetah gives modest gains and (5) Theory assumes converged optimal policies, whereas the experiments use finite training.

Critical strengths
  1. The paper addresses a compelling and foundational question in hierarchical RL: identifying how semi-Markov commitment induces suboptimality. While prior work recognized the benefit of interrupting options, this work goes further by formally separating execution suboptimality from policy suboptimality and establishing an explicit loss decomposition.

  2. Decoupling the execution tree from the task tree provides a conceptually elegant abstraction. By separating decision interruption from task termination, the framework enables independent execution choices for behavior, training targets, and deployment without distorting underlying task objectives.

  3. The theoretical claims are well-supported across diverse settings, including option-based (OC, DAC) and goal-conditioned (HAC) architectures in discrete and continuous domains. Notably, the controlled stochasticity sweep effectively highlights how transition noise and spatial dynamics dictate the relative gains of execution versus policy improvements.

Critical weaknesses
  1. Key acronyms and frameworks (such as ESIF, PSIF, and OC) appear in the introduction before being spelled out or properly contextualized in later sections. Additionally, the notation in Section 2 is tightly packed and shifts between general node indices (n(i)n(i)), subtrees (x∣n(i)x\vert{}n(i)), and task nodes (τn(i)\tau_{n(i)}), making the formal exposition challenging to follow on a first read.

  2. Critical elements of the theoretical narrative—including formal definitions of SME and ME, detailed descriptions of the policy tree, and step-by-step proofs—are deferred to the supplementary material. Moving key conceptual definitions, particularly the formal mechanics of execution modes and policy-tree construction, into the main body would substantially improve clarity and self-containment.

  3. While the paper effectively motivates execution suboptimality through unexpected environmental stochasticity, the narrative would benefit from explicitly clarifying whether execution and policy suboptimality exhaust all potential sources of loss within a fixed task hierarchy. A clearer discussion contrasting this decomposition with representation-induced suboptimality or task-specification error would strengthen the conceptual foundation in Section 2.

Questions for authors

Could the authors elaborate on the advantages and trade-offs of formalizing hierarchical scheduling via explicit task and execution trees compared to alternative representations (such as call-stack augmented state spaces or programmatic automata)? Specifically, are there scalability, memory, or computational constraints when maintaining these tree structures in deeper hierarchies or environments with continuous subtask spaces?

Reviewer_aHb4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper separates two losses inside a fixed task hierarchy: execution suboptimality, from committing to a subtask until it terminates (SME) instead of re-deciding every frame (ME), and policy suboptimality, from optimizing the node policy for the SME objective and then deploying it under ME. It introduces task trees and execution trees, a value function indexed by both the evaluated task and the node holding decision authority (UVFH), and a four-stage Bellman recursion in which the execution mode enters only through an interruption function β^\hat{\beta}. It proves policy and execution improvement theorems, shows that ME is optimal under a task-subtree compatibility assumption, and derives the ordering JA≥JB≥JC≥JDJ_A \ge J_B \ge J_C \ge J_D with the decomposition ΔJ=(JA−JB)+(JB−JC)\Delta J = (J_A - J_B) + (J_B - J_C), illustrated by a GridWorld with returns −8/−11/−12/−14-8/-11/-12/-14. Three frameworks follow: ESIF (train with SME, deploy with ME), PSIF-2S (bottom-up two-stage) and PSIF-1S (SME behavior with local ME targets). Experiments use tabular Option-Critic on Fourrooms with two kinds of transition noise, HAC on goal-conditioned control, and DAC on HalfCheetah.

Critical strengths
  1. The conceptual separation is clean and useful. The 2×22 \times 2 table and the GridWorld example make both losses explicit: interruption alone recovers one of the four lost frames, retraining for ME recovers three more, and the ME-optimal policy run under SME is worse than the SME solution. Treating behavior, target and deployment execution as three independent choices is a good way to think about HRL training, and PSIF-1S (keep SME exploration, learn frame-level ME targets) is a practical payoff.

  2. The tabular OC study is carefully done. The same checkpoints are evaluated under SME and ME with shared seeds, Fig. 6 reports paired SEM, and Table 2 reports all twelve settings including the non-monotone ones. The paper is honest about what it does not claim.

Critical weaknesses
  1. In the two-level case, which is the only case any experiment uses, Theorem 2.4 and the JB≥JCJ_B \ge J_C half of Theorem 2.5 are the interruption theorem of Sutton, Precup and Singh (1999, Thm. 2) applied to the SMDP-optimal policy. That paper already describes ME as "interrupt on every step and switch to the greedy option (as in polling execution)" and points to Dietterich's MAXQ, whose hierarchical greedy execution and hierarchical vs recursive optimality are the natural precedents for both losses here. The main text cites neither, and Appendix I says Sutton et al. "only identifies execution suboptimality", which understates that result. JA≥JBJ_A \ge J_B and JC≥JDJ_C \ge J_D are just the definition of optimality under each mode. So the new theory is the multi-level generalization under Assumption 2.3. For that, the proof of Theorem L.22 (p. 45) has a step I could not follow: the third line replaces the maximum of V(s,τn(h+1))V(s, \tau_{n(h+1)}) over the children of n(h^)n(\hat{h}) by the maximum of V(s,τn(h^+1))V(s, \tau_{n(\hat{h}+1)}) over the same children, i.e. it treats the value of the same task placed at depth h+1h+1 and at depth h^+1\hat{h}+1 as equal. Under the paper's own definitions the extended state is indexed by the execution node, authority returns to a different parent after the task ends, and a deep task is also cut off when an intermediate ancestor terminates, so I do not see why these are equal, and no lemma is given. Appendix F calls this theorem the core theoretical contribution, so this matter for my score. Also, Assumption 2.3 excludes standard layered hierarchies with different task sets per level, so "arbitrary depth" in the abstract is stronger than what is proved. I may be missing something and would be glad to be corrected.

  2. The empirical evidence is thinner than Table 1 suggests.

    (a) Checkpoints are evaluated with an ϵ\epsilon-greedy selector, ϵ=0.1\epsilon = 0.1, for both SME and ME (App. B.1). A random option is committed to until termination under SME but lasts one frame under ME, so part of the "execution" gain may be an evaluation artifact; no greedy evaluation is reported.

    (b) The headline −60.6%-60.6\% has a reference of 41.8±35.141.8 \pm 35.1 over ten policy indices, so a few bad indices drive it, and Table 1 shows only p=1/3p = 1/3, where the slip effect is largest (Table 2 gives about −10%-10\% at the other pp for several settings).

    (c) The +46.7%+46.7\% on "random AntReacher" comes from a random transition added only at deployment (App. N.1), which the main text does not say; on HAC's three original tasks the gains are 2-3 points, and the DAC changes are within noise with no paired test.

    (d) App. C.1 says the PSIF-1S runs add a "deliberation term" to the termination update that is not defined, cited, or used by the baseline, so I cannot tell how much of the PSIF-1S gain comes from it.

    (e) The 2×22 \times 2 decomposition is never measured on learned policies; Table 2 has no PSIF-under-SME column.

Questions for authors
  1. Please justify the third equality in the proof of Theorem L.22, or restate the theorem for the case it covers. Theorem L.21 is also stated for one node and one state but used for all descendants at all states.
  2. Please relate Theorems 2.2/2.4 to Sutton et al. (1999, Thm. 2) and to MAXQ's hierarchical greedy execution in the main text, and scope the "arbitrary depth" claim.
  3. Please report the SME vs ME checkpoint comparison with a greedy selector (ϵ=0\epsilon = 0).
  4. For Table 1, please give medians or paired per-index differences and all three pp values.
  5. What is the deliberation term (definition, value, citation)? Please report the baseline with the same term, or PSIF-1S without it.
  6. Please add a PSIF-under-SME column to Table 2, and confirm that random AntReacher was trained without the perturbation.
Reviewer_QyivOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper identifies two distinct HRL suboptimalities (loss of expected return at deployment): committing to a subtask too long, and learning a policy optimized for such commitment. It assumes the task ontology is given by a predefined hierarchy and uses several trees to present the task structure and semantics. Based on that, it provides a unified hierarchical value function, then derives conditions under which per-step subtask reselection improves return. Then, it proposes either keeping the learned subtask policies unchanged and reselecting subtasks every step at deployment (ESIF), or changing value targets so policies learn to perform well under such reselection (PSIF).

Critical strengths

The study on commitment is interesting, and it is indeed a fundamental problem in HRL.

Critical weaknesses

Major:

  1. The first and foremost: Many abbreviations are used without spelling them out, e.g., OC, HAC, without proper citations either (many important citations first appear in the appendix). For example, for OC, you can only find the full name in Appendix. E.g., I may assume it's option-critic, but there are many other terms with the abbreviation "OC". Things like ESIF and PSIF appear in the introduction before their full names are given. People without an HRL background will completely get lost. Some terms, like I would suggest adding a termination table, could be helpful.
  2. Similar to the first point, many terms are used before definition or never defined as if they are well-defined, and the logical connections between sentences and paragraphs are loose in general. I believe all of these call for a major revision, which makes this work not ready for publication.
  3. In intro or later section, I don't find sufficient discussion about previous related work (deferred to Appendices C.2 and I), making readers hard to distinguish the contribution made by the authors and the existing contribution. Many statements are made as if they are completely new and not relevant to existing works. The whole intro is not like an intro: only 2 papers are cited, little motivation is provided, and it goes to technicalities too quickly. Moreover, those two papers are not just saying "temporal abstraction gives HRL the ability to explore better" but also more efficient learning and planning (and exploration is one of the causes). You may also want to make your motivation clearer by introducing an example of why committing to some subtask too long will lead to suboptimality.
  4. Overall, the discussion is blurring the boundaries of environment and agent -- which is very confusing. E.g., options are often agent-side constructs, but your termination functions are always on the env side. It's okay to do that, but a clear background section that clarifies everything would help a lot.
  5. Sec 2: UVFH is defined without enough motivation. For the trees, it's confusing which parts are predefined by the problem and which parts are learned. And the two-level instance of UVFH is very similar to what has been discussed in interruption (theorem 2), but the discussion is very little.
  6. Sec 3 resonates a lot with the paper "Learning with Options that Terminate Off-Policy" by Harutyunyan et al. They also do decoupling of the behavior and target terminations, which is close to your PSIF-1S.
  7. For the experiment, it would be greatly enhanced by clearly justifying the choice of baselines. For example, the off-policy paper by Harutyunyan can also be compared. It also has little evidence for the multilevel contribution. In addition, DAC's hyperparam setting is missing even in appendix and the list provided in appendix does not seem complete either. And why are you using different # of seeds for DAC and HAC?

Minor:

  1. The "task-specific MDP" defines one task, but it does not by itself specify the hierarchical control problem studied in the paper. It can be somewhat completed by the task-tree formulation, but the narration is somewhat poor. Why not first say that, we want to solve a task that can be formulated as an MDP for its dynamics, and as a tree in terms of its hierarchy? And put those things together in sec.2, not separately.
  2. The two suboptimalities, to me, can be introduced in a much better way. In the paper "Discovering Temporal Structure: An Overview of Hierarchical Reinforcement Learning" by Klissarov et al., sec.8.1 talks about non-stationarity (that a high-level policy would face), which could be the main cause of that problem.
  3. Many presentation issues exist. I don't want to expand on this because of the succinctness requirement.
Questions for authors
  1. Can you fix all the abbreviation issue, and make the whole paper easier to read?
  2. Can you talk about the connection of previous work, so that your contribution can be more clearly stated? E.g., your UVFH to Dietterich’s MAXQ which seems closely related. Wen et al., 2020 (you've cited) also used the subMDP formulation. Please also discuss the work from Sutton et al., 1999 on the relationship between your UVFH and Harutyunyan et al.'s aforementioned off-policy paper.
  3. Can you reorganize the paper so that not all the important explanation and discussion is in appendix?
  4. The proposed methods rely heavily on per-step subtask reselection. However, one motivation for temporal abstraction in HRL is to trade some policy flexibility for computational efficiency by reducing higher-level decision frequency (Klissarov et al. 2025, sec.3.2). Could the authors briefly discuss this tradeoff and whether the performance gains justify the additional computation?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.