Kernelized Reinforcement Learning with Order Optimal Regret Bounds
Authors: Sattar Vakili
Julia Olkhovskaya
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Kernel ridge regression
Gaussian processes
LSVI
TL;DR: We significantly improve the regret bounds for kernelized RL using a domain partitioning technique.

Abstract: Modern reinforcement learning (RL) has shown empirical success in various real world settings with complex models and large state-action spaces. The existing analytical results, however, typically focus on settings with a small number of state-actions or simple models such as linearly modeled state-action value functions. To derive RL policies that efficiently handle large state-action spaces with more general value functions, some recent works have considered nonlinear function approximation using kernel ridge regression. We propose $\pi$-KRVI, an optimistic modification of least-squares value iteration, when the action-value function is represented by an RKHS. We prove the first order-optimal regret guarantees under a general setting. Our results show a significant polynomial in the number of episodes improvement over the state of the art. In particular, with highly non-smooth kernels (such as Neural Tangent kernel or some Matérn kernels) the existing results lead to trivial (superlinear in the number of episodes) regret bounds. We show a sublinear regret bound that is order optimal in the cases where a lower bound on regret is known (which includes the kernels mentioned above).

Kernelized Reinforcement Learning with Order Optimal Regret Bounds
Sattar Vakili Media Tek Research
Julia Olkhovskaya TU Delft" Delft, the Netherlands julia. o www.koosswaaagaall...ooo
Cambridge, UK
sattar.. battar.vakila wakkil.@ttkreeeeacch.com
Abstract
Reinforcement learning (RL) has shown empirical success in various real world settings with complex models and large state-action spaces. The existing analytical results, however, typically focus on settings with small number of state-actions simple models such as linearly modeled state-action value functions. To derive RL policies that efficiently handle large state-action spaces with more general value functions, some recent works have considered nonlinear function approximation using kernel ridge regression. We propose KRRV, optimistic modification of least-squares value iteration, when the state-action value function represented by reproducing kernel Hilbert space (RKHS). We prove the first order-optimal regret guarantees under a general setting. Our results show a significant polynomial in the number of episodes improvement over the state of the art. In particular, with highly non-smooth kernels (such as Neural Tangent kernel or some Matérn kernels) the existing results lead trivial (superlinear in the number of episodes) regret bounds. We show a sublinear regret bound that is order optimal in the case of Matérn kernels where lower bound on regret is known.
Introduction
Reinforcement learning (RL) in real world often has to deal with large state action spaces and complex unknown models. While RL policies using complex function approximations have been empirically effective in various fields including gaming (Silver al., 2016; Lee et al., 2018; Vinyals et al., 2019), autonomous driving (Kahn et al., 2017), microchip design (Mirhoseini et al., 2021), robot control (Kalashnikov et al., 2018), and algorithm search (Fawzi et al., 2022), little is known about theoretical performance guarantees in such settings. The analysis of RL algorithms has predominantly focused on simpler cases such as tabular linear Markov decision processes (MDPs). In tabular setting, regret bound of 8 ATT has been shown for optimistic state-action value learning algorithms (e.g., see, Jin et al., 2018), where H is the length of episodes, T is the number of episodes, and S and A are finite state and action spaces. This bound does not scale well when the size of state-action space grows large. Furthermore, when the model (the state-action value function or the transitions) admits d-dimensional linear representation in some state-action features, regret bound of Ö(v ((VH337)) established (Jin al., 2020), that scales with the dimension of the linear model rather than the cardinality of the state-action space.
Several recent studies have explored the utilization of complex models with large state-action spaces. A very general model entails representing the state-action value function using reproducing kernel Hilbert space (RKHS). This approach allows using kernel ridge regression obtain confidence intervals, which facilitate the design and analysis of RL algorithms. The most significant contribution
Work was done when the author was affiliated with Vrije Universiteit Amsterdam.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

to this general RL problem is Yang et al. (2020a),² that provides regret guarantees for an optimistic least-squares value iteration (LSVI) algorithm, referred to as kernel optimistic least-squares value iteration (KOVT). The main assumption is that the state-action value function can be represented using the RKHS of known kernel k. The regret bounds reported in Yang et al. (2020a) scale as Ö H2 ((T() + log ((T)) with e = 4, where T(T) and (c)) are two kernel related complexity terms, respectively, referred to as maximum information gain and e-covering number of the class of state-action value functions. The definitions are given in Section 4. Both complexity terms are determined using the spectrum of the kernel. While for smooth kernels. characterized by exponentially decaying Mercer cigenvalues, such as Squared Exponential kernel, I(T) and log. # are logarithmic in T' for more general kernels with greater representation capacity, these terms may grow polynomially in T, possibly making the regret bound trivial (superlinear).
To have a better understanding of the existing result, let fam > 0 denote the Mercer eigenvalues of the kernel k in a decreasing order. Also, let { denote the corresponding eigenfeatures. Refer to Section 2.2 for details. The kernel & is said to have a polynomial eigendecay when om decay at least fast as = for some p > 1. The polynomial eigendecay profile satisfies for many kernels of practical and theoretical interest such as Matérn family of kernels (Borovitskiy et al., 2020) and the Neural Tangent (NT) kereel (Arora ct al., 2019). For Matérn kernel with smoothness parameter on a d-dimensional domain, p 2u+d (e.g., see, Janz et al., 2020). For a NT kernel with 1 times differentiable activations, p = 2--1+d (Vakili et al., 2021b). In Yang et al. (2020a), the regret bound is specialized for the class of kernels with polynomially decaying eigenvalues, by bounding the complexity terms based on the kernel spectrum. However, the reported regret bound is sublinear
in T only when the kernel eigenvalues decay very fast. In particular, let ğ = p(1 27), where for 7 2 O, of om is uniformly bounded. Then, Yang et al. (2020a), Corollary 4.4 reports a regret bound of Ö(TS +x" +2) ), with
2d + p p+1
2 33 E"
d + 1 2(p + d)
K² maxtf"
(I)
The regret bound Ö(TS' +x* +4) is sublinear only when p and p are sufficiently large. That, at least, requires 25" < 2, implying p d + 2, when is also sufficiently large. For instance, for Matérn kernels, this requirement can be expressed as V > did+1) when [2v+d)(1-2m) is sufficiently large. d
+x*+4)
Special case of bandits. A similar issue existed in the simpler problem of kernelized bandits, corresponding to the special case where H 1, |S| 1. Specifically, the ((I(T)VTT) regret bounds reported for optimistic sampling (Srinivas et al., 2010a, GP-UCB), as well as for Thompson sampling (Chowdhury and Gopalan, 2017, GP-TS) are also trivial (superlinear) when I'TT) grows faster than VT. It remains an open problem whether the suboptimal performance guarantees for these two algorithms is a fundamental shortcoming or an artifact of the proof. This observation is formalized as an open problem on the online confidence intervals for RKHS elements in Vakili et al. (2021d). For the kernelized bandits problem. Scarlett et al. (2017) proved lower bounds on regret in
the case of Matérn family of kernels. In particular, they proved an Q(T 2042 lower bound on regret of any bandit algorithm. Several recent algorithms, different from GP-UCB and GP-TS, have been developed alleviate the suboptimal and superlinear regret bounds in kemelized bandits and obtain an Ö( (TT))) regret bound (Li and Scarlett, 2022; Salgia et al., 2021), that matches the lower bound in the case of the Matérn family of kernels, up to logarithmic factors. The Sup variations of the UCB algorithms also obtain the optimal regret bound in the contextual kernel bandit setting with finite actions (Valko et al., 2013).
Main contribution. The RL setting presents greater level of complexity compared to the bandit setting due to the Markovian dynamics. None of the solutions in Li and Scarlett (2022); Salgia et al. (2021); Valko et al. (2013) seem appropriate the presence of MDP dynamics, thereby leaving the question of order optimal regret bounds largely open. In this work, we leverage the scaling of the kernel spectrum with the size of the domain improve the regret bounds. We consider kernels with polynomial eigendecay on a hypercubical domain with side length P. where eigenvalues scale with pa for some a > O. See Definition 1. This encompasses a large class of common kernels, including the Matérn family, for which, a = 2v. The hypercube domain assumption is a technical formality
Also, the extended version on arXiv (Yang et al., 2020b).

---

that can be relaxed to other regular compact subsets of R In Section 3, we propose a domain partitioning kernel ridge regression based least-squares value iteration policy (T -RRII that achieves sublinear regret of Ó( dia "Td² for kernels introduced in Definition 1. This is the first sublinear regret bound under such a general stetting. Moreover, with Matérn kernels, our regret bound matches the ((T ) lower bound reported in in Scarlett al. (2017) for the special case of kernelized bandits, up to logarithmic factor.
Our proposed policy, T-KRVI, is based on least-squares value iteration (similar to KOVI, Yang et al. (2020a)). However, in order to effectively utilize the confidence intervals from kernel ridge regression, T- T-KRVI creates a partitioning of the state-action domain and builds the confidence intervals only based on the observations within the same partition element. The domain partitioning allows us to leverage the scaling of the kernel eigenvalues with respect to the domain size. The inspiration for this idea is drawn from π 7-GP-UCB algorithm introduced in Janz et al. (2020) for kernelized bandits. In comparison to Janz et al. (2020), KRRI and its analysis present greater complexity due the Markovian dynamics in the MDP setting. Furthermore, we provide a finer analysis that significantly improves the results compared to Janz et al. (2020). Although Janz et al. (2020) obtained sublinear 212--))))))
regret guarantees of Ó(T (04d(22d11)
) in the kernelized bandit setting with Matérn kemnll, there still remained a polynomial in T gap between their regret bounds and the lower bound reported in Scarlett al. (2017). As a consequence of our results, we also close this gap.
There are several novel contributions in our analysis that lead to the improved and order optimal regret bounds. We establish confidence intervals for kernel ridge regression that apply uniformly to all functions in the state-action value function class (Theorem 1). A similar confidence interval was given in Yang et al. (2020a). We however provide flexibility with respect to setting the parameters of the confidence interval, that eventually contributes to the improved regret bounds, with a proper choice of parameters. We also derive bounds the maximum information gain (Lemma 2) and the function class covering number (Lemma 3), taking into consideration the size of the state-action domain. These bounds are important for the analysis of our domain partitioning policy which effectively controls the number of observations utilized in kernel ridge regression by partitioning the domain into subdomains of diminishing size. These intermediate results may also be of general interest in similar problems.
The KRRV policy enjoys an efficient runtime, polynomial in T,, and linear in |A], similar to the runtime of KOVI (Yang et al., 2020a). The dependency of the runtime on |A| limits the scope of the policy to finite A. while allowing continuous S (with |S] infinite). The assumption of finite A can be relaxed. provided there is an efficient optimizer of a certain state-action value function. See the details in Section 3.2.
Other related work. There is an extensive literature on the analysis of RL policies which do not rely on a generative model or an exploratory behavioral policy. The literature has primarily focused on the tabular setting (Jin et al., 2018; Auer et al., 2008; Bartlett and Tewari, 2012). The domain of potential applications for this setting is very limited, as in many real world problems, the state-action space is very large or even infinite. In response to this, recent literature has placed a notable emphasis on employing function approximation in RL, particularly within the context of generalized linear settings. This approach involves representing the value function or transition model through a linear transformation to well-defined feature mapping. Important contributions include the work of Jin et al. (2020); Yao et al. (2014), as well as subsequent studies by Russo (2019); Zanette et al. (2020a,b); Neu and Pike-Burke (2020); Yang and Wang (2020). Furthermore, there have been several efforts to extend these techniques to a kernelized setting. as explored in Yang et al. (2020a); Yang and Wang (2020); Chowdhury and Gopalan (2019); Yang et al. (2020c); Domingues al. (2021). These works are also inspired by methods originally designed for linear bandits (Abbasi-Yadkori Yadkori al., 2011; Agrawal and Goyal, 2013), as well as kernelized bandits (Srinivas et al., 201 Ob; Valko et al., 2013; Chowdhury and Gopalan, 2017). However, all known regret bounds in the RL setting (Yang al., 2020a; Yang and Wang, 2020; Chowdhury and Gopalan, 2019; Yang et al., 2020c; Domingues et al., 2021) are not order optimal. We compare our regret bounds with the state of the art reported in Yang et al. (2020a). similar issue existed for classic kernelized bandit algorithms. A detailed discussion can be found in Vakili et al. 20) The authors in Yang and Wang (2020) considered finite state-actions under a kernelized MDP model where the transition model can be directly estimated. That is different from the setting considered in our work and Yang et al. (2020a).
3

---

2 Preliminaries and Problem Formulation
In this section, we overview the background on episodic MDPs and kernel ridge regression.
2.1 Episodic Markov Decision Processes
An episodic MDP can be described by the tuple (5, where S is the state space. A is the action space, the integer H is the length of each episode, r = (rr h==1 are the reward functions and P === {Pr, H denote the state-action space. For each E [H], the reward rh 2 -> [0. 1] is the reward function at step h, which is supposed to be deterministic for simplicity, and PA ( s, a) is the transition probability distribution on S for the next state from state-action pair (s, The choice of deterministic rewards allows us to concentrate limitation. Both the framework and results can be readily extended to setting with random rewards.
the transition probability distributions." 2 We use the notation Z = S A to
the core complexities of the problem, and should not be regarded
A policy (TA ) at each step h. determines the (possibly random) action Th S -> A taken 1, ...,, the environment picks an h= [ Then, at each step h E [M], the agent observes the state si, E S, picks an action of = -ं (s). and observes the reward rh (sj aj The new state s/+1 then is drawn from the transition distribution Pa(- of). The episode ends when the agent receives the final reward ror (s/2 d'z).
by the agent at state s. At the beginning of each episode
arbitrary state s The agent determines policy - { H
The goal find a policy v that maximizes the expected total reward in the episode, starting at step h, i.e., the value function defined as
H
(s)(s) E
Σ The (SN ax) ax) Lk==h
8h vs
(2)
where the expectation is taken with respect to the randomness in the trajectory {(sh, H
obtained by the policy т. can be shown that under mild assumptions (c.g.. continuity of Ph.
compactness of Z, and boundedness of r) there exists optimal policy n² which attains the
maximum possible value of V (s) at every step and at every state (e.g., see, Puterman, 2014). We
use the notation (s) = max, (i((s,, (s), Vs E S, E [H] By definition V."" = Vi-- For a value function V S - (0, H]. we define the following notation
[PAV a) = E. (r. (s))]
(3)
We also define the state-action value function Q7 : 2 + 10, H as follows.
H
(x, = E,r
rhe (sw )x)0 s = Σ
(4)
where the expectation is taken with respect to the randomness in the trajectory {(s,, an) an)]/= obtained by the policy æ. The Bellman equation associated with a policy æ then is represented as
(T, a) = (s) [PA V. (s, V (s) F. [QT(s (() (s)),, V#+1 0,
(5)
where the expectation taken with respect to the randomness in the policy т. The Bellman op- timality equation is also given (s,ss) a) (n(ss a) + [Pr 1 a), V max, Q7 a). Vi+1 0. The performance of a policy n' is measured in terms of the loss in the value function, referred to as regret, denoted by RTT) in the following definition
R(T) = > (VT VT'
66)
Recall that n' is the policy executed by the agent episode where sf is the initial state in that episode determined by the environment.
"We intentionally do note use the standard term transition kernel for Ph. to avoid confusion with the term kernel in kernel- learning.

---

2.2 Kernel Ridge Regression
We assume that the acteon value functions belong known reproducing kemnel Hilbert space (RKHS). See Assumption and Lemma I for the formal statement. This is very general assumption, considering that the RKHS of common kernels can approximate almost all continuous functions on the compact subsets of Rd (Srinivas et al., 201)a). Consider a positive definite kernel k 2 2 + R. Let Hy be the RKHS induced by k. where He contains a family of functions defined on 2. Let H), HK x Hss -> IR and || ||, HHE - R denote the inner product and the norm of Hg. respectively. The reproducing property implies that for f E Hyx and & E 2, (f: (1; 2) fz).. Without loss of generality, we assume k(z, 2) < for all Mercer theorem implies, under certain mild conditions, k can be represented using an infinite dimensional feature map:
k(2,2')
Σ m Om)0m(z))))) (z) (z'),
where am > 0, and Von tm Hr form an orthonormal basis of Hx. In particular, any f E H4 can be represented using this basis and wights Wm E R as
Wm om
(8)
where [lf = =m wh A formal statement and the details are provided in Appendix A. We refer to Fm and om (Mercer) eigenvalues and eigenfeatures of k, respectively.
Kernel-based models provide powerful predictors and uncertainty estimators which can be leveraged to guide the RL algorithm. In particular, consider a fixed unknown function f E Hy. Consider a set z (= M= C of inputs. Assume noisy observations {Y(=*) = f(z²) + + e are provided, where s are independent zero mean noise terms. Kernel ridge regression provides the following predictor and uncertainty estimate, respectively (see, e.g., Schölkopf al., 2002).
(x) (z) - 121t)-1
(z)) k(z,2) - (2) + -
(9)
where (z) [k(z, ",.,,,,,,,,,,,,),
vector of the kernel values between z and observations, Kz. 1k(z', 2 "=) is the x kernel matrix, Yz' (Y'),, (z*)" the t x observation vector, I is the identity matrix of dimensions and À > 0 is a free regularization parameter. The predictor and uncertainty estimate could be interpreted as posterior mean and variance of a surrogate centered Gaussian process (GP) model with covariance k and zero mean Gaussian noise with variance 2 (e.g., see, Williams and Rasmussen, 2006).
is a
2.3 Technical Assumption
We assume that the reward functions (rn, H 1=1 and the transition probability distributions Pa (s'1:.))) [| M R) denote the
belong the 1-ball of the RKHS. We use the notation BR (f R-ball of the RKHS.
Assumption We assume
Th (, BR... Vh E [H], Vs' S.
(10)
This mild assumption considering the generality of RKHSs, that also supposed to hold in Yang al. (2020a). Similar assumptions are made in linear MDPs which are significantly more restrictive (e.g., see, Jin et al., 2020).
An immediate consequence of Assumption is that for any integrable V : S - [0, H.. TM + [Pr V++1 E Bx.H+1. This is formalized in the following lemma.
Lemma Consider any integrable V S - [0, HJ. Under Assumption 1, we huve
Th [PAV] Bg,
(11)
See (Ych et al., 2023, Lemma 3) for proof.
5

---

3 Domain Partitioning Least-Squares Value Iteration Policy
A standard policy in episodic MDPs is the least-squares value iteration (L.SVI), which computes an estimate 2% for Q at each step of episode t, by recursively applying Bellman equation as discussed in the previous section. In addition, an exploration bonus term bj, Z + IR is typically added leading to
Ø = min + Sb) H - 1--h-- h 13.
(12)
The term Øi - 368, is an upper confidence bound on the state-action value function, that is inspired by the principle of optimism in the face of uncertainty. Since the rewards are assumed be most 1, the state-action value function at step h is also bounded by H - h + 1. In episode t, then x' is the greedy policy with respect to Q' = Under Assumption I, the estimate Q4 the parameter 3 and the exploration bonus bf, can all be designed using kernel ridge regression. Specifically, having the Bellman equation in mind, 2% is the (kernel ridge) predictor for ra + [Pr Vi+11 using (possibly some of) the past i observations (rx(2,,) + Vi (1)))))))))))) at points {>Ø]==1- Recall that [r% (=f) + +1 [8++)] = (=]) + [Pr Vi 1 where the expectation taken with respect to PA (+(g) The observation noise V (11) [P% V (=a]) is due to random transitions and bounded by H h < H.
3.1 Domain Partitioning
To overcome the suboptimal performance guarantees rooted in the online confidence intervals in kernel ridge regression, we introduce domain partitioning kernel ridge regression based least-squares value iteration (RVI...). The proposed policy partitions the state-action space Z into subdomains and builds kernel ridge regression only based on the observations within each subdomain. By doing so, we obtain tighter confidence intervals, ultimately resulting in tighter regret bound. To formalize this procedure, we consider the state-action space 2 C [0, 1 Let S h E [H] E [T] be sets of hypercubes overlapping only at edges, covering the entire [0, 1]d. For any hypercube 2' S we use pzz to denote the length of any of its sides, and (2') to denote the number of observations at step h in 2' up to episode t:
N1(2') = Σ 1(sh af) 2').
(13)
For all h E [H], we initialize S f10, 1] At each episode t, for each step h, after observing a sample from rr. + [PrV/ at (5%, a. we construct a new cover St as follows. We divide every element Z' E S that satisfies Pz" < (z') + 1, into two equal halves along each side, generating 2d hypercubes. The parameter > 0 in the splitting rule is constant specified in Definition Subsequently, we define S as the set of newly created hypercubes and the elements of S that were not split.
The construction of the cover sets described above ensures the number (2') of observations within each cover element Z' remains relatively small with respect to the size of Z', while also controlling the total number [S of cover elements. The key parameter managing this tradeoff a, which is carefully chosen to achieve an appropriate width for the confidence interval, as shown in Section 4.
3.2
π KRVI
Our proposed policy, KRVI, is derived by adopting the precise structure of an optimistic LSVI, as described previously, where the predictor and the exploration bonus are designed based on kernel ridge regression only cover elements. In particular, for Z, let ()(2) E S be the cover element at step h of episode containing z. Define Z = {( a)) E ()),), T < t) to be the set of past observations belonging to the same cover element as We then set
Q (=) (z)
+ x21 Y2)()))
(14)
where kzz(=)) = =k(2,, =))T= the kernel values between 2 and all observations z' in (x).
Kzf(=)) = (K(e",2"))=,,,"ez""" is the kernel matrix for observations in 21(2),, and Y2ç(=)

---

[ra(2)) (4444 where 8/+1 is drawn from the transition distribution Pa (= denotes the observation values for the observation points 2' E (2). The vectors kzz (x) and Y2 (x) are N (Z) dimensional column vectors, and (z)(s) and are dimensional matrices.
N (3) (z))
The exploration bonus is determined based on the uncertainty estimate of the kernel ridge regression model on cover elements defined as
b4 (z) (k(z, 2) (=)) (2,11) + +221) +x21)=x2(00(33))
(15)
The policy r-KRVI then is the greedy policy with respect to
(=) min( + (r) H h 13.
(16)
Specifically, at step h of episode t, the following action is chosen, after observing s%,
arg max Ø (8%, a).
(17)
aEA
pseudocode provided in Algorithm
Algorithm 1 The T KRRI Policy.
1: Input: X, (6), k; M (S, P.r).
2: For all h E [M] let 8% 1]
3: for Episode /. = 1, 1,2, , do
4: Receive the initial state sf-
5: Set V/++1 (s) = 0, for all
6: for step H ... do
7: Obtain value functions (z) as in (16).
8:
end for
9:
for step h 11 H. do
Take action a < arg max Q4 (s).
Observe the reward rn (sh af) and the next state s/.+1
12:
Split any element Z' E S St-l for which pz' < (2)) + along the middle of each side, and obtain S end for
13:
14:
end for
The predictor Øi the confidence interval width multiplier (5) and the exploration bonus b/ all designed using kernel ridge regression limited to the observations within cover elements given above. The parameter (6), in particular, is designed in way that Qf is a 1 - 5 upper confidence bound on FΛ + [PrV 11. Using Theorem I on the confidence intervals, we show that a choice of (6) 0( log( TH)) satisfies this requirement.
Figure demonstrates the domain partitioning used in -- KRVI on a 2-dimensional domain. The colors represent the value of the target function. The observation points are expected to concentrate around the areas where the target function has high value. As a result the domain is partitioned to smaller squares in that region.
Runtime complexity. The KRRV policy also runtime efficient with a polynomial runtime complexity. In particular, an upper bound on the runtime of -RRV is O similar to KOVI (Yang et al., 2020a). However, analogous (Janz al., 2020), we expect an improved runtime for T KRVI in practice. In addition, the runtime can further improve in terms of T. utilizing sparse approximations of kernel ridge predictor and uncertainty estimate (e.g., see, Vakili et al., 2022). The dependency of the runtime on [A] is due to the step given in Equation (17). If this optimization can be done efficiently over continuous domains, RRRI (also KOVI) could handle infinite number of actions. The assumption that the upper confidence bound index can be efficiently optimized over continuous domains is often made in the kernelized bandits (e.g. see, Srinivas et al., 2010a).
+ H )*), that
7

---

10
0.6
0.2
0.0
0.2
0.6
1.0
Figure A 2-dimensional domain partitioned into smaller squares.
4 Main Results and Regret Analysis
In this section, we present our main results. In Theorem 2, we establish an (H dbo/2 ato bound for KRRI,, for the class of kernels with polynomial eigendecay. We first prove bounds on maximum information gain and covering number of state-action value function class. Those enable us to present our uniform confidence interval for state-action value functions (Theorem I), and subsequently the regret bound (Theorem 2).
regret
Definition (Polynomial Eigendecay) Consider the Mercer eigenvalues {am ] of:: 2x RR given in Equation (7), in decreasing order, as well the corresponding eigenfeatures (0m los Assume Z is d-dimensional hypercube with side length pz. For some Cp. 0, the kernel said to have a polynomial eigendecay, if for all m E N, om S Cym Pzz. In addition, for some 7) 2 0, m pT 2) is uniformly bounded over all m and z. We use the notation p p(1 22).
m==1-
The polynomial eigendecay profile encompasses large class of common kernels, e.g., the Matérn family of kernels. For a Matérn kemeel with smoothness parameter v, 204d and a 2n (e.g.. see, Janz et al., 2020). Another example is the NT kernel (Arora et al., 2019). has been shown that the RKHS of the NT kernel, when the activations are times differentiable, is equivalent to the RKHS of a Matérn kernel with smoothness v
(Vakili et al., 2021b). For instance, the RKHS of an NT kernel with ReLU activations is equivalent to the RKHS of Matérn kernel with / = 1 (also known as the Laplace kernel). In this case, p = 1 1 and a 1. The hypercube domain assumption is a technical formality that can be relaxed to other regular compact subsets of Tedd. The uniform boundedness of m=P"pmm(3) for some 7) 0, also holds for broad class of kernels, including the Matérn family, as discussed in (Yang et al., 2020a). Several works including (Vakill al., 2021b; Kassraie and Krause, 2022), have employed an averaging technique cigenfeatures, demonstrating that, for the bounds on information gain, the effective value of can be considered in the case of Matérn and NT kernels.
subsets of
4.1 Confidence Intervals for State-Action Value Functions
Confidence intervals are an important building block in the design and analysis of bandit and RL algorithms. For fixed function ff in the RKHS known kernel,
confidence intervals of the form - (=)] < 3(8)6' are established in several works (Srinivas et al., 2010a; Chowdhury and Gopalan, 2017: Abbasi- Yadkori, 2013; Vakili al., 2021a) under various assumptions. In our setting of interest, however, these confidence intervals cannot be directly applied. This is due to the randomness of the target function itself. Specifically, in our case, the target function тж + [Pr 1+ which is not fixed function due to the temporal dependence within an episode. An argument based on the covering number of the state-action value function class was used Yang et al. (2020a) to establish uniform confidence intervals over all z E Z and all in specific function class. In Theorem 1, we prove different confidence interval that offers flexibility with respect to setting the parameters of the confidence interval. Our approach Ieads to more refined confidence interval,

---

which, with a proper choice of parameters, contributes to the improved regret bound achieved by our policy.
We first give formal definition of the two complexity terms: maximum information gain and the covering number of the state-action value function class, which appear in confidence intervals.
Definition (Maximum Information Gain) In the kernel ridge regression setting described in Section 2.2, the following quantity is referred as maximum information gain: TR,,(t) kzz).
max 2 log det(1
Upper bounds on maximum information gain based on the spectrum of the kernel are established in Janz et al. (2020); Srinivas et al. (2010a); Vakili al. (2021c). Maximum information gain is closely related to the effective dimension of the kernel. While the feature representation of common kernels infinite dimensional, with a finite observation set, only finite number of features have a significant impact on kernel ridge regression, that is referred to as the effective dimension. It has been shown that information gain and effective dimension are the same up logarithmic factors (Calandriello et al., 2019). This observation offers an intuitive understanding of information gain.
State-action value function class: Let use Q..A B) denote the class of state-action value functions. In particular for a set of observations Z. let (2) be the uncertainty estimate obtained from kernel ridge regression as given in (9). We define
Qk B) {Q : Q(2) min (Qu(2) + (b)(2), - h 1,, 11ll H. S R, B S T
(18)
Definition 3 (Covering Set and Number) Consider a function class F. For O, we define the minimum e-covering set C(E) as the smallest subset of FF that covers it up to an error in Loo norm. That is to say, for all E F, there exists a g C(e), such that [|ʃ gll S We refer the size of C(e) as the e-covering number.
We use the notation (e; R, B) to denote the e-covering number of Qa, (R, B), that appears in the confidence interval.
In Lemmas and 3, we establish bounds on (t, and (e,n B), respectivlly..
Lemma 2 (Maximum information gain) Consider a positive definite kernel k: Z Z - I. with polynomial eigendecay on hypercube with side length pz. The maximum information gain given in Definition 2 satisfies
[T, 0 ( (log (log(T))'
Lemma 3 (Covering Number of D B)) Recall the class of state-action value functions Q (R, B), where k : Z x Z + IR satisfies the polynomial eigendecay on a hypercube with side length pz. We have
log Ne R, =0
(
R2 R2 2
221
(1+ log
)))
R (
B
2z 2
221
1 +og log
(1))
BB)
Our bound on maximum information gain is stronger than the ones presented in Yang et al. (2020a); Janz et al. (2020); Srinivas et al. (2010a) and is similar to the one given in Vakili et al. (2021c), in terms of dependency on T. Our bound on function class covering number similar to the one given in Yang et al. (2020a), in terms of dependency on T. Both Lemmas 2 and 3 given in this work are, however, novel in terms of dependency on the domain size pz, and are required for the analysis of our domain partitioning algorithm.
We next present the confidence interval. Proofs are given in the appendix.
Theorem (Confidence Interval) Let Qi and bf, denote the kernel ridge predictor and uncertainty estimate of Tu + [Pr 1h using t observations (Vi+1 (1 at Zi { C Z, where Thi is the next state drawn from (a.-12g) Let Rr = 2H /TH.TE. (T). For c,8 8 E (0,1), with probability, at least 1 ō, we have, Vz Z, h E [H] and L [T].
(r((2) (PA (x) (6 ())( +

---

where B% is set to any value satisfying
H
TH
3v
()(0,)) ((16)1++++ +1+
log.)))+oooeM (0, + log
(19)
V2
4.2 Regret of -RKII
key step in the analysis of x =-KRVI is to apply the confidence interval Theorem a subdomain Z' E Sg. By design of the splitting rule, we can prove that the maximum information gain
corresponding to Z' satisfies (x (2)) (log(()). In addition, we choose H Aoylo 4
/ (2))
when applying the confidence interval at step h of episode t on this subdomain. That ensures log ( (2') (8, (5(6,,)) e)) (log(T)) From these, and by applying probability union
bound over all subdomains Z' created in x KRVI, we can deduce that the choice of Br(6) =
( log( ) with a sufficiently large constant, satisfies the requirements for confidence interval widths based on Theorem 1. The details are provided in the proof of Theorem in Appendix D. Then, using standard tools from the analysis of optimistic LSVI algorithms, we arrive at the following regret bound.
Theorem (Regret of π- -RRVII Consider the π TRKVI policy described in Section 3.2, with (6) = O(H / )) with sufficiently large constant implied in the θ notation. Under Assumption for kernels given in Definition 1, with probability at least 1 - ô, the regret RKRVI satisfies
R(T) O H
dta/2 ata log(T)
V log
H 8 )
(20)
The regret bound of π- -RRI presented in Theorem 2 is sublinear in 7 when > 0, in contrast to the state of the art regret bound Yang al. (2020a). The O notation used the expression above hides constants that depend p, and d. See Appendix D) for more details. When specialized to the Matérn family of kernels, replacing 2utd and a 2v, the regret bound becomes
d
R(T) = ( [1TTE
)4)
H (
log(T) log
(21)
In terms of scaling, this matches the lower bound for the special case of kernelized bandits (Scarlett et al., 2017), up to (T') factor.
Conclusion
The analysis of RL algorithms has predominantly focused simple settings such tabular linear MDPs. Several recent studies have considered more general models, including representing the state-action value functions using RKHSs. Notably, the work in Yang al. (2020a) derives regret bounds for an optimistic LSVI policy. However, the regret bounds in Yang et al. (2020a) are sublinear only when the eigenvalues of the kernel decay rapidly. In this work, we leveraged domain partitioning technique, a uniform confidence interval for state-action value functions, and bounds on complexity terms based on the domain size propose ा KRRI, which attains sublinear regret bound for general class of kernels. Moreover, our regret bounds match the lower bound derived for Matérn kernels the special case of kernelized bandits. up to logarithmic factors. It remains an open problem whether the suboptimal regret bounds in the case of standard optimistic LSVI policies (such as KOVI, Yang et al., 2020a) represent fundamental shortcoming or an artifact of the proof.
Funding Disclosure
This work was funded by MediaTek Research.
10

---

References
Abbasi-Yadkori, Y. (2013). Online learning for linearly parametrized control problems. PhD Thesis, University of Alberta.
Abbasi-Yadee Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24.
Agrawal, S. and Goyal, N. (2013). Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR.
Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R. (2019). On exact computation with infinitely wide neural net. Advances in neural information processing systems, 32.
Auer, P., Jaksch, T., and Ortner, R. (2008). Near-optimal regret bounds for reinforcement learning. In Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L., editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc.
Bartlett, P. L. and Tewari, A. (2012), REGAL: A regularization based algorithm for reinforcement learning in weakly communicating mdps. CoRR, abs/1205.2661.
Borovitskiy, V., Terenin, A., Mostowsky, P., et al. (2020). Matémn Gaussian processes Riemannian manifolds. In Advances in Neural Information Processing Systems, volume 33, pages 12426- 12437.
Calandriello, D., Carratino, L., Lazaric, A., Valko, M., and Rosasco, L. (2019). Gaussian process optimization with adaptive sketching; scalable and no regret. In Proceedings of the Thirty-Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, Phoenix, USA. PMLR.
Chowdhury, S. R. and Gopalan, A. (2017). On kernelized multi-armed bandits. In International Conference Machine Learning, pages 844 853. PMLR.
Chowdhury, S. R. and Gopalan, A. (2019). Online learning in kemelized Markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3197-3205. PMLR.
Christmann, A. and Steinwart, I. (2008). Support Vector Machines. Springer New York, NY.
Domingues, O. D., Ménard, P., Pirotta, M., Kaufmann, E., and Valko, M. (2021). Kernel-based reinforcement learning: A finite-time analysis. In International Conference on Machine Learning, pages 2783-2792. PMLR.
Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera-Paredee B., Barekatain, M., Novikov, A., R Ruiz, F. J., Schritwieserr, J., Swirszez, G., al. (2022). Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-53.
Hoeffding, W. (1994). Probability inequalities for sums bounded random variables. The collected
works of Wassily Hoeffdding, pages 409-426.
Janz, D., Burt, D., and González, J. (2020). Bandit optimisation of functions in the Matérn kernel RKHS. In International Conference on Artificial Intelligence and Statistics, pages 2486-2449 PMLR.
Jin, C., Allen-Zhu Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? Advances in neural information processing systems, 31.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR.
Kahn, G., Villaflor, A., Pong, V., Abbeel, P., and Levine, S. (2017). Uncertainty-aware reinforcement learning for collision avoidance. arXiv preprint 170.01170..0
Kalashnikov, D., Irpan, A., Pastor, P., Ibarz, J., Herzog, A., Jang, E., Quillen, D., Holly, E., Kalakr- ishnan, M., Vanhoucke, V., et al. (2018). Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, pages 651-673, PMLR.
11

---

Kassraie, P. and Krause, A. (2022). Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Statistics, pages 240-278. PMLR.
Lee, K., Kim, S.-A., Choi, J., and Lee, S.-W. (2018), Deep reinforcement learning in continuous action spaces: case study in the game of simulated curling. In International Conference Machine Learning,, pages 2937- 2937-2946. PMLR.
Li, Z. and Scarlett, J. (2022). Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics.
Mercer, (1909). Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 209:415-446.
Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J. W., Songhori, E., Wang, S., Lee, Y.-J,, Johnson, E., Pathak, O., Nazi, A., al. (2021). A graph placement methodology for fast chip design. Nature, 594(766))207-212..
Neu, G. and Pike-Burke, C. (2020). A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1392-1403.
Pozrikidis, C. (2014). An introduction to grids, graphs, and networks. Oxford University Press.
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
Russo, D. (2019). Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32.
Salgia, S., Vakili, S., and Zhao, Q. (2021). A domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance. Conference on Neural Information Processing Systems, 34.
Scarlett, J., Bogunovic, I., and Cevher, V. (2017). Lower bounds on regret for noisy Gaussian process bandit optimization. In Conference on Learning Theory, pages 1723-1742. PMLR.
Schölkopf, B., Smola, A. J.. Bach, F., al. (2002). Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanetot, M., al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):4844889
Srinivas, N., Krause, A., Kakade, S., and Seeger, M. (2010a). Gaussian process optimization in the bandit setting: No regret and experimental design. In ICML 2010 Proceedings, 27th International Conference on Machine Leurning, pages 1015-1022.
Srinivas, N., Krause, A., Kakade, S., and Seeger, M. (2010b). Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 1015-1022.
Vakili, S., Bouziani, N., Jalali, S., Bernacchia, A., and Shiu, D.-s. (2021a). Optimal order simple regret for Gaussian process bandits. Advances in Neural Information Processing Systems, 34:21202- 21215.
Vakili, S., Bromberg, M., Garcia, J., Shiu, D.-s., and Bernacchia, A. (2021b). Uniform generalization bounds for overparameterized neural networks. arXiv preprint arXiv:2109.06099.
Vakili, S., Khezeli, K., and Picheny, V. (2021c). On information gain and regret bounds in Gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR.
Vakili, S., Scarlett, J., and Javidi, T. (2021d). Open problem: Tight online confidence intervals for RKHS elements. In Conference on Learning Theory, pages 4647-4652, PMLR.
12

---

Vakili, S., Scarlett, J., Shiu, D.-s.. and Bernacchia, A. (2022). Improved convergence rates for sparse approximation methods in kemel-based learning. In International Conference on Machine Learning, pages 21960-21983. PMLR.
Valko, M., Korda, N., Munos, R., Flaounas, I., and Cristianini, N. (2013). Finite-time analysis of kernelised contextual bandits. In Uncertainty in Artificial Intelligence.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H.,
Powell, R.,. Ewalds, T., Georgiev, P., al. (2019). Grandmaster level in starcraft II using multi-agent reinforcement learning. Nature, 575(7782):30-335.
Williams, C. K. and Rasmussen, C. E. (2006). Gaussian processes for machine learning. MIT press Cambridge, MA.
Yang, L., and Wang, M. (2020). Reinforcement learning feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR.
Yang, Z., Jin, C., Wang, Z., Wang, M., and Jordan, M. (2020a). Provably efficient reinforcement learn- ing with kernel and neural function approximations. Advances in Neural Information Processing Systems, 33:13903-13911
Yang, Z., Jin, C., Wang, Z., Wang, M., and Jordan, M. (2020b). On function approximation in rein- forcement learning: Optimism in the face of large state spaces, arXiv preprini vrXiv:2011.04622.
Yang, Z., Jin, C., Wang, Z., Wang, M., and Jordan, M. I. (2020c). On function approximation in rein- forcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.042: 1,04622.
Yao, H., Szepesvári, C., Pires, B. A., and Zhang, X. (2014). Pseudo-MDPs and factored linear action models. In 2014 JEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pages 1-9. IEEE.
Ych, S.-Y., Chang, F.-.., Yueh, C.-W., Wu, P.-.,, Bernacchia, A., and Vakili, S. (2023). Sample complexity of kernel-based q-learning, In International Conference on Artificial Intelligence and Statistics, pages 453-469. PMLR.
Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M., and Lazaric, A. (2020a). Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. (2020b). Learning near optimal policies with low inherent Bellman error. In III. H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10989. PMLR.
13

---

A Mercer Theorem and the RKHSs
Mercer theorem (Mercer, 1909) provides representation of the kernel in terms of infinite dimensional feature map (c.g., see, Christmann and Steinwart, 2008, Theorem 4.49). Let Z be compact metric space and μ be finite Borel measure on Z (we consider Lebesgue measure in Euclidean space). Let (2) be the set of square-integrable functions on Z with respect to We further say kernel is square-integrable if
| d((=zz))d(()ddp())) < co.
Theorem (Mercer Theorem) Let Z be a compact metric space and be a finite Borel measure on 2. Let be continuous and square-integrabi kernel, inducing integral operator Tç. (Z) + (Z) defined by
()) -0,0-//(0/0000 ((,2)((2)))))))( d22)))()))))
where f E (Z). Then, there exists a sequence of eheevvalu-eigenffaauuee pairs {foms 6 mm) ) such that am O, and T Tw om for m 1. Moreover, the kernel function can be represented
as
1o (2,
E
Fm Om (m) (z)
(z'),
where the convergence of the series holds uniformly on Z x Z.
According the Mercer representation theorem (e.g., see, Christmann and Steinwart, 2008, Theorem 4.51), the RKHS induced by l can consequently be represented in terms of {am, pm) J
be the Mercer eigenvalue eigen- Theorem (Mercer Representation Theorem) Let {(om: 2m H feature pairs. Then, the RKHS of k is given by
H4 f(-)
Wm (. Wm E R. [l
w
m=1
Mercer representation theorem indicates that the scaled eigenfeatures thonormal basis for Hi-
fm m= form or-
B Proof of Theorem 1 (Confidence Interval)
Confidence bounds of the form given in Theorem have been established for a fixed function f with bounded RKHS norm and sub- Gaussian observation noise in several works including Abbasi- Yadkori (2013); Chowdhury and Gopalan (2017); Vakili al. (2021a). In the RL setting, however, apply the confidence interval to f = ra + [Pr Vi+ Although the RKHS norm this target function is bounded by / + 1, this is not fixed function as it depends on Vi+ In addition the observation noise terms VA++1 ( ) Pr, (*s,, af,)) also depend on V To handle this setting, we prove a confidence interval that holds for all possible Vi+1 S + H]. For this purpose, we use probability union bound and covering set argument over the function class of V Vh+1"
We first recall the confidence interval for fixed function and noise sequence given in (Chowdhury and Gopalan, 2017, Theorem 2). See also (Abbasi-Yadkorii, 2013, Corollary 3.15).
Lemma 4 Let {2' ZYT= be stochastic process predictable with respect to the filtration (FiYE Let {T' be a real valued Fe measurable stochastic process with a Sabh-Gusssin distribution conditioned on Fr-1. Let prr and b be the kernel ridge predictor and uncertainty estimate of f using noisy observations of the form {f(=T) + + -- Assume f E BR Then with probability at least 1 8. for all z E Z and t t2
1f(z) (x)( (2)
(22)
where B1 = R 2 ((T
l))
14

---

As discussed above, we cannot directly use this confidence interval on + [P. in the RL setting. Instead, we need to prove new confidence interval that holds true for all possible h4+1- We thus define V to be the function class of h+1 as follows.
(R, = (V (()) = max Q(s, a), for some Q E QE,M(R, B)}.
(23)
aEAA
For simplicity of presentation, we specify the parameters It and B later.
Let (e; R, B) be the smallest e-covering set of V4,n B) in terms too norm. That to say for all V E Va,A (R, B), there exists some V E CV (E; R, B) such that ||V Viliz I e. Let NE, (e; R, B) denote the e covering number of Va,n (R, B). By definition NE (e: R, B) = IC (6; R, B-
We create confidence bound for all V (,, R, B). using Lemma 4 and a probability union ef
bound over Ch2, R, B). Fix h E [H] and t [T. Let us the notation Q for the kernel ridge predictor with V. That is @ (2) (2 YY, where Y (V(s =1=+)))=-1 and 8/111 is the next state drawn randomly from probability distribution P..-)2)) In addition, to simplify the notation, we use = ra + [Pr]] and مم = @ Also, let (=) = (k(2,z) (=) + 2) k2: (z)) Then, we have, with probability at least 1 5, for all V E (e, R, B) and for all E 2,
(ø(2) - (z)) (2)
(24)
where B2 H +1+ v2 V (T.a(t) + No (c; R, B) + log(z).
Confidence interval (24) is a direct application of Lemma 4 and using a probability union bound over all V E Ch,, R, B). Note that, ||,, + P/ VlN2 S H + (Lemma 1). In addition, V(s (2)) [0, H] for all h and т. A bounded random variable in [o, H] is H/2 sub-Gaussiaa random variable based on Hoeffding inequality (Hoeffding, 1994).
Now, we extend the uniform confidence interval over all V E (e R, B) to uniform confidence interval over all V VR, B). For some V E: VR, B), define f f= rn + [PAV] and n²م Q',
similar to g and μ/. By definition of (c; R, B), there exists V Ch, B), such that
||V Vllae I 6. Thus, for all 2 E 2,
[PV](=) (PV()) (PV] f(=)
sup sup (V)) -
(25)
Therefore, with probability at least 5,
If(=) - -1)((2) s 1f(z) g(2) + - /t-(()) 11110(2)) -11((2))
S Bzb' (z) + +ct (2))(2) (2)) 1¹:1 (z)).
(26)
Next, we prove that 1 (2)- <
(z))
3c)
Let us further simplify the notation by introducing (2) = (K -22 FT = [PA) = [g(2))) E, = =|=-
[[(+
E = -E
so that t/'d (z) = a (z) + E,) and (z = a (z) + E.).
As discussed earlier, the observation noise terms et also depend on V. We have, for all t > 1.
E --=-" E²| =
- - (
< 2c.
15

---

Using the difference between f and as well as the difference between noise terms, we have (1)+((2) (=))
= (x) + E,) - a' (=)(G, + E2) s ||aa())|l| - G. + E, - Eell
s (evi)la((2)
3e (z)
where the last inequality follows from ||o - (=) X (e.g.. see, Vakili et al., 2021a, Proposition 1).
The bound on 1 (z)) combined with (26) proves that for a fixed t [T], fixed E [H], for all = 2 and for all V Ve,a B),
(5(z) ndd (=) s (z) te,
where
H
3 (27)
83 - 11+++ + log 6 BB) log(
The confidence interval holds uniformly for all E [H] and & E [7] using a probability union bound, when B3 is replaced with the following
H 22 V (ma(1) Nog.NN, B)
HT
3evi A
Ba = ++
log(
(28)
To complete the proof, we bound NW (c; R, B) in terms of the specific parameters of the problem. Firstly, the e-covering number of VA. ( R, B) is bounded by that of Qk, (R, B) (Yang et al., 2020a, proof of Lemma D.1). Recall the definition of Qu, B) in (18). We note that 10i1 I 211 / (t) (Yang et al., 2020a, Lemma C.1). Thus, the theorem follows with B) (8,e), e), where (5, set to some value satisfying
H
HT 8
3evt
(8,)))) H ++
V2 V [2,)(() Na, R., (1,, + log(
+ A
(29)
with R. 2H (TRA())) That completes the proof of Theorem 1.
C Proof of Lemmas (Maximum Information Gain) and 3 (Covering Number).
We first introduce the projection of the RKHS lower dimensional RKHS that is used in the proof of both lemmas. We then present the proofs, Recall the Mercer theorem and the representation of kernel using Mercer eigenvalues and eigenfeatures. Using Mercer representation theorem, any f E BR can be written as
Σ Wm v o Um
(30)
with E0 2 < R22 For some D E N, let [T]s]] denote the projection of onto the D- dimensional RKHS corresponding to the first D features with the largest eigenvalues
1IIlf
Σ
Wm / o
(31)
Let us use the notations wp [Wi, W2, TDD for the D-dimensional column vector of weights, (x))) (x)(2), (2)), (()())))))))) for the D-dimensional column vector of eigenfeatures, and
16

---

Σp diag(lo1. 02, ,pl) for the diagonal matrix of eigenvalues with [01. "2, o as the diagonal entries. We also use the notations
= =b)))))=(())
(32)
to denote the kernel corresponding to the D-dimensional RKHS, as well as (2,, = k(2,z²)
kD (z,z')
C.1 Proof of Lemma on Maximum Information Gain
Recall the definition of (t)) We have
log det [ 2e (2z)
1 log det
1
1
(K2
+ k2-))
2
12
2 log det
1
1
22
1
Z'
+ 2
log der
(1+
1
x2
1
(1
1
K
22222-11
Term (4)
Term (ii)
next bound the two terms on the right hand side.
Term (i): Note that for DP corresponding to the D-dimensional RKHS, we have K = D
where Q = (z)(2))=c2 is a t x D matrix that stacks the feature vectors (2(2)), = 1,... as
rows. By Weinstein- Coanstein-Aronzajann identity (Pozrikidis, 2014) special case of matrix determinant lemma),
log det (r'
x2 2z
= log det
I'
D.DD
(33)
X2
= log det
1 + [
X2 -1.000110
tr(TD + +
Dlog(
D
D Dogg(1 +
X²D
The first inequality follows from the inequality of arithmetic and geometric means eigenvalues of the argument, and the second inequality follows from I.D 1. For clarity, we used the notations J and DD for identity matrices of dimension and D, respectively. Otherwise, we drop the superscript.
Term (ii): Similarly using the inequality of arithmetic and geometric means on eigenvalues, bound the log det by the log of the trace of the argument. Let us use eD to denote an upper bound on k
log det (++
1 (T+ (T+
1 -2-0--kk 12
K2))
-kx
log
[r([+ + 32 (I+ (
1 K2) 22
K2.) -K.))
(34)
x2
log (1
(D)
X2
TED
X2
The last inequality uses log(1 x:) S which holds for all RR
Combining the bounds on Term (i) and Term (it), we have
D log(1 + X²D )
tep
(t) < 2
(35)
2X2
17

---

Now, using the polynomial eigendecay profile given in Definition 2,
k (2,)))
=
Dm (2)
(36)
m= D+
Csppp
m -p(1-2n)
m=D-1
000
cpp2
dd
Pppp2 D-
pp2
(37)
The constant C₁ is the uniform bound on m PM Rm and Cp is the parameter in Definition
Choosing D Ct pz (log(t))- ,, with constant C C. (5- we obtain
C 12 (10e(()+ log(1 + X²D ) + (log(())=+))
t
(1)
(38)
that completes the proof.
C.2 Proof of Lemma on Covering Number of State-Action Value Function Class
Recall the definition of the state-action value function class,
(R, Q(2) min (Qo(z) + 36(=), h + 1}, 11101 S &R
B, ST}.
and the notation NR. a. (e; R, B) for its e-covering number. Let us use the notation R() for the e-covering number of RKHS ball BR R {f llffllxe < <R).Noo.n (e) for the e-covering number of interval [0, B] with respect to Euclidean distance, and (V,,((c for the c-covering number of class of
uncertainty functions by {b(z) (k(z, 2) - (=) + kzz 3 |2| T}.
Consider Q,Q E Qu, B) where Q(z) min (Qn()) + 3b(=),bb3()))))))))) H h 1} and Q(2)
min (Qo(2) + 3b(2), H h + 1]. We have
[Q(z) Q(=) < (Qo(=)
Blb(2) b(=))-
(39)
That implies
Ne,(e S Nu.n Mo. Mo.nn Wo.ll 3B
(40)
For the e-covering number of the (0, B interval, simply have Ni,.m(c/// < 3B/B.. In the next lemmas, we bound the e-covering number the RKHS ball and the class of uncertainty functions.
Lemma (RKHS Covering Number) Consider a positive definite kernel k : 2 - R, with polynomial eigendecay on hypercube with side length pz. The e-covering number of R-ball in the RKHS satisfies
(( 18 pz (1T22
2))-
log (e, =
log(1
(41)
Lemma (Uncertainty Class Covering Number) Consider a positive definite kernel x Z R. with polynomial eigendecay hypercube with side length pz. The c-covering number of the class of uncertainty functions satisfies
No, = (1))))2211
(42)
18

---

Combining (40) with Lemmas 5 and 6, we obtain
R BB) R2 ) (1 + log( -
(
B²p² 6²
) (1 log( B
-1
(43)
that completes the proof of Lemma 3. Next, provide the proof of two lemmas above the covering numbers of the RKHS ball and the uncertainty function class.
Proof (Proof of Lemma 5) For f in the RKHS, recall the following representation
Wm V
(44)
mrml
as well as its projection on the D-dimensional RKHS
Tn = Σ
Wm V mm
(45)
m=1
We note that
|| - Ibffllo
= Σ
Wm mo
m= m=D+1
s
C. Pz
Wmm im p(1 -() -n)
m=D+1
1
s
CC a/2
Σ
[mml 12
Σ
p(1
Am= D+1
Im D+1
s CC 0/2
x dd
CiC R D
0/2 Pz
In the expressions above, C1 the uniform bound on PD &m and C.p is the constant specified in Definition 1. The third inequality follows form Cauchy-Schwarz inequality.
Now, let Da be the smallest D such that the right hand side is bounded by 5. There exists a constant C2 > O, only depending on constants C₁ Cy 17 and p. such that
R2p2
R2
p-1
Do S.C, C2
(46)
For a D-dimensional linear model, where the norm of the weights is bounded by R, the e-covering at most C3D(1 + log( E), for some constant C3 (e.g. see, Yang al., 2020a). Using an e/2 covering number for the space of 1DD[f] and using the minimum number of dimensions that ensures If [1] < e/2, we conclude that
R log.N,,R(e) - CoDo log
-))
Rep3 ?
R log(
C2Cs
(1
-1),
that completes the proof of the lemma.
19

---

Proof 2 (Proof of Lemma 6) Let us define b = {b² b E b and N4, to be its e-covering number. We note that, for b, E b.
[b() b(z)) S V (b(z))² (b(2))²1
(47)
Thus, an e-covering number of is bounded by an -'ooeriing of b²:
Ne,((e) S &Ni,oa(Ee).
(48)
We next bound N2, (E²).
Using the feature space representation of the kernel, we obtain
(b(2)) Σ mm (2),
(49)
for some 7m E [0, 1]. Based on the GP interpretation of the model, i' can be understood as the posterior variances of the weights. Let Do be the smallest D such that Em=D+1 o Tm (m) I e² From Equation (37), we can see that, for some constant Ca. only depending on constants C1, Cp. and p.
Do C4
(50)
For DDo 7 om 8n (z) on a finite Do-dimensional spectrum, as shown in Lemma D.3 of Yang et al. (2020a), an e² 2 covering number scales with Da- Specificully, an 2/2 covering number of the space of Ym' Tm m 2n 2 (2) is bounded by
+
(51)
Combining Equations (50) and (51), we obtain
(e7 1 C.D log(
S C& p
that completes the proof of the lemma.
D Proof of Theorem 2 (Regret of -KRVVI)
Following the standard analysis of optimisite LSVI policies, for any [H]. t E [T], we define temporal difference error 6% Z R as
(1((2) = rx) (1 - Q+)(2,, V2 E Z.
(52)
Roughly speaking, (2)) quantify how far the {Q are from satisfying the Bellman optimality equation.
1/1
For any h E [H) E (T). we also define
ch = (v)(s)) Vे (sh) - (Qh(e)) - Q (2h))
S = (PRAV441)(*))) - (PA
(PAVTLL(( - (Vh+1(sh41)
VV (hh+))
(53)
Using the notation defined above, then have the following regret decomposition into three parts.
20

---

Lemma (Lemma 5.1 in Yang et al. (2020a) on regref decomposition) We have
T
H
T
R(T) =
Ex
(2n)ss1
=
-
Ch
1=1 hmm
(=1 h=
(6)
(18)
T
H
Ex 1Q (sn)) - 2 (sh, (sn)))ss = st
(54)
(sis)
The third term is negative, by definition of T that the greedy policy with respect Q/: (sh,, (sx)) - Q (SA, (s.)) Q (sh, (7())) - max Q (sh, a) S 0,
aEA
for all 9p. E S. The second term bounded using the following lemma.
Lemma 8 (Lemma 5.3 in Yang et al. (2020a)) For any 8 E (0, 1), with probability at least 1 8, we have
T H
ΣΣ t=1 ==
SE + (
S
TH3 log
(55)
Term (t): turns out that the dominant term and the challenging term to bound the first term in
Lemma 7. We next provide upper bound on this term.
For step h, let UT = - Sj be the union of all cover elements used by KRRI over all episodes. The size of Uh is bounded in the following lemma and is useful in the analysis of Term (i).
Lemma 9 (Lemma 2 in Janz et al. (2020)) The size of satisfies
u S Co
(56)
for some constant Cs.
The size of UT, depends on the dimension the domain and the parameter a used in the splitting rule in Section 3.1.
Now, consider cover element 3' E EU, Using Theorem 1, we have, with probability at least for all h E HH), E [T), E Z', for some of (0, 1),
(x)( + ([))) (h()) S (1) +
(57)
where (,, (l)) is the smallest value satisfying
NH
3v NN
(5 c 2 H +++ V2
(6,, + +1+ + log (xx((N) + log Na Rx (x,
+
with = NT. and ef " 2
VNT.e"
We also note that
TRA(NZZ))
O ((VV.))) (1gg2)))
O (P2z) (log(NT. (1) +1)
O (108((N7.2:))
O (log(T))
(58)
21

---

where the first line is based on Lemma 2, and the second line is by the design of partitioning in T--RRI. Recall that each hypercube is partitioned when Pz' No. h + 1, ensuring that N7.z remains at most Pzr.
For the covering number, with the choice of c/ H Hylog( 4
have
log N RN. (5,,)))))
R2
P-1
RN )) + (1)16.c))))
7-1
(1(6.
(1 + log(
(1+ + log(
(e,))
(ch))²
Ry
J
RN ]) +
(8, (1))) H12 log( )))
3 ph(0,6h) (60,6h)))
(1 log(
(1 (1+log( log(
Ho
HT
c/
We thus that the choice of (6, ( v log( 1 satisfies the requirement for confidence interval width Z' based on Theorem 1. We probability union bound over all Z' UK to obtain
TH )) = ((H log TH
0r()) = ((H log(
(59)
5
For this value of (o)) we have with probability at least 1 - 6, for all h [H] E [T]. E Z.
(z) + [[+1((() (+)) < (0)) +
(60)
where in the above expression of is the parameter of the covering number corresponding to 2' when E Z'.
Therefore, we have, with probability at least 1 -
Term (1) s
(2h)) I 23r(0)
Σ
by (2h)) )
2ch.
(61)
t=1 A=
1=1 hm1
with
c = H V log TH o
(62)
2(,)s)))
We bound the total uncertainty in the kernel ridge regression measured by Σt= (2))))
T
Σ (BA())))² = Σ
(bh)))
Z'EUK
E,
Σ
log(1 + 1/22) (N
2
z'eur
= o log(T)
2' Z'EuT
O (1447 loo (T)
o T log (T)
The first inequality commonly used in kernelized bandits. For example see (Srinivas al., 2010a, Lemma 5.4). The third and fifth lines follow from Equation (58) and Lemma 9, respectively. Also,
22

---

we have
T a log( TH
Σ (ch)
(63)
N, (xf,)
H² log( TH
N Ni,2' TH (log(()) +1)
Z'Eug 2/,22'
U 122 log(
8
o
T d log( T
TH
log log((T) (T)
8
We are now ready to bound the
T H
T
H
Term (i) v
23r(5)
Σ
b/1 (2h)
+
(64)
h
1=1 h=1
1m1
H
I 28r(5) T
( (=t))) 2VT
Σ (c,))
dto/3 o H2T H1T d-a
TH V Vlog(7) (T) log(
8
The proof is completed.
23


Reviews:
[{"review_id": "2OguybGOgU", "reviewer": "Reviewer_qSio", "summary": "This paper theoretically studies the performance of a reinforcement learning algorithm under the assumption that the Q function is a member of RKHS with a known kernel. The authors provide cumulative regret bound on the iterative-least value iteration algorithm and specialise their results to the kernel with polynomial decay of eigenvalues. They improve the regret bounds of prior works by refined analysis of confidence sets in this non-parametric setting. ", "questions": "- Mercer decomposition diagonalize the infinite dimensional operator either under a specific distribution or on a bounded domain (essentially uniform distribution), could you be more specific what you mean by the Mercer decomposition in Section 2.2 \n- Why is there H^2 in the regret bounds? What is the nature of this? One \"H\" would be more intutivie. \n- How are quantities Infogain and covering numbers related?\n- Does one also need info-gain to derive the bound? Clearly there are bound with only the info-gain, can there be only covering number bounds? I wonder if works by van der Geer on high dimensional statistics are related to this. \n- Covering numbers for Sobolev paper are well-studied objects in functional analysis, especially due to seminal paper of field’s medalist Smale. I suggest looking into ref in publications of this author.\n", "limitations": "None identified. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly written in the context of its rather technical nature. \n\nThe work combines the newest understanding of adaptive confidence sets and their analysis for the case of Matern kernels with Linear MDPs, by providing a kernelized variant of thereof. I am not familiar with the other literature utilising the novel variants of the analysis in the context of RL. \n\nSeems like there is a sub-community interested in this issue given the COLT open problem, however, as somebody not in this community, I have to say it seems certainly a matter of taste rather than importance. \n", "weaknesses": "The prior work, [10] indeed does not provide optimal bounds, but arguably the algorithm seems to be more practical than a rather time-varying discretization of the domain in order to facilitate the construction of the order optimal confidence sets. \n\nTo be slightly harsh I wonder if the proper academic solution would not have been informing the authors of [10] of this new technique rather than writing a wholly new paper which utilises the trick with the domain splitting which comes from other prior works e.g. [14]. At the expense of creating more elaborate confidence sets one can indeed improve the bounds, but whether this improves the performance remains unanswered in this paper, as no comparison is provided. The proposed contribution is solely of theoretical nature. \n\nIt is common in online learning to use the doubling trick and mention it in passing in case improved results are desired. I wonder if this is not a similar discretization trick, and whether this deserves an independent publication at NeurISP.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We value your feedback and are pleased that you found the paper clearly written. We address your comments below and hope that it will positively impact your evaluation of the paper. We are open to further discussion if required. \n\nIn terms of contribution, we would like to mention that we make substantial contribution to the related work. For example, we provide flexibility in setting the parameters of the confidence interval (in Theorem 1), that ultimately contributes to the improved regret bounds. We also derive bounds on the maximum information gain (Lemma 2) and the function class covering number (Lemma 3), taking into consideration the size of the state-action domain. Lemma 2 provides a stronger bound than the one used in [14], which also contributes to the improved regret bounds. Thus, in applying the partitioning technique of [14] to the kernel-based RL problem, we make significant improvements to the technique and provide a finer analysis that also significantly improves the results of [14], as stated in lines 91-93 in the introduction. To further clarify this point, we will report the regret bounds for kernel bandits in [14, Theorem 3], which is in order of $\\tilde{O}(T^{(d(2d+3)+2\\nu)(d(2d+4)+4\\nu)})$, and has a polynomial gap from the $\\mathcal{O}(T^{(\\nu+d)/(2\\nu+d)})$ proven in our work for the more involved RL setting. Given these significant improvements, we believe our results constitute a significant contribution to the literature regarding achievable regret bounds in kernel-based RL. Nonetheless, our work reports the first order optimal regret bounds in $T$ for a broad class of common kernels, which is a novel result that may be of wide interest in the community and become a main reference for the achievable regret bounds. \n\nResponses to all questions (in order):\n\n-  A formal presentation of Mercer theorem with the details is provided in Appendix B. For example, we can consider the Lebesgue measure as stated in Appendix B. We note that our analysis only relies on the expressions of kernel and RKHS elements in terms of eigenvalues and eigenfeatures given in equations (7) and (8). The choice of measure in Mercer theorem only affects the eigenvalues and eigenfeatures, and not the expressions in equations (7) and (8) or the rest of our proof. For regular domains such as hyperspheres and hypercubes, with typical kernels, Mercer decompositions are well studied and can be used within our results. Following your comment, we will make this further clear in the paper. \n\n- One $H$ scaling seems to be due to the RKHS norm of state-action value functions, the target functions in kernel ridge regression. Lemma 1 shows that this norm scales with $H$. Our results on regret bound align with those in the SOTA [10]. With our results, the optimality of scaling with $H$ cannot be determined. We will make this point further clear in the paper.\n\n- Information gain and covering number both represent the complexity of the function class that we are considering. Roughly speaking, information gain represents the effective dimension of the kernel. That is to say, while typical kernels have an infinite-dimensional feature space, only a limited number of features have a significant effect on the regression with a finite dataset. This represents the effective dimension that is the same as information gain up to a log factor. The covering number, on the other hand, is determined by the RKHS topology, gauging the count of RKHS elements required to approximate the entire set within a given sup norm error margin.\n\nWhile information gain and covering number represent distinct complexities of the problem, they are both characterized using the kernel spectrum. Thus, it is expected that their value is related. Please see Lemmas 2 and 3 for bounds on their value. In our domain partitioning algorithm, we set $\\epsilon$ proportional to $1/\\sqrt{N}$, where $N$ is the number of samples in the corresponding subdomain, while [10] sets $\\epsilon$ proportional to 1/T. In both cases, covering number turns to be the dominating term in the confidence intervals width factor. \n\n- We here provide a brief explanation on where these quantities appear in the analysis. Please let us know if further details are needed. \n\nOne important component in the analysis is the confidence intervals for the kernel-based models. The information gain appears due to adaptivity of samples and the covering number appears to to variation of the target function. In an offline setting, $1-\\delta$ confidence intervals of the form $|f(x)-\\mu_t(x)| \\le \\beta(\\delta)\\sigma_t(x)$ are established where $\\beta(\\delta) = R+\\sqrt{\\log(\\frac{1}{\\delta})}$ up to multiplicative constants, which are not related to information gain and covering number. In the online setting, with adaptively collected samples (bandit or RL, for example), information gain appears in the confidence interval $\\beta(\\delta) = R+\\sqrt{\\Gamma + \\log(\\frac{1}{\\delta})}$. Please see the work on vector valued self-normalized martingale inequalities and their extension to Hilbert spaces [17,34,42]. In addition, in the RL setting, the target function itself is not predetermined and varies due to Markovian dynamics. The confidence interval thus needs to hold uniformly for all functions within a certain class. This is where the log covering number appears in the confidence interval, $\\beta(\\delta) = R+\\sqrt{\\log N + \\Gamma + \\log(\\frac{1}{\\delta})}$. It is thus expected for both terms to appear in the regret bound of standard LSVI [10]. In our approach with the domain partitioning technique, we ensure both terms stay logarithmic in $T$ at most, and instead we bound the number of partitions, which leads to the improved regret bounds. \n\n- Thank you. We will look into this for future research on the topic.\n"}, {"review_id": "JrXT5pCYuT", "reviewer": "Reviewer_fuZF", "summary": "This paper presents an optimism-based online learning algorithm for RL with large state-action spaces (including continuous spaces). It proposes a (Gaussian) kernel-based function approximation + optimism (building on UCBVI) algorithm. It assumes that the reward and transition density functions are representable in  1-bal of an RKHS (with a Gaussian kernel), which is quite reasonable.  It also introduces a domain-partitioning technique  to make the kernel ridge regression part scalable. The regret bound obtained for the algorithm is shown to be an improvement over SOTA [10]. Specifically, regret scales H^2 and sublinear in T. ", "questions": "1. Could you present some numerical studies so we can understand the strength of your algorithm? It could even be large tabular but difficult problems such as DeepSea and Montezuma's revenge.", "limitations": "Kernel-based method may limit scalability. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Online RL algorithms for continuous state and action spaces is a really challenging problem, and until recently was unresolved. This is the best such result I have seen. It makes a very smart (and now seemingly natural) use of kernel-based function approximation. ", "weaknesses": "The authors have not presented any numerical results. So it leaves one wondering whether it is all nice theory, and there is some hope of the making the algorithms practical.\n\nNote: Title has a typo for Kernelized\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We appreciate your feedback and are glad that you mention the significance and novelty our results. \n\nWhile we agree that numerical experiments are important for evaluating the practicality of RL algorithms, our main contribution in this paper is theoretical in nature, similar to existing work, e.g., [9-10].\n\nThere seems to be a natural progression of model complexity in RL, from tabular to linear, to kernel-based, and to deep learning based. While tabular and linear problems are adequately studied, the state of the art delas with kernel-based RL. Our work makes a significant contribution by providing an order-optimal regret bound in the number of episodes for a broad class of common kernels. This contribution is particularly important considering that existing results fail to demonstrate even sublinear regret bounds for this class of kernels. We appreciate your recognition of the significance of our results."}, {"review_id": "zxMr5ZIqk2", "reviewer": "Reviewer_2xmH", "summary": "This paper proposes a reinforcement learning algorithm called $\\pi$-KRVI that achieves order-optimal regret. The algorithm performs local kernelized optimistic least squares value iteration update - specifically, it partitions the state-action space so that each cell contains a small number of observations, and the Q value within a cell is updated to a Gaussian Process based Upper Confidence bound using observations in that cell only. This is motivated by KOVI [10] and $\\pi$-GP-UCB [14]. A sublinear upper bound on the regret is given - this seems to be the first sublinear bound in a general setting, and it is claimed to be order optimal in the number of episode $T$.", "questions": "I would appreciate a discussion on the weaknesses before minor comments.", "limitations": "A discussion on the limitation of Assumption 1 would be beneficial.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The sublinear regret seems to be the first one established in a general setting, and this seems to be order-optimal. The paper is generally clear, but a few things could be improved as mentioned in Weaknesses. The idea seem to be sound, but I didn't read the proofs.", "weaknesses": "* The paper only informally refers to [19] when stating the bound is order optimal. This is not immediately clear due to differences in notations, and some ambiguity in the paper's discussion. A more precise and detailed discussion would be helpful.\n* It is not clear what ${\\cal S}$ and ${\\cal A}$ are, but it seems both are cubes? If yes, is this a necessary assumption?\n* The reward functions and transition distributions are assumed to have a norm $\\le 1$. How will the regret change if the upper bound is larger than 1?\n* Lemma 1: $V$ is not used anywhere. Is it supposed to be $V_{h+1}$? If yes, an arbitrary $V_{h+}$ can potentially have a large norm, and Eq. (11) may not hold? A proof of the lemma seems to be missing.\n* Line 233: why is the target value constructed using a new random state $s_{h+1}'$, rather than the random state $s^{t}_{h+1}$ from the current episode?\n* Line 248: Does the running time refer to the total running time of Algorithm 1? If yes, can you explain why the upper bound is independent of the size of the partitions?\n\nMinor comments\n* Kernel ridge regression is generally described as a method that doesn't provide any uncertainty estimate, while the paper describes it as a method that provides uncertainty estimates. In particular, [38] is cited as the reference, but it doesn't seem to provide such an account of kernel ridge regression. What's described as kernel ridge regression is Gaussian process regression.\n* A brief explanation on the motivation behind maximum information gain would be helpful.\n* Putting the pseudocode of the algorithm in the paper would be helpful. Alternatively, provide a more complete description of the algorithm.\n* Algorithm 1, line 10: $x_{h}^{t}$ should be $s_{h}^{t}$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We appreciate your feedback and we are glad that you find the paper generally clear. We respond to all your comments in the weaknesses section (in order) and hope that it positively affects your evaluation of the paper.\n\n- In the kernel based bandit setting, which corresponds to the special case of $H=1$ and $|S|=1$, [19] established a lower bound of $\\Omega(T^{\\frac{\\nu+d}{2\\nu+d}})$. This lower bound implies that the regret bound in Theorem 2 cannot be improved in terms of $T$, in general. We however agree with the reviewer that a lower bound under the RL setting, taking into account the general case and incorporating $H$ would be useful. That however seems itself a challenging problem and beyond the scope of this paper. We will add a more detailed and precise discussion following your comment.  \n\n- In our construction of the domain partitioning, we assume that $\\mathcal{S}\\times \\mathcal{A}$ is a hypercube, implying $\\mathcal{S}$ and $\\mathcal{A}$ are hypercubes. This is for simplicity and correctness of a formal derivation. This assumption is not necessary for the overall approach. The domain partitioning technique can be applied to other compact subsets of $R^d$ by considering the smallest cube containing the domain. This allows us to apply the partitioning technique and obtain valid results for RL problems with non-cube-shaped state and action spaces.\n\n- Scaling the norms of the reward functions and transition distributions with a constant 'C' would scale the \"H+1\" term in the confidence interval (see Theorem 1) with C. This represents the RKHS norm of the target function in kernel regression. However, this additive term does not affect the order of the regret bounds, as it is overshadowed by the dominant terms (information gain and log covering number), which grow with $T$. This is similar to the case of kernel bandits, where the regret order in $T$ remains unchanged as long as a bound on the RKHS norm of the target function is known. Only if the RKHS norm of the function scales with $T$ would further investigation be needed to understand the impact on the regret bounds. \n\n- Thanks for mentioning this. There is a typo and $V_{h+1}$ should be $V$. We express the lemma for a general $V:\\mathcal{S}\\rightarrow [0,H]$. This result is also used in [10]. We will add a proof (e.g., see Lemma 3 in Yeh et al., AISTATS'23 for a proof). \n\nS. Y. Yeh,  F. Chang, C. Yueh, P. Wu, A. Bernacchia, S. Vakili, \"Sample Complexity of Kernel-Based Q-Learning\", AISTATS 2023. \n\n- We believe the notation is consistent and correct. The episode index $t$ is specified in the notation $Z_h^t$ defined in Line 230. \n\n- Yes, it is the total running time of Algorithm 1. At each episode $t$ and each step $h$, the computation of the kernel ridge regression statistics in each hypercube has a cost of $O(N_c^3+|A_c|N_c^2)$ where $|A_c|$ is the number of actions in the hypercube and $N_c$ is the number of previous observations in the hypercube. Summing up over all hypercubes, we bound the computational complexity with $O(t^3+|\\mathcal{A}|t^2)$, where $|\\mathcal{A}|$ is the total number of actions. This bound is obtained using the simple arithmetic that the cube of the sum of natural numbers is larger than the sum of their cubes. Summing up over steps and episodes, we arrive at the overall runtime complexity of $O(HT^4+H\\mathcal{A}T^3)$. This calculation is similar to [14], and analogous to [14], we expect an improved runtime for $\\pi$-KRVI in practice due to inequalities used in this calculation. We will add further details and clarification on this calculation following your comment. \n\n*Minor comments*\n\n- Kernel ridge regression and Gaussian process (GP) regression lead to essentially the same calculation for the prediction and uncertainty estimate based on data, but from different Bayesian and frequentist perspectives, respectively. The equivalence between these two methods and an interpretation of the uncertainty estimate within kernel ridge regression framework are discussed in detail in Chapter 3 of \"Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences\", M Kanagawa, P Hennig, D Sejdinovic, and B K Sriperumbudur. We find the terminology of kernel ridge regression better suited for our case, similar to [10], as the use of GP terminology (when a *surrogate* GP is employed for modeling the target function) may incorrectly imply that the target function is a sample from a GP. We will further clarify this point and cite Kanagawa et al. as a reference. \n\n- Roughly speaking, information gain represents the effective dimension of the kernel. That is to say, while typical kernels have an infinite-dimensional feature space, only a limited number of features have a significant effect on the regression with a finite dataset. This represents the effective dimension that is the same as information gain up to a log factor. This quantity appears in the confidence intervals for kernel-based models as shown in the results on vector valued self-normalized martingale inequalities and their extension to Hilbert spaces [17,34,42]. We will add this explanation to the final version of the paper. \n\n- The pseudocode of $\\pi$-KRVI is provided in Appendix A in the submitted version of the paper. Due to space limitations, we have placed it in the appendix. However, in the final version of the paper, with the availability of an extra page, we will include the pseudocode in the main body of the paper.\n\n- Thanks for pointing out the typo. We will correct it. "}, {"review_id": "JtYjJyPGu6", "reviewer": "Reviewer_o5D2", "summary": "This work studies RL with kernel function approximation, specifically where it is assumed that the transition dynamics and reward function live in some RKHS. While there has been some work on RL with kernel function approximation, existing work provides bounds which are suboptimal. This work seeks to tighten these bounds, and ultimately obtains a bound scaling as $O(\\sqrt{\\Gamma(T) T})$ where $\\Gamma(T)$ is the maximum information gain, matching the lower bound in certain settings of the bandit case. Their proposed algorithm is a variant of optimistic LSVI.", "questions": "Please provide further clarification on the instantiation of the results to linear bandits/MDPs (see comment above). ", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "1. The setting of kernel RL has not been studied as thoroughly as some areas of RL, and optimal bounds do not exist. This work takes a step in obtaining optimal regret, tightening the best-known existing bounds, and obtaining optimal regret in certain special cases (some bandit instances). However, I believe the stated result is incorrect—see below.", "weaknesses": "1. I do not believe the stated result is correct. In the setting of linear bandits/linear MDPs/linear mixture MDPs, the information gain is bounded as $\\Gamma_{k,\\lambda}(T) \\le O(d \\log T)$, which would translate to a regret guarantee scaling as $O(\\sqrt{d T})$. However, there are well-known lower bounds for these settings which scale as $\\Omega(d \\sqrt{T})$ (see e.g. [1] and [2]). Thus, the bound stated in this paper is better than the lower bound by a factor of $\\sqrt{d}$, which is impossible.\n\nThe following are less significant issues, but are also important to address:\n\n2. There is a vast body of literature on RL beyond tabular and linear function approximation which is not referenced or discussed. See references [3-6] below for a start, and the works cited therein. This literature should be cited and discussed.\n3. To make the results concrete, it would be helpful to instantiate Theorem 2 in the setting of tabular and linear MDPs.\n4. The result is only provably optimal in the setting of bandits with Matern kernels. However, this paper considers deterministic rewards, so it doesn’t actually capture the bandit setting and as such does not handle the setting for the stated lower bound. It’s difficult, then, to make the claim that this result is optimal in any setting. I would suggest modifying the setting to allow for noisy rewards, or showing that there is a reduction from the current setting to the bandit setting (by encoding reward randomness in the transitions).\n5. In addition, it would greatly strengthen the paper to show a lower bound for kernelized RL.\n6. It was not clear to me what the $\\eta$ parameter corresponded to or how it was defined. This should be clarified. \n7. A reference or proof should be given for Lemma 1. \n\n[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. \"Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.\" Conference on Learning Theory. PMLR, 2021.\n\n[2] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.\n\n[3] Du, Simon, et al. \"Bilinear classes: A structural framework for provable generalization in rl.\" International Conference on Machine Learning. PMLR, 2021.\n\n[4] Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. \"Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.\" Advances in neural information processing systems 34 (2021): 13406-13418.\n\n[5] Foster, Dylan J., et al. \"The statistical complexity of interactive decision making.\" arXiv preprint arXiv:2112.13487 (2021).\n\n[6] Zhong, Han, et al. \"A posterior sampling framework for interactive decision making.\" arXiv preprint arXiv:2211.01962 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and providing helpful comments. We have addressed your questions below and hope that it will positively affect your evaluation of the paper. We would also like to highlight that we firmly disagree that our results contradict the lower bounds for linear case, as clarified below. We welcome further discussions if required. \n\n1. Our results do not contradict the lower bounds for linear case, as mentioned in the review. Several NeurIPS, AISTATS and ICML published works on kernel bandits, including [20,21,40], report $\\mathcal{O}(\\sqrt{\\Gamma(T) T})$ regret bounds with $\\Gamma(T)$ as the maximum information gain. The reasoning in the review would challenge all such results, which is not correct. The $\\mathcal{O}(\\sqrt{\\Gamma(T) T})$ regret bounds match the lower bounds given in [19] for kernel-based bandits with Matérn kernel. The reasoning in the review seem to suggest that $\\mathcal{O}(\\Gamma(T)\\sqrt{ T})$ should be the best achievable regret bounds in kernel bandits/RL. This, however, is undesirable as it may be trivial (superliner). Also see [18] for a technical discussion on the challenges in desining algorithms obtaining $\\mathcal{O}(\\sqrt{\\Gamma(T) T})$ regret bounds.  This comment from the reviewer further emphasizes the significance of our results and our contribution to the literature. \n\nThe alleged contradiction between the $\\mathcal{O}(\\sqrt{\\Gamma(T) T})$ upper bounds and the $\\Omega(d\\sqrt{T})$ lower bound in the linear case arises from an oversight. The upper bound $\\mathcal{O}(\\sqrt{\\Gamma(T) T})$ is more explicitely  $\\mathcal{O}(\\sqrt{d\\Gamma(T) T})$, with an $\\sqrt{d}$ factor hidden in the $\\mathcal{O}$ notation. When applied to linear case, we recover $\\mathcal{O}(d\\sqrt{ T})$ regret as expected. In kernel settings, $d$ and $\\Gamma(T)$ represent different notions of dimension: $d$ is dimension of the input space, while $\\Gamma(T)$ , roughly speaking, represents the effective dimension of the kernel. Although they coincide in the linear case, in general kernel-based settings, $\\Gamma(T)$, which grows with $T$, is the dominating term. Hence, it is customary to omit the $d$ terms in the expression of regret bounds in kernel-based bandit and RL literature, e.g., [10, 16, 18, 20, 21, 40]. See a similar discussion in the paragraph next to last in [18]. We will add the $d$ term in our final expression of regret bound and explain this point in the paper, also commenting on the linear case. \n\nWe hope this clarification addresses the concern. We welcome further discussion and suggest referring to [18, 20] for a detailed technical exploration of this intricate issue.\n\n2. We acknowledge the extensive RL literature. We have cited crucial related works, including [10] and references therein, as well as relevant literature on bandits. We value the reviewer's recommendations and will incorporate the suggested references, discussing their relevance and contributions.\n\n3. In the tabular setting, the regret bound scales with the cardinality of state-action space. Thus, when the cardinality of state action space is very large, we obtain tighter regret bounds. Our regret bounds remain the same for a finite state-action space. For the linear model, please see response to question 1.  \n\n4. Thanks for mentioning this point. Even with deterministic rewards, the observations of target function are noisy due to the random transition to the next step. While we agree that noisy rewards makes the problem more general and aid in comparisons with noisy bandits, they will not effectively change the results in general. Hence, deterministic rewards are often assumed for simplicity, as seen in [10], without loss of generality. Reference [10] also compares the results with the noisy bandit setting. We value your feedback and will incorporate this discussion in the final version.\n\n5. Having a general lower bound that incorporates the episode length $H$ seems a significantly challenging problem, which is beyond the scope of this paper. \n\n6. The introduction of the parameter $\\eta$ is a technical formality for the correctness of the results, as also given in [10]. In some works, $\\eta$ is simply assumed to be zero by assuming the Mercer eigenfeatures are uniformly bounded. This, however, may not hold in general as Mercer eigenfeatures depend on the shape of the domain. We introduce $\\eta$ such that $\\sigma_m^{\\eta}\\phi_m$ are uniformly bounded. This uniform boundedness is used in the bounds on maximum information gain and function calss covering number. The uniform boundedness of $\\sigma_m^{\\eta}\\phi_m$ holds for regular domains such as hyperspheres and hypercubes with typical kernels such as Matérn [10].\n\n7. This result is also used in [10]. Following your comment, we will add a proof (e.g., proof of Lemma 3 in Yeh et al., AISTATS'23). \n\nS. Y. Yeh, F. Chang, C. Yueh, P. Wu, A. Bernacchia, S. Vakili, \"Sample Complexity of Kernel-Based Q-Learning\", AISTATS 2023.\n"}]

Author rebuttal:

Meta-review: This paper provides novel regret bounds for RL under the assumption that the action-value functions are members of an RKHS with a known kernel. This is a well-motivated problem formulation and the authors' results and techniques are sound. The reviewers are, for the most part, supportive of accepting this paper. I support this recommendation, but strongly suggest that the authors incorporate some important writing-oriented suggestions made by the reviewers, notably:
- clarify technical novelty of the approach over the related paper [10].
- make explicit all dependences on the data dimension d and clarify how these results recover the known results for linear function approximation.
Decision: Accept (poster)