Provably (More) Sample-Efficient Offline RL with Options
Authors: Xiaoyan Hu
Ho-fung Leung
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning with Options
Offline RL
Provably Efficient RL
TL;DR: Options (i.e., closed-form policies) provably improves the sample complexity in offline RL by temporal abstraction and the reduction of the state space

Abstract: The options framework yields empirical success in long-horizon planning problems of reinforcement learning (RL). Recent works show that options help improve the sample efficiency in online RL. However, these results are no longer applicable to scenarios where exploring the environment online is risky, e.g., automated driving and healthcare. In this paper, we provide the first analysis of the sample complexity for offline RL with options, where the agent learns from a dataset without further interaction with the environment. We derive a novel information-theoretic lower bound, which generalizes the one for offline learning with actions. We propose the PEssimistic Value Iteration for Learning with Options (PEVIO) algorithm and establish near-optimal suboptimality bounds for two popular data-collection procedures, where the first one collects state-option transitions and the second one collects state-action transitions. We show that compared to offline RL with actions, using options not only enjoys a faster finite-time convergence rate (to the optimal value) but also attains a better performance when either the options are carefully designed or the offline data is limited. Based on these results, we analyze the pros and cons of the data-collection procedures.

Provably (More) Sample-Efficient Offline RL with Options
Xiaoyan Hu
Ho-fung Leung Independent Researcher Hong Kong SAR, China ho-fung 1ewng@outlook.cco
Department of Computer Science and Engineering The Chinese University of Hong Kong Hong Kong SAR, China xyhu21@cse cuhk. edu.hk
Abstract
The options framework yields empirical success in long-horizon planning prob- lems of reinforcement learning (RL). Recent works show that options improves the sample efficiency online RL where the learner can actively explores the environment. However, these results exploring the environment online is risky, e.g., automated driving and healthcare. In this paper, provide the first analysis of the sample complexity for offline RL with options, where the agent learns from a dataset without further interaction with the environment. We propose the PEssimistic Value Iteration for Learning with Options (PEVIO) algorithm and establish near-optimal suboptimality bounds (with respect to the novel information-theoree options) for two popular cola-collection procedures, where the first one collects state-option transitions and the second one collects actennction transitions. We show that compared to offline RL with actions, using options not only enjoys a faster finite-time convergence rate (to the optimal value) but also attains a better performance (when either the options are carefully designed or the offline data is limited). Based on these results, we analyze the pros and cons the data-collection procedures, which may facilitate the selection in practice.
longer applicable scenarios where
lower bound for offline RL with
Introduction
Planning in ang-horizon tasks is challenging in reinforcement learning (RL) Rey-Ryye et al.
2018
Eysenbach et al. 2019 Hoang et al.] 2021]. A line of study proposes to accelerate learning in
these tasks using temporally-extender actions (Fikes et al. 1972; Sacerdoti 1973 Drescher 1991
Jiang et al. 2019 Nachum et al., 2019 Machado et al. [021 Erraqabi et al. 2022 One powerful
approach is the options framework introduced by (Sutton et al. 1999), where the agent interacts with
the environment with closed-loop policies called options. Empirical success [Tessler et al. 2017
Vezhnevets et al. 2017) shows that options help achieve sample-efficient performance in long-horizon planning problems.
To provide theoretical guarantee to the options framework, recent works have focused on the sample complexity of RL with options in the online setting, where the agent continuously explores the environment and learns hierarchical policy to select options. BBunskill and Li (2014) establish PAC-like sample complexity of RL with options the semi-Markov decision processes (SMDPs), where temporally-extendee
actions are treated as indivisible and unknown units. Later, Fruit and Lazaric (007)) provide the first regret analysis of RI. with options under the Markov decision processes (MDPs) framework. While their proposed algorithm attains sublinear regret, it requires prior knowledge of the environment, which is not usually available in practice. To address this problem, Fruit et al. (2017) propose an algorithm that does not require prior knowledge, yet achieves
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

opar-optimal regret bound. However, these results are inapplicable to many real-world scenarios where online exploration is not allowed. For example. it has been argued that in healtheare (Gottesman et al. (019) and automated driving (Shalev-Shwartz et al. 2016). learning in an online manner is risky and costly. In these scenarios, offline learning, where the agent learns policy from a dataset, is preferred. We note that there is a line of studies on the sample complexity of offline RI. with primitive actions only (i.c., without the use of options) (Levine et al., 20200 Fu et al. 2020, Rashidinejad et al., 202I). Unfortunately, to the best of our knowledge, there have been no results reported on the offline RL with options.
In this paper, we make the following contributions. First, we derive novel information-thon theoretic lower bound, which generalizes the one for offline learning with actions. Second, we propose the PEssimistic Value Iteration for Learning with Options (PEVIO) algorithm and derive near-optimal suboptimality bounds for two popular data-collection procedures, where the first one collects state- option transitions and the second one collects state-action transitions. More importantly, we show that options facilitate more sample-efficient learning in both the finite-time convergence rate and actual performance. To shed light offline RL with options in practice, we discuss the pros and cons of both data-collection procedures based on our analysis.
2 Related Work
Learning with Options Building upon the theory of semi-Markov decision processes (SMDPs) (Bradtke and Duff 1994; Mahadevan et al. 1997),,Sutoon SStton et al. (1999) propose to learn with options. Following their seminal work, learning with options has been widely studied in the function approximation setting (Sorg and Singh 2010) and hicrarchical RL (Igl et al. 2020 Klissarov and Precup 2021; Wulfmeier et al. 2021). Discovering useful options has also been the subject of extensive research (Stolle and Precup 2002, Riemer et al. 2018 Mankowitz et al. 2018 Harb al. 2018 Hiraoka et al. 2019; Bagaria et al., 2021). Despite its empirical success, there have been fairly limited studies on the sample efficiency of learning with options. Brunskill and Li (2014) analyze the sample complexity bound for an RMAX-liK algorithm for SMDPs. Fruit and Lazaric (0177) derive the first regret analysis of learning with options. They propose an algorithm that attains sublinear regret the infinite- horizon average-reward MDP while requiring prior knowledge of the environment. Later, Fruit et al. (2017) remove this requirement.
Offline RL. In the offline setting, a dataset that is collected by executing a behavior policy in the environment is provided, and the agent is asked to learn a near-optimal policy using only this dataset. A key challenge in offline RL is the insufficient coverage of the dataset (Wang et al. [2021). which is also known as distributional shift (Chen and Jiang 2019: Levine et al. 2020p. To address this problem. the previous study on sample- -efple-ffficient learning assumes uniform coverage of the dataset (Liu et al. 2018 Chen and Jiang, 2019 Diang and Huang 2020 Yang et al. 2020: Xie and Jiang, [2020]Uehara) et al. 2020 Qu and Wierman 2020; Yin et al. 2021). This assumption is relaxed in recent works by pessimism principle (Xie et al. 2021 Rashidinejad et al. 2021 et al. (021).
3 Preliminaries
3.1 Episodic MDP with Options
Let A(X) denote the probability simplex on space X' and [N] := {1. .N. for any positive integer N. An episodic MDP with options is a sextuple M = (S, O, H,P,r), where S is the state space, A the (primitive) action set, O the finite set of options, H the length of each episode, P = (Pr : S x A + A(S) the transition kernel, r = {rm :h::S S x A + [0, 1]b the deterministic reward function We define S := |S]. A == [|), and 0 == 10). A (Markov) option o E O is a pair (T², 88 where x" = { S + ((A))ee is the option's policy and 3 { S + 10, [0,1]]eej is the probability of the option's termination. For convenience, define (s) = -1 for all (s, S O, i.., any option is terminated after the end of an
'Our results can be directly generalized to stochastic rewards.

---

episode. We assume that the initial state is fixed Upon arriving at state at any timestep [H], if h 1 (at the beginning of an episode), the agent selects option 0r μu (-[s)), where = (mn S + (EE)) is a hierarchical policy to select an option at each state. Otherwise (h 2 2), the agent first terminates option 0h-1 with probability - (sh). If option oh-1 1 is terminated, she then selects a new option oh ~ (-1ss) according to the hierarchical policy μ. option 0h-1 is not terminated, the agent continues to use option 0/-1 timestep h, i..., O4, 0h-1- After that, the agent takes action aj ~ Th (-1sn), receives a reward Th := Th (Shx ), and transits to the next state 8h+1 is that an action a is an option o, such that Ti (als) = 1 and (8) = for any (h,8) E [H] x S. For convenience, we use the notation O A represent that each option corresponds to an action, which is the case in RL with primitive actions.
(-1sh,, a4)) An episode terminates at timestep H 1. special case
To define the Q-function and the value function, we introduce some useful notations Let T {Th x + AS x [H + 1]) and = {UA, S x O + [0, Ho denote the option transition function and the option utility function, respectively. Particularly, for any (h, s. E [H] x S x O, the option transition function Tú, (s'|s s, o. r) is the probability that the agent uses option at state at timestep h, reaches state s' at timestep h + T without terminating option in these r timesteps, and finally terminates option o at state s' at timestep / + r. The option utility function (s, o) is the expected cumulative reward within timesteps that the option is used without being terminated. Given any arbitrary series of functions (ys : S + TR ]EEH), define the operator
[Ti.th+>](ss o) == Ee's (s'ls, o, T) +)))++((s)) for any (s, o, 7) E S x O x [H - h + 1]. In the following, derive the Q-function and the value function for learning with options. (The detailed proof can be found in Appendix B
Theorem (Q-function and value function). For any hierurchical policy y and (h,8,0) E [M] x
S x O, the Q-function is given by
(s) EE
The (sw, aw) Li=h
Σ
9h s, 0h = Un(8,,0+
E
-4+1
and the value function is given by
H Σ
VI((s) :Eppp
rhe (sw, ax)) = 0, ~ -wnn -Wn(t1s)) Σ
(2)
OEO
where Vii = 1'+41
any for any (s, E S x O.
Intuitively, the first term (s o) of the Q-function is the expected reward within timesteps that option o is used without being terminated, and the second term - [T) V I (ss o) corresponds to the expected reward within timesteps after option o is terminated and a new option is selected according to μ.. It can be shown that there exists optimal (and deterministic) hierarchical policy 4² = {Hi S + Ohe that attains the optimal value function, i.c., Vg (s) = sup, Vi((s) for all (h, s) E [ x S [Sutton et al. 1999).
3.2 Offline RL with Options
We consider learning with options in the offline setting. That is, given dataset 'D that is collected by an experimenter through interacting with the environment, the algorithm outputs a hierarchical policy f.. The sample complexity is measured by the suboptimality, i.e., the shortfall in the value function of the hierarchical policy j compared to that of the optimal hierarchical policy j², which is given by
SubOpt ( s1) == (s1 (sP(ss)
To derive novel information-theoortie lower bound of SubOpt.p. we first define some useful notations.
For any hierarchical policy μr, we denote by 0 {0] S O + [0, []] its state-option
Note that any H length episodic MDP with a stochastic initial state equivalent to an (H + 1)-length MDP with a fixed initial state so.
The formal definitions can be found in Appendix A
3

---

occupancy measure. That is. (s, o) is the probability that the agent selects particular option state at timestep (either when or when the option on-1 used at the timestep is terminated) when following the hierarchical policy With slight abuse of the notation, we denote by (s) == Eoeo 0% (s, the state occupancy measure for any (h,s) [H] S. Further, we
define
Z = Σ (s). Z= = Σ (s, 0] h
8,8,0
where I[-] is the indicator function. Intuitively, Z the expected number of timesteps to alternate a new option and % is the maximal number of state-option pairs that can be visited, when following the hierarchical policy p. The following proposition shows that options facilitate temporal abstraction and reduction of the state space.
Proposition 1. For any hierarchical policy we have that Zó S H. If μ is deterministic, i.e.,
{m S One(M. we further have that ZoO HS. All the above equalities hold when O
A.
Next, derive novel information-theorrtie lower bound of SubOpt The detailed proof can be found in Appendix C
Theorem 2 (Information thheoretictcecccccc lower bound). Let = {pn S + ((O) denote any hierarchical behavior policy to collect the dataset. Define the class of problem instances
(M, p) Exists deterministic p² of episodic MDP M M(Coption 2², 2²,²"):=
8% (s. h,5.0 (s)
such that max
S Coptionn 2%O0 S ZZ" S 5T}
and x" 2 12" |S, where |x| == max(n E n S xx} is the largest integer greater than x E R. Then, there exists absolute constant en such that for any offline algorithm that outputs a hierarchical policy t., if the number of episodes
Suppose that Coption 2 2, 2, 2"
K Co Cuptioo 1
2²
on which the hierarchical policy then there exists problem instance (M, MiCoptioon ==, x²)) suffers from e-suboptimality, that is,
Ead (SbbOpt, (p,ss) 2
where the expectation By with respect to the randomness during the execution of within MDP M.
Theorem shows that, when dataset D sufficiently covers the trajectories induced by n², i.e., max 0f o) (s. o) < Cropton at least 52 Coppion H H / episodes are required to learn an c-optimal hierarchical policy from dataset DD Note that when O A, recovers the lower bound 2 SCH SC" /e2)
for offline RI. with primitive actions, where C* is the concentrability defined therein.
4 The PEVIO Algorithm
Inspired by the Pessimistic Value Iteration (PEVI) algorithm (Jin et al. 2021). we propose the PEssimistic Value Iteration for Learning with Options (PEVIO) Algorithm I Given dataset D and the corresponding Offline Option Evaluation (OOE) subroutine, whose details are specified in Sections 5.1 and 5.2 PEVIO outputs hierarchical policy (Mr S {(O))
To estimate the Q-function, given a dataset D. PEVIO first constructs (f,Ū, Ú, T) by the OOE subrou- tine (line 3). Specifically, Tn and Ü, are the empirical counterparts of Tū and Un presented in the Q-function given by Equation (T), respectively. addition, I' penalty function computed based on dataset D. We remark that the OOE subroutine varies when different data-collecting procedures

---

Algorithm PEssimistic Value Iteration for Learning with Options (PEVIO)
1: Input: Dataset D and the corresponding Offline Option Evaluation (OOE) subroutine.
2: Initialize: Qu(s, o) <- 0, (s) 0, Vs) for any 8,, [H] x S O.
3: (T, 1) f- (D)
4: for h -1..,,
5: for (s,0) E ESSxdd
6:
(s) t Ua(s,) + (Tn (s.
7:
(s max min o). h 1}}. end for
8:
9:
for E S do
10:
(h t arg max
(s) (Qn(s,))) (-((s))))
12:
end for
end for
14:
Output: ğt = [hemm
are considered and we provide the details in Sections 5.1 and 5.2 respectively. Given UR, Th. and
Th, the estimated Q-function Qn is the derived (lines 6 and 7). Particularly, Q₁ computed in line 6 can be seen as first replacing Un and T7, with their empirical counterparts UR. Tū in Equation (1) and then subtracting the penalty function 1ax Further, a hierarchical policy cúa is constructed greedily with Qn (line 10), where (f()),(())) == Eoeo [())g()) for any arbitrary functions S.g defined
on O. Finally, given Qn and ain. the corresponding estimated value function VA computed (line 11). To analyze the suboptimality of the hierarchical policy ğ output from PEVIO, we first provide the the following definition, which motivates the design of the penalty function I.
Definition 1 (f-uncertainty quantifier for dataset D). The penalty function r {T S O R hhe output from the OOE subroutine in Algorithm (line 3) is said to be & f-uncertainty quantifier with respect PD if the following event
H-h+1
E =(((ūn(s,o) -[(((s))))U(((s))
Σ
[ - -W))
(5)
[n(ss,) for all (h, s)
[ x
satisfies that PD(() 2 1 - E, where PD is the joint distribution of the data collecting process.
In other words, the penalty function I is a É-uncertainty quantifier if it upper bounds the estimation errors in the empirical option transition function T and the empirical option utility function Ü. Next, we show that the suboptimality of ğ output from PEVIO is upper bounded if I is g-uncertainty quantifier. (The detailed proof can be found in appendix[D]
Theorem 3 (Suboptimality of learning with options using dataset D). Let js denote the hierarchical i output from the OOE subroutine is a E E-uncertainty quantifier. Conditioned on the successful event & defined in Equation (5) which satisfies that (E) 2 1- E, we have that
policy output by Algorithum 7 Suppose that
(f, 2 2 Ep (sh, ssl
(6)
h=1
where Ey [g(sh, on)] = Eis,o) 0f (s, (s,o)g(s, o) any h E [H] and functionn g S +> R.
Remark 1. Since the temporal structure of learning with options is much more complex than learning with actions, PEVIO is significantly different from the algorithms proposed for offline RL with primitive actions, such as PEVI (Jin et al. 202T) or VI-LCB (Xie al.) 202T). despite sharing similar intuition. First, in terms of the algorithm design, PEVI and VI-LCB estimate (one-step) transition kernel and reward function to compute the Q-function state-action pair. However, by Equation (I. the fufunciion of state-option pair depends multi-step transitions and rewards.
5

---

Hence, it is challenging to design the OOE subroutine and analyze the estimated ( T.. for options. Indeed, if the dataset contains (s. o, u) (state-option-utiln) utilityy) tuples. then (T, U, can be estimated similarly to the case of learning with primitive actions. However, if the dataset contains only (8, a, r) (state-acting seree-actioo-ewwardd tuples, then remains elusive estimate and analyze (T, TT,. D)) Second, in terms of the suboptimality analysis. previous works on offline RI. with primitive actions rely on the extended value difference lemma (Cai et al., 2020] Lemma 4.2), which also depends on the one-step temporal structure of actions and cannot be directly applied to our setting, Hence, to derive Theorem 3 it is non-trivial to generalize the extended value difference lemma to the options framework (See Lemma 8 in the Appendices).
5 Data-Collection and Suboptimality Analysis
In this section, we consider two data-collection procedures that are widely deployed in the options literature. The first one collects state-option-utiliy tuples (dataset D1) and similar datasets are utilized in the work of Zhanng et al. (023). The second one collects state-action-rewe reward tuples (dataset D2) and is studied in a line of works (Ajay et al. 2021 Villecroze et al. 2022; Salter et al. 2022). Intuitively, dataset D1 requires smaller storage and enables efficient evaluation of the options, while dataset D2 provides richer information on the environment and even facilitates the evaluation of new options. For each dataset, design the corresponding OOE subroutine and derive suboptimality bound for the PEVIO algorithm. Based on these results, we further discuss the advantages and the disadvantages of both data-collection procedures, which sheds light on offline RL with options in practice.
5.1 Learning from State-Option Transitions
( )e([))) consisting of state-option-utility tuples, We consider dataset D {( " which is collected by the experimenter's interaction with the environment for K episodes using hierarchical behavior policy م {ph S + ((O)hett)) More precisely, timestep t of the kth episode, the experimenter selects new option oft uses for (1 ( timesteps, collects a cumulative reward of uh within these (th+1 + timesteps, and finally terminates this option at state s at timestep 2 For convenience, we define th 5,+11 := H + for any & E [K]. '41
Let a va maxfa, b) for any pair of integers a, E N. When dataset Dj is available, the OOE subroutine in Algorithm| iis given by Subroutine 2 Particularly, Subroutine incorporate the data splitting technique (Xie et al. 202T) (line 2). That is, given dataset D,, the algorithm randomly splits into H/ subdatasets (DI, Then Tü and Ur are constructed using subdataset Di,t (lines 4-7).
To derive the suboptimality for output from PEVIO, we follow the previous study and make standard assumption on the coverage of dataset D,
Assumption 1 (Single hierarchical policy concentrability for dataset D1). The experimenter collects dataset Dj by following hicrarchical behavior policy p {ph A(O))ee(M)) There exists some deterministic optimal hicrarchical policy μ such that
0 (s,
Cuppioon = max
8,5.0 0 (8)
(with the convention 0/0 0) is finite.
In other words, Assumption] I states that dataset Dj sufficiently covers the trajectories of state-option- utility tuples induced by some deterministic optimal hierarchical policy p². We derive an upper bound of SubOpt in the following theorem. (The detailed proof can be found in Appendix E
with probability at least 1 ç. we Theorem 4 (Suboptimality for dataset D,). Under Assumption 7 have that
SubOptp, (2, 2 (
Coption H 2/32g22 Z
(8)
K

---

Subroutine Offlin Option Evaluation (OOE) for Dataset Di
1: Input: Dataset D2 = {s of, u ( [eEE))
2: Initialize: Randomly split the dataset D into 1/ subdatasets ( Jeeamn with |Pi,A|
K/H. More precisely, let I = (la)ne be random partition of the set [K], where In (Un.s (jn,)) C. [K] is uniformly sampled from [K] such that Uhe(m/h = [K] and
4. 4 0 for any h + h'. Then we have that Di, {15
e4 oz. u Mee,,,,,,, for any h E [H]. (e, o) == EkEI, I[h E hebp4 s = s, of: = ol denote the number of times that the experimenter selects a particular option state timestep h in subdataset Di,
3: for (h, 8,0) E [H]
x S x O do
4: for (s', E E H h + do
6: end for (s + Eeer, (hE (4 m.0 o- -
5:
7: (x f- ΣxEr [[kEtt) =h
[ana(s,0)
8: (a( + -0 Ö(V (Vintoojy
9: end for
10: Output: (f = (Tn N 0 =((0==((@neee ==
where 7o: = 7% and 7.00- == %/00
Compared to the lower bound in Theorem suboptimality bound (8) is near-optimal except for an extra factor of H More importantly, it shows that learning with options enjoys faster convergence rate to the optimal value than learning with primitive actions. Recall that the VI-LCB algorithm (Xie) al. 2021) that learns with primitive actions attains the suboptimality bound Ö(y D(*H'SC**/ K)), where C" is the concentrability defined therein. When ignoring the concentrability parameters, the suboptimality bound (8) is smaller since Z < H and Zo < HS.
Remark 2. While, in the worst case, both Z3 and Zo can scale with H and HS, respectively, we note that in many long-horizon planning problems, they often scale with the number of sub-tasks, which are greatly smaller, especially for tasks that enables temporal abstraction and the reduction of the state space. For example, while the route- cuate-pannnig task of going from City A to City B by transportation takes thousands of primitive actions to finish, it can be efficiently solved by decomposing into the following sub-tasks, (1) going the airport/train station in City A: (2) taking transportation to City B; and (3) reaching the final destination in City B, for which options are designed. In this case, both Z3 and / S may only scale as o(H). In other words, options facilitate more sample-efficient learning through temporal abstraction, i.e., sticking to an option until a sub-task is finished. Another concrete example is solving a maze, where options are often designed to move agents to bottleneck states (Simşek and Barto 2004] (Solway et al., 2014 Machado et al., 2017) that connect different densely connected regions of the state space, e.g., doorways. In this case, while the number of option switches may grow proportionally to H, i.e., Z5/ H (1), the number of states to switch options
can be greatly smaller than S, i.e. Zo/ H = o(s). That is to say, options help improve the sample complexity by the reduction of the state space.
Further, we show that learning with options attains better performance than learning with primitive actions, when either the options are carefully designed or the offline data is limited.
V (s1) vf (s1). where Vo.pái is the optimal value function defined for the primitive actions. Ignoring the concentrability parameters. we have that TrueSubOptp, (T,,a) )1 S Ō(v SH*SS* /K) attained by the VI-LCB algorithm (Xie et al.
Corollary 1 (Better performance). Let TrueSubOpt (ū. s= Vi
2021), when either the options are curefully designed (i.e., Ao(s1) == Vi (s1)) (81) Vi or
'We note that the extra factor H in the suboptimality bound g can be reduced by applying the reference- advantage decomposition technique (Xie al. 2021
7

---

the number K of trajectories in the dataset is
H 2
VH2SC*
Oiption ZOZO
o
where (x)+ == ma x for any E.R.
Corollary implies that when data is limited, c.g., in cases where the data collection is highly expensive risky, learning with options beneficial since the output hierarchical policy yields higher value than learning with primitive actions.
5.2 Learning from State-Action Transitions
We consider dataset D2 == {s 0% r he [H] kE[K] consisting of state-action-reward tuples, which is collected by an experimenter' ' interaction with the environment for K episodes using any arbitrary behavior policy. That is, the experimenter takes action af, at state sf, at timestep of the kth episode, receives reward of r and transits state 8f+11
When dataset D2 is provided, the OOE subroutine in Algorithm is given by Subroutine 3 Note that one difficulty is that we cannot directly estimate the option transition function and the option utility function from dataset D2 as it only includes the information of the primitive actions. Hence, Subroutine first constructs the empirical transition kernel P {Pr her and the empirical reward function F (fnthe (lines 4-7), and use them to further construct Tr and Un (lines 8-20). To
Subroutine Offline Option Evaluation (OOE) for Dataset D:2
1: Input: Dataset D2 = {(*, a =e))e(()
2: Initialize: ÚH+1( (.) < 0. Let (s, == Σ Iss = s, a a] denote the number of visits
of state-action pair (s, a) at timestep in dataset D2. Function Φ == { S x O + RRie[ is
given by Equation 22 in the Appendices.
do 4: for (s,a) S A do
3: for h H, H
P)( + Exerg [s. = = =0 for any
5:
(8.a
6: Fa(s, a) + I[Na(s, 1|rx(s,a)
7:
end for
8:
for (8,0,8') S x x do
9:
(s( - 8 (5') E Ti (1((ss)
10:
1) (1 + (s')) ΣOEA (al
11:
1 do
12:
T,(5'(s,0,1) < E. (a(s))
E." Pr(s" (1 ( T 15'1"""'"",,,
(s E. (a|s) Egr Pa (1-11t1(3")) 7 h+ (8'1""
14: end for
15: end for
16: end for
17: for (h, 8, E ( x XSx
[n(s,0) ( 1
HPS Em E(aa)eN (M,aa + Hoo(s.o)
On (n,s))) + ((s,0))Enes EnEd (a(als)F EvES (n(''ls, o, 1
19:
20:
end for
Output: (f= ( (Tetn 0 0= (Ünheetn =TTnheeja)
21:
derive the suboptimality,
first define some useful notations. For any (h, s, o) [H] x S O and < m & H, we denote by Xm the set of state-action pairs that can be reached at timestep m by using option at state and timestep h without being terminated Further, let de (dh, x A+
For convenience, we assume that Xm is known prior. When X is unknown, it can be replaced by superset that does not require prior knowledge and results directly follow (See Remark 3 in Appendix F

---

[0, [e denote the state-action distribution of the behavior policy used by the experimenter. That is, di, (s, a) is the probability that the agent takes action a at state at timestep h. Similarly, we make the following assumption on dataset D2.
Assumption 2 (Single hicrarchical policy concentrability for dataset D2). The experimenter collects dataset D2 by following an arbitrary behavior policy There exists some deterministic optimal hierarchical policy μ² such that
0 (s,0) d d (s),
C2 = max h,300
Cuppioon
Σ
(9)
bs Mm. yE
(with the convention 0/0 0) is finite.
Intuitively, Assumption 2 states that dataset D2 sufficiently covers the trajectories state-action- reward tuples induced by the optimal hierarchical policy μ². Next, we derive upper bound of Su under Assumption The detailed proof can be found in Appendix
Theorem 5 (Suboptimality for dataset D2). Under Assumption have that
with probability least 1 &.
(V
Coption H3sZo
22soc2ttion
SubOptp, (2, S
(10)
K
K
which translates
Coption 1 H3S7870
K
when K of dataset D22 is sufficiently large, ie.. K Ö(Crriin H 1²02/ where 7% %% and 7. = %
While, in general, suboptimality bound (10) does not compare favorably against the suboptimality Ö(v (CH attained by the VI-LCB algorithm that learns with primitive actions, we argue that can be better in long-horizon problems where the horizon // is much greater than the cardinality of the state space S.
5.3 Further Discussion
We analyze the pros and cons of both data-collection procedures, which sheds light offline RL with options in practice. Compared to D2, dataset Dj requires smaller storage and enjoys faster convergence the optimal value, which is further illustrated follows.
Storage: For dataset D:2 {(5) ah r(t (h)he H Me[K]. the storage is simply HK. However, for dataset D1 {(s og ) [SE]")AA[[]]] its expected size is K Z% HK, where p is the hierarchical behavior policy. Therefore, in the case of small 2g. dataset Dj requires much smaller storage than D: (on average).
Suboptimality:
Ignoring the concentrability, the suboptimality bound (T0) for dataset D2 is worse than the suboptimality bound (8) for dataset D, by factor of vS, which is introduced
when estimating the option transition function and the option utility function using only the information of the primitive actions.
However, since dataset D2 contains more information the environment than D1, it has weaker requirement on the behavior (hierarchical) policy and allows the evaluation new options, which is illustrated follows.
Concentrability: Recall that the suboptimality bounds for both datasets build upon the suffi- cient coverage assumptions, i.e., Assumption [ D, and Assumption for Dz. While they are generally incomparable (as dataset D2 can be collected by an arbitrary behavior policy), we focus on the case that both datasets are collected by the same hierarchical behavior policy p. Particularly, it can be shown that Assumption 2 is weaker than Assumption I Indeed. if

---

covers the trajectories of caatte-pttoo-utiiie tuples induced by μ¹ (i.e., Assumption holds), then it must have covered the trajectories of state-action- reward tuples induced by μr" (i.e.. Assumption 2 holds). However, the opposite does not hold in general and we provide such an example in Appendix H
Evaluation of New Options: In the options literature, a popular task is offline option
discovery Aaay al., | Villecroze et al. 2022]. i.e., designing new and useful options from the dataset. Therefore, an important problem whether these new options can be evaluated through the dataset. We argue that dataset D2 yields greater flexibility than D in this case. Again, we assume that both datasets are collected by the same hierarchical behavior policy p. Unfortunately, one cannot use dataset D1 to evaluate any (h, 8, o) that is not visited by p. i.e., (8, o) = O, let along evaluating the new options. However, this not the case for dataset D2. In fact, any (h, 8, o) can be evaluated if the visiting state-action pairs are also reachable by p. i..., Ensms (e' a') k...o 1/d%, (s', .a) < co. An interesting problem is how to leverage the results in this paper to facilitate offline option discovery, which we shall research in the future work.
6 Conclusions
In this paper, we provide the first analysis of the sample complexity for offline RL with options. A novel information-theorrtie lower bound is established, which generalizes the one for offline RL with actions. We derive near-optimal suboptimality bounds of the PEssimistic Value Iteration for Learning with Options (PEVIO) algorithm for two popular data-collection procedures. Our results show that options facilitate more sample-effice learning than primitive actions in offline RL in both the finite-time convergence rate to the optimal value and the actual performance.
Acknowledgments and Disclosure of Funding
The work presented in this paper was partially supported by research grant from the Research Grants Council, Hong Kong, China (RGC Ref. No. CUHK 14206820), Part of the research reported in this paper was done when the second author was with The Chinese University of Hong Kong. The authors are grateful to the anonymous reviewers for their helpful comments.
References
Ajay, A., Kumar, A., Agrawal, P., Levine, S., and Nachum, O. (2021). OPAL: Offline primitive discovery for accelerating offline reinforcement learning. In International Conference Learning Representations.
Bagaria, A., Senthil, J., Slivinski, M., and Konidaris, G. (2021). Robustly learning composable options in deep reinforcement learning. In Zhou, Z..H., editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, ISCAI-21, pages 2161-2169. International Joint Conferences on Artificial Intelligence Organization. Main Track.
Bradtke, S. and Duff, M. (1994), Reinforcement learning methods for continuous-time Markoy decision problems. In Tesauro, G., Touretzky, D.,, and Leen, T., editors, Advances in Neural Information Processing Systems, volume 7. MIT Press.
Brunskill, E. and Li, L.. (2014). PAC-inspired option discovery in lifelong reinforcement learning. In Xing, F. P. and Jebara, T., editors, Proceedings of the 3 International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 316-324, Bejing, China. PMLR.
Cai, Q., Yang, Z.. Jin, C., and Wang, Z. (2020). Provably efficient exploration in policy optimization. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1283-1294 PMLR.
Chen, J. and Jiang, N. (2019). Infornition-theerriicc considerations in batch reinforcement learning. In Chaudhuri. K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference
10

---

on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1042-1051. PMLR.
Co-Reyes, J., Liu, Y., Gupta, A., Eysenbach, B.. Abbeel, P., and Levine, S. (2018). Self-consisten trajectory autoencoder: Hierarchical reinforcement learning with trajectory embeddings. In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 Proceedings of Machine Learning Research, pages 1009-1018. PMLR.
Simyek, O. and Barto, A. G. (2004). Using relative novelty to identify useful temporal abstractions in reinforcement learning. In Proceedings of the Twenty-Firs First International Conference on Machine Learning, ICML '04, page 95, New York, NY, USA. Association for Computing Machinery.
Drescher, G. L. (1991). Made-up minds: a constructivist approach to artificial intelligence. MIT press.
Erraqabi, A., Machado., M. C.,, Zhao, M., Sukhbaatar, S., Lazaric, A., Ludovic, D., and Bengio, Y. (2022). Temporal abstractions-augmeente temporally contrastive learning: An alternative to the Laplacian in RL. Cussens, and Zhang, K., editors, Proceedings of the Thirty-Eighe Conference on Uncertainty in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pages 64 641-6... PMLR.
Eysenbach, B., Salakhutdinov, R. R., and Levine, S. (2019). Search on the replay buffer: Bridging planning and reinforcement learning. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché- Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Fikes, R. E., Hart, P. E.,, and Nilsson, N.J. (1972). Learning and executing generalized robot plans. Artificial Intelligence, 3:251-288.
Fruit, R. and Lazaric, A. (2017). iitooration-Epploiaatiinn in MDPs with Options. In Singh, A. and Zhu, J., editors, Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 576-584. PMLR.
Fruit, R., Pirotta, M., Lazaric, A., and Brunskill, E. (2017). Regret minimization in mdps with options without prior knowledge. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances Neural Information Processing Systems, volume 30, Curran Associates, Inc.
J., Kumar, A., Nachum, O., Tucker, G., and Levine, S. (2020). D4rl: Datasets for deep data-driven reinforcement learning.
Gottesman, O., Johansson, F., Komorowski, M., Faisal, A., Sontag, D., Doshi-Velez, F., and Celi,
L. A. (2019). Guidelines for reinforcement learning in healthcare. Nature Medicine, 25(1):16 18.
Harb, J., Bacon, P.-L., Klissarov, M., and Precup, D. (2018). When waiting is not option: Learning options with deliberation cost. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1).
Hiraoka, T., Imagawa, T., Mori, T., Onishi, T., and Tsuruoka, Y. (2019). Learning robust options by conditional value at risk optimization. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché- Buc, F., Fox, E., and Garnett, R., editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Hoang, C., Sohn, S., Choi, J., Carvalho, W., and Lee, H. (2021). Successor feature landmarks for long-horizon goal-conditioned reinforcement learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances Neural Information Processing Systems, volume 34, pages 26963-26977 Curran Associates, Inc.
Igl. M., Gambardella, A., He, J., Nardelli, N., Siddharth, N., Boehmer, W., and Whiteson, (2020). Multitask soft option learning. In Peters, J. and Sontag, D., editors, Proceedings of the 36th Conference on Uncertuinty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pages 969-978. PMLR.

---

Jiang, N. and Huang, J. (2020). Minimax value interval for off off-po evaluation and policy optimiza- tion. In Larochelle, H.,, Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 2747-2758. Curran Associates, Inc.
Jiang, Y., Gu, S. S., Murphy, K. P., and Finn, C. (2019). Language abstraction for hierarchical deep reinforcement learning. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F, Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T. (2020). Learning adversarial Markov decision processes with bandit feedback and unknown transition. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4860-4869, PMLR.
Jin, Y., Yang, Z., and Wang, Z. (2021). Is pessimism provably efficient for offiine RL? In Meila, M. and Zhang. T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5084-5096. PMLR.
Klissarov, M. and Precup, D. (2021). Flexible option learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang. P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 4632 4646. Curran Associates, Inc.
Levine, S., Kumar, A., Tucker, G., and Fu, (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems.
Liu, Q. Li, L., Tang, Z., and Zhou, D. (2018). Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
Machado, M. C., Barreto, A., and Precup, D. (2021). Temporal abstraction in reinforcement learning with the successor representation.
Machado, M. C., Bellemare, M. G., and Bowling, M. (2017). A Laplacian framework for option discovery in reinforcement learning. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages
PMLR.
Mahadevan, S., Marchalleck, N., Das, K., and Gosavi, A. (1997). Self-improving factory simula- tion using continuous-time average-rewart reinforcement learning. In Proc. 14th International Conference on Machine Learning, pages 202-210.
Mankowitz, D., Mann, T., Bacon, P.-L., Precup, D., and Mannor, S. (2018). Learning robust options. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1).
Nachum, O., Tang, H., Lu, X., Gu, Lee, H., and Levine, (2019). Why does hierarchy (sometimes) work so well in reinforcement learning?
Qu, G. and Wierman, A. (2020). Finite-time analysis of asynchronous stochastic approximation and q-learning. In Abernethy, J. and Agarwal, S., editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3185-3205. PMLR.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: tale of pessimism. Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 11702-11716. Curran Associates, Inc.
Riemer, M., Liu, M., and Tesauro, G. (2018). Learning abstract options. In Bengio, S., Wallach, N., and Garnett, R., editors, Advances in Neural
H., Larochelle, H., Grauman, K., Information Processing Systems, volume 31. Curran Associates, Inc.
Sacerdoti, E. D. (1973). Planning in hierarchy of abstraction spaces. Artif. Intell., 5:115-135.
12

---

Salter, S., Wulfmeier, M.. Tirumala, D., Heess, N., Riedmiller, M., Hadsell, R., and Rao. D. (2022). Mo2: Model-based offline options. In Chandar, S., Pascanu, R., and Precup, D., editors, Proceed- ings of the Ist Conference on Lifelong Learning Agents, volume 199 of Proceedings of Machine Learning Research, pages 902-919. PMIR.
Shalev-Shwarte S., Shammah, S., and Shashua, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving.
Solway, A.. Diuk, C.,, Córdova, N., Yee, D., Barto, A. G., Niv, Y., and Botvinick, M. M. (2014). Optimal behavioral hierarchy. PLOS Computational Biology, 10(8):1-10.
Sorg. J. and Singh, S. (2010). Linear options. In Proceedings of the 9th International Conference Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 31-38.
Stolle, M. and Precup, D. (2002). Learning options in reinforcement learning. Proceedings of the 5th International Symposium on Abstraction, Reformulation and Approximation, page 212-223, Berlin, Heidelberg. Springer-Verler Verlag.
Sutton, R. S., Precup, D., and Singh, S. (1999). Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1):181-211.
Tessler, C., Givony, S., Zahavy, T., Mankowitz, D., and Mannor, S. (2017). A deep hierarchical approach to lifelong learning in minecraft. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1).
Uchara, M., Huang, J., and Jiang. N. (2020). Minimax weight and Q-function learning for off-policy evaluation. III. H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9659-9668 PMLR.
Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver, D., and Kavukcuoglu, K. (2017). FeUdal networks for hierarchical reinforcement learning. In Precup, D. and Teh, Y. W.. editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3540-3549. PMLR.
Villecroze, V., Braviner, H., Naderian, P., Maddison, C., and Loaiza-Ganent G. (2022). Bayesian nonparametries for offline skill discovery. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato. S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22284-22299, PMLR.
Wang. R., Foster, D., and Kakade, S. M. (2021). What are the statistical limits of offline RL with linear function approximation? In International Conference on Learning Representations.
Wulfmeier, M., Rao, D., Hafner, R., Lampe, T., Abdolmaleki, A., Hertweck, T., Neunert, M., Tirumala, D., Siegel, N., Heess, N., and Riedmiller, M. (2021). Data-efficient hindsight off-policy option learning. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11340-11350, PMLR.
Xie, T. and Jiang, N. (2020). Q approximation schemes for batch reinforcement learning: A theoretical comparison. Peters, J. and Sontag, D., editors, Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pages 550-559. PMLR.
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. (2021). Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 27395-27401 Curran Associates, Inc.
Yang, M., Nachum, O., Dai, B., Li, L., and Schuurmans, D. (2020). Off-policy evaluation via the regularized lagrangian. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 6551-6561. Curran Associates, Inc.
13

---

Yin, M., Bai, Y.. and Wang, Y.-X. (2021). Near- provable uniform convergence in offline policy evaluation for reinforcement learning. In Banerjee. A. and Fukumizu, K., editors, Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1567-1575. PMLR.
Zhang, F.. Jia, C., Li, Y.-.,, Yuan, L., Yu, Y., and Zhang, Z. (2023). Discovering generalizable multi- agent coordination skills from multi-task offline data. In The Eleventh International Conference on Learning Representations.
14


Reviews:
[{"review_id": "z3QRy1nI2S", "reviewer": "Reviewer_BJAs", "summary": "This analysis is the study of sample complexity in offline reinforcement learning (RL) with options, highlighting potential risks in online environmental exploration. The paper proposes the innovative PEssimistic Value Iteration for Learning with Options (PEVIO) algorithm and provides near-optimal suboptimality bounds for two common data-collection methods. The research underscores PEVIO's superior performance and faster convergence when optimally designed options are used or offline data is limited. Moreover, the study explores two different data collection methods, providing unique insights into their respective benefits and challenges. Overall, this research offers valuable contributions to the practical implementation and understanding of offline RL with options.", "questions": "I just want to understand on curiosity - Is there any thought that the work may be helpful or this approach can also be helpful in  Hybrid (Online +Offline RL). Any substantial logic for this?\nAlso, Can the authors discuss potential extensions or improvements of the PEVIO algorithm?", "limitations": "Author mentioned the limitations in some way Pros and Cons. So, OK. But I would love to understand explicitly about the scope limitation of the algorithm in more detail if there is any additional material.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper tries to put the innovative exploration of sample complexity in offline reinforcement learning (RL) with options, introducing the novel PEVIO algorithm. Combining  theory with sound empirical evaluations provides robust insights into different data collection methods and their implications. Despite the complexity of the subject, the paper maintains fair clarity. Its practical significance is clear, as it tries to fill a literature gap and holds the potential to influence future RL system design, making it a vital addition to the field of RL.", "weaknesses": "While the paper is undoubtedly insightful, further exploration of the influence of option complexity on PEVIO's effectiveness could enhance its contribution. Expanding the experimental setup to include varied environments and offline datasets might be beneficial to validate PEVIO's performance robustly. I think a more thorough discussion of the trade-offs between the two data collection methods could aid practitioners in making more informed choices in diverse application contexts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews, we would like to address your concerns as follows.\n\n**(Q1) Connecting to Hybrid RL.** \n\nThe reviewer asks whether our results can also facilitate hybrid RL. While this is out of the scope of the paper, we would like to provide some comments as follows. In hybrid RL, it is often the case that a policy is pre-trained or the $Q$-function is estimated in the offline phase using a batch dataset and then fine-tuned in the online phase. Hence, the performance during online learning is often affected by, e.g., the quality of the pre-trained policy or estimated values. As our paper shows that offline learning with options is more sample-efficient than RL with primitive actions, i.e., the output policy enjoys lower suboptimality, it may also help the learning in hybrid RL. For example, one possible way is to use options to obtain better estimated values in the offline phase, which further improves online performance. Therefore, we believe that the results presented in this paper are of importance for not only the understanding of the options framework in offline RL but could also provide insights into relevant research fields.\n\n**(Q2) Limitations and Potential Improvements of PEVIO.** \n\nThere could be several improvements to PEVIO. For example, our paper primarily focuses on tabular MDPs (finite state space). Hence, one direction is to extend PEVIO to more general MDPs (infinite state space), e.g., linear MDPs. In addition, when state-action-reward tuples are provided (Dataset $\\mathcal{D}_2$), the algorithm needs to estimate the one-step transition model to compute the $Q$-function, which can be computationally inefficient. Therefore, reducing the computation of PEVIO remains an interesting future work."}, {"review_id": "vSCCi0VCrj", "reviewer": "Reviewer_UEUz", "summary": "The authors provide a sample complexity analysis of offline RL with options. A sub-optimality analysis was performed considering two data collection schemes, (D1) state-option-utility collection and (D2) state-action-reward collection for the proposed pessimistic value iteration algorithm (PEVIO). The analysis reveals that (D1) is storage efficient and has a fast convergence rate, while (D2) has weak assumptions and allows flexible evaluation of new options.", "questions": "I think this study is interesting since it draws conclusions about the advantages and disadvantages of the data collection schemes through solid theoretical analysis. However, as mentioned above, it appears the current version of this paper has three weaknesses. I would appreciate it if the authors could answer the following questions.\n\n-Is the scope of the authors' theory and algorithms limited to Tabular MDPs (MDPs with discrete state and action space)? I can guess this from the content, but some clear description is needed.\n-Are there any related works and background on the finite concentrability assumption (Assumption 5.1 and 5.4), which is the central assumption of the analysis? It is helpful if list papers that adopt the same or similar assumptions and/or discuss the approach with different assumptions, etc. That will help to place this study in the context of the research.\n-How to update the penalty function in the Proposed PEVIO algorithm? It only provides the order-level update equation, unlike the (original) PEVI. Please give us some guidelines for implementation even if it is through numerical experiments. \n\nMinor Comment:\n-Citation needed at (L147) and (L217)", "limitations": "No \"Limitations\" section is provided by the author.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(S1) Solid theoretical analysis\n\n(S2) Analysis of the Pros and cons of the data-collection procedures", "weaknesses": "(W1) Scope of the theory is not clearly stated.\n\n(W2) Background and discussion on key assumptions seem insufficient.\n\n(W3) Unclear parameter update equation in the proposed Algorithm.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews, we would like to address your concerns as follows.\n\n**(Q1) Scope of the Theory.** \n\nThe results in this paper are limited to tabular MDPs. We will clearly illustrate this assumption in the preliminaries section in the later version of the paper.\n\n**(Q2) Finite Concentrability Assumption and Related Works.** \n\nAs we have illustrated in the related work section, the finite single-policy concentrability assumption is quite standard and is adopted by the works of Rashidinejad et al. (Definition 1, 2021), Jin et al. (Corollary 4.5, 2021), and Xie et al. (Assumption A, 2021). We will improve our expression in the later version of the paper.\n\n**(Q3) Update of the Penalty Function.** \n\nWe point out that to update the penalty function, the algorithm only needs to count the visits to state-action or state-option pairs. To see this, we provide the exact expression of the penalty function $\\Gamma$ as follows. When state-option-utility tuples are provided (Dataset $\\mathcal{D}\\_1$), the penalty in Line 8 of Subroutine 2 is computed by $\\Gamma_h(s,o)\\leftarrow2\\sqrt{\\frac{H^2}{n_h(s,o)\\vee 1}\\log(\\frac{2HSO}{\\xi})}$, where $n_h(s,o)$ is the number of visits to $(h,s,o)$ in subdataset $\\mathcal{D}\\_{1,h}$ and $\\xi\\in(0,1)$ is the probability of failure. In addition, when state-action-reward tuples are provided (Dataset $\\mathcal{D}\\_2$), the penalty in Line 18 of Subroutine 18 is computed by $\\Gamma_h(s,o)\\leftarrow2\\sqrt{\\sum_{m=h}^H\\sum_{(s,a)\\in\\mathcal{S}_{h,s,o}^m}\\frac{HS}{N_m(s,a)\\vee 1}\\log(\\frac{2HSA}{\\xi})}+2\\cdot\\phi_h(s,o)\\log(\\frac{2HSA}{\\xi})$, where $N_h(s,a)$ is the number of visits to $(h,s,a)$ in $\\mathcal{D}_2$ and $\\phi_h$ is defined in Equation (32) in the Appendices.\n\n**(Q4) Citations.** \n\nThe citation at (L147) should be (Xie et al., 2021) and the citation at (L217) should be (Rashidinejad et al., 2021; Jin et al., 2021; Xie et al., 2021)."}, {"review_id": "1SccUknf9F", "reviewer": "Reviewer_FY62", "summary": "In this paper, the authors analyze the sample complexity for offline reinforcement learning with options. In particular, the sample complexity is measured by the suboptimality (the shortfall in the value function) of a hierarchical policy compared to the optimal hierarchical policy. The authors propose the pessimistic Value Iteration for Learning with Options algorithm and propose bounds when using two popular data collection methods: one collecting state-option-utility tuples and one collecting state-action-reward tuples. The paper shows that using options can lead to a faster convergence rate (to the value of the optimal hierarchical policy over given options).", "questions": "- Could the authors please provide more details for how $\\theta_h^\\mu(s,o)$ relates to the policy $\\mu$?\n- There is possibly a type in line 125, $(h, s) \\in [H] \\times \\mathcal O$.\n- Theorem 3 holds “when dataset $\\mathcal D$ sufficiently covers the trajectories induced by $\\mu^*$”. Could the authors provide some intuition for how often this holds, or how one could verify if it holds?\n- Could the authors provide more details about the penalty function $\\Gamma$? For instance, what is it’s intuitive meaning, why does it have the format described in Subroutines 2 and 3?\n- Theorem 4.2 holds if the penalty function is an $\\xi$-uncertainty quantifier. Could the authors provide some intuition for how often this holds, or how one could verify if it holds?\n- How strong are assumptions 5.1 and 5.4? How could one ensure that they are satisfied?\n- How does the magnitude of $C^*$ compares with $C^{option}$? How does the magnitude of these constants generally compare with the other terms in the bounds?", "limitations": "The authors discuss the limitations of the work. No major concerns.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper investigates an important problem in the HRL literature: how does using options impact the efficiency of offline learning algorithms, considering different data collection approaches. \n- The paper is well-written, drawing parallels with existing work whenever possible.\n- The paper is very thorough with the mathematical formulation, assumptions, and definitions.", "weaknesses": "The theory is based on the assumption that a set of options is already available, and it focuses on the suboptimality of the hierarchical policy over those options (when compared to the optimal hierarchical policy over those options). Thus, the overall performance of the final hierarchical policy is dependent on the quality of the underlying options (as their policy is not being updated). Also, the intuition behind some of the other assumptions necessary to prove the results presented in the paper could be improved (see questions below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews, we would like to address your concerns as follows.\n\n**(Q1) Explanation of $\\theta_h^\\mu(s,o)$.** \n\nBy its definition in (L121), $\\theta_h^\\mu(s,o)$ is the probability of visiting the state-option pair $(s,o)$ at timestep $h$, when following the hierarchical policy $\\mu$. For example, let $\\mu$ and $\\mu'$ denote two hierarchical policies. Particularly, in the first step, we have that $\\mu_1(o|s_1)=1$ and $\\mu'_1(o|s_1)=0$ for some option $o$, i.e., $\\mu$ *always* picks option $o$ while $\\mu'$ *never* picks option $o$. In this case, we have that $\\theta_1^\\mu(s_1,o)=1$ while $\\theta_1^{\\mu'}(s_1,o)=0$.\n\n**(Q2) Typo in (L125).** \n\nThe expression in (L125) should be $(h,s)\\in[H]\\times\\mathcal{S}$. We thank the reviewer for pointing out the typo.\n\n**(Q3) Sufficient Coverage in Theorem 3.**\n\nAs it is pointed out in (L144) the sufficient coverage assumption in Theorem 3 refers to the condition that $\\max_{h,s,o}\\frac{\\theta^{\\mu^*}_h(s,o)}{\\theta^\\rho_h(s,o)}\\le C^\\text{option}<\\infty$, where $\\mu^*$ is the optimal hierarchical policy, $\\rho$ is the behavior policy to collect the dataset, and $\\theta$ is the probability of visiting the state-option pairs. We note that one case that this assumption holds is the behavior policy $\\rho$ is uniformly random.\n\n**(Q4) Intuition of the Penalty Function and Subroutines.** \n\nThe meaning of the penalty function $\\Gamma$ can be directly seen from Inequality (5) in Definition 4.1, which says that with high probability, $\\Gamma$ should bound the error in estimating the $Q$-function for each $(h,s,o)\\in[H]\\times\\mathcal{S}\\times\\mathcal{O}$. To further interpret Inequality (5), first note that the $Q$-function (See Equation (1)) is a linear combination of the utility $U_h$ and the value $V_{h+\\tau}$ in future steps. Hence, the error of estimated $Q$-function can be further decomposed as the error in estimating the utility, i.e., $\\widehat{U}\\_h-U_h$, and the error in estimating the future values, i.e., $(\\widehat{T}\\_h-T_h)\\widehat{V}_{h+\\tau}$, which correspond to the two terms in Inequality (5) exactly. The reviewer also asks why different formats in Subroutines 2 and 3 are given to compute $\\Gamma$. We point out that this is because that when different datasets are provided, the computations for $\\Gamma$ are also different. For example, when $(s,o,u)$ (i.e., state-option-utility) tuples are given (Dataset $\\mathcal{D}_1$), the computation of $\\Gamma_h(s,o)$ in Line 8 of Subroutine 2 needs to count the number of visits to $(h,s,o)$ in the dataset. However, the same computation cannot be done when only $(s,a,r)$ (i.e., state-action-reward tuples) are given (Dataset 2). Therefore, we need to design a different subroutine to compute $\\Gamma$ in Subroutine 3.\n\n**(Q5) Verification of $\\xi$-uncertainty Quantifier.** \n\nThe reviewer asks when the penalty function is an $\\xi$-uncertainty quantifier. We point out that by our designs of $\\Gamma$, i.e., Line 8 in Subroutine 2 and Line 18 in Subroutine 3, $\\Gamma$ is already an $\\xi$-uncertainty quantifier, without *any* further conditions or assumptions. The detailed proof can be found in Lemmas E.1 and F.2 in the Appendices.\n\n**(Q6) Assumptions 5.1 and 5.4.** \n\nThe reviewer asks how strong are Assumptions 5.1 and 5.4. We note that they immediately hold when the behavior policy collecting the dataset is uniformly random, which is quite common in practice. In addition, we point out that they are standard in the offline RL literature (Rashidinejad et al., 2021; Jin et al., 2021; Xie et al., 2021). As a comparison, there is another line of studies on offline RL that assumes full coverage of the behavior policy [1, 2], i.e., $\\min_{h,s,a}d_h^\\rho(s,a)>0$, which is much more strict than Assumptions 5.1 and 5.4.\n\n**(Q7) Comparison of $C^\\*$ and $C^\\{\\text{option}}$.** \n\nIn general, $C^*$ and $C^\\textup{option}$ are incomparable as they depend on the design of options, the behavior policy to collect the dataset, and the transition kernel of the MDP. Nonetheless, we show that (the upper bound of) $C\\^\\textup{option}\\_1$ can be smaller than (the upper bound of) $C^*$ in the following example. Assume that we have access to a generative model that given any $(h,s,o)$, returns the timestep-state pair $(h+\\tau,s')$ that option $o$ is terminated. In this case, if we uniformly sample state-option pair to collect the dataset, i.e., $(s,o)\\sim\\textup{Uniform}(\\mathcal{S}\\times\\mathcal{O})$, for each timestep $h$, then we have that $C^\\textup{option}\\_1=\\max_{h,s,o}\\frac{\\theta^{\\mu^*}_h(s,o)}{\\theta^\\rho_h(s,o)}=\\max\\_{h,s,o}\\frac{\\theta^{\\mu^*}_h(s,o)}{1/SO}\\le SO$, where $\\mu^*$ is the optimal hierarchical policy and $O$ is the number of options. In addition, in RL with primitive actions, if we have access to a generative model that given any $(s,a)$, returns $s'$ in the next timestep and we still uniformly sample $(s,a)\\in\\mathcal{S}\\times\\mathcal{A}$ for each $h$, then we have that $C^\\*=\\max\\_{h,s,a}\\frac{d^{\\pi^*}\\_h(s,a)}{d^\\rho\\_h(s,a)}=\\max\\_{h,s,a}\\frac{d^{\\pi^*}\\_h(s,a)}{1/SA}\\le SA$, where $\\pi^*$ is the optimal policy defined on primitive actions and $A$ is the number of actions. Since $O$ is often smaller than $A$, the upper bound for $C\\^\\textup{option}_1$ is smaller than the one for $C^*$.\n\n**References**\n1. Ming Yin, Yu Bai, Yu-Xiang Wang (2021). Near-Optimal Offline Reinforcement Learning via Double Variance Reduction.\n2. Ming Yin, Yu Bai, Yu-Xiang Wang (2021). Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning."}, {"review_id": "w3jo0i7doY", "reviewer": "Reviewer_V1tj", "summary": "The paper investigates the sample complexity of offline reinforcement learning (RL) with options. An information-theoretic lower bound for the suboptimality of the expected return of the policy over options that is learned offline is derived (by constructing hard MDP instances). The main contribution of the paper is the PEVIO algorithm, a version of value iteration for offline learning with options, and its theoretical analysis. The main idea behind PEVIO (borrowed from the PEVI algorithm for offline RL with primitive actions) is to be pessimistic in the face of uncertainty arising from the finite, fixed dataset. This pessimism is implemented by subtracting a penalty function from the value estimates which bounds the error in the estimates for the option transition function and option utilities. Suboptimality bounds are derived for two versions of PEVIO, intended for learning from state-option-utility and state-action-reward triplets. Depending on the frequency of option switches and the optimality of the option set, these bounds show that offline learning with options can be more sample efficient compared to learning with primitive actions.", "questions": "* I would suggest to explicitly spell out in the text that the reward is assumed to be in the range $[0, 1]$ as it is easy to overlook this assumption when it is absorbed into the formal definition of the reward function.\n* In Subroutine 3, would it also be possible to learn the option model more directly (without relying on a model for primitive actions), perhaps using importance sampling?", "limitations": "A dedicated paragraph or section about limitations is lacking at the moment. I feel like this would help the reader to better place the contributions of the paper. In particular a clear discussion of how the suboptimality bounds for PEVIO compare to each other and to VI-LCB with realistic assumptions on the option switching frequency would be helpful.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "As offline RL is highly relevant for many applications and hierarchical RL with the options framework promises to speed up learning, a theoretical analysis of the sample complexity offline RL with options is of interest to the RL community. To my knowledge, the results in the paper are novel and relevant. The paper is comprehensive in the sense that it presents both an information-theoretic lower bound and a concrete algorithm with suboptimality bounds. The advantages and disadvantages of storing state-option or state-action transitions are discussed which are relevant for practical applications. The majority of the paper is well written and the presentation is well structured.", "weaknesses": "From the perspective of somebody mainly interested in practical algorithms and applications, PEVIO seems to be quite far away from an algorithm that would perform well in practice. In particular the data splitting technique discussed in line 214 seems to effectively throw away a large fraction $\\frac{H – 1}{H}$ of the data as it randomly splits the data into $H$ subsets and estimates $\\hat{T}\\_h$ and $\\hat{U}\\_h$  solely from the subset with index $h$. As a reader, I would be interested in learning whether such a procedure would be required in practice or is merely a tool to facilitate theoretical analysis. When learning from state-action transitions, it is furthermore assumed that the sets $\\mathcal{S}^m_{h, s, o}$ (footnote 5) are known in advance. Moreover, the option transition function and utilities are obtained by first learning a one-step model which would suffer from compounding model errors. \n\nI would like to better understand the claim that PEVIO has near-optimal suboptimality. Equation (8) looks like it has an additional factor of $H^2$ under the square root which is quite significant. In practice, $Z^*_\\mathcal{O}$ and $\\bar{Z}^*_\\mathcal{O}$ can be expected to scale with $H$ as well which results in a factor of $H^5$ under the square root which is identical to $VI-LCB$. This would also mean that Corollary 5.3 would not make sense but that it actually depends on the constants whether (8) or the bound for VI-LCB is better. For these reasons I am not quite convinced that the claim “Therefore, Theorems 5.2 and Corollary 5.3 combine to show that [...], options facilitate more sample-efficient learning than primitive actions in both the convergence rate to the optimal value and the actual performance.” is correct with respect to the convergence rate. \n\nFurthermore, the summation in equation (9) seems to effectively introduce another factor of $H$ which is absorbed into a constant. The requirement on the number of episodes in Theorem 5.5 seems to be quite excessive because it scales with $S^9$ which is quite extreme and could never be satisfied in practice.\nIn general I would expect options to speed things up by a constant factor which is effectively the frequency of option switches. As I do not see why this frequency should automatically decrease on long horizon problems I am not sure if the claim about a faster convergence rate in the conclusion is sufficiently backed.\n\nTypos:\n* In line 116 there is a superfluous space before the comma.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews, we would like to address your concerns as follows.\n\n**1. (Paragraph 1 in Weakness Section) Data Splitting Technique.** \n\nWe point out that the data splitting procedure for dataset $\\mathcal{D}\\_1$ is only to facilitate theoretical analysis. Indeed, by Definition 4.1, a $\\xi$-uncertainty quantifier upper bounds the error $|\\widehat{U}\\_h(s,o)-U_h(s,o)+\\sum_{\\tau=1}^{H-h+1}\\[(\\widehat{T}\\_h-T_h)\\widehat{V}\\_{h+\\tau}\\](s,o)|$. Without splitting the dataset, i.e., we estimate $\\widehat{T}\\_h$ and $\\widehat{V}\\_{h+\\tau}$ using the same data, it requires to bound concentration terms of the form $(\\widehat{T}\\_h-T_h)\\widehat{V}\\_{h+\\tau}$. However, after splitting the dataset, as $\\widehat{T}\\_h$ only depends on $\\mathcal{D}\\_{1,h}$ and $\\widehat{V}_{h+\\tau}$ only depends on $\\mathcal{D}\\_\\{1,t>h\\}$, $\\widehat{T}\\_h$ and $\\widehat{V}\\_{h+\\tau}$ are independent. Therefore, we can derive the penalty function as $\\Gamma_h(s,o)\\leftarrow\\widetilde{O}(\\frac{H^2}{n_h(s,o)\\vee 1})$.\n\n**2. (Paragraph 1 in Weakness Section) Knowledge of $\\mathcal{S}_{h,s,o}^m$.** \n\nWe point out that while we assume the knowledge of $\\mathcal{S}\\_{h,s,o}^m$, i.e., the set of state-action pairs that can be reached at timestep $m\\ge h$ by using option $o$ at state $s$ and timestep $h$ without terminating, it is only for convenience and simplicity of the proof. Indeed, as it is pointed out in Footnote 5 we can replace $\\mathcal{S}\\_{h,s,o}^m$ with its superset $\\overline{S}\\_{h,s,o}^m:=\\\\{(s,a)\\in\\mathcal{S}\\times\\mathcal{A}:\\pi_m^o(a|s)>0\\\\}$, which does not require any prior knowledge on the environment.\n\n**3. (Paragraph 2 in Weakness Section) Near-Optimality of PEVIO.** \n\nWe note that in goal-oriented tasks (such an example is given by Fig. 2., Sutton et al., 1999), where the agent aims to reach the goal state as quickly as possible, the options are often designed to minimize the steps of reaching some states from the other. Noting that  $Z_\\mathcal{O}^*$ and $\\overline{Z}\\_\\mathcal{O}^*$ only depend on the optimal hierarchical policy, we would have that $Z_\\mathcal{O}^*=\\overline{Z}\\_\\mathcal{O}^*=O(1)$, i.e., at the initial state, the learner picks the option that reaches the goal state using minimal steps and does not terminate it until the end. In this example, while the horizon of the problem can be large, i.e., the number of steps to reach the goal state is large, the frequency of options switching is much lower. Similar situations can also be found in tasks involving multiple sub-tasks. For instance, a robot that serves a cup of coffee to a customer can decompose the task into (1) making a cup of coffee, (2) picking up the coffee, (3) going to the table where the customer sits, and (4) serving the coffee. Again, in this example, while it takes a large number of (primitive) actions to finish the task, the need for switching options only emerges after a sub-task is finished. In these learning scenarios, the frequency of option switches, or equivalently, $Z_\\mathcal{O}^*$ and $\\overline{Z}\\_\\mathcal{O}^*$, scales with *the number of sub-tasks*, which can be greatly smaller than the horizon $H$ of the problems. Therefore, our results indeed show that options facilitate more sample-efficient learning than primitive actions.\n\n**4. (Paragraph 3 in Weakness Section) Further Clarification of Theorem 5.5.** \n\nWe point out that the requirement that $K$ scales with $S^9$ in Theorem 5.5 is merely to simplify the regret bound. As it is stated in the proof of Theorem 5.5 (See Appendix F), the suboptimality bound of *any* $K$ should be $\\widetilde{O}(\\sqrt{\\frac{C\\_2\\^\\textup{option}H^3SZ_\\mathcal{O}\\overline{Z}\\_\\mathcal{O}^*}{K}}+\\frac{C_2^\\textup{option}H^4S^5AO}{K})$, where the second term decays to zero faster than the first term. Hence, when $K$ is sufficiently large, i.e., $K>\\widetilde{O}(C_2^\\textup{option}H^5S^9A^2O^2/(Z_\\mathcal{O}\\overline{Z}_\\mathcal{O}^*))$, the first term is dominant. Therefore, to simplify the expression in Theorem 5.5, we let $K$ scale with $S^9$.\n\n**5. Typos and (Q1) Range of the Reward.** \n\nWe thank the reviewer for pointing out the typo in (L116) and the suggestion of spelling out the range of the reward more explicitly in the text. These will be improved in the later version of the paper.\n\n**6. (Q2) Possible Improvements on Subroutine 3.** \n\nThe reviewer asks whether it is possible to learn the option model through importance sampling. We point out that there are two potential problems. First, when options are different, e.g., they select different actions, it is often difficult to have a good estimation of the values using importance sampling. Second, as the importance sampling often takes the form $\\frac{\\pi_h^o(a|s)}{\\pi_h^{o'}(a|s)}$, where $o$ and $o'$ are two options and $\\pi$ is the option's policy, the proportion can be arbitrarily large. In this case, the suboptimality bound may be looser than our current results. We agree with the reviewer that techniques like importance sampling could facilitate the implementation of PEVIO in practice and we shall research it in future work."}]

Author rebuttal:

Meta-review: The paper examines offline RL with options and studies the effect of having options on the performance of the offline RL algorithm. They also analyse the effects of two different data collection strategies. The paper is well-executed and well-written. In terms of shortcomings, the paper: (1) has a limited experimental evaluation (2) treats table-lookup problems only (3) assumes that set of options is given (as opposed to learned) (4) provides an algorithm quite far from a practical larger-scale implementation. Overall I think these are OK in a theoretical paper (and the reviewers seem to agree).
Decision: Accept (poster)