  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.
