# Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning

arXiv: https://arxiv.org/abs/2512.04958 · HTML: https://mlsanity.com/paper/2512.04958/

## 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.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 30 of 32)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Data-Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1805.08296/) (2018)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Language as an Abstraction for Hierarchical Deep Reinforcement Learning](https://mlsanity.com/paper/1906.07343/) (2019)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [A Boolean Task Algebra for Reinforcement Learning](https://mlsanity.com/paper/2001.01394/) (2020)
- [Learning Markov State Abstractions for Deep Reinforcement Learning](https://mlsanity.com/paper/2106.04379/) (2021)
- [A Survey of Constraint Formulations in Safe Reinforcement Learning](https://mlsanity.com/paper/2402.02025/) (2024)
- [Discovering Options for Exploration by Minimizing Cover Time](https://mlsanity.com/paper/1903.00606/) (2019)
- [Options of Interest: Temporal Abstraction with Interest Functions](https://mlsanity.com/paper/2001.00271/) (2020)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [A Theory of Abstraction in Reinforcement Learning](https://mlsanity.com/paper/2203.00397/) (2022)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Successor Options: An Option Discovery Framework for Reinforcement Learning](https://mlsanity.com/paper/1905.05731/) (2019)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)
- [Learning Options via Compression](https://mlsanity.com/paper/2212.04590/) (2022)
- [Hierarchical Reinforcement Learning with Timed Subgoals](https://mlsanity.com/paper/2112.03100/) (2021)
- [Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces](https://mlsanity.com/paper/1405.6757/) (2014)
- [Exploration--Exploitation in MDPs with Options](https://mlsanity.com/paper/1703.08667/) (2017)
- [DHRL: A Graph-Based Approach for Long-Horizon and Sparse Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2210.05150/) (2022)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning](https://mlsanity.com/paper/1612.02516/) (2016)
- [Verifiable and Compositional Reinforcement Learning Systems](https://mlsanity.com/paper/2106.05864/) (2021)
- [Abstract Value Iteration for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2010.15638/) (2020)
- [State Representation Learning for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2205.01965/) (2022)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes](https://mlsanity.com/paper/2106.15380/) (2021)

## 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.