Reinforcement learning (RL) has shown empirical success in various real world settings with complex models and large state-action spaces. The existing analytical results, however, typically focus on settings with a small number of state-actions or simple models such as linearly modeled state-action value functions. To derive RL policies that efficiently handle large state-action spaces with more general value functions, some recent works have considered nonlinear function approximation using kernel ridge regression. We propose $\pi$-KRVI, an optimistic modification of least-squares value iteration, when the state-action value function is represented by a reproducing kernel Hilbert space (RKHS). We prove the first order-optimal regret guarantees under a general setting. Our results show a significant polynomial in the number of episodes improvement over the state of the art. In particular, with highly non-smooth kernels (such as Neural Tangent kernel or some Mat\'ern kernels) the existing results lead to trivial (superlinear in the number of episodes) regret bounds. We show a sublinear regret bound that is order optimal in the case of Mat\'ern kernels where a lower bound on regret is known.
Paper
Similar papers
Peer review
Summary
This work studies RL with kernel function approximation, specifically where it is assumed that the transition dynamics and reward function live in some RKHS. While there has been some work on RL with kernel function approximation, existing work provides bounds which are suboptimal. This work seeks to tighten these bounds, and ultimately obtains a bound scaling as $O(\sqrt{\Gamma(T) T})$ where $\Gamma(T)$ is the maximum information gain, matching the lower bound in certain settings of the bandit case. Their proposed algorithm is a variant of optimistic LSVI.
Strengths
1. The setting of kernel RL has not been studied as thoroughly as some areas of RL, and optimal bounds do not exist. This work takes a step in obtaining optimal regret, tightening the best-known existing bounds, and obtaining optimal regret in certain special cases (some bandit instances). However, I believe the stated result is incorrect—see below.
Weaknesses
1. I do not believe the stated result is correct. In the setting of linear bandits/linear MDPs/linear mixture MDPs, the information gain is bounded as $\Gamma_{k,\lambda}(T) \le O(d \log T)$, which would translate to a regret guarantee scaling as $O(\sqrt{d T})$. However, there are well-known lower bounds for these settings which scale as $\Omega(d \sqrt{T})$ (see e.g. [1] and [2]). Thus, the bound stated in this paper is better than the lower bound by a factor of $\sqrt{d}$, which is impossible. The following are less significant issues, but are also important to address: 2. There is a vast body of literature on RL beyond tabular and linear function approximation which is not referenced or discussed. See references [3-6] below for a start, and the works cited therein. This literature should be cited and discussed. 3. To make the results concrete, it would be helpful to instantiate Theorem 2 in the setting of tabular and linear MDPs. 4. The result is only provably optimal in the setting of bandits with Matern kernels. However, this paper considers deterministic rewards, so it doesn’t actually capture the bandit setting and as such does not handle the setting for the stated lower bound. It’s difficult, then, to make the claim that this result is optimal in any setting. I would suggest modifying the setting to allow for noisy rewards, or showing that there is a reduction from the current setting to the bandit setting (by encoding reward randomness in the transitions). 5. In addition, it would greatly strengthen the paper to show a lower bound for kernelized RL. 6. It was not clear to me what the $\eta$ parameter corresponded to or how it was defined. This should be clarified. 7. A reference or proof should be given for Lemma 1. [1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. "Nearly minimax optimal reinforcement learning for linear mixture markov decision processes." Conference on Learning Theory. PMLR, 2021. [2] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. [3] Du, Simon, et al. "Bilinear classes: A structural framework for provable generalization in rl." International Conference on Machine Learning. PMLR, 2021. [4] Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms." Advances in neural information processing systems 34 (2021): 13406-13418. [5] Foster, Dylan J., et al. "The statistical complexity of interactive decision making." arXiv preprint arXiv:2112.13487 (2021). [6] Zhong, Han, et al. "A posterior sampling framework for interactive decision making." arXiv preprint arXiv:2211.01962 (2022).
Questions
Please provide further clarification on the instantiation of the results to linear bandits/MDPs (see comment above).
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
1 poor
Presentation
2 fair
Contribution
2 fair
Limitations
Yes.
Summary
This paper proposes a reinforcement learning algorithm called $\pi$-KRVI that achieves order-optimal regret. The algorithm performs local kernelized optimistic least squares value iteration update - specifically, it partitions the state-action space so that each cell contains a small number of observations, and the Q value within a cell is updated to a Gaussian Process based Upper Confidence bound using observations in that cell only. This is motivated by KOVI [10] and $\pi$-GP-UCB [14]. A sublinear upper bound on the regret is given - this seems to be the first sublinear bound in a general setting, and it is claimed to be order optimal in the number of episode $T$.
Strengths
The sublinear regret seems to be the first one established in a general setting, and this seems to be order-optimal. The paper is generally clear, but a few things could be improved as mentioned in Weaknesses. The idea seem to be sound, but I didn't read the proofs.
Weaknesses
* The paper only informally refers to [19] when stating the bound is order optimal. This is not immediately clear due to differences in notations, and some ambiguity in the paper's discussion. A more precise and detailed discussion would be helpful. * It is not clear what ${\cal S}$ and ${\cal A}$ are, but it seems both are cubes? If yes, is this a necessary assumption? * The reward functions and transition distributions are assumed to have a norm $\le 1$. How will the regret change if the upper bound is larger than 1? * Lemma 1: $V$ is not used anywhere. Is it supposed to be $V_{h+1}$? If yes, an arbitrary $V_{h+}$ can potentially have a large norm, and Eq. (11) may not hold? A proof of the lemma seems to be missing. * Line 233: why is the target value constructed using a new random state $s_{h+1}'$, rather than the random state $s^{t}_{h+1}$ from the current episode? * Line 248: Does the running time refer to the total running time of Algorithm 1? If yes, can you explain why the upper bound is independent of the size of the partitions? Minor comments * Kernel ridge regression is generally described as a method that doesn't provide any uncertainty estimate, while the paper describes it as a method that provides uncertainty estimates. In particular, [38] is cited as the reference, but it doesn't seem to provide such an account of kernel ridge regression. What's described as kernel ridge regression is Gaussian process regression. * A brief explanation on the motivation behind maximum information gain would be helpful. * Putting the pseudocode of the algorithm in the paper would be helpful. Alternatively, provide a more complete description of the algorithm. * Algorithm 1, line 10: $x_{h}^{t}$ should be $s_{h}^{t}$?
Questions
I would appreciate a discussion on the weaknesses before minor comments.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
A discussion on the limitation of Assumption 1 would be beneficial.
Summary
This paper presents an optimism-based online learning algorithm for RL with large state-action spaces (including continuous spaces). It proposes a (Gaussian) kernel-based function approximation + optimism (building on UCBVI) algorithm. It assumes that the reward and transition density functions are representable in 1-bal of an RKHS (with a Gaussian kernel), which is quite reasonable. It also introduces a domain-partitioning technique to make the kernel ridge regression part scalable. The regret bound obtained for the algorithm is shown to be an improvement over SOTA [10]. Specifically, regret scales H^2 and sublinear in T.
Strengths
Online RL algorithms for continuous state and action spaces is a really challenging problem, and until recently was unresolved. This is the best such result I have seen. It makes a very smart (and now seemingly natural) use of kernel-based function approximation.
Weaknesses
The authors have not presented any numerical results. So it leaves one wondering whether it is all nice theory, and there is some hope of the making the algorithms practical. Note: Title has a typo for Kernelized".
Questions
1. Could you present some numerical studies so we can understand the strength of your algorithm? It could even be large tabular but difficult problems such as DeepSea and Montezuma's revenge.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
Kernel-based method may limit scalability.
Summary
This paper theoretically studies the performance of a reinforcement learning algorithm under the assumption that the Q function is a member of RKHS with a known kernel. The authors provide cumulative regret bound on the iterative-least value iteration algorithm and specialise their results to the kernel with polynomial decay of eigenvalues. They improve the regret bounds of prior works by refined analysis of confidence sets in this non-parametric setting.
Strengths
The paper is clearly written in the context of its rather technical nature. The work combines the newest understanding of adaptive confidence sets and their analysis for the case of Matern kernels with Linear MDPs, by providing a kernelized variant of thereof. I am not familiar with the other literature utilising the novel variants of the analysis in the context of RL. Seems like there is a sub-community interested in this issue given the COLT open problem, however, as somebody not in this community, I have to say it seems certainly a matter of taste rather than importance.
Weaknesses
The prior work, [10] indeed does not provide optimal bounds, but arguably the algorithm seems to be more practical than a rather time-varying discretization of the domain in order to facilitate the construction of the order optimal confidence sets. To be slightly harsh I wonder if the proper academic solution would not have been informing the authors of [10] of this new technique rather than writing a wholly new paper which utilises the trick with the domain splitting which comes from other prior works e.g. [14]. At the expense of creating more elaborate confidence sets one can indeed improve the bounds, but whether this improves the performance remains unanswered in this paper, as no comparison is provided. The proposed contribution is solely of theoretical nature. It is common in online learning to use the doubling trick and mention it in passing in case improved results are desired. I wonder if this is not a similar discretization trick, and whether this deserves an independent publication at NeurISP.
Questions
- Mercer decomposition diagonalize the infinite dimensional operator either under a specific distribution or on a bounded domain (essentially uniform distribution), could you be more specific what you mean by the Mercer decomposition in Section 2.2 - Why is there H^2 in the regret bounds? What is the nature of this? One "H" would be more intutivie. - How are quantities Infogain and covering numbers related? - Does one also need info-gain to derive the bound? Clearly there are bound with only the info-gain, can there be only covering number bounds? I wonder if works by van der Geer on high dimensional statistics are related to this. - Covering numbers for Sobolev paper are well-studied objects in functional analysis, especially due to seminal paper of field’s medalist Smale. I suggest looking into ref in publications of this author.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
None identified.
response
Thank you for your responses. I liked the clarifications. - Are you the first work to discuss the covering approach for order-optimal confidence sets? - [10] sets covering using 1/N instead of 1/\sqrt{N}. What would their bounds be if they used your discretization with 1/\sqrt{N}? However, there is still a fundamental disagreement in terms of contribution. I feel like you use a trick from paper A [and arguably polish the analysis a bit] to apply in a setting of paper B, where they use it as a tool, to get a *theoretically* better algorithm at the expanse of being more difficult to implement. It is not the same method as in [10] since the confidence construction is more elaborate. If A and B were completely different fields, I would be fine with this setup, but this essentially the same field. I do not find this surprising that one can use these techniques in the RL context compared to Bandits. These improved confidence sets can be applied and improve the bounds anywhere they need. I am not saying your work does not deserve audience, but, the following description still were accurately characterizes my general opinion of this paper: "Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation." I do not share the viewpoint of the other reviewer who claims some lower bounds are contradicted. I think the results are believable but I did not check the maths. They are especially believable since somebody already did near identical analysis before in a different context.
We greatly appreciate your participation in the discussion. Regarding the questions: - The use of a covering set to establish confidence intervals applicable to all members of a function class is a requirement imposed by the MDP framework. The target function $r_h+[P_h V_{h+1}^{t}]$ is not fixed and determined; it depends on $V_{h+1}^{t}$due to the temporal dependence in the MDP setting. The utilization of a covering set is also employed in the most related work [10]. However, in establishing our confidence intervals, we allow flexibility in choosing the parameter of the covering set, which ultimately contributes to improved regret bounds with an appropriate parameter selection. - The proof in [10] does not provide flexibility in choosing the parameter of the covering set. So we cannot directly observe the answer to your question by setting $\epsilon^*$ (in their notation) in their Theorem 4.2 proportional to $1/\sqrt{t}$, where $t$ is the episode number. However, we can see that the regret bound would at least scale with $O(\Gamma(T)\sqrt{T})$. The reason for this is that the confidence interval width would at least scale with $\sqrt{\Gamma(T)}$, and following the rest of the proof of [10] (which is independent of $\epsilon^*$) leads to a regret bound scaling at least with $O(\Gamma(T)\sqrt{T})$. We agree with the reviewer that our improved and order optimal regret bounds come at the price of a more sophisticated algorithm. However, we still believe that our results are significant and of interest to the wider research community for several reasons. There is a broad interest in RL and its analysis. We provide the first order-optimal regret bounds in the kernel-based RL setting for a broad class of common kernels. The SOTA fails to show even sublinear regret bounds. Our results are not achieved by simply applying a technique from [14] to [10]. Although, we agree that our work is highly inspired by [10] and [14], and we have acknowledged this throughout the paper. Specifically, even in the much simpler problem of kernel bandits, [14] obtained sub-optimal regret bounds of $\tilde{O}(T^{(d(2d+3)+2\nu)/(d(2d+4)+4\nu)})$, while we obtain optimal regret bounds of $\tilde{O}(T^{(\nu+d)/(2\nu+d)})$. This is achieved based on the merit of our Lemma 2, which provides a tighter bound on information gain than the one used in [14], and subsequent improvements to the algorithm and its analysis. Also, we would like to address the comment in the review that states "*These improved confidence sets can be applied and improve the bounds anywhere they need*." This statement is not entirely accurate. We would like to emphasize that the algorithm and domain partitioning are closely intertwined. Domain partitioning alone cannot be used to achieve tighter confidence intervals in general. Instead, a careful and elaborate algorithm that leverages domain partitioning is required to improve the regret bounds. This observation is also highlighted in the recent work of [Lattimore, COLT'23] on the kernel-based confidence intervals, where it is stated that "... any analysis of linear contextual bandits aimed at proving a similar result [order optimal regret bounds] cannot completely decouple the concentration analysis and the algorithm. The same is true for kernelised bandits where the dimension-dependence arising from loose confidence bounds is especially pernicious and can be the difference between sublinear and linear regret". Tor Lattimore, "A Lower Bound for Linear and Kernel Regression with Adaptive Covariates'', COLT 2023. We hope that these further clarifications improve the reviewer's evaluation of the paper.
Reply to rebuttal
I would like to thank the authors for their detailed response. I had a few follow-up questions: 1. Could the authors point me to the specific line in the proof where the factor of $d$ is hidden? 4. I agree that considering stochastic rewards should not change the results, and that it is often possible to embed a bandit in a 1-step RL problem with deterministic reward by encoding the bandit reward noise into the stochastic transition. As such, I agree with the authors that it's not unreasonable to compare with the bandit lower bound even when considering deterministic rewards. However, I do think this should be mentioned explicitly in the discussion around equation (22) (or the embedding of bandits into 1-step RL problems with deterministic rewards made explicit).
Response to follow up questions
We greatly value the reviewer's engagement and helpful comments. In response to follow up questions: 1. Regarding the input dimension $d$: The constatns in front of both the information gain and the logarithm of the covering number scale with $d$. Consequently, the confidence interval width multiplier $\beta_h^t(\delta, \epsilon)$, as given in Equation (19)), also increases with $d$. This leads to the constants in regret bound increasing with $d$. The growth of constants in both the information gain and the logarithm of the covering number is attributed to the constants in the kernel's spectrum increasing with $d$. Specifically, within the proof of Lemmas 2 and 3, these constants scale with $d$ (in Equations (39), (47) and the subsequent one, and (52) and the one follwoing). In proof of Theorem 2, this scaling impacts the constant in Equation (59) and the implied constant, in $\Theta$ notation, in Equation (60). That carries to the constant in Equation (65), which appears in the final regret bounds. We wish to highlight that hiding constants dependent on $d$ is not a peculiarity of our presentation. Such a practice is commonplace in all kernel bandits and RL papers we are familiar with, as evident by well-cited papers such as [10, 14, 16, 20, 21, 22, 31, 40, 44, 45]. In this line of work, the primary focus has been on the regret growth with $T$, stiving for sublinear and, ideally, order-optimal regret bounds in $T$, that has overshadowed attention to $d$. Prompted by the reviewer's comment, we will include a more detailed explanation and clearer discussion on this point in the final version. 2. We completely agree with this comment. We will elaborate on this point in the final version of the paper. Specifically, we will clarify that adding observation noise to rewards does not affect the order of regret bounds presented. Therefore, we can compare our results to the noisy bandits, as in [10], without any loss of generality. We appreciate the reviewer's constructive feedback. We are confident that incorporating these discussions will enrich our exposition, further improving the quality of our paper.
Response
I spent some time going through the proof more carefully and agree with the authors comments. As such, I will increase my score accordingly. I would strongly encourage the authors to make this more transparent, however. In particular, there are other terms hidden in absolute constants and big-O notation (such as $C_p$), which is only mentioned deep in the proofs. The big-O notation should be formally defined so it is obvious from reading the text in the main body what is being hidden.
Thank you. We greatly appreciate your participation in the discussion and the valuable feedback. We will include the aforementioned discussions on noisy rewards, as well as dependence of constants on $d$ and $p$, and the connection to linear case in the final version. These additions will strengthen the overall quality of the paper.
Decision
Accept (poster)