Kernelized Advantage Estimation: From Nonparametric Statistics to LLM Reasoning

Shijin Gong, Kai Ye, Jin Zhu, Xinyu Zhang, Hongyi Zhou, Chengchun ShiarXiv 2026 · arXiv

TL;DR

Reinforcement learning for LLM reasoning typically requires either memory-heavy value networks (like PPO) or massive per-prompt sample generation (like GRPO). This paper introduces Kernelized Advantage Estimation (KAE), a method that leverages classical nonparametric kernel smoothing to borrow reward information across training iterations. KAE eliminates the need for a separate value network while achieving low-variance gradient estimation and oracle-level performance under strict resource constraints.

What Problem Does This Paper Address?

Post-training Large Language Models (LLMs) using Reinforcement Learning from Verifiable Rewards (RLVR) has become the standard for boosting complex reasoning capabilities (e.g., math and coding). However, optimizing these models requires estimating an "advantage function" to determine how much better a specific reasoning path is compared to the baseline average.

Currently, practitioners face a difficult trade-off:

  1. Actor-Critic methods (PPO/A2C) train a separate deep neural network to estimate values, incurring massive memory and computational overhead.
  2. Group Relative Policy Optimization (GRPO) eliminates the value network but requires sampling a large group of reasoning traces per prompt to compute a stable average, which is computationally expensive.
  3. Single-trace methods (REINFORCE++) are computationally cheap but suffer from high variance and poor sample efficiency.

This paper targets a practical, resource-constrained setting common in universities and small labs: How do you achieve low-variance, high-quality policy learning when you can only afford to sample a small number of reasoning traces per prompt?

Methods

The authors propose Kernelized Advantage Estimation (KAE). Instead of treating each training step in isolation or training a heavy neural network critic, KAE recognizes that the same or similar prompts reappear across training iterations.

Figure 2: Illustrations of a generic algorithm that unifies A2C, REINFORCE- and GRPO-type algorithms.

KAE treats the training iteration index as a time-like predictor and applies classical kernel smoothing (such as a triangular or exponential kernel) to compute a weighted average of historical rewards for a given prompt. Because the LLM's policy changes incrementally due to a small learning rate, recent historical rewards serve as an excellent, computationally free proxy for the current value function. KAE integrates these historical rewards in a leave-one-out fashion to estimate the baseline without introducing bias.

Datasets

The authors evaluated KAE across three benchmark reasoning datasets using different base models:

  • GSM8K: Grade School Math 8K (evaluated with Qwen2.5-1.5B-Instruct).
  • MATH: A challenging competition-level mathematics dataset (levels 3–5, evaluated with Qwen2.5-Math-1.5B and Qwen2.5-Math-7B).
  • DAPO: A 17k dataset used for multi-stream alignment evaluation.

Key Insights and Ideas

  • Temporal vs. Spatial Averaging: Instead of generating a massive batch of concurrent rollouts to find a stable baseline (spatial averaging, like GRPO), KAE looks backward across training steps (temporal averaging) to harvest baseline data.
  • The "Oracle" Property: The authors theoretically prove that KAE achieves the optimal minimax convergence rate for one-dimensional nonparametric regression. Empirically, KAE performs on par with a hypothetical "oracle" algorithm that has perfect, advance knowledge of the true value function.
  • Reviving Classical Stats for LLMs: While modern deep learning often defaults to "adding another neural network" to solve variance problems, this paper demonstrates that classical, non-parametric statistical tools can match deep critics at a fraction of the cost.

Key Results

  • Drastic Variance Reduction: KAE achieves a 60%–70% reduction in value estimation Mean Squared Error (MSE) compared to GRPO, and an over 90% reduction compared to REINFORCE++. This directly translates to a 32%–65% reduction in gradient estimator variance over REINFORCE++.
  • Downstream Performance Boosts: In multi-stream settings ($G=4$ or $8$), KAE consistently outperforms GRPO, Dr. GRPO, and GPG, yielding an average accuracy improvement of 5% on MATH and 11.8% on DAPO.
Figure 1: Expected rewards of one-shot GRPO (Wang et al., 2025b), the oracle algorithm, and our method (denoted as KAE) on training (left) and testing (right) datasets in the one-shot regime where the training data consists of a single observation. One-shot GRPO applies the standard GRPO algorithm directly to this regime. Shaded areas represent confidence intervals.
  • Training Stability: In single-stream settings ($G=1$), standard REINFORCE training eventually degrades due to high gradient variance. KAE stabilizes training, steadily improving to outperform REINFORCE by 14.9% on GSM8K and 6.6% on MATH by the final iteration.

Limitations and Future Work

  • Prompt Recurrence Dependency: KAE relies on prompts being revisited during training. To maximize its efficiency, the authors implemented a specific prompt-sampling schedule that reuses minibatches for a few consecutive steps. Its performance on entirely non-repeating, infinite prompt streams remains an open question.
  • Bandwidth Tuning: While sensitivity analyses showed KAE is robust across a wide range of kernel bandwidths ($h$), optimal performance still requires selecting a suitable bandwidth hyperparameter.
  • Extension to Token-Level Rewards: The current framework operates under a contextual bandit assumption where rewards are given at the end of a full completion. Extending KAE to token-level or step-by-step dense rewards within full Markov Decision Processes (MDPs) is a promising direction for future research.

Summary updated

Abstract

Recent advances in large language models (LLMs) have increasingly relied on reinforcement learning (RL) to improve their reasoning capabilities. Three types of approaches have been widely adopted: The first relies on a deep neural network to estimate the value function of the learning policy in order to reduce the variance of the policy gradient. However, estimating and maintaining such a value network incurs substantial computational and memory overhead. The second avoids training a value network by approximating the value function using sample averages. However, it samples a large number of reasoning traces per prompt for accurate value function approximation, making it computationally expensive. The third samples only a single reasoning trajectory per prompt, which reduces computational cost but suffers from poor sample efficiency. This paper focuses on a practical, resource-constrained setting in which only a small number of reasoning traces can be sampled per prompt, while low-variance gradient estimation remains essential for high-quality policy learning. To address this challenge, we bring classical nonparametric statistical methods, which are both computationally and statistically efficient, to LLM reasoning. We employ kernel smoothing as a concrete example for value function estimation and the subsequent policy optimization. Numerical and theoretical results demonstrate that our proposal achieves accurate value and gradient estimation, leading to improved policy optimization.
BibTeX
@misc{gong2026kernelized,
  author = {Shijin Gong and Kai Ye and Jin Zhu and Xinyu Zhang and Hongyi Zhou and Chengchun Shi},
  title = {{Kernelized Advantage Estimation: From Nonparametric Statistics to LLM Reasoning}},
  year = {2026},
  eprint = {2604.28005},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.28005},
}
Figure