PaperlayerView exact revision on arXiv

Source-linked AI summary

Enabling Token-wise Importance Sampling in Off-Policy RLVR with Proximal KL Regularization

Hao Bai, Jiarui Yao, Tong Zhang

arXiv:2610.18738v1cs.LG

TL;DR

Off-policy RLVR uses responses generated by behavior policies that can differ from the policy being optimized, while token-wise importance weighting generally biases policy gradients. This paper combines token-wise weighting with future KL credit and proves conditions under which the proximal optimizer remains the unique stationary policy. Proximal KL outperforms GRPO in micro-averaged held-out accuracy across all seven matched off-policy settings.

  • Problem

    Off-policy RLVR responses may come from older behavior policies, and token-wise importance weighting avoids high-variance response-level ratios but generally biases policy gradients.

    Source: §1 · pp. 1–2

  • Method

    Proximal KL combines token-wise importance weighting with bounded future KL credit, using verifier rewards and policy statistics without fitting a value or Q function.

    Source: §4 · pp. 5, 7

  • Results

    Proximal KL achieves higher micro-averaged held-out accuracy than GRPO in all seven matched off-policy settings; finite horizons also outperform the full tail on AIME24 mean@16 and pass@16.

    Source: §1 · p. 2, §6.4 · p. 17

  • Takeaways & Limitations

    Under coverage and local expressiveness, token-wise updates can retain the proximal target for supported stale behavior-policy mixtures without full-response ratios or a fitted critic.

    Source: §1 · p. 2

    The convergence result is limited to independent tabular logits with history visit probabilities uniformly bounded away from zero, under time-varying behavior policies.

    Source: §5 · p. 9

Abstract

from arXiv · show

Off-policy data in reinforcement learning with verifiable rewards (RLVR) can arise from asynchronous generation, rollout-training mismatch, and response reuse. Token-wise importance weighting avoids multiplying likelihood ratios across a response but generally biases policy gradients. We prove that, under coverage and local expressiveness conditions, full future KL credit makes the exact proximal optimizer the update's unique stationary policy, even for mixtures of older policies, without full-response weights or a fitted critic. We further establish convergence of continuous-time tabular population updates under persistent coverage and time-varying behavior policies, and a finite-sample reward guarantee for linear logistic models under additional assumptions. These results motivate Proximal KL, a practical off-policy RLVR method that separates the proximal reference from the sampling policy and replaces PPO clipping with bounded future KL credit. Across all seven matched off-policy comparisons on Qwen3-1.7B and Qwen3-4B, spanning two learning rates, response reuse, and rollout staleness, Proximal KL outperforms GRPO in micro-averaged accuracy over eight math benchmarks by up to 2.58%. A separate on-policy comparison yields comparable aggregate accuracy. In periodic-refresh experiments, Proximal KL avoids the collapses observed in PG and CISPO, exceeds GRPO's training accuracy, and reaches higher accuracy in fewer policy updates. Ablations show that token-wise correction outperforms sequence-level and unweighted controls. With token-wise correction retained, future KL feedback reduces sensitivity to the tested baseline perturbation relative to PPO clipping. A finite future horizon improves AIME24 mean@16 and pass@16 over the full tail, while fixed-policy measurements show that truncation reduces correction variance over the tested horizons.

1 Introduction

The introduction frames off-policy RLVR as a setting where token-wise weighting avoids response-level ratio products but can bias gradients. It presents Proximal KL, its theoretical guarantees, and empirical comparisons with GRPO and other updates.

1 Introduction

  • Proximal KL separates the fixed proximal reference, which defines the target, from the behavior policy, which determines sampling.Its practical update uses bounded future KL costs and omits ordinary PPO clipping.Source: §1 · p. 2
  • Under coverage and local expressiveness, full future KL credit makes the proximal optimizer the unique stationary policy, even with supported stale behavior mixtures.The expected update may differ from the exact proximal gradient away from the optimizer; tabular updates also converge under persistent coverage.Source: §1 · p. 2
  • For linear logistic models, repeated reference refreshes yield a finite-sample reward guarantee under additional assumptions, without forming response-level ratio products.The guarantee concerns approaching a comparator’s expected reward for a single response.Source: §1 · p. 2
  • Proximal KL achieves higher micro-averaged held-out accuracy than GRPO in all seven matched off-policy settings.The comparisons span eight math benchmarks, 1.7B and 4B models, tested learning rates and rollout staleness, including response reuse.Source: §1 · p. 2
  • Periodic-refresh experiments show Proximal KL sustains gains through PG and CISPO collapses and exceeds GRPO training accuracy at comparable update counts.Ablations find token-wise correction outperforms sequence-level and unweighted controls; future KL feedback is less sensitive than PPO clipping to the tested baseline perturbation.Source: §1 · pp. 2–3
  • In the reported ablations, a finite horizon outperforms both strong local and full-tail corrections, while fixed-policy measurements confirm that truncation reduces correction variance over the tested horizons.The tightest tested future-cost bound combines strong accuracy with smaller gradient-norm excursions.Source: §1 · p. 3

2 Related Work

The related work situates Proximal KL among KL-regularized proximal methods, future-KL gradients, and off-policy policy-gradient methods. Its focus is the actor update’s stationary policy under token-wise weighting and behavior-policy mismatch.

2 Related Work

  • Batch-size-invariant policy optimization separates the proximal reference from the behavior policy, distinguishing the optimization target from the sampling distribution (Hilton et al., 2022).The paper applies this distinction to asynchronous optimization alongside AReaL, AsyncWebRL, Slime, and Miles (Fu et al., 2025; Bai et al., 2026; RadixArk, 2026).Source: §2 · p. 3
  • FRPO derives the on-policy Future-KL gradient identity (Yao et al., 2026), which this paper uses to analyze reward regularized against a fixed proximal reference.PCL and Trust-PCL establish soft path consistency and related regularized formulations (Nachum et al., 2017, 2018).Source: §2 · p. 3
  • Unlike V-trace and Retrace guarantees for corrected value learning, this work characterizes the actor update’s stationary policy using sampled rewards and no fitted critic.The update combines full future credit with current-token importance weighting under behavior-policy mismatch (Espeholt et al., 2018; Munos et al., 2016).Source: §2 · p. 3

3 Setup and Proximal Update

The setup optimizes verifier-scored responses against a fixed proximal reference while sampling from a potentially different behavior policy. It replaces response-level importance products with token-wise weights and analyzes the resulting update without a fitted value or Q function.

3 Setup and Proximal Update

  • The objective maximizes expected verifier reward while penalizing reverse KL from the learner to a reference held fixed during each round.The behavior policy generates responses and may differ from both the learner and reference.Source: §3 · p. 4
  • The exact unrestricted optimizer is a Gibbs policy that reweights reference probabilities by exponentiated rewards before normalization.For binary rewards, correct responses are multiplied by e^1/β; β controls the strength of reweighting.Source: §3 · p. 4
  • The learner-to-reference ratio tracks movement from the proximal target, whereas the learner-to-behavior ratio corrects the sampled token’s action distribution.The ratios are related by the reference-to-behavior factor and coincide when the behavior policy equals the reference.Source: §3 · p. 4
  • Response-level importance sampling multiplies token ratios and can have variance that grows exponentially with response length.The analyzed alternative uses one current-token ratio for each sampled token.Source: §3 · p. 4
  • The update uses sampled rewards and policy log probabilities without a fitted value or Q function, and analyzes stationary points directly.The history-only baseline and advantage are held fixed during differentiation and recomputed after policy changes.Source: §3 · pp. 4–5

4 Algorithm

Proximal KL combines token-wise importance weighting with bounded future KL credit while keeping the proximal reference distinct from the sampling policy. Its window and cost bounds trade approximation bias against sampling fluctuations, and its update omits ordinary PPO clipping.

4 Algorithm

  • Proximal KL pairs each sampled token’s behavior probability with a periodically refreshed, round-fixed reference and applies token-wise importance weighting with bounded future KL credit.The algorithm uses verifier rewards and group-relative advantages without fitting a value or Q function.Source: §4 · p. 5
  • The behavior-weighted score loss and learner-to-reference KL correction serve separate roles: sampling correction versus regularized return.The ratios coincide only when behavior and reference policies match; using the reference ratio alone otherwise omits the reference-to-behavior correction.Source: §4 · p. 5
  • At each token, the future-KL window includes the current token and up to H−1 subsequent tokens; the full tail includes all remaining tokens.Finite cost bounds limit accumulated correction, and stop-gradient holds the resulting coefficient fixed while the score gradient remains active at saturation.Source: §4 · pp. 5–6
  • Bounding costs or shortening the future window can control sampling fluctuations, but both may introduce approximation bias.The window retains nearby future costs while limiting the number of terms included.Source: §4 · pp. 6–7, Figure 1 · p. 6
  • Unlike Proximal KL’s future KL feedback, the GRPO variant uses symmetric PPO clipping and omits the separate initial-reference penalty.Its KL term is not the periodically refreshed reference penalty used by Proximal KL.Source: §4 · p. 7
  • Above the upper ratio bound, PPO clipping removes positive score-function contributions and can shift the expected update.For the symmetric-noise example, clipping shifts the mean by −σ/2 rather than zero, while reducing conditional coefficient variance.Source: §4 · p. 7, Figure 2 · p. 8
  • CISPO clips detached importance weights without future KL correction, whereas PG uses importance-weighted reward advantages without future KL regularization.Removing PPO clipping removes its gate bias but leaves the reward-gradient estimator without the regularization term.Source: §4 · pp. 7–8
  • The importance-weight ablations compare token-wise ratios with response-level geometric-mean ratios and an importance-weight-free control.Both controls retain each token’s future KL credit and omit PPO clipping.Source: §4 · pp. 8–9

5 Theoretical Guarantees

Full future KL credit gives token-wise off-policy updates the proximal optimizer as their unique stationary policy under coverage and local expressiveness, including stale behavior-policy mixtures. The section extends this result to tabular convergence and a finite-sample reward guarantee under additional assumptions.

Population update

  • At the proximal target, full future KL credit makes reward-minus-KL depend only on current history, so current-token importance weighting has zero expected score contribution despite stale continuations.This cancellation identifies the target uniquely under the stated conditions.Source: §5 · p. 9
  • Under coverage and local expressiveness, the expected token-wise update with full future KL credit vanishes only at the proximal optimizer, even for stale behavior-policy mixtures.The expected update may differ from the exact proximal gradient away from that optimizer.Source: §5 · p. 9
  • With independent tabular logits and history visit probabilities uniformly bounded away from zero, continuous-time population trajectories converge under time-varying behavior policies.The convergence is toward a fixed reference’s target when the expected update is available exactly.Source: §5 · p. 9

Finite-sample reward guarantee

  • Under its linear-logistic assumptions, repeated reference refreshes make the final policy’s single-response success probability approach a comparator’s, with polynomially many scored responses for fixed group size.The guarantee assumes bounded fixed features, deterministic binary rewards, bounded response length, representation control, token-ratio control, and sufficiently small aggregate behavior mismatch.Source: §5 · p. 10
  • For fixed δ ∈(0, 1], accuracy dependence is 1/ε plus cδ/ε1+δ under a δ-dependent token-ratio condition; on-policy, the direct history-transfer bound gives 1/ε dependence.Smaller δ can require tighter token-ratio control and increase cδ; uniformly bounded token log-ratios can keep Vlog bounded independently of response length.Source: §5 · p. 10

Single-response reward compared with best-of-N

  • The single-response guarantee also covers a comparator that samples N initial-policy responses and selects a correct one when available, with oracle success probability 1 − (1 − p0(x))^N.The training budget and oracle inference budget are accounted for separately.Source: §5 · p. 10

6 Empirical Experiments

Across the tested off-policy settings, Proximal KL improves held-out accuracy over GRPO while sustaining training gains under periodic refresh and controlled rollout staleness. Ablations favor token-wise correction and show that finite future horizons can improve accuracy while reducing correction variability.

6.1 Setup

6.2 Stability Test

  • Proximal KL retains training gains across four model sizes while PG and CISPO show large accuracy declines at 8B and 32B.At 1.7B, CISPO initially improves before its training accuracy falls sharply; all four methods use importance weights.Source: Figure 3 · p. 12, §6.2 · p. 12
  • Under controlled staleness, Proximal KL and GRPO avoid comparable collapses, while Proximal KL improves training accuracy with fewer updates.At 8B, EMA-smoothed training accuracy first reaches 50% after about 200 updates with Proximal KL versus about 640 with GRPO.Source: Figure 4 · p. 12, §6.2 · p. 13

6.3 Held-out Set Evaluation

  • Up to 2.58%, Proximal KL raises micro-averaged accuracy over GRPO in all seven matched off-policy comparisons across eight math benchmarks.The separate on-policy comparison yields comparable aggregate accuracy.Source: §6.3 · p. 13, Table 1 · p. 14
  • As Qwen3-4B staleness increases from 4 to 16, Average rises for Proximal KL and falls for GRPO; Proximal KL has the more favorable change on six of eight benchmarks.The comparison uses learning rate 5 × 10^-6.Source: Table 2 · p. 14, §6.3 · p. 14

6.4 Ablations

  • Token-wise importance correction sustains training pass@16 and achieves stronger MATH500 greedy pass@1 and AIME24 mean@16 than sequence-level IS and IS-free controls.All three updates retain token-specific future KL credit; both controls undergo substantial held-out accuracy declines.Source: §6.4 · pp. 15–16, Figure 6 · p. 15
  • Proximal KL better preserves MATH500 greedy pass@1 and AIME24 scores under the tested baseline perturbation; its default future-cost bound also pairs good accuracy with smaller gradient-norm excursions.The gradient norms are measured before optimizer clipping.Source: §6.4 · p. 16, Figure 7 · p. 16, Figure 8 · p. 17
  • Intermediate future-KL windows outperform the full tail in AIME24 mean@16 and pass@16, while fixed-policy correction variance increases over the tested horizons.With βH matched, the one-token correction improves mean@16 more slowly than the intermediate window.Source: Figure 9 · p. 17, §6.4 · pp. 17–18

7 Conclusion

Proximal KL combines token-wise importance weighting with future KL credit for off-policy RLVR, with theoretical guarantees and stronger held-out accuracy than GRPO across tested off-policy settings.

7 Conclusion

  • Under coverage and expressiveness conditions, the full-tail critic-free update has the exact proximal optimizer as its unique stationary policy, and tabular population flow converges to it.The paper also gives a finite-sample reward guarantee for linear logistic models under stated assumptions.Source: §7 · p. 18
  • Proximal KL separates token-wise importance weighting from future KL credit, using clipped costs and an optional finite window in the practical algorithm.An adaptive choice of horizon H could retain useful future credit without accumulating unnecessary variability.Source: §7 · p. 18
  • Proximal KL has higher micro-averaged accuracy than GRPO in all seven matched off-policy settings, while the separate on-policy comparison yields comparable aggregate accuracy.Periodic-refresh experiments show stable training where PG and CISPO can collapse, and higher training accuracy than GRPO at comparable optimizer-update counts.Source: §7 · p. 18
  • The ablations favor combining current-token correction with future credit; bounding individual costs and truncating the horizon control correction fluctuations.An adaptive horizon could balance useful future credit against variability.Source: §7 · p. 18

A Practical Update Design

The update distinguishes the policy defining the improvement target from the policy that generated the data, then applies token-wise correction and future KL costs. Several design choices can make the implemented update differ from the idealized target.

Proximal and behavior policies

  • The proximal reference defines the improvement target, while the behavior policy determines sampling; Proximal KL uses the current-to-behavior weight directly rather than splitting it into two ratios.In GRPO, the ratio from the proximal policy is used for PPO clipping.Source: A Practical Update Design · p. 22

Bias relative to the proximal objective

  • Token-wise weighting generally changes the gradient field, while full future KL credit supplies the omitted KL gradient under exact sampling.The omitted KL gradient vanishes at the reference policy; response-wide importance weights preserve the equality off policy.Source: A Practical Update Design · p. 22

Group normalization and KL correction

  • The correction includes the current token and future costs through the response boundary; the window selects which costs enter, while β sets their per-token strength.The correction is subtracted from each token’s reward advantage without normalization by window length.Source: A Practical Update Design · p. 22

Detached update coefficients

  • Horizon truncation and log-ratio cost bounds can introduce approximation bias, while group normalization and token averaging can change the expected update field and its stationary policy.The effect on total update variance depends on covariance between retained and omitted terms.Source: A Practical Update Design · p. 22

Sequence-level IS and IS-free controls

  • The sequence-level control uses a geometric mean of token ratios and the IS-free control sets the weight to one; both retain token-specific future KL credit and omit PPO clipping.The geometric mean is distinct from the full-response ratio product.Source: A Practical Update Design · p. 23

B Training with Periodic Policy Refresh

The appendices specify training and evaluation protocols for periodic-refresh and controlled-staleness experiments, including model settings, rollout synchronization, and checkpoint evaluation procedures.

B Training with Periodic Policy Refresh

  • The appendix collects the training protocol, model and precision settings, and method-specific hyperparameters for periodic-refresh experiments.The stated purpose is to document the experiments rather than report their outcomes.Source: B Training with Periodic Policy Refresh · p. 23

B.1 Training Protocol

  • Each iteration collects a fresh response batch for one optimizer update, and rollout weights synchronize with the training policy every 64 updates.Weights remain fixed between refreshes; training accuracy is the fraction of correct responses, computed as (1 + R)/2.Source: §B.1 · p. 23

B.2 Hyperparameters

  • Periodic-refresh training uses Qwen3 base models, DAPO-Math-17K, Adam, group-mean-centered advantages, and response-token-averaged losses; PG and Proximal KL use current-token current-to-behavior weights.Qwen3-32B uses a post-trained checkpoint because a corresponding pre-trained checkpoint was unavailable.Source: §B.2 · pp. 23–24, Table 4 · p. 24

C Training with Controlled Rollout Staleness

  • The controlled-staleness appendix documents training and evaluation protocols, hyperparameters, and ablation diagnostics, with Appendix E providing the theoretical target guarantee.The protocol controls rollout staleness and checks policy-version gaps in training logs.Source: C Training with Controlled Rollout… · p. 24, §C.1 · p. 24

C.1 Training and Evaluation Protocols

  • Controlled-staleness evaluation uses EMA-smoothed online curves but separate raw checkpoint evaluations without smoothing or performance-based checkpoint selection.The stability test reports held-out accuracy and policy entropy, while gradient diagnostics use norms measured before optimizer clipping.Source: §C.1 · p. 24

C.2 Hyperparameters

  • Controlled-staleness runs use four optimizer minibatches for off-policy batches, with the proximal reference refreshed before each global batch and frozen during its minibatches.The configurations compare staleness levels 4 and 16; evaluation reports three-seed means for 1.7B at 2,000 updates and 4B scores at approximately 1,500 updates.Source: §C.2 · p. 25, Table 5 · p. 26

C.3 Ablation Configurations

The ablations examine baseline perturbation, learning-rate selection, and GRPO clipping width. They motivate future KL feedback as an alternative to an advantage-sign clipping gate and identify settings associated with the reported comparisons.

C.3 Ablation Configurations

  • A common upward advantage shift can switch off some PPO-clipped contributions, whereas an additive future KL correction preserves expected cancellation under the stated conditions.The experiment compares each method’s perturbed run with its unperturbed run to assess preservation of held-out accuracy.Source: §C.3 · pp. 26–27

C.4 Learning-Rate Selection

  • Proximal KL’s micro-averaged accuracy is higher than GRPO’s at both tested learning rates; 5 × 10−6 was selected because both methods score higher on all four greedy-evaluated benchmarks at staleness 4 and 16.The learning-rate sweep shows metric-specific preferences: 5 × 10−6 for MATH500 greedy pass@1 and AIME24 pass@16, and 1 × 10−5 for AIME24 mean@16.Source: §C.4 · p. 28, Figure 10 · p. 28

C.5 GRPO Clipping Width

  • Wider GRPO clipping at ϵclip = 0.4 is less stable than 0.2 in this comparison, with larger gradient excursions and a temporary decline in training mean@16 and pass@16.The narrower interval maintains steadier growth in training mean@16 with smaller gradient excursions.Source: §C.5 · p. 29, Figure 11 · p. 29

D Proximal target and future KL gradient

The section characterizes the proximal target and shows how future KL credit lets token-wise updates retain it under off-policy sampling. It also illustrates how proximal feedback can avoid interference between shared-parameter prompts.

D Proximal target and future KL gradient

  • Repeated exact proximal updates reach success probability one from any positive initial success probability for binary rewards.Each exact reference refresh adds 1/β to the success log-odds.Source: D Proximal target and future KL gradient · p. 30

D.1 Illustration of proximal feedback with shared parameters

  • With shared parameters, Euclidean reward-gradient flow converges to success probabilities (1, 0), while exact proximal updates converge to (1, 1).The example shows that reward-gradient improvement on one prompt can interfere with another, whereas exact proximal solves improve both.Source: §D.1 · p. 31

D.2 The Gradient of Proximal Improvement

  • The proximal-gradient coefficient includes each token’s current and later KL costs; omitting future costs generally changes the gradient.Earlier tokens affect later prefixes, so their policy-gradient coefficients include subsequent regularization costs.Source: §D.2 · pp. 31–32

E Asynchronous updates with token-wise importance weighting

E.1 Exact Response Correction

  • The exact response-level importance correction recovers the full future-KL gradient by changing measure from behavior sampling to learner sampling.The proposition assumes a finite generation tree, shared prompt distribution, and positive token probabilities.Source: §E.1 · p. 32

E.2 Token-Wise Importance Weighting and Its Stationary Target

  • Under coverage and local expressiveness, the full-future-KL token-wise update has the proximal optimizer as its unique stationary policy, including for mixtures of supported stale behavior policies.Away from the optimizer, the expected update can differ from the exact proximal gradient.Source: §E.2 · p. 35

E.3 Population Convergence and Outer Improvement

Under persistent coverage, the tabular population flow converges to the frozen-reference proximal target even when behavior policies vary over time. Approximate inner solves also preserve progress across reference refreshes when their success-log-odds error stays below the specified tolerance.

Convergence of the asynchronous population flow

  • With independent softmax logits and history occupancy uniformly bounded away from zero, the population flow converges to the proximal target at every history under time-varying supported behavior mixtures.The convergence result concerns a continuous-time population update with a fixed reference during each flow.Source: §E.3 · pp. 35–36
  • Backward induction establishes convergence at each history: the last-token policies converge exponentially, and convergence then extends to earlier histories.The proof uses the future-error identity to bound the effect of downstream policy errors.Source: §E.3 · p. 37

Reference refresh with approximate inner solves

  • Approximate reference refreshes improve every prompt’s success log-odds when each inner solve’s error is below a fixed tolerance smaller than 1/β.Each approximate round leaves a positive log-odds increment, and the required inner-flow tolerance is reached in finite time under the stated assumptions.Source: §E.3 · pp. 37–38
  • The stopping rule measures each inner solve by its success-log-odds error relative to the proximal target.A fixed tolerance below 1/β leaves a positive increment at every outer round.Source: §E.3 · p. 38

F Finite-sample convergence with a linear logistic model

This section studies finite-sample guarantees for projected full-KL-credit updates and proximal solves in a linear logistic model, including the effect of approximate inner solves under coverage. It also relates solve accuracy to reward after repeated reference refreshes and gives a best-of-N specialization comparing trained-policy single-response reward with oracle selection at initialization.

F Finite-sample convergence with a linear logistic model

  • The analysis uses a projected group update with full KL credit on finite prompt and response trees, assuming binary rewards and exact reference-relative Gibbs-target representation; nonlinear Transformer use requires additional error control.The theorem’s projected variant uses fresh response groups and an independently selected pre-update output; the implemented Algorithm 1 does not perform this projection.Source: F Finite-sample convergence with a… · pp. 38–40
  • The best-of-N specialization applies with π⋆ = qN and C⋆ = N, comparing one trained-policy response with oracle best-of-N selection while accounting separately for training and oracle-draw budgets.The oracle draws N responses from the initial policy per prompt and selects a correct one when available.Source: F Finite-sample convergence with a… · pp. 40–41

F.1 Accuracy of one proximal round

  • Lemma F.6 combines log-moment and history-transfer bounds, a drift estimate, and a group-estimator noise bound to establish accuracy of one proximal round.Source: §F.1 · p. 41

Log-moment bounds and history transfer

  • The log-moment analysis identifies centered log error with the score in the parameter-error direction, while Lemmas F.1–F.3 bound likelihood-ratio moments, history transfer, and martingale continuation.The bounds use the pathwise log-ratio budget and apply to prefixes and the full-response ratio.Source: Log-moment bounds and history transfer · pp. 42–43

Progress toward the proximal target

Group-estimator mean and noise

  • The centered group estimator has mean E[SU], with a second-moment bound under bounded score norms; both conclusions also hold conditionally for independent groups.Source: Group-estimator mean and noise · p. 45

Inner accuracy guarantee

  • Under the linear logistic model and stated coverage conditions, the one-round trajectory-KL gap is at most 3C∞A/(5L) when prefix ratios are bounded.The bound tends to zero as the number of inner updates L grows; the result assumes local target representation, 1/2 ≤ wi ≤ 2, and Vlog ≤ 1/8.Source: Inner accuracy guarantee · pp. 46, 48
  • Current-token weights control the update, while prefix weights are needed only to transfer history distributions; future-KL estimation error shrinks with token-score error.The proof shows that this error remains a fraction of exact-Q progress, preserving a positive direction toward the target under the stated mismatch budget.Source: Inner accuracy guarantee · pp. 46–47

F.2 Reward improvement across reference refreshes

  • With covered initialization and K ≥ ⌈β log(3C⋆/ε0)⌉ refreshes, the reward bound separates finite-round tolerance from accumulated inner-solve errors.The transfer result applies to positive policy sequences and uses the unrestricted proximal gap; an expected inner-gap tolerance ζ at every round yields the stated bound.Source: §F.2 · pp. 49–50

F.3 Complete finite-sample reward guarantee

Under the stated linear-logistic assumptions, repeated reference refreshes yield a finite-sample single-response reward guarantee from a covered initialization.

F.3 Complete finite-sample reward guarantee

  • The guarantee assumes bounded features and deterministic binary rewards in a linear logistic model, with target-representation and uniform token-condition requirements.The theorem requires a representable Gibbs target within the projection radius and a token condition holding uniformly over allowed actions, histories, rounds, and updates.Source: §F.3 · p. 52
  • The final policy’s expected reward is at least the comparator’s minus ε after K reference refreshes and L inner group updates per reference.The theorem sets K = ⌈β log(6C⋆/ε)⌉ and specifies L in terms of κ, X, and cδ; the response bound includes the GK ceiling contribution.Source: §F.3 · p. 52
  • A uniform-history-coverage alternative gives the same reward guarantee, but its coefficient C∞ can grow exponentially with response length.The tokenwise coefficient Vlog aggregates token log-ratio second moments additively.Source: §F.3 · p. 52
  • Projection bounds legal-token log ratios by 2B/β, so cost clipping at ϵF ≥ 2B/β leaves the analyzed update unchanged.When active, clipping has a bias–variance trade-off; approximate target representation introduces additional error terms.Source: §F.3 · p. 52

G Examples of local target representation

The section illustrates local target representation in several model families, showing how Gibbs targets can be represented at each reference. The examples also expose settings where the representation condition does not ensure a polynomial sampling budget or needs additional bounds.

Condition

  • The general local target representation condition requires representing each Gibbs target at every reference with a parameter change of norm at most B/β.The examples described meet this requirement, including at references produced by projected inner solves.Source: G Examples of local target… · p. 53

Independent tabular logits

  • In a fully branching response tree, independent tabular logits can represent each Gibbs policy, but the feature dimension can grow exponentially with response horizon T, so the resulting B does not generally give a polynomial sampling budget.The two-prompt shared-head example also satisfies the condition at every reference, with B ≥ 5.Source: G Examples of local target… · p. 53

Deterministic linear MDPs

  • For deterministic linear MDPs, backward soft values define the Gibbs token policy and the linear transition representation yields parameter changes that represent it at every reference.The transition-operator and terminal-reward coefficient bounds are explicit assumptions; deterministic dynamics alone do not imply them.Source: G Examples of local target… · pp. 53–54

A shared-feature family with B = 1

  • A shared-feature model represents the Gibbs target at every reference and horizon when reward depends only on the final coordinate.The example uses one prompt, binary actions, and features that tie the same parameter coordinate across histories at a given position.Source: G Examples of local target… · p. 54

Fixed tangent features

  • For fixed tangent features, a bounded-norm coefficient representing the soft action values is sufficient to represent the Gibbs target through a parameter shift of v_k/β.The norm bound must hold at β = 16/T; applying the result to a nonlinear Transformer additionally requires controlling logit-linearization and gradient errors along training.Source: G Examples of local target… · p. 54

Related papers

Loading 2610.18738v1…