Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators
Year: 2021

Abstract:
In TD-learning, off-policy sampling is known to be more practical than on-policy sampling, and by decoupling learning from data collection, it enables data reuse. It is known that policy evaluation has the interpretation of solving a generalized Bellman equation. In this paper, we derive finite-sample bounds for any general off-policy TD-like stochastic approximation algorithm that solves for the fixedpoint of this generalized Bellman operator. Our key step is to show that the generalized Bellman operator is simultaneously a contraction mapping with respect to a weighted `p-norm for each p in [1,∞), with a common contraction factor. Off-policy TD-learning is known to suffer from high variance due to the product of importance sampling ratios. A number of algorithms (e.g. Q(λ), Tree-Backup(λ), Retrace(λ), and Q-trace) have been proposed in the literature to address this issue. Our results immediately imply finite-sample bounds of these algorithms. In particular, we provide first-known finite-sample guarantees for Q(λ), TreeBackup(λ), and Retrace(λ), and improve the best known bounds of Q-trace in [19]. Moreover, we show the bias-variance trade-offs in each of these algorithms.

heading: 1 Introduction
text: Reinforcement learning (RL) demonstrated its success in learning effective policies for a variety of decision making problems such as autonomous driving [25, 26], recommender systems [1, 41], and game-related problems [23, 27, 39]. In RL, there is an important sub-problem – called the policy evaluation problem – of estimating the expected long term reward of a given policy. Solving the policy evaluation problem is usually an itermediate step in many existing RL algorithms to ultimately find an optimal policy, such as approximate policy iteration and actor-critic framework.
The policy evaluation problem is usually solved with the TD-learning method [30]. A key ingredient in TD-learning is the policy used to collect samples (called the behavior policy). Ideally, we want to generate samples from the target policy whose value function we want to estimate, and this is called on-policy sampling. However, in many cases such on-policy sampling is not possible due to practical reasons [16, 40], and hence we need to work with historical data that is generated by a possibly different policy (i.e., off-policy sampling). Although off-policy sampling is more practical than on-policy sampling, it is more challenging to analyze and is known to have high variance [15], which is a fundamental difficulty in off-policy learning. To overcome this difficulty, many variants of off-policy TD-learning algorithms have been proposed in the literature, such as Qπ(λ) [17], Tree-Backup(λ) (henceforth denoted by TB(λ)) [24], Retrace(λ) [22], and Q-trace [19], etc.

heading: 1.1 Main Contributions
text: In this work, we establish finite-sample bounds of a general n-step off-policy TD-learning algorithm that also subsumes several algorithms presented in the literature. The key step is to show that such
35th Conference on Neural Information Processing Systems (NeurIPS 2021)
algorithm can be modeled as a Markovian stochastic approximation (SA) algorithm for solving a generalized Bellman equation. We present sufficient conditions under which the generalized Bellman operator is contractive with respect to a weighted `p-norm for every p ∈ [1,∞), with a uniform contraction factor for all p. Our result shows that the sample complexity scales as Õ( −2), where is the required accuracy. It also involves a factor that depends on the problem parameters, in particular, the generalized importance sampling ratios, and explicitly demonstrates the bias-variance trade-off.
Our result immediately gives finite-sample guarantees for variants of multi-step off-policy TDlearning algorithms including Qπ(λ), TB(λ), Retrace(λ), and Q-trace. For Qπ(λ), TB(λ), and Retrace(λ), we establish the first-known results in the literature, while for Q-trace, we improve the best known results in [19] in terms of the dependency on the size of the state-action space. The weighted `p-norm contraction property with a uniform contraction factor for all p ∈ [1,∞) is crucial for us to establish the improved sample complexity. Based on the finite-sample bounds, we show that all four algorithms overcome the high variance issue in Vanilla off-policy TD-learning, but their convergence rates are all affected to varying degrees.

heading: 1.2 Generalized Bellman Operator and Stochastic Approximation
text: In this section, we illustrate the interpretation of off-policy multi-step TD-learning as an SA algorithm for solving a generalized Bellman equation. Consider the policy evaluation problem where the goal is to estimate the state-action value function Qπ of a given policy π. In the simplest setting where TD(0) with on-policy sampling is employed, it is well known that the algorithm is an SA algorithm for solving the Bellman equationQ = Hπ(Q), whereHπ(·) is the Bellman operator. The generalized Bellman operator B(·) we consider in this paper is defined by:
B(Q) = T (H(Q)−Q) +Q, (1)
where T (·) and H(·) are two auxiliary operators. In the special case where T (·) = I(·) and H(·) = Hπ(·), the generalized Bellman operator B(·) reduces to the regular Bellman operatorHπ(·). Note that any fixed point ofH(·) is also a fixed point of B(·), as long as T (·) is such that T (0) = 0. Thus, the operatorH(·) controls the fixed-point of the generalized Bellman operator B(·), and as we will see later, the operator T (·) can be used to control its contraction properties. To further understand the operatorB(·), we demonstrate in the following that both on-policy n-step TD and TD(λ) can be viewed as SA algorithms for solving the generalized Bellman equation B(Q) = Q, with different auxiliary operators T (·) and H(·). On-policy n-step TD is designed to solve the n-step Bellman equation Q = Hnπ(Q), which can be explicitly written as Q = ∑n−1 i=0 (γPπ)
iR + (γPπ)
nQ. Here R is the reward vector, γ is the discount factor, and Pπ is the transition probability matrix under policy π. By reverse telescoping, the n-step Bellman equation is equivalent to Q =∑n−1 i=0 (γPπ) i(R + γPπQ − Q) + Q = T (Hπ(Q) − Q) + Q, where T (Q) = ∑n−1 i=0 (γPπ)
iQ. Similarly, one can formulate the TD(λ) Bellman equation in the form of B(Q) = Q, where T (Q) = (1− λ) ∑∞ i=0 λ i ∑i−1 j=0(γPπ) iQ andH(·) = Hπ(·).
In these examples, the operator T (·) determines the contraction factor of B(·) by controlling the degree of bootstrapping. In this work, we show that in addition to on-policy TD-learning, variants of off-policy TD-learning with multi-step bootstrapping and generalized importance sampling ratios can also be interpreted as SA algorithms for solving the generalized Bellman equation. Moreover, under some mild conditions, we show that the generalized Bellman operator B(·) is a contraction mapping with respect to some weighted `p-norm for any p ∈ [1,∞), with a common contraction factor. This enables us to establish finite-sample bounds of general multi-step off-policy TD-like algorithms.

heading: 1.3 Related Literature
text: The TD-learning method was first proposed in [30] for solving the policy evaluation problem. Since then, there is an increasing interest in theoretically understanding TD-learning and its variants.
On-Policy TD-Learning. The most basic TD-learning method is the TD(0) algorithm [30]. Later it was extended to using multi-step bootstrapping (i.e., the n-step TD-learning algorithm [11, 37, 38]), and using eligibility trace (i.e., the TD(λ) algorithm [28, 30]). The asymptotic convergence of TDlearning was established in [13, 18, 35]. As for finite-sample analysis, a unified Lyapunov approach is presented in [10]. To overcome the curse of dimensionality in RL, TD-learning is usually incorporated with function approximation in practice. In the basic setting where a linear parametric architecture is
used, the asymptotic convergence of TD-learning was established in [36], and finite-sample bounds in [5, 12, 29, 34]. Very recently, the convergence and finite-sample guarantee of TD-learning with neural network approximation were studied in [7, 8].
Off-Policy TD-Learning. In the off-policy setting, since the samples are not necessarily generated by the target policy, usually importance sampling ratios (or “generalized” importance sampling ratios) are introduced in the TD-learning algorithm. The resulting algorithms are Qπ(λ) [24], TB(λ) [17], Retrace(λ) [22], and Q-trace [19] (which is an extension of V -trace [14]), etc. The asymptotic convergence of these algorithms has been established in the papers in which they were proposed. To the best of our knowledge, finite-sample guarantees are established only for Q-trace and V -trace [9, 10, 19]. In the function approximation setting, TD-learning with off-policy sampling and function approximation is a typical example of the deadly triad [31], and can be unstable [2, 31]. To achieve convergence, one needs to significantly modify the original TD-learning algorithm, resulting in two time-scale algorithms such as GTD [21], TDC [32], and emphatic TD [33], etc.

heading: 1.4 Preliminaries
text: In this section, we cover the background of RL and the TD-learning method for solving the policy evaluation problem. The RL problem is usually modeled as a Markov decision process (MDP). In this work, we consider an MDP with a finite set of states S , a finite set of actionsA, a set of unknown action dependent transition probability matrices P = {Pa ∈ R|S|×|S| | a ∈ A}, an unknown reward functionR : S ×A 7→ [0, 1], and a discount factor γ ∈ (0, 1). In order for an MDP to progress, we must specify the policy of selecting actions based on the state of the environment. Specifically, a policy π is a mapping from the state-space to probability distributions supported on the action space, i.e., π : S 7→ ∆|A|. The state-action value function Qπ associated with a policy π is defined by Qπ(s, a) = Eπ[ ∑∞ k=0 γ
kR(Sk, Ak) | S0 = s,A0 = a] for all (s, a). The goal in policy evaluation is to estimate the state-action value function Qπ for a given policy π.
Since the transition probabilities as well as the reward function are unknown, such state-action value function cannot be directly computed. The TD-learning algorithm is designed to estimate Qπ using the SA method. Specifically, in TD-learning, we first collect a sequence of samples {(Sk, Ak)} from the model using some behavior policy πb. Then the value function Qπ is iteratively estimated using the samples {(Sk, Ak)}. When πb = π, the algorithm is called on-policy TD-learning, otherwise the algorithm is referred to as off-policy TD-learning.

heading: 2 Finite-Sample Analysis of General Off-Policy TD-Learning
text: In this section, we present our unified framework for finite-sample analysis of off-policy TD-learning algorithms using generalized importance sampling ratios and multi-step bootstrapping. The proofs of all technical results presented in this paper are provided in the Appendix.

heading: 2.1 A Generic Model for Multi-Step Off-Policy TD-Learning
text: Algorithm 1 presents our generic algorithm model. Due to off-policy sampling, the two functions c, ρ : S × A 7→ R+ are introduced in Algorithm 1 to serve as generalized importance sampling ratios in order to account for the discrepancy between the target policy π and the behavior policy πb. We denote cmax = maxs,a c(s, a) and ρmax = maxs,a ρ(s, a). We next show how Algorithm 1 captures variants of off-policy TD-learning algorithms in the literature by using different generalized importance sampling ratios c(·, ·) and ρ(·, ·). Vanilla IS. When c(s, a) = ρ(s, a) = π(a|s)/πb(a|s) for all (s, a), Algorithm 1 is the standard off-policy TD-learning with importance sampling [24]. We will refer to this algorithm as Vanilla IS. Although Vanilla IS was shown to converge to Qπ [24], since the product of importance sampling ratios ∏i j=k+1 π(Aj |Sj) πb(Aj |Sj) is not controlled in any way, it suffers the most from high variance.
The Qπ(λ) Algorithm. When c(s, a) = λ and ρ(s, a) = π(a|s)/πb(a|s), Algorithm 1 is the Qπ(λ) algorithm [17]. The Qπ(λ) algorithm overcomes the high variance issue in Vanilla IS by introducing the parameter λ. However, the algorithm converges only when λ is sufficiently small [22].
The TB(λ) Algorithm. When c(s, a) = λπ(a|s) and ρ(s, a) = π(a|s)/πb(a|s), we have the TB(λ) algorithm [24]. The TB(λ) algorithm also overcomes the high variance issue in Vanilla IS and is
Algorithm 1 A Generic Algorithm for Multi-Step Off-Policy TD-Learning 1: Input: K, {αk}, Q0, π, πb, generalized importance sampling ratios c, ρ : S × A 7→ R+, and
sample trajectory {(Sk, Ak)}0≤k≤K+n collected under the behavior policy πb. 2: for k = 0, 1, · · · ,K − 1 do 3: αk(s, a) = αkI{(s, a) = (Sk, Ak)} for all (s, a) 4: ∆(Si, Ai, Si+1, Ai+1, Qk) = R(Si, Ai)+γρ(Si+1, Ai+1)Qk(Si+1, Ai+1)−Qk(Si, Ai) for all i ∈ {k, k + 1, ..., k + n− 1}. 5: Qk+1(s, a) = Qk(s, a)+αk(s, a) ∑k+n−1 i=k γ i−k∏i j=k+1 c(Sj , Aj)∆(Si, Ai, Si+1, Ai+1, Qk) for all (s, a) 6: end for 7: Output: QK
guaranteed to converge to Qπ without needing any strong assumptions. However, as discussed in [22], the TB(λ) algorithm lacks sample efficiency as it does not effectively use the multi-step return.
The Retrace(λ) Algorithm. When c(s, a) = λmin(1, π(a|s)/πb(a|s)) and ρ(s, a) = π(a|s)/πb(a|s), we have the Retrace(λ) algorithm, which overcomes the high variance and converges to Qπ. The convergence rate of Retrace(λ) is empirically observed to be better than TB(λ) in [22].
The Q-trace Algorithm. When we choose c(s, a) = min(c̄, π(a|s)/πb(a|s)) and ρ(s, a) = min(ρ̄, π(a|s)/πb(a|s)), where ρ̄ ≥ c̄, Algorithm 1 is the Q-trace algorithm [19]. The Q-trace algorithm is an analog of the V -trace algorithm [14] in that Q-trace estimates the Q-function instead of the V -function. The two truncation levels c̄ and ρ̄ in these algorithms separately control the variance and the asymptotic bias in the algorithm respectively. Note that due to the truncation level ρ̄, the algorithm no longer converges to Qπ , but to a biased limit point, denoted by Qπ,ρ [19].
From now on, we focus on studying Algorithm 1. We make the following assumption about the behavior policy πb, which is fairly standard in off-policy TD-learning. Assumption 2.1. The behavior policy πb satisfies πb(a|s) > 0 for all (s, a). In addition, the Markov chain {Sk} induced by the behavior policy πb is irreducible and aperiodic.
Irreducibility and aperiodicity together imply that the Markov chain {Sk} has a unique stationary distribution, which we denote by κS ∈ ∆|S|. Moreover, the Markov chain {Sk} mixes geometrically fast in that there exist C > 0 and σ ∈ (0, 1) such that maxs∈S ‖P k(s, ·) − κS(·)‖TV ≤ Cσk for all k ≥ 0, where ‖ · ‖TV is the total variation distance [20]. Let κSA ∈ ∆|S||A| be such that κSA(s, a) = κS(s)πb(a|s) for all (s, a). Note that κSA ∈ ∆|S||A| is the stationary distribution of the Markov chain {(Sk, Ak)} under the behavior policy πb. Let KS = diag(κS) ∈ R|S|×|S|, and let KSA = diag(κSA) ∈ R|S||A|×|S||A|. Denote the minimal (maximal) diagonal entries of KS and KSA by KS,min (KS,max) and KSA,min (KS,max) respectively.

heading: 2.2 Identifying the Generalized Bellman Operator
text: In this section, we identify the generalized Bellman equation which Algorithm 1 is trying to solve, and also the corresponding generalized Bellman operator and its asynchronous variant. Let Tc,Hρ : R|S||A| 7→ R|S||A| be two operators defined by
[Tc(Q)](s, a) = n−1∑ i=0 γiEπb [ i∏ j=1 c(Sj , Aj)Q(Si, Ai) | S0 = s,A0 = a], and
[Hρ(Q)](s, a) = R(s, a) + γEπb [ρ(Sk+1, Ak+1)Q(Sk+1, Ak+1) | Sk = s,Ak = a] for all (s, a). Note that the operator Tc(·) depends on the generalized importance sampling ratio c(·, ·), while the operatorHρ(·) depends on the generalized importance sampling ratio ρ(·, ·). With Tc(·) andHρ(·) defined above, Algorithm 1 can be viewed as an asynchronous SA algorithm for solving the generalized Bellman equation Bc,ρ(Q) = Q, where the generalized Bellman operator Bc,ρ(·) is defined by Bc,ρ(Q) = Tc(Hρ(Q)−Q) +Q. Since Algorithm 1 performs asynchronous update, using the terminology in [10], we further define the asynchronous variant B̃c,ρ(·) of the generalized Bellman operator Bc,ρ(·) by
B̃c,ρ(Q) := KSABc,ρ(Q) + (I −KSA)Q = KSATc(Hρ(Q)−Q) +Q. (2)
Each component of the asynchronous generalized Bellman operator B̃c,ρ(·) can be thought of as a convex combination with identity, where the weights are the stationary probabilities of visiting stateaction pairs. This captures the fact that when performing asynchronous update, the corresponding component is updated only when the state-action pair is visited. It is clear from its definition that B̃c,ρ(·) has the same fixed-points as Bc,ρ(·) (provided that they exist). See [10] for a more detailed explanation about asynchronous Bellman operators.
Under some mild conditions on the generalized importance sampling ratios c(·, ·) and ρ(·, ·), we will show in the next section that both the asynchronous generalized Bellman operator B̃c,ρ(·) and the operatorHρ(·) are contraction mappings. Therefore, since Tc(0) = 0, the operatorsHρ(·), Bc,ρ(·), B̃c,ρ(·) all share the same unique fixed-point. Since the fixed-point of the operator Hρ(·) depends only on the generalized importance sampling ratio ρ(·, ·), but not on c(·, ·), we can flexibly choose c(·, ·) to control the variance while maintaining the fixed-point of the operator B̃c,ρ(·). As we will see later, this is the key property used in designing variants of variance reduced n-step off-policy TD-learning algorithms such as Qπ(λ), TB(λ), and Retrace(λ).

heading: 2.3 Establishing the Contraction Property
text: In this section, we study the fixed-point and the contraction property of the asynchronous generalized Bellman operator B̃c,ρ(·). We begin by introducing some notation. Let Dc, Dρ ∈ R|S||A|×|S||A| be two diagonal matrices such that Dc((s, a), (s, a)) = ∑ a′∈A πb(a
′|s)c(s, a′) and Dρ((s, a), (s, a)) = ∑ a′∈A πb(a
′|s)ρ(s, a′) for all (s, a). We denote Dc,min (Dc,max) and Dρ,min (Dρ,max) as the minimal (maximal) diagonal entries of the matrices Dc and Dρ respectively.
In view of the definition of B̃c,ρ(·) in Eq. (2), any fixed-point ofHρ(·) must also be a fixed-point of B̃c,ρ(·). We first study the fixed point ofHρ(·) by establishing its contraction property. Proposition 2.1. Suppose that Dρ,max < 1/γ. Then the operator Hρ(·) is a contraction mapping with respect to the `∞-norm, with contraction factor γDρ,max. In this case, the fixed-point Qπ,ρ of Hρ(·) satisfies the following two inequalities: (1) ‖Qπ − Qπ,ρ‖∞ ≤ γmaxs∈S ∑ a∈A |π(a|s)−πb(a|s)ρ(s,a)|
(1−γ)(1−γDρ,max) , and (2) ‖Q π,ρ‖∞ ≤ 11−γDρ,max .
Observe from Proposition 2.1 (1) that when ρ(s, a) = π(a|s)/πb(a|s), which is the case for Qπ(λ), TB(λ), and Retrace(λ), the unique fixed-point Qπ,ρ is exactly the target value function Qπ. This agrees with the definition of the operator Hρ(·) in that it reduces to the regular Bellman operator Hπ(·) when ρ(s, a) = π(a|s)/πb(a|s) for all (s, a). If ρ(s, a) 6= π(a|s)/πb(a|s) for some (s, a), then in general the fixed-point ofHρ(·) is different from Qπ . See Appendix A.2 for more details. In that case, Proposition 2.1 provides an error bound on the difference between the potentially biased limit Qπ,ρ and Qπ . Such error bound will be useful for us to study the Q-trace algorithm in Section 3. Proposition 2.1 (2) can be viewed as an analog to the inequality that ‖Qπ‖∞ ≤ 1/(1− γ) for any policy π. SinceHρ(·) is no longer the Bellman operatorHπ(·), the corresponding upper bound on the size of its fixed-point Qπ,ρ also changes.
Note that Proposition 2.1 guarantees the existence and uniqueness of the fixed-point of the operator Hρ(·), hence also ensures the existence of fixed-points of the asynchronous generalized Bellman operator B̃c,ρ(·). To further guarantee the uniqueness of the fixed-point of B̃c,ρ(·), we establish its contraction property. We begin with the following definition. Definition 2.1. Let {µi}1≤i≤d be such that µi > 0 for all i. Then for any x ∈ Rd, the weighted `p-norm (p ∈ [1,∞)) of x with weights {µi} is defined by ‖x‖µ,p = ( ∑ i µi|xi|p)1/p.
We next establish the contraction property of the operator B̃c,ρ(·) in the following theorem. Let ω = KSA,minf(γDc,min)(1 − γDρ,max), where the function f : R 7→ R is defined by f(x) = n when x = 1, and f(x) = 1−x n
1−x when x 6= 1. Theorem 2.1. Suppose c(s, a) ≤ ρ(s, a) for all (s, a) and Dρ,max < 1/γ. Then we have the following results: (1) For any θ ∈ (0, 1), there exists a weight vector µ ∈ ∆|S||A| satisfying µ(s, a) ≥ ω(1−θ)(1−θω)|S||A| for all (s, a) such that the operator B̃c,ρ(·) is a contraction mapping with respect to ‖ · ‖µ,p for any p ∈ [1,∞), with contraction factor γc = (1−ω)1−1/p(1− θω)1/p, (2) The operator B̃c,ρ(·) is a contraction mapping with respect to ‖ · ‖∞, with contraction factor γc = 1− ω.
Consider Theorem 2.1 (1). Observe that we can further upper bound γc = (1− ω)1−1/p(1− θω)1/p by 1 − θω, which is independent of p and is the uniform contraction factor we are going to use. Theorem 2.1 (2) can be viewed as an extension of Theorem 2.1 because limp→∞ ‖x‖µ,p = ‖x‖∞ for any x ∈ Rd and weight vector µ, and limp→∞(1− ω)1−1/p(1− θω)1/p = 1− ω. Theorem 2.1 is the key result for our finite-sample analysis, and we present its proof in the next section. The weighted `p-norm (especially the weighted `2-norm) contraction property we established for the operator B̃c,ρ(·) has a far-reaching impact even beyond the finite-sample analysis of tabular RL in this paper. Specifically, recall that the key property used for establishing the convergence and finite-sample bound of on-policy TD-learning with linear function approximation in the seminal work [36] is that the corresponding Bellman operator is a contraction mapping not only with respect to the `∞-norm, but also with respect to a weighted `2-norm. We establish the same property in the off-policy setting, and hence lay down the foundation for extending our results to the function approximation setting. This is an immediate future research direction.

heading: 2.4 Proof of Theorem 2.1
text: We begin by explicitly computing the asynchronous generalized Bellman operator B̃c,ρ(·). Let πc and πρ be two policies defined by πc(a|s) = πb(a|s)c(s,a)Dc((s,a),(s,a)) and πρ(a|s) = πb(a|s)ρ(s,a) Dρ((s,a),(s,a)) for all (s, a). Let R ∈ R|S||A| be the reward vector defined by R(s, a) = R(s, a) for all (s, a). For any policy π′, let Pπ′ be the transition probability matrix of the Markov chain {(Sk, Ak)} under π′, i.e., Pπ′((s, a), (s ′, a′)) = Pa(s, s ′)π′(a′|s′) for all state-action pairs (s, a) and (s′, a′).
Proposition 2.2. The operator B̃c,ρ(·) is explicitly given by B̃c,ρ(Q) = AQ + b, where A = I −KSA ∑n−1 i=0 (γPπcDc) i(I − γPπρDρ) and b = KSA ∑n−1 i=0 (γPπcDc) iR.
In light of Proposition 2.2, to prove Theorem 2.1, it is enough to study the matrix A. To proceed, we require the following definition. Definition 2.2. Given β ∈ [0, 1], a matrix M ∈ Rd×d is called a substochastic matrix with modulus β if and only if Mij ≥ 0 for all i, j and ∑ jMij ≤ 1− β for all i.
Remark. Note that for any non-negative matrix M , we have ‖M‖∞ = maxi ∑ jMij . Therefore, a matrix M being a substochastic matrix with modulus β automatically implies that ‖M‖∞ ≤ 1− β.
We next show in the following two propositions that (1) the matrix A given in Proposition 2.2 is a substochastic matrix with modulus ω, and (2) for any substochastic matrix M with a positive modulus, there exist weights {µi} such that the induced matrix norm ‖M‖µ,p is strictly less than 1. These two results together immediately imply Theorem 2.1. Proposition 2.3. Suppose that c(s, a) ≤ ρ(s, a) for all (s, a) and Dρ,max < 1/γ. Then the matrix A given in Proposition 2.2 is a substochastic matrix with modulus ω.
The condition c(s, a) ≤ ρ(s, a) ensures that the matrixA is non-negative, and the conditionDρ,max < 1/γ ensures that the each row of the matrix A sums up to at most 1 − ω. Together they imply the substochasticity of A. The modulus ω is an important parameter for our finite-sample analysis. In view of Theorem 2.1, we see that large modulus gives smaller (or better) contraction factor of B̃c,ρ(·). Proposition 2.4. For any substochastic matrix M ∈ Rd×d with a positive modulus β ∈ (0, 1), for any θ ∈ (0, 1), there exists a weight vector µ ∈ ∆d satisfying µi ≥ β(1−θ)(1−θβ)d for all i such that ‖M‖µ,p ≤ (1− β)1−1/p(1− θβ)1/p for any p ∈ [1,∞). Furthermore, if M is irreducible 1, then we can choose θ = 1.
The result of Proposition 2.4 further implies ‖M‖µ,p ≤ 1− θβ, which is independent of the choice of p. This implies that B̃c,ρ(·) is a uniform contraction mapping with respect to ‖ · ‖µ,p for all p ≥ 1. In general, for different p and p′, an operator being a ‖ · ‖p-norm contraction does not imply being a ‖ · ‖p′ -norm contraction. The reason that we have such a strong uniform contractive result is that the operator B̃c,ρ(·) has a linear structure, and involves a substochastic matrix. Note that Proposition 2.4 introduces the tunable parameter θ. It is clear that large θ gives better contraction factor of B̃c,ρ(·) but worse lower bound on the entries of the weight vector µ. In
1A non-negative matrix is irreducible if and only if its associated graph is strongly connected [4].
general, when M is not irreducible, we cannot hope to choose a weight vector µ ∈ ∆d with positive components and obtain ‖M‖µ,p ≤ 1 − ω. To see this, consider the example where M = (1−ω)[0,0, · · · ,1], which is clearly a substochastic matrix with modulus ω, but is not an irreducible matrix. For any weight vector µ ∈ ∆d, we have ‖M‖µ,p = (1 − ω) maxx∈Rd:‖x‖µ,p=1 |xd| = (1− ω)/µ1/pd > 1− ω. However, by choosing µd close to unity, we can get ‖M‖µ,p arbitrarily close to 1− ω. This is analogous to choosing θ close to one in Proposition 2.4. Since Proposition 2.4 is the major result for proving Theorem 2.1, we provide its proof sketch in Section 4.

heading: 2.5 Finite-Sample Convergence Guarantees
text: In light of Theorem 2.1, Algorithm 1 is a Markovian SA algorithm for solving a fixed-point equation B̃c,ρ(Q) = Q, where the fixed-point operator B̃c,ρ(·) is a contraction mapping. Therefore, to establish the finite-sample bounds, we use a Lyapunov drift argument where we choose W (Q) = ‖Q−Qπ,ρ‖2µ,p as the Lyapunov function. This leads to a finite-sample bound on E[‖Qk−Qπ,ρ‖2µ,p]. However, since µ is unknown, to make the finite-sample bound independent of µ, we use the lower bound on the components of µ provided in Theorem 2.1, and also tune the parameters p and θ to obtain a finite-sample bound on E[‖Qk − Qπ,ρ‖2∞]. The fact that we have a uniform contraction factor 1− θω (cf. Theorem 2.1) plays an important role in such tuning process. To present the results, we need to introduce more notation. For any δ > 0, define tδ(MCS) as the mixing time of the Markov chain {Sk} (induced by πb) with precision δ, i.e., tδ(MCS) = min{k ≥ 0 : maxs∈S ‖P k(s, ·) − κS(·)‖TV ≤ δ}. Under Assumption 2.1, one can easily verify that tδ(MCS) ≤ L(log(1/δ) + 1) for some constant L > 0, which depends only on C and δ. Let τδ,n = tδ(MCS) + n+ 1. The parameters c1, c2 and c3 used in stating the following theorem are numerical constants, and will be explicitly given in the Appendix. For ease of exposition, we here only present the finite-sample bound for using constant stepsize. Theorem 2.2. Consider {Qk} of Algorithm 1. Suppose that: (1) Assumptions 2.1 is satisfied, (2) c(s, a) ≤ ρ(s, a) for all (s, a) and Dρ,max < 1/γ, and (3) the constant stepsize α is chosen such that ατα,n ≤ c1ωlog(2|S||A|/ω)f(γcmax)2(γρmax+1)2 . Then we have for all k ≥ τα,n:
E[‖Qk−Qπ,ρ‖2∞]≤ζ1 (
1−ωα 2
)k−τα,n + ζ2 f(γcmax) 2(γρmax + 1)
2 log(2|S||A|/ω) ω ατα,n, (3)
where ζ1 = c2(‖Q0 −Qπ,ρ‖∞ + ‖Q0‖∞ + 1)2, and ζ2 = c3(3‖Qπ,ρ‖∞ + 1)2.
Theorem 2.2 enables one to design a wide class of off-policy TD variants with provable finite-sample guarantees by choosing appropriate generalized importance sampling ratios c(·, ·) and ρ(·, ·). The first term on the RHS of Eq. (3) is usually called the bias in SA literature [6], and it goes to zero at a geometric rate. The second term on the RHS of Eq. (3) stands for the variance in the iterates, and it is a constant proportional to ατα,n. To see more explicitly the bias-variance trade-off, we derive the sample complexity of Algorithm 1 in the following. Corollary 2.2.1. For an accuracy > 0, to obtain E[‖Qk −Qπ,ρ‖∞] ≤ , the sample complexity is
O ( log2(1/ )
2 ) ︸ ︷︷ ︸
T1
Õ ( 1
ω2 ) ︸ ︷︷ ︸
T2
Õ ( nf(γcmax) 2(γρmax + 1) 2
(1− γDρ,max)2 ) ︸ ︷︷ ︸
T3
. (4)
In Corollary 2.2.1, the Õ( −2) dependence on the accuracy is the same as n-step TD-learning in the on-policy setting [10], and is in general not improvable. The term T2 can be equivalently written as Õ(1/(1 − Contraction factor)2), hence capturing the impact from the contraction factor. This agrees with our intuition that smaller contraction factor leads to better sample complexity. The term T3 arises because of the variance term on the RHS of Eq. (3). The linear dependence on n is due to using n-step bootstrapping. By optimizing the sample complexity in terms of n, we have noptimal ∼ 1/ log(1/(γDc,min)). This is analogous to the optimal n in the on-policy setting, which is 1/ log(1/γ) [10]. The additional Dc,min factor arises because of using off-policy learning. The rest of parameters in T3 are determined by the choice of the generalized importance sampling ratios c(·, ·) and ρ(·, ·). It is clear that smaller cmax and ρmax lead to smaller variance. As we will see later, this is the reason for the variance reduction of various off-policy TD-learning algorithms in the literature. In light of the previous analysis, the bias-variance trade-off in general off-policy multi-step TD-learning algorithm 1 is intuitively of the form Õ ( Variance
(1− Contraction factor)2
) .

heading: 3 Application to Various Off-Policy TD-Learning Algorithms
text: In this section, we apply Theorem 2.2 to various off-policy n-step TD-learning algorithms in the literature. We begin by introducing some notation. Let πmax (πmin) and πb,max (πb,min) be the maximal (minimal) entry of the target policy π and the behavior policy πb respectively. Let rmax = maxs,a(π(a|s)/πb(a|s)) (rmin = mins,a(π(a|s)/πb(a|s))) be the maximum (minimum) ratio between π and πb. We will overload the notation of ζ1 and ζ2 from Theorem 2.2. Note that Qπ,ρ = Qπ in Qπ(λ), TB(λ), and Retrace(λ), but Qπ,ρ 6= Qπ in Q-trace.

heading: 3.1 Finite-Sample Analysis of Vanilla IS
text: We first present the sample complexity bound of the Vanilla IS algorithm, where c(s, a) = ρ(s, a) = π(a|s)/πb(a|s) for all (s, a). Theorem 3.1. Consider Algorithm 1 with Vanilla IS update, where we note that cmax = ρmax = rmax, Dc = Dρ = I , and ω = KSA,min(1 − γn). Suppose that Assumption 2.1 is satisfied. Then, to achieve -accuracy, the sample complexity is O ( log2(1/ )
2
) Õ (
1 ω2
) Õ ( n((γrmax) n+1)2
(1−γ)2
) .
In the special case where π = πb (i.e., on-policy n-step TD), the sample complexity bound reduces to Õ
( n log2(1/ )
2K2SA,min(1−γn)2(1−γ)2
) , which is comparable to the results in [10]. See Appendix C.2 for
more details. In the off-policy setting, note that the factor ((γrmax)n + 1)2 appears in the sample complexity. When γrmax > 1 (which can usually happen), the sample complexity bound involves an exponential factor (γrmax)n. The reason is that the product of importance sampling ratios c(·, ·) are not at all controlled by any means in Vanilla IS. Therefore, the variance can be very large. On the other hand, since the importance sampling ratios are not modified, Vanilla IS effectively uses the full n-step return. As a result, the parameter ω = KSA,min(1− γn) within Vanilla IS is the largest (best) among all the algorithms we study.

heading: 3.1.1 Finite-Sample Analysis of Qπ(λ)
text: In this section, we present the sample complexity of the Qπ(λ) algorithm, where c(s, a) = λ and ρ(s, a) = π(a|s)/πb(a|s) for all (s, a). Theorem 3.2. Consider Algorithm 1 with Qπ(λ) update, where we note that cmax = λ, ρmax = rmax, Dc = λI , Dρ = I , and w = KSA,minf(γλ)(1 − γ). Suppose that Assumption 2.1 is satisfied, and λ ≤ rmin. Then, to achieve -accuracy, the sample complexity is O ( log2(1/ ) 2 ) Õ ( 1 ω2 ) Õ ( nf(γλ)2(γrmax+1) 2 (1−γ)2 ) .
To see how Qπ(λ) overcomes the high variance issue in Vanilla IS, observe that since γλ ≤ γrmin ≤ γ < 1, we have f2(γλ) ≤ 1/(1− γλ)2. Therefore, by replacing c(s, a) = π(a|s)/πb(a|s) in Vanilla IS with a properly chosen constant λ, Qπ(λ) algorithm successfully avoids an exponential large factor in the sample complexity. However, choosing a small λ to control the variance has a side effect on the contraction factor. Intuitively, when λ is small, Qπ(λ) does not effectively use the n-step return. Hence the parameter ω in Qπ(λ) is less (worse) than the one in Vanilla IS.

heading: 3.1.2 Finite-Sample Analysis of TB(λ)
text: In this section, we present the sample complexity of the TB(λ) algorithm, where c(s, a) = λπ(a|s) and ρ(s, a) = π(a|s)/πb(a|s) for all (s, a). Theorem 3.3. Consider Algorithm 1 with TB(λ) update, where we note that cmax = λπmax, ρmax = rmax,Dc(s, a) = λ ∑ a πb(a|s)π(a|s),Dρ(s, a) = 1, and ω = KSA,minf(γDc,min)(1−γ). Suppose that Assumption 2.1 is satisfied, and λ ≤ 1/πb,max. Then, to achieve -accuracy, the sample complexity is O ( log2(1/ )
2
) Õ (
1 ω2
) Õ ( nf(γλπmax) 2(γrmax+1) 2
(1−γ)2
) .
Suppose we further choose λ < 1/(γπmax), the TB(λ) algorithm also overcomes the high variance issue in Vanilla IS because f(γλπmax) ≤ 1/(1− γλπmax), which does not involve any exponential large factor. When compared to Qπ(λ), an advantage of TB(λ) is that the constraint on λ is much relaxed. However, the same side effect on the contraction factor is also present here. To see this, since Dc,min = λmins,a ∑ a πb(a|s)π(a|s) ≤ 1, the TB(λ) algorithm does not effectively use the n-step return, hence the parameter ω in TB(λ) is less (worse) than the one in Vanilla IS.

heading: 3.1.3 Finite-Sample Analysis of Retrace(λ)
text: In this section, we present the sample complexity of the Retrace(λ) algorithm, where c(s, a) = λmin(1, π(a|s)/πb(a|s)) and ρ(s, a) = π(a|s)/πb(a|s) for all (s, a). Theorem 3.4. Consider Algorithm 1 with Retrace(λ) update, where we note that cmax = λ, ρmax = rmax, Dc(s, a) = λ ∑ a min(πb(a|s), π(a|s)), Dρ(s, a) = 1, and ω = KSA,minf(γDc,min)(1− γ). Suppose that Assumption 2.1 is satisfied, and λ ≤ 1. Then, to achieve -accuracy, the sample complexity is O ( log2(1/ )
2
) Õ (
1 ω2
) Õ ( nf(γλ)2(γrmax+1) 2
(1−γ)2
) .
The Retrace(λ) algorithm overcomes the high variance issue in Vanilla IS by truncating the importance sampling ratio at 1, which prevents an exponential large factor in the variance term. In addition, it does not require choosing λ to be extremely small as required in Qπ(λ). As for the compromise in the contraction factor, note that min(1, π(a|s)/πb(a|s)) ≥ π(a|s), which implies that Dc(s, a) (and hence Dc,min) is larger in the Retrace(λ) algorithm than the TB(λ) algorithm. As a result, Retrace(λ) does not truncate the n-step return as heavy as TB(λ), and hence the parameter ω is larger (better) in Retrace(λ) than in TB(λ).
3.1.4 Finite-Sample Analysis of Q-Trace Lastly, we present the sample complexity of the Q-trace algorithm, where c(s, a) = min(c̄, π(a|s)/πb(a|s)) and ρ(s, a) = min(ρ̄, π(a|s)/πb(a|s)) for all (s, a). Theorem 3.5. Consider Algorithm 1 with Q-trace update, where we note that cmax = c̄, ρmax = ρ̄, Dc(s, a) = ∑ a min(c̄πb(a|s), π(a|s)), Dρ(s, a) = ∑ a min(ρ̄πb(a|s), π(a|s)), and ω = KSA,minf(γDc,min)(1− γDρ,max). Suppose that Assumption 2.1 is satisfied, and c̄ ≤ ρ̄. Then, to achieve -accuracy, the sample complexity is O ( log2(1/ )
2
) Õ (
1 ω2
) Õ ( nf(γc̄)2(γρ̄+1)2
(1−γDρ,max)2
) .
To avoid an exponential large variance, in view of the term f(γc̄) in our bound, we need to choose c̄ ≤ 1/γ. The major difference between Q-trace and Retrace(λ) is that the importance sampling ratio ρ(·, ·) inside the temporal difference (line 4 of Algorithm 1) also involves a truncation. As shown in Section 2.3, due to introducing the truncation level ρ̄, the algorithm converges to a biased limit Qπ,ρ instead of Qπ . Such truncation bias can be controlled using Proposition 2.1. These observations agree with the results [19], where the finite-sample bounds of Q-trace were first established.
Compared to [19], we have an improved sample complexity. Specifically, the result in [19] implies a sample complexity of Õ( log 2(1/ )nf(γc̄)2(γρ̄+1)2
2ω3(1−γDρ,max)2 ), which has an additional factor of ω −1. Since
ω−1 ∝ K−1SA,min ≥ |S||A|, our result improves the dependency on the size of the state-action space by a factor of at least |S||A| compared to [19]. Similarly, since the V -trace algorithm [14] is an analog of the Q-trace algorithm, we can also improve the sample complexity for V -trace in [10].
In addition to analyzing existing algorithms, observe that our results, especially Theorem 2.2, provide sufficient conditions under which Algorithm 1 has provable finite-sample guarantees, and hence enable us to design new algorithms. As an example, in light of the Retrace(λ) algorithm and the Qtrace algorithm, one can take advantage of both algorithms to let c(s, a) = λc min(c̄, π(a|s)/πb(a|s)) and ρ(s, a) = λρ min(ρ̄, π(a|s)/πb(a|s)), where λc, λρ, c̄, and ρ̄ are tunable parameters. As long as λcc̄ ≤ λρρ̄ < 1/γ, Theorem 2.2 is applicable and hence finite-sample convergence is guaranteed. To avoid an exponentially large variance, we choose λcc̄ ≤ 1/γ so that there are no exponentially large terms in the term T3 of sample complexity bound. After that, we can tune the rest of the parameters to further optimize the performance of the algorithm.
Sample Complexity Comparison. Now that we have derived the sample complexity bounds of various off-policy n-step TD-learning algorithms, we summarize them in the following table. For ease of exposition, we omit the common factor log2(1/ )/( 2K2SA,min) when presenting the sample complexity, and use a ∧ b (a ∨ b) to denote the minimum (maximum) of two real numbers a and b. In view of Table 1, when rmax < 1/γ, which indicates that the target policy π and the behavior policy πb are relatively close to each other, Vanilla IS has the best performance since it has the best contraction factor, and the cumulative product of the generalized importance sampling ratios does not result in exponentially large variance. When rmax > 1/γ, then Vanilla IS can potentially have exponentially large variance, while other four algorithms do not. In this case, among Qπ(λ), TB(λ), and Retrace(λ), Qπ(λ) has the best sample complexity bound. However, we need to point out that
the requirement λ ≤ rmin for Qπ(λ) is most restrictive, and the algorithm can easily diverge when this requirement is not satisfied, as evidenced by the numerical experiments presented in [22]. As for the Q-trace algorithm, although rigorously speaking it is not directly comparable with the other algorithms as it converges to a biased limit point, it is clear that using truncated importance sampling ratio for ρ(·, ·) can further reduce the sample complexity. We want to mention that our comparison is based on the upper bounds we derived for the sample complexity, which may not be tight. To complete the story, one should also derive lower bounds on the sample complexity, which is an interesting future direction. Nevertheless, our comparison provides insight into the behavior of off-policy n-step TD-learning algorithms,

heading: 4 Proof sketch of Proposition 2.4
text: The idea is to construct a stochastic matrix M ′′ such that: (1) M ′′ dominates M in the sense that M ′′ij ≥Mij for all i, j, and (2) the Markov chain associated with M ′′ is irreducible, hence admits a unique stationary distribution µ > 0. Using µ as weights and we have the desired result. The detailed analysis is presented in Appendix A.5. We here present the construction of the stochastic matrix M ′′.
First of all, consider the special case where M itself is irreducible. Then we first scale up M by a factor of 1/(1− ω) to obtain M ′ = M1−ω , which is clearly a substochastic matrix, with modulus zero. Hence there exists a stochastic matrix M ′′ that dominates M ′ (and also M ). Moreover, since M ′′ is also irreducible, its associated Markov chain has a unique stationary distribution µ. This is equivalent to choosing θ = 1 in Proposition 2.4. In fact, the matrix M being irreducible is only a sufficient condition to choose θ = 1. What we need is the existence of a strictly positive stationary distribution of the stochastic matrix M ′′, which is guaranteed when M ′′ does not have transient states.
Now consider the general case where M is not necessarily irreducible. We construct the intermediate matrix M ′ by performing a convex combination of the matrix M1−ω and the uniform stochastic matrix E d , where E is the all one matrix, with weight 1−ω 1−θω . Specifically, for any θ ∈ (0, 1), we define
M ′ = (
1−ω 1−θω
) M 1−ω + ( 1− 1−ω1−θω ) E d . Note that M ′ is a non-negative matrix. In addition, since
M ′1 ≤ 1−ω1−θω1 + ( 1− 1−ω1−θω ) 1 = 1, where 1 is the all one vector, the matrix M ′ is a substochatic matrix with modulus zero, and is also irreducible because all its entries are strictly positive. Therefore, there exists a stochastic matrix M ′′ such that M ′′ ≥ M ′. In addition, since M ′′ also has strictly positive entries, the Markov chain associated withM ′′ is irreducible, hence admits a unique stationary distribution µ ∈ ∆d. By our construction, we can show a lower bound on the components of the stationary distribution µ.

heading: 5 Conclusion
text: In this work, we establish finite-sample guarantees of general n-step off-policy TD-learning algorithms. The key in our approach is to identify a generalized Bellman operator and establish its contraction property with respect to a weighted `p-norm for each p ∈ [1,∞), with a uniform contraction factor. Our results are used to derive finite-sample guarantees of variants of n-step off-policy TD-learning algorithms in the literature. Specifically, for Qπ(λ), TB(λ), and Retrace(λ), we provide the first-known results, and for Q-trace, we improve the result in [19]. The finite-sample bounds we establish also provide insights about the trade-offs between the bias and the variance.

heading: Acknowledgements
text: This work was partially supported by ONR Grant N00014-19-1-2566, NSF Grants 1910112, 2019844, NSF Grant CCF-1740776, and an award from Raytheon Technologies. Maguluri acknowledges seed funding from Georgia Institute of Technology.

Review summaries:
This paper derives finite-sample bounds for off-policy TD learning algorithms. The main idea is to propose a generalized Bellman operator and rewrite the off-policy TD learning as stochastic approximation algorithms. Then it remains to show under what kind of conditions this generalized Bellman operator is a contraction mapping. The proof technique can be used as a general tool to derive finite sample bounds for existing off-policy learning algorithms. 

The authors propose a unified framework for understanding several existing tabular off-policy TD algorithms for policy evaluation. Central to this new framework is a generalized Bellman equation and its contraction. The unified framework provides new insights about the bias-variance trade-off of those existing algorithms, as well as finite sample analysis.