# Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks

Thanh Nguyen-Tang
&Sunil Gupta
&Hung Tran-The
&Svetha Venkatesh
&Applied Artificial Intelligence Institute (A2I2)
Deakin University, Australia Corresponding<EMAIL_ADDRESS>
###### Abstract

We study the statistical theory of offline reinforcement learning (RL) with
deep ReLU network function approximation. We analyze a variant of fitted-Q
iteration (FQI) algorithm under a new dynamic condition, namely Besov dynamic
closure, which encompasses the conditions from prior analyses for deep neural
network function approximation. Under Besov dynamic closure, we prove that the
FQI-type algorithm enjoys the sample complexity of
$\tilde{\mathcal{O}}\left(\kappa^{1+d/\alpha}\cdot\epsilon^{-2-2d/\alpha}\right)$
where $\kappa$ is a distribution shift measure, $d$ is the dimensionality of
the state-action space, $\alpha$ is the (possibly fractional) smoothness
parameter of the underlying MDP, and $\epsilon$ is a user-specified precision.
This result improves over the sample complexity of
$\tilde{\mathcal{O}}\left(K\cdot\kappa^{2+d/\alpha}\cdot\epsilon^{-2-d/\alpha}\right)$
in the prior result (Yang et al., 2019) where $K$ is an algorithmic iteration
number which is arbitrarily large in practice. Importantly, our sample
complexity is obtained under the new general dynamic condition and a data-
dependent structure where the latter is either ignored in prior algorithms or
improperly handled by prior analyses. This is the first comprehensive analysis
for offline RL with deep ReLU network function approximation under a general
setting.

##  1 Introduction

Offline reinforcement learning (Levine et al., 2020) is a practical paradigm
of reinforcement learning (RL) where logged experiences are abundant but a new
interaction with the environment is limited or even prohibited. The
fundamental offline RL problems are how well previous experiences could be
used to evaluate a new target policy, known as off-policy evaluation (OPE)
problem, or 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 use function approximation such as deep neural
networks to generalize across states from an offline dataset without any
further exploration. Such problems form the core of modern RL in practical
settings, but relatively few work provide a comprehensive and adequate
analysis of the statistical efficiency for the problems.

On the theoretical side, predominant sample efficiency results in offline RL
focus on tabular environments with small finite state spaces (Yin and Wang,
2020; Yin et al., 2021; Yin and Wang, 2021), but as these methods scale with
the number of states, they are infeasible for infinitely large state space
settings. While this tabular setting has been extended to large state spaces
via linear environments (Duan and Wang, 2020), the linearity assumption often
does not hold for many RL problems in practice. More relevant theoretical
progress has been achieved for more complex environments with general and deep
neural network function approximations, but these results are either
inadequate or relatively disconnected from practical settings (Munos and
Szepesvári, 2008; Yang et al., 2019; Le et al., 2019). In particular, their
finite-sample results either (i) depend on a so-called inherent Bellman error
(Munos and Szepesvári, 2008; Le et al., 2019), which could be arbitrarily
large or uncontrollable in practice, (ii) avoid the data-dependent structure
in their algorithms at the cost of losing sample efficiency (Yang et al.,
2019) or improperly ignore it in their analysis (Le et al., 2019), or (iii)
rely on relatively strong dynamics assumption (Yang et al., 2019).

In this paper, we study a variation of fitted-Q iteration (FQI) (Bertsekas et
al., 1995; Sutton and Barto, 2018) for the offline RL problems where we
approximate the target $Q$-function from an offline data using a deep ReLU
network. The algorithm is appealingly simple: it iteratively estimates the
target $Q$-function via regression on the offline data and the previous
estimate. This procedure, which intuitively does the best it could with the
available offline data, forms the core of many current offline RL methods.
With linear function approximation, Duan and Wang (2020) showed that this
procedure yields a minimax-optimal sample efficient algorithm, provided the
environment dynamics satisfy certain linear properties. While their
assumptions generalize the tabular settings, they are restrictive for more
complex environment dynamics where non-linear function approximation is
required. Moreover, as they highly exploit the linearity structure, it is
unclear how their analysis can accommodate non-linear function approximation
such as deep ReLU networks.

In this paper, we provide the statistical theory of a FQI-type algorithm for
both OPE and OPL problems with deep ReLU networks. In particular, we provide
the first comprehensive analysis for offline RL under deep ReLU network
function approximation. We achieve this generality in our result via two novel
considerations. First, we introduce Besov dynamic closure which is, to our
knowledge, the most general assumption that encompasses the previous dynamic
assumptions in offline RL. In particular, our Besov dynamic closure reduces
into Hölder smoothness and Sobolev smoothness conditions as special cases.
Moreover, the MDP under the Besov dynamic closure needs not be continuous,
differentiable or spatially homogeneous in smoothness. Second, as each value
estimate in a regression-based offline RL algorithm depends on the previous
estimates and the entire offline dataset, a complicated data-dependent
structure is induced. This data-dependent structure plays a central role in
the statistical efficiency of the algorithm. While prior results ignore the
data-dependent structure, either in their algorithm or their analysis,
resulting a loss of sample efficiency or improper analysis, respectively, we
consider it in a FQI-type algorithm and effectively handle it in our analysis
(this is discussed further in Section 2 and 4). Under these considerations, we
establish the sample complexity of offline RL with deep ReLU network function
approximation that is both more general and more sample-efficient than the
prior results, as summarized in Table 1 which will be discussed in details in
Subsection 4.3. Moreover, as our technical proof combining a uniform-
convergence analysis and local Rademacher complexities with a localization
argument is sufficiently general and effective in handling complex function
approximations, our proof could be of independent interest for other offline
RL methods with non-linear function approximation.

##  2 Related Work

The majority of the theoretical results for offline RL focus on tabular
settings and mostly on OPE task where the state space is finite and an
importance sampling -related approach is possible (Precup et al., 2000; Dudík
et al., 2011; Jiang and Li, 2015; Thomas and Brunskill, 2016; Farajtabar et
al., 2018; Kallus and Uehara, 2019). The main drawback of the importance
sampling -based approach is that it suffers high variance in long horizon
problems. The high variance problem is later mitigated by the idea of
formulating the OPE problem as a density ratio estimation problem (Liu et al.,
2018; Nachum et al., 2019a; Zhang et al., 2020a, b; Nachum et al., 2019b) but
these results do not provide sample complexity guarantees. The sample
efficiency guarantees for offline RL are obtained in tabular settings in (Xie
et al., 2019; Yin and Wang, 2020; Yin et al., 2021; Yin and Wang, 2021). A
lower bound for tabular offline RL is obtained in (Jiang and Li, 2016) which
in particular show a Cramer-Rao lower bound for discrete-tree MDPs.

For the function approximation setting, as the state space of MDPs is often
infinite or continuous, some form of function approximation is deployed in
approximate dynamic programming such as fitted Q-iteration, least squared
policy iteration (Bertsekas and Tsitsiklis, 1995; Jong and Stone, 2007;
Lagoudakis and Parr, 2003; Grünewälder et al., 2012; Munos, 2003; Munos and
Szepesvári, 2008; Antos et al., 2008; Tosatto et al., 2017), and fitted
Q-evaluation (FQE) (Le et al., 2019). A recent line of work studies offline RL
in non-linear function approximation (e.g, general function approximation and
deep neural network function approximation) (Le et al., 2019; Yang et al.,
2019). In particular, Le et al. (2019) provide an error bound of OPE and OPL
with general function approximation but they ignore the data-dependent
structure in the FQI-type algorithm, resulting in an improper analysis.
Moreover, their error bounds depend on the inherent Bellman error that can be
large and controllable in practical settings. More closely related to our work
is (Yang et al., 2019) which also considers deep neural network approximation.
In particular, Yang et al. (2019) focused on analyzing deep Q-learning using a
fresh batch of data for each iteration. Such approach is considerably sample-
inefficient in offline RL as it undesirably does not leverage the past data.
As a result, their sample complexity scales with the number of iterations $K$
which is very large in practice. In addition, they rely on a relatively
restricted smoothness assumption of the underlying MDPs that hinders their
results from being widely applicable in more practical settings. We summarize
the key differences between our work and the prior results in Table 1 which
will be elaborated further in Subsection 4.3.

Since the initial version of this paper appeared, a concurrent work studies
offline RL with general function approximation via local Rademacher
complexities (Duan et al., 2021). While both papers independently have the
same idea of using local Rademacher complexities as a tool to study sample
complexities in offline RL, our work differs from (Duan et al., 2021) in three
main aspects. First, we focus on infinite-horizon MDPs while (Duan et al.,
2021) work in finite-horizon MDPs. Second, we focus on a practical setting of
deep neural network function approximation with an explicit sample complexity
while the sample complexity in (Duan et al., 2021) depends on the critical
radius of local Rademacher complexity. Bounding the critical radius for a
complex model under the data-dependent structure is highly non-trivial. Duan
et al. (2021) provided the specialized sample complexity for finite classes,
linear classes, kernel spaces and sparse linear spaces but it is unclear how
their result applies to more complex models such as a deep ReLU network.
Importantly, we propose a new Besov dynamic closure and a uniform-convergence
argument which appear absent in Duan et al. (2021).

##  3 Preliminaries

We consider reinforcement learning in an infinite-horizon discounted Markov
decision process (MDP) with possibly infinitely large state space
$\mathcal{S}$, continuous action space $\mathcal{A}$, initial state
distribution $\rho\in\mathcal{P}(\mathcal{S})$, transition operator
$P:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}(\mathcal{S})$, reward
distribution $R:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}([0,1])$,
and a discount factor $\gamma\in[0,1)$. Here we denote by
$\mathcal{P}(\Omega)$ the set of probability measures supported in domain
$\Omega$. For notational simplicity, we assume that
$\mathcal{X}:=\mathcal{S}\times\mathcal{A}\subseteq[0,1]^{d}$ but our main
conclusions do not change when $\mathcal{A}$ is finite.

A policy $\pi:\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$ induces a
distribution over the action space conditioned on states. The $Q$-value
function for policy $\pi$ at state-action pair $(s,a)$, denoted by
$Q^{\pi}(s,a)\in[0,1]$, is the expected discounted total reward the policy
collects if it initially starts in the state-action pair,

$\displaystyle Q^{\pi}(s,a)$
$\displaystyle:=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|s_{0}=s,a_{0}=a\right],$

where $r_{t}\sim R(s_{t},a_{t}),a_{t}\sim\pi(\cdot|s_{t})$, and $s_{t}\sim
P(\cdot|s_{t-1},a_{t-1})$. The value for a policy $\pi$ is simply
$V^{\pi}=\mathbb{E}_{s\sim\rho,a\sim\pi(\cdot|s)}\left[Q^{\pi}(s,a)\right]$,
and the optimal value is $V^{*}=\max_{\pi}V^{\pi}$ where the maximization is
taken over all stationary policies. Alternatively, the optimal value $V^{*}$
can be obtained via the optimal $Q$-function $Q^{*}=\max_{\pi}Q^{\pi}$ as
$V^{*}=\mathbb{E}_{s\sim\rho}\left[\max_{a}Q^{*}(s,a)\right]$. Denote by
$T^{\pi}$ and $T^{*}$ the Bellman operator and the optimality Bellman
operator, i.e., for any $f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$

$\displaystyle[T^{\pi}f](s,a)$ $\displaystyle=\mathbb{E}_{r\sim
R(s,a)}[r]+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a),a^{\prime}\sim\pi(\cdot|s^{\prime})}\left[f(s^{\prime},a^{\prime})\right]$
$\displaystyle[T^{*}f](s,a)$ $\displaystyle=\mathbb{E}_{r\sim
R(s,a)}[r]+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\left[\max_{a^{\prime}}f(s^{\prime},a^{\prime})\right],$

we have $T^{\pi}Q^{\pi}=Q^{\pi}$ and $T^{*}Q^{*}=Q^{*}$.

We consider the offline RL setting where the agent cannot explore further the
environment but has access to a fixed logged data
$\mathcal{D}=\\{(s_{i},a_{i},s^{\prime}_{i},r_{i})\\}_{i=1}^{n}$ collected a
priori by certain behaviour policy $\eta$ where
$(s_{i},a_{i})\overset{i.i.d.}{\sim}\mu(\cdot,\cdot):=\frac{1}{1-\gamma}\sum_{t=0}^{\infty}\gamma^{t}P(s_{t}=\cdot,a_{t}=\cdot|\rho,\eta),s^{\prime}_{i}\sim
P(\cdot|s_{i},a_{i})$ and $r_{i}\sim R(s_{i},a_{i})$. Here $\mu$ is the
(sampling) state-action visitation distribution. The goal of OPE and OPL are
to estimate $V^{\pi}$ and $V^{*}$, respectively from $\mathcal{D}$, and in
this paper we measure performance by sub-optimality gaps.

For OPE. Given a fixed target policy $\pi$, for any value estimate $\hat{V}$
computed from the offline data $\mathcal{D}$, the sub-optimality of OPE is
defined as

$\displaystyle\text{SubOpt}(\hat{V};\pi)=|V^{\pi}-\hat{V}|.$

For OPL. For any estimate $\hat{\pi}$ of the optimal policy $\pi^{*}$ that is
learned from the offline data $\mathcal{D}$, we define the sup-optimality of
OPL as

$\displaystyle\text{SubOpt}(\hat{\pi})=\mathbb{E}_{\rho}\left[V^{*}(s)-Q^{*}(s,\hat{\pi}(s))\right],$

where $\mathbb{E}_{\rho}$ is the expectation with respect to (w.r.t.)
$s\sim\rho$.

###  3.1 Deep ReLU Networks as 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 networks with the ReLU activation offer a rich class of
parameterized functions with differentiable parameters. Deep ReLU networks are
state-of-the-art 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 directly work on. A $L$-height, $m$-width ReLU network on
$\mathbb{R}^{d}$ takes the form of

$\displaystyle
f_{\theta}^{L,m}(x)=W^{(L)}\sigma\left(W^{(L-1)}\sigma\left(\ldots\sigma\left(W^{(1)}\sigma(x)+b^{(1)}\right)\ldots\right)+b^{(L-1)}\right)+b^{(L)},$

where $W^{(L)}\in\mathbb{R}^{1\times
m},b^{(L)}\in\mathbb{R},W^{(1)}\in\mathbb{R}^{m\times
d},b^{(1)}\in\mathbb{R}^{m}$, $W^{(l)}\in\mathbb{R}^{m\times
m},b^{(l)}\in\mathbb{R}^{m},\forall 1<l<L$,
$\theta=\\{W^{(l)},b^{(l)}\\}_{1\leq l\leq L}$, and $\sigma(x)=\max\\{x,0\\}$
is the (element-wise) ReLU activation. We define $\Phi(L,m,S,B)$ as the space
of $L$-height, $m$-width ReLU functions $f_{\theta}^{L,m}(x)$ with sparsity
constraint $S$, and norm constraint $B$, i.e.,
$\sum_{l=1}^{L}(\|W^{(l)}\|_{0}+\|b^{(l)}\|_{0})\leq S,\max_{1\leq l\leq
L}\|W^{(l)}\|_{\infty}\lor\|b^{(l)}\|_{\infty}\leq B$ where $\|\cdot\|_{0}$ is
the $0$-norm, i.e., the number of non-zero elements, and $a\lor
b=\max\\{a,b\\}$. Finally, for some $L,m\in\mathbb{N}$ and $S,B\in(0,\infty)$,
we define the unit ball of ReLU network function space $\mathcal{F}_{NN}$ as

$\displaystyle\mathcal{F}_{NN}:=\bigg{\\{}f\in\Phi(L,m,S,B):\|f\|_{\infty}\leq
1\bigg{\\}}.$

We further write $\mathcal{F}_{NN}(\mathcal{X})$ to emphasize the domain
$\mathcal{X}$ of deep ReLU functions in $\mathcal{F}_{NN}$ but often use
$\mathcal{F}_{NN}$ when the domain context is clear.

The main benefit of deep ReLU networks is that in standard non-parametric
regression, they outperform any non-adaptive linear estimator due to their
higher adaptivity to spatial inhomogeneity (Suzuki, 2018). Later, we show that
this adaptivity benefit of deep ReLU networks transfers to the value
regression problem in offline RL even though the value regression is much more
complex than the standard non-parametric regression.

###  3.2 Regularity

In this section, we define a function space for the target functions for which
we study offline RL. Note that a regularity assumption on the target function
is necessary to obtain a nontrivial rate of convergence (Györfi et al., 2002).
A common way to measure regularity of a function is through the $L^{p}$-norm
of its local oscillations (e.g., of its derivatives if they exist). This
regularity notion encompasses the classical Lipschitz, Hölder and Sobolev
spaces. In particular in this work, we consider Besov spaces. Besov spaces
allow fractional smoothness that describes the regularity of a function more
precisely and generalizes the previous smoothness notions. There are several
ways to characterize the smoothness in Besov spaces. Here, we pursue a
characterization via moduli of smoothness as it is more intuitive, following
(Giné and Nickl, 2016).

######  Definition 3.1 (Moduli of smoothness).

For a function $f\in L^{p}(\mathcal{X})$ for some $p\in[1,\infty]$, we define
its $r$-th modulus of smoothness as

$\displaystyle\omega_{r}^{t,p}(f):=\sup_{0\leq h\leq
t}\|\Delta_{h}^{r}(f)\|_{p},t>0,r\in\mathbb{N},$

where the $r$-th order translation-difference operator
$\Delta_{h}^{r}=\Delta_{h}\circ\Delta_{h}^{r-1}$ is recursively defined as

$\displaystyle\Delta_{h}^{r}(f)(\cdot)$
$\displaystyle:=(f(\cdot+h)-f(\cdot))^{r}=\sum_{k=0}^{r}{{r}\choose{k}}(-1)^{r-k}f(\cdot+k\cdot
h).$

######  Remark.

The quantity $\Delta_{h}^{r}(f)$ captures the local oscillation of function
$f$ which is not necessarily differentiable. In the case the $r$-th order weak
derivative $D^{r}f$ exists and is locally integrable, we have

$\displaystyle\lim_{h\rightarrow
0}\frac{\Delta^{r}_{h}(f)(x)}{h^{r}}=D^{r}f(x),\frac{\omega^{t,p}_{r}(f)}{t^{r}}\leq\|D^{r}f\|_{p}\text{
and
}\frac{\omega^{t,p}_{r+r^{\prime}}(f)}{t^{r}}\leq\omega^{t,p}_{r^{\prime}}(D^{r}f).$

######  Definition 3.2 (Besov space $B^{\alpha}_{p,q}(\mathcal{X})$).

For $1\leq p,q\leq\infty$ and $\alpha>0$, we define the norm
$\|\cdot\|_{B^{\alpha}_{p,q}}$ of the Besov space
$B^{\alpha}_{p,q}(\mathcal{X})$ as
$\|f\|_{B^{\alpha}_{p,q}}:=\|f\|_{p}+|f|_{B^{\alpha}_{p,q}}$ where

$\displaystyle|f|_{B^{\alpha}_{p,q}}:=\begin{cases}\left(\int_{0}^{\infty}(\frac{\omega_{\lfloor\alpha\rfloor+1}^{t,p}(f)}{t^{\alpha}})^{q}\frac{dt}{t}\right)^{1/q},&1\leq
q<\infty,\\\
\sup_{t>0}\frac{\omega_{\lfloor\alpha\rfloor+1}^{t,p}(f)}{t^{\alpha}},&q=\infty,\end{cases}$

is the Besov seminorm. Then, $B^{\alpha}_{p,q}:=\\{f\in
L^{p}(\mathcal{X}):\|f\|_{B^{\alpha}_{p,q}}<\infty\\}$.

Intuitively, the Besov seminorm $|f|_{B^{\alpha}_{p,q}}$ roughly describes the
$L^{q}$-norm of the $l^{p}$-norm of the $\alpha$-order smoothness of $f$.
Having defined Besov spaces, a natural question is what properties Besov
spaces have and how these spaces are related to other function spaces
considered in the current literature of offline RL? It turns out that Besov
spaces are considerably general that encompass Hölder spaces and Sobolev
spaces as well as functions with spatially inhomogeneous smoothness (Triebel,
1983; Sawano, 2018; Suzuki, 2018; Cohen, 2009; Nickl and Pötscher, 2007).
Before presenting the main properties of Besov spaces, we introduce necessary
notations. Let
$L^{p}(\mathcal{X},\mu)=\\{f:\mathcal{X}\rightarrow\mathbb{R}\text{ }|\text{
}\|f\|_{p,\mu}:=(\int_{\mathcal{X}}|f|^{p}d\mu)^{1/p}<\infty\\}$ be the space
of measurable functions for which the $p$-th power of the absolute value is
$\mu$-measurable,
$C^{0}(\mathcal{X})=\\{f:\mathcal{X}\rightarrow\mathbb{R}\text{ }|\text{
}f\text{ is continuous and }\|f\|_{\infty}<\infty\\}$ be the space of bounded
continuous functions, $C^{\alpha}(\mathcal{X})$ be the Hölder space with
smoothness parameter $\alpha\in(0,\infty)\backslash\mathbb{N}$,
$W^{m}_{p}(\mathcal{X})$ be the Sobolev space with regularity $m\in\mathbb{N}$
and parameter $p\in[1,\infty]$, and $X\hookrightarrow Y$ be continuous
embedding from a metric space $X$ to a metric space $Y$. For simplicity, we
use $\|\cdot\|_{\mu}$ for $\|\cdot\|_{p,\mu}$ when $p=2$. We summarize the key
intriguing characteristics of Besov spaces and their relation with other
spaces:

  * •

(Monotonicity in $q$) For $1\leq p\leq\infty,1\leq q_{1}\leq q_{2}\leq\infty$
and $\alpha\in\mathbb{R}$, $B^{\alpha}_{p,q_{1}}(\mathcal{X})\hookrightarrow
B^{\alpha}_{p,q_{2}}(\mathcal{X})$;

  * •

(With $L^{p}$ spaces) $L^{2}(\mathcal{X})\hookrightarrow
B^{0}_{2,2}(\mathcal{X})$, $B^{0}_{p,1}(\mathcal{X})\hookrightarrow
L^{p}(\mathcal{X})\hookrightarrow B^{0}_{p,\infty}(\mathcal{X})$ for $1\leq
p\leq\infty$, and $B^{\alpha}_{p,q}(\mathcal{X})\hookrightarrow
L^{r}(\mathcal{X})$ for $\alpha>d(1/p-1/r)_{+}$ where
$r=\lfloor\alpha\rfloor+1$;

  * •

(With $C^{0}(\mathcal{X})$) $B^{\alpha}_{p,q}(\mathcal{X})\hookrightarrow
C^{0}(\mathcal{X})$ for $1\leq p,q\leq\infty,\alpha>d/p$;

  * •

(With Sobolev spaces) $B^{m}_{2,2}(\mathcal{X})=W^{m}_{2}(\mathcal{X})$ for
$m\in\mathbb{N}$;

  * •

(With Hölder spaces)
$B^{\alpha}_{\infty,\infty}(\mathcal{X})=C^{\alpha}(\mathcal{X})$ for
$\alpha=(0,\infty)\backslash\mathbb{N}$.

In particular, the Besov space $B^{\alpha}_{p,q}$ reduces into the Hölder
space $C^{\alpha}$ when $p=q=\infty$ and $\alpha$ is positive and non-integer
while it reduces into the Sobolev space $W^{\alpha}_{2}$ when $p=q=2$ and
$\alpha$ is a positive integer. We further consider the unit ball of
$B^{\alpha}_{p,q}(\mathcal{X})$:

$\displaystyle\bar{B}^{\alpha}_{p,q}(\mathcal{X}):=\\{g\in
B^{\alpha}_{p,q}:\|g\|_{B^{\alpha}_{p,q}}\leq 1\text{ and }\|g\|_{\infty}\leq
1\\}.$

To obtain a non-trivial guarantee, certain assumptions on the distribution
shift and the MDP regularity are necessary. Here, we introduce such
assumptions. The first assumption is a common restriction that handles
distribution shift in offline RL.

######  Assumption 3.1 (Concentration coefficient).

There exists $\kappa_{\mu}<\infty$ such that
$\|\frac{d\nu}{d\mu}\|_{\infty}\leq\kappa_{\mu}$ for any realizable
distribution $\nu$.

Here, a distribution $\nu$ is said to be realizable if there exists $t\geq 0$
and policy $\pi_{1}$ such that
$\nu(s,a)=\mathbb{P}(s_{t}=s,a_{t}=a|s_{1}\sim\rho,\pi_{1}),\forall s,a$.
Intuitively, the finite $\kappa_{\mu}$ in Assumption 3.1 asserts that the
sampling distribution $\mu$ is not too far away from any realizable
distribution uniformly over the state-action space. $\kappa_{\mu}$ is finite
for a reasonably large class of MDPs, e.g., for any finite MDP, any MDP with
bounded transition kernel density, and equivalently any MDP whose top-Lyapunov
exponent is negative (Munos and Szepesvári, 2008). Chen and Jiang (2019)
further provided natural problems with rich observations generated from hidden
states that has low concentration coefficients. These suggest that low
concentration coefficients can be found in fairly many interesting problems in
practice.

######  Assumption 3.2 (Besov dynamic closure).

$\forall
f\in\mathcal{F}_{NN}(\mathcal{X}),\forall\pi,T^{\pi}f\in\bar{B}^{\alpha}_{p,q}(\mathcal{X})$
for some $p,q\in[1,\infty]$ and $\alpha>\frac{d}{p\land 2}$.

The assumption signifies that for any policy $\pi$, the Bellman operator
$T^{\pi}$ applied on any ReLU network function in
$\mathcal{F}_{NN}(\mathcal{X})$ results in a Besov function in
$\bar{B}^{\alpha}_{p,q}(\mathcal{X})$. Moreover, as $T^{\pi_{f}}f=T^{*}f$
where $\pi_{f}$ is the greedy policy w.r.t. $f$, Assumption 3.2 also implies
that $T^{*}f\in\bar{B}^{\alpha}_{p,q}(\mathcal{X})$ if
$f\in\mathcal{F}_{NN}(\mathcal{X})$. This kind of assumption is relatively
standard and common in the offline RL literature (Chen and Jiang, 2019). A
natural example for this assumption to hold is when both the expected reward
function $r(s,a)$ and the transition density $P(s^{\prime}|s,a)$ for each
fixed $s^{\prime}$ are Besov functions. This specific example posits a general
smoothness to the considered MDP which can be considered a way to impose
restrictions in MDPs. We remark again that restrictions in MDPs are necessary
to obtain non-trivial convergence rates.

Importantly, as Besov spaces are more general than Hölder and Sobolev spaces,
our Besov dynamic closure assumption is considerably general that encompasses
the dynamic conditions considered in prior results (Yang et al., 2019). In
particular, as remarked earlier, the Besov space $B^{\alpha}_{p,q}$ reduces
into the Hölder space $C^{\alpha}$ and Sobolev space $W^{\alpha}_{2}$ at
$p=q=\infty,\alpha\in(0,\infty)\backslash\mathbb{N}$, and at
$p=q=2,\alpha\in\mathbb{N}$, respectively. Moreover, our dynamic assumption
only requires the boundedness of a very general notion of local oscillations
of the underlying MDP. In particular, the underlying MDP can be discontinuous
or non-differentiable (e.g., when $\alpha\leq 1/2$ and $p=2$), or even have
spatially inhomogeneous smoothness (e.g., when $p<2$). These generality
properties were not possible to be considered in the prior results.

The condition $\alpha>\frac{d}{p\land 2}$ guarantees a finite bound for the
compactness and the (local) Rademacher complexity of the considered Besov
space. When $p<2$ (thus the condition above becomes $\alpha>d/p$), a function
in the corresponding Besov space contains both spiky parts and smooth parts,
i.e., the Besov space has inhomogeneous smoothness (Suzuki, 2018). In
particular, when $\alpha>d/p$, each equivalence class $[f]_{\lambda},f\in
B^{\alpha}_{p,q}(\mathbb{R}^{d})$, i.e., modulo equality $\lambda$-almost
everywhere, contains a unique continuous representative. In addition, this
representative has partial derivatives of order at least $\alpha-d/p$; thus
$\alpha-d/p$ is called the differential dimension of the Besov space.

##  4 Algorithm and Main Result

###  4.1 Algorithm

Now we turn to the main algorithm and the main result. We study least-squares
value iteration (LSVI) for both OPE and OPL with the pseudo-code presented in
Algorithm 1 where we denote $\rho^{\pi}(s,a)=\rho(s)\pi(a|s)$. The algorithm
is nearly identical to (Duan and Wang, 2020) but with deep neural network
function approximation instead of linear models. As such, it can be considered
as a generalization.

Algorithm 1 Least-squares value iteration (LSVI)

1:Initialize $Q_{0}\in\mathcal{F}_{NN}$.

2:for $k=1$ to $K$ do

3: If OPE (for a fixed policy $\pi$): $y_{i}\leftarrow
r_{i}+\gamma\int_{\mathcal{A}}Q_{k-1}(s^{\prime}_{i},a)\pi(da|s^{\prime}_{i}),\forall
i$

4: If OPL: $y_{i}\leftarrow
r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}Q_{k-1}(s^{\prime}_{i},a^{\prime}),\forall
i$

5:
$Q_{k}\leftarrow\operatorname*{arg\,min}_{f\in\mathcal{F}_{NN}}\frac{1}{n}\sum_{i=1}^{n}(f(s_{i},a_{i})-y_{i})^{2}$

6:end for

7:If OPE, return
$V_{K}=\|Q_{K}\|_{\rho^{\pi}}=\sqrt{\mathbb{E}_{\rho(s)\pi(a|s)}\left[Q_{K}(s,a)^{2}\right]}$

8:If OPL, return the greedy policy $\pi_{K}$ w.r.t. $Q_{K}$.

The idea of LSVI is to do the best it could with all the offline data using
least-squares regression over a function space. The algorithm arbitrarily
initializes $Q_{0}\in\mathcal{F}_{NN}$ and iteratively computes $Q_{k}$ as
follows: at each iteration $k$, the algorithm constructs a new regression data
$\\{(x_{i},y_{i})\\}_{i=1}^{n}$ where the covariates $x_{i}$ are
$(s_{i},a_{i})$ and the Bellman targets $y_{i}$ are computed following dynamic
programming style. In particular, depending on whether this is an OPE or OPL
problem, $y_{i}$ are computed according to line 3 and line 4 of Algorithm 1,
respectively. It then fits the function class $\mathcal{F}_{NN}$ to the
constructed regression data by minimizing the mean squared error at line 5.
This type of algorithm belongs to the fitted Q-iteration family (Munos and
Szepesvári, 2008; Le et al., 2019) that iteratively uses least-squares (value)
regression to estimate the value functions. The main difference in the
algorithm is here we use deep neural networks as function approximation for
generalization to unseen states and actions in a complex MDP.

On the computational side, solving the non-convex optimization at line 5 of
Algorithm 1 can be highly involved and stochastic gradient descent is a
dominant optimization method for such a task in deep learning. In particular,
GD is guaranteed to converge to a global minimum under certain structural
assumptions (Nguyen, 2021). Here, as we focus on the statistical properties of
LSVI, not on the optimization problem, we assume that the minimizer at line 5
is attainable. Such a oracle assumption is common when analyzing the
statistical properties of an RL algorithm with non-linear function
approximation (Yang et al., 2019; Chen and Jiang, 2019; Duan et al., 2021;
Wang et al., 2019, 2020; Jin et al., 2021). For the optimization problem of
deep neural networks, we refer the readers to its vast body of literature (see
e.g. Sun, 2019, and references therein).

###  4.2 Data-dependent Structure

We remark the data-dependent structure in Algorithm 1. The target variable
$y_{i}$ computed at line 3 and line 4 of the algorithm depends on the previous
estimate $Q_{k-1}$ which in turn depends on the covariate
$x_{i}:=(s_{i},a_{i})$. This induces a complex data-dependent structure across
all iterations where the current estimate depends on all the previous
estimates and the past data. In particular, one of the main difficulties
caused by such data-dependent structure is that conditioned on each $x_{i}$,
the target variable $y_{i}$ is no longer centered at $[T^{*}Q_{k-1}](x_{i})$
for OPL (or at $[T^{\pi}Q_{k-1}](x_{i})$ for OPE, respectively), i.e.,
$\mathbb{E}\left[[T^{*}Q_{k-1}](x_{i})-y_{i}|x_{i}\right]\neq 0$. This data-
dependent structure hinders the use of any standard non-parametric regression
analysis and concentration phenomenon typically used in supervised learning.
Prior results either improperly ignore the data-dependent structure in their
analysis (Le et al., 2019) or directly avoid it by estimating each $Q_{k}$ on
a separate subset of the original data (Yang et al., 2019). While the latter
removes the data-dependent structure, it pays the undesirable cost of scaling
the sample complexity with the number of iterations $K$ in the algorithm as it
requires splitting the original data into $K$ disjoint subsets. In our work,
we consider the data-dependent structure in LSVI and effectively handle it via
a uniform-convergence argument and local Rademacher complexities. While our
uniform-convergence argument overcomes the data-dependent structure by
considering deterministic coverings of the target function space
$T^{*}\mathcal{F}_{NN}$ without the need for breaking the original data into
$K$ disjoint subsets, local Rademacher complexities localize an original
function space into local data-dependent balls which can then be gracefully
integrated with the uniform-convergence argument and the complicated deep ReLU
function approximation. The technical details for our handling method of the
data-dependent structure are presented in the proof of our main theorem (in
Subsection 4.3) in the supplementary material.

###  4.3 Main Result

Our main result is a sup-optimality bound for LSVI in both OPE and OPL
settings under Assumption 3.1 and Assumption 3.2. Before stating the main
result, we introduce the necessary notations of asymptotic relations. For any
two real-valued functions $f$ and $g$, we write $f(\epsilon,n)\lesssim
g(\epsilon,n)$ if there is an absolute constant $c$ such that
$f(\epsilon,n)\leq c\cdot g(\epsilon,n),\forall\epsilon>0,n\in\mathbb{N}$. We
write $f(\epsilon,n)\asymp g(\epsilon,n)$ if $f(\epsilon,n)\lesssim
g(\epsilon,n)$ and $g(\epsilon,n)\lesssim f(\epsilon,n)$. We write
$f(\epsilon,n)\simeq g(\epsilon,n)$ if there exists an absolute constant $c$
such that $f(\epsilon,n)=c\cdot g(\epsilon,n),\forall\epsilon,n$.

######  Theorem 4.1.

Under Assumption 3.1 and Assumption 3.2, for any
$\epsilon>0,\delta\in(0,1],K>0$, and for
$n\gtrsim\left(\frac{1}{\epsilon^{2}}\right)^{1+\frac{d}{\alpha}}\log^{6}n+\frac{1}{\epsilon^{2}}(\log(1/\delta)+\log\log
n)$, with probability at least $1-\delta$, the sup-optimality of Algorithm 1
is

$\displaystyle\begin{cases}\text{SubOpt}(V_{K};\pi)\leq\frac{\sqrt{\kappa_{\mu}}}{1-\gamma}\epsilon+\frac{\gamma^{K/2}}{(1-\gamma)^{1/2}}&\text{
for OPE},\\\
\text{SubOpt}(\pi_{K})\leq\frac{4\gamma\sqrt{\kappa_{\mu}}}{(1-\gamma)^{2}}\epsilon+\frac{4\gamma^{1+K/2}}{(1-\gamma)^{3/2}}&\text{
for OPL.}\end{cases}$

In addition, the optimal deep ReLU network $\Phi(L,m,S,B)$ that obtains such
sample complexity (for both OPE and OPL) satisfies

$\displaystyle L\asymp\log N,m\asymp N\log N,S\asymp N,\text{ and }B\asymp
N^{1/d+(2\iota)/(\alpha-\iota)},$

where $\iota:=d(p^{-1}-(1+\lfloor\alpha\rfloor)^{-1})_{+},N\asymp
n^{\frac{(\beta+1/2)d}{2\alpha+d}}$, and
$\beta=(2+\frac{d^{2}}{\alpha(\alpha+d)})^{-1}$.

The result states that LSVI incurs a sub-optimality which 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$,
the statistical error reflects the fundamental difficulty of the problems. The
statistical errors for both OPE and OPL cases are bounded by the
distributional shift $\kappa_{\mu}$, the effective horizon $1/(1-\gamma)$, and
the user-specified precision $\epsilon$ for $n$ satisfying the inequality
given in Theorem 4.1. In particular, the sample complexity does not depend on
the number of states as in tabular MDPs (Yin and Wang, 2020; Yin et al., 2021;
Yin and Wang, 2021) or the inherent Bellman error as in the general function
approximation (Munos and Szepesvári, 2008; Le et al., 2019). Instead, it
explicitly scales with the (possible fractional) smoothness $\alpha$ of the
underlying MDP and the dimension $d$ of the input space. Importantly, this
guarantee is established under the data-dependent structure of the algorithm
and the Besov dynamic closure encompassing the dynamic conditions of the prior
results. Thus, Theorem 4.1 is the most comprehensive result we are aware of
for offline RL with deep neural network function approximation.

Moreover, to develop further intuition on our sample complexity, we compare it
with the prior results. Regarding the tightness of our result, our sample
complexity $\epsilon^{-2-2d/\alpha}$ (ignoring the log factor and the factor
pertaining to $\kappa_{\mu}$ and effective horizon) nearly matches the
nonparametric regression’s minimax-optimal sample complexity
$\epsilon^{-2-d/\alpha}$ (Kerkyacharian and Picard, 1992; Giné and Nickl,
2016) even though in our case we deal with a more complicated data-dependent
structure in a value iteration problem instead of a standard non-parametric
regression problem. This gap is necessary and expected due to the data-
dependent structure in the algorithm. We remark that it is possible to retain
the rate $\epsilon^{-2-d/\alpha}$ if we split the offline data $\mathcal{D}$
into $K$ (given in Algorithm 1) disjoint subsets and estimate each $Q_{k}$ in
Algorithm 1 using a separate disjoint subsets. This however comes at the cost
that the overall sample complexity scales with $K$ which could be arbitrarily
large in practice.

Work | Functions | Regularity | Tasks | Sample complexity | Remark
---|---|---|---|---|---
Yin and Wang (2020) | Tabular | Tabular | OPE | $\tilde{\mathcal{O}}\left(\frac{\kappa}{\epsilon^{2}}\cdot|\mathcal{S}|^{2}\cdot|\mathcal{A}|^{2}\right)$ | minimax-optimal
Duan and Wang (2020) | Linear | Linear | OPE | $\tilde{\mathcal{O}}\left(\frac{\kappa}{\epsilon^{2}}\cdot d\right)$ | minimax-optimal
Le et al. (2019) | General | General | OPE/OPL | N/A | improper analysis
Yang et al. (2019) | ReLU nets | Hölder | OPL | $\tilde{\mathcal{O}}\left(K\cdot\kappa^{2+\frac{d}{\alpha}}\cdot\epsilon^{-2-\frac{d}{\alpha}}\right)$ | no data reuse
Ours | ReLU nets | Besov | OPE/OPL | $\tilde{\mathcal{O}}\left(\kappa^{1+\frac{d}{\alpha}}\cdot\epsilon^{-2-2\frac{d}{\alpha}}\right)$ | data reuse

Table 1: Recent advances in the sample complexity of offline RL with various
function approximations. Here, $|\mathcal{S}|$ and $|\mathcal{A}|$ are the
cardinalities of the state and action space when they are finite, $\kappa$ is
a measure of distribution shift, $\epsilon$ is the user-specified precision,
$d$ is the dimension of the input space, $\alpha$ is the smoothness parameter
of the underlying MDP, and $K$ is the algorithmic iteration number.

To show the significance of our sample complexity, we summarize our result and
compare it with the prior results in Table 1. From the leftmost column to the
rightmost one, the table describes the related works, the function
approximations being employed, the regularity conditions considered to
establish theoretical guarantees, the offline RL tasks considered, the sample
complexity obtained, and the important remarks or features of each work.
Specifically, the “data reuse” in Table 1 means that an algorithm reuses the
data across all iterations instead of splitting the original offline data into
disjoint subsets for each iteration and the regularity column specifies the
regularity assumption on the underlying MDP. Based on this comparison, we make
the following observations. First, with simpler models such as tabular and
linear MDPs, it requires less samples to achieve the same sub-optimality
precision $\epsilon$ than more complex environments such as Hölder and Besov
MDPs. This should not come as a surprise as the simpler regularities are much
easier to learn but they are too strong as a condition to hold in practice.
Second, as remarked earlier that Besov smoothness is more general than Hölder
smoothness considered in (Yang et al., 2019), our setting is more practical
and comprehensive as it covers more scenarios of the regularity of the
underlying MDPs than the prior results. Third, our result obtains an improved
sample complexity as compared to that in (Yang et al., 2019) where we are able
to get rid of the dependence on the algorithmic iteration number $K$ which can
be arbitrarily large in practice. On the technical side, we provide a unifying
analysis that allows us to account for the complicated data-dependent
structure in the algorithm and handle the complex deep ReLU network function
approximation. This can also be considered as a substantial technical
improvement over (Le et al., 2019) as Le et al. (2019) improperly ignores the
data-dependent structure in their analysis. In addition, the result in (Le et
al., 2019) does not provide an explicit sample complexity as it depends on an
unknown inherent Bellman error. Thus, our sample complexity is the most
general result in a practical and comprehensive setting with an improved
performance.

Finally, we provide a detailed proof for Theorem 4.1 in the supplementary. The
proof has four main components: a sub-optimality decomposition for error
propagation across iterations, a Bellman error decomposition using a uniform
convergence argument, a deviation analysis for least-squares value regression
with deep ReLU networks using local Rademacher complexities via a localization
argument, and an upper bound minimization step to obtain an optimal deep ReLU
architecture.

##  5 Conclusion and Discussion

This paper presents the sample complexity of offline RL with deep ReLU network
function approximation. We prove that the FQI-type algorithm with the data-
dependent structure obtains an improved sample complexity of
$\tilde{\mathcal{O}}\left(\kappa^{1+d/\alpha}\cdot\epsilon^{-2-2d/\alpha}\right)$
under a standard condition of distributional shift and a new dynamic condition
namely Besov dynamic closure which encompasses the dynamic conditions
considered in the prior results. Established under the data-dependent
structure and the general Besov dynamic closure, our sample complexity is the
most general result for offline RL with deep ReLU network function
approximation.

We close with some open problems. First, although the finite concentration
coefficient is a uniform data coverage assumption that is relatively standard
in offline RL, can we develop a weaker, non-uniform assumption that can still
accommodate offline RL with non-linear function approximation? While such a
weaker data coverage assumptions do exist for offline RL in tabular settings
(Rashidinejad et al., 2021), it seems difficult to generalize this condition
to function approximation. Another important direction is to investigate the
sample complexity of pessimism principle (Buckman et al., 2020) in offline RL
with non-linear function approximation, which is currently studied only in
tabular and linear settings (Rashidinejad et al., 2021; Jin et al., 2020).

## Acknowledgement

The first author would like to thank Richard Nickl (Prof. at the University of
Cambridge) for the clarification on the bracketing entropic number of Besov
spaces.

## References

  * Antos et al. (2008) András Antos, Csaba Szepesvári, and Rémi Munos.  Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path.  _Mach. Learn._ , 71(1):89–129, April 2008.  ISSN 0885-6125.  doi: 10.1007/s10994-007-5038-2.  URL https://doi.org/10.1007/s10994-007-5038-2.
  * Bartlett et al. (2005) Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson.  Local rademacher complexities.  _Ann. Statist._ , 33(4):1497–1537, 08 2005.  doi: 10.1214/009053605000000282.  URL https://doi.org/10.1214/009053605000000282.
  * Bertsekas and Tsitsiklis (1995) Dimitri P Bertsekas and John N Tsitsiklis.  Neuro-dynamic programming: an overview.  In _Proceedings of 1995 34th IEEE Conference on Decision and Control_ , volume 1, pages 560–564. IEEE, 1995.
  * Bertsekas et al. (1995) Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas.  _Dynamic programming and optimal control_ , volume 1.  Athena scientific Belmont, MA, 1995.
  * Buckman et al. (2020) Jacob Buckman, Carles Gelada, and Marc G Bellemare.  The importance of pessimism in fixed-dataset policy optimization.  _arXiv preprint arXiv:2009.06799_ , 2020.
  * Chen and Jiang (2019) Jinglin Chen and Nan Jiang.  Information-theoretic considerations in batch reinforcement learning.  In _ICML_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1042–1051. PMLR, 2019.
  * Cohen (2009) Albert Cohen.  A primer on besov spaces, 2009.  URL http://cnx.org/content/col10679/1.2/>.
  * Duan and Wang (2020) Yaqi Duan and Mengdi Wang.  Minimax-optimal off-policy evaluation with linear function approximation.  _CoRR_ , abs/2002.09516, 2020.
  * Duan et al. (2021) Yaqi Duan, Chi Jin, and Zhiyuan Li.  Risk bounds and rademacher complexity in batch reinforcement learning.  _arXiv preprint arXiv:2103.13883_ , 2021.
  * Dudík et al. (2011) Miroslav Dudík, John Langford, and Lihong Li.  Doubly robust policy evaluation and learning.  _arXiv preprint arXiv:1103.4601_ , 2011.
  * Farajtabar et al. (2018) Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh.  More robust doubly robust off-policy evaluation.  _arXiv preprint arXiv:1802.03493_ , 2018.
  * Farrell et al. (2018) 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 arXiv:1809.09953_ , 2018.
  * Giné and Nickl (2016) Evarist Giné and Richard Nickl.  _Mathematical foundations of infinite-dimensional statistical models_ , volume 40.  Cambridge University Press, 2016.
  * Grünewälder et al. (2012) Steffen Grünewälder, Guy Lever, Luca Baldassarre, Massimiliano Pontil, and Arthur Gretton.  Modelling transition dynamics in mdps with RKHS embeddings.  In _ICML_. icml.cc / Omnipress, 2012.
  * Györfi et al. (2002) László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk.  _A Distribution-Free Theory of Nonparametric Regression_.  Springer series in statistics. Springer, 2002.
  * Jiang and Li (2015) Nan Jiang and Lihong Li.  Doubly robust off-policy value evaluation for reinforcement learning, 2015\.
  * Jiang and Li (2016) Nan Jiang and Lihong Li.  Doubly robust off-policy value evaluation for reinforcement learning.  In _ICML_ , volume 48 of _JMLR Workshop and Conference Proceedings_ , pages 652–661. JMLR.org, 2016.
  * Jin et al. (2021) Chi Jin, Qinghua Liu, and Sobhan Miryoosefi.  Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms.  _CoRR_ , abs/2102.00815, 2021.  URL https://arxiv.org/abs/2102.00815.
  * Jin et al. (2020) Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline rl?  _arXiv preprint arXiv:2012.15085_ , 2020.
  * Jong and Stone (2007) Nicholas K. Jong and Peter Stone.  Model-based function approximation in reinforcement learning.  In _AAMAS_ , page 95. IFAAMAS, 2007.
  * Kallus and Uehara (2019) Nathan Kallus and Masatoshi Uehara.  Double reinforcement learning for efficient off-policy evaluation in markov decision processes, 2019.
  * Kerkyacharian and Picard (1992) Gérard Kerkyacharian and Dominique Picard.  Density estimation in besov spaces.  _Statistics & probability letters_, 13(1):15–24, 1992.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pages 1097–1105, 2012.
  * Lagoudakis and Parr (2003) Michail G. Lagoudakis and Ronald Parr.  Least-squares policy iteration.  _J. Mach. Learn. Res._ , 4:1107–1149, 2003.
  * Le et al. (2019) Hoang Minh Le, Cameron Voloshin, and Yisong Yue.  Batch policy learning under constraints.  In _ICML_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 3703–3712. PMLR, 2019.
  * Lei et al. (2016) Yunwen Lei, Lixin Ding, and Yingzhou Bi.  Local rademacher complexity bounds based on covering numbers.  _Neurocomputing_ , 218:320–330, 2016.
  * Levine et al. (2020) Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Liu et al. (2018) Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou.  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  In _NeurIPS_ , pages 5361–5371, 2018.
  * Mnih et al. (2015) 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(7540):529–533, 2015.
  * Munos (2003) Rémi Munos.  Error bounds for approximate policy iteration.  In _ICML_ , pages 560–567. AAAI Press, 2003.
  * Munos and Szepesvári (2008) Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  _J. Mach. Learn. Res._ , 9:815–857, 2008.
  * Nachum et al. (2019a) Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li.  Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections, 2019a.
  * Nachum et al. (2019b) Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans.  Algaedice: Policy gradient from arbitrary experience.  _ArXiv_ , abs/1912.02074, 2019b.
  * Nguyen (2021) Quynh Nguyen.  On the proof of global convergence of gradient descent for deep relu networks with linear widths.  _arXiv preprint arXiv:2101.09612_ , 2021.
  * Nickl and Pötscher (2007) 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\.
  * Precup et al. (2000) Doina Precup, Richard S. Sutton, and Satinder P. Singh.  Eligibility traces for off-policy policy evaluation.  In _Proceedings of the Seventeenth International Conference on Machine Learning_ , ICML ’00, page 759–766, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.  ISBN 1558607072.
  * Rashidinejad et al. (2021) Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell.  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  _arXiv preprint arXiv:2103.12021_ , 2021.
  * Rebeschini (2019) Patrick Rebeschini.  Oxford Algorithmic Foundations of Learning, Lecture Notes: Maximal Inequalities and Rademacher Complexity, 2019.  URL: http://www.stats.ox.ac.uk/~rebeschi/teaching/AFoL/20/material/lecture02.pdf. Last visited on Sep. 14, 2020.
  * Sawano (2018) Yoshihiro Sawano.  _Theory of Besov Spaces_ , volume 56.  Springer, 2018.  ISBN 978-981-13-0835-2.
  * Sun (2019) Ruoyu Sun.  Optimization for deep learning: theory and algorithms.  _arXiv preprint arXiv:1912.08957_ , 2019.
  * Sutton and Barto (2018) Richard S. Sutton and Andrew G. Barto.  _Reinforcement Learning: An Introduction_.  A Bradford Book, Cambridge, MA, USA, 2018.  ISBN 0262039249.
  * Suzuki (2018) Taiji Suzuki.  Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality.  _arXiv preprint arXiv:1810.08033_ , 2018.
  * Thomas and Brunskill (2016) Philip Thomas and Emma Brunskill.  Data-efficient off-policy policy evaluation for reinforcement learning.  In _International Conference on Machine Learning_ , pages 2139–2148, 2016.
  * Tosatto et al. (2017) Samuele Tosatto, Matteo Pirotta, Carlo D’Eramo, and Marcello Restelli.  Boosted fitted q-iteration.  In _ICML_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 3434–3443. PMLR, 2017.
  * Triebel (1983) H. Triebel.  Theory of function spaces.  1983\.
  * Voloshin et al. (2019) Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue.  Empirical study of off-policy policy evaluation for reinforcement learning.  _arXiv preprint arXiv:1911.06854_ , 2019.
  * Wang et al. (2020) Ruosong Wang, Ruslan Salakhutdinov, and Lin F. Yang.  Provably efficient reinforcement learning with general value function approximation.  _CoRR_ , abs/2005.10804, 2020.  URL https://arxiv.org/abs/2005.10804.
  * Wang et al. (2019) Yining Wang, Ruosong Wang, Simon S. Du, and Akshay Krishnamurthy.  Optimism in reinforcement learning with generalized linear function approximation.  _CoRR_ , abs/1912.04136, 2019.  URL http://arxiv.org/abs/1912.04136.
  * Xie et al. (2019) Tengyang Xie, Yifei Ma, and Yu-Xiang Wang.  Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling, 2019.
  * Yang et al. (2019) Zhuoran Yang, Yuchen Xie, and Zhaoran Wang.  A theoretical analysis of deep q-learning.  _CoRR_ , abs/1901.00137, 2019.
  * Yin and Wang (2020) Ming Yin and Yu-Xiang Wang.  Asymptotically efficient off-policy evaluation for tabular reinforcement learning.  In _AISTATS_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 3948–3958. PMLR, 2020.
  * Yin and Wang (2021) Ming Yin and Yu-Xiang Wang.  Characterizing uniform convergence in offline policy evaluation via model-based approach: Offline learning, task-agnostic and reward-free, 2021.
  * Yin et al. (2021) Ming Yin, Yu Bai, and Yu-Xiang Wang.  Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning.  In Arindam Banerjee and Kenji Fukumizu, editors, _The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 1567–1575. PMLR, 2021.  URL http://proceedings.mlr.press/v130/yin21a.html.
  * Zhang et al. (2020a) Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans.  Gendice: Generalized offline estimation of stationary values.  _ArXiv_ , abs/2002.09072, 2020a.
  * Zhang et al. (2020b) Shangtong Zhang, Bo Liu, and Shimon Whiteson.  Gradientdice: Rethinking generalized offline estimation of stationary values.  _ArXiv_ , abs/2001.11113, 2020b.

## Checklist

The checklist follows the references. Please read the checklist guidelines
carefully for information on how to answer these questions. For each question,
change the default [TODO] to [Yes] , [No] , or [N/A] . You are strongly
encouraged to include a justification to your answer, either by referencing
the appropriate section of your paper or providing a brief inline description.
For example:

  * •

Did you include the license to the code and datasets? [Yes] See Section
LABEL:gen_inst.

  * •

Did you include the license to the code and datasets? [No] The code and the
data are proprietary.

  * •

Did you include the license to the code and datasets? [N/A]

Please do not modify the questions and only use the provided macros for your
answers. Note that the Checklist section does not count towards the page
limit. In your paper, please delete this instructions block and only keep the
Checklist section heading above along with the questions/answers below.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] See Section 5

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
See Section 3

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] See the
supplementary

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [N/A]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [N/A]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

## Appendix A. Proof

We now provide a complete proof of Theorem 4.1. The proof has four main
components: a sub-optimality decomposition for error propagation across
iterations, a Bellman error decomposition using a uniform convergence
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 to obtain an optimal deep ReLU architecture.

#### Step 1: A sub-optimality decomposition

The first step of the proof is a sub-optimality decomposition, stated in Lemma
5.1, that applies generally to any least-squares Q-iteration methods.

######  Lemma 5.1 (A sub-optimality decomposition).

Under Assumption 3.1, the sub-optimality of $V_{K}$ returned by Algorithm 1 is
bounded as

$\displaystyle\text{SubOpt}(V_{K})\leq\begin{cases}\frac{\sqrt{\kappa_{\mu}}}{1-\gamma}\displaystyle\max_{0\leq
k\leq
K-1}\|Q_{k+1}-T^{\pi}Q_{k}\|_{\mu}+\frac{\gamma^{K/2}}{(1-\gamma)^{1/2}}&\text{
for OPE},\\\
\frac{4\gamma\sqrt{\kappa_{\mu}}}{(1-\gamma)^{2}}\displaystyle\max_{0\leq
k\leq
K-1}\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}+\frac{4\gamma^{1+K/2}}{(1-\gamma)^{3/2}}&\text{
for OPL}.\end{cases}$

where we denote $\|f\|_{\mu}:=\sqrt{\int\mu(dsda)f(s,a)^{2}},\forall
f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$.

The lemma states that the sub-optimality decomposes into a statistical error
(the first term) and an algorithmic 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 $T^{\pi}$ and
$T^{*}$ allows the sup-optimality error at the final iteration $K$ to
propagate across all iterations $k\in[0,K-1]$. Note that this result is
agnostic to any function approximation form and does not require Assumption
3.2. The result uses a relatively standard argument that appears in a number
of works on offline RL (Munos and Szepesvári, 2008; Le et al., 2019).

###### Proof of Lemma 5.1.

We will prove the sup-optimality decomposition for both settings: OPE and OPL.

(i) For OPE. We denote the right-linear operator by
$P^{\pi}\cdot:\\{\mathcal{X}\rightarrow\mathbb{R}\\}\rightarrow\\{\mathcal{X}\rightarrow\mathbb{R}\\}$
where

$\displaystyle(P^{\pi}f)(s,a):=\int_{\mathcal{X}}f(s^{\prime},a^{\prime})\pi(da^{\prime}|s^{\prime})P(ds^{\prime}|s,a),$

for any $f\in\\{\mathcal{X}\rightarrow\mathbb{R}\\}$. Denote Denote
$\rho^{\pi}(dsda)=\rho(ds)\pi(da|s)$. Let
$\epsilon_{k}:=Q_{k+1}-T^{\pi}Q_{k},\forall k\in[0,K-1]$ and
$\epsilon_{K}=Q_{0}-Q^{\pi}$. Since $Q^{\pi}$ is the (unique) fixed point of
$T^{\pi}$, we have

$\displaystyle Q_{k}-Q^{\pi}$
$\displaystyle=T^{\pi}Q_{k-1}-T^{\pi}Q^{\pi}+\epsilon_{k-1}=\gamma
P^{\pi}(Q_{k-1}-Q^{\pi})+\epsilon_{k-1}.$

By recursion, we have

$\displaystyle Q_{K}-Q^{\pi}$ $\displaystyle=\sum_{k=0}^{K}(\gamma
P^{\pi})^{k}\epsilon_{k}=\frac{1-\gamma^{K+1}}{1-\gamma}\sum_{k=0}^{K}\alpha_{k}A_{k}\epsilon_{k}$

where $\alpha_{k}:=\frac{(1-\gamma)\gamma^{k}}{1-\gamma^{K+1}},\forall
k\in[K]$ and $A_{k}:=(P^{\pi})^{k},\forall k\in[K]$. Note that
$\sum_{k=0}^{K}\alpha_{k}=1$ and $A_{k}$’s are probability kernels. Denoting
by $|f|$ the point-wise absolute value $|f(s,a)|$, we have that the following
inequality holds point-wise:

$\displaystyle|Q_{K}-Q^{\pi}|\leq\frac{1-\gamma^{K+1}}{1-\gamma}\sum_{k=0}^{K}\alpha_{k}A_{k}|\epsilon_{k}|.$

We have

$\displaystyle\|Q_{K}-Q^{\pi}\|^{2}_{\rho^{\pi}}$
$\displaystyle\leq\frac{(1-\gamma^{K+1})^{2}}{(1-\gamma)^{2}}\int\rho(ds)\pi(da|s)\left(\sum_{k=0}^{K}\alpha_{k}A_{k}|\epsilon_{k}|(s,a)\right)^{2}$
$\displaystyle\overset{(a)}{\leq}\frac{(1-\gamma^{K+1})^{2}}{(1-\gamma)^{2}}\int\rho(ds)\pi(da|s)\sum_{k=0}^{K}\alpha_{k}A_{k}^{2}\epsilon_{k}^{2}(s,a)$
$\displaystyle\overset{(b)}{\leq}\frac{(1-\gamma^{K+1})^{2}}{(1-\gamma)^{2}}\int\rho(ds)\pi(da|s)\sum_{k=0}^{K}\alpha_{k}A_{k}\epsilon_{k}^{2}(s,a)$
$\displaystyle\overset{(c)}{\leq}\frac{(1-\gamma^{K+1})^{2}}{(1-\gamma)^{2}}\left(\int\rho(ds)\pi(da|s)\sum_{k=0}^{K-1}\alpha_{k}A_{k}\epsilon_{k}^{2}(s,a)+\alpha_{K}\right)$
$\displaystyle\overset{(d)}{\leq}\frac{(1-\gamma^{K+1})^{2}}{(1-\gamma)^{2}}\left(\int\mu(ds,da)\sum_{k=0}^{K-1}\alpha_{k}\kappa_{\mu}\epsilon_{k}^{2}(s,a)+\alpha_{K}\right)$
$\displaystyle=\frac{(1-\gamma^{K+1})^{2}}{(1-\gamma)^{2}}\left(\sum_{k=0}^{K-1}\alpha_{k}\kappa_{\mu}\|\epsilon_{k}\|^{2}_{\mu}+\alpha_{K}\right)$
$\displaystyle\leq\frac{\kappa_{\mu}}{(1-\gamma)^{2}}\max_{0\leq k\leq
K-1}\|\epsilon_{k}\|_{\mu}^{2}+\frac{\gamma^{K}}{(1-\gamma)}.$

The inequalities $(a)$ and $(b)$ follow from Jensen’s inequality, $(c)$
follows from $\|Q_{0}\|_{\infty},\|Q^{\pi}\|_{\infty}\leq 1$, and $(d)$
follows from Assumption 3.1 that
$\rho^{\pi}A_{k}=\rho^{\pi}(P^{\pi})^{k}\leq\kappa_{\mu}\mu$. Thus we have

$\displaystyle\text{SubOpt}(V_{K};\pi)$ $\displaystyle=|V_{K}-V^{\pi}|$
$\displaystyle=\bigg{|}\mathbb{E}_{\rho,\pi}[Q_{K}(s,a)]-\mathbb{E}_{\rho}[Q^{\pi}(s,a)]\bigg{|}$
$\displaystyle\leq\mathbb{E}_{\rho,\pi}\left[|Q_{K}(s,a)-Q^{\pi}(s,a)|\right]$
$\displaystyle\leq\sqrt{\mathbb{E}_{\rho,\pi}\left[(Q_{K}(s,a)-Q^{\pi}(s,a))^{2}\right]}$
$\displaystyle=\|Q_{K}-Q^{\pi}\|_{\rho^{\pi}}$
$\displaystyle\leq\frac{\sqrt{\kappa_{\mu}}}{1-\gamma}\max_{0\leq k\leq
K-1}\|\epsilon_{k}\|_{\mu}+\frac{\gamma^{K/2}}{(1-\gamma)^{1/2}}.$

(ii) For OPL. The sup-optimality for the OPL setting is more complex than the
OPE setting but the technical steps are relatively similar. In particular, let
$\epsilon_{k-1}=T^{*}Q_{k-1}-Q_{k},\forall k$ and
$\pi^{*}(s)=\operatorname*{arg\,max}_{a}Q^{*}(s,a),\forall s$, we have

$\displaystyle Q^{*}-Q_{K}$
$\displaystyle=T^{\pi^{*}}Q^{*}-T^{\pi^{*}}Q_{K-1}+\underbrace{T^{\pi^{*}}Q_{K-1}-T^{*}Q_{K-1}}_{\leq
0}+\epsilon_{K-1}$ $\displaystyle\leq\gamma
P^{\pi^{*}}(Q^{*}-Q_{K-1})+\epsilon_{K-1}$
$\displaystyle\leq\sum_{k=0}^{K-1}\gamma^{K-k-1}(P^{\pi^{*}})^{K-k-1}\epsilon_{k}+\gamma^{K}(P^{\pi^{*}})^{K}(Q^{*}-Q_{0})(\text{by
recursion}).$ (1)

Now, let $\pi_{k}$ be the greedy policy w.r.t. $Q_{k}$, we have

$\displaystyle Q^{*}-Q_{K}$ $\displaystyle=\underbrace{T^{\pi^{*}}Q^{*}}_{\geq
T^{\pi_{K-1}}Q^{*}}-T^{\pi_{K-1}}Q_{K-1}+\underbrace{T^{\pi_{K-1}}Q_{K-1}-T^{*}Q_{K-1}}_{\geq
0}+\epsilon_{K-1}$ $\displaystyle\geq\gamma
P^{\pi_{K-1}}(Q^{*}-Q_{K-1})+\epsilon_{K-1}$
$\displaystyle\geq\sum_{k=0}^{K-1}\gamma^{K-k-1}(P^{\pi_{K-1}}\ldots
P^{\pi_{k+1}})\epsilon_{k}+\gamma^{K}(P^{\pi_{K-1}}\ldots
P^{\pi_{0}})(Q^{*}-Q_{0}).$ (2)

Now, we turn to decompose $Q^{*}-Q^{\pi_{K}}$ as

$\displaystyle Q^{*}-Q^{\pi_{K}}$
$\displaystyle=(T^{\pi^{*}}Q^{*}-T^{\pi^{*}}Q_{K})+\underbrace{(T^{\pi^{*}}Q_{K}-T^{\pi_{K}}Q_{K})}_{\leq
0}+(T^{\pi_{K}}Q_{K}-T^{\pi_{K}}Q^{\pi_{K}})$ $\displaystyle\leq\gamma
P^{\pi^{*}}(Q^{*}-Q_{K})+\gamma P^{\pi_{K}}(Q_{K}-Q^{*}+Q^{*}-Q^{\pi_{K}}).$

Thus, we have

$\displaystyle(I-\gamma
P^{\pi_{K}})(Q^{*}-Q^{\pi_{K}})\leq\gamma(P^{\pi^{*}}-P^{\pi_{K}})(Q^{*}-Q_{K}).$

Note that the operator $(I-\gamma P^{\pi_{K}})^{-1}=\sum_{i=0}^{\infty}(\gamma
P^{\pi_{K}})^{i}$ is monotone, thus

$\displaystyle Q^{*}-Q^{\pi_{K}}\leq\gamma(I-\gamma
P^{\pi_{K}})^{-1}P^{\pi^{*}}(Q^{*}-Q_{K})-\gamma(I-\gamma
P^{\pi_{K}})^{-1}P^{\pi_{K}}(Q^{*}-Q_{K}).$ (3)

Combining Equation (3) with Equations (1) and (2), we have

$\displaystyle Q^{*}-Q^{\pi_{K}}$ $\displaystyle\leq(I-\gamma
P^{\pi_{K}})^{-1}\left(\sum_{k=0}^{K-1}\gamma^{K-k}(P^{\pi^{*}})^{K-k}\epsilon_{k}+\gamma^{K+1}(P^{\pi^{*}})^{K+1}(Q^{*}-Q_{0})\right)-$
$\displaystyle(I-\gamma
P^{\pi_{K}})^{-1}\left(\sum_{k=0}^{K-1}\gamma^{K-k}(P^{\pi_{K}}\ldots
P^{\pi_{k+1}})\epsilon_{k}+\gamma^{K+1}(P^{\pi_{K}}\ldots
P^{\pi_{0}})(Q^{*}-Q_{0})\right).$

Using the triangle inequality, the above inequality becomes

$\displaystyle
Q^{*}-Q^{\pi_{K}}\leq\frac{2\gamma(1-\gamma^{K+1})}{(1-\gamma)^{2}}\left(\sum_{k=0}^{K-1}\alpha_{k}A_{k}|\epsilon_{k}|+\alpha_{K}A_{K}|Q^{*}-Q_{0}|\right),$

where

$\displaystyle A_{k}$ $\displaystyle=\frac{1-\gamma}{2}(I-\gamma
P^{\pi_{K}})^{-1}\left((P^{\pi^{*}})^{K-k}+P^{\pi_{K}}\ldots
P^{\pi_{k+1}}\right),\forall k<K,$ $\displaystyle A_{K}$
$\displaystyle=\frac{1-\gamma}{2}(I-\gamma
P^{\pi_{K}})^{-1}\left((P^{\pi^{*}})^{K+1}+P^{\pi_{K}}\ldots
P^{\pi_{0}}\right),$ $\displaystyle\alpha_{k}$
$\displaystyle=\gamma^{K-k-1}(1-\gamma)/(1-\gamma^{K+1}),\forall k<K,$
$\displaystyle\alpha_{K}$
$\displaystyle=\gamma^{K}(1-\gamma)/(1-\gamma^{K+1}).$

Note that $A_{k}$ is a probability kernel for all $k$ and
$\sum_{k}\alpha_{k}=1$. Thus, similar to the steps in the OPE setting, for any
policy $\pi$, we have

$\displaystyle\|Q^{*}-Q^{\pi_{K}}\|_{\rho^{\pi}}^{2}$
$\displaystyle\leq\left[\frac{2\gamma(1-\gamma^{K+1})}{(1-\gamma)^{2}}\right]^{2}\left(\int\rho(ds)\pi(da|s)\sum_{k=0}^{K-1}\alpha_{k}A_{k}\epsilon_{k}^{2}(s,a)+\alpha_{K}\right)$
$\displaystyle\leq\left[\frac{2\gamma(1-\gamma^{K+1})}{(1-\gamma)^{2}}\right]^{2}\left(\int\mu(ds,da)\sum_{k=0}^{K-1}\alpha_{k}\kappa_{\mu}\epsilon_{k}^{2}(s,a)+\alpha_{K}\right)$
$\displaystyle=\left[\frac{2\gamma(1-\gamma^{K+1})}{(1-\gamma)^{2}}\right]^{2}\left(\sum_{k=0}^{K-1}\alpha_{k}\kappa_{\mu}\|\epsilon_{k}\|^{2}_{\mu}+\alpha_{K}\right)$
$\displaystyle\leq\frac{4\gamma^{2}\kappa_{\mu}}{(1-\gamma)^{4}}\max_{0\leq
k\leq K-1}\|\epsilon_{k}\|_{\mu}^{2}+\frac{4\gamma^{K+2}}{(1-\gamma)^{3}}.$

Thus, we have

$\displaystyle\|Q^{*}-Q^{\pi_{K}}\|_{\rho^{\pi}}\leq\frac{2\gamma\sqrt{\kappa_{\mu}}}{(1-\gamma)^{2}}\max_{0\leq
k\leq K-1}\|\epsilon_{k}\|_{\mu}+\frac{2\gamma^{K/2+1}}{(1-\gamma)^{3/2}}.$

Finally, we have

$\displaystyle\text{SubOpt}(\pi_{K})$
$\displaystyle=\mathbb{E}_{\rho}\left[Q^{*}(s,\pi^{*}(s))-Q^{*}(s,\pi_{K}(s))\right]$
$\displaystyle\leq\mathbb{E}_{\rho}\left[Q^{*}(s,\pi^{*}(s))-Q^{\pi_{K}}(s,\pi^{*}(s))+Q^{\pi_{K}}(s,\pi_{K}(s))-Q^{*}(s,\pi_{K}(s))\right]$
$\displaystyle\leq\|Q^{*}-Q^{\pi_{K}}\|_{\rho^{\pi^{*}}}+\|Q^{*}-Q^{\pi_{K}}\|_{\rho^{\pi_{K}}}$
$\displaystyle\leq\frac{4\gamma\sqrt{\kappa_{\mu}}}{(1-\gamma)^{2}}\max_{0\leq
k\leq K-1}\|\epsilon_{k}\|_{\mu}+\frac{4\gamma^{K/2+1}}{(1-\gamma)^{3/2}}.$

∎

#### Step 2: A Bellman error decomposition

The next step of the proof is to decompose the Bellman errors
$\|Q_{k+1}-T^{\pi}Q_{k}\|_{\mu}$ for OPE and $\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}$
for OPL. Since these errors can be decomposed and bounded similarly, we only
focus on OPL here.

The difficulty in controlling the estimation error
$\|Q_{k+1}-T^{*}Q_{k}\|_{2,\mu}$ is that $Q_{k}$ itself is a random variable
that depends on the offline data $\mathcal{D}$. In particular, at any fixed
$k$ with Bellman targets $\\{y_{i}\\}_{i=1}^{n}$ where
$y_{i}=r_{i}+\gamma\max_{a^{\prime}}Q_{k}(s_{i}^{\prime},a^{\prime})$, it is
not immediate that $\mathbb{E}\left[[T^{*}Q_{k}](x_{i})-y_{i}|x_{i}\right]=0$
for each covariate $x_{i}:=(s_{i},a_{i})$ as $Q_{k}$ itself depends on $x_{i}$
(thus the tower law cannot apply here). A naive and simple approach to break
such data dependency of $Q_{k}$ is to split the original data $\mathcal{D}$
into $K$ disjoint subsets and estimate each $Q_{k}$ using a separate subset.
This naive approach is equivalent to the setting in (Yang et al., 2019) where
a fresh batch of data is generated for different iterations. This approach is
however not efficient as it uses only $n/K$ samples to estimate each $Q_{k}$.
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 $Q_{k}$.
This requires a different approach to handle the complicated data dependency
of each $Q_{k}$. To circumvent this issue, we leverage a uniform convergence
argument by introducing a deterministic covering of $T^{*}\mathcal{F}_{NN}$.
Each element of the deterministic covering induces a different regression
target
$\\{r_{i}+\gamma\max_{a^{\prime}}\tilde{Q}(s^{\prime}_{i},a^{\prime})\\}_{i=1}^{n}$
where $\tilde{Q}$ is a deterministic function from the covering which ensures
that
$\mathbb{E}\left[r_{i}+\gamma\max_{a^{\prime}}\tilde{Q}(s^{\prime}_{i},a^{\prime})-[T^{*}\tilde{Q}](x_{i})|x_{i}\right]=0$.
In particular, we denote

$\displaystyle
y_{i}^{Q_{k}}=r_{i}+\gamma\max_{a^{\prime}}Q_{k}(s^{\prime}_{i},a^{\prime}),\forall
i\text{ and
}\hat{f}^{Q_{k}}:=Q_{k+1}=\operatorname*{arg\,inf}_{f\in\mathcal{F}_{NN}}\sum_{i=1}^{n}l(f(x_{i}),y_{i}^{Q_{k}}),\text{
and }f_{*}^{Q_{k}}=T^{*}Q_{k},$

where $l(x,y)=(x-y)^{2}$ is the squared loss function. Note that for any
deterministic $Q\in\mathcal{F}_{NN}$, we have
$f_{*}^{Q}(x_{1})=\mathbb{E}[y_{1}^{Q}|x_{1}],\forall x_{1}$, thus

$\displaystyle\mathbb{E}(l_{f}-l_{f_{*}^{Q}})=\|f-f_{*}^{Q}\|_{\mu}^{2},\forall
f,$ (4)

where $l_{f}$ denotes the random variable $(f(x_{1})-y_{1}^{Q})^{2}$. Now
letting
$f_{\perp}^{Q}:=\operatorname*{arg\,inf}_{f\in\mathcal{F}_{NN}}\|f-f_{*}^{Q}\|_{2,\mu}$
be the projection of $f_{*}^{Q}$ onto the function class $\mathcal{F}_{NN}$,
we have

$\displaystyle\max_{k}\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}^{2}$
$\displaystyle=\max_{k}\|\hat{f}^{Q_{k}}-f_{*}^{Q_{k}}\|_{\mu}^{2}\overset{(a)}{\leq}\sup_{Q\in\mathcal{F}_{NN}}\|\hat{f}^{Q}-f_{*}^{Q}\|_{\mu}^{2}\overset{(b)}{=}\sup_{Q\in\mathcal{F}_{NN}}\mathbb{E}(l_{\hat{f}^{Q}}-l_{f_{*}^{Q}})$
$\displaystyle\overset{(c)}{\leq}\sup_{Q\in\mathcal{F}_{NN}}\left\\{\mathbb{E}(l_{\hat{f}^{Q}}-l_{f_{*}^{Q}})+\mathbb{E}_{n}(l_{f_{\perp}^{Q}}-l_{\hat{f}^{Q}})\right\\}$
$\displaystyle=\sup_{Q\in\mathcal{F}_{NN}}\left\\{(\mathbb{E}-\mathbb{E}_{n})(l_{\hat{f}^{Q}}-l_{f_{*}^{Q}})+\mathbb{E}_{n}(l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}})\right\\}$
$\displaystyle\leq\underbrace{\sup_{Q\in\mathcal{F}_{NN}}(\mathbb{E}-\mathbb{E}_{n})(l_{\hat{f}^{Q}}-l_{f_{*}^{Q}})}_{I_{1},\text{empirical
process
term}}+\underbrace{\sup_{Q\in\mathcal{F}_{NN}}\mathbb{E}_{n}(l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}})}_{I_{2},\text{bias
term}},$ (5)

where (a) follows from that $Q_{k}\in\mathcal{F}_{NN}$, (b) follows from
Equation (4), and (c) follows from that
$\mathbb{E}_{n}[l_{\hat{f}^{Q}}]\leq\mathbb{E}_{n}[l_{f^{Q}}],\forall
f,Q\in\mathcal{F}_{NN}$. That is, the error is decomposed into two terms: the
first term $I_{1}$ resembles the empirical process in statistical learning
theory and the second term $I_{2}$ specifies the bias caused by the regression
target $f_{*}^{Q}$ not being in the function space $\mathcal{F}_{NN}$.

#### 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 (5) is taken uniformly over the
function space, thus standard concentration arguments such as Bernstein’s
inequality and Pollard’s inequality used in (Munos and Szepesvári, 2008; Le et
al., 2019) do not apply here. Second, 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 a
localization argument for local Rademacher complexities (Farrell et al.,
2018), we localize an 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 easier 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 our proof, we introduce relevant notations. Let
$\mathcal{F}-\mathcal{G}:=\\{f-g:f\in\mathcal{F},g\in\mathcal{G}\\}$, let
$N(\epsilon,\mathcal{F},\|\cdot\|)$ be the $\epsilon$-covering number of
$\mathcal{F}$ w.r.t. $\|\cdot\|$ norm,
$H(\epsilon,\mathcal{F},\|\cdot\|):=\log N(\epsilon,\mathcal{F},\|\cdot\|)$ be
the entropic number, let $N_{[]}(\epsilon,\mathcal{F},\|\cdot\|)$ be the
bracketing number of $\mathcal{F}$, i.e., the minimum number of brackets of
$\|\cdot\|$-size less than or equal to $\epsilon$, necessary to cover
$\mathcal{F}$, let $H_{[]}(\epsilon,\mathcal{F},\|\cdot\|)=\log
N_{[]}(\epsilon,\mathcal{F},\|\cdot\|)$ be the $\|\cdot\|$-bracketing metric
entropy of $\mathcal{F}$,let
$\mathcal{F}|\\{x_{i}\\}_{i=1}^{n}=\\{(f(x_{1}),...,f(x_{n}))\in\mathbb{R}^{n}|f\in\mathcal{F}\\}$,
and let $T^{*}\mathcal{F}=\\{T^{*}f:f\in\mathcal{F}\\}$. Finally, for sample
set $\\{x_{i}\\}_{i=1}^{n}$, we define the empirical norm
$\|f\|_{n}:=\sqrt{\frac{1}{n}\sum_{i=1}^{n}f(x_{i})^{2}}$.

We define the inherent Bellman error as
$d_{\mathcal{F}_{NN}}:=\sup_{Q\in\mathcal{F}_{NN}}\inf_{f\in\mathcal{F}_{NN}}\|f-T^{*}Q\|_{\mu}$.
This implies that

$\displaystyle
d_{\mathcal{F}_{NN}}^{2}:=\sup_{Q\in\mathcal{F}_{NN}}\inf_{f\in\mathcal{F}_{NN}}\|f-T^{*}Q\|_{\mu}^{2}=\sup_{Q\in\mathcal{F}_{NN}}\mathbb{E}(l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}}).$
(6)

We have

$\displaystyle|l_{f}-l_{g}|\leq 4|f-g|\text{ and }|l_{f}-l_{g}|\leq 8.$

We have

$\displaystyle
H(\epsilon,\\{l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}}:Q\in\mathcal{F}_{NN}\\}|\\{x_{i},y_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1})$
$\displaystyle\leq
H(\frac{\epsilon}{4},\\{f_{\perp}^{Q}-f_{*}^{Q}:Q\in\mathcal{F}_{NN}\\}|\\{x_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1})$
$\displaystyle\leq
H(\frac{\epsilon}{4},(\mathcal{F}-T^{*}\mathcal{F}_{NN})|\\{x_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1})$
$\displaystyle\leq
H(\frac{\epsilon}{8},\mathcal{F}_{NN}|\\{x_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1})+H(\frac{\epsilon}{8},T^{*}\mathcal{F}_{NN}|\\{x_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1})$
$\displaystyle\leq
H(\frac{\epsilon}{8},\mathcal{F}_{NN}|\\{x_{i}\\}_{i=1}^{n},\|\cdot\|_{\infty})+H(\frac{\epsilon}{8},T^{*}\mathcal{F}_{NN},\|\cdot\|_{\infty})$

For any $\epsilon^{\prime}>0$ and $\delta^{\prime}\in(0,1)$, it follows from
Lemma 5.3 with $\epsilon=1/2$ and $\alpha=\epsilon^{\prime 2}$, with
probability at least $1-\delta^{\prime}$, for any $Q\in\mathcal{F}_{NN}$, we
have

$\displaystyle\mathbb{E}_{n}(l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}})\leq
3\mathbb{E}(l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}})+\epsilon^{\prime 2}\leq
3d_{\mathcal{F}_{NN}}^{2}+\epsilon^{\prime 2},$ (7)

given that

$\displaystyle n\approx\frac{1}{\epsilon^{\prime
2}}\left(\log(4/\delta^{\prime})+\log\mathbb{E}N(\frac{\epsilon^{\prime
2}}{40},(\mathcal{F}_{NN}-T^{*}\mathcal{F}_{NN})|\\{x_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1})\right).$

Note that if we use Pollard’s inequality (Munos and Szepesvári, 2008) in the
place of Lemma 5.3, the RHS of Equation (7) is bounded by $\epsilon^{\prime}$
instead of $\epsilon^{\prime 2}$(i.e., $n$ scales with $O(1/\epsilon^{\prime
4})$ instead of $O(1/\epsilon^{\prime 2})$). In addition, unlike (Le et al.,
2019), the uniform convergence argument hinders the application of Bernstein’s
inequality. We remark that Le et al. 2019 makes a mistake in their proof by
ignoring the data-dependent structure in the algorithm (i.e., they wrongly
assume that $Q^{k}$ in Algorithm 1 is fixed and independent of
$\\{s_{i},a_{i}\\}_{i=1}^{n}$). Thus, the uniform convergence argument in our
proof is necessary.

#### Step 3.b: Bounding the empirical process term via local Rademacher
complexities

For any $Q\in\mathcal{F}_{NN}$, we have

$\displaystyle|l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}}|$ $\displaystyle\leq
2|f_{\perp}^{Q}-f_{*}^{Q}|\leq 2,$
$\displaystyle\mathbb{V}[l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}}]$
$\displaystyle\leq\mathbb{E}[(l_{f_{\perp}^{Q}}-l_{f_{*}^{Q}})^{2}]\leq
4\mathbb{E}(f_{\perp}^{Q}-f_{*}^{Q})^{2}.$

Thus, it follows from Lemma 1 (with $\alpha=1/2$) that with any
$r>0,\delta\in(0,1)$, with probability at least $1-\delta$, we have

$\displaystyle\sup\\{(\mathbb{E}-\mathbb{E}_{n})(l_{\hat{f}^{Q}}-l_{f_{*}^{Q}}):Q\in\mathcal{F}_{NN},\|\hat{f}^{Q}-f_{*}^{Q}\|^{2}_{\mu}\leq
r\\}$
$\displaystyle\leq\sup\\{(\mathbb{E}-\mathbb{E}_{n})(l_{f}-l_{g}):f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F},\|f-g\|^{2}_{\mu}\leq r\\}$ $\displaystyle\leq
3\mathbb{E}R_{n}\left\\{l_{f}-l_{g}:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|_{\mu}^{2}\leq
r\right\\}+2\sqrt{\frac{2r\log(1/\delta)}{n}}+\frac{28\log(1/\delta)}{3n}$
$\displaystyle\leq 6\mathbb{E}R_{n}\left\\{f-g:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|_{\mu}^{2}\leq
r\right\\}+2\sqrt{\frac{2r\log(1/\delta)}{n}}+\frac{28\log(1/\delta)}{3n}.$

#### Step 3.c: Bounding $\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}$ using localization
argument via sub-root functions

We bound $\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}$ using the localization argument,
breaking down the Rademacher complexities into local balls and then build up
the original function space from the local balls. Let $\psi$ be a sub-root
function (Bartlett et al., 2005, Definition 3.1) with the fixed point $r_{*}$
and assume that for any $r\geq r_{*}$, we have

$\displaystyle\psi(r)\geq
3\mathbb{E}R_{n}\left\\{f-g:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|_{\mu}^{2}\leq r\right\\}.$ (8)

We recall that a function $\psi:[0,\infty)\rightarrow[0,\infty)$ is sub-root
if it is non-negative, non-decreasing and $r\mapsto\psi(r)/\sqrt{r}$ is non-
increasing for $r>0$. Consequently, a sub-root function $\psi$ has a unique
fixed point $r_{*}$ where $r_{*}=\psi(r_{*})$. In addition,
$\psi(r)\leq\sqrt{rr_{*}},\forall r\geq r_{*}$. In the next step, we will find
a sub-root function $\psi$ that satisfies the inequality above, but for this
step we just assume that we have such $\psi$ at hand. Combining Equations (5),
(7), and (8), we have: for any $r\geq r_{*}$ and any $\delta\in(0,1)$, if
$\|\hat{f}^{Q_{k-1}}-f_{*}^{Q_{k-1}}\|_{2,\mu}^{2}\leq r$, with probability at
least $1-\delta$,

$\displaystyle\|\hat{f}^{Q_{k-1}}-f_{*}^{Q_{k-1}}\|_{2,\mu}^{2}$
$\displaystyle\leq
2\psi(r)+2\sqrt{\frac{2r\log(2/\delta)}{n}}+\frac{28\log(2/\delta)}{3n}+3d^{2}_{\mathcal{F}}+\epsilon^{\prime
2}$
$\displaystyle\leq\sqrt{rr_{*}}+2\sqrt{\frac{2r\log(2/\delta)}{n}}+\frac{28\log(2/\delta)}{3n}+(\sqrt{3}d_{\mathcal{F}}+\epsilon^{\prime})^{2},$

where

$\displaystyle n\approx\frac{1}{4\epsilon^{\prime
2}}\left(\log(8/\delta)+\log\mathbb{E}N(\frac{\epsilon^{\prime
2}}{20},(\mathcal{F}_{NN}-T^{*}\mathcal{F}_{NN})|\\{x_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1})\right).$

Consider $r_{0}\geq r_{*}$ (to be chosen later) and denote the events

$\displaystyle B_{k}:=\\{\|\hat{f}^{Q_{k-1}}-f_{*}^{Q_{k-1}}\|^{2}_{2,\mu}\leq
2^{k}r_{0}\\},\forall k\in\\{0,1,...,l\\},$

where $l=\log_{2}(\frac{1}{r_{0}})\leq\log_{2}(\frac{1}{r_{*}})$. We have
$B_{0}\subseteq B_{1}\subseteq...\subseteq B_{l}$ and since
$\|f-g\|_{\mu}^{2}\leq 1,\forall|f|_{\infty},|g|_{\infty}\leq 1$, we have
$P(B_{l})=1$. If $\|\hat{f}^{Q_{k-1}}-f_{*}^{Q_{k-1}}\|^{2}_{\mu}\leq
2^{i}r_{0}$ for some $i\leq l$, then with probability at least $1-\delta$, we
have

$\displaystyle\|\hat{f}^{Q_{k-1}}-f_{*}^{Q_{k-1}}\|_{2,\mu}^{2}$
$\displaystyle\leq\sqrt{2^{i}r_{0}r_{*}}+2\sqrt{\frac{2^{i+1}r_{0}\log(2/\delta)}{n}}+\frac{28\log(2/\delta)}{3n}+(\sqrt{3}d_{\mathcal{F}_{NN}}+\epsilon^{\prime})^{2}$
$\displaystyle\leq 2^{i-1}r_{0},$

if the following inequalities hold

$\displaystyle\sqrt{2^{i}r_{*}}+2\sqrt{\frac{2^{i+1}\log(2/\delta)}{n}}$
$\displaystyle\leq\frac{1}{2}2^{i-1}\sqrt{r_{0}},$
$\displaystyle\frac{28\log(2/\delta)}{3n}+(\sqrt{3}d_{\mathcal{F}_{NN}}+\epsilon^{\prime})^{2}$
$\displaystyle\leq\frac{1}{2}2^{i-1}r_{0}.$

We choose $r_{0}\geq r_{*}$ such that the inequalities above hold for all
$0\leq i\leq l$. This can be done by simply setting

$\displaystyle\sqrt{r_{0}}$
$\displaystyle=\frac{2}{2^{i-1}}\left(\sqrt{2^{i}r_{*}}+2\sqrt{\frac{2^{i+1}\log(2/\delta)}{n}}\right)\bigg{|}_{i=0}+\sqrt{\frac{2}{2^{i-1}}\left(\frac{28\log(2/\delta)}{3n}+(\sqrt{3}d_{\mathcal{F}_{NN}}+\epsilon^{\prime})^{2}\right)}\bigg{|}_{i=0}$
$\displaystyle\lesssim
d_{\mathcal{F}_{NN}}+\epsilon^{\prime}+\sqrt{\frac{\log(2/\delta)}{n}}+\sqrt{r_{*}}.$

Since $\\{B_{i}\\}$ is a sequence of increasing events, we have

$\displaystyle P(B_{0})$ $\displaystyle=P(B_{1})-P(B_{1}\cap
B_{0}^{c})=P(B_{2})-P(B_{2}\cap B_{1}^{c})-P(B_{1}\cap B_{0}^{c})$
$\displaystyle=P(B_{l})-\sum_{i=0}^{l-1}P(B_{i+1}\cap B_{i}^{c})\geq
1-l\delta.$

Thus, with probability at least $1-\delta$, we have

$\|\hat{f}^{Q_{k-1}}-f_{*}^{Q_{k-1}}\|_{\mu}\lesssim
d_{\mathcal{F}_{NN}}+\epsilon^{\prime}+\sqrt{\frac{\log(2l/\delta)}{n}}+\sqrt{r_{*}}$
(9)

where

$\displaystyle n\approx\frac{1}{4\epsilon^{\prime
2}}\left(\log(8l/\delta)+\log\mathbb{E}N(\frac{\epsilon^{\prime
2}}{20},(\mathcal{F}_{NN}-T^{*}\mathcal{F}_{NN})|\\{x_{i}\\}_{i=1}^{n},n^{-1}\|\cdot\|_{1}))\right).$

#### Step 3.d: Finding a sub-root function and its fixed point

It remains to find a sub-root function $\psi(r)$ that satisfies Equation (8)
and thus its fixed point. The main idea is to bound the RHS, the local
Rademacher complexity, of Equation (8) 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 $\mathcal{F}_{NN}$ and
$T^{*}\mathcal{F}_{NN}$.

For any $\epsilon>0$, we have the following inequalities for entropic numbers:

$\displaystyle
H(\epsilon,\mathcal{F}_{NN}-T^{*}\mathcal{F}_{NN},\|\cdot\|_{n})$
$\displaystyle\leq
H(\epsilon/2,\mathcal{F}_{NN},\|\cdot\|_{n})+H(\epsilon/2,T^{*}\mathcal{F}_{NN},\|\cdot\|_{n}),$
$\displaystyle H(\epsilon,\mathcal{F}_{NN},\|\cdot\|_{n})$ $\displaystyle\leq
H(\epsilon,\mathcal{F}_{NN}|\\{x_{i}\\}_{i=1}^{n},\|\cdot\|_{\infty})\overset{(a)}{\lesssim}N[(\log
N)^{2}+\log(1/\epsilon)],$ (10) $\displaystyle
H(\epsilon,T^{*}\mathcal{F}_{NN},\|\cdot\|_{n})$ $\displaystyle\leq
H(\epsilon,T^{*}\mathcal{F}_{NN},\|\cdot\|_{\infty})\leq
H_{[]}(2\epsilon,T^{*}\mathcal{F}_{NN},\|\cdot\|_{\infty})$
$\displaystyle\overset{(b)}{\leq}H_{[]}(2\epsilon,\bar{B}^{\alpha}_{p,q}(\mathcal{X}),\|\cdot\|_{\infty})\overset{(c)}{\lesssim}(2\epsilon)^{-d/\alpha},$
(11)

where $N$ is a hyperparameter of the deep ReLU network described in Lemma
5.10, (a) follows from Lemma 5.10, and (b) follows from Assumption 3.2, and
(c) follows from Lemma 5.9. Let
$\mathcal{H}:=\mathcal{F}_{NN}-T^{*}\mathcal{F}_{NN}$, it follows from Lemma
5.6 with $\\{\xi_{k}:=\epsilon/2^{k}\\}_{k\in\mathbb{N}}$ for any $\epsilon>0$
that

$\displaystyle\mathbb{E}_{\sigma}R_{n}\\{h\in\mathcal{H}-\mathcal{H}:\|h\|_{n}\leq\epsilon\\}\leq
4\sum_{k=1}^{\infty}\frac{\epsilon}{2^{k-1}}\sqrt{\frac{H(\epsilon/2^{k-1},\mathcal{H},\|\cdot\|_{n})}{n}}$
$\displaystyle\leq
4\sum_{k=1}^{\infty}\frac{\epsilon}{2^{k-1}}\sqrt{\frac{H(\epsilon/2^{k},\mathcal{F}_{NN},\|\cdot\|_{\infty})}{n}}+4\sum_{k=1}^{\infty}\frac{\epsilon}{2^{k-1}}\sqrt{\frac{H(\epsilon/2^{k},T^{\pi}\mathcal{F}_{NN},\|\cdot\|_{\infty})}{n}}$
$\displaystyle\leq\frac{4\epsilon}{\sqrt{n}}\sum_{k=1}^{\infty}2^{-(k-1)}\sqrt{N\left((\log
N)^{2}+\log(2^{k}/\epsilon)\right)}+\frac{4\epsilon}{\sqrt{n}}\sum_{k=1}^{\infty}2^{-(k-1)}\sqrt{\left(\frac{\epsilon}{2^{k-1}}\right)^{-d/\alpha}}$
$\displaystyle\lesssim\frac{\epsilon}{\sqrt{n}}\sqrt{N((\log
N)^{2}+\log(1/\epsilon))}+\frac{\epsilon^{1-\frac{d}{2\alpha}}}{\sqrt{n}},$

where we use $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b},\forall a,b\geq 0$,
$\sum_{k=1}^{\infty}\frac{\sqrt{k}}{2^{k-1}}<\infty$, and
$\sum_{k=1}^{\infty}\left(\frac{1}{2^{1-\frac{d}{2\alpha}}}\right)^{k-1}<\infty$.

It now follows from Lemma 5.5 that

$\displaystyle\mathbb{E}_{\sigma}R_{n}\\{f\in\mathcal{F},g\in
T^{*}\mathcal{F}:\|f-g\|_{n}^{2}\leq r\\}$
$\displaystyle\leq\inf_{\epsilon>0}\bigg{[}\mathbb{E}_{\sigma}R_{n}\\{h\in\mathcal{H}-\mathcal{H}:\|h\|_{\mu}\leq\epsilon\\}+\sqrt{\frac{2rH(\epsilon/2,\mathcal{H},\|\cdot\|_{n})}{n}}\bigg{]}$
$\displaystyle\lesssim\bigg{[}\frac{\epsilon}{\sqrt{n}}\sqrt{N((\log
N)^{2}+\log(1/\epsilon))}+\frac{\epsilon^{1-\frac{d}{2\alpha}}}{\sqrt{n}}+\sqrt{\frac{2r}{n}}\sqrt{N((\log
N)^{2}+\log(4/\epsilon))}+\sqrt{\frac{2r}{n}}(\epsilon/2)^{\frac{-d}{2\alpha}}\bigg{]}\bigg{|}_{\epsilon=n^{-\beta}}$
$\displaystyle\asymp n^{-\beta-1/2}\sqrt{N(\log^{2}N+\log
n)}+n^{-\beta(1-\frac{d}{2\alpha})-1/2}+\sqrt{\frac{r}{n}}\sqrt{N(\log^{2}N+\log
n)}+\sqrt{r}n^{-\frac{1}{2}(1-\frac{\beta d}{\alpha})}=:\psi_{1}(r),$

where $\beta\in(0,\frac{\alpha}{d})$ is an absolute constant to be chosen
later.

Note that
$\mathbb{V}[(f-g)^{2}]\leq\mathbb{E}[(f-g)^{4}]\leq\mathbb{E}[(f-g)^{2}]$ for
any $f\in\mathcal{F}_{NN},g\in T^{*}\mathcal{F}_{NN}$. Thus, for any $r\geq
r_{*}$, it follows from Lemma 5.2 that with probability at least
$1-\frac{1}{n}$, we have the following inequality for any
$f\in\mathcal{F}_{NN},g\in T^{*}\mathcal{F}_{NN}$ such that
$\|f-g\|^{2}_{\mu}\leq r$,

$\displaystyle\|f-g\|_{n}^{2}$
$\displaystyle\leq\|f-g\|^{2}_{\mu}+3\mathbb{E}R_{n}\\{(f-g)^{2}:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|^{2}_{\mu}\leq r\\}+\sqrt{\frac{2r\log
n}{n}}+\frac{56}{3}\frac{\log n}{n}$
$\displaystyle\leq\|f-g\|^{2}_{\mu}+3\mathbb{E}R_{n}\\{f-g:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|^{2}_{\mu}\leq r\\}+\sqrt{\frac{2r\log
n}{n}}+\frac{56}{3}\frac{\log n}{n}$ $\displaystyle\leq r+\psi(r)+r+r\leq 4r,$

if $r\geq r_{*}\lor\frac{2logn}{n}\lor\frac{56logn}{3n}$. For such $r$, denote
$E_{r}=\\{\|f-g\|_{n}^{2}\leq 4r\\}\cap\\{\|f-f_{*}\|_{\mu}^{2}\leq r\\}$, we
have $P(E_{r})\geq 1-1/n$ and

$\displaystyle 3\mathbb{E}R_{n}\\{f-g:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|^{2}_{\mu}\leq r\\}$
$\displaystyle=3\mathbb{E}\mathbb{E}_{\sigma}R_{n}\\{f-g:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|^{2}_{\mu}\leq r\\}$ $\displaystyle\leq
3\mathbb{E}\bigg{[}1_{E_{r}}\mathbb{E}_{\sigma}R_{n}\\{f-g:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|^{2}_{\mu}\leq r\\}+(1-1_{E_{r}})\bigg{]}$
$\displaystyle\leq
3\mathbb{E}\bigg{[}\mathbb{E}_{\sigma}R_{n}\\{f-g:f\in\mathcal{F}_{NN},g\in
T^{*}\mathcal{F}_{NN},\|f-g\|^{2}_{n}\leq 4r\\}+(1-1_{E_{r}})\bigg{]}$
$\displaystyle\leq 3(\psi_{1}(4r)+\frac{1}{n})$ $\displaystyle\lesssim
n^{-\beta-1/2}\sqrt{N(\log^{2}N+\log
n)}+n^{-\beta(1-\frac{d}{2\alpha})-1/2}+\sqrt{\frac{r}{n}}\sqrt{N(\log^{2}N+\log
n)}$ $\displaystyle+\sqrt{r}n^{-\frac{1}{2}(1-\frac{\beta
d}{\alpha})}+n^{-1}=:\psi(r)$

It is easy to verify that $\psi(r)$ defined above is a sub-root function. The
fixed point $r_{*}$ of $\psi(r)$ can be solved analytically via the simple
quadratic equation $r_{*}=\psi(r_{*})$. In particular, we have

$\displaystyle\sqrt{r_{*}}$ $\displaystyle\lesssim
n^{-1/2}\sqrt{N(\log^{2}N+\log n)}+n^{-\frac{1}{2}(1-\frac{\beta
d}{\alpha})}+n^{-\frac{\beta}{2}-\frac{1}{4}}[N(\log^{2}N+\log n)]^{1/4}$
$\displaystyle+n^{-\frac{\beta}{2}(1-\frac{d}{2\alpha})-\frac{1}{2}}+n^{-1/2}$
$\displaystyle\lesssim n^{-\frac{1}{4}((2\beta)\land
1)+1)}\sqrt{N(\log^{2}N+\log n)}+n^{-\frac{1}{2}(1-\frac{\beta
d}{\alpha})}+n^{-\frac{\beta}{2}(1-\frac{d}{2\alpha})-\frac{1}{2}}+n^{-1/2}$
(12)

It follows from Equation (9) (where $l\lesssim\log(1/r_{*})$), the definition
of $d_{\mathcal{F}_{NN}}$, Lemma 5.10, and Equation (12) that for any
$\epsilon^{\prime}>0$ and $\delta\in(0,1)$, with probability at least
$1-\delta$, we have

$\displaystyle\max_{k}\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}$ $\displaystyle\lesssim
N^{-\alpha/d}+\epsilon^{\prime}+n^{-\frac{1}{4}((2\beta)\land
1)+1)}\sqrt{N(\log^{2}N+\log n)}+n^{-\frac{1}{2}(1-\frac{\beta d}{\alpha})}$
$\displaystyle+n^{-\frac{\beta}{2}(1-\frac{d}{2\alpha})-\frac{1}{2}}+n^{-1/2}\sqrt{\log(1/\delta)+\log\log
n}$ (13)

where

$\displaystyle n$ $\displaystyle\gtrsim\frac{1}{4\epsilon^{\prime
2}}\bigg{(}\log(1/\delta)+\log\log n+\log\mathbb{E}N(\frac{\epsilon^{\prime
2}}{20},(\mathcal{F}_{NN}-T^{*}\mathcal{F}_{NN})|\\{x_{i}\\}_{i=1}^{n},n^{-1}\cdot\|\cdot\|_{1}))\bigg{)}.$
(14)

#### 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 $\beta\in(0,\frac{\alpha}{d})$
and $N\in\mathbb{N}$. Note that $N$ parameterizes the deep ReLU architecture
$\Phi(L,m,S,B)$ given Lemma 5.10. In particular, we optimize over
$\beta\in(0,\frac{\alpha}{d})$ and $N\in\mathbb{N}$ to minimize the upper
bound in the RHS of Equation (13). The RHS of Equation (13) is minimized (up
to $\log n$-factor) by choosing

$\displaystyle N\asymp n^{\frac{1}{2}((2\beta\land
1)+1)\frac{d}{2\alpha+d}}\text{ and
}\beta=\left(2+\frac{d^{2}}{\alpha(\alpha+d)}\right)^{-1},$ (15)

which results in $N\asymp n^{\frac{1}{2}(2\beta+1)\frac{d}{2\alpha+d}}$. At
these optimal values, Equation (13) becomes

$\displaystyle\max_{k}\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}$
$\displaystyle\lesssim\epsilon^{\prime}+n^{-\frac{1}{2}\left(\frac{2\alpha}{2\alpha+d}+\frac{d}{\alpha}\right)^{-1}}\log
n+n^{-1/2}\sqrt{\log(1/\delta)+\log\log n},$ (16)

where we use inequalities
$n^{-\frac{\beta}{2}(1-\frac{d}{2\alpha})-\frac{1}{2}}\leq
n^{-\frac{1}{2}(1-\frac{\beta d}{\alpha})}\asymp
N^{-\alpha/d}=n^{-\frac{1}{2}\left(\frac{2\alpha}{2\alpha+d}+\frac{d}{\alpha}\right)^{-1}}$.

Now, for any $\epsilon>0$, we set $\epsilon^{\prime}=\epsilon/3$ and let

$\displaystyle
n^{-\frac{1}{2}\left(\frac{2\alpha}{2\alpha+d}+\frac{d}{\alpha}\right)^{-1}}\log
n\lesssim\epsilon/3\text{ and }n^{-1/2}\sqrt{\log(1/\delta)+\log\log
n}\lesssim\epsilon/3.$

It then follows from Equation (16) that with probability at least $1-\delta$,
we have $\max_{k}\|Q_{k+1}-T^{*}Q_{k}\|_{\mu}\leq\epsilon$ if $n$
simultaneously satisfies Equation (14) with $\epsilon^{\prime}=\epsilon/3$ and

$\displaystyle
n\gtrsim\left(\frac{1}{\epsilon^{2}}\right)^{\frac{2\alpha}{2\alpha+d}+\frac{d}{\alpha}}(\log^{2}n)^{\frac{2\alpha}{2\alpha+d}+\frac{d}{\alpha}}\text{
and }n\gtrsim\frac{1}{\epsilon^{2}}\left(\log(1/\delta)+\log\log n\right).$
(17)

Next, we derive an explicit formula of the sample complexity satisfying
Equation (14). Using Equations (13), (17), and (15), we have that $n$
satisfies Equation (14) if

$\displaystyle\begin{cases}n&\gtrsim\frac{1}{\epsilon^{2}}\left[n^{\frac{2\beta+1}{2}\frac{d}{2\alpha+d}}(\log^{2}n+\log(1/\epsilon))\right],\\\
n&\gtrsim\left(\frac{1}{\epsilon^{2}}\right)^{1+\frac{d}{\alpha}},\\\
n&\gtrsim\frac{1}{\epsilon^{2}}\left(\log(1/\delta)+\log\log
n\right).\end{cases}$ (18)

Note that $\beta\leq 1/2$ and $\frac{d}{\alpha}\leq 2$; thus, we have

$\displaystyle\left(1-\frac{2\beta+1}{2}\frac{d}{2\alpha+d}\right)^{-1}\leq
1+\frac{d}{\alpha}\leq 3.$

Hence, $n$ satisfies Equations (17) and (18) if

$\displaystyle
n\gtrsim\left(\frac{1}{\epsilon^{2}}\right)^{1+\frac{d}{\alpha}}\log^{6}n+\frac{1}{\epsilon^{2}}(\log(1/\delta)+\log\log
n).$

## Appendix B. Technical Lemmas

######  Lemma 5.2 (Bartlett et al. (2005)).

Let $r>0$ and let

$\displaystyle\mathcal{F}\subseteq\\{f:\mathcal{X}\rightarrow[a,b]:\mathbb{V}[f(X_{1})]\leq
r\\}.$

  1. 1.

For any $\lambda>0$, we have with probability at least $1-e^{-\lambda}$,

$\displaystyle\sup_{f\in\mathcal{F}}\left(\mathbb{E}f-\mathbb{E}_{n}f\right)\leq\inf_{\alpha>0}\left(2(1+\alpha)\mathbb{E}\left[R_{n}\mathcal{F}\right]+\sqrt{\frac{2r\lambda}{n}}+(b-a)\left(\frac{1}{3}+\frac{1}{\alpha}\right)\frac{\lambda}{n}\right).$

  2. 2.

With probability at least $1-2e^{-\lambda}$,

$\displaystyle\sup_{f\in\mathcal{F}}\left(\mathbb{E}f-\mathbb{E}_{n}f\right)\leq\inf_{\alpha\in(0,1)}\left(\frac{2(1+\alpha)}{(1-\alpha)}\mathbb{E}_{\sigma}\left[R_{n}\mathcal{F}\right]+\sqrt{\frac{2r\lambda}{n}}+(b-a)\left(\frac{1}{3}+\frac{1}{\alpha}+\frac{1+\alpha}{2\alpha(1-\alpha)}\right)\frac{\lambda}{n}\right).$

Moreover, the same results hold for
$\sup_{f\in\mathcal{F}}\left(\mathbb{E}_{n}f-\mathbb{E}f\right)$.

######  Lemma 5.3 (Györfi et al. (2002, Theorem 11.6)).

Let $B\geq 1$ and $\mathcal{F}$ be a set of functions
$f:\mathbb{R}^{d}\rightarrow[0,B]$. Let $Z_{1},...,Z_{n}$ be i.i.d.
$\mathbb{R}^{d}$-valued random variables. For any $\alpha>0$, $0<\epsilon<1$,
and $n\geq 1$, we have

$\displaystyle
P\left\\{\sup_{f\in\mathcal{F}}\frac{\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})-\mathbb{E}[f(Z)]}{\alpha+\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})+\mathbb{E}[f(Z)]}>\epsilon\right\\}\leq
4\mathbb{E}N(\frac{\alpha\epsilon}{5},\mathcal{F}|Z_{1}^{n},n^{-1}\|\cdot\|_{1})\exp\left(\frac{-3\epsilon^{2}\alpha
n}{40B}\right).$

######  Lemma 5.4 (Contraction property (Rebeschini, 2019)).

Let $\phi:\mathbb{R}\rightarrow\mathbb{R}$ be a $L$-Lipschitz, then

$\displaystyle\mathbb{E}_{\sigma}R_{n}\left(\phi\circ\mathcal{F}\right)\leq
L\mathbb{E}_{\sigma}R_{n}\mathcal{F}.$

######  Lemma 5.5 (Lei et al. (2016, Lemma 1)).

Let $\mathcal{F}$ be a function class and $P_{n}$ be the empirical measure
supported on $X_{1},...,X_{n}\sim\mu$, then for any $r>0$ (which can be
stochastic w.r.t $X_{i}$), we have

$\displaystyle\mathbb{E}_{\sigma}R_{n}\\{f\in\mathcal{F}:\|f\|_{n}^{2}\leq
r\\}\leq\inf_{\epsilon>0}\bigg{[}\mathbb{E}_{\sigma}R_{n}\\{f\in\mathcal{F}-\mathcal{F}:\|f\|_{\mu}\leq\epsilon\\}+\sqrt{\frac{2r\log
N(\epsilon/2,\mathcal{F},\|\cdot\|_{n})}{n}}\bigg{]}.$

######  Lemma 5.6 ( Lei et al. (2016, modification)).

Let $X_{1},...,X_{n}$ be a sequence of samples and $P_{n}$ be the associated
empirical measure. For any function class $\mathcal{F}$ and any monotone
sequence $\\{\xi_{k}\\}_{k=0}^{\infty}$ decreasing to $0$, we have the
following inequality for any non-negative integer $N$

$\displaystyle\mathbb{E}_{\sigma}R_{n}\\{f\in\mathcal{F}:\|f\|_{n}\leq\xi_{0}\\}\leq
4\sum_{k=1}^{N}\xi_{k-1}\sqrt{\frac{\log\mathcal{N}(\xi_{k},\mathcal{F},\|\cdot\|_{n})}{n}}+\xi_{N}.$

######  Lemma 5.7 (Pollard’s inequality).

Let $\mathcal{F}$ be a set of measurable functions
$f:\mathcal{X}\rightarrow[0,K]$ and let $\epsilon>0,N$ arbitrary. If
$\\{X_{i}\\}_{i=1}^{N}$ is an i.i.d. sequence of random variables taking
values in $\mathcal{X}$, then

$\displaystyle
P\left(\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{N}\sum_{i=1}^{N}f(X_{i})-\mathbb{E}[f(X_{1})]\bigg{|}>\epsilon\right)\leq
8\mathbb{E}\left[N(\epsilon/8,\mathcal{F}|_{X_{1:N}})\right]e^{\frac{-N\epsilon^{2}}{128K^{2}}}.$

######  Lemma 5.8 (Properties of (bracketing) entropic numbers).

Let $\epsilon\in(0,\infty)$. We have

  1. 1.

$H(\epsilon,\mathcal{F},\|\cdot\|)\leq
H_{[]}(2\epsilon,\mathcal{F},\|\cdot\|)$;

  2. 2.

$H(\epsilon,\mathcal{F}|\\{x_{i}\\}_{i=1}^{n},n^{-1/p}\cdot\|\cdot\|_{p})=H(\epsilon,\mathcal{F},\|\cdot\|_{p,n})\leq
H(\epsilon,\mathcal{F}|\\{x_{i}\\}_{i=1}^{n},\|\cdot\|_{\infty})\leq
H(\epsilon,\mathcal{F},\|\cdot\|_{\infty})$ for all
$\\{x_{i}\\}_{i=1}^{n}\subset dom(\mathcal{F})$.

  3. 3.

$H(\epsilon,\mathcal{F}-\mathcal{F},\|\cdot\|)\leq
2H(\epsilon/2,\mathcal{F},\|\cdot\|))$, where
$\mathcal{F}-\mathcal{F}:=\\{f-g:f,g\in\mathcal{F}\\}$.

######  Lemma 5.9 (Entropic number of bounded Besov spaces (Nickl and
Pötscher, 2007, Corollary 2.2)).

For $1\leq p,q\leq\infty$ and $\alpha>d/p$, we have

$\displaystyle
H_{[]}(\epsilon,\bar{B}^{\alpha}_{p,q}(\mathcal{X}),\|\cdot\|_{\infty})\lesssim\epsilon^{-d/\alpha}.$

######  Lemma 5.10 (Approximation power of deep ReLU networks for Besov spaces
(Suzuki, 2018)).

Let $1\leq p,q\leq\infty$ and $\alpha\in(\frac{d}{p\land 2},\infty)$. For
sufficiently large $N\in\mathbb{N}$, there exists a neural network
architecture $\Phi(L,m,S,B)$ with

$\displaystyle L\asymp\log N,m\asymp N\log N,S\asymp N,\text{ and }B\asymp
N^{d^{-1}+\nu^{-1}},$

where $\nu:=\frac{\alpha-\delta}{2\delta}$ and
$\delta:=d(p^{-1}-(1+\lfloor\alpha\rfloor)^{-1})_{+}$ such that

$\displaystyle\sup_{f_{*}\in\bar{B}^{\alpha}_{p,q}(\mathcal{X})}\inf_{f\in\Phi(L,W,S,B)}\|f-f_{*}\|_{\infty}\lesssim
N^{-\alpha/d}.$