acceptodds
Under review as a conference paper at ICLR 2027

Hierarchical Reinforcement Learning with Multi-Level State-Action Abstraction

Abstract

State and action abstractions can help reinforcement learning agents scale to complex environments. State abstraction groups states that can be treated equivalently, action abstraction allows agents to act with temporally extended behaviours, and combining the two at multiple levels of abstraction enables agents to learn over compact representations of an environment. Theoretical foundations exist for hierarchical state-action abstractions, but discovering such hierarchies and learning over them are open problems. We address both, proposing a temporal-difference learning architecture for multi-level state-action abstractions, with a restricted bootstrap rule that prevents value estimates at more abstract layers from biasing learning at less abstract ones. The architecture is agnostic to the discovery method, requiring only a hierarchy of nested state partitions. We construct hierarchies using graph partitioning methods. We find learning with the architecture is more sample-efficient than with the corresponding action-only abstraction in most cases, and is competitive with or better than established option discovery methods.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, hierarchical reinforcement learning, skill discovery, state abstraction, action abstraction

Reviews

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

This paper presents an approach for learning a hierarchy of options, one for each level of a state abstraction hierarchy. The authors evaluate this approach with multiple state abstraction methodologies. Their primary contribution, however, is in designing the update rules for learning policies for hierarchical options at layer i in terms of the options generated at layer i-1.

Critical strengths
  • Good empirical evaluation of how the choice of state abstractions and option construction methods affects agent performance.

  • The paper addresses a clear open problem in the community.

Critical weaknesses
  • The main conclusion that learning state abstractions is useful is not surprising, and is well known in the community

  • Analysis of results mostly summarizes the empirical results, without shedding light on the reasons behind the observations. For instance, why do eigenoptions do well only in the London-streets domain?

  • The test domains appear to be limited to discrete settings. It is not clear how these methods would extend to realistic settings where the entire transition graph may not be available for learning state abstractions.It is not clear how these methods would apply to image-based or robotics problems high-dimensional input.

Questions for authors
  • Which of the domains include stochastic actions?
  • Can you describe the nature of stochasticity (action transition probabilities)
  • How does this approach compare with recent methods for learning abstractions, e.g:
  1. Sinclair, Sean, et al. "Adaptive discretization for model-based reinforcement learning." NeurIPS 2020.
  2. Allen, Cameron, et al. "Learning markov state abstractions for deep reinforcement learning." NeurIPS 2021.
  3. Wang, Zizhao, et al. "Causal dynamics learning for task-independent state abstraction." ICML 2022.
  4. Nayyar, Rashmeet et al. "Context-sensitive abstractions for reinforcement learning with parameterized actions." AAAI 2026.
5 comments

We thank you for taking the time to read our paper and leave thoughtful comments in your review. We hope that our response below answers your questions. We are updating the submission based on the reviews, and will upload a revised version during the discussion period.


Weakness (1). The main conclusion that learning state abstractions is useful is not surprising, and is well known in the community.

Please note that the usefulness of state abstraction is part of our motivation, not our conclusion. The main motivation for our paper is fully autonomous learning in large, complex environments: an agent learning from its own experience, with no human guidance. Abstraction is an essential ingredient of this, and the importance of both state and action abstraction is widely recognised. In reinforcement learning, action abstraction is well established through the options framework. Yet no existing method autonomously discovers, and learns with, a hierarchy of state-action abstractions. This is exactly the contribution of our paper, offering a concrete and significant step forward in this exciting field.

We develop (1) a novel practical method for constructing multi-level state-action abstractions, and (2) a novel temporal-difference learning architecture for learning with them. Our experiments compare the proposed approach against agents using alternative action-only abstractions, as well as no abstraction at all.

Central to our proposed learning architecture is a novel restricted bootstrapping rule, which prevents value estimates from more abstract layers from biasing learning at less abstract layers. Importantly, the ablation (Appendix E.3) demonstrates that combining state and action abstractions is not trivial: without the proposed restricted bootstrapping rule, learning performance can degrade substantially, even compared to agents using only primitive actions. Therefore, our contribution is not simply demonstrating that state-action abstraction is useful but also identifying important challenges in learning with such abstractions and developing practical methods for addressing them.


Weakness (2). Analysis of results mostly summarizes the empirical results, without shedding light on the reasons behind the observations. For instance, why do eigenoptions do well only in the London-streets domain?

We are happy to elaborate on potential causes of the performance differences observed in our experiments below, and will expand on these explanations in the revised manuscript.

The most important comparison reported in our main experiments is between the proposed state-action abstraction (Louvain (ϕ,O)(\phi,O)) and its corresponding action-only abstraction (Louvain (O)(O)), which use exactly the same set of options. We find that state-action abstraction improves sample efficiency in most environments, with the benefits increasing as the state space grows. Intuitively, this is because state abstraction allows the agent to generalise option values across states within the same abstract region, whereas action-only abstraction requires the agent to learn separate values in each ground state. In this way, the state-action abstraction allows the agent to improve its value estimates for an entire region of the state space using the experience that an action-only abstraction would use to update only the visited ground states. Furthermore, the restricted bootstrap rule ensures that the value estimates at more abstract levels of the hierarchy do not bias the learning at lower levels.

We include the performance of agents using action-only abstractions produced by alternative methods, such as the eigenoptions approach of Machado et al. (2017), primarily to serve as established reference points against which to compare the performance achieved by agents using the proposed state-action abstraction. These baselines are not subjects of deeper investigation in our paper, as such an investigation would not be directly relevant to the research questions we consider.

On the specific example you raise: eigenoptions perform well in Taxi, but fail to demonstrate any meaningful learning in Towers of Hanoi, Office, and London Streets within the training budget. These results are consistent with the variable performance of eigenoptions observed in prior work (e.g., Evans and Şimşek, 2023). The reasons behind their uneven performance is not a subject of our paper.

Weakness (3). The test domains appear to be limited to discrete settings. It is not clear how these methods would extend to realistic settings where the entire transition graph may not be available for learning state abstractions. It is not clear how these methods would apply to image-based or robotics problems with high-dimensional input.

The method does not require the state transition graph in advance. Our incremental results (Figure 6) demonstrate that the state-action abstractions can be discovered online in tabular settings, when the transition graph is unknown to the agent, and still substantially improve learning.

We address extension to very large or continuous state spaces in the discussion (lines 467-479). Specifically, we suggest it requires three distinct components:

  1. A partitioning method that is applicable to very large or continuous state spaces. This is an open line of research (e.g. Mendonça, Ziviani and Barreto, 2018; Hoang et al., 2021; Baek et al., 2025), and any progress in this area would be useful to other discovery methods that partition the state transition graph (e.g. Evans and Şimşek, 2023).
  2. Ground layer value estimates represented with function approximation, learned online from the task reward. Value-based deep reinforcement learning (e.g. DQN; Mnih et al., 2015) is an obvious candidate.
  3. Layer 1 option policies represented with function approximation, each trained to reach its target abstract state, using a pseudo-reward rather than the task reward. This is a separate policy-learning problem, to which value-based or gradient-based deep reinforcement learning methods could be applied.

Above the ground layer, the architecture is discrete by nature, and so value estimates at these layers can remain tabular. Combining these components into an effective architecture is an important open problem, one that requires considerable research effort and analysis, and we leave it to future work.

The tabular scope is the most suitable for introducing the proposed method and demonstrating its feasibility and potential. It supports in-depth ablations, isolating the effect of the abstraction and learning rule from function-approximation error, so that differences in our comparisons are attributable to the learning architecture and joint state-action abstractions.


Question 1. Which of the domains include stochastic actions?

Question 2. Can you describe the nature of stochasticity (action transition probabilities)?

None of the environments used in our evaluation have stochastic transitions. But both our abstraction discovery approach and our learning architecture apply naturally to stochastic domains.

We use graph partitioning methods applied to the interaction graph, where edge weights can represent transition probabilities. Both partitioning methods used in the paper (Louvain and spectral clustering) accept weighted graphs and so can be applied to stochastic transition dynamics.

Our learning architecture uses sample-based temporal-difference updates that are naturally compatible with learning in stochastic MDPs. Under the restricted bootstrap rule, the ground layer update is standard Q-learning, so ground-layer values converge to optimal values under standard conditions (Remark 1).


References:

Baek, S., Park, T., Park, J., Oh, S. and Kim, Y. (2025). Graph-assisted stitching for offline hierarchical reinforcement learning. ICML.

Evans, J.B. and Şimşek, Ö. (2023). Creating multi-level skill hierarchies in reinforcement learning. NeurIPS.

Hoang, C., Sohn, S., Choi, J., Carvalho, W. and Lee, H. (2021). Successor feature landmarks for long-horizon goal-conditioned reinforcement learning. NeurIPS.

Mendonça, M.R.F., Ziviani, A. and Barreto, A.M.S. (2018). Abstract state transition graphs for model-based reinforcement learning. BRACIS.

Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature.

Question 3. How does this approach compare with recent methods for learning abstractions (e.g., [1-4])?

In each of these works, the agent represents each part of the state space at only one resolution, replacing the original ground problem, and none of the abstractions use temporally extended abstract actions. Our approach differs on both counts: we discover a multi-level hierarchy, in which every state has an abstract representation at every layer, and whose abstract actions are options. Options may span many steps, so a single decision moves the agent further through the state space, and a single update propagates value further back along the trajectory. We learn values across every layer, including the ground layer, so any behaviour possible in the underlying problem remains possible.

Sinclair et al. (2020) propose an algorithm for online reinforcement learning in environments with continuous state and action spaces. They recursively split the state-action space into regions, further dividing a region once it has been visited often enough. They learn a single value estimate per region of that state-action space, and each decision is a primitive action. In contrast, we learn values at every layer of a multi-level abstraction, and the agent can execute temporally extended behaviours (options) that span many steps.

Allen et al. (2021) learn a state abstraction in the form of an encoder that maps high-dimensional observations into a latent representation, such that the decision process over that representation remains approximately Markov. Their abstraction is a continuous embedding, over which standard deep reinforcement learning algorithms learn. In contrast, we focus on aggregation-based state abstraction combined with temporal abstraction (options), and learn values over abstract states and options at every layer.

Wang et al. (2022) learn a causal dynamics model in a factored MDP, and derive a task-independent state abstraction from that model by filtering out state variables that are deemed irrelevant to the consequences of the agent’s actions. The abstraction is only over the state space, with abstract states represented by the remaining state variables, and downstream tasks are solved by model-based planning over these abstract states. In contrast, we learn values over abstract states and options at every layer of a multi-level abstraction.

Nayyar et al. (2026) focus on reinforcement learning with parameterised actions in continuous state spaces. Starting from a coarse abstraction, they recursively split regions of the state space and intervals of the action parameters where temporal difference errors and value estimates vary most, giving a task-specific abstraction. Values are learned over the abstract states and actions, and each state has a single set of value estimates, whereas in our hierarchy every state has value estimates at every layer. Their abstract actions are the environment's actions with parameters restricted to intervals, not new behaviour. In contrast, our abstraction is multi-level and reward-agnostic, built from the environment’s transition structure, and our abstract actions are options: new behaviours that act over multiple steps.

We will add all four to the related work, thank you for raising them.

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

This paper proposes a hierarchical reinforcement learning architecture that jointly exploits multi-level state and action abstractions. Building on the ϕ\phi-relative hierarchy formulation, the authors introduce a restricted bootstrapping rule that allows higher abstraction layers to use lower-level value estimates without propagating abstraction-induced bias back to the ground level. Hierarchical abstractions are constructed using graph partitioning, with options trained to navigate between abstract regions.

Experiments across six discrete environments show that the proposed architecture generally improves sample efficiency over action-only abstraction and several established option discovery methods. Additional experiments investigate scalability, hierarchy depth, alternative partitioning methods, restricted bootstrapping, and incremental abstraction discovery.

Critical strengths
  1. A well-motivated learning architecture for multi-level state-action abstraction.

The proposed restricted bootstrapping rule in Eq. (1) addresses a concrete difficulty in hierarchical value learning: abstract state values can introduce bias when used to update more precise value estimates. Preventing this downward propagation while retaining primitive actions is a reasonable and technically meaningful design.

  1. A controlled evaluation of the contribution of state abstraction.

The comparison between Louvain (ϕ,O)(\phi,O) and Louvain (O)(O) is particularly valuable because both methods use the same discovered options. This provides relatively direct evidence that learning over abstract states can improve sample efficiency beyond temporal action abstraction alone.

  1. Comprehensive ablations and scalability analysis.

The experiments examine hierarchy depth, partitioning methods, restricted bootstrapping, and state-space size. Figure 4 shows an increasing sample-efficiency advantage as the environment grows, while the single-level and spectral clustering experiments provide additional evidence that the benefits are not restricted to one particular hierarchy construction.

  1. Encouraging results with incremental abstraction discovery.

The experiments in Figure 6 demonstrate that the architecture remains useful when the state-transition graph and abstraction hierarchy are updated through online interaction. This is a meaningful step beyond assuming a fixed, manually specified hierarchy.

Critical weaknesses
  1. The theoretical guarantee does not extend to the final hierarchical policy.

Remark 1 establishes the convergence of ground-level Q-values under standard Q-learning assumptions. However, the deployed greedy policy selects options across all abstraction levels, where the value estimates aggregate information from different ground states. Restricted bootstrapping prevents these estimates from biasing ground-level learning but does not guarantee that the resulting hierarchical policy is optimal. This limitation is reflected in the slightly lower converged performance in Rush Hour and London Streets. A characterization of the resulting policy loss would strengthen the theoretical contribution.

  1. The approach still relies heavily on offline option construction.

In the main experiments, the transition graph is available for discovering the hierarchy, and option policies are pre-trained using value iteration before task learning. Even in the incremental setting, option policies are not learned online, as acknowledged in Section 6. Consequently, the results demonstrate efficient learning with constructed abstractions more convincingly than fully autonomous hierarchical skill discovery. The extent of the required environmental knowledge should be made clearer.

  1. The experimental scope is limited to relatively small tabular problems.

The six main environments contain approximately 400–5000 states and primarily involve deterministic, discrete transitions. Although these benchmarks are appropriate for investigating hierarchical abstractions, the proposed architecture has not been evaluated with function approximation, continuous states, or stochastic dynamics. Its scalability to larger problems therefore remains uncertain, particularly because the construction and execution of higher-level options depend on the underlying state representation.

  1. The computational cost of abstraction discovery and option learning is not sufficiently evaluated.

Sample efficiency is measured using ground-environment transitions, while hierarchy construction, option pre-training, and multi-level value updates introduce additional computation. Appendix D.3 analyzes memory requirements, but a corresponding analysis of runtime or preprocessing cost is missing. This distinction matters when comparing the overall efficiency of state-action abstraction against simpler approaches.

  1. The restricted bootstrapping mechanism would benefit from broader validation.

The direct comparison between restricted and unrestricted bootstrapping is conducted only in a hand-designed Four Rooms setting (Appendix E.3). Although the result is convincing in that environment, it remains unclear how much of the improvement in the six main benchmarks is attributable specifically to restricted bootstrapping rather than abstract-state value sharing. Extending this ablation to the main benchmarks would better isolate the contribution of the proposed learning rule.

  1. The convergence argument requires more careful qualification.

Remark 1 argues that soft option selection, eventual option termination, and retained primitive actions ensure sufficient visitation for ground-level Q-learning. However, these properties alone do not guarantee infinite visits to every reachable state-action pair in a general MDP without additional assumptions on reachability or recurrence. Moreover, the experiments use fixed learning rates, whereas the stated convergence guarantee requires Robbins–Monro conditions. The authors should distinguish the formal convergence conditions from those satisfied by the experimental implementation.

Questions for authors
  1. Can the authors characterize conditions under which selecting the greedy option across abstraction levels preserves optimality, or provide a bound on the potential value loss caused by abstract-state averaging?

  2. How much computation is required for hierarchy construction and option pre-training relative to task learning? Does the reported sample-efficiency advantage translate into lower end-to-end computational cost?

  3. Can the authors clarify what information is required to construct and train the option hierarchy in the incremental setting? In particular, are option policies re-trained using only the observed transitions?

  4. Have the authors evaluated restricted versus unrestricted bootstrapping on any of the six main benchmarks? If not, can they explain whether the gains primarily arise from the bootstrap restriction or from abstract-state value sharing?

5 comments

We thank you for taking the time to read our paper and leave thoughtful comments in your review. We hope that our response below answers your questions. We are updating the submission based on the reviews, and will upload a revised version during the discussion period.


Weakness (1). The theoretical guarantee does not extend to the final hierarchical policy. Remark 1 establishes the convergence of ground-level Q-values under standard Q-learning assumptions. However, the deployed greedy policy selects options across all abstraction levels, where the value estimates aggregate information from different ground states. Restricted bootstrapping prevents these estimates from biasing ground-level learning but does not guarantee that the resulting hierarchical policy is optimal. This limitation is reflected in the slightly lower converged performance in Rush Hour and London Streets. A characterization of the resulting policy loss would strengthen the theoretical contribution.

Question 1. Can the authors characterize conditions under which selecting the greedy option across abstraction levels preserves optimality, or provide a bound on the potential value loss caused by abstract-state averaging?

We agree that Remark 1 does not bound the value loss of the agent's greedy policy over the state-action abstraction, and we note this as a limitation in the submission (lines 480-482). Such bounds would be a valuable contribution, but we argue it is of little practical importance, for two reasons. First, a central aim of abstraction in reinforcement learning is to improve sample efficiency, as the availability of experience is often the limiting factor for learning. Whether a small reduction in converged performance is a worthwhile trade-off for faster learning depends on the application. Theoretical bounds would help with this decision. Second, there is a simple algorithmic route to recovering the optimal policy. Under the restricted bootstrapping rule of Equation 1, ground values converge to the optimal values (Remark 1). At convergence, an optimal policy can therefore be recovered by restricting the greedy policy to primitive actions.


Weakness (2). The approach still relies heavily on offline option construction. In the main experiments, the transition graph is available for discovering the hierarchy, and option policies are pre-trained using value iteration before task learning. Even in the incremental setting, option policies are not learned online, as acknowledged in Section 6. Consequently, the results demonstrate efficient learning with constructed abstractions more convincingly than fully autonomous hierarchical skill discovery. The extent of the required environmental knowledge should be made clearer.

Offline option construction is a property of our main experiments, not of the proposed approach. In our main experiments, we deliberately construct the options offline to answer a specific research question: are the multi-level state-action abstractions produced by the proposed method useful for improving an agent's learning performance, compared with agents using alternative abstractions or no abstraction at all? This allows us to isolate the benefits of the proposed approach independently of how the abstractions are acquired during the learning process. All alternative methods (baselines) in these experiments are also derived offline, so there is no fairness issue here.

After answering this research question in the affirmative, we then investigate the separate research question of how such abstractions might be acquired incrementally, through online interaction. In these experiments, the agent begins with no prior knowledge of the environment and constructs its state transition graph, abstractions, and options using only its own experience. The results demonstrate that the proposed approach remains effective in this setting.

In the incremental setting, no prior environment knowledge is required. Please see our response to Question 3 for full details on how the agent constructs and trains the hierarchy in the incremental setting.

Weakness (3). The experimental scope is limited to relatively small tabular problems. The six main environments contain approximately 400–5000 states and primarily involve deterministic, discrete transitions. Although these benchmarks are appropriate for investigating hierarchical abstractions, the proposed architecture has not been evaluated with function approximation, continuous states, or stochastic dynamics. Its scalability to larger problems therefore remains uncertain, particularly because the construction and execution of higher-level options depend on the underlying state representation.

We agree that scaling to larger problems is an important area for further work. The key components required to achieve this are the following:

  1. A partitioning method that is applicable to continuous spaces. This is an open line of research (e.g. Mendonça, Ziviani and Barreto, 2018; Hoang et al., 2021; Baek et al., 2025), and any progress in this area would be useful to other discovery methods that partition the state transition graph (e.g. Evans and Şimşek, 2023).
  2. Ground layer value estimates represented with function approximation. Value-based deep reinforcement learning (e.g. DQN; Mnih et al., 2015) is an obvious candidate.
  3. Layer 1 option policies represented with function approximation. Either value-based or gradient-based deep reinforcement learning methods could be applied here.

This is a significant research problem in itself. Addressing it in a sound way requires substantial research effort that falls outside the scope of the current paper.


Weakness (4). The computational cost of abstraction discovery and option learning is not sufficiently evaluated. Sample efficiency is measured using ground-environment transitions, while hierarchy construction, option pre-training, and multi-level value updates introduce additional computation. Appendix D.3 analyzes memory requirements, but a corresponding analysis of runtime or preprocessing cost is missing. This distinction matters when comparing the overall efficiency of state-action abstraction against simpler approaches.

Question 2. How much computation is required for hierarchy construction and option pre-training relative to task learning? Does the reported sample-efficiency advantage translate into lower end-to-end computational cost?

The Louvain algorithm is relatively efficient, with its runtime scaling approximately linearly with the number of graph edges (Blondel et al., 2008). Alternative partitioning methods will have different time complexities. Training the corresponding option policies also incurs a computational cost, which depends on the specific learning method used. We use value iteration, but other approaches could be used instead.

An inherent cost of learning with multi-level abstraction hierarchies is that additional value updates may be performed at each decision stage. For deep hierarchies, this overhead may be substantial. However, state-action abstraction lets a single update affect value estimates across an entire abstract region of the state space, whereas action-only abstraction requires separate updates for each individual ground state. Consequently, fewer updates will generally be needed to achieve a given level of learning performance with a state-action abstraction than with an action-only abstraction. Given the sample-efficiency improvements demonstrated in our experiments, the modest additional computation costs would be justified in most circumstances.

In the incremental setting, abstraction discovery and option policy learning are performed periodically as the agent gathers experience. As such, the one-off construction costs become recurring costs dependent on the frequency of these incremental abstraction updates. However, these costs are amortised over potentially many interactions between updates. Importantly, our experiments demonstrate that the proposed approach retains its sample-efficiency benefits even when the agent must construct its abstractions from scratch, entirely from its own experience.

Finally, we note that our abstraction discovery method is reward-free, and when an agent faces many tasks with different reward functions in the same environment (this is a common problem setting in the literature), the same state-action abstraction can be used for each task. Hierarchy construction and option pre-training are both reward-free, and our results indicate they are useful over a range of tasks in the same environment (for example in Office and London Streets in Figure 3). The costs of generating the hierarchy are therefore only incurred once, and this hierarchy can then be applied to many different tasks.

Weakness (5). The restricted bootstrapping mechanism would benefit from broader validation. The direct comparison between restricted and unrestricted bootstrapping is conducted only in a hand-designed Four Rooms setting (Appendix E.3). Although the result is convincing in that environment, it remains unclear how much of the improvement in the six main benchmarks is attributable specifically to restricted bootstrapping rather than abstract-state value sharing. Extending this ablation to the main benchmarks would better isolate the contribution of the proposed learning rule.

Question 4. Have the authors evaluated restricted versus unrestricted bootstrapping on any of the six main benchmarks? If not, can they explain whether the gains primarily arise from the bootstrap restriction or from abstract-state value sharing?

We are running the proposed ablation in all six of the main environments. We will report on the results in a follow-up response, and add it to the revised submission. We note that the restricted bootstrap rule is motivated primarily by achieving convergence at the ground layer (Remark 1), not by sample-efficiency.


Weakness (6). The convergence argument requires more careful qualification. Remark 1 argues that soft option selection, eventual option termination, and retained primitive actions ensure sufficient visitation for ground-level Q-learning. However, these properties alone do not guarantee infinite visits to every reachable state-action pair in a general MDP without additional assumptions on reachability or recurrence. Moreover, the experiments use fixed learning rates, whereas the stated convergence guarantee requires Robbins–Monro conditions. The authors should distinguish the formal convergence conditions from those satisfied by the experimental implementation.

Thank you for raising this, we will more clearly distinguish the properties of our method from assumptions about the MDP. An informal framing of Remark 1 is that under our method, Q0Q_0 converges to Q∗Q^{\ast} in MDPs where standard tabular Q-learning would also converge to Q∗Q^{\ast}. That is, nothing in our method prevents convergence at layer 0. We will update the argument for Remark 1 to make this clearer, as below:

Sufficient visitation depends on the environment and on the method. For the environment, we assume every state is reachable from every other state, or that the task is episodic, every episode terminates with probability one, and every state is reachable from the initial state distribution. For the method, three properties ensure the hierarchy does not prevent sufficient visitation: the behaviour policy is soft, every option policy reaches an abstract state that satisfies its termination with probability 1; and the primitive actions are retained.

We will also better distinguish the formal convergence conditions from our experimental results, adding the below or similar to the revised submission: While Remark 1 concerns the asymptotic behaviour of the learning rule, our experiments use constant learning rates, which do not satisfy the Robbins–Monro conditions.


Question 3. Can the authors clarify what information is required to construct and train the option hierarchy in the incremental setting? In particular, are option policies re-trained using only the observed transitions?

In the incremental setting, the proposed approach assumes no prior knowledge whatsoever. During learning, option policies are computed by value iteration on a transition model estimated from observed transitions only.

The agent begins with only primitive actions and an empty state transition graph, containing no nodes or edges. As it interacts with the environment, it records observed state-action-next-state (s,a,s′)(s,a,s') transitions: it adds newly encountered states to the graph as nodes, newly encountered transitions as edges, and estimates transition probabilities based on observed transition counts.

Periodically, the Louvain algorithm is applied to the agent's current, incrementally constructed state transition graph to produce a new hierarchy of state partitions. These partitions then act as the basis for a new state-action abstraction. In particular, the policies of options in the agent's abstraction are computed using value iteration on the empirical transition function estimates derived from the observed transition counts. As such, all aspects of the state-action abstraction are built incrementally using only the experience collected by the agent itself, without any access to the true environment model or any unobserved transitions.

Each new hierarchy replaces the previous one, with abstract option values reset while primitive action values are retained.

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

The paper presents a unifying view of state-action abstraction for hierarchical reinforcement learning. The view constructs nested state domains, which then achieved via Louvain clustering. The options are policies that move from one abstract state (cluster) to adjacent ones. The proposed algorithm takes the fixed hierarchy as input and learns option values across the ground states within the cluster. The paper chooses to limits a abstraction level to only see values at the same or lower abstraction level to prevent coarse errors from propagating deeper. The experiments test the suggested approach against acation-only abstraction and option-discovery baselines in 6 tabular environments, next to some scaling ablations.

Critical strengths

The comparison between action-state abstraction and action-only abstraction is interesting, as it shows the benefit of sharing option values across ground states versus using option state directly, and related directly to the sample efficiency HRL claims. The bootstraping restriction is reasonably motivated and addresses a common engineering choice in HRL and mixture of experts: is the gating policy optimization oblivious to its sub-policies values or not? The experiments are also transparent about the limitations of the suggested approach and when it works or underperforms.

Critical weaknesses

The main weakness of this work is its insufficiently distinguished contribution. The paper core definitions and theory are directly adopted from Abel et al. (2020), which already introduce ϕ\phi-relative options and multilevel state-action, and the main result about state abstraction propagating information is classical insight in HRL literature.

The Louvain clustering is also not new, and was used by Evans and Simsek (2023) for multilevel skill discovery and incremental hierarchy with the extremely similar environments setup. The paper does not clearly distinguish its proposal from these existing components. The discussion of the line of work by Machado el. is also limited: (1) and (2): representation-driven discovery with scalable option and hierarchy learning, which goes beyond the fixed hierarchy in the current manuscript.

Even if we assume that the novelty is more experimental, the results and tested tabular cases are limited when compared to the current state of the field where RL environment have large states spaces and rely on gradient based methods. If the method is only specific to tabular cases, it should be made explicit and clear

Questions for authors

Based on the aforementioned assessment:

  • What is the precise novel contribution after accounting for all the related work mentioned? Is it Equation 1? Algorithm1?
  • If the contribution is more experimental, what are the limitations of the existing results and where do they show up?
  • Do the gains (when they exist) persist gainst value-aware eigenoptions and stronger controllers?
  • How easy is it to extend the suggested approach beyond tabular RL and to stochastic dynamics?
4 comments

We thank you for taking the time to read our paper and leave thoughtful comments in your review. We hope that our response below answers your questions. We are updating the submission based on the reviews, and will upload a revised version during the discussion period.


Question 1. What is the precise novel contribution after accounting for all the related work mentioned? Is it Equation 1 or Algorithm 1?

The precise novel contributions are as follows:

  1. Equation 1, a novel bootstrapping rule.
  2. Algorithm 1, a new and complete reinforcement learning algorithm that learns values over a joint hierarchical state-action abstraction, with no limit to the number of levels in the hierarchy. The algorithm uses Equation 1 to prevent overestimation at coarse layers from biasing updates at lower layers.
  3. Empirical learning results with Algorithm 1, using autonomously constructed multi-level state-action abstractions.

Equation 1 is important; it prevents overestimation at higher layers (coarser, more abstract layers) from biasing updates at lower layers (finer, less abstract layers), ensuring ground values converge to optimal (Remark 1). Without it, ground layer values are not guaranteed to converge to the optimal values, and our ablation (Figure 10) shows that removing it can substantially impair learning performance.

Algorithm 1 (which uses Equation 1) addresses the question of how an agent should learn with multi-level state-action abstractions. Despite the critical importance of this question for efficient and scalable reinforcement learning, it has not been addressed to date by Abel et al. (2020) or other researchers. Our work is the first to attempt or achieve learning with autonomously generated ϕ\phi-relative state-action abstractions.

In our empirical analysis, we use the Louvain partitioning algorithm for our main results due to its demonstrated success for autonomous discovery of useful action-only abstractions (Evans and Şimşek, 2023), but our approach is not limited to the Louvain partitioning algorithm, and we include results with spectral clustering (Figure 5), as well. Evans and Şimşek (2023) consider only temporal abstraction (action-only abstraction); they do not consider state abstraction or joint state-action abstraction (which is our focus); nor do they address how learning should happen with joint state-action abstraction.

Abel et al. (2020) define the core formalism of ϕ\phi-relative state-action abstractions; our work targets important open questions that they do not answer: How can useful state-action abstractions be discovered? How should an agent learn with them? What, if any, are the empirical benefits?

We give further details about our contributions relative to the prior work by Abel et al. (2020) and Evans and Şimşek (2023) in separate responses.

The main motivation for our paper is fully autonomous learning in large, complex environments: an agent learning from its own experience, with no human guidance. Abstraction is an essential ingredient of this, and the importance of both state and action abstraction is widely recognised. In reinforcement learning, action abstraction is well established through the options framework. Yet no existing method autonomously discovers, and learns with, a hierarchy of state-action abstractions. This is exactly the contribution of our paper, offering a concrete and significant step forward in this exciting field.

Weakness (a). The main weakness of this work is its insufficiently distinguished contribution. The paper core definitions and theory are directly adopted from Abel et al. (2020), which already introduce ϕ\phi-relative options and multilevel state-action

Abel et al. (2020) define ϕ\phi-relative options and hierarchies, and bound the value loss of the policies they can represent. Their definitions are not our contribution, and we do not claim them. We instead target important open questions that they do not answer: How can useful ϕ\phi-relative state-action abstractions be discovered? How should an agent learn with them? What are the empirical benefits on learning performance?


Weakness (b). The main result about state abstraction propagating information is classical insight in HRL literature.

This is not a result we claim in our paper. We offer it only as intuition for our results in the discussion (lines 454-455).


Weakness (c). The Louvain clustering is also not new, and was used by Evans and Simsek (2023) for multilevel skill discovery and incremental hierarchy with the extremely similar environments setup. The paper does not clearly distinguish its proposal from these existing components.

The Louvain algorithm was originally proposed by Blondel et al. (2008) for community detection in graphs. Evans and Şimşek (2023) demonstrated that it can be used to discover useful temporal abstractions (action-only abstractions) in reinforcement learning. This earlier result motivated our use of the Louvain algorithm for joint state-action abstraction, which proved effective, but our contribution is independent of any specific partitioning algorithm, and we provide results with spectral partitioning, as well.

To give further detail: Evans and Şimşek (2023) operate only with ground states; they do not consider state abstraction at all. In contrast, we generate (a hierarchy of) abstract states; and we learn values over both ground and abstract states, using our proposed learning architecture and restricted bootstrap rule.


Weakness (d). The discussion of the line of work by Machado el. is also limited: (1) and (2): representation-driven discovery with scalable option and hierarchy learning, which goes beyond the fixed hierarchy in the current manuscript.

Machado et al. (2023) investigate representation-driven option discovery using the successor representation, while Klissarov and Machado (2023) extend Laplacian-based option discovery to the function-approximated setting using deep reinforcement learning. Both of these papers consider action-only abstraction; and the abstraction is only one-level deep (a single layer of options over the primitive actions). In contrast, our paper considers how to construct joint state-action abstractions; and the abstraction can be of arbitrary depth rather than being limited to a single layer. Additionally, neither of these papers addresses the challenges of learning value estimates for abstract actions at multiple levels of state abstraction, which directly motivates our proposed learning architecture and restricted bootstrapping rule.

We would also like to clarify that the proposed approach does not require a fixed hierarchy. In Figure 6 (Section 5), we demonstrate incremental abstraction discovery, in which the agent continually gathers experience and periodically updates its state-action abstraction hierarchy. This incremental approach is an instance of Machado et al.'s (2023) ROD cycle, and we will acknowledge this connection in the revised manuscript.

Finally, we recognise the importance of extending our approach to larger problems using function approximation, and we discuss how to do so in Section 6 (lines 467-479) and in our response to Question 4 below. Regarding Klissarov and Machado's (2023) line of work, we note that Laplacian-based action abstraction has benefited from an extensive body of research addressing precisely these scaling challenges. In contrast, the problem of constructing and learning with multi-level state-action abstractions remains much less developed. Our paper takes an important step toward addressing this distinct problem, and extending the proposed approach to the function-approximated setting (e.g., via deep learning) is a natural direction for future work.

Weakness (e). Even if we assume that the novelty is more experimental, the results and tested tabular cases are limited when compared to the current state of the field where RL environment have large states spaces and rely on gradient based methods. If the method is only specific to tabular cases, it should be made explicit and clear.

As explained in our answer to question 1, our contribution is not only experimental.

Our experiments ask specific research questions about the proposed learning architecture, and the tabular setting is the most appropriate one for those questions. It supports in-depth ablations, isolating the effect of the abstraction and learning rule from function-approximation error, so that differences in our comparisons are attributable to the learning architecture and joint state-action abstractions.

We address how to scale the method to large or continuous state spaces (i.e. to deep RL) in our discussion (Section 6, lines 467-479), and in our response to Question 4 below.


Question 2. If the contribution is more experimental, what are the limitations of the existing results and where do they show up?

First we note that our contribution is not only experimental, as described in our response to question 1.

One limitation raised by our results is that, in some cases, the agent's greedy policy converges to slightly lower performance than the corresponding action-only abstraction. This is consistent with the averaging effect of state abstraction, where an option can appear greedy at ground states where it is not the best choice. A key motivation for abstraction in reinforcement learning is to improve sample efficiency, as experience is often the limiting factor for learning. Whether a small reduction in converged performance is a worthwhile trade-off for faster learning depends on the application.

We note that this effect is caused by acting greedily over the learned abstract option values, not from learning with the abstraction itself. Under the restricted bootstrapping rule of Equation 1, ground values converge to the optimal values (Remark 1). At convergence, an optimal policy can therefore be recovered by restricting the greedy policy to primitive actions.


Question 3. Do the gains (when they exist) persist against value-aware eigenoptions and stronger controllers?

We implemented eigenoptions as proposed by Machado et al. (2017); this is a common and well-understood baseline in hierarchical reinforcement learning. We are not clear on what you mean by value-aware eigenoptions and stronger controllers, could you please clarify?

Question 4. How easy is it to extend the suggested approach beyond tabular RL and to stochastic dynamics?

We address the route to function approximation in the discussion (lines 467-479). Specifically, we suggest it requires three distinct components:

  1. A partitioning method that is applicable to very large or continuous state spaces. This is an open line of research (e.g. Mendonça, Ziviani and Barreto, 2018; Hoang et al., 2021; Baek et al., 2025), and any progress in this area would be useful to other discovery methods that partition the state transition graph (including Evans and Şimşek, 2023).
  2. Ground layer value estimates represented with function approximation, learned online from the task reward. Value-based deep reinforcement learning (e.g. DQN; Mnih et al., 2015) is an obvious candidate.
  3. Layer 1 option policies represented with function approximation, each trained to reach its target abstract state, using a pseudo-reward rather than the task reward. This is a separate policy-learning problem, to which value-based or gradient-based deep reinforcement learning methods could be applied.

Above the ground layer, the architecture is discrete by nature, and so value estimates at these layers can remain tabular. Combining these components into a robust and effective architecture is a substantial research challenge on its own, beyond the scope of the current paper.

Both our abstraction discovery approach and our learning architecture apply naturally to stochastic domains. We use graph partitioning methods applied to the state transition graph, where edge weights can represent transition probabilities. The partitioning methods used in the paper (Louvain and spectral clustering) accept weighted graphs and so can be applied to stochastic environments. Our learning architecture uses sample-based temporal-difference updates that are naturally compatible with learning in stochastic MDPs.


References:

Baek, S., Park, T., Park, J., Oh, S. and Kim, Y. (2025). Graph-assisted stitching for offline hierarchical reinforcement learning. ICML.

Evans, J.B. and Şimşek, Ö. (2023). Creating multi-level skill hierarchies in reinforcement learning. NeurIPS.

Hoang, C., Sohn, S., Choi, J., Carvalho, W. and Lee, H. (2021). Successor feature landmarks for long-horizon goal-conditioned reinforcement learning. NeurIPS.

Mendonça, M.R.F., Ziviani, A. and Barreto, A.M.S. (2018). Abstract state transition graphs for model-based reinforcement learning. BRACIS.

Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised submission

We thank all the reviewers for their constructive comments and suggestions.

We have uploaded a revised submission based on reviewer feedback, with the following changes:

  • Restricted bootstrap ablation: We have replaced the hand-coded Four Rooms ablation with a more thorough one, in the same environments and with the same state-action abstractions as our main results (Section 5, Figure 10). The ablation provides strong support for the importance of the restricted bootstrap rule for learning with state-action abstractions. Please note the London Streets runs are for 12 of 20 agents, and will be updated once the experiment completes.
  • Remark 1: We separate the assumptions on the environment from the properties of the method that ensure sufficient visitation, and note in Appendix D.1 that the convergence guarantee of Remark 1 describes the learning rule, not our experimental agents, which use constant learning rates.
  • Incremental approach: We clarify that the incremental agent does not require any prior knowledge of the environment. The state-transition graph, the abstraction and the option policies are all built from its own experience. We also cite the representation-driven option discovery cycle of Machado et al. (2023) here.
  • Related Work: We added discussions of Sinclair et al. (2020), Allen et al. (2021), Wang et al. (2022) and Nayyar et al. (2026).
  • Analysis of Results: We state that the corresponding action-only abstraction is our primary comparison, and provide intuitions for why state-action abstraction is more sample-efficient than action-only abstraction with the same options, and why the multi-level abstraction outperforms single-level ones.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.