Free Everywhere, Exact on Trees: PPO's Dropped Correction Buys Sample Efficiency Under Aggressive Reuse

1 Introduction

• TRPO, PPO, and GRPO substitute the behavioral policy's state-visitation distribution for the improved policy's, making the objective estimable from rollouts but introducing divergence-growing error.That error motivates trust regions or clipping and limits far-off-policy batch reuse.Source: §1 · p. 1
• Under history-injective dynamics, the dropped state-visitation ratio equals the product of per-step policy ratios along each sampled trajectory, using log-probabilities PPO already computes.The exact correction has importance-sampling variance that grows with horizon, motivating a family between PPO's biased low-variance update and the full correction.Source: §1 · p. 2
• The correction changes the unclipped policy gradient through two channels, with three increasingly strong conditions marking where it may have systematic leverage.These conditions concern late-decided rewards, prefix dependence, and a training loop that can trap the policy; the effect also depends on per-update drift.Source: §1 · p. 2
• On hard credit-assignment scheduling tasks, a short corrected warmup with aggressive early sample reuse learns faster than PPO and the same reuse uncorrected.The gain grows with task difficulty; correction held throughout, or used where clipping already contains reuse bias, is null to harmful.Source: §1 · p. 2
• An enumerable testbed verifies the conditions' predictions, while a pretrained 0.5B model retains the correction's speed effect but not its trap effect.The testbed also verifies the correction to floating-point precision.Source: §1 · p. 2

2 Setting: tree-structured dynamics

• History-injectivity requires the current state to identify its unique generating history; it makes the reachable state graph a tree with no merging paths.The property concerns the state representation, not determinism: stochastic outcomes are compatible when the state records them.Source: §2 · pp. 2–3
• Autoregressive generation is history-injective because each state is the prompt and generated-token prefix, including when tool outputs are recorded in context.This covers discrete-token language, code, symbolic-mathematics, protein, and molecular generation.Source: §2 · p. 3
• Constructive optimization is history-injective under a canonical decision order, which fixes the next slot while leaving the policy to choose each decision's content.The scheduling experiments use this convention.Source: §2 · p. 3

3.1 Correcting the state-visitation distribution

• The correction reweights both state and action draws from the improved policy onto old-policy rollouts; PPO drops the state-visitation ratio because it is not generally computable.Under history-injectivity, the ratio is the product of per-step policy ratios along the sampled trajectory, with transition-kernel factors canceling.Source: §3.1 · pp. 3–4
• Under history-injectivity, the sampled prefix weight equals the state-visitation ratio pointwise; where histories merge, it is only an unbiased estimate and incurs conditional variance.The exact correction is unbiased but high-variance, with trajectory importance-sampling variance growing exponentially in the horizon.Source: §3.1 · p. 4

3.2 A family of prefix-corrected surrogates

• The family trades systematic error against accumulated-weight variance: only the exact correction yields the true improvement with exact advantages, while PPO is the g_t=1 variant.The evaluated variants apply correction factors to the prefix log-ratio.Source: §3.2 · p. 5
• The prefix correction adds an exclusive cumulative sum and O(T) elementwise operations per sample, without another forward or backward pass.Its computation is a factor V below the output layer's O(TV) work.Source: §3.2 · p. 5

• The gradient difference has two channels: reweighting scales the current-position gradient by prefix probability change, while credit routing sends advantage back to earlier actions.Source: §4 · p. 7
• C1 requires reward to remain dependent on actions ahead where drift has accumulated; terminal payment alone does not make a reward late-decided.Source: §4 · pp. 7–8
• C2 requires prefix-dependent reward so states upweighted and downweighted by drift differ in gradient content; the omitted-bias covariance is its measurable witness.Source: §4 · p. 8
• C3 requires the sampling-and-update loop to amplify gradient differences; a self-reinforcing trap can make rewarded trajectories too rare for a finite batch to restore the policy.Trap susceptibility also depends on batch size, baseline, regularization, optimizer, and reuse epochs.Source: §4 · p. 8
• The checklist predicts little leverage without C1, unchanged training without C2, faster learning to the same endpoint without C3, and changed run success when all three hold.Source: §4 · p. 8
• Recovering bias is not free: prefix-ratio variance grows with correction strength and horizon, while clipping can gate both gradient-difference channels to zero.Source: §4 · p. 8

5.1 Testbed and reward ladder

• The exactly enumerable V = 4 autoregressive testbed verifies the correction identity and compares methods differing only in correction; the two-branch reward activates all three conditions.Source: §5.1 · pp. 9–10
• The sparse trajectory-match control rewards one sequence with uniform-policy probability 4^-6, making its training outcomes noisy.Source: §5.1 · pp. 9–10

5.2 Estimator diagnostics on fixed policy pairs

• The full correction is unbiased but has variance an order of magnitude above PPO’s; PPO’s update direction falls to cosine 0.20 despite negligible bias.Source: §5.2 · pp. 10–11
• At the largest tested drift, tempered α = 0.25 improves gradient cosine to 0.53 from PPO’s 0.20 while also lowering MSE.Source: §5.2 · p. 11, Figure 1 · p. 11

5.3 Training on the two-branch reward

• Tempered α = 0.1 solves the tabular two-branch task by iteration 50 versus PPO’s 70, a 1.4× difference in time to solve.Source: Table 4 · p. 12, §5.3 · p. 12
• Under Adam, clipped variants and tempered α = 0.1 lead PPO, while the full correction has no successful seed at lr = 10^-2.Source: §5.3 · p. 12

5.4 Transfer to a pretrained language model

• +6.7 pp in mean Monte Carlo return over iterations 2–8 for tempered α = 0.10 versus PPO; all 16 paired seeds favor the correction.Source: §5.4 · p. 12

5.3 Training on the two-branch reward

• At N-SGD lr = 1.0, tempered α ∈ {0.05, 0.1} succeeds on 10/10 transformer seeds versus PPO’s 7/10; failed runs commit to the wrong first branch.Source: §5.3 · p. 12, Figure 2 · p. 13

6.1 Setting, and the null at realistic operating points

• At realistic FJSP hyperparameters, drift was σ2T ≈3 × 10−5 and the held correction lost to PPO in every cell, winning 4 of 60 paired comparisons.With little stale state distribution to repair, the correction's credit-routing channel incurs its horizon-dependent variance cost without a compensating gain.Source: §6.1 · p. 14

6.2 The win: a corrected warmup under aggressive early reuse

• A short corrected warmup followed by PPO beats PPO on AUC at W = 25 and W = 50, whereas holding the correction throughout loses.The second-half ∆AUC turns positive after the correction is switched off; too long a warmup dilutes the effect below significance.Source: §6.2 · p. 15, Table 7 · p. 16
• +0.087 marginal ∆AUC over the no-correction control at the hardest non-saturated deadline on a seven-machine flow shop; reuse alone was null to negative against PPO.The same correction-plus-reuse arm won at every deadline, with competing bottlenecks making credit assignment non-myopic.Source: §6.2 · p. 15
• On a single-bottleneck flow shop, the no-correction control captured most of the K = 30 warmup's gap over PPO, leaving the correction's marginal ∆AUC nonsignificant.At clip 0.2 the clip already contains reuse bias, and the correction's prefix ratios blow up at the largest whole-run reuse counts.Source: §6.2 · p. 16
• Across J = 20, 30, 40, and 50 jobs, the corrected warmup led PPO in the first half, but its second-half lead disappeared by J = 40.The measured prefix bias roughly doubled from J = 20 to J = 40 while the early lead stayed positive and roughly flat; PPO's headroom gates the gain.Source: §6.2 · p. 16
• +0.364 marginal ∆AUC on the feasible-deadline disjunctive job shop across all 6 seeds, about four times the largest flow-shop marginal.Most of the margin reflects the no-correction reuse control's collapse against PPO; the corrected arm's smaller lead over PPO was not significant with 6 seeds.Source: §6.2 · p. 16

6.3 What kind of win, and where it stops

• On the flow shop, the warmup reaches the same on-time ceiling as PPO, with final performance within 0.01; its ∆AUC reflects a faster early climb.The warmup uses several times the optimizer steps per rollout batch, so it buys scarce rollouts rather than FLOPs; the corrected and uncorrected high-K arms are compute-matched.Source: §6.3 · p. 17
• The correction's scheduling win is bounded by task and learner conditions: informative rewards or easy credit assignment remove the win, while realistic scheduling often offers continuous progress signal.On the flow shop, the correction's marginal gain grows as the deadline tightens, reaching +0.087 at the hardest non-saturated deadline.Source: §6.1 · p. 14, §6.2 · p. 15, §6.3 · p. 18

Related proposals

• MinPRO [6] and CTPO [19] independently apply the prefix ratio to language models at α = 1, but neither states when the correction is exact or extends it beyond autoregressive language models.Neither proposal parameterizes the design space or analyzes which correction strength wins under which conditions.Source: §7 · p. 18

Off-policy correction

• Classical off-policy methods estimate or truncate products of policy ratios to control variance, while this paper applies the sampled prefix ratio when it already equals the state-visitation ratio.Marginalized and conditional importance sampling estimate the averaged ratio; Retrace(λ) and V-trace truncate ratios in value targets.Source: §7 · p. 18

Policy optimization applications

• LLM methods including GRPO [15], GSPO [20], and ASPO [21] modify token- or sequence-level ratios, but none corrects the state-visitation term.Constructive optimization methods already use canonical construction order, the convention that makes the correction exact, but do not correct reused batches' state-visitation distribution.Source: §7 · p. 19

8 Discussion and limitations

• The correction can affect success rate only when the sampling loop preserves its gradient difference; otherwise its benefit is at most faster learning.The proposed operating-point hypothesis says batch size relative to squared horizon determines whether a correct-sign effect clears seed noise, but the horizon scaling of S is unresolved.Source: §8 · pp. 19–20
• The usable α must be matched to horizon: longer trajectories, merged histories, and aggressive optimizers push it toward zero.The proposed hypothesis predicts an advantage proportional to N and inversely proportional to T^2, and identifies a short-horizon, large-batch test.Source: §8 · p. 20
• The sampling-trap mechanism did not transfer to the pretrained model at the tested batch size, and a batch-size-≤64 test remains follow-up work.The discussion interprets real-model instability under this mechanism as slow convergence from biased gradient direction rather than lost seeds.Source: §8 · p. 21
• The full correction should not replace PPO because its variance is prohibitive at long horizons; stabilized algorithms interpolate between the endpoints.Which variant and α to use depends on optimizer and reuse schedule.Source: §8 · p. 21

A Time-indexed versus collapsed occupancies

• A fixed-time occupancy ratio is a product of policy ratios along the prefix, whereas a collapsed discounted occupancy is a time-mixture and does not simplify that way.Applying a per-token importance-sampling product to the collapsed ratio would be incorrect.Source: A Time-indexed versus collapsed… · p. 22

B Derivation of the prefix factorization

• History-injectivity makes each state reachable by one path, collapsing the sum over paths into one term and equating the state ratio with the realized prefix product.The transition kernels cancel because the unique path is shared by both policies.Source: B Derivation of the prefix factorization · p. 23
• The resulting ratio is computable from policy log-probabilities, regardless of transition-kernel values; determinism is not required.For stochastic dynamics, the state must retain each realized outcome for histories to remain distinct.Source: B Derivation of the prefix factorization · p. 23
• For any MDP, the sampled-path policy-ratio product is an unbiased estimator of the state-visitation ratio, but generally not its pointwise value.The result is standard per-decision importance sampling; the conditional identity is related to marginalized importance sampling [7] and its time-indexed form [27].Source: B Derivation of the prefix factorization · pp. 23–24
• When histories merge, the sampled path supplies one random term in the state-ratio average, creating conditional variance that injectivity removes.In free-order dispatching, a canonical construction order restores injectivity; otherwise the correction remains unbiased but pays a path-merging variance premium.Source: B Derivation of the prefix factorization · p. 24

C Family details: implementation and unevaluated members

• The correction is implemented by a cumulative sum of per-step log-ratios, excluding the current step, in PyTorch, JAX, or TensorFlow.Self-normalization and adaptive α selection are described as natural family members but were not evaluated.Source: C Family details: implementation and… · p. 24

D.1 Common protocol

• Learning experiments use a 4-layer, 128-dimensional, 4-head transformer or a tabular policy, typically with 256 trajectories per iteration and four update epochs.Compared variants include PPO, tempered α values, truncated weights, and clipped settings.Source: §D.1 · p. 24
• Sign tests are exact and one-sided for prespecified directional improvements, but two-sided for falsifier and null comparisons.The convention follows Section 6.Source: §D.1 · p. 25

D.2 Estimator diagnostics

• At the largest drift, tempered α = 0.25 and clipped (0.25, 1.0) reach MSE 5.0 × 10−2, a 7% margin over PPO’s 5.4 × 10−2.The full correction has bias bounded by 2 × 10−17 but variance 2.7× PPO; PPO’s early-gate bias grows with KL while its gradient cosine falls to 0.951.Source: §D.2 · p. 25
• For the late-only reward at KL ≈0.33, tempered α = 0.25 has MSE 2.03 × 10−1, 32% below PPO, and variance 2.02 × 10−1 versus PPO’s 2.96 × 10−1.The full correction’s variance reaches 2.9, while PPO’s gradient cosine falls to 0.20.Source: §D.2 · p. 25

D.3 Null controls: rewards without prefix dependence or a sampling trap

• The best interior estimator’s MSE margin over PPO is 11% on the early gate, 32% on late-only, and present but noisy on sparse trajectory match; only the two-branch reward activates all three conditions for training tests.The late-only control isolates estimator diagnostics from training-loop advantage.Source: §D.3 · p. 26

E.1 Tabular policy under N-SGD

• Interior tempered and clipped variants break through the tabular η ≈0.25 plateau before PPO, while full and truncated k = 4 come last.The compared metrics include breakthrough iteration, exact return at iteration 50, and the iteration at which η reaches 1.Source: §E.1 · p. 26, Table 8 · p. 26, Figure 7 · p. 27

E.2 Transformer under N-SGD

• At transformer N-SGD lr 1.0, interior tempered variants succeed on every seed while PPO succeeds on seven of ten.At lr 0.3 all methods succeed 10/10; at lr 3.0 the best, tempered α = 0.25, succeeds 2/10.Source: §E.2 · p. 26

E.3 Transformer under Adam

• At Adam lr 3 × 10−3, clipped (0.1, 1.0) and tempered α = 0.1 lead PPO by 19 pp; at 10−2, tempered α = 0.1 leads by 20 pp while the full correction has no successful seed.Under the more aggressive setting, Adam’s adaptivity applied to accumulated ratios produces unbounded updates on outlier tokens.Source: §E.3 · pp. 26–27

E.4 Optimizer-absorption ablation on the tabular policy

• Adam’s per-parameter RMS normalization reduces the interior-tempered advantage at iteration 50 to a relative lead of about 20%.The tabular comparison moves from η = 0.961 vs. 0.341 under N-SGD; the transformer comparison likewise shrinks from 30 pp to 19 pp.Source: §E.4 · p. 27

F Pretrained-LM study: structured-record consistency at 0.5B

• At η0 = 0.386, tempered α = 0.10 climbs faster over iterations 2–5; all 16 seeds favor it at iteration 3, with the effect fading by iteration 7.The rule-verifiable six-slot task has 4096 possible sequences, allowing exact enumeration of η and relevant conditional quantities.Source: F Pretrained-LM study:… · pp. 27, 29, Table 12 · p. 30
• Across the Cell 1 method grid, the rate advantage peaks near α = 0.10 and collapses at α = 1, where variance cancels the bias correction.Clipped (0.10, 1.0) is indistinguishable from tempered 0.10 at this KL scale.Source: F Pretrained-LM study:… · p. 29, Table 13 · p. 31
• In the low-reward Cell 3 trap test, fatal-branch marginals decline rather than rise, and all 16 PPO and 16 corrected runs succeed.The authors attribute this to rewarded trajectories arriving often enough for their advantage signal to dominate biased-gradient drift.Source: F Pretrained-LM study:… · pp. 29–30
• The late-only control yields +1.9 pp with 8/16 seeds positive, versus Cell 1’s +6.7 pp at 16/16; residual prefix dependence remains at LM scale.The Cell 3 non-headline arms were cancelled after PPO completed 16/16 runs at ceiling, so no success-rate comparison was possible for those arms.Source: F Pretrained-LM study:… · p. 30
• With no bias to correct in Cell 4, the full correction is strictly worse than PPO by −4.4 pp, with 0/10 seeds positive.Interior variants have small, sign-inconsistent residuals; all 72 Cell 4 runs succeed.Source: F Pretrained-LM study:… · p. 31

G.1 With no measured drift, the correction only costs variance

• At published settings, the correction loses in every tested FJSP cell: measured prefix log-ratio magnitude is only ≈0.005, leaving variance cost without stale-state bias to correct.The canonical-order experiment uses α = 0.03, lr 2 × 10−4, clip 0.2, and K = 3 reuse epochs.Source: §G.1 · p. 31
• Under scarce-signal hard deadlines, paired final on-time differences rise with measured drift and cross zero, with every paired seed won at the highest drift.The continuous makespan endpoint agrees at the highest drift (0.342 vs. 0.395), but on-time levels near the floor make this a sign-and-ordering result, not an effect-size estimate.Source: §G.1 · p. 32
• At recalibrated fair deadlines, all three paired differences are within seed noise; with plentiful reward signal, PPO recovers from stale data within a few updates.The binary reward is already successful on 75% of untrained instance–samples and both methods reach an early plateau, while mean makespan remains ≈0.35 above optimal.Source: §G.1 · p. 32
• A rich graded reward combining feasibility, makespan gap, and violations also produces negative AUC differences at all three tested drift settings.Final-level secondary endpoints agree with the null.Source: §G.1 · pp. 32–33
• A registered 16-seed confirmation found no acquisition-phase advantage for the held correction: seed wins were at chance and mean AUC was slightly below zero.An exploratory cut had suggested faster early learning, but the fresh-seed confirmation did not reproduce it.Source: §G.1 · p. 33

G.2 Positive controls: the mechanism and its implementation are sound

• The free-choice positive control rescues runs from a FATAL dead-branch trap, with several full rescues and no seed harmed.The control requires N-SGD and a dead-branch escape regime; the same code reproduces the win when learner and environment match the toy setting.Source: §G.2 · pp. 33–34, Figure 11 · p. 35

G.3 The reward boundary: why the win does not transfer to realistic objectives

• On the closest scheduling analogue to the two-branch reward, two orders with a tight deadline, correction improves paired AUC by +0.004 across 5/0 non-tied seeds.The sign transfers, but adding a second binding condition makes feasibility jump from 0 to 0.68 rather than passing through the two-branch depth of 0.125.Source: §G.3 · p. 35
• Scheduling cannot naturally combine a single decisive, unobservable early action with enough trap depth; the held correction’s boundary is a hand-constructed reward.Two orders offer the decisive action but shallow, quantized feasibility; four or more orders distribute the decisive structure across a contention-mediated permutation.Source: §G.3 · pp. 35–36

G.2 Positive controls: the mechanism and its implementation are sound

• With the learner, optimizer, and FATAL regime fixed, the free-choice advantage persists under emergent terminals and coupling, but vanishes under strong coupling when PPO’s score jumps to 0.46.The table attributes the null to the task becoming easy as forced exploration dissolves the dead-branch trap.Source: §G.2 · p. 34, Table 16 · p. 36, Figure 12 · p. 36

G.4 A drifting transformer learner does not rescue it

• Under scarce tight-deadline scheduling reward across three on-time floors, the held correction consistently loses by a small margin: PPO rises from each floor to ≈0.97 while the corrected curve tracks just below, noisier.At K = 12, transformer drift is σ2T = 1.38, more than four orders above the HGNN; the drift-dial crossover appears at σ2T ≈15–34, a band requiring near-divergent updates.Source: §G.4 · pp. 36–37

G.5 The win in detail: warmup, reuse, horizon, and dose

• On the easy task, PPO is robust across K = 4–128 at clip 0.2, failing only at K = 128/clip = 0.4; correction is at or below PPO at all but one K as drift rises five orders of magnitude.Drift reaches ∼10^6 at K = 128/clip = 0.4.Source: §G.5 · pp. 38, 40
• In long-horizon flow shop, the corrected run leads through warmup but PPO reaches the same plateau; disjunctive JSSP at c = 1.10 is the durable exception.Across flow-shop horizons J = 20–50, the warmup-corrected run leads plain PPO in the first half; the lead is gone by J = 40.Source: Figure 16 · p. 40
• In the ceiling-controlled horizon sweep, measured prefix bias rises with J while the early-half win stays roughly flat; headroom caps realized gains, and dose correlations do not establish causation.J = 50 is excluded because no in-band calibration cell exists.Source: §G.5 · p. 38, Figure 17 · p. 41