acceptodds
Under review as a conference paper at ICLR 2027

A Closed-Loop Non-Asymptotic Convergence Analysis of PPO with Learned Critics and Clipping

Abstract

Despite its widespread use, Proximal Policy Optimization with clipping (PPO-Clip) remains difficult to tune, and the interactions among critic learning, clipping, and rollout reuse remain incompletely understood. We develop a non-asymptotic analysis of PPO-Clip as a closed-loop actor–critic system. It captures actor–critic coupling, nonsmooth probability-ratio clipping, finite-batch reuse, and predictable early stopping under explicit coverage and critic regularity assumptions, using raw GAE and Monte Carlo critic targets. Our synchronous and asynchronous guarantees jointly characterize policy stationarity and the tracking accuracy of the learned critic, with explicit dependence on algorithmic parameters. A sufficient coupling condition gives optimization, critic tracking, clipping, and finite-batch errors a common amplification bound. The asynchronous result also requires a delay-dependent critic stepsize restriction; violating these conditions does not establish divergence. For finite layered MDPs with tabular critics, a uniform bound on the actual clipped-gradient class replaces complete-trajectory counting. A verified growing-horizon family has polynomial sample complexity, and a two-time-scale schedule gives stationarity and critic-tracking bounds with explicit fresh-rollout accounting. These results together advance our understanding about PPO and provide theoretical guidance in tuning.

Primary area:
reinforcement learning
Keywords:
Proximal Policy Optimization (PPO), Reinforcement Learning Theory, Non-Asymptotic Convergence

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_mbhJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper studies the theoretical convergence guarantee of PPO-Clip algorithm as a closed-loop AC system. The analyzed MDPs are finite-horizon episodic. The paper jointly controls policy stationarity and critic tracking error, showing an explicit coupling amplification factor to elucidate how stochastic noise, clipping bias, multi-epoch data, and KL budget impact the algorithm's finite-time convergence behavior. For structured tabular MDP, it also shows an O(T^{-2/5}) stationary and critic-tracking bounds.

Critical strengths
  1. A unified finite-time convergence analysis of closed PPO AC dynamics. The paper provides a rigorous non-asymptotic analysis controlling policy stationarity and critic tracking error simultaneously, and shows explicitly how each algorithm part (clip, multi-epoch data reuse, KL budget) impact the convergence. This result gives a useful guide for designing appropriate parameters of PPO-clip algorithm.

  2. Careful treatment of adaptive data reuse with structured statistical guarantees. I think a notable technical novelty of this paper is the explicit control of empirical-to-population discrepancies when actor and critic iterates adaptive to the same reused data batch. Furthermore, the structured tabular result establishes uniform concentration for the actual clipped-gradient class without enumerating complete trajectories.

Critical weaknesses
  1. There are some restrictive assumptions. The main theorem of this paper relies on strong critic regularity conditions, including local convexity, quadratic growth, value realizability, and a Lipschitz-continuous selected critic optimum, together with uniform policy coverage and population KL control. These assumptions significantly restrict the applicability of the results to practical neural PPO and RLHF implementations. It would be better if the authors could explain how these assumptions are natural, or if they are commonly used in previous works.
  2. The writing needs substantially improved. Although the manuscript is rigorously structured and technically precise, its presentation is overly long, making it difficult to follow at times. Several topics: (1) the actor–critic coupling, (2) the bias introduced by clipping, and (3) the limitations of theoretical guarantees are revisited repeatedly across the introduction, main results, and appendices without offering any substantive new insights. Furthermore, the main theoretical results are laden with an abundance of constants, auxiliary quantities, and technical conditions, which obscures the core theoretical insights and their significance. The frequent inclusion of qualifying remarks and caveats further disrupts the flow of the argument and diminishes the emphasis on the paper’s primary contributions. In short, the quality of the manuscript could be significantly enhanced by making the exposition more concise and focused, highlighting key technical innovations, providing intuitive understanding before presenting formal statements, and eliminating redundant explanations.
Questions for authors

Q1. How does the proposed framework capture the interaction between critic estimation errors and PPO clipping?

The main theorem controls critic-induced GAE bias through the critic tracking error, while clipping distortion is treated as a separate residual term. In particular, the coupling coefficient vanishes when lambda=1, even though critic errors may still affect clipping decisions through the signs of estimated advantages. Could the authors clarify to what extent the analysis captures this interaction and whether a tighter, tracking-dependent bound on clipping distortion can be established?

Q2. Can the authors further clarify the technical novelty over existing PPO and actor–critic convergence analyses?

Prior works, such as Jin et al. (2024), Wu et al. (2020), and Doering et al. (2026), have already established convergence guarantees for PPO-Clip, learned actor–critic dynamics, and finite-batch reuse under different settings. Could the authors identify which specific technical challenges in the proposed analysis cannot be addressed by directly combining existing results? In particular, it would be helpful to distinguish genuinely new theoretical insights from the integration and refinement of established analytical techniques.

6 comments
AuthorsOpenReview ↗

Rebuttal (1/3)

Thank you for your careful reading and constructive feedback. Below, we address your questions on critic-dependent clipping and technical novelty, clarify the motivation and scope of our assumptions, and summarize the revisions made to improve the paper’s presentation.

Q1. How does the proposed framework capture the interaction between critic estimation errors and PPO clipping?

Response

Thank you for this insightful question. We agree that critic errors can change clipping decisions even at λ=1\lambda=1. The submitted theorem controls this interaction through a uniform clipping residual that does not track critic accuracy. Thus a=0a=0 at λ=1\lambda=1 is compatible with critic-dependent clipped updates.

1. Why the coupling coefficient vanishes and how the residual covers the interaction. The coefficient aa bounds the contribution of critic tracking error to the squared population actor bias before clipping. At λ=1\lambda=1, the TD residuals in GAE telescope. With matched terminal values Vw(sH)=Vπ(sH)V_w(s_H)=V^\pi(s_H) and the prescribed terminal value included in GhG_h,

A^h(w)=Gh−Vw(sh).\widehat A_h(w)=G_h-V_w(s_h).

Relative to using VπV^\pi, the critic error therefore enters only through the state baseline b(s)=Vπ(s)−Vw(s)b(s)=V^\pi(s)-V_w(s). This error is independent of the action at a fixed state. At a fixed checkpoint, exact action importance weighting gives

=b(s)\sum_a\nabla\pi_\theta(a\mid s)=0.$$ This is the cancellation used in Corollary C.2: critic error contributes zero to the unclipped on-policy population direction. Accordingly, $a=4G_\pi^2L_V^2\widetilde C_{\lambda,H}^2$ vanishes at $\lambda=1$, since $\widetilde C_{\lambda,H}=\gamma(1-\lambda)\sum_{j=0}^{H-2}(\gamma\lambda)^j$, and hence $\rho=10ad=0$. The remaining critic-dependent clipping effect is covered by the clipping component of $F$ in Theorem 3.1: $$F_{\rm clip}:=8G_\pi^2A_{\max}^2\kappa(1+1/\delta)^2.$$ Even when $a=\rho=0$, this term contributes to the actor stationarity bound and to the critic tracking bound. It bounds total clipping distortion with learned-critic advantages uniformly over admissible critics, including effects of critic errors on advantage signs. Thus the interaction remains covered by the result, although its dependence on the current tracking error $\Delta_t$ is not explicit. Finite-batch and policy-drift errors are also retained separately in $F$. The refinement below isolates the critic-dependent part of clipping distortion. **2. A refined tracking-dependent checkpoint bound.** Fix the current actor and behavior policy, and define $D(w)=g_{\rm clip}(w)-g_{\rm unclip}(w)$. Both population directions average over behavior trajectories and a uniform time $h$, with weight $\gamma^h$, action ratio $r$, and the unclipped derivative at ties. The removed labels above the upper and below the lower clipping boundaries are $\max(\widehat A,0)$ and $\min(\widehat A,0)$, respectively; both maps are 1-Lipschitz. With matched terminal values, Eq. (C.43) gives $|\widehat A_h(w)-\widehat A_h(w^\star)|\le C_{\lambda,H}L_V\sqrt{\Delta_t}$, where $C_{\lambda,H}=1+\widetilde C_{\lambda,H}$ and $w^\star=w^\star(\theta_t)$. Under this averaging law, Corollary C.1 bounds $\mathbb E[r\,\mathbf 1_{\{|r-1|\ge\delta\}}]$ by $\sqrt{2\kappa}(1+1/\delta)$. Combining this with the score and label bounds gives $$\|D(w)-D(w^\star)\|\le L_D\sqrt{\Delta_t}, \qquad L_D=G_\pi C_{\lambda,H}L_V\sqrt{2\kappa}(1+1/\delta).$$ Consequently, $$\|D(w)\|^2\le 2\|D(w^\star)\|^2+2L_D^2\Delta_t.$$ This separates exact-value clipping distortion from the additional critic-dependent distortion. Since $C_{1,H}=1$, critic-dependent distortion can persist at $\lambda=1$; exact-value distortion can persist at perfect tracking. **3. Changes to the manuscript.** We have added **Proposition C.8 in Appendix C.6**, including both inequalities, a full proof, and an explanation of the remaining critic dependence at $\lambda=1$. We also added cross-references beside the existing clipping bound and in the coupling discussion. All additions are highlighted in red.
AuthorsOpenReview ↗

Rebuttal (2/3)

Q2. Can the authors further clarify the technical novelty over existing PPO and actor–critic convergence analyses?

Response

We appreciate the opportunity to clarify our contribution. Our goal is a joint finite-time guarantee for actor stationarity and critic tracking under the PPO protocol studied here. Our contribution includes both additional discrepancy bounds and the adaptation and integration of established analytical tools.

1. Why this integration requires additional analysis. Both the actor and critic adapt to the same reused buffer. Critic error changes advantages and clipping decisions, while actor movement changes the critic’s population target. Given the training history, the expected minibatch gradients equal the empirical buffer gradients, and single-action importance weighting leaves a behavior-policy continuation error. Controlling these effects jointly requires compatible error bounds under a common sampling history that account for the feedback between the two updates.

The cited works provide important foundations. For our protocol, the remaining requirements are:

  • Jin et al. retain an advantage/sampling discrepancy ϕn\phi_n in their clipped-update guarantee. Our setting requires explicit bounds on the discrepancies arising when both parameters adapt to a reused buffer.
  • Wu et al. analyze online Markovian updates with a linear TD(0) critic. A tracking analysis for our setting must account for stored-return critic fitting and the shared adaptive buffer history.
  • Doering et al. control finite-buffer reuse under reshuffling using a symmetric ratio-truncation proxy and an advantage-bias bound. Our protocol additionally requires control of the actual sign-dependent clipped-gradient class with recomputed GAE.

2. The additional results we establish.

  • Lemma C.5 bounds the actor and critic conditional gradient discrepancies under a common sampling history and isolates the behavior-policy continuation error.
  • Lemma C.6, for bounded tabular critics, controls the actual sign-dependent clipped-gradient class uniformly over the adapted actor and critic. It uses positive and negative parts of the labels within time–state–action cells, avoiding continuity assumptions across clipping boundaries and enumeration of complete trajectories.

These bounds remain valid when the actor and critic share minibatch indices. Integrating them with the actor-progress and critic-tracking arguments allows us to close the coupled recursions and obtain the joint finite-time guarantee, with an explicit sufficient coupling condition and a common amplification factor for residual errors.

3. Changes to the manuscript. We have revised Related Work section to clarify the distinctions from prior analyses and the challenges posed by shared adaptive buffer reuse. The revision identifies the roles of Lemmas C.5–C.6 and distinguishes these additional bounds from the adaptation and integration of established analytical tools. The changes are highlighted in red.

AuthorsOpenReview ↗

Rebuttal (3/3)

W1: restrictness of assumption

Response

Thank you for raising this concern. Our goal is a joint finite-time guarantee for actor stationarity and critic tracking, accounting for clipping and buffer reuse. The assumptions control critic stability, target movement, and distribution mismatch. Related analyses use analogous controls, and several of our conditions are local or admit explicit relaxations.

1. Motivation and theoretical precedents.

  • Critic stability and target regularity. Under the stated smoothness and stepsize conditions, local convexity and quadratic growth support critic contraction, while a Lipschitz selected optimum controls target movement. The geometry is required on regions containing the critic iterates, selected optima, and connecting segments. [1, 2] impose uniform negative definiteness for TD stability; [1] also establishes Lipschitz dependence of the critic fixed point on actor parameters. Our regression conditions serve analogous stability and tracking purposes.

  • Realizability and value accuracy. Realizability identifies the population critic optimum with the true value function, and value Lipschitzness converts parameter-tracking error into a GAE error bound. This isolates tracking effects from representation error while allowing the learned critic to remain imperfect throughout training. Appendix N.3 permits bounded approximation error, retaining the learned-critic dynamics and other premises with an explicit approximation-error floor and a revised coupling condition.

  • Population KL control. Each buffer refresh begins with the current and behavior policies equal, so their KL divergence is initially zero. Under Appendix F's score bounds along parameter segments and gradient bounds, choosing the stepsize and reuse count appropriately guarantees the required population KL budget. Refreshing the reference policy each epoch permits continued policy change across training.

2. Joint consistency and alternative tracking measures.

Appendix J verifies that all premises hold jointly along the actual updates of a growing-horizon construction, establishing their consistency for the specified protocol. Appendix N.2 discusses loss-gap tracking as an alternative to parameter-distance tracking, subject to additional value-error calibration and objective-drift control.

We have added a brief explanation (highlighted in red) immediately after each of the six assumptions in Section 2.4 to clarify its role in the analysis.

[1] A Finite-Time Analysis of Two Time-Scale Actor-Critic Methods

[2] Finite-Time Analysis of Single-Timescale Actor-Critic

W2: writing and presentation

Response

Thank you for these helpful suggestions on presentation. We have made two targeted revisions around Theorem 3.1, with the revised and relocated passages highlighted in red.

1. Present the intuition before the theorem. The revised introduction explains how critic error affects the actor's advantage estimates and how actor movement shifts the critic's population target. It then describes how compatible error bounds yield a joint guarantee under the sufficient condition ρ<1\rho<1, with the common amplification factor (1−ρ)−1(1-\rho)^{-1}.

2. Place the interpretation directly after the result. We moved the existing “Reading the guarantee: decomposition and amplification” paragraph immediately after Theorem 3.1. Readers can now interpret the error terms and coupling factor before proceeding to the two corollaries.

These changes clarify the progression from intuition to the formal guarantee and its interpretation, while preserving the mathematical statements and assumptions. We will further streamline repeated explanations and improve the flow of the exposition in the next revision.

In the end, thank you again for your thoughtful feedback. We hope our responses address your concerns, and we would be happy to clarify any remaining points or discuss further questions.

Reviewer_JR6vOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper gives the first closed loop finite time sample complexity analysis of the PPO-Clip algorithm, where the actor and critic are jointly updated from the same batch of samples using a coupled analysis of the actor and critic updates and no critic oracle is assumed. It also accounts for the non-smoothness induced by the clipping step. The analysis additionally shows that in the asymptotic limit of the batch size, the classical result of actor critic analysis is obtained. To my knowledge, this is the only existing analysis that jointly accounts for 1) bias induced due to GAE via critic estimation error, 2) distortion cause due to clipping, 3) trajectory drift due to importance sampling and off policy reuse. The more realistic analysis of the PPO algorithm is however, performed at the cost of restricting the analysis to either a tabular setup or a setup with linear function approximation since local convexity is needed for the analysis to hold. While in my opinion this is a limitation, the analysis is itself nevertheless, an improvement upon prior related analyses.

Critical strengths

The main strengths of the paper lie in it's analysis of a more realistic and practical implementations of the PPO algorithm. This is demonstrated in the following ways.

1.) Analyzes PPO as it is with critic and actor analyses interleaved at every step from the same pre update parameters and minibatch, using the GAE from the current critic and sample based clipped gradient. 2) Obtaining the uniform concentration for the iterates being fitted on the same batch they are being evaluated on. 3) Improves upon prior analyses where critic oracles were used, thereby sidestepping critic estimation error. Also, prior works assumed multiple critic updates per actor updates, thereby analyzing a regime where critic is stationary for a given actor update, thus moving away from the reaslistic implementations.

Critical weaknesses

In spite of the strengths of the work, I do have one critical objection to the work. It has to do with the assumptions on the problem setup, the work here, while it does get rid of the procedural simplifications of the work, it does so at the cost of assuming that the setup is tabular or has a linear function approximation. This is because the PL and quadratic growth assumption does not hold for neural networks (not in the general case at least). This restriction conflicts with the chief application of the PPO algorithm to begin with. This is exacerbated by the fact that the result does not account for the state space size.

Questions for authors
  1. can you state the dependence on the state and action space cardinality of the sample complexity result?
  2. Is the KL trust region control assumption not an assumption on the bounding of step sizes? Does that conflict with the step size requirement of the main obtaine rate.
2 comments
AuthorsOpenReview ↗

Rebuttal (1/2)

Thank you for the careful reading and thoughtful feedback. We appreciate the opportunity to clarify the assumptions and scope of our results, and we apologize that our presentation did not make this distinction sufficiently clear. Our main convergence theorem does not assume a tabular or linear critic; it applies to parameterized critics satisfying the stated regularity and realizability conditions. Tabular and linear settings illustrate how these assumptions can be satisfied, rather than define the scope of the main theorem.

Q1. can you state the dependence on the state and action space cardinality of the sample complexity result?

Response

We thank the reviewer for this question and apologize that our presentation did not make this dependence sufficiently clear. Our sample-complexity bound captures state/action complexity through Straj=∣Ω∣S_{\rm traj}=|\Omega|, the number of supported complete trajectories, and through constants governing coverage, critic regularity, and coupling.

With KK and the remaining problem constants fixed, Theorem 3.1 and Corollary 3.3 give the sufficient fresh-trajectory count

Q=O(Strajε−7/2),Q=O\left(S_{\rm traj}\varepsilon^{-7/2}\right),

where ε\varepsilon bounds both the average squared actor-gradient norm and the average squared critic parameter error. Each trajectory records a state–action sequence, so StrajS_{\rm traj} reflects how many supported sequences the MDP can generate, including initial-state and reward outcomes. This factor enters both actor and critic sampling errors through ϵB=min⁡{1,Straj/(4B)}\epsilon_B=\min\{1,S_{\rm traj}/(4B)\}, where BB is the number of fresh trajectories per batch.

For deterministic rewards, AA actions, and at most SS states per layer, including the terminal layer,

\le S^{H+1}A^H.$$ This gives an explicit, conservative cardinality bound that can be exponential in $H$. For stochastic rewards, their supported outcomes also contribute to $S_{\rm traj}$. This characterizes the explicit state/action cardinality dependence arising from trajectory counting. Other problem-dependent constants, including coverage and critic regularity, are held fixed and may introduce additional cardinality dependence. > **2. Is the KL trust region control assumption not an assumption on the bounding of step sizes? Does that conflict with the step size requirement of the main obtaine rate.** **Response** We thank the reviewer for this insightful question. **The stepsize requirement and the KL trust-region condition are compatible.** You correctly note that both help control how much the policy changes during training. They constrain different quantities: the learning rate scales each parameter update, whereas the KL condition bounds the policy distribution’s cumulative deviation from the behavior policy during batch reuse. We state them separately because the relationship between stepsize and KL also depends on the update magnitudes and the policy’s sensitivity to its parameters. Our main result, Theorem 3.1, imposes upper bounds on the stepsizes and the within-epoch population KL. Both requirements limit excessive policy movement. Satisfying both of them is equivalent to taking the minimum among them. Therefore, they are naturally compatible. For the rate in Corollary 3.3, compatibility can be verified directly. The corollary uses $\eta_T=c_\eta T^{-3/5}$ and requires $\kappa_T=O(T^{-2/5})$. For fixed $K$, suppose the update directions and policy scores along the connecting parameter segments admit bounds uniform in $T$. Appendix F then gives $$\mathrm{KL}(\pi_{\bar\theta_n}\Vert\pi_{\theta_n^{(k)}}) \le G_\pi G_gK\eta_T =O(T^{-3/5}).$$ Since $T^{-3/5}\le T^{-2/5}$ for $T\ge1$, the prescribed actor stepsize already satisfies the KL requirement under these conditions. The optimization term therefore retains its order $1/(\eta_TT)=O(T^{-2/5})$. The positive stepsize constants can also be chosen to satisfy the critic and coupling restrictions simultaneously, preserving the claimed convergence rate.
AuthorsOpenReview ↗

Rebuttal (2/2)

W1: justification of assumptions

Response

We thank the reviewer for recognizing the strengths of our work and for raising this important question about its scope. We appreciate the opportunity to clarify our assumptions. Theorem 3.1 does not assume a tabular or linear critic parameterization. Section 2.2 defines a parameterized value function VwV_w, and Assumptions 4–5 impose local critic-loss regularity, target regularity, and value realization. The theorem applies to nonlinear parameterizations whenever these and the remaining premises hold on the regions used in the analysis.

1. Why the joint analysis needs these conditions. The critic assumptions provide three distinct controls:

  • Critic stability. Local convexity, quadratic growth around the selected optimum, smoothness, and the critic stepsize restriction support contraction of the critic's parameter error, up to sampling error and target movement.
  • Target regularity. Lipschitz dependence of w⋆(θ)w^\star(\theta) on the actor parameter bounds how far the critic target moves after a policy update. This connects actor movement to critic tracking error.
  • Value accuracy. Realizability identifies the population critic optimum with VπθV^{\pi_\theta}; value Lipschitzness then converts tracking error into a bound on critic-induced GAE error. The learned critic can still have nonzero tracking error throughout training.

These controls close the feedback between the actor and critic and yield the sufficient coupling condition ρ<1\rho<1. Our contribution is a joint finite-time guarantee for actor stationarity and learned-critic tracking that accounts for recomputed GAE, clipping, and shared buffer reuse under these conditions. The proof uses the stated regularity properties of VwV_w and its loss; it does not require VwV_w to be linear in ww.

2. Role of the tabular and linear settings. The tabular constructions demonstrate that our assumptions can hold simultaneously along actual PPO updates; Appendix J provides such a verification. Linear regression offers another familiar setting in which the critic conditions can be checked explicitly. Separately, Corollary 3.2 uses bounded tabular structure to obtain a sampling bound expressed directly in state/action counts. These settings therefore provide concrete examples and a specialized statistical result. They do not define the architectural scope of Theorem 3.1, which applies to parameterized critics satisfying the stated assumptions.

3. Applicability to neural critics. Our critic assumptions concern local loss geometry on the regions used in the analysis. These properties can hold even when a neural-network loss is globally nonconvex. For example, [1] establish local strong convexity of the population squared loss for one-hidden-layer neural networks with trained hidden-layer weights and fixed output weights, under specified distributional and rank conditions and suitable smooth activations. Local strong convexity implies local convexity, PL, and quadratic growth toward the locally unique minimizer, providing a nonlinear neural example of the loss geometry required by our analysis.

The moving-target requirement also admits a sufficient condition for nonlinear critics. If the critic losses are uniformly strongly convex on a common convex region containing their selected stationary minimizers, and the critic gradients vary Lipschitz-continuously with the actor parameter, then the selected minimizer w⋆(θ)w^\star(\theta) is Lipschitz-continuous in θ\theta. This provides a concrete route to satisfying both critic stability and target regularity with nonlinear parameterizations.

These convexity, PL, and quadratic-growth requirements concern the critic; they impose no analogous convexity or PL requirement on the neural actor. Our theorem therefore supports neural PPO in local regimes where its premises, including realizability and uniform regularity, hold along the joint actor–critic updates.

In the end, thank you again for your thoughtful feedback. We hope our responses address your concerns, and we would be happy to clarify any remaining points or discuss further questions.

[1] Recovery Guarantees for One-hidden-layer Neural Networks. ICML.

Reviewer_ZaDeOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The authors provide a sample complexity of convergence of PPO algorithm to stationary point. This result could be interesting, as many of the prior work only consider a modified variant of PPO. But the authors in this paper aim at analyzing the original PPO algorithm. The authors shows a O~(ϵ−3.5)\widetilde O(\epsilon^-3.5) sample complexity of PPO.

Critical strengths

The authors aim at establishing the convergence of the original PPO algorithm along with clipping, which is an important component that makes PPO successful. Almost all prior work on policy space algorithms in RL study a modified version of PPO, without any clipping. The authors provide a finite time convergence bound for this algorithm. The paper is well written and easy to follow.

Critical weaknesses

Assumption 4 of the paper is very restrictive. The authors establish a O~(ϵ−3.5)\widetilde O(\epsilon^-3.5) sample complexity of PPO. However, the best previously known results for policy gradient algorithms has O~(ϵ−2)\widetilde O(\epsilon^-2) sample complexity. For instance, you can look at "Finite-time analysis of single-time scale actor-critic", or "On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation". Then it is not clear why we should look at the results of this paper. We know that the clipping in PPO was what made many of the success stories of PPO. However, the authors are not even establishing the advantage of clipping. How clipping can help in PPO? Decreasing \delta uniformly worsens the upper bound. One important critic of this work is that, as the authors assume step size \eta_T=T^{-3/5}, asymptotically the ratio between \pi_{\theta_t} and \pi_{\bar{\theta}_n} converges to one. Hence, assymptotically the clipping is inactive. Hence the claims about asymptotic results in this paper are invalid.

Questions for authors

If you remove assumption 5, what does change in your results? Does it only create a constant in the upper bound? Can the authors motivate each assumption right after that assumption?

5 comments
AuthorsOpenReview ↗

Rebuttal (1/4)

Thank you for your careful review and questions. Our objective is a joint finite-time guarantee for actor stationarity and critic tracking under the studied PPO protocol, where both parameters adapt to a reused buffer and advantages are recomputed before each update. We explain the role and relaxations of the assumptions, clarify the asymptotic guarantee and sample accounting, and distinguish control of clipping distortion from evidence of a performance benefit.

Q1: If you remove assumption 5, what does change in your results? Does it only create a constant in the upper bound?

Response

Assumption 5 combines exact value realization with value Lipschitzness. Exact realization can be relaxed while preserving the structure of our joint finite-time analysis of actor stationarity and critic tracking under clipping and adaptive buffer reuse. Appendix N.3 establishes this extension with an approximation-dependent residual and a revised sufficient coupling condition. Exact realization in the main text isolates learning and tracking errors from approximation error, making the actor–critic interaction easier to interpret.

Retaining value Lipschitzness and the other premises, let

:=\sup_{\theta\in\mathcal R_\theta} \|V_{w^\star(\theta)}-V^{\pi_\theta}\|_\infty<\infty.$$ Separating tracking error from approximation error gives $$\lVert V_{w_t} - V^{\pi_{\theta_t}} \rVert_{\infty}^{2} \leq 2L_V^{2}\Delta_t + 2\bar{\varepsilon}_{\mathrm{app}}^{2}.$$ Substituting this decomposition into the actor-bias bound yields $$a_{\rm app}=2a, \qquad F_{\rm app} =F+8G_\pi^2\widetilde C_{\lambda,H}^{\,2} \bar\varepsilon_{\rm app}^2.$$ The critic recursion continues to track the selected regression minimizer, with $U$ and $d$ unchanged. The joint bounds retain their form with these substituted constants, subject to $$\rho_{\rm app}=10a_{\rm app}d=20ad<1,$$ and use the corresponding denominator $1-\rho_{\rm app}$. Thus, relaxing realization preserves the central feedback mechanism: critic error affects actor updates, while actor movement shifts the critic target. Its effect is more than changing the prefactor of a vanishing rate: fixed approximation error can leave a nonzero stationarity floor, and the sufficient coupling condition changes. Value Lipschitzness serves a separate role by converting parameter tracking into value-error control. If it is also removed, the joint proof requires a replacement relation between the tracking metric and prediction error. Appendix N.3 therefore relaxes exact realization while retaining this regularity condition. We will clarify these two roles beside Assumption 5 and highlight the existing extension. > **Q2. Can the authors motivate each assumption right after that assumption?** **Response** Thank you for this suggestion. We have added a brief motivation **immediately after each of the six assumptions in Section 2.4**. These paragraphs explain how the assumptions support the analysis before the theorem's constants are introduced. **All six additions are highlighted in red.** The added motivations clarify the following roles: - **Assumption 1: actor progress.** Smoothness relates an actor update to a change in return, while boundedness controls the cumulative objective change in the stationarity proof. - **Assumption 2: minibatch noise.** Conditional variance controls fluctuations around the empirical buffer gradient; its discrepancy from the population direction is bounded separately. - **Assumption 3: clipping distortion.** Bounded raw GAE, together with score and importance-ratio bounds, controls the magnitude of sample directions removed by clipping. - **Assumption 4: critic stability and target movement.** Critic geometry supports contraction for a sufficiently small critic stepsize, while Lipschitz continuity of the selected optimum controls target movement after an actor update. - **Assumption 5: advantage accuracy.** Realization separates tracking error from approximation error, and value Lipschitzness converts parameter tracking into value and GAE error control. - **Assumption 6: policy drift and clipping.** Population KL controls distribution mismatch and clipping activity, while bounded scores convert these controls into bounds on actor-gradient distortion.
AuthorsOpenReview ↗

Rebuttal (2/4)

W1: inactivity of clipping in asymptotic regime

Response

Thank you for this insightful observation. Our main goal is to characterize the finite-time behavior of PPO with a learned critic, including regimes in which clipping remains active. The asymptotic result connects this analysis to the classical two-time-scale actor–critic limit. Clipping inactivity limits what this asymptotic result explains about active clipping, but does not invalidate its stated stationarity and tracking guarantees.

For a fixed number of updates per batch and a fixed clipping width, we agree that the diminishing-stepsize schedule makes clipping inactive under the bounded-update and score conditions described in Appendix F. More generally, inactivity is naturally expected in a convergent PPO run. If the actor iterates converge and the reference policy is refreshed after a fixed number of updates, the current and reference policies approach the same limit. Under the stated regularity and coverage conditions, their likelihood ratios approach one, so a fixed clipping interval eventually ceases to modify the updates. This behavior is therefore a natural consequence of convergence in this setting and is not specific to our choice of stepsize schedule.

W2: restrictness of assumption 4

Response

Thank you for raising this concern. Our goal is to obtain a clear finite-time characterization of the interaction between actor updates and critic learning in PPO. Assumption 4 provides sufficient conditions for controlling two parts of this interaction: the critic’s correction toward a fixed-policy optimum and the movement of that optimum as the actor changes. These conditions restrict the critic class, but allow us to derive interpretable bounds on how actor–critic feedback interacts with clipping and buffer reuse.

Related actor–critic analyses also impose conditions ensuring critic stability and target regularity. [1] assume uniform negative definiteness of the linear TD matrix and establish Lipschitz continuity of the critic fixed point. [2] likewise impose a uniform negative-definiteness condition. Our regression assumptions serve an analogous tracking purpose, although the critic models and update rules differ.

We also provide a concrete setting where these conditions hold. Appendix J verifies the premises along the actual updates of a growing-horizon tabular construction. In particular, the population critic loss has uniformly positive curvature under the verified state coverage, and the selected critic optimum varies Lipschitz-continuously with the actor parameters. This supports both fixed-policy contraction and tracking of the moving target throughout the analyzed run.

These conditions are not automatic for arbitrary neural critics. Our guarantee applies to critic models and visited parameter regions where the stated regularity can be verified. We will clarify this scope and highlight the Appendix J construction alongside the discussion of Assumption 4.

[1] A Finite-Time Analysis of Two Time-Scale Actor-Critic Methods

[2] Finite-time analysis of single-timescale actor-critic

AuthorsOpenReview ↗

Rebuttal (3/4)

W3: Comparison with faster actor–critic rates

Response

Thank you for raising this comparison. The rates are not directly comparable because the training protocols and sample accounting differ. Our analysis also provides insights into PPO dynamics beyond the sample-complexity exponent.

1. Our goal is to understand the joint PPO dynamics. We analyze clipping with advantages recomputed from a learned critic, while both actor and critic learn from the same reused batch. The resulting bounds quantify how these components jointly affect actor stationarity and critic tracking. Corollary 3.3 provides a sufficient sample-complexity bound for this protocol; its optimality remains open.

2. The rates concern different protocols and sample counts. [1] obtain a O~(ε−2)\widetilde O(\varepsilon^{-2}) transition bound for online actor–critic with a linear TD critic and zero approximation error. This is a faster benchmark, but it does not directly cover clipped updates with recomputed advantages and shared batch reuse. [2]'s O(ε−2)O(\varepsilon^{-2}) result counts actor updates, each requiring k+1k+1 critic updates at iteration kk, rather than total transitions.

Our bound counts O~(ε−7/2)\widetilde O(\varepsilon^{-7/2}) fresh length-HH trajectories, or O~(Hε−7/2)\widetilde O(H\varepsilon^{-7/2}) transitions, to make both averaged squared-gradient and critic-tracking errors at most ε\varepsilon. We acknowledge the faster online rate, while emphasizing that the exponents alone do not capture the different protocols and error sources covered by these guarantees.

3. The analysis identifies practical trade-offs in PPO training.

  • Actor and critic stepsizes: Holding other constants fixed, ρ∝(η/βc)2\rho\propto(\eta/\beta_c)^2 quantifies how relative update speeds affect error amplification. Increasing the critic stepsize can reduce tracking lag but also increases its noise contribution.
  • Batch size and reuse: At a fixed fresh-data budget and reuse count, larger batches reduce statistical error but allow fewer updates. Under an explicit drift certificate, Appendix F quantifies the trade-off between additional updates through reuse and increased policy-drift terms in the bound.
  • Policy drift and clipping width: The clipping residual scales with κ(1+1/δ)2\kappa(1+1/\delta)^2. Narrowing the clipping interval therefore worsens this term at fixed policy drift, motivating joint consideration of clipping width and policy drift.

These trade-offs provide quantitative guidance within the stated assumptions. Related discussion appears in Section 3.1 ("Practical implications and tuning guidance"), with the fixed-rollout-budget analysis in Appendix F (Proposition F.1). We will highlight these insights alongside Corollary 3.3 to make the contribution beyond the rate more explicit.

[1] Finite-Time Analysis of Single-Timescale Actor-Critic

[2] On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.