Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm
Authors: Sattar Vakili
Julia Olkhovskaya
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement learning
infinite horizon average reward setting
no-regret algorithm
kernel-based model
Primary area: reinforcement_learning
TL;DR: We propose an optimisitc kernel-based RL algorithm for the infinite horizon average reward setting and prove no-regret performance guarantees.

Abstract: Reinforcement Learning (RL) utilizing kernel ridge regression to predict the expected value function represents a powerful method with great representational capacity. This setting is a highly versatile framework amenable to analytical results. We consider kernel-based function approximation for RL in the infinite horizon average reward setting, also referred to as the undiscounted setting. We propose an *optimistic* algorithm, similar to acquisition function based algorithms in the special case of bandits. We establish novel *no-regret* performance guarantees for our algorithm, under kernel-based modelling assumptions. Additionally, we derive a novel confidence interval for the kernel-based prediction of the expected value function, applicable across various RL problems.

Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm
Sattar Vakili MediaTek Research sattar. wwt.::aiwww.rrrrrrrrrr..coooo com
Julia Olkhovskaya TU Delft
julia. hriiaoolloooskky@gaaa..ooo
Abstract
Reinforcement learning utilizing kernel ridge regression to predict the expected value function represents a powerful method with great representational capac- ity. This setting is highly versatile framework amenable to analytical results. We consider kernel-based function approximation for RL in the infinite horizon average reward setting, also referred to as the undiscounted setting. We propose an optimistic algorithm, similar to acquisition function based algorithms the special case of bandits. We establish novel no-regret performance guarantees for our algorithm, under kernel-basee modelling assumptions. Additionally, we derive novel confidence interval for the kernel-based prediction of the expected value function, applicable across various RL problems.
Introduction
Reinforcement learning (RL) has demonstrated substantial practical success across variety of application domains, including gaming (Silver al., 2016; Lee et al., 2018; Vinyals al., 2019), autonomous driving (Kahn et al., 2017), microchip design (Mirhoseini et al., 2021), robot control (Kalashnikov al., 2018), and algorithmic search (Fawzi al., 2022). This empirical success has prompted deeper investigations into the analytical understanding of RL, especially in complex environments. Over the past decade, significant advances have been made in establishing theoretically grounded algorithms for various settings. In this work, we focus on the infinite horizon average reward setting, also known as the undiscounted setting (Wei al., 2020, 2021). This setting is particularly well-suited for applications that involve continuing operations not divided into episodes such as load balancing and stock market operations. In contrast to the episodic setting (Jin et al., 2020) and the discounted setting (Zhou et al., 2021), theoretical understanding of RL algorithms is relatively limited for the undiscounted setting. We develop a computationally efficient algorithm and establish its theoretical performance guarantees in the undiscounted case.
There is natural progression in the complexity RL models corresponding the structural complexity of the Markov Decision Process (MDP). This progression ranges from tabular models to linear, kessel- and deep learning- -based models. The kernel-based structure is an extension of linear structure to an infiite-dimmnsional linear model in the feature space of a positive definite kernel, resulting in highly versatile model with great representational capacity for nonlinear functions. In addition, the closed-form expressions for the prediction and the uncertainty estimate in kernel-based models allow the development of algorithms based on nonlinear function approximation that are amenable to theoretical analysis. Kernel-based models also serve understanding the deep learning- based models (see, e.g., Yang et al., 2020) based on the Neural Tangent (NT) kernel approach (Jacot et al., 2018).
intermediate step towards
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The anfinit-hhorizon average-rewardd setting has been extensively explored under the tabular struc- ture (Auer et al., 2008; Wei et al., 2020; Zhang and Xie, 2023). Under the performance measure of regret, defined as the difference in the total reward achieved by a learning algorithm over 'T' steps and that of the optimal stationary policy, performance bounds of (Sp (T) have been established (see, e.g., Zhang et al., 2020), where S and A represent the state and action spaces, respectively, and the regret grows polynomial with their sizes. It is assumed for these results that the MDP is weakly communicating, condition necessary for achieving sublinear regret (Bartlett and Tewari, 2009). Averaged over T steps, the regret diminishes as T increases, thereby offering what is known as a no-regret performance guarantee. The applicability of the tabular setting is limited, as many real-world problems feature very large or potentially infinite state-action spaces. Consequently, recent literature has explored the use of function approximation in RL, particularly through linear models (Abbasi-Yadkori et al., 2019a,b; Hao et al., 2021; Wei et al., 2021). This approach represents the value function or the transition model via a linear transformation applied to a predefined feature mapping. In the linear setting, regret bounds of ((dT)) have been established (Wei et al., 2021), where d represents the ambient dimension of the linear feature map. Kernel-based models can be considered as linear models in the feature space of the kernel. That, however, is often infinite dimensional
= 0o). As such, the results with linear models do not translate to the kernel-basee settings, necessitating novel analytical techniques. Also, for a discussion on further limitations of the linear models, see Lee and Oh (2023).
In this work, we propose the first RL algorithm in the infinite horizon average reward setting with non-linear function approximation using kemel-riige regression. This is one of the most general models that lends well to theoretical analysis. Our algorithm, referred to as Kernel-based Upper Confidence Bound (KUCB-RL), utilizes kernel ridge regression to build predictor and uncertainty estimates for the expected value function. Inspired by the principle of optimism in the face of uncertainty and equipped with these statistics, KUCB-RL builds an upper confidence bound on the state-action value function over a future window of w steps. This bound serves as a proxy qt, at each step t, for the state-action value function over this future window. At each step t with the current state St, the action is selected greedily with respect to this proxy: 0r arg max A qe (St, a). This approach resembles the acquisition function based algorithms such as GP-UCB and GP-TS, using Upper Confidence Bound and Thompson sampling, respectively, in the context of kernel-based bandits, also known as Bayesian optimization (Srinivas al., 2010; Chowdhury and Gopalan, 2017). Kernel-based bandit setting corresponds to the degenerate case of [S] = 1. In comparison, in the RL setting, the action is selected based on the current state, and the reward depends on both the state and the action. A kesnel-based model is used to provide predictions for the expected value function, which varies due to the Markovian nature of the temporal dynamics. This makes the RL problem significantly more challenging than the bandit problem where the predictions are derived for fixed reward function. To address this latter challenge, we derive a novel kernel-based confidence interval that is applicable across RL problems.
1.1 Contributions
To summarize, contributions are as follows. We develop kernel based optimistic al- gorithm for the infinite horizon average reward setting, referred to as KUCB-RL. We estab- lish no-regret guarantees for the proposed learning algorithm, which is the first for this set- ting to the best of our knowledge. Specifically, in Theorem 3, we prove a regret bound of o O (w+ " vp (>(T::)) + tog())) VPTT(T;p) p) + + (T: wr; p)). at a 1 5 con- fidence level, where p is the parameter of kernel ridge regression and ((T; p) is the maximum information gain, a kernel specific complexity term (see Section 2). This regret bound translates
to Ō (d in the special case of linear model, recovering the best existing results (Wei et al.,
2021) in dependence on T, and improving by a factor of d'à When applied to very smooth kernels with exponential eigendecay such as the Squared Exponential (SE) kernel, we obtain a regret of Ö(r?). with the notation Ô hiding logarithmic factors. For one of the most general cases, the kernels with polynomial eigendecay with parameter p > 1 (See Definition 1), that includes, for example, the Matérn family and NT kernels, we show that our regret bound translates to Ö(T 3) which constitutes a no-regret guarantee. To highlight the significance of this result, we point out that no-regret guarantees for GP-UCB in the degenerate case of bandits were established only recently

---

in Whitehouse et al. (2024), while the initial studies of GP-UCB (as well as GP-TS) (Srinivas et al., 2010; Chowdhury and Gopalan, 2017) did not provide no-regret guarantees for the case of polynomial eigendecay. As part of our analysis, in Theorem I, we develop a novel confidence interval applicable across kernel-based RI. problems that contributes to the eventual improved results.
1.2 Related Work
The vast RL literature can be categorized across various dimensions. In addition to the average reward, episodic, and discounted settings, as well as tabular, linear, and kerne-bbased structures mentioned above, other notable distinctions among settings include model- versus model-free approaches, and offline versus online versus settings where the existence of a generative model is assumed (allowing the learning algorithm to sample the state-action of its choice each step, rather than following the Markovian trajectory). Covering the entire breadth of RL literature is challenging. Here, we will focus on highlighting and providing comparisons with the most closely related works, particularly in terms of their setting and structure.
The baaeel MDP structure has been considered in several recent works under the episodic setting (Yang et al., 2020; Vakili and Olkhovskaya, 2023; Chowdhury and Oliveira, 2023; Domingues et 2021; Vakili, 2024). The regret bound proven in Yang al. (2020) for the episodic setting applies only to very smooth kernels such as SE kernel. Vakili and Olkhovskaya (2023) addressed this limitation by extending the results to Matérn and NT' families of the kernels, alheit with sophisticated algorithm that actively partitions the state-action domain into possibly many subdomains, using only the observations within each subdomain to obtain kernel-based prediction and uncertainty estimates. Their work is also based on particular assumption that relates the kernel eigenvalues to the size of the domain. The work of Chowdhury and Oliveira (2023) is most closely related ours in terms of kemnel-related assumptions. Specifically, our Assumption 4 is identical to Assumption 1 of Chowdhury and Oliveira (2023). They establish regret bound of O (HN p) V /N) for the episodic MDP setting, where N is the number of episodes, ((N: p) is the maximum information gain, a kernel-related complexity term, H is the episode length and the value of p is a fixed constant close to 1. However, their regret bounds do not apply to general families of kernels, such as those with polynomially decaying eigenvalues (see Section 2.2 for the definition) including Matérn and NT kernels, as for this family of kernels y(N: p) possibly grows faster than vN. As result, no-regret guarantee cannot be established in many cases of interest. In comparison, the infinite horizon setting considered in this work is more challenging than the episodic setting as evident when comparing these settings with linear modeling. For this more challenging setting, we establish no-regret guarantees. A key element of our improved results is the novel confidence interval we utilize in our analysis (Theorem 1). This result is general and can be used across RL problems, for example, improving the results of Chowdhury and Oliveira (2023) well.
In the tabular case, a lower bound of Ω ((v /VV/D))) A()) on regret was established in Auer et al. (2008) in the hiriite- average-reward setting, where D is the diameter of the MDP. For ergodic MDPs, Wei et al. (2020) shows a regret bound of ((VEL [S]|)[)), where fmix is the mixing time of an ergodic MDP. Furthermore, under the broader assumption of weakly communicating MDPs, which is necessary for low regret (Bartlett and Tewari, 2012), the best existing regret bound of model-free algorithms is
achieved by the recent work of Zhang and Xie (2023). Several works have studied linear function approximation in the infinite horizon average reward setting under strong assumptions of uniformly mixing and uniformly excited feature conditions (Abbasi- et al., 2019a,b; Hao et al., 2021). Notably, Hao et al. (2021) achieved a regret bound
of δ { V/mm under the linear bias function assumption, where a is the smallest eigenvalue of policy-weid weighted covariance matrix. Under the much less restrictive setting of Bellman optimality equation assumption (Assumption 1) for linear MDP, Wei et al. (2021) provides an algorithm with regret guarantee of ((dT)3/44) We also consider our kernel- based approach under this general assumption on MDP. Furthermore, for examples of infeasible algorithms in the literature, see Wei et al. (2021), Algorithm 1. There also exists separate model- approach to the problem where the transition probability distribution (model) learned and used for planning, usually requiring high memory and computational complexity and utilizing substantially different techniques and assumptions. While this approach is studied under tabular settings (Bartlett and Tewari, 2009; Auer et al., 2008) and linear settings (Wu et al., 2022), it is not clear whether model-based approaches can
3

---

be feasibly constructed in the kernel-based setting, due to the space complexity of a kernel- based model.
Our work is also related to the simpler problem of kernelized bandits (Srinivas et al., 2010; Chowdhury and Gopalan, 2017; Vakili et al., 2021b; Li and Scarlett, 2022; Salgia et al., 2021). Our construction of the confidence interval for the RL setting has been inspired by the previous work on bandits, utilizing novel analysis introduced in Whitehouse al. (2024). Bandit settings can be considered degenerate case of the RL framework with | 1. In comparison, the temporal dependencies of MDP introduce substantial challenges, and the confidence intervals used in the bandit setting cannot be directly applied.
We summarize the most closely related work with a focus model-free feasible algorithms in Table 1. We present the existing regret bounds under various assumptions on MDP and its structure (tabular, linear, kernel-based.. The assumptions include weakly communicating MDP (See Puterman, 1990, Section 8.3.1). Bellman optimality equation (our Assumption 1), and uniform mixing assumption (see Wei et al., 2021, Assumption 3). For a formal definition of linear MDP, see Wei al. (2021), Assumption 2, and for the linear bias function case, see Wei et al. (2021), I), Assumption 4.
Table Summary the existing regret bounds in the infinite horizon average reward setting under various cases with respect to MDP structure (tabular, linear, kernel based) and assumptions.
Algorithm
Regret
MDP Assumption
Structure
UCB-AVG (Zhang and Xie, 2023)
((SMAATT)))))
Weakly Communicating
Tabular
OLSVLFH (Wei al., 2021)
Bellman Optimality Eq.
Linear
MDP-Exp2 (Wei et al., 2021)
mix ((TTT)
Uniform Mixing
Linear Bias function
KUCB-RL (Algorithm I)
Bellman Optimality Eq.
Linear
KUCB-RL (Algorithm I)
T
Bellman Optimality Eq.
Kernel-based (expomential)
KUCB-RL (Algorithm I)
Spen T 4pp4
Bellman Optimality Eq.
Kernel-based (polynomial)
Problem Formulation
In this section, overview the background on infinite horizon average reward (undiscounted) MDPs and kernel based modelling.
2.1 Infinite Horizon Average Reward MDP
An undiscounted MDP is described by the tuple (8, A,r, P) where S is state space with possibly infinite number of clements, A a finite action set, r x A > [0, 1] is the reward function, and P(-|s, a) is the unknown transition probability distribution over S of the next state when action is selected at state s. Throughout the paper we use the notation (s, a) for the state-action pairs, and Z = S A.
The learner interacts with the MDP through T steps, starting from an arbitrary initial state s1 E S. At each step t, the learner observes state and takes an action resulting in reward r(s,, The next state 8141 is revealed as sample drawn from the transition probability distribution: 8141 P(-(st,a.).
The goal of the learner is to compete against any fixed stationary policy. A stationary policy S 5 is possibly random mapping from the states to actions. The long-term average reward of stationary policy æ,, starting from state s S, defined as:
T Σ ((s), at)
J (s) lim inf L
81 s. Vt 2 1. = x(8)), 8111 P(-1s
T-300 T
We assume that the MDP belongs to the broad class of MDPs where the following form of the Bellman optimality equation holds:
Assumption 1 (Bellman optimality equation). There exists J E R and bounded measurable
functions v² S - R and q¹ S A - R. such that the following conditions are satisfied for all

---

states E S and actions A: r(x,
J +" r ((laa) (0'))
(²(s) max q (s, a). acA
(1)
This assumption was also used for the linear MDP case in Wei et al. (2021). By applying the Bellman optimality equation, it can be shown that policy π (s)s = arg max 9* (s, (s,a), which deterministically selects actions that maximize q in the current state, is the optimal policy nt arg max,, JR, with J (s) = J", for all (Wei et al., 2021).
For the finite state setting, Assumption follows from the weakly communicating MDP assump- tion (see, e.g., Puterman, 1990, Chapter 9). Assumption also holds under several other common conditions (Hemáánez--Lerma (2012). Section 3.3).
The learner's performance measured by regret, which is defined as the difference in total reward between the learnrr and the optimal stationary policy. Specifically,
T
R(T) =
(2)
1=1
We emphasize that under Assumption 1, for any initial state $1 E S, JF J", that is reflected in our regret definition. For any value function v S + R, throughout the paper, we use the notation
[Pu](=) Eg ((ss)()))((s)
for the expected value function of the next state.
2.2 Kernel-Basee -aneed Models and the RKHS
Consider a positive definite kernel k. 2 x 2 + RR Let H4 be the reproducing kernel Hilbert space (RKHS) induced by k. where Hg contains family of functions defined on Let ( He. x Hs + R and || |l He - R denote the inner product and the norm of Ha. respectively. The reproducing property implies that for all ʃ Ha. and z E Z, (f, k(, 2)) Rt. f(z). Mercer theorem implies that & can be represented using possibly infinite dimensional feature map:
k(z,z')= Σ
(2) (2')
where Am 0, and VAm H4 form orthonormal basis of Hy. In particular, any f E H4 can be represented using this basis and weights Wm. E R as
Wm AmiPm
m=1
where Il
Em w A formal statement and the details are provided in Appendix 8. We refer Am and Pm as (Mercer) eigenvalues and eigenfunctions of kernel k, respectively.
2.3 Kernel-Based Prediction
Kernel-based models provide powerful predictors and uncertainty estimators which can be leveraged guide the RL algorithm. In particular, consider fixed unknown function f He. Assume at x vector of noisy observations y: = [y; = f(z) + e at observation points { is provided, where e; are independent zero mean noise terms. Kernel ridge regression provides the following predictor and uncertainty estimate, respectively (see, e.g., Schölkopf et al., 2002),
f((z)) = k, (=) pT) pT)-1 - d3(c) = k(2,2) k (=) (
(4)
where kz)=) = [k(z, 21), .... k(2, =T is a 1 vector of the kernel values between and observa- tions, K, [k(2,, 25)] the 1 / kernel matrix, 7 is the identity matrix appropriately sized to match K;, and p > 0 is a free regularization parameter.
5

---

Confidence bounds of the form f()) (2) are established, for a confidence interval width multiplier (() at a confidence level 1 6, which depends on the assumptions on the setting and the noise. We will establish a such confidence interval specific to the RI. setting, in Theorem 1, and utilize in our regret analysis.
2.4 Kernel-Rased Modelling in RL
In our RL setting, we use kernel-based model to predict the expected value function. In particular, for a given transition probability distribution P() and value function v - R, we define [Pu] and use past observations to form predictions and uncertainty estimates for as detailed in the following section. The value functions vary due to the Markovian nature of the temporal dynamics. To effectively use the confidence intervals established by the kemnl--based models on f. we require the following assumption.
Assumption 2. We assume P(s E HK for some positive definite kernel k. and (| S 1 for all s' E S.
2.5 Eigendecay and Information Gain
Our regret bounds are presented terms of maximum information gain which is kernel-specific complexity term. Specifically, for a kernel k and sets of observation points {24 H= we define the maximum information gain 7(: p) as follows
Kg
(t: = sup
log det T+
(= C2
where p >> O, and K; is the kernel matrix defined in Section 2.3. Several works have established upper bounds on (t: p). In the special case of d-dimensional linear kernel, we have (t: p) O(d ltg(t)). For kernels with exponential eigendecay, including SE, r(t p) = O(polylog(t) (Srinivas et al., 2010: Vakili et al., 2021b). For kernels with polynomial eigendecay, which represent crucial case due to challenges in establishing no-regret guarantees in RL and bandits, and include kernels of both practical and theoretical interest such the Matérn family and NT kernels, first provide the definition below and then the bound on 7/-
Definition 1. A kernel k is said to have a p-polynomial eigendecay im 2 1, Am I Cm P, for some p 1, C' > 0 where Nm are the Mercer eigenvalues of the kernel in decreasing order.
For kernels with p-polynomial eigendecay, we have (Vakili et al., 2021b, Corollary 1):
(t:pp) - (t:p)= (()) $ log 1+ t :))) 1-#
(1+
)
3 KUCB-RL Algorithm
In this section, introduce algorithm, Kernel-based Upper Confidence Bound for Reinforce- ment Learning (KUCB-RL). The algorithm's 's structure is similar to acquisition- kernel bandit algorithms such as GP-UCB (Srinivas et al., 2010), where each action chosen as the maximizer of an acquisition function. We construct an optimistic proxy for the state-action value function. At each step given the current state St, the action a, selected as the maximizer of qe (se, a) over a. This proxy de is derived using past observations of transitions, employing kernel ridge regression to provide prediction and uncertainty estimate for the state-action action value function over future window of size w E N. The proxy is established as an upper confidence bound, following the principle of optimism the face of uncertainty. The value functions are computed in batches of w steps, and the derived policies are unrolled over the subsequent steps. The details are presented next.
We define fixed window size, w E N, which represents the future interval that the algorithm will consider. For a given to where (to mod w) = 0, including to O, we initialize Uta+ = Vs E S, reflecting the algorithm's consideration of the reward within this future window of size w. Subsequently, we recursively obtain proxies and for all steps & E (t to + < < to + w). Let fo denote [Po fo represent the kereel ridge predictor of [Pu+t1], and be its uncertainty

---

Algorithm Kernel-based Upper Confidence Bound for Reinforcement Learning (KUCB-RL)
Require: Regularization parameter p. window size w, confidence interval width multiplier B, confi- dence level 1 - 6, r.
1: for = 0, 1, ... do
2:
if (L mod w) = 0 then
3:
Let u++ 0: for = 1,2, ,0 do
4:
5:
Compute a++++1- and Ut+w+1-h using equations (6) and (7).
end for 7: end if
6:
8: Select a,
arg max de a);
Observe 8++1 ~ P(-|s,, a.) and receive r(st, az).
9: end for
estimator. The predictor and the uncertainty estimator are derived using the data set Deo, which contains observations of past transitions up to to. We use the notation D, = {(S}. aj. sj+1) hise for the past transitions, and also define Vt+1,ta = [12+1(52), Ut41 (s3).... Vt+ (st++1]] for the values of the proxy value function at the history of state observations. We then have
f((=) (=) (Kro + +pl) 1e-1,501
==(=)= = k(z, - (z) (Kto + pp)) (z), +xo))=kto=z),
(5)
where ke(=) [k(2, 21), k(z, ,2), ... k(z, = denotes the vector of kernel values between and (z) = (sy, js)))ss in the history of observations, and Kr [k[z,, 2y)li denotes the kernel matrix.
Equipped with the kernel ridge predictor and uncertainty estimator, we define as an upper confi- dence bound for fú, as follows:
(2) [1 (f(:) + + ((O)))) V2 E Z,
(6)
where 1 represents confidence level, and B(5) is confidence interval width multiplier, the specific value of which is given in Theorem 3. The notation [[ is used for projection on Ja, 6] interval. This step is natural since with the assumption r 2 > [0, 1] the value over a window of size can not be more than w. We also define
(s))
max (1 a), Vs S.
aEA
By iteratively updating from f to to to + 1, we compute the values of qe and 1 for all from to + to to + w. Then, we unroll the learned policy over the subsequent w steps, as the greedy policy with respect to q::
arg max (i($t, aeA
(8)
pseudocode provided in Algorithm
Computational Complexity. KUCB-RL enjoys a polynomial computational complexity of O T ) where the bottleneck is the matrix inversion step in (5) in kernel ridge regression every steps. This not unique to our work and is common across kernel-based supervised learning, bandit, and RL literature. Luckily, sparse approximation methods such Sparse Variational Gaussian Processes (SVGP) or the Nyström method significantly reduce the computational complexity of matrix inversion step (to as low as linear in some cases), while maintaining the kernel-based confidence intervals and, consequently, the eventual rates (sec, c.g., Vakili et al., 2022, and references therein). These results are, however, generally applicable and not specific to our problem.
4 Regret Bounds for KUCB-RL
In this section, we provide analytical results on the performance of KUCB-RL. We prove the first sublinear regret bounds in undiscounted RI setting under general assumptions based on kernel-based modelling. We first derive novel confidence interval that broadly applicable to the kernel-based RL problems. We then utilize this result to establish bounds on the regret of KUCB-RL.
7

---

4.1 Confidence Intervals for Kernel Based RL
The analysis of our algorithm utilizes confidence intervals of the form lf((z) ( f((=)1 (())
where ft = [Por] denotes the expected value of a value function Vt, and ft and or represent the kernel ridge predictor and the uncertainty estimate of ft. Here, (()) represents the width multiplier for the confidence interval at a 1 8 confidence level. Similar confidence intervals are established in kernel ridge regression for fixed function f in the RKHS of specified kernel i (see, e.g.. Abbasi- Yadkori, 2013; Srinivas et al., 2010; Chowdhury and Gopalan, 2017: Vakili et al., 202 la; Whitehouse et al., 2024). In the RL context, specific considerations are required as both f. [Pu,] and the observation noise depend on the value function ey that varies due to the Markovian nature of the temporal dynamics. We note that in this setting, for given value function e : S + IR, the observation noise is captured by (($+1)) - -PPu] [P,, ax).. A possible approach involves deriving confidence intervals that apply to class V of value functions. Such results appear in some of the existing work (Chowdhury and Oliveira, 2023; Vakili and Olkhovskaya, 2023). The result most closely related to our is Chowdhury and Oliveira (2023), which derives its confidence interval under the exact same kernel related assumptions as our work, but for the episodic MDP setting. With the same assumptions, the confidence interval that we establish is different from the one in Chowdhury and Oliveira (2023). In particular, their confidence interval is applicable to specific value of kernel ridge regression parameter p. constrained by their proof techniques. Inspired by Whitehouse et al. (2024), which established confidence interval for kernel ridge regression (not within the RL context) but allowed for a judicious selection of p. we prove a new confidence interval suitable for the RI. setting that allows tuning parameter p. As result, we obtain the first improved no-regret algorithms in this setting.
Theorem 1 (Confidence Bound). Consider u : S - TR conditional probability distribution P(s|z), 8 E S, 2 E 2, and two positive definite kernels k x 2 + TR. and k :S x S + R2 where 2 S x A is compact subset of Rdd Let = [Pu] and assume ||ll|y S C., u(s) Sw, V/s E S, and [l I CG, for some C., W. Cf > 0. A dataset {2,,,,)) C (Z x S) is provided such that s² ~ P(-12)). Let Am m 1,2.... denote the Mercer's 's eigenvalues of k in a decreasing order and tim denote the corresponding eigenfunctions, with 1mm. m/mxx for some thmax O.
Let fn and on be the kernel ridge predictor and the uncertainty estimate of using the observations:
fn(=) 1 = (p) + Kn))"on
'.)- Un: o²(()) = k(2, z) - (=) + Kn) kmn) ki((),
where on = [u(s{), -.,6,),-,,,,,,,,, [T is the vector of observations.
For all E Z and v
|| S Cv, the following holds, with probability at least 1 6,
15(z) (ic)-ff(4h fa())))+ ((8)om()),
with 3(0) =
1 "(2 2log (VT. der(I + p- p=1kk)) ))
Cy+ Cormax vp
MM Σ 1
20, Vmax
Am
+
dm
vp
m== M+1
We can simplify the presentation of 3 under the following assumption.
Assumption 3. For the kernel K', we assume that for some C1, O2 and > 0, EM Am S C1 and, 2m = M41 Am < C2M for any M E N.
This is mild assumption. For example, p-polynomial eigendecay profile with p 1, which applies to large class of common kernels including SE, Matérn and NT kernels, satisfies this assumption C_ and = p - 1, where C' is the constant specified in Definition 1.
with C = p-1 C2 p-
PC
Remark 2. Under Assumption 3, the expression of B in Theorem 3 can be simplified as
B(6) =o (c,+ ( C.
log( n ( (p:n))
vpV
Remark can be observed by selecting M = [ in the expression of ((6), which provides a straightforward presentation of the confidence interval width multiplier.
8

---

The proof of Theorem 1 involves the Mercer representation of in terms of dmm. The expression of the prediction error [f(=) f.(2)) I is then decomposed into error terms corresponding to each thm- We then partition these terms into the first M elements corresponding to eigenfunctions with the largest M eigenvalues and the rest. For each of the first M eigenfunctions, we obtain high probability bounds using existing confidence intervals from Whitehouse et al. (2024). Summing up over m, and using a bound based uncertainty estimates, we achieve a high probability bound-corresponee corresponding to the second term in the expression of B()). We then bound the remaining m > M elements based on the decay of Mereer bigenvalues-oorreee corresponding to the third term in the expression of (()). A
detailed proof is provided in Appendix 6.
Theorem 1 is presented in a self-contained way. making it broadly applicable across various RL settings. the following section, we apply this theorem within the analysis of the infinite horizon average reward setting to obtain no-regret algorithm. This is the first no-regret algorithm within this setting under general kernel-related assumptions.
4.2 Regret Analysis of KUCB-RL
The weakest assumption regarding value functions is realizabillity, which suggests that the optimal value function v* either belong to the an RKHS or are at least well-approximated by its elements. realizability alone sufficient for provably efficient
In the degenerate case of bandits with [S] algorithms (Srinivas et al., 2010; Chowdhury and Gopalan, 2017; Vakili et al., 202 However, for general MDPs, realizability is inadequate, necessitating stronger assumptions (Jin al., 2020; Wang et al., 2019; Chowdhury and Oliveira, 2023). Building on these works, our main assumption involves a closure property for all value functions within the following class:
W. max { (((s,a) a) + (s, + 8 (o, }}} aEA
V V= + min
where 3 E R and 3 0, 010 < oo, and E an Do x ac matrix operator such that Σ > pl for some > O, and Φ = [01 62. ...]. where om = V Am and Am and pm are the Mercer eigenvalues and eigenfunctions corresponding to kernel & defined on Z x Z. We assume V is subset of the RKHS of a kernel k'' defined on S S.
Assumption 4 (Optimistic Closure). For any e E V, and for some positive constant Co. we have ||l||a S C.. Additionally, for S - [0, w). we assume C. O(w).
This technical assumption is the same as Assumption 1 in Chowdhury and Oliveira (2023). The optimistic closure assumption in the kernel-based setting is strietly weaker than the ones explored in the context of generalized linear function approximation (Wang et al., 2020).
Theorem 3. Consider the undiscounted MDP setting described in Section 2. Run KUCB-RL given in Algorithm I for T steps. Under Assumptions 1, 2, 3, and 4, the regret of KUCB-RL RL, defined in Equation (2), satisfies, with probability at least -
T
T (T) V (T) ( (T:))
(T) O
+
vDV vDV (T::) log
The proof of Theorem 3 utilizes standard methods from the analysis of optimistic algorithms in RL and bandits, such as the elliptical potential lemma, leverages the confidence interval proven in Theorem 1, and also incorporates novel techniques. Algorithm updates the observation set every w steps, requiring us to characterize and bound the effect of this delay in the proof. A straightforward application of the elliptical potential lemma results in loose bounds that do not guarantee no-regret. In Lemma 4, we establish a tight bound on the sum of standard deviations of a sequence of points with delayed updates of the observation sets, contributing to the improved regret bounds. This is independently a useful result in other settings with delayed updates, such as delayed feedback settings (Vakili et al., 2023a; Kuang et al., 2023) or when observations provided in batch (Chowdhury and Gopalan, 2019). The details are provided in Appendix 7.
There is an apparent trade-off in choosing the window size. Intuitively, this trade-off balances the strength of the value function against the strength of the noise. A larger preferred to capture the long-term performance of the policy, but larger w also increases the observation noise affecting

---

the prediction enror in kernel ridge regression. The optimal window size results from an interplay between these two factors, which is reflected in the regret bound.
We next instantiate our regret bounds for some special cases. In the linear case, with a choice of w T and replacing the bound on >(T; we obtain R(T) ( recovering the existing results in their dependence on T and improving by factor of d+, For kernels with exponential eigendecay, with choice of w T and replacing the bound <(T; p), obtain RR() (T We formalize the result with p-polynomial kernels in the following remark as may be of broader interest.
Remark Under the setting of Theorem 3, with a p-polynomial kernel, with the choice of parameters. 2-1 w = T mp+ and p T TTF,, we obtain the following no-regret guarantee R(T) = ÖT Sp
Tp7) Tp-7
In the case of Matérn kernel with smoothness parameter v, where p 1 d' the regret bound translates to RT) O (T [ This also directly extends to NT kernels using the equivalence between the RKHS of Matérn kernels and NT kernels with the appropriate smoothness (Vakili et al., 2023b).
5 Discussion and Limitations
We proposed KUCB-RL in the infinite horizon average reward setting and proved no-regret guarantees with general kernels, including those with polynomial eigendecay such Matém and NT kernels. To highlight the significance of our results, we note that in the case of episodic MDPs, the existing work of (Yang et al., 2020; Chowdhury and Oliveira, 2023) do not provide no-regret guarantees with general kernels. The work of Vakili and Olkhovskaya (2023) utilizes sophisticated domain partitioning techniques and relies with the size of the domain. We achieve improved rates on regret leveraging a confidence interval proven in Theorem 1, which is applicable across various RL problems. We next point out two main limitations of our work.
specific assumption about the scaling of kernel eigenvalues
Regarding optimality, we can juxtapose our results with the (u- lower bounds proven in (Scar- lett et al., 2017), for the degenerate case of bandits with Matérn kernel. Sophisticated algorithms, such as the sup variation of optimistic algorithms and those based on sample or domain partitioning (Valko et al., 2013; Salgia et al., 2021; Li and Scarlett, 2022), achieve this lower bound up to logarithmic factors the case of bandits. However, a no-regret Ö(T
guarantee, though suboptimal, for standard rqquisition-basede algorithms like GP-UCB has been provided only recently (Whitehous
2v422
al., 2024). While we offer the first no-regret ÖT setting of RI,, we cannot determine whether our results are improvable. This remains an area for future investigation.
3x+-dd
guarantee in the much more complex
Although RKHS elements of common kernels can approximate almost all continuous functions on compact subsets of TRd (Srinivas et al., 2010), the optimistic closure assumption is somewhat limiting. A rigorous approach involves relaxing this assumption and finding an RKHS element that serves as an upper confidence bound on function of interest f within the same RKHS. While this method appears to reasonably address the assumption, it is a technically involved problem that invites further contributions from researchers in the field.
References
Y. Yadkori. Online learning for linearly parametrized control problems. 2013.
Y. Abbasi Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Y. Abbasi- Yadkor, P. Bartlett, K. Bhatia, N. Lazic, C. Szepesvari, and G. Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pages 3692-3702 PMLR, 2019a.
Y. Abbasi- Yadkori, N. Lazic, C. Szepesvari, and G. Weisz. Exploration-enhancee politex, arXiv preprint 19oiv 10041.99988 2019b.
10

---

P. Auer, T. Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Bartlett and A. Tewari. Regal: regularization based algorithm for reinforcement learning in weakly communicating mdps. In Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference, pages 35-42. AUAT Press, 2009.
L. Bartlett and A. Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint arXiv: 2012.
D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco. Scaling Gaussian process optimization by evaluating a few unique candidates multiple times. International Conference on Machine Learning, pages 2523-2541. PMLR, 2022.
S. R. Chowdhury and A. Gopalan. On kemeliied multi- bandits. In International Conference on Machine Learning, pages 853. PMLR, 2017.
S. R. Chowdhury and A. Gopalan. On batch bayesian optimization. arXiv preprint arXiv:1911.01033 2019.
S. R. Chowdhury and R. Oliveira. Value function approximations via kernel embeddings for no-regret reinforcement learning. In Asian Conference on Machine Learning, pages 249-264. PMLR, 2023,
A. Christmann and I. Steinwart. Support Vector Machines. Springer New York, NY, 2008.
O. D. Domingues, P. Ménard, M. Pirotta, E. Kaufmaan, and M. Valko. A kernel-based approach to non non- statitottonnry reinforcement learning metric spaces. International Conference on Artificial Intelligence and Statistics, pages 2538-35445 PMLR, 2021.
A. Fawzi, M. Balog, A. Huang, T. Hubert, B. Romera-PPredee Paredes, M. Barekatain, A. Novikov, F. J. R Ruiz, Schritwieser, Swirszez, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-533 2022.
B. Hao, N. Lazic, Y. Abbasi-Yadkorf P. Joulani, and C. Szepesvári. Adaptive approximate policy iteration. International Conference on Artificial Intelligence and Statistics, pages 523-531. PMLR, 2021.
O. Hernández- Lerma. Adaptive Markov control processes, volume 79. Springer Science & Business Media, 2012.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. Advances in neural information processing systems, 31, 2018.
C. Jin, Z. Yang. Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
G. Kahn, A. Villaflor, V. Pong, P. Abbeel, and S. Levine. Uncertainty-aware reinforcement learning for collision avoidance. arXiv preprint arXiv: 182, 2017.
D. Kalashnikov, A. Irpan, P. Pastor, J. Ibarz, A. Herzog, F. Jang, D. Quillen, F. Holly, M. Kalakrishnan, V. Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, pages 6-1-673. PMLR, 2018.
N. L. Kuang. M. Yin, M. Wang, Y.-X. Wang, and Y. Ma. Posterior sampling with delayed feedback for reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 36:6782 6824, 2023.
P. Lalley. Concentration inequalities. Lecture notes, University of Chicago, 2013.
Lee and M.-h. Oh. Demystifying linear mdps and novel dynamics aggregation framework. The Twelfth International Conference on Learning Representations, 2023.
K. Lee, S.-A. Kim, J. Choi, and S.-W. Lee. Deep reinforcement learning in continuous action spaces: case study in the game of simulated curling. International Conference on Machine Learning. pages 2937-2946. PMLR, 2018.

---

Z. Li and J. Scarlett. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics, 2022.
J. Mercer. Functions of positive and negative type, and their connection with the theory of integral equations. Philosephical Transactions of the Royal Society of London. Series Containing Papers of a Mathematical or Physical Character, 209:415-444 1909.
A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, A. Nazi, et al. A graph placement methodology for fast chip design. Nature, 594(7862):
207-212, 2021.
M. L. Puterman. Markov decision processes. Handbooks in operations research and management science, 2:331-434, 1990.
S. Salgia, S. Vakili, and Q. Zhao. domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance. Conference on Neural Information Processing Systems, 34, 2021.
J. Scarlett, I. Bogunovic, and V. Cevher. Lower bounds on regret for noisy gaussian process bandit optimization. In Conference on Learning Theory, pages 1723-1742. PMLR, 2017.
B. Schölkopf, A. J. Smola, F. Bach, et al. Learning with kernels: support vector machines, regular- ization, optimization, and beyond. MIT press, 2002.
D. Silver, A. Huang, J. Maddison, Guez, L. Sifre, G. Van Den Driessche, Schrittiieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In ICML 2010 Proceedings, 27th International Conference on Machine Learning, pages 1015-1022, July 2010.
S. Vakili. Open problem: Order optimal regret bounds for kernel-based reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 5340-5344. PMLR, 2024.
S. Vakili and J. Olkhovskaya. Kernelized reinforcement learning with order optimal regret bounds. Advances in Neural Information Processing Systems, 36, 2023.
S. Vakili, N. Bouziani, S. Jalali, A. Bernacchia, and D.-s. Shiu. Optimal order simple regret for gaussian process bandits. Advances in Neural Information Processing Systems, 34:21202-21215, 2021a.
S. Vakili, K. Khezeli, and V. Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021b.
S. Vakili, J. Scarlett, D.-s. Shiu, and A. Bernacchia. Improved convergence rates for sparse approx- imation methods in kernel-based learning. In International Conference Machine Learning, pages 21960-21983. PMLR, 2022.
S. Vakili, D. Ahmed, A. Bernacchia, and C. Pike-Burke. Delayed feedback in kernel bandits. In International Conference on Machine Learning, pages 14779-34792 PMLR, 2023a.
S. Vakili, M. Bromberg, J. Garcia, D.-s. Shiu, and A. Bernacchia. Information gain and uniform generalization bounds for neural kernel models. In 2023 IEEE International Symposium on Information Theory (ISIT), pages 555-560. IEEE, 2023b.
M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint /309vv3333068800 2013.
O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, Georgiev, et al. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nature, 575(7782)3350-3344 2019.
12

---

Y. Wang, R. Wang. S. S. Du, and A. Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:19/2.04136, 2019.
Y. Wang, R. Wang, S. S. Du, and A. Krishnamurthy. Optimism reinforcement learning with gener- alized linear function approximation. In International Conference on Learning Representations, 2020.
C.-Y. Wei, M. J. Jahromi, H. Luo, H. Sharma, and R. Jain. Model-free reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference machine learning, pages 101 101000000 PMLR, 2020.
C.-Y. Wei, M. J. Jahromi, H. Luo, and R. Jain. Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3007-3015. PMLR, 2021.
J. Whitehouse, A. Ramdas, and S. Z. Wu. On the sublinear regret of gp-ucb. Advances in Neural Information Processing Systems, 36, 2024.
Y. Wu, D. Zhou, and Q. Gu. Nearly minimax optimal regret for learning infinite-horizon average- reward mdps with linear function approximation. In International Conference Artificial Intelli- gence and Statistics, pages 3883-3913, PMLR, 2022.
Z. Yang, C. Jin, Z. Wang, M. Wang, and M. Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. Advances in Neural Information Processing Systems, 33: 3903-13916, 2020.
S.-Y. Yeh, F.-C. Chang, C.-W. Yueh, P.-Y. Wu, A. Bernacchia, and S. Vakili. Sample complexity of sernel-based q- q-learning. International Conference on Artificial Intelligence and Statisties, pages 453-469. PMLR, 2023.
J. Zhang, A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572-45883 2020.
Z. Zhang and Q. Xie. Sharper model-free reinforcement learning for average-reward markov decision processes. In The Thirty Sixth Annual Conference on Learning Theory, pages 5476-5477. PMLR, 2023.
D. Zhou, He, and Q. Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793-12802. PMLR, 2021.
13

---

Proof of Theorem
In this section, we provide a detailed proof the confidence bound given in Theorem
Let us use the notation
an k. (z) Kn)
(10)
and E, = u(${) - f(z).. En = F21. ". , fn [f(z)), f(2)) .. fzn))
This allows to rewrite the prediction error as
f(=) )(=)-f((3) -[()) an (z)
=f(=) -a, (=) +ex)
-f(=) (.)))) or (z)En.
(11)
The first term on the right-hand side represents the prediction error from noise-free observations, and the second term is the prediction error due to noise. The first term is deterministic (not random) and can be bounded following the standard approaches in kernel-based models, for example using the following result from Vakili et al. (2021a):
Lemma (Proposition Vakili et al. (2021a)). We have
(2)
sup (f(z) a (2) p
Based this lemma, the first on the right hand side of (11) can be deterministically bounded by Czon(z):
a Cyon(z).
The challenging part in Equation (11) the second term, which is the noise-dependent term a (z) Next, we provide a high probability bound on this term
We leverage the Mercer representation of v and write:
((8)
Win Xin (s).
We rewrite the observation vector v. as the sum of noise and the noise-free part f:
v wx() (u( (v(+)) - ((x)) +
f(z))
Observarion noise
Noise-free observation
Using the notation (=) = -Eg (E))P(())((s'), we can rewrite f(z)) as follows:
f(z,) Em-P((e)(o(s))
00
=E,P((
Σ
Wm A (m)
m=1
Wm Ah P
m=l
Wmm Am m (2:).
(12)
14

---

Using this representation, we can rewrite the second term of (11) as follows
Σ c=(6))= = Σ ar(2)
Σ
Wm Ama 3lm (m
Σ
Wm (m
mm=1
m=
Σ
Wmmhe
Am
ax(2) (wm - (2i)
M
Σ
Wm
Am
(2(2) (m (5() - T (2i))
m=1
Wm Am
Σ (z(2) (Um
T (zi))
We decomposed the noise-related error term into infinite series corresponding each eigenfunction Vm. m = 1, 2, .. and partitioned that into the first M elements and the rest. For each the first M elements, we apply the standard confidence intervals for kernel ridge regression. Specifically, Corollary in Whitehouse et al. (2024) implies that, with probability at least 1 - 6/M, we have
Σ a;(=)(Umm -m S Vmaxxn(2)
(V de + +p-1km)
2og
VP
Summing up over the first M elements, and using a probability union bound, with probability least 1
8, we have
M
Σ
(z(())(m - J. (2i))
Wm
m=1
1=1
M
(1))
M
W/m Am
2 2log
V
det(T + p-1Km)
VP
===1
#maxxTn (2)
M
2 22l0g (V
2
Σ Am
deil1 + p=)
Wm
VP
Culimannnz)) (z)
Ad
Am
2
V det(T + p.))
m==1
where the second inequality follows from the Cauchy-Schwarr inequality, and the third inequality follows from the bound ||u|| S Ce.
For the rest of the elements M, have
Σ as(2) (v/ (= S 24/maxx
Σ
Σ 05(2)
WmmAm
Wm Am
m=M+1
1=1
M=
1=1
< 2
Wmdd
n Σ
(z)
m= M+
i=l
2
<
Wmdnm
VP
m=M+1
1/2
2 2n
Σ
w
Σ
Am
VP
M+1
N+11
20, (mxlmaa
<
n
Σ
Am
Vp
M=M+1
15

---

The first inequality holds by the definition of mmax. The second inequality follows from the Cauchy- Schwarz inequality. The third inequality is derived using Lemma The fourth inequality again applies the Sanchy-Schwarz.. inequality, and the final inequality results from the upper bound on the RKHS norm of v.
Putting all the terms together, with probability 1 1,
If(z) f
where B(5)
Cy+ Cormax
VP
M Σ
Am
1
(21108
2log
(v ddee det(T I + x-2KK)
))
1 +
2C m'ax
vP
n
Σ
00
Am
2
mm=1
m=M++
+1
that completes the proof.
Proof of Theorem 3
To analyze the performance of KUCB-RL, first define an event & that all the confidence intervals used in the algorithm hold true.
= (1)(()) 8()),((2), 1t e W
(13)
where
T
B(8) O w log
((T.
By Theorem we have Pr[E] 2 1 1 8/2. We note the under Assumption 4, ||lll SC,, Oww). Also, for v - [0, w]. we have || = O(w). See Yeh et al. (2023), Lemma 3, for proof. Since is upper bounded by by construction, we have P = O(w) that replaces Cj in the expression of in Theorem 1.
We condition the rest of the proof on event E.
Consider such that (to mod w) 0 bound the regret window (Lo 1, w). denoted by Reg (w). In addition let V*(s)) (s) denote the optimum achievable total reward over a window of size starting with initial state and V (s) denote the total reward over window of size achieved by KUCB-RL starting with initial state s.
to
Rio (w) = wt*
r(st, = w. - (Vto + (8to+1)
Σ
((8,
Am
For bounded function v : R, we define its span as span(v) = sup, SES (o(s) - v(5'))
The first term is bounded by the span of v².
Lemma 2. For any s, |wJ* (s) & sp)
Proof follows the exact same lines in the proof of Lemma 13 in Wei et al. (2021).
We next bound the second term in R.o (w). We first prove that (s) S v (s). Lemma 3. Under event E, we have V ())ss) Uto (s), Vs e S.
16

---

Proof.
We can prove this by induction. Note that (s) = Uto +w++++1 = O. For any j E [wo, we
have
Vj (8)
Utg -o 1-j max
aEA ()(s,a) max 1o -
max (s, glo (lotwt1-s(s
aEA
max maxx(PV)-1l(s...) (Puto
"EA
max [ V
dEA
S 0.
The first inequality is due to rearrangement of max, and the second inequality is by the induction assumption. We thus have V (s) S uto (s).
We now bound the difference between Uta (sto+1) 1) and sum of the reward over the window starting at step to + 1: Uto (sto+1) V (stot)). We note that t (Stotw) Vi" (Sto+w) and
2to (to+s($tat)) - V / (sto+s) = 9o + (Sto alo+s) QT (Stotj Ato+i)
< Putots+1l 0to - PV ツー ""mj](($p fo( atots) + 28(5)) (Sto+s: acots)
Voo (8tot5+1) V - (sto+i+1) + ( (Stots: 0to+s)
+ ([Pooottal 4t. 00
+ (V (3to+ [PV (Vt_j][(to++))4ooro
The inequality holds under event E. We obtained a recursive relationship for (1ots Vw- (S-((ttot)) Iterating over j w j get
ta+w w
tatw Σ
Ut 110+1(86+11 - (86++1) I
Σ
28(0)02a (s) +
(PPutil(())))) - ((41(1441))
1=to+1
t=
fo+t
(Vi ((400-1-((141)) - [PV 1
t
The second and third terms are zero mean martingales with span of 2w, which are sub- Gab-Gussiin random variables with parameter w. Therefore, by czuma-Hoeffding inequality (Lalley, 2013), with probability at least 1 - 5/2,
T
(Potil(ss,a)) - 1041 (8(+1))
v [e
(8++1)
[PV (0-1)(1)))])- ot)
1=1
S swy2r log (2)
We note that for each & [T]. we can present the corresponding tu with to = w0 (t-(tt1) (00-)/w]. Summing up the regret over all windows of size up to time have, with probability 1 5,
Tspan(o") W
R(T)
S
+ w 27 log
+ 2,3(6)
(14)
thus remains to bound ΣT. (wt((t))/1 (z+).
The sum of sequential standard deviations of a kernel based model is often bounded using the following result from Srinivas al. (2010) that similar to the elliptical potential lemma in linear bandits (see, Abbasi-Yaa Yadkori et al., 2011).
17

---

T Σ t=1
2y(T:p) log(1 [1 + 1/p)
(z)) -
(15)
This result however is not directly applicable here due to the w w|(t /w subscript (w((t-1)/ 1)/w] rather dt-1. A loose approach would be to partition the sequence into w sequences, each for one j e [w] of the form o (i- 1)++. 1,2, ... //W. For each of those sequences, (15) is applicable and we get
T/ Σ 1=1
2T(T/w; log(1 + 1/p)
1)+5 wli (ili-)+ (Zwitz)
(16)
Using this bound we have
10 T/w
Σ
w [[(t-1)/w] (2+) Σ
(o(i-1)+/ (it
j=1
2wy(T/uu /w: /w:p)
$
(17)
log(1 + 1/p)
Next, we prove a stronger bound on E o [(+ 1)/w] (zt) that contributes to the sublinear regret bounds in this paper.
Lemma 4, For a sequence of observation points {zrTT= and any w N, we have
2y(T:p) Jwi(t 1/ S log(1+ + 1/p) (T+
2w2z p) log(1 + 1/p) (1pp)
(18)
Proof of Lemma 4. We use the following lemma on the ratio of variances conditioned on two sets of observations.
Lemma 5 (Proposition A.1 in Calandriello et al. (2022)). For any sequence of points 1- for any and t' < t
(2) 1
S1+
Σ (2))
07 (2)
j j=
We thus can write
T
n (t 11/w (1/1 az) s
5e ar)
1+
Σ
o2 - (s,, ag) a,)
(==((t-1/w]+
T
of (5 at)
T 02 (0100-))a
t=1
(T; log(1 1 + 1/p)
(T 2w2> log(1 + 1/p)
(19)
The first inequality is by Lemma 5, the second inequality follows from Cauchy- Sehohy--S inequality, and the last inequality is the bound established in Equation (17). This completes the proof of Lemma 4.
18

---

Using Lemma 4, and substituting the value of (()) into (14), we obtain
T + R(T) 0
((T: log 7
v (T:T((Tp))
p ( p))
(20)
The proof of the regret bound is complete.
8 Mercer Theorem and the RKHSs
Mercer theorem (Mercer, 1909) provides a representation of the kernel in terms of an infinite dimensional feature map (e.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 square-integrable functions on Z with respect to p. We further say kernel is square-integrable if
Ja 12 (((()))d(())(()))) < 00.
Theorem (Mereer Theorem). Let Z be a compact metric space and μ be a finite Borel measure on Z. Let l be a continuous and square-iie iittur--itterablee kernel, inducing an integral operator Tr 1 (Z) + (Z) defined by
(TT) - d du(z))
where f E (Z). Then, there exists a sequence of sigenvalue-eigeffannie pairs {(Ams im pm)) ) such that Am 0, and TRPP Am for m. 1. Moreover, the kernel function can be represented as
1 (22
Σ Am (m) (z))
where the convergence of the series holds uniformly
Z.
According to the Mercer representation theorem (c.g., see, Christmann and Steinwart, 2008, Theorem 4.51), the RKHS induced by l can consequently be represented in terms of {(mms )
Theorem 6 (Mercer Representation Theorem). Let {()m (Pm)) be the Mercer eigenvalue eigen- feature pairs. Then, the RKHS of is given by
-(10) Σ
H4 = 10)
Wm Ai Pm wm E &R =
W < 00
m=1
m=1
Mercer representation theorem indicates that the scaled eigenfeatures { Ammmpmma form an orthonormal basis for Hy.
19

---

1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims include
Proposing an optimistic algorithm for kenrel-based function approximation in the infinite horizon average reward RL setting: KUCB-RL (Algorithm 1) presented in Section 3.
Establishing novel no-regret performance guarantees for our algorithm: The regret analysis provided in Section 4.
Deriving a novel confidence interval for the kernel-based prediction of the expected value function, applicable across various RL problems: Provided in Theorem 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Discussed in Section 5,
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
20

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All of the Assumptions used in Theorem are presented in the statement of the theorem, making it self-contained and easy to apply across various RL settings. The Assumptions used in Theorem 3 are Assumptions 1, 2, 3, and 4, clearly stated. The detailed proofs are provided in Appendix 6 and Appendix 7, with proof sketches briefly discussed in the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: Paper does not include experiments
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
21

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer:[NMa [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nip)) cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. wwtpccccppppcceeccccccccccccccct httpa///cgiieee/eeeeuubiiiieeee wwweeeeubmmssiooPooi
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question:
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
22

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / /tt.riuuui.pp//. wwttrips.cccpppeee cttppclcccc//ccccccccccccccccltt /ettiiccieiiiioooeeie ing
Answer: [Yes]
Justification:
We have reviewed the NeurlPS code of Ethics and ensured that we are in full compliance.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: Our work provides guidance on designing efficient RI algorithms but does not address specific applications that constitute an explicit impact statement.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
23

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer:[NA].
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswi twwoee.hooo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
24

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer:[NA]]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
25


Reviews:
[{"review_id": "L0Hbjl4UZM", "reviewer": "Reviewer_KBUd", "summary": "The paper proposes a kernel-based optimistic algorithm for the average reward setting and corresponding regret analysis. As described, the kernel-based setting is a more general extension of linear structure to an infinite-dimensional linear model in the feature space of a positive definite kernel.", "questions": "1)Can the results be improved to \\sqrt{T} under uniform mixing conditions (which is a stronger assumption)?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This seems to be the first treatment for average reward MDP in the kernel-based setting. The paper seems to be well-written. Overall, this could be interesting addition to the set of literature in average reward RL", "weaknesses": "The technical portion of the main text can be improved if the paper discusses the key steps/challenges of the proof. E.g., Theorem 1 is based on results of prior work [37]; without moving to the appendix, it is impossible to extract the technical novelty in this paper.", "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 positive feedback.\n\nFollowing your comment, we will enhance the main text with more detailed technical content. We have provided a proof sketch in the paragraph following Remark 1, which we will expand to further detail the proof of Theorem 1. \n\nUnlike typical settings such as (supervised) kernel ridge regression or kernel-based bandit settings [22, 23, 24, 36, 37, 24], in the RL setting, confidence intervals are applied to $f_t = [P v_{t+1}]$, which varies due to the Markovian nature of temporal dynamics, with each $v_t$ derived recursively from $v_{t+1}$. Hence, the confidence interval must be applicable to all functions $v$ in a function class. This requirement is captured in the theorem: \"For all $z \\in Z$ and $v: ||v||_{H_k'} \\le C_v$, the following holds ...\". To achieve such confidence intervals, we use a novel technique by leveraging the Mercer representation of $v$ and decomposing the prediction error $|f(z) - \\hat{f}_n(z)|$ into error terms corresponding to each Mercer eigenfunction $\\psi_m$. We then partition these terms into the first $M$ elements corresponding to eigenfunctions with the largest $M$ eigenvalues and the rest. For each of these $M$ eigenfunctions, we obtain high probability bounds using existing confidence intervals from [24]. Summing up over $m$, and using a bound based on uncertainty estimates, we achieve the high probability bound—corresponding to the second term in $\\beta(\\delta)$, and bound the remaining elements based on the eigendecay—corresponding to the third term in $\\beta(\\delta)$.\n\nIn summary, the key technical novelties in deriving the concentration bound involve leveraging the Mercer decomposition of $v$ and the error term, partitioning the decomposition into the first $M$ elements and the rest, bounding each of the first $M$ elements using exisitng kernel-based confidence intervals, bounding the rest based on eigendecay, and then summing up over all $m$ to derive the confidence interval. \n\nWe emphasize that this is a substantial result that can be applied across various RL problems.\n\n> *1) Can the results be improved to \\sqrt{T} under uniform mixing conditions (which is a stronger assumption)?*\n\n\nAs noted in the introduction, [20] achieved a regret bound of $\\tilde{O}(\\frac{1}{\\sigma}\\sqrt{t_{mix}^3 T})$ under the linear bias function assumption, where $\\sigma$ is the smallest eigenvalue of the policy-weighted covariance matrix. While assuming a strictly positive smallest eigenvalue (independnt of $T$) for the covariance matrix is reasonable in a finite-dimensional setting where $d \\ll T$, it becomes unrealistic in the kernel setting. This presents significant challenges in adapting the existing results to the kernel setting. It is not clear whether tighter results can be achieved under uniform mixing conditions, necessitating further research.\n\nPlease let us know if any further clarifications on these points are required.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zp5Oa3aQxW", "reviewer": "Reviewer_pN55", "summary": "The authors consider the setting of reinforcement learning in infinite horizon average reward MDPs. In particular, they consider a kernel based function approximation to represent value functions. Most of the prior work involving kernel regression has been in the context of bandits, where the state cardinality is 1. In the context of reinforcement learning, the complexity is enhanced, since the state space is no longer degenerate and actions influence transitions to future states. Hence, the setting in which kernel approximation is employed is thus more complicated. Some limited prior work in the domain of RL involves using kernel functions whose eigenvalues decay in an exponential manner which in the current work has been relaxed to polynomial decay, thus encapsulating a wider class of approximation architectures. The value functions are computed using kernel functions along with a confidence bound. Another contribution of the authors is characterizing the confidence bounds in this context. The value functions are set to zero ahead of a time horizon $w$ and are recursively back calculated using samples generated till previous time horizon. The next set of samples are generated using these new estimates of value functions. The final regret bounds are characterized as a function of the polynomial decay $p$, but are sublinear for all $p>1$.", "questions": "1. The notion of maximum information gain $\\gamma$ is unclear. If the information gained is maximized, intuitively, it results in better regret bounds? However, larger the value of $\\gamma$, greater the magnitude of the regret. It would help to characterize what $\\gamma$ represents in the context of RL. \n\n2. It is unclear as to how the reseting and back calculation of the value function from time $t+w+1$ to $t+1$ in Algorithm 1 helps with the analysis. \n\n2. Won't the projection operator in Equation 5 negate the role of the confidence bounds? It makes sense for the value functions to not exceed the horizon $w$, since the rewards are $<1$, however the information from the previous samples seem to be represented solely through the confidence bound term $\\beta \\sigma$. Would the performance be better if the projection was onto a space larger than $w$? Since there seems to be a tradeoff with respect to $w$ in the final bounds, is there a intuitive explanation as to why such a tradeoff exists? As in what aspect of the analysis gets better as $w$ grows larger and what gets worse?", "limitations": "The limitations of this work have been explicitly addressed.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. A major strength of using kernel functions is the expressibility of the function class with respect of the representation of state action and state value functions. Most literature in the context of RL relies on linear function approximation (which is a special case of kernel functions) due to ease of analysis. Kernel approximations on the other hand capture functions classes such as neural tangent kernel and Matern family. Moreover this work relaxes the exponential decay of eigenvalues utilized in the previous work to polynomial decay, which is a significant improvement.\n\n2. The final bounds are in general form which depends on the polynomial decay of the eigenvalues. The authors also remark on how the regret bounds for the linear function approximation case can be derived from this general form. The authors also present the first sublinear regret bounds in the context of polynomially decaying eigenvalues of the kernel function.\n\n3. Their construction of confidence bounds may be of independent interest for the design of optimistic algorithms in RL using kernel function approximation.", "weaknesses": "1. The function approximation representation of the state action value function at time $t$ involves inversion of a matrix of dimension $t$. This operation is performed at every iteration of the algorithm. As $t$ grows, this computation might be expensive. It is unclear as to whether there is a short cut to circumvent this step in the algorithm, which might make it intractable in large time horizons. \n\n2. The value functions are being reset to 0 repeatedly after a finite time horizon $w$. The samples generated till that time instant only manifest in the confidence bounds. It's not entirely clear as to what the significance of reseting this value function to 0 is establishing since it seems to be not data-efficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our paper. We appreciate your positive feedback regarding the generality of our setting and results, as well as the potential independent interest in the confidence bounds. We will address your comments and questions in detail, hoping this will enhance your evaluation of the paper.\n\n> *Computational complexity:*\n\nKernel-based models provide powerful and verstile nonlinear function approximations and lend themselves to theoretical analysis.\nIt is, however, well-known that kernel ridge regression has a relatively high computational complexity, primarily due the matrix inversion step. This challenge is not unique to our work and is common across kernel-based supervised learning, bandit, and RL literature. Luckily, sparse approximation methods such as Sparse Variational Gaussian Processes (SVGP) or the Nyström method significantly reduce the computational complexity (to as low as linear in some cases), while maintaining the kernel-based confidence intervals and, consequently, the eventual rates; e.g., see Vakili et al. ICML'22 and references therein. These results are, however, generally applicable and not specific to our problem. We thus preferred to avoid further complicating the notation and presentation of an already notation-heavy RL setting to focus on our main results and contributions specific to this paper.\n\n``Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning'', Vakili, Scarlett, Shiu, Bernacchia, ICML 2022.\n\nAdditionally, as a minor point, the matrix inversion step is required only every other $w$ steps, in contrast to every step, which further improves computational complexity. We will add these discussions to the revision. \n\n> 1. *maximum information gain:* \n\nThis is a kernel-specific quantity that captures the complexity of kernel-based learning. It is a common measure in the literature on kernel-based bandits [22, 23, 24, 36, 27] and RL [12, 25, 26]. As defined in Section 2.5, the value of $\\gamma$ depends only on the kernel and the free parameter $\\rho$. The algorithm itself does not aim to maximize information gain; rather, it is an algorithm-independent and kernel-specific complexity term that appears in the regret bound. Intuitively, $\\gamma$ captures the complexity of the function class. Under a linear assumption, $\\gamma=O(d\\log(T))$. For kernels with exponentially decaying eigenvalues  $\\gamma=O(poly\\log(T))$, and for kernels with polynomially decaying eigenvalues, such as the Matérn family and Neural Tangent kernels, the bound on $\\gamma$ is given in Section 2.5. For proofs of these bounds, see [22, 35]. \n\n> 2. *Reseting and back calculation of the value function on a window with size $w$:* \n\nWe here address this question along with the related observations from the \"Weaknesses\" section and the subsequent discussion on the tradeoff in choosing $w$ from the next question. We understand the reviewer's comments to be highlighting two specific aspects of our algorithm and analysis.\n\n**First aspect:** For kernel ridge regression on $[P v_{t+1}]$, we only use observations up to $t_0$, where $(t_0 \\mod w) = 0$ and $t_0+1 \\le t \\le t_0+w$. This might seem data inefficient as it does not utilize the $t-t_0 \\le w$ samples: \n\nWe address this in our analysis. After Theorem 2, which presents the performance of the algorithm, it is noted: \"Algorithm 1 updates the observation set every $w$ steps, requiring us to characterize and bound the effect of this delay in the proof. A straightforward application of the elliptical potential lemma results in loose bounds that do not guarantee no-regret. We establish a tighter bound on this term, contributing to the improved regret bounds.\" In particular, we show that this delay in updating the observation set does not change the eventual rates. The proof, based on Lemma 4, is detailed in lines 555 - 565 in the appendix. The key idea in the proof is to bound the ratio between a delayed uncertainty estimate update and a non-delayed one, followed by some arithmetic manipulation.\n\n**Second aspect:** Regarding the window’s role (i.e., setting the value function to $0$ at the end of the window, backtracking to compute the proxy value function over the window, and unrolling the policy in a forward direction over the window), there is an apparent tradeoff in choosing the window size:\n\nThis tradeoff balances between the strength of the value function and the strength of the noise. A longer window is preferred to capture the long-term performance of the policy, while a larger window increases the observation noise affecting the kernel ridge regression. We recall that both target function $[Pv_{t+1}]$ and observation noise $v_t-[Pv_{t+1}]$ are bounded by $w$. This tradeoff is explicitly seen in the regret bounds. The optimal size of the window, as specified in line 335, results from an optimal interplay between these two factors, which is explicitly captured in the regret bounds.\n\nWe appreciate this discussion and believe that the inclusion of these points will enhance the paper. Please let us know if any further clarifications are needed regarding these aspects.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1HoJZlYekr", "reviewer": "Reviewer_unzJ", "summary": "This paper studies learning in MDPs with the long-run average reward objective, assuming that the MDP satisfies some kernel assumptions. A UCB-type of learning algorithm is proposed and is proved to achieve sublinear regret when the eigenvalues of the kernel operators decay at the rate of a p-th degree polynomial with p > 1. \nThe paper also proves a confidence interval bound for kernel ridge regression, which is of independent interest.", "questions": "M is not defined in the equation in line 291. Do you mean the equation holds for any natural number M?", "limitations": "A discussion of limitation is included.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The result in this paper seems to be strong: it proves a regret bound with a pretty weak MDP assumption (weaker than weakly-communicating), and a RKHS kernel assumption on the structure of the transition kernel which seems to significantly weaken the tabular and linear assumptions in prior work.", "weaknesses": "The use of Bachmann-Landau notation is confusing. Specifically, in Assumption 3, it is unclear which variable is scaling in the o(1) notation. Similarly, in Theorem 2, multiple variables appear in the big-O notation, again making it unclear which variable is scaling. \nIt seems to me that the use of big-O notation is unnecessary, given that most steps in the proofs are non-asymptotic. It would be clearer to state the theorems in the non-asymptotic form, and then state a corollary when certain variables scale. \n\nDetails for bounding the maximal information gain \\gamma(\\rho; t) is missing. The authors mention that this maximum information gain is O(d \\log(t)) in line 216-211 in the special case of d-dim linear kernels, but did not provide references or proofs.", "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 positive feedback on the strength of the results. Here, we address your comments in detail and hope this will enhance your evaluation of the paper.\n\n> *The use of $O$ notation:* \n\nAs mentioned by the reviewer all of our proofs are non-asymptotic and our use of $O$ notation, which is common practice in the literature, serves to simplify presentations. Theorem 1 does not use $O$ notation. We will revise the statement of Assumption 3 to read: \"...$M\\sum_{m=M+1}^{\\infty}\\lambda_m\\le C$, for any $M\\in\\mathbb{N}$ and some constant $C>0$ independet of $M$.\" We will also clarify the statement of Theorem 2 by introducing an absolute constant independent of all parameters: $T,w, \\rho, \\delta$. We are ultimately interested in scaling with $T$ after $w$ and $\\rho$ are selected optimally with respect to $T$, as given in Remark 2, which we will further clarify. \n\n> *References for bounds on information gain*\n\nThank you for pointing out the missing references for maximum information gain. The bound for the linear case is given in [22]. Further discussions and tight bounds for kernels with exponential and polynomial eigenvalue decay are provided in [35]. We will ensure these references are properly included.\n\n> *M is not defined in the equation in line 291. Do you mean the equation holds for any natural number M?*\n\nYes, the statement holds for any natural number $M$. We will clarify this point in the revision.\n\nFor further details on the role of this $M$ in the analysis, please see our response to Reviewer KBUd. Additionally, a simplified presentation of the confidence interval is given in Remark 1, where $M$ is removed.\n\nWe would be happy to provide further clarifications on any of these points.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a kernel-based optimistic algorithm for average reward RL in the infinite horizon setting. The authors provide new no-regret performance guarantees under kernel-based modeling assumptions, extending previous work to the more complex RL context.
The reviewers highlight both strengths and weaknesses of the paper. They praise its technical soundness and contribution, recognize its novelty in the average reward MDP context, and emphasize the importance of the kernel-based approach. However, some concerns are raised regarding computational complexity, the effectiveness of the value function reset, and the role of the projection operator in the analysis. The authors address all these issues.

Overall, the paper presents a solid contribution to the field of average reward RL by extending kernel-based methods and achieving sublinear regret bounds. The reviews acknowledge the novelty and theoretical strength of the work while raising valid concerns about computational complexity and specific aspects of the analysis. The authors demonstrate a comprehensive understanding of the issues and provide convincing responses. This paper warrants acceptance, provided the authors address the reviewers' concerns and further clarify the details of their analysis.
Decision: Accept (poster)