On Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks in Besov Spaces
Authors: Thanh Nguyen-Tang
Sunil Gupta
Hung Tran-The
Svetha Venkatesh
Venue: Accepted by TMLR ()

Abstract: Offline reinforcement learning (RL) leverages previously collected data for policy optimization without any further active exploration. Despite the recent interest in this problem, its theoretical results in neural network function approximation settings remain elusive. In this paper, we study the statistical theory of offline RL with deep ReLU network function approximation. In particular, we establish the sample complexity of $n = \tilde{\mathcal{O}}( H^{4 + 4 \frac{d}{\alpha}} \kappa_{\mu}^{1 + \frac{d}{\alpha}} \epsilon^{-2 - 2\frac{d}{\alpha}} )$ for offline RL with deep ReLU networks, where $\kappa_{\mu}$ is a measure of distributional shift, $H = (1-\gamma)^{-1}$ is the effective horizon length,  $d$ is the dimension of the state-action space, $\alpha$ is a (possibly fractional) smoothness parameter of the underlying Markov decision process (MDP), and $\epsilon$ is a user-specified error. Notably, our sample complexity holds under two novel considerations: the Besov dynamic closure and the correlated structure. While the Besov dynamic closure subsumes the dynamic conditions for offline RL in the prior works, the correlated structure renders the prior works of offline RL with general/neural network function approximation improper or inefficient in long (effective) horizon problems. To the best of our knowledge, this is the first theoretical characterization of the sample complexity of offline RL with deep neural network function approximation under the general Besov regularity condition that goes beyond the linearity regime in the traditional Reproducing Hilbert kernel spaces and Neural Tangent Kernels. 

Published in Transactions on Machine Learning Research (12/2022)
On Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks in Besov Spaces
Thanh Nguyen-Tang Deportment of Computer Science, Johns Hopkins University
thaguuyentong@@mall.om
Sunil Gupta & Hung Tran-The & Svetha Venkatesh
Applied AI Institute, Denkin University
Reviewed on OpenReview: https: // openreview. net/ formfo id- LdEmOunNco
Abstract
Offline reinforcement learning (RL) leverages previously collected data for policy optimiza- tion without any further active exploration. Despite the recent interest in this problem, its theoretical results in neural network function approximation settings remain elusive. In this paper, we study the statistical theory of offine RL with deep ReLU network function approx- imation. In particular, we establish the sample complexity n Ō( 1+ - for offline RL with deep ReLU networks, where Ky is measure of distributional shift, H = (1-7)-1 is the effective horizon length, d is the dimension of the statc-action space, is (possibly fractional) hnest parameter of the underlying Markov decision process (MDP), and e is a user-specified error. Notably, our sample complexity holds under two novel considerations: the Besov dynamic closure and the correlated structure. While the Besov dynamic closure subsumes the dynamic conditions for offline RL the prior works, the correlated structure renders the prior works of offline RL with general/ network function approximation improper or inefficient in long (effective) horizon problems. To the best of our knowledge, this is the first theoretical characterization of the sample complexity of offiine RL with deep neural network function approximation under the general Besov regularity condition that goes beyond the linearity regime in the traditional Reproducing Hilbert kernel spaces and Neural Tangent Kernels.
1 Introduction
Offline reinforcement learning (Lange al. 2012 Levine al. 2020) is a practical paradigm of reinforcement learning (RL) where logged experiences are abundant but interaction with the environment is limited even prohibited. The fundamental offiine RL problems concern with how well previous experiences could be used to evaluate new target policy, known off-policy evaluation (OPF) problem, to learn the optimal policy, known as off-policy learning (OPL) problem. We study these offline RL problems with infinitely large state spaces, where the agent must rely on function approximation such as deep neural networks to generalize across states from an offline dataset. Such problems form the core of modern RT. in practical settings (Levine al. 2020 Kumar et al. 2020 Singh al. 2020 Zhang et al., 2022).
Prior sample-efficient results in offline RL mostly focus on tabular environments with small finite state spaces (Yin & Wang] 2020 Yin et al. 2021 Yin & Wang 2021a),, but as these methods scale with the number of states, they are infeasible for the settings with infinitely large state spaces. While this tabular setting has been exlended to large state spaces via linear environments (Duan & Wang 2020 Jin et al. 2020b Xiong el. al.,
2022 Yin et al. 2022 Nguyen-Taane Tanne et al., 2022b), the linearity assumption often does not hold for many RL problems in practice. Thcoretical guarantees for offline RI. with general and deep neural network function approximations have also been derived, but these results are either inadequate or relatively disconnected from the regularity structure of the underlying MDP. In particular, while the finite-sample results for offline

---

Published in Transactions on Machine Learning Research (12/2022)
RL with general function approximation (Munos & Szepesvári 2008 Le et al. 2019 depend an inherent Bellman error which could be uncontrollable in practice, the other analysis in the neural network function approximation in Yang et al. (2119) relies on a data splitting technique to deal with the correlated structures arisen in value regression for offline RL and use a relatively strong dynamic assumption. Recent works have studied offine RI. with function approximations in Reproducing Hilbert kernel spaces (RHKS) (Jin et al. 2020b) and Neural Tangent Kernels (NTK) (Nguyen-Taie et al. 2022a). However, these function classes also have (approximately) linear structures (in terms of the underlying features) which make their analysis similar to the linear case. Moreover, the smoothness assumption imposed by the RKHS is often strong for several practical cases while the NTK analysis requires a extremely wide neural net (the network width scales with n2 for the NTK case in 'guyen-Tann et al. (2022a) versus only n/2/5 (Proposition 5.1) in the current
work). Recent works (Xie et al. 2021a Zhan et. al.) 2022 Chen & Jiang] 2022 Uehara & Sun 2021 have considered offline RL with general function approximation with weaker data coverage assumption. However, they assumed the function class is finite and did not consider the (Besov) regularity of the underlying MDP. Thus, to our knowledge, no prior work has dedicated to study a comprehensive and adequate analysis of the statistical efficiency for offiine RL with neural network function approximation in Besov spaces. Thus, it is natural to ask:
Is offline RL sample-efficient with deep ReLU network function approzimation beyond the (approzimate-) linear regime imposed by RKHS and NTK?
Our contributions. In this paper, we provide statistical theory of both OPE and OPL with neural net- work function approximation in a broad generality that is beyond the (approximate-) linear regime imposed by RKHS and NTK. In particular, our contributions, which are summarized in Table [and will be discussed in details in Section
are:
First, we achieve a generality for the guarantees of offline RL with neural network function approx- imation via two novel considerations: (i) We introduce a new structural condition namely Besov dynamic closure which subsumes the cxisting dynamic conditions for offline RL with neural network function approximation and even includes MDPs that need not be continuous, differentiable or spa- tially homogeneous in smoothness; (ii) We take into account the correlated structure of the value estimate produced by a regression-based algorithm from the offline data. This correlated structure plays a central role in the statistical efficiency of an offline algorithm; yet the prior works improperly ignore this structure (Le et al. 2019) or avoid using an data splitting approach (Yang et al. 2019).
Second, prove that offline RL algorithm based on fitted-Q iteration (FQI) can achieve the sample complexity of Ō(H4+4 Ky "c --22% where measures the distributional shift in the offline data, H = (1-7)-1 is the effective horizon length, d is the input dimension, is a smoothness parameter of the underlying MDP, and is a user-specified error. Notably, our guarantee holds under our two novel considerations above that generalize the condition in Yang et al. (2019) and do not require data splitting in Yang et al. 2019). Moreover, our analysis also corrects the technical mistake in Le et al. (2019) that ignores the correlated structure of offline value estimate.
Problem scope. We emphasize that the present work focuses on statistical theory of offline RL with neural network function approximation in Besov spaces where we analyze a relatively standard algorithm, FQI. Regarding the empirical effectiveness of FQI with neural network function approximation for offline RL. we refer the readers to the empirical study in Voloshin et al. (2019). Finally, this work is an extension of our workshop paper [Nguyen-Tane Tang et al. 2021
Notations. Denote ||I = (L
1/v
and for simplicity, we write || lle for || Il when p = 2 and write || I|p for ll Ilpu if i is the Lebesgue measure. Let LP() be the space of measurable functions for which the p-th power of the absolute value is Lebesgue integrable, ie. L*(X') = {f : X + Rll fllp < oo). Denote by || llo the O-norm, i.e, the number of non-zero elements, and b max(a, b). For any two
2

---

Published in Transactions on Machine Learning Research (12/2022)
Table 1: Comparison among existing representative works of FQI estimators for offline RL with function approximation under uniform data coverage assumption. Here S and A are the cardinalities of the state and action space when they are finite, is a measure of distribution shift (which can be defined slightly different in different works), e is the user-specified precision, d is the dimension of the input space, a is the smoothness parameter of the underlying MDP, and H = (1 - 7) is the effective horizon length.
Work
Function
Regularity
Tasks
Sample complexity
Remark
Yin & Wang 2020
Tahular
Tahular
OPE
(x. Ha. 2...._2.000 (5A))))
Duan & Wang 2020
Linear
Linear
OPE
(K. -1.. ==
Le et al.
2019
General
General
OPE/OPI.
N/A
improper analysis
Yang sl.
2019
ReLU nets
Hölder
OPL
Ô (x2t 11a22g_ 2 log(
data splitting
This work
ReIUU nets
Besov
OPE/OPL
Ô Ön!t2 Ho+a8 . 22222
data reuse
real-valued functions f and 9, write f(-) S 9()) if there is an absolute constant e independent of the function parameters (.) such that f(-) S c- 9()). We write f()) x g() if f(+) S s(-) and g(-) S f(-). We write f() = g())) if there exists an absolute constant e such that f() = c. g()). We denote H := (1 -))- which is the effective horizon length in the discounted MDP and is equivalent to the horizon (episode) length in finite-horizon MDPs.
2 Related Work
Offline RL with tabular representation.
The majority of the theoretical results for offline RL focus on tabular MDP where the state space is finite and an importance sampling -related approach is possible
(Precup et al. 2000 Dudik et al.) 2011 Jiang & Li 2015 Thomas & Brunskill 2016 Farajtabar et al. 2018) Kallus & Uchara 2019). The main drawback of the importance sampling- bampling-bssed approach is that it suffers high variance in long horizon problems. The high variance problem can be mitigated by direct methods where we employ models to estimate the value functions or the transition kernels. We focus on direct methods in this work. For tabular MDPs with some uniform data-visitation measure dm > 0, a near-optimal sample complexity bound of (HHdmm/e) and O(Hdm//²) were obtained for time-inhomogenccous tabular MDP (Yin al., )021) and for Line-homoggenes respectively. With the single-concenntrablityy assumption, tight bound of OCH"SC" was achieved (Xie
tabular MDP (Yin & Wang 2021b Ren et al.] 2021
et al. 2021b Rashidinejad et al. 2021,, where H ~ 1/(1- is the episode length. Yin & WWang (002cc)
introduced intrinsic offline bound that further incorporates instance-dependen quantities. [hi et al. (0022)
obtained the minimax rate with model-free methods. Wang et al. (2022) derived gap-dependent bounds for offline RL in tabular MDPs.
Offline RL with linear function approximation. Offline RL with function approximation often follow
two algorithmic approaches: Fitted Q-iteration (FQI) (Bertsekas & Tsitsiklis
1995 Jong & Stone] 2007
Lagoudakis & Parr
2003
Grünewälder et al., 2012 Munos 2003: Munos & Szepesvári 2008 [Atts et al.
2008 Tosatto et al. 2017 Le et al. 2019), and pessimism principle (Buckman et al. 2020 where the former
requires a uniform data coverage and the latter only needs a sufficient coverage over the target policy. Duann
& Wann (2020) studied fitted-Q iteration algorithm in linear MDPs. Wang et al. (2020) highlighted the
necessity of strong structural assumptions (e.g., low distributional shift strong dynamic condition beyond rcalizability) for sample-efficient offline RL with linear function approximation suggesting that only realizability and strong uniform data coverage are not sufficient for sample-efficient oflline RL. Jii et al. (2020b) brought pessimism principle into offline linear MDPs. Nguyen- Tang et al. (2022b) derived a minimax rate of 1//n for offline lincar MDPs under a partial data coverage assumption and obtained the instance- dependent rate of 1 1/n when the gap information is available. Xiong et al. (2022); Yin et al. (2022) used variance reduction and data splitting to tighten the bound of Jīn et al. (2020b). Xie et al. (2021a) proposed
3

---

Published in Transactions on Machine Learning Research (12/2022)
Bellman-consistent condition with general function approximation which improves the bound of Jin et al. (2020b) by a factor of vi when realized to finite action space and linear MDPs. Chen et al. (2021) ) studied sample complexity of FQI in linear MDPs and derive lower bound for this setting.
Offline RL with non-linear function approximation. Beyond linearity, some works study offline RL in general or nonparametric function approximation, either with FQI estimators (Munos & Szepesvári 2008;
Le al. 2019: Duan et al. 2021a b Hu al. 2021), pessimistic estimators (Uchara & Sun| 2021 Ng Nguynn-
Tang et al. 2022a Jin el al. 2020b or minimax estimators (Uehara et al. 2021), where Uehara al. (2021)
also realized their minimax estimators to the neural network function approximation, Nguyen- Tane--Tarn Tang et al.
(022a) considered offline contextual bandits with Neural Tangent Kernels (NTK), and Jin et al. (020b))
considered the pessimistic value iteration algorithm with Reproducing Kernel Hilbert Space (RKHS) in their extended version. Our work is different from these aforementioned works in that we analyze the fundamental FQI estimators with neural network function approximation under the Besov regularity condition that is much more general than RKHS and NTK. We also further emphasize that even that RKHS and NTK spaces are non-linear function approximation, the functions in those spaces are linear in terms of an underlying feature space, making the analysis for these spaces akin to the case of lincar function approximation (Yan et al. (2019) also considered deep neural network approximation. In particular, Yang et al. (2019) locused on analyzing deep Q-learming using disjoint fold of offline data for each iteration. Such approach is considerably sample-ineffciint for offline RL with long (effective) horizon. In addition, they rely on a relatively restricted smoothness assumption of the underlying MDPs that hinders their results from being widely applicable in more general settings. Recently, other works (Xie et al. 2021a Zhan et al. 2022: Chen & Jiang, 2022 Uehara & Sun 2021) considered offline RL with general function approximation and imposed weaker data coverage assumption by using pessimistic algorithms. Their algorithms are more involved than FQI but did not study the effect of the regularity of the underlying MDP on the sample complexity of oflline RL. They also assume that the function class is finite which is not applicable to neural network function approximation. Since the first version of our paper appeared online, there have been several other works establishing sample complexity of reinforcement learning in Besov spaces for various problem settings, including e-greedy exploration for online setting with Markovian data (Liu et al. 2022) and off-policy evaluation on low-dimensional manifolds (Ji et al. 2022).
3 Preliminaries
We consider a discounted Markov decision process (MDP) with possibly infinitely large state space S, continuous action space A, initial state distributiin p E P(S), transition operator P: P - P(S), reward distribution R: S A + P(O0, 1J), and discount factor 7 E [0, 1). For notational simplicity, we assume that X : S x A C 1]a.
A policy π: : S + P(A) induces a distribution over the action space conditioned on states The Q-value function for policy x at state-action pair (s, a), denoted by Q a) E [o, 1], is the expected discounted total reward the policy collects if it initially starts in the state-action pair, i.c.,
("(s,a) = E,
= a000
Σ r==
where To ~ R(s,, ar), ~ T-1ss), and ~ P(-Is:-1, E Eampara((1)) (s, a)l, and the optimal value is V = max, V where the maximization is taken over all stationary policies. Alternatively, the optimal value V can be obtained via the optimal Q-function Q" = max, Q* as V = =E [max, (s a)). Denote by T and T the Bellman operator and the optimal- ity Bellman operator, respectively, i.e., for any f: S A R
The value of policy क is V =
[T" a) E [r] + BB P (1)a)) [f(s', [T' [[,,)) E + -B f
we have TTQ Q" and T=Q Q"
4

---

Published in Transactions on Machine Learning Research (12/2022)
Offline regime. We consider the offiine RL setting where a learner cannot explore the environment but has access to fixed logged data D = {(s,, 0z, 8/; r=)) collected priori by certain behaviour policy For simplicity, we assumne that { are independent and 1, is stationary. Equivalently, {(8, ())a are ii.d. samples from the normalized discounted stationary distribution over statc-actions with respect to T,, i.e., as) i.d. p!::-) (1 - -) Ei= 7 " at lpp, 7) where s P(-|s;, a:) and a; ~ 77([ss)). This assumption is relatively standard in the offinn RL setting (Munos & Szepesvári, 2008 Chen & Jiang, 2019a; Yang al. 2019). The goals of off-Policy Evaluation (OPE) and Off-Policy Learning (OPL) are to estimate 7 and V respectively from D. The performance of OPE and OPL estimates are mcasured via sub-optimality gaps defined as follows.
For OPE Task. Given a fixed target policy n, for any value estimate V computed from the offline data D, the sub-optimality of OPE is defined as
SubOpt(V; | V..
For OPL Task. For any estimate á of the optimal policy x that is learned from the offline data D, we define the sup-optimality of OPL as
SubOpt(ft) == Es-p V*())
3.1 Deep ReLU Networks Function Approximation
In practice, the state space is often very large and complex, and thus function approximation is required to ensure generalization across different states. Deep neural networks with the ReLU activation offer a rich class of parameterized functions with differentiable parameters. Deep ReLU networks are state-of-the-arl in many applications, e.g., Krizhevsky et al. (2012); Mnih et al.] (2015), including offline RL with deep ReLU networks that can yield superior empirical performance (Voloshin et al. 2019). In this section, we describe the architecture of deep ReLU networks and the associated function space which we use throughout this paper. Specifically, L-height, m-width ReLU network on Rd takes the form of
(x) = w(t) (wrl--1l (...(W(OO))) + (w))O))))6))
...) + +b(1-1)
+ 6(6)
where W(L)) E Rixm ((0) E R, (()) E Rmxdd E RT W E Rmxm B(0) R" V1 < 1 < L, 8 (W(), (1)) )isss, and (xx) = max max 0} is the (element-wise) ReLU activation. We define (L,, m, S, B) the space of L-hoight, m-width ReLU functions (x) with sparsity constraint S, and norm constraint B, i.e., (l lo + |]60) (o) s S, maxısss [| v ||66"|| I B. Finally, for some L,m E N and S, B E oo), we define the unit ball of ReLU network function space FNN as
= {{
lf < }
m. S,B
In nonparametric regressions, Suzuki 2018) showed that deep ReLU networks outperform any non-adaptive lincar estimator due to their higher adaptivity to spatial inhomogeneity.
3.2 Besov spaces
Our new dynamic condition relies on the regularity of Besov spaces. There are several ways to characterize the smoothness in Besov spaces. Here, we pursue a characterization via multivariate moduli of smoothness as it is more intuitive, following Giné Nickl (2016).
Definition 3.1 (Multivariate moduli of smoothness). For any > 0 and r e N, the r-th multivoriate modulus of smoothness of any function f E ( oc] is defored as
wf)(s)== = sup ||A
o5 <t
5

---

Published in Transactions on Machine Learning Research (12/2022)
where (f) is the r-th order translation-diffeeend operator defined
AX0) = (-) =000=-=0-))+)++
Remark 3.1. The quantity (f( captures the local oscillation of f which is not necessarily differentiable. In the case the r-th order weak derivative f exists and is locally integrable, we have
(T()()) D ((x).
lim k-+
||/11"
It also follows from Minkowski's inequality that
wf) ||D' and (f)
S (D'
1"
1r
Definition 3.2 (Besov space Bg,g (X)). For 1 S p.q S co and a 0, we define the norm || llpg, of the Besov space Bp.g(2)) [|] ||/ Is 19., where
w (o)+1(()
9
1/4
dt
1 1 q < C0,
MM
whp (f)
SUP=>0
q 00,
is the Besov seminorm. Then, Bpg == e ( Iifll <o0.
Intuitively, the Besov seminorm [[ay, roughly describes the L.-normm of the P--ormm of the a-order smooth- ness of f. Besov spaces considerably general that subsume Hölder spaces and Sobolev spaces
well as functions with spatially inhomogeneous smoothness (Tricbel, 1983 Sawano 2018 Suzuki 2018
Cohen 2009 Nickl & Pötscher, 2007). In particular, the Besov space B reduces into the Hölder space Ca when = = 00 and a is positive and non-integer while reduces into the Sobolev space Wi when = q = and a is a positive integer. We further consider the unit ball of (2g(2) as (X)) = {g Bp lg I and ||g||>> 1). When the context is clear, we drop X' from Bgg(A)
4 Fitted Q-Iteration for Offline Reinforcement Learning
Algorithm Fitted Q-Iteration with Neural Network Function Approximation
1: Input: Offline data D = ((8; 0g 8,, r number of iterations K, function family FNN, target policy x (for OPE Task ouly)
Initialize Qo FNN
for k 1,..., K do
Compute the estimated state-action value Qk
Qk + arg Jex 1 E (f(s;, as) - -B (Bo--a(1k))) 1Q (Qk-1(5/, if OPE Task Q& aigmin n D (J(s) - ri - m Qk- 1x-1
if OPL. Task
5: end for Output: Return the following estimates
Vi + 1Qkl = V Bats)a(ass) [Qx(s,
if OPE Task
(K(--s) + arg max, Qx (als)
if OPL Task

---

Published in Transactions on Machine Learning Research (12/2022)
In this work, study a variant of fitted Q-iteration (FQI) algorithm for offiine RL, presented in Algorithm This algorithm is appealingly simple as it iteratively constructs Q-estimate from the offline data and the previous Q-estimate, as in Algorithm I This FQI-style algorithm has been largely studied for offline RL, such as Munos & Szepesvári (2008); Chen & Jiang (2019al; Duan et al. (2021a) to name a fow; yet there has been no work studying this algorithm in offline RL with neural network lunction approximation except Yang et al. (019).. However, [Yang et al. (2019) use data splitting and rely on a more limited dynamic condition than ours. Thus, the notable difference Algorithm I i the use of neural network to approximate Q-functions and we estimate each QE using the entire offline data set, instead of splitting the data into disjoint sets as in Yang et al. (2019). In particular, Yang et al. (2019) split the offline data into K disjoint sets, resulting in the sample complexity linearly scaled with K, which is highly inefficient in long (effective) horizon problems where the elfective horizon length H = 1/(1 -7) is large.
As we do not split: the data into disjoint sets, a correlated structure induced. Specifically, at each iteration l in Algorithm [ Q==1 also depends on (s),a:) which makes E irs + y max, Q a)] * [T< a:) in OPL Task (and E rr + =B)=)((1))) 1Qk- (5'. * [T*Qu- a,) in OPE Task, respectively). This correlated structure hinders a direct use of the standard concentration inequalities such as Bernstein's in- equality that require a sequence of random variables to adapt to certain filtration. We overcome this technical difficulty using uniform convergence argument.
In our analysis, we assume access to the minimizer of the optimization in Algorithm I In practice, we can use (stochastic) gradient descent to effectively solve this optimization with Lo regularization (Louizos et al., 2017). If the Lo constraint is relaxed in practice, (stochastic) gradient descent is guarnnteed to converge to global minimum under certain structural assumptions (Du et al. 2019a b Allen-Zhu et al. 2021
2019 Nguyen
5 Main Result
To oblain a non-trivial guarantee, certain assumptions on the distribution shift and the MDP regularity are necessary. We introduce the assumptions about the data generation in Assumption 5.1 and the regularity of the underlying MDP 5.2.
Assumption 5.1 (Uniform concentrability coefficient Munos & Szepesvári 2008 ) 3xg < oo such that
du
Kkp for any admissible distribulion v. dp
The finite Ny in Assumption 5.1 asserts that the sampling distribution a is not too far away from any admissible distribution, which holds for a reasonably large class of MDPs, c.g., for any finite MDP, any MDP with bounded transition kernel density, and equivalently any MDP whose top-Lyapunov exponent is negative. We present simple (though stronger than necessary) example for which Assumption 5.1 holds.
Example 5.1. If there exist absolute constants 01, > O such that for any 8, s' E E,, there exists on action a E A such that a)) 2 1/c1 and nraas)) 2 1/c2, Vs, a, then we can choose Ky = C1
Chen & Jiang 2019a) further provided natural problems with rich observations generated from hidden states that has a low concentrability coefficient. These suggest that low concentrability coefficients can be found in fairly many interesting problems in practice.
We now state the assumption about the regularity of the underlying MDP.
A Assumption 5.2 (Besov dynamic closure). Consider some fixed p. g E [1, oo] and a a> mpn
For OPE Task: For largel policy n, and for some (L, m, S, B) N R4 (which will be specified later) we assume that: vf E FNN(L,
= T p...
For OPL, Task: For some (T., m. S, Ex>NNNx R (which will be specified later) we assume. that: Vf E FNN(L, S, B) f' Da
Iy is said to he admissible if there exist and policy a such that v(s,a) P(st = 8, alsı ~ P. R), Vs,
7

---

Published in Transactions on Machine Learning Research (12/2022)
Assumption 5.2 signifies that for OPL task (for OPE task with target policy т, respectively) the Bellman operator 7 (7 respectively) applied on any ReLU network function in FNN( m, B) results in new d
function that sits in p.g (2). The smoothness constraint > min(n.2] is necessary to guarantee the compact- ness and the finite (local) Rademacher complexity of the Besov space, and a - ddpp is called the differential dimension of the Besov space. Note that when p 2 (thus the condition above becomes > d/p), a fune- tion in the corresponding Besov space contains both spiky parts and smooth parts, i.c., the Besov space has inhomogeneous smoothness (uzuki 2018).
Our Besov dynamic closure is sufficiently general that subsumes almost all the previous completeness assumptions in the literature. For example, simple (yet considerably stronger than necessary) suffi- cient condition for Assumption 5.2 is that the expected reward function r(s, a) and the transition density P(s'ls, a) for each fixed s' are functions in Bp.g: regardless of any input function f and any target policy Such condition on the transition dynamic is common in the RL literature; for example, linear MDPs (Jin et al., 2020a) posit a linear structure on the expected reward and the transition density as r(s, a) = (Ø(s,a), 0) and a) = (é(s,a), N(s')) for some feature map Φ X' + idd and signed mea- To make it even more concrete, we present the following examples for sures X(s') = (A('))....,,A
Assumption 5.2
Example 5.2 (Reproducing kernel Hilbert space (RKHS)). Defone kn,1 the Malérn kernel with smoothness porometer h > 0 and length scale > If both r(.) and ge g.) == P(s'l.) at any s' E S are functions in the RKHS of Matérn kernel kn, where h = a- d/2 Moreover, this particular case is equivalent to the dynamic condition considered in Yang et al. 2019).
and 1 > 0, then Assumption 5.2 holds for p q 2.
Example 5.3 (Reduction to linear MDPs). Linear MDPs Jin et al. 2020o correspond to Assumption 5.2 with 1 and p q p-norm bounded domain.
Note that Assumption 5.2 even allows the expected rewards r(-) and the transition densities g-) == P(s'I-) to contain both spiky parts and smooth parts, i.c., inhomogencous smoothness, as long p < 2 (thus the constraint condition becomes a > d/p).
We are now ready to present our main result.
Theorem 5.1. Under Assumption 5.1 and Assumption 2.2 for some (L, m, S, B) satisfying 1 for any
<> 0, E (0, 1], K > 0, n satisfies that n 2 1+ log n + 2 (log(1/6) + log log n), then with probability
(2)
least 1 8, the sup-oplimality of Algorithm
VKy S 7-7
21/2
SubOpt(Vx;;))
+
for OPE,
(1-7)1/2
2%, / Kp
2y14//2
SubOpt(TKK+ 1
e
for OPL.
(1 - 7)2
(1
7/3/22
In addition, the optimal deep ReLU network 4LL, m, S, B) that obtains such sample complerity (for both OPE and OPL) satisfies
L 1x N, Nog S= N, and B x N1/44(20/(0-))
(1)
(ootta))) (ata+ 112072
where N x
and ::
d(p :== (1+
[a])
As the complete form of Theorem 5.1 is quite involved, we interpret and disentangle this result to understand FQI algorithms with neural network function approximation for offline RL tasks. The sub-optimality in both
2This sufficient condition imposes the smoothness constraint solely on the underlying MDP regardless of the input function f. Thus, the "max" over the input function ((s.a) does not affect the smoothness of the resulting function after f is passod through the Bellman operator. This holds regardless of whether f is in the Besov space.
3hhis is due to the norm-equivalence between the above RKHS and the Sobolev space W (x)) (Kanagawa et al. 2018 and (X'.
the degeneration from Besov spaces Sobolev spaces BT
'However, linear MDPs do not require the smoothness coustraint a min(p.2 to ensure a finite Rademacher complexity of linear models. Of course, our analysis addresses significantly more complex and general settings than linear MDPs which believe more important than recovering this particular condition of linear MDPs.
8

---

Published in Transactions on Machine Learning Research (12/2022)
OPE and OPL consists of the statistical error (the first term) and the algorithmic error (the second term). While the algorithmic error enjoys the fast linear convergence to 0 as K gets large, the statistical error reflects the fundamental difficulty of our problems. To make it more interpretable, we present a simplified version of Theorem 5.1 where we state the sample complexity required to obtain a sub-optimality within c.
Proposition 5.1 (Simplified version of Theorem 5.1 For any K 2 H log(1/e), the sample complexity of 1+
Algorithu 1 for OPE Task and OPL Task is n= Ó(H2+2# Rig " --2222 and n= m==Or Ó(H++44 Ki 1+ = =-22-2%)
respectively. Moreover, the optimal deep ReLU network $(I,, m, S, B) for both OPE and OPL. Tasks that obluins such sample complenity is L= O(ogn), = O(2// ( log n), S (n2215), and log B = 0 20)
To discuss our result, we compare it with other existing works in Table 1 As the literature of offline RL is vast, we only compare with representative works of FQI estimators for offline RL with function approximation under a uniform data coverage assumption, as they are directly relevant to our work that uses FQI estimators with neural network function approximation under uniform data coverage. Here, our sample complexity does not scale with the number of states as in tabular MDPs (Yin & Wang 2020; Yin et al.) 2021 Yin & Wang 2021a) or the inherent Bellman error as in the general function approximation (Munos & Szepesvári 2008; Le et al. 2019 Duan et al. 2021a). Instead, it explicitly scales with the (possible fractional) smoothness a of the underlying MDP, the dimension d of the input space, the distributional shift mcasure Ki and the effective episode length H = (1 -1 Importantly, this guarantee is established under the Besov dynamic closure that subsumee the dynamic conditions of the prior results. Compared to Yang et al. (2019), our sample complexity has a strong advantage in long (effective) horizon problems where H > a-2d log()/e) 5
and improves it by a factor of -1 log (1211 It also suggests that the data splitting in Yang ct al. (2019) should be preferred for short (effective) horizon problems. Though our bound has a tighter dependence on H in the long horizon setting, the dependence on e in our bound is compromised and does not match the minimax rate in the regression setting. We leave as future direction to construct the lower bound for the data-reuse setting of offline RL.
On the role of deep ReLU networks in offline RL. We make several remarks about the role of deep networks in offiine RL. The role of deep ReLU networks in offline RL is to guarantee maximal adaptivity to the (spatial) regularity of the functions in Besov space and obtain an optimal approximation error rate that otherwise were not possible with other function approximation such as kernel methods (Suzuki 2018 Morcover, by the equivalence in the functions that a neural architecture can compute (Yarotsky) 2017) Theorem 5. also readily holds for any other continuous piece-wise linear activation functions with finitely many line segments M where the optimal network architecture only increases the number of units and weights by constant factors depending only on M. Moreover, we observe that the optimal ReLU network is relatively "thinner" " than overparameterized neural networks that have been recently studied in the literature (Arora let al. 2019 Allen-Zhu et al.) 2019: Hanin & Nica 2019 Cao & Gu 2019 Belkin 2021 where the width m is a high-order polynomial of n. As overparameterizattoon is a key feature for such overparameterized neural networks to obtain a good generalization, it is natural to ask why a thinner neural network in Theorem 5.1 also guarantees strong generalization for offline RL? Intuitively, the optimal ReLU network in Theorem 5.1 is regularized by strong sparsity which resonates with our practical wisdom that sparsity-basod regularization prevents over-fitting and achieve a better generalization. Indeed, as the total number of parameters in the considered neural network is p md + m + m² (T. 2) = O(2 log" N) while the number of non-zeros parameters S only scales with N, the optimal ReLU network in Theorem 5.1 is relatively sparse.
6 Technical Review
In this section, we highlight the key technical challenges in our analysis. In summary, two key technical challenges in our analysis are rooted in the consideration of the correlated structure in value regression in Algorithm D and the use of deep neural network as function approximation (and their combination).
To address these challenges, we devise the so-called double uniform convergence argument and leverage a
Thii condition is often easily satisfied as practice we commonly set, 7 = 0.99 and 0.001, thus have H 100 and 1og(1/r)= 3.
9

---

Published in Transactions on Machine Learning Research (12/2022)
localization argument via sub-root functions for local Rademacher complexities. In what follows, we briefty discuss these technical challenges and our analysis approach.
The analysis and technical proofs of Yang et al. (2019); Le et al. (0019) heavily rely on the equation E ri - ((1) (Qx-1(s;, a]]] = [T (=*xxI((ss;00) ai) to leverage the standard nonparametric regression
techniques (in a supervised learning setting). However, the correlated structure in Algorithm | implics
I rr T (==+ (Qk-1(5), a)] # [T*RR=1[(s;; a:) as Qk-1 also depends on (si, 0z). Thus, the techniques in these prior works could not be used here and we require a new analysis. It is worth noting that Le et al. (2019) also re-use the data as in Algorithm [ (instead of data splitting as in Yang et al. 2019 but
mistakenly assume that E r. + ( (Q (Qk-1 a)] = [I= Qz). To deal with the correlated structure, devise double uniform convergence argument. The double uniform convergence argument is appealingly intuitive: while in standard regression problem, the (single) uniform convergence argument soeks the generalization guarantee uniformly over an entire hypothosis space of a data-dependent empirical risk minimizer, in the value regression problem of Algorithm [ we additionally guarantee generalization uniformly over the hypothesis space of the data-dependent regression target T* To make it concrete, we highlight a key equality in our proof where the double uniform convergence argument is used:
max [Q 1 Qx11
sup QENNN
(E En - (g) + sup QEFNN
En 1 10:112-108 (0))
I empiticaal process term
1ias term
where 1 (x) = Eir + maxx' Q(5', (/66,'' d') [=], and f == arg IIf 122, and 499 := (f((x)) - -r Y max, a()) and 1,00 == (J. (m)) - m - max. Q(5), )²) are random variables with respect to the randomness of (an, ri, We have learned that a similar general idea of the double uniform convergence argument has been leveraged in Chen & Jiang (2019b) for general function classes. We remark they use finite function classes, and in our case, the double uniform convergence argument is particularly helpful in dealing with local Rademacher complexities under a data-dependent structure as local Rademacher complex- ities already involve the supremum operator which can be naturally incorporated with the double uniform convergence argument.
The double uniform convergence argument also requires different technique to control an empirical process term J1 as it now requires uniform convergence over the regression target. We leverage local Rademacher complexities to derive bound on 1ı:
- supf (E -l Q 11f 1-1 S r}
2r (10)
28 log(1/))
S 6ER,, g E FNN, 2lle < sr) + 2/
+
3n
where Rn is the local Rademacher complexity (Bartlett et al. 2005p. An explicit bound is then derived via a localization argument and the fixed point of a sub-root function.
The use of neural networks pose a new challenge mainly in bounding the bias term /z. We derive this bound using the adaptivity of deep ReLU network to the regularity in Besov spaces, leveraging our Besov dynamic condition in Assumption 5.2 Bounding the bias term also requires the use of a concentration incquality.
While Le et al. (2099) use Bernstein's 's inequality, our bias term 12 requires a uniform convergence version of Bernstein's 's inequality as 1, requires guarantee uniformly over FNN. We omit detailed proof for Theorem to Section A
7 Conclusion and Discussion
We presented the sample complexity of FQI estimators for offline RL with deep ReLU network function approximation under a uniform data coverage assumption. We proved that the FQI-type algorithum achieved 1 the sample complexity of = Ō(H4+4g ki. - under correlated structure and a general dynamic condition namely the Besov dynamic closure. In addition, we corrected the mistake in ignoring the correlated
10

---

Published in Transactions on Machine Learning Research (12/2022)
structure when reusing data with FQI estimators in Le al. (2019), avoided the possibly inefficient data splitting technique in Yang et al. (2019) for long (effective) horizon problems, and proposed general dynamic condition that subsumes all the previous Bellmen completeness assumptions. In the following, we discuss future directions.
Relaxing the assumption about uniform data coverage. For a future work, we can include the pessimistic approach in Jin et al. (2020b); Rashidinejad et al. (2021); Uehara & Sun (2021): Nguyen-Tang
et al. (022a)) to the current work with a more involved analysis uncertainty quantifiers under non-linear function approximation relax the strictness of the uniform data coverage assumption.
Relaxing the assumption about optimization oracle. The present work assumes access to the op- limization oracle when fitting neural network the offline data. It is desirable to understand how optimization and generalization of trained neural network can contribute to offiine RL with neural func- tion approximation. A promising approach to obtain tight trajectory--ependent sub-optimality bound of offline RL with neural function approximation is to characterize the SGD-based optimization via stochastic differential equation by allowing the stochastic noises to follow the fractional Brownian motion
Tan et al.
b2 Tong et al. 2022).
Acknowledgements
We thank our anonymous reviewers and our action editor Yu-Xiang Wang (UC Santa Barbara) TMLR for the constructive comments and feedback. Thanh Nguyen-Tang thank Le Minh Khue Nguyen (University of Rochester) for the support of this project during the COVID times.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019. 7
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-resicuul minimization based fitted policy iteration and single sample path. Mach. Learn., 71(1):89 129, April 2008, ISSN 0885-6125. doi: 111007//119994007-55000 URL 810994-007-50387
http://800..rg11111000000/
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv:1904. 11955, 2019.
Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Ann. Statist., 1374) 08 2005. doi:
URL ltttp:://doii oorpoloorg/10..1/1111
00905366500000002822
25
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. arxiv preprint ar Xrx::2200.11 14368, 2021.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: an overview. In Proceedings of 1995 34th IEEE Conference on Decision and Control, volume 1, pp. 560 564. IEEE, 1995.
Jacob Buckman, Carles Gelada, and Marc Bellemare. The importance of pessimism fixed-dataset policy optimization. arXiv preprint urXim:0009 06709,, 2020.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Newral Information Processing Systems, 32:10836 10846, 2019.
Jinglin Chen and Nan Jiang. ceemmationnthhoreete considerations in batch reinforcement learning. In ICML, PMIRR 2019a.
volume 97 of Proceedings of Machine Learning Research, pp.
11

---

Published in Transactions on Machine Learning Research (12/2022)
Jinglin Chen and Nan Jiang. Information- considerations in batch reinforcement learning. arXiv
preprint or Xiv: 1eo:1905.. 00360, 2019b.
10
Jinglin Chen and Nan Jiang. Ofllie reinforcement learning under value and density-ratio realizability: the
power of gaps. 2022. 2
Lin Chen, Bruno Scherrer, and Peter L. Bartlett. Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm. orXiv preprint arXiv:2103.096//7 2021.
Albert Cohen. A primer on besov spaces, 2009. URL http:////aa.ooorcccoottttooo/1/1
G
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In ICML, volume 97 of Proceedings of Machine Learning Research, pp- 1975-1685. PMLR, 2019a.
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over-
parameterized neural networks. In ICLR (Poster). OpenReview.net, 2019b. 7
Yaqi Duan and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. CoRR, abs/2002.09516, 2020.
1
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. arXiv preprint arXiv:2103.1180 2021a.
9
Yaqi Duan, Mengdi Wang, and Martin J Wainwright. Optimal policy evaluation using kernel-based temporal difference methods. arXiv preprint arXiv:2109.19002 2021b. 4
Miroslav Dudík, John Langford, and Lihong L.i. Doubly robust policy evaluation and learning, arXiv preprint arXiv:1103.4601, 2011.
Mchrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadch. More robust doubly robust off- off-policy evaluation. arXiv preprinl vxXiv:1802.03490 2018. 3
Max H Farrell, Tengyuan Liang, and Sanjog Misra. Deep neural networks for estimation and inference: Application to causal effects and other semiparametric estimands. arXiv preprint Xrx:1:1800 09955, 2018.
20
Evarist Giné and Richard Nickl. Mathematical foundations of infinite-dimensiinn statistical models, vol- ume 40. Cambridge University Press, 2016.
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Massimiliano Pontil, and Arthur Gretton. Modelling transition dynamics in mdps with RKHS embeddings. In ICML. icml.ce Omnipress, 2012. 3
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A Eistribuution-Fre. Theory of Nonpara- metric Regression. Springer series in statistics. Springer, 2002.
25
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. arXiv preprinl
arXiv:1909.0530 05989, 2019. 9
Yichun Hu, Nathan Kallus, and Masatoshi Uchara. Fast rates for the regret of offline reinforcement learning. arXiv preprint Xic:21102. 000.00077999 79, 2021. 4
Xiang Ji, Minshuo Chen, Mengdi Wang, and Tuo Zhao. Sample complexity of nonparametric off-policy evaluation on low-dimensional manifolds using deep networks. arXiv preprinl Xrx:::2206. 02887, 2022.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning, 2015.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp- 2137-2143 PMI.R, 2020a.
12

---

Published in Transactions on Machine Learning Research (12/2022)
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offine rI? orXiv preprint arXiv:2012. 15085, 2020b.
3
Nicholas K. Jong and Peter Stone. Model-basee function approximation reinforcement learning. In
AAMAS, pp. 95. IFAAMAS, 2007.
3
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes, 2019.
g
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovie, and Bharath K Sriperumbudur. Gaussian processes and kernel methods: A review connections and equivalences. ar preprint ar arXiv:1807.02582 2018.
g
Alex Krizhevsky, Πya Sutskever, and Geoffrey Hinton. Imagenct classification with deep convolutional neural networks. In Advances in neurul information processing systems, pp. 1097-1105, 2012.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for ollline reinforce-
ment learning. arviv preprint arXiv:2006. 04779, 2020.
Michail G. Lagoudakis and Ronald Parr. Least-squares policy iteration. J. Mach. Learn. Res., 4:1107-1149, 2003.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pp. 45 73. Springer, 2012. I
Hoang Minh Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In JCML, volume 97 of Proceedings of Machine Learning Research, pp. 3703 3712. PMLR, 2019.
4
9
16
19
20
Yunwen Lei, Lixin Ding, and Yingzhou Bi. Local rademacher complexity bounds based on covering numbers.
Neurocomputing, 218:320 218:320-330, 2016. 25
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint wrXiv:2005.0664: 2020.
Fanghui Liu, Luca Viano, and Volkan Cevher. Understanding deep neural function approximation in re- inforcement learning via S1epsilonS- exploration. In Alice H. Oh, Alekh Agarwal, Danielle Bel- grave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022. URL
https://openreviiee http:://ww.....eoo/ooooooooo///.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through 1o regularization. CoRR, abs/1712.01312, 2017. URL
7
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7)40):529 533, 2015.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, Pp. 560-567. AAAI Press, 2003,
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. J. Mach. Learn. Res., 815-857, 2008.
2
20
Quynh Nguyen. On the proof of global convergence of gradient. descent for deep relu networks with linear widths. arXio preprint (xXiv:2101.096111 2021.
Thanh Nguyen-Tangg Tang, Sunil Gupta, Hung Tran- and Svetha Venkatesh. Sample complexity of offline reinforcement learning with deep relu networks, 2021. 2
Thanh Nguyen-Tang, Sunil Gupta, A. Tuan Nguyen, and Svetha Venkatesh. Offline neural contextual bandits: Pessimism, optimization and generalization. In International Conference on Learning Represen- lations, 2022a. URL https:://pperrevieu htt.a:/ae.....eaeeeeaaaaaaae//ea
13

---

Published in Transactions on Machine Learning Research (12/2022)
Thanh Nguyen-Tune Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement, learning with linear function approximation. ar Xix preprint arXiv:2211.13208 2022b.
13 3
R. Nickl and B. M. Pötscher. Bracketing metric entropy rates and empirical central limit theorems for function classes of besov- and sobolev-type. Journal of Theoretical Probability, 20:177-199, 2007.
26
Doina Precup, Richard S. Sutton, and Satinder Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the Seventeenth International Conference Machine Learning, ICML '00, pp. 759-766, San Francisco, CA, USA, 2000. Morgan Kaulmann Publishers Inc. ISBN 1558607072. g
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging oflline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103. 12021, 2021.
Patrick Rebeschini. Oxford Algorithmic Foundations of Learning, Lecture Notes: Maximal Inequalities
and Rademacher Complexity, 2019. URL: lhttp://www stats. ox. ac. hcc.u///bbbeecc//ccchhhcg////// 20/material//lacuur022.. pdf Last visited Sep. 14, 2020. 25
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforce- ment learning. Advances in neurol information processing systems, 34:15621 15634, 2021.
Yoshihiro Sawano. Theory of Besoe Spaces, volume 56. Springer, 2018. ISBN 978-981-13-06335
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic llearnnig for oflline reinforcement learning: Towards optimal sample complexity. arXiv preprint arXic:220.. 13890, 2022.
Avi Singh, Albert Yu, Jonathan Yang, Jesse Zhang, Aviral Kumar, and Sergey Levine. Cog: Connecting new skills to past experience with offline reinforcement learning. arXiv preprint or arXiv:2010.1 14500. 2020.
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rale and curse of dimensionality. arviv preprint ar Xiv:118810. 00x0:0181000003, 2018
5
6
g
26
Chengli Tan, Jiangshe Zhang, and Junmin Liu. deapeeeo generalization bounds for deep neural
networks via fractional brownian motion. arXiv preprint orXin:2206.044: 04359, 2022.
1I
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 2139-2148, 2016.
Anh Tong, Thanh Nguyen-Tanne Toan Tran, and Jacsik Choi. Learning fractional white noises in neural stochastic differential equations. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreviice net./ net/
forum? 2d==mm1dx21222
Samuele Tosatto, Matteo Pirotta, Carlo D'Eramo, and Marcello Restelli. Boosted fitted q-iteration. In ICML, volume 70 of Proceedings of Machine Learning Research, pp. 3434-3443. PMLR, 2017. 3
H. Tricbel. Theory of function spaces. 1983.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial cov-
crage. arXiv preprint ar arXi::2177.06226, 2021. 2
Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. ar preprint arXix:2102. 02981, 2021.
Cameron Voloshí,, Hoang M Le, Nan Jiang, and Yisong Yuc. Empirical study of off- off-policy policy evaluation for reinforcement learning. arXiv preprint arXiv:1911.000 2019. 2
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offine rl with linear function approximation? Xrxio preprint or orXin:2000.1 11895, 2020. 3
14

---

Published in Transactions on Machine Learning Research (12/2022)
Xinqi Wang, Qiwen Cui, and Simon S Du. On gap-dependent bounds for offiine reinforcement learning. arXiv preprint or Xic:22006.00 0010000.0011000000 00177, 2022.
Tengyang Xie, Ching-Ar An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman--consssennt pessimism for offine reinforcement learning. Advances in neural information processing systems, 34, 2021a. 2
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finctuning: Bridging sample- efficient offline and online reinforcement learning. Advances in newral information processing systems, 34: 27395-27407, 2021b. 8
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and T. Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game.
ArXio, abs/2205.1552 15511, 2022. 3
Zhuoran Yang, Yuchen Xie, and Zhaoran Wang.
theoretical analysis of deep q-learning. CoRR,
abs/1901.00137, 2019. 2
19
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 04:103-114 2017.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In ATSTATS, volume 108 of Proceedings of Machine Learning Research, pp. 3948-3958. PMLR, 2020.
3
Ming Yin and Yu-Xiang Wang. Characterizing uniform convergence in offline policy evaluation via model- based approach: Offline learning, task-agnostic and reward-free, 2021a. g
Ming Yin and Yu-Xiang Wang. Optimal uniform ope and model-based offline reinforcement learning in time- homogeneous, reward-free and task-agnostic settings. Advances in neural information processing systems, 34:12890 12903, 2021b. 3
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065-4074 2021c. 3
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in oflline policy eval- uation for reinforcement learning. In Arindam Banerjee and Kenji Fukumizu (eds.), The 24th Inter- Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pp. 1567-1575. PMLR, 2021. URL
national Conference
http://procesdingg www.eeeeedinnssm.......m. mml. http:/aacsaaaaamm..prrre//////// h11.3/0/yi21a.httt html
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. orXiv preprint orXiv:2203.0588 2022.
3
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D Lee. Offline reinforcement learning with realizability and single-policy concentrability. arXiv preprinl arXim:2202.0440
2022. 2
Mengyan Zhang, Thanh Nguyen-Tang, Fangzhao Wu, Zhenyu He, Xing Xie, and Cheng Soon Ong. Two- stage neural contextual bandits for personalised news recommendation. arXiv preprint orXiv:2206.1464 146488 2022.
A Appendix
A Proof of Theorem 5.1
We now provide complete proof of Theorem 5.1 The proof has four main components: a sub-oplimality decomposition for error propagation across iterations, a Bellman error decomposition using a uniform con- vergence argument, a deviation analysis for least squares with deep ReLU networks using local Rademacher complexities and a localization argument, and a upper bound minimization step obtain an optimal deep ReLU architecture.
15

---

Published in Transactions on Machine Learning Research (12/2022)
Step 1: A sub-optimality decomposition
The first step of the proof is a sub-optimality decomposition, stated in Lemma A.1 that applies generally any least-squares Q-iteration methods.
Lemma A.1 (A sub-optimality decomposition). Under Assumption 5.1 the sub-optimality of VK returned
by Algorithe i is bounded as
7k12
Fug max oskgk-1
11 Qu7Qul + (1 (1-7)1/3
for OPE,
SubOpt(Vx)
S
472+K/2
17 (1-7)²
max oskgk-1
11Q++1 - Qx + (1- (1-7)3/2
for OPL.
7)3/22
The lemma states that the sub-optimality decomposes into statistical error (the first term) and algo- rithmnc error (the second term). While the algorithmic error enjoys the fast linear convergence rate, the statistical error arises from the distributional shift in the offline data and the estimation error of the target Q-value functions due to finite data. Crucially, the contraction of the (optimality) Bellman operators 7 and allows the sup-optimality error at the final iteration K to propagate across all iterations E [0, K 1]. Note that this result is agnostic any function approximation form and does not require Assumption 5.2 The result uses a relatively standard argument that appears in number of works on offline RL Munos & Szeeesvári
2008
Le et al. 2019
Proof of Lemma A.1 We will prove the sup-optimality decomposition for both settings: OPE and OPL.
(i) For OPE. We denote the right-linear operator by pt.: (X' - R} - (X - IR where
(P" = / f(s's (')dd' P(ds')ss
for any f {X RR.. Denote Denote p² (dsda)= ((da))(dalss) Let E Q++1 - Vk E [0, and сx = Qo Q". Since Q" is the (unique) fixed point of T", we have
Q -- Q T= T=Q --- = 7P 1-11--0 QQ²) 1-
By recursion, we have
K
1-2K+1 K+1 K
Qx Q* = Σ
(npaakee =
a ApER
1 7 k=
k=0
where ay == ( FT, Vk [K] and A = (P Vk E [K]. Note that Σ ag = 1 and A 's are probability kernels. Denoting by lf] the point-wise absolute value [f(s, a)], we have that the following inequality holds point-wise:
1 - 7
K+1
QQ Q
or AulAll
7 0=0
16

---

Published in Transactions on Machine Learning Research (12/2022)
We have
(1 (1-2
/ ((ds))((aass)
K
1 Q71 I
On
(1 7)2
k=0
WV
(1 x
/ pdds))
(1 11-73 7/2
IA3
(1 (1- [1-
/ (dds))
a Ax
(1 - (1-7)8 7/2
k=
IAS
(1 11-7 +1
(1 p(ds))(ddass
(8, a) akk
(1-77) (1-7)²
k=0
(4) (1 (1- x+t
[uldd, [ldds, da) Σ
(
a a) + ak
(1 - 2]²
(1 11
K-11
Σ Cexxlllexll2 + ax
- 7)2
7k
(1 7)2 osks
Kig
max
||c
(1 (1-7)*
The inequalities (a) and (b) follow from Jensen's is inequality, (c) follows from 1|ooloo |10 S 1, and (d) that p² p² (PT)k I Kute. Thus we have
follows from Assumption 5.1
SubOpt(Vxx:n = VV - V
Pp 10 (s: a)] (x)
S Ep. [1Qx(s, (s,
$ V Ep. [[Qx Q (s,
10x 1=1|p=
RE max
2K/2
S 1 osksk-1
||el|x + (1 (1-7)1/2
The sup-optimality for the OPL setting more complex than the OPE setting but the tech- nical steps are relatively similar. In particular, let ck-1 = Qu, Vk and x² rs) arg max, Q* a), Vs, have
(ii) For OPL.
=T= Q- -T" QK-1QQ1--0 +1 T - Ox-1-T'O -K-I- EKK-1
50
S 7xp= (Q" - QK-1) +6K-1
K-1
k (p=)) kk ek 2 (p*((pF))) 11=t)((() (Q" Qu) (by recursion).
(2)
Now, let Thk be the greedy policy w.r.t. Qk, we have
Q' - -Q = Q" -x QK- + 1 T TT* tek-1
2 ppTk- (Q" - -KK-1)+ + CKK-
k-1
K k pra+) Des + 7 (ptk-1... (ro Qo).
(3)
k=
17

---

Published in Transactions on Machine Learning Research (12/2022)
Now, we turn to decompose Q" QTE as
-"= = (T Q- -T Qx) + (T" QK -T Qk) +(1 - -TTKQTK )
50
- S 7pp (Q" -Q" + p (Qx - ---+-+- -(TK)
Thus, we have
(I (I->PTAy (Q2 - Q*x) S > PPx) Qk).
Note that the operator
(1 - 7/ p )-1 -1 (>= p is monotone, thus
- Q >T - 7 p pr (Q" - Qk) >(1 pa - Qx).
(4)
Combining Equation
with Equations
and 3 we have
K-
k (p= k- KK-eex FEx + x jk+1 - 201) -Q0i)
Q < (I - 7pak)-1
(I (1-xpex)-1
y k- (prk pentt + tg ( (Q' -Qu)
km0
Using the triangle incquality, the above incquality becomes
-"* v 27(1 k
Ax Aalllll+axxte +xx -Qol)
71-
where
1 1-7 7 (T pmk ( (p=')k= + pax prott) .k < K,
A =
2
Ak = 1- 2 (I - --ppk)-1 (pr') + pak pp.....P .mo
2
0A 7 K- K- 1-1(1 7) (1 k) vk < K,
ak K (1 - 7) (11x)/(11,kkt))
Note that Ag is probability kernel for all k and Σn 0g = 1. Thus, similar to the steps in the OPE setting, for any policy x, we have
2y(1 - 2
(ʃ p(ds))((dass)
K-1
11Q- - Q -
(1-
Σ
a
A + +ak)
(1 72
k=0
2y(1 - +
(f
K-1
p(ds, da)
Σ
( + okk
(1 7)2
k=0
21(1 - +
axxx + +ar
(1 11-79 7)2
< 1y²kep
||cx|] + 4-
max osksk-1
(1 - 74
(1- 7)3
Thus, we have
2T max
2//22-1
SubOpt(7*)) = -1Q² -Q 10= -
p ||elll +
(1 - 732
(1 (1-7)3/22
18

---

Published in Transactions on Machine Learning Research (12/2022)
Step 2:
A Bellman error decomposition
The next step of the proof is to decompose the Bellman errois 1 for OPE and 1Q++1-TQulll for OPI. Since these errors can be decomposed and bounded similarly, we only focus on OPL here.
The difficulty in controlling the estimation error [[Q++1 Qxllul is that Qa itself is a random variable that depends on the offline data D. In particular, at any fixed k with Bellman targets {u where Vi r max, Q& (51; a'), it is not immediate that E [***)) sdlma] = for each covariate 2; == (8;, a:) as Qx itself depends on T; (thus the tower law cannot apply here). A naive and simple approach to break such data dependency of Qu is to split the original data D into K disjoint subsets and estimate each Qs using a separate subset. This naive approach is equivalent to the setting in Yang et al. (2019) where a fresh batch of data generated for different iterations. This approach however not efficient as it uses only n/K K samples to estimate each Qs. This is problematic in high-dimensional offline RL when the number of iterations K can be very large as it is often the case in practical settings. We instead prefer to use all n samples to estimate each Qx- This requires different approach to handle the complicated data dependency of cach Qs. To circumvent this issue, we leverage a uniform convergence argument by introducing a deterministic covering of T FNN- Each element of the deterministic covering induces a different regression target {r, + y max, Q(s,, a ) E (rr + y maxa ('s), (x;))a) = In particular, we denote
1 where Q is a deterministic function from the covering which ensures that
max max Qu d'), and for == QK+1 = arg inf JEFNN
Σ ((f(z)) "*,, and 1 = =T"Qu:
Vi = = -
a'
where ((x, v) = (x= - y)² is the squared loss function. Note that for any deterministic Q E FNN, we have (21) Ely Elyi|21) [z]), Vxr, thus
B(ly - -15-
(5)
where Iy denotes the random variable (f(z)) - /2 for a given fixed Q. Now letting 1 = arg JEFNN Ilf 121,,,1 be the projection of fo onto the function class FNN, have
(a) || - T Qx - = max 1I - 110 S max k
11ʃ2- - 119-199122 (b)
sup QEINN
sup QETNN
Bllja 190)
&
(c)
{ [E(10 - (110) + +B -p00)}
sup QETNN
sup (E (E-Ex)) E1 - 11,8) + En (1/ - (1)
QETNN
sup (E - En)(1fa - -1/ sup En (l 10)); QE
(6)
NNN
I emmpiriaa process term
1iss term
where (a) follows from that Qs E FNN, (b) follows from Equation and (c) follows from that En S E.. Fo E FNN- That is, the error is decomposed into two terms: the first term In resembles the empirical process in statistical learning theory and the second term Ig specifies the bias caused by the regression target S not being in the function space FNN.
Step 3: A deviation analysis
The next step is to bound the empirical process term and the bias term via an intricate concentration, local Rademacher complexities and a localization argument. First,, the bias term in Equation 6 is taken uniformly over the function space, thus standard concentration arguments such as Bernstein's inequality Szepesvári (2008): Le et al. (2019) do not apply here. Second,
and Pollard's incquality used in Munos local Rademacher complexities (Bartlett et al.) 2005) are data-dependent complexity measures that exploit the fact that only a small subset. of the function class will be used. Leveraging localization argument for
19

---

Published in Transactions on Machine Learning Research (12/2022)
local Rademacher complexities (Farrell et al. 2018). localize empirical Rademacher ball into smaller balls by which we can handle their complexities more effectively. Moreover, we explicitly use the sub-root function argument to derive our bound and extend the technique to the uniform convergence case. That is, reasoning over the sub-root function argument makes our proof more modular and casier to incorporate the uniform convergence argument.
Localization is particularly useful to handle the complicated approximation errors induced by deep ReLU network function approximation.
Step 3.a: Bounding the bias term via a uniform convergence concentration inequality
Before delving into proof, introduce relevant notations. Let = - Ne,,F, II- be the e-covering number of F w.r.t. I| norm, H, -I- == log N(e, be the entropic number, let NI || () be the bracketing number of F, i.e. the minimum number of brackets of || |l-size less than or equal to E, necessary to cover F, let H (e, (e, F, || I]) = log Nf, II) be the || -ll-bracketing E / E F), and let T = (T SE Finally,
G), let
metric entropy Fllet = ((((
for sample set {=r we define the empirical norm [| == V E f(x,)2
We define the inherent Bellman error dFEN == SUPQETxN inf JEFxN ||ʃ T TmQlpp-
This implies that
dAAN= = sup inf QEFNx JEINN
- = sup
Blly - -1)))
(7)
QEANN
We have
1 - 4lf and 1 - lul S 8.
We have
H(c - 13 : Q Fuull(z,
< <H( ( 159 f0 fxN) 111)
< Hi (F- - T FNNN - ) n -1 11.1
H 5. [ n 11 111) H e
T FNN Fn l11)
g:
- 11 G F || (1)) + 1 e T FNN, 11,0)
(
For any d'> 0 and 8' E (0, it follows from Lemma B.2 with 11/2 and E?, with probability at least 8,, for any Q E FNN, we have
1 11,0) 33 - +c2 S3dk + +c²
(8)
given that
1
1og(4/8)) + log EN 40 - FxN)) -1 lla)
"
n R e2
Note that if we use Pollard's incquality (Munos & Szepesvári 2008 in the place of Lemma B.2 the RHS
of Equation [8] is bounded by instead of Li.e. n scales with O(1/e1) instead of ((1e²)) In addition, unlike Le et al. ).19), the uniform convergence argument hinders the application of Bernstein's inequality. We remark that Le al. 2019 makes mistake in their proof by ignoring the data-dependent structure the algorithm (i.e., they wrongly assume that Q* in Algorithm [ fixed and independent of {s, 1=). Thus, the uniform convergence argument in
proof is necessary.
20

---

Published in Transactions on Machine Learning Research (12/2022)
Step 3.b: Bounding the empirical process term via local Rademacher complexities
For any Q E FNN; we have
1 - 1 2 f.1 12
V - 1 s Bll - - 4B( - 1,0)2
Thus, it follows from Lemma (with a 1/22 that with any > 0, 8 E (0, 1), with probability at least. 1 1-6 6, have
sup - En) - (12) Q FNx, 121 sr}
S suup( - En) 11): E FNN,NEETTEE ||/ - -9l sr}
2r log (1/0)
28 log (L/6)
3ER,, {41 1 I - 5r} + +2/
n
3n
2r log(1/))
28 (1/6)
< 6ER (s-9: E ENN, FNN 9912 sr) + 2/
n
3n
Step 3.c: Bounding ||x+1 - Qu using localization argument via sub-root functions
We bound - - using the localization argument, breaking down the Rademacher complexities into local balls and then build up the original function space from the local balls. Tet th be a sub-root function Bartlett et al. 2005 Definition 3.1) with the fixed point r. and assume that for any 2 T., we have
((r) 2 3ERn {s 9= E TT 911. sr).
(9)
We recall that function 1b : [0, 00) 10, oc) is sub-roof if is non-negative, non-decreasing and (/rr /F is non- non-increasing for r > 0. Consequently, sub-root function & has a unique fixed point where (r.). In addition, (b)) I /PT., Vr 2 r.. In the next step, we will find a sub-root function vp that satisfics the inequality above, but for this step we just assume that we have such & at hand. Combining Equations (
and 9 we have: for any r 2 and any 8 E (0, 1), if ff f 112 r, with probability at least 8
2r (2/)
28 (og(2/))
[1 12
12,0 S 2()()) + +2
+ 3dz + C2
n
3n
2r 2ogg2(2/8)
28 log(2/))
S Vrr. +2
+ (V3dy + E)P
n
3n
where
[log(8/8) + log EN 12
n 2
(FNN T FNN) -
20
Consider To 2 r. (to be chosen later) and denote the events
B = [1= - 112, S 2hrr), Ak (0, 1, ".....!}. l].
where / = logg < logz(
). We have By S B1 C ... C B₁ and since || - gll < 1, V. Ig S 1, we have P(B)) = 1. If pQu-1 -- 1/3 < 2'ro for some < I, then with probability at least - 5, we have
2i+ log (2/5)
28 2810g(2/6)
11 01--1 1 < V2rrrr + 22
+ (v3dFxx + +
n
3n
2' 2
21

---

Published in Transactions on Machine Learning Research (12/2022)
if the following inequalities hold
2i+1 log(2/8)
1
2'r + +2
2í
Voo
"
2
28 (2/()
1
+ (V3dFxx +6)²
7 2/
20-1ro-
ro-
3n
2
We choose ro 2 ro such that the inequalities above hold for all Si 1. This can be done by simply setting
Vru = 2 V2'rr + 2
2 1og(2/6)
2
28 log(2/6)
+ (v3dSwN + tc)2)
+ *1
n
i=0
2'-1
3n
i=0
S dNNN + (log(2/0) /
Vr..
Since {Bi} is a sequence of increasing events, we have
P(Bb) P(B1) P(B P(B2) P(B2 n BB) P(B n BB)
1-1
= P(BI) - Σ P(B41 n B5) 2 1 18.
1m
Thus, with probability at least 1 8, we have
11 - f-a-111u dANN + + 1og(21/8)
+ vr.
(10)
where
(1o((8100) log EN (FNn
R 4e
20
Step 3.d: Finding a sub-root function and its fixed point
It remains to find a sub-root function (br) that satisfics Equation and thus its fixed point. The main idea is to bound the RHS, the local Rademacher complexity, of Equation (9) by its empirical counterpart as the latter can then be further bounded by a sub-root function represented by a measure of compactness of the function spaces JNN and T FNN-
For any > we have the following inequalities for entropic numbers:
H(G,FNN T FNN, |l (1x)) Fus, 11- + H(c/2, T FNN, IIm),
(a)
H(c, |l 11x) < FNN [a ||- blxe) S Ni N)² + log(1/e)]
(11)
FNN, 11xx)) < H(e, T FNNN |1b0) < (2e, JNN, || (1b))
(b) < (2c, (2c B (x), |loc) S (26) 12aa
(c)
(12)
where is a hyperparameter of the deep ReLU network described in Lemma
B.9 (a) follows from Lemma
B.9. and (b) follows from Assumption 5.2 and (c) follows from Lemma B.8 Let H FNN T TNNN it
22

---

Published in Transactions on Machine Learning Research (12/2022)
follows from Lemma B.5 with (Ex: := c/2 JKEN for any 0 that
H(c/24-1
1.H. 1lm)
E, Rxih E H- H: 11bl1n { S 4
2
k=1
6
H(e/2t, FNN, 11 1100)
H(c/2", TM |1 ..100)
< <4>
+4 4
2k-1
2k-1
n
k=1 1
k=1
4e
-(k- (k-1)) 2
V . (log N)2 + (2))))))) +
vn
4e
Σ
20
2
(k--1)
V
2k-1
c
d//a
k=1
k=
d' :
N[oog + log(1//))
+
vn
vn
(x-zz k-1
where we use Va + u va vb, Va, b 0. Exm
v 2
< oc, and Ex=1
< 00.
It now follows from Lemma B4 that
Bg Rr
(S (. || 3 r}
(c/2, 12,1,,11,111111 1ln)
H H: 11bl1 <c} + inf Eg fhe
n
V ([ooog +og (1){) + c :/4
2r
2r
2
V N ((log + log(4/e)) + V 1= (e/2) .m
8
xn 8-112 [log* N logn) + n 8(1 -8(1-11-----
No -1/2
1/2
V N + logg) + Vrn = (
24 (r))
where 3 E (0. 9) is an absolute constant to be chosen later.
Note that V((f - < [ g)*| S IB[[ - g} for any f E FNN.9 E FNN. Thus, for any r 2 T.r it follows from Lemma B.1 that with probability at least 1 1 I E FNN,9 9 E FNx such that || g S r,
n' we have the following incquality for any
|/5 1--9 -91l
2r log n
56 log n
$ ||f - gl1 + 3ER, [(f 9)² E ENN 1lf - -gll. Sr) +
3 n
2r log n
56
log n
$ || - g1 + 3ER, (1 g:: E FNN,9 E FNN, - -gl sr) +
3
n
S r + (()) +r 4r
ifr 2 V.V zoogn y 5ölegn
For such r, denole E, = -15--11 S 44) S Sr), we have P(E,) 2 1 1- -1/n
and
3ER g:fe FAN. If - all; sr}
-EE,, RnIf -9:f T llf 91|2 sr}
< 3E
Eo -g:f fE F g
2 <r) + (1- LE.)
< 3E
E. Raff g: f FN 5
S 4r + (1 (1-1 (1)1)
$ ((1)(4)) +
I -n-1/2
Nlogg 2 N + logn) + n
-0-0(1-
1/2 -1--)) -1/1
N(log* N + +lg n)
n
+ Vin ビ11 (1--2 26) ::
23

---

Published in Transactions on Machine Learning Research (12/2022)
It is easy to verify that (br)) defined above is sub-root function. The fixed point r, of (b(r) can be solved analytically via the simple quadratic equation (/(r)). In particular, we have
Vra S n 1/2 N(log² N + logn) + n 21 2 +n 2- 222 N + logn))
11 ) 1/2
5 n (120111)+1) (logg² N + logn) + n - =x) + 4 +t + 11/2
(13)
It follows from Equation (where S log(1/r.)), the definition dINNY Lemma B.9 and Equation 13 that for any è' > 0 and å (0, 1), with probability at least 1 8, we have
max 11 Qxll SN +e' + (((23)11)+1) N N + log + t 31-
+n 91 - 1/2 Iog (1/6) + log logn.
(14)
where
log(1/8) + log logn n + log EN
_.- (FNN - FxN= 1 -111))))))))
"
n 2 4e
(15)
20
Step 4: Minimizing the upper bound
The final step for the proof is to minimize the upper error bound obtained in the previous steps w.r.t. two free parameters 3 (0, a) and N E N. Note that N parameterizes the deep ReLU architecture &(L, m, S, B) given Lemma B.9 In particular,
optimize over 3 E (0) and N E N to minimize the upper bound in
the RHS of Equation
14]. The RHS of Equation [14 is minimized (up to log n-factor) by choosing
N = n (2 and B = (2 a(a + d)
de
+
(16)
which results x (23+11) zata At these optimal values, Equation 14 becomes
max 1Q @*ll S é' + n =) log n + n 1/2 log(1/8) + log log
(17)
where we use inequalities n [1 -
=. 1 < n (1--d) a-a/d (129
Now, for any e > O, we set é' = c/3 and let
= log n S c/3 and n 1/2 /log(1/0) + log log n S c/3.
n
- It then follows from Equation 17 that with probability at least 1 - 6, we have max -|Q++1- T Se
if n simultancously satisfies Equation
15 with = e/3 and
(log² n) u & and 2 (log(1/8) + log logn).
1
(18)
2
Next, derive explicit formula of the sample complexity satisfying Equation 15 we have that satisfies Equation
Using Equations
14
18
and 16
15
if
28+1 2
(log² log(1/e))
n
2a
l+
(19)
(log(1/8) + log logn).
24

---

Published in Transactions on Machine Learning Research (12/2022)
Note that 1/2 and 2; thus, we have
28 +
d
)²
S14 d 3.
1
2
2a +
Hence, satisfies Equations
18 and
19
if
1+
log + 2 (log(1/6) + log log n).
2
B
Technical Lemmas
Lemma B.1 (Bartlett al. (2005 )
Let and let
FC [a.b] v[f(x)) r
1. For any À 0, have with probability at least 1 - -
2r>
1
sup SEF
[Ef Enf) - inf as0
2(1 + aa RR +
+ (b a)
+
2. With probability at least 1 - 2e-
2(1+a)
Eg [R Fl + 1rr + (b a) (1
+ a
sup (Ef - Enf) S inf aE(0.1)
feF
(1 (1-a)
3 a 2a - a) 12
Moreover, the same results hold for supjer (En Ef)
Lemma B.2 Györfi al. [2002] Theorem 11.6)). Let 2 1 and F be a set of functions f Rd - [0, B). Let i,,... On be i.ddd Rd-valued random variables. For any a 0, O<e<l, and 1, we have
P sup 1E,,((2) -(A feFa+ 1 (Z)) {e)
aE 4EN( ( Flz, n 1 exp
-3
40B
Lemma B.3 (Contraction properly Rebeschini
Let Φ :R + R. be L-Lipschilz, then 2019
Eg Ry (6 o F) S R,,
Lemma B.4 (Lei et al. 2016 Lemma 1)). Let F be function class and Pa be the empirical measure supported on X XI..., Xn v ~ then for any > (which can be stochastic w.r.t Xi), we have
Ra F: 1: set 2r log (e/2 11 1lm)
E, E 1f1l snf
inf e0
Lemma B.5 Lei et al. 2016 modification)). Let XI,.., X, be a sequence of samples and Pa be the associated empirical measure. For any function class and any monotone sequence {E decreasing to 0, we have the following inequality for any non-negative integer N
log,N(Ex. F. 1ln) + En-
R. EF :111 < {o) <4 Ek-11
7
1=1
25

---

Published in Transactions on Machine Learning Research (12/2022)
Lemma B.6 (Pollord's inequality). Let F be set of measurable functions X - [0, and let 0, arbilrary. If (x:) is an i.i.d. sequence of random variables taking values in X, then
1 N
> >0)
P
sup fer
((X))
ST (N(c/8,
Lemma B.7 (Properties of (bracketing) entropic numberr). Let E (0, We have
H(c,F,111 II) - H (2c,
He,,, ((a 1/p. || (lb) = HI(EFF || llan)) & (( l (eFFF (loo) for all {ri)i-1 C (Fm
3. [( F, II) & 2H( (D,, where F F= 15 - f.g
Lemma B.8 (Entropic number of bounded Besov spaces (Nickl & Pötscher 2007 1 p.9 00 and d/p, have
Corollary 2.2)). For
Hn B (2), Se
Lemma B.9 (Approrimation power of deep ReLU networks for Besov spaces (Suzuki 2018 modified version)). Let p.q S and E (192, 00). For sufficiently large N N, there ewists neural network architecture & m, S, B) with
L x log N, m N log N,S N, and B Nd 4t
where ;:=
9-6 and 8 = d(p (1 + [a]) such that 28
inf f.e (E.(L.
sup
|| - Salloo S N-ajd
26


Reviews:
[{"review_id": "c8Da7L5Cu4", "reviewer": "Reviewer_HrkQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper proves a more general sample complexity result when $T^\\pi f$ belongs to a Besov class whenever $f \\in \\mathcal F$. Specifically, prior works have shown similar results for Holder classes or with finite classes.\n- There are comparatively fewer theoretical works addressing neural networks for offline RL despite widespread usage of them in practice and so it is timely and contributes to filling the knowledge gap.\n- The rates seem to be very close to existing work, but with potentially more general conditions.\n- The algorithm does not require sample splitting unlike prior work.\n\nWeaknesses\n- There are several notable clarity issues regarding the assumptions about completeness (5.2) and other claims. See questions in the next section.\n- The analysis does not seem too novel (see also questions about this), but this isn’t a big deal as long as the claims are accurate, as per TMLR guidelines.\n- It could be argued that 5.1 is strong, but, given that papers have only recently been addressing weaker coverage conditions and there are still many interesting problems involving 5.1, I think it is acceptable for now.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of sample complexity for offline RL (OPE and OPL) using neural network function approximators. In particular, the authors study the general case of neural networks satisfying a Besov condition, which is more general than prior analyses. Sample complexity bounds are presented for OPE and OPL and they are comparable to existing works. The underlying Besov condition, which replaces a typical completeness condition, requires that for any $f \\in \\mathcal F$, $T^\\pi f$ is in the Besov space. The analysis avoids sample splitting.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "_Major things_\n\n- There is one important question which I feel is not properly addressed in the main text. This paper claims that the condition subsumes all previously made completeness conditions and goes on to state model-based assumptions like the linear MDP. But such model-based assumptions are generally not the ones used to analyze offline RL problems. Existing literature is often concerned with more generic completeness conditions like $f \\in \\mathcal F \\implies T^* f \\in \\mathcal F$, which doesn’t explicitly constrain the MDP (only implicitly). It has been shown many times that this along with Assumption 5.1 is sufficient (Chen and Jiang, 2019) and more recently it has been shown that sample efficient learning is not possible without it (in general). If completeness is not fully satisfied, one usually sees some approximation error term show up. So my question is the following. Does Assumption 5.2 and the requirement in the second part of Theorem 5.1 implicitly constrain the problem so that the approximation error is zero? Judging from the analysis, it seems this is indeed the case. It also seems to be the case in Yang et al. I hope the authors can clarify. If the answer is yes, I believe it is necessary to be upfront about this since these subtle parts of the assumptions are of great importance in the surrounding literature.\n\n- Additionally this seems to lead to a chicken-and-egg problem: Assumption 5.2 is assumed to hold at the start of Theorem 5.1 (presumably with $\\alpha$, $p$, and $q$ set according to the defined class $\\mathcal F$). But at the end of the theorem statement, the parameters of $\\mathcal F$ are chosen according to $\\alpha$. So my question to the authors is: how should we interpret the “order of operations” here. What should really go first? Should we assume that all functions $f \\in (\\mathcal S  \\times \\mathcal A \\to \\mathbb R)$ satisfy $T^\\pi f \\in B$ for this particular MDP but it is sufficient to consider the restriction to $\\mathcal F$ with those parameters in Theorem 5.1? Or should we say that $\\mathcal F$ is given and happens to satisfy 5.2 and the conditions in Theorem 5.1 simultaneously?\n\nThe latter seems more reasonable to me. But then I think the statement of Assumption 5.2 should be corrected. It should perhaps say there exists p, q, \\alpha such that (L, m, S, B) satisfy those conditions originally stated in Theorem 5.1 and T^\\pi \\in B. This is less general than before, but, in my view, this is the correct way. \n\n- The exponential dependence on d is a bit jarring but there is also a requirement that $\\alpha = \\Omega (d)$ in Assumption 5.2, which somehow makes this okay. But I am wondering if this requirement is just trivializing problem. Can the authors clarify this part?\n\n_Minor things_\n\n- Typical completeness conditions require that $f \\in \\mathcal F \\implies T^* f \\in \\mathcal F$ but Assumption 5.2 says that this must hold for all $T^\\pi$ operators. Is this really necessary? Why?\n\n- The claims about K -> inf in Yang et al are a bit strong. While this is undesirable practically, the language is a bit harsh. K need only be logarithmically large, which is really not that bad and you often see similar data splitting methods in many fields like robust estimation, so it is not totally unimaginable that someone would do this.\n\n- “This correlated structure hinders a direct use of the standard concentration inequalities. We overcome this technical difficulty using uniform convergence argument.”\n\nI do not think these two are mutually exclusive. You can use concentration inequalities to prove uniform convergence results…\n\n- I’m a little skeptical about the claims of how novel this “double uniform convergence” analysis is. Prior works like Chen and Jiang (and earlier works referenced in their paper) have handled this and they did not give it special treatment. Granted, analyses are typically a lot less messy when the function classes are finite, but the principle is the same and I think this should be made clear in the paper.\n", "broader_impact_concerns": "I do not have any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wZeVRIW9Cd", "reviewer": "Reviewer_2FTk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) Offline RL with nonlinear function approximation is a very challenging problem. Under practical settings, neither the convergence nor the global optimality guarantee can be guaranteed. This paper provides a new framework to establish some interesting results.\n(2) Overall, this paper is easy to follow.\n(3) The theoretical result guarantee and algorithm structure have some advantage over some previous works.\n\nWeakness:\n(1) Although assumption 2 is acceptable given the challenging setting this paper cares about, assumption 1 is a little bit strong compare with many SOTA works, since they only requie nonzero distribution coverage in state-action pairs that are also non-zero in target/optimal policy distributions. Given assumption 2 in this paper, many technical difficulties can be avoided. Although it might be the case that under the deep nerual network and Besove assumptions previous coverage assumption may not be able to lead to a reasonably good bound. If that is the case, the author might need to add some comments here to illustrate why previous coverage assumption can not be adopted here.\n\n(2) The \"uniform bound\" techniques have been widely used in previos regret based RL analysis to handle the dependence between samples. The \"double uniform convergence argument\" in this paper is more like a nature adaptation of previous work due to the nature of the problem instead of proposing a new technique. The author might need to further demonstrate their novel regarding this.\n\n(3) When comparing with other works, it might be fair to include one column of coverage assumption that they adopted.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the sample complexity of offline policy evaluation/optimization under deep ReLu neural network approximation. The theoretical analysis is conducted under two key assumptions: (1) \"Besov dynamic closure\" and (2) behavior policy distribution coverage and the proposed algorithm adopts a standard LSQI structure. Under those two assumptions, the author established the suboptimality guarantee of their proposed algrithm in OPL and OPE problems. The author also compare their theoretical results with some state-of-the-art results that under tabular or linear MDP assumptions to demonstrate the significance of their work.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "See my comments in weakness.", "broader_impact_concerns": "This is a theoretical work and does not hav significant ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q75qtNsypX", "reviewer": "Reviewer_saLt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Extend the scheme of function approximation from reproducing kernel Hilbert spaces and Hölder spaces to Besov spaces.\n* Provide a new method to decouple the dependency of $Q$ estimate with the data.\n\nWeaknesses:\n* The technical part is not so novel. It basically integrates the technical components of the statistical analysis on Besov spaces to standard offline reinforcement learning with general function approximation. The main technical improvement for reinforcement learning is on decoupling the $Q$ estimate from the data, which is relatively straightforward with the idea of uniform convergence.\n* The presentation is poor.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors proposed to perform offline reinforcement learning in Besov space, which can be represented with deep ReLU networks under certain sparsity and norm constraints. Under the assumption that the function class is Bellman complete, the authors show the PAC guarantee of the FQI algorithm for both offline policy evaluation and offline policy learning. The main technical novelty is a uniform concentration on the $Q$ estimator for each iteration, which avoids the data-splitting.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* If the authors claim the data-splitting will lead to severe issues, the authors should explicitly claim the dependency on $K$. If I understand correctly, we only require $K = O(\\log(1/\\varepsilon))$ to make the algorithmic error at a order of $\\varepsilon$, which, for me is not an issue in both theory and practice. \n* For the sub-optimality of offline learning, a proper definition should be $V^{\\hat{\\pi}}(s)$. I don’t see the reason we should use $Q^*$, as in the following steps we don’t follow $\\pi^*$ as well.\n* In the definition of the moduli of continuity and the Besov space, you already assume $\\mathcal{X} = \\mathbb{R}$, as the difference you use is $0\\leq h \\leq t$ instead of any other increment. I would like to argue that the authors need to discuss the topology of $\\mathcal{X}$ at the beginning. This makes me puzzled as in reinforcement learning our state and action are never one dimensional.\n* The statements in Remark 3.1 are repeating.\n* The claim on the hardness of the correlated data claimed in Section 4 is hard to follow. I guess the authors would like to argue that $Q$ is estimated with $x_i$ in the last iteration, but we can decouple this dependency via a uniform convergence on $Q$.\n* I don't understand the reason we don't return $V^\\pi$ with the Bellman equation in Line 7 of the Algorithm 1.\n* I’m not aware of any provable algorithms within polynomial time for optimizing sparse neural networks (with $\\ell_0$ constraints), hence the claim in Section 4 is not proper. I hope the authors can provide references on that.\n* Assumption 5.2 is just the Bellman completeness assumption that is widely used in reinforcement learning with general function approximation. I would claim that this assumption is in fact hiding lots of the issues, and make the original problem back to a statistical estimation problem with Besov space.\n* Example 5.3 is not an example.\n\n\n", "broader_impact_concerns": "This work focus on the theoretical analysis, so I believe it does not require any broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have conflicting views about the novelty and the impact of the work, but all agree that the paper is a solid contribution. The primary concerns are threefold.  1. The completeness assumption is strong (stronger than existing work that operates in simpler settings).  2. The "double uniform convergence" technique is not as novel as the authors indicated initially.  3.  The exponential dependence on the dimension is unsatisfactory.

I find the first two concerns valid, but the authors have submitted a revision that clearly carves out a niche for them and had a more modest claim on the novelty. I think the revision is satisfactory.  There is nothing the authors could do for the third concern because Besov space is so large that the "curse of dimension" is unavoidable even in simpler supervised learning settings.  In some sense, only because Besov space is so large, it is possible for functions --- after Bellman backups --- could possibly be still in the space. 

Under these arguments, I think that the paper passes the correctness and relevance bar for TMLR and the results should be made known to RL theory people.  I think the authors could have done a better job in giving examples of Besov space functions so as to motivate the study a bit more. For example, whenever "max" is involved, it is hard to argue that the resulting function out of the Bellman operator is still within the same smooth function class, because it essentially becomes piecewise. Yet, it could still be within the Besov function with a small \alpha parameter. 

I have one more concern about the specific assumptions and one other item on my wishlist that I hope the authors discuss in the final version of the paper.

1. In Assumption 5.2, the claim is that for any neural network, after passing it through a Bellman operator, it sits inside a Besov class.  However, even neural networks are not in Besov classes with \alpha > 1 (which requires higher order differentiability).   NN can "improperly" approximate Besov class functions of any order of smoothness in L_infty but cannot exactly recover Besov space functions.

2. The authors should have discussed the optimality of the rates.  It is hard for me to read it off from the current results. It appears to be suboptimal?  If the authors can construct a lower bound showing that the current rate is minimax optimal then the results would be significantly stronger.  It is not required because the current paper passes the bar, but I think it is a result that should naturally go into the same paper if easily provable.

Decision: Accept (poster)