Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification

• URL: http://arxiv.org/abs/2607.29294v1
• Date: Fri, 31 Jul 2026 11:12:31 GMT
• Title: Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification
• Abstract summary: We present HBPI-UCRL, a model-based algorithm for hierarchical reinforcement learning (HRL) that learns high-level and low-level policies in parallel.<n>In the sparse-reward, goal-directed setting, our sample upper bound for HBPI-UCRL is strictly lower than that of its non-hierarchical counterpart.
• Score: 11.621402971675835
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We present HBPI-UCRL, a model-based algorithm for hierarchical reinforcement learning (HRL) that learns high-level and low-level policies in parallel. HBPI-UCRL exploits the fact that a high-level transition corresponds to a multi-step transition at the low level. We introduce two conditions on the low-level dynamics that are sufficient to make parallel HRL learnable. When these conditions hold, we prove that HBPI-UCRL has a polynomial sample complexity in the problem parameters. In the sparse-reward, goal-directed setting, our sample complexity upper bound for HBPI-UCRL is strictly lower than that of its non-hierarchical counterpart, providing theoretical justification for the empirical success of HRL.

Related papers

• Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity [44.384258745074646]
  We propose a hypergradient-based bilevel RL algorithm using the optimality of the Boltzmann policy for the entropy regularized discounted RL objective function.<n>Our proposed algorithm is Hessian-free and obtains an iteration complexity of $O(-1)$ and state-of-the-art sample complexity of $tildeO(-2)$ under mild regularity conditions.
  arXiv  Detail & Related papers  (2026-07-30T21:21:52Z)
• Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning [47.66330599017582]
  We analyse the sample complexity of a constrained bilevel RL algorithm, building on the progress in the unconstrained setting.<n>We are the first ones to analyse the generally parameterized policy-based RL algorithm with a non-smooth objective function.
  arXiv  Detail & Related papers  (2026-01-30T20:10:21Z)
• Sample-Efficient Neurosymbolic Deep Reinforcement Learning [49.60927398960061]
  We propose a neuro-symbolic Deep RL approach that integrates background symbolic knowledge to improve sample efficiency.<n>Online reasoning is performed to guide the training process through two mechanisms.<n>We show improved performance over a state-of-the-art reward machine baseline.
  arXiv  Detail & Related papers  (2026-01-06T09:28:53Z)
• Direct Preference Optimization for Primitive-Enabled Hierarchical Reinforcement Learning [75.9729413703531]
  DIPPER is a novel HRL framework that formulates hierarchical policy learning as a bi-level optimization problem.<n>We show that DIPPER achieves up to 40% improvement over state-of-the-art baselines in sparse reward scenarios.
  arXiv  Detail & Related papers  (2024-11-01T04:58:40Z)
• Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity [4.917399520581689]
  Bilevel reinforcement learning (RL) features intertwined two-level problems.<n>Non-level convex information is an impediment to developing bilevel optimization methods.<n>Hyper-gradient serves as an integration of exploitation and exploration.
  arXiv  Detail & Related papers  (2024-05-30T05:24:20Z)
• REBEL: Reinforcement Learning via Regressing Relative Rewards [59.68420022466047]
  We propose REBEL, a minimalist RL algorithm for the era of generative models.<n>In theory, we prove that fundamental RL algorithms like Natural Policy Gradient can be seen as variants of REBEL.<n>We find that REBEL provides a unified approach to language modeling and image generation with stronger or similar performance as PPO and DPO.
  arXiv  Detail & Related papers  (2024-04-25T17:20:45Z)
• DHRL: A Graph-Based Approach for Long-Horizon and Sparse Hierarchical Reinforcement Learning [26.973783464706447]
  Hierarchical Reinforcement Learning (HRL) has made notable progress in complex control tasks by leveraging temporal abstraction. Previous HRL algorithms often suffer from serious data inefficiency as environments get large. We present a method of Decoupling Horizons Using a Graph in Hierarchical Reinforcement Learning (DHRL) which can alleviate this problem.
  arXiv  Detail & Related papers  (2022-10-11T05:09:34Z)
• Hierarchical Reinforcement Learning with Optimal Level Synchronization based on a Deep Generative Model [4.266866385061998]
  One of the HRL issues is how to train each level policy with the optimal data collection from its experience. We propose a novel HRL model supporting the optimal level synchronization using the off-policy correction technique with a deep generative model.
  arXiv  Detail & Related papers  (2021-07-17T05:02:25Z)
• Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning [56.17667147101263]
  In real-world tasks, reinforcement learning agents encounter situations that are not present during training time. To ensure reliable performance, the RL agents need to exhibit robustness against worst-case situations. We propose the Robust Hallucinated Upper-Confidence RL (RH-UCRL) algorithm to provably solve this problem.
  arXiv  Detail & Related papers  (2021-03-18T16:50:17Z)

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.