Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set

Thank you for your positive evaluation and perfect score for our manuscript. We appreciate the opportunity to clarify the comparison of our tabular $Q$-learning convergence rate with existing literature:

Comparing the convergence rate for the tabular case with existing rates in the literature would be useful. Is the proposed method faster, or is its performance simply comparable to existing approaches?

Comparing our tabular $Q$-learning convergence rate (Theorem 2) with existing literature reveals that our method achieves an $L^2$ rate simply comparable to prior approaches. Theorem 2 shows exponential decay, similar to rates in works like Even-Dar et al. (2003) and Chen et al. (2021), which also exhibit exponential convergence under different assumptions (e.g., count-based rates or fixed policies).

The primary novelty of our result lies not necessarily in achieving a strictly faster rate in terms of the exponent's constants (as comparing these constants, which depend on complex problem parameters like $B_{2,5}$ and $B_{2,6}$ across different analytical frameworks is inherently difficult), but rather in demonstrating this competitive exponential convergence under a practical adaptive $\epsilon$-softmax behavior policy and without using count-based learning rates.

Therefore, while the exponential convergence form aligns with existing benchmarks, the significance stems from achieving this strong type of guarantee under arguably more standard algorithmic settings used in practice. We view our rate as highly competitive, prioritizing the demonstration of robust convergence under these practical conditions.

It would be helpful to update the references to reflect their most recent status.

Thank you for the thoughtful and valuable suggestions. We appreciate the recommendation to update references to their latest status and will ensure all citations reflect the most recent publication details.

Improving the readability of the presentation would be beneficial, especially given the extensive mathematical content.

Improving readability is also a great point, and we will refine the presentation to make the mathematical content more accessible. For example, we will add detailed derivations in the revised Appendix (e.g., Sec C.4) showing how intermediate constants like $D$ combine, considering factors like norm conversions, to form the final $B$ bounds presented in the main theorems.

It would be valuable to include experiments to demonstrate the results. In particular, testing the well-known Baird example of the deadly triad would be interesting.

We do agree experiments would be a great add-on. However, we note that we study exactly the same algorithm as Meyn (2024) and Meyn (2024) already includes extensive experimental validation, including Baird example. We feel there is no need to redo it, as our work focuses on novel convergence rates that complement Meyn's empirical results.

It would be helpful to provide an intuitive explanation for the choice of the specific exploration policy using softmax.

We’re grateful for the suggestion to explain the softmax exploration policy intuitively. The adaptive $\epsilon$-softmax policy choice is technically motivated. Our analysis framework (Theorem 3) requires Lipschitz continuity of the expected update $h(w)$ (Assumption A3/A3'). Our policy ensures this (Lemmas 5, 6), enabling the analysis. Standard $\epsilon$-greedy is discontinuous due to argmax and typically violates this assumption, preventing the direct application of our proof technique. The adaptive temperature $\kappa_w$ is the crucial mechanism ensuring this smoothness holds globally, even if $\\|w\\|$ is large (by making the policy appropriately less sensitive). This is also key to our proof technique. An $\epsilon$-greedy policy would fail to use our novel single-timescale SA result. We will clarify this more in the revision.

We truly appreciate your support and positive evaluation of our research.

We're grateful for your thoughtful inquiry and positive assessment. We address your points below:

Could empirical evidence be provided ...?

This paper studies the same algorithm as Meyn (2024), which already provides extensive empirical results on its behavior. So we feel there is no need to redo it again.

... compare performance with methods using algorithmic modifications.

Thanks for the great suggestion. We will add this comparison in the next version and believe this will be a great add-on. While our theoretical contributions are already significant, this addition should certainly enhance the overall paper.

How should practitioners select $\epsilon$, $\kappa_0$, and $t_0$?

We appreciate this practical query. Since our algorithm aligns with Meyn (2024), practitioners can draw from its empirical insights: $\epsilon \leq 0.2$ ensures stability for high $\gamma$ (e.g., 0.99), per Lemma A.9; $\kappa_0=1$ serves as a reasonable starting point; and for our step size $\alpha_t=\alpha/(t+t_0)^{\epsilon_\alpha}$, we suggest $t_0 \geq 10$ with $\epsilon_\alpha=0.85$ for balance. Our revision will clarify these, blending Meyn’s findings with our theoretical framework.

For linear $Q$-learning, what are the implications of converging to a bounded set and the quality of policies?

Thanks for this insightful question. The immediate implication is that we now know that the variance of the parameters is uniformly bounded across time steps. Assessing the quality of the learned policy is challenging without making further artificial assumptions (see Meyn (2024) for more discussion) and is indeed an opportunity for future work.

How does it scale to high dimensions or non-linear methods?

The approach scales to high-dimensional linear settings. Theorem 1 holds regardless of dimension $d$. The adaptive temperature $\kappa_w$ is crucial, ensuring sufficient smoothness (Lemmas 5, 6) and controlled exploration even if weight norm $\\|w\\|_2$ grows large.

Extending to non-linear methods (e.g., neural networks) is feasible if we would like to introduce overparameterized networks and do linearization around initial weights (cf. Cai (2019)). We will additionally have some terms controlled by the width of the network. We believe such an extension is mostly a matter of labor and won't shed new technical insights.

Ref: Q. Cai et al. Neural Temporal-Difference Learning Converges to Global Optima. Advances in Neural Information Processing Systems, 32, 2019.

Could it extend to Expected SARSA or Q($\lambda$)?

For Expected SARSA, Yes. Replacing $\max_a$ with an expectation over $\mu_w$ (for on-policy) or some $\pi_w$ (for off-policy) fits our framework (Theorem 3), maintaining Lipschitz continuity (Lemma 5). For Q($\lambda$), the existence of off-policy eligibility traces will significantly complicate the behavior of the chain (we have to construct an auxiliary chain to contain the trace). But we envision the techniques from Yu (2012) can help.

Ref: H. Yu. Least squares temporal difference methods: An analysis under general conditions. SIAM Journal on Control and Optimization, 2012.

The constants in the bounds are not fully characterized. How tight/optimal are the rates?

Thank you for raising this point. We will revise the Appendix to show how intermediate constants(e.g., $D$) combine into the final $B$ bounds presented in the main theorems, accounting for norm conversions.

Tightness is unclear due to unknown parameters and RL’s hardness with linear function approximation (cf. Liu (2023)). We offer the first $L^2$ rates for linear Q-learning under weak assumptions as a benchmark. Liu (2023) suggests polynomial convergence is unlikely, supporting our state-of-the-art rates. For tabular Q-learning, we improve prior work with an $\epsilon$-softmax policy, without count-based steps. Optimality remains open.

Ref: Liu, S. et al. Exponential hardness of reinforcement learning with linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory (pp. 1588-1617). PMLR.

Limited discussion on adaptive $\epsilon$-softmax vs $\epsilon$-greedy and why adaptive temperature is crucial.

The motivation for not using the $\epsilon$-greedy policy is detailed at the very end of our response to the 2nd reviewer (bV3r). In short, it's because argmax is discontinuous.

The adaptive temperature $\kappa_w$ further ensures the required smoothness beyond continuity, even when $\\|w\\|$ is large. This smoothness allows us to apply our analysis framework (Theorem 3) to prove $L^2$ rates. We will add this discussion in the revision.

Thank you again for the constructive feedback and positive evaluation. We hope these responses have adequately addressed your insightful questions.

Thank you for the constructive feedback and careful reading of our manuscript, which has improved our manuscript. We will incorporate your suggestions into the revised version. Below are our responses:

Assumption A1 seemed non-trivial, and the citation to Zhang (2021) Lemma 9 appears incorrect.

We apologize for the confusion. In short, Lemma 9 of Zhang (2021) is not meant to verify A1.

A1 is much more trivial than it looks like. To our knowledge, A1 has been used at least three times previously: (1) A3.1 and A3.2 in Zhang et al. (2022) JMLR, (2) A5.1 in Zhang et al. (2021) ICML, and (3) Marbach & Tsitsiklis (2001) (TAC) (same concept with different wording). A1 is readily satisfied under simple conditions, e.g., when our Assumption A3.1 (ergodicity under the uniform random policy) holds and an exploring policy (like $\epsilon$-greedy or $\epsilon$-softmax with $\epsilon > 0$) is used. The intuition is that $\epsilon > 0$ ensures that all the state-action transition matrices in the closure share the same connectivity, i.e., any policy in that closure will choose all actions with a strictly positive probability. So all transition matrices share the same ergodicity with the uniform random policy. Our verification of A1 is in Line 332 - 346. This is also how Zhang et al. (2021, 2022) verify this assumption, see more discussion in Zhang (2022) in the text below their A3.2 and A4.4. We will add more details in the revision.

Lemma 9 of Zhang (2021) states the Lipschitz continuity of the stationary distribution w.r.t. the policy parameters under their A5.1. We restate it as our Lemma 15. We will clarify this further in our revision.

Ref: Marbach, P. and Tsitsiklis, J. N. Simulation-based optimization of markov reward processes. IEEE Transactions on Automatic Control, 2001.

Lemma 6 uses norm equivalence; does this require finite state and action spaces, and is this assumption necessary?

Yes and yes. Analyzing the underlying time-inhomogeneous Markov chain in a general state space is inherently difficult, even if it is compact. We need to introduce lots of (hard to verify) assumptions to ensure uniform mixing and will complicate the presentation a lot, especially as key constants like $β$ depend on $\log |\mathcal{A}|$, posing challenges for infinite action spaces.

The final bound in Lemma 7's proof seems inconsistent, particularly for the case where $\\|w\\|\_2 < 1$.

Thanks for spotting this oversight. In the case when $\\|w\\|\_2 \leq 1$, we have $\\|w\\|^2\_2\leq \\|w\\|\_2$, which then gives us $\langle w, A(w)w + b(w)\rangle \leq (C_{7,1} + C_{7,2})\\|w\\|\_2 \leq -\beta \\|w\\|^2\_2 + (C_{7,1} + C_{7,2} + \beta)\\|w\\|\_2$. Thus, we can redefine $C_7 = C_{7,1} + C_{7,2} + \beta$ to ensure $\langle w, A(w)w + b(w)\rangle \leq -\beta \\|w\\|^2\_2 + C_7\\|w\\|\_2$ for both cases. We will correct this definition in the next version.

Typo in an exponent's base on page 19.

You are correct. The base of the exponent should be $(\frac{t_0+\bar{t}}{t+t_0}) ^{D_{1,2}\alpha}$. We will correct the term and subsequent constant $D_{1,3}$ in the revised manuscript.

Details are needed on how the conditions for Gronwall's inequality are met in the final step of Theorem 1's proof.

Thank you for questioning about the proof details. Below, we provide a detailed explanation to address this concern, and we will include this in Section C.4 of the revised manuscript. Starting from the update of $w_{t+1}$, we have $\\|w_{t+1}\\|\leq \\|w_t\\| + \alpha_t \\|H(w_t,Y_{t+1})\\|\\\\ \leq \\|w_t\\| + \alpha_t C_{18}(\\|w_t\\|+1)$.

That is, $\\|w_{t+1}\\| \leq \alpha_0 C_{18} + \sum_{i=0}^t(\alpha_0 C_{18}+1)\\|w_i\\|$. Applying discrete Gronwall inequality, we obtain $\\|w_{\bar{t}}\\| \leq (C_{18} + \\|w_0\\|) \exp(\sum_{t=0}^{\bar{t}-1} (1+\alpha_0 C_{18})) = (C_{18} + \\|w_0\\|) \exp(\bar{t}+\bar{t}\alpha_0 C_{18})$.

Furthermore, combining this with the bound on $B_{1,3}$ from Section C.4, we have $B_{1,3} = 2\left(\frac{D_{1,3}}{(t + t_0)^{D_{1,2} \alpha}}\times 2C_{18} \exp(2\bar{t}+2\bar{t}\alpha_0 C_{18})+D_{1,4}\right)$, where $D_{1,4}$ is a constant bounded in Section C.4. We will include this detailed derivation in the revised manuscript.

An inequality involving $\frac{1}{k^\epsilon}$ on page 20 seems incorrect.

Thank you for this precise catch. We will correct it by introducing an appropriate constant factor $2^{\epsilon_\alpha}$ and update Appendix C.4 accordingly.

It would strengthen the paper to explain why the analysis doesn't apply to epsilon-greedy policies.

We agree with this suggestion. The argmax makes the $\epsilon$-greedy policy discontinuous. This means the stationary distribution is also discontinuous in $w$, violating the Lipschitz continuity needed for $h(w)$ (Assumption A3/A3'). Our adaptive $\epsilon$-softmax policy is smooth by design, satisfying this requirement.

We hope these responses address your points and you could consider updating your evaluation.

Thank you for your valuable feedback and positive evaluation. We appreciate the opportunity to address the specific questions and comments.

Hardness results in Liu (et al., 2023).

Thanks for the excellent suggestion. The hardness results indeed provide key context and may suggest that convergence to a set with the current rate might be the best we can hope. We will add this discussion and cite Liu et al. (2023) in Section 4 in next version.

Large constant ... making the non-asymptotic rates potentially no more informative than Meyn's (2024) asymptotic result.

We understand the concern but want to make two points. (1) Meyn's results are only almost sure boundedness and convey no information about the variance. Even ignoring the rates, our results still provide a uniform bound of the variance across time steps. We argue that this is already valuable. (2) Although the constant is large, we argue it's the first result of this kind. It provides an explicit exponential decay rate, showing the dependency on key factors like $\gamma$, step-size, and exploration parameters ($\epsilon$, $\kappa_0$). We believe this will lay a foundation for future refinements.

Notation discrepancy for constants between the main text (using B) and the Appendix (using D).

Thanks for noting this. We use $B$ for main theorem constants and $D$ for intermediate ones in the Appendix. Some translation uses the equivalence between norms. We will clarify all these in next version.

Is it possible to provide some bounds on the value of a constant $\beta$?

We appreciate the suggestion. We adopt the explicit bound for $\beta$ from Meyn (2024), Lemma A.9: $\beta = \left[ (1 - \gamma) - \epsilon \gamma \sqrt{\epsilon^{-1} + (1 - \epsilon)^{-1}} \right] \lambda_{\min}(X^\top D_{\mu_w} X) - \gamma (1 - \epsilon) \frac{\log (|\mathcal{A}|)}{\kappa_0} \sqrt{\lambda_{\max}(X^\top D_{\mu_w} X)}$, where $\lambda_{\min}(\cdot)$ and $\lambda_{\max}(\cdot)$ namely denote the minimal and maximal eigenvalue of the matrix. This bound is positive for sufficiently small $\epsilon$ and large $\kappa_0$. We will add this to the revised manuscript (Appendix C.3).

Could you provide an exact value of the constant $B_{1,3}$ in the main text?

Thank you for the suggestion. We have $B_{1,3} \leq 2\left(\frac{D_{1,3}}{(t + t_0)^{D_{1,2} \alpha}}\times 2C_{18} \exp(2\bar{t}+2\bar{t}\alpha_0 C_{18})+D_{1,4}\right)$, where the parameters $D_{1,3}$, $D_{1,2}$, $C_{18}$, $D_{1,4}$, $t_0$, and $\alpha$ are fixed constants from our analysis. Those constants are well defined and we can easily assemble them. We will add this in the revision but unfortunately we cannot display it here right now because it's too long.

Thanks again for your helpful questions, which have allowed us to enhance the technical clarity of our manuscript. We hope these responses fully address your points.