A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning
<|reference_start|>A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning: 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 \emph{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.<|reference_end|>
@article{drappo2024a,
    title={A Provably Efficient Option-Based Algorithm for both High-Level and
  Low-Level Learning},
    author={Gianluca Drappo, Alberto Maria Metelli, Marcello Restelli},
    journal={arXiv preprint arXiv:2406.15124},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.15124},
    primaryClass={cs.LG}
}