Analysis of On-policy Policy Gradient Methods under the Distribution Mismatch

Weizhen Wang; Xinzhe Zhou; Jianping He; Xiaoming Duan

cs.LGMar 28, 2025

Analysis of On-policy Policy Gradient Methods under the Distribution Mismatch

Authors: Weizhen Wang, Xinzhe Zhou, Jianping He, Xiaoming Duan

Organizations: School of Automation and Intelligent Sensing, Shanghai Jiao Tong University · Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, China

Abstract

Policy gradient methods are among the most successful approaches for solving challenging reinforcement learning problems. Despite their empirical success, many state-of-the-art policy gradient algorithms for discounted problems estimate update directions using a sampling distribution that differs from the discounted state distribution required by the policy gradient theorem. In this work, we analyze the impact of this distribution mismatch on policy gradient methods. Specifically, {for tabular direct and softmax parameterizations, we establish global convergence of objective values under biased updates}. {For tabular softmax policies, we further derive the exact leading-order coefficients of the asymptotic objective errors under biased and normalized exact updates. Their ratio provides an explicit criterion for determining when distribution mismatch accelerates or slows asymptotic convergence.} We then extend the analysis to more general policy parameterizations by deriving explicit bounds on both the state distribution mismatch and the induced normalized policy-gradient mismatch in episodic and continuing MDPs. These mismatches vanish at least linearly as the discount factor approaches one. Under an additional smoothness assumption, we further show that the limit inferior of the squared norm of the normalized exact policy-gradient direction along the biased iterates is bounded by $O((1-γ)^2)$ in both settings. Our results provide theoretical insights into the robustness of policy gradient methods to distribution mismatch and shed light on the gap between their theoretical formulations and practical implementations.

Figures & tables

Figure 1: Objective-value convergence under biased and normalized exact policy-gradient updates with

\gamma=0.7

Figure 2: Asymptotic convergence under the tabular softmax parameterization. Top: objective values with zoomed-in views. Middle: scaled objective errors and their theoretical limits. Bottom: objective-error ratios and their theoretical limits.

Figure 3: Actor-critic results on CliffWalking with a neural network parameterization. Top: mean discounted returns under biased and corrected training. Bottom: $\ell_{2}$ -norms of the biased and corrected actor gradients and of their difference, all evaluated along the biased-training trajectory.

Figure 4: Actor-critic results on FrozenLake with a neural network parameterization. Top: mean discounted returns under biased and corrected training. Bottom: $\ell_{2}$ -norms of the biased and corrected actor gradients and of their difference, all evaluated along the biased-training trajectory.

Figure 5: Actor-critic results on Acrobot-v1 with a neural network parameterization. Top: mean discounted returns under biased and corrected training. Bottom: $\ell_{2}$ -norms of the biased and corrected actor gradients and of their difference, all evaluated along the biased-training trajectory.

Notation	Meaning
$J(\pi)$	Objective function for policy $\pi$ .
$J(\theta)$	Shorthand for $J(\pi_{\theta})$ .
$P^{\pi}$	Transition matrix corresponding to policy $\pi$ .
$\tilde{\mathcal{S}}$	Relevant state set: $\mathcal{S}$ in continuing MDPs and $\mathcal{S}\setminus\{z\}$ in episodic MDPs.
$\tilde{P}^{\pi}$	Principal submatrix of $P^{\pi}$ indexed by $\tilde{\mathcal{S}}$ in episodic MDPs. It is a row-substochastic matrix.
$d_{0}$	Initial state distribution. $d_{0}(z)=0$ in episodic MDPs; $d_{0}(s)>0$ for every $s\in\tilde{\mathcal{S}}$ .

Table 1: Notation

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: The $4\times 4$ gridworld with terminal states 1 and 16 and stochastic wind toward the right and down.

Figure 7: Objective values under biased and unbiased policy-gradient updates with a shared scalar policy parameter in the gridworld task.

Policy Gradient

Policy gradient methods improve a decision-making policy by estimating how its actions affect expected reward.

See all 69 papers

Jun 17, 2019

Is the Policy Gradient a Gradient?

The policy gradient theorem describes the gradient of the expected discounted return with respect to an agent's policy parameters. However, many policy gradient methods omit the outer discount factor, yielding an update that need not equal the gradient of the discounted objective. Is the resulting update the gradient of another objective? This has been an open question for several years, and this lack of theoretical clarity has led to an abundance of misstatements in the literature. We answer this question for the resulting episode-summed, on-policy update by proving that it need not equal the gradient of any function. Further, we construct a counterexample in which exact expected updates drive the policy toward a deterministic limit that is globally pessimal with respect to both the discounted and undiscounted objectives, while the parameter diverges. We motivate this work by surveying the literature and showing that there remains a widespread misunderstanding regarding discounted policy gradient methods, with errors present even in highly-cited papers published at top conferences.

Chris Nota, Philip S. Thomas

College of Information and Computer Sciences University of Massachusetts Amherst

Policy Gradient Policy Gradient Methods

Ask PDF

Mar 20, 2026

Delightful Distributed Policy Gradient

Distributed reinforcement learning trains on data from stale, buggy, or mismatched actors, producing actions with high surprisal (negative log-probability) under the learner's policy. The core difficulty is not surprising data per se, but negative learning from surprising data. High-surprisal failures can dominate finite-batch updates through large perpendicular components, while high-surprisal successes reveal opportunities the current policy would otherwise miss. The Delightful Policy Gradient (DG) separates these cases by gating each update with delight, the product of advantage and surprisal, suppressing rare failures and preserving rare successes without behavior probabilities. In a tabular analysis, DG suppresses the perpendicular second moment of high-surprisal failures by a policy-overlap factor that vanishes as the learner improves. The advantage sign is essential for surprisal-based filtering: any learner-probability-only gate that suppresses rare failures also suppresses rare successes. On MNIST with simulated staleness, DG without off-policy correction outperforms importance-weighted PG with exact behavior probabilities. On a transformer sequence task with staleness, actor bugs, reward corruption, and rare discovery, DG often achieves nearly order-of-magnitude lower error. When all four frictions act simultaneously, its sample-efficiency advantage is order-of-magnitude and grows with task complexity.

Ian Osband

Google DeepMind

Policy Gradient Methods Policy Learning Distributed RL Sample-Efficient RL Off-Policy RL

Ask PDF

May 11, 2026

Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework

In this work, we show that natural policy gradient, a core algorithm in reinforcement learning, admits an exact formulation as a smoothed and averaged form of policy iteration. Specifically, we introduce doubly smoothed policy iteration (DSPI), a Bellman-operator framework in which each policy is obtained by applying a regularized greedy step to a weighted average of past

Q

-functions. DSPI includes policy iteration, dual-averaged policy iteration, natural policy gradient, and more general policy dual averaging methods as special cases. Using only monotonicity and contraction of smoothed Bellman operators, we prove distribution-free global geometric convergence of DSPI. Consequently, standard natural policy gradient and policy dual averaging achieve an iteration complexity of

\mathcal{O}((1-γ)^{-1}\log((1-γ)^{-1}ε^{-1}))

for computing an

ε

-optimal policy, without modifying the MDP, adding regularization beyond the mirror map inherent in the update, or using adaptive, trajectory-dependent stepsizes. For the unregularized greedy case, corresponding to dual-averaged policy iteration, we also prove finite termination. The same Bellman-operator framework further extends to discounted MDPs with linear function approximation and stochastic shortest path problems.

Phalguni Nanda, Zaiwei Chen

Edwardson School of Industrial Engineering, Purdue University

Policy Gradient Reinforcement Learning Natural Gradient Methods Natural Policy Gradient Policy Optimization Policy Iteration+2

Ask PDF

Abstract

Policy Gradient

Explore similar work

Is the Policy Gradient a Gradient?

Delightful Distributed Policy Gradient

Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework