Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators
Authors: Zaiwei Chen
Siva Theja Maguluri
Sanjay Shakkottai
Karthikeyan Shanmugam
Venue: NeurIPS 2021 Poster (2021)
Keywords: Off-policy multi-step TD-learning
generalized Bellman operator
contraction mapping
finite-sample analysis

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 fixed-point 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 $\ell_p$-norm for each $p$ in $[1,\infty)$, 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^\pi(\lambda)$, Tree-Backup$(\lambda)$, Retrace$(\lambda)$, 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^\pi(\lambda)$, Tree-Backup$(\lambda)$, and Retrace$(\lambda)$, and improve the best known bounds of $Q$-trace in \citep{chen2021finite}. Moreover, we show the bias-variance trade-offs in each of these algorithms.

Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators
Zaiwei Chen Georgia Institute of Technology
Siva Theja Maguluri Georgia Institute of Technology
Sanjay Shakkottai
Karthikeyan Shanmugam IBM Research NY
The University Texas at Austin
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 generalized Bellman equation. In this paper. we derive finite-sample bounds for any general off off-policy TD-like stochastic approximation algorithm that solves for the fixed- point this generalized Bellman operator. Our key step is to show that the generalized Bellman operator is simultaneously contraction mapping with respect to a weighted fg-norm for each in [1, o0), with a common contraction factor. Off-policy TD-leamning known suffer from high variance due to the product of importance sampling ratios. A number of algorithms (e.g. Q* Free-Backuu(A)) Retrace(A), and Q-trace) have been proposed in the literature address this issue. Our results immediately imply hampee bounds of these algorithms. In particular, we provide first-known finite-sample guarantees for Q" (A). Tree- Backup(A), and Retrace(A), A), and improve the best known bounds of Q-trace in 19 Moreover, we show the bias- variance trade-off's in each of these algorithms.
Introduction
Reinforcement learning (RL) demonstrated its success in learning effective policies for variety of
decision making problems such autonomous driving [25 26 recommender systems 4T] 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 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-Jeaming method 30 A key ingredient in TDDlearning 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- 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 generated by a possibly different policy (i.e., off-policy sampling). Although off-policy sampling is more practical than on- on-policy sampling, it is more challenging to analyze and is known to have high variance [1], which is fundamental difficulty in off off-policy learning. To overcome this difficulty, many variants of off-policy TD-learning algorithms have been proposed in the literature, such as Q" (A)
17 Tree-Back (henceforth denoted by TB())) 24 Retrace(A)
22 and Q-trace [19 etc.
1.1 Main Contributions
In this work, we establish finite-sample bounds of 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 (NcurIPS 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 weighted fy-norm for every p E [1, 00), with a uniform contraction factor for all p. Our result shows that the sample complexity scales as O)c-²), 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 off-policy TD- learning algorithms including (*) TB()), Retrace(A), and Q-trace. For Q* TB(A), and (etrace(A), 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 é, -n-norm contraction property with a uniform contraction factor for all p E [1, oc) is crucial for 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 aff-policy TD-learnnng but their convergence rates are all affected to varying degrees.
1.2 Generalized Bellman Operator and Stochastic Approximation
In this section, we illustrate the interpretation of off-policy multi-step TD-learnin 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 given policy æ. In the simplest setting where (D(0) with on-policy sampling is employed, it is well known that the algorithm is an SA algorithm for solving the Bellman equation Q = Hz (Q), where Ho (-) is the Bellman operator. The generalized Bellman operator B()) we consider in this paper is defined by:
( = ((H(Q) - Q) +Q,
where T()) and H() are two auxiliary operators. In the special case where T(-) I(.) and H((-) = (-). the generalized Bellman operator (-)) reduces to the regular Bellman operator H. (-). Note that any fixed point of H---) also a fixed point of B(.). as long as T--) is such that T(0) Thus, the operator H((-) controls the fixed-point of the generalized Bellman operator B(-), and as we will see later, the operator (-) can be used to control its contraction properties.
To further understand the operator B.)), we demonstrate in the following that both on- on-policy 2-step TD and TD(A) 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 = He QQ), which can be explicitly written as Q = Ei= (?
(T..)"".. Here R is the reward vector, 7 the discount factor, and P= is the transition probability matrix under policy æ. By reverse telescoping, the n-step Bellman equation is equivalent to Q
E E (yPx)' + PP.QQ Q) + Q T T(H, (Q) Q) + Q, where T(Q) = E (y )QQ Similarly, one can formulate the TD(A) Bellman equation in the form of B(Q) = Q. where T(Q)= =
(1 (I- X (TPa) and H(-- = (-).
In these examples, the operator T()) determines the contraction factor of B(.) by controlling the degree of bootstrapping. In this work, show that in addition on-policy TD-learning variants of off-policy TD-lcarning 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 B3-) is a contraction mapping with respect to some weighted l-- f--norm for any p E [1, oo). with a common contraction factor. This enables us to establish finite-sample bounds of general multi-step off off-policy TD-like algorithms.
1.3 Related Literature
The TD-Icarning 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- On-Policy TD- Te-Lennnng. The most basic TD-leaming method is the TD(0) algorithm 30 Later
was extended to using multi-step bootstrapping (i.e., the n-step TD-learning algorithm [I 37 38))
and using eligibility trace (i.e., the TD(X) algorithm 28 30 ). The asymptotic convergence of TD-
learning was established in 13 18 35 As for finite-sample analysis, a unified Lyapunov approach is
presented [10. To overcome the curse of dimensionality in RI., TD-learning is usually incorporated
with function approximation in practice. In the basic setting where 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-learnig with
neural network approximation were studied in g
Off-Policy TI>-Lamming. In the off- setting, since the samples
necessarily generated by
the target policy, usually importance sampling ratios (or "generalized" importance sampling ratios) are introduced in the TD-Jearning algorithm. The resulting algorithms are QT (24), (B(A) [17]
(etrace(A) (2). and Q-trace [99] (which is an extension of Vttrace 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- finite-sample guarantees are established only for Q-trace and V-trace In the function approximation setting, TD-Jeariig with off- ofl-policy sampling and function
[0 19]. approximation is a typical example of the deadly triad [31, and can be unstable (2 [1]. To achieve convergence, one needs to significantly modify the original TD-Jearnin algorithm, resulting two time-scale algorithms such as GTD 21
TDC
32
and emphatic TD 33 etc.
1.4 Preliminaries
In this section, we cover the background of RL and the TD-leaming 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 actions A, set of unknown a E A}, an unknown reward function R: : S A + [0, 1), and discount factor ? E (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, policy π is mapping from the state-space to probability distributions supported on the action space, i.e., क. : A Al_ The state-action value function QT associated with policy defined by > R Ax) Su 8, Ao a] for all (s, a). The goal in policy evaluation
action dependent transition probability matrices P = {Po E R g[())|S
(*, = E,, D k= estimate the state-action value function Q" for a given policy I..
Since the transition probabilities as well as the reward function are unknown, such sate-action value function cannot be directly computed. The TD-learnng algorithm is designed to estimate Q" using the SA method. Specifically, in T'D-leamiigg we first collect a sequence of samples ((S,. Ax)] from the model using some behavior policy gg. Then the value function Q" is iteratively estimated using the samples {(S,, }-)) When n, æ, the algorithm is called on on-policy TD-Jearning otherwise the algorithm is referred to off-policy TD-Jeaming.
2 Finite-Sample Analysis of General Off-Policy TD-Learning
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.
2.1 A Generic Model for Multi-Step Off-Policy TD-Learning
Algorithm I presents our generic algorithm model. Due to off-policy sampling, the two functions p.p: S A + R. are introduced in Algorithm I to serve as generalized importance sampling ratios in order to account for the discrepancy between the target policy π and the behavior policy Tb- We denote Cmax max,,0 c(s, a) and Pmax max,,a p(s, a). We next show how Algorithm ] captures variants of off-policy TD-learning algorithms in the literature by using different generalized importance sampling ratios e(.,-) and p.:--)-
Vanilla IS. When c(s,a) a) = p(s,a) (als))/ (1)))//m(()) (a]s) for all (s, a), Algorithm T is the standard off-policy TD-Icarning 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 1i a(A, (3). is not controlled in any way. it suffers the most from high variance. 18,)
The (A) Algorithm. When c(s, a) À and p(s, a) T m)))sm))mm))))) Algorithm I is the Q" (A) algorithm [17] The Q** (A) algorithm overcomes the high variance issue in Vanilla IS by introducing the parameter X. However, the algorithm converges only when À is sufficiently small (22).
The (B(A) Algorithm. When c(s, a) = Art (a]s) and p(s, a) = [[a) ())]))/=mm (T)////(aa (a)s))) we have the TB(X) algorithm 24]. The (B))) algorithm also overcomes the high variance issue in Vanilla IS and is
3

---

Algorithm A Generic Algorithm for Multi-Step Off-Policy TD-Learning
Input: K, {. Qo. n, Th, generalized importance sampling ratios c, p : x A + Ru,, and
sample trajectory {[Sk. A&) locksK +n collected under the behavior policy TT-
2: for k= -..
1 do
3: ag(ssa) a) = ((s,aa a) = (Sk. } for all (s)
4: A(S, A., S441.A+1 Qx) = R(S
A41) - A.) for
all i E (k, k + k..., + 1}.
5: QR+1(s,
a (8, a) Ektr- 1, A4
for all (s.
6: end for
7: Output: QK
guaranteed to converge to Q" without needing any strong assumptions. However, as discussed in [22]. the (B) algorithm lacks sample efficiency as does not effectively use the multi-ster return.
The Retrace(A) Algorithm. When c(s, a) = X min 1, π (als)/mA (alss) and p(s, a) = [T]ss) / / (als), we have the Retrace (A) algorithm, which overcomes the high variance and converges to Q". The convergence rate of Retrace(A) is empirically observed to be better than (B(A) in (22].
The Q-trace Algorithm. When we choose c(s, a) min(e, π (als)/mm(al)) (als)) and p(s, a) min(ō, ग [a) algorithm 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 č and p in these algorithms separately control the variance and the asymptotic bias in the algorithm respectively. Note that due to the truncation level p. the algorithm no longer converges to Q², but to biased limit point, denoted by QT [19].
where 2 č, Algorithm is the Q-trace algorithm [19]. The Q-trace
From now on, we focus on studying Algorithm 1 We make the following assumption about the behavior policy Th, which is fairly standard in off-policy TD-learning.
Assumption 2.1. The behavior policy Ty satisfies To na(als) > 0 for all (s. a). In addition, the Markov chain { induced by the behavior policy ma is irreducible and aperiodic.
Irreducibility and aperiodicity together imply that the Markov chain {Sk} has a unique stationary distribution, which we denote by Kig A Moreover, the Markov chain {Sx} mixes geometrically fast in that there exist for all 2 0, where || ||ıv is the total variation distance (20] Let иSa A (S5) Al be such that ASA (s, a)
0 and a (0, such that max.es (s,
kg(-)]lTv S Co
(a)s)) for all (s, a). Note that KSA E A |S||A|| is the stationary distribution of the Markov chain {(S,, Ax)) under the behavior policy Ty. Let K's diag(Ns) |S and let K.s.A = diag(Ks.)) E R|S|| (8||A), Denote the minimal (maximal) diagonal entries Kss and KSs by Ks (Ks, and KSS.min (Ks, respectively.
2.2 Identifying the Generalized Bellman Operator
In this section, identify the generalized Bellman equation which Algorithm is trying to solve, and also the corresponding generalized Bellman operator and its asynchronous variant. Let Te, Hpp RISIIA + R S||AI be two operators defined by
n-1 T=(
C( A)Q(S,)) So = A, = a). and 3=1
1=0
(ss, R(s, + Ip, A
AR+1) S = s, A = a]
for all a). Note that the operator Te(-) depends on the generalized importance sampling ratio
c(-s-), -), while the operator (-) depends on the generalized importance sampling ratio p(-s.).
With T-(-) and (.) defined above, Algorithm I can be viewed as asynchronous SA algorithm for solving the generalized Bellman equation Bep(() (Q) = Q. where the generalized Bellman operator
(-, is defined by Be,p (Q= (el Q) + Q. Since Algorithm |
performs asynchronous update, using the terminology in [10]. we further define the asynchronous variant (-,p()) of the
generalized Bellman operator (-) by
(Q, == K.. (Q) + (I -KsAJQ KsaTc(H,(Q) Q.
(2)

---

Each component of the asynchronous generalized Bellman operator (-) can be thought of as convex combination with identity, where the weights are the stationary probabilities of visiting state- action pairs. This captures the fact that when performing asynchronous update, the corresponding component is updated only when the state-action pair is visited. clear from its definition that
(-)p(-) has the same fixed-points as (.) (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 p(ts.), we will show in the next section that both the asynchronous generalized Bellman operator ( and the operator Hpp-) are contraction mappings. Therefore, since (c( O, the operators (.).). (.) (-) all share the same unique fixentpoint. Since the fixed-por -oontt of the operator H.(-) depends only on the generalized importance sampling ratio :(.,,), but not on c).-). we can flexibly choose
.) to control the variance while maintaining the fixed-point of the operator BB,((.). As we will see later, this is the key property used in designing variants of variance reduced n-step off-policy TD-Jeaming algorithms such as Q" (A), TB))), and Retrace(A).
2.3 Establishing the Contraction Property
In this section, we study the fixed-point and the contraction property of the asynchronous gen- eralized Bellman operator (-, We begin by introducing some notation. Let De, Dp RISIIA x (|S||A| be two diagonal matrices such that De((s, a), (s, =ar'E ToreAAT(aaa Ta(a'|s)cc(s a') and Dj Dp((s, a), (s. = Ea'EA (T(aa) ())(aa)))(sss) a') for all (s, a). We denote D De,min (D (De,max) and D p.min (D mmp) as the minimal (maximal) diagonal entries of the matrices Dr and Dp respectively.
In view of the definition of (-) in Eq. ②). any fixed-point of H.(()) must also be a fixed-point of (-). We first study the fixed point of H-p-) by establishing its contraction property.
Proposition 2.1. Suppose that D Dpamxx < 1/7. Then the operator HH(()) a contraction mapping with respect to the -oorm, with contraction factor 7Dp.max- In this case, the fxed-point Q of Hp(()) satisfies the following two inequalities: (1) 1|Q - QToPlloo S
m (T(ls) my(als)p(sa)) and (2) 1[Q= S I--D (1-7)(1- (Dppmae))))))
Observe from Proposition 2.1 (1) that when p(s,a) = x (als)/ h/ts)//T((a/) which is the case for Q" (A), TB(A). and Retrace(A), A). the unique fixed-point QT is exactly the target value function Q This agrees with the definition of the operator (-)()) in that it reduces to the regular Bellman operator (-) when p(s, a) x ((aa))/mm(()) ()) for all (s, If p(s, a) * (a]ss) TT(als) s) for some (s, a), then in general the fixed-point of (.) that case, Proposition provides
(.) is different from Q". See Appendix A.2 for more details. In error bound on the difference between the potentially biased limit QT 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 || S 1/(1 - 7) for any policy π. Since (-) )))
is no longer the Bellman operator H. (-), the corresponding upper bound on the size of its fixed-point Q=.P also changes.
Note that Proposition 2.1 guarantees the existence and uniqueness of the fixed-point of the operator H,p(-), hence also ensures the existence of fixed- fxxe-poiitss of the asynchronous generalized Bellman operator (-). To further guarantee the uniqueness of the fixed-point of B-, we establish its contraction property. We begin with the following definition.
Definition 2.1. Let (14) siis
a be such that μ4; > 0 for all i. Then for any x E Rdd, the weighted fn-norm (p E [1, o)) of & with weights {1:} is defined by ||>||pp. = (E, M4 | p/)1//
We next establish the contraction property of the operator B.,p(.) in the following theorem. Let >pp.max), where the function f R E is defined by f(x) = = (i I-x" T-x when x 1.
when æ and fxx
Theorem 2.1. Suppose c(s.a) S p(s, a) for all (s, a) and Dp.max < 1/7. Then we have the following results: (1) For any E (0, there exists a weight vector i E AISIAA satisfying a(),a)= > [I-Bw]]siaT for all (s, a) such that the operator Be,(() is contraction mapping with respect to || for any E 20), with contraction factor To = (1 (1-
w(1-0)
(2) The
operator (-) is contraction mapping with respect to || Iloo, with contraction cnnnraactionacttroo. Ne 1 W.
5

---

Consider Theorem 2.1 (1). Observe that we can further upper bound Yo = (1 - (1-w) w fw))
by Bwi 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- || = || so for
any E R and weight vector μa, and limp- (1 -))= - PP Ow) = -1- w.
Theorem 2.1 is the key result for our finte-ssmppl analysis, and we present its proof in the next section. The weighted Lp -n-rr (especially the weighted (y-norm) contraction property we established for the operator (-) 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 fnite-sample bound of on-policy TD-Jeaming with linear function approximation in the seminal work [6)] is that the corresponding Bellman operator is a contraction mapping not only with respect to the 20 -norm, but also with respect to weighted fn-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 immediate future research direction.
2.4 Proof of Theorem 2.1
We begin by explicitly computing the asynchronous generalized Bellman operator (-), Let Te and Tp be two policies defined by Te(als) Ty (=(a)))((x.a)
(s(( and Ta(ass) ag(als)p(s.o) for all D,((s.a),(saaa]
(s, a). Let R E RISIIA be the reward vector defined by R(s,a) = R(s, a) for all (x, a). For any policy x', let Per be the transition probability matrix of the Markov chain ((Sg. As)) under x', i.e. Pe ((s(())) (s', ,a') Pa s'' (a'ls') for all state-action pairs a) and a').
Proposition 2.2. The operator B..p(.) is explicitly given by Be,p(Q) (Q) AQ + b, where A = (7Px.. (I) Dp) and b KSS (7Px.. D.)
I- Ks, (7P
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 3 E [o. 1). matrix M Rdxd called substochastic matrix with modulus ( if and only if Mj 2 0 for all i and Σ, Mij I - for all i.
Remark. Note that for any non-negative matrix M, we have |/ max; E, My.. Therefore, matrix M being substochastic matrix with modulus 8 automatically implies that || S 1 - B.
We next show in the following two propositions that (1) the matrix A given in Proposition 2.2 is a substochastic matrix with modulus w, and (2) for any substochastic matrix M with positive modulus, there exist weights }P:} such that the induced matrix norm || is strictly less than 1. These two results together immediately imply Theorem 2.I
Proposition 2.3. Suppose that c(s, a) S p(s, a) for all (s, a) and D Dp.max 1/7. Then the matrix A given in Proposition 2.2 a substochastic matrix with modulus w.
The condition c(s, a) S <(ss.a) ensures that the matrix A is non-negative, and the condition Dp.maxx < 1/7 ensures that the each row of the matrix A sums up to at most 1 w. Together they imply the substochasticity of A. The modulus w is an important parameter for our siniee-smpll analysis. In view of Theorem 2.1 we see that large modulus gives smaller (or better) contraction factor of Be Proposition 2.4. For any substochastic matrix M E Raxd with a positive modulus /3 E (0, 1), for B(1-0) any 0 E (0, 1), there exists a weight vector E A satisfying 2 (1-03yd for all i such that [|MlIp.p S (1 3)1-1/p(( - -0 for any p E [s). Furthermore, if M is irreducible ! then can choose 0 = 1.
The result of Proposition 2.4 further implies || S
03, which is independent of the choice of p. This implics that (-) is a uniform contraction mapping with respect to || lla.p for all 2 1. In general, for different p and p'. an operator being a ||- 1|p llo-norm contraction does not imply being -I-ll--norm contraction. The reason that we have such a strong uniform contractive result is that the operator (-) has linear structure, and involves a substochastic matrix.
Note that Proposition 2.4 introduces the tunable parameter 0. It is clear that large 0 gives better contraction factor of (-, but worse lower bound on the entries of the weight vector μ. In
A negntige matrix is irreducible if and only if its associated graph strongly connected 4

---

general, when M is not irreducible, we cannot hope to choose a weight vector E A with positive components and obtain ||M p.p I w-- w. To see this, consider the example where M (1 (1-w) 0, 1, which is clearly a substochastic matrix with modulus w, but is not an irreducible
matrix. For any weight vector E A", we have || = (1 - w) maxppe<::lllllp [a
(1 (1-w)/ua 1/p > 1 w. However, by choosing da close to unity, we can get || Ipp arbitrarily close
1o1- 1-1-w. w. This analogous to choosing 0 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
2.5 Finite-Sample Convergence Guarantees
In light of Theorem 2.1 Algorithm Tis is a Markovian SA algorithm for solving fixed-point equation
(Q) Q. where the fixed-point operator (+) is contraction mapping. Therefore, to establish the finite-sample bounds, we use a Lyapunov drift argument where we choose ((Q) 1|Q-Q* Q= as the Lyapunov function. This leads to finite-sample bound on E|ll Qx
Q - p.pll
However, since ju is unknown, to make the finite-sample bound independent of we use the lower bound on the components of j provided in Theorem 2.1 and also tune the parameters p and 0 to obtain a finite-sample bound on E|IlQ= - QT The fact that we have a uniform contraction factor - Ow (ef. Theorem 2.1 plays important role in such tuning process.
To present the results, we need to introduce more notation. For any > O, define to (MCss as the mixing time of the Markov chain {Sx} (induced by my) with precision 6, i..., (5(MCs) ks(()]lTv S 8). Under Assumption 2.1 one can easily verify that (MCs) S (1og(1/)) + 1) for some constant
minfk 2 0 max,es PK (s.
O, which depends only on C' and Let T8nn = (sMS + + 1. The parameters c and ca 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 fiite-ssaple bound for using constant stepsize.
Theorem 2.2. Consider {Qx}] of Algorithm
7 Suppose that: (1) Assumptions 2.1 is satisfied, (2)
c(8, a) I p(s, a) for all (8, a) and D Dpmax
1/7, and (3) the constant stepsize is chosen such Then we have for all 2 Ta.ni
that @Ta, S (/g(((]]AA//w))((1mm))
+172.
E| - QT 1 | S<i (1 wa k-Tam
f(yCmax ) (rPPmxx + 1)² log (2S))))///)
+ +
(Toom (3)
2
where S1 = c2ll 100010~0 + 11Qull + 1)?, and (2 = 11 + 1)
Theorem 2.2 enables one to design a wide class of off off-policy TD variants with provable sinite-sample guarantees by choosing appropriate generalized importance sampling ratios c(.,-) and p(:,)) The first term the RHS of Eq. 5 is usually called the bias in SA literature (6) and it goes zero at geometric rate. The second term on the RHS of Eq. (B) stands for the variance in the iterates, and it is constant proportional to a.aa To see more explicitly the bias variancee trade-off, we derive the sample complexity of Algorithm in the following.
Corollary 2.2.1. For accuracy 0, to obtain B[I[Qx [TTPP11o0] the sample complexity is
log 2 (1/c)
' (ff((Cmmxx) )2 (7PPexx + 1)2 (1 - 7 DDp.max) )2
Ö
(4)
22
T
T2
Ta
In Corollary 2 the Ō(E=2) dependence on the accuracy is the same as n-step TD-learning in the on-policy setting [0]. and in general not improvable. The term T2 can be equivalently written as ((1/(1 Contraction factor)²), 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 is due to using n-step bootstrapping. By optimizing the sample complexity in terms of n. we have Noptimal 1/ log (1/(7
This is analogous to the optimal n in the on- on-policy setting, which is 1/ /o/ol//1)) [10] The additional Dr,min factor arises because of using off- 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 Pmax lead to smaller variance. As we will see later, this is the reason for the variance reduction of various off-policy TD-learnin algorithms in the literature. In light of the previous analysis, the bias-variance trade-off in general off-policy multi-step TD-lcarning algorithm| is intuitively of the form
Variance
Contraction factor)"
7

---

3 Application to Various Off-Policy TD-Learning Algorithms
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 mmax (Tmin) and Tbmaax (To,.inn) be the maximal (minimal) entry of the target policy и and the behavior policy T6 respectively. Let Tmax m (I s)/TT mb(als)) (Tmin ming,a (1 (T)a(a))am))))) (TT[mss))(((ssss)s) ratio between π and TT. We will overload the notation of Ç1 and (2 from Theorem 2.2
be the maximum (minimum)
Note that
Q Q" in Q" (A), (A),,, and Retrace(A), but QTIP Q" in Q-trace.
3.1 Finite-Sample Analysis of Vanilla IS
We first present the sample complexity bound of the Vanilla IS algorithm, where c(s, p(8, a) T (als)/ (als)) for all (s, a).
Theorem 3.1. Consider Aagorithhm@with Vanilla IS update, where note that Cmax Pmax Tmaxx
De = Dp = I, and w = KsA, ). Suppose that Assumption 2.1 is satisfied. Then, to
achieve e-accuracy, the sample complexity is O log" (1/c(
( Ö
"(le +1)
(1-5)²
In the special case where Thb (i.e., on-policy n-step TD), the sample complexity bound reduces which is comparable to the results in [10]. See Appendix C.2 for
to Ô n lllo""(1// (1/e)
more details. In the off- off- policy setting, note that the factor ((1Mmax) ) - 1)² appears in the sample complexity. When TTmax > 1 (which can usually happen), the sample complexity bound involves an exponential factor (Ymmmx)* )". The reason is that the product of importance sampling ratios c(:,)) 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 w = KSA among all the algorithms we study.
?") within Vanilla IS is the largest (best)
3.1.1 Finite-Sample Analysis of (A)
In this section, we present the sample complexity of the Q (A) algorithm, where c(s, a) A and p(s, a) = x (als)) (a(ass) for all (8, a).
Theorem 3.2. Consider Algorithm
[ with Q (A) update, where we note that Cmax Tmax: D. = =XI, Dp I, and w = KKsAmiuu(AA)(( -)). Suppose that Assump- satisfied, and S Tmin- Then, to achieve e-accuracy, the sample complexity is 5 (yrmax
Pmax
tion
2.7
O
Log (1/e)
(1-?)*
To see how (A) overcomes the high variance issue in Vanilla IS, observe that since 7d < Mimi S
Y < 1, we have (7 S 1/(117A)) Therefore, by replacing c(s, a) raa (s/ [ Vanilla IS with a properly chosen constant x, 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, (*( does not effectively use the n-step return. Hence the parameter w in Q" (A) is less (worse) than the one in Vanilla IS.
3.1.2 Fimite-Sample Analysis of TB())
In this section, we present the sample complexity of the TB(A) algorithm, where c(8, a) Ar(a(s) and p(8, a) = π (a]s)/ ((als)///((() (als)) for all (8,a).
Theorem 3.3. Consider Algorithm 7 with TB(A) update, where we note that Cmax = ATmax Paaxx Tmaxx De(s, a) A En Tola s (alss). (s, and w = Mnn..inf(yDee.uu (1-.mi))1171) Suppose that Assumption 2. is satisfied, and X < 1 Then, to achieve e-accuracy, the sample log"
nffrdmmea) (1T (1TTmax (1)))x+11))
complexity is
Suppose we further choose À < 11/(TTmax), the TB(A) algorithm also overcomes the high variance issue in Vanilla IS because ((x'Ammax)) S 1/(1 mx which does not involve any exponential large factor. When compared to Q (A), ), an advantage of (B(A) 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 De,mi = À min,,a Σ. To(ass) ( (a)s s)) < 1, the (B))) algorithm does not effectively use the n-step return, hence the parameter in TB (X) is less (worse) than the one in Vanilla IS.
8

---

3.1.3 Finite-Sample Analysis of Retrace(A)
In this section, we present the sample complexity of the Retrace(X) algorithm, where c(s, a) minn(1, (alss)/m (alss) and p(s, a) = π (aals)/mo(als) for all (8,a).
Theorem 3.4. Consider Algorithm|] 7 with Retrace(A) update, where we note that Cmax X Pmax Tmax. Ds(s, a) = A E. min(TT (To(( [8), (a)ss)), Dy(s, a) = and w = ff
7).
Suppose that Assumption 2.7 is satisfied, and À S 1. Then, to achieve e-accuracy, the sample
complexity is O lo/e(1/)
Ö (1 +12
(1-7)²
The Retrace(A) algorithm overcomes the high variance issue in Vanilla IS by truncating the importance sampling ratio at 1, which prevents exponential large factor in the variance term. In addition, it does not require choosing À to be extremely small as required in (A). As for the compromise in the contraction factor, note that min(1, π (als)/ //y (als)) 2 т Talss), which implies that De a) (and hence De,min) ) is larger in the Retrace ()) algorithm than the (A) algorithm. As a result, (etrace does not truncate the rt-ttep return as heavy as TB (BA)), and hence the parameter is larger (better) in Retrace(A) than in (A).
3.1.4 Simite-Sample Analysis of Q-Trace
Lastly, we present the sample complexity of the Q-trace algorithm, where c(s,a) min(C, ((aas)/m((aa)))) and p(s,a) a) = min(p, <<als)/=a(a(s)) for all (s,
Theorem 3.5. Consider Algorithm 7 with Q-trace update, where we note that Cmax
Pmax = P. D)(s.a) = =Ee min( eTT (als), (a)s), {a]ss), Dp(s,a) = - (ainp x(a[s)), and
KSA.miaf (1 (r:De,in)(11 >Dp.max). Suppose that Assumption 2.1 is satisfied, and S p. Then,
to achieve e-accuracy, the sample complexity is O (1oR2 Ô Ô (n((10)((044+)))
(1-7Dp.max))
To avoid an exponential large variance, in view of the term f(72) in our bound, we need to choose a S 1/7: The major difference between Q-trace and Retrace A) is that the importance sampling ratio p(...) inside the temporal difference (line 4 of Algorithm also involves truncation. As shown in Section 2.3 due to introducing the truncation level p. the algorithm converges to a biased limit QTsP instead of Q Such truncation bias can be controlled using Proposition 2.1 These observations agree with the results [19,, where the mamee-sample bounds of Q-trace were first established.
Compared to 19. we have an improved sample complexity. Specifically, the result in 19 implies (fee)//ee((()))))))))
a sample complexity of Ö (-w"(1->)] DDp..
which has an additional factor of w Since
w-1 x A.mii 2 ||), our result improves the dependency on the size of the state-action space
by factor of at least [S] ||| compared to [9]. Similarly, since the V-trace algorithm [4 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 provide sufficient conditions under which Algorithm [ has provable finite-sample guarantees, and hence enable us to design new algorithms. As an example, in light of the Retrace(A) (A) algorithm and the Q- trace algorithm, one can take advantage of both algorithms to let c(s, a) X min C, π (Ta (a|s)/ (Ta(ss)) and p(s.a) = Ap min(p, x s)ss TT (a)s)))) where de. Ap ट, and ğ are tunable parameters. As long as Xee S App < 1/7, Theorem 2.2 is applicable and hence finite-sample convergence is guaranteed. To avoid an exponentially large variance, we choose d₂x S 1/7 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 (1/e)/ A.).A.,ia) when presenting the sample complexity, and use A b (a V b) to denote the minimum (maximum) of two real numbers a and 6.
In view of Table 1, when Fmax < 1/7, which indicates that the target policy π and the behavior policy Te 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 r'ax > 1/7, then Vanilla IS can potentially have exponentially large variance, while other four algorithms do not. In this case, among (*).), TB(X), and Retrace(A), Q*(()) has the best sample complexity bound. However, we need to point out that

---

Table 1: Summary of the Sample Complexity Bounds
Algorithm
c(s, a)
p(s, a)
Requirements
Sample Complexity
Vanilla IS
s(aas)
s(als)
None
Ö
( 1)
su(a]s)
(a(s)
(1
7 (1-2))
(A)
A
s(als)
X Fiin
(P +1) 11-7)"
[a(a]a)
TB(A)
Ar(alss
x(als)
À max Viaie
[erAAtmrr )' ((yima +1
Wa(d]e)
MyyDe, ((T))((Tmman +1)2 el [11 (1-g)) S(100) 130+13 Fl7Desmin 121 DD.man
Retrace(A)
A[1A
=[a]e)
x(als)
A
O
k((a(=)
[a(a]a)
Q-trace
[(als)
PA
esp,e<
the requirement X S Tmin for (*) is most restrictive, and the algorithm easily diverge when this requirement is not satisfied, as evidenced by the numerical experiments presented in [22]. As for the Q 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 p(-))) :) 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- off-policy n-step TD-learning algorithms.
Proof sketch of Proposition 2.4
The idea is to construct a stochastic matrix M such that: (1) M dominates M in the sense that My 2 Maj for all j, and (2) the Markov chain associated with M" is irreducible, hence admits unique stationary distribution y > 0. Using j 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 MM factor of 1/(1 - w) to obtain M' = T- which is clearly a substochastic matrix, with modulus zero Hence there exists stochastic matrix M that dominates M' (and also M). Moreover, since M" is also irreducible, its associated Markov chain has a unique stationary distribution ju. This equivalent to choosing 0 = 1 in Proposition 2.4 In fact, the matrix M being irreducible is only sufficient condition to choose 0 = 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 convex combination of the matrix M
1-u and the uniform stochastic matrix 3. where E is the all one matrix, with weight 1- Specifically, for any 0 E (0,1), 1), define
M'
M
1-w 1-
E
d. Note that M' is a non-negative matrix. In addition, since
1-
I-
==1, 1, where 1 is the all one vector, the matrix M' is a substochatic matrix with modulus 7ero, and also irreducible because all 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 with A1" " irreducible, hence admits a unique stationary distribution Ad. By our construction, we can show a lower bound the components of the stationary distribution μl.
M' < T-
T
1- T-Bw
5 Conclusion
In this work, we establish Anite-sample guarantees of general n-step off-policy TD- TD-learning algo- rithms. The key in our approach is to identify generalized Bellman operator and establish its contraction property with respect to a weighted l, ep-norm for each E [1, oc), with a uniform contrac- tion factor. Our results are used to derive finite-sample guarantees of variants of re-tep off-policy TD-learning algorithms in the literature. Specifically, for (A), (A), and Retrace(A) (A), we provide the first-known results, and for Qtracee, 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.
10

---

Acknowledgements
This work was partially supported by ONR Grant N0001419--1-255 NSF Grants 1910112, 2019844, NSF Grant CCF-1740776, and an award from Raytheon Technologies. Maguluri acknowledges seed funding from Georgia Institute of Technology.
References
[1] Aggarwal, C. C. et al. (2016). Recommender systems, volume Springer.
[2] Baird, L. (1995). Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier.
[3] Beck, A. (2017). First-order methods in optimization, volume 25, SIAM.
[4] Berman, A. and Plemmons, J. (1994). Nonnegative matrices in the mathematical sciences. SIAM.
[5] Bhandari, J.. Russo, D., and Singal, R. (2018). A finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pages 1691- 1692.
[6] Bottou, I.., Curtis, F. E., and Nocedal, J. (2018). Optimization methods for large-scale machine learning. Siam Review, 60(2):223-11.
[7] Cai, Q. Yang, 7., Lee, J. D., and Wang, Z. (2019). Neural temporal-difference learning converges global optima. Advances in Neural Information Processing Systems, 32.
[8] Cayci, S., Satpathi, S., He, N., and Srikant, R. (2021). Sample Complexity and Overparameteri- zation Bounds for Projection-Free Neural TD Learning. Preprint arXiv:2103.0133)
[9] Chen, Z.,, Maguluri, T., Shakkottai, S., and Shanmugam, K. (2020). Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes. Advances in Neural Information Processing Systems, 33.
[10] Chen, 7., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2021). A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-Hearnig variants. Preprint 2rXiv:2102.01:
[11] Cichosz, and Mulawka, J. (1995). Fast and efficient reinforcement learning with truncated temporal differences. In Machine Learning Proceedings 1995, pages 99-107. Elsevier.
[12] Dalal, G.. Szörényi, B., Thoppe. G., and Mannor, S. (2018). Finite Sample Analyses for TD (0) With Function Approximation. In Thirty-Second AAAI Conference on Artificial Intelligence.
[13] Dayan, P. (1992). The convergence of TD(A) for general X. Machine learning, 8(3-4):341-36.
[14] Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T.. Dunning, I., et al. (2018). IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures. In International Conference on Machine Learning, pages 1407-1416.
[15] Glynn, P. W. and Iglehart, D. L. (1989). Importance sampling for stochastic simulations. Management science, 35(11):1367-1392
[16] Gottesman, O., Futoma, J., Liu, Y., Parbhoo, S., Celi, L., Brunskill, E., and Doshi-Velez, (2020). Interpretable off policy evaluation reinforcement learning by highlighting influential transitions. In International Conference on Machine Learning, pages
PMLR.
[17] Harutyunyan, A., Bellemare, M. G., Stepleton, T., and Munos, R. (2016). Q()) with Off- Policy Corrections. In International Conference on Algorithmic Learning Theory, pages 305-320. Springer.
11

---

[18] Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994). Convergence of stochastic iterative dynamic programming algorithms. In Advances in neural information processing systems, pages 703-710.
[19] Khodadadian, S., Chen, Z., and Maguluri, S. T. (2021). Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm. The 38th International Conference Machine Learning.
[20] Levin, D. A. and Peres, Y. (2017). Markov chains and mixing times, volume 107. American Mathematical Soc.
[21] Maci, H. R. (2011). Gradient temporal-difference learning algorithms. University of Alberta.
[22] Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M. G. (2016). Safe and efficient off off-poliey reinforcement learning. In Proceedings of the 30th International Conference Neural Information Processing Systems. pages 1054-1062.
[23] Nowé, A., Vrancx, P., and De Hauwere, Y.-M. (2012). Game theory and multi-agent reinforce- ment learning. In Reinforcement Learning, pages 441 440-470. Springer.
[24] Precup, D., Sutton, R. S., and Singh, S. P. (2000). Eligibility Traces for Off-Policy Policy Evaluation. In Proceedings of the Seventeenth International Conference on Machine Learning, pages 759-766.
[25] Sallab, A. E.,, Abdou, M., Perot, E., and Yogamani, S. (2017). Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19):70-76.
[26] Shalev-Shwartz, S., Shammah, S., and Shashua, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving. Preprint arXiv:1610.03295.
[27] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T. Baker, L., Lai, M., Bolton, A., et al. (2017). Mastering the game of go without human knowledge.
Nature, 550(7676)3354.
[28] Singh, P., Jaakkola, T., and Jordan, M. I. (1994). Learning without state-estimation in partially observable Markovian decision processes. In Machine Learning Proceedings 1994, pages 284-292, Elsevier.
[29] Srikant, R. and Ying, L.. (2019). Finite-time error bounds for linear stochastic approximation and TD learning. In Conference on Learning Theory, pages 2803-2830.
[30] Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine learning, (11):9444.
[31] Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
[32] Sutton, R. S., Maci, H. R., Precup. D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. (2009). Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 900-
[33] Sutton, R. S., Mahmood, A. R., and White, M. (2016). An emphatic approach to the problem of off-policy temporal-difference learning. The Journal of Machine Learning Research, 17(1):2603- 1.31.
[34] Thoppe. G. and Borkar, V. (2019). A concentration bound for stochastic approximation via Alekseev's ' formula. Stochastic Systems, 9(1):1-26.
[35] Tsitsiklis. J. N. (1994). Asynchronous stochastic approximation and Q-learning Machine learning, 16(3):185-22
[36] Tsitsiklis, N. and Van Roy, (1997). Analysis of temporal-difference learning with function approximation. In Advances in neural information processing systems, pages 1075-1081.
[37] Van Seijen, H., Mahmood, A. R., Pilarski, P. M., Machado, M. C., and Sutton, R. S. (2016). True online lemporal-difference learning. The Journal of Machine Learning Research, 17(1):0057- 5096.
12

---

[38] Watkins, C. C. H. (1989). Learning from delayed rewards. King's College, Cambridge United Kingdom.
[39] Zhang, Q. Guan, Y., and Tsiotras, P. (2020). Learning Nash Equilibria Zero-Sum Stochastic Policy Approximation. Preprint arX:n:2009.00162.
Games via
[40] Zhao, Y., Zeng, D., Socinski, M. A., and Kosorok, M. R. (2011). Reinforcement learning strategies for clinical trials nonsmall cell lung cancer. Biometrics, 67(4):1422-1433
[41] Zou, I.,, Xia, I.., Ding, Z., Song, J., Liu, W. and Yin, D. (2019). Reinforcement learning to optimize long-term user engagement in recommender systems. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2810-2818.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proof's are presented in the Appendix based on the order they appear the paper.
you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [N/A]
you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica- ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "sLPy5Hrs1lq", "reviewer": "Reviewer_1iu2", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I think this is a solid work and the paper is well written, easy to follow. I checked the proof of Proposition 2.4 in detail, which I believe is the most important ingredient to all the theoretical results in the paper. It looks correct to me. With Proposition 2.4, I do expect all other results to hold.\n\nI have only a few points.\n1. In both Line 223 and Line 402, the authors mention the possible extension to linear function approximation. It looks not straightforward to me. With FA, we typically need a projection operator w.r.t. to the norm induced by the sampling distribution (or some other distribution we can sample from). However the generalized Bellman operator is contractive w.r.t. the ergodic distribution of M''. So one possible approach is to design a method to sample according to M''. By the construction of M'', this looks nontrivial. I understand this FA thing is just a possible future, but I might be nice if the authors could discuss this more to give readers more insights.\n2. In general I like works unifying existing methods. With this unified framework, is it possible to come up with some new algorithms to optimize the bias variance tradeoff revealed by the analysis? I think by doing so the papers can have more algorithmic contribution.", "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": "3"}, "extra_text": {}}, {"review_id": "fyM6jmy68D", "reviewer": "Reviewer_USL9", "summary": "This paper proposes a generalized Bellman operator for off-policy methods and provides finite-sample bounds for the associated stochastic approximation algorithm. These bounds can be applied to several previous off-policy TD algorithms such as Retrace and Tree-Backup, which allows one to assess their tradeoffs in the form of a variance term and a contraction factor.\n", "questions": "", "limitations": "", "rating": 8, "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": "Overall, I enjoyed the paper and think it can improve our understanding of off-policy TD methods through a theoretical analysis of sample complexities. The writing was clear and the paper was easy to follow. I particularly appreciated the clear exposition and proof sketches. \nI would be interested in seeing the next works in this direction with extensions to function approximation.\nI do have some certain clarifications questions written below and would raise my score if these are addressed.\n\nComments and questions:\n- Interesting formulation for the generalized Bellman operator. It seems fruitful to consider those generalizations as a basis for further theoretical analysis.\n\n- The proposed general stochastic approximation update doesn't match the original update for Tree-Backup and Retrace. In particular, there is a importance sampling ratio in the TD-error but, in the original Tree-Backup/Retrace update, there is no such ratio and the target is replaced by \\sum_a' pi(a'|s') q(s', a'). This target should intuitively have lower variance than the importance-sampled one and perhaps the bounds can be refined to account for this. \nAt the very least, it would be important to mention this difference between the original algorithms and the variants currently described in the paper. \n\n- I think the sample bounds established on the various TD methods are interesting and I appreciate that they can meaningfully discriminate between the tradeoffs of each algorithm. In particular, the decomposition into variance and contraction factor is interesting. Pushing this a bit further, can you propose new update rules that improve sample complexity by optimizing these theoretical bounds? I think the theory would be stronger if it could also be to design new algorithms in addition to understanding previous ones. \n\n- As a suggestion to improve clarity, for the individual sample complexities, I suggest omitting the exact iteration bound and specifiyng the step sizes every time since it follows the template of theorem 2.2. I would only include the parameter values to be substituted (c(s,a), \\rho(s,a), etc.), along with the value of \\omega (the contraction factor) and the sample complexity. It would be nice to additionally include the 'variance' term too. It may be easier to compare algorithms at a glance in this form.  \n\n- An explanation of the effect of n (from n-step updates) in the theoretical bounds would be a nice inclusion. As far as I can tell, this only affects the f(.) function which plays a role in both the variance and contraction factor terms. \n\n- A clarification question about proposition 2.4: This proposition guarantees the existence of certain weights \\mu for which the Bellman operator is a contraction mapping. Does it matter if this \\mu does not correspond to the stationary distribution of any policy? For the standard analyses of on-policy TD, usually the weighting does in fact correspond to the stationary distribution of the behaviour policy.\n\n- Are there any papers analyzing the vanilla IS algorithm and giving finite-sample bounds? I'm a bit surprised there are none since it seems closely related to standard on-policy TD.\n- How do these bounds compare to the on-policy TD sample bounds?\n\nMinor comments:\n- In several parts, the variable 'a' is overloaded in both the sum and as a argument e.g. line 189 in the definition of D_c, 'a' is used in both the sum and the variable of the function. This would need to be clarified.\n- Line 218: The matrix 'A' is referenced but hasn't been introduced up to this point. \n- Line 128: Instead of referring to c(.,.) and rho(.,.) both as generalized importance sampling ratios, perhaps the it would be clearer to call c(.,.) something else, such as a 'trace' (following the terminology in the Retrace paper), since it actually consists of a product of the one-step importance sampling ratios. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While the limitations are discussed briefly, it would be nice to expand on that: which parts are less satisfying or that could be improved in the present work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "8ITLA-GOfFv", "reviewer": "Reviewer_NGvZ", "summary": "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. ", "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": "The paper is well written and the problem setups are defined clearly. I really enjoy reading this paper. \n\nThe nice thing about the generalized Bellman operator is to provide a unified framework to study the finite sample guarantees of off-policy TD learning algorithms. Also, in the derived bound we can clearly see the bias-variance trade off. Although I am not very familiar with previous theoretical analysis on these algorithms, this does look like a very nice contribution to the literature.  \n\nThere are some quantities used in the presented results, such as $c_\\text{max}, \\rho_\\text{max}, D_{c, \\text{min}}$. It might be good to give some example to show how large these quantities are so that the reader can get some intuitions when the bounds will be large or small. \nFurthermore, the paper focus on the policy evaluation problem. How do the results imply for the control setting? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal issue has been found. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issue has been found. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers reached a consensus that this paper makes solid contributions. I recommend acceptance. The authors should still carefully revise their paper on the clarity issues raised by the reviewers and explain more about the intuitions for better readablity. 
Decision: Accept (Poster)