An Option-Dependent Analysis of Regret Minimization Algorithms in
  Finite-Horizon Semi-Markov Decision Processes
Gianluca Drappo Alberto Maria Metelli Marcello Restelli
A large variety of real-world Reinforcement Learning (RL) tasks is
characterized by a complex and heterogeneous structure that makes end-to-end
(or flat) approaches hardly applicable or even infeasible. Hierarchical
Reinforcement Learning (HRL) provides general solutions to address these
problems thanks to a convenient multi-level decomposition of the tasks, making
their solution accessible. Although often used in practice, few works provide
theoretical guarantees to justify this outcome effectively. Thus, it is not yet
clear when to prefer such approaches compared to standard flat ones. In this
work, we provide an option-dependent upper bound to the regret suffered by
regret minimization algorithms in finite-horizon problems. We illustrate that
the performance improvement derives from the planning horizon reduction induced
by the temporal abstraction enforced by the hierarchical structure. Then,
focusing on a sub-setting of HRL approaches, the options framework, we
highlight how the average duration of the available options affects the
planning horizon and, consequently, the regret itself. Finally, we relax the
assumption of having pre-trained options to show how in particular situations,
learning hierarchically from scratch could be preferable to using a standard
approach.