Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning
Authors: Qiwei Di
Heyang Zhao
Jiafan He
Quanquan Gu
Venue: ICLR 2024 poster (2024)
Keywords: Offline reinforcement learning
instance-dependent
least-squares value iteration
Primary area: reinforcement learning
TL;DR: In this paper, we present Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI), an oracle-efficient algorithm for offline RL with non-linear function approximation.

Abstract: Offline reinforcement learning (RL), where the agent aims to learn the optimal policy based on the data collected by a behavior policy, has attracted increasing attention in recent years. While offline RL with linear function approximation has been extensively studied with optimal results achieved under certain assumptions, many works shift their interest to offline RL with non-linear function approximation.
However, limited works on offline RL with non-linear function approximation have instance-dependent regret guarantees.
    In this paper, we propose an oracle-efficient algorithm, dubbed Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI), for offline RL with non-linear function approximation. Our algorithmic design comprises three innovative components: (1) a variance-based weighted regression scheme that can be applied to a wide range of function classes, (2) a subroutine for variance estimation, and (3) a planning phase that utilizes a pessimistic value iteration approach. Our algorithm enjoys a regret bound that has a tight dependency on the function class complexity and achieves minimax optimal instance-dependent regret when specialized to linear function approximation. Our work extends the previous instance-dependent results within simpler function classes, such as linear and differentiable function to a more general framework. To the best of our knowledge, this is the first statistically optimal algorithm for nonlinear offline RL.

PESSIMISTIC NONLINEAR LEAST-SQUARES VALUE IT- ERATION FOR OFFLINE REINFORCEMENT LEARNING
Qiwei Di Heyang Jiafan he', Quanquan Gu 'Department of Computer Science. University of California, Los Angeles {qiwe 2000, hyzhao, j jiafanhel 9, q uulal edd,,
ABSTRACT
Offline reinforcement learning (RL), where the agent aims to learn the optimal policy based on the data collected by behavior policy, has attracted increasing attention in recent years. While offline RL with linear function approximation has been extensively studicd with optimal results achieved under certain assumptions, many works shift their interest to offline RL with non-linear function approximation. However, limited works on offline RL with non-linear function approximation have instance-dependent regret guarantees. In this paper, we propose an oracle-efficient algorithm, dubbed Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI), for offline RL with non-linear function approximation. Our algorithmic design comprises three innovative components: (1) a variance-based weighted regression scheme that can be applied to wide range of function classes, (2) subroutine for variance estimation, and (3) planning phase that utilizes a pessimistic value iteration approach. Our algorithm enjoys a regret bound that has a tight dependency the function class complexity and achieves minimax optimal instance-dependen regret when specialized to linear function approximation. Our work extends the previous instance-des -eeaanee-eeedeent results within simpler function classes, such linear and differentiable function to a more general framework.
INTRODUCTION
Offline reinforcement learning (RL), also known as batch RL, is a learning paradigm where an agent learns make decisions based set of pre-collected data, instead of interacting with the environment in real-time like online RL. The goal offline RL is to learn a policy that performs well in given task, based on historical data that was collected from unknown environment. Recent years have witnessed significant progress in developing offline RL. algorithms that can leverage large amounts of data learn effective policies. These algorithms often incorporate powerful function approximation techniques, such as deep neural networks, to generalize across large state-action spaces. They have achieved excellent performances in wide range of domains, including the games of Go and chess (Silver et al. 2017] Schrittwieser et al. 2020), robotics (Gu et al. 2017 Levine et al.
2018), and control systems (Degrave et al.) (2022).
Several works have studied the theoretical guarantees of offline tabular RL. and proved near-optimal sample complexities in this setting (Xic et al. [2021b] Shi et 2022 Li et al. 2022). However, these algorithms cannot handle real-world applications with large state and action spaces. Consequently, significant body of research has devoted to offline RL with function approximation. For example, (Tin et al.) 2021b) proposed the first efficient algorithm for offline RL with linear MDPs, employing the principle of pessimism. Subsequently, numerous works have presented a range of algorithms for offline RL with linear function approximation, as seen in Zanette al. (2021) 1); Min et al.) (202T): Yin et al. (2022a); : Xiong et al. ): Nguyen-'Tane Tang et al. (2023). Among them, some works have instance- deeenne-deeendentt (a.k.a..
-eleemmd-eeedeent) upper bound (Jin et al., 2021b Yin al./ 2022al] Xiong et al. [023 Nguyen- Tauyen-Tang-a et al. (202)), which matches the worst-case result when dealing with the "hard instance" and performs better easy cases.
To address the complexities of working with more complex function classes, recent research has shifted the focus towards offline reinforcement learning (RL) with general function approximation
(Chen & Jiang 2019 Xie et al.) 2021a). Utilizing the principle of pessimism first used in Jin et al. (2021b), Xie et al. (2021a) enforced pessimism at the initial state over the set of functions consistent with the Bellman equations. Their algorithm requires solving optimization problem over all the potential policies and corresponding version space, which includes all functions with lower Bellman-error. To overcome this limitation, Xie et al. (2021a) proposed practical algorithm which

---

has poor dependency the function class complexity. Later, Cheng al. (2022) proposed an adversarially trained actor critic method based upon the concept of relative pessimism. Their result is not statistically optimal and was later improved by/Zhu et al. (2023). Both algorithms' implementation relies on a no-regret policy optimization oracle. Another line of works, such as (Zhan et al.) 2022] Ozdaglar al., 2023] [Rahidinnejad al. 202T], sought solve the offline RI. problem through linear programming formulation, which requires some additional convexity assumptions on the policy class. However, most of these works only have worst-case regret guarantee. The only exception is Yin et al. (2022)), which studies the general differentiable function class and proposed an LSVI-type algorithm. For more general function classes, how to get instance-dependee characterizations is still an open problem. Therefore, a natural question arises:
Can we design a computationally tructable algorithm that is statistically efficient with respect to the complexity of nonlinear function class and has an aastance-depente regret bound? We give an affirmative answer to the above question in this work. Our contributions are listed as follows:
We propose a pessimism- based algorithm Pessimistic Nonlinear Least-Square Value Iteration (PNLSVT) designed for nonlinear function approximation, which strictly generalizes the existing pessimism-basee algorithms for both linear and differentiable function approximation (Xiong et al., 2023 Yin et al. 2022b). Our algorithm is oracle-efficien, i.c., it is computationally efficient when there exists an efficient regression oracle and bonus oracle for the function class (e.g., generalized linear function class). The bonus oracle can also be reduced to a finite number of calls to the regression oracle.
We introduce a new type of D*-divergence to quantify the uncertainty of an offline dataset, which naturally extends the role of the elliptical norm seen in the linear setting and the Di-ddvergencc in Gentile et al. (2022); Agarwal et al. (2023); Ye et al. (2023) for online RL. We prove an instance- dependent regret bound characterized by this new Dd Divdivergence. Our regret bound has a tight dependence on complexity of the function class, i.e., Ö(VoggN) with N being the cardinality of the underlying function class, which improves the Ö(log N) dependence in Yin et al. 2022b) and resolves the open problem raised in their paper.
Notation: In this work, we lowercase letters to denote scalars and use lower and uppercase boldface letters to denote vectors and matrices respectively. For a vector x E Rd and matrix E E Rdxd, we denote by ||x||2 the Euclidean norm and ||x|| = Vx Σx. For two sequences {an} and )b we write an = Ob,,, if there exists an absolute constant C' such that a, S Cbn,, and we write an = ((b,,) if there exists an absolute constant C such that an 2 Cb We use Ö(-) and π2(-) to further hide the logarithmic factors. For any a S b E IR, function 1(x S a) + x 1 (a < < b) + b 1(b S æ),, where 1-)) is the indicator function. For positive integer n1, we use [n]] = 21, n} to denote the set of integers from to n.
IR. let [a]]o.b) denote the truncate
2 RELATED WORK
RL with function approximation. As one of the simplest function approximation classes, linear representation in RL has been extensively studied in recent years (Jiang et al., 2017] Dann et al.
2018, Yang & Wang. 2019 Jin al. 2020 Wang al. 2020c] Du al. 2019; (Sun et al. 2019
Zanette et al. [200a bj Weisz et al. [02]]|aag & Wang
et al. 2020 Ayoub et al. 2020
Zhou al. |221]] He et al. 2021: Zhong et al.) 2022). ). Several assumptions on the linear structure
of the underlying MDPs have been made in these works, ranging from the linear MDP assumption
(Yang& & Wang 2019 Din et al. 2020 Hu et al.) 2022; He al.) 2022; Agarwal et al.) 2023) to the low Bellman-rank assumption (Jiang et al. 2017) and the low inherent Bellman error assumption (Zanette) jet al.) 2020b). Extending the previous theoretical guarantees to more general problem classes, RL with nonlinear function classes has garnered increased attention in recent years (Wang et al.) 2020b
Jin et al. 2021a| Foster et al. 2021 Du et al., 2021 Agarwal & Zhang 2022 Agarwal et al. (023)) Various complexity measures of function classes have been studied including Bellman rank (Jiang Coefficient (Foster
et al. 2017), Bellman-FFluder dimension (Jin et al. 2021a). Decision-EEsimatie
2021 and generalized Eluder dimension (Agarwal al. 2023). Among these works, the setting
in our paper is most related to Agarwal et al. (2023) where D Di-divergence (Gentile et al. 2022) was introduced in RL indicate the uncertainty of a sample with respect to particular sample batch.
In Yin et al. 2022h), they denote by d the complexity of the underlying function class, which is essentially log.V N using our notation.
2

---

Offline tabular RL. There is line of works integrating the principle of pessimism to develop
statistically efficient algorithms for offline tabular RL setting (Rashidinejad et al. 2021 Yin & Wang
202T [ie et al. 2021b; (Shi et al.] 2022 Li et al. 2022). More specifically, Xie al. (2021b) utilized the variance of transition noise and proposed a nearly optimal algorithm based on pessimism and
Bernstein-type bonus. Subsequently, [i et al. (022) proposed a model-based approach that achieves
minimax-optimal sample complexity without burn-in cost for tabular MDPs. [Shi et al. (2022) also contributed by proposing the first nearly minimax-optimal model-free offline RL algorithm.
Offline RL with linear function approximation. Din et al. (2021b) presented the initial theoretical results on offline linear MDPs. They introduced a pessimism pessimism-primcipledd algorithmic framework for
offline RL and proposed an algorithm based on LSVI (Jin et al., 2020). Min et al. (202T) subsequently considered offline policy evaluation (OPE) linear MDPs, assuming independence between data samples across time steps to obtain tighter confidence sets and proposed an algorithm with optimal d dependence. Yin et al. (2022a) took one step further and considered the policy optimization in linear MDPs, which implicitly requires the same independence assumption. Zanette et al. (2021) proposed an actor-critic- based algorithm that establishes pessimism principle by directly perturbing the parameter vectors in linear function approximation framework. Recently, Xiong et al. (2023)
proposed a novel uncertainty decomposition technique via a reference function, and demonstrated their algorithm matches the performance lower bound up to logarithmic factors.
Offline RL with general function approximation. Chen & Jiang (0119) examined the assumptions
underlying value-function approximation methods and established an information-theoreti lower pessimism, which enables sample-efficient guarantees by relying solely the Dellman-completenes assumption. Uchara & Sun (202T) focused on model-based offline RL with function approximation under partial coverage, demonstrating that realizability in the function class and partial coverage are sufficient for policy learning. Zhan et al.] (2022) proposed an algorithm that achieves polynomial sample complexity under the realizability and single-policy concentrability assumptions. Nguyen-Tang & Arora (2023) proposed a method of random perturbations and pessimism for neural function approximation. For differentiable function classes. Yin et al.. (2022b) made advancements by improving the sample complexity with respect to the planing horizon H. However, their result had an additional dependence on the dimension d of the parameter space, whereas in linear function approximation, the dependence typically on Vd. Recently, a sequence of works focus on proposing statistically optimal and practical algorithms under single concentrability assumption. Ozdaglar et al.] (2023) provided a new reformulation of progaamrrgg..mmng.... [Rasiidinejad et al. (2022) used the augmented Lagrangian method and proved augmented Lagrangian is enough for statistically optimal offline RL. aL..Cheng et al.
bound. [iie et al.] (202Ta) introduced the concept of Bellman-
(2022) proposed an actor-critic algorithm by formulating the offline RL problem into a Stackelberg game. However, their result is not statistically optimal and Zhu et al. (2023) improved it by combining the marginalized importance sampling framework and achieved the optimal statistical rate. We leave comparison of these works in Appendix A
3 PRELIMINARIES
In our work, we consider the inhomogeneous episodic Markov Decision Processes (MDP), which can be denoted by a tuple of M (S, A, H, (ra)# (1) In specific, S is the state space, A is the finite action space, H is the length of each episode. For each stage h E [H]. rs S A + [0, 1] is the
reward functior P and ( (s'1ss, a) is the transition probability function, which denotes the probability for state transfer to next state s' with current action a. A policy æ == {TAA) h=1 is collection of mappings Ta from a state 3 E S to the simplex of action space A. For simplicity, we denote the state-action pair as z := (s, a). For any policy and stage [II], we define the value function
V. (s) and the action-valus function Q (s, a) as the expected cumulative rewards starting at stage h, which can be denoted as follows:
()) (1(8 + +E
Σ
TW (swssTT: (sh 8, an a). VT (7, (+)),
M=++1
where 88441 Pac-|ss,, ax)) denotes the observed state at stage h'' + 1. By this definition, the value function V (+) and action-value function Q (s, a) are bounded in [0, H.. addi- tion, we define the optimal value function Vi and the optimal action-value function Q as
Whiile we study the deterministic reward functions for simplicity, it is not difficult to generalize our results stochastic reward functions.
3

---

(s) max, (s) and (s. max, Qi as. We denote the corresponding optimal policy by π². For any function V - R. we denote [I, a) = E (-Ix.a) V(s') and [Varn (s) = [P (s, a) (IP for simplicity. For any function f S x A - R, we define f(s) = max, f(s, a). For any function f: + F we define the Bellman operator Tn. as h [H] and policy -u (-1s2..) 1ra(8h: ah) + f(sn+1)) Based on this definition, for every stage have the following Bellman equation for value functions Q (s, a) and (T((s), as well as the Bellman optimality equation for optimal value functions:
[Tr (Tn;
Q7 (sh, at. [7h (sk, an). Q% (sh, ah) = [Tr (4(%, ax), where V (5) V
O. We also define the Bellman operator for second moment as
[T2, an) Exg 1 PP C.P..Clee (.1)).0).) ((ra(5). 0n) + f(sh+1)) For simplicity, we omit the sub- scripts h in the Bellman operator without causing confusion.
Offline Reinforcement Learning: In offline RL, the agent only has access to batch-dataset D { of r h E k E [K], which is collected by behavior policy J4, and the agent cannot interact with the environment. We also make the compliance assumption of the dataset:
K.H r let I'D be the joint distribution of the data Assumption 3.1. For dataset D = [(sh at, JR.h..
collecting process. We say D is compliant with underlying MDP (S, A, H, if
PD(r = r', sh41 = s ((5) a (17 (1+1))=)1) = PP (sh an) = r', sh+1 5 = 5 an =ax))
for all r' E [0, E S, h E [M] and k E [K].
This assumption is common in offline RL and has also been made in Jin al. (022bb) Zhong et al. (2022). When the dataset originates from one behavior policy, this assumption naturally holds. In this paper, we assume our dataset is generated by single behavior policy μ.. In addition, for each stage h. we denote the induced distribution of the state-action pair by d/. Given the batch dataset, the goal of offline RL is finding near-optimal policy ı that minimizes the suboptimality Vs)(s) V (s). For simplicity, and when there's no risk of confusion, we will use the shorthand notation zi. (0 a to denote the state-action pair the dataset up to stage h and episode k.
General Function Approximation: Given general function class (FA)NE(H), where each func- tion class Fú is composed of functions fa : S x A + [0, L). For simplicity, we assume L = O(H) throughout the paper. We make the following assumptions on the function class.
Assumption 3.2 (e-realizability under general function approximation). For each stage h E [H]. there exists function fx E Fy close the optimal value function such that Il Q7 0c S c.
Assumption 3.3 (e-completeness under general function approximation, Agarwal et al. 2023). We assume for each stage h E [H). and any function V S + [o, H], there exists functions fh. f2. Fr such that
max (f a) [Ts a)l S e, and max (s,, - (s.a)ESxA
(x.a)ESx.A
In this paper, for simplicity, we assume that the function class finite and denote its cardinality by A ma [. For infinite function classes, cardinality. Note that the covering number will be reduced to the cardinality when the function class finite.
use the covering number to replace the
We introduce the following definition (D² -iveerrrg))) to quantify the disparity of a given point (s, from the historical dataset D,, It is a reflection of the uncertainty of the dataset.
Definition 3.4. For a function class Fu consisting of functions fn. S x A + TR and DA = ((*) a (rrr) be(k)) as dataset that corresponds to the observations collected up stage h in the MDP, introduce the following D Divedivere:cc::
(h(z)=f((e)) D3, (2:Dao fr.f EnE[K] (an(=)))² (f1(2))) - fa(z)))² +X
sup
where (..)))) 5 x A R is weight function.
IIn this paper, we slightly abuse notation o for both f(s) and f(s.a). The context readily clarifies the intended meaning, i.c., value function or action-value function.
4

---

Remark 3.5. This definition signifies the extent to which the behavior of functions within the function class can deviate at the point 2 = (s, a), based on their difference in the historical dataset. It can be viewed as the generalization of the weighted elliptical norm ||o(s, 2) in linear case, where is the feature map and Σn is defined _KE[K] hh (s), ( o a T + XI. Similar ideas have been used to define the Generalized Eluder dimension for online RL (Gentile et al.)
2022; Agarwal et al.) 2023 Ye et al. 2023). In these works, the summation is over a sequence up to the k-th episode rather than the entire historical dataset.
Data Coverage Assumption: In offline RL, there exists discrepancy between the state-action distribution generated by the behavior policy and the distribution from the learned policy. Under this situation, the distribution shift problem can cause the learned policy to perform poorly or even fail in offline RL. In this work, we consider the following data coverage assumption to control the distribution shift.
Assumption 3.6 (Uniform Data Coverage). there exists constant 0, such that for any stage and functions fi, J2 E Fh, the following inequality holds,
Exg
[(Ji (8h, an) [2( an)) xI|Si f2ll
where the state-action pair (at stage h) (s), an)) is stochasticly generated from the induced distribution d'
Remark 3.7. Similar uniform coverage assumptions have also been considered in Wang et al. (2020a): Min al. 202T]; 1; Yin et al. (2022a); Xiong et al. (2023); Yin et al. (2022b). Among these works, Yin et al. (2022b) the most related to ours, proving an ristance-dependen regret bound under general function approximation. Here we make a comparison with their assumption. In detail, Yin et al. (2022b) considered the differentiable function class, which is defined as follows
F = (0, o(: x A
R. R.
They introduced the following coverage assumption such that for all stage h E [H), there exists constant K,
Egg
((0)),,))))000, 2 x110 02112. vol.vo,.co 02 E θ; (*) Eg Vf (fs, ol.. > kl, 00 O.
(**)
We can prove that our assumption is weaker than the first assumption (*), and we do not need the second assumption (**). This suggests that the diffcrentiable function class studied in Yin al. (2022b) is an example covered by our general function class.
In addition, in the special case of linear function class, the coverage assumption in Yin et al. 2022b)
will reduce to the following linear function coverage assumption (Wang et al. 2020a Min et al. 2
Yin al. 2022a Xiong al. 2023).
Amin (Eay (Ø(s ()@(s, a)
0, Vh [4].
Therefore, our assumption is also weaker than the linear function coverage assumption when dealing with the linear function class. Due to space limitations, we defer detailed comparison to Appendix B
Remark 3.8. Many works such as Uehara & Sun (2021): Xie et al. (2021a); Cheng et al. (0022); Ozdaglar et al. Rashidijaad et al., (202)); Zhu al. (002) adopted a weaker partial coverage assumption than ours, where the f.x norm on the right hand is replaced with the expectation over distribution corresponding
single policy, typically the optimal one. Their assumption, however, generally confines their results to worst-case scenarios. It is unclear if we can still prove the instance- dependent regret under their assumption. We will explore it in the future.
4 ALGORITHM
In this section, we provide a comprehensive and detailed description of our algorithm (PNLSVI), as displayed in Algorithm | In the sequel, we introduce the key ideas of the proposed algorithm.
4.1 PESSIMISTIC VALUE ITERATION BASED PLANNING
Our algorithm operates in two distinct phases, the Variance Estimate Phase and the Pessimistic Planning Phase. At the beginning the algorithm, the dataset is divided into two independent disjoint subsets D, D with equal size K, and each is assigned specific phase.
5

---

Algorithm Pessimistic Nonlinear Least-Squares Value Iteration (PNLSVI)
Require: Input confidence parameters 3h. 3n and e > O.
I: Initialize: Split the input dataset into D = {sh o K.KK D = {5% ah AAkkh= A
K.
Set the
value function (+))(+) /++1())=0
/ /CConstruciin the variance estimator
3: for stage h = H,..., 1 do
4: fh argmin Mer Ene(K]
( att Fh Fh+i (5++()))1))
argmin M..F. EKE[K] Ih (5h - (rh Inti((t++)))
5:
6: Calculate a bonus function bn with confidence parameter Br.
7: Jn (ʃh by - (0
8: Construct the variance estimator
(s. = max (, (fx(s,a)33 o (VVlostN-iiH VKK
VKx
9: end for
10: / //Pessimistic value iteration based planning
11: for stage h = ,,,...,1e, do
12:
Fr f EnE(K] (e
(Fa(S) az) - Fntz(sh+z))
Calculate a bonus function by with bonus parameter 3n:
14: fn + {5r bn -0
(-ss) argmax, as)
16: end for
Output: मे )
The basic framework of our algorithm follows the pessimistic value iteration, which was initially introduced by Jin et (2021b). In details, for each stage [H]. we construct the estimator value function fn. by solving the following variance-weighted ridge regression (Line 13
Fr argmiin J.EJ RE[K]
( at) (fulsh at) r (
where 0), the estimated variance and will be discussed Section 4.2 In Line 14 we subtract the confidence bonus function b2 from the estimator value function fr to construct the pessimistic value function ST. With the help of the confidence bonus function bn. the pessimistic value function fr. is almost lower bound for the optimal value function fū The details of the bonus function will be discussed in Section 4
Based on the pessimistic value function fr for horizon h, we recursively perform the value iteration for the horizon h - 1. Finally, we use the pessimistic value function Jn to do planning and output the greedy policy with respect to the pessimistic value function fr. (Lines 15 17 4.2 VARIANCE ESTIMATOR
In this phase, provide estimator for the variance ōn in the weighted ridge regression. We construct this variance estimator with D, thus independent of D. Using a larger bonus function by we conduct pessimistic value iteration process similar that discussed Section 4. and obtain more crude estimated value function ( JeemH According to the definition Bellman operators T and T2, the variance of the function fa+1 for each state-action pair (s, can be denoted by
[Var. a) (72nih+11(s00) a) - (17,
Therefore, we need estimate the first-order and second-order moments for JA+1- We perform nonlinear least-squares regression separately for each of these moments. Specifically, in Line 4 we conduct regression to estimate the first-order moment.
fn = argmin
Σ fAEJn KE(K
(In(S), at: - Intz(ohrr))

---

In Line we perform regression for estimating the second-order moment.
(+h fl+z((h+1) 2
Oh argmin
Σ ghE KE[K]
ga a.t)
In this phase, set the variance function to 1 for each state-action pair (s, a). Combing these two regression results and subtracting some perturbing terms (We will discuss in Section 6.1). we create a pessimistic estimator for the variance function (Lines to g
4.3 NONLINEAR BONUS FUNCTION
As we discuss in Sections and 4.2 following Wang et al. (2020b); Kong et al. (2021) Agarwal al. (2023), we introduce a bonus function. This function is designed to account for the functional uncertainty, enabling us to develop a pessimistic estimate of the value function. Ideally, we hope to choose bn (++ = 3 Dy.( Dri o.). where 3n, is the confidence parameter and Dy, (,, DAs o.) defined in Definition 3.4 However, the D2 Di-divergence composes a complex function class, and its calculation involves solving complex optimization problem. To address this issue, following Agarwal et al. 2023). we assume there exists a function class W with cardinally [W] Ni. and approximate the Di-divergence well. For the parameters BR, À O, error parameter 2 taking a variance function o% (..)).) : S A + R and fn E Fn as input, we can get bonus function bn(t,") E W satisfying the following properties:
(zx) 2 max {Ifu(en) - f. E Fi: ExE(K]
$ (Ba)) for any 2n E S A.
by (=x) C. (Dr, (z; (3,)² + + cBh) for all 2n E A with constant 0 < < co.
We can implement the function class W with bounded No, by extending the online subsampling framework presented in Wang et al. (2020b); Kong et al. (2021) to an offline dataset. Additionally, using Algorithm 1 of Kong et al. (2021), we can calculate the bonus function with finite calls of the oracle for solving the variance-weighted ridge regression problem. We leave detailed discussion to Appendix
MAIN RESULTS
In this section, we prove an instance-dependent regret bound of Algorithm 1
Theorem 5.1. Under Assumption 3.6. for K 2 H (oR(H-No)HH*
if we set the parameters Mi 12,1 = Õ Vlg(( H2) and 84 = ÖVVlog N) in Algorithm then with probability at least 1 1- 8, for any state E S, we have
x²
(
S Ō( O(ylogg)i Ex DD,, (Eni Da;
)1. =
where (V.Vit1l(s max (Vara (s, a)} is the truncated conditional variance.
This theorem establishes an upper bound for the suboptimality of our policy The bound depends on the expected uncertainty, which is characterized by the weighted D D*-divergence along the trajectory, marking itself as an instance-dependent result. It's noteworthy that both the trajectory and the weight function are based on the optimal policy and the optimal value function, respectively. This bound necessitates that the dataset size K is sufficiently large. Furthermore, all parameters are determined solely by the complexity of the function class, the horizon length H, and the data coverage assumption constant k regardless of the dataset's composition.
Remark 5.2. In Theorem 5.1, the dependence on the cardinality of the function class scales as Ö(vlogNV) which is better than that in Yin et al. (2022b). which scales as Öllg A'). This improved dependence is due to the reference-advantage decomposition (discussed in Section 6.2). which avoids the unnecessary covering argument. Thus we resolve the open problem raised by Yin et al. (2022b), ie., how to achieve the OVooo N) dependence.
Remark 5.3. When specialized to linear MDPs (Jin et al. 2020), the following function class
F = ( 0.)) 0, E Rd ||0 la S B,) for any h E [H].
suffices and satisfies the completeness assumption (Assumption 3.3 Let J (e) be an e-net of the linear function class Flin. with log (c)] = Ö(d). The dependency of the function class will reduce to O(ylogN) = Ō(v)). For linear function class, we can prove the following inequality: D (e Das (V, V < [|
7

---

where = ketk Φf (f)) a (VaVitill a%) + AI. Therefore, regret guarantee in Theorem 5. is reduced to
H
(o)) Ō(v)) Σ Bx [1((5) (n)ss) 1 =
which matches the lower bound proved in Xiong et al. (2023). This suggests that our algorithm is optimal for linear MDPs.
KEY TECHNIQUES
In this section, we provide an overview of the key techniques in our algorithm design and analysis. 6.1 VARIANCE ESTIMATOR WITH NONLINEAR FUNCTION CLASS
In our work, we extend the technique of variance- weighted ridge regression, first introduced in Zhou ct al. (2021) for online RL, and later used by Min et al. (2021): Yin et al. (20222 bb; Xiong et al. (2023) for offline RL with linear MDPs, general nonlinear function class F. We the following nonlinear least-squares regression to estimate the underlying value function:
Jn argmin JNEF kE[K]
(JaCOhs at) r - -
For this regression, it is crucial to obtain reliable evaluation for the variance of the estimated cumulative reward rf + fn+1($h+2) As discussed in Section 4.2 use D to construct a variance estimator independent from D. According to the definition of Bellman operators T and Tz. the variance of the function JA+1 for each state-action pair (s, a) can be denoted by
[Var,, a) = [Ta, [Tanfi+ - 110
In our algorithm, we perform nonlinear least-squares regression on D. For simplicity, we denote the empirical variance B, a) In (s, a) (Jr a)) and the difference between empirical variance B3, (s, a) and actual variance [Var Varrff++1lss a) is upper bound by
(s, a) Narr.f++166 (s. a)} a) I 1 at + (fa(s, ([Thfh+1(ss, a))
For these nonlinear function estimators, the following lemmas provide coarse concentration properties for the first and second order Bellman operators.
Lemma 6.1. For any stage h E [.f], let fn+ H be the estimated value function constructed in Algorithm Line By utilizing Assumption 3.3 there exists function f% E Fi, satisfying that
15% (zx) [T. f (x) I holds for all state-action pair (sh,ax). Then with probability at
least 1 (4HH), (.df).i holds that
EME(K] (PA(Et) Tx (BI,))
where B1,6 δ
(VoVVoooo log(N .N) and In is the estimated function for first-moment Bellman
operator (Line 4 in AalinAlgann Algorithm []
Lemma 6.2. For any stage h E [H]. let (+ H be the estimated value function constructed
in Algorithm| Line 7
By utilizing Assumption 3.33, there exists function Hh E Fi, satisfying that
1% (zx) 12. (=n) < holds for all state-action pair (sh, 0x). Then with probability at
least 1 5/ (4HH), holds that
ExE[K] (0% IN (=t))² (B2,n)²,
where 32, ( log(N .N,) H²), and Øn is the estimated function for second-moment Bellman operator (Line 5
Algorithm [
Notice that all of the previous analysis focuses on the estimated function f By leveraging an in- duction procedure similar to existing works in the linear case (Jin et al. (2221)) can control the dis- tance between the estimated function Ja+1 and the optimal value function fi+1- In details, with high
8

---

probability, for all stage E [H], the distance is upper bounded by Ō (Vlog(V .o6 KK)
This result allows to further bound the difference between \Vr,, f (s, a) and Vark//++ (s, a). 1
Therefore, the concentration properties in Lemmas enbbellll us to add some perturbation terms and construct a variance estimator, which satisfies the following property:
(a - (VVVlogge Vlog(N -N6)
(s, [V (VVi+ta((s.)).
(6.1)
VKK
where [V i a) - m1 [Var, Vis,,s a)} is the truncated conditional variance. 6.2 IEPERRECE-ADVANTEI
DECOMPOSITION
To obtain the optimal dependency on the funcction class complexity, we need to tackle the challenge of additional error from uniform concentration over the whole function class Fr. To address this problem, we utilize the so-called dfference-advantee (Xiong al., 2023) to achieve the optimal regret for offline RL with linear function approximation. We generalize this technique to nonlinear function approximation. We provide detailed insights into this approach as follows:
decomposition technique, which was used by
(8h, (n) fh41 [Th 1 an) =rh (sh an) + 1h+1((n41) [Th 11) an.
Reference uncertainty
+ f1+1(8h+1) - i (8h+1) (1p+1)-(PPh1a)) (PPhhtt1(ssn an) - PP ((5h, ax))
Advaniage uncertuinty
We decompose the Bellman error into two parts: the Reference uncertainty and the Advantage uncertainty. For the first term, the optimal value function fh++1 is fixed and not related to the pre- collected dataset, which circumvents additional uniform concentration over the whole function class and avoids any dependence on the function class complexity. For the second term, is worth noticing that the distance between the estimated function S1+1 and the optimal value function fī decreases with the speed of (1/ Kr)). Though, we still need to maintain the uniform convergence guarantee, the Advantage uncertainty is dominated by the Reference uncertainty when the number of episodes K is large enough. Such an analysis approach has been first studied in the online RL setting (Azar et al. 2017; Zhang al., [021] Hu al. 2022, He et al. 2022] Agarwal et al., 2023) and later in the offline environment by Xiong et al. (202). Previous works, such as Yin et al. (2022b), didn't ' adapt the aeference-advantage decomposition analysis their nonlinear function class, resulting in parameter space dependence that scales with d, instead of the optimal vd. By integrating these results, we can prove a variance-weighted concentration inequality for Bellman operators.
Lemma 6.3. For each stage h E [H], assuming the variance estimator ōn satisfies
(6.1) let
F.+1(..)) < H be the estimated value function constructed in Algorithm Line 14
Then with
2
probability at least 1 - 6/(4H), it holds that Σxe(k] (5.()))) (ThJ [x
< (Bx)²,
where 3n = No and Fr. is the estimated function from the weighted ridge regression (Line 12 in Algorithm D
After controlling the Bellman error, with similar argument to Jin al. (2021b), obtain the following lemma, which provides an upper bound for the regret.
Lemma 6.4 (Regret Decomposition Property). If (Trff+ll<>) - (x)
6z) holds for all stage h H and state-action pair = = (8, a) E S x A. then the suboptimality of the output policy ăt in Algorithm I can be bounded as
Vi'(s) - V (s) 2 [6, (sh, an) s1 ===s] s].
Here, the expectation Ex- is with respect to the trajectory induced by x² in the underlying MDP.
Combining the results in Lemmas 6.3 and 6.4 we have proved Theorem 5.1
CONCLUSION AND FUTURE WORK
In this paper, we present Pessimistic Nonlinear Least-Square Value Iteration (PNLSVD), an oracle- efficient algorithm for offline RL with non-linear function approximation. Our result matches the lower bound proved in Xiong et al. (2023) when specialized to linear function approximation. We notice that uniform coverage assumption can sometimes be strong in practice. In our future work, we plan to relax this assumption by devising algorithms for nonlinear function classes under a partial coverage assumption.

---

ACKNOWLEDGEMENTS
We thank the anonymous reviewers and area chair for their helpful comments. QD, HZ, JH and QG are supported in part by the National Science Foundation CAREER Award 1906169, CPS-23 231944, Amazon Research Award and the Sloan Research Fellowship. JH is also supported in part by Amazon PhD Fellowship. The views and conclusions contained this paper are those of the authors and should not be interpreted representing any funding agencies.
REFERENCES
Alekh Agarwal and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. arXiv preprint arXiv:2206.07669, 2022.
Alekh Agarwal, Yujia Jin, and Tong Zhang. Vo q I: Towards optimal regret in model-free rl with nonlinear function approximation. The Thirty Sixth Annual Conference on Learning Theory, pp. 987-1063. PMLR, 2023.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Nicolo press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge university
Jinglin Chen and Nan Jiang. Information-thheortiicc considerations in batch reinforcement learning. In International Conference on Machine Learning. pp. 1042-1051. PMLR, 2019.
Ching-An Aann--An&o Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In International Conference Machine Learning, pp. 3852-3878. PMLR, 2022.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert Schapire. On oracle-efficient pac rl with rich observations. Advances in neural information processing systems, 31, 2018.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897)44444199 2022.
Simon Du Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 2826-28262 PMLR, 2021.
Simon Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv: arXiv:1910.00
2019.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference Machine Learning, pp. 1539-1548. PMLR, 2018
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprini arXiv:22 12. 13447, 2021.
Claudio Gentile, Zhilei Wang, and Tong Zhang. Achieving minimax rates in pool-based batch active learning. International Conference on Machine Learning, pp. 7367. PMLR, 2022.
Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 20/7 IEEE international conference on robotics and automation (ICRA), pp. 3389-3396. IEEE, 2017.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 4171-4180. PMLR, 2021.
10

---

Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.061.33 2022.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference Machine Learning, pp. 8971-9019. PMLR, 2022.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficien algorithms. Advances neural information processing systems, 1111340--13488, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021b.
Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.07200 2021.
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference Machine Learning, pp. 1915-1924. PMLR, 2017.
Sergey Levine, Peter Pastor, Alex Krizhevsky, Julian Ibarz, and Deirdre Quillen. Learning hand- eye coordination for robotic grasping with deep learning and large-scale data collection. The International journal of robotics research, 3744-5):221 -366, 2018.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05225. 2022.
Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 34: 7598-7610, 2021.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Thanh Nguyen- Tanen and Raman Arora. Viper: Provably efficient algorithm for offline rl with neural function approximation. In The Eleventh International Conference on Learning Representations, 2023.
Thanh Nguyen- Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement learning with linear function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 9310-9318, 2023.
Asuman E. Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. Revisiting the linear- programming framework for offline with general function approximation. International Conference Machine Learning, pp. 26769-26791. PMLR, 2023.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation Iearning: A tale of pessimism. Advances in Neural Information Processing Systems, 34: 15:11100-111711 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao. Optimal conserva- tive offline rl with general function approximation via augmented lagrangian. In The Eleventh International Conference Learning Representations, 2022.
11

---

Julian Schrittwiserr, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):644-699 2020.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. In International Conference Machine Learning, pp. 19967-20025. PMLR, 2022.
David Silver, Julian Schritwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)3354-33 359, 2017.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements model-free approaches. In Conference on learning theory, pp. 2898-2933 PMLR, 2019.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference on Learning Representations, 2021.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint 0rXiv:2010.11890 2020a.
Ruosong Wang. Russ Salakhutdinov. and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-611 133661336,,, 2020b.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy, Optimism in rein- forcement learning with generalized linear function approximation. International Conference on Learning Representations, 2020c.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with renearlyreallzzblle optimal action-value functions. In Algorithmic Learning Theory, pp. 1237-1264. PMLR, 2021.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Cellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27407, 2021b
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. In International Conference Learning Representations (ICLR), 2023.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang. Cormuption-rouus algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. In International Conference on Machine Learning, pp. 39834-39863. PMLR, 2023.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065-4078, 2021.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.00 055804 2022a.
12

---

Ming Yin, Mengdi Wang, and Yu- Yu-Xiang Wang. Offline reinforcement learning with differentiable function upproximation is provably efficient. In The Eleventh International Conference on Learning Representations, 2022b.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pp. 1954-1964, PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning, pp. 10978-10989, PMLR, 2020b.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34:13626 13640, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pp. 2730-222220 2775. PMLR, 2022.
Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp- 4528 4531. PMLR, 2021.
Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning, pp. 27117-27142. PMLR, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532-4576. PMLR, 2021.
Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. arXiv preprint arXiv:2301.12714 2023.
13

---

A COMPARISON OF OFFLINE RL ALGORITHMS
In this section, make comparison between different offline RL algorithms, concerning their algorithm type, function approximation class, data coverage assumption. used oracles, and regret type. In the upper part the algorithms with worst-case regret, while in the lower part those with instance-dependent regret.
Table I: Comparison of offline RL algorithms in terms of algorithm type, function classes, data coverage assumption, types of oracle and regret-type.
Algorithm
Algorithm Type
Function
Data Coverage
Types of Oracle
Regret Type
Classes
Xic et 2021a
Bellman- consistent Pessimism MLE
General
Partial
Optimization on Policy and Function Class Optimization on Policy and Hypothesis Class Optimization on Policy and
Worst-case
CPPO-TV
General
Partial
Worst-case
Uehara & Sun [2021
CORAL
Augmented Lagrangian with MIS
General
Partial
Worst-case
Rashidinejad ad ct al. (202)
Function Class
Relormu lnted
Lineur Program
General
Partial
Lineur Programming
Worst-case
Ozdaglar et (2023
ATAC C hhnng
Actor Critic
General
Partial
No-regret Policy Optimization and Optimizaticn on the Function Class
Worst-case
ct 2022
A-Crah /hu et al. 2023
Actor Critic
General
Partial
No-regret Policy Optimization and Optimization the Function Class
Worst-case
LinPEVI-ADV+ Xiong
LSVI-type
Linear
Uniform
Instance- dependent
2023
PRO Yun al.
LSVI-type
Differentible
Uniform
Gradient Oracle and Optimization on the Function Class
Instance- dependent
20226
PNI.SV (Our
LSVI-type
General
Uniform
Regression
Instance- dependent
work)
Oracle
B COMPARISON OF DATA COVERAGE ASSUMPTIONS
In Yin et al. (2022b), they studied the general differentiable function class, where the function class can be denoted by
F (() R
In this definition, is compact subset, and Φ( : : A + T C R is a feature map. The parameter space θ is compact subset + Rd The function Rd x Rm R satisfies the following smoothness conditions:
For any vector & E f(e, is third-time differentiable with respect to the parameter
Functions f, f 0g.o.. o. are jointly continuous for (0, Φ).
Under this definition, Yin et al. 2022b) introduce the following coverage assumption (Assumption 2.3) such that for all stage H.. there exists a constant K.
E
(f1) a)) f(O,. 6(x a)) 2 * xI10; - 02112, v0,. Og e θ; (+)
ExL Vf o(
a)) ((.
a)) kI, 40 (***))
It is worth noting that assumption 3.6 weaker than this assumption. For any compact sets θ v and continuous function f. there always exist a constant Knn such that ʃ is no-Lipschitz with respect the parameter O.i.e:
|f Φ) f(02, x1) S 0 0 v0, O2 O w.
14

---

Therefore, the coverage assumption in Yin et al.
(002b) implies that
Edg [1(01, f(0.. - o(.-)))
x
021
(s(01, ((2,)))))(0020))00000 (2 a)))²
sup (x,
Our assumption can be reduced to their first assumption (*). We do not need the second assumption (**).
In addition, for the linear function class, the coverage assumption in Yin al.
(022b) will reduce to
the following linear function coverage assumption (Wang et al. 2020a Min et al. 2021 Yin et al.
2022a Xiong et al., 2023).
min (E ())(2,))()))))))) a) = > 0, wh E [H].
Therefore, our assumption is also weaker than the linear function coverage assumption when dealing with the linear function class.
C DISCUSSION ON THE CALCULATION OF THE BONUS FUNCTION
To obtain the bonus function satisfying the required properties, we need to consider the constraint optimization problem
(n(E (a FF
(f((1))) 12(=1)² (ān a²))²
max
S (Ba)²
(C.1)
KE[R]
We utilize the online subsampling framework presented in Wang (2020b): Kong et al. 2021) to an offline dataset. Additionally, we generalize the idea of Kong et al. (221) to the weighted problem. Using the shorthand expression
(f(z1))²
D.
(ān(s, )²)
kE[K]
we aim to estimate the solution of the following constraint optimization problem.
min [1/i - Sallon., + "h 2 f2(3,a) -2
(C.2)
f..f2
Algorithm 2 Binary Search
Input: Dataset Dj, { a 1 objective = (s, a), 9r. precision
2: G + F4 - Fn
3: Define R(g, w) == 11911...... + (g(s,a) 2(I 1)) Vg eg
4: wr + 0, WH + (a/ 1))
5: IL + 0, f-
6: Iи + argmingeg R(g, WH). ). 2H + gn(ss
7: A + +a +1
8: while |2и 11 > and |ml 11l > A do
9: w + (wH + /2
g -arggiiinge geg Rig, d), 0(s,a)
11: ir |[ Dn.D > 31 then
12:
WH & 2H +
13: else
14:
WL <- w, + Σ
end if
16:
end while
Output: 2/
The binary search algorithm is similar to Kong et al. (2021). which utilizes the oracle for variance- weighted ridge regression Lines 6 and [0 reduces the computational complexity of the constrained optimization problem given by (C.I). limiting it to a finite number of calls to the regression oracle. If the function class Fr convex, the binary search algorithm can solve the optimization problem (C.I) up precision of with ((lo((//a) calls of the regression oracle. We summarize the result in the following theorem. F, is not convex, the method of Krishnamurthy al. (2017) can solve the problem with O(1/a:) calls of the regression oracle.
15

---

Theorem C.1. Assume the optimal solution of the optimization problem C..1 is g" f f and the function class Fh. is convex and closed under pointwise convergence, then Algorithm terminate after (log([//a) calls of the regression oracle and the returned values satisfy
F 9 (8,a)] S a.
Fn Fi also convex. We then follow the proof of Proof of Theorem C.I Easy see Theorem of Foster et al. (2018).
To see the solution of optimization problem recall the definition of the D -ivdivereence
C.I satisfies the condition of the bonus function,
- f
D2 (z; 02)
sup h.JzETn EKE[K] ( (f1(z)) - f2(2,))
Therefore, for any f1, f2 E Fn satisfying EnE(K] (an(et)) (fi(z)) f2(x)))² s (B)), ) we have
(Ji(z)) - 12(zn)] & Dr (2; O) V (3,)² +
D ANALYSIS OF THE VARIANCE ESTIMATOR
In this section, our main objective is to prove that our variance estimators are close to the truncated variance of the optimal value function [Va i a). The following lemmas are helpful in the proof
of Lemma D.4 To start with, we need an upper bound the D -i-viveree for a large dataset.
Lemma D.I. Let Dj, be the dataset satisfying Assumption
3.6 When the size of data satisfies
K
log with probability at least 1 8, for each state-action pair 2, we have x
Dy. (2, - KR
Lemma 6. and Lemma 6.2 show the confidence radius for the first and second-order Bellman error, which is essential in our proof. Here we restate them with more accurate parameter choices.
Lemma D.2 (Restatement of Lemma 6.1 For any stage h E [f]] let Fr H be the estimated value function constructed in Algorithm Line 7 By utilizing Assumption 3.3 there exists function
Ph E Fr. satisfying that [ (2x) f (2()) ] S e holds for all state-action pair Nn. (Sh, an). Then with probability least 1 8/ (4H). ). holds that
Σ kE[K]
(R =x S (Br,)),
where B1,5 Ōō log(N NN)HH), and In is the estimated function for first-moment Bellman operator (Line A in Algorithm T
Lemma D.3 (Restatement of Lemma 6.1 For any stage h E [H] let (.41(.)) H be the estimated
value function constructed in Algorithm Line 7 By utilizing Assumption 3.3 there exists function
g. E Fr. satisfying that 0 (2+) [T2 fr ( ) < c holds for all state-action pair 21. (8h, ax). Then with probability least 6/(HH), holds that
Σ kE|K]
(gh (= - (= & (B2,))2
where 32,4
Õlv log(N .N.)H 22) and ğn is the estimated function for second-moment Bellman operator (Line 5 Algorithm D..
Recall the definition of the variance estimator.
Fn argmin Σ
(Jh(S), at) - -hot(sshi))
fnEFs
kE[K]
Øh argmin E
(n at:) (Ft: t Tntz((h41))
kE[K]
16

---

The variance estimator is defined as:
(s. == max {
(ao(ssaa-(fn(ss.0e ((voo( -N)HH
VKr
We can prove the following lemma:
Lemma D.4. with probability least 5/2, for any h E [H], the variance estimator designed above satisfies:
(VVR+al(s..)- -ō VVog(NVNN)))
(s, S Ma (iVitll(s.a).
VKE
Proof of Lemma D.4 We write (s, Jn (f((s,a)² We first bound the difference between BB, a) and (Vrr
a). By the definition of conditional variance, we have
(s, a) [Var a) s (s. a) [Tam ad| (F) ((),
where we use our definition of Bellman operators. By Assumption 3.3 there exists f/ E Fn. Th E Fri such that for all (s
(1, a) - [T. a) Se (s. a) -
(D.1)
a) S.
(D.2)
Then by Lemma D.2 with probability at least 1 - 6/(4H²²) the following inequality holds
Σ
- pk())) 2 < (B1.))²
(D.3)
KE(K]
Similarly, for the second-order term, using Lemma D.3 with probability at least 1 5/(4H2), the following inequality holds
Σ (gx( - Th (=h)) < (B2,))² REJK]
(D.4)
After taking a union bound, with probability at least 1- (2H), D.3 and D.4 hold for all h E [H] simultaneously. Consequently, we focus on this high probability event and prove that
(s,8, a) - -1T2, a) + (Ja a))²
Set a)) (s, a)l + O(H) [[F((s,)) F a) +E
Fa
O(H) .et (n) 0 as)
(gn - (= X
EKE[K] (zt) - 3h (=h)))
+
KE[K]
Fn a) - (s.(s.))
+O(H)
Σ ( - }²)))))² +
Σ EKE(K] (Fn(2)) - FA. (=t))²
+
KE[K]
(gn(s, (),
SO(H)
V (B2,n)2 +
ELEIKI (gn( Zh (=h)) +
(s, a) (s,
+O(H)
EKETKT (Fn())) - Ph. (=t))² + (BI,))++ +1
< Ö(v Tog(N N.)HH9) Dr, (z, 1).11) VVog(WV .NHHH2
VKK
17

---

where the first inequality holds due to the completeness assumption. The second inequality holds due to (D3) and (D.4). The third inequality holds due to Definition 3.4 Lemma D.I Therefore, we have
The last inequality holds due to
Vlog(N ( N2
B& (8. a) - \arna [Vara (atn),t1((ss))) =o
(D.5)
VKx
To further bound the difference between [Varn/n+1]] (s, a) and [Var Vi a), we prove ||
Vh+ lo <ō
Vlo(VV-N .Nijes
by induction.
VKK
At horizon H + 1, Fu+1= VH+1 0, the inequality holds naturally, At horizon H, we have
QH(s, a)
[TH Vi+ i
(Tufu+il(s,a)
2 fu(s, a) [[nff=+i((so)) (s(
2 Sn(ssa) (e+ --+(((())))[((((d))) [n((,
2 an( bs)(s, -
= fs(
where the first inequality holds due to the triangle inequality. The second inequality holds due to (D.I). The third inequality holds due to the property of the bonus function by and (D.3). The last equality holds due to our definition of fH in Algorithm Line Therefore, VH)(s) (s) for all E S.
We denote the policy derived from Fn by H i.c R (5) = argmax, (s a) and then we have
vH(() FH(s) (s,) (,
(s, (7 (-1s) - (=(sss))
I -
<[TnVä+il(s.) - fs( ) by ( (-1ss)
([Tufu+i(ss..) (s. (s)
+ ((TuVH# (1.,
(8, :), TH ( a)) zō Vlog(N No.
VKn
where the first inequality holds because the policy H takes the action which maximizes Ju- The second inequality holds due to (D.I) and (D.3). For the last incquality, we use the choice of by such that for all E S A with constant 0 0<C
C' <
(2(2) C. (D (2; (2;D); ((Bx)* +
Therefore, we have max, brr(2) S δ [Voo(N-N.)HH ((Voog(N-NN)))
which uses Lemma D.1 and Byr
VRK
Viog(--No)9I Next, we prove by induction. Let R₁ Ō
(H - h 1). We define the induction
VKR
assumption as follows: Suppose with the probability of 5R+1, the event Ea+1 = {0 S Vi+t((s) fh+1(s) RR+1} holds. Then want prove that with the probability of 1 8n (6,, will be determined later), the event &, = (0 < - < R } holds.
Conditioned on the event Ea+1, using similar argument to stage H, we have
(s, = [Tx [T
[Tr
18

---

2 fils, a) - [Tntn+i((s,a) a)
2 fa(ss a) - (c+ (c f((s,a))
-
2 [n(s, a) - (s -E
(s.
where the first inequality holds due to En41- The second inequality holds due to the triangle inequality. The third inequality holds due to (D.I). The fourth inequality holds due to the property of the bonus function by, and (D3). The last equality holds due to our definition of fr. in Algorithm Line Therefore, V (-) 2 (-).
On the other hand, similar to the case at horizon H, we denote the policy derived from Jn by The i.e. (s) = argmax, (s,,, a). Taking union bound over the event in Lemma D.1 and En41, we have with probability at least 5ut1 5/(2H²),
Vi (8) ]a(s) (Q%(s,) :) (
(,,
(-1s))
S (8,) - (8, (1(()))) ([TVVi+il(s) - [n((, ) + (f) t ((TnFatil(ss.)) fs,,, + (s a), (11s))
+ (1TA VITh - [Th )), ( (-18)) +
S 2(bb ), (-,))))))))))) + 2e + Ra+1
Vlog(N -N6H
s Ra+1 +
VK
Vlog(N NN6 VKw
(H 1H) = Ra,
where the first inequality holds because the policy # takes the action which maximizes fH The second inequality holds due to (D.I) and (D.3). The third inequality holds due to Lemma D. The last inequality holds due to the induction assumption. Therefore, we can choose 8, (H h 12H/ < 8/2H. Taking a union bound over all h E [H]. we prove that with probability at least 1 - 6/2, the following inequality holds for all h E [H] simultaneously
.N.JH2 [Vog(W VI
0 S Vi+i()) (
(D.6)
VKr
Conditioned on this event, we can further bound the difference between [VarnJh+11(s, a) and VVar,Vii (s).).
Var, VarnJn+1](ss - Varn V Vot
$ [PhNi+ (s, [PA V (s, a) + (PWWar1))0aa) [ ((Priin)((sa))
1 (HH)) | - Fn+1
xō Vlog(N :3
(D.7)
VKK
where the first inequality holds due to the triangle inequality. The second inequality holds due to Vitta Jh & H. The last inequality holds due to (D.6). Therefore, for any (s, E E x A, we have
Ba a) - Vaar, VoL ((s, a)l < (s a) - VV
+ [Varn - [Var, (
19

---

Vlog(N .N6)
<ō
VKK
Thus, for any (s,a) E S A, we have
VVlg(V .N3)
Ba(s,a)- -
Vara (i))(s,,))
VKK
where the first inequality holds due to the triangle inequality. The second inequality holds due to (D.5) and (D.7). Finally, using the fact that the function max(1, } increasing and nonexpansive, we complete the proof of Lemma D.4, which is
VVog(N NN6)
(VVR+2l(s,a)-
S (.) S (WVi)al(s..).
VKK
E PROOF OF LEMMAS IN SECTION D
E.1 PROOF OF LEMMA D.1
Proof of Lemma From the definition of D divergence (Definition 3.4). we have (Ji(z) - S2())²
D3, (2;
sup
(E.1)
fi.feEF,
ΣnE(K] (fi(z)) f2(x))) + X
By the Hoeffding's ss inequality (Lemma
I.3 with probability at least (N),), we have
Σ (fi(2h) f2(= 2 KE (fi(#n) - fe(=n)) 2 22/2K log (N2 /8) llfi - fella.
KE[K]
Hence, after taking union bound, we have with probability at least - 6, for all f1, f2 E Fi.
Σ (fi(=)) fa(z1)))² z KKn,h [fi(z)) f2(zn)) 2 log(N²/8)) Ilfi f2ll3
kE(K]
K kl fel1z. - 2222222lgg log(N²/5) II - fell
(E.2)
where the second inequality holds due to Assumption 3.6 Substituting
E.2 into E. when the
size of dataset K 2 á
log.V x²
we have
(2())))(222) =
D3, (z; 1n;1)
sup f..EEf
JK
kl]fi
f2 +X
KK
E.2 PROOF OF LEMMA D.2
In the proof of Lemma D.2, we need to prove the following concentration inequality,
K.H Lemma E.1. Based on the dataset D' = { a/, F we define the filtration
H = a (sl. F1, sh...., Th. 8 87 aद, 77, 52 ... ph. 5 #4tii.... st af. st. 5h+))
.
For any fixed functions f.f S + [0, H) we make the following definitions:
T = (x - (st a DK = 1 (f(zt) (Tt))())))
Then with probability at least 1 1-8/(AH2NN2N3) the following inequality holds,
ExEIgg (f(2)) - [T+))
Σ
D (24H + 5))
2
KE[K]
where i(8) / 22g (N- H2 log 1K) log (2L122)
20

---

Proof of Lemma D.2 Let (31,a)2 (48H² + (0) + H6 We define the event Ei,
[EEEKK) (=h( - ) > (31,))) j. We have the following inequality:
Σ - T2
ke(k]
Σ
(rh + + 1 - -((E)))))))) + (In(ET)- - r [hhn( -
kE[K]
Σ [E[K]
Fh + Fr+t (
Σ
(Fu(2h) - -rh Sak-Fneee -Fat((8ht2))
kE[K]
(1k + 1n+1(51+2) -R((t)))))) (Ju(2t) -rt - -
2
kE[K]
S 2 Σ
( + 1 Ph
kE[K]
2 Σ
(p) + Fn+z - f2t) (fu(Et) -rt Fnoz(sh+t))
kE(K]
2 Σ
F + Tn+2 (( (Jh( P,(t)t),
(F.3)
kE[K]
where the first inequality holds due to our choice of frs i.c,,
Σ (InCK) ah) - th Inta(shttt)
fr argmin EREFF
RE(K)
Next, we will use Lemma
E.1
For any fixed h, let f = fr E Fr. f fn-1 {f -ho
where f = fn - bn Fn.
W. Following the construction in Lemma E.1
we define
T = F% + ((5 E [rt + ('hh
and
(f( (T
Due to the result of Lemma E.T taking a union bound on the function class, with probability at least 1 2/HH2,), the following inequality holds,
DMU.J' (24H + + ExEIKI (J(E)) - (+t))
(E.4)
2
K
Therefore, with probability at least 1 5/(4H²), we have
Σ
( + ( -, )(())) -M
RE(R]
2 Σ
(FÂ Fh+1(5h+1) (Th - (fh - (h()
kE(K]
+ Σ
(Tntf)))(*))))) - P(()))) (fa(Et) Fa(tt)
(E.5)
KE[K]
2 Σ
(PR (3) [T (Tnt++ (Ta(+t) - (i))))) + #4KHe
kE[K]
< (24HH +5)((1) + 4KKH+ + ExE(K] (Fa(E)) - (T+F
(E.6)
EMEKK] (PA(E)) - Fr. (zt))²
< (24H² +)) + 8KL++
2
21

---

EnEma (F((E)) PM (E
(3 2
+
(E.7)
where the first and third inequalities hold because the completeness assumption. The second inequality holds due to E.4). The last equality holds due to the choice of
1 22(2222 + 5))²(6) + 16K = Ō .N))H)
However, conditioned on the event & we have
Fh + Fa+z(shiti) -h(th) (fa(et)-FAAtt) - FA(E
2
KE[K]
Σ
(Ph(E Fa(Ett)²
kE|K]
(3i,a)² EkEjKi (Fh(#t) - )
2
2
where the first inequality holds due contradictory with (E7). Thus, we have P| S 6/(4113) and complete the proof of Lemma
The second inequality holds due & This is
D.2
E.3 PROOF OF LEMMA D.3
To prove this lemma, need lemma similar Lemma E.1
Lemma E.2. On dataset D' = ( ag pk p
K.H h. we define the filtration
h = (st als),aj,r. F1. s2.............. ................................ . ............... $) # o.
Pi ; st rt,
The 5k sh+1).
For any fixed function f S [0, HJ, we make the following definitions:
Th('') == (Fi 1) [P +' (5h at DLL, = - (f(=t) - (T=))"
Then with probability at least 1 8/(AH2 the following inequality holds,
+ EnepK] (S(#)) [T2, ) 2
Σ KEAK]
2
where 1'(6) V 4 log (1
Proof of Lemma D.3 Let (32,n)2 (4011 (8) 16K Le. We define the event Eg,
EkE[K] (gh (zt) (xt))) (B2,)) We can prove the following inequality:
Σ (oh( gn (=h))²
kE(K]
Σ
[(Th + ( (( (gn(2t) (Fh: + Jo- (xx+)))))))
KE[R]
= Σ
(rh + -
Σ (n()))))) - (rh + (o+z(
KE[K]
KE[K]
+2 2 Σ
(FX + Fh+1 -(((t)))))))))))
(an(E))
(Fk + F
kE[K]
2 Σ
(Fh th+1 -th()t)
KE(K] K]
22

---

+2 Σ (Fh + Fh+z(sh+1)) sh(())) (on(E)) - (Fh + Fh+z(sh+1))))
kE[K]
2 Σ
(rh + I
gh (=x) (gn(2)) - (h()))
(E.8)
RE(K]
where the first inequality holds due our choice of gh, i.e.
9h
argmin
Σ
(5h ah) (Fhi + Fn+z(5h+1))
E
KE(K]
Next, we will use Lemma
E.2
For any fixed h, let f = In E Fr. f = fitt = {f -h4]-
where f = fh- bn E Fr.
W. Following the construction in Lemma E.2
we define
nh [5" = (rx + ())++ - [Pa + [') (s%,
and D f = 27 (Ta,,
Due to the result of Lemma E.2 taking a union bound on the function, with probability at least 1 ) the following inequality holds,
DIIF. fl (20H²* + 5))(6) + ERE,K) (f(E)) - [f ((+)))
Σ
(E.9)
2
KE[K]
Therefore, with probability at least 1 -8/(41(4)))))) we have
2 Σ
( + - (gn(2 - (z+))
KE[K]
= 2 Σ
(r* + ( (Tani++1) (gn - 5h (=t)
kE[K]
+2 Σ
(Ten - kh()))) (g - gh (2)))
KE[K]
2 Σ
( Fn+1 1T (on (Eh) Th (Et)) + 4KLL
kE(K]
< (20H +5) + 4KLE + EKE(K) (Im(zt) [Te.n
< (20/1 + ()) +8KLE + EKEIK (gh (2h)
gn (=
2
(Be,,) 2 + ΣNE(K] K] (xh) - In (2
(E.
2
where the first and third inequalities hold due to the Bellman completeness assumption. The second inequality holds due E.9). The last inequality holds due to the choice of
3 (40H* + 10) 16KL = Ö(Vlog(N .NH.
However, conditioned on the event εg,,, we have
2 Σ
(Fh + (1
5h (xh)) (gn - (
AE [R]
(gh (=t)) Ir (
KE[K]
(3 EtEKK] (1t - In (
2
2
where the first inequality holds due to E.8). The last inequality holds due εg, It is contradictory with 10. Thus, we have P(E 6/(4))) and complete the proof of Lemma D.3
23

---

F PROOF OF THEOREM 5.1
In this section, prove Theorem The proof idea is similar to that of Section D To start with, we prove that our data coverage assumption (Assumption 3.6) can lead to an upper bound of the weighted Di-divergence for large dataset.
Lemma F.1. Let D/, be a dataset satisfying Assumption
3.6 When the size of data set satisfies
K
0
No
Th S H, with probability at least 6, for each state-action pair 2, we have
(
H
Dy, Dn, Ō
VKK
With Lemma D.4 we can prove a variance-weighted version of concentration inequality.
Lemma F.2 (Restatement of Lemma 6.3 Suppose the variance function ōn satisfies the inequality
in Lemma D.4, at stage E [H]. the estimated value function fay1 in Algorithm is bounded
by H. According Assumption 3.3 there exists some function fh Fn. such that (fa(
[TT]n+1]==)] < for all žΛ (sh, un). Then with probability at least 6/2, the following inequality holds for all stage h E [H] simultaneously.
Σ kE[K]
(+)(3)) (fa(et)- Fn(ctt) S (Bh)²
With these lemmas, we can start the proof of Theorem 5.1
Proof of Theorem 5.1 For any state-action pair 2 (s,a) S x A, have
[T)]+ ]n(=){ s [Th Fa(z) [h(()) Fn())
br
where bound I with the Bellman completeness assumption. For the second term, the property of the bonus function and Lemma F.2 Using Lemma [.2] we have
Vi((s) - (T(()) (s) 2 E [br (n)) 81 = 2
H
<
B
(zn, (3x)2 +
81 + 2cH
h
< Ō
@Ö(Viop (Vog.N
Ex [Drn (Zh; Dn:
81 =
h=1
H
s δ [Vog.N] N)
Σ
B DDx, (zni Dai V vi = =8]
h=1
where the first inequality holds due to Lemma
1.2
The second inequality holds due the property of
the bonus function
by (=) < C. (Dx,, Dn; (3r)² 2 + e,Bx).
The third inequality holds due our choice 3n Ō (vlog.V.. The last inequality holds due to Lemma and the fact that D2 diverreene increasing with respect to the variance function. We complete the proof of Theorem 5.1
L
G PROOF OF THE LEMMAS IN SECTION
G.1 PROOF OF LEMMA F.1
Proof of Lemma F. From the definition of D divergence, we have
- f2()))
D3 (z; Da; R.)
sup ΣLE[K] (f (Ji -2((z))) +
(G.1)
24

---

By the Hoeffding's inequality (Lemma L.3 with probability at least 5/(N2)
Σ
(fi(zh) f=(=/)) KE [(fi(*)) - fa(2))) -2 log(log(N')) /6) 1lf - f2llio.
kE[K]
Hence, after taking a union bound, we have with probability at least - 6, for all f1, E Fr.
Σ
(Fi(#)) - =2(=)))²
(on(=)))²
kE[K]
H (KEpph [(f((z)) f2(zx)) - 2K log(N2/8)
Ilfr f2ll23
K [K-lllfi fall' -2 2K log(2//) Il.i -falle)
(G.2)
H²
where the last inequality holds due to Assumption 3.6
Substituting
G.2 into G.
when K
>
Nog.N
we have
(f) - Ō
H2
Dz, (2;Dnio)))))
2 sup f..E
JK xl|Si 12 +X
K
G.2 PROOF OF LEMMA F22
In this section, we assume the high probability event in Lemma Dolhsss, the following inequality holds:
(Voo(N- NN)H
W (oVita((s,o) - -
(s) S (V..s)(s..
(G.3)
VK
To prove Lemma F2 need the following lemmas.
Lemma G.1. Based on the dataset D {s a rk K.H of rī, s..... rh 2 #411 .r.......
k we define the filtration H.
ass at, ri. s2.... ......... ........... s4-11 ...
....... st any fixed function f. : -E [0, LJ. we define the following random variables:
af, rf, sh...., rh sh+1). For
.....
n = Vi+ii
[PA V V (s af
D f=] =
mh
(f(=f) f'(x))),
(6r (2
inequality holds, As the variance function 3n satisfies G.3 p. with probability at least -8/(4H223), the following
Σ KE(K]
Df 0(8)A V20(8) (0068)+300 36)
ΣLE(K] (antat))² (f(zh) - f2))))
where v6)) /2 2/2l log
Lemma G.2. Based on the dataset D - { att
2 K.H
k we define the following filtration H/
.5....,ff rh sh+1) For any fixed functions f.f S + 10, L] and l S + [0, H]. we define the following random variables
(st, at, s2, sb...., r..,, L = at r 83. ,r2, 2 ... st at, rf, sh...,,
shis'l = f'( (i+t(())+1)) - [F Vi+1)) (s),a at),
1 [....]] = = = (Gn (s(=)) - -((+h))
25

---

As the variance function 0% satisfies G.3 with probability at least 1 1 1-8 the following inequality holds,
AUUSAM +1001++2(0)) 1110 Vittilll + 2
Σ [K[
513 (0)/ log
ΣxE(K] (on(+])) (s(z)) - 2x
+ +0062 11
4
where c(8) v 3 H[N HWN.Kk/122o((111))))2100//////
With these lemmas, we can start the proof of Lemnal F22
Proof of Lemma F.2 We define the event &n = EdElKT (क(e)))² (Ih(t)) - I > (8h)e}
We have the following inequality:
(Fa(=h)- - )
(2
KE[K]
Σ
[1* Fe+r - Fn(ett) + (Fn(eh) - rh Fnin(shiti)]
(0
kE[K]
Σ KE[K]
(1h Fittlssi1))
Fn(=b)) -f((e))))) + Σ
(0(=)))2 (Faleh) - - - Fntz(shht))
(2))))
kE]K]
+ Σ
(1++1+1(5H+)) -f((())) (Fh(ch) - Finz(18it1))
kE[K]
(1) Th + Fn+z(shita) ffa(t))))))))))) )
2
(z
KE[K]
(r) In+i(sh+2) Fa(zh)) (Fa(et) - rh Fn+I(SHtt))
(022)))2
kE[K]
2
(r): (Th (s -B(l))) (Fu( Fnlett)
(G.4)
KE[K]
where the first inequality holds due to our choice of Jn in Algorithm Line 12
F
argmin Σ
(a(2)))2 (fulsh ah) - rh Fn+z(sh+1))
fEEF RE[K]
We prove this lemma by induction. At horizon H, first Lemma G.1 Let f Jn E Fu.
f' = fH E FR. We define
V/H = ( - [PnVH+1l=*t)
Ir 1' := (6 - ff'(=)))
TH
Taking a union bound over the function class, with probability at least 1 - 5/(4HH), the following inequality holds,
Σ kE[K]
- ((tt)) < (0)AA v2u(6) + 300
(6H (=+))
Σ (on(=)))² -f(t)))
)(
(G.5)
4
26

---

Then Lemma G.2
Let f fH E FH, f= fH E FH, f fu+1 0. We define:
CM = f' (6 - (+1((#++)) - [P V++1)((+#)
LF = (6 (2
f(+tt)
Taking union bound over the function class, with probability at least 1 - -8/(4H22, we have
4 2 SH shifutal (Faleh) - Fu(Eti) - ((0OVA++ v2(0)) | -V++11ll (o
KE[K]
EkE[Ki (an(z²)))
(Fu(zh) - - Fm(#))
2 (0)/
log No htr//VoogN 30(2(0)) 1
3
4
(G.6)
Combining holds:
G.5 and G.6). we have with probability at least 1 - (/((H the following inequality
(ra + (n+1((h+)) -n(())) (
(0H(2 kE[K]
(+ + - (Fn(*))-
2
(on(=
kE[R]
(Fu()))))(())))))))))))))))))))) -Fieh))F((ttt)
+ 2
(0n(22))2
kE[K]
( + - (Fa(=t)) -F((tt))F((ttt)) + L4Le
5 2
(+122
kE[K]
4 $ 3
(0)) + (2) + 30) + 4 (+ (2(0)) IIf' - Vi + 2 (
Exe(K] (o (fn(t)) Fn((21))
+ +30c2(0)1 HH4 vi+1 123 + 8KLe +
2
+ ELERK] (f (In(=t)-In(())
- Jm(=
(3n)² 2
(G.7)
where the first inequality holds due to the complete assumption. The second inequality holds due to (G.5) and (..6). The last inequality holds due to the fact fH+1 V#+1 = and our choice of
Br..e.
3n 12 ( 0(6)VA+ 220(6) + 300 + (8) + +8KL))
Ö(Vog.N)
However, conditioned on the event EH, we have
(rh + Fu4r())) - -f(t))))) (Fa(=h) fn(21)) -f
KE|K] (on(2t))²
Σ kE|K]
(on()1))² (Fulet)) - Fu(eti)²
(2 EkEIKI
(f((hh) - Fm(())))
where the first inequality holds due to G.4 with (.7). Therefore, we prove that TP En
The second inequality holds due to En. It contradicts
2 1 5/2H2.
27

---

Suppose the event Ey holds, we can prove the following result.
QH( a)
+IVE+il(ss)
2 au(s,a)
[ fl((,aa)
2 an(s,a) (<+]f((s,)-Fniit
(s)(,,a))
2 2n((sa))-b((3s bn((sa)
= fs(ssa).
where the first inequality holds due to the triangle inequality. The second inequality holds due to the completeness assumption. The third inequality holds due to the property of the bonus function and
Σ
(Fa(et)
Thcet)) s (Bn)
(=)(2
kE[K]
by Lemma R:2
Therefore, (8) 2 (s) for all EE..
We also have
(s) [s)ss = (Qī -) Fn(s, x (1s))aa +
- =H1(1s))
S (Q) fs( xt (+1s))
<(TnVVl(s,)) - [n((,) ab)
((Tnfu+i((s,.) - (s, bu
a), T"' (1|s)) + +[[TH + (1)))))))))))))))))
S 2(b TH (+1))) +
(Mog (
VKR
where the first inequality holds due the policy मा takes the action which maximizes Jn. The second inequality holds due to the Bellman completeness assumption. The last inequality holds due the property of the bonus function
(2) S C- (DF ((
and Lemma
Then we do the induction step. Let R₁ = Ō
N VKn
111 = -11 ( (1-
We define another event ch
gind for induction.
gind {0 S Vi(ss Pa(s) < Rs
Vs E).
The above analysis shows that En Elrd and [P{En] 2 1 1-25. Moreover, P(g > 1 25
We conduct the induction in the following way. At stage h, if P(E 2 25 and PP 8
1 20 we prove that P|Ex] 2 1 26, and P( 2 28p.
Suppose stage h, 1 2 1 28,+1 and P[ 2 28 We first use Lemma G.I Let
fo Fr. f fn Fr. We define
n = Vi++ (s - 1
D = (z)
m
(5(xh) - f'(x)t))
After taking union bound, we have with probability at least 1 - 8/(411²), the following inequality holds,
(T(+h) - f(=+)) s 1000)A +200))+2200))) +302((0)
4
2 kE[A]
(+)())))²
28

---

+ ExE(K] (²,())))) (f( - F(th))
(G.8)
4
Next, we use Lemma G.2 at stage h. Let f - Jn E Fhr J Sn E Fr. = -sh+1 10
where b = fn- by E Fn W. We define:
I = ('(1 (i+t((6/+1) - - -Vi+1)) (=/)
If
A f.f:f = (on (f(eh) -f(zh))
-
After taking a union bound, we have with probability at least - 5/(4H²), we have
Fn+il (fr(=h) - fa( - (1 (00)V++ 11,1" 11 1 + 5 (8)/ /log.N. + 33022 1l ExE(K] (ōn(= (Tu(zh) - (z
(Z)(2)
kE|K]
2
(G.9)
Let Un be the event that G..8 and G.9
holds simultaneously. On the event Un n gind
h-1 which
satisfies PlU, n Eind
20 28/H =1- - 28 we have
1
(rh (0 - F((ett) (Tn(=)- Sn(=k))
2
(on(2)))²
kE[K]
2
Σ
Fhta(shh))) [Th (TnPh+al(+3)) (Fu(=h)- - Fu(
(=)(2
KETK]
+ 2 Σ
(Thhftti(t))) Fn(et)) (Fa(eh) -m((tt)
(#n(=R))2
kE[K]
rh + (n+t (T(A++1(=3)) 1() (TuCH) - Iu(=h) + 4K
2
(on(21))
KE[K]
3 0(0) V 220(6) + 30) + ( (0VV v2((0) 11 - 11
Vit 11 + 8KLC+ + EnE[K] (o)()p)))
- Fn(ttt)
2 26)) log.Ng 30)2
+ 3
2
+ ELE(K] ( (fx( - Tx()t)
(3n)² 2
(G.10)
2
where the first inequality holds due to the completeness assumption. The second inequality holds due to (G.8) and (G.).. The last inequality holds due to the event gind
h+11 and the choice of K 2
5 (())'H"
However, on the event of E we have
- (v%+ - Fn(=1)) (Fa(eN)- Fn(c))))))))))
2 kE[K]
(o(z)))2
Σ
(Fu(eh) - F2(44)) 2
(0(z)))2
kE[K]
Ene(K] (
- (fa(sf)
(3
2
where the first inequality holds due G.4). The second inequality holds due event & However, this contradicts with (G.TO). We conclude that Un cktt C En, thus P[Ex] 20g.
29

---

Next prove P( that
N 1 25,. Suppose the event Un n hh+1 holds, the above conclusion shows
Σ kE|K]
(Fulzh) Fn(ct)) > (8h)².
(on
We prove the following result.
2% (s. a) Vhi
2 [TT (|(,,a)
(s))))) 2 Jn a) - - (s,
2 Fh(s,a) a) - (e+ (fi(s,))))) -
(s, a) - (s,
(s)
where the first inequality hold due to the event Eind The second inequality holds due to the triangle inequality. The third inequality holds due to the completeness assumption. The last inequality holds due to the property of the bonus function and
E (fulet) -n(ettt² & (Bh)²
E kE|K]
(2)(2
Therefore, (s) 2 (s) aorallses We also have
(s) - (s) = (0) - fn(s, (+1s)) +
(n(sss)
(Q)(s,))) - fn(s,,), ) (+1s)))
((TAVAl(s,)) - Fa(s,)) by a), (-1s))
((TaBa+1)(s,.) Fa(s, bz a), x" (1(1))
+ +(TT Vitt iss, [Tn (1)54
S ((n ), (,,))))) + + +R++1
2ō log VlggNH - (H h (1+1) Rr.
VK*
where the first inequality holds due the policy 7. takes the action which maximizes Jh. The second inequality holds due to the Bellman completeness assumption. The second incquality holds due to the property of the bonus function
(x) ( (2; (BB)2 cBh))
and Lemma F.1 The last inequality holds due to the induction assumption. Therefore, we have UA n gind gdd and P [i 2 1 28, Thus we complete the proof of induction. Finally, taking the union bound of all the En, we get the result that with probability at least 8/2. the event _ En holds, i.e for any E [H] simultancously, we have
Σ KE[K]
(fa Fu(ctt) s (Bh)
Therefore, we complete the proof of Lemma F2
H PROOF OF LEMMAS IN SECTION E
AND G
H.1 PROOF OF LEMMA E.
Proof of Lemma E.1
We use Lemmal
I.I with the following conditions:
D&U, J f'] is adapted to the filtration H and E [D l') - 0.
30

---

D 2 2 max [f(z) [Th. (=)) I 4H² = M.
Σ E [ kE[K]
Σ KE[K]
( (Thf)))))))())?) - (4HK)²
V².
On the other hand,
Σ E KE|K]
Σ E
[ (vR("T) [/)
- -Ta
kE(K]
S 8H2
E (f(=h) - [Tnf(())))
RE(K]
Then using Lemma [.] with v 1, with at least 1- 88((HHN233)
Σ KE|K]
( - [Th (T))))))))))))))))))))) - (())
2(2 8H2)
Σ (f(Eh) - (Th
kE[K]
+ 2 (5) + -1 (6) 4H²
3
< (24H² + 5)) + ΣnE(K] (f(zh) - (T+
2
We complete the proof of Lemma B.1
H.2 PROOF OF LEMMA
E.2
Proof of Lemma
E.2
We use Lemma with the following conditions:
D [') is adapted the filtration H and E [D* J') H
O.
s 2 max (f(=) [T2,, S 4T.2 = M.
Σ [DAU.SD) = kE[K]
Σ E [<4G (J(=)) - (Tan))))))) x (4IPK) = V2. KE(K]
On the other hand,
Σ E KE[K]
ΣE
Σ E [ 2 | -
kE(A)
8L - (Tan(()))))
RE(K]
Then using Lemma [.T with
1, have:
Σ kE[K]
(f - (T2)) (0)) 2(2-8I4) Σ (f(z)) (T2,
KE[K]
3/ (2) + 7 (2( 41,2
2
3
(20Z) +5) + ΣnE[K] - (
We complete the proof of Lemma E.2
H.3 PROOF OF LEMMA G.
Proof of Lemma G.I We use Lemma
.1 with the following conditions:
DKL, [') is adapted to the filtration H/ and E [DAIS, #4 0.
D 2 nill max [[(=) [')) < 8LH M.
E
[
Σ E [(DKU,ST) -4 kE[K]
(s( ('(x)))
(ox
kE[K]
31

---

On the other hand,
E 1|
Σ [
E [DNU),)1)
= 4
(1(=)) (((h)))
(on (2
k
kE|A]
8
Σ
(f(#)) - ( r'(xt))²
(on))
kE[K]
where the last inequality holds because of the inequality in Lemma D.4
E (1/)) |= [aar, Vh 10 at)
S Vv V ab.)
(VlogAV. -No)
S (ox(z 2 +6
VKK VKx
S 2 (ōn() 2
where we use the requirement that K 52 log (og(WVNNs)H1 Moreover, for any k E [K],
f1I 2
[(x - fz(
(Gr(2
< 4H
D2, (* Dr. o
Σ
(f(et))(()))) (x +2)
(Tn(2z))2
KE[K]
4H12
<ō
Σ
(f(=))- ('(xh)) +
VKK
(ān()t))²
kE[A]
Σ KE(K!
(on(2)))2 -(=)) +
v(6)
The second inequality holds because of the definition of D divergence (Definition 3.4). The third inequality holds due Lemma F.I The last inequality holds because of the choice of K 2 (1))
Ω
Then using Lemma I.I with v = 1, m = 1, we have
(o)()) (f(=h) f'(xt) s v(8), KE(K]
Σ
16
Σ
(f(#))- f'(+t))2 + 2
3 (0)(0)
(on(=)))2
kE|K]
(0))
(xh(2 (F(*)) - ((xh))² +
KE(K]
()) / + VZu(d) + +30m2())
3
ΣRE(K] (on)))))²
(f(xt) - (xx
4
We complete the proof of Lemma G.1
H.4 PROOF OF LEMMA G.2
Proof of Lemma G.2
A. f, f'] is adapted to the filtration HA and E [ANI 17 0.
We also have
(chIPT) x
Σ
E (ANU.
1T) [ =
Σ
(5(=)) (()b))
(#n))))))
kE(K]
kE[K]
32

---

Il Vittal20
2 8
(f(zh) - f(
(ōn (2
kE[R]
Moreover, for any E [K].
A F. 2
(==h))
(2))²
4||s- - Vitillo,
(2h (=h Dn, 0k)
Dzg,
Σ KE[K]
(on (f(z)) (( +1
H
-118" - Vittilo,
Σ (on() (f(*)) - ('(+t))² +
VKR/
KEIK
||" Vi++il 1lxo
(2n(2²) (s(=)) J'(= +
(())
KE[K]
The second inequality holds because of the definition of D divergence (Definition 3.4). The third inequality holds due Lemma F.1 The last inequality holds because of the choice of K 2
(6))
Then using Lemma have
I.1 with v 1, 1, 1/ log Ns, with probability at least 1 N6((4HF2N33)), we
SN ((=))- (())
|l 1l
2
8
- +
(2)()
(2x
KE[K]
kE|K]
/ 20)) + (0)0) Vittillo
Σ KE(K]
(o (2t))) (s(=k) - f'(x1))2 +
< ( (OVA v2((0) 115 -V=+
2 "3" (6)) log 30, (6)11') - 11
1i+ +
EXE[K] ()
(s(=))
4
We complete the proof of Lemma
G.2
I AUXILIARY LEMMAS
Lemma I.1 (Agarwal et al. 2023 Let M > 0, V > 0 be constants, and
(zi)iej be stochastic process adapted to a filtration (Hi Suppose E[a,[Hi-1] = |od & M and Eiel 11 & 52 almost surely. Then for any d,e > 0, let i =
V log (2 (logs/ +2) we have
8
Σ KE[d]
x,
>6
2
2
E E[ H4-2] + v²
+
2,2
2
max (xg + m vEld]
S S.
.E|e]
Lemma 1.2 (Regret Decomposition Property, Jin et al. 2021b). holds,
Suppose the following inequality
(T)ff+1)(2)) (=) S bn()) (s, E S A [M].
the regret of Algorithm I can be bounded as
Vit (s) - v2(())
E.. (bn (sh, an) 91 = s].
1=1
Here E is with respect to the trajectory induced by n² in the underlying MDP.
33

---

Lemma 1.3 Ho inequality, Cesa-Bianchi & Lugosi 2006). Let {a:)i= be martin- gale difference sequence with respect to filtration { satistying c $ M for some constant M, I, is 9441- mcaaurabbe,,,, [[ = 0. Then for any 0 < d < with probability at least - 6, have
Σ 24 S M logog
34


Reviews:
[{"review_id": "57QlmYvLUo", "reviewer": "Reviewer_FxDp", "summary": "This paper considers the problem of offline reinforcement learning in finite-horizon MDPs with general function approximation, from a theoretical perspective.\nThe main assumptions are:\n- Bellman completeness: completeness of the of the value-function hypothesis class under first and second order Bellman optimality operators, possibly with misspecification\n- Uniform coverage of the hypothesis class by the offline dataset, in a novel form suited to general nonlinear value function approximation.\n- Access to a computational oracle (nonlinear least-squares regression)\n\nThe algorithm is UCBVI-like and combines pessimism variance-weighted least squares regression, where in turn the variance is estimated pessimistically from a fold of the dataset. It is oracle-efficient.\n\nThe main theoretical result is an upper bound on the simple regret that scales with the square root of the logarithm of the cardinality (or covering number) of the hypothesis class, and with inverse data coverage as measured by a D^2 divergence. The latter makes the bound instance-dependent. In this way, an instance-dependent regret bound is achieved in a more general setting and with weaker assumptions w.r.t. previous works.", "questions": "Could you give an intuitive reason for why you also need an *under*estimation of the variance? Also, does it make sense to call it \"pessimistic\" in this case? A smaller variance estimate has the effect of inflating the value estimate since you are using inverse variance weights, so it would seem more optimistic than pessimistic.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and clear. Theoretical claims are supported by detailed and well commented proofs, the main technical tools are highlighted and explained, and the assumptions are clear.\nThe summary of the state of the art is particularly complete and detailed. Both the strengths and the limitations of the work are properly highlighted and discussed.", "weaknesses": "I just have some minor remarks:\n1. In section 3 I think you went a bit too far with the abuse of notation when defining Bellman operators. Is f a function of the state or the state and action? How can you define the relationship between the Q and the V function of a fixed policy by Bellman's *optimality* operator?\n2. Assumption 3.2 is followed/complemented by other assumptions that are just given in-line. I suggest to state them as separate assumptions to improve clarity.\n3. You define $\\mathcal{N}$ as the cardinality of the hypothesis class but refer to it as the \"covering number\". The two are not the same, and the only covering argument that I could find was in Remark 5.3. for the linear case. \n\nTypos:\n- page 4 \"closed to the optimal value function\"\n- page 6: \"construct this variance estimator with...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "gDkpfOnz29", "reviewer": "Reviewer_KfKk", "summary": "This paper studies offline reinforcement learning with non-linear function approximation. It proposes an oracle-efficient algorithm, Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI), for offline RL with non-linear function approximation. The algorithmic design comprises three innovative components: (1) a variance-based weighted regression scheme that can be applied to a wide range of function classes, (2) a subroutine for variance estimation, and (3) a planning phase that utilizes a pessimistic value iteration approach. The algorithm enjoys a regret bound that has a tight dependency on the function class complexity and achieves minimax optimal instance-dependent regret when specialized to linear function approximation.", "questions": "Please answer the questions above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a pessimism-based algorithm Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI) designed for nonlinear function approximation, which strictly generalizes the existing pessimism-based algorithms for both linear and differentiable function approximation (Xiong et al., 2023; Yin et al., 2022b). The algorithm is oracle-efficient, i.e., it is computationally efficient when there exists an efficient regression oracle and bonus oracle for the function class (e.g., generalized linear function class). In addition, this paper introduces a new type of D2-divergence to quantify the uncertainty of an offline dataset, which naturally extends the role of the elliptical norm seen in the linear setting and the D2-divergence.", "weaknesses": "1. Even though there is an Appendix C explaining the computational aspect of computing the bonus, it seems only address the first bullet point in 4.3. How to computationally efficiently obtain the condition for the second bullet point in 4.3?\n\n2. This paper claims it generalizes over the differentiable parametric models in [Yin et al. 22b], would the main theorem 5.1 improves the results obtained in  [Yin et al. 22b]? \n\n3. This paper seems to be closely related to [Alekh et al. 23], however is not enough discussion about. May I consider this paper as an offline version of [Alekh et al. 23]? If not, what are differences?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "hXEPIE1fb7", "reviewer": "Reviewer_Fsc5", "summary": "This paper proposes an offline RL algorithm called Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI) for general function approximation. It introduces a type of D$^2$-divergence to quantify the uncertainty of the offline dataset, and proves an instance-dependent regret bound that has a tight dependence on the function class complexity (its covering number).", "questions": "- How to interpret Thm 5.1? \n- When is Thm 5.1 better than instance-independent regret bounds?\n- Your coverage assumption is weaker, but does it really matter in practice?\n- You assume that dataset is produced by a single BP. In reality, this may not always be true. What is the impact of different BPs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ This work fills a gap of designing efficient offline RL algorithms with general function approximation.\n+ It extends the concept of D$^2$-divergence in online RL to offline RL.\n+ It generalizes reference-advantage decomposition to general function approximation.", "weaknesses": "- The work is overall incremental. The key techniques are largely known, either from online RL or offline RL. I can see that there are technical barriers in directly extending them to the problem of offline RL with general function approximation, but such extensions are mostly not too difficult.\n- Improving the regret by a square-root of $d$ is quite standard for reference-advantage decomposition. This is more about the previous paper not doing the best job than developing truly novel method/analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "9dAZvKIrYg", "reviewer": "Reviewer_38or", "summary": "This paper considers offline RL with non-linear function approximation. The authors propose a new pessimism-based algorithm, Pessimistic Nonlinear Least-Square Value Iteration, to solve this problem. The proposed algorithm is oracle-efficient, and achieves instance-dependent regret bound characterized by the newly-proposed $D^2$ divergence.", "questions": "- Which part of the proof requires uniform data coverage while partial data coverage does not work?\n- This paper considers general function approximation, yet I'm unclear what types of function classes & instance structures will satisfy the conditions listed in the paper. Can you give some concrete examples beyond linear MDPs?\n- Can you provide a lower bound for general function approximations?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper proposes an algorithm for offline RL with non-linear function approximation that has instance-dependent regret guarantees, which is new in literature.\n- The author extend techniques used for linear MDPs (including variance-weighted ridge regression and reference-advantage decomposition) to nonlinear function classes.\n- The paper is generally well-written and clear.", "weaknesses": "- This paper poses a very strong converage assumption (Assumption 3.5), which may not be realistic in practice. In contrast, most pessimism-based offline RL papers that I'm aware of adopt weaker partial coverage assumptions. I wonder how valuable it is to prove an instance-dependent bound when we have to impose a uniform coverage condition.\n- The lower bound cited by the paper only works for linear cases. The authors do not provide a matching lower bound to showcase the optimality of the proposed algorithm with general function approximations.\n- The authors do not provide any numerical experiments in the paper. In my opinion, adding numerical experiments can better showcase the benefits of the proposed algorithm compared to other offline RL algorithms with general function approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)