Worst-Case Offline Reinforcement Learning with Arbitrary Data Support
Authors: Kohei Miyaguchi
Venue: NeurIPS 2024 poster (2024)
Keywords: offline reinforcement learning
worst-case learning
support free
sample complexity analysis
Primary area: reinforcement_learning

Abstract: We propose a method of offline reinforcement learning (RL) featuring the performance guarantee without any assumptions on the data support. Under such conditions, estimating or optimizing the conventional performance metric is generally infeasible due to the distributional discrepancy between data and target policy distributions. To address this issue, we employ a worst-case policy value as a new metric and constructively show that the sample complexity bound of $O(\epsilon^{−2})$ is attainable without any data-support conditions, where $\epsilon>0$ is the policy suboptimality in the new metric. Moreover, as the new metric generalizes the conventional one, the algorithm can address standard offline RL tasks without modification. In this context, our sample complexity bound can be seen as a strict improvement on the previous bounds under the single-policy concentrability and the single-policy realizability.

Worst-Case Offline Reinforcement Learning with Arbitrary Data Support
Kohei Miyaguchi'
IBM Research Tokyo
Tokyo, Japan
koheimiyaguchi @arp:iccch@mmmm...ooo
Abstract
We propose method of offline reinforcement learning (RL) featuring the per- formance guarantee without any assumptions on the data support. Under such conditions, estimating or optimizing the conventional performance metric is gener- ally infeasible due the distributional discrepancy between data and target policy distributions. To address this issue, we employ worst-case policy value as a new metric and constructively show that the sample complexity bound of O(c-2) is attainable without any data-support conditions, where 0 is the policy subopti- mality in the new metric. Moreover, the new metric generalizes the conventional one, the algorithm can address standard offline RL tasks without modification. In this context, our sample complexity bound can be seen as a strict improvement on the previous bounds under the single-policy concentrability and the single-policy realizability.
Introduction
Offline reinforcement learning (RL) (Levine et al. 2020 Prudencio et al. 2023) is a framework for learning
policies while constrained a fixed batch of data, preventing the learner from acquiring new information about the environment during training.
The primary challenges of offline RL thus originated from the discrepancy between the state- action distribution the batch data ((a)))(a)))) and the visitation distribution the trained policy d= (s))(()s)) Most of the previous studies have avoided directly dealing with this discrepancy by posing the assumption known as concentrability (Munos and Szepesvári] 2008 Antos et al.) 2008 Chen and Jiang 2019 Xie al. 2022). Roughly speaking, the condition asserts that the ratio between these two distributions d" 1B is well-defined and uniformly bounded over the entire state-action space. This, in turn, constrains the trained policy strictly stay inside the state space covered by the data support.
However, concetrability may be impractical in real-world applications for several reasons. First, one often ends up with a poor coverage of the state-action space when exhaustive data collection expensive practically infeasible in the domains of autonomous driving (Fang al., (022). healthcare YYu et al.) 2021) and public policy- of the partial coverage unknown if the considerations making it partial not well-documented disclosed. On the other hand, it is generally difficult to accurately predict if a policy will visit a given not based only on the knowledge of the policy and the batch dataset. As a result, the set of concentrable policies in a hypothesis space may be too small to achieve reasonable performance or
(Abe et al.) (2100). Moreover, the precise shape
'The author is affiliated with LY Corporation the time of publication.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table I: Assumptions and sample complexity bounds of related work. n² and #* denote optimal policies in the conventional and worst-case offline RI., respectively. Th denotes sequence of policies indexed with the sample size n. The realizability of π means that -assocciate model-free parameters (e.g., value functions, visitation weight functions and the policy itself) are realizable. c > is the policy suboptimality given in Problem [.] (or equivalently in Problem 3.1 see Corollary 4.2 for the equivalence). 0 < 8 < 1 denotes the confidence parameter. H denotes the time horizon and roughly comparable to (1 7) Cgap and Sgap denote the minimum and the lower-tail exponent of the action value gaps, respectively. NN denotes the cardinality of the function classes. The improvements made by our result are emphasized. See Appendix A for more details.
Assumptions
Method
Sample complexity bound
Concentrability
Realizability
Zhan et al.
2022
π
6 (1- - 7) *In(N/8) ([n_)))
Chen and Jiang 2022
π
n
Ozdaglar et al.
2023
π
E ? - 7) -C /o)
Uehara et al.
2023)
T
22-4/ (1 7) -6-1-61-0000 36-A///ee
Ours (Corollary 6.3
6 (1 - -) (In(NN/)
even empty D Therefore, for applying offline RL in such domains, we need a method that works well without concentrability or any coverage-related conditions.
To tackle with this issue, we study offline RL with arbitrary data support. We present two major results in this paper.
i) We develop worst-case offline RL (Problem 4. poor state-action coverage, which can be seen as a natural generalization of conventional offline RL (Corollary 4.2).
a new offline RL framework for handling
ii) We develop worst-case minimax RL (WMRL, Section 6.3 a model-free algorithm address- ing worst-case offline RL (Corollary 6.3). The resulting sample complexity bound improves the previous state of the art in terms of both the weakness of the assumptions and the strength of the bound (Table D.
The rest of the paper is organized as follows. In Section 2 we review the previous work in the literature of offline RL, centered around theoretical studies on the role of concentrability. In Section 3 we introduce some preliminaries around Markov decision process (MDP), offline RL and concentrability. Then, in Section 4 with the observation that offline RL is ill-posed without concentrability, we introduce worst-case offline RL as a natural generalization and discuss some of its properties useful in our subsequent analysis. In Section 5 we establish the connection between worst-case offline RL and the Lagrangians derived from the saddle-point formulation of offline RL. In Section 6 exploiting the connection established earlier, we construct a method for solving worst-case offline RL with polynomial sample complexity. Finally, we discuss the limitation and the future work in Section 7
2 Related Work
The notion of concentrability is introduced by Munos (2003); Munos and Szepesvári (2008); AAtos ct al. (2008) to analyze the value/policy iteration algorithms not necessarily in the context of offline RL. Recently, it has been increasingly gaining traction as one of the key characteristics of the difficulty of offline RL (Chen and Jiang 2019) due to the distribution mismatch. In its original definition, concentrability requires the norm of the density ratio ||d π x/11,l1 to be bounded uniformly for all the policies म. Liu et al. (2020) showed that this uniform boundedness can be relaxed the single-policy boundedness with the principle of pessimism in the face of uncertainty (PFU). Considering the case where the single-policy concentrability is even slightly violated, Xie et al. (021) further analyzed the
"There are two typical examples for the empty case: i) when the time horizon of the policy evaluation (even ever so slightly) longer than the episode length of the collected data in time- iomm-inhomogeeeuu environments. and ii) when there are undocumented restrictions on the actions taken by the behavior policy, but the trained policy is modeled with distributions with full action supports such as Gaussian distributions.

---

performance degradation caused by the lack of concentrability. Finally, we completely remove the concentrability assumption by incorporating it into new performance metric.
The removal of concentrability is useful not only for widening the applicability of offline RL., but also strengthening the sample complexity bound by streamlining the analysis. Previously, /Zhan iet al. (2022) established polynomial sample complexity bounds under the weakest known model-free assumptions, yet being unable achieving the statistically reasonable rate O(E-2), Also, Chen and Jiang )2022): Ozdagla ar et al. (2033; ; Uchara et al. (202)) gave improved rates additionally assuming that the minimum action value gap is bounded away from zero. On the other hand, under set of assumptions as weak as Zhan et al. (2022), our sample complexity bound achieves the rate of O (c)=)).
See Appendix for more detailed discussions.
Algorithmically, the PFU principle is often materialized as the pessimistic or behavioral regular- ization (Kumar al. 2020 Fujimoto and Gu 2021] Yu et al. 2020). Previous analyses often sensitive to the hyperparameters controlling the degree of such regularization, such as the truncation threshold in Liu al. (2020), the Bellman consistency threshold in Xie et al. (0021): Chen and Jiang (202)) and the regularization weight in Zhan et al. x [eeaaa et al. (023)) On the other hand, our method has no hyperparameter other than the choice of the function approximators. One may see the root cause of this difference in that the PFU principle is built into our single new performance metric, whereas the previous studies adopt it as an additional objective, resulting in bi-objective optimizations.
3 Preliminaries
We denote the set of nonnegative real numbers by R4, = 00 x)) and the uniform norm a function y over its domain by ||g = sup supxxeom(1) [=(=)]. We also denote by A(Y) the set of (generalized) probability density functions on X' relative suitable base measure such as the counting measure and the Lebesgue measure.
Markov decision process (MDP) and RL. Me (S. be an MDP consisting of the
state space S, the action space A. the reward function R S x A - A((0, 1)) and the transition probability T A (SS). We assume both S and A are finite sets for simplicity. The goal of RL in general is to optimizing policy π : S + A(A) in terms of the policy value,
J(x) = J(T(M) = (1 E
T 120
with discount factor E (0, 1). Here, the expectation 1ET is taken with respect to the Markov chain generated with a T--[s),, Fr R(se, at) and st+1 (((s,aa), 0, starting from known initial-state distribution 80 (s)).
Offline constraint. In maximizing (TT) the offline constraint prohibits to access the environ- ment M except through the offfine dataset D = [(s) a,, Tı, >/> We assume the dataset is sampled from a fixed distribution Vaai E ASS x A x [0, 1] S)" such that
Pdnta (D) = II ((s)) B(a. M(riss,, a.) T(((1ss,)))
where μ E (SS) and 3 S A(A) are the behavior state distribution and the behavior policy, respectively. Typically, Pana (D) represents the distribution of the past observational data. The problem of offline RL now formally given as follows.
M
Problem 3.1 (Offline RL). Given the offline dataset DD and a small number e > 0, find a policy n achieving J J(x)= I 6, where J = max J(T).
Value, visitation and weight functions. Let a) = R(s.a [y] be the expected reward func- tion and yd (s) = Σ. r(s, (als) be its marginalization with respect to policy и. Let T, T and
Examples of the generalized probability density functions include the Dirac's delta function.

---

arrive at T.e be the raw transition operator, the policy transition operator and its adjoint given by T
E. v(s') v (s'"s a). T v(s) = E. Tu(s, a) (((ss) and T." Ex. d(s (T'')((a')) (T(ssssss respectively. Then, the state value function e" + R. the action value function q" 8 A and the state visitation distribution d= E (S) are given by
v" (1 11- -1-
=
o' =
YT.) ''oo Po
as well the state weight function w supp(u) + R and the action weight function f supp(u3) + I by
(s)
w (8) = mss)
(8)8)) = w" w") (5)
where supp(g) = far E dom(g) (xxx + 0} denotes the support of function y and p² (s,a) miale) is the density ratio π to 3. We also define the optimal value functions by v*(s) B[als)
max, vn (s) and ()) { :S:S- + (AA) 0" = }* which by definition all attain J See Table for the summary of the notation introduced above.
max; q" (8, a) as well as the set of the optimal policies IT* =
Concentrability A policy æ is said to be concentrable (or satisfying concentrability) if its state- action visitation is contained in the data support, supp(d"x)) C supp(ug). We denote the set of all the concentrable policies by Icc = far S - A(A) supp(d"<)) C supp(u33))
4 Worst-Case Offline Reinforcement Learning
In offline RL (Problem 3.1 the information on M is restricted by the data support supp(u3)) In such situations, one cannot know about the transition probability T(s, a) and the reward probability R(s, a) for (s, a) & supp(u²). Consequently, the accurate estimation of ((r) ) is infeasible (even with n = oo) for unconcentrable policies, and thus previous analyses on Problem oftee require that there exists at least one concentrable optimal policy, i.e., Ilcc O argmax, J(x) 7 0.
To remove such dependency concentrability, we introduce performance metric alternative to (TT). Let 1 (M' -P pánta } be the set of the environments indistinguishable from the true environment M with respect to the resulting data distribution Pa Noting that 1 is the ieformation-theorretee limit of the uncertainty on .M under the offline constraint, we follow the pessimism- bessimism-in--hheeeeee of principle and consider the worst case within 1l,
J(x) = inf [TT(MM),
M'ES
which refer worst-case policy value. Replacing J(T) with J(T) in Problem 3.1 the following problem.
Problem 4.1 (Worst-case offline RL). Given the offtine dataset D and a small mumber e > 0, find a policy π. achieving j - J(T] S e, where J == max J(x).
next. introduce the notion of truncated environment, which is similar to, yet different from those previously considered Liu et al. (2020) Yin and Wang (202T) as is based on the true and unknown data support rather than the empirical one. The truncation useful for characterizing the worst-case policy value ((T).
To facilitate the subsequent analysis Problem 4.1
Definition 4.1 (Truncated environment). The truncation of . with respect to i and B is given by M (8, A, where S S U {1} with 1 being an absorbing state with reward zero and
R(((s,,) == Xn.s(8, a) R(r|s, a) + (1 - Xn, a)) 5o(r), ((d1s, = (u,e(s, T(8 a) + (1 Xn.s (8, a)) 81 (s"),
(2)
(3)
for E S and a E A, where (s, a) = {p(s)) > (3((s()))) 0} is the indicator function of the support of ((s) B(ass) and dn E A(X) the Dirac's 's delta function located at x E X.
Theorem 4.1. We have J(T) ( for all S A(A).

---

Proof (sketch). It suffices to show ((T[M) I J(T) S J(aMM,, where the first inequalilty follows from J(r MM) I J[r[M') for all M' E Il and the second inequality follows from M E il. See Appendix D.I for the complete proof.
In other words, worst-case offline RL is nothing but offline RL with the truncated environment M. Thus, in principle, one can exploit conventional offline RL methods to solve Problem 4.1 We hereafter refer to the truncated counterparts (those defined by replacing M with M) of v", v", - q- II", d", w" and f as 8", 0", q", . II,, d=, w" and f", respectively. Likewise, let f, F", T, TT "T.
7 and 7." be the truncated counterparts of r, r",
and T,",, respectively.
Let us remark several key implications of Theorem 4.1 First, since the unknown parameters R and T of the truncated environment M are only nontrivial on the data support, it is intuitively obvious that (=) can be accurately estimated even without the concetrability, given sufficiently large n. Thus, reasonable to expect that Problem 4.1 does not require any concetrabilities to be well-posed, unlike Problem 3.1 Second, the constructive existence of M makes the relationship between J(T) and (Tx) clearer, stated in the following corollary.
Corollary 4.1. We have (TT) = (T) i E 1lc and J(x) S (T) otherwise.
Proof. See Appendix D.2
According to Corollary 4.1 the pessimism introduced by the truncation is mild in the sense that it conserves the values of concentrable policies. Finally, also clarifies the relationship between the suboptimality metries of the conventional and the worst-case problems.
Corollary 4.2. For all S + (AA), we have
J - -
Tlc argmax, J(z) + 0. Moreover, the equality is attained if in addition æ Ile.
Proof. Trivial from Corollary 4.1
In other words, solutions of the worst-case problem are also valid as solutions of the conventional problem under the standard assumption, while the two solution concepts are identical if only concen- trable policies are concerned. In this sense, worst-case offline RL is a natural generalization of the conventional offline RL for handling arbitrary data distributions.
Finally, we conclude this section by showing a useful property of the worst-case optimal policies. Let Lig == { S (AA) sμрр(μт)) supp(u3)) be the set of the on-support policies, i.c., the policies with the support covered by the behavior policy. The following lemma allows us to limit the scope of policy optimization to IIg without sacrificing the optimality in terms of M. The proof is relegated to Appendix D.3
Lemma 4.1. There is at least one worst-case optimal policy that is on-support, iee. It' O # 0.
5 Lagrangians for Worst-Case Offline Reinforcement Learning
In this section, we set up theoretical foundation of worst-case offline RL. Specifically, in Section 5_1 we show a connection between J(T) and the Lagrangian of RL (Puterman, 2014). However, since the Lagrangian in its original form is unstable the function approximation error (Section 5.2 further introduce a regularized variant of (Section 5.3
5.1 Unregularized Lagrangian
Consider the following functional of v + R4 and f supp(u3) R+,
L(u f) (1 - Ep [e[s]] + Ep, (f() 5TD 8TD
(5)
5

---

where Ep, and E,.0 are the expectation operators with respect to ~ po(s) and (s, a) ~ ((s)) respectively, and OTTD; RS + ESSA is the time-difference error operator given by 5TD v(s a) = r(s, a) + (elo)))777(sss/) v()).
We refer to L(v, f) as the (unregularized) Lagrangian since it has been known as the Lagrangian of the linear-progren paaarrrooggmnnnggggggg based formulations of RL (Puterman 2014 Chen and Wang/ 2016 Nachum et al. 2019 Zhang et al. 2021] Zhan et al., 2022). The following theorem reveals that, perhaps surprisingly, is also connected with worst-case offline RL.
Theorem 5.1. For all 11g n fr,", f"" is saddle point of L(v, f) in R$ x IR$*..
Proof (sketch). The key of the proof is the following identity of Lagrangian.
Lemma 5.1. For all π E II nī", we have
[) = j - [ (I (-- (+) + DE(0) - Df(
(6)
where ( - dx (s) u(s) and DJ( :pp (8) (8) (s,
Now, observe that the third term (v) and the fourth term (f in Eq. 66) are nonnegative since all of v, f, dd and 8" - /" nonnegative. Therefore, Lemma 5.1 implies that Lagrangian is bounded from below with L(v, 2 J taking =f", while bounded from above with L(u, f) < J taking v = ~. Combining these two inequalities, a class the saddle points of Lagrangian is identified as desired. The full proof is found in Appendix F.2
Note that the previous studies on the LP-based formulation of RL typically consider the saddle points in a different domain, R$ x RSSxA, where the domain of the primal variable unconstrained, unlike our setting with the constraint with the worst-case environment M.
0. This constraint is the key to establish the connection
Theorem 5.1 superficially suggests that finding the saddle points of L(v, f) a reasonable way of finding the optimal policies with respect to M.. However, in the next section, we show that unstable and easily breaks down by the function approximation error.
5.2 Instability of Unregularized Lagrangian
When the state space S is large, it is practically infeasible to find saddle point of L(u, naïvely searching over the whole space R x R Therefore, one may introduce compact function classes V Ş and F C RASA and limit the scope of the search to these classes. Since we do not know the saddle points (which motivates to find one), such function classes likely incur the function approximation error. Thus, it is likely that the saddle points (ū*, f() may sit near the search space V x F, but not exactly included in the space, (0", V
In this context, we show even tiny function approximation error can completely disrupt the connection established in Theorem 5.1 Consider the function classes V. = {u E R v 2 6* }} and J. = {f E _ 3 E 11g n II s.t. f f E) with a small constant e > Then, even though the function approximation error is small (c for both V and F in terms of the -nrm), the saddle point is collapsed to zero under the approximations with V. and F.. The proof relegated to Appendix B.3
Corollary 5.1. Suppose V. and F. are nonempty. Then, the saddle points of L(U, f) in V. x SxA must satisfy f = 0. Moreover, the saddle points of L(v, f) in TR. x F. must satisfy v = O.
5.3 Regularized Lagrangian
Corollary 5.1 shows that the saddle points of Lagrangian cannot be used as a reliable way to find the optimal policies with the function approximation. As a workaround, we introduce a regularized Lagrangian,
K(v, f) = (1 - B, [u(s]] + Ev, [f(s, 8 8T v(s) + (1-7)² 1 2.p
(7)
2

---

((s)) (s))) denotes the Ln(m)-norm of the functions where Ji === + +T= a and a
over S. Then, it is shown that the regularized Lagrangian is also connected with worst-case offline RL through its saddle points. To see this, let us define the regularized counterparts of d=, w" and f" with d' = (1 -) -- 1ith = d= /t. I' == i= obtained by substituting the initial state distribution Po with P = ++ - 7)00 j..
Theorem 5.2. For all a E eIgnn (8", fr) is saddle point of K K(v, f) in R x RSSA Moreover, the primal solution ü* is unique on (u))(p).
Proof (sketch). Similarly as the proof of Theorem 5.1 the key is the following identity.
Lemma 5.2. There exist U E IR such that, for all π E H nit,
K(v, - pp (5 {T, -1-77) (5saa - Di(S,,
(8)
where DR(U) = - = Eskpupp(u) d' (s)
+ 11-2)² ||0 8n 1 2.
The first claim of Theorem 5.2 then follows from the fact D (v) is nonnegative, and the second claim follows from the strong convexity of (v, with respect to supp(a). The full proof is in Appendix E,5
Comparing Theorems 5.1 and 5.2 it turns out that the regularization does not alter the primal part of the saddle points 8". Moreover, since (1v f) is strongly convex terms of v, the regularized solution is more stable against the function approximation error opposed to the unregularized solution. To see this, denote the regularized primal solution under the function approximation by
T
E argmin max K (v, f),
"EV
FEF
where V C R and J C S are compact function classes. Also denote the individual function approximation errors of V and F by
= min ||0 - 8n 11, oF
min JeF,eEll,
{Bullf f 11,, + 2(1 - 7) - - (10)
NEV
where By = max (1 + BB, By} and By == maxvev ||o| are scale factors Then, the following lemma shows the stability of the approximate solution oz in terms of the aggregated function approximation error
Eapp, (V,F)= = 22 B5) + 14/5 +AV== =0
(VBBEV++E 1-7
1-7
where By = max [Ifll is the scale factor of F. The proof is relegated to Appendix E.6
Lemma 5.3 (Stability of the regularized primal solution). We have ||
6* 1|2,p S Eapp. (V,
Note that the approximation error of trivially bounded by a simpler error term
CF S By
min xEILxElI;Ni
|lf f
ie., the L' error with respect to the function j'n of the optimal on-support policy E II O fr... Our definition of the enror is weaker than that, measuring the error with respect to that of the possibly suboptimal on-support policy π E IIg in exchange for the additional suboptimality cost 2(1 - 7) || -i" ||, This is beneficial if the optimal policies are difficult to approximate, like deterministic policies in a continuous action space, yet some near-optimal policies such as the soft-optimal policies 77 (als) exp(-nĀ" (s, } are easy approximate.
We also note that the idea of stabilizing the saddle saddle-point point-based policy optimization via a strongly convex regularizer is not new (Nachum et al. 2019 Lee et al. [202T] Zhan et al., 2022] Uehara et al.) 2023). The major difference here (other than the truncation) is that we regularize the value function (like Uehara et al. (2023)) but extract the information of the optimal policy from ʃ (like Nachum al. 2019);] Lee et al. (202)) T): Zhan et al. (2022), which, combined with our worst-case framework, results in striking improvement in the sample complexity.
7

---

6 Corst-Case Minimax Reinforcement Learning
Now, present method to solve worst-case offline RL with the saddle points of (u,, f). We first introduce a method of extracting policy from the dual variable f (Section 6.1). then show the suboptimality bound of the extracted policy (Section 6.2), which is main result, and finally show the sample complexity bound taking into account the finite sample approximation (Section 6.3
6.1 Policy Extraction
Motivated by Theorem 5.2, we propose method of extracting the worst-case optimal policy x² from the saddle point of K f Specifically, we consider minimizing the loss function given by
D=
T = max {Ey,, [S(s a) E(x, a)) - Epp (w((s) E(s, a))) geE
(11)
where w : SS - is an auxiliary weight function, w=(s) == max {1 - 7, [8)} } is its lower clipping and =\t C RSSA is class of discriminator functions. Note that D=([; w. πT) is the integral probability metric (IPM) (Sriperumbudur et al. 2009) between [(x, a) ju(s) [{a[s) and w(s) (u() r[als) with respect to the discriminators E. With sufficiently rich E. this implies Dz(f: w. TT) attains its minimum value (i.c., zero) only if π Tf thereby informally justifies the minimization of Eq. as way of policy extraction.
This approach introduces additional (functional) variables to be optimized, w : S + R and π S (AA). To simplify the notation, consider parameter space O and suppose f. w and share the same parameter space θ, i.e., there exists a mapping e Đ 8 + (fa, We. To). and redefine the dual We define the associated function approximation error with space with J F(O) (Jo 10 { We
ce min { xEllg
(Bv + 2(1 7) 110" - 0t 11,)
(12)
where By. = m Bv, Be, 15 30 Bz = maxçe= 11 and
|1:00 jm|
(T) = min 8E8
1,11 + I|wo - wn 11,, + By 1I n
Tllry...
(13)
denotes the r-specific function approximation error of @. Here, Bw = maxaçe || loc is the boundedness of (s) and .I is the mean total variation (TV) distance with respect to μ. given by ||x - x' I'Il = E, E. [T(as) n (alss)
Finally, conclude this section by introducing key quantities of the policy extraction for the subsequent analysis. Let Bμ = maxsee ||Te/Tolloo denote the size of the policy class with respect to some fixed base policy To. Also let minçe= ( be the function approximation eтror of E, where (s,, a) = q" (s, a) - 5" (s) is the optimal advantage function.
6.2 The Suboptimality Bound
Unifying the saddle-point problem and the policy extraction problem, we arrive at the aggregated loss function
(()) = Lsr + (x))..
(14)
where (0) == mingev K(v, fe) is the loss of fa as a dual solution (cf. Eq. and (x =
Dz(fe; Wa, TT)) is the loss of the policy extraction from fo to To (cf. Eq. 11 Let us denote the corresponding estimation error by
Caal 0 L()) min L()).
(15)
6ce
We also define the aggregated function approximation error with Eapp. (V, 0, =) = (2 3B²) Eapp. (V,, + 3ee + (Br (1-
(16)
The following theorem establishes an upper bound on the policy suboptimality in terms of (o) and Eapp.1( E E,)
The lower clipping w(s) 2 1 y plays crucial role here exclude the trivial minima fs.
for every E S.
There is no loss of generality due to the coupling introduced by the parameter sharing, since one can take it product space è θ5 Ow On.
8

---

Theorem 6.1. For all 0 E @ we have
|1000 loo {fe + Eapp,1 J(To)
(V, 0,E)).
(17)
1 1-7
Proof (sketch). the heart of the proof is the following inequalities:
T(TO)= - (Ja) + Cx( + B'ez
(0 + Ep (V,
1-7
1 1-7
where T( = Ey (x) q" (s, a)] denotes the average action value gap with policy wo and B' == By + (1 )B Here, the lower clipping of w (Eq. (11) and the stability of the primal
solution (Lemma 5..3) are instrumental in deriving the first and the second inequality, respectively.
Then, the proof is completed by bounding J (TTA) in terms T(me) invoking the performance difference lemma in the worst-case environment. See Appendix F. for the full proof.
Theorem suggests that one can minimize the policy suboptimality up the function approximation error on two conditions, i.e., the weight factor |1 is appropriately bounded and the loss function [()) minimized. the following, we first discuss how to satisfy the first condition.
trivial way of bounding || || is uniformly bounding with respect all I E O. Define Coo == maxége " ol which we refer to as the uniform truncated concentrability (UTC) coefficient. Since ||a ol I Coo, get the following simple suboptimality bound.
Corollary 6.1. For all E O, we have
Coo j j(=o) S 1-7 (Cea(0) + Capp. (V, (,))
(18)
Note that Coo is always finite because of the compactness of the whole policy space A(A)S and the continuity and well-definedness of + || Thus, Eq. (18) is non-vacuous for arbitrary data distributions opposed the conventional concentrability- results. Moreover, the conventional bounds are non-vacuous, Coo recovers the conventional concentrability coefficient as 20th u.x
Eq. 18 can be further refined using the localized variants of the uniform coefficient Öx. The results due to space limitation.
are presented as Corollaries and F3 in Appendix
6.3 Sample Complexity Analysis
Now that given Corollary 6.1 (and Corollaries F22 and F.3 as well) bounds the weight factor || Il
with some milder variants of the concentrabilityy coefiiient, the remaining task, minimizing L(0), is handled within the framework of the statistical learning, leading to a sample complexity bound. Let
1 Σ L. E)),,))
(()) = max max-
(19)
EEE n
=ED
be the empirical loss function where
(0;00 (11 us) fo(s fr + yu(5) u(s)} + (1 11-773 7)2 7x
2
fo((ss))(ss. (s) [E(s,
(20)
is the one-sample loss function, = (s, a, s') E S x A [0. 1] S denotes transition record.
Note that Eq. 20) is an unbiased estimator of the objective function L(0) 6 Therefore, is expected
that the oracle loss L(0) can be approximated with the empirical loss ((0) and hence the oracle
estimation error (0) can be approximated with the empirical estimation error
tea = Ž(() min (()).
(21)
#ee
Formalizing such an intuition, the following corollary shows the empirical counterpart of Corollary 6. See Appendix F for the proof.
'Note that the expectation with respect to my can be computed exactly since the action space is finite. For the continuous case, one can replace the expectation with the Monte-Caun Carlo approximation without corrupting the unbiasedness.

---

Corollary 6.2. Les (,= one-sample loss functions and (H.) be its Rademacher complexity (Definition I 0 E à and 8 E (0, 1), with probability - 6, we have
O V E be the class of the
Then, for all
Coo
(cs + (0) Eapp, 11 + + Ban
In (2/))
J J(To) _ 1 7-7
where Ball (1-7) + ByBy + (1- 7) (By By) Bg is the aggregated scale factor.
The corollary above implies that minimizing Eq. (9).. which is possible with the minimax optimizers such as the one developed by [Thekumparampil al. (2019), gives near-optimal policy in terms of the worst-case environment M, up to the error proportional the sum of the optimization error Rea (0), the approximation emror Expp, E (V, O, and the statistical error O (H) n 1/2). We refer to this method as worst-case minimax reinforcement learning (WMRL).
The next corollary gives the sample complexity of WMRL in the simplified case where the function approximators V, θ and are all finite sets.
Corollary 6.3. Suppose V. F and E are all finite sets and (0) = Eapp.1I (V. 0, Take any c <> 0 and 0 < 5 < 1. Then, we have J - [[To) I c with probability 5
Bar 02 21 7)2
.V.
n n=
In
(22)
8
where N = [V] denote the product of the cardinalities of the function approximators.
Proof. It follows from Corollary 6.2 with Massart's lemma (Lemma B.2
A few remarks follow. First, we can replace the UTC coefficient Coc with the localized vari- ants (Definitions F.I and F22 to obtain tighter bounds, by making the same argument starting from and F3 instead of Corollary 6. respectively. Second, there are implicit dependencies and B= 2 | due to the realizability 8" E V and &" E E that follows from
Corollaries F.2
00 Ep (2, 0, 0. Hence, Eq. (22) has implicit y-dependency through the scale factor Ban-
By
which brings extra @(11 y) factor in the worst case. Table I adopts this form for the fairness of comparison.
7 Conclusion
To develop offline RL method for challenging data distributions, we have introduced and studied generalization of the conventional framework called worst-case offtine RL. As result, we have shown is possible to learn worst-case optimal policy without any data-support conditions. Moreover, the presented sample complexity bound strictly improves the previous state of the art under the single-policy realizability and the single-policy concentrability, suggesting the utility of the proposed method even with non-challenging data distributions.
We anticipate the presented results are readily extendable to continuous state-action spaces, except that the truncated concentrability coefficients are not unconditionally finite anymore. The results in Appendix F.3 are particularly useful in this context, yet the complete picture on the conditions of their boundedness largely remains to be studied in future work.
Acknowledgments and Disclosure of Funding
The author is grateful to LY Corporation for providing travel funding.
References
Abe, N., Melville, P., Pendus, C., Reddy, C. K., Jensen, L., Thomas, V. P., Bennett, J., Anderson,
G. F., Cooley, B. R., Kowalczyk, M., Domick, M., and Gardinier, T. (2010). Optimizing debt
10

---

collections using constrained reinforcement learning. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Diseovery and Data Mining, KDD '10, page 75-84, New York, NY, USA. Association for Computing Machinery.
Antos, A., Szepesvári, C., and Munos, R. (2008). Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71:89-129.
Chen. J. and Jiang, N. (2019). information-thcoredr considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR.
Chen, J. and Jiang. N. (2022). Offline reinforcement learning under value and density-ratis ratio realizabil- ity: the power of gaps. In Uncertainty in Artificial Intelligence, pages 378-388. PMLR.
Chen, Y. and Wang, M. (2016). Stochastic primal-dual methods and sample complexity of reinforce- ment learning. arXiv preprint 162.0255
Fang, X., Zhang, Q., Gao, Y., and Zhao, D. (2022). Offline reinforcement learning for autonomous driving with real world driving data. In 2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC), pages 3417-3422.
Fujimoto. S. and Gu. S. S. (2021). A minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34:20132-20145.
Jiang, N. and Huang, J. (2020). Minimax value interval for off-policy evaluation and policy opti- mization. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA. Curran Associates Inc.
Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020). Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33:1179-1191.
Lee, J., Jeon, W., Lee, B., Pineau, J., and Kim, K.-E. (2021). Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference Machine Learning, pages 6120-6130. PMLR.
Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005. 006633.
Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E. (2020). Provably good batch off-policy reinforcement learning without great exploration. Advances in neural information processing systems, 33:1264-1217
Munos, R. (2003). Error bounds for approximate policy iteration. Proceedings of the Twentieth International Conference International Conference Machine Learning. ICML'03, page 560-567. AAAI Press.
Munos, R. and Szepesvári, C. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5).
Nachum, O., Dai, B., Kostrikov, I., Chow, Y., Li, L., and Schuurmans, D. (2019). Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074,
Ozdaglar, A. E., Pattathil, S., Zhang, J., and Zhang, K. (2023). Revisiting the linear- Amnea-programminn framework for offline RL with general function approximation. In International Conference on PMLR.
Machine Learning, pages
Prudencio. R. F., Maximo, M. R., and Colombini, E. L. (2023). A survey on offline reinforcement learning: Taxonomy, review, and open problems. IEEE Transactions on Neural Networks and Learning Systems.
Puterman, M. I. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
11

---

Rashidinejad, P., Zhu, H., Yang. K. Russell, S., and Jiao, J. (2023). Optimal conservative offline RL with general function approximation via augmented lagrangian. In The Eleventh International Conference on Learning Representations.
Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
Sriperumbudur, B. K., Fukumizu, K., Gretton, A., Schölkopf, B., and Lanckriet, G. R. (2009).
On integral probability metrics, metrics.'phi-eeeeee phi-divergences and binary classification. arXiv preprint
arXiv:0901.2698.
Thekumparampil, K. K., Jain, P., Netrapalli, P., and Oh, S. (2019). Efficient algorithms for smooth minimax optimization. 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.
Uchara, M., Kallus, N., Lee, J. D., and Sun, W. (2023). Offline minimax soft-q-learning under realizability and partial coverage. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S., editors, Advances in Neural Information Processing Systems, volume 36, pages 12797-12809. Curran Associates, Inc.
Uchara, M. and Sun, W. (2022). Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference Learning Representations.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems.
Xie, T., Foster, D. J., Bai, Y., Jiang, N., and Kakade, S. M. (2022). The role of coverage in online reinforcement learning. arXiv preprint arXiv:22 10.04157.
Yin, M. and Wang. Y.-X. (2021). Towards instance-optimal offline reinforcement learning with pessimism. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. editors, Advances in Neural Information Processing Systems, volume 34, pages 4065 Curran Associates, Inc.
Yu. C., Liu, J., Nemati, S., and Yin, G. (2021). Reinforcement learning in healthcare: A survey, ACM Comput. Sure, 55(1).
Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J. Y., Levine, S., Finn, C., and Ma, (2020). MOPO: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 33:14129-14144 14142.
Zanette, A. (2023). When is realizability sufficient for off-policy reinforcement learning? In International Conference Machine Learning, pages 40637-40668. PMLR.
Zhan, W., Huang, B., Huang. A., Jiang, N., and Lee, J. (2022). Offlinn reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 2730-2775. PMLR.
Zhang. J., Hong, M., Wang, M., and Zhang, S. (2021). Generalization bounds for stochastic saddle point problems. In International Conference Artificial Intelligence and Statistics, pages -76. PMLR.
A Additional Discussion on Table 1
In T. we compare our result with the previous results on the sample complexity of the conven-
tional offline RL under the weakest known assumptions. The weakest known means that it relies only
on the assumptions of the single-policy realizability and the single-policy concentrability. Specifi-
cally, they do not assume the Bellman completeness (Munos and Szepesvári] 2008 Xie et al. 2021
Chen and Jiang] 2022) or its variants (Zanette| (0033] RRahiiiinejad et al. (023). the model-basee
realizability (Uchara and Sun 2022) or the all-policy realizability (Jiang and Huang 2020), which
12

---

Meaning
Symbol
Type
Definition
Expectation w.r.t. action
p
ISSA + +RS
PT = E.
Extension of action
Pr
RS + RAAA
PT 0) = d(s)
Backward transition
T
RS - SRSAA
Tu(s,a) a) = =.., v(s') ( as)
with policy
T
IR - TRS
PTT
Forward transition
T.
RSXA_ + IS
To((s) = Ean T(s s a) c(s,a)
-with policy
T.
RS + R
T.P.
Marginal reward func.
r"
S + R S + R 8 + R 8 x A R x A R 24(A)
PTr
State value func.
6x
(1 ---TT"--
Optimal
20 (5)) = max, 0 (s)
Action value func.
9-
r "+ 7TT
Optimal
9"
('ss, a) = mmax, (s,
Optimal policies
II
[ + A(A)) 10= 0²!
State visitation dist.
d=
S + R
- (1- - ) Pp
State weight func.
w
supp (4) +
d' p
Policy ratio
p=
supp(ug) - R
/ 3
Action weight func.
supp(u3) + R
" p
Policy value
((T)
(1 - By (s)]
Optimal- -
J R
max, J (T))
Table 2: Basic Notation
strictly stronger than the single-policy realizability and deemed to be rather stringent (Chen and Jiang 2019). Below, we discuss each of the methods listed in the table.
Leveraging the Lagrangian- -aaee formulation of RL, Zhan et al. (022) showed the polynomial sample complexity only with the single-policy realizability and the single-policy concentrability for the first time. However, the order of the sample complexity bound O is significantly looser than the standard statistical rate O 3). Moreover, their realizability assumption requires the function approximators to include the value/weight functions associated with a policy n. depending on the sample size n. In particular, the resulting realizability condition is difficult to interpret since there is no explicit characterization of T..
Chen and Jiang (2022) took a different approach, the pessimistic value learning, achieving the statistically reasonable rate O). One of the main drawbacks of their result is, however, that the sample complexity bound blows up if the action value gap Cgap is near zero. Here, the action value gap is defined as the minimum gap in the values of the best action and the second best action, Cgap m maX ( a) maxe' 9" (s. a')), which becomes (near) zero if there exist two actions that are (near) optimal for even one state. In addition. it only competes with the optimal policy ne and requires the data to cover the corresponding visitation distribution d= Finally, the time-horizon dependency O(115) is a bit worse than the other results in the table.
Ozdaglar et al. (2023) showed two distinct results: one requiring a completeness-tye -tpee assumption and the other requiring realizability and action-value-gau value-gap assumptions, in addition to concentrability. We included the latter to the table. Roughly speaking, their result is similar to that Chen and Jiang (2022) except with the difference in the infinite/fnitte time horizons. Consequently, it also requires the action gap to be bounded away from zero We note that their algorithm relies on a constrained L., where the number of the constraints is equal to the size of S, making it possibly difficult scale to practical problems.
Uehara al. 2023) also proposed two distinct methods: one establishes slower O rate with the entropy regularization method, and the other establishes a sample complexity depending on so-called the soft action value gap. We only shows the latter in Table I For the latter result, the new condition on the soft action value gap relaxes those imposed on the ordinary action value gap by Chen and Jiang (2022); : Ozdaglar et al. (023). The order of the resulting sample complexity bound is (2-12177 1/app ) where Ugap 0 corresponds to the lower-tail exponent of the distribution of the state-wise action
13

---

value gaps, We also note that these bounds are explicitly depending on the size of the action space A. which could be potential drawback of the entropy-baae based method.
Compared to these results, our sample complexity bound has the following advantages. First of all, if there
gives the performance guarantees the model-free realizability with respect to (fixed) worst-case optimal policy म*. Third, it achieves the statistically reasonable rate O( 2) without any dependencies on the action value gap. Finally, it has no explicit dependency in the algorithm on the size of S and A, even in the policy extraction process.
concentrable policies. Second, it only requires
B Rademacher Complexity and Uniform Convergence
In this section, we introduce the Rademacher complexity and its properties as well as celebrated uniform convergence theorem. Below, let E be sample space, ( be probability distribution on it, and G R2 be set of functions from 2 IR.
Definition B.1 (Rademacher complexity). The Rademacher complexity of 9 with the sample size 2 is given by
Ry (9) = Eg ,
sup gEg i=1
oig(zi)
(23)
where En denotes the expectation with respect to samples or = {oi) and 2n = { drawn from Uniform" (f-1, and p", respectively.
Lemma B.1 (Uniform convergence theorem). Suppose l19llc for all g G. Then, for all E (0, 1), we have
2 2ln(2/8)
sup gEg
[9(2)) [9(2))]] s (9) + +ov
with probability 1 - 8 on the draw of nn p"
Proof. Refer to Claim 1, Theorem 26.5, Shalev-Shwartz and Ben-Davis (2014) for one-
side high-probability bound and apply it to both of supgeg H [x:))) E [1()))]] and
supyeg(-1) n. Ei= [s(2))] E [g(21)] } setting the confidence parameter 8/2. The proof is
completed by taking the union of the events that these tigh-probability bounds do not hold.
O
The following is another well-known result of the Rademacher complexity.
Lemma B.2 (Massart's lemma). For finite G. have
(G) & M 2 g
n
where
M(g)=
sup 9.9 0.9'Eg. sEZ
Ig(2) - 9 (=)
Proof. Refer to Shalev-Shwartz and Ben-David 2014). Lemma 26.8.
C Basic Properties of Regularized Lagrangian
In this section, we show basic property of regularized Lagrangian (Eq, 7)) Lemma C.1 (Primal Lipschitz continuity). For all v, v' have
[0, - --1-- and f F, we
K(E, f) K-'' fl < (2 Bx) |/u
111,,
14

---

Proof. Observe that by Eq. 7
|K (v, f) [K(,,)
((V s (1 7) l -u-vlll v 1, + || (6Th - - 0') I1l + (1 - >) 1|u o'll,,
The second term on the RHS further bounded as
|| (6TD 0 v')l') 1m
|| (1 -TT) v' 12
I
By 11(I 7T) 0')
By 110 - 11.
where (a) follows from Hölder's inequality and (b) follows from the triangle inequality. We obtain the desired result by summing up both sides of the two inequalities since S f..
Lemma C.2 (Stability minimax value against dual error). For all v 2 and x E 1l, we have
K(v, f) U Bv ||5 5
fm
1u8 - 2(1 7) -1 - 8- 1,2
where By = max (1 + BBv Bv}.
Proof. Observe that
K(v, f) 2 (V, f) - DT
(b) U(T) En, (1- DF())
@ (()) E (S-
(s,,
En (f (0))
@ U(T) + En3 (f- (r(s,a) + xT((s u(s)
U(()) - Bv B
where (a) follows from the nonegativity of (v), (b) from Lemma E.3 (c) from DF = 0. (d) from 7"th (8, a) 7T v(s, a) r(s,a) and (e) from Hölder's inequality with Ir 7Tv vl s By. The claim is then proved by the continuity of (TT).
U- U(T) = (1 - 7) 100 - 0 111,, + - 21
E, [( + ()) 6²)
2
$ (1 (1--)) 7) 1/ - -. 11,,,,,, + (1 -) || - 5" 1,,
< 2(1 7) ||ō" -001-
D Proofs of Section
4
D.I Proof of Theorem 4.1
Proof. The claim M E 1l is trivial from Definition 4.1 The other claim, J(T|MM S JTT(MM)
follows from that i) f(s, a) r(s,a) with f(s, a) E R(yls.))))) [y] for all S and a E A and ii)
the truncated transition probability T--|s, a), when in conflict with T(-]s, a), leads to the absorbing state 1, which has the lowest possible cumulative discounted value, zero.
D.2 Proof of Corollary 4.1
Proof. Since the inequality is trivial from Eq. [T. we show the equality. Observe that the state-action pair (st, a.) at time > stays inside supp(u3) almost surely for all > 0 if supp(d" c supp(u3). Hence, the law of the reward sequence {rahe2 generated with x is the same under M
and M, leading to J M (T.M).
15

---

D.3 Proof of Lemma 4.1
Proof. We show denying the conclusion results contradiction. Take a policy a E fr.
Let x)(s,a) = a() supp(3)) be the indicator function of supp(3). Let (7) Eo Xa(s, s) be the mass of (-|ss) inside the support of 3, which satisfies - x =5 S 1 for
all s E.
Let n' S + A(A) be a policy proportional to with the support restricted to supp(3), i.e. (s) n' (a]s) = xs(s, a) Taass) for all s E S and a E A.
By the definitions of fm and T we now have
I xols)
E (a)))((aas))())))
(5) E [xoss_))r/(sssr((ss
= 25 pT (s) 5))
and
Σ (1)
a,a'
= (s) Σ <'ass)) ((db)>x..ls..))](llss..h))
= (s) T' u(s) TT v(s)
for all v: S + [0, oc) and S. Therefore, we have for all E
-8)== - -1-
Ent S EGt y (s) =s)=ū" (s),
which leads to the strong optimality 8n = 8" However, we also have n' E IIg by the definition. contradicting with the assumption 11" Il. 0.
E
Proofs of Section
F. Proof of Lemma
The proof relies two lemmas (Lemmas E.I and E.2 where the second one is built top of the first one. Then, Lemma 5.1 is immediately proved as a special case of Lemma E.2 with и being restricted to Ii*.
Lemma E. gives saddle-poin -ointt decompasition of Lagrangian ignoring the offline constraint.
Lemma E.1 (Incomplete saddle-point decomposition of Lagrangian). For all a S + A(A).
=(v,f)=I(m) = J(T) + Σ (fuB-dd))(: TD a()
(24)
Proof. Comparing the LHS and the RHS, it suffices show
( (1 - Ep [o(s)] = Σ d= (s))s((()))) ((),s))
8.0
16

---

This is seen by simplifying the RHS of the above equation as follows,
(
d' (8) - (s- 70"
8,0
(b) Σ (I
v)
_ (1 7) Σ Po(s) (v" - v)
@ [(T] - (1 - Ppp [o(+)]
Here, (a) follows from E. T(als) 6TD
DDD ((s,a) = (r" + 7 (s) and fr = (1 7T- (b)
from (I-?T," being the adjoint operator of (I - TT") (c) from (1 - 7)po = (I - "T="""" dd" and
(d) from the definition of (T).
Note that the second term of Eq. (24) may have no root with respect to f if the data support does not cover the visitation distribution d", hence incomplete. Lemma E.2 gives a modification of Eq. (24) to fix this problem.
Lemma E.2 (Generalized saddle poidde decomposition of Lagrangian). For all π E IT we have
f(e,f) = J(T) - En.s ( - (s, - ( (4-F))ss011-7/(0==))s)))) (+))) -F(C), (25)
where D7(U)= = Eapp(p()) (s) and DF( = Ep,
a)))
Proof. Since Lagrangian is defined with r(s, a) and T(+ss, a) only on the support of the offline data distribution supp(uB), Lemma E.I together with the indistinguishabiitty of M and M gives
L(e, = Jmm)+ + E - 8,0
- ds 8 8TD u(s,a),
where JTT = F + +xT v. The second term of the RHS of the above equation further evaluated by separating the summation the on-support and off-st terms
Σ (fuB d= (s) 8T as
Σ
Σ
(fuB 5' ()) a) 8) v(s,a)
(sx))smupp(H))
(2) Ey,,8 [Is - (s) a) 8TD 8TD v(s,a)
Σ {((s)((
(sup)()))))))
-1-
- DF)
Σ
( (a)s)
sggsup((u) sesupp(a))a(sup(((t)))
( En,
(s, DF(F) + (T),),
where (a) follows from that ((ss))) (s) if (s, supp(u3) and STD ((s a) = (s, & supp(u(), (b) from transforming i in the first term, within JTD with
F= (I- + - and simplify the resulting (ğ- - with Enw If (s, (GT
(e))) and (c) from evaluating the last summation as zero with the fact supp(ut) c sup
Finally, Lemma 5.1 shown by taking such that 11. ni.
17

---

E.2 Proof of Theorem 5.1
Proof. First, see Appendix E for the proof of Lemma 5.1 Then, recall that (8*, fr) is a saddle point
of [(w,J) f) if I(ö", ff) S T(0", fr) s [(v, f(r for all v, f 2 0. By Eq. (6) with the nonnegativity of (u) and DF(f), it suffices to show (+-(")) = 0 and (f") = 0. The former follows from ö (s) = 0 for all # supp(n) and the latter follows from Ba- (s. (8) q" (s) =
v" (s) ū" (s) Barn(als) (7"("," (s,a)] a)]} 0 for all क E 11 n.."
E.3 Proof of Corollary 5.1
Proof. Note that the existence of the saddle points is always ensured since the (restricted) domains of u and f are all convex. Therefore, the first claim is reduced to 0 argmax min,ev, L(v, f), which is shown by Lemma 5.1 and the fact (1 - (v - 0) 2 (1 - 7) e >> for all E V.. Besides, the second claim is reduced to 0 argmin Jer. Lev, f), which is also shown by Lemma 5.1 and the fact Bf (s, a) (I - 77) - (s) 2 (1 - e [(V attains the minimum uniquely with v = 0.
eB
ū (s)]. which
E.4 Proof of Lemma 5.2
Define
U(T) = (1- (1-7) F) [s)] + (1 (1-
100d 112
2
Then, Lemma 5.2 is proved as special case of the following lemma with the restriction E Tg nîr and U = - E, (s)]
+ - || 2..
Lemma E.3 (Generalized saddle-point decomposition of regularized Lagrangian). For all E Ng.
K(v, f) = U(T) Eu.o (f (1) (s),a) DZ(() DF(
(26)
Proof. Observe that
2² = (v - 10 20 (2
Thus, multiplying both sides with (1 - 7//222 and plugging to Eq. 77) we get
K(v,f) f) (1-
2 (1v- Tx 112 115T ||==1|2,0
+ (1 - 7) Σ (M(s) + (1 - 7) 8T (s) (ss)s((())))))) + Ep,s [f(s, ((ss,,)
Now, applying Lemma we have
E.2 on the last two terms of the RHS with the formal substitution Pa + 8"
K(v,)) = (1 7)²
(11- 5 12, -1001
2
Σ de (s) FT (T((s) -En, | (
Σ (s) - DF(f)
(s) 71- パ 12,,2
- En, -f -1--)) + - DF(F).
where j(x), d' (s) and f* a) in Lemma 5.1 are replaced with Σ, ds) (s), dz (s) and j" a).
respectively, due to the substitution. Finally, the proof is concluded by simplifying the first term
18

---

the RHS
(1 7) Σ {ut (1- -
(1 - 7)
U(T) +
2
2.
where (a) follows from the fact (1 (1-71 ( is the adjoint operator of (1 (1--7>)- and (b) is owing
to 0 = -
E.5 Proof of Theorem 5.2
Proof. First, see Appendix E.4 for the proof of Lemma 5.2 Then, note that the third term D7 (v) nonegative for all 2 since d' (e, f) I U taking v ö* The first claim is then proved by combining these two inequalities, in the same manner as the proof of Theorem [5.1 The second claim, the uniqueness of o*, follows from the strong convexity of ()
Thus, have ((e, f) 2 U taking f = fr and
E.6 Proof of Lemma
Proof. Denote the primal excess risk function relative to F by
EPER (v) = max K(,,f) min max K (e,, f) v20 FEF
fEF
and its minimizer by en argmin,.2 m K(v, f). Now, the strong convexity of K(: f) implies the strong convexity of EPER and thus, for all v S R.
(1 ?1 ||v - e 12, & SPER(U).
2
We utilize this bound via the triangle inequality
2erEn (ig) + v 2ErER(("
|: 0* 11,,
112 + 11== 0n 0'112,
1-7
Then, each term on the RHS is bounded by
EPER (i*) S 26F,
(27)
EPER (op) -EPR) (ī*) (2 +2+ By)ey, (
(28)
completing the proof. The proofs of Eqs. (27) and (28) are separately given below.
Proof of Eq. Recall that by definition
EPER (ū*) max K( f) argmin max K (v, #20
JEF
FEF
Then, on the RHS, the first term is upper bounded with U by Theorem 5.2 and the second term
(without the negative sign) is lower bounded by Lemma C.2 leading to the inequality
EPER (ō*) < min
By
2(1 7) ||e 5.d 11
JEF
for all π E 1Ig. The proof is completed by taking the minimum with respect to
Proof of Eq. 28
immediately seen from
()E)(0)) EPen("") min max K(v, f) max K(i", ff)
wEv JeF
FEF
min max (K(v, f) - K( f)) wev fef
< (2 + By)
min || - 5" 8"112,p
wev
where the last inequality follows from Lemma C.I
19

---

Proofs of Section 6
F.1
Proof of Theorem 6.1
Recall that the average action value gap is given by
[(π)) = B, [0 (s) q (s, a)]
The following lemma establishes the connection of (TT)) and Eest (0). Lemma F.1. For all O we have
[(To) < (er(0) + Eap,
1 1-7
Proof. Refer Appendix F.2
Then, Theorem 6.1 is proved by combining Lemma E. with the following lemma.
Lemma F2. For all π : S + A(A), we have
J - J(m)
10 [(m).
Proof. It follows directly from Hölder's inequality with the performance difference lemma for the truncated environment (Lemma E.3).
F.2 Proof of Lemma F1
The proof relies on the following variant of the performance difference lemma adopted for the worst-case environment M.
Lemma E3 (Worst-case performance difference lemma). For all क S A(A), we have
J j(x) = E,,= (s) as,
Consequently, for all x E 1Ig
= En,e (() (s.,)))) J- - -(x)=
Proof. Observe that
j =1= - ro0
-
R, -1)
where the second equality follows from (I - -d Pu and the third equality follows from (s) and ((((s)) 0 for all supp(n) and (AA). Thus,
j (T) E (5) (1- (1- Exp -0 (s)F
E. - (6))
= Ep, [0= (0 (8) as)
where the second equality follows from fr ~ p= This proves the first claim.
The second claim follows from the definition of ft.
Let p = + (1 - 7)6" z be an alternative (unnormalized) initial state distribution and
(=)a) (1 --T"T"" (8) (s,
(29)
Hu(s)
be the corresponding action visitation weight function. Applying Lemma F3 to this setting, we obtain the following corollary.
20

---

Corollary F.1. Define
Ü (1-?) (s)
and let U = (1 (1-9) (.)
(*)) be its maximum. Then, we have
Ü Eun (5)) -
Now are prepared to prove Lemma F.1
Proof of Lemma F.I.
Let { argmin ll5 - -1,1,,,,0 Now, observe that
((TT))
(s
E p,
- a)] + Buc=
(6)
En,so (s)s) (s, + BTE
(e)
{ {- as) H)H D=(fo: wo ko)) } Bnee
IA
En [f((saa) { (s. |tf + Byez + Da(fo: no)} + Bies
16
(DF( + Lx(() + By(z) BIEe
(30)
where (a) follows from ||{ ll < Bme,, (b) from Hölder's inequality with (s, a) 2 and Wg 2 Y, and (c) from Eq. 11p. (d) from || wb S Bncs, and (e) from the definition of (f) (Lemma 5.1 and Lx (0). In the rest of the proof, we bound D (Ja) + (x( with (0)
Fix any E and क 1g.. Let iz E argmin max K ((v,f) and 1 argmax ( f). Also let K* ( ing minimax value. Then, K' + C() lower- bounded with (f( - (for)) up to an error term,
A min maxfez K(v, f) be the correspond-
K' + Lsr
max NEV K(05, f1) K(v, fo)
K(0i f1) K( fo)
2 ((0ū,fo)) K(ūg, fo)
@ DF((f) DF(f + E,, (Fo -
W8 (f())) DF( 2Br 1/ -8- 11,p
I/ (F( DF(Jer) - 2B Eap. (V,F),
(31)
where (a) follows from compromising the maximum with v :3 E V, (b) from the definition of J
above, (c) from Lemma 5.2 (d) from |lfollsc.l1.orl11_ I By and (c) from Lemma 5.3
Moreover, let
((6') = min
By for
1= + 2(1 7) 1 - 1=
jr| 1.0
ellla
21

---

be the intrinsic enror of 0' and fix arbitrary n²" E IIg IiI. Then, K + Lsr( is upper- with (66) up to another enror term.
- K + Lsp( K- - U0+ - min K (u, fo.)
NEV
@ (69 K(ū" f + U
min K (v, for
vEV
2 K (1) (( Ri) + U min K K(v, for)
ee
$ (2+ Bx) (2)
ग" 1. 2(0))
(d)
$ Bz) vV, +
(32)
where (a) follows from Lemma 5.2
(b) from Theorem 5.2 (c) from Lemma C. and Lemma C.2 and
(d) from Lemma 5.3
Subtracting both sides of Eq. from those of Eq. we get
(f6) (0) Csp( Di( + + (2+ (V,
which, summed with (x) S Lx + Few (z) (0) + ((0)) on both sides, yields (fo) + < Ean + +x ++)))))))))(((()++(+++)))++++))+
(V,F).
(33)
The remaining task is choose 0' θ such that (f Lx (00') is nicely bounded. Now, observe that
(fff En as) (s) q" (s)
Ey,ee fm a) (0 (s) q" (s, a)) + =En [fo- (s, (6"(s) q" ('(.
min =Eil
@ min *Ells
(ū*-Ü(p> Ü(T) Ep, (Jor jem) a) E (s, at)
(1 (1- |1ō- 1",,,,-- | for f* [1m0s >lmm)
min #Ells
(0'),,
(34)
where (a) follows from fエ fm (see Eq. (29) for the definition of f ) (b) from Lemma F3 (c)
from Hölder's 's inequality and (d) from p < 2 and || I Bv. Moreover, for all π E II we have
Cx(0') max LEE,, [So ((sss))((ss())) a)] - En (s){s)(s)))) EEE
(2)
< max E,, (0), a)] -max Ep, [ wa) (s)(s)
ECE
EEE
max (Buí (wig (s)E(s, - Ey [Wg (s){(s)))))) EEE
B
fo
fr
+ ||wa - tt 11,, + Bw lI - x TTV
(35)
1,4
where (a) follows from the telescoping and (b) from || < B for all E E E and || - wo 1, S
| i since पो minimizers of Eqs. and (13 respectively, we arrive at
1-7. Adding both sides of Eqs. (34) and (35) and taking and o' as the
(ffre) Lx (0') I (4'(0) + Bzee (T) < 3
(36)
where the last inequality follows from (0') < c (Eq. 12 The proof is concluded by adding both sides of Eqs. (30
33 and (36) and simplifying the error terms with Eq. (16).
22

---

F.3 Extensions of Corollary 6.1
The suboptimality bound established by Corollary 6.1 requires the uniform boundedness of - || With more careful analysis, however, we can obtain policy suboptimality bounds with milder condi- tions. We present two of such upper bounds below.
To this end, we introduce two types of local truncated concentrability. Let = (T()) = (To 1 E E) be the set of all the policy candidates.
Definition F.1. Let Č2 = max | J -(x) SE, 11} be the e-weakly local truncated concentrability (c- (c-LLTC) coefficient for O. We also define the limit WLTC coefficient
Co = lim--0+ C..
Definition F.2. Let E ==ax ol ( (s) (s, S S -
} be the e-strongly local truncated concentrabiliity (e-SLTC) coefficient for > 0. We also define the limit SLTC coefficient as lim.-0+ Ce.
Intuitively, both the WLTC and SLTC coefficients bound the norm of 7 locally for near-optimal policies x. The difference is the ways they measure the locality: WLTC uses the policy suboptimality and SLTC uses the maximum action value gap. Note that WLTC dominates SLTC, & S C. S Coc. (I))) covers the entire policy space A(A)s. In general, there is no particular order between WLTC and SLTC and we just have C. S Ooe.
The following lemma is the foundation of our local concentrability results.
Lemma F.4. For any π IL we have
J -(x) S (L+ (xa(=) cO(F))
20
where EO(T)=
Proof. Refer to Appendix F.4
Combining it with Lemma F.1 and discarding the non-asymptotic term for the simplicity, we get the first bound as the following corollary.
Corollary F.2. For all E θ we have
J- ((To S $21
Co (Eem(0) + Eapp, (V,
(37)
where a S means lim sup, a/b S
In words, Eq. 37 allows to replace the uniform concentrability coefficient Eo with the limit SLTC coefficient Co at the cost of the slower convergence rate due to the square root.
Moreover, faster bound can be obtained exploiting the limit WLTC coefficient Co instead of co leading to our second bound.
Corollary F.3. For all E O we have
Co (Ees(()) + Eapo. (0, 0,E)) jr j((o) 1-7
(38)
Proof. Observe that Corollary F.2 implies ||:ū*T0| 11 is bounded with Č.,, where is taken as the RHS of Eq. (37). The claim thus follows from Theorem 6.1 with | Il S Ö. - Co test Eapp.1 (V, 0, E)
Similarly as Corollary F22 in comparison to Theorem 6. the coefficient of the upper bound is improved from Čop to Co, meaning that asymptotically we only need the weakly local, not uniform, concentrability.
23

---

F.4 Proof of Lemma F.4
Let us denote the set of the e-strongly near-optimal policies by
-== (T 8 A(A) (s)) C (s)) supp(u))
where (;(s) fa A (s) - q" (s) S E) is the e-optimal action subset for E S Note that by definition ii f1" and Г is monotone nondecreasing with respect to e, reaching the set of all policies with 2 1/(1 - 7). Then, the SLTC coefficient can be written in terms of II;,
C max | =
Now, to prove Lemma F.4 we show that there exists strongly optimal policy स E II; that approxi- mates the target policy if [(T) is small.
Lemma F.S. For all ((A) and > have
(T
min || - क TV #Ell;
Proof. Take n' E iī as projection onto Ii,, i.e.
<'(ss) 1/a E (1))))T(aas)) + c(s) mo(als),
SES,
with arbitrary To E II; and c(s) = 1 Eue ((ass). Observe that, by the triangle inequality,
|| - n IT = E Σ (T(as)) - <'|ss)
- E, Σ 11- 1 ([())))(alss++ + +c(s)
= 2E [c(s)]
Then, we have
|| TT. S 2F [c(s)] 2R [1aa s A:()))]-
min #ell;
Now, plugging
I 1fa -10)
(5 (s, a))
(5
on the RHS. we arrive at the desired inequality
min || - क TV, S 2 En, -() = T(T).
2 as)
As corollary, can also bound the difference of their policy values based the SLTC coefficient.
Corollary F.4. For all + A(A) and > 0, we have
22, [(T))
min
j(() j(m)
<
1 1-7
It referred strong near-optimality since it implies the near-optimality in the usual sense, i.e. J J(x) e for all a II:
24

---

Proof. Take arbitrary ă E II; and observe that
(s) d (b) = (1 (1- (1-) (1-
-1] po(s)
(1-7) (1--))11- (1- -I (1-7),) (1 -t,²) ('o())
= 7(1 7)(1 1111-770 ,T,)) (T.- - -.)) (1 - 1->T.")~\po(s
71 -t=) (PT - -P!) (s).
Thus, we have
100h
w 111,0
Σ
dC - 8 [(s)
sEsupp(u)
Σ
7(1 (T.)) 'T (P. 1P5-P' -P.) d' ds((s
*Esupр(μ)
7
(P - -P.) d= (s,
(s.p)Esupp(dd)
(x)
By 1-7
7_
(x(aas) [((b))+ =(als))
(u(s)
aEsupp(((s)
(b)
70c,
Ep
ITaas) #(a
7
70g 7
||
T ,T
(39)
where (a) follows from the fact t.T and T. can be identified as non-expansive mappings of types L' (supp(μ)) + L' ('(uup(()) and L (ssuup(u))) + L' (((up)(())) respectively, and (b) follows from म E π.. Finally, observe that
(((x) J(()
E, [ - - -***) [>)]
3V
E2 (w" w )r* (8) + 1 (F - F*) { (8)
1/3
w || 1n,1 + ce || - क FlT
#IlTV.
where (a) follows from the triangle inequality, (b) from the fact (F(s a)l S 1 and (c) from Eq. (9) The proof is concluded by applying Lemma F5 on the RHS.
We now arrive at the following corollary, which immediately implies Lemma F.4 as a special case with the substitution cu(TT)
Corollary F.S. For all c > 0, we have
2c. [(T)
j-- [(T] S
7
Proof. By Lemma F3 we have
(( = By. [00 (s) 17 - S elE (ú0 (s) S
for all स E n.. Thus, decomposing the suboptimality
j j- j(x) + {((m) j(
and applying Corollary F4 results in the desired result.
25

---

F55
Proof of Corollary 6.2
Proof. The celebrated uniform convergence theorem (Lemma B.1 with the boundedness
(0),,, < Ball implies that, for all E (0,
l2(2/))
max ....EVVEEE
((0 [[[(0; (H) + Ball
(40)
2n
with probability 1-6 8. Now, by definition, (es is uniformly approximated with (0) up as twice as the statistical error given by Eq. (40). Plugging this into Eq. (18), we obtain the desired bound.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The worst-case policy value is introduced in Section and the sample complex- ity bound is given by Corollary 6.3 wherein the realizabiliity condition (Eapp. 0, 0) is the only major assumption. The improvements over the previous sample complexity
Justification:
bounds are summarized in Table and discussed in Section 2 and Appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations discussed in Section 7
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer:
[Yes]
Justification: All the assumptions are explicit in the main text. The complete proof is presented in Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
No experimental result is presented.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
No experimental result is presented.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guudddeeeedSuuuummbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experimental result is presented.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No experimental result is presented.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experimental result is presented.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp/://oourrpss..cpppuee//e//
Answer: [Yes]
Justification: This paper is purely theoretical.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There no immediate societal impact to considered the present work since the results are purely theoretical.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No dataset or model is disclosed.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "tv0NSBU3H5", "reviewer": "Reviewer_cb9T", "summary": "This paper studies offline RL with no data support assumptions. To address the data coverage problem, the paper studies a new setting with worst-case policy value. It formulates the RL problem with Lagrangian and shows the instability compared with the regularized Lagrangian. Improved sample complexity is proved in the new framework.", "questions": "1. Why do you think the realizability assumption in [ZHH+22] is $\\pi_n$-realizable? Do you think there is a huge influence on the result?\n\n2. What are the $\\bar w$ and $\\|\\cdot\\|_{1,\\bar w}$ in equation (10)?\n\n3. In equation (17), the empirical loss function is defined from the one-sample loss function. Is it possible to generalize the method using the batch loss function?", "limitations": "The authors have addressed the limitations in section 7.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed new framework is novel and interesting in the study of offline RL.\n2. The paper provides analysis of the stability of lagrangian and regularized lagrangian.\n3. The paper proved an improved sample complexity.", "weaknesses": "1. The paper studies everything in a new framework, where the transition is constrained in the range of the data. It seems unfair to compare the results in the new framework with previous works, as they can also work for out-of-distribution data to some extent. As shown in Theorem 4.1, the loss will become smaller in the new framework.\n\n2. The behavior of the truncated transition kernel (2) is strange. As the indicator function does not contain any information about the next state s’, $\\sum_{s’} \\tilde T(s’|s,a) = \\chi_{\\mu, \\beta}(s,a)$, which takes values in 1 or 0 only. It does not match the leaky description in the paper, i.e., it may sum to less than unity.\n\n3. The paper misses comparison with some relevant papers. For example, [1] [2]\n\n[1] Rashidinejad et al 2022. Optimal conservative offline rl with general function approximation via augmented lagrangian. In ICLR.\n\n[2]  Ozdaglar et al. 2023. Revisiting the linear-programming framework for offline rl with general function approximation. In ICML.\n\n4. The superscripts used are too complex and lack explanations, making the writing hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate your helpful review and comments.\nWe hope our response below resolve potential misunderstandings and address your questions.\nThe response consists of two parts: clarifications and answers.\n\n## Clarifications\n> It seems unfair to compare the results in the new framework with previous works, as they can also work for out-of-distribution data to some extent. As shown in Theorem 4.1, the loss will become smaller in the new framework.\n\nLet us clarify one potential confusion here: The comparison of our method to previous work in Table 1 is in fact fair since all the methods in the table bound the sample complexity with respect to the same (conventional) metric, $J(\\pi)$. This is, as stated in the last sentence of Section 6, seen by the fact the new metric and conventional metric coincides under the concentrability condition. \n\n> The paper misses comparison with some relevant papers. For example, [1] [2]\n\nThank you for pointing out relevant papers. We agree these references should be included in our paper.\nBelow, we discuss their similarities and differences in comparison with our result.\n\nFirst of all, one notable similarity is that [1], [2] and we all studied offline RL based on the LP formulation.\nOn the other hand, the most essential difference is that both [1] and [2] consider the conventional offline RL, unlike us considering the worst-case offline RL making the scopes of our analysis broader than theirs.\nThat being said, their results can be compared to ours within the non-worst-case framework as we did in Table 1.\nThe following is the extension of Table 1 including [1] and [2].\n\n| method | concentrability | realizability | sample complexity bound |\n|----|----|----|----|\n| [1] | $\\pi^\\*$ | $\\pi^\\*$-realizable + \"completeness\" | $\\epsilon^{-2}(1-\\gamma)^{-6}\\ln(\\mathcal{N}/\\delta)$ |\n| [2] | $\\pi^\\*$ | $\\pi^\\*$-realizable | $\\epsilon^{-2}C\\_{\\mathrm{gap}}^{-2}(1-\\gamma)^{-6}\\ln(\\mathcal{N}/\\delta)$ |\n| ours | any comparator | $\\pi^\\*$-realizable | $\\epsilon^{-2}(1-\\gamma)^{-4}\\ln(\\mathcal{N}/\\delta)$ |\n\nIn summary, our result strictly improves upon both of theirs.\nBelow are the detailed comments on the table.\n\n- [1] achieves the sample complexity bound of $O(1/\\epsilon^2)$ leveraging the notion of the occupancy validity, enforced by a new regularization term. However, their bound requires some completeness-type condition (\"$u^\\star\\_w\\in\\mathcal{U}$ for all $\\mathcal{W}$\", Theorem 4, [1]) for one of its function approximators $\\mathcal{U}$, which is more stringent than the realizability. Besides that, our sample complexity bound improves theirs by factor of $(1-\\gamma)^2$.\n\n- [2] shows two distinct results: one requiring the completeness-type assumption and the other requiring the realizability and the action gap assumption, in addition to the concentrability. We included the latter to the table. Roughly speaking, the result of [2] is similar to that of [CJ22] except with the difference in the infinite/finite time horizons, requiring the action gap to be bounded away from zero.\n\n\n## Answers to the questions\n> Why do you think the realizability assumption in [ZHH+22] is $\\pi\\_n$-realizable?\n\nIn Corollary 12, [ZHH+22], their sample complexity bound requires the regularization weight $\\alpha$ to be dependent on the error tolerance parameter $\\epsilon$.\nThis implies the target policy $\\pi\\_{\\alpha,B\\_w}^\\*$ of the realizability condition (Assumption 6, [ZHH+22]) depends on $\\epsilon$ as well,\ni.e., their method requires $\\pi\\_\\epsilon$-realizability.\nSince the minimum possible $\\epsilon$ depends on $n$, it also implies $\\pi\\_n$-realizability.\n\n> Do you think there is a huge influence on the result?\n\nWe think whether the influence is huge or not is context-dependent.\nOne potential drawback is that the nonconstancy of $\\pi\\_n$ would make the nonparametric extension more difficult\nsince the target policy moves around as $n\\to\\infty$.\n\n> What are the $\\bar{\\omega}$ and $|\\cdot|\\_{1,\\bar{\\omega}}$ in equation (10)?\n\nThis is typo: sorry for that and thank you for pointing it out. The correct notation is $\\bar{\\mu}$ and $|\\cdot|\\_{1,\\bar{\\mu}}$,\nwhich are defined just below Eq. (5).\n\n> In equation (17), the empirical loss function is defined from the one-sample loss function. Is it possible to generalize the method using the batch loss function?\n\nOur method uses the mean of the one-sample loss functions over the batch data $\\mathcal{D}$ (Eq. (16)),\nwhich is, in a sense, a batch loss function and our method uses it directly.\nPlease let us know if you have other kind of batch loss function in mind.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0FLMrBSFsE", "reviewer": "Reviewer_AjPn", "summary": "The paper develops a framework for evaluating offline reinforcement learning methods without any data-support conditions. Traditional techniques rely on the concentrability coefficient to ground the difference between the offline data distribution and the induced policy distribution. However, the concentrability condition is often unrealistic in practice, especially when the state-action space is very large, as is frequently the case. This paper proves by construction a sample complexity upper bound of $O(\\epsilon^{-2}(1 - \\gamma)^{-4}\\ln(1/\\delta))$ is achievable without relying on the concentrability condition. This improves upon several bounds from previous work, involving similar assumptions.", "questions": "No questions.", "limitations": "The authors have mentioned that although their results extend to continuous state-action spaces, the concentrability coefficients are not unconditionally finite anymore.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper shows some originality in creating a new framework that does not rely on the frequent concentrability condition found in offline RL literature. The associated restriction in this paper is even less-so than the single-policy concentrability condition found in Zhan, Huang, Huang, et al.\n- The paper simplifies the traditional offline RL evaluation framework by removing the need to directly incorporate pessimism or behavioral cloning via hyperparameters into the analysis.\n- The paper provides a strong theoretical proof to establish the stated upper bound.", "weaknesses": "- I feel the proposed truncated environment is overly restrictive and ignores information between similar state-action pairs, even if they're not represented in the support of the offline data distribution. Although the benefit of doing this is that it removes the need to control for pessimism and behavioral cloning, there could be some useful information discarded, which could help improve the bound derived in the paper.\n\nUPDATE: this has been addressed by the authors' followup.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful review and comments.\nBelow, we would like to provide additional discussion on the weakness you mentioned.\n\n> I feel the proposed truncated environment is overly restrictive and ignores information between similar state-action pairs, even if they're not represented in the support of the offline data distribution. Although the benefit of doing this is that it removes the need to control for pessimism and behavioral cloning, there could be some useful information discarded, which could help improve the bound derived in the paper.\n\nFirst of all, we agree that there may be more practically reasonable way of introducing pessimism and it is an interesting research topic.\n\nHowever, we would like to emphasize that the effect of ignoring the state/action similarities here is minimal under the conventional RL setting.\nThis can be verified by that \nthe truncation of the transition kernel conserves the (non-pessimistic) policy value $J(\\pi)$ under $\\pi$-concentrability, as stated by Theorem 4.1.\nIn other words, the seemingly-excessive pessimism of our truncation method only affects the RL outside the data support, which is previously unexplored. Thus, we think it is currently unclear if the conventional pessimism/behavioral cloning methods can be better alternatives here.\n\nAlso note that our method can take into account the on-support state-action similarity via the smoothness of the function approximators.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2urxgyAAGg", "reviewer": "Reviewer_Kpf4", "summary": "This paper studies offline reinforcement learning with arbitrary data support. More specifically, they truncate the original environment so that the new environment (called truncated environment) is always covered by the offline data. They further show that the optimal policy of the truncated environment can be found by solving a regularized Lagrangian problem and analyze the corresponding sample complexity. As a byproduct, they attain a $O(1/\\epsilon^2)$ sample complexity bound for learning an $\\epsilon$-optimal policy against any comparator policy with bounded concentrability and realizability.", "questions": "Similar to the weaknesses:\n1. can we get rid of $\\tilde{C}_{\\infty}$?\n2. can the algorithm work without the knowledge of the behavior policy?", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The connection between the truncated environment and the regularized Lagrangian problem is very novel and useful in my opinion. \n2. The authors improve the sample complexity of learning with single-policy concentrability and realizability to $1/\\epsilon^2$, which is a significant contribution.", "weaknesses": "1. In the sample complexity of Corollary 6.16.2/6.3, the rates scale with $\\tilde{C}_{\\infty}$, which is indeed the concentrability bound for all policies within the policy class. This seems stronger than the naive single-policy concentrability.\n2. The algorithm requires the knowledge of the behavior policy, which might be hard to estimate in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful review and comments.\nPlease find below the answers to your questions.\n\n> can we get rid of $\\tilde{C}\\_\\infty$?\n\nAsymptotically, yes. Such extensions are discussed in the appendix, Section E.4.\nIn summary, we can replace the uniform concentrability $\\tilde{C}\\_\\infty$ with either of the two variants of local concentrabilities $\\tilde{C}\\_0$ and $\\tilde{c}\\_0$, where the policy class is restricted to near-optimal policies rather than all policies.\nPlease refer to Definition E.1 and E.2 for the precise definitions and Corollary E.2 and E.3 for the corresponding results.\nThat being said, whether similar improvements in a non-asymptotic manner is possible or not remains unclear and open for the future work.\n\n> can the algorithm work without the knowledge of the behavior policy?\n\nThis is also yes. In our algorithm, the behavior policy need not be known since it is estimated as $\\beta_\\theta$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A1bHbOZ38T", "reviewer": "Reviewer_xcKA", "summary": "In this submission, the authors propose some new bounds for offline reinforcement learning. Their contribution is twofold. First, they remove the classical data support assumption by solving a relaxed problem, in which any non observed transition is replaced by a transition to an absorbing state. This new MDP yields a lower reward than the original one, hence the worst-case name, but can be learned with the given data. Second, they use a regularized version of the Linear Programming formulation of the optimal policy problem to estimate the good policy. Their improved bounds come from the direct use of the dual variable to obtain the policy, rather than using a policy-improvement step on the primal variable (the value function).", "questions": "The bounds obtained are upper bound. Are the author aware of corresponding lower bounds?\n\nTypos and misc.:\n- 167: formulation\n- 179: Why is $v \\geq 0$ so important\n- 209: $\\bar v$ vs $\\tilde v$ : hard to distinguish\n- 259: $\\epsilon_\\theta$ is often called an excess risk, or something similar.\n- 306: $n \\geq$ rather than $n =$", "limitations": "The only limitation is that there is no numerical experiment to support the claim, but this should not be expected from such a theoretical paper.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The approach is interesting with simultaneously a new “worst-case” setting and new way to obtain result with the regularized linear programming approach.\n\nThe paper is well written, the proofs seem correct (I did not check them carefully).", "weaknesses": "The paper is very technical and is written in a linear way. I know that the space constraint is strong, but I would have liked a better summary of the main idea at the beginning of the paper so that the position with respect to the relative work would be easier to understand.\n\nThe notations often differ only by a slight detail. Using larger difference may be beneficial for the readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful review and feedbacks.\nIn particular, we agree that the manuscript can be improved by adding the position/contribution summary and improving visual aspects of some notation.\nPlease find below the answers for your questions.\n\n----\n\n> Are the author aware of corresponding lower bounds?\n\nNo, we are not aware of lower bounds for the model-free estimators with funciton approximation.\nThe closest result we are aware of is given by [1], which is a minimax lower bound for the model-based estimators without function approximation (i.e., tabular setting).\nSince the underlying hypothesis classes are different (i.e., general model-free function class vs tabular environment class),\nit is not straightforwardly applicable to our setting.\n\n----\n\n> 179: Why is $v\\ge 0$ so important\n\nWe assume you are referring to Line 169.\nIn fact, the nonnegativity of $v$ is the key to make the LP feasibility agnostic to the concentrability condition.\nThis is seen by that,\nwhen the concentrability does not hold (i.e., $\\mathrm{supp}(d^\\pi)\\not\\subset \\mathrm{supp}(\\mu)$),\nthe $v$-residual term $D\\_V^\\pi(v)$ in Eq. (4) can be negative infinity by taking $v(s)\\to-\\infty$ for $s\\in \\mathrm{supp}(d^\\pi)\\setminus\\mathrm{supp}(\\mu)$.\nThe constraint of $v\\ge 0$ prevents the divergence towards negative infinity\nand necessary to ensure the concentrability-agnostic existence of the saddle points of $L(v,f)$.\n\n----\n\n[1] Li, Shi, Chen, Chi & Wei. (2024). Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper tackles the setting where there is no data distribution assumption and derives the sample complexity analysis on the modified environment. This is a nice study that makes interesting contributions to RL theory. It is also in the interest of the NeurIPS community.  I recommend the paper be accepted. However, there are two aspects that are currently missing and should be added in the final version. 

1. The discussion of related literature needs to be improved. For instance, since the current paper focus on the offline RL with general function approximation, there are many other formats of doing function approximation and many results have been obtained e.g. [1],[2]. The authors should add these literatures (and other papers) to make the related literature section more comprehensive. 

[1] Pessimistic nonlinear least-squares value iteration for offline reinforcement learning, ICML 2024.
[2] Offline reinforcement learning with differentiable function approximation is provably efficient, ICLR, 2023.

2. The notion of truncated environment is very similar to Section 5 of [3] which uses absorbing MDPs to handle assmption-free regime. When the bahavior policy has sufficient data coverage, it reduces to the standard result with finite single concentrability coefficient. Though [3] tackles Tabular RL and instance-dependent perspective, I believe the idea of handling arbitrary data is similar and should be discussed in the final version.  

[3] Towards Instance-Optimal Offline Reinforcement Learning with Pessimism, NeurIPS 2021.
Decision: Accept (poster)