mlsanityData to 14 Oct 2026

Sampling Complexity of TD and PPO in RKHS

arXiv 2509.24991 ↗First posted 29 Sep 2025cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

Key facts. Cited by 1 paper 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.

Builds on

24 of 62 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Elementary Analysis of Policy Gradient Methods4 Apr

Other references · 23

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2015Trust Region Policy Optimizationcited by 2,580
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  5. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  7. 2017A unified view of entropy-regularized Markov decision processescited by 182
  8. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  9. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  10. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  11. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  12. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
11 more
  1. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  2. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  3. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 89
  4. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  5. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  6. 2020Accountable Off-Policy Evaluation With Kernel Bellman Statisticscited by 36
  7. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  8. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  9. 2019Geometric Insights into the Convergence of Nonlinear TD Learningcited by 13
  10. 2015A theoretical framework for calibration in computer models: parametrization, estimation and convergence propertiescited by 12
  11. 2023Random Smoothing Regularization in Kernel Gradient Descent Learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026A Closed-Loop Non-Asymptotic Convergence Analysis of PPO with Learned Critics and Clippingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Tailoring Reproducing Kernels for Optimal Control via Policy Iteration
  2. 2026KLip-PPO: A per-sample KL perspective on PPO-Clip
  3. 2024Enhancing Sample Efficiency and Exploration in Reinforcement Learning through the Integration of Diffusion Models and Proximal Policy Optimization
  4. 2025Reparameterization Proximal Policy Optimization
  5. 2026Structure-Aware Numerical Stabilization for Half-Precision Proximal Policy Optimization
  6. 2026PS-PPO: Prefix-Sampling PPO for Critic-Free RLHF
  7. 2026ANO: Robust Policy Optimization via Bounded, Redescending Gain Fields
  8. 2024Lipschitz-Regularized Critics Lead to Policy Robustness Against Transition Dynamics Uncertainty