PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Junwei Su, Mengfan Liu, Yanyong Zhang, Chuan Wu

arXiv:2610.10273v1cs.LG

TL;DR

PPO-Clip’s interacting critic learning, clipping, and rollout reuse remain difficult to analyze jointly. The paper develops a non-asymptotic closed-loop actor–critic analysis, yielding O(T^-2/5) stationarity and critic-tracking bounds under a sufficient coupling condition.

  • Problem

    Existing analyses do not jointly guarantee control of PPO mechanisms whose actor, critic, and reused-data dependencies interact.

    Source: §1 · p. 2

  • Method

    The paper analyzes PPO-Clip as a closed-loop actor–critic system, jointly controlling actor stationarity and critic tracking under explicit assumptions.

    Source: §1 · pp. 2–3, §5 · p. 12

  • Results

    O(T^-2/5) stationarity and critic-tracking bounds follow from an explicit two-time-scale schedule.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The bounds provide sufficient, problem-dependent guidance for coordinating actor–critic timescales, KL budgets, clipping ranges, and batch reuse.

    Source: §1 · p. 3

    The guarantees assume coverage, value realizability, and critic regularity, do not cover unrestricted neural PPO, and have conservative constants.

    Source: §1 · p. 3

Abstract

from arXiv · show

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 \emph{non-asymptotic} analysis of PPO-Clip as a \emph{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 $O(T^{-2/5})$ stationarity and critic-tracking bounds with explicit fresh-rollout accounting. These results together advance our understanding about PPO and provide theoretical guidance in tuning.

1 Introduction

PPO-Clip’s actor–critic coupling, clipping, and rollout reuse make their joint behavior difficult to analyze and tune. This paper develops a non-asymptotic analysis that jointly bounds policy stationarity and critic tracking under explicit assumptions.

Existing Gap

  • Existing results analyze finite-time actor–critic learning, PPO clipping, or learned value estimation separately, while their interacting dependencies make a joint guarantee a substantive challenge.Critic errors affect actor advantages, policy changes move the critic target, and both adapt to reused data.Source: §1 · p. 2

Contributions and Results

  • The analysis combines policy-gradient, concentration, and tracking arguments to study PPO-Clip as a closed-loop actor–critic system.It covers raw-GAE updates, Monte Carlo critic targets, finite-batch reuse, and empirical and trajectory-policy discrepancies under explicit coverage and critic regularity.Source: §1 · pp. 2–3

Unified finite-time analysis

  • A sufficient coupling condition gives finite-time control of policy stationarity and critic tracking, with a common amplification bound for noise, tracking, reuse-induced drift, and clipping bias.For tabular critics in finite layered MDPs, a uniform bound on the actual clipped-gradient class replaces complete-trajectory counting.Source: §1 · p. 3

Finite-time refinement

  • O(T^-2/5) stationarity and critic-tracking bounds follow from an explicit schedule, while the finite-time refinement quantifies residual errors from reuse, clipping, and behavior-policy mismatch.The schedule also has a rollout-budget bound; these are sufficient upper bounds, not necessary instability thresholds.Source: §1 · p. 3

Extension to asynchronous PPO-Clip

  • The asynchronous guarantee includes staleness penalties and requires a delay-dependent critic stepsize restriction and a sufficient coupling condition.It applies under prescribed batch assignment and nonanticipative sampling.Source: §1 · p. 3

Scope and limitations

  • The guarantees rely on explicit coverage, value-realizability, and critic-regularity assumptions, and do not cover unrestricted neural PPO.The tabular experiments are qualitative illustrations, and the conditions are sufficient and problem-dependent.Source: §1 · p. 3

2 Preliminaries and Problem Formulation

The section sets up a finite-horizon actor–critic analysis in which the critic estimates policy-dependent values and PPO reuses behavior-policy rollouts. It specifies the assumptions and sampling protocol used to analyze the coupled updates.

2.1 Finite-Horizon Episodic Setting

  • The setup is a finite-horizon episodic MDP with a fixed reward mechanism; sampled data and a learned value baseline provide advantage estimates when true advantages are unavailable in closed form.The motivating LLM example treats generated tokens as actions and evaluates trajectories with a fixed reward model.Source: §2.1 · pp. 3–4

2.2 Actor–Critic Framework

  • The critic minimizes a policy-conditioned regression loss to track the value function associated with the current policy, and its tracking error controls bias in the actor update.As the actor changes, the critic’s state distribution and target move.Source: §2.2 · p. 4
  • GAE uses critic-based temporal-difference residuals, with λ trading variance against bias; the analysis quantifies critic-induced bias through λ and critic tracking error.The stated return convention requires matching terminal values; a nonmatching terminal bootstrap needs an additional bound.Source: §2.2 · p. 4

2.3 Modern PPO-Clip Surrogate

  • PPO-Clip reuses rollouts collected under a behavior policy, using likelihood ratios and clipping to address distribution shift while introducing nonsmoothness and clipping bias.The clipping parameter δ determines the clipping range, and the analysis controls distortion from active sample directions differing from their unclipped counterparts.Source: §2.3 · p. 5

2.4 Objective of the Analysis and Assumptions

  • The analysis targets non-asymptotic convergence for a learned actor–critic and assumes a bounded, smooth objective plus critic learnability, stability, and value realization.The critic loss is locally convex and satisfies PL and quadratic-growth conditions in the stated region.Source: §2.4 · p. 6
  • The sampling premises include a population KL budget and separate coverage and boundedness assumptions; KL control alone does not establish critic geometry or realizability.The finite-sample bridge uses finite trajectory support, while a tabular specialization uses finite layered states and actions, a bounded critic, and bounded returns.Source: §2.4 · pp. 6–7
  • Each outer iteration collects B independent behavior-policy trajectories, retains their Monte Carlo returns, and reuses the batch for K joint updates with raw GAE recomputed before each update.The actor and critic use empirical gradients evaluated at pre-update parameters; minibatch noises may be correlated.Source: §2.4 · p. 7

3 Main Results

The synchronous analysis jointly bounds actor stationarity and critic tracking, with a coupling condition that controls how finite-time errors are amplified. It also gives a tabular finite-batch result, an explicit rate and rollout budget, an asynchronous extension, and mechanism-checking experiments.

3.1 Convergence of PPO-Clip

  • When the coupling coefficient ρ is below 1, the synchronous guarantee jointly controls actor stationarity and critic tracking, with actor–critic feedback amplifying finite-time errors.The bound separates optimization and stochastic noise from reuse, trajectory drift, clipping, and critic-target mismatch; ρ < 1 is sufficient to close the coupled inequalities.Source: §3.1 · pp. 7–9
  • For finite layered MDPs with tabular critics, a uniform bound on the actual clipped-gradient class replaces complete-trajectory counting in the finite-batch result.The bound covers adaptive reuse without assuming continuity of the clipped gradient in actor parameters; a verified family has polynomial bounds in H despite 2^H action paths.Source: §3.1 · p. 8
  • With η = cηT^-3/5, βc = cβT^-2/5, κT = O(T^-2/5), and the stated batch choices, stationarity and critic error are both O(T^-2/5).The sufficient fresh-trajectory counts for error at most ε are O(ε^-7/2) under finite support and eO(ε^-7/2) under the tabular corollary.Source: §3.1 · pp. 7–8
  • The bound motivates coordinating KL budget, critic stepsize, critic quality, and batch reuse; smaller clipping ranges can make its κ/δ^2 distortion term less informative.This is an upper-bound implication, not a monotone claim about actual clipping bias; increasing reuse K has effects that depend on policy drift.Source: §3.1 · p. 9
  • The finite-time bound recovers classical two-time-scale actor–critic stationarity and critic tracking under diminishing stepsizes and vanishing trust-region budgets.Its finite-time characterization makes coupling explicit through (η/βc)^2 and includes bias floors controlled by κ and δ through κ/δ^2.Source: §3.1 · pp. 9–10
  • The asynchronous extension adds staleness penalties and requires a delay-dependent critic stepsize restriction as well as ρasync < 1.Source: §3.1 · p. 10

3.2 Empirical Study

  • The experiments illustrate joint actor–critic tracking, finite-batch error under adaptive reuse, and critic–clipping interaction, but do not test theorem rates or bound tightness.In the two-step example, population GAE bias vanishes at λ = 1 while finite-batch and behavior-policy/clipping residuals remain; at K = 64, mean interaction is 2.04 × 10^-3 for the slow critic and 4.21 × 10^-4 for the fast critic.Source: §3.2 · pp. 10–11, Figure 1 · p. 11

4 Related Work

Prior work studies policy gradients, learned critics, and PPO clipping under varying assumptions, while this analysis derives discrepancies for interleaved raw-GAE/Monte Carlo updates and closes the resulting actor–critic recursions.

4 Related Work

  • Learned critics can reduce policy-gradient variance but may introduce bias when approximate, while actor–critic theory also studies finite-time critic tracking.The cited literature includes classical policy-gradient convergence and non-asymptotic actor–critic analyses.Source: §4 · p. 11
  • PPO analyses vary in policy, value-estimation, and sampling models; prior work retains nonsmooth clipping and multiple updates or includes learned value estimation.Those features alone do not distinguish the present analysis.Source: §4 · p. 11
  • This analysis derives advantage and sampling discrepancies for interleaved raw-GAE/Monte Carlo updates and closes the resulting actor–critic recursions.For finite layered MDPs with tabular critics, it controls adaptive reuse through trajectory-function classes rather than complete-path counting; Table 1 compares updates and statistical premises.Source: §4 · p. 11, Table 1 · p. 12
  • Guarantees cannot be directly ranked across analyses that use different objectives, sampling laws, or geometries.Table 1 presents closest theoretical comparisons under each work’s assumptions, with the paper’s row describing its structured tabular specialization.Source: §4 · p. 12, Table 1 · p. 12

5 Concluding Discussion

The discussion frames PPO-Clip as a closed-loop actor–critic system, analyzing policy stationarity and critic tracking across synchronous and asynchronous settings under explicit sampling assumptions. It emphasizes that critic tracking and actor drift co-evolve, with clipping and KL control modulating their coupling, and cautions that open-loop predictions may not match LLM PPO runs with online learned critics, bootstrapped targets, and interleaved multi-epoch reuse.

5 Concluding Discussion

  • The analysis jointly characterizes policy stationarity and learned-critic tracking for synchronous and asynchronous PPO-Clip, accounting for coupling, nonsmooth clipping, old-policy trajectories, and finite-sample multi-epoch reuse.Source: §5 · p. 12

Synchronous Result Dependencies

Dependencies for Extensions and Examples

  • Asynchronous convergence combines finite-batch bias at stale parameters with delayed-critic tracking, subject to nonanticipative scheduling, mixed-parameter regularity, delay-dependent critic stepsize, and coupling conditions.Source: Dependencies for Extensions and Examples · p. 19
  • Predictable stopping adapts one-step inequalities to a predictable gate; verified growing-horizon examples combine structured statistics with explicit bounds on remaining problem constants.Source: Dependencies for Extensions and Examples · p. 19
  • The loss-gap route remains conditional on additional drift and calibration estimates rather than a proved replacement theorem, while the approximation-error extension uses a parameter-distance argument.Source: Dependencies for Extensions and Examples · p. 19

A.5 The role of actor–critic dependency

  • The analysis links critic learning to advantage distributions and surrogate geometry, while critic error evolves with actor drift.For a fixed critic under on-policy sampling and matched terminal values, critic-error contribution cancels at λ=1 or H=1, though empirical-batch, policy-drift, and clipping errors may remain.Source: §A.5 · p. 24
  • Open-loop predictions may not match LLM PPO runs with online critic learning, bootstrapped targets, and interleaved multi-epoch reuse.The cited examples include predictions of monotone improvement, stable steps under a fixed KL budget, and negligible bias floors.Source: §A.5 · p. 24
  • PPO’s coupled updates create feedback in which critic tracking and actor drift co-evolve, with clipping and KL control modulating the coupling.The analysis treats these errors as co-evolving rather than as exogenous noise.Source: §A.5 · p. 24

A.6 Objective of the analysis

The analysis treats PPO-Clip with a learned critic as a closed-loop system: actor advantages depend on the critic, while the critic’s regression objective moves with the policy. Its bounds quantify this coupling alongside clipping and reuse errors.

A.6 Objective of the analysis

  • The actor update uses advantages that depend on the learned critic.The critic follows a policy-dependent regression objective whose minimizer moves with the actor.Source: §A.6 · p. 24
  • The critic’s regression objective changes with the actor’s policy.Its minimizer moves as the actor changes.Source: §A.6 · p. 24
  • The bounds quantify actor–critic coupling through critic error’s contribution to actor stationarity and actor drift’s effect on critic tracking.They also include error terms from clipping and multi-epoch reuse.Source: §A.6 · p. 24

B Extended Related Work

The section situates the analysis within actor–critic, PPO, and tracking theory while detailing how critic-induced GAE bias and nonsmooth clipping effects are handled. Its guarantees concern stationarity and critic tracking under stated premises, without claiming global optimality or applying to arbitrary PPO implementations.

B Extended Related Work

  • The analysis closes actor and critic bias bounds for interleaved, reused-batch PPO, while its structured specialization avoids trajectory-count dependence but retains coverage, realizability, critic-geometry, and population-KL premises.The guarantees cover stationarity and critic tracking; they do not assert global optimality or cover arbitrary neural PPO or LLM fine-tuning implementations.Source: B Extended Related Work · p. 26

C Useful Lemmas

  • The lemmas bound critic-induced GAE bias and clipping- and trust-region–induced distortion at intermediate reused-batch iterates, with explicit dependence on critic tracking error, λ, δ, and κ.Neither actor nor critic needs to have converged for these bounds to apply.Source: C Useful Lemmas · pp. 26–27

C.1 Bounds for critic-based advantage estimation

  • The finite-horizon GAE bias bound depends on value-estimation error, λ, horizon, and terminal convention; matched terminal values remove the terminal term, while population bias vanishes for λ = 1 or H = 1.The bound concerns conditional mean bias, not variance; population cancellation assumes an on-policy expectation with a fixed critic and does not remove empirical, clipping, or old-policy discrepancies.Source: §C.1 · pp. 27, 30

C.2 Handling PPO-Clip non-smoothness via event localization

  • PPO-Clip’s nonsmoothness is localized to sign-dependent clipping events, where the update can differ from the unclipped gradient; outside them, the sample derivative matches it, but reused-batch updates need not be unbiased.At a zero-probability active boundary, the population objective is differentiable; clipping distortion is weighted by the probability of the clipping event.Source: §C.2 · pp. 30–31
  • Clarke derivatives use selectors 1 or 0 away from the boundary and a value in [0, 1] on it, with nondifferentiability at the corresponding clipping thresholds.Source: §C.2 · p. 33
  • Common support and normalization give an integrable local envelope for differentiation under the expectation; when the boundary has positive mass, the joint expectation includes the chosen selector.Source: §C.2 · pp. 32–33
  • The clipping difference is supported only where |rθ − 1| ≥ δ, and the analysis does not identify it with an arbitrary population Clarke subgradient.Source: §C.2 · p. 33

C.3 Bounding clipping-induced bias

The section bounds clipping distortion and clipping-related empirical errors through KL control and uniform gradient-class control, including an alternative empirical-gradient bridge for tabular critics that avoids counting complete trajectories. It also decomposes open-loop bias into critic error, trajectory drift, clipping distortion, and finite-batch reuse error.

C.3 Bounding clipping-induced bias

  • Clipping distortion is controlled through clip activation, advantage and score envelopes, and KL divergence; an active clipping event need not create nonzero aggregate bias.The corollary compares population clipped and unclipped surrogate directions, not the unclipped direction with the current-policy return gradient or empirical KL with population quantities.Source: §C.3 · pp. 33, 35, 36

C.4 Finite-batch bias under adaptive rollout reuse

  • The finite-batch comparison bounds actor and critic discrepancies under adaptive rollout reuse, with centered conditional variance bounds for both update directions.It covers raw GAE recomputed using the current pre-update critic and stored Monte Carlo critic targets; the finite-support error floor scales as Straj/B and is not removed by more inner updates.Source: §C.4 · pp. 36, 39, 40

C.5 A structured bridge without trajectory counting

  • For finite layered MDPs with tabular critics, uniform bounds on the actual clipped-gradient class avoid complete-trajectory counting, even with continuous reward distributions.The bounds apply simultaneously to admissible actor parameters and critics selected adaptively after arbitrarily many preceding uses of the batch, without a covering number for actor parameters.Source: §C.5 · pp. 40–41, Their conditional second moments obey · p. 41

Their conditional second moments obey

  • The tabular-critic bridge also supplies conditional second-moment bounds and remains valid for parameters chosen adaptively at deterministic outer–inner indices.No covering number for actor parameters is required.Source: Their conditional second moments obey · p. 41
  • The clipped-gradient bound is uniform over admissible actor and critic parameters, so it covers data-selected parameters without requiring continuity in θ.The proof also avoids a measurability assumption on an uncountable actor supremum.Source: Their conditional second moments obey · pp. 42–43
  • Under the structured setting and retained population-comparison assumptions, the actor and critic bias conclusions hold with coefficient a without finite trajectory support; the synchronous theorem applies when its remaining premises hold.Layered tabular structure supplies a uniform bound for the critic class, and the synchronous result still requires its smoothness, critic-contraction, and stepsize premises.Source: Their conditional second moments obey · pp. 43–44
  • With M, d_V, W, G_max, and A_max = O(H) and bounded score and ratio envelopes, the uncapped bounds are e_a(B) = O(H^3 log(B + H)/B) and e_c(B) = O(H/B).The complexity terms depend on the dimensions of the specified gradient classes rather than the number of complete action sequences.Source: Their conditional second moments obey · p. 44

D Open-Loop Convergence Results

  • The open-loop actor bias decomposition separates critic-induced advantage error, within-epoch trajectory drift, clipping distortion, and finite-batch error under adaptive reuse.These bounds treat critic tracking error as an input; the closed-loop analysis combines actor and critic inequalities to control it.Source: D Open-Loop Convergence Results · p. 45

D.1 Open-Loop Convergence Results for the Actor

The section establishes separate open-loop bounds for actor stationarity and critic tracking over the actual actor–critic updates. The actor bound decomposes PPO-specific bias, while the critic bound accounts for target drift and sampling bias.

D.1 Open-Loop Convergence Results for the Actor

  • The actor’s open-loop stationarity bound has O(1/(ηNK)) optimization and O(η) noise terms, plus critic, drift, clipping, and finite-batch bias.The finite-batch term is not removed by taking more inner updates.Source: §D.1 · p. 46
  • The actor’s conditional update bias separates into empirical-to-population error, clipping distortion, trajectory drift, and current-policy GAE error.The trajectory comparison includes behavior-policy continuation effects in multistep GAE, and the random advantage sign remains inside the clipping selector.Source: §D.1 · pp. 46–47

D.2 Open-Loop Convergence for the Critic

  • The critic tracking guarantee relies on convexity, smoothness, quadratic growth, and a Lipschitz moving minimizer along actor iterates.The convex region must contain the current critic iterate and selected stationary minimizer.Source: §D.2 · pp. 48–49
  • The critic tracks the moving current-policy population minimizer, with an explicit bias floor from stored-batch Monte Carlo data and a target-drift term scaling as η^2/β_c^2.The stored-batch discrepancy is treated as bias, not martingale noise.Source: §D.2 · p. 48

E Closed-Loop Convergence Results

The section combines actor and critic recursions to bound closed-loop stationarity and critic tracking while accounting for finite-batch and trajectory mismatch. A sufficient coupling condition controls the combined bounds, without requiring population-unbiased updates or independent actor and critic minibatches.

E Closed-Loop Convergence Results

  • Finite-batch error remains even with an exact critic, identical behavior and current policies, and inactive clipping.The actor–critic analysis does not require population-unbiased updates or independent minibatches.Source: E Closed-Loop Convergence Results · p. 50
  • The trajectory comparison accounts for behavior-policy continuation in multistep GAE, which a single action ratio does not make on-policy.The closed-loop proof combines actor and critic recursions while accounting for finite-batch error and trajectory mismatch.Source: E Closed-Loop Convergence Results · pp. 49–50
  • Under the sufficient coupling condition ρ = 10ad < 1, the combined recursions yield critic-tracking and actor-stationarity bounds.The critic inequality is solved before substituting its bound into the actor stationarity inequality.Source: E Closed-Loop Convergence Results · pp. 50–51

F Rates and Rollout-Budget Consequences

The section gives rollout-budget consequences and rates under prescribed schedules, then establishes a classical two-time-scale limit. These guarantees concern stationarity and critic tracking, not policy optimality or monotonic return improvement.

F Rates and Rollout-Budget Consequences

  • The prescribed schedule gives O(T^-2/5) stationarity and critic-tracking bounds, with T = O(ε^-5/2) sufficient and an extra logarithm in the structured-case rollout count.The bounds are averages of squared errors, not gradient-norm guarantees at the same numerical tolerance.Source: F Rates and Rollout-Budget Consequences · p. 51
  • The continuous minimizers optimize the stated upper bound only; actual choices must satisfy the protocol’s integer, coverage, sampling, and stepsize requirements.The proof recommends checking neighboring feasible values on a discrete feasible set.Source: F Rates and Rollout-Budget Consequences · p. 52
  • At fixed rollout budget, larger batches reduce uniform statistical error but allow fewer updates, while greater reuse supplies updates and increases certified drift.The stationarity guarantee does not show that relaxed choices maximize return or that the upper bound is tight.Source: F Rates and Rollout-Budget Consequences · p. 52

G The Classical Two-Time-Scale Limit

  • Under the stated growing-batch and vanishing-coupling conditions, both finite-batch error and error from stored behavior-policy targets vanish.The critic and actor bounds then tend to zero under the classical schedules.Source: G The Classical Two-Time-Scale Limit · p. 53
  • The result establishes expected stationarity and critic tracking, not policy optimality or monotonic improvement in return.Appendix I supplies a concrete nonempty family of admissible schedules.Source: G The Classical Two-Time-Scale Limit · p. 54

H Predictable Early Stopping and Population KL Control

The section extends finite-time control to predictable early stopping under a population-KL certificate. Its update-weighted bounds adjust the finite-batch term for the reduced number of executed updates.

H Predictable Early Stopping and Population KL Control

  • Predictable stopping requires the population KL budget; an empirical KL statistic alone does not provide this certificate.The stopping gate is measurable before the current minibatch draw, and both actor and critic updates are skipped on inactive slots.Source: H Predictable Early Stopping and… · p. 54
  • A predictable gate can combine the population certificate with an empirical stopping threshold, but rejecting a proposal after inspecting its fresh stochastic gradient is not covered.The population certificate must cover the executed step, including a step that raises empirical KL above its threshold.Source: H Predictable Early Stopping and… · p. 54
  • The finite-time result replaces T with expected executed updates R and scales the finite-batch term by χ = Tmax/R.The batch adjustment applies to F and Ec, while the theorem retains its other definitions.Source: H Predictable Early Stopping and… · p. 54
  • Predictability preserves conditional noise cancellation; inactive slots add no progress or critic contraction because parameters remain unchanged.The output ratios of expectations weight runs proportionally to their executed updates.Source: H Predictable Early Stopping and… · p. 55

I An Explicit Finite-Batch Actor–Critic Example

The section constructs a two-step finite-batch PPO-Clip example with a learned tabular critic, then verifies nontrivial actor–critic feedback and a vanishing-error schedule.

I An Explicit Finite-Batch Actor–Critic Example

  • The example is a horizon-two MDP with one initial state, two time-one states, and two actions, using a scalar actor and three-parameter tabular critic.Both Monte Carlo returns in a trajectory equal R, and the current-policy population reference loss has the true, unnormalized value function as its unique minimizer.Source: I An Explicit Finite-Batch… · pp. 55–56
  • Each rollout batch is reused for exactly K ≥2 joint updates, with raw GAE recomputed from the current critic and Monte Carlo targets retained.Minibatch trajectory indices are sampled with replacement, and actor and critic directions use the same pre-update pair.Source: I An Explicit Finite-Batch… · p. 56
  • Population coverage holds uniformly over actor iterates, with minimum time-averaged state probability at least 1/8, although a finite batch may omit states.The critic stays in [0, 1]^3 for every realized batch and minibatch sequence.Source: I An Explicit Finite-Batch… · p. 57
  • At initialization, the learned critic changes the mean actor direction, while the actor changes the critic’s policy-dependent minimizer.The example uses clipped updates but does not require clipping to activate at every admissible stepsize.Source: I An Explicit Finite-Batch… · p. 59
  • For fixed K ≥2, the example gives both F and Ec = O(T^-2/5) under a synchronous schedule.The constants are uniform in T; the result does not establish delayed or randomly stopped variants.Source: I An Explicit Finite-Batch… · p. 59
  • The numerical certificate gives Ḡ < 0.002094 < 1/432 ≈ 0.002315, but requires 5·10^11 fresh trajectories and is not a training result.The authors state that this sample requirement is not practical and the certificate does not establish a tight quantitative prediction.Source: I An Explicit Finite-Batch… · p. 60

J A Growing-Horizon Example with Polynomial Resources

This section presents a growing-horizon PPO-Clip example with polynomial resource bounds that avoids complete-trajectory support counting, and specifies the scope of its asynchronous analysis. It distinguishes parameter-server stale-compute from decoupled stale-data training and states the single-gradient read-delay model and behavior-snapshot-age condition for the population-KL premise.

J A Growing-Horizon Example with Polynomial Resources

  • An O(H)-state chain uses a shared policy and a jointly learned tabular critic that realizes the unnormalized true values, while its objective remains nonconstant uniformly in H.The example also exhibits nonzero actor–critic feedback: at initialization the population actor bias is nonzero, and the selected critic target changes with the actor.Source: J A Growing-Horizon Example with… · pp. 60, 61, 64
  • For fixed K and m, the growing-horizon chain has eO(H^17 ε^-7/2) collected trajectories, and structured concentration avoids complete-trajectory support counting.The bound concerns expected stationarity and critic tracking, not global policy optimality; both errors are at most ε at the stated horizon-dependent update count.Source: J A Growing-Horizon Example with… · pp. 62–64

K.1 Asynchronous PPO-Clip: Parameter-Server vs. Decoupled Rollout– Training

  • Asynchronous PPO-Clip relaxes the synchronous iteration barrier, allowing updates to use older policy data or critic and actor parameters.The section distinguishes parameter-server and decoupled rollout–training paradigms, which induce different forms of staleness.Source: §K.1 · p. 65

K.1.1 Model I: Parameter-Server Asynchronous PPO-Clip

  • In parameter-server PPO-Clip, workers evaluate gradients using stale actor–critic snapshots and retained behavior-policy batches, then send updates to the current server parameters.Delays can cause policy-gradient mismatch, critic-target drift, and clipping or KL distortion; the analysis bounds these effects through parameter drift over the delay window.Source: §K.1.1 · pp. 65–66

K.1.2 Model II: Decoupled Rollout–Training Asynchronous PPO-Clip

  • In decoupled rollout–training PPO-Clip, rollout workers feed a frequently refreshed shallow buffer while trainers update current parameters using trajectories generated by older policy snapshots.Snapshot-per-epoch reuse and streaming rollouts are two variants; both can be modeled with delay and induced-drift bounds.Source: §K.1.2 · p. 66

K.1.3 Comparison and modeling implications

  • Parameter-server updates use stale computation, whereas decoupled updates use current parameters on stale data; the theorem covers only the specified single-gradient parameter-server model.Sufficient conditions jointly constrain actor and critic stepsizes using coupling and delay bounds, with a smaller permitted critic stepsize as its delay bound increases; applying the result to decoupled systems requires verifying the same premises.Source: §K.1.3 · pp. 66–67
  • The asynchronous theorem allows delayed single-gradient jobs only when their application schedule does not inspect fresh minibatch noise and excludes accumulated multi-step local fitting.Each gradient pair uses a critic snapshot taken before computation. A behavior-snapshot age of at most D_b actor updates suffices for the population-KL premise when G_πηG_gD_b ≤ κ, with G_g = R_maxG_πA_max and the score bound along connecting segments.Source: §K.1.3 · p. 67

K.2 Asynchronous convergence guarantee

This section extends closed-loop PPO-Clip guarantees to a bounded-staleness parameter-server model, giving delay-dependent stability conditions and bounds that recover the synchronous form at zero delay. It also reports diagnostics on joint training, population GAE bias, and adaptive batch discrepancies, while noting that the controlled two-step experiments do not test asynchronous updates or the broader rate and horizon claims.

K.2 Asynchronous convergence guarantee

  • Theorem K.1 analyzes one actor and critic gradient pair per server job with bounded delays, fixed batch assignments, and nonanticipative sampling; stability requires both a delay-dependent critic stepsize and ρasync < 1.The predictable critic bias contributes an explicit 49Ec/m^2 floor; the guarantee does not cover accumulated local worker updates or data-dependent arrival selection.Source: §K.2 · pp. 68–69, §K.4 · p. 72
  • At zero delay, the asynchronous bound takes the synchronous form, with Aasync = a, Fasync = F, and qasync = 0.Theorem 3.1 gives tighter critic constants in this zero-delay case.Source: §K.2 · p. 69, §K.4 · p. 74

K.3.1 A key auxiliary bound: server drift under bounded staleness

  • The parameter-server drift lemma bounds average distances to stale snapshots in a bounded window, including history-dependent snapshot indices, without requiring their independence.The same averaged bound applies between any two indices in the window.Source: §K.3.1 · p. 69

K.3.2 Asynchronous control of clip activation in the parameter-server model

  • The asynchronous clipping lemma uses a KL condition between the behavior and evaluated policies to control clipping-region activation and bound population gradient distortion.It applies when stored batches may predate the evaluated actor snapshot; empirical batch-reuse error is controlled separately.Source: §K.3.2 · p. 70

K.3.3 Open-loop critic tracking with delayed gradients

  • Delayed critic tracking permits predictable bias under bounded delays, assuming critic regularity on the visited region and mixed current/stale parameter pairs.The target-shift argument does not require independent actor and critic noise.Source: §K.3.3 · pp. 70–71

L.2 Joint training diagnostics: Figure 1a

  • In the two-step diagnostic, the mean actor statistic was 2.8413 × 10−4 and the mean critic statistic was 1.9790 × 10−3 at T = 8192.The complete-bound upper bounds, 7.5065 for the actor and 35.1910 for the critic, were vacuous; the measured reductions do not establish bound tightness.Source: §L.2 · pp. 75–76, §L.1 · p. 75

L.3 Population cancellation and residual errors: Figure 1b

  • At λ = 1, the empirical RMS error was 0.008439 versus 0.008704 for the variance-based estimate, while drifted-policy clipping left absolute bias 0.08035.Population raw-GAE bias cancels at λ = 1 despite critic inaccuracy, but sampling error remains; the drifted-policy setting has active clipping.Source: §L.3 · p. 76

L.4 Adaptive batch discrepancies: Figure 1c

  • The adaptive batch-discrepancy diagnostic used 256 independent batches for each B from 16 to 1024, with a single epoch from common initialization and K = 8 in the main figure.At each pre-update iterate, it computed the empirical clipped actor and Monte Carlo critic directions.Source: §L.4 · p. 76
  • The adaptive diagnostic takes maxima over visited iterates, with clipping inactive; larger K raises the maximum by construction and does not show that reuse harms learning.The H=2 study illustrates adaptive empirical error but does not distinguish complete-path counting from the structured complexity bound at growing horizons.Source: §L.4 · pp. 76–77
  • At B=16, actor and critic discrepancy means were 1.7915 × 10^-4 and 0.030325; at B=1024, they were 3.1169 × 10^-6 and 0.00045487.Uniform pathwise envelopes over the actor and critic classes yield expectation bounds of 4/B for the actor and 1/B for the critic.Source: §L.4 · p. 77

L.5 Statistical analysis and reproducibility

  • The two-step experiments used pointwise 95% bootstrap intervals and do not test asynchronous updates, a necessary threshold at ρ=1, the T^-2/5 rate, or polynomial horizon-resource exponents.They included all 32 training seeds and specified replicates without exclusions or replacements; the controlled measurements do not test neural or LLM performance.Source: §L.5 · p. 77

L.6 Critic–clipping interaction during training

The section tests whether critic error changes clipping decisions and distortion, and examines the reverse coupling in which actor updates move the critic’s population target. At K = 64, learned critics show positive mean interaction, while performance comparisons do not establish a universal ranking of critic speeds.

L.6 Critic–clipping interaction during training

  • Each of 12 configurations ran 16 replicates of 2,048 updates; K = 16 and K = 64 collected 32,768 and 8,192 fresh trajectories, while the oracle reused data and raw GAE.The oracle did not refresh the data or substitute true advantages.Source: §L.6 · pp. 78–79
  • Clipping activity averages the indicator of active clipping over behavior trajectories and time positions, while the population-direction comparison holds actor, behavior law, ratios, and raw-GAE convention fixed.The study also measures sampled clipping activity over the actual minibatch.Source: §L.6 · p. 78
  • At K = 64 with clipping, mean interaction norms were 0.00204463 for the slow critic and 0.000421091 for the fast critic; their paired difference was 0.00162354 [0.00159658, 0.00165281].Mask disagreement was 1.59182% for the slow critic and 0.136202% for the fast critic.Source: §L.6 · p. 79
  • At K = 64, the slow critic exceeds the fast critic in final return by 0.0180456 [0.0148847, 0.0212563], but clipping lowers return in all three modes.The observations do not establish a universal performance ranking of critic speeds.Source: §L.6 · p. 79
  • At K = 64, mean target movement was 2.01810×10−5, 1.93706×10−5, and 1.94415×10−5 across the three clipped modes; learned critics’ signed effects averaged 0.0303849 and 0.00532343.Negative effects occurred at 0.787354% and 12.4725% of checkpoints for the learned critics.Source: §L.6 · p. 79
  • These experiments support interacting mechanisms but do not test convergence rate, the coupling condition, bound tightness, horizon scaling, or generalization to neural PPO.Cross-K comparisons match updates but not fresh-data budgets.Source: §L.6 · pp. 79–80

M Discussion

  • M Discussion considers the roles and limitations of the assumptions and the interpretation of the coupling index ρ.Source: M Discussion · p. 80

M.1 Discussion of assumptions

The discussion identifies the assumptions that let the finite-time actor–critic bounds close, especially critic tracking and the coupling condition. It also outlines a loss-gap alternative whose additional calibration and drift requirements are not supplied by PL alone.

M.1 Discussion of assumptions

  • The guarantees are finite-sample specializations requiring coverage, critic regularity, and a statistical bridge; KL control alone does not certify arbitrary neural PPO implementations.The bridge requires finite trajectory support or structured tabular conditions, while positive action coverage and the conditional sampling protocol are separate premises.Source: §M.1 · pp. 80, 83
  • Smoothness is assumed for the true objective J, while event localization handles the nonsmooth clipped surrogate; bounded raw advantages and population KL control also support the stated bounds.The population KL premise controls within-epoch policy drift and clipping activity; empirical KL checks or penalties alone do not establish it.Source: §M.1 · pp. 80–81
  • The critic’s local convexity and quadratic growth provide the tracking contraction needed to control its moving-target error and its contribution to actor bias.Without this contraction, critic lag may accumulate under constant stepsizes and propagate through advantage estimation; the parameter-distance proof does not establish tracking without its premises.Source: §M.1 · p. 81

M.2 Stability lens: the coupling index ρ

  • ρ < 1 lets the scalar closure yield a finite amplification bound; when ρ ≥ 1, the theorem establishes neither convergence nor divergence.As ρ approaches 1 from below, the bound’s amplification factor grows, which signals loss of uniform finite-time control rather than an algorithmic stability transition.Source: §M.2 · p. 83

N Extensions and Alternative Critic Error Measures

  • The discussion considers critic-loss tracking under additional calibration and drift assumptions, and an extension that includes critic approximation error.PL and smoothness alone control a frozen critic objective, not the moving-objective drift needed to close the coupled process.Source: N Extensions and Alternative Critic… · p. 84, §N.1 · p. 85

N.1 Why the strongest assumptions concern the critic landscape

  • The main parameter-distance route relies on stronger local critic geometry, which supplies a moving-target contraction for tracking the selected minimizer.These conditions impose structure on a potentially nonconvex learned value-function objective.Source: §N.1 · pp. 84–85

N.2 Tracking the critic loss gap instead of parameter distance

  • Loss-gap tracking avoids directly tracking a selected minimizer, but requires calibration from loss gap to value error and a separate moving-objective drift estimate.PL alone does not provide the drift estimate; the alternative route remains conditional on these additional premises.Source: §N.2 · pp. 85–86

N.3 Including critic approximation error

The section extends the analysis to an imperfect critic class while retaining the learned-critic dynamics. The resulting bounds include irreducible value-approximation error, which also affects critic tracking through the actor update magnitude.

N.3 Including critic approximation error

  • The main theorem assumes a realizable critic, treating critic quality as an exogenous oracle property rather than quantifying critic optimization and actor drift.The closed-loop analysis instead quantifies dependence on critic optimization, actor drift, and the actor–critic timescale ratio.Source: §N.3 · p. 87
  • With a realizable critic, the extension removes irreducible value-approximation error, leaving tracking lag and finite-batch, clipping, and trajectory-mismatch floors.The extension retains the other geometry, coverage, sampling, terminal-boundary, and boundedness premises.Source: §N.3 · p. 87
  • The extension retains learned-critic dynamics while adding irreducible value-approximation error to the closed-loop bounds.The approximation floor also enters critic tracking through the actor update magnitude.Source: §N.3 · p. 87
Loading 2610.10273v1…