# A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 21 Jun 2024.

## Placed in

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

## Built on by (most cited first, 2 of 2)

- [Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification](https://mlsanity.com/paper/2607.29294/) (2026)
- [When Do Options Help? Policy Necrosis and Redundant Coverage in Option-Critic](https://mlsanity.com/paper/2609.05508/) (2026)

## Abstract (arXiv)

Hierarchical Reinforcement Learning (HRL) approaches have shown successful results in solving a large variety of complex, structured, long-horizon problems. Nevertheless, a full theoretical understanding of this empirical evidence is currently missing. In the context of the option framework, prior research has devised efficient algorithms for scenarios where options are fixed, and the high-level policy selecting among options only has to be learned. However, the fully realistic scenario in which both the high-level and the low-level policies are learned is surprisingly disregarded from a theoretical perspective. This work makes a step towards the understanding of this latter scenario. Focusing on the finite-horizon problem, we present a meta-algorithm alternating between regret minimization algorithms instanced at different (high and low) temporal abstractions. At the higher level, we treat the problem as a Semi-Markov Decision Process (SMDP), with fixed low-level policies, while at a lower level, inner option policies are learned with a fixed high-level policy. The bounds derived are compared with the lower bound for non-hierarchical finite-horizon problems, allowing to characterize when a hierarchical approach is provably preferable, even without pre-trained options.