acceptodds
Under review as a conference paper at ICLR 2027

Is Constant Step-Size Double Q-Learning Stable? Analysis and an Asymmetric Variant

Abstract

Double Q-learning is a classical reinforcement learning method designed to reduce maximization bias, yet its worst-case finite-time behavior under constant step sizes has received relatively limited theoretical attention. This paper develops a direct switching-system framework for analyzing the finite-time behavior of constant step-size double Q-learning. By formulating the coupled updates as a switched linear system on an augmented error space, we show that, unlike standard Q-learning, joint spectral radius (JSR) stability of the resulting augmented switching family is not automatically guaranteed. Accordingly, we characterize a mode-wise necessary condition for JSR stability and show that the augmented double-Q switching family can contain unstable modes even for arbitrarily small positive constant step sizes. To address this limitation, we propose a novel asymmetric double Q-learning variant whose tracking structure admits a JSR stability guarantee under explicit constant step-size conditions. We further validate the proposed method through empirical evaluations.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Double Q-learning, Joint Spectral Radius, Switching systems, Maximization bias

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_vnFGOpenReview ↗
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
  1. 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.

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

  2. The sufficient stability conditions in Proposition 2 do not cover the experimental settings. Even with uniform sampling and γ=0.99\gamma=0.99, they require τ=β/α>198\tau=\beta/\alpha>198, 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
  1. 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?

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

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

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α\mathcal{H} _ \alpha 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 DD and identical initial tables (Q01=Q02=Q0Q _ 0 ^ 1 = Q _ 0 ^ 2 = Q _ 0) 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)(\pi _ k ^ 1, \pi _ k ^ 2) but removes the offset term (which linearizes into the signed policy-difference blocks) from the error update. This control uses Q∗Q ^ \ast 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 τ=β/α\tau = \beta / \alpha 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 τ\tau. There is also a clear practical trade-off: a very large τ\tau makes Q2Q ^ 2 track Q1Q ^ 1 too closely, which weakens maximization-bias reduction, whereas a smaller τ\tau 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\gamma = 0.99, uniform stationary occupancy dmax⁡=dmin⁡d _ {\max} = d _ {\min}, α=0.004≤αˉ\alpha = 0.004 \le \bar{\alpha}, β=0.8\beta = 0.8, τ=200\tau = 200). In this certified regime, AT-DQ converges twice as fast as double Q-learning at step size α\alpha, achieves lower value-estimation error when double Q-learning suffers from underestimation bias, and exhibits a steady reduction in residual error as α\alpha decreases at fixed τ=200\tau = 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.

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 τ=200\tau=200 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.

Reviewer_drKLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies how the two estimates of an action value interact through a family of mathematical updating rules when using a common fixed learning rate. It finds that unstable rules could be identified within this family and proposes a method in which one estimate learns from experience while the other follows it, proves stability under certain learning rate conditions and reports more efficient learning on several controlled small domains.

Critical strengths

The paper studies a specific problem that is somewhat understudied, to my best knowledge, supported by detailed theoretical evidence. The proposed updating rule seems to be simple.

Critical weaknesses

Here are the main limitations. In general, I think the significance of the work can be hardly established due to both theoretical and empirical gaps.

First, though some unstable rules are discovered but actually it cannot really show that double-q learning is unstable. Practically, it is well-known in the community that both the classic q-learning in tabular setting and many deep RL variants, including many variants are well-cited/broadly empirically tested. There is no strong evidence of their instability empirically were found.

In fact, the paper does not really show that the unstable switching behavior is realizable by the actual proposed algorithm. Large finite-horizon errors in Appendix F do not resolve this gap while lemma 4 already establishes that the actual estimates remain unbounded.

Second, the experiments do not really test the theoretically guaranteed tracking regime. The reported improvements appears to occur outside the establish sufficient guarantee and do not validate the proposed theoretical explanation of stability by proposition 2, which requires the tracking-to-learning rate ratio to exceed 198 when the discount factor is 0.99, even under uniform sampling.

Third, theorem 2 assumes a joint-spectral radius condition, but it does not identify which problem class would make those conditions verified. Moreover, its stochastic conclusion is an expected-error bound under independent sampling with complete coverage, rather than a high-probability learning guarantee supporting the safety-critical motivation.

Last, in the experiments, the methods use the same learning rate with different update frequencies, leaving faster learning interfered with updating schedule. There is no control that distinguishes instability from errors that decrease very slowly. Tuned baselines and a comparable soft-target Q would make the claimed benefits more convincing.

Questions for authors

see weakness

1 comment

We sincerely thank you for your careful review and constructive feedback. We address all four points from the critical weaknesses (W1-W4) below (revisions marked in blue in the PDF).

W1. Does the mode-wise instability affect actual double Q-learning trajectories, given boundedness in Lemma 4?: Lemma 4 establishes boundedness, which does not rule out transient error growth. Example 1 concerns the augmented switching family. Appendix F shows transient amplification in the actual double Q-learning updates and uses a matched control to examine the contribution of the signed policy-difference terms.

Specifically, in the revised Example 1, Appendix E, and Appendix F (Table 1), we evaluate a stationary i.i.d. distribution DD and identical initial tables (Q01=Q02=Q0Q _ 0 ^ 1 = Q _ 0 ^ 2 = Q _ 0) across 5 seeds and 7 step sizes. As the matched control, double Q-learning (no offset) (a diagnostic, not a deployable algorithm) uses Q∗Q ^ \ast and replays double Q-learning's exact samples, table selections, and greedy policies with the offset term removed. While both standard Q-learning and double Q-learning (no offset) decrease steadily without exceeding their initial error, double Q-learning undergoes up to 28×28\times transient error amplification before eventually settling over an extended horizon, resulting in a convergence delay.

W2. How does Proposition 2 relate to the experimental settings, and can AT-DQ be validated in the certified regime?: Proposition 2 gives a conservative sufficient condition for worst-case contraction, not a necessary one. The theoretical threshold on τ=β/α\tau = \beta / \alpha 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 τ\tau. There is also a practical trade-off: a very large τ\tau makes Q2Q ^ 2 track Q1Q ^ 1 too closely, which weakens maximization-bias reduction, whereas a smaller τ\tau keeps the two tables separated to suppress bias (Section 8 and Appendix H.1-H.2).

To directly validate Proposition 2 in its certified regime, we added Appendix H.3 (Tables 6 and 7), evaluating two controlled MDPs (MDP1 and MDP2) that satisfy all assumptions of Proposition 2 simultaneously (γ=0.99\gamma = 0.99, uniform stationary occupancy dmax⁡=dmin⁡d _ {\max} = d _ {\min}, α=0.004≤αˉ\alpha = 0.004 \le \bar{\alpha}, β=0.8\beta = 0.8, τ=200\tau = 200). In this certified regime, AT-DQ converges twice as fast as double Q-learning at step size α\alpha, achieves lower value-estimation error when double Q-learning suffers from underestimation bias, and exhibits a steady reduction in residual error as α\alpha decreases at fixed τ=200\tau = 200.

W3. Which problem class satisfies the JSR condition in Theorem 2, and how does an expected-error bound fit the motivation?: To provide an explicit problem class where the JSR condition of Theorem 2 is guaranteed, we added Corollary 1 in Section 6. When γ<1/3\gamma \lt 1/3, a direct row-sum bound shows that every mode in Hα\mathcal{H} _ \alpha satisfies $\Vert H _ \theta(\alpha) \Vert _ \infty \le 1 - \alpha p _ {\min} d _ {\min}(1 - 3\gamma) \lt 1$ for all α∈(0,1)\alpha \in (0, 1), which directly certifies ρα<1\rho _ \alpha \lt 1 with K=1K = 1 and c=pmin⁡dmin⁡(1−3γ)c = p _ {\min} d _ {\min}(1 - 3\gamma). Thus, the augmented family of double Q-learning is automatically JSR-stable in the small-discount regime (γ<1/3\gamma \lt 1/3).

Regarding the motivation, our "worst-case" certificate refers strictly to control-theoretic switching stability across arbitrary policy-switching sequences, while Theorem 2 bounds the expected finite-time estimation error. To avoid any confusion with high-probability Safe RL guarantees, we have removed the "safety-critical" phrasing from the Introduction and Related Work.

W4. How do we separate instability from slow two-table updates, and how does AT-DQ compare against frequency-matched double Q-learning (2α2\alpha) and soft-target Q-learning?: First, as noted in W1, the double Q-learning (no offset) control shares the exact same two-table update schedule and greedy-policy path yet contracts steadily without amplification, confirming that the transient amplification is driven by the signed policy-difference terms rather than the two-table update rate.

Second, in Appendix H.3 (Table 6), we include both double Q-learning with a doubled step size (DQ-2α\text{DQ-}2\alpha, matching the per-table update rate under p1=p2=0.5p _ 1 = p _ 2 = 0.5) and a matched soft-target Q-learning baseline (using the same α,β\alpha, \beta without cross-evaluation). On MDP1, doubling double Q-learning's step size (DQ-2α\text{DQ-}2\alpha) largely closes the convergence-speed gap with AT-DQ, isolating the effect of update allocation; however, on MDP2 (where underestimation bias dominates), DQ-2α\text{DQ-}2\alpha exacerbates the underestimation bias and doubles the tail estimation error relative to standard double Q-learning, whereas AT-DQ maintains a much lower estimation error.

Reviewer_8HfiOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper looks at constant-step-size Double Q-learning using a switching-system formulation. It finds unstable modes in the enlarged matrix family, which means a uniform JSR stability guarantee does not come for free. The authors then propose an asymmetric tracking variant, give stability conditions and finite-time bounds, and test it on several environments.

Critical strengths
  1. The direct representation makes the interaction between the two tables easier to see. It gives useful starting point for studying stability without going through comparison systems (Section 4.2, Theorem 1).

  2. The tracking variant comes with explicit stability conditions and a finite-time bound. This is a concrete result, and I see value in this part of the paper (Proposition 2; Appendices C–D).

Critical weaknesses
  1. Is Example 1 intended to use an arbitrary full-support i.i.d. sampling distribution? Its state marginal is (0.4435, 0.1725, 0.384), whereas the successor-state marginal induced by the stated transitions is (0.107, 0.453, 0.44). These would need to agree for stationary occupancy sampling. Could you clarify how this fits Section 3.5?

  2. The experiments do not test the parameter range covered by Proposition 2. At γ = 0.99, its sufficient condition requires β/α > 198 even with uniform sampling, while the tested ratios only go up to 10. This does not imply that the experimental settings are unstable, but it leaves the practical role of the guarantee unclear (Proposition 2; Section 8; Appendix H).

Questions for authors
  1. Is Example 1 intended to use an arbitrary full-support i.i.d. sampling distribution? Its state marginal is (0.4435, 0.1725, 0.384), while one transition gives (0.107, 0.453, 0.44). Please clarify how this fits the stationary sampling assumption in Section 3.5.

  2. Could you clarify how Proposition 2 relates to the experimental settings? Is there a stability guarantee for the ratios used in the experiments, or should those results be understood as empirical evidence outside the proved conditions?

3 comments

We sincerely thank you for your careful review and constructive feedback. Because the two critical weaknesses and the two questions for authors raise the same two core points, we address them together as W1/Q1 and W2/Q2 below (revisions marked in blue in the PDF).

W1 & Q1. Stationary occupancy in Example 1 and consistency with Section 3.5: Thank you for catching this mismatch. To clearly illustrate the impact of JSR instability in double Q-learning while strictly satisfying the sampling assumption in Section 3.5, we have updated Example 1, Appendix E, and Appendix F with a revised MDP and a stationary sampling distribution DD whose state marginal matches the one-step successor marginal (p⊤Pb=p⊤p ^ \top P _ b = p ^ \top, with d(s,a)>0d(s,a) \gt 0 for all (s,a)(s,a)). Under this stationary setting, the mode generator GθG _ \theta still has a strictly positive eigenvalue (λ+>0\lambda _ + \gt 0), confirming that ρα≥ρ(I+αGθ)>1\rho _ \alpha \ge \rho(I + \alpha G _ \theta) \gt 1 for all α∈(0,1)\alpha \in (0, 1).

In Appendix F (Table 1), we also re-ran the sample-path simulation on this updated MDP starting from identical initial tables (Q01=Q02=Q0Q _ 0 ^ 1 = Q _ 0 ^ 2 = Q _ 0) and compared double Q-learning against double Q-learning (no offset), which removes the offset term from the error update along the exact same trajectory. This control uses Q∗Q ^ \ast 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, resulting in a convergence delay.

W2 & Q2. How Proposition 2 relates to the experimental settings and the practical role of the guarantee: The ratios τ=β/α∈[0.25,10]\tau = \beta / \alpha \in [0.25, 10] in Section 8 and Appendices H.1-H.2 are outside the sufficient condition of Proposition 2 (τ>198\tau \gt 198 at γ=0.99\gamma = 0.99) and should be understood as empirical evaluations outside the proved regime. Proposition 2 gives a conservative sufficient condition for worst-case contraction, not a necessary one, because its proof bounds each matrix block separately using worst-case max norms. In practice, AT-DQ converges stably at much smaller values of τ\tau. There is also a clear practical trade-off: a very large τ\tau makes Q2Q ^ 2 track Q1Q ^ 1 too closely, which weakens maximization-bias reduction, whereas a smaller τ\tau keeps the two tables sufficiently separated to suppress bias.

To directly validate Proposition 2 in its certified regime, we added Appendix H.3 (Tables 6 and 7), evaluating two controlled MDPs (MDP1 and MDP2) that satisfy all assumptions of Proposition 2 simultaneously (γ=0.99\gamma = 0.99, uniform stationary occupancy dmax⁡=dmin⁡d _ {\max} = d _ {\min}, α=0.004≤αˉ\alpha = 0.004 \le \bar{\alpha}, β=0.8\beta = 0.8, τ=200\tau = 200). In this certified regime, AT-DQ converges twice as fast as double Q-learning at step size α\alpha, achieves lower value-estimation error when double Q-learning suffers from underestimation bias, and exhibits a steady reduction in residual error as α\alpha decreases at fixed τ=200\tau = 200.

Thanks for the detailed response and revisions. I think the updated example and additional experiments have addressed my main concerns.

I still have some doubts about how the unstable modes relate to actual Double Q-learning behavior, and whether AT-DQ offers clear advantages over existing methods, especially given the trade-off with maximization bias.

Overall, the paper has improved, but I’ll keep my original rating for now.

Thank you for your time, feedback, and for acknowledging the revisions. We appreciate your perspective on the remaining trade-offs and will keep these points in mind to further clarify the discussion.

Reviewer_4fCeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the stability of Double Q-learning with constant step sizes. The authors model the coupled updates of the two Q-tables as a switched system and use the joint spectral radius to analyze worst-case stability. They derive finite-time error bounds under the stability conditions. The paper also constructs examples of unstable modes within an enlarged set of switching matrices and proposes an asymmetric variant, AT-DQ, in which the second Q-table tracks the first. Explicit sufficient conditions for stability are provided for this variant. Experiments on several tabular reinforcement learning tasks compare learning performance and value estimation bias.

Critical strengths

Modeling the coupled updates as a switched system offers a useful perspective on the stability of Double Q-learning.

The paper provides explicit sufficient conditions for stability and finite-time error bounds. It also evaluates the proposed variant across several tasks and includes an ablation on the tracking step size.

Critical weaknesses

I am not sure what new insights the analysis adds to prior work. The proposed algorithm also resembles target-network tracking updates, so its contribution needs a stronger explanation.

The motivation based on safety-critical systems needs more support. The paper lacks references connecting its stability guarantees to safety concerns, and the experiments do not examine safety constraints or failure risks.

The experimental settings do not satisfy the theoretical conditions. At a discount factor of 0.99, Proposition 2 requires a tracking-to-learning step-size ratio above 198 under uniform sampling, while the experiments use 8 or 0.25. This leaves it unclear how the guarantee helps in practice.

Finding unstable modes in the enlarged switching-matrix set does not mean that Double Q-learning itself is unstable. The paper needs to make this distinction clear and avoid drawing conclusions beyond what the analysis and experiments support.

Questions for authors

Please address the concerns listed under Weaknesses.

5 comments

We sincerely thank you for your careful review and constructive questions. We address W1-W4 below (revisions marked in blue in the PDF).

W1. What new insights does the switching analysis provide, and how does AT-DQ relate to target networks?: Prior switching analyses of double Q-learning (Na & Lee, 2026) relied on auxiliary bounding systems because the error recursion contains a policy-dependent offset term in Eq. (2). Using Lemma 2, Theorem 1 absorbs this offset into the switching matrix and yields an exact linear conditional-mean recursion on the augmented error space. The main insight is structural: unlike standard Q-learning (whose modes are nonnegative and contractive via row sums), double Q-learning introduces signed policy-difference blocks on the diagonal (Remark 1). Consequently, individual modes can have eigenvalues outside the unit disk (Proposition 1 and Example 1), so uniform JSR stability is not automatic.

For AT-DQ, we do not claim that soft target tracking is a new heuristic. Section 7 already describes its connection to Double DQN. Our contribution is showing how this structure resolves the switching instability analytically. In the transformed tracking coordinates, fast tracking isolates the signed policy-difference block and yields an explicit weighted block-norm contraction (Proposition 2) and finite-time bound (Theorem 3), while retaining cross-evaluation to reduce maximization bias.

W2. Why frame the motivation around "safety-critical" systems?: We agree that this phrasing could be misread as Safe RL. 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. We have removed the "safety-critical" phrasing from the Introduction and Related Work.

W3. How do we reconcile the large theoretical ratio τ=β/α\tau = \beta / \alpha in Proposition 2 with the smaller values in experiments?: Proposition 2 gives a conservative sufficient condition for worst-case contraction, not a necessary one. The theoretical threshold on τ=β/α\tau = \beta / \alpha 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 τ\tau. There is also a clear practical trade-off: a very large τ\tau makes Q2Q ^ 2 track Q1Q ^ 1 too closely, which weakens maximization-bias reduction, whereas a smaller τ\tau keeps the two tables sufficiently separated to suppress bias (Section 8 and Appendix H.1-H.2).

To directly validate Proposition 2 in its certified regime, we added Appendix H.3 (Tables 6 and 7), evaluating two controlled MDPs (MDP1 and MDP2) that satisfy all assumptions of Proposition 2 simultaneously (γ=0.99\gamma = 0.99, uniform stationary occupancy dmax⁡=dmin⁡d _ {\max} = d _ {\min}, α=0.004≤αˉ\alpha = 0.004 \le \bar{\alpha}, β=0.8\beta = 0.8, τ=200\tau = 200). In this certified regime, AT-DQ converges twice as fast as double Q-learning at step size α\alpha, achieves lower value-estimation error when double Q-learning suffers from underestimation bias, and exhibits the expected error reduction as α\alpha decreases at fixed τ=200\tau = 200.

W4. Does the mode-wise instability affect actual double Q-learning trajectories?: We agree with this distinction and have revised Example 1 and Appendix F to state our conclusions precisely. Finding an unstable mode in Hα\mathcal{H} _ \alpha (ρα>1\rho _ \alpha \gt 1) means that the enlarged switching family lacks a uniform JSR contraction certificate, not that the actual double Q-learning recursion diverges. Rather, in our sample-path simulations, the signed policy-difference terms that create unstable modes in Hα\mathcal{H} _ \alpha manifest as finite-time transient error amplification and a convergence delay. To verify this mechanism, we updated Example 1, Appendix E, and Appendix F (Table 1) using a stationary i.i.d. distribution DD and identical initial tables (Q01=Q02=Q0Q _ 0 ^ 1 = Q _ 0 ^ 2 = Q _ 0) across 5 seeds and 7 step sizes. We compare double Q-learning against double Q-learning (no offset), which follows the exact same sampled coordinates, table selections, and greedy policies but removes the offset term from the error update. This control uses Q∗Q ^ \ast 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 in this MDP, resulting in a convergence delay.

  1. I understand the authors’ explanation. This response has largely clarified my concern.
  2. I agree with removing the references to “safety-critical applications,” but I remain concerned about the significance of the contribution, as I noted in my original review.
  3. I still have some concerns about the response to this point. I appreciate the additional experiments in Appendix H.3 that satisfy the conditions of Proposition 2. However, both environments use uniform stationary occupancy distributions, which make the sufficient conditions easier to satisfy. The practical relevance of the guarantee therefore remains unclear to me. In particular, please explain why certification and evaluation were not performed on the original tasks. I understand that experimental validation of theoretical results is often constrained by the assumptions, so it would help to clarify whether the main obstacle is the sampling assumptions, visitation frequencies, step-size restrictions, or computational cost. The additional results do not yet sufficiently establish a connection between the theoretical guarantee and the gains reported in the main experiments.
  4. Overall, I broadly accept the distinction the authors have made on this point.

Thank you for the follow-up. We address the remaining concerns below.

Point 3. Why the original tasks were not certified and the role of Proposition 2

The main obstacles on the original tasks are the sampling protocol, nonuniform visitation, and the resulting step-size restrictions, rather than the cost of checking the certificate. The Gym and GridWorld experiments use episodic trajectories with changing exploration policies, which do not satisfy the fixed-distribution i.i.d. sampling assumption in Section 3.5. Roulette uses simultaneous action updates and therefore requires an extension of the single-coordinate analysis.

Nonuniform occupancy also tightens the sufficient condition. For example, at γ=0.99\gamma = 0.99, dmax⁡/dmin⁡=2d _ {\max} / d _ {\min} = 2 requires τ>790.02\tau \gt 790.02, compared with τ>198\tau \gt 198 under uniform occupancy. Because the sampled-update analysis requires β=τα≤1\beta = \tau \alpha \le 1, a larger required ratio restricts α\alpha and may require longer runs. Uniform occupancy is not required by Proposition 2; we chose it in Appendix H.3 to satisfy all assumptions cleanly and evaluate learning within the proved regime.

Regarding the value of Proposition 2 despite its conservatism: in standard double Q-learning, JSR stability is not merely conservative—it can fail for every positive step size α∈(0,1)\alpha \in (0, 1) (Proposition 1, Example 1). Moreover, directly computing the JSR across all policy modes is generally intractable. Proposition 2 resolves both issues by proving that AT-DQ always admits a nonempty constant-step-size regime with guaranteed JSR contraction (ρjsr<1\rho _ {\mathrm{jsr}} \lt 1) for any γ∈(0,1)\gamma \in (0, 1) and dmin⁡>0d _ {\min} \gt 0, certified via a simple closed-form inequality with no JSR computation. While Proposition 2 certifies worst-case stability rather than optimal performance, the Section 8 benchmarks and Appendices H.1-H.2 complement it by evaluating the empirical trade-off between convergence speed and maximization bias at smaller τ\tau.

Point 2. Significance of the contribution

Taken together, the contribution of this paper is establishing an exact switching-stability foundation for double Q-learning: (i) deriving an exact linear conditional-mean switching representation without auxiliary bounding systems (Theorem 1); (ii) showing that cross-evaluation introduces signed policy-difference blocks that break automatic JSR contraction under constant step sizes and induce transient error amplification (Proposition 1, Example 1, Appendix F); and (iii) proving that asymmetric target tracking eliminates these signed blocks in tracking coordinates to restore an explicit JSR certificate and an O(α)O(\sqrt{\alpha}) finite-time error bound (Proposition 2, Theorem 3).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.