cs.LGSep 30, 2026

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

Authors: Nima H. Siboni

Organizations: Juna.ai, Kastanienallee 32, 10435 Berlin, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Common policy improvement methods, including TRPO, PPO, and GRPO, estimate policy improvement under the behavioral policy's state-visitation distribution rather than the improved policy's own. The substitution makes the objective estimable from the behavioral policy's rollouts but adds a bias growing with policy divergence, hence the trust region or clip, and hence no reuse of a batch far off-policy. We show that under history-injective dynamics, where each state is reached by exactly one history, the dropped state-visitation ratio equals the product of per-step policy ratios along the sampled prefix, on every trajectory and not only in expectation. The ratio is therefore restored exactly, from log-probabilities PPO already computes. Autoregressive generation and canonical-order constructive optimization are both history-injective. The exact correction pays importance-sampling variance that grows with the horizon, so we generalize it to a one-parameter family with PPO (α=0α{=}0) and the full correction (α=1α{=}1) as endpoints: a single bias--variance knob. A gradient-level analysis of the unclipped surrogate identifies two channels the correction acts through and three conditions under which it carries signal; an enumerable testbed confirms the conditions' predictions. On hard credit-assignment scheduling tasks, a short corrected warmup with aggressive early sample reuse learns faster than PPO and than the same reuse uncorrected; the marginal gain grows with task difficulty (+0.02+0.02 to +0.09+0.09 learning-curve AUC), and the early win over PPO tracks the prefix bias that reuse incurs. A correction held throughout, or applied where clipping already contains the reuse bias, is null to harmful.

Figures & tables

Variantgt(Lts)g_{t}(L^{s}_{t})
PPO11 (biased; no added variance)
Fullexp⁡(Lts)\exp(L^{s}_{t}) (unbiased; full IS variance)
Temperedexp⁡(αLts)\exp(\alpha L^{s}_{t}) , α∈[0,1]\alpha\in[0,1]
Truncatedexp⁡ ⁣(∑i=max⁡(0,t−k)t−1ℓi)\exp\!\bigl(\sum_{i=\max(0,t-k)}^{t-1}\ell_{i}\bigr)
Clippedexp⁡(clip⁡(αLts,−c,c))\exp(\operatorname{clip}(\alpha L^{s}_{t},-c,c))
Table 1: Correction factors gtg_{t} evaluated in this paper. Tempered interpolates PPO ( α=0\alpha{=}0 ) and full ( α=1\alpha{=}1 ); truncated corrects only the last kk steps; clipped caps the correction in log space.
MethodMSE[L^]\mathrm{MSE}[\hat{L}]cos⁡\cosESS
PPO ( α=0\alpha=0 )0.296±0.0020.296\pm 0.0020.200.201.001.00
Tempered α=0.05\alpha=0.050.255±0.0020.255\pm 0.0020.260.261.001.00
Tempered α=0.10\alpha=0.100.229±0.0020.229\pm 0.0020.330.330.980.98
Tempered α=0.25\alpha=0.250.203±0.003\mathbf{0.203\pm 0.003}0.530.530.900.90
Tempered α=0.50\alpha=0.500.296±0.0050.296\pm 0.0050.810.810.700.70
Full ( α=1\alpha=1 )2.90±0.322.90\pm 0.321.001.000.260.26
Table 2: Estimator diagnostics at DˉKL≈0.33\bar{D}_{\mathrm{KL}}\approx 0.33 on the late-only reward, 2525 seeds ( ±\pm SEM): MSE of the single-trajectory estimate L^\hat{L} ( 7 ), gradient cosine cos⁡(∇η,∇E[L^])\cos(\nabla\eta,\nabla\mathbb{E}[\hat{L}]) , and normalized ESS. ∣Bias∣|\mathrm{Bias}| is ≤3×10−4\leq 3\times 10^{-4} for every method and 2×10−172\times 10^{-17} for the full correction (Appendix F.2 ). Bold marks the lowest MSE.
 TabularTransformer
MethodN-SGDN-SGDAdam
Tempered α=0.05\alpha=0.05555510/10\mathbf{10/10}6/106/10
Tempered α=0.10\alpha=0.10505010/10\mathbf{10/10}8/10\mathbf{8/10}
Tempered α=0.25\alpha=0.2560608/108/107/107/10
Clipped (0.10,1.0)(0.10,1.0)50509/109/108/9\mathbf{8/9}
Clipped (0.25,1.0)(0.25,1.0)50505/105/107/97/9
Table 3: Learning on the two-branch reward ( K=4K=4 , 256256 -trajectory rollouts, 200200 iterations). Tabular (lr 0.30.3 , 33 seeds): iteration at which mean return reaches η=1\eta=1 . Transformer (N-SGD lr 1.01.0 ; Adam lr 3×10−33\times 10^{-3} ): fraction of seeds with final η>0.5\eta>0.5 . Bold marks the best entry per column.
 Two-branchLate-only
MethodΔ\Delta (pp)seedsΔ\Delta (pp)seeds
Tempered α=0.05\alpha=0.05+4.5+4.59/109/10+1.2+1.25/105/10
Tempered α=0.10\alpha=0.10+6.7\mathbf{+6.7}16/16\mathbf{16/16}+1.9+1.98/168/16
Tempered α=0.25\alpha=0.25+5.8+5.810/1010/10+1.1+1.14/104/10
Clipped (0.10, 1.0)(0.10,\,1.0)+6.5+6.510/1010/10+2.6+2.66/106/10
Full ( α=1\alpha=1 )+0.1+0.16/106/10−4.4-4.40/100/10
Table 4: Pretrained-LM study (Qwen2.5-0.5B, Adam): paired difference against PPO in mean Monte Carlo return over iterations 22 – 88 , and the paired seeds favoring the correction, on the two-branch reward and the late-only falsifier. Confidence intervals and the trap cell are in Appendix H .
Figure 1: The correction as a short warmup. (a) Bottleneck flow shop at the standard reuse count, c=1.0c=1.0 : greedy validation on-time rate, mean and 95%95\% band over 4848 seeds; shaded: the 5050 warmup iterations. The warmup run leads PPO through the early climb and ends at the same level; the correction held for the whole run falls behind. (b) Seven-machine flow shop at its hardest deadline, aggressive early reuse ( K=30K=30 for the first 5050 iterations) with and without the correction, 2424 seeds: PPO and reuse alone peak and then degrade, while the corrected warm start holds its level. (c) The same K=30K=30 warmup on every task and deadline: paired per-seed AUC gain over PPO, without (reuse only) and with the correction; markers are means with 95%95\% CIs, and the numbers count the seeds that beat PPO. Values, sign tests, and the correction’s marginal over reuse only are in Tables 18 (a) and 17 (b, c), Appendix I.5 .
Appendix figures & tables32 assets

Supplementary material from the paper’s appendix.

Appendix

ConditionPlain statementQuantity to checkIf it fails
C1: late-decided rewardreward still action-dependent after prefix mismatch has accumulated∣Lts∣|L^{s}_{t}| at advantage-carrying positions ( Var(Lts)≈tσ2\mathrm{Var}(L^{s}_{t})\approx t\sigma^{2} )channels are inert; only variance remains
C2: prefix-dependent rewardupweighted and downweighted prefixes differ in valuebt=Covπold(Rts,rtA^t)≠0b_{t}=\mathrm{Cov}_{\pi_{\mathrm{old}}}(R^{s}_{t},r_{t}\hat{A}_{t})\neq 0contributions cancel across prefixes
C3: sampling trapan early mistake starves batches of rewarded trajectoriesfrequency of zero-reward batchesspeed gain at most; same endpoint
Appendix
Table 5: The three conditions under which the correction matters, the measurable quantity behind each, and what is lost when the condition fails. C1 and C2 concern the per-update gradient; C3 concerns the repeated sampling-and-update process.
Method∣Bias[L^]∣|\mathrm{Bias}[\hat{L}]|MSE[L^]\mathrm{MSE}[\hat{L}] ( ±\pm SEM)cos⁡(∇η,∇E[L^])\cos(\nabla\eta,\nabla\mathbb{E}[\hat{L}])Normalized ESS
PPO ( α=0\alpha=0 )1.8×10−41.8\times 10^{-4}2.96×10−1±1.9×10−32.96\times 10^{-1}\pm 1.9\times 10^{-3}0.200.201.001.00
Tempered α=0.05\alpha=0.052.3×10−42.3\times 10^{-4}2.55×10−1±1.9×10−32.55\times 10^{-1}\pm 1.9\times 10^{-3}0.260.261.001.00
Tempered α=0.10\alpha=0.102.6×10−42.6\times 10^{-4}2.29×10−1±2.2×10−32.29\times 10^{-1}\pm 2.2\times 10^{-3}0.330.330.980.98
Tempered α=0.25\alpha=0.253.0×10−43.0\times 10^{-4}2.03×10−1±2.7×10−3\mathbf{2.03\times 10^{-1}\pm 2.7\times 10^{-3}}0.530.530.900.90
Tempered α=0.50\alpha=0.502.6×10−42.6\times 10^{-4}2.96×10−1±5.2×10−32.96\times 10^{-1}\pm 5.2\times 10^{-3}0.810.810.700.70
Full ( α=1\alpha=1 )2.1×10−172.1\times 10^{-17}2.90×100±3.2×10−12.90\times 10^{0}\pm 3.2\times 10^{-1}1.001.000.260.26
Appendix
Table 6: Estimator diagnostics at DˉKL≈0.33\bar{D}_{\mathrm{KL}}\approx 0.33 on the late-only reward, 2525 seeds; single-trajectory estimate L^\hat{L} ( 7 ). Bold marks the lowest MSE.
Figure 2: Mean squared error MSE[L^]\mathrm{MSE}[\hat{L}] ( 17 ) of the single-trajectory estimate versus the tempering coefficient α\alpha , on the late-only reward at the largest tested drift ( DˉKL≈0.33\bar{D}_{\mathrm{KL}}\approx 0.33 , 2525 seeds, error bars ±1\pm 1 SEM, log scale). The dashed line is PPO ( α=0\alpha=0 ). The trade-off has an interior minimum at tempered α=0.25\alpha=0.25 ; the values are in Table 2 .
MethodBreak-through iter.η\eta at iter. 5050Iter. to η=1.000\eta=1.000
Tempered α=0.10\alpha=0.103030 – 45450.961\mathbf{0.961}5050
Clipped (0.25, 1.0)(0.25,\,1.0)3030 – 45450.9600.9605050
Tempered α=0.05\alpha=0.0550500.9000.9005555
Tempered α=0.25\alpha=0.255050 – 55550.7810.7816060
Tempered α=0.50\alpha=0.505050 – 60600.4680.4687070
PPO5050 – 60600.3410.3417070
Appendix
Table 7: Tabular policy under N-SGD ( lr=0.3\mathtt{lr}=0.3 , K=4K=4 , 33 seeds): iteration of break-through past the η≈0.25\eta\approx 0.25 plateau, exact return at iteration 5050 , and iteration at which η\eta reaches 11 .
Figure 3: Exact return versus iteration on the two-branch reward: tabular policy, N-SGD ( lr=0.3\mathtt{lr}=0.3 , K=4K=4 , mean over 33 seeds). The clipped variants are omitted: their curves overlap exactly with those of their tempered counterparts in this run, as the log-space cap cc never binds.
Figure 4: Mean exact return over 1010 seeds versus iteration for the 793793 k-parameter transformer under N-SGD ( lr=1.0\mathtt{lr}=1.0 , K=4K=4 ). Outcomes are bimodal ( η≈0\eta\approx 0 or 11 ), so the mean is the success-rate curve; the success rates are in Table 3 .
MethodSuccess rate ( n=10n=10 )Final η\eta (mean ±\pm SEM)
Tempered α=0.05\alpha=0.0510/10\mathbf{10/10}1.000±0.000\mathbf{1.000\pm 0.000}
Tempered α=0.10\alpha=0.1010/10\mathbf{10/10}1.000±0.000\mathbf{1.000\pm 0.000}
Clipped (0.10, 1.0)(0.10,\,1.0)9/109/100.900±0.1000.900\pm 0.100
Clipped (0.25, 2.0)(0.25,\,2.0)8/98/90.889±0.1110.889\pm 0.111
Tempered α=0.25\alpha=0.258/108/100.800±0.1330.800\pm 0.133
PPO7/107/100.700±0.1530.700\pm 0.153
Appendix
Table 8: Transformer under N-SGD at lr=1.0\mathtt{lr}=1.0 ( K=4K=4 , 1010 seeds): success rate and final η\eta per variant.
Figure 5: Adam ablation of Figure 4 ( lr=3×10−3\mathtt{lr}=3\times 10^{-3} , K=4K=4 , 1010 seeds). The success-rate advantage survives at reduced amplitude (Table 9 ).
MethodSuccess rateFinal η\eta (mean ±\pm SEM)
Clipped (0.10, 1.0)(0.10,\,1.0)8/9\mathbf{8/9}0.889±0.111\mathbf{0.889\pm 0.111}
Tempered α=0.10\alpha=0.108/108/100.800±0.1330.800\pm 0.133
Clipped (0.25, 1.0)(0.25,\,1.0)7/97/90.778±0.1470.778\pm 0.147
PPO7/107/100.700±0.1530.700\pm 0.153
Tempered α=0.25\alpha=0.257/107/100.700±0.1530.700\pm 0.153
Full7/107/100.700±0.1530.700\pm 0.153
Appendix
Table 9: Transformer under Adam at lr=3×10−3\mathtt{lr}=3\times 10^{-3} ( K=4K=4 ): success rate and final η\eta per variant.
MethodSuccess rateFinal η\eta (mean ±\pm SEM)
Tempered α=0.10\alpha=0.105/10\mathbf{5/10}0.500±0.167\mathbf{0.500\pm 0.167}
PPO3/103/100.300±0.1530.300\pm 0.153
Tempered α=0.05\alpha=0.052/102/100.200±0.1330.200\pm 0.133
Tempered α=0.25\alpha=0.252/102/100.200±0.1330.200\pm 0.133
Clipped (0.25, 1.0)(0.25,\,1.0)2/92/90.222±0.1470.222\pm 0.147
Clipped (0.25, 2.0)(0.25,\,2.0)2/92/90.222±0.1470.222\pm 0.147
Appendix
Table 10: Transformer under Adam at lr=10−2\mathtt{lr}=10^{-2} ( K=4K=4 ): success rate and final η\eta per variant.
Methoditer 2iter 3iter 4iter 5iter 10iter 20
PPO0.5340.5340.7560.7560.8840.8840.9570.9570.9980.9980.9990.999
Tempered α=0.10\alpha=0.100.706\mathbf{0.706}0.910\mathbf{0.910}0.978\mathbf{0.978}0.994\mathbf{0.994}0.9990.9990.9990.999
Δ\Delta (T −- P) pp+17.1+17.1+15.4+15.4+9.4+9.4+3.7+3.7+0.1+0.1+0.05+0.05
Appendix
Table 11: Cell 1 (NEUTRAL N=8N=8 , TWO_BRANCH) per-iteration MC η\eta , 1616 paired seeds. 16/1616/16 seeds positive at iteration 33 , 15/1615/16 at 55 ; the effect reaches the noise floor by iteration 77 as both arms hit ceiling.
Methodnn (paired seeds)Δ\Delta vs. PPO (pp)seeds positive95%95\% CI (pp)
Tempered α=0.05\alpha=0.051010+4.5+4.59/109/10±2.6\pm 2.6
Tempered α=0.10\alpha=0.101616+6.7\mathbf{+6.7}16/16\mathbf{16/16}±2.5\pm 2.5
Tempered α=0.25\alpha=0.251010+5.8+5.810/1010/10±3.4\pm 3.4
Clipped (0.10, 1.0)(0.10,\,1.0)1010+6.5+6.510/1010/10±3.4\pm 3.4
Full ( α=1\alpha=1 )1010+0.1+0.16/106/10±1.9\pm 1.9
Appendix
Table 12: Cell 1 full grid: paired difference vs. PPO on mean MC η\eta over iterations 22 – 88 (the pre-registered rate endpoint); normal-approximation 95%95\% CI on the paired mean.
iter123457101520
mean0.7780.6490.4540.3330.2290.0960.0140.0010.000
max0.9960.9960.9880.9570.9730.6680.1800.0080.004
min0.3120.1410.0350.0120.0000.0000.0000.0000.000
Appendix
Table 13: Cell 3 per-iteration fatal-marginal decline (mean/max/min over 1616 PPO seeds). No seed rises; all reach ≤10−2\leq 10^{-2} by iteration 1010 .
Methoditer 2iter 3iter 4iter 5iter 10iter 20
PPO0.6630.6630.8760.8760.9550.9550.9850.9850.9990.9990.9990.999
Tempered α=0.10\alpha=0.100.7150.7150.9210.9210.9840.9840.9940.9940.9980.9980.9990.999
Δ\Delta (T −- P) pp+5.1+5.1+4.6+4.6+2.9+2.9+0.9+0.9−0.05-0.05−0.02-0.02
Appendix
Table 14: Cell 4 (NEUTRAL N=8N=8 , LATE_ONLY) per-iteration MC η\eta , same protocol and 1616 paired seeds as Table 11 . Per-seed signs at iterations 22 – 55 : 8/168/16 , 9/169/16 , 8/168/16 , 5/165/16 positive — at or below chance, against Cell 1’s 16/1616/16 at iterations 22 – 33 .
Settingσ2T\sigma^{2}TEndpointΔ\Delta (corr. −- PPO)Seed wins
HGNN dispatcher, FJSP 10×510\times 5 , T=50T=50 ; correction held for the whole run
Published regime ( K=3K=3 ), two deadlines3×10−53\times 10^{-5}final on-time−6.0-6.0 , −8.6-8.6 pp4/604/60
Drift dial, hard deadline (reward floor)1.31.3final on-time−5.2-5.2 pp1/51/5
 1515 +4.4+4.4 pp3/53/5
 3434 +9.0+9.0 pp5/55/5
Drift dial, fair deadline (saturated)1.71.7final on-time+1.8+1.8 pp3/53/5
Appendix
Table 15: Held-correction results at and beyond realistic operating points. Δ\Delta is the paired, per-seed difference (corrected minus PPO) on the stated endpoint; seed wins count paired seeds favoring the correction. Drift σ2T\sigma^{2}T is measured on the rollout policy after one full KK -epoch update, before training, and was not recorded for the transformer update-strength dial. Details, the sizing rule for α\alpha , and the registered endpoints are in Appendices I.1 and I.4 .
Figure 6: Reward saturation at the fair deadline (early training, iterations 00 – 250250 ). Validation on-time rate at the recalibrated deadline for the three drift settings ( 55 paired seeds thin, mean bold; dashed line: the untrained sampling policy’s mean success rate, 0.750.75 ). There is no extended learning phase: both methods reach their operating level within tens of iterations — near or below the untrained baseline — and under the drift settings decay from an early peak at matched rates. The binary indicator is blind to the remaining, still-large gap to optimal makespans ( ≈0.35\approx 0.35 mean), so the fair-deadline comparison resolves seed noise around a saturated reward rather than a difference in learning.
Figure 7: The drift-dial on canonical-order FJSP, in two reward regimes. Paired final on-time difference (corrected minus PPO; 55 paired seeds, mean ±\pm s.e.) against the drift measured at each training regime before launching, σ2T\sigma^{2}T (log scale). At the hard deadline (green), where training operates at the on-time floor, the gap is monotone in measured drift and crosses zero, with every paired seed won at the top on both registered endpoints. At the fair deadline (purple), where all runs train mid-range, the same dial yields a null: with plentiful signal PPO absorbs the staleness on its own. The published training regime lies off the left edge, where the correction loses everywhere: with nothing stale to correct, only its variance cost remains. Values in Table 15 .
Figure 8: Free-choice positive control. Greedy two-branch success vs. iteration under the LM-toy structure, the real correction code, N-SGD, and the FATAL dead-branch regime; 1616 seeds thin, mean bold; plain PPO ( α=0\alpha=0 , blue) and the prefix correction ( α=0.5\alpha=0.5 , orange). Primed toward a dead first branch, PPO frequently stays trapped at the reward floor while the correction routes credit back to the first action and escapes. Statistics in Table 16 , first row.
env (learner/optimizer fixed)sizePPO AUCcorr. Δ\Delta AUCsign test
free (chosen terminal)T=8T{=}80.160.16+0.19+0.1910/010/0 , p=0.001p{=}0.001
emergent (whole-traj. terminal)T=8T{=}80.130.13+0.11+0.118/18/1 , p=0.02p{=}0.02
emergent, longer horizonT=12T{=}120.070.07+0.21\mathbf{+0.21}15/015/0 , p<10−4p{<}10^{-4}
coupled (busy =2=2 )T=8T{=}80.280.28+0.10+0.1010/310/3 , p=0.05p{=}0.05
coupled, strong (busy =3=3 )T=8T{=}80.460.46−0.03-0.038/118/11 , p=0.82p{=}0.82
Appendix
Table 16: Env-only ablation, all else fixed. The correction’s win survives an emergent terminal and coupling, and grows with a longer horizon (deeper credit-routing chain). It vanishes only under strong coupling — where PPO’s own score jumps to 0.460.46 because forced exploration dissolves the dead-branch trap: the task became easy, not the correction broken. The advantage tracks the difficulty of the escape/credit-routing problem, not the environment’s “scheduling-ness”.
Figure 9: Env-only ablation learning curves (learner, optimizer, regime, and hyperparameters all fixed; 1616 seeds thin, mean bold; greedy two-branch success). The prefix correction (orange) stays above PPO (blue) under an emergent terminal (panel 1), an emergent terminal over a longer horizon (panel 2), and coupling (panel 3); only strong coupling (panel 4) erases the gap, where both methods rise together. Statistics in Table 16 .
Figure 10: The reward boundary (learner/optimizer fixed at the winning configuration). (A) Two orders with a tight deadline — the closest scheduling analogue of the two-branch reward. The correction (orange) beats PPO (blue) directionally and consistently (paired Δ\Delta AUC +0.004+0.004 , 5/05/0 non-tied seeds, p=0.03p=0.03 , never harmful): the structure and sign of the win transfer. (B) Adding a second binding condition (both orders on tight deadlines) to deepen the trap: the feasible fraction jumps from 00 to 0.680.68 as slack increases, never passing through the two-branch depth ( 0.1250.125 , dashed). Two binary decisions quantize feasibility; reaching 0.1250.125 needs a four-option second decision (four-plus orders), which distributes the decisive action. The magnitude cannot transfer without hand-carving the two-branch structure.
Figure 11: A drifting transformer does not rescue the correction on a hard scheduling task. Three-machine bottleneck flow shop, transformer pointer policy, N-SGD, GRPO, under the scarce tight-deadline reward at three tightnesses (on-time floor 0.14/0.35/0.560.14/0.35/0.56 ). Greedy on-time rate vs. iteration; 1616 paired seeds thin, mean bold; PPO blue, corrected orange. At every setting PPO climbs from the floor and the corrected curve sits just below it; values in Table 15 .
Figure 12: The correction as a warmup beats PPO; held the whole run it loses. Bottleneck transformer, 4848 seeds per deadline. (A) Greedy on-time rate vs. iteration at c=1.0c=1.0 : the warmup ( α\alpha on for 5050 iterations then off, orange) climbs above PPO (blue) early and stays ≥\geq it, while holding a fixed α\alpha the whole run (red) sags below PPO late. Dotted line marks the off-switch. (B) Δ\Delta AUC vs. warmup length WW for both deadlines, with hold plotted at W=200W=200 (the full run); bars are 22 SE and the dashed line is the PPO baseline. Short warmups sit above the baseline and holding the correction drops below it; the pooled statistics are in Table 18 .
Figure 13: Disjunctive JSSP: the largest correction win, in the longest-range credit-assignment task. Classical JSSP ( 88 jobs, 55 machines, own routes, one shared bottleneck, T=40T=40 , sparse binary deadline reward). (A) At c=1.10c=1.10 , aggressive reuse with the correction (orange) leads plain PPO (blue) and reuse without the correction (red) throughout. (B) Correction marginal Δ\Delta AUC over reuse only vs. deadline ( ±2\pm 2 SE; early measured bias annotated): sharp at the feasible c=1.10c=1.10 and vanishing on either side — collapse at c=1.05c=1.05 , too-loose null at c=1.15c=1.15 . Values are in Table 17 .
Figure 14: The early win tracks the bias dose; the late win does not. Per configuration–seed point ( n=66n=66 ) correction win over plain PPO vs. the measured prefix bias ∑t∣bt∣\sum_{t}|b_{t}| that aggressive reuse incurs without correction, colored by configuration. (Left) First-half win rises with the dose. (Right) Second-half win is uncorrelated with it — consistent with the mechanism being early prefix-bias cancellation that decouples once the warmup correction switches off. Pooled and difficulty-partialled rr are in the panel titles; per-configuration rr in Table 19 .
  PPOCorrected vs. PPOReuse only vs. PPOCorrection’s marginal: corrected −- reuse only
Task / deadlinennfinalΔ\Delta AUCseedsppΔ\Delta AUCseedsppΔ\Delta AUCseedspp
Single-bottleneck flow shop, J=12J=12 (easy); K=30K=30 for the first W=50W=50 iterations, then standard KK
c=1.02c=1.0216160.980.98+0.087\boldsymbol{+0.087}14/16\boldsymbol{14/16}0.002\boldsymbol{0.002}+0.064\boldsymbol{+0.064}14/16\boldsymbol{14/16}0.002\boldsymbol{0.002}+0.023+0.02310/1610/160.2270.227
Seven-machine flow shop, J=20J=20 , three bottlenecks (hard); same K=30K=30 warmup
c=1.06c=1.0624240.990.99+0.009\boldsymbol{+0.009}19/23\boldsymbol{19/23}0.001\boldsymbol{0.001}−0.009-0.00912/2312/230.5000.500+0.018\boldsymbol{+0.018}15/21\boldsymbol{15/21}0.039\boldsymbol{0.039}
c=1.05c=1.0548480.890.89+0.034\boldsymbol{+0.034}41/48\boldsymbol{41/48}<10−4\boldsymbol{<10^{-4}}−0.005-0.00527/4827/480.2350.235+0.039\boldsymbol{+0.039}38/48\boldsymbol{38/48}<10−4\boldsymbol{<10^{-4}}
Appendix
Table 17: The aggressive-reuse warmup recipe: K=30K=30 for the first 5050 iterations, then plain PPO at the standard KK , with the correction ( corrected ) or without it ( reuse only ). Δ\Delta AUC is the paired, per-seed difference in the area under the greedy validation on-time curve; seeds counts the seeds favoring the first arm over the non-tied paired seeds, and pp is the one-sided exact sign test; bold marks a win, a positive difference with p<0.05p<0.05 . The two arms do the same optimizer work, so the correction’s marginal is its contribution beyond the reuse itself. PPO final is plain PPO’s final on-time rate, which sets the headroom.
  PPOCorrected vs. PPO
Warmup lengthnnfinalΔ\Delta AUCseedspp
W=25W=2596960.970.97+0.026\boldsymbol{+0.026}59/95\boldsymbol{59/95}0.012\boldsymbol{0.012}
W=50W=5096960.970.97+0.028\boldsymbol{+0.028}58/94\boldsymbol{58/94}0.015\boldsymbol{0.015}
W=75W=7596960.970.97+0.014+0.01452/9652/960.2380.238
held, whole run96960.970.97−0.023-0.02342/9642/960.9080.908
Appendix
Table 18: Warmup length at the standard reuse count: bottleneck flow shop, J=12J=12 , transformer policy, the correction on for the first WW iterations and then plain PPO (“held”: on for the whole run); deadlines c∈{1.0,1.02}c\in\{1.0,1.02\} pooled, 4848 seeds each. Columns and bolding as in Table 17 . There is no extra reuse here, so corrected vs. PPO already isolates the correction.
  PPOLead over PPOMarginal rr (dose, win)
Configurationnnfinalfirst halfsecond halfΔ\Delta AUCDoseearlylate
Multi-bottleneck flow shop, horizon sweep at fixed c=1.03c=1.03
J=20J=2012120.670.67+0.115+0.115+0.149+0.149+0.178+0.1783.753.75+0.51+0.51−0.19-0.19
J=30J=3012120.570.57+0.071+0.071+0.050+0.050+0.045+0.0455.535.53−0.39-0.39+0.45+0.45
J=40J=4012120.870.87+0.083+0.083−0.016-0.016+0.021+0.0215.415.41+0.67+0.67−0.12-0.12
J=50J=5012120.980.98+0.092+0.092+0.003+0.003+0.049+0.0495.275.27+0.74+0.74−0.48-0.48
Appendix
Table 19: Horizon and dose detail behind Section 6.2 . Lead over PPO is the warmup-corrected run’s mean greedy on-time minus plain PPO’s over the first and second halves of training; marginal Δ\Delta AUC is over the reuse-only K=30K=30 arm; dose is the prefix bias ∑t∣bt∣\sum_{t}|b_{t}| on that arm, averaged over the warmup window; rr is the within-configuration Pearson correlation across seeds between the dose and the half-wise lead. In the calibrated block the deadline is chosen per JJ by a PPO-only calibration (see text); J=50J=50 has no deadline in the calibration band and is excluded.
Figure 15: KK -tolerance frontier on the easy task: reuse opens no window for the correction. Reuse KK held the whole run, swept 44 – 128128 , at clip=0.2\text{clip}=0.2 (solid) and 0.40.4 (dashed). (A) Final greedy on-time vs. KK : PPO (blue) is robust — it peaks at K=64K=64 and barely drops by K=128K=128 at clip=0.2\text{clip}=0.2 , failing only at K=128K=128 / clip=0.4\text{clip}=0.4 — and the corrected update (orange) sits at or below PPO at nearly every KK . (B) Drift σ2T\sigma^{2}T (median, log scale) climbs steeply with KK and explodes to ∼ ⁣106\sim\!10^{6} at K=128K=128 / clip=0.4\text{clip}=0.4 : the variance regime that sinks the correction. Clip already contains the reuse bias on an easy task, so the correction only adds variance — its value needs hard credit assignment (Figure 1 c), not merely high KK .
Figure 16: Faster early, same endpoint — the sample-efficiency win across horizon and a second task family. Learning curves (mean ±2\pm 2 SE) for plain PPO (blue), aggressive reuse without the correction (red), and aggressive reuse with the correction (orange); dotted line marks the end of the correction warmup. In the long-horizon flow shop ( J=40,50J=40,50 ) the correction leads through the warmup window and PPO converges to the same plateau afterward (sample efficiency, not a better policy). The durable exception is disjunctive JSSP at c=1.10c=1.10 , where the correction stays ahead throughout.
Figure 17: Horizon drives the bias dose; the win is headroom-gated. Ceiling-controlled horizon sweep: for each JJ the deadline cc is calibrated (PPO-only, blind to the corrected arm) so PPO’s final on-time sits in a mid-band ( J=50J=50 excluded — no in-band cell). (A) Correction early-half win over PPO vs. JJ at the held ceiling: positive and roughly flat. (B) Measured prefix bias vs. JJ : rises monotonically even though the ceiling is fixed — the dose is horizon-driven, while the realised win is capped by headroom (here held constant). Values are in Table 19 .
Figure 18: The early-win–dose coupling peaks where the correction wins. Per-config within-seed Pearson rr between the measured bias dose and the correction’s win over plain PPO, early (orange, solid) vs. late (blue, dashed), plotted along each task’s difficulty axis. (A) Flow shop: the early correlation is highest at long horizon JJ . (B) JSSP: it peaks at the feasible deadline c=1.10c=1.10 — the winning cell — and falls off on either side. Per-config n=6n=6 – 1212 , so the late correlations scatter widely around zero; the axis-wise pattern of the early correlation, not any single point, is the message. Values are in Table 19 .

Explore similar work

CardsList

  1. Reusing Past Samples in Proximal Policy Optimization: When and How Does It Help?

    Oct 1, 2026Alessandro Montenegro, Riccardo Venturelli, Marco Mussi +2Proximal Policy OptimizationOff-Policy Learning

    Politecnico di Milano, Milan, Italy · Università degli Studi di Milano, Milan, Italy

  2. Beyond Importance Sampling: Rejection-Gated Policy Optimization

    Apr 16, 2026Ziwu Sun, Zhen Gao, Jiyong Zhang +1Frictive Policy Optimization

  3. OPTS-TTPO: Enhancing Finite-Sample Policy-Gradient Learning with Tree Search

    Sep 30, 2026Junyu Lu, Shichao Weng, Zhiqiang Wang +10Frictive Policy OptimizationPolicy Gradient

    Dobot Robotics · Independent Researcher · Zhejiang University +2