Sampling Complexity of TD and PPO in RKHS
Authors: LU ZOU
Wendi Ren
WEIZHONG ZHANG
Liang Ding
Shuang Li
Venue: ICLR 2026 Poster (2026)
Keywords: Kernel method
Kernel gradient descent
PPO
Temporal difference
Primary area: learning theory
TL;DR: By framing PPO in an RKHS (kernel) setting, we provide a new analytical perspective that both deepens understanding and delivers global convergence guarantees.

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}$  convergence rate for stochastic optimization.
Empirically, the theory-aligned schedule improves stability and sample efficiency on common control tasks (e.g., CartPole, Acrobot, and HalfCheetah), 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.

Published as a conference paper at ICLR 2026
SAMPLING COMPLEXITY OF TD AND PPO IN RKHS
Lu Zou', Wendi Ren', Weizhong Zhang', Liang Ding', Shuang Li
1 School of Management, Shenzhen Polytechnic University
Schooo of Data Science, The Chinese University of Hong Kong (Shenzhen)
"School of Data Science, Fudan University
zoulul 9903308 gma il. com, wendi ren link. cuhk. fveizhongzhang, 1 liang.ding] fudan. edu. en, tishuang@cuhk.. edu, on
ABSTRACT
We revisit Proximal Policy Optimization (PPO) from function-space perspec- tive. Our analysis decouples policy evaluation and improvement in reproducing kernel Hilbert space (RKHS): (i) A kernelized cemporal-difference (TD) critic performs efficient RKHS- gradient updates using only one-step state- tran- sition samples. (ii) KL-regularized, natural- gradiintt policy step exponentiates the evaluated action-value, recovering a PPO/TRPO-style proximal update in continuous state-action spaces. We provide non-asymptotic, ansativee guarantees whose rates depend on RKHS entropy, unifying tabular, linear, Sobolev, Gaussian, and Neural Tangent Kernel (NTK) regimes, and we derive sampling rule for the proximal update that ensures the optimal - convergence rate for stochastic optimization. Empirically, the theory-aligned schedule improves sta- bility and sample efficiency common control tasks (e.g.. CartPole, Acrobot, and HalfCheetah), while our TD-based critic attains favorable throughput versus a GAE baseline. Altogether, our results place PPO on a firmer theoretical footing beyond mnite-dimensional assumptions and clarify when RKHS- RKHS-proximal proximal updates with kernel- TD crities yield global policy improvement with practical efficiency.
INTRODUCTION
Volicy-gradien 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 al. 2017), and actor-critic (AC) methods (Konda & Tsitsiklis 1999)). when coupled with ciiporal-diifereenn continuous control, thanks 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 a rich function class, and (ii) couples this evaluation step with policy improvement update that provably ascends toward the optimal policy.
(TD) critics, are among the most effective tools in modern RI. for large,
Existing analyses often establish convergence only in tabular/linear regimes under strong realizabil- ity and concentrability conditions, see, e.g., (Agarwal et al., 2020 Bhandari & Russo 2024). With nonlinear nonparametric critics, guarantees frequently rely on idealized, exact value/advantage es- timates. Moreover, many sampling noise, leaving the per-iteration data requirements for ensured improvement unspecified.
bounds treat expectation terms as if computed without
For TD learning (Sutton 1988 Maci et al. 2009; Bhandari et al. 2018). linear TD is well understood, with asymptotic convergence and finite-time ear 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
bounds. By contrast, the theory under nonlin-
"Coresponding author

---

Published as a conference paper at ICLR 2026
prove nonasymptotic global convergence of mirror descent policy optimization for two-layer overpa- rameterized 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 an RKHS, which encom- passes tabular/linear models, Sobolev classes, Gaussian kernels, and wide neural networks through their neural tangent kernels. We study policy evaluation and improvement using gradient-bart based updates: (i) a kernel TD critic-distinct from least-squares TD-that implements RKHS-gradingg 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- -base TD evaluator in an RKHS that acts as an implicit pre- conditioner and attains geometric convergence without costly matrix inversions. The evaluator leverages N step TD learning for any N 2 and provides non-asymptotic TD-error bounds that attain the minimax rate (up to logarithmic factors).
We design KL-regularized proximal update implementable in continuous action spaces. We explicitly quantify the per-iteration sample size needed to achieve the intended improvement, addressing common gap where policy expectations 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 CCa et al. (2019), who provided the first finite-sample analysis of neural TD, proving sublinear convergence under an overparameterized network; see also Brandfonbrener & Bruna (019); [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 & Bartleti 2000), natural policy gradient (NPG) (Kakade) (001). trust-region policy optimization (TRPO) (Schulman et al., 2015), proximal policy optimization (PPO) (Schulman et al., 2207)) ) 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 the 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 al.]
Liu al. 2019). TRPO and PPO have likewise 2017) and Shani et al. (2020) analyzed TRPO, while Liu
2019
received theoretical attention: Neu et al.
al. 2019) and Cai et al. (2200) 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); [Grunewwlddr 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- con-paraettric setting, and by Duan et al. (2024), who proposed a regularized kernel-based LSTD estimator in RKHS for Markov chains independent of actions, deriving a non- ma-asyyptotic error bound and establishing a matching minimax lower bound.
2

---

Published as a conference paper at ICLR 2026
3 PRELIMINARIES
where S C Rid and A C Rd. compact and convex sets, P S S A - P(S) is the transition kernel for any state-action pair (s, a) E S x A to the space of distribution on S denoted as P(S).r: S x A + IR is the reward function, and 7 E [0, 1] is the discount factor. These yields Markov chain (so, do, 81, "1."..).
Markov Decision Process. We consider the MDP
The performance of policy ::S. + P(A) is evaluated by the following value function:
V (s)
E Σ (r((,, s, (-11s)), 81+1 P(-(s,, 0t)]
and the action-value function (Q-function):
(=(s,a) E
('r(si, ai) s, 0, a, a, T(-(s)), s1+1 [-]]s,,a))]
(2)
t=0
The corresponding ad advantage function ( a) is define as A a) study, we will focus on learning the Q-function. this end, we define the Bellman evaluation operator:
V=(s). In this
T(Q a) = r(s, a) for which Q is the fixed point of the operator: Q" TQQ
(Q"''aa'))
We let ( (s, a) = π {{)))){(s) denote the action-state distribution associated to policy т. Let v denote the stationary state distribution of the Markov chain given the optimal policy x² and let o" 0"(8, a) = x >=(2" (alss) denote the stationary state-action distribution. When given a policy æ, we first sample initial samples from a pre-determined initial distribution /40- We have the following assumption on og = TTp.-
Assumption 1. Distribution C oΦ 2 is bounded.
Assumption is essential for analyzing the generalization error. For instance, even if the empirical loss on the dataset is small, as shown in Theorem [O] an unbounded distribution could produce extreme outliers or unobserved data, making meaningful generalization (Corollary II impossible.
RKHS. Define w = (s,a) E S x A. We assume the Q-function Q associated with a policy lies in H(S A) where H is a RKHS induced by symmetric positive definite kernel K (S x A) (S x A) + R. Using kernel K, we define the linear space of functions on S x A as
follows:
H
b, (un, :,,b, R.W, A
and this space is equipped with the bilinear form
Σ b ) Σ C;:KWws ))
Σ b, b,K(w,
Without loss of generality, we assume that max K K(w,w) w) oo is bounded. The RKHS H(S x A) induced by is defined as the closure H under the inner product (. K and H(S x A) is equipped with norm || [| induced by (:, k).
Many functional spaces can be represented within the RKHS framework. For example, deep neural networks, Sobolev spaces, the Euclidean space, and discrete set all be formulated as RKHSs. For further details, please refer to Adams & Fournier 22003); Wendland (2004): (Jaoo et al. (2018).
We first impose the following assumption the MDP (8, P,),7) Assumption 2. There exists R > O such that max max((|r/| Il n, max,ss [PP(s)) ) < R.
In policy optimization, the RKHS norm || which plays central role, is difficult to determine, even generating single observation of Q" can be expensive. Assumption 2 provides useful alternative by requiring conditions only on the reward r. the transition kernel P(s' s, a), and the policy n, which typically much easier verify than condition directly the Q-function.
3

---

Published as a conference paper at ICLR 2026
Lemma 3. There exists positive constant C that only depends R, such that 1|0" I C+Ix((+))l
Covering Number. The following measures of RKHS complexity are fundamental to our analysis: Definition 4 (Covering number & entropy). For a given ê > O, the covering number of a RKHS H under Loe norm, denoted by (6, I| || : HH), is defined by the smallest integer M sucht that there exists centers {fm JM mm=1 C for which ff E H. 3m: [l - -flle I 6. The entropy of H is the
log of its covering number: H (6, I| I| H) log.N
|1_... H).
Assumption 5. The entropy of a unit ball in the RKHS H: B = {f H: 11fllw I 1) satisfies
H || Iew B) S C8-28 log 8|
28
for some C > 10,BE. 10, and n: 2 0.
Assumption | 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 & Bartlet 2009).
4 POLICY EVALUATION
For policy evaluation, we generalize the TD learning for parameters in a fiite-dimensional space to functions in infiniely-dimensiiee RKHS. We focus on one-step TD learning and its analysis in the main paper. The kernelized N-step TD presented in Appendix ! as it can viewed as a one-step TD with discount factor 7xh modified transition kernel P(sN so, ao), and modified reward F(5u, do) EN-1 7*,(s,, az). Given this equivalence, the convergence analysis for N-step TD is readily obtained simply by following the proofs for its one-step counterpart.
4.1 OPTIMIZATION FORMULATION
In this paper, we study the problem of estimating the Q function by samples from the Markov chain. In every update of policy т,, we sample i.i.d. {s) (2)
~ pol
j=1 from some chosen distribution No and
generate the subsequent state and actions
( and (s(") .
(1) following the Markov chain as follows:
Po: 6o
(-1s))
(8) s P(-10)) (1) " af ~ (-1ss"")
(5)
The initial distribution μsf can be specified using prior knowledge or obtained by following the chain trajectory and applying MCMC to sample i.i.d. quadruplets (5o, on, 81, a.). The resulting distribution only required to satisfy Assumption I
together with an additional assumption:
Assumption 6. There exists constant c.s.t f P(s |s, (alaa(a)aaa (s)dddaa S cuo(8") and ety < 1.
far Remark 7. Assumption ensures that the one-step transition is not too far from the initial distribution; otherwise, convergence slows. For example, if p. is the stationary distribution of the MDP, then 1. The constunt eγ in the convergence rate reflects sampling complexity, with smaller values indicating higher sample requirements. In the general N-step TD setting, Assumption can be relaxed to Assumption 6B in Appendix] Under this relaxation, the constant ey in our convergence theorems can be replaced by ey resulting in faster convergence rates at the cost of requiring additional sampling steps. Please refer to Appendix details.
Given dataset (wi (o) >z with w/ (6/)) ). 0,1 for any given policy n, we aim to learn the Q-function Q associated with the Bellman equation 3 by solving the following fixed-point Kernel Ridge Regression (KRR) over the whole RKHS H:
Q = min
m-mnnn JEH Ti
1 Σ
(f(w))) - r(w!)) 2Q (wf))) + A|lf
(6)
The functional minimization problem in equation is implicit. Nevertheless, by the representer theorem, can be shown to admit a closed form solution: Proposition 8. The estimator Q* has closed-form solution as follows
QT (((,w)))"
4

---

Published as a conference paper at ICLR 2026
where wa (wb (1) .... wb TT) E R ((;,o)) (K(,ub))) , and
b" = K + Anl - r, K, = K (w6 w C₁5 = [(wl") w ) r= [r(w6)) ... :.:....,,,u r((6 )T
KRR equation 6 allows extend the current standard TD algorithm for tabular learning the kernel TD framework.
4.2
KERNEL TEMPORAL-DIFERENCE LEARNING
From Proposition
we know that the solution Q" Hl so the KRR equation 6 can be rewritten
b
min bE
Σ
(K((u)))
wolb r(wb)) K 7K(w] wo)b" + Ab Kb. Ab...
(8)
Instead of directly solving equation 8 for the vector b" by gradient-based method on R", we treat
equation 6 as functional optimization the RKHS H. Inspired by Kernel Gradient Descent (Ding
et al.... 2024 Lin & Zhou 2018. Raskutti et al. 2014), we propose the following updating rule the
RKHS:
Σ (M((w)) r( -((((()) -ud K K(ub),
=++1 - o.)
where Ot acts as the weight decay to prevent over-fitting and improve generalization (Hu et al. 2021 and nh the step-size for the learning rate. can be noticed that equation 9 can converted to form similar to semi-gres amiigrrdientt TD(0) (Sutton et al. 1998) if we represented it by b, K (wo):
b = (1 - ax - 7o (fe(wo) - (7f((w)))
(10)
The difference between equation I0 and semi-gradient TD(0) lies in the fact equation 10 uses functional gradient in the infinite-dimensionall RKHS, while semi-gradient TD(0) uses a gradient of some parameterized functions in a diteessiinnii space.
A natural question is why we don't 't directly solve the n-dimensiinal equation 8 The reason is that the update rule equation iO more efficient because uses the RKHS inner product (:, 1) instead the 12 inner product in I" 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).
we can derive the convergence pattern of ft to the target Q for correctly-selected constant weight decay ar = a: and step size
From updating rule equation 10
b b" = =[1 (al + πバK C) b 17 (al mk - mC)
= [ - (al + 1₁K CC [b. - b"]
(11)
[[(1 all n c [bo b"]
the cigenvalues of [[1 a)l - 1 + mC are small, then ft converges to Q exponentially fast.
4.3 CONVERGENCE ANALYSIS OF KERNEL TD
We first show error decomposition for the estimator equation 6 Define the difference function
1= Q -Q- and the Bellman residual:
5 = r(wb) + 7Q (w) Q² (z(
(12)
We have the following error decomposition Proposition 9 (Statistical-Apppoiimiil Error Decomposition).
DT (w) (1)) -DD (D
(w))))) = Σ D (w) (T A(D")Q")) )"
(13)
5

---

Published as a conference paper at ICLR 2026
From the enror decomposition the right-hand side of equation
13 then empirical process (Geer 2000) derive the following convergence rate of Q" training data
Theorem 10. Suppose Assumptions
5 and O hold. Let = Ci/n, a = nAn, and iteration
number 2 C2 log ||bo b"1l for some universal constants C1,C₂ 0 and X O((1
ey) 2-28 n 2+1 log nl Tē*), then the kernel TD estimator fo satisfies
1 n
(w( ( (m(ub))) SOp (11 m7) 24
(()-
2+.
log
1+
(14)
I S 00((1)
Theorems yield convergence only on the dataset, not generalization error. Establishing generaliza- tion requires additional structural information the RKHS, and for the following cases, kernelized TD attains the optimal convergence rates for non-parametric estimators (Nemirovski 20000.
Corollary 11. Suppose Assumptions)
S hold, then
for Tabular: IfS x A are uncorrelated discrete set {wy : = 1,... n for some constant v E (0, 1),
then K da=z' and the Kernel TD estimator satisfies
Ilfe - Q" Q-1112(05)) 5Op 000(1110)))) (11-0))''n" |logg 1/2 n(1+v//44 1Q" 10ml/m:
(15)
Sobolev: If K = -gga=a' where Ks is Sobolev type kernel with smoothness m and intrinsic dimension d and {a]a= then the Kernel TD estimator satisfies
Ie Q" (=(1))( S SOpp (1-((117)
(1-
2m+4/22
2m 12
2m
11Q
(16)
NTK: K = Noamal where N is the NTK (8,8) 8') of two-layer neural network on d-sphere gd and {a] 1, then the Kernel TD estimator satisfies
Ilfe (7 S ((1-07) 07)
34-1
n
d+1
11
(17)
Gaussian: If Gaussian RKHS, i.e. K= - c1ul-=''11 with S A = 10, 11d hypercube, then
Ilfe - - (TILLOO Op (11 (1-c7) [ogn((d+1)/2 11
(18)
5 POLICY IMPROVEMENT
In this section, we focus on the following policy update rule:
x R+1
arg max
Exp
Ax
S ( ()((s)))(als KL (x((s))))+)
(1=))
(19)
[A 1,0
where E, [f]] - f()00)
) is the empirical expectation, Kp(p)))) denote the KL divergence, ((k) is the kernel TD estimator of Qui) == Q= trained for T' iterations, and A is the step size.
Equation 19 differs from the original PPO (Schulman et al. 2017), which uses K (LL((((())) (-Is) T(-ss) instead of K L (TT[sss) (-Is)) Equation 19 has closed-form solution equivalent to Natural Policy Gradient (NPG) so we refer to it as explicir PPO or NPG. Analysis for the original PPO is provided in Appendix K Its solution takes an implicit form analogous to implicit stochastic gradient descent
(SGD) (Toulis et al. 2021) and we therefore refer to it as implicit PPO.
5.1
NATURAL POLICY GRADIENT IN RKHS
For sequence of RKHS function (f() HH) the NPG update rule given by:
k+t x (()) exp Esp(ee A
(20)

---

Published as a conference paper at ICLR 2026
Lemma 12.
Suppose x* exp(F) (F) for some function F and Assumption 7 holds, then equation 20
the solution to equation 19 on {so A.
The update rule equation 20 generalizes existing NPG methods, including those for tabular RL Liu al., 2024), linear RL (Cen et al. 2022), and two-layer neural networks (Liu al.) 2019), to general RKHS functions. Our update rule equation alloos nh to be continuous function of (s, a) and
replaces the population expectation with an empirical expectation that is adaptive to the data.
By combining the NPG update rule equation 20 with the kernel TD update rule equation 9 we introduce an efficient algorithm that generalizes NPG to nnfnite-dimensional RKHS as Algorithm
Algorithm NPG in RKHS
1: Require: MDP (S,A,P, 7), RKHS H.
2: Initialize T ( for some ((0) E H. set F = Ao
3: for k = 0, 2.... do
4: Select an initial sampling distribution un and number of samples t n(() si
5: Generate {[s)] (1)) ,si a ~ ( (ao so) P(s)lss) (0)=(((1|s)))))
6: Set - T(k), a + (1k,, n1 + 1)(
7: Initialize f(k)
T do 9: Update f(k) (1- (()) ( Ei. (F()) r(wb²) (w))) k(w)"-)
8:
10: end for
F F F + (M) n x exp(F)
12: end for
From the NTK perspective, Algorithm can be viewed as the evolution of a deep neural network described by kernel K. Consequently, it remains valid we replace the RKHS functions f(k) with deep neural net fow parameterized by (k) and the policy proportional to exp(Jeun).
5.2 GLOBAL CONVERGENCE OF NPG
We first define the expected total reward to measure the optimality of a policy क
R[m]
Es [V* = Es (()))))((
(21)
We can have a fundamental inequality for the equation 21 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 13. In Algorithm 7
inf (R(x*) - R(
Σ -
[Ex
A (111-)))) Es KL (-IS))
Σn Ak
(22)
observe that achieving the optimal (kk-1/2) convergence rate for stochastic optimization requires selecting suitable parameters in Algorithm I to ensure the policy evaluation error well-controlled under the Lox norm. This leads the following corollary.
From Theorem 13
Corollary 14. Let {n k be the policies induced by Algorithm Set A = 1lVT.. For settings Tk=1 listed in Corollary 11 set (K) and (k) according Table 1 Set (k)) ((k) and (K) according to
Theorem 10 with = X (k) Then under the same conditions as Corollary
we have
inf (R[T*] - R( < Op( -
(23)
18kSk
7

---

Published as a conference paper at ICLR 2026
Table I: Parameters selection in Algorithm
for four cases in Corollary
Setting
(A)
A(R)
n log
Tabular
(1 - cy)2
0
(
1-my
|| 1|
+ (+kll 11 147
212m 2m+ted
Sobolev
o
|| 1, 2m-0
1 1-69
2m=dd22
(1-c7)
|| Zmm
NTK
o
| 11 (1-07) 3+T
1-cy
T
111 || N *
Gaussian
o
I | 1 TT (1-07)²
log
1bck 1-07
llack
(1-ox)
Ae E (0,1)
|| VKT.
Corollary 14 shows that the required sampling number increases with both the step size k and the policy complexity, measured by the RKHS norm ||* [[æ.. 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 well-defined and meaningful measure policy complexity. For example, in the Sobolev and NTK cases, the policy is from composing softmax with an RKHS function, and remains in the RKHS since the softmax analytic. Although the RKHS norm hard to estimate in the NTK case-where the policy corresponds to deep neural network- attributes such as network stability and architecture can serve as practical proxies for the RKHS norm complexity.
6 EXPERIMENTS
We conduct numerical experiments to empirically validate our theoretical analysis of Q-function esti- mation within the NPG framework outlined in Algorithm [ gate the convergence properties of deep neural network- implementattnnnnn and sample efficiency. Our code is available at https: / // thub. com/ o i RKHS.
The experiments are designed to investi-
6.1 EXPERIMENTAL SETUP
Environments. We evaluate our method on standard benchmarks: (1) CartPole-vl (Barto et al. 2012), a classic low-dimensional control task (4-dim continuous states and 2-dim discrete actions); (2) Acrobot-vl (Sutton et al.) 1998), a more challenging underactuated robotics problem (6-dim continuous states and 3-dim discrete actions): (3) Salffhhetahh-v5 a high-dimensional environment in Multi-Joint dynamics with Contact (MuloCo) with 17-dim continuous states and 6-dim continuous actions. The details of these three environments are in the Appendix [..]
Model Architecture. We instantiate the non-parametric function ((k) from Algorithm I with neural network foon, where the policy is given by no Softmax(fe). The network is a simple Multilayer Perceptron (MLP) with two hidden layers. This model is implemented within an Actor- Critic paradigm where the MLP backbone serves as the Critic (fe), outputting Q-values, and the addition of a Softmax layer forms the Actor (Na). The Actor and Critic share all parameters, enabling efficient end-to-er -o--to-end training.
Algorithm Configuration. Algorithm Sarithmm[unee Nutlinnes two-stage process: optimizing the Q-function for epochs, followed by a single policy update. In practice, finite number of updates (c.g., 7 = 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 's NPG objective (Line 12) into a unified loss function. This objective then minimized over T epochs for each batch of collected data.
8

---

Published as a conference paper at ICLR 2026
Each outer iteration k proceeds as follows: execute the current policy collect samples, after which we rum optimization epochs over this batch to update the shared actor-cri critic parameters. Experiments run for 1000 episodes and averaged over 10 random seeds; report the mean and standard deviation across seeds. Hyperparameters are shown Appendix L.4
6.2 CONVERGENCE ANALYSIS
We investigate the empirical impact of the step size schedule, A₁ k_ by testing three theoretically motivated exponents: a E {0.2, 0.5, 1.5).
Results Analysis. Figure corroborates our theoretical predictions, revealing three distinct learning dynamics determined by the schedule a. These results empirically confirm that the step size schedule 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 AS vズ schedule in Corollary 14 Moreover, as
shown in Figure I (b), the learning curve for A vk exhibits 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 effectiiveness of optimization. A similar trend emerges when the CartPole experiments run for longer episodes (e.g., Figure 2 (a)). We report the runtime and memory cost for Figure [ Appendix [L.2] which indicates that for high-dimensional continuous control tasks like HalfCheetah-v5 (17-dim state, 6-dim action), our method maintains reasonable run time and memory.
2530
-20
1030
530
272
220
211
127
-622
225
100
200
2000
4.00
5383
5000
30000
Stog Size Sckedala Compaation Cartheeett
Stop Sizo Schedale Comparissn en Berobativt
Sep Schedall Computton CCretthhe
2336
422
2038
1538
Smeetee Renarr
382
Sreetter Rotuaro
122
330
Smeether
$25
202
2302
4000
6002
10000
(a) CartPole-vl: raw (top) and (b) Acrobot-vl: raw (top) and (c) HalfCheetah-v5: raw (top) and smoothed (bottom) rewards.
smoothed (bottom) rewards.
smoothed (bottom) rewards.
Figure 1: Convergence analysis on CartPole-vl, Acrobot-vl, and HalfCheetah-v5. Each column stacks (top) and smoothed (bottom, window size 60) rewards. All environments show the same trend: A 00. converges, A = --0.2 diverges, and A = k -1.5 stagnates.
6.3 RUNNING EFFICIENCY ANALYSIS
To analyze the sample efficiency, we compare our Algorithm with the ciip-PPO(Schulman al.) 2017). The key architectural difference between these methods lies in their data requirements for value estimation: clip-PPO can be viewed as a second-order approximation of implicit PPO with t-step TD and relies on Generalized Advantage Estimation (GAE). GAE requires complete trajectory segments (sg, ao, To, 81, @1..... St, 0z) to recursively compute advantage targets, rendering its update rule non-local in time. Instead, Our NPG employs action-vall valuue critic (Q(s, a)) and learns from single-step Temporal Difference (TD) errors. This approach is highly data-efficient, as it only requires (So, 4g. To, $1, a leam Q
Results Analysis. Our experiments demonstrate that our NPG with TD learning significantly outperforms PPO in both sample efficiency and computational efficiency. As shown in Figure

---

Published as a conference paper at ICLR 2026
Learning Curves (10 Seeds)
Smoothhed Returns- (windcw-wo
Learning Seeds)
Computational Efficiency Seeds)
7230.1
Returns
400
k00
Stops per Secoodd
6000
5406.0
4000
200
200
clip PPO
2000
Our NPG
2000 Episode
3000
4000
clp-990
Our NPG
(a) Reward.
(b) Smoothed reward.
(c) Processed steps/second.
Figure 2: Performance and efficiency comparison on CartPole-vl over 10 seeds.
(a-b), our NPG consistently solves the task, achieving the maximum reward of 500. In contrast, clip-PPO converges more slowly and exhibits high variance, with only some seeds reaching the optimal solution. Since our algorithm depends on sampling quality (Assumption and 66, choosing suitable distribution enables fast convergence, confirmed in Figure
Figure c) shows our NPG is more efficient, processing more state-action pairs (i.e. w/ , 0,1-0,11 per
second compared to PPO's pairs (i.e. ) per second. This computational advantage stems directly from our algorithm's 's design. The update for our NPG is based on a computationally lightweight, one-step TD-error calculation. In contrast, clip-PPO must perform a more complex, recursive GAE calculation over entire trajectory segments for each update.
We further compare our NPG with discrete SAC (Haarnoja et al. 2018 DQN (Mnih et al. 2015), and implicit PPO (explained in Appendix K). The results of Cartpole-2 shows that implicit PPO shows similar performance as our NPG, and akin to implicit SGD, it results more stable iterations. Discrete SAC fails find the optimal solution. DQN is computationally efficient but unstable, converging to the optima only in some seeds.
in Appendix L.3 Figure
7 CONCLUSIONS AND FUTURE STUDIES
We generalize TD and NPG to infinite-dimensional RKHSs. The framework is illustrated using four commonly studied RKHSs, and numerical experiments further confirm that the theoretical results align well with empirical performance. In specific, we
Propose a KRR formulation for solving the functional N-step TD problem using finitely many -tstep trajectory samples, and provide the corresponding sampling complexity;
2. Generalize the PPO update rules to functional minimization problems and derive functional- form solutions for both explicit PPO (NPG) and implicit PPO (the original formulation). Building on these solutions, we establish the sample complexity RKHS-bure PPO required to achieve the (k-1/2) convergence rate.
3. Empirical results validate our theory on both low-dimensional discrete and high digensimensional continuous control benchmarks (CartPPle-ve
Acrobot-ve Hal (Cheetah-v5) showing that the 4: 1/2 step-size schedule yields fast and stable convergence. Besides, the proposed N-step TD extensions show the bias-variance trade-offs.
We also believe that our results can be further improved and generalized. First, the kernelized TD and PPO methods developed in this study may be extended to the more general Mirror Descent methods for policy optimization. Second, our convergence analysis for TD is conducted under the L2 metric to establish minimax optimality. Although the L. metric may be more appropriate for RL setting, the fixed-point KRR formulation for TD differs substantially from the standard KRR formulation. We therefore leave the convergence analysis under the Tooo metric for future work.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
We thank the anonymous reviewers and the area chair for their constructive feedback, which helped improve the paper. This work was supported in part by the Key Program of the National Natural Science Foundation of China (NSFC) under Grant No. 72495131; the Shenzhen Stability Science Program 2023; the Shenzhen Science and Technology Program No. JCY12025060414103800
and the Longgang District Key Laboratory of Intelligent Digital Economy Security. This work was also supported in part by the National Natural Science Foundation of China under Grant No. 72301076 and the Science and Technology Commission of Shanghai Municipality under Grant No. 23PJ1400800
REPRODUCIBILITY STATEMENT
We have included all the experimental design in paper. Details of the computational setup, including hardware configuration and software environment, network structure, as well as the choice of hyperparameters, are documented in Appendix L.4 We also release our code.
REFERENCES
Robert A Adams and John J Fournier. Sobolev Spaces. Academic Press, 2003.
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- 66-66. PMLR, 2020.
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)11-76, 2021.
Andrea Agazzi and Jianfeng Lu. Temporal-diiferencee learning for nonlinear value function approxi- mation in the lazy training regime. 2019,
Martin Anthony and Peter L Bartlett. Neural network learming: Theoretical foundations.. cambridge university press, 2009.
J Andrew Bagnell and Jeff Schneider. Policy search in kernel hilbert space. 2003.
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5): 834 846, 2012.
Jonathan Baxter and Peter Bartlett. Direct gradient- based reinforcement learning. In 2000 IEEE International Symposium Circuits and Systems (ISCAS), volume 3, pp. 271-274, IEEE, 2000.
Brett Bethke, Jonathan P How, and Asuman Ozdaglar. Kernel-based reinforcement learning using bellman residual elimination. Journal of Machine Learning Research (Io appear), 2008.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Opera- tions Research, 72(5): 2024.
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.
M Š Birman and Mikhail Z Solomjak. Piecewise-pole pooyyoia- approximations of functions of the classes. Mathematics of the USSR-Sbornik, 2(3):295, 1967.
David Brandfonbrener and Joan Bruna. Geometric insights into the convergence of nonlinear td learning. arXiv preprint arXiv: 12155 2019.
Qi Cai, Zhuoran Yang, Jason Lee, and Zhaoran Wang. Neural temporal-differenn learning converges global optima. Advances in Neural Information Processing Systems, 32, 2019.

---

Published as a conference paper at ICLR 2026
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pp. 1283-1294. PMLR, 2020.
Semih Cayci, Niao He, and Rayadurgam Srikant. Convergence of entropy-regularizee natural policy gradient with linear function approximation. SIAM Journal on Oplimization, 34(3):272--2755, 2024.
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.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs, arXiv preprint arXiv:2009. 10683, 2020.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. Advances in neural information processing systems, 22, 2009.
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.
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.
Amir-massoud Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Regular- ized policy iteration with nonparametric function spaces, Journal of Machine Learning Research, 17(139):1-66, 2016.
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.
Sara A Geer. Empirical Processes M-estimation, volume 6. Cambridge university press, 2000.
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.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference machine learning, pp. 1861-1878 Pmlr, 2018.
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-3111 2021.
Thomas Hofmann, Bernhard Schölkopf, and Alexander Smola. Kernel methods in machine learning. 2008.
Tianyang Hu, Wenjia Wang, Cong Lin, and Guang Cheng. Regularization matters: A nonparamet- ric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics, pp. 829-837. PMLR, 2021.
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.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the nineteenth international conference machine learning, pp. 267-274, 2002.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
12

---

Published as a conference paper at ICLR 2026
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-1860 2020.
David Krieg and Mathias Sonnleitner. Random points are optimal for the approximation of sobolev functions. IMA Journal of Numerical Analysis, (443):1346-11 2024.
Thomas Kühn. Covering numbers of gaussian reproducing kernel hilbert spaces. Journal of Com- plexity, 27(5):489-499 2011.
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.
Shao-Bo Lin and Ding-Xuan Zhou. Distributed kernel-based gradient descent algorithms. Construc- five Approximation, 47(2):249-277 2018.
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.
Jiacai Liu, Wenye Li, and Ke Wei. Elementary analysis of policy gradient methods. arXiv preprint arXiv:2404.03372, 2024.
Hamid Maei, Csaba Szepesvari, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard Sutton. Convergent temporal-difference learning with arbitrary smooth function approximation. Advances in neural information processing systems, 22, 2009.
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. PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 518(7540):529533, 2015.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 95)), 2008.
Arkadi Nemirovski. Topics in non-parana non-parametrie. Ecole d' Eté de Probabilités de Saint-Flour, 28:85, 2000.
A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization. SIAM Review, 2742)2264-265, 1985. doi: 10.1137/1027074.
Yurii Nesterov, Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of retropy-regularized markov decision processes. arXiv preprint arXiv:1705.0779% 2017.
John Neuberger. Sobolev gradients and differential equations. Springer Science & Business Media, 2009.
Dirk Ormoneit and Šaunak Sen. Kernel-based reinforcement learning. Machine learning, 49(2): 161-178, 2002.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Early stopping and non-parametric regression: an optimal data-dependen stopping rule. The Journal of Machine Learning Research, 15(1): 335-366, 2014.
Christian Rieger. Sampling inequalities and applications. Georg-August Goettingen (Germany), 2008.
13

---

Published as a conference paper at ICLR 2026
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy 2017.
optimization algorithms. arXiv preprint
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5668-5675, 2020.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. Conference on learning theory, pp. 2803-2830. PMLR, 2019.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
Richard Sutton, Andrew Barto, et Reinforcement learning: introduction, volume MIT press Cambridge, 1998.
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.
Panos Toulis, Thibaut Horel, and Edoardo M Airoldi. The proximal robbins-monro method. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(1):188-212, 2021.
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.
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-1544 1547, 2020.
Florencio Utreras. Convergence rates for multivariate smoothing spline functions. Journal of approximation theory, 52(1):1-27, 1988.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates convergence. arXiv preprint arXiv: (00v:/99000000 01 150, 2019.
Pawet Wawrzyúski. A cat-like robot real-time learning to run. In International Conference on Adaptive and Natural Computing Algorithmss, pp. 380-390, Springer, 2009.
Holger Wendland. Scattered data approximation, volume 17. Cambridge university press, 2004.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6): 3586-3612, 2020.
Ding-Xuat Xuan Zhou. Derivative reproducing properties for kernel methods in learning theory. Journal of computational and Applied Mathematics, 220(1-2):456 463, 2008
14

---

Published as a conference paper at ICLR 2026
A
PROOF OF LEMMA 3
Proof. Form the definition of QT and triangle inequality, we have
|Q n S
|r at) (s) aoll|
(24)
So only need prove | az) so ' 0, -Ilx - CiR for some Ci < for all t. For the
()){s0
case = 0, we use Assumption 2 to have
Bir(so 4o) so = 000 11l |rl S R.
For general t, rewrite E[r(s., 000 -1 in integral form
E[r(se, [e)]so so, anl
= =/ ax) ae)
i It 11) P(si|su, (a))r(alss))dssd ds;da;
/ r(() ar) ((si) (st, a.)) P(si|so, (ao so)
(25)
where P P(si) (st, at)) is the distribution of (st, az) conditioned on s1. Let {di} be the eigen- function of K then the RKHS norms of P(s).-) and π are then
[ 111 Σp:(s) s R,
|
2 n S
R
(26)
where p.(s) = (P(s) )) di) and T; = (TT, Di)
The coefficient regarding (sr [=)]s0, aol projected onto di is then
ao), dx H / r(st, az) ((81) (s)) (P(si|so, ao) so); de) H
Fs [[[(r(s,, (08(ss,,)))ss0 (s)
S max r(s, a) max ((s) a0) 80), diHH
(s.
#ES
S max ((, max ((s|s wESXA
ao) ( di)
SES
(27)
where the last line because max, r(w) (r, ((,W)) S || [x(()\)) S max, K K(w, R.
From equation 27] we only need to calculate the RKHS norm of function P(s|so, (a)ssa) From equation 26 we can derive that
\I<ree T,: l1
PS(sss, (a) (l) =11 Σ p:(s))s)
(28)
Σ pr(s) p(pp)pp
|| s 11
By combining equation 26 equation 28 we can conclude that
[[[rst, a:) (()(s,,)))os
ao -|lH ClI li2e
(29)
Substituting equation 29 into equation
24 we can have the final result.
B PROOF OF PROPOSITION g
Proof of equation] 7 We first briefty introduce the concept of covariance operators, which is crucial in
the proof. We adopt the shorthand notation ((w) = K (w, -) and 1 (w,,w)) = 1r" ((x,a)), (s(aa)= =
(ss))(s(a)PP( a) (() (a))s'). Then the covariance operator Ownao and cross-covariance operator Cwow,, on the RKHS H are defined as:
Cup iwl ((s ( & (S,
Cwp w1 (((S)A))(S) (1) (0S *S
15

---

Published as a conference paper at ICLR 2026
where f @ g denote the tensor product between functions f and g. Accordingly, for any for fi H.
Cup.ary and Capaan satisfy
(fo, Cun fi) = B.s.
(fo. Cun.an f1) = ((S,A)) (1)) (5 A')]
We also define the empirical version of operators Cwo and Canaan follows:
a Cwo Σ ((wb
n Σ ((ub') & (((
( s )( Cun.ee
With the concept of covariance operator, we can have the following lemma which can yield a specific
formulation for the solution of equation 6
Lemma 15. Solution to equation is equivalent to the the following equation:
Cup 620 QT [Camcooo + &uun,er Q-) + XQ = 0.
(30)
From Lemma 15
prove that the solution Q resides in finite-dimensional space:
Lemma 16. Let Fi {K(w,, (wi, ), 1,..,,,.......... , be the finite dimensional space spanned by kernel functions. We have QT E H.
From Lemma 16 we know that Q must be of the form:
Q
k(,,;)b;; K(:,wobb.
(31)
Substitute equation 31 into equation 30
togothe with the definition of empirical operators Cun and
Euo we then have
$
Σ
(wb ww)'
n Σ o (1) (1)
r(ub)) + Σ kw) (100))
"
(32)
1=1
1=1
by (w
(6) 0.
Rearrange equation
32 and write it in vector form, we have
T (ww) Kb + Anb -Cbb = $ (wo)).
(33)
So, we have
b K ArI AnI -C -C r.
B.1
PROOF OF LEMMA 15
Proof. Solution to the KRR equation Gls the minimizer of the following functional
Jff= = - - -(=6))) 2 + Allfli
(34)
The functional J is Fréchet differentiable obviously with RKHS derivative V VyJ[J] as follows:
Js + 5u]] lu]l
(35)
n
Σ ((a((()) - -(((())) ~ -u(u)))) K(wb", .) A5, u)
-VVJJf] u)m: Vu H.
(36)
16

---

Published as a conference paper at ICLR 2026
From the definition of empirical covariance operators, notice that (flug") r(ub")) K( K(wō", .) = C Cor r],
(37)
Q- ( K(w) = Öwneer δ²
(38)
Substitute equation 37 and equation
38 into equation 35| we then have:
V Cunowood (wo + &eu Q-) Af-
(39)
According to definition, Q7 is also the minimizer of J. Substitute f Q into equation 39 we can conclude that the minimization of equation 34 equivalent to equation
B.2 PROOF OF LEMMA 16
Proof. Rearrange equation 30 as follows
X Cuo.coo + Omngenn Q"
Cun Q-.
(40)
According to equation 37 and equation 38 the right hand side of equation 40 can be written
Cupuur [r- @-) + Tuoo.i Q²
= (= (3)) (r(wx")) (~" (m) E H.
The right-hand side of equation resides in H.. So, the left hand side Q H.
C PROOF PROPOSITION 9
Proof. According to the definition of the covariance operator, the Bellman equation equation equivalent to the following form:
3 is
Own wwo Q" Cwn weo + WCoo Cor Q"
(41)
Substitute equation 41 into Lemma 15 we can have
Own,wwo Al Q= Cwo wo Q" [Coo... Cworwo) r 7
Cio Cwo.wr Q-
(42)
Recall that D = Q - Q", we can rewrite equation 42 as
Cunycoo AI - (Cuneen D
(43)
Owniaoo Al Cwn
(r (-- xr Canoiun -wwosun Q
CWn.oo X1] (r (r-Q7 (+) +=)) Q"- dr
(Cuo (Q" - r) -uung Q"1)
Cup Al (r (r-Q") 7Cnn QF
Ar
(44)
where the last line is from equation 41 Taking the Hilbert space inner product with D in equation 43
and equation 44]
(D" [Cim + Al - CCnones) Dr
(45)
=(D", [Cunnco x1] (r (r-Q" Q²) 770 Q" ->x
(46)
17

---

Published as a conference paper at ICLR 2026
According to the definition of empirical covariance operators, equation 45 can be further rewritten as
(D*, Cwo.wo + A1 - /Coo..
D² )H
(47)
D (w) )2 7 D (wb (W) YD=
+ 11
n
i=1
and equation 46 can be further rewritten as
(D", (Ounoeo + dxl (r - Q") + moun Q" 1
(48)
= (D", Cun,ano (r Q") + +Woonm Q") I/ A(D", Qu")-
Because equation 47 and equation 48 are equals, by rearranging their terms, we have
D" 10 7
D (T
( (w())
(49)
n
=(D", Own (r - Q*) + Cos ²"1x A(D Q"))..
(50)
We use the definitions of empirical and population covariance operators again, the first term of equation 50 is
(D Cumnuoo (r (r-Q' Q-)) CCoo ²"
(51)
1 D (wb ( (r(w)) - (1) (w
1 Σ E (wb²)
1=1
i=1
Substituting equation into equation 50 we can have the final result.
D PROOF OF THEOREM 10
In order prove Theorem 10 we first need the following theorem, which we will provide its proof in Appendix B
Theorem 17. Let O((1 my) can have
log n
T ). Under Assumptions
5 and we
n
Dx (wb )// SO, (11-37)
1-
log n
T#7
|1@ 1
(52)
I| 11 < (p(1)
Proof of Theorem
10 By triangle inequality and Theorem 17
we have
Ilfe - 1l < ft - Q7 + 114 - ll
(53)
S f+ - Q= 112 + Op ((1 ((1-c)) (7)
2+20 n 2-20 logg n/ |logn|
2+8
and
Iifel I || + l1f - Q 11 1 O,(1)) + lIfe Q 1|
(54)
Therefore, we only need to prove that the convergence rates of fi to Q under || - |lx and the same order their counterpart in Theorem 17
||
||x have
Note that by the selections of decay weight and step size a/n = X. Then we can use equation || and Hölder inequality have
ll - Q- = (b: - bd) K² (b: - bb²)
max K k(www) n (b, - bba²
(55)
-Cn (I((1 - a)I 17K + C7: [bu - b") [ba))
<CnAb(bo - -b
18

---

Published as a conference paper at ICLR 2026
where A2 is the maximum eigenvalue [[(1 - nkK + my [((1 all 7/K + my myC and
C' (max, K (w,,)))?
Note that the maximum and minimum cigenvalue of the matrix K c is upper bounded by (1 + y) max, K (w,w)) and lower bounded by - max, K (w, (w,,), respectively. Therefore, if we
can select y) such that
a1-a- a (1+ max K (w,w)mm) S C a a y max K (w.w)mn) S C2 1
(56)
then A2 I C3 where C3 max C1 C2) We also need an extra condition that fr converges to the estimator Q with correctly selected as in Theorem 17 we also have
nn..
(57)
Solving equation 56 and equation 57 to get
1- 0 0< n21 + +C
and then by letting logcs (In(bo - b-)) we have
Ilft - 17 & Cn(bu C = Cn(bo - b losc, ( (n(bo-bbb)) $ O(A). (58)
Similarly, for the convergence in RKHS norm, we have
Ilfe 1² (b, b") K (b, -b²)
max K K(w,w) (b. -b²)
(59)
- -vnn (I((1 aa]l- ail 11K 1n CJ' [bo - -b1))
SvOnAj bウ)².
Note that the order of equation 59 is the same as that of equation 55
except that the constant term
is changed from C' to vC. Therefore, the same iteration number t is enough for the following convergence
[|fe Q S O(A).
(60)
Substitute equation 58 into equation 53 and equation 60 into equation 54 results.
we can have the final
E PROOF OF THEOREM 17
first slightly modify the error decomposition equation 13 get the following inequality
(w) (1) - (w >D' DD (w)))) + x1
(61)
D T (0)) + X(Q ).)
7
By further rewriting equation
61
we obtain the oracle that is essential to the proof:
(T >DDT(uu (D=
1 Σ D (wb) v²2 100000% (62)
variance
19

---

Published as a conference paper at ICLR 2026
For the left-hand side of equation 62 use the standard central limit theorem for Monte Carlo integration to have
1 (1)
7 D" (wo
5> E D ("o') (wi)] 0z( (()"
71
( Op(n (1) (P
(63)
00 Op $) E [ (wo))
(0) + On ">> s D" (w)
where the third line of equation follows from Assumption that
Bi|D" (w1)
D (s1, ((als:)))((s)((s so, ao) (a) dsoddo
(s) a1) ((1ls)) [
(4o)s) do ds dajda
/ DD (s ( (u()))))
(w)))
empirical processes (Geer 2000) to estimate the variance term in equation 62] 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 the expectation of the Bellman residual is O, i.c., Es; = 0 for all i = 1.... n. From Assumption equation and Lemma 3 we can know that the Bellman residual bounded:
For the right-hand side of equation 62
(r(w)) + +00 (w) (w) (3) $ ||ll + (1 (1=7)110=1l*
where the right-hand side because max, f(w) (f, ((,W))) I [[((,,))l fllx for any H. So E; is sub-Gaussian.
For natation simplicity, first define the empirical inner product and empirical norm for any pair of functions fi and f2 defined on {
f2n = Σ (2(w0)) Ilf. = (f1, ft).
The sub- -abu-ussiiantty of Bellman residual { allows us to apply the following lemma to estimate the variance terms.
Lemma 18. Suppose the RKHS H satisfies Assumption 5 as defined equation 12 Then, for all t large enough,
Suppose that { are Bellman residual
n2 (E. f)x
sup JEH | log
1
R
t
(64)
1
with probability at most C2 C2 12 with some positive constants C1 and Cz.
We can substitute equation
62 and equation 64 in Lemma 18 into the oracle equation 62
(1 cr) D +
X||@T 1
SO, (n 1/2)
D ||
log
D n D
+XQ0 )²)
(65)
HM
Case I 11 2 10 equation 65
yields two subcases, either
- 1D + X||@_ 1
(66)
SOp (n -1/2) 1 - log [ + log [
20

---

Published as a conference paper at ICLR 2026
cy)ll + s xXQ"
Op(n (p(nn))1(Q)) 1
(67)
Solving equation 66 yields
| ll =1 -1- (1-cc)3-100(1 2)사 ( n log
(68)
|| ll (1 oy) 55¹ Op(n 3) - (1 [0lg nl + llog Al)*
Solving equation 67 yields
2 1|
| ln - -
(69)
1 S 1
Case 11 11 S ||Q equation 65 yields another two subcases, either
(1 - c>) [ S Op(n
1/2) 1/2 1" "
(70)
or
(1 - (1-c>||D" < 21
(71)
It follows that either equation 70 holds
D < (1 - 07) 143 Op ж+ス)
(72)
Now summarize equation 69 equation by selecting
70
equation 71 and equation 72
We can notice that
e A= 0 07)
2-28 n
2458 log ni 1+#),
(73)
we can have the final result,
| 50, (1-101 -7)
2 2+23
log n * 11QT
(74)
1Q-"1xx (0,(1)]]
(75)
E.1 PROOF OF LEMMA 18
To proof Lemma we first need the following lemma from Geer 2000)
Lemma 19 (Corollary 8.3 in Geer (2000)). Let a > O, R > O, and H. be function space. Suppose
that SEN I S R for and & = {e are independent zero-meun aab-Gaussian random
variables. If there exists some universal positive constant C satisfying
a 2 On
H+ (1,111111e. -11ez H)du V B).
(76)
then we have
(c=naa
P
sup
(E,, f) 20) 22exp
(77)
for some positive Č
Proof. Let B = (f 11fl S 1) be the unit ball in H. Recall from Assumption 5 that
H6. || |I... B) s C8-29 log 2k
for some positive constant C, k, and | E [0, 1). Hence,
J/" R
R (H( ||- 11ll B)) du s C f "llogud"d
"du S CR. - log R7
21

---

Published as a conference paper at ICLR 2026
One may readily check that for all R 1 and 2 n met, and thus by equation 77 we have
llog R the condition equation 76
P
sup SEH.IISII..R
n= fm 2 R!
log R|
=
sup
(w0, fiml 2
/EH. SR
na
I 2 expp (xp
(78)
R
for positive constant C1.
Let f/llf (z. Then, the left-hand-side the inequality equation 64
becomes
(E, h)
sup KE H
|
log ||bl|m] 1M
We can then give the following upper bound for its tail distribution:
(E, m)
P
sup hEH
>t t
|
log
||All
||/||/ 1-1 log |// > >1))
Ke,, 1t)mll
sup kEH
ne (5, 12 -2+11)0 (0+1)-) (00000000(00)0000 (2++))
P
sup NEHH//I 1.E(2-6-1,2
n [E, 12 (141))1())))
sup hEH.1KI1,
2exp( (C22-(2228
< Σ 2 2(cxpl -C2t)))
I C3 c CC2t²)
where the fifth line follows from applying equation 78 with R 2- and in 101111212+11--00 (1+1)
F PROOF OF COROLLARY
Proof. The proof relies on the following so-called sampling inequality of RKHSs ( S |1 + 8H. 11.
(79)
where 8n,, depends on the distribution of data ( and the structure of RKHS H.
Case I: Hs (s) and AA {a)
In this case, we can note the RKHS is a discrete set (w; where M SA, og (w,) = W
M the
weight on element w, (according to our assumption, W, < C), and data fw (0) are i.i.d. samples from {wy 1 following oj.
Because the kernel K(w,w") 8.=s Swow, can derive that the RKHS is equipped with the inner product
(f.9)
Σ 1=1
figh f.g e
22

---

Published as a conference paper at ICLR 2026
where fy and gj the values of f and g wy, respectively. Also, the L2 norm and empirical norm are
M
If
(
-
WW
Il =
(w)).
Let It, denote the indicator function that wp follows:
(4)
W/, then rewrite the empirical norm as
M
Ji.
If
(w)))
==
M
W
M
EE=
I5
W
Σ
F2
f3
(80)
M
M
j=l
3=1
M
Zj
W
= =II =llfll(a(()))
42
n
M
where [4,ر,= is Multinomial distributed with trials, M mutually exclusive events, and probability
vector [W/m]] M
By properties of the Multinomial distribution, the last term in equation 80 has expectation
M
2
W
M
nW
/
W
E
f3 j=1
0,
(81)
M
M
==1
and variance
))
M
Var
Σ
2
W
1
Σ
Cov (2
M
n
1=1
JJ=1
W
Wi
(82)
Σ
87
n
M
M
M
<0
1
I
where the last line is from our assumption that M n² for some E (0,
Substitute equation 81 and equation inequality
82 into equation 80 it is straightforward to derive the sampling
I < 1 + Op (IT(1 Il
1
(83)
straightforward to see that the covering number of under To directly the covering number of H is M/8 so its entropy is
H |1,.,, 70) S logn + log
Substituting this result into the sampling inequality, have the final result:
II (2(1(1(0)) Silff Q" -2 + +Op (1(
I1fe Q2
<0, (1 (1-c7)) -ll-cr) cyy='n=
n -
log n 1/2)
+Op
(
1
Ilfe -Q"
00, (1- - - logn 1/2
+ +Op
1
||Q ||
n(1+2)/4
where the second line is from the empirical error in Theorem 10 with 3 = 0 and x: 1/2, and the last line is from the RKHS norm of / in Theorem 10
23

---

Published as a conference paper at ICLR 2026
Case II: Hys is Sobolev space and A {a]
For spaces of continuous functions, we first need to define a concept called the filled distance of data set so that we can apply the sampling inequality.
Definition 20. Given n points = {x on the set X equipped with norm || ||. the fill distance of the set X is
9X
max min ||x; - x||2-
xE X,EX
Using the concept of fill distance, we have the following Lemma from Tuo et al. (0000: : Rieger (2008)
Utreras 1988)
Proposition 21 (Proposition 2.6 in Tuo et al. (020)). Let H. be a Sobolev space for function defined on a compact and convex X' with smoothness parameter m. Let {x: Ji=1 be a of scattered point on X' with fill distance and || l|a is the empirical norm induced by X. Then there exists constant (depending only on and X) such that for any H:
|l Ilflligex S C (lifll 9x ll
We also need the following proposition for the distribution of fill distance:
Proposition 22 (Proposition 3 in Krieg & Sonnleitner 20244). Let {x, ~ o be i.id. distributed on compuct and convex set X. Let (()) E". If there exists a positive number Eo such that (x)) ((E) for all S and E B where (x(x) is sphere centered at x with radius Then there exist positive constants Cj2 c22 03, and by such that for any b > bo we have
blog ))
Pr
max inf |xx x, c xES
S C2n c2n' 1-gbb
From Proposition 22
derive that the filled distance on X' with intrinsic dimension is
Qx = O 1/d log n)).
(84)
Lastly, from Geer 2000): Birman & Solomjak (1967). we have the entropy of Sobolev spaces H with smoothness m defined on compact d-dimensional domain
H ll 1la. H) s C18
(85)
where C1 some constant independent of 5.
Now ready to prove the sampling inequality in the form equation 79 our RKHS. According to our assumption, H.s a Sobolev space with smoothness parameter m embedded on a domain with intrinsic dimension d and H.4 is discrete set. So it is straightforward derive that the overall RKHS H a vector-valued function (J1," fA) where each fa E Hss and H is define as
{ f= (f1. ....... fa): :1f11
Σ Ilaal < <00)
Because fe, Q H. we then have
1"1 (()
11 Qill2
C (Ilfa.t Q1 + 2m Il Q 111))
(86)
2m C' (Ilfa.t - Q Op((
log nz
2m Ml 1 111)
50, (1-c7)
Antd 2m
- 2m log 2m )(Q" + +ppnn
120 n
2m
<0, (1 (1-67)
4m
12
2m
24

---

Published as a conference paper at ICLR 2026
where the second line is from Proposition 21 equation 84 the fourth line is from Theorem with
the third line is from the distribution of fill distance and
2m
Case III: Hs is a NTK and A = {a)
According to Chen & Xu (2020), the NTK N associated two-layer neural network Sd equivalent to the Laplace kernel e- ş The Laplace kernel is Matérn kernel with smoothness parameter = 1/2. Also, according to Corollary in Tuo & Jeff Wu (016),, RKHS induced by Matérn kernel with smoothness parameter is equivalent to (Iractional) Sobolev space with smoothness m = // + d/2.
Therefore, we can conclude that H. is equivalent Sobolev space with smoothness (d 1)/2 embedded on gd-1, which has intrinsic dimension d - 1. So Case III is special case of Case II, i.c. Sobolev space with smoothness the value of m and d - 1 into equation T6 we can have the final result.
(d 1)/2 embedded the - dimension. By substituting
Case IV: Hi and H.A are Gaussian RKHSs
Note that K (w,, w/) = || ||--="|| II is Gaussian kernel on the hypercube [0, 1] with d, + dy. So H. is a Gaussian RKHS on [0, 1]d.
From Chapter 4 in Rieger (2008), we have the sampling inequality:
[ S e boog(oooooo / || + cllfll,, Aʃ H
(87)
for some generic constant equation 87 we can have
0. Substitute the distribution of fill distance in equation 84 into
| S cllfll + Op(e llflll Vf 7.
(88)
From Theorem in Kühn (011). the entropy of H is
H || ol B) s C₁ log 8
(89)
where C is some generic constant.
So we can have
Il.r Q² (l Scllse Q7 - Ople 1/v2 }] Q71
log (d+ (d+1)/2) / Op Op(e-n-/va )l
50p((1-c)) -
<0p((1- log logn (d+1)/2)
where the first line from the sampling inequality equation 88 and the second line is from entropy
equation 89 and Theorem 10 with / = 0 and ń = (d + 1)/2.
G PROOF OF LEMMA 12
Proof. We generalize the proof for Proposition 3.1 in Liu et al. (019). following its main lines of reasoning while incorporating additional techniques RKHS. For notation simplicity, denote the Le inner product of on A as (J. 9).4 La (())g
The Lagrangian of equation 19 takes the form
En Ax (x( (s, (-11s)) KL (I((ss)))= + E, (f<((as)) - A(s)
(90)
where A(8) is the L2 Lagrange multiplier defined on (6) By taking the functional derivative of equation 90 with respective to ग, we can have
(+) (8,a) + a(s.a) (log (als) + log 7(s)) A(s)
(91)
25

---

Published as a conference paper at ICLR 2026
where 2(5)= - Sa (a Then equation
91 should holds any 8 (06") and A such that (3) [F(s, a)l and log ((s) is bounded. According to Assumption any (s,a) E (00)) x A satisfies this condition. Then we can solve equation 911, which yields
ग (a|s) = x (a|s) exp A (s.a) a) + A(a) -1 log Z(0)
(92)
In equation 92 we can note that n² (als) must be proportional to (als) explAxf (() (s. a)} because
it is a density on a.
H
PROOF OF THEOREM 13
Proof. From direct calculations, we have for any 8 E S
KL (x (-1s)]1 (+1)) (-|s)) KL. (-1s (+)))|(+<((1)))
A = =(log- xKtI T x , - {log π nh+1 k+1 A
An(p(M) -²* - > + (k(p(k) n//t1 ~ (log nh+11
z xttt111
(93)
= (((()) , - - A - (f( -((), T - ,
kht1
(k()(()) ,- - ~ /
A - (log
: ,T/ A
- ) AA( .
S - AA(Q x -
-Q(A), -T" - x * A
(94)
JA ( (s, (x* - -x++) da
2 (Js | (als) - (a|s)) da
1
S (K( . - nh )
A- - AR( ((1)-Q() -Q(A), n -x
1 (La | - n da + (( (s. (AE / | -x da
2
=
(95)
||rla 1-y
s ~ (K) x- - - Q(M), n a L + A
where equation 93 is from the NPG update rule equation 20 equation 94 is from Pinsker inequality, equation 95 is from the fact that zy n²² < x² and ((k) max (ss,a)//(11 7)))
Taking expectation ESnu- on equation 95 we can have:
Es-.- KL (TT (+s)]] (-1s) - KL (nT (+IS)]]=**+ ((1S))
EESu (.) (-1S) - **(1S))
(96)
Esny Du (())) (,,S),
(.))
" (+|S) - (-+1))
(97)
|11lec 1-7
A
For equation 96
we can use the performance difference lemma in Kakade & Langford 2002
(equivalent Liu et (2019) Lemma 5.1):
Lemma 23 (Performance Difference Lemma). For R[m] defined in equation 21 R[T] - R[mT] = Es (-1)) x
we have
(98)
From equation
98
we directly have for equation 96
Es (.)),, x
(-15)) = Ax (R|T*) R(
(99)
For equation 97
E Es A An(f() - (-18) - *++((1)))
- -Q (f
(als)) (sls))
(s) + / (als)/" (s))))
=2A+ll - -Q21/10
26

---

Published as a conference paper at ICLR 2026
Substitute the above upper bounds for equation 96 and equation 97 into equation 95 and rearrange the terms, we have
Ae (R(x*) R[(x*)) + ESS-~ [KL (1r (+|5) (-I))) KI. (T (-15) (-15)) <2 Q || + (1- -
(100)
By summing over all the k in equation 100 we can have the final result.
I PROOF OF COROLLARY
Proof.
The proof mainly relies on the following L2 and Loe norm embedding inequality
|l S Clllfll 11ff
(101)
for some constants C' and 0 S & < 1 independent of f and is any measure equivalent to the uniform measure S x A. Based on Assumption [ 1/* is lower bounded on S A. we can use equation TOT and Theorem 10 to determine the parameters in Algorithm | such that the Too error satisfies
1
(
(102)
VW
Then by substitute equation 102 and A₂ 1/ V into equation prove the cases one by one
22
we can have the target result. We
Tabular: On the discrete set, obvious that
[Illez(r)) min, V
| = max (f(W) =
Σ
f(w)
(103)
WESXA
WESXA
By letting (k)
-| and | = 0, = 1/2 for the tabular case, we can derive 0 k log (1-cy)
(1-ey)²
from Theorem 17 that the required (k) for the optimal error rate is
(4) = nn | ml =
k - 07)
11 +1
log
Vki nh 1|
We then substitute equation 103 into equation 15
( - Q(1)) 50p ((1 (1
log n 11/2) 11Q(6) 1 + OOp (mitttn))) |1Q
50p
1 Vi
+ +Op
1 nn(111/44
|10(1))
(104)
where the second line is from Lemma
From equation 104 we can note that we also need to make sure that the second term on the right- hand side is in the order 1122, So we may need more samples so that Op (mariszz)) [[Q()) l| I (k--1/2), By solving this equation, we can have the target result.
Sobolev with intrinsic dimension d: According the Cagliardo-Nirenberg inequality, when H is Sobolev space with smoothness parameter m and dimension d, we have
| S ClIll
Zmm bz(ee
(105)
2/3m++d)
By letting (A)
O
17
22m d)
2m4d/22
and B
2m K
for the Sobolev case, we can derive
(1-ey)
from Theorem 17 that the required X (R) for the optimal error rate is
4/2 = = ex)
Im+2
2m+a 1)
||
74
Z
Im
27

---

Published as a conference paper at ICLR 2026
Similar to the tabular case, then substitute equation 105 into equation 16
( - Q 5Op ((a-
2m2-d/2 2m 1d
2m
| Il
SOp
1 VT
NTK:
As we have shown in Section Case III that the NTK N associated to a two-layer neural network gd-1 is equivalent the (fractional) Sobolev space with smoothness m 1 d/2 with intrinsic dimension d 1. Substitute the smoothness (1 + d)/2 2 and intrinsic dimension d - 1 into the Sobolev case, can have the result.
Gaussian: we use Lemma E.4 in Ding et al. (022)) for the interpolation inequality in Gaussian RKHS. states that for any f E H. there exists universal constant C' such that
1l & C
(106)
for any >> 0.
By letting n (A) = - we can derive from Theorem
||s k (1 (1-oy)2
log
|| llakk and B = 0, is = =(d+ 1)/2 for the Gaussian case, 1-ey
17 that the required (A) for the optimal error rate is
(1 (1-r)) (
A = O(n 1 log " )
Ve E (0,
Similar to the tabular case, we then substitute equation 106
into equation 18
-
- 11 SO, ((1- 1 n
d+1
||
S SOp
N-STEP TD LEARNING
In the main paper, introduced the learning of the Q-function using samples generated from one-step transitions evolved from an initial distribution μr. The one-step TD method can be naturally extended N-step TD by viewing the -tsepp dynamics of the original MDP the one-step transition dynamics of an enlarged MDP. The additional sampling steps reduce sampling variance and lead to faster convergence.
In every update of policy т,, we first sample i.i.d. { no Ho from some chosen distribution No and, for each i, generate subsequent states and actions ag and {(st a (2) ( following the Markov chain as follows:
(8) 80
Po:
a (1)
x-1100))
S441
P(-1s ot (2)), al (1-
(107)
In the N-step TD learning, Assumption 6 can be relaxed to the following assumption: Assumption 6B. The marginal density of the N- Ntstep state N given
P P(N s)
= -/P((5 P(S)SN--L,NN-)
-/
N-1
II
((al1s)) ((r.:ls)))())))1,,,, ((ools)))o(0o) T=0
II ds da,)
There exists a constant such that P (sN s) S cpo(s) and Nx <.
The constraint cy < 1 in Assumption is replaced by ex < 1 in Assumption 6B In N-step TD learning, the constant су appearing in the convergence rate in Theorem I0 Corollary II and Corollary 14 can accordingly be replaced by the smaller constant e Icading to faster convergence. The intuition behind this improvement that Assumption 6B is exactly equivalent Assumption on an MDP with the smaller discount factor > modified transition kerne P(s++N St, 4z). and
modified reward F(so, ao)
- N-1 7')(s,,
28

---

Published as a conference paper at ICLR 2026
0, , for any given policy x, we aim to learn the Q-function Q" associated with the N-step Bellman equation in the following form:
Given dataset (wo wi
(0)
(8)
M== with wi (
(6
N-1
(s) =
(z) 8, do = a) 7 "=++"B(("" (s;""(s;,)))) (x),0 00 = a).
(108)
t=
be also treated the Bellman equation associated to MDP with discount factor ? one-step expected reward function E E| 7'r(s,, (t)ss 8, ag = al. and transition kernel P( 80, do). So it is natural to derive that equation 108 can be approximated by solving the following fixed-point KRR over whole RKHS H:
Note that equation 108
108
N-
2 + AILLIEE
Q
min FEH
f(w0) (1)
Σ
+ >'r(aa
(109)
The N-step fixed point KRR equation 109 is almost the same the one-step case equation
except that we replace the terms r(wp)) and 7("T (wa{)) in equation by (Enoo N-1 )*>(w! and
y N (wxx in equation 109 respectively. In the following subsections, we first introduce the connection between the equation 108 and equation (109) and derive the solution of Next, introduce the generalization from the one-step to the -stepp TD update. Finally, we analyze the convergence pattern of N-step TD.
J.1 EMPIRICAL N-STEP BELLMAN EQUATION
We first generalize the definition of covsricov operator on the RKHS H. as defined in Appendix According to equation 107. the distribution of (wo, W1+1) ((so, aq)), (St+1, ac+1)) is given as
Mo+1 ((50, an)), ($1+1, a4+1)
T / II -(i (ar 18 P(rr+1))) daiday ... (mo
Then the generalized N-step cross-covariance operator and its empirical counterpart for (wo, we) be defined as
Cun (((S.A),(SS (0 &(",
Cup.ar 1 Σ (ww
(w)
Using the cross-covariance operators {Cup Jo we then can rewrite the Bellman equation in equation 108 as:
N Σ
Caso.u o
2' (CCoour)) + N Q".
(110)
Equation 110 is exactly equivalent to the Bellman equation defined in equation 41 Since we only
have access to the samples [(wb .... empirical counterpart of equation 110:
w N ) we can only work with the following penalized
-
N N-1
Cunian Q
-
Σ
x Cunnese)
+ + Cunans Q + AQ= =0
(111)
We call equation 111 the N-step empirical Bellman equation. This allows establish generalized version of Lemmal 15 which connects the N-step empirical Bellman equation to KRR. Lemma 24. Solution to KRR (09 equivalent to the N-step empirical Bellman equation 111
Proof. Solution Q to the KRR equation 109 is the minimizer of the following functional
Jifl 1 Σ n 1=1
[(wb())
N Σ
~ + >11
2
-
(112)
0=0
29

---

Published as a conference paper at ICLR 2026
The functional J is Fréchet differentiable obviously with RKHS derivative V [J[l as follows:
Jf
òulla=0
(113)
N
((w00)
Σ >(((a))) - ~~" K(wō) + H)
Vu H.
(114)
Proceeding as in the proof of Lemma 15 yields
v [[J[f] Own.eo &²
Σ X (eCnm
+ 7 Own.w Q= + AQ²
(115)
According to definition, Q7 is also the minimizer of J. Substitute f = Q into equation 115 we
can conclude that the minimization of equation 112 equivalent to equation T09
By reasoning exactly the same as Lemma 16 we can also show that solution Q to the KRR equation 109 is finite-dimensional::
Lemma 25. Let 7 (K (w;, = 1, n be the finite dimensional space spanned by kernel
functions and Q7T be the solution to the KRR equation 109 We have Q7 H.
Similar to the proof for Proposition g we can use Lemma and Lemma
25 to derive the explicit
form for the solution Q7 to the KRR equation
109
From Lemma 25 we know that Q must be of the form:
K(,,:)bb; = K(,,wo)b
(116)
Substitute equation 116 into equation {Cuo IN we then have
togethe with the definition of empirical operators
bi K K(wb)) )
(117)
j=1
1
(w0) (1))
NN-1
Σ >'r(w(()) ) +g Σ by K K( (061))
n
1=1
b, + (wb (1) = O.
+
Rearrange equation 117 and write it in vector form, have
(w)) Kb + Xnb - Tanb-~No ~N = (ww))F.
(118)
where [CN1s, proposition:
K
((w ) and ENN-1 (rr(w, (o) In summary, we have the following
Proposition 26. Let Q" be the solution to the KRR equation 109 Then Q = K(,wwp) where
b K AnI 7 Cn
(119)
J.2 N-STEP KERNEL TEMPEROAL
CEAMPERRAL-DIFFERNCCE DIFFERENCE LEARNING
we see that the KRR estimator in equation 109 has exactly the same form as the KRR formulation in equation g In specific,
From Proposition equation 26
bT min
K( (1)
F, - -2 K(W (K(W)) + Ab Kb.
(120)
bERn
30

---

Published as a conference paper at ICLR 2026
We can observe that the differences between equation 120 and equation are that the constants r(w6))
7, and K ((w))
(1) wo in equation 8 are replaced by r, = 2 >'r(w) ), r and K K(w w)) in
equation 120, respectively. The changes in the constants equation 120 do not affect the procedure
for computing the solution b" We can apply exactly the same iterative rule used for solving equation 8 to obtain ba in equation 120
= (1-=(1-a0))) at)
Σ -
- - f((w))) K(ub".. :.)
(121)
It can also be noticed that equation 121 can be converted to a form similar to semi-gradient TD(T) (Sutton et al. 1998) if represented it by b, K -K- f(loo:
b a, th (f((wo) -F -f- f((W)((
(122)
Similar to the one-step case, the difference between equation 122 and semi-gradient TD(T) in Sutton (1988) lies in the fact that equation T22 uses functional gradient in the infmite-dimensional RKHS, which can be treated as preconditioning to improve the performance of the algorithm.
J.3 CONVERGENCE ANALYSIS OF N-STEP KERNEL TD
We first generalize the error decomposition in Proposition KRR equation 109 the difference function D Q Q" as before and the N-step Bellman residual:
9 for one-step TD. Define for the N-step
N-1 E Σ
(r((u)))) + + (F - (u)
(123)
We have the following error decomposition for the N-step kernel TD Proposition 27.
(D 3 yD (w)))
Σ e D (w(") ((D=,Q"")
(124)
n
Proof. Substitute equation ino equation
we can have
N-1 Σ 7d (Cuoiiee
[Cuo.wo + A1l - O
Owoiwe r + [woo :² Cwo wN Q"1
(125)
Recall that D = Q - Q", we can rewrite equation 125 as
Cunpiroo + AI - N.N (NCoowww D=
(126)
N-
('oiieee t=0
+ N Owanww Q" -wug Q"
XQ=
(127)
Taking the Hilbert space inner product with DE in equation] 126 and equation 127
(D",
Cunn
+ AI
nNN Cunnoo D
(128)
N-1
=(D"
Σ
r' y'Cuower
+ N Cun Q" Cun Q"
XQ )H.
(129)
1=
According to the definition of empirical covariance operators, equation 128 can be further rewritten
(D=, [Cuo.ao + +II - -N Cunpoon )
(130)
D (w/ (1) N D" (w)) (0) (w) (w) 1|I
31

---

Published as a conference paper at ICLR 2026
and using the definition of empirical cross-covariance operators, equation 129 can be further rewritten as
N W-1
(D",
y Auuouu + 7 Cuoown C Q" - Cuo Q- - >Q
(131)
n 71
D ( A(D", ²")
e,
Because equation result.
130 and equation
131 are equals, by rearranging their terms, we can have the final
From Proposition 26 and Proposition 27 the N-step TD can be entirely reformulated an equivalent one-step TD with Bellman residuals having smaller variance. This transformation requires changing only Assumption 6 to Assumption 6B and entails direct mapping: the --step discount 7 becomes the new one-step discount factor, the state-action sequence wN serves as the one-step state-action input, is treated the associated one-step reward, and equation| T23 is the corresponding one-step Bellman residual. Consequently, replacing the one-step TD in the main paper with N N-step TD leaves the convergence results of Theorem [0] Corollary [I] and Corollary [4 unchanged, requiring only the substitution of y with 7. This substitution results in faster convergence rates.
J.4 EXTENSION TO KERNELIZED TD(p)
Following equation 110 we can further rewrite the Bellman equation using cross-covariance operators in the following form
N
N-1
Cun O-
== =1 (1-p)
Σ
Σ
o
+ +7 Cwn Q
(132)
N=1
1=0
Following the same reasoning as the previous subsections, we can directly derive that if we take an -ttep samples {wi (t)
w N=
(1)
} then we can have the empirical counterpart of equation 132
in
N
Cun Q" -
(1
Σ
N-1
Cuo +A²= = (133)
N=1
1=1
which can be reformulated as the following fixed-point KRR
min JEH
1 Σ (1
-
Σ
N
N-
[C
N-1
(xrlas))) + tN007((0)))
+ +Alff
N=1
(134)
Following the same reasoning, we have the following update rule for solving equation 134
f41 (1 ac) (1)
7h Σ
f((wo - -1-
(M K (w))).). (135)
N=1
where r; = (1- ()
Ei= ((((w))))
The main difference between TD(A) and N-step TD is that, by carefully selecting p and N the corresponding Bellman residual can be made arbitrarily small at the cost of increasing sampling steps N This yields faster convergence rate in terms of the number of trajectories n. Consequently, the convergence behavior of TD(p) may differ from that of N N-step TD, and we leave detailed analysis of this for future study.
K IMPLICIT PROXIMAL POLICY OPTIMIZATION
As we have mentioned, in contrast to the original formulation of PPO (Schulman et al.) (017). the variant in 19 replaces KL ( (-Is), (-1s)) with KL (=(-1s), I, x (-[s)). This choice yields closed-fome update for 7 +++1 and we therefore refer to it as explicit PPO. this section, we show that the original PPO be treated implicit counterpart of 19]
32

---

Published as a conference paper at ICLR 2026
K.1 IMPLICIT PPO IN RKHS
The update rule of the original version of PPO in RKHS H is given by
p(l+1) arg max E Ba FEH
A -), (T - KL (TP(+
(136)
((k) x exp(F(()) is the policy from the last where policy is represented as FF x exp(F) update, and f(R) the kernel TD estimator of the Q-function Q(A) trained for iterations. The solution to equation does not admit closed-form expression, but it has an implicit representation analogous to implicit also referred to as the proximal Robbins-Monro method in Toulis et al.
(2021) given as follows:
Lemma 28. The solution to equation 136 satisfies:
(als) = =x (als) + A k+ (als) (s) (1(H)ss (
(137)
for almost all (s, a) A.
Proof. We first define the functional over functions H4:
JIF] = E E- (f) +), (+(s)) KL (-F((-s))[ (-1s))
Let H be the dual space of H. We can take the Fréchet functional derivative of at function F along E HH" and set it to 0:
O&J + 5gl
0.
(138)
6=0
According to equation 136 p(++1) is minimizer of J so it satisfies equation 138 for any y E H From direct calculations, can have
0
A
(s, (cls)sss
5
Ax
(als)da x ++1 (cls)s((ss
+ / [+lss) - t g(s, a)da dsp(s).
(139)
Equation 139 must hold for any g E H. So inside the integral, we must have for almost all (s, E S A:
A (als) (s.0)))) (1) (als)da [T*(s - x x 0.
g(s,a) a)
(140)
By factoring out g(s,a) a) and rearranging the terms inside the brackets in equation 140 equation 137
obtain
We can note that the term x*+1 (s,0)s (s) (T 1- is exactly the functional
derivative of U[F] (s, (-)ss) evaluated at f(++1). The functional U serves
surrogate of the expected total reward functional R in equation 21 with the stationary distribution
v" replaced by the initial distribution μ Consequently, equation 137 is directly analogous to
implicit SGD update:
Equation 137 is non-linear Fredholm integral equation of the second kind. In the case that A discrete and the step size As small enough, it follows directly from the contraction mapping theorem that it can be solved using the following iterative method
T(sla) x (s|a) (at(als) (()) a) (P(*) (s, (.1)(1))))) Va E A.
(141)
However, developing numerical method for solving equation 137 with general S x A lies beyond the scope of this work. We therefore assume that can be solved with sufficiently high accuracy such that the numerical emrrr is negligible. So implicit PPO can be summarized as Algorithm
33

---

Published as a conference paper at ICLR 2026
Algorithm 2 Implicit PPO in RKHS
1: Require: MDP AS, P. r, n) RKHS H
2: Initialize T x ( for some f()) H
3: for k ===0 0, ........ do
4: Select an initial sampling distribution Há and number of samples n (k)
5: Generate {[s)) -9 s1 "aia (5)))) (o)ls)) P()) on)
(8) (1)
6: Set T t T(A) t a (4), t- 17 (k)
7: Initialize ((6)
8:
for 1 1,.. T do
9: Update f(a) - (1 - f Ei= (wb) - r(wb)) +f (w))) K(wb".) (s,
end for
11: Solve N ( = (a|s) + ( (als) - ()(0)ss) ,), +++
end for
K.2 GLOBAL CONVERGENCE OF IMPLICIT PPO
Similar the explicit case, we can have a fundaaental inequality for the one-step improvement
equation 21 Theorem 29. In Algorithm
inf (R|=*] R[xx1)
(2Ax + (() - 110)) )+ (Ex A7 - (1)---)--1 -|rll()) + Es KL (=
Σx A
(142)
Proof. For polices ++1 and R², we have, for s ~ v², the one-step improvement in KL
E Egne'
KL (T (+Is)) ++(ss)
KL (TTI())))++
(143)
x (als)) (a|ss)
=Rgwyr
(als) da
(als) tt (als) - x n da
(als)
/ N (a, / (()) (s (s, a da
-Egwy*
= Byywy'
(s.)) x, (:|8) - ( (-((s))))
Ax(f(0 (s, ((1s))))))))) - **((ss) Var AN (AA))
Egny
(:1s)
(K) (. ** (+1+))
AA(Q(()(s..) - ((h) (s. ), T (-1s) ** (+1s))
34

---

Published as a conference paper at ICLR 2026
where the third line is from inequality log x x 1 for any 0, the fourth line is from the updating policy equation 137 and the sixth line is because
D
( (s, ) x+ (-1s) - - (-1s))
27
=
Σ aEA
(10) a)) x ((ot(()))))
Σ
(s) (s)) (cols)
aEEd
A Var (A,
For term A, we use Lemma 23 to directly have:
ES (N (-15) (-15)) = Ax (R[T") - -R[
(144)
For term
Es A Ax(
- (,,,, - (-1S)))
- <Aall - 121 (a + / x (als) (r)))((((0)) (s)dads)
(145)
=2 - -Q41
For term
(A,)) = =Var =Var (100)))0)0000))0)01))))111 (0)() (A,s) (A,) (A()
Var Var
=110(0) + (1(()) - (+) |1r 3 | + [15(() - 11
(146)
Substitute the above upper bounds equation 144 equation and rearrange the terms, have
[45 and equation 146 into equation
143
A& R)==") ES KL
(+15) *+(S) KI. ( (+1S) (+1S))
(147)
<(2Ax + ()) Q (K)
+ A - --r
By summing over all the & in equation 147 we can have the final result.
We observe that Theorem 29 For implicit PPO is almost identical to Theorem 13 except for the
difference in the constants 24, + A versus 2A, in the Loo error term [[ - Q I| However,
as As > O, the difference vanishes. As a result, the sampling requirement in Corollary [4] for Algorithm also applies to Algorithm 2 since both algorithms share the same policy evaluation error and their one-step improvements differ only by multiplicative constant:
Corollary 30. Let TT
1 be the policies induced by Algorithm Set A 1/VR. For settings Jk=1
listed Corollary set (k) and (M) according to Table [ Set (R), m and (k) according to Theorem 10 with
X (k)) Then under the same conditions Corollary
we have
inf (R[T") - R(=*1) S Op(
(148)
1Skck
L EXPERIMENT SUPPLEMENTS
L. RL ENVIRONMENTS
CartPole-vl (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. The default duration of an episode is 500 time steps.
Acrobot-vl (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
35

---

Published as a conference paper at ICLR 2026
1-1,0,+13). The objective is to swing the free end above target height, with optimal reward of 100. The default duration of an episode is 500 time steps.
HalfCheetah-v5 [awwzyiski 2009); A continuous control task from the MuJoCo physics sim- ulator with 17-dimensional continuous state space and 6-dimensional continuous action space. The state space (Box(-oo, oo, (17,): ), float64)) includes the root position and orientation, joint gles, and angular velocities for 6 hinge joints (back/front thigh, shin, and foot). The action space (Box(-1, 1, (6,) ), float32)) represents torques applied these joints. The goal is to maximize for- ward velocity, with rewards typically ranging from to several thousand, depending on the policy performance. The Half Cheetah never terminates, and the default duration of an episode is 1,000 time steps.
L.2 RUN TIME AND MEMORY COST ANALYSIS
To thoroughly evaluate the computational complexity and scalability of our proposed NPG algorithm. we conducted comprehensive analysis of runtime and memory costs across tasks with varying state-action dimensions and under different step size schedules. The results for discrete control tasks (CartPole-vl I and Acrobot-vl) are summarized in Table 2 while Table presents presents the performance on the higher-dimensional continuous control task (HalfCheetah-vS)) The results correspond to Figure [T the discrete environment runs 1,000 episodes, and the continuous environment runs 10,000 episodes.
Table 2: Performance comparison on Cartpole-vl and Acrobot-vl.
Environment
Cartpole-vi E
Acrobot-vi
Step size
k
k
Kunning time (s)
30.20 = 1.49
19.01
7.39
7,80
1.0=2.1
80.82 = 20.12
19.77 25.28
96.07
2077000 0.31
Peak Memory (MB)
282 1 6.79
272.77 1.10
273.00 0.04
19428
00.02
230.04
1017
230.52 0.16
Table 3: Performance comparison HalfCheetah-v5.
Step size
--1.1 834.23 + 18.56
k-5
k-5.5
Running time (s)
911.84 + 48.86 88.86
917.94 + 72.95
Peak Memory cost (MB)
202.65 = 70.77
116.47 47 = 8.26
160.79 58.42
Analysis:
Our method demonstrates high computational efficiency. In lower-dimensional settings, for CartPole-vl (state dimension 4, action dimension 2), the average runtime remains under 50 seconds across all step sizes; in Acrobot-v1 1 (state dimension 6, action dimension 3), runtimes 0.5 similarly efficient, ranging from approximately 50 to 96 seconds. -055 often yields a favorable balance between convergence speed and stability.
For the high- nigh-dimensional HalfCheetah-vS task (state dimension 17, action dimension 6), the algorithm scales gracefully. Despite the significant increase in state-action space complexity and episode length (1000 steps), the runtime remains manageable, averaging between 834 and 918 seconds for 10,000 episodes.
Memory usage remains stable and relatively low across all environments, confirming the practical feasibility of our approach.
In summary, our proposed NPG algorithm exhibits robust scalability to high-dimensional environ- ments. As our NPG does not require the ordered trajectory sampling, if we use the GPU device, the runtime would be smaller due to parallel computing.
L.3 BASELINE ALGORITHMS
We compare our proposed NPG method with the following baseline algorithms:
Clip-PPO with GAE (Generalized Advantage Estimation): A standard policy gra- dient method that uses value function Vss) to estimate advantages via GAE (Schul- man et al., 2017). The policy update employs clipped surrogate objective L L
E, (in((:(())) A0) (l)) e, + +.)]), where r0) is the importance ratio be-
36

---

Published as a conference paper at ICLR 2026
tween and old policies, and advantages computed as A, = (72)6r+1 +... with 6; = rt + ( -
((t).
Discrete Soft Actor-Critic (SAC): An off-policy actor-critic algorithm adapted for discrete action spaces (Haarnoja et al. 2018). SAC maintains Q-networks reduce overes- timation bias and uses automatic entropy tuning. The policy is updated to maximize the expected Q-value minus an entropy term, encouraging exploration while maintaining sample efficiency.
Deep Q-Network (DQN): A value-based method that learns action-value functions Q(s, a) using temporal difference learning (Mnih et al. 2013). DQN employs experience replay and target networks for stable learning. Actions are selected using e-greedy exploration, and the policy is implicitly defined as the greedy action selection π (()) = arg max, Q(s, a).
Implicit PPO: We explain the details in Appendix
Results Analysis. We show the results of Cartpole-vl as an example in Figure 3 Our results indicate that implicit PPO achieves performance similar to our NPG, and it converges to the optima faster. The reason is that the implicit way, like implicit SGD, performs more stably in policy iteration. The classic clip-PPO is less efficient and more unstable than our NPG, as GAE used clip-PPO requires the complete trajectory; instead, our NPG learns from one-step TD error. Discrete SAC failed to find the optimal solution this setting. DQN, while efficient, exhibited unstable performance across seeds.
As for runtime, although our NPG and implicit PPO have the largest total runtime when run for the full 4,000 episodes in Figure both algorithms already converge within the first 1,000 episodes. If we instead measure runtime only over these first 1,000 Figure and Table 2 the training of NPG and implicit PPO would complete in under 50 seconds.
with the setting in
Learning Curves
Smoothed Learning Curves
600
500
500
Smoothed Returs (w=:60)
400
mWVV
Our NPG
Returns
300
300
Discrete SAC
DON
200
dIoFPO
PPG
200
inplici PPO
dio-PPO
100
500
1000 1500 2000 2500 3000
3500 4000
0
500
1000
1500 2000
2500
3000 3500 4000
Episade
Episode
(a) Reward.
(b) Smoothed reward (window = 60).
Computational Efficiancy
Runtime Comparison
600
20000
500
17500
Total Runbime (secondss
15000
400
22500-
300
226.1s
202.14
Steps
7500
7225
6890
71h4
200
100
126.8s
147.8s
5394
5000
2300
-100
our NPG
Discrete SAC
DON
Implicit PPO
cip-PPO
Our MPG
Discrete SAC
DON Implicn PPO
clip-PPO
(c) Processed steps/second.
(d) Runtime.
Figure 3: Performance and efficiency comparison CartPole-vl under baselines over 10 seeds.
37

---

Published as a conference paper at ICLR 2026
L.4 HYPERPARAMETER CONFIGURATION
Table 4 shows the hyperparameter setting of convergence analysis experiments in Section 6.2 as well as the runtime and memory cost analysis in Section L.2 We use the CPU with Apple M4, Arm64.
Table 4: Hyperparameters of convergence analysis in Figure
Hyperparameter
CartPole-vl
Acrobot-vl
HalfCheetah-v5
Optimizer
Adam MLP with two hidden layers
Network
Hidden width haim for two hidden layer
64
TD Error Loss Coefficient
1.0
Learning rate r)
1 x 10-3
2.5 10
3 10-4
Activation
ReLU 32
ReLU
Tanh
Batch size
32
2048
Algorithm Optimization Epochs (I)
4
4
10
Table presents the hyperparameter configuration used in comparative study (Section 6.3 between classic PPO with GAE and our novel NPG implementation with TD learning on CartPole-V..
Table 5: Hyperparameter Configuration for CartPole-vl Comparison Study in Figure 2
Parameter
Value
Unit
Description
Environment Configuration
Training Episodes
4,000 128
episodes steps
Total training episodes
Update Frequency
Steps per PPO update
Learning Parameters
Learning Rate
1
10-3
Adam optimizer rate
Discount Factor (7)
0.99
Future reward discounting
GAE Lambda (A)
0.95
GAE
trade-off
PPO
0.2
PPO clip parameter
Kl. Penalty Configuration
KL Schedule
k-0.5
Dynamic 3 = schedulle pow
Initial KL Penalty
1.0
Starting So coefficient Policy entropy regularization
Entropy Coefficient
0.01
Training Configuration
Value Loss Coefficient
1.0
Critic loss weighting
PPO Epochs
Policy update iterations Mini-batch size
Batch Size
64
samples
Architecture
Hidden Dimensions
64
neurons
Network layer width Non-linear activation Gradient descent
Activation
ReLU
Optimizer
Adam
Package
Pytorch
Device
CPU
Apple M4, Arm64
L.5 N-STEP TD LEARNING
We verify the generalization our algorithm to N-step TD learning. The experimental results under three look-ahead horizon lengths N on the Halffhhetaa-pp presented in Figure We observe that the convergence pattern is similar Figure where the step size under A -ー achieves
38

---

Published as a conference paper at ICLR 2026
Screduke Compadion et Si
eddie Compatioon Hefthaethhs
Siee Scheta Concertion SaMCrestnnes
2000
Secuemee Nerh www.mme ONEENTIO [1)
510007ee faturr Denddoeeee
1300
1000
500
323
2000
4000
2010
3000
33000
2303
4320
5000
0303
10303
2300
6000
6032
3100
20200
(a)
5
(b) N 10.
(c) N 50.
Figure 4: Smoothed Reward of N-step TD learning HalfCheetah-v5.
the optimal performance. Moreover, we find a clear trade-off between bias and variance. Shorter horizons (N and N 10) yield stable learning curves with lower variance. However, increasing the horizon to N = 50 destabilizes the training. It is attributed to the high variance accumulated over long trajectories, which outweighs the benefits reduced bias in the value estimation.
M USE OF LLMS
this paper, LLMs were used solely for writing polishing several paragraphs, like the Experiment section. All the key ideas, proofs, research, and writing are created completely by human authors.
39


Reviews:
[{"review_id": "uDiViqC91u", "reviewer": "Reviewer_4sex", "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", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 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. \n\n2. 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.   \n\n3.  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.   \n\n4.  Experiments on control benchmarks (CartPole, Acrobot) support the theoretical predictions and show improved stability and efficiency compared with PPO baselines.", "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.  \n\n2. 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.    \n\n3. 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.    \n\n4. 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.    \n\n5. 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.    \n\n6. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f0s8Xc4Mdj", "reviewer": "Reviewer_eHMp", "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.", "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?\n* *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?\n* *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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "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.\n* *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.\n* *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.\n* *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.", "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.\n* *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.\n* *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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fttytWYOiG", "reviewer": "Reviewer_L5Ur", "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.", "questions": "- Does the analysis extend to multi-step TD or TD($\\lambda$) for $\\lambda \\in (0,1]$ with eligibility traces?\n- 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.\n- In conjunction with the previous point, can the analysis here be extended to entropic regularization?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The per-step sample complexity bounds in the paper are definitely interesting and important.\n- 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.\n- The approach to connect TD learning with NPG-PPO-style policy improvement updates is classic yet elegant.", "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.\n- 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}$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PKy3YCmd2v", "reviewer": "Reviewer_4UFk", "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.", "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.\n\n----\n\n**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.\n\nIn 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.\n\n----\n\n**Comments**\n\n1. 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.\n\n2. 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.\n\n3. What does assumption 2 mean in more intuitive terms?\n\n4. 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?\n\n5. How do the results in Corollary 10 relate with previous works?\n\n6. 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?\n\n7. 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?\n\ntypos and minor:\n- l139: \"and it is equipped this space with the bilinear form\" something is off with the sentence construction\n- l151: \"We first impose the following assumption on the Markov chain\". Which Markov chain?\n- l235: \"Derivethe\"\n- l260: \"Unclear whether C_1 and C_2 are universal constants or coming from Asm.1\"\n- l372: misplaced dot\n- l406: missing bracket\n- l454: \"learning Q\" -> \"to learn Q\"", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 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.", "weaknesses": "- The paper may not be accessible for a general RL audience\n- Some assumptions may be unreasonable in most settings (e.g., Asm 1 and 6)\n- Practical implications of the reported results are not stated clearly\n- The empirical comparison between PPO and the proposed algorithm may be flawed or comparing the baselines in mismatching settings", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)