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].
Average-Reward Policy Evaluation. 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
Tsitsiklis and Van Roy [10] proved the asymptotic convergence

---

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 I == 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
Foo if exists, is an Ox
equation (ODE) Ô, AO, + b, and the limit of θ, denoted by 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
for (s,a)
Sample s' a), 6² p(-ls' (1(s)) )) ,)....,, ~ :He(s")))) ,p((s",,((s""))
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(()) 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 s 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 11 (po (/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.00440 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": "Tqb9aRnadBy", "reviewer": "Reviewer_Vg8w", "summary": "This paper provides finite-sample convergence analysis of TD algorithms in both policy evaluation and optimization, under the average reward setting. ", "questions": "", "limitations": "", "rating": 5, "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 provides finite-sample convergence analysis of TD algorithms in both policy evaluation and optimization, under the average reward setting. Such a setting is basically more challenging than the finite horizon and discount reward settings. The paper can be divided into two quite separate parts. The first part studies policy evaluation with linear function approximations and the second part studies policy optimization (Q-learning) with tabular MDPs. \n\nFor the first part, the paper provides a solid analysis of the convergence rate/sample efficiency by showing that the underlying ODE of the solution path has a negative drift and characterizing the error from Markovian noise. The paper shows that the equilibrium of the ODE is the fixed point of the projected Bellman equation and also discussed the case when it is not unique. I did not check the complete proof but believe the analysis route is correct. The properties of the ODE of TD($\\lambda$) under the average-reward setting with linear function approximations (Lemma 2) can be a solid contribution to the theoretical foundation of reinforcement learning.\n\nFor the second part, it seems the proposed algorithm requires the sample starting from each state-action pair, which implies either a simulator of the environment or extra interactions with the environment are required. For either case, this makes the derived results deviate from the purpose of analyzing the sample efficiency, but only the computational efficiency (under a restrictive setting). Also, I believe Assumption 3 deserves more discussion, e.g., the intuitive reason why it holds and the magnitude of $\\gamma$ with regard to J, |S|, or other quantities of the transition kernel matrix.\n\nOverall, the reviewer believes the results on policy evaluation with linear approximation are nontrivial contributions while the results on Q-learning are not very relevant (to be put in the same paper) and with too restrictive environments. Although both algorithms use TD updates, the parametrizations, proof techniques, and sampling schemes are completely different.\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": "4"}, "extra_text": {}}, {"review_id": "FgogQFv93Sy", "reviewer": "Reviewer_2V8c", "summary": "This paper provides finite-sample analysis for the average-reward TD($\\lambda$) policy evaluation with linear function approximation and the average-reward tabular Q-learning algorithm.  ", "questions": "", "limitations": "", "rating": 5, "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 is clearly written and easy to follow. It presents two separate results. One is the TD($\\lambda$) policy evaluation with linear approximation and the other is tabular Q-learning. Both are under the average-reward setting, which is more difficult compared with the discounted infinite-horizon setting.\n\nFor the first part, I think the TD($\\lambda$) policy evaluation with linear function approximation is not that hard even if it's under the average-reward setting. Essentially it is centered around the positive definiteness of $\\Phi^{\\top} D (I - P) \\Phi$ and the rest is just regular routine. For the positive definiteness, it calls the lemma from the MDP book. The potential non-uniqueness of the optimal solution is usually assumed away in previous works but handled in this paper, which I believe is an advantage.\n\nFor the second part, since I am not quite familiar with relevant papers I am not going to judge the technical originality and significance. Some questions are 1) Compared with [17] Chen et al. what is the new technique in this paper, except taking the non-uniqueness into account? 2) Assumption 3 seems non-trivial to me. Line 272 says it's not restrictive since the aperiodic transformation can be applied. That transformation is used to guarantee aperiodicity if I understand correctly. How that can lead to Assumption 3? I feel this claim needs more reasoning and explanation. Also, what is the relation between $J$ and $|S|$?\n\nSome typo I found:\nLine 65: an additional period sign\nLine 553: fellowing -> following", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0o0m7X8LYVL", "reviewer": "Reviewer_wBw2", "summary": "The authors provide a finite sample analysis for average reward TD with linear function approximation. Importantly, the authors succeeded in eliminating a commonly used assumption. The authors also provide a J-step synchronous average reward Q-learning and a corresponding finite sample analysis. One central idea to the success of the paper is to work on equivalent classes directly to deal with the challenge that differential Bellman equation has multiple solutions.", "questions": "", "limitations": "", "rating": 7, "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": "Overall I like the idea to work on equivalence classes directly and it appears novel to me.\nFor the TD side, it is great to see that the assumption X\\theta \\neq ce is finally eliminated. And I believe the study of the TD fixed point in Lemma 1 can be VERY useful for many future work. I briefly checked the proofs of the TD part, it looks correct for me. But I have the following concerns:\n\n1. The equivalence in Line 453 does not seem trivial to me. It is easy to compute \\Pi_{2, E} but computing \\Pi_{D, W^*} looks quite involving. Can the author provide a detailed computation to show this equivalence?\n\n2. In Line 508, the bound of (A1), why does the 4th inequality hold? Shouldn't it contain ||\\Theta_{t-1}||_2 - 1, \\dots, ||\\Theta_{t-\\tau(\\beta_t)}||_2 - 1?\n\n3. In Line 510, the bound of (A2,1), why does the 4th inequality hold? It looks some clarification of the property of \\Theta_{t - \\tau(\\beta_t)} is missing.\n\nFor the Q-learning part, overall the story makes sense to me and I like the idea. However, it looks checking the technical correctness in details requires a good understanding of [17] which I don't have. So I can't comment on this.\nAnyway, I suggest the authors to briefly describe [17] so the readers not familiar with [17] can have some context. \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": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers RL in average-reward setting. In particular, it provides sample complexity guarantees for (1) TD(lambda) with linear function approximation for policy evaluation; (2) Q-learning in the tabular setting for policy optimization. Reviewers believe there is a clear disconnection of the two parts of the paper (since algorithm/setting/proof techniques are all different). Furthermore, reviewers are concerned with the assumptions and technical contribution of the second part. Although reviewers agree the first part does have some interesting technical contribution, but these contribution of the first part alone may not be sufficient for NeurIPS.
Decision: Accept (Poster)