Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm

Authors: sattar  vakili
mediatek  research
julia  olkhovskaya
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 16:48:23

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.

Main paper: 
 introduction: 
 Reinforcement learning (RL) has demonstrated substantial practical success across a variety of application domains, including gaming (Silver et al., 2016; Lee et al., 2018; Vinyals et al., 2019) , autonomous driving (Kahn et al., 2017) , microchip design (Mirhoseini et al., 2021) , robot control (Kalashnikov et al., 2018) , and algorithmic search (Fawzi et 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 et al., 2020 (Wei et al., , 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 a natural progression in the complexity of RL models corresponding to the structural complexity of the Markov Decision Process (MDP). This progression ranges from tabular models to linear, kernel-based, and deep learning-based models. The kernel-based structure is an extension of linear structure to an infinite-dimensional linear model in the feature space of a positive definite kernel, resulting in a 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 as an intermediate step towards 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) .The infinite-horizon average-reward setting has been extensively explored under the tabular structure (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 O(poly(|S|, |A|) √ 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, a 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 O((dT ) 3 4 ) 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 (d = ∞). As such, the results with linear models do not translate to the kernel-based 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 kernel-ridge 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 q t , at each step t, for the state-action value function over this future window. At each step t with the current state s t , the action is selected greedily with respect to this proxy: a t = arg max a∈A q t (s t , 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 et 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 kernel-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 a fixed reward function. To address this latter challenge, we derive a novel kernel-based confidence interval that is applicable across RL problems.To summarize, our contributions are as follows. We develop a kernel based optimistic algorithm for the infinite horizon average reward setting, referred to as KUCB-RL. We establish no-regret guarantees for the proposed learning algorithm, which is the first for this setting to the best of our knowledge. Specifically, in Theorem 3, we prove a regret bound ofO T w + w + w √ ρ γ(T ; ρ) + log( T δ ) ρT γ(T ; ρ) + ρ 2 w 2 γ(T ; ρ)γ(T /w; ρ) , at a 1 -δ con-fidence level, where ρ is the parameter of kernel ridge regression and γ(T ; ρ) is the maximum information gain, a kernel specific complexity term (see Section 2). This regret bound translates to Õ d1 2 T 3 4in the special case of a 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 Õ(T 3 4 ), 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 3p+5 4p+4 ), 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 1, we develop a novel confidence interval applicable across kernel-based RL problems that contributes to the eventual improved results.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 kernel-based structures mentioned above, other notable distinctions among settings include model-based 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 at 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 kernel-based 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 al., 2021; Vakili, 2024) . The regret bound proven in Yang et 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, albeit with a 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 a particular assumption that relates the kernel eigenvalues to the size of the domain. The work of Chowdhury and Oliveira (2023) is most closely related to ours in terms of kernel-related assumptions. Specifically, our Assumption 4 is identical to Assumption 1 of Chowdhury and Oliveira (2023) . They establish a regret bound of O(Hγ(N ; ρ)N ) for the episodic MDP setting, where N is the number of episodes, γ(N ; ρ) is the maximum information gain, a kernel-related complexity term, H is the episode length and the value of ρ 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 γ(N ; ρ) possibly grows faster thanN . As a result, a 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) as well.In the tabular case, a lower bound of Ω( D|S||A|T ) on regret was established in Auer et al. (2008) in the infinite-horizon average-reward setting, where D is the diameter of the MDP. For ergodic MDPs, Wei et al. (2020) shows a regret bound of Õ( t 3 mix |S||A|T ), where t mix 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 Õ(|S| 5 |A| 2 √ T ), 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-Yadkori et al., 2019a,b; Hao et al., 2021) . Notably, Hao et al. (2021) achieved a regret bound of Õ 1 σ t 3 mix T under the linear bias function assumption, where σ is the smallest eigenvalue of policy-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/4 ). 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 a separate model-based approach to the problem where the transition probability distribution (model) is 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 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 et al. (2024) . Bandit settings can be considered a degenerate case of the RL framework with |S| = 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 on 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 et al. (2021) , Assumption 2, and for the linear bias function case, see Wei et al. (2021) , Assumption 4. (Wei et al., 2021) Õ((dT ) 3/4 ) Bellman Optimality Eq. Linear MDP-Exp2 (Wei et al., 2021 )Õ( t 3 mix |S||A|T ) Uniform Mixing Linear Bias function KUCB-RL (Algorithm 1) Õ d 1 2 T 3 4Bellman Optimality Eq. LinearKUCB-RL (Algorithm 1) Õ T 3 4Bellman Optimality Eq. Kernel-based (exponential)KUCB-RL (Algorithm 1) Õ T 3p+5 4p+4Bellman Optimality Eq. Kernel-based (polynomial)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 as long as it is clear that these goals are not attained by the paper. 
problem formulation: 
 In this section, we overview the background on infinite horizon average reward (undiscounted) MDPs and kernel based modelling.An undiscounted MDP is described by the tuple (S, A, r, P ) where S is a state space with a possibly infinite number of elements, A is a finite action set, r : S × 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 a is selected at state s. Throughout the paper we use the notation z = (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 s 1 ∈ S. At each step t, the learner observes state s t and takes an action a t resulting in a reward r(s t , a t ). The next state s t+1 is revealed as a sample drawn from the transition probability distribution:s t+1 ∼ P (•|s t , a t ).The goal of the learner is to compete against any fixed stationary policy. A stationary policy π : S → A is a possibly random mapping from the states to actions. The long-term average reward of a stationary policy π, starting from state s ∈ S, is defined as:J π (s) = lim inf T →∞ 1 T E T t=1 r(s t , a t ) s 1 = s, ∀t ≥ 1, a t = π(s t ), s t+1 ∼ P (•|s t , a 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 ⋆ ∈ R and bounded measurable functions v ⋆ : S → R and q ⋆ : S × A → R such that the following conditions are satisfied for all states s ∈ S and actions a ∈ A :EQUATIONThis 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 a policy π ⋆ (s) = arg max a∈A q ⋆ (s, a), which deterministically selects actions that maximize q ⋆ in the current state, is the optimal policy π ⋆ = arg max π J π , with J π ⋆ (s) = J ⋆ , for all s (Wei et al., 2021) .For the finite state setting, Assumption 1 follows from the weakly communicating MDP assumption (see, e.g., Puterman, 1990, Chapter 9) . Assumption 1 also holds under several other common conditions (Hernández-Lerma (2012), Section 3.3).The learner's performance is measured by regret, which is defined as the difference in total reward between the learner and the optimal stationary policy. Specifically,EQUATIONWe emphasize that under Assumption 1, for any initial state s 1 ∈ S, J π ⋆ (s 1 ) = J ⋆ , that is reflected in our regret definition.For any value function v : S → R, throughout the paper, we use the notation[P v](z) = E s ′ ∼P (•|z) [v(s ′ )]for the expected value function of the next state.Consider a positive definite kernel k : Z × Z → R. Let H k be the reproducing kernel Hilbert space (RKHS) induced by k, where H k contains a family of functions defined on Z.Let ⟨•, •⟩ H k : H k × H k → R and ∥ • ∥ H k : H k → Rdenote the inner product and the norm of H k , respectively. The reproducing property implies that for all f ∈ H k , andz ∈ Z, ⟨f, k(•, z)⟩ H k = f (z).Mercer theorem implies that k can be represented using a possibly infinite dimensional feature map:EQUATIONwhere λ m > 0, and √ λ m φ m ∈ H k form an orthonormal basis of H k . In particular, any f ∈ H k can be represented using this basis and weights w m ∈ R asf = ∞ m=1 w m λ m φ m , where ∥f ∥ 2 H k = ∞ m=1 w 2 m .A formal statement and the details are provided in Appendix 8. We refer to λ m and φ m as (Mercer) eigenvalues and eigenfunctions of kernel k, respectively.Kernel-based models provide powerful predictors and uncertainty estimators which can be leveraged to guide the RL algorithm. In particular, consider a fixed unknown function f ∈ H k . Assume a t × 1 vector of noisy observations y t = [y i = f (z i ) + ε i ] t i=1 at observation points {z i } t i=1 is provided, where ε i 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) ,EQUATIONwhere k t (z) = [k(z, z 1 ), . . . , k(z, z t )] ⊤ is a t × 1 vector of the kernel values between z and observations,K t = [k(z i , z j )] t i,j=1is the t × t kernel matrix, I is the identity matrix appropriately sized to match K t , and ρ > 0 is a free regularization parameter.Confidence bounds of the form |f (z) -ft (z)| ≤ β(δ)σ t (z) are established, for a confidence interval width multiplier β(δ) at a confidence level 1 -δ, which depends on the assumptions on the setting and the noise. We will establish a such confidence interval specific to the RL setting, in Theorem 1, and utilize it in our regret analysis.In our RL setting, we use a kernel-based model to predict the expected value function. In particular, for a given transition probability distribution P (s ′ |•, •) and a value function v : S → R, we define f = [P v] and use past observations to form predictions and uncertainty estimates for f , 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 kernel-based models on f , we require the following assumption. Assumption 2. We assumeP (s ′ |•, •) ∈ H k , for some positive definite kernel k, and ∥P (s ′ |•, •)∥ H k ≤ 1 for all s ′ ∈ S.Our regret bounds are presented in terms of maximum information gain which is a kernel-specific complexity term. Specifically, for a kernel k and sets of observation points {z i } t i=1 , we define the maximum information gain γ(t; ρ) as followsγ(t; ρ) = sup {zi} t i=1 ⊂Z 1 2 log det I + K t ρ ,where ρ > 0, and K t is the kernel matrix defined in Section 2.3. Several works have established upper bounds on γ(t; ρ). In the special case of a d-dimensional linear kernel, we have γ(t; ρ) = O(d log(t)).For kernels with exponential eigendecay, including SE, γ(t; ρ) = O(polylog(t)) (Srinivas et al., 2010; Vakili et al., 2021b) . For kernels with polynomial eigendecay, which represent a crucial case due to challenges in establishing no-regret guarantees in RL and bandits, and include kernels of both practical and theoretical interest such as the Matérn family and NT kernels, we first provide the definition below and then the bound on γ. Definition 1. A kernel k is said to have a p-polynomial eigendecay if ∀m ≥ 1, λ m ≤ Cm -p , for some p > 1, C > 0 where λ m 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; ρ) = O t ρ 1 p log 1 + t ρ 1-1 p .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 are encouraged to create a 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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. 
kucb-rl algorithm: 
 In this section, we introduce our algorithm, Kernel-based Upper Confidence Bound for Reinforcement Learning (KUCB-RL). The algorithm's structure is similar to acquisition-based kernel bandit algorithms such as GP-UCB (Srinivas et al., 2010) , where each action is chosen as the maximizer of an acquisition function. We construct an optimistic proxy q t for the state-action value function. At each step t, given the current state s t , the action a t is selected as the maximizer of q t (s t , a) over a. This proxy q t is derived using past observations of transitions, employing kernel ridge regression to provide a prediction and uncertainty estimate for the state-action value function over a future window of size w ∈ N. The proxy is established as an upper confidence bound, following the principle of optimism in the face of uncertainty. The value functions are computed in batches of w steps, and the derived policies are unrolled over the subsequent w steps. The details are presented next.We define a fixed window size, w ∈ N, which represents the future interval that the algorithm will consider. For a given t 0 where (t 0 mod w) = 0, including t 0 = 0, we initialize v t0+w+1 (s) = 0, ∀s ∈ S, reflecting the algorithm's consideration of the reward within this future window of size w. Subsequently, we recursively obtain proxies q t and v t for all steps t ∈ {t : t 0 + 1 ≤ t ≤ t 0 + w}. Let f t denote [P v t+1 ],for t = 0, 1, 2, • • • do 2: if (t mod w) = 0 then 3: Let v t+w+1 = 0; 4: for h = 1, 2, • • • , w do 5:Compute q t+w+1-h and v t+w+1-h using equations ( 6) and ( 7). Select a t = arg max a∈A q t (s t , a); Observe s t+1 ∼ P (•|s t , a t ) and receive r(s t , a t ). 9: end for estimator. The predictor and the uncertainty estimator are derived using the data set D t0 , which contains observations of past transitions up to t 0 . We use the notation D t = {(s j , a j , s j+1 )} j≤t for the past transitions, and also definev t+1,t0 = [v t+1 (s 2 ), v t+1 (s 3 ), • • • , v t+1 (s t0+1 )] ⊤ ,for the values of the proxy value function at the history of state observations. We then haveEQUATIONwherek t (z) = [k(z, z 1 ), k(z, z 2 ), • • • , k(z, z t ))]⊤ denotes the vector of kernel values between z and (z j = (s j , a j )) j≤t in the history of observations, andK t = [k(z i , z j )] t i,j=1 denotes the kernel matrix.Equipped with the kernel ridge predictor and uncertainty estimator, we define q t as an upper confidence bound for f t , as follows:EQUATIONwhere 1 -δ represents a confidence level, and β(δ) is a confidence interval width multiplier; the specific value of which is given in Theorem 3. The notationΠ [a,b] (•) is used for projection on [a, b]interval. This step is natural since with the assumption r : Z → [0, 1] the value over a window of size w can not be more than w. We also define v t (s) = max a∈A q t (s, a), ∀s ∈ S.By iteratively updating from t = t 0 + w to t = t 0 + 1, we compute the values of q t and v t for all t from t 0 + 1 to t 0 + w. Then, we unroll the learned policy over the subsequent w steps, as the greedy policy with respect to q t : a t = arg max a∈A q t (s t , a).A pseudocode is provided in Algorithm 1.Computational Complexity. KUCB-RL enjoys a polynomial computational complexity of O( T 4 w ), where the bottleneck is the matrix inversion step in (5) in kernel ridge regression every w steps. This 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 of matrix inversion step (to as low as linear in some cases), while maintaining the kernel-based confidence intervals and, consequently, the eventual rates (see, e.g., Vakili et al., 2022, and references therein) . These results are, however, generally applicable and not specific to our problem. 
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 RL setting under general assumptions based on kernel-based modelling. We first derive a novel confidence interval that is broadly applicable to the kernel-based RL problems. We then utilize this result to establish bounds on the regret of KUCB-RL.The analysis of our algorithm utilizes confidence intervals of the form |f t (z) -ft (z)| ≤ β(δ)σ t (z), where f t = [P v t ] denotes the expected value of a value function v t , and ft and σ t represent the kernel ridge predictor and the uncertainty estimate of f t . Here, β(δ) represents the width multiplier for the confidence interval at a 1 -δ confidence level. Similar confidence intervals are established in kernel ridge regression for a fixed function f in the RKHS of a specified kernel k (see, e.g., Abbasi-Yadkori, 2013; Srinivas et al., 2010; Chowdhury and Gopalan, 2017; Vakili et al., 2021a; Whitehouse et al., 2024) . In the RL context, specific considerations are required as both f t = [P v t ] and the observation noise depend on the value function v t that varies due to the Markovian nature of the temporal dynamics. We note that in this setting, for a given value function v : S → R, the observation noise is captured by v(s t+1 ) -[P v](s t , a t ). A possible approach involves deriving confidence intervals that apply to a 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 a specific value of kernel ridge regression parameter ρ, constrained by their proof techniques. Inspired by Whitehouse et al. (2024) , which established a confidence interval for kernel ridge regression (not within the RL context) but allowed for a judicious selection of ρ, we prove a new confidence interval suitable for the RL setting that allows tuning parameter ρ. As a result, we obtain the first improved no-regret algorithms in this setting. Theorem 1 (Confidence Bound). Consider v : S → R, a conditional probability distribution P (s|z), s ∈ S, z ∈ Z, and two positive definite kernels k :Z × Z → R and k ′ : S × S → R, where Z = S × A is compact subset of R d . Let f = [P v] and assume ∥v∥ H k ′ ≤ C v , v(s) ≤ w, ∀s ∈ S, and ∥f ∥ H k ≤ C f , for some C v , w, C f > 0. A dataset {(z i , s ′ i )} n i=1 ⊂ (Z × S) n is provided such that s ′ i ∼ P (•|z i ). Let λ m , m = 1, 2, • • • denote the Mercer's eigenvalues of k ′ ina decreasing order and ψ m denote the corresponding eigenfunctions, with ψ m ≤ ψ max for some ψ max > 0.Let fn and σ n be the kernel ridge predictor and the uncertainty estimate of f using the observations:fn (z) = k ⊤ n (z)(ρI + K n ) -1 v n , σ 2 n (z) = k(z, z) -k ⊤ n (z)(ρI + K n ) -1 k n (z), where v n = [v(s ′ 1 ), v(s ′ 2 ), • • • , v(s ′ n ))]⊤ is the vector of observations. For all z ∈ Z and v : ∥v∥ H k ′ ≤ C v , the following holds, with probability at least 1 -δ,|f (z) -fn (z)| ≤ β(δ)σ n (z), with β(δ) = C f + C v ψ max √ ρ M m=1 λ m 1 2 2 log M δ det(I + ρ -1 K n ) 1 2 + 2C v ψ max √ ρ n ∞ m=M +1 λ m 1 2.We can simplify the presentation of β under the following assumption.Assumption 3. For the kernel k ′ , we assume that for some C 1 , C 2 and q > 0,M m=1 λ m ≤ C 1 and, ∞ m=M +1 λ m ≤ C 2 M -q for any M ∈ N.This is a mild assumption. For example, a p-polynomial eigendecay profile with p > 1, which applies to a large class of common kernels including SE, Matérn and NT kernels, satisfies this assumption with C 1 = pC p-1 , C 2 = C p-1 , and q = p -1, where C is the constant specified in Definition 1. Remark 2. Under Assumption 3, the expression of β in Theorem 3 can be simplified asβ(δ) = O C f + C v √ ρ log( n δ ) + γ(ρ; n) .Remark 2 can be observed by selecting M = ⌈n 1 q ⌉ in the expression of β(δ), which provides a straightforward presentation of the confidence interval width multiplier.The proof of Theorem 1 involves the Mercer representation of v in terms of ψ m . The expression of the prediction error |f (z) -fn (z)| is then decomposed into error terms corresponding to each ψ 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 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 on uncertainty estimates, we achieve a high probability bound-corresponding to the second term in the expression of β(δ). We then bound the remaining m > M elements based on the decay of Mercer eigenvalues-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. In the following section, we apply this theorem within the analysis of the infinite horizon average reward setting to obtain a no-regret algorithm. This is the first no-regret algorithm within this setting under general kernel-related assumptions.The weakest assumption regarding value functions is realizability, which suggests that the optimal value function v ⋆ either belong to the an RKHS or are at least well-approximated by its elements. In the degenerate case of bandits with |S| = 1, realizability alone is sufficient for provably efficient algorithms (Srinivas et al., 2010; Chowdhury and Gopalan, 2017; Vakili et al., 2021a) . However, for general MDPs, realizability is inadequate, necessitating stronger assumptions (Jin et 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:EQUATIONwhere β ∈ R and β > 0, ∥θ∥ < ∞, and Σ is an ∞ × ∞ matrix operator such that Σ ⪰ ρI for some ρ > 0, andϕ = [ϕ 1 , ϕ 2 , • • • ],where ϕ m = √ λ m φ m , and λ m and φ m are the Mercer eigenvalues and eigenfunctions corresponding to a kernel k defined on Z × Z. We assume V is a subset of the RKHS of a kernel k ′ defined on S × S. Assumption 4 (Optimistic Closure). For any v ∈ V, and for some positive constant C v , we have∥v∥ k ′ ≤ C v . Additionally, for v : S → [0, w], we assume C v = 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 strictly 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 1 for T steps. Under Assumptions 1, 2, 3, and 4, the regret of KUCB-RL, defined in Equation (2), satisfies, with probability at least 1 -δR(T ) = O T w + w + w √ ρ γ(T ; ρ) + log T δ ρT γ(T ; ρ) + ρ 2 w 2 γ(T ; ρ)γ(T /w; ρ) .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 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. 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 are provided in a 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 w is preferred to capture the long-term performance of the policy, but a larger w also increases the observation noise affecting the prediction error 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 ). We formalize the result with p-polynomial kernels in the following remark as it may be of broader interest. Remark 4. Under the setting of Theorem 3, with a p-polynomial kernel, with the choice of parameters, w = T p-1 4p+4 and ρ = T 1 p+1 , we obtain the following no-regret guarantee R(T ) = Õ(T 3p+5 4p+4 ).In the case of a Matérn kernel with smoothness parameter ν, where p = 1 + 2ν d , the regret bound translates to R(T) = O T 3ν+4d 4ν+4d. 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) . 
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 as Matérn 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 on a specific assumption about the scaling of kernel eigenvalues 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.Regarding optimality, we can juxtapose our results with the Ω(T ν+d 2ν+d ) lower bounds proven in (Scarlett 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 in the case of bandits. However, a no-regret Õ(T ν+2d 2ν+2d ) guarantee, though suboptimal, for standard acquisition-based algorithms like GP-UCB has been provided only recently (Whitehouse et al., 2024) . While we offer the first no-regret Õ(T 3ν+4d 4ν+4d ) guarantee in the much more complex setting of RL, we cannot determine whether our results are improvable. This remains an area for future investigation.Although RKHS elements of common kernels can approximate almost all continuous functions on compact subsets of R d (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 a 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] .Justification: The paper does not include experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
proof of theorem 1: 
 In this section, we provide a detailed proof the confidence bound given in Theorem 1.Let us use the notationEQUATIONandε i = v(s ′ i ) -f (z i ), ε n = [ε 1 , ε 2 , • • • , ε n ] ⊤ , f n = [f (z 1 ), f (z 2 ), • • • , f (z n )]⊤ . This allows us to rewrite the prediction error asEQUATION)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 1 (Proposition 1 in Vakili et al. (2021a) ). We haveσ 2 n (z) = sup f :∥f ∥ H ≤1 (f (z) -α ⊤ n (z)f n ) 2 + ρ ∥α n (z)∥ 2 ℓ 2 .Based on this lemma, the first term on the right hand side of ( 11) can be deterministically bounded byC f σ n (z) : |f (z) -α ⊤ n (z)f n | ≤ C f σ n (z).The challenging part in Equation ( 11) is the second term, which is the noise-dependent term α ⊤ n (z)ε n . Next, we provide a high probability bound on this term.We leverage the Mercer representation of v and write:v(s) = ∞ m=1 w m λ 1 2 m ψ m (s).We rewrite the observation vector v n as the sum of a noise term and the noise-free part f :EQUATION)Using this representation, we can rewrite the second term of (11) as followsn i=1 α i (z)ε i = n i=1 α i (z) ∞ m=1 w m λ 1 2 m ψ m (s ′ i ) - ∞ m=1 w m λ 1 2 m ψ m (z i ) = ∞ m=1 w m λ 1 2 m n i=1 α i (z) ψ m (s ′ i ) -ψ m (z i ) = M m=1 w m λ 1 2 m n i=1 α i (z) ψ m (s ′ i ) -ψ m (z i ) + ∞ m=M +1 w m λ 1 2 m n i=1 α i (z) ψ m (s ′ i ) -ψ m (z i ) .We decomposed the noise-related error term into an infinite series corresponding to each eigenfunction ψ m , m = 1, 2, • • • , and partitioned that into the first M elements and the rest. For each of the first M elements, we can apply the standard confidence intervals for kernel ridge regression. Specifically, Corollary 1 in Whitehouse et al. (2024) implies that, with probability at least 1 -δ/M , we haven i=1 α i (z)(ψ m (s ′ i ) -ψ m (z i )) ≤ ψ max σ n (z) √ ρ 2 log M δ det(I + ρ -1 K n ) 1 2.Summing up over the first M elements, and using a probability union bound, with probability at least 1 -δ, we haveM m=1 w m λ 1 2 m n i=1 α i (z)(ψ m (s ′ i ) -ψ m (z i )) ≤ M m=1 w m λ 1 2 m ψ max σ n (z) √ ρ 2 log M δ det(I + ρ -1 K n ) 1 2 ≤ ψ max σ n (z) √ ρ M m=1 w 2 m 1 2 M m=1 λ m 1 2 2 log M δ det(I + ρ -1 K n ) 1 2 ≤ C v ψ max σ n (z) √ ρ M m=1 λ m 1 2 2 log M δ det(I + ρ -1 K n ) 1 2, where the second inequality follows from the Cauchy-Schwarz inequality, and the third inequality follows from the bound ∥v∥H k ≤ C v .For the rest of the elements m > M , we have∞ m=M +1 w m λ 1 2 m n i=1 α i (z) ψ m (s ′ i ) -ψ m (z i ) ≤ 2ψ max ∞ m=M +1 w m λ 1 2 m n i=1 α i (z) ≤ 2ψ max ∞ m=M +1 w m λ 1 2 m n n i=1 α 2 i (z) 1 2 ≤ 2ψ max σ n (z) √ n √ ρ ∞ m=M +1 w m λ 1 2 m ≤ 2ψ max σ n (z) √ n √ ρ ∞ m=M +1 w 2 m 1 2 ∞ m=M +1 λ m 1 2 ≤ 2C v ψ max σ n (z) √ ρ n ∞ m=M +1 λ m 1 2.The first inequality holds by the definition of ψ max . The second inequality follows from the Cauchy-Schwarz inequality. The third inequality is derived using Lemma 1. The fourth inequality again applies the Cauchy-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 -δ,|f (z) -fn (z)| ≤ β(δ)σ n (z),whereβ(δ) = C f + C v ψ max √ ρ M m=1 λ m 1 2 2 log M δ det(I + ρ -1 K n ) 1 2 + 2C v ψ max √ ρ n ∞ m=M +1 λ m 1 2, that completes the proof.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 a 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, or as supplemental material. 
proof of theorem 3: 
 To analyze the performance of KUCB-RL, we first define an event E that all the confidence intervals used in the algorithm hold true.EQUATIONwhereβ(δ) = O w + w √ ρ log T δ + γ(T, ρ) .By Theorem 1, we have Pr[E] ≥ 1 -δ/2. We note the under Assumption 4, ∥v∥H k ′ ≤ C v = O(w).Also, for v : S → [0, w], we have ∥P v∥ H k = O(w). See Yeh et al. (2023) , Lemma 3, for a proof. Since v t is upper bounded by w by construction, we have ∥P v t ∥ = O(w) that replaces C f in the expression of β in Theorem 1.We condition the rest of the proof on event E.Consider t 0 such that (t 0 mod w) = 0 we bound the regret over window t ∈ [t 0 + 1, t 0 + w], denoted by R t0 (w). In addition let V ⋆ w (s) denote the optimum achievable total reward over a window of size w starting with initial state s, and V π w (s) denote the total reward over a window of size w achieved by KUCB-RL starting with initial state s.R t0 (w) = wJ ⋆ - t0+w t=t0+1 r(s t , a t ) = wJ ⋆ -V ⋆ w (s t0+1 ) + V ⋆ w (s t0+1 ) - t0+w t=t0+1 r(s t , a t ).For a bounded function v : S → R, we define its span as span(v) = sup s,s ′ ∈S |v(s) -v(s ′ )|.The first term is bounded by the span of v * .Lemma 2. For any s,|wJ ⋆ -V ⋆ w (s)| ≤ span(v * ).Proof follows the exact same lines as in the proof of Lemma 13 in Wei et al. (2021) .We next bound the second term in R t0 (w). We first prove that V ⋆ w (s) ≤ v t0 (s). Lemma 3. Under event E, we have V ⋆ w (s) ≤ v t0 (s), ∀s ∈ S.Proof. We can prove this by induction. Note that V ⋆ 0 (s) = v t0+w+1 (s) = 0. For any j ∈ [w], we haveV ⋆ j (s) -v t0+w+1-j = max a∈A Q ⋆ j (s, a) -max a ′ ∈A q t0+w+1-j (s, a ′ ) ≤ max a∈A {Q ⋆ j (s, a) -q t0+w+1-j (s, a)} = max a∈A {[P V ⋆ j+1 ](s, a) -[P v t0+w-j ](s, a)} = max a∈A {E s ′ ∼P (•|s,a) [V ⋆ j+1 (s ′ ) -v t0+w-j (s ′ )]} ≤ 0.The first inequality is due to rearrangement of max, and the second inequality is by the induction assumption. We thus have V ⋆ w (s) ≤ v t0 (s).We now bound the difference between v t0 (s t0+1 ) and sum of the reward over the window starting at step t 0 + 1:v t0+1 (s t0+1 ) -V π w (s t0+1 ). We note that v t0+w (s t0+w ) = V π 0 (s t0+w ) = 0 and v t0+j (s t0+j ) -V π w-j (s t0+j ) = q t0+j (s t0+j , a t0+j ) -Q π w-j (s t0+j , a t0+j ) ≤ [P v t0+j+1 ](s t0+j , a t0+j ) -[P V π w-j ](s t0+j , a t0+j ) + 2β(δ)σ t0 (s t0+j , a t0+j ) = v t0+j+1 (s t0+j+1 ) -V π w-j-1 (s t0+j+1 ) + 2β(δ)σ t0 (s t0+j , a t0+j ) + ([P v t0+j+1 ](s t0+j , a t0+j ) -v t0+j+1 (s t0+j+1 )) + V π w-j-1 (s t0+j+1 ) -[P V π w-j ](s t0+j , a t0+j ) .The inequality holds under event E. We obtained a recursive relationship for v t0+j (s t0+j ) -V π w-j (s t0+j ). Iterating over j = w to j = 1, we getv t0+1 (s t0+1 ) -V π w (s t0+1 ) ≤ t0+w t=t0+1 2β(δ)σ t0 (s t , a t ) + t0+w t=t0+1 ([P v t+1 ](s t , a t ) -v t+1 (s t+1 )) + t0+w t=t0+1 V π w+t0-t-1 (s t+1 ) -[P V π w+t0-t ](s t , a t ) .The second and third terms are zero mean martingales with a span of 2w, which are sub-Gaussian random variables with parameter w. Therefore, by Azuma-Hoeffding inequality (Lalley, 2013) , with probability at least 1 -δ/2, T t=1([P v t+1 ](s t , a t ) -v t+1 (s t+1 )) + T t=1 V π w+w⌊(t-1)/w⌋-t-1 (s t+1 ) -[P V π w+w⌊(t-1)/w⌋-t ](s t , a t ) ≤ w 2T log 2 δ .We note that for each t ∈ [T ], we can present the corresponding t 0 with t 0 = w⌊(t-1)/w⌋. Summing up the regret over all windows of size w up to time t, we have, with probability 1 -δ,EQUATIONIt thus remains to bound T t=1 σ w⌊(t-1)/w⌋ (z t ). The sum of sequential standard deviations of a kernel based model is often bounded using the following result from Srinivas et al. (2010) that is similar to the elliptical potential lemma in linear bandits (see, Abbasi-Yadkori et al., 2011) .EQUATIONThis result however is not directly applicable here due to the w⌊(t -1)/w⌋ subscript in σ w⌊(t-1)/w⌋ rather σ t-1 . A loose approach would be to partition the sequence into w sequences, each for one j ∈ [w] of the form σ w(i-1)+j , i = 1, 2, • • • T /w. For each of those sequences, ( 15) is applicable and we getEQUATIONUsing this bound we haveEQUATIONNext, we prove a stronger bound on T t=1 σ w⌊(t-1)/w⌋ (z t ) that contributes to the sublinear regret bounds in this paper.Lemma 4. For a sequence of observation points {z t } T t=1 and any w ∈ N, we haveEQUATIONProof 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 {z j } T j=1 , for any z and t ′ < t1 ≤ σ 2 t ′ (z) σ 2 t (z) ≤ 1 + t j=t ′ +1 σ 2 t ′ (z j ).We thus can writeT t=1 σ w⌊(t-1)/w⌋ (s t , a t ) ≤ T t=1 σ t (s t , a t ) 1 + t j=w⌊(t-1)/w⌋+1σ 2 w⌊(t-1)/w⌋ (s j , a j )EQUATIONThe first inequality is by Lemma 5, the second inequality follows from Cauchy-Schwarz inequality, and the last inequality is the bound established in Equation ( 17). This completes the proof of Lemma 4.Using Lemma 4, and substituting the value of β(δ) into ( 14), we obtainEQUATIONThe proof of the regret bound is complete.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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. Guidelines:• The answer NA means that the paper does not 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 runs 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). 
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 a compact metric space and µ be a finite Borel measure on Z (we consider Lebesgue measure in a Euclidean space). Let L 2 µ (Z) be the set of square-integrable functions on Z with respect to µ. We further say a kernel is square-integrable ifZ Z k 2 (z, z ′ ) dµ(z)dµ(z ′ ) < ∞.Theorem 5 (Mercer Theorem) . Let Z be a compact metric space and µ be a finite Borel measure on Z. Let k be a continuous and square-integrable kernel, inducing an integral operator T k :L 2 µ (Z) → L 2 µ (Z) defined by (T k f ) (•) = Z k(•, z ′ )f (z ′ ) dµ(z ′ ) ,where f ∈ L 2 µ (Z). Then, there exists a sequence of eigenvalue-eigenfeature pairs{(λ m , φ m )} ∞ m=1such that λ m > 0, and T k φ m = λ m φ m , for m ≥ 1. Moreover, the kernel function can be represented ask (z, z ′ ) = ∞ m=1 λ m φ m (z)φ m (z ′ ) ,where the convergence of the series holds uniformly on Z × Z.According to the Mercer representation theorem (e.g., see, Christmann and Steinwart, 2008, Theorem 4.51) , the RKHS induced by k can consequently be represented in terms of {(λ m , φ m )} ∞ m=1 . Theorem 6 (Mercer Representation Theorem) . Let {(λ m , φ m )} ∞ i=1 be the Mercer eigenvalue eigenfeature pairs. Then, the RKHS of k is given byH k = f (•) = ∞ m=1 w m λ 1 2 m φ m (•) : w m ∈ R, ∥f ∥ 2 H k := ∞ m=1 w 2 m < ∞ .Mercer representation theorem indicates that the scaled eigenfeatures { √ λ m φ m } ∞ m=1 form an orthonormal basis for H k . 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have reviewed the NeurIPS code of Ethics and ensured that we are in full compliance.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 RL 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.• 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 out 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 or unintentional) misuse of the technology. • If there are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.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 the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset'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/model 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 is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: 1)Can the results be improved to \sqrt{T} under uniform mixing conditions (which is a stronger assumption)?
limitations: limitations: N/A
paper_summary: paper_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$.
strength_weakness: strength_weakness: 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. 

2. 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.
questions: 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. 

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

2. 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: limitations: The limitations of this work have been explicitly addressed.
paper_summary: paper_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. 
The paper also proves a confidence interval bound for kernel ridge regression, which is of independent interest.
strength_weakness: strength_weakness: 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. 
It 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. 

Details 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.
questions: questions: M is not defined in the equation in line 291. Do you mean the equation holds for any natural number M?
limitations: limitations: A discussion of limitation is included.

Comments: title: Rebuttal by Authors - Part 2
comment: Thank you again for your thoughtful comments. We appreciate your contribution to the review process.
I appreciate the authors' thorough response to my concerns. Based on the rebuttal, I will raise my score to 6.
Thank you for your response.

Theorem 2 relies on Assumption 3 only through Remark 1. As discussed above, the adjustment to Assumption 3 does not affect the presentation of $\beta(\delta)$ in Remark 1, nor does it affect Theorem 2.

In Theorem 2, the first factor in the second term inside the $O$ notation represents $\beta(\delta)$. Specifically, $w + \frac{w}{\sqrt{\rho}} \sqrt{\gamma(\rho; T) + \log(T/\delta)}$ can be replaced by $\beta(\delta)$, offering a variation of the theorem with $\beta(\delta)$. This term matches the expression of $\beta(\delta)$ in Line 527, as pointed out by the reviewer.

The parameter $C_f$ in Theorem 1 denotes the upper bound on the RKHS norm of the target function $f$. Within the proof of Theorem 2, the target function is $Pv_t$. We substitute $C_f$ with $w$ because $||Pv_t||_{H_k} = O(w)$, given that $v_t$ is bounded by $w$ (due to the projection step onto $[0,w]$), and according to Lemma 3 of [42], that:

$||Pv||_{H_k} = O(span(v))$.

This is explained in Lines 530 and 531. Following your comment, we will add more details and reiterate this point in the main text.

Thank you for your engagement in the review process, which has significantly contributed to improving the paper. We appreciate your feedback and would be grateful if you could let us know if our response has clarified your question.
Thanks. I am convinced that this new version of Assumption 3 is implied by p-eigendecay with $p>1$, and the expression of $\beta(\delta)$ in remark 1 remains unchanged. However, since Theorem 2 also relies on Assumption 3, I am a bit concerned if this change in Assumption 3 affects the correctness of Theorem 2. Could you please clarify to what extent Theorem 2 relies on Assumption 3? In particular, is there a more general version of Theorem 2 that does not rely on Assumption 3 and has $\beta(\delta)$ in its regret bound?

Also, I notice that on line 527, the expression of beta used in the proof of Theorem 2 does not exactly match the expression of beta in remark 1 (one starts with $C_f$ and the other starts with $w$). Could you please clarify?
That is correct, and thank you for pointing it out. We overlooked this rather straightforward calculation. Here, we reexamine the entire calculation for clarity.

For Remark 1, we select $M$ with respect to $n$ such that the third term in $\beta(\delta)$ becomes only a constant. We have updated Assumption 3 as follows:

**Assumption 3** For kernel k′, we assume $\sum_{m=M+1}^{\infty}\lambda_m \le C_1M^{-\alpha}$ for constants $C_1, \alpha>0$, both independnet of $M$. 

This is a mild assumption. For instance, for the $p$-polynomial kernels defined in Definition 1, which apply to a large class of common kernels including SE, Matérn, and NT kernels, Assumption 3 is satisfied with $C_1=C/(p-1)$ and $\alpha=p-1$, where $C>0$ is the constant in Definition 1. 

Under this adjustment, to prove Remark 1, we choose $M=\lceil n^{1/\alpha}\rceil$. In the third term in $\beta(\delta)$, we have $n\sum_{m=M+1}^{\infty}\lambda_m\le C_1nM^{-\alpha}\le C_1$, thus the third term is only a constant. In the second term in $\beta(\delta)$ rather than $\log(\frac{n}{\delta})$ under square root, we have $\frac{1}{\alpha}\log(n)+\log(\frac{1}{\delta})$, where $\alpha$ is only a kernel specific constant independent of all other paramters $n, C_f, \delta, w, \rho$. 

We appreciate your feedback and would be grateful if you could please let us know if this adjustment and explanation address your question.
Thanks for your response. I have one more question: I am a bit confused if "$M\sum_{m=M+1}^\infty \lambda_m \leq C$ for any $M$" is the definition of Assumption 3, for two reasons:

First, $o(1)$ typically means a sequence converges to zero, while the definition you just gave only requires the sequence to be bounded. Did you intend to write $O(1)$ instead of $o(1)$ in Assumption 3?

Second, in the sentence after Assumption 3, you said that Assumption 3 is implied by p-polynomial eigendelay with $p> 1$, which I do not quite follow. 
By definition 1 of [35], p-polynomial eigendelay means $\lambda_m \leq C'*m^{-p}$ for some constant $C'$, so $M\sum_{m=M+1}^\infty \lambda_m$ has order $\Theta(M^{-p+2})$, which is bounded only when $p\geq 2$.
Thank you for your response to my comments. I have read them and am keeping my score.
Thanks for your detailed response. I am broadly satisfied by the rebuttal.
> 3. *The projection operator in Equation 5:* 

The analysis requires a confidence interval with diminishing width. In other words, we condition the proof on the validity of the confidence intervals with probability $1-\delta$, hence "... with probability at least $1 − \delta$ ..." in the statement of Theorem 2. We also show that the regret grows with the sum of the widths of confidence intervals over time. 

Projecting on $[0,w]$ maintains the validity of confidence intervals. It also does not affect the growth rate of the sum of the widths: $\sum_{t=1}^T\sigma_{\lfloor t/w\rfloor}(z_t)$ given that the uncertainties eventually diminish in a way that the confidence interval width $\beta(\delta)\sigma_{\lfloor t/w\rfloor}(z_t)$ becomes smaller than $w$. However, it significantly simplifies the proof by allowing us to use a uniform $w$ upper bound on noise over time, rather than dealing with noise terms of the power $\beta(\delta)\sigma_{\lfloor t/w\rfloor}(z_t)$ that could be larger than $w$ for small $t$.

In summary, although removing projections does not seem to affect the eventual rates, it can complicate the proof. We also note that the projection of the confidence intervals onto a priori known interval for the target function is a commonly used technique across RL literature [9, 10, 12, 23, 25, 29] and is not specific to our work.

We appreciate your detailed comments and constructive review. We would be happy to provide any further clarifications or engage in further discussions.