# Sampling Complexity of TD and PPO in RKHS

arXiv: https://arxiv.org/abs/2509.24991 · HTML: https://mlsanity.com/paper/2509.24991/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 29 Sep 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 24 of 24)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network](https://mlsanity.com/paper/2007.02486/) (2020)
- [Accountable Off-Policy Evaluation With Kernel Bellman Statistics](https://mlsanity.com/paper/2008.06668/) (2020)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024)
- [Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation](https://mlsanity.com/paper/2106.04096/) (2021)
- [Geometric Insights into the Convergence of Nonlinear TD Learning](https://mlsanity.com/paper/1905.12185/) (2019)
- [A theoretical framework for calibration in computer models: parametrization, estimation and convergence properties](https://mlsanity.com/paper/1508.07155/) (2015)
- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)

## Built on by (most cited first, 1 of 1)

- [A Closed-Loop Non-Asymptotic Convergence Analysis of PPO with Learned Critics and Clipping](https://mlsanity.com/paper/2610.10273/) (2026)

## Abstract (arXiv)

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