Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes

We thank the reviewer for the encouraging comments regarding the contributions of this work. Please find our point-by-point responses to all the questions below.

Question: Theorem 3.1 makes no assumptions on the initial point $Q_1$. Should the constant in the upper bound therefore depend on $p_{span}(Q_1)$ (or a comparable measure of its magnitude)?

Response: The reviewer is absolutely correct. To clarify, our finite-time bound is different for $k \leq K$ and $k \geq K$, where $K$ is a threshold that roughly captures the mixing of the Markov chain {$(S_k, A_k)$} induced by the behavior policy $\pi$. For $k \leq K$, we bound $p_{span}(Q_k - Q^\star)$ as

$p_{span}(Q_k - Q^\star)\leq p_{span}(Q_k) + p_{span}( Q^\star )\leq b_k+p_{span}(Q^\star)=m_k$,

where $b_k$ is the time-varying almost-sure bound of $p_{span}(Q_k)$ established in Proposition B.1, and $m_k$ is defined right before Theorem 3.1. Note that in the proof of Proposition B.1, we assume without loss of generality that $p_{span}(Q_1) = 0$, which will be made explicit in the next version of this work. This can be easily achieved by initializing $Q_1$ as a constant vector.

As for $k \geq K$ (which is the more interesting case), the bound naturally depends on the "initial error" $p_{span}(Q_K - Q^\star)$. However, because $Q_K$ is inherently random, to maintain the mathematical rigor of our result, we apply the following inequality to ensure that the bound does not depend on random quantities:

$p_{span}(Q_K - Q^\star) \leq p_{span}(Q_K) + p_{span}(Q^\star) \leq b_K + p_{span}(Q^\star) = m_K$,

which is the term that multiplies the leading factor in all cases of Theorem 3.1.

To summarize, if one accepts having $p_{span}(Q_K - Q^\star)$ in the finite-time bound, one can simply replace $m_K$ by $\mathbb{E}[p_{span}(Q_K - Q^\star)^2]$ in Theorem 3.1 so that the theorem captures the dependence on the "initial error" $Q_K - Q^*$.

Question: This work focuses on the adaptive stepsize: $\alpha_k(s, a) = \alpha / (N_k(s, a) + h)$ and achieves a $O(1/k)$ convergence rate with some condition on $\alpha$. In the Markovian-SA literature (e.g. [21]), one can obtain $O(1/k^\xi)$ for $0 < \xi < 1$ with a broader rule of stepsize $\alpha_k = \alpha / (k + h)^\xi$ without imposing extra conditions on $\alpha$. Would it be straightforward, or are there hidden technical obstacles, to extend your proof to the more robust choice, with no extra conditions on $\alpha$?

Response: This is a very good question. We next elaborate on the algorithmic design of Q-learning under alternative choices of adaptive stepsizes, which is not as straightforward as directly setting $\alpha_k(s,a) = \alpha / (N_k(s,a) + h)^\xi$. We then discuss the potential challenges that arise from the analysis.

We start with Eq. (9) from the submission:

$Q_{k+1}(s,a) = Q_k(s,a) + \tilde{\alpha}_k \cdot \frac{\mathbb{1}{(S_k, A_k) = (s,a)}}{D_k(s,a)} \cdot \delta_k$

where $D_k$ is the empirical frequency matrix and $\delta_k$ denotes the temporal difference. As illustrated in Section 4.2, the above equation is the correct way of viewing average-reward Q-learning, where $D_k$ serves as implicit importance sampling. When choosing $\tilde{\alpha}_k = \alpha / (k + h)$, we arrive at the Q-learning algorithm presented in this work. However, we can also set $\tilde{\alpha}_k$ to be either a polynomial stepsize or a constant stepsize, as illustrated below.

Polynomial stepsizes: Analogous to using $\alpha_k = \alpha / (k+h)^\xi$ in Markovian stochastic approximation, by setting $\tilde{\alpha}_k = \alpha / (k+h)^\xi$, we arrive at the following Q-learning algorithm:

$Q_{k+1}(s,a) = Q_k(s,a) + \frac{\alpha}{(k + h)^\xi} \cdot \frac{\mathbb{1}_{{(S_k, A_k) = (s,a)}}}{D_k(s,a)} \cdot \delta_k = Q_k(s,a) + \frac{\alpha \cdot (k + h)^{1 - \xi}}{N_k(s,a) + h} \cdot \mathbb{1} _{(S_k, A_k) = (s,a)} \cdot \delta_k$,

where we recall that $D_k(s,a) = (N_k(s,a) + h)/(k + h)$. In this case, the algorithm can be viewed as using adaptive stepsizes of the form $\alpha_k(s,a) =\alpha (k + h)^{1 - \xi}/(N_k(s,a) + h)$. When using this stepsize, we expect similar convergence behavior as in Markovian stochastic approximation with $\alpha_k = \alpha / (k + h)^\xi$, robustly achieving an $\mathcal{O}(1 / k^\xi)$ rate of convergence independent of the choice of $\alpha$.

Constant stepsizes: Similarly, by setting $\tilde{\alpha}_k \equiv \alpha$ in Eq. (9), we obtain:

$Q_{k+1}(s,a) = Q_k(s,a) + \alpha \cdot \frac{\mathbb{1}{{(S_k, A_k) = (s,a)}}}{D_k(s,a)} \cdot \delta_k = Q_k(s,a) + \frac{\alpha \cdot (k + h)}{N_k(s,a) + h} \cdot \mathbb{1}_ {(S_k, A_k) = (s,a)} \cdot \delta_k$

In this case, the adaptive stepsize can be understood as $\alpha_k(s,a) = \alpha (k + h)/(N_k(s,a) + h)$. When using this stepsize, we expect similar convergence behavior as in Markovian stochastic approximation with constant stepsize, achieving geometric convergence to a ball with radius proportional to $\alpha$. Moreover, we expect that existing studies on constant stepsize Markovian stochastic approximation [32,81]—such as using Polyak averaging for variance reduction, RR-extrapolation for asymptotic bias reduction, and weak convergence behavior—are extendable to our setting.

Challenges in the Analysis: To extend our result to the above variants of adaptive stepsizes, one must address the challenge of non-Markovian noise introduced by the use of adaptive stepsizes, as in this work. Another challenge we anticipate is that $\alpha_k(s,a)$ may not lie in the interval $(0,1)$. Specifically, when using $\alpha_k(s,a) = \alpha / (N_k(s,a) + h)$, as long as $h \geq \alpha$, the stepsize is always in the interval $(0,1)$ with probability one. However, when using the above variants—for example, $\alpha_k(s,a) = \alpha (k + h)/(N_k(s,a) + h)$—no matter how small $\alpha$ is, $\alpha_k(s,a)$ lies in $(0,1)$ only with high probability for any fixed large enough $k$. Nevertheless, we do not expect this is a fundamental challenge and anticipate that it can be overcome with some careful Markov chain concentration analysis.

Question: I understand that convergence in a semi-norm guarantees only convergence to a set, the paper would benefit from a discussion of how your techniques could be adapted—either through algorithm design or deeper analysis—to produce a consistent estimate of the true $Q^\star$.

Response: This is an excellent question. For the current algorithm design, we do not expect pointwise convergence. To achieve this, recall the algorithm design for classical RVI Q-learning [1] (see also the last paragraph in Section 3.1 of our submission). By subtracting an offset $f(Q)$ within the temporal difference, RVI Q-learning achieves pointwise convergence to a solution $Q' \in \mathcal{Q}:=Q^\star +$ {$ce \mid c \in \mathbb{R}$} satisfying $f(Q') = r^*$. We believe similar ideas could be incorporated into our algorithm to achieve pointwise convergence to some point in $\mathcal{Q}$, though convergence to the exact $Q^\star$ may not be guaranteed. This is an interesting future direction.

That being said, as the goal of Q-learning is to find an optimal policy by choosing actions greedily based on the output Q-function estimate, an error in the direction of the all-ones vector does not matter, and achieving set convergence to $\mathcal{Q}$ (or equivalently, convergence in $p_{span}(\cdot)$ to $Q^*$) is sufficient.

Comment: The main weaknesses, in my opinion, are limited theoretical novelty and overly strong theoretical assumptions.

Response: We thank the reviewer for the comments. While we agree that Assumption 2.1 is indeed a strong assumption, we believe the reviewer may have misunderstood the nature of our technical contributions. Below, we provide a detailed point-by-point response to the reviewer's concerns.

Comment: Assumption 2.1 being strong, which is also related to the question of relaxing Assumption 2.1.

Response: We agree with the reviewer that Assumption 2.1 is stronger than assuming uniform ergodicity of the transition kernel, in the sense that uniform ergodicity only implies a multi-step contraction of the Bellman operator, not a single-step contraction.

Note that such a multi-step contraction property has been used in the existing study of synchronous Q-learning [80], where a stochastic estimator of the multi-step Bellman operator is obtainable precisely due to the availability of a generative model that enables free i.i.d. sampling. However, in the much more challenging asynchronous setting, to our knowledge, no techniques have been developed (and in our opinion, such techniques may be impossible) to obtain an estimator of the multi-step Bellman operator, due to the presence of only a single trajectory of samples and the nonlinearity of the Bellman operator. Therefore, having a multi-step contraction (implied by uniform ergodicity) does not benefit the analysis, and we view our assumption as somewhat necessary if one wishes to study Q-learning from a span-seminorm contractive stochastic approximation perspective.

That being said, as mentioned in the conclusion of this work, relaxing such an assumption to more realistic ones—such as the MDP being weakly communicating—would require completely abandoning the contractive viewpoint of the Bellman operator and instead studying Q-learning as a stochastic approximation with a non-expansive operator (which always holds). To our knowledge, a finite-time analysis of asynchronous Q-learning from this perspective does not yet exist in the literature and is, in fact, the next step of this line of work.

Comment: The theoretical novelty of this work, especially relative to [21].

Response: We thank the reviewer for raising this comment. To clarify, the technical contributions of this work are in fact significant and do not follow directly from, nor are they a minor extension of, [21, 22]. We have highlighted the unique technical challenges and our techniques in multiple places throughout the paper: in the second paragraph of the abstract, as a bullet point in Section 1 (the last paragraph), in the proof sketch in Section 5, and in the full proof in Appendix B, especially Appendix B.3. Next, we elaborate in more detail our technical contributions relative to [21]. Note that [22] is not particularly relevant, as it studies concentration bounds for norm-contractive stochastic approximation with i.i.d. noise, whereas this work studies mean-square bounds for average-reward Q-learning with adaptive stepsizes, which is inherently a seminorm-contractive stochastic approximation with non-Markov noise.

In general, to perform a finite-time analysis of a stochastic approximation algorithm using a Lyapunov-drift argument, there are two main steps in the proof:

(1) constructing a valid Lyapunov function and showing that the "deterministic" part of the algorithm induces a negative drift with respect to this Lyapunov function;

(2) showing that the errors due to discretization and, more importantly, stochasticity are dominated by the negative drift.

As for part (1), due to the seminorm-contractive property of the Bellman operator, a valid Lyapunov function based on the generalized Moreau envelope has already been constructed in the literature. Therefore, as clearly stated on page 9, line 353 of the submission—"inspired by [18, 21, 24, 81],..."—we do not claim any technical contribution in constructing a valid Lyapunov function; this credit goes to [21].

Part (2)—i.e., controlling the error due to stochasticity—is where the unique challenges arise in Q-learning with adaptive stepsizes. In the existing literature, when the noise sequence is i.i.d., a martingale, or forms a uniformly ergodic Markov chain, the stochastic error can be handled either through a simple conditioning argument (in the i.i.d. and martingale cases) or through a more sophisticated conditioning argument based on mixing time (in the Markovian case), as used in [21]. However, in our case, due to the use of adaptive stepsizes (which, as illustrated in Section 4, are necessary) that depend on the entire history of the sample path, the Q-learning algorithm—viewed as a stochastic approximation—is not even Markovian. This leads to the unique technical contribution of this work: handling non-Markovian noise within Q-learning.

The first step in our proof (illustrated in detail in Section 5, line 339) is to reformulate the algorithm as a Markovian stochastic approximation. Specifically, we reformulate the Q-learning algorithm as a Markovian stochastic approximation driven by the Markov chain {$Z_k = (D_k, S_k, A_k, S_{k+1})$}, where $D_k$ is the empirical frequency matrix and $(S_k, A_k, S_{k+1})$ captures the latest transition. However, while {$Z_k$} is a Markov chain, it is time-inhomogeneous and lacks geometric mixing—precisely due to incorporating $D_k$ into its definition. This is discussed in detail in Appendix B.1. Note that geometric mixing is typically required in the existing literature on Markovian stochastic approximation [65].

To further handle the time-inhomogeneous Markovian noise {$Z_k$}, we developed an approach based on first showing that the stochastic iterate $Q_k$, while not uniformly bounded by a constant (in stark contrast to discounted Q-learning [29]), satisfies a time-varying almost-sure bound that grows at most logarithmically with $k$ (cf. Proposition B.1). These two properties (i.e., almost-sure bound + logarithmic growth) enable us to decouple the iterate $Q_k$ from the time-inhomogeneous Markovian noise $Z_k$. After decoupling, we handle the randomness in $Z_k = (D_k, S_k, A_k, S_{k+1})$ separately, where two challenges arise: (1) the correlation between $D_k$ and $(S_k, A_k, S_{k+1})$, and (2) the presence of the empirical frequency $D_k(s,a)$ in the denominator of the algorithm update, which breaks linearity. To address the first challenge, we use a conditioning argument based on the fast mixing of $(S_k, A_k, S_{k+1})$ (cf. Assumption 3.2). To tackle the second, we employ Markov chain concentration inequalities and the $\mathcal{L}^2$ weak law of large numbers for functions of Markov chains. This is illustrated at a high level in Section 5 and elaborated in detail with clear intuition in Appendix B.3.

Overall, we believe that the technical novelties of this work—specifically, handling non-Markovian noise in Q-learning with adaptive stepsizes—represent a significant contribution. In addition to the technical contributions, the conceptual contributions of this work are also noteworthy. In particular, identifying the necessity of using adaptive stepsizes and leveraging them as a means of implicit importance sampling are important insights for the future study of the reinforcement learning community.

Comment: Numerical simulations and practical implementations of Q-learning

Response: We will add numerical experiments to verify the performance of Q-learning with adaptive stepsizes in the next version of this work.

Minor points Line 132: I do not understand where "(to be discussed shortly)" refers to

Response: It refers to the paragraph after Assumption 2.1, where we discuss the seminorm contraction of the Bellman operator. We will make this clearer in the next version of this work.

Question: Assumption 3.1 requires a fixed behavioral policy with full support. In practice, behaviour policies are often learned, sometimes in a particular parametric family. How the derived bounds scale with the minimum visitation probability of a state-action pair $(s,a)$, that is, with $\min_{s,a}\pi(a|s)$?

Response: The minimum visitation probability appears in our finite-time bound in the form of $D_{\min} := \min_{s,a} \mu(s)\pi(a|s)$ (see the definitions of the constants $C_1$ and $C_2$ in Theorem 3.1), where $\mu$ is the stationary distribution of the Markov chain {$S_k$} induced by the behavior policy $\pi$. The parameter $D_{\min}$ appears inversely and quadratically in the sample complexity bound stated in Corollary 3.1.1.

Assuming a fixed behavior policy that induces a uniformly ergodic Markov chain is common even in existing studies of discounted Q-learning [45]. In contrast, Q-learning with a learned (and potentially time-varying) policy is often studied in the context of regret; see [3] and the work of Jin et al., "Is Q-learning provably efficient?" Advances in Neural Information Processing Systems 31 (2018), which differs from the focus of this work—namely, establishing last-iterate convergence rates measured in the span seminorm.

We thank the reviewer for the encouraging comments regarding the significance of the contributions of this work. In the following, we provide a point-by-point response to all of the reviewer's comments.

Comment: Assumption 2.1 is a strong assumption that is not satisfied in many of the more general classes of MDPs and is crucial to the convergence guarantees of the algorithm.

Response: We agree with the reviewer that Assumption 2.1 is a strong assumption. The next step in this line of work is to remove this assumption by considering stochastic iterative algorithms under non-expansive operators, which would allow us to relax it to weakly communicating MDPs. That said, as acknowledged by the reviewer, this paper has already overcome several major conceptual and technical challenges—such as identifying the necessity of using adaptive stepsizes, leveraging adaptive stepsizes as a means of implicit importance sampling, and handling non-Markovian noise—to achieve the main result. Relaxing Assumption 2.1 is an interesting future direction, but it is beyond the scope of this work.

Question: What about the distance between the two sets of fixed points described in Proposition 4.1? (For instance, with a universal stepsize schedule such as $\alpha_k=c/k$)?

Response: This is an excellent question. Before going into the details, we would like to clarify that, regardless of the number of iterations we run, Q-learning with universal (respectively, adaptive) stepsizes can only converge to the set of solutions to the asynchronous Bellman equation $p_{span}(\bar{\mathcal{H}}(Q) - Q) = 0$ (respectively, the original Bellman equation $p_{span}(\mathcal{H}(Q) - Q) = 0$). Recall that the sets of solutions to $p_{span}(\bar{\mathcal{H}}(Q) - Q) = 0$ and $p_{span}(\mathcal{H}(Q) - Q) = 0$ are of the forms $\bar{Q}^\star +${$ce \mid c \in \mathbb{R}$} and $Q^\star +${$ce \mid c \in \mathbb{R}$}, which are identical when $D = I / (|\mathcal{S}||\mathcal{A}|)$ (cf. Proposition 4.1). Therefore, to conduct the sensitivity analysis, it is enough to bound $p_{span}(\bar{Q}^\star - Q^\star)$ as a function of $D$.

Since the asynchronous Bellman operator $\bar{\mathcal{H}}(\cdot)$ is defined as $\bar{\mathcal{H}}(Q) = (I-D)Q + D\mathcal{H}(Q)$ (see Eq. (5) of the submission), if $p_{span}(\bar{\mathcal{H}}(\bar{Q}^\star) - \bar{Q}^\star) = 0$, there must exist some $c \in \mathbb{R}$ such that

$\bar{\mathcal{H}}(\bar{Q}^\star) - \bar{Q}^\star=D(\mathcal{H}(\bar{Q}^\star) - \bar{Q}^\star) = ce \quad \Leftrightarrow \quad \mathcal{H}(\bar{Q}^\star) - \bar{Q}^\star = c D^{-1} e$,

where $e$ is the all-ones vector. On the other hand, we know that

$\mathcal{H}(Q^\star) - Q^\star = r^\star e$.

Taking the difference of the above two equations, we obtain

$\bar{Q}^\star - Q^\star = \mathcal{H}(\bar{Q}^\star) - \mathcal{H}(Q^\star) + r^\star e - c D^{-1} e$.

Taking the span seminorm on both sides and using the facts that $\mathcal{H}(\cdot)$ is a $\beta$-contraction with respect to $p_{span}(\cdot)$ and $\text{ker}(p_{span}) =${$ce \mid c \in \mathbb{R}$}, we conclude that

$p_{span}(\bar{Q}^\star - Q^\star) \leq \frac{|c| \cdot p_{span}(D^{-1} e)}{1 - \beta}$.

To interpret the result, consider the special case where $D = I / (|\mathcal{S}||\mathcal{A}|)$, in which case the right-hand side vanishes and we conclude that $p_{span}(\bar{Q}^\star - Q^\star) = 0$, implying that the solution sets to $p_{span}(\bar{\mathcal{H}}(Q) - Q) = 0$ and $p_{span}(\mathcal{H}(Q) - Q) = 0$ are the same. This agrees with Proposition 4.1. More generally, when $D \neq I / (|\mathcal{S}||\mathcal{A}|)$, the above inequality provides a sensitivity analysis. We will add the above result to the next version of this work.

As a follow-up to this comment, we note that the ultimate goal of reinforcement learning is not to find $Q^\star$ per se, but to identify an optimal policy $\pi^\star$. Therefore, even if $p_{span}(\bar{Q}^\star - Q^\star) \neq 0$, Q-learning with universal stepsizes could still be acceptable if the greedy policy induced by $\bar{Q}^\star$ is optimal (or close to optimal). Unfortunately, we have constructed a two-state, two-action MDP that demonstrates this is, in general, not the case. Due to space limitations, we are unable to include the example here, but we will add it in the next version of the paper (or during the discussion phase, if the reviewer is particularly interested).

Question: Could the authors provide any commentary on aspects of the proof of the main theorem that are suboptimal (in terms of leading to a suboptimal sample complexity)?

Response: This is a very good question. We agree with the reviewer that the sub-optimality arises from both algorithmic design choices (e.g., without using variance reduction techniques) and artifacts of our proof. Regarding potential looseness in the analysis, we identify two main sources.

The almost sure bound on $p_{span}(Q_k):$ As highlighted in Sections 1, 3, and 5, a major technical challenge in the analysis is handling the non-Markovian noise introduced by the use of adaptive stepsizes. In Section 5.1, we reformulate the algorithm as a Markovian stochastic approximation by incorporating the empirical frequency matrix $D_k$ into the definition of the Markov chain. However, the resulting chain {$Z_k$} lacks geometric mixing, which is typically used in the literature to handle Markovian noise—i.e., to break the correlation between the stochastic iterates $Q_k$ and the Markov noise $Z_k = (D_k, S_k, A_k, S_{k+1})$.

To address this issue, our approach—detailed in Section 5.3—first establishes that while the iterates $Q_k$ do not admit a uniform bound as in the discounted setting, they do admit a time-varying almost-sure bound that grows at most logarithmically in $k$ (cf. Proposition B.1). The proof of Proposition B.1 is nontrivial: it involves an induction argument to bound $p_{span}(Q_{k+1})$ in terms of $p_{span}(Q_k)$ and a combinatorial argument to identify the worst-case scheduling of adaptive stepsizes that leads to the maximal upper bound.

Unfortunately, this time-varying bound (denoted $b_k$) stated in Proposition B.1 scales as $b_k = \mathcal{O}(|\mathcal{S}||\mathcal{A}|\log k)$. Since $b_k$ appears quadratically in the finite-time analysis, this introduces an additional $\mathcal{O}(|\mathcal{S}|^2|\mathcal{A}|^2)$ dependence in the sample complexity. Intuitively, the almost-sure time-varying bound on $Q_k$ should not exhibit any $|\mathcal{S}||\mathcal{A}|$ dependence, as we use $p_{span}(\cdot)$ as the measure. Note that $p_{span}(\cdot)$ can be viewed as a projection with respect to the $||\cdot||_\infty$ norm (cf. Lemma 2.1), which does not depend on the dimension of the vector. However, rigorously proving that $b_k$ is independent of $|\mathcal{S}||\mathcal{A}|$—that is, refining the analysis in Proposition B.1—appears to be significantly more challenging due to the use of adaptive (stochastic) stepsizes.

The variance analysis: To further mitigate the dependence on the size of the state-action space and $1/(1-\beta)$, we note that the existing literature has employed advanced concentration inequalities—such as Freedman’s inequality [45] and Bernstein's inequality [46]—to refine the analysis of the indicator function of the Markov chain {$(S_k, A_k)$} in asynchronous Q-learning. In contrast, our Lyapunov-based technique for mean-square analysis does not exploit such techniques.

Question: Could the theorem statement be refined to provide a guarantee that depends on the fixed-point residual of the initialization $Q_1$ or its distance from a fixed-point? (Would such a term replace some factors of $1/(1-\beta)$?)

Response: The reviewer is absolutely correct. To clarify, our finite-time bound is different for $k \leq K$ and $k \geq K$, where $K$ is a threshold that roughly captures the mixing of the Markov chain {$(S_k, A_k)$} induced by the behavior policy $\pi$. For $k \leq K$, we bound $p_{span}(Q_k - Q^\star)$ as

$p_{span}(Q_k - Q^\star)\leq p_{span}(Q_k) + p_{span}( Q^\star )\leq b_k+p_{span}(Q^\star)=m_k$,

where $b_k$ is the time-varying almost-sure bound of $p_{span}(Q_k)$ established in Proposition B.1, and $m_k$ is defined right before Theorem 3.1. Note that in the proof of Proposition B.1, we assume without loss of generality that $p_{span}(Q_1) = 0$, which will be made explicit in the next version of this work. This can be easily achieved by initializing $Q_1$ as a constant vector.

As for $k \geq K$ (which is the more interesting case), the bound naturally depends on the "initial error" $p_{span}(Q_K - Q^\star)$. However, because $Q_K$ is inherently random, to maintain the mathematical rigor of our result, we apply the following inequality to ensure that the bound does not depend on random quantities:

$p_{span}(Q_K - Q^\star) \leq p_{span}(Q_K) + p_{span}(Q^\star) \leq b_K + p_{span}(Q^\star) = m_K$,

which is the term that multiplies the leading factor in all cases of Theorem 3.1. Moreover, to make the sample complexity bound instance-independent, we further upper bound $p_{span}(Q^*)$ by $1/(1 - \beta)$ in Corollary 3.1.1 when computing the sample complexity.

To summarize, if one accepts having $p_{span}(Q_K - Q^\star)$ in the finite-time bound, one can simply replace $m_K$ by $\mathbb{E}[p_{span}(Q_K - Q^\star)^2]$ in Theorem 3.1 so that the theorem captures the dependence on the "initial error" $Q_K - Q^\star$. Moreover, if one also wants explicit dependence on $p_{span}(Q^\star)$ in the sample complexity, the result is

$\mathcal{O}(|\mathcal{S}|^3 |\mathcal{A}|^3 D_{min}^{-2} \epsilon^{-2} (1 - \beta)^{-3} p_{span}(Q^*)^2).$

See also the proof of Corollary 3.1.1 in Appendix B.5.

We thank the reviewer for the encouraging comments regarding the contributions of this work. In the following, we provide a point-by-point response to all of the reviewer's comments.

Comment: The analysis relies on Assumption 2.1, which states that the Bellman operator is a contraction mapping with respect to the span seminorm. While a sufficient condition is provided, the paper notes that analyzing Q-learning without such an assumption (i.e., under non-expansive operators) is an important direction for future research.

Response: We agree with the reviewer that Assumption 2.1 is a strong assumption. Removing this assumption would require completely abandoning the contractive viewpoint of the Bellman operator $\mathcal{H}(\cdot)$ and instead studying Q-learning as a stochastic approximation with a non-expansive operator, which is always true for $\mathcal{H}(\cdot)$. That said, as acknowledged by the reviewer, this paper has already overcome several major conceptual and technical challenges—such as identifying the necessity of using adaptive stepsizes, leveraging adaptive stepsizes as a means of implicit importance sampling, and handling non-Markovian noise—to achieve the main result. Relaxing Assumption 2.1 is an interesting future direction, but it is beyond the scope of this work.

Comment: While the paper acknowledges $h$ as a "tunable parameter" in the adaptive stepsize formula, it does not offer practical guidelines or methods for its selection. This leaves a gap for practitioners trying to implement and optimize the algorithm.

Response: We first clarify the role of $h$ in the stepsize $\alpha_k(s,a) = \alpha / (N_k(s,a) + h)$. In the $Q$-learning algorithm we study, to achieve the optimal $1/k$ rate of convergence (see Theorem 3.1, third case), the constant $\alpha$ must exceed a certain threshold (specifically, $\alpha \geq 2 / (1 - \beta)$). The parameter $h > 0$ is introduced solely to ensure that $\alpha_k(s,a) \in (0,1)$ for all $(s,a)$. This phenomenon has also been observed in other stochastic iterative algorithms that do not use adaptive stepsizes. For example, in discounted $Q$-learning [44] (where it is referred to as rescaled linear stepsizes) and in stochastic gradient descent (SGD) for smooth and strongly convex objectives, the optimal convergence rate is achieved with $\alpha_k = \alpha / (k + h)$, where $\alpha$ must be above a threshold that depends on the condition number. The parameter $h$ is again introduced to ensure that $\alpha_k \in (0,1)$ for all $k$.

In the next version of this work, we will add numerical simulations and discuss the choice of $h$ in that context.

Question: For Proposition 4.1, it claims that without choosing a proper $D$, the set of solutions to the asynchronous Bellman equation is disjoint from the solutions to the original Bellman equation measured in the seminorm $p_{span}$. How to interpret the condition to ensure the two solution sets are identical: $D=I/(|S||A|)$? $D$ is supposed to be a diagonal matrix with diagonal entries {$\mu(s)\pi(a|s)$}$_{(s,a)\in\mathcal{S}\times \mathcal{A}}$, does that mean that policy $\pi$ is a deterministic policy?

Response: To clarify, $D$ is the $|\mathcal{S}||\mathcal{A}| \times |\mathcal{S}||\mathcal{A}|$ diagonal matrix whose entries correspond to the stationary distribution of the Markov chain {$(S_k, A_k)$} induced by the behavior policy $\pi$, where $|\mathcal{S}|$ and $|\mathcal{A}|$ denote the cardinalities of the state and action spaces, respectively. Proposition 4.1 states that a necessary and sufficient condition for $Q$-learning with a universal stepsize to converge to the correct target is that $D = I / (|\mathcal{S}||\mathcal{A}|)$; that is, $\mu(s)\pi(a|s) = 1 / (|\mathcal{S}||\mathcal{A}|)$ for all $(s,a)$. This condition is equivalent to saying that the behavior policy $\pi$ must be uniform over actions for every state, i.e., $\pi(a|s) = 1/|\mathcal{A}|$ for all $(s,a)$, and the Markov chain {$S_k$} induced by $\pi$ must also have a uniform stationary distribution over the state space, i.e., $\mu(s) = 1/|\mathcal{S}|$ for all $s$.

However, the stationary distribution (i.e., the matrix $D$) is jointly determined by the behavior policy $\pi$ and the unknown environment transition dynamics, and thus cannot be freely chosen to be $D = I / (|\mathcal{S}||\mathcal{A}|)$. This is why $Q$-learning with a universal stepsize is, in general, not guaranteed to converge to the correct target. This limitation motivates the use of importance sampling with the uniform distribution as the target distribution, leading to the development of $Q$-learning with adaptive stepsizes, as illustrated in Section 4.2.

Question: Another question about Proposition 4.1 is that, although the sets of solutions are disjoint with some choice of $D$, are those two sets close to each other?

Response: This is an excellent question. Recall that the sets of solutions to the asynchonous Bellman equation $p_{span}(\bar{\mathcal{H}}(Q) - Q) = 0$ and the original Bellman equation $p_{span}(\mathcal{H}(Q) - Q) = 0$ are of the forms $\bar{Q}^\star +${$ce \mid c \in \mathbb{R}$} and $Q^\star +${$ce \mid c \in \mathbb{R}$}, which are identical when $D = I / (|\mathcal{S}||\mathcal{A}|)$ (cf. Proposition 4.1). Therefore, to conduct the sensitivity analysis, it is enough to bound $p_{span}(\bar{Q}^\star - Q^\star)$ as a function of $D$.

Since the asynchronous Bellman operator $\bar{\mathcal{H}}(\cdot)$ is defined as $\bar{\mathcal{H}}(Q) = (I-D)Q + D\mathcal{H}(Q)$ (see Eq. (5) of the submission), if $p_{span}(\bar{\mathcal{H}}(\bar{Q}^\star) - \bar{Q}^\star) = 0$, there must exist some $c \in \mathbb{R}$ such that

$\bar{\mathcal{H}}(\bar{Q}^\star) - \bar{Q}^\star=D(\mathcal{H}(\bar{Q}^\star) - \bar{Q}^\star) = ce \quad \Leftrightarrow \quad \mathcal{H}(\bar{Q}^\star) - \bar{Q}^\star = c D^{-1} e$,

where $e$ is the all-ones vector. On the other hand, we know that

$\mathcal{H}(Q^\star) - Q^\star = r^\star e$.

Taking the difference of the above two equations, we obtain

$\bar{Q}^\star - Q^\star = \mathcal{H}(\bar{Q}^\star) - \mathcal{H}(Q^\star) + r^\star e - c D^{-1} e$.

Taking the span seminorm on both sides and using the facts that $\mathcal{H}(\cdot)$ is a $\beta$-contraction with respect to $p_{span}(\cdot)$ and $\text{ker}(p_{span}) =${$ce \mid c \in \mathbb{R}$}, we conclude that

$p_{span}(\bar{Q}^\star - Q^\star) \leq \frac{|c| \cdot p_{span}(D^{-1} e)}{1 - \beta}$.

To interpret the result, consider the special case where $D = I / (|\mathcal{S}||\mathcal{A}|)$, in which case the right-hand side vanishes and we conclude that $p_{span}(\bar{Q}^\star - Q^\star) = 0$, implying that the solution sets to $p_{span}(\bar{\mathcal{H}}(Q) - Q) = 0$ and $p_{span}(\mathcal{H}(Q) - Q) = 0$ are the same. This agrees with Proposition 4.1. More generally, when $D \neq I / (|\mathcal{S}||\mathcal{A}|)$, the above inequality provides a sensitivity analysis. We will add the above result to the next version of this work.

As a follow-up to this comment, we note that the ultimate goal of reinforcement learning is not to find $Q^\star$ per se, but to identify an optimal policy $\pi^\star$. Therefore, even if $p_{span}(\bar{Q}^\star - Q^\star) \neq 0$, Q-learning with universal stepsizes could still be acceptable if the greedy policy induced by $\bar{Q}^\star$ is optimal (or close to optimal). Unfortunately, we have constructed a two-state, two-action MDP that demonstrates this is, in general, not the case. Due to space limitations, we are unable to include the example here, but we will add it in the next version of the paper (or during the discussion phase, if the reviewer is particularly interested).