# An Option-Dependent Analysis of Regret Minimization Algorithms
in Finite-Horizon Semi-Markov Decision Processes

Gianluca Drappo  DEIB, Politecnico di Milano, Milan, 20133, Italy.  Alberto
Maria Metelli  DEIB, Politecnico di Milano, Milan, 20133, Italy.  Marcello
Restelli  DEIB, Politecnico di Milano, Milan, 20133, Italy.

###### Abstract

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.

##  1 Introduction

Hierarchical Reinforcement Learning [HRL, Pateria et al., 2021] is a learning
paradigm that decomposes a long-horizon Reinforcement Learning [RL, Sutton and
Barto, 2018] task into a sequence of potentially shorter and simpler sub-
tasks. The sub-tasks themselves could be further divided, generating a
hierarchical structure organized in an arbitrary number of levels. Each of
these defines a different problem, where the original action space is replaced
by the set of sub-tasks available on the lower level, and the same could be
replicated for multiple levels. Although, the actual state transition is
induced only once the control reaches the leaf nodes, where the policies
choose among the primitive actions (i.e., actions of the original MDP on top
of which the hierarchy is constructed). For the higher levels, once a sub-task
is selected, the control passes to the relative internal policy until its
termination. This introduces the concept of _temporal abstraction_ [Precup and
Sutton, 1997], for what concerns the high-level policy, the action persists
for a certain time, resulting in an actual reduction of the original planning
horizon.

Several algorithms demonstrate outstanding performance compared to standard RL
approaches in several long-horizon problems [Levy et al., 2019, Vezhnevets et
al., 2017, Bacon et al., 2017, Nachum et al., 2018]. However, such evidence is
mainly emerging in practical applications, and the theoretical understanding
of the inherent reasons for these advantages is still underdeveloped. Only a
few papers tried to justify these advantages theoretically, focusing on
different aspects. For instance, Mann et al. [2015] studies the convergence of
an algorithm that uses temporally extended actions instead of primitive ones.
Fruit et al. [2017] and the extension Fruit and Lazaric [2017] focus on the
exploration benefit of using options in average reward problems. More
recently, Wen et al. [2020] show how the MDP structure affects regret. In this
paper, we seek to further bridge this theory-practice gap, following the
intuition that a hierarchical structure in a finite-horizon problem would
positively affect the sample complexity by reducing the planning horizon. This
could help to discriminate among situations in which a hierarchical approach
could be more effective than a standard one for this particular family of
problems.

Contributions The contributions of the paper can be summarized as follows. (1)
We propose a new algorithm for the finite-horizon setting that exploits a set
of _fixed_ options [Sutton et al., 1999] to solve the HRL problem. (2) We
conducted a regret analysis of this algorithm, providing an option-dependent
upper bound, which, to the best of our knowledge, is the first in the Finite
Horizon setting. This result could be used to define new objective functions
for options discovery methods that would search for options that minimize this
regret. (3) For the sake of our analysis, we formulate the notion of Finite
Horizon SMDP and a _performance difference lemma_ for this setting. (4)
Lastly, we provide an algorithm to relax the assumption of having options with
fixed policies, and we demonstrate that there are situations in which such an
approach could provide better guarantees in terms of sample complexity.

Outline In the following sections, we first introduce the problem and the
notion used. Then, Section 3 describes the main motivation behind this work
and the focus on the finite-horizon settings, and Section 4 describes the new
formalism introduced. The algorithm and its extension are described in Section
5, and the main result and its derivation are discussed in Sections 6 and 7.
Finally, we describe in detail the related works (Section 8) and discuss some
further directions of research beyond the present work.

##  2 Preliminaries

In this section, we provide the necessary background that will be employed in
the remainder of the paper.

#### Finite-Horizon MDPs

A Finite Horizon Markov Decision Process [MDP, Puterman, 2014] is defined as a
tuple $\mathcal{M}=(\mathcal{S,A},p,r,H)$, where $\mathcal{S}$ and
$\mathcal{A}$ are the finite state and the primitive action spaces,
respectively, $p(s^{\prime}|s,a,h)$ is the transition probability function
defining the probability of transitioning to state $s^{\prime}\in\mathcal{S}$
by taking action $a\in\mathcal{A}$ in state $s\in\mathcal{S}$ at stage
$h\in[H]$. $r(s,a,h)$ is the reward function that evaluates the quality of
action $a\in\mathcal{A}$ when taken in state $s\in\mathcal{S}$ at stage
$h\in[H]$, and $H$ is the horizon, which defines the duration of each episode
of interaction with the environment. The behavior of an agent is modeled by a
deterministic policy $\pi:\mathcal{S}\times[H]\rightarrow\mathcal{A}$ that
maps states $s\in\mathcal{S}$ and stages $h\in[H]$ to actions.

#### Semi-MDP

A Semi-Markov Decision Process [SMDP, Baykal-Gürsoy, 2010, Cinlar, 2013] is a
generalization of the MDP formalism. It admits _temporally extended_ actions,
which, contrary to _primitive_ ones (i.e., actions that execute for a single
time step), can execute for a certain time during which the agent has no
control over the decision process. A usual notion when treating SMDP is the
_duration_ or _holding time_ , $\tau(s,a,h)$, which is the number of primitive
steps taken inside a temporally extended action.

HRL builds upon the theory of Semi-MDPs, characterizing the concept of
temporally extended action with basically two main formalisms [Pateria et al.,
2021]: sub-tasks [Dietterich, 2000] and options [Sutton et al., 1999]. For the
sake of this paper, we focus on the options framework.

Options An option [Sutton et al., 1999] is a possible formalization of a
temporally extended action. It is characterized by three components
$o=(\mathcal{I}_{o},\beta_{o},\pi_{o})$.
$\mathcal{I}_{o}\subseteq\mathcal{S}\times[H]$ is the subset of states and
stages pairs $(s,h)$ in which the option can start,
$\beta_{o}:\mathcal{S}\times[H]\to[0,1]$ defines the probability that an
option terminates in a specific state-stage pair,
$\pi_{o}:\mathcal{S}\times[H]\to\mathcal{A}$ is the policy executed until its
termination. An example of an option could be a pre-trained policy to execute
a specific task in a control problem, such as picking up an object.

Exactly as stated by Sutton et al. [1999, Theorem 1] an MDP in which primitive
actions $\mathcal{A}$ are replaced by options $\mathcal{O}$, becomes an SMDP.
In this paper, we consider a hierarchical approach working for a two-level
hierarchy. On the top, the goal is to find the optimal policy
$\mu:\mathcal{S}\to\mathcal{O}$, which determines the optimal option for each
state-instant pair. Once an option is selected, out of the SMDP’s scope, its
policy is executed until its termination, and the control returns to the high-
level policy. An assumption is needed on the set of the given options [Fruit
et al., 2017].

######  Assumption 2.1 (Admissible options).

The set of options $\mathcal{O}$ is assumed admissible, i.e., all options
terminate in finite time with probability 1 and, $\\{\forall
o\in\mathcal{O},\,s\in\mathcal{S},\,\text{and }h\in[H],\ \exists
o^{\prime}\in\mathcal{O}:\beta_{o}(s,h)>0\ \text{and}\
(s,h)\in\mathcal{I}_{o^{\prime}}\\}$.

Lastly, we introduce an essential quantity for our analysis.

Regret The _regret_ is a performance metric for algorithms frequently used in
provably efficient RL. For any starting state $s\in\mathcal{S}$, and up to the
episode $K$, it is defined as:

$\displaystyle\textit{Regret(K)}\stackrel{{\scriptstyle\textit{\text{def}}}}{{=}}\sum_{k=1}^{K}V^{*}(s,1)-V^{\mu_{k}}(s,1)$
(1)

and evaluates the performance of the policy learned until episode $k$,
$V^{\mu_{k}}$ compared to the value of an optimal policy $V^{*}$.

###  2.1 Notation

In the following, we will use $\tilde{O}(\cdot)$ to indicate quantities that
depend on $(\cdot)$ up to logarithmic terms. $\mathbbm{1}(x=a)$ defines the
indicator function

$\displaystyle\mathbbm{1}(x=a)\stackrel{{\scriptstyle\textit{\text{def}}}}{{=}}\begin{cases}0,&\text{if}\
x\neq a\\\ 1,&\text{if}\ x=a\end{cases}$

In the analysis, we denote optimistic terms with $\sim$ and empirical ones
with $\land$, e.g., $\tilde{p}$ and $\hat{r}$ are, respectively, the
optimistic transition model and the estimated reward function.

##  3 Motivation and Intuition

Usually, in Reinforcement Learning, the complexity of a problem is highly
correlated to the planning horizon, which is even more natural in finite-
horizon MDPs. The regret analysis in the literature provides results for both
the lower and upper bound on the regret paid by an algorithm in this setting,
where there is a dependency on $H$.

Here comes our intuition, by using a hierarchical approach, we can
intrinsically reduce the planning horizon because the number of decisions
taken in $H$ time steps is scaled by a term closely related to the average
duration of each action, and thus, also the complexity scales with this
quantity. In addition, if the sub-tasks themselves need to be learned because
policies are not provided, simplification can also be induced in these new
problems. Under certain assumptions, they could have shorter horizons, and an
agent during the training can focus just on smaller regions of the entire
state space. Furthermore, the learning could be further guided by an
additional reward that could better specify the singular sub-problem.
Starting from this intuition, we analyze the performance of an algorithm in a
Finite Horizon Semi-MDP, considering a set of pre-trained options and,
afterward, its extension, which incorporates a first phase of options
learning. Lastly, we provide a comparative study with its flat counterpart.

##  4 Finite Horizon SMDP

In this section, we present a new formalism, _Finite-Horizon Semi-Markov
Decision Processes_ , that combines the notion used in FH-MDP with the concept
of temporal abstraction.

A finite-horizon semi-MDP is defined as a tuple
$\mathcal{SM}=(\mathcal{S,O},p,r,H)$, where $\mathcal{S}$ and $\mathcal{O}$
are the finite state and the temporally extended action spaces, respectively,
$p(s^{\prime},h^{\prime}|s,o,h)$ is the probability of ending to state
$s^{\prime}\in\mathcal{S}$, after $(h^{\prime}-h)$ steps, by playing the
temporally extended action $o\in\mathcal{O}$ in state $s\in\mathcal{S}$ at
stage $h\in[H]$. On the other hand, $r(s,o,h)$ is the expected reward
accumulated until the termination of the temporally extended action
$o\in\mathcal{O}$ played in state $s\in\mathcal{S}$ at stage $h\in[H]$ of the
episode. Finally, $H$ is the horizon of interaction, and still $\tau(s,o,h)$
is the number of primitive steps taken inside the temporally extended action.
The agent’s behavior is modeled by a deterministic policy
$\mu:\mathcal{S}\times[H]\rightarrow\mathcal{O}$ mapping a state
$s\in\mathcal{S}$ and a stage $h\in[H]$ to a temporally extended action. The
goal of the agent is to find a policy $\mu^{*}$ that maximizes the value
function, defined as the expected sum of the rewards collected over the
horizon of interaction and recursively defined as:

with the convention that $V^{\mu}(s,H)=0$. The value function of any optimal
policy is denoted by $V^{*}(s,h)\coloneqq V^{\mu^{*}}(s,h)$.

##  5 Algorithms

FH-SMDP-UCRLis a variant of the algorithm presented in Fruit and Lazaric
[2017], which in turn is inspired by UCRL2 [Auer et al., 2008] and adapted for
FH-SMDPs. This family of algorithms implements the principle of "optimism in
the face of uncertainty", which states that when interacting in unknown
environments—with an unknown model—the decisions have to be guided by a trade-
off between what we believe is the best option and by a term representing the
uncertainty on our estimates. More formally, it is introduced the so-called
_exploration bonus_ , which quantifies the uncertainty level on our
estimations of the model, computed from the observed samples. This exploration
bonus is used to regulate the exploration-exploitation dilemma, inducing the
algorithm to explore regions of the space with high uncertainty instead of
sticking to what seems to be the optimal solution and to overcome situations
in which the optimal solution resides in a region not yet discovered.

However, a direct application of these algorithms in our setting is
unfeasible, as they are designed for infinite-horizon average reward settings.
Due to the lack of methods operating in these settings, we need to design a
new algorithm for finite-horizon SMDPs following the same paradigm.

As displayed by Algorithm 1, at each episode $k$, we compute an estimate of
the SMDP model, by computing, from the collected samples up to episode $k$,
the empirical transition probability $\hat{p}_{k}$ and the reward function
$\hat{r}_{k}$.

(2) (3)

We then redefine the confidence intervals of these two quantities,
$\beta^{p}_{k}$ and $\beta^{r}_{k}$, respectively as

$\displaystyle\beta^{r}_{k}(s,o,h)\ \propto\
\sqrt{\frac{2\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)\ln
2/\delta}{n_{k}(s,o,h)}}+\frac{7\ln 2/\delta}{3(n_{k}(s,o,h-1)},$ (4)
$\displaystyle\beta^{p}_{k}(s,o,h)\ \propto\
\sqrt{\frac{S\log\bigl{(}\frac{n_{k}(s,o,h)}{\delta}\bigl{)}}{n_{k}(s,o,h)}},$
(5)

where $\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)$ is the sample variance
of the reward function. From the estimates and the confidence intervals just
defined, we can build the confidence sets $B_{k}^{p}$ and $B_{k}^{r}$, which
contain, with high probability, the true model. Being $\mathcal{SM}_{k}$ the
set of plausible SMDPs, characterized by rewards and transition within the
confidence sets, with $\mathcal{SM}_{k}$ and an adaptation of extended value
iteration [Auer et al., 2008], for FH-SMDP (Algorithm 2), we can compute the
optimistic policy $\tilde{\mu_{k}}$ and the relative optimistic value function
$\tilde{V}^{\mu_{k}}$. Then, by playing this policy for an entire episode, we
collect new samples and restart the process for the next episode $k+1$.

###  5.1 Option Learning

By relaxing the assumption of having a set of pre-trained options, considering
known just their initial state set and termination conditions, we can enhance
characteristics of problems more suited to be solved with a hierarchical
approach even when no pre-trained policies are provided.

We present a model-based algorithm divided into two phases, which initially
learns each option policy individually, and then exploits them to solve the
SMDP with FH-SMDP-UCRL. As Algorithm 3 shows, each option is considered as a
single FH-MDPs, defined based on its initial-state set and termination
probability, as
$\mathcal{M}_{o}=(\mathcal{S}_{o},\mathcal{A}_{o},p,r_{o},H_{o})$ where
$S_{o}\subseteq S$, $A_{o}\subseteq A$, $H_{o}\leq H$, which means that each
option operates on a restricted portion of the original problem, for a certain
fixed horizon $H_{o}$. The option’s optimal policy is the policy of the
relative sub-FH-MDP computed until episode $K_{o}$, which is the number of
episodes assigned to each option.

Nevertheless, if no assumption on the reward function is defined, the options’
optimal policies could be sub-optimal regarding the optimal policy computed by
a standard approach for that portion of the MDP, being the option’s scope
limited to a certain part of the MDP with the impossibility of having feedback
on what happens after its termination.
Therefore we need to state:

######  Assumption 5.1.

Given an MDP $\mathcal{M}=(\mathcal{S,A},p,r,H)$ and a set of options
$o\in\mathcal{O}$. Define $\pi_{o}^{*}$ as the optimal policy of the option
$o$ learned individually on the sub-MDP
$\mathcal{M}_{o}=(\mathcal{S}_{o},\mathcal{A}_{o},p,r_{o},H_{o})$ with
$S_{o}\subseteq S$, $A_{o}\subseteq A$, and $H_{o}\leq H$. The reward function
$r_{o}$ of the sub-MDP $\mathcal{M}_{o}$, which could differ from $r$, ensure
that

$\displaystyle\pi^{*}(s)=\pi_{o}^{*}(s)\leavevmode\nobreak\
\leavevmode\nobreak\ \forall s\in S_{o}$

with $\pi^{*}(s)$ the optimal policy on $\mathcal{M}$.

This assumption guarantees that the computed option’s optimal policy equals
the optimal policy of the entire problem in the option’s region.

Algorithm 1 UCRL-FH-SMDP

0: $\mathcal{S,O}\text{ with fixed policies, }H$Initialize $\mu_{0}$ at random
and $Q_{1}(s,o,h)=0$ for all $(s,o,h)\in\mathcal{S}\times\mathcal{O}\times[H]$

1: Execute $\mu_{0}$ for $H$ steps and collect tuples
$(s,o,h,s^{\prime},h^{\prime})$ and $r(s,o,h)$ to store in $\mathcal{D}_{1}$

2: for $k=1,\dots,K$ do

3: Compute $n_{k}(s,o,h)$

4: Estimate empirical SMDP
$\widehat{\mathcal{SM}}_{k}=(\mathcal{S,O},\hat{p}_{k},\hat{r}_{k})$ with
equations 2, 3.

5: Compute the confidence sets $B^{r}_{k}(s,o,h)$ and $B^{p}_{k}(s,o,h)$ using
the confidence interval (Eq. 4, 5)

6: Planning with Backward Induction for $\mu_{k}$, using an adaptation to
finite horizon of Extended Value Iteration [Auer et al., 2008] (Algorithm 2)

7: for $h=1,\dots,H$ do

8: Execute $o=\mu_{k}(s,h)$ until it terminates

9: Observe $(s^{\prime},h^{\prime})$ and $r(s,o,h)$

10: Add the tuple $(s,o,h,s^{\prime},h^{\prime})_{k}$ and $r_{k}(s,o,h)$ to
$\mathcal{D}_{k+1}$

11: Set $h=h^{\prime}$

12: end for

13: end for

Algorithm 2 Extended Value Iteration for FH-SMDP

1: Input: $\mathcal{S,O},B^{r}_{k},B^{p}_{k}$

2: Set $Q_{H+1}(s,o)=0$ for all $(s,o)\in\mathcal{S\times O}$

3: for $h=H\dots 1$ do

4: for $(s,o)\in\mathcal{S\times O}$ do

5: for $h^{\prime}=h+1\dots H+1$ do

6: Compute

7: end for

8: end for

9: end for

10: Output: $\mu_{k}(s,h)=\operatorname{argmax}_{o\in\mathcal{O}}Q_{hk}(s,o)$

Algorithm 3 Option Learning

1: Input: $\mathcal{S}_{o},\mathcal{A}_{o},H_{o},K_{o}$, and
$B^{r}_{k}(s,a),B^{p}_{k}(s,a)$ which are respectively the confidence sets of
the flat model.

2: Set $Q_{H_{o}+1}(s,a)=0$ for all $(s,a)\in\mathcal{S_{o}\times A_{o}}$

3: for $k=1,\dots,K_{o}$ do

4: Compute $n_{k}(s,a,h)$

5: Estimate empirical MDP
$\widehat{\mathcal{M}}_{k}=(\mathcal{S}_{o},\mathcal{A}_{o},\hat{p}_{k},\hat{r}_{k})$,
with an adaptation of eq. 2 and 3 for the flat model.

6: Planning by backward induction for $\pi_{o_{hk}}$ with Extended Value
Iteration for FH-MDPs [Ghavamzadeh et al., 2020], in the horizon $H_{o}$.

7: Play $\pi_{o_{k}}$ for an episode to collects new samples.

8: end for

9: Output: $\pi^{K_{o}}_{o}$.

##  6 Main Results

In this section, we present the main contributions of the paper, which in
particular are an upper bound on the regret of FH-SMDP-UCRL that highlights
particular problem-dependent features and, an upper bound on the regret of its
extension including a first phase of options learning.

######  Theorem 6.1.

Considering a non-stationary Finite Horizon SMDP $\mathcal{SM}$ and a set of
options $\mathcal{O}$, with bounded primitive reward $r(s,a)\in[0,1]$. The
regret suffered by algorithm FH-SMDP-UCRL, in $K$ episodes of horizon $H$ is
bounded as:

$\displaystyle\textit{Regret(K)}\leq\tilde{O}\Bigg{(}\Big{(}\sqrt{SOKd^{2}}\Big{)}\bigg{(}\overline{T}+\sqrt{S}H\bigg{)}\Bigg{)}$

with probability $1-\delta$.
Where:

$\displaystyle\overline{T}$
$\displaystyle=\max_{s,o,h}\sqrt{\operatorname*{\mathbb{E}}[\tau(o,s,h)^{2}]}$
$\displaystyle=\max_{s,o,h}\sqrt{\operatorname*{\mathbb{E}}[\tau(o,s,h)]^{2}+\operatorname{Var}[\tau(s,o,h)]},$

$\tau$ is the holding time, and $d$ describes the expected number of decisions
taken in one episode that is $d\approx H/\bar{\tau}$, with $\bar{\tau}$ the
average duration of the set of options.

This result introduces one of the main contributions, an option-dependent
upper bound on the regret in FH-MDP with options, not worst-case as in Fruit
and Lazaric [2017]. A dependency on the properties of an option set is
introduced, embodied into both $\overline{T}$ and $d$. The former gives the
same interesting consideration already underlined by Fruit and Lazaric [2017],
whereby the extra cost of having actions with random duration is only
partially additive rather than multiplicative. On the other hand, the latter
emphasizes the real benefit of using a hierarchical approach over a flat one.
The longer the expected duration of the set of options, the more the effective
horizon of the SMDP, $d$, decreases. Indeed, $d\approx\frac{H}{\bar{\tau}}$,
with $\bar{\tau}$ the average holding time of the options. Notice that there
is a $\sqrt{d}$ worsening factor, which comes from the fact that we consider a
non-stationary MDP in the analysis. This outcome is common in finite-horizon
literature [Azar et al., 2017, Dann et al., 2017, Zanette and Brunskill,
2018], where, instead, the regret increases by a factor of $\sqrt{H}$.

Let’s now analyze the regret suffered by the two-phase algorithm that first
learns each option policy and then subsequently solves the relative SMDP.

######  Theorem 6.2.

The regret paid by the two-phase learning algorithm until the episode K is:

$\displaystyle
Regret(K)\leq\tilde{O}\Big{(}K^{\frac{2}{3}}\sqrt[3]{H^{5}_{o}S^{2}_{o}A_{o}O}+\frac{H^{2}S}{H_{o}}\sqrt{OK}\Big{)}$

with $H_{o}$ the fixed horizon of each option $o\in\mathcal{O}$, $S_{o}$, and
$A_{o}$ the upper bounds on the cardinality of the state and action space of
the sub-FH-MDPs.

As mentioned before, we consider a situation where we allocate $K_{o}$
episodes for each option learning, hence $T_{1}=\sum_{o\in O}K_{o}H_{o}$, and
$K_{2}$ episodes for the SMDP policy learning at fixed options policies. Being
the algorithm divided into two phases, we expected a regret that scales with
$K^{2/3}$, a study of a more efficient algorithm is left for future works.

We now would like to understand if there are any situations in which such an
approach could produce more benefit compared to a standard one, to examine if
there are any classes of problems in which learning using a hierarchical
approach almost from scratch should be preferred to a standard one. Therefore
we conduct a comparison of regrets paid by this algorithm and a standard flat-
one, UCRL2 in particular.

We recall that the regret of UCRL2 adapted for non-stationary FH-MDPs
[Ghavamzadeh et al., 2020] is
$Regret(UCRL2-CH)\leq\tilde{O}(H^{2}S\sqrt{AK})$, thus the ratio between the
two regret bounds, $\mathcal{R}$, is

$\displaystyle\mathcal{R}=\frac{Regret_{SMDP}}{Regret_{MDP}}\leq\frac{K^{2/3}(H^{5}_{o}S^{2}_{o}A_{o}O)^{1/3}}{H^{2}S\sqrt{AK}}$

By considering particular relations between the option-MDP and the original
one, where $A_{o}=\alpha A$, $S_{o}=\alpha S$ and $H_{o}=\alpha H$, we can
rewrite this ratio as:

$\displaystyle\mathcal{R}\leq\frac{K^{1/6}\alpha^{3/8}O^{1/3}}{(HS)^{1/3}A^{1/6}}$
(6)

When $\mathcal{R}\leq 1$ is clearly beneficial to use this approach instead of
a standard one. Thus, by imposing this assumption, we can find the maximum
number of episodes for which this constraint is satisfied.

$\displaystyle K\leq\frac{H^{2}S^{2}A}{\alpha^{16}O^{2}}$

Remark While in general, a comparison of upper bounds is potentially loose, in
this case, the two upper bounds have been derived with similar techniques;
hence they would be _similarly loose_.

#### Final Sub-Optimality Remark.

In both results, we need to consider that, by using a defined option set, we
are introducing a bias. It could be that the optimal policy on the flat
problem is irreproducible by a concatenation of the policies of the options
chosen by the optimal high-level policy $\mu^{*}$. This is because the
structure introduced by the options can cause some states to become
inaccessible for the high-level SMDP. This issue is also treated by Fruit and
Lazaric [2017] and produces an additional term on the regret equal to
$V^{*}(M)-V^{*}(M_{O})$, where $M$ is the primitive MDP, and $M_{O}$ the same
MDP with options.

###  6.1 Renewal Process

The expected number of options played in one episode $d$, clearly depends on
the random duration of each of these options; hence it is itself a random
variable, and we would like to bound it with some quantity. Resorting to the
Renewal Theory [Smith, 1958], this corresponds to the Renewal Function $m(t)$.

######  Definition 6.3 (Renewal Process).

Let $S_{1},S_{2}\dots$ be a sequence of i.i.d. random variables with finite
and non-zero mean, representing the random time elapsed between two
consecutive events, defined as the holding time. For each $n>0$ we define
$J_{n}=\sum_{i=1}^{n}S_{i},$ as the time at which the $n^{th}$ event of the
sequence terminates. Then, the sequence of random variables $X_{t}$,
characterized as

$\displaystyle X_{t}=\sum_{n}^{\infty}\mathbb{I}_{\\{J_{n}\leq
t\\}}=\operatorname{sup}\\{n:J_{n}\leq t\\}$ (7)

constitutes a Renewal Process $(X_{t})_{t\geq 0}$, representing the number of
consecutive events that occurred up to time $t$.

######  Definition 6.4 (Renewal Function).

Considering a renewal process $(X_{t})_{t\geq 0}$, the renewal function $m(t)$
is the expected number of consecutive events that occurred by time $t$.

$\displaystyle m(t)=\operatorname*{\mathbb{E}}[X_{t}]$

Hence, it is possible to take inspiration from a bound of the renewal function
to bound the expected number of options played in one episode.

######  Lemma 6.5.

[Bound on number of options played in one episode] Considering a Finite
Horizon SMDP $\mathcal{SM}$ with horizon H and, $O$ options with duration
$\tau_{min}\leq\tau\leq\tau_{max}$ and
$\min_{o}(\operatorname*{\mathbb{E}}[\tau_{o}])$ the expected duration of the
shorter option. The expected number of options played in one episode $d$ can
be seen as the renewal function $m(t)$ of a renewal process up to the instant
$H$. With probability $1-\delta$ this quantity is bounded by

$\displaystyle d<\sqrt{\frac{32(\tau_{max}-\tau_{min})H(\ln
2-\ln{\delta})}{(\min_{o}(\operatorname*{\mathbb{E}}[\tau_{o}]))^{3}}}+\frac{H}{\min_{o}(\operatorname*{\mathbb{E}}[\tau_{o}])}$

Refer to the appendix for detailed proof of this result.

###  6.2 Fixed option length

Let’s now analyze a particular case to clarify the claim introduced with
Theorem 6.1. A scenario in which the given options are deterministic with
fixed length.

######  Corollary 6.6.

Considering a non-stationary Finite Horizon SMDP $\mathcal{SM}$ and a set of
deterministic option $O$ with fixed duration $\bar{\tau}$, the regret payed by
FH-SMDP-UCRL, after K steps is upper bounded by:

$\displaystyle\textit{Regret(K)}\leq\tilde{O}\Bigg{(}\frac{H}{\bar{\tau}}\Big{(}\sqrt{SOK}\Big{)}\bigg{(}\bar{\tau}+\sqrt{S}H\bigg{)}\Bigg{)}$

Proof. The result is trivially derived by substituting $d$ with the actual
number of decisions taken in one episode, which now is a defined number equal
to $H/\bar{\tau}$. Then, the same applied for $\overline{T}$ that, considering
options of length $\bar{\tau}$, is exactly $\bar{\tau}$.

This bound clearly shows a dependency on the choice of the options set. The
second term, which is the dominant one, is mitigated by the
$\sqrt{\bar{\tau}}$, thus reducing the sample complexity as expected. The
other $\sqrt{\frac{H}{\bar{\tau}}}$, as for Theorem 6.1, comes from the non-
stationarity of the SMDP.

###  6.3 Derivation of FH-MDP and parallelism with AR-SMDP.

To further strengthen the obtained result, we can show that considering some
assumptions, we can derive the upper bound by Auer et al. [2008] adapted to
FH-MDPs [Ghavamzadeh et al., 2020].

#### Finite Horizon MDP.

Referring to the result provided by Auer et al. [2008] adapted to the finite
horizon case [Ghavamzadeh et al., 2020], the regret in Finite Horizon MDPs
scales with $\tilde{O}(HS\sqrt{AT})$, or with
$\tilde{O}(H^{\frac{3}{2}}S\sqrt{AT})$ when the MDP in non-stationary. If, in
our upper bound, we substitute the cardinality of the option set $O$, with the
primitive-action space $A$. This leads to having $\overline{T}=1$ and $d=H$
because the primitive actions, by definition, terminate after a single time
step. Thus, the average duration of these single-step options is 1, and the
number of decisions taken in one episode is exactly $H$. Then, having bounded
primitive reward $r(s,a)\in[0,1]$, we can write our result as
$\tilde{O}(H^{\frac{3}{2}}S\sqrt{AKH})$ and considering the definition of
$T=KH$ [Dann et al., 2017, Azar et al., 2017, Zanette and Brunskill, 2018], we
obtain the same equation.

Remark We are aware of the tighter upper bounds in the Finite Horizon
literature by Azar et al. [2017], that get rid of a $\sqrt{HS}$, by tightly
bounding the estimation error $(\tilde{p}-p)\tilde{V}^{\mu_{k}}$ and their
exploration bonus in terms of the variance of $V^{*}$ at the next state, and
by using empirical Bernstein and Freedman’s inequalities [Maurer and Pontil,
2009, Freedman, 1975]. However, with this work, our main focus is to emphasize
the role played by the options set’s composition instead of providing a very
tight analysis. We still think the same tricks could be used in our analysis
to tighten the bound, but we leave that for future work.

#### Parallelism with Average Reward Setting.

Fruit and Lazaric [2017] showed that the regret in SMDPs with options when
considering bounded holding times, and $R_{max}=1$ scales with
$\tilde{O}(D_{\mathcal{O}}S_{\mathcal{O}}\sqrt{On}+T_{max}\sqrt{S_{\mathcal{O}}On})$.
On the other hand, considering the same assumptions, our result becomes of
order $\tilde{O}(HS\sqrt{OKd^{2}}+T_{max}\sqrt{SOKd^{2}})$. It is clearly
impossible to derive one setting from the other. Nevertheless, we can spot
some similarities between the two bounds. We can say that for finite-horizon
problems, the diameter $D$ coincides with the horizon $H$ [Ghavamzadeh et al.,
2020]. Besides, $Kd$ is exactly equal to $n$, the number of decisions made up
to episode $K$. The state space $S$ is the state space of the SMDP in our
formalism, which is the definition provided for $S_{O}$ in Fruit and Lazaric
[2017]. Consider, again, that the additional $\sqrt{d}$ comes from the fact
that we refer to a non-stationary FH-SMDP.

Thus, we prove that our result is a generalization of the case of FH-MDP and
closely relates to the result presented for the Average Reward Setting.

##  7 Proofs sketch

In this section, we provide the sketch proofs of theorem 6.1 and theorem 6.2.
Please refer to the appendix for all the details.

###  7.1 Sketch proof of theorem 6.1

We defined the regret in finite horizon problems as in eq. 1. Optimistic
algorithms work by finding an optimistic estimation of the model of the
environment to compute the optimistic value function and the optimistic
policy. Considering how the confidence sets are constructed, we can state that
$\tilde{p}\geq p$ and $\tilde{r}\geq r$, where terms without tilde are the
real one, hence, $V^{*}(s,h)\leq\tilde{V}^{\mu_{k}}(s,h)$ for all $h$. Thus,
we can bound eq. 1 with

$\displaystyle\textit{Regret(K)}\stackrel{{\scriptstyle\textit{\text{opt}}}}{{\leq}}\sum_{k=1}^{K}\tilde{V}^{\mu_{k}}(s,1)-V^{\mu_{k}}(s,1)$
(8)

Let’s now introduce a Performance Difference Lemma for FH-SMDPs.

######  Lemma 7.1.

[Performance Difference Lemma for FH-SMDP] Given two FH-SMDPs $\hat{M}$ and
$\tilde{M}$ with horizon $H$, and respectively rewards $\hat{r}$, $\tilde{r}$
and transition probabilities $\hat{p}$, $\tilde{p}$. The difference in the
performance of a policy $\mu_{k}$ is:

$\displaystyle\tilde{V}^{\mu_{k}}(s,1)-\hat{V}^{\mu_{k}}(s,1)$
$\displaystyle=\hat{\mathbb{E}}\bigg{[}\sum_{i=1}^{H}\Big{(}\big{(}\tilde{r}(s_{i},o_{i},h_{i})-\hat{r}(s_{i},o_{i},h_{i})\big{)}$
$\displaystyle+\big{(}\tilde{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})-\hat{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})\big{)}$
$\displaystyle\tilde{V}^{\mu_{k}}(s_{i+1},h_{i+1})\Big{)}\mathbbm{1}\\{h_{i}<H\\}\bigg{]}$

where $\hat{\operatorname*{\mathbb{E}}}$ is the expectation taken w.r.t.
$\hat{p}$ and $\mu_{k}$.

Note that the summation steps are not unitary but skip according to the length
of the transitions $h^{\prime}-h$. The derivation of this lemma follows the
one provided by Dann et al. [2017] for FH-MDPS that is commonly used in
literature [Azar et al., 2017, Zanette and Brunskill, 2018]. Check the
appendix for further details.

Now we can use lemma 7.1 to substitute the difference of value function in eq.
8 and we can upper bound both the difference of $r$ and $p$, with 2 times
their confidence intervals and the optimistic value
$\tilde{V}^{\mu_{k}}(s_{i+1},h_{i+1})$ with the horizon $H$ \- we consider
bounded primitive reward $r(s,a)\in[0,1]$.

$\displaystyle\textit{Regret(K)}\leq\sum_{k=1}^{K}\mathbb{E}\bigg{[}\sum_{i=1}^{H}\Big{(}2\beta_{k}^{r}+2\beta_{k}^{p}H\Big{)}\mathbbm{1}\\{h_{i}<H\\}\bigg{]}$

In the Finite-Horizon literature[Dann et al., 2017, Zanette and Brunskill,
2018], two terms are commonly used in the proofs: (1) $w_{k}(s,o,h)$ that is
the probability of taking the option $o$, in state $s$ at time step $h$, which
clearly depends on the policy $\mu_{k}$ and the transition probability of the
real SMDP, (2) $L_{k}$, which defines the set of episodes visited sufficiently
often, and the set of $(s,o,h)$ that were not visited often enough to cause
high regret. Therefore, for using the same approach to conduct the proof, we
can substitute the expectation $\operatorname*{\mathbb{E}}$, which is taken
w.r.t. the policy $\mu_{k}$ and the real transition probability
$p(s^{\prime},h^{\prime}|s,o,h)$, with

$\displaystyle\sum_{(s,o,h)\in L_{k}}w_{k}(s,o,h)$

We defined the confidence intervals of $r$ and $p$, as in the equations 4, 5,
respectively using Empirical Bernstein Inequality [Maurer and Pontil, 2009],
Hoeffding [1963] and Weissman et al. [2003].

By substituting these definitions and the term just introduced, we get, up to
numerical constants, that the regret is bounded by

######  Lemma 7.2.

Considering a non-stationary MDP M with a set of options as an SMDP
$M_{\mathcal{O}}$ [Sutton et al., 1999]. In $M_{\mathcal{O}}$ the number of
decisions taken in the $k^{th}$-episode is a random variable $d$ and

Therefore, the following holds true:

or, using the same notation used in Fruit and Lazaric [2017],
$\tilde{O}(\sqrt{SOKd^{2}})$, with $n=Kd$ the number of decisions taken up to
episode $K$.

Substituting the result of Lemma 7.2 in the equation of the regret, we get

where as mentioned above, $d$ is the expected number of decision steps taken
in one episode, $n$ is the total number of decisions taken up to episode $k$,
and $\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)$ is the empirical variance
of the reward that emerged from the use of Empirical Bernstein inequality. A
dependency on the variance of the reward is not that explainable for what we
want to show; hence we upper bound this term by the square root of the
empirical variance $\overline{T}$ of the duration of the options seen up to
episode $k$, and this complete the proof.

###  7.2 Sketch proof of theorem 6.2

In order to prove the regret paid by the two-phase algorithm, we first
consider that we can write the regret as the sum of the regret paid in the
first phase and the regret paid in the second one, plus an additional bias
term. In the first phase, we pay full regret for each option learning, then
the maximum average regret considering the option learning as a finite horizon
MDP with horizon $H_{o}$, and the regret of the SMDP learning with fixed
options

(9)

Where $K_{2}$ are the episodes used for the SMDP learning, and $K=\sum_{o\in
O}K_{o}+K_{2}$. Then considering that we allocate $K_{o}$ episodes for each
option learning, and $A_{o}$ and $S_{o}$ are respectively the upper bounds on
the action-space cardinality and state-space cardinality of the options set,
we can get rid of the $\max_{o\in\mathcal{O}}$. Now bounding $K_{2}\leq K$, we
can find the optimal $K_{o}$ in closed form, and substituting it in Equation
9, we conclude the proof.

##  8 Related Works

In the FH-MDP literature, several works provide an analysis of the regret of
different algorithms. Osband and Van Roy [2016] present a lower bound that
scales with $\Omega(\sqrt{HSAT})$. On the other hand, many other works propose
various upper bounds for their algorithm. The most common upper bound is the
adaptation of Auer et al. [2008] proposed by Ghavamzadeh et al. [2020], which
is of the order of $O(HS\sqrt{AT})$. This result has then been improved in the
following papers. An example is Azar et al. [2017], which proposes a method
with an upper bound on the regret of $O(\sqrt{HSAT})$ that successfully
matches the lower bound. As mentioned above, both upper and lower bounds
depend on $H$.

Nevertheless, few works focused on theoretically understanding the benefits of
hierarchical reinforcement learning approaches, and, to the best of our
knowledge, this is the first to analyze these aspects in FH-SMDPs. To conduct
our analysis, we take inspiration from the paper by Fruit and Lazaric [2017],
in which they propose an adaptation of UCRL2 [Auer et al., 2008] for SMDPs.
They first study the regret of the algorithm for general SMDPs and then focus
on the case of MDP with options, providing both a lower bound and a worst-case
upper bound. This work was the first that theoretically compares the use of
options instead of primitive actions to learn in SMDPs. Nonetheless, it
focuses on the average reward setting to study how it is possible to induce a
more efficient exploration by using options, and it assumes fixed options.
Differently, we aim to analyze the advantages of using options to reduce the
sample complexity of the problem, resorting to the intuition that temporally
extended actions can intrinsically reduce the planning horizon in FH-SMDPs.
Furthermore, we provide an option-dependent upper bound, instead of a worst-
case one, that better quantifies the impact of the option duration on the
regret. Other works providing a theoretical analysis of hierarchical
reinforcement learning approaches are Fruit et al. [2017], which is an
extension of the aforementioned work in which the need for prior knowledge of
the distribution of cumulative reward and duration of each option is relaxed.
Even in this case, they consider the average reward setting, and the objective
is identical.

Then, Mann et al. [2015] study the convergence property of Fitted Value
Iteration (FVI) using temporally extended actions, showing that a longer
duration of options and pessimistic estimates of the value function lead to
faster convergence. Finally, Wen et al. [2020] demonstrate how patterns and
substructures in the MDP provide benefits in terms of planning speed and
statistical efficiency. They present a Bayesian approach exploiting this
information, and they analyze how sub-structure similarities and sub-problems’
complexity contribute to the regret of their algorithm.

##  9 Conclusions

In conclusion, we propose a new algorithm for Finite Horizon Semi Markov
decision processes called FH-SMDP-UCRL, and we provide theoretical evidence
that supports our original claim. Using hierarchical reinforcement learning,
it is provably possible to reduce the problem complexity of a Finite Horizon
problem when using a well-defined set of options. This analysis is the first
for FH-SMDP and provides a form of option-dependent analysis for the regret
that could be used to define objectives for options discovery methods better.
Furthermore, by relaxing the assumption of having a set of fixed options’
policies, we were able to provide insights on classes of problems in which a
hierarchical approach from scratch would still be beneficial compared to a
flat one. In the future, we would like to improve the algorithm proposed for
options learning to tighten the theoretical guarantees and further
characterize this family of problems. Finally, we would like to investigate,
following the ideas of Wen et al. [2020], how the structure of the MDP could
appear in our bound, which, in our opinion, is a fundamental point to put
another brick in the direction of total understanding on the promising power
of HRL.

## References

  * Auer et al. [2008] Peter Auer, Thomas Jaksch, and Ronald Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Azar et al. [2017] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pages 263–272. PMLR, 2017.
  * Bacon et al. [2017] Pierre-Luc Bacon, Jean Harb, and Doina Precup.  The option-critic architecture.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * Baykal-Gürsoy [2010] Melike Baykal-Gürsoy.  Semi-markov decision processes.  _Wiley Encyclopedia of Operations Research and Management Science_ , 2010.
  * Cinlar [2013] Erhan Cinlar.  _Introduction to stochastic processes_.  Courier Corporation, 2013.
  * Dann et al. [2017] Christoph Dann, Tor Lattimore, and Emma Brunskill.  Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Dietterich [2000] Thomas G Dietterich.  Hierarchical reinforcement learning with the maxq value function decomposition.  _Journal of artificial intelligence research_ , 13:227–303, 2000.
  * Dvoretzky et al. [1956] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz.  Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator.  _The Annals of Mathematical Statistics_ , pages 642–669, 1956.
  * Freedman [1975] David A Freedman.  On tail probabilities for martingales.  _the Annals of Probability_ , pages 100–118, 1975.
  * Fruit and Lazaric [2017] Ronan Fruit and Alessandro Lazaric.  Exploration-exploitation in mdps with options.  In _Artificial intelligence and statistics_ , pages 576–584. PMLR, 2017.
  * Fruit et al. [2017] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill.  Regret minimization in mdps with options without prior knowledge.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Ghavamzadeh et al. [2020] Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta.  Exploration in reinforcement learning.  Tutorial at AAAI’20, 2020.  URL https://rlgammazero.github.io/.
  * Hoeffding [1963] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  _Journal of the American Statistical Association_ , 58(301):13–30, 1963.
  * Levy et al. [2019] Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko.  Learning multi-level hierarchies with hindsight.  In _Proceedings of International Conference on Learning Representations_ , 2019.
  * Mann et al. [2015] Timothy A Mann, Shie Mannor, and Doina Precup.  Approximate value iteration with temporally extended actions.  _Journal of Artificial Intelligence Research_ , 53:375–438, 2015.
  * Maurer and Pontil [2009] Andreas Maurer and Massimiliano Pontil.  Empirical bernstein bounds and sample variance penalization.  _arXiv preprint arXiv:0907.3740_ , 2009.
  * Nachum et al. [2018] Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine.  Data-efficient hierarchical reinforcement learning.  _Advances in neural information processing systems_ , 31, 2018.
  * Osband and Van Roy [2016] Ian Osband and Benjamin Van Roy.  On lower bounds for regret in reinforcement learning.  _arXiv preprint arXiv:1608.02732_ , 2016.
  * Pateria et al. [2021] Shubham Pateria, Budhitama Subagdja, Ah-hwee Tan, and Chai Quek.  Hierarchical reinforcement learning: A comprehensive survey.  _ACM Computing Surveys (CSUR)_ , 54(5):1–35, 2021\.
  * Pinelis [2019] Iosif Pinelis.  Dkw type inequality for renewal processes.  MathOverflow, 2019.  URL https://mathoverflow.net/q/326434.
  * Precup and Sutton [1997] Doina Precup and Richard S Sutton.  Multi-time models for temporally abstract planning.  _Advances in neural information processing systems_ , 10, 1997.
  * Puterman [2014] Martin L Puterman.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons, 2014.
  * Smith [1958] Walter L Smith.  Renewal theory and its ramifications.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 20(2):243–284, 1958.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Sutton et al. [1999] Richard S Sutton, Doina Precup, and Satinder Singh.  Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning.  _Artificial intelligence_ , 112(1-2):181–211, 1999.
  * Vezhnevets et al. [2017] Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu.  Feudal networks for hierarchical reinforcement learning.  In _International Conference on Machine Learning_ , pages 3540–3549. PMLR, 2017.
  * Weissman et al. [2003] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.  Inequalities for the l1 deviation of the empirical distribution.  _Hewlett-Packard Labs, Tech. Rep_ , 2003.
  * Wen et al. [2020] Zheng Wen, Doina Precup, Morteza Ibrahimi, Andre Barreto, Benjamin Van Roy, and Satinder Singh.  On efficiency in hierarchical reinforcement learning.  _Advances in Neural Information Processing Systems_ , 33:6708–6718, 2020.
  * Zanette and Brunskill [2018] Andrea Zanette and Emma Brunskill.  Problem dependent reinforcement learning bounds which can identify bandit structure in mdps.  In _International Conference on Machine Learning_ , pages 5747–5755. PMLR, 2018.

##  Appendix A Detailed proof of Theorem 6.1

###  A.1 Notation and Setting

First, we need to define the value function of an SMDP. In Sutton et al.
[1999] it is defined as a formalism for MDP with options, that itself, by the
demonstration presented in the same article, is an SMDP.
In our case, however, for the SMDP model, we are considering an additional
dependency on $h\in[0,H]$.
Notation used:

  * •

$H$ is the horizon

  * •

$\mu$ policy over options $\\{\mu:S\times O\times H\rightarrow[0,1]\\}$

  * •

$r(s,o,h)$ is the discounted cumulative reward gained by selecting the option
$o$, in state $s$, in the instant $h$ of the horizon $H$

  * •

$p(s^{\prime},h^{\prime}|s,o,h)$ is a new transition model that characterizes
both the state dynamic and the time the option executes.

  * •

$w(s,o,h)$ is the probability of playing option $o$ being in state $s$ at
time-step $h$

The value function is defined as:

$\displaystyle V^{\mu}(s,h)$ $\displaystyle=\sum_{o\in
O_{s}}\mu(s,o,h)\Bigl{[}r(s,o,h)+\sum_{s^{\prime},h^{\prime}>h}p(h^{\prime},s^{\prime}|s,o,h)V^{\mu}(s^{\prime},h^{\prime})\Bigr{]}$
(10)

with $V^{\mu}(s,H)=0$.

###  A.2 Performance Difference Lemma

Difference in value of a policy $\mu$ in two different SMDPs ( $\tilde{}$ and
$\bar{}$ )

$\displaystyle\tilde{V}^{\mu_{k}}(s,1)-\bar{V}^{\mu_{k}}(s,1)$

$\displaystyle=\hat{\mathbb{E}}\bigg{[}\sum_{i=1}^{H}\Big{(}\big{(}\tilde{r}(s_{i},o_{i},h_{i})-\bar{r}(s_{i},o_{i},h_{i})\big{)}+\big{(}\tilde{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})-\bar{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})\big{)}\tilde{V}^{\mu_{k}}(s_{i+1},h_{i+1})\Big{)}\mathbbm{1}\\{h_{i}<H\\}\bigg{]}$

$\hat{\mathbb{E}}$ is the expectation taken w.r.t. the policy $\mu$ and the
transition probability $\hat{p}(s^{\prime},h^{\prime}|s,o,h)$, and can be
rewrite as:

$\displaystyle\prod_{i=1}^{H}\mu_{k}(s_{i},o_{i},h_{i})\hat{p}_{k}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})\mathbbm{1}\\{h_{i}<H\\}$

This quantity is the distribution of visits for the policy $\mu_{k}$ in the "
$\hat{}$ " SMDP and it is equivalent to $w_{tk}$ for the FH-MDP case.

###### Proof.

The result follows by unrolling equation 10. Lemma E.5 Dann et al. [2017] for
an example in FH-MDPs. ∎

###  A.3 Confidence Intervals

The confidence sets are defined as:

$\displaystyle B^{r}_{k}(s,o,h):=[\hat{r}_{k}(s,o,h)-\beta^{r}_{k}(s,o,h),\
\hat{r}_{k}(s,o,h)+\beta^{r}_{k}(s,o,h)]$ $\displaystyle
B^{p}_{k}(s,o,h):=\bigl{\\{}p_{k}(\cdot,\cdot|s,o,h)\in\nabla(s):\|\tilde{p}_{k}(\cdot,\cdot|s,o,h)-\hat{p}_{k}(\cdot,\cdot|s,o,h)\|_{1}\leq\beta^{p}_{k}(s,o,h)\bigr{\\}}$

and the relative confidence bounds $\beta^{r}_{k}(s,o,h)$ and
$\beta^{p}_{k}(s,o,h)$ using Empirical Bernstein bound [Maurer and Pontil,
2009], Hoeffding [1963] and Weissman et al. [2003].

$\displaystyle\beta^{r}_{k}(s,o,h)\ \propto\
\sqrt{\frac{2\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)\ln
2/\delta}{n(s,o,h)}}+\frac{7\ln 2/\delta}{3(n-1)}$ (11)
$\displaystyle\beta^{p}_{k}(s,o,h)\ \propto\
\sqrt{\frac{S\log\bigl{(}\frac{n_{k}(s,o,h)}{\delta}\bigl{)}}{n_{k}(s,o,h)}}$
(12)

with $\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)$ be the sample variance
of r.

$\displaystyle\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)=\frac{1}{n(n-1)}\sum_{1\leq
i\leq j\leq n}(r_{i}-r_{j})^{2}$ (13)

###  A.4 Actual Proof

See 6.1

###### Proof.

Regret(K) $\displaystyle=\sum_{k=1}^{K}V^{*}(s,1)-\bar{V}^{\mu_{k}}(s,1)$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{Opt.}}}}{{\leq}}\sum_{k=1}^{K}\tilde{V}^{\mu_{k}}(s,1)-\bar{V}^{\mu_{k}}(s,1)$
$\displaystyle=\sum_{k=1}^{K}\bar{\mathbb{E}}\bigg{[}\sum_{i=1}^{H}\Big{(}\big{(}\tilde{r}(s_{i},o_{i},h_{i})-\bar{r}(s_{i},o_{i},h_{i})\big{)}+\big{(}\tilde{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})-\bar{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})\big{)}\tilde{V}^{\mu_{k}}(s_{i+1},h_{i+1})\Big{)}$
$\displaystyle\mathbbm{1}\\{h_{i}<H\\}\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{a}}}}{{=}}\sum_{k}\sum_{i\in[H]}\sum_{(s,o,h)\in
L_{k}}w_{k}(s_{i},o_{i},h_{i})\biggl{(}\bigl{(}\tilde{r}(s_{i},o_{i},h_{i})-\bar{r}(s_{i},o_{i},h_{i})\bigr{)}$
$\displaystyle+\bigl{(}\tilde{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})-\bar{p}(s_{i+1},h_{i+1}|s_{i},o_{i},h_{i})\bigr{)}^{T}\tilde{V}^{\mu_{k}}(s_{i+1},h_{i+1})\biggr{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{b}}}}{{\leq}}\sum_{k}\sum_{i\in[H]}\sum_{(s,o,h)\in
L_{k}}w_{k}(s_{i},o_{i},h_{i})\Big{(}2\beta^{r}_{k}(s_{i},o_{i},h_{i})+2\beta^{p}_{k}(s_{i},o_{i},h_{i})^{T}H\Big{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{c}}}}{{\propto}}\sum_{k}\sum_{i\in[H]}\sum_{(s,o,h)\in
L_{k}}w_{k}(s_{i},o_{i},h_{i})\bigg{(}\sqrt{\frac{\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)}{n_{k}(s,o,h)}}+\frac{1}{n_{k}(s,o,h)-1}+\sqrt{\frac{S}{n_{k}(s,o,h)}}H\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{d}}}}{{\leq}}\sum_{k}\sum_{i\in[H]}\sum_{(s,o,h)\in
L_{k}}\frac{w_{k}(s_{i},o_{i},h_{i})}{\sqrt{n_{k}(s_{i},o_{i},h_{i})}}\bigg{(}\sqrt{\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)}+\sqrt{S}H\bigg{)}+\sum_{k}\sum_{i\in[H]}\sum_{(s,o,h)\in
L_{k}}\frac{w_{k}(s_{i},o_{i},h_{i})}{n_{k}(s,o,h)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{e}}}}{{\leq}}\tilde{O}\Bigg{(}\Big{(}\sqrt{dSOn}\Big{)}\bigg{(}\sqrt{\hat{\operatorname*{\mathbb{V}\mathrm{ar}}}(r)}+\sqrt{S}H\bigg{)}+dSO\Bigg{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{f}}}}{{\leq}}\tilde{O}\Bigg{(}\Big{(}\sqrt{dSOn}\Big{)}\bigg{(}R_{max}\overline{T}+\sqrt{S}H\bigg{)}+dSO\Bigg{)}$

with

$\displaystyle\overline{T}=\max_{s,o,h}\sqrt{\operatorname*{\mathbb{E}}[\tau(o_{i},s_{i},h_{i})^{2}]}=\max_{s,o,h}\sqrt{\operatorname*{\mathbb{E}}[\tau(o_{i},s_{i},h_{i})]^{2}+\text{Var}[\tau(s_{i},o_{i},h_{i})]}$
(14)

with $\tau$ representing the average duration of the set of options seen so
far.

The first passage is a standard inequality when proving the regret in
frameworks adopting optimism in face of uncertainty.

  1. (a)

The expectation with respect to the policy $\mu_{k}$ and the transition model
$\bar{p}$ can be replaced with a more common formulation used in the Finite
Horizon literature [Dann et al., 2017, Zanette and Brunskill, 2018],
$\sum_{(s,o,h)\in L_{k}}$.
Where, $L_{k}$ is defined as the good set [Dann et al., 2017, Zanette and
Brunskill, 2018], which is the number of episodes in which the triple
$(s,o,h)$ is seen sufficiently often, and this equation is valid for all the
tuples $(s,o,h)$ being part of this set.

  2. (b)

We upper bound the difference of rewards and transition probabilities with two
times their relative confidence intervals, and, the Value function at the next
step with the horizon length $H$.

  3. (c)

We substitute the confidence intervals with their definitions (eq. 12)
neglecting logarithmic terms.

  4. (d)

We divide the summation in two, to upper bound the terms separately

  5. (e)

Using the adaptation of lemma 16 of Zanette and Brunskill [2018] for SMDPs,
lemma 7.2, for the first term. Using passage (b) and (c) in the proof of lemma
E.1

  6. (f)

Upperbounding the sample variance of $r$, with $R_{max}\overline{T}$. Where
$\overline{T}$ is the sample variance of the duration.

∎

##  Appendix B Special Case of fixed-length options

Let’s consider the same finite horizon MDP with options with fixed length
$M:=<S,O,R_{h},P_{h},H,\bar{\tau}>$ where each option $o:=<I,\pi^{o},\beta>$
has a fixed initial set $I$ and fixed termination condition $\beta$,
$R_{h}(s,o)\in[0,\bar{\tau}R_{max}]$ is the expectation of the reward function
distribution, $P_{h}(\cdot|s,o)$ is the transition distribution, $H$ is the
horizon, and $\bar{\tau}\leq H$ is the options fixed length. The solution of
the MDP will be a policy $\pi^{H}:S\rightarrow O$ that maximizes the
cumulative return choosing among options’ optimal policies $\pi^{o_{i}}$. The
reward function over $state-options$ pairs relates to the flat-MDP’s reward
as:

$\displaystyle
R_{h}(s,o)=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s_{0}=s\\\
a_{i}\sim\pi^{o}(\cdot|s_{i})\\\ s_{i+1}\sim
p_{h+1}(\cdot|s_{i},a_{i})\end{subarray}}\biggl{[}\sum_{i=0}^{\bar{\tau}-1}r_{h+i}(a_{i},s_{i})\biggr{]}$

Denote with $V^{\pi^{H}}_{n}(s)$ the state value function associated with a
hierarchical policy $\pi^{H}$ (with Hierarchical policy we define a policy
that chooses among options).

$\displaystyle
V^{\pi^{H}}_{n}(s)=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s_{0}=s\\\
o_{j}\sim\pi^{H}(\cdot|s_{j})\\\ s_{j+1}\sim
P(\cdot|s_{j},o_{j})_{h}\end{subarray}}\biggl{[}\sum_{j=0}^{N}R_{h\times\bar{\tau}}(s_{j},o_{j})\biggr{]}$

with $N=\frac{H}{\bar{\tau}}$ the number of decision steps that occurs during
the Horizon.
In this way, we can exploit the same performance difference lemma of Dann
[Dann et al., 2017] Lemma E.15, where, instead of actions we have fixed length
options, and we sum over $N$ decision steps. Hence, we can write:

Regret(K)
$\displaystyle\stackrel{{\scriptstyle\textit{\text{Opt.}}}}{{\leq}}\sum_{k=1}^{K}\tilde{V}^{\pi^{H}_{k}}_{1}(s)-\bar{V}^{\pi^{H}_{k}}_{1}(s)$
(15)
$\displaystyle\stackrel{{\scriptstyle\textit{\text{a}}}}{{=}}\sum_{k}\sum_{n\in[N]}\sum_{(s,o)\in
L_{k}}w_{nk}(s,o)\biggl{(}\bigl{(}\tilde{R}_{n}(s,o)-\bar{R}_{n}(s,o)\bigr{)}+\bigl{(}\tilde{P}_{n}(s,o)-\bar{P}_{n}(s,o)\bigr{)}^{T}\tilde{V}^{\pi_{k}}_{n+1}\biggr{)}$
(16) $\displaystyle+\textit{term considering the state-options pairs inside
the failure event}$ (17)

here $w_{nk}(s,o)$ is the probability of visiting state $s$ and choosing
option $o$ there at the decision step n in the $k$-th episode.

Then, we consider a new formulation of the confidence sets:

$\displaystyle B^{R}_{nk}(s,o):=[\hat{R}_{nk}(s,o)-\beta^{R}_{nk}(s,o),\
\hat{R}_{nk}(s,o)+\beta^{R}_{nk}(s,o)]$ $\displaystyle
B^{P}_{nk}(s,o):=\bigl{\\{}P_{nk}(\cdot|s,o)\in\nabla(s):\|\tilde{P}_{nk}(\cdot|s,o)-\hat{P}_{nk}(\cdot|s,o)\|_{1}\leq\beta^{P}_{nk}(s,o)\bigr{\\}}$

using Hoeffding [1963] and Weissman et al. [2003] the confidence bounds are:

$\displaystyle\beta^{R}_{nk}(s,o)\ \propto\
R_{max}\bar{\tau}\sqrt{\frac{\log\bigl{(}\frac{n_{nk}(s,o)}{\delta}\bigr{)}}{n_{nk}(s,o)}}$
(18) $\displaystyle\beta^{P}_{nk}(s,o)\ \propto\
\sqrt{\frac{S\log\bigl{(}\frac{n_{nk}(s,o)}{\delta}\bigl{)}}{n_{nk}(s,o)}}$
(19)

After the definition of the confidence sets we can bound the previous equation
as follow:

$\displaystyle\sum_{k=1}^{K}\tilde{V}^{\pi^{H}_{k}}_{1}(s)-\bar{V}^{\pi^{H}_{k}}_{1}(s)$
$\displaystyle=\sum_{k}\sum_{n\in[N]}\sum_{(s,o)\in
L_{k}}w_{nk}(s,o)\biggl{(}\bigl{(}\tilde{R}_{nk}(s,o)-\bar{R}_{nk}(s,o)\bigr{)}+\bigl{(}\tilde{P}_{nk}(s,o)-\bar{P}_{nk}(s,o)\bigr{)}^{T}\tilde{V}^{\pi_{k}}_{h+1}\biggr{)}$
$\displaystyle+\textit{term considering the state-options pairs inside the
failure event}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{a}}}}{{\leq}}\sum_{k}\sum_{n\in[N]}\sum_{(s,o)\in
L_{k}}w_{nk}(s,o)\biggl{(}2\beta^{R}_{nk}+2{\beta^{P}_{nk}}^{T}(H-\bar{\tau})\biggr{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{b}}}}{{\propto}}\sum_{k}\sum_{n\in[N]}\sum_{(s,o)\in
L_{k}}w_{nk}(s,o)\biggl{(}\frac{R_{max}\bar{\tau}}{\sqrt{n_{nk}}}+\sqrt{\frac{S}{n_{nk}}}(H-\bar{\tau})\biggr{)}$
$\displaystyle=\sum_{k}\sum_{n\in[N]}\sum_{(s,o)\in
L_{k}}\frac{w_{nk}(s,o)}{\sqrt{n_{nk}}}\biggl{(}R_{max}\bar{\tau}+\sqrt{S}(H-\bar{\tau})\biggr{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{c}}}}{{\leq}}\tilde{O}\Bigl{(}N\sqrt{SOK}\bigl{(}R_{max}\bar{\tau}+\sqrt{S}H-\sqrt{S}\bar{\tau}\bigr{)}\Bigr{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{d}}}}{{\leq}}\tilde{O}\Bigl{(}N\sqrt{SOK}\bigl{(}R_{max}\bar{\tau}+\sqrt{S}H)\Bigr{)}$

  1. (a)

substituting the $\tilde{R}_{n}(s,o)-\bar{R}_{n}(s,o)$ and
$\tilde{P}_{n}(s,o)-\bar{P}_{n}(s,o)$ with double the relative confidence
interval and considering $\tilde{V}^{\pi_{k}}_{h+1}\leq(H-\bar{\tau})$. The
second term will be omitted for ease of notation.

  2. (b)

replacing the confidence intervals with their definition

  3. (c)

Lemma E.3

  4. (d)

considering the worst case, where there isn’t the negative term

comparing it with the bound of Fruit and Lazaric [2017] for bounded holding
time:

$\displaystyle\tilde{O}\Bigl{(}\bigl{(}D_{o}\sqrt{S}+T_{max}+(T_{max}-T_{min})\bigr{)}R_{max}\sqrt{S_{O}On}\Bigr{)}$

that having options with fixed duration $\bar{\tau}$, and considering
$R_{max}=1$ reduces to:

$\displaystyle\tilde{O}\Bigl{(}DS\sqrt{On}+\bar{\tau}\sqrt{SOn}\Bigr{)}$

we have the same bound where instead of the diameter we have the Horizon $H$,
and where $NK$ is exactly equal to the number of the decisions up to episode
$k$, which is $n$ in their notation. We have:

$\displaystyle\tilde{O}\Bigl{(}HS\sqrt{ON^{2}K}+\bar{\tau}\sqrt{SON^{2}K}\Bigr{)}$

Important: Note that we have an additional $\sqrt{N}$ terms because we
considered non-stationary MDP. This is a well-known penalty term when
considering non-stationarity in the process.

##  Appendix C Proof of Theorem 6.2

See 6.2

###### Proof.

The regret of the two-phase algorithm can be written in this form

$\displaystyle Regret(K)$
$\displaystyle=\sum_{k=1}^{K_{1}}V_{*}^{*}(s,1)-V_{(\pi_{k})}^{\mu}(s,1)+\sum_{k=k_{1}}V_{*}^{*}(s,1)-V^{\mu_{k}}_{\pi_{K_{1}}}$
$\displaystyle=\underbrace{\sum_{k=1}^{K_{1}}V_{*}^{*}(s,1)-V_{(\pi_{k})}^{\mu}(s,1)}_{\text{Options
learning
Regret}}+\sum_{k=K_{1}}^{K}\underbrace{V_{*}^{*}(s,1)-V^{*}_{(\pi_{K_{1}})}}_{\text{Bias}}+\underbrace{V^{*}_{(\pi_{K_{1}})}-V^{\mu_{k}}_{(\pi_{K_{1}})}}_{\text{Regret
SMDP with fixed options}}$

The regret is the sum of the regret paid in the first phase and the regret
paid in the second one, plus an additional bias term. By assuming all options
with equal samples $K_{o}$ and the options’ policies learning as $O$ finite
horizon MDPs for which $S_{o},A_{o},H_{o}$ are the upper bounds of the
option’s state space dimension, the option’s action space dimension and the
option’s horizon, and $K_{1}=\sum_{o\in O}K_{o}$ and

$\displaystyle K=\sum_{o\in O}K_{o}+K_{2}$ (20)

we can write the regret as

$\displaystyle Regret(K)\leq\sum_{o\in O}K_{o}H_{o}+K_{2}\max_{o\in
O}\frac{1}{K_{o}}H^{2}_{o}S_{o}\sqrt{A_{o}K_{o}}+HS\sqrt{Od^{2}K_{2}}$

In which we pay full regret for each option learning, then the maximum average
regret considering the option learning as a finite horizon MDP with horizon
$H_{o}$, and the regret of the SMDP learning with fixed options.
However, considering the options with equal samples and with
$S_{o},A_{o},H_{o}$ the upper bounds of the relative quantities we can get rid
of the maximization in the second term, and $d=\frac{H}{H_{o}}$ and the regret
became

$\displaystyle Regret(K)$ $\displaystyle\leq
OK_{o}H_{o}+\frac{K_{2}}{K_{o}}H^{2}_{o}S_{o}\sqrt{A_{o}K_{o}}+\frac{H^{2}}{H_{o}}S\sqrt{OK_{2}}$

Now, by substituting $K_{2}$ with eq. 20, and upper bounding $(K-OK)\leq K$ we
can solve in closed form to find $K_{o}$ to minimize the regret.

$\displaystyle Regret(K)\leq
OK_{o}H_{o}+\frac{K}{K_{o}}H^{2}_{o}S_{o}\sqrt{A_{o}K_{o}}+\frac{H^{2}}{H_{o}}S\sqrt{OK}$
$\displaystyle K_{o}=\sqrt[3]{\frac{K^{2}S^{2}_{o}H^{2}_{o}A_{o}}{O^{2}4}}$

Therefore, by substituting $K_{o}$ in the original equation we have

$\displaystyle
Regret(K)\leq\tilde{O}\Big{(}K^{\frac{2}{3}}(H^{5}_{o}S^{2}_{o}A_{o}O)^{\frac{1}{3}}+\frac{H^{2}S}{H_{o}}\sqrt{OK}\Big{)}$

∎

Now we can compare the regret of this algorithm compared to the regret of
UCRL2 adapted for non-stationary FH-MDPs [Ghavamzadeh et al., 2020].

$\displaystyle Regret(UCRL2-CH)\leq\tilde{O}(H^{2}S\sqrt{AK})$

$\displaystyle\frac{Regret_{SMDP}}{Regret_{MDP}}\leq\frac{K^{1/6}\alpha^{3/8}O^{1/3}}{(HS)^{1/3}A^{1/6}}\leq
1$ (21) $\displaystyle K\leq\frac{H^{2}S^{2}A}{\alpha^{16}O^{2}}$ (22)

##  Appendix D Renewal Processes

######  Lemma D.1 (Renewal Function Bound).

Considering a Renewal process, $(X_{t})_{t\geq 0}$, and a sequence
$S_{1},S_{2}\dots$ of random variables, characterizing the random duration of
an event, alternatively defined as holding time, with
$supp(S_{i})\in\\{1,\dots,H\\}$. We can bound, with probability $1-\delta$,
the expected number of random events that occurred up to time $t$, $X_{t}$,
with:

$\displaystyle X_{t}<\sqrt{\frac{\ln 2-\ln{\delta}}{cK}}+\frac{t}{\mu}$

with $c=\frac{\mu^{3}}{32\sigma^{2}T}$ where $\mu$ is the mean of the r.v.s
and $\sigma^{2}$ the variance.

###### Proof.

Based on the proof presented on Pinelis [2019], which apply DKW type
inequalities to renewal processes [Dvoretzky et al., 1956]

$\displaystyle\Pr\left(\sup_{0\leq t\leq
T}\left|{\frac{X_{nt}}{n}-\frac{t}{\mu}}\right|\geq\epsilon\right)\leq
2e^{-cn\epsilon^{2}}$

Now we can equal $2e^{-cn\epsilon^{2}}$ to $\delta$ and find $\epsilon$.

$\displaystyle\epsilon=\sqrt{\frac{\ln 2-\ln\delta}{cn}}$

Thus with probability $1-\delta$

$\displaystyle X_{t}\leq\sqrt{\frac{\ln 2-\ln{\delta}}{cn}}+\frac{t}{\mu}$

that completes the proof ∎

The following lemma is lemma 6.5 in the main paper. See 6.5

###### Proof.

The proof followed the one of lemma D.1 and the fact that we are considering
$T=H$, $n=1$, $t=H$, $\mu=\bar{\tau}$, $\sigma^{2}=(\tau_{max}-\tau_{min})$,
and $X_{t}=d$. ∎

##  Appendix E Usefull Lemmas

######  Lemma E.1 (lemma 16 [Zanette and Brunskill, 2018] for non stationary
MDPs).

The following holds true:

$\displaystyle\sum_{k}\sum_{h\in[H]}\sum_{(s,a)\in
L_{k}}w_{hk}(s,a)\sqrt{\frac{1}{n_{k}(s,a,h)}}=\tilde{O}(\sqrt{HSAT})$

where the extra $\sqrt{H}$ is due to the non-stationarity of the environment

###### Proof.

$\displaystyle\sum_{k}\sum_{h\in[H]}\sum_{(s,a)\in
L_{k}}w_{hk}(s,a)\sqrt{\frac{1}{n_{k}(s,a,h)}}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{a}}}}{{\leq}}\sqrt{\sum_{k}\sum_{h\in[H]}\sum_{(s,a)\in
L_{k}}w_{hk}(s,a)}\sqrt{\sum_{k}\sum_{h\in[H]}\sum_{(s,a)\in
L_{k}}w_{hk}(s,a)\frac{1}{n_{k}(s,a,h)}}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{b}}}}{{=}}\sqrt{KH}\sqrt{\sum_{k}\sum_{h\in[H]}\sum_{(s,a)\in
L_{k}}w_{hk}(s,a)\frac{1}{n_{k}(s,a,h)}}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{e}}}}{{\leq}}\tilde{O}(\sqrt{HSAT})$

Then:

$\displaystyle\sum_{k}\sum_{h\in[H]}\sum_{(s,a)\in
L_{k}}\frac{w_{hk}(s,a)}{n_{k}(s,a,h)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{c}}}}{{\leq}}\sum_{h\in[H]}\sum_{(s,a)\in
L_{k}}\sum_{k}\frac{w_{hk}(s,a)}{\frac{1}{4}\sum_{j\leq k}w_{hj}(s,a)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{d}}}}{{\leq}}4HSA\log\biggl{(}\frac{Ke}{w_{min}}\biggr{)}$
$\displaystyle\stackrel{{\scriptstyle\textit{\text{$\sim$}}}}{{\propto}}HSA$

  1. (a)

by Cauchy-Schwartz

  2. (b)

$\sum_{t\in[H]}\sum_{(s,a)\in L_{k}}w_{tk}(s,a)=H$ lemma 17 (b) Zanette and
Brunskill [2018]

  3. (c)

lemma 2 Zanette and Brunskill [2018] adapted to the non-stationary case

  4. (d)

lemma E.5 Dann et al. [2017] considering that being (s,a) part of the good set
$L_{k}$, then we are assuming (Appendix E.3 Dann et al. [2017]) that
$w_{k}(s,a)\geq w_{min}$.

  5. (e)

substituting (f) we get the upper bound, and we conclude the proof.

∎

######  Lemma E.2 (lemma 16 [Zanette and Brunskill, 2018] for SMDPs (Lemma 7.2
main paper)).

Considering a non-stationary MDP M with a set of options as an SMDP
$M_{\mathcal{O}}$ [Sutton et al., 1999]. In $M_{\mathcal{O}}$ the number of
decisions taken in the $k^{th}$-episode is a random variable $d$ and

$\displaystyle\sum_{i\in H}\sum_{(s,o)\in
L_{k}}w_{k}(s_{i},o_{i},h_{i})\mathbbm{1}\\{h_{i}<H\\}=d_{k}\ \text{with}\
\\{\forall k:d_{k}\leq H\\}$

with mean $d$. Therefore, the following holds true:

$\displaystyle\sum_{k}\sum_{i\in H}\sum_{(s,o)\in
L_{k}}w_{k}(s_{i},o_{i},h_{i})\sqrt{\frac{1}{n_{k}(s_{i},o_{i},h_{i})}}=\tilde{O}\biggl{(}\sqrt{SOKd^{2}}\biggr{)}$

or, more generally, using the same notation used in Fruit and Lazaric [2017]

$\displaystyle\sum_{k}\sum_{i\in H}\sum_{(s,o)\in
L_{k}}w_{k}(s_{i},o_{i},h_{i})\sqrt{\frac{1}{n_{k}(s_{i},o_{i},h_{i})}}=\tilde{O}\biggl{(}\sqrt{dSOn}\biggr{)}$

with $n$ number of decisions taken up to episode $k$.

###### Proof.

Due to the stochasticity of the option’s duration, $d$ is a random variable
expressing the number of decisions taken in a step. Thus, first, we can
rewrite passage $(b)$ of the proof of lemma 17 Zanette and Brunskill [2018]
then, we change lemma E.1 considering the same notion of good set considered
in the appendix of Zanette and Brunskill [2018] and the validity of lemma 2 of
Zanette and Brunskill [2018], in the options framework(replacing $o$ with
$a$). If all the aforementioned assumptions hold, thus the derivation of the
new lemma follows the derivation of lemma E.1 ∎

######  Lemma E.3 (lemma 16 [Zanette and Brunskill, 2018] for MDPs with
options of fixed lenght).

For an MDP with $O$ options, with a fixed lenght $\bar{\tau}$, where the
horizon is divided in $N=\frac{H}{\bar{\tau}}$ decision steps, the following
holds true:

$\displaystyle\sum_{k}\sum_{n\in N}\sum_{(s,o)\in
L_{k}}w_{nk}(s,o)\sqrt{\frac{1}{n_{k}(s,o)}}=\tilde{O}\biggl{(}N\sqrt{SOK}\biggr{)}$

###### Proof.

In this MDP the control returns to the hierarchical policy after exactly
$\bar{\tau}$ time steps (the length of an option), thus, we can have at most
$N=\frac{H}{\bar{\tau}}$ actions in the horizon $H$. For this reason, passage
(b) of the proof of lemma E.1 become

$\displaystyle\sum_{n\in N}\sum_{(s,o)\in L_{k}}w_{nk}(s,o)=N$

The rest results for the same passage of the proof of lemma E.1. ∎

To have a more complete analysis we need also to consider the triples (s, o,
h) which aren’t inside the good set. To do that, we can adapt Lemma 3 of
Zanette and Brunskill [2018], for the FH-SMDP setting.

######  Lemma E.4 (Outside the good set).

It holds that:

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{d}\sum_{(s,o,h)\notin
L_{k}}w_{k}(s,o,h)=\tilde{O}(SOd)$

The proof follows from the one of lemma 3 of Zanette and Brunskill [2018].