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.
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.
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