An Option-Dependent Analysis of Regret Minimization Algorithms in Finite-Horizon Semi-MDP
Authors: Gianluca Drappo
Alberto Maria Metelli
Marcello Restelli
Venue: Accepted by TMLR ()

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, is still preferable a hierarchical approach over a standard one.

Published in Transactions on Machine Learning Research (09/2023)
An Algorithms in
Analysis of Regret Minimization Semi-MDP
Gianluca Drappo
Deportment of Electronics, Information and Bioengineering Politecnico Milano
gianluca. cranluec.ddappo@polliii
Alberto Maria Metelli
Department of Electronics, Information and Bioengineering Politecnico di Milano
abbertomrria.mttelliSppiii...
Marcello Restelli
Department of Electronics, Information and Bioengineering Politecnico di Milano
mareello.reatellä@hollmm..
Reviewed on OpenReview: https: /ttps://openn/ee opwp://veepreeeeee..mmmm net/ formmo id- VP9p4u9jAo
Abstract
A large variety of real-world Reinforcement Learning (RL) tasks are characterized by 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 those problems thanks to a convenient multi-level docomposition of the lasks, making their solution accessible. Although often used practice, few works provide theoretical guarantees 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 option-dependent upper bound to the regret suffered by regret minimization algorithms in finitehhorzon 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, is still preferable hierarchical approach over standard one.
1 Introduction
Hierarchical Reinforcement Learning (HRL. Pateria et al. 2021 is a learning paradigm that decomposes long-horizon Reinforcement Learning (RL, Sutton & Barto 2018 task into sequence of potentially shorter and simpler sub-tasks. The sub-tasks could be further divided, generating a hicrarchical structure organized at arbitrary levels. Fach 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 induced only once the control reaches the leaf nodes, where the policies choose among the primitive actions (i.e., actions of the original MDP 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 & 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 al. 2019 Vezhnevets et al. 2017 Bacon et al. 2017 Nachum al. 2018

---

Published in Transactions on Machine Learning Research (09/2023)
However, such evidence is mainly emerging in practical applications, and the theoretical understanding of the inherent reasons for these advantages is still underdeveloped. Only 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 & Lazaric (2017) focus on the exploration benefit of using options in average reward problems. Finally, 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 by analyzing the impact of temporal abstraction the complexity of finite-horizon problems, class in which the influence of hierarchical structure naturally emerges. The complexity of solving a finite-horizon MDP depends on the length of the planning horizon. Intuitively, the longer the planning horizon, the more complex the problem. Introducing a hierarchy of sub-tasks temporally partitioned the problem into many different potentially shorter sub- problems. As mentioned above, once a level policy selects an action, the control passes to the lower level until the sub-task terminates. Typically, if the hicrarchy is well constructod, a sub-task would exccute for more than one primitive step; during which the high-level has neither control over what is happening, and often, nor visibility. Thus, concerning policy that selects among sub-tasks, the number of actions (sub-tasks in this case) played in one episode depends on the duration of the available sub-tasks and is smaller than the original amount. This procedure produces an actual planning horizon reduction, scaled down by this term proportional to the sub-tasks duration, resulting in a less complex problem than the original one.
Firstly, we extend the formalism of FH-MDP to include temporally extended actions, defining an FH-SMDP. Then, we show that standard algorithms for FH-MDPs, can not be used to find a solution in this new setting, being unable to treat temporally extended actions properly. Therefore, we propose an approach, FH-SMDP- UCRL, to solve Finite-Horizon Semi-Markov Decision Processes when a set of fixed pre-trained sub-tasks policies are given (options) to theoretically demonstrate this effective improvement in complexity compared to a standard approach for Finite-Horizon MDPs. Moreover, to move toward a more realistic application of Hicrarchical methods, we provide insights to characterize problems in which the benefits above persist approach (Lattimore &
even when no fixed policies are available. We present an Heelore-Then-Coniiee Szeeesvári, 2020), that first separately learns each sub-task policy and then exploits FH-SMDP-UCRLL to solve the SMDP with fixed policies. Afterward, we theoretically prove that this second approach would also benefit performance in specific MDPs compared to standard approach. Eventually, both these results could help to discriminate among problems in which hierarchical approach could be more effective than a standard one.
Contributions The paper's contributions can be summarrizd 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 (Section 4. (2) We conducted a regret analysis of this algorithm, providing an option-dependen 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 to search for options minimizing this regret (Section 4.1. (3) For the sake of our analysis, we formulate the notion of Finite Horizon SMDP
and a performance difference lemma for this setting (Section 3 7 (4) We conducted a finer analysis to bound the expected number of temporally extended actions selected in one episode, resorting to the renewal
process theory (Section 5). (5) Lastly, we extend our analysis to the options policies learning; we present an Saplore-Then. "Phen-Commit approach and characterize a class of problems more efficiently solvable through a Hierarchical approach, even when no set of pre-trained policies is available (Section 6 Therefore, we demonstrate that there are problems for which better guarantees in terms of sample complexity are achieved when solved by a hicrarchical approach when both a set of fixed options are provided and not.
2 Preliminaries and Problem Definition
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 M= (S,A.p,r, H), where S and A are the finite state and the primitive action spaces, respectively, p(s') |8, a, h) is the transition probability function defining the probability of transitioning to state s' S by
2

---

Published in Transactions on Machine Learning Research (09/2023)
taking action E A in state s E S at stage h E [H] quality of action E A when taken in state 8 E S at stage h E [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 π S x [H] + A that maps states 8 E S and stages E
ah) is the reward function that evaluates the
[H] to actions.
Semi-MDP A Semi-Markov Decision Process (SMDP, Baykal-Girsoy 2010 Cinlar 2013) is gener- alization of the MDP formalism. It admits temporally extended actions, which, contrary to primitive ones (i.e., actions that execute for single time step), can execute for 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, 7(8, 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 temporally extended action, which generalize the standard primitive onos. It can be seen as fixed policy that acts on its own when selected until its termination. It consists of three components 0 = (Zo, Bo To)- Io C S x [H] is the subset of states and stages pairs (s, h) in which the option can start, 8, : S x [H] - [o, 1] defines the probability that an option terminates in a specific state-stage pair, To : Sx [M] + A is the policy executed until its termination. An example of an option could be a policy that, a control problem, executes just a specific task, such as picking up an object.
MDP in which primitive actions A are replaced by options O, becomes an SMDP. This paper considers a hicrarchical approach for problems with two-level of temporal abstractioos.. At the high level, the problem is seen as divided into different sub-tasks, the options, and at the low level, each sub-task is considered a problem on its own. More formally, on the top, the goal is to find the optimal policy μ : S x [H] + O, which determines the optimal option for each state-instant pair, and thus defines the optimal sequence of sub-task execute. On the other hand, at the bottom, the problem is to find the optimal option's 's policy to execute the respective sub-task individually. In this work, we first consider situation in which the latter has already been solved, and a set of fixed policies are given. Then, we discuss solution when this assumptiion fails. Regarding the former situation, an assumption is needed on the set of options (Fruit et al. 2017) to reach a proper optimal solution.
Problem Definition Exactly as stated by Sutton et al. 1999 Theorem 1)
A Assumption 2.1 (Admissible options). The set of options O is assumed admissible, i... (Yo E O, S, and h E [M], 3o' O Bo,s, h) and hs E I.r].
Average per-episode duration In the following analysis, we will refer to d as the average per-episode number of decisions laken in an episode of length H.
d == KΣΣΣ ds(s,,,h)
(1)
LEO #ES NE(H]
where ds,s, o, h) is the number of times lemporally extended action (or option) o has been selected in state s, in step h, in the episode i of interaction with the environment. This quantity is a random variable, being dependent on the duration of the options, which is a random variable in turn.
2.1 Notation
In the following, we will use Ô(-) to indicate quantitics that depend on (-) up to logarithmic terms. 1(x = a) defines the indicator function
1 (x = a) def
0,
if x
1, if ===
In the analysis, we denote optimistic terms with and empirical ones with A, e.g., P and & are, respectively, the optimistic transition model and the estimated reward function.
3

---

Published in Transactions on Machine Learning Research (09/2023)
3 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 defined as a tuple SM = (S,O,p.T,H) H), where S and O are the finite state and the temporally extended action spaces, respectivcly, o(s,, is the probability of ending to state s E S, after (h' (h'-h) h) steps, by playing the lemporally extended action E O in state 8 S al stage h [M]] On the other hand, r(s, o, h) is the expected reward accumulated until the termination of the temporally extended action o E O played in state 8 E S at stage h E [H] of the episode. Finally, H is the horizon of interaction, and we define as T(s, o, h) the random mumber of primitive steps taken when playing a temporally
extended action o. The agent's 's behavior is modeled by a deterministic policy μ:: S x [H] + O mapping a state 8 and a stage h E [M] to a temporally extended action. The goal of the agent is to find a policy
μ² that maximizes the value function, defined as the expected sum of the rewards collected over the horizon of interaction and recursively defined as:
(s, = Eies ( (r(s, ((s, + V=((
with the convention that (" H) = 0. The value function of any optimal policy is denoted by V*(s, = Ve" hs.
To evaluate the performance of an algorithm in this setting, as commonly used in the provably efficient RT. literature Auer et al. (2008); Azar et al. (2017); Zanette & Brunskill (2018); Fruit & Lazaric (2017), we define the regret in FH-SMDP as:
Regret For any starting state E S, and up to the episode K:
K
Regret(K) def Σ (s, ('th
(2)
evaluates the performance of the policy learned until episode k, VP compared to the value of an optimal policy V*, with n² the optimal policy selecting among options.
Even if this formalism is an extension of FH-MDP, it is impossible to apply the same algorithms used to solve FH-MDPs directly. The main complication, which will also appear in the analysis, is the uncortainty over the duration of the temporally extended actions. The number of decision steps taken in one episode is unknown because it depends on the random number of steps for which each selected temporally extended action exccutes.
For this reason, in the next section, we propose novel algorithm for this setting.
4 FH-SMDP-UCRL
FH-SMDP-UCRT. is a variant of the algorithm presented in Fruit & Lazaric (217)). which in turn is inspired by UCRL2 (Auer et al. 2008) and adapted for PHHSMMPs. This family of algorithms implements the princi- ple of optimismm in the face of uncertainty', which states that when interacting in unknown environments with an unknown model option and by a term representing the uncertainty on our estimates. More formally, the so-called exploration bonus is introduced, 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-ezplue explootatzliiinonn dilemma, in- ducing 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.
decisions have to be guided by a trade-off between what we believe is the best
However, directly applying these algorithms in our setting is unfcasible, as they are designed for infinite- horizon average reward settings. Due the lack of methods operating in these settings, we must design a new algorithm for finite-horizon SMDPs following the same paradigm.
4

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm 1: UCRI-FH-SMDP
Input: 8, with fixed policies, H, K
Initialize No at random and Qi h) 0 for all (s 8 O [M] Execute MM for H steps and collect tuples (s,,, hh) and r(s, h) to store in D1 ;
for k = l,..... K do
Compute ns, o, h));
Estimate empirical SMDP SM = (S, Pk. fx) with equation 3 equation
Compute the confidence sets [s, o, h) and (s, o, h) using the confidence interval (equation
equation 6);
Planning with Backward Induction for Pk. using adaptation to finite horizon of Extended Value
Iteration (Auer et al. 2008) (Algorithm
for h = =l...... 1...., H do
Execute 0 = (s, h) until it terminates; Observe (s', and r(s, o, h);
Add the tuple (s, o, h, s', N')x and o,(s,o,h) h) De+1: Set h h;;
end end
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 Pa and the reward function kk.
Pu (166,,18,,,11) Et o(s,,,,,,ss.. (s,0,,,, (
(3)
(2(5,,,h)
hx) Σ (s,
(4)
We then redefine the confidence intervals of these two quantities, 8 and 3r. respectively
2Vr 2/0 (x (s, 0,h)
7 2/8
h) x
+ 3(nx (8, o, 11)
(5)
S Slog me(e,o.)))
k, V (8(88, o,
(6)
where Var(r) is the sample variance of the reward function. From the estimates and the confidence intervals just defined, model. Then, define SM₁, the set of plausible SMDPs, characterized by rewards and transition models within the confidence sets. Given SM₁ we can compute the oplimistic policy μãs and the relative optimistic value function Vrs. We use an adaptation of extended value iteration (Auer et al. 2008) for FH-SMDP, Algorithm 2 which admits multi-step transitions and, thus, temporally extended actions.
build the confidence sets By and By, which contain, with high probability, the true
Then, by playing this policy for an entire episode, we collect new samples and restart the process for the next episode + 1.
4.1 Regret Analysis
In this section, we theoretically analyze the regret suffered by FH-SMDP-UCRL. In particular, we provide upper bound highlighting the options set's 's dependency.

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm 2: Extended Value Iteration for FH-SMDP
Input: S,O, Bg Bg
Set Q=+1 (s, 0) 0) = for all =5x0)xxx0)
for h H
do
for (8,0) E d
for h' = 1... H do Compute;
Qna(s,0)= max r(s,0,h) + max Ey Isw.
((, PEB((.,0)))
Vi*(s) = min - (h' 1), max Qwk(s,0)}
oEO
end end end
Output: (s) argmaX Q))
Theorem 4.1. Considering non-slalionary Finile Horizon SMDP SM and set of options O with bounded primitive reward r(s, a.) E [0. The regret suffered by algorithm FH-SMDP-UCRI, in K episodes of horizon H is bounded as:
RKgrel(K) S 2ō ((V50kez)
(T+VSH))
VSH)
with probability 1 8. Where:
T = max / O[ s,o,h ([ (
max s,0,h
is the holding time, the random number of primétive steps taken when playing temporully extended action o, and d is the average per-episode wumber of played oplions.
This result introduces one of the main contributions, an option-dependent upper bound the regret in FH- MDP with options, not worst-case in Fruit & Lazaric (2017). A dependency the properties of option set is introduced, embodied into both T and d. The former gives the same interesting consideration already underlined by Fruit & 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. Considering only the dominant term, the regret of FH- SMDP-UCRL, scales with O(HSVOK)P) where which directly depends on the average duration of each option selected. While the regret of UCRL2 adapted to the finito-horizon setting scales with Ó(HSV AKFSAKHHH)) when considering non-stationary transitions. By definition, d < H, however, for specific classes of problems with well-constructed hierarchy, d < H, and O < A, which finally proves the gain in the complexity of using a hierarchical approach over a standard one, clearly this valid when a proper set of fixed options is given.
the average per-episode number of played options,
4.2 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 (Ghavamzadch et al., 2020). and, by doing particular consideration, the regret of the algorithm designed for average reward settings.
possible to underline some similarity between our result and the upper bound

---

Published in Transactions on Machine Learning Research (09/2023)
4.2.1 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 O(HSVAT), or with O( SS S AT) when the MDP is non-stationary,
the sense that the transition kernel different for each step E [M]. If, in our upper bound, we substitute the cardinality of the option set O, with the primitive-action space A. This leads to having T -- 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) a) E [0.1] we can write our result as Ó(HESVAKH and considering the definition of T = KH DDnnn et al. 2017 Azar et al. 2017 Zanette & 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 v VHS, by tightly bounding the estimation error (ū- 1 V) 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 & Pontil 2009 Freedman 1975). However, with this work, our primary focus is to emphasize the role played by the options set's composition instead of providing 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.
4.2.2 Parallelism with Average Reward Setting
Fruit & Lazaric 2017) showed that the regret paid by their algorithm, designed for the Average Reward setting when considering bounded holding times, and Rmaz = upper bounded by with ODDoSo + T Tmax v On)... By doing the same, hence considering bounded holding times and Rmaz 1, our result becomes of order Ö(HSVOKd + Taaz VSO It is clearly impossible to derive one setting from the other. Nevertheless, we can spot some similaritics between the two bounds. For Amite-horizon problems, the diameter D coincides with the horizon H (Ghavanzadeh et al.) 2020). Besides, Kd equals n, the number of decisions made up to episode K. Then, the state space S is the state space of the SMDP in our formalism, which is the definition provided for So in Fruit & Lazaric (2017). The only difference is the additional Vd, which is considered in our work contrary to what has been done in Fruit & Lazaric (017)) due to non-stationary transitions.
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.
5 Renewal Process
In this section, provide more accurate analysis of d, the average per-episode number of options that are selected in an episode of Horizon H, which, mentioned above, is random variable. We resort to the renewal processes theory Smith (1958) to provide an upper bound on this quantity, which turns out to depend on both the horizon H and the options set.
The number of options selected one episode clearly depends on the random duration of each option; hence, it is a random variable, and we would like bound it with some quantity. Resorting to the Renewal Theory (mmihh 1958), this has an analogy with the Renewal Function m(t).
Definition 5.1 (Renewal Process). Let S₁, S2... ... be a sequence of i.idd 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 Jn Dn St, as the time which the th event of the sequence terminates. Then, the sequence of random variables Xe, characterized
X, Σ lu.54 sup(n: Jn S
constitutes a Renewal Process (X1) representing the number of consecutive events that occurred up time t.

---

Published in Transactions on Machine Learning Research (09/2023)
Definition 5.2 (Renewal Function). Considering renewal process (Xi)120, the renewal function m(t) is the expected number of consecutive events that occurred by time L.
m(t) = E[x]]
Hence, it possible to take inspiration from bound of the renewal function to bound d for a single episode of length H.
Lemma 5.3. [Bound on number of options played in one episodej Considering Finite Horizon SMDP SM with horizon H and, O oplions with duralion Tmin S S Tmaz and (il,((()).))) the expected duralion of the shorter option. The expected number of options played in one episode d can be seen as the renewal function m(l) of renewal process up to the instand H. With probability 1 Ö, this quantity is bounded by
32 Tmaz Tmin (In 2- - In
H
d < <<
(E(r.))())
min. (E(To)
This bound can also be considered bound for d, being worst-case, because the denominator is lower bounded by min, (E(ro)) which is the expected duration of the shorter option. Refer to the appendix for detailed proof of this result.
6 Option Learning
Clearly, having a set of pre-trained options does not properly characterizes a realistic scenario. Tt would be more interesting to study situations in which we relax the assumption of having a set of pre-trained options and consider known just their initial state set and termination conditions. We can highlight characteristics of problems more suited to be solved with a hierarchical approach rather than standard ones.
To address this analysis, we decide to present model-based two-phase approach, Algorithm 4 which uses Algorithm 3 to learn each option policy individually and subsequently exploits them to solve the SMDP with FH-SMDP-UCRL. As Algorithm 3 shows, each option is considered
single FH-MDP, defined based its initial-state set and termination probability, as MM = (S.. A.. p. To, Ho) where S, S S, A. S A, Ho < H. which means that each option operates on a restricted portion of the original problem, for a specific fixed horizon H.. The option's optimal policy the policy of the relative Sub-FH-MDP computed until episode Ko, 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 certain part of the MDP with the impossibility of having feedback on what happens after its termination.
Therefore we need to state:
Assumption 6.1. Given an MDP M = (S,A, H) and set of options o E O, which define a Semi- MDP S.M. Define म. as the optimal policy of the option o learned individually on the sub-MDP M. = (S.. Ao. P. To, H.) with S, C S, Ao S A, and H. S H. The reward function ra of the sub-MDP Mo, which could differ from r, ensure that
" 7s()= (s)) As E. Yo E (s)))
with (s) the optimal policy on M, and n² (s) the optimal policy on SM.
This assumption guarantees that the computed option's optimal policy equals the optimal policy of the entire problem in the option's region for all the options selected by the optimal SMDP policy μ².
This assumption is required to highlight the convenience a hierarchical solution compared to a standard (flat) onc. There exist several problems in which this condition verified. For instance, let us consider a manipulation task in which robot has to pick a die that shows a number, and place it in differently defined location, changing the displayed number. This problem could be divided into four different. individual
8

---

Published in Transactions on Machine Learning Research (09/2023)
problems, the object pick-up, the rotation of the die, the movement of an object from specific position to second one, and the drop of the object. When considering all these problems individually, each optimal policy learned separately for each skill would equal an optimal policy learned when considering the problem as a whole for the same states. Indeed, the best possible policy to pick up an object would be similar we consider the problem as whole or restricted to a particular region of the stale-action space, which crucial just for this specific task.
With the result presented in the following section, this assumption characterizes class problems in which such approach should be preferred to standard one.
Algorithm 3: Option Learning
Input: the option and K. Compute H. for the option
Set +0,+1(5,3) a) = 0 for all (s,a) (S, S) x (A. A):
for = l,....,, Ko do
Sample randomly (s, in Io:
Compute ne(s, a, h):
Estimate empirical MDP Me = (S., Aor Pk, fx), with an adaptation of eq. and 4 for the flat model.;
Compute the confidence sets (s a, h) and (, a, h) using adaptation the confidence interval (equation [] equation 6) for the flat model;
Planning by backward induction for Toss with Extended Value Iteration for FH-MDPs
GGaaamzzach et al. 2020), in the horizon H,:
Play Top for episode to collect new samples.;
end
Output: To.
Algorithm 4: Two-Phase Algorithm
Input: set of oplions O with random policies, K,, and K
for o E O do K. Option Learning(o, Ko);
end Output: FH SMDP UCRI H,K KoHo)
6.1 Theoretical Analysis Option Learning
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. This result then used to characterize the problems in question. Theorem 6.2. The regret paid by the two-phase learning algorithm until the episode K is:
Regret( s ( H858400 HSV
with Ho max.go Ho, and So, and Ao, respectively, the upper bounds on the cardinalily of the state and action space of the sub-FH-MDPs.
This result shows the regret paid by this two-phase approach for both option learning and the SMDP resolution. The sccond term, the non-dominant in the K (number of cpisodes) dependency, is preciscly the regret paid by PH-SMDP-UCRL. On the other hand, the dominant one comes from the two-phase analysis and encloses both the regret paid for the option learning and the bias paid for stopping this procedure at certain point before the convergence the optimal options policics. We note that scales with R2/3 but it was expected for the Explore- Explore-Then- 2020). However, studying more efficient algorithm is left for future work.
nature of the proposed algorithm (Lattimore & Szepesvári

---

Published in Transactions on Machine Learning Research (09/2023)
Given this result, it is now essential to understand if there are any situations in which such approach could produce more benefit compared to standard one. This would lead to defining classes of problems in which learning using hierarchical approach almost from scratch should be preferred to standard one.
In order to do so, we compare the regret paid by our method with the theoretical lower bound for flat FH- MDPs with non-stationary transition probabilities, which (HHvSAT) (Auer et al. 2008 Ghavamzadeh et al. 2020). If the comparison results in favor of the hierarchical approach, would be theoretically possible to define the characteristies of the problem that would discriminate the preferred framework.
Let R be the ratio between the regret upper bound of our approach and the regret theoretical lower bound.
RegretsMDP R
(8)
Q(HVSAT)
H3A2vSAK
By considering particular relations between the option-MDP and the original one, where Ao aA, So as and Ho = all, we can rewrite this ratio as:
K
R
<
(9)
A2/6
R S is the condition that determines that approach is preferable over the standard one. Thus, by imposing it, can find the maximum number of episodes for which this constraint is satisfied.
A a H6
KS
(10)
The problems with characteristics compliant with this equation are the ones which hierarchical approach should be preferred a standard one, even when no fixed sub-tasks policies (fixed options) are provided.
need to consider that, by using defined option set, are introducing bias. It could be that the optimal policy the flat problem is irreproducible by a concatenation of the policies of the options chosen by the optimal high-level policy μ². 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 & Lazaric (2017) and produces an additional term on the regret equal to (M) - (Mo),, where M is the primitive MDP and Mo the same MDP with options.
Final Sub-Optimality Remark. In both Theorem 4.1
6.2
7 Proofs sketch
In this section, we provide the sketch proofs of theorem 4.1 and theorem 6.2 Please refer to the appendix for all the details.
7.1 Sketch proof of theorem 4.1
We defined the regret in finite horizon problems as in eq. 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 p 2 p and f 2 r. where terms without tilde the real one, hence, V*(s, h) < (u for all h. Thus, with
2 Optimistic algorithms work by finding an
bound eq. 2
K PPE (s, 1) 1
opt
(K) S
/ez (s, 1)
(11)
Let's introduce Performance Difference Lemma for FH-SMDPs.
10

---

Published in Transactions on Machine Learning Research (09/2023)
Lemma 7.1. [Performance Difference Lemma for FH-SMDP) Given two FH-SMDPs M and M with horizon H, and respeclively rewards f, F and transition probabililies P, p- The difference. in the performance of policy is:
ÇiL (s, VTH
Σ Σ (F(ss, 05, f8,, 0i.
(f(s:+1. 1441/8ss 0i, hi) f(5141, h Og, hz))
Va (8441, (1mi)))1h1 1(hs < H]
where È the expectation taken w.r.t. P and pik-
Note that the summation steps are not unitary but skip according to the length of the transitions h' - h. The derivation this lemma follows the one provided by Dann et al. (2017) for FH-MDPS that commonly used literature [Azar et al. 2017 Zanette Brunskill 2018). Check the appendix for further details.
Now we can use lemma 7.1 substitute the difference of value function in eq. 11 and we can upper bound both the difference of and p, with 2 times their confidence intervals and the optimistic value i've ( (51+1, with the horizon H we consider bounded primitive reward r(s,a) [0,
H Σ
Regret (K <
2 + 28 1f H)}
In the SiniteHHorizon Aterature(Dann et al.
2017 Zanette & Brunskill 2018 two terms are commonly used in the proofs: (1) o, that is the probability of taking the option o, in state s at time step h, which depends on the policy μ* and the transition probability of the real SMDP, (2) Lx, which defines the set of episodes visited sufficiently often, and the set (s, 0, 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 E, which is (aken w.r.l. the policy μs and the real transition probability p(s', h² /,l,s,,,,, h,), with
Σ
wx(s,o,h)
(s.0.A)ETx
respectively using Empirical Bernstein Inequality (Maurer & Pontil 2009), Hoeffding 1963) and Weissman et al. (2003).
We defined the confidence intervals of and p, in the equations 5 6
By substituting these definitions and the term just introduced, we get, up to numerical constants, that the regret is bounded by
ΣΣ Σ (ETHT (KO.)ELL Voulsn,o,h))
(,, (Vaarr) + VSH + vnu(s,o,h)
Lemma 7.2. Considering non-stationary MDP M with set of options as SMDP Mo 1999). In Mo the number of decisions laken in the kth -episode is random variable d and
Sutton et al.
ΣΣN
hr < H} = d with {Ak d < H
iEH (s,0)
Therefore, the following holds true:
=
ΣΣ E wk(St,,,,)) ne(si,ot,he) I iCH (s.0)EL,
11

---

Published in Transactions on Machine Learning Research (09/2023)
Substituting the result of Lemma 7.2 in the equation of the regret, we get
Regret(K)so) s o
( ( ( ((a((r)vSH)) VSH + dsO
(12)
where 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 Var(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 T of the duration of the options seen up to episode k, and this complete the proof.
Challenge The main challenge encountered during the analysis, which makes it different from the of FH-MDPs, resides under the fact that in Finite Horizon SMDP, the policy takes nunber of temporally extended actions that are not defined, being the duration of a temporally extended action random variable itself. Thus, it is not possible to recursively apply the standard bellman operator to define the performance difference lemma as in Dann et al. (2017) (Lemma E.5). More procisely, we have a summation of a number of elements that is a random variable, and thus it unknown. This, and the fact that we resort the renewal process theory (Smith) 1958), to upper bound this unknown variable (d, Section 5). describe the novelty in our analysis with respect the standard analysis followed in the FH-MDP literature.
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 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 bias is defined as the maximum average regret considering the option learning as finite horizon MDP with horizon Ho. Finally, the last term equals the regret of the SMDP learning with fixed options for the remaining episodes.
1 + K22 max oEO K, bias
Regret K) S Σ K.H. 6EO
-2SS.v AoKo
HSVORK, TH-SMDP-UCRE regret
(13)
option learning
Where K2 are the episodes used for the SMDP learning and K K= -oEc0 K2 + K2- Then considering that we allocate K2 episodes for cach option lcarning and upper bound K₂ S K, by bounding Ao, So, and Ho respectively, with the upper bounds on the action-space cardinality, state-space cardinality, and horizon of the options set, we can get rid of the maxoco, and solve the equation in closed form to find the K, which minimizes the regret.
K.
(14)
024
Now, we conclude the proof by substituting equation 14 in equation
13
8 Related Works
In the FH-MDP litcrature, several works analyze the regret of different algorithms. Osband & Van Roy (2016) present a lower bound that scales with Ω Q(VHSAT). On the other hand, many other works propose various upper bounds for their algorithm. The most common upper bound is the adaptation of [uer et al. (2008h proposed by Ghavamzadeh et al. (2020), which is of the order of O(HSVAT). 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( ((VH5AT) that successfully matches the lower bound.
Nevertheless, only some works focusod on thcoretically understanding the benefits of hicrarchical reinforce- ment 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. & Lazarie (2017), in
12

---

Published in Transactions on Machine Learning Research (09/2023)
which they propose adaptation of UCRL2 [Auer 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, focuses on the average reward setting to study how is possible to induce a more efficient exploration by using options, and assumes fixed options. Differently, we aim to analyze the advantages of using options to reduce the sample complex- ity of the problem, resorting to the intuition that temporally extended actions can intrinsically reduce the planning horizon in FH-SMDPs. Furthermore, worst-case one, that better quantifies the impact of the option duration on the regret. Other works providing theoretical analysis of hierarchical reinforcement learning approaches are Fruit et al. (2017), which is an extension of the previous work in which the need for prior knowledge of the distribution of cumulative reward and duration each option is relaxed. Even in this case, they consider the average reward setting, and the objective identical.
provide
dereenddependent upper bound, instead of a
Then, Mann et. al. (2015) study the convergence property of Fitted Value Iteration (FVT) using temporally extended actions, showing that longer options duration and pessimistic value function estimates lead to faster convergence. Finally, Wen et al. (2020) demonstrate how patterns and substructures in the MDP ben- efit planning speed and statistical efficiency. They present a Bayesian approach exploiting this information and 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 provably possible to reduce the problem complexity of Finite Horizon problem when using a well-defined set of options. This analysis 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 set of fixed options policies, were able to provide insights on classes of problems in which hicrarchical approach from scratch would still be beneficial compared to a flat one. In the future, it could be interesting to analyze the HRL problem by resorting to the framework proposed in Foster et al. (202I), and the associated multi-purpose method, to provide an alternative to our approach. Morcover, we would like to improve the algorithm proposed for options lcarning to tighten the theoretical guarantees and further characterize this family of problems, Finally, following the ideas of Wen et al. (2020), would like to investigate how the structure of the MDP could appear in our bound, which, in our opinion, is fundamental point to put another brick in the direction of total understanding on the promising power of HRL.
the first for FH-SMDP and provides form of
References
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement
learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 31, 2017.
Melike Barsol-GGrsoy. Semi-markov decision processcs. Wiley Encyclopedia of Operations Research and Management Science, 2010.
Erhan Cinlar. Introduction lo slochastic processes. Courier Corporation, 2013.
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.
13

---

Published in Transactions on Machine Learning Research (09/2023)
Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of artificial intelligence research, 13:227-300 2000.
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character the sample distri- bution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pp. 642 669, 1956.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint (tff::2112.14495 2021.
David Freedman. On tail probabilities for martingales. the Annals of Probabilily, pp. 100 100-118, 1975.
Ronan Fruit and Alessandro Lazaric. Exploration in mdps with options. In Artificial intelligence and statistics, pp. 586- PMLR, 2017.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret minimization in mdps with options without prior knowledge. Advances Neural Information Processing Systems, 30, 2017.
Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Exploration in reinforcement learning, Tutorial at AAAD20, 2020. URL httpp::/rlgammazze wwt.gaaaaaeo.iiiicb.bb... io/
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 30, 1963.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. In Proceedings of International Conference on Learning Representations, 2019.
Timothy A Mann, Shie Mannor, and Doina Precup. Approximate value iteration with temporally extended actions. Journal of Artificial Intelligence Research, 53:375 438, 2015.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint vxXic:0907.37.p0 2009.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advonces in newral information processing systems, 31, 2018.
Tan Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. orXio preprint arXiv:1608.0 1.XX:11688.0232,, 2016.
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.
losif Pinelis. Dkw type inequality for renewal processes. MathOverflow, 2019. URL htthh:://mmthhhvrrflloo net/q/326434
Doina Precup and Richard S Sutton. Multi-time models for temporally abstract planning. Advances in neural information processing systems, 10, 1997.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Walter L Smith. Renewal theory and its ramifications. Journal of the Royal Statisticol Society: Series B (Methodological), 20(2):243-22) 284, 1958.
Richard S Sutton and Andrew G Barlo. Reinforcement learning:: An introduction. MIT press, 2018.
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-22 1111 1999.
14

---

Published in Transactions on Machine Learning Research (09/2023)
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, pp. 3540 3549. PMLR, 2017.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the 11 deviation of the empirical distribution. Packart-Packard Labs, Tech. Rep, 2003.
Zheng Wen, Doina Precup, Morteza Ibrahimi, Andre Barreto, Benjamin Van Roy, and Satinder Singh. On efficiency in hicrarchical reinforcement learning. Advances in Neural Information Processing Systems, 33: 6708 6718, 2020.
Andrea Zanetie and Emma Brunskill. Problem dependent reinforcement learning bounds which can identify bandit structure in mdps. In International Conference on Machine Learning, pp. 5747-5755 -555, PMLR, 2018.
15

---

Published in Transactions on Machine Learning Research (09/2023)
A Detailed proof of Theorem 4.1
A.1 Notation and Setting
First, we need define the value function of an SMDP. In Sutton et al. (1999) it is defined as formalism for MDP with options, that itself, by the demonstration presented in the same article, SMDP.
In our case, however, for the SMDP model, are considering additional dependency on E [0, 1/}. Notation used:
H the horizon
policy over options {u:
r(s, o, h) the discounted cumulative reward gained by selecting the option o, in state s, in the instant h of the horizon H
p(s', W,s,,, h), is a new transition model that characterizes both the state dynamic and the time the option execules.
h) is the probability of playing option o being in state s at time-step h
The value function defined as:
VH(s,h) Σ [ls.o.h)(r(s...0))) E p(h', (lo.,sl....h)vvM3$.), oEO,
(15)
with V"(s, H) = 0.
A.2
Performance Difference Lemma
Lemma 7.1. (Performance Difference Lemma for FH-SMDPJ Given two FH-SMDPs M and M with horizon H, and respectively rewards f, F and transition probabilities é, p. The difference in the performance of policy is:
Vin (s, 1) (s,
(F(s), Os, hi) - o(,,,,,, o,,
(p(8it), M441l88s oi hi) M8it1, h441 Oz, hz))
(8441114411) 1(h; < H}
where E is the expectation taken w.r.t. f and pk-
Proof. È is the expectation taken wardt. the policy i and the transition probability p(s', M/s,, o, h), and can be rewrite as:
II [ oi, or, hhwphh)pp(sssa he or, [h; H)
This quantity the distribution of visits for the policy μe in the SMDP and is equivalent wis for the FH-MDP case. The result follows by unrolling equation 15 Lemma E.5 Dann al. (2017) for an example in FH-MDPs.
16

---

Published in Transactions on Machine Learning Research (09/2023)
A.3 Confidence Intervals
The confidence sets are defined as:
(s, o. (f o, hi, o, os,
ss, o, (px(:.-s,,,,h) ((s): |i -ls,,,)) - fls S of
and the relative confidence bounds [[(s, o, h) and ( o, h) using Empirical Bernstein bound Mauurer Pontil 2009). Hooeldinn (1963) and Weissman et al. 2003).
Var(() 2/6
7h 7
O,) V
+
(16)
o(s,o,h)
3(n 1)
( Sllgg (m
(17)
0z(8,0,1)
with Var(r) be the sample variance of r.
Var(r) n(n - 1)
Σ 1SisJ5n
(r: - rz)²
(18)
A.4 Actual Proof
Theorem 4.1. Considering non-stationary Finite Horizon SMDP SM and set of options O with bounded primilive reward r(s,a) a) E [0. The regret suffered by algorithm FH-SMDP-UCRL, in K episodes of horizon bounded as:
Regret(K) 5 30
) (T+ VSH)
with probability 1 8. Where:
T max v [TT(s,,,,)) s.o.h max hE|r(s,,,h)13+ + Var[t(s, h)]], s,0,h
is the holding time, the random nurbbe of primáliiee steps laken when playing temporally erlended action o, and d is the average per-episode number of played options.
Proof-
Regret(K)-
Σ
(*, 1) Vmn (1,
Opt.
k
<
Vun (s, 1) -vut (s,
k=1
K
H1
(F(si,os,hs) F(si, o(s (p(si+1, hit Me4ilsi, o,, h4) 5(8 hit1 oz hi), V ( (8141,
1=1
t=1
1sh,
H}
17

---

Published in Transactions on Machine Learning Research (09/2023)
3ΣΣ Σ
vu(ss,oi,hig hi) (f(0s, o1, - f(8i, 02, 0i))
A iE[M] (s
+ (p(s)+1, 144111 os, h4) h 84, 0z, /
h,)) 7 Vun (si+1, (sit1, ho+1))
3Σ E
wa(si, ki) (20% (2) oz, h4) a=)+ (5 h4)
à 1E[H] (s,0,
ΣΣ Σ
wa(s;, hi)
(V Var(r)
S
nx(s,o,h)-1 V
+
on H
K sE[H] (s,0,A)ELE
Σ ΣΣ E
wh wp(ss, on,)i)
(
+ vSH)
+ 3ΣΣ E & (E (sio,
Wk(ss, 0z h2)
& ic|m] (s.a, Vnc(si,,s,hi)
( O,
(Vason) (
(VVar(r) + VSH
+ dsO
(Vason)
[RmaOT + VSH dSO
with
T = max v E B[ 1,) a.0
max V[(r(o: h:)] Var(r 0z h;)
(19)
8.0.
with r representing the average duration of the of options so far.
The first passage is standard inequality when proving the regret in frameworks adopting optimism in face of uncertainty.
(a) The expectation with respect to the policy μe and the transition model can be replaced with
more common formulation used in the Finite Horizon literature (Dann et al. 2017 Zanette & Brunskill 2018), (ss,,,))
Where, La is defined as the good set (Dann et al. 2017 Zanette & Brunskill 2018 which is the number of episodes in which the triple (s, h) is seen sufficiently often, and this equation is valid for all the tuples (8, o, h)) being part of this set.
(b) We upper bound the difference rewards and transition probabilities with two times their relative confidence intervals, and, the Value function at the next step with the horizon length H.
(c) We substitute the confidence intervals with their definitions (eq. 17 neglecting logarithmic terms.
(d) We divide the summation in two, to upper bound the terms scparately
(e) Using the adaptation of lemma 16 of Zanette & Brunskill (0188 for SMDPs, lemma 7.2 for the first term Using passage (b) and (c) in the proof of lemma E.1
(f) Upperbounding the sample variance of r, with Rmax T. Where T is the sample variance of the duration.
18

---

Published in Transactions on Machine Learning Research (09/2023)
B Special Case of fixed-length options
Let's consider the same finite horizon MDP with options with fixed length == RA. H, > where each option ;=< 1, , > has a fixed initial set / and fixed termination condition 3, Rs, o) E [0,TRmaz is the expectation of the reward function distribution, Pr(-Is, o) is the transition distribution, H is the horizon, and 7 H is the options fixed length. The solution of the MDP will be a policy म - O that maximizes the cumulative return choosing among options' optimal policies x², The reward function over state options pairs relates to the flat-MDP's reward as:
Ra =
50 (+1s)
rn+ilaii 8i) 1=0
Σ
61 1a1
Denote with V/= (s) the state value function associated with a hicrarchical policy x" (with Hicrarchical policy define policy that chooses among options).
N
V (s) = E
Rax (8),
(-18g)
with N
= H the number of decision steps that occurs during the Horizon. 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 sum over decision steps. Hence, we write:
Opt. S
K
Regret(K) K)
th
(8)
(20)
k=1
Σ
Σ wn
(Rn(s (s)))) (Pr(s,0) Pn(s, ViT
(21)
(s.o)EL
term considering the state-options pairs inside the failure event
(22)
here ()) the probability of visiting state and choosing option there at the decision step n in the k-th episode.
Then, we consider new formulation of the confidence sets:
B o) = ( o) - (s, o), (nn(s, + (s.
P (s) = (Pril () E ((s): (+s. - Pnu o) s (s,
using Hoeffding 1963 and
Weissman et al. 2003 the confidence bounds are:
log (ane(
8.t (s, x Rmax 7
(23)
S Slog Pax(
(8, a
(24)
Bonk (8,
19

---

Published in Transactions on Machine Learning Research (09/2023)
After the definition of the confidence sets we can bound the previous equation follow:
t (8) (0=
Σ
Wor (8, o) ( Rui (8, 0)) (Prk(s; - Puu (s,((, (8, V
h+1
ne[N]
term considering the state-option pairs inside the failure event
Σ
Σ
Wikk (8, 0)
2 + 2 (H +)) -+))
nE|N] (s,0)EL
RmaoT Vrikk
S (H - F)
Σ
Σ
Σ
(n)(
V
Bykk
nE[N] (s,0)ELk
Wnk(s,0)
Σ
E
E
Rmaaz + (S(H-
mukk
nE[N| (8,0)ELE
- 0 Nv NVSOK (Rmaat + +VSH-VS VSF))
$ 0 NNSOK [Rmaxt + (SH))
(a) substituting the (s, (),, 0) and (s. o) Pa o) with double the relative confidence interval and considering TH & (H - -). The second term will omitted for ease of notation.
(b) replacing the confidence intervals with their definition
(c) Lemma E.2
(d) considering the worst case, where there isn't the negative term
comparing with the bound of Fruit Lazaric 2017 for bounded holding time:
((DDV + Tmaz + (Tmar - Tmin)) Rmaa V SoOn)
that having options with fixed duration F, and considering Rmaz 1 reduces to:
(psvon++VVSO
have the same bound where instcad of the diameter have the Horizon H, and where NK is exactly equal to the number of the decisions up to episode k which is in their notation. We have:
HSVON'K + FVSSONKK
Important: Note that have additional VN terms because considered non-stationary MDP. This is a well-known penalty term when considering non-stationarity in the process.
C Proof of Theorem 6.2
Theorem 6.2. The regret paid by the two-phase learning algorithm until the episode K is:
Regret(K) / HHSO.=K
H8853000
with Ho max.eo Ho, and So, and Ao, respectively, the upper bounds on the cardinality of the state and action space of the MDDPs..
20

---

Published in Transactions on Machine Learning Research (09/2023)
Proof.
The regret of the two-phase algorithm can be written in this form
K1
Regret(Ks (K) =
Σ
(s, 1) - (s) Σ
(8, 1) V
==1
k=ks
K1 (s. (ow) (s, 1)
(s, 1) (AKK
V (mx2)
Vuk (Mx))
Regret SMDP with fixed options
Options learning Regret
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 to find the option's is policies by solving O different sub-FH-MDPss and giving all options equal samples Ko (K1 = EoEo Ko), we can write the regret paid in K Eoco K, K2 episodes
Regret(K) & Σ KoHo + K2 max H.S.VA.K A.K, + HSVORK.
aEO K.
6EO
where Ho each sub-FH-MDP horizon, and Ao and So the cardinality of the action and state spaces.
We consider paying full regret for each option learning, then the maximum average regret considering the option learning as finite horizon MDP with horizon Ho. and the regret of the SMDP learming with fixed options. However, we can further simplify the regret we assume So, Ho to be the upper bounds of the relative quantitics, getting rid of the maximization in the second term, and the regret became
K2 H3S0 AoK, + HS /K
Regret(K)) S Ho + K.
Now, by substituting K2 and upper bounding OK.) S K we can solve in closed form to find K, to minimize the regret.
K
Regret( (K) S OK,Ho + K.
HoSov ΛoK, + HSVOKT
K2 12
K.
044
Therefore, by substituting K2 in the original equation, we have
Regret(K) s { (1K #HSOKd
Now can compare the regret of this algorithm compared to the regret of UCRL2 adapted for non-stationary FH-MDPs Ghavamzadeh et al. 2020
CH)
RegrelsMMP
K1/6 8/300/3
(H1S)//3 S
(25)
Regret
H2S
K < 16
(26)
21

---

Published in Transactions on Machine Learning Research (09/2023)
D Renewal Processes
Lemma D.1 (Renewal Function Bound). Considering a Renewal process, (Xt)t20, and sequence S1,S2 S2. of random variables, characterizing the random duration of event, olternatively defined as holding time, with supp(S,) E (I,.... H}. We can bound, with probability 1 - ö, the expected number of random events that occurred up to time t, Xt, with:
In2 - -nnd t X1 x
+ P
cK
where μ is the mean of the r.v.s and o² the variance. with 320²T
1
Proof. Based on the proof presented on Pinclis 2019 processes Dvorrtzky el al. 1956)
which apply DKW type incqualities to renewal
Pr
sup OSSET
Xnt
S 2e cene
n1
Now we can equal 2e - to and find e.
In 2 In 6
Thus with probability 5
In 2
In
X, S
+ 1
cn
that completes the proof
Lemma 5.3. [Bound on number of options played in one episodej Considering Finite Horizon SMDP S. with horizon H and, options with duration Tmin S T S Tmaz and min.(((ro)] the expected duration of the shorter option. The expecled number of options played in one episode d con be seen as the renewal function m(t) of renewal process up to the instant H. With probobility 1 ô, this quantity is bounded by
32( 22(Tmaz Tmin (In In (E )3
H
d <
min (E(7.)
Proof. The proof followed the one of lemma D.1 and the fact that considering = - == 7, o² = (Tmaz Tmin), and X, d. Moreover, considering F, the average holding time of the option, we can further state that 7 > mino(E((T.)) which is the expected duration of the shorter option, and complete the proof.
E
Useful Lemmas
Lemma E.1 (lemma 16
ZZantto & Brunskill, 2018 for non stationary MDPs). The following holds true:
ΣΣ Σ whk(s, hE(H] (s.)ELz
nx(s,a,h) Ö(VHSAT)
1
where the exlra H is due to the non-stationarily of the environsent
22

---

Published in Transactions on Machine Learning Research (09/2023)
Proof.
ΣE Σ
wha(s, a)
V
nx(s,a,
hE(m) (s.a)eTx
Σ3 bEIH] (s,a)EL
Σ
w
ΣΣ Σ
(n,
1
ax(s,a,h)
I hE(H] (o.a)ELx
VKH
ΣE HE|H] (s,a)EL2
E
Wha(s,a) a)
1
nk(8,a,))
Then:
Wha a)
ΣΣ E
he[H (s,a)ELx n
W))(s,a)
NETH| (8,0)ELi k Eisk Why
Ke
$ 4HSA log
Weinn
X HSA
(a) by Cauchy-Schwand
(b) EiE(m] E(sajet, u)) H lemma 17 (b) Zanette Brunskill (2018)
(c) Jemma 2 Zanette & Brunskill (0088) adapted to the non-stationary case
(d) lemma E.5 Dann al. (2017) considering that being (s,a) part of the good Lxs then we are assuming (Appendix E.3 Dann et al. (2017)) that wx(ss, a) Wmin-
(e) substituting (l) we get the upper bound, and we conclude the proof.
Lemma 7.2. Considering non-stationary MDP M with of options as an SMDP Mo 1999). In Mo the number of decisions laken in the bth -episode is random variable d and
Sutton al.
Σ
Σ
0r h, < H} = d with {vk: d 5 H}
iE (s,0)
Therefore, the following holds true:
ΣE Σ
wa(S;, he) ma(ooo = - =Ō (5.0)ELk
Proof. Due to the stochasticity of the option's duration, d is random variable expressing the number of decisions taken in a step. Thus, first, we can rewrite passage (b) of the proof of lemmn 17 Zanette & Brunskill (0018) then, we change lemma E.1 considering the same notion of good set considered in the appendix of Zanette & Brunskill (2018) and the validity lemma of Zanctte & 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 F.1
23

---

Published in Transactions on Machine Learning Research (09/2023)
Lemma E.2 (lemma 16 (Zanette & Brunskill 2018 for MDPs with options of fixed lenght). For MDP with O options, with fized lenght 5, where the horizon is divided in N I! decision sleps, the following holds true:
- NVSOO
ΣE Σ REN Ls
mx(s.0) =
Proof. In this MDP the control returns to the hierarchical policy after exactly F time steps (the length of H
an option), thus, we can have at most N = + actions in the horizon H. For this reason, passage (b) of the proof of lemma become
Σ Σ
On)
EEN (8,0)ELa
The rest results for the same passage of the proof of lemma E.1
To have more complete analysis we need also to consider the triples (s. h) which aren't inside the good set. To do that, we can adapt Lemma 3 of Zanette & Brunskill (2018). for the FH-SMDP setting.
Lemma E.3 (Outside the good set). It holds thal:
ΣΣ Σ
0, o)(s,,,))=0((300)
k=1 (s,0,h)ETL
The proof follows from the one of lemma 3 of Zanette & Brunskill
2018
24


Reviews:
[{"review_id": "x8chdpqnMy", "reviewer": "Reviewer_S8Us", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper studies an important and practically relevant problem that has not so much theoretical development so far despite its practical import.\n\n- The technical results largely appear to be sound.\n\n- There is helpful discussion and interpretation of the results.\n\n- The separation between new contributions and use of existing tools is well-written, making the paper easy to understand on this front.\n\nWeaknesses:\n\nMinor\n\n- The first result is not easy to interpret in my opinion, but this is eventually cleared up with the discussion on the parameter $d$ and its bound. However, in (and before) the theorem, $d$ is not formally defined. There is just a natural language description as the number of decisions in an episode. But the number of decisions of which policy? The bound is on the regret, which is defined over $K$ policies, so presumably this value is different for each policy. Is it the average over all the policies? Or is it just the one for the optimal policy?\n\n- It is my understanding (please correct me if I am wrong) that the techniques used to develop the results in this paper are not particularly new. However, this is not an important criterion for TMLR.\n\nMajor\n\n- The assumption about the division of the state and action spaces into regions where the options coincide with the optimal policy and the assumption that they can be individually learned is definitely strong. It is hard to imagine such an example in practice. While the first could still be an effective model, the second is key for the two-phase algorithm. Overall, in this section there is a lack of clarity about what formally the two-phased algorithm is – only the subroutine about learning the options is provided. It seems to suggest that there is an implicit assumption that one can sample an initial state for each option to learn the optimal policy, but this doesn’t appear to be explicitly stated anywhere either.\n\n\n- I do not believe the second result is being demonstrated in the most understandable way. First, the UCRL $\\sqrt{K}$ bounds can be easily converted to the $K^{2/ 3}$ style bounds by online-to-batch conversion. This will give a more directly comparable result for the ratio calculation: $K^{2 / 3} (H^4 S^2 A)^{1  /  3}$.\n\nThat being said, I am skeptical about whether regret is even the best way to compare them. Considering the regret bound is already compromised with $K^{ 2 / 3}$, it may be better to just consider this entirely a PAC result. In this case, to get $\\epsilon$ suboptimality, UCRL will require $H^4S^2 A /\\epsilon^2$ samples and the options algorithm will require $\\alpha^8 H^5 S^2 A O  /\\epsilon^2 +  H^2 S^2 d^2 O / \\epsilon^2$ This seems to be an easier comparison. By the way, in Eq 8, should this be $\\alpha^{8/3}$ instead?  \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of reinforcement learning in finite horizon MDPs with options. The purpose of options is generally to handle longer sequential tasks that can be robustly divided into manageable sub-tasks handled by sub-policies. The sub-policies are managed by an overarching options policy. This paper is primarily theoretical, building on some initial work in this direction and developing theory for the finite horizon setting.\nThe first major contribution specializes to the setting where a set of options are fixed and given. An algorithm and regret bound are given. The regret depends only on the option-specific parameters such as the number of options and number of option decisions made in rollouts\nThe second major contribution focuses on learning the options simultaneously. This is given as a two-phased approach.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The requested changes will depend on the answers to the above questions, but here are also some concrete ones.\n\n- The regret in equation 1 is defined with value functions, which have not been defined yet. I think these are important to define first. For example, it is not clear if V* is the value function of the true optimal policy or the optimal meta-policy that optimally uses the available options. These could be different.\n\n- More formal and detailed explanation of the two-phased algorithm and what is being assumed about access to the MDP. It seems it is implicitly being assumed that one can solve the option subproblems directly.\n\n- More direct comparison with UCRL in discussion of the second result, as described above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FrQF2mExLd", "reviewer": "Reviewer_GasD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Hierarchical RL is practically relevant, but has lacked a rigorous theoretical treatment for the most part. Thus, this work fills a relevant hole in the literature.\n- This should be made more explicit (see below), but the analysis in this work could likely be used to show that there are cases where hierarchical RL is formally easier than standard RL. While perhaps not too surprising, to my knowledge this has not been shown before.\n\n\nWeaknesses:\n- The regret bound obtained is not optimal, scaling as $O(H^{3/2} S \\sqrt{A T})$ in the tabular setting (with no options). \n- Assumption 6.1 seems very strong. It simply would not be the case in general that one could optimize a small sub-MDP, and that the optimal policy on that sub-MDP is equal to the optimal policy on the full MDP (for the states in the sub-MDP). Furthermore, the $O(K^{2/3})$ regret given in Theorem 6.2 (where the learner is also trying to learn options) is likely very suboptimal in this setting. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work is motivated by hierarchical reinforcement learning (RL), where a learner seeks to combine existing knowledge on how to solve a variety of low-level tasks into a high-level controller that solves the high-level goal. They formulate this as a Semi-MDP, where instead of having access to actions, the learner can play a given “option”, which is a low-level policy that acts for some number of steps. They propose an optimism-based algorithm in this setting, and show that it achieves $O(\\sqrt{K})$ regret, with polynomial dependence on the size of the state space, option set, and horizon, as well as on how long each option runs. In addition, they consider the question of actually learning good “options”, and show an algorithm that achieves $O(K^{2/3})$ regret for learning options. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Some discussion should be given on how the DEC and bounds from [1] would scale here. I believe the setting proposed here would fit into the interactive decision-making framework of [1], so that may immediately give a characterization of the problem.\n- Some discussion on the optimal dependence on $d$ and $\\tau$ would be helpful (i.e. showing a lower bound on these parameters). \n- Is Assumption 2.1 actually needed given that we are in the finite-horizon setting? \n- I believe it is important to construct an explicit, non-trivial example where there is a provable gain to using hierarchical RL over standard RL. That is, construct an instance or family of instances, show a lower bound on the performance of any standard RL algorithm for these instances, and apply the upper bound given in Theorem 4.1 to show that the regret of hierarchical RL is lower than the lower bound for standard RL. \n- Similarly, it would greatly strengthen the paper if the discussion in section 6.1 on settings when the regret of Theorem 6.2 is lower than the regret for standard (non-hierarchical) RL algorithms could be made formal, as suggested above. As noted by the authors, comparing upper bounds does not offer much insight into which setting is actually harder, and a lower bound should instead be compared with the upper bound of Theorem 6.2. \n- I was somewhat confused by the discussion on the average reward setting in Section 4.2.2. As I understand it, the algorithm given here does not handle the average reward setting. What does the sentence “On the other hand, when considering the same assumptions…” mean then? As far as I can tell the regret bound stated in that sentence is not shown to hold. I would suggest removing this section or clarifying this.\n- In Theorem 6.2, how is regret defined? Furthermore, what if there are states that are not included in any $\\mathcal{S}_o$?\n\nThere were several aspects of the problem setting not clearly defined:\n- Is it possible for multiple options to be running at once? Or as soon as one option starts, is the algorithm unable to play additional options until it finishes?\n- I could not find the definition of $V^*$, the optimal value function. I assume it is defined as the optimal value function achievable by playing only options. One could imagine a scenario where the options are simply “bad”, and one would instead prefer to simply play the raw actions. What guarantees does this algorithm have in such settings?\n- A precise definition of $\\tau$ should be given in the option setting.\n- $d$ is only defined after Theorem 4.1, and even then is only defined informally. A formal definition of $d$ should be given. \n- On the third line of section 4.2.1, the term “non-stationary” is used, but it’s not entirely clear what this means. Is this simply referring to MDPs where the transition kernel is different for each step $h$, or to settings where the transitions are changing from one episode to the next? This should be clarified.\n\nMinor typos or wording issues which should be fixed:\n- in the abstract, the first sentence should read “tasks are characterized” not “tasks is characterized”.\n- there is an extra “)” in algorithm 1 on the line “Compute $n_h(s,o,h))$;”.\n- I had difficulty parsing the sentence starting with “We can enhance characteristics…” at the top of page 8. Consider rewording. \n\n\n[1] Foster, Dylan J., et al. \"The statistical complexity of interactive decision making.\" arXiv preprint arXiv:2112.13487 (2021).", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qDLsPpFKCh", "reviewer": "Reviewer_tVm5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- This paper is well-written and easy to follow. The scope of this paper covers the HRLs from using the deterministic options to learning these options. \n- The regret bound (both $\\sqrt{T}$ for the known option setting and $\\sqrt[3]{T^2}$ for the learning paradigm aligned with my intuition and seems to be correct\n\nWeakness:\n\n- The definition of $d$, the expected number of decisions taken in one episode, is confusing. What is the policy the expectation is taken on? \n\n- I'm confused about how Algorithm 3 will corporate with Algorithm 1. For example, since the length of each option is defined by the probability $\\beta_o$, how will the horizon length $H_o$ be calculated? Second, it seems to me that the agent needs to know the $S_o$ and $A_o$ for each option, which might be a little bit restrictive.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper extends the UCRL algorithm to an 'option-dependent' setting where the MDP with a longer horizon can be decomposed to several short-horizon MDPs. The authors provide a $\\sqrt{T}$ regret bound for different options for these short-horizon MDPs. The learning process of these options is also discussed in the latter part of this paper, suggesting an $\\sqrt[3]{T^2}$ regret bound.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I would suggest the authors formally define $d$ in the problem settings since it is also heavily discussed in Sec 5.\n\nI also have some questions besides the above suggestions.\n\n- Regarding $d$, if the expectation is an empirical expectation (i.e. $dT$ = Number of Decisions over $T$ episode), will it lead to some dependency issue in analyzing the regret bound?\n\n- Why Extended value iteration is necessary, can we replace it with dynamic programming starting from $h = H$ to $h = 1$ as UCRL paper?\n- What if Assumption 6.1 cannot guarantee $\\pi^*(s) = \\pi_o^*(s)$, which means some misspecification exists on the designed rewards and desired behavior?", "broader_impact_concerns": "I don't have any broader impact concerns regarding this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a theoretical analysis of hierarchical reinforcement learning, more specifically of options, under the setting of finite-horizon semi-MDPs. The authors extend UCLR to this setting, considering both the cases where the option are given or learnt beforehand, and provide a regret analysis, discussing the cases where options can be preferable to a flat policy. 

The rebuttal and discussion mostly addressed reviewers initial concerns and questions, who are all on the acceptance side, noticing that this contribution fills a relevant hole in the literature. I thus recommend acceptance.

There was some further discussion among reviewers about the connection to Foster et al paper (cf review of GasD and associated rebuttal). It was agreed that if HRL could fit this general framework, doing so is not direct and would be a contribution by itself, so a precise comparison is out of scope. However, the authors are encouraged to mention this work, eg as a possible alternative for the theoretical study of HRL in future works. For the camera-ready, please also add the content to sec. 6.1 as given in your last reply to reviewer GasD.
Decision: Accept (poster)