Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrability
Authors: Hanlin Zhu
Amy Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: offline goal-conditioned RL
provably efficient algorithm
single-policy concentrability
general function approximation
TL;DR: We provide rigorous theoretical guarantees of a previously proposed empirically successful offline goal-conditioned RL algorithm under mild assumptions.

Abstract: Goal-conditioned reinforcement learning (GCRL) refers to learning general-purpose skills that aim to reach diverse goals. In particular, offline GCRL only requires purely pre-collected datasets to perform training tasks without additional interactions with the environment. Although offline GCRL has become increasingly prevalent and many previous works have demonstrated its empirical success, the theoretical understanding of efficient offline GCRL algorithms is not well established, especially when the state space is huge and the offline dataset only covers the policy we aim to learn. In this paper, we provide a rigorous theoretical analysis of an existing empirically successful offline GCRL algorithm. We prove that under slight modification, this algorithm enjoys an $\tilde{O}(\text{poly}(1/\epsilon))$ sample complexity (where $\epsilon$ is the desired suboptimality of the learned policy) with general function approximation thanks to the property of (semi-)strong convexity of the objective functions. We only require nearly minimal assumptions on the dataset (single-policy concentrability) and the function class (realizability). Moreover, this algorithm consists of two uninterleaved optimization steps, which we refer to as $V$-learning and policy learning, and is computationally stable since it does not involve minimax optimization. We also empirically validate our theory by showing that the modified algorithm outperforms the previous algorithm in various real-world environments.
To the best of our knowledge, this is the first algorithm that is both provably efficient with general function approximation and single-policy concentrability, and empirically successful without requiring solving minimax optimization problems.

Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrability
Hanlin Zhu EECS, UC Berkeley; Meta Al hanlinzhubbrrkely edu
Amy Zhang ECE, UT Austin; Meta AI
amy uny.zhng@austin. htw.:/aauuuiiutut.a..o.aa utw.as. edu
Abstract
Goal-conditioned reinforcement learning (GCRL) refers to learning general- purpose skills that aim reach diverse goals. In particular, offline GCRL only requires purely pre-collected datasets to perform training tasks without additional interactions with the environment. Although offline GCRL has become increas- ingly prevalent and many previous works have demonstrated its empirical success, the theoretical understanding of efficient offline GCRL algorithms is not well established, especially when the state space is huge and the offline dataset only covers the policy we aim learn. In this paper, we provide a rigorous theoretical analysis of an existing empirically successful offline GCRL algorithm. We prove that under slight modification, this algorithm enjoys an (ppoly1//e) sample com- plexity (where is the desired suboptimality of the learned policy) with general function approximation thanks to the property of (semi-)strong convexity of the objective functions. We only require nearly minimal assumptions on the dataset (single-policy concentrability) and the function class (realizability). Moreover, this algorithm consists of two uninterleaved optimization steps, which we refer to as V-learning and policy learning, and is computationally stable since it does not involve minimax optimization. We also empirically validate our theory by showing that the modified algorithm outperforms the previous algorithm in various real- world environments. To the best of our knowledge, this is the first algorithm that is both provably efficient with general function approximation and single-polic concentrability, and empirically successful without requiring solving minimax optimization problems.
1 Introduction
Goal-conditioned reinforcement learning (GCRL) aims design agents that able learn general- purpose skills to reach diverse goals Kaelbiing 1993 Schaul et al., 2015 Plappert et al. 2018). In particular, offline GCRL learns goal-reaching policies by purely pre-collected data without any further interactions with the environment [Chebotar et al., 2021 Yang et al.) 2022). Since such interaction can be expensive or even unsafe practice, offline GCRL increasingly popular as way to learn generalist agents in real-world environments [angee et al. 2012 Levine et al. 2020).
Although offline GCRL is promising and achieves great success in various practical scenarios [Lynch jtt al.] 2020 Chebotar et al. 2202 Yang et al.] 2022 Ma
[002bb]c 2022b] designing practical algorithms that are provably efficient still remains open question. On the practical side, an ideal algorithm should be scalable to huge (or infinite) state spaces and only require minimal dataset coverage assumptions. Moreover, the algorithm should be computationally efficient and stable (e.g., only
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

using regression based methods to train policies to avoid unstable minimax optimization). On the theoretical side, we aim to provide finite-sample guarantees of the learned policy,
Unfortunately, most existing algorithms are not both theoretically and practically efficient. On the one hand, many empirically efficient algorithms do not enjoy finite-sample guarantees (Lynchh et al.
2022c or even suffer constant suboptimality 2020 Chebotar et al., [022]] Yang et al. 2022 Ma et al.
2022e D. On the other hand, although many previous offline RL algorithms with theoretical finite- sample guarantees can be naturally extended
favorable settings given infinite data (e.g.. Ma et al.
to offline GCRL settings, they either cannot handle general value function approximation in the presence of huge (or infinite) state spaces (Jin et al. [202] Rashidinejad et al. [021] Yin et al. [2021] Shi al., 2022 Li et al. 2022], or require impractically strong dataset coverage assumptions, such as
all policy concentrability [Antos et al. 2008 Munos and Szepesvári 2008 Xie and Jiang (021b]]
Recently, several provably efficient algorithms have been proposed under general function approxi- mation and single-policy concentrability (Zhan et al. 2022] Cheng et al. [2022] Rashidinejad et al.)
2022]. In particular, the algorithm of [Zhan al. 2022], based on the duality form of regularized linear programming formulation of RL, only requires the realizability assumption of function class. However, they all require solving minimax optimization problems which can be difficult or compu- tationally unstable (Daskalakis et al. 202T]. On the contrary, some practically efficient algorithms (e.g., Ma et al. e do not involve minimax optimization and thus are computationally more stable. This naturally raises an important question:
(e.
Can we design an efficient offline GCRL algorithm that enjoys favorable theoretical guarantees under mild assumptions and performs well empirically in real-world scenarios without a minimax formulation?
In this paper, we answer the above question affirmatively by providing rigorous theoretical guarantees for empirically successful offline GCRL algorithm named GoFAR proposed by |Ma et al. [2022c]. We made some slight yet critical modifications to GoFAR. For deterministic MDPs, we need to carefully select the value of one hyperparameter that is set to in the original GoFAR (which can be tuned in practice). For stochastic MDPs, we need to first learn the true transition model via maximum likelihood (MLE) and then plug in the learned model in the algorithm. To distinguish the difference between the original algorithm and the modified ones, we name the modified versions VP-learning (Algorithm I.
We show that the VP-learning algorithm has both good empirical performance in real-world scenarios (already shown by Ma et al. (2022c), and we compare VP-learning and GoFAR empirically and show that our modification further improves the performance of the previous algorithm GoFAR) and favorable theoretical guarantees under mild assumptions. Specifically, it achieves (pooyy11/4) sample complexity (where is the desired suboptimality level of the learned policy) under general function approximation with realizability-only assumption and partial data coverage with single- policy concentrability assumption. Morcover, the VP-learning algorithm can be decomposed into two uninterleaved learning (optimization) procedures (i.c., V-learning and policy learning), which only require solving regression problems without minimax optimization.
Note that the VP-learning algorithm can be naturally applied to single-task RL settings, and all the analysis in this paper does not rely on whether the setting is goal-conditioned. Since the original algorithm proposed and empirically validated in goal-conditioned settings, we analyze the algorithm in gond-cond settings as well.
1.1 Related Work
Since our algorithm can be naturally applied to single-task offline RL settings, we discuss the related work in a broader scope, which also includes single-task offline RL.
Offline RL in tabular and linear function approximation settings. In tabular and linear settings, a line of work proposed efficient (both statistically and computationally) algorithms under single- policy concentrability [Jin et al. 2021 Rashidinejad et al.) 2021 Yin et al. 2021 (Shi et al.) 2022 Li et al. 2022]. These algorithms construct uncertainty quantifiers to ensure pessimism such that policies not well covered by the dataset (which, by single-policy concentrability assumption, are thus suboptimal) suffer large penalty. Yin and Wang [202]) also consider offline RL with single-policy

---

concentrability and achieve restance-depender characterization. However, the above algorithms cannot be directly applied to many practical scenarios when non-linear function approximators are required, since it is hard to obtain uncertainty quantifiers without oracle access when function approximators are non-linear [Jiang and Huang. 2020, Jii et al. 2021 Uehara and Sun 2021] Xie) et al. 2021]. In our algorithm (V-leaniigg step), we use regularizer in the form of f f-divergence instead of uncertainty quantifiers to ensure pessimism, which makes our algorithm efficient in the presence of non-linear function approximators without additional oracle access.
Offline RL with all-policy concentrability. Besides huge state spaces, another central challenge for offline RL is the lack of dataset coverability, Concentrability, defined as the ratio of occupancy frequency induced by a policy to the dataset distribution, is one of the most widely used definitions to
characterize the dataset coverability [Munos 2007 Scherrer 2014]. Many previous works require
all-policy concentrability to make the algorithm efficient [Szepesvári and Munos| 2005 Munos] (2077
Antos et al., 2007
2008 Farahmand et al.] 2010 [Scherrer] 2 et al.) 2019| and Jiang
2019 Jiang 2019 Wang et al. 2019 Feng et al. 2019 Liao et al. 2020 Zhang et al., [0200] Uchara
al. 2020 Xie and Jiang 2022 la). However, in practice, it is unreasonable to require that the offline
dataset can cover all candidate policies, and our algorithm only requires single-policy concentrability.
Offiine RL with general function approximation and single-policy concentrability. recent line of work, which is based on marginalized importance sampling (MIS) formulation of RL, has shown success either empirically [Nachum et al.] 2019a b Lee al., 2021 Kim et al. 2021
or theoretically [Zhan et al.) 2022 Rashidinejad et al. 2022]. In particular, Zhan et al. [0022].
Rashidinejad et al. [2022] provide sample guarantees for their algorithms under general function
approximation and only single-policy concentrability. Another line of work (Xie et al. [02 Cheng jet al. 2022] also proposes provably efficient algorithms based on an actor-critic formulation under similar assumptions. However, all the above algorithms require solving minimax optimization, which could be difficult or computationally unstable [Daskalakis et al. [222]] Instead, our algorithm only involves uninterleaved regression-base based optimization without minimax optimization.
Offline GCRL. In the context of offline GCRL, the sparsity of the reward is another core chal- lenge [Kaelllngg 1993 Schaul et al. 2015]. Several previous works aim to solve the issue and show empirical success without finite-sample guarantee [Ghosh et al. 2019 Chebotar et al. 2021 Yang et al. 2022 Ma al. 2022c). Although there exist theoretical studies of relevant problems such as the offline stochastic shortest path problem [Yin et al.) 2022). theoretical understanding of the offline GCRL problem is still lacking. The most relevant work to this paper is Ma al.) [2022c). which shows great performance in several real-world settings without minimax optimization but lacks theoretical guarantee. In this paper, we proved that a slightly modified version of their algorithm (i.e.. our VP-learning algorithm shown in Algorithm T is provably efficient. Also, we note that Ma et al. 2022a] can be viewed as the single-task version of Ma et al. [2022c], and our algorithm and analysis can be naturally extended to single-task offline RL settings.
2 Preliminaries
Basic Notations. Throughout this paper, we use | and A(X) to denote the cardinality and probability simplex of given set X. We use S y denote that there exists constant e > 0 such that & S cy use x 2 y if $ x and use x x if x S y and y S x. Also, we use the standard O()) notation where f(n) n no. and denote f(n) (g((n) g(n) (((()). For any x RR define x4 A max (2r 0}: for any general function ʃ X + R, define f=(x) = max (x) 0). Vx E X. Also, for any function f: + F. define f(x) f() min f(u) for any Z if min fu) exists and further overwrite the notation (x) = (x) 2 0} 10-f(oe f(z) where 1 {-} is the indicator function.
(gg(n)) if there exists no: C 0 such that (f)) Cg(n) for all
Markoy decision process. We consider an iafinite-horize
discounted Markov decision process (MDP), which is described by a tuple M = (S. A. P. R. (....,), 7). where S and AA denote the state and
action spaces respectively, P S A - (SS) is the transition kernel, R: S x A + A 1)) encodes a family of reward distributions given state-action pairs with : S x A + [0, 1] as the
expected reward function, S + [0, 1] is the initial state distribution, and y E [0, 1) is the discount
factor. We assume A is finite while S could be arbitrarily complex (even continuous) in many
3

---

real-world scenarios. A stationary (stochastic) policy π S + ((A) outputs a distribution over action space for each state.
Goal-conditioned reinforcement learning. In goal-conditioed RL, we additionally assume goal set G. Similar to Ma et al. [002cc] in goal-conditioned settings, the reward function R((s; (as well as the expected reward function r(s: g)) and policy x [aass, g) also depend on the commanded goal g E G, and the reward no longer depends on the action a and deterministic.
Each (goal-conditioned) policy π induces a (discounted) occupancy density over state-action pairs for any commanded goal d' 8 x A x 9 + [0, 1] defined d" (s,0; g) == (1 - 7) E 7 Pr(s; 8, Oz. = a; R),, where Pr(*; = 8, dg. = a; TT) denotes the visitation probability of state-action pair (s, a) step t. starting at so p(.) and following π given commanded goal g. We also write
dd (s; = = ds a;g) to denote the marginalized state occupancy. Let p(g) be a distribution
over desired goals, then we denote (s, g) = (s. a; g)p(g) and d" (s. g) = d (s; g)p(g). An important property of occupancy density d" is that it satisfies the following Bellman flow constraint:
Σ Edls, = (1 (1- +))))++>
Σ 8a.a"
P(ols', d')d(s's d':
for all 8 E S and g e 9 when letting d = dd for any policy x. Moreover, any d satisfying ( is the occupancy density of policy Ta where
<a(a|s,g) = [dsss a(ss,a;)/d(s:0)) |//|A|
d(s;g) >0 0 d(s:g) = 0
and d(s:g) = Σ d(s.
(2)
acA
An important quantity associated with a policy n is the value function, which the expected dis- counted cumulative reward defined as V V*(s;; g) == E == y'r, 8p 8,0 ~ (1(1,,,00 g) A 2 0] starting at state & E S with a commanded goal g E 9 where r; = R(s;g)
g)) We use the notation (TT == (1 ->)pe=pppppp (V=((:))) = (s.. (r(s; g)] to represent scalar summary of the performance of a policy æ. We denote by n² the optimal policy that maximizes the above objective and use V = V" to denote the optimal value function.
Offline GCRL. In this paper, we focus on offline GCRL, where the agent is only provided with a previously-coll
offline dataset D {(s,, a; ri; s/ 9:) ) Here, r; ~ R(s;; 9:), sf ~ P(. 8;, a;), and we assume that 9i are i.i.d. sampled from p(-) and it is common that data are collected by a behavior policy j of which the discounted occupancy density (ss, (;)g;) are sampled i.i.d. from distribution μ where ju(s, a. g) =p(g)d (s, a; d' d' a, g.))) Note that we use z to denote both the behavior policy and the dataset distribution. We also assume an additional dataset Do = {(o... (o.,:.g..))) No where 80.2 are i.i.d. sampled from p(.) and go.; are i.i.d. sampled from p(-). The goal of offline RL is to learn a policy a using the offline dataset so as to minimize the sub-optimality compared to the optimal policy π², i.c., J(T') - J(+), with high probability.
d², Therefore, we assume that
Function approximation. To deal with huge state spaces, (general) function approximation necessary for practical scenarios. In this paper, we assume access to two function classes: a value function class V C (V S G - [0. Vm that models the value function of the (regularized) optimal policies, and policy class 1I C {T S x G + ((A)) consisting of candidate policies. For stochastic MDP (Section 3.1.2), we also need a transition kernel class P ( S x A A(S) which contains the grouhd-truth transition kernel. Additionally, for any function f S x G + RR we denote the operator T IR Sxg + s as (Tf) a: g) = E -p (f g)]. Also, for any function V S 9 > [0, Vina)), we define Av a; g) = r rs: g) + 7TV (; Vss
Offiine data coverage assumption. Our algorithm works within the single-policy concentrability framework [Rashidinejad et al. (021], which is defined as below.
Definition 1 (Single-policy concentrability for GCRL). Given a policy n, define CR to be the smallest d' (s.agg) < Ca for all s E S, E and g E G. constant that satisfies
a(s.a.g)
The single-policy concentrability parameter C' captures the coverage of policy π in the offline data. Our algorithm only requires this parameter to be small for nh which is a regularized optimal policy

---

(see Section for formal definition) and is close to some optimal policy, This assumption is similar to Zhan a.. 2022 and and is much weaker than the widely used all all-policy concentrability that assumes bounded C for all Scherrer 2014)
3 Algorithms
Offline GCRL can formulated as the following program:
max
((sg))
33 requires solving an optimization problem over the policy space. One can also optimize over occupancy density d(ss, () s.t. d = d for some policy which equivalent that d satisfies Bellman flow constraint ① Therefore, the program (3) can be represented equivalently as follows:
max d(s,a:9)20 20
E ((sa))d((ss)
(4)
s.t.
Σ
+ E a's)s' s/,aa
((s.))
Let d" denote the optimal solution of ( then (one of) the optimal policy can be induced by re
as in (2). Under partial data coverage assumptions, (4) might fail in empirical settings by choosing highly suboptimal policy that is not well covered by the dataset with constant probability. Similar to
Zhan et al. [202]] Ma et al. [2022c), regularizer is needed to ensure that the learned policy is well covered by the dataset. Therefore, one should instead solve regularized version of (4) which is
stated as follows:
max d(s,a:g)20
((sg))d(o.)) aDD
s.t. Σ d(s,a;g)) =
+ d'dsss.''dd''''''g) ((s,))eSxe (5)
st,a'
where the f-divergence defined as (y(d]lu) A T. (( ([ a, 9) g)/ 0, g) for convex function f. Throughout this paper, we choose f(x) = (x - 1)2 as in Ma et al. 2022c where the f-divergence known as divdivereence under this specific choice of / and is shown to be more stable than other divergences such as KI. divergence (Ma et al. 2022c). Let d% denote the optimal solution of (5). then the regularized optimal policy can be induced by Th = Rd; as in (2). The following single-policy concentrability assumption assumes that na is well covered by the offline dataset.
Assumption (Single-policy concentrability for T²)). Let d' be the optimal solution of 5 and let T. Taz as defined in (2). We assume C S C. where C is defined in Definition and Ca > constant.
Under Assumption I can be observed that the performance difference between the regularized optimal policy T and the optimal policy x" is bounded by O(a). The following proposition formally presents this observation.
Proposition 3.1. Let d'a be the optimal solution of (5) and let o. Td; as defined in ? under Assumption holds that " SO (o(C)))
Then
The proof of Proposition 3.1 is deferred to Appendix A. Proposition 3.1 shows that by solving the
regularized program (5). we can obtain a near-optimal policy as long as a is small. The algorithm Ma et al. [2022c also aims to solve (5) and they simply choose = 1. We show empirically in Section 5haat a achieves better performance than a In theory, we must carefully choose the value of a s.t. the suboptimality of our learned policy vanishes to with reasonable rate. Finally, as in Ma et al. [2022c], we convert (5) to the dual form, which is an unconstrained problem and
amenable to solve:
Proposition 3.2 (Dual form of (5). The duality form of 55 is
min - (17))) ()g + (ss. (1 (4t
(Ag
((sg)20
(6)
5

---

where is the convex conjugate of = a. Moreover, let V denote the optimal solution of (6) then it holds
+ (8, dz (8, a: g) - p(s, 7
(z;
for all (s, E Axg.
The proof of Proposition 3.2 is shown in Appendix A.2 According to the above proposition, one can first learn the V function according (6). and then use the learned V function learn the desired policy by 77. We call the first step V-learning and the second step policy learning, which will be
discussed in detail Sections 3.1 and 3.2 respectively. Finally, the main algorithm, which we call
VP-learning, is presented in Algorithm
Algorithm Velleann
Input: Dataset D {s,, ag sy. 9:) f==1 Do (0,0,:90.))) 90.)) value function class V.
policy class II, model class P for stochastic settings.
2: Obtain U by V-Learning (Algorithm or 3)
3: Obtain ă by policy learning (Algorithm using learned function U.
4: Output: n.
3.1 V V-Learning
Define
La (V) [a(1 - (oa0) + (ela))-a("(((AA/(ssss (2) (Av
Then 6 is equivalent minv La (V). A natural estimator of (v) is
N
1-7 V(sux:
1
Σ
a. (a.gr4(r + 7V ((ssgg)))
N
However, when the transition kernel deterministic, this estimator is biased and will cause an over-estimation issue since g-(x) = af-(x/a) a<#/a+1)"
contains a square operator outside
of the Bellman operator (consider estimating (B using N X?).
Therefore, use the original version of Ma et al. [022c for V-learning in deterministic dynamics
(Algorithm 2 in Se.tiooB..1.I. and a slightly modified version in stochastic dynamics (Algorithm) in Section 3.1.2.. For both settings, assume realizability of V value function class V:
Assumption (Realizability of V:)) Assume Va E V.
3.1.1 V-Learning in Deterministic Dynamics
When the transition kernel P is deterministic, it holds that TV(s, a; V(s': g) where P(s'|s.a) this case, the natural estimator 2 unbiased and can directly applied to the V-learning procedure. The V-learning algorithm for deterministic dynamic settings is presented in Algorithm
Algorithm 2 V Velannnn in deterministic dynamics
1: Input: Dataset = {(ss, d,, ri, a/ ) Do = {000., 9o. No value function class V. 2: V-learning by solving = arg minvey (() where
[V) &
1
Σ 1=1
V(Su,s
Σ
g.+ g.+ (r. (V(5::)) - V(s:g.)). (10)
No
3: (s)a; + -((3g) + (s':g) ((s; +
4: Output: V.Ù.
Now for any V. we define (s, a: r(;;g) (V,,, - +a Av a; + a which can be interpreted as the advantage function of V with an a-shift. We also denote U = Uv:

---

Note that besides the learned V function, Algorithm 2 also outputs a Ü function. By one can observe that in policy learning, what we indeed need is Ú instead of V. and thus in the V-learning procedure we also compute this Ü function in preparation for policy learning.
One may challenge that cannot be computed for all (s,a;g) g) since we do not have knowledge of all r(s.g)) However, we only need the value of (sa, az 9b) for (8i, az (ggg;) contained in the offline dataset, where r, is also contained. Therefore, requested in the policy learning algorithm.
evaluate the value of U all (s g) tuples
Note that Algorithm iis equivalent to the first step of Ma al. [2022c] except for the choice of a and a clip for the value of g.. However, the above V-learning, as well as the original GoFAR algorithm, might suffer the over-estimation issue under stochastic dynamics, and present algorithms suitable for stochastic dynamics in Section 3.1.2
3.1.2 V-Learnin Stochastic Dynamics
When the transition kernel is stochastic, cannot directly use g() to estimate (V(s, a; Since (V g; = ((-ss())s,))) [V (V's' g)], a natural idea is to learn the ground-truth transition kernel P_ first, and then the learned transition kernel P to estimate (V(s, a; (V(ssa;)) E, (-Is,a)))) [V(s'g))] This achievable under the following realizability assumption.
Assumption (Realizability of the ground-trune -ound transition model). Assume the ground-truth transi- tion kernel p* E P.
The algorithm for stochastic dynamic settings is presented in Algorithm 3 where we first learn the transition kernel P, and then plug the learned transition kernel to learn V function. Similar to Algorithm we also compute in V-learning procedure.
Algorithm 3 V-learning in stochastic dynamics
1: Input: Dataset D = {(s,, a, Th, s/,, 9)) Do [ value function class V. model class P.
2: Estimate the transition kernel via maximum likelihood estimation (MLE)
N log (())(s;,a;)
- max PEP
Σ
(11)
N
3: V-learing using the learned transition kernel: V arg miny ev (V) with
(V)(V) & 1-7 No
N
Σ a 1=1
+ (oa.s:oo.)
a
9. (r. + + 7TV V(sggi)). (12)
No
N
where TV (g:g) P((aa)) (Vs':g))
4: Ü(s, () + r(s;g) (8, ((sgg) +
5: Output: V.U.
3.2 Policy Learning
We now derive policy learning, the second step of the VP-learning algorithm. Note that m =
arg max, E (s [agss()s By (7). also have
U (=
d, = +. (s: =((saa))))
For notation convenience, stochastic settings, use 1* to denote the ground ground-truth transition kernl.
7

---

(g Therefore, TH arg max,, (T) where ( (TT) & ((s,a,)~
log (a g) Since
o
we already learned U, which is close to U we can use the following estimator for L (T):
N Üss, az (ii log ग
MLE n
(13)
N
Algorithm 4 Policy learning
Input: Dataset {(s,, Ti 5/ 9:) g policy class II, Ú learned by Algorithm 2r
2: Policy learning by:
Üs 04i (:)9:
arg max L MLE
log π (a; (s)
(14)
Tell
t=
3: Output: A.
The policy learning algorithm is presented in Algorithm which can be viewed as weighted maximum likelihood estimation (MLE) procedure. Finally, we make the following two assumptions on the policy class IT.
Assumption 4 (Single-policy realizability). Assume Ta E II.
Assumption (Lower bound of policy). For any policy II, we assume that (aaas. g) 2 27> for any (s, a. 9) E x A G.
Remark One may consider Assumption strong if is a constant independent of or N. However, In that case, be extremely small, and any policy mixed with
allow that depends uniform policy with a tiny probability satisfies this assumption. Therefore, Assumption 3 is mild.
Theoretical Guarantees
In this section, we provide theoretical guarantees of our main algorithm (Algorithm T). We first show the results for V- V-Learning and policy learning in Section 4.1 and Section 4.2 respectively and then combine them to obtain our main theorem Section 4.3
4.1 Analysis of V V-Learning
We mainly focus on V-learning in deterministic dynamics in this section. The analysis for stochastic dynamics is similar and presented in Appendix B.2
As discussed in Section 3.1.1] although the first step of the algorithm is called V-learning, the main goal of this step is estimate U Uv; accurately. The following lemma provides a theoretical
guarantee that the output V-learning algorithm Ü a good estimator of U in positive parts:
Lemma (Closeness of U4 and U.+). Under Assumptions andd with probability at least 1 I|O U.+ U2+ O (Vesm)) where is the output of Algorithm and Cuua
1/2 max
log( (V)
Proof sketch. By standard concentration argument, it can be shown that the empirical estimator (() in Algorithm (which is unbiased in deterministic dynamics) concentrates well on L., for all V V (Lemma 3). Therefore, by realizability of V., the value of La at V." and the learned V-function V. are close (Lemma 4p. Finally, one can observe that I., is "semi-strongly" convex w.r.t. Uv in norm, and thus
show that Ü. and U*+ also close.
The complete proof Lemma is deferred to Appendix B.1 Appendix B.2 we also show the counterpart of Lemmal D for stochastic dynamic settings.

---

4.2 Analysis of Policy Learning
After obtaining accurate estimator Ú_ of U*_ in the V-Learning procedure, i.e., || - 12
v Cestats we can use U+ to perform policy learning and obtain the following guarantee:
Lemma (Closeness of T. and 8). Under Assumptions and with probability at least 1 - 8, the output policy it of Algorithm satiifies
Eg pwplaill =-118 O ( T
(V
where stat is defined in Lemma 8
The proof of Lemma provided Appendix C.2 the regularized optimal policy T. and the outpui policy म by Algorithm 4 is small, which translates to bounded performance difference between these two policies as formalized Theorem
This result shows that the TV distance between
Theorem (Suboptimality of t). Under Assumptions 4 ladd with probability at least - 6, the
ouppu policy tt of Algorithm 4 satisfies (TTa) J(tt S O (mmax
MLLEE 7
The proof of Theorem deferred to Appendix
4.3 Main Theorem:
Statistical Rate of Suboopimaaiity
Theorem compares the performance difference between R and the regularized optimal policy nr- Since the ultimate goal to compare with the optimal policy x², we also need to combine this result with Proposition 3.1 By carefully choosing the value of a to balance ( ( and
-(x) J(=a), we can bound the suboptimality of the policy Ā output by Algorithm I compared to the optimal policy n², leading to the following main result:
Theorem (Statistical rate of suboptimality (in deterministic dynamics)). Under Assumptions 7
2 4 and 5 with probability at least 1 - 5, the outpul policy & by Algorithm !
(with the choice of
Algorithm for V-learning in deterministic dynamics) satisfies
V3
max ( log( loggl/ 1/3
-(=") J(+))
72N1/4
we choose a x (imi log(1//) ( 1/3 and assume N No-
The proof of Theorem 2 is deferred to Appendix D.I Note that Theorem Theorem suboptimalityy rate of (11/N1/12) which implies an O (1/poly(c)) sample complexity and thus is statistically efficient. A similar rate can also be obtained in stochastic dynamic settings, and we present the result in Appendix D.2 Note that our rate is slightly worse than the (11/N1/6) rate in Zhan et al. [2022] and worse than the optimal rate O(1/VN) in Rashidinejad et al. [2022]. We briefly discuss the intrinsic difficulty to derive an optimal convergence rate. First, we only require realizability assumption on our function class, while |Rashdiinejad et al. (2022) requires much stronger completeness assumption. Second, our optimization procedure uninterleaved and only requires solving regression problems, while Zhan et al. (2022) and Rashidinejaa et al. [2022) require solving minimax problems. Finally, Rashidinejjd et al. [2022] assumes that the behavior policy is known and directly computes the policy using the knowledge of behavior policy, while our algorithm uses a more practical method, i.c.. MLE, to solve the policy in the policy learning step.
We also compare our theoretical results to Ma et al. [022cc Theorem 4.1 of Ma et al. 2022c provides a finite-sample sample guarantee for the suboptimality. However, they compare the performance of 1) instead of π²" Since the performance gap between π and т can be as large
f to =; (with as a constant when a = 1, even zero suboptimality (compared to = cannot imply that the learned policy has good performance. Moreover, their theoretical analysis assumes that V* can be learned with zero error, which is unreasonable in practical scenarios. We also note that they only provide proof for deterministic policy classes, which can be restrictive in practice.

---

5 Experiments
In this section, we provide experimental results of our VP-learning algorithm with different choices of a under five different environments: FetchReach, FetchPick, FetchPush, FetchSlide, and Han- dReach [Plappert et al., 2018). Similar to Ma et al. (2022c). the datasets for the five tasks are from Yang et al. [2022] All the implementation details of our VP-learning are the same as GoFAR (see dataset details and implementation details in Ma et al. (202cc) except for the value of a. Note that our VP-learning algorithm with 1 is equivalent to the GoFAR algorithm. Table [ablee[preentt the discounted returns and Table pressenss the final distances of the policies trained after 100 epochs and evaluated over 10 runs. For each environment and each a the result was averaged over 3 random seeds. The best results of each environment are in bold.
Table 1: Discounted return of different choices of a, averaged over random seeds.
a) Env
FetchReach
FetchPick
FetchPush
FetchSlide
HandReach
0.01
27.4 0.29
18.5 1. 0.1
18.0 1: 1.8
2.36 1: 1.13
8.72 d: 1.69
0.02
27.4
18.7 + 1.8
18.6 + 2.6
2.40 + 0.47
7.96 + 1.27
0.05
27.4 1: 0.32
17.3 1: 1.1
19.3 1: 2.0
3.18 1: 0.90
8.98 1: 3.11
0.1
27.4 0.33
20.3 +: 1.3
20.3 + 2.5
3.22 +: 0.38
5.28 +: 1:25
0.2
27.4 :: 0.32
20.7 0.9
17.7 1: 2.9
2:25 1: 0.23
2.92 d: 0.98
0.5
27.5
0.29
18.5 0.4
20.1 + 2.2
3.47 1.08
5.74 +: 2.72
1
27.3 0.34
18.2 4: 1.2
19.6 +: 1.6
2.75 4: 1.84
7.13 d: 3.60
2
27.1 0.29
18.3
19.6 1.4
1.80 +: 0.66
3.99 +: 1.88
Table 2: Final distance of different choices of a, averaged over 3 random seeds.
a Eav
FetchReach
FotchPick
FetchPash
FeichSüdde
HandReach
0.0171
0.0017
1: 0.004
0.001
0.1177 1. 0.012
0.0269 0.0049
0.0168 = 0.0016
0.045 + 0.012
0.031 = 0.002
0.1085 + 0.010
0.0274 0.0049
0.0181
0.0011
0.052 1: 0.013
0.032
0.002
0.1061 1: 0.009
0.0270 0.0049
0.1
0.01 73 = 0.0014
0.032 + 0.010
0.027 0.002
0.1018 + 0.002
U.0275 + 0.0043
0.2
0.0172 = 0.0019
0.031 0.001
0.081 = 0.003
0.1029 + 0.010
0.0275 + 0.0016
0.5
0.0166 = 0.0011
0.044 + 0.009
0.031 - 0.005
0.1017 0.017
0.026826 + 0.00-19
0.0175 = 0.0013
0.043 + 0.011
0.013 = 0.012
0.1202 + 0.019
0.026828 0.0011
0.0171 0.0011
0.034 1: 0.005
0.032 1i 0.001
0.1044 1: 0.011
0.0275 1: 0.0045
The empirical results demonstrate the correctness of our theoretical analysis: choosing a will result in a large suboptimality of n" and thus the learned policy Ā. Instead, we should carefully choose the value of a to ensure vanishing suboptimality. In practice, we can tune the value of a and typically it is less than one. In our experiments, the best ranges over [0.05, 0.5).
Conclusions
In this paper, we theoretically analyze the VP-learning algorithm (Algorithm which is based on the previous empirically successful algorithm in Ma et al. (202cc) for both single-task and goal- conditioned offline settings. This algorithm can deal with general value function approximation and only requires near minimal assumptions on the dataset (single-policy concentrability) and function class (realizability). We also provide an O(1 O(1/N1/12) upper bound of the suboptimality of the policy learned by the algorithm and empirically validate its effectiveness.
As for future directions, one important question is whether we can achieve the optimal suboptimality rate Õ /N) while keeping the algorithm practical without unreasonably strong assumptions.
We use the code at http::///gghibb..cca/aaaaaaatssp with different values of a for our exper- iments.
10

---

Acknowledgements
We thank the anonymous reviewer for catching a technical issue in previous version of our paper. The work was done when HZ was visiting researcher at Meta.
References
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pages 10-4, 2019.
Andras Antos, Rémi Munos, and Csaba Szepesvari. Fitted Q-iteration in continuous action-space mdps. In Neural Information Processing Systems, 2007.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 1299, 2008.
Yevgen Chebotar, Karol Hausman, Yao Lu, Ted Xiao, Dmitry Kalashnikov, Jake Varley, Alex Irpan, Benjamin Eysenbach, Ryan Julian, Chelsea Finn, et al. Actionable models: Unsupervised offline reinforcement learning of robotic skills. arXiv preprint arXiv:2104.07749 2021.
Jinglin Chen and Nan Jiang. inoommtiionthhoreele considerations in batch reinforcement learning. arXiv preprint arXiv: arXiv:1905.00 1905.0030, 2019.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3852 3878. PMLR, 17-23 Jul 2022. URL https: htttps://proceedings mlr www.ppesss//... wwtpppewssseeeeeeee httpss/vv2/ccheenge cheng22b html
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 1478, 2021.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. Advances in Neural Information Processing Systems, 2010.
Yihao Feng, Lihong Li, and Qiang Liu. A kernll loss for solving the Bellman equation. arXiv preprint 1905vv1900..000
2019.
Dibya Ghosh, Abhishek Gupta, Ashwin Reddy, Justin Fu, Coline Devin, Benjamin Eysenbach, and Sergey Levine. Learning to reach goals via iterated supervised learning. arXiv preprint arXiv:1912.06088, 2019.
Nan Jiang. On value functions and the agent-envinonment boundary. arXiv preprint arXiv:1905.1334 2019.
Nan Jiang and Jiawei Huang. Minimax value interval for off- evaluation and policy optimization. Advances in Neural Information Processing Systems, 33, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5086-5096. PMLR, 2021.
Leslie Pack Kaelbling. Learning to achieve goals. In IJCAI, volume 2, pages 1094-8. Citeseer, 1993.
Geon-Hyeong Kim, Scokin Sco, Jongmin Lee, Wonseok Jeon, HyeongJoo Hwang, Hongseok Yang. and Kee-Eung Kim. Demodice: Offline imitation learning with supplementary imperfect demonstrations. In International Conference Learning Representations, 2021.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.

---

Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning, pages 202--133 PMLR, 2021.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05225, 2022.
Peng Liao, Zhengling Qi, and Susan Murphy. Batch policy learning in average reward Markoy decision processes. arXiv preprint arXiv:2007.11771, 2020.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. In Neural Information Processing Systems, 2019.
Corey Lynch, Mohi Khansari, Ted Xiao, Vikash Kumar, Jonathan Tompson, Sergey Levine, and Pierre Sermanet. Learning latent plans from play. In Conference on robot learning, pages 1113-1132. PMLR, 2020.
Yecheng Jason Ma, Andrew Shen, Dinesh Jayaraman, and Osbert Bastani. Smodice: Versatile offline imitation learning via state occupancy matching. arXiv preprint arXiv:2202.02433, 2022a.
Yecheng Jason Ma, Shagun Sodhani, Dinesh Jayaraman, Osbert Bastani, Vikash Kumar, and Amy Zhang. Vip: Towards universal visual reward and representation via value-implicit pre-training. arXiv preprint Xiv:22i0::.... 000000 2022b.
Yecheng Jason Ma, Jason Yan, Dinesh Jayaraman, and Osbert Bastani. How far i'll go: Offline goal- conditioned reinforcement learning via a-avvantage regression, arXiv preprint arXiv:2206.03022, 2022c.
Rémi Munos.
Performance bounds in norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-561, 2007. 2007.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 32, 2019a.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.020 2019b.
Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, et al. Multi-goal reinforcement learn- ing: Challenging robotics environments and request for research. arXiv preprint 100i::8802.0944 2018.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 14:11702-11716 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang. Stuart Russell, and Jiantao Jiao. Optimal conser- vative offline rl with general function approximation via augmented lagrangian. arXiv preprint 1:Xiv:2211.0077 16, 2022.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference on machine learning, pages 1312-1320. PMLR, 2015.
Bruno Scherrer. Approximate policy iteration schemes: comparison. In International Conference on Machine Learning, pages 1312-1322, 2014.
12

---

Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint arXiv:2202.13890 2022.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference Learning Representations, 2021.
Masatoshi Uchara, Jiawei Huang, and Nan Jiang. Minimax weight and Q-function learning for off- policy evaluation. In International Conference on Machine Learning, pages 9659-9668, PMLR, 2020.
Sara Van de Geer. 2000.
Empirical Processes M-estimation, volume 6. Cambridge university press,
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11404-11413, PMLR, 2021a.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, pages 11404 11413, PMLR, 2021b.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consiste pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021.
Rui Yang, Yiming Lu, Wenzhe Li, Hao Sun, Meng Fang, Yali Du, Xiu Li, Lei Han, and Chongjic Zhang. Rethinking goal-conditioned supervised learning and its connection to offline rl. arXiv preprint arXiv:2202.044778 2022.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances neural information processing systems, 34:4065-4077 2021.
Ming Yin, Yu Bai, and Yu- Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01744. 2021.
Ming Yin, Wenjing Chen, Mengdi Wang, and Yu-Xiang Wang. Offline stochastic shortest path: Learning, evaluation and towards optimality. Uncertainty in Artificial Intelligence, pages PMLR, 2022.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages
PMLR, 2022.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Varia- tional policy gradient method for reinforcement learning with general utilities. arXiv preprint arXiv:2007.02151. 2020.
13

---

A Missing Proofs for Propositions in Section 3
A.1 Proof of Proposition 3.1
Proof.
Since both d' and d' satisfy the Bellman flow constraint II due to the optimality of da in the regularized program (5). we have
des 9)) + aDy(d"lla) (1a) S Bis.g) aDy (dD (l))
B((s)) (r:::) ((o.))aat (s S aDy(dall)) S 2/C2)
Therefore,
J( - (TT( = Besg) (
A.2 Proof of Proposition 3.2
Proof. By Lagrangian duality, we can obtain that the dual problem is
min maxdd v(sg)22
(a-))o(s)+ +
(15)
Σ ((g))(s:g) #.
Σ
P(sss''d''ddss Σ d(s,a;
6'.a'
where (sg)V(s:g) is the Lagrangian vector. Similar Ma [202cc]
Σ ((l Σ
8'aa'
Σ plg)d((s' d':g) Σ d()
.9
plg)d(s' d' dg)) 8 9
Then 15 is equivalent to
min maX - (ar ((agl20
- V(s
-aD,(d(s,a
which can be further represented
min (1 - (1-7)]B (ooo))) pa t (TV(s, ((ag120
-(sss)
DD,dd(s, (r(dss,agg)lll (,l,,, a;g)),
where 9 a f. Combining the constraint that d(s, a: g) 2 and the proof of Proposition 4.3 (Proposition B.2) of of et al. (002c), the above program is equivalent to
min - E (..0) (V(s:)) ((=g)22
( (s. a) 2 0)g. (Av (8, a: g)))
and it holds that
B Proof for V V-Learning
In this section, we provide theoretical analysis for the guarantees --larnning different settings (deterministic dynamics in Appendix B.I and stochastic dynamics in Appendix B.2
14

---

Recall that choose [(x (x-1)²² and thus fx(x) (x+1)² Therefore,
2
have g(œ) az( a(x-1)² and ga(x) a(x/a+1)²
Also, define Ja,max maxve[--Vaze + (v), min = mim Vmnsn Vmnx+ (v) and I.A 9o max min We easily obtain that Ir a(1 Vimax D(Vaax/a)
2
For the purpose of theoretical analysis, we further define
(V) =(1 3) V(s:))
L2(V) (s g.- (r( ( (7V V
and
(v) 1 V(50,1900.))
No
N
(V)
a g++ g++ (+(()))))+++++ +V((g))))) ((s;g:)))
Note that (V) = LvV + L2(V) and (V) 11th (V) + (V).
B.1 Proof for Deterministic Dynamics
We first show that with high probability, the estimator (V) in Algorithm 2 concentrates well on La(V) for all V V.
Lemma 3 (Concentration of i.()) f.(.). Under Assumptions / and when the dynamic of the environment is deterministic, with probability at least 1 5, VV E V. it simultaneously holds that
log(
30
aV aViaax
No
(1
log (V188
- (V)
0o
a 9
N
= 0
V2
max
N
which immediately implies
log(1>1/0)
log([V//5) N
[v) -
aV @Vmmax 50
No
+
V22
max
Estar
Proof. First, fix any V V. The expectation of i (V) is
No
BLi (1) (V)l
1 1-7
B B 90. V (Su,s 9o.)]
No
==1
=(1 - (e.e)))))))) ((sgg)
=V,(V).
Also,
N
BLLL (1) (V)
E B(x.a. ()(:)))))))+++ +V((s:))))))))) - ((s:g)))
N
N
1
E B(scan.))aal ( ((s 9.))
N
(V).
15

---

Also note that (so, 90.x) [0, Viaxl and g++ (r(s;: gi) + (T, a;: ((s:gg)
[0, gr,a).
By Hoeftding's inequality and a union bound, we have with probability at least
l0g(1/0)
(V) - Li() 5o
aViax V
No
(
1 (V) - L2(V) 0
gr
N
Applying a union bound over all V V concludes the result.
Next, we show that the value of La the regularized optimal V-function Vi and the learned function V is close.
Lemma (Closeness of the population objective of V and V.), Under Assumptions 7 and with probability at least - 8, we huve
(V) (V²) S (CCma))
Proof. We condition on the high probability event in Lemma 3 Note that
(V) La (Va) = LV) ( L (0) (V) (V.) (Va) La
(2)
(1), (3) S (Estat by Lemma 3 and (2) S 0 by the definition of V, which completes the proof.
Now we define "semi-strong" convexity, which is used prove Lemma and might be of independent interests.
Definition (Positive semi-strong convexity). For an arbitrary set X, assume F C (f X R)
is convex set. Let p A(X) be a probability distribution over X. The 11-1l,,p
F is
defined as 1| (f Define functioon 1: IR R and define functional C F + as
L(F) Ex>p!(((<>)))
We say L is o--postiivessemi-stronnlly convex W.E. in norl for some 0 if
C(F) |1
is convex w.rll f in 11-112,, noom.
Note that the common o-strongly convex definition requires C(f)
fl to be convex. Now we
prove the following property for ppositive-semi-siieee strong convexity.
Proposition B.1. Under the same setting of Definition 2
L is o--poxifive-semii-stonnngy convex w.r.t
in |I- norr,, holds that for any f.9 E
C(f) L(g) VC(g) - g) + = Ilf++ -9+11
Proof. By Definition 2 Ê(S) C()) $11f 11,,,1 is convex, which, by the definition of convex,
implies that
Σ(f ((g) 2 vā(g) -9)-
Plugging in the definition Z(-), we have
0 1l.+ ( + σ 19 12 (f (0)
C(f)
2
16

---

Rearranging, we can obtain that
- >v((g) - 9) -oooo-pp((())) - + + | 8
1 11
2 E E -2 ((()))20())))))))))))) (f(x) 9(x))]
-VC(g) - 9)
0
2
-VC(g) - 9) E Ba-p [ (I) - 9 2g(x) (f(x) 2(x))
-VC(g) - 9) + 0 1 11 -9
+ (= f(x))] + oo g (x))).
It suffices to show that
(x)(f f(x))) 2 0,
2 0.
Note that for any x E X. 9+ (x) 2 0 and f (x) f(x). which implies g+ (2)) S (2) - f(x))( 0.
Also, note that when g(x) 2 we have ((x)
- 9+ (z) and when g(x) 0, we have g+ (I)
which means (I) 9+ (+))) = 0. Therefore, we have
Be (x) - f(x)) 2 O,
g- (x))] = O,
which concludes.
Finally, by semi-strong convexity of La w.r.t. Uy in I1- norm, we can show that O and Ug are also close.
Proof of Lemmal 7 We condition the high probability event in Lemma 3 Recall that Uv (8,a;)
r(s; g) + > TV a: g) - V(s;g) + a and deterministic dynamics, ú = Ug. Let = (Uv V
[ R [X) which is a convex set by definition. Also, since Uv is linear in V. can also obtain that V can linearly represented by U. Therefore, we can define that (Uv)
R |
(V)
and - (s, a, g)+] is linear and thus convex in Uv which implies that La (Uv) prositive-semi-stronne convex w.r.t. Uv and I|-1|2, Then, by Proposition B. we have
LO) (U VÚ.(U:) U2) +
1110= u2)+
U@+ U2+112
Since U arg mincru (U), by the first order optimality condition, it holds that Vi (Ú- U 2 0. Combining Lemma we have
114
2((a(()) La (U2)) S ( Estat
B.2 Proof for Stochastic Dynamics
In stochastic dynamic settings, we first learn the ground-truth transition model and then calculate Ú The following lemma provides theoretical guarantee for maximum likelihood estimation (MLE) that P and P* are close.
Lemma (Convergence rate of MLE, Van de Geer (000 For any fixed 5 O. with probability at least 8, we have
log([P) /8)
B( [ a)) S
N
where P defined as This immediately implies that
log([P (I/8)
E Es [1(()ss Pm* (-1ss, S
N
17

---

Equipped with Lemma 5 we can guarantee that for any V, the population objective La (V) is close to the empirical objective (V))), (V), which is presented in Lemma
Lemma (Concentration of [(.)). Under Assumptions it holds that
t0
with probability at least - VV E V.
log( (og(V1//)) No
log( (V/0)
log( (P/0)
a aVVmaoy
+
V2
7V2
stochastic
max
N
max
N
stat
Proof. For convenience, define
1-7 No
(V
No Σ a (80.653000). i=1
(V)
g++ (r(s:5g)) - +TV( ag3 - Vss::
= N
Note that 2 (V) (V) and thus by Lemma we have that with probability least 1 6, for all V E V.
(V)
log(1V//5)
(V) - L2V) 5o @VVmax
(16)
No
Now define
(V) = =B( g.+ + xTV(s, v(s:g))
Since (( [ (V)) i. (V), by Lemma 3 we have that with probability 1 5, for any
V E holds that
o V2 log 118())/88)
(17)
Also, note that
[L((V) -
-( (V)
a (( + -
-Vo V(s::))
2 B( (r(s:g) + TTV VV:s)) + - ( - v(s:g)+
v(s:g)
<T Vimax (s. IT - VV,
Vinax (s,.))
- (Vs::))11
S212 max (s..a [IlP" a)
By Lemma 5 with probability least 1 5, for all V V,
log([Pl/4
(P1/8)
(2(V) - -L B V
P' (+ss,a) - P(-ls, a)) v22 22
(18)
N
By rescaling and applying a union bound, we can obtain that with probability at least (18) hold simultaneously. The conclusion holds by applying the triangle inequality.
(66)
Finally, show that O4 and U are close.
18

---

Lemma 7 (Closeness of Ü+ and U in stochastic dynamics), Under Assumptions 1o probability least 6.
with
(
|14+ U 12,,12 O
Stochasiic Estat
where U is the output of Algorithm 3 a = S2
log( Mo]([VIPPAA
and
VN
log ( |P /8)
stochattic
V22 max
stot
N
Proof. For convenience, let Ú = Up. Following the same analysis as in the deterministic case, we
have 1 - U+112,15 0 (Ve
stochastic stat
by Lemma
Also,
|1 - U+ 111 - -
((n-P(aa))()::)))) 2) S-² max Braagem - a'(
-B(sna,o (NEEs -7Bx
PP
Sy2 lo/(()10)) max
N
where the last inequality holds by Lemma Therefore,
||4+ Uat 12,, S |0+ Ua+ 112,,+110 1-11,,
Tog (PI/5)
stochastic
+ +VVmaxx
stat
N
stochastic stat
C Proof for Policy Learning
We provide theoretical analysis of policy learning in this section. We first show two key lemmas in Appendix C.I and then provide missing proofs of the main text in Appendix C.2 and Appendix C.3
C.1 Key Lemmas
Lemma (Statistical error of the weighted MLE objective). Under Assumption with probability at least 1 - for any policy π E 11, it holds that
LLLE
MLE (T)ls (Eo en log(1/7)
MLL stat
where ty Olv Estat 2 and e A O CCV
[0 N
Vius aN
log((IT1/6)
Proof. For convenience, we assume that the offline dataset used policy learning is independent of the dataset used in V'-Leaming. This can be easily achieved by splitting the original dataset D uniformly at random into two datasets of equal size. Also. for analysis. define
Ü a; g)+ log (als, VT II.
MLE ())
((s.a.g)
Now condition the high probability event in Lemma which denote by E,. Then by Us.
0+
Lemma 1 we have
<v. By Cauchy-Schwarr inequality, we can obtain that for
2.1
19

---

any policy T
(s g)+ Ü(, asss,,g)) g)
L ( (T) - M.LE ( 5
log (als,
Ua+
Sey log log (1/T).
Also, for any fixed II, since o inequality that with probability at least 8,
[ /.M (TM((TTT]] ( we can obtain by Bernstein's
[i) - [L)
(((.a:g)= log (a)s, log(1/6) ||0+/al|ooog(1// log(1/8)
Varw
0o
N
N
Since as9))/ d. S Cs we have /all2, C and thus /a+la,,,, IVa+/alla,ter S Ca + S (0(O)) Also,
U(s,ag))+ logr(als.g)
Ü(s,a; a
2
Var
stp
log x(als_g)
a
(U(s
2 log2 (1/T)
<O((CA)2 log2(1/)))
Applying a union bound over π E IT, it holds that with probability least 5, for all
J.MLE xx) - f.MEE (x)
119()11/0)
Vmax log(1/T)
00
Ca log(1/T))
log (T))
N
a.
-m log(1/r).
We denote the above event by Ez. When & and & hold simultaneously, we have by the triangle inequality that
MLE (T) i MLE
(T)|5 MLB - 1 MLE (T) (T)|++I MLE -
MIE (T)) (eu + en) log(L/T).
Also,
<6 x 0 36.
The conclusion holds by rescaling 8.
Lemma (Closeness of MLEE objective of क and R). Under Assumption with probability at least
1 1-8 6,
L
MIE MI O
MLE)
Proof. We condition on the high probability event in Lemma Note that
LMM (m)))
MLF
MI.F (mT)
MLF (mT
i
MLF
i MIF.
(
i MLLF(A)
L. MLF F
(2)
(1) S MLE) by Lemma and (2) S by the optimality of empirical MLE objective, which completes the proof.
20

---

C.2
Proof of Lemma
Proof of Lemma
We condition on the high probability event in Lemma Note that
L MLE = ( + 7 Va (s: 9)) log (a)s,
() [log (a)s,
We also define
Iials, g)
MLE (TT) = La (LLB(T)) (s.ag))d [log T. (a g)] E (x.. log Rel
( (8
and note that L is constant shift of LALE For any I1, further define Ta πT ma By Assumption 5 F (a)s.g) E [7.1/7]. Let MMLE (r*) = (s,,,)))-d; (logr>(a)s;g)) which is -tronlyy concave w.r.t. 11-112.dg when (= g) E [r, 1/r]. Since n, is the maximizer of LMLE and thus the maximizer of L R. and the optimality of T; we have
have that Tag is the maximizer of L o. By strong concavity
Rel
(T) i. MLE (FR) L Rel Rel (TT) MILE (at) LALEETT
7 |1== ra 11, S i.MLE
LALE (+)
0
MLE (Estat
where the last inequality holds by Lemma
9 Note that
|| r* I12:a:
E (3,
(r+(als,g)
[((as.g) - 27
2 (s [[ 9) (-1.
(s)g)))>;; [| ()gg) (+s
where the last incquality holds since TV distance is upper bounded by x² distance. Therefore, we can finally obtain that
E (o (1*((1), (T)() SO (V
MLE /72
C.3 Proof of Theorem
Proof of Theorem
7 We condition the high probability event in Lemma 8 By performance
difference lemma Agarwal et al. 2019), we have
J(m)) - (ft -E (a0.)))a [A (s, g)
E (nginat En (11s.g) A ( a;) Ea A as)
V max (sg)) |+ 9)-1)
V Vaaee E (s.g || (+18, #-119.))|TVV)
MLE
SV max
Stul
72
where the last inequality holds by Lemma
D Statistical Rate of the Suboptimality in Different Settings
In this section, we analyze the statistical rate of the suboptimality of the output policy á by Algorithm D in different settings.
21

---

D.1 Deterministic Seftings
Proof of Theorem
By Theorem and Proposition 3.1
J(TT) ( =J(T') - (TT)) + J(Ta) J(
MLE
Sa(C2)² + Viaxx
72
Sa(Ca)² + Vaax /lg(11/T
log( (11)
Viaxx a.
Cstaa 2 + C%
log( log( [I]
N
Since Sata x V2nx
/6) N
we can further obtain that
J(x²)~ - J(A)
Sa((2)² + Vmax v log( ()
Vmax
[og((V]/8)
1/4
log
II |
Vmax o.N
+
+Ca
lo
N
Sa(CZ)² + Vmaa (lo((1/T)
Vmax Ca
log((>)(1T1/0)
x/1/44
V3 Max (Cx)3 log(1// 10g
1/3
72N1/4
Vanus log(1/r) (o
1/3
where a x
(C
D.2 Stochastic Settings
Theorem (Statistical rate of the suboptimality in stochastic settings). Under Assumptions with probability at least 1 1 8, the output policy ā by Algorithm 7 (with the choice of Algorithm for V V-learning in stochastic settings) satisfies
V3 max (Ca)
(Cx)3 log(1177 log( (V 1/3
J( ((#)
N²N1/4
if we choose a x ( log( (PIIi 18)
1/3
and assume No-
Proof. The proof is identical to the proof of Theorem except that we replace esaa with stochastic stat
22


Reviews:
[{"review_id": "iazORGnMuZ", "reviewer": "Reviewer_fB34", "summary": "This paper establishes a rigorous theoretical analysis for offline goal-conditioned reinforcement learning algorithms (GCRL). To achieve that, the authors made a slight modification on top of an existing offline GCRL algorithm (GoFAR), achieve a polynomial sample complexity by regression instead minimax optimization.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-organized and provides a throughout survey of related work.\n2. It seems to achieve an effective and reasonable improvement from the lens of theory.", "weaknesses": "There is no experiment to support the correctness of the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>There is no experiment to support the correctness of the theoretical analysis.\n\nWe provide experiments to support the correctness of our theoretical analysis (especially the choice of $\\alpha$). Please see the “global” response for details.\n"}, {"review_id": "UfKmw5DoTR", "reviewer": "Reviewer_39fV", "summary": "This paper aims at improving the theoretical understanding of offline goal-conditioned RL (GCRL). In particular, this paper modifies an existing offline GCRL algorithm and shows an O^˜ (poly(1/ϵ)) sample complexity under minimal assumptions of single-policy concentrability and realizability. Their algorithm, called VP-learning, consists of two uninterleaved optimization steps and has good empirical performance while retaining computational stability. Moreover, it can also be applied in non-goal-conditioned settings.\n\nThere seems to be a theory-practice gap that this paper addresses. Namely, most provably efficient algorithms seems to require minimax optimization, while in practice that is not effective. Ideally, an algorithm should be practical with good sample complexity guarantees, which is a gap this paper aims to fill.\n\nIn particular this paper provides guarantees for a modified version of an algorithm GoFAR, with modifications in the deterministic and stochastic MDP settings. They call their modified algorithm VP-learning. While other algorithms have been shown to be efficient under single-policy concentrability and realizability assumptions, they require solving minimax optimization problems.\n", "questions": "How do you expect the modified algorithm, VP-learning to compare to GoFAR in terms of empirical performance? How do you expect the modifications will impact things adversely?\n", "limitations": "To my knowledge, the authors do adequately address the limitations of the paper.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "While other algorithms have been shown to be efficient under single-policy concentrability and realizability assumptions, they require solving minimax optimization problems. This algorithm does not. \n\nThe algorithm they develop is built off of an algorithm with good empirical performance.\n", "weaknesses": "While part of the pitch of the paper is that they desire an algorithm that has provable efficiency whilst also having good empirical performance, they do not have empirical results to demonstrate that their modified algorithm performs well.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>How do you expect the modified algorithm, VP-learning to compare to GoFAR in terms of empirical performance? How do you expect the modifications will impact things adversely?\n\nThe modified algorithm, VP-learning outperforms GoFAR in terms of empirical performance, and we provided details in the “global” response.\n"}, {"review_id": "sTtt7EUFt4", "reviewer": "Reviewer_quHd", "summary": "This paper provides a rigorous theoretical analysis to a modified version of existing offline Goal-conditioned RL algorithm, and proves that it has an $\\tilde O (poly(1/\\epsilon))$ sample complexity, where $\\epsilon$ is the desired suboptimality of the learned policy. The algorithm requires minimal assumptions on the dataset and the function class and does not involve minimax optimization.", "questions": "Can you explain more on the raised issue?  ", "limitations": "The authors of the paper have discussed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes a novel contribution by providing a theoretical analysis of an existing offline GCRL algorithm. \n\nThe paper is clearly written and well-organized. The theoretical analysis is well-explained.\n", "weaknesses": "The derivation of this paper is flawed due to a mistake in Proposition 3.2. This mistake leads to the conclusion that strong duality holds, and we can recover the optimal policy by solving the dual problem. However, it can be seen that, at the limit of $\\alpha\\to0$, the dual problem (Equation (6)) solves a value function that evaluates the behavior policy. Therefore, solving the dual problem cannot recover the optimal value from suboptimal data, and strong duality does not hold. As a result, all subsequent derivation is invalid, and the claims are unsupported.\n\nThe mistake in Proposition 3.2 stems from a citation of Proposition 4.2 of [1] which incorrectly establishes strong duality.\n\nOverall, I think the paper would have been a valuable contribution to the field of offline RL. However, the flawed derivation is a serious issue that needs to be addressed.\n\n[1] Ma, Jason Yecheng, et al. \"Offline goal-conditioned reinforcement learning via $f$-advantage regression.\" Advances in Neural Information Processing Systems 35 (2022): 310-323.\n\n\n===Post-rebuttal Update===\n\nPreviously raised concerns have been effectively addressed. Overall, I am optimistic that, with some revisions, this paper could meet the standards for acceptance. I am pleased to raise my score from 3 to 6 and look forward to seeing your further refinement of this paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>Overall, I think the paper would have been a valuable contribution to the field of offline RL. However, the flawed derivation is a serious issue that needs to be addressed.\n\nWe really appreciate the reviewer’s work in identifying the issue that is caused by “a citation of Proposition 4.2 of [1] which incorrectly establishes strong duality”. We carefully checked the derivation of Proposition 4.2 of [1], and found that their result indeed has some issues theoretically. Below we provide a simple fix to this issue with details and show that our theoretical results still hold.\n\nThe issue is caused when we solve \n\n$\\max\\_{d(s,a;g) \\geq 0} \\mathbb{E}\\_{(s,a,g)\\sim d} [r(s;g) + \\gamma \\mathcal{T} V(s,a;g) - V(s;g)]  - D\\_g(d(s,a;g) || \\mu(s,a;g)).$\n\nFor notation convenience, we denote $A_V(s,a;g) = r(s;g) + \\gamma  \\mathcal{T}  V(s,a;g) - V(s;g)$, and denote $w(s,a;g) = d(s,a;g)/\\mu(s,a;g)$. Then the above problem can be rewritten as \n\n $ {\\max}\\_{w \\geq 0}  \\mathbb{E}\\_{(s,a,g) \\sim \\mu}[w(s,a;g) A\\_V(s,a;g) - g(w(s,a;g))].$\n\nNote that we can solve $w(s,a;g)$ separately for each individual $(s,a,g)$ pair.\n\nIf we don't have the constraint that $w \\geq 0$, then equation (22),(23) in [1] is correct, i.e., the maximum of the above object is \n    $\\mathbb{E}\\_{(s,a,g) \\sim \\mu}[g\\_\\*(A\\_V(s,a;g))]$\n and the optimal $w$ satisfies $w\\^\\star\\_V(s,a;g) = g'\\_\\*(A\\_{V}(s,a;g))$. However, we have the constraint that $w \\geq 0$, which makes the above solution incorrect. Under this constraint, one can solve that when $g$ is convex, we have \n       $ d\\_V^\\star(s,a;g) = w\\_V^\\star (s,a;g) \\cdot \\mu(s,a;g) = g'\\_\\*(A\\_V(s,a;g))\\_+ \\cdot \\mu(s,a;g)$\n    where $x\\_+ \\triangleq \\max$ {$x, 0$}, and the maximum of the above object is \n\n   $\\mathbb{E}\\_{(s,a,g)\\sim \\mu}[I$ { $g'\\_\\*(A\\_V(s,a;g)) \\geq 0$ } $\\cdot g\\_\\*(A\\_V(s,a;g)) + I$ { $g'\\_\\*(A\\_V(s,a;g)) < 0$ } $\\cdot \\min_{u \\in \\mathbb{R}} g\\_\\*(u)].$\n\nIf we further define $\\tilde{g}\\_\\*(x) = g\\_\\*(x) - \\min\\_{u \\in \\mathbb{R}} g\\_\\*(u)$ which is a constant shift of $g\\_\\*$, then the above objective can be expressed as \n\n   $ \\mathbb{E}\\_{(s,a,g)\\sim \\mu}[ I$ { $g'\\_\\*(A\\_V(s,a;g)) \\geq 0$ } $ \\cdot \\tilde{g}\\_\\*(A\\_V(s,a;g)) ] + \\min\\_{u \\in \\mathbb{R}} g\\_\\*(u).$\n\nTherefore, the $V$-learning should be corrected as $\\min_V L_\\alpha (V)$ where \n \n$L\\_\\alpha(V) =  \\alpha( (1-\\gamma)\\mathbb{E}\\_{(s,g)\\sim(\\rho,p(g))}[V(s;g)]  + \n   \\mathbb{E}\\_{(s,a,g)\\sim \\mu}[ I$ { $g'\\_\\*(A\\_V(s,a;g)) \\geq 0 $ } $ \\tilde{g}\\_\\*(A\\_V(s,a;g)) ]).$\n\nNote that this is similar to the previous $L_\\alpha(V)$ except that we only consider the $\\tilde{g}\\_\\*$ of which $g'\\_\\* \\geq 0$ in the second term.\n\nUnder our choice of $f(x) = \\frac{1}{2}(x-1)^2$, $g = \\alpha \\cdot f$, we have $g_*(x) = \\frac{(x+\\alpha)^2-\\alpha^2}{2\\alpha}$. Note that in our paper we defined  $U_V(s,a;g) = r(s;g) + \\gamma  \\mathcal{T}  V(s,a;g) - V(s;g) + \\alpha = A_V(s,a;g) + \\alpha$. Therefore, the $V$-learning objective is also equivalent to \n\n  $ L\\_\\alpha(V) =  \\alpha(1-\\gamma)\\mathbb{E}\\_{(s,g)\\sim(\\rho,p(g))}[V(s;g)] + \\frac{1}{2} \\mathbb{E}\\_{(s,a,g)\\sim \\mu}[ (U\\_V(s,a;g)\\_+)^2 ].$\n\nSimilarly, in the policy learning procedure, we need to modify the algorithm to \n\n   $ \\pi^\\*\\_\\alpha = \\arg\\max\\_{\\pi} \\mathbb{E}_{(s,a,g)\\sim \\mu}[(U\\_\\alpha^*(s,a;g)\\_+/\\alpha) \\cdot \\log \\pi(a|s,g)].$\n\nNote that this is also similar to the previous form, except that we ignore the term with a negative $U$ value.\n\nWith the above modification, our algorithm is correct and the whole proof still goes through. Note that for the most part, the proof remains unchanged, and the only place we need to pay attention to is Lemma 1. Since now our policy learning procedure uses $U_+$ as the weight instead of $U$, we only need to control\n$|| \\hat U\\_+ - (U^\\*\\_\\alpha)\\_+ ||\\_{2,\\mu}$.\nThe previous proof uses the property that $\\tilde{L}\\_\\alpha(U\\_V) \\triangleq L\\_\\alpha(V)$ is strongly convex w.r.t. $U\\_V$ and $|| \\cdot ||_{2,\\mu}$. Then we can upper bound $|| \\hat U - U^\\*\\_\\alpha ||\\_{2,\\mu}^2$ using $\\tilde{L}\\_\\alpha(\\hat U) -  \\tilde{L}\\_\\alpha(U\\_\\alpha^*)$.\nAfter modification, $\\tilde{L}\\_\\alpha(U\\_V) \\triangleq L\\_\\alpha(V)$ is no longer strongly convex, but is ``semi''- strongly-convex, i.e., $\\tilde{L}\\_\\alpha(U\\_V) - \\frac{1}{2}\\mathbb{E}\\_{(s,a,g)\\sim \\mu}[ (U\\_V(s,a,g)\\_+)^2]$ is linear (and thus convex). Therefore, if we define $h(U\\_V) = \\tilde{L}\\_\\alpha(U\\_V) - \\frac{1}{2}\\mathbb{E}\\_{(s,a,g)\\sim \\mu}[ (U\\_V(s,a,g)\\_+)^2]$, we have by the definition of convexity that \n    $h(y) \\geq h(x) + \\nabla h(x)^{\\mathsf{T}} (y-x)$\nwhich implies that \n   $ \\tilde{L}\\_\\alpha(y) \\geq \\tilde{L}\\_\\alpha(x) + \\nabla \\tilde{L}\\_\\alpha(x)^{\\mathsf{T}}(y-x) + \\frac{1}{2}|| y\\_+ - x\\_+ ||\\_{2,\\mu}^2.$ \nTherefore, we can use the same method to upper bound $|| \\hat U\\_+ - (U^\\*\\_\\alpha)\\_+ ||\\_{2,\\mu}^2$ using $\\tilde{L}\\_\\alpha(\\hat U) -  \\tilde{L}\\_\\alpha(U\\_\\alpha^\\*)$ and all the other proof remains unchanged.\n\nWe thank the reviewer again for identifying the issue so that we can fix it and make our theoretical results more solid. We are also encouraged that the reviewer thought our paper would be “a valuable contribution to the field of offline RL” if we could address the issue. We are happy to discuss this further if the reviewer still has any unaddressed concerns.\n\n**Short Version** \n\n$V$-learning should be \n\n$L\\_\\alpha(V) =  \\alpha( (1-\\gamma)\\mathbb{E}\\_{(s,g)\\sim(\\rho,p(g))}[V(s;g)]  + \n   \\mathbb{E}\\_{(s,a,g)\\sim \\mu}[ I$ { $g'\\_\\*(A\\_V(s,a;g)) \\geq 0 $ } $ \\tilde{g}\\_\\*(A\\_V(s,a;g)) ]).$\n\nand policy learning should be \n\n $ \\pi^\\*\\_\\alpha = \\arg\\max\\_{\\pi} \\mathbb{E}_{(s,a,g)\\sim \\mu}[(U\\_\\alpha^*(s,a;g)\\_+/\\alpha) \\cdot \\log \\pi(a|s,g)].$\n\n**Reference:**\n\n[1] Ma J Y, Yan J, Jayaraman D, et al. Offline goal-conditioned reinforcement learning via f-advantage regression[J]. Advances in Neural Information Processing Systems, 2022, 35: 310-323.\n"}, {"review_id": "HGZ5Vhyol8", "reviewer": "Reviewer_vRJf", "summary": "The paper proposes the VP-learning algorithm to solve offline goal-conditioned RL in the context of general function approximations. The algorithm is based on a previous empirically successful algorithm proposed by [1], and the author proves the finite sample complexity for VP-learning under mild assumptions. The proposed  algorithm avoids minimax learning by using a duality formulation first identified by [1], which makes the proposed VP-learning algorithm friendly to implementation while also enjoying theoretical guarantees.\n\n**References:**\n\n[1] Ma J Y, Yan J, Jayaraman D, et al. Offline goal-conditioned reinforcement learning via $ f $-advantage regression[J]. Advances in Neural Information Processing Systems, 2022, 35: 310-323.", "questions": "- Regarding Assumption 4 (single policy realizability), what is the $\\alpha$ in the equation $\\pi_{\\alpha}^{\\star}\\in\\Pi$? Since in Theorem 2 and 3 this assumption is imposed before the choice of $\\alpha$, the $\\alpha$ in the assumption seems undetermined. I think this needs clarification since the paper assumes that the policy class $\\Pi$ is finite, which necessitates a specific choice of $\\pi_{\\alpha}^{\\star}$.\n- Regarding Assumption 5 (lower bound of policy), this seems a quite strong assumption which is not needed by previous single task offline RL algorithms with general function approximations, e.g., [2, 3, 4]. The author argues that the parameter $\\tau$ can be very small, but a small $\\tau$ will also increase the upper bound of the suboptimality of VP-learning due to Theorem 2&3. Is this assumption actually  necessary for offline goal-conditioned RL? or is it only required by the specific analysis for VP-learning algorithm?\n\n**References:**\n\n[2] Zhan W, Huang B, Huang A, et al. Offline reinforcement learning with realizability and single-policy concentrability[C]//Conference on Learning Theory. PMLR, 2022: 2730-2775.\n\n[3] Uehara M, Sun W. Pessimistic model-based offline reinforcement learning under partial coverage[J]. arXiv preprint arXiv:2107.06226, 2021.\n\n[4] Xie T, Cheng C A, Jiang N, et al. Bellman-consistent pessimism for offline reinforcement learning[J]. Advances in neural information processing systems, 2021, 34: 6683-6694.", "limitations": "The above questions are potential limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The VP-learning algorithm proposed in the paper enjoys finite sample guarantees under a mild single policy concentrability assumption. Compared with previous works on offline RL (single-task) algorithms with general function approximations, VP-learning does not involve minimax optimization, potentially making the algorithm more easy and stable to implement.", "weaknesses": "- This theoretical paper aims to study the problem of offline goal-conditioned RL. But it seems that the whole theory does not essentially rely on the setting of goal-conditioned RL. The existing theoretical works this paper compares with are also for standard offline RL, which makes the motivation of the paper confusing. It's true that the standard offline RL can be interpreted as a special case of goal conditioned RL, but I hope to see more intuitions and messages on the problem of goal-conditioned RL itself.\n- The key path through which the VP-learning algorithm can avoid solving minimax optimization problems is based on [1], which makes the theoretical contributions and insights of the paper weakened.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>But it seems that the whole theory does not essentially rely on the setting of goal-conditioned RL\n\nWe provide the following reasons (motivations) that our paper uses goal-conditioned settings.\n\n1. The original algorithm GoFAR we analyze is designed for GCRL setting, so we keep their setting. Also, as we compare our VP-learning and GoFAR algorithm empirically (see “global” response for details), the environments are goal-conditioned.  \n2. GCRL is a more general setting that includes single-task RL as a special case, and our algorithm “can also be applied in non-goal-conditioned settings” as Reviewer 39fV mentioned. Since it can be analyzed and applied in both GCRL and single-task settings, we choose the more general one to make our result applicable in a wider scope.\n\n\n>The key path through which the VP-learning algorithm can avoid solving minimax optimization problems is based on [1], which makes the theoretical contributions and insights of the paper weakened.\n\nAs Reviewer fB34 said, our algorithm “achieves an effective and reasonable improvement from the lens of theory”, and our theory further provides insightful guidance on the practical implementation of algorithms (as shown in the “global” response and the attached pdf). \n\nWe disagree that the above step makes our theoretical contribution and insight weakened. Instead, this is one of the important steps that ensure our algorithm has a theoretical guarantee and outperforms [1] empirically. Note that the GoFAR algorithm in [1] lacks a theoretical guarantee and we provide a finite sample guarantee under a careful choice of $\\alpha$. An appropriate value of $\\alpha$ not only ensures that our algorithm has a finite sample guarantee (Theorem 1) but also helps to improve over the previous algorithm GoFAR empirically (see “global” response for details). \n\n\n>What is the $\\alpha$ in the equation $\\pi_\\alpha^\\star \\in \\Pi$? \n\n$\\alpha$ can be chosen as in Theorem 2 or 3. Our Assumption 4 is actually similar to Assumption 2,3 in [2]. We will mention it in our assumption that $\\alpha$ can be chosen as in Theorem 2 or 3. Also, the policy class can have infinite cardinality, and our results still hold as long as the policy class $\\Pi$ has a bounded log-covering number. We assume a finite cardinality only for the convenience of presentation (also similar to [2]).\n\n>Regarding Assumption 5 (lower bound of policy), this seems a quite strong assumption which is not needed by previous single task offline RL algorithms with general function approximations, … Is this assumption actually necessary for offline goal-conditioned RL? or is it only required by the specific analysis for VP-learning algorithm?\n\nFirst, although some previous single tasks offline RL algorithms do not require the lower bound assumption, they require other strong assumptions. For example, [3] requires a completeness-type assumption, where for all policy $\\pi \\in \\Pi$, it requires the $Q$ function of $\\pi$  is realized in a value function class $\\mathcal{F}$, and $\\mathcal{F}$ further needs to satisfy the completeness assumption. [2] does not require a lower bound of policy, but they assume that the behavior policy $\\mu$ is known; note that if this is true for our algorithm, then we can directly calculate the policy using $\\mu$ and the learned $U_V$ after $V$-learning and thus does not even require a policy class. However, this method is not realistic and thus we use a more practical method (i.e., weighted MLE) to calculate the policy. \n\nAlso, we argued that $\\tau$ can be very small and even depends on $\\alpha$. When $\\tau$ depends on $\\alpha$, e.g., $\\tau = \\alpha^c$ for some constant $c > 0$, we can choose a different $\\alpha$ between line 588 and 589 in the proof of the main theorem s.t.  the two terms in the third line between line 588 and 589 equal to each other and still obtain a suboptimality rate polynomial in $n$. Roughly speaking, we require that $\\alpha = \\frac{1}{\\alpha^c}\\cdot \\frac{1}{\\alpha^{1/4}N^{1/8}}$, and thus the suboptimality is $O(\\alpha) = O(1/N^{\\frac{1}{10+8c}})$, which equals to $O(1/N^{1/10})$ when $c = 0$ as in Theorem 2. When $c$ is positive but small, our lower bound assumption on policy class is mild and it only makes the sample complexity slightly worse.\n\nIn practice, we don’t need this lower bound assumption and can directly apply the weighted MLE algorithm in the policy learning procedure. We add this assumption for theoretical analysis. To the best of our knowledge, it remains an open question whether a lower bound assumption on policy class is necessary for a finite sample guarantee if one uses MLE.\n\n**Reference:**\n\n[1] Ma J Y, Yan J, Jayaraman D, et al. Offline goal-conditioned reinforcement learning via f-advantage regression[J]. Advances in Neural Information Processing Systems, 2022, 35: 310-323.\n\n[2] Zhan W, Huang B, Huang A, et al. Offline reinforcement learning with realizability and single-policy concentrability[C]//Conference on Learning Theory. PMLR, 2022: 2730-2775.\n\n[3] Xie T, Cheng C A, Jiang N, et al. Bellman-consistent pessimism for offline reinforcement learning[J]. Advances in neural information processing systems, 2021, 34: 6683-6694.\n"}]

Author rebuttal:
We thank all the reviewers for their helpful and insightful comments. Below we first address common issues.  Since several reviewers mentioned that our paper does not provide empirical results of the modified algorithm, we provide experimental results of our VP-learning algorithm with different choices of $\alpha$ under five environments (FetchReach, FetchPick, FetchPush, FetchSlide, and HandReach) used in [1] (see the two tables in the attached pdf file ). All the implementation details of our VP-learning are the same as the GoFAR algorithm [1], except for the value of $\alpha$. Note that our VP-learning algorithm with $\alpha=1$ is equivalent to the GoFAR algorithm. Table 1 contains the discounted returns and Table 2 contains the final distances of the policies trained after 100 epochs and evaluated over 10 runs. For each environment and each $\alpha$, the result was averaged over 3 random seeds as in the GoFAR paper [1]. The best results of each environment are in bold. 

The empirical results demonstrate the correctness of our theoretical analysis: choosing $\alpha=1$ will result in a large suboptimality of $\pi_\alpha^\star$ and thus the learned policy $\hat \pi$. Instead, we should carefully choose the value of $\alpha$ to ensure a vanishing suboptimality. In practice, we should tune the value of $\alpha$ and typically it should be less than 1. In our experiments, the best $\alpha$ ranges over $0.05-0.5$.

**Reference:**

[1] Ma J Y, Yan J, Jayaraman D, et al. Offline goal-conditioned reinforcement learning via f-advantage regression[J]. Advances in Neural Information Processing Systems, 2022, 35: 310-323.


Meta-review: This paper provides a new theoretical understanding of offline goal-conditioned RL (GCRL). In particular, under the assumptions of single-policy concentrability and realizability, this paper modifies an existing offline GCRL algorithm and shows an $\tilde{O}(Ploy(1/\epsilon))$ sample complexity via VP-learning. I recommend the paper be accepted. The authors should incorporate the reviewers suggestions in the revision. In addition, there are two missing papers that I believe is relevant: [1] initiated the theoretical study for the offline stochastic shortest path problem, albeit for the tabular setting; Beyond  Rashidinejad et al., 2021, [2] considered the offline reinforcement learning with single-policy concentrability and achieved instance-depend characterization. It is of great importance to ask (beyond the worst-case guarantee) whether instance-depend bound can be arrived for offline goal-conditioned learning. The authors should include the discussion for [1],[2] in the camera-ready.

[1] Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality, UAI22
[2] Towards instance-optimal offline reinforcement learning with pessimism, NeurIPS21
Decision: Accept (poster)