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

Thank you for reviewing our paper. We appreciate your positive feedback on the strength of the results. Here, we address your comments in detail and hope this will enhance your evaluation of the paper.

The use of $O$ notation:

As mentioned by the reviewer all of our proofs are non-asymptotic and our use of $O$ notation, which is common practice in the literature, serves to simplify presentations. Theorem 1 does not use $O$ notation. We will revise the statement of Assumption 3 to read: "...$M\sum_{m=M+1}^{\infty}\lambda_m\le C$, for any $M\in\mathbb{N}$ and some constant $C>0$ independet of $M$." We will also clarify the statement of Theorem 2 by introducing an absolute constant independent of all parameters: $T,w, \rho, \delta$. We are ultimately interested in scaling with $T$ after $w$ and $\rho$ are selected optimally with respect to $T$, as given in Remark 2, which we will further clarify.

References for bounds on information gain

Thank you for pointing out the missing references for maximum information gain. The bound for the linear case is given in [22]. Further discussions and tight bounds for kernels with exponential and polynomial eigenvalue decay are provided in [35]. We will ensure these references are properly included.

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

Yes, the statement holds for any natural number $M$. We will clarify this point in the revision.

For further details on the role of this $M$ in the analysis, please see our response to Reviewer KBUd. Additionally, a simplified presentation of the confidence interval is given in Remark 1, where $M$ is removed.

We would be happy to provide further clarifications on any of these points.

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?

Thank you for your detailed review of our paper. We appreciate your positive feedback regarding the generality of our setting and results, as well as the potential independent interest in the confidence bounds. We will address your comments and questions in detail, hoping this will enhance your evaluation of the paper.

Computational complexity:

Kernel-based models provide powerful and verstile nonlinear function approximations and lend themselves to theoretical analysis. It is, however, well-known that kernel ridge regression has a relatively high computational complexity, primarily due the matrix inversion step. This challenge is not unique to our work and is common across kernel-based supervised learning, bandit, and RL literature. Luckily, sparse approximation methods such as Sparse Variational Gaussian Processes (SVGP) or the Nyström method significantly reduce the computational complexity (to as low as linear in some cases), while maintaining the kernel-based confidence intervals and, consequently, the eventual rates; e.g., see Vakili et al. ICML'22 and references therein. These results are, however, generally applicable and not specific to our problem. We thus preferred to avoid further complicating the notation and presentation of an already notation-heavy RL setting to focus on our main results and contributions specific to this paper.

``Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning'', Vakili, Scarlett, Shiu, Bernacchia, ICML 2022.

Additionally, as a minor point, the matrix inversion step is required only every other $w$ steps, in contrast to every step, which further improves computational complexity. We will add these discussions to the revision.

1. maximum information gain:

This is a kernel-specific quantity that captures the complexity of kernel-based learning. It is a common measure in the literature on kernel-based bandits [22, 23, 24, 36, 27] and RL [12, 25, 26]. As defined in Section 2.5, the value of $\gamma$ depends only on the kernel and the free parameter $\rho$. The algorithm itself does not aim to maximize information gain; rather, it is an algorithm-independent and kernel-specific complexity term that appears in the regret bound. Intuitively, $\gamma$ captures the complexity of the function class. Under a linear assumption, $\gamma=O(d\log(T))$. For kernels with exponentially decaying eigenvalues $\gamma=O(poly\log(T))$, and for kernels with polynomially decaying eigenvalues, such as the Matérn family and Neural Tangent kernels, the bound on $\gamma$ is given in Section 2.5. For proofs of these bounds, see [22, 35].

2. Reseting and back calculation of the value function on a window with size $w$:

We here address this question along with the related observations from the "Weaknesses" section and the subsequent discussion on the tradeoff in choosing $w$ from the next question. We understand the reviewer's comments to be highlighting two specific aspects of our algorithm and analysis.

First aspect: For kernel ridge regression on $[P v_{t+1}]$, we only use observations up to $t_0$, where $(t_0 \mod w) = 0$ and $t_0+1 \le t \le t_0+w$. This might seem data inefficient as it does not utilize the $t-t_0 \le w$ samples:

We address this in our analysis. After Theorem 2, which presents the performance of the algorithm, it is noted: "Algorithm 1 updates the observation set every $w$ steps, requiring us to characterize and bound the effect of this delay in the proof. A straightforward application of the elliptical potential lemma results in loose bounds that do not guarantee no-regret. We establish a tighter bound on this term, contributing to the improved regret bounds." In particular, we show that this delay in updating the observation set does not change the eventual rates. The proof, based on Lemma 4, is detailed in lines 555 - 565 in the appendix. The key idea in the proof is to bound the ratio between a delayed uncertainty estimate update and a non-delayed one, followed by some arithmetic manipulation.

Second aspect: Regarding the window’s role (i.e., setting the value function to $0$ at the end of the window, backtracking to compute the proxy value function over the window, and unrolling the policy in a forward direction over the window), there is an apparent tradeoff in choosing the window size:

This tradeoff balances between the strength of the value function and the strength of the noise. A longer window is preferred to capture the long-term performance of the policy, while a larger window increases the observation noise affecting the kernel ridge regression. We recall that both target function $[Pv_{t+1}]$ and observation noise $v_t-[Pv_{t+1}]$ are bounded by $w$. This tradeoff is explicitly seen in the regret bounds. The optimal size of the window, as specified in line 335, results from an optimal interplay between these two factors, which is explicitly captured in the regret bounds.

We appreciate this discussion and believe that the inclusion of these points will enhance the paper. Please let us know if any further clarifications are needed regarding these aspects.

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.

Thank you for reviewing our paper. We appreciate your positive feedback.

Following your comment, we will enhance the main text with more detailed technical content. We have provided a proof sketch in the paragraph following Remark 1, which we will expand to further detail the proof of Theorem 1.

Unlike typical settings such as (supervised) kernel ridge regression or kernel-based bandit settings [22, 23, 24, 36, 37, 24], in the RL setting, confidence intervals are applied to $f_t = [P v_{t+1}]$, which varies due to the Markovian nature of temporal dynamics, with each $v_t$ derived recursively from $v_{t+1}$. Hence, the confidence interval must be applicable to all functions $v$ in a function class. This requirement is captured in the theorem: "For all $z \in Z$ and $v: ||v||_{H_k'} \le C_v$, the following holds ...". To achieve such confidence intervals, we use a novel technique by leveraging the Mercer representation of $v$ and decomposing the prediction error $|f(z) - \hat{f}_n(z)|$ into error terms corresponding to each Mercer eigenfunction $\psi_m$. We then partition these terms into the first $M$ elements corresponding to eigenfunctions with the largest $M$ eigenvalues and the rest. For each of these $M$ eigenfunctions, we obtain high probability bounds using existing confidence intervals from [24]. Summing up over $m$, and using a bound based on uncertainty estimates, we achieve the high probability bound—corresponding to the second term in $\beta(\delta)$, and bound the remaining elements based on the eigendecay—corresponding to the third term in $\beta(\delta)$.

In summary, the key technical novelties in deriving the concentration bound involve leveraging the Mercer decomposition of $v$ and the error term, partitioning the decomposition into the first $M$ elements and the rest, bounding each of the first $M$ elements using exisitng kernel-based confidence intervals, bounding the rest based on eigendecay, and then summing up over all $m$ to derive the confidence interval.

We emphasize that this is a substantial result that can be applied across various RL problems.

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

As noted in the introduction, [20] achieved a regret bound of $\tilde{O}(\frac{1}{\sigma}\sqrt{t_{mix}^3 T})$ under the linear bias function assumption, where $\sigma$ is the smallest eigenvalue of the policy-weighted covariance matrix. While assuming a strictly positive smallest eigenvalue (independnt of $T$) for the covariance matrix is reasonable in a finite-dimensional setting where $d \ll T$, it becomes unrealistic in the kernel setting. This presents significant challenges in adapting the existing results to the kernel setting. It is not clear whether tighter results can be achieved under uniform mixing conditions, necessitating further research.

Please let us know if any further clarifications on these points are required.

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