Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networks
Authors: Xiang Ji
Minshuo Chen
Mengdi Wang
Tuo Zhao
Venue: ICLR 2023 poster (2023)
Keywords: RL theory
deep off-policy evaluation
neural network function approximation
manifold data

Abstract: We consider the off-policy evaluation problem of reinforcement learning using deep convolutional neural networks. We analyze the deep fitted Q-evaluation method for estimating the expected cumulative reward of a target policy, when the data are generated from an unknown behavior policy. We show that, by choosing network size appropriately, one can leverage any low-dimensional manifold structure in the Markov decision process and obtain a sample-efficient estimator without suffering from the curse of high data ambient dimensionality. Specifically, we establish a sharp error bound for fitted Q-evaluation, which depends on the intrinsic dimension of the state-action space, the smoothness of Bellman operator, and a function class-restricted $\chi^2$-divergence. It is noteworthy that the restricted $\chi^2$-divergence measures the behavior and target policies' {\it mismatch in the function space}, which can be small even if the two policies are not close to each other in their tabular forms. We also develop a novel approximation result for convolutional neural networks in Q-function estimation. Numerical experiments are provided to support our theoretical analysis.

Published as a conference paper at ICLR 2023
SAMPLE COMPLEXITY OF NONPARAMETRIC OFF-POLICY EVALUATION ON LOW-DIMENSIONAL MANIFOLDS USING DEEP NETWORKS
Xiang Ji'
Minshuo Chen
Mengdi Wang"
Tuo Zhao'
Princetton University (xiangi, mc0750,
Georgia Institute of Technology
tourzhao@gatech..
ABSTRACT
We consider the off- evaluation problem of reinforcement learning using deep convolutional neural networks. We analyze the deep fitted Q-evaluation method for estimating the expected cumulative reward of target policy, when the data are generated from an unknown behavior policy. We show that, by choos- ing network size appropriately, one can leverage any low-dimensional manifold structure in the Markov decision process and obtain sample-efficient estimator without suffering from the curse of high data ambient dimensionality. Specifically, we establish a sharp error bound for fitted Q-evaluation, which depends on the in- trinsic dimension of the state-action space, the smoothness of Bellman operator, and a function class-restricted divdiverge It is noteworthy that the restricted diveeregee measures the behavior and target policies' mismatch in the func- tion space, which can be small even if the two policies are not close to each other in their tabular forms. We also develop novel approximation result for con- volutional neural networks in Q-function estimation. Numerical experiments are provided support our theoretical analysis.
INTRODUCTION
Off-policy Reinforcement Learning (RL) [38, 40] is an important area decision decision-making applica- tions, when the data cannot be acquired with arbitrary policies. For example, in clinical decision- making problems, experimenting new treatment policies on patients is risky and may raise ethical concerns. Therefore, we only allowed to generate data using certain policies (or sampling distri- butions), which have been approved by medical professionals. These so-called "behavior policies" unknown but could impact our problem of interest, resulting in distribution shift and insufficient data coverage of the problem space. In general, the goal is to design algorithms that need as little data as possible attain desired accuracy.
A crucial problem in off-policy RL is policy evaluation. The goal of Off-Policy Evaluation (OPE) is to estimate the value of new target policy based on experience data generated by existing behavior policies. Due to the mismatch between behavior and target policies, the off- off-policy setting is entirely different from the on-policy one, which policy value can be easily estimated via Monte Carlo.
A popular algorithm to solve OPE is the fitted Q-evaluation method (FQE), as an off-policy variant of the fitted Q-iteration [28, 15, 75]. FQE iteratively estimates Q-functions by supervised regression using various function approximation methods, e.g., linear function approximation, and has achieved great empirical success [65, 20, 21], especially large-scale Markov decision problems. Comple- mentary to the empirical studies, several works theoretically justify the success of FQE. Under linear function approximation, [31] show that FQE asymptotically efficient, and [15] further provide a minimax optimal non-asymptotic bound, and [47] provide variance-aware characterization of the distribution shift via a weighted variant of FQE. [75] analyze FQE with realizable, general differen- tiable function approximation. [37, 64] tackle OPE for more general function approximation, but they require stronger assumptions such as full data coverage. [16] focus on on-policy estimation and study kernel least square temporal difference estimator.
Recently, deploying neural networks in FQE has achieved great empirical success, which is largely due networks' superior flexibility of modeling in high-dimensional complex environments

---

Published as a conference paper at ICLR 2023
[65, 20, 21]. Nonetheless, the theory of FQE using deep neural networks has not been fully under- stood. While there are existing results on FQE with various function approximators [28, 15, 75], many of them not immediately applicable to neural network approximation. [18] focus the online policy learning problem and studies DQN with feed-forward ReI.U network; a concurrent work [73] studies offline policy learning with realizable, general differentiable function approxima- tion. Notably, a recent study [51] provide an analysis of the estimation error of nonparametric FQE using feed-forward ReLU network, yet this error bound grows quickly when data dimension is high. Moreover, their result requires full data coverage, i.e., every state-action pair has to eventually be visited in the experience data. Precisely, besides universal function approximation, there are other properties that contribute to the success of neural networks in supervised learning, for example, its ability to adapt to the intrinsic low-dimensional structure of data. While these properties are actively studied in the deep supervised learning literature, they have not been reflected in RI. theory. Hence, is of interest to examine whether these properties still hold in a problem with sequential nature under standard assumptions and how neural networks can take advantage of such low-dimensional structures in OPE.
Main results. This paper establishes sample complexity bounds of deep FQE using convolutional neural networks (CNNs). Different from existing results, our theory exploits the intrinsic geomet- ric structures in the state-action space. This is motivated by the fact that in many practical high- dimensional applications, especially image-based ones [59, 11, 76), the data are actually governed by a much smaller number of intrinsic free parameters [2, 55, 32]. See an example Figure 1.
Figure 1: An example of state-action space with low- diwdemmnniooal structures. The states of OpenAI Gym Bipedal Walker can be visually displayed in high resolution (e.g., 200 300), while they are internally represented by a 24-tuple [29].
Consequently, we model the state-action space d-dimensional Riemannian manifold embedded in IED with d < D. Under some standard regularity conditions, we show CNNs can efficiently approximate Q-functions and allow for fast-rate policy value estimation-fres of the curse of am- bient dimensionality D. Moreover, particular, we develop a function class-restricted -ddvieegee to quantify the mismatch between the visitation distributions induced by behavior and target policies. The function class be viewed as a smoothing factor of the distribution mismatch, since the function class may be insensitive to cer- tain differences in the two distributions. Our approximation theory and mismatch characterization significantly sharpen the dimension dependence of deep FQE, In detail, our theoretical results are summarized follows:
results do not need strong data coverage assumptions. In
(I) Given target policy π. we measure the distribution shift between the experience data distribution (gh data Jh=1 and the visitation distribution of target policy {9% 1/ h=1 by
data) + 1,
where x2 9 data) is the restricted x² -diveergee between 97 and data defined as
Eg [f]
22 ( Aata) = sup fee g
with Q being a function space relevant to our algorithm.
(II) We prove that the value estimation error of target policy π is
Elp" - ग.h Ö (
where is the effective sample size of experience data sampled by the behavior policy (more details in Section 3), H is the length of the horizon, is the smoothness parameter of the Bellman operator,
2

---

Published as a conference paper at ICLR 2023
is defined in (1), and Ö.) hides some constant depending on state-action space and polynomial factor in D.
We compare results with several related works in Table 1. Both [15] and [75] consider paramet- ric function approximation to the Q-function: [15] study linear function approximation, and [75] as- sume third-order differentibility, which is not applicable to neural networks with non-smooth activa- tion. On the other hand, [51] use forwwfd neural networks with ReLU activation to parametrize nonparametric Q-functions, but they do not take any low-dimensional structures of the state-action space into consideration. Therefore, their result suffer from the curse of dimension D. Moreover, they characterize the distribution shift with the absolute density ratio between the experience data distribution and the visitation distribution of target policy, which is strictly larger than our character- ization in restricted X d2-divergences. As can be seen from our comparison, our result improves over existing results. Moreover, since CNNs have been widely used in deep RL applications and also retain state-of-the-an performance [48, 22], our consideration of CNNs is a further step of bridging practice and theory.
Table I: K1 and fig are measures of distribution shift with respect to their respective regularity spaces; Deff denotes the effective dimension of the function approximator from the curse of dimensionality; K3 is the absolute density ratio between the data distribution and target policy's s visitation distribution; x defined in (I) and is no larger than and often substantially smaller than K3. See in-depth discussions in Section 4.
[75], which usually suffers
Work
Regularity
Approximation
Estimation Error
[15]
Linear
None
δ H2 CDVKKD/E
Third-time differentiable
[75]
None
Ö H12 /K2Dott//
Feed-Forward ReLU Net
[51]
Besov
δ (HR-a//2442) K3 K3KK k3KK0//20+22)))
This work
Besov
CNN
Additional Related Work Besides FQE, there are other types of methods in the OPE literature. One popular type is using importance sampling to reweigh samples by the distribution shift ratio [56], but importance sampling suffers from large variance, which exponential in the length of the horizon in the worst case. To address this issue, some variants with reduced variance such as marginal importance sampling (MIS) [68] and doubly robust estimation [35, 61] have been devel- oped. For the tabular setting with complete data coverage, [72] show that MIS is an asymptotically efficient OPE estimator, which matches the Cramer- Rao lower bound in [35]. Moreover, a line of work [49, 50, 39, 74] focuses policy evaluation without function approximation using MIS and linear programming.
Notation For a scalar a > O, [a] denotes the ceiling function, which gives the smallest integer which is no less than a; [a] denotes the floor function, which gives the largest integer which is no larger than a. For any scalars a and b, a b denotes max(a, b) and a A b denotes ma, b). For a vector or matrix, I|-Il, denotes the number of nonzero entries and |1-1|,a denotes the maximum
.D) TT. S g |I denote the L norm of function f. We adopt the convention 0/0 = 0. denotes Tur Te
magnitude of entries. Given function ʃ RDD - RR and multi-index s [st.... ..))"
Given distributions p and q. if absolutely continuous with respect to q, the Pearson x divieenee is defined as x²(p, q) == E, de 1)
2 PRELIMINARIES
2.1 TIME-INHOMGGENEUUS MARKOV DECISION PROCESS
We consider a finite-horizon time-inhomogeneous Markov Decision Process (MDP) (- [R, 1H H), where is the initial state distribution. At time step = 1. H. from a state s in the state space S, we may choose action a from the action space A and transition to random next state s' S according to the transition probability distribution s' (. s, a). Then, the system generates a random scalar reward r ~ (, a) with E [0. 1]. We denote the mean of Ra a) by as)
[Pr (H
3

---

Published as a conference paper at ICLR 2023
A policy {Th J specifies a set of H distributions TT(- for choosing actions at every state 8 E and time step h. Given a policy æ, the state-action value function, also known as the Q-finction, for h 1,2, .. is defined as
H Σ 1==h
(ī(,,a) = E
The(she
8h 8,0h
where on T- sw) and sw41 ~ Pa-(- sw', (x), Moreover, let 0h denote the state-action visitation distribution of step i... 9% (s, a) F [sh. s, ah a 81 E
For notational ease, denote X' = A. Let Pj R.t TR denote the conditional transition operator at step h:
= 8, a), vʃ X R,
where a' ~ T 8') and 8' ~ Pa(-18,a).
Denote the Bellman operator time under policy и Th: Th a( == (s a) + (s a), vf : X R.
The Bellman equation may be written Q Qu++1
2.2 RIEMANNIAN MANIFOLD
Let M be a d-dimensional Riemannian manifold isometrically embedded R.. A chart for M is a pair (U, Φ) such that U C M is open and ø U - Rd is homeomorphism, i.e., & is bijection, its inverse and itself are continuous. Two charts (U, ②) and (V, v) are called C* compatible if and only if
Φ : (UNV) and ΦoR (UNV) + (UNVV)
are both C* functions (k-th order continuously differentiable). A C atlas of M is collection of Ck compatible charts {UU, Φ:)} such that U, U2 M. An atlas of M contains an open cover of and mappings from each open cover to Rd.
Definition (Smooth manifold). manifold M smooth if has a C atlas.
We introduce the reach [19, 53] a manifold to characterize the curvature of M. Definition (Reach, Definition 2.1 (1)). The medial axis M is defined as T(M), which the closure of
T(M) = {x R
33x + 22 E M, such that || - æ1112 = ||0 - x2l12
inf ||x - - WEM
The reach w of M is the minimum distance between M and T(M),
inf || vl12.
=ET(M)
Roughly speaking, reach measures how fast manifold "bends". A manifold with a large reach "bends" relatively slowly. On the contrary, a small signifies more complicated local geometric structures, which are possibly hard to fully capture.
2.3 BESOV FUNCTIONS ON SMOOTH MANIFOLD
Through the concept of atlas, able define Besov space smooth manifold.
Definition 3 (Modulus of Smoothness [12]). Let Ω R., For function R Re in (P())
for > O, the r-th modulus of smoothness of is defined by
Wr Wr,p(f,t)
sup 1
| where
AT))(()= = Ej (-1-)) jhh) x 02 x rh Q otherwise.
4

---

Published as a conference paper at ICLR 2023
Definition 4 (Besov functions on .M). Let M be compact manifold of dimension d with finite
atlas 0.)). A function f M + R belongs to the Besov space p.g (MM, ,) on any chart U, it holds
| (, (U.) == ( +
11
18.. (UL)
< <0.
where
(1- 11)
dr) 1/9
if q xo,
B8g (,,()))) sup to u (I.
if co.
Further, the Besov norm of f is defined as | Bg. (M) Ei |1[ [/fl|lly. (U,)" We occasionally omit M
in the Besov norm when is clear from the context.
2.4 CONVOLUTIONAL NEURAL NETWORK
We consider one-sided stride-one convolutional neural networks (CNNs) with rectified linear unit (ReLU) activation function (RcLU(z) = max(2,0) Specifically, a CNN we consider consists of a padding layer, several convolutional blocks, and finally fully connected output layer.
Given an input vector x E R.P, the network first applies a padding operator P TR + DxC for some integer C 2 such that
Z P(z) ja Then the matrix is passed through M convolutional blocks. We will denote the input matrix to the m-th block as Zm and its output as Zm+1 (i.e., Z1 2).
0J E R
Let us define the convolution operation in Equation (2). Let W (Wy..}} E TgC'xxxc. be filter where C' is the output channel size, the filter size and C/ the input channel size. For Z IR DxC the convolution of W with Z, denoted with W x Z, results in Y E DDCC with
C
j-hh column
Wjas
D
W
D
W
1
C
C¹
Yk. ΣΣ Wj
Figure 2: Convolution of W * Z. WY is 1 x XC
i=1
matrix for the j-th output channel.
where we Zk+i-1,1 0 for ts +i- D.
In the m-th convolutional block, let Wm = ( ..... W(ll)) and B,, (B Bllmm) be collection filters and biases proper sizes. The m-th block maps input matrix Zm F DDxC to Zm+1 E R DxC by
Zm+1 ReLU (w((m)) * ..... ReLU (wi!) Zm + +B(
B(lmm)
with ReLU applied entrywise. For notational simplicity, denote this series of operations in the m-th block with single operator from DxC to TR xxx with Conv so (2) can be abbreviated
Zm+1 Conv Bm (Zm)-
Overall, denote the mapping from input to the output of the M-th convolutional block G(x) (ConVwa. o...o (Convw,.es P(z).
(3)
Given (3), CNN applies additional fully connected layer to G' and outputs f(z) W @ G(x) +b,
where W E DxC and b E are a weight matrix and a bias, respectively, and @ denotes sum of entrywise product, i.c. W @ G(x) Ex, Waz(G(z))es. Thus, we define class of CNNs of the same architecture as F(M, J,,,,,
{f f(z) = W Q(x) + with |[] V V S 72, G(zz in the form of (3) with M blocks.
The number of filters block is bounded by T,; filter size is bounded by 7; the number of
channels is bounded by J: max
| lloo $ Iloo S 7.}.
md
5

---

Published as a conference paper at ICLR 2023
Furthermore, FM, defined F(M, J,, T1, 72, V) F(M,L,, T2) M
S SV}.
(5)
Universal Approximation of Neural Networks There exists rich literature about using neural networks to approximate functions supported compact domain in Euclidean space, from early asymptotic results [34, 23, 10, 33] to later quantitative results [3, 46, 44, 30, 71J. These results suf- fer from the curse of dimensionality, in that to approximate function up to certain error, the network size grows exponentially in the data dimension. Recently, line of work advances the approxima- tion theory of neural network to functions supported on domains with intrinsic geometric structures [8, 57, 60, 58, 7, 42). They show that neural networks are adaptive to the intrinsic structures in data, suggesting that to approximate function up certain error, it suffices to choose the network size only depending on the intrinsic dimension, which often much smaller than the representation di- mension of the data. addition existing results, we prove a novel universal approximation theory of CNN en route to our RL result.
NEURAL FITTED Q-EVALUATION
We consider the off-policy evaluation (OPE) problem of finite-horizon time-inhomogeneous MDP. The transition model {Ph Mi=1 and reward function {R, J are unknown, and we are only given the access an unknown behavior policy xo to generate experience data from the MDP. Our objec- tive is to evaluate the value from a fixed initial distribution & over horizon H, given by
H
UR
E
ra(sn, an)
81 11~6
where on ~ x( 84) and 8141 ~ P- 8h, an).
At time-step h, generate data D,, {S an,k, kh,k )) Specifically, {sh,s) i..d. samples from some state distribution. For each Sh,k, generate 0b,k ~ Tp(. k) More generally, we may view {( <n,,) as i.i.d. samples from
the unknown behavior policy To to
a sampling distribution 2t For each ($),,, an,,). we can further generate $ ~ Pr(. kh,k: (.,k) and rh, ~ R,, (sh,k, (h,,k) independently for each k.
This assumption data generation is the time- iamm---homogeeouus analog of standard data assump- tion in time-homogeneous OPE, which assumes all data are i.i.d. samples from the same sampling distribution [51, 74, 50, 69]. Moreover, episodes generated by the behavior policy, as [41] introduce a subroutine whereby one can process an episodic dataset and treat as an -sampld dataset in any downstream algorithm.
dataset similar one that comprises K independent
To estimate v*, neural FQE estimates Q7, backward, recursive fashion. Q our estimate at step h, is taken as Ír (Qi+1) whose update rule is based on the Bellman equation:
K
the (0%+1) arg min JEJ
[(SN,K) - Th.k - S 1 a)ma sh) da
(6)
k=1
where Ír"" is an intermediate estimate of the Bellman operator Tr" Q 1 is an intermediate estimate of Qh and F denotes class of convolutional neural networks specified in (5) with proper hyperparameters. The pseudocode for our algorithm is presented in Algorithm 1.
MAIN RESULTS
In this section, we prove an upper bound on the estimation error nr by Algorithm 1. First, let us state assumptions on our MDP of interest.
Assumption (Low-dimensiona state-action space). The state-action space X' is a d-dimensional compact Riemannian manifold isometrically embedded in RD. There exists B > 0 such that ||æ|| < B for any E X. The reach of X is > 0.
Assumption characterizes the low-dimensional structures of the MDP represented in high dimen- sions. We say that the "intrinsic dimension" of X' is d < D. Such setting, as mentioned in Section 1, is common in practice, because the representation or feature people have access to are often ex- cessive compared to the latent structures of the problem. For instance, images of a dynamical system

---

Published as a conference paper at ICLR 2023
Algorithm 1 Neural Fitted Q-Evaluation (Neural-FQE)
Input: Initial distribution &, target policy x, horizon H. effective sample size K, function class F.
Init: Qi: := 0
for h H. H-- - 1,
do Sample Dn - ( an,,, sh (h,))
Update 07, + Trr (0h+1) by (6).
end for Output: 8-' == fxx Qi (8, ds da.
are widely believed to admit such low-dimensional latent structures [26, 32, 55]. People often take the visual display of a computer game as its state representations, which are in pixels, but computer only keeps small number of parameters internally represent the state of the game.
Assumption 2 (Bellman completeness). Under target policy π, for any time step h and any f E F, we have Th f (X), where 0 < p.q S oc and d/p S a cc. Moreover, there exists constant co > 0 that satisfies [T fll Bg., (X) S co for any time step h.
Bellman completeness assumption is about the closure of function class under the Bellman opera- tor. has been widely adopted RL literature [70, 14, 6, 69]. Some classic MDP settings implicitly possess this property, e.g., linear MDP [36]. Note that [66] show the necessity of such an assump- tion on the Bellman operator to regulate the Bellman residual: without such assumption, even in the simple setting of linear function approximation with realizability, solve OPE up constant error, the lower bound on sample complexity is exponential in horizon.
The Besov family contains large class of smooth funetions, and has been widely adopted in existing nonparametric statistics literature for various problems [24, 62, 63]. For MDP, Assumption 2 holds for most common smooth dynamics, as long certain regularity conditions satisfied. For instance, [51] show a simple yet sufficient condition, under which for any time step h and s' E S, the reward function rh (s, a.) and the transition kernel Ps (s'|s,, a) are functions in Bp, This further implies Q Qu, E Bp.,(()), In addition, Assumption 2 may be satisfied even when the transition kernel not smooth, examples of which are provided in [18].
smoothness
Note that while most existing work on function approximation assumes Bellman completeness with respect the function approximator, which our work is deep convolutional neural networks with ReLU activation, we are only concerned with the closure of the Besov class 1 (X') under the Bellman operator. This assumption is weaker than the previous work [75], which considers smooth function approximation (excluding ReLU networks).
Our main result is summarized in Theorem 2, which relies on using CNNs to accurately represent TV f for any ʃ F. The following theorem provides novel quantatitive analysis on how to properly choose CNN classes for approximating TT." f depending on the regularity of T
Theorem 1. Suppose Assumption I and 2 hold. For any positive integers I [2, DJ and M, J 0.
we let
L L= 0 (log(M 0 + D + log Dog D) = O(DJ), n - -M M 0(1),
log T2 O (log² MJ D Dlog M.) M = OM))
(7)
Then CNN class F(M, L, 1, TI, T2) (4) can approximate TV for any f E F(M, J, and h = 1,..., , H, ie., there exists f E F(M, L,, J, T,T1, with
Ilf - floc I (MJ)-
O()) hides constant deperding on d, a, ap-a p. 9, T fll (xy B, w and surface area of X.
24
The proof is provided in Appendix B. As can be seen, the rate of approximation free of the curse of ambient dimension D. We remark that Theorem I allows an arbitrary rescaling of M and J. as only their product is relevant to the approximation error. This is more flexible than conventional

---

Published as a conference paper at ICLR 2023
approximation theories [7, 54, 51], where the network width and depth have to maintain fixed ratio in terms of the desired approximation error. In Theorem we choose a configuration of M and J that leads to the optimal statistical rate via a variana tradeoff argument.
Theorem 2. Suppose Assumption I andd 2 hold. By choosing
L = Ollo K + D + log D), J = O(D), T1 0(1. log 72 = Ollog² K + D Dog K), M = O(K Tota) V with any integer I E [2, DJ in Algorithm I, in which (-)) hides factors depending on d, a, ap-d P. Co. B, w. and the surface area of X, we have
(9)
2d
- - S. CH zata log² K,
(10)
in which the expectation is taken over the data, and C is a constant depending on D t d, a, op-d P. 9. Co. B, w and the surface area of X. The distributional mismatch is captured by
Σ K
12 9h )
H
h=1
in which th and To are the visitation distributions of x and To at step h respectively and Q is the Minkowski sum between the CNN function class in (5) and the Besov function class, i.e. {I + g If E B (2) E F(M,L, J, T1, T2, V)).
We next compare our Theorem 2 with existing work:
(I) Tight characterization of distributional mismatch. The term к depicts the distributional mismatch between the target policy's visitation distribution and data coverage via restricted x² divergence. Note that the restricted x divdiverge is always no larger than the commonly-ure absolute density ratio [51, 6, 67] and can often be substantially smaller. This is because probability measures 0h and gh might differ a lot over some small regions in the sample space, while their integrations of smooth function in Q over the entire sample space could be close to each other. The absolute density ratio measures the former and restricted x² <--divergence measures the latter.
More strikingly, when considering function approximation (e.g. state-action space is not countably finite), the restricted x x=-divergence can still remain small even when absolute density ratio becomes unbounded. For example, we consider two isotropic multivariate Gaussian distributions with dif- ferent means. [52] has shown that Pearson x² -2-divergence which is always larger than or equal to restricted x2 diveeggeece, has a finite expression:
x2 (W(n, (W((,,)) (Hz, I)) = elll-~aall - 1,
whereas one may find the absolute density ratio unbounded: for any #1 # p2, dN(p), dW T)
x (μI (2)) || 1| + 1 |ل21| ao.
supexp
Such stark comparison can also be observed in other common distributions that have support with infinite cardinality, e.g. Poisson distribution.
Furthermore, when the state-action space exhibits small intrinsic dimensions, i.c., d < D. the re- stricted x divvieereence adapts to such oow-dimensional structure and characterizes the distributional mismatch with respect to Q, which is small function class depending on the intrinsic dimension. In contrast, the absolute density ratio in [51] does not take advantage of the www-dimensional structure.
In summary, though the absolute density ratio is a tight in the tabular setting and some other special classes of MDPs, in the general function approximation setting, it could easily become intractably vacuous, and restricted -dvvveegee is tighter characterization of distributional mismatch.
(II) Adaptation to intrinsic dimension. Note that our estimation error is dominated by the intrinsic dimension d, rather than the representation dimension D. Therefore, it is significantly smaller than the error of methods oblivious the problem's 's intrinsic dimension such [51].
Such a fast convergence owes to the adaptability of neural networks to the manifold structure in the state-action space. With properly chosen width and depth, the neural network automatically captures local geometries on the manifold through the empirical risk minimization in Algorithm for approximating Q-functions.
8

---

Published as a conference paper at ICLR 2023
Sample Complexity Comparison. Given pre-specified estimation enror of policy value c, algorithm requires a sample complexity of
D(H1+26/o -
We next compare our result with [51], which among existing work is the most similar to ours. Specifically, we reprove result with feed-forward ReLU network to be in the same setting as [51] (details in Theorem 3 of Appendix E).
When the experience data allowed to be reused, they show sample complexity of OHH2+2D/0 ng 2422/o (2222//))
As can be seen, our result is more efficient than theirs as long as H 1--D I <--l==a" Such requirement of the horizon can be satisfied in real applications, as d < D and is moderate. Note that even with no consideration for low-dimensional structures, i.e., d = D, our result is still more efficient, as is often substantially smaller than Kg. Moreover, when the experience data used just for one pass, our method is instantly more efficient, as their sample complexity becomes O(H++2D/0 D/ 22-///)) lig
5 EXPERIMENTS
We present numerical experiments for evaluating FQE with CNN function approximation the classic CartPole environment [4]. The CartPole problem has a 4-dimensional continuous intrinsic state space. We consider finite-horizon MDP with horizon H = 100 in this environment. In our experiments, we solve the OPE problem with FQE (Algorithm 1). We take the visual display of the environment states. These images serve original 4-dimensional continuous state space. In our algorithm, we use a deep CNN to approximate the Q-functions and solve the regression with SGD (see Appendix F.1 for details).
high-dimensional representation of CartPole's
Table 2: Value estimation 6R under high resolution and low resolution. The true ar 65.2 is
computed via Monte Carlo rollout.
Sample size
(A) No distribution shift High res
(B) Off off-policy
K
Low
High
Low res
5000
64.6 + 2.0
63.5 # 1.9
60.4 = 2.8
60.0 + 3.3
10000
66.0 + 1.3
66.5 + 1.7
67.0 + 1.8
68.0 E 2.3
20000
65.1 + 1.0 65.1 + 1.2
65.0 + 1.6 65.1 2.0
We consider two settings with different visual resolutions (see Appendix F.1 for details): one in high resolution (dimension 3 40 150) and the other in low resolution (dimension x 20 x 75). We use a policy trained for 200 iterations with REINFORCE as the target policy. We conduct this experiment in two cases: (A) data are generated from the target policy itself; (B) data are generated from a mixture policy of 0.8 target policy and 0.2 uniform distribution. (A) aims to verify the performance's 's dependence on data intrinsic dimension without the influence from distribution shift.
We observe that the performance of FQE on high-resolution and low-resolution data is similar, in both the off- off-policy case and the easier case with no distribution shift. shows that the estimation error of FQE takes little influence from the representation dimension of the data but rather from the intrinsic structure of the environment, which is the same regardless of resolution. We also observe that the estimation becomes increasingly accurate as sample size K increases. These empirical results confirm our upper bound in Theorem 2, which only dominated by data intrinsic dimension.
6 CONCLUSION
This paper studies nonparametric off-policy evaluation in MDPs. We use CNNs to approximate Q- functions. Our theory proves that when state-action space exhibits low-dimensional structures, the finite-sample estimation error of FQE converges depending on the intrinsic dimension. In the esti- mation error, the distribution mismatch between the data distribution and target policy's visitation distribution is quantified by restricted x² -ddvveeree term, which is oftentimes much smaller than the absolute density ratio. Our theory also reassures practitioners of the benignity of overrepresen- tation in deep RL and provides insights into how to choose network hyperparameters properly in presence of low intrinsic dimension. We support theory with experiments. For future directions, would be of interest to adapt this low-dimensional analysis to time-home hom-hhoogeneous MDPs. It is nontrivial to preserve the error rate with sample reuse in the presence of temporal dependency.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
Mengdi Wang acknowledges the support by NSF grants DMS-1953686, IIS-2107304, CMMI- 1653435, ONR grant 1006977, and C3.AL Tuo Zhao acknowledges the support by DMS-2012652.
REFERENCES
[I] Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman. Estimating the reach of a manifold. Electronic journal of statistics, 13(1):1359- 1399, 2019.
[2] William K Allard, Guangliang Chen, and Mauro Maggioni. Multi-scale geometric methods
for data sets ii: Geometric multi-resolution analysis. Applied and computational harmonic analysis, 32(3):435-46) 462, 2012.
[3] Andrew Barron. Universal approximation bounds for superpositions a sigmoidal function. IEEE Transactions Information theory, 39(3):930-945, 1993.
[4] Andrew G. Barto, Richard S. Sutton, and Charles W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(5)))) 846, 1983. doi:
[5] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprini arXiv: 1606.01500 2016.
[6] Jinglin Chen and Nan Jiang. Information-theerrtiee considerations in batch reinforcement learn- ing. In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
[7] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao Nonparametric regression diw-dimeniional manifolds using deep relu networks Function approximation and statistical recovery, 2021.
[8] Charles K Chui and Hrushikesh Narhar Mhaskar. Deep nets for local manifold learning. arXiv preprint arXiv: 1607.07 10, 2016.
[9] J. H. Conway, N. J. A. Sloane, and E. Bannai. Opringer-Verlag, Berlin, Heidelberg, 1987. ISBN 038796617X.
Lattices, and Groups.
[10] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
[11] Abhishek Das, Satwik Kottur, José MF Moura, Stefan Lee, and Dhruv Batra. Learning co- operative visual dialog agents with deep reinforcement learning. In Proceedings of the IEEE international conference computer vision, pp. 2951-2960. 2017.
[12] Ronald A Vore and George G Lorentz. Constructive Approximation, volume 303. Springer Science & Business Media, 1993.
[13] Ronald A. DeVore and Vasil Atanasov Popov. Interpolation of besov-spaces. Transactions of the American Mathematical Society, 305:397-414, 1988.
[14] Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is a good representation suf- ficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020. URL attps: opwprevieeeeeeeee//e/pp... /
net formm?ormmmmm weeeeddddrggneeee
[15] Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th In- ternational Conference on Machine Learning, volume 119 of Proceedings of Machine Learn- ing Research, pp. 2701-2709. PMLR, 13-18 Jul 2020. URL http:// /proceedings. 9/ duan20b. html.
wwwpppressvvv.. mwr.press/wee mlr.
[16] Yaqi Duan, Mengdi Wang, and Martin Wainwright. Optimal policy evaluation using kernel- based temporal difference methods. arXiv preprint arXiv:2109, 1200002, 2021.
[17] Dinh Dung. Optimal adaptive sampling recovery. Advances in Computational Mathematics, 34:1-41, 2011.
[18] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pp. 489. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2023
[19] Herbert Federer. Curvature measures. Transactions of the American Mathematical Sociery, 93
(3):418-49) 1959.
[20]
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arX1v:2004.07219, 2020.
[21] Justin Fu, Mohammad Norouzi, Ofir Nachum, George Tucker, Ziyu Wang. Alexander Novikov, Mengjiao Yang. Michael R Zhang, Yutian Chen, Aviral Kumar, et al. Benchmarks for deep off-policy evaluation. arXiv preprint arXiv:2/03. /6596, 2021.
[22] Scott Fujimoto. David Meger, and Doina Precup. A deep reinforcement learning approach to marginalized importance sampling with the successor representation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 351 1--3229, PMLR, 18-24 Jul 2021. URL https: /ptp//eeeoccccsppeeeeeeeeoescsse mll press v139 fu j jimt a html.
[23] Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural net- works. Neural networks, 2(3):183-192, 1989.
[24] Daryl Geller and Isaac Z Pesenson. Band-limited localized parseval frames and Besov spaces on compact homogeneous manifolds. Journal of Geometric Analysis, 21(2):33--371, 2011.
[25] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Geoffrey Gordon, David Dunson, and Miroslav Dudík (eds.). Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 315-323, Fort Lauderdale, FL, USA, 11-13 Apr 2011.
PMLR.
[26] Sixue Gong, Vishnu Naresh Boddeti, and Anil K Jain. On the intrinsic dimensionality of image representations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3987-3996, 2019.
[27] lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cam- bridge, MA, USA, 2016. http: www.
org.
[28] Omer Gottesman, Joseph Futoma, Yao Liu, Sonali Parbhoo, Leo Celi, Emma Brunskill, and Finale Doshi Velez. Interpretable off-po evaluation in reinforcement learning by highlight- ing influential transitions. In International Conference on Machine Learning, pp. 3658-3667. PMLR, 2020.
[29] David Ha. Reinforcement learning for improving agent design. Artificial life, 2554)335.-365, 2019.
[30] Boris Hanin. Universal function approximation by deep neural nets with bounded width and relu activations. arXiv preprint arXiv: 1oo:::708.000 02691, 2017.
[31] Botao Hao, Xiang Ji, Yaqi Duan, Hao Lu, Csaba Szepesvari, and Mengdi Wang. Bootstrap- ping fitted q-evaluation for off-policy inference. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pp. 4074-4084, PMLR, 18-24 Jul 2021. URL
https: /twpeee..eeecc/oeeeo ings mlr prwps//esssse.. v1 39 hwwhaalbbbb..... html.
[32] Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504 507, 2006.
[33] Kurt Homik. Approximation capabilities of multilayer feedforward networks. Neural net- works, 4(2):251 2577, 1991.
[34] Bunpei Irie and Sei Miyake. Capabilities of three-layered perceptrons. JEEE 1988 Interna- tional Conference on Neural Networks, pp. 641-648 vol.1, 1988.
[35] Nan Jiang and Lihong Li. Doubly robust off- poofcy value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652-661. PMLR, 2016.
[36] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137- 2143. PMLR, 2020.
[37] Nathan Kallus and Masatoshi Uchara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. J. Mach. Learn. Res., 21(167):1-63, 2020.
11

---

Published as a conference paper at ICLR 2023
[38] Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch Reinforcement Learning, pp. 45-73. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. ISBN 978-3-642- 27645-3. doi: (01000/9788--66-277444-4 2. URL https::/acc.oog///////p
978-3-66 1-1-3---2222745-3-2
[39] Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning, pp. 6120-6130. PMLR, 2021.
[40] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint 2rXiv:2005.016: 2020.
[41] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint urXiv:2204.05222 2022.
[42] Hao Liu, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 6770-6780. PMLR, 18-24 Jul 2021. URL https:/ httpt:://ptcceeeeeeeeee //ppoceeeiingssseeeeeeeeeeees.ee mlr wwwpppesssvsi. 91llll..
html.
[43] Hao Liu, Minshuo Chen, Siawpeng Er, Wenjing Liao, Tong Zhang, and Tuo Zhao. Benefits of overparameterized convolutional residual networks: Function approximation under smooth- ness constraint. arXiv preprint arXiv:2206. 04566, 2022.
[44] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. In Advances in Neural Information Processing Systems, pp. 12319, 2017.
[45] H.N Mhaskar and Charles A Micchelli. Approximation by superposition of sigmoidal and ra- dial basis functions. Adv. Appl. Math., 13(3):300373, sep 1992. ISSN 0196-8858. doi: 10. (0160116--855((220000622 URL https: /ttp////....g.1111//010011111110 01t/--1966--111 8858 (92) 90016-P.
[46] Hrushikesh N Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Neural computation, 8(1):144 177, 1996.
[47] Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy eval- uation with linear function approximation. Advances neural information processing systems,
34, 2021.
[48] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 518(7540):529-333 2015.
[49] Ofir Nachum and Bo Dai. Reinforcement learning via fenchel-rockafellaa duality. arXiv preprint arXiv:2001. 00660, 2020.
[50] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 32, 2019.
[51] Thanh Nguyen- Tang, Sunil Gupta, Hung Tran-The, and Svetha Venkatesh. On sample complexity of offline reinforcement learning with deep reLU networks in besov spaces. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL https:
//openreview attee//orommi----ennnimeeeeee
[52] Frank Nielsen and Richard Nock. On the chi square and higher-order chi distances for approx- imating f-divergences. JEEE Signal Processing Letters, 10-13: 2013.
[53] Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submani- folds with high confidence from random samples. Discrete & Computational Geometry, 39 (1-3):419-44 441, 2008
[54] Kenta Oono and Taiji Suzuki. Approximation and non-parametric estimation of ResNet-type convolutional neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning. volume 97 of Pro- ceedings of Machine Learning Research, pp. 4922 4931. PMLR, 09-15 Jun 2019. URL https:/ / https://proceete htpp//oeeennggss ml press 97 oonol 9a html.
12

---

Published as a conference paper at ICLR 2023
[55] Stanley Osher, Zuoqiang Shi, and Wei Zhu. Low dimensional manifold model for image processing. SIAM Journal on Imaging Sciences, 10(4): 2017.
[56] Doina Precup. Richard S. Sutton, and Satinder P. Singh. Eligibility traces for off- aff-po policy evaluation. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML '00, pp. 759-766, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072.
[57] Uri Shaham, Alexander Cloninger, and Ronald R Coifman. Provable approximation properties for deep neural networks. Applied and Computational Harmonic Analysis, 44(3):537-557,
2018.
[58] Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation characterized by number of neurons. arXiv preprint arXiv: 190060049777 2019.
[59] James Supancic III and Deva Ramanan. Tracking as online decision-making: Learning a policy from streaming videos with reinforcement learning. Proceedings of the IEFE International Conference Computer Vision, pp. 322-331, 2017.
[60] Taiji Suzuki. Adaptivity of deep reI.U network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, 2019.
[61] Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforce- ment learning. In International Conference on Machine Learming, pp. 2139-2148. PMLR, 2016.
[62] Hans Triehel. Theory of Function Spaces. Modern Birkhäuser Classics. Birkhäuser Basel, 1983.
[63] Hans Triebel. Theory of function spaces II. Monographs in Mathematics. Birkhäuser Basel, 1992.
[64] Masatoshi Uchara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, pp. 9659-9668. PMLR, 2020.
[65] Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue. Empirical study of off off-policy policy evaluation for reinforcement learning. arXiv preprint /91 106654, 2019.
[66] Ruosong Wang, Dean Foster, and Sham M. Kakade. What are the statistical limits of offline RI. with linear function approximation? In International Conference on Learning Representations, 2021. URL https: http////ppeeeeeeeeeeeeeeeeeee/em net wttpeeeeeedddeeeeeeeeeeeeee 30eeiidddd0-voe2ee- 2aQLD.
[67] Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. Conference on Uncertainty in Artificial Intelligence, pp. 550-559. PMLR, 2020.
[68] Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for rein- forcement learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32, 2019.
[69] Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. Advances neural information pro- cessing systems, 34, 2021.
[70] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint wttp:iv:2011040000
2020.
[71] Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103-114, 2017.
[72] Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular rein- forcement learning. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Pro- ceedings of Machine Learning Research, pp. 3948-3958 PMLR, 26-28 Aug 2020. URL http:// http:://poccceieieeeeo m.lr. press/vi00 wyinnbb.... html.
[73] Ming Yin, Mengdi Wang, and Yu-Xiang Wang. Offline reinforcement learning with differen- tiable function approximation is provably efficient. arXiv preprint arXiv:2210.00751 2022.
13

---

Published as a conference paper at ICLR 2023
[74] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D Lee. Offline inforcement learning with realizabilitt and single-policy concentrability. arXiv preprint arXiv:2202.04634 2022.
[75] Ruiqi Zhang. Xuezhou Zhang, Chengzhuo Ni, and Mengdi Wang. Off-policy fitted q- evaluation with differentiable function approximators: Z-estimation and inference theory. arXiv preprint TrXiv:2202.04999 2022.
[76] Kaiyang Zhou, Yu Qiao, and Tao Xiang. Deep reinforcement learning for unsupervised video summarization with diversit-repesennatvenesss reward. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 32, 2018
14

---

Published as a conference paper at ICLR 2023
A PROOF OF THEOREM 2
In this section, we provide a proof for the upper bound on the estimation emor in Theorem 2. We can tackle the sequential dependencies by recursively conditioning on the previous-step estimation and the fact that the error in the previous steps accumulates linearly. The estimation error can be decomposed into a sum of statistical error and approximation error. A tradeoff exists about the network size: while larger network reduces the approximation error, it leads to higher variance in the statistical error. Consequently, we choose the network size and architecture appropriately to balance the two types of error, which in turn minimizes the final estimation emro.
Proof of Theorem 2. The goal is to bound
E 1 - v- = (( S R U oi - (s.
To get an expression for that, we first expand it recursively. To illustrate the recursive relation, examine the quantity at step h:
E
QR 2% (g
(gT (s.
Th QT -TT" (0%++) as)
E
E
TT Tr T (1h
ER 1/x T Th+T
Tr (Qī++) (g)
E
1h+ -h++1 (s, (g)))
Tw @h+1 - (Qi+1) (s, a) doy (8, Da+1.... Dn
E
E
(a)
1h+1 - @itz (8)
+
E
E
TT to (σī+1)) (s, " a)
x8( X + 1 D..,, ... ,DH
1/
Q @i+t (15
J (T. Qha1 - - (Di++)) d9 Da+1. DH V Vx2l 97) +
E
(4)
Q7+1 @h+1 (s, a) 1 + (3(HH)) 20 log" K / 22 9hh)) +
/ 0h @i+1 (g (8, + CHK In 0/2 K X ( 9 + +1,
where C denotes a (varying) constant depending on D d, a, op P. Co. B, w and the surface area of X.
In (a), note Ty ThQ2t E B (x) by Assumption and T (Qi+1) E F by our algorithm, so TF Qu+1 7/ (Qī+1) Q. Then we employ a change-of -hange-of-measure measure argument and obtain this inequality by invoking the following lemma.
Lemma 1. Given a function class Q that contains functions mapping from X' R and two proba- bility distributions yi and supported on X, for any y E Q
E Exng [g(x)] S
[Bol)_/BBnn//rr VEn-qale (x)) (o
+ x2(9)
15

---

Published as a conference paper at ICLR 2023
Proof of Lemma 1.
E Exng [g gx))11
Ex [z(x)] - Ex (x)
Per [x(
R 11 [xx)
Ex (g
sup
Bg {x)
SEQ
En (x)]((
xa (11, 92)),
where the last step is by the definition of x2 92)
Byg [f] su
B [
In (b), we use Jensen's 's inequality and the fact that square root is concave.
To obtain (c), we invoke Lemma 10, which provides upper bound on the error of nonparametric regression at each step of the FQE algorithm.
Specifically, we will invoke Lemma 10 when conditioning on Pa+1, DH. i... the data from time step to time step H. Note that after conditioning, Th" Q7, becomes measurable and deterministic with respect D4+1, DH. Also, Du+1. ,DH are independent from Dj, which we use in the regression at step h.
To justify use of this theorem, we need to cast our problem into regression problem described the theorem. Since ((s,, (b,x)]k=1 are i..d from 9% we can view them as the samples x; 's in the lemma. We can view Th Qh+1, which is measurable under our conditioning, as fo in the lemma. Furthermore, we let
Sb.A = Th,k + JA @h+ilbhh::)) a) sh,x)) da Th. TT7Qh+4 ( 0h,k).
In order to invoke Lemma 10 under the conditioning D4+1,". Dr, need verify whether three conditions are satisfied (conditioning on " ,DH):
1. Sample {(s,,,, [ are ii.d;
2. Sample {(S,, (n, KR and noise (Co, 1K are uncorrelated;
3. Noise {K independent, zero-mean, subgaussian random variables.
In our setting, ((S,, a are i.i.d. from th Due to the time-inhomogeneous setting, they are independent from ".. DHr so {( K are still i.id.. under our conditioning. Thus, Condition 1 clearly satisfied.
We may observe that under our conditioning, the transition from (8t,A, an.k) to s/y, is the only source of randomness in Sr,K, besides (Sh,)s ah,k) itself. The distribution of (sh,e, an, s),)) is actu- ally the product distribution between Pa ai,k) and 9; function of s/ generated from the transition distribution Pa(+Isan (,, (), is uncorrelated with (Sh, ap,a). Thus, (sp, ap,))* are uncorrelated with CA, 's under our conditioning, and Condition 2 is satisfied.
Condition 3 can also be easily verified. Under conditioning, the randomness in Çh.R only comes from (Sh,k> Kh k k), which are independent from (81,es an,k' Th, for any k' o k. so Ch. are independent from each other. As for the mean of Çr.k.
E Kn. DDtt..... ".tt
E Ph.k + / (5h da (N(, az,)) PT PTT an,)) DD411" DH
E Th,k - (n kn.k) Qitilshar a)T(a (a) s
Pallo..nc.. U Qi aa)((a 8s) da 8h,ks an Dr+1s DH Dr
16

---

Published as a conference paper at ICLR 2023
0 0 = 0.
On the other hand, |
< H almost surely. because it is a function in our CNN class F. Thus, Sh. is a bounded random variable with Sh.a [-2H, 2H] almost surely, so its variance is bounded by 4H²2 Its boundedness also implies it is a subgaussian random variable. Thus, Condition 3 is also satisfied.
Hence, Lemma 10 proves, for step our algorithm.
Qh+ - - (Qī+1) 2 (s, a) dg Du+1, D11
S CC 44H 204a log K,
where C' depends on Doaed d, a, ap-d P. 9, co. B, w and the surface area of X.
2d
Note that this upper bound holds for any Th+ or Da+1, Dr. The sole purpose of our condi- tioning is that could view Q and then apply Lemma 10. Therefore,
measurable deterministic function under the conditioning
Qh+ - (Ditz))² (s, a) (s Dn+1, .. DH
E
E
I C² (H² + A K log K.
Finally, we carry out the recursion from time step time step H, and the final result
E 1 8" S CHHK Bota log 5/2 K
x869% 9% +
H h=1
B PROOF OF THEOREM
For simplicity, let denote fo := Th. in the theorem statement. Note that fo E B Big(() More- over, let us define a class single-block CNNs the form of
f(x) = W Conv
as J: SCSNNN (1, [f f() in the form of (3) with L layers. The number of filters per block
is bounded by L; filter size is bounded by I; the number of channels
is bounded by Ja [ al V || 1bs ST, [ S m2)- md
(11)
We will refer to CNNs in this form as "single-block CNNs" and use them as building blocks of our final CNN approximation for the ground truth Besov function.
B. PROOF OVERVIEW THEOREM 1
Theorem serves as a building block for Theorem 2, which establishes the relation between network architecture and approximation error. For simplicity, denote co := [[follay., Theorem is proven in the following steps:
STEP 1: DECOMPOSE f AS SUM OF LOCALLY SUPPORTED FUNCTIONS OVER MANIFOLD
Since manifold X' is assumed compact (Assumption 1), we can cover it with a finite set of dimensional open Euclidean balls (B; where c; denotes the center of the i-th ball and is its radius. We choose B w/2, and define U; (c,) X. Note that each U2 is diffeomorphic
17

---

Published as a conference paper at ICLR 2023
to open subset of Rd (Lemma 5.4 in Niyogi al. [53]); moreover, {U:) forms open cover for X. There exists a carefully designed open cover with cardinality Cx S _a Ty), where A(X) denotes the surface area X and Ta denotes the thickness U3 ss ie., the average number of U,'s that contain given point X. Ta is Old log d) (Conway et al. [9]).
Moreover, for each UG, we can define a linear transformation
(x()) = V.V. (z c;) + b,
where IR is the scaling factor and bg R is the translation vector, both of which chosen to ensure o(U,) C [0, 1] and the columns Vi E Rxd form an orthonormal basis for the tangent space To, (Z)). Overall, the atlas {(o;, U transforms each local neighborhood on the manifold
d-dimensional cube.
Thus, we can decompose fo using this atlas as
fo
f:
with fi fP:.
(12)
because there exists such a O partition of unity {0:)/< al. [42]). Since each fi is only supported on U, we can further write
Cx with supp(Ø:) C U; (Proposition 1 in Liu
Cx fo Σ (fi o o lu with fi = fpr.
(13)
where Lu; is the indicator for membership in Us-
Lastly, we extend Si o,² to entire [0, 1j with 0, which is a function in 8% B% ((0, 1] with Br. ((O, 1 Besov norm at most Cco (Lemma in Liu et al. [42]), where C is constant de- pending on a, p. g and d. This extended function is to be approximated with cardinal B-splines in the next step.
STEP 2: APPROXIMATE EACH LOCAL FUNCTION WITH CARDINAL B-SPLINES
With most things connected with the intrinsic dimension d in the last step, we proceed approxi- mation of fo on the low-dimensional manifold. With a 2 d/p+t assumed Assumption 2, we can invoke a classic result of using cardinal B-splines to approximate Besov functions (Lemma 5), by setting r = +oo and m [a] + in the lemma. It states that there exists a weighted sum of cardinal B- B-splines f, in the form
f=> Fu
fooo with Fa,
(0) ckj
(14)
such that
- f. f
Pm S CC.N-aja
(15)
In (14), Ckj E is coefficient and J... [0, 1jd - TR denotes a cardinal B-spline with index k.m N Rdd, & is scaling factor, j is shifting vector, is the degree of the B-spline.
By (13) and (14), we now have a sum of cardinal B-splines
Cx
Cx N o x Lu,
M
ΣΣ i=1
o x l0,
(16)
which can approximate our target Besov function fo with error
7 sallz- ~ 5 SCCxo,N-a/4
(17)
18

---

Published as a conference paper at ICLR 2023
STEP 3: APPROXIMATE EACH CARDINAL B- S-LLIE WITH COMPOSITION CNNS
Each summand in (16) is a composition of functions, each of which we can implement with a CNN. Specifically, we do with special class of CNNs defined in (11), which we refer "single- block CNNs
The multiplication operation can be approximated by single-block CNN X with most error in the _ sense (Proposition 1). x needs O(log +) layers and 6 channels. All weight parameters are bounded by (cā V 1).
We consider each Je o Φ; together, which we can approximate with a sum of N CNNs JSCNN, 3 up to error, namely,
Σ
SCNN - Jt oi hi
S.
In particular, we can use single-block CNN Jij error. Moreover, since d; is linear, it be expressed with single-layer perceptron T.. The architecture and size of fijj
FSONN approximate the B-spline fig up to 8/N
ISONN and di are characterized in Proposition 2 as functions of 5.
1u, is an indicator for membership in U, we need 11 (x) = 1 if d(x) = | - < 8 and Lu; (x) = 0 otherwise. By this definition, we can write 1y; as a composition of a univariate indicator 1 [0,82] and the distance function df:
Lu, (a)) 1 (o.33) o (x)) for x E X.
(18)
Given 0 E 10 and 2 8DB*0, turns out that [0, and dł can approximated with two single-block CNNs L and d: respectively (Proposition 3) such that
2 - de 1
S $4B²DO
(19)
and
1. Ul)) 8 A
is o d((x)=
0, &
(20)
some value between 0 and 1, otherwise.
The architecture and size of I and d are characterized in Proposition 3 as functions of 9 and A.
The above three approximations rely the classic result of using CNN to approximate cardinal B-splines (Lemma 10 in Liu et al. [42]; Lemma in Suzuki [60]). Putting the above together, we can develop composition of single-bil block CNNs
Ja. = (JRONN 0i, TA oz
(21)
as an approximation for Jag o Φi x Lu. The overall approximation error of fú, can be written of the three types of approximation error above. Details provided in Appendix B.2. Moreover, by Lemma 6, there exists single-block CNN Fu,J that can express fr.z-
STEP EXPRESS THE SUM OF CNN COMPOSITIONS WITH A CNN
Finally, assemble everything into f
Cx
N
Fi.s
(22)
i=1==1
which serves as approximation for fo. By choosing the appropriate network size in Lemma 2, which the tradeoff between the approximation error of Si, and size, we can ensure that
[ So S aa/d
(23)
19

---

Published as a conference paper at ICLR 2023
By Lemma 7, for M. > O, we can write this sum of N Cx dingle-blck. CNNS single-block CNNs with the same architecture, whose channel number upper bound J depends on J. This allows Theorem to be more flexible with network architecture. By Lemma 4, this sum of M CNNs can be further expressed as one CNN in the CNN class (5). Finally, N will be chosen appropriately as a function of network architecture parameters, and the approximation theory of CNN is proven.
of M
When Theorem is applied in our problem setting, we will take the target function fo above to be Th, Qh+1 at each time step h, which is the ground truth of the regression at each step of Algorithm 1. For more details about this, please refer to the proof of Theorem 2 in Appendix A.
B.2 PROOF OF THEOREM
In the following, we provide the proof details for Theorem 1, which quantifies the tradeoff between a CNN in the class 11 and its approximation error for Besov functions on a low-dimensional manifold. We start from the decomposition of the approximation error of f. which is based on the decomposition the approximation error of Ju. in (21), and will proceed to the end of this proof.
Lemma 2. Let be the approximation error of the multiplication operator (-.-)) as defined in Step of Appendix B.I I and Proposition 1, be defined as Step 3 of Appendix B. and Proposition 2, A and 6 be defined as in Step 3 of Appendix B. I and Proposition 3. Assume N is chosen according
to Proposition 2. For any = 1,... Ox. we have | foll 1,00
<EM((A (Ai, + Ai2 + Aiz) with
N
A.1 =
Σ
2SCNN o 3. 1s ood 2.
2SONN Jig
o oe x (is o 2
SC"8 408-d/an.
1
==1
66)) x (Îs ot) (is o di) Pis
A,2
Σ
PSCNN
5
1.00
c(T + 1)
A,3 11 (1 d3) - Six x 11 11=00 <
A
3(1 3/ww)
for some constant C depending on d, a. p. and some constant c. Furthermore, for any & E (0, 1), setting
N-a/d
1 N-1-a/d
8(1- N(133/w)Naafe
8 8= 3Cx 7 C" (3Cx)a/a
(24)
30(s + 1)Cx
16B2D
gives rise
| | -
The choice in (24) satisfies the condition A 8B2 in Proposition
Proof of Lemma 2. As in Proposition 1, Ar,1 measures the error from X:
N
A, = Σ & (
SSCNN o S, is o d;) - fi..
2SCNN o x (1s o a 1.0
S S C"8-dlan.
1=1
for some constant C" depending on d, a.q. The last inequality is due to the choice of N in Proposition 2.
A measures the error from CNN approximation of Besov functions. As in Proposition 2, A, S 6. A,s measures the error from CNN approximation of the chart determination function. The bound of Ai,3 be derived using the proof of Lemma 4.5 in Chen et al. [7], since f; o; is Lipschitz function and its domain is in [0, 1dd
In order to attain the error desired in Lemma 2, we need each network in Je, with appropriate size. The network size of the components in Jij can be analyzed follows:
20

---

Published as a conference paper at ICLR 2023
Iy The chart determination network 1, d; a is the composition of d; and a By Proposition 3, di is a single-block CNN with Ollog 8) O log N D log D) layers and width 6D; I is single-block CNN with (1log(52AA)) = O log N) layers and width In both subnetworks, all parameters are of O(1). By Lemma 6, the chart determination network 11, is a single-block CNN with O log N + + log D) layers, width 6D 2 and all weight parameters are of ((1).
x: By Proposition the multiplication network is single-block CNN with Ollog +) ( + 2) log N) layers and (1) width. All weight parameters are bounded by (c3 V 1).
ōy: The projection Φ; is a linear one, so it can be expressed with a single-layer perceptron. By Lemma 8 in Liu et al. [42], this single-layer perceptron be expressed with single- block CNN with 2 + D layers and width d. All parameters are of O(1).
[aj iSCNN; by Proposition 2, each JSONN is single-block CNN with O !))
( log N) layers and [24d(a + 1)(a 3) Sd] channels. All weight parameters (log (log))aap-aa (aaaattdddd
in the order of O (8-01g
0 (No( (ap"a
Next, we want to show fi.. a composition of the aforementioned single-block CNNs, can be simply expressed as single-block CNN.
By Lemma 6, there exists a single-block CNN 9iu with Olog N + D) layers and [24d(a + (a + 3) + 9d] width realizing JEONN Φt. All weight parameters in Ji,j are in the order of O (Iv( (12 Moreover, recall that the chart determination network 1, is a single- block CNN with (log N D + log D) layers and width 6D + 2, whose weight parameters of 0(1). By Lemma 14 in Liu et al. [42], one can construct a convolutional block, denoted by Øi.j- such that
(x) = (x))+ (11)(1))-
(L(x))) ((((z))-
(25)
Here F., has [24d(a + 1)(a 3) + 9d + 6D 2 channels.
Ki 1,
Since the input of is
by Lemma 15 Liu et [42], there exists CNN 9ú, which takes
(25) as the imput and outputs (9i,j, T,).
Note that Fi, only contains convolutional layers. The composition Ji.5 o Gs.j. denoted by Dig CNN and for any X, K.N.NN (I) ft,(z)) We have
SCNN is
2., @SCNN E JSCNN (L, I,T,T) with
L O (log N D + log D) [48d(aa 1)(a + 3) 18d 12D + O(1,
T O (N(OOR2) o (1 +ord 1))
(26)
and can be any integer in [2, DJ. Therefore, we have shown that Øi.j @SCNN is single-block CNN that expresses fi.j. as we desired.
Furthermore, recall that f can be written as a sum of Cx such SCNNs. By Lemma 7, for any M, satisfying MJ = O(N), there exists CNN architecture JSONN (I, (,T,) that gives rise to set of single-block CNNs (7: JZ E JSSNN/ (L, J, I, T,,,)) with
M
9.
(27)
i=1
and
L 0= N + +D++ + log D) J= O (1
(28)
By Lemma below, we slightly adjust the CNN architecture by re-balancing the weight parameter boundary of the convolutional blocks and that of the final fully connected layer. In particular,
21

---

Published as a conference paper at ICLR 2023
rescale all parameters in convolutional layers of Jr to be larger than 1. While this procedure does not change the approximation power of the CNN, can make the CNN have a smaller covering smaller variance.
number, which is conducive
Lemma 3 (Lemma 16 in Liu et al. [42]). Let 2 1. For any 9 E FSENN (L,,,,, T2), there exists ʃ E JSSNN (I, J, 1, lr,
",,,,,,,,,777 T" such that g(x) = [(x).
In this case, we y d' N V 2) a of told (SID)M E, where c' is a constant such that 7 S aa e' (1ogg) : ap-- toyd" With this 7, we have ft E JSSNN L, T2) with
L = Ollg + D + log D), J = OD)) TI = (8ID) M - = 0(1)
log 72 = (log M + log 2 N + D Dog N)
Finally, we prove that it suffices to use one CNN to realize the sum of single-block CNNs in (27). Lemma 4. Let JSCNNN JL Tı, T2) be any CNN architecture from ID. to R. Assume the weight matrix in the fully connected layer of JSSNN (L,J, J, T1,T2) T2) has nonzero entries only in the first row. For any positive integer M, there exists a CNN architecture F(M, L, J, 71, 7,, for any (f( CJSONN(T, (T., J, I, T2), there exists E F I, 4,44 J, 22) VT))) with
such that
M
f(x) Σ fm)
Consequently, by Lemma there exists CNN that can express sum of M single-block CNNs with architecture F(M, L,, J, I, T1, 72) with
L = O N + D log D), = O(D),,, TI = (MID) 0(1),
log 72 = O (log M + logg + Doog N) MMM(M)
(29)
and J, M satisfying
MJ O(N),
(30)
which is requirement inherited from Lemma 7. This CNN is our final approximation for fo-
Applying this relation N (MM) (29) gives
|| - fo 1 I (MJ)-²
(31)
and the network size
L = O (log( (MJ) + D + log D) J O(DĪ), 7= (8ID) = 0(1),
log O (1og² MJ + D Doog MJ). M =
M O(M).
B.3 PROOF OF LEMMA
Denote the architecture of fmm with
Fm(xx) = Wm Convw...B.. (x);
where Wm, { [wl)
1=1" Bm = B
L S 1=1
Furthermore, denote the weight matrix and bias in
the fully connected layer of f with W, and the set of filters and biases the m-th block of f with Wm, and Bm, respectively. The padding layer P in f pads the input æ from RDD to Dx4 with zeros. Each column denotes channel.
Let us first show that for each m, there exists some Conv W.., 8... Z E IR Dx4 with the form
D24 + Dx4 such that for any
Z = [(x)+
(z)
(32)
22

---

Published as a conference paper at ICLR 2023
where (x)+ means applying (- V 0) to every entry of z and (x)) means applying - 0) to every entry of z, so all entries in are non-negative We have
mu (fm())
(m)()) A 007
Conv Wi By, (2)
+ Z
(33)
where *'s denotes entries that do affect this result and may take any different value.
For any m, the first layer of fm takes input in RRP. Thus, the filters in w are in IRP. Again, we pad these filters with zeros to get filters in IR Px4 and construct W() such that
(WW)) 1,., = [1
0]
(WLL)) 2,: 0
0]
(W1(1) J... 0
0
61
0].
(WO() 44:::
)4..: 0
0
0
e1]:
(WIL) 444j
(mil)) )o::
(-W(l)
0
wil v. The first four output channels the end of this first layer is a copy of For the filters in later layers fm and all biases, we simply set
where we the fact that w (a)+ W
(Ir)
(Wil) 1, ) c1
0]
for = 2, L, for
(WL() 2,:,: 0
el
0]
(W1(() Ja..: 0
0
0
0]
for 1 = 2, 1 1
(Wi(() 4..,;
00
C1
0]
for / 2, ..... 1,
(Wi()) m 1+J.1.
0
0
0
0
(Wm
Jan
for / 2,.... 1,
(B JA: =
0
(Bm) )ann
for 1 1,
In ConV am additional convolutional layer is constructed to realize the fully connected layer in Im By our assumption, only the first row of Wm is nonzero. Furthermore, we set ((()) = 0 and WL as size-one filters with three output channels in the form of
(WLL)) a. 0 0
TI (W [:m).:].
72
(WLL)
0 0
(Wm)..
Under such choices, (33) is proved and all parameters in Wm, Bn, are bounded by By composing convolutional blocks, we have
DM (Fm V
-1 ΣM (F Franoo A0)
(ConwWnn.Bwl )...... ...... (Conv w. B,, p(x)= (x)+ (x)
Lastly, the fully connect layer can be set as
W
b b= 0.
Note that the weights in the fully connected layer are bounded by T2 V 1
The above construction gives
M
M
M Σ (m) (z).
f(x)
(Z) Σ
(m)
m=1
M=
23

---

Published as a conference paper at ICLR 2023
B.4 SUPPORTING LEMMAE FOR THEOREM
Before stating Lemma 5, we provide a brief definition of cardinal B-splines.
Definition (Cardinal B-spline). Let (xx) [(..) be the indicator function for membership in
[0, 1]. The cardinal B-spline of order in defined by laking m 1-fimes convolution of th:
4m (x) = (16
w (x)
m+1 times
where / [ ()g((dt.
Note that 2m is piecewise polynomial with degree m and support [0, m + 1]. It can be expressed as [45]
m+1
m + (m) m! E (mH )
For any k,j E N, let Ik..j.m (x) th (2 x j), which is the rescaled and shifted cardinal B- spline with resolution 2- and support 2 ijj + (m 1)]. For k = (kI...., .a....,,a), ka) E N and (i,,...;Ja) Nd, we define the d dimensional cardinal B-spline as Ikj.m (x) II vmm (2
je). When h1 ... kd k E N, denote F.j.m (I) II 1m x; j:).
B.4.1 APPROXIMATING BESOV FUNCTIONS WITH CARDINAL B-SPLINES
For any E N. let J(k) = {-m, -m 1, 1,...,," 2 1, and the quasi-norm norm of the coefficient {CK.) for & E N,j ((k) be
1/v
1/4
Σ KEN
24(a d/p)
Σ JEJ(K)
(34)
We state the following lemma, from Vore & Popov [13]. Dung [17], which provides upper bound on the error using cardinal B- B-splines to approximate functions in B ((0, 1]¹)
Lemma (Lemma oo and 0 < a < сo satisfying > d(1/p 1/r)+. Let m E NN be the order of the cardinal B-spline basis such that
Suzuki [60]; DeVore & Popov [13], Dung [17]). Assume that p.q.r
< min m, m 1+ 1/p). For any 15,, 1]d), there exists fN satisfying
Il fN ((0.1) CN-a/d fg ((01))))
for some constant with 1. f is in the form of
H
H Σ
[N(x) = Σ Σ
+
Ck...k j... (x).
(35)
J(ka)
k= k= 1=1
where fja]na C J(k), H = Ca log( /N) = [v- (og((N))
H+,, INN2 (k--))
for 1 H H,.,...,, H
d(1/p-1/r) and v/ (a (2u). The real numbers 61 > 0 and
> 0 are two absolute constants chosen to satisfy Σ (2* + =m) Ek=#41 ni S N, which
H²
are to N. Moreover, we can choose the coefficients {cuj} such that |KC,hHllo, < C₁ (1 ((..1())))
for some constant Cj.
B.4.2 APPROXIMATING CARDINAL B-SPLINES AND OTHERS WITH SINGLE-BLLOCK CNNs
The following Proposition quantifies the tradeoff between the size of a single-block CNN and its approximation error for the multiplication operator.
Proposition 1. Let x be defined as in (13). For any 1 E (0,1), there exists single-block CNN ((,-) such that
aa x b 8(a,b))l 100 S
24

---

Published as a conference paper at ICLR 2023
where a,b b are functions uniformly bounded by cu-
X is a single-block CNN appreximation of and is in FSCNN (L, J,I,T, with L= = (loo 1/1) + D layers, J 24 channels and any 2 1 S D. All parameters bounded by (c) v 1). Furthermore, the weight matrix in the fully connected layer of x has nonzero entries only in the first row.
Proof of Proposition 1. First, let us define particular class of feed-forward ReLU networks of the form
f(x)= = Wz- ReLU -e- +b) + bl-1) + bL.
(36)
as
J.T, = ff) in the form (36) with L layers and width at most J.
[ loo T, ||0:l S for 1...., , L..
(37)
By Proposition 3 in Yarotsky, there exists a feed-forward ReLU network that can approximate the multiplication operation between values with magnitude bounded by co. with v error. Such feed- forward network has Ollog 1/1) layers, whose width is all bounded by 6, and all its parameters are bounded by c.. Therefore. such a feed-forward network sufficient approximate with 17 error in 1.2-normm, because the arguments of x are uniformly bounded by Assumption 2.
Furthermore, by Lemma 8 in Liu et al. [42], we can express the aforementioned feed-forward net- work with a single-block CNN in JSSCNN (L,J, where L, J, 1, are as specified in the state- ment of the proposition.
Proposition 2 quantifies the tradeoff between the size of single-block CNN and its approximation error for the cardinal B-spline fi o $,
Proposition 2 (Proposition 3 in Liu et al. [42]). Let f:o be defined as in (13), For any 8 E (0, 1), set N = C C/5-d/o d/a For any < S D, there exists a set of single-block CNNs { [SSCN)] N
such
j=1
that
SSCNN Σ Jij
fo of
S 6,
where C1 is constant depending a,p, and d.
ZSONN a block CNN approximation of fr, (defined in (14)) in JSCNN J, J, T. with Ji.
L= = (log(1/))) J= [24d((x + 1)(a - 3) + 8d = (8-0lgg 2)(
ay _ي teld teid)))
The constant hidden in (-)) depends on d, a, ap-d P. co-
2d
Proposition 3 quantifies the tradeoff between the size of the sub-networks for the chart determination network and its approximation error for the chart determination indicators and the distance function d?
Proposition 3 (Lemma 9 Liu et al. [42]). Let d? and 10 be defined as in (18). For any 0 e (0, 1) and A 2 8B² D8, there exists a single-block CNN d approximating de such that
| df - DO,
and a CNN i approximating (0,99) with
Ta(x) = O. I, (* Da 1),
ifa S (1-2 4B2
if 2 32 2 D9,
otherwise.
for & E X. The single-block CNN for de has O(log(1/0) /0)) layers, 6D channels and all weights parameters bounded by 4B2. The single-blod block CNN for 11 has [log(32 (33/))) layers, 2 channels. All weight parameters are bounded by max(2, 122 4B2 DØ
25

---

Published as a conference paper at ICLR 2023
As result, for any X. i (x) gives approximation of Lu, satisfying
if U, and dz( - B² A;
a o d2(x)
0,
i & Us
between 0 and 1,
otherwise.
B.4.3 LEMMAE ABOUT SUMMATION AND COMPOSITION OF CNN
Lemma 6 states that the composition of two single-block CNNs can be expressed as single-block CNN with augmented architecture.
Lemma 6. Let FICNN( LL,, 11.11..1.T TI. be CNN architecture from RD + R and FRONN (L2, 12, T2, T2) be a CNN architecture from E - R. Assume the weight matrix in the fully connected layer of FSCNN (I1, J. TI,T,, and FŞCNN (In, J2. 12, T2, T2) has nonzero en- tries only the first row. Then there exists a CNN architecture JSCNN( (I, J,,J,I,,, from R. R with
L L L2, =
I=
such that for any fi FSSNNN (L1, J1, I1, T1) and f2 FSCNN J2, I2, T2, T2), there exists I E JSSSKK (L, J, I, T,)) such that ((x) = f2 fi fi(x). Furthermore, the weight matrix in the fully connected layer of JSONN (L, I, T,T) has nonzero entries only in the first row.
Lemma 7 states that the sum of no single-block CNNs with the same architecture can be expressed as the sum of ny single-block CNNs with modified width.
Lemma 7 (Lemma 7 in Liu et al. [43]). Let {fi) 2 be set of single-block CNNs with architecture FSSNNN (To, Jo. To: To, TO)- For any integers S S no and J satisfying nJ = (n) and J 2 Jo. there exists an architecture FSOONN (L, J. I,T,T) that gives set of single-block CNNs {9:)=1 such that
(:( = fi(x).
i=1
i=1
Such an architecture has
--
Furthermore, the fully connected layer of f has nonzero elements only in the first row
C PROOF OF CNN CLASS COVERING NUMBER
In this section, we prove bound on the covering number of the convolutional neural network class used in Algorithm 1.
Lemma 8. Given 5 > 0, the 5-covering number of the neural network class F(M, L, J, 71,72, V) satisfies
(2(n 1,.
( vr2)A10-1)
(38)
where
A (M + +3)DD(L
A2 = -L
with " PM p =1+
MLpt, , ppp With network architecture stated in Theorem 1, have
(J and pt = J1
F(M, M L, J. TI, T2, V) = O D (MJ) log 2
log (
where O(-) hides constant depending d, a, op-a- P. q, Co, B, and the surface of X.
26

---

Published as a conference paper at ICLR 2023
C.I SUPPORTING LEMMAE AND PROOFS
Proposition 4 below provides an upper bound on the -nom of a series of convolutional neural network blocks in terms of its architecture parameters. e.g. number of layers, number of channels, etc.
Let J be the number of channels i-th layer of the m-thh block, and let 1 be the filter size of i-th layer in the m-th block. [b.aa] is defined as
P (1) = (Convw, BB,))) w,B, ..... (Convw,BB.) (z).
Proposition 4. For m
2. .. .M and x E [-1, we have
m L;
m ) (1 (1+
(1)mll((=) (1Vm)
6 1) p0
L
Jk
k=1
Proof.
(1))l
Coov Bm (9 (1 (2)))] 00
Lm
Lm
J
1) (0) m T1 0 (1
+ Lm II
[1v
[1 100 m
n1)
m
1m1
m
m
L
Y12
< [P(())
j=li=1
1=++1:=1
m
172
$
|
n1
L
I
5=1==1
1+ IIv
m1
where the first two inequalities are obtained by applying Proposition 9 from Oono & Suzuki [54] recursively.
L
Lemma 9 quantifies the sensitivity of CNN with respect to small changes in its weight parameters. This will be used to create a discrete covering for the CNN class.
Lemma 9. For f.J' E F(M, L, J, 1, TI, T1, V) such that for E > O, ||W - W'l S e, [ 10o S ||w!!! W
I and ||S/ - -B%0 |l
I c for all m and i, where
(W.b, (EOWI) Blll Dam and (W', M (1(WI) _!lh )) } are the parameters of f and f' respectively, we have
|f - ff I A16,
where A1 is defined in Lemma 8.
Proof. For any E 11.
[sxx) - f'(x))
= -IW @ +b
= -IW =() W' @ (Q(x) ('(x))
-I(W ((2) W' @ (Q(z) Couv (x(())) + Conv By (Q(()) - ('(x))
M
W' @ Qm+LM (Convw...B.. Conv B,, 2 fu,mm-1) (W - w') -()))(0))-6 + Σ
27

---

Published as a conference paper at ICLR 2023
M
$ IW - W") 2 Q(;; 0) +
+ +
Σ
W
2 Q 1 (Conv - Conv BBn) o a Q/u.m-11
m=1
(0) S (3 + MJJD(IVT)((TTT))
M L,
M
Lx
1+ L
(IV T1)
k=
1=1
where (a) is obtained through the following reasoning.
The first term in (a) can be bounded as
(W w') ((x) b- 1'
< (ll || lloo I - 1l [1(()) + Ilb - 8' llo
< 2JDe [1)(2)) +e
1
LE (+
)
3.D m
k=1
i=1
where the first inequality uses Proposition 8 from Oono & Suzuki [54] and the last inequality is obtained by invoking Proposition 4.
For the second term in (a), it is true that for any m = 1, 1, .M, we have
W' & Q(++1,M (ConvW...e) Bm -onnww,, B...) Q/1m- Qmm+1.M o W.... - Conv B/) o Q Q/1.m-ull
W"
llo
T2
M
Ls
JD
II
II
1
[ConVWm.BB. Conv BB. Q P(um--
j=++1i= 1=
M
L
Q Pi.m-ull ))
JDm
(6-1) 197m
II
( (()) Ti
j jmm++ 1 1=1
M
Lin
JDT2
100
(( 160 m
TI
j=++i= 1=1
1=1
(1Vm)
m
((0 n
(1 1+
Σ
m
L
L
(Iv (( ((2))) m2)
j=1i=1
A=1
f=1
(1+
La
S JDD2
IIII
10
(1vn)
Σ
II
La
where (b) is by Proposition 7 from Oono & Suzuki [54]. (c) is by Proposition 2 and 4 from Oono &
Suzuki [54], (d) by Proposition and from Oono & Suzuki [54], and (c) obtained by invoking Proposition 4.
C.2 PROOF OF LEMMA 8
Proof of Lemma 8. We grid the range of each parameter into subsets with width A 8, so there are at most 2(TI V V7) A,81 different subsets for each parameter. In total, there are (2(71 V 12)AA1-1) A2 bins in the grid. For any f. L,M, J, 72, V) within the same grid, by Lemma 9, have || - fl < 8. We can construct the e-covering with cardinality (2(T) V 6 As by selecting one neural network from each bin in the grid.
Taking log and plugging in the network architecture parameters in Lemma 1, we have (8, L,, J. I mi 72, V). l1 O (A2 log ((T V 72) A1) 11)=1))
28

---

Published as a conference paper at ICLR 2023
00 MDD3J log(MM) log (M log
1
= MJ D log" (M log
where the inequality is due to A2 = O log(M By plugging in the choice of Tis P (1/2)* M I M- so p= -1 (1+ M 1) Se. Moreover, pt =I+ ML.
D STATISTICAL RESULT OF CNN-BESOV APPROXIMATION (LEMMA 10)
In this section, we derive the statistical estimation error for using CNN empirical MSE minimizer to estimate a Besov ground truth function over an i.i.d dataset. We need to choose the appropriate CNN architecture and size in order to balance the approximation error from Theorem I and variance. Thsi statistical estimation error can be decomposed into the error of using CNN to approximate Besov function (Theorem 1), terms that grow with the covering number of our CNN class, and the error of using the discrete covering to approximate our CNN class.
In Theorem 2, expand the estimation error गTH e over time steps and spper-bound the amount of estimation error in each time step with Lemma 10. Details of Theorem are in Appendix A.
Lemma 10. Let X be a d-dimensional compact Riemannian manifold that satisfies Assumption 1. We are given a function fo E (X)) where 8,P,q satisfies Assumption 2. We are also given samples Sn = {Ix; Ub) y1)); Di where 2; are i.idd sampled from a distribution Pa on and yi = fo(2;) + C.. Çi's are i.idd sub- Gauusiann random noise with variance o², uncorrelated with x; 's. we compute an estimator
Fn arg min
Σ (f(a;) - -,,)²
JEF n2
with the neural network class
= F(M, J,,, V) such that
L O(logn D log D); O(D), n 0(1), log 72 Ollgg + D log n),
M = ((zaai)) ), V = Il
(39)
with any integer I [2, and M, J 0 satisfying MJ On (nzot ) then have
E / (fa(a) fu(z)) f((z))
dPz(x) S c (V3 n zūía log" n,
(40)
x
where Vy [l and the expectation is taken over the training sample Sn, and is constant depending on 23 d, a, op 9, Cp, B, w and the surface area of X. O(+) hides constant 2d depending on d, a, op-d P. q. co, B, and the surface area of X.
2d
First, note that the nonparametric regression error can be decomposed into two terms:
J (Falo) - -o(lo)) 2 dD,(s)) = 2E
( - fo(x)))
+ 1 (o(o))))(0)) dDz(x))
M (f(();) - -
2E
n
where T, reflects the squared bias of using neural networks to approximate ground truth fo. which related to Theorem 1, and T2 the variance term.
D.1 SUPPORTING LEMMAE
Lemma 11 (Lemma 5 in Chen al. [7]). Fix the neural network class F(M, J,1, I, T1, 72, V). For any constant & E (0, 2V), we have
inf JeF(M.LJJ...... ( (f(x) - (o()))
Ti &
29

---

Published as a conference paper at ICLR 2023
L, F(M, L, J,1, T1, T2. VHH +2 +2
480
78
log FMM, L, TI, T2, V), + 8)08
(8V6)
72
where M,,. (1-1)))))) denotes the d-covering number of F(M, J,,, V2, with respect to the to norm, ie., there exists discretization of T1,
F(M, T,,
into F(M, L, T. V), 11-11-))))) distinct elements, such that for any f E E.F, there is f in the discretization satisfying || - S.
Lemma 12 (Lemma in Chen et al. [7]. For any constant ô E (0,2 72 satisfies
104V2 log/N (6/4V, L, J. 71 72, 1+1l))+++++ + (4+ 2V 8.
T2 S
3n
D.2 PROOF OF LEMMA 10
Proof of Lemma 10. Recall that
the
bias
and
variance
decomposition
of
E [x (Fulit) -J((z))) (P)
J (Fulco) - fco()) (P)
2 -o(s)))
E
=B E
21
+ E
(Fa(x) (o((o)) dPa(x))
E
2
(fn():) fo(z;))
n
Applying the upper bounds of Ti and T3 in Lemmas 11 and 12 respectively. we can derive
inf JeF(M.L,.ll..... J (Ta(o) - -o(o)) dP2(())) <4
/ (f(x) - (o())))Ppp)
N08 1, V), 10))
+ 48o
n
log N(8 1, TI, 72,
+
+ 8/G
104V2
+
16/4V M
3n
1
+
4
80 8.
2VF
We need there to exist network in F(M, L, J, II,, 72, V) which can yield function f satisfying |l follzo for e E (0, 1). will chosen later balance the bias-variance tradeoff. order to achieve such e-error, we set MJ -- -d/a so we now have our network architecture specified Theorem terms of e. Then, we can use the parameters in this architecture to invoke the upper bound of the covering number in Lemma 8:
(6,, J, T T2, 1-.1)- = (Az log ((T2 V T2) T2) A18
00
M log (M log
dd/a d/a D3 log log 1 8
where O(-) hides constant depending on log D, d, ap-d P. 9, B, w and the surface area of X.
2d
Plugging it in, we have
J (fm(x)) - Io(z))² aD2(s)) s 462
(fa())))o(z)))
48o²
dd log J +
30

---

Published as a conference paper at ICLR 2023
d/da DS log"
elog 1 o8
+ 8v 66d
104V?
+
c
-dja Dd log log 5
3n
+
4 +
80
2
V + o²
2
+
D log log
n
c dl D3 log clog 1
0²
+ +oo1
(41)
11
n
n - # which gives c 8 Substiuting both e and into (41), we deduce the desired estimation error bound
Finally we choose satisfy e²
- It suffices pick
E 1/x
(Tn((t)) So(1))
dD)
S c(VV a²) d²)n 2o+a log
where constant depends D zati d, a, ap-d P. 9, co, B, and the surface area of X.
Go
2d
E A RESULT FOR FEED-FORWARD RELU NEURAL NETWORK
E.
FEED-FORWAKE RELU NEURAL NETWORK
We consider multi-layer ReLU (Rectified Linear Unit) neural networks [25]. ReLU activation is popular in computer vision, natural language processing, etc. because the vanishing gradient issue less severe with it, which nonetheless common with its counterparts like sigmoid hyperbolic tangent activation [25, 27]. An L-layer ReLU neural network can be expressed as
f(x) = Wz ReLU 1-1 ... ReLU(W1 + b,) ... (b-
(42)
in which WT. W, and b,. by are weight matrices and vectors and ReI.U(-) is the entrywise max(0, The width of a neural network is defined as the number of neurons in its widest layer. For notational simplicity, we define a class of neural networks F(L,P, V) = { f(x) in the form (42) with L layers and width at most
rectified linear unit, i.c. ReLU((a)
L.
11 SV. Σ
Willo llb.llo S I, || ST, |1billoc S for = 1,. L).
(43)
E.2 POLICY EVALUATION ERROR AND ITS PROOF
From this point, we denote the function class F(L,p,1, I, V), whose parameters L, p, I, T, V are chosen according to Theorem 3, with the shorthand F. In this section, this F is used in Algorithm 1, instead of the CNN class (1I).
Theorem 3. Suppose Assumption and hold. By choosing
= O (log K), p = O zor4 ) O= न log K),
(44)
T max H1, vd,w²), -
in Algorithm 1, which 0(-) hides factors depending on a, d and log we have
E 1u"
.t < CH2R --vr VD/K) log K,
(45)
which the expectation is taken over the data, and C' is a constant depending on log D, o, B, d, w, the surface area of X' and co. The distributional mismatch captured by
Σ
V 122 ( 9h
+1,
in which Q is the Minkowski sum between the ReLU function class and the Besov function class, i.e. (ʃ + Bg (2),, E F).
31

---

Published as a conference paper at ICLR 2023
Proof of Theorem 3. The goal is to bound
/ (QT @QT
U oi - @ी (s. (s. (s) (s.
E
0
E
Q7) (s, daî (s,a)
SE
To get expression for that, first expand it recursively. To illustrate the recursive relation, examine the quantity at step h:
E
QR - 0% (s. dg (s. a)
X
Th 0h+1 - - (0%++1) (g)
E
+ +E 1/x Th Qh+1 - frr (0%+1) (s. dgğ (s.
Th QF Th Q7 Qh+1 dgt
E
0h+1 -Qh+1 (10))
E
Th" Qh+1 - - (D%+1) (s, dg)
+
E
E
(a)
@h+1 @7++ (8,a) d (8.
E
J TTr - To (Ditz)) (s, (s,, ( x2( + |
IE
Da+1. ...... ,DH
(8)
Qhan - @iril (5,0) du (4.
K
E
(Tr - - (Qitt)) (s, d0) (s (s,
EE
E
Da+1, ,D V X2 (2
(c)
Qh+1 @i+z dg)+) (((5112)
24 (K-
K
D
log K
X2 tho
/ x 0h - Ti+z (s) de (1, CH
D
K Katd +
log 3/2 8/2 K
x² (4 k
where C denotes (varying) constant depending log D, a, B, d. w, the surface area of X and co-
In (a), note T Qu+1 E BB (x) by Assumption and - (Qi+1) E
F by our algorithm, so T. Qh+1 Trr ( E Q. Then we obtain this inequality by invoking the following lemma.
In (b), we use Jensen's 's inequality and the fact that square root is concave.
To obtain (c), we invoke the following lemma, which provides an upper bound on the regression error.
Specifically, we will use Lemma 13 when conditioning on D Dr. i.c. the data from time step h + to time step H. Note that after conditioning, T3 Q7+1 becomes measurable and deter- ministic with respect to Da+1.' ... , ,D.. Also, D DH are independent from D), which we in the regression at step h.
To justify our use of Lemma 13, we need to cast our problem into a regression problem described in the lemma. Since {(L,,, K are i.i.d. from zh we can view them the samples a; 's in the lemma. We can view Th QT which is measurable under our conditioning, as fo in the lemma. Furthermore, we let
ÇA. = Th,k + / (s a) (a sh,x) da - Th Qh+ (Sh.k, ab,)).
In order to invoke Lemma 13 under the conditioning on Da+1. Drr we need to verify whether three conditions are satisfied (conditioning D "*. Dn))
32

---

Published as a conference paper at ICLR 2023
1. Sample {(sh,k, (k= are ii.d;
2. Sample {(s,,,, a (n) and noise (hh,kl k== are uncorrelated;
3. Noise [Sh,*)k=1 1K are independent, zero-mean, subgaussian random variables.
In our setting, {(H,,, (N, are ii.d. from 9h Due to the time-inhomogeneous setting, they are independent from D DH, so {(S,,k (n,))) are still i..d. under our conditioning. Thus, Condition 1 clearly satisfied.
We may observe that under our conditioning, the transition from (sh, ah,k) to s/1, is the only source of randomness in Çh,k., besides (Sh,k, (h.,k itself. The distribution of (sh.es ah, an, s/,)) is actu- ally the product distribution between (, (h,ak) and 1, function of 8/,,= k. generated from the transition distribution (r(-1sh,k: (), ) is uncorrelated with (Sh. a).,).. Thus, (Sh,kr ap,k) 's are uncorrelated with Çi. under our conditioning, and Condition 2 is satisfied.
Condition 3 can also be easily verified. Under conditioning, the randomness in Sh.k only comes from (St,,, K,,k, $ &),,),, which are independent from (8N,Ks an,k', "h.,,TT,kk for any o k, so Sh.k 's are independent from each other. As for the mean Çh,Rs
E 1h Dutt....... .DH
E &h / (hh sh da (n ah,kk PT QT (s ana)) Da+1. DH
E Thik ra an,c) (htil a) s)),)) da
-EggP.tthn..a..u Us @iri(s', a)t(a s') da ah an Dati.
DH Ditt,
DH
-0+0=
@
On the other hand,
H almost surely, because is function in our ReLU network class F. Thus, Sh, is bounded random variable with Sn,A [H 2H| almost surely, its variance is bounded by 2 2 Its boundedness also implies it is subgaussian random variable. Thus, Condition is also satisfied.
Hence, Lemma 13 proves, for step in our algorithm,
Qu - - (Di+1)) (s, dg, (s, Dat1. ... ,
I c(H2 +4H²)
K K-ruaa
20
log K.
K
Note that this upper bound holds for any T D4+1. DH. The sole purpose of our condi- tioning is that we could view @ as measurable or deterministic function under the conditioning and then apply Lemma 13. Therefore,
/
(wr - (Qhtz) (s, " -. DH
E
E
< c(H² + 4H2)
(K-
D R)
log" K.
Finally, we carry out the recursion from time step to time step H, and the final result
E Elu² ह7 5 CH2
K
+
+
D
log
3/2
1
X2 9h +1
H
33

---

Published as a conference paper at ICLR 2023
E.3 LEMMA 13 AND ITS PROOF
Lemma 13. Let X be a d-dimensional compact Riemannian manifold isometrically embedded in RD with reach w. There exists a constant B such that for any E X, [zz] B for all where Is
j 1=,...,, D. We are given a function So E p.q. (X) and samples Sn = {(r,, are i.i.d. sampled from a distribution Ps on X' and = =fo(xs) + +G. Ci's are i.i.d. sub-Gaussian random noise with variance d², uncorrelated with x; Ifwe compute an estimator
fn arg min
Σ (f(x.) -.)² i=1
IEF nE
with the neural network class F(L, p. I, TTVVV V)
such that
L= 0 (log n): :P O (n Ia+e ,T O
(nzate logn
T T= =axx VJ,, V wd, VVV =Va,
(46)
then we have
E J (o())) dP)())) S c (V² (V²+ +
D
2042
log n,
(47)
where Vy = [[ and the expectation taken over the training sample Sny and e is a constant depending log D, a, B. d, w. the surface area of X and co-
Proof of Lemma 13. Recall
that the bias and
variance
decomposition
of
Sx (Fu(x)) (((()))((())))))) d2) as
E 1/x (Fulss) - =6(x)) dPa(x)
2 (1x)) fo(x:))?
= E
fo(z)))
Ti
+ E
(fa(2)- (folo)) folz)) dPa(z)
E
2
(F fo(z))) fo(z:))²
71
T2
Applying the upper bounds of Ti and T2 in Lemmas 11 and 12 respectively, we can derive
E J (fulm)- - fo(()) dPx(2) S FEF(L.D.I
/ (o())))
inf
(LL V), +2
+ 480
n
16g V). 11.)) +2 58
+ 8 8/6
104V2
log
T,, V).
3n
8 8.
2V
We need there to exist a network in F(L, P1L,,,1 I,,, V) which can yield a function satisfying - folloo < for E (0, 1). will be chosen later to balance the bias- tradeoff. By Lemma 2 of Nguyen-Tang et al. [51], in order to achieve such e-error, we need
L= log 1 --= 0 2)
11-0 ( $ log è !
T max B. VF, Vd, V=
where 0(.) hides factors log D, a, d and the surface area of X, so we now have our network architecture as specified in Theorem in terms of e. Then, we can use the architecture parameters (13) to invoke the upper bound of the covering number Lemma of Chen et al. [7]:
2L 2LB + 2)7
Nog, V). 11.1 log
8
34

---

Published as a conference paper at ICLR 2023
1 c log" log 8¹
1
where c" is a constant depending on log B, w and log logn.
Plugging it in, have
E Uxx (fa(o))(o(t)) dD)
48o² < 4e²
d" dde log" log 1 +
n
cd/aa log" 3 1 log
+ 86"
08
n
104V3
1 log
8 dd/a log
3n
1
+
4 +
+ 80
2V
V2 + 0²
1 log log
0
log 3 log aō +
0²
+ 0d
(48)
n
Finally choose to satisfy e² = - which gives é 20-a, It suffices to pick ô Substituting both e and into (48), we deduce the desired estimation error bound
J.
2 UL (((o)) dDz & cVV2 +0²)
D
log n,
where constant depends on log D, a ap-d" P. q, co. B, w and the surface area of X.
2d
F SUPPLEMENT FOR EXPERIMENTS
F.1 DETAILS FOR EXPERIMENTS WITH CARTPOLE
We use the CartPole environment from OpenAl gym. We consider it as time-inhomogeneou finite-horizon MDP by setting a time limit of 100 steps. We turn the terminal states the original CartPole into absorbing states, if trajectory terminates before 100 steps. the agent would keep receiving zero reward in its terminal state until the end. The target policy is a policy trained for 200 iterations using REINFORCE, in which each iteration samples for 100 trajectories with truncation after 150 time steps. The target policy value v" is estimated to be 65.2117, which we obtain by Monte Carlo rollout from the initial state distribution.
For a given behavior policy, to obtain dataset DD, at time step h, we sample for K independent episodes under the behavior policy and only take the (s, (s,a, s', tuple from the h-th transition in each episode. This is an excessive way to guarantee the independence among these K samples; in practice we could directly sample from a sampling distribution. We sample for D), for each h 1,--.-..,100
We use the render function in OpenAl gym for the visual display of CartPole. We downsample images to the desired resolution via cubic interpolation. A high-resolution image (see Figure 3) is represented as
40 150 RGB array; low-resolution image (see Figure 4) is represented as 3 x 20 x 75 RGB array.
For the function approximator in FQE, we use a neural network that comprises 3 convolutional layers each with output channel size 16, 32 and 32 and final linear layer. These layers are interleaved with ReLU activation and batch norm layers for weight normalization. For high resolution input, we use kernel size 5 and stride 2; for low resolution input, we use kernel size 3 and stride 1. For experiments with high resolution, in each step of FQE, we solve the regression by training the network via stochastic gradient descent with batch size 256 for 20 epochs. In high-resolution experiments, use 0.01 learning rate; in low-rest oowressoutionn experiments, we use 0.001 learning rate. We compute the average and standard deviation of FQE's result over 5 random seeds.
35

---

Published as a conference paper at ICLR 2023
Figure 3: CartPole in high resolution.
Figure 4: CartPole in low resolution.
F.2 EXPERIMENTS WITH LUNARLANDER
In addition CartPole experiments, present numerical experiments for evaluating FQE with CNN function approximation on the LunarLander environment [5]. The LunarLander problem has 8-dimensional continuous intrinsic state space. We consider a unite-horizon MDP with horizon 100 in this environment. In our experiments, we solve the OPE problem with FQE (Algorithm 1). We take the visual display of the environment as states. These images serve as high-dimensional representation of LunarLander's 's original 8-dimensional continuous state space. In our algorithm, we use a deep CNN to approximate the Q-functions and solve the regression with SGD. The results are report in Table 3.
Table 3: Value estimation T- under high resolution and low resolution. The true 8a 55.982 is computed via Monte Carlo rollout.
Sample size
(A) No distribution shift
(B) Off- Off-OOolice policy
K
High res
Low res
High res
Low res
5000
55.9 + 3.8
5,.5
55.5 5.5
55.0 5.9
10000
55.1 + 2.7
55.7 2.9
55.8 + 4.0
55.4 + 3.9
20000
55.4 1.9
55.6
2.0
56.3
56.0 = 3.5
The experiment setup is almost the same our CartPole experiments. We conduct this experiment in two cases: (A) data are generated from the target policy itself; (B) data are generated from a mixture policy of 0.9 target policy and 0.1 uniform distribution. high-resolution image (see Figure 5) is represented as 3 x 40 x 70 RGB array; a low-resolution image (see Figure 6) is represented as a 3 x 20 x 35 RGB array.
Figure 5: Lunarl in high resolution.
Figure LunarLLnnder low resolution.
F.3 ERROR DECAY RATE IN CARTPOLE
We plot the relative error of FQE in CartPole experiments from Section 5. Figure 7 and 8 show that the estimation error follows an exponential decay. We also plot this relative error in log-log plots (Figure 9 and 10). We observe that the curves linear, which confirms the form of
36

---

Published as a conference paper at ICLR 2023
theoretical bound in Theorem 2. Moreover, can observe that the slope, which represents the decay rate of the estimation error, is generally the same between high-resolution and low-resolution experiments. This confirms our theory that the decay rate takes little influence from the ambient dimension.
High res
High res
0.30
Low res
0.30
Low res
0.25
0.25
Relative error
Relative error
0.20
0.20
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0.00
2500
7500
12500 17500
2500
7500
1250017500
K
K
Figure 7: On-policy CartPole.
Figure 8: Off-policy CartPole.
High res
High res
Low
Low res
Log relative error
10-1
Log relative error
10-1
10
10-2
10
6x 10)
104
101
1
1
6x 10
104
10
log
K
log K
Figure 9: On-policy CartPole (log-log plot).
Figure 10: Off-policy CartPole (log-log plot).
37


Reviews:
[{"review_id": "x5-mzBKlvjU", "reviewer": "Reviewer_sfri", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The manuscript studies the estimation error of fitted Q-evaluation with convolutional neural networks under the assumption of a low dimensional state-action space. \nThe main contribution is that the decay rate of the estimation error only depends on the dimension of the state-action space rather than the ambient dimension. \nThe result builds on an new approximation result for Besov functions on submanifold, which is established in the manuscript. \n", "summary_of_the_review": "The manuscript studies an important and timely problem within the theory of reinforcement learning. \nIt is well written and provides a result on the estimation error, which depends on the intrinsic dimension of the state-action space and offers an analogon to existing result in the context of supervised learning.\nOverall, I believe this manuscript provides a valuable contribution to the theoretical RL literature. My main critcism is summarized in the following points:\n\n* *Insights into the proof and tools:* The manuscript would be stronger if it provided more insight into the techniques and main steps in the proof of the main results. In particular, this would is more important in my view compared to the discussion of the $\\chi^2$ distance and absolute density ratio, which could be moved to the appendix without big sacrifices, as well as as the paragraph *Sample Complexity Comparison*, which does not offer too much insight compared to Table 1.\n* *Experiments:* The experiments show that estimated value function does only weakly depend on the ambient dimension. However, this does not imply anything about the estimation error nor its decay rate for increasing sample size, which is the content of Theorem 1. I think a much more suitable experiment to get experimental evidence for Theorem 1 would be one that evaluates the estimation error and compares the decay to the predicted power law decay $O(K^{-\\frac{\\alpha}{2\\alpha+d}})$. In its current form, I think the space used for the experimental section could be of better use to provide more insight to the proof. However, with experiments confirming the predicted power law decay and possibly its tightness, a presentation of them would be justified in the main body of the manuscript.\n* *Definition of Besov space:* Currently, the definition is not very clear to pass. More precisely, $U$ is not introduced in the definition of the Besov norm and it is unclear which atlas is to be taken in the definition of the global Besov norm since its value does depend on the atlas (it could even be infinite). Further, I am suprised to not see any charts appearing in the definition and thus I am wondering what the difference to the notion of the Besov norm induced by the ambient space.\n* *Relation to existing results:* The manuscript does give an extensive overview of results on Q-value function estimation. However, the relation to results using Besov functions defined and low dimensional structures in the context of supervised learning is not discussed sufficiently.\n* *Presentation of Theorem 1:* The choice $\\mathcal F$ as a family induced by a CNN is only implicit and should be made explicit. Further, I believe that Algorithm 1 should be in the main body since in its current form it is required to parse the main result.\n\n", "strength_and_weaknesses": "**Strengths:**\n* Sound rigorous analysis; proper application of adequate mathematical tools.\n\n**Weaknesses:**\n* Little insight into the main steps of the proof is given in the main body.\n* Experimens are weak: I do not believe that a theoretical paper necessarily requires experiments. However, if experiments are provided, they should be well designed and provide substantial insight to the theoretical results. The biggest shortcomings of the experiments is their implications: 1) \"performance [i.e., the fitted value function] of FQE on high-resolution data and low-resolution data is similar\" 2) \"estimation becomes increasingly accurate as sample size K increases\". Where these findings don't contradict the Theorem 1 they do not evaluate its main claim, which is a error decay rate, which is independent of the ambient dimension. I think the experiments would be much stronger if tested for this rate, i.e., for a given setup simply increase the number of samples $K$ and then plot the estimation error on a log log plot including the predicted power law decay of $O(K^{-\\frac{\\alpha}{2\\alpha+d}})$. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "nITOY0wflU5", "reviewer": "Reviewer_5uSb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of off-policy evaluation using deep convolutional neural network. The main contribution of this paper is a theoretical justification of the ability that a deep neural network captures low-rank structures in high-dimensional datasets in off-policy RL settings. Although preliminary results on off-policy evaluation problem has been obtained in Nguyen-Tang et al. (2021), this work is stronger without the data coverage assumption. Also, it leverages a restricted $\\chi^2$-divergence which is generally tighter than the density ratio. Finally, the sample complexity is measured in terms of the intrinsic dimension of the problem, that is significantly smaller than the data dimension.\n\nOverall, the proposed theoretical analysis on the convergence of deep fitted Q-evaluation for off-policy RL and CNN networks achieves superior regret bound result due to the ability to capture low-dimensional structure.\n", "summary_of_the_review": "Overall, the paper seems prospective, it provides a sharper sample complexity under a more general assumption. I will consider raising my score if the technical novelty of this paper, Theorem 2, and the experimental results can be better explained.", "strength_and_weaknesses": "\nThe main strength of this paper is that it provides the first regret bound result on off-policy evaluation with deep neural network approximation with practical assumptions. The authors provide a theorem that bounds the sample complexity in terms of the intrinsic dimension and the $\\chi^2$-divergence between the sampling policy and the target policy, where both the dimension and the divergence generally improves upon previous results.\n\nHowever, there are a several vagueness and weakness, listed as follows\n\n- The paper spends lots of effort in introducing the background (at least the CNN part is a little bit distracting, as the CNN structure does not seem to influence the complexity analysis?)\n- On the other hand, the authors does not provide much explanation about what leads to the theoretical success of capturing the intrinsic dimension of the dataset. Has similar tools been leveraged in the literature of supervised learning? \n- Similarly, what is the intuition behind the proof that removes the data coverage assumption?\n- The paper adopted the Besov spaces and the Besov closure property, and the sample complexity is dependent on the Besov parameter $\\alpha$. How does this $\\alpha$ affect the sample complexity and the scope of hypothesis class?\n- Theorem 2 appears abruptly. What is this theorem for? Is Theorem 2 basically a Lemma essential for proving Theorem 1? This part seems incomplete.\n- In the experimental section, the authors Illustrate their claim by showing that the performance under high resolution and low resolution are similar. However, that might be due to the simplicity of the CartPole problem, let along the fact that $3\\times 40\\times 150$ and $3 \\times 20 \\times 75$ are not significantly different. More empirical validations are needed to truly verify their claim.\n\nAlso, there are a few typos:\n- In the definition of Reach, the $inf$ has to be taken on $x \\in \\bar{\\mathcal{T}}$ instead of $\\mathcal{T}$?\n- In the convolutional network part, $\\mathcal{W}_{j, :, :}$ is not $D \\times C$ (Caption of Figure 2)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h-QsUSCLpn", "reviewer": "Reviewer_Mweq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the off-policy evaluation problem in MDPs using function approximations. To estimate the offline target policy, the fitted Q-evaluation method is used, and to approximate Q-functions, CNNs are used. Their theoretical results show that when state-action space has low-dimensional structures, the finite-sample estimation error of FQE converges, depending on (1) the intrinsic dimension without suffering from the curse of high dimensionality, and (2) a function class-restricted  $\\chi^2$ -divergence which measures the distribution shift between the experience data distribution and the target policy. They use an experiment on CartPole to evaluate their theory.\n", "summary_of_the_review": "The novelty and originality of this paper are low. I lean toward rejecting this paper. ", "strength_and_weaknesses": "Strengths:\n- The paper is well written.\n- The regret bound with provided theoretical analysis, and especially using a function class-restricted  $\\chi^2$ -divergence for insufficient data coverage are new.\n\nWeaknesses:\n- The results seem to be a combination of existing results: the sample complexity in Besov space of off-policy evaluation using deep neural networks from [1] and low-dimensional manifolds in deep networks from [2,3,4,5].\n\n [1]  Thanh Nguyen-Tang, Sunil Gupta, Hung Tran-The, and Svetha Venkatesh. Sample complexity of ofﬂine reinforcement learning with deep relu networks. arXiv preprint arXiv:2103.06671, 2021.\n [2]  Minshuo Chen, Haoming Jiang, Wenjing Liao, Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. NeurIPS 2019.\n [3] Minshuo Chen, Haoming Jiang, Wenjing Liao, Tuo Zhao. Nonparametric regression on low-dimensional manifolds using deep ReLU networks: Function approximation and statistical recovery.2022.\n [4] Hao Liu, Minshuo Chen, Tuo Zhao, Wenjing Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks. ICML 2021.\n [5] Minshuo Chen, Hao Liu, Wenjing Liao, Tuo Zhao. Doubly robust off-policy learning on low-dimensional manifolds by deep neural networks. 2020.\n- Recently, several results about the sample complexity of offline RL without using function approximations are published. \nThe authors are missing a discussion about these works. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_xybNFMC27", "reviewer": "Reviewer_cmJs", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nThis paper provides new sample complexity guarantees for convolutional neural networks applied to off-policy Q-learning of MDPs with low-dimensional manifold structure.\n\nThe work is novel in that it provides a new characterization of the sample-complexity in terms of the underlying manifold dimension rather than the the ambient dimension of the data and action space -- which can be extremely large for state spaces defined in terms of image and video data. The bound is also novel in that it is utilizes the \\chi^2 divergence between the logging policy and the target policy, rather than the maximum density ratio which can be unbounded for continuous action spaces.\n\nThe authors define their bound with respect to a restricted but flexible class of Besov functions which captures many of the essential aspects of modern convolutional neural networks.\n\nFinally, the paper concludes with a limited set of experiments on the CartPole environment which demonstrate that Q-functions fitted on images do learn with fewer examples than the ambient dimension of the data.\n", "summary_of_the_review": "This work provides novel and improved bounds that further our understanding of how and why deep Q-learning (with convnets) performs well in very high dimensional state spaces. As such it is of interest to theorists currently working at the intersection of deep learning and RL. I support adding this paper to the 2023 ICLR program.\n", "strength_and_weaknesses": "Strengths:\n- Novel and tighter sample complexity bound for off-policy deep Q-learning with convnets that is characterized in terms of the dimension of the underlying data manifold and the \\chi^2 divergence between on- and off-line policies.\n\nWeaknesses:\n- the class of convnet functions used in the does not include skip connections which are always used in modern CNN architectures like ResNets. Does incorporating skip connections change the analysis or complexity bounds?\n- the experimental results are suggestive but quite cursory. It would be interesting to test networks with different numbers of channels, layers and see if the empirical estimation errors actually increase and decrease in accordance with what is predicted by the new bounds.\n- the bounds agree with empirical findings that CNNs seem to have a sample complexity that is lower than the ambient image dimension. But it's not clear if the theory will yield advances in applications.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster