Paper deep dive
Free Everywhere, Exact on Trees: PPO's Dropped Correction Buys Sample Efficiency Under Aggressive Reuse
Nima H. Siboni
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
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.39634v1
- Canonical: https://arxiv.org/abs/2609.39634v1
Trouble viewing inline? Open PDF directly →
Full Text
136,688 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 — Trust Region Policy Optimization (TRPO) [13], Proximal Policy Optimization (PPO) [14], and Group Relative Policy Optimization (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 (Section 3; Appendix B treats the path-merging case). 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 (Section 3.2). 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, and both are silent at the rollout policy under a conditionally centered advantage. Away from the rollout policy, 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 to change — the sampling loop can trap the policy. The size of the effect depends on how far the policy drifts per update, which is measurable from a short pilot run (Section 4). We test these claims in two settings with different roles. An exactly enumerable sequence-model testbed, with a ladder of rewards that switch the conditions on one at a time, 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 (Section 5). Constructive scheduling is the application: samples there are expensive, policies are trained by reusing each rollout batch, 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 (Section 6). 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 We consider sequential decision processes with one structural property. 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 Markov decision process (MDP) many histories lead to the same state, and the state does not reveal which was taken. A robotic hand is the typical non-injective case; its state, the current joint configuration, is reachable by many motion paths and records where the hand is, not how it got there. 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, so that distinct histories remain distinct states. History-injectivity makes the reachable state graph a tree rooted at the initial state: no two paths merge, so every state is reached by exactly one history; 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, which is the form both settings below take. Determinism is a convenience of those settings, not a requirement; the derivation of Section 3 uses only injectivity. Autoregressive sequence models satisfy the condition natively. For a prompt x and a token sequence y, 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; distinct token sequences are distinct prefixes. This covers any autoregressive generator over discrete tokens that is fine-tuned with reinforcement learning — language, code, symbolic mathematics, and protein or molecular sequences (e.g. ProtGPT2 [3]). It also covers agentic generation in which the environment inserts tokens the policy did not emit, such as tool outputs: those insertions are stochastic transitions that the context records, so the prefix stays injective and the correction runs over the policy’s own tokens. The enumerable testbed of Section 5 is a sequence model of this kind. Constructive combinatorial optimization satisfies it under one further convention. In the constructive paradigm of neural combinatorial optimization a policy builds a solution one element at a time [1, 5]. A canonical construction order is a fixed rule for which slot is decided next; in scheduling, for example, always the machine that next becomes free, under a fixed tie-break. Under such an order each partial solution can be constructed in only one way, so the state recovers its history and the process is history-injective. The convention does not restrict the policy: it still chooses the content of every decision, only not its position. The scheduling experiments of Section 6 use this convention throughout. 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) Here dπ,t(s)=Pπ(St=s)d_π,t(s)=P_π(S_t=s) is the time-t state-visitation distribution of a policy π. Aπold=Qπold−VπoldA_ _old=Q_ _old-V_ _old is the old policy’s advantage function, the difference of its action- and state-value functions, and the only advantage function in this paper. Both the state and the action are drawn from the improved policy π~ π, which cannot be rolled out before the update produces it. Importance sampling applied twice, once to the state draw and once to the action draw, reweights the expectation onto rollouts of πold _old: η(π~)=η(πold)+∑t=0∞γtst∼dπold,t,at∼πold[dπ~,t(st)dπold,t(st)⏟Rtsπ~(at∣st)πold(at∣st)⏟rtAπold(st,at)].η( π)=η( _old)+ _t=0^∞γ^t\,E_s_t d_ _old,t,\,a_t _old\! [\; d_ π,t(s_t)d_ _old,t(s_t)_R^s_t\; π(a_t s_t) _old(a_t s_t)_r_t\;A_ _old(s_t,a_t) ]. (3) 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, which approximates dπ~,td_ π,t by dπold,td_ _old,t. They drop it because dπ~,td_ π,t is not computable in general. Under the history-injectivity of Section 2, 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. Behind (4) is a collapse to a single term (Appendix B gives the step-by-step derivation). 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 one taken. That history is the same for both policies, and so are the kernels along it, so numerator and denominator of RtsR^s_t share every kernel factor; the kernels cancel, and what remains is the product of per-step policy ratios in (4). Determinism plays no part: it would make each kernel an indicator, but 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) is computable from the log-probabilities in hand, and because the transition kernels cancel along any realized path, πold[Wt∣st]=RtsE_ _old[W_t s_t]=R^s_t: the corrected surrogate has the right expectation, by standard per-decision importance sampling [10], and the conditional statement is the identity behind marginalized importance sampling [7, 27]. Tree structure adds the pointwise statement (4), 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 by leaving one path per state (Appendix B treats the merging case). Substituting (4) into (3) merges the state and action ratios into a single product through position t, 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. Applied without modification, (5) is unbiased but high-variance. Write ℓi=logπ~(ai∣si)−logπold(ai∣si) _i= π(a_i s_i)- _old(a_i s_i) for the per-step log-ratio. Write σ2=1t∑i<t[Var(ℓi∣si)]σ^2= 1t _i<tE[Var( _i s_i)] for its average per-step conditional variance. Then logRts=∑i<tℓi R^s_t= _i<t _i accumulates one term per step, and because the centered terms are uncorrelated across steps their variances add, Var(logRts)≈tσ2Var( R^s_t)≈ tσ^2.11 1 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. The variance of RtsR^s_t itself therefore grows exponentially in the horizon: the classical trajectory-IS problem [10, 17], arising here in the policy update rather than in value estimation. The design task is therefore a family of corrections between the two, trading bias against variance. 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 through position t: named for how it is computed, a sum along the prefix, with the superscript recording what it equals, the log of the state-visitation ratio. Each surrogate replaces RtsR^s_t by a correction factor gt(Lts)g_t(L^s_t), chosen in Table 1, giving the corrected ratio r~t=gt(Lts)exp(ℓt) r_t=g_t(L^s_t)\, ( _t). Writing π~=πθ π= _θ for the trainable policy, r~t r_t enters the usual clip-min objective ℒPC(θ)=t[min(r~tA^t,clip(r~t,1−ϵ,1+ϵ)A^t)],L^PC(θ)=E_t\! [ \! ( r_t\, A_t,\;clip( r_t,1-ε,1+ε)\, A_t ) ], (6) with ϵε the PPO clip range and tE_t the average over sampled positions. Here A^t A_t is the advantage estimate at position t, computed once from the rollout batch and held fixed across update epochs. As a function of the sampled data alone it is constant with respect to θ; we drop the hat only for the exact advantage Aπold(st,at)A_ _old(s_t,a_t). Table 1 lists the correction factors we evaluate; PPO is the gt=1g_t=1 row. Variant gt(Lts)g_t(L^s_t) Notes PPO 11 Biased — ignores RtsR^s_t; no added variance Full exp(Lts) (L^s_t) Unbiased; full trajectory-IS variance Tempered exp(αLts) (α L^s_t), α∈[0,1]α∈[0,1] Interpolates PPO (α=0α=0) ↔ full (α=1α=1) Truncated exp(∑i=max(0,t−k)t−1ℓi) \! ( _i= (0,t-k)^t-1 _i ) Corrects only the last k steps Clipped exp(clip(αLts,−c,c)) (clip(α L^s_t,-c,c)) Hard cap in log space Table 1: Correction factors gtg_t evaluated in this paper. Each per-position expectation in (3) is the position-t marginal of a trajectory τ∼πoldτ _old, so the identity is equivalently a single expectation over rollout trajectories: η(π~)−η(πold)=τ∼πold[∑tγtRtsrtAπold(st,at)].η( π)-η( _old)\;=\;E_τ _old\! [\, _tγ^t\,R^s_t\,r_t\,A_ _old(s_t,a_t) ]. (7) The bracket, evaluated on a sampled trajectory, is an unbiased single-trajectory estimator of the improvement. Each family member replaces RtsR^s_t by its correction factor and the exact advantage by the estimate: L^(τ)=∑tγtgt(Lts)rtA^t. L(τ)\;=\; _tγ^t\,g_t(L^s_t)\,r_t\, A_t. (8) 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. Section 5.2 measures the trade for every variant. 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. 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. The tempered family is the one we use throughout. 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 (related to, but distinct from, the clipped variant’s position-independent cap c on αLtsα L^s_t); each is one point of Table 1 with a stabilizer, which the family turns into one setting of a knob. Which setting wins, under which conditions, is the question the rest of the paper takes up. 4 When the correction matters This section characterizes when the correction carries a signal worth its cost: where it enters the policy gradient, what reward structure makes the gradient difference systematic across states rather than noise, and when a better per-update gradient changes what training reaches, not only how fast. Each question yields one checkable condition on the task, C1 to C3 in Table 2, and the testbed of Section 5 switches them on one at a time. The conditions delimit progressively stronger regimes of systematic leverage, not necessary conditions. Nor is the trade monotone in α: at finite drift an interior member can carry a larger scalar bias and a lower variance than PPO at once, by partially cancelling PPO’s rare-prefix outliers (Section 5.2); only the endpoints are guaranteed, PPO’s bias and the full correction’s trajectory-IS variance. Two objects join those of Section 3.2. The score zi(θ)=∇θlogπθ(ai∣si)z_i(θ)= _θ _θ(a_i s_i) is the parameter direction that makes the sampled action aia_i more probable. Its sum over the steps before t, St(θ)=∑i<tzi(θ)S_t(θ)= _i<tz_i(θ), is the direction that makes the entire sampled prefix more probable. 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. The analysis of this section is of the unclipped surrogate; how the clipped objective (6) gates it is stated at the end. 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 the expected estimate πold[L^]E_ _old[ L] of (8). Subtracting PPO’s gradient from that of ℒtgL^g_t leaves Δtg ^g_t :=∇θℒtg−∇θℒtPPO := _θL^g_t- _θL^PPO_t (9) =π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 difference has exactly two parts. The first, the reweighting channel gt(Lts)−1zt\g_t(L^s_t)-1\\,z_t, is PPO’s own position-t gradient rescaled by how much the updated policy has raised or lowered the probability of the sampled prefix. The second, the credit-routing channel gt′(Lts)Stg_t (L^s_t)\,S_t, has no counterpart in PPO: through StS_t it routes the position-t advantage backward to the earlier actions that produced the prefix. By history-injectivity the state sts_t identifies the prefix, so conditioning on sts_t freezes the prefix-determined factors gt(Lts)g_t(L^s_t) and StS_t while the action-dependent factors remain random. The inner average, over everything after sts_t, replaces those factors by two conditional means, hθ(st):=πold[rtA^tzt∣st],A¯πoldπθ(st):=πold[rtA^t∣st],h_θ(s_t):=E_ _old[r_t A_tz_t s_t], A_ _old _θ(s_t):=E_ _old[r_t A_t s_t], (10) where hθ(st)h_θ(s_t) is the average position-t gradient contribution collected at state sts_t, and A¯πoldπθ(st) A_ _old _θ(s_t) is the average of the old policy’s advantage under the updated policy’s action draw. The subscript names whose advantage, the superscript which policy draws the action: for the exact advantage the ratio rtr_t moves the draw from πold _old to πθ _θ, so A¯πoldπθ(st)=a∼πθ(⋅∣st)[Aπold(st,a)] A_ _old _θ(s_t)=E_a _θ(· s_t)[A_ _old(s_t,a)]. The outer average over the states πold _old visits then gives the gradient difference state by state: Δtg=st∼dπold,t[gt(Lts)−1hθ(st)+gt′(Lts)StA¯πoldπθ(st)]. ^g_t=E_s_t d_ _old,t\! [\g_t(L^s_t)-1\\,h_θ(s_t)+g_t (L^s_t)\,S_t\, A_ _old _θ(s_t) ]. (11) At θ=θoldθ= _old, the first gradient step after a rollout, both channels of (11) 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. The first condition is that the reward must still be undecided late (C1). Each term of (11) 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.22 2 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. The second condition is that the reward must depend on the prefix (C2). At a fixed position, (11) 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. C2 is checkable in practice, because the cancellation it forbids 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). (12) As a covariance of quantities every rollout batch already contains, btb_t is measurable in any training run; Section 6 measures it, summed over positions, as the bias dose against which the correction’s win is correlated. It is a scalar summary: the vector difference (9) is what moves the parameters. 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. Read as a nested checklist, the conditions predict: • C1 inactive (early-decided reward): little leverage; the credit-routing channel carries only what imperfect centering leaves. • C1 without C2 (late-decided, prefix-independent reward): a better estimator, lower bias and MSE, but unchanged training, since the contributions cancel in the update. • C1 and C2 without C3 (prefix-dependent reward, recoverable loop): faster learning to the same endpoint. • C1–C3 all active: a changed probability that a run succeeds. 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 2: 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. 5 Verifying the mechanism on an enumerable testbed 5.1 Testbed and reward ladder This section is an instrument for Section 4, not an application: it checks that the correction is what Section 3 says it is, which needs quantities computed exactly, and that C1–C3 predict where a partial correction wins, which needs a comparison in which nothing varies but the correction. The testbed is an exactly enumerable autoregressive MDP with vocabulary size V=4V=4; the estimator diagnostics and the control rewards use horizon T=6T=6, the two-branch learning experiments T=8T=8. Two policy representations run on it: a small causal transformer (793793k parameters), trained from sampled rollouts, and a tabular softmax with one logit per prefix–token pair, which admits exact η, exact KL, and exact backward-induction advantages. On the tabular policy the correction can therefore be verified as an identity, to floating-point precision, rather than estimated. The compared methods differ only in the correction factor gt(Lts)g_t(L^s_t): PPO, the full correction, tempered variants over a grid of α, and truncated and clipped variants, all members of the family of Section 3.2 sharing the objective, the advantage estimation, and the optimizer (grids and settings in Appendix D). Observed differences are therefore attributable to the correction alone. Four rewards form a ladder in which the conditions of Section 4 are switched on one at a time. The first three are controls, each stopping short of either the full condition set or measurable training outcomes; the fourth, the two-branch reward, stops short of neither and is the principal learning task: • 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. • Two-branch. The principal learning task, R(y0:T−1)=1if y0= and yT−1=,1if y0= and yT−1=,0otherwise,R(y_0:T-1)= cases1&if y_0= A and y_T-1= B,\\ 1&if y_0= C and y_T-1= D,\\ 0&otherwise, cases (13) activates all three conditions: the reward stays contested until the terminal token (C1); the correct terminal action depends on the first-token branch, preventing cancellation across prefixes (C2); and a wrong early commitment can make rewarded continuations disappear from a finite batch (C3). And unlike the sparse match, the two-branch reward keeps rewarded trajectories frequent enough across its two branches (untrained success rate 1/81/8) for training outcomes to be measurable. 5.2 Estimator diagnostics on fixed policy pairs The first experiment measures the estimators before any training, on fixed policy pairs, and asks whether they behave as Section 4 predicts. Each pair sets the rollout policy πold _old against a candidate πθ _θ obtained by perturbing its logits, so the perturbation magnitude dials the policy drift directly; we measure drift as D¯KL(πold,πθ) D_KL( _old, _θ), the KL divergence from πold _old to πθ _θ averaged over the states πold _old visits. The tested range, 4×10−54× 10^-5 to 0.330.33, spans the drift that accumulates over the reuse epochs of one update or on stale data. Because the testbed is enumerable, every quantity that follows is computed exactly, with no rollout sampling. Each estimator is scored first as an estimator: the bias, variance, and mean squared error (MSE) of the single-trajectory estimate L L (8), Bias[L^] [ L] =πold[L^]−(η(πθ)−η(πold)), =E_ _old[ L]- (η( _θ)-η( _old) ), (14) Var[L^] [ L] =πold[(L^−πold[L^])2], =E_ _old\! [ ( L-E_ _old[ L] )^2 ], (15) MSE[L^] [ L] =πold[(L^−(η(πθ)−η(πold)))2]=Bias[L^]2+Var[L^], =E_ _old\! [ ( L-(η( _θ)-η( _old)) )^2 ]=Bias[ L]^2+Var[ L], (16) 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 D.2 reports the sweeps over all drift magnitudes and both control rewards, and Table 3 and Figure 1 the full variant grid at this operating point, D¯KL≈0.33 D_KL≈ 0.33. 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, and its update direction tracks the exact gradient. At D¯KL≈0.33 D_KL≈ 0.33 its variance is an order of magnitude above PPO’s and its normalized ESS falls to about a quarter (Table 3): the batch effectively shrinks to a quarter of its trajectories. PPO’s error is directional. Its bias is negligible and it has the lowest variance in the family, yet the cosine between its update and the exact gradient falls to 0.200.20 at the largest drift: PPO estimates the objective almost perfectly while pointing nearly orthogonally to it. That failure is invisible to bias- and variance-style diagnostics, and it does not average out with more data. The interior Pareto-dominates. Tempered α=0.25α=0.25 improves on PPO on both axes at once — a better direction (cos=0.53 =0.53 against PPO’s 0.200.20) and a lower MSE — because exp(0.25LT−1s) (0.25\,L^s_T-1) partially cancels the outlier contributions that PPO’s last-step ratio makes at rarely visited prefixes. Bias2 is negligible, so the MSE column of Table 3 is the variance, and the improvement lands at the interior minimum of Figure 1: a 32%32\% reduction in MSE. 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 3: Estimator diagnostics at D¯KL≈0.33 D_KL≈ 0.33 on the late-only reward, 2525 seeds; single-trajectory estimate L L (8). Bold marks the lowest MSE. Figure 1: Mean squared error MSE[L^]MSE[ L] (16) 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 3. 5.3 Training on the two-branch reward The per-update estimator advantage compounds across iterations, and the method classes order themselves as the diagnostics predict (Table 4). The tabular experiment isolates the direction effect: normalized stochastic gradient ascent (N-SGD) fixes the update magnitude, so the compared methods differ only in the direction of their updates. Under that control, the interior tempered and clipped variants break out of the initial plateau first, PPO follows, and the full and long-truncated corrections trail: tempered α=0.1α=0.1 solves the task by iteration 5050 and PPO by 7070 (per-seed results in Appendix E.1). The better direction is not a refinement but a 1.4×1.4× difference in time to solve the task. The transformer changes what the comparison measures. Trained from random initialization under N-SGD at =1.0 lr=1.0, its outcomes are bimodal (η≈0η≈ 0 or 11), so the estimator advantage appears as success rate rather than speed: tempered α∈0.05,0.1α∈\0.05,0.1\ succeeds on every seed, PPO on 7/107/10, and the full and long-truncated corrections on fewer still (Figure 2; Appendix E.2). The failed seeds show why the outcome is all-or-nothing: each commits to a wrong first branch within the first few gradient steps and never recovers — the sampling trap of C3. An adaptive optimizer attenuates the effect without erasing it, and it shifts the best variant toward clipping. Under Adam at =3×10−3 lr=3× 10^-3 the best variants are clipped (0.1,1.0)(0.1,1.0) and tempered α=0.1α=0.1, and the gap over PPO shrinks to roughly two thirds of its N-SGD size; a matched tabular ablation shows the same direction (Appendix E.4). At the aggressive =10−2 lr=10^-2 the ordering holds and the full correction collapses to no successful seed (Appendix E.3). Combining bias reduction with variance control is therefore the robust choice under adaptive optimization, and the full correction is fragile at aggressive learning rates. Method Tabular Transformer Transformer N-SGD, lr 0.30.3 N-SGD, lr 1.01.0 Adam, lr 3×10−33× 10^-3 iter. to η=1η=1 (n=3n=3) success rate (n=10n=10) success rate (n∈9,10n∈\9,10\) 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 gap 2020 iter. (1.4×1.4×) +30p+30\,p +19p+19\,p Table 4: Learning results on the two-branch reward. All runs use K=4K=4 epochs, 256256-trajectory rollouts, and 200200 iterations. The tabular column reports the iteration at which mean return reaches η=1η=1; transformer columns report the fraction of seeds with final η>0.5η>0.5. Bold marks the best entry per column; the lr =10−2=10^-2 Adam runs are in Appendix E.3. Figure 2: 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 4. 5.4 Transfer to a pretrained language model The speed effect transfers to a pretrained policy under Adam; the trap effect does not. Both claims are tested by fine-tuning Qwen2.5-0.5B on a rule-verifiable six-slot structured-record task whose rewards mirror the ladder (protocol in Appendix F); Table 5 collects the paired differences. The speed effect shows on the prefix-dependent two-branch reward: tempered α=0.10α=0.10 leads PPO by +6.7+6.7 p in mean Monte Carlo return over iterations 22–88, with every one of 1616 paired seeds favoring the correction. Across the method grid the gain is interior in α, peaking near α=0.10α=0.10 and collapsing at α=1α=1, where variance cancels the bias correction — the testbed’s interior-α profile, reproduced at pretrained scale. Two-branch reward Late-only falsifier Method Δ vs. PPO (p) seeds positive Δ vs. PPO (p) seeds positive 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 5: Pretrained-LM study (Qwen2.5-0.5B, Adam): paired difference against PPO in mean Monte Carlo return over iterations 22–88, the pre-registered rate endpoint, on the prefix-dependent two-branch reward and on the matched late-only falsifier. Confidence intervals and per-iteration curves are in Appendix F. The trap cell, which primes the policy onto the wrong branch, is not tabulated: all 1616 PPO seeds and all 1616 tempered seeds succeed, so it offers no success-rate comparison. The matched late-only falsifier asks whether that gain needs prefix dependence or only a delayed reward. Removing dependence on the first slot while keeping the delayed reward contracts the advantage to +1.9+1.9 p with per-seed signs at chance, and turns the full correction harmful on every seed (Table 5, right). The residual is small but not unexplained: its 95%95\% CI marginally excludes zero, and it has a mechanistic home in the pretrained model’s conditional prior, which is not exactly prefix-independent (Appendix F). Delayed reward alone does not justify the variance cost. The trap test primes the policy to start on the wrong branch of the two-branch reward and asks whether the sampling loop strands it there. It does not: every PPO seed succeeds. The trap mechanism requires a wrong commitment to make rewarded continuations vanish from the batch, which the toy MDP guarantees and a pretrained model at the 256256-rollout batch size does not — about 8.58.5 rewarded trajectories per batch survive the priming, and their advantage signal outweighs the biased-gradient drift from the first iteration. At realistic batch sizes the correction therefore changes learning speed rather than rescuing otherwise lost runs. The transfer is bounded on two sides: the synthetic rewards are exactly decided at known positions, which a realistic reward model is not, and the pretrained study is one model at 0.50.5B under one hyperparameter freeze. The practical case for the correction rests on the scheduling application that follows. 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, all built under the canonical construction order of Section 2, the convention that makes each partial schedule constructible in exactly one way and the correction therefore exact. A heterogeneous graph network (HGNN) dispatcher [16] or a transformer pointer policy constructs the schedule, over horizons of T=12T=12 to T=50T=50 decisions; the reward is either 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 (full protocols in Appendix G). The conditions of Section 4 may fail to hold here: terminal outcomes are emergent (the makespan-determining job is not a chosen token), action sets are constrained, and rewards often carry continuous progress signal. Two measurements organize the results. The first is the quantity we compare: the area under the learning curve (AUC) of the greedy validation on-time rate, the on-time rate of the argmax-decoded policy on held-out validation instances; Δ is the corrected-minus-control difference, paired by seed. Sign tests are exact binomial tests on the non-tied paired seeds, under the sidedness convention that holds throughout the paper: tests of pre-specified directional improvement hypotheses are one-sided in the predicted direction, and falsifier and null comparisons are two-sided. The second is drift, measured on the rollout policy after one full K-epoch update as σ2Tσ^2T, the per-step log-ratio variance of Section 3.1 accumulated over the horizon. Drift ties the results to the mechanism: it measures how much staleness each operating point actually accumulates. At realistic operating points a held correction is null to harmful, for two measurable reasons (Table 6). 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 G.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 G.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 G.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 6: 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 G.1 and G.4. 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 the bottleneck flow shop with the transformer policy, a warmup that applies the correction for the first W iterations and then runs plain PPO beats PPO on AUC at W=25W=25 and W=50W=50; holding the correction for the whole run loses, and too long a warmup dilutes the effect below significance (Table 7, first block). The second-half Δ , negative under the held correction, turns positive once α switches off: the early correction gains ground in the high-drift phase and the hand-off to PPO keeps it (Figure 3). PPO Corrected vs. PPO Control vs. PPO Marginal: corrected −- control Schedule / deadline n final Δ seeds p Δ Δ seeds p Bottleneck flow shop, J=12J=12, transformer policy; warmup of W iterations at the standard K; c∈1.0,1.02c∈\1.0,1.02\ pooled W=25W=25 9696 0.970.97 +0.026+0.026 59/9559/95 0.0120.012 — — — — W=50W=50 9696 0.970.97 +0.028+0.028 58/9458/94 0.0150.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 — — — — 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/1614/16 0.0020.002 +0.064+0.064 +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/2319/23 0.0010.001 −0.009-0.009 +0.018+0.018 15/2115/21 0.0390.039 c=1.05c=1.05 4848 0.890.89 +0.034+0.034 41/4841/48 <10−4<10^-4 −0.005-0.005 +0.039+0.039 38/4838/48 <10−4<10^-4 c=1.04c=1.04 2424 0.790.79 +0.114+0.114 22/2422/24 <10−4<10^-4 +0.026+0.026 +0.087+0.087 20/2420/24 0.00080.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 +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.364+0.364 6/66/6 0.0160.016 c=1.05c=1.05 66 0.410.41 −0.110-0.110 0/60/6 1.0001.000 −0.060-0.060 −0.050-0.050 3/63/6 0.6560.656 Table 7: Scheduling results under the warmup recipe. Δ 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. PPO final is plain PPO’s final on-time rate, which sets the headroom. First block: correction on for the first W iterations at the standard reuse count, then plain PPO (“held”: correction on for the whole run); 4848 seeds per deadline. Remaining blocks: correction on for W=50W=50 iterations at K=30K=30, then plain PPO; the control is the same K=30K=30 warmup without the correction, so the marginal column is the correction’s contribution beyond the reuse itself. We raise the reuse count K to 3030 during the warmup because reuse-induced policy drift is one of the two routes through which the correction acts (Section 4) and K is its cleanest practical lever. The lever is not pure: raising K also changes the optimizer work per batch and how often clipping engages, so a gain over PPO at high K does not by itself belong to the correction. The comparison arm is therefore a no-correction warmup at the same high K, and the marginal Δ , corrected minus this control, is what the correction contributes beyond the reuse itself. Aggressive early reuse pays with the correction on hard credit-assignment tasks, and does not without it. On a seven-machine flow shop with 2020 jobs and three spread-out bottlenecks, where competing bottlenecks make credit assignment non-myopic, reuse alone does not pay: the high-K control is null to negative against PPO at every deadline. The same reuse with the correction wins at every deadline, and the marginal Δ grows as the deadline tightens, reaching +0.087+0.087 at the hardest non-saturated deadline (Table 7, third block; Figure 4). The correction lets early batches be reused harder on problems where PPO alone cannot. On an easy task no amount of reuse opens a window for the correction. On the single-bottleneck flow shop the same K=30K=30 warmup widens the gap over PPO, but the no-correction control captures most of it and the marginal Δ is not significant (Table 7, second block): at clip 0.20.2 the clip alone contains the reuse bias. Sweeping K held for the whole run from 44 to 128128 confirms it: PPO’s final on-time is nearly flat in K, while the corrected update sits at or below PPO throughout and its prefix ratios blow up at the largest K (Figure 15 in Appendix G.5). The lever is credit-assignment difficulty, not K. The gain is faster early learning to the same endpoint, and it reproduces across horizons. Sweeping the multi-bottleneck flow shop over J∈20,30,40,50J∈\20,30,40,50\ jobs, which sets the trajectory length, the warmup-corrected run leads plain PPO in the first half of training at every J; the second-half lead shrinks with J and is gone by J=40J=40 (Table 17 in Appendix G.5; Figure 16). A ceiling-controlled calibration, which sets the deadline per J so that PPO’s final on-time is held in a narrow band, separates the two things horizon does: the measured prefix bias roughly doubles from J=20J=20 to J=40J=40 while the early lead stays positive and roughly flat (Figure 17). Horizon drives the bias dose; PPO’s headroom gates how much of it the correction converts into a gain. The largest marginal gain is on the task with the longest-range credit assignment, and it reads differently from the flow-shop gains. On a classical disjunctive job shop (88 jobs, 55 machines, job-specific machine routes, one shared bottleneck, T=40T=40), at the feasible deadline the marginal Δ is +0.364+0.364 on every one of 66 seeds, about four times the largest flow-shop marginal (Table 7, last block; Figure 5). Most of that margin is the control’s collapse: aggressive reuse without the correction loses heavily to plain PPO, while the corrected arm’s own lead over PPO is smaller and, with 66 seeds, not significant, though unlike the flow shop it persists into the second half of training (Table 17). The win sits on a feasibility knife-edge, collapsing for both methods one deadline step tighter and vanishing one step looser; with n=6n=6 the sign of the marginal is established and the magnitude is not. The early win tracks the bias dose; the late win does not. The dose is the bias PPO drops by ignoring the prefix, btb_t of (12) evaluated at the rollout policy (where rt=1r_t=1) and summed as ∑t|bt| _t|b_t|, measured on the aggressive-reuse run without correction, so it is the dose the correction would cancel. Across n=66n=66 configuration–seed points with task difficulty partialled out, the first-half win over plain 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 6; per-configuration values in Table 17). The early advantage tracks the prefix bias the reuse actually incurred and decouples from it once the warmup switches off and PPO catches up. Across tasks the naive dose–response is flat, because PPO’s headroom additionally caps the gain; the relationship appears within a task. Figure 3: 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 7. Figure 4: Seven-machine flow shop, 2020 jobs, three bottlenecks, K=30K=30 warmup. (A) Greedy validation on-time rate versus iteration at c=1.05c=1.05 (4848 seeds): plain PPO (blue), aggressive early reuse without the correction (red), and the same reuse with the correction (orange). (B) Marginal Δ of the correction over the no-correction control at each deadline, harder to the right; bars are 22 SE and PPO’s final on-time is annotated. Values and seed counts are in Table 7. Figure 5: 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 the no-correction reuse control (red) throughout. (B) Correction marginal Δ over the no-correction control 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 7. Figure 6: 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 17. 6.3 What kind of win, and where it stops The recipe is a short warmup — correction on, K high — followed by plain PPO for the rest of the run. On the flow shop what the warmup buys is sample efficiency, not a better policy: after the off-switch the run converges to the same on-time ceiling as PPO, final performance within 0.010.01, and the Δ is the area under a faster early climb, about 3%3\% of AUC. The job shop is the exception: there the lead over PPO persists through both halves of training (Table 17; Figure 5). Sample efficiency is not compute efficiency. During the warmup the high-K arm spends several times the optimizer steps of plain PPO on each rollout batch, so the recipe buys rollouts — the currency that is scarce in this domain — not FLOPs. The corrected and uncorrected high-K arms, however, do the same optimizer work, so the marginal Δ is a compute-matched comparison. The win has two preconditions, the two that Section 6.1 saw fail: measured drift large enough that PPO’s stale-state bias exceeds the variance the correction adds, which grows with α and T (Section 4), and a reward sparse enough that PPO cannot relearn what stale data corrupted. The scheduling nulls are a property of the task and learner, not of the implementation: the same correction code, on an environment stripped to the toy’s structure, rescues runs from the dead-branch trap on every non-tied seed, and the win survives as the environment is moved toward scheduling until an informative reward or easy credit assignment removes it (Table 16; Appendices G.2–G.3). A drifting transformer learner does not restore it, so the boundary is a property of the training regime, not of the architecture (Appendix G.4). 7 Related Work Two concurrent proposals apply the prefix ratio of Section 3 to the policy update. Lei et al. [6] (“prefix importance ratio,” MinPRO) and Zhang et al. [19] (“cumulative token IS ratio,” CTPO) independently name the same bias, neither citing the other; both fix the correction at α=1α=1, stabilize it with their own variance control (Section 3.2), and evaluate on LLM mathematical-reasoning benchmarks. Neither states the structural condition under which the correction is exact, and neither extends beyond autoregressive language models, to processes whose state records its history whether deterministic or stochastic, or parameterizes the design space: the tempered family, k-truncation, and the question of 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] replaces it by an estimate of the state-visitation ratio it averages to, conditional importance sampling [12] frames that replacement 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] has the accumulated-product structure available and declines it for the policy ratio (“we do not take the product of those ρt _t coefficients …so the variance does not explode”). Applying the sampled prefix ratio to the policy update — no estimate is needed where the product already equals the ratio — and characterizing when its variance is worth paying, is the distinguishing point. In LLM reinforcement learning the token-level ratio is the default and its instability is met by modifying the ratio rather than the state-visitation distribution. GRPO [15] and DeepSeek-R1 [18] use the token-level ratio and inherit the bias we characterize. GSPO [20] uses a length-normalized sequence ratio and ASPO [21] an asymmetric ratio, two other points in the design space; DPO [11] bypasses the ratio entirely. None of these corrects the state-visitation term. Neural constructive combinatorial optimization trains a policy to build a solution one element at a time [1, 5], and PPO-family learners with sample reuse are its standard training loop, including for job-shop dispatching [16]. These methods fix a reuse count and a clip range but do not correct the state-visitation distribution the reused batches were drawn from. The canonical construction order that makes the correction exact is a convention these methods already use for decoding, not an additional assumption (Section 2). 8 Discussion and limitations The state-visitation approximation PPO inherits from TRPO is a design choice, not a necessity, and three nested questions decide before training whether to revisit it. Is the correction exact here? Yes under history-injective dynamics, which autoregressive models have natively and construction problems acquire under a canonical decision order; where histories merge, as in free-order dispatching, the estimator 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 of (12) measures from any rollout batch; a prefix-independent reward, as in the late-only falsifier of Section 5.4, leaves only the variance cost. Does the training loop preserve the difference? A wrong early commitment the loop cannot recover from turns the advantage into a success-rate effect; otherwise the correction yields at most a speed advantage (C3). In either case α must be matched to the horizon: a value tuned at one trajectory length does not transfer unrescaled, and long T, merged histories, and aggressive optimizers push the usable α toward zero. 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), (17) 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, (18) and (18) 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. The sampling-trap mode did not transfer to the pretrained model at the batch size we ran (Section 5.4); under this mechanism, RL instability on real language models reads as slow convergence from a biased gradient direction rather than as bimodal lost seeds. Whether the trap fires at batch ≤64≤ 64 is a registered follow-up (Appendix F); running it as a rescue after the null would be effect-hunting, and we did not. Two things this paper does not claim. The full correction should not replace PPO: its variance is prohibitive at long horizons, and the testbed shows it losing to PPO under aggressive Adam (Table 11). And the importance-sampling identity is not new [10]; what is new is its pointwise form under tree-structured dynamics (Section 3.1). The proposed algorithms are stabilized approximations between the two endpoints; which variant, at which α, under which optimizer and reuse schedule, is what the experiments answer. 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. 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). (19) 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 G. 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. Appendix C Family details: implementation and unevaluated members 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 Testbed protocol and estimator diagnostics D.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. D.2 Estimator diagnostics 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 (8) 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 3, Figure 1). 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 3, Figure 1). 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. D.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 (13) 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 E Testbed training experiments E.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 7, Table 8). 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 8: 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 7: 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. E.2 Transformer under N-SGD 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 2, Table 9), 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 9: Transformer under N-SGD at =1.0 lr=1.0 (K=4K=4, 1010 seeds): success rate and final η per variant. E.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 E.4). At =10−3 lr=10^-3 all methods succeed 10/1010/10. At 3×10−33× 10^-3 (Figure 8, Table 10) 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 11) 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 8: Adam ablation of Figure 2 (=3×10−3 lr=3× 10^-3, K=4K=4, 1010 seeds). The success-rate advantage survives at reduced amplitude (Table 10). 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 10: 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 11: Transformer under Adam at =10−2 lr=10^-2 (K=4K=4): success rate and final η per variant. E.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 E.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 F 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 12): tempered α=0.10α=0.10 climbs faster over iterations 22–55, collapsing to noise by iteration 1010 at ceiling. Table 12: 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 13; 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 13: 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 14). 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 14: 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 15: Cell 4 (NEUTRAL N=8N=8, LATE_ONLY) per-iteration MC η, same protocol and 1616 paired seeds as Table 12. 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 G Scheduling: nulls, controls, and boundary G.1 With no measured drift, the correction only costs variance 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 6 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 6) 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 6; Figure 10); 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 6). 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 10 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 9) 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 9: 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 10: 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 6. 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 6). 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 6); 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 G.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. 18). G.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 E), 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 11). 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 11: 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 12: 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. G.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 13A: 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 13B), 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 13: 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. G.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 G.1), swept across three on-time floors, it consistently loses by a small margin (Table 6; Figure 14). 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 6). 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 14: 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 6. G.5 The win in detail: warmup, reuse, horizon, and dose 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 7. 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 3). Aggressive reuse during the warmup, with a no-correction control. K=30K=30 for the first W=50W=50 iterations, then the standard K; the control 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 7. 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 17, 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 17, 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 7, last block; Table 17, third block; Figure 5). 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 17; 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 17: 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 no-correction K=30K=30 control; dose is the prefix bias ∑t|bt| _t|b_t| on that control, 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 4), 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 17. 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 17.