- 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:
- Sinclair, Sean, et al. "Adaptive discretization for model-based reinforcement learning." NeurIPS 2020.
- Allen, Cameron, et al. "Learning markov state abstractions for deep reinforcement learning." NeurIPS 2021.
- Wang, Zizhao, et al. "Causal dynamics learning for task-independent state abstraction." ICML 2022.
- Nayyar, Rashmeet et al. "Context-sensitive abstractions for reinforcement learning with parameterized actions." AAAI 2026.
5 comments
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:
- 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).
- 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.
- 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.
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)) and its corresponding action-only abstraction (Louvain (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.