Finite Sample Analysis of Average-Reward TD Learning and $Q$-Learning
Authors: Sheng Zhang
Zhe Zhang
Siva Theja Maguluri
Venue: NeurIPS 2021 Poster (2021)
Keywords: Finite Sample Analysis
Average-Reward Reinforcement Learning
TD Learning with Linear function Approximation
Q-Learning

Abstract: The focus of this paper is on sample complexity guarantees of average-reward reinforcement learning algorithms, which are known to be more challenging to study than their discounted-reward counterparts. To the best of our knowledge, we provide the first known finite sample guarantees using both constant and diminishing step sizes of (i) average-reward TD($\lambda$) with linear function approximation for policy evaluation and (ii) average-reward $Q$-learning in the tabular setting to find the optimal policy. A major challenge is that since the value functions are agnostic to an additive constant, the corresponding Bellman operators are no longer contraction mappings under any norm. We obtain the results for TD($\lambda$) by working in an appropriately defined subspace that ensures uniqueness of the solution. For $Q$-learning, we exploit the span seminorm contractive property of the Bellman operator, and construct a novel Lyapunov function obtained by infimal convolution of a generalized Moreau envelope and the indicator function of a set.

Finite Sample Analysis of Average-Reward TD Learning and Q-Learning
Sheng Zhang" Zhe Zhang" Siva Theja Maguluri
The H. Milton Stewart School of Industrial and Systems Engineering
Georgia Institute of Technology siva. the edu
{shengzhang,
Abstract
The focus of this paper is on sample complexity guarantees of average- reinforcement learning algorithms, which are known to be more challenging to study than their discounted-rewee reward counterparts. To the best of our knowledge, we provide the first known finite sample guarantees using both constant and dimin- ishing step sizes of (i) average-reward TD(A) with linear function approximation for policy evaluation and (ii) average-reward Q-learning in the tabular setting to find the optimal policy. major challenge is that since the value functions are agnostic an additive constant, the corresponding Bellman operators are longer contraction mappings under any norm. We obtain the results for TD(A) by working in appropriately defined subspace that ensures uniqueness of the solution. For Q-learning, we exploit the span seminorm contractive property of the Bellman operator, and construct novel Lyapunov function obtained by infimal convolution a generalized Moreau envelope and the indicator function of a set.
Introduction
The average-reward setting is a classical setting for formulating the goal an infinite-horizon Markov decision process (MDP) [1]. The need to maximize the average reward has been demonstrated in many applications, including scheduling automatic guided vehicles [2), inventory management in supply chains [3], communication system control and routing [4], cooperative multi-robot learning [5] and qucuing network control [6]. In these problems, the discounted-rewann criterion usually leads to poor long-time performance since the system operates over extended period of time and the goal is to optimize long- terg-term behavior, whereas the discounted objective biases the optimal policy to choose actions that lead to high near-term performance.
Even though there is a well developed theory of average-reward MDPs [7, 8, 9], the theoretical understanding of average-reward RL methods is still quite limited. Most existing results are focused only on asymptotic convergence [10, 11, 12, 13]. The focus this paper is to understand the sample efficiency. How much data is required to guarantee given level of accuracy?
Recent literature obtains finite sample guarantees for discounted-reward TD learning and Q-learning algorithms by developing novel analytical techniques [14, 15, 16, 17, 18]. Such a study of average- reward RL algorithms not undertaken. Analysis average-reward RL algorithms is known to be more challenging to study than their discounted-reward counterparts. The key property that is exploited in the study of discounted-red reward problems is the contraction property of the underlying Bellman operator. In the average-reward setting, such a contraction property does not hold under any norm, and the Bellman equation known to have multiple fixed points.
Equua contribution. Correspondence to Sheng Zhang sshhenghang@ggatcchn. <onnczhnggbooggc.omm
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work, we take the first step toward understanding finite sample guarantees of (i) average- reward TD(A) with linear function approximation for policy evaluation, and (ii) average-reward tabular Q-learning in the synchronous setting for the control problem.
1.1 Contributions and Summary of Our Techniques
We establish the first finite sample convergence guarantees of average-reward TD(A) with linear function approximation and average-reward tabular Q-learning in the literature.
TD(A) Results. We study the average-reward TD()) with linear function approximation under general asynchronous update. We present finite sample bounds under both constant and diminishing step sizes. With constant step-size, the iterates converge at an exponential rate to small cylinder around the set of TT fixed points. With properly chosen diminishing step sizes, the mean-square distance of the iterates the set of TD fixed points converges with an Ô (+) rate, and this leads to
sample complexity of Ô (1)). Our sample complexity bound also suggests that an intermediate value of A yields the best performance. The dependence on the effective horizon plays a key role in the study of discounted-reward RI. algorithms [19, 20]. There is no such effective horizon in average-reward problems, and the spectral gap of an appropriately defined matrix plays a key role instead.
TD(A) Analysis. major challenge in the analysis is that the projected Bellman operator is not contraction under any norm. Moreover, even though the projected Bellman equation can be written as linear set of equations, they are underdetermined. So existing techniques [14, 15] are not directly applicable. Since the value function is unique up to an additive constant, we have a unique solution of the projected Bellman equation when restricted an appropriately defined subspace. We exploit this property and work in this subspace, and use a quadratic Lyapunov function to obtain finite sample guarantees.
Q-learning Results. We consider a J-step synchronous Q-learning algorithm. We present finite sample error bounds for both constant and diminishing step sizes. The span of vector is defined to be the difference between the maximum and minimum element. Since the optimal action-value function, Q", is agnostic up an additive constant, we show that, with at most O(1/e²) samples, the expected span of the error QT - Q' converges to for both decreasing and constant step sizes.
Q-learning Analysis. While the corresponding Bellman operator is not contraction under any norm, it is known to be a contraction under the span seminorm. The span seminorm can be interpreted as the foc -distance to the subspace spanned by the all-ones vector. Finite sample bounds for stochastic approximation of a -nomm contractive operators were obtained in [18] by using generalized Moreau envelop as smooth Lyapunov function. Here, we generalize this approach and introduce new Lyapunov function to study span seminorm contractive operators. Our Lyapunov function is obtained by applying an infimal convolution with respect an indicator function the generalized Moreau envelop used in [18].
1.2 Related Literature
Average-Reward MDP. There is an extensive body of literature on awerage-reward MDPs. Several authors have made early contributions to everage-reward problems [21, 7, 8, 22, 23]. There are well known dynamic programming algorithms for finding optimal policies such as policy iteration [7] and value iteration [24]. However, these algorithms require complete knowledge the MDP, and are also computationally intractable in large state spaces [25].
Tsitsiklis and Van Roy [10] proved the asymptotic convergence of the average-reward TD(A) with linear function approximation, and provided approximation error bounds. Yu and Bertsekas [26] proved the asymptotic convergence of the average-reward LSPE(A), and provided the rate of convergence for constant step size. Both TD(1) with linear function approximation and LSPE()) aim to solve the same projected Bellman equation. However, TD(A) is based on stochastic approximation while LSPE(A) is based on least squares. In addition, the papers above assumed that the set of basis functions are independent of the all-ones vector, which apparently does not hold in the tabular setting. We do not require such restrictive assumption in this paper. Recent work has also established the asymptotic convergence of the off-policy average-reward TD learning algorithm in the tabular setting [12], and finite sample guarantees of average-rewan gradient
Average-Reward Policy Evaluation.

---

TD algorithms with linear function approximation [13]. Note that, [13] needed either the restrictive assumption aforementioned or the ridge regularization obtain the finite sample results.
Average-Reward Control. The earliest control algorithms were those introduced by Schwartz [27] and Singh [28] without convergence proofs. The first provably convergent algorithms are RVI Q- learning and SSP Q-learning, introduced by Abounadi, Bertsekas, and Borkar [11]. SSP Q-learning and the algorithm introduced later by Gosavi [29] are limited to MDPs with special state that is recurrent under all stationary policies, whereas RVI Q-learning is convergent for more general MDPs. Recently, Wan et al.[12] introduced an algorithm without reference function, which is needed in RVI Q-learning, and proved its asymptotic convergence with the techniques which are slight generalization of those in [11]. To the best of our knowledge, our paper the first work in the literature that studies the finite sample guarantees of general average-reward Q-learning algorithm.
Stochastic Approximation. Many RL algorithms
be viewed through the lens of stochastic
approximation (SA). There a well developed asymptotic theory of SA [30, 31, 32). The ODE method is a dominant approach used in most asymptotic convergence proofs in RL [33]. However, this is a coarse tool, since it is not able to generate insight into an algorithm's 's sensitivity to noise in the system and step-size choices. Driven by the interest in finite sample guarantees of RL algorithms, recent years have witnessed focus shifted from asymptotic analysis to non-asymptotic analysis of SA schemes. For example, a finite-time bound for linear SA was given in [15], which leads to finite- time bounds for asynchronous TD learning. [17] provided finite-time analysis of asynchronous nonlinear SA, which yields finite-time bounds for asynchronous Q-learning.
Others. There are other related papers which are beyond the scope of the present paper. For instance, there is a line of work [34, 35, 36] regret guarantees, which is different focus compared to our work, for learning in average-reward MDPs. In addition, there are RL methods based on linear programming [37, 38], or learning automata [39, 40].
The Average-Reward Problem Setting
We consider an infinite-horizon average-reward MDP described by (S, R. p). where S (1.2.... ..... ||] is a finite state space, A = (1.2..... | is finite action space, R A - [0. is the reward function, and p S x S A + [0. 1] is the transition dynamics of the environment. An agent interacts with the environment according to the following protocol: at each time step 1 == 0, 1,2.... the agent is in a state S, S and selects action A, E A, then receives from the environment an immediate reward RS,,, A₂) and the next state S1+1 which is a sample drawn from P(-|S,, At). The average reward of deterministic stationary policy p S + A starting from state s E S is defined as
(s) = lim inf 7 E T-220
Σ R(S,, (SS))) =
(2.1)
Let r" (*) == suPpEM rd (s), where M is the set of deterministic stationary policies. A policy
4² E . is said to be optimal if it satisfies pd( (s) (s) for all S.
3 Policy Evaluation Algorithm: TD Learning
3.1 Problem Formulation
We consider the problem of evaluating a given policy μ E M when the data is generated by applying the policy in the MDP. Since the system is an induced Markov reward process (MRP), for simplicity,
we employ the notation R(i)= := R(i, p())) for rewards, and P(i.j) := p(jlú, u(i) for transition probabilities. We make the following standard assumption to ensure the existence and uniqueness of a stationary distribution ; := [_,, s
Assumption 1. The Markov chain associated with P is irreducible and aperiodic
*It is standard assumption in studying convergence of TD learning algorithms with linear function approxi- mation (41, 10, 14] and guarantees that all states are visited an infinite number of times during an infinitely long trajectory.
3

---

Notice that x satisfies T = π with n; > 0 for all E S. Let E. denote expectation with respect to and define D = (T.. A(ss) E R It is easy to see that (x. y) == x Dy a D-weighted inner product and we denote its induced norm by | == Vx Dr.
Under Assumption 1, the average reward in (2.1) satisfies r*(s) r(m) == T - R for all E S. A differential value function v S - R for policy lr satisfies the Bellman equation To = v, where the Bellman operator T RISI + glSl is defined by T' == R - r(u)e + Pv. Here, e E RI the all-ones vector. Under Assumption 1, it is known that the set of differential value functions takes the form (2/ + celc E R). where v : S - I., known as the basic differential value function, is given by vd
- Pt (R r(u)e).
Most modern applications have large state spaces, so due to the curse of dimensionality, exact value function learning may be intractable. To mitigate this, we consider a linear function approximation
Vi(i) = x(i) 0 to differential value functions, where <61) [61 (i), ... (a(1)) E Rd is the feature vector for state i S and 0 E R4 is tunable parameter vector. Here, {Øx S + Rij 1, 2, ... .d) is set of d basis functions to be viewed as vectors of dimension |S]. With this notation, Vo can be expressed compactly in the form V₂= 46,, where is |S] d matrix whose k-th column is Φx. We assume that & has full column rank; that is, the basis functions {Ør = 1, 2, ... .d are linearly independent. This results no loss of generality because if some basis function de is a linear combination of the others, it can be eliminated without changing the power of the approximation architecture. Additionally, we assume that | I for all E S, which can be ensured through feature normalization.
3.2 Average-Reward TD(A)
Algorithm 1: TD(A) with linear function approximation
Input :initial guess Fo and lg. basis functions {Øx 12=1 step-size sequence (3e JeN and positive constant Ca.
Initialize: 2-1 0, À E 10.
for f = 1, do
Observe tuple: O, (st, R(st), 81+1)
Get TD error: 6,, - R(s)) - Ft ((1+11) 0, o(s)) T0,
Update eligibility trace: 2, = λ + (($))
Update average-reward estimate: fi+1 Fi + (R(s))())) Fr))
Update parameter vector: f,+1 = 0, + (0,)22
end
We study the average-reward TD learning with eligibility traces [10], denoted by TD(A) and parame- terized by À E [0. 1). We consider the Markov chain observation model, where the observed tuples used by TD(A) are gathered from single trajectory of the MRP. At every time step f, the algorithm observes one data tuple O := (st, R(s)). sc-1) consisting of the current state, the current reward and the next state. Suppose that at some time t, the current value of the parameter vector 0 is 0,, and we have a scalar estimate F, of the average reward r(u),, we define the TD error ò, (0.) corresponding the transition from 8t to 8 as (0.) R(st) Ft ((5++1) )) 0, - d(s:)T( To. TD(A) updates F, and Og as follows:
Fit1 Ft (R(st) r.) and 0,+1 02 + (0))
(3.1)
where on and 3r are scalar step sizes, and the vector := Ek x (($)) is called the eligibility trace.
In this work, we focus on the single time-scale variant of TD(A) presented in Algorithm 1, that is, we assume that there exists a constant e, > 0 such that a₂ = C,,3, for all t. In order to represent TD(A) in compact form, we construct a process X == (st, 1 2.). It is easy to see that (X.} is
a Markov chain with an infinite state space. If we let O, = Ft the TD(A) updates (3.1) can be
0g
expressed compactly
0,1= 0. [ b(X,)).
(3.2)

---

where
CCa A(x))
((:)) R(s{)
(0(841)TT- ((s)) and b(X,)
-t
Non-uniqueness of TD(A) limit point. For any m = 0, 1.,, the m-step Bellman operator is given by
T PR'
pm+
1=
The asymptotic properties of (D(A) are closely tied to the X-weighted version of the m-step Bellman operator. Define the averaged Bellman operator
TWyy (1 (1-X) A)
xmpm+
m==
Note that the set of differential value functions is also the fixed points of T(A); see Lemma 3 in [10] for proof.
We denote by A E, [A()))] and b E, [Xx))] the steady-state expectations of A(X;) and ((,), respectively. Stochastic approximation theory [32] shows that the asymptotic behavior of the sequence [ generated by (3.2) is closely linked with the corresponding ordinary differential
equation (ODE) Ô, AO, + b, and the limit of θ, denoted by Ox Foo if exists, is an Ox
cquilibrium point of the ODE, i.c.
A + b b 0.
(3.3)
Therefore, Foo = r()), and 0o is solution of the projected Bellman equation
t = I,,,, TA))0
(3.4)
where IID,w, =- + (Φ D4) D is the projection matrix onto the column space Ws. == ( Rd) of de with respect to the norm |1-||p- It worth noting that if Ws, then II H.D.W, w. (A) has multiple fixed points, since any scalar multiple of when added fixed point of II D.D. w. (A)
would also be a fixed point. For example, in the tabular case where = I, Eq. (3.4) would become g, of which the set of differential value functions are solutions.
3.3 Finite-Time Bounds for Average-Reward TD(A)
Before we present the finite-time bounds on the performance of TD(A) with Markovian observation noise, we illustrate the key ideas, which are inspired by [15]. The detailed proof can be found in Appendix A.3.
We study the drift of an appropriately chosen Lyapunov function obtain an upper bound on the mean-square error. We define the subspace Sq,e as
So = span (00 = = {0).
i & Wa. [d).E))) if e E Wa and Φ0. = e.
Let E be the orthogonal complement of Sp.c. We can interpret E as the set equivalent classes with the equivalence relation ~ on Idd defined by 01 ~ O2 and only if 01 - 02 is in Sa,e- The following lemma characterizes the set of TD(A) fixed points; see Appendix A.1 for proof.
Lemma 1. Under Assumption 1, the fixed points of the projected Bellman equation (3.4) are
(0*) (0+ + dl E RR,
i & Wo. ife Wa and $8. c,
C -- St.e
(0) Here, Hp, (.) is the projection operator onto the subspace W { E}} with respect to the norm ||: D
where 6* E E is a unique solution the equation &0 II DD)
5

---

Remark 1. In the case where e & Wa. the projected Bellman equation (3.4) has a unique fixed point 8". This is why prior work requires that e does not belong to the column space of D.
We consider the Lyapunov function ((, == (F- (F-r |[|2 (0 0*) Here, 112.5 is
the projection onto the subspace E with respect to the 2-norm |1-112- Note that ||I|,, e (0 - 0r) 2 measures the distance of f the set of TD(A) fixed points. The following Lemma establishes that the matrix A in (3.3) is negative definite over the subspace IR x E for sufficiently large cg. The proof presented Appendix A.2. With this result, we can show that the Lyapunov function (rr 0) has one-time-step negative drift.
Lemma 2. Under Assumption 1, we have
TT D TTTDD(- 1 0.
A
min 10 1,
(3.5)
where P(A) (1 A) -m A pm+1 have
Furthermore, when Ca 2 A+ v 2211-211
(1-x32
A 2
min
-T ATO 2
|
To handle the Markovian noise, we use the conditioning argument along with the geometric mixing of the underlying Markov chain {Xe}. Thus, we consider the following definition of the mixing time of Markov chain.
Definition 1. Given a positive constant e, we define r(E) 2 to be the mixing time of Markov chain {X,} such that
E [A(x))) - AAl2 S and [b(x) Xo] - bll2 S for any Xo and t 2 r(E)
The following lemma establishes that the expectations of A(x)) and b(X,) converge to their steady- state values a geometric rate. See Lemma 6.7 in [42] for proof.
Lemma 3. Under Assumption 1, the Markov chain {X,} has a geometric mixing time, i.e., there exists a constant K 2 such that given a small positive constant e we have r(c) S KIn (t).
We now state two unite-time bounds the performance of TD(A). Part (a) studies TD(A) applied with sufficiently small constant step-size, which is common in practice. In this case, the iterates O will never converge any TD(A) fixed point due the noise variance, but result shows that the expected distance of 6, to the set of TD(A) fixed points decreases at an exponential rate below some level that depends on the choice of step-size. Part (b) attains an Ô (+) convergence rate to some TD(A) fixed point with carefully chosen decaying step-size sequence.
Theorem 1. Consider iterates {(Fr, 0:)} generated by Algorithm with Assumption 1 and
Ca 2 + V MP TT-IJo Let & = ( (2/18 106++10011 110111 Vr(w)² + 110 +1 and
2
(vrlw) + 110-112 +1) [1001[+1]
& = 22817
where n V
5 (--X
(a) Let B B for all 1, where positive constant B is properly chosen such that AB < and A }. Then, for all T 2 T(3), we have
(T( & min an 22877
E [iT - ((w)) 1112, E (Or - or) 03>1 < E1
(1
A
T-r(8)
+ E2 3T(3)
(b) Let 3, = e where positive constants 6₁ and 02 are properly chosen such that 2 < Ae < 202 1402
and there exists a smallest positive integer t" such that Ei--1 3x S 2n and for all t 2 t", 1111 E 3x S min an 228q2 }. Then, for all T 2 t", we have
a
Ag
t' +
8eK oft In(T + 02) In(e1)
(FT r(n))² + |11|, (0T 00)13 <1
+
T
Aci -2
T +2

---

Therefore, with an appropriate decaying step sizes suggested in Theorem 1(b), the following sample complexity of Algorithm can be obtained.
Corollary 1. To find pair (f.0) with E B r(u)ll and E [[[T2 & (0 12) Algorithm I requires at most the following number of samples:
K log (2) |10
A1(1 Xy
where K is the mixing time constant defined in Lemma 3.
Remark 2. Since A defined in (3.5) non-decreasing function of X, the sample complexity in Corollary implies that the optimal X should be neither too large nor too small.
3,4 Approximation Error
As we are satisfied with an approximation of any differential value function, define the approx- imation error, infEER || - (v" + ce) p: as the infimum of the D-weighted Euclidean distance of &0" the set of differential value functions. Following the similar arguments from the proof of Theorem 3 in [10], we obtain the following upproximation error bound,
1 inf | (v" + cE)llD,
inf ||00" (v* ce)llD cER
(3.6)
VI-
BER4,oER
where the constant CΛ is in [0, 1) for any (0, and goes to 0 as - 1. Note that the term inføER",cER ||00 - (v" + cE)llD is the minimal error possible given approximation architecture, and becomes zero if our approximation architecture is able to represent exactly some differential value function. In particular, under the tabular setting, since any differential value function has exact representation, we have inf || |00" - (v" + ce)ll 0.
Control Algorithm: Q-learning
4.1 Problem Formulation
We consider the problem of finding an optimal policy μ E M under the following unichain assumption (see Section 8.4 in [9] for details).
Assumption 2. An MDP is called unichain if the induced Markov chain consists of a single recurrent class plus a possibly empty set of transient states for any deterministic stationary policy.
Under Assumption 2, standard MDP theory [9] shows that there exist unique r" E R such that (s)) r" for all S, and unique Q" : S
I up an additive constant, such that the following Bellman optimality equation holds for all state-action pairs (s, E S x A:
Q" (8, a) = R(s, a) + Eves p(s1ss,a) max Q" (s',''''' -
(4.1)
The optimal policy n² is then obtained by μ² (s) = argmax aE (8 a). If we define E = fcelc E }} as the subspace spanned by the all-ones vector e E IR x|AI and denote the Bellman operator H by
(s,) R() Evest(s')ss a) max.'e ('(,,aa), V(s,a) SSA.
then (4.1) can be rewritten set inclusion condition:
Q -H(Q))
(4.2)
Importantly, by observing that the operator is indifferent to constant shifting, i.e., HQQ + ce) (QQ) + ce, we can view all Q constant shifts, QE = IQ + ce E R), as an equivalent class and interpret (4.2) as fixed-set equation:
Q H(
(4.3)
Next we propose an SA algorithm to solve (4.3) by iteratively updating some "representative" of the underlying equivalent class.
7

---

Algorithm 2: .-step Synchronous Q-learning
Input :initial guess Qu. step-size sequence HEN offiset function f R1S|(|A1 7 R.
for 0, 1....... do
Compute the Qe-improving policy (+(s) == arg max, Qi a) for all E. A do Sample s' a), 6² p(-ls' (1(5)) )) ,)....,, ~ :He(s")))) ,p((s",,((s""))
for (s,a)
Compute Q++1(8,0) a) &- Q+(s,a)+
di (R( + E ((s)) + Qi(s .m(s)) - -f(Qi))
end
end
4.2 Synchronous Q-learning
Given the sample Bellman operator A defined by
H(Q)(s, a) = R(s,a) + max Q(s', Q(s', p(.ss,)), V(s,a) a'EA
an SA algorithm for solving (4.3) is
Q++1== 11 (f((Q))
(4.4)
It might be necessary, sometimes, to apply H to Q for steps before updating Q. More specifically, if we denote by (s( arg max, Q(8, a) the Q-improving policy, the J-step Bellman operator and the J-step fixed-set equation are
H (Q)(s, a) == R(s, a) + Eg
(o(ss--))))) R(s (Q(s)) +... R(s ( (Q(()-1)) +
(4.5)
(Q)))) = Q
(4.6)
So the J-step SA algorithm is the same as (4.4) except for J-step sample Bellman operator,
( R) R(s', (o((s)) +... + R(s ( Q41 (q(")) where s² p(- .'... od p(-1s--1, (ogss--1)) The complete algorithm is presented in Algorithm
1. (2) The solution to the J-step fixed-set sixe--st equation (4.6) is the same for all J 2 1. (3) An extra offset function f(Q) included to ensure numerical stability (see Section 2.2 in [11]). If = and the offser function f satisfies Assumption 2.2 in [11], Algorithu recovers the RVI Q-learning algorithm.
Remark 3. (1) The SA algorithm in (4.4) is a special case of Algorithm 2 with
4.3 Finite-Time Time Analysis
Now seek establish finite-time convergence guarantees of Algorithm 2. Since the Q-improving policy and its suboptimality gap are the same for any Q E Qg. we can measure Algorithm 2's progress by
||Q Q lla := min [I - Q*) - ce) CER
(4.7)
for some norm Il. For example, the span seminorm is equivalent ||. Il.loo.sp Additionally, need to make span contraction assumption similar to Theorem 8.5.2 in [9].
Assumption 3. The J-step Bellman operator J is span contraction for some J 2 1, i.e., there exists a y 1) such that for any Q1 and Q2 defined S x A.
|| H (Q)) H HQ2) so.sp S ||Q - Q21loc.p
Such an assumption not restrictive, lower bound for - 7 is the minimum probability of any two deterministic stationary Markov policies starting from any pair of states ending in the same state

---

in J/ steps [9]. Thus, under an unichain assumption, can be guaranteed for J [S] if we apply the aperiodic transformation in Section 8.5.4 of [9] ensure non-zero probability of all states in single recurrent class in |S] steps.
We sketch the outline of Lyaponuv convergence proof and leave the details Appendix B. First, we construct a Lyaponov functtin. The key insight is that the span seminorm Il- can be interpreted the infimal convolution of the -oom Il and the indicator function of E, i.e.,
|| (11 (z) inf | yll +g((v) Vx,
(4.8)
where (z(z) 00 x xE E,
oc, otherwise.
As illustrated by Lemma 4 in Appendix B. the inifimal convolution operation has many desirable properties. For example, is commutative, associative, sunvexity-preservii and smoothness- preserving. These nice properties allow to design Lyaponov function Mg for the equivalent classes by tweaking the usual Lyaponov function M as follows,
Mg(Q)= == (MD6g) (Q).
(4.9)
In particular, since Assumption implies only span contraction, we utilize the smoothed Lyaponov function proposed in [18] for fo norm contraction, i.e., M(Q) == (11-11 D (1)1( with p = 4 log([S]]AA) and == (1/2 + 1/(2))) 1. We show M (-) is uniform approximation of |1-113x...
101
AQ.
and it is smooth with respect to |1-11 pmppp
Mg(Qu+1- - Q*) = M (VM((---))))))
Q")
Q1)
(4.10)
[[og(| ||Q++1
Q: 1:122-p
Next, since the span contraction assumption leads to a negative drift (4.10) for some constant 0g defined in Appendix B.3,
E (VM Q*) Q111 Qil < Ma(H - --) M (Qu Q*)
(4.11)
I -2 Q*),
we can use the smoothness and uniform approximation properties of Mg to provide a recursive bound of Q++1 for some 03 and Ota defined in Appendix B.3,
E E[Ma(Q++1 - Q')l S (1 - 2022) + az Ma - Q²) + oarh
(4.12)
Clearly, by taking a small enough step size TJ. (4.12) implies the convergence of [Mę(Q: Q*)] Now we can state sample complexity upper bound for Algorithm 2 by choosing specific step-size sequence.
Theorem 2. If (Qr) is generated by Algorithm 2 with a decaying step-size sequence
T/ 1-n t with = max {
[288log( (
.3
(1-7)²
then for some universal constant the following bound holds for all t 2 1,
[1Q+ - 1111 1111--0112..1
s
110-Q'112 113 (log [S)?
(J²+1IQ' 113
(19) Al)
41-
(1-7)
(1-
instead a constant step size 17 S
(S||AA) is employed, then
E 3[1Q. - 12122_00 5 v
- 1Qo 11 + 48(J2 -1Q 11 log ([8||A])
(1

---

In both cases, it takes
( (J2 + ( +1 11100"110, spo (/psss111111 [og([S)|411)
|og() (1-1) (1-7)882
samples to find Q. with E span contraction assumption, the sample complexity can be simplified further to
[[Q: - Q* 20
S 6. Taking into account ||@" lloc S 1- from the
δ | (1-7)622
which is similar to the sample complexity of 7-discounted Q-learning algorithm [18, 43).
5 Numerical Experiments
In this section we present empirical results of the average-reward TD(A) with linear function approxi- mation (i.e. Algorithm 1). In our simulation, consider a randomly generated MRP with |8| 100 states and a randomly generated feature matrix with d = 20 features and E Wa. Experimental details and figures are provided in Appendix C. All the implemeentations are publicly available
We first show that if the algorithm starts from different initial points. it will converge to different TD fixed points. To demonstrate that, we implement the algorithm using diminishing step sizes
as functions of the number of iterations in Figure 1 and 2, respectively. Recall from Lemma that {0- + cfe/c R} the set of TD limit points. We observe in Figure that E [[[TT, (0, 0* }| converges to 0 for all 4 initial points, which means that the iterates 0g converge to some TD limit point regardless of 0g Moreover, Figure shows that E. (0, - 0²) 00 [o converges different values for different
for 4 different og. and then plot E |||||, (6: 112] and (0, - ---) T [10
0.
initial points. This, combined with Figure 1, implies that the algorithm converges to different TD limit points, starting from different 0g-
We next numerically verify the finite-time error bounds of Algorithm 1 using decaying step sizes. In Figure 3, we plot E (Fr - r² + |[[ (0. 8* || as a function of t for X E {0, 0.2, 0.4, 0.8), where r" denotes the average-reward of the MRP. We see that the iterates {(Fr, 0:)) of the algorithm converge for all values of X. To further verify the rate of convergence, we plot In E (Fr- (Fe-r*)² || (0, (0,-0")1: 01)
as a function of In in Figure 4 for large / and the slopes of
these lines are provided in the legend. The plot shows E (Fr - (+) + ||lb, (0, - 03)1 ~ (H) asymptotically, which agrees with Theorem 1(b). In addition, we notice from Figure and that the best À in terms of sample complexity is 0.2, which confirms our Remark 2 that intermediate value of yields the best performance with regard to sample complexity.
Conclusion
We establish the first finite sample convergence bounds of (i) average-reward TD(A) with linear function approximation under Markovian observation noise, and (ii) average-reward tabular Q- learning in the synchronous setting. These RL algorithms can be viewed as SA schemes to solve average-reward Bellman equations. However, the Bellman operators are not contractive under any norm. To resolve this difficulty, we construct Lyapunov functions using projection and infimal convolution to analyze the convergence of equivalent classes generated by these algorithms. Our approach is simple and general,
expect it to have broader applications in other problems.
When analyzing the average-reward Q-learning algorithm, we made a J-step span contraction assumption (i.e. Assumption 4), which is not needed for the asymptotic convergence [10]. However, is unclear such an assumption necessary for establishing any finite-time convergence bound. Since our results are the first finite sample bounds, future research direction is on relaxing this assumption. Besides, it would be interesting to experiment our algorithms in practice and see how the empirical performance is compared with our theoretical bounds.
"huns///ghhbbboomm/ooojinnnnnnna Reward TD-
-ewaad-TD.--LLaaaniiee Q-Leaming
10

---

Acknowledgment
This work was partially supported by an award from Raytheon Technologies and seed grant from Georgia Institute of Technology.
References
[1] Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3(1):9 44, 1988.
[2] Prasad Tadepalli, DoKyeong Ok, al. H-learning: A reinforcement learning method optimize undiscounted average reward. 1994.
[3] Ilaria Giannoccaro and Pierpaolo Pontrandolfo. Inventory management in supply chains: reinforcement learning approach. International Journal of Production Economics, 78(2):153- 161, 2002.
[4] Peter Marbach, Oliver Mihatsch, and John N Tsitsiklis. Call admission control and routing in integrated services networks using ceuro-dynamic programming. IEEE Journal on selected areas in communications, 18(2):197-208, 2000.
[5] Poj Tangamchit, John M Dolan, and Pradeep K Khosla. The necessity of average rewards in cooperative multirobot learning. In Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292), volume 2, pages 1296-1301. IEEE, 2002.
[6] Jim G Dai and Mark Gluzman. Queueing network controls via deep reinforcement learning. arXiv preprint 20Xiv:2088.01444 2020.
[7] Ronald A Howard. Dynamic programming and markov processes. 1960.
[8] David Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pages 719-726, 1962.
[9] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming John Wiley & Sons, 2014.
[10] John N Tsitsiklis and Benjamin Van Roy. Average cost temporal learning, Automatica, 35(11):1799-1800 1999.
[1]] Jinane Abounadi, D Bertsekas, and Vivek S Borkar. Learning algorithms for markov decision processes with average cost. SIAM Journal Control and Optimization, 40(3):681-698 2001.
[12] Yi Wan, Abhishek Naik, and Richard S Sutton. Learning and planning in average-reward markov decision processes. arXiv preprint arXiv:2006. 16318, 2020.
[13] Shangtong Zhang, Yi Wan, Richard S Sutton, and Shimon Whiteson. Average-reward off-policy policy evaluation with function approximation. arXiv preprint arXiv:2101.02808 2021.
[14] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation, arXiv preprint arXiv: 1806.004400 2018.
[15] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Conference Learning Theory, pages 2803-2830. PMLR, 2019.
[16] Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Performance of q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprint arXiv: 1905. 2019.
[17] Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approxima- tion and q-learning. In Conference on Learning Theory, pages
PMLR, 2020.
[18] Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite- sample analysis of stochastic approximation using smooth convex envelopes. arXiv preprint arXiv:2002.00874. 2020.

---

[19] Ashwin Pananjady and Martin Wainwright. ceeancee-ependentt -oundds for policy evalua- tion in tabular reinforcement learning. IEEE Transactions on Information Theory, 6761):566
585, 2020.
[20] Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A lya- punov theory for sample guarantees of asynchronous q-learning and td-learning variants. arXiv preprini arXiv:2 102.01 2021.
[21] Dean Gillette, stochastic games with zero stop probabilities. Contributions the Theory of Gumes (AM-39), Volume III, pages 179-188. Princeton University Press, 2016.
[22] Barry W Brown. On the iterative method of dynamic programming finite space discrete time markov process. The annals of mathematical statistics, pages 1279-1285, 1965.
[23] Arthur F Veinott. On finding optimal policies in discrete dynamic programming with no discounting. The Annals of Mathematical Statistics, 37(5):1284 ((5)):124-1294 1294, 1966.
[24] Douglas J White. Dynamic programming, markov chains, and the method of successive approximations. Journal of Mathematical Analysis and Applications, 6(3):373-376, 1963.
[25] Sridhar Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine learning, 22(():159-1955 1996.
[26] Huizhen Yu and Dimitri P Bertsekas. Convergence results for some temporal difference methods based on least squares. IEEE Transactions on Automatic Control, 54(7):1515-1333 1531, 2009.
[27] Anton Schwartz. A reinforcement learning method for maximizing undiscounted rewards. In Proceedings of the tenth international conference on machine learning. volume 298, pages 298-305 1993.
[28] Satinder P Singh. Reinforcement learning algorithms for average-payoff markovian decision processes. In AAAI, volume 94, pages 700-705, 1994.
[29] Abhijit Gosavi. Reinforcement learning for long-run average cost. European Journal of Operational Research, 155(3):654-674, 2004.
[30] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
[31] Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009.
[32] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science Business Media, 2012.
[33] Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447446,, 2000.
[34] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning, Journal of Machine Learning Research, 11(4), 2010.
[35] Yasin Abbasi-Yadkon Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference Machine Learning, pages 3692-3702. PMLR, 2019.
[36] Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward markov decision processes. In International Conference on Machine Learning, pages 10170-10180. PMLR, 2020.
[37] Mengdi Wang. Primal-dual v learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint arXiv:1710.061000 2017.
[38] Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-regularized markov decision processes. arXiv preprint 170507170, 2017.
12

---

[39] R Wheeler and K Narendra. Decentralized learning in finite markov chains. IEEE Transactions on Automatic Control, 31(6):519-526, 1986.
[40] Hyeong Soo Chang. Decentralized learning in finite markov chains: revisited. IEEE Transac- lions on Automatic Control, 54(7):1648-1653: 2009.
[41] John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE transactions on automatic control, 42(5)x674-690, 1997.
[42] Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
[43] Martin J Wainwright. Stochastic approximation with cone-contractive operators: Sharp & bounds for q-learning. arXiv preprint arXiv:1905.06220 2019.
[44] Abhishek Gupta, Rahul Jain, and Peter W Glynn. An empirical algorithm for relative value iteration average-cost mdps. 2015 54th IEEE Conference on Decision and Control (CDC), pages 5079-5084. IEEE, 2015.
[45] Amir Beck. First-order methods in optimization. SIAM, 2017.
13


Reviews:
[{"review_id": "cw-Ge3WWqm0", "reviewer": "Reviewer_bLoK", "summary": "This paper focuses on the theoretical analysis (especially on the non-asymptotic sample efficiency) of two algorithms under the average-reward setting: (1) TD($\\lambda$) with linear function approximation under Markovian observation noise (2) tabular Q-learning in the synchronous setting.\n\nPrevious works have obtained similar finite-sample guarantees under the discounted setting. However, this work focuses on the average-reward setting where the Bellman equation is known to have multiple fixed points. For the TD($\\lambda$) analysis, the authors work in a subspace to get the unique solution of the projected Bellman equation. For the Q-Learning case, the Bellman operator is a contraction under the span seminorm.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides the first known finite-sample guarantees using both constant and diminishing step sizes of two widely applicable algorithms in RL. \n\nThere are, however, several points that can benefit the manuscript if tended to:\n\n1)  It would be helpful to highlight the substantial differences in a nutshell from the present analysis and from [Zhang et al, 2021].\n\n2) The paper proposed convergence guarantees for the TD learning algorithm and the Q-learning algorithm. However, currently, the sense of how tight the proposed convergence theorem and analysis are reflected in real/practical scenarios is missing.\n\nThe paper would greatly benefit from further theoretical/experimental discussions that investigate:\n\ni)How does the change from discounted setting to the average-reward setting affect the terms in the main theorem (compared with [Zhang et al, 2021])?\n\nii) How does this algorithm converge in practice? In what zone does the theoretical analysis match the practical performance?\n\nOverall, this paper provides insightful and novel theoretical results that broaden our analyzing tools on td learning and Q-learning under the stochastic approximation framework.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed that one of the limitations of their work is that it is unclear whether Assumption 4 is necessary for establishing any finite time convergence bound.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "aJxCADf1RdE", "reviewer": "Reviewer_qoyS", "summary": "This paper focuses on the infinite-horizon average-reward setting and develops the non-asymptotic upper bound for TD($\\lambda$) with linear function approximation and tabular Q-learning. Its upper bounds match the best-known results on the discounted-reward MDP for $\\epsilon$-accuracy. Its technique used to deal with the non-uniqueness of the limit point seems new, and its construction of Lyapunov function from noticing the connection between the span seminorm and the infimal convolution is a non-trivial observation. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Thanks for this well-written work with solid theoretical analysis on the infinite-horizon average-reward RL problem. I agree that this paper has its own technical novelty in dealing with the non-uniqueness of limit points. All derived upper bounds nearly match the existing infinite-horizon discounted-reward RL problem. There are several of my concerns regarding this paper:\n1.\tI am not clear if the average-reward setting is practical in real-life applications since most of the cited applications ([2], [3], and [4]) are from 20 years ago. Is there any more recent work using this setup?\n2.\tAssumption 3 in Section 4.3 seems unnatural for me. For the traditional discounted-reward setup, there is no such assumption. Does this assumption automatically hold for discounted-reward MDP? \n3.\tFrom Theorem 2, it seems that $\\gamma$ is comparable with the discounted factor. However, the dependence on $\\gamma$ is worse than the best-known result on discounted-reward Q-learning: In the paper below, the order of $1/(1-\\gamma)$ is 4 rather than 5.\nLi, Gen, et al. \"Is Q-learning minimax optimal? a tight sample complexity analysis.\" arXiv preprint arXiv:2102.06548 (2021).\nMoreover, the analysis of tabular Q-learning is not as complete as TD($\\lambda$). In Section 3.3, this paper introduces two learning rate schedules: constant learning rate and decaying learning rate. But for tabular Q-learning, this paper only considers the decaying learning rate. So, I think there are still many works that should be done on the Q-learning section. \n\nIn summary, this paper can be further improved by introducing more recent applications and adding more explanations on the non-standard assumption. Regarding the Q-learning section, I don’t think it is complete enough, as stated above, so I cannot give a clear accept.    ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since this paper is purely theoretical, the limitations and societal impact section are not applicable. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "D_Uf3HG9Op6", "reviewer": "Reviewer_1neJ", "summary": "This paper establishes the first finite-sample convergence results for average-reward TD(\\lambda) policy evaluation with linear function approximation and average-reward tabular Q-learning in the synchronous setting. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. This work provides novel theoretical results for average-reward MDP with solid technical contributions;\n2. The paper is well-written and the ideas are clearly explained.\n\nI have several questions:\n\n1. The current results are: policy evaluation with linear function approximation and tabular control. I wonder why the authors did not further extend to control with linear function approximation. Is there any technical challenge in achieving that?\n\n2. The current convergence is to the best solution in the linear space i.e., \\theta^*. I wonder whether the algorithm is robust to model misspecification, i.e., if the value function can not really be linearly represented, how the representation error (\\|V-\\Phi\\theta^*\\|) would affect the convergence.\n\n3. In line 81, do you mean LSPE(\\lambda) instead of LSTD(\\lambda)?\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "3aD0Dmzvl3g", "reviewer": "Reviewer_ZKyN", "summary": "This paper studies the average reward TD-learning and Q-learning. In detail, the authors analyze the TD-$\\lambda$ learning with linear function approximation. A finite sample analysis is given for the constant step size and diminishing step size. They also provide a finite-sample analysis of Q-learning in a tabular setting. The main contribution in this paper is how to deal with the constant shift in Bellman equality. In detail, in the TD-learning part, their analysis does not need to assume the uniqueness of the limit point of TD-$\\lambda$. In the Q-learning part, they build the contraction based on the distance between two function classes to consider the constant shift.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well organized and written. It provides a solid theoretical tool to analyze the constant shift in the value function. However, for the TD-learning part, the proof technique is similar to [1]. The result, including the constant step size and the diminishing step size, is also similar to [1]. Therefore, the contribution of this paper is somehow limited, and the result cannot be considered groundbreaking.\n\nAnother drawback in the Q-learning part is the proposed algorithm needs a generative model which allows simulating the trajectory for $J$ step given arbitrary initial state and action $(s, a)$. This will make the algorithm impractical, comparing to an algorithm receiving the initial state from an unknown distribution.\n\nI tend to suggest marginally reject this paper due to the limitation of contribution. I'd like to change my adjust my rating after discussion.\n\n[1] Bhandari, Jalaj, Daniel Russo, and Raghav Singal. \"A finite time analysis of temporal difference learning with linear function approximation.\" Conference on learning theory. PMLR, 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There's no negative societal impact in this paper.\n\nSuggestions:\n\nThe paper is overall easy to follow.  In Corollary 1, I'll suggest the authors restate that the learning rate is set as the case (b) in Theorem 1. It confused me at first because it is not well-clarified. \n\nFurthermore, there's a series of works [2, 3] also providing finite-time analysis in the average reward setting using Actor-Critic with linear function approximation. However, all these works require the unique limit point of TD. Therefore, it would be interesting if the authors can comment about how the proposed method in this paper can be extended to these works to remove such uniqueness assumption. These comments will help readers understanding the contribution of this paper better.\n\n[2] Qiu, Shuang, et al. \"On Finite-Time Convergence of Actor-Critic Algorithm.\" IEEE Journal on Selected Areas in Information Theory 2.2 (2021): 652-664.\n\n[3] Wu, Yue, et al. \"A finite time analysis of two time-scale actor critic methods.\" Advances in Neural Information Processing Systems, 2020.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves the sample complexity of $TD(\lambda)$ learning and Q-learning in the average reward setting. After the author response and reviewer discussion, the paper gathers enough support from the reviewers. Thus, I recommend acceptance. 

Decision: Accept (Poster)