PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method
Authors: Ziwei Guan
Tengyu Xu
Yingbin Liang
Venue: ICLR 2022 Poster (2022)
Keywords: emphatic temporal difference
finite-time analysis
off-policy evaluation
reinforcement learning

Abstract: Emphatic temporal difference (ETD) learning (Sutton et al., 2016) is a successful method to conduct the off-policy value function evaluation with function approximation. Although ETD has been shown to converge asymptotically to a desirable value function, it is well-known that ETD often encounters a large variance so that its sample complexity can increase exponentially fast with the number of iterations. In this work, we propose a new ETD method, called PER-ETD (i.e., PEriodically Restarted-ETD), which restarts and updates the follow-on trace only for a finite period for each iteration of the evaluation parameter. Further, PER-ETD features a design of the logarithmical increase of the restart period with the number of iterations, which guarantees the best trade-off between the variance and bias and keeps both vanishing sublinearly. We show that PER-ETD converges to the same desirable fixed point as ETD, but improves the exponential sample complexity of ETD to be polynomials. Our experiments validate the superior performance of PER-ETD and its advantage over ETD.

Published as a conference paper at ICLR 2022
PER-ETD: A POLYNOMIALLY EFFICIENT EMPHATIC TEMPORAL DIFFERENCE LEARNING METHOD
Ziwei Guan, Tengyu Xu & Yingbin Liang
Department of Electrical and Computer Engineering Ohio State University Columbus, OH 43210, USA {guan. 283, xu. 3 @buckeyemail www.eeaaal....eeeee....ee...oo
osu. edu & liang. 8896osu. edu
ABSTRACT
Emphatic temporal difference (ETD) learning (Sutton et al., 2016) is successful method to conduct the off off-policy value function evaluation with function approxi- mation. Although ETD has been shown converge asymptotically to desirable value function, it is well-known that ETD often encounters large variance so that its sample complexity erations. this work, we propose a new ETD method, called PER-ETD (i.e., PEriodically Restarted-ETTD), which restarts and updates the follow-on trace only for a finite period for each iteration of the evaluation parameter. Further, PER- ETD features a design of the logarithmical increase of the restart period with the number of iterations, which guarantees the best trade-off between the variance and bias and keeps both vanishing sublinearly. We show that PER-ETD converges to the same desirable fixed point as ETD, but improves the exponential sample complexity of ETD to polynomials. Our experiments validate the superior per- formance of PER-ETD and its advantage over ETD.
increase exponentially fast with the number of it-
INTRODUCTION
As a major value function evaluation method, temporal difference (TD) learning (Sutton 1988
Dayan, 1992) has been widely used in various planning problems in reinforcement learning. Al- though TD learning performs successfully in the on-policy settings, where an agent can interact with environments under the target policy, it can perform poorly or even diverge under the off off-policy set- tings when the agent only has access to data sampled by behavior policy (Baird) 1995| Tsitsiklis & Van Roy 1997, Mahmood et al. 2015). To address such an issue, the gradient temporal -iiforraldiiffeeecee (GTD) (Sutton et al., (2088) and least-squares temporal difference (LSTD) Yu 2010 algorithms have been proposed, which have been shown converge in the off-policy settings. However, since GTD and LSTD consider an objective function based on the behavior policy, which adjusts only the distribution mismatch of the action and does not adjust the distribution mismatch of the state, their converging points can be largely biased from the true value function due to the distribution mismatch between the target and behavior policies, even when the express power of the function approximation class is arbitrarily large (Kolter 2011).
In order to provide a more accurate evaluation, (uttonn al. (016)) proposed the emphatic temporal difference (ETD) algorithm, which introduces the Jollow-on trace to address the distribution mis- match issue and thus adjusts both state and action distribution mismatch. The stability of ETD was then shown in Sutton et al. (2016): Mahmood et al. (2015), and the asymptotic convergence guaran- tee for ETD was established in (215), it has also achieved great success in many tasks (Ghiassian et al. 2016 Ni 2021). However, although ETD can address the distribution mismatch issue to yield a more accurate evaluation, it often suffers from very large variance error due to the follow-on trace estimation over long infinite time horizon (Hallak et al. 2016). Consequently, the convergence of ETD can be unstable. It can be shown that the variance of ETD can grow exponentially fast as the number of iterations grow that ETD requires exponentially large number of samples to converge. Hallak et al. (2016) proposed an ETD method to keep the follow-on trace bounded but at the cost of possibly large bias error. This thus poses the following intriguing question:

---

Published as a conference paper at ICLR 2022
Can design a new ETD method, which overcomes its large variance without introducing a large bias enror, and improves its exponential sample complexity to be polynomial at the same time?
In this work, provide affirmative answer.
1.1 MAIN CONTRIBUTIONS
We propose novel ETD approach, called PER-ETD (i.e., PEriodically Restarted-ETD), in which for each update of the value function parameter we restart the follow-on trace iteration and update only for times (where call b as the period length). Such a periodic restart effectively reduces the variance of the follow-on trace. More importantly, with the design of the period length b to increase logarithmically with the number of iterations, PER-ETD attains the polynomial rather than exponential sample complexity required by ETD.
We provide the theoretical guarantee of the sample efficiency of PER-ETD via the finite-time anal- ysis. We show that PER-ETD (both PER-ETD(O) and PER-ETD(A)) converges to the same fixed points of ETD(O) and ETD(A), respectively, but with only polynomial sample complexity (whereas ETD takes exponential sample complexity). Our analysis features the following key insights. (a) The period length plays the role of trading off between the variance (of the follow-on trace) and bias enror (with respect to the fixed point of ETD), and its optimal choice of logarithmical increase with the number of iterations achieves the best tradeoff and keeps both errors vanishing sublin- early. (b) Our analysis captures how the mismatch between the behavior and target policies affects the convergence rate of PER-ETD. Interestingly, the mismatch level determines a phase-transitee phenomenon of PER-ETD: long as the mismatch is below a certain threshold, then PER-ETD achieves the same convergence rate as the on-policy TD algorithm; and the mismatch is above the threshold, the converge rate of PER-ETD gradually decays as the level of mismatch increases.
Experimentally, we demonstrate that PER-ETD converges in the case that neither TD nor ETD converges. Further, our experiments provide the following two interesting observations. (a) There does exist a choice of the period length for PER-ETD, which attains the best tradeoff between the variance and bias errors. Below such a choice, the bias error is large so that evaluation is not accurate, and above it the variance eтгоr is large so that the convergence is unstable. (b) Under a small period length b, it is not always the case that PER-ETD(A) with À attains the smallest error with respect to the ground truth value function. The best À depends on the geometry of the locations of fixed points PER-ETD(A) for 0 < X S 1, which is determined by chosen features.
1.2 RELATED WORKS
TD learning and GTD: The asymptotic convergence of TD learning was established by Sutton
(1988 Jaakkola et al. (199)); Dayan & Sejnowski (1994); Tiissiklis & Van Roy (1997), and its non-
asymptotic convergence rate was further characterized eccetllylnn in Dalal et al. (201 Sa); Bhandari et al. (2118: Kotsalis et al. (2020); Chen al. (2019); Kaledin et al. y Hu & Syed (019); Srikant :
& Ying (019)). The gradient temporal-differenee (GTD) was proposed in Sutton et al. (2008) for off-policy evaluation and was shown to converge asymptotically. Then, Dalai al. (20T 8b); Gupta ct al. (2019): WWang et al. (2018); Xu et al. (2019;; Xu & Liang (222)) provided the finite-time analysis of GTD and variants.
Emphatic Temporal Difference (ETD) Learning: The ETD approach was originally proposed
in the seminal work (Suttnn et al. (2016), which introduced the follow-on trace to overcome the distribution mismatch between the behavior and target policies. Yu (2015) provided the asymptotic al. (2016) showed that the variance of the follow-on trace may be unbounded. They further proposed an ETD method with a variable decay rate to keep the follow-on trace bounded but at the cost of a possibly large bias error. Our approach is different and keeps both the variance and bias vanishing sublinearly with the number of iterations. [maai et al.) 20088) developed a new policy gradient thcorem, where the emphatic weight is used to correct the distribution shift. Zhang et al. (2020b) provided new variant of ETD, where the emphatic weights are estimated through function approximation. Van Hasselt et al. 2018 Jiang et al. (2021) studied ETD with deep neural function class.
convergence guarantee for ETD. Hallak EaDlHallak
Comparison to concurrent work: During our preparation of this paper, a concurrent work (Zhang
& Whiteson 2021) was posted on arXiv, and proposed truncated ETD (which refer to as
2

---

Published as a conference paper at ICLR 2022
T-ETD for short here), which truncates the update of the follow-on trace to reduce the variance of ETD. While T-ETD and our PER-ETD share a similar design idea, there are several critical differences between work from Zhang & Whiteson (202I). (a) Our PER-ET EER-ETD features design of the logarithmical increase of the restart period with the number of iterations, which guarantees the convergence the original fixed point of ETD, with both the variance and bias errors vanishing sublinearly. However, T-ETD is guaranteed to converge only to a pnncatton-lenggt-deeeeeee point, where the convergence obtained by treating the truncation length constant. careful review of the convergence proof indicates that the variance term scales exponentially fast with the truncation length, and hence the polynomial efficiency not guaranteed as the truncation length becomes large. (b) Our convergence rate for PER-ETD does not depend on the cardinality of the state space and has only polynomial dependence on the mismatch parameter of the behavior and target policies. However, the convergence rate in /Zhan & Whiteson (202T) scales with the cardinality of the state space, and increases exponentially fast with the mismatch parameter of behavior and larget policies. (c) This paper further studies PER-ETDOM and the impact of À on the converge rate and variance and bias errors, whereas Zhang & Whiteson (2021) considers further the application of T-ETD the control problem.
fixed
BACKGROUND AND PRELIMINARIES
2.1 MARKOV DECISION PROCESS
We consider the infinite-horizon Markov decision process (MDP) defined by the five tuple (S, A, r, 7)7.. Here, S and A denote the state and action spaces respectively, which are both as- sumed to be finite sets, r S A -> IR denotes the reward function, P S x A A(S) denotes the transition kernel, where (SS) denotes the probability simplex over the state space S, and y E (0, the discount factor.
A policy : S + ((A) of an agent maps from the state space to the probability simplex over the action space A. i.e., [[ass) represents the probability of taking the action a under the state At any time f. given that the system is at the state the agent takes an action with the probability (ar)s)). and receives a reward r(st, az). The system then takes a transition the next state $t41 at time ++ 1 with the probability P(s 1 oz).
For given policy म, we define the value function corresponding to an initial state sp E S as (s) = E 1 7'r(s,, [s) = s, x|. Then the value function over the state space can be expressed a vector Vj (V=(1), V2(2),... V=(())) E gls!, Here, V, deterministic function of the policy æ. We use capitalized characters to be consistent with the literature.
When the state space is large, we approximate the value function V, via a linear function class as Ve(s) = o (s)6, where @(s) E R denotes the feature vector, and 0 E Rd denotes the parameter vector to learned. We further let + = [c(11,, (6(2..... ((S)) denote the feature matrix, and then Vo = Φ0. We assume that the feature matrix + has linearly independent columns and each feature vector has bounded fn-norm, i.c., [ I Bo for all s E S.
2.2 TEMPORAL DIFFERENCE (TD) LEARNING FOR ON-POLICY EVALUATION
In order evaluate the value function for given target policy (i.e., find the linear function approximation parameter 0), the temporal difference (TD) learning can be employed based on a sampling trajectory, which takes the following update rule at each time
0.+1 = 02 + ne (r(se, aq) + 700 (05++1) 0g ((s:)) ((st),
where 7) is the stepsize at time t. The main idea here is to follow the Bellman operation update to approach its fixed point, and the above sampled version update can be viewed as the so-called semi- gradient descent update. If the trajectory is sampled by the target policy t, then the above TD algo- rithm can be shown to converge to the fixed point solution, where the convergence is guaranteed by the negative definiteness of the so-called key matrix A == lim E [(T((s + 1) (()))) (s:)
3

---

Published as a conference paper at ICLR 2022
2.3 EMPHATIC TD (ETD) LEARNING FOR OFLICY EVALUATION
Consider the off-policy setting, where the goal is still to evaluate the value function for a given target policy æ, but the agent has access only trajectories sampled under behavior policy μ.. Namely, each time i, the probability of taking an action d, given 8, is p((a())). Let dy denote the stationary distribution of the Markov chain induced by the behavior policy μ., i.c., dy satisfies di d Pa- We assume that dz > O for all states. The mismatch between the target and behavior policies can be addressed by incorporating the importance sampling factor p(s, a) ={als) into eq. 1 to adjust the TD learning update direction. However, with such modification, the key matrix may not be negative definite so that the algorithm is no longer guaranteed to converge.
p(a]s]
In order address this divergence issue, the emphatic temporal difference (ETD) algorithm has been proposed by SSttton et al. (2016), which takes the following update
0(+1 = 8, + n:p(s;, Fi (r(s), ox) + 70, o(s(+1) 0 o(s)) ((s)).
(2)
In eq. 2 in addition to the importance sampling factor p. follow-on trace coefficient Ft is intro- duced as a calibration factor, which is updated as
Fr =
with initialization Fo = 1. With such a follow-on trace factor, the key matrix becomes negative definite, and ETD has been shown to converge asymptotically in Yu (203)) to the fixed point
0 (TTF( F(I - -)x) 4 Frx,
(4)
where F = Similarly, the ETD(A) algorithm can be further derived, which has the following update
f((S)) and f(i) dy (t) 1im E = 1).
1.+1 0, + mpp(s, ar) (r(st, at) + 70, ((s++1) 02 ((s:)) ex:
where e, is updated as c₁ -)p(s a--1 aa-1a-1--11- M and M, x1 (1-1)111))))) F,. where Mo
and eo = (())). It has been shown that with a diminishing stepsize YYu 2015). ETD(A) converges
to the fixed point given by 8% (Ø M(I -xPx))((1 (I- )b)
lrr. Φ M(I -
where M diag(m((), m(2).... m(())) m(([))) and m(i) (1) lom
E [ i].
2.4 NOTATIONS
For the simplicity of expression, we adopt the following shorthand notations. For fixed integer b, let S7. == 51(b+)+77 af == (((b+))++ P.
=sa)ls) and o. o(s7). We also define the filtration F; Further, let Tx E [8| where Ta rs) (s, Let P₂ [| where Pa (s'(s) EnEA ((a)s) a). For matrix M NXN M(s.) denotes its s-th row and M(...) denotes its s-th column. We define BB = s(als)
(5o. do. $1, (((++))+
as the max, [1)( 2 as the upper bound on the feature vectors, and define Pmar max [(ass) maximum of the distribution mismatch over all state-action pairs.
PROPOSED PER-ETD ALGORITHMS
Drawbacks of ETD: In the original design of ETD Suttonn al. 2016) described in Section 2.3 the follow-on trace coefficient F, is updated throughout the execution of the algorithm. As a result, its variance can increase exponentially with the number of iterations, which causes the algorithm to be unstable and diverge, as observed in Hallak et al. (016)) (also see our experiment in Section 5)
In order to overcome the divergence issue of ETD, we propose to PEriodically Restart the follow-on trace update for ETD, which we call as the PER-ETD algorithm (see Algorithm [T] At iteration t, PER-ETD reinitiates the follow-on trace and update for b iterations to obtain an estimate F.b where we call b as the period length. The emphatic update operator at is then given by
T:(0) F² P.P.o
F.P.o
(5)
4

---

Published as a conference paper at ICLR 2022
Algorithm PER-ETD(())
1: Input: Parameters T, b, and 1).-
2: Initialize: 0g
3: for ( =0 0, 1, T do
4: F update: F7 ?ip FT + 1, where r = ",l.....b b- and FP = 1;
5: 0 update: dc+1 = ll (0, + n F pi(r + 70, o. 02 o))
6: end for
and PER-ETD updates the value function parameter 0g as 0t+1 = ITe (0.- 1/6 ((o) where the projection onto bounded closed convex set + helps to stabilize the algorithm. It can be shown T(0) where T(0) ($FFC F(1 7Pr)) 0 4 Fr.. The fixed
that oo [[T,(0) point of the operator T(0) is 6" defined in eq. which is exactly the fixed point of original ETD. Definition (Optimal point and e-accurate convergence). We call the unique fixed point 0 of T() as the optimal point (which the same as the fixed point of ETD). The algorithm attains an e- accurate optimal point if its output OT satisfies |0r 1 S.
The goal of PER-ETD is to find the original optimal point 0" of ETD, which is independent from the period length b. Our analysis will provide guidance to choose the period length b in order for PER-ETD to keep both the variance and bias errors below the target e-aceuracy with polynomial sample efficiency.
Algorithm PER-ETD(A)
1: Input: Parameters T, and T)--
2: Initialize: 0g- 0.
3: for t = 0, 1....... T do
4: Set F,00 M and ef of
5: for = 1..... do
6: FT= Pi F 1, MI = X (1-1) of = = - - + MI 0z
7: end for
8: 8 update: 0.+1 Ie (0, + nelk (rl + 70, 05 0T o8) ett)
9:
end for
We then extend PER-ETD(O) to PER-ETD(A) (see Algorithm 2 which incorporates the eligible
trace. Specifically, at each iteration i, PER-ETD(A) reinitiates the follow-on trace F; and updates together with M, and the eligible trace for b iterations to obtain estimate ef. Then the emphatic update operator given by
(0) ple (o) 1
T 0 pirtect
(6)
and the value function parameter 0, is updated 0.+1 TT (0: TT (0.)) It can be shown that
limo- E 7. (0) [ [
= T where T^ T T - (I
)P which takes unique fixed point 87 as the original ETD(A). The optimal point and the e-accurate convergence can be defined in the same fashion as in Definition It has been shown in Hallak et al. (2016) that 6% is exactly the orthogonal projection of V, the function space when
1, and thus is the optimal approximation to the value function.
4 FINITE-TIME ANALYSIS OF PER-ETD ALGORIHTM
4.1 TECHNICAL ASSUMPTIONS
We take the following standard assumptions for analyzing the TD-type algorithms in the literature (Jiang et al. 2021 Zhang & Whiteson, 2021 Yu 2015).
Assumption (Coverage behavior policy). For all s E and a E A. the behavior policy μ satisfies u(als) ) > 0 as long (als)) >
5

---

Published as a conference paper at ICLR 2022
Assumption 2. The Markov chain induced by the behavior policy is irreducible and recurrent.
The following lemma on the geometric ergodicity has been established.
Lemma 1 (Geometric ergodicity). (Levin & Peres 2017 Thm. 4.9) Suppose Assumption 2 holds. Then the Markov chain induced by the behavior policy p has a unique stationary distribution dp over the state space S. Moreover, the Markov chain is uniformly geometric ergodic, ie., there exist constants Cm 2 and 0 X < such that for every initial state so E S, the state distribution (s,(()) = (8: 8|80) after transitions satisfies | - dulli S CMXX'.
4.2 FINITE-TIME ANALYSIS OF PER-ETD(O)
In PER-ETD(O), the update of the value function parameter is fully determined by the empirical emphatic operator (8) defined in eq. ( Thus, first characterize the bias and variance errors of (0), which serve the central role in establishing the convergence rate for PER-ETD(())
Proposition 1 (Bias bound). Suppose Assumptions andd Then we have
E (
(1.).) [r-1]11]] C (Bollo. 8-112 + Capproz) c²:
where Capprox = 40 - V oo is the approximation error of the fixed point, & = max {r.x} x} < 1, BB max, (0(() 11, and C2 is constant whose exact form can be found in the proof.
Proposition [ characterizes the conditional expectation of the bias error of the empirical emphatic operator (0). Since { = max (r, x3 1, such bias error decays exponentially fast as increases. Proposition 2 (Variance bound). Suppose Assumptions and hold. Then we have
O(1)
if 22 Pinax < 1,
E |
Fo so²,
where 0²
O(b),
if 72 Pmas 1,
(7)
(62 Pmnx) )9).
if 72 Pinax 1.
where (-) is with respect to the scaling b, and Pmaz maxs,a p(als)
s(als)
Proposition 2 captures the variance bound of the empirical emphatic operator. It can be seen that if the distribution mismatch is large (i.e., 72 Pmaz > 1), the variance bound grows exponentially large as 6 increases, which is consistent with the finding in Hallak al. (2016). However, below, as long as b controlled to grow only logarithmically with the number of iterations, such variance eтror will decay sublinearly with the number of iterations. At the same time, the bias error can also be controlled to decay sublinearly, so that the overall convergence of PER-ETD can be guaranteed with polynomial sample complexity efficiency.
show
Theorem 1. Suppose Assumptions Aad holld
hold. Consider PER-E PER-ETD(O) specified in Algorithm ! O (2) and suppose the period length and the projection set O are properly
Let the stepsize chosen (see Appendix [2.3 for the precise conditions). Then the output Or of PER-ETD(O)) falls into
the following two cases.
(a) If < then E |||0 0 11
< 10(1 (+)
(b) If Pmaz > 1, then E |||0r 6* < O (1t), where 1//log (2 Pmax) + 1) < 1.
Thus, PER-ETD(O) attains an e-accurate solution with Ö (+) samples if 7² Pmaa < 1, and with
Ô ) samples if 22pmmaz >
Theorem captures how the convergence rate depends on the mismatch between the behavior and target policies via the parameter Pmex (where Pmaz 2 1). (a) 2
Pmaa I 1, i.c., the mismatch is less than a threshold, then (ER-ETD(O) converges at the rate of Ô (7), which is the same as that of on-policy TD learning (Bhandari al. 2018). This result indicates that under mild mismatch < Pmaz < 1//², PER-ETD achieves the same convergence rate as on-policy TD learning. (b) If 72 Pmar 2 1, i.e., the mismatch is above the threshold, then PER-ETD(O)) converges slower

---

Published as a conference paper at ICLR 2022
rate of Ö (Tt) because 1. Further, the mismatch parameter Pmoz gets larger, the converge becomes slower, because a becomes smaller.
Bias and variance tradeoff: Theorem I also indicates that although PER-ETD(0) updates the follow-on trace only over a finite period length b, it still converges to the optimal fixed point d*. This benefits from the proper choice of the period length, which achieves the best bias and variance tradeoff as we explain as follows. The proof of Theorem [ shows that the output By of PER-ETD(O)) satisfies the following convergence rate:
E [1|0T - 11]] S SO
[10a
+
+ +0 (5))
(8)
T
T
variance
bias
If 7 Pmaz I 1, then x² in the variance term in eq. satisfies o² S (b) as given in eq. 7 which
so that both the variance and the bias terms in eq. achieve the same order of O which dominates the overall convergence.
increases at most linearly fast with Then we set = lox T Tog(1/E)
If 72 Pmax > 1. then o² in the variance term in eq. satisfies x² = O ((>2Pmaz))) )*) given in eq. 7) Now, we need to set b as b = O "eg(7"Pmees P Hlog((/E) where the increase with log 7 has a smaller coefficient than the previous case, so that both the variance and the bias terms in eq. (8) achieve the same order of O ( ). Such choice of b balances the exponentially increasing variance and expomentially decaying bias to achieve the same rate.
log(
4.3 FINITE-TIME ANALYSIS OF PER-ETD(A)
In PER-ETD(A), the update of the value function parameter is determined by the empirical emphatic operator T,*(0) (f) defined in eq. 6 Thus, first obtain the bias and variance errors of T,¹ (0), which facilitate the analysis of the convergence rate for PER-ETD(A).
Proposition 3. Suppose Assumptions 7 and hold. Then we have
IE
T: (1))
F
( Co.A (Bolle 0%112 + Capprow) 5
where Capprox = |100% - Vol is the approximation error of the fixed point, 5 = max(x; 7 < 1, BB max, [1)()] and Ch, is a constant given fixed X whose exact form can be found in proof.
The above proposition shows that the bias error of the empirical emphatic operator 7,((0) in PER- ETD(A) decays exponentially fast as b increases, because { = max {7, x} < 1.
Proposition
Suppose Assumptions and hold. Then we have (A
2 Fi-1 S o
2
where o = O (pinaz).
Compared with Proposition 2 of PER-ETD(()) Proposition f indicates that ETD(A) has a larger variance, which always increases exponentially with 6 when Pmaz 1. This is due to the fact that the eligible trace ei carries the historical information and is less stable than of.
Theorem 2. Suppose Assumptions 7 and 2 hold. Consider PER-ETD(A) (A) specified in Algorithm 2 Let the stepsize πt O
(2) and suppose the period length and the projection set O are properly
chosen (see Appendix E.3 for the precise conditions). Then the output OT of PER-ETD(2) satis- PER-ETD(A) attains an e-accurate
fies E [[|0T - 0%
where as Iog./z/Pmax)+1 )+1
solution with δ
samples.
2770X
Theorem 2 indicates that PER-ETD(A) converges to the optimal fixed point 0% determined by the lnfitite-length update of the follow-on trace. Furthermore, PER-ETD(2) converges the rate of which is slower than PER-ETDON (as a사 < due the larger variance of PER-ETD(A).
Bias and variance tradeoff: We next explain how the period length achieves the best tradeoff between the bias and variance errors and thus yields polynomial sample efficiency. The proof of
7

---

Published as a conference paper at ICLR 2022
Theorem 2 shows that the output 8y of PER-ETD(A) satisfies the following convergence rate:
||0r 0 0x| S O
[190-1211
+ ( + 0
T2
variance
bias
In eq. (.. of in the variance term takes the form o3 (pinar) as given in Proposition 4 We need
to set 6 = [ogl 3 (1g(( so that both the variance and the bias terms in eq. (9) achieve the
(og(T)
same order of O Tex ). Thus, such choice of b balances the exponentially increasing variance and exponentially decaying bias to achieve the same rate.
Impact of the eligible trace (via the parameter X) on error bound: It has been shown that with the aid of eligible trace, both TD and ETD achieve smaller error bounds (Sutton Barto 2018 Hallak et al.) 2016). However, this is not always the case for PER-ETD. Since PER-ETD applies finite period length b, the fixed point of PER-ETD(L) is generally not the same as the projection of the ground truth to the function approximation space. Thus, À changes from 0 to 1, depending on the geometrical locations of the fixed points PER-ETD(A)) for all (determined by chosen features) with respect to the ground truth projection, any value À s may achieve the smallest bias error. We illustrate this further by experiments in Section 5.2
5 EXPERIMENTS
5.1 PERFORMANCE OF PER-ETD(O)
We consider the BAIRD counter-example. The details of the MDP setting and behavior and tar- get policies could be found in Appendix A.I We adopt a constant learning rate for both PER- ETD(O) and PER-ETI (ER-E and all experiments take an average over 20 random initialization. We set the stepsize r = 2-9 for all algorithms for fair comparison. For PER-ETD(O), we adopt one- dimensional features Φ (0.35, 0.35, 0.35, 0.35, 0.35, 0.35, 0.37) T. The ground truth value func- tion V = (10, 10, 10, 10, 10, 10, 10) and does not lie inside the linear function class.
1000
PERTTEES PERCTIOO
RTD ETOYL FORETOCC
PERCCTEE
reReTions h-10
000
PER-ETOIO
FOR 10/CL wil
(a) Comparison of TD, ETD, PER-ETD(O)
(b) Tradeoff between bias and variance by
Figure 1: Performance of PER-ETD(O) and comparison
In Figure [a), compare the performance of of TD, vanilla ETD(O) and PER-ETD(()) with b 2, 4, 8 in terms of the distance between the ground truth and the learned value functions. It can be observed that our proposed PER-ETD(() converges close the ground truth at a properly chosen period length such as b = 4 and b = 8, whereas TD diverges due to no treatment on off-polic data historically, and ETD (0) also diverges due to the very large variance.
In Figure [b), we plot how the bias and the variance of PER- FER-ETD(O) change as the period length b changes. Clearly, small (e.g., b = 4) yields a small variance but a large bias. Then as b increases from 4 to 6, bias is substantially reduced. As b continues to increase from 8 to 20, there is significant increase in variance. This demonstrates a clear tradcoff between the bias and variance as capture in our theory.
5.2 PERFORMANCE OF PER-ETD(A)
We next focus on PER-ETD(A) under the same experiment setting as in Section 5.1 and study how affects the performance. We conduct experiments under three features o,, P2 and o specified
8

---

Published as a conference paper at ICLR 2022
PERCTROL D 8-4
300
CUDIO PE
PERETOO 45,
344
PEBCTTO-O
24-
POSEEDIE
PID CTDJ
PEREETOULL
POH (02)
300
200
281
0.
0.
2.0
3.5
X07
(a) Feature 41
(b) Feature 42
(c) Feature 4a
Figure 2: Performance of PER-ETD(A) and dependence features
Ve projedtin
Vi procedtion
A-1
Amps
increase
1-24
A- 0...05.000 02
Increases
(a) Feature
(b) Feature 42
(c) Feature 43
Figure 3: Fixed points of PER-ETD(X) and project of the value function. (a): 0 lies in I-dimensional Euclidean space IR² along horizontal direction; (b), (c): 0 lies in 2-dimensional Euclidean space IK?2.
Figure 2 shows how the bias error with respect to the ground truth changes as increases under the three chosen features. As shown in Figure (a), (b), and (c), À 0, and some value between 0 and respectively achieve the smallest error under the corresponding feature. This in contrast to the general understanding that À In fact, each case can be explained by the plot in Figure under the same feature. Each plot in Figure Billustrates how the fixed points of PER-ETD(A) are located with respect to the ground truth projection (as V* projection) for b = 4. Since the period length b is finite, the fixed point of PER- ETD(1) is not located at the same point as the ground truth projection. The geometric locations of the fixed points of PER-ETD(A) for 0 < X corresponds to the distance between the fixed point of PER PER-ETD(A) and the V, projection. Then under each feature, the value of that attains the smallest error with respect to the V₂ projection can be readily seen from the plot in Figure 3 For example, under the feature 23. Figure 3 (c) suggests that neither X nor 1, but some between 0 and I achieves the smallest error. This explains the result in Figure 2 (c) that À = 0.4 achieves the smallest error among other curves.
in Appendix A.2
typically achieves the smallest error.
are determined by chosen features. The bias
As summary. our experiment suggests that the best A. under which PER-ETD(A) attains the small- est error, depends on the geometry of the problem determined by chosen features. In practice, if PER-ETD(A) used as a critic in policy optimization problems, may be tuned via the final reward achieved by the algorithm.
6 CONCLUSION
In this paper, we proposed novel PER-ETD algorithm, which uses periodic restart technique to control the variance of follow-on trace update. Our analysis shows that by selecting the period length properly, both bias and variance of PER-ETD vanishes sublinearly with the number of iterations, leading to the polynomial sample efficiency to the desired unique fixed point of ETD, whereas ETD requires exponential sample complexity. Our experiments verified the advantage of PER-ETD against both TD and ETD. Moreover, our experiments of PER (ER-ETD(A) illustrated that under the finite period length in practice, the best À that achieves the smallest bias error is feature dependent. We anticipate that PER-ETT can be applied to various off policy optimal control algorithms such as actor-critic algorithms and multi-agent reinforcement learning algorithms.

---

Published as a conference paper at ICLR 2022
REFERENCES
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning, pp. 30-37. Elsevier, 1995.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Proc. Annual Conference on Learning Theory (COLT), pp. 1691-1692. PMLR, 2018.
Zaiwei Chen, Sheng Zhang. Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke Perfor- mance of q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprint arXiv:I905.1144: 2019.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td (0) with function approximation. In Proc. AAAI Conference on Artificial Intelligence (AAAI), 2018a.
Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two- timescale stochastic approximation with applications to reinforcement learning. In Proc. Annual Conference on Learning Theory (COLT), pp. 1199-1233. PMLR, 2018b.
Peter Dayan. The convergence of TD (A) for general X. Machine learning, 833-4)344-362. 1992.
Peter Dayan and Terrence J Sejnowski. TD (A) converges with probability Machine Learning, 14 (3):995-301, 1994.
Sina Ghiassian, Banafsheh Rafice, and Richard S Sutton. A first empirical study of emphatic tempo- ral difference learning. In Proc. Advances in Neural Information Processing Systems (NeurIPS), Continual Learning and Deep Networks workshop, 2016.
Harsh Gupta, R Srikant, and Lei Ying. Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning. Proc. Advances in Neural Information Pro- cessing Systems (NeurIPS), 32:4704-4711, 2019.
Assaf Hallak, Aviv Tamar, Rémi Munos, and Shie Mannor. Generalized emphatic temporal differ- ence learning: Bias-variance analysis. In Proc. AAAI Conference on Artificial Intelligence (AAAI), 2016.
Bin Hu and Usman Ahmed Syed. Characterizing the exact behaviors temporal difference learn- ing algorithms using markov jump linear system theory. Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Ehsan Imani, Eric Graves, and Martha White. An off- policy gradient theorem using emphatic weightings. Proc. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Tommi Jaakkola, Michael I Jordan, and Satinder P Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural computation, (66):1185-1200 1994.
Ray Jiang, Shangtong Zhang, Veronica Chelu, Adam White, and Hado van Hasselt. Learning ex- pected emphatic traces for deep RI.. arXiv preprint 107.v:2217.004::: 2021.
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. In Proc. Annual Conference on Learning Theory (COL.T), pp. 2103-2203. PMLR, 2020.
J Kolter. The fixed points of off-policy TD. Proc. Advances in Neural Information Processing Systems (NeurIPS), 24:2169-2177, 2011.
Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic vari- ational inequalities, ii: Markovian noise and policy evaluation in reinforcement learning. arXiv preprint arX1v:2011.08434, 2020.
Guanghui Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer Nature, 2020.
10

---

Published as a conference paper at ICLR 2022
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
A Rupam Mahmood, Huizhen Yu, Martha White, and Richard S Sutton. Emphatic temporal- difference learning. European Workshop on Reinforcement Learning, 2015.
Jingjiao Ni. Toward emphatic reinforcement learning. Master's thesis, University of Alberta, 2021.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Proc. Annual Conference on Learning Theory (COLT), pp. 2803-2830. 2803-2830.PMLR, PMLR, 2019.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Sutton, Csaba Szepesvári, and Hamid Reza Maei. convergent o (n) algorithm for off- policy lemporal-difference learning with linear function approximation. Proc. Advances in Neural Information Processing Systems (NeurIPS), 21 2008.
Richard S Sutton, A Rupam Mahmood, and Martha White. An emphatic approach to the problem of off-policy temporal-differene learning. Journal of Machine Learning Research (JMLR), 17(1): 2603-2631, 2016.
John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal- learning with function approximation. IEEE transactions on automatic control, 42(5):674469)) 690, 1997.
Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Mo- dayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv:1812.0266 2018.
Yue Wang, Wei Chen, Yuting Liu, Zhi-Ming Ma, and Tie- Yan Liu. Finite sample analysis of the
GTD policy evaluation algorithms in markov setting. arXiv preprint arXiv: 180i:08800009922 2018.
Tengyu Xu and Yingbin Liang. Sample complexity bounds for two timescale value-based reinforce- ment learning algorithms. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 119. PMLR, 2021.
Tengyu Xu, Shaofeng Zou, and Yingbin Liang. Two time-scale off-policy TD learning: Non- asymptotic analysis over markovian samples. Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Huizhen Yu. Convergence of least squares temporal difference methods under general conditions.
In Proc. International Conference on Machine Learning (ICML), pp. 1207-1214, 2010.
Huizhen Yu. On convergence of emphatic cemporal-difference on Learning Theory (COL.T), pp. 1724-1751. PMLR, 2015.
difference learning. In Proc. Annual Conference
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. Proc. International Conference on Learning Representations (ICLR). 2020a.
Shangtong Zhang and Shimon Whiteson. Truncated emphatic temporal difference methods for pre- diction and control. arXiv preprint arXiv:2108.0533 2021.
Shangtong Zhang, Bo Liu, Hengshuai Yao, and Shimon Whiteson. Provably convergent two- timescale policy actor-critic with function approximation. In Proc. International Conference on Machine Learning (ICML), pp. 1 11204-1122 11213. PMLR, 2020b.
11

---

Published as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIALS
A SPECIFICATION OF EXPERIMENTS IN SECTION 5
A.1 EXPERIMENT SETTINGS
The BAIRD counter-example illustrated Figure which has 7 states and 2 actions. the first action (illustrated dashed lines) is taken, then the environment transitions from the current state to states 1 to 6 following the uniform distribution and returns a reward O; and if the second action (illustrated solid lines) is taken, the environment transitions from the current state state 7 with probability and returns a reward 1. We choose the target policy as (0[ss) = 0.1 and (1[s)) = 0.9 for all states; and choose the behavior policy ((O]s) 6/7 and (1]ss) 1/7 for all states. Moreover, we specify the discount factor = 0.99.
2
3
4
5
6
7 0.99
Figure 4: BAIRD example Sutton Barto 2018)
A.2 FEATURES FOR EXPERIMENTS IN SECTION 5.2
In the experiment in Section
we choose the following features:
Φ (0.35, 0.35, 0.35, 0.35, 0.35, 0.35, 0.37) ;
2 1000(000 ((0.3425, 0.0171) (0.1902, 0.4248) T. (0.1354, 0.76) (0.1357,0.7973)
(0.8674.0.8774) (0.5166, 0.9493) T, (0.3094, 0.8535) )
4 (0.51162,090013 (0.5128, 0.5999) (0.289, 0.4649) T, (0.3399, 0.5334)
(0.315, 0.2278) (0.667, 0.461) (0.3706, (..45)
A.3 COMPUTATION OF THE FIXED POINT OF PER-ETD(A)
In this section, we provide the steps compute the fixed point of PER-ETD(A) in Figure 3 We first define the matrix A and as follows
A == lim
E
Ae - -
: lim
E
cc (== (rr)))))
can be shown that, the fixed point of PER-ETD(A) algorithm is 0" = A-tc.
We next show how to derive the formulation of the matrix A and vector As will show later in
eqs. (5 (53) and (55). we have
A lim
E [A - (P))
(10)
f-
c lim
E [ct[F=-1] = B5rz,
(11)
1-00
where B, = lime
E [ and
Bs(s) λΦ Du. + (1 Fs 7180-1P
(12)
12

---

Published as a conference paper at ICLR 2022
where D DH.,r diag d. (s) iteratively by eq. (25) as follows
P(s F(Fi)) Fb diag(fo). and fo is determined
Jb dn + +Pp fo-1, with fo = dy.0-
(13)
Taking expectation on both sides of eqs.
(2) and
with respect to Fx-1 and letting + oo yield
f du PP 1o-1, with fo dus
(14)
B. X T D + (1 2) T Fb + 7AB with 3o = TTD D2
(15)
where f. == lim,- oc [L and F. diag(f)). The explicit formulation of Bb can be derived by applying eqs. (14) and (15) iteratively. We can then obtain and c by substituting the obtained
formulation of B, into eq. (10) and eq. respectively.
A.4 REPLOTTED FIGURES AND WITH VARIANCE BARS
In this subsection, we replotted Figures and 2 with variance bars (rather than error bands) in
Figures 3 and respectively.
1000
(ER c-4
Vanila ETD PER-ETD(O), b-1
PER-ETU()) 5
PER-ETD(O).
PER.ETD(S), b-2
PER-ETIIO)
19,0. Valb
PER ETD(3), b-1
PEREETII) 111
PER-ETD(U), b-b
PER-ETD(O). 2-
PER ETD(2), b
400
(a) Comparison of TD, ETD, (E)-ETD(O)
(b) Tradeoff between bias and variance by
Figure 5: Performance of PER-ETD(()) and comparison
PER ETDIL L-f PERETOIA
PERETOOOS
2001
25
PAREEDDEO PEB ETDDEDD
CTOVA (0)
PERETOIO
PENE 1OX0
PER ETDIE bot PaserDIc PER CTDO), bew
FEINE TD/0-4.
350
RER-ETDIR
PER ETDNG 9) hnd
PER-ETOOO
2000
808
(a) Feature Φ
(b) Feature 42
(c) Feature 43
Figure Performance of PER-ETD(A) and dependence on features
B MORE EXPERIMENTS
In this section, we conduct further experiments to answer the following two intriguing questions:
If the distribution mismatch parameter Pmaz changes, how will different approaches per- form and compare with each other?
Focusing on our algorithm PER-ETD, how do the choices behavior policy and target policy affect its convergence?
13

---

Published as a conference paper at ICLR 2022
250
5400
TD
Van lla ETD
Vanila ETD
200
PERETTD()). b-4
PER EEDIEE 3::4
PER-ETO(O),
ETD(C). 5-6
1.53
PER ETD() b-H
ETD(ET)))
103
100
0.0
0.2
0.1
0.6
0.8
1.0
0.2
0.4
0.8
x
(a) Omaz 1.17
(b) Pmaz 5.60
Figure 7: Comparisons of TD, ETD, PER-ETD(()) with different target policies
100
Pas -1
-117
850
Pes
350
Plar
300
Aeu 300-
280
200
Aus -4.20
250
5.00
250
Ploo
200
200
150
150
100
100
0
0.0
0.8
x107
X16
(a) b =
(b) b = 6
Figure 8: Performance of PER-ETD(O) under different target policies (marked by their different resulting distribution mismatch parameter Pmaa)) The behavior policy is kept the same.
400
Peu -112
Pes
350
Peu
Pess -129
Peur
-150
300
Pear -1.0
-225
250-
Peua -4 30
200
200
150
150
100
50-
0.0
0.2
0.4
0.6
0.8
1.0
x1107
(a) = 4
(b) 6
Figure 9: Performance of PER-ETD(0) under different behavior policies (marked by their different resulting distribution mismatch parameter Pmoa). The target policy is kept the same.
We focus the MDP environment in Appendix A.] In our experiments, the performance of every algorithm is averaged over 20 random initializations and the error band our plots captures the actual variation of the performance during these experimental runs (which be viewed as the variance the algorithms).
In Figure 7 we consider two settings with the distribution mismatch parameter Pmae 1.17 and 5.60, respectively, and compare the performance of three off off-policy algorithms: TD, vanilla ETD and our PER-ETD, More specifically, choose the behavior policy p(]|s) and (((2s))
14

---

Published as a conference paper at ICLR 2022
for all states, and choose two target polices, whose probabilities to take the second action are 0.167 and 0.8, respectively, on all states. (Then their probabilities to take the first action are determined automatically through T [[]]s) + (2]s) 1). Therefore, the maximum distribution mismatch Pmaz for the these two target policies are 1.17 and 5.60, respectively. Figure 7 (a) shows that under only slightly mismatch (i.e., Pmer 1.17), TD suffers from large convergence error (i.e., the error with respect to the ground truth value function at the point of convergence) and converges slowly. Vanilla ETD converges with the fastest rate and achieves a smaller convergence error than TD, but suffers from relatively large variance. Our PER-ETD achieves a better tradeoff between the convergence rate and the variance (faster rate than TD, almost the same convergence error as ETD but with smaller variance). Figure 7 (b) shows that under large distribution mismatch (i.e., Prerr 5.6), TD does not converge, and vanilla ETD experiences a substantially large variance. However, our PER-ETD still convergences fast as long as the period length b is chosen properly, e.g., b = 4, 6, 8. Further note that PER-ETD has smaller convergence error as the period length increases, but the variance gets larger, which are consistent with our theorem.
In Figure g we focus on our PER-ETD, and study how different target policies affect the per- formance. We choose the same behavior policy as the above experiment, i.e., μ(l(s)
and () for all states. We choose 5 target polices, whose probabilities take the second action are 0.167, 0.2, 0.4, 0.6, 0.8 for all states, respectively. These different target policies affect the per- formance via their resulting distribution mismatch Pmas 1.17, 1.40, 2.80, 4. 4.20, 5.60, respectively. For both b = 4 and b 6, Figure X indicates that larger mismatch causes slower convergence rate, larger convergence error and larger variance, which agrees with our theorem.
In Figure we also focus our PER-ETD, and study how different behavior policies affect the performance. We pick the target policy to be (11 8) 0.1 and π (2)ss) 0.9 for states, and different behavior policies with (=2[s) 0.2, 0.4, 0.6, 0.7 and 0.8 for all state, respectively. These different behavior policies affect the performance via their different resulting distribution mismatch Pmoz 1.12, 1.29, 1.5, 2.25, 4.5, respectively. Figure clearly demonstrates that larger distribution mismatch results in slower convergence rate, larger convergence error and larger variance, which is in the same nature changing the target policy shown in Figure and is consistent with our theorem.
C SUPPORTING LEMMAS
The following lemma is well-known. We include for the convenience of our proof.
Lemma Consider a transition matrix P E R N where E3 P(t.i) = for all i and S
P(S) $1 for all j. We have for any E N, || |M lo = 1, and [1(PT)* =1
Lemma 3. Consider 0 p.g < 1, with # 9. We have Σk qa I 1 where
< = maxxpp
Proof of Lemma If q, we have
k
n-1 <
p
k=0
m=0
Without loss of generality, we assume p < and = q. We have
n-1 Σ
Σ ( - 1 1-p/q
n-1
1 (p/g)"
9"
1
1p
k=
k=0
Lemma 4. Consider a matrix P E NNN where E3 P(is) S C for all i and 0 S P(is) S 1 for all j. and a positive vector a where N and x; 2 for all We have
1 Pr < TT.
15

---

Published as a conference paper at ICLR 2022
Proof of Lemma 4
We have
1 Pr = Σ
Piçzi=
Σ Ii ISiN
Σ ISISN
Pis
Pij
SC
Σ ISISN
= C1
ISUJNN
Lemma 5. Consider diagonal matrix D [[5))(ss where D diag(d d(2). ((())
transition matrix ||Ssi|Si where Σ, P.. for all 2....... |S| and Pa. 2 for all j. and an arbitrary vector E ERRS. We huve
| DPxll2 S Bolld||||ET||.
Proof of Lemma
We have
④ D= (d==) ((())))(()))))(((()))
and
(0) DP) (sN) - Ps.
which implies
$ DPT =
Ex(s) >x(s) )
Σ
Σ x(s) d(5)o(3).
Taking & norm on both sides of the above equality yields
② T DDIl1
Σ
(s.)
d(3)o(5)
r Ps..
[d(3) [1)(5))
BB Bolldl11
Σ ass))
BBlld|bbl==l max Σ Pa.
Lemma 6. Consider diagonal matrix E R|S)x(S| where D (())dd))))(()....... d(S)))
transition matrix P [|S)((s| where E, Po.j for all i 1, 1,2.....15. and P.₃ 2 for all j. matrix Q E R|S| that satisfies 0 < Q < C...j where C > 1 is constant, and an arbitrary
vector E R [S) We have
trace (Qm D) s CM B3ld
and.
trace (P"Q"TD"" D) < CM B3ldd]1,
for any and N2o.
Proof of Lemma 6 For any given 2 m 2 0 and 2 0,
( ((Q)mp"-0 Janl ((Q"))a)) (p"44 ( )(.)))) - (1( (PT) 1o0 (16)
16

---

Published as a conference paper at ICLR 2022
where (i) follows from the Hölder's inequality.
Furthermore, for the term of (P" )(.))) we have,
(("""0 (--)) bl PM Ioo (10 Dosilloo @ |1 (oooT)(so (oolloo
where (i) follows from Lemma Moreover, for the ith entry of (& T ((.))) we have
((.)) = (0i) T Φ0) = |+())lall)()111 - B²
The above uniform bounds over all i imply that [ )(,)) B Hence,
[! (1,))llo I B).
Substituting the above inequality back into eq.
[6.. we obtain
[(Q pa T (ant < (Q) (a,ll S (GP
CCn B Σ P-- = Cm
CB, B²,
(17)
where (i) follows by the condition of Q, (1,)) & CP(s)) for all i,
Finally, we have
trace pmm T D) = Σ d(i)(Qm pm )a. - Σ [Q pm Taol
s |dl|l max (Q p"d""""" )
0 B Idd|l,,
(18)
where (i) follows from eq.
17
Following steps similar to those eqs.
16 to 18 we can obtain
trace (m" D) s Cm BLldd]n.
Lemma 7. The operators T(0) and (0) satisfy the generalized monotone variational inequality.
There exist Po: Px > 0, s.t., (T) (*) 2 poll0 0- .and (T) 0 0*) 2 1x1 8" 113
Proof of Lemma 7
We have
(T(0),0 0-) (2) ((T F(I 70 (0) 0*)
(0 - 07 (4) F(1 - 7P))) (0 0*)
2 Amin (Φ) F(1 - -P+)4) |00 0- 12
(19)
where (i) follows from the definition of the and 6*.
Recall that F(I yPa)) is positive definite Sutton et al. 2016 Mahmood al. 2015) and & has linearly independent columns. For any x E 12" with x: 7 0, we have कx. 7 0 and
T T F(I - >Px) (Φx)
- (()=))a)( 0.
The above inequality shows that $ T FF - PP.) is positive definite and thus, there exists μr such that μ4 Amin T F(I (b)
Following steps similar those in eq. 19 and applying the positive definiteness of M(T -(Px)-((L -1- (Sutton et al. 2016 Mahmood et al. 2015) yield
(T) 0*) 2 aa 0 0-
17

---

Published as a conference paper at ICLR 2022
Lemma 8. The operators T()) and (#) satisfy the Lipschitz condition. There exist Lo, LA 0,
such that, [|T(6;) T(02))l2 Lo |00 02112, and [T>()]) ( Tx1101 02112.
Proof of lemma
8 We have
- - |1 - (01 02)112
I |1 ([] - 101 02112-
(20)
Let Lp = - eq. 20
completes the proof of the first inequality in the Lemma.
Let 1,_ == | M( ((TT-)Pp)--11 7 112,, the steps similar to those in eq. (20) finalizes the proof of the second inequality in the Lemma.
Lemma 9 (Three point lemma). Suppose θ is closed and bounded subset of IR and 0* is the solution of the following maximization problem, maxége 1) (G,0) + 21 0u 12. where G E IRd is a vector. Then, we have, for any 0 E O.
1 (G, 0" 8) + 2 100 1
2 100
-01
2 110 013
Proof. The proof can be found in Lan 2020)
D PROOFS OF PROPOSITIONS AND THEOREM FOR PER-ETD(O)
D.1 PROOF OF PROPOSITION
First, by the definition of (9)),, we have
E
(1.)
Fr-1]
ΣΣΣ
aES s'ES
PP (0)
8, 8, 5, =0,00 b+1 = 1)) E Fr-1,, =8, =. 0, 8 b+1 8²]
F,-1,
ΣΣΣP(
#ES JEES
E (0
a, b+1 s'
Pd (s)0, r(s,a)-70) -
70 (s')0e)
AEES
E F 5 =
Σ (s) = s F(-1) E [F 5 =s] o(s) (s)o: T[Px - (s] -r,r (21)
SS
where (i) follows from the law of total probability, (ii) follows from rewriting s' F(11, and (iid) follows from the facts that F only depends on (so, dg, $1, d1.... s1(+1)+b-1 1)6-1) and the chain is Markov.
P (s) s, a a, S b+1
Recall the definition of T(0,), we have
T(0,) = Φ T F [[I- (P))o, -ra]
= Σ ((s) (T (8), - - -1.r -ra (1)).
(22)
SES
Equations 21 and 22
together imply the following.
T(0,)
f. Fi-1] = Σ (f(s) P (s = s| B B(F =
18

---

Published as a conference paper at ICLR 2022
(s)0, - 7 [P, 0r - Txx (8)) d(s)
(f(s) - -((s)) (o (s)), 7 [P (s.)) Os rx(s)) d(s)
#ES
Σ (f(s) f((()) (1=>>x; Db: r=), d(s).
#ES
where in (i) We define [o(s) P (5) Fi E PP o = =]. Taking l norm on both sides of the above equality yields
((0))) E To((0.) Fi-1) (r-00) ||
Σ (f(s) [o(s)) (1I -(---p;) $0. - -ra), d(s)
Σ 15()) fb(5) (((I-~>++) :8. r=7,1 ((b(s)]1)
SES
S max (1](())12} max {l((I - yP7) $0. - 13 Σ 15(s) - [a(o]]
#EB
sES
SES
Bl - 7P=)00, - x ll fulla-
(23)
We next proceed to bound |lf full2. Consider fo(s), we have
fo(s) = P (s) = 1 [F 1 = Fr1l
P ( s(F(-1)
Σ P (s
6-1 = 8, 04
b-1 = =|ss = ss Fi
SES,aEA
E [YpE
1- 1pb-1 + 1 F 56 = 8,88
3, 3,46-1 b--1 -
a]
(8) Fi 1)
IP (s) h-1 = F(-) (((l3)) a)
T(ol3)
1 Σ
E
Fr-1, 88 F
b-1
PP (s} = s= F(-1)
((a(s)
BES,aEA
= P (s) = F| +7
>
[F.
F b-1 s].
RES
where (1) follows from the law of total probability and (ti) follows from the Bayes rule and the facts
that Fo only depends on the chain elements (sf, (o),af, .?...... b-1 1) and the Markov property.
Define ds)((s) = (s = F.-1), the above equality can be rewritten as
fs(s) ds.b(s) + 7 > (1)
(24)
Since eq. 24 holds for all E S, we have
fo dn. b + PT fo-1
(25)
Note that for ff we have the following holds (Sutton et al. 2016 Zhang et al. 2020a)
f= dr + PP S.
(26)
Equations 25 and 26 imply
f f- fo dr - dub + PPT (f - fo-1).
Applying the above equality recursively yields
b-1
1- f = - (T (d,, - P - fo).
T=0
19

---

Published as a conference paper at ICLR 2022
Take l norm on both sides of the above equality, we have
If - folli =
( (dp - =) -fo)
fo)
)T (dd, d (ff folll
MIMMINM
MiMM
WV WV wn M4
y" (
R y1l, ld,, dubb-ila + ( If - foll
7 11d - dnbbrlly 112 +72 foll
CarT + foll2
CMe + + + llfll)),
(27)
where (i) follows from Lemma
2 (ii) follows from Lemma D and (ii) follows from Lemma 3 and
defining 5 = max max(x:7>
To bound the term [] PPx
/00- Txx Pll. we proceed as following
( ||(T 7P+)( - V+)
II(I Pb:)
10
= [I(T 7P=) - 50 + $0" - -V>)l 00
S ||I ->P= (1 - $000 11x + +1000 Vol)
(4)
$ (1 + Be - 112 + (1 7) Eapprox
(28)
where (i) follows from the fact V2 (I - 7 ?P>) p and (ii) follows from the facts that ||z
yP max; (1- - (Px)(e.) + + (Px) (1,)) 11 cappror == |100" Vz loo and 1
||00;- $00 11 = max e (s) - 0-) S Bol10, - 1|
#ES
Substituting eqs.
27 and 28
into eq.
yields
[(()) - E [T(00.)
Fi-1 11, < (B3 - 00 1l| + B&t approo)) (1 77) ( + 70 + -1/(11))
(Cus
S C, (Bol - 0001 ||2 + cappror) 5t
where { = max {x.7} and C. = B1 + 7) 1--7 + (1+ Ilfll1)
D.2 PROOF OF PROPOSITION 2
According to the definition of ((.),, we have
E
(T((0))
Fi
=E (D) (0T 02 r -00 -0TT0 )²
ob P (s s. of a, ot b+1 F((F(-1) o(s) - rs(,,)) -00T -7'))
1 2 110 [
SES aEA SEES
[ls) E [
F 8 s a, الو = s
(88)
ΣΣ
P (F)
(0 ((s) r(s, 0) -0.T0(s))
SES OSSESS
20

---

Published as a conference paper at ICLR 2022
| (a
(2(sss) [FF)) Fi-1, -
s. / = =a, a, St = s'
Σ (s = = E [1 = |1(
क (a BEA m(lls)
P( 1s, a) () - - r(s, ()))0 76 (s')0:)²
(29)
where (i) follows from the law of total probability and (ii) follows from the fact that P is indepen- dent from previous states and actions given sp-
Note that [|x())l22 I B& for all S, rss,a) Tmaz for all (s. E S x A, and ||0112 S Bg for all t due to projection. We have
(s)0 r(s, a) - 70 (5')0,)2 s 2((((s) - (o('')) 0,1 + 2r a)
S 21(((1)) - -0003)11110 2rmax
s 4( ((1(()) +1 + 2r
- 4(1 4(1+~2)BB33 + +2
(30)
We also have
n (als) p(alss ss, a) S Pmaz
P(s||s,
ΣΣ x(cls)P(s((ssa) = -mao
RESSESS
aEAVES
Substituting the above two inequalities into eq. (29 yields
F.(0.) || Fi-1
E
S Pmaz (4(1+>2) + 2maax) B Σ P (s = =( B B ((Ft) =s] (31)
SES
Define (s) = TP (s: = B F s s| dr (5 (())
s].
We have the following equations hold for (s)):
ro(s) = P(s =sFF-1)E (rph b-1 F 1 + 1) F, 1, 5t =
ds.((s)E [1 pp h-1 1 + 7²2 (p: b- 1000-1))(F))) (F 11
=d,((8) 2xdp. [pt 1-1 p26 | s = 8]
b, (pp ( F
(32)
For the second term in the RHS of eq.
we have
(s)
Ppt
F =
(s)
Σ
(s h-1 = 3, h-1 a =. F(-1)
P
RES,aCA
Fb
- F 5/ = 8, 8
b-1
8, ā]
(4)
d (s)
dp,b-1 ju P(s
[p
1-1 Fbb
Fr-1, = 8, b
8, a
b-1 = ū
ds
(114)
Σ
dn, d (3))[((]))]
T(p3)
E
[F[-1
F
Fe 8t
b-1 8
((a
RES
Σ (8(3) (
FT-1,
aES
(1))
(P. fb-1)s>
(33)
21

---

Published as a conference paper at ICLR 2022
where (i) follows from the law of total probability, (ii) follows from the Bayes rule, (dit) follows from Markov property and (iv) follow from the definition of fo which is given above eq. (3)
For the third term the RHS of eq. (32 have
(s) [Pp 6-1 1 o
dub(s) Σ
P ( (s--1-
3, ag
1-1
à a.s = Fi-1)
aES,ãEA
E [Ptt 1 1 F1
8, 8, 1-1 8, 4z b-1 ā)
(10
(s)(())
du (5)
B [ot Ft ) F Fo-1= S = =8,88 8,88 6-1 =- 8, dz [
dn)(s)
3
(a(s) p?(a(s)
Σ (3)=
E [[F (F Fc,, sp-1
8ES,ãEA
PAIT (1)(())3)
8ES
Po..7o-100 1)89
(34)
where (i) follows from the law of total probability, (ii) follows from the Bayes' rule, and in (iii)
we define Pa. E S where (Pn,T)s,5 Eaed [(a
(a (ss|s, a) for each (s, 8) E S S.
Substituting eqs.
33 and 34 into eq.
32 yields
Tb dp,b + PT fo-1 + 72 PT
H. Tb-1
We also have the following inequality holds
1 rb 1 d2,b + +7y1 T P. fo-1 + 721 pT Tb-
+1+2y1 fo-1 + 1 P
(8) $ 1 2 fo-1 1 + 7² Pmaz 1 rb-1-
(35)
where (i) follows from 1 TT = (P^1) T T and (ii) follows from the facts that rb-1 2 0 and
22 (ā P(s|3, a) vec
(als)
PP a.3t = (Pu,x1) = vec
Σ
Pmax
(
m(ālz)
BES acd
AEEA
Recursively applying eq.
35 yields
1J rb $
(22 Pmax) (1 fo-r-1) (>²Pmax) )'1 1'1n TTn
(?2 Pinax) (1+ f0-7-1) + (7² (r2Pmaxx).
(36)
where (i) follows from the fact that 1 1J =
Recall that du.b PT fo- and dg + PTT.f. We have
1 (fr 1( f) f) T (d,,.- d,) - 71 PT 1 1 f). f),
(
where (i) follows from the facts that dy,r and dy are both probability distributions and 1 d 1 dy. = 1 and 1 PT = I and (ii) follows from recursively applying (i).
Thus, we have
1 1 = (1-
fol s 11- $ 111l 1.
(37)
22

---

Published as a conference paper at ICLR 2022
Substituting eq. 37 into eq. (36) yields
1 rbr Σ (? Pmaz) 2y/1fli) + (T² Pman))
Under different conditions of Pmaar the term 1Tmy rb is upper bounded differently as following:
(a). 7 Pmox
1 T 5
3 2711f
+ +1) 7 Pmmax.
(38)
Pmax
(b). 22 Pmax
1 S (3 (3+2111f11bb++
(39)
(c). Pmax <
3 2
1 T S
+ 1.
(40)
722 Pmax
|1000)
Substituting the above inequalities into eq. (1), we can upper-bound the term E under different conditions accordingly:
Fi-1
(a). Pmax
E
(T().)) 1/ Fr S Pmaz (4(1 + 72) + 27 man)
B²
3
2
- + +1)
pinax
? Pmaa
1 12, Pmazi
where we specify Co,1 = Pmaz BB 2r
B
+ +1) 7 Pmos
3+2-11fll
mas
(b). 72 Pmacx
E
(80)
[u < Pmaz B2 + 2x 2)
B (33+ b
Co,2l,
where we specify Co.2 = Pmaz (4(1+ (4(1+ 2
max
(c). x2 Pmnc <1
E
(1()))
| Fi-1 S Pmax (4(1+ + 2r max)
B
3 2yl1f Ill
+1)
72 Pmnax
= Co.3.
where we specify C..3 = Pmaz
(4(1 (4(1+22)B33B) 2r 2m
B
3+2-1151l
+ 1).
I-
Pmaz
| 2 can be bounded as following
To summarize, the variance term
7.(00) ||] ||
s0²
where
O(1),
if Pmaz 1.
0²
O(6),
if Pmaz 1.
O(()² )))))))))
if Pmaz 1.
23

---

Published as a conference paper at ICLR 2022
D.3 PROOF OF THEOREM 1
Theorem 3 (Formal Statement of Theorem D. Suppose Assumptions 7 and 2 hold. Consider PER-ETD(O) specified Algorithm Let the stepsize 1he Ho(s+tta) where to
SL3
Po
Mg
is defined in Lemma 7 and To is defined in Lemma g in Appendix [ Let the projection set {0 E GRRR: ||0||2 S Ba), where Bg - laTmar (which implies 6* (). Then the con-
(1-9)14
vergence guarantee falls into the following two cases depending on the value of Pmaz.
log } where Co is constant defined (a) If Pmaz S 1, les max log(un) log(ua)-log(ee -logg(G, log(1/E) fr
(og(E)
in the proof of Proposition the output Or satisfies
7 in Appendix D.1
Bg == max,Es (|0(s)]l2. and = max X). Then
E ||0T 0'
O
T
(b) If Pmas > 1, b max
log(T
log(1/Ei where Cb
log(E)
log( Pmas
constant whose definition could be found in the proof of Proposition max,s [1o(s)]l2 and == max (7, x}. Then the output oy satisfies
in Appendix D.I Bg
E [[0r - 11 S
To
where Pmar) (0ma)))
1.
Thus, EER-E attains an e-accurate solution with Ô (2) samples if 7² Pmax S and with 2/a
samples if 72 Pmaz > 1.
Proof. Note the update specified in Algorithm maximization problem.
is the closed form solution of the following
1 +1110 -2ll3 Oz+1 = argmax 1/t (F.(0)).0) +
DEE
Applying Lemma 9 with 0" = 0c+1, = 1/1 G (0.), and On = 0g yields, for any 0 E O
Th (T.(0.))0++) - 0) + 0 1 < 2 10 011 10+1 0112.
(41)
Proceed with the first term in the above inequality follows
(.(0)), 8)
(T((++1) 1,00))00011111 -0) (T(0.) T(0++1), (100+1),00+11 0) (Ti(0.) T(O+), Oc+1 0)
@ (T(0++1),0 0111 8) Lolle 0- - 0 10-1112100411 - 0112 + (π((e)) - T(O.), 0s11 - 8)
(T((++1), 0++1 - 0) - Lo 0+t1|2210041 - 0|| (fr(O.) T(O.), T(0.),0+11 0g
+ +(F((0)) -T(O:), Og 0)
(T(1+11), 0141 - 8) - Lollo 6,+1 04t1l2210441 - 01 - || T(0) 110 - 88112
+ + -(()),, - 0).
where (1) follows from the Cauchy-Schwand inequality and Lemma
Substituting the above inequality into eq. (41 yields
mh (0(41))) 0.41 - 0) - Lo -04111 012 me [T((0)) T(0)) 110 - 0cl12
24

---

Published as a conference paper at ICLR 2022
+ Th
-0)+ -0++111 - 1
x2100. - -012 -3552110 12 -012.
1
(42)
Applying Young's inequality to 1// [T((O)) - T(0i)112 110++1 0el12 yields
" | - T( 110++11-1010 - 02ll2 - 10+1 - 0.113 + r Tr(O.)) - T
and applying Young's 's inequality to T/ L0 os+1 12110++1 -01l yields
Lo 0++1 11 0112 - 1 0, Oc+1 1 ni L8110++1 0112.
Substituting the above two inequalities into eq. (42) yields
2 110 011 2 vi (T 0c+1 - 0) + [ 2
-
n/ Li 110c+1 - 0112
+77 (Tr(0.) T(0.), 0, 0) - π
-
- -
Taking expectation conditioned on Fe-1 on the both sides of the above inequality, we obtain
1
1 -
2 211 0112 2 n 1 [[T (0++1))), 03] +
2 r/
IP [1|0++1 F(
+ nr (E -T(b))-T((8)
T(8s) F
0s 10--0 0) B
[| T(0i)l( Fi-1
(43)
Letting 0" and applying Lemma 7 to eq. (43) yields
2 11: - 1/ 2
2 + Molh - 1/2 LD E ||0+11 0- 12 Fr-1]
$ 110, Bap
0-112
m Cataaappran S010e 112
-n/BB [ - -(Bi))
Fi-1
(1) 1 + Mom
n/ Lb)
E (110-11- 1 18'11 F(-2]
C. b 11:-
8 11
The ThChaappe 1100 - -0'12 - CZ 10: -0'
Cn/ Cf5
Capprox 20²2/
2
(44)
where (i) follows from Propositions aadd] 2 and the facts that (x: + y)² < 2x + 2n² and
[T(00)) [[
2
2 E [T.00) F-1] T(0,)
/| +2 E [T((0)) [r-1] 7. 11
2
2
< 7 (0.) + 2 | [T((0.) [-1] - 1:
Taking expectation on both sides of the above inequality yields
1
-/2 + Mall - 1. [100-1 - -0'1
1 1 + C, + 4CB n/
E 18, 012
+ Cr Cacopnonn gb
2
+ Cn 2 capproz + 20221 2 1/:
Recall that we set 40 8L3 the above inequality and telescoping from t 0,1,2...., T
Let a: = (1 + 00 + 1)(( + l0 + 2). Multiplying 20, on both sides of
Mg
yields
T-1
Oe (1 + 2007h - L7) E [110++1 - 0'
25

---

Published as a conference paper at ICLR 2022
T-1
Σ 0t (1 + +0,0Bss + BBBB35 m())
110, - 0-112]
t=0
T
+ (4o² + +50 2
opprox
Σ
anh + 20 Bo approox
adh.
(45)
t=
Recall the setting of Th, we have
3/407
4
4
1 + 2
2112in = 1 +
1/1
LB
2
3
3/10
3/407
(
4
=1+
1
1
m m0
2
4O
(1)
3yo
2
+
2
where (i) follows from the fact that
4n, La
>
1
8L
0. Multiplying or on both sides of the
No
PGto
above inequality yields
3pm 2
a1 + 2poT: - 2n2 2 (t + to + 1)(t + to +2)
1+
2 polt + to)
= (t + to + 1) + to + +t to + 3) + to).
(46)
Under appropriate value of b, we have CB cb < 5
Which implies that
160, B35
2C,B,55T +
No
PoT
140
140
MO77
POT
[
+
16
1
5
25
HOTT
POTE
4p6
2
25
2
5
0
MOJJ
Multiplying a+41 on both sides of the above inequality yields
B 01+1 + 2C, 2C, M+ - SC, 1 S a0+11
2h
(1 MuTl++1
2
00+11 1
M47744111
2
(t + to 2) + to +3) 1 P/
2
polt + to 1)
(1 + to 2) to + +3) to + 1).
(47)
Equations (46
and 47
together imply that
a1
2po - 2n 2 +80 B3
(1 to + 1)(( + ln + 2) l0 +
(1+ 40 + 2) + t0 3)
t to
t to +1
(1+ + +2)(1 In +3)
((t to + 1 (1++ + ta + 2))
(++ (t)(t + to + 1)
(1+ + () lo +3)
(1+ (t) + 40 +1)
0.
26

---

Published as a conference paper at ICLR 2022
The above incquality shows that the ||0, 8* 11 t I..... terms both sides of eq. 45 can be canceled, which indicates the following
(T + to) + to 1) (1 11 -1 1E [1 - 11
$ (to 1)(to + 2) (1 + 100B20CB55mm no + SC B3 220 no) 110p
0-
T-1
+ (40 + + 2
Eapproz)
Σ
aml + 2C Bgaaprooz
(48)
t=
t=0
Note that Ei=0
6 - Σi=0
6T pb
+ 2po0fr-1 - 21 2 and
Mb
T-1
4 T-1
Σ
04 S
Σ
(t + to +2 S
(T + to + 2)
Pa
t=0
=
Dividing (T + (T to + (1 21
2 Lg) both sides of eq.
48 yields
| 0- [|
I (T' + (T + to 11
(tu (to + 2)
(1+
Ho77)
110 - 1
24 2 + 48C3522
E
Eapprox
4C CoC
(T + to + 2)²
P
T 10 +1
Po
(T lo + ()( + (0)
=0 100
8º1 1
CB
+
+0
+C(C)))
(49)
T
T
Based on different conditions of o², we pick different b and the convergence rate follows.
(a). 72 Pmax I 1, Proposition 2 show that 0² < (b).. We specify
b = max (og(ma)-Log(()) Bo)
log T log(1/E)
- (log(T))
log(E)
Equation 49 yields,
02112 +0 || 8" 11]] = (116 -
(Tg(T) +
(0(1)) 1 T2
+0 (0()) - -0())
T
(b). 22 Pmaa > 1, Proposition
2 show that 0² O ((?? Pmax) We specify
log(sug) -aalia)-ooggooo (5C, Rg)) log(E)
log(2)
max
Pman)) Pog(>>pman) +log(1/E)
Equation 49 yields
(0116
|10g 8
T
C TI+e
C.
(0(1)
E || [13]
=0
+
+ +0
+0
0
T2
To
E PROOFS OF PROPOSITIONS AND THEOREM FOR PER-ETD(1)
E.1 PROOF OF PROPOSITION
Define the matrix A, = de 7 and := r/plet. We have
(:,())) AgO: ct.
(50)
Recall that 0g is F--r-meaurrable We have
[., Fr
E[A[ ) -
27

---

Published as a conference paper at ICLR 2022
To bound the bias error term
E (7)) Fr-1
1aani---40 - we first take conditional expectations
on As and C₁ respectively, as following
E [A.[Ft-1)
EE (0) - 10t [
P ( = A
E
s, d. at b+1 = =
E (p) - -0 + F F s = s, 0. = a. St
b+1 =s1
18
Σ
P (s = 8 Fi-1) (aalss)P(ss
x(als)
[c = s, F(-1] (d(s))70(5)) ~
p(als)
8,0,5'
(s) = F(-1) E [
s Σ
x(als)P(s' (s)(sssss)))))))) (ds)) (
-
#ES
aEA''ES
- PP (+) s(Fi-1) E [ Fe 8 = (()) 7 (P= (.)))
(51)
where (i) follows from the law of total probability and (ii) follows from the Markov property and the fact that eg only depends on (s+, ag st,...,... $
Define (5) = IP (sf = s| 1) Fr 27 = s]. We have
(s) P (s) s F(- E [cp] s = F(
P (s) = s(F(1)
Σ P ((0 (66-1 8, 0z
b-1 = a/st = 8, Ft-1)
BESREAA
E 11App-11
c b-1 + +(++ (1+(1- (1-1)(11 pi- 71
10)))s 4 =3, b-1 ā 5 8, Fo-1]
(4)
P (s) = Fi ((5)
P P 1 F ((a
+P = 8 Fi-1) Σ
P P(s - Ft
RES,ãEA
π [apss
E [ndee] b-1 + (1- - AATE ) = 5, F(-]]
-
(5))
u 5)
= P (8) = =[F ((x) + P (0) b--1 = 8 F( (s(3))
8ES
E [x>e] h-1 + +11 1 3. -
(658) (A
(ss) + +APPP B0-1)..
(52)
where (1) follows from the law of total probability. (ii) follows from the Bayes rule
and the Markov property, and (izi) follows from the following definitions: dy
P (s) F( fs(s) (s) [ = 8/s4 F. Sa = dy.b + 7PT Jo-1, and (x) =
P( F(1) Fc
Define the matrix 8, E [dx(ss where B, (2) ... (+(())))))), Then, eq. 52 implies that
B, = Xo T Dub + (1 2)o F. + 7283-11 Pr,
(53)
where Du =
... dr (181) and F6 diag([s
Recursively applying the above equality yields
b-1 3. = (>>)* + A Σ
b-1
(T + (1 A) >
(T>)T P.
(54)
0=0
0=0
28

---

Published as a conference paper at ICLR 2022
Taking expectation of et conditioned on Fe-1, we have
E [c = E
[pletr Fc-1]
Σ
P(s = =s = a F(-1) E 10letr0108
s, = a, Fi-1
sES,
x(als)
Σ
P( = F( m(als)
r E [eglor = Fc-1]
[(aas)
Σ
Tr (s) s F( E |e 8, Fi-1
sES
Σ (s)
(55)
SES
Substituting eqs.
51 and (55)
into eq. 50 yields
E
(0))
Fi
Σ
(s(s) (D0, 70x00- -rx). = 33: 7P rT))
Recall the definition of (0). We have
(+,) - E T: (0.) Fi-] TMI M(I ((P=-))P)~1- -B6) ( - yP, rx))
(56)
We then proceed to bound the term D - - 33
T M(T ->>P=) 3o
8
( M
Φ
Σ (7))T P7
-Bb
80 Σ
T (AD,, + (1-))F)
(7 P
(TA)) pd + A
b-1
6-1
Σ
(>))< Dp.b- (1- " (7))"0t T Fo-
T=0
==0
b-1
6-1
A
Σ (>>)T&T T (Dp, Dub-+) PF + (1 Σ
(7>)= x (F- - Fb PT
-=0
1=0
+ Σ r=b
EGA) (AD + (1 {(>2)^ D DuoP
where (1) follows from the fact that -1- Σー 7" Pr. and (ii) follows from eq.
54
Substituting the above equality into eq. (56) and taking & norm on the both sides yield
(0.)) - 7. (0:) 11
b-1
Σ (7 :T T (Dp - DD +1 A)
Σ
T (F-Fo-r) Pr
-=0
(>))= T + - D
TT Du
(40, -6P,- Tx
T=b
6-1
< (7^)T | T (D,, - -ubb-)) P7 ($0; 7P,00. - -
7=0
b-1
+ +
Σ (72)7 11 (F-Fb PT ($0, 7P -
T=0
29

---

Published as a conference paper at ICLR 2022
Σ (Td)" ΦT +1- PF (D0:- -Pxx00 122
+ *(7>)* (TAT)/|(@DDOOf
DMOPP (00: - - - 122
(T1)" Id dy.- (Boll, 071l2 + Eapproz)
-=0
b-1
+ +11 A)
Σ
(T1)" BB 11f - fo- ( 821l2 + CCapprox)
T=0
(Td) BB (Alld +
(1 + (1
(Bpl1. - 021l2 + copproe)
A(>A) (1
(Bol10, - 8x1l2 Capproz)
(1)
0B 0, 8ill2 + BxSapproz)
Σ(a2)" (N(1+ ()(1+))Cax** (1 A) (1-2))1++7) ( (C =1 + [1filla)))
((*tl-Nlllll +2) (12)0)
+ (1+ (B%l10, -0ill2 Bekapproz)
1-72 71
(10)
(B3 - -02l12 + BaCapproz)
(1 +7) ( Cart + - 5h +(1 (1++11/1) 1|[1))>>>* + (A+ + 2) (22)00)
(60)
S Ca. (B&l 10: 0xl12 + Eupproz) 5":
where (i) follows from Lemma 5 and eq. (2)). (ii) follows from Lemma 1 [nd eq. (7 in (iéi) define
CaA = B1 + 7) (Ix-T Cm CM
CM-(1-)) x- +1 +1++10 11fll1 + 1-7x +2))
and (iv) follows from Lemma 3
E.2 PROOF OF PROPOSITION 4
According to the definition of T,A, we have
E T. (0.) Fr-1
= E [WO (12
Tc Fi-1
Σ
P( = ot a. 1+1 s F(FF-))
DESSESSSSS
E
(10)) (r+ + 10000tt01110001 -
10-110000000 )²)² 2 (4)) c 07 s, =a, b+1 = 16- F(
(ii)
Σ
JESESS
(alss)
(o5,a)+00, - 00 (()) ( - F
(P(ass)
(111)
P (5) 8 F(Fi1) [[( //// = 8, F(-1]
SES
Σ
+ 7 To, d(s) To,²
e'ES
30

---

Published as a conference paper at ICLR 2022
(iv) S Pmaz BB + 2r mr)
B P (s F( E [(e)) e =. F(-1)
SES
(57)
where (i) follows from the law of total probability, (ii) follows from the Markov property and the fact that et only depends on (f
ab o...., , st), and (iit) follows from eq. 30 and the fact
Es (u,x(6'lo S Pman-
Define (s(s) = TP (s. = =(Fi-1) E [(e)) T T F(-i- We then proceed to bound the term
(s(s). We have
As(s)
①
(8) s(
Σ
(s6-1) 03 b-1 = =ālst s. Fc-1) IE [(e)]] Te -, ā 8y 8, Fi
RES,aEA
P (s)
F(-1)
P (s h-1 ((
Σ
E [(e)) Tel)) -,,05- ā, 5/ 8, Fi
P(s 1111))
BES,aEA
(163
Σ
P(ab-1 = F. ((
BES,GEA
(TApT
b-
C + (A + (1 1 1)) 0.))
(r2p) 1-1 b-1
+ (A + (1 + 13) =,, b-1 0, =, F(-1]
=ā,
E
( =(
=
SES,aEA
E
((()) ((s))
+2y2>(1 2x12 A) 1000
((8) o6 - b-1
+2(1 A\ypi - ((8) (0s) =3, a. 8 =s F,
= (5) = 8 11-1) ||b())]13
+ (s(3)P (s) = F [2 + 2 1)FF)) 66)) 3, Fi-1]
+ x277 (s (st ( F
X(1 2222211 + 2y
2) (1
c | 3, F(1l
SES
+ +110(s)1172(1 (1- Σ
n (s/3))P (st F(F [ 122ss = F(11
<. (sd,,(()) + A9 2 (s)(
+ 27 -7
(3 (P.T fo-1).
(PT 4,57 A--1) 1), 2 A) B3
1b-1)s (PTTT
+2 X(1 2) Σ Pr n.. (>|8) (s)
8 F. E.
T 8,
EES
(10) Bzd (s) + X2 1,,
fh-1), - 1), 27 (P +
2n (s) Pz)
+ (3 2 x)o(s) (60-1Pust(
(58)
where (i) follows from the law of total probability, (ii) follows from the Bayes rule, (iii) follows the update rule of ot and in (iv) we define
8-(s) (5 =F =,
31

---

Published as a conference paper at ICLR 2022
Summing eq. (58) over S yields
A - Es((s)
B T dspb(s) + 1- P.T n.= Au- 27 - 1 fo-1 + Atrace (93)-1Px)
+ 2)2 B P H. Ho- + 2 X(1 A)trace (P
X2 2272 Pmax 1' + B3g + 2y - 1) fo-1
- + 2yAtrace (286-1Pa
+ 7 X) B)2 Pman 1 1 Th- + 2- AA1 A)trace (Ddr-1 Pp,5)
where (i) follows from Lemma with P P..-.
Recursively applying the above inequality, we have
1 A. $ (A2)3)0 e max 1 Do +
(1293)) (eppm-"(ppp "Pmmax)" 1- (B3 + -))B31 f--1
T=1
+tyAtrace (03 2 B)2 Bages 1 r4-1 + 27222( X(1 A)trace (467-1 Pp,x)) (59)
Substituting eq. (54) into trace Px), with b and 7 replaced by t and m respectively yields trace P+)
trace (0.30P+t))
Σ (7)) (20 Pur-mprrtt + (1 A)trace (44 T F Pm-mp
m==
ttrace @p D2,o)
Σ (72)*T (trace (pmtt Du + (1 A)trace ppm+lpp T Fr-m)
(116
T-1
1 (7A)² r Bº1 T dn,p= + B
Σ (7)) (A/ld + (1- A)11fr-mlla)
m=U
1 1- (-A))
B²
(2 + (1 A) + ([/II)))) B
1 1-
B2
(1 + (1 (1-1)).))l),
(60)
where (i) follows from eq. 54 (ii) follows from the facts that trace(AB) trace( BA) and
50 क Du., (Hii) follows from Lemma with P Pa. and (iv) follows from eq. (37
Next, we proceed to bound the term trace (Φ T PP.1.
86_
1- = E (72p)-22
(A + (1 1)4-) {1 =,5
(1t)
X)IP (s} B B
8, [ (63)
AIP - = 5 ((5)
+ XP F( - ((3)
+ + (60- s| E
(a8)
- X)n (5) + A/6 (8)
PP( & (i-1)) Σ P (0+
8 0t
b-2 a" a F,
32

---

Published as a conference paper at ICLR 2022
E kAp: b-2 2 h-2 7 Aapp
2- 222
5" h-2 a", h-1 =,, Fi
(1 Ajro-1 (3))(3) + A (3))(8)
P (56-2
8" Ft P(()l"") ,d))
+ (s) 1 = 8 Fi-1)
Σ
P P(ot Fi-1)
8".0"
x <a"
E 71 uuaa|""' 8n)
Ei + 722
Fl 2
h-2
1s h-2 s" Fi-1
12(a"(3")
= -1 - (5)-
A/. (3))(8) (1 (.)))))) + +- M6r 2 Pur (..0)
where (i) follows from the update of e (ii) follows from the update rule of F and (iii) follows from the law total probability.
The above equality implies that
6--1 (1 \) T diag(ro-1) X T diag(So-1) 7A30-2P, + 7
Recursively applying the above equality yields
66- 1 Σ + ( A)diig((m) Adiag([m)) + 7A8m-1 (P)a
+ +7 5o
Note that the above inequality holds for any fixed b >= As a result, by changing of notation, for all 7 2 1, we have
6, Σ T ((1 ((1 (idd-)(da(()))) Adiag(fm)) + PA (7²2)² (P....
(61)
Substituting eq. 61 into trace (L6, Pa,x), we have
trace (0Ō P,,#)
= trace
Σ ( ((1 A)diag(rm) + Adiag(fm)) + (P) m=1
+ 60 6o(=m))) Pua
trace ((Px ( r- (TDD -1)ddagggrr)) + Adiag(fm)) +
trace ((> A)T (1
100)
(62)
where (i) follows from the fact that trace(AB) trace(BA) and trace(A A + B) = trace(A) + trace( B)-
Applying Lemma 6 with Q = PH..r C Pmozi P Pn. and D = (1 - A)diag(rm.) we have
trace (T
m+1 00 T(1 A)diag(rm)) I (1 X) "Ba1lmmll
(63)
Applying Lemma 6 with Q PH.to C Pmaz, P Prr and D Adiag have
(6)
trace ((Pa,)) ++ 11 कΦ Adiag(sm)) S Ap -+1-m (all-BBlll. B311mmll S Ap -+1-m 1-1m BB3(1 + [1/1))) (64)
where (i) follows from eq. 377..
For the term trace ((Pr,u) +++-- T 3mmm111 Pa), we have
trace ((Pr,)) -+1- 3
33

---

Published as a conference paper at ICLR 2022
(TA)m=-trace trace (Pr,)) +t) Du.
(x2)) (Atrace (P=-1(Px.))) ==1mm)
(P. ΦT T D 1-1m
Ajtrace (pt (P (Pa.u)= -- u F fxmm-1-1))
-m
(GA))=-11 du,0 +
m
Σ (x2) (AIT d + -1-2111
2)1 (1-))--(((11))mmm-111 /m-1-)
t=
(1i)) B Bapmiett
5
mar
(1-
(65)
where (1) follows from eq. (54 and the facts that trace (A
(A+ + B) = Irace(A) + trace (B) and
trace(AB) trace BA), (ti) follows from Lemma with Q PH. P = Px. and D F Fm-
and Dr,m- 1-1 respectively, and (iti) follow from the eq. 337
Recall 60- = T Du.o0- Applying Lemma 6 with Q = P and = Du.o yields
trace ((72>) A)* (Px (T +600) s (r x)= B Par
(66)
Substituting eqs.
63 to 66
into eq. 622 we have
trace (RDŌ, ),,T
Tt1 S (7>2)) Bopmat
Bapmornt m=1
Σ
(X(ILfls= + +
1 (1 +1 1)11f111
11-1-N11fll
-
Pommm B mmll.
1 7d
m=1
(67)
Substituting eqs. (60) and 67 into eq. 59 we have
b 2b Pmax B3 + (1 + (1 1) + (1 B3
A S 2b
Σ
2 2) ((-r)))))))))) r) Piine
T=1
+ 71 - p
1+1 &
2b 25 26 2r
P Pmaxe 11 + 2 21
)) B²
b-
T=1
1 (1 -Alllfla
+ +2 2)B3
(XlsslI + 1+
Pmaxx
2h 27 x
28
27
Pmax
1 1-7X
m=1
T-1
+ +222A(1 -2)1 13
20-22 26
p Pmaz m
(68)
n3 1ークx (1 (1+(1 (1+ 1)1l(1))
where we let C3
[AA(0))
Under different conditions of Pmaz, the term Ab and E differently as following:
Ft
can be upper bounded
(a). 72 Pmma < 1, substituting eq. 40 into eq. 68 yields
1 I S 20 20p
Pmax B3 (1 + 27 A)(1 1151h) - 27A0s) B3
Σ
2)
b
(3+ (3+2111f1ll +1
+ + A) p B
2 26 Pmax
1-72
+ 22
B2 Σ
b-
7=1
34

---

Published as a conference paper at ICLR 2022
1 + (1- (1-A)]lfiIl
+ + - 1)B2
(|Sll +1+
Pinas
1 7>
2b 2b 2 2h--2 25
m Pmox
==1
m=1
+27 - ))2 B
20 25 225-2 27 Σ Pmar
3 + 2711.fl1
+1)
1 1-
T=1
m=1
(1 +1+ 2
A) + [1 + 2yACs) B%
I 20 26
B Pmaz
+
10
1 2 Pmmadd
(1 Pmaz B
3 1-11fl111
-- + +1) + 222 p B3
0
Pmand
2y² A)B3 R
xllfli+++ 1+
++ (1
6+1
(1 7²22)(1 pmazz)
1-7A
27²A(1 - 13
(3+ 23+21lllll 1-72
Pentar:
(69)
(1 (1-7">3)(1 pmaz)
where the last two terms the above inequality are of the order
O (Pman) Therefore, we have
1 Do I Cpinar for some C' >> 0. Substituting eq. (69) into eq. 57) yields
E
|
F S CoNA1
where C,,A,1 0 is constant and is determined by eq. (69
(b). 72 Pmar = 1, substituting eq.
(39 into eq. (68) yields
1 As S 2 B² + (1+ 2 A) + (1 + 2yAC3) B Σ 22(0-))
-=1
+0²(1 - 2)² Pmax B
26 (4 24+2)11f +2 - A) Σ x
1 (1 2)11f11a
+ +222A(1 B)BB [AIifll+
Pmnn
26 27 26 27
Pmaa
1 1-
+ +222A(1 - 21)11ll B3 Σ 26-52 2r Σ
Pinz m
m=1
S B3 + 27 - A)(1 - 11/lh) + 27)C0) B²
B2
72 - 2)2 Pmar B3
(4+ 241111111h) + 2y² X)2 (4 2 fx1l BB
+
1- 22
(1-22)(1- pmaa))
2y² -
AIISII+ +1+ 1+ (1- A)1lfIl
Pitaa
(70)
(1 -1--20m (1 - pmaz)
1-72
where the last term of the above inequality is of the order O (Pinaz). Therefore, we have 1 AAA, S
Opiaa for some C >>0 0. Substituting eq. (70 into eq. (57) yields
E
Fi-1
S Co.A,PPmax
where Co.2.2 is constant and is determined by eq. (70).
(c). 22 Pmax > 1, substituting eq. (38) into eq.
(68 yields
b
1 T Ab < 26, P Pina B3, + (1 (1+22((1 27 - A)(1 (1 + 27ACa) B&
Σ
x 20 (2(6-)) -), 2(0-r) r) P
T=1
35

---

Published as a conference paper at ICLR 2022
3- 2711
h
+ 21 - 2)² Pmaae B²g
+ Σ
26-22
+ +210720(1
\) B Σ
x2 Pman
1=1
T=l
+ (1 - 1)11f111
2272X(1 X(1 -))B3 Allflla +1
Pmax
26 27
27
P Pmaz
1 1-71
T=1
m=1
(3 (3+2yll +y11l1l11
22721(1- 2) x)) Pmaa B²
P2pmaxx - + Σ
26- 2h x 24
2m
(1 11+27(1- 1)(1 +1f[l1) + 2x>Ca) B
S x 26,,7 2b P maa B²g +
26 Pmax
Pmaa -
2b+2 (1 - ))²
1+ B3 maa
P22max - +1) + 22 Pina
3 2
BB
1 1 X2
27/2(1 A(1 2)B2
1 1+(11 ++(1-N11111)
(llffll + 1
b+1 Pinas
(1 +2)2 - pmac))
1 1-7d
2y² 2)2
B3 + 2yl1fll1
7 Pmaz - +1) Pinax:
(71)
(1 71) - 22
where the last term of the above inequality is of the order O (Pinaz). Therefore, we have 1 Ab
Opinas for some C 0. Substituting eq- (71 into eq. (57 yields
|
Fi-1 s CaxxPmoar
where Ca,2,3 > is a constant and is determined by eq.
71
To summarize, the variance term |
Fi-1
can be bounded by of = Oppina))
E.3 PROOF OF THEOREM
Theorem 4 (Formal Statement of Theorem 2}. Suppose Assumptions
7 [and hold. Consider PER-
ETD(A) specified in Algorithm Let the stepsize
px tx
8L.
where μa is defined in
Lemma and Lx defined in Lemma 8 in Appendix
Further let
[og(())) 1o
log((1)
= max
log(E)
log(pmos) Hlog (1E)
B3 max.es [[(()]]2, and { = max(?, X). Let the projection set θ E Rd ||0112 S Be where
where Co. is constant defined in the proof of Proposition in Appendix
E.1
By || larmaz (which implies 0% Q). Then the output 0r of PER-ETDIA satisfies (1-7)ux
E [110T
[x < O
Tax
where ax = samples.
ToR1/g (Pmax )+1 Further, PER-ETD(>) attains an e-accurate solution with δ
(11) I
Proof. The proof follows the same steps as Theorem by replacing the terms F., T, to. Lo, H0. Cr. o² and 6* with T,a, T tx, Lx. yr Co,2, of and 0 respectively. Specifically. Propositions 3 and are applied to bound the bias and variance over the steps similarly to eq. (44) We then have the convergence as follows.
1100
0N1
2b
[| 03
0
+
(5*)
T2
T
=
0
110g
8 112
O
Praaz T
+
O
2h
+0 (5*).
+
(72)
T
T
36

---

Published as a conference paper at ICLR 2022
We further specify b
{{
log(e)
log((Chh Bol
log Pmaa Hlog (1/5) j.
log(T)
Then Equation 72
yields
100 - 02
(T2-0x>
Ti+ax )
1
E |||T 02112 s 0
+ 0
+0
0
o
T2
T
Tax
Tox
37


Reviews:
[{"review_id": "e6GXvsNgHXK", "reviewer": "Reviewer_RfbH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is well written and clear to follow.\n- Strong theoretical analysis\n- The proposed tricks are simple and elegant.\n\nSome suggestion:\n- Adding an experiment to discuss the choice of behavior policy and target policy would be appreciated.\n- Figure 1&2 is hard to read, perhaps you could plot the line with variance bar\n", "summary_of_the_paper": "This paper proposed a new off-policy evaluation successor method of ETD. The method has reduced variance by leveraging a simple and effective way that restarting follow-on trace iteration every couple of updates. The authors also provide theoretical analysis that shows that the proposed method improves the converge rate from an exponential one to a polynomial one with the guarantee of the same fixed converging points. The empirical results show that the proposed method could converge in the case that neither TD nor ETD does. ", "summary_of_the_review": "Overall, I think the paper is solid and sound, it is marginally above the acceptance threshold. However, I would consider changing the scores if my concerns are addressed.\n\n------------\nAfter Rebuttal:\nAfter reading the author's rebuttal and the comments of other reviewers, I decided to increase the score to 8. I appreciate the author's thorough and conscientious rebuttal to address all my concerns.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EXdMccyETqo", "reviewer": "Reviewer_vCDh", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 easy to follow. The analysis make the improvements of PER-ETD over ETD evident and convincing, and the empirical results, while limited, illustrate well the theoretical contributions when dealing with a significant mismatch.\n\nI think the experiments should have contained some results in settings that aren't constructed to diverge. Specifically, I would have liked to see how PER-ETD performs compared to ETD and TD a bit more broadly. I think small illustrative domains are sufficient for this kind of work, but having more than a single domain/setting to either show that we see the same predicted effects in different settings or to give a more complete picture would have improved this work. For instance, an experiment which varies mismatch could have helped illustrate how mismatch affects PER-ETD, ETD, and TD, and possibly help visualize the two-phase behavior discussed in the paper.\n\nThat being said, I find the overall contributions sufficient for acceptance. The work is well motivated, novel, and provides a notable improvement over ETD. A more complete comparison would have been nice, but, as it stands, this is likely to be of interest to parts of RL community and is worth sharing.\n\nQuestions:\n================\n\n- Is setting the same step size really \"fair\"? I can understand keeping the same step-size for different $b$ for the purpose of illustrating the theoretical contributions, but why is it fair to use a fixed step size across different algorithms?\n- What does the shaded area represent?", "summary_of_the_paper": "The authors propose an improved variant of emphatic temporal difference (ETD) aimed at addressing issues of high variance when faced with a large mismatch between behavior and target policies. The main improvement of PER-ETD, the proposed algorithm, comes from periodically clearing the follow-on trace at logarthmically increasing periods. The authors present a finite-time analysis for both the PER-ETD(0) and PER-ETD($\\lambda$) case showing how bias and variance depends on the time between clearing the trace. This is used to derive a schedule that effectively minimizes the variance and bias to achieve polynomial sample complexity. The authors conclude by illustrating these improved properties in Baird's counter-example MDP. The results confirm the effect on bias and variance of the period parameter and highlight's that $\\lambda=1$ no longer results in the closest fixed-point to the optimal solution. ", "summary_of_the_review": "The paper is well written and easy to follow. The analysis make the improvements of PER-ETD over ETD evident and convincing, and the empirical results, while limited, illustrate well the theoretical contributions when dealing with a significant mismatch.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9iOZonnKfYr", "reviewer": "Reviewer_M48z", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 addresses a fundamental problem in reinforcement learning, and proposes a simple solution to this problem, with theoretical guarantees. The paper discusses the issues with off-policy evaluation, specifically the problem of distribution correction, for which emphatic algorithms have been introduced. It proposes that previous methods like GTD deal with this poorly, due to this distribution mismatch, though it is not clear why that is the case, or is it specified. The paper would benefit from a clear explanation on what objective function these class of methods optimize and how that differs, and how one is preferable to the other, since both these class of methods have been algorithms that can deal with off-policy learning. Page 3 -> \"cardinality of the state\", maybe you mean \"states\" or \"state space\"? The vector of values for all the states has the same notation as the value function, and capitalized like random variables, which is a bit confusing. $B_\\phi$ is not introduced. Page 5, \"helps to stabilize\" -> \"helps stabilize\". Lemma 1 (geometric ergodicity) -- can you explain what this lemma says in words, it is not clear why this will be useful or you need it in your analysis. There is no row space above \"Proposition 1\". There are a lot of constants introduced that it's easy to lose sight of what they mean and get confused, if ever they were introduced at the beginning of the paper. One way to make the paper more clear would be to hide all these details and explain high level the steps of the analysis or proof. In proposition 1, $\\zeta$ should be $\\zeta^b$ everywhere? Is $\\rho_max$ defined anywhere? What is $T_a$? The explanations below Theorem 1 are confusing because I'm not sure how to interpret $a$, and I don't understand where the threshold comes from. Below proposition 4., should that be \"PER-ETD\" instead of \"ETD\" ?  Above \"Experiments\", in the \"impact of $\\lambda$ on error bound, do you mean \"eligibile traces\" or \"the eligible trace\" maybe? Figure 3. what is the space in which these are plotted? The first sub-figure is also missing the y-axis. How confident are we that these methods are scalable in the general spaces we use these methods in? Is there such a way of increasing the period still applicable?", "summary_of_the_paper": "This paper presents a technique of reducing the variance of emphatic algorithms by resetting the trace periodically, and that increasing the period logarithmicaly can result in an optimal way of trading off bias and variance of the resulting learned value function. The authors prove such a method obtains the optimal tradeoff and results in convergence in settings where predecessor variants fails (TD and ETD). The paper proves these claims theoretically, and show an illustration on the Baird domain for empirical support.", "summary_of_the_review": "The paper addresses a fundamental problem in RL is a simple way and proves that such a method achieves an optimal tradeoff between bias and variance in emphatic algorithms, leading to polynomial sample complexity. The claims of the paper are also illustrated in a toy domain, showing great potential. The paper could benefit from some more explanations and clarity.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6KeNJplY2B", "reviewer": "Reviewer_TgfL", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Pros:\n1. In my opinion, this paper does answer an important question in off-policy value evaluation. The contribution is solid, and the proposed algorithm intuitively makes sense.\n2. The analysis in this paper is quite novel. The trade-off between variance and bias is very interesting.\n3. Theorem 1 is interesting in capturing how the sample complexity depends on the mismatch level.\n4. The advantage of this work over the concurrent paper (Zhang2021) is clear.\n\n\n\nCons:\n1. It seems that the algorithm is not using all the data in an efficient manner. It seems to me that the update for the theta parameter mostly depends on the the last data point within the last period. Is that right? Most data points in the period are only used to update F? Is there a better way to make full use of the data? Maybe some variant similar to least square type methods?\n2. This paper considers a projected version of ETD.  Is it possible to remove the projection operator? In addition, there are a few papers on how to remove projection for the analysis of stochastic approximation under Markovian noise which should be mentioned in this paper.\n\n   R. Srikant and L. Ying,  Finite-time error bounds for linear stochastic approximation and TD learning, COLT 2018. \n    \n    B. Hu and U. Syed, Characterizing the exact behaviors of temporal difference learning algorithms using Markov jump linear system theory, NeurIPS 2019.\n    \n   M. Kaledin, E. Moulines, A. Naumov, V. Tadic, H. Wai. Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise, COLT 2020. \n \n   C. Z. Chen, S. Zhang, T. T. Doan, S. T. Maguluri, and J.-P. Clarke, Performance of Q-Learning with Linear Function Approximation: Stability and Finite-Time Analysis.\n\n\n", "summary_of_the_paper": "The variance of ETD can grow up exponentially so this paper proposes to use a periodically restarted variant (namely, the PER-ETD) as an improvement.  The authors show that the proposed method has a polynomial sample complexity, and provide some experimental validation. ", "summary_of_the_review": "Overall I am still positive on this paper. The analysis is very interesting and insightful in characterizing the trade-off between variance and bias. Currently my score is 6 but I am willing to increase my score if all my comments are addressed. \n\n\n---------------------------------------------------\nI think the authors' response to my comments are very reasonable. I have increased my score to 8.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates TD-based off-policy policy evaluation. This topic is of interest as most SOTA DRL methods are built upon unsound algorithms, whereas more sound variants are difficult to use in practice and have not been widely adopted. This paper introduces a new variant of ETD that addresses the variance issue with the existing algorithm, along with theory characterizing sample efficiency. The paper includes a well done illustrative empirical study to support the theory. The reviewers all scored the paper highly. 

The AC pointed out several minor issues in the presentation that the authors should address for camera ready.  In addition the grammar and word usage is rough in some places. Please take time to improve the text.
Decision: Accept (Poster)