Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning

• URL: http://arxiv.org/abs/2512.04958v1
• Date: Thu, 04 Dec 2025 16:26:56 GMT
• Title: Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning
• Authors: Roberto Cipollone, Luca Iocchi, Matteo Leonetti,
• Abstract summary: This paper defines Realizable Abstractions, a new relation between generic low-level MDPs and their associated high-level decision processes.<n>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.<n>We propose RARL, a new HRL algorithm that returns compositional and near-optimal low-level policies.
• Score: 4.024538378639506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Learning Temporal Abstractions via Variational Homomorphisms in Option-Induced Abstract MDPs [17.335266921332092]
  Large Language Models (LLMs) have shown remarkable reasoning ability through explicit Chain-of-Thought prompting.<n>We develop a framework for efficient, implicit reasoning, where the model "thinks" in a latent space without generating explicit text for every step.
  arXiv  Detail & Related papers  (2025-07-22T11:22:58Z)
• RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation [73.2390735383842]
  We introduce the first sample-efficient algorithm for LMDPs without any additional structural assumptions. We show how these can be used to derive near-optimal guarantees of an optimistic exploration algorithm. These results can be valuable for a wide range of interactive learning problems beyond LMDPs, and especially, for partially observed environments.
  arXiv  Detail & Related papers  (2024-06-03T14:51:27Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  We propose the first instance-dependent lower bound on the sample complexity required for the PAC identification of a near-optimal policy. We demonstrate that the sample complexity of the PEDEL algorithm of citeWagenmaker22linearMDP closely approaches this lower bound.
  arXiv  Detail & Related papers  (2023-10-31T19:26:36Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Exploiting Multiple Abstractions in Episodic RL via Reward Shaping [23.61187560936501]
  We consider a linear hierarchy of abstraction layers of the Markov Decision Process (MDP) underlying the target domain. We propose a novel form of Reward Shaping where the solution obtained at the abstract level is used to offer rewards to the more concrete MDP.
  arXiv  Detail & Related papers  (2023-02-28T13:22:29Z)
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning [132.45959478064736]
  We propose a general framework that unifies model-based and model-free reinforcement learning. We propose a novel estimation function with decomposable structural properties for optimization-based exploration. Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed.
  arXiv  Detail & Related papers  (2022-09-30T17:59:16Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  We propose the first (nearly) matching upper and lower bounds on the sample complexity of PAC RL in episodic Markov decision processes. Our bounds feature a new notion of sub-optimality gap for state-action pairs that we call the deterministic return gap. Their design and analyses employ novel ideas, including graph-theoretical concepts such as minimum flows and maximum cuts.
  arXiv  Detail & Related papers  (2022-03-17T11:19:41Z)
• Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality [141.89413461337324]
  Deployment efficiency is an important criterion for many real-world applications of reinforcement learning (RL) We propose a theoretical formulation for deployment-efficient RL (DE-RL) from an "optimization with constraints" perspective.
  arXiv  Detail & Related papers  (2022-02-14T01:31:46Z)
• Reward is enough for convex MDPs [30.478950691312715]
  We study convex MDPs in which goals are expressed as convex functions of the stationary distribution. We propose a meta-algorithm for solving this problem and show that it unifies many existing algorithms in the literature.
  arXiv  Detail & Related papers  (2021-06-01T17:46:25Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  We consider the regret problem for reinforcement learning in latent Markov Decision Processes (LMDP) In an LMDP, an MDP is randomly drawn from a set of $M$ possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We show that the key link is a notion of separation between the MDP system dynamics.
  arXiv  Detail & Related papers  (2021-02-09T16:49:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Learning Abstract Models for Strategic Exploration and Fast Reward Transfer [85.19766065886422]
  We learn an accurate Markov Decision Process (MDP) over abstract states to avoid compounding errors. Our approach achieves strong results on three of the hardest Arcade Learning Environment games. We can reuse the learned abstract MDP for new reward functions, achieving higher reward in 1000x fewer samples than model-free methods trained from scratch.
  arXiv  Detail & Related papers  (2020-07-12T03:33:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.