Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
Authors: Zaiwei Chen
Venue: NeurIPS 2025 poster ()
Keywords: Average-reward Q-learning
adaptive stepsizes
non-asymptotic analysis
non-Markovian stochastic approximation.
Primary area: theory
TL;DR: This work presents the first finite-time analysis of average-reward Q-learning with asynchronous updates based on a single trajectory of Markovian samples.

Abstract: This work presents the first finite-time analysis of average-reward $Q$-learning with an asynchronous implementation. A key feature of the algorithm we study is the use of adaptive stepsizes that act as local clocks for each state-action pair. We show that the mean-square error of this $Q$-learning algorithm, measured in the span seminorm, converges at a rate of $\smash{\tilde{\mathcal{O}}(1/k)}$. To establish this result, we demonstrate that adaptive stepsizes are necessary: without them, the algorithm fails to converge to the correct target. Moreover, adaptive stepsizes can be viewed as a form of implicit importance sampling that counteracts the effect of asynchronous updates.

Technically, the use of adaptive stepsizes causes each $Q$-learning update to depend on the full sample history, introducing strong correlations and making the algorithm a non-Markovian stochastic approximation (SA) scheme. Our approach to overcoming this challenge involves (1) a time-inhomogeneous Markovian reformulation of non-Markovian SA, and (2) a combination of almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities to break the strong correlations between the adaptive stepsizes and the iterates.

Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
Zaiwei Chen
School of Industrial Engineering, Purdue University chen52520purdue.. edu
Abstract
This work presents the first finite-time analysis of average-reward Q-learning with an asynchronous implementation. A key feature of the algorithm we study is the use of adaptive stepsizes that act as local clocks for each state-action pair. We show that the mean-square error of this Q-learning algorithm, measured in the span seminorm, converges at rate of O(1/k). To establish this result, demonstrate that adaptive stepsizes are necessary: without them, the algorithm fails to converge the correct target. Moreover, adaptive stepsizes can be viewed implicit importance sampling that counteracts the effect of asynchronous updates. Technically, the use of adaptive stepsizes causes each Q-learning update to depend on the full sample history, introducing strong correlations and making the algorithm a Mon-Markovinn stochastic approximation (SA) scheme. Our approach to over- coming this challenge involves (1) time-inhomogeneous Markovian reformulation of non-Markovian SA, and (2) combination of almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities to break the strong correlations between the adaptive stepsizes and the iterates.
form of
Introduction
Reinforcement Learning (RL) has become as a powerful framework for solving sequential decision- making problems, as demonstrated by its growing impact across a range of real-world applications, including autonomous robotics [64], game planinn AI [63], and the development of large language models [15]. Given the promising potential of RL. establishing strong theoretical foundations to guide its practical implementation is of sigmificant importance.
An RL problem is typically modeled Markov decision process (MDP) [67], but its objective can vary by application. Finite-horizon RL maximizes cumulative rewards over a fixed time, while infinite-horizon discounted RL introduces discount factor y E (0, 1) to prioritize immediate rewards over future rewards. However, selecting an appropriate discount factor can be challenging. For instance, it is often unclear how far into the future decisions should account for rewards. Moreover, in decision-making tasks such as robotic control, queuing systems, and financial trading, introducing discount factor may not be appropriate. The infinite-horizon average-reward setting addresses these challenges by optimizing the long-run average reward without requiring a discount factor. However, the absence of discounting introduces unique challenges for both algorithm design and theoretical analysis. For example, the associated Bellman operator is no longer norm-contrad contracttt mapping [58), sample-based updates add additional complexities to the structure of the algorithm [1], and optimality depends on value differences rather than absolute values.
These challenges are particularly evident in Q-learnig [75], one of the most classical and practically impactful RL algorithms. Due to its popularity and its role as a major milestone in RL [53], substantial efforts have been dedicated to providing theoretical guarantees, especially terms of convergence rates, for Q-learning. In the discounted setting, the first finite-time analysis of Q-learning was
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

conducted in the early 2000s [28], followed by a series of works over the past two decades that eventually led to matching upper and lower bounds [4, 45]. In contrast, the average-reward setting, due to the aforementioned challenges, existing results are largely limited to asymptotic convergence 11, 66, 73, 74, 77, 78) and regret analysis [3, 34, 76, 83). Regarding finite-time analysis, even for Q-learning with synchronous updates (which requires a generative model for i.i.d. sampling), results have only appeared very recently [14, 35, 80J. To the best of our knowledge, no existing work provides a finite-time analysis for the last-iterate convergence of Q-learning with asynchronous updates based on a single trajectory of Markovian samples.
In this work, we provide the first principled study on the finite-time analysis of average-reward Q-learning. Specifically, we make the following contributions.
Finite-Time Analysis for the Last-Iterate Convergence. We study a natural variant of average- reward Q-learning (cf. Algorithm 1). The only difference compared to its discounted counterpart (aside from setting the discount factor to one) is the use of stepsizes ogg (s, a) that adapt to individual state-action pairs (s,a), Specifically, the adaptive stepsize ag a) is inversely proportional number of visits to the state-action pair (s, a), thereby serving as a local clock for each pair. We establish finite-time convergence bounds for this Q-learning algorithm, showing that IE [ppspan( (Qn- @*)²] (where Popan( (-) denotes the span seminorm, Qx is the k-th iterate, and Q* is the optimal relative )-function) converges at a rate of ((1 (1/)). To the best of our knowledge, this result provides the first finite-time analysis for the last-iterate convergence of average-reward Q-learning.
the
The Necessity of Using Adaptive Stepsizes.
Since the use of adaptive stepsizes is the only major difference compared to the existing finite-time analysis of discounted Q-learning. 1 we conduct a thorough investigation into both the necessity and the fundamental reasons for using adaptive stepsizes in average-rewand
used Q-learning. Specifically, we show that if universal stepsizes (e.g., 0r (x, a) = 1/k & for all (s, a)), the algorithm is, in general, guaranteed not to converge in Pspan() to Q* (cf. Proposition 4.1). We then identify that the use of adaptive stepsizes can be interpreted as form of importance sampling that counteracts the effect of asynchronous updates based on a single sample trajectory, with the importance sampling ratios estimated using empirical frequencies derived from the historical number of visits to each state-action pair.
Technical Contributions. The use of adaptive stepsizes in Q-learning causes each update to depend on the entire history of visited state-action pairs, introducing strong correlations and making the algorithm a non-Markovian stochastic approximation (SA). This poses significant challenges for the finite-time analysis, which have not been addressed in the existing literature. To overcome this challenge, we first reformulate the algorithm frequencies of visited state-action pairs into the stochastic process that drives the algorithm. However, the resulting Markovian noise is fime-inhomogeneous and does not exhibit the geometric mixing property typically used to handle correlations between the iterates and the noise. To resolve this issue, develop an approach that begins by showing that the Q-learning iterates, while not uniformly bounded by a constant (in stark contrast to the discounted setting [29]), nonetheless satisfy an almost-sure, time-varying bound that grows at most logarithmically with k. We then leverage this result, along with conditioning arguments and Markov chain concentration inequalities, to break the correlation. See Section 5 for a more detailed discussion of our proof techniques.
Markovian SA by incorporating the empirical
1.1 Related Literature
In this section, we discuss related literature on average-reward Q-learning, discounted Q-learning, and Markovian SA.
Perrage-Reward Q-Learning. The first provably convergent algorithms for average-reward Q- learning are the relative value iteration (RVI) Q-learning and stochastic shortest path (SSP) Q-laariing algorithms [1]. Since then, many variants have been proposed, including differential Q-learning [72, 73], dynamic horizon Q-learning [35], among others. The asymptotic convergence of RVI Q-learning and its variants was established in [1] by leveraging results from general asynchronous SA [11], and was later extended under relaxed assumptions [2, 74, 78] and to MDPs with continuous state spaces [37, 77]. In contrast, asymattpttoiic results are much more limited. Specifically,
Although adaptive stepsizes have been used in the existing asymptotic analysis of discounted Q-learning [1, 68]. they have been less explored in the context of finite-time time analysis.

---

even for Q-learning with synchronous implementation (which requires a generative model for ii.d. sampling), finite-time analysis has not been conducted until very recently [24, 35, 80J. A related but distinct line of work designs online D-learning-hasee algorithms that aim to balance the exploration-ext exxplittoneellliiatiionn trade-off, with performance measured in terms of regret; see [3, 76, 83] and the references therein. However, since the performance metrics are fundamentally different (regret versus last-iterate convergence in the span seminorm), these results are not directly comparable.
Discounted Q-T.earning- The celebrated Q-learning algorithm for discounted MDPs was first proposed in [75], and its almost sure convergence was established through various approaches in [13, 33, 68]. The first finite-time analysis of Q-learning (for both synchronous and asynchronous implementations) was performed in [28]. Since then, a sequence of works has aimed to provide refined characterizations of its convergence rate, including mean-square bounds [5, 6. 20, 21, 42, 70] and high-probability concentration bounds [44-46, 60, 71]. Variants of Q-learning, including Zap Q- learning, Q-learning with Polyak averaging, and Qllaarnin with Richardson Romberg extrapolation, have been proposed and studied in [25]. [48], and [82], respectively. To overcome the curse of dimensionality. Q- Q-learning is often implemented with function approximation in practice. A rich body of literature provides theoretical guarantees for Q-learning with function approximation [19, 23, 49- 51, 79). Compared with Q-learnng in the discounted setting, the finite-time analysis of average- reward Q-learning is significantly more challenging due to the following reasons: (1) the lack of discounting makes the Bellman operator non-contractive in any norm, (2) the iterates are not uniformly bounded, and (3) the use of adaptive stepsizes (which is necessary, as will be illustrated in Section 4) introduces strong correlations and makes the algorithm a non-Markovian SA. As result, none of the existing approaches for discounted Q-learning are applicable here.
Stochastic Approximation. At high level, Q-learning can be viewed as iteratively solving the Bellman equation, a fixed-point equation, using the SA method [61]. The asymptotic convergence of SA for solving fixed-point equations has been established under fairly general assumptions in [7, 12, 13, 39, J1 among many others. For finite-time analysis, the properties of the fixed-point operator and the nature of the noise sequence play crucial roles. In particular, when the operator is linear contractive with respect to some norm, and the noise process is either i.i.d. or forms a uniformly ergodic Markov chain, there rich body of literature establishing mean-square and high- bigh-probability bounds [9, 21, 22, 26, 32, 54, 55, 59, 60, 65, 70J. Beyond these standard settings, finite-time analysis of SA with seminorm contractive operators and non-expansive operators have been developed recently in [24] and [10, 14), respectively. A main feature of the average-reward Q- learning algorithms studied in this work is that, as SA algorithms, they are inherently non- non-Markovian due to the use of adaptive stepsizes that depend on the entire history of visited state-action pairs. Through a novel reformulation, we cast the algorithm as a Markovian SA; however, the resulting and, more importantly, does not exhibit geometric mixing,
Markovian noise is time-inhomogenes or even mixing faster than 1/k. This presents a unique challenge that has not been addressed in the existing finite-time analysis of SA.
From Reeaade-Reward RL to the Seminorm Bellman Equation
In this section, we first provide background on average-reward RL. and then introduce the seminorm Bellman equation, which plays a central role in motivating both the algorithm design and the analysis of Q-learning in subsequent sections.
2.1 Background on Average-Reward RL
Consider an hariiite undiscounted MDP defined by the tuple (S, P.R.) [58], where S and A denote the finite state and action spaces, respectively. The transition dynamics are given by P = {p('')e (/, )). xxxxxxxx where p(s') |s, a) denotes the probability of transitioning to state s' after taking action a state s. The stage-wise reward function is denoted by R: x A - [-1, The transition probabilities and the reward function are unknown to the agent, but the agent can interact with the environment by taking actions, observing transitions, and receiving rewards.
Given policy π : S + A(A) (where A(A) denotes the set of probability distributions supported on A), the average reward nd e IR $ is defined as n (s) lim E, K> k= R(Sk, Aa) K S s]
3

---

for all s E S, where the expectation [ is taken over the randommess in the trajectory generated by the policy æ,. It is shown in standard MDP theory [58] that if the Markov chain induced by the policy has single recurrent class, the limit exists and is independent of the initial state. In this work, we operate under this setting. Consequently, we slightly abuse notation and use r" to denote the scalar average reward associated with policy и. The goal is to find an optimal policy x² that maximizes the average reward. Define the optimal relative Q- funntttoo (also known as the Q-value bias function) Q" E R (R|A as Q" (s, = E,-
E,-IEx= |Σx=1 (R(Sk, A&) r") S = s, A1 = a] for all (s, a) E S x A, where r" E R is the optimal average reward. It is known that any policy that satisfies T (s)) E arg ma Q* a) for all state E S an optimal policy [58]. Therefore, the problem reduces to finding the optimal relative Q-function Q"
To find Q", we next introduce the Bellman equation. Let H IS |A| + ||5||A| denote the Bellman operator defined as [H{Q)](s,, a) R(s, a) + E[maxx'e.. Q(S2, a') S1 8, A1 al for all (s,a) a)
and Q ||S||A|, The Bellman equation is then given by
H(Q) (QQ)-Q=1 =ree,
(I)
where e denotes the all-ones vector. It is well known that Q" is a solution to Eq. (1) [58]. However, such a solution is not unique. To see this, observe that for any с R. it follows directly from the definition of (())) that Hi'²" + ce) (Q* + ce) = H(Q") + CE - Q" - ce = H(Q") Q* = ree, implying that Q" + ce is also solution to Eq. (1). Fortunately, for the purpose of finding an optimal policy, errors in the direction of the all-ones vector have no impact on the result, because x" (s) E arg max Q" (s. a) = arg max (Q" (s. a) + c) for all IR. Therefore, it suffices to find any point in the set Q = (Q" + ce c IR..
2.2 The Seminorm Bellman Equation
Due to the lack of discounting, the Bellman operator H(-)) is not a contraction mapping under any norm. However, it has been shown in [58] that the operator H(-) can be a contraction mapping with respect the span seminorm under certain additional assumptions on the underlying stochastic model (to be discussed shortly). Since this property forms the foundation of the Q-learning algorithm we will present, we begin by formally introducing the span seminorm and discussing its properties.
For any x E IR,, the span seminorm of x, denoted by (xr), is defined as Pspan (x) = (max, I; miny /2. Similar to a norm, the span seminorm is non-negative and satisfies the triangle inequality:
Pspan (x: + v) S Psqun (3:) + Popan (y) for all 2; y E Rdd; and absolute homogeneity: Pspan (ax) =
Jai Pspan (z) for all a E R and E Rd [57, Section 6.6.1]. However, unlike a norm, Pepan (2) = 0 does not imply = 0. In fact, the set {x E Rd Pqpan (a) = 0} is called the kernel of the span seminorm and is denoted by ker (Pspan). Since Pspan (z) = 0 if and only if max; 2; = miny zy. in which case all R}. Another important property of the span seminorm is that Pspan (x) can be interpreted as the distance from æ to the linear subspace fcelc E R) with respect to ||- 1l oc. Since this result will be used frequently throughout the paper, formally state it in the following lemma. The proof is provided in Appendix C.I.
entries of must be identical, we have ker(Ps
{ce
Lemma 2.1.
For any x E Rdd, we have arg min || cel cellac x = (max; my + min, xz)/2. As result, the span seminorm of can be equivalently written as Pspan (2) = min || ce lool
With ( properly introduced, we next state our assumption on the Bellman operator H())) Assumption 2.1. The Bellman operator H--) is a 3-contraction mapping with respect to Pspan (-).
A sufficient condition for Assumption 2.1 to hold is max llx(- s. s. p(- s',, s',,'))' [|T < 1, where || |/Tv denotes the total variation distance. In this case, Assumption 2.1 is satisfied with 3 = (sa (ar,aa) I|p(- s, - p(- s', s²,a')) d')l This condition is adopted from standard MDP theory textbooks [58], where it was used to study the convergence of relative value iteration [57, Proposition 6.6.1 and Theorem 6.6.2]. Since the goal of this work
establish the convergence rate for Q-learning in the span seminorm contraction setting, we do not attempt to relax Assumption 1. Nevertheless, we include a discussion in Section 6 on potential approaches for analyzing Q-learning when Assumption 2.1 is not satisfied.
Under Assumption 2.1, we have the following result, whose proof is presented in Appendix C.2.
Lemma 2.2. {Q" + ce c R}- (Q H(Q) Q == =rre} {Q Papon (H(Q) Q) 0}.
4

---

As result of Lemma 2.2, the seminorm fixed- fixed-point equation
Pspea (H(Q)- - Q) =0
and the Bellman equation (1) are equivalent in the sense that they have the same set of solutions: Q {Q- + E R). Therefore, suffices to find a solution Eq. (2) in order to compute an
optimal policy. For this reason, we shall refer to Eq. (2) as the seminorm Bellman equation, or simply the Bellman equation.
3 Main Results
To solve the Bellman equation (2), we next introduce a Q-learning algorithm with finite-time convergence guarantees. Recall that the RL setting, the parameters of the stochastic model (i.e.. the transition dynamics and the reward function) are unknown to the agent, but the agent can interact with the environment by taking actions, receiving rewards, and observing environment transitions.
3.1 Algorithm
Let л denote the policy used by the agent to interact with the environment, commonly referred to as the behavior policy. Our Q-learning algorithm is represented in Algorithm 1.
Algorithm Q-Learning
Input: Initializations Q E R S1 S, and behavior policy m
2: for == 1,2, 1.2. do
3: Take A& ~ T- Sx). observe S ~ p(: Sk, Ar). and receive R(Sk; Ak).
4: Compute the temporal difference: 82 = R(Sk, Aa) + max,' Qu Qu Qx As).
5: Update the Q-function: Q (8, = (u a) + [
for all (8, a).
where 0% (s, a) a//NN a) + h)), and Ni == Σ ((8,,A))(4.) denotes the total number of visits to the state-action pair (s, a) up the k-th iteration.
6: end for
7: Output: (Qsha11
Note that Algorithm 1 is surprisingly simple and represents the most natural extension of Q-learning in the discounted setting [75]. fact, the only modification (aside from setting the discount factor to one) is using adaptive stepsizes of the form ag (s(s,, a) a/(N(ss, a) + h), where a. h > 0 are tunable parameters. Importantly, the stepsize og (s, a) depends on the specific state-action pair through the counter N&(s,, a) and is therefore not universal. Throughout, we refer to such stepsizes as adaptive stepsizes. Although adaptive stepsizes of this form have been used in the existing asymptotic analysis of QQ-eeanning and iemporal-differnnc learning in both the discounted and wverage-reward settings [1, 68), they have been less explored the context of finite-time analysis. The necessity and theoretical motivation behind this choice will be discussed in detail in Section 4.
In the existing literature. the algorithm most closely related Algorithm 1 is RVI Q-learning [1]. In RVI Q-learning, the temporal difference is defined as 6₁ = R(Sk, As) 3.) + max, (R<+++1,00 a') Qu(SR, Ax) f(Qx), where f(-) is a Lipsehitz function satisfying f(e)
and f(Q + ce) = f(Q) + e for any E RR Subtracting the additional term f(Qx) in the temporal difference ensures almost sure convergence to a particular solution Q of Eq. (1) that satisfies f(Q) r" [1]. In contrast, Algorithm does not include such a step, as we will show that it guarantees convergence to Q" in Pepan( (.), or equivalently, convergence to the set Q = (Q" + oe c E IR] with respect to || Iloo. From a theoretical standpoint, such set convergence is sufficient for computing optimal policy.
3.2 Sinite-Time Analysis
To present main theoretical result, we first state assumption regarding the behavior policy. Assumption 3.1. The hehavior policy satisfies I (a|s) > 0 for all (s, a), and the Markov chain {Sx) induced by the behavior policy is irreducible and aperiodic.
Assumption 3.1 is standard in the existing studies of both value-based and posicy-based RL. algorithms [46, 47, 65, 68, 69], and guarantees that all state-action pairs are visited infinitely often during learning.
5

---

Specifically, under Assumption 3.1, the Markov chain } induced by т has a unique stationary
distribution, denoted by μ E (SS), which satisfies min,es pu(s) 0 [43]. Moreover, there exist
Cs 1 and p e (0, 1) such that max,ee [S+ = 1|S =) =(-) ITV I Cp*-1 1 for all k 2 1 [43]. where denotes the transition kernel of the Markov chain } induced by π.
To aid in the statement of our main theorem, introduce the following notation. Let min Cp--1= S a/ + h}}, , by a|S]||A] log(T [S] Ai 1/h 1), and my by + Pspan Pspan(Q",, where [æ] returns the smallest integer greater than or equal to x. Note that The bg. and my grow at most logarithmically in k. Let Dmin = mins,a ({))t(als), which is positive under Assumption 3.1.
Theorem 3.1. Consider {Qt} ) generated by Algorithm 1. Suppose that Assumptions 2.1 and 3. are satisfied. Then, there exists K > O such that for any k E 21, KK we have Pspan (Qx - Q²) S by + Pspan (Q*) almost surely (a.s.), and for any 2 K + 1, we have
20-6)
+h
CITA +12
3m 2
if - (3) <2
k + h
(k+ h) ali-8)
E Plpponn (Qk= QQ)) <
3m 2
+
+
C2TA(TR + +1121log's log(k + h)
if - B) =2
1 + h
(I: + h)
oil g)
K + h
CiTA(my + 1)²
3m
ifa(l 3) >
+ h
(k: + h)
Here, C1 and C2 are problem- constants defined as
(og]s
C|S||A|| log([5]|AA)
C C= (1- B) a1) (1 -3)a''
and C2
(1 p1 333 D
where 0j and C2 are absolute constants.
A proof sketch of Theorem 3.1 is provided in Section 5, with the full proof deferred to Appendix A. Due to the presence of Markovian noise and the use of adaptive stepsizes, the convergence bound in Theorem 3.1 does not hold from the initial iteration. Specifically, prior to iteration K, establish an almost-sure bound that grows at most logarithmically with k. After iteration K. the "averaging" effect becomes dominant, and the mean-square error begins to decay, with the rate of convergence depending critically on the choice of the constant a in Algorithm 1. In particular, if a is below the threshold 2/(1 B), the convergence rate is O(- (1- which be arbitrarily slow. Conversely, if a exceeds the threshold, the convergence rate improves to the optimal O(1/k) up to logarithmic factors. A qualitatively similar phenomenon has been observed norm-contracttiv SA algorithms [21], linear SA algorithms [9], and stochastic gradient descent/ascent algorithms [40].
Based on Theorem 3.1, we have the following corollary for the sample complexity.
Corollary 3.1.1. Given c > 0, to achieve E[pepon (Qx - Q")] I c with Algorithm 1, the sample complexity is Ô (| min (1
-)-
The proof of Corollary 3. is provided in Appendix A.5. Notably, the dependence on the desired accuracy level is Ö(E-2), 2), which is unimprovable in general. While we make the dependence on the size of the state-action space and the seminorm contraction factor explicit, these terms are by no means optimal in light of existing information-theorelt lower bounds [36]. It is worth noting, however, that the lower bound in [36] was derived under a generative model that provides i.i.d. samples, whereas our analysis considers the more challenging Markovian sampling setting. Despite this discrepancy, tightening the dependencies on |S||_A,, 1/(1 $), and Dmin, whether through refined analysis or improved algorithmic techniques such as Polyak averaging or variance reduction, remains an important direction for future research. That being said, we emphasize that this is the first result to establish last-iterate convergence rate guarantees for model-free Q-learning with an asynchronous implementation.
4
The Necessity of Using Adaptive Stepsizes
As discussed in the previous section, the most important feature of Algorithm 1 its use of adaptive stepsizes. Theoretically breaking their strong correlation with the iterates Qs will be our primary

---

technical innovation in the proof of Theorem 3.1. However, before delving into the proofs, it is important to first answer the following two questions: (1) the use of adaptive stepsizes necessary. and how does the algorithm behave if we instead use universal stepsizes (e.g., (s,(s, a) = 1 1/k for all (s, aa)? (2) If adaptive stepsizes are indeed necessary, how do we interpret their role? In this section, we provide clear answers to these questions. The insights developed in this section will play central role in guiding our proof Theorem 3.1.
4.1 Q-Learning with Universal Stepsizes: Provable Convergence to the Wrong Target
In this section, we will show that if we use universal stepsizes in Algorithm 1, the algorithm fails to converge in Pspan()) to Q*. To this end, first present the main update equation for Q-learning with universal stepsizes in the following:
Qu+I a) - Qu ((s.)))) (R(S +
(3)
for all (s, a), where the asynchronous nature the update equation is captured by the indicator function. Here, the stepsize on depends only on & and is independent of the state-action pairs.
The Q-learning algorithm described in Eq. (3) takes the typical form of a Markovian SA algo- rithm. We begin with the reformulation and identify the target equation it aims to solve. Let Y (Sk, Ag, Sk+1) for all k 2 1. Note that {Y&} forms a Markov chain, with state space O = SSx x A x S. In addition, under Assumption 3.1, the Markov chain {Ya} admits unique stationary distribution v E A()) satisfying (ss, a, s') = {=()) (a is Dp((s(p |ss a) for all (s, a, s') E V. Let G |IS x y + RIS||A|| be an operator defined such that given input arguments Q E R (|]A|
and y = (So, ao; 81) E V, the (8, a)th entry of the output of the operator is given by
(G(Q,))](s: a) ((0.000)=(s.00) (R( no) + max ((),,a)) Q(so, Q(s
a'EA
With (Y&) and G() defined above, Eq. (3) can be formulated as a Markovian SA:
Qk+1 Qx + an (G(Qk, Qu)-
(4)
Let Hi RRSIIAI + R |||A| be the "expected" operator defined as:
R((Q) == Ey-, G(Q = [[I - D) + DH)(Q), YQERIAIAI
(5)
where H((.) is the Bellman operator, and D is an |S||_A] x [S] diagonal matrix with diagonal entries (a(s))(a(s)) (s.))))) Inspired by [21] (which studies Q-learning in the discounted setting), we refer to H((-) as the asynchronous Bellman operator. The reason is that for each (s, a). the output [H[()) a). according its definition, can be viewed as the expectation of random variable that takes [Q) a) with probability D(s, a) and takes Q(s, a) with probability 1 - D(s a), capturing the asynchronous nature of Q-learning
The following lemma shows that Fl(-) is also a contraction mapping with respect to Pspan (+).
Lemma 4.1. Under Assumptions 2.1 and 3.1, the asynchronous Bellmun operator H(-) is a contruc- tion mupping with respect to Popan ()), with contruction, factor 3 == 11 (1 -
The proof of Lemma 4.1 is presented in Appendix C.3. In light of Lemma 4.1, we identify that the Markovian SA algorithm described in Eq. (4) is designed to solve the seminorm fixed-point equation
Papan (H) Q) O,
which we refer to as the asynchronous Bellman equation, in contrast to the original Bellman equation (2). Therefore, applying recent results on Markovian SA with seminorm contractive operators [24), we show in the following proposition that Q-learning with universal stepsizes (cf. Eq. (3)) provably achieves mean-square convergence in Pspan (.) to wrong target. See Appendix C.4 for its proof.
Proposition 4.1. Suppose that Assumptions 2.1 and 3.1 are satisfied. Then, we have
S (Q Pspure (H(Q) - Q) = 03 =QQ Pspan (H(Q) Q) 0}. if I/([S]|A|), { [1Q Papuee (H((Q) Q) = 0} n [Q Papan (H((Q) Q) 03 = 0. otherwise.
(7)
Moreover, when agk a/(k: + h) with appropriately chosen and h, the Q-learning algorithm described in Eq. (3) achieves Elpapan( Q2+ 22)31 < (1)/k), where Q* is a particular solution to the asynchronous Bellman equation Papan (H(Q) Q) 0.
7

---

Since the sets of solutions to the asynchronous Bellman equation and the original Bellman equation are completely disjoint, except in the degenerate case where D D= Proposition 4.1 reveals the following critical issue: as long as D & T/()S||A)), Q-learning with universal stepsizes is guaranteed not to converge to any point in the desired set of solutions Q = (Q* + ce E [R) of the original Bellman equation Pspan(H(QQ (H(()) Q) =0.
In summary, the fundamental issue for Q-learning with universal stepsizes in the average-reward setting is that the combination of a seminorm contraction mapping and asynchronous updates can make the set of solutions to the asynchronous Bellman equation Pspan (H()) Q) completely
different from that of the original Bellman equation Papan (apan(1(( (H(Q) - Q) = 0.
Before illustrating how adaptive stepsizes resolve this issue, we quantify the discrepancy through a sensitivity analysis, presented in the following lemma. The proof of Lemma 4.2 is presented in Appendix C.5.
Lemma 4.2. There exists a constant e E IR such that Pspan (Q" (Q"-QQ" -Q")= S
|es| Pinar ( (D=
1-3
To interpret this result, consider the special case D = I I/(])| in which the right-hand side vanishes and hence Popan Q² Q") = 0, implying that the sets of solutions to Pspun (H(Q) Q) 0
and Papan ( (H(()) Q) = 0 coincide. This agrees with Proposition 4.1. More generally, when D + (/((S| A)). the above inequality provides sensitivity bound.
The Discounted Setting. One might ask: why is discounted Q-learning able to achieve provable convergence to the optimal Q-function with universal stepsizes? To illustrate, consider the 7- discounted MDP that shares the same transition kernel and reward function as the average-reward MDP studied in this work. Let Q be the optimal Q- Q-function, and let (-) denote the Bellman operator, which is "-contraction mapping with respect to || l|o [8, 58, 67]. Following the same line of reasoning, discounted Q-learning (with asynchronous updates) can be formulated as a Markovian SA algorithm for solving the fixed-point equation (Q) Q. where H,) is the asynchronous Bellman operator in the discounted setting, defined as (Q) [1 -I-D) D) + DQ2 It has been shown in the existing literature [12, 21] that, under Assumption 3.1, the asynchronous Bellman operator (-) maintains the following two important properties of the original Bellman operator H,,(): (1) (.) is a contraction mapping with respect to |l and (2) the asynchronous Bellman equation (Q) Q admits a unique solution Q", which is the optimal Q Q-function in the discounted setting. Consequently, discounted Q-learning with universal stepsizes converges to Q by standard results on Markovian SA with nont-contractive operators [7, 13].
4.2 Q-Learning with Adaptive Stepsizes: Implicit Importance Sampling to the Rescue
In view of Proposition 4.1 and the definition of the asynchronous Bellman operator in Eq. (5). suppose that the triple (Sp, Ak, Sk+1) were drawn from the distribution v' E A()) defined by v(()) = p(s' s, distribution induced by sampling Sy Unif(S), A& ~ Un) and Sk+1 p(( Sk, As). Then, we would have D = I [l),, and the asynchronous Bellman equation would share the same set of solutions the original Bellman equation. However, when following the trajectory of the Markov chain {(S,, Ag, 11+1)]. even asymptotically, we only receive samples from its stationary distribution o()), which satisfies v(y)= = p(s)=(a s)p(s' 8, a) for any y = (s, a, 8') y. Phrased this way, the solution to fixing Q-learning with universal stepsizes becomes natural: importance sampling.
for all y = (s. a, s') s') E y. Note that v'(.) corresponds to the joint
Importance sampling is technique widely used in statistics [38], rare-event simulation [16], and off- policy RL [27]. Specifically, when direct sampling from a target distribution is difficult, importance sampling enables the estimation of expectations with respect to the target distribution by instead drawing samples from a different, more accessible distribution, referred to as the behavior distribution. The key idea is to reweight the samples drawn from the behavior distribution according to the likelihood ratio between the target and behavior distributions.
Coming back to the problem of fixing Q-learning with universal stepsizes (cf. Eq. (3)), we want to perform importance sampling with v'(-) being the target distribution and vx-) being the behavior distribution. Therefore, using dz (R(Se, As) + max Qx(Se+1, Qx (Sp, As)) to denote
8

---

the temporal difference for simplicity of notation, the algorithm becomes
(s, a, s') 6n 1 (8),,,88)
QR+I(S, a) = Qu((sa) + ar
1 (1))_A))=()a)) OR
=Q((8,a) + ork
(s,,
1 ((Sk (1S).AA)==s dz. ((s.a)
=Q)(s,a) + ās:
(8)
D(s,a)
where the last equality follows by absorbing the 1/([S||AA) factor into the stepsizes, i.e., by redefining āg = ax/ [|S]]
While the algorithm described in Eq. (8) seems promising, it is impractical because we do not have access to the stationary distribution of the Markov chain ((Sg, As) induced by x. A natural way to obtain an estimate of D(s, a) is by using the empirical frequency. Specifically, recall that we have denoted (s, a) as the total number of visits to state-action pair (s, a) up the k--th iteration. Then, the estimator (s, a)/k, or more generally, Ds(s,a) == (N, a) + h)) + h) for any z O, is an asymptotically unbiased estimator of D(s, a) because under Assumption 3.1, the law of large numbers holds for functions of the Markov chain {(S,. A [52]. Substituting the estimator Dx(s, a) of (ss,0) a) into Eq. (8), when the universal stepsize set to 0g = =a/ h), we obtain
Qx+1(s, a) = Qu(s,a)+ āg ( (LS,,A)))(sa)) 82 Qs
al ((5).A)))xx.. 8N. (x a) + h
(9)
Dx(s,a)
for all (8,a) a) E S x A. Note that this is exactly the main update equation of the Q-learning algorithm presented in Algorithm 1, which uses adaptive stepsizes the form ar a) = a/(NNx a) h).
In summary, the use of adaptive stepsizes in Q-learning (which is necessary, as illustrated in Sec- tion 4.1) can be viewed as form of implicit importance sampling that counteracts the effect of asynchronous updates, where the importance sampling weights are effectively constructed from the empirical frequency visits each state-action pair.
Proof Sketch of Theorem 3.1
Although the underlying stochastic process {Sa,, As)] driving Algorithm I is Markov chain, the k-th update depends on the entire sample history (S), AI, S2, A Sk, Ax) due to the use of adaptive stepsizes. As result, the algorithm, viewed as SA, is non-Markovian. This presents the main technical challenge establishing a finite-time analysis. To address it, our proof proceeds through the following key steps.
Markovian Reformulation of Non-Markovian SA: In light of the discussion in Section 4.2, especially Eq. (9), the k-th iteration of Algorithm depends deterministically on the following random variables: the current iterate Qk. the k-th transition (Sk, Ag. Sk+1), and the empirical frequency matrix Dr, which is an (S||-A|-b-|(S) |S|AA) diagonal matrix with diagonal entries (s, a) hk
( (x.))ExA This motivates us to define a stochastic process {Zx- = (De, Sk, Ak, Sk41) and reformulate Algorithm an SA driven by {Zx]:
Qx+1
Q: ON (F(Qk: 7k) Qx),
(10)
where a = a/(k + h) is the stepsize and F R|S|1A x Z + R|S||A|| is operator defined such
that given input arguments Q E (S|AA and (D, so, ao 81) E 2, the (s, a)-th entry of the output of the operator is given by
[F(Q,))](s, 1 ((00,a))=(00))) R((8,, un) max Q( a') Qs0, a))) Q(s,a). ''EAA
(11)
D(s,a)
Although the reformulation casts the Q-learnin algorithm as an SA with universal stepsizes, emphasize that the stochastic process {Zx} forms a time-innomen intte-innooogouuss Markov chain and therefore does not exhibit the geometric mixing property typically assumed in the SA literature (9, 65, 68).
Lyapunov Framework for the Analysis: After reformulating Algorithm as an SA with time- inhomogencous Markovian noise, as presented in Eq. (10), we employ Lyapunov approach

---

to carry out the finite-time analysis. Inspired by [18. 24, 81], we construct Lyapunov function
M() as the generalized Moreau envelope of Pspan (Q²)/2. Our goal is show that the sequence {Qx) generated by the SA algorithm in Eq. (10) exhibits negative drift with respect to M(.):
E[M - Q*) - (1
- Q') + o(ax).
(12)
To establish a recursive inequality of the form (12), the high-level idea is to show that the "determin- istic" part of the update in Eq. (10) induces negative drift of (O( Q*)], while the
error due to stochasticity is at most o(ax).
Establishing the negative drift is not particularly challenging in our case due to the span seminorm contraction property of the Bellman operator H(-) and the construction of the Lyapunov function M(.). The main challenge lies in controlling the stochastic error, particularly in handling the correlation between the iterates {Q*} and the stochastic process {- J. In the existing literature studying Markovian SA, if the underlying noise sequence is i.i.d. or forms a uniformly ergodic Markov chain, the correlation between the iterate and the noise can be handled using either an approach based on conditioning and mixing time [65] or more recently developed approach based on the Poisson equation [17, 30, 31]. Unfortunately, neither approach is applicable here due to the fact that [Z } is time-inhomogeneous and lacks geometric mixing.
Breaking the Correlation: To break the correlation between Zx and Qu, we develop an approach consisting of the following two steps:
Time- Varying Almost-Sure Bounds:
The first step to show that the iterate Qk. while not uniformly bounded by constant, satisfies a time- time-iarying almost-sure bound that grows at most logarithmicall with (cf. Proposition A.1). These two properties together enable us to decouple the iterate Qk from the time-inhomogeneous Markovian noise Zk.
Conditioning Arguments + Markov Concentration Inequalities: After decoupling, we handle the randomness in Z = (Dx. Sk; Ak. Sk+1) separately, where two challenges arise: (1) the correlation between D; and (Sk. Ag. Sk+1), and (2) the presence of the empirical frequency D& (s, a) in the denominator of the algorithm update (cf. Eq. (9) and Eq. (11)), which breaks linearity. To address the first challenge, we use conditioning argument based on the fast mixing of (Sx. As. Sk+1) 1) (cf. Assumption 3.2). To tackle the second, we employ Markov chain concentration inequalities and the L weak law of large numbers for functions of Markov chains.
In the end, we obtain a Lyapunov-dre -diff inequality of the form (12), which can be recursively applied to derive the finite-time bound stated in Theorem 3.1.
6 Conclusion
In this work, we present the first study on the last-iterate convergence rates of average-reward Q- learning with asynchronous implementation. Moreover, we show that the key to achieving the desired convergence is the use of adaptive stepsizes, which can be viewed as a form of implicit importance sampling to counteract the asynchronous updates. We believe that our analysis is broadly applicable to the study of general SA algorithms with adaptive stepsizes.
Regarding future work, we identify three directions. First, the sample complexity dependence on the size of the state-action space and the seminorm contraction factor presented in this work is generally not tight. Developing refined analyses improved algorithmic designs (such as incorporating Polyak averaging or variance reduction) to tighten these bounds is an interesting research direction. Second, investigating the convergence behavior of Q-learning with other variants of adaptive stepsizes (as illustrated in Section 4.2) is another promising direction. Finally, while this work focuses on the setting where the Bellman operator is a seminorm contraction mapping, it is worth exploring how to conduct finite-time analysis of Q-learning without this assumption. Since the Bellman operator is always non-expansive with respect || I/... studying SA with non-expansive operators and inmomogeeoge)) Markovian noise will likely play an important role in advancing this direction.
10

---

Acknowledgments
I would like thank Mr. Shaan UI Haque from Georgia Tech for his help in identifying the seminorm contraction property of the asynchronous Bellman operator presented in Lemma 4.1. I would also like thank Dr. Siva Theja Maguluri from Georgia Tech for his valuable feedback on an early draft of this work.
References
[1] Abounadi, J., Bertsekas, D., and Borkar, S. (2001). Learning algorithms for Markov decision processes with average cost. SIAM Journal Control and Optimization, 40(3):681-696
[2] Abounadi, J., Bertsekas, D. P., and Borkar, V. (2002). Stochastic approximation for nonexpansive maps: Application Q-learning algorithms. SIAM Journal on Control and Optimization, 41(1):1- 22.
[3] Agrawal, P. and Agrawal, S. (2024). Optimistic Q-learning for average reward and episodic reinforcement learning. arXiv preprint 1rXiv:2407.13745
[4] Azar, M. G., Gómez, V., and Kappen, J. (2012). Dynamic policy programming. The Journal of Machine Learning Research, 13(1):3207-3255.
[5] Beck, L. and Srikant, R. (2012). Error bounds for constant stepsize Q-learing. Systems & control letters, (111):1203-1220)
[6] Beck, C. and Srikant, R. (2013). Improved upper bounds on the expected error in constant stepsize Q-learning. 2013 American Control Conference, pages 1926-1931. IEEE.
[7] Benveniste, A., Métivier, M., and Priouret, P. (2012). Adaptive Algorithms and Stochastic Approximations, volume 22. Springer Science & Business Media.
[8] Bertsekas, P. and Tsitsiklis, N. (1996). Neuro-dynamic programming. Athena Scientific.
[9] Bhandari, J., Russo, D., and Singal, R. (2018). finite-time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691-1692. PMLR.
[10] Blaser, E. and Zhang. (2024). Asymptotic and finite sample analysis of nonexpansive stochastic approximations with Markovian noise. Preprint arXiv:2409. 19546.
[11] Borkar, V. S. (1998). Asynchronous stochastic approximations. SIAM Journal on Control and Optimization, 36(3):840-851.
[12] Borkar, V. S. (2008). Stochastic Approximation: Dynamical Systems Viewpoint. Cambridge University Press.
[13] Borkar, V. and Meyn, P. (2000). The ODE method for convergence stochastic approxi- mation and reinforcement learning. SIAM Journal Control and Optimizatioon, 38(2):447-469,
[14] Bravo, M. and Cominetti, R. (2024). Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds. SIAM Journal on Control and Optinization, 62(1):191-219
[15] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, D., Dhariwal, P., Neelakantan, A.. Shyam, P. Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances neural information processing systems, 33:1877-1901.
[16] Bucklew, J. A. and Bucklew, J. (2004). Introduction rare event simulation, volume 5. Springer.
[17] Chandak, and Borkar, V. S. (2023). A concentration bound for TD(O) with function approxi- mation. Preprint arXiv:2312.10424,
[18] Chandak, S., Haque, S. U., and Bambos, N. (2025). Finite-time bounds for two-timescale stochastic approximation with arbitrary norm contractions and Markovian noise. Preprint 2xXi:250331189.
11

---

[19] Chen, Z., Clarke. J.-P., and Maguluri, S. T. (2023a). Target network and truncation overcome the deadly triad in Q-learning. SIAM Journal on Mathematics of Data Science, 5(4):1078- 1101.
[20] Chen, Z.., Maguluri, S. T. Shakkottai, S., and Shanmugam, K. (2020). Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. Advances in Neural Information Processing Systems, 33.
[21] Chen, Z.,, Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2024). A Lyapunov theory for finite-sample guarantees of Markovian stochastic approximation. Operations Research, 72(4)1332- 1367.
[22] Chen, Z., Maguluri, S. T., and Zubeldia, M. (2023b). Concentration of contractive stochastic approximation: Additive and multiplicative noise. Preprint arXiv:2303.
[23] Chen, Z., Zhang, S., Doan, T. T., Clarke, J.-P., and Maguluri, S. T. (2022). Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning. Automatica, 146:1 10623.
[24] Chen, Z., Zhang, S., Zhang, Z., Haque, S. U., and Maguluri, S. T. (2025). A non-asymptotic theory of seminorm Lyapunov stability: From deterministic to stochastic iterative algorithms. Preprint 20..20002.4228.
[25] Devraj, A. M. and Meyn, S. (2017). Zap Q-learning. In Advances in Neural Information Processing Systems, pages 2235-2244.
[26] Durmus, A., Moulines, E., Naumov, A., Samsonov, S., Scaman, K., and Wai, H.-T. (2021). Tight high probability bounds for linear stochastic approximation with fixed stepsize. Advances in Neural Information Processing Systems, 34:30063-30074.
[27] Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I., et al. (2018). IMPALA: Scalable Distributed Deep-RL. with Importance Weighted Leaner Architectures. International Conference on Machine Learning, pages 1407-1416.
[28] Even-Dar, E., Mansour, Y., and Bartlett, P. (2003). Learning rates for Q-learning. Journal of machine learning Research, 5(1).
[29] Gosavi, A. (2006). Boundedness of iterates in Q-learning Systems & control letters, 55(4))347- 349.
[30] Haque, S. U., Khodadadian, S., and Maguluri, S. T. (2023). Tight finite time bounds of two-time-scale linear stochastic approximation with Markovian noise. Preprint arXiv:2401.00::
[31] Haque, S. U. and Maguluri, S. T. (2024). Stochastic approximation with unbounded Markovian noise: A general-purpose theorem. Preprint arXiv:2410.21704,
[32] Huo, D., Chen, Y., and Xie, Q (2023). Bias and extrapolation in Markovian linear stochastic approximation with constant stepsizes. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 81-82.
[33] Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994). Convergence of stochastic iterative dynamic programming algorithms. In Advances in neural information processing systems, pages 703-710.
[34] Jaksch, T., Ortner, R., and Auer, (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1 |1(Apr):
[35] Jin, Y., Gummadi, R., Zhou, Z., and Blanchet, J. (2024). Feasible Q-learning for average reward reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1630-1638. PMLR.
[36] Jin, Y. and Sidford, A. (2021). Towards tight bounds on the sample complexity of average-reward MDPs. In International Conference on Machine Learning, pages 5055-5064. PMLR.
[37] Kara, A. D. and Yuksel, S. (2023). Q-learning for continuous state and action MDPs under average cost criteria. Preprint 078552200..07591.
12

---

[38] Kloek, T. and Van Dijk, H. K. (1978). Bayesian estimates of equation system parameters: An application of integration by Monte Carlo. Econometrica: Journal of the Econometric Society, pages 1-19.
[39] Kushner, H. J. and Clark, D. S. (2012). Stochastic Approximation Methods for Constrained and Unconstrained Systems, volume 26. Springer Science & Business Media.
[40] Lan, G. (2020). First-Order and Stochastic Optimization Methods for Machine Learning. Springer.
[41] Lauand, C. and Meyn, S. (2024). Revisiting stepsize assumptions in stochastic approximation. Preprint wwXiv2240S.1782.
[42] Lee, D. (2024). Final iteration convergence bound of Q-learning: Switching system approach. IEEE Transactions on Automatic Control, 6977)4766-4472.
[43] Levin, D. A. and Peres, Y. (2017), Markov Chains and Mixing Times, volume 107. American Mathematical Soc.
[44] Li, G., Cai, C., Chen, Y., Gu, Y., Wei, Y., and Chi, Y. (2021). Tightening the dependence horizon in the sample complexity of Q-learning. In International Conference on Machine Learning, pages 6296-6306. PMLR.
[45] Li, G., Cai, C.,, Chen, Y., Wei, Y., and Chi, Y. (2024a). Is Q-leaming minimax optimal? a tight sample complexity analysis. Operations Research, 72(1):222-22 2
[46] Li, G., Wei, Y. Chi, Y., Gu, Y., and Chen, Y. (2020). Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. Advances neural information processing systems, 33:7031-7043.
[47] Li, T., Wu, F., and Lan, (2024b). Stochastic first-order methods for average-reward Markov decision processes. Mathematics of Operations Research.
[48] Li, X., Yang, W., Liang, J., Zhang, Z., and Jordan, M. I. (2023). A statistical analysis of Polyak-Ruppert averaged Q-learning. In International Conference on Artificial Intelligence and Statistics, pages 2207-2261. PMLR.
[49] Melo, F. S., Meyn, S. P., and Ribeiro, M. I. (2008). An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning, pages 664-671.
[50] Meyn, S. (2023). Stability of Q-learning through design and optimism. arXiv:2307.02632. 02632..
Preprint
[51] Meyn, S. (2024). The projected Bellman equation in reinforcement learning. IEEE Transactions on Automatic Control.
[52] Meyn, S. P. and Tweedie, R. I.. (2012). Markov Chains and Stochastic Stability. Springer Science Business Media.
[53] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness. J., Bellemare, M. G., Graves, A.. Riedmiller, M., Fidjeland, A. K., Ostrovski, G., al. (2015). Human-level control through deep reinforcement learning. nature, 51807540):529-533.
[54] Mou, W., Li, C. J., Wainwright, M. J., Bartlett, P. I.., and Jordan, M. I. (2020). On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947-2997. PMLR.
[55] Mou, W., Pananjady, A., Wainwright, M. J., and Bartlett, L. (2021). Optimal and instance- dependent guarantees for Markovian linear stochastic approximation. Preprint 12.
[56] Paulin, D. (2015). Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20:1-32.
13

---

[57] Puterman, M. L. (1995). Markov Decision Processes: Discrete Stochastic Dynamic Program- ming. Journal of the Operational Research Society, 46(6):792-792.
[58] Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Program- ming. John Wiley & Sons.
[59] Qian, X., Xie, Z., Liu, X., and Zhang. S. (2024). Almost sure convergence rates and concen- tration of stochastic approximation and reinforcement learning with Markovian noise. Preprint arXiv:2411.13711
[60] Qu, G. and Wierman, A. (2020). Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Conference on Learning Theory, pages 3185-3205. PMLR.
[61] Robbins, H. and Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407.
[62] Shwartz, al. (2012). Online learning and online convex optimization. Foundations and Trends@ in Machine Learning. 4(2):107-194.
[63] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419): 140-114444 1144.
110-1999:111-1444
[64] Singh, B., Kumar, R., and Singh, P. (2022). Reinforcement learning in robotic applications: a comprehensive survey. Artificial Intelligence Review, 55(2):945
[65] Srikant, R. and Ying, L. (2019). Finite-time emror bounds for linear stochastic approximation and TD-leaming. In Conference on Learning Theory, pages 2803-2830.
[66] Suttle, W., Zhang, K., Yang, Z., Liu, J., and Kraemer, (2021). Reinforcement learning for cost-aware Markov decision processes. In International Conference on Machine Learning, pages 9989-9999, PMLR.
[67] Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT press.
[68] Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine learning, 16(3):185-202.
[69] Tsitsiklis, J. N. and Van Roy, B. (1999). Average cost temporal differeee learning. Automatica, 35(11):1799-1888.
[70] Wainwright, M. (2019a). Stochastic approximation with cone-contractive operators: Sharp Lx bounds for Q-learning. Preprint arXiv:
[71] Wainwright, M. J. (2019b). Variance-reduced Q-learning minimax optimal. Preprint 04697.
[72] Wan, Y., Naik, A., and Sutton, R. (2021a). Average-reward learning and planning with options. Advances Neural Information Processing Systems, 34:22758-221 22769.
[73] Wan, Y., Naik, A., and Sutton, R. (2021b). Learning and planning in average-reward Markoy decision processes. In International Conference on Machine Learning, pages 10653-10662. PMLR.
[74] Wan, Y., Yu, H., and Sutton, R. S. (2024). On convergence of average-reward Q-learning in weakly communicating Markov decision processes. Preprini arXiv:2408. 16262.
[75] Watkins, C. J. and Dayan, (1992). Q-learning. Machine learning, 803-4)277--992.
[76] Wei, C.-Y., Jahromi. M. J.. Luo, H., Sharma, H., and Jain, R. (2020). Model-free reinforcement learning in infinite-horizon average-reward Markov decision processes. In International conference on machine learning, pages 10170-10180 PMLR.
[77] Yang, X., Hu, J., and Hu, J.-Q. (2024). Relative Q-learning average-reward Markov decision processes with continuous states. IEEE Transactions Automatic Control.
14

---

[78] Yu, H., Wan, Y., and Sutton, R. S. (2024). Asynchronous stochastic approximation and average- reward reinforcement learning. Preprint arXiv:2409.03915.
[79] Zhang, S., Yao, H., and Whiteson, S. (2021a). Breaking the deadly triad with a target network. In International Conference Machine Learning, pages 12621-12631. PMLR.
[80] Zhang, S., Zhang, Z.., and Maguluri, S. T. (2021b). Finite sample analysis of average-reward TD-learning and Q-learning. Advances in Neural Information Processing Systems, 34: 14:0-22-12
[81] Zhang, Y., Huo, D., Chen, Y., and Xie, Q. (2024). Prelimit coupling and steady-state convergence of constant-stepsize nonsmooth contractive SA. Abstracts of the 2024 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, pages 35-36.
[82] Zhang, and Xie, Q. (2024). Constant stepsize Q-learning: Distributional convergence, bias, and extrapolation. Preprint arXiv:2401. 13884.
[83] Zhang, Z. and Xie, Q. (2023). Sharper model-free reinforcement learning for average-reward Markov decision processes. In The Thirty Sixth Anmual Conference on Learning Theory, pages 5476-5477. PMLR.
15

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction clearly state the problem we study (i.e.. average-reward Q-eaarning) and highlight the main contributions in terms of results and technical tools developed.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals motivation long it is clear that these goals not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The main limitations are discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification: The assumptions are clearly stated the paper, and the complete proof presented in the appendix.
16

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification: This is a theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This a theoretical work.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
17

---

Please see the NeurIPS code and data submission guidelines cctpp// Laaddes/CodeSubmii sylcccl for more details.
While we encourage the release code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //tpp//ip.paa/pe/ cc/public/ /uides//Coeeuubrs wwwibbiissionn ssssssolllls Poooollcyyy for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reprodueible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This a theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
18

---

8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [NA]
Justification: This is theoretical work.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't t make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, every respect, with the NeurIPS Code of Ethics httpp::/neeut ips.
Answer: [Yes]
Justification: The authors have read the NeurIPS Code of Ethics and confirm that the research conducted in this paper conforms to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
The authors should consider possible harms that could arise when the technology being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
19

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
20

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
The core method development this research does not involve LLMs as any important, original, non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-standard components.
Please refer to our LLM policy http:p///eerrppp.c///////eeee/ee http:////.oooeeeeeee///////////. for what should or should not be described.
21

---

Appendices
A Proof of Theorem 3.1
We follow the road map described Section to prove Theorem 3.1.
A.1 Markovian Reformulation of Non-Markovian Stochastic Approximation
Let ZІ (D,, Sk, Ak, Sk+1) for all & 2 1, whose state space is denoted by Z. To see that {Zx} forms ihmooooooogee Markov chain, given Z (Dz, Sk, Ak, Sk41). consider the distribution of Zu+1 = (D&+1, Sk+1, 1,,1, Sk+2). Since S is given in Zu. A&+1 ~ (-1(S++)). Sk42 pl- 1541,Ax+11 and
Dx+1(s,a)= (s) ((S441)A( +
+ 1-11-11 h (k + h)) a) +
+ (s,a),,
(13)
+ 1
which deterministic function of k, (Sk+1, As+1), and DR. the stochastic process { is a simeinhhmmoeeneou Markov chain, where the time inhomogeneity arises from the fact that the transition of D& depends on k.
Although } is time-inhommognneuus, it admits unique limiting distribution μı satisfying Hz (D, su, au, $1) = 1 - (u( ( 6o (p)p((1 So. oo). which follows from Assumption 3.1 and the strong law of large numbers for functions of Markov chains [52]. However, since it is well known that the convergence rate from D3 to D is Ok--1/k (measured in B||| D1l2),, which is sublinear, the Markov chain {2x} } does not exhibit the geometric mixing property typically used in the cxisting study of Markovian SA.
With Zu defined above, to reformulate Algorithm as a Markovian SA, let F: -RSSIAA x Z + [RISIAI be an operator defined such that given input arguments Q E RRSS|A and z = (ñ, 80, Cn, 81) E 2, the (s, a)-th entry of the output of the operator is given by
1 [(=00.0)==(sa)) (R(so, an) + max Q(s1, QS0, a0) + Q(, (1s,a). a). (14)
=)),,a))
D(s,a) a)
EA
Using the definition of Z& and F(-), the main update equation from Algorithm can be written as
Qx+1 Qx (F( Za) Qk),
(15)
where =k) The properties of the operator F(-), along with its connections to the Bellman operator H((-) are summarized the following lemma, whose proof is presented in Appendix B.
Lemma A.1. The following properties hold regarding the operator F()).
81) E D, we have (1) For any Q1 Q2 D, and y (so, ag. ag)
2 Pspan (F(Q1, F(22, S D(so. oo)
Pspon (Q1 Q2).
(2) For any Q, D. and y = (8o, on, 81) Y, we have
2
Pspan (F(Q, <
(Pspan (Q) + 1).
D(so, ao)
(3) For any Q, we have Ey [F(Q D, DY) H(Q)).
Among the properties stated in Lemma A. Parts (1) and (2) present the Lipschitz continuity of F(-) and its at-most-affine growth with respect to the estimated Q-function. However, we point out that Lipschitz constant inherently random in our analysis, as depends on the input argument î, which corresponds to the empirical frequency matrix Dę. Lemma A. (3) further states that the operator
22

---

F()) is an asymptotically unbiased estimator of the Bellman operator H-()), thereby justifying that Eq. (15) represents an SA algorithm for solving the Bellman equation (2).
Since the Bellman operator H())) will also frequently appear in our analysis, we summarize its properties in the following lemma. See Appendix B.2 for the proof.
Lemma A.2. The following properties hold regarding the Bellman operator H(-))
(1) For any Q1, Q2. we have Papan (H(Q1) HH(Q2)) S Pspan QQ1 -Q2).
(2) For any Q, we have Pspan (H( S Pspau (Q) +
Remark. The proof of Lemma A.2 also implies [[H((1)) H(Q2) S 11 Q21l for any Q1 and Q2. This suggests that a possible direction for relaxing the seminorm contraction mapping assumption (cf. Assumption 2.1) is to consider (time-inhomooencoous) Markovian SA under non- expansive operators, as discussed Section 6.
A.2 Lyapunov Framework for the Analysis
After reformulating Algorithm 1 in the form of Eq. (15), we will use a Lyapunov-drift approach to perform the finite-time analysis. Inspired by [18, 21, 24, 81], we construct the Lyapunov function as the generalized Moreau envelope, defined as the informal convolution between the square of the span seminorm and the square of the ég-norm:
Mq.0(Q) = min
2
2 ul?
AQ e (
VERISTIAI
where both 2 1 and 0 O are tunable parameters yet to be chosen. For simplicity of notation, we will write (-) for M. throughout the rest of the proof.
Properties of this type of Lyapunov function have been thoroughly investigated in [21, 24], and are restated in the following lemma for the special case of the span seminorm, for completeness. Let by ([S||A))-2) and thy Note that we have tg 111 S I|Q lo uullQll, for any Q
Lemma A.3 (Proposition 4.1 from (24]). The Lyapumov function M has the following properties:
(1) The function M() convex, difserentiable, and satisfies
L M(Q2) & M(11) + (VM(Q1)) Q2 - -Q1) + 2 Popan (Q2 QQ)3 HQ,,Q2 e Rd,
where L = (=q-)))(((0)
(2) There exists seminorm (.), which satisfies Pm(Q) min ||Q cellm for some norm
|| Ilm such that M(Q) Pm (Q)2/2
(3) There exist Im (1 + 0/2 and Umm. (1 + Ou2)1/2 such that Pm (Q) S Pspan (Q) S unpP (n)Po(Q) for all Q A|
(4) It holds for all Q E IR S1|A1 and E E F that (VM(Q), = =0.
(5) It holds for all Q1, Q2, Q3 E RISIAI that (VM(QI) VM()2), Qa) < Lp (Qi 22) (Qa).
Lemma A.3 establishes several key properties of M(). Specifically, Part (1) states that M-) is smooth function with respect to the span seminorm. Part (2) states that M(-) itself can be written as the square of seminorm with kernel space {ce c RR. Part (3) states that M(-) can approximate the seminorm-square function Pspan (Q)² /2 arbitrarily closely, since limg- Um Cm = 1. This property, together with Part (1), implies that (Q) is a smooth approximation of Pspun (22) Part (4) states that the gradient of (.) is always orthogonal to ker ker(P.) Finally, Part (5) follows consequence of Parts (1) and (4).
Using the smoothness of (.) (cf. Lemma A.3 (1)) together with the reformulated update equation (15), we have for all & 2 1 that
B[M Q*)] < (Qu Q*) + E Q*), Q641 Q+)
23

---

L
El -
-
2
R + +r - Q²), F(Qu: 7x) - -Qx)
Lakk E Papun (F(Qk: Za) -xx)
(Lemma A.3 (4))
2
=QI Q²1 ag (QV -2), Q+1
T
+ +a (I(M((Q F(QK, D.Y.) H(Q))1
+
(VM(( Q*), F(QK, DR. Vb) - F(QU, D,
Ts
La 2
Pspan F(kk: 7k) 2x)
(16)
where Yú: (Sk, Ak. 1k+1) and is the |A|||| by |S||A] diagonal matrix with diagonal entries Recall that {Y& forms time- home-homogeneuus Markov chain, with state space denoted by V. Moreover, under Assumption 3.1, the Markov chain (Y&) admits a unique stationary distribution v E A(V), which satisfies (ss, a, s') ((s) s))(s' a) for all y (s, a, s') y.
In view of Eq. (16), remains to bound the terms Ti, T2, Ta, and T4. We begin with the term Ti, which can be viewed as the "deterministic" part of Algorithm I because F(., Zz) is asymptotically unbiased estimator of H(.). We show the following lemma that the term Tj provides a negative drift. The proof of Lemma A.4 is presented in Appendix B.3.
Lemma A.4. It holds for all k 2 1 that Ti S 2 Q²)]. where Φi 1 - Bum em-
Since lime- Un// lm and 3 E (0, 1), we can make Φi strictly positive (thereby ensuring a negative drift) by choosing appropriately.
Moving to the terms T2. T3. and T4 in Eq. (16), the term T. accounts for the error due to the Markovian noise {Yx}, the term T3 accounts for the error in estimating the matrix D using the empirical firquency matrix Dx. and the term T2 arises due to the fact that Eq. (15) is a discrete-time algorithm. To show that all of them dominated by the negative drift provided by the term Tú, the analysis is different from and significantly more challenging than the existing literature on Markovian SA. Specifically, the main challenge in bounding these terms lies in handling the correlation among the iterate Qk- the empirical frequency matrix DR. and the Markov chain (Y& }- In the existing literature, if the underlying noise sequence is i.i.d. forms uniformly ergodic Markov chain, such correlations can be handled using either an approach based on conditioning and mixing time [65] or a more recently developed approach based the Poisson equation [17, 30, 31J. Unfortunately, neither approach is applicable here due to the fact that [Zx- (Dx, } is time-inmoonee inmooonhoooesssuu and lacks geometric mixing.
A.3 Breaking the Correlation
Our approach to breaking the correlation relies on a combination of almost-sure time-varying bounds, conditioning arguments, and concentration inequalities for Markov chains. To illustrate this approach, we use the term T1 T4, the term T2 is the easiest to handle. Specifically, since the term T2 is multiplied by az in Eq. (16), it suffices to show that T4- = Õ(1) for it to be dominated by the negative drift (cf. Lemma A.4). In contrast, for the terms T2 and T3, we need establish that they are o(1), which is more challenging.
example. Before proceeding,
note that among the error terms T2. Ts. and
According to the definition of F(.) in Eq. (14), the vector F(Q Z+) Qx has only one non-zero entry, i..., the (Sx, As)-th one. Therefore, we have by the definition of Pspan( (-) that
Ta = Elpspan! (F(Qk. Dx, - - 2
2 Ax) + max Q4 (s(+2,)) Qu.. A4) AA) 27 d'EA
(D((k,AAi) (Du(st.
(R(SE) As)
4
24

---

A )r
2
- - |)
- 1
Dkk As)
(R(SS)) Ax)1+
a'EA
max
(T((St_AA))
) De Ax) (1 2gspan Qx))²
2
B
(17)
To proceed, the immediate challenge we face is that the random variable (s Ax), which rep- resents the frequency of visiting the state-action pair (Sk, in the first & time steps, is strongly correlated with Qs.
Step One: Time- Vare--arying Almost-Sure Bounds. The first step of our approach break the correlation between (Sk. Aa) and Qs is to show that the iterates Qk. while not uniformly bounded by constant (which is a key difficulty compared the discounted counterpart [29]), admit time-varying almost-sure bound. Specifically, we have the following proposition.
Proposition A.I. The following inequality holds for all k 2 1:
Pspan (Qx) S by:
where by: = || log(
[U=-)/[[S]AA]+4
Remark. Note that the proof of Theorem 3.1 for h E (-1) is complete, since Proposition A.1 implies Pepan (Qu- Q")
) S Pspan (Q.) Pspam (Q") by + PQ" a.s. for all k.
Proposition A. a non-trivial observation, as the bound holds independent of the randomness the sample trajectory and grows logarithmically in k. These two features together enable us to decouple the iterate Qx and the time-inhomogeneous Markovian noise Zx. The proof of Proposition A.1 (presented in Appendix B.4) relies on combination of induction and combinatorial argument.
Apply the almost-sure time-varying bound from Proposition A.1 Eq. (17), we have
(D
2
T4 S (SK,, Ax)
(1 + 2p (Qx))²
1
$ (1 + bz)² F.
Du Ax)2
((S..AA)=(3.0)) a)
(1 + bp)
E
(18)
8,0
Step Two: A Conditioning, Argument. In view of Eq. (18), it remains to bound the quantity E[1 ((S.AA))))))) (D,(,, a} for any (s,a). The immediate challenge lies handling the corre- lation between the empirical frequency Da(s, a) and the indicator function I ((Sv.AA To address this issue, we apply a conditioning argument, which inspired by [65]. Specifically, since aa(s,a) = aN) h)/(k: h1), we have for any (8, a) and < k- 1 that
((SL:AA)=(Aaa))
(Sk,))(SA,AA))) (k+ h)2
E
=E
Ds(s,a)²
(N*(s, a) + h)2
1 ((saa)=
h)2
E
(N (8, a) + h1²
(The pair (Sk, As) is visited at time step k.)
(Sc.)))) (K h)2
SE
E
(N, a) is an increasing function of k:))
(Nt-+-1 a) + +1+ h)2
(k + h)2 P(S; = s, A, = a Sp (N + +1 h)
E
(19)
where the last equality follows from the tower property of conditional expectations and the Markov property.
25

---

Under Assumption 3.1, the Markov chain {(Sx, AA)) also enjoys geometric mixing. As result, we have
P(S: = s, A = -
$ (S A, = - D(s, a)) D(s,a)
$ 2Cp'p (ss,a)
s (s,
(20)
where the last line follows from choosing 5 = min(t: Cp' S D Dmnn) See Appendix B.8 for more details.
Combining Eqs. (18), (19), and (20), we have
(k 11)
Ti S 21 bb)²²
a)) (Na-i-1(sa)) A)
(21)
8,0
Step Three:
To proceed from Eq. (21), the last challenge we face here is that the random variable N a) appears in the denominator of the fraction, which breaks the linearity. We overcome this challenge by using Markov chain concentration inequalities.
Markov Chain Concentration.
For simplicity of notation, denote D (8 = - (s,aa(k - F - 1). Given 5 E (0, 1), for any (s, (s,a), let Ea(s, a) (iDx-F-(ss, a) Dss, a)l 6D(s, and let Es a) be the complement of event (s, a). Note that on the event Es a), we have D a) D(s a) s (s, a), which implies D 2 (1 - D(,, a), while on the event (j a), we have the trivial bound D D () 2 0. Therefore, we obtain
(k+
(A: h)2
E
E
(N (NN- + +++++0 h)2
L((k - -- 1)Dx= 18, a) + + 11)
1 (E)(H,)) + (E7(s,0))
(k + 1:)
F (1)---1)D---- 1) +1 h
(k: + h)2
(I: + h)
(k: - (1- (1=))) +
P (s))((s))) a)). (22)
(h+ 1)2
To bound (sE),s, a)), we use the following Markov chain concentration inequality, which consequence of [56, Corollary 2.11]. The proof of Lemma A.5 is presented in Appendix B.5.
Lemma A.5. Let {x*]=21 be a finite, irreducible, and aperiodic Markov chain taking values in X' = =1=11,,33, (1,2,3, ... nn.. m.). Denote its unique stationary distribution by E A(X). Let > and I E (0,1) be such that maXeex IIp(X, = X1 = x) v(-)llrv S C for all k 2 1. Then, there exists
(which depends on the mixing time of the Markov chain) such that the following 40
inequality holds for all e 2 [I-M
P (1( v(x)) 2 2) S 2exp((cckk) VEEX.
where (x) Σj 1x
1)82D(ss D(s, a)2) for any 8 > 4C (1 - (k 7 - 1)], where Cmce > 0 is a constant depending on the mixing time of the Markov chain (SE, As)). Combining the previous inequality with Eq. (22) yields
Apply Lemma A.5 and we have P(E a)) < 2 2exp(-Cmeek:
(k: + h)2 (Na 11
(k + h)² (k- 1)3 (1 -8)DDs,a))
E
+ 2(k: h)2
exp(-cmo(ts - - -1))
(h + 1)²
3
< D ass
where the last line follows from (1) choosing properly based on k; and (2) when & large enough. See Appendix B.8 for more details.
26

---

Finally, using the previous inequality in Eq. (21), we have the following lemma, which shows that T4 (1). A more detailed proof of Lemma A.6 (following the road map described above) is presented in Appendix B.8.
Lemma A.6. The following inequality holds for all 2 K: Pspan (Q") 1)²
[8|8||A|(
T4 S
Duin
Following similar ideas, specifically, combining the time-varying almost-sure bounds (cf. Proposition A.1) with conditioning arguments and Markov chain concentration results (cf. Lemma A.5), we are able to bound the terms T2 and T3 on the right-hand side of Eq. (16). The results are presented in the following two propositions.
Proposition A.2. The following inequality holds for all k: 2 K:
T 2 + Psspan' (Q") 1)2 ak.
D2 min
Proposition A.3. The following inequality holds for all k 2 K:
Ta S S1 - QQ")+ 32C
| SIAA (bx + Pspon (Q") + 1)²
R2 O (1 p)aDDi min
Okk-
The proof's of Propositions A.2 and A.3 are presented in Appendices B.6 and B.7, respectively, Using the bounds we obtained for the terms Ti, T2, Ts. and T4 altogether in Eq. (16), we obtain the following result.
Proposition A.4. The following inequality holds for all k 2 K:
[QM - Q') s (1 (1a)) Q*)] + The Pipan (Q") + 1)
(23)
where
C|S|IAA
LA
Φ
(1 p) 61 D2
min
D2
min
Note that Eq. (23) is one-step Lyapunov drift inequality of the desired form: it exhibits a negative drift with an additive error that is order-wise smaller than the magnitude of the drift.
A.4 Solving the Recursion
This part is standard the non-asymptotic analysis SA algorithms. Repeatedly applying Proposi- tion A.4, we have for any A: 2 K that
1-1
(Q^ 23)
II j=K
(1 - E[M(KK Q*)]
+ 35
(B + Popan (Q") 11' of
II (1 01az). j=i+1
To translate the result to bound on [E[pspan (Qu (2) using Lemma A.3 (3), we have
1
2u Popun (Q) < M(Q) = Pm (Q) < 2P2
Pspan (Q)2
It follows that
EE ElIpspan (Qu
< 2u 2ur E. B.M - Q")I
k-1
< 2u m II
(1 - 2 BLM Q*)]
j=k
27

---

k-1
k-1
+ 70
22
TB + Pspan (Q")+
II (1 - Φ1aj)
m
==
j=++1
k-1
(1 010;) 1l/ssan -
m
j=k
+ 70 22
Te (B; + Pspan (Q")
II 4=i+1
(1 Φ1a3)
i= K
k-1
Um f2
(bx + Popan (Q))²²
II (1 &10;)
J=K
k-1 k-1
70 T2 + Papan (Q') + 1)²
Σ
(1 01a5),
i=
jmi+1
where the last inequality follows from
Pspan (Qx Q") Papan (Q + Pspan Pspan(Q")) S bx Pspan (Q").
Before we proceed, we finalize the choices of the tunable parameters q and B in the definition of M.) to make all constants on the right-hand side of the previous inequality explicit. Specifically, by choosing
11
2 - 1, = 2
0 =
2,9
we have ul = 1 and la = d d- 1/1 = 1/Ve, which further implies
1
2 1 Ou
1 05
<4
(Assume without loss of generality that 3 > 1/2.)
82
2 + Ou?
1+0
$ Ve
33
2
+ 002
1 1 0/ve
m
Φ1 1 Bum
1 1+ 3
1- B
2
2m
2B
2
1
6 6log((511A1)
L
022
3
70u 2 ||||A|
Omc
70u2.. 02
m
Bumm 1m )c + +L)
D2 min
S|A
20
61og(15|(A)
+
D2 min
(1 - p) - 3)a
1- 3
(2240C|SS|A44 log( (((AA)
(1 B) -P) min(1, a))
Therefore, we have for all K that
(1- - B)a
Blppsan (Q+- -Q*) < 3(bx + Pepan (Q)))²
1
2
==
:=
+ 2240C/S[[4[[og((|]144]
R-1
k-1
(1
B)az
(1 31 D2 min (1, Th (bx + Pepan (0pan(Q2) (Q") 1)2
1
2
k=
j=1+1
(24)
28

---

It remains to bound the terms E1 and Ez. For simplicity of notation, denote c = (1 -1- -1233 Then, since ag a/(kk h), we have
E1
II (1
ca.))
j=K
k-1
S exp
Σ caj
7
ca
exp
j=K j + h
J/ coE
S exp
dx
K x + h
k ck+ h K K+h
exp
-ca log
K +h+
k +
Similarly, we also have
E2
(1-ca;)
j=++1
k-1
II (1-ca;)
1=1+1
k-1
a²
i 1h h
ca
+ h)2
+ h
1= K
4a²
k-1
1
(A: + h)ca
(i + + h)2-ca
1
ca (0,1),
ca
4a
$ (k: + h)aa
log(k: + h))
co 1,
(k+ + h)aa-1
ca oo).
Ca
4a²
ca E (0,1),
(k + h)00
ca
Alog (: + +h)
ca =1
(k + h)
12a
ca E (1)
(k: + h)
Using the previous two inequalities together in Eq. (24) and recalling that c= (1 - BB)/2, we finally obtain the desired finite-tinn bound:
(1) When a(1 B) 2, we have
-tt-9
K + h k
Elyipan (Q Q²) < 3(bx + Pspan (Q'))²
C7920a2C/3]]|| [S)
Tk (br + Pspan (Q*)+
+ 1)2
[1 - (1 - Dp) min (1, (2 - (1 - -3)a)
(k: + (1(111))/2
29

---

(2) When a(1 - B) 2, we have
K +
E Pssan (Qx - Q2) = 3(bk + Pspan Pspan (Q"))²
h h
35840C|S|||||og/ (AA) Th (bb + +
(²)) + 1)² log(k: +
(1- 3)
(k + h)
(3) When a(1 - B) > 2, we have
aft-
K + h
El E(pspan 2 Popun (Q)))
53760a (og(())
The Tk(bk + Popun (opun(Q² (Q") 1)²
(1 - p)(1 - Rin ((1 3)a 2)
(k: + h)
The proof of Theorem 3.1 is complete.
A.5 Proof of Corollary 3.1.1
By Jensen's 's inequality, have
E Pspan (Qx - Q-'
EiPspan (Qx - -Q")
To achieve E Plps (Qk 2²) S 2, uusinn Theorem 3.1 with the case a(1 - (3) we have
15 || 8 Psna (?')
k ==
D2 min (1 3) p)c
To bound Pspan (Q") in terms of B, using the Bellman equation, have
Pspan ( (")) )
= Pspan (H(Q") r*e)
Pspan (H(Q") H(()) + Pipan (H()))
S span (Q*) +
where the last inequality follows from Lemma A.2. Rearranging terms, we obtain Pspun (Q*) < 1/(1 - 3). Therefore, the overall sample complexity is
LA (1- (1- p)22
D2 min
B Proofs of Technical Lemmas and Propositions in Support of Theorem 3.1
We begin with summary of notation.
For any & 2 1, let DR. Dr. and D be |S||A] x |S|A diagonal matrices with diagonal entries {(Na(s, + h)/ + + {Nu(s, a) (x.A)ESAA and (a(s))([[s))
respec- 1l ((ss.))))=(())) counts the number of times the state-
tively, where we recall that a= action pair (s, a) has been visited up to iteration k. For simplicity, we will write De(s, a) to denote the (s, a)-th diagonal entry of DR: similarly for (s a) and D(s, a). Let Dunin ming (a))s( which is strictly positive under Assumption 3.1.
Let Zμ, = (D. Ar. 1k+1) for all & 2 1. Note that { is time-inhomogeneous Markov chain with state space denoted by Define Y3 = (St, Sk+1) for all k: > 1. clear that (Yx) is also Markov chain, with state space denoted by y. Moreover, under Assumption 3.1, the Markov chain (Ye) admits a unique stationary distribution v A(Y), which satisfies a(s,a,s)) u(s) ( )p(s (s, a) for all (s,a,5) y.
B.1 Proof of Lemma A.1
(1) Let RIS|AA be defined
F(Q1, D.v) F(Q2. (Q1 Q2).
30

---

It is clear by the definition of F(-) that
a(s.a)= D(so. an)
1
max (1(1 max Q2(s1, a²) Q1 (su, ao) + Q2(80, au) a'EA
if (8, a) (50, an) and (s, a) otherwise. By the triangle inequality, have
Popun (Q,, D. y) FQ2.. D, I Pspun (Q1 - Q2) + Popun (T).
(25)
To bound Popan (z). since æ has only one
entry, we have
max Q1(81, max Q2(81, (Qi(s0, (o) Q2(s02 an)) ''EA
Pspan(2)) (s0, an)
a'EA
(26)
To further bound the absolute value, observe that on the one hand, we have
max Q1 a') max Q2(51, a') (Qi ao) (2)ss,
a'EA
a'EA
S max (Qi(s', ,a) 12(''22''''000 min min(Qi - s',a'
8,a'
ppm @1 - Q2)-
On the other hand, since
max
(1 a') max Q2(81, max Q1()), - Q2(11.)) a'
a'
(Denote a E arg max Q2(51,a'))
21( Q2(81,))
min min(Qi(s', Q2(''
we have
max Q (81, a') max a'EAA
a'EA Q2 d') - (80 ao) - Q2(s0, an))
min(Q1(s', d') Q2(s', (00, 0o) Q2(s0, ao))
s'aa
min (Qinn d²) -2(5', max 8'
2pspan ( (Q1 Q2).
It follows that
Qi(s),d') max Q2(51, d') (Qi an) Q2(50, on)) $ 2p (Q1 Q2).
max
R'EA
a'EA
Using the previous inequality in Eq. (26), obtain
ao) Popan (x) - D(so, ao) Pypan (Q1 - Q2)-
Combining the previous inequality with Eq. (25), we have
Pspun ((Q1. F(Q2. D. S Pspan (Q: - Q2) + Papaa (2)
(22)
1
< D(so, an)
Popan (Q1 - Q2)
Pspan (Q1 Q2),
D(su, an)
where the last inequality follows from D(s,a) E (0, for all (s)
(2) By Part (1) of this lemma, we have
Pspan (Q. S Pspan L.Q.DDD) F(O, D. + Pspan (F(O, D.v))
31

---

2
Popun (Q)
(Q) + Popan (F(O, D, v)).
(s0: ao)
Since the vector FOO, D.v) to ((so, an) D (so, 0o), we have
v) has only one non-zero entry, i.e., the (so, )-h entry, which is equal
1
1
Popan ((0,, D.v)) 2 ao)
R(so: ao)l S
25(0 ao)
Combining the previous two inequalities, have
2
2
Popan ((Q,D,)) -
Popan (Q) + 25( ao)
(Pspan (Q) + 1).
D(so, an)
D(s0. ao)
(3) For any (s) we have
By (T]][[(().)))]((s..)
((o)) on) ((0))))=((aa))
(s
90,00.e1
R(s0, ao) + max (811 - ((50 (00.ma)) + Q(s,a)
x
d'EA
D(s, a)p(s11s, D(s,a)
Σ
R(s,a) + max - Q(3,a)) + ((s,a)
Σ p(sils,a)
(maaa))+mxx)))m R((sa) + max Q()1,a)))
(s..))(s.a).
B.2 Proof of Lemma A.2
(I) For any Q1, Q2 E R S) Al and e E IR we have
[HQQ)) - cl [H(Q))](ss
E
max d'Ed
Q1 - c) - max d'EA
Q2 |dlel S = 8, A1 = a
max N'EA
Q1 (1(, -c) max (2 d') |dle| S = 8, A1 = a d'EA
<
E
max Q1 d') - O2(S2,a') - cl |dle| S = 8, A1
a'EA
< 1 - Q2 - cel
The above inequality implies
[1?((1)) H(Q2) cell I 1|11-1 - Q2 - -ceooloo: VQi E |SIIAA
c CER. R.
As a side note, by setting 0 in the above inequality, we have
(H((1) (l2) S ||Q: Q2llac, VQ1, |
To show the exanssaanssee property with respect Pspan (+), let ē arg min ||Q1 -Q2 celloo. Then, we have
Pspan (H(Q1) - H((22))
= min [[{(()) - H(Q2) - cel1
CER
< [lH((1)) -H((2) 10
< [1Q - Q2 - 100
Pspan (Q= Q2).
32

---

(2)
Using Part (1) of this lemma, we have
Pspan (H(Q)) S Pspan (H(Q) *H(0) + Pspan (H(()) S Pspan (Q) + Pspan (H(0)).
Since
Pogun (H((0) - [[7((0)] = max (R(s, 5 8,0
have
Popan (H(Q)) Papam (Q) +
B.3
Proof of Lemma A.4
Since H(Q") Q" = =r"e E ker(Pspan) we have by Lemma A.3 (4) that
(VM(Qu- - Q*) H((x)) Qu) = (VM(Qx Q"), H((Qk) (((0))+Q Quk)
= (VM(Qu Q"), H(Qx) H(1)))
Tii
(V Q*), Q Q+)
(27)
11.2
Next, we bound the terms Ti, and Ti, on the right-hand side the previous inequality.
Since (Q) Pm 32) differentiable, have
(M())) = Pm (pm
A E SIAA
follows that for any e I, we have
Ti, (M - (",, H(Qx) H(Q") ce)
(Lemma A.3 (4))
Pm (Qu - (Vm (Qx - Q'), m(Q2)) - H(Q²) ce)
Pm 5m (Qx Q²)[[ (Q Q1))l m1) - -H(Q") cce|ms
where || Ilm, is the dual norm of || Ilm- Since
(Qm()1) Pm pmmpp2p010) (Q2) Pm (Q: Q2) min 11 - -2-deell - 1Q Q2llms
c'Elt
the function Pm (.) is 1-Lipschitz continous with respect to || |l It then follows from [62, Lemma 2.6] that Pm Q+ Q" mmm, S. Therefore, we have
Ti,1 S Pm (Qx Pm 10m)_m
H(Q²) cellm
I (m( ()) H(Q*) -e|l
pm(Qu Q" (H({)) H((")))
(Choosing = arg min [[H(Q.) H(Q²)) - c'ellm)
1 Pm (Qn(Qx P (pppn(((()))) H((²))
(Lemma A.3 (3))
km
3
Pm (Qu -(p') (Q: Q*)
(Assumption 2.1)
Lm
fum
pm (Qx Q²)²
(Lemma A.3 (3))
Em
28um M(Q - Q"),
(28)
Lm
where the last inequality follows from Lemma A.3 (2).
Next, we consider the term Ti,2 on the right-hand side of Eq. (27). Since pm( (-) a convex function, which follows from
(aQ1 + - aa))2) $ Pm (aQ1) + Pm (1- = apm. (Q,)(Q))
(1 a)pm (Q2)
33

---

for any E [0, 1] and Q1, Q2 RISIIA we have
Pmo (0) Pm (Qx - QQ") 2 VQm - Q-), Qa))-
follows that
T1 -VM(Q=-Q))
Q+)
Pm (Qk (V (Qx Q²),¹¹ Qu))
< Pm (mk Q²)²
2M(Qu Q*).
(29)
Finally, using Eqs. (28) and (29) together in Eq. (27), we have
(VM(Qu Q*) H(Qu) Qx) Ti 1 Tı,
Bum
2
MiQe Q")
fm
201 M MQx
Q*).
Taking expectations both sides of the previous inequality finishes the proof.
B.4 Proof of Proposition A.1
The following lemma is needed for the proof.
Lemma B.1. The following inequality holds for all 1:
Pspaa (k++1) I Pspam Qk) + (u Ax).
The proof of Lemma B.1 presented in Appendix B.10.1.
Recursively applying Lemma B.1 and then using the definition of an (Sk, Ak), we obtain
Pspan (Qx) S Pspan (Q1)
NAS A.) + h
k
a
1
A)
where the last line follows from Q1 = remains to bound the quantity Σ a/(N A,) + +
For any lo 2 define the set M as
M (S A)* {(8) (181,41..... $ 0i 1/8s E S,, a; E A, Vi = 1,2, ..., 1}.
Then, the following inequality holds with probability one:
N.,S,, A.) S
max (s1.01 JEM
Ni(si, oz) +h
Next, we identify a scheduling (81, (s,,01,...,,.)) side of the previous inequality. Let
0k-1) 0k-
that achieves the maximum on the right-hand
Nmax max (s.0)
1 ((..))))(..)))
(8, a) arg Max
((..)))))))))
(s.a)
Nmin min (9.0)
M
((..a))(ssa))
(s.g) arg min (5.a)
Σ [(sra)=((aa))
We now show that if scheduling optimal, must hold that Niax Nmin S 1. Suppose, for contradiction, that N Nmmn 2. Consider modified scheduling identical to the original one
34

---

except that, instead of choosing (3, â) at its last occurrence, we select (s,a) instead. modification, the objective increases by exactly
Under this
a
N Mmin
Naax
which is strictly positive since Maxx Mmn 2 2, contradicting the optimality of the original scheduling. Therefore, an optimal scheduling must satisfy Nmax - 1.
Next, we show that all schedulings satisfying Nmax - Miin S must yield the same value. Let where is the quotient and < |S||||] is the remainder. The only way to satisfy N max - miiin & for exactly n state-action pairs to be visited m + 1 times and the remaining ||||A| pairs to be visited times. For any such scheduling (s1, a1,' " 5k-1, Qk-1), the corresponding value is
k - = =
+ m|A||A||
m |ST|1|]
Σ i i
n0
(ss +h
m
+
Therefore, we obtain
max
(S A.) +h
(1........ 1, JEML a((s) +
|S|||| Σ
ith h
m +-+11 ++1+h
m-1
<a[8||A|
+ h
=
i+ h
where t [[k: - 1)) Since
Σ ith S S
(1+ h
dx log
E + h
h
conclude that
[kk- - 1)/((S|AA1) + +h). )
[(k
Papam (Qx) 2 ||
h
B.5
Proof of Lemma A.5
Fixing X, let W, x IR be function defined as
W₂ (x1, Ø2 .. px) Σk (z.
VILa E x*,
k
where we 1i,4 denote (21,022"" .k) for simplicity of notation. is clear that (-) satisfics
1
Wa 22 ".,,", II) Wn (2,, 9k) Σ
1 (mtucl VZLA. E 2
k
With the above notation, our goal is to bound P ([,, (X,, v(x) 2 c). Observe that
-
W (X E.W. x X )1) [EI,s v(x)).
Since
&
B[Wa(X -(x)] = - Σ
(xx x v(z))
35

---

p(X; = (1) u(x))
Σ 20p
2C
$ (1 - p)k
we have
2C
[Wa(X1,) - v(x) S (W(X1,.) B[W (XI + (1- p)k
Therefore, for any 2 [T-p}æ. applying Corollary 2.11 from [56]. we have
4C
2c
P P((,((X1A)) - 2 IP (Wa(X1.) - E 2 (1- p)
2t
2
< 2xxp
-c'k
(1 - [1-
d'ke²
< 2 exp
where e' is a constant depending on the mixing time of the Markov chain {Xa}.. The result follows by redefining& = e' d/44.
B.6 Proof of Proposition A.2
We begin with the following decomposition:
T2 E(VV - Q"), F(Qk, D. Vx) - H(Qx)))
E(V F(Qx -u D,Y - H((Qk
(Q - -Q"), D.Y,) (2 -(QO)
==12,
E(VM(QR Q*) VMI =2 Q"), F(Qu, D2 H((N)))
(30)
T=22.3
where we recall that minft: Cp- < a/(k (k + h)}
B.6.1 Bounding the Term 72,1
We begin with some notation. For any 1, let F& be the o-algebra generated by the set of random variables (Qi, S1, AI, S2, A2, Sh- A S. Note that Qu is measurable with respect to Fi. By the tower property of conditional expectations, we have for any & 2 т + 1 that
T2.1 = E (V - ""', F(QU - -
- H((Qk=1))) E F (Q=-T D.Y.)
< LE'pspon (Qk-T2 - Q") Papan [E[F(Qk-1 D, (x) -
where the last inequality follows from Lemma A.3 (5). According to Proposition A. we have
Pspan Qk-TH Q") < Papaa (Q=-Ta) + Popan
Poppn((n))) (Q*) S bi-Tz + Popan Pspaa(Q2)) S by + Pepan (²))
which further implies
22,1 - L(bb + Pspan P (Q")) (1a.PaaaaaEEEEFL. (2 H(Qu
36

---

< L(bx + Pspan ))
Σ vEy
Ip(Yr
y( (y))pp (F(Qu D.y1)
where the last line follows from Lemma A.1 (3) and the triangle inequality. On the one hand, we have by Lemma A.I (2) and Proposition A. that
Pspan ( (F(Qk- QQQ-TT v)) S (Pspan (Qu-Tx) + +1
2(bk-T + +1)
2(br +1) Dmnn
Dmnn
Dmnn
On the other hand, we have by Assumption 3.1 that
Σ
lYy = - v(y)]= = Σ
I((2 (So. ao: $1) s1))Ya v(s0, ao, 81)l
DEY
$0.40.$1
Σ
(Sx so(Sk-Te) ((so)) (s))p(ssspsssssoos ao)
$0,00.81
Σ
Ipx (Ss. SolSk-re) ((so)l
2 21p -1Sk- -n(-)llTV
< 2²p
Together, they imply
T2.1 S L(bb + Papan ( (Q))
Σ
Ip(2+ = (m00) (F(Qk-T):.
v(v)
NEY
4L + Popan ( (Q 1) CpT
D Dmnn
4bbbb Dspan (Q*))))) (bbe +1) a#k
(This follows from the definition of r..)
Duin
4T. + Papan(") + 1)2
Dmnn
ak.
(31)
for all k 2 +1.
B.6.2
Bounding the Term T2.2
The following lemma is needed to bound the terms T2,2 and T2,3 on the right-hand side of Eq. (30).
See Appendix B. B.10.2 for its proof.
Lemma B.2. Let k be positive integer. Then, we have for all k. 2 k1 that
Pspan (Q+ Qk.) ( (~ alk k2)
(pspan (Qk,) + 1),
(Nei- +
where f(x) == xe for all x > 0 and Nk.miu == min.,o (s for any k 2
Next, we proceed to bound the term T2.2 on the right-hand side of Eq. (30).
Using Lemma A.3 (5), we have
T2.2 E (V Q'), D, F(QU-TU)) D, Yx))
+
(2),H((( -((Qu))
LE LE g (Qk Q² Pepun (F(Qu: D,Ya) F(QQ-TT: D, Y2))
+ LE LE(p (Qk-Te - "²) Pspan (H(Qk)) H(Q (()))T)))
D I.) Elpappan ( (QK-Ty Q" Papan (Q - Qk
(Lemma A.I (I) and Lemma A.2 (1))
37

---

3L Dmin
Elpspan (Qhppan(u=u (Qu-Tk 22' Pspan (Qk - Qu-reel
where the last inequality follows from Dmnn E (0, 1). On the one hand, we have by Lemma B.2 and Proposition A. that
Pspan (Qx - Qk-Te) sf
Q:T
(Pspen (Qk- +
N k 1,min +
(:T
(bk-Ta +1)
N Na-T2- l,min +
CTT
<
(b: + 1).
N Nk-To 1,min +
On the other hand, we have
Popan Qk-TH Q*) S Pepan (Qk + Pspan
Popan((")) (Q") S bk-Ta + Pspan Pspan(Q") S by + Pepan Q*).
Together, they imply
3L
22 <
El Elpspan (Qk-TT - Q'))))ppan (Qx Qk-Tae)
Dmin
3b 1)b Pepan (Q"))
CTTK
Dmin
- + 1 +
3b.
Pspam (xpan(Q") + 1)2
aTKK
f
(32)
Dmin
N N + 1 + h
remains to bound the term (f (NTre//NNTTntttee
+ h)].
Using the definition of f(-) (ef. Lemma B.2), we have
QTK
IE
+
Lmmin
0.T
OTT
EE
exp
Na-rz 1 min + h
N N - m,m + 1
max 9,a
exp
N Nk- 11 188 h
N Ng- a) +1+
(f(x) = xe is an increasing function of on [0, x)).)
0TK
aTR
<
E
Nk-Ta (8,
+1+1
exp
N NK-r--10 1 +1
aTT
aT
+1 +1 exp
(Is Th
(k: (KT-T-- - -1) -1 + +1+1 h
5,a
where the last line follows from our notation = To proceed, for any 8 0 and (s, a), let
Es(s, a) (1Dx-n-i(s,d) D(s, a)l S 8D(s
and let E5 a) be the complement of the event Es(s, a). Note that on the event E8 a), we have
Dx-n--(s, 2 (1 a),
while on the event Eg a), we have D DR-m-118,00 2 0. Therefore, we obtain
TTK
E
f
1 + 11
aTK (k - Th. 11)Ds-a---100 1 exp ( (k- Th. 1)Dx (s..) +10 1
E
38

---

OTe (TI(11 + 1 (Eg((.a)))
Σ E
ath
11 1 exp
(k.
(k- 1) -1 (8,0) + 11
8,0
11](11 (s, +1+ exp
(k:
Th
QT4
1+1
exp
h+1
QTK
Σ 3,
(()
To proceed, let K' be such that l 2 2nd for all & 2 K", which is always possible since & = min Cp'-1 S ax} (log(())) Then, have
0.TR
Tk 1)(1 8)D(s, + (1+ h) (1- (k Th 1)(1))))111))) D +1+h
(s,
(1 8)D a)
k h
7k
2Tk
(1 (s a) k +
O
2Th
D k + h
which further implies
Nk Nk-ra- m,min + 1 )
OTT
20TTH |S|IA|
20Tk
(h: + 11) - -5)
exp
(1 - -8)Dmin
(k: + h1
QTk
ATK
Σ P(E
exp
h ++1
h+1
because f(x) xE is an increasing function of x on [0, o0).
To bound (sE a)), use the Markov chain concentration inequality stated in Lemma A.5. As long as
4C
8 2 D (1 p)(k Tk -1)
(33)
we have
P(EA(s,a)) =P - D(s,a) > dD(
$2exp(- (k- Tk D).
where Ome is constant depending on the mixing time of the Markov chain {Sp} induced by æ. It follows that
QTK
E
f
- + 1 111 h
20TH| |||A||
2ATT
exp
(k: + h)(1 - -D)Dmin
(k+ + +h((1 - D
+ h+1
20tk
exp
aTk
Σ
exp(- -Cmckk - Th - 1)62D(s,
h - 1
s,a
20TT|S||AA
20T
< (k: + h) 6)) Diin min
exp
+ h)(11
8)
20TH S||AA|
h exp(-cmel Cmc Th 1)8² D2 D2
exp
h+1
The next step is to choose 5 appropriately. Specifically, we want to choose such that
20TH 20tx/S||A|
QTk
exp(- (m (k Th 1)82 D2 2 (k - aT
exp
++
h+1
39

---

which is equivalent to
1
2(k + D
aTR
8
log
(34)
Cmc (k
7h
1) D min
h
In view of Eq. (33) on the lower bound of 6, let K" be such that the following inequality holds for all
k 2 K":
2(k + D
QT +
4C
log h +
Cmcl Tk 1) D min
h+1 1
D Diia p) 1.-7-1 Th 1)
Then, for all k: 2 K", choosing according to Eq. (34), we have
NR NK-Ta- 1,min + 1/) 11)
αTT
20Th |S||A|
20TH
(A: + 11 - -6)
exp
(k + 1i)(1 (1)1 - 8)Dmin
arT [
(1: + h)) Dinn
Since 7x min(t : Cpt-1 < ax3 = (llog(A)), there exists K
> such that the following
inequality holds for all k K"
20.TR |A
20Tk
30rk |||A
exp
(As + h1 8
(k + h)( 66)
(k: D
Therefore, when A: 2 K" we have
TTT
}
4atM|S|A4
4T agk
E
f
(35)
N -.min
(Ks + D)
Dmin
Finally, using the previous inequality in Eq. (32), we have for any k 2 K2 = max(K', K" K" that
T2,2 3l(bx + Pspan (Qp)
E
Dmnu
NK-Ta- 1,min + 1
3bg Pspan (Q") + 1)2 47 (S|AA)
<
Dmin
D Dmnn
12TH L|81/Abbt + Papan (Q*)
+ 1)
OKk
(36)
D2 Diin
B.6.3
Bounding the Term T2.3
Using Lemma A.3 (5), we have
T2,3 E[ - -") VM -Q)), F(Q,, D.Y:) H(Qu)))
< LIE (Q - Qk-re )esan (F(QR, D,Y,) - H(Q))))
On the one hand, we have by Lemma B.2 and Proposition A.1 that
Popan (2 - (
arK
(popun(Qk-n)) +
N Limin
+ 1 + h
ATT
(he-T + 1)
N Nk- L,min
+ 1 h
aTK
S N +
(by + 1).
On the other hand, we have by Lemma A.1 (2). Lemma A.2 (2). and Proposition A.1 that
Popum (F(Qk, D,Y H(Qx)) S Papan F(Qu, D, Yx)) + Pepan (H(Q&))
2 2p (Qx) + 1) + Pspun (Q+) +
D
40

---

3(bx + +1) Dmin
Together, they imply
2,3 S T.E. (alpaaa (Qk= - Qk Popanl (F(Qk. D, Vk) H(QQ)))
3b< + +1)2 E ANk-re-1,ma + 1
aTK
Dmnn
3L(b + Pspan (Q") + 1)2
aTK
E
h
Dmi
Recall that we have already shown in the previous section (cf. Eq. (35)) that
Na No 1,min + +1 b
OTT
4T ATA[S||AA
4k 2 K2. ak:
Dmin
Therefore, have for any k 2 K2 that
22,3 |/TAL| + Pspan (Q") + 1)²
D min
Or..
(37)
B.6.4 Combining Everything Together
Finally, using the bounds we obtained for the terms T2,1 (cf. Eq. (31) from Appendix B.6. T2, (cf. Eq. (36) from Appendix B.6.2), and T2,3 (cf. Eq. (37) from Appendix B.6.3) altogether in Eq. (30), we have for all & 2 K2 that
4T.bb + Popan (Q") + 1)2
12T [8] + Pspan +Q"++)²² ap.
+
T2 z
Dmnn
P
12TH S| + Pspan (Q") + 1)a OA
D2
28T L| |A (bx + (Q=) 1)2
D2
Ok-
The proof of Proposition A.2 complete.
B.7
Proof of Proposition A.3
Using Lemma A.3 (3) and (4), we have for any c E R that
MV Q"), F(Q&, Da, Yk) F(Qu, D2Y))
(VM - Q"),, F(Qu, Dr,
F(Qu. 0x) - ce)
Pm (Qk P')(V Pm (Qu - QQ", F(Qu, DR. Yx) F(Qu. D, D.) ce)
<Pm(Qu - Q') Ppm (Qx - 11 [(( Dz.Y,)) Y2) F(Qx, D, Yv) ce cel| m
By choosing
c a-argmin min CEERR
F(Qu. DR. Yv) - F(Qx. D.Y,) - dellmn
we have by Lemma A.3 (2) that
(V' - F(Q,, Dr, D(Q,
S Pm (Qx - Q'II (Q+ - Qm) (Ox, Dú, Yx) F(Q D,Yx))
Recall that we have shown in the proof of Lemma A.4 that Vpm (Qu 1m,, 1. Therefore, we have
( - F(Qx DR, Y2) F(Q,, D. D.Y))
Pm 5mm(Qu (Qu - Q2')P DR. Yx) F(Qu, D, Yx))
$ lm
(m PP)spa (F(Qk, DR, Y2) F(Qu, D. Y2))
(Lemma A.3 (3))
41

---

L
2e km P' (Qk Q-)+
28m Pspan (F(Qu, DE, Yv) P(QK, 2Y
(This follows from Cauchy Schwarz inequality, where c' > 0 can be arbitrary.)
d'
M(Qx - Q") +
28 Popan (F(Q.. DR. Vx.) - F(Qk, D, (,)),
dl
where the last line follows from M(Q) Pm (Q) /2 (ef. Lemma A.3 (2)). By choosing
1
c' = mm (1 /umm (mmm
we have from the previous inequality that (Qx - F(Qx,
F DR. - DY
d
S
M(Qu - -Q")+ + 28m Pspun ( D2, Yk) - F(QK, D. Yt))²
cllm
-(1 Bum Em
M(Qu Q0) Popant (F(2k. DR, Yk) - F(K,, D, Yx))² 2F m (1 B3mm km)
To proceed, observe that the vector F(Qk, Dx, Y2) F(Qu. D, Ya) has only one non-zero entry, i.c. the (Sks )-t one. Therefore, we have by the definition Pspan (+) that
Popan (1(Qk, DR. Yx) F(Qk, D,Yx))
1
R(Kk, Ag) + max Q+ Qx(S++1,d)) - Qx(Sk, A4) d'EA
-
An)
D(Sk, Ab)
1
2
$
(1 + 2pn Qx))²
(K Ak)
D(Sk, Ac)
(Definition of P-pan(-) and max [R(s, $
$ (11+ + bk))
DR AR)
D(Sk, A&)
where the last line follows from Proposition A.1.
Combining the previous two inequalities together, we have
T3 = E (VVM(QQ - -Q"), DR, Yu) F(Qu, D, Yx)i
Bum
im EMM(Q -Q') E |Pyan (F(Qu, DR. Yn) - F(Qu, D. 2
282 (1 (m)
(1 b1) P (D(SL.AA) D(SE,Ae)
Blm
P[M(Q=-Q2)
(38)
lm
262 9tmm/em
It remains to bound (1/D Av) 1/D(Sa, Az))%), which is highly nontrivial due to the following reasons: (1) for any fixed (8, a), De(s, a) depends on the entire history of the Markov chain induced by the behavior policy; (2) Da.(s, a) is correlated with (Sk, Ax); and (3) the appearance of random variables in the denominators of fractions destroys lincarity.
For any F < k - 1, we have
1
)
E
DR Av) D(S,, Av)
(Da(Se, Aw) - D(SE, Ax)
Du(Sk Ds Au)²
(Nu(SK, 4
hh ((S 2
E
(DR A&) (Na(S,. +h) h))
(N
(N 4 DS 2
E
((Sg, is visited at time step k)
(N (Sk, A +1+ (1 A
42

---

(N 1 o))²
((Se_A))=(..0))
E
1 ((E.0)))=(E.0))
8,0
(Nka (s,a) I (s, for any k2.)
(A B C2
I (((8) (N +1+ h)2
8,0
where
AR.F ==
- -
D(s, a)),
Bg.F N=-11 Nx-+-1(s..) - - a), which satisfies |xx S.,
CK.+ = (1 h)(1 D(s,a)) a)), which satisfies |Ck,*| S (1 + h).
follows that
27
E
Da(Sk Ax)
D(Sk, Ak)
(Ak, Bk,F Ck,+)² ((8h.AA)))11))) (Na- + 1+ +1+
E
a,a
3(4 72 + +
<
E
[((S).A))((sa))
+ 1
h)2 a)²
8,0
(a c)² 3(a² + + c2) for any c R.)
= +
>> E
A, - A (1
where the last line follows from the tower property of conditional expectations and the Markov property.
Observe that
P(s s, -
< PSS, = Av = a|S 4 D(s, + D(s,a)
= Σ P(Sk- = - 1 = s|Sk- = s')r((ls) ((s)=(a|s)) + D(s, a)
$ max P = -|Sk- = = - [(s) as
I max Σ (S s|SA = s') - n(s) + ((s
20p + a(s
where the last inequality follows from Assumption 3.1. By choosing
i minnt: : 2Cp' < Dminn
have
P(Sx = 8, As = - A S 2D(x,a)
(39)
follows that
1
27
E
(a As)
D(Sk, Ax)
3(A6 + 72 (h+ 1)3)
2
Ds, a)E
(Na-+-1 ()+
43

---

3(k -- - -(.
2 Σ D(s a)E
((k ( -11
8,0
3(F² + (h + 1)
+ 2 Σ D(s a)
[(k- 1)Db-=-1(5,0)) + D
To proceed, for any d (0, 1) and (s, a), let Es(s, = (1D a) D(s, a)t I 6D a)) and let Ej a) be the complement of event Es(s, a). Note that on the event Es(s, a). we have
6) (s, S D S (1 + (s,
while on the event (s a). we trivially have D a) 2 0. It follows that
27
1
(S Ax)
D(Sk, An)
33k - - ())2(D)= - (ss, a)) Es(s.a) + Es(e,)))
2
D(s,a)E
- (3) + (ss,,
8,0
3(7² (h+ 1)²) ( + Es(s,a)=)
+ 2
a(s,
[(k 7 - 1)D
+1+ - 1)3
8,0
3(k - 7 1 1)2
2 Σ
((k- 7- -- 8) + +1+ h1+ E (8) a)
3(k - - ((E
+ 2
(1 (1+ 11+))D(s,0)
8,0
3(7² + (h + 1)3)
22
((k - 7 1)(1 (s) + 1 h))
3(7² + (h + 1)
+ 2
(1+ (++))2((ssa) (())(())))
8,0
3(k 7 1)2 ((k - 7 1)(1 8) 8, a) + +1+ ()((,) (D)= a)s
3(7² + (h+
+2
((k - - 1)(1-8)Dss,0 ())
+ 3(kk - - - + h)2 ((E)(s,
h1+
8,0
remains to bound the terms (((D)==-($s,)) D(s, a)) and P(E a)). To bound B((Dx=f-1(s, a) - ((s,a))² we use the following lemma, which is a mean-square bound for functions of finite, irreducible, and aperiodic Markov chains. The proof of Lemma B.3 is provided in Appendix 101.
Lemma B.3. Under Assumption 3.1, the following inequality holds for all k 2 14C/((1 pmin]:
10C a)
[(Dx(s. D)s (1 p)k
For simplicity of notation, denote Cme = C/(1- - p). Apply Lemma B.3, we have when 2 140me/ Dmin that
27
60Cmo (k: - F -1
Du(Su, Ax)
D(Sr, Ax)
((k - 1)(11 a))
8,0
((k: 7 - h))
44

---

6((k 6((----)++7+
(1+ (1++)3) (())(,,
(1+1)DD(s,a)
3,0
To proceed, observe that
60Cme (k- 1)
7-11 60C (k-
((k - 1)(1 as) + h)2
((k: - 1 - + (1 + h)) o))(s,
(k: + h - - -)
and
6(72 + (h + 1)
((k 9 - 1 ()) 0) + 1+ +1+h)DD(ss))
6(72 + (h+
((k - 1 -
6(F + 1)²)
(A: + h 61 - (s)
Therefore, we have
( (DAlS) As) D(SE, Ax)
27
60C 90Cme|S||AA(( - -- 6]S]||](F² + (h 1)2)
De(Sk,
S (A: + F)2(1 - -8)2 min
(I+ - 10+th- - 8)2 min
G]S]|A[((K - 1)² + (1+ h)3 (s) (1+ 1)) min
To bound P(E a)), use the Markov chain concentration inequality stated in Lemma A.5, which implies
((E)(s,a)) =P ((s -Dss,) >)D(s,)) 22 Cmo - 7 1
D(s)))(( a)))
for all 6 2 4C/[Dmiin p)(k 1)]. follows that
1
27
E
DR(Sk, A&) DS5t AA)
600me ||||A| (I: 5 1)
(]S]|A|(F + (h (h++)3))
<
+ (k+ h - 7)2 8)2 min
(k + h 7)2(1 1 -2)= min
12|S)|A|((K- - - +2 (1+1)3)
exp(-cmo(k - - 1 min).
(1+ h)2 Diin
Let K" be such that the following inequality holds for all k: 2 K":
log 12(R+AX(K- F 112 (14)))
4C
(1+h)²
D (1 p) 7 1) S $1
Cme - 7 1)D2 p
Then, for any K' choose
12(k + ()(k - - 1)2 +1+++++++97 (1))))))
8 = V Cmolk 1) log
(1 h)²
we have
12 - 125-1) +2 (1 h)2)
|
exp( ssp(-cmolk: - D2 min
(1 + h)2
(I: + D
It follows that
27
600 60 --
||S]|A|( (h 1)2)
(Da(St Av) D(St,AN
<
(k: + h F) - 8)2D2 min
- D) Di
45

---

|S||A]
(k + D
Let K" be such that the following inequalities hold for all k: 2 K"
(k -
61
+ (h + 1)
(k+ 7)2(1 8)2 S
60(k + h))
(k: 1++h- - 8)2 Dunnn
6(k + h)
Then, we have for all 2 K" that
E (Da(ShnAa) - ((S,,A)) )
)
61 ml ||||A|
|S||A|
|S||A|]
+
(k: + h) D min
(K: + h)
(I: + h) h)
63Cmel |
(k: + 1 min
where the last line follows from Cme C/(1 p) 2 Finally, combining the previous inequality with Eq. (38), we have for all & 2 K3 == max(14444))m (4c0m//m////// Dmins "YKK" that
27 (1+bb)22B Du(Sk.Ae) D(SkiAe)
1
8
T3
E [M Q²)1+ +
lm
28 (1 Blmm/mm)
Blm
E [[ Q')1 32C mc |||A (1 616²
lm
(1, (1 33m mm )a min
Ckk
Bumm
E [M Q')1+ + 32C mel (SI
Pepaa (Q") + 1)²
lm
l7. B2mm / D min
Oak
32C S|| (bx + Pspan (Q") ) + 1)2
Φ1 E (Q
+*)++
(40)
L cb (1 p)a min
where the last line follows from our definition Φ1 = -3mm///
B.8 Proof of Lemma A.6
Since the vector F(Qu, De, Yx) - Qx has only one non-zero entry, i.e., the (Sk, Ax)-th one, we have by the definition of Pspan| (.) that
Pspan ((Qur Da, Yk) -2x)²
1
2
R(Sk, A&) + max Qu Qe( (S&,s, 2 d'A
4
Du A&)
1
+ 2Pspan (Qx))
4
DR Ax)
1
(1 + 20h 2
(Proposition A.
4
DR Ax)
2
$ (1 (1--by b2)
(sk,
Taking expectations on both sides, we obtain
T4 S (1+
(41)
(Sk, Ax)2
It remains to bound E[1/Da (St, 2.) Observe that for any F S A 1, we have
(k: + h2)2
(Da(s (N)((,))))) h// + h))
N (Sk: A&) + 1))3
(k + h122
=E
(Ng (St, Ax) + +1+
(The pair (Sk, Ax) is visited at time step k.)
46

---

((x.)) (k: + 1)2
(N (8,0) + h))2
6,0
1 ((s,a) (S,, (S.,A)) (A: h)2
E
(N (5, a) + +1+hy
8;0
(Nii (8, S Nag (8, for any kı S k2)
(k: + h)²
E
P(S =, As = 1 (N h)2
8,0
where the last line follows from the tower property of conditional expectations and the Markov property.
Recall that we have shown in Eq. (39) that, when choosing F = min(l: Cpt < Dmin we have
P (Sx = As = a|Sk- - - (s.
It follows that
(k+ + h)2
E
S
Σ 2s(
(42)
(Sk Ax
(N a) + h12
8,0
To proceed and bound E [(k + h1) ( (s, Ea a) = (
h) given ō (0, 1), for any (s,a), let (s,, a) - (s))a))
and let Ej(s, a) be the complement of event (s a). Note that on the event Es a), we have I (ss,a) < (D( a), which implies
D a) 2 (1 (1-8))(ssa))
while on the event (s a), we have the trivial bound DR- 1s, a) 2 0. Therefore, we obtain
(A: + h)²
(k + h)2
(k 7 - 1)²
E
(N----1
1+ h)
(k 7 1)2
+ h)²
(k h)2
(k - 7 1)2
- (Dx- 0) + +1 + - 1))2
(k + h)2
1 (Fg().)) + +F(((()))
(k - 7 1)
(Dx= (1 h)/ - 1))2
(k + h)²
1
(k - 7 - 1)2 ((1 8) 0) (1 h)/(k - -
(k h)2
11 ((E)(s
(k: + h)2
1
(I: + h)2
< (k - 1)2 (1- 8)2 (h + 1)2 ((E)(s,)))
To bound (sE5(s, a)), use the Markov chain concentration inequality stated in Lemma A.5, which implies
D(s, ((Eg(s, =P - > >)(ssa))
S cxp CCm 7 - 1)52 a)),
for any 8 2 4C/|D DC/[Dminl) min (p) - 1)). Combining the previous two inequalities, we have
(k+ hh)
(k: + h)2
E
< (k: - 7 - (11-8)2(ssa)))
(Ng---15,aa)
h)2
+ 2(k: + h)²
exp(
- - ()),))((ssa))))
-
(h 1)3
47

---

Let K' be such that the following inequality holds for all l. 2 K":
4C
log|2(k: - h)) (h
Cmo - + 1)
S max
Diin (1 pk -
Then, for any K', choosing
1og + ())
8 max 3,0
Gme - 1))(
we have
2(k: + ht2
exp(-cmmet - s a(s,a)²
(h - 1)2
follows that
(k: + h22
S (k+ + h12
1
E
(N (8, +1
1 1) (1 (1- 8)2 (8, a)²
2(k +1
+
exp(-cmoll - - D(s))))())
(h + 1)2
(k + h)2
(k: 7 1) (1 D) D)s
Let K" be such that the following inequality holds for all k 2 K":
(k + h)2 1
(A: - 1 1)2 (1 - 8)2 2.
Then, for any K", we have
(k h)2
< 2
1
3
E
S
(N+-F-18,,)) (8, +
h)
D(s a)²
D(s a)²
a)s,a)2
Using the previous inequality in Eq. (42), we have
6
6|
E
(S Ax
D(s.a
D
8,0
Finally, using the previous inequality in Eq. (41), obtain for any k 2 K4 max(K', R") that
6]5]|A|[1 + bb)²
G|S]|A[(bb + Pspan (Q'
Ta S
Dmnn
Dmin
B.9 Proof of Proposition A.4
Using the upper bounds we obtained for the terms Ti (cf. Lemma A.4), T2 (cf. Proposition A.2), T3 (cf. Proposition A.3), and T4 (cf. Lemma A.6), in Eq. (16), we obtain for any k 2 K max(K2, K3, K4) that
Lo T3
E[M(Q Q")) <E(M(Qr QQ)) +a))) (T: + +T2 + TT) +
2
Bum
1
axk
E [M - QQ')]
lm
35|S||AA|
C
Bum (mm) p)a L. (bi + Pspan (Q') + 1)²ax
D2 D
P2
)1 E [M(Qr Q')) + 35ch2TT (be + Papaa (Q") ) a
where
S|A
22, p) + 1.)
C
D2
min
48

---

B.10
Proofs of Auxiliary Lemmas
B.10.1
Proof of Lemma B.1
To show the desired inequality, it suffices prove that
max 1x-1(s, I max Qx(s, + (x Ak). 8;6
(43)
s,a
min Q 2 min (x(s, - - As). 8,0
(44)
8,0
The result then follows from the definition of the span seminorm:
1
Popan (Q++1)
max 1 (8. a) min Q6+1(188))
2
S max Qx -min (x(8, + (Sk As)
2
Pspan (Qu) + az (Sk. As).
In the following, we will prove Eq. (43); the proof Eq. (44) follows from an identical argument. In view of Algorithm 1, when (s. a) * (Sk: A&), we have
Qx+1(8, a) = Qx(x, a) + ck I max (x( + (x Ag).
5,a
When (s, a) (Sk, At), since maxs,a R() S 1, we have
Qu+1(s,)) = Qu (8, a) + (Sx, As) R(Sa, An) + max Qu( Qu(Sku As)) a'EA
(1 (St, At)) (St, A&) + (Sk, Ax) R((s,a) max QK+ (5k-1,
d'EA
S (1 arl (Sx; Ax)) max Qu Qu d') + (Sk: (1+
max Qu(d + cx
s'aa'
s'
max (s's a') + an Sk. Ax). s/.a'
Combining both cases, obtain
max Q++1 (8, S max Qu a) + (S, 8,0
which establishes Eq. (43).
B.10.2 Proof of Lemma B.2
Using the definition of Pepun( (.), we have by Algorithm that
Pspan Qk+1) 1) Pspan ( (2x) S Pspan (K++1
Qu)
an (Sk, Av)
R(Sk, Ak) + max a'EA
Ax)
2
0ik (Sk, AR)
(R((S)) An)) + max Q4 (ux+111,))) - Qu a'EA
2
an (Sk, An)
[R(SE, Ac) + max Qu ,a') s'.a'
min Qu ( (5', a')
2
s'a"
On (Sk, Ar)
(1 + Pqpan (+))
2
$ Lar(St, Ak) (Pegan (Q+) 1).
(45)
Rearranging terms, obtain Pepan (Q+1)) + 1 < (1 + (Sr, As)) (Pepan (Qx) + 1).
49

---

Therefore, we have for all h 2 h1 that
k-1
Pspan (Qx) ~
II
(1+
aa(s, (Pspen(Qk.)) + 1)
j=h
k-1
1 Ny(Sj. Aÿ) + th) (Popan (oppa(Qks))) -1
j=k1
k-1
a [1 N 15.1 A,) + ++ (Pugun (Qk,) + 1)
j=h
A5) is visited in the j-th iteration)
1 - + 1 + h
(Pspan (Qk,) 1)
j=h
ark:: - ki)
S exp
Nk 11,iu 11+11 1+hh (Pspum (Qkz) + 1)
where the last line follows from
(1+x) S 6x for all IR. Rearranging terms, we have
a(k kn)
Pupan (Qx:) + exp
(Pspan (Qka) + 1), 44 hi.
-1,ii + 1 h
Using the previous inequality in Eq. (45), we have Pspan (Q++1 - Qx) S ar (Sk, Ax) (Pspan (ux) + 1)
S (N 1,min + + h1)
a
exp
N N1 + + 1
a(k - k1) (11)
(Dspan (Qkz) + 1).
By telescoping, we have for any 2 1: that
Pspan (Q -in) S
Popan (Q++1 - Qi)
a
exp
ali - k1)
(Dspun (2x, + 1)
Nki I,min + 1 11 h
- 1 -
k=
alk: - h:1)
a(k - k1)
NR. -1,in + +1+ h
exp
Nk. 1,min + 11+ + h
(Pepun (Qix) 1)
alk - kk)
=ʃ N1,in, +
(Pipan (Qk,) + 1),
where the last line follows from the definition of f(.).
B.10.3 Proof of Lemma B.3
For simplicity of notation, let (s, [((S..A))((s))) for all 1. By definition of D)(s,a). we have
- E (Dx - ((s, a)) = (D2.s.))BBD(es))))EE(GG
D a))
E [Dx - E(Da(s, (B[Dn(s, ((s a))² (46)
D(s
Variance
hias
We first bound the bias term. Observe that
E[X,(s, - D(s.a)) 2
Σ E (E[X,(s,,)) a)] D(s,a)))
1 5 42 Σ
bias?
k
50

---

Moreover, under Assumption 3.1, we have
[E|X;(s a)] D(s, a)l
= -P((S) s, A, = alSi) - (())
= 1px - =(S1) (as)\
x max Σ
(r = =|S1 = - -
< 200p-
(47)
It follows that
2
Σ 20p-11
4C2
bias
S
(48)
k2
h2 p)
Next, we turn to the variance term on the right-hand side of Eq (46). Observe that
1
Variance
Var
Σ Xi(0, a)
1-2
Var Var(X:((,aa)
2
Σ
Co)(X((s.0),,x((..a))
(49)
On the one hand, we have
Var (ar(X((s,a)) = ([, as)))²
E[),(s,a)] - (E(X)(s,a)))
as)
[[(X - D(s, a) + a)
2Cp +(ssa)).
(50)
where the last line follows from Eq. (47). On the other hand, we have Cov(X((s.a.
(s .)]
= =P((,(s,a) = 1, (s, = =P(X,(s,a) = ()(P(X((s.a) 1|,, =1) -IX_P(X 1)) SP(X,(s,a) = 1)(P(X,(s,0)) 1|x,(s, = - P(X,(5, -I)
(()((xs.)==))((XX 1)
Using the same analysis as in Eq. (47), we obtain
F(X((s,))=1) (s, a) 1) - D(s, ((s s 20p'' - D(s,a)
and
PP(X((s (|x, = P(X,(s,,) = =)] < [P( = =2Cp/-i1+2Cpp <4Cp-111
= - ((s, (((s P =1)
Combining the previous three inequalities together, we have
Cov(Xi(s, X, a)) <Cp'" + D(s = =422 + D(s, a)4Cp i-1
Using the previous inequality and Eq. (50) together in Eq. (49), we have
2
Variance
Var (a, a)) +
1sisjsk
2C 2Cp-11 + D(s, a)
2
24 + DDl.-=+DDs.
j=it1
51

---

2C
D(s,a) a)
40
8C'
+
D(s,a) a)
12 - p)
12 (1 - p)3
k(1 p)
10C
9CD(ss, a)
(1 - p)a
k(1 pp)
where the last line follows from C 2 and p (0,
Finally, using the previous inequality and Eq. (48) together Eq. (46), we obtain
E (Da(s,a) ((s, a)} variance bias
14C
9CD(ssa) a)
12(1 - /)2
k(1 p)
10CD(s,
(1-P))
where the last inequality follows from k Z 14C/((1-p) Dmiul
C Proofs of All Technical Results in Sections 2 and 4
C.1 Proof of Lemma 2.1
We first verify that when (max; H; + miny 22)/2, we have ||2 - cello (max; min, x2)/22 On the one hand, for any E [1,2, .......,. ,d]. ,d... we have
|mmax 24 of
min x. c) max; Z; miin xj
|. cl S max
which implies
|| cellox max; T2 miny 2.j
On the other hand, letting i = arg max, e .d) Ts, we have
||x cello0 2 |2: - cl max; 2; min, Tj
2
Together, they imply
|| - oello0 max; T; min; Dz
Pspan (2r).
2
To complete the proof, it remains to show that for any d' * c, have ||2 d'eloo 1|2 celloo. Assume without loss of generality that c' < c = (max, o + min, /2 Then, we have
||x dellox 2 |zi, - d'el
= max - d'
max; Vú + miny 2y
max
max; I;- minj
2
C.2 Proof of Lemma 2.2
For simplicity of notation, denote
C = (Q) H(Q) - -Q= =r-ree and 2, = =Q= Popan (H(Q) Q) = -}.
We will show that Q C Q Q2 C Q. which would imply Q1 Q2.
For any Q E Q. there exists c E R such that Q = Q" + ce. Since
H(Q) Q H(Q" cε) Q' -c H(Q") - Q" rre,
52

---

we have Q E Q1. implying Q _ 21.
For any 11, since ((Q)
r'ee, have (ppa(H((Q) Q) Pspan (r- e) 0. As result,
we have Q E 22 implying Q C Q2
Finally, show that 22 S Q. it is enough to show that for any Q E Q2. we must have Q Q" ker (er(Pspo)). To see this, since Q E 22. there exists c E such that H(Q) Q = ce. It follows that
Popan (Q Q") Papan (H(Q)
H(Q") rree
Papan (H(Q) - H(()))
Papan QQ-Q")
where the last line follows from Assumption 2.1. Therefore, we must have Popun (Q - Q") = 0.
implying Q Q" ker(Pspan)-
C.3 Proof of Lemma 4.1
Given any Q1 Q2 E [ISIIAI, for simplicity of notation, denote
M max 9.8
())(()))))( [H(Q=)](s,a))
min((H((:))(ssa)) (M((:))sss..
= max (Qi - a)), 8,0
= (Q)(((()))))((s..))) 8,a
To show the seminorm contraction property of the asynchronous Bellman operator H((-), first show that M < L and m 2 f. By definition of the Bellman operator H((-, we have
(max Q1 d') max Q2(5',a") Σ p(8(ss,
M = max 8,0
a"
#ESS
max
Σ
p(s'|s ((s'|ss00 (s max(Qi .') Q2(s',a'))
8,0
EESS
< max
- -2(,s)))
L.
Similarly, we also have
m
min s,a
Σ p(s'|ss, [(s'|ssa))
max Q2(5', aa)) (max (i(x a"
s'ES
min 8,0
Σ p(s' s min(()))) - (2('',')))
s'ES
(2((5))
Q2(8,a))
=6.
Now that we have established M < and m 2 e, to proceed with the proof, using the definition of H(-), we have
Pspam (F((Q)) F((Q2))
PPspan (1- Q2) D(H(()) H(Q2)))
max [(1 D(s - (2(x, o- -
min [[1 ((s,,)))(1((s,..) |00p::/0000000000000000000000000 (H()))((((____))))))){)))))))))) [H(Q:)((s 8.a
On the one hand, we have
max als. (000000000000000o0000000///////0 (+()2)((s.))
< max [[1 - D(s.a)))
5,
max [L - D(s, (L--
53

---

=L- min (L -
where the last inequality follows from M S L.
On the other hand, we have
min [[1 D(s, -2(l))) + D(s.))( [H((2)](s,
2 min [[1 D(s, a)) a(s.)mm)
8,
-min [e - D(8, ((x,a)(e-m)) m)]
=l D min (e m).
where the last inequality follows from 2 L. Together, we obtain
Pspan (((Q))-F((Qa) - 52(1: Dmin (L M))
2 Dmii m))
1 (1 - Dmin)(L E) D Duni (M m).
2
Since H((-) is a contraction mapping with respect to Pspan()) (cf. Assumption 2.1), we have
Pspan (H((1)) H((2)) = M - m
S 8pspan (Q1 - -Q2) = 3(L - E)
2
It follows that
Pepan (H(Q1)) H(Q2)) < (1 - Dminn -L) + Dmmin (M ml
2
<
(1 - Duinn (L - +))+ + DL
2
1
2 [1 Dminn (1 (1-BB)) B)) - 8)
= (1 - Dmin - (1 (Q1 - Q2).
Finally, since Diin E (0, 1) under Assumption 3.1, which implies 3 = (1 Dmin (1 9)) g (0, 1), the operator H()) is contraction mapping with respect to Pipan with contraction factor 3.
C.4 Proof of Proposition 4.1
Using the definition of H((-), if D T/(()| have
Pupan (f((Q) Q) =
Pspan (D(H(()) - Q)) = 0,
S S Papan (H( - Q) = 0,
Pepan (H(Q) - Q) = 0,
which implies
{Q] Papan (H((Q) Q) 0) ( 11ppa (H Q) = 0}.
D # I/((ST|A)), let Q Q (Q' + cele R}- 1Q0pp (H((Q) Q) 0} be arbitrary. Then, we have
Pspan (F((Q) - Q2) = Papan D(H(())-0
Pspam (rree)
|r"
max D(s, a) 2,0
min D(s
> 0.
54

---

Since Pspan (PL(Q) - Q) # 0 for any Q in the set of solutions Q of the original Bellman equation (2),
we must have
Pspan (H()) - Q) - - (QlPa - QQ = 0} =
To establish the convergence rate of Eppspan (Qx Q* )², we will apply [24, Theorem 4.1]. For the completeness of this work, we first restate [24, Theorem 4.1] for the special case of span seminorm contractive SA in the following.
Theorem C.1 (Theorem 4.1 from [24]). Consider a Markovian SA of the form
Ja+1 = I& + (g
SotksYY YR)
-xk), Vk 2 1,
where {Yx} is a stochastic process taking values in a finite set y and T Rd x Rd is an operator. Suppose that the following assumptions are satisfied:
(1) The stochastic process {Yx} } is uniformly ergodic Markov chain with stationary distribution v.
(2) The operator T Rd - R defined as (xx) [T } is a contraction mapping with respect to Pspan (-), with contraction factor 3' (0,
(3) The operator T-)) satisfies Pspau (T v) (x v)) S (x -x) and Pspon! (T ((,2)) s Bı for any Tı, T2 Ba and y, where A1, B1 > 0 are constants.
Then, when using or = ax/(k:+ + h)) with appropriately chosen and h, we have E. Elpopnn (3 x:" x=)) z (1/kk), where x² is a particular solution to Pspan (T(x) x) = 0, which is guaranteed to exist due the seminorm fixed-point theorem [24, Theorem 2.
To apply Theorem C. to Q-learning with universal stepsizes as described in Eq. (3), we only need to verify Assumption (3) because Assumption (1) holds under Assumption 3.1 and Assumption (2) has been verified in Lemma 4.1.
Using the definition of G(-), for any Q1 Q2 E IR SI Al and = (so, ao. s1) E y, observe that the vector G)) - G(Q2. y) and the vector Q1 - Q2 differ by exactly one entry, namely the (su, -th one. Therefore, let Qui E RIS|IAI be defined as
Quat(so an) = [G(Q1, (su: an) - [G(Q,, 8) au) - (Q1(s0. au) Q2(s0 an)) max Q (81, a') - max Q2 a') - (Q (so, an) - Q2(00, an));
and Qatr(s, a) 0 for any (s,a) a) + (80, an). Then, we have
G(Q v) - G(Q2, 9) = Q Q2 + Qaif-
By the triangle incquality, we have
Pspan (GQ1, G((2,, v)) S Papan (Q: Q2) + Pspan (apan(Qait)) (Qait).
(51)
To bound Pspan (air)), since Qairr has only one non-zero entry, we have by the definition of Pspan (.) that
Pspan (Qair
max Q1(81, a') max Q2(81, a') - (Q1 (8o: 0n) (2 ao))
2 a'
To further bound the absolute value on the right-hand side the previous inequality, observe that on the one hand, we have
max Q1(51, max Q2(31, (Q) ao) - (2 ao))
max(Qi a') O2(s',d')) (Qi oo) Q2(30, ao)) 5'.0'
min (a' - -Qz(s',d)) s' (Q 12(5',
2p (Q1 - Q2).
On the other hand, since
max Q1 (s), max Q2(81, = max Qi(si,a') Q2(81,)) a'
(Denote @ E arg max, Q2(81,a'))
55

---

2 - Q2(s,,a)
M min Q2(s', -))(s,)))
we have
max Qi(s),a)) max (2x1Q (Q) ao) - Q2(5).
min(Q1(s',a)) Q2(s', (Qi ao) Q2(su, ao)) 8'aa'
(in((1 d') Q2(s',a')) max Q2(s',00 ,d))
d'aa
Pponn (Q1 Q2)
follows that
1
Pspan Qdift)
max (1(,) max max " (Qi(so, ao)
Q2(s0,
2 2
S Pspan (Q1 - Q2).
Combining the previous inequality with Eq. (51), we obtain
Popan (G(Q1, G(Q2, w)) S PPspun (Q1 - Q2).
To show that Papan (G(O, y)) is uniformly bounded for all D, observe that G(O, y) has only one non-zero entry, i.c., the (sp, 4-)-th one, which equal R(so. an). Therefore, using the definition of G(-), we have
max (=
Pepan (G(O, v)) = max R an) S 2
C.5 Proof of Lemma 4.2
Using the definition of H-)-) (ef. Eq. (5)), since Pspan -H(Q")-0 0. there must exist some E R such that D(H(Q") - Q*) cre, which implies
H((²) Q" Dc
On the other hand, we know that
H(Q') - -2¹ = reee.
Subtracting the two equations yields
Q' H(Q") - - -
Taking the span seminorm on both sides and using Assumption 2.1, we have
Pspan (2" -Q") |ca Pspan D (D-le)
B
56


Reviews:
[{"review_id": "IqSR2XqDwQ", "reviewer": "Reviewer_i7gX", "summary": "This paper aims to solve the infinite-horizon, undiscounted MDP problem by proposing a provably optimal asynchronous updating Q-learning algorithm. The algorithm adapts the RVI Q-learning [Abounadi et al., 2001] by using an adaptive stepsize that is related to the history trajectory per state-action pair. In measuring the optimality of a policy in the infinite-horizon, undiscounted MDP environment, the authors reformulate the Bellman equation by adapting it to the Seminorm Bellman equation with a seminorm $p_{\\text{span}}$. Under the new proposed seminorm, the optimality Q-function $Q^\\star$ should satisfy the equation $p_{\\text{span}}(\\mathcal{H}(Q^\\star) - Q^\\star) = 0$, where $\\mathcal{H}(\\cdot)$ is a Bellman operator. Solving this equation is equivalent to finding a fixed point/set of fixed points in the space measured by $p_{\\text{span}}$.\nThe adaptive stepsize breaks the Markovian property of the trajectories and makes the standard analysis technique inapplicable.\nThe authors overcome this difficulty and derive the theoretical regret guarantee in the finite-time regime.\nThe authors also present the necessity of introducing an adaptive stepsize by showing that using a universal stepsize will lead the outcome to converge to the wrong target.", "questions": "1. 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_{\\text{span}}$. How to interpret the condition to ensure the two solution sets are identical: $D(s, a) = I/(|\\mathcal{S}| |\\mathcal{A} |)$? $D$ is supposed to be a diagonal matrix with diagonal entries $\\{ \\mu(s)\\pi(a \\mid s) \\}_{(s, a) \\in \\mathcal{S} \\times \\mathcal{A}}$, does that mean that policy $\\pi$ is a deterministic policy?\n\n2. 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?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written with rigorous theory analysis and clear notations.\n\n2. This is the first work to analyze an asynchronous updating algorithm in the setting of an average reward infinite-horizon undiscounted MDP environment.\nThe introduction of adaptive stepsizes breaks the Markovian property of the trajectories, making the algorithm a non-Markovian stochastic approximation scheme. The authors propose innovative techniques to address this challenge by incorporating the empirical frequencies of state-action pairs in the trajectories of the stochastic process. \n\n3. For completeness, the authors justify the necessity of the adaptive stepsize by showing that using a universal stepsize like harmonic stepsize $\\alpha_k \\coloneqq \\alpha / (k + h)$.\n\nWeakness:\n\n1. The analysis relies on Assumption 2.1, which states that the Bellman operator is a $\\beta$-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\n\n2. 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.", "was_revised": true, "final_justification": "The author has resolved my questions during the rebuttal. I will keep my score and support this paper.", "rebuttal": "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.\n\n>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.\n\n**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.\n\n>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.\n\n**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$.\n\nIn the next version of this work, we will add numerical simulations and discuss the choice of $h$ in that context.\n\n>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?\n\n**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$. \n\nHowever, 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.\n\n>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?\n\n**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$.\n\nSince 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  \n\n$\\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$,  \n\nwhere $e$ is the all-ones vector. On the other hand, we know that  \n\n$\\mathcal{H}(Q^\\star) - Q^\\star = r^\\star e$.\n\nTaking the difference of the above two equations, we obtain  \n\n$\\bar{Q}^\\star - Q^\\star = \\mathcal{H}(\\bar{Q}^\\star) - \\mathcal{H}(Q^\\star) + r^\\star e - c D^{-1} e$.\n\nTaking 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  \n\n$p_{span}(\\bar{Q}^\\star - Q^\\star) \\leq \\frac{|c| \\cdot p_{span}(D^{-1} e)}{1 - \\beta}$.\n\nTo 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.\n\nAs 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)."}, {"review_id": "PRRHDKB5Ye", "reviewer": "Reviewer_vKC5", "summary": "The main theorem is the first to establish nonasymptotic convergence guarantees for the classical asynchronous Q-learning algorithm for average-reward RL. The algorithm deviates from usual Q-learning by using adaptive stepsizes, and the paper also presents formal arguments for why they are necessary for the process to converge to the correct limit, as well as demonstrating that they can be understood via a connection to importance sampling. Their use introduces the main technical challenge of the paper (by causing the underlying stochastic process to be non-Markovian).", "questions": "What can be said 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(s,a) = c/k $)?\n\nCould the authors provide any commentary on aspects of the proof of the main theorem which are suboptimal (in terms of leading to a suboptimal sample complexity)? \n\nCould the theorem statement be refined to provide a guarantee which 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)$ ?)", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is very well-written and clear. The main result is a fundamental contribution with great significance, and also is the consequence of overcoming multiple conceptual and technical obstacles. At a high level, I think it is great that the paper attempts to study whether adaptive stepsizes are necessary, and I imagine that the related result and discussion may have even greater significance than the convergence analysis of Theorem 3.1. The connection to importance sampling is similarly an interesting and significant contribution. I also appreciate the comparison with discounted Q-learning.\n\nWeaknesses: \nAssumption 2.1 is a strong assumption which is not satisfied in many of the more general classes of MDPs and is crucial to the convergence guarantees of the algorithm.\n\nWhile Proposition 4.1 states that the fixed points of the synchronous and asynchronous fixed-point equations are disjoint, to completely justify the necessity of adaptive stepsizes it seems like we would instead need to understand the distance between the sets of fixed points? In principle if the distance is small (relative to the number of iterations $ k $) then it seems this would not be a fatal issue.\n\n(As discussed after Corollary 3.1.1) the sample complexity analysis appears suboptimal. Specifically, I do not view it as a weakness that the upper bound does not match the minimax lower bound (for a synchronous setting), since this would not be expected, both due to the more difficult setting and the lack of variance-reducing techniques. It is very worthwhile to understand the complexity of Q-learning despite its algorithmic suboptimality. However, it additionally seems that the analysis is very likely suboptimal. It might be interesting to have additional discussion of suboptimal aspects of the proof structure.\n\nWhile the algorithm accepts an arbitrary initialization $ Q_1$, the guarantees do not seem to depend on the distance between $ Q_1$ and some fixed point.", "was_revised": true, "final_justification": "Overall the paper has many strengths (see above) and makes an important contribution to a fundamental problem. The rebuttal also satisfactorily addresses my main outstanding questions regarding Proposition 4.1.", "rebuttal": "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.\n\n>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.\n\n**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.\n\n> 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$)?\n\n**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$.\n\nSince 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  \n\n$\\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$,  \n\nwhere $e$ is the all-ones vector. On the other hand, we know that  \n\n$\\mathcal{H}(Q^\\star) - Q^\\star = r^\\star e$.\n\nTaking the difference of the above two equations, we obtain  \n\n$\\bar{Q}^\\star - Q^\\star = \\mathcal{H}(\\bar{Q}^\\star) - \\mathcal{H}(Q^\\star) + r^\\star e - c D^{-1} e$.\n\nTaking 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  \n\n$p_{span}(\\bar{Q}^\\star - Q^\\star) \\leq \\frac{|c| \\cdot p_{span}(D^{-1} e)}{1 - \\beta}$.\n\nTo 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.\n\nAs 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).\n\n>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)?\n\n**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.\n\n*The almost sure bound on $p_{span}(Q_k):$*\nAs 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})$.\n\nTo 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.\n\nUnfortunately, 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.\n\n*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.\n\n>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)$?)\n\n**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\n\n$p_{span}(Q_k - Q^\\star)\\leq p_{span}(Q_k) + p_{span}( Q^\\star )\\leq b_k+p_{span}(Q^\\star)=m_k$,\n\nwhere $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.\n\nAs 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:\n\n$p_{span}(Q_K - Q^\\star) \\leq p_{span}(Q_K) + p_{span}(Q^\\star) \\leq b_K + p_{span}(Q^\\star) = m_K$,\n\nwhich 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.\n\nTo 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  \n\n$\n\\mathcal{O}(|\\mathcal{S}|^3 |\\mathcal{A}|^3 D_{min}^{-2} \\epsilon^{-2} (1 - \\beta)^{-3} p_{span}(Q^*)^2).\n$\n\nSee also the proof of Corollary 3.1.1 in Appendix B.5."}, {"review_id": "gW9Iv4MYjQ", "reviewer": "Reviewer_pbot", "summary": "In this paper, the authors propose a variant of the Average-Reward Q-learning algorithm with an adaptive step-size based on the counters of each state-action pair. They provide a finite-time analysis for the last-iterate convergence in the span seminorm, based on a single trajectory of Markovian samples. Additionally, they demonstrate that standard Q-learning with a diminishing step-size might fail to converge to the same optimum $Q^*$. The derived convergence rate is optimal in terms of the accuracy level $\\varepsilon$ for $\\varepsilon$ small enough, resulting in sample complexity $O(\\varepsilon^{-2})$.", "questions": "1. Can Assumption 2.1 be relaxed, at least to cover the setting of uniformly geometrically ergodic chain (s_k,a_k,s_{k+1})?\n2. 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)$?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper is well-structured and rather easy to follow. The paper suggests an MSE bounds for the last-iterate for average-reward Q-learning with a single Markovian data trajectory. These bounds are, to the best of my understanding, new. \n\n***Weaknesses***\n\nMain weaknesses, to my opinion, are limited theoretical novelty and overly strong theoretical assumptions. \n\nFirst, regarding the theoretical assumptions - theoretical guarantees, developed by the authors, rely on the Assumption 2.1 that the Bellman operator is a \\(\\beta\\)-contraction in the span seminorm. The authors suggest a sufficient condition (which is a total-variation contraction of the transition kernel in $1$ step), which is overly strong. This assumption, in fact, is even stronger compared to a unifrom geometric ergodicity of transition kernel.\n\nRegarding the theoretical novelty, it seems that significant parts of the analysis adapts recent papers on seminorm-contractive SA [21,22] in the current submission. The contribution would be much clearer if the authors highlight the new elements of the current submission from those which readily follows from the past stream of works.\n\nFinally, although the work is primarily theoretical, it lacks experimental validation of the results. Moreover, the literature review shows that while adaptive step-sizes have been explored in prior works on discounted Q-learning, no works have attempted to apply them in practice.\n\n***Minor points***\nLine 132: I do not understand where \"(to be discussed shortly)\" refers to", "was_revised": true, "final_justification": "I would like to thank the authors for their clarifications. I am not an expert in the average-reward RL setting, and appreciate the detailed response. I think the paper will greatly benefit from including the outlined discussion (especially about assumption 2.1 and challenges related with the geometric ergodicity and multi-step contraction) to the paper.\n\nRegarding the numerical experiments, I do not insist on including them, as this is a purely theoretical paper. I think that including a toy experiment will not add much to the value of the paper. The main purpose of my comment was to question the practical applicability of adaptive step-size versions of Q-learning.\n\nThat being said, I am happy to increase my score and wish the authors good luck.", "rebuttal": ">Comment: The main weaknesses, in my opinion, are limited theoretical novelty and overly strong theoretical assumptions.\n\n**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.\n\n>Comment: Assumption 2.1 being strong, which is also related to the question of relaxing Assumption 2.1.\n\n**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. \n\nNote 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.\n\nThat 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.\n\n>Comment: The theoretical novelty of this work, especially relative to [21].\n\n**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.\n\nIn 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: \n\n(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; \n\n(2) showing that the errors due to discretization and, more importantly, stochasticity are dominated by the negative drift.\n\nAs 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].\n\nPart (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.\n\nThe 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].\n\n\nTo 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.\n\nOverall, 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.\n\n>Comment: Numerical simulations and practical implementations of Q-learning\n\n**Response:** We will add numerical experiments to verify the performance of Q-learning with adaptive stepsizes in the next version of this work. \n\n\n\n>Minor points Line 132: I do not understand where \"(to be discussed shortly)\" refers to\n\n**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.\n\n>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)$?\n\n**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. \n\nAssuming 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."}, {"review_id": "YQPnLM9TUx", "reviewer": "Reviewer_pG1e", "summary": "This paper delivers the first non-asymptotic analysis of average-reward asynchronous Q-learning. Due to the asynchronous sampling, the authors show the universal stepsizes cannot guarantee convergence. Motivated by the importance-sampling, the authors design an adaptive stepsize and establish an $O(1/k)$ convergence rate. To establish the convergence, the authors reformulate the non-Markovian update as a time-inhomogeneous Markovian SA and breaks the correlation between iterates and data through two main steps: 1. demonstrating that the span of $Q_k$ grows at most $O(\\log k)$ and 2. controlling the data sequence via conditioning arguments and appropriate Markov concentration bounds.", "questions": "It may be due to my lack of expertise in averaged-reward RL, I have some questions about the related work and the main theorem. I hope the following questions would help the authors improve the paper.\n\nQ1. Theorem 3.1 makes no assumptions on the initial point $Q_1$. Should the constant in the upper bound therefore depend on  $||Q_1||_{\\text{span}}$ (or a comparable measure of its magnitude)?\n\nQ2. 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$?\n\nQ3. 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^{*}$.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\nS1. The paper delivers the first finite-time performance bound for average-reward asynchronous Q-learning.\n\nS2. It extends classical Lyapunov-based analyses for Markovian SA to settings with time-inhomogeneous Markovian noise—a contribution that, to my knowledge, is new to the literature. The technique appears broadly applicable to a wider class of SA algorithms with adaptive stepsizes.\n\nS3. The use of adaptive stepsizes derived through an importance-sampling argument is particularly interesting.\n\nS4. This is a theoretically solid work. The paper is relatively well-written. The proof seems correct, although I did not check line by line.\n\nWeaknesses:\n\nPlease see questions below.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n>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)?\n\n**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\n\n$p_{span}(Q_k - Q^\\star)\\leq p_{span}(Q_k) + p_{span}( Q^\\star )\\leq b_k+p_{span}(Q^\\star)=m_k$,\n\nwhere $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.\n\nAs 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:\n\n$p_{span}(Q_K - Q^\\star) \\leq p_{span}(Q_K) + p_{span}(Q^\\star) \\leq b_K + p_{span}(Q^\\star) = m_K$,\n\nwhich is the term that multiplies the leading factor in all cases of Theorem 3.1. \n\nTo 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^*$.\n\n\n\n>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$?\n\n**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.\n\nWe start with Eq. (9) from the submission:\n\n$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$\n\nwhere $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.\n\n*Polynomial stepsizes:*\nAnalogous 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:\n\n$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$,\n\nwhere 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$.\n\n*Constant stepsizes:*\nSimilarly, by setting $\\tilde{\\alpha}_k \\equiv \\alpha$ in Eq. (9), we obtain:\n\n$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$\n\nIn 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.\n\n*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.\n\n>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$.\n\n**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.\n\nThat 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."}]

Author rebuttal:

Meta-review: The paper develops finite-time analysis of average-reward Q-learning in the asynchronous setting with adaptive stepsizes. A highlight of the paper is to demonstrate that adaptive stepsizes provably help, and without adaptation, the algorithm might fail, thus providing a more complete understanding. The reviewers are all positive about the paper, and therefore it warrants acceptance. However, it is not recommended for more recognition due to the caveat that 1) the rate depends pessimistically with the size of the state-action space at a polynomial order, which diminishes the value of the faster convergence rate; 2) the faster rate requires a stringent assumption (Assumption 2.1), which eliminates its applicability to many standard MDPs.
Decision: Accept (poster)