Optimistic Exploration with Learned Features Provably Solves Markov Decision Processes with Neural Dynamics
Authors: Sirui Zheng
Lingxiao Wang
Shuang Qiu
Zuyue Fu
Zhuoran Yang
Csaba Szepesvari
Zhaoran Wang
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement Learning
Neural Network
Representation Learning.

Abstract: Incorporated with the recent advances in deep learning, deep reinforcement learning (DRL) has achieved tremendous success in empirical study. However, analyzing DRL is still challenging due to the complexity of the neural network class. In this paper, we address such a challenge by analyzing the Markov decision process (MDP) with neural dynamics, which covers several existing models as special cases, including the kernelized nonlinear regulator (KNR) model and the linear MDP. We propose a novel algorithm that designs exploration incentives via learnable representations of the dynamics model by embedding the neural dynamics into a kernel space induced by the system noise. We further establish an upper bound on the sample complexity of the algorithm, which demonstrates the sample efficiency of the algorithm. We highlight that, unlike previous analyses of RL algorithms with function approximation, our bound on the sample complexity does not depend on the Eluder dimension of the neural network class, which is known to be exponentially large (Dong et al., 2021).

Published as a conference paper at ICLR 2023
OPTIMISTIC EXPLORATION WITH LEARNED FEATURES PROVABLY SOLVES MARKOV DECISION PROCESSES WITH NEURAL DYNAMICS
Sirui Zheng! Lingxiao Wang! Shuang Qiu²
Zuyue Fu!
Zhuoran Yang*
Csaba Szepesvári Zhaoran Wang!
ABSTRACT
Incorporated with the recent advances in deep learning, deep reinforcement learning (DRL) has achieved tremendous success in empirical study. However, analyzing DRL is still challenging due to the complexity of the neural network class. In this paper, we address such a challenge by analyzing the Markov decision process (MDP) with neural dynamics, which covers several existing models special cases, including the kernliizdd nonlinear regulator (KNR) model and the linear MDP. We propose a novel algorithm that designs exploration incentives via learn- able representations of the dynamics model by embedding the neural dynamics into a kernel space induced by the system noise. We further establish an upper bound on the sample complexity of the algorithm, which demonstrates the sample efficiency of the algorithm. We highlight that, unlike previous analyses of RI. algorithms with function approximation, our bound on the sample complexity does not depend on the Eluder dimension of the neural network class, which is known to be exponentially large (Dong et al., 2021).
Keywords: Reinforcement Learning, Neural Network, Representation Learning,
INTRODUCTION
Reinforcement learning (RL) aims accomplish sequential decision-makinn making in an uncertain en- vironment via iteratively interacting with the environment (see Sutton et al. (1998)). Equipped with modern function approximators such as deep neural networks, deep RI. algorithms achieve tremendous empirical successes (Mnih et al., 2015; Silver et al., 2017: Hafner et al., 2019).
Despite its empirical successes, the theoretical understanding of deep RL is relatively underdeveloped. There are several recent works (Abbasi- that analyze RL algorithms with neural network parameterization, including policy iteration (PI) (Lagoudakis & Parr, 2003), policy gradient (PG) (Williams, 1992) and deep Q-leariig (Mnih et al., 2013). However, those works depend on restrictive assumptions that either the agent has access to a simulator the MDPs have bounded concentrability coefficients, which in fact imply that the state space is already well-explored. Another line of research (Jiang et al., 2017: Jin et al., 2020; Cai et al., 2019; Du et al., 2021) further removes such assumptions by conducting provably efficient exploration in RL. Such a direction of research typically hinges on a low-rank MDP assumption. Thus, those works either assume that the MDP is linear in the known feature or propose computational-inetie iinftfati algorithms, limiting the ability to explore the environment with neural network parameterization To explore the environment with neural network parameterization, a recent line of work (Wang et al., 2020; Jin et al., 2021a) analyzes the use of general function approximators in RI., covering neural network parameterization as a special case. Such analyses typically depend on the Eluder dimension (Russo & Van Roy, 2013), which unfortunately network class (Dong et al., 2021) and thus makes the results statistically incfficient for neural network parameterization. Therefore, we raise the following question:
et al., 2019; Wang et al., 2019; Fan et al., 2020)
be exponentially large even for simple neural
Northwestern University University of Chicago Yale University "University of Alberta DDeepiind Corresponding authors: rui wirruizeeggeege zheng20250u nnt

---

Published as a conference paper at ICLR 2023
Can we design RL algorithms that can conduct provably efficient exploration in structured environments with neural network parameterization?
Specifically, Our goal is to develop computational-effiient algorithms whose sample efficiency does not depend on the Eluder dimension of neural networks for structured environments with neural network parameterization. Our key insight is that, when the transition dynamics is captured by an energy-based model, we leverage the spectral decomposition of the kernel such that the challenge of distribution shift is characterized by the effective dimension of the kernel. To illustrate this insight, we propose a new model called MDPs with neural dynamics, which allows neural network parameterization and captures various MDP models proposed in previous works, including the KNR model (Kakade et al., 2020) and the linear MDP model (Jin et al., 2020). We then propose an algorithm, namely, Exploration with Learnable Neural Features (ELNF), and show that ELNF is sample efficient. ELNF iteratively fits the transition dynamics and reward functions with neural networks. Upon fitting the models, ELNF conducts exploration based on upper confidence bounds (UCB) (Abbasi- Yadkori et al. (201 1)). which are obtained from the feature maps that correspond to the fitted model. We remark that the bonus in ELNF can be efficiently computed.
Contributions.
Our contribution is threefold. First, we identify class of models that incorporates NN feature representation, which captures nonlinearity in the transition dynamics beyond the KNR and linear MDP model. We also show that our proposed setting can generalize to models in previous works (Kakade et al. (2020), Ren et al. (2021)). Second, we propose a new algorithm, namely ELNF, which tackles our proposed MDPs with neural dynamics. Our algorithm is computationally efficient when we have an optimization oracle for the model estimation. Third, we analyze the sample complexity of ELMF and show that ELNF is sample efficient. key feature of ELNF that the sample complexity of ELNF depends only on the covering number of neural network classes and does not depend on the corresponding Eluder dimension. We highlight that our work is the first to cover arbitrary NN classes with bounded log-covering numbers. In contrast, previous research typically depends on the Eluder dimension (Russo & Van Roy, 2013) of the hy hypothesis class, which is exponentially large for simple neural network classes (Dong et al., 2021).
1.1 RELATED WORK
Our work is closely related to the line of research on provably efficient exploration in the function approximation setting (Jiang et al., 2017: Jin et al., 2020; Cai et al., 2019; Du et al.. 2021: Uchara et al., 2021; Zhang et al., 2022a). Such a line of research typically hinges on MDPs with low-rank structure. For instance, the study of linear MDPs (Jin et al., 2020; Cai al., 2019) requires that the transition dynamics are linear in the known feature map. In contrast, the feature maps are unknown in our setting and need to be estimated. The study of low-rank MDPs (Jiang et al., 2017; Du et al., 2021; Uehara et al., 2021; Ren et al., 2022) is more closely aligned to work in the sense that the feature map is unknown and needs to be estimated. Jiang et al. (2017) and Du et al. (2021) require optimistic planning over the confidence set of transition dynamics, which is computationally inefficient. Uehara et al. (2021) and Ren et al. (2022) propose an algorithm for low-rank MDP that is both computationally efficient and sample efficient. Nevertheless, they only consider finite hypothesis classes, and require sampling from the stationary distribution of the MDP.
Our work is also related to the study of provably efficient exploration with general function approxi- mation (Wang et al., 2020; Jin et al., 2021a). Nevertheless, previous results typically depend on the Eluder dimension (Russo& & Van Roy, 2013) of the hypothesis class, which is exponentially large for simple neural network classes (Dong et al., 2021). Yang et al. (2020) achieves sample-efii cample-efficient exploration based on the overparameterized neural networks (Simsek et al., 2021) as the function approximator. However, their analysis hinges on the neural tangent kernel (NTK) and can not handle NNs beyond NTK regime. In contrast, our analysis can adapt to generic neural network classes.
Our work is also related to the analysis of model-based RL. (Osband & Van Roy, 2014; Ayoub et al., 2020; Kakade et al., 2020) and representation learning (Ren et al., 2021; Nachum & Yang, 2021; Zhang et al., 2022b). The definition of our MDPs with neural dynamics generalizes that in Kakade et al. (2020) and Ren et al. (2021). In contrast to the KNR model in Kakade et al. (2020). we can handle the infinite neural network hypothesis class and do not require the nonlinear feature map to be known. Ren et al. (2021) require sampling from the posterior distribution of the hypothesis class, which is computational- -nnfffffiiin when the hypothesis class is large. In addition, the sample
2

---

Published as a conference paper at ICLR 2023
complexity bound of Ren et al. (2021) depends on the Eluder dimension of the feature map class, which is exponentially large for simple neural network classes (Dong et al., 2021). In contrast, our sample complexity bound depends only on the neural network classes only through its capacity.
Our work motivated by the complexity analysis neural network classes. Dong et al. (2021) show that the Eluder dimension of one-layer neural network classes is exponentially large, suggesting that the previous analysis of RL algorithms based on the Eluder dimension (Russo Van Roy, 2013) may not be applicable neural networks.
1.2 NOTATION
For vector E Rdd, we define == (Ei uf of)1//2 where is the i-th element of For real-valued function
- R, we define [l max [=()]]- For vector-valued function f + RR,, we define |I = max,ex [2))22 For a sequence of real-valued functions r r= (ra]i C - R. we define |||| = Su the e-covering number of the function class F with respect to the norm ||-||- define (F, log.V(F.c. (l-)lcc)) for a real-valued function class F, and define H2(F, = (og,((Fs e, 21))) for a vector-valued function class F. We further define [n]] = (1....,,1) n) when n is an integer. For a set C. we denote by A(C) the set of the distributions over C, and (CC) the uniform distribution over C. For g X' + R and Xr {II,...,III InJ C X, we define g|
|n((r)). We denote by NNFF c, II-I))
PRELIMINARY
We consider an episodic MDP =²= (S. with a state space S E Rdd an action space A, a horizon H, transition kernels p = (P%) and reward functions r" {[r H We assume that the reward functions are bounded and deterministic, that is, || E [0, for all h E [H]. We also assume that the action space finite, that is, |A] < 00. The agent iteratively interacts with the environment follows. At the beginning of each episode, the agent determines policy where Tr : S + ((A) for any h E [H]. Without loss of generality, we assume that the initial state is fixed to Sinit E S across all episodes. At the f-thh step, the agent receives a state 8s, and takes an action an following an T.(- 8n). Subsequently, the agent receives a reward (Sh, (h)) and the next state following 8h+1 P (- 18, sh)a)). The episode ends after the
π =
agent receives the last state 11 For a given policy т = {To 1i=1 where Thh :S + ((A) for any
h E [H], we define the value function VY"" and the Q-function Q7 for any h E [H]] as
(8 = En.p.
8h = (8i, az)
i=
(2.1)
Q,,s,,;r", ,P')= E P.
Σ r (st, az)
sh =; s, =
Here the expectation E,, [-|] in (2.1) is taken with respect 8:41 (. ( a;) and a; Tx(- ( s:) for i E {h, h + 1,..., H H.. For convenience, we define VT (s, P) = 0 for any state a E S. reward function transition kernel P and policy n. For simplicity. we define the expected total reward JTT;"", ,,*) [TT,,",, PP) = Vi" (8iit ("mittr",, The goal of RL is to find a policy x that maximizes the expected total reward. Specifically, for the episodic MDP V = (S. H, r*) We define x" E argmax, !(;;r",, P*) as an optimal policy. Correspondingly, we define the optimal Q-function Q and the optimal value function VI (7, a; P*) = O (s,a;r", P*) and (8, "'""""""*"*"""""""""""""" VA"" (s;r", p** for any (8, E S A.
3 MARKOV DECISION PROCESSES WITH NEURAL DYNAMICS
In this paper, our goal is to develop provably efficient algorithm for RL problems adapted with large feature space, such as neural networks (NNs). To this end, we introduce the MDPs with neural dynamics, whose reward and transition dynamics parameterized by NNs.
3

---

Published as a conference paper at ICLR 2023
Motivation. Our definition is motivated by the kernelized nonlinear regulator (KNR). In KNR model, the transition kernel takes the following form.
$/+1 W o (Sh, an) +
c~ (O, Ta):
(3.1)
where of, is a known nonlinear feature map. Former research proposes sample-efficient algorithms for such a model. Although such a KNR setting empowers sample efficient RL (Kakade et al. (2020)), it is relatively restrictive in the following two aspects. First, the feature map o%, and the expected reward ry are known a priori. Second, the model only imposes nonlinearity on (8h, (x) via the known feature map, while the conditional expectation of the next state given 8h, aj is a linear function of 6% (sh, an). In other words, when Φ7 is known, the transition dynamics can be recovered via linear system identification methods such ridge regression.
To generalize the KNR model, we interpret (3.1) as an energy- model. More specifically, we can write the transition of the MDP in (3.1)
(8 8/: (x) x (Fp(-F((s+1, 8h, ak))
(3.2)
where the energy function (s Sh, an) is defined as
E(sa+1, Shy an) || (i an 1l)11//2
(3.3)
Here (3.2) omits a normalization factor, which is a function of (sh, an). We generalize this model and impose nonlinearity on the next state 8 by substituting nonlinear feature map v (81+1) for 86-1 in (3.3). Such generalization allows us to incorporate the nonlinearity of the next state in the model. In addition, we assume that the nonlinear feature maps 07 and + are unknown and need to be estimated from pre-specified feature classes & and V, which for example, can be two classes of NNs. We further assume that the expected reward r" is unknown and needs be estimated from the reward function class R. We formalize our generalization in the following definition.
Definition 3.1 (MDPs with Neural Dynamics). An episodic MDP (S, A, H, ,",r") is an MDP with neural dynamics its reward function r" {rā ) belongs to reward function class R, which is known function class that consists of NNs, and the transition kernel of the MDP P {P takes the following form,
Ph(sn+1 Sh, ax) x exp( [1 (on, ( 12)
(3.4)
Rm and 1hat E V Rdd + R.T are two unknown feature maps, and क V are two known feature map classes that consist of NNs. We denote by M the set of all the transition kernels that take the form of (3.4), and let X E R denote the union of the image spaces of the feature maps, namely,
Here 0% E T
x= ()(()))) (v,,,, E x S A (p(s) (p,8) E V S} CRR.
Generality of Definition 3.1. We remark that Definition 3.1 is a significant generalization of stochastic nonlinear systems beyond KNR. For instance, when vi 1 (5++1) = 8h+1, the transition kernel Definition 3.1 takes the following form,
(S Sh, ag)) x exp (-11 |k41 an))///)))
which is the transition kernel in Ren et al. (2021). Therefore, we recover the model in Ren et al. (2021) when oh is known to be the identity map and the reward function is known. Moreover, the transition kernel defined in (3.4) also includes class of nonlinear dynamics satisfying
Sh+1 = (vi++) (0% (Sh, ax) + te)),
where C Imm 4/++1 R >> RT the determinant of Jacobian matrix of v// is constant, and e is Gaussian noise. Our model significantly generalizes such model by allowing possibly noninvertible feature map t
Relationship with Kernelized Linear MDP. Recall that K(x, y) = exp(-1i= y v/3/2) is also known as the Gaussian RBF kernel, which induces a reproducing kernel Hilbert space (RKHS) defined on RM (Rahimi et al., 2007). (See Appendix $D for a brief introduction of RKHS.) Intuitively, K(x, y) measures the proximity between & and y in the kernel space. From this perspective, the transition
4

---

Published as a conference paper at ICLR 2023
kernel in (3.4) specifies the next state 84+1 by measuring the proximity of the representations
(sh, an) and th+1 ($1+1). Besides, since K(x y) can be written as (k(z), k(y)),, where the feature map of the RKHS k is defined as k(x) = K(x,)),, -), and (: the is the inner product of the RKHS respectively. Thus, (3.4) can be equivalently written as
(8 8h, an) - ( (K an) ( an)) (1
(3.5)
H²
where (sh, a4)) is the normalization factor in (3.4). Thus, when 2j, is known, our model can be regarded as an RKHS extension of the linear MDP model (Jin et al., 2020). This is the case when e the identity maps but unknown to the learner, and 77, (Sh; (1)) becomes constant (Ren et al., 2021). See Appendix $D for more details of the relationship between the model in (3.4) and RKHS.
Role of NNs in Our Model. We would like remark that the model specified in Definition 3.1 not restricted to NNs. In fact, the definition only requires proper function classes of the reward function, representations of (s), ai.) and 8i+1, namely, R, L, and V. Thus, our model can also be defined for other function approximators such as polynomial spline (Unser et al., 1993), classification and regression tree (Syrgkanis & Zampetakis. 2020). Meanwhile, as we will see in the sequel, both our algorithm and the theoretical results do not hinge on NNs and can employ general function classes with bounded capacity. Here we call our model neural dynamies in order to highlight that our work is the first one that covers arbitrary NN classes with bounded log-covering numbers.
4 ALGORITHM
In this section, we introduce an algorithm for solving MDPs with neural dynamics in the online setting. We first introduce the motivation of the algorithm, and then introduce the procedure in detail.
Motivation. To strike a balance between exploration and exploitation, our algorithm follows the principle of Optimism in the Face of Uncertainty (Lattimore& & Szepesvári, 2020). When we know the true feature maps {o we can apply kernel LSVI (Yang et al., 2020) to construct the exploration bonus since the energy-base transition admits kernel structure. (See $3 for the details.) However, in MDPs with neural dynamics, we do not know { A straightforward solution for handling the unknown feature maps is to learn the feature maps from the data we collect and construct the bonus based on the learned features. However, the bonus constructed by the learned features might be invalid since the learned features have errors. We handle the error in the learned feature by purposefully taking uniform actions when exploring the environment. Such a sampling scheme gives us more diverse data for model estimation. Based on this motivation, we design an iterative algorithm that outputs policy after N iterations. In particular, in each iteration n E [N], our algorithm performs the following four steps: (i) sampling new data from the environment, (ii) estimating the model via maximum likelihood estimation, (iii) constructing exploration incentives using the features of the learned model, and (iv) updating the online policy for exploration via planning on the learned model.
Sampling Scheme. As we mentioned in $3, the transition of MDPs with neural dynamics can be written as an energy-based model and admits the Gaussian RBF kernel. To exploit the kernel structure in the transition, we explore the environment using the exploration bonus induced by the Gaussian RBF kernel and the feature maps learned from the data, which motivated by Yang et al. (2020). However, since the bonus is not induced by the true underlying feature, it might fail to indicate the most uncertain state-action pairs for exploration. To mitigate such an issue, we combine the uniform policy, which samples action from the uniform distribution over the action space, with the optimistic policy during the sampling procedure. Intuitively, such a sampling scheme provides a wider coverage over the state-action space and better explores the environment.
To simplify the presentation in the main text, we present the sketch of the sampling scheme as follows. The rigorous presentation of the sampling scheme for the boundary case deferred to Appendix $B. In the n-th iteration of our algorithm, given the previously collected dataset D for i E {0. 1,2] and h E [H], we interact with the MDP following the policy न" { 1 and obtain the new dataset DE, for i E {0, 1, 2} and h E [/] Specifically, for any h E t-1, H}. we start from the initial state 81 and choose the action og ~ T. s5.) in the h-th step when h E {1,... ,h), and choose the action aj ~ (AA) when h E [h + 1, h + 2}. Here (AA) is the uniform distribution over the action space A. By following such procedure, we obtain the following trajectory.
$1, 01, .1,..., 8h42, a2+ Th+2, 8h43,
(4.1)
5

---

Published as a conference paper at ICLR 2023
where 81 Sinit- Then, we label the obtained trajectory follows,
hhi,i = Sh++i
C,+i, ah+i, Thtis Phtii S1tt11 = Shtit1, (4.2)
for any i (0,1,2) We then update the dataset Di by Di, D (88% "2,5 hhe 8 (.)) for any E {0, and E [H]] We use in (4.2) to indicate how many steps of the uniform policy we need to execute obtain such dataset. Intuitively, the dataset with bigger has better coverage over the state-action space A. We summarize the sampling scheme in Algorithm 1. See Figure in Appendix $B for illustration of the sampling scheme, and see Algorithm 3 in Appendix şB for the formal presentation of Algorithm I.
Algorithm 1 Sampling Scheme (Informal)
1: Input: Policy n" {xr h= datasets D for i E (0,1, and h E [M].
2: for h = --,...... H do
3: Interact with environment to obtain the trajectory (4.1) by first executing x" from 81 to
8h. and then execute U(A) for two more steps. Label the obtained trajectory as (4.2).
4: end for
5: Set Ph.s (0% 0 Th, sh(,)) -=1 for h [H] and i {0,1,2), where the tuple > Updating the datasets
(sh Th,:: (h+t,)) the data label in (4.2).
h= 6: Return: Datasets h,3 h=1,
Model Estimation. To estimate the model, solve the following optimization problems,
Th argmin ER
Σ
[rA ars-rrsh.ah an))
(4.3)
D = argmin
Σ
log P(sn+1 [hh ap).
(4.4)
PEM
(9h.0h.7h.hh+
Here R and . are the reward function class and the transition kernel class defined in Definition 3.1. We denote by ob and + the feature maps that correspond the transition kernel pt estimated in (4.4). To simplify our analysis, we assume that there exists an oracle that returns the global minimum of the optimization problems (4.3) and (4.4). Similar assumption also arises in the previous study of RI. (Fan et al., 2020; Kakade et al., 2020; Uehara et al., 2021; Jin et al., 2021a). When the normalization factor in (3.5) a constant, (4.4) can be easily implemented since is equivalent with
P argmin
Σ
(1+(+++)) - (hnn, (ah,, an)
NE (sh, 4y PEDD
Remark 4.1 (Transition Estimation). We would like to remark that the method for estimating the transition is not restricted to maximum likelihood estimation (MLE). Methods including variational autoencoder (Kingma & Welling, 2013), score matching (Hyvärinen & Dayan, 2005) can also be used for transition estimation. Our sample complexity bound holds for any transition estimator whose total variance enror has an upper bound.
Exploration Bonus. The transition kernel in Definition 3.1 is closely related to the radial basis function (RBF) kernel. In the sequel, we define the bonuses for exploration and update the policy based on such bonuses. Specifically, for fixed feature map o S IR, we define the Gram matrix Ky and the function [[] S A + R² as follows,
K7 [o]
K(o(5)
2 11) ----=
Eaxn
k (s. = k(((s, a), 0 ( o1
( a), o( ]]]
e ER. V(s, SxA.
where ((8) th Th )) |m E Di. We then define the bonus ug as follows,
(s,)a)) ( 22 (s, as)
(4.5)
where ())))))) 1 ( a) (A KE(ON) (s,

---

Published as a conference paper at ICLR 2023
Here B > 0 and À > 0 are the tuning parameters. We remark that the form of the bonus in (4.5) aligns with the bonus in other previous works that use kernel functions for function approximation (Srinivas et al., 2009; Yang et al., 2020).
Remark 4.2 (Dependency of Rewards on Features.). Here we do not require that the reward depends on the feature in the transition kernel, which is different from the literature in linear MDPs ( (Cai et al., 2019; Jin et al., 2020). Common sense seems to dictate that we can not characterize the uncertainty using the feature without such dependency. However, the estimation error of the reward estimators Th in the empirical measure can be bounded from the above by the property of the least square estimator. Therefore, the uncertainty of r the distribution induced by any new policy, such as n². can be bounded from the above by the distribution shift, which is characterized by uh-1- Such an observation allows us characterize the uncertainty of the reward estimator even when the reward does not depend on the feature in the transition kernel.
Policy Update. We update the policy n=+1 by setting it as the optimal policy of the learned model, which can be efficiently computed by dynamic programming. Due to the space limit, we defer the details of the planning algorithm Appendix $B. We remark that we can also apply other model- based algorithms, including Dyna (Sutton, 1991) and Gradient-Awan Model-bass badel--ased Policy Search (D'Oro Oro al., 2020). to compute the optimal policy of the learned model, and the suboptimality of the output of Algorithm 2 is bounded when the error of the planning oracle is bounded.
Remark 4.3 (Computational Efficiency). Our algorithum is oracle efficient in the sense that our algorithmm is computationally efficient given an optimization oracle for model estimation, which also appears in the previous study (Fan et al., 2020; Kakade et al., 2020; Uehara et al., 2021). More specificully, the bonus and the policy in euch iteration can be esficiently computed by (4.5) and Algorithm in the appendix. The existing literature on general function approximation requires either global optimism over the confidence set (Kakade et al., 2020; Jin et al., 2021a) posterior sampling over the hypothesis set (Ren et al., 2021), which can not be computed efficiently.
Algorithm 2 Exploration with Learnable Neural Features (ELNF)
1: Input: Failure probability 5 > tuning parameters 3,A O.
2: Initialize: Set T = {TH h== 11 where T s) = =A) for any (s, E S x [H], and set Dh., = 0 for all (h, E [ x {0, 1,2).
3: for n = 1,..., .N do
4: Set (Di, (Dr h- by applying Algorithm 1 (Sampling Scheme) with the policy x" and the
datasets (D%,7 (Dn-1yh= 11
Th=1,i=0 as the input.
> Sampling
5: Set (7%) and (P /
as in (4.3) and (4.4), respectively.
b Model estimation
6: Set {øg)
h=1 and { 1 as the feature maps corresponding to (Pr) h=1'
H
7: Set [up]
in (4.5).
b Feature estimation and bonus construction
8:
Set n by applying Algorithm 4 (Planning Algorithm) in the appendix with the learned
model {T%) 1h (Pr) and the bonuses (ū7) H hhm as the input.
b Planning
9: end for
10: Return: मे = 21( 11
5 THEORY
In this section, we present the analysis of ELNF. We first present the boundedness assumption on the model.
Assumption 5.1 (Boundedness of Model). We assume that the state space is a bounded set of Rdd, and the Lebesgue measure of S is absolute constant. We also assume that max{[|o(ss, a)ll2- (1b())l))) I for all (s, a, v) E Ax W. We further assume that 0 r(s,a) a) < for any (s,a,r) E Ax R.
Since S is bounded, Assumption 5.1 is a reasonable regularity condition on the model. Such a regularity assumption is standard and is also assumed in the previous works (Cai et al., 2019; Jin et al., 2020: 2021b). Next, we introduce the following assumption, which characterizes the complexity of the NN classes.
7

---

Published as a conference paper at ICLR 2023
Assumption 5.2 (Decay Rate of Covering Number). There exists constants Cuet 0 and y 2 0 that only depend on (R, Q, V), such that
Ho(e) max (Ho ( 5) H2( H2(V, Ceet log(1/e))/CC
In Assumption 5.2, y characterizes the complexity of the NN class by quantifying the growth of the covering number when the covering radius decays. We remark that previous research bounds the covering number of NN classes from the above the same scale Assumption 5.2. For example, Schmidt- -cheee (2020) and Chen et al. (2019) show that NN classes with specific structures satisfy Assumption 5.2 with ? = See Lemmas C.3 and C.6 Appendix &C for the details.
Theorem 5.3 (Sample Complexity of ELNF). We assume that Assumption 5.2 holds with y < 1/2, and we can obtain the exact solution to the optimization problems (4.3) and (4.4). We set the tuning parameters X and / as
= C' m (og(4HH 3 C|A (23/044 Vlog (8H
in ELNF, where m the dimension of the image of the feature maps, C', C" are constants that only depend on the regularity parameters in Assumption 5.1. Under Assumplion 5.1 and 5.2, for the policy returned by ELNE, it holds with probability at least 1 that
"a""r""P" - [R;;"" ,P)) S CHH |A|2 ; 2r(2-11/(2+27)) (log Nym+1.
Here C is constant that only depends the dimension m, the bound of the feature maps R, and Cnet Assumption 5.2, and = (log (NN is a logarithmic factor.
Proof. See Appendix şE for detailed proof.
In Theorem 5.3, À is the regularization parameter that trades off between bias and variance, and | is the uncertainty coefficient, which scales with y and N. We remark that our analysis is not restricted to NN classes, and can be extended to other bounded function classes with bounded covering numbers. further remark that m Theorem 5.3 is the dimension the image of the feature maps, which can be much smaller than the dimension of the state.
Moreover, Appendix ŞE, we show that the suboptimality bound Theorem 5.3 reduces to (r2 (2/222)) in terms of N, where der the effective dimension in Definition E.4 in the appendix. Such bound connects the sample efficiency of ELNF to the effective dimension of the RKHS and the covering number of NN classes. We further remark that when = 0 Theorem 5.3, the suboptimality bound sublinear N, which aligns with the previous theoretical research. detailed comparison with the related work can be found in Appendix $A.
PROOF SKETCH OF THEOREM 5.3
In this section, we sketch the proof of Theorem 5.3 and highlight the technique that allows us to remove the dependency the Eluder dimension of NN classes. Since the policy â returned by Algorithm (ELNF) is the mixture πT r.....,, N,, we can decompose the suboptimality as
J(m"rr", J(a:"" Pm)
J(m :r PT) - J(x";r" T th u², Pr)]
Term (a)
[[m";: n" pm) 1 n + w", pm)]
Term (b)
J( n 1, n" pm " po))
Term (c)
8

---

Published as a conference paper at ICLR 2023
Here Term (a) is the out-of-sample estimation error of the estimated value J. Term (b) is the error of the planning algorithm, and Term (c) is the in-sample estimation error of the estimated value J. Since the bonus u" captures the uncertainty of the estimated model with high probability, and the planning algorithm finds the optimal policy of the learned model, Term (a) and Term (b) are small with high probability, which is shown in the following lemma.
where C2 a constant that depends the regularity parameters and the parameters of the NN class. Following the same condition of Theorem 5.3, we have Term(() S AHS holds with probability at least 1 6. We also have Term(b) < when we use Algorithm 4 for planning.
Lemma 6.1 (Informal). We define Ç VC2
RN/6)
Proof. This can be directly proved by Lemma E.5 and Lemma E. See Appendix $E for the details.
The remaining analysis is to connect Term (c) with the complexity measure of the model class. Former research (Wang et al., 2020; Jin et al., 2021 that allows neural network parameterization quantifies the uncertainty by the level set, and the Eluder dimension naturally appears when we telescope the in-sample error. To remove the dependency quantify the uncertainty by the bonus defined by the true feature. However, since the true feature is unknown, can only quantify the uncertainty using the learned feature. Inspired by Uchara et al. (2021), we obtain the following lemma, which connects the bonus defined by the learned feature with the bonus defined by the true unseen feature.
the Eluder dimension, we want to
Lemma 6.2 (Bonus Equivalence for the True Model, Informal). Following the same condition with Theorem 5.3, we have
[[; u", P') S2|A| Bd //n J(;
holds for any policy π and n 2 2 with high probability, where the bonus defined by the true feature un {1,, (. Jh=1 is defined in Lemma I.1.
Proof. This is Lemma 1.2. See Appendix $1.5 for the details.
We remark that we cannot obtain the above lemma by directly applying the technique in Uchara al. (2021) since they only consider the fintte-dimensional inner product. Using the lemma above, we have Term(c) S 32 |A| V + Σ J[ P*) holds with high probability. Finally, we show that the sum of the bonuses defined by the true feature can be bounded by the effective dimension of the RKHS induced by the noise instead of the Eluder dimension of NN classes. We conclude the proof of Theorem 5.3 by combining the upper bounds of Term (a), Term (b), and Term (c).
Removing Dependency on Eluder Dimension. The existing literature on RL using general function approximators relies on the Eluder dimension when bounding the regret or the suboptimality (Wang et al., 2020; Jin et al., 2021a; Ren et al., 2021), which is exponentially large for simple neural network class (Dong et al., 2021). However, we can remove such dependency in MDPs with neural dynamics. Our key insight is that et al., 2020) whose feature is the composite map of the neural network and the feature map of the RKHS since the energy-bass transition admits kernel structure, which is shown in $3. Therefore, we can characterize the effect of the distribution shifts by the bonus defined by the true feature, whose sum is bounded by the effective dimension of the RKHS instead of the Eluder dimension of the NN class, without knowing the true feature.
regard MDPs with neural dynamics as kernel MDPs (Yang
Role of Uniform Policy in Proof. The uniform policy in the sampling scheme enables us to bound the influence of the distribution shift and show that the bonuses defined by the learned feature are valid uncertainty quantification.
order to show that the estimated value defined by the learned bonus is almost optimistic (Lemma E.5) for any policy, we need to bound the influence of the distribution shift. The data that we obtain from the uniform sampling has better coverage over S x A, and the bonuses construct with these data quantify the uncertainty with the presence of the distribution shift. Therefore, we take uniform actions when exploring the environment to obtain a valid uncertainty quantification without knowing the true feature, and |A| in the suboptimality bound is the price paid for the uniform sampling.

---

Published as a conference paper at ICLR 2023
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Yasin Abbasi- Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pp. 3692-3702. PMLR, 2019.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68333337,444, 1950.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pp. 463-474. PMLR, 2020.
Mikhail Belkin, Approximation beats concentration? an approximation view on inference with smooth radial kernels. Conference On Learning Theory, pp. 1348-1361. PMLR, 2018.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. arXiv preprini 19XXv:9112.058... 2019.
Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds family of recurrent neural networks. arXiv preprint 1rXiv: 12947, 2019.
Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. arXiv preprint arXiv:2102.000 168, 2021.
Pierluca DrOro, Alberto Maria Metelli, Andrea Tirinzoni, Matteo Papini, and Marcello Restelli. Gradient-aware model-basee policy search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3801-3808, 2020.
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint Xw1::i20233100000 2021.
Jianqing Fan, Zhaoran Wang. Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pp. 486-489 PMLR, 2020.
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning 2019.
behaviors by latent imagination. arXiv preprint
Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6, 2005.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire, Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pp. 1704- 1713. PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. arXiv preprint arXiv:2 102.001,, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021b.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information theoretic regret bounds for online nonlinear control. arXiv preprint arXiv:2006. /2466, 2020.
Diederik Kingma and Max Welling. arXiv:1312.611 2013.
Auto-encoding variational bayes.
arXiv preprint
10

---

Published as a conference paper at ICLR 2023
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of machine learning research, 4(Dec):1107-1144, 2003.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
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, 51a.re,,.1115550 518(7540):529, 2015.
Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. Advances in Neural Information Processing Systems, 34:30100-301 12, 2021.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS, volume 3. pp. 5. Citeseer, 2007.
Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. arXiv preprint arXiv:2111.11483 2021.
Tongzheng Ren, Tianjun Zhang, Lisa Lee, Joseph E Gonzalez, Dale Schuurmans, and Dai. Spectral decomposition representation for reinforcement learning, arXiv preprint arXiv:2208.0 20:::2228009951,,, 2022.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In NIPS, pp. 2256-2264. Citeseer, 2013.
Johannes Schmidt- Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 48(4):1875-189) 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017.
Berfin Simsek, François Ged, Arthur Jacot, Francesco Spadaro, Clément Hongler, Wulfram Gerstner, and Johanni Brea. Geometry of the loss landscape overparameterized neural networks: Symme- tries and invariances. In International Conference on Machine Learning, pp. 9722-9732. PMLR, 2021.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprini arXiv:0912.3995, 2009.
Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting. ACM Sigart Bulletin, 264):160-163, 1991.
Richard S Sutton, Andrew G Barto, et al. Introduction to reinforcement learning, volume 135. MIT press Cambridge, 1998.
Vasilis Syrgkanis and Manolis Zampetakis. Estimation and inference with trees and forests in high dimensions. In Conference on learning theory, pp. 3453-3454, PMLR, 2020.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline rl in low-rank mdps. arXiv preprint arXiv:2110.04652, 2021.
Michael Unser, Akram Aldroubi, and Murray Eden. A family of polynomial spline wavelet transforms. Signal processing, 30(2):141-162, 1993.
Sara A Van de Geer. Applications of empirical process theory, volume 91. Cambridge University Press Cambridge, 2000.
11

---

Published as a conference paper at ICLR 2023
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01 2019.
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005. 10804, 2020.
Holger Wendland. Scattered data approximation, volume Cambridge university press, 2004.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-255) 1992.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.0400 2020.
Tianjun Zhang, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear mdps practical via contrastive representation learning, In International Conference on Machine Learning, pp. 26447-26466. PMLR, 2022a.
Xuezhou Zhang, Yuda Song, Masatoshi Uchara, Mengdi Wang, Alckh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach. In International Conference on Machine Learning, pp. 26517-26541 PMLR, 2022b.
12

---

Published as a conference paper at ICLR 2023
LIST OF NOTATION
In the sequel, we present a list of notations in the paper.
Notation
Explanation
A.A. X
The state, the action, and the feature spaces, respectively.
The length of an episode, and the total number of iterations of Algorithm (ELNF), respectively.
H. N
The index that iterates from 1 to N, and the index that iterates from to H, respectively.
n, h
The index that iterates from 1 to n,, and the index that iterates from to h, respectively.
7, h
The feature map classes of the current state-action pair and the next state, which parameterized by NNs.
V
R
The reward function class parameterized by NNs.
(PAMeED (ri
The transition kernel and the reward of the MDP.
The dimension of the state space and the image space of the feature maps, respectively.
d,
1h= x"
The dataset and the policy in the n-th iteration Algorithm 2 (ELNF), respectively.
(PR Phhh
[F Uhhh-
The estimated transition, the estimated reward, and the bonus in the n-th iteration Algorithm (ELNF), respectively.
The learned feature in the n-th iteration of Algorithm 2 (ELNF). respectively.
(oR (611
K(x,y) = exp( | yll2). is the RKHS induced by K, and is the feature map of H.
H.K.
The set of the distributions over C, and the uniform distribution over C.
ACC),((C)
R
The upper bound of the norm of the features.
Cnet.
The parameters Assumption 5.2.
X.
The tuning parameters of Algorithm 2 (ELNF).
delt
The effective dimension we defined in Definition E.4.
cØ 1i (s,a)
The normalization function we defined (E.1).
The e-covering number of the function class F with respect the norm ||-
M(FFc,,1-1))
Ho (F.c) log e, 11-1loc.2).
log I1-...)) and H2(F,c)
(F c), (F)
Gmax is the upper bound of the feature maps, Gmin is the lower bound of the feature maps, and Tmax = Cmax/ Cmax/Cmin Cminn
Cranx Criin Tmax
The parameter that related to the upper bound of the estimation error in Lemma E.3.
S
STRUCTURE OF APPENDIX
We provide detailed comparison between our work and the existing literature in Appendix $A, and provide the supplementary for the planning algorithm, the NNs, and the RKHS in Appendix $B, Appendix $C, and Appendix ŞD. We then provide detailed proof of Theorem 5.3 in Appendix $E. We provide the proof of the key lemmas used in Appendix $E, including Lemma E.2, Lemma E.3, and Lemma E.8, in Appendix $F, Appendix $G, and Appendix SH. We provide the proof of other lemmas used in Appendix $E Appendix $I, and provide the proof of other auxiliary lemmas in Appendix $J.
13

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Detailed Comparison with Existing Literature
14
B Supplementary for Algorithm
15
Supplementary for Neural Networks
D Supplementary for Reproducing Kernel Hilbert Spaces
19
E Proof of Theorem 5.3
20
F Concentration the Inverse Covariance
24
G Proof of Lemma E.3
27
H Discussion on the Effective Dimension
34
Proof Lemmas in Appendix $E
42
Proof Auxiliary Lemmas
46
A DETAILED COMPARISON WITH EXISTING LITERATURE
In this section, we provide detailed comparison with existing literature.
Comparison with Kakade et al. (2020). Kakade al. (2020) studies the setting of KNRs and proposes the algorithm Lower Confidence- Continuous Control (L.C). They show that L.C is sample efficient by bounding the expectation of the regret from the above by ((133/22//22 22/2d which aligns with our results in terms of / and dont- However, they assume that the nonlinear feature map is known, while need learn from prespecified NN classes. Thus, our model is significantly more challenging. Moreover, their algorithm requires optimism over the confidence set, which is not computational efficient.
Comparison with Research on Linear MDPs and Low-rank MDPs. We show in $D.1 that our model can be generalized include linear MDP with unknown feature maps and nonlinear reward as a special case. Jin et al. (2020) show that their algorithm achieves Õ m H²N) regret. Our bound suboptimality aligns with their results in terms of the dimension and the number of iterations without assuming known feature maps and linear reward functions. Uehara et al. (2021) and Ren et al. (2022) propose algorithms for linear MDPs with unknown feature maps and show that the sample complexity of their algorithm is Ö(m* /e²) in horriit linear MDP with unknown feature maps, which also aligns with us in terms of However, they assume that the transition is finite dimensional inner product, and the unknown feature maps belong to a finite set, which greatly reduces the complexity of the problem.
Comparison with Dong et al. (2021). The sample complexity is Õ(E in terms of N when the logarithmic factors are omitted and = Mcanwhile, Theorem 5. in Dong et al. (2021) shows that the minimax sample complexity of solving nonlinear bandit problem with one-layer NNs and ReLU activation is ( To obtain such lower bound, Dong et al. (2021) assume that the action space the unit sphere Sd-1 in Rd which an infinite set, while the action space our setting is finite. In the case where H 1, our model reduces to finite-an arm bandit problem whose reward is parameterized by an NN. Although the Eluder dimension of the NN class large, the agent only needs explore the arms of the bandits in model, while the agent needs explore the unit sphere
14

---

Published as a conference paper at ICLR 2023
in their model. Therefore, their model does not belong to our model, result does not contradict
the lower bound in Dong et al. (2021), and the sample complexity in our model is dominated by the number of arms instead of the Eluder dimension of the NN class when H = 1.
Comparison with Ren et al. (2021). Ren et al. (2021) studies a nonlinear model with Gaussian noise. They show that the expectation of the regret of their algorithm is
H log .N- 1/2, 11-11)) (0,
where ( is the Eluder dimension of Φ. We show in $3 that the model in Ren et al. (2021) is a special case of our model. Our bound on the suboptimality aligns with their result in terms of the number of iterations N when 7 O. However, they do not fully exploit the kernel structure in the transition in their analysis, and their result depends on the Eluder dimension of v. Lemma C.7 in Appendix $C.2 provides an example of an NN class whose e-Bluder dimension is at least (()-(11)) and the e-log covering number is most (log (1e)). Lemma C.7 shows that removing the dependency of the sample complexity on the Eluder dimension significantly improves the sample complexity. In addition, their algorithm requires sampling from the posterior distribution of the hypothesis class, which is difficult to implement in practice. In contrast, our algorithm only requires planning with respect to the learned model, which can be computed efficiently.
Comparison with Yang et al. (2020). Yang et al. (2020) use overparameterizee NNs for function approximation in the algorithm Neural Optimistic Least-Squares Value Iteration (NOVI) and shows that NOVI is sample efficient. However, their analysis relies on the connection between overparameterized NNs and neural tangent kernel and can not handle NNs beyond NTK regime.
B SUPPLEMENTARY FOR ALGORITHM
As we mentioned in $4, our algorithm performs the following four steps in each iteration: (i) sampling new data from the environment, (ii) estimating the model via maximum likelihood estimation, (ii) constructing exploration incentives using the features of the learned model, and (iv) updating the online policy for exploration via planning on the learned model. We simplify the presentation of the sampling algorithm and omit the details of the planning algorithm in the main text due to the space limit. In this section, we first describe the sampling scheme rigorously in detail. We then provide the detail of the planning algorithm.
Sampling Scheme. As we mentioned in $3, the transition of MDPs with neural dynamics can be written energy- based model and admits the Gaussian RBF kernel. To exploit the kernel structure in the transition, we explore the environment using the exploration bonus induced by the Gaussian RBF kernel and the feature maps learned from the data, which is motivated by Yang al. (2020). However, since the bonus is not induced by the true underlying feature, it might fail to indicate the most uncertain state-action pairs for exploration. To mitigate such an issue, we combine the uniform policy, which samples action from the uniform distribution over the action space, with the optimistic policy during the sampling procedure. Intuitively, such a sampling scheme provides a wider coverage over the state-action space and better explores the environment.
To simplify the presentation of the algorithm in our work, we introduce an extended MDP, where we assign meanings to steps h = -1. 0. H + 1, and H + 2. In particular, the interaction of an agent with the extended MDP starts with a dummy initial state 8-1- During the interaction, all the dummy state and action sequences {s-1, 01,,, 80, 0o) lead to the same initial state Sinit- Moreover, the agent is allowed to interact with the environment for two steps after observing the final state #1+1 of an episode. Nevertheless, the agent only collects the reward Th (sh, ax) at steps E [H], which leads to the same learning objective as the original MDP. In addition, we denote by [H] [- O, H + 2] the set of steps in the extended MDP. We remark that the dummy state and action sequences {s $5-14 1,4-1.8p ag / do not exist, and we introduce them just to simplify the rigorous presentation of the boundary case of our algorithm. In the sequel, we do not distinguish between an MDP and an extended MDP for the simplicity of presentation.
Now we describe the sampling procedure in detail. In the n-th iteration of algorithm, given the previously collected dataset D for i E {0, 1,2) and h E [M]. we interact with the MDP following the policy x² (m 1 and obtain the new dataset DR, for i (0,1,2) and h [M].
1 H
15

---

Published as a conference paper at ICLR 2023
Specifically, for any h {-l...., H), start from the initial state 8-1 and choose the action an ~ ( (4) the h-th step when h E (-1,... h), and choose the action oj ~ (d(A) when h E { + 2}. Here (((A) is the uniform distribution over the action space A. By following such a procedure, we obtain the following trajectory,
8-1: 1:: 0-1: 80, 0o: 81, 01, P1: ... 81+2 42+2 Th+2: 81+3+
(B.1)
where $1 = Sinit- Then, we label the obtained trajectory as follows,
Shit 8h+ii
ah++
Thts Thtt
3hts, sh+it1,
for any i 20. We then update the dataset as follows,
Di, = Di,5 {6 oh Tho R+,)) (0 (h (h.s (ha)))
(B.2)
for any í E {0, 1 and h E [H]. The index (B.2) indicates how many steps of the uniform policy we need to execute obtain such dataset. Intuitively, the dataset with bigger index has better coverage over the state-action space $ x A. See Figure for an illustration of the sampling scheme, which summarized in Algorithm
Algorithm 3 Sampling Scheme (Formal)
H 1: Input: Policy n" [T A=-1 datasets h, for i E (0,1 and h E [H].
2: for = -1,-.....
do
Interact with the environment obtain the trajectory in (B.1) by first executing n" from 8 Sampling
to sh. and then executing ((A) for two more steps.
4: Set (5h44,, th+i rn Theiia 5h- + (8)+4) Obta Thto Sh+142) for {0, 2,), where
(81+41; Oh+i, th+s; 8h41+1) i is defined in (B.1). 444, (
5: Set Phtii + (
h44,0 $141.) for 10,1,
Labeling
6: end for
7: for h 1......, H do
b Updating the datasets
8:
Set Di,, < Di, UDD for E 10,1,2)
9: end for
10: Return: Datasets (Dm,simm
1h=H,i=2
%
$2 1
gh 81+111
hh2,2
8h4222
Label
Label
LabelLabel
Label
Label
8-1
Sh
5h+1
8h+2
8h+3
h
Th
u(A)
u(A)
a=
ah -
ah
ah++
ah+2
Label
Label
Label
0
Figure 1: Sampling procedure in the h-th trajectory of the n-iteration. We first execute the optimistic policy for h steps, and then execute the uniform policy for two steps. Finally, we label the collected data as the figure shows.
Planning Algorithm. The details of the planning algorithm is now summarized in Algorithm 4,
16

---

Published as a conference paper at ICLR 2023
Algorithm 4 Planning Algorithm
(hhh-11 estimated transition (Ph 14 2: Set Qir(s, a) 77 (s, a) + (s.
1: Input: Estimated reward {f% 1H
hJAmi bonus { 141 [0/hh11
3: Set (s) <- m 2 (s, a) and HH (11s) argmax EaEd ())
4: for h H1 1..... do
5: Set Q7 a) + (s, a) + (5, a) + Ss (s |, (
(s')d''
6: Set V2, (5) A (5, a) and i (. s) argmax EEEd Q7 ()(
7: end for
n++1 as the uniform policy ((A). 8: Set m and To"
9: Return: n n+t t (mh -
We remark that we can also apply other model-based algorithm, including Dyna (Sutton, 1991) and Gradient-Awan Model-bases Policy Search (D' D'oOro et al., 2020), to compute the optimal policy of the learned model.
C SUPPLEMENTARY FOR NEURAL NETWORKS
In this section, we provide more details neural networks. In the first subsection, we introduce the definition of the covering number, which measure the complexity of function class, and provide two examples of neural networks in detail and show that such neural networks satisfy our assumptions. We remark that our analysis can be extended to other neural network classes when Assumption 5.2 is satisfied with y S 1/2, and is not restricted to the examples below. In the second subsection, we provide a lemma that compares the log-covering number of an NN class with the Eluder dimension. Lemma C.7 in Appendix $C.2 shows that removing the dependency of the sample complexity on the Eluder dimension greatly improves the sample complexity.
C.I EXAMPLES
We begin with the definition of the covering number. Definition C.1 (Covering Number). Let (æ, I)) be a normed space, and 2o C Q. The set f0i, 02,..., &.} is an c-covering of t if supace, inf,e(s) ll dil We define the covering number N(0o, e, IIII) as the minimum size of such covering.
In what follows, we provide two examples of neural networks in detail and show that such neural networks satisfy our assumptions.
Example 1. The first example is the s-sparse neural network class. Schmidt--Hihhee (2020) show that the s-sparse neural network class satisfies Assumptions 5.1 and 5.2. We first introduce the defnnition.
Definition C.2 (The s-Sparse Neural Network Class). We define (xx) max(æ, 03. For vector E R", we define the shifted activation function og IR" - R" as
Te (c( = (a uI,,..., o - bt))
A neural network with network architecture [I.p)) is function that takes the form,
RR + RP4+) f(x) = W....... Wox.
(C.1)
when x E R Here is the depth of the neural network, W; is a Pi+1 X ps weight matrix, va E IR is shift vector, and p (Po. .......,, (po...., ,LL+1)) The neural network class Fm LL, p) is defined
|| V 1l S 11.. Fm p) {f f takes the form of (C.1) with j=.....L
max
The s-sparse neural network class is defined
s, (flff (L, Σ
[Wll + 11lyllo S s, supplf(())ll S M). xEX
17

---

Published as a conference paper at ICLR 2023
We directly obtain the boundedness of the neural network class F FLn(L,p, p,s, M) by the definition. Moreover, Schmidt-Hieber (2020) bound the covering number of Fm (L, 8, M) from the above by the following lemma.
Lemma C.3 (Lemma in Schmidt- (2020)), We define V e > 0, we have
-1 (pt + 1). Then, for any
log (F (L, (L, M), e, 111l.e) 2 (s (1++))oog((44+1)))
Lemma C.3 verifies that the s-sparse neural network class satisfies Assumption 5.2 with y = Therefore, the s-sparse neural network class defined in Definition C.2 satisfies Assumptions 5.1 and 5.2.
Example 2. The second example is the recurrent neural network class. Chen et al. (2019) show that the recurrent neural network class satisfies Assumptions 5.1 and 5.2. We first introduce the definition.
Definition C.4 (Recurrent Neural Network Class). A recurrent neural network f(X,, t: U, W,h is a mapping that, when it is parumeterized by E Rdd xdn, V RR Rddy W E RR Xda, ho E Rd and gel X, (Z1, ................................ Lx. E RddxXt Xt, L inpul, it relurns Y, = (y1,..., Rd,xt
h4 (Uh + Wxt),
Yt (Vhh),
where Th and are two nonlinear activation functions. We define the function class FRNV(L, B) as the set of functions that take the form of [(; 3,,t; W, bo), where a recurrent neural network that only takes bounded input, and the spectral norm of U, V, and W are all bounded by B.
In Chen al. (2019), they analyze the recurrent neural network class under the following assumption. Assumption C.5. We assume that the activation functions dn and By are Lipschitz with parameters Ph and Py respectively, and (0) o, O. Additionally, we assume that dh entrywise bounded by M.
Assumption C.5 can be satisfied by lot of activation functions. For example, Assumption C.5 satisfied when we choose (-) = tanh(-) and (.).) max(0, -). We directly obtain the boundedness of the function class FRNN(L, B) under Assumption C.5. Moreover, Chen et al. (2019) bound the covering number of FRNN B) from the above by the following lemma.
Lemma C.6 (Lemma 3 in Chen al. (2019)). Under Assumption C.5, we have
log.N (Fawv(L, B), 11-11oo) S 3dl log Getvd - 1) 1)) ())((e( -1)).
where d = (dz + dy + dn) and e = PyPh B max (1, ph. B).
Lemma C.6 verifies that the recurrent neural network class satisfies Assumption 5.2 with y Therefore, the recurrent neural network class defined in Definition C.4 satisfies Assumptions 5.1 and 5.2.
C.2 COMPARISON OF ELUDER DIMENSION AND LOG-COVERING NUMBER
In this section, we provide lemma that use an example to illustrate that, the log covering number of a NN class can grow more moderately as the covering radius decays than the Eluder dimension.
Lemma C.7. Let R be a one-layer NN class defined as
R {rob: A R ra,)(a) a08 b), 0 E |10|/2 1, 51..0b5555 05b51),
where a is the activation function in Definition C.2. Suppose we have A C Rd and ||a||æ < 1 when R is at least Q (d-1),, and the e-log covering number is
E A, then the E-Eluder dimension R bounded from the above by (llog{/e)).
Proof. See Appendix L1.4 for detailed proof.
Lemma C.7 suggests that, the log-covering number an NN class can be much smaller than the Eluder dimension. Our algorithm is sample efficient since the sample complexity of ELNF depends on the log-covering number of the NN class instead of the Eluder dimension. We remark that the NN class in Lemma C.7 also satisfies Assumption 5.2 with 7 0.
18

---

Published as a conference paper at ICLR 2023
D SUPPLEMENTARY FOR REPRODUCING KERNEL HILBERT SPACES
As shown in Nachum & Yang (2021) and Ren et al. (2021), the transition kernel our model is closely related to the RKHS corresponding to the Gaussian kernel. In this section, provide more details on the RKHS. In the first subsection, we provide the definition of RKHSs and some basic properties of RKHSs. In the second subsection, we lay out several properties of the population operator and the empirical operator defined in (E.44 and (B.2).
D.1 BASIC CONCEPT
We will be considering the use of RKHS for designing the exploration bonus. We first introduce the definition of RKHS and positive-definite kernels.
Definition (Reproducing Hilbert Kernel Space). Let H. be a vector space which consists of functions
that take element in X input and take their values in R. We assume that H. is equiped with
inner-product (s-)x H x H + R. The function K : X x X + I. is reproducing kernel of H if satisfies the following properties, namely, (1) we have ((x,,) E for all E X, and (2) we
have (g, K (zz.)))) g all x E X' and H. We call H reproducing Hilbert kernel space (RKHS) it a Hilbert space with a reproducing kernel K.
Definition Dossitive-Definie Kernel), A kernel function K X x X + R is positive definite if E Ej=1 a,a,K (xx,, (z)) 2 for all n 2 1, (a1...., an) E R and (Z1, 2n)" E X
The following lemma reveals the connection between MDPs with neural dynamics and RKHS.
Lemma. There exists an RKHS H. such that K (I1, = exp(- - | - 2211 /2) is the kernel of H. The kernel is called the Gaussian kernel.
Proof. Rahimi et al. (2007) show that the Gaussian kernel is a positive-definite kernel on X C R Moore-Aronszajn theorem (Aronszajn (1950)) shows that for every positive-definite kernel, there exists an RKHS H. associated with the kernel. Thus, conclude the proof.
We remark that by the similarity between different RKHSs, our analysis can be adapted to the cases when the right-hand-side of (3.4) is another kernel function.
Definition D.1 (Generalization of Definition 3.1). An episodic Markov decision process (S, A, H, (r" is an MDP with neurul dynamics if its reward functions r" = {ri)==1 C R. where R is a known reward function class that consists of neural networks, and the transition kernel of the MDP P {PP) h= takes the following form,
!1
(h
Sh: an) = K [(00, (57 (8h, 0h); 1/ 1
Here K a positive-definit kernel, oi, E $ RRdd x A - Th and 1/ E V R.d Thmh are two unknown neural networks, and & and y are two known feature map classes that consist of neural networks. We denote by M the set of all the transition kernels that take the form of (3.4), and denote by X E mm the space of the embedded feature.
We remark that when K( x22 = xx x2 in Definition D.1, we recover linear MDP with unknown feature and nonlinear reward function.
D.2 OPERATOR PROPERTIES
In this subsection, we provide the properties of operators defined in (E.2) and (E.4). The following lemma shows that [ D, X] and TplØ, p. T, are both positive-definite operators on H. which guarantees the existence of the corresponding inverse.
Lemma D.2. Let be a probability measure over X, and [22 be the set of all functions that is square-integrable on X with respect to p. We have H C (X). When we define the operator T as T [g(z) Sx K(x', ((x',,))((a (x)g(x')p(a)) ), we have Ig E H when g E I2)(2). Moreover, when I is regarded as an operator from to H, it is non-negative definite.
Proof. See Appendix $1.5 for detailed proof.
19

---

Published as a conference paper at ICLR 2023
The following lemma shows that the operator norm of the inverse operator of the empirical operator can be computed efficiently. Lemma D.3. Let H be an RKHS. For Xn f0r 1.1.-.., Fn we define r[X,] H - H
N[Kagg(>) >g(x)) + (F
Here K is the kernel of the RKHS. We denote by ls the feature map of the RKHS. We have
[1((2)]] 1[t.] ((xxx)) (x) (AT K( ( (((x)(x))) />.
Here k() = (K(11, x).... (Zn, x)) E IK" and K[ = [K (x ) E R"x"
Proof. See Appendix $J.6 for detailed proof.
We end this subsection by bounding the operator norm of the operators I=[0, D, A] and po, p,,
Lemma D.4. For any E H. we have
Xg < [. (. - (A+
Σ
((6(s,a). g)
+ K[6(, a), o(s o(s. (g. 9)n
Ng.gin &
Proof. See Appendix $J.7 for detailed proof.
E PROOF OF THEOREM 5.3
We first state the theorem again with clearer description on the choice of the parameters. Theorem (Theorem 5.3, restated). For MDP with neural dynamics that satisfies Assumptions 5. and 5.2 with 7 < 11/2, we set
(nt/(L+>)) m (og(48H)N/8)
1=) 4202/2222222 + 10r2 P [A].
in Algorithm (ELNF). where is the dimension of the image of the feature maps. Suppose we can obtain the exact solution to the optimization problems (4.3) and (4.4). We have
P*) J(f:""
C |Ap 2(27-13/(222) (Log (log(48HRN/88) 5/2
(log my
with probability least 8, where के is the policy returned by Algorithm (ELNF). Here C is constant only depends on the dimension m, the bound of the feature maps RG and Onet in Assumption 5.2, and is defined as
<= Cog /N/
where C2 is constant depends the regularity parameters and the parameters of the NN class.
Proof. We define the normalization function c(Oj, 1 116 (sh, ax)) )) as
clo 2h 1 an)
J exp 117 an) - 3 2h (s dsnti-
(E.1)
By (3.4) and (E. the transition kernel pj can be written
Ph Sh an) =exp ( [10 an) &h i /cli 1h+ an).
We define the bound on the normalization constant as
Crnax
sup clo, (s, Guin
inf dER.EEW (x
cle (s, Tuax CCuax/Cuin
PEO.EEV (x,0)ESxA
20

---

Published as a conference paper at ICLR 2023
We have Cmax U, Cmin 2 v exx( and Tmax I exp(2R when Assumption 5.1 holds. Here v is the Lebesgue measure of S.
Since the kernel function ( x22 cxp([ - xzl 222 /2) is positive-definite kernel, it induces an RKHS. We denote by H6 the RKHS induced by K, and denote by k the corresponding feature map. This allows us to corporate techniques in RKHS into our analysis. The following lemma reveals the relationship between the bonus we define and H.
Lemma E.1. For a finite dataset DD = {18 Or operator on H. Telo, D as
(1, 1 8,+1)8+ and g E H. we define the empirical
[elo, D, Dgg()) >g(x) +
Σ
((((s,))
(E.2)
(s.a.T;"))D
and denote by (0, D, A] the corresponding inverse operator. Then we have
(s, a) = min 2H + + (1 1- DM
Proof. We conclude the proof by directly applying Lemma D.3.
In the sequel, we introduce two good events. We first define distributions and the population operator, which
in the definitions of the good events. For index [N] and E {0, 1, 2). denote
by 0he the distribution of (sh, as)) when 81 = Sinit, the state 87+1 ~ Pk( 8h 0%), the action ag #f. | s;)) for [h i]. and as ((A) for h E {h i 1, ..... h). where U(AA) is the uniform distribution over the action set A. We further define the measure Ph.e as
()) Σ (s,/aa)) v(s,a) ESXA
(E.3)
For distribution over S A, we define the population operator as
po p, A, [))(()) = >g(x) + T (((e ())(sss))))()) a))x(((()))))))))))))))))) a),
(E.4)
and denote by I- (0, p, A, 7] the corresponding inverse operator. For the empirical operator and the H and I (( p, X, Tlg H when g H. The operators
population operator, have [e D, P. in (F.2) are also positive-definite and self-adjoint for any dataset DD when X, F > 0, which guarantees the existence of its inverse. We denote by E that the bonus defined by the empirical operator is bounded from the above and below by the operator defined by the population operator, that is,
1 2 [ a)) ()) Am) S (1(( a)) (o.D, S 22|| (r=
(E.5)
for any @ E क, (s, a) S x A (0. 1, 2), and (h, n) E [H] [N]. The data we collected contains enough information for us to design the bonus for exploration when & holds. We denote by &g that
E(
TV a,) Ph( 0))
S <²/nn,
(E.6)
E Essa))=
(f, ( o)1 < <3/n
(E.7)
for all (h, n) E [H] x [N]. í E (1,2). Here TVip1 (V))(.).P2( is the total variance divergence of two distributions. Our estimators of the model are accurate the sense that the population risk of our estimators are small when & holds. The following lemmas show that E and &g hold with high probability.
Lemma E.2 (Concentration of Inverse Covariance). Under Assumption 5.2. when X CpmN7/0++)) log ( RN/ Event ε, defined in (F.5) holds with probability at least 8/4. Here C is constant only depends the parameters of the NN class.
Proof. See Appendix F for detailed proof.
21

---

Published as a conference paper at ICLR 2023
Lemma E.3 (Estimation Error). We assume that Assumption 5.2 holds with 7 2. Event &g defined in (E.6) and (E.7) holds with probability at least - 6/5 when
<= (002log((21))) (2
Here C2 is a constant depends on the regularity parameters and the parameters of the NN class.
Proof. See Appendix $G for a detailed proof.
Lemmas E.2 and E.3 show that good events E and &g hold with high probability. In the following part of the proof, we condition on Event & and &z. We also define the effective dimension follows.
Definition E.4 (Effective Dimension). Let H be an RKHS and K be the corresponding kernel. For Nn f#1...... ,.,, we define the matrix K| [[x]] [K(T,, Ir, 5 and define
(n Ao) = sup log det + K K/ X,CX
Let k be the feature map of H., and ((2) be the set of distributions over X, we define
A2(n, Ao) = sup nEn-p PEA(X)
Here the population operator I H H. is defined
Ao fxx) (x)(2) + nnEoo (K(
We define der (N +
The effective dimension A₁ is the maximum information gain in Srinivas et al. (2009), which is closely related to Gaussian process regression. The effective dimension A2 is also closely related to the dimension in finite-dimension RKHSs. See Appendix $H for a brief discussion. The effective dimension def is closely related to the sample complexity.
We are now ready to present the proof of Theorem 5.3. Our goal is to bound (T ;"" (@;r", P*). Since the policy स returned by Algorithm 2 (ELNF) is the mixture of π ..... N have
J( -
J PT)
Σ
J(m';r", (m P")].
(E.8)
We decompose the suboptimality as
N
N
N
N
-
n,
+
nn.2
n,33
(E.9)
R=1
n=1
n=
Torm
Term (b)
Term
where n" = [(/]] hh1 is the bonus we define in (4.5) and {z F (a.N)E(N)x(s are defined as
2n,1 = J(T r* p¹) - J[T=;'r'' r + ut" Pr),
2n, J(T u. pm) ( T + un, p")
Zn,3 " + u", Pd) J ( P*).
In the sequel, we bound the terms from the above in (E.9) separately. Term (a). To bound Term (a), we introduce the following characterization of the bonus.
Lemma E.5 (Almost Optimistic for the Planning Phase). Following the same condition of Theorem 5.3, when condition on the good events Ex, Eg defined (E.5), (E.6) and (E.7), we have
[T;;"" uu pd) (T:r, ((:T,,"")) > - -H 1)
holds for any policy n. Here the bonus n (u defined in (4.5).
22

---

Published as a conference paper at ICLR 2023
Proof. See Appendix $1.1 for detailed proof.
By Lemma E.5, we have Term (a) S (H+ JACVVN.
Term (b). The following lemma bounds Term (b) from the above.
Lemma E.6. For the policy x= returned by Algorithm (Planning Algorithm), we have
J r" + u² uu, (P") ; ;
rr" + u², Pm) S 0.
Proof. See Appendix $1.2 for a detailed proof.
By Lemma E.6, we have Term (b) = E +u" - +xx ; + pn) S 0.
Term (c). We have the following lemma, which bounds Term (c) from the above.
Lemma E.7 (Bounded optimistism). Following the same condition of Theorem 5.3, we have
N
Σ [ + +u,Pp") p") -[x PT)] & 46H² |A| C3i V des N log(10H/0) V
with probability least 6/2. Here 31 (4H² + 6H 2) 4 / and Ç is defined in Lemma E.3.
4r max A (
Proof. See Appendix $1.3 for a detailed proof.
We denote by Eg the event defined by Lemma E.7. In the following part of the proof, condition on Event Eg. By Lemma E.7, we have Term (c) S 46/² |A| (31 1:3i/deh N log(10H//8. Combining the upper bounds of the terms in (E.9), we have
N
Σ [[(a'rr" J PT)] S H HIAIINNNSS 46H v den log(10/1/0)), (E. n=1
By the definition of 81 in Lemma E.7, we have 31 S 24H2 UC emin (VV + CB dett [A).. By the definition of 3 in Theorem 5.3, we have B 3 24H / Smin ( (V> C (A))). Therefore, we have
81 S 3 at.. dea (V( vIAI)
(E.11)
Combining (E.10), (E.11) with the value of À in Theorem 5.3, we have
Σ [i J ( p')] < 36000H 22 | 2 AN (1g(10//8)/5)) n=1
S C2 1A N1+4443122))) (1og(48H)R/66)) 5/2
(E.12)
where C3 is a constant that only depends on the dimension of the feature the bound of the feature maps R, and Cuet in Assumption 5.2. The following lemma bounds des from the above.
Lemma E.8. For the Gaussian kernel K ((x1, x2)) = exp(- || x2112/2), we have
dett S C)
Here Ca is constant that only depends the dimension and the radius R.
Proof. See Appendix $H.1 for detailed proof.
Combining (E.8), (E.12) with Lemma E.8, we have
J(xT :rr::"",, P*) J P') C LA 2( (1g(4(HHN/))) 5/2 (log Nym+1, where C3 is a constant that only depends on the dimension of the feature m, the bound of the feature maps R, and Cnet in Assumption 5.2. Thus, we conclude the proof of Theorem 5.3.
n
23

---

Published as a conference paper at ICLR 2023
F CONCENTRATION OF THE INVERSE COVARIANCE
In this section, we provide the proof of Lemma E.2, which shows that Event & defined in (E.S) happens with high probability. We first show that we can prove Lemma E.2 by the concentration of covariance using Lemma F.2. We then prove the concentration of the covariance for fixed feature map using the concentration inequality in Lemma F.3. Next, we take a union bound to prove the uniform concentration for covering of the feature map class, and use the property of the covering prove the uniform concentration of the covariance for the whole feature map class, which concludes the proof of Lemma F.2.
Proof. We first introduce the filtration we use for our analysis.
Definition F1 (Filtration). For any E [M], we define Fu as the o-algebra generated by the trajectories the first n. loops of Algorithm (ELNF).
By taking a union bound, we only need to show that for fix n E [N] and E 10,1, we have
(((((, () lo.e,... /4 - ((((s, Iee 1e. S [[ a)) a))
for any @ E + and (s, a) E S x A with probability 1 1 - 6/(2H Since we have (1,(,, a)lla S R. it remains show that with probability 1 8/(2HHN), have
[k(=))lf=' 10.0g, Am) /4 (1(())) (( S 441]((())
for any I RT with |0||| I R. We first prove that [|+(())] (6. [o.D S 4 (1x(2))) (0. Am)
for any x E RT with ||>||| S with probability at least 5/ 5/(48NN) The following lemma allows us to prove the concentration of the inverse covariance by the concentration of the covariance.
Lemma F.2. Let H be Hilbert space, and A, B be two positive-defiiite and self-adjoint bounded linear operators on H. Suppose (I, Ar 2 (æ, Br) for all x E D, we have (x, A x)Hx S (x,, B- B-1x) when B BB-/2C-1B--122 E Here C. = (B 1B21/2 AB-1/2/12
Proof. See Appendix $J.8 for detailed proof.
For simplicity, we define r, ppp0, Mh. A, n]. T22 = [e((o, Di, Al.
Ho = { k(x)) x E Thm and || - R and Hi = [Tk(.) x E TR"" and | S R²). (F.1)
where -
By Lemma R2, it remains show that |I s 4 |1gl1 for any y Hi with probability at least 1 - 5/ 6/(48HN). By the definition of the population operatór, we have
Illl, =
Amj = A llall + Σ B(ra))ek. (
Similarly, we have llall = > llal + ΣT 9 ah,)). Therefore, we can prove || < 4 Il, by the concentration of g². We define
Mi = C(H,, 61 l+1l))))
N₂ -2 = c( - (2, 11.1),))))
(F22
for simplicity. Here C denote the covering sets defined in notations, é1 and 62 tuning parameters. By Bernstein inequality, we have the following lemma, which can be used to show the concentration of g².
24

---

Published as a conference paper at ICLR 2023
Lemma F.3. Suppose that {F+ is a filtration and {(s [a") is a S x A-value stochastic process adapted to this filtraion. We denote by o' the distribution of (s",a") when condition on F1 For any fix E H. and ò E D. The following inequality holds with probability least 1 8/2.
S2 2
B(s.a)=e' [o'( + 2log(2/6))
We also have the following inequality with probability at least 8/2.
Σ Essarrer [9] (o (6)((())))
Σ ( - 2 log((/0)()
Proof. See Appendix $J.9 for a detailed proof.
For any 9 C(H,, l1e and & E C2, 11,) by Lemma F.3, we have
Σ B [9]
g² (6(5) aT,1) + 2o (DNN(NNNNN////00... (F33 (0 (o((, / Σ
with probability at least 1 - 6/ (N.HH.N Here Ni and N22 are defined in (F:2), 0%, is the distribution of (8) aTs)) when condition on -1 By taking a union bound, we have (F.3) holds for all g E C(H1, c1, (l)))()) and & E C(Ø. E2, 2l with probability at least 1 8/( 8/(48HN), Therefore, we have k(E,, 2 1 N/(HHNN when we define En,h,i as the event that (F.3) holds for all g C(H1, E1, Il)) and Φ E C(Φ, e2, 1
In the following part of the proof, we condition on Event En,h,i. For an arbitrary Hi and ø E Φ we choose go E C(H,, 61, 11-11 and Φo E ((,,,,,, l|.11l..,2) such that supzex (g(x)) - (o(()) S 6 and (U (1((s,)) - (o(ss)))le SEz.
E2. We decompose the difference the expectation by
B ((,a)ee (0b(0((s, [ El(aaamet [o [o²
(F.4)
Be (10 (s0(()(()aa)) + ((((s,)))) (30 (90(cb(s, =(((b))))))=(((((a)))))
s(((s,))))
Since suPaex 1ø(z) 90 <1, we have
00 (o(0o(s, a)) g(o(s, S s(<u(s.a)) g(0(ss
(F.)
for any (s E x A. Combining (F.5) with the reproducing property of H. we have
(o((o(s.a)) s(o(s, 61 + (o. (9. k(o(s,
(F.6)
sa 11l1m [ a)) - k a)) m
where the last inequality follows Cauchy-Schward inequality. For the kernel feature map k, we have (( a)) ((((s a)) || [| a)) + | 2(A(0u(s, a)) ((((o(s
=2(1- -x(1-exp(-11po66
((s, a)ll /2) < (| o(s, a)l² s eg.
(F.7)
Combining (F.6) with (F.7), we have (00 a)) 5(0(1 ((((( a))l S + e2 || and
go (o(oo(s,0) a)) (( s <a + e2 |l + 2111||x
(F88
We plug (F.8) into (F.4) and have
n
Σ
E (e. or. | (((
Σ B(r.a)oo. (00()
(F9)
S (62 + 2ez) g) + (2e162 + 26,) ||lll + c
The following lemma provide an upper bound and lower bound of g) for g E Hi.
25

---

Published as a conference paper at ICLR 2023
Lemma F.4. For any g H and the operator I defined in (F.1), we have Xg.9)m + -))² (Tg,Tg)> - (A (). 9/29.
Proof. See Appendix $J.10 for detailed proof.
Combining the definition of Hi in (F.1) with Lemma F4, we have (0.9) (k())) (() n)² 2/(A +n),
(F.10)
where the operator I' is defined Lemma F.4. Therefore, we plug (F.10) into (F.9) and have
22
Σ B(aaarer [g² (d(s,a))
E (s,a)~e (s) Σ
(F.11)
I In[(c + 26x) + (A n) (26 + 201)/A1/2 ( () (9.
By the same method that induces (F.11), we have
Σ 2o (000( () Σ o (oloh, (h,)))
(F.12)
S <n((c) + 262) + (2 m) (2 2c, 2////
By the definition of Event En in (F.3), we have
a
Σ Bla.a~oo (
Σ
( aT,))) 2 Nog(485HNNNNNN/0))
(F.13)
for E C(H1, e1, llo) when En,h.s holds. We plug (F.11), (F.12) into (F.13), and have
Σ B(s,a)met, (0(((s
(F.14)
+ el, x2,,
when condition Event & defined in (F.13. Here n(n, 61, 62] is defined as
<|n, 11, (2) = 3n [ + 262) (A n) (/ 22 22 m) By the definition of n|n, E1, <2] in (F.15), we have
(F.15)
x|n, E [2] 5n + 6(A 8/2 / 3/33223/22) 2(( + /))3 < 38n ((1+7)
(F.16)
when we set 6 = (2) and = 11((1n)) Combining (F.14) with (F.16), have
Σ B(naa)ehh ( /2 /2
(F.17)
Σ 3 ( + log + log + 2lgg(48HN/8) + +38m2/0+1) (o 9
remains bound No and log from the above. The following lemma bounds Mi from the above.
Lemma F.5. For the set H, defined in (F.I), have 6(HH,,,,lHl)))) (IE(A ())(222))m/2
Proof. See Appendix $1.11 for detailed proof.
26

---

Published as a conference paper at ICLR 2023
By the definition of M1 in (F.2) and Lemma F.5, have lo I 12m log(nR). By the definition of Mi in (F.2) and Assumption 5.2, we have loggN2 I Caie, (n(,11 log where Celc,1 is constant only depends on Cas in Assumption 5.2. Therefore, by (F.17), we have
E BGaaaee (6(ssa))
Σ g² ( ()))) + 530Ga..mm 1o04
when condition on En,h,i in (F.3). By choosing 1060oa,, log we have
Σ E (o,0)~e ( /2 Ng.ghn/2 S (o(sT, (5,)) Ng.9)a
(F.18)
for any g E H1 and & when condition En,,, By the same method inducing (F.18), we have
Σ (o(s )h Mg.9.n 9/ S 2 B(sa)re (o(( + 2> ghn
for any g E H₂ and o E when condition on En,h,i, which concludes the proof of Lemma E.2.
G PROOF OF LEMMA E.3
In this section, we provide the proof of Lemma E.3, which shows that Event &g defined in (E.6) and (E.7) happens with high probability. We conclude the proof of Lemma E.3 by combining Lemma G. and Lemma G.2, which provide upper bounds of the estimation errors of the reward and the transition estimation. Lemma G. is proven by the standard technique of bounding generalization error. Lemma G.2 is proven by the same method of Theorem 7.4 in Van de Geer (2000). To prove Lemma G.2, we show that the estimation error in the transition closely related to the uniform convergence over function class induced by the transition kernel, and then prove the uniform convergence over the function class using empirical process theory.
Proof. The following lemma bounds the population risk of the estimators of the reward from the above.
Lemma G.1. Let (Fr be a filtration and {x-17=1 be X v-lueed stochastic process adapted to this filtration. Suppose r- is a F,+1 -aa-mmaaarabll random variable with Bir, F+]= r (x+). where r* R is an unknown function and R is known function class. We define the estimator of r* as
F= arggmin FR
(rr- - (r=))(
ET=1 B[(r(x+)) (xx))) [r-il/n, and then We also define the population risk as Risk(r)
have
Risk(F) s 16 lolog 1101))))))) 12e
with probability at least for any fix e, 8 >
Proof. See Appendix $G.1 for detailed proof.
We first apply Lemma G.1 with 1/(14T) then have
(ssa)><H, (s, - (), a) +( [P((s,a) - a))
< 24n 11(11+)) 32 32og + Cnan 1002m/ + +7))/n
Cuet,1n -1ue,,nn1/(4+)110 (og0000
27

---

Published as a conference paper at ICLR 2023
for any n) [H] x [M] with probability least 1 - 6/(2HH)) by Assumption 5.2. Here 1uet.1 = 56 + 3eCnet/ (1 + + is a constant only depends on the parameter of the neural network classes. By taking union bound, we have
E (aa))=o
1% (s,a) as) Cuet, 1/(1++)) -uet,inn\//1+))) log(20HN/0)
holds for all hi, E [2] [H] x [N] with probability at least 6/20.
The following lemma bounds the population risk of the estimators of the transition kernel from the above.
Lemma G.2. Let "F=)"=o be a fitratiion and let {(,,, Sr) 7-1 a x A S-value stochastic process adapted to this filtration. Let Pr be the distribution of (S,, when condition Fr We assume that S₁, ~ (*(-1 St, A7) when condition on (S+, A7) and Fr We estimate P by
p
argmax PEM
log P(S A+).
Let M, be the covering number of the transition class M, and define (c, log,Ne, 1x)) Let G be function satisfies (1). G(e) non-increasing, and (2)
G( 2 max {8)
2/22
2 -1/2 9/) g)du,
22/211
where G (ōp as V (P(s' s, + P* s, a.a))/2, P E M}. Suppose en satisfies
Vnc, 2 CgG((n)) where Cg is an absolute constant. Then for any 2 max 1//n), we have
2 2)) Cg cxp cxoxp(-ne2/C)
E (a
Proof. See Appendix $G.2 for detailed proof.
The following lemma bounds the covering number of & in Lemma G.2 from the above. Lemma G.3. For two feature map classes & and M, we define the density class as
M {P. P
P(s'| s, = cxp( 1lo(1, a) (ss')1 /2)/ 3s a) & E DE w)
where the normalization function clp, vil (s, a) is defined in (E.1). We then have
exp(p R² (_ex_p((-- )
4 (1-1160.2) )
H₂ exp(- (R2 )2 2 (RyCmax (v + Cmax) V ll- (1-1))..))
Hod (6. 9) S H12
R.yCmaxx( + cmax)
where G is defined in Lemma G.2.
Proof. See Appendix $G.3 for detailed proof.
By Lemma G.3, when we define & in the same way as Lemma G.2, we have
Hoc (c, () & Hz H2 4) + H2 (2 < 20nett (1 log Creg.1 + log(1 (Crog < 2 + log(1/c))
where Creg,1 = exp(- R2) ct (Reiia/RRrrrr /R (Ry/Cmax(U + Cmax)). and
Greg.2 2Cuc log 1rrg,,)//77 1eg,1
constants only depend on the regularity parameters. We have
1/8
H 2
I)
Crog.2 / log (og/////too(/
2
2/217
/ 7/22)
28

---

Published as a conference paper at ICLR 2023
when 7 2. Therefore, we set G(c) Creg.2/ log C (25
/ a//e/////(( 7//2). By such def- inition, the solution of Vnez = (G((n) should satisfy cn I Crog.3n-1/22+ log n, where Creg,3 is a constant only depends on the regularity parameters. Therefore, when we choose Creg.an (n N/0 where Czeg.1 is a constant only depends on the regularity parameters, we have
S 2 1=1
(x. TV ( ( s, s. 2 C 1eg.17 -2/(2+)) log
x [N] with probability 1- 6))2HN By taking a union bound, (E.6) holds for all (i, (t,,,n) n) [2] [H] [M] with probability at least 5/20, which concludes the proof of Lemma E.3.
for any n) E x [H]
G.1 PROOF OF LEMMA G.1
Proof. We first define & = rr r" (x.) and Risk(r) = n [r, r(æ,)]? )1/// /n. By the definition,
the noise e, is Fr+1 -eessurbble random variable with Eler Jx] 0. We have
[r+ rxx+)]² = 2 [r (x++) - r(x+)] + [r' - r(x+))² 2
(G.1)
for any fix E R. We also have Risk(r*) Σこ= G. Since Bic, FF] 0. by (G.I), we have
e {[(r= r(x,))² - (rr - r" (2,)) (r'(z,) - r(z,)) | = 0,
and Var (r= r(xx))² - (r, - rr'( (xxt)) -fr - r(xz))² [
= Var 2e (r" (x+) - r(x+)) Fイ < 4E (x.) - r(x=))² Fr-1
Applying Lemma J.4 with X= = 1/4, we have
Risk(r) Risk(r") Risk(r)= 2 -e 2)
Σ E (r=(z)) ( 1 100((1/8))
"
|rr
with probability at least 8. By the definition of the population risk Risk(r), we have Risk(r) - Risk(r") - (3 Risk(r)) 2 -100 with probability least 1 8. Equation (G.2) shows the concentration of the risk for a fix R. For the uniform convergence, we define C as the e-covering set of R with infinity norm, and have
(G.2)
Risk(r) Risk(r") - Risk(r)/4 2 -4log(N/6)//
(G.3)
for all r E C with probability at least - by taking a union bound. Here the covering number V CC) Therefore, when we denote by ER. the event that (G.3) holds for all E C. we have ((ER)) 2 1 - 8. In the following part of the proof, we condition on Event &x. For an arbitrary E R. choose r' E R such that ||r--rll I 6. First, have
Risk(r) - Risk(r))/)/))) Risk(r') + Risk(ri)//4/
Σ (2r, r(xx) - -' (f-))) -((r))
+ 4n Σ R (2r - r(xx)())))))))(
1
-(() r - ((x))) ((r)) Fr-]]
By the definition of the covering and the boundedness of the reward, we have Risk(r) - Risk(r)/4 Risk(r") Risk(r')/4 2 -3c. Therefore, we have
Risk(r) Risk(r) Risk 44oog(W/8)/n 3e
for all r E R when condition on &R defined in (G.3). Let 7 be the minimizer of Risk(r), we have Risk(F) > (F) Risk(F) <r"sk(r*) 2 16 log(A//8)/rr 12c
when condition on Event &R. Since P(Ex)) 2 1 - 5. we conclude the proof of Lemma G.I.
29

---

Published as a conference paper at ICLR 2023
G.2 PROOF OF LEMMA G.2
Proof. We denote by H the Hellinger divergence of two probability measures, which is defined as H' (P1().)2))) = / (VP
(P((s)
ds.
Since we have (V3 P2) S (P1 P2). remains bound the population risk from the above in terms of the Hellinger divergence. We now require the following lemmas, which connect the Hellinger divergence with the uniform law of large number (ULLN).
Lemma G.4 (Lemma 4.2 in Van de Geer (2000)). For the Hellinger divergence H. two probability
measures P(- (-|ssa) a. and (- 8, a,,. we have
16H² ((P(- | 8, + (. /2, 8, a)) 2 HP((( (,,)), P-
Lemma G.5. When we define P(s' s, = (P(s' s, + P* | a))a) we have
> H2 (P(- Sr, Ar), Sr, Ar)) Fイ-1]
P(S
Sr Ar)
n R
log P(S S,, Ar) P* Ar)
log
Fr-1
P* ST, A+)
Proof. We conclude the proof by directly applying Lemma 4.1 Van de Geer (2000).
We define the function gr,1, the functional Vn,1, Vn,1 follows,
(P(s') ss,a) + P | s. a)) (2P"(s s,a))):
(s, as = log
(G.4)
2
(g) 1
Σ
n
g(( uT;
R btaa
Vn
H2 ((P(( (s,0)+
+ P' s a)) P" ('11s,)))
(P) ((s,))mpr
(G.5)
By Lemma G.5, we have Vn, (97,1) ( 2 0. By Lemma G.4, we can prove Lemma G.2
by showing that Un < 2 122 holds with high probability. Therefore, we only need to prove that
P
Vn. (gP.1) V 2 20) < <Cexp(-nee /C2)
sup PEM. (P))2 //28
for some absolute constant C.. Since the Hellinger distance is bounded from the above by 1, we have
sup PEMMonalP))20//10
1n, (gp,1) - (TVvn,(P) 2 20)
(G.6)
sup (n,1(9) 2 Vn122-10222
gEg(2> 4c)
where = min(s: 2--44 > 1} and G(e) = (gp,1 | P M, 2). Therefore, we can prove Lemma G.2 by the uniform law of large number on the function class g(c). We introduce the definition of the bracketing and related ULLN in martingale processes as follows.
Definition G.6 (6-entropy with the bracketing). Let {F+}r=o be a filtration and { be X-valued random process adapted to this filtration. For 0
8 S R. let be the smallest value of N for which there exists non-random collection flo/ :9; 1 1- such that for all g E G, there exists non- non-random j(g) E [N], such
NB, (ō, G. [X,]= )= (x)]"=:((FF)"
that gtio) (x) E g(x) < Sy (x) for all x E X, and (2). ( -6. (X,)a_ 1n_ S 8 for
30

---

Published as a conference paper at ICLR 2023
all j E [M]. We define d-entropy with the bracketing HB. as HB 9, (X, FFr }===0)
B, (, 9, {X, 17=1: (Fr)r=o) Here Xa1 (g. {x, ( {F+)7=)) is defined as
Xar (g. (X, 1 -0) 2M²
Σ E eex((l((X))) - 1- (g(x Fr Fr-1
Lemma G.7. Let (Fr be filtration and {X-}²=1 be --valued random process adapted to this filtration. Suppose we have sup XM (g) S foror the function class G. We set the values of the parameters M, So. St. S2. and C2 such that the following inequalities hold.
<u I SeVVRRR /M,
5O SVVR.
2 C2 +1),
(G.7)
R [ {
SO SI max
B.M (u, 9, (x
1 - (r)
(G.8)
(BA///)
where HB, M is defined in Definition G.6 and C2 is absolute constant. We have
[(((x)) - [(x(X+) 1 11 so
- C2eepp(
(
P
sup gEo
Proof.
We conclude the proof by directly applying Theorem 8.13 in Van de Geer (2000).
By the following lemma, we have (i) S 4e for g G(e).
Lemma. For the function gp,1, (P) defined in (G.4), (G.5). We have xi(gp,) S 16),,)(P).
Proof. We conclude the proof by directly applying Lemma 7.2 in Van de Geer (2000).
Therefore, we apply Lemma G.7 on G(2*-4e) with So /n122-10022 S1 4C2, $2 15, M = 1, and R = 20-2.. Our selection of parameters satisfies (G.7). To validate (G.8), we need to bound the generalized entropy of (e)) from the above, which depends on the distribution of the corresponding stochastic process. The following lemma decouples such dependency.
s,a) S (2 s, s,a), and define g', pi as Lemma G.8. We assume that S (s'
P((s,a,s') - 1-pPii Piis'
8, + (s s,a)
P* s,a) g' as) 2 log (s,,, 1 (1)(0))))))))
2
for 1,2. Let u be the Lebesgue measure of S. We have
X1 (g² -g" A,,
A,, S St) {o+)==)) S 2
- -PP()))))(((s,s))))))
sup (ESxAx)
Proof. See G.7 for a detailed proof.
Combining Lemma G.8, Definition G.6, with the definition of G(e) in (G.6), we have
HB.1 u. 9(t,, ((S,, A,,
S H ((8)) 1/2 G).
(G.9)
where (e, G) is the ello--cverrig number of G with respect to the infinity norm, and & is defined in Lemma G.2. When en satisfies the condition in Lemma G.2 with Cg = 21,C2 and 2 en, we have
10 2 C2G(2*c)
(G.
2
2 C2 max 8
(2))((2)) I)du, 2'c 3
2220
Combining (G.9) with (G.10), we have
27225-1022 10 > 4C₂ max
B. u1 (1,0(22
(0) A,, (F))"= )d, du, 20 25-26 }0
(,,,,,,,,,,,
220
31

---

Published as a conference paper at ICLR 2023
for all en and O, which validates (G.8) in Lemma G.7. Therefore, by Lemma G.7, we have
sup (n) 2 v7122-10 v CGexp(((1222 9Eg fe)
Therefore, by (G.6), when 1/ /n and C3 is an absolute constant that large enough, we have
sup PE.,,
(g(g).) - VnVn2(P))
- C2
Σ cxp(- 16 2
8=0
< C3 exp(-nc /C3).
We conclude the proof of Lemma G.2 by setting Cg in Lemma G.2 by the maximum of C3 and 2 22.
G.3 PROOF OF LEMMA G.3
Proof. We use the following lemmas to connect the covering number of different function classes and bound the covering number from the above using the covering number of and V.
Lemma G.9. We have (6, 9, & M. (+llo)) where & is defined in Lemma G.2 and infpe.M.r ((s' s.a).
Proof. See Appendix $G.4 for detailed proof.
Lemma G.10. Suppose the function class M defined as
M Pa(s' M={Puls s.a)/c(Pulss..)) P Mu]]
where the normalization function c(Pu)(s, a) is defined c(Pu)( a) Sses Pals' s,a)d(s)).
We assume that Crax (s, a) 2 Cmin and Pu(s' s, for any Pu E Mi. We have
N M, S (Cain 0/ ( 11-))
Proof. See Appendix $G.5 for detailed proof.
Lemma G.11. For two feature map classes & and V we define the function class M., as
My = (ccp(pcll((ss.. v(5'1l2/2) /2) de D D. w)
We have (8, l1 S ( o, 11 (/65(44)) V. ll,,),,,)) where R is the bound of the feature maps.
Proof. See Appendix $G.6 for detailed proof.
For the density class M, we have inf aaE P(s' s, 2 exp(-2R2)/eo CCmase where R bounds the norm of the feature maps from the above. Combining Lemma G.9, G.10, with G.11, have
(6, M', 11:160)) S (Ccover, 6, &, 11 (olo.) V 11-1
(G.11)
where Cenver = exp(-EB R2) 2
/ (r (rC/mmmle (U + Cmax)). We conclude the proof of Lemma G.3 by taking logarithms of both sides of (G.
32

---

Published as a conference paper at ICLR 2023
G.4 PROOF OF LEMMA G.9
Proof. For Pí, P2 E g'. we have Ps(s' s.a) ((P((s s.a) + P= s,a))/2 for i = 1,2, 8',8 E S and a E A for some P2 M. Therefore, we have
Pi(6' (8,0) P2(6' 18,a)
(G.12)
Pi(d' 8, P2 8,0)
Pi(s's a, + (s 8, v P2((' 8, (* s,a))
Combining (G.12) with the fact that P(s' a, 2 c for any P E M, we have
Pi(s' 8, - (s s, a)ه - Pi(s' 8, a, P2(8' s.,))/44/G.
(G.13)
Let C be 4/ce-covrring set of M. We define C" by
C'
(P(s) s, + | s,,)) P PE cc..
By (G.13), C' is e-covering set of G. and C'I = N148 11-1bo)) Thus, conclude the proof of Lemma G.9.
G.5 PROOF OF LEMMA G.10
Proof. For pl, p2 E M, we have (i(s' s.a) = Pi(s' s.a))/(Pilss,) holds for all e [2]. 8' E S and a E A for some p,, P E Mn. Therefore, we have
(' s, - (s s, (s - as s,a)
(G.14)
c(Pal(s, (cc()) ( s, (s, as (s,a)
s,a)
c[Pu](s, (s)
Combining (G.14) with Cmax 2 cc(Pu(ss,a) 2 Cmin for all Pu E Mu, we have
[P' 8, a) D2 |8,0) Semax PPl(s' s, P2 ( 8, a) 2
(G.15)
p 88 a) (c(P)) c (P a) //m
By the definition of the normalization function c(Pu)(s, a), we have
(PP.I(s.)) clP3](s ((plsaas))ppp))s......))))( a) < IP s, s, pi(ss s. s.a) Su Su|iP -P Pulloc (G.16)
where is the Lebesgue measure of S. Combining (G.15) (G.16) with the fact that Pu(8' 8, a) < Pall
for all Pu E M,, we have (s'(s' s,a) P²(s' | a,a] < |Pl. - (v + cmax) / Let
be a 2 + Ccoxer-oveering set of My We define C' by
(P=(Pa(s' s,a)//PPu(sss0 Pa Ec.. C' = (P
The set C' an e-covering set of M, and |e'l (c 5/(u (v + cmax), 11.11cc) Thus, we conclude the proof of Lemma 1.
G.6 PROOF OF LEMMA G.11
Proof. First, for any 0, we have
exp(-x²) exp(-)3) =1 exp(-u)de S -
(G.17)
33

---

Published as a conference paper at ICLR 2023
We set (0 (s.saa a) (1(('))12 / /v2 and y = (02(5, (22(5)112 /v2 in (G.17) and have
exp(( - || (8, a) - w4 (s))l /2)
- 2s2
(G.18)
(1) -i (s (1)((s,)) - [
|1 V2 [e( |102 22(s5))
by triangle inequality. For the first term in (G.18), we have
(s, - S [1 - (s)) (2, - 1 (s') #2(
(s, (2(6')1
(G.19)
Combining (G.19) with the boundedness of the feature maps, we have
(s,)) - (>')) - (2('')11 4R (12222)))))))))))))))))))))))( -1 (1(22)1
Similarly, we have (s, 22(2 - (l02(s,a) v 4R|1o2(s, By (G. we have
- U2 ( - exp(- 102(10)(s,)) - 2
- 4R ( (122((5')))))) ii (1: o (s, (s,,a)l2
(G.20)
Let Cj be a</(4r)coovrrin set of Φb and C2 be ( set of v. We define C by
( (1 /2/ E C2) C c a)
|0(s
By (G.20), C is an e-covering set of M,, and C| (V Φ, 11 ((66/4R), V, 1x.,))))) Thus, we conclude the proof of Lemma G.11.
G.7 PROOF OF LEMMA G.8
Proof. Since 2(exp(x)) 1 1-x)
x)) < (exp(x)) 1)2 when 2 have
xi (9 gt, (((r, )-)
exp((g((sr,an (sr: gf (s,, - 11)² Fr-1
EE
(s 8r, Br, pt (s' sT.
(*(s') ST, + (s' (s, -1 (D(5') (5 ay,s Fz-1
n2 1=1
2
(pU (8T7 - pl 8') ds' [r--]]
(G.21)
n
We also have
(s,, (p"(s,,,,,s') pz - s') 'ds) Fr-1
(pu
(G.22)
<v v
sup (xx
(" - P a, ss)
Thus, we conclude the proof of Lemma G.8 by combining (G.21) with (G.22).
H DISCUSSION ON THE EFFECTIVE DIMENSION
We first provide the following lemma, which shows the relation between A₂ in Definition E,4 and the dimension of space the case of finite dimension.
Lemma H.1. We have A Ann, Ao) when X' d and K K(I1,
x1 x2
34

---

Published as a conference paper at ICLR 2023
Proof. For any H. there exists 2 E R such that f(x) = 2 We also have k(z) By the definition of p. we have T plp, Ao, fx) = Ag Jar + nxz Exi~o(atar [a] I.. Therefore, the operator I pplp,>0. Ao n can be written as Aola + nE 1BExappaaaa] By the property of the matrix trace, we have
nLEEa (k(x), λo, Ao.m)k()))
=nB tr {dola + nB po )
=nB tr ((dota nB 1 xx.
for any p E A(X). By the exchangeability of the expectation and the trace, we have
nEzup (M<z), rp
- pp, Ao. ni n(k(z)) - nr (Dota nEEi~olz1011 "Exxp'"'a'xx
Exxplaxx" (xx
[r((Ta) oo (Aola NE NE S d.
Since p can be arbitrary distribution over we conclude the proof of Lemma H.1.
H.1 PROOF OF LEMMA E.8
To bound the effective dimension from the above, we construct an upper bound of the effective dimension by the eigenvalue of the operator in the RKHS, and then use the characterization of the eigenvalue in Lemma H.2 to obtain the upper bound. Lemma H.2 can be proven by Theorem A of Belkin 2). and we provide the proof in Appendix $H.2 here for the completeness of our paper.
Proof. In the following part of the proof, we bound A and A2 from the above separately.
Upper Bound of A1. Let XN+1 = fa1...., xN+1} be subset X. We define KN+1 = [K (K + 7y=1- Let X be the j-th eigenvalue of KN+1 and aj = (rnij-...,,0411, denote the corresponding eigenvector, have
N+1 log(1 + Ar/A).
logdet + KN+I/A) = Σ
(H.1)
Therefore, we bound log det(IN+1 KN+1/A) from the above by bounding { above. We define the operator Io as (x) = N+1 (I.,))()) + 1). The function N+1 (i. K (x,,a) .)) is an eigenfunction of To and >₃/(N 1) is the corresponding eigenvalue. The following lemma bounds the eigenvalue of I'o from the above.
N+1 from
Lemma H.2. Suppose X C X C R", and X is cube with side length I 2 1/mm, and is distribation over X, and the operator I L2(X) + LL(X) is defined as
If(x) / [ ((t)
JEEX
where K(t,z) x)) exp(- 2112 /2) It holds that >x(T) S Capp,5 asppa-Cap.aall //m). Here Capp.5 and Capp.4 are two constants only depend on the side length I and the dimension m.
Proof. See Appendix $H.2 for detailed proof.
Applying Lemma H.2 on Fo, we have Xy S. NCCppps exp(-Capppppppppeeeeeeeee (cap--app. //m) where Capp, Capp.1 are two constants that only depend on and R. Therefore, by (H.I), we have
Naii
log (T KN+I/A) Se
log(1 (1 + NC exp( Capp.
(H.2)
log 1 + NC exp( - a/mm
J=Nmio-1
We have Eyer log(1 NCapp.5 jj < Nmid log(1 NC 5/)). The fol- lowing lemma bounds the second term from the above.
35

---

Published as a conference paper at ICLR 2023
Lemma H.3. If is positive integer, have Ja t I 2mlx" when 2
Proof. When define bm -- e S e- we have
bm [o de e= + m 1m- e ' dt e= mbm-1-
By induction, we have bm = mle x E m Lemma H.3.
/mo! I 2mlx" which concludes the proof of
Since log(1 + 2) x, by the lemma above, have
N
N
5 log (1 + NC [[[[+NNCappp w.w.aaaaeppppC.a...aaa app. exp((Capp... m//m)///////)))))
NCapp,5 Capp-Capp.ai//mng aj ///////>
1
Nmaa+1
&NmCapp.5
jm exp(-j)dj/(C (ppp.11)
(-(mm1/// 1)/m exp(-Cappl mid mid $ 2Nm..app.. N
N1/m (ACapp..).
(H.3)
By (H.2) and (H.3), we have log dc + KN+1/A) S Ca a/Capp.a) m*+1 when we choose Nmid (log A Here C4 is a constant that only depends on the dimension and the bound of the feature maps R. Since Xx+1 can be any subset of X with [x+11| N + 1, we have AN + A, S Ca(log N/Capp.a)*++
Upper Bound of Ag. In order to bound A2 from the above, we need to choose an appropriate representation of the RKHS. We define the integral operator To L2(X) + (X(X) as Tof((r) Exgwp of (zo) K (20, z)}. Since p is a probability measure and the Gaussian kernel is bounded from the above, To is compact and self-adjoint. Therefore, by spectral theorem, there exists {e, {e such that it both the eigenfunction of the operator T and the orthonormal basis of the space (2(x). We
then define H. as
H = (=-SSSEL((M)) 1(())
Σ (x) ooj < <0]
where Xy is the eigenvalue corresponding to ej. We also know that = Σ;
(x),()),,())
For f(x) === (x) and g(z) =
00 1 (x), we define the inner product on H as
(f.9)n / Then the space H. is an RKHS with the kernel K, e A is an eigenfunction of I with eigenvalue ',. and {e// V D0 is an orthonormal basis of H. We represent k(z) using the orthonormal basis and have
[ - (M(a), (ko)), Σ ))e(()) Σ \1
Σ >)eg())(AA+N))
when we define Tf(x) = =f(x)=)((<) + (T). Therefore, using Fubini's Theorem, we have
NE [18(x])]]]]]] Σ
E. N Σ
N2y/(A+ NA2). (H.4)
j=1
1=1
36

---

Published as a conference paper at ICLR 2023
By Lemma H.2, we have X, Capp.s exp( Capp..a.) where Co and C1 are two constants only depend on the side length and the dimension m. We combine the bound on >3 with (H.4) and have
aappp. exp( Capp.4. 1/m)
NE [1I(())
NCapp. exp( - Capp, //mm m/m + A
Nmid
aappp exp(- (xpp(CCap..a)//)
8
aapp exp( Capp.ajt/my
apppp exp(
Capp. \/m) +
NC exp( Capp, aj f m) + A
j= Nmia+1
I Nmid + NCapp.
expl exp(-Capp.1) Capp. 1/ 1/m m)dd//.
Nmid
By Lemma H.3, we have JNma exp(- aj jdj S 2m!N 1-11m exp((Caspp.ll Capp. ///n) //Cdd)/Capp app.. Therefore, we choose Nmid = (log N/ N/Capp.4)" and have
PE (1tk))/ S(log 4/Capp.4) 2m!Capp.5 /(Capp. v
Ca N)m
where C4 = (1 + 2m!Capppp.p (ppp.)p) Com App.5- By the definition, C4 is a constant that only depends on the side length and the dimension m.
We conclude the proof of Lemma E.8 by combining the upper bound of A and A2.
H.2 PROOF OF LEMMA H.2
Proof. We require the following two lemmas. The first lemma allows us to bound the eigenvalues by the bound on the residuals of the approximation, and the second lemma bounds the residuals.
+ H. is a self-adjoint operator on Hilbert space H. and I,, is finite-rank operator with rank n. such that |[ I'llop S Here ||Allop sup ||Ax [| I holds that all eigenvalues of the operator I' except for at most (counting multiplicity) are smaller than
Lemma H.4 (Lemma 1 in Belkin (2018)). Suppose
Lemma H.S. Suppose X R is cube with side length 2 1//m, and I' V + H is (not necessarily linear) map from a Hilbert space V to an RKHS H functions on IR" There exists map I from the space V an n-dimensional linear subspace H., C H, such that
| - Fxllvvlv-- S exle22xpppppppppa 2/m) |[
Here Cupp.2 and Capp.3 are two positive constants that only depend on the side length I and the dimension m. and ||I (1'((x=)))())) suPeEv/to; [[Tollng(x) Wwllv.
Remark. Since H is subxet of (x) can view I as operator from the space V to the space L2(X) and investigate its operator norm accordingly.
Proof. See Appendix HH.3 for detailed proof.
First, by Lemma H.4, we have (TT) S inf (ank(()TT=))=-111 | 11-1llop: By Lemma H.5, we have
inf
||T Pi- rank(T:-1)) =i--
inf ||T ri- -T---llllgax
(H.5)
(ank(T';-))==)
$ Capp,2 exp( Capp,3 11) || TTllgg00)- S Cupp.2 cxp( Capp, (2/m)
for i> 1. Here Capp.t = Capp.32-1/m. It remains to bound [|[]] 1g(2)-< from the above. For elements E H and c' Lg(x)), we have
(e, Te'Te' = (c nEx <(())((t))dp(()) = -T (s,K((t))))<(00(0(( / c(t))((1(dp())
J
$ (1ell2g(0) Ile'l le'llegass & I|ellx lle" [e''llg(x0)
37

---

Published as a conference paper at ICLR 2023
where the last inequality is derived from (H.10). Therefore, have
[T''ll 1lx
(e, /ell S ||ee (eg())
eEH
which implies Lg - S Therefore, we have >x(T) S Capp.2 expl C Cappail/my for by (H.5). For i = 1, we have
(T) <
sup xELG(A)/(0)
[T> ( || 2ggars
sup zEL5(A)/(0)
[T /aap///lllllgg |= ||FlLgaa)) 1.
Therefore, we have (T) I Capp.5 exp(-Cupppl Cupp, m/m for all integer i when we set Capp,5 Capp.2 exp(Capp,a), which concludes the proof of Lemma H.2.
H.3 PROOF OF LEMMA H.5
Proof. We prove Lemma H.5 by constructing an operator that satisfies the condition in this lemma. For 2 (3 exp(8mnmm + 2)mm///pymm we have
max min || - x' /mln 11/mm S 13 exp(8m + 2)
1/m
" d'E
when 7m m! and Xr (II,..., (nn is m-dimensional grid of X. By Theorem 6.10 of Wendland (2004), the kernel K (1), exp(- ||| x21/2 /2) is positive-definite Therefore, the matrix K [Xx, is invertible, and Σ Ciji K (z,, 2zz)) -j== when K K[Kaaay ej. Oij is the i-th element of Oj, and
K [[X,] [K Irre =
(H.6)
(xx](x)) = (X(,,,)))...KK(((a)))
(H.7)
The following lemma allows to construct an operator that satisfies the condition in Lemma H.5.
Lemma H.6. Let H be the RKHS induced by the kernel K, where K R x Inm - IR is defined as K K(2,x') = exp(- || x' 2/112 22) Suppose X C. 1 is cube with side length 2 22/m, and
max min || x' 1'112 S 1/(3 m! exp(m22m+s ml 2))l).
XEX E'X
for the set X.. X with [aal We define u, (x) = = Oii ((i, x), where oj- = - (Xo]e Oify is the i-th element of o and the matrix K K[X,] is defined in (H.6). We also define Sx. as Sx, f(x) = Ei= f(z)), (z,()) for all f H. For operator I H. + LL(X)) where is probability measure over X. we define [[F'l [Fllz-Lg(x = Sep/E/H(O) [[T (Iffllgux [lfll
We have
S. Sx 11 I el (-aapp.1/(2))))
where Tm 4th m!, Cspp,1 1/(3mm), and So + L2(X') is defined as Sof((z) f(x))
Proof. See Appendix $H.4 for detailed proof.
Let So and Sx, be the operator defined Lemma H.6, we have I Sx. = (So - Sx.,) o Combining the definition of the norm with Lemma H.6, we have
r T-Sxx Sx, ollv=
||Til== ||So Sx, 11
(H.8)
Wtymeexpp-Capp.ii 1/1 /21)) [[llv-
Here Capp.1 1/(3mm)) Therefore, we also have
[ Iallv-1g00) I 41ym exp( C Capp. 1/mm /(2)) ||Fly
38

---

Published as a conference paper at ICLR 2023
when define r Sx, I in the that 2 (3 exp(8m 2)mm Since the rank of Sx, does not exceed n, the rank of n, does not exceed n. When n < (3 exp(8m + 2) we define I'n as (x)(() = for all X and v E V. We then have ||I'ly -25(0) = - - a. 1g- We first show that []Tily-13(e is bounded from the above by y By the reproducing property of the space H. we have
Iooligge = JUEX g ((())d(()== J.e JRex ((g, )dp(())
dd(xz)
(H.9)
for any g E H. Combining (H.9) with Cauchy-Schwarz inequality, we have
|blllge00 I [ (e (()) JOEX (g. (9.9)) 11
(H.10)
JZEX
for any g E H. when p is probability measure. By (H.10), we have
|| [
sup
|| / |olyy
sup vEV/(0)
|| ||lly -IFIlv-
(H.11)
vEV/(u)
Since -Inllvv--ga ||'lly - when define In as I [2x)) O, we have
|| - -rlllv-gg( I exp( exp(Capp.111) (Cap.. 1/m /(2)) exp( Capp. 1/m ((21) |IT [
(H.12)
by (H. Combining 12) with n S (3 exp mm + 2)m we have
[ - --Inlll--ggA & exp(mm 8/2 m + 2)/2) exp (onn 1/m /(67m)) (00/m//(6mmm))))))
[Tlv= (H.13)
since Capp,1 mm) Therefore, by combining (H.8) with (H.13), when choose
Capp.2 max 41 m, exp(m3/ 3/2/2 exp(8m + +2)/2
and Capp.3 = Capp. (2t) 1/).)m), we have (1) both Capp.2 and Capp.3 are constants that only depend on the side-length I and the dimension m, and (2) for any positive integer n, there exists an operator In : > Lg (x)) with finite rank n, such that
| - Tully S Capp.2 exp( Capp-pppppnn |[
Thus, we conclude the proof of Lemma H.5.
H.4 PROOF OF LEMMA H.6
Proof. By the definition Lemma H.6 and the reproducing property of the kernel, we have
[s(x) - [x)) = (k(x),
(x))
(H.14)
= =b())) Σ (1)
Combining (H.14) with Cauchy-Schwarz inequality, we have
[f(z) - Sx, f(x) < k(x)) - Σ (())((<)))))))))))))))))))))))) lf
Therefore, taking expectation with respect to the probability measure p. we have
(R - Sx.)) o 1o fll13(x) = |1(0)) - (x) dd(()) dp(x)
(H.15)
sup zEx
[(()) Σ (x(x))((z;)) 1| 11
The following lemma allows us to bound the term sup ||((x) En ((<x)(((z)) from the above.
39

---

Published as a conference paper at ICLR 2023
Lemma H.7. For a fix a E X, s X, f2,1= 1 C X, and a vector (u,,...,Uh)' when we define Q(u) as
we have
mingeR= Q(1) = (xx, x) (x) K 1 k( k(
Q(v) K(x,2) x) - Σ
K (zt
ΣΣ vel vu, (g (2),
:=1
K x) - 2u xxx,(())=)))))) + K[
Here the matrix K [,,, the vector (x)) are defined (H.6) and (H.7).
Proof. We conclude the proof by using simple linear algebra.
Combining (H.15) with the lemma above, we can prove Lemma H.6 by bounding the term sup inf (xx, - 2c (x),,(x) + e K[At,].
VERVER
We bound the term using tools from the approximation theory.
Lemma H.8 (Theorem 11.21 in Wendland (2004)). Suppose that X' C T is a cube with side length I, and we have maxsex ming'ex, || - z'112 S ffoor Xn = {I1...... J. We define "m = m!,, Capp.1 m3 and q (Capp.1/t), where [x] denote the maximal integer that does not exceed
Then there exists a sequence of function (2x(x) [ C²' + R such that for every p E wg (R"), have p(z) E v((x)p((;;) for all X. (2) we have Ei=1 [1,(2)) I exp( m2 (g 1))
for all E X, and (3) we have vx(x)) = 0 when || Iz l2 /mnl. Here wa (B is the set of all
polynomials in Th with total degree no higher than q.
By the lemma above, there exists sequence of function (w:) such that (1) we have
p(x) Σ vi(2)p(x.).
(H.16)
for all æ E X' and p E (R."). and (2) we have Σn= [xx(x)] s exp(2m (q + 1)) for all x E X. For fix 2o, we have p(æ zo) w (R when p(x) 2y (RT). By (H.16), we have
p(0) p(20 z0) = Σ (10)))(( -x) zo).
(H.17)
Similarly, we have p(a; - x) E , (RR) when whr) E w, (R We apply (H.16) again and have
a
(((o)))(22)P(C - 23y)
(H.18)
i=1==1
for all 2o E X and p E (R.).. Combining (H.17) with (H.18), we have
p(0) Σ (z))p(((z zo) + (x0))) 2,) =0.
(H.19)
Combining (H.19) with Lemma H.7, we have
K K(x0, 20) - k (xro))))r)) K [ S ((ro,20) p(0)
(H.20)
2 Σ (1(2)) [K;,,, [K()))(((,,
p(:; mo)] + ΣΣ (20))) (K.,, p(x; - x;;]]
for all xo E X' and p E (P.)) By the definition the kernel K, we have K(x, x²)= = k (x - x¹)
when we define kg = exp( - | /2) Therefore, by (H.20), we have
K(xo, zp) k( (xo) K - (X,,
(H.21)
(((o)ey( [ks - 2z)) plæ xr>]]
(x() (ko zu) p(u; =m>i| + (k) p(0)
+2
40

---

Published as a conference paper at ICLR 2023
for all To E X' and p (B"..) Combining (H.21) with the fact that || 2'112 S /ml when I, E X, we have
(()o k( K (X,))((,,, 2 I|, (B(0,
(H.22)
+2 - (2(()))) llks (B(0 |A:s Pl Pll2=
Here [ (m1)) s [x))). By Lemma H.8, we have E (ei(x0)) S exp exp(2mmmm (q + 1)) for all xo X. Therefore, by (H.22). we have
[[(o (rr)) K [ - (1 exp 11) So
(H.23)
for all xo E X' and p 8 (. Here Sp = liks - (B0. = supp|=ll Symi (ka(x) p(x))- Therefore, we only need bound inf (E llki p Pll,, from the above. We have p(||=12) E (B"")) when p E w Since define k, (z) exp( || 1/2 /2, by (H.23), have
(2o, K[X, (2o) T K [x1
(H.24)
< 4expp44mmmmm (q 1)) inf sup exx((=x/2) p(x)) pEFa/z(R) =E[0mml
By Taylor's Theorem (with Lagrange Remainder), we have sup m=(0
exp( (- 2/2) (x()) [m(2/2)/o/2++1/(((p/ 1)!
(H.25)
when we choose the polynomial as the Taylor polynomial of exp(-x/2) around zero of degree [g/2]. Without loss of generality, we assume ml2 > 2. Since the degree q an integer, we have
[g/2] 2 (g - 1)/2 and 2 1 when & I Capp,1. Combining (H.25) with Stirling's formula, we have
(exp(-x/2) pc(x)) S (ml² (mll222) /2/11/21+1 =E(0,m!3]
(l//2) + + S (emll /2)/1//1///////////// (1g/2]+
1
(9/2)-1
sup
s (212 exp (g + 1)/2) ((9 + 10)2)) (1+1)/2
(H.26)
We plug (H.26) into (H.24) and have
+ 1)) (0+1)/2 K (K0o, -o) k{X,,, (xo) | < 41/mmesppmmm)m + 1ymll
Since we choose [Capp.1 14]. we have + 1 2 Capp.1/1. Therefore, we have
K (2o, zu) (x)) T K [X, <41 1)mmft//appp (g+1)/2
=41/mm (3 exp(8mmm + 1) 1)mli) (0+1)/2
where the second equation is induced by the definition of Capp.1 in Lemma H.8. Therefore, when 1 < 1/(3 exp(8mm),, + 2)ml), we have
(Io, (xoo)(( T K- (X,,
< mm (1)/2)
(H.27)
Combining (H.15) with (H.27), we have
[ flleg(x) (1lree Sx.
-x Sx. Sx. dp(a) s Wt//mexp--aapp///// [|
for f E H. By the definition of the operator norm, we have
R - Sx, 1Ix = sup [| - Sx.) fllego / [1fllx S 4l/mexp(-CCap (aap-pCp..112)))
SEH/ (o)
which concludes the proof of Lemma H.6.
41

---

Published as a conference paper at ICLR 2023
1 PROOF OF LEMMAS IN APPENDIX ŞE
I.1 PROOF OF LEMMA E.5
Proof. In the following part of the proof, we condition on the events good events & and &g. First, by Lemma J.1, we decompose the difference in value as follows,
[T;; P + u", ,")) - r
(1.1)
11
Ea [B Pp as) ( ($/+2ir", ,T)] - -Es (Pp(onas) (ita PP)]] (P)]
h=1
+
Ex ju (Sh, ax) + (sh, an) rx (sh, an)).
h=1
Since the value function in (1.1) is bounded from the above by H, we have
[T; fm + uu² P") - [1;;; r", PT)
(1.2)
H
B Bn pm (sh, an)l - Σ h=1
En (sh, and
Σ h=1
Ex p= (shh,
N=1
where (s) = (- s, - P s, s))1,,, and (s. 1 an) (s ax)l. In
the following part of the proof, we bound the expectation of in (I.2) from the above. For h = 1, by the definition of Event & in (E.5) and pf, in (E.3), we have
- |A] pr. [fip(s (s, a)] s |AI LAI [R, a)) s SlAlc//n, (1.3)
when condition on Event E, Here the second inequality follows Cauchy-Schwarz inequality. By the same technique in (L3), we have
ET,p' (81, ai)] S /AlC/VT.
For h 1, we have ll S 2. Since we have (s',a') Ph.z when (s,a) Ph-I1. Pj (: 8, 8, a' =(AA), by Lemma J.2, we have
Ba (f,, an)1l S E. (9
where 8% =%=v/ v 4202 /22n +2 max |A Epp [ (s, a) + 4(2). By the definition of (E.5), we have nlEEpg (s, (s, a) s <² when condition on E,. We also have
|| an) II, | (o an)) " (r)) (eg. S 2
when condition on Event &g Lemma E.2. By the definition of Uj in (4.5), we have
Er,pn [fh, an)] S p.. [uh an / 1). By the exactly same method, have [E If (sp, an)ll S Ey [uj (sn, an)l/(H + 1). There- fore, we conclude the proof of Lemma E.5 by combing the bound above, (I.2), with (I.3).
1.2 PROOF OF LEMMA E.6
Proof. By the definition of Q in Algorithm 4 (Planning Algorithm), have (5,
QR a, >=*1,pp + u², " pP) for all (8,0) a) E S x A, and n+1 is the greedy policy with regard to Q By the definition of the value function, have
VT (s; T + w "u,P" Pm) (s) = (Q (8, + uu pa) - Qh(s, +), 1. (s)) (QR m. ./a ( 1s))
(I.4)
42

---

Published as a conference paper at ICLR 2023
Since x=+1 is the greedy policy with regard to Qh, we have (Qi )) n,
(:1 s) (-) |s)s O.
We also have Q% (s, +u", - (s, a) Pp [V h+ (s'; nd + +u". , -
Therefore, taking expectation over pm and x² in both sides of (1.4), we have
Bp",=* [V, (sx; + u", u", ,,") -77 (sa)) I E= x ( + u", ,P) - V h+1 (8h+1)]
Using induction on h, we have
Vi" (Smuu:" r" + u²," P")) (smit) I Ep [V (sH+1;r" + u", (")) - V ($ ) = 0.
Since we have V/= (Simits r +u"
, PP)) = (m";"" +u", P") and Vf J n+ + uu= Pm).
conclude the proof of Lemma E.
1.3 PROOF OF LEMMA E.7
Proof. The following lemma shows that the value function defined by the estimated model is bounded from the above by the value function defined by the true model.
Lemma I.1 (Bounded optimistism Each Iteration). Following the same condition with Theorem 5.3, when condition on the good events E1 and Ez. which are defined in (E.5), (E.6) and (E.7), have
J(xr"" + +u" + , J(T; + +u" "u","") 2 + 3H + 1111A////n
for any policy n, where the bonus u" = {uh l==1 is defined in Lemma E.5. Here the underlying bonus u² = {un, "
Th=1 is defined as
un "h (s, a) = min 4H² 6H + 2, (6 an)) Ilr, 20
where B1 = (4H2 - 6H 2) 4xv2/2 min + 4r max
A ( and B is defined in Lemma E.5.
Proof. See Appendix $1.4 for detailed proof.
By Lemma I.1, and the definition of the expected total reward, we have
N
[J(
u", ,uuPP' pn) - +1 ;r"
;r","")) PP)]
(1.5)
N Σ 22H² + 3H 3 11)LAI//V + Σ
N
uuma pP)
1=1
n=1
However, the bonus defined by the learned feature might vary in each episode, which make it difficult to bound from the above. The following lemma connects the bonus defined by the learned feature with the bonus defined by the true feature.
Lemma I.2 (Bonus Equivalence for the True Model). Following the same condition with Theorem 5.3, when condition on εr and Eg, which are defined in (E.5), (E.6), and (E.7), we have
[[z; n", ,P") $2 [A] Ba //n J[r; ,P")
for any policy a and n 2 2, where the bonus n [w] hh= is defined in Lemma E.5 and the *,n, m
underlying bonus u = [u,, Th=1 is defined in Lemma 1.1.
Proof. See Appendix $1.5 for a detailed proof.
Combining (I.5) with Lemma I.2, we have
N
[(T": nd + tu", p²) - J P*)]
(I.6)
N (2H² + 3H + 1) |/|// + Σ 2| 3d //////+22 E
N
N
n=1
n=1
n=1
N
< 2 |A| SV Ne +
[( [ p
43

---

Published as a conference paper at ICLR 2023
Therefore, it remains to bound Smitt u""", P.). Since the bonus un" are bounded by 4H² 6H + 2, it is a 12H2-subGaussinnn random variable. Therefore, by Hoeffding 's inequality and the definition of the value function, we have
H
Σ J( n=1
p')
u tn pT)
B pp- [uli (8h, an)]
(1.7)
h= n=
N "n
121f2 1og(10H/08)N
($%,0 %
with probability at least 5/10. Combining the definition of the underlying bonus in Lemma with Cauchy-Setie Schwarz inequality, we have
H
N
"k
n.n
(5,,0 , 22,0
3
M . oxtt))
(I.8)
A=1n=
1=1
n=1
H
N
3B V
(0 . (gpt'))))
For simplicity, we define 2i = (s (h
K
[K( 2x ) 7= and
ky (K(ah; 2/ m+11. ....),................ K K( 2h ))
By Lemma D.3, we have
($ n+1 : 20,0 r. 10z, DK,
a+1))
|
(K (K(2) a+ ,'h 1x, > - kn
,xxht1)
TO.T(aL (AI + KE))
We also define dx = (K(*,* n+
2hh 1xtt1) ) -k7,
kn.T
(AI + Tm.
(g)))1()/+ We then have
I /
kn/>
det(I + Khtt /A) = det
1 (xxh" n+l ,xht ))x))//)
kh /A
det ( bt
9) det
(I+ Kn/X
0
det (1
b
= det(T + Ky/A)(1 + ai))
1 an
1
where b- (\I + KH) -1 lep. We also have dj S 1. Since S Eeoog(1 +x) when S 1, we have
o S Selog(T + KT /A) - e log(T + /A) and ΣN aj S e log + N-N+ 1/11// S edef by the
definition of den in Definition E.4. Therefore, by (L.8), we have Σ En Up (5h.0 4,0 B. VeNden Combining (I.6) with (I.7), we have
+.a a+1 n+1 S
Σ [J(=": u", pm) rr" P')]
32H AA No + 12H
+ 3,H1 V eeN
< 2 [A| Ç3 / des log(0HH/0))
which concludes the proof of Lemma E.7.
I.4 PROOF OF LEMMA 1.1
Proof. In the following part of the proof, we condition on E, and Ez. First, by Lemma J.1, decompose the difference in value as follows,
J(r;"" + n" + un ","" [x;; + uu,,"" Pr)
(I.9)
11
Eo 1a V (s/m1: + +u" "ump"") Es, P [ (sh pr + un, pp)]
1=1
Ex Ex [uh *. (sh, ax) + (7 an) (sh, an)].
1=1
44

---

Published as a conference paper at ICLR 2023
Since 1 + un loo - (2H + 3). the value function in (L.9) is bounded from the above, and we have [x;r" + u² + +u nnnn."" ,P") - J [T;; F
+ ,
(I.10)
p. [un" (sh, (sh, am)] h=1
ΣE'TE Fr [S [n)) h=1
Σ T [2H 3H) 3H) p an)] h=1
where (s, a) (1 s, - P I s, a)]l and (s. (s) 0n) (sh, as are
defined for simplicity. In the following part of the proof, we bound the expectation of f in (I.10) from the above. For h = 1, by the definition of Event & in (E.5) and pf;1 in (E.3), we have
Ex (s,, E,, (s,) S |A| V EE, (f. s /A/C/Vá (L.II)
when condition on & Here the second inequality follows Cauchy-Schwarz inequality, By the same technique in (I.11), we have
ET [s1, S LAIC/VT.
For h > 1, we have Ilfr, I 2. Since (s',d) ~ Ph,1 when (8, a) ~ Ph-1,018 o ~ Ph-Il |
8, a)) a' ~ ((A), by Lemma J.3, we have
Br.p- (fhe-sffnssssaas an)) S 'M [|A(0)-_(shh-1) an- 1), 1). 107 18 100 Loodm (1.12)
where 3y v /202//2m muax 11 (Al Bien, [nn, an) By the definition of & in (E.5), we have ni and Pr [/n )m < <²² when & holds. We also have
(M an) I|r 1oz (0
S 2 (0) (sh, an)) (n)))lrr" (e,
when condition on Event Eg defined in (E.6), (E.7). By the definition of uj in Lemma I.1 and (I.12), we have
E. [fh,e($h, an)]] S Er,p- [u (8h (8h-1,ah-1)) (h-1)) (1)1)) +3H + 1).
By the same method, we have |E,, [fn (s,, [n)]l Ey [u (hh-1,0h-1)]/(22) + +3H 1). Therefore, we conclude the proof of Lemma 1.1 by combing the bound above, (1.10), with (I.11). L
I.5 PROOF OF LEMMA I.2
Proof. In the following part of the proof, we condition on the good events & and &g defined in (E.5),
(E.6), and (E.7). By the definition of the value function, we have
HT; E, [u] (Sinit an))
Σ Er, p- (sh,
(I.13)
Term (a)
Term (b)
Now we bound the terms in (I.13) from the above separately.
Term (a). By the definition of př, in (E.3), Algorithm (Sampling Scheme), and Cauchy-Schward inequality, we have
Ex [u] (Sinit: on)] < [A] E,g, (s, a)] < Ml Epr, [ a))
(I.14)
By the definition of wh in (4.5) and der in Definition E.4, when Event &g defined in Lemma E.2 holds, we have
Epg, (1][s,,))) < [ a))ssa)))))) 102 (
< <48 ph
[|K(08(s, a)) 1) S deannn
45

---

Published as a conference paper at ICLR 2023
Therefore, by (1.14), have Ex (Sinit, a1)] s 2|A| 3d /Vn.
Term (b). By the definition of uh in Lemma E.5, we have || I 2H By the definition of p% and Ph in (E.3), we have (s',a') a') ~ Ph., when (s, a) ~ Ph-1,0 ~ Ph-i(- 8, a), d' ~ U(A).
Therefore, by Lemma J.3, when we condition on Event Eg defined in Lemma E.2, we have
E Eg (uh an))
S 50p S. ET
107, 10 Am) [| (n-1)) ||rs"
(1.15)
[||( $25h ER,
ah "ei- 18th (sh (8h- (
Iog - P
where "/= = 4X(H + 1))u2////0 /cmin max n |A| Epr [u] a)?].
By the definition of uj, in (4.5),
and deft in Definition E.4, when condition Event &g defined in Lemma E.2, we have
PF. (s, a) s B pr.,
()) (oR.
S 2 PK (I) 1o S 2 dat/n.
Therefore, we have 31 2 2.% where 31 is defined in Lemma 1.1. By (I.15) and the definition of un (5h-1, a)) in Lemma I.1, we have Ex [u]] (hh: an)l Bx [ (sh-1, a2-1)]
We conclude the proof of Lemma 1.2 by combining the bound on Term (a) and Term (b).
J PROOF OF AUXILIARY LEMMAS
J.1 PROOF OF LEMMA J.1
In this subsection, we provide the proof of the simulation lemma. We first state it below.
Lemma J.1 (Simulation Lemma). Let (s; P,T) be the value function defined in (2.1). For the transition kernels P = {PP P = ={P) and the reward functions r = {rr 1 we have
H1
(8,r + P, - V/ (s;r, = Σ
EAP (uz (8)
a5)
s]
h=
H
+
Σ h=h
Eg. Eg Vit h+1
(it,, P*]] - E,2 Vir (6 P')] sh = s].
where [- = -Be Palnnn and B2,l(:] = PPinna Here B,, is the expectation taken over the trajectory induced by the policy π = { Mi and the transition kernel P.
Proof. By the definition of (s, P, π) in (2.1), have
(s; u,P) Vi P*) V (s; Vo (s;r, (s;r,,
(J.1)
Exp pupluun(shr00 an) sh. s] (T (s,,,
Here Ky,, is the expectation taken over the trajectory induced by policy x and the transition kernel P. By the definition of the value function Vs,,,,, P, TT) in (2.1), we have
V (oh
true
rr, P) = E,,P [r an) + h+ (8h41i1; 8 sh
(
(J.2)
Σ ( aa mue Ex V ($t+1iT, P) s%
=sh
a
By (J.2), we have
V. (s Inue
r, r,P) V (stree; ;r, P*)
(I.3)
= Er, VV h+1 (SH=1iT, P) 8% =
sh
mue
E.,p- [V2r Wh (8541i7, P*) |
ss true
46

---

Published as a conference paper at ICLR 2023
Combining the property of the expectation with (I.3), we have
V. (sh r. P) V. (s r, PT) En, (
(5 iir, P) V (s P.)) )²] 5%
sh
E [ ii PT) 8% = [ - p. | (8h+1i PT)) 8% = %%= (I.4)
Taking expectation in both sides of (J.4) and summing it up from = to H, we have
Vi (s:r, P) (s;r,
(J.5)
Σ Br,P BI,1 (5% P")] E2,4 ( ( =
k=h
where Ei,ll:] Es Ph (sn H and E P We conclude the proof of
Lemma J.1 by combining (J.1) with (J.5).
J.2 PROOF OF LEMMA J.2
In this subsection, provide the proof of the one-step backward inequality for the learned model. We first state this lemma below.
Lemma J.2 (One-Step Backward for the Learned Model). Let Ph-1 be distribution over A. We assume that the transition kernels pm {PP) and P (Pt, ki satisfy
( 8, (k( a)) A (1 (6)) H// d0% 1/ (h++)(ss,)) and (s s,a) (k(67 a)) k ( (s / cl0%, (h+1l(s,
where clØ, (sss a) is the normalization function defined in (E.1) and t: X H. is the feature map of the RKHS H. We assume further that nil (s.)(s.))> (TV (P 8, a), Ph (. 8,a))] < 6
and the non-negative function g satisfies ||g| I B. For any policy n, we have
(t..=(9($5, an)] S Er,ppn 33 (90 0n-1)) 1)- (oR_ Am
Here the operator pploh 1h-11 ph-1:1., X, n) is defined in (E.4), E, is the expectation taken over the trajectory induced by the policy т (Tn) and the transition kernel P, is defined
2r (n [r|A| ..PHUAA) [s22 + Be(²): Br = V AB2 /22 min
and the expectation Epy PA (ca)laa an)) is defined as
E Pp PR [g(s an]] (ss 1.94 PPp 1.th. (L an)]
Proof. By the structure of the transition and the property of conditional expectation, have
Ex [g(s,, ((sn,an))] aw)]
(J.6)
(f (h 1/-11 (/-11:0-11) Σ (a s)g(s, a)ds
Eg.pn
aEA
= Er,pa Use
1 mn (
where the last equation follows from the structure Pip and g(8, π) is defined as
g(s IT) = Σ aaa| ())
(J.7)
acA
Combining (1.6) with the lower bound of the normalization constant, we have
Ex, pm [g(5n, an)] En.p' [/[
Tn mn)ds /miaa
(J.8)
47

---

Published as a conference paper at ICLR 2023
For bounded function 9. define the functional x(v% n. g) H RR
x gig' I (d (d.
E Ta(a s)g(s,
(I.9)
H acAA
The functional x(v> n, is linear. Moreover, for any g' H. we have
[x(1% n. gl6 < f Joes 119' (1((
Σ
Ta(al s)
(I.10)
aEA
/ JOES 11o'l1x Bds Be 1l
$
where v the Lebesgue measure of S. Therefore, x T, g) is bounded by Bv. By Riesz theorem, there exists element uly/% n, g] E H with || jush T, 1ill S Bu, such that x n, glg (u(w), n, "..'"'"" gh for any o' E H. Therefore, by (J.8) and Cauchy-Schwarz inequality, we have
Ex Ex lg an)) s Bx.pn [K (ulvy
(90--(((9-1 H
/Cminn
(J.11)
< EE || (1%/0%%111) 1 an-))) (1,,) 10r 1:g i. || ग, 9e olllr,,o% pol 1:8 Am) /min
where I | Ph ri] is defined in (E.4), and Cmin is the lower bound of the normalization constant cl 2 (sh-1, 1). What remains is to bound the term ||u[./. n, E,ggll,,,,, 1el.rlrrrr...._.. PR--1-1 from the above. By the definition p Ph A, n)., we have
|| n, 2 s111 Aml =X AVllu[yn ول 11 + nB I [W n., g
<XBav2
v. nL o (
(J.12)
Since u(t n, g] is the representation of x( म. defined in (J.9), we have
ulvi g. (0% a)) = =ulvE x, N.g). ( (s,a)))
(J.13)
Σ mnld' (s')g(s', d')ds'
J.es
H a'EA
Combining (J.13) with the structure of the transition kernel P Ph1 in Lemma J.2, we have
ulva n, ( cook11 WNI(s, a)
Ph- ss,a)
Σ
mn 8 "op(s',a'dd
SES
a'EA
S Cmax Earap_ ((aa)) lo(s d')l
(J.14)
since cioii1: (7) is bounded from the above by Cmax. By the property of the sum of squares.
we have
Ey PEy 1o('','')² dd)]² 52 (leo) =n [p(s',a'} d')]
(ll,))) [o(s', ( a'))
}}}
+ 2B ( [o(s',d']]
(J.15)
By simple calculation, we have
EgrnPi (-b.,))) [g(5',a') -Egrpp [9(5', a')
(J.16)
/ Ph s, - -Prii(s' s,
Σ Aala' s')g(s', d''ds's
a'EA
< B- TV(PR_ 8, .), PA (-
where the last inequality follows from the definition of the total variance divergence. Combining (J.14), (J.15) with (J.16), we have
u ulyi n, g.9] (8h a))² (00h11+]]( a
[o(s',a')) (s,)), Pi ( a.)))
(J.17)
< 2c EvApp (( (')) B2TV2 (11,,,),
48

---

Published as a conference paper at ICLR 2023
We plug (J.17) into (J.12) and have
111%% gl ro n 1.Ph ind
AB=x² (n.B(s c Bunn (1a))) l0(s' a')]²
+ 2n 2nB (3, max
TV2 8, s, Pk- 8.
(J.18)
Therefore, when n. (s,) (PV2 8, Ph-)),Ph-1 Ph-1( (,,
s, [, 5 holds, we have
||lla n, n,99 1 AB + 20 maxx
nnp P. m. (s' + B²5 (I.19)
by (1.18). Here the expectation is defined in Lemma J.2. By the definition of (AA, have [g (s', a')] = |A| pr PP (s (s',a')}
(I.20)
Combining (J.11), (I.19) with (I.20), we have S.
Ex, Px [g(s,, an)]
s [1lkk(o [ (, P [mm)
Here the expectation and 3 are defined in Lemma J.2. Thus, we conclude the proof of Lemma J.2.
J.3 PROOF OF LEMMA J.3
In this subsection, provide the proof of the one-step backward inequality for the true model. We first state this lemma below.
Lemma J.3 (One-Step Backward for the True Model). Let Ph-1 be a distribution over S x A. We assume that for the transition kernel P = (PA and the transition kernel P = [Pr with
/// PR(6' a, (k(0 a)) k ((h++((6))) / clo% (8+,)(
and (& 8, (1 a)) : (1 (s')) 2// /cl0 (h+1)(s,
We also assume that the non-negative finction g satisfies || S B. Then for any policy x, we have
Se.p;lo(<s, am)] < Ex 10 an 101_110 1h - Here the expectation ppp_ Pr, the operator T Ph X, n| is the operator defined in (E.4), and 33 is defined as
an)] is defined as ((A) (g(s
(s [m)] (s 1)0 ~ (- - [g(sn, an)],
Bi v /BB202/22 2 + P |A B M(A) [g an)].
Proof. The proof is similar with the proof of Lemma J.2. Similar with (J.8), we have
vi Ex,p- (((sh.an)] < Ea,p [.[ K (1))) ( mn)ds / Caiin (J.21)
where g(s, n.) is defined in (J.7). By (J.10), the the linear functional x/v J. defined in (J.9) is bounded by Bv. Here is the Lebesgue measure of S. By Riesz's theorem, there exists an element Lbbg. :, g] H with ||u[y, n. glll I Bv, such that x( n, glg (ulvg. म, gl o' holds for all g6 E H. Combining this property with (J.21), we have
En.p; [g(s), an)l & Ex.p: KK Kulen v, 9l. k (0 (Sn- ah 11) H // Cuuin
(J.22)
x Ex.pg [ ( (sn-1,91-2)))
9ill 10l1,,10,-10 19 - /Cmin
49

---

Published as a conference paper at ICLR 2023
Here 1h is defined in (E.4), and Cmin is the lower bound of the normalization constant cl0h-1 1/7 (8h-1, 00-1) By the definition of the operator we have
|u(0% n, wel. 1r [An) => Al/ n, 9 | + nl [ [n n, (0
SXB20² nB u² 0
(I.23)
Similar with (I.14), we have
u(1% n. N. (s. We plug (I.24) into (J.23) and have
((00))
[ [g(s'
(I.24)
| n, olll
SXB20² + ncmax TimaxB(a,a)aa B(o.a) Eg (BspPt(le [9(5', a')?²
<XB20² nc Bog (-la..)) [o" (s',a')) a')]:
(J.25)
where the last inequality follows from Cauchy-Schwanl inequality. Since 8² is non-negative, we have Epg_, Pll,,,)) (sn,,, an)] _ |A] E Ph.l,, (9 (sh, an)]-
(J.26)
Here Bpp_,: ( (/h, ax) Bssn-110, 1 Sp. (1 (4 ian i)aa ~ (15)) lg an)). Com-
bining (J.22), (J.25) and (J.26), we have
E Px [g(*)= []]] S Px (Bx ( -ل-1)) 1 .mmm)
where Be is defined in Lemma J.3. Thus, we conclude the proof of Lemma J.3.
J.4 PROOF OF LEMMA C.7
Proof. The lower bound the c-Eluder dimension has been proven by Theorem 5.2 of Dong et al. (2021). Therefore, only need to bound the e-log covering number of R. from the above. Let Ci be an e e/2-covering set of the unit sphere in Ik",, and C2 be an e/2-covering set of [0, 1]. We have [c,] 2 and |C1 S 2/c. We define the set
C {ra.s : A + R (r,s(a)) = (0 a + b), e Cı, E C2}.
For any re, R, there exists 0g e C1 and by E C2, such that ||0 B0ll2 S e and |b bul S e/2.. We have to E C. and
(ra,(0)) ro (a)l max (T a + 6,00 max (0) a bo. 03+1
(J.27)
0 00l12 |all| + dul Sc
for any E A. Therefore, C is an e-coerring set of R. and
log |C| < log C1 + log [C2| S (d + 1)) 1+)))og(44)) log(4/)), which concludes the proof of Lemma C.7.
J.5 PROOF OF LEMMA D.2
Proof. By the reproducing property of H and J ((())))())= = / ((6, (g. - / (g, ( x)dp(x) g)x
inequality, we have
(J.28)
when g H. Therefore, we have H c 12(X) and |I Lallzgeo $ 1 We also have
[T(=)) 1 I/ ((dd
dp(x)
(J.29)
x [/ K2 (K2
1 0263"" "(*")d((=")) dp(z)
Up o (a"))a((o") / (o
/ 1 (a"")d((e""
50

---

Published as a conference paper at ICLR 2023
z'112 Where the last equation holds since ((x, 2') -xp(-1|=-z'11/ 21../2))eerrfore we have Ig (2)) when g E (2)) which implies that I is a linear operator on (2)) When we define the functional "ig H R ig = (()))())) for (2))),
have
7g(0)= - S g (()))o()))/ / / ((())do()) Vl..9 (((x)dp(z)
by (J.28) and (J.29). Therefore, by Riesz's theorem, we know that there exists H. such that (u, n. ()), which implies. [g(z) E H. The operator r H. - H is also non-negative definite since we have (g. rg = Sx g 2 when E H. Thus, we conclude the proof of Lemma D.2.
J.6 PROOF OF LEMMA D.3
Proof. We first define the operator [[x]] as
[[X))o(x) (9(x) [(x) (AT K(X,)) ((X8,))'(((Ax))) (xx,)(()) /v,
(J.30)
for any H. E X. Here g(Xr,] is defined in $1.2. We show that r[2,,] is the inverse of [[X,]. By the definition of r[X,] in Lemma D.3, we have (T[ = (>I [[Xx1)9(Xx]] and
[1x))1(()) = Ag(z) + (<),
(J.31)
where k (x))(x)) is defined in Lemma D.3. Combining Equaitions (J.30) with (I.31), we have
F[ T(x,)))))))(>)) (T(x,11(1))
((( /> g(x).
= (Ag(x) + -,
By the definition in (J.30) and the definition of (I(x)]g)(<<,) in $1.2. we have
(F(*)]9) [X.] = [g[X,] K[ K(Xx,) - 91 ((xm)) / />= (AT k(X,,) -t)))))))) "[[u]] (J.32) Combining (J.32) with (I.30), we have
(1(8.19) (z) xf(xx,9(=x) (1)
= =g(x) x,x,'''' (AI + [
(Ar + K(X,)) "x(X,(()) = g(x).
Therefore, the operator [x,, is the inverse operator of [. and
||<())]]====.. = =,<=),,11111__1)) (x,]]<=)
(( (MM+ (
(b(Xu((o))/ /A.
Thus, we conclude the proof of Lemma D.3.
J.7 PROOF OF LEMMA D.4
Proof. By the definition of the operator TelØ, D,A], A), we have
(o D. Alg); >Ag. g/u + Σ g(6(s,a)))
(J.33)
(s.a.r,)")D
Therefore, have Mgg g|u < (g. Talo D, Ag'n. By the definition of the reproducing kernel, have Eeean g( a) E Eeaonn))e k(o(s, a)) Therefore, we have
Σ g()(s,))) < (9.9)n
Σ
(()(s,a).((s.)
(J.34)
(s.a.r."))D
(s.0.r.9))D
by Cauchy-Schin Schwarz inequality. Combining (J.33) with (J.34), we have Te(o, D, A1g)x S (A+
Σ (B)D.),e)ED
K ((b(s,)) ((. ((..)) (g,
Similarly, by the definition of the operator pp(0,, P, X, T). have
(g. rp A, F|9) = Mgg, g) + 7 TB( [3 a)) Therefore, we have X(g. g)H S (g. T 10. p. >,),)) H Similar with (J.34), we have B( [ (1)) < (g, g) E (s.0)~ [K(0ss a), (0, ())
(J.35)
(J.36)
We conclude the proof of Lemma D.4 by combining (I.35) with (J.36).
n
51

---

Published as a conference paper at ICLR 2023
J.8 PROOF OF LEMMA F.2
Proof.
Since the operators A, B are self-adjoint and positive-definite, the operator 1-1/22A' AB-1/2 also self-adjoint and positive-defintt. Therefore, the operator C = (B (B-1/2AE 1/2)1/2 is also
self-adjoint and positive-definite Since 1--/2C-1 E D, we have
(B-1 ",,_,,""""""0B""11110
(B-1/2C-1--12 AB -
by the definition of D Lemma F.2. Since the operators B and are self-adjoint, we have
(J.37)
Bx BB 1/
(z. B- C- B-2/ax)
We also have = 1 when C (B- AB 1/2 Therefore, we have (1-10"--b=-173__1--------1111111 1/ A 12
(J.38)
= 1
by (I.37). Similarly, we have
<1-11"--11-112a,000-""""--0-1111 1/g 112 B- 1/2 20
B
= - = =z, B z)
(J.39)
We conclude the proof of Lemma F.2 by combining (J.38) with (I.39).
J.9 PROOF OF LEMMA F.3
Proof. Without loss of generality, we assume that (g. 90 = We then have
g(z) = (g. k(x)) S // V/6o (9.9)) g)n (()x))())) =
for any x E X. We also introduce the following version of Bernstein inequality.
Lemma J.4. Let [F be a filtration. and {X, ) 7=11 be R-valued stochastic process adapted to this filtration. Suppose E[X, [ = 0 and [ < с almost surely, we have
X, S (e 2) F F+-1] + log(L/6)/A) 2 21-8
for any fix 0 < 1/c
Proof. See Appendix $1.12 for detailed proof.
Since Ble,a)orr 1 (0(8, [)) Bigg( Fr-1), using Lemma J.4 with À 1/2, we have
Σ 9 (o(s" ,a))))) - Σ Blaaaver [
(J.40)
< (e - 2) Σ Var (g((() ;a,))aa))))) (F-1) llg((1
holds with probability at least - 5. By the property of the variance, we have
Var Var(9 (9((6(") "osss,a"))) aa)) [ < , Fr-1] s ( [r (J.41)
Combining (J.40) with (J.41), we have
Σ 3 (o(s" ,a)) s > E (0(s" aa)) Fr-1) //2 +2log(1/0)(g.)))
52

---

Published as a conference paper at ICLR 2023
holds with probability at least 1 - 6. Similarly, we have
- Σ
[o((o(s',a))
n
(e- 2) Σ
E 0 (0(5", , aa")) | //2 1og(1/0))
holds with probability at least 1 - 6. By simple calculation, we have
(4 - e EE .a²)) Fr- 22 (o6 a²)) +
holds with probability at least 1 - 6. Thus, we conclude the proof of Lemma E33
J.10 PROOF OF LEMMA F.4
Proof. By the definition of I' in (F.1), we have I'y 11-=111/0 1/2 (/111/3/1111 T2111/1 1/3-//11 Since the operator 1/2 is self-adjoint, we have
1/2
(Tg. rg)h = (TT -11 g.
(TT -
1/2 9)
(J.42)
By Lemma D.4, we have (91, 1 91) n S (91.91)m4 /// for any 91 E H. Therefore, have
(Tg, [g 1 (TT T2 1/2/ 1 1/2 9, (T)
1/2 r 1/3 1/2 1/9)) ))),x)
1
(J.43)
1/2 9,
(TT
1/2 T2r
1/2
- 1/2 /2.
74
The following lemma characterize the operator r 1/2 1 1/2
Lemma J.5. When we define I' r'llo, ph, n2] and I'2 -eelo, Ph,; A1, we have
Mg. () h/(1 + +n) S (g., - 1/2 r2 1/2 9//²)²x²² S (A (A+ ())
for any g E H. Similarly we have
(T Mg. 9) h/ (A n) (T. #
<A++n)o.
Here pplo Ph. X, n] and I [o Di, >) are defined in (E.2) and (E.4).
Proof. See Appendix $J.13 for a detailed proof.
Combining Lemma J.5 with (J.43), we have
(gg, S(A m) (T] 1/2 9, 1/-1/12.)) 9/ (A o)
By Lemma D.4, we have (91, IT 91 S (91.91) for any 91 E H. Therefore, we have
(Tg, [gg) R S (A + n) 9//2
Similarly, by Lemma D.4, we have (g), r 91 / 2 (g1.9)) H//////// (2 + n) for any In E H. Therefore, by (J.42), we have
19) (TT 1/2 T 1/2) 1/2 1/2 9, (TT 1/211/1112 - 1/2 1/2 1/2 120)))///0/// / (J.44)
[ 1/2 9, (T 1 1 1/2 9),, H
/ (x+m).
Combining Lemma J.5 with (J.44), have
g/ n)². (Tg, Tg) 2A 1/2 g, r 1/2 g/H +)² = >(g, NT
By Proposition D.4, we have (91. 1 91 (01,914// //(1////1)/ + n) for any I1 H. Therefore, have
(g) 2 M(g, T 9) 2/ /1 n)3
Thus, conclude the proof of Lemma F.4
53

---

Published as a conference paper at ICLR 2023
J.11 PROOF OF LEMMA F.5
Proof. We denote by C the E-covering of the unit ball in m dimension, and define C' by C² (T,(x,)) x E C). In the following part of the proof, we show that C' is a v(A+n)22 covering of H1 with regard the infinity norm.
For any 9 E Hi, we have g(-) = [x, :) for some r in the unit ball. By the definition of the set C, there exist x' E such that |a - x'1l S é. By the reproducing property of the kernel, we have
[T( - M (x', w) (T(K(()) - k(z')). k(v))
(J.45)
for any y E R".. Combining (J.45) with Cauchy-Schwarn inequality, we have
[K(2, v) - TK(2', v) = v (T(K(z) - ((ko)) -
), (k(V). (J.46)
- x(x')) -M()
- (k(t))))))) )m
for any y R". where the second equation follows from the fact that (k()), k(y)) = 1. By Lemma F.,, we have (Ig1, fgi) I (A + n) (g1. 91)/ for any 91 E H. Therefore, by (J.46). we have
[K(x, v) [K v\ s / m) - k(x²), k(x) - k(x'){ H
A3
(J.47)
Similar with (F.7), we have (A(z) - k(2)),)))))))))))) k(z) k(x')) S e² when || 2' S. By (I.47),
we have [x; y) [K y) - V(2 + n)²//13 Therefore, C' is a of 7/1 with regard to the infinity norm. We also have |C|| |C| s (R/z)m. We conclude the proof of Lemma F.5 by setting غ eA 2// nn).
J.12 PROOF OF LEMMA J.4
Proof. Since ex $1+1+ x (e 2)x² holds for any x S 1, we have
E | | s E[ + Xx, + (e - 2)x2X² x² Fイ-1] = B[1+[[+([] (e (2)))xxx Fr-1]
S exp exp E[(e
- x) Fイ
when À < 1/cc. Therefore, when we define Y, = exp ( Σ X2 - (e-2)) > we have E F(-1] S [Y 11. Using induction, we have R[(Y,) S Therefore, we have
-== E Fイ11}}
Σ X, (c- 2) Σ
B[X Fr-1l + log(1/5)/A) 2 1- 5
by Markov inequality. Thus, we conclude the proof of Lemma J.4.
J.13 PROOF OF LEMMA J.5
Proof. By the property of the inverse operator, it remains to prove that
+ n) < (g. (,, 9)H S (A+ g/n/A for any g E H. By Lemma D.4, we have (g), (291)x - (A n) 91) Therefore, we have
(g,17 1 1/2 g)x = (r 1/2
g. 121, 1/2 g)H S 1n+)(TT7// 1/2 g. 1 1/2 g)n.
By Lemma D.4, we have (91, ( f1 < (1..9))// for any I1 E H. Therefore, we have
(g. D. 1/2 1. - 1/2 g)H <
< (A+ ().9)/AA.
Similarly, by Lemma D.4, we have (g). 22 2 N91,91) H. Therefore, we have
rg 1/2 r2r 1/2 9)H (TT 1/2 g, 12 1/2 g)H 2 > 1/2 1/2 g)x
1
By Lemma D.4, we have (01, I 91 2 (0. /// (A n) for any E H. Therefore, we have
(g. / 9)H 2 X/g, T g)H Ngg.g (A + n))
Thus, we conclude the proof of Lemma J.5.
54


Reviews:
[{"review_id": "q2F4DlwP62", "reviewer": "Reviewer_rz87", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 analyses a method for learning transition and reward dynamics in MDPs.  They show that a more generally parameterised MDP can be solved efficiently.  No empirical results are presented, but extensive theoretical analyses are.  \n", "summary_of_the_review": "Since I cannot faithfully comment on the full theoretical extent of the work, but the content that I have analysed is good, I will rate this paper as a weak accept.  \n", "strength_and_weaknesses": "This is an **intensely** theoretical paper, in a domain that I am not overly familiar with.  While I have an understanding of the high-level findings, I did not and cannot faithfully review the derivations in the supplement (which is over 40 pages long).  \n\nThis paper is really in two parts: there is the high-level algorithm and result (that an MDP with NN link functions can be handled efficiently), and a long sequence of incredibly low-level results proving out the theory that underpins this algorithm.  I think there is merit in this paper for both audiences at ICLR:  a high-level audience which will benefit from the formalism, discussion of MDPs and the final result, and a low-level audience that will enjoy the theoretical analysis.  \n\n## Strengths\n1.  The paper does an excellent job of defining the core RL terms and formalism.\n2.  The core idea is appealing, and provides a good generalisation of existing ideas.\n3.  The authors appear to have done an incredibly thorough job of theoretically analysing the topic.  \n4.  Although a bit too theoretically and technically heavy for my liking, the material that is there is presented exceptionally well, with basically no typos, typographical errors or grammatical errors.\n\n## Weaknesses\n\n### Challenging presentation.\nThe intensity of theoretical analysis is also a weakness.  While the core claims seem reasonable, I don’t believe many, if any, readers (or reviewers!) will review the supplementary material.  While the authors are to be commended for the depth of their theoretical analysis, they must do a better job in breaking down the analysis and making it more accessible for the average reader.  Sketch proofs are the main way of doing this.  \n\nSome of the theoretical material and nuanced comparison could be dropped to the supplement and replaced with higher-level summaries to expand the target audience of the paper.  \n\n### Methodological Comments\nI understand that assuming oracles is common in RL analysis (because the alternative is realistically intractable to analyse), but I would like to see some comment on what the impact of not being able to use an oracle in practice is.  \n\nBuilding on this, I would like the authors to confirm that my evaluation of their method is correct:  You essentially rollout under the current policy, and then take two steps from a uniform policy.  This uniform sampling increases the diversity, but degrades the sampling efficiency.  I am struggling to see the relevance of exactly two steps under a uniform policy, after rolling out for P steps.  Is there not a more principled way of doing this?  Eg. rolling out under a policy with an entropy increase (adding uniform at each timestep, increasing the variance)?  Why is exactly two additional steps the best option?\n\nThen, the “method” is using an oracle to “solve” for the transition and reward functions from a very expressive variational family using these extra two steps.  Why do you use just the extra two steps?  Isn’t it more sample efficient to use the whole trajectory?  Does using just the final two steps bias the function estimator to be biased towards the regions of state space with a high occupancy at the *end* of the trajectory? \n\nThen the remaining analysis is showing that the approximation error is bounded with a tractable complexity?  One thing that I don’t understand is the “exploration bonus”.  This exploration bonus modifies the policy that is currently held, and so does this bonus go to zero during optimization, so that the final policy is “purely exploit”?  The policy learning is also done exactly through using the planning algorithm in the appendix?  Does this algorithm impose any further constraints on the space?  Does inaccuracies in the planning algorithm lead to pathological failures in the algorithm?  \n\n\n### Empirical Validation\nI acknowledge that ICLR has a strong purely theoretical remit.  However, for an algorithm as practically motivated and generally applicable as this, I would have liked to have seen at least a toy example.  This is partly to “validate” the theory, but also to help the reader understand the different facets of the algorithm.  While this is not a requirement for my response, I implore the authors to at least explore applying this to an LQR, an in-built MuJoCo example, even something like mountain cart.  This would help the reader a lot, and would further increase the reach and impact of the paper.  \n\n\n## Minor Weaknesses / Typographical Comments\n\n(a)  Advanced concepts such as covering number and Eluder number are completely undefined (although maybe there is little in this paper for anyone that doesn’t already understand those terms).  \n\n(b)  The bold-facing of fonts is unnecessary.  \n\n(c)  Are the terms in the norm in (3.4) reversed compared to the preceding and next equation?  It would probably be clearer if they were the same way around in each expression.  \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": "Not applicable"}, "extra_text": {}}, {"review_id": "ay6DuQhFTl4", "reviewer": "Reviewer_DNrX", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 paper aims at building \"novel algorithm that designs exploration incentives via learnable representations of the dynamics model by embedding the neural dynamics into a kernel space induced by the system noise.\"", "summary_of_the_review": "The paper is not clear", "strength_and_weaknesses": "Strength:\nThe aim of the paper seems ambitious and interesting\n\nWeaknesses:\nThe paper is not clear", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "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": "Wi16YGRrGK", "reviewer": "Reviewer_UMwu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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 studies the exploration problem for MDPs with transition kernel captured by general function classes with bounded covering number. The transition dynamics is assumed to be a low-rank Gaussian RBF kernel with unknown features of states and actions, which captures both linear MDPs and a number of neural nets as special cases. It proposes an exploration algorithm named ELNF that has provable sublinear sample complexity to find a near-optimal policy. The sample complexity is guaranteed to depend only on the covering number instead of the Eluder dimension, which is shown to be exponentially large even for two-layer neural nets.\n", "summary_of_the_review": "This is a good paper studying the neural dynamics models in RL, though I do have some problems about the results. I recommend for accepting the paper, and may raise my score if my concerns are addressed properly. ", "strength_and_weaknesses": "I found this paper very well motivated with inspiring results. The major observation made in the paper is that the kernelized nonlinear regulator, linear MDPs, and neural-nets parameterized MDPs can be summarized by the so-called MDPs with neural dynamics models. The neural dynamics models assume the transition dynamics is proportional to the Gaussian RBF kernel in the low-rank embedding space of the states and actions. To find the optimal policies, the proposed algorithm ELNF adapts estimation and planning techniques based on MLE estimation scheme in low-rank MDPs and kernelized LSVI algorithm proposed by Yang et al. (2020). However, it requires much effort to adapt these techniques in the neural dynamics model, which I believe is another key novelty. \n\nNevertheless, I do have some concerns about the results of the paper. \n\n1. The first question is about the number of actions appearing in the sample complexity. For general MDPs with neural dynamics, the number of actions should also be large. Examples include continuous control tasks, combinatorial optimization tasks, etc. The famous AlphaTensor algorithm has exponential number of actions. I think it is better to discuss how to perform \"discretization\" or establish some Lipschitz assumptions on the action space to reduce the cost of uniform sampling.\n2. Intuitively the log-covering number of neural nets should have polynomial dependency on the number of parameters. It seems that the sample efficient neural dynamics model does not include the well-known over parameterized neural nets whose number of parameters are very large.\n3. The authors claim that the ELNF algorithm is computational-efficient if the optimization oracle (4.3) and (4.4) can be implemented efficiently. How does this oracle implemented when the dynamics is parameterized by neural nets?\n4. I think there should be more discussions on the decay rate $\\gamma$ of the covering number. How large is this decay rate for common neural nets? Could you provide some intuitions on why $\\gamma$ affects the sample complexity in the exponents?\n5. Why do you need step -1 and step 0, and how do you assure $s_1$ is exactly the initial state?\n\nA minor question: \nPage 9 (comparison with Done et al.(2021)): $\\epsilon=0$ should be $\\gamma=0$", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster