Sequence Compression Speeds Up Credit Assignment in Reinforcement Learning

Aditya Ramesh, Kenny John Young, Louis Kirsch, Jürgen Schmidhuber

Abstract

Temporal credit assignment remains a fundamental challenge in reinforcement learning, particularly in environments with delayed rewards or high stochasticity. We present Chunked-TD, an algorithm that leverages a learned world model to dynamically adjust the bootstrapping parameter $\lambda$. By "chunking" predictable sequences of experience and treating them as Monte Carlo returns while bootstrapping at points of high uncertainty, Chunked-TD accelerates credit propagation while maintaining robustness to model inaccuracies. Our results across several hard credit assignment tasks demonstrate significantly faster convergence compared to standard TD($\lambda$) baselines.

Introduction

In Reinforcement Learning (RL), determining which past actions are responsible for a current reward—the temporal credit assignment problem—is notoriously difficult. Standard approaches face a stark trade-off: Monte Carlo (MC) methods are unbiased but suffer from high variance due to stochasticity along a trajectory, while Temporal Difference (TD) learning reduces variance through bootstrapping but introduces bias that can be slow to correct, especially when rewards are distant.

While TD($\lambda$) allows for interpolation between these extremes using a fixed decay parameter, it treats all transitions uniformly. This fails to exploit the inherent structure of many environments, where some sequences are highly predictable and others are chaotic. We propose that predictable sequences are redundant for credit assignment and can be compressed to speed up learning.

Methodology: The Chunked-TD Algorithm

Chunked-TD replaces the fixed $\lambda$ with a time-varying value derived from a learned world model. This approach is inspired by the concept of "history compression," where predictable sequences of events are "chunked" together.

The Chunking Principle

If a model can predict the next state with high certainty, the agent can propagate credit across those states immediately, similar to a Monte Carlo update. Conversely, when the model encounters uncertainty, it should bootstrap to protect itself from variance.

Illustration of the Chunked-TD return calculation, where rewards are accumulated over a predictable sequence before bootstrapping at a point of uncertainty.

Adaptive $\lambda$ and Model Robustness

The algorithm sets $\lambda_{t+1}$ equal to the predicted probability of the transition $P(X_{t+2} | X_{t+1})$.

  • Highly predictable transitions ($P \approx 1$): $\lambda$ is high, and the update behaves like Monte Carlo, jumping across the delay.
  • Surprising or stochastic transitions ($P \approx 0$): $\lambda$ is low, and the agent reverts to TD(0) bootstrapping.

Unlike "Dyna-style" RL, which can be misled by a poor model, Chunked-TD only uses the model to decide how to update from real experience. If the model is inaccurate, the algorithm simply degrades to standard TD(0) rather than failing catastrophically.

Experimental Evaluation

The method was evaluated on three environments designed to stress-test credit assignment:

  • Chain-and-Split: A toy MDP with delayed deterministic rewards vs. immediate noisy outcomes.
  • Accumulated-Charge: A trajectory where "charge" is accumulated stochastically at specific points.
  • Key-to-Door: A classic task requiring long-term memory of a "key" event to unlock a "door" reward, amidst noisy distractors.

Key Results

Faster Convergence

In the Chain-and-Split task, Chunked-SARSA identified the optimal action and converged to the true value gap ($\Delta Q$) significantly faster than SARSA(0) or SARSA(1) baselines. This demonstrates the efficiency of using predictability to bridge temporal gaps.

Comparison of convergence rates on the Chain-and-Split task, showing Chunked SARSA reaching the true value gap significantly faster than standard baselines.

Solving Hard Credit Assignment

For the Key-to-Door task, we introduced C-factored credit assignment. By decomposing rewards into components (e.g., "key reward," "door reward") and maintaining separate $\lambda$ values for each based on their specific predictability, the agent successfully ignored noisy distractors. The C-factored version solved the task reliably, failing in only ~13% of episodes, whereas other methods failed in over 40%.

Discussion and Future Work

Chunked-TD demonstrates that world models can serve as effective "gatekeepers" for bootstrapping, combining the speed of model-based RL with the stability of model-free methods. While currently demonstrated in tabular settings, future work will focus on extending this to continuous state spaces and off-policy learning. The computational cost of learning generative models remains a consideration, suggesting the method is most effective when pre-trained models are available or environment dynamics are relatively simple to capture.

Summary updated

Abstract

Temporal credit assignment in reinforcement learning is challenging due to delayed and stochastic outcomes. Monte Carlo targets can bridge long delays between action and consequence but lead to high-variance targets due to stochasticity. Temporal difference (TD) learning uses bootstrapping to overcome variance but introduces a bias that can only be corrected through many iterations. TD($\lambda$) provides a mechanism to navigate this bias-variance tradeoff smoothly. Appropriately selecting $\lambda$ can significantly improve performance. Here, we propose Chunked-TD, which uses predicted probabilities of transitions from a model for computing $\lambda$-return targets. Unlike other model-based solutions to credit assignment, Chunked-TD is less vulnerable to model inaccuracies. Our approach is motivated by the principle of history compression and ‘chunks’ trajectories for conventional TD learning. Chunking with learned world models compresses near-deterministic regions of the environment-policy interaction to speed up credit assignment while still bootstrapping when necessary. We propose algorithms that can be implemented online and show that they solve some problems much faster than conventional TD($\lambda$).
BibTeX
@inproceedings{ramesh2024sequence,
  author = {Aditya Ramesh and Kenny John Young and Louis Kirsch and Jürgen Schmidhuber},
  title = {{Sequence Compression Speeds Up Credit Assignment in Reinforcement Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=NlM4gp8hyO},
}
Figure