Library

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

Reinforcement learning 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.

cs.LGcs.AIstat.MLComputer ScienceMathematics
Source

Paper

Similar papers

Kernelized Reinforcement Learning with Order Optimal Regret BoundsSattar Vakili, Julia Olkhovskaya2023 · Neural Information Processing Systems · 21 citations In Library
Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement LearningSattar Vakili2024 · arXiv (Cornell University) · 2 citations In Library
Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement LearningSayak Ray Chowdhury, Rafael Oliveira2020 · Asian Conference on Machine Learning · 6 citations In Library
On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State SpacesZhuoran Yang, Chi Jin, Zhaoran Wang et al.2020 · arXiv (Cornell University) · 18 citations In Library
Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement LearningAya Kayal, Sattar Vakili, Laura Toni et al.2025 · arXiv (Cornell University) · 1 citation In Library
On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov GameShuang Qiu, Jieping Ye, Zhaoran Wang et al.2021 · arXiv (Cornell University) · 27 citations In Library
Kernel-Based Reinforcement Learning: A Finite-Time AnalysisO. D. Domingues, Pierre Ménard, Matteo Pirotta et al.2020 · International Conference on Machine Learning · 29 citations In Library
Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function ApproximationYue Wu, Dongruo Zhou, Quanquan Gu2021 · arXiv (Cornell University) · 24 citations In Library
Kernel-Based Reinforcement Learning: A Finite-Time AnalysisOmar Domingues, Pierre Ménard, Matteo Pirotta et al.2021 · HAL (Le Centre pour la Communication Scientifique Directe) In Library
RL as Regressor: A Reinforcement Learning Approach for Function ApproximationYongchao Huang2025 · arXiv (Cornell University) · 0 citations In Library

Peer review

Accept (poster)NeurIPS 2024 · via OpenReview
Reviewer unzJ6/10 · confidence 2/52024-07-12

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.

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

M is not defined in the equation in line 291. Do you mean the equation holds for any natural number M?

Rating

6

Confidence

2

Soundness

2

Presentation

3

Contribution

3

Limitations

A discussion of limitation is included.

Reviewer unzJ2024-08-12

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?

Authorsrebuttal2024-08-13

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.

Reviewer unzJ2024-08-13

I appreciate the authors' thorough response to my concerns. Based on the rebuttal, I will raise my score to 6.

Authorsrebuttal2024-08-14

Thank you again for your thoughtful comments. We appreciate your contribution to the review process.

Reviewer pN555/10 · confidence 2/52024-07-16

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

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

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?

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

3

Limitations

The limitations of this work have been explicitly addressed.

Authorsrebuttal2024-08-06

Rebuttal by Authors - Part 2

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

Reviewer KBUd7/10 · confidence 2/52024-07-18

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.

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.

Questions

1)Can the results be improved to \sqrt{T} under uniform mixing conditions (which is a stronger assumption)?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Reviewer KBUd2024-08-11

Thanks for your detailed response. I am broadly satisfied by the rebuttal.

Reviewer unzJ2024-08-12

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

Authorsrebuttal2024-08-12

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.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC