OPTIMISTIC POLICY OPTIMIZATION WITH GENERAL FUNCTION APPROXIMATIONS
Year: 2020

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 √ 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.

text: √ 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.

heading: 1 INTRODUCTION
text: Reinforcement learning with neural networks achieved impressive empirical breakthroughs (Mnih et al., 2015; Silver et al., 2016; 2017; Berner et 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 a lack of computational and statistical efficiency in practice, which calls for the principled design of efficient algorithms. Specifically, in terms of computational efficiency, the recent progress (Abbasi-Yadkori et 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 a 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 particular, 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.
In this paper, we aim to provably achieve sample efficiency in model-based policy optimization, which is 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); Osband & Van Roy (2014); Ayoub et al. (2020); Wang et al. (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 it through policy improvement. In particular, we establish a κ(P) · √ H3T -regret 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 κ(P) is
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-dimensional model classes.
Our work is related to the study on computational efficiency of policy optimization (Fazel et al., 2018; Yang et al., 2019; Abbasi-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 a 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 on 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., 2010a;b; Zimin & Neu, 2013; Neu et 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 settings. 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 a type of optimistic estimation is innovated by Russo & Van Roy (2014) in the bandit problem. In particular, to characterizing the optimism and accuracy of the optimistic 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 of kernel and neural function approximations.

heading: 1.1 NOTATIONS
text: We denote by ‖ · ‖p the `p-norm of a vector when p ∈ N or the spectral norm of a matrix when p = 2. For any two distributions p1, p2 over a discrete set A, we denote by DKL(p1 ‖ p2) the KL-divergence
DKL(p1 ‖ p2) = ∑ a∈A p1(a) log p1(a) p2(a) .
For any a, b, x ∈ R, we define the clamp function
clamp(x, a, b) =  b, if x > b, x, if a ≤ x ≤ b, a, if x < a.
(1.1)

heading: 2 PRELIMINARIES

heading: 2.1 ONLINE REINFORCEMENT LEARNING WITH ADVERSARIAL REWARDS
text: We consider an episodic MDP (S,A, H, {Ph}Hh=1, {rh}Hh=1), where S is a continuous state space,A is a discrete action space, H is the number of steps in each episode, {Ph}Hh=1 represent the unknown transition model, and {rh}Hh=1 represent the reward function. In particular, for any h ∈ [H], Ph represents the transition kernel from a state-action pair (sh, ah) at the h-th step to the next state sh+1, while rh represents the reward function at the h-th step that maps a state-action pair to a deterministic reward. Moreover, we allow the reward function to vary across episodes and denote by rkh the reward function at the h-th step of the k-th episode. In particular, rkh 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 a fixed state s1 and all rewards fall in the interval [0, 1].
For any h ∈ [H], a policy πh 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 a collection as a policy when it is clear from the context. For any (k, h) ∈ N× [H], given a policy π and reward functions {rkh}Hh=1, the value function and Q-function at the h-th step of the
k-th episode are defined by
V π,kh (s) = Eπ [ H∑ j=h rkj (sj , aj) ∣∣∣ sh = s], Qπ,kh (s, a) = Eπ[ H∑ j=h rkj (sj , aj) ∣∣∣ sh = s, ah = a]
for any (s, a) ∈ S × A. Here the subscript π in the expectation Eπ[·] 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 a sequence of policies {πk}k≥1 and minimize the regret
Regret(T ) = max π K∑ k=1 ( V π,k1 (s1)− V πk,k 1 (s1) ) , (2.1)
where K is the number of episodes and T = KH is the number of steps taken by the algorithm.

heading: 2.2 REPRODUCING KERNEL HILBERT SPACE
text: We say H is a reproducing kernel Hilbert space (RKHS) on a set Y with the reproducing kernel K : Y × Y → R if there exists an inner product 〈·, ·〉H such that, for any f ∈ H and x ∈ Y , we have f(x) = 〈f,Kx〉H. Here Kx represents the function K(x, ·), which is the Riesz representation of the evaluation functional at x (Schölkopf et al., 2002). When the reproducing kernel K is continuous, symmetric, and positive definite, Mercer’s theorem (Steinwart & Christmann, 2008) says K has the representation
K(x, y) = ∞∑ j=1 λjφj(x)φj(y), for any x, y ∈ Y, (2.2)
where {φj}∞j=1 is an orthonormal basis of L2(Y) and λ1 ≥ λ2 ≥ · · · ≥ 0. See more details on RKHS in Section A.

heading: 3 ALGORITHM
text: Framework: Before the k-th episode begins, we construct the policy πk based on πk−1 and {Qk−1h }Hh=1, which are the policy in the (k − 1)-th episode and estimators of {Q πk−1,k−1 h }Hh=1, respectively. Then, we execute the policy πk in the k-th episode and correspondingly update the Q-function estimators {Qkh}Hh=1 using the reward function {rkh}Hh=1, which is observed after the k-th episode ends.
Policy Improvement: For any (k, h) ∈ [K]× [H], we parametrize πkh by
πkh(a | s) = exp{Ekh(s, a)}∑
a′∈A exp{Ekh(s, a′)} , for any (s, a) ∈ S ×A. (3.1)
Here Ekh is the potential function, which is initialized as the zero function and updated by
Ekh(s, a) = E k−1 h (s, a) + α ·Q k−1 h (s, a). (3.2)
Here α > 0 is the stepsize of policy improvement. Equivalently, we have πkh(· | s) ∝ πk−1h (· | s) · exp ( α ·Qk−1h (s, ·) ) for any s ∈ S. To see (3.2) is a policy improvement step, note that πkh is the maximizer of
Lkh(πh) = Eπk−1 [ 〈Qk−1h (sh, ·), πh(· | sh)〉A + α −1 ·DKL ( πh(· | sh) ∥∥πk−1h (· | sh))].
This is the same as the update in Politex (Abbasi-Yadkori et al., 2019a), which originates at MDP-E (Even-Dar et al., 2009). It is also very close to a slightly changed variant of the one-step objective in the proximal policy optimization (PPO) algorithm (Schulman et al., 2017; 2015).
Policy Evaluation: Let P be a known class of transition models such that Ph ∈ P for any h ∈ [H], which is specified in Section 4. Also, for any P ∈ P , s ∈ S, a ∈ A, and V : S → [0, H], we define
zP (s, a, V ) = ∫ S V (s′) · P (s′ | s, a) ds′. (3.3)
For any (k, h) ∈ [K] × [H], we construct a confidence set of the transition model Ph and correspondingly the optimistic Q-function estimator Qkh 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 kH+1 be the zero function. Inspired by Ayoub et al. (2020), given the optimistic value function estimators {V τh+1} k−1 τ=1 from the first (k − 1) episodes, we construct the confidence set Pkh of Ph by
Pkh = { P ∈ P ∣∣∣ k−1∑ τ=1 ( zP (s τ h, a τ h, V τ h+1)− zPkh (s τ h, a τ h, V τ h+1) )2 ≤ β}, (3.4) where P kh = argmin
P∈P k−1∑ τ=1 ( V τh+1(s τ h+1)− zP (sτh, aτh, V τh+1) )2 for a threshold β > 0, which represents the degree of optimism. Then, for any (s, a) ∈ S ×A, given the optimistic value function estimator V kh+1, we define the optimistic Q-function estimator Q k h by
Qkh(s, a) = r k h(s, a) + max
P∈Pkh zP (s, a, V
k h+1) (3.5)
and correspondingly update the optimistic value function estimator by V kh (s) = 〈Qkh(s, ·), πkh(· | s)〉A for any s ∈ S . We apply the clamp function defined in (1.1) to the second term on the right-hand side of (3.5) to ensure it falls in the range [0, H − 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 to solve the constrained minimization problem in Line 11 of Algorithm 1. In particular, for kernel function approximations in Section 4.1, it reduces to a convex optimization problem, which allows the PSGD algorithm to converge to a global minimizer. Meanwhile, for neural function approximations, it reduces to an approximately convex problem in the overparametrized regime (Arora et al., 2019), which leads to the same global convergence guarantee. Also, to implement Lines 12 and 13 of Algorithm 1, it suffices to solve a constrained maximization problem (Feng et al., 2020), where the constraint is defined in Line 12. The Lagrangian relaxation of such a constrained maximization problem can be solved by the PSGD algorithm in the same manner of Line 11. In addition, to instantiate the update of Qkh in Line 13, it suffices to solve a least-squares regression problem. In summary, we can instantiate the aforementioned steps through supervised learning oracles, which can be implemented in a computationally efficient manner.

heading: 4 THEORY
text: 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 classP , while in Section 4.3, we characterize the regret for a general P , which serves as a meta result. An informal version of the results is given in the following theorem.
Algorithm 1 Optimistic Policy Optimization with General Function Approximations 1: Input: number of episodes K, model class P , stepsize α, threshold β 2: Initialize π0 as the uniformly random policy 3: For k = 1 to K do 4: Start the k-th episode and receive the initial state sk1 5: For step h = 1 to H do (policy improvement) 6: Update the policy by πkh(· | s) ∝ π k−1 h (· | s) exp{αQ k−1 h (s, ·)} for any s ∈ S
7: Take the action akh ∼ πkh(· | skh) and receive the next state skh+1 8: Observe the reward function {rkh(·, ·)}Hh=1 9: Initialize V kH+1(·) as the zero function
10: For step h = H to 1 do (policy evaluation) 11: P kh ← argminP∈P ∑k−1 τ=1(V τ h+1(s τ h+1)− ∫ S V τ h+1(s
′)P (s′ | sτh, aτh) ds′)2 12:
Pkh ← {P ∈ P : k−1∑ τ=1 ( ∫ S V τh+1(s ′)P (s′ | sτh, aτh) ds′ − ∫ S V τh+1(s ′)P kh (s ′ | sτh, aτh) ds′)2 ≤ β}
13: Qkh(·, ·)← rkh(·, ·) + clamp(maxP∈Pkh ∫ S V k h+1(s
′)P (s′ | ·, ·) ds′, 0, H − h)

heading: 14: V kh (·)← 〈Qkh(·, ·), πkh(· | ·)〉A
text: Theorem 4.1 (Informal Version of Theorems 4.3, 4.7, and 4.12). With proper choices of α and β, the regret of Algorithm 1 satisfies
Regret(T ) = Õ ( κ(P) · √ H3T ) with high probability. Here Õ omits absolute constants and logarithmic factors of H , T , and |A|, while κ(P) 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π ∑K k=1 V π,k 1 (s1), the average regret of Algorithm 1, namely Regret(T )/T , converges to zero at a sublinear rate. In other words, at least one of theK policies attained by Algorithm 1 achieves a vanishing optimality gap with respect to the varying reward function across the K episodes. The model capacity κ(P) is specified in Sections 4.1 and 4.2 for kernel and neural function approximations, respectively. To establish such specific results, we characterize κ(P) using the eluder dimension for general function approximations in Section 4.3, which serves as the unified analysis.

heading: 4.1 KERNEL FUNCTION APPROXIMATIONS
text: Let P be a subset of an RKHS H with the reproducing kernel K, which has the representation in (2.2). In detail, let S be a 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 |A|, where |A| denotes the number of actions. Meanwhile, let Y be a dY -dimensional set such that S × A × S ⊂ Y . We assume there exists R ≥ 2 such that P ⊂ HR, whereHR 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 |K(x, y)| ≤ 1, |φj(x)| ≤ 1, and λj ≤ 1 for any x, y ∈ Y and j ∈ N.
(ii). There exist a threshold γ ∈ (0, 1/2) and absolute constants C1, C2 > 0 such that λj ≤ C1 · exp(−C2jγ) for any j ∈ N.
Note that we can replace the 1’s in the upper bounds of Assumption 4.2 with any absolute constant, which is reflected in the H-norm of any function in H. Meanwhile, we can relax |φj(x)| ≤ 1 into |λτj · φj(x)| ≤ 1 for any absolute constant τ ∈ [0, 1/2), which leads to the same regret. We have the following result on the regret of Algorithm 1.
Theorem 4.3. Suppose Assumption 4.2 holds andP ⊂ HR. There exist absolute constantsC3, C4 > 0 such that, for any p ∈ (0, 1), if we set
α = √ 2 log |A|/(HT ), β = C3H2 · log1+1/γ(RT/p) · log2(1/γ)/γ
in Algorithm 1, then it holds that
Regret(T ) ≤ C4 √ H3T · log1+1/γ(|A|RT/p) · log2(1/γ)/γ
with probability at least (1− p).
Proof. See Section C for a detailed proof.
Theorem 4.3 indicates that log1+1/γ(|A|RT/p) · log2(1/γ)/γ serves as the model capacity κ(P) in Theorem 4.1 for kernel function approximations. In particular, we can obtain γ for a broad range of reproducing kernels K (Srinivas et al., 2009). Meanwhile, we can scale R to control the model capacity κ(P) (Schölkopf et al., 2002).

heading: 4.2 NEURAL FUNCTION APPROXIMATIONS
text: Let P be a set of overparametrized neural networks. In detail, we denote by NN a neural network with its weights collected in a vector w ∈ Rm. Let w0 be the random initial weights. For a radius R ≥ 2, we define
P = {P : ∃w ∈ BR, s.t.P (s′ | s, a) = NN(x;w), for anyx = (s, a, s′) ∈ S ×A× S ⊂ Y}, where BR = {w ∈ Rm : ‖w − w0‖2 ≤ R}. (4.1)
Without loss of generality, we assume NN(x;w0) = 0 for any x ∈ Y , which can be achieved by a symmetric initialization scheme. See Section E for a detailed explanation. To connect with the result for kernel function approximations in Section 4.1, we define the following condition. Condition 4.4 (Implicit Linearization). It holds that
ξm = max x∈Y,w∈BR
|NN(x;w)−∇wNN(x;w0)>(w − w0)| ≤ 1/(4K3/2H).
Condition 4.4 indicates that NN(x;w) is uniformly close to the linear function∇wNN(x;w0)>(w− w0) of w. In particular, the linearization error ξm is 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 (Overparametrization). Suppose NN is a two-layer neural network, where the activation function is 1-smooth, and it holds that ‖x‖2 ≤ 1 for any x ∈ Y . Then, Condition 4.4 holds when m ≥ dYR4K3H2.
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 (ReLU), and multilayer neural networks (Allen-Zhu et al., 2019; Du et al., 2019; Zou et al., 2020; Gao et al., 2019), which ensures Condition 4.4 holds. The linear function of w in Condition 4.4 induces an RKHSH with the reproducing kernel
KNTK(x, y) = ∇wNN(x;w0)>∇wNN(y;w0), for any x, y ∈ Y, (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 w0. When m goes to infinity, such an empirical NTK converges to its expectation, which gives the population NTK. It is shown in Yang
& 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 C5, C6 > 0 such that for any p ∈ (0, 1), if we set
α = √ 2 log |A|/(HT ), β = C5H2 · log1+1/γ(RT/p) · log2(1/γ)/γ
in Algorithm 1, then it holds that
Regret(T ) ≤ C6 √ H3T · log1+1/γ(|A|RT/p) · log2(1/γ)/γ
with probability at least (1− p).
Proof. See Section D for a detailed proof.
In parallel with Theorem 4.3, Theorem 4.7 indicates that log1+1/γ(|A|RT/p) · log2(1/γ)/γ serves as the model capacity κ(P) in Theorem 4.1 for neural function approximations, which can be controlled by scaling R (Arora et al., 2019).

heading: 4.3 GENERAL FUNCTION APPROXIMATIONS
text: Let P be a 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 Z be a set of real-valued functions on the domain X . For any ε > 0 and τ ∈ N, we say xτ ∈ X is (Z, ε)-independent of x1, . . . , xτ−1 ∈ X if there exist f1, f2 ∈ Z such that(τ−1∑
j=1
|f1(xj)− f2(xj)|2 )1/2 ≤ ε, |f1(xτ )− f2(xτ )| > ε. (4.3)
The eluder dimension of Z at scale ε, which is denoted by dimE(Z, ε), is the length of the longest sequence x1, . . . , xτ ∈ X such that, for any j ∈ [τ ], xj is (Z, ε′)-independent of x1, . . . , xj−1 for some ε′ ≥ ε.
The following lemma decomposes the regret of Algorithm 1 into errors that arise from policy improvement and policy evaluation, respectively. Lemma 4.9 (Regret Decomposition). For any k ∈ [K], it holds that
Regret(T ) = K∑ k=1 H∑ h=1 Eπ∗ [〈Qkh(·, sh), π∗h(· | sh)− πkh(· | sh)〉] + K∑ k=1 ( V k1 (s1)− V πk,k 1 (s1) ) +
K∑ k=1 H∑ h=1 Eπ∗ [rkh(sh, ah) + zPh(sh, ah, V kh+1)−Qkh(sh, ah)].
Proof. See Lemma 4.2 of Cai et al. (2019) for a detailed proof.
The following lemma characterizes the error that arises from policy improvement. Lemma 4.10 (Policy Improvement). It we set α = √
2 log |A|/(KH2) in Algorithm 1, then it holds that
K∑ k=1 H∑ h=1 Eπ∗ [〈Qkh(·, sh), π∗h(· | sh)− πkh(· | sh)〉] ≤ √ 2KH4 · log |A|.
Proof. See Section B.2 for a detailed proof.
Recall that for any P ∈ P , zP is defined in (3.3). Also, let ZP = {zP : P ∈ P}. For any > 0, we denote byN (P, ‖ · ‖∞,1) the -covering number of P with respect to the `∞,1-norm distance, which is defined by
‖P − P ′‖∞,1 = max (s,a)∈S×A ∫ S |P (s′ | s, a)− P ′(s′ | s, a)|ds′, for any P, P ′ ∈ P.
The following lemma characterizes the error that arises from policy evaluation. Lemma 4.11 (Policy Evaluation). For any p ∈ (0, 1), if we set
β ≥ 2H2 · log ( N1/(KH)(P, ‖ · ‖∞,1) · 2H/p ) + 4 ( H + √ H2/4 · log(8K2H/p) ) (4.4)
in Algorithm 1, then the following results hold with probability at least (1− p).
• (Optimism) For any (k, h) ∈ [K]× [H] and (s, a) ∈ S ×A, it holds that
rkh(s, a) + zPh(s, a, V k h+1)−Qkh(s, a) ≤ 0.
• (Accuracy) Let d = K ∧ dimE(ZP , 1/K). It holds that
K∑ k=1 ( V k1 (s1)− V πk,k 1 (s1) ) ≤ √ 32KH3 · log(p/2) +H(dH + 1) + 4 √ dβKH2.
Proof. See Section B.1 for a detailed proof.
Recall that T = KH . The following theorem characterizes the regret of Algorithm 1 when P is a general model class, which serves as a meta result. Theorem 4.12. In Algorithm 1, if we set α as in Lemma 4.10 and β as in Lemma 4.11, then it holds that
Regret(T ) ≤ √ 2H3T · log |A|+ √ 32H2T · log(p/2) +H(dH + 1) + 4 √ dβHT
with probability at least (1− p), where d = K ∧ dimE(ZP , 1/K).
Proof. The proof follows from combining Lemmas 4.9, 4.11, and 4.10.
Theorem 4.12 indicates that max { d, √ d · log ( N1/(KH)(P, ‖ · ‖∞,1) )} serves as the model capacity κ(P) in Theorem 4.1. The regret upper bound in Theorem 4.12 is similar to that in Ayoub et al. (2020) when P is a general model class, whose model capacity is characterized by the eluder dimension. In contrast, our algorithm additionally handles adversarial rewards, which is 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 is a set of d-dimensional linear models with a finite d, which is studied in Cai et al. (2019). In particular, the eluder dimension and log-covering number in (4.4) are both Õ(d) (Ayoub et al., 2020), which leads to the √ d2H3T -regret in Cai et al. (2019). In contrast, Theorem 4.12 additionally handles the case where d is infinite as in kernel and neural function approximations.

heading: A MORE DETAILS ON RKHS
text: An example of the RKHS is the linear model class. In particular, let ψ be a d-dimensional feature vector
ψ(x) = ( ψ1(x), . . . , ψd(x) )> , for any x ∈ Y,
where ψ1, . . . , ψd are linearly independent. Then, the linear span of {ψj}∞j=1 forms an RKHSHψ with the reproducing kernel Kψ(x, y) = ψ(x)>ψ(y) for any x, y ∈ Y , and the corresponding inner product 〈·, ·〉Hψ is defined by the Euclidean inner product
〈ψ(·)>c1, ψ(·)>c2〉Hψ = c>1 c2
for any c1, c2 ∈ Rd. The above example can be naturally generalized to the case where d = ∞, that is, the feature vector can be infinite-dimensional. Moreover, recall that (2.2) says the reproducing kernel K has the representation
K(x, y) = ∞∑ j=1 λjφj(x)φj(y), for any x, y ∈ Y,
where {φj}∞j=1 is an orthonormal basis of L2(Y) and λ1 ≥ λ2 ≥ · · · ≥ 0. We refer to {φj}∞j=1 as the eigenfunctions of K with the corresponding eigenvalues {λj}∞j=1. Such a representation gives the feature vector
φ̃(x) = (√ λ1 · φ1(x), √ λ2 · φ2(x), . . . )> , for any x ∈ Y.
The linear span of { √ λj · φj}∞j=1 recovers the RKHS H with the reproducing kernel K and inner product 〈·, ·〉H. When the reproducing kernel K is infinite-dimensional, that is, K has an infinite number of non zero eigenvalues, φ̃ is an infinite-dimensional vector. It is known that RKHSs of various infinite-dimensional 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.

heading: B PROOFS FOR SECTION 4.3
text: In this section, we provide the detailed proofs of the result in Section 4.3. For notational simplicity, we denote by Ph the operator that takes the conditional expectation with respect to the transition kernel Ph for any h ∈ [H].

heading: B.1 PROOF OF LEMMA 4.11
text: Proof. We define the event E that
Ph ∈ Pkh , for any (k, h) ∈ [K]× [H]. (B.1)
By our choice of β and Lemma F.4 with δ = p/2, it holds that E occurs with probability at least (1− p/2).
Optimism: For any (k, h) ∈ [K]× [H], Ph ∈ Pkh implies
Qkh(·, ·)− ( rkh(·, ·) + (PhV kh+1)(·, ·) ) = clamp
( max P∈Pkh ∫ S V kh+1(s ′) · P (s′ | ·, ·) ds′, 0, H − h ) − ∫ S V kh+1(s ′) · Ph(s′ | ·, ·) ds′
≥ clamp (∫ S V kh+1(s ′) · Ph(s′ | ·, ·) ds′, 0, H − h ) − ∫ S V kh+1(s ′) · Ph(s′ | ·, ·) ds′. (B.2)
When h = H , the right-hand side of (B.2) is zero since V kH+1(·) = 0. When h < H , by the construction of Qkh+1 in (3.5) and the assumption that r k h+1(·) ∈ [0, 1], we have
Qkh+1(·, ·) ∈ [0, H − h], V kh+1(·) ∈ [0, H − h], ∫ S V kh+1(s ′) · Ph(s′ | ·, ·) ds′ ∈ [0, H − h].
The right-hand side of (B.2) is also zero, which implies Qkh(·, ·)− ( rkh(·, ·) + (PhV kh+1)(·, ·) ) ≥ 0.
Thus, the optimism result holds under the event E .
Accuracy: We invoke Lemma F.1 and obtain
K∑ k=1 V k1 (s k 1)− V π k 1 (s k 1) = K∑ k=1 H∑ h=1 (Dkh,1 +D k h,2) (B.3)
+ K∑ k=1 H∑ h=1 ( Qkh(s k h, a k h)− ( rkh(s k h, a k h) + PhV kh+1(skh, akh) )) ,
where |Dkh,1| ≤ 2H , |Dkh,2| ≤ 2H , DkH,2 = 0 for any (k, h) ∈ [K]× [H], and
D11,1, D 1 1,2 +D 1 2,1, D 1 2,2 +D 1 3,1, . . . , D 1 H−1,2 +D 1 H,1, D21,1, D 2 1,2 +D 2 2,1, D 2 2,2 +D 2 3,1, . . . , D 2 H−1,2 +D 2 H,1, . . . . . .
is a martingale difference sequence. The Azuma-Hoeffding inequality (Azuma, 1967) implies
K∑ k=1 H∑ h=1 (Dkh,1 +D k h,2) ≤ √ 32KH3 · log(p/2) (B.4)
with probability at least (1− p/2). It remains to upper bound the second term on the right-hand side of (B.3). For any (k, h) ∈ [K]× [H], Ph ∈ Pkh implies
Qkh(s k h, a k h)− ( rkh(s k h, a k h) + (PhV kh+1)(skh, akh) ) = clamp
( max P∈Pkh ∫ S V kh+1(s ′) · P (s′ | skh, akh) ds′, 0, H − h ) − ∫ S V kh+1(s ′) · Ph(s′ | skh, akh) ds′
≤ max P∈Pkh ∫ S V kh+1(s ′) · P (s′ | skh, akh) ds′ − min P∈Pkh ∫ S V kh+1(s ′) · P (s′ | skh, akh) ds′.
Applying Lemma F.5, for any h ∈ [H], we have
Qkh(s k h, a k h)− ( rkh(s k h, a k h) + (PhV kh+1)(skh, akh) ) ≤
K∑ k=1 ( max P∈Pkh ∫ S V kh+1(s ′) · P (s′ | skh, akh) ds′ − min P∈Pkh ∫ S V kh+1(s ′) · P (s′ | skh, akh) ds′ )
≤ 1 + dH + 4 √ dβK, (B.5)
where d = K ∧ dimE(ZP , 1/K). Combining (B.3)-(B.5), we have
K∑ k=1 V k1 (s k 1)− V π k 1 (s k 1) ≤ √ 32KH3 · log(p/2) +H + dH2 + 4 √ dβHT .
In summary, when the event E and (B.4) hold, which occur with probability at least (1− p), we have
Qkh(·, ·) ≥ rkh(·, ·) + (PhV kh+1)(·, ·), for any (k, h) ∈ [K]× [H], K∑ k=1 ( V k1 (s k 1)− V πk,k 1 (s k h) ) ≤ √ 32KH3 · log(p/2) +H(1 + dH) + 4 √ dβHT .
Therefore, we conclude the proof of Lemma 4.11.

heading: B.2 PROOF OF LEMMA 4.10
text: Proof. By Lemma 3.3 of Cai et al. (2019), for any (k, h) ∈ [K]× [H] and s ∈ S, we have
〈Qkh(s, ·), π∗h(· | s)− πkh(· | s)〉 ≤ αH2/2 + α−1 · ( DKL ( π∗h(· | s) ∥∥πkh(· | s))−DKL(π∗h(· | s)∥∥πk+1h (· | s))), (B.6) which implies
K∑ k=1 H∑ h=1 Eπ∗ [〈Qkh(sh, ·), π∗h(· | sh)− πkh(· | sh)〉]
≤ αKH3/2 + α−1 · H∑ h=1 Eπ∗ [ DKL ( π∗h(· | sh) ∥∥π1h(· | sh))] ≤ αKH3/2 + α−1H · log |A|. (B.7)
Plugging α = √
2 log |A|/(HT ) into the right-hand side of (B.7), we conclude the proof of Lemma 4.10.

heading: C PROOF OF THEOREM 4.3
text: In this section, we prove Theorem 4.3. By Theorem 4.12, it suffices to upper bound the eluder dimension of ZP = {zP : P ∈ P} and log-covering number ofHR, which are characterized by the following two lemmas, respectively. Lemma C.1. Under Assumption 4.2, there exists an absolute constant C7 > 0 such that
K ∧ dimE(ZP , 1/K) ≤ C7 · log2(1/γ)/γ · log1+1/γ(RT ).
Proof. Let t = K ∧ dimE(ZP , 1/K). By Definition 4.8, there exists a sequence x1, . . . , xt ∈ S ×A× [0, H]S such that xτ is (ZP , 1/K)-independent of x1, . . . , xτ−1 for any τ ∈ [t]. Here the independency scale is assumed to be 1/K without loss of generality, which can be changed to any
value larger than 1/K. In other words, for any τ ∈ [t], there exist P1, P2 ∈ P such that
τ−1∑ i=1 |zP1(xi)− zP2(xi)|2 ≤ 1/K2, (C.1)
|zP1(xτ )− zP2(xτ )| > 1/K. (C.2)
Note that for any x = (s, a, V ) ∈ S ×A× [0, H]S and P ∈ P , by the reproducing property of the RKHSH, we can write
zP (x) = ∫ S V (s′) · P (s′ | s, a) ds′ = ∫ S V (s′) · 〈P,K(s,a,s′)〉H ds′.
The representation of K in (2.2) implies
zP (x) = ∫ S V (s′) · 〈 P, ∞∑ j=1 λj · φj(s, a, s′) · φj 〉 H ds′
= ∫ S V (s′) · ∞∑ j=1 √ λj · φj(s, a, s′) · 〈P, √ λj · φj〉H ds′
= ∞∑ j=1 √ λj · ∫ S V (s′) · φj(s, a, s′) ds′ · 〈P, √ λj · φj〉H.
For any d0 such that d γ 0 ≥ 4(1 − γ)(γC2)−1 where γ and C2 are defined in Assumption 4.2, we define
z̃P (x) = ∑
1≤j≤d0
√ λj · ∫ S V (s′) · φj(s, a, s′) ds′ · 〈P, √ λj · φj〉H
for any x = (s, a, V ) ∈ S ×A× [0, H]S and P ∈ P . Then, we have
|zP (x)− z̃P (x)| = ∣∣∣∑ j>d0 √ λj · ∫ S V (s′) · φj(s, a, s′) ds′ · 〈P, √ λj · φj〉H ∣∣∣ ≤ ∑ j>d0 √ λj · |S| ·H · ‖P‖H ≤ ∑ j>d0 √ λj ·RH,
where |S| is the Lebesgue measure of S and |S| ≤ 1. Here the first inequality follows from the Cauchy-Schwarz inequality and ‖ √ λj · φj‖H = 1 for any j ∈ N, since { √ λj · φj}∞j=1 is an orthonormal basis ofH. By Assumption 4.2, we obtain
|zP (x)− z̃P (x)| ≤ ∑ j>d0 √ C1 · exp(−C2jγ/2) ·RH
= √ C1 ·RH · ∑ j>d0 exp(−C2jγ/2)
≤ √ C1 ·RH · 4d1−γ0 (γC2)−1 · exp(−C2d γ 0/2), (C.3)
where the last inequality follows from Lemma F.6. For notational simplicity, let Γ(d0) = √ C1 ·RH · 4d1−γ0 (γC2)−1 · exp(−C2d γ 0/2). (C.4)
By (C.1), it holds that
τ−1∑ i=1 |z̃P1(xi)− z̃P2(xi)|2 ≤ τ−1∑ i=1 ( |zP1(xi)− zP2(xi)|+ 2Γ(d0) )2 ≤ τ−1∑ i=1 ( 2|zP1(xi)− zP2(xi)|2 + 8Γ(d0)2
) ≤ 2/K2 + 8t · Γ(d0)2, (C.5)
where the last inequality uses τ ≤ t. For any τ ∈ [t], we define
y = ( 〈P1 − P2, √ λ1 · φ1〉H, . . . , 〈P1 − P2, √ λd0 · φd0〉H )> , (C.6)
vτ = (√ λ1 · ∫ S Vτ (s ′) · φ1(sτ , aτ , s′) ds′, . . . , √ λd0 · ∫ S Vτ (s ′) · φd0(sτ , aτ , s′) ds′ )> , (C.7)
Λτ = Id0×d0/(d0K 2R2) + τ−1∑ i=1 viv > i . (C.8)
Then, it holds that
y>Λτy = 1
d0K2R2 · ‖y‖22 + τ−1∑ i=1 (y>vi) 2
= 1 d0K2R2 · d0∑ j=1 〈P1 − P2, √ λj · φj〉2H + τ−1∑ i=1 |z̃P1(xi)− z̃P2(xi)|2 ≤ 1 d0K2R2 · 4d0R2 + 2/K2 + 8t · Γ(d0)2 = 6/K2 + 8t · Γ(d0)2, (C.9)
where the inequality uses (C.5) and 〈P1 − P2, √ λj · φj〉2H ≤ ‖P1 − P2‖2H · ‖ √ λj · φj‖2H ≤ 4R2 · 1 = 4R2. Here we uses ‖P‖H ≤ R for any P ∈ P and ‖ √ λi · φi‖H = 1 for any j ∈ [d0]. In the sequel, we establish an upper bound of |z̃P1(xτ )− z̃P2(xτ )|. By the definitions of y in (C.6) and vτ in (C.7), we can write z̃P1(xτ )− z̃P2(xτ ) = 〈y, vτ 〉. By (C.9), |z̃P1(zτ )− z̃P2(zτ )| is upper bounded by
max y′∈Rd0
〈y′, vτ 〉 s.t. (y′)>Λτy′ ≤ 6/K2 + 8t · Γ(d0)2.
The maximizer of such a quadratic program is
y′ = √ [6/K2 + 8t · Γ(d0)2]/(v>τ Λ−1τ vτ ) · Λ−1τ vτ .
Therefore, we obtain |z̃P1(xτ )− z̃P2(xτ )| ≤ √( 6/K2 + 8t · Γ(d0)2 ) (v>τ Λ −1 τ vτ ). (C.10)
On the other hand, by (C.2)-(C.4), we have
|z̃P1(xτ )− z̃P2(xτ )| ≥ |zP1(xτ )− zP2(xτ )| − ( |z̃P1(xτ )− zP1(xτ )|+ |z̃P2(xτ )− zP2(xτ )| ) ≥ |zP1(xτ )− zP2(xτ )| − 2Γ(d0) > 1/K − 2Γ(d0). (C.11)
We set d0 = dC̃ · log(1/γ)/γ · log1/γ(4tRKH)e, where C̃ is defined in Lemma F.7. Then, by Lemma F.7, it holds that dγ0 ≥ 4(1− γ)(γC2)−1 and
Γ(d0) ≤ 1/(4tK). (C.12)
Combining (C.10), (C.11), and (C.12), we obtain
v>τ Λ −1 τ vτ >
( 1/K − 2Γ(d0) )2 6/K2 + 8t · Γ(d0)2 ≥ ( 1/K − 1/(2K) )2 6/K2 + 1/(2K2) > 1/100. (C.13)
Therefore, by (C.13), we have
t/100 = t∑ τ=1 min{1/100, v>τ Λ−1τ vτ}
≤ t∑
τ=1
2 log(1 + v>τ Λ −1 τ vτ ) ≤ 2 ( (log det(Λt+1)− log det(Λ1) ) , (C.14)
where the last inequality uses the elliptical potential lemma (Abbasi-Yadkori et al., 2011). Here, similar to (C.8), Λt+1 is defined by
Λt+1 = Id0×d0/(d0K 2R2) + t∑ i=1 viv > i .
Note that
‖vτ‖22 = d0∑ j=1 λj · (∫ S Vτ (s ′)φj(sτ , aτ , s ′) ds′ )2 ≤ d0H2
for any τ ∈ [t]. Thus, setting λ = 1/(d0K2R2), we have
log det(Λ1) = d0 · log λ, (C.15)
log det(Λt+1) ≤ d0 · log ‖Λt+1‖2 ≤ d0 · log ( λ+ t∑ i=1 ‖vi‖22 ) ≤ d0 · log(λ+ d0KH2). (C.16)
where the last inequality follows from t = K ∧ dimE(ZP , 1/K). Combining (C.15) and (C.16), we have
2 ( (log det(Λt+1)− log det(Λ1) ) ≤ 2d0 · log(1 + d0KH2/λ) = 2d0 · log(1 + d20K3R2H2)
(C.17)
Combining (C.14) and (C.17), we obtain
t ≤ 200d0 · log(1 + d20K3R2H2) ≤ 600d0 · log(d0KRH). (C.18)
Moreover, by d0 = dC̃ · log(1/γ)/γ · log1/γ(4tRKH)e and (C.18), there exists an absolute constant C8 > 0 such that
t ≤ 600d0 · log(d0KRH) ≤ 600 · ⌈ C̃ · log(1/γ)/γ · log1/γ(tKRH) )⌉ · log ( dC̃ · log(1/γ)/γ · log1/γ(tKRH)e ·KRH ) ≤ C8 · log2(1/γ)/γ · log1+1/γ(tKRH). (C.19)
Recall that t = K ∧ dimE(ZP , 1/K). Thus, by (C.19), we obtain
t ≤ C7 · log2(1/γ)/γ · log1+1/γ(KRH) (C.20)
for an absolute constant C7 > 0. Thus, we conclude the proof of Lemma C.1.
Lemma C.2. Under Assumption 4.2, there exists an absolute constant C9 > 0 such that
N1/(KH)(P, ‖ · ‖∞,1) ≤ C9 · log2(1/γ)/γ · log1+1/γ(RT )
for any R ≥ 2.
Proof. Recall that we define Γ(d0) in (C.4). By choosing t = 2KH in Lemma F.7, there exists
d0 = dC̃ · log(1/γ)/γ · log1/γ(2KRH2)e
where C̃ is defined in Lemma F.7, such that dγ0 ≥ 4(1− γ)(γC2)−1 and
Γ(d0) ≤ 1/(2KH). (C.21)
Here γ and C2 are defined in Assumption 4.2. Let C be a minimal 1/(2d1/20 KH)-covering of the Euclidean ball {v ∈ Rd0 : ‖v‖2 ≤ R} with respect to the `2-norm distance. For any P ∈ P , we define P̃ ∈ P by
P̃ (x) = d0∑ j=1 λj · 〈P, φj〉H · φj(x), for any x ∈ Y.
Also, we write
v = (√ λ1 · 〈P, φ1〉H, . . . , √ λd0 · 〈P, φd0〉H ) .
Since { √ λj · φj}∞j=1 is an orthonormal basis ofH and P ∈ HR, we have
‖v‖2 = ‖P̃‖H ≤ ‖P‖H ≤ R.
Thus, by the definition of C, there exists v∗ ∈ C with ‖v−v∗‖2 ≤ 1/(2d1/20 KH). We define P ∗ ∈ P by
P ∗(x) = d0∑ j=1 v∗j · √ λj · φj(x), for any x ∈ Y.
Then, by Assumption 4.2, for any x ∈ Y , we have
|P̃ (x)− P ∗(x)| = ∣∣∣ d0∑ j=1 (vj − v∗j ) · √ λj · φj(x) ∣∣∣ ≤ ‖v − v∗‖1 ≤ d1/20 · ‖v − v∗‖2 ≤ 1/(2KH). (C.22)
Also, for any x ∈ Y , we have |P (x)− P̃ (x)| = ∣∣∣∑ j>d0 √ λj · φj(x) · 〈P, √ λj · φj〉H ∣∣∣ ≤ ∑ j>d0 √ λj ·R
≤ ∑ j>d0 √ C1 · exp(−C2jγ/2) ·R ≤ Γ(d0), (C.23)
where the first inequality uses ‖P‖H ≤ R and ‖ √ λj · φj‖H = 1, the second inequality follows from Assumption 4.2, and the last inequality follows from the same argument in (C.3) and H ≥ 1. Thus,
for any x ∈ Y , it holds that
|P (x)− P ∗(x)| ≤ |P (x)− P̃ (x)|+ |P̃ (x)− P ∗(x)| ≤ Γ(d0) + 1/(2KH) ≤ 1/(KH). (C.24)
We define
PC = { P : ∃ v ∈ C s.t.P (x) = d0∑ j=1 vj · √ λj · φj(x) for any x ∈ Y } .
Then, by (C.24), PC is a 1/(KH)-covering of P with respect to the `∞-norm distance. Therefore, we have
N1/(KH)(P, ‖ · ‖∞,1) ≤ N1/(KH)(P, ‖ · ‖∞)
≤ |PC | ≤ |C| ≤ C12 · d0 · log(d0KRH) ≤ C9 · log2(1/γ)/γ · log1+1/γ(KRH), (C.25)
where C12, C9 > 0 are absolute constants. Here the first inequality is because ‖ · ‖∞,1 ≤ ‖ · ‖∞ given |S| ≤ 1, 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.1 and C.2 for the exponential decay case can be made general. For a finite-rank kernel, we can let d0 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 is upper bounded by O(d0 log(RKH)). Moreover, for a kernel with polynomially decaying eigenvalues, that is, we have
λj ≤ Cpoly · j−γ for some constants Cpoly, γ > 0 and any j ≥ 1,
we can still truncate at dimension d0 and calculate Γ(d0) in (C.4) using the polynomial eigenvalue decay condition. It can be shown that Γ(d0) decays polynomially in d0. Then, we can find a proper d0 by solving (C.12) and (C.21) and follow the same proof afterwards. Proof of Theorem 4.3
Proof. Recall that d = K ∧ dimE(ZP , 1/K). By Theorem 4.12, it holds that Regret(T ) ≤ √ 2H3T · log |A|+ √ 32H2T · log(p/2) +H(dH + 1) + 4 √ dβHT , (C.26)
with probability at least (1− p), where we set α = √ 2 log |A|/(KH2) and
β ≥ 2H2 · log ( N1/T (P, ‖ · ‖∞,1) · 2H/p ) + 4 ( H + √ H2/4 · log(8K2H/p) ) . (C.27)
By Lemma C.2, we have
N1/(KH)(P, ‖ · ‖∞,1) ≤ C9 · log2(1/γ)/γ · log1+1/γ(RT ),
which implies there exists an absolute constant C3 > 0 such that 2H2 · log ( N1/(KH)(P, ‖ · ‖∞,1) · 2H/p ) + 4 ( H + √ H2/4 · log(8K2H/p) ) ≤ C3H2 · log2(1/γ)/γ · log1+1/γ(RT/p).
In other words, (C.27) holds if we set
β = C3H 2 · log2(1/γ)/γ · log1+1/γ(RT/p). (C.28)
On the other hand, by Lemma C.1, we have
d ≤ C7 · log2(1/γ)/γ · log1+1/γ(RT ). (C.29)
Plugging (C.28) and (C.29) into (C.26), we obtain Regret(T ) ≤ √ 2H3T · log |A|+ √
32H2T · log(p/2) +H + C7H 2 · log2(1/γ)/γ · log1+1/γ(RT )
+ 4 √ C3C7H3T · log2(1/γ)/γ · log(1+1/γ)/2(RT ) · log(1+1/γ)/2(RT/p)
≤ C4 √ H3T · log2(1/γ)/γ · log1+1/γ(|A|RT/p) (C.30)
with probability at least (1− p), where C4 > 0 is an absolute constant. Thus, we conclude the proof of Theorem 4.3.

heading: D PROOF OF THEOREM 4.7
text: In this section, we prove Theorem 4.7. Similar to 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 of KNTK in (4.2), we have
HR = {P : ∃w ∈ BR s.t.P (x) = ∇wNN(x;w0)>(w − w0) for any x ∈ Y}.
Without loss of generality, we assume entries of ∇wNN(·;w0) 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 ∧ dimE(ZP , 1/K) ≤ C10 · log2(1/γ)/γ · log1+1/γ(RT ).
Proof. Let t = K ∧ dimE(ZP , 1/K). By Definition 4.8, there exists a sequence x1, . . . , xt ∈ S ×A× [0, H]S such that xτ is (ZP , 1/K)-independent of x1, . . . , xτ−1 for any τ ∈ [t]. In other words, for any τ ∈ [t], there exist P1, P2 ∈ P such that
τ−1∑ i=1 |zP1(xi)− zP2(xi)|2 ≤ 1/K2, (D.1)
|zP1(xτ )− zP2(xτ )| > 1/K. (D.2)
For any x = (s, a, V ) ∈ S ×A× [0, H]S and P ∈ P , we define
P̄ (x;w) = ∇wNN(x;w0)>(w − w0).
Using the reproducing property ofH and the representation of K in (2.2), we have
zP (x) = ∫ S V (s′) · P (s, a, s′;w) ds′
= ∫ S V (s′) · P̄ (s, a, s′;w) ds′ + ∫ S V (s′) · ( P (s, a, s′;w)− P̄ (s, a, s′;w) ) ds′
= ∞∑ j=1 √ λj · ∫ S V (s′) · φj(s, a, s′) ds′ · 〈P̄ , √ λj · φj〉H
+ ∫ S V (s′) · ( P (s, a, s′;w)− P̄ (s, a, s′;w) ) ds′.
For any d0 such that d γ 0 ≥ 4(1− γ)(γC2)−1, we define
z̃P (x) = ∑
1≤j≤d0
√ λj · ∫ S V (s′) · φj(s, a, s′) ds′ · 〈P̄ , √ λj · φj〉H
for any x = (s, a, V ) ∈ S ×A× [0, H]S and P ∈ P . And we have
|zP (x)− z̃P (x)| ≤ ∣∣∣∑ j>d0 √ λj · ∫ S V (s′) · φj(s, a, s′) ds′ · 〈P̄ , √ λj · φj〉H ∣∣∣ + ∣∣∣∫ S V (s′) ( P (s, a, s′;w)− P̄ (s, a, s′;w) ) ds′ ∣∣∣
≤ ∑ j>d0 √ λj ·H ·R+ ξmH
≤ 4d1−γ0 √ C1HR(γC2) −1 · exp(−C2dγ0/2) + ξmH = Γ(d0) + ξmH, (D.3)
where the second inequality uses Assumption 4.2, ‖P‖H ≤ R, ‖ √ λj · φj‖H = 1, and the definition of ξm in Condition 4.4, the third inequality follows from Lemma F.6, and Γ(d0) is defined in (C.4). Then, using the triangle inequality, we have
τ−1∑ i=1 |z̃P1(xi)− z̃P2(xi)|2 ≤ τ−1∑ i=1 ( |zP1(xi)− zP2(xi)|+ 2Γ(d0) + 2ξmH )2 ≤ τ−1∑ i=1 2|zP1(xi)− zP2(xi)|2 + 16t · Γ(d0)2 + 16tξ2mH2
≤ 2/K2 + 16t · Γ(d0)2 + 16tξ2mH2, (D.4)
where the last inequality is by (D.1).
In the sequel, we establish an upper bound of |z̃P1(xτ ) − z̃P2(xτ )|. For any τ ∈ [t], similar to (C.6)-(C.8), we denote
y = ( 〈P1 − P2, √ λ1 · φ1〉H, . . . , 〈P 1 − P 2, √ λd0 · φd0〉H )> , (D.5)
vτ = (√ λ1 · ∫ S Vτ (s ′) · φ1(sτ , aτ , s′) ds′, . . . , √ λd0 · ∫ S Vτ (s ′) · φd0(sτ , aτ , s′) ds′ )> , (D.6)
Λτ = Id0×d0/(d0K 2R2) + τ−1∑ i=1 viv > i . (D.7)
Then, we have
y>Λτy = 1
d0K2R2 · ‖y‖22 + τ−1∑ i=1 (y>vi) 2
= 1 d0K2R2 · d0∑ j=1 〈P 1 − P 2, √ λj · φj〉2H + τ−1∑ i=1 |z̃P1(xi)− z̃P2(xi)|2 ≤ 1 d0K2R2 · 4d0R2 + 2/K2 + 16t · Γ(d0)2 + 16te2mH2 = 6/K2 + 16t · Γ(d0)2 + 16te2mH2 ≤ 7/K2 + 16t · Γ(d0)2. (D.8)
Here the inequality uses (D.4), Condition 4.4, and 〈P 1 − P 2, √ λj · φj〉2H ≤ ‖P 1 − P 2‖2H · ‖ √ λj · φj‖2H ≤ 4R2 · 1 = 4R2, which follows from the fact ‖P 1‖H, ‖P 2‖H ≤ R and ‖ √ λi · φi‖H = 1 for any j ∈ [d0]. By the definitions of y in (D.5) and vτ in (D.6), we can write z̃P1(xτ )− z̃P2(xτ ) = 〈y, vτ 〉, which by (D.8) is upper bounded by
max y′∈Rd0
〈y′, vτ 〉 s.t. (y′)>Λτy′ ≤ 7/K2 + 16t · Γ(d0)2.
The maximizer of such a quadratic program is y′ = √( 7/K2 + 16t · Γ(d0)2 ) /(v>τ Λ −1 τ vτ ) · Λ−1τ vτ .
Therefore, we have |z̃P1(xτ )− z̃P2(xτ )| ≤ √( 7/K2 + 16t · Γ(d0)2 ) (v>τ Λ −1 τ vτ ). (D.9)
On the other hand, by (D.2), (D.3), and Condition 4.4 we have
|z̃P1(xτ )− z̃P2(xτ )| ≥ |zP1(xτ )− zP2(xτ )| − ( |z̃P1(xτ )− zP2(xτ )|+ |z̃P1(xτ )− zP2(xτ )| ) ≥ |zP1(xτ )− zP2(xτ )| − 2Γ(d0)− 2ξmH > 1/K − 2Γ(d0)− 1/(2K) ≥ 1/(2K)− 2Γ(d0). (D.10)
We set d0 = dC̃ · log(1/γ)/γ · log1/γ(8tKRH)e, where C̃ is defined in Lemma F.7. Then, by Lemma F.7 it holds that dγ0 ≥ 4(1− γ)(γC2)−1 and
Γ(d0) ≤ 1/(8tK). (D.11)
Combining (D.9)-(D.11), we obtain
v>τ Λ −1 τ vτ >
( 1/(2K)− 2Γ(d0) )2 7/K2 + 16t · Γ(d0)2 ≥ ( 1/(2K)− 1/(4K) )2 7/K2 + 1/(4K2) > 1/100.
Following the same argument in (C.14)-(C.20) in the proof of Lemma C.1, we obtain
t ≤ C10 · log2(1/γ)/γ · log1+1/γ(KRH)
for an absolute constant C10 > 0. 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
N1/(KH)(P, ‖ · ‖∞,1) ≤ C11 · log2(1/γ)/γ · log1+1/γ(RT )
for any R ≥ 2.
Proof. By choosing t = 4KH in Lemma F.7, there exists d0 = dC̃ · log(1/γ)/γ · log1/γ(4KRH2)e, where C̃ is defined in Lemma F.7, such that dγ0 ≥ 4(1− γ)(γC2)−1 and
Γ(d0) ≤ 1/(4KH). (D.12)
Here Γ(d0) is defined in (C.4), γ and C2 are defined in Assumption 4.6. Let C be a minimal 1/(4d
1/2 0 KH)-covering of the Euclidean ball {v ∈ Rd0 : ‖v‖2 ≤ R} with respect to the `2-norm
distance. For any P ∈ P with parameter w, we define P̄ and P̃ by
P̄ (x) = ∇wNN(x;w0)>(w − w0),
P̃ (x) = d0∑ j=1 λj · 〈P̄ , φj〉H · φj(x).
for any x ∈ Y . Also, we write v = (√ λ1 · 〈P̄ , φ1〉H, . . . , √ λd0 · 〈P̄ , φd0〉H ) .
Note that, because { √ λj · φj}∞j=1 is an orthonormal basis inH and w ∈ BR, we have
‖v‖2 = ‖P̃‖H ≤ ‖P̄‖H ≤ R.
Thus, there exists v∗ ∈ C with ‖v − v∗‖2 ≤ 1/(4d1/20 KH). We define P ∗ ∈ HR by
P ∗(x) = d0∑ j=1 v∗j · √ λj · φj(x).
By the same arguments in (C.22) and (C.23), for any x ∈ Y , we have
|P̄ (x)− P̃ (x)| ≤ Γ(d0), |P̃ (x)− P ∗(x)| ≤ 1/(4KH). (D.13)
Then, by (D.12), (D.13), and Condition 4.4, for any x ∈ Y , it holds that
|P (x)− P ∗(x)| ≤ |P (x)− P̄ (x)|+ |P̄ (x)− P̃ (x)|+ |P̃ (x)− P ∗(x)| ≤ ξm + Γ(d0) + 1/(4KH) ≤ 3/(4KH). (D.14)
Moreover, since P ∗ ∈ HR, there exists a wv ∈ BR such that
P ∗(x) = ∇wNN(x;w0)>(wv − w0)
for any x ∈ Y . By Condition 4.4, we have
|P ∗(x)−NN(x;wv)| ≤ ξm ≤ 1/(4KH). (D.15)
Combining (D.14) and (D.15), we have
|P (x)−NN(x;wv)| ≤ 1/(KH). (D.16)
Note that because entries of ∇wNN(·;w0) are linearly independent, wv is unique for any v : ‖v‖2 ≤ R. We define
PC = { P : ∃ v ∈ C s.t.P (x) = NN(x;wv) for any x ∈ Y } .
Then, by (D.16), PC is a 1/(KH)-covering of P with respect to the `∞-norm distance. Following the same argument of (C.25), we have
N1/(KH)(P, ‖ · ‖∞,1) ≤ N1/(KH)(P, ‖ · ‖∞)
≤ |PC | ≤ |C| ≤ C13 · d0 · log(d0KRH) ≤ C11 · log2(1/γ)/γ · log1+1/γ(KRH),
where C13, C11 > 0 are absolute constants. Thus, we conclude the proof of Lemma D.2.

heading: Proof of Theorem 4.7
text: Proof. Recall that d = K ∧dimE(ZP , 1/K). By the result of a general P in Theorem 4.12, we have Regret(T ) ≤ √ 2H3T · log |A|+ √ 32H2T · log(p/2) +H(dH + 1) + 4 √ dβHT , (D.17)
with probability at least (1− p), when we set α = √ 2 log |A|/(KH2) and
β ≥ 2H2 · log ( N1/T (P, ‖ · ‖∞,1) · 2H/p ) + 4 ( H + √ H2/4 · log(8K2H/p) ) (D.18)
By Lemma D.2, we have
N1/(KH)(P, ‖ · ‖∞,1) ≤ C11 · log2(1/γ)/γ · log1+1/γ(RT ),
which implies that there exists an absolute constant C5 such that 2H2 · log ( N1/(KH)(P, ‖ · ‖∞,1) · 2H/p ) + 4 ( H + √ H2/4 · log(8K2H/p) ) ≤ C5H2 · log2(1/γ)/γ · log1+1/γ(RT/p).
In other words, (D.18) holds if we set
β ≥ C5H2 · log2(1/γ)/γ · log1+1/γ(RT/p). (D.19)
On the other hand, by Lemma D.1, we have
d ≤ C10 · log2(1/γ)/γ · log1+1/γ(RT ). (D.20)
Plugging (D.19) and (D.20) into (D.17), we obtain Regret(T ) ≤ √ 2H3T log |A|+ √ 32H2T log(p/2) +H
+ C10H 2 · log2(1/γ)/γ · log1+1/γ(RT ) + 4 √ C5C10H3T · log2(1/γ)/γ · log(1+1/γ)/2(RT ) · log(1+1/γ)/2(RT/p)
≤ C6 √ H3T · log2(1/γ)/γ · log1+1/γ(|A|RT/p)
with probability at least (1− p), where C6 > 0 is an absolute constant. Thus, we conclude the proof of Theorem 4.7.
E IMPLICIT LINEARIZATION
Two-layer fully-connected neural networks: A two-layer fully-connected neural network is defined by
NN(x;w) = 1√ m/dY m/dY∑ j=1 bj · σ(x>wj), (E.1)
where, without loss of generality, we assume m 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>1 , . . . , w > m/dY )> ∈ Rm, b = (b1, . . . , bm/dY ) > ∈ Rm/dY ,
respectively. During the training, we only tune the weights in w.
Symmetric Initialization: When initializing the neural network, we generate the initial weight vectors w0 and b by
w0j i.i.d.∼ N (0, 1/dY · IdY×dY ), w0j+m/(2dY) = w 0 j ,
bj i.i.d.∼ Unif({−1, 1}), bj+m/(2dY) = −bj
for any j ∈ [m/(2dY)]. As a result of such initialization, we have NN(·;w0) = 0 and we can generalize the result to multilayer neural networks by setting the last two layers in this manner.

heading: Proof of Lemma 4.5
text: Proof. Let NN be a two-layer fully-connected neural network in the form (E.1). The activation function σ is 1-smooth and the second layer weights satisfies bj ∈ {−1, 1] for any j ∈ [m/dY ].
For any w ∈ Rm such that ‖w − w0‖2 ≤ R, we have
‖∇wNN(x;w)−∇wNN(x;w0)‖22
= 1
m/dY m/dY∑ j=1 ‖bjσ′(x>wj) · x− bjσ′(x>w0j ) · x‖22
= 1
m/dY m/dY∑ j=1 ( σ′(x>wj)− σ′(x>w0j ) )2 · (bj)2 · ‖x‖22 Note that, by the assumption that σ is 1-smooth, we have(
σ′(x>wj)− σ′(x>w0j ) )2 ≤ (x>wj − x>w0j )2 ≤ ‖wj − w0j‖22.
Thus, we have
‖∇wNN(x;w)−∇wNN(x;w0)‖22 ≤ 1
m/dY m/dY∑ j=1 ‖wj − w0j‖22 ≤ dYR2/m. (E.2)
By the mean value theorem, for any w : ‖w − w0‖2 ≤ R, there exists w† : ‖w† − w0‖2 ≤ R such that
NN(x;w)−NN(x;w0) = ∇wNN(x;w†)>(w − w0)
= ∇wNN(x;w0)>(w − w0) + ( ∇wNN(x;w†)−∇wNN(x;w0) )> (w − w0),
combining which with (E.2) we obtain
|NN(x;w)−∇wNN(x;w0)>(w − w0)| = |NN(x;w)−NN(x;w0)−∇wNN(x;w0)>(w − w0)|
= ∣∣(∇wNN(x;w†)−∇wNN(x;w0))>(w − w0)∣∣ ≤ ‖∇wNN(x;w†)−∇wNN(x;w0)‖2 · ‖w − w0‖2 ≤ dY1/2R2m−1/2.
Therefore, we have ξm ≤ dY1/2R2m−1/2. Then, Condition 4.4 holds when
m ≥ dYR4K3H2.
Thus, we conclude the proof of Lemma 4.5.

heading: F SUPPORTING LEMMAS

heading: F.1 DECOMPOSITION
text: For notational simplicity, we define the linear operator Jkh for (k, h) ∈ [K]× [H] by
(Jkhf)(s) = E[f(s, a) | a ∼ πkh(· | s)], for any s ∈ S, f ∈ [0, H]S×A.
Lemma F.1 (Martingale Decomposition). For any k ∈ [K], we have
V k1 (s k 1)− V π
k
1 (s k 1) = H∑ h=1 (Dkh,1 +D k h,2) + H∑ h=1 ( Qkh(s k h, a k h)− ( rkh(s k h, a k h) + PhV kh+1(skh, akh) )) ,
where Dkh,1 and D k h,2 take the forms
Dkh,1 = ( Jkh(Qkh −Q πk,k h ) ) (skh)− (Qkh −Q πk,k h )(s k h, a k h), Dkh,2 = (PhV kh+1 − PhV πk,k h+1 )(s k h, a k h)− (V kh+1 − V πk,k h+1 )(s k h+1).
Moreover, we have DkH,2 = 0 for any k ∈ [K], and the sequence
D11,1, D 1 1,2 +D 1 2,1, D 1 2,2 +D 1 3,1, . . . , D 1 H−1,2 +D 1 H,1, D21,1, D 2 1,2 +D 2 2,1, D 2 2,2 +D 2 3,1, . . . , D 2 H−1,2 +D 2 H,1, . . . . . . (F.1)
is a martingale difference sequence with respect to the filtration {F̃t}t≥1 in Definition F.2 and each term is bounded by 4H .
Proof. For any (k, h) ∈ [K]× [H], by the definition of the operator Jkh, we have
V kh (s k h)− V π
k
h (s k h)
= (JkhQkh)(skh)− (JkhQ πk,k h )(s k h) = (Qkh −Q πk,k h )(s k h, a k h) + ( Jkh(Qkh −Q πk,k h ) ) (skh)− (Qkh −Q πk,k h )(s k h, a
k h)︸ ︷︷ ︸
= Dkh,1
, (F.2)
where we denote the second term on the right-hand side by Dkh,1. Also, we have
(Qkh −Q πk,k h )(s k h, a k h)
= (Qkh − rkh − PhV πk,k h+1 )(s k h, a k h) = (PhV kh+1 − PhV πk,k h+1 )(s k h, a k h) + (Q k h − rkh − PhV kh+1)(skh, akh) = V kh+1(s k h+1)− V πk,k h+1 (s k h+1) + (Q k h − rkh − PhV kh+1)(skh, akh)
+ (PhV kh+1 − PhV πk,k h+1 )(s k h, a k h)− (V kh+1 − V πk,k h+1 )(s k h+1)︸ ︷︷ ︸
= Dkh,2
, (F.3)
where we denote the third term on the right-hand side by Dkh,2. Combining (F.2) and (F.3) we obtain( V kh (s k h)− V π k h (s k h) ) − ( V kh+1(s k h+1)− V πk,k h+1 (s k h+1) ) = Dkh,1 +D k h,2 + (Q k h − rkh − PhV kh+1)(skh, akh). (F.4)
Note that V kH+1(·) = 0 for any k ∈ [K]. Using the identity (F.4) for h ∈ [H] we have
V k1 (s k 1)− V π
k
1 (s k 1)
= H∑ h=1 ( V kh (s k h)− V π k h (s k h) ) − ( V kh+1(s k h+1)− V πk,k h+1 (s k h+1) ) =
H∑ h=1 ( Dkh,1 +D k h,2 + (Q k h − rkh − PhV kh+1)(skh, akh) ) =
H∑ h=1 ( Dkh,1 +D k h,2 ) + H∑ h=1 ( Qkh(s k h, a k h)− ( rkh(s k h, a k h) + PhV kh+1(skh, akh) )) .
In the sequel, we show that the sequence in (F.1) is a bounded martingale difference sequence with respect to the filtration {F̃t}t≥1. For any (k, h) ∈ [K]× [H], by the definitions of Dkh,1 and Dkh,2, we have
|Dkh,1 +Dkh,2| ≤ |Dkh,1|+ |Dkh,2| ≤ 4H.
When h = 1, we have
E[Dk1,1 | F̃i(k,1)−1] = E [( Jk1(Qk1 −Q πk,k 1 ) ) (sk1)− (Qk1 −Q πk,k 1 )(s k 1 , a k 1) ∣∣ F̃i(k−1,H)]
= ( Jk1(Qk1 −Q πk,k 1 ) ) (sk1)− ( Jk1(Qk1 −Q πk,k 1 ) ) (sk1) = 0.
Here the second equality is because the only randomness conditional on F̃i(k−1,H) is ak1 ∼ πk1 (· | sk1), which is because, by our definitions of Qπ
k,k 1 , F̃i(k−1,H), Qk1 , and πk, we have
Qk1(·), Q πk,k 1 (·) ∈ F̃i(k−1,H).
Similarly, when h ≥ 2, we have
E[Dkh−1,2 | F̃i(k,h)−1] (F.5)
= E[(Ph−1V kh − Ph−1V πk,k h )(s k h−1, a k h−1)− (V kh − V πk,k h )(s k h) | F̃i(k,h−1)] = (Ph−1V kh − Ph−1V πk,k h )(s k h−1, a k h−1)− (Ph−1V kh − Ph−1V πk,k h )(s k h−1, a k h−1) = 0,
which is because the only randomness conditional on F̃i(k,h−1) is skh ∼ Ph(· | skh−1, akh−1) and we have
E[Dkh,1 | F̃i(k,h)−1] = E [ E[Dkh,1 | F̃i(k,h)−1, skh] ∣∣ F̃i(k,h)−1] = 0. (F.6) Combining (F.5) and (F.6), we obtain
E[Dkh−1,2 +Dkh,1 | F̃i(k,h)−1] = 0.
Therefore, we conclude the proof of Lemma F.1.
Definition F.2 (Filtration). We define the time index map i(·, ·) by
i(k, h) = H · (j − 1) + h,
for any (k, h) ∈ [K] × [H], which is a bijection from [K] × [H] to [KH]. Then, for any (τ, h) ∈ [K]× [H], we define F̃t(k,h) as the σ-algebra generated by
(r1, s11, a 1 1, · · · , s1H , a1H , r2, s21, a21, · · · , sτ−1H , a τ−1 H , r τ , sτ1 , a τ 1 , · · · , sτh, aτh),
when h ≤ H − 1, which are the reward functions and state-action pairs determined before sτh+1, and
(r1, s11, a 1 1, · · · , s1H , a1H , r2, s21, a21, · · · , sτH , aτH , rτ+1),
when h = H , which are the reward functions and state-action pairs determined before sτ+11 . Then, the sequence {F̃t}t≥1 forms a filtration. Note that rτ = {rτh}Hh=1 are determined before the beginning of the τ -th episode although they are revealed to the agent until the τ -th episode ends.

heading: F.2 CONCERNTRATION
text: Let {(Xτ , Yτ )}τ≥1 be a sequence of random elements in X × R for some measurable set X . Let Z be a set of [0, C]-valued measurable functions with domain X for some C > 0. Let F = {Fτ}τ≥1 be a filtration such that for any τ ≥ 1, (X1, Y1, · · · , Xτ−1, Yτ−1, Xτ ) is Fτ−1-measurable and there exists z∗ ∈ Z such that E[Yτ | Fτ−1] = z∗(Xτ ) holds. The least-squares predictor ẑ given
{(Xτ , Yτ )}tτ=1 is defined by
ẑt = argmin z∈Z t∑ τ=1 ( z(Xτ )− Yτ )2 . (F.7)
We say that η is conditionally σ-sub-Gaussian given Fτ ∈ F for any τ ≥ 1 if for any λ ∈ R,
logE[exp(λη) | Fτ ] ≤ λ2σ2/2.
For any ε > 0, we denote byNε(Z, ‖·‖∞) the ε-covering number of Z with respect to the supremum norm distance ‖z1 − z2‖∞ = supx∈R |z1(x)− z2(x)|. For any β > 0, we define
Zt(β) = { z ∈ Z : t∑ τ=1 ( z(Xτ )− ẑt(Xτ ) )2 ≤ β}. (F.8) Lemma F.3 (Proposition 6 of Russo & Van Roy (2014)). Assume that for any t ∈ N, Yt − z∗(Xt) is conditionally σ-sub-Gaussian given Ft−1. Then, for any ε > 0 and δ ∈ [0, 1], with probability at least (1− δ), it holds that z∗ ∈ Zt(βt(δ, ε)) for any t ∈ N, where
βt(δ, ε) = 8σ 2 · log ( Nε(Z, ‖ · ‖∞)/δ ) + 4tε ( C + √ σ2 log(4t(t+ 1)/δ) ) .
Lemma F.4. For any δ ∈ [0, 1], if we let
β ≥ 2H2 · log ( N1/(KH)(P, ‖ · ‖∞,1) ·H/δ ) + 4 ( H + √ H2/4 · log(4K2H/δ) ) in Algorithm 1, then, with probability at least (1− δ), for any (k, h) ∈ [K]× [H], we have Ph ∈ Pkh .
Proof. Recall that, for any p ∈ P , we define zP : S ×A× [0, H]S → [0, H] by
zP ( s, a, V (·) ) = ∫ S V (s′) · P (s′ | s, a) ds′, ∀ ( s, a, V (·) ) ∈ S ×A× [0, H]S .
Let Z = ZP = {zP : P ∈ P}. For any (k, h) ∈ [K] × [H], we set Yk = V kh+1(skh+1), Xk = (skh, a k h, V k h+1(·)), and z∗ = zPh . Then, Yτ − z∗(Xτ ) is conditionally H/2-sub-Gaussian given F̃i(k,h) defined in Definition F.2. Then, by the definitions of Pkh in (3.4) and Zk(β) in (F.8), we have Zk(β) = {zP : P ∈ Pkh}. By setting
β ≥ 2H2 · log ( N1/K(Z) ·H/δ ) + 4 ( H + √ H2/4 · log(4K2H/δ) ) in Algorithm 1, it holds that
β ≥ 2H2 · log ( N1/K(Z) ·H/δ ) + 4(k − 1)/K · ( H + √ H2/4 · log(4k(k − 1)H/δ) ) = βk−1(δ/H, 1/K)
for any k ∈ [K], where βk−1(δ/H, 1/K) is defined in Lemma F.3. Applying Lemma F.3 with C = H , with probability at least (1− δ/H), for any k ∈ [K], we have
z∗ ∈ Zk ( βk−1(δ/H, 1/K) ) ⊂ Zk(β),
which implies Ph ∈ Pkh . Using the union bound over all h ∈ [H], with probability at least (1− δ), for any (k,H) ∈ [K]× [H], we have Ph ∈ Pkh .
In the sequel, we prove that Nε(Z, ‖ · ‖∞) ≤ Nε/H(P, ‖ · ‖∞,1) for any ε > 0. Indeed, this is obtained by the observation that, for any zP , zP ′ ∈ Z with P, P ′ ∈ P , we have
‖zP − zP ′‖∞ = sup (s,a,V (·))∈S×A×[0,H]S ∣∣∣∫ S V (s′) · P (s′ | s, a) ds′ − ∫ S V (s′) · P ′(s′ | s, a) ds′ ∣∣∣ ≤ sup
(s,a)∈S×A H · ∫ S |P (s′ | s, a)− P ′(s′ | s, a)|ds′ = H · ‖P − P ′‖∞,1.
Thus, we conclude the proof of Lemma F.4.

heading: F.3 ELUDER DIMENSION
text: Recall that Z is a set of [0, C]-valued functions with domain X for some C > 0. Meanwhile, Zk(β) is defined in (F.8). Lemma F.5 (Lemma 5 of Russo & Van Roy (2014)). For any β > 0, we have
K∑ k=1 sup z,z′∈Zk(β) |z(xk)− z′(xk)| ≤ 1 + C · d+ 4 · √ dβK,
where d = K ∧ dimE(Z, 1/K).
Proof. When dimE(Z, 1/K) ≤ K, by Lemma 5 of Russo & Van Roy (2014) we have
K∑ k=1 sup z,z′∈Zk(β) |z(xk)− z′(xk)| ≤ 1 + C · dimE(Z, 1/K) + 4 · √ dimE(Z, 1/K)βK
= 1 + C · d+ 4 · √ dβK.
When dimE(Z, 1/K) > K, since Z is a set of [0, C]-valued functions and Zk(β) ⊂ Z for any k and β, we have
K∑ k=1 sup z,z′∈Zk(β) |z(xk)− z′(xk)| ≤ KC ≤ 1 + C · d+ 4 · √ dβK.
Thus, we conclude the proof of Lemma F.5.

heading: F.4 OTHER USEFUL INEQUALITIES
text: Lemma F.6. For any γ ∈ (0, 1/2), C2 > 0, and any d0 ∈ N such that
dγ0 ≥ 4(1− γ)(γC2)−1, (F.9)
it holds that ∑ j>d0 exp(−C2jγ/2) ≤ 4d1−γ0 (γC2)−1 · exp(−C2d γ 0/2).
Proof. By basic calculus we have
2d1−γ0 /(γC2) · exp(−C2d γ 0/2) = ( −2t1−γ/(γC2) · exp(−C2tγ/2) )∣∣∞ t=d0
= ∫ ∞ d0 ( 1− 2(1− γ)t−γ/(γC2) ) exp(−C2tγ/2) dt
≥ ( 1− 2(1− γ)d−γ0 /(γC2) ) · ∫ ∞ d0 exp(−C2tγ/2) dt,
where the inequality is because 1− γ ≥ 0 and t−γ ≤ d−γ0 for t ≥ d0. Thus, we obtain∫ ∞ d0 exp(−C2tγ/2) dt ≤ 2d1−γ0 /(γC2) 1− 2(1− γ)d−γ0 /(γC2) exp(−C2dγ0/2) ≤ 4d 1−γ 0 /(γC2) · exp(−C2d γ 0/2), where the last inequality is because 1− 2(1− γ)d−γ0 /(γC2) ≥ 1/2 by (F.9). Then, by the fact that∑ j>d0 exp(−C2jγ) ≤ ∫ ∞ t=d0 exp(−C2tγ) dt,
we conclude the proof of Lemma F.6.
Recall that Γ(d0) is defined in (C.4). Lemma F.7. Let C1 and C2 be the absolute constants in Assumption 4.2. There exists an absolute constant C̃ such that for any γ ∈ (0, 1/2), t ≥ 1, and R ≥ 2, if we set
d0 = dC̃ · log(1/γ)/γ · log1/γ(tRH)e,
then it holds that dγ0 ≥ 4(1− γ)(γC2)−1 and
Γ(d0) = C 1/2 1 d 1−γ 0 RH(γC2) −1 · exp(−C2dγ0/2) ≤ 1/t. (F.10)
Proof. For any y > 0, we consider the function
f(x) = ex/xy, x > 0.
Taking derivatives, we have
f ′(x) = exxy−1(x− y)
x2y .
Note that f ′(x) ≥ 0 if and only if x ≤ y, which implies f(x) ≥ f(y) for any x > 0. Reorganizing the inequality, we obtain
ex ≥ (ex/y)y
for any x > 0 and y > 0. Applying the above inequality via choosing
x = C2d γ 0/4, y = (1− γ)/γ,
we obtain
d1−γ0 C 1/2 1 HR(γC2) −1
exp(C2d γ 0/2)
= d1−γ0
exp(C2d γ 0/4)
C 1/2 1 HR(γC2) −1
exp(C2d γ 0/4)
≤ d 1−γ 0
(eC2d γ 0/4 · γ 1−γ )
1−γ γ
C 1/2 1 HR(γC2) −1
exp(C2d γ 0/4)
= 1
(eC2/4 · γ1−γ ) 1−γ γ
C 1/2 1 HR(γC2) −1
exp(C2d γ 0/4)
.
Thus, to obtain (F.10), it suffices to make the following inequality hold,
exp(C2d γ 0/4) ≥
tC 1/2 1 RH
γC2(eC2/4 · γ1−γ ) 1−γ γ
,
which is equivalent to
d0 ≥ ( 1 C2 log tC 1/2 1 RH
γC2(eC2/4 · γ1−γ ) 1−γ γ
)1/γ .
Since γ ∈ (0, 1/2) and tRH ≥ 2, there exists an absolute constant C̃ such that
4(1− γ)(γC2)−1 ≤ C̃ · log(1/γ)/γ · log(tRH),
4/C2 · log tC
1/2 1 HR
γC2(eC2/4 · γ1−γ ) 1−γ γ
≤ C̃ · log(1/γ)/γ · log(tRH).
Therefore, by choosing d0 ≥ (C̃ log(1/γ)/γ · log(tRH))1/γ , we conclude the proof of Lemma F.7.

heading: G EXAMPLES OF KERNELS WITH EXPONENTIALLY DECAYING EIGENVALUES
text: In this section, we provide examples of kernels that satisfies Assumption 4.2. We let Y = SdY−1, which represents the unit sphere in RdY . For any kernel K, we define the integral operator TK : L2(Y)→ L2(Y) by
(TKf)(x) = ∫ Y Kse(x, y)f(y) dµ(y), for any f ∈ L2(Y) and x ∈ Y (G.1)
where µ is the uniform measure on Y .

heading: G.1 SQUARED EXPONENTIAL KERNEL
text: The squared exponential kernel is defined as
Kse(x, y) = exp{−1/ι2 · ‖x− y‖22}, for any x, y ∈ Y, (G.2)
where the constant ι satisfies ι2 ≥ 2/dY . For any u ∈ [−1, 1], we define k̃(u) = exp{−2(1−u)/ι2} and
P̃j(u) = (−1/2)j · Γ
( (dY − 1)/2 ) Γ ( (2j + dY − 1)/2 ) · (1− u2)(3−dY)/2 · ( d du )j [(1− u2)j+(dY−3)/2], (G.3)
where, with a slight abuse of notations, we use Γ(·) to denote the Gamma function in this section. Lemma G.1 (Theorem 2 of Minh et al. (2006)). For the kernel Kse defined in (G.2), the eigenvalues {ρj}j≥1 (without duplicates) of the corresponding integral operator TKse take the form
ρj = |SdY−2| |SdY−1| · ∫ 1 −1 k̃(u) · P̃j(u; dY) · (1− u2)(dY−3)/2 du,
and each ρj has multiplicity
N(j) = (2j + dY − 2) · (dY + j − 3)!
j!(dY − 2)! . (G.4)
Moreover, when ι2 ≥ 2/dY , we have that {ρj}j≥1 is in a decreasing order and satisfies
ρj > A1 · ( e ι2 )j · (2j + dY − 2)−(2j+dY−1)/2,
ρj < A2 · ( e ι2 )j · (2j + dY − 2)−(2j+dY−1)/2, (G.5)
for any j ≥ 1, where the constants A1, A2 only depend on dY and ι.
By Lemma G.1, the eigenvalues {λj}j≥1 (with duplicates) of the kernel Kse satisfy, for any j ≥ 1,
λj = ρt, for t such that t−1∑ i=1 N(i) < j ≤ t∑ i=1 N(i). (G.6)
By the definition of N(j) in (G.4) and Stirling’s formula, we have
N(j) (2j + dY − 2) · (dY + j − 3) 1/2 · [(dY + j − 3)/e](dY+j−3)
j1/2 · (j/e)j jdY−2. (G.7)
Here the asymptotic notation omits constant factors that are independent of j. Combining (G.6) and (G.7), when j is sufficiently large, we have
λj = ρt, for t such that (t− 1)dY−1 < j ≤ tdY−1.
Then, by (G.5) we obtain
λj = O (( e ι2 )j1/dY · (2j1/dY + dY − 2)−(2j 1/dY+dY−1)/2 ) = O(e−c·j 1/dY ) (G.8)
as j → ∞ for an absolute constant c > 0. Thus, we know Kse satisfies the second condition of Assumption 4.2.

heading: G.2 NTK OF SINE ACTIVATION
text: We consider the neural tangent kernel of a 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
NN(x;w, l) =
√ 2
m/(dY + 1) · m/(dY+1)∑
j=1
bj · sin(x>wj + lj)
for any x ∈ Y . Here we modify the initial form in (E.1) by adding an intercept term, which is equivalent to adding one more dimension with constant value 1 to the input space. The initialization of the network weights follows the same symmetric random initialization scheme
bj i.i.d.∼ Unif ( {−1, 1} ) , bj+m/(2dY+2) = bj ,
wj i.i.d.∼ N (0, IdY ), wj+m/(2dY+2) = wj ,
lj i.i.d.∼ Unif ( [0, 2π] ) , lj+m/(2dY+2) = lj ,
for j ∈ [m/(2dY + 2)]. Here without loss of generality we assume m/(2dY + 2) ∈ N. Then, the population NTK of such a parametrization takes the form
Kntk(x, y) = 2 · EW∼IdY ,L∼Unif([0,2π])[x >y · cos(x>W + L) · cos(y>W + L)]
= x>y · exp{−‖x− y‖22/2} = x>y · exp{x>y − 1},
for any x, y ∈ Y , which is the limit of the empirical NTK defined in (4.2) as m goes to infinity. Here the second equality is derived in Rahimi & Recht (2007) and the third equality is by the fact that ‖x‖2 = ‖y‖2 = 1 for any x, y ∈ Y = SdY−1. For any j ≥ 1, let Yj be the set of all homogeneous harmonics of degree j on SdY−1, which is a finite-dimensional subspace of L2µ(SdY−1), the space of square-integrable functions on SdY−1 with respect to µ. It can be shown that the dimensionality of Yj is given by N(j).
Lemma G.2 (Funk-Hecke formula (Müller (2012), page 30)). Let k̃2 : [−1, 1]→ R be a continuous function, which gives rise to an inner product kernel K̃ on SdY−1 × SdY−1 with the definition
K̃(x, y) = k̃2(x>y), for any x, y ∈ SdY−1.
Then, for any j ≥ 1, f ∈ Yj , x ∈ SdY−1, we have∫ SdY−1 K̃(x, y)f(y) dµ(y) = ( |SdY−2| |SdY−1| · ∫ 1 −1 k̃2(u) · P̃j(u) · (1− u2)(dY−3)/2 du ) · f(x),
where P̃j(u) is defined in (G.3).
We let k̃2(u) = u · exp{u− 1}. Recall the definition of k̃ in Section G.1, we have k̃2(u) = u · k̃(u) for ι = √ 2, which satisfies the requirement in Lemma G.1. Lemma G.2 shows that the eigenvalues {ρ̃j}j≥1 (with duplicates) of TK̃ takes the form
ρ̃j = Cρ · ∫ 1 −1 k̃2(u) · P̃j(u) · (1− u2)(dY−3)/2 du
= Cρ · ∫ 1 −1 u · k̃(u) · P̃j(u) · (1− u2)(dY−3)/2 du,
where Cρ = |SdY−2|/|SdY−1|. Using the relation
u · P̃j(u) = j
2j + dY − 2 · P̃j−1(u) + j + dY − 2 2j + dY − 2 · P̃j+1(u),
which is from the definition of P̃j(u), we have
ρ̃j = Cρ · ( j
2j + dY − 2 · ρj−1 + j + dY − 2 2j + dY − 2
· ρj+1 ) ,
where {ρj}j≥1 are the eigenvalues of the operator TKse studied in Section G.1 with ι = √
2. Thus, following the same argument of (G.6)-(G.8), we know such an NTK satisfies the second condition of Assumption 4.2.

Review summaries:
This 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).

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.