In the world of autoregressive models—the architecture behind everything from ChatGPT to protein folding predictors—training with Reinforcement Learning (RL) is a standard practice. However, these models suffer from a fundamental "credit-assignment bottleneck." When a model generates a long sequence and gets a single reward at the end, standard algorithms struggle to figure out which specific token in the past was responsible for the final outcome.
A new paper from researchers at EPFL and CNRS, titled "On Reparameterizing the Score Function," proposes a clever way to break this bottleneck by making the model's own history differentiable.
TL;DR
Standard policy gradients treat a model's past outputs as fixed constants, ignoring how early decisions shape future probabilities. This paper introduces History-Reparameterized (HR) policy gradients, which allow gradients to flow backward through the generated trajectory, significantly improving credit assignment and reducing variance in sparse-reward tasks.
What Problem Does This Paper Address?
When we train a sequence model using RL (like REINFORCE or PPO), we use the "score function": $\nabla_\theta \log p_\theta(x_t | x_{<t})$. Crucially, this formula treats the history ($x_{<t}$) as a frozen constant.
Imagine a model solving a multi-step math problem. If it makes a tiny arithmetic error in step 1 but reasons perfectly for the next nine steps, a standard RL algorithm sees a "wrong" final answer and penalizes every step equally. It doesn't "know" that the later steps were actually correct given the initial mistake. This is because the gradient doesn't capture how changing step 1 would have changed the probabilities of steps 2 through 10. As sequences get longer, this lack of "pathwise" information makes the gradient signal extremely noisy.
Methods
The authors bridge the gap between score-function estimators (which don't need differentiable rewards) and pathwise estimators (which are low-variance but require everything to be differentiable).
- History Reparameterization (HR): Instead of treating the history as a fixed prefix, they replace it with a differentiable "relaxed" history. This allows them to use Backpropagation Through Time (BPTT) to see how a slight change in a past token would affect the log-probability of current tokens.
- Optimal HR (OHR): The raw HR estimator is biased. To fix this, the authors derive a "control-variate" version called OHR. It centers the history-pathwise term and uses a closed-form coefficient ($\alpha^*_1$) to minimize the total variance of the gradient while keeping it unbiased.
- Embedding-Level Relaxation: For discrete tokens (like words), they find that "straight-through" methods don't work well. Instead, they use a soft weighted average of token embeddings during the forward pass of the gradient calculation, creating a smooth, differentiable path through the sequence.
Datasets
The researchers validated OHR across four increasingly complex settings:
- Gaussian Linear Markov Model: A mathematical sandbox used for analytical proof and validation.
- Minimal Autoregressive Model: A toy discrete model tasked with matching a specific target sequence.
- T-Maze: A classic RL benchmark where an agent receives a cue at the very start and must remember it to make a correct turn at the very end of a long corridor.
- Traveling Salesman Problem (TSP): A combinatorial optimization task where a Transformer-style model constructs a route one city at a time.
Key Insights and Ideas
- The "Environment" is Differentiable: In standard RL, the environment is a black box. But in autoregressive generation, the "environment" for token $t$ is just the model's own previous outputs. Since we own the model, we can make that environment differentiable.
- Relaxation is Decisive: The choice of how to handle discrete tokens is critical. The authors show that embedding-level relaxation provides substantial variance reduction that grows with the sequence length, whereas the popular Gumbel-Softmax "straight-through" approach yields almost no benefit in this context.
- Structure-Dependent Gains: HR isn't a silver bullet for a completely random model. It provides the most benefit when a model has already learned some sequential structure (e.g., during fine-tuning), as the "pathwise" signal becomes more informative than noise.
Key Results
- Massive Variance Reduction: In the minimal embedding model, OHR achieved up to a 5x reduction in variance compared to standard policy gradients.
- Solving the Unsolvable: In the T-maze task, standard REINFORCE often failed to converge as the corridor lengthened. OHR remained reliable, solving the task at lengths where the baseline was completely "stuck."
- Composability: OHR can be combined with other popular techniques. When paired with the RLOO baseline on the Traveling Salesman Problem, the benefits were multiplicative, achieving the lowest overall gradient variance.
Limitations and Future Work
While the results are promising, the authors note several areas for further exploration:
- Scale: The experiments were conducted on relatively small models (up to ~120K parameters). Whether these gains persist in massive Large Language Models (LLMs) with billions of parameters remains an open question.
- Computational Cost: HR requires an additional backward pass through the trajectory, adding $O(N)$ compute overhead.
- Baselines: The method hasn't yet been tested alongside complex per-token baselines or PPO-style value functions in large-scale settings.
By turning the "frozen" history of autoregressive models into a differentiable path, OHR offers a mathematically grounded way to make RL training more efficient and stable for the next generation of sequence models.
Summary updated