- Rating
- 4(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the stability of tabular Double Q-learning with constant step sizes. The authors represent the coupled updates of the two Q-tables as a switching system and give finite-time expected error bounds under a joint spectral radius (JSR) condition. They also construct a counterexample showing that the augmented switching family can contain unstable modes. The authors further propose an asymmetric tracking variant, AT-DQ, and give sufficient conditions for its stability. The paper supports the analysis with theoretical proofs and evaluates convergence and maximization bias through experiments on tabular tasks.
Critical strengths
-
The authors directly analyze the coupled updates of the two Q-tables in Double Q-learning and identify the signed policy-difference terms introduced by cross-evaluation. This helps explain why the contraction argument for standard Q-learning does not directly apply.
-
The authors propose AT-DQ and give explicit sufficient conditions for stability and finite-time error bounds. This shows how changing the update relationship between the two tables can lead to provable stability, connecting the structural analysis to algorithm design.
Critical weaknesses
-
In Appendix F, the authors interpret the large DQ errors as evidence that the instability of the augmented switching family can manifest in actual DQ trajectories. However, longer runs in our reproduction show that the error decreases to near zero. This suggests that a slow transient can explain the reported behavior, and the connection to the unstable modes remains unclear.
-
The sufficient stability conditions in Proposition 2 do not cover the experimental settings. Even with uniform sampling and , they require , while the experiments use much smaller ratios. Convergence and bias reduction have not been evaluated experimentally in the range covered by the theory. This makes it unclear how the stability guarantee relates to the reported empirical gains.
Questions for authors
-
What is the connection between the large DQ errors in Appendix F and the unstable modes? In longer runs of our reproduction, the error continues to decrease and approaches zero. Do the authors have further evidence that the reported behavior reflects the unstable modes rather than a slow transient?
-
How does AT-DQ perform in terms of convergence speed and maximization bias under the conditions of Proposition 2? Could the authors provide results for one such setting to clarify the connection between the theoretical guarantee and the empirical gains?
-
The worst-case stability guarantee concerns the conditional-mean switching system, while the final error bound holds in expectation. Could the authors clarify what this guarantee implies for the safety-critical applications discussed in the introduction?
3 comments
Thank you for the additional experiments. The no-offset comparison clarifies the role of the offset term in the transient error amplification. The results at also answer my question about convergence speed and bias under the conditions of Proposition 2. I have no further questions and will raise my rating to 4.
Thank you for your constructive feedback, for reviewing our revisions, and for updating your rating. We appreciate your thoughtful engagement throughout the review process.
We sincerely thank you for your careful review, constructive feedback, and for reproducing the Appendix F experiment over longer horizons. We address W1/Q1, W2/Q2, and Q3 below (revisions marked in blue in the PDF).
W1 & Q1. Connection between Appendix F and the unstable modes, and distinguishing unstable modes from a slow transient over longer runs: We agree that the error in Appendix F eventually decays over a sufficiently long horizon, and we have revised Example 1 and Appendix F accordingly. However, a slow transient would only cause the error to decay sluggishly, whereas the unstable modes in Hα manifest in actual trajectories as finite-time transient error amplification followed by a convergence delay, rather than divergence to infinity.
To directly test whether the observed behavior is caused by the signed policy-difference blocks (which create the unstable modes in Theorem 1) rather than merely a slow two-table transient, we updated Example 1, Appendix E, and Appendix F (Table 1) using a stationary i.i.d. distribution D and identical initial tables (Q01=Q02=Q0) across 5 seeds and 7 step sizes. Crucially, we compare double Q-learning against double Q-learning (no offset), which follows the exact same sampled coordinates, two-table update schedule, and greedy policies (πk1,πk2) but removes the offset term (which linearizes into the signed policy-difference blocks) from the error update. This control uses Q∗ and replays double Q-learning's greedy policies; it is a diagnostic, not a deployable algorithm. For both standard Q-learning and double Q-learning (no offset), the error never exceeds its initial value and decreases steadily across all step sizes. In contrast, double Q-learning undergoes large transient error amplification before eventually settling over an extended horizon. Because double Q-learning (no offset) shares the exact same two-table update schedule and policy path, this confirms that the behavior is not merely a slow transient, but transient amplification directly driven by the signed policy-difference terms.
W2 & Q2. How Proposition 2 relates to the experimental settings, and performance of AT-DQ under the certified conditions: Proposition 2 gives a conservative sufficient condition for worst-case contraction, not a necessary one. The theoretical threshold on τ=β/α is large because the proof bounds each matrix block separately using worst-case max norms. In practice, AT-DQ converges stably at much smaller values of τ. There is also a clear practical trade-off: a very large τ makes Q2 track Q1 too closely, which weakens maximization-bias reduction, whereas a smaller τ keeps the two tables sufficiently separated to suppress bias (Section 8 and Appendix H.1-H.2).
To directly evaluate convergence speed and bias under the conditions of Proposition 2, we added Appendix H.3 (Tables 6 and 7), testing two controlled MDPs (MDP1 and MDP2) that satisfy all assumptions of Proposition 2 simultaneously (γ=0.99, uniform stationary occupancy dmax=dmin, α=0.004≤αˉ, β=0.8, τ=200). In this certified regime, AT-DQ converges twice as fast as double Q-learning at step size α, achieves lower value-estimation error when double Q-learning suffers from underestimation bias, and exhibits a steady reduction in residual error as α decreases at fixed τ=200.
Q3. What the conditional-mean worst-case guarantee and expected-error bound imply for the "safety-critical" motivation: We agree that this phrasing could be misread as Safe RL with high-probability state or action constraint satisfaction. Our use of "worst-case" refers strictly to control-theoretic switching stability---certifying contraction of the conditional-mean dynamics across arbitrary policy-switching sequences via the JSR---while Theorem 2 and Theorem 3 bound the expected finite-time estimation error. To avoid any confusion, we have removed the "safety-critical" phrasing from the Introduction and Related Work.