- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
TD-learning algorithms with function approximation introduce a compound error where an erroneous update to the current state due to wrong value estimation of the next state, lead to further aggravating the erroneous prediction of the next state due to function approximation. The paper shows that in stationary deterministic chains with constant positive feature overlap between consecutive states, this compound error is strong enough to lead the TD update to never decrease the next state squared value error in expectation. To mitigate this issue, the paper introduces Successor-Shift-Controlled TD (SSC-TD), which controls the next state value shift (i.e., reducing the error from propagating by a tunable fraction), while preserving the magnitude of the TD update. However, the paper further argues that fully suppressing the next state value shift is not always beneficial (e.g., when both current and next state values estimates need to be adjusted in the same direction). Thus, they further introduce adaptive SSC-TD, which suppresses the next state value shift during learning, only when the update increases the next-state squared value error on average. The paper shows good performance on Atari Lifetime MSE as well as no divergence in Baird's Counter example (unlike TD-learning).
Critical strengths
- Targets a fundamental problem in TD-learning with function approximation (i.e., the compound error due to function approximation and bootstrapping the next state estimated value).
- To my knowledge, the derivation of how the TD-update affects the expected change in the next-state value error is novel, albeit limited to to stationary deterministic chains with constant positive feature overlap between consecutive states.
- The paper shows good performance on Atari Lifetime MSE (i.e., policy evaluation only) compared to two baselines as well as no divergence in Baird's Counter example (unlike TD-learning).
- The paper is clearly written and easy to follow.
Critical weaknesses
- The "successor-error shift" identified by the paper is a well-know mechanism in RL, which has been studied extensively and it is even described in Sutton and Barto 2018, RL text-book ("Examples of Off-policy Divergence" 11.2, independently of whether the transitions are on- or off- policy). While the authors mention this in the related work section, the abstract and introduction present this as a core contribution of the paper.
- The derived SSC-TD is similar to Constrained TD conceptually (Durugkar & Stone 2017). The authors compare SSC-TD performance with Constrained TD, but the results are buried in the appendix (i.e., Table1) with no reference in the main text.
- In the current implementation, the algorithm is limited to policy evaluation with linear function approximation. With nonlinear functions, the feature overlap itself changes during training, which the linear case cannot capture.
- There was no attempt to investigate the proposed policy evaluation algorithm in relation to policy improvement (i.e., in a full policy iteration loop).
- The stationary deterministic chains with constant positive feature overlap between consecutive states is quite restrictive.
Overall my biggest concerns are reduced novelty (e.g., compared to Constrained TD), limited empirical analysis (e.g., no extension to generalised policy iteration or comparison to residual algorithms) and theoretical results limited to a restrictive case (i.e., stationary deterministic chains with constant positive feature overlap between consecutive states).
Questions for authors
- Residual methods solve a similar issue (e.g., Baird's residual algorithm), although they suffer from slower learning. Could the authors also compare SSC-TD to residual algorithms, assessing learning speed and performance ?
- On Mixed states, SSC-TD is slower on earlier episodes than standard TD-learning. How does this trend behave during generalised policy iteration (i.e., when the policy is also updated). Does this translate to a slower overall learning ? Especially, since during policy iteration, the policy is updated before the policy evaluation step has "converged". Could the authors integrate adaptive SSC-TD in a generalised policy iteration loop comparing it to standard TD-method that delayed the target network updates (i.e., Mnih et al., 2015).
- Could the authors be more explicit on the novel contribution of SSC-TD relative to Constrained TD?
- Since SSC-TD does not have a general convergence result under linear function approximation. Does this mean SSC-TD lose the convergence guarantees that standard TD-learning has under linear function approximation and on-policy learning?
2 comments
Author Response to Reviewer unsp (Part 2/2: Theory and Experiments)
W5 / Q4: Theory and Analysis
W5: Are the deterministic-chain and constant-overlap assumptions essential?
They are needed for the closed-form net effect (9), not for successor-error reinforcement (7) itself. The decomposition in Eq. (7) holds for stochastic transitions and varying overlap. Positive overlap still amplifies the successor's own error, though the net shift need not be harmful.
To address this concern more fully, we have extended the net-effect analysis in Eq. (9) to stochastic transitions in the revised manuscript (Appendix B). Under stationarity and constant positive overlap, stochastic transitions add the following covariance contribution to Eq. (9): This covariance can have either sign. At (with centered rewards), the net shift remains harmful unless a negative covariance offsets the nonnegative error-difference term.
Q4: Convergence of SSC-TD under linear function approximation
Standard TD's linear on-policy guarantee does not automatically transfer to SSC-TD, because the expected-update operator changes. We have not established a guarantee for general suppression strengths or adaptive switching. The Baird experiment demonstrates stability in the tested configuration, not universal convergence. We state this explicitly in Section 8.
Experiments
W3: Does SSC-TD extend to nonlinear approximation with changing feature overlap?
We agree that our reported experiments do not establish SSC-TD's effectiveness with learned representations. We focus on linear value prediction, where prediction changes can be measured exactly and the mechanism can be studied without the additional effects of representation learning. We have clarified this scope in the revision and identify nonlinear SSC-TD as an important direction for future work (Sec. 8).
The restriction to linear approximation limits our theoretical guarantees and empirical conclusions, not the underlying mechanism. Successor-error amplification does not require fixed feature overlap. Equation (7) holds for varying overlap, and for differentiable nonlinear value functions, the same decomposition holds to first order with current value gradients replacing features (Sec. 2). Their overlap can change during learning.
W4: Why is SSC-TD not evaluated within policy iteration?
Our primary contribution concerns successor-error reinforcement in value prediction, rather than policy improvement. We use fixed-policy evaluation, following the established Atari prediction benchmark of Javed et al., to isolate the effect of TD updates on prediction accuracy. Whether these improvements also lead to better policy learning is an important question for future work (mentioned in Sec. 8). A reliable Atari control comparison would require additional experiments and evaluation beyond what is feasible during the rebuttal period.
Q2: Does the early slowdown in Mixed States imply slower policy improvement?
The early slowdown in Mixed States occurs with fixed SSC-TD, not adaptive SSC-TD. In the same experiment, adaptive SSC-TD avoids this slowdown and performs at least as well as TD throughout learning (Fig. 4). This is precisely the motivation for adaptation: to preserve useful generalization while suppressing harmful successor shift.
The Mixed States environment has only one action, so policy improvement cannot be evaluated there. Although these results address the concern about early prediction performance, they do not establish how adaptive SSC-TD performs under changing policies.
Author Response to Reviewer unsp (Part 1/2: Contributions and Related Work)
We thank the reviewer for the detailed review and constructive feedback. We clarify our contributions, their relationship to prior work, and the scope and limitations of our theoretical and empirical results.
W1 / W2 / Q1 / Q3: Contributions and novelty
Successor shift and successor-error amplification are different phenomena. The former is known and the later is novel (current paper). Successor shift is the change in the successor's prediction caused by an update at its predecessor. This is well known, as we acknowledge in the Introduction and Related Work (Sec. 7). Sutton and Barto's (Sec. 11.2) includes examples that show how such feedback can cause TD to diverge.
What is new is the analysis of how this shift affects the successor's value error. To our knowledge, prior work has not isolated and quantified the component by which the successor's own error enters the predecessor's TD target and is reinforced at that same successor through feature overlap. We distinguish this harmful component from useful transfer and establish conditions under which the complete successor shift worsens successor's prediction. Importantly, this mechanism occurs even when on-policy TD converges. It is not merely another explanation of divergence.
Both suppress successor shift, but differ in motivation, derivation, and update rule. Motivated by the success of DQN, Constrained TD (CTD) was designed to limit bootstrap-target movement without delayed target networks. It projects out the entire successor-aligned component, which can nearly eliminate the update when consecutive features align. In contrast, SSC-TD is developed to address successor error amplification, and is derived from an optimization objective that penalizes successor shift (Eq. 11). The SSC-TD update allows partial suppression, and normalizes the update to preserve TD's norm. Unlike CTD, adaptive SSC-TD suppresses only when the estimated shift is harmful, because useful generalization should be retained (Sec. 6.2, Fig. 4).
The empirical difference is substantial. Adaptive SSC-TD outperforms Constrained TD on ALL of the 56 Atari games, and the gap is substantial on some of the games (e.g., Skiing and Tennis); see Table~1-3 in the Appendix E.4. We already discuss CTD in Related Work and refer to its comparison in Sec. 6.3, with full results in Appendix E.4. In the revision we highlight these numbers in the main experiments.
Residual gradient (RG) is not a standard competitive baseline for value-prediction accuracy. Its slow learning has long been documented (Baird, 1995). More directly, Li (2008) compared TD and RG and found that TD generally achieves lower prediction error, while RG produces smaller TD errors. Recent experiments with neural networks also found TD superior to RG (Yin et al., 2022). This distinction is important because our objective is accurate value prediction, not minimizing the Bellman residual. We therefore use TD as the primary benchmark.
SSC-TD is closely related to residual algorithms, and its update can be expressed as a state-dependent mixture of TD and RG. However the motivation and derivation of the two algorithms are totally different. RG's successor-gradient correction arises from minimizing squared Bellman error, not from analyzing successor shift. RG applies this correction regardless of its effect and can even reverse the shift. SSC-TD instead partially suppresses the shift without reversing it, while adaptive SSC-TD suppresses it only when estimated to be harmful. Our contribution is not mixing TD and RG, but identifying when and how suppression is beneficial.
In the revised paper we clarify this relationship and the established TD–RG comparisons in Related Work.