Paper deep dive
Free Everywhere, Exact on Trees: PPO's Dropped Correction Buys Sample Efficiency Under Aggressive Reuse
Nima H. Siboni
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 10/6/2026, 10:09:11 AM
Summary
This paper introduces an exact correction for policy improvement methods like PPO, TRPO, and GRPO by recovering the dropped state-visitation ratio under history-injective (tree-structured) dynamics. The authors propose a one-parameter family of surrogates that interpolates between PPO's biased, low-variance update and the full importance-sampling correction. They identify three conditions (late reward decision, prefix-dependent reward, and sampling traps) under which this correction improves sample efficiency, particularly during aggressive early sample reuse in hard credit-assignment tasks.
Entities (11)
Relation Signals (6)
Nima H. Siboni → affiliatedwith → Juna.ai
confidence 99% · Nima H. Siboni Affiliation: Juna.ai
History-Injective Dynamics → enables → Exact State-Visitation Ratio Recovery
confidence 98% · under history-injective dynamics... the dropped state-visitation ratio equals the product of per-step policy ratios... on every trajectory
MinPRO → applies → Exact Correction
confidence 95% · MinPRO [6] and CTPO [19] apply the same correction to language models at α=1
CTPO → applies → Exact Correction
confidence 95% · MinPRO [6] and CTPO [19] apply the same correction to language models at α=1
PPO → uses → Clipping
confidence 95% · hence the trust region or clip, and hence no reuse of a batch far off-policy.
Corrected Warmup → improves → Sample Efficiency
confidence 92% · a short corrected warmup with aggressive early sample reuse learns faster than PPO
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 ($\alpha{=}0$) and the full correction ($\alpha{=}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$ to $+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.
Tags
Links
- Source: https://arxiv.org/abs/2609.39634v2
- Canonical: https://arxiv.org/abs/2609.39634v2
Trouble viewing inline? Open PDF directly →
Full Text
130,594 characters extracted from source content.
Expand or collapse full text
Free Everywhere, Exact on Trees: PPO’s Dropped Correction Buys Sample Efficiency Under Aggressive Reuse Nima H. Siboni Affiliation: Juna.ai, Kastanienallee 32, 10435 Berlin, Germany Email: nima@juna.ai 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. 1 Introduction Policy-improvement methods build on the performance-difference identity for the expected discounted return η, written with the advantage AπoldA_ _old of the old policy and discount γ, η(π~)=η(πold)+τ∼π~[∑t=0∞γtAπold(st,at)],η( π)=η( _old)+E_τ π\! [ _t=0^∞γ^tA_ _old(s_t,a_t) ], (1) whose expectation is over trajectories of the improved policy π~ π. The improved policy cannot be rolled out before it is known, so Conservative Policy Iteration (CPI) [4] and its successors — TRPO [13], PPO [14], and GRPO [15] — evaluate the expectation under the old, behavioral policy πold _old instead. The substitution makes the objective estimable from the rollout batch, but it is exact only when the two policies induce the same state-visitation distribution. Its error grows with their divergence, which is why every method in this family confines each update to a trust region or a clip and cannot reuse a batch far off-policy. The dropped ratio has a standard unbiased estimate in any MDP, the product of policy ratios along the sampled prefix [10], computable from the log-probabilities PPO already has. Whenever the dynamics are history-injective, each state reached by exactly one history, that product does not merely estimate the ratio but equals it on every trajectory. The contribution is not a new importance-sampling identity but this pointwise collapse on tree-structured dynamics, together with an analysis of when paying the correction’s variance improves learning. The exact correction carries trajectory importance-sampling (IS) variance that grows with the horizon, so we generalize it to a one-parameter family with PPO’s biased, low-variance update at the other end. Whether removing the bias is worth its added variance depends on the reward and on the training loop. For the unclipped surrogate, the correction changes the policy gradient through exactly two channels, both silent at the rollout policy under a conditionally centered advantage. Away from it, three conditions of increasing strength mark out where the correction has systematic leverage: the reward is decided late, it depends on the prefix, and — for the endpoint of training rather than its speed — the sampling loop can trap the policy. We test these claims in two settings with different roles. An exactly enumerable sequence-model testbed is the instrument: it verifies the correction to floating-point precision and shows that the conditions predict where a partial correction wins and where it only adds variance. Constructive scheduling is the application: samples there are expensive, each rollout batch is reused, and the question is whether the correction lets early batches be reused harder. It does, on hard credit-assignment tasks: a short corrected warmup under aggressive early reuse learns faster than PPO and than the same reuse uncorrected, and the gain grows with task difficulty. Contributions. Two concurrent and independent proposals, MinPRO [6] and CTPO [19], apply the same correction to language models at α=1α=1; we share the base derivation with both, and each of the four claims below is absent from either (Section 7). 1. The state-visitation ratio that CPI, TRPO, PPO, and GRPO drop is exactly recoverable, pointwise on every trajectory, from log-probabilities PPO already computes, whenever the dynamics are history-injective (Sections 2–3.1). 2. A one-parameter family, PPO at α=0α=0 and the exact correction at α=1α=1, turns the correction’s bias–variance trade into a single knob (Section 3.2). 3. Three conditions — the reward is decided late, it depends on the prefix, and the training loop admits a sampling trap — predict when the correction helps; an enumerable testbed confirms them, and a pretrained 0.50.5B model shows that the speed effect, but not the trap effect, survives realistic training (Sections 4–5). 4. A short corrected warmup under aggressive early sample reuse learns faster than PPO on hard credit-assignment scheduling tasks; held throughout, or applied where the clip already contains the reuse bias, the correction is null to harmful (Section 6). 2 Setting: tree-structured dynamics Let ht=(s0,a0,s1,a1,…,st)h_t=(s_0,a_0,s_1,a_1,…,s_t) denote the history up to time t and ϕ(ht)=stφ(h_t)=s_t the state it reaches. History-injectivity: ϕφ is injective on histories of each length, so the current state identifies the history that produced it. In a general MDP many histories lead to the same state; a robot arm’s joint configuration, reachable by many motion paths, is the typical non-injective case. The property concerns the state representation, not chance: a process with stochastic transitions is history-injective as long as the state records each realized outcome. History-injectivity makes the reachable state graph a tree rooted at the initial state; we call such processes tree-structured. When the dynamics are also deterministic, st+1=(st,at)s_t+1=T(s_t,a_t), the unique history is identified by its action sequence alone, the form both settings below take; the derivation uses only injectivity. Autoregressive sequence models satisfy the condition natively: the state at step i is the prefix si=(x,y<i)s_i=(x,y_<i) and the action is the next token ai=yia_i=y_i, so distinct token sequences are distinct prefixes. This covers any autoregressive generator fine-tuned with reinforcement learning — language, code, or protein sequences [3] — and agentic generation in which the environment inserts tokens such as tool outputs, which are stochastic transitions that the context records. Constructive combinatorial optimization satisfies it under one further convention. A policy builds a solution one element at a time [1, 5]; a canonical construction order fixes which slot is decided next (in scheduling, the machine that next becomes free, under a fixed tie-break). Each partial solution can then be constructed in only one way, so the process is history-injective. The policy still chooses the content of every decision, only not its position. 3 The exact correction and a family of surrogates 3.1 Correcting the state-visitation distribution Written over states and actions, the performance-difference identity (1) is η(π~)=η(πold)+∑t=0∞γtst∼dπ~,t,at∼π~[Aπold(st,at)],η( π)=η( _old)+ _t=0^∞γ^t\,E_s_t d_ π,t,\,a_t π\! [A_ _old(s_t,a_t) ], (2) where dπ,t(s)=Pπ(St=s)d_π,t(s)=P_π(S_t=s) is the time-t state-visitation distribution of π and Aπold=Qπold−VπoldA_ _old=Q_ _old-V_ _old is the old policy’s advantage, the only advantage function in this paper. Importance sampling applied twice, to the state draw and to the action draw, reweights the expectation onto rollouts of πold _old, st∼dπold,ts_t d_ _old,t and at∼πolda_t _old: η(π~) η( π) =η(πold)+∑t=0∞γtπold[RtsrtAπold(st,at)], =η( _old)+ _t=0^∞γ^t\,E_ _old [R^s_t\,r_t\,A_ _old(s_t,a_t) ], (3) Rts R^s_t =dπ~,t(st)dπold,t(st),rt=π~(at∣st)πold(at∣st). = d_ π,t(s_t)d_ _old,t(s_t), r_t= π(a_t s_t) _old(a_t s_t). Equation (3) holds in any MDP. The action ratio rtr_t is the one PPO already uses. CPI, TRPO, and PPO drop the state-visitation ratio RtsR^s_t, replacing it by 11, because dπ~,td_ π,t is not computable in general. Under history-injectivity, RtsR^s_t equals the product of the per-step policy ratios along the sampled trajectory, and is therefore available from the same log-probabilities: Rts=dπ~,t(st)dπold,t(st)=∏i<tπ~(ai∣si)πold(ai∣si).R^s_t= d_ π,t(s_t)d_ _old,t(s_t)= _i<t π(a_i s_i) _old(a_i s_i). (4) We call RtsR^s_t the prefix ratio. In general dπ,t(st)d_π,t(s_t) sums over every history that reaches sts_t, each weighted by a product of policy probabilities and transition kernels. History-injectivity removes the sum: exactly one history ends at sts_t, the same for both policies, so numerator and denominator share every kernel factor; the kernels cancel, and what remains is (4) (Appendix B). Determinism plays no part: a ratio of identical kernels is one whether or not they are indicators. The tree structure buys noise reduction, not correctness or computability. In any MDP the sampled-path weight Wt=∏i<tπ~(ai∣si)/πold(ai∣si)W_t= _i<t π(a_i s_i)/ _old(a_i s_i) satisfies πold[Wt∣st]=RtsE_ _old[W_t s_t]=R^s_t, by standard per-decision importance sampling [10]; the conditional statement is the identity behind marginalized importance sampling [7, 27]. Tree structure adds the pointwise statement Wt=RtsW_t=R^s_t on every sampled path. Where histories merge, the conditional variance of WtW_t given sts_t is the Rao–Blackwell gap between the sampled weight and the ratio it estimates [12]; injectivity closes that gap. Substituting (4) into (3) merges the two ratios into one product, Rtsrt=∏i≤tπ~(ai∣si)πold(ai∣si),R^s_t\,r_t= _i≤ t π(a_i s_i) _old(a_i s_i), (5) of which PPO keeps only the factor i=ti=t. Unmodified, (5) is unbiased but high-variance. With the per-step log-ratio ℓi=logπ~(ai∣si)−logπold(ai∣si) _i= π(a_i s_i)- _old(a_i s_i) and σ2σ^2 its average per-step conditional variance, logRts=∑i<tℓi R^s_t= _i<t _i has Var(logRts)≈tσ2Var( R^s_t)≈ tσ^2 (the centered terms form a martingale-difference sequence; Appendix B), so the variance of RtsR^s_t grows exponentially in the horizon: the classical trajectory-IS problem [10, 17], arising here in the policy update rather than in value estimation. 3.2 A family of prefix-corrected surrogates Let Lts=∑i<tℓi=logRtsL^s_t= _i<t _i= R^s_t be the prefix log-ratio. Each surrogate replaces RtsR^s_t by a correction factor gt(Lts)g_t(L^s_t) (Table 1), giving the corrected ratio r~t=gt(Lts)exp(ℓt) r_t=g_t(L^s_t)\, ( _t). With π~=πθ π= _θ the trainable policy, r~t r_t enters the usual clip-min objective ℒPC(θ)=t[min(r~tA^t,clip(r~t,1±ϵ)A^t)],L^PC(θ)=E_t\! [ \! ( r_t A_t,\,clip( r_t,1±ε)\, A_t ) ], (6) with ϵε the PPO clip range and A^t A_t the advantage estimate at position t, computed once from the rollout batch and held fixed across update epochs; we drop the hat only for the exact advantage. Variant gt(Lts)g_t(L^s_t) PPO 11 (biased; no added variance) Full exp(Lts) (L^s_t) (unbiased; full IS variance) Tempered exp(αLts) (α L^s_t), α∈[0,1]α∈[0,1] Truncated exp(∑i=max(0,t−k)t−1ℓi) \! ( _i= (0,t-k)^t-1 _i ) Clipped exp(clip(αLts,−c,c)) (clip(α L^s_t,-c,c)) Table 1: Correction factors gtg_t evaluated in this paper. Tempered interpolates PPO (α=0α=0) and full (α=1α=1); truncated corrects only the last k steps; clipped caps the correction in log space. Each per-position expectation in (3) is the position-t marginal of a trajectory τ∼πoldτ _old, so the identity is a single expectation over rollouts, η(π~)−η(πold)=τ∼πold[∑tγtRtsrtAπold(st,at)]η( π)-η( _old)=E_τ _old[ _tγ^tR^s_tr_tA_ _old(s_t,a_t)], and each family member yields the single-trajectory estimate L^(τ)=∑tγtgt(Lts)rtA^t. L(τ)\;=\; _tγ^t\,g_t(L^s_t)\,r_t\, A_t. (7) With exact advantages, πold[L^]E_ _old[ L] equals the true improvement only at gt=exp(Lts)g_t= (L^s_t); every other member trades this systematic error against the variance of the accumulated weight. The added computation is the exclusive cumulative sum LtsL^s_t of the per-step log-ratios: one line of code, no extra forward or backward pass, and O(T)O(T) elementwise operations per sample, a factor of the vocabulary size below the output layer’s work (Algorithm 1 and implementation in Appendix C). Computationally, then, the correction is free in any MDP; that is the sense of “Free” in the title, and tree structure adds exactness to it, not computability. The cost that remains is its variance. MinPRO [6] and CTPO [19] both fix α=1α=1 and add a variance-control layer, a running minimum and a t t-scaled clip respectively; each is one point of Table 1 with a stabilizer, which the family turns into one setting of a knob. 4 When the correction matters This section asks where the correction enters the policy gradient, what reward structure makes it systematic rather than noise, and when a better per-update gradient changes what training reaches. Each question yields one checkable condition, C1 to C3, which delimit progressively stronger regimes of systematic leverage, not necessary conditions; Appendix D gives the full statements. The trade is not monotone in α: at finite drift an interior member can have lower variance than PPO and a better direction at once (Section 5.2). Let the score zi(θ)=∇θlogπθ(ai∣si)z_i(θ)= _θ _θ(a_i s_i) and St(θ)=∑i<tzi(θ)S_t(θ)= _i<tz_i(θ), the direction that makes the sampled prefix more probable. For the unclipped surrogate, let ℒtg=πold[gt(Lts)rtA^t]L^g_t=E_ _old[g_t(L^s_t)\,r_t\, A_t] be the position-t term of πold[L^]E_ _old[ L]. Subtracting PPO’s gradient leaves Δtg ^g_t :=∇θ(ℒtg−ℒtPPO) := _θ (L^g_t-L^PPO_t ) (8) =πold[rtA^t(gt(Lts)−1zt+gt′(Lts)St)]. =E_ _old\! [r_t A_t (\g_t(L^s_t)-1\\,z_t+g_t (L^s_t)\,S_t ) ]. The first part, the reweighting channel, is PPO’s own gradient rescaled by how much the update has changed the probability of the sampled prefix. The second, the credit-routing channel, has no counterpart in PPO: through StS_t it routes the position-t advantage backward to the earlier actions that produced the prefix. Conditioning on sts_t, which by injectivity fixes the prefix and so gt(Lts)g_t(L^s_t) and StS_t, replaces the action-dependent factors by hθ(st):=πold[rtA^tzt∣st]h_θ(s_t):=E_ _old[r_t A_tz_t s_t] and A¯πoldπθ(st):=πold[rtA^t∣st] A_ _old _θ(s_t):=E_ _old[r_t A_t s_t], the old policy’s advantage averaged under the updated policy’s action draw: Δgt=st∼dπold,t[ ^g_t=E_s_t d_ _old,t\! [ gt(Lts)−1hθ(st) \g_t(L^s_t)-1\\,h_θ(s_t) (9) +gt′(Lst)StA¯πoldπθ(st)]. +g_t (L^s_t)\,S_t\, A_ _old _θ(s_t) ]. At θ=θoldθ= _old both channels are silent under a conditionally centered advantage estimate, πold[A^t∣st]=0E_ _old[ A_t s_t]=0: the reweighting channel because gt(0)=1g_t(0)=1, the credit-routing channel because A¯πoldπold(st) A _old_ _old(s_t) vanishes. The exact advantage is centered; sampled returns with a batch-mean baseline are not. The correction therefore acts through policy drift across the reuse epochs of one update, and through imperfect centering, present from the first step. C1: the reward is decided late. Each term of (9) is a reward-blind drift factor, gt(Lts)−1g_t(L^s_t)-1 or gt′(Lts)Stg_t (L^s_t)S_t, which starts at zero and grows with position, times a content factor, hθh_θ or A¯πoldπθ A_ _old _θ, which carries the advantage. The advantage at position t measures only reward the actions from t onward can still influence, so a reward decided by the first action vanishes from Aπold(st,⋅)A_ _old(s_t,·) at exactly the late positions where drift is large, even if it is paid at the end. C1 requires the reward to remain contested at positions where drift has accumulated. C2: the reward depends on the prefix. To first order the reweighting term averages to gt′(0)Cov(Lts,hθ(st))g_t (0)\,Cov(L^s_t,h_θ(s_t)), nonzero only if hθh_θ differs between the prefixes the correction upweights and those it downweights. A reward that leaves every prefix equally good cancels across prefixes, and the credit-routing term reduces to a residual that is zero for the full correction and first-order in drift otherwise. C2 has a one-number witness, the omitted bias itself, bt=πold[(Rts−1)rtA^t]=Covπold(Rts,rtA^t),b_t=E_ _old[(R^s_t-1)\,r_t A_t]=Cov_ _old(R^s_t,\,r_t A_t), (10) measurable from any rollout batch; Section 6 measures it, summed over positions, as the bias dose. C3: the loop can trap the policy. A gradient that is better in expectation need not change where training ends: PPO may reach the same solution a few updates later. The clearest amplifier is a self-reinforcing sampling trap: a wrong early commitment makes rewarded trajectories so rare that a finite batch, scored against a batch-mean baseline, contains no restoring gradient. Whether a task admits a trap depends jointly on the reward, batch size, baseline, regularization, optimizer, and number of reuse epochs. Read as a nested checklist, the conditions predict: with C1 inactive, little leverage; C1 without C2, a better estimator but unchanged training; C1 and C2 without C3, faster learning to the same endpoint; C1–C3, a changed probability that a run succeeds. In every case the recovered bias must be weighed against the variance of RtsR^s_t, which grows with α and the horizon. The analysis is of the unclipped surrogate; wherever the min in (6) selects the flat clipped branch, the gradient is zero and neither channel enters. 5 Verifying the mechanism on an enumerable testbed 5.1 Testbed and reward ladder The testbed is an exactly enumerable autoregressive MDP with vocabulary size V=4V=4 and horizon T=6T=6 (diagnostics, control rewards) or T=8T=8 (learning). Two policy representations run on it: a small causal transformer (793793k parameters), trained from sampled rollouts, and a tabular softmax, which admits exact η, KL, and advantages, so the correction can be verified as an identity. The compared methods differ only in gt(Lts)g_t(L^s_t) and share the objective, advantage estimation, and optimizer (Appendix F). Four rewards form a ladder that switches the conditions on one at a time. Three are controls (Appendix F): a step-additive early gate (C1 partial, C2 weak), a late-only reward R=[yT−1=]R=1[y_T-1= B] (C1 without C2), and a sparse trajectory match (C2, C3, but too rare a target for measurable training). The principal learning task is the two-branch reward R(y0:T−1)=1if y0=,yT−1=,1if y0=,yT−1=,0otherwise,R(y_0:T-1)= cases1&if y_0= A,\ y_T-1= B,\\ 1&if y_0= C,\ y_T-1= D,\\ 0&otherwise, cases (11) which activates all three: the reward is contested until the terminal token (C1), the correct terminal action depends on the first-token branch (C2), and a wrong early commitment can make rewarded continuations disappear from a finite batch (C3), while the untrained success rate of 1/81/8 keeps outcomes measurable. 5.2 Estimator diagnostics on fixed policy pairs Before any training, we score the estimators on fixed policy pairs: πold _old against a logit perturbation πθ _θ, whose magnitude dials the drift D¯KL(πold,πθ) D_KL( _old, _θ) from 4×10−54× 10^-5 to 0.330.33. Every quantity is computed exactly: the bias, variance, and MSE of L L (7); the direction, the cosine between ∇θπold[L^] _θE_ _old[ L] and the exact ∇θη _θη; and the normalized effective sample size (ESS) [25] of the correction weights (definitions in Appendix F.2). Table 2 reports the late-only reward at the largest drift, where the contrasts are sharpest. Method MSE[L^]MSE[ L] cos ESS PPO (α=0α=0) 0.296±0.0020.296± 0.002 0.200.20 1.001.00 Tempered α=0.05α=0.05 0.255±0.0020.255± 0.002 0.260.26 1.001.00 Tempered α=0.10α=0.10 0.229±0.0020.229± 0.002 0.330.33 0.980.98 Tempered α=0.25α=0.25 0.203±0.0030.203± 0.003 0.530.53 0.900.90 Tempered α=0.50α=0.50 0.296±0.0050.296± 0.005 0.810.81 0.700.70 Full (α=1α=1) 2.90±0.322.90± 0.32 1.001.00 0.260.26 Clipped (0.25, 1.0)(0.25,\,1.0) 0.204±0.0030.204± 0.003 0.520.52 0.900.90 Table 2: Estimator diagnostics at D¯KL≈0.33 D_KL≈ 0.33 on the late-only reward, 2525 seeds (± SEM): MSE of the single-trajectory estimate L L (7), gradient cosine cos(∇η,∇[L^]) (∇η, [ L]), and normalized ESS. |Bias||Bias| is ≤3×10−4≤ 3× 10^-4 for every method and 2×10−172× 10^-17 for the full correction (Appendix F.2). Bold marks the lowest MSE. The full correction is exactly unbiased, at a steep variance price: its bias is at floating-point zero (2×10−172× 10^-17) at every tested drift, verifying (5) as an algebraic identity, but its variance is an order of magnitude above PPO’s and its normalized ESS falls to about a quarter. PPO’s error is directional: negligible bias and the lowest variance, yet its update has cosine 0.200.20 with the exact gradient, a failure invisible to bias- and variance-style diagnostics that does not average out with more data. The interior Pareto-dominates: tempered α=0.25α=0.25 improves on PPO in direction and in MSE at once, a 32%32\% reduction at the interior minimum of the trade-off (Figure 2 in Appendix F.2), because exp(0.25LT−1s) (0.25\,L^s_T-1) partially cancels the outlier contributions PPO’s last-step ratio makes at rarely visited prefixes. 5.3 Training on the two-branch reward The per-update estimator advantage compounds across iterations, and the methods order as the diagnostics predict (Table 3). On the tabular policy, normalized stochastic gradient ascent (N-SGD) fixes the update magnitude, isolating direction: tempered α=0.1α=0.1 solves the task by iteration 5050 and PPO by 7070, a 1.4×1.4× difference, while the full and long-truncated corrections trail. On the transformer the outcomes are bimodal, so the advantage appears as success rate: tempered α∈0.05,0.1α∈\0.05,0.1\ succeeds on every seed, PPO on 7/107/10. Each failed seed commits to a wrong first branch within the first few steps and never recovers — the sampling trap of C3 (Figure 4 in Appendix G.2). Adam attenuates the effect without erasing it and shifts the best variant toward clipping; at the aggressive =10−2 lr=10^-2 the full correction collapses to no successful seed (Appendix G.3). Tabular Transformer Method N-SGD N-SGD Adam Tempered α=0.05α=0.05 5555 /10/10 6/106/10 Tempered α=0.10α=0.10 5050 /10/10 /8/10 Tempered α=0.25α=0.25 6060 8/108/10 7/107/10 Clipped (0.10,1.0)(0.10,1.0) 5050 9/109/10 /8/9 Clipped (0.25,1.0)(0.25,1.0) 5050 5/105/10 7/97/9 PPO (α=0α=0) 7070 7/107/10 7/107/10 Full (α=1α=1) 8585 6/106/10 7/107/10 Truncated k=4k=4 100100 5/105/10 3/93/9 Best −- PPO 1.4×1.4× +30p+30\,p +19p+19\,p 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η=1. Transformer (N-SGD lr 1.01.0; Adam lr 3×10−33× 10^-3): fraction of seeds with final η>0.5η>0.5. Bold marks the best entry per column. 5.4 Transfer to a pretrained language model The speed effect transfers to a pretrained policy under Adam; the trap effect does not. We fine-tune Qwen2.5-0.5B [28] on a rule-verifiable six-slot structured-record task whose rewards mirror the ladder (Appendix H). On the prefix-dependent two-branch reward, tempered α=0.10α=0.10 leads PPO by +6.7+6.7 p in mean return over iterations 22–88, the pre-registered endpoint, with all 1616 paired seeds favoring the correction; the gain is interior in α and collapses at α=1α=1 (Table 4). On the matched late-only falsifier, which keeps the delayed reward but removes prefix dependence, the advantage contracts to +1.9+1.9 p with per-seed signs at chance and the full correction is harmful on every seed. A trap cell that primes the policy onto the wrong branch does not trap it: all 1616 PPO seeds succeed, because about 8.58.5 rewarded trajectories per 256256-rollout batch survive the priming. At realistic batch sizes the correction changes learning speed rather than rescuing lost runs. Two-branch Late-only Method Δ (p) seeds Δ (p) seeds Tempered α=0.05α=0.05 +4.5+4.5 9/109/10 +1.2+1.2 5/105/10 Tempered α=0.10α=0.10 +6.7+6.7 /16/16 +1.9+1.9 8/168/16 Tempered α=0.25α=0.25 +5.8+5.8 10/1010/10 +1.1+1.1 4/104/10 Clipped (0.10, 1.0)(0.10,\,1.0) +6.5+6.5 10/1010/10 +2.6+2.6 6/106/10 Full (α=1α=1) +0.1+0.1 6/106/10 −4.4-4.4 0/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. 6 Application: constructive scheduling under aggressive sample reuse 6.1 Setting, and the null at realistic operating points Scheduling is the least controlled setting in this paper and the one where samples are expensive. The expense is met by reusing each rollout batch for K update epochs, and reuse moves the policy away from the data it trains on, the staleness the correction exists to repair. The tasks are flexible job-shop (FJSP), permutation flow-shop, and disjunctive job-shop instances under the canonical construction order of Section 2, so the correction is exact. A heterogeneous graph network (HGNN) dispatcher [16] or a transformer pointer policy constructs the schedule over T=12T=12 to 5050 decisions; the reward is a binary on-time indicator [Cmax≤c⋅C∗]1[C_ ≤ c· C^*] for a deadline factor c on the optimal makespan C∗C^*, or a dense makespan objective (Appendix I). We compare the area under the learning curve (AUC) of the greedy validation on-time rate; Δ is the difference between two arms, paired by seed. Sign tests are exact binomial tests on the non-tied paired seeds, one-sided for pre-specified directional hypotheses and two-sided for falsifiers and nulls. Drift is measured after one full K-epoch update as σ2Tσ^2T. At realistic operating points a held correction is null to harmful, for two measurable reasons (Table 15 in Appendix I.1). Realistic training accumulates no staleness to repair: at published FJSP hyperparameters the drift is σ2T≈3×10−5σ^2T≈ 3× 10^-5 and the correction wins 44 of 6060 paired comparisons. And where the reward retains signal, PPO absorbs the staleness on its own: dialing the drift up five orders of magnitude helps only at a deadline where training sits at the reward floor, and a rich-reward benchmark built for the correction is null at the largest drift we measured. 6.2 The win: a corrected warmup under aggressive early reuse The correction pays when it is used briefly, while the policy is still moving, and then switched off. On a bottleneck flow shop with the transformer policy, applying the correction for the first W∈25,50W∈\25,50\ iterations and then running plain PPO beats PPO on AUC, while holding it for the whole run loses (Figure 1a; Table 18 in Appendix I.5). We raise the reuse count to K=30K=30 during the warmup because reuse-induced drift is one of the two routes through which the correction acts (Section 4). Raising K also changes the optimizer work per batch and how often clipping engages, so the comparison arm is the same high-K warmup without the correction (reuse only), and the correction’s marginal Δ , corrected minus reuse only, is what the correction contributes beyond the reuse itself; the two arms do the same optimizer work. Aggressive early reuse pays with the correction on hard credit-assignment tasks, and much less without it. On a seven-machine flow shop with 2020 jobs and three spread-out bottlenecks, reuse alone is null at the two looser deadlines and a small win only at the tightest, while the same reuse with the correction wins at every deadline, and the marginal Δ grows as the deadline tightens, to +0.087+0.087 (Figure 1c; Table 17). At the two hardest deadlines the corrected warm start also ends higher: PPO peaks and then degrades to a final on-time rate of 0.890.89 and 0.790.79, while the corrected run holds at 0.960.96 (Figure 1b). This endpoint comparison is post hoc, and reuse without the correction also ends above PPO, so at these seed counts the higher endpoint is not separated from the reuse itself. On the easy single-bottleneck flow shop the reuse-only arm captures most of the gain and the marginal is not significant: at clip 0.20.2 the clip alone contains the reuse bias, and sweeping a held K from 44 to 128128 never favors the correction (Figure 15 in Appendix I.5). The lever is credit-assignment difficulty, not K. The largest marginal gain is on the task with the longest-range credit assignment. On a disjunctive job shop (88 jobs, 55 machines, T=40T=40), at the feasible deadline the marginal Δ is +0.364+0.364 on all 66 seeds (Figure 1c; Table 17). Most of that margin is the reuse-only arm’s collapse, the corrected arm’s own lead over PPO is not significant, and with n=6n=6 the sign of the win is established, not its magnitude. The early win tracks the bias dose; the late win does not. The dose is ∑t|bt| _t|b_t| of (10) at the rollout policy, measured on the aggressive-reuse run without correction. Across n=66n=66 configuration–seed points with task difficulty partialled out, the first-half win over PPO rises with the dose (r=+0.32r=+0.32) while the second-half win is uncorrelated with it (r=−0.03r=-0.03; Figure 14 in Appendix I.5). Across horizons J∈20,…,50J∈\20,…,50\ the early lead persists while the measured prefix bias roughly doubles (Appendix I.5). 6.3 What kind of win, and where it stops Where PPO holds its ceiling, the warmup buys sample efficiency, not a better policy: after the off-switch the run converges to PPO’s level, final performance within 0.010.01, and the Δ is a faster early climb, about 3%3\% of AUC (Figure 1a). Where PPO itself degrades late — the hardest flow-shop deadlines and the job shop — the warm-started run keeps its lead through the second half of training (Figure 1b; Table 19). Sample efficiency is not compute efficiency: the high-K arms spend several times PPO’s optimizer steps per batch, buying rollouts, the scarce currency here, not FLOPs. The win needs drift large enough that PPO’s stale-state bias exceeds the added variance, and a reward sparse enough that PPO cannot relearn what stale data corrupted. The nulls are a property of the task and learner, not of the implementation: on an environment stripped to the testbed’s structure the same code rescues trapped runs on every non-tied seed (Appendices I.2–I.4). 7 Related Work Two concurrent proposals apply the prefix ratio to the policy update. Lei et al. [6] (MinPRO) and Zhang et al. [19] (CTPO) independently name the same bias; both fix the correction at α=1α=1, stabilize it with their own variance control, and evaluate on LLM mathematical-reasoning benchmarks. Neither states the structural condition under which the correction is exact, extends beyond autoregressive language models, or parameterizes the design space: the tempered family, k-truncation, and which point wins under which conditions are absent from both. The product-of-ratios structure and its bias–variance trade-off are classical in off-policy evaluation [10, 17], and the standard response is to refuse the product. Marginalized importance sampling [7, 27] estimates the state-visitation ratio instead, conditional importance sampling [12] frames this as Rao–Blackwellization, and Liu et al. [8] carry the estimated ratio into the off-policy policy gradient, which is (3) with RtsR^s_t learned rather than sampled. Retrace(λ) [9] truncates per-step ratios in value targets; V-trace [2] declines the accumulated product for the policy ratio so that “the variance does not explode.” Applying the sampled prefix ratio to the policy update, where no estimate is needed, and characterizing when its variance is worth paying, is the distinguishing point. In LLM reinforcement learning the token-level ratio is the default. GRPO [15] and DeepSeek-R1 [18] use it and inherit the bias we characterize; GSPO [20] uses a length-normalized sequence ratio and ASPO [21] an asymmetric one; DPO [11] bypasses the ratio. None corrects the state-visitation term. Neural constructive combinatorial optimization [1, 5], including job-shop dispatching [16], trains with PPO-family learners that fix a reuse count and a clip but do not correct the state-visitation distribution of the reused batches; the canonical order that makes the correction exact is a convention these methods already use for decoding. 8 Discussion and limitations Three nested questions decide before training whether to revisit PPO’s state-visitation approximation. Is the correction exact here? Yes under history-injective dynamics; where histories merge, as in free-order dispatching, it stays unbiased but pays a path-merging variance premium (Appendix B). Does it carry a systematic signal? Only if the reward is decided late and depends on the prefix (C1, C2), which the bias witness btb_t measures from any rollout batch. Does the loop preserve the difference? Only a sampling trap turns it into a success-rate effect; otherwise the correction yields at most a speed advantage (C3). In every case α must be matched to the horizon: long T, merged histories, and aggressive optimizers push the usable α toward zero. A heuristic operating-point argument (Appendix E) suggests the effect size scales with N/T2N/T^2, batch size over squared horizon, which would place the scheduling nulls three orders of magnitude below the testbed’s operating point; we state it as a falsifiable hypothesis, not a result. The limitations are these. The synthetic rewards are decided at known positions, which a realistic reward model is not; the pretrained study is one 0.50.5B model under one hyperparameter freeze, and the sampling trap did not transfer to it at the batch size we ran (whether it fires at batch ≤64≤ 64 is a registered follow-up). The scheduling win needs a warmup schedule and a hard, sparse-reward task, and its largest effect rests on 66 seeds. The full correction should not replace PPO: its variance is prohibitive at long horizons, and it loses to PPO under aggressive Adam (Table 10). The importance-sampling identity is not new [10]; what is new is its pointwise form under tree-structured dynamics and the analysis of when the variance it costs is worth paying. AI Use Statement In this work, we used generative AI tools (a large language model coding and writing assistant) for developing the code for the experiments, including the scripts that check the derivations by exact enumeration, and for plotting the results; for launching and monitoring the experiment runs on cloud machines; and for improving the text of the paper. We have not used generative AI tools for the research ideas, the theoretical derivations, or the interpretation of the results. We have reviewed all AI-assisted work: AI-generated code was checked against independent tests, the corrected estimator is verified to floating-point precision against exact enumeration on the tabular testbed, and the scheduling tables are regenerated by script from the stored result files rather than transcribed; AI-improved text was checked by the authors against the derivations and result files. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI. References [1] Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv:1611.09940, 2016. [2] Lasse Espeholt, Hubert Soyer, Remi Munos, et al. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In ICML, 2018. [3] Noelia Ferruz, Steffen Schmidt, and Birte Höcker. ProtGPT2 is a deep unsupervised language model for protein design. Nature Communications, 13:4348, 2022. [4] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, 2002. [5] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In ICLR, 2019. [6] Shiye Lei, Rongxi Cheng, and Dacheng Tao. A step back: Prefix importance ratio stabilizes policy optimization. arXiv:2601.22718, January 2026. [7] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. In NeurIPS, 2018. [8] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. In UAI, 2019. [9] Remi Munos, Tom Stepleton, Anna Harutyunyan, and Marc G. Bellemare. Safe and efficient off-policy reinforcement learning. In NeurIPS, 2016. [10] Doina Precup, Richard S. Sutton, and Satinder Singh. Eligibility traces for off-policy policy evaluation. In ICML, 2000. [11] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In NeurIPS, 2023. [12] Mark Rowland, Anna Harutyunyan, Hado van Hasselt, Diana Borsa, Tom Schaul, Rémi Munos, and Will Dabney. Conditional importance sampling for off-policy learning. In AISTATS, 2020. [13] John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region policy optimization. In ICML, 2015. [14] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv:1707.06347, 2017. [15] Zhihong Shao et al. DeepSeekMath: Pushing the limits of mathematical reasoning in open language models. arXiv:2402.03300, 2024. [16] Wen Song, Xinyang Chen, Qiqiang Li, and Zhiguang Cao. Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 19(2):1600–1610, 2023. [17] Philip S. Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-policy evaluation. In AAAI, 2015. [18] DeepSeek-AI. DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv:2501.12948, 2025. [19] Yuheng Zhang, Chenlu Ye, Shuowei Jin, Changlong Yu, Wei Xiong, Saurabh Sahu, and Nan Jiang. Rethinking importance sampling in LLM policy optimization: A cumulative token perspective (CTPO). arXiv:2605.07331, May 2026. [20] Chujie Zheng et al. Group Sequence Policy Optimization (GSPO). arXiv:2507.18071, 2025. [21] ASPO: Asymmetric Importance Sampling Policy Optimization. arXiv:2510.06062, 2025. [22] A. Rupam Mahmood, Hado van Hasselt, and Richard S. Sutton. Weighted importance sampling for off-policy learning with linear function approximation. In NeurIPS, 2014. [23] Tim Hesterberg. Weighted average importance sampling and defensive mixture distributions. Technometrics, 37(2):185–194, 1995. [24] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. In NeurIPS, 2015. [25] Augustine Kong. A note on importance sampling using standardized weights. Technical Report 348, Department of Statistics, University of Chicago, 1992. [26] Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In NeurIPS, 2018. [27] Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. In NeurIPS, 2019. [28] Qwen Team. Qwen2.5 technical report. arXiv:2412.15115, 2024. Appendix A Time-indexed versus collapsed occupancies The collapsed occupancy ratio ρπ~(s)/ρπold(s)=∑tγtdπ~,t(s)/∑tγtdπold,t(s) _ π(s)/ _ _old(s)= _tγ^td_ π,t(s)/ _tγ^td_ _old,t(s) is a ratio of mixtures over time and does not simplify to a product of policy ratios; correcting it with a per-token IS product would be wrong. The product form applies at a fixed time index: dπ~,t(st∣x)/dπold,t(st∣x)=∏i<tπ~(yi∣⋅)/πold(yi∣⋅)d_ π,t(s_t x)/d_ _old,t(s_t x)= _i<t π(y_i ·)/ _old(y_i ·). This is why the derivation starts from the time-expanded identity rather than the collapsed ρ-form. Appendix B Derivation of the prefix factorization Setup. Condition throughout on the initial state s0s_0. Under a policy π, a length-t path (s0,a0,…,st)(s_0,a_0,…,s_t) has probability ∏i<tπ(ai∣si)P(si+1∣si,ai) _i<tπ(a_i s_i)\,P(s_i+1 s_i,a_i), and the time-t state-visitation distribution is its marginal: dπ,t(st)=∑pathsending at st∏i<tπ(ai∣si)P(si+1∣si,ai).d_π,t(s_t)\;=\; _ subarraycpaths\\ ending at s_t subarray\; _i<tπ(a_i s_i)\;P(s_i+1 s_i,a_i). (12) History-injectivity collapses this sum of products into a single product. History-injectivity removes the sum. If distinct histories of length t reach distinct states, exactly one path ends at sts_t — the one actually taken. The sum has a single term: dπ,t(st)=∏i<tπ(ai∣si)P(si+1∣si,ai),d_π,t(s_t)\;=\; _i<tπ(a_i s_i)\,P(s_i+1 s_i,a_i), with (si,ai,si+1)(s_i,a_i,s_i+1) the states, actions, and successors along that unique path. The kernels cancel in the ratio. The unique path into sts_t is a property of the dynamics, not of the policy, so it is the same path for π~ π and πold _old, with the same transition kernels along it; only the policy probabilities differ. Dividing, every kernel factor appears identically in numerator and denominator and cancels, Rts=dπ~,t(st)dπold,t(st)=∏i<tπ~(ai∣si)πold(ai∣si),R^s_t\;=\; d_ π,t(s_t)d_ _old,t(s_t)\;=\; _i<t π(a_i s_i) _old(a_i s_i), which is (4): the uncomputable state-visitation ratio equals a product of per-step action ratios along the realized trajectory, available from the log-probabilities PPO already computes. However complex the dynamics may be (an arbitrary simulator, a scheduling engine, a stochastic environment), they enter only through which path reaches sts_t, never through the weight of the ratio. Determinism is not used. If si+1=(si,ai)s_i+1=T(s_i,a_i) each kernel is an indicator, 11 on the feasible path and 00 otherwise, and the path weight simplifies to a pure policy product; but the cancellation above holds whatever the kernels’ values, so determinism adds nothing to the identity. What it adds is descriptive: the unique history into sts_t is then determined by the action sequence alone. A stochastic process is history-injective whenever its state records each realized outcome — stochastic execution in scheduling with realized durations carried in the state, or environment-inserted tokens in an agentic language-model context — and the identity then holds with the product taken over the policy’s own decisions, the environment’s kernels cancelling as above. Remark: what history-injectivity does — and does not — buy. Write Wt=∏i<tπ~(ai∣si)/πold(ai∣si)W_t= _i<t π(a_i s_i)/ _old(a_i s_i) for the sampled-path weight, and compare it with the state ratio Rts=dπ~,t(st)/dπold,t(st)R^s_t=d_ π,t(s_t)/d_ _old,t(s_t) it stands in for. The two are different kinds of objects: RtsR^s_t depends only on the endpoint sts_t, while WtW_t depends on the whole path taken to reach it. Three statements relate them, in decreasing strength: • Pointwise (needs history-injectivity). Wt=RtsW_t=R^s_t on every sampled path — the derivation above. • Conditionally unbiased (any MDP). πold[Wt∣st]=RtsE_ _old[W_t s_t]=R^s_t: averaged over the paths that reach sts_t, the weight recovers the ratio. • Unbiased (any MDP). τ∼πold[Wtf(st)]=s∼dπ~,t[f(s)]E_τ _old[W_t\,f(s_t)]=E_s d_ π,t[f(s)] for any f: the corrected surrogate has the right expectation. The two general statements need no structure at all, because the transition kernels are the same under both policies: along any realized path they appear identically in the numerator and denominator of the trajectory-probability ratio and cancel, leaving Pπ~(τ)/Pπold(τ)=WtP_ π(τ)/P_ _old(τ)=W_t. Summing this over all paths ending at sts_t gives the conditional statement; summing over all paths gives the unbiasedness statement — standard per-decision importance sampling [10]. The conditional statement is the identity behind marginalized importance sampling [7], in the time-indexed form of Xie et al. [27]. Both require only the support condition πold>0 _old>0 wherever π~>0 π>0, automatic for softmax policies. What the structural condition buys is therefore not correctness or computability but noise. When many paths merge into the same state, the true ratio RtsR^s_t is an average over all of them, while a single sampled path supplies one random term of that average — right on average, wrong path by path. The conditional variance Varπold(Wt∣st)Var_ _old(W_t s_t) is exactly the Rao–Blackwell gap between the sampled-path weight and the ratio it estimates, the gap that conditional importance sampling [12] closes by estimation. History-injectivity closes it by leaving exactly one path into each state: the sample is the average. In practice: when injectivity fails — e.g., dispatching A then B across two free machines, or B then A, yields the same partial schedule — the reachability graph is a DAG, and the correction is still unbiased but pays this path-merging variance premium. A canonical construction order (Section 2) restores injectivity by making each partial solution constructible in exactly one way; since it changes the action space, corrected-vs-uncorrected comparisons must be run within that environment. This free-order (DAG) vs. canonical-order (tree) distinction is used in the scheduling experiments of Appendix I. Stochastic execution (random processing times, breakdowns) breaks the pointwise statement only when the state omits the realized outcome, so that different draws land on the same partial schedule and paths merge; the two general statements hold either way. Variance of the prefix log-ratio. Write ℓi=μi+mi _i= _i+m_i with μi=[ℓi∣si] _i=E[ _i s_i]. Since aia_i is drawn from πold(⋅∣si) _old(· s_i) given the past, [mi∣s0,a0,…,si]=0E[m_i s_0,a_0,…,s_i]=0, so (mi)(m_i) is a martingale-difference sequence and Var(∑i<tmi)=∑i<t[Var(ℓi∣si)]=tσ2Var\! ( _i<tm_i )= _i<tE[Var( _i s_i)]=tσ^2 exactly. The approximation drops Var(∑i<tμi)+2Cov(∑i<tmi,∑i<tμi)Var\! ( _i<t _i )+2\,Cov\! ( _i<tm_i, _i<t _i ), the terms carrying the variation of the conditional-mean drift across states; both vanish when μi _i is constant. Appendix C Family details: implementation and unevaluated members The added computation is the exclusive cumulative sum LtsL^s_t of the per-step log-ratios ℓi _i; Algorithm 1 shows the tempered member in a standard PPO loop, and Appendix C the one-line implementation in common frameworks. The sum adds no forward or backward pass: LtsL^s_t is a linear function of log-probabilities already in the computation graph, and the backward of a cumulative sum is a reversed cumulative sum. What it adds is O(T)O(T) elementwise operations per sample and one float tensor of shape (batch,T)(batch,T), each a factor V (the size of the action set, the vocabulary for an LM) below the output layer’s O(TV)O(TV) work and the logits the forward pass materializes. Computationally, then, the correction is free, in any MDP; that is the sense of “Free” in the title, and tree structure adds exactness to it, not computability. The cost that remains to weigh is its variance. Algorithm 1 Tempered Prefix-Corrected PPO 1: rollout policy πold _old, trainable policy πθ _θ, value model VϕV_φ, PPO clip ϵε, prefix temperature α, KL coefficient β 2: Sample initial states s0∼p(s0)s_0 p(s_0) and roll out trajectories (a0,…,aT−1)∼πold(a_0,…,a_T-1) _old (for an LM: prompts x and completions y). 3: Store logπold(at∣st) _old(a_t s_t); compute rewards, values, and advantage estimates A^t A_t (held fixed across epochs). 4: for each PPO minibatch and update epoch do 5: Compute logπθ(at∣st) _θ(a_t s_t); set ℓt=logπθ−logπold _t= _θ- _old. 6: Compute prefix log-ratios Lts=∑i<tℓiL^s_t= _i<t _i via an exclusive cumulative sum. ⊳ the only addition to PPO 7: Corrected log-ratio ℓ~t=αLts+ℓt _t=α L^s_t+ _t; corrected ratio r~t=exp(ℓ~t) r_t= ( _t). ⊳ addition 8: Compute clipped policy loss (6); add value loss, entropy bonus, reference-KL penalty. 9: Update θ, ϕφ. 10: end for 11: πold←πθ _old← _θ; repeat. Every variant acts on the prefix log-ratio LtsL^s_t rather than on the product RtsR^s_t it exponentiates to, for four reasons. The clip acts before exponentiation, so nothing under- or overflows. LtsL^s_t is one cumulative sum over log-probabilities PPO already computes. One template covers every row of Table 1. And the variance statement Var(logRts)≈tσ2Var( R^s_t)≈ tσ^2 lives in log space. In code, the correction is one line in any framework (ell of shape (batch,T)(batch,T)): PyTorch L = torch.cumsum(ell, dim=-1) - ell; JAX L = jnp.cumsum(ell, axis=-1) - ell; TensorFlow L = tf.cumsum(ell, axis=-1, exclusive=True). Two further members of the family are natural but not evaluated here. A self-normalized variant divides each weight by the batch mean of the weights — the classical weighted importance-sampling estimator [23, 22, 24]; its bias is a small-batch artifact, O(1/|B|)O(1/|B|), unlike PPO’s structural bias, which no batch size removes. An adaptive variant selects the largest α each batch subject to a floor on the effective sample size of the reweighted batch, the standard weight-degeneracy diagnostic of importance sampling [25], used analogously to constrain policy updates by Metelli et al. [26]. Appendix D Full statements of the conditions This appendix gives the complete arguments behind the conditions summarized in Section 4; notation as there. Throughout, prefix means the partial trajectory up to position t, the history hth_t of Section 2; at positions where the environment rather than the policy moves, ℓi _i and ziz_i are zero, so LtsL^s_t and StS_t both run over the policy’s own decisions. Both channels at the rollout policy. At θ=θoldθ= _old, the first gradient step after a rollout, both channels of (9) are silent under a conditionally centered advantage estimate. The reweighting channel vanishes pointwise, since Lts=0L^s_t=0 and gt(0)=1g_t(0)=1. The credit-routing channel is controlled by A¯πoldπold(st) A_ _old _old(s_t), the value of A¯πoldπθ A_ _old _θ at θold _old where rt=1r_t=1, which reduces to πold[A^t∣st]E_ _old[ A_t s_t]; the channel vanishes state by state exactly when the advantage estimate is conditionally centered, zero-mean given the state. The exact advantage is, by definition (a∼πold[Aπold(st,a)]=0E_a _old[A_ _old(s_t,a)]=0), and so is any estimator whose baseline equals the true state value, such as returns-to-go corrected by a well-fit critic. The estimators training uses are not: sampled returns with a batch-mean baseline are centered across the batch, not within each state, leaving πold[A^t∣st]≠0E_ _old[ A_t s_t]≠ 0. The correction therefore acts through two routes: policy drift, the movement away from the rollout policy across the reuse epochs of one update or on stale data; and imperfect centering of the advantage estimate, which is present from the first step. C1. The first condition is that the reward must still be undecided late (C1). Each term of (9) is a product of a drift factor, gt(Lts)−1g_t(L^s_t)-1 or gt′(Lts)Stg_t (L^s_t)\,S_t, and a content factor, hθh_θ or A¯πoldπθ A_ _old _θ, at the same position, and the two have separate origins. The drift factors are reward-blind: they start at zero and grow with position (L0s=0L^s_0=0 and Var(Lts)≈tσ2Var(L^s_t)≈ tσ^2 by Section 3.1; StS_t collects t scores), and depend on the reward only through earlier gradient steps. The reward enters through the content factors, which carry the advantage, and the advantage at position t measures only reward that position can still influence. Aπold(st,a)A_ _old(s_t,a) is the difference between the expected return given (st,a)(s_t,a) and given sts_t alone, so any reward component whose expectation given sts_t no longer depends on the actions from t onward contributes equally to both and cancels: reward already collected, and equally reward not yet paid that the actions ahead can no longer influence. What sets where content can live is therefore the position at which the reward is decided, not the position at which it is delivered. A reward decided by the first action vanishes from Aπold(st,⋅)A_ _old(s_t,·) for every t≥1t≥ 1, exactly the late positions where the drift factors are large, even if it is paid at the terminal step, whereas a reward that late actions can still win or lose keeps the content factors alive there.11 1 For the exact advantage or any conditionally centered estimate. An imperfectly centered estimate, such as the trajectory return minus a batch-mean baseline, is constant along the trajectory and does survive at late positions. But an early-decided reward is fixed by the prefix, so conditioning on sts_t makes A^t A_t a function of the state alone; this still silences the reweighting channel, hθ(st)=A^(st)πold[rtzt∣st]=0h_θ(s_t)= A(s_t)\,E_ _old[r_tz_t s_t]=0 since πold[rtzt∣st]=∇θ∑aπθ(a∣st)=0E_ _old[r_tz_t s_t]= _θ _a _θ(a s_t)=0, while the credit-routing content A¯πoldπθ(st)=A^(st) A_ _old _θ(s_t)= A(s_t) stays alive — the imperfect-centering route above. C1 is this alignment: the reward must remain contested, still dependent on the actions ahead, at positions where drift has accumulated. In the rewards studied below the deciding and the delivering position coincide, so we keep the shorthand late reward; the operative property is late decision. C2. The second condition is that the reward must depend on the prefix (C2). At a fixed position, (9) still averages over states. To first order gt(L)−1≈gt′(0)Lg_t(L)-1≈ g_t (0)\,L, so the reweighting term’s average is, to leading order in the drift, gt′(0)Cov(Lts,hθ(st))g_t (0)\,Cov(L^s_t,\,h_θ(s_t)). C2 is the requirement that this covariance be nonzero: hθh_θ must differ between the states the correction upweights (Lts>0L^s_t>0) and those it downweights (Lts<0L^s_t<0). A reward that leaves every prefix equally good makes the conditional law of (at,A^t)(a_t, A_t) given sts_t the same at every state. Then hθh_θ varies across states only through the score, so the covariance carries no reward signal, and A¯πoldπθ A_ _old _θ is a constant c across states, so the credit-routing average reduces to cπold[gt′(Lts)St]c\,E_ _old[g_t (L^s_t)\,S_t]. For the full correction this factor is exactly zero at any θ: gt′=Rtsg_t =R^s_t moves the prefix draw to πθ _θ, where πθ[zi]=0E_ _θ[z_i]=0. For tempered members it is zero at θ=θoldθ= _old, where πold[St]=0E_ _old[S_t]=0 by the same score identity, and first-order in the drift beyond. A conditionally centered advantage makes c first-order as well, leaving a second-order residual; imperfect centering keeps c order one, the centering route again. The late-only reward of Section 5.1 instantiates this case, C1 active and C2 absent. C3. The third condition is that the sampling-and-update loop must amplify a per-update gradient difference rather than wash it out (C3). A gradient that is better in expectation need not change where training ends: PPO may learn the same solution a few updates later, so without amplification the correction shows up as speed, not as a different endpoint. The clearest amplifier is a self-reinforcing sampling trap: a wrong early commitment makes rewarded trajectories so rare that a finite batch, scored against a batch-mean baseline, contains no restoring gradient, so the next batch is drawn from a still-worse policy. Whether a task admits such a trap depends jointly on the reward, the batch size, the baseline, entropy or KL regularization, the optimizer, and the number of reuse epochs. Condition Plain statement Quantity to check If it fails C1: late-decided reward reward still action-dependent after prefix mismatch has accumulated |Lts||L^s_t| at advantage-carrying positions (Var(Lts)≈tσ2Var(L^s_t)≈ tσ^2) channels are inert; only variance remains C2: prefix-dependent reward upweighted and downweighted prefixes differ in value bt=Covπold(Rts,rtA^t)≠0b_t=Cov_ _old(R^s_t,r_t A_t)≠ 0 contributions cancel across prefixes C3: sampling trap an early mistake starves batches of rewarded trajectories frequency of zero-reward batches speed gain at most; same endpoint 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. In every case the recovered bias must be weighed against the variance of the prefix ratio RtsR^s_t, which grows with α and with the horizon (Section 3.1); the conditions say when there is a bias worth recovering, not that recovering it is free. Algorithm 1 optimizes the clipped objective (6), not the surrogate analyzed above, and clipping gates both channels: wherever the min in (6) selects the flat clipped branch, the position-t gradient is zero and neither gtg_t nor gt′g_t enters. The observation of Section 6 that on an easy task the clip alone contains the bias of even aggressive reuse describes this gate empirically; it is not derived here. Appendix E An operating-point hypothesis for the effect size The three questions decide whether an effect is possible; a heuristic operating-point argument suggests its magnitude, and we state it as a hypothesis. Expanding the tempered estimator around θold _old (eαLts≈1+αLtse^α L^s_t≈ 1+α L^s_t), the reweighting channel’s expected contribution is αSα S with S=∑tCov(Lts,hθ(st))S= _tCov(L^s_t,\,h_θ(s_t)), the omitted bias itself, while the credit-routing channel’s variance grows like T2T^2 (position t sums t score vectors) even at zero drift. With N trajectories per batch and gradient scale G, the expected per-update progress advantage then has the form Δ(α)≈αS−α2NV,V∝T2G(1+σ2), (α)\;≈\;α\,S\;-\; α^2N\,V, V\; \;T^2\,G\,(1+σ^2), (13) maximized at α⋆=SN/2Vα =SN/2V with peak Δ⋆=S2N/4V =S^2N/4V. The peak advantage carries a prefactor of order N/T2N/T^2 if S scales with T more slowly than V does — writing S2/VS^2/V as ρ2σ4/T2ρ^2σ^4/T^2 up to the unresolved T-dependence of S, with ρ the correlation between the drift direction and reward-relevant structure — Δ⋆∝ρ2σ4⋅NT2, \; \;ρ^2σ^4· NT^2, (14) and (14) is the hypothesis: the T-scaling of S is not pinned down here. Its content is that batch size relative to squared horizon decides whether a correct-sign effect clears the seed-noise floor. The testbed cells operate at N/T2≈256/62≈7N/T^2≈ 256/6^2≈ 7; the scheduling experiments at 20/502≈0.00820/50^2≈ 0.008, three orders of magnitude lower at nominally comparable drift, correlation, and reward shape. Under the hypothesis, the scheduling nulls at realistic operating points are consistent with the mechanism rather than evidence against it, and the hypothesis is falsifiable: a paired advantage that grows linearly in N and falls as 1/T21/T^2, which a short-horizon scheduling variant (T≈20T≈ 20) at testbed batch sizes (N=256N=256) would test. Appendix F Testbed protocol and estimator diagnostics F.1 Common protocol The transformer policy used in the synthetic learning experiments is a 44-layer, dmodel=128d_model=128, 44-head causal transformer (≈793≈ 793k parameters). The tabular policy has one logit per prefix–token pair, V(VT−1)/(V−1)V(V^T-1)/(V-1) in total: about 66k at T=6T=6 and 9090k at T=8T=8. Unless stated otherwise, learning experiments use 256256 trajectories per iteration, returns-to-go advantages with a batch-mean baseline, and K=4K=4 update epochs. The compared estimator variants are PPO; tempered α∈0.05,0.1,0.25,0.5,1α∈\0.05,0.1,0.25,0.5,1\; truncated k∈1,2,4k∈\1,2,4\; and clipped (α,c)∈(0.1,1.0),(0.25,1.0),(0.25,2.0)(α,c)∈\(0.1,1.0),(0.25,1.0),(0.25,2.0)\. Sign tests follow the convention of Section 6: exact, one-sided for pre-specified directional improvements, two-sided for falsifier and null checks. Control rewards of the ladder. The three controls of Section 5.1, each stopping short of either the full condition set or measurable training outcomes: • Step-additive early gate. The first token gates the reward: for sequences starting with y0=y_0= A (resp. y0=y_0= C) the target symbol is B (resp. D), the reward is the fraction of later positions equal to the target, R=1T−1∑t=1T−1[yt=target]R= 1T-1 _t=1^T-11[y_t=target], and any other first token gives R=0R=0. Signal therefore accrues at every step, only partly overlapping with accumulated prefix mismatch (C1 partial), and prefix dependence is weak (C2 weak), making the early gate the lowest-leverage control. • Late-only. R=[yT−1=]R=1[y_T-1= B] is decided by the final action, the position where the prefix ratio RtsR^s_t is largest (C1), but the reward does not distinguish earlier prefixes (C2 absent): this is the rung that isolates C1 from C2. • Sparse trajectory match. R=[y=]R=1[y= ABBBBB] rewards exactly one complete sequence at T=6T=6, adding what the late-only rung lacks: prefix dependence (C2), and with it the possibility of a narrow sampling trap (C3). But a single rewarded sequence is too rare a target — probability 4−64^-6 under the uniform policy — and training outcomes on it are noisy. F.2 Estimator diagnostics Each estimator is scored first as an estimator: the bias, variance, and mean squared error (MSE) of the single-trajectory estimate L L (7), Bias[L^] [ L] =πold[L^]−(η(πθ)−η(πold)), =E_ _old[ L]- (η( _θ)-η( _old) ), (15) Var[L^] [ L] =πold[(L^−πold[L^])2], =E_ _old\! [ ( L-E_ _old[ L] )^2 ], (16) MSE[L^] [ L] =πold[(L^−(η(πθ)−η(πold)))2]=Bias[L^]2+Var[L^], =E_ _old\! [ ( L-(η( _θ)-η( _old)) )^2 ]=Bias[ L]^2+Var[ L], (17) where averaging L L over a batch of N trajectories divides the variance by N and leaves the bias unchanged. Two further diagnostics look past the scalar estimate. The direction, the cosine cos(∇θη,∇θπold[L^]) ( _θη,\, _θE_ _old[ L] ) between the gradient of the expected estimate and the exact return gradient, scores the update the estimator induces. The normalized effective sample size, ESS=(πold[w])2/πold[w2]∈(0,1]ESS= (E_ _old[w] )^2/E_ _old[w^2]∈(0,1] with w the estimator’s prefix-correction weight gt(Lts)g_t(L^s_t) [25], scores the batch: N trajectories carry the information of roughly ESS⋅NESS· N equally weighted ones. The contrasts are sharpest on the late-only reward at the largest tested drift; Appendix F.2 reports the sweeps over all drift magnitudes and both control rewards, and Table 2 and Figure 2 the full variant grid at this operating point, D¯KL≈0.33 D_KL≈ 0.33. Method |Bias[L^]||Bias[ L]| MSE[L^]MSE[ L] (± SEM) cos(∇η,∇[L^]) (∇η, [ L]) Normalized ESS PPO (α=0α=0) 1.8×10−41.8× 10^-4 2.96×10−1±1.9×10−32.96× 10^-1± 1.9× 10^-3 0.200.20 1.001.00 Tempered α=0.05α=0.05 2.3×10−42.3× 10^-4 2.55×10−1±1.9×10−32.55× 10^-1± 1.9× 10^-3 0.260.26 1.001.00 Tempered α=0.10α=0.10 2.6×10−42.6× 10^-4 2.29×10−1±2.2×10−32.29× 10^-1± 2.2× 10^-3 0.330.33 0.980.98 Tempered α=0.25α=0.25 3.0×10−43.0× 10^-4 2.03×−±2.7×−2.03× 10^-1± 2.7× 10^-3 0.530.53 0.900.90 Tempered α=0.50α=0.50 2.6×10−42.6× 10^-4 2.96×10−1±5.2×10−32.96× 10^-1± 5.2× 10^-3 0.810.81 0.700.70 Full (α=1α=1) 2.1×10−172.1× 10^-17 2.90×100±3.2×10−12.90× 10^0± 3.2× 10^-1 1.001.00 0.260.26 Clipped (0.25, 1.0)(0.25,\,1.0) 2.8×10−42.8× 10^-4 2.04×10−1±2.6×10−32.04× 10^-1± 2.6× 10^-3 0.520.52 0.900.90 Table 6: Estimator diagnostics at D¯KL≈0.33 D_KL≈ 0.33 on the late-only reward, 2525 seeds; single-trajectory estimate L L (7). Bold marks the lowest MSE. Figure 2: Mean squared error MSE[L^]MSE[ L] (17) of the single-trajectory estimate versus the tempering coefficient α, on the late-only reward at the largest tested drift (D¯KL≈0.33 D_KL≈ 0.33, 2525 seeds, error bars ±1± 1 SEM, log scale). The dashed line is PPO (α=0α=0). The trade-off has an interior minimum at tempered α=0.25α=0.25; the values are in Table 2. Measurement procedure. Each measurement is made on a controlled pair of policies standing in for the data-collecting and updated policies of one reuse step. The rollout policy πold _old is a fixed near-uniform tabular softmax; the candidate πθ _θ is obtained by adding Gaussian noise to every logit, θπ~=θπold+δε _ π= _ _old+δ\, with ε∼(0,I) (0,I), so the magnitude δ dials the policy drift directly. We sweep δ∈0.01,0.03,0.1,0.3,0.6,1.0δ∈\0.01,0.03,0.1,0.3,0.6,1.0\, spanning D¯KL(πold,π~) D_KL( _old, π) from 4×10−54× 10^-5 to 0.330.33, with 55 noise seeds per magnitude (2525 for the late-only run of (d)); all 1212 variants are evaluated on the same policy pair within each (seed, δ) cell. Because the MDP is enumerable at horizon T=6T=6, every quantity is computed exactly by summing over all 464^6 sequences, so no Monte Carlo error enters. For each variant, the single-trajectory estimate L L (7) is formed from the exact backward-induction advantages AπoldA_ _old, and its expectation is taken under the exact sequence distribution of πold _old. Bias, variance, MSE, gradient cosine, and normalized ESS are as defined in Section 5.2; the two gradients in the cosine are computed by automatic differentiation through the exact sums and flattened over the candidate’s full logit table, one cosine per policy pair, and the normalized ESS is taken over the joint (sequence, position) distribution. (a) PPO. On the step-additive early-gate reward, PPO’s bias is negative and grows monotonically with KL (−5.3×10−7-5.3× 10^-7 to −4.8×10−3-4.8× 10^-3); variance stays near the trajectory-advantage floor (3.3×10−23.3× 10^-2 to 5.4×10−25.4× 10^-2); gradient cosine degrades from 1.0001.000 to 0.9510.951. Bias stays below 5×10−35× 10^-3 — masked by the variance floor in MSE but visible in direction. (b) Full. Bias bounded by 2×10−172× 10^-17 at every δ — floating-point zero, verifying (5) as an algebraic identity, a check no sampled experiment could provide. Gradient cosine stays 1.0001.000. The cost: variance grows to 1.4×10−11.4× 10^-1 (2.7×2.7× PPO at the same KL) and normalized ESS collapses from ≈1.0≈ 1.0 to ≈0.27≈ 0.27. (c) Intermediate variants. Interpolation is monotone in α, k, and c on every metric. At the largest δ: interior MSE minimum at tempered α=0.25α=0.25 / clipped (0.25,1.0)(0.25,1.0) (5.0×10−25.0× 10^-2, vs. PPO’s 5.4×10−25.4× 10^-2 and full’s 1.4×10−11.4× 10^-1 — a 7%7\% margin on this reward, capped by the variance floor); gradient-cosine ordering full 1.000>1.000> truncated k=4k=4 0.998>0.998> tempered 0.50.5 0.985>0.985> tempered 0.250.25 0.973>0.973> PPO 0.9510.951; nESS 0.900.90 (tempered 0.250.25), 0.700.70 (0.50.5), 0.290.29 (truncated k=4k=4), 0.270.27 (full). Gradient direction is already decisive here — the prediction taken to the training experiments. (d) Late-only reward — sharpened gaps. Concentrating all advantage at t=T−1t=T-1 via R=[yT−1=]R=1[y_T-1= B] amplifies everything (Table 2, Figure 2). At D¯KL≈0.33 D_KL≈ 0.33: PPO’s bias stays ≲2×10−4 2× 10^-4 but its gradient cosine collapses to 0.200.20, near-orthogonal; full’s variance explodes to 2.92.9, an order of magnitude above PPO, driven by trajectory-IS outliers at rare-visit prefixes. Tempered α=0.25α=0.25: MSE 2.03×10−12.03× 10^-1 (32%32\% below PPO), variance 2.02×10−12.02× 10^-1 against PPO’s 2.96×10−12.96× 10^-1 (Table 2, Figure 2). A terminal reward that late tokens still decide — final-answer correctness, a terminal reward-model score — falls in this regime; one already sealed by the early tokens falls under the early-decided case of Section 4. F.3 Null controls: rewards without prefix dependence or a sampling trap On the three control rewards of the ladder (Section 5.1) the estimator MSE margin of the best interior variant over PPO is 11%11\% on the step-additive early gate (C1 partial, C2 weak); 32%32\% on late-only (C1 without C2), with no training-loop advantage — the cleanest separation of the estimator diagnostic from the training effect; and present, with noisy training outcomes, on the sparse trajectory match (C2, C3). The two-branch reward (11) activates C1–C3 while keeping rewarded trajectories frequent enough for training outcomes to be measurable, which is why the training sub-experiments use it. Appendix G Testbed training experiments G.1 Tabular policy under N-SGD Tabular policy, two-branch reward, N-SGD at =0.3 lr=0.3, K=4K=4, 33 seeds, 200200 iterations. N-SGD removes the direction-vs-magnitude confound. The break-through order through the η≈0.25η≈ 0.25 plateau is strict and matches the estimator prediction: interior tempered and clipped first, PPO next, full and truncated k=4k=4 last, paying the predicted variance penalties (Figure 3, Table 7). Method Break-through iter. η at iter. 5050 Iter. to η=1.000η=1.000 Tempered α=0.10α=0.10 3030–4545 0.9610.961 5050 Clipped (0.25, 1.0)(0.25,\,1.0) 3030–4545 0.9600.960 5050 Tempered α=0.05α=0.05 5050 0.9000.900 5555 Tempered α=0.25α=0.25 5050–5555 0.7810.781 6060 Tempered α=0.50α=0.50 5050–6060 0.4680.468 7070 PPO 5050–6060 0.3410.341 7070 Full 7070 0.2600.260 8585 Truncated k=4k=4 8080–9090 0.2620.262 100100 Table 7: Tabular policy under N-SGD (=0.3 lr=0.3, K=4K=4, 33 seeds): iteration of break-through past the η≈0.25η≈ 0.25 plateau, exact return at iteration 5050, and iteration at which η reaches 11. Figure 3: Exact return versus iteration on the two-branch reward: tabular policy, N-SGD (=0.3 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 c never binds. G.2 Transformer under N-SGD Figure 4: Mean exact return over 1010 seeds versus iteration for the 793793k-parameter transformer under N-SGD (=1.0 lr=1.0, K=4K=4). Outcomes are bimodal (η≈0η≈ 0 or 11), so the mean is the success-rate curve; the success rates are in Table 3. Same reward and PPO scaffold with the 793793k-parameter transformer, sample-based η on fresh 10241024-trajectory batches, N-SGD, ∈0.3,1.0,3.0 lr∈\0.3,1.0,3.0\, 1010 seeds. At =0.3 lr=0.3 all methods succeed 10/1010/10; at 3.03.0 everything is too aggressive (best: tempered α=0.25α=0.25 at 2/102/10). The discriminating rate is =1.0 lr=1.0 (Figure 4, Table 8), where the interior tempered variants succeed on every seed and PPO on seven of ten. Losing seeds fail by self-reinforcing wrong-branch commitment — P(y0∈,)→1P(y_0∈\ B, D\)→ 1 within iterations 55–1010, after which no batch contains a rewarded trajectory and the gradient estimate is zero. Method Success rate (n=10n=10) Final η (mean ± SEM) Tempered α=0.05α=0.05 /10/10 1.000±0.0001.000± 0.000 Tempered α=0.10α=0.10 /10/10 1.000±0.0001.000± 0.000 Clipped (0.10, 1.0)(0.10,\,1.0) 9/109/10 0.900±0.1000.900± 0.100 Clipped (0.25, 2.0)(0.25,\,2.0) 8/98/9 0.889±0.1110.889± 0.111 Tempered α=0.25α=0.25 8/108/10 0.800±0.1330.800± 0.133 PPO 7/107/10 0.700±0.1530.700± 0.153 Tempered α=0.50α=0.50 7/107/10 0.700±0.1530.700± 0.153 Truncated k=2k=2 7/107/10 0.700±0.1530.700± 0.153 Full 6/106/10 0.600±0.1630.600± 0.163 Truncated k=1k=1 6/106/10 0.600±0.1630.600± 0.163 Truncated k=4k=4 5/105/10 0.500±0.1670.500± 0.167 Clipped (0.25, 1.0)(0.25,\,1.0) 5/105/10 0.500±0.1670.500± 0.167 Table 8: Transformer under N-SGD at =1.0 lr=1.0 (K=4K=4, 1010 seeds): success rate and final η per variant. G.3 Transformer under Adam Same setup with Adam, ∈10−3,3×10−3,10−2 lr∈\10^-3,3× 10^-3,10^-2\. Adam’s per-parameter RMS normalization partially absorbs gradient-direction bias (Appendix G.4). At =10−3 lr=10^-3 all methods succeed 10/1010/10. At 3×10−33× 10^-3 (Figure 5, Table 9) clipped (0.1,1.0)(0.1,1.0) and tempered α=0.1α=0.1 lead PPO by 1919 p, roughly two thirds of the N-SGD gap. At the aggressive 10−210^-2 (Table 10) tempered α=0.1α=0.1 keeps a 2020 p lead over PPO while the full correction collapses to no successful seed, the worst method: Adam’s per-parameter adaptivity applied to the accumulated ratio produces unbounded updates on outlier tokens, the failure mode CTPO’s t t-scaled clip prevents. Figure 5: Adam ablation of Figure 4 (=3×10−3 lr=3× 10^-3, K=4K=4, 1010 seeds). The success-rate advantage survives at reduced amplitude (Table 9). Method Success rate Final η (mean ± SEM) Clipped (0.10, 1.0)(0.10,\,1.0) /8/9 0.889±0.1110.889± 0.111 Tempered α=0.10α=0.10 8/108/10 0.800±0.1330.800± 0.133 Clipped (0.25, 1.0)(0.25,\,1.0) 7/97/9 0.778±0.1470.778± 0.147 PPO 7/107/10 0.700±0.1530.700± 0.153 Tempered α=0.25α=0.25 7/107/10 0.700±0.1530.700± 0.153 Full 7/107/10 0.700±0.1530.700± 0.153 Tempered α=0.05α=0.05 6/106/10 0.600±0.1630.600± 0.163 Tempered α=0.50α=0.50 6/106/10 0.600±0.1630.600± 0.163 Truncated k=2k=2 5/95/9 0.556±0.1760.556± 0.176 Clipped (0.25, 2.0)(0.25,\,2.0) 5/95/9 0.556±0.1760.556± 0.176 Truncated k=1k=1 4/104/10 0.400±0.1630.400± 0.163 Truncated k=4k=4 3/93/9 0.333±0.1670.333± 0.167 Table 9: Transformer under Adam at =3×10−3 lr=3× 10^-3 (K=4K=4): success rate and final η per variant. Method Success rate Final η (mean ± SEM) Tempered α=0.10α=0.10 /5/10 0.500±0.1670.500± 0.167 PPO 3/103/10 0.300±0.1530.300± 0.153 Tempered α=0.05α=0.05 2/102/10 0.200±0.1330.200± 0.133 Tempered α=0.25α=0.25 2/102/10 0.200±0.1330.200± 0.133 Clipped (0.25, 1.0)(0.25,\,1.0) 2/92/9 0.222±0.1470.222± 0.147 Clipped (0.25, 2.0)(0.25,\,2.0) 2/92/9 0.222±0.1470.222± 0.147 Tempered α=0.50α=0.50 1/101/10 0.100±0.1000.100± 0.100 Truncated k=1k=1 1/101/10 0.100±0.1000.100± 0.100 Clipped (0.10, 1.0)(0.10,\,1.0) 0/90/9 0.002±0.0020.002± 0.002 Truncated k=2k=2 0/90/9 0.0000.000 Truncated k=4k=4 0/90/9 0.0000.000 Full (α=1α=1) /0/10 0.0000.000 (worst) Table 10: Transformer under Adam at =10−2 lr=10^-2 (K=4K=4): success rate and final η per variant. G.4 Optimizer-absorption ablation on the tabular policy Swapping N-SGD for Adam on the tabular two-branch setup shrinks the interior-tempered-over-PPO advantage at iteration 5050 from η=0.961η=0.961 vs. 0.3410.341 under N-SGD to a relative lead of about 20%20\% — Adam’s per-parameter RMS normalization rescales the biased direction back toward the true gradient, absorbing part but not all of the estimator-level bias. The transformer result (3030 p → 1919 p, Appendix G.3) matches this tabular prediction, completing the optimizer × parameterization 2×22× 2 and showing the mechanism decomposition is not sensitive to parameterization scale at the sizes tested. Appendix H Pretrained-LM study: structured-record consistency at 0.50.5B We test whether the gradient-and-training account of Section 4 predicts the LM-scale effect on Qwen2.5-0.5B (base). The reward is a rule-verifiable string check on structured JSON: the model fills a 66-slot template (status/service/region/retries/load/code), each slot a masked 44-way choice with all candidates single-token in context (tokenizer gate 24/2424/24), and the reward reads two slots. The complete-sequence space is 46=40964^6=4096, so η(π)η(π), S1S_1 marginals, and P(S6∣S1)P(S_6 S_1) are exactly enumerable at any training point. Protocol. Custom masked-slot generation and PPO update — no TRL/HF-Trainer scaffold — so all six variants share one code path differing only in the g(Lts)g(L^s_t) switch (asserted by a bit-identical-loss test at α=0α=0). Frozen config: 256256 rollouts/iteration, minibatch 88, K=4K=4, ϵ=0.2ε=0.2, Adam (β1=0.9 _1=0.9, β2=0.95 _2=0.95), grad clip 1.01.0, entropy =0=0, ref-KL =0=0 (no external restoring force), =3×10−6 lr=3× 10^-6 frozen by pilot; advantage == trajectory return minus batch-mean baseline. 1010 seeds per (cell, method), extended to 1616 paired seeds for the pre-registered headline pair (PPO vs. tempered α=0.10α=0.10) in Cells 1, 3, 4. bf16 with gradient checkpointing on one L4. Cell design. All cells place reward at the terminal slot S6S_6. The reward and an N=8N=8 few-shot priming prefix vary whether terminal value depends on the earlier slot S1S_1 and whether the sampling loop is susceptible to a low-reward trap: Cell Priming (S1S_1 in N=8N=8) Reward η0 _0 [rew/256]E[rew/256] Role 1 NEUTRAL (uniform) TWO_BR (matched) 0.3860.386 9999 Prefix-dependent value; dense reward prevents a trap 3 FATAL (unknown, soften 0.250.25) TWO_BR 0.0330.033 8.58.5 Prefix-dependent value; designed low-reward trap 4 NEUTRAL (uniform) LATE_ONLY 0.3980.398 102102 Terminal reward independent of S1S_1 — null control Pre-run sign-off measurements (per-condition S1S_1 marginals, full P(S6∣S1)P(S_6 S_1), η0 _0 per reward, off-policiness dry-run, α⋆=1/(Tσ2)α =1/(Tσ^2) heuristic in [0.02,0.3][0.02,0.3] for every cell) are recorded in FREEZE_TABLE.md; all 1212 pre-flight gates pass. Pilot and endpoint revision. A Cell-1 pilot (22 methods × 33 lrs × 33 seeds, 5050 iterations) froze =3×10−6 lr=3× 10^-6 and showed a +9+9 p early lead for tempered α=0.10α=0.10 at iteration 33, collapsing by iteration 1010 as both arms hit ceiling (18/1818/18 pilot runs succeeded). The pilot revised the primary endpoint from iters-to-η0.9 _0.9 (which the _=10 eval\_every=10 discretisation cannot resolve for sub-1010-iteration effects) to mean MC η over iterations 22–88; Cell 3 kept the brief’s original success-rate endpoint, since a sampling trap would turn mean-η into a mixture of successful and failed runs. The pilot table is in outputs/pilot/. Cell 1 — rate advantage transfers. At η0=0.386 _0=0.386 (≈99≈ 99 rewarded trajectories per batch), a sampling trap is implausible and the analysis predicts a rate advantage, which is what we observe (Table 11): tempered α=0.10α=0.10 climbs faster over iterations 22–55, collapsing to noise by iteration 1010 at ceiling. Table 11: Cell 1 (NEUTRAL N=8N=8, TWO_BRANCH) per-iteration MC η, 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. Method iter 2 iter 3 iter 4 iter 5 iter 10 iter 20 PPO 0.5340.534 0.7560.756 0.8840.884 0.9570.957 0.9980.998 0.9990.999 Tempered α=0.10α=0.10 0.7060.706 0.9100.910 0.9780.978 0.9940.994 0.9990.999 0.9990.999 Δ (T −- P) p +17.1+17.1 +15.4+15.4 +9.4+9.4 +3.7+3.7 +0.1+0.1 +0.05+0.05 The full method grid (Table 12; all 7272 Cell-1 runs succeed, so the cell is purely rate-mode) reproduces the toy interior-α profile, peaking at α=0.10α=0.10 and collapsing at α=1α=1 where the variance penalty cancels the bias correction. The peak brackets the pre-registered α⋆≈0.08α ≈ 0.08 heuristic; clipped (0.10,1.0)(0.10,1.0) is indistinguishable from tempered 0.100.10, as expected when the log-space clip rarely binds at this KL scale. Table 12: Cell 1 full grid: paired difference vs. PPO on mean MC η over iterations 22–88 (the pre-registered rate endpoint); normal-approximation 95%95\% CI on the paired mean. Method n (paired seeds) Δ vs. PPO (p) seeds positive 95%95\% CI (p) Tempered α=0.05α=0.05 1010 +4.5+4.5 9/109/10 ±2.6± 2.6 Tempered α=0.10α=0.10 1616 +6.7+6.7 /16/16 ±2.5± 2.5 Tempered α=0.25α=0.25 1010 +5.8+5.8 10/1010/10 ±3.4± 3.4 Clipped (0.10, 1.0)(0.10,\,1.0) 1010 +6.5+6.5 10/1010/10 ±3.4± 3.4 Full (α=1α=1) 1010 +0.1+0.1 6/106/10 ±1.9± 1.9 Cell 3 — the success-rate mechanism does not fire. At η0=0.033 _0=0.033 ([rew/256]=8.5E[rew/256]=8.5, just above the absorbing floor), a sampling trap would require the biased-gradient direction to drive the policy toward the fatal-primed marginal in iterations 11–55; if it wins, η falls below 0.0200.020, zero-reward batches become likely (≥5.7×10−3≥ 5.7× 10^-3 per iteration, cumulatively ≳10% 10\% over 2020), and the run pins. The measured per-iteration MC fatal marginal does not rise on any of the 1616 PPO seeds: it starts in [0.31,1.00][0.31,1.00] (Poisson-noised around the exact 0.7420.742 under FATAL priming) and declines monotonically, reaching mean ≤0.02≤ 0.02 by iteration 1010 and ≤10−3≤ 10^-3 by 1515 (Table 13). One seed (PPO_s2) plateaus near 0.980.98 for iterations 11–55 before collapsing — the expected signature at a high-initial-fatal seed where rewarded rollouts number 11–22 per batch — but the biased direction never dominates. All 1616 PPO seeds succeed; tempered α=0.10α=0.10 shows the same pattern (16/1616/16; highest initial fatal marginal 0.9960.996, collapsing to 0.0000.000 by iteration 55). Table 13: Cell 3 per-iteration fatal-marginal decline (mean/max/min over 1616 PPO seeds). No seed rises; all reach ≤10−2≤ 10^-2 by iteration 1010. iter 1 2 3 4 5 7 10 15 20 mean 0.778 0.649 0.454 0.333 0.229 0.096 0.014 0.001 0.000 max 0.996 0.996 0.988 0.957 0.973 0.668 0.180 0.008 0.004 min 0.312 0.141 0.035 0.012 0.000 0.000 0.000 0.000 0.000 The reason is structural: in the toy MDP a wrong first-token commitment yields deterministically zero reward under any continuation, whereas at LM scale ≈8.5≈ 8.5 rewarded trajectories per batch arrive in expectation even under FATAL priming, and their advantage signal dominates the biased-gradient drift from iteration 11. Truncation disclosure. Cell 3’s non-headline arms (tempered α∈0.05,0.25α∈\0.05,0.25\, clipped, full) were cancelled after the PPO tier completed 16/1616/16 at ceiling with no fatal-marginal drift — no success-rate comparison was possible at ceiling. Only the pre-registered headline pair ran to 1616 seeds; the other methods are retained in Cell 1’s grid, where the rate endpoint discriminates. Cell 4 — the pre-registered falsifier passes. Cell 4 keeps Cell 1’s priming (same NEUTRAL N=8N=8 lines, same initial S1S_1 marginal) and swaps only the reward: LATE_ONLY =[S6=target]=1[S_6=target] pays regardless of S1S_1, removing reward dependence on S1S_1 while holding terminal reward placement and the off-policiness scale (Var(logR5s)=10.4Var( R^s_5)=10.4, identical to Cell 3’s gate value) fixed. The pre-registered prediction is Δη≈0 η≈ 0; a Cell-1-sized effect here would contradict the Cell 1 attribution. Table 14: Cell 4 (NEUTRAL N=8N=8, LATE_ONLY) per-iteration MC η, 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. Method iter 2 iter 3 iter 4 iter 5 iter 10 iter 20 PPO 0.6630.663 0.8760.876 0.9550.955 0.9850.985 0.9990.999 0.9990.999 Tempered α=0.10α=0.10 0.7150.715 0.9210.921 0.9840.984 0.9940.994 0.9980.998 0.9990.999 Δ (T −- P) p +5.1+5.1 +4.6+4.6 +2.9+2.9 +0.9+0.9 −0.05-0.05 −0.02-0.02 On the primary endpoint the paired difference is +1.9+1.9 p (95%95\% CI ±1.8± 1.8 p) with 8/168/16 seeds positive — a two-sided sign test at exactly chance (p=1.0p=1.0), against Cell 1’s +6.7+6.7 p at 16/1616/16 (p≈3×10−5p≈ 3× 10^-5): a 3.5×3.5× attenuation in mean and a complete collapse in per-seed consistency. The paired-mean CI marginally excludes zero, and the residual has a mechanistic home — unlike the tabular late-only null, where the optimum provably leaves early tokens uniform, the pretrained conditional P(S6∣S1)P(S_6 S_1) is not exactly S1S_1-independent, so the reward-relevant prefix dependence is attenuated rather than eliminated exactly at LM scale. The per-seed S1S_1 endpoints corroborate this: Cell 1’s PPO seeds all commit S1S_1 to a reward-matched branch by iteration 2020, while Cell 4’s scatter across seed-dependent directions (two seeds drift onto unknown, a value TWO_BRANCH would kill) — free drift under no restoring force, not a reward-required commitment. The full Cell 4 grid sharpens the null into a positive prediction: with no bias to correct, the correction’s cost should remain. The full correction is strictly worse than PPO — −4.4-4.4 p, 0/100/10 seeds positive, 95%95\% CI ±2.5± 2.5 p — the variance penalty with no compensating bias reduction, mirroring the late-only control in the reward ladder of Section 5.1 and V-trace’s motivation for refusing the accumulated product. Interior variants sit at small, sign-inconsistent residuals (tempered α=0.05α=0.05: +1.2+1.2 p at 5/105/10; α=0.25α=0.25: +1.1+1.1 p at 4/104/10; clipped: +2.6+2.6 p at 6/106/10). All 7272 Cell-4 runs succeed, as expected at [rew/256]=102E[rew/256]=102. Appendix I Scheduling: nulls, controls, and boundary I.1 With no measured drift, the correction only costs variance At realistic operating points a held correction is null to harmful, for two measurable reasons (Table 15). The first is that realistic training accumulates no staleness to repair. At published FJSP hyperparameters the drift after a full K=3K=3 update is σ2T≈3×10−5σ^2T≈ 3× 10^-5, and the correction loses to PPO in every cell, winning 44 of 6060 paired comparisons (Appendix I.1). With no stale state distribution to repair, the credit-routing channel pays its horizon-dependent variance cost and buys nothing back. The second reason is why raising drift alone does not help. Dialing the learning rate, clip, and K until the drift rises by five orders of magnitude makes the paired final on-time difference cross zero, with every paired seed won at the top, but only at a deadline where training sits at the reward floor; at a fair deadline the same dial yields a null, because with plentiful signal PPO relearns from fresh batches on its own. Neither a richer reward nor a drifting learner rescues the held correction: a rich-reward benchmark built to give the correction its best case is null at the largest drift measured in this paper (Appendix I.1), and a drifting transformer policy under a scarce reward loses by a small margin at every deadline, turning positive in sign only when the update is so aggressive that PPO itself diverges (Appendix I.4). The two failures are independent: where drift is realistic there is nothing to repair, and where the reward retains signal, PPO absorbs the staleness on its own, whatever the drift. Setting σ2Tσ^2T Endpoint Δ (corr. −- PPO) Seed wins HGNN dispatcher, FJSP 10×510× 5, T=50T=50; correction held for the whole run Published regime (K=3K=3), two deadlines 3×10−53× 10^-5 final on-time −6.0-6.0, −8.6-8.6 p 4/604/60 Drift dial, hard deadline (reward floor) 1.31.3 final on-time −5.2-5.2 p 1/51/5 1515 +4.4+4.4 p 3/53/5 3434 +9.0+9.0 p 5/55/5 Drift dial, fair deadline (saturated) 1.71.7 final on-time +1.8+1.8 p 3/53/5 7.27.2 −3.8-3.8 p 3/53/5 22.522.5 −3.2-3.2 p 2/52/5 Rich graded reward (resting windows) 0.70.7 AUC −0.080-0.080 1/51/5 38.838.8 −0.039-0.039 2/52/5 60.760.7 −0.027-0.027 3/53/5 Acquisition, hard deadline, fresh seeds 3434 early AUC −0.019-0.019 8/168/16 Transformer pointer policy, three-machine bottleneck flow shop, J=12J=12; correction held Dense makespan reward 1.381.38 AUC n.s. 9/169/16 Tight deadline, floor 0.140.14 (scarce) 1.381.38 AUC −0.062-0.062 5/165/16 floor 0.350.35 −0.034-0.034 6/166/16 floor 0.560.56 −0.012-0.012 5/155/15 Update dial D1 (PPO final 0.950.95) — AUC −0.067-0.067 7/167/16 D2 (PPO final 0.470.47) — −0.045-0.045 8/168/16 D3 (PPO final 0.300.30) — +0.122+0.122 9/169/16 Table 15: Held-correction results at and beyond realistic operating points. Δ is the paired, per-seed difference (corrected minus PPO) on the stated endpoint; seed wins count paired seeds favoring the correction. Drift σ2Tσ^2T is measured on the rollout policy after one full K-epoch update, before training, and was not recorded for the transformer update-strength dial. Details, the sizing rule for α, and the registered endpoints are in Appendices I.1 and I.4. Empirical test: the drift dial. We tested the correction on flexible job-shop scheduling (FJSP, 10×510× 5, binary on-time terminal reward [Cmax≤c⋅C∗]1[C_ ≤ c· C^*], HGNN dispatching policy of Song et al. [16], horizon T=50T=50), in both the free-order (DAG) protocol and the canonical-order (tree) protocol of Appendix B. At the published training regime (lr 2×10−42× 10^-4, clip 0.20.2, K=3K=3 reuse epochs) the correction loses to PPO in every cell of both protocols; Table 15 lists the canonical-order cell at α=0.03α=0.03 and the count of paired comparisons won. A direct measurement says why: the per-step log-ratio variance between the data-collecting and updated policy, measured after a full K-epoch update, is σ2≈5×10−7σ^2≈ 5× 10^-7, i.e. a prefix log-ratio of magnitude ≈0.005≈ 0.005 over the whole episode. The staleness that the correction reweights for is absent — the omitted term is measured to be ≈0≈ 0 — while the credit-routing channel still pays its α⋅Tα· T variance cost on a sparse binary signal. We therefore turned the drift dial — raising the learning rate 1010–30×30×, widening or removing the clip, and setting K=12K=12 — producing three settings whose measured drifts (Table 15) sit five to six orders of magnitude above the published regime; PPO’s own performance falls from 0.960.96 to 0.050.05–0.110.11, confirming that the staleness bias is real. At each setting the correction strength was frozen before training by the rule α=min(1, 1/(Tσ2))α= (1,\,1/(Tσ^2)) from the measured drift, and both arms share all hyperparameters and paired seeds. The registered readout, the paired final on-time difference, is monotone in measured drift and crosses zero, with every paired seed won at the highest drift (Table 15; Figure 7); the pre-registered continuous secondary endpoint, mean makespan gap to C∗C^*, agrees there on every seed (0.3420.342 vs. 0.3950.395). The absolute on-time levels at these settings sit near the floor (0.050.05–0.150.15), so we read the result as a sign-and-ordering finding rather than an effect-size estimate. At the lowest drift the sizing rule licenses a near-full correction (α=0.74α=0.74), which loses. A registered follow-up retested the same three training regimes away from the reward floor, at a deadline recalibrated (by a PPO-only pilot, blind to the corrected method) so that all settings train into the 0.550.55–0.950.95 on-time range; the drift re-measured at that deadline is lower (Table 15). There the result is a null: all three paired differences are within seed noise, the secondary endpoint agrees, and the strong-correction arm no longer loses either (α=0.58α=0.58 at the lowest drift). Figure 7 overlays both regimes: with plentiful reward signal, PPO recovers from stale data within a few updates on its own. The fair-deadline null itself carries a caveat that bounds how much either method could have shown there: the binary reward saturates at initialization. At the recalibrated deadline the untrained sampling policy already succeeds on 75%75\% of instance–samples (per-instance range 0.270.27–0.970.97), and the training curves (Figure 6) show no extended learning phase — both methods reach their operating level within the first ∼10 \!10–3030 iterations, peak early, and under the drift settings erode from that peak at matched rates rather than climb. Meanwhile the continuous quality metric shows both plateauing at a mean makespan gap of ≈0.35≈ 0.35 above optimal, versus ≈0.13≈ 0.13 reachable at published hyperparameters: the indicator reward stops registering schedule quality long before quality is good, so past the first few updates it provides no gradient toward better schedules for either method to exploit. The binary on-time reward in this problem class thus has a narrow informative band — starved at the hard deadline under drift, saturated at the fair one — and endpoint differences at the fair deadline are dominated by seed noise around an early-attained plateau. 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≈ 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 ± s.e.) against the drift measured at each training regime before launching, σ2Tσ^2T (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. A rich-reward benchmark built for the correction — and a null. A third experiment gives the correction its best case with an informative signal, to test whether the fair-deadline null was an artifact of the indicator reward: FJSP with resting-time windows (a hard minimum lag between consecutive operations of a job, enforced by the environment; a soft maximum lag whose violation is measured), and a graded terminal reward R=[V=0]−(Cmax−C∗)/C∗−V/C∗R=1[V=0]-(C_ -C^*)/C^*-V/C^* combining a feasibility bonus, the normalized makespan gap, and the normalized violation sum V. Missing a window is a delayed consequence of early machine-allocation decisions — the credit-routing structure the correction targets. The benchmark was difficulty-calibrated by a registered two-stage pilot (untrained feasibility in [0.05,0.40][0.05,0.40]; then PPO-only learnability and headroom at 200 iterations), and the confirmatory run registered sample efficiency (paired per-seed AUC of greedy validation reward) as the primary endpoint, with α frozen from probes measuring the two largest drifts of the project, plus a third setting pre-declared as a no-drift control (Table 15). The result is a null across the board: the paired AUC difference is negative at all three settings, nowhere near the registered criteria, with final-level secondaries agreeing. No acquisition-phase advantage even under scarce signal. An exploratory cut of the hard-deadline data suggested that the held correction also learns faster in the starved regime (corrected arms at ∼2× 2× PPO’s on-time rate within the first 5050 iterations at the highest-drift setting; 4/54/5 seeds, +0.18+0.18 early-phase AUC, short of significance). A registered confirmation on 1616 fresh paired seeds — everything else frozen verbatim: pool, deadline, hyperparameters, α=0.03α=0.03 — returned seed wins at chance and a mean slightly below zero (Table 15); the fresh seeds’ PPO-only early level itself differed from the original seeds’ by a factor of two. The held correction has no confirmed acquisition-phase advantage. Among the held-correction experiments of this subsection, the correction’s demonstrated value is survival under scarce signal with stale data: holding an already-learned policy against drift erosion; the warmup schedule of Appendix I.5 is a different device. Under the operating-point hypothesis of Section 8, these nulls sit three orders of magnitude below the testbed in N/T2N/T^2 (Eq. 14). I.2 Positive controls: the mechanism and its implementation are sound Free-choice positive control. A control rules out a bug in the correction implementation as the cause of the scheduling nulls. It runs the same correction code (correction_factor, α=0α=0 recovering PPO bit-identically) on an environment stripped to the LM/toy structure: T free K-way choices with the two-branch reward read from the first and last chosen actions, a small policy that must learn the prefix dependence (bag-of-prefix embeddings, no direct index on the branch symbol), and a GRPO group-relative baseline. Two ingredients decide whether the correction’s benefit appears, both established elsewhere in this paper: the optimizer must be N-SGD (Adam absorbs part of the effect; Appendix G), and the run must sit in the dead-branch escape regime, primed toward a dead branch it must escape. In that regime the correction rescues runs from the absorbing dead-branch trap, with several full rescues and no seed harmed (Table 16, first row; Figure 8). The control isolates the boundary. The same code reproduces the win the moment the environment and learner match the toy, so the scheduling non-reproduction lies in the environment (a coupled, constraint-driven dispatch process whose terminal outcome, the makespan-determining job, is emergent rather than chosen) or in the learner (a graph network with a value critic under Adam, rather than a sequence model under N-SGD with a group baseline), not in the mechanism or its implementation. 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α=0, blue) and the prefix correction (α=0.5α=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-only ablation. We vary only the environment toward scheduling while freezing the learner, optimizer, group baseline, FATAL dead-branch regime, and every hyperparameter, to ask which scheduling property (if any) removes the win. Two env modifications move the free-choice task toward scheduling: an emergent terminal, where the reward reads the modal symbol over the whole trajectory (the analogue of the makespan-determining job) rather than a directly chosen last token; and coupling, where a chosen symbol is masked as “busy” for a fixed number of steps so the action set shrinks and changes, the constraint that prevents freely piling work onto the target. Table 16 reports the paired advantage (sign test on non-tied seeds) at each rung. env (learner/optimizer fixed) size PPO AUC corr. Δ sign test free (chosen terminal) T=8T=8 0.160.16 +0.19+0.19 10/010/0, p=0.001p=0.001 emergent (whole-traj. terminal) T=8T=8 0.130.13 +0.11+0.11 8/18/1, p=0.02p=0.02 emergent, longer horizon T=12T=12 0.070.07 +0.21+0.21 15/015/0, p<10−4p<10^-4 coupled (busy =2=2) T=8T=8 0.280.28 +0.10+0.10 10/310/3, p=0.05p=0.05 coupled, strong (busy =3=3) T=8T=8 0.460.46 −0.03-0.03 8/118/11, p=0.82p=0.82 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. The advantage tracks whether a hard credit-routing problem is preserved, not emergent outcomes or coupling per se. With the correction code and the environment structure both excluded, the learner (T=50T=50 graph network) and optimizer (Adam with a value critic, low measured drift) remain as the operative cause, consistent with the N/T2N/T^2 prefactor and the optimizer ablations. I.3 The reward boundary: why the win does not transfer to realistic objectives Mapping the boundary. Holding the learner and optimizer at the winning configuration (N-SGD, group baseline), we asked directly what reward recovers the win on a scheduling task, and mapped the boundary by construction. A single-machine on-time objective is greedily solvable (Jackson’s rule) and yields nothing; a two-machine flow-shop with time-lags and varying, observed instances is null because an observing policy reads off which jobs are critical and applies a priority rule. Hiding the criticality does not recover it either — and an all-jobs-on-time reward makes the feasible set exponentially small, so both methods starve equally (the correction needs some rewarded trajectories to route credit from). Decomposing the winning two-branch reward pinpoints why: it is sharp on one directly chosen early action whose “liveness” the policy must discover, and dense given that action — a hard cliff followed by a broad rewarded basin, with untrained success ≈0.5×0.25=0.125≈ 0.5× 0.25=0.125. The closest scheduling analogue is two orders with a tight deadline: one decisive early action (who runs first) and a cliff (the lag-critical order misses if it is not first). There the correction does help, directionally and consistently (Figure 10A: paired Δ +0.004+0.004, 5/05/0 non-tied seeds, p=0.03p=0.03, never harmful) — the structure and sign transfer. But the magnitude does not, and a second experiment shows why it cannot: adding a second binding condition (both orders on tight deadlines) to deepen the trap makes the feasible fraction jump from 00 to 0.680.68 as the deadline loosens (Figure 10B), with no ≈0.125≈\!0.125 regime in between. Two binary decisions quantize feasibility to 0,12,1\0, 12,1\; the two-branch depth 12×14 12× 14 requires a second decision with four options, i.e. four or more orders — at which point the decisive structure distributes across a contention-mediated permutation and no single early action carries the credit. Scheduling thus forces a choice: two orders give the single decisive action but only shallow, quantized depth; four-plus orders give the depth but distribute the action. The single-decisive-action structure and the trap depth cannot be had together without constructing the reward by hand, as the two-branch reward is. A held correction’s boundary is therefore that it pays only where a reward isolates a single decisive early commitment, sharp enough to trap yet dense enough to escape, whose liveness is unobservable — a configuration realistic scheduling objectives do not admit. 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 Δ +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. I.4 A drifting transformer learner does not rescue it Transformer pointer policy. The scheduling nulls above all used the HGNN dispatching policy, whose pooled graph representation barely moves per update (measured σ2T≈3×10−5σ^2T≈ 3× 10^-5 at published reuse) — which leaves open whether they reflect a low-drift learner rather than the domain. We replaced the graph network with a transformer pointer policy (self-attention encoder, autoregressive attention decoder) on an NP-hard multi-machine task — a three-machine permutation flow shop (F3∥Cmax\|C_ ) with a bottleneck middle machine, 1212 jobs, varying instances, N-SGD, and a proper GRPO group baseline (G rollouts of the same instance). The transformer drifts: σ2T=1.38σ^2T=1.38 at K=12K=12, more than four orders of magnitude above the HGNN. The correction still does not win. Under a dense makespan reward it is a wash; under the scarce tight-deadline reward, the only regime where a held correction has helped here (Appendix I.1), swept across three on-time floors, it consistently loses by a small margin (Table 15; Figure 11). At every setting PPO climbs smoothly from the on-time floor to ≈0.97≈ 0.97 and the corrected curve tracks just below it, noisier, paying the αTα T variance premium with no stale-state bias to buy back: a competent transformer learns to schedule well, and the “scarce” reward is scarce only at initialization. A held correction helps only when PPO is stuck in an absorbing trap that pins the reward near zero, and nulls or loses whenever PPO can climb; the two-branch/FATAL construction produces such a trap, and realistic scheduling objectives, with continuous progress signal, do not. The drift number makes the same point quantitatively: σ2T=1.38σ^2T=1.38 is real drift but an order of magnitude below the σ2T≈15σ^2T≈ 15–3434 at which the drift-dial crossover fires, and reaching that band on the transformer requires raising the learning rate and loosening the clip until the update is near-divergent. Dialing the update strength up through three settings (D1: lr 0.25lr\,0.25, clip 0.50.5, K=24K=24; D2: 0.35/0.6/300.35/0.6/30; D3: 0.45/0.8/400.45/0.8/40; 1616 paired seeds each), the correction’s Δ moves monotonically with drift and crosses zero at D3, exactly where PPO can no longer climb (Table 15). The crossover is directional, not significant, but it reproduces the HGNN’s drift-dial crossover on a different architecture: the threshold is a property of the training regime, not of the learner. 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. I.5 The win in detail: warmup, reuse, horizon, and dose 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 (α on for 5050 iterations then off, orange) climbs above PPO (blue) early and stays ≥ it, while holding a fixed α the whole run (red) sags below PPO late. Dotted line marks the off-switch. (B) Δ vs. warmup length W 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 Δ over reuse only vs. deadline (±2± 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| _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 r are in the panel titles; per-configuration r in Table 19. PPO Corrected vs. PPO Reuse only vs. PPO Correction’s marginal: corrected −- reuse only Task / deadline n final Δ seeds p Δ seeds p Δ seeds p Single-bottleneck flow shop, J=12J=12 (easy); K=30K=30 for the first W=50W=50 iterations, then standard K c=1.02c=1.02 1616 0.980.98 +0.087 +0.087 / 14/16 0.002 0.002 +0.064 +0.064 / 14/16 0.002 0.002 +0.023+0.023 10/1610/16 0.2270.227 Seven-machine flow shop, J=20J=20, three bottlenecks (hard); same K=30K=30 warmup c=1.06c=1.06 2424 0.990.99 +0.009 +0.009 / 19/23 0.001 0.001 −0.009-0.009 12/2312/23 0.5000.500 +0.018 +0.018 / 15/21 0.039 0.039 c=1.05c=1.05 4848 0.890.89 +0.034 +0.034 / 41/48 <− <10^-4 −0.005-0.005 27/4827/48 0.2350.235 +0.039 +0.039 / 38/48 <− <10^-4 c=1.04c=1.04 2424 0.790.79 +0.114 +0.114 / 22/24 <− <10^-4 +0.026 +0.026 / 17/24 0.032 0.032 +0.087 +0.087 / 20/24 0.0008 0.0008 Disjunctive job shop, 88 jobs, 55 machines, T=40T=40; same K=30K=30 warmup c=1.15c=1.15 66 0.530.53 +0.040+0.040 3/63/6 0.6560.656 +0.033+0.033 2/52/5 0.8120.812 +0.006+0.006 2/62/6 0.8910.891 c=1.10c=1.10 66 0.570.57 +0.100+0.100 4/64/6 0.3440.344 −0.264-0.264 0/60/6 1.0001.000 +0.364 +0.364 / 6/6 0.016 0.016 c=1.05c=1.05 66 0.410.41 −0.110-0.110 0/60/6 1.0001.000 −0.060-0.060 3/63/6 0.6560.656 −0.050-0.050 3/63/6 0.6560.656 Table 17: The aggressive-reuse warmup recipe: K=30K=30 for the first 5050 iterations, then plain PPO at the standard K, with the correction (corrected) or without it (reuse only). Δ 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 p 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. PPO Corrected vs. PPO Warmup length n final Δ seeds p W=25W=25 9696 0.970.97 +0.026 +0.026 / 59/95 0.012 0.012 W=50W=50 9696 0.970.97 +0.028 +0.028 / 58/94 0.015 0.015 W=75W=75 9696 0.970.97 +0.014+0.014 52/9652/96 0.2380.238 held, whole run 9696 0.970.97 −0.023-0.023 42/9642/96 0.9080.908 Table 18: Warmup length at the standard reuse count: bottleneck flow shop, J=12J=12, transformer policy, the correction on for the first W iterations and then plain PPO (“held”: on for the whole run); deadlines c∈1.0,1.02c∈\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. Warmup schedule. α=α0α= _0 for the first W iterations, then α=0α=0 (plain PPO); bottleneck transformer, 4848 seeds per deadline, c∈1.0,1.02c∈\1.0,1.02\, pooled in Table 18. Per deadline, the W=25W=25 and W=50W=50 warmups remain significant at c=1.02c=1.02 alone (p=0.030p=0.030 and 0.0390.039). The second-half Δ is −0.06-0.06 to −0.09-0.09 under a held α and within 0.020.02 of zero once α switches off (Figure 12). Aggressive reuse during the warmup, with a reuse-only arm. K=30K=30 for the first W=50W=50 iterations, then the standard K; the reuse-only arm runs the same schedule without the correction. On the easy task (single-bottleneck flow shop, 1616 seeds) the correction at the standard K gives Δ +0.024+0.024 over PPO, against the K=30K=30 values in Table 17. The hard task’s three bottlenecks sit at machines 1,3,5\1,3,5\. K-tolerance frontier (easy task). K held for the whole run, swept 44–128128 at clip 0.20.2 and 0.40.4, with the drift σ2Tσ^2T measured alongside (Figure 15). PPO is robust to reuse at clip 0.20.2 and fails only at K=128K=128 under clip 0.40.4; the corrected update sits at or below PPO at every K but one, while its drift climbs by five orders of magnitude across the sweep. Horizon sweep and calibration. Multi-bottleneck flow shop, J∈20,30,40,50J∈\20,30,40,50\ jobs (setting T), 1212 seeds each at fixed c=1.03c=1.03 (Table 19, first block; Figure 16). Because PPO’s final on-time rises with J at fixed c, the sweep partly conflates trajectory length with PPO’s AUC headroom. A PPO-only calibration (88 seeds, blind to the corrected arm, commit 3a3c0a1) therefore chooses, for each J, the deadline in a grid whose PPO final on-time is closest to 0.650.65, accepting it only inside [0.50,0.85][0.50,0.85]; J=50J=50 is excluded because its feasibility jumps from 0.250.25 at c=1.01c=1.01 to ≈1.0≈ 1.0 at c=1.03c=1.03 with no grid point in the band (Table 19, second block; Figure 17). Disjunctive job shop. Machine routes are drawn at random per job, T=J⋅M=40T=J· M=40, the same binary deadline reward, 66 seeds (Table 17, last block; Table 19, third block; Figure 13). At c=1.05c=1.05 PPO itself falls from 0.940.94 to 0.410.41 over training, with no within-group signal for GRPO. 1616 seeds at c=1.10c=1.10 would be needed before the magnitude is headlined. Dose regression. The dose of Section 6.2 is averaged over the warmup window per seed. Difficulty is partialled out by z-scoring dose and win within configuration before pooling the n=66n=66 points; the early-half correlation is positive in 55 of 77 configurations. The per-configuration correlations (Table 19; Figure 18) are point estimates on 66–1212 seeds and scatter widely; the early correlation is largest on the job-shop winning cell. A correlation does not by itself establish the dose as the cause, and the across-task dose–response without difficulty control is flat because PPO’s headroom caps the realised win. Replication across environments. The effect reproduces in sign and magnitude across a local 88-seed and a cloud 1616- and 4848-seed environment with different PyTorch builds. PPO Lead over PPO Marginal r(dose, win) Configuration n final first half second half Δ Dose early late Multi-bottleneck flow shop, horizon sweep at fixed c=1.03c=1.03 J=20J=20 1212 0.670.67 +0.115+0.115 +0.149+0.149 +0.178+0.178 3.753.75 +0.51+0.51 −0.19-0.19 J=30J=30 1212 0.570.57 +0.071+0.071 +0.050+0.050 +0.045+0.045 5.535.53 −0.39-0.39 +0.45+0.45 J=40J=40 1212 0.870.87 +0.083+0.083 −0.016-0.016 +0.021+0.021 5.415.41 +0.67+0.67 −0.12-0.12 J=50J=50 1212 0.980.98 +0.092+0.092 +0.003+0.003 +0.049+0.049 5.275.27 +0.74+0.74 −0.48-0.48 Same task, deadline calibrated per J to hold PPO’s ceiling fixed J=20J=20, c=1.035c=1.035 88 0.710.71 +0.097+0.097 +0.077+0.077 +0.109+0.109 3.083.08 +0.03+0.03 −0.38-0.38 J=30J=30, c=1.03c=1.03 88 0.750.75 +0.092+0.092 +0.055+0.055 +0.192+0.192 4.714.71 +0.07+0.07 +0.09+0.09 J=40J=40, c=1.025c=1.025 88 0.710.71 +0.138+0.138 −0.092-0.092 +0.158+0.158 5.965.96 −0.19-0.19 −0.55-0.55 Disjunctive job shop, T=40T=40 c=1.05c=1.05 66 0.410.41 −0.023-0.023 −0.196-0.196 −0.050-0.050 7.767.76 +0.34+0.34 −0.62-0.62 c=1.10c=1.10 66 0.570.57 +0.055+0.055 +0.144+0.144 +0.364+0.364 6.116.11 +0.79+0.79 +0.54+0.54 c=1.15c=1.15 66 0.530.53 −0.023-0.023 +0.102+0.102 +0.006+0.006 3.953.95 −0.68-0.68 +0.48+0.48 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 Δ is over the reuse-only K=30K=30 arm; dose is the prefix bias ∑t|bt| _t|b_t| on that arm, averaged over the warmup window; r 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 J by a PPO-only calibration (see text); J=50J=50 has no deadline in the calibration band and is excluded. Figure 15: K-tolerance frontier on the easy task: reuse opens no window for the correction. Reuse K held the whole run, swept 44–128128, at clip=0.2clip=0.2 (solid) and 0.40.4 (dashed). (A) Final greedy on-time vs. K: PPO (blue) is robust — it peaks at K=64K=64 and barely drops by K=128K=128 at clip=0.2clip=0.2, failing only at K=128K=128/clip=0.4clip=0.4 — and the corrected update (orange) sits at or below PPO at nearly every K. (B) Drift σ2Tσ^2T (median, log scale) climbs steeply with K and explodes to ∼106 \!10^6 at K=128K=128/clip=0.4clip=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 1c), not merely high K. Figure 16: Faster early, same endpoint — the sample-efficiency win across horizon and a second task family. Learning curves (mean ±2± 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 J the deadline c 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. J at the held ceiling: positive and roughly flat. (B) Measured prefix bias vs. J: 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 r 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 J. (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. Appendix J Computing infrastructure and assets All experiments ran on Google Cloud virtual machines and a local workstation. The transformer testbed experiments and the pretrained-LM study ran on g2-standard-8 machines with one NVIDIA L4 GPU each; the tabular testbed, the derivation checks, and the scheduling experiments ran on CPU only, on multi-core cloud machines (c2-standard family) and locally. Scheduling seeds were sharded across machines and the result files merged; because random-number streams differ across software environments, cross-environment replications agree in sign but not exactly in magnitude (Appendix I.5). The pretrained model is Qwen2.5-0.5B [28], released under the Apache 2.0 license. The HGNN dispatcher builds on the public implementation of Song et al. [16], released under the Apache 2.0 license and included, with our modifications, in the code supplement. All scheduling instances are generated synthetically, with that implementation’s instance generator for the flexible job shop; no external dataset is used.