Finite Sample Analysis of Average-Reward TD Learning and Q-Learning
Year: 2022

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(λ) 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(λ) 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.

heading: 1 Introduction
text: The average-reward setting is a classical setting for formulating the goal in 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 queuing network control [6]. In these problems, the discounted-reward criterion usually leads to poor long-time performance since the system operates over an extended period of time and the goal is to optimize long-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 of this paper is to understand the sample efficiency. How much data is required to guarantee a 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 averagereward RL algorithms is not undertaken. Analysis of 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-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 is known to have multiple fixed points.
∗Equal contribution. Correspondence to Sheng Zhang <shengzhang@gatech.edu | shengzhangblog.com>.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this work, we take the first step toward understanding finite sample guarantees of (i) averagereward TD(λ) with linear function approximation for policy evaluation, and (ii) average-reward tabular Q-learning in the synchronous setting for the control problem.

heading: 1.1 Contributions and Summary of Our Techniques
text: We establish the first finite sample convergence guarantees of average-reward TD(λ) with linear function approximation and average-reward tabular Q-learning in the literature.
TD(λ) Results. We study the average-reward TD(λ) with linear function approximation under a general asynchronous update. We present finite sample bounds under both constant and diminishing step sizes. With a constant step-size, the iterates converge at an exponential rate to a small cylinder around the set of TD fixed points. With properly chosen diminishing step sizes, the mean-square distance of the iterates to the set of TD fixed points converges with an Õ ( 1 T ) rate, and this leads to
a sample complexity of Õ ( 1 2 ) . Our sample complexity bound also suggests that an intermediate value of λ yields the best performance. The dependence on the effective horizon plays a key role in the study of discounted-reward RL 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(λ) Analysis. A major challenge in the analysis is that the projected Bellman operator is not a contraction under any norm. Moreover, even though the projected Bellman equation can be written as a 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 to 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 a vector is defined to be the difference between the maximum and minimum element. Since the optimal action-value function, Q∗, is agnostic up to an additive constant, we show that, with at most O(1/ 2) 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 a contraction under any norm, it is known to be a contraction under the span seminorm. The span seminorm can be interpreted as the `∞-distance to the subspace spanned by the all-ones vector. Finite sample bounds for stochastic approximation of `∞-norm contractive operators were obtained in [18] by using generalized Moreau envelop as a smooth Lyapunov function. Here, we generalize this approach and introduce a new Lyapunov function to study span seminorm contractive operators. Our Lyapunov function is obtained by applying an infimal convolution with respect to an indicator function to the generalized Moreau envelop used in [18].

heading: 1.2 Related Literature
text: Average-Reward MDP. There is an extensive body of literature on average-reward MDPs. Several authors have made early contributions to average-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 of the MDP, and are also computationally intractable in large state spaces [25].
Average-Reward Policy Evaluation. Tsitsiklis and Van Roy [10] proved the asymptotic convergence of the average-reward TD(λ) with linear function approximation, and provided approximation error bounds. Yu and Bertsekas [26] proved the asymptotic convergence of the average-reward LSPE(λ), and provided the rate of convergence for constant step size. Both TD(λ) with linear function approximation and LSPE(λ) aim to solve the same projected Bellman equation. However, TD(λ) is based on stochastic approximation while LSPE(λ) 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 a 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-reward gradient
TD algorithms with linear function approximation [13]. Note that, [13] needed either the restrictive assumption aforementioned or the ridge regularization to 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 Qlearning 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 a 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 a reference function, which is needed in RVI Q-learning, and proved its asymptotic convergence with the techniques which are a slight generalization of those in [11]. To the best of our knowledge, our paper is the first work in the literature that studies the finite sample guarantees of a general average-reward Q-learning algorithm.
Stochastic Approximation. Many RL algorithms can be viewed through the lens of stochastic approximation (SA). There is 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 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 a 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 a 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] on regret guarantees, which is a 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].

heading: 2 The Average-Reward Problem Setting
text: We consider an infinite-horizon average-reward MDP described by (S,A,R, p), where S = {1, 2, · · · , |S|} is a finite state space,A = {1, 2, · · · , |A|} is a finite action space,R : S×A → [0, 1] is the reward function, and p : S × 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 t = 0, 1, 2, · · · , the agent is in a state St ∈ S and selects an action At ∈ A, then receives from the environment an immediate rewardR(St, At) and the next state St+1 which is a sample drawn from p(·|St, At). The average reward of a deterministic stationary policy µ : S → A starting from state s ∈ S is defined as
rµ(s) := lim inf T→∞
1 T E [ T−1∑ t=0 R(St, µ(St))|S0 = s ] . (2.1)
Let r∗(s) := supµ∈M r µ(s), where M is the set of deterministic stationary policies. A policy µ∗ ∈M is said to be optimal if it satisfies rµ∗(s) = r∗(s) for all s ∈ S.

heading: 3 Policy Evaluation Algorithm: TD Learning

heading: 3.1 Problem Formulation
text: We consider the problem of evaluating a given policy µ ∈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, µ(i)) for rewards, and P (i, j) := p(j|i, µ(i)) for transition probabilities. We make the following standard assumption to ensure the existence and uniqueness of a stationary distribution π := [π1, · · · , π|S|]>.
Assumption 1. The Markov chain associated with P is irreducible and aperiodic. It is a standard assumption in studying convergence of TD learning algorithms with linear function approximation [41, 10, 14] and guarantees that all states are visited an infinite number of times during an infinitely long trajectory.
Notice that π satisfies π>P = π>, with πi > 0 for all i ∈ S. Let Eπ[·] denote expectation with respect to π and define D = diag(π1, · · · , π|S|) ∈ R|S|×|S|. It is easy to see that 〈x, y〉D := x>Dy is a D-weighted inner product and we denote its induced norm by ‖x‖D := √ x>Dx.
Under Assumption 1, the average reward in (2.1) satisfies rµ(s) = r(µ) := π>R for all s ∈ S. A differential value function v : S → R for policy µ satisfies the Bellman equation Tv = v, where the Bellman operator T : R|S| → R|S| is defined by Tv := R− r(µ)e+ Pv. Here, e ∈ R|S| is the all-ones vector. Under Assumption 1, it is known that the set of differential value functions takes the form {vµ + ce|c ∈ R}, where vµ : S → R, known as the basic differential value function, is given by vµ := ∑∞ t=0 P
t (R− r(µ)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 Vθ(i) = φ(i)
>θ to differential value functions, where φ(i) := [φ1(i), · · · , φd(i)]> ∈ Rd is the feature vector for state i ∈ S and θ ∈ Rd is a tunable parameter vector. Here, {φk : S → R|k = 1, 2, · · · , d} is a set of d basis functions to be viewed as vectors of dimension |S|. With this notation, Vθ can be expressed compactly in the form Vθ = Φθ, where Φ is an |S|×dmatrix whose k-th column is φk. We assume that Φ has full column rank; that is, the basis functions {φk|k = 1, 2, · · · , d} are linearly independent. This results in no loss of generality because if some basis function φk is a linear combination of the others, it can be eliminated without changing the power of the approximation architecture. Additionally, we assume that ‖φ(i)‖2 ≤ 1 for all i ∈ S, which can be ensured through feature normalization.

heading: 3.2 Average-Reward TD(λ)
text: Algorithm 1: TD(λ) with linear function approximation Input : initial guess r̄0 and θ0, basis functions {φk}dk=1, step-size sequence {βt}t∈N and positive constant cα. Initialize: z−1 = 0, λ ∈ [0, 1). for t = 0, 1, . . . do
Observe tuple: Ot = (st,R(st), st+1) Get TD error: δt(θt) = R(st)− r̄t + φ(st+1)>θt − φ(st)>θt Update eligibility trace: zt = λzt−1 + φ(st) Update average-reward estimate: r̄t+1 = r̄t + cαβt(R(st)− r̄t) Update parameter vector: θt+1 = θt + βtδt(θt)zt
end
We study the average-reward TD learning with eligibility traces [10], denoted by TD(λ) and parameterized by λ ∈ [0, 1). We consider the Markov chain observation model, where the observed tuples used by TD(λ) are gathered from a single trajectory of the MRP. At every time step t, the algorithm observes one data tuple Ot := (st,R(st), st+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 θ is θt, and we have a scalar estimate r̄t of the average reward r(µ), we define the TD error δt(θt) corresponding to the transition from st to st+1 as δt(θt) := R(st)− r̄t + φ(st+1)>θt − φ(st)>θt. TD(λ) updates r̄t and θt as follows:
r̄t+1 = r̄t + αt(R(st)− r̄t) and θt+1 = θt + βtδt(θt)zt, (3.1) where αt and βt are scalar step sizes, and the vector zt := ∑t k=0 λ
t−kφ(sk) is called the eligibility trace.
In this work, we focus on the single time-scale variant of TD(λ) presented in Algorithm 1, that is, we assume that there exists a constant cα > 0 such that αt = cαβt for all t. In order to represent TD(λ) in a compact form, we construct a process Xt := (st, st+1, zt). It is easy to see that {Xt} is
a Markov chain with an infinite state space. If we let Θt := [ r̄t θt ] , the TD(λ) updates (3.1) can be expressed compactly as
Θt+1 = Θt + βt [ A(Xt)Θt + b(Xt) ] , (3.2)
where
A(Xt) = [ −cα 0 −zt zt ( φ(st+1) > − φ(st)> )] and b(Xt) = [cαR(st)R(st)zt ] .
Non-uniqueness of TD(λ) limit point. For any m = 0, 1, · · · , the m-step Bellman operator is given by
Tmv = m∑ t=0 P t (R− r(µ)e) + Pm+1v.
The asymptotic properties of TD(λ) are closely tied to the λ-weighted version of the m-step Bellman operator. Define the averaged Bellman operator
T (λ)v := (1− λ) ∞∑ m=0 λmTm+1v.
Note that the set of differential value functions is also the fixed points of T (λ); see Lemma 3 in [10] for a proof.
We denote by A := Eπ[A(Xt)] and b := Eπ[b(Xt)] the steady-state expectations of A(Xt) and b(Xt), respectively. Stochastic approximation theory [32] shows that the asymptotic behavior of the sequence {Θt} generated by (3.2) is closely linked with the corresponding ordinary differential
equation (ODE) Θ̇t = AΘt + b, and the limit of Θt, denoted by Θ∞ = [ r̄∞ θ∞ ] if exists, is an equilibrium point of the ODE, i.e.,
AΘ∞ + b = 0. (3.3)
Therefore, r̄∞ = r(µ), and θ∞ is a solution of the projected Bellman equation
Φθ = ΠD,WΦT (λ)Φθ, (3.4)
where ΠD,WΦ := Φ ( Φ>DΦ )−1 Φ>D is the projection matrix onto the column space WΦ := {Φθ|θ ∈ Rd} of Φ with respect to the norm ‖·‖D. It is worth noting that if e ∈WΦ, then ΠD,WΦT (λ) has multiple fixed points, since any scalar multiple of e when added to a fixed point of ΠD,WΦT (λ) would also be a fixed point. For example, in the tabular case where Φ = I , Eq. (3.4) would become θ = T (λ)θ, of which the set of differential value functions are solutions.

heading: 3.3 Finite-Time Bounds for Average-Reward TD(λ)
text: Before we present the finite-time bounds on the performance of TD(λ) 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 to obtain an upper bound on the mean-square error. We define the subspace SΦ,e as
SΦ,e := span ( {θ|Φθ = e} ) = { {0}, if e 6∈WΦ, {cθe|c ∈ R}, if e ∈WΦ and Φθe = e.
Let E be the orthogonal complement of SΦ,e. We can interpret E as the set of equivalent classes with the equivalence relation ∼ on Rd defined by θ1 ∼ θ2 if and only if θ1 − θ2 is in SΦ,e. The following lemma characterizes the set of TD(λ) fixed points; see Appendix A.1 for a proof. Lemma 1. Under Assumption 1, the fixed points of the projected Bellman equation (3.4) are
L := θ∗ + SΦ,e = { {θ∗}, if e 6∈WΦ, {θ∗ + cθe|c ∈ R}, if e ∈WΦ and Φθe = e,
where θ∗ ∈ E is a unique solution to the equation Φθ = ΠD,WΦ,ET (λ)Φθ. Here, ΠD,WΦ,E (·) is the projection operator onto the subspace WΦ,E := {Φθ|θ ∈ E} with respect to the norm ‖·‖D
Remark 1. In the case where e 6∈WΦ, the projected Bellman equation (3.4) has a unique fixed point θ∗. This is why prior work requires that e does not belong to the column space of Φ.
We consider the Lyapunov function Φ(r̄, θ) := (r̄ − r(µ))2 + ‖Π2,E (θ − θ∗)‖22. Here, Π2,E is the projection onto the subspace E with respect to the 2-norm ‖·‖2. Note that ‖Π2,E (θ − θ∗)‖ 2 2 measures the distance of θ to the set of TD(λ) fixed points. The following Lemma establishes that the matrix A in (3.3) is negative definite over the subspace R× E for a sufficiently large cα. The proof is presented in Appendix A.2. With this result, we can show that the Lyapunov function Φ(r̄, θ) has a one-time-step negative drift. Lemma 2. Under Assumption 1, we have
∆ := min ‖θ‖2=1,θ∈E
θ>Φ>D ( I − P (λ) ) Φθ > 0, (3.5)
where P (λ) = (1− λ) ∑∞ m=0 λ mPm+1. Furthermore, when cα ≥ ∆ + √ 1 ∆2(1−λ)4 − 1 (1−λ)2 , we have
min ‖Θ‖2=1,Θ∈R×E −Θ>AΘ ≥ ∆ 2 .
To handle the Markovian noise, we use the conditioning argument along with the geometric mixing of the underlying Markov chain {Xt}. Thus, we consider the following definition of the mixing time of a Markov chain. Definition 1. Given a positive constant , we define τ( ) ≥ 1 to be the mixing time of a Markov chain {Xt} such that
‖E [A(Xt)|X0]−A‖2 ≤ and ‖E [b(Xt)|X0]− b‖2 ≤ , for any X0 and t ≥ τ( )
The following lemma establishes that the expectations of A(Xt) and b(Xt) converge to their steadystate values at a geometric rate. See Lemma 6.7 in [42] for a proof. Lemma 3. Under Assumption 1, the Markov chain {Xt} has a geometric mixing time, i.e., there exists a constant K ≥ 1 such that given a small positive constant we have τ( ) ≤ K ln ( 1 ) .
We now state two finite-time bounds on the performance of TD(λ). Part (a) studies TD(λ) applied with sufficiently small constant step-size, which is common in practice. In this case, the iterates θt will never converge to any TD(λ) fixed point due to the noise variance, but our result shows that the expected distance of θt to the set of TD(λ) fixed points decreases at an exponential rate below some level that depends on the choice of step-size. Part (b) attains an Õ ( 1 T ) convergence rate to some TD(λ) fixed point with a carefully chosen decaying step-size sequence. Theorem 1. Consider iterates {(r̄t, θt)} generated by Algorithm 1 with Assumption 1 and
cα ≥ ∆ + √ 1 ∆2(1−λ)4 − 1 (1−λ)2 . Let ξ1 := ( 2 √ r̄20 + ‖θ0‖ 2 2 + √ r(µ) 2 + ‖θ∗‖22 + 1 )2 and
ξ2 := 228η 2 (√ r(µ) 2 + ‖θ∗‖22 + 1 )2 , where η := √ c2α + 5 (1−λ)2 .
(a) Let βt = β for all t, where positive constant β is properly chosen such that ∆β < 2 and βτ(β) ≤ min{ 14η , ∆ 228η2 }. Then, for all T ≥ τ(β), we have
E [ (r̄T − r(µ))2 + ‖Π2,E (θT − θ∗)‖22 ] ≤ ξ1 ( 1− ∆
2 β
)T−τ(β) + ξ2 βτ(β)
∆ .
(b) Let βt = c1t+c2 where positive constants c1 and c2 are properly chosen such that 2 < ∆c1 < 2c2 and there exists a smallest positive integer t∗ such that ∑t∗−1 k=0 βk ≤ 1 2η , and for all t ≥ t
∗,∑t−1 k=t−τ(βt) βk ≤ min{ 1 4η , ∆ 228η2 }. Then, for all T ≥ t ∗, we have
E [ (r̄T − r(µ))2 + ‖Π2,E (θT − θ∗)‖22 ] ≤ ξ1 ( t∗ + c2 T + c2 )∆c1 2 + 8eKc21ξ2 ∆c1 − 2 ln(T + c2)− ln(c1) T + c2 + 1 .
Therefore, with an appropriate decaying step sizes suggested in Theorem 1(b), the following sample complexity of Algorithm 1 can be obtained. Corollary 1. To find a pair (r̄, θ) with E [|r̄ − r(µ)|] ≤ and E [ ‖Π2,E (θ − θ∗)‖2 ] ≤ , Algorithm 1 requires at most the following number of samples:
Õ
( K log ( 1 ∆ ) ‖θ∗‖22
∆4(1− λ)4 2
) ,
where K is the mixing time constant defined in Lemma 3. Remark 2. Since ∆ defined in (3.5) is a non-decreasing function of λ, the sample complexity in Corollary 1 implies that the optimal λ should be neither too large nor too small.

heading: 3.4 Approximation Error
text: As we are satisfied with an approximation of any differential value function, we define the approximation error, infc∈R ‖Φθ∗ − (vµ + ce)‖D, as the infimum of the D-weighted Euclidean distance of Φθ∗ to the set of differential value functions. Following the similar arguments from the proof of Theorem 3 in [10], we obtain the following approximation error bound,
inf c∈R ‖Φθ∗ − (vµ + ce)‖D ≤ 1√ 1− c2λ inf θ∈Rd,c∈R ‖Φθ − (vµ + ce)‖D, (3.6)
where the constant cλ is in [0, 1) for any λ ∈ [0, 1) and goes to 0 as λ → 1. Note that the term infθ∈Rd,c∈R ‖Φθ − (vµ + ce)‖D is the minimal error possible given our 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 infc∈R ‖Φθ∗ − (vµ + ce)‖D = 0.
4 Control Algorithm: Q-learning

heading: 4.1 Problem Formulation
text: We consider the problem of finding an optimal policy µ∗ ∈ 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 a unique r∗ ∈ R such that r∗(s) = r∗ for all s ∈ S, and a unique Q∗ : S × A → R up to an additive constant, such that the following Bellman optimality equation holds for all state-action pairs (s, a) ∈ S ×A:
Q∗(s, a) = R(s, a) + ∑ s′∈S p(s ′|s, a) maxa′∈AQ∗(s′, a′)− r∗. (4.1)
The optimal policy µ∗ is then obtained by µ∗(s) := argmaxa∈AQ ∗(s, a). If we define Ē := {ce|c ∈ R} as the subspace spanned by the all-ones vector e ∈ R|S|×|A| and denote the Bellman operator H by
H(Q)(s, a) = R(s, a) + ∑ s′∈S p(s ′|s, a) maxa′∈AQ∗(s′, a′), ∀(s, a) ∈ S ×A,
then (4.1) can be rewritten as a set inclusion condition:
Q∗ −H(Q∗) ∈ Ē. (4.2)
Importantly, by observing that the operator H is indifferent to constant shifting, i.e., H(Q+ ce) = H(Q) + ce, we can view all Q constant shifts, QĒ := {Q+ ce : c ∈ R}, as an equivalent class and interpret (4.2) as a fixed-set equation:
Q∗Ē = H(Q ∗ Ē). (4.3)
Next we propose an SA algorithm to solve (4.3) by iteratively updating some “representative" of the underlying equivalent class.
Algorithm 2: J-step Synchronous Q-learning Input : initial guess Q0, step-size sequence {ηt}t∈N, offset function f : R|S|×|A| → R. for t = 0, 1, . . . do
Compute the Qt-improving policy µt(s) := arg maxaQt(s, a) for all s ∈ S. for (s, a) ∈ S ×A do
Sample s1 ∼ p(·|s, a), s2 ∼ p(·|s1, µt(s1)), . . . , sJ ∼ p(·|sJ−1, µt(sJ−1)). Compute Qt+1(s, a)← Qt(s, a) + ηt ( R(s, a) + ∑J−1 j=1 R(sj , µt(sj)) +Qt(sJ , µt(sJ))−Qt(s, a)− f(Qt) ) .
end end
4.2 Synchronous Q-learning
Given the sample Bellman operator Ĥ defined by
Ĥ(Q)(s, a) := R(s, a) + max a′∈A
Q(s′, a′), s′ ∼ p(·|s, a), ∀(s, a) ∈ S ×A,
an SA algorithm for solving (4.3) is
Qt+1 := Qt + ηt ( Ĥ(Qt)−Qt ) . (4.4)
It might be necessary, sometimes, to apply H to Q for J steps before updating Q. More specifically, if we denote by µQ(s) := arg maxaQ(s, a) the Q-improving policy, the J-step Bellman operator and the J-step fixed-set equation are
HJ(Q)(s, a) := R(s, a) + Es1∼P (·|s,a),...,sJ∼P (·|sJ−1,µQ(sJ−1)) [ R(s1, µQ(s 1)) + . . .+R(sJ−1, µQ(s J−1)) +Q(µJ , µQ(s J)) ] , (4.5)
HJ(Q∗Ē) = Q ∗ Ē . (4.6)
So the J-step SA algorithm is the same as (4.4) except for a J-step sample Bellman operator,
ĤJ(Q)(s, a) := R(s, a) +R(s1, µQ(s1)) + . . .+R(sJ−1, µQ(sJ−1)) +Q(µJ , µQ(sJ)),
where s1 ∼ p(·|s, a), . . . , sJ ∼ p(·|sJ−1, µQ(sJ−1)). The complete algorithm is presented in Algorithm 2. Remark 3. (1) The SA algorithm in (4.4) is a special case of Algorithm 2 with J = 1. (2) The solution to the J-step fixed-set equation (4.6) is the same for all J ≥ 1. (3) An extra offset function f(Q) is included to ensure numerical stability (see Section 2.2 in [11]). If J = 1 and the offset function f satisfies Assumption 2.2 in [11], Algorithm 2 recovers the RVI Q-learning algorithm.

heading: 4.3 Finite-Time Analysis
text: Now we seek to establish finite-time convergence guarantees of Algorithm 2. Since the Q-improving policy and its suboptimality gap are the same for any Q ∈ QĒ , we can measure Algorithm 2’s progress by
‖Q−Q∗‖α,sp := minc∈R ‖(Q−Q ∗)− ce)‖α , (4.7)
for some norm ‖·‖α. For example, the span seminorm is equivalent to ‖·‖∞,sp. Additionally, we need to make a span contraction assumption similar to Theorem 8.5.2 in [9]. Assumption 3. The J-step Bellman operator HJ is a span contraction for some J ≥ 1, i.e., there exists a γ ∈ [0, 1) such that for any Q1 and Q2 defined on S ×A,∥∥HJ(Q1)−HJ(Q2)∥∥∞,sp ≤ γ ‖Q1 −Q2‖∞,sp . Such an assumption is not restrictive. A lower bound for 1− γ 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, γ < 1 can be guaranteed for J = |S| if we apply the aperiodic transformation in Section 8.5.4 of [9] to ensure a non-zero probability of all states in a single recurrent class in |S| steps. We sketch the outline of our Lyaponuv convergence proof and leave the details to Appendix B. First, we construct a Lyaponov function. The key insight is that the span seminorm ‖·‖∞,sp can be interpreted as the infimal convolution of the `∞-norm ‖·‖∞ and the indicator function of Ē, i.e.,
‖x‖∞,sp = (‖·‖∞2δĒ)(x) := infy ‖x− y‖∞ + δĒ(y), ∀x, (4.8)
where δĒ(x) := {
0, x ∈ Ē, ∞, otherwise.
As illustrated by Lemma 4 in Appendix B.1, the inifimal convolution operation has many desirable properties. For example, it is commutative, associative, convexity-preserving and smoothnesspreserving. These nice properties allow us to design a Lyaponov function MĒ for the equivalent classes by tweaking the usual Lyaponov function M as follows,
MĒ(Q) := (M2δĒ) (Q). (4.9)
In particular, since Assumption 3 implies only span contraction, we utilize the smoothed Lyaponov function proposed in [18] for `∞-norm contraction, i.e., M(Q) := 12 (‖·‖ 2 ∞2 1 u ‖·‖ 2 p)(Q) with p := 4 log(|S||A|) and u := (1/2 + 1/(2γ))2 − 1. We show MĒ(·) is a uniform approximation of ‖·‖2∞,sp:
(1 + (1 + 1/γ)2/4 √ e)MĒ(Q) ≤ 12 ‖Q‖ 2 ∞,sp ≤ (1 + (1 + 1/γ) 2/4)MĒ(Q), ∀Q,
and it is smooth with respect to ‖·‖p,sp:
MĒ(Qt+1 −Q∗) ≤MĒ(Qt −Q∗) + 〈∇MĒ(Qt −Q∗), Qt+1 −Qt〉
+ 2 log(|S||A|)u ‖Qt+1 −Qt‖ 2 p,sp .
(4.10)
Next, since the span contraction assumption leads to a negative drift in (4.10) for some constant α2 defined in Appendix B.3,
E [〈∇MĒ(Qt −Q∗), Qt+1 −Qt〉] ≤MĒ(HJ(Qt)−Q∗)−MĒ(Qt −Q∗) ≤ −2α2MĒ(Qt −Q∗),
(4.11)
we can use the smoothness and uniform approximation properties ofMĒ to provide a recursive bound of Qt+1 for some α3 and α4 defined in Appendix B.3,
E[MĒ(Qt+1 −Q∗)] ≤ (1− 2α2ηt + α3η2t )MĒ(Qt −Q∗) + α4η2t . (4.12)
Clearly, by taking a small enough step size ηt, (4.12) implies the convergence of E [MĒ(Qt −Q∗)]. Now we can state a sample complexity upper bound for Algorithm 2 by choosing a specific step-size sequence.
Theorem 2. If {Qt} is generated by Algorithm 2 with a decaying step-size sequence
ηt = 4 1−γ 1 t+K , with K = max { 288 log(|S||A|) (1− γ)2 , 3 } ,
then for some universal constant C the following bound holds for all t ≥ 1 ,
E [ ‖Qt −Q∗‖2∞,sp ] ≤ C ( ‖Q0−Q∗‖2∞,sp(log |S||A|) 2 (1−γ)4t2 + (J2+‖Q∗‖2∞,sp) log(|S||A|) (1−γ)3t ) .
If instead a constant step size η ≤ (1−γ) 2
288 log(|S||A|) is employed, then
E [ ‖Qt −Q∗‖2∞,sp ] ≤ √ e(1− 1−γ2 η) t ‖Q0 −Q∗‖2∞,sp + 48(J2+‖Q∗‖2∞,sp) log(|S||A|) (1−γ)2 η.
In both cases, it takes
O
( (J2 + ‖Q∗‖2∞,sp)J |S||A| log(|S||A|)
(1− γ)3 2 ) samples to find a Qt with E [ ‖Qt −Q∗‖∞,sp ] ≤ . Taking into account ‖Q∗‖∞,sp ≤ J 1−γ from the span contraction assumption, the sample complexity can be simplified further to
Õ ( |S||A|J3 (1−γ)5 2 ) ,
which is similar to the sample complexity of γ-discounted Q-learning algorithm [18, 43].

heading: 5 Numerical Experiments
text: In this section we present empirical results of the average-reward TD(λ) with linear function approximation (i.e. Algorithm 1). In our simulation, we consider a randomly generated MRP with |S| = 100 states and a randomly generated feature matrix Φ with d = 20 features and e ∈WΦ. Experimental details and figures are provided in Appendix C. All the implementations 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 for 4 different θ0, and then plot E [ ‖Π2,E (θt − θ∗)‖2 ] and E [ (θt − θ∗)> θe‖θe‖2 ] as functions of the number of iterations t in Figure 1 and 2, respectively. Recall from Lemma 1 that {θ∗ + cθe|c ∈ R} is the set of TD limit points. We observe in Figure 1 that E [ ‖Π2,E (θt − θ∗)‖2 ] converges to 0 for all 4 initial points, which means that the iterates θt converge to some TD limit point regardless of θ0. Moreover, Figure 2 shows that E [ (θt − θ∗)> θe‖θe‖2 ] converges to different values for different initial points. This, combined with Figure 1, implies that the algorithm converges to different TD limit points, starting from different θ0.
We next numerically verify the finite-time error bounds of Algorithm 1 using decaying step sizes. In Figure 3, we plot E [ (r̄t − r∗)2 + ‖Π2,E (θt − θ∗)‖22 ] as a function of t for λ ∈ {0, 0.2, 0.4, 0.8}, where r∗ denotes the average-reward of the MRP. We see that the iterates {(r̄t, θt)} of the algorithm converge for all values of λ. To further verify the rate of convergence, we plot lnE [ (r̄t − r∗)2 + ‖Π2,E (θt − θ∗)‖22 ] as a function of ln t in Figure 4 for large t and the slopes of
these lines are provided in the legend. The plot shows E [ (r̄t − r∗)2 + ‖Π2,E (θt − θ∗)‖22 ] ≈ O ( 1 t ) asymptotically, which agrees with Theorem 1(b). In addition, we notice from Figure 3 and 4 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.

heading: 6 Conclusion
text: We establish the first finite sample convergence bounds of (i) average-reward TD(λ) with linear function approximation under Markovian observation noise, and (ii) average-reward tabular Qlearning 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, so we 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, it is unclear if such an assumption is necessary for establishing any finite-time convergence bound. Since our results are the first finite sample bounds, a 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.
®https://github.com/xiaojianzhang/Average-Reward-TD-Q-Learning

heading: Acknowledgment
text: This work was partially supported by an award from Raytheon Technologies and a seed grant from Georgia Institute of Technology.

Review summaries:
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.

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. 

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.  Previous 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.

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.