mlsanityData to 14 Oct 2026

Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning

arXiv 2512.04958 ↗First posted 4 Dec 2025cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

The main focus of Hierarchical Reinforcement Learning (HRL) is studying how large Markov Decision Processes (MDPs) can be more efficiently solved when addressed in a modular way, by combining partial solutions computed for smaller subtasks. Despite their very intuitive role for learning, most notions of MDP abstractions proposed in the HRL literature have limited expressive power or do not possess formal efficiency guarantees. This work addresses these fundamental issues by defining Realizable Abstractions, a new relation between generic low-level MDPs and their associated high-level decision processes. The notion we propose avoids non-Markovianity issues and has desirable near-optimality guarantees. Indeed, we show that any abstract policy for Realizable Abstractions can be translated into near-optimal policies for the low-level MDP, through a suitable composition of options. As demonstrated in the paper, these options can be expressed as solutions of specific constrained MDPs. Based on these findings, we propose RARL, a new HRL algorithm that returns compositional and near-optimal low-level policies, taking advantage of the Realizable Abstraction given in the input. We show that RARL is Probably Approximately Correct, it converges in a polynomial number of samples, and it is robust to inaccuracies in the abstraction.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 32 of its 75 references that are in the map. First posted on arXiv 4 Dec 2025.

Builds on

32 of 75 references.

References · 32

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2018Data-Efficient Hierarchical Reinforcement Learningcited by 455
  3. 2016The Option-Critic Architecturecited by 448
  4. 2016Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivationcited by 286
  5. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 203
  6. 2019Language as an Abstraction for Hierarchical Deep Reinforcement Learningcited by 138
  7. 2017A Laplacian Framework for Option Discovery in Reinforcement Learningcited by 110
  8. 2021Compositional Reinforcement Learning from Logical Specificationscited by 67
  9. 2020A Boolean Task Algebra for Reinforcement Learningcited by 48
  10. 2021Learning Markov State Abstractions for Deep Reinforcement Learningcited by 44
  11. 2024A Survey of Constraint Formulations in Safe Reinforcement Learningcited by 44
  12. 2019Discovering Options for Exploration by Minimizing Cover Timecited by 31
20 more
  1. 2020Options of Interest: Temporal Abstraction with Interest Functionscited by 30
  2. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  3. 2022A Theory of Abstraction in Reinforcement Learningcited by 27
  4. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  5. 2019Successor Options: An Option Discovery Framework for Reinforcement Learningcited by 23
  6. 2016The Multi-fidelity Multi-armed Banditcited by 22
  7. 2022Learning Options via Compressioncited by 22
  8. 2021Hierarchical Reinforcement Learning with Timed Subgoalscited by 21
  9. 2014Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spacescited by 19
  10. 2017Exploration--Exploitation in MDPs with Optionscited by 19
  11. 2022DHRL: A Graph-Based Approach for Long-Horizon and Sparse Hierarchical Reinforcement Learningcited by 19
  12. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  13. 2016Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learningcited by 15
  14. 2021Verifiable and Compositional Reinforcement Learning Systemscited by 13
  15. 2020Abstract Value Iteration for Hierarchical Reinforcement Learningcited by 12
  16. 2022State Representation Learning for Goal-Conditioned Reinforcement Learningcited by 11
  17. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  18. 2021Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processescited by 6
  19. 2021Primal-Dual Stochastic Mirror Descent for MDPscited by 3
  20. 2023Exploiting Multiple Abstractions in Episodic RL via Reward Shapingcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Abstraction for Offline Goal-Conditioned Reinforcement Learning
  2. 2024A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning
  3. 2024Reinforcement Learning with Options and State Representation
  4. 2026Q-Shaped Options for Hierarchical Reinforcement Learning
  5. 2024Exploring the limits of Hierarchical World Models in Reinforcement Learning
  6. 2024Hierarchical Average-Reward Linearly-solvable Markov Decision Processes
  7. 2026Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification
  8. 2026On Semi-Markov Suboptimality in Hierarchical Reinforcement Learning