PaperlayerView exact revision on arXiv

Source-linked AI summary

The Variance of Thought: Policy Variance, Critical Forks, and Local Credit Assignment

Yingru Li

arXiv:2608.22467v1cs.LG

TL;DR

Long-horizon reasoning and tool-using agents face credit-assignment difficulty because terminal rewards provide little intermediate signal. The paper analyzes this through policy variance, deriving discovery and estimation costs and showing how bootstrapping can reduce horizon dependence under multiplicative value accuracy. Its scope includes a stochastic-environment caveat: environmental variance remains and policy dispersion screens only policy criticality.

  • Problem

    Long-horizon language-model tasks are limited by credit assignment when terminal rewards provide no token-level signal.

  • Method

    The paper analyzes credit assignment through policy variance, critical forks, local discovery bounds, and long-horizon Monte Carlo estimation in deterministic and stochastic environments.

  • Results

    Policy variance determines a local discovery budget, while the remaining horizon creates an exponential estimation cost shared by sampling schemes, including branched search.

  • Takeaways & Limitations

    Bootstrapping converts products of survival probabilities into sums under multiplicatively accurate value representations, motivating log-value critics and rollout budgets based on policy variance.

  • Takeaways & Limitations

    In stochastic environments, environmental variance adds estimator noise, leaves residual TD-advantage variance, and makes attribution require repeated rollouts from the same state–action pair.

Abstract

from arXiv · show

Long-horizon language-model tasks --- multi-step reasoning and tool-using agents alike --- are limited by credit assignment. We analyze it through the policy variance $σ_π^2(s)=\operatorname{Var}_{a\simπ}[Q_π(s,a)]$, which in a deterministic MDP is the sole source of return variance and is injected in discrete pulses at states we call critical forks. Three results follow. (i) Policy variance is a discovery budget: observing an action of advantage $c$ requires $Ω(c^2/σ_π^2(s))$ draws, a bound that is exact on the canonical two-point fork. (ii) Policy variance is bounded by the policy's Gini dispersion, $σ_π^2(s)\le 1-\|π(\cdot|s)\|_2^2$, a rollout-free necessary condition for criticality computable from logits alone. (iii) The remaining horizon sets the estimation cost: at a fork whose downstream success probability is $P$, the Monte Carlo advantage estimate has signal-to-noise ratio of order $\sqrt{P}$, so its sample cost scales as $1/P$ --- a cost that branched sampling shares. Bootstrapping removes it by converting a product of survival probabilities into a sum, provided the value representation is multiplicatively accurate, which argues for log-value parameterization.

1 Introduction

Long-horizon reasoning lacks token-level feedback, making credit assignment difficult. The paper reframes policy-induced return variance as both the learning signal and a guide to local discovery versus long-horizon estimation.

  • Terminal-only rewards provide no direct token-level signal for trajectories of length T.
  • In deterministic environments, all return variance originates in the policy’s choices, so uniformly suppressing it also removes learning signal.
  • Local discovery asks how many action samples are needed to observe an action whose advantage exceeds c.
  • Long-horizon estimation asks how many trajectory samples are needed to estimate an observed action’s advantage accurately enough to use.
  • Policy variance governs local discovery, while the remaining horizon governs an exponential estimation cost.

2 Setup: Policy Variance as the Sole Source of Instability

The paper models reasoning as a finite-horizon MDP with terminal reward and defines policy variance as the choice-driven component of return variability. In deterministic reasoning, this variance appears as local pulses at critical forks.

  • Reasoning is modeled as a finite-horizon MDP whose states are token prefixes, actions are next tokens, and reward is a single terminal R in [0, 1].
  • For pure reasoning, transitions are deterministic, while determinism is used to isolate policy variance and instantiate the long-horizon chain.
  • Under deterministic transitions and γ = 1, the environmental variance term vanishes.
  • Return variance in deterministic reasoning is a sum of state-local pulses rather than diffuse background noise.
  • A τ-critical fork is introduced as a state whose policy variance exceeds the threshold τ.

3 Local Discovery Is Polynomially Gated

Local discovery is controlled by action-probability dispersion and policy variance rather than by long-horizon rollout cost. The resulting discovery bound is exact on the canonical two-point fork, while dispersion remains only a necessary screen.

  • For bounded Qπ, advantage magnitude is limited by the action probability through |Aπ(s, a)| ≤ 1 − π(a|s).
  • High-advantage actions therefore lie in the low-probability tail of π(·|s).
  • The Gini–Simpson dispersion D(s) provides a rollout-free necessary condition: if D(s) < τ, s is not a τ-critical fork.The condition costs O(|A|) time on the next-token distribution and requires no generation.
  • Policy dispersion is necessary but not sufficient for criticality because value-equivalent actions can make D large while σ_π^2 remains small.For a two-point policy, the gap between D and σ_π^2 is 2/∆^2; the bound is within two of tight at maximal value gap.
  • The discovery budget requires Ω(c^2/σ_π^2(s)) samples to observe advantage at least c.The second-moment bound is sharp for a single draw.
  • On the canonical two-point fork, the discovery bound is attained exactly at c = 1 − ε.
  • When the policy’s success probability is v ≪ 1, positive-advantage discoveries are rare in proportion to v.The sharper success-rate bound yields approximately v/c for c ≤ 1.

4 Long-Horizon Estimation Is Exponentially Costly

Long-horizon estimation becomes exponentially costly because successful continuations have shrinking probability, while local bootstrapping converts multiplicative survival structure into additive log-space targets.

  • Monte Carlo cost: 1/Pj+1 rollouts are required for unit-SNR Monte Carlo advantage estimation when the successful continuation probability is Pj+1.The estimate is unbiased, but its Bernoulli signal is exponentially small in the remaining horizon.
  • Monte Carlo cost: The wrong branch produces a deterministic failure signal, so sampling cost falls entirely on estimating the successful branch.Branched sampling inherits the same 1/Pj+1 cost because it estimates the successful action value by rollout.
  • Sampling schemes: A whole-trajectory method additionally faces the joint probability that all forks resolve correctly, whereas local estimation resolves each fork conditionally and marginally.This distinguishes local credit assignment from trajectory-level sampling without removing the successful-branch estimation cost.
  • Bootstrapping: Log-value bootstrapping makes each regression target a single O(1) increment and represents the long-horizon value as a sum of increments.Value-space estimation instead requires absolute accuracy much smaller than the downstream success-weighted advantage gap.
  • Bootstrapping: Multiplicative calibration is required for a local credit resolver, motivating log-value critics as the paper’s main long-horizon empirical prediction.The proposed resolver may be a learned critic, value-equipped tree search, or another bootstrapped estimator.

5 Algorithmic Implications

The algorithmic framework uses policy dispersion to detect and classify critical forks, allocates rollouts by the discovery budget, and contrasts amortized critics with non-amortized branching.

  • Fork taxonomy: σ^2_π and policy entropy identify (ε, Δ) uniquely, whereas neither statistic alone suffices for fork characterization.This yields distinct uncertainty and exploration regimes.
  • Fork taxonomy: At Type I forks, ε ≈ 1/2 and value-divergent actions appear within O(1) samples, making decision rather than discovery the difficulty.The stated intervention is a wider trust region permitting a decisive update.
  • Fork taxonomy: At Type II forks, ε ≪ 1, so discovery requires Θ(1/ε) samples and the rare positive update must be retained against a confident default.The same sample count follows from the lower bound and the minority-branch hit probability.
  • Resolver trade-offs: Learned critics trade approximation bias for amortized horizon cost O(1), while branching rollouts avoid approximation bias but cost Θ(1/Pj+1).Branching rollouts can supply targets for critics when spent where the discovery budget makes them affordable.
  • Detection procedure: Fork detection first screens states from next-token distributions at no rollout cost, then budgets surviving states with approximately c^2/τ rollouts.The procedure samples both top-p head and tail candidates and uses an EWMA outlier test followed by entropy classification.
  • Stochastic environments: In stochastic environments, the dispersion screen covers only policy criticality, while environmental variance adds an irreducible estimation floor and makes attribution ambiguous.Separating the two variance terms requires repeated rollouts from the same state-action pair; its sample cost remains open.

6 Conclusion

The conclusion separates local discovery from long-horizon estimation: policy variance determines the former, while remaining horizon determines the latter, motivating bootstrapping and log-value critics.

  • Conclusion: Policy variance sets the local discovery budget, with Ω(c^2/σ^2_π(s)) samples attained exactly on the two-point fork.It is also bounded by policy Gini dispersion, enabling rollout-free screening.
  • Conclusion: The remaining horizon creates an exponential estimation cost shared by every sampling scheme, including branched search.This cost is distinct from the local discovery budget.
  • Conclusion: Bootstrapping converts the product of survival probabilities into a sum when the value representation is multiplicatively accurate.This supports the paper’s prediction that log-value critics should dominate at long horizons.
  • Conclusion: The framework provides a free fork-screening rule and a rollout budget derived from the discovery analysis rather than selected as a hyperparameter.These are presented alongside the long-horizon log-value prediction.
  • Variance decomposition: The deterministic variance decomposition uses the law of total variance and collapses transition variance because the next state is a point mass given the current state and action.The recursion unrolls return variance into policy-variance terms under deterministic transitions.

C Proof of Theorem 6

The proof bounds the probability of observing a sufficiently advantageous action using centered advantage variance and shows tightness on a two-point distribution.

  • Setup: A centered advantage variable has mean zero, variance σ^2_π, and support [−V^π(s), 1−V^π(s)].These support constraints enable one-sided, two-sided, and success-rate bounds.
  • One-sided bound: σ^2_π/(σ^2_π+c^2) is the tight one-sided upper bound obtained by optimizing Cantelli’s inequality over the auxiliary threshold.The optimizing threshold is u⋆ = σ^2_π/c.
  • Tightness: The bound is attained by a two-point law with mass σ^2_π/(σ^2_π+c^2) at advantage c and mass c^2/(σ^2_π+c^2) at −σ^2_π/c.Setting c = 1−ε and σ^2_π = ε(1−ε) recovers the canonical fork exactly.
  • Two-sided bound: Chebyshev gives P(|X| ≥ c) ≤ σ^2_π/c^2, while summing the one-sided bounds is weaker whenever c ≥ σ.The comparison distinguishes the two-sided absolute-deviation bound from the optimized one-sided result.
  • Success-rate bound: The success-rate bound follows by applying Markov’s inequality to positive advantage after bounding positive and negative means using the support limits.The resulting expectation bound is E[X+] ≤ min{V^π(s), 1−V^π(s)}.

D Why Bernstein’s Inequality Is Vacuous Here

Bernstein’s single-draw bound is structurally vacuous: with n=1, its exponent is dominated by the linear term, erasing the policy-variance dependence. Reintroducing N independent draws restores exponential decay, and the canonical fork shows the gap exactly.

  • On the admissible domain c ∈ (0, 1], Qπ ∈ [0, 1] implies |Aπ| ≤ 1 and σ^2 ≤ 1/4.
  • The bound is uniformly at least 0.4463, because E ≤ 3/2; it therefore remains non-informative across the domain.
  • As σ^2 → 0, the bound approaches 2e^(-3c/2), so it cannot certify rare discovery at a non-critical fork.
  • On the canonical fork, the true discovery probability is ε, Equation (4) is exact, while Equation (11) is at least 0.446, overstating it by ε^-1.
  • With n = 1 and b = 1, Bernstein’s useful exponent is dominated by c/3, washing out the σ^2 dependence.The issue is structural rather than a matter of constants.
  • Over N independent draws, the no-discovery probability is at most e^(-Npc), restoring exponential decay at rate pc ≤ σ^2/(σ^2 + c^2).The two-point fork attains the corresponding discovery budget exactly.

E.2 Proof of Proposition 9

On the chain, exact-baseline Monte Carlo advantage estimation has a success-probability-dependent cost: its signal-to-noise ratio shrinks with the remaining horizon, while logarithmic value targets keep each regression increment bounded.

  • Proof of Proposition 9: Conditioned on taking the correct action at sj, the Monte Carlo return is Bernoulli(Pj+1), with an unbiased exact-baseline advantage estimate.Its variance is Pj+1(1 − Pj+1).
  • Proof of Proposition 9: The required rollout count is nj = (1 − pj)^-2(1 − Pj+1)/Pj+1 ≍ (1 − pj)^-2P^-1 for unit signal-to-noise ratio.Averaging n i.i.d. rollouts reduces standard error by n^-1/2.
  • Proof of Proposition 9: For the wrong branch, the return is zero almost surely, making the Monte Carlo advantage estimate deterministically −Pj.
  • Proof of Proposition 9: Because Vπ(sj) = pjVπ(sj+1), log-space targets equal the bounded per-step increment log pj, avoiding horizon-dependent conditioning.
  • Identifiability: Measuring the pair (σ^2π(s), H(s)) identifies the fork type, whereas neither policy variance nor entropy alone suffices.

F.2 Gradient SNR at a Type II fork

At a Type II fork, the rare positive branch produces a gradient estimator whose signal-to-noise cost matches the policy-variance discovery budget. This agreement follows from exact score–advantage alignment on the two-point fork.

  • Gradient construction: At the softmax-parameterized fork, the single-sample REINFORCE gradient equals (1 − ε)^2 with probability ε and ε^2 with probability 1 − ε.The two logits contribute opposite gradients, so one coordinate suffices for the SNR analysis.
  • Gradient construction: The gradient’s expected value is ε(1 − ε), while its second moment is ε(1 − ε)^4 + (1 − ε)ε^4.
  • SNR result: Θ(1/ε) samples give unit gradient SNR, exactly matching the policy-variance budget 1/ε at σ^2π = ε(1 − ε).The agreement is exact in order and reflects perfect score–advantage alignment.
  • SNR result: Policy variance is the operative statistic for the gradient estimator, not merely for return variance.
Loading 2608.22467v1…