Sampling Complexity of TD and PPO in RKHS

## Abstract

Abstract We revisit Proximal Policy Optimization (PPO) from a function-space perspective.
Our analysis decouples policy evaluation and improvement in a reproducing kernel Hilbert space (RKHS):
(i) A kernelized temporal-difference (TD) critic performs efficient RKHS-gradient updates using only one-step state–action transition samples.
(ii) a KL-regularized, natural-gradient policy step exponentiates the evaluated action-value, recovering a PPO/TRPO-style proximal update in continuous state-action spaces.
We provide non-asymptotic, instance-adaptive guarantees whose rates depend on RKHS entropy, unifying tabular, linear, Sobolev, Gaussian, and Neural Tangent Kernel (NTK) regimes, and we derive a sampling rule for the proximal update that ensures the optimal k − 1 / 2 k^{-1/2} convergence rate for stochastic optimization.
Empirically, the theory-aligned schedule improves stability and sample efficiency on common control tasks (e.g., CartPole, Acrobot), while our TD-based critic attains favorable throughput versus a GAE baseline.
Altogether, our results place PPO on a firmer theoretical footing beyond finite-dimensional assumptions and clarify when RKHS-proximal updates with kernel-TD critics yield global policy improvement with practical efficiency.

## 1 Introduction

Policy-gradient and trust-region methods (e.g., natural policy gradient (NPG) (Kakade, 2001), trust-region policy optimization (TRPO) (Schulman et al., 2015), proximal policy optimization (PPO) (Schulman et al., 2017), and actor–critic (AC) methods (Konda & Tsitsiklis, 1999)), when coupled with temporal-difference (TD) critics, are among the most effective tools in modern RL for large, continuous control, thanks to their compatibility with expressive function approximators and stable improvement steps.
Yet despite impressive empirical success, our theoretical understanding of global convergence for these algorithms under expressive function approximation remains fragmented across settings.
In particular, a central problem is to design an algorithm that (i) performs policy evaluation with controlled statistical error when the action–value function lies in a rich function class, and (ii) couples this evaluation step with a policy improvement update that provably ascends toward the optimal policy.

Existing analyses often establish convergence only in tabular/linear regimes or under strong realizability and concentrability conditions, see, e.g., (Agarwal et al., 2020; Bhandari & Russo, 2024). With nonlinear or nonparametric critics, guarantees frequently rely on idealized, exact value/advantage estimates. Moreover, many policy-improvement bounds treat expectation terms as if computed without sampling noise, leaving the per-iteration data requirements for ensured improvement unspecified.

For TD learning (Sutton, 1988; Maei et al., 2009; Bhandari et al., 2018), linear TD is well understood, with asymptotic convergence and finite-time error bounds. By contrast, theory under nonlinear approximation is thinner. A key advance is (Cai et al., 2019), which establishes finite-sample convergence of neural TD under overparameterized networks with discrete actions (and continuous states) at a sublinear rate. On the policy-optimization side, the strongest results remain in tabular or linear settings; with expressive function classes, guarantees weaken. Notably, (Liu et al., 2019) prove nonasymptotic global convergence of mirror descent policy optimization for two-layer overparameterized neural policies in continuous-state, discrete-action problems under the neural tangent regime.

In this paper, we take a function-space approach and optimize policies in a RKHS, which encompasses tabular/linear models, Sobolev classes, Gaussian kernels, and wide neural networks through their neural tangent kernels. We study policy evaluation and improvement using gradient-based updates: (i) a kernel TD critic–distinct from least-squares TD–that implements an RKHS-gradient iteration acting as an implicit preconditioner and avoids cubic-time matrix inversions, and (ii) a KL-regularized functional proximal step for policy improvement, implementable in continuous action spaces, where the policy is updated by exponentiating the evaluator’s value estimate.
Our main contributions are:

- •
We introduce a kernel, gradient-based TD evaluator in an RKHS that acts as an implicit preconditioner and attains geometric convergence without costly matrix inversions.
The evaluator uses one-step samples (no trajectory rollouts) and comes with non-asymptotic TD-error bounds that match the minimax rate (up to logarithms).
- •
We design a KL-regularized proximal update implementable in continuous action spaces. We explicitly quantify the per-iteration sample size needed to achieve the intended improvement, addressing a common gap where policy expectations are treated as exact or left unspecified.
- •
Because kernel gradient descent mirrors the NTK dynamics of wide networks trained by gradient descent, our RKHS analysis directly informs neural critics/actors in the corresponding regimes. Experiments on continuous-control benchmarks exhibit the trends predicted by our theory.

## 2 Related Studies

TD method (Sutton, 1988) is one of the most commonly used for policy evaluation. The convergence of linear TD has been extensively studied, with finite-time error bounds established in recent works (Bhandari et al., 2018; Lakshminarayanan & Szepesvari, 2018; Srikant & Ying, 2019). In contrast, the behavior of TD with nonlinear function approximation remains less understood. A notable advance is due to Cai et al. (2019), who provided the first finite-sample analysis of neural TD, proving sublinear convergence under an overparameterized network; see also Brandfonbrener & Bruna (2019); Agazzi & Lu (2019) for related results in tabular settings.

Policy optimization has also been extensively studied, with algorithms including policy gradient (PG) (Sutton et al., 1999; Baxter & Bartlett, 2000), natural policy gradient (NPG) (Kakade, 2001), trust-region policy optimization (TRPO) (Schulman et al., 2015), proximal policy optimization (PPO) (Schulman et al., 2017), and actor–critic (AC) methods (Konda & Tsitsiklis, 1999). Among these, NPG has been analyzed most thoroughly. Its convergence is well understood in the tabular setting, while function approximation presents additional challenges (Bhandari & Russo, 2024; Cen et al., 2022; Mei et al., 2020). For linear approximation, Agarwal et al. (2020) established global convergence in tabular setting and restricted class of parametric
policies, Agarwal et al. (2021) derived finite-sample rates for unregularized NPG with softmax parameterization. In more general settings, Zhang et al. (2020) obtained only local guarantees, and Cayci et al. (2024) provided sharp nonasymptotic bounds for entropy-regularized NPG. Broader classes of function approximation, including neural networks, have also been considered (Wang et al., 2019; Liu et al., 2019). TRPO and PPO have likewise received theoretical attention: Neu et al. (2017) and Shani et al. (2020) analyzed TRPO, while Liu et al. (2019) and Cai et al. (2020) studied PPO and its variant.

Our work is closely related to kernel methods (Hofmann et al., 2008; Zhou, 2008; Cho & Saul, 2009), which is one of the commonly used approaches in policy learning, e.g., Bagnell & Schneider (2003); Bethke et al. (2008); Grunewalder et al. (2012); Feng et al. (2020); Koppel et al. (2020). Early work e.g., Ormoneit & Sen (2002); Munos & Szepesvári (2008), established consistency results for non-parametric value function approximation. More refined analyses were later provided by Farahmand et al. (2016), who studied the convergence of the Bellman contraction mapping under the non-parametric setting, and by Duan et al. (2024), who proposed a regularized kernel-based LSTD estimator in RKHS for Markov chains independent of actions, deriving non-asymptotic error bound and establishing matching minimax lower bound.

## 3 Preliminaries

Markov Decision Process. We consider the MDP $(\mathcal{S},\mathcal{A},P,r,\gamma)$, where $\mathcal{S}\subset\mathbb{R}^{d_{2}}$ and $\mathcal{A}\subset\mathbb{R}^{d_{a}}$ are compact and convex sets, $P:\mathcal{S}\times\mathcal{A}\to\mathcal{P}(\mathcal{S})$ is the transition kernel for any state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$ to the space of distribution on $\mathcal{S}$ denoted as $\mathcal{P}(\mathcal{S})$, $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is the reward function, and $\gamma\in[0,1]$ is the discount factor. These yields a Markov chain $(s_{0},a_{0},s_{1},a_{1},\cdots)$.

The performance of a policy $\pi:\mathcal{S}\to\mathcal{P}(\mathcal{A})$ is evaluated by the following value function:

$$ $V^{\pi}(s)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\big|s_{0}=s,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim P(\cdot|s_{t},a_{t})],$ (1) $$

and the action-value function (Q-function):

$$ $\displaystyle Q^{\pi}(s,a)=$ $\displaystyle\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\big|s_{0}=s,a_{0}=a,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim P(\cdot|s_{t},a_{t})].$ (2) $$

The corresponding advantage function $A^{\pi}(s,a)$ is define as $A^{\pi}(s,a)=Q^{\pi}(s,a)-V^{\pi}(s)$. In this study, we will focus on learning the Q-function. To this end, we define the Bellman evaluation operator:

$$ $\mathcal{T}[Q^{\pi}](s,a)=r(s,a)+\gamma\mathbb{E}_{a^{\prime}\sim\pi(\cdot|s^{\prime}),s^{\prime}\sim P(s^{\prime}|s,a)}[Q^{\pi}(s^{\prime},a^{\prime})],$ (3) $$

for which $Q^{\pi}$ is the fixed point of the operator: $Q^{\pi}=\mathcal{T}Q$.

We let $\sigma^{\pi}_{\mu}(s,a)=\pi(a|s)\mu(s)$ denote the action-state distribution associated to policy $\pi$. Let $\nu^{*}$ denote the stationary state distribution of the Markov chain given the optimal policy $\pi^{*}$ and let $\sigma^{*}(s,a)=\pi^{*}(a|s)\nu^{*}(s)$ denote the stationary state-action distribution. When given a policy $\pi$, we first sample $n$ initial samples from a pre-determined initial distribution $\mu_{0}$. We have the following assumption on $\sigma_{0}^{\pi}=\pi\mu_{0}$ and $\sigma^{*}$.

###### Assumption 1 .

Distributions $C_{1}\geq\sigma^{*}\geq c_{1}$ and $C_{2}\geq\sigma^{\pi}_{0}\geq c_{2}$ are bounded.

Assumption [1](https://arxiv.org/html/2509.24991v1#Thmtheorem1) implied that $\sigma^{*}$ and $\sigma^{\pi}_{0}$ are neither overly concentrated nor sparse. This condition is crucial because such distributions would cause numerical difficulties during their evaluation.

RKHS. Define $\omega=(s,a)\in\mathcal{S}\times\mathcal{A}$. We assume the Q-function $Q$ associated with a policy $\pi$ lies in $\mathcal{H}(\mathcal{S}\times\mathcal{A})$ where $\mathcal{H}$ is a RKHS induced by a symmetric positive definite kernel $K:(\mathcal{S}\times\mathcal{A})\times(\mathcal{S}\times\mathcal{A})\to\mathbb{R}$. Using kernel $K$, we define the linear space of functions on $\mathcal{S}\times\mathcal{A}$ as follows:

$$ $\hat{\mathcal{H}}=\{\sum_{i=1}^{n}b_{i}K(\omega_{i},\cdot),b_{i}\in\mathbb{R},\omega_{i}\in\mathcal{S}\times\mathcal{A}\}$ $$

and it is equipped this space with the bilinear form

$$ $\langle\sum_{i=1}^{n}b_{i}K(\omega_{i},\cdot),\sum_{i=1}^{n}c_{i}K(\omega_{i},\cdot)\rangle_{K}=\sum_{i,j=1}^{n}b_{i}K(\omega_{i},\omega_{j})c_{j}.$ $$

Without loss of generality, we assume that $\max_{\omega}K(\omega,\omega)<\infty$ is bounded. The RKHS $\mathcal{H}(\mathcal{S}\times\mathcal{A})$ induced by $K$ is defined as the closure of $\hat{\mathcal{H}}$ under the inner product $\langle\cdot,\cdot\rangle_{K}$ and $\mathcal{H}(\mathcal{S}\times\mathcal{A})$ is equipped with norm $\|\cdot\|_{\mathcal{H}(\mathcal{S}\times\mathcal{A})}$ induced by $\langle\cdot,\cdot\rangle_{K}$.

Many functional spaces can be represented within the RKHS framework. For example, deep neural networks, Sobolev spaces, the Euclidean space, and discrete set can all be formulated as RKHSs. For further details, please refer to Adams & Fournier (2003); Wendland (2004); Jacot et al. (2018).

We first impose the following assumption on the Markov chain

###### Assumption 2 .

There exists $R>0$ such that $\max\{\|r\|_{\mathcal{H}},\max_{s\in\mathcal{S}}\|P(s|\cdot,\cdot)\|_{\mathcal{H}}\}\leq R$.

In policy optimization of RL, the RKHS norm $\|Q^{\pi}\|_{\mathcal{H}}$, which is crucial in our analysis, is difficult to determine. The following lemma to show that it is related to the RKHS norm of $\pi$:

###### Lemma 3 .

There exists positive constant $C$ that only depends on $R$, such that $\|Q^{\pi}\|_{\mathcal{H}}\leq C\|\pi(\cdot|\cdot)\|_{\mathcal{H}}$.

Covering Number. The following measures of RKHS complexity are fundamental to our analysis:

###### Definition 4 (Covering number & entropy) .

For a given $\delta>0$, the covering number of a RKHS $\mathcal{H}$ under $L_{\infty}$ norm, denoted by $\mathcal{N}(\delta,\|\cdot\|_{L_{\infty}},\mathcal{H})$, is defined by the smallest integer $M$ sucht that there exists centers $\{f_{m}\}_{m=1}^{M}\subseteq\mathcal{H}$ for which $\forall f\in\mathcal{H}$, $\exists m$: $\|f_{m}-f\|_{L_{\infty}}\leq\delta$. The entropy of $\mathcal{H}$ is the log of its covering number: $H(\delta,\|\cdot\|_{L_{\infty}},\mathcal{H})=\log\mathcal{N}(\delta,\|\cdot\|_{L_{\infty}},\mathcal{H})$.

###### Assumption 5 .

The entropy of a unit ball in the RKHS $\mathcal{H}$: $\mathcal{B}=\{f\in\mathcal{H}:\|f\|_{\mathcal{H}}\leq 1\}$ satisfies

$$ $H(\delta,\|\cdot\|_{L_{\infty}},\mathcal{B})\leq C\delta^{-2\beta}|\log\delta|^{2\kappa}$ (4) $$

for some $C>0$, $\beta\in[0,1)$, and $\kappa\geq 0$.

Assumption [5](https://arxiv.org/html/2509.24991v1#Thmtheorem5) covers a broad class of RKHSs, including those previously mentioned, as well as Sobolev spaces with low intrinsic dimension (Ding et al., 2024; Hamm & Steinwart, 2021) and RKHSs induced by deep neural networks (Anthony & Bartlett, 2009).

###### Assumption 1 .

###### Assumption 2 .

###### Lemma 3 .

###### Definition 4 (Covering number & entropy) .

###### Assumption 5 .

## 4 Policy Evaluation

For policy evaluation, we generalize the TD learning for parameters in finite-dimensional space to functions in infinitely-dimensional RKHS. We first present the optimization formulation and then our Kernel TD algorithm. Theoretical analysis is provided in the last subsetion.

### 4.1 Optimization Formulation

In this paper, we study the problem of estimating the Q function by samples from the the Markov chain. We consider, in every update of policy $\pi$, we sample i.i.d. $\{s_{0}^{(i)}\sim\mu_{0}\}_{i=1}^{n}$ from some chosen distribution $\mu_{0}$ and generate the subsequent state-action pairs $a_{0}^{(i)}$ and $(s^{(i)}_{1},a^{(i)}_{1})$ following the Markov chain as follows:

$$ $s_{0}^{(i)}\sim\mu,\quad a_{0}^{(i)}\sim\pi(\cdot|s_{0}^{(i)}),\quad s_{1}^{(i)}\sim P(\cdot|s_{0}^{(i)},a_{0}^{(i)}),\quad a_{1}^{(i)}\sim\pi(\cdot|s_{1}^{(i)}).$ (5) $$

The initial distribution $\mu_{0}$ can be specified using prior knowledge or obtained by following the chain trajectory and applying MCMC to sample i.i.d. quadruplets ${(s_{0},a_{0},s_{1},a_{1})}$. The resulting distribution is only required to satisfy Assumption [1](https://arxiv.org/html/2509.24991v1#Thmtheorem1) together with an additional assumption:

###### Assumption 6 .

There exists a constant $c$ such that $\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}P(s^{\prime}|s,a)\leq c^{2}\mu_{0}(s^{\prime})$ and $c\gamma<1$.

Assumption [6](https://arxiv.org/html/2509.24991v1#Thmtheorem6) ensures that the one-step transition is not too far from the initial distribution; otherwise convergence slows. The constant $1-c\gamma$ in the convergence rate reflects sampling complexity, with smaller values indicating higher sample requirements.

We then can have dataset $(\omega_{0}^{(i)},\omega_{1}^{(i)})_{i=1}^{n}$ with $\omega_{j}^{(i)}=(s_{j}^{(i)},a_{j}^{(i)})$, $j=0,1$ for any given policy $\pi$. Corresponding to equation [3](https://arxiv.org/html/2509.24991v1#S3.E3), we aim to learn the Q-function $Q^{\pi}$ by solving the following Kernel Ridge Regression (KRR) over the whole RKHS $\mathcal{H}$:

$$ $\hat{Q}^{\pi}=\min_{f\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\left(f(\omega_{0}^{(i)})-r(\omega_{0}^{(i)})-\gamma\hat{Q}^{\pi}(\omega_{1}^{(i)})\right)^{2}+\lambda\|f\|_{\mathcal{H}}^{2}.$ (6) $$

The functional minimization problem in equation [6](https://arxiv.org/html/2509.24991v1#S4.E6) is implicit. Nevertheless, by the representer theorem, it can be shown to admit a closed-form solution:

###### Proposition 7 .

The estimator $\hat{Q}^{\pi}$ has closed-form solution as follows

$$ $\displaystyle\hat{Q}^{\pi}=K(\cdot,\bm{\omega}_{0})\mathbb{b}^{\pi}$ (7) $$

where $\bm{\omega}_{0}=[\omega_{0}^{(1)},\cdots,\omega_{0}^{(n)}]^{\top}\in\mathbb{R}^{n}$, $K(\cdot,\bm{\omega}_{0})=[K(\cdot,\omega_{0}^{(1)}),\cdots,[K(\cdot,\omega_{0}^{(n)})]$, and

$$ $\displaystyle\mathbb{b}^{\pi}=\left[\mathbb{K}+\lambda n{\rm I}-\gamma\mathbb{C}\right]^{-1}\mathbb{r},\quad\mathbb{K}_{i,j}=K(\omega^{(i)}_{0},\omega^{(j)}_{0}),$ $\displaystyle\mathbb{C}_{i,j}=K(\omega^{(i)}_{1},\omega^{(j)}_{0}),\quad\mathbb{r}=[r(\omega_{0}^{(1)}),\cdots,r(\omega_{0}^{(n)})]^{\top}.$ $$

KRR equation [6](https://arxiv.org/html/2509.24991v1#S4.E6) allows us to extend current standard TD algorithm for tabular learning to the kernel TD framework.

###### Assumption 6 .

###### Proposition 7 .

### 4.2 Kernel Temporal-Difference Learning

From Proposition [7](https://arxiv.org/html/2509.24991v1#Thmtheorem7), we know that the solution $\hat{Q}^{\pi}\in\hat{\mathcal{H}}$, so the KRR equation [6](https://arxiv.org/html/2509.24991v1#S4.E6) can be rewritten as

$$ $\mathbb{b}^{\pi}=\min_{\mathbb{b}\in\mathbb{R}^{n}}\frac{1}{n}\sum_{i=1}^{n}\left(K(\omega_{0}^{(i)},\bm{\omega}_{0})\mathbb{b}-r(\omega_{0}^{(i)})-\gamma K(\omega_{1}^{(i)},\bm{\omega}_{0})\mathbb{b}^{\pi}\right)^{2}+\lambda\mathbb{b}^{\top}\mathbb{K}\mathbb{b}.$ (8) $$

Instead of directly solving equation [8](https://arxiv.org/html/2509.24991v1#S4.E8) for the vector $\mathbb{b}^{\pi}$ by gradient based method on $\mathbb{R}^{n}$ , we treat equation [6](https://arxiv.org/html/2509.24991v1#S4.E6) as a functional optimization on the RKHS $\mathcal{H}$. Inspired by Kernel Gradient Descent (Ding et al., 2024; Lin & Zhou, 2018; Raskutti et al., 2014), we propose the following updating rule in the RKHS:

$$ $f_{t+1}=(1-\alpha_{t})f_{t}-\eta_{t}\sum_{i=1}^{n}\left(f_{t}(\omega_{0}^{(i)})-r(\omega_{0}^{(i)})-\gamma f_{t}(\omega_{1}^{(i)})\right)K(\omega_{0}^{(i)},\cdot),$ (9) $$

where $\alpha_{t}$ acts as the weight decay to prevent over-fitting and improve generalization (Hu et al., 2021), and $\eta_{t}$ is the step-size for learning rate. It can be noticed that equation [9](https://arxiv.org/html/2509.24991v1#S4.E9) can be converted to a form similar to semi-gradient TD(0) (Sutton et al., 1998) if we represented it by $\mathbb{b}_{t}=\mathbb{K}^{-1}f_{t}(\bm{\omega}_{0})$:

$$ $\mathbb{b}_{t+1}=(1-\alpha_{t})\mathbb{b}_{t}-\eta_{t}\left(f_{t}(\bm{\omega}_{0})-\mathbb{r}-\gamma f_{t}(\bm{\omega}_{1})\right).$ (10) $$

The difference between equation [10](https://arxiv.org/html/2509.24991v1#S4.E10) and semi-gradient TD(0) lies in the fact equation [10](https://arxiv.org/html/2509.24991v1#S4.E10) uses a functional gradient in the infinite-dimensional RKHS, while semi-gradient TD(0) uses a gradient of some parameterized functions in a finite-dimensional space.

A natural question is why we don’t directly solve the $n$-dimensional equation [8](https://arxiv.org/html/2509.24991v1#S4.E8). The reason is that the update rule equation [10](https://arxiv.org/html/2509.24991v1#S4.E10) is more efficient because it uses the RKHS inner product $\langle\cdot,\cdot\rangle_{\mathcal{H}}$ instead of the $l^{2}$ inner product in $\mathbb{R}^{n}$. This change in inner product modifies the gradient and Hessian, effectively serving as a preconditioner that can improve the performance of the algorithm (Neuberger, 2009).

From updating rule equation [10](https://arxiv.org/html/2509.24991v1#S4.E10), we can derivethe convergence pattern of $f_{t}$ to the target $\hat{Q}^{\pi}$ for correctly-selected constant weight decay $\alpha_{t}=\alpha$ and step size $\eta_{t}=\eta$:

$$ $\displaystyle\mathbb{b}_{t+1}-\mathbb{b}^{\pi}=$ $\displaystyle\left[\rm{I}-\left(\alpha\rm{I}+\eta\mathbb{K}-\eta\gamma\mathbb{C}\right)\right]\left[\mathbb{b}_{t}-\eta\left(\alpha\rm{I}+\eta\mathbb{K}-\eta\gamma\mathbb{C}\right)^{-1}\mathbb{r}\right]$ (11) $\displaystyle=$ $\displaystyle\left[\rm{I}-\left(\alpha\rm{I}+\eta\mathbb{K}-\eta\gamma\mathbb{C}\right)\right]\left[\mathbb{b}_{t}-\mathbb{b}^{\pi}\right]$ $\displaystyle=$ $\displaystyle\left[((1-\alpha)\rm{I}-\eta\mathbb{K}+\eta\gamma\mathbb{C}\right]^{t+1}\left[\mathbb{b}_{0}-\mathbb{b}^{\pi}\right]$ $$

If the eigenvalues of $\left[(1-\alpha)\rm{I}-\eta\mathbb{K}+\eta\gamma\mathbb{C}\right]$ are small, then $f_{t}$ converges to $\hat{Q}^{\pi}$ exponentially fast.

### 4.3 Convergence Analysis of Kernel TD

We first show an error decomposition for the estimator equation [6](https://arxiv.org/html/2509.24991v1#S4.E6). Define the difference function $D^{\pi}=\hat{Q}^{\pi}-Q^{\pi}$ and the Bellman residual:

$$ $\varepsilon_{i}=r(\omega_{0}^{(i)})+\gamma Q^{\pi}(\omega_{1}^{(i)})-Q^{\pi}(\omega^{(i)}_{0}).$ (12) $$

We have the following error decomposition

###### Proposition 8 (Statistical-Approximation Error Decomposition) .

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left(\mathcal{D}^{\pi}(\omega^{(i)}_{0})^{2}-\gamma\mathcal{D}^{\pi}(\omega^{(i)}_{0})\mathcal{D}^{\pi}(\omega^{(i)}_{1})\right)={\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathcal{D}^{\pi}(\omega^{(i)}_{0})}-{\lambda\langle\mathcal{D}^{\pi},\hat{Q}^{\pi}\rangle_{\mathcal{H}}}.$ (13) $$

From the error decomposition on the right-hand side of equation [13](https://arxiv.org/html/2509.24991v1#S4.E13), we then can use empirical process (Geer, 2000) to derive the following convergence rate of $\hat{Q}^{\pi}$ on training data

###### Theorem 9 .

Suppose Assumptions [1](https://arxiv.org/html/2509.24991v1#Thmtheorem1), [2](https://arxiv.org/html/2509.24991v1#Thmtheorem2), [5](https://arxiv.org/html/2509.24991v1#Thmtheorem5), and [6](https://arxiv.org/html/2509.24991v1#Thmtheorem6) hold. Let $\eta=C_{1}/n$, $\alpha=\eta\lambda n$, and iteration number $t\geq C_{2}\log n\|\mathbb{b}_{0}-\mathbb{b}^{\pi}\|$ for some universal $C_{1},C_{2}>0$ and $\lambda=\mathcal{O}((1-c\gamma)^{\frac{\beta}{2+2\beta}}n^{-\frac{1}{2+2\beta}}|\log n|^{\frac{\kappa}{1+\beta}})$, then the kernel TD estimator $f_{t}$ satisfies

$$ $\displaystyle\sqrt{\frac{1}{n}\sum_{i=1}^{n}\left|f_{t}(\omega_{0}^{(i)})-Q^{\pi}(\omega_{0}^{(i)})\right|^{2}}\leq\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{2+\beta}{2+2\beta}}n^{-\frac{1}{2+2\beta}}|\log n|^{\frac{\kappa}{1+\beta}}\right)\|Q^{\pi}\|_{\mathcal{H}},$ (14) $\displaystyle\|f_{t}\|_{\mathcal{H}}\leq\mathcal{O}_{p}(1)\|Q^{\pi}\|_{\mathcal{H}}.$ $$

Theorems [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9) yields convergence only on the dataset $\{\omega_{0}^{(i)}\}_{i=1}^{n}$, not generalization error, since Assumption [5](https://arxiv.org/html/2509.24991v1#Thmtheorem5) is imposed solely for general applicability. Establishing generalization requires additional structural information on the RKHS, after which it follows readily from sampling inequalities.

###### Corollary 10 .

Suppose the same assumptions in Theorem [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9) hold, then

- Tabular:
: If $\mathcal{S}\times\mathcal{A}$ are uncorrelated discrete set $\{\omega_{j}:j=1,\cdots,n^{\nu}\}$ for some constant $\nu\in(0,1)$, then $K=\delta_{s=s^{\prime}}\delta_{a=a^{\prime}}$ and the Kernel TD estimator satisfies
$\|f_{t}-Q^{\pi}\|_{L_{2}(\sigma^{\pi}_{0})}\leq\mathcal{O}_{p}\left((1-c\gamma)^{-1}n^{-\frac{1}{2}}|\log n|^{1/2}+\frac{1}{n^{(1+\nu)/4}}\right)\|Q^{\pi}\|_{\mathcal{H}};$
(15)
- Sobolev:
If $K=K_{\mathcal{S}}\delta_{a=a^{\prime}}$ where $K_{\mathcal{S}}$ is a Sobolev type kernel with smoothness $m$ and intrinsic dimension $d$ and $\mathcal{A}=\{a\}_{a=1}^{A}$, then the Kernel TD estimator satisfies
$\|f_{t}-Q^{\pi}\|_{L_{2}(\sigma^{\pi}_{0})}\leq\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{2m+d/2}{2m+d}}n^{-\frac{m}{2m+d}}\right)\|Q^{\pi}\|_{\mathcal{H}}.$
(16)
- NTK:
If $K=N\delta_{a=a^{\prime}}$ where $N$ is the NTK $N(s,s^{\prime})$ of a two-layer neural network on a $d$-sphere $\mathbb{S}^{d-1}$ and $\mathcal{A}=\{a\}_{a=1}^{A}$, then the Kernel TD estimator satisfies
$\|f_{t}-Q^{\pi}\|_{L_{2}(\sigma^{\pi}_{0})}\leq\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{3d+1}{4d}}n^{-\frac{d+1}{4d}}\right)\|Q^{\pi}\|_{\mathcal{H}}.$
(17)
- Gaussian:
If $\mathcal{H}$ is Gaussian RKHS, i.e., $K=e^{-\|\omega-\omega^{\prime}\|^{2}}$ with $\mathcal{S}\times\mathcal{A}=[0,1]^{d}$ hypercube, then
$\|f_{t}-Q^{\pi}\|_{L_{2}(\sigma^{\pi}_{0})}\leq\mathcal{O}_{p}\left((1-c\gamma)^{-1}n^{-\frac{1}{2}}|\log n|^{{(d+1)}/{2}}\right)\|Q^{\pi}\|_{\mathcal{H}}.$
(18)

###### Proposition 8 (Statistical-Approximation Error Decomposition) .

###### Theorem 9 .

###### Corollary 10 .

## 5 Policy Improvement

We generalize the popular NPG update rule to a version for policy evaluation in the infinite-dimensional RKHS. In this section, we first present our algorithm for updating the policy function from a functional perspective, then we provide global convergence for our algorithm.

### 5.1 Natural Policy Gradient in RKHS

We consisder updating policy by NPG:

$$ $\pi^{k+1}\propto\pi^{k}\exp\{\Delta_{k}f_{T}^{(k)}\}\propto\exp\{\sum_{j=0}^{k}\Delta_{j}f_{T}^{(j)}\}$ (19) $$

where $f_{T}^{(j)}$ is the kernel TD estimator of $Q^{(j)}:=Q^{\pi^{j}}$, trained for $T$ steps on initial data $\{s_{0}^{(i)}\}_{i=1}^{n}$ and $\Delta_{j}$ is the step size. equation [19](https://arxiv.org/html/2509.24991v1#S5.E19) is the solution of the following functional proximal gradient optimization:

###### Lemma 11 .

Suppose $\pi^{k}\propto\exp\{F\}$ and $1>\pi^{(k+1)}>0$. Then on the sets $\{s^{(i)}_{0}\}\times\mathcal{A}$,

$$ $\pi^{k+1}=\operatorname*{arg\,max}_{\int_{\mathcal{A}}\pi(a|\cdot)da=1,\pi\geq 0}\mathbb{E}_{n}\left[\Delta_{k}\int_{\mathcal{A}}f^{(k)}(s,a)\pi(a|s)da-\text{KL}\left(\pi(\cdot|s)\|\pi^{k}(\cdot|s)\right)\right]$ (20) $$

where $\mathbb{E}_{n}[f(s)]=\frac{1}{n}\sum_{i=1}^{n}f(s_{0}^{(i)})$ is the empirical expectation induced by dataset $\{s_{0}^{(i)}\}$ and KL$(p\|q)$ denote the KL divergence between distributions $p$ and $q$.

The update rule equation [19](https://arxiv.org/html/2509.24991v1#S5.E19) generalizes existing NPG methods, including those for tabular RL (Liu et al., 2024), linear RL (Cen et al., 2022), and two-layer neural networks (Liu et al., 2019), to general RKHS functions. Our update rule equation [20](https://arxiv.org/html/2509.24991v1#S5.E20) allows the policy $\pi^{k}$ to be a continuous function of $(s,a)$ and replaces the population-level expectation with an empirical expectation that is adaptive to the data.

By combining the NPG update rule equation [19](https://arxiv.org/html/2509.24991v1#S5.E19) with the kernel TD update rule equation [9](https://arxiv.org/html/2509.24991v1#S4.E9), we introduce an efficient algorithm that generalizes NPG to infinite-dimensional RKHS as follows:

Figure: Algorithm 1 NPG in RKHS

From the NTK perspective, Algorithm [1](https://arxiv.org/html/2509.24991v1#alg1) can be viewed as the evolution of a deep neural network described by kernel $K$. Consequently, it remains valid if we replace the RKHS functions $f^{(k)}$
with a deep neural net $f_{\bm{\theta}^{(k)}}$ parameterized by $\bm{\theta}^{(k)}$ and the policy as $\text{Softmax}(f_{\bm{\theta}^{(k)}})$.

###### Lemma 11 .

### 5.2 Global Convergence of NPG

We first define the expected total reward to measure the optimality of a policy $\pi$

$$ $\mathcal{R}[\pi]=\mathbb{E}_{S\sim\nu^{*}}[V^{\pi}(S)]=\mathbb{E}_{S\sim\nu^{*}}[\langle Q^{\pi}(S,\cdot),\pi(\cdot|S)\rangle_{\mathcal{A}}].$ (21) $$

We can have a fundamental inequality for the equation [21](https://arxiv.org/html/2509.24991v1#S5.E21) in RKHS. This inequality, which slightly modifies the mirror descent analysis in Nesterov (2013); Nemirovsky & Yudin (1985) for infinite-dimensional spaces, is central to our analysis.

###### Theorem 12 .

In Algorithm [1](https://arxiv.org/html/2509.24991v1#alg1),

$$ $\displaystyle\inf_{k}\left(\mathcal{R}[\pi^{k}]-\mathcal{R}[\pi^{*}]\right)$ (22) $\displaystyle\leq$ $\displaystyle\frac{\left(\sum_{k}2\Delta_{k}\|f^{(k)}-Q^{(k)}\|_{L_{\infty}}\right)+\left(\sum_{k}\Delta^{2}_{k}(1-\gamma)^{-1}\|r\|_{L_{\infty}}\right)+\mathbb{E}_{S\sim\nu^{*}}\text{KL}\left(\pi^{*}(\cdot|S)||\pi^{0}(\cdot|S)\right)}{\sum_{k}\Delta_{k}}.$ $$

From Theorem [12](https://arxiv.org/html/2509.24991v1#Thmtheorem12), we observe that achieving the optimal $\mathcal{O}(k^{-1/2})$ convergence rate for stochastic optimization requires selecting suitable parameters in Algorithm [1](https://arxiv.org/html/2509.24991v1#alg1) to ensure the policy evaluation error is well-controlled under the $L_{\infty}$ norm. This leads to the following corollary.

###### Corollary 13 .

Set $\Delta_{k}=1/\sqrt{k}$. For settings listed in Corollary [10](https://arxiv.org/html/2509.24991v1#Thmtheorem10), set $n^{(k)}$ and $\lambda^{(k)}$ according to Table [1](https://arxiv.org/html/2509.24991v1#S5.T1). Set $\alpha^{(k)},\eta^{(k)}$, and $T^{(k)}$ according to Theorem [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9) with $\lambda=\lambda^{(k)}$. Then under the same conditions as Corollary [10](https://arxiv.org/html/2509.24991v1#Thmtheorem10), we have

$$ $\inf_{1\leq k\leq k^{*}}\left(\mathcal{R}[\pi^{k}]-\mathcal{R}[\pi^{*}]\right)\leq\mathcal{O}_{p}(\frac{1}{\sqrt{k^{*}}}).$ (23) $$

Table: Table 1: Parameters selection in Algorithm [1](https://arxiv.org/html/2509.24991v1#alg1) for four cases in Corollary [10](https://arxiv.org/html/2509.24991v1#Thmtheorem10)

Corollary [13](https://arxiv.org/html/2509.24991v1#Thmtheorem13) shows that the required sampling number increases with both the step size $k$ and the policy complexity, measured by the RKHS norm $\|\pi^{k}\|_{\mathcal{H}}$. As the policy nears the optimum, the performance gap narrows, requiring more accurate evaluation and hence more samples. As NPG progresses, the policy may also become highly concentrated, approaching a delta distribution; in this case, the RKHS norm diverges and the sampling requirement grows accordingly.

The RKHS norm is a well-defined and meaningful measure of policy complexity. For examples, in the Sobolev and NTK cases, the policy is from composing a softmax with RKHS function, and remains in the RKHS since the softmax is analytic. Although the RKHS norm is hard to estimate in the NTK case—where the policy corresponds to a deep neural network—other attributes such as network stability and architecture can serve as practical proxies for the RKHS norm complexity.

###### Theorem 12 .

###### Corollary 13 .

## 6 Experiments

We conduct numerical experiments to empirically validate our theoretical analysis of Q-function estimation within the NPG framework outlined in Algorithm [1](https://arxiv.org/html/2509.24991v1#alg1). The experiments are designed to investigate the convergence properties of a deep neural network-based implementation and sample efficiency.

Figure: (a) Reward (CartPole-v1).
Refer to caption: x1.png

### 6.1 Experimental Setup

Environments.
We evaluate our method on standard benchmarks: CartPole-v1 (Barto et al., 2012), a classic low-dimensional control task (4-dim continuous states and 2-dim discrete actions), and Acrobot-v1 (Sutton et al., 1998), a more challenging underactuated robotics problem (6-dim continuous states and 3-dim discrete actions. The details of these two environments are in the Appendix [K.1](https://arxiv.org/html/2509.24991v1#A11.SS1).

Model Architecture. We instantiate the non-parametric function $f^{(k)}$ from Algorithm 1 with a neural network $f_{\theta^{(k)}}$, where the policy is given by $\pi_{\theta}\propto\text{Softmax}(f_{\theta})$. The network is a two-layer MLP.
This model is implemented within an Actor-Critic paradigm where the MLP backbone serves as the Critic ($f_{\theta}$), outputting Q-values, and the addition of a Softmax layer forms the Actor ($\pi_{\theta}$). The Actor and Critic share all parameters, enabling efficient end-to-end training.

Algorithm Configuration. Algorithm [1](https://arxiv.org/html/2509.24991v1#alg1) outlines a two-stage process: optimizing the Q-function for $T$ epochs, followed by a single policy update.
In practice, a finite number of updates (e.g., $T=4$) is insufficient for the Critic to learn well. Consequently, updating the Actor based on an imperfect Critic leads to inefficient and unstable learning. To address this, we adopt a joint optimization strategy, a standard practice in algorithms like PPO. We combine the Critic’s TD Error loss (Line 9) and the Actor’s NPG objective (Line 12) into a unified loss function. This objective is then minimized over $T$ epochs for each batch of collected data.

Each outer iteration $k$ proceeds as follows: we execute the current policy to collect $n$ samples, after which we run $T$ optimization epochs over this batch to update the shared actor–critic parameters. Experiments are run for 1000 episodes and averaged over 10 random seeds; we report the mean and standard deviation across seeds. Hyperparameters are shown in Table [2](https://arxiv.org/html/2509.24991v1#A11.T2) in Appendix [K.2](https://arxiv.org/html/2509.24991v1#A11.SS2).

### 6.2 Convergence Analysis

We investigate the empirical impact of the step size schedule, $\Delta_{k}=k^{-\alpha}$, by testing three theoretically motivated exponents: $\alpha\in\{0.2,0.5,1.5\}$.

Results Analysis.
Figure [1](https://arxiv.org/html/2509.24991v1#S6.F1) corroborates our theoretical predictions, revealing three distinct learning dynamics determined by the schedule $\alpha$.
These results empirically confirm that the step size schedule is a critical factor governing the stability and efficiency of NPG with TD learning. The narrow confidence intervals across 10 seeds highlight the statistical reliability of our findings, providing strong evidence for the optimal convergence for the $\Delta_{k}=\frac{1}{\sqrt{k}}$ schedule in Corollary [13](https://arxiv.org/html/2509.24991v1#Thmtheorem13). Moreover, as shown in Figure [1](https://arxiv.org/html/2509.24991v1#S6.F1) (c-d), the learning curve for $\Delta_{k}=\tfrac{1}{\sqrt{k}}$ exhibits a decline after some episodes. This occurs because, as the neural network becomes more complex, the available samples are insufficient to fully support training, thereby weakening the effectiveness of optimization. A similar trend emerges when the CartPole experiments run for longer episodes (e.g., Figure [2](https://arxiv.org/html/2509.24991v1#S6.F2) (a-b)).

### 6.3 Running Efficiency Analysis

To analyze the sample efficiency, we compare our Algorithm with Standard PPO(Schulman et al., 2017). The key architectural difference between these methods lies in their data requirements for value estimation: Standard PPO utilizes a state-value critic ($V(s)$) and relies on Generalized Advantage Estimation (GAE). GAE requires complete trajectory $(s_{0},a_{0},r_{0},s_{1},a_{1},...,s_{t},a_{t})$ segments to recursively compute advantage targets, making its update rule non-local in time. Instead, Our NPG employs an action-value critic ($Q(s,a)$) and learns from single-step Temporal Difference (TD) errors. This approach is highly data-efficient, as it only requires $(s_{0},a_{0},r_{0},s_{1},a_{1})$ learning Q.

Figure: (a) Reward.
Refer to caption: x5.png

Results Analysis.
Our experiments demonstrate that our NPG with TD learning significantly outperforms Standard PPO in both sample efficiency and computational efficiency. As shown in Figure [2](https://arxiv.org/html/2509.24991v1#S6.F2) (a–b), our NPG consistently solves the task, achieving the maximum reward of 500. In contrast, Standard PPO converges more slowly and exhibits high variance, with only some seeds reaching the optimal solution. Since our algorithm depends on sampling quality (Assumption [1](https://arxiv.org/html/2509.24991v1#Thmtheorem1) and [6](https://arxiv.org/html/2509.24991v1#Thmtheorem6)), choosing a suitable distribution enables fast convergence, as confirmed in Figure [2](https://arxiv.org/html/2509.24991v1#S6.F2). The detailed Hyperparameter setting are explained in the Appendix [K.2](https://arxiv.org/html/2509.24991v1#A11.SS2).

Figure [2](https://arxiv.org/html/2509.24991v1#S6.F2)(c) shows our NPG is about 78.2% more efficient, processing 7,963 state-actions pairs (i.e. $\omega_{t}^{(i)},t=0,1$) per second compared to PPO’s 4,468 pairs (i.e. $\omega_{t}^{(i)}$) per second.
This computational advantage stems directly from our algorithm’s design. The update for our NPG is based on a computationally lightweight, one-step TD-error calculation. In contrast, Standard PPO must perform a more complex, recursive GAE calculation over entire trajectory segments for each update.

## 7 Conclusions

We generalize TD and NPG to infinite-dimensional RKHSs and develop a unified framework for analyzing the convergence rate of kernelized TD in terms of sample size, as well as the sample complexity of RKHS-based NPG for attaining the $\mathcal{O}_{p}(k^{-1/2})$ rate. The framework is illustrated using four commonly studied RKHSs, and numerical experiments further confirm that the theoretical results align well with empirical performance.

## References

- Adams & Fournier (2003)
Robert A Adams and John J F Fournier.
*Sobolev Spaces*.
Academic Press, 2003.
- Agarwal et al. (2020)
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.
Optimality and approximation with policy gradient methods in markov decision processes.
In *Conference on learning theory*, pp. 64–66. PMLR, 2020.
- Agarwal et al. (2021)
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.
On the theory of policy gradient methods: Optimality, approximation, and distribution shift.
*Journal of Machine Learning Research*, 22(98):1–76, 2021.
- Agazzi & Lu (2019)
Andrea Agazzi and Jianfeng Lu.
Temporal-difference learning for nonlinear value function approximation in the lazy training regime.
2019.
- Anthony & Bartlett (2009)
Martin Anthony and Peter L Bartlett.
*Neural network learning: Theoretical foundations*.
cambridge university press, 2009.
- Bagnell & Schneider (2003)
J Andrew Bagnell and Jeff Schneider.
Policy search in kernel hilbert space.
2003.
- Barto et al. (2012)
Andrew G Barto, Richard S Sutton, and Charles W Anderson.
Neuronlike adaptive elements that can solve difficult learning control problems.
*IEEE transactions on systems, man, and cybernetics*, (5):834–846, 2012.
- Baxter & Bartlett (2000)
Jonathan Baxter and Peter L Bartlett.
Direct gradient-based reinforcement learning.
In *2000 IEEE International Symposium on Circuits and Systems (ISCAS)*, volume 3, pp. 271–274. IEEE, 2000.
- Bethke et al. (2008)
Brett Bethke, Jonathan P How, and Asuman Ozdaglar.
Kernel-based reinforcement learning using bellman residual elimination.
*Journal of Machine Learning Research (to appear)*, 2008.
- Bhandari & Russo (2024)
Jalaj Bhandari and Daniel Russo.
Global optimality guarantees for policy gradient methods.
*Operations Research*, 72(5):1906–1927, 2024.
- Bhandari et al. (2018)
Jalaj Bhandari, Daniel Russo, and Raghav Singal.
A finite time analysis of temporal difference learning with linear function approximation.
In *Conference on learning theory*, pp. 1691–1692. PMLR, 2018.
- Birman & Solomjak (1967)
M Š Birman and Mikhail Z Solomjak.
Piecewise-polynomial approximations of functions of the classes.
*Mathematics of the USSR-Sbornik*, 2(3):295, 1967.
- Brandfonbrener & Bruna (2019)
David Brandfonbrener and Joan Bruna.
Geometric insights into the convergence of nonlinear td learning.
*arXiv preprint arXiv:1905.12185*, 2019.
- Cai et al. (2019)
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang.
Neural temporal-difference learning converges to global optima.
*Advances in Neural Information Processing Systems*, 32, 2019.
- Cai et al. (2020)
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang.
Provably efficient exploration in policy optimization.
In *International Conference on Machine Learning*, pp. 1283–1294. PMLR, 2020.
- Cayci et al. (2024)
Semih Cayci, Niao He, and Rayadurgam Srikant.
Convergence of entropy-regularized natural policy gradient with linear function approximation.
*SIAM Journal on Optimization*, 34(3):2729–2755, 2024.
- Cen et al. (2022)
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi.
Fast global convergence of natural policy gradient methods with entropy regularization.
*Operations Research*, 70(4):2563–2578, 2022.
- Chen & Xu (2020)
Lin Chen and Sheng Xu.
Deep neural tangent kernel and laplace kernel have the same rkhs.
*arXiv preprint arXiv:2009.10683*, 2020.
- Cho & Saul (2009)
Youngmin Cho and Lawrence Saul.
Kernel methods for deep learning.
*Advances in neural information processing systems*, 22, 2009.
- Ding et al. (2024)
Liang Ding, Tianyang Hu, Jiahang Jiang, Donghao Li, Wenjia Wang, and Yuan Yao.
Random smoothing regularization in kernel gradient descent learning.
*Journal of Machine Learning Research*, 25(284):1–88, 2024.
- Duan et al. (2024)
Yaqi Duan, Mengdi Wang, and Martin J Wainwright.
Optimal policy evaluation using kernel-based temporal difference methods.
*The Annals of Statistics*, 52(5):1927–1952, 2024.
- Farahmand et al. (2016)
Amir-massoud Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor.
Regularized policy iteration with nonparametric function spaces.
*Journal of Machine Learning Research*, 17(139):1–66, 2016.
- Feng et al. (2020)
Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu.
Accountable off-policy evaluation with kernel bellman statistics.
In *International Conference on Machine Learning*, pp. 3102–3111. PMLR, 2020.
- Geer (2000)
Sara A Geer.
*Empirical Processes in M-estimation*, volume 6.
Cambridge university press, 2000.
- Grunewalder et al. (2012)
Steffen Grunewalder, Guy Lever, Luca Baldassarre, Massi Pontil, and Arthur Gretton.
Modelling transition dynamics in mdps with rkhs embeddings.
*arXiv preprint arXiv:1206.4655*, 2012.
- Hamm & Steinwart (2021)
Thomas Hamm and Ingo Steinwart.
Adaptive learning rates for support vector machines working on data with low intrinsic dimension.
*The Annals of Statistics*, 49(6):3153–3180, 2021.
- Hofmann et al. (2008)
Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola.
Kernel methods in machine learning.
2008.
- Hu et al. (2021)
Tianyang Hu, Wenjia Wang, Cong Lin, and Guang Cheng.
Regularization matters: A nonparametric perspective on overparametrized neural network.
In *International Conference on Artificial Intelligence and Statistics*, pp. 829–837. PMLR, 2021.
- Jacot et al. (2018)
Arthur Jacot, Franck Gabriel, and Clément Hongler.
Neural tangent kernel: Convergence and generalization in neural networks.
*Advances in neural information processing systems*, 31, 2018.
- Kakade & Langford (2002)
Sham Kakade and John Langford.
Approximately optimal approximate reinforcement learning.
In *Proceedings of the nineteenth international conference on machine learning*, pp. 267–274, 2002.
- Kakade (2001)
Sham M Kakade.
A natural policy gradient.
*Advances in neural information processing systems*, 14, 2001.
- Konda & Tsitsiklis (1999)
Vijay Konda and John Tsitsiklis.
Actor-critic algorithms.
*Advances in neural information processing systems*, 12, 1999.
- Koppel et al. (2020)
Alec Koppel, Garrett Warnell, Ethan Stump, Peter Stone, and Alejandro Ribeiro.
Policy evaluation in continuous mdps with efficient kernelized gradient temporal difference.
*IEEE Transactions on Automatic Control*, 66(4):1856–1863, 2020.
- Krieg & Sonnleitner (2024)
David Krieg and Mathias Sonnleitner.
Random points are optimal for the approximation of sobolev functions.
*IMA Journal of Numerical Analysis*, 44(3):1346–1371, 2024.
- Kühn (2011)
Thomas Kühn.
Covering numbers of gaussian reproducing kernel hilbert spaces.
*Journal of Complexity*, 27(5):489–499, 2011.
- Lakshminarayanan & Szepesvari (2018)
Chandrashekar Lakshminarayanan and Csaba Szepesvari.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
In *International conference on artificial intelligence and statistics*, pp. 1347–1355. PMLR, 2018.
- Lin & Zhou (2018)
Shao-Bo Lin and Ding-Xuan Zhou.
Distributed kernel-based gradient descent algorithms.
*Constructive Approximation*, 47(2):249–276, 2018.
- Liu et al. (2019)
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang.
Neural trust region/proximal policy optimization attains globally optimal policy.
*Advances in neural information processing systems*, 32, 2019.
- Liu et al. (2024)
Jiacai Liu, Wenye Li, and Ke Wei.
Elementary analysis of policy gradient methods.
*arXiv preprint arXiv:2404.03372*, 2024.
- Maei et al. (2009)
Hamid Maei, Csaba Szepesvari, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard S Sutton.
Convergent temporal-difference learning with arbitrary smooth function approximation.
*Advances in neural information processing systems*, 22, 2009.
- Mei et al. (2020)
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans.
On the global convergence rates of softmax policy gradient methods.
In *International conference on machine learning*, pp. 6820–6829. PMLR, 2020.
- Munos & Szepesvári (2008)
Rémi Munos and Csaba Szepesvári.
Finite-time bounds for fitted value iteration.
*Journal of Machine Learning Research*, 9(5), 2008.
- Nemirovsky & Yudin (1985)
A. S. Nemirovsky and D. B. Yudin.
Problem complexity and method efficiency in optimization.
*SIAM Review*, 27(2):264–265, 1985.
doi: 10.1137/1027074.
- Nesterov (2013)
Yurii Nesterov.
*Introductory lectures on convex optimization: A basic course*, volume 87.
Springer Science & Business Media, 2013.
- Neu et al. (2017)
Gergely Neu, Anders Jonsson, and Vicenç Gómez.
A unified view of entropy-regularized markov decision processes.
*arXiv preprint arXiv:1705.07798*, 2017.
- Neuberger (2009)
John Neuberger.
*Sobolev gradients and differential equations*.
Springer Science & Business Media, 2009.
- Ormoneit & Sen (2002)
Dirk Ormoneit and Śaunak Sen.
Kernel-based reinforcement learning.
*Machine learning*, 49(2):161–178, 2002.
- Raskutti et al. (2014)
Garvesh Raskutti, Martin J Wainwright, and Bin Yu.
Early stopping and non-parametric regression: an optimal data-dependent stopping rule.
*The Journal of Machine Learning Research*, 15(1):335–366, 2014.
- Rieger (2008)
Christian Rieger.
*Sampling inequalities and applications*.
Georg-August-Universitaet Goettingen (Germany), 2008.
- Schulman et al. (2015)
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.
Trust region policy optimization.
In *International conference on machine learning*, pp. 1889–1897. PMLR, 2015.
- Schulman et al. (2017)
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
*arXiv preprint arXiv:1707.06347*, 2017.
- Shani et al. (2020)
Lior Shani, Yonathan Efroni, and Shie Mannor.
Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps.
In *Proceedings of the AAAI conference on artificial intelligence*, volume 34, pp. 5668–5675, 2020.
- Srikant & Ying (2019)
Rayadurgam Srikant and Lei Ying.
Finite-time error bounds for linear stochastic approximation andtd learning.
In *Conference on learning theory*, pp. 2803–2830. PMLR, 2019.
- Sutton (1988)
Richard S Sutton.
Learning to predict by the methods of temporal differences.
*Machine learning*, 3(1):9–44, 1988.
- Sutton et al. (1998)
Richard S Sutton, Andrew G Barto, et al.
*Reinforcement learning: An introduction*, volume 1.
MIT press Cambridge, 1998.
- Sutton et al. (1999)
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.
Policy gradient methods for reinforcement learning with function approximation.
*Advances in neural information processing systems*, 12, 1999.
- Tuo & Jeff Wu (2016)
Rui Tuo and CF Jeff Wu.
A theoretical framework for calibration in computer models: Parametrization, estimation and convergence properties.
*SIAM/ASA Journal on Uncertainty Quantification*, 4(1):767–795, 2016.
- Tuo et al. (2020)
Rui Tuo, Yan Wang, and CF Jeff Wu.
On the improved rates of convergence for matérn-type kernel ridge regression with application to calibration of computer models.
*SIAM/ASA Journal on Uncertainty Quantification*, 8(4):1522–1547, 2020.
- Utreras (1988)
Florencio I Utreras.
Convergence rates for multivariate smoothing spline functions.
*Journal of approximation theory*, 52(1):1–27, 1988.
- Wang et al. (2019)
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang.
Neural policy gradient methods: Global optimality and rates of convergence.
*arXiv preprint arXiv:1909.01150*, 2019.
- Wendland (2004)
Holger Wendland.
*Scattered data approximation*, volume 17.
Cambridge university press, 2004.
- Zhang et al. (2020)
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar.
Global convergence of policy gradient methods to (almost) locally optimal policies.
*SIAM Journal on Control and Optimization*, 58(6):3586–3612, 2020.
- Zhou (2008)
Ding-Xuan Zhou.
Derivative reproducing properties for kernel methods in learning theory.
*Journal of computational and Applied Mathematics*, 220(1-2):456–463, 2008.

## Appendix A Appendix

## Appendix B Proof of Lemma 3

###### Proof.

Form the definition of $Q^{\pi}$ and triangle inequality, we have

$$ $\|Q^{\pi}\|_{\mathcal{H}}\leq\sum_{t=0}^{\infty}\gamma^{t}\|\mathbb{E}[r(s_{t},a_{t})|s_{0},a_{0}]\|_{\mathcal{H}}.$ (24) $$

So we only need to prove $\|\mathbb{E}[r(s_{t},a_{t})|s_{0}=\cdot,a_{0}=\cdot]\|_{\mathcal{H}}\leq C_{1}R$ for some $C_{1}<\infty$ for all $t$. For the case $t=0$, we use Assumption [2](https://arxiv.org/html/2509.24991v1#Thmtheorem2) to have

$$ $|\mathbb{E}[r(s_{0},a_{0})|s_{0}=\cdot,a_{0}=\cdot]\|_{\mathcal{H}}=\|r\|_{\mathcal{H}}\leq R.$ $$

For general $t$, we rewrite $\mathbb{E}[r(s_{t},a_{t})|s_{0}=\cdot,a_{0}=\cdot]$ in an integral form

$$ $\displaystyle\mathbb{E}[r(s_{t},a_{t})|s_{0},a_{0}]$ $\displaystyle=$ $\displaystyle\int r(s_{t},a_{t})\left(\prod_{\tau=1}^{t}\pi(a_{\tau}|s_{\tau})P(s_{\tau}|s_{\tau-1},a_{\tau}-1)\right)P(s_{1}|s_{0},a_{0})\pi(a_{0}|s_{0})ds_{1}da_{1}\cdots ds_{t}da_{t}$ $\displaystyle=$ $\displaystyle\int r(s_{t},a_{t})P\left((s_{1})\to(s_{t},a_{t})\right)P(s_{1}|s_{0},a_{0})\pi(a_{0}|s_{0})$ (25) $$

where $P\left((s_{1})\to(s_{t},a_{t})\right)$ is the distribution of $(s_{t},a_{t})$ conditioned on $s_{1}$. Let $\{\phi_{i}\}$ be the eigenfunction of $K$ then the RKHS norms of $P(s|\cdot,\cdot)$ and $\pi$ are then

$$ $\|P(s|\cdot,\cdot)\|_{\mathcal{H}}^{2}=\sum_{i}p_{i}(s)^{2}\leq R,\quad\|\pi\|_{\mathcal{H}}^{2}=\sum\pi_{i}^{2}\leq R$ (26) $$

where $p_{i}(s)=\langle P(s|\cdot,\cdot),\phi_{i}\rangle_{\mathcal{H}}$ and $\pi_{i}=\langle\pi,\phi_{i}\rangle_{\mathcal{H}}$.

The coefficient regarding $\mathbb{E}[r(s_{t},a_{t})|s_{0},a_{0}]$ projected onto $\phi_{i}$ is then

$$ $\displaystyle E_{i}=$ $\displaystyle\langle\mathbb{E}[r(s_{t},a_{t})|s_{0},a_{0}],\phi_{i}\rangle_{\mathcal{H}}=\int r(s_{t},a_{t})P\left((s_{1})\to(s_{t},a_{t})\right)\langle P(s_{1}|s_{0},a_{0})\pi(a_{0}|s_{0}),\phi_{i}\rangle_{\mathcal{H}}$ (27) $\displaystyle\leq$ $\displaystyle\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}r(s,a)\max_{s\in\mathcal{S}}\langle P(s|s_{0},a_{0})\pi(a_{0}|s_{0}),\phi_{i}\rangle_{\mathcal{H}}$ $\displaystyle\leq$ $\displaystyle\max_{\omega\in\mathcal{S}\times\mathcal{A}}K(\omega,\omega)R\max_{s\in\mathcal{S}}\langle P(s|s_{0},a_{0})\pi(a_{0}|s_{0}),\phi_{i}\rangle_{\mathcal{H}}$ $$

where the last line is because $\max_{\omega}r(\omega)=\langle r,K(\cdot,\omega)\rangle_{\mathcal{H}}\leq\|K(\cdot,\omega)\|_{\mathcal{H}}\|r\|_{\mathcal{H}}\leq\max_{\omega}K(\omega,\omega)R$.

From equation [27](https://arxiv.org/html/2509.24991v1#A2.E27), we only need to calculate the RKHS norm of function $P(s|s_{0},a_{0})\pi(a_{0}|s_{0})$. From equation [26](https://arxiv.org/html/2509.24991v1#A2.E26), we can derive that

$$ $\displaystyle\|P(s|s_{0},a_{0})\pi(a_{0}|s_{0})\|^{2}_{\mathcal{H}}=$ $\displaystyle\|\left(\sum_{i}p_{i}(s)\phi_{i}\right)\left(\sum_{i}\pi_{i}\phi_{i}\right)\|_{\mathcal{H}}^{2}$ (28) $\displaystyle=$ $\displaystyle\sum_{i}p_{i}(s)^{2}\pi_{i}^{2}\leq\left(\sup_{s}\sup_{i}p_{i}(s)^{2}\right)\|\pi\|_{\mathcal{H}}^{2}\leq R^{2}\|\pi\|_{\mathcal{H}}^{2}.$ $$

By combining equation [26](https://arxiv.org/html/2509.24991v1#A2.E26) equation [28](https://arxiv.org/html/2509.24991v1#A2.E28), we can conclude that

$$ $\|\mathbb{E}[r(s_{t},a_{t})|s_{0}=\cdot,a_{0}=\cdot]\|_{\mathcal{H}}\leq C\|\pi\|_{\mathcal{H}}^{2}.$ (29) $$

Substitute equation [29](https://arxiv.org/html/2509.24991v1#A2.E29) into equation [24](https://arxiv.org/html/2509.24991v1#A2.E24), we can have the final result.
∎

###### Proof.

## Appendix C Proof of Proposition 7

###### Proof of equation 7 .

We first briefly introduce the concept of covariance operators, which is crucial in the proof. We adopt the shorthand notation $\Phi(\omega)=K(\omega,\cdot)$ and $\mu^{\pi}(\omega,\omega^{\prime})=\mu^{\pi}((s,a)),(s^{\prime},a^{\prime})=\mu(s)\pi(s|a)P(s^{\prime}|s,a)\pi(a^{\prime}|s^{\prime})$. Then the covariance operator $C_{\omega_{0},\omega_{0}}$ and cross-covariance operator $C_{\omega_{0},\omega_{1}}$ on the RKHS $\mathcal{H}$ are defined as:

$$ $\displaystyle C_{\omega_{0},\omega_{0}}=\mathbb{E}_{(S,A)\sim\mu(s)\pi(a|s)}[\Phi(S,A)\otimes\Phi(S,A)],$ $\displaystyle C_{\omega_{0},\omega_{1}}=\mathbb{E}_{((S,A),(S^{\prime},A^{\prime}))\sim\mu^{\pi}}[\Phi(S,A)\otimes\Phi({S^{\prime},A^{\prime}})]$ $$

where $f\otimes g$ denote the tensor product between functions $f$ and $g$. Accordingly, for any $f_{0},f_{1}\in\mathcal{H}$, $C_{\omega_{0},\omega_{0}}$ and $C_{\omega_{0},\omega_{1}}$ satisfy

$$ $\displaystyle\langle f_{0},C_{\omega_{0},\omega_{0}}f_{1}\rangle_{\mathcal{H}}=\mathbb{E}_{(S,A)\sim\mu(s)\pi(a|s)}[f_{0}(S,A)f_{1}(S,A)],$ $\displaystyle\langle f_{0},C_{\omega_{0},\omega_{1}}f_{1}\rangle_{\mathcal{H}}=\mathbb{E}_{((S,A),(S^{\prime},A^{\prime}))\sim\mu^{\pi}}[f_{0}(S,A)f_{1}(S^{\prime},A^{\prime})]].$ $$

We can also define the empirical version of operators $C_{\omega_{0},\omega_{0}}$ and $C_{\omega_{0},\omega_{1}}$ as follows:

$$ $\hat{C}_{\omega_{0},\omega_{0}}=\frac{1}{n}\sum_{i=1}^{n}\Phi({\omega^{(i)}_{0}})\otimes\Phi({\omega^{(i)}_{0}}),\quad\hat{C}^{\pi}_{\omega_{0},\omega_{1}}=\frac{1}{n}\sum_{i=1}^{n}\Phi({\omega^{(i)}_{0}})\otimes\Phi({\omega^{(i)}_{1}}).$ $$

With the concept of covariance operator, we can have the following lemma which can yield a specific formulation for the solution of equation [6](https://arxiv.org/html/2509.24991v1#S4.E6):

###### Lemma 14 .

Solution to equation [6](https://arxiv.org/html/2509.24991v1#S4.E6) is equivalent to the following equation:

$$ $\hat{C}_{\omega_{0},\omega_{0}}\hat{Q}^{\pi}-\left[\hat{C}_{\omega_{0},\omega_{0}}r+\gamma\hat{C}_{\omega_{0},\omega_{1}}\hat{Q}^{\pi}\right]+\lambda\hat{Q}^{\pi}=0.$ (30) $$

From Lemma [14](https://arxiv.org/html/2509.24991v1#Thmtheorem14), we can prove that the solution $\hat{Q}^{\pi}$ resides in a finite-dimensional space:

###### Lemma 15 .

Let $\hat{\mathcal{H}}=\{K(\omega_{i},\cdot),i=1,\cdots,n\}$ be the finite dimensional space spanned by kernel functions. We have $\hat{Q}^{\pi}\in\hat{\mathcal{H}}$.

From Lemma [15](https://arxiv.org/html/2509.24991v1#Thmtheorem15), we know that $\hat{Q}^{\pi}$ must be of the form:

$$ $\hat{Q}^{\pi}=\sum_{i=1}^{n}K(\cdot,\omega_{i})b_{i}=K(\cdot,\bm{\omega}_{0})\mathbb{b}.$ (31) $$

Substitute equation [31](https://arxiv.org/html/2509.24991v1#A3.E31) into equation [30](https://arxiv.org/html/2509.24991v1#A3.E30), togethe with the definition of empirical operators $\hat{C}_{\omega_{0},\omega_{0}}$ and $\hat{C}_{\omega_{0},\omega_{1}}$, we then have

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\Phi(\omega_{0}^{(i)})\sum_{j=1}^{n}b_{j}K(\omega_{0}^{(i)},\omega_{0}^{(j)})-\frac{1}{n}\sum_{i=1}^{n}\Phi(\omega_{0}^{(i)})\left[r(\omega_{0}^{(i)})+\gamma\sum_{j=1}^{n}b_{j}K(\omega_{1}^{(i)},\omega_{0}^{(j)})\right]$ (32) $\displaystyle+\lambda\sum_{i=1}^{n}b_{i}\Phi(\omega_{0}^{(i)})=0.$ $$

Rearrange equation [32](https://arxiv.org/html/2509.24991v1#A3.E32) and write it in vector form, we have

$$ $\Phi(\bm{\omega}_{0})\left[\mathbb{K}\mathbb{b}+\lambda n\mathbb{b}-\gamma\mathbb{C}\mathbb{b}\right]=\Phi(\bm{\omega}_{0})\mathbb{r}.$ (33) $$

So, we have

$$ $\mathbb{b}=\left[\mathbb{K}+\lambda n{\rm I}-\gamma\mathbb{C}\right]^{-1}\mathbb{r}.$ $$

∎

###### Proof of equation 7 .

###### Lemma 14 .

###### Lemma 15 .

### C.1 Proof of Lemma 14

###### Proof.

Define the functional

$$ $\mathcal{J}[f]=\|\hat{C}_{\omega_{0},\omega_{0}}f-\left(\hat{C}_{\omega_{0},\omega_{0}}r+\gamma\hat{C}_{\omega_{0},\omega_{1}}Q^{\pi}\right)\|_{n}^{2}+\lambda\|f\|_{\mathcal{H}}^{2}.$ (34) $$

The functional $\mathcal{J}$ is Fréchet differentiable obviously with RKHS derivative $\nabla_{f}\mathcal{J}[f]$ as follows:

$$ $\displaystyle\frac{1}{2}\partial_{\delta}\mathcal{J}[f+\delta u]\big|_{\delta=0}$ (35) $\displaystyle=$ $\displaystyle\langle\frac{1}{n}\sum_{i=1}^{n}\left(f(\omega^{(i)}_{0})-r(\omega^{(i)}_{0})-\gamma\hat{Q}^{\pi}(\omega^{(i)}_{1})\right)K(\omega^{(i)}_{0},\cdot)+\lambda f,u\rangle_{\mathcal{H}},$ $\displaystyle=$ $\displaystyle\langle\nabla_{f}\mathcal{J}[f],u\rangle_{\mathcal{H}},\quad\forall u\in\mathcal{H}.$ (36) $$

From the definition of empirical covariance operators, we can notice that

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left(f(\omega^{(i)}_{0})-r(\omega^{(i)}_{0})\right)K(\omega^{(i)}_{0},\cdot)=\hat{C}_{s_{0},s_{0}}[f-r],$ (37) $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\hat{Q}^{\pi}(\omega^{(i)}_{1})K(\omega^{(i)}_{0},\cdot)=\hat{C}_{\omega_{0},\omega_{1}}\hat{Q}^{\pi}.$ (38) $$

Substitute equation [37](https://arxiv.org/html/2509.24991v1#A3.E37) and equation [38](https://arxiv.org/html/2509.24991v1#A3.E38) into equation [35](https://arxiv.org/html/2509.24991v1#A3.E35), we then have:

$$ $\nabla_{f}\mathcal{J}[f]=\hat{C}_{\omega_{0},\omega_{0}}f-\left[\hat{C}_{\omega_{0},\omega_{0}}r+\gamma\hat{C}_{\omega_{0},\omega_{1}}\hat{Q}^{\pi}\right]+\lambda f.$ (39) $$

According to definition, $\hat{Q}^{\pi}$ is also the minimizer of $\mathcal{J}$. Substitute $f=\hat{Q}^{\pi}$ into equation [39](https://arxiv.org/html/2509.24991v1#A3.E39), we can conclude that the minimization of equation [34](https://arxiv.org/html/2509.24991v1#A3.E34) is equivalent to equation [6](https://arxiv.org/html/2509.24991v1#S4.E6).
∎

###### Proof.

### C.2 Proof of Lemma 15

###### Proof.

Rearrange equation [30](https://arxiv.org/html/2509.24991v1#A3.E30) as follows

$$ $\lambda\hat{Q}^{\pi}=\hat{C}_{\omega_{0},\omega_{0}}r+\gamma\hat{C}_{\omega_{0},\omega_{1}}\hat{Q}^{\pi}-\hat{C}_{\omega_{0},\omega_{0}}\hat{Q}^{\pi}.$ (40) $$

According to equation [37](https://arxiv.org/html/2509.24991v1#A3.E37) and equation [38](https://arxiv.org/html/2509.24991v1#A3.E38), the right hand side of equation [40](https://arxiv.org/html/2509.24991v1#A3.E40) can be written as

$$ $\displaystyle\hat{C}_{\omega_{0},\omega_{0}}\left[r-\hat{Q}^{\pi}\right]+\gamma\hat{C}_{\omega_{0},\omega_{1}}\hat{Q}^{\pi}$ $\displaystyle=$ $\displaystyle\frac{1}{n}K(\cdot,\omega^{(i)}_{0})\left[r(\omega^{(i)}_{0})-\hat{Q}^{\pi}(\omega^{(i)}_{0})+\hat{Q}^{\pi}(\omega^{(i)}_{1})\right]\in\hat{\mathcal{H}}.$ $$

The right hand side of equation [40](https://arxiv.org/html/2509.24991v1#A3.E40) resides in $\hat{\mathcal{H}}$. So, the left hand side $\hat{Q}^{\pi}\in\hat{\mathcal{H}}$.
∎

###### Proof.

## Appendix D Proof of Proposition 8

###### Proof..

According to the definition of covariance operator, the Bellman equation equation [3](https://arxiv.org/html/2509.24991v1#S3.E3) is equivalent to to follow form:

$$ $C_{\omega_{0},\omega_{0}}Q^{\pi}=C_{\omega_{0},\omega_{0}}r+\gamma C_{\omega_{0},\omega_{1}}Q^{\pi}.$ (41) $$

Substitute equation [41](https://arxiv.org/html/2509.24991v1#A4.E41) into Lemma [14](https://arxiv.org/html/2509.24991v1#Thmtheorem14), we can have

$$ $\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}\right]\hat{Q}^{\pi}-C_{\omega_{0},\omega_{0}}Q^{\pi}=\left[\hat{C}_{\omega_{0},\omega_{0}}-C_{\omega_{0},\omega_{0}}\right]r+\gamma\left[\hat{C}_{\omega_{0},\omega_{1}}\hat{Q}^{\pi}-C_{\omega_{0},\omega_{1}}Q^{\pi}\right].$ (42) $$

Recall that $\mathcal{D}^{\pi}=\hat{Q}^{\pi}-Q^{\pi}$, we can rewrite equation [42](https://arxiv.org/html/2509.24991v1#A4.E42) as

$$ $\displaystyle\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}-\gamma\hat{C}_{\omega_{0},\omega_{1}}\right]\mathcal{D}^{\pi}$ (43) $\displaystyle=$ $\displaystyle\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}-C_{\omega_{0},\omega_{0}}\right]\left(r-Q^{\pi}\right)-\lambda r+\gamma\left[\hat{C}_{\omega_{0},\omega_{1}}-C_{\omega_{0},\omega_{1}}\right]Q^{\pi}$ $\displaystyle=$ $\displaystyle\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}\right]\left(r-Q^{\pi}\right)+\gamma\hat{C}_{s_{0},s_{1}}Q^{\pi}-\lambda r$ $\displaystyle+\left(C_{\omega_{0},\omega_{0}}\left(Q^{\pi}-r\right)-\gamma C_{\omega_{0},\omega_{1}}Q^{\pi}\right)$ $\displaystyle=$ $\displaystyle\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}\right]\left(r-Q^{\pi}\right)+\gamma\hat{C}_{\omega_{0},\omega_{1}}Q^{\pi}-\lambda r$ (44) $$

where the last line is from equation [41](https://arxiv.org/html/2509.24991v1#A4.E41). Taking the Hilbert space inner product with $\mathcal{D}^{\pi}$ in equation [43](https://arxiv.org/html/2509.24991v1#A4.E43) and equation [44](https://arxiv.org/html/2509.24991v1#A4.E44):

$$ $\displaystyle\langle\mathcal{D}^{\pi},\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}-\gamma\hat{C}_{\omega_{0},\omega_{1}}\right]\mathcal{D}^{\pi}\rangle_{\mathcal{H}}$ (45) $\displaystyle=$ $\displaystyle\langle\mathcal{D}^{\pi},\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}\right]\left(r-Q^{\pi}\right)+\gamma\hat{C}_{\omega_{0},\omega_{1}}Q^{\pi}-\lambda r\rangle_{\mathcal{H}}.$ (46) $$

According to the definition of empirical covariance operators, equation [45](https://arxiv.org/html/2509.24991v1#A4.E45) can be further rewritten as

$$ $\displaystyle\langle\mathcal{D}^{\pi},\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda{\rm I}-\gamma\hat{C}_{\omega_{0},\omega_{1}}\right]\mathcal{D}^{\pi}\rangle_{\mathcal{H}}$ (47) $\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathcal{D}^{\pi}(\omega_{0}^{(i)})^{2}-\frac{\gamma}{n}\sum_{i=1}^{n}\mathcal{D}^{\pi}(\omega_{0}^{(i)})\mathcal{D}^{\pi}(\omega_{1}^{(i)})+\lambda\|\mathcal{D}^{\pi}\|^{2}_{\mathcal{H}}$ $$

and equation [46](https://arxiv.org/html/2509.24991v1#A4.E46) can be further rewritten as

$$ $\displaystyle\langle\mathcal{D}^{\pi},\left[\hat{C}_{\omega_{0},\omega_{0}}+\lambda_{K}{\rm I}\right]\left(r-Q^{\pi}\right)+\gamma\hat{C}_{\omega_{0},\omega_{1}}Q^{\pi}-\lambda r\rangle_{\mathcal{H}}$ (48) $\displaystyle=$ $\displaystyle\langle\mathcal{D}^{\pi},\hat{C}_{\omega_{0},\omega_{0}}\left(r-Q^{\pi}\right)+\gamma\hat{C}_{\omega_{0},\omega_{1}}Q^{\pi}\rangle_{\mathcal{H}}-\lambda\langle\mathcal{D}^{\pi},Q^{\pi}\rangle_{\mathcal{H}}.$ $$

Because equation [47](https://arxiv.org/html/2509.24991v1#A4.E47) and equation [48](https://arxiv.org/html/2509.24991v1#A4.E48) are equals, by rearranging their terms, we have

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathcal{D}^{\pi}(\omega_{0}^{(i)})^{2}-\frac{\gamma}{n}\sum_{i=1}^{n}\mathcal{D}^{\pi}(\omega_{0}^{(i)})\mathcal{D}^{\pi}(\omega_{1}^{(i)})$ (49) $\displaystyle=$ $\displaystyle\langle\mathcal{D}^{\pi},\hat{C}_{\omega_{0},\omega_{0}}\left(r-Q^{\pi}\right)+\gamma\hat{C}_{\omega_{0},\omega_{1}}Q^{\pi}\rangle_{\mathcal{H}}-\lambda\langle\mathcal{D}^{\pi},\hat{Q}^{\pi}\rangle_{\mathcal{H}}.$ (50) $$

We use the definitions of empirical and population covariance operators again, the first term of equation [50](https://arxiv.org/html/2509.24991v1#A4.E50) is

$$ $\displaystyle\langle\mathcal{D}^{\pi},\hat{C}_{\omega_{0},\omega_{0}}\left(r-Q^{\pi}\right)+\gamma\hat{C}_{\omega_{0},\omega_{1}}Q^{\pi}\rangle_{\mathcal{H}}$ (51) $\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathcal{D}^{\pi}(\omega_{0}^{(i)})\left(r(\omega_{0}^{(i)})-Q^{\pi}(\omega_{0}^{(i)})+\gamma Q^{\pi}(\omega_{1}^{(i)})\right)=\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathcal{D}^{\pi}(\omega_{0}^{(i)}).$ $$

Substitute equation [51](https://arxiv.org/html/2509.24991v1#A4.E51) into equation [50](https://arxiv.org/html/2509.24991v1#A4.E50), we can have the final result.
∎

###### Proof..

## Appendix E Proof of Theorem 9

In order to proof Theorem [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9), we first need the following theorem, which we will provide its proof in Appendix [F](https://arxiv.org/html/2509.24991v1#A6).

###### Theorem 16 .

Let
$\lambda=\mathcal{O}((1-c\gamma)^{\frac{\beta}{2+2\beta}}n^{-\frac{1}{2+2\beta}}|\log n|^{\frac{\kappa}{1+\beta}})$.
Under Assumptions [1](https://arxiv.org/html/2509.24991v1#Thmtheorem1), [2](https://arxiv.org/html/2509.24991v1#Thmtheorem2), [5](https://arxiv.org/html/2509.24991v1#Thmtheorem5), and [6](https://arxiv.org/html/2509.24991v1#Thmtheorem6) we can have

$$ $\displaystyle\sqrt{\frac{1}{n}\sum_{i=1}^{n}\left|\mathcal{D}^{\pi}(\omega_{0}^{(i)})\right|^{2}}\leq\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{2+\beta}{2+2\beta}}n^{-\frac{1}{2+2\beta}}|\log n|^{\frac{\kappa}{1+\beta}}\right)\|Q^{\pi}\|_{\mathcal{H}},$ (52) $\displaystyle\|\hat{Q}^{\pi}\|_{\mathcal{H}}\leq\mathcal{O}_{p}(1)\|Q^{\pi}\|_{\mathcal{H}}.$ $$

###### Proof of Theorem 9 :.

By triangle inequality and Theorem [16](https://arxiv.org/html/2509.24991v1#Thmtheorem16), we have

$$ $\displaystyle\|f_{t}-Q^{\pi}\|_{n}\leq$ $\displaystyle\|f_{t}-\hat{Q}^{\pi}\|_{n}+\|\hat{Q}^{\pi}-Q^{\pi}\|_{n}$ (53) $\displaystyle\leq$ $\displaystyle\|f_{t}-\hat{Q}^{\pi}\|_{n}+\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{2+\beta}{2+2\beta}}n^{-\frac{1}{2+2\beta}}|\log n|^{\frac{\kappa}{1+\beta}}\right),$ $$

and

$$ $\displaystyle\|f_{t}\|_{\mathcal{H}}\leq\|\hat{Q}^{\pi}\|_{\mathcal{H}}+\|f_{t}-\hat{Q}^{\pi}\|_{\mathcal{H}}+\|\hat{Q}^{\pi}-Q^{\pi}\|_{\mathcal{H}}\leq\mathcal{O}_{p}(1)\|Q^{\pi}\|_{\mathcal{H}}+\|f_{t}-\hat{Q}^{\pi}\|_{\mathcal{H}}.$ (54) $$

Therefore, we only need to prove that the convergence rates of $f_{t}$ to $\hat{Q}^{\pi}$ under $\|\cdot\|_{n}$ and $\|\cdot\|_{\mathcal{H}}$ have the same order as their counterpart in Theorem [16](https://arxiv.org/html/2509.24991v1#Thmtheorem16).

Note that by the selections of decay weight $\alpha$ and step size $\eta$, $\alpha/\eta=\lambda$. Then we can use equation [11](https://arxiv.org/html/2509.24991v1#S4.E11) and Hölder inequality to have

$$ $\displaystyle\|f_{t}-\hat{Q}^{\pi}\|_{n}^{2}=$ $\displaystyle\frac{1}{n}\left(\mathbb{b}_{t}-\mathbb{b}^{\pi}\right)^{\top}\mathbb{K}^{2}\left(\mathbb{b}_{t}-\mathbb{b}^{\pi}\right)$ (55) $\displaystyle\leq$ $\displaystyle\left(\max_{\omega}K(\omega,\omega)\right)^{2}n\left(\mathbb{b}_{t}-\mathbb{b}^{\pi}\right)^{2}$ $\displaystyle=$ $\displaystyle Cn\left(\left[((1-\alpha)\rm{I}-\eta\mathbb{K}+\eta\gamma\mathbb{C}\right]^{t}\left[\mathbb{b}_{0}-\mathbb{b}^{\pi}\right]\right)^{2}$ $\displaystyle\leq$ $\displaystyle Cn\Lambda_{2}^{t}(\mathbb{b}_{0}-\mathbb{b}^{\pi})^{2}$ $$

where $\Lambda_{2}$ is the maximum eigenvalue $\left[((1-\alpha)\rm{I}-\eta\mathbb{K}+\eta\gamma\mathbb{C}\right]\top\left[((1-\alpha)\rm{I}-\eta\mathbb{K}+\eta\gamma\mathbb{C}\right]$ and $C=(\max_{\omega}K(\omega,\omega))^{2}$.

Note that the maximum and minimum eigenvalue of the matrix $\mathbb{K}-\gamma\mathbb{C}$ is upper bounded by $(1+\gamma)\max_{\omega}K(\omega,\omega)n$ and lower bounded by $-\gamma\max_{\omega}K(\omega,\omega)n$, respectively. Therefore, if we can select $\eta$ such that

$$ $\displaystyle(1-\alpha-(1+\gamma)\max_{\omega}K(\omega,\omega)n\eta)\leq C_{1}<1.$ (56) $\displaystyle(1-\alpha+\gamma\max_{\omega}K(\omega,\omega)n\eta)\leq C_{2}<1,$ $$

then $\Lambda_{2}\leq C_{3}^{2}<1$ where $C_{3}=\max\{C_{1},C_{2}\}$. We also need an extra condition so that $f_{t}$ converges to the estimator $\hat{Q}^{\pi}$ with correctly selected $\lambda$ as in Theorem [16](https://arxiv.org/html/2509.24991v1#Thmtheorem16), we also have

$$ $\alpha=\eta\lambda n.$ (57) $$

Solving equation [56](https://arxiv.org/html/2509.24991v1#A5.E56) and equation [57](https://arxiv.org/html/2509.24991v1#A5.E57) to get

$$ $0<\eta\leq\frac{1-C_{1}}{n(1+\gamma)C+\lambda}$ $$

and then by letting $t=\log_{C_{3}}\left([n(\mathbb{b}_{0}-\mathbb{b}^{\pi})^{2}]^{-1}\lambda\right)$, we have

$$ $\displaystyle\|f_{t}-\hat{Q}^{\pi}\|_{n}^{2}\leq Cn(\mathbb{b}_{0}-\mathbb{b}_{1})^{2}C_{3}^{t}=Cn(\mathbb{b}_{0}-\mathbb{b}^{\pi})^{2}C_{3}^{\log_{C_{3}}[n(\mathbb{b}_{0}-\mathbb{b}^{\pi})]^{-1}\lambda}\leq\mathcal{O}(\lambda).$ (58) $$

Similarly, for the convergence in RKHS norm, we have

$$ $\displaystyle\|f_{t}-\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}=$ $\displaystyle\left(\mathbb{b}_{t}-\mathbb{b}^{\pi}\right)^{\top}\mathbb{K}\left(\mathbb{b}_{t}-\mathbb{b}^{\pi}\right)$ (59) $\displaystyle\leq$ $\displaystyle\left(\max_{\omega}K(\omega,\omega)\right)n\left(\mathbb{b}_{t}-\mathbb{b}^{\pi}\right)^{2}$ $\displaystyle=$ $\displaystyle\sqrt{C}n\left(\left[((1-\alpha)\rm{I}-\eta\mathbb{K}+\eta\gamma\mathbb{C}\right]^{t}\left[\mathbb{b}_{0}-\mathbb{b}^{\pi}\right]\right)^{2}$ $\displaystyle\leq$ $\displaystyle\sqrt{C}n\Lambda_{2}^{t}(\mathbb{b}_{0}-\mathbb{b}^{\pi})^{2}.$ $$

Note that the order of equation [59](https://arxiv.org/html/2509.24991v1#A5.E59) is the same as that of equation [55](https://arxiv.org/html/2509.24991v1#A5.E55) except that the constant term is changed from $C$ to $\sqrt{C}$. Therefore, the same iteration number $t$ is enough for the following convergence

$$ $\|f_{t}-\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}\leq\mathcal{O}(\lambda).$ (60) $$

Substitute equation [58](https://arxiv.org/html/2509.24991v1#A5.E58) into equation [53](https://arxiv.org/html/2509.24991v1#A5.E53) and equation [60](https://arxiv.org/html/2509.24991v1#A5.E60) into
equation [54](https://arxiv.org/html/2509.24991v1#A5.E54), we can have the final results.
∎

###### Theorem 16 .

###### Proof of Theorem 9 :.

## Appendix F Proof of Theorem 16

We first slightly modify the error decomposition equation [13](https://arxiv.org/html/2509.24991v1#S4.E13) to get the following inequality

$$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left(\mathcal{D}^{\pi}(\omega^{(i)}_{0})^{2}-\gamma\mathcal{D}^{\pi}(\omega^{(i)}_{0})\mathcal{D}^{\pi}(\omega^{(i)}_{1})\right)+\lambda\|\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}$ (61) $\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathcal{D}^{\pi}(\omega_{0}^{(i)})+\lambda\langle Q^{\pi},\hat{Q}^{\pi}\rangle_{\mathcal{H}}.$ $$

By further rewriting equation LABEL:eq:convergence_KRR_1, we obtain the oracle that is essential to the proof:

$$ $\frac{1}{n}\sum_{i=1}^{n}\left(\mathcal{D}^{\pi}(\omega^{(i)}_{0})^{2}-\gamma\mathcal{D}^{\pi}(\omega^{(i)}_{0})\mathcal{D}^{\pi}(\omega^{(i)}_{1})\right)+\lambda\|\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}=\underbrace{\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathcal{D}^{\pi}(\omega_{0}^{(i)})}_{\text{variance}}+\underbrace{\lambda\langle\hat{Q}^{\pi},Q^{\pi}\rangle_{\mathcal{H}}^{2}}_{\text{bias}}.$ (62) $$

For the left-hand side of equation [62](https://arxiv.org/html/2509.24991v1#A6.E62), we can use standard central limit theorem for Monte Carlo integration to have

$$ $\displaystyle\gamma\frac{1}{n}\sum_{i=1}^{n}\mathcal{D}^{\pi}(\omega^{(i)}_{0})\mathcal{D}^{\pi}(\omega^{(i)}_{1})\leq$ $\displaystyle\gamma\big|\mathbb{E}[\mathcal{D}^{\pi}(\omega_{0})\mathcal{D}^{\pi}(\omega_{1})]\big|+\mathcal{O}_{p}(n^{-\frac{1}{2}})\left|\mathbb{E}[\mathcal{D}^{\pi}(\omega_{0})\mathcal{D}^{\pi}(\omega_{1})]\right|$ (63) $\displaystyle\leq$ $\displaystyle\left(\gamma+\mathcal{O}_{p}(n^{-\frac{1}{2}})\right)\sqrt{\mathbb{E}[|\mathcal{D}^{\pi}(\omega_{0})|^{2}]\mathbb{E}[|\mathcal{D}^{\pi}(\omega_{1})|^{2}]}$ $\displaystyle\leq$ $\displaystyle c\left(\gamma+\mathcal{O}_{p}(n^{-\frac{1}{2}})\right){\mathbb{E}[|\mathcal{D}^{\pi}(\omega_{0})|^{2}]}$ $\displaystyle\leq$ $\displaystyle c\gamma\frac{1}{n}\sum_{i=1}^{n}\mathcal{D}^{\pi}(\omega^{(i)}_{0})^{2}+\mathcal{O}_{p}(n^{-\frac{1}{2}}){\mathbb{E}[|\mathcal{D}^{\pi}(\omega_{0})|^{2}]},$ $$

where the third line of equation [63](https://arxiv.org/html/2509.24991v1#A6.E63) follows from Assumption [6](https://arxiv.org/html/2509.24991v1#Thmtheorem6) that

$$ $\displaystyle\mathbb{E}[|\mathcal{D}^{\pi}(\omega_{1})|^{2}]=$ $\displaystyle\int\left|\mathcal{D}^{\pi}(s_{1},a_{1})\right|^{2}\pi(a_{1}|s_{1})P(s_{1}|s_{0},a_{0})\pi(a_{0}|s_{0})\mu(s_{0})ds_{1}da_{1}ds_{0}da_{0}$ $\displaystyle=$ $\displaystyle\int\left|\mathcal{D}^{\pi}(s_{1},a_{1})\right|^{2}\pi(a_{1}|s_{1})\left[\int P(s_{1}|s_{0},a_{0})\pi(a_{0}|s_{0})\mu(s_{0})ds_{0}da_{0}\right]ds_{1}da_{1}$ $\displaystyle\leq$ $\displaystyle\int\left|\mathcal{D}^{\pi}(s_{1},a_{1})\right|^{2}\pi(a_{1}|s_{1})\left(\max_{s,a}P(s_{1}|s,a)\right)ds_{1}da_{1}$ $\displaystyle\leq$ $\displaystyle c\int\left|\mathcal{D}^{\pi}(s_{1},a_{1})\right|^{2}\pi(a_{1}|s_{1})\mu(s_{1})ds_{1}da_{1}$ $\displaystyle=$ $\displaystyle c^{2}\mathbb{E}[|\mathcal{D}^{\pi}(\omega_{0})|^{2}].$ $$

For the right-hand side of equation [62](https://arxiv.org/html/2509.24991v1#A6.E62), we use empirical processes (Geer, 2000) to estimate the variance term in equation [62](https://arxiv.org/html/2509.24991v1#A6.E62). In order to do so, we first show that the Bellman residual is zero-mean sub-Gaussian. From the definition of Bellman operator equation [3](https://arxiv.org/html/2509.24991v1#S3.E3), the expectation of the Bellman residual is 0, i.e., $\mathbb{E}\varepsilon_{i}=0$ for all $i=1,\cdots,n$. From Assumption equation [2](https://arxiv.org/html/2509.24991v1#Thmtheorem2) and Lemma [3](https://arxiv.org/html/2509.24991v1#Thmtheorem3), we can know that the Bellman residual is bounded:

$$ $|r(\omega_{0}^{i})+\gamma Q^{\pi}(\omega_{1}^{(i)})-Q^{\pi}(\omega_{0}^{(i)})|\leq\|r\|_{\mathcal{H}}+(1-\gamma)\|Q^{\pi}\|_{\mathcal{H}}$ $$

where the right-hand side because $\max_{\omega}f(\omega)=\langle f,K(\cdot,\omega)\rangle_{\mathcal{H}}\leq\|K(\cdot,\omega)\|_{\mathcal{H}}\|f\|_{\mathcal{H}}$ for any $f\in\mathcal{H}$. So $\varepsilon_{i}$ is sub-Gaussian.

For natation simplicity, first define the empirical inner product and empirical norm for any pair of functions $f_{1}$ and $f_{2}$ defined on $\{\omega_{0}^{(i)}\}$:

$$ $\langle f_{1},f_{2}\rangle_{n}=\frac{1}{n}\sum_{i=1}^{n}f_{1}(\omega_{0}^{(i)})f_{2}(\omega_{0}^{(i)}),\quad,\|f_{1}\|_{n}^{2}=\langle f_{1},f_{1}\rangle_{n}.$ $$

The sub-Gaussianity of Bellman residual $\{\varepsilon_{i}\}$ allows us apply the following lemma to estimate the variance terms.

###### Lemma 17 .

Suppose the RKHS $\mathcal{H}$ satisfies Assumption [5](https://arxiv.org/html/2509.24991v1#Thmtheorem5).
Suppose that $\{\varepsilon_{i}\}_{i=1}^{n}$ are Bellman residual as defined in equation [12](https://arxiv.org/html/2509.24991v1#S4.E12).
Then, for all $t$ large enough,

$$ $\sup_{f\in\mathcal{H}}\frac{n^{\frac{1}{2}}\langle\bm{\varepsilon},f\rangle_{n}}{{\|f\|_{n}^{1-\beta}\|f\|^{\beta}_{\mathcal{H}}\left|\log\frac{\|f\|_{n}}{\|f\|_{\mathcal{H}}}\right|^{\kappa}}}>t,$ (64) $$

with probability at most $C_{2}\exp(-C_{1}t^{2})$ with some positive constants $C_{1}$ and $C_{2}$.

We can substitute equation [62](https://arxiv.org/html/2509.24991v1#A6.E62) and equation [64](https://arxiv.org/html/2509.24991v1#A6.E64) in Lemma [17](https://arxiv.org/html/2509.24991v1#Thmtheorem17) into the oracle equation [62](https://arxiv.org/html/2509.24991v1#A6.E62):

$$ $\displaystyle(1-c\gamma)\|\mathcal{D}^{\pi}\|_{n}^{2}+\lambda\|\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}$ (65) $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}\left(n^{-1/2}\right)\|\mathcal{D}^{\pi}\|_{n}^{1-\beta}\|\mathcal{D}^{\pi}\|_{\mathcal{H}}^{\beta}\left|\log\frac{\|\mathcal{D}^{\pi}\|_{n}}{\|\mathcal{D}^{\pi}\|_{\mathcal{H}}}\right|^{\kappa}+\lambda\langle Q^{\pi},\hat{Q}^{\pi}\rangle_{\mathcal{H}}.$ $$

Case I $\|\hat{Q}^{\pi}\|_{\mathcal{H}}\geq\|Q^{\pi}\|_{\mathcal{H}}$, equation [65](https://arxiv.org/html/2509.24991v1#A6.E65) yields two subcases, either

$$ $\displaystyle(1-c\gamma))\|\mathcal{D}^{\pi}\|_{n}^{2}+\lambda\|\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}$ (66) $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}\left(n^{-1/2}\right)\|\mathcal{D}^{\pi}\|_{n}^{1-\beta}\|\hat{Q}^{\pi}\|_{\mathcal{H}}^{\beta}\left||\log{\|\mathcal{D}^{\pi}\|_{n}}|+|\log{\|\hat{Q}^{\pi}\|_{\mathcal{H}}}|\right|^{\kappa}$ $$

or

$$ $(1-c\gamma)\|\mathcal{D}^{\pi}\|_{n}^{2}+\lambda\|\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}\leq\lambda\langle Q^{\pi},\hat{Q}^{\pi}\rangle_{\mathcal{H}}+\mathcal{O}_{p}(n^{-\frac{1}{2}})\|\hat{Q}^{\pi}\|_{\mathcal{H}}^{2}.$ (67) $$

Solving equation [66](https://arxiv.org/html/2509.24991v1#A6.E66) yields

$$ $\displaystyle\|\mathcal{D}^{\pi}\|_{n}=({1-c\gamma})^{\frac{\beta}{2}-1}\mathcal{O}_{p}(n^{-\frac{1}{2}})\lambda^{-\beta}(|\log n|+|\log\lambda|)^{\kappa},$ (68) $\displaystyle\|\hat{Q}^{\pi}\|_{\mathcal{H}}=({1-c\gamma})^{\frac{\beta-1}{2}}\mathcal{O}_{p}(n^{-\frac{1}{2}})\lambda^{-\frac{1+\beta}{2}}(|\log n|+|\log\lambda|)^{\kappa}.$ $$

Solving equation [67](https://arxiv.org/html/2509.24991v1#A6.E67) yields

$$ $\displaystyle\|\mathcal{D}^{\pi}\|_{n}\leq\frac{2}{1-c\gamma}\lambda\|Q^{\pi}\|_{\mathcal{H}},$ (69) $\displaystyle\|\hat{Q}^{\pi}\|_{\mathcal{H}}\leq 2\|Q^{\pi}\|_{\mathcal{H}}.$ $$

Case II $\|\hat{Q}^{\pi}\|_{\mathcal{H}}\leq\|Q^{\pi}\|_{\mathcal{H}}$, equation [65](https://arxiv.org/html/2509.24991v1#A6.E65) yields another two subcases, either

$$ $(1-c\gamma)\|\mathcal{D}^{\pi}\|_{n}^{2}\leq\mathcal{O}_{p}(n^{-1/2})\|\mathcal{D}^{\pi}\|_{n}^{1-\beta}\|Q^{\pi}\|_{\mathcal{H}}^{\beta},$ (70) $$

or

$$ $(1-c\gamma)\|\mathcal{D}^{\pi}\|_{n}^{2}\leq 2\lambda\|Q^{\pi}\|_{\mathcal{H}}^{2}.$ (71) $$

It follows that either equation [70](https://arxiv.org/html/2509.24991v1#A6.E70) holds or

$$ $\|\mathcal{D}^{\pi}\|_{n}\leq(1-c\gamma)^{\frac{-1}{1+\beta}}\mathcal{O}_{p}(n^{-\frac{1}{2+2\beta}}).$ (72) $$

Now we can summarize equation [69](https://arxiv.org/html/2509.24991v1#A6.E69), equation [70](https://arxiv.org/html/2509.24991v1#A6.E70), equation [71](https://arxiv.org/html/2509.24991v1#A6.E71), and equation [72](https://arxiv.org/html/2509.24991v1#A6.E72). We can notice that by selecting

$$ $\lambda=\mathcal{O}((1-c\gamma)^{\frac{\beta}{2+2\beta}}n^{-\frac{1}{2+2\beta}}|\log n|^{\frac{\kappa}{1+\beta}}),$ (73) $$

we can have the final result,

$$ $\displaystyle\|\mathcal{D}^{\pi}\|_{n}\leq\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{2+\beta}{2+2\beta}}n^{-\frac{1}{2+2\beta}}|\log n|^{\frac{\kappa}{1+\beta}}\right)\|Q^{\pi}\|_{\mathcal{H}},$ (74) $\displaystyle\|\hat{Q}^{\pi}\|_{\mathcal{H}}\leq\mathcal{O}_{p}(1)\|Q^{\pi}\|_{\mathcal{H}}.$ (75) $$

###### Lemma 17 .

### F.1 Proof of Lemma 17

To proof Lemma [17](https://arxiv.org/html/2509.24991v1#Thmtheorem17), we first need the following lemma from Geer (2000)

###### Lemma 18 (Corollary 8.3 in Geer ( 2000 ) ) .

Let $a>0$, $R>0$, and $\mathcal{H}$ be a function space.
Suppose that $\sup_{g\in\mathcal{H}}\|f\|_{L_{\infty}}\leq R$ for and $\bm{\varepsilon}=\{\varepsilon_{i}\}_{i=1}^{n}$ are independent zero-mean sub-Gaussian random variables.
If there exists some universal positive constant $C$ satisfying

$$ $a\geq Cn^{-\frac{1}{2}}\bigg(\int^{R}_{0}H^{\frac{1}{2}}(u,\|\cdot\|_{L_{\infty}},\mathcal{H})du\vee R\bigg),$ (76) $$

then we have

$$ $\mathbb{P}\left(\sup_{f\in\mathcal{H}}\left|\langle\bm{\varepsilon},f\rangle_{n}\right|\geq a\right)\leq 2\exp\biggl(-\tilde{C}\frac{na^{2}}{R^{2}}\biggr),$ (77) $$

for some positive $\tilde{C}$.

###### Proof.

Let $\mathcal{B}=\{f:\|f\|_{\mathcal{H}}\leq 1\}$ be the unit ball in $\mathcal{H}$. Recall from Assumption [5](https://arxiv.org/html/2509.24991v1#Thmtheorem5) that

$$ $H(\delta,\|\cdot\|_{L_{\infty}},\mathcal{B})\leq C\delta^{-2\beta}\left|\log\delta\right|^{2\kappa},$ $$

for some positive constant $C$, $\kappa$, and $\beta\in[0,1)$.
Hence,

$$ $\displaystyle\int_{0}^{R}\left(H(u,\|\cdot\|_{L_{\infty}},\mathcal{B})\right)^{\frac{1}{2}}d{u}\leq C\int_{0}^{R}u^{-\beta}\bigl|\log u\bigr|^{\kappa}d{u}\leq CR^{1-\beta}\bigl|\log R\bigr|^{\kappa}.$ $$

One may readily check that
for all $R<1$ and $a\geq n^{-1/2}CR^{1-\beta}\bigl|\log R\bigr|^{\kappa}$, the condition equation [76](https://arxiv.org/html/2509.24991v1#A6.E76) is met,
and thus by equation [77](https://arxiv.org/html/2509.24991v1#A6.E77), we have

$$ $\displaystyle\mathbb{P}\biggl(\sup_{f\in\mathcal{H},\|f\|_{n}\leq R}n^{\frac{1}{2}}|{\langle\bm{\omega},f\rangle_{n}}|\geq R^{1-\beta}|\log R|^{\kappa}\biggr)$ $\displaystyle=\mathbb{P}\biggl(\sup_{f\in\mathcal{H},\|f\|_{n}\leq R}\bigl|\langle\bm{\omega},f\rangle_{n}\bigr|\geq a\biggr)$ $\displaystyle\leq 2\exp(-C_{1}\frac{na^{2}}{R^{2}}),$ (78) $$

for some positive constant $C_{1}$.

Let $h=f/\|f\|_{\mathcal{H}}$. Then, the left-hand-side of the inequality equation [64](https://arxiv.org/html/2509.24991v1#A6.E64) becomes

$$ $\sup_{h\in\mathcal{H}}\frac{|{\langle\bm{\varepsilon},h\rangle_{n}}|}{{\|h\|_{n}^{1-\beta}}\bigl|\log\|h\|_{n}\bigr|^{\kappa}}.$ $$

We then can give the following upper bound for its tail distribution:

$$ $\displaystyle\mathbb{P}\Biggl(\sup_{h\in\mathcal{H}}\frac{|{\langle\bm{\varepsilon},h\rangle_{n}}|}{{\|h\|_{n}^{1-\beta}}\bigl|\log\|h\|_{n}\bigr|^{\kappa}}>t\Biggr)$ $\displaystyle={}$ $\displaystyle\mathbb{P}\Biggl(\bigcup_{i=0}^{\infty}\biggl\{\sup_{h\in\mathcal{H}}\frac{|{\langle\bm{\varepsilon},h\rangle_{n}}|}{{\|h\|_{n}^{1-\beta}}\bigl|\log\|h\|_{n}\bigr|^{\kappa}}>t\biggr\}\Biggr)$ $\displaystyle\leq{}$ $\displaystyle\mathbb{P}\Biggl(\bigcup_{i=0}^{\infty}\biggl\{\sup_{h\in\mathcal{H},\|h\|_{n}\in(2^{-i-1},2^{-i}]}n^{\frac{1}{2}}|{\langle\bm{\varepsilon},h\rangle_{n}}|>t2^{-{(i+1)}{(1-\beta)}}(i+1)^{\kappa}\biggr\}\Biggr)$ $\displaystyle\leq{}$ $\displaystyle\sum_{i=0}^{\infty}\mathbb{P}\biggl(\sup_{h\in\mathcal{H},\|h\|_{n}\leq 2^{-i}}n^{\frac{1}{2}}|{\langle\bm{\varepsilon},f\rangle_{n}}|>t2^{-{(i+1)}{(1-\beta)}}i^{\kappa}\biggr)$ $\displaystyle\leq{}$ $\displaystyle\sum_{i=0}^{\infty}2\exp(-C_{2}t^{2}2^{\beta i}i^{\kappa})$ $\displaystyle\leq{}$ $\displaystyle\sum_{i=1}^{\infty}2\bigl(\exp(-C_{2}t^{2})\bigr)^{i}$ $\displaystyle\leq{}$ $\displaystyle C_{3}\exp(-C_{2}t^{2}),$ $$

where the fifth line follows from applying equation [78](https://arxiv.org/html/2509.24991v1#A6.E78) with $R=2^{-i}$ and $a=tn^{-1/2}2^{-{(i+1)}{(1-\beta)}}i^{\kappa}$.
∎

###### Lemma 18 (Corollary 8.3 in Geer ( 2000 ) ) .

###### Proof.

## Appendix G Proof of Corollary 10

###### Proof.

The proofs relies on the following so-called sampling inequality of RKHSs

$$ $\|f\|^{2}_{L_{2}(\sigma^{\pi}_{0})}\leq\|f\|_{n}^{2}+\delta_{\mathcal{H},n}\|f\|_{\mathcal{H}}^{2}$ (79) $$

where $\delta_{\mathcal{H},n}$ depends on the distribution of data $\omega_{0}^{(i)}$ and the structure of RKHS $\mathcal{H}$.

Case I: $\mathcal{H}_{\mathcal{S}}=\{s\}_{s=1}^{S}$ and $\mathcal{A}=\{a\}_{a=1}^{A}$

In this case, we can note the the RKHS is a discrete set $\{\omega_{j}\}_{j=1}^{M}$ where $M=SA$, $\sigma^{\pi}_{0}(\omega_{j})=\frac{W_{j}}{M}$ is the weight on element $\omega_{j}$ (according to our assumption, $c<W_{j}<C$), and data $\{\omega_{0}^{(i)}\}$ are i.i.d. samples from $\{\omega_{j}\}_{j=1}^{M}$ following $\sigma^{\pi}_{0}$.

Because the kernel $K(\omega,\omega^{\prime})=\delta_{s=s^{\prime}}\delta_{a=a^{\prime}}=\delta_{\omega=\omega^{\prime}}$, we can derive that the RKHS is equipped with the inner product

$$ $\langle f,g\rangle_{\mathcal{H}}=\sum_{j=1}^{M}f_{j}g_{j},\quad f,g\in\mathcal{H}$ $$

where $f_{j}$ and $g_{j}$ are the values of $f$ and $g$ on $\omega_{j}$, respectively. Also, the $L_{2}$ norm and empirical norm are

$$ $\displaystyle\|f\|_{L_{2}(\sigma^{\pi}_{0})}^{2}=\sum_{j=1}^{M}f_{j}^{2}W_{j},\quad\|f\|_{n}^{2}=\frac{1}{n}\sum_{i=1}^{n}f^{2}(\omega_{i}^{0}).$ $$

Let $I_{i,j}$ denote the indicator function that $\omega_{0}^{(i)}=\omega_{j}$, then we can rewrite the empirical norm as follows:

$$ $\displaystyle\|f\|_{n}^{2}=$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}f^{2}(\omega_{i}^{0})=\sum_{j=1}^{M}f_{j}^{2}\frac{\sum_{i=1}^{n}I_{i,j}}{n}$ (80) $\displaystyle=$ $\displaystyle\sum_{j=1}^{M}f_{j}^{2}\frac{W_{j}}{M}+\sum_{j=1}^{M}f_{j}^{2}\left(\frac{\sum_{i=1}^{n}I_{i,j}}{n}-\frac{W_{j}}{M}\right)$ $\displaystyle=$ $\displaystyle\|f\|^{2}_{L_{2}(\sigma^{\pi}_{0})}+\sum_{j=1}^{M}f_{j}^{2}\left(\frac{Z_{j}}{n}-\frac{W_{j}}{M}\right)$ $$

where $[Z_{j}]_{j=1}^{M}$ is Multinomial distributed with $n$ trials, $M$ mutually exclusive events, and probability vector $[W_{j}/m]_{j=1}^{M}$.

By properties of Multinomial distribution, the last term in equation [80](https://arxiv.org/html/2509.24991v1#A7.E80) has expecatation

$$ $\mathbb{E}\sum_{j=1}^{M}f_{j}^{2}\left(\frac{Z_{j}}{n}-\frac{W_{j}}{M}\right)=\sum_{j=1}^{M}f_{j}^{2}\left(\frac{nW_{j}/m}{n}-\frac{W_{j}}{M}\right)=0,$ (81) $$

and variance

$$ $\displaystyle\text{Var}\left(\sum_{j=1}^{M}f_{j}^{2}\left(\frac{Z_{j}}{n}-\frac{W_{j}}{M}\right)\right)=$ $\displaystyle\frac{1}{n^{2}}\sum_{j,l=1}^{m}f_{j}^{2}f_{l}^{2}\text{Cov}\left(Z_{j},Z_{l}\right)$ (82) $\displaystyle=$ $\displaystyle\frac{1}{n^{2}}\left(\sum_{j=1}^{m}f_{j}^{2}\frac{nW_{j}}{M}(1-\frac{W_{j}}{M})-\sum_{j\neq l}f_{j}^{2}f_{l}^{2}\frac{nW_{j}W_{l}}{M^{2}}\right)$ $\displaystyle\leq$ $\displaystyle\mathcal{O}(\frac{1}{n^{1+\nu}}\|f\|_{\mathcal{H}}^{2})$ $$

where the last line is from our assumption that $M\geq n^{\nu}$ for some $\nu\in(0,1)$.

Substitute equation [81](https://arxiv.org/html/2509.24991v1#A7.E81) and equation [82](https://arxiv.org/html/2509.24991v1#A7.E82) into equation [80](https://arxiv.org/html/2509.24991v1#A7.E80), it is straightforward to derive the sampling inequality

$$ $\|f\|_{n}^{2}\leq\|f\|_{L_{2}(\sigma^{\pi}_{0})}^{2}+\mathcal{O}_{p}\left(\frac{1}{n^{(1+\nu)/2}}\right)\|f\|_{\mathcal{H}}^{2}.$ (83) $$

It is straightforward to see that the covering number of $\mathcal{H}$ under $L_{\infty}$ is directly the covering number of $\mathcal{H}$ is $M/\delta$ so its entropy is

$$ $H(\delta,\|\cdot\|_{L_{\infty}},\mathcal{H})\leq\nu\log n+|\log\delta|.$ $$

Substitute this result into the sampling inequality, we can have the final result:

$$ $\displaystyle\|f_{t}-Q^{\pi}\|_{L_{2}(\sigma^{\pi}_{0})}\leq$ $\displaystyle\|f_{t}-Q^{\pi}\|_{n}+\mathcal{O}_{p}\left(\frac{1}{n^{(1+\nu)/4}}\right)\|f_{t}-Q^{\pi}\|_{\mathcal{H}}$ $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}\left((1-c\gamma)^{-1}n^{-\frac{1}{2}}|\log n|^{1/2}\right)+\mathcal{O}_{p}\left(\frac{1}{n^{(1+\nu)/4}}\right)\|f_{t}-Q^{\pi}\|_{\mathcal{H}}$ $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}\left((1-c\gamma)^{-1}n^{-\frac{1}{2}}|\log n|^{1/2}\right)+\mathcal{O}_{p}\left(\frac{1}{n^{(1+\nu)/4}}\right)\|Q^{\pi}\|_{\mathcal{H}}$ $$

where the second line is from the empirical error in Theorem [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9) with $\beta=0$ and $\kappa=1/2$ and the last line is from the RKHS norm of $f_{t}$ in Theorem [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9).

Case II: $\mathcal{H}_{\mathcal{S}}$ is a Sobolev space and $\mathcal{A}=\{a\}_{a=1}^{A}$

For spaces of continuous functions, we first need to define a concept called filled distance of data set so that we can apply the sampling inequality.

###### Definition 19 .

Given $n$ points $\mathbb{X}=\{\mathbb{x}_{i}\}_{i=1}^{n}$ on the set $\mathcal{X}$ equipped with norm $\|\cdot\|$, the fill distance of the set $\mathbb{X}$ is

$$ $q_{\mathbb{X}}=\max_{\mathbb{x}\in\mathcal{X}}\min_{\mathbb{x}_{i}\in\mathbb{X}}\|\mathbb{x}_{i}-\mathbb{x}\|_{2}.$ $$

Using the concept of fill distance, we have the following Lemma from Tuo et al. (2020); Rieger (2008); Utreras (1988)

###### Proposition 20 (Proposition 2.6 in Tuo et al. ( 2020 ) ) .

Let $\mathcal{H}$ be a Sobolev space for function defined on a compact and convex set $\mathcal{X}$ with smoothness parameter $m$. Let $\mathbb{X}=\{\mathbb{x}_{i}\}_{i=1}^{n}$ be a set of scattered point on $\mathcal{X}$ with fill distance $q_{\mathbb{X}}$ and $\|\cdot\|_{n}$ is the empirical norm induced by $\mathbb{X}$. Then there exists a constant $C$ (depending only on $m$ and $\mathcal{X}$) such that for any $f\in\mathcal{H}$:

$$ $\|f\|^{2}_{L_{2}(\mathcal{X})}\leq C\left(\|f\|^{2}_{n}+q_{\mathbb{X}}^{2m}\|f\|_{\mathcal{H}}^{2}\right).$ $$

We also need the following proposition for the distribution of fill distance:

###### Proposition 21 (Proposition 3 in Krieg & Sonnleitner ( 2024 ) ) .

Let $\{\mathbb{x}_{i}\sim\sigma\}_{i=1}^{n}$ be i.i.d. distributed on a compact and convex set $\mathcal{X}$. Let $\Phi(\varepsilon)=\varepsilon^{d}$. If there exists a positive number $\varepsilon_{0}$ such that $\sigma(B_{\varepsilon}(\mathbb{x}))\geq\Phi(\varepsilon)$ for all $\varepsilon\leq\varepsilon_{0}$ and $\mathbb{x}\in B$ where $B_{\varepsilon}(\mathbb{x})$ is a sphere centered at $\mathbb{x}$ with radius $\varepsilon$. Then there exist positive constants $c_{1}$, $c_{2}$, $c_{3}$, and $b_{0}$ such that for any $b>b_{0}$ we have

$$ $\Pr\left(\max_{\mathbb{x}\in\mathcal{S}}\inf_{i}\|\mathbb{x}-\mathbb{x}_{i}\|\geq c_{1}\Phi^{-1}(\frac{b\log n}{n})\right)\leq c_{2}n^{1-c_{3}b}.$ $$

From Proposition [21](https://arxiv.org/html/2509.24991v1#Thmtheorem21), we can derive that the filled distance on $\mathcal{X}$ with intrinsic dimension $d$ is

$$ $q_{\mathbb{X}}=\mathcal{O}_{p}(n^{-1/d}\log n).$ (84) $$

Lastly, from Geer (2000); Birman & Solomjak (1967), we have the entropy of Sobolev spaces $\mathcal{H}$ with smoothness $m$ defined on compact $d$-dimensional domain is

$$ $H(\delta,\|\cdot\|_{L_{\infty}},\mathcal{H})\leq C_{1}\delta^{-\frac{d}{m}}$ (85) $$

where $C_{1}$ is some constant independent of $\delta$.

Now we are ready to prove the sampling inequality in the form equation [79](https://arxiv.org/html/2509.24991v1#A7.E79) for our RKHS. According to our assumption, $\mathcal{H}_{\mathcal{S}}$ is a Sobolev space with smoothness parameter $m$ embedded on a domain with intrinsic dimension $d$ and $\mathcal{H}_{\mathcal{A}}$ is a discrete set. So it is straightforward to derive that the overall RKHS $\mathcal{H}$ is a vector-valued function $(f_{1},\cdots,f_{A})$ where each $f_{a}\in\mathcal{H}_{\mathcal{S}}$, and $\mathcal{H}$ is define as

$$ $\mathcal{H}=\left\{f=(f_{1},\cdots,f_{A}):\|f\|_{\mathcal{H}}^{2}=\sum_{a=1}^{A}\|f_{a}\|^{2}_{\mathcal{H}_{\mathcal{S}}}<\infty\right\}.$ $$

Because $f_{t},Q^{\pi}\in\mathcal{H}$, we then have

$$ $\displaystyle\|f_{t}-Q^{\pi}\|_{L_{2}(\sigma^{\pi}_{0})}^{2}=$ $\displaystyle\sum_{a=1}^{A}\|f_{a,t}-Q^{\pi}_{a}\|_{L_{2}(\sigma^{\pi}_{0})}^{2}$ (86) $\displaystyle\leq$ $\displaystyle\sum_{a=1}^{A}C\left(\|f_{a,t}-Q^{\pi}_{a}\|_{n}^{2}+q_{\bm{\omega}_{0}}^{2m}\|f_{a,t}-Q^{\pi}_{a}\|_{\mathcal{H}_{\mathcal{S}}}^{2}\right)$ $\displaystyle\leq$ $\displaystyle\sum_{a=1}^{A}C\left(\|f_{a,t}-Q^{\pi}_{a}\|_{n}^{2}+\mathcal{O}_{p}(n^{-\frac{2m}{d}}|\log n|^{2m})\|f_{a,t}-Q^{\pi}_{a}\|_{\mathcal{H}_{\mathcal{S}}}^{2}\right)$ $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{4m+d}{2m+2d}}n^{-\frac{2m}{2m+d}}\right)+\mathcal{O}_{p}(n^{-\frac{2m}{d}}|\log n|^{2m})\|Q^{\pi}\|_{\mathcal{H}}^{2}$ $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}\left((1-c\gamma)^{-\frac{4m+d}{2m+2d}}n^{-\frac{2m}{2m+d}}\right)$ $$

where the second line is from Proposition [20](https://arxiv.org/html/2509.24991v1#Thmtheorem20), the third line is from the distribution of fill distance equation [84](https://arxiv.org/html/2509.24991v1#A7.E84), the fourth line is from Theorem [7](https://arxiv.org/html/2509.24991v1#Thmtheorem7) with $\beta=\frac{d}{2m}$ and $\kappa=0$.

Case III: $\mathcal{H}_{\mathcal{S}}$ is a NTK and $\mathcal{A}=\{a\}_{a=1}^{A}$

According to Chen & Xu (2020), the NTK $N$ associated to a two-layer neural network on $\mathbb{S}^{d-1}$ is equivalent to the Laplace kernel $e^{-\|s-s^{\prime}\|}$ on $\mathbb{S}^{d-1}$. The Laplace kernel is a Matérn kernel with smoothness parameter $\nu=1/2$. Also, according to Corollary 1 in Tuo & Jeff Wu (2016), RKHS induced by Matérn kernel with smoothness parameter $\nu$ is equivalent to (fractional) Sobolev space with smoothness $m=\nu+d/2$.

Therefore, we can conclude that $\mathcal{H}$ is equivalent to a Sobolev space with smoothness $(d+1)/2$ embedded on $\mathbb{S}^{d-1}$, which has intrinsic dimension $d-1$. So Case III is a special case of Case II, i.e. Sobolev space with smoothness $m=(d+1)/2$ embedded on $d-1$ dimension. By substituting the value of $m$ and $d-1$ into equation [16](https://arxiv.org/html/2509.24991v1#S4.E16), we can have the final result.

Case IV: $\mathcal{H}_{\mathcal{S}}$ and $\mathcal{H}_{\mathcal{A}}$ are Gaussian RKHSs

Note that $K(\omega,\omega^{\prime})=e^{-\|\omega-\omega^{\prime}\|^{2}}$ is a Gaussian kernel on the hypercube $[0,1]^{d}$ with $d=d_{s}+d_{a}$. So $\mathcal{H}$ is a Gaussian RKHS on $[0,1]^{d}$.

From Chapter 4 in Rieger (2008), we have the sampling inequality:

$$ $\|f\|_{L_{2}(\sigma^{\pi}_{0})}\leq e^{c\log(cq_{\bm{\omega}_{0}})/\sqrt{q_{\bm{\omega}_{0}}}}\|f\|_{\mathcal{H}}+c\|f\|_{n},\quad\forall f\in\mathcal{H}$ (87) $$

for some generic constant $c>0$. Substitute the distribution of fill distance in equation [84](https://arxiv.org/html/2509.24991v1#A7.E84) into equation [87](https://arxiv.org/html/2509.24991v1#A7.E87), we can have

$$ $\|f\|_{L_{2}(\sigma^{\pi}_{0})}\leq c\|f\|_{n}+\mathcal{O}_{p}(e^{-n^{1/\sqrt{d}}})\|f\|_{\mathcal{H}},\quad\forall f\in\mathcal{H}.$ (88) $$

From Theorem 3 in Kühn (2011), the entropy of $\mathcal{H}$ is

$$ $H(\delta,\|\cdot\|_{\infty},\mathcal{B})\leq C_{1}|\log\delta|^{d+1}$ (89) $$

where $C_{1}$ is some generic constant.

So we can have

$$ $\displaystyle\|f_{t}-Q^{\pi}\|_{L_{2}(\sigma^{\pi}0)}\leq$ $\displaystyle c\|f_{t}-Q^{\pi}\|_{n}+\mathcal{O}_{p}(e^{-n^{1/\sqrt{d}}})\|f_{t}-Q^{\pi}\|_{\mathcal{H}}$ $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}((1-c\gamma)n^{-\frac{1}{2}}|\log n|^{(d+1)/2})+\mathcal{O}_{p}(e^{-n^{1/\sqrt{d}}})\|Q^{\pi}\|_{\mathcal{H}}$ $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}((1-c\gamma)n^{-\frac{1}{2}}|\log n|^{(d+1)/2})$ $$

where the first line is from the sampling inequality equation [88](https://arxiv.org/html/2509.24991v1#A7.E88) and the second line is from entropy equation [89](https://arxiv.org/html/2509.24991v1#A7.E89) and Theorem [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9) with $\beta=0$ and $\kappa=(d+1)/2$.

∎

###### Proof.

###### Definition 19 .

###### Proposition 20 (Proposition 2.6 in Tuo et al. ( 2020 ) ) .

###### Proposition 21 (Proposition 3 in Krieg & Sonnleitner ( 2024 ) ) .

## Appendix H Proof of Lemma 11

###### Proof.

We generalize the proof for Proposition 3.1 in Liu et al. (2019), following its main lines of reasoning while incorporating additional techniques of RKHS. For notation simplicity, denote the $L_{2}$ inner product of on $\mathcal{A}$ as $\langle f,g\rangle_{\mathcal{A}}=\int_{\mathcal{A}}f(a)g(a)da$.

The Lagrangian of equation [20](https://arxiv.org/html/2509.24991v1#S5.E20) takes the form

$$ $\mathbb{E}_{n}\left[\Delta_{k}\langle f^{(k)}(s,\cdot)\pi(\cdot|s)\rangle_{\mathcal{A}}-\text{KL}\left(\pi(\cdot|s)\|\pi^{k}(\cdot|s)\right)\right]+\mathbb{E}_{n}\left[\left(\int_{\mathcal{A}}\pi(a|s)-1\right)\Lambda(s)\right]$ (90) $$

where $\Lambda(s)$ is the $L_{2}$ Lagrange multiplier defined on $\{s^{(i)}_{0}\}$. By taking the functional derivative of equation [90](https://arxiv.org/html/2509.24991v1#A8.E90) with respective to $\pi$, we can have

$$ $\Delta_{k}f^{(k)}(s,a)+F(s,a)-\left(\log\pi(a|s)+1+\log Z(s)\right)+\Lambda(s)=0$ (91) $$

where $Z(s)=\int_{\mathcal{A}}e^{F(s,a)}da$. Then equation [91](https://arxiv.org/html/2509.24991v1#A8.E91) should holds on any $s\in\{s^{(i)}_{0}\}$ and $a\in\mathcal{A}$ such that $|F(s,a|$ and $\log Z(s)$ is bounded. According to our assumption that $1>\pi^{(k)}>0$, any $(s,a)\in\{s^{(i)}_{0}\}\times\mathcal{A}$ satisfies this condition. Then we can solve equation [91](https://arxiv.org/html/2509.24991v1#A8.E91), which yields

$$ $\pi(a|s)=\pi^{k}(a|s)\exp\left\{\Delta_{k}f^{(k)}(s,a)+\Lambda(s)-1-\log Z(s)\right\}.$ (92) $$

In equation [92](https://arxiv.org/html/2509.24991v1#A8.E92), we can note that $\pi^{k}(a|s)$ must be proportional to $\pi^{k}(a|s)\exp\{\Delta_{k}f^{(k)}(s,a)\}$ because it is a density on $a$.
∎

###### Proof.

## Appendix I Proof of Theorem 12

###### Proof.

From direct calculations, we have for any $s\in\mathcal{S}$

$$ $\displaystyle\text{KL}\left(\pi^{*}(\cdot|s)||\pi^{k+1}(\cdot|s)\right)-\text{KL}\left(\pi^{*}(\cdot|s)||\pi^{k}(\cdot|s)\right)$ $\displaystyle=$ $\displaystyle\langle\log\frac{\pi^{k}}{\pi^{k+1}},\pi^{*}-\pi^{k+1}\rangle_{\mathcal{A}}-\langle\log\frac{\pi^{k+1}}{\pi^{k}},\pi^{k+1}\rangle_{\mathcal{A}}$ $\displaystyle=$ $\displaystyle\Delta_{k}\langle f^{(k)},\pi^{*}-\pi^{k}\rangle_{\mathcal{A}}-\Delta_{k}\langle f^{(k)},\pi^{k+1}-\pi^{k}\rangle_{\mathcal{A}}-\langle\log\frac{\pi^{k+1}}{\pi^{k}},\pi^{k+1}\rangle_{\mathcal{A}}$ (93) $\displaystyle=$ $\displaystyle\Delta_{k}\langle Q^{(k)},\pi^{*}-\pi^{k}\rangle_{\mathcal{A}}-\Delta_{k}\langle f^{(k)}-Q^{(k)},\pi^{*}-\pi^{k+1}\rangle_{\mathcal{A}}$ $\displaystyle-\Delta_{k}\langle Q^{(k)},\pi^{*}-\pi^{k+1}\rangle_{\mathcal{A}}-\langle\log\frac{\pi^{k+1}}{\pi^{k}},\pi^{k+1}\rangle_{\mathcal{A}}$ $\displaystyle\leq$ $\displaystyle\Delta_{k}\langle Q^{(k)},\pi^{*}-\pi^{k}\rangle_{\mathcal{A}}-\Delta_{k}\langle f^{(k)}-Q^{(k)},\pi^{*}-\pi^{k+1}\rangle_{\mathcal{A}}$ (94) $\displaystyle-\int_{\mathcal{A}}\Delta_{k}Q^{(k)}(s,a)\left(\pi^{*}-\pi^{k+1}\right)da-\frac{1}{2}\left(\int_{\mathcal{A}}\left|\pi^{k+1}(a|s)-\pi^{k}(a|s)\right|da\right)^{2}$ $\displaystyle\leq$ $\displaystyle\Delta_{k}\langle Q^{(k)},\pi^{*}-\pi^{k}\rangle_{\mathcal{A}}-\Delta_{k}\langle f^{(k)}-Q^{(k)},\pi^{*}-\pi^{k+1}\rangle_{\mathcal{A}}$ $\displaystyle+\|\Delta_{k}Q^{(k)}(s,)\|_{L_{\infty}(\mathcal{A})}\int_{\mathcal{A}}\left|\pi^{*}-\pi^{k+1}\right|da-\frac{1}{2}\left(\int_{\mathcal{A}}\left|\pi^{k+1}(a|s)-\pi^{k}(a|s)\right|da\right)^{2}$ $\displaystyle\leq$ $\displaystyle{\Delta_{k}\langle Q^{(k)},\pi^{*}-\pi^{k}\rangle_{\mathcal{A}}}-{\Delta_{k}\langle f^{(k)}-Q^{(k)},\pi^{*}-\pi^{k+1}\rangle_{\mathcal{A}}}+\Delta^{2}_{k}\frac{\|r\|_{L_{\infty}}}{1-\gamma}$ (95) $$

where equation [93](https://arxiv.org/html/2509.24991v1#A9.E93) is from the NPG update rule equation [19](https://arxiv.org/html/2509.24991v1#S5.E19), equation [94](https://arxiv.org/html/2509.24991v1#A9.E94) is from Pinsker inequality, equation [95](https://arxiv.org/html/2509.24991v1#A9.E95) is from the fact that $xy-y^{2}\leq x^{2}$ and $Q^{(k)}\leq\max_{s,a}|r(s,a)|/(1-\gamma)$.

Taking expectation $\mathbb{E}_{S\sim\nu^{*}}$ on equation [95](https://arxiv.org/html/2509.24991v1#A9.E95), we can have:

$$ $\displaystyle\mathbb{E}_{S\sim\nu^{*}}\left[\text{KL}\left(\pi^{*}(\cdot|s)||\pi^{k+1}(\cdot|s)\right)-\text{KL}\left(\pi^{*}(\cdot|S)||\pi^{k+1}(\cdot|S)\right)\right]$ $\displaystyle\leq$ $\displaystyle{\mathbb{E}_{S\sim\nu^{*}}\Delta_{k}\langle Q^{(k)}(\cdot,S),\pi^{*}(\cdot|S)-\pi^{k}\pi^{*}(\cdot|S)\rangle_{\mathcal{A}}}$ (96) $\displaystyle-\mathbb{E}_{S\sim\nu^{*}}{\Delta_{k}\langle f^{(k)}(\cdot,S)-Q^{(k)}(\cdot,S),\pi^{*}(\cdot|S)-\pi^{k+1}(\cdot|S)\rangle_{\mathcal{A}}}$ (97) $\displaystyle+\Delta^{2}_{k}\frac{\|r\|_{L_{\infty}}}{1-\gamma}$ $$

For equation [96](https://arxiv.org/html/2509.24991v1#A9.E96), we can use the performance difference lemma in Kakade & Langford (2002) (equivalent to Liu et al. (2019) Lemma 5.1):

###### Lemma 22 (Performance Difference Lemma) .

For $\mathcal{R}[\pi]$ defined in equation [21](https://arxiv.org/html/2509.24991v1#S5.E21), we have

$$ $\mathcal{R}[\pi]-\mathcal{R}[\pi^{*}]=\mathbb{E}_{S\sim\nu^{*}}[\langle Q^{\pi}(S,\cdot),\pi(\cdot|S)-\pi^{*}(\cdot|S)\rangle_{\mathcal{A}}].$ (98) $$

From equation [98](https://arxiv.org/html/2509.24991v1#A9.E98), we can directly have for equation [96](https://arxiv.org/html/2509.24991v1#A9.E96)

$$ ${\mathbb{E}_{S\sim\nu^{*}}\Delta_{k}\langle Q^{(k)}(\cdot,S),\pi^{*}(\cdot|S)-\pi^{k}\pi^{*}(\cdot|S)\rangle_{\mathcal{A}}}=\mathcal{R}[\pi^{*}]-\mathcal{R}[\pi^{k}].$ (99) $$

For equation [97](https://arxiv.org/html/2509.24991v1#A9.E97),

$$ $\displaystyle\left|\mathbb{E}_{S\sim\nu^{*}}{\Delta_{k}\langle f^{(k)}(\cdot,S)-Q^{(k)}(\cdot,S),\pi^{*}(\cdot|S)-\pi^{k+1}(\cdot|S)\rangle_{\mathcal{A}}}\right|$ $\displaystyle\leq$ $\displaystyle\Delta_{k}\|f^{(k)}-Q^{k}\|_{L_{\infty}}\left(\int\pi^{*}(a|s)\nu^{*}(s)dads+\int\pi^{k+1}(a|s)\nu^{*}(s)dads\right)$ $\displaystyle=$ $\displaystyle 2\Delta_{k}\|f^{(k)}-Q^{k}\|_{L_{\infty}}$ $$

Substitute the above upper bounds for equation [96](https://arxiv.org/html/2509.24991v1#A9.E96) and equation [97](https://arxiv.org/html/2509.24991v1#A9.E97) into equation [95](https://arxiv.org/html/2509.24991v1#A9.E95) and rearrange the terms, we have

$$ $\displaystyle\Delta_{k}\left(\mathcal{R}[\pi^{k}]-\mathcal{R}[\pi^{*}]\right)+\mathbb{E}_{S\sim\nu^{*}}\left[\text{KL}\left(\pi^{*}(\cdot|S)||\pi^{k+1}(\cdot|S)\right)-\text{KL}\left(\pi^{*}(\cdot|S)||\pi^{k}(\cdot|S)\right)\right]$ (100) $\displaystyle\leq$ $\displaystyle 2\Delta_{k}\|f^{(k)}-Q^{(k)}\|_{L_{\infty}}+\Delta^{2}_{k}(1-\gamma)^{-1}R^{(k)}.$ $$

By summing over all the $k$ in equation [100](https://arxiv.org/html/2509.24991v1#A9.E100), we can have the final result.
∎

###### Proof.

###### Lemma 22 (Performance Difference Lemma) .

## Appendix J Proof of Corollary 13

###### Proof.

The proof mainly relies on the following $L_{2}$ and $L_{\infty}$ norm embedding inequality

$$ $\|f\|_{L_{\infty}}\leq C\|f\|_{L_{2}(\mu)}^{\varphi}\|f\|_{\mathcal{H}}^{1-\varphi}$ (101) $$

for some constants $C$ and $0\leq\varphi\leq 1$ independent of $f$ and $\mu$ is any measure equivalent to the uniform measure on $\mathcal{S}\times\mathcal{A}$. Based on Assumption [1](https://arxiv.org/html/2509.24991v1#Thmtheorem1) that $\nu^{*}$ is lower bounded on $\mathcal{S}\times\mathcal{A}$, we can use equation [101](https://arxiv.org/html/2509.24991v1#A10.E101) and Theorem [9](https://arxiv.org/html/2509.24991v1#Thmtheorem9) to determine the parameters in Algorithm [1](https://arxiv.org/html/2509.24991v1#alg1) such that the $L_{\infty}$ error satisfies

$$ $\|f^{(k)}-Q^{(k)}\|_{L_{\infty}}\leq\frac{1}{\sqrt{k}}$ (102) $$

Then by substitute equation [102](https://arxiv.org/html/2509.24991v1#A10.E102) and $\Delta_{k}=1/\sqrt{k}$ into equation [22](https://arxiv.org/html/2509.24991v1#S5.E22), we can have the target result. We prove the cases one by one

Tabular: On the discrete set, it is obvious that

$$ $\|f\|_{L_{\infty}}=\max_{\omega\in\mathcal{S}\times\mathcal{A}}|f(\omega)\leq\sqrt{\sum_{\omega\in\mathcal{S}\times\mathcal{A}}f(\omega)^{2}}\leq\frac{\|f\|_{L_{2}(\nu^{*})}}{\min_{\omega}\nu^{*}}.$ (103) $$

By letting $n^{(k)}=\mathcal{O}(\frac{k\|\pi^{k}\|^{2}_{\mathcal{H}}}{(1-c\gamma)^{2}}\log\frac{k\|\pi^{k}\|_{\mathcal{H}}}{(1-c\gamma)}$ and $\beta=0$, $\kappa=1/2$ for the tabular case, we can derive from Theorem [16](https://arxiv.org/html/2509.24991v1#Thmtheorem16) that the required $\lambda^{(k)}$ for the optimal error rate is

$$ $\lambda^{(k)}=\mathcal{O}\left(n^{-\frac{1}{2}}|\log n|^{1}\right)=\mathcal{O}\left(\frac{(1-c\gamma)}{\sqrt{k}\|\pi^{k}\|_{\mathcal{H}}}{|\log\frac{k\|\pi^{k}\|_{\mathcal{H}}}{(1-c\gamma)}|^{\frac{1}{2}}}\right).$ $$

We then substitute equation [103](https://arxiv.org/html/2509.24991v1#A10.E103) into equation [15](https://arxiv.org/html/2509.24991v1#S4.E15):

$$ $\displaystyle\|f^{(k)}-Q^{(k)}\|_{L_{\infty}}\leq$ $\displaystyle\mathcal{O}_{p}\left((1-c\gamma)^{-1}n^{-\frac{1}{2}}|\log n|^{1/2}\right)\|Q^{(k)}\|_{\mathcal{H}}+\mathcal{O}_{p}\left(\frac{1}{n^{(1+\nu)/4}}\right)\|Q^{(k)}\|_{\mathcal{H}}$ (104) $\displaystyle\leq$ $\displaystyle\mathcal{O}_{p}\left(\frac{1}{\sqrt{k}}\right)+\mathcal{O}_{p}\left(\frac{1}{n^{(1+\nu)/4}}\right)\|Q^{(k)}\|_{\mathcal{H}}$ $$

where the second line is from Lemma [3](https://arxiv.org/html/2509.24991v1#Thmtheorem3).

From equation [104](https://arxiv.org/html/2509.24991v1#A10.E104), we can note that we also need to make sure that the second term on the right hand side is in the order $k^{-1/2}$. So we may need more samples so that $\mathcal{O}_{p}\left(\frac{1}{n^{(1+\nu)/4}}\right)\|Q^{(k)}\|_{\mathcal{H}}\leq\mathcal{O}(k^{-1/2})$. By solving this equation, we can have the target result.

Sobolev with intrinsic dimension $d$: According to the Gagliardo-Nirenberg inequality, when $\mathcal{H}$ is a Sobolev space with smoothness parameter $m$ and dimension $d$, we have

$$ $\|f\|_{L_{\infty}}\leq C\|f\|_{L_{2}(\nu^{*})}^{\frac{2m-d}{2m}}\|f\|_{\mathcal{H}}^{\frac{d}{2m}}.$ (105) $$

By letting $n^{(k)}=\mathcal{O}\left(\frac{\|\pi^{k}\|_{\mathcal{H}}^{\frac{2(2m+d)}{(2m-d)}}k^{\frac{2m+d}{2m-d}}}{(1-c\gamma)^{\frac{2m+d/2}{m}}}\right)$ and $\beta=\frac{d}{2m}$, $\kappa=0$ for the Sobolev case, we can derive from Theorem [16](https://arxiv.org/html/2509.24991v1#Thmtheorem16) that the required $\lambda^{(k)}$ for the optimal error rate is

$$ $\displaystyle\lambda=\mathcal{O}((1-c\gamma)^{\frac{d/2}{2m+d}}n^{-\frac{m}{2m+d}}|)=\mathcal{O}\left(\frac{(1-c\gamma)}{\|\pi\|_{\mathcal{H}}^{\frac{2m}{2m-d}}k^{\frac{m}{2m-d}}}\right)$ $$

Similar to the tabular case, we then substitute equation [105](https://arxiv.org/html/2509.24991v1#A10.E105) into equation [16](https://arxiv.org/html/2509.24991v1#S4.E16):

$$ $\displaystyle\|f^{(k)}-Q^{(k)}\|_{L_{\infty}}\leq\mathcal{O}_{p}\left(\left((1-c\gamma)^{-\frac{2m+d/2}{2m+d}}n^{-\frac{m}{2m+d}}\right)^{\frac{2m-d}{2m}}\|\pi^{(k)}\|_{\mathcal{H}}\right)\leq\mathcal{O}_{p}\left(\frac{1}{\sqrt{k}}\right).$ $$

NTK: As we have shown in Section [G](https://arxiv.org/html/2509.24991v1#A7) Case III that
the NTK $N$ associated to a two-layer neural network on $\mathbb{S}^{d-1}$ is equivalent to the (fractional) Sobolev space with smoothness $m=1/2+d/2$ with intrinsic dimension $d-1$. Substitute the smoothness $(1+d)/2$ and intrinsic dimension $d-1$ into the Sobolev case, we can have the result.

Gaussian: we use Lemma E.4 in Ding et al. (2024) for the interpolation inequality in Gaussian RKHS. It states that for any $f\in\mathcal{H}$, there exists a universal constant $C>0$ such that

$$ $\|f\|_{L_{\infty}}\leq C\|f\|_{L_{2}(\nu^{*})}^{1-\epsilon}\|f\|_{\mathcal{H}}^{\epsilon}$ (106) $$

for any $\epsilon>0$.

By letting $n^{(k)}=\mathcal{O}\left(\frac{\|\pi^{k}\|^{\frac{2}{1-\epsilon}}k^{\frac{1}{1-\epsilon}}}{(1-c\gamma)^{2}}\log\frac{\|\pi^{k}\|_{\mathcal{H}}k}{1-c\gamma}\right)$ and $\beta=0$, $\kappa=(d+1)/2$ for the Gaussian case, we can derive from Theorem [16](https://arxiv.org/html/2509.24991v1#Thmtheorem16) that the required $\lambda^{(k)}$ for the optimal error rate is

$$ $\displaystyle\lambda=\mathcal{O}(n^{-\frac{1}{2}}|\log|^{\frac{d+1}{2}})=\mathcal{O}\left(\frac{(1-c\gamma)}{\|\pi\|_{\mathcal{H}}^{\frac{1}{1-\epsilon}}\sqrt{k}^{\frac{1}{1-\epsilon}}}\right),\quad\forall\epsilon\in(0,1).$ $$

Similar to the tabular case, we then substitute equation [106](https://arxiv.org/html/2509.24991v1#A10.E106) into equation [18](https://arxiv.org/html/2509.24991v1#S4.E18):

$$ $\displaystyle\|f^{(k)}-Q^{(k)}\|_{L_{\infty}}\leq\mathcal{O}_{p}\left(\left((1-c\gamma)^{-1}n^{-\frac{1}{2}}|\log n|^{\frac{d+1}{2}}\right)^{\frac{1}{1-\epsilon}}\|\pi^{(k)}\|_{\mathcal{H}}\right)\leq\mathcal{O}_{p}\left(\frac{1}{\sqrt{k}}\right).$ $$

∎

###### Proof.

## Appendix K Experiment Supplements

### K.1 RL environments

CartPole-v1 (Barto et al., 2012): A classic control task with 4-dimensional continuous state space (cart position, cart velocity, pole angle, pole angular velocity) and 2 discrete actions (push left/right). The goal is to balance a pole on a cart, with an optimal reward of 500.

Acrobot-v1 (Sutton et al., 1998): An underactuated robotics task with 6-dimensional continuous state space (cosine/sine of both joint angles, angular velocities) and 3 discrete actions (torque values $\{-1,0,+1\}$). The objective is to swing the free end above a target height, with an optimal reward of $-100$.

### K.2 Hyperparameter Configuration

Table [2](https://arxiv.org/html/2509.24991v1#A11.T2) shows the hyperparameter setting of convergence analysis experiments in Section [6.2](https://arxiv.org/html/2509.24991v1#S6.SS2). The only difference in the hyperparameter is the learning rate.

**Table 2: Hyperparameters of convergence analysis in Figure [1](https://arxiv.org/html/2509.24991v1#S6.F1).**
| Hyperparameter | CartPole-v1 | Acrobot-v1 |
| --- | --- | --- |
| Optimizer | Adam |  |
| Learning rate $\eta$ | $1\times 10^{-3}$ | $2.5\times 10^{-4}$ |
| Network | 2-layer MLP |  |
| Hidden width $h_{\mathrm{dim}}$ | 64 |  |
| Activation | ReLU |  |
| Batch size | 32 |  |
| PPO Epochs ($T$) | 4 |  |
| TD Error Loss Coefficient | 0.5 |  |

Table [3](https://arxiv.org/html/2509.24991v1#A11.T3) presents the hyperparameter configuration used in our comparative study (Section [6.3](https://arxiv.org/html/2509.24991v1#S6.SS3)) between classic PPO with GAE and our novel NPG implementation with TD learning on CartPole-v1.

**Table 3: Hyperparameter Configuration for CartPole-v1 Comparison Study in Figure [2](https://arxiv.org/html/2509.24991v1#S6.F2).**
| Parameter | Value | Unit | Description |
| --- | --- | --- | --- |
| Environment Configuration |  |  |  |
| Training Episodes | 5,000 | episodes | Total training episodes |
| Update Frequency | 128 | steps | Steps per PPO update |
| Learning Parameters |  |  |  |
| Learning Rate | $1\times 10^{-3}$ | - | Adam optimizer rate |
| Discount Factor ($\gamma$) | 0.99 | - | Future reward discounting |
| GAE Lambda ($\lambda$) | 0.95 | - | GAE bias-variance trade-off |
| KL Penalty Configuration |  |  |  |
| KL Schedule | $k^{-0.5}$ | - | Dynamic $\beta=k^{\text{schedule_pow}}$ |
| Initial KL Penalty | 1.0 | - | Starting $\beta_{0}$ coefficient |
| Entropy Coefficient | 0.01 | - | Policy entropy regularization |
| Training Configuration |  |  |  |
| Value Loss Coefficient | 0.5 | - | Critic loss weighting |
| PPO Epochs | 4 | - | Policy update iterations |
| Batch Size | 64 | samples | Mini-batch size |
| Architecture |  |  |  |
| Hidden Dimensions | 64 | neurons | Network layer width |
| Activation | ReLU | - | Non-linear activation |
| Optimizer | Adam | - | Gradient descent |
| Package | Pytorch | - |  |
| Device | CPU | - | Apple M4, Arm64 |

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: N/A
soundness: 3
strengths: 1. Provides the first comprehensive analysis of TD and PPO/NPG in infinite-dimensional RKHS, bridging classical tabular/linear theory with modern kernel and neural tangent kernel regimes. 

2. Introduces an efficient kernel TD evaluator that acts as an implicit preconditioner, achieving geometric convergence without cubic matrix inversion, thereby improving scalability in continuous spaces.   

3.  The results elegantly connect function-space policy optimization to kernelized and neural-network representations, offering a unified view of convergence and sample complexity across different model classes.   

4.  Experiments on control benchmarks (CartPole, Acrobot) support the theoretical predictions and show improved stability and efficiency compared with PPO baselines.
summary: This paper provides a theoretical and algorithmic study of Temporal-Difference (TD) learning and Natural Policy Gradient (NPG)/PPO methods in Reproducing Kernel Hilbert Spaces (RKHS). The work unifies prior results across tabular, linear, Sobolev, Gaussian, and Neural Tangent Kernel (NTK) regimes, with empirical validation on standard control benchmarks
weaknesses: 1) Limited Experimental Scope: The empirical evaluation is restricted to low-dimensional toy environments, leaving scalability to high-dimensional or real-world continuous control tasks (e.g., MuJoCo, DMControl) untested.  

2. Strong Theoretical Assumptions: The analysis relies on idealized assumptions such as bounded RKHS norms, smooth reward functions, and known transition kernels—conditions rarely satisfied in practical RL settings.    

3. Sampling Distribution Dependence: The framework presumes access to controllable sampling distributions and well-behaved state–action densities (Assumptions 1 & 6), which may not hold for off-policy or non-stationary data.    

4. Implicit Domain Knowledge: While the paper claims generality, the theoretical derivation implicitly assumes that the underlying domain shift or policy complexity can be quantified via RKHS norms, which may not be observable in real applications.    

5. Lack of Comparative Baselines: No direct comparison with recent kernel-based RL methods or strong deep-RL algorithms (e.g., SAC, TRPO, DDPG) limits the practical interpretability of the reported advantages.    

6. Algorithmic Practicality: Although the authors claim computational efficiency, the per-iteration kernel operations could still be costly for large datasets, and no analysis of memory or runtime scaling is provided.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: * *Relaxing the Assumption on Bounded*: The assumption that $\sigma$ is bounded might not hold in all real-world applications. Have you considered how the algorithm performs if $\sigma$ is not bounded or exhibits more variability? Are there methods to ensure the algorithm's stability and convergence even when this assumption is relaxed?
* *Computational Efficiency and Scalability*: In the experiments, you demonstrated superior performance on standard tasks. How does the algorithm scale with respect to both computation and memory as the size of the state and action spaces increases? Are there strategies to further optimize the method for large-scale reinforcement learning problems?
* *Nonlinear Approximators and Deep Networks*: The paper discusses the applicability of kernelized TD and RKHS methods for non-linear function approximators. Do you think this approach can be extended to more complex architectures such as deep neural networks? What are the practical challenges of applying this method to deep reinforcement learning algorithms?
soundness: 3
strengths: * *Theoretical Innovation*: The paper makes a significant contribution by combining kernel methods with reinforcement learning, particularly through the use of kernelized TD for policy evaluation and KL-regularized natural gradient updates for policy improvement. This approach successfully addresses theoretical gaps in PPO and similar algorithms when dealing with complex, non-linear function approximators.
* *Comprehensive Analysis*: The paper offers a detailed analysis of sample complexity and convergence rates, providing a unified framework for understanding PPO's behavior in RKHS. The analysis is not limited to simple models but extends to Sobolev spaces, NTK, and deep neural networks, offering theoretical guarantees for various function spaces.
* *Empirical Validation*: The experimental results strongly support the theoretical analysis, demonstrating that the proposed method outperforms the standard PPO algorithm in terms of sample efficiency and computational efficiency. The experiments on benchmark control tasks such as CartPole and Acrobot show that the theoretical predictions align well with empirical performance.
* *Practical Relevance*: The paper provides not only theoretical insights but also practical guidance on how to improve PPO and similar reinforcement learning algorithms. The proposed methods are directly applicable to large-scale reinforcement learning tasks that require efficient sample usage and computational performance.
summary: This paper revisits Proximal Policy Optimization (PPO) from a function-space perspective by introducing a kernelized temporal-difference (TD) method for policy evaluation and a KL-regularized natural-gradient method for policy improvement, both within a Reproducing Kernel Hilbert Space (RKHS). The authors provide non-asymptotic error bounds and sample complexity analysis, showing that the proposed framework improves stability and sample efficiency in standard control tasks (such as CartPole and Acrobot). The results suggest that this method places PPO on a more solid theoretical foundation, extending it beyond finite-dimensional assumptions and clarifying when kernelized updates with TD critics yield global policy improvement with practical efficiency.
weaknesses: * *Assumption of Bounded Distributions*: One of the key assumptions in the paper is that the distribution $\sigma(s,a)$ is bounded. While this assumption simplifies the theoretical analysis, it may not hold in all real-world scenarios, especially when dealing with highly variable or concentrated distributions. Further discussion on how the algorithm behaves under weaker or less restrictive assumptions would be valuable.
* *Computational Complexity Analysis*: While the paper provides a thorough theoretical analysis, it lacks an in-depth discussion on the computational complexity of the proposed method, especially for high-dimensional problems. As the state and action spaces grow, it would be useful to analyze how the algorithm scales in terms of computation and memory.
* *Limited Experimental Environment*: The experiments are conducted on relatively simple control tasks (CartPole and Acrobot). While these tasks are useful for validating the method, it would be helpful to see how the proposed method performs on more complex, high-dimensional environments to better assess its scalability and robustness.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - Does the analysis extend to multi-step TD or TD($\lambda$) for $\lambda \in (0,1]$ with eligibility traces?
- A key component of (natural) policy gradient algorithms is exploration. This is usually established by assuming finite concentrability coefficients, or using entropic regularization with a fixed regularization coefficient. In this paper, how is sufficient exploration guaranteed to avoid strictly suboptimal and near-deterministic policies? The role of KL-regularization from an exploration perspective could be discussed further.
- In conjunction with the previous point, can the analysis here be extended to entropic regularization?
soundness: 3
strengths: - The per-step sample complexity bounds in the paper are definitely interesting and important.
- The analysis of kernelized TD critic is clean and rigorous. The connection to the metric entropy in the RKHS provides a unified perspective, which is valuable.
- The approach to connect TD learning with NPG-PPO-style policy improvement updates is classic yet elegant.
summary: This work studies an actor-critic method akin to TRPO/PPO in an RKHS, which integrates TD learning in a kernelized way as critic with a KL-regularized natural policy gradient update. It is related to a kernelized version of natural actor-critic method. On the technical side, the paper establishes sample complexity bounds need per policy optimization step to achieve a target error.
weaknesses: - Assumption 6 is a little unusual as it controls the state transitions per step. The situation worsens for weakly-ergodic MDPs with poor mixing times. It can be worth discussing further justifications, and benign and pathological extremal cases.
- The dependency on the effective time-horizon $1-\gamma$ is a little obscure. In the bounds, does effective time-horizon appear in terms of $1-c\gamma$, or are there any hidden multiplicative factors of $(1-\gamma)^{-1}$?

---

confidence: 2
contribution: 2
initial_rating: 4
presentation: 1
questions: **Disclaimer**: My current evaluation is essentially an educated guess of someone working in (theoretical) RL but not familiar with functional analysis. As I could not understand most of the submission, I am mostly focusing my review on the presentation of the results and how they could be made more accessible for a broader audience, while I am leaving a technical evaluation of the work to reviewer that are more familiar with the employed mathematical tools and prior works.

----

**Evaluation**: Assuming a solid technical contribution, I think the paper shall improve the presentation in a few aspects to clear the bar for acceptance. It shall discuss the practical implication of the reported theoretical results, it shall clarify how the analysis advance over prior works more directly (e.g., comparison of convergence rates in the same function space), it shall clarify why the reported results are important and valuable going forward.

In terms of motivation, I am not sure the paper aims at providing a theoretical support for new algorithmic solutions that advance over PPO and others or more of a theoretical understanding on when (in which domains/settings) is PPO expected to work/be efficient.

----

**Comments**

1. I am not sure why the title and abstract suggest that the paper provides an analysis of PPO, when the actual algorithm that is being analyzed looks quite different than PPO. Perhaps natural policy gradient would be more appropriate.

2. Assumption 1 and 6 look quite strong to me. Everything, evaluation/optimization, is easier when good data are available, but a crucial challenge of RL is to collect them from interaction with the MDP.

3. What does assumption 2 mean in more intuitive terms?

4. Not easy to understand what Theorem 9 and its corollary imply. I understand that the "training loss" decreases with a certain function of $n$, although the actual rate is not trivial to grasp. Is $\beta$ capturing a property of the function space or a parameter of the approach?

5. How do the results in Corollary 10 relate with previous works?

6. Why in eq. 21 the return of a policy is computed in expectation over the state distribution of an optimal policy, instead of the state distribution induced by the policy itself?

7. Experiments: If I understand it correctly, the comparison between PPO and the proposed algorithm is spurious. It looks like PPO is running with trajectories collected on-policy, while the proposed algorithm gets data from some sort of reset distribution. Learning from a "good" reset distribution is way easier than learning from actual rollouts. Can the authors clarify how the experiments are indeed comparing apples to apples?

typos and minor:
- l139: "and it is equipped this space with the bilinear form" something is off with the sentence construction
- l151: "We first impose the following assumption on the Markov chain". Which Markov chain?
- l235: "Derivethe"
- l260: "Unclear whether C_1 and C_2 are universal constants or coming from Asm.1"
- l372: misplaced dot
- l406: missing bracket
- l454: "learning Q" -> "to learn Q"
soundness: 2
strengths: Establishing the sample complexity of popular algorithms PPO in general function spaces is an interesting proposition. I am not familiar with prior work on this matter and with the function-space analysis reported in the paper, so it is hard for me to evaluate the strengths of the submission beyond noting that the problem is relevant.
summary: The paper revisits the theory of temporal difference value estimation and natural policy gradient from the perspective of function spaces. First, it sets up a value estimation setting in which the value function lies in a RKHS. Under some assumptions, the paper provides a result on the dynamic of the estimation error of the value function with a kernelized temporal difference method. Then, the kernelized TD is incorporated into an actor-critic, natural policy gradient method, for which convergence analysis is derived. Finally, the paper reports a few experiments in simple continuous control domains to validate the theory and to compare the resulting algorithmic implementation with PPO.
weaknesses: - The paper may not be accessible for a general RL audience
- Some assumptions may be unreasonable in most settings (e.g., Asm 1 and 6)
- Practical implications of the reported results are not stated clearly
- The empirical comparison between PPO and the proposed algorithm may be flawed or comparing the baselines in mismatching settings


Decision: Accept (Poster)