Optimistic Policy Optimization with General Function Approximations
Authors: Qi Cai
Zhuoran Yang
Csaba Szepesvari
Zhaoran Wang
Venue:  (2021)

Abstract: Although policy optimization with neural networks has a track record of achieving state-of-the-art results in reinforcement learning on various domains, the theoretical understanding of the computational and sample efficiency of policy optimization remains restricted to linear function approximations with finite-dimensional feature representations, which hinders the design of principled, effective, and efficient algorithms. To this end, we propose an optimistic model-based policy optimization algorithm, which allows general function approximations while incorporating~exploration. In the episodic setting, we establish a $\sqrt{T}$-regret that scales polynomially in the eluder dimension of the general model class. Here $T$ is the number of steps taken by the agent. In particular, we specialize such a regret to handle two nonparametric model classes; one based on reproducing kernel Hilbert spaces and another based on overparameterized neural networks.

Under review as conference paper at ICLR 2021
OPTIMISTIC POLICY OPTIMIZATION WITH GENERAL FUNCTION APPROXIMATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Although policy optimization with neural networks has track record of achieving ofate-of-the-art results in reinforcement learning on various domains, the theoretical understanding of the computational and sample efficiency of policy optimization remains restricted linear function approximations with dimenssoiai feature representations, which hinders the design of principled, effective, and efficient algorithms. To this end, we propose an optimistic model-based policy optimization algorithm, which allows general function approximations while incorporating ex- ploration. In the episodic setting, we establish a v -regret that scales polynomially in the eluder dimension of the general model class. Here is the number of steps taken by the agent. In particular, metric model classes; one based on reproducing kernel Hilbert spaces and another based overparameterizee neural networks.
specialize such regret to handle two nonpara-
INTRODUCTION
Reinforcement learning with neural networks achieved impressive empirical breakthroughs (Mnih al., 2015; Silver et al., 2016; 2017; Berner al., 2019; Vinyals et al., 2019). These algorithms are often based on policy optimization (Williams, 1992; Baxter & Bartlett, 2000; Sutton et al., 2000; Kakade, 2002; Schulman et al., 2015; 2017). Compared with value-based approaches, which iteratively estimate the optimal value function, policy-based approaches directly optimize the expected total reward, which leads to more steady policy improvement. In particular, as shown in this paper, policy optimization generates steadily improving stochastic policies and consequently allow adversarial environments.
On the other hand, policy optimization often suffers from lack of computational and statistical efficiency in practice, which calls for the principled design of efficient algorithms. Specifically, in al., 2019a;b; Bhandari & Russo, 2019; Liu et al., 2019; Agarwal et al., 2019; Wang et al., 2019) establishes the convergence of policy optimization to globally optimal policy given sufficiently many data points, even in the presence of neural networks. However, in terms of sample efficiency, it remains less understood how to sequentially acquire the data points used in policy optimization while balancing exploration and exploitation, especially in the presence of neural networks, despite the recent progress (Cai et al., 2019; Agarwal et al., 2020). In partieular, such a lack of sample efficiency prohibits the principled applications of policy optimization in critical domains, e.g., autonomous driving and dynamic treatment, where data acquisition is expensive.
terms of computational efficiency, the recent progress AAbbasi-Yadkon
In this paper, we aim to provably achieve sample efficiency in model-based policy optimization, which quantified via the lens of regret. In particular, we focus on the episodic setting with general function approximations on the transition kernel. Such a setting is studied by Russo & Van Roy (2013; 2014 4);; Osband Van Roy (2014); Ayoub et al. (2020); Wang et (2020), which however focus on value iteration. In contrast, policy optimization remains less understood, despite its critical role in practice. To this end, we propose an optimistic policy optimization algorithm, which achieves exploration by incorporating optimism into policy evaluation and propagating through policy improvement. In particular, establish x(P)- / --e-rrerret of the proposed algorithm, which matches that of existing value iteration algorithms but additionally allow the reward function to adversarially vary across each episode. Here T is the number of steps, H is the length of each episode, and s(P) is

---

Under review as a conference paper at ICLR 2021
the model capacity, which is defined based on the eluder dimension. Moreover, we instantiate the proposed algorithm for the special cases of reproducing kernel Hilbert spaces and overparameterized neural networks, both of which are infinite-dimensionn model classes.
Our work related to the study on computational efficiency of policy optimization (Fazel et al., 2018; Yang et al., 2019; Abbasi-Yadkori Yadkori et al., 2019a;b; Bhandari & Russo, 2019; Liu et al., 2019; Agarwal et al., 2019; Wang et al., 2019). These works assume either the transition model is known or there exists well-explored behavior policy such that the policy update direction can be estimated accurately. With such assumptions, the tradeoff between exploration and exploitation is absent and their focus is solely the computational aspect. In addition, our work is related to the works on adversarial MDP (Even-Dar et al., 2009; Yu et al., 2009; Neu et al., 201 20;b;;;; Zimin & Neu, 2013; Neu al., 2012; Rosenberg & Mansour, 2019b;a). The algorithm in these work directly estimates the visitation measure and their algorithm utilize mirror descent to handle adversarial reward functions. Furthermore, our work is closely related the recent work on the sample complexity of policy optimization methods Cai et al. (2019), which only focus on the tabular and linear In contrast, our work consider general function approximation setting, which is significantly more general. Moreover, the construction of optimistic policy evaluation is related to Ayoub et al. (2020), where the similar approach is incorporated in estimating the optimal value function. The theoretical foundation of such type of optimistic estimation is innovated by Russo & Van Roy (2014) in the bandit problem. evaluation, we rely on the notion of the eluder dimension proposed by Russo & Van Roy (2014), which is further instantiated by this paper to the cases kernel and neural function approximations.
I settings.
particular, to characterizing the optimism and accuracy of the optimistic
1.1 NOTATIONS
We denote by || ||p the fp-norm of a vector when p N the spectral norm of matrix when p 2. For any two distributions p1. P2 over a discrete set A, we denote by DKL P2) the KL-divergence
(1) log (i(a) (2(a)
(PI.PI P2) = Σ
aEA
For any a, b, x E I, define the clamp function
b. if b,
clamp(æ, a,
2, a < x $
(1.1)
0, if < a
PRELIMINARIES
2.1 ONLINE REINFORCEMENT LEARNING WITH ADVERSARIAL. REWARDS
We consider an episodic MDP (S, A, H, (PA) (r where is a continuous state space, A a discrete action space, H is the number of steps in each episode, { represent the unknown particular, for any h E [H], Ph. represents the transition kernel from state-action pair (sh, as) at the li-th step to the next state 8h+11 while Ta represents the reward function at the /i-th step that maps a state-action pair to deterministic reward. Moreover, function at the f-thh step of the k-th episode. In particular, r depends on the trajectories before the k-th episode begins, possibly in an adversarial manner, and remains unobservable until the k-th episode ends. Without loss of generality, we assume each episode starts from fixed state $1 and all rewards fall in the interval (0, 1).
transition model, and {rx ||= represent the reward function.
allow the reward function to vary across episodes and denote by 1% the reward
For any h E [H]. a policy Th represents the conditional distribution of the action given the state at the h-th step. We drop the subscript h to represent the collection of policies at all steps and still refer to such collection as a policy when it is clear from the context. For any (ks, h) N x [H), given H
a policy π and reward functions {r (r k= the value function and Q-function at the h-th step of the
2

---

Under review conference paper at ICLR 2021
k-th episode are defined by
H
V (8) = EN
Σ =
(s))
8h =
(8,0) = En
Σ ==
of (8 az) 8h = 8,00 =
for any a) E S x A. Here the subscript æ in the expectation [-] denotes all actions are taken according to the policy т except for the one given in the condition. An online algorithm aims to construct and execute sequence of policies {x J621 and minimize the regret
K v () ((1)),
(T) max
(2.1)
k=1
where is the number of episodes and 7 KH is the number of steps taken by the algorithm.
2.2 REPRODUCING KERNEL HILBERT SPACE
We say H. is reproducing kernel Hilbert space (RKHS) on a set y with the reproducing kernel I. : x + R if there exists inner product ( such that, for any H and x E V. we have f(x) = (f,K..))t Here Kg represents the function ((x,)) :), which the Riesz representation of the evaluation functional at æ (Schölkopf al., 2002). When the reproducing kernel K. is continuous, symmetric, and positive definite, Mercer's theorem (Steinwart & Christmann, 2008) says I. has the representation
06 K(z, v)
Σ (z) for any x, E V,
(2.2)
1=1
where { an orthonormal basis of I2()) and A 2 x2 2 ... 2 0. See more details on RKHS in Section A.
ALGORITHM
Before the k-th episode begins, we construct the policy T² based on * and (Q |ー which are the policy in the (A: 1)-th episode and estimators of {Q], (Q)=-11 - - respectively. Then, we execute the policy n² in the k-th episode and correspondingly update the Q-function estimators {Qh) using the reward function {r {TThh=1> which is observed after the k-th episode ends.
Framework:
Jh=1
Policy Improvement:
For any hk E [K] x [H], we parametrize o by exp(F (s, for any (s, AS
( = Enee expl (x
(3.1)
Here Ej is the potential function, which is initialized as the zero function and updated by
(s, (s, - a).
(3.2)
Here a > 0 is the stepsize of policy improvement. Equivalently, we have
* ( x - (-1ss) exp(a (s,-()
for any s E see (3.2) is policy improvement step, note that क is the maximizer
(m)))) B_*_1((2) (Sk. -), Tn a + -! DKL (Ta s=)ll== (-ll)) -

---

Under review conference paper at ICLR 2021
This is the same as the update in Politex (Abbasi-Yadee) et al., 2019a), which originates at MDP-E (Even-Dar et al., 2009). also very close to a slightly changed variant of the one-step objective in the proximal policy optimization (PPO) algorithm (Schulman al., 2017; 2015).
Policy Evaluation: Let P known class of transition models such that Ps. E P for any [H] which is specified in Section 4. Also, for any P P, E S. a A. and V : S - [0. HJ. we define
2p(8, a, = / V(s') (16518,a)10) ((s)))(('(8..)))) ds'.
(3.3)
For any (k:, h) [K] x [H]. we construct confidence set of the transition model Pa. and corre- spondingly the optimistic Q-function estimator O using the data collected before the k-th episode begins. Note that we do not use the data collected from the k-th episode although they are available, which, however, is only used to simplify the analysis. Let V be the zero function. Inspired by Ayoub et al. (2020), given the optimistic value function estimators (Vi+11 k-11 from the first (k 1) episodes, we construct the confidence set P/ of Pa. by
k-1 (sp ah Vit1)) - Zpp (5% 0h vi++1)²² s.)..
Ph {PEP)
(3.4)
k-1 (Vitz 2p(8% ah vi+t)))
where PK = argmin PEP
for threshold 3 0, which represents the degree optimism. Then, for any (s, S A, given the optimistic value function estimator V we define the optimistic Q-function estimator Q by
(=(s,a)= + 2p a, V PEPE
(3.5)
and correspondingly update the optimistic value function estimator by (s) (Q) (s. m. (+){s))) for any S. We apply the clamp function defined in (1.1) to the second term the right-hand side of (3.5) to ensure it falls the range [0, - h], which is due to the assumption that all rewards fall in the range [0, 1].
Implementation: The full algorithm is presented in Algorithm 1. Given a parametrization of the model class P. we can apply the projected stochastic gradient descent (PSGD) algorithm solve the constrained minimization problem in Line 11 of Algorithm 1. In particular, for kernel function approximations in Section 4.1. it reduces convex optimization problem, which allows the PSGD algorithm to converge to a global minimizer. Meanwhile, for neural function approximations, it reduces an approximately convex problem in the overparametrized regime (Arora al., 2019), which leads to the same global convergence guarantee. Also, to implement Lines 12 and 13 of Algorithm I, it suffices to solve a constrained maximization problem (Feng et al., 2020), where constraint is defined in Line 12. The Lagrangian relaxation of such constrained maximization problem can be solved by the PSGD algorithm in the same manner of Line 11. In addition, to instantiate the update of Q in Line 13, it suffices to solve least-squares regression problem. In summary, we can instantiate the aforementioned steps through supervised learning oracles, which can be implemented in computationally efficient manner.
4 THEORY
We analyze the regret of Algorithm 1, which is defined in (2.1). In Sections 4.1 and 4.2, we characterize the regret with specific choices of the model class P. while in Section 4.3, we characterize the regret for general P, which serves meta result. An informal version of the results is given in the following theorem.

---

Under review conference paper at ICLR 2021
Algorithm Optimistic Policy Optimization with General Function Approximations
1: Input: number of episodes K, model class P, stepsize threshold 3
2: Initialize T as the uniformly random policy
3: For k = to K do
4: Start the k-th episode and receive the initial state of
5: For step h 1 to H/ do
(policy improvement)
6:
Update the policy by m x ( exp(x(t (s,-)) for any S Take the action at, . ( and receive the next state sh+
7:
8:
Observe the reward function (r)()))) Initialize V For step h #++ (-) the zero function
9:
10:
to I do Ph < argmin Et=l (V7+ ((4 (7) ds))
(policy evaluation)
11:
k-1
Px - (PEP: Σ
(i sh a7) ds' ViT (P sh az)) ds')² s 8}
(+(,))) + -x()) clamp PEPk Is Vh V ds, d5, h)
14:
v((() - (2
Theorem 4.1 (Informal Version of Theorems 4.3, and 4.12). With proper choices of and B the regret of Algorithm satisfies
RT) = (R(()) H
with high probability. Here Ō omits absolute constants and logarithmic factors of H, T, and [A], while xcP) denotes the model capacity of P, which is specified in Sections 4.1, 4.2, and 4.3.
Theorem 4.1 indicates that, compared with the optimal policy in hindsight, namely argmax, Ek (s1) the average regret of Algorithm 1, namely Regret(T))/2 converges to zero at a sublinear rate. In other words, at least one of the K policies attained by Algorithm achieves vanishing optimality gap with respect to the varying reward function across the K episodes. The model capacity se(P) is specified in Sections 4. and 4.2 for kernel and neural function approx- imations, respectively. To establish such specific results, characterize x(P) using the eluder dimension for general function approximations in Section 4.3, which serves as the unified analysis.
4.1 KERNEL FUNCTION APPROXIMATIONS
Let P be a subset of an RKHS with the reproducing kernel K., which has the representation in (2.2). In detail, let S be measurable set with |S] < 1, where | denotes the Lebesgue measure. With a slight abuse of notation, we denote by A the embedding of the action space into a Euclidean space with the dimension IA], where AA] denotes the number of actions. Mcanwhile, let ) be dy-dimensional set such that A x S C y. We assume there exists R 2 2 such that P. C HR. where Hn is the RKHS ball over y with the radius R.
Assumption 4.2. We assume K. satisfies the following regularity conditions.
(i). It holds that [C(,,, y < (2)())) < 1, and >3 < 1 for any x, E y and jEE N.
(ii). There exist threshold E (0, 1/2) and absolute constants C1, C2 > 0 Ouch that X3 S C1 exp(-C2j²) for any E N.
Note that replace the I's in the upper bounds of Assumption 4.2 with any absolute constant, which is reflected the H-norm of any function in H. Meanwhile, we can relax (x)) S into |XZ (1)) & for any absolute constant E [0, 1/2), which leads to the same regret.
We have the following result on the regret of Algorithm 1.
5

---

Under review conference paper at ICLR 2021
Theorem 4.3. Suppose Assumption 4.2 holds and P C Hn. There exist absolute constants C3, C4 such that, for any p (0, 1), if we
a 2og (A/HH))
= == C2H² -log' 14/1 (RT/pp))))) log/(1/7)/7
in Algorithm 1, then it holds that
(T) C. C.C H3T log" 1+1/ ( 1og/(1/)//
with probability at least (1 -p).
Proof. See Section C for a detailed proof.
Theorem 4.3 indicates that log (l log (1/7)/7 serves as the model capacity kc()) in Theorem 4.1 for kernel function approximations. In particular, we can obtain y for a broad range of reproducing kernels K. (Srinivas et al., 2009). Meanwhile, we can scale R to control the model capacity x: (P)) (Schölkopf et al., 2002).
4.2 NEURAL FUNCTION APPROXIMATIONS
Let P be set of overparametrized neural networks. In detail, we denote by NN a neural network with its weights collected in vector R". Let wD be the random initial weights. For radius
R 2 2, we define
P (P w BR, s.t. P.t. (. NN(x;; w), for any xx (4.1)
where B = (w R. | w w0 S R).
Without loss of generality, we assume NN w for any x which can be achieved by symmetric initialization scheme. See Section E for detailed explanation. To connect with the result for kernel function approximations Section 4.1, we define the following condition.
Condition 4.4 (Implicit Lincarization). holds that
Em
max [N w) V NNNNN ( w =EV.EEB
Condition 4.4 indicates that NN(x; w) is uniformly close the linear function ... NN, T w²) of w. particular, the linearization error Em negligible compared with the dominating terms in the regret. The following lemma ensures Condition 4.4 holds for two-layer neural networks when m is sufficiently large.
Lemma 4.5 (Overparametrizztioon) Suppose NN a two-layer neural network, where the activation function is 1-smooth, and it holds that ||0|| <. for any E Y. Then, Condition 4.4 holds when m 2 dy K3²
Proof. See Section E for a detailed proof.
Note that the analogous of Lemma 4.5 also applies to nonsmooth activation functions, for example, the rectified linear unit (ReL.U), and multilayer neural networks (Allen-Zhu al., 2019; Du et al., 2019; Zou et al., 2020; Gao et al., 2019), which ensures Condition 4.4 holds. The linear function of in Condition 4.4 induces RKHS H with the reproducing kernel
KNTK(I, v) V NN( w TV NN w)), for any 2, 3,
(4.2)
which is known as the neural tangent kernel (NTK) (Jacot et al., 2018).
Assumption 4.6. We assume KNTK satisfies the regularity conditions in Assumption 4.2.
Note that the NTK defined in (4.2) depends on the randomness of w When m goes to infinity, such an empirical NTK converges to its expectation, which gives the population NTK. It is shown Yang

---

Under review conference paper at ICLR 2021
& Salman (2019) that Assumption 4.2 holds for the population NTK, which implies it also holds for the empirical NTK with high probability when m is sufficiently large.
We have the following result on the regret of Algorithm 1.
Theorem 4.7. Suppose Assumption 4.6 and Condition 4.4 hold and P has the representation in (4.1).
There exist absolute constants Cs, Cs > such that for any E (0, 1), if we set
a = 2og (I/(H)),
B = C2 log +1/1 (RTTHR/p))) /p) log (1/7)/7
in Algorithm 1, then it holds that
RTgret(T) S C& H3T C3VH3T (og(+1/2((AA1/)))) 1o//(1/)//
with probability at least (1 - p)-
Proof. See Section for detailed proof.
In parallel with Theorem 4.3, Theorem 4.7 indicates that log (ggg" serves as the model capacity x(P) in Theorem 4.1 for neural function approximations, which can controlled by scaling R (Arora et al., 2019).
4.3 GENERAL FUNCTION APPROXIMATIONS
Let P be general model class, whose model capacity is characterized by the eluder dimension (Russo & Van Roy, 2014; Osband & Van Roy, 2014; Ayoub et al., 2020) defined as follows.
Definition 4.8 (Eluder Dimension). Let 2 be set of real-valued functions on the domain X. For any > 0 and E N, say I. X is (2, eiindeeennd of Fyp. X if there exist f1 E Z such that
E (h((,)) Sa(,)))) 1/2
se, [f((+)) - fe(x+)] >E
(4.3)
The eluder dimension of at scale s, which is denoted by dimp (2, E), is the length of the longest sequence Ff, X' such that, for any j E [r], 2i is (2,,e"-independen of 21,..., .1. for some è' 2
The following lemma decomposes the regret of Algorithm into errors that arise from policy improvement and policy evaluation, respectively.
Lemma 4.9 (Regret Decomposition). For any le [K], it holds that
T/c (8x)8 + Regret(T)) = E.- (( T)( 1 88))
(V) -Vr *si))
A Am1
A=
E. (ri, an) zP, (sh, an, V (sh,
Proof. See Lemma 4.2 of Cai et (2019) for detailed proof.
The following lemma characterizes the enror that arises from policy improvement.
Lemma 4.10 (Policy Improvement). we set a = 22g [AI((H²2) in Algorithm 1, then it holds that
Ey- Bx.(((Q()) 1((
/2KH1. llg [A].

---

Under review conference paper at ICLR 2021
Proof. See Section B.2 for detailed proof.
Recall that for any E P, 2p is defined (3.3). Also, let 2p = (zp : e P). For any > we denote by No (P, -1oo,,1)) the e-covering number of P with respect the b -norm distance, which defined by
- P
max (s,a)E8xAA
P(s s, PP'('' (s(s'|s,a) s,
ds', for any P,P' E P.P
The following lemma characterizes the error that arises from policy evaluation.
Lemma 4.11 (Policy Evaluation). For any p E (0, 1). if we set
B > 2H² (og(N ll - 2H/p) + 4(H + (19/4-log(KK3H/pp)
(4.4)
in Algorithm 1, then the following results hold with probability at least (1 p).
(Opiiiism) For any (k, h) E [K] [H] and (s, S ESx A. it holds that
(s, a) + 2PA (s,a, v (s. 0.
(Accuracy) Let d K dimp (2m KK). holds that
(v) -/t"t/>s)))) (s1)) $ /32KH3 (ogk///log(//2)) H(dH + 1) + 4/O3KH².
Proof. See Section B.1 for detailed proof.
Recall that T= = KH. The following theorem characterizes the regret of Algorithm 1 when P is general model class, which serves as a meta result.
Theorem 4.12. In Algorithm 1, if we set a as in Lemma 4.10 and 3 as in Lemma 4.11, then it holds that
(Tg I /2H*T log [ + / /2222 logpp// + H(HH + 1) + 4 d3HT
with probability at least (1 p), where K A dimmd dimg(2p,1/K))
Proof. The proof follows from combining Lemmas 4.1,4.11, and 4.10.
Theorem 4. 4.12 indicates that
max d, v d log (og IIo,,)))
serves the model capacity kcP)) in Theorem 4.1. The regret upper bound in Theorem 4.12 is similar to that in Ayoub et al. (2020) when P a general model class, whose model capacity is characterized contrast,
by the eluder dimension. a benefit of the policy optimization approach. To establish the regret upper bounds in Sections 4.1 and 4.2, it remains to characterize the corresponding eluder dimension and log-covering number, respectively. See Sections C and D for details. As a special case, Theorem 4. 12 also applies to the case where P a of d-dimensional linear models with finite d, which is studied in Cai al. (2019). In particular, the eluder dimension and log-covering number in (4.4) are both ( (Ayoub et al., 2020), which leads to the / H in Cai et al. (2019). In contrast, Theorem 4.12 additionally handles the case where d infinite as in kernel and neural function approximations.
algorithm additionally handles adversarial rewards, which
REFERENCES
Yasin Abbasi- Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, pp. 2312-2320, 201

---

Under review conference paper at ICLR 2021
Yasin Abbasi-Yadkorr Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvári, and Gellért Weisz. POLITEX: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pp. 3692-3702, 2019a.
Yasin
Nevena Lazic, Csaba Szepesvári, and Gellert Weisz, Exploration-echanned POLITEX. arXiv preprint arXiv: 10479, 2019b.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gauray Mahajan. Optimality and approximation with policy gradient methods Markov decision processes. arXiv preprint arXiv: arX8iv/908..000 /908.00261, 2019.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pc-pg: Policy cover directed exploration for provable policy gradient learning. arXiv preprint arXiv:2007.0844 2020.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584. 2019.
Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin F Yang. Model-based reinforcement learning with value-targeted regression. arXiv preprint arXiv:2006.01 107, 2020.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):35--367, 1967.
Jonathan Baxter and Peter Bartlett. Direct gradient-based based reinforcement learning. International Symposium on Circuits and Systems, pp. 271-274, 2000.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 192.00691, 2019.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv: 190.://966077866 2019.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- 2019.
tion. arXiv preprint
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online Markov decision processes. Mathe- maties of Operations Research, 34(3):726-736 2009.
Maryam Fazel, Rong Ge, Sham M Kakade, and Mehran Mesbahi. Global convergence of policy 2018.
gradient methods for the linear quadratic regulator. arXiv preprint
Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu, Accountabbc off-policy evaluation with kernel bellman statistics. arXiv preprint arXiv:2008.0660 06668, 2020.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. In Advances in Neural Information Processing Systems, pp. 13029-13044 13040, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, pp. 8571-8580, 2018
Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, pp. 1531-1538, 2002.

---

Under review conference paper at ICLR 2021
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint arXiv:/906. 2019.
Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing. In International Conference on Computational Learning Theory, pp. 154-168. Springer, 2006.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 51 518(7540):5295555 2015.
Claus Müller. Analysis of spherical symmetries in Euclidean spaces, volume 129. Springer Science & Business Media, 2012.
Gergely Neu, András Antos, András György, and Csaba Szepesvári. Online Markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems, pp- 1804-1812, 2010a.
Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-path problem. In Conference on Learning Theory, pp. 231 2010b.
Gergely Neu, András György, and Csaba Szepesvári. The adversarial stochastic shortest path problem with unknown transition probabilities. In International Conference on Artificial Intelligence and Statistics, pp. 805-813, 2012.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, pp. 1466-1474, 2014.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in nearal information processing systems, 20: 177-1184, 2007.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In Advances in Neural Information Processing Systems, pp. 2209- 2218, 2019a.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. arXiv preprint arXiv:1905.07773, 2019b.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pp. 2256-2264 2013.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, (2(4 1243, 2014.
Bernhard Schölkopf, Alexander J Smola, and Francis Bach. Learning with kernels: Support vector machines, regularization, optimization, and beyond. MIT Press, 2002.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 2017.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche. Julian Schritwiesser, Ioannis Antonogiou, Veda Panneershelvam. Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
David Silver, Julian Schritwieserr, 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.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arx1v.09/2.3995, 2009.
10

---

Under review conference paper at ICLR 2021
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, 2000.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3350-344 2019.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.0///55 2019.
Ruosong Wang. Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005. 2020.
Ronald J Williams. Simple statistical gralient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229-255 1992.
Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks. arXiv preprint arXiv: 10599, 2019.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. On the global convergence of actor- critic: A case for linear quadratic regulator with ergodic cost, arXiv preprint arXiv:190.006266. 2019.
Zhuoran Yang, Chi Jin, Zhaoran Wang. Mengdi Wang, and Michael I Jordan. Bridging exploration and general function approximation in reinforcement learning: Provably efficient kernel and neural value iterations. arXiv preprint arXiv:2011.04622 2020.
Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Mathematics of Operations Research, 34(3):337-751 2009.
Alexander Zimin and Gergely Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Advances Neural Information Processing Systems, pp. 1583-1591, 2013.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine Learning, 109(3):467 492, 2020.
11

---

Under review conference paper at ICLR 2021
A
MORE DETAILS ON RKHS
An example the RKHS is the linear model class. In particular, let d be a d-dimensional feature vector
(xx) = (v), (.())),.,,,,(())))
()(()))
for any E V
where ei...... the are linearly independent. Then, the linear span of {1t 1 forms an RKHS H.p with the reproducing kernel K y) (x)) (v) for any x, V and the corresponding inner product (,, is defined by the Euclidean inner product
(w)-) C (())())) 12)H.. = =
for any C2,02 C2 R2
The above example can be naturally generalized to the case where = oo, that is, the feature vector can be infiniteddimensional. Moreover, recall that (2.2) says the reproducing kernel I. has the representation
K(x, y) Σ (z) for any x, E y,
where { is an orthonormal basis of L2()) and λ 2 A 2 ... 2 O. We refer to {o as the eigenfunctions of KC with the corresponding eigenvalues feature vector
(Az 1.00 Such a representation gives the
Ō(x) (Vλ1 @1(x), VT2 o2(x)....)) for any V.
The linear span of (yA/- - recovers the RKHS with the reproducing kernel K' and inner product (x. When the reproducing kernel K. is infiniteddimensional, that is, has an infinite number of non zero cigenvalues, ò is an infiniteddimensioall vector. It is known that RKHSs of various infinitediimensinaal reproducing kernels, for example, the Gaussian radius basis function kernel (Steinwart & Christmann, 2008), are rich function model classes in the sense that they are dense in the class of continuous and bounded functions.
B PROOFS FOR SECTION 4.3
In this section, provide the detailed proofs of the result in Section 4.3. For notational simplicity, we denote by Pd the operator that takes the conditional expectation with respect to the transition kernel PA, for any h (H).
B.1 PROOF OF LEMMA 4.11
Proof. We define the event & that
Ph E Ph, for any (k, h) E [K] x [H].
(B.1)
By choice of 3 and Lemma F.4 with 5 p/2, it holds that occurs with probability least (1 - p/2).
12

---

Under review conference paper at ICLR 2021
Optimism:
For any (k: E [K] x [H], Ph. E P implies
@x(+,)) - (PA ((,-))
/
V P |( -1) - -1 Vi Viti(ss) Pa(s's (s)5)s)))
- -clamp max (PEPR
2 clamp/ (
Vo+z Pa(s' ds' , 0, H - i1) Vitz((') P 1.))d'' (B.2)
When h = H, the right-hand side of (B.2) is zero since V (++ = O. When h < H, by the construction of Qh+ in (3.5) and the assumption that (+)) E [0, 1]. we have
V++++)) [0, H h], [ Vitt(ss) Pa(s' 1.,-) E 10, H - h).
Qh+1(s)) E [0, H- - h],,
The right-hand side of (B.2) is also zero, which implies
(. (ri())) + (PAVEL))))) 2 0. Thus, the optimism result holds under the event E.
Accuracy:
We invoke Lemma F.1 and obtain
Σ ( v7* (st) Σ
Σ
D
D)22)
(B.3)
K H
Qhish att) (rh a + PP, (sh
of:)).
k= 1=1
where 14,11 s 2H, | < 2H,, D H.2 0 for any (k: h) E [K] x [H]. and
D1,1, D1.2 D2,1 D1, D ................................ D 11-1122 + D H111>
Df, DJ,2 + D2,,, D2, + - + Dz
is martingale difference sequence. The Azuma-Hoeffdding inequality (Azuma, 1967) implies
K Σ ΣΣOD (DL, + Dh.2) S /32K 132K///--o(p//12 log(p/2)
(B.4)
1=1 1=1
with probability at least (1 - -p/2). remains to upper bound the second term on the right-hand side of (B.3). For any (k:, h) [K] x [H, P. Ph implies
(sh at:) (r at) + (P, V/ h (s af:)
clamp( max / Viizass): P(s' 1/ at) do' O, H - - Viti(s") PP sh at) do'
PEPÉ
min /
Vi (s'r P(s' |s at) ds' PEPk I Vitr(65) P(s' | at) ds'.
max PEPk
JS
13

---

Under review conference paper at ICLR 2021
Applying Lemma F.5, for any h E [H]. we have
@his a - (rf a + (I V h+ (3 a)))
min / Vi+z(s') PP') 18% alt) ds')
Vi+z((s)) P(s' 18 a ds'
max PEPA S
PEP, s
$ 1 + dH = 4 d3K,
(B.5)
where d K dime Zp, 1/K). Combining (B.3)-(B.5), have
K
Σ
(+() V (5+) 32 logíp/2) H dHf 48ННН.
In summary, when the event & and (B.4) hold, which occur with probability at least (1 p), we have
(Pw (+s)), for any (k, h) E [K] [M].
(vr((s) - Vi" ((tt) 32 log(p/2) - (1 + dH) d3HT.
Therefore, we conclude the proof Lemma 4.11.
B.2 PROOF OF LEMMA 4.10
Proof. By Lemma 3.3 of Cai et al. (2019), for any hk E [K] [H] and s E S, we have
s) (- I saH? /2 + a (KI m))+1))
(
Th
k+1 (+*+((1)))) (-18)))
(B.6)
which implies
Σ Σ
E. - () --
H
I SaKH3 /2 aa
a -1 11. Σ
E. [DKL (TZ
h=1
< aKK 12 + a IA].
(B.7)
Plugging log [HT(H into the right-hand side of (B.7), conclude the proof of Lemma 4.10.
C PROOF OF THEOREM 4.3
In this section, we prove Theorem 4.3. By Theorem 4.12, it suffices to upper bound the eluder dimension of 2p = {>p: : P following two lemmas, respectively.
P and log-covering number of HR. which are characterized by the
Lemma C.I. Under Assumption 4.2, there exists an absolute constant Cr > such that
K dimg (Zp, 1/K) S C7
log log 1+1/ (RT).
Proof. Let = K A dimp(Zp 1/K). By Definition 4.8, there exists a sequence æj.... By E S x A x (0, HJS such that x, is 1 1 of .1,..., 2y-1 1 for any [t]. Here the independency scale is assumed to be 1/K without loss of generality, which can be changed to any
14

---

Under review conference paper at ICLR 2021
value larger than 1/K. In other words, for any E [8], there exist P1, P2 E P such that
2n (xi) - 213 (x:)) < 11/K²
(C.1)
lep (x+) - 2p,, (2+)) > 1/K.
(C.2)
Note that for any x = as, V) E Sx A x [0, H and P, by the reproducing property of the RKHS H. we write
2p(x) V(5). P(''ls,a) / V(s)) ((s))-P,KKa (P.K)s
The representation of X in (2.2) implies
zp(x)= = / V(5) (P.E
" 05) ds'
1=1
V(8) Σ
T (P. v. 2i)H ds'
j=l
Σ
TT
V(s') () ds' (P, T dj)m.
A=1
For any do such that dy 2 4(1 7)( where y and C2 are defined Assumption 4.2, we define
Ep(x)= = Σ Vaj / V(s') os (P. V, 0jHn
15iSdo
for any = (8, E E Ax (0, HJS and P PEP. Then, we have
(zr(z) -x(()- = Σ VΛ V(s') as ds' (P.V 05
j>do
Σ VA IS| H. |P S V2 RH,
j>do
jodo
where [8] the Lebesgue measure of S and |S| < 1. Here the first inequality follows from the
Cauchy-Schwazz inequality and / dy || = for any j N, since (vīg .515 is orthonormal basis of H. By Assumption 4.2, we obtain
=p(x) < Σ
VC exp(-C2i" RH
j>dg
Vo -H- Σ exp(-C2jj//2 /2)
j2do
SVC RH 44
(1C2) expp(CC2lf
(C.3)
where the last inequality follows from Lemma F.6. For notational simplicity, let
[(do) = V RH 4dh (1C2) exp((C2d6)
(C.4)
15

---

Under review as a conference paper at ICLR 2021
By (C.1), it holds that
Σ ER (21) - (x:1p -
(12p, (2i) - (2,)) + (do))
(2)zp, (1:) - (x;1) (TT(o))
-
i=1
$ 2/K² + 81 r(do)?
(C.5)
where the last inequality uses T S f. For any [t], we define
((Pi - P2, VT 11).. (PI P2, v Ado Deo (21)
(C.6)
(VAi- Is Vi((') $1(s,, ar. 50) ds'...., ..... Vdd / Vi(s') (d, at)))ss)
(C.7)
A, Ldoxdo/ (dok R²) + Σ yuu
(C.8)
Then, holds that
1
y A-V = dok2 R²
11ul112 +
( u;)
i=1
1
Σ
P1
P2. VAy 21131 Σ Ep (2.) (x,)1
R2
R
1
Rd +2/K² 8 = 6/K2 + r(d)))
(C.9)
K2
where the inequality uses (C.5) and
(Pi - P2, N o5 S P1 - P2lk // 3 S 4R² 1 4R².
Here we uses |||| S R for any P and Vl dill = for any j E [do].
In the sequel, we establish an upper bound of [2p, - (x+ )1 By the definitions of y in (C.6) and v, in (C.7), we can write Ep, (I+) Ep, (x+) = (z, By (C.9), Er (z+) Ep, (z+)) is upper bounded by
-
(. s.t. TTY 6//K² + 8t stdo))))
A,
max y ERR
The maximizer of such quadratic program is
y' = (100)////// A Cy.
Therefore, we obtain
EB (x+) Erg (x+) S (0//2++8-T(())))) (
(C.10)
On the other hand, by (C.2)-(C.4), we have
E (2,)) Ep, (1x))
lzp, (xx) - -p, (2,)), (1²p, zp, (x+) (x,) (x,)))
2 lap (xx) - =p, =2, (x,)) 2T(d))
1/K- (dd)))
(C.11)
16

---

Under review conference paper at ICLR 2021
We set dg = [Č- log(1 (0gg11/)/ log 1/7 (og where C' is defined in Lemma F.7. Then, by
Lemma F.7, holds that d 2 4(1 ()(rC2) and
((do) - 1/(4tK).
(C.12)
Combining (C.10), (C.11), and (C.12), we obtain
(1/K (do))
(1/K - 1/(2K))²
6 A Ur
1/100.
(C.13)
6/K² + 8t r(d))
6/K² 11((22))
Therefore, by (C.13), we have
t/100
min(1/100, A,','''
2 log(( 2 A,² u+) s (((oodet(Ae+1)) - logdet(A1))
(C.14)
where the last inequality uses the elliptical potential lemma AAbbasi-Yadkon et al., 2011). Here, similar (C.8), A4+1 is defined by
A--1 (dodd//dok
Σ vzu;
Note that
|0- 12 = Σ >3 (/ (/ S H2 j=1
do
for any E [t]. Thus, setting À 2 we have
log (et) do log X,
(C.15)
log det((A++1) S do log Act1lle I do log A A
Σ
|1o 12) s do log(A HoKH (C.16)
1=1
where the last inequality follows from t A dimg Zp, 1/K). Combining (C.15) and (C.16), we have
2( (((og)e((Ae+1) det(A)) S 2dg loglll111111111111 + doKH2 2dg log(1 KK 3 H?
(C.17)
Combining (C.14) and (C),7), we obtain
< 200do log(1 dk
600dg
(C.18)
Moreover, by do - Log(Loog (44KKK and (C.18), there exists an absolute constant Cs 0 such that
t s 600do RHH(doKRH)
< 600 -č- log(loo((//////// logg log([C log([[-too((/)))// -
< C's log (1/r)// log 1+111 RtK.
(C.19)
Recall that / = K A dime (2p, 1/K). Thus, by (C.19), we obtain
Zpp
< C7 (og2(1///// log 1+1 log/l1///////// 1+1/++1//K (K((HH)
(C.20)
17

---

Under review conference paper at ICLR 2021
for absolute constant C > 0. Thus, we conclude the proof of Lemma C.I.
Lemma C.2. Under Assumption 4.2, there exists an absolute constant Cy > 0 such that
NI ll lb,,1) S C9 log (1/7)/7 log (H1/((RR)
for any R 2 2.
Proof. Recall that we define ('(d)) in (C.4). By choosing t 2K H in Lemma F.7, there exists
dg = [ 1olo(1////// log (2K
where C is defined in Lemma F.7, such that dā 2 4(1 - ([(1-))))C2-- and
((d)) < 1/K2
(C.21)
Here and C2 are defined in Assumption 4.2. Let C' be minimal K Euclidean ball {v E I2 ||i|| I R} with respect to the fo-norm distance. For any P E P, we define P by
K -coverin of the
P(x) Σ
Xj (P. 2,(2), for any V ==1
Also, we write
v -= (V (P. Vddo (P, (d)))).
Since (vT 0 is orthonormal basis of H and P HR. we have
||l12 = 1| < PP| S R.
Thus, by the definition of C, there exists e C with 1 1012 1l2 S // KH). We define P* e by
do
Pa (x) Σ 0z Ag (z(),, for any x E y.
1=1
Then, by Assumption 4.2, for any x E V, we have
do
1P(x) - PP(x)) = Σ (0g - 03) /A oz(x)
5=1
$ || 0211 111 S dd -110 2212 $ 1/(2KH)
(C.22)
Also, for any x V, have
IP(x) P(x)
(P. V2 Σ (25-0,(2)) (
66))
j>do
Σ VT R
j2do
Σ
VC, exp( -Cij /2) R T(do),
(C.23)
j>do
where the first inequality uses || < R and T d3 the second inequality follows from
Assumption 4.2, and the last inequality follows from the same argument in (C.3) and 2 1. Thus,
18

---

Under review conference paper at ICLR 2021
for any E ) it holds that
P((x) Pr)) -(x)) + (P(x) - P*(x) s ((do) + + (K)(H)) (C.24)
We define
da Pc - P:= Σ vy Vag 0y(x) for any x E }}. j=1
Then, by (C.24), Pe is ( -covernn of P with respect to the loo -nom distance. Therefore, we have
(L/(KH) (P, |lc,,) S (P
5 PPel S [C] S C12 do
S Coooo -lgg log" log h//lo///////////// (KRH), (C.25)
where C12, Cg > 0 are absolute constants. Here the first inequality is because || |loe.1 S || ll
given |8| S I, the third inequality follows from Corollary 4.2.13 of Vershynin (2018), and the last inequality follows from the same argument in (C.19), Thus, we conclude the proof of Lemma C.2.
We note that our proofs of Lemmas C.I and C.2 for the exponential decay case can be made general. For a finite-rank kernel, we can let do be the rank of the kernel, i.e., the number of nonzero eigenvalues. Then, the same proof still holds and we can show that the eluder dimension upper bounded by (do Log(RKIH) H)). Moreover, for kernel with polynomially decaying cigenvalues, that is, we have
> S Opoly J for some constants Cpoly 7 > 0 and any j 2 1,
we can still truncate at dimension do and calculate [ddo) in (C.4) using the polynomial eigenvalue decay condition. It can be shown that ((do) decays polynomially in dg. Then, we can find proper dg by solving (C.12) and (C.21) and follow the same proof afterwards.
Proof of Theorem 4.3
Proof. Recall that d dimg (pp, 1/K). By Theorem 4. 12, it holds that Regret(T)) S /2H log |A| + /32H12T log(p/2) + H(dH + + 43HT,
(C.26)
with probability at least (1 p), where we set = /2 (K)) and
2 2H² log (P, 11 2H/p) + 4 H2 log(8K2
(C.27)
By Lemma C.2, we have
N1 (P, 11,.,)) $ log' (1/7)// log 111/
which implies there exists absolute constant C3 such that
2H² log (og((N llo,,) 211/p) + +4(H1 + /122/4 (8K < C.Hf2 log" (1/7)/11)//)))))) loggll// (1/T
In other words, (C.27) holds if set
8 C2H² log log (1/7)/7 11/
(C.28)
On the other hand, by Lemma C. we have
d < Cr log 2 (1g))1/7)/ 1111
(C.29)
19

---

Under review conference paper at ICLR 2021
Plugging (C.28) and (C.29) into (C.26), we obtain
Regret v 2HST. log A + - !I
+ CrHl2 log 2 (1/7)/7
+ +4/C,C,HTT (l/))//1/// log
log loggllg////// 1/2 (RT) /p)
$ CAV log (1/x)/y log
1ogg+)/((AART//))
(C.30)
with probability at least p). where C2 > 0 is an absolute constant. Thus, conclude the proof of Theorem 4.3.
D PROOF OF THEOREM 4.7
In this section, we prove Theorem 4.7, Similar the proof of Theorem 4.3, we upper bound the eluder dimension of Zp and log-covering number of P by the following two lemmas respectively.
Recall that BR is defined in (4.1). By the definition KNTK in (4.2), we have
HR (P ww S.t P(x) NN; (w w0) for any E)).
Without loss of generality, we assume entries of V NN, are linearly independent, which happens with probability one for most neural networks with nonlinear activation functions and random initialization.
Lemma D.1. Under Assumptions 4.6 and 4.4, there exists an absolute constant C10 such that
K A didmm(2p, 1/K) C1o log loggoo1 (1/7//7 log' (1/1((T))))))
Proof. Let t K A dimp(Zp. 1/K). By Definition 4.8, there exists sequence Zi.... Zt A x [0, HJS such that x, is (Zp, 1/ L/KK)-indep indeepeentn f1,..., Fr-1 for any E [t]. In other words, for any [t], there exist P1, P2 P such that
pp (x,) - 2p, (x;)) < 1/K2,
(D.1)
1=1
1zp, (x,) - zp, (x,) )| 1/K.
(D.2)
For any x = (s, V) ESXXX (0, H and P E P. we define
P(r; V NN T
T (w w
Using the reproducing property of H and the representation of K. in (2.2), we have
zp(x)= [ v(s)) P(s,a,8;;wdds
v(s') P(s,aas':w)ds' / v(s)). (P(s,a,s';w)) ((s,a,s';w) ds'
Ar ( v(s)) 0, (P, AAy 25)H
/ v(s') (P(s,a,s(;0)) P(s, a s w)) ds'
For any do such that de 2 4(1 - -)(( we define
Ep(x) = Σ VTy / V(8) (5(s, IP.VT, 2nyu
15i5d
20

---

Under review as a conference paper at ICLR 2021
for any x (s, a, V) E x x (J, and P P. And we have
Σ Vī / V(s') dy(s, VA 05)H
(zp(z) - 3p(x)] -
j2do
+ ((s)) - P(s,a, ds'
Σ Vīg H H j>do
s - (GHH((C2)) exp( (xp(-CCah/2) + Em H [(do) + HmHH, (D.3)
where the second inequality uses Assumption 4.2, |l S R. 11 , = 1, and the definition of Em in Condition 4.4, the third inequality follows from Lemma F.6, and r(d6) is defined in (C.4).
Then, using the triangle inequality, we have
(x.) - (x,)) S
Σ (lzA (2,) - -p,, + (do) + +22m H)²
<
Σ 2/2Ø/ (x:)) - (x;)) + 16t - r(do)² + 16152 !!?
1=1
2 k² + 16t r(do)² + 1615"
(D.4)
where the last inequality is by (D.I).
In the sequel, we establish an upper bound of 12p (2+) - Ep, For any 7 E [t], similar to (C.6))(C.8), we denote
= ((P1 - P2, VTr .1.............................. - P2, Ado (5o) T.
(D.5)
0r = (VTx : / V=(5') . (1(1,, ar, 5') d'dd''......... ds'...., VAdu / Vz(s') Ddo Qr, 8') (D.6)
A, = x (do + Σ nog.
(D.7)
Then, have
T-1
y JAA = d2 R²
11v112 + Σ v T 1;)²
1=1
dg Σ (P P2, A3 2312 + Σ
Epp (x:) - -xp, (2:))
R2
1=1
1=1
d2 4dg R2 + 22/K2 + 16t [(do)² + 16te2 H²
6/K² + 16t r(do)² + 16te 2 H² < </KK² + 16t I(do)2
(D.8)
Here the inequality uses (D.4), Condition 4.4, and
(Pi-P2. P2, Vr di < PP Pali IV 3ز S 4R² 1 4R2,
which follows from the fact | 1l,
P2lxx S and ||V 0illx for any j [dg]. By the
definitions of y in (D.5) and v, in (D.6), we can write εp, (x+) - (x,(2)) = (v, 2T), which by (D.8) upper bounded by
(,++) s.t. (1)) ANU ST/K² + 166 T(do)2
max o ERR
21

---

Under review conference paper at ICLR 2021
The maximizer of such quadratic program is
s' V (7/K2 + 161 (7 11) A Ur.
Therefore, have
(x+) Ep, (-+) S v (7/K2 16L (o. (o.T)))))) k.)))
(D.9)
On the other hand, by (D.2), (D.3), and Condition 4.4 we have
Ep (z,) (x,)1
2 lzn (I+) - 2n (x+)) (IEn (I+)) - 2P3 (1+()++) [2 (I+) - 21,(2))))
lpp, (x,) - zp, (,,)) (d)) - 22
1/K (T - 1/(2K) 1/(2K) (do).
(D.10)
We set do = [Õ log( 1/7)// 1og//
where Č defined Lemma E.7. Then, by Lemma F.7 it holds that db 2 4(1 (111-)))((2-- and
T(d)) - 1/(8tK).
(D.11)
Combining (D.9)-(D.1)), we obtain
1 A u, 7/K2 + 16t I(do)² 2 (1/(2K) (1/(2))11(4K3) 1/(4K))
(1/(2))-2(dd))
7/K² 11(4K33 1/100.
Following the same argument in (C.14)-(C.20) in the proof of Lemma C.I. obtain
S C10 2og2 (1/7)/7 log (KH))
for an absolute constant C1o > Thus, we conclude the proof of Lemma D.1.
Lemma D.2. Under Assumption 4.6 and 4.4, there exists an absolute constant C11 such that we have (a 1l..1) s Cn log (o/1((11/////1i1/ log 1+1/1 (RT))
for any R 2 2.
Proof. By choosing 4K Lemma F.7, there exists do (ogl/))/////////////// ( where C' defined in Lemma F.7, such that d, 2 4(1 - ()(C22) and
ldd)) < L/(4KH).
(D.12)
Here [(do) is defined in (C.4), y and C2 are defined in Assumption 4.6. Let C be minimal 1/(4d//2 K H)-H--oo -covering of the Euclidean ball (u Rdo ||ul|2 s R} with respect to the norm distance. For any P E P with parameter w, define P and P
P(x) NNNN( w00T (w w") do P(x) Σ
(P.0))x
j=1
for any x E V. Also, we write
u (v/1 (P.0i),....
V (P,o).))
22

---

Under review conference paper at ICLR 2021
Note that, because (v وززرم=1 is an orthonormal basis in H and w E BR, we have
||o||2 - 1| - || s R.
Thus, there exists 2" E C with ||0 u²112 - 1/(4d) 2 We define P E Ha by
do
Pr (*(x)
Σ of ==1
VA $5(+).
By the same arguments in (C.22) and (C.23), for any x E V, have
PP(x) - P(x) T(do), IP(x) (x) S 1/(4HH)
(D.13)
Then, by (D.12), (D.13), and Condition 4.4, for any x E V, it holds that
PP(x) P)(())) (x) - P( - P (z))
S Em + (do)) 1/(KH)) S 3/(4
(D.14)
Moreover, since Pa E Hn. there exists Wh E Bn such that
(*(x) NNNN: w (we )
for any æ E V. By Condition 4.4, we have
(x) - NN(x;w.) 5m $1/(4HH).
(D.15)
Combining (D.14) and (D.15), have
P(z) - NN(x; uN)r: S 1)(KH).
(D.16)
Note that because entries of V m N,,:N:5 w²) are linearly independent, w. is unique for any v: ||llaa
S
R. We define
Pc { PP::
NN(x; w.) for any x E EY}.
Then, by (D.16), Pc is (/(KK) of P with respect to the &xo distance. Following the same argument of (C.25), we have
(P 1) & N1/(KM) (P, lloo)
< |Pccl S |C| Cia do log(do RH) s Cn log)((/))// 1og
where Cia, Ci1 are absolute constants. Thus, we conclude the proof of Lemma D.2.
Proof of Theorem 4.7
Proof. Recall that K A dimp (Zv, 1/K). By the result of a general P in Theorem 4.12, we have Regret(T) S 22H3T log A + /22H22 log(p/2) + H(dH 11 d3HT,
(D.17)
with probability at least (1 p), when we set a = / 2o A {²(KH2) and
8 > 2H log(NN)rTP) (lo.,)) 2H/p) 4 + H2 / log 8K2 (k2 By Lemma D.2, we have
(D.18)
(P, (11111)),)))
(1,,1)) < Cn -1g2((4/1/77 (171)
23

---

Under review conference paper at ICLR 2021
which implies that there exists an absolute constant Cs such that
2H²² log log(N1)((K)) ll..1) 2H/p) + 4(411 + v /12/4 log(8K211/))
S CG log log (1/1)/7 log
In other words, (D.18) holds if we set
B 2 C&H² log (1/7)// (oTT+//((R//p))
(D.19)
On the other hand, by Lemma D.I, we have
S C10 (1/1)/7 1
(D.20)
Plugging (D.19) and (D.20) into (D.17), we obtain
Regret(T)) s Tog A + 22HHTTlog(p// H
+ C1 log (1 (1/1)// log 11/1
log (1+1/1)/2 (1 CG. log" (1/7)// log" 1+1 (lA[R/pp
+ +4/CcCinof log
(1/7)/7 1gggg(1////g/00
log (1+1//)) (RT/p)
with probability at least (1 - p). where Cg > 0 is an absolute constant. Thus, conclude the proof of Theorem 4.7.
E IMPLICIT LINEARIZATION
Two-layer fully-comnected neural networks: A two-layer fully-connected neural network is de- fined by
m/dy
1
NN(x:w)
/m/dy by 0x wy),
(E.1)
where, without loss of generality, assume is integer times of 2dy. Here is the activation function. The weight vectors w and b corresponding to the first layer and second layer, respectively, take the form
w [w]
W m/ dyy T
R", b (bi....,blr by bm )T Rm/dy,
respectively. During the training, we only tune the weights in w.
When initializing the neural network, we generate the initial weight Symmetric Initialization:
vectors w and by
W NOO 1/dy Idyxdy), wi w5tm/(2dyy) = w
by lid
Uni,((-1,1)), bjtm/(2dy) = -by
for any j E [m/))dy)]] As result of such initialization, have NN(:; w²) 0 and we can generalize the result to multilayer neural networks by setting the last two layers in this manner.
Proof of Lemma 4.5
Proof. Let NN be two-layer fully-connected neural network in the form (E.1). The activation function a is 1-smooth and the second layer weights satisfies by E [-1, for any j E [m/dy].
24

---

Under review conference paper at ICLR 2021
For any w Rm such that 1/ue w0112 - R. we have
NN, w) NN
m/dy
1
Σ
(x x112 110,o' (z wz) (x)))))))..
m/dy
j=1
m/dy
Σ
(d'a wz) d' (xTww)) (b,)² ||
m/dy
f=1
Note that, by the assumption that a 1-smooth, we have
(o'(x wy) - d'(x'' (w)))²²² s (x T wy uug 1 1|m w3112
Thus, have
m/dy
NN w) NN, m/dy
Σ
1la-- w311 s dy R22 /m.
(E.2)
By the mean value theorem, for any w 1|0 woll2 S R, there exists nt l|we - u0l12 S such that
NN(:; w) - NN(x;; w²)
(w Vo,N((:;; wt) ([ w
VWNN((;; wO) (w--ww-wl w0 (V -V (w =
combining which with (B.2) obtain
NN(x;) V NN w (ww (w-
[NN(I; NN(x; NNN(N w T w
(V wt) V.NN(a; w w))) (w (ww- w0
S (N V NN, 122 ||w w0 S dy 1/2 p2m 1/2
1/2 Therefore, have Em S Rm 1/2 Then, Condition 4.4 holds when
m 2 2 H²
Thus, we conclude the proof of Lemma 4.5.
F
SUPPORTING LEMMAS
F.1 DECOMPOSITION
For notational simplicity, define the linear operator JH for (k, [K] x [H] by
(s))))) (f a) ( s)), for any S, [0, SXA
Lemma F.1 (Martingale Decomposition). For any le E [K], we have
H V)((s)) V (of) = EDh, + Dia2) + Σ Q at) (r: att PA PP (hh at))):
25

---

Under review conference paper at ICLR 2021
where 1 and D22 take the forms
D (J - 0% (s)) (Q 2% "s ai)
D (PP h+1 Ps. h+1 (b att (V/+1 "
Moreover, we have D1122 = 0 for any E [ and the sequence
D1, D1, + D2,11 D2 + s.......,.. + D41,,
D1, Di,2 12,,, D22 D ... + D2.,1
(F.1)
a martingale difference sequence with respect the filtration (Fehe1 in Definition F.2 and each term is bounded by 4H.
Proof. For any (k. h) E [K] x [H]. by the definition of the operator JH we have
(s (sh)
23 ( (st))
= -Q - - > a (JR(Q) Q (s))))))))))))))))))))))))))(( - -Qh) 2 at).
(R2)
D
where we denote the second term on the right-hand side by 1 Also, we have
(h 0 de ( al)))
(Qh: ri Pn PnVnt hti (sh a
(PAVitT PP h+t ) at) (Q) r PA 1 (s ali)
(ii+r( virii (8 + (0) r PA V. (s ali
+ (IP Vt - PA V (sh at: (V V (
(F3)
Di.2
where we denote the third term on the right-hand side by Di.2. Combining (F.2) and (F.3) we obtain
(V% Vg (sh) (V h+ (5 V ( (st+1)) = Dh,1 Di + (Q): r PA V 1 az).
(F4)
Note that V& V (.) = 0 for any & E [K]. Using the identity (F.4) for h E [H] we have
V (s/) V=" (sf)
(V/ (s - -V, -V (sf)) - (1i4 v (sfitz))
=
#=1
Σ (Dk, DŽ + (Q) - r P..A aft))
h=1
H
Σ (D)., + Di,2) Σ
( at) - (ri(( at) + V af)))
hm1
26

---

Under review conference paper at ICLR 2021
In the sequel, we show that the sequence in (F.1) is a bounded martingale difference sequence with respect to the filtration (Fi)21. For any (k, h) [K] [H], by the definitions of D and D we have
DD D 1D 1I 2 S 4H.
When = 1, we have
B[D F (1 ((J Q7 ())((()))))))))))))})))))) (of o7 " ((s)),o) at) Fuu-1,ml (Ji( oi (5 (J Qi
3 (5()) =0
Here the second equality is because the only randomness conditional on 1, is af ~ xf(-1sf).
which is because, by our definitions of o ( Qf, and n², we have
210) * ()) ((K--1
Similarly, when 2, we have
(F.)
= =E[(Pr-1 V/2 Fn-1 V. ( ()) (6) - (Vr Vn - ( F((k,A-1)
= -PP--VV PA-1VE
- (P 1/+t - Pp- V/= xM (s) 1/-1) 0,
which is because the only randomness conditional on F F(( is ot Pn( (.1 -/ - and we have
B[D [F(km))1)] = E(B( (F x [
=0. 0.
(F.6)
Combining (F.5) and (F.6), we obtain
B(D + DÝ. [((())))))
Therefore, we conclude the proof of Lemma F.I.
Definition F.2 (Filtration). We define the time index map i(:; by
(kk, h) = (1 - +h,
for any (k, [K] [H], which is bijection from [K] [H] to [KH]. Then, for any (r, h)
[K] [H], we define Fi(k,K) as the o-algebra generated by
(r-,, s at. sh. anp r2,
T a , s of............................ sh
when h < H - 1, which are the reward functions and state-action pairs determined before 8 and
(r' s a). s/ az, r2 s4 af,
Sh aig rT+1).
when h H. which the reward functions and state-action pairs determined before sf + Then, the sequence hFe forms a filtration. Note that r- = [r h=1 are determined before the beginning of the 7-th episode although they are revealed the agent until the 7-th episode ends.
F.2 CONCERNTRATION
Let {(X,, Y,, }>>1 be sequence of random elements in X' x H for some measurable set X. Let Z be a set of [0, Calvul measurable functions with domain X' for some > 0. Let {F+)r2 be filtration such that for any 2 1, (X1, Y,, X Yx-1,X,) is 1-=1-measurabbl and there exists x E 2 such that E [ = 2" (X+) holds. The least-squares predictor given
27

---

Under review conference paper at ICLR 2021
((X,, == is defined by
Σ = argmin ZEZ
(x(X,)- - -Yz)²
(F.7)
We say that rj conditionally -aussian given F, F for any 1 for any À I.
log (())p(An)) F+1 = 12
For any > O, we denote by NV | the E-covering number of Z with respect to the supremum norm distance || 22 = sup,ER (z(2) - 22(2)) For any > 0, we define
2((3) - = z: -
2 (x+)) $3).
(F88
Lemma F.3 (Proposition 6 of Russo & Van Roy (2014)). Assume that for any t E N, Y, 2* (X,) is conditionally o-sub-Gaussian given Ft-1. Then, for any > 0 and d E [0, 1], with probability at least - 8), it holds that =* (8, E)) for any E N. where
8( So?. (N, I| (1x))/6) + 4le + / (ogglo(41((1 (1((+1)/6))
Lemma F44 For any 8 [0, 1], we let
B 2H² log (N (P, (l,o,)) H/8) + 4(H + V H22/4 log 44²²H/8)
Algorithm I, then, with probability at least (1 - 6), for any (k: h) [K] x [1]. we have Ph. E Pk.
Proof. Recall that, for any E P, we define zp :8:xx Ax x HJS + 10, H] by
=p(0, a v()) V(8) P( ()) v(s,aV E Ax (0, HJS.
Let 2 = Zp 1zp E P). For any h) [K] x [.. set Y2 Vh++1 (s Xx (s), a Vk (-)). and Fi(RA) defined in Definition F.2. Then, by the definitions of Ph in (3.4) and (x in (F.8), we have (x)3) (=p: P PET p))) By setting
2P,,- Then, Y, (X,) is conditionally Ef/2sub--Gaussine given
8 2H² logooo/ H/8) + 4(H + v H2/4 (og(4K2H/8)
in Algorithm 1, it holds that
B > 2H² lllooo log(N1/x(2)) H/0) + 4(k - 4(k-1)KK (H + / H2// H/2/441oo(44//) 11)H/0((()HH0)
3 16/H,
for any h [K], where 8 (6-16//11/KK) defined in Lemma F.3. Applying Lemma F.3 with C' = H, with probability at least (1 - (1-8/H) H). for any &o [K], we have
z* E (6/ C (x))
which implies Pa. E .pk Using the union bound over all E [H], with probability at least (1 8). for any (ki, H) E [K] x [H] we have PA. E Pk.
28

---

Under review conference paper at ICLR 2021
In the sequel, we prove that (2, l1=)) s (P, II .llx..) for any & >>> 0. Indeed, this is obtained by the observation that, for any 2p, Tp E 2 with P,P' E P, we have
V(s') P(s' as ds' / V(s') P'(s' (s, ds' 18
2| 200
sup ())
JS
- P' (s, = -.H.1. - - P 00.10
sup (s.
Thus, we conclude the proof of Lemma F.4.
F.3 ELUDER DIMENSION
Recall that Z is set of [0, -alluleed functions with domain X for some C >> 0. Mcanwhile, (x) defined in (F.8).
Lemma F.5 (Lemma 5 of Russo & Van Roy (2014)). For any 8 > 0, we have
K
Σ
sup 22x
[z(x)) - - s1+ 4.4.4..BB /BK,
k=1
where d K dimm(2,1/K)
Proof.
When dimp dimm (2,1/K) I K. by Lemma 5 of Russo & Van Roy (2014) we have
Σ sup (B)
(2(xk) - 2 (xx)] s 11+0 C- dimg(2,1/K) + + v (2
+1+ d d / /d3..
When dimg (2,1/())))) K, since Z set of [0, Cl-valued functions and Zx(3) Z for any and B, we have
K
(x(xx) - 2'(xx)1 S KC $1+ 4. d3K.
sup (2)))
1=1
Thus, conclude the proof of Lemma F.5.
F.4
OTHER USEFUL INEQUALITIES
Lemma F6. For any 7 E (0, 1/2), C2 > O, and any do E N such that
dg 2 4(1 - -)(
(F9)
it holds that
Σ exp(-C2j7/2) < 4dh (7C22) exp(-
jodd
Proof. By basic calculus we have
2dp /()C2) exp(-Czdh/2)
(-2 (-26 exp(-C2t7//) -
1 (1-2(1 2(1 7)t -)t exp( CCt /2t dt do
> (1- - 2(1 7)d (306/(((()) // exp(-C2f7 C2f7/2)dt dt,
29

---

Under review conference paper at ICLR 2021
where the inequality is because 1 7 0 and 1 v do for t 2 do. Thus, we obtain
/d/
2xp(-C2f/2)dtt 1 2(1 (611-1)00 2(112))6" (77O2) exp( exp(-C2d,/2) /2) - /(yC2) exp(-C2dh/2) /2),
where the last inequality is because - 2(1 - >))d (1/22) 2 1/2by by (F.9). Then, by the fact that
Σ exp(-C2j1) - - Opp(-Ct?))t.
1=
j>do
we conclude the proof of Lemma F.
Recall that (dd)) is defined in (C.4).
Lemma E.7. Let C and C2 be the absolute constants in Assumption 4.2. There exists an absolute constant C' such that for any 10,) t 2 1, and R 2 2, if we set
do [č log( log(1/n)/7 log (tRHH),
then it holds that dg 2 4(1 - ()) and
r(ds) C/ dg RH exp(ex2pfp) s 1/t.
(F.10)
Proof. For any 0, we consider the function
f(x) = ==//2", x O.
Taking derivatives, we have
e" x= (x: y)
f'(x)
22y
Note that f'(x:) 2 if and only if x S y. which implies f(x) 2 f(y) for any x > Reorganizing
the inequality, obtain
(ex/v))
for any æ > 0 and > 0. Applying the above inequality via choosing
x C2d./4 y= (1
we obtain
exp(C2dh/2)
-
C
exp(C2dl/4 /4)
exp(C2db//)
H((2R(((C2)-
1 H2(2HR((22)--
(eCzdh/ /4-
exp(C2dB /4)
(eC2/4 /4- -
exp(C2d7/44
Thus, to obtain 10), suffices to make the following inequality hold,
+C2/2 RH
exp(C2d,/4)
7C2(CC2/4 -
30

---

Under review conference paper at ICLR 2021
which is equivalent to
1 log C2
1 R.
117
do 2
yC2(cC2/4 2
Since y E 10,1 and tRH 2, there exists an absolute constant Č such that
4(1 - (11-))()C2) ő lo//))
tC//2111 HR C log
4/C2- log
C2(e02/44 1-n)=
Therefore, by choosing do 2 (Clog(1/7)/7) log(tRH)) we conclude the proof of Lemma E.7.
G EXAMPLES OF KERNELS WITH EXPONENTIALLY DECAYING EIGENVALUES
In this section, we provide examples of kernels that satisfies Assumption 4.2. We let y gdy-1 which represents the unit sphere in Rdy For any kernel K, we define the integral operator Tk: T,²()) > ())) by
(Tef)())= / Kao(a, (2) du(y), for any f E L2) and æ e y
(G.1)
where j is the uniform measure on V.
G.1 SQUARED EXPONENTIAL KERNEL
The squared exponential kernel is defined as
(x, v) = exp(-1/22 -11x -11)), for any x, y E V,
(G.2)
where the constant satisfies 122 2/dy. For any u E [-1, 1]. we define k(u) exp(-2(1 and
-2(1 - -))
(idy)- 11/2) (v) = [((2j dy 1)/2) - u1l 13
d (2))) (1 ud) -3/ (G.3)
where, with a slight abuse of notations, use r(-) to denote the Gamma function in this section.
Lemma G.1 (Theorem of Minh al. (2006)). For the kernel K defined in (G.2), the eigenvalues (pibzz (without duplicates) of the corresponding integral operator Tx... take the form
gdy
k(u)) (y dy) (1 u²) 2²) (ddy-31/2
3)/2 du.
Pj gdy
and each Pj has multiplicity
N(J) (2j + dy - 2) (dy + - 3)! j.(dy 2)!
(G.4)
Moreover, when 2 > 2/dy, we have that {pz}521 in decreasing order and satisfies
Pj > A
(2)
(2j + dy - (2/
Pj < 42
(
(2j + dy - 2) (2j (2j+dy
(G.5)
31

---

Under review conference paper at ICLR 2021
for any j 2 1, where the constants A1, A2 only depend on dy and 6.
By Lemma G.I, the eigenvalues {11321 (with duplicates) of the kernel Kn satisfy, for any j 2
Aj Pt: for & such that Σ N(1) < Σ N(1.
(G.6)
By the definition of (j) in (G.4) and Stirling's formula, we have
NG) (2) + dy 2) (dy + --3))/2 I(dy + 3)/e|
(G.7)
jr/2 (j/e)²
Here the asymptotic notation omits constant factors that are independent of Combining (G.6) and (G.7), when j is sufficiently large, have
AS Pt: for such that (t - 1)dy-1 <j issa 5
Then, by (G.5) we obtain
X1 = ((( 1e
(2ji/dy +dy (dy-2)-tl -d =0ee -(e-osliiyy
(G.8)
as j + oo for an absolute constant c > 0. Thus, we know K satisfies the second condition of Assumption 4.2.
G.2 NTK OF SINE ACTIVATION
We consider the neural tangent kernel of two-layer neural network of the form (E.1) where the activation function is the sine function. In detail, the neural network is parametrized as
m/ m/dd++1)
NN(:; w. V m m/(dy + 1)
by sin(x wj + 1j)
for any x E y. Here we modify the initial form in (E.1) by adding an intercept term, which is equivalent adding one more dimension with constant value the input space. The initialization of the network weights follows the same symmetric random initialization scheme
by iid. Unif([-1,1]) bj+m/(2dy+2) by,
iid. wy N(O,, Iay), Wj+m/(2dy+2) = WWy
1, Ltd. Uni (T))), 15+m/(2dy+2) =
j E [m/(2dy + 2)). Here without loss of generality we assume m m/(2dy + 2) N. Then, the population NTK of such parametrization takes the form
Kntk (z. y) = 2 Ew LL-Uni(([ (, y cos(x W + L) cos(y) W + L)]
[122
= x T y exp -1 //1/22
= x expfx
1/.
for any y E Vr which is the limit of the empirical NTK defined (4.2) as goes infinity. Here the second equality is derived in Rahimi & Recht (2007) and the third equality is by the fact that for any x, y E
||æ||| ||y||a
11
For any j 2 1, let V, be the set of all homogeneous harmonics of degree j on gdy-1 which is finite-dimensional subspace of L (1d the space of square-interrable f'unctions on gdy-1 with respect to μ. It can be shown that the dimensionality of 3/, is given by N(j).
32

---

Under review conference paper at ICLR 2021
Lemma G.2 (Funk-Hecke formula (Müller (2012), page 30)), Let 1: : [-1,1] + R be a continuous function, which gives rise inner product kernel K on S x Sdy-1 with the definition
K(x, v) (2 y), for any x. y gdy-1
Then, for any f Jj, gdy-1, we have
Jes- ((x,y)((1) du(y)
184y-21
S
33/2 sw) [(x), [2(()) P,()) (1 -1- -1-12)(dd (2)(dy-3)/22
-dy-1|
where (u) is defined in (G.3).
We let (u) = u exp(u - 1}. Recall the definition of in Section G.I, we have k2(u) = u ku))
for = v2, which satisfies the requirement Lemma G.1. Lemma G.2 shows that the eigenvalues {/j (with duplicates) of Tx takes the form
5. = Cp. S Ta(w)- Py()) (1 - (2)(dy-3)) du
Cp. [" u.k(()) Pv(()) (1 =2) 31/2 du.
where Cp = (gd (gdy 21/1(dd 11. Using the relation
u (u) 2j + dy 2 PP-i(u)+ + jt dy - 2
j
2j dy -2 Pp),(u),
which is from the definition of (y( we have
p. = Cp 2 + dy - PO-1 + + dy - 2j + dy - 2 p/+1)
where {pjb21 are the eigenvalues of the operator Tk., studied in Section G.1 with + = V2. Thus, following the same argument of (G.6)-(G.8), we know such NTK satisfies the second condition of Assumption 4.2.
33


Reviews:
[{"review_id": "oocmOKVHPI4", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper propose a novel policy optimization algorithm that allows general function approximation (i.e., kernel function approximation, neural function approximation) that go beyond linear approximation, the algorithm achieves exploration by absorbing optimism into policy evaluation. An \\sqrt{T} regret bound of the proposed algorithm is obtained.\n\nOverall, this paper is very well-written, the problem is well-motivated, and the claims and proofs looks solid.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Or1tCtYv2c", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an optimistic policy optimization algorithm. It is theoretically shown that the algorithm has sublinear regret for multiple model classes such as kernel function and NTK. The policy update rule also allows the algorithm to have sublinear regret for  adversarial reward function. The technique for analyzing nonparametric model classes can potentially be extended to other reinforcement learning algorithms based on optimism.\n\nWhile the algorithm itself is neat and clean, the paragraph describing its implementation is not very rigorous. In particular, how is Line 13 computed? Note that for general value function approximation, the state space is usually large (or even infinite).  If I understand correctly, there is no assumption about the structure of Q-function in this paper. How is the Q-function even stored, or parameterized? \n\nA similar question is that, the last few sentences before Sec 4 says \"it suffices to solve a least-square regression problem\". Does it mean that $Q_h^k(\\cdot\\mid\\cdot)$ is computed by doing a regression problem where the target is r+clamp...? If this is the case, can the Q-function be solved exactly? Can the algorithm work for the case where the regression error is small but not zero?\n\nIt seems to me that the analysis for general function class is different to those for kernel function and NTK, so I'm wondering that are there any upper/lower bounds for the Eluder dimension of the two non-parametric classes described in this paper? Besides that, the regret upper bound given by Theorem 4.3 and 4.7 depends on parameter $\\gamma$. In what scenario the parameter $\\gamma$ is lower bounded by some constant?\n\nMinor issue:\n- In Eq. (3.1), Page 3: should the policy be $\\pi_h^k(a\\mid s)=\\frac{\\exp(E_h^k(s,a))}{\\sum \\exp(E_h^k(s,a))}$?\n\nOverall, the results are solid and interesting. Therefore I would recommend a acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GtGcAwu3w0m", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary:**\n\nThis paper proves a regret bound for an optimistic variant of a policy optimization algorithm in an advsersarial reward setting. The paper extends prior work in this setting by considering function classes with bounded Eluder dimension instead of linear functions. This yields guarantees for a kernel-based variant of the algorithm (which also apply to neural kernels like the NTK).\n\n--------------------------------------------------------------------\n\n**Strengths:**\n\n1. More general than prior work. The main strength of this paper is to extend the work of Cai et al. (2019) beyond the Linear MDP setting to one with a kernelized transition matrix. This essentially requires introducing some results based on the Eluder dimension from Russo and Van Roy (2014). The paper helps to fill out this line of research by showing that the algorithm from Cai et al. (2019) does indeed work when the linear MDP is replaced by a kernelized one.\n2. The proofs seem to be correct.\n\n--------------------------------------------------------------------\n\n**Weaknesses:**\n\n1. Setting seems unrealistic. The paper assumes that the *entire reward function* is revealed after each episode rather than only seeing the rewards at the visited states. This is integral to the algorithm since this reward function is then queried at new state, action pairs. I understand that this allows for adversarial reward functions and is the same assumption from Cai et al. (2019), but it seems unrealistic and unmotivated. I cannot think of a problem where the *entire reward function* would be revealed at the end of each episode, and without this assumption the entire algorithm and argument seem to break down.\n2. Calling this algorithm policy optimization seems misleading. The algorithm requires using the kernel-based approximator to learn not just a model, but an entire confidence set over models. In the usual RL nomenclature this would seem to be a model-based algorithm. While the policy is not simply attained by planning in the learned model, having to learn these models seems to make the algorithm indeed model-based. This would not be so important except a major motivation for the paper in the abstract and intro is to provide guarantees for model-free policy optimization algorithms like the policy gradient algorithms that are often used in practice. This motivation does not align with the algorithm the paper is actually analyzing.\n3. The main assumption is not clearly explained. The main assumption in the paper is that the transition kernel is in some RKHS, but the paper never explains what this assumption means and which sorts of MDPs it may apply to. It is more general than the Linear MDP, but how much more general? Moreover, the introduction makes it sound like the function approximation assumption is merely for the policy class, but in fact the approximator must be able to represent the entire transition kernel, which is potentially much more complicated. \n4. Novelty. To me the paper is only an incremental improvement over the results of Cai et al. (2019). Specifically, extending results from a linear setting to a kernel setting provides a technical challenge, but it is not clear how much insight is gained. The main result follows quickly from combining the results on Eluder dimension from Russo and Van Roy (2014) with thos of Cai et al. (2019). \n5. Algorithm seems computationally infeasible. The algorithm requires maximizing an integral over the entire state space against over a set of measures defined by a confidence set over models in the RKHS at every step. The paper argues that the algorithm can be implemented with supervised learning oracles, but having to solve several supervised learning problems at each step of training over all historical data seems quite inefficient. In short, this is not an algorithm that a practitioner would attempt to implement.\n\n--------------------------------------------------------------------\n\n**Recommendation:**\n\nI recommend to reject this paper, and gave it a score of 4. While the paper is a logical extension of some prior work, I am not convinced of the usefulness of the setting or algorithm proposed.\n\nIf the authors can provide better motivation for the setting, novelty, and practical value of the contribution, I would consider raising my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "0KAd5rhJvRg", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper claims to study the sample efficiency in policy optimization with general function approximation. Specifically, the authors propose an algorithm with transition model approximation and analyze the regret when adopting RKHS or function classes with bounded Eluder dimension. The results also apply to neural networks in the NTK regime.\n\n-----------------------------------------------------------------------------------------\n\nReasons for score:\n\nThe theoretical understanding of RL with function approximation is an important issue. It is nice to see that the paper provides a wide-ranging discussion under this topic. My major concerns are about the novelty and clarity. The paper investigates many interesting scenarios, but disappointingly, none of them is satisfyingly addressed.\n\n-----------------------------------------------------------------------------------------\n\nPros:\n* The paper goes beyond tabular MDP and finite-dimensional linear function setting. The use of RKHS and Eluder dimension makes the results more general.\n* The paper connects reinforcement learning with neural network and attempts to provide a unified theoretical explanation for the empirical successes in deep RL.\n\n-----------------------------------------------------------------------------------------\n\nCons:\n* In introduction, the authors claim to study a policy-based approach but their algorithm turns out to be a model-based one.\n* The paper seems only a combination of Cai et al. (2019) and Ayoub et at. (2020) using RKHS and Eluder dimension techniques. Admittedly, the extension needs some work, however, the results do not provide much more insights compared with Cai et al. (2019).\n* Assumption 4.2 is too restrictive. It assumes the eigenvalues of kernel to decay exponentially fast. A discussion of power law spectral decay would definitely improve the quality of the paper. In Assumption 4.6, it is also unclear why exponential spectral decay is a reasonable assumption on NTK.\nThe authors refer to Srinivas et al. (2019) and Yang & Salman (2019) to justify their assumptions. However, it seems to the reviewer that Srinivas et al. (2019) considers all finite spectrum, exponential spectral decay and power law spectral decay. Also, Theorem 3.1 in Yang & Salman (2019) shows a power law for NTK and does not support Assumption 4.6.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers appreciated the aim of the work, they found the technical contribution to be too incremental to be of sufficient interest and the exploration of the problem and its significance to be incomplete in the paper's current state.
Decision: Reject