History reparameterization improves credit assignment in sequence models
On Reparameterizing the Score Function
Machine Learning
Summary
Assigning credit to early decisions in sequences is hard when rewards come late or are rare. The authors introduce a new way to let learning signals flow backward through past choices, helping improve how models learn. They develop a technique called Optimal History-Reparameterized policy gradients to reduce noise in this approach. Their method works best when the model’s decisions depend on earlier ones, and they test it with different models showing it cuts down on guesswork in learning.
What this means in practice
- •For machine learning engineers: Train sequence prediction models with better credit propagation for sparse reward tasks to improve learning efficiency.
- •For ai operations teams: Optimize autoregressive models controlling complex sequences like routing with improved gradient techniques reducing training noise.
Authors
Mohammad Hossein Amani, Leonardo Bocchieri, Maxime Peyrard, Clément Hongler, Robert West
Abstract
Policy gradients for autoregressive sequence models differentiate each token's log-probability while holding the conditioning history fixed. This discards information about how earlier decisions shape later conditional distributions, creating a credit-assignment bottleneck when rewards are sparse. We introduce History-Reparameterized (HR) policy gradients, which replace the frozen prefix in the score function with a differentiable reparameterized or relaxed history, allowing gradients of downstream log-probabilities to propagate backward through the generated trajectory. The resulting history-pathwise term is generally biased when added directly, so we derive Optimal HR (OHR), a centered control-variate estimator with a closed-form coefficient that minimizes the trace of the gradient variance at the population level. The variance reduction is governed by temporal structure in the policy dynamics: random or weakly structured policies provide little benefit, while policies with learned sequential dependencies yield informative history-pathwise corrections. For discrete tokens, the choice of relaxation is crucial: embedding-level relaxation yields substantial variance reduction that grows with horizon, whereas straight-through Gumbel-Softmax yields essentially none in our diagnostics. We validate the method on a Gaussian linear Markov model, a sparse-reward T-maze with a recurrent policy, and an autoregressive Transformer model for small Traveling Salesman Problem (TSP) instances.