PER-ETD: A POLYNOMIALLY EFFICIENT EMPHATIC TEMPORAL DIFFERENCE LEARNING METHOD
Year: 2021

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, PERETD 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.

heading: 1 INTRODUCTION
text: 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. Although 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-policy settings when the agent only has access to data sampled by a behavior policy (Baird, 1995; Tsitsiklis & Van Roy, 1997; Mahmood et al., 2015). To address such an issue, the gradient temporal-difference (GTD) (Sutton et al., 2008) and least-squares temporal difference (LSTD) (Yu, 2010) algorithms have been proposed, which have been shown to 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, Sutton et al. (2016) proposed the emphatic temporal difference (ETD) algorithm, which introduces the follow-on trace to address the distribution mismatch 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 guarantee for ETD was established in Yu (2015), 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 a long or 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 so 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 a possibly large bias error. This thus poses the following intriguing question:
Can we design a new ETD method, which overcomes its large variance without introducing a large bias error, and improves its exponential sample complexity to be polynomial at the same time?
In this work, we provide an affirmative answer.

heading: 1.1 MAIN CONTRIBUTIONS
text: We propose a 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 it only for b times (where we 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 analysis. We show that PER-ETD (both PER-ETD(0) and PER-ETD(λ)) converges to the same fixed points of ETD(0) and ETD(λ), respectively, but with only polynomial sample complexity (whereas ETD takes exponential sample complexity). Our analysis features the following key insights. (a) The period length b plays the role of trading off between the variance (of the follow-on trace) and bias error (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 sublinearly. (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-transition phenomenon of PER-ETD: as long as the mismatch is below a certain threshold, then PER-ETD achieves the same convergence rate as the on-policy TD algorithm; and if 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 error is large so that the convergence is unstable. (b) Under a small period length b, it is not always the case that PER-ETD(λ) with λ = 1 attains the smallest error with respect to the ground truth value function. The best λ depends on the geometry of the locations of fixed points of PER-ETD(λ) for 0 ≤ λ ≤ 1, which is determined by chosen features.

heading: 1.2 RELATED WORKS
text: TD learning and GTD: The asymptotic convergence of TD learning was established by Sutton (1988); Jaakkola et al. (1994); Dayan & Sejnowski (1994); Tsitsiklis & Van Roy (1997), and its nonasymptotic convergence rate was further characterized recently in Dalal et al. (2018a); Bhandari et al. (2018); Kotsalis et al. (2020); Chen et al. (2019); Kaledin et al. (2020); Hu & Syed (2019); Srikant & Ying (2019). The gradient temporal-difference (GTD) was proposed in Sutton et al. (2008) for off-policy evaluation and was shown to converge asymptotically. Then, Dalal et al. (2018b); Gupta et al. (2019); Wang et al. (2018); Xu et al. (2019); Xu & Liang (2021) provided the finite-time analysis of GTD and its variants.
Emphatic Temporal Difference (ETD) Learning: The ETD approach was originally proposed in the seminal work Sutton 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 convergence guarantee for ETD. Hallak et 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. Imani et al. (2018) developed a new policy gradient theorem, where the emphatic weight is used to correct the distribution shift. Zhang et al. (2020b) provided a 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.
Comparison to concurrent work: During our preparation of this paper, a concurrent work (Zhang & Whiteson, 2021) was posted on arXiv, and proposed a truncated ETD (which we refer to as 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 our work from Zhang & Whiteson (2021). (a) Our PER-ETD features a design of the logarithmical increase of the restart period with the number of iterations, which guarantees the convergence to 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 truncation-length-dependent fixed point, where the convergence is obtained by treating the truncation length as a constant. A careful review of the convergence proof indicates that the variance term scales exponentially fast with the truncation length, and hence the polynomial efficiency is 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 Zhang & Whiteson (2021) scales with the cardinality of the state space, and increases exponentially fast with the mismatch parameter of behavior and target policies. (c) This paper further studies PER-ETD(λ) and the impact of λ on the converge rate and variance and bias errors, whereas Zhang & Whiteson (2021) considers further the application of T-ETD to the control problem.

heading: 2 BACKGROUND AND PRELIMINARIES

heading: 2.1 MARKOV DECISION PROCESS
text: We consider the infinite-horizon Markov decision process (MDP) defined by the five tuple (S,A, r,P, γ). Here, S and A denote the state and action spaces respectively, which are both assumed to be finite sets, r : S ×A → R denotes the reward function, P : S ×A → ∆(S) denotes the transition kernel, where ∆(S) denotes the probability simplex over the state space S, and γ ∈ (0, 1) is 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., π(a|s) represents the probability of taking the action a under the state s. At any time t, given that the system is at the state st, the agent takes an action at with the probability π(at|st), and receives a reward r(st, at). The system then takes a transition to the next state st+1 at time t+ 1 with the probability P(st+1|st, at). For a given policy π, we define the value function corresponding to an initial state s0 = s ∈ S as Vπ(s) = E [ ∑∞ t=0 γ
tr(st, at)|s0 = s, π]. Then the value function over the state space can be expressed as a vector Vπ = (Vπ(1), Vπ(2), . . . , Vπ(|S|))> ∈ R|S|. Here, Vπ is a 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 Vθ(s) = φ
>(s)θ, where φ(s) ∈ Rd denotes the feature vector, and θ ∈ Rd denotes the parameter vector to be learned. We further let Φ = [φ(1), φ(2), . . . , φ(|S|)]> denote the feature matrix, and then Vθ = Φθ. We assume that the feature matrix Φ has linearly independent columns and each feature vector has bounded `2-norm, i.e., ‖φ(s)‖2 ≤ Bφ for all s ∈ S.

heading: 2.2 TEMPORAL DIFFERENCE (TD) LEARNING FOR ON-POLICY EVALUATION
text: In order to evaluate the value function for a given target policy π (i.e., find the linear function approximation parameter θ), the temporal difference (TD) learning can be employed based on a sampling trajectory, which takes the following update rule at each time t:
θt+1 = θt + ηt ( r(st, at) + γθ > t φ(st+1)− θ>t φ(st) ) φ(st), (1)
where ηt 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 semigradient descent update. If the trajectory is sampled by the target policy π, then the above TD algorithm can be shown to converge to the fixed point solution, where the convergence is guaranteed by the negative definiteness of the so-called key matrixA := limt→∞ E [ (γφ(st + 1)− φ(st))φ>(st) ] .

heading: 2.3 EMPHATIC TD (ETD) LEARNING FOR OFF-POLICY EVALUATION
text: 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 to trajectories sampled under a behavior policy µ. Namely, at each time t, the probability of taking an action at given st is µ(at|st). Let dµ denote the stationary distribution of the Markov chain induced by the behavior policy µ, i.e., dµ satisfies d>µ = d > µPπ . We assume that dµ(s) > 0 for all states. The mismatch between the target and behavior policies can
be addressed by incorporating the importance sampling factor ρ(s, a) := π(a|s)µ(a|s) into eq. (1) to adjust the TD learning update direction. However, with such modification, the key matrix A may not be negative definite so that the algorithm is no longer guaranteed to converge.
In order to address this divergence issue, the emphatic temporal difference (ETD) algorithm has been proposed by Sutton et al. (2016), which takes the following update
θt+1 = θt + ηtρ(st, at)Ft ( r(st, at) + γθ > t φ(st+1)− θ>t φ(st) ) φ(st). (2)
In eq. (2), in addition to the importance sampling factor ρ, a follow-on trace coefficient Ft is introduced as a calibration factor, which is updated as
Ft = γρ(st−1, at−1)Ft−1 + 1, (3)
with initialization F0 = 1. With such a follow-on trace factor, the key matrix becomes negative definite, and ETD has been shown to converge asymptotically in Yu (2015) to the fixed point
θ∗ = ( Φ>F (I − γPπ)Φ )−1 Φ>Frπ, (4)
where F = diag(f(1), f(2), . . . , f(|S|)) and f(i) = dµ(i) limt→∞ E [Ft|st = i]. Similarly, the ETD(λ) algorithm can be further derived, which has the following update
θt+1 = θt + ηtρ(st, at) ( r(st, at) + γθ > t φ(st+1)− θ>t φ(st) ) et,
where et is updated as et = γλρ(st−1, at−1)et−1 + Mtφ(st) and Mt = λ + (1 − λ)Ft, where M0 = 1 and e0 = φ(s0). It has been shown that with a diminishing stepsize (Yu, 2015), ETD(λ) converges to the fixed point given by
θ∗λ = ( Φ>M(I − γλPπ)−1(I − γPπ)Φθ )−1 Φ>M(I − γλPπ)−1rπ,
where M = diag(m(1),m(2), . . . ,m(|S|)) and m(i) = dµ(i) limt→∞ E [Mt|st = i].

heading: 2.4 NOTATIONS
text: For the simplicity of expression, we adopt the following shorthand notations. For a fixed integer b, let sτt := st(b+1)+τ , a τ t := at(b+1)+τ , ρ τ t = π(aτt |s τ t )
µ(aτt |sτt ) and φτt = φ(s τ t ). We also define the filtrationFt = σ ( s0, a0, s1, a1, . . . , st(b+1)+b, at(b+1)+b, st(b+1)+b+1 ) . Further, let rπ ∈ R|S|, where rπ(s) =∑
a∈A r(s, a)π(a|s). Let Pπ ∈ R|S|×|S|, where Pπ(s′|s) = ∑ a∈A π(a|s)P(s′|s, a). For a matrix M ∈ RN×N , M(s,·) denotes its s-th row and M(·,s) denotes its s-th column. We define Bφ := maxs ‖φ(s)‖2 as the upper bound on the feature vectors, and define ρmax := maxs,a π(a|s)µ(a|s) as the maximum of the distribution mismatch over all state-action pairs.

heading: 3 PROPOSED PER-ETD ALGORITHMS
text: Drawbacks of ETD: In the original design of ETD (Sutton et al., 2016) described in Section 2.3, the follow-on trace coefficient Ft 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. (2016) (also see our experiment in Section 5).
Algorithm 1 PER-ETD(0) 1: Input: Parameters T , b, and ηt. 2: Initialize: θ0 = 0. 3: for t = 0, 1, ..., T do 4: F update: F τ+1t = γρ τ t F τ t + 1, where τ = 0, 1, . . . , b− 1 and F 0t = 1;
5: θ update: θt+1 = ΠΘ ( θt + ηtF b t ρ b t(r b t + γθ > t φ b+1 t − θ>t φbt)φbt ) 6: end for
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 1). At iteration t,
PER-ETD reinitiates the follow-on trace F and update it for b iterations to obtain an estimate F bt , where we call b as the period length. The emphatic update operator at t is then given by
T̂t(θ) = F bt ρbtφbt(φbt − γφb+1t )>θ − F bt ρbtφbtrbt , (5) and PER-ETD updates the value function parameter θt as θt+1 = ΠΘ ( θt − ηtT̂t(θt) ) , where the
projection onto an bounded closed convex set Θ helps to stabilize the algorithm. It can be shown that limb→∞ E[T̂t(θ)|Ft−1] = T (θ) where T (θ) := ( Φ>F (I − γPπ)Φ ) θ − Φ>Frπ . The fixed point of the operator T (θ) is θ∗ defined in eq. (4), which is exactly the fixed point of original ETD. Definition 1 (Optimal point and -accurate convergence). We call the unique fixed point θ∗ of T (θ) as the optimal point (which is the same as the fixed point of ETD). The algorithm attains an - accurate optimal point if its output θT satisfies ‖θT − θ∗‖22 ≤ .
The goal of PER-ETD is to find the original optimal point θ∗ of ETD, which is independent from the period length b. Our analysis will provide a guidance to choose the period length b in order for PER-ETD to keep both the variance and bias errors below the target -accuracy with polynomial sample efficiency.
Algorithm 2 PER-ETD(λ) 1: Input: Parameters T , b, and ηt. 2: Initialize: θ0 = 0. 3: for t = 0, 1, . . . , T do 4: Set F 0t = M 0 t = 1 and e 0 t = φ 0 t
5: for τ = 1, . . . , b do 6: F τt = ρ τ−1 t γF τ−1 t + 1, M τ t = λ+ (1− λ)F τt , eτt = γλρτ−1t eτ−1t +Mτt φτt 7: end for 8: θ update: θt+1 = ΠΘ ( θt + ηtρ b t ( rbt + γθ > t φ b+1 t − θ>t φbt ) ebt ) 9: end for
We then extend PER-ETD(0) to PER-ETD(λ) (see Algorithm 2), which incorporates the eligible trace. Specifically, at each iteration t, PER-ETD(λ) reinitiates the follow-on trace Ft and updates it together withMt and the eligible trace et for b iterations to obtain an estimate ebt . Then the emphatic update operator at t is given by
T̂ λt (θ) = ρbtebt ( φbt − γφb+1t )> θ − ρbtrbtebt , (6)
and the value function parameter θt is updated as θt+1 = ΠΘ ( θt − ηtT̂ λt (θt) ) . It can be shown
that limb→∞ E [ T̂ λt (θ) ∣∣∣Ft−1] = T λ(θ), where T λ(θ) = Φ>M(I − γλPπ)−1(I − γPπ)Φθ − Φ>M(I − γλPπ)−1rπ,
which takes a unique fixed point θ∗λ as the original ETD(λ). The optimal point and the -accurate convergence can be defined in the same fashion as in Definition 1. It has been shown in Hallak et al. (2016) that θ∗λ is exactly the orthogonal projection of Vπ to the function space when λ = 1, and thus is the optimal approximation to the value function.

heading: 4 FINITE-TIME ANALYSIS OF PER-ETD ALGORITHMS

heading: 4.1 TECHNICAL ASSUMPTIONS
text: 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 1 (Coverage of behavior policy). For all s ∈ S and a ∈ A, the behavior policy µ satisfies µ(a|s) > 0 as long as π(a|s) > 0. 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 µ has a unique stationary distribution dµ over the state space S. Moreover, the Markov chain is uniformly geometric ergodic, i.e., there exist constants CM ≥ 0 and 0 < χ < 1 such that for every initial state s0 ∈ S , the state distribution dµ,t(s) = P (st = s|s0) after t transitions satisfies ‖dµ,t − dµ‖1 ≤ CMχt.
4.2 FINITE-TIME ANALYSIS OF PER-ETD(0)
In PER-ETD(0), the update of the value function parameter is fully determined by the empirical emphatic operator T̂t(θ) defined in eq. (5). Thus, we first characterize the bias and variance errors of T̂t(θ), which serve the central role in establishing the convergence rate for PER-ETD(0). Proposition 1 (Bias bound). Suppose Assumptions 1 and 2 hold. Then we have
E [∥∥∥T (θt)− E [T̂t(θt)∣∣∣Ft−1]∥∥∥
2
] ≤ Cb (Bφ‖θt − θ∗‖2 + approx) ξb,
where approx = ‖Φθ∗ − Vπ‖∞ is the approximation error of the fixed point, ξ = max {γ, χ} < 1, Bφ = maxs ‖φ(s)‖2, and Cb > 0 is a constant whose exact form can be found in the proof.
Proposition 1 characterizes the conditional expectation of the bias error of the empirical emphatic operator T̂t(θ). Since ξ = max {γ, χ} < 1, such a bias error decays exponentially fast as b increases. Proposition 2 (Variance bound). Suppose Assumptions 1 and 2 hold. Then we have
E [∥∥∥T̂t(θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ σ2, where σ2 =  O(1), if γ2ρmax < 1, O(b), if γ2ρmax = 1, O ( (γ2ρmax) b ) , if γ2ρmax > 1,
(7)
where O(·) is with respect to the scaling of b, and ρmax = maxs,a π(a|s)µ(a|s) .
Proposition 2 captures the variance bound of the empirical emphatic operator. It can be seen that if the distribution mismatch is large (i.e., γ2ρmax > 1), the variance bound grows exponentially large as b increases, which is consistent with the finding in Hallak et al. (2016). However, as we show below, as long as b is controlled to grow only logarithmically with the number of iterations, such a variance error 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. Theorem 1. Suppose Assumptions 1 and 2 hold. Consider PER-ETD(0) specified in Algorithm 1. Let the stepsize ηt = O ( 1 t ) and suppose the period length b and the projection set Θ are properly chosen (see Appendix D.3 for the precise conditions). Then the output θT of PER-ETD(0) falls into the following two cases.
(a) If γ2ρmax ≤ 1, then E [ ‖θT − θ∗‖22 ] ≤ Õ ( 1 T ) .
(b) If γ2ρmax > 1, then E [ ‖θT − θ∗‖22 ] ≤ O ( 1 Ta ) , where a = 1log1/ξ(γ2ρmax)+1 < 1.
Thus, PER-ETD(0) attains an -accurate solution with Õ ( 1 ) samples if γ2ρmax ≤ 1, and with
Õ ( 1 1/a ) samples if γ2ρmax > 1.
Theorem 1 captures how the convergence rate depends on the mismatch between the behavior and target policies via the parameter ρmax (where ρmax ≥ 1). (a) If γ2ρmax ≤ 1, i.e., the mismatch is less than a threshold, then PER-ETD(0) converges at the rate of Õ ( 1 T ) , which is the same as that of on-policy TD learning (Bhandari et al., 2018). This result indicates that even under a mild mismatch 1 < ρmax ≤ 1/γ2, PER-ETD achieves the same convergence rate as on-policy TD learning. (b) If γ2ρmax ≥ 1, i.e., the mismatch is above the threshold, then PER-ETD(0) converges at a slower rate of Õ ( 1 Ta ) because a < 1. Further, as the mismatch parameter ρmax gets larger, the converge becomes slower, because a becomes smaller.
Bias and variance tradeoff: Theorem 1 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 θ∗.
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 1 shows that the output θT of PER-ETD(0) satisfies the following convergence rate:
E [ ‖θT − θ∗‖22 ] ≤ O
( ‖θ0 − θ∗‖22
T 2
) +O ( σ2
T ) ︸ ︷︷ ︸
variance
+O ( ξ2b
T
) +O ( ξb )
︸ ︷︷ ︸ bias . (8)
If γ2ρmax ≤ 1, then σ2 in the variance term in eq. (8) satisfies σ2 ≤ O(b) as given in eq. (7), which increases at most linearly fast with b. Then we set b = O
( log T
log(1/ξ)
) so that both the variance and
the bias terms in eq. (8) achieve the same order ofO (
1 T
) , which dominates the overall convergence.
If γ2ρmax > 1, then σ2 in the variance term in eq. (8) satisfies σ2 = O ( (γ2ρmax) b ) as given in
eq. (7), Now, we need to set b as b = O (
log(T ) log(γ2ρmax)+log(1/ξ)
) , where the increase with log T has
a smaller coefficient than the previous case, so that both the variance and the bias terms in eq. (8) achieve the same order ofO ( 1 Ta ) . Such a choice of b balances the exponentially increasing variance and exponentially decaying bias to achieve the same rate.
4.3 FINITE-TIME ANALYSIS OF PER-ETD(λ)
In PER-ETD(λ), the update of the value function parameter is determined by the empirical emphatic operator T̂ λt (θ) defined in eq. (6). Thus, we first obtain the bias and variance errors of T̂ λt (θ), which facilitate the analysis of the convergence rate for PER-ETD(λ). Proposition 3. Suppose Assumptions 1 and 2 hold. Then we have∥∥∥E [T̂ λt (θt)∣∣∣Ft−1]− T λ(θt)∥∥∥
2 ≤ Cb,λ (Bφ‖θt − θ∗λ‖2 + approx) ξb,
where approx = ‖Φθ∗λ − Vπ‖∞ is the approximation error of the fixed point, ξ = max{χ, γ} < 1, Bφ = maxs ‖φ(s)‖2, and Cb,λ is a constant given a fixed λ whose exact form can be found in proof.
The above proposition shows that the bias error of the empirical emphatic operator T̂ λt (θ) in PERETD(λ) decays exponentially fast as b increases, because ξ = max {γ, χ} < 1. Proposition 4. Suppose Assumptions 1 and 2 hold. Then we have
E [ ∥∥∥T̂ λt (θt)∥∥∥2
2 ∣∣∣Ft−1] ≤ σ2λ, where σ2λ = O (ρbmax) . (9) Compared with Proposition 2 of PER-ETD(0), Proposition 4 indicates that ETD(λ) has a larger variance, which always increases exponentially with b when ρmax > 1. This is due to the fact that the eligible trace ebt carries the historical information and is less stable than φ b t . Theorem 2. Suppose Assumptions 1 and 2 hold. Consider PER-ETD(λ) specified in Algorithm 2. Let the stepsize ηt = O ( 1 t ) and suppose the period length b and the projection set Θ are properly chosen (see Appendix E.3 for the precise conditions). Then the output θT of PER-ETD(λ) satisfies
E [ ‖θT − θ∗λ‖22 ] ≤ O
( 1
T aλ
) ,
where aλ = 1log1/ξ(ρmax)+1 . PER-ETD(λ) attains an -accurate solution with Õ ( 1 1/aλ ) samples.
Theorem 2 indicates that PER-ETD(λ) converges to the optimal fixed point θ∗λ determined by the infinite-length update of the follow-on trace. Furthermore, PER-ETD(λ) converges at the rate of Õ (
1 Taλ ) which is slower than PER-ETD(0) (as aλ < a) due to the larger variance of PER-ETD(λ).
Bias and variance tradeoff: We next explain how the period length b achieves the best tradeoff between the bias and variance errors and thus yields polynomial sample efficiency. The proof of Theorem 2 shows that the output θT of PER-ETD(λ) satisfies the following convergence rate:
E [ ‖θT − θ∗λ‖22 ] ≤ O
( ‖θ0 − θ∗λ‖22
T 2
) +O ( σ2λ T ) ︸ ︷︷ ︸
variance
+O ( ξ2b
T
) +O ( ξb )
︸ ︷︷ ︸ bias . (10)
In eq. (10), σ2λ in the variance term takes the form σ 2 λ = O ( ρbmax ) as given in eq. (9). We need to
set b = O (
log(T ) log(ρmax)+log(1/ξ)
) so that both the variance and the bias terms in eq. (10) achieve the
same order ofO (
1 Taλ
) . Thus, such a 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 λ) 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 a finite period length b, the fixed point of PER-ETD(1) is generally not the same as the projection of the ground truth to the function approximation space. Thus, as λ changes from 0 to 1, depending on the geometrical locations of the fixed points of PER-ETD(λ) for all λ (determined by chosen features) with respect to the ground truth projection, any value 0 ≤ λ ≤ 1 may achieve the smallest bias error. We illustrate this further by experiments in Section 5.2.

heading: 5 EXPERIMENTS

heading: 5.1 PERFORMANCE OF PER-ETD(0)
text: We consider the BAIRD counter-example. The details of the MDP setting and behavior and target policies could be found in Appendix A.1. We adopt a constant learning rate for both PERETD(0) and PER-ETD(λ) and all experiments take an average over 20 random initializations. We set the stepsize η = 2−9 for all algorithms for fair comparison. For PER-ETD(0), we adopt onedimensional features Φ1 = (0.35, 0.35, 0.35, 0.35, 0.35, 0.35, 0.37)>. The ground truth value function Vπ = (10, 10, 10, 10, 10, 10, 10)> and does not lie inside the linear function class.
In Figure 1(a), we compare the performance of of TD, vanilla ETD(0) and PER-ETD(0) 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(0) converges close to 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-policy data historically, and ETD (0) also diverges due to the very large variance.
In Figure 1(b), we plot how the bias and the variance of PER-ETD(0) change as the period length b changes. Clearly, small b (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 a significant increase in variance. This demonstrates a clear tradeoff between the bias and variance as we capture in our theory.
5.2 PERFORMANCE OF PER-ETD(λ)
We next focus on PER-ETD(λ) under the same experiment setting as in Section 5.1 and study how λ affects the performance. We conduct our experiments under three features Φ1, Φ2, and Φ3 specified in Appendix A.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 2 (a), (b), and (c), λ = 0, 1, and some value between 0 and 1 respectively achieve the smallest error under the corresponding feature. This is in contrast to the general understanding that λ = 1 typically achieves the smallest error. In fact, each case can be explained by the plot in Figure 3 under the same feature. Each plot in Figure 3 illustrates how the fixed points of PER-ETD(λ) 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 PERETD(1) is not located at the same point as the ground truth projection. The geometric locations of the fixed points of PER-ETD(λ) for 0 ≤ λ ≤ 1 are determined by chosen features. The bias error corresponds to the distance between the fixed point of PER-ETD(λ) 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 Φ3, Figure 3 (c) suggests that neither λ = 0 nor λ = 1, but some λ between 0 and 1 achieves the smallest error. This explains the result in Figure 2 (c) that λ = 0.4 achieves the smallest error among other curves.
As a summary, our experiment suggests that the best λ, under which PER-ETD(λ) attains the smallest error, depends on the geometry of the problem determined by chosen features. In practice, if PER-ETD(λ) is used as a critic in policy optimization problems, λmay be tuned via the final reward achieved by the algorithm.

heading: 6 CONCLUSION
text: In this paper, we proposed a novel PER-ETD algorithm, which uses a 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-ETD(λ) illustrated that under the finite period length in practice, the best λ that achieves the smallest bias error is feature dependent. We anticipate that PER-ETD can be applied to various off-policy optimal control algorithms such as actor-critic algorithms and multi-agent reinforcement learning algorithms.

heading: SUPPLEMENTARY MATERIALS

heading: A SPECIFICATION OF EXPERIMENTS IN SECTION 5

heading: A.1 EXPERIMENT SETTINGS
text: The BAIRD counter-example is illustrated in Figure 4, which has 7 states and 2 actions. If the first action (illustrated as 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 0; and if the second action (illustrated as solid lines) is taken, the environment transitions from the current state to state 7 with probability 1 and returns a reward 1. We choose the target policy as π(0|s) = 0.1 and π(1|s) = 0.9 for all states; and choose the behavior policy as µ(0|s) = 6/7 and µ(1|s) = 1/7 for all states. Moreover, we specify the discount factor γ = 0.99.

heading: A.2 FEATURES FOR EXPERIMENTS IN SECTION 5.2
text: In the experiment in Section 5.2, we choose the following features:
Φ1 =(0.35, 0.35, 0.35, 0.35, 0.35, 0.35, 0.37) >;
Φ2 =((0.3425, 0.0171) >, (0.1902, 0.4248)>, (0.1354, 0.76)>, (0.1357, 0.7973)>,
(0.8674, 0.8774)>, (0.5166, 0.9493)>, (0.3094, 0.8535)>)>;
Φ3 =((0.5162, 0.9013) >, (0.5128, 0.5999)>, (0.289, 0.4649)>, (0.3399, 0.5334)>,
(0.315, 0.2278)>, (0.667, 0.461)>, (0.3706, 0.1457)>)>.
A.3 COMPUTATION OF THE FIXED POINT OF PER-ETD(λ)
In this section, we provide the steps to compute the fixed point of PER-ETD(λ) in Figure 3. We first define the matrix A and c as follows
A := lim t→∞
E [ At ( := ( ρbte b t(φ b t − γφb+1t )>)] ,
c := lim t→∞
E [ ct ( := ρbtr b te b t )] .
It can be shown that, the fixed point of PER-ETD(λ) algorithm is θ∗ = A−1c.
We next show how to derive the formulation of the matrix A and vector c. As we will show later in eqs. (52), (54) and (56), we have
A = lim t→∞
E [At|Ft−1] = β̄b(I − γPπ)Φ, (11)
c = lim t→∞
E [ct|Ft−1] = β̄brπ, (12)
where β̄b := limt→∞ E [βb] and
βb(s) = λΦ >Dµ,b + (1− λ)Φ>Fb + γλβb−1Pπ, (13)
where Dµ,τ = diag(dµ,τ ), dµ,τ (s) = P(sτt = s|Ft−1), Fb = diag(fb), and fb is determined iteratively by eq. (26) as follows
fb = dµ,b + γP > π fb−1, with f0 = dµ,0. (14)
Taking expectation on both sides of eqs. (13) and (14) with respect to Ft−1 and letting t→∞ yield
f̄b = dµ + γP > π f̄b−1, with f̄0 = dµ, (15) β̄b = λΦ >Dµ + (1− λ)Φ>F̄b + γλβ̄b−1Pπ, with β̄0 = Φ>Dµ (16)
where f̄b := limt→∞ E[fb] and F̄b = diag(f̄b). The explicit formulation of β̄b can be derived by applying eqs. (15) and (16) iteratively. We can then obtain A and c by substituting the obtained formulation of β̄b into eq. (11) and eq. (12), respectively.

heading: A.4 REPLOTTED FIGURES 1 AND 2 WITH VARIANCE BARS
text: In this subsection, we replotted Figures 1 and 2 with variance bars (rather than error bands) in Figures 5 and 6, respectively.

heading: B NEW EXPERIMENTS
text: In this section, we conduct further experiments to answer the following two intriguing questions:
• If the distribution mismatch parameter ρmax changes, how will different approaches perform and compare with each other?
• Focusing on our algorithm PER-ETD, how do the choices of behavior policy and target policy affect its convergence?
We focus on the MDP environment in Appendix A.1. In our experiments, the performance of every algorithm is averaged over 20 random initializations and the error band in our plots captures the actual variation of the performance during these experimental runs (which can be viewed as the variance of the algorithms).
In Figure 7, we consider two settings with the distribution mismatch parameter ρmax = 1.17 and 5.60, respectively, and compare the performance of three off-policy algorithms: TD, vanilla ETD and our PER-ETD. More specifically, we choose the behavior policy as µ(1|s) = 67 and µ(2|s) = 1 7
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 π(1|s) + π(2|s) = 1). Therefore, the maximum distribution mismatch ρmax for the these two target policies are 1.17 and 5.60, respectively. Figure 7 (a) shows that under only slightly mismatch (i.e., ρmax = 1.17), TD suffers from a 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 a 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 a large distribution mismatch (i.e., ρmax = 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 a smaller convergence error as the period length b increases, but the variance gets larger; which are consistent with our theorem.
In Figure 8, we focus on our PER-ETD, and study how different target policies affect the performance. We choose the same behavior policy as the above experiment, i.e., µ(1|s) = 67 and µ(2|s) = 17 for all states. We choose 5 target polices, whose probabilities to 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 performance via their resulting distribution mismatch ρmax = 1.17, 1.40, 2.80, 4.20, 5.60, respectively. For both b = 4 and b = 6, Figure 8 indicates that larger mismatch causes slower convergence rate, larger convergence error and larger variance, which agrees with our theorem.
In Figure 9, we also focus on our PER-ETD, and study how different behavior policies affect the performance. We pick the target policy to be π(1|s) = 0.1 and π(2|s) = 0.9 for all states, and 5 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 ρmax = 1.12, 1.29, 1.5, 2.25, 4.5, respectively. Figure 9 clearly demonstrates that larger distribution mismatch results in slower convergence rate, larger convergence error and larger variance, which is in the same nature as changing the target policy shown in Figure 8 and is consistent with our theorem.

heading: C SUPPORTING LEMMAS
text: The following lemma is well-known. We include it for the convenience of our proof. Lemma 2. Consider a transition matrix P ∈ RN×N , where ∑ j P(i,j) = 1 for all i and 0 ≤ P(i,j) ≤ 1 for all j. We have for any n ∈ N, ‖Pn‖∞ = 1, and ‖(P>)n‖1 = 1.
Lemma 3. Consider 0 < p, q < 1, with p 6= q. We have ∑n−1 k=0 p kqn−k ≤ 1|p−q|ξ n, where ξ = max{p, q}.
Proof of Lemma 3. If p > q, we have
n−1∑ k=0 pkqn−k ≤ n−1∑ k=0 pk+1qn−1−k ≤ n−1∑ m=0 pn−mqm.
Without loss of generality, we assume p < q and ξ = q. We have
n−1∑ k=0 pkqn−k = qn · n−1∑ k=0 (pq ) k = qn · 1− (p/q) n 1− p/q ≤ 1 q − p · qn = 1 |p− q| · ξn.
Lemma 4. Consider a matrix P ∈ RN×N where ∑ j P(i,j) ≤ C for all i and 0 ≤ P(i,j) ≤ 1 for all j, and a positive vector x where x ∈ RN and xi ≥ 0 for all i. We have
1>Px ≤ C1>x.
Proof of Lemma 4. We have
1>Px = ∑
1≤i,j≤N
Pi,jxi = ∑
1≤i≤N
xi  ∑ 1≤j≤N Pi,j  ≤ C ∑ 1≤i≤N xi = C1 >x.
Lemma 5. Consider a diagonal matrix D ∈ R|S|×|S|, where D = diag(d(1), d(2), . . . , d(|S|)). a transition matrix P ∈ R|S|×|S| where ∑ j Pi,j = 1 for all i = 1, 2, . . . , |S| and Pi,j ≥ 0 for all j, and an arbitrary vector x ∈ R|S|. We have
‖Φ>DPx‖2 ≤ Bφ‖d‖1‖x‖∞.
Proof of Lemma 5. We have
Φ>D = (d(1)φ(1), d(2)φ(2), . . . , d(|S|)φ(|S|)) ,
and ( Φ>DP ) (·,s) = ∑ s̃ Ps̃,sd(s̃)φ(s̃),
which implies
Φ>DPx = ∑ s x(s) (∑ s̃ Ps̃,sd(s̃)φ(s̃) ) = ∑ s̃ (∑ s x(s)Ps̃,s ) d(s̃)φ(s̃).
Taking `2 norm on both sides of the above equality yields∥∥Φ>DPx∥∥ 2 = ∥∥∥∥∥∑ s̃ (∑ s x(s)Ps̃,s ) d(s̃)φ(s̃) ∥∥∥∥∥ 2
≤ ∑ s̃ ∣∣∣∣∣∑ s x(s)Ps̃,s ∣∣∣∣∣ · |d(s̃)| · ‖φ(s̃)‖2 = Bφ‖d‖1 ·max
s̃ ∣∣∣∣∣∑ s x(s)Ps̃,s ∣∣∣∣∣ ≤ Bφ‖d‖1‖x‖∞max
s̃ ∣∣∣∣∣∑ s Ps̃,s ∣∣∣∣∣ = Bφ‖d‖1‖x‖∞.
Lemma 6. Consider a diagonal matrix D ∈ R|S|×|S| where D = diag(d(1), d(2), . . . , d(|S|)), a transition matrix P ∈ R|S|×|S| where ∑ j Pi,j = 1 for all i = 1, 2, . . . , |S| and Pi,j ≥ 0 for all j, a matrix Q ∈ R|S|×|S| that satisfies 0 ≤ Qi,j ≤ CPi,j , where C > 1 is a constant, and an arbitrary vector x ∈ R|S|. We have
trace ( QmPnΦΦ>D ) ≤ CmB2φ‖d‖1,
and,
trace ( PnQmΦΦ>D ) ≤ CmB2φ‖d‖1,
for any m and n ∈ N≥0.
Proof of Lemma 6. For any given τ ≥ m ≥ 0 and n ≥ 0,∣∣(QmPnΦΦ>)(i,j)∣∣ = ∣∣〈(Qm)(i,·), (PnΦΦ>)(·,j)〉∣∣ (i)≤ ‖(Qm)(i,·)‖1‖(PnΦΦ>)(·,j)‖∞, (17)
where (i) follows from the Hölder’s inequality.
Furthermore, for the term of (PnΦΦ>)(·,j), we have,
‖(PnΦΦ>)(·,j)‖∞ ≤ ‖Pn‖∞‖(ΦΦ>)(·,j)‖∞ (i) = ‖(ΦΦ>)(·,j)‖∞,
where (i) follows from Lemma 2.
Moreover, for the ith entry of (ΦΦ>)(·,j), we have∣∣(ΦΦ>)(i,j)∣∣ = ∣∣φ(i)>φ(j)∣∣ ≤ ‖φ(i)‖2‖φ(j)‖2 ≤ B2φ The above uniform bounds over all i imply that ‖(ΦΦ>)(·,j)‖∞ ≤ B2φ. Hence,
‖(PnΦΦ>)(·,j)‖∞ ≤ B2φ.
Substituting the above inequality back into eq. (17), we obtain∣∣(QmPnΦΦ>)(i,j)∣∣ ≤ B2φ‖(Qm)(i,·)‖1 (i)≤ Cm‖(P τ−m)(i,·)‖1B2φ ≤ CmB2φ
∑ j P τ−m(j|i) = CmB2φ, (18)
where (i) follows by the condition of Q, Q(i,j) ≤ CP(i,j) for all i, j. Finally, we have
trace ( QmPnΦΦ>D ) = ∑ i d(i)(QmPnΦΦ>)(i,i) ≤ ∑ i |d(i)| ∣∣(QmPnΦΦ>)(i,i)∣∣
≤ ‖d‖1 max i ∣∣(QmPnΦΦ>)(i,i)∣∣ (i)≤ CmB2φ‖d‖1, (19) where (i) follows from eq. (18).
Following steps similar to those in eqs. (17) to (19), we can obtain trace ( PnQmΦΦ>D ) ≤ CmB2φ‖d‖1.
Lemma 7. The operators T (θ) and T λ(θ) satisfy the generalized monotone variational inequality. There exist µ0, µλ > 0, s.t., 〈T (θ), θ − θ∗〉 ≥ µ0‖θ − θ∗‖22 ,and 〈 T λ(θ), θ − θ∗ 〉 ≥ µλ‖θ − θ∗‖22.
Proof of Lemma 7. We have 〈T (θ), θ − θ∗〉 (i)= 〈( Φ>F (I − γPπ)Φ ) (θ − θ∗), θ − θ∗ 〉
= (θ − θ∗)> ( Φ>F (I − γPπ)Φ ) (θ − θ∗)
≥ λmin ( Φ>F (I − γPπ)Φ ) ‖θ − θ∗‖22, (20)
where (i) follows from the definition of the T and θ∗. Recall that F (I − γPπ) is positive definite(Sutton et al., 2016; Mahmood et al., 2015) and Φ has linearly independent columns. For any x ∈ Rd with x 6= 0, we have Φx 6= 0 and
x>Φ>F (I − γPπ)Φx = (Φx)>F (I − γPπ)(Φx) > 0.
The above inequality shows that Φ>F (I − γPπ)Φ is positive definite and thus, there exists µ0 > 0 such that µ0 = λmin ( Φ>F (I − γPπ)Φ ) .
Following steps similar to those in eq. (20) and applying the positive definiteness of M(I − γλPπ)
−1(I − γPπ) (Sutton et al., 2016; Mahmood et al., 2015) yield〈 T λ(θ), θ − θ∗ 〉 ≥ µλ‖θ − θ∗‖22.
Lemma 8. The operators T (θ) and T λ(θ) satisfy the Lipschitz condition. There exist L0, Lλ > 0, such that, ‖T (θ1)− T (θ2)‖2 ≤ L0‖θ1 − θ2‖2, and ∥∥T λ(θ1)− T λ(θ2)∥∥2 ≤ Lλ‖θ1 − θ2‖2. Proof of lemma 8. We have
‖T (θ1)− T (θ2)‖2 = ∥∥(Φ>F (I − γPπ)Φ) (θ1 − θ2)∥∥2
≤ ∥∥Φ>F (I − γPπ)Φ∥∥2 ‖θ1 − θ2‖2. (21)

heading: Let L0 :=
text: ∥∥Φ>F (I − γPπ)Φ∥∥2, eq. (21) completes the proof of the first inequality in the Lemma. Let Lλ := ‖Φ>M(I − γλPπ)−1(I − γPπ)Φ‖2, the steps similar to those in eq. (21) finalizes the proof of the second inequality in the Lemma.
Lemma 9 (Three point lemma). Suppose Θ is a closed and bounded subset of Rd, and θ∗ is the solution of the following maximization problem, maxθ∈Θ η 〈G, θ〉 + 12‖θ − θ0‖ 2 2, where G ∈ Rd is a vector. Then, we have, for any θ ∈ Θ,
η 〈G, θ∗ − θ〉+ 1 2 ‖θ0 − θ∗‖22 ≤ 1 2 ‖θ0 − θ‖22 − 1 2 ‖θ∗ − θ‖22.
Proof. The proof can be found in Lan (2020).

heading: D PROOFS OF PROPOSITIONS AND THEOREM FOR PER-ETD(0)

heading: D.1 PROOF OF PROPOSITION 1
text: First, by the definition of T̂t(θt), we have E [ T̂t(θt) ∣∣∣Ft−1] (i) = ∑ s∈S ∑ a∈A ∑ s′∈S
· P ( sbt = s, a b t = a, s b+1 t = s ′∣∣Ft−1)E [T̂t(θt)∣∣∣Ft−1, sbt = s, abt = a, sb+1t = s′] (ii) = ∑ s∈S ∑ a∈A ∑ s′∈S P ( sbt = s
∣∣Ft−1)µ(a|s)P(s′|s, a) · E [ ρbtF b t φ(s)[φ >(s)θt − r(s, a)− γφ>(s′)θt] ∣∣Ft−1, sbt = s, abt = a, sb+1t = s′]
(iii) = ∑ s∈S ∑ a∈A ∑ s′∈S P ( sbt = s ∣∣Ft−1)π(a|s)P(s′|s, a)φ(s)[φ>(s)θt − r(s, a)− γφ>(s′)θt] · E [ F bt ∣∣Ft−1, sbt = s]
= ∑ s∈S P ( sbt = s ∣∣Ft−1)E [F bt ∣∣Ft−1, sbt = s]φ(s) [φ>(s)θt − γ[PπΦ](s,·)θt − rπ(s)] , (22) where (i) follows from the law of total probability, (ii) follows from rewriting P ( sbt = s, a b t = a, s b+1 t = s ′ ∣∣Ft−1), and (iii) follows from the facts that F bt only depends on (s0, a0, s1, a1, . . . , st(b+1)+b−1, at(b+1)+b−1) and the chain is Markov.
Recall the definition of T (θt), we have
T (θt) = Φ>F [(I − γPπ)Φθt − rπ] = ∑ s∈S f(s) ( φ>(s)θt − γ[PπΦ](s,·)θt − rπ(s) ) φ(s). (23)
Equations (22) and (23) together imply the following, T (θt)− E [ T̂t(θt) ∣∣∣Ft−1] = ∑ s∈S ( f(s)− P ( sbt = s ∣∣Ft−1)E [F bt ∣∣Ft−1, sbt = s])
· ( φ>(s)θt − γ [PπΦ](s,·) θt − rπ(s) ) φ(s)
(i) = ∑ s∈S (f(s)− fb(s)) ( φ>(s)θt − γ [PπΦ](s,·) θt − rπ(s) ) φ(s)
= ∑ s∈S (f(s)− fb(s)) ((I − γPπ) Φθt − rπ)s φ(s),
where in (i) We define fb(s) := P ( sbt = s ∣∣Ft−1)E [F bt ∣∣Ft−1, sbt = s]. Taking `2 norm on both sides of the above equality yields∥∥∥T (θt)− E [T̂t(θt)∣∣∣Ft−1]∥∥∥
2
≤ ∥∥∥∥∥∑ s∈S (f(s)− fb(s)) ((I − γPπ) Φθt − rπ)s φ(s) ∥∥∥∥∥ 2
≤ ∑ s∈S |f(s)− fb(s)| · |((I − γPπ) Φθt − rπ)s| · ‖φ(s)‖2
≤ max s∈S {‖φ(s)‖2}max s∈S {|((I − γPπ) Φθt − rπ)s|} ∑ s∈S |f(s)− fb(s)|
= Bφ‖(I − γPπ)Φθt − rπ‖∞‖f − fb‖1. (24) We next proceed to bound ‖f − fb‖1. Consider fb(s), we have
fb(s) = P ( sbt = s ∣∣Ft−1)E [F bt ∣∣sbt = s,Ft−1] (i) = P ( sbt = s
∣∣Ft−1)∑ s̃∈S,ã∈A P ( sb−1t = s̃, a b−1 t = ã
∣∣sbt = s,Ft−1) · E [ γρb−1t F b−1 t + 1
∣∣Ft−1, sbt = s, sb−1t = s̃, ab−1t = ã] (ii) = P ( sbt = s
∣∣Ft−1) ·
1 + ∑ s̃∈S,ã∈A P ( sb−1t = s̃ ∣∣Ft−1)µ(ã|s̃)P(s|s̃, ã) P ( sbt = s ∣∣Ft−1) E [ γ π(ã|s̃) µ(ã|s̃) F b−1t ∣∣∣∣Ft−1, sb−1t = s̃] 
= P ( sbt = s ∣∣Ft−1)+ γ∑ s̃∈S P(sb−1t = s̃|Ft−1)Pπ(s|s̃)E [ F b−1t ∣∣Ft−1, sb−1t = s] , where (i) follows from the law of total probability and (ii) follows from the Bayes rule and the facts that F b−1t only depends on the chain elements (s 0 t , a 0 t , s 1 t , . . . , s b−1 t , a b−1 t ) and the Markov property.
Define dµ,b(s) = P ( sbt = s ∣∣Ft−1), the above equality can be rewritten as fb(s) = dµ,b(s) + γ
∑ s̃ Pπ(s|s̃)fb−1(s̃). (25)
Since eq. (25) holds for all s ∈ S, we have
fb = dµ,b + γP > π fb−1. (26)
Note that for f we have the following holds (Sutton et al., 2016; Zhang et al., 2020a)
f = dµ + γP > π f. (27)
Equations (26) and (27) imply
f − fb = dµ − dµ,b + γP>π (f − fb−1). Applying the above equality recursively yields
f − fb = b−1∑ τ=0 (γP>π ) τ (dµ − dµ,b−τ ) + γb(P>π )b(f − f0).
Take `1 norm on both sides of the above equality, we have
‖f − fb‖1 = ∥∥∥∥∥ b−1∑ τ=0 γτ (P>π ) τ (dµ − dµ,b−τ ) + γb(P>π )b(f − f0) ∥∥∥∥∥ ≤
b−1∑ τ=0 γτ ∥∥(P>π )τ (dµ − dµ,b−τ )∥∥1 + γb ∥∥(P>π )b(f − f0)∥∥1
≤ b−1∑ τ=0 γτ ∥∥(P>π )τ∥∥1 ‖dµ − dµ,b−τ‖1 + γb ∥∥(P>π )b∥∥ ‖f − f0‖1
(i) ≤ b−1∑ τ=0 γτ ‖dµ − dµ,b−τ‖1 + γ b ‖f − f0‖1
(ii) ≤ b−1∑ τ=0 CMγ τχb−τ + γb‖f − f0‖1
(ii)
≤ 1 |χ− γ| · CMξb + γb(1 + ‖f‖1), (28)
where (i) follows from Lemma 2, (ii) follows from Lemma 1 , and (iii) follows from Lemma 3 and defining ξ := max{χ, γ}. To bound the term ‖(I − γPπ)Φθt − rπ‖∞, we proceed as following
‖(I − γPπ)Φθt − rπ‖∞ (i) = ‖(I − γPπ)(Φθt − Vπ)‖∞ = ‖(I − γPπ)(Φθt − Φθ∗ + Φθ∗ − Vπ)‖∞ ≤ ‖I − γPπ‖∞(‖Φθt − Φθ∗‖∞ + ‖Φθ∗ − Vπ‖∞) (ii)
≤ (1 + γ)Bφ‖θt − θ∗‖2 + (1 + γ) approx, (29)
where (i) follows from the fact Vπ = (I − γPπ)−1rπ and (ii) follows from the facts that ‖I − γPπ‖∞ = maxi{1− (Pπ)(i,i) + γ ∑ j 6=i(Pπ)(i,j)} ≤ 1 + γ, approx := ‖Φθ∗ − Vπ‖∞, and
‖Φθt − Φθ∗‖∞ = max s∈S φ>(s)(θt − θ∗) ≤ Bφ‖θt − θ∗‖2.
Substituting eqs. (28) and (29) into eq. (24) yields∥∥∥T (θt)− E [T̂t(θt)∣∣∣Ft−1]∥∥∥ 2 ≤ ( B2φ‖θt − θ∗‖2 +Bφ approx ) (1 + γ) ( CMξ b |χ−γ| + γ b(1 + ‖f‖1) ) ≤ Cb (Bφ‖θt − θ∗‖2 + approx) ξb,
where ξ = max {χ, γ} and Cb = Bφ(1 + γ) ( CM |χ−γ| + (1 + ‖f‖1) ) .

heading: D.2 PROOF OF PROPOSITION 2
text: According to the definition of T̂t(θt), we have E [∥∥∥T̂t(θt)∥∥∥2∣∣∣∣Ft−1]
= E [( ρbtF b t )2 ( θ>t φ b t − rbt − γθ>t φb+1t )2 ‖φbt‖22∣∣∣Ft−1] (i) = ∑ s∈S ∑ a∈A ∑ s′∈S P ( sbt = s, a b t = a, s b+1 t = s
′∣∣Ft−1) · (θ>t φ(s)− r(s, a)− γθ>t φ(s′))2 · ‖φ(s)‖22 · E [ (ρbtF b t ) 2 ∣∣Ft−1, sbt = s, abt = a, sb+1t = s′]
(ii) = ∑ s∈S ∑ a∈A ∑ s′∈S P ( sbt = s ∣∣Ft−1)µ(a|s)P(s′|s, a) · (θ>t φ(s)− r(s, a)− γθ>t φ(s′))2
· ‖φ(s)‖22 · π2(a|s) µ2(a|s)
E [ (F bt ) 2 ∣∣Ft−1, sbt = s, abt = a, sb+1t = s′]
= ∑ s∈S P ( sbt = s ∣∣Ft−1)E [(F bt )2∣∣Ft−1, sbt = s] ‖φ(s)‖22 · ∑ a∈A ∑ s′∈S π2(a|s) µ(a|s) P(s′|s, a)(φ>(s)θt − r(s, a)− γφ>(s′)θt)2, (30)
where (i) follows from the law of total probability and (ii) follows from the fact that F bt is independent from previous states and actions given sbt .
Note that ‖φ(s)‖2 ≤ Bφ for all s ∈ S, r(s, a) ≤ rmax for all (s, a) ∈ S × A, and ‖θt‖2 ≤ Bθ for all t due to projection. We have
(φ>(s)θt − r(s, a)− γφ>(s′)θt)2 ≤ 2[(φ(s)− γφ(s′))>θt]2 + 2r2(s, a) ≤ 2‖φ(s)− γφ(s′)‖22‖θt‖22 + 2r2max ≤ 4(‖φ(s)‖22 + γ2‖φ(s′)‖22)‖θt‖22 + 2r2max ≤ 4(1 + γ2)B2φB2θ + 2r2max. (31)
We also have∑ a∈A ∑ s′∈S π2(a|s) µ(a|s) P(s′|s, a) ≤ ρmax · ∑ a∈A ∑ s′∈S π(a|s)P(s′|s, a) = ρmax.
Substituting the above two inequalities into eq. (30) yields E [∥∥∥T̂t(θt)∥∥∥2∣∣∣∣Ft−1] ≤ ρmax ( 4(1 + γ2)B2φB 2 θ + 2r 2 max
) B2φ ∑ s∈S P ( sbt = s ∣∣Ft−1)E [(F bt )2∣∣Ft−1, sbt = s] . (32) Define rb(s) := P ( sbt = s
∣∣Ft−1)E [(F bt )2∣∣Ft−1, sbt = s] = dµ,b(s)E [(F bt )2∣∣Ft−1, sbt = s]. We have the following equations hold for rb(s):
rb(s) = P(sbt = s|Ft−1)E [( γρb−1t F b−1 t + 1 )2∣∣∣Ft−1, sbt = s] = dµ,b(s)E [ 1 + 2γρb−1t F b−1 t + γ 2(ρb−1t ) 2(F b−1t ) 2 ∣∣Ft−1, sbt = s]
= dµ,b(s) + 2γdµ,b(s)E [ ρb−1t F b−1 t ∣∣Ft−1, sbt = s] + γ2dµ,b(s)E [ (ρb−1t ) 2(F b−1t ) 2 ∣∣Ft−1, sbt = s] . (33)
For the second term in the RHS of eq. (33), we have dµ,b(s)E [ ρb−1t F b−1 t ∣∣Ft−1, sbt = s] (i) = dµ,b(s)
∑ s̃∈S,ã∈A P ( sb−1t = s̃, a b−1 t = ã ∣∣sbt = s,Ft−1) · E [ ρb−1t F b−1 t
∣∣Ft−1, sbt = s, sb−1t = s̃, ab−1t = ã] (ii) = dµ,b(s)
∑ s̃,ã dµ,b−1(s̃)µ(ã|s̃)P(s|s̃, ã) dµ,b(s) · E [ ρb−1t F b−1 t ∣∣Ft−1, sbt = s, sb−1t = s̃, ab−1t = ã] (iii) =
∑ s̃∈S,ã∈A dµ,b−1(s̃)µ(ã|s̃)P(s|s̃, ã) · π(ã|s̃) µ(ã|s̃) E [ F b−1t ∣∣Ft−1, sb−1t = s̃] = ∑ s̃∈S Pπ(s|s̃) · dµ,b−1(s̃)E [ F b−1t
∣∣Ft−1, sb−1t = s̃] (iv) = (P>π fb−1)s, (34)
where (i) follows from the law of total probability, (ii) follows from the Bayes rule, (iii) follows from Markov property and (iv) follow from the definition of fb which is given above eq. (24).
For the third term on the RHS of eq. (33), we have dµ,b(s)E [ (ρb−1t F b−1 b ) 2 ∣∣Ft−1, sbt = s]
(i) = dµ,b(s) ∑ s̃∈S,ã∈A P ( sb−1t = s̃, a b−1 t = ã ∣∣sbt = s,Ft−1) · E [ (ρb−1t F b−1 b ) 2 ∣∣Ft−1, sbt = s, sb−1t = s̃, ab−1t = ã]
(ii) = dµ,b(s) ∑ s̃,ã dµ,b−1(s̃)µ(ã|s̃)P(s|s̃, ã) dµ,b(s) · E [ (ρb−1t F b−1 t ) 2 ∣∣Ft−1, sbt = s, sb−1t = s̃, ab−1t = ã]
= ∑
s̃∈S,ã∈A dµ,b−1(s̃)µ(ã|s̃)P(s|s̃, ã) ·
π2(ã|s̃) µ2(ã|s̃)
· E [ (F b−1t ) 2 ∣∣Ft−1, sb−1t = s̃]
(iii) = ∑ s̃∈S Pµ,π(s|s̃)rb−1(s̃)
= (P>µ,πrb−1)s, (35)
where (i) follows from the law of total probability, (ii) follows from the Bayes’ rule, and in (iii) we define Pµ,π ∈ R|S|×|S| where (Pµ,π)s,s̃ = ∑ ã∈A π2(ã|s̃) µ(ã|s̃) P(s|s̃, ã) for each (s, s̃) ∈ S × S.
Substituting eqs. (34) and (35) into eq. (33) yields
rb = dµ,b + 2γP > π fb−1 + γ 2P>µ,πrb−1.
We also have the following inequality holds
1>rb = 1 >dµ,b + 2γ1 >P>π fb−1 + γ 21>P>µ,πrb−1
(i) = 1 + 2γ1>fb−1 + γ 21>P>µ,πrb−1
(ii)
≤ 1 + 2γ1>fb−1 + γ2ρmax1>rb−1, (36)
where (i) follows from 1>P>π = (Pπ1) > = 1>, and (ii) follows from the facts that rb−1 0 and
1>P>µ,π = (Pµ,π1) > = vec (∑ s∈S ∑ ã∈A π2(ã|s̃) µ(ã|s̃) P(s|s̃, ã) ) = vec (∑ ã∈A π2(ã|s̃) µ(ã|s̃) ) ρmax1>.
Recursively applying eq. (36) yields
1>rb ≤ b−1∑ τ=0 (γ2ρmax) τ (1 + 2γ1>fb−τ−1) + (γ 2ρmax) b1>r0
(i) = b−1∑ τ=0 (γ2ρmax) τ (1 + 2γ1>fb−τ−1) + (γ 2ρmax) b, (37)
where (i) follows from the fact that 1>r0 = 1.
Recall that fb = dµ,b + γP>π fb−1 and f = dµ + γP > π f . We have
1>(fτ − f) = 1>(dµ,τ − dµ) + γ1>P>π (fτ−1 − f) (i) = γ1>(fτ−1 − f) (ii) = γτ1>(f0 − f),
where (i) follows from the facts that dµ,τ and dµ are both probability distributions and 1>dµ,τ = 1>dµ = 1 and 1>P>π = 1 > and (ii) follows from recursively applying (i).
Thus, we have
|1>fτ | = |(1− γτ )1>f + γτ1>f0| ≤ |(1− γτ )1>f |+ γτ ≤ ‖f‖1 + 1. (38)
Substituting eq. (38) into eq. (37) yields
1>rb ≤ b−1∑ τ=0 (γ2ρmax) τ (3 + 2γ‖f‖1) + (γ2ρmax)b.
Under different conditions of ρmax, the term 1>rb is upper bounded differently as following:
(a). γ2ρmax > 1
1>rb ≤ (
3 + 2γ‖f‖1 γ2ρmax − 1 + 1
) γ2bρbmax. (39)
(b). γ2ρmax = 1
1>rb ≤ (3 + 2γ‖f‖1) b+ 1. (40)
(c). γ2ρmax < 1
1>rb ≤ 3 + 2γ‖f‖1 1− γ2ρmax + 1. (41)
Substituting the above inequalities into eq. (32), we can upper-bound the term E [∥∥∥T̂t(θt)∥∥∥2
2 ∣∣∣∣Ft−1] under different conditions accordingly:
(a). γ2ρmax > 1 E [∥∥∥T̂t(θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ ρmax (4(1 + γ2)B2φB2θ + 2r2max)B2φ( 3 + 2γ‖f‖1γ2ρmax − 1 + 1 ) γ2bρbmax
= Cσ,1γ 2bρbmax, where we specify Cσ,1 = ρmax ( 4(1 + γ2)B2φB 2 θ + 2r 2 max ) B2φ ( 3+2γ‖f‖1 γ2ρmax−1 + 1 ) .
(b). γ2ρmax = 1 E [∥∥∥T̂t(θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ ρmax (4(1 + γ2)B2φB2θ + 2r2max)B2φ ((3 + 2γ‖f‖1) b+ 1) = Cσ,2b,
where we specify Cσ,2 = ρmax ( 4(1 + γ2)B2φB 2 θ + 2r 2 max ) B2φ (4 + 2γ‖f‖1).
(c). γ2ρmax < 1 E [∥∥∥T̂t(θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ ρmax (4(1 + γ2)B2φB2θ + 2r2max)B2φ( 3 + 2γ‖f‖11− γ2ρmax + 1 )
:= Cσ,3. where we specify Cσ,3 = ρmax ( 4(1 + γ2)B2φB 2 θ + 2r 2 max ) B2φ ( 3+2γ‖f‖1 1−γ2ρmax + 1 ) .
To summarize, the variance term ∥∥∥T̂t(θt)∥∥∥2
2 can be bounded as following
E [∥∥∥T̂t(θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ σ2, where
σ2 =  O(1), if γ2ρmax < 1. O(b), if γ2ρmax = 1. O((γ2ρmax)b), if γ2ρmax > 1.

heading: D.3 PROOF OF THEOREM 1
text: Theorem 3 (Formal Statement of Theorem 1). Suppose Assumptions 1 and 2 hold. Consider PER-ETD(0) specified in Algorithm 1. Let the stepsize ηt = 2µ0(t+t0) , where t0 = 8L20 µ20
, µ0 is defined in Lemma 7, and L0 is defined in Lemma 8 in Appendix C. Let the projection set Θ = { θ ∈ Rd : ‖θ‖2 ≤ Bθ } , where Bθ = ‖Φ>‖2rmax (1−γ)µ0 (which implies θ
∗ ∈ Θ). Then the convergence guarantee falls into the following two cases depending on the value of ρmax.
(a) If γ2ρmax ≤ 1, let b = max {⌈ log(µ0)−log(5CbBφ) log(ξ) ⌉ , log Tlog(1/ξ) } , where Cb is a constant defined in the proof of Proposition 1 in Appendix D.1, Bφ := maxs∈S ‖φ(s)‖2, and ξ := max{γ, χ}. Then the output θT satisfies
E [ ‖θT − θ∗‖22 ] ≤ Õ
( 1
T
) .
(b) If γ2ρmax > 1, let b = max {⌈ log(µ0)−log(5CbBφ) log(ξ) ⌉ , log(T )log(γ2ρmax)+log(1/ξ) } , where Cb is a constant whose definition could be found in the proof of Proposition 1 in Appendix D.1, Bφ := maxs∈S ‖φ(s)‖2, and ξ := max{γ, χ}. Then the output θT satisfies
E [ ‖θT − θ∗‖22 ] ≤ O
( 1
T a
) ,
where a = 1log1/ξ(γ2ρmax)+1 < 1.
Thus, PER-ETD(0) attains an -accurate solution with Õ ( 1 ) samples if γ2ρmax ≤ 1, and with
Õ ( 1 1/a ) samples if γ2ρmax > 1.
Proof. Note the θ update specified in Algorithm 1 is the closed form solution of the following maximization problem.
θt+1 = argmax θ∈Θ ηt
〈 T̂t(θt), θ 〉 + 1
2 ‖θ − θt‖22.
Applying Lemma 9 with θ∗ = θt+1, η = ηt, G = T̂t(θt), and θ0 = θt yields, for any θ ∈ Θ,
ηt 〈 T̂t(θt), θt+1 − θ 〉 + 1
2 ‖θt − θt+1‖22 ≤
1 2 ‖θt − θ‖22 − 1 2 ‖θt+1 − θ‖22. (42)
Proceed with the first term in the above inequality as follows〈 T̂t(θt), θt+1 − θ 〉 = 〈T (θt+1), θt+1 − θ〉+ 〈T (θt)− T (θt+1), θt+1 − θ〉+ 〈 T̂t(θt)− T (θt), θt+1 − θ
〉 (i)
≥ 〈T (θt+1), θt+1 − θ〉 − L0‖θt − θt+1‖2‖θt+1 − θ‖2 + 〈 T̂t(θt)− T (θt), θt+1 − θ 〉 = 〈T (θt+1), θt+1 − θ〉 − L0‖θt − θt+1‖2‖θt+1 − θ‖2 + 〈 T̂t(θt)− T (θt), θt+1 − θt
〉 + 〈 T̂t(θt)− T (θt), θt − θ
〉 ≥ 〈T (θt+1), θt+1 − θ〉 − L0‖θt − θt+1‖2‖θt+1 − θ‖2 − ∥∥∥T̂t(θt)− T (θt)∥∥∥ 2 · ‖θt+1 − θt‖2
+ 〈 T̂t(θt)− T (θt), θt − θ 〉 ,
where (i) follows from the Cauchy-Schwartz inequality and Lemma 8.
Substituting the above inequality into eq. (42) yields ηt 〈T (θt+1), θt+1 − θ〉 − ηtL0‖θt − θt+1‖2‖θt+1 − θ‖2 − ηt ∥∥∥T̂t(θt)− T (θt)∥∥∥
2 · ‖θt+1 − θt‖2
+ ηt 〈 T̂t(θt)− T (θt), θt − θ 〉 + 1
2 ‖θt − θt+1‖22 ≤
1 2 ‖θt − θ‖22 − 1 2 ‖θt+1 − θ‖22. (43)
Applying Young’s inequality to ηt ∥∥∥T̂t(θt)− T (θt)∥∥∥
2 · ‖θt+1 − θt‖2 yields
η ∥∥∥T̂t(θt)− T (θt)∥∥∥
2 · ‖θt+1 − θt‖2 ≤
1 4 ‖θt+1 − θt‖22 + η2t ∥∥∥T̂t(θt)− T (θt)∥∥∥2 2 ,
and applying Young’s inequality to ηtL0‖θt − θt+1‖2‖θt+1 − θ‖2 yields
ηtL0‖θt − θt+1‖2‖θt+1 − θ‖2 ≤ 1
4 ‖θt − θt+1‖22 + η2tL20‖θt+1 − θ‖22.
Substituting the above two inequalities into eq. (43) yields
1 2 ‖θt − θ‖22 ≥ ηt 〈T (θt+1), θt+1 − θ〉+
( 1
2 − η2tL20
) ‖θt+1 − θ‖22
+ ηt 〈 T̂t(θt)− T (θt), θt − θ 〉 − η2t ∥∥∥T̂t(θt)− T (θt)∥∥∥2 2 .
Taking expectation conditioned on Ft−1 on the both sides of the above inequality, we obtain 1
2 ‖θt − θ‖22 ≥ ηtE [〈T (θt+1), θt+1 − θ〉|Ft−1] +
( 1
2 − η2tL20
) E [ ‖θt+1 − θ‖22 ∣∣Ft−1] + ηt 〈 E [ T̂t(θt)− T (θt) ∣∣∣Ft−1] , θt − θ〉− η2tE [∥∥∥T̂t(θt)− T (θt)∥∥∥2 2
∣∣∣∣Ft−1] . (44)
Letting θ = θ∗ and applying Lemma 7 to eq. (44) yields
1 2 ‖θt − θ∗‖22 ≥
( 1
2 + µ0ηt − η2tL20
) E [ ‖θt+1 − θ∗‖22 ∣∣Ft−1] − ηtCbBφξb ‖θt − θ∗‖22 − ηtCb approxξ b‖θt − θ∗‖2
− η2tE [∥∥∥T̂t(θt)− T (θt)∥∥∥2
2 ∣∣∣∣Ft−1] (i)
≥ ( 1
2 + µ0ηt − η2tL20
) E [ ‖θt+1 − θ∗‖22 ∣∣Ft−1] − ηtCbBφξb ‖θt − θ∗‖22 − ηtCb approxξ
b‖θt − θ∗‖2 − 4η2tC2bB2φξ2b‖θt − θ∗‖22 − 4η2tC2b ξ2b 2approx − 2σ2η2t , (45)
where (i) follows from Propositions 1 and 2, and the facts that (x+ y)2 ≤ 2x2 + 2y2 and∥∥∥T̂t(θt)− T (θt)∥∥∥2 2 ≤ 2 ∥∥∥E [T̂t(θt)∣∣∣Ft−1]− T (θt)∥∥∥2 2 + 2 ∥∥∥E [T̂t(θt)∣∣∣Ft−1]− T̂t(θt)∥∥∥2 2
≤ 2 ∥∥∥T̂ (θt)∥∥∥2
2 + 2 ∥∥∥E [T̂t(θt)∣∣∣Ft−1]− T̂t(θt)∥∥∥2 2 .
Taking expectation on both sides of the above inequality yields( 1
2 + µ0ηt − η2tL20
) E [ ‖θt+1 − θ∗‖22 ] ≤ ( 1
2 + CbBφξ
bηt + 4C 2 bB 2 φξ 2bη2t ) E [ ‖θt − θ∗‖22 ] + ηtCbBθ approxξ b
+ 4η2tC 2 b ξ 2b 2approx + 2σ 2η2t .
Recall that we set t0 = 8L20 µ20
. Let αt = (t + t0 + 1)(t + t0 + 2). Multiplying 2αt on both sides of the above inequality and telescoping from t = 0, 1, 2, . . . , T − 1 yields
T−1∑ t=0 αt ( 1 + 2µ0ηt − 2η2tL20 ) E [ ‖θt+1 − θ∗‖22 ]
≤ T−1∑ t=0 αt ( 1 + 2CbBφξ bηt + 8C 2 bB 2 φξ 2bη2t ) E [ ‖θt − θ∗‖22 ] + ( 4σ2 + 8C2b ξ
2b 2approx ) T−1∑ t=0 αtη 2 t + 2CbBθ approxξ b T−1∑ t=0 αtηt. (46)
Recall the setting of ηt, we have
1 + 2µ0ηt − 2η2tL20 = 1 + 3µ0ηt
2
( 4
3 − 4 3µ0 ηtL 2 0 ) = 1 +
3µ0ηt 2
( 1 + 1
3
( 1− 4
µ0 ηtL
2 0 )) (i) ≥ 1 + 3µ0ηt 2 ,
where (i) follows from the fact that 1− 4ηtL 2 0 µ0 ≥ 1− 8L 2 0 µ20t0 ≥ 0. Multiplying αt on both sides of the above inequality yields
αt(1 + 2µ0ηt − 2η2tL20) ≥ (t+ t0 + 1)(t+ t0 + 2) (
1 + 3µ0 2
2
µ0(t+ t0) ) = (t+ t0 + 1)(t+ t0 + 2)(t+ t0 + 3)/(t+ t0). (47)
Under appropriate value of b, we have CbBφξb ≤ µ05 . Which implies that
2CbBφξ bηt + 8C 2 bB 2 φξ 2bη2t = µ0ηt 2 + µ0ηt 2
( 4CbBφξ b
µ0 +
16C2bB 2 φξ 2bηt
µ0 − 1
)
≤ µ0ηt 2 + µ0ηt 2
( 4
5 + 16µ0ηt 25
− 1 )
≤ µ0ηt 2 + µ0ηt 2
( 4µ20
25L20 − 1 5 ) ≤ µ0ηt
2 .
Multiplying αt+1 on both sides of the above inequality yields
αt+1(1 + 2CbBφξ bηt+1 + 8C 2 bB 2 φξ 2bη2t+1) ≤ αt+1 ( 1 + µ0ηt+1
2 ) ≤ αt+1 ( 1 +
µ0ηt+1 2 ) = (t+ t0 + 2)(t+ t0 + 3) ( 1 +
µ0 2
2
µ0(t+ t0 + 1) ) = (t+ t0 + 2) 2(t+ t0 + 3)/(t+ t0 + 1). (48)
Equations (47) and (48) together imply that
αt(1 + 2µ0ηt − 2η2tL20)− αt+1(1 + 2CbBφξbηt + 8C2bB2φξ2bη2t )
≥ (t+ t0 + 1)(t+ t0 + 2)(t+ t0 + 3) t+ t0 − (t+ t0 + 2) 2(t+ t0 + 3) t+ t0 + 1
= (t+ t0 + 2)(t+ t0 + 3)
(t+ t0)(t+ t0 + 1)
( (t+ t0 + 1) 2 − (t+ t0)(t+ t0 + 2) )
= (t+ t0 + 2)(t+ t0 + 3)
(t+ t0)(t+ t0 + 1)
> 0.
The above inequality shows that the ‖θt − θ∗‖22, t = 1, . . . , T − 1, terms on both sides of eq. (46) can be canceled, which indicates the following
(T + t0)(T + t0 + 1) ( 1 + 2µ0ηT−1 − 2η2T−1L20 ) E [ ‖θT − θ∗‖22 ] ≤ (t0 + 1)(t0 + 2) ( 1 + 2CbBφξ bη0 + 8C 2 bB 2 φξ 2bη20 ) ‖θ0 − θ∗‖22
+ ( 4σ2 + 8C2b ξ 2b 2approx ) T−1∑ t=0 αtη 2 t + 2CbBθ approxξ b T−1∑ t=0 αtηt. (49)
Note that ∑T−1 t=0 αtη 2 t ≤ ∑T−1 t=0
6 µ20 ≤ 6T µ20 , 1 + 2µ0ηT−1 − 2η2T−1L20 ≥ 1, and
T−1∑ t=0 αtηt ≤ 4 µ0 T−1∑ t=0 (t+ t0 + 2) ≤ 2 µ0 (T + t0 + 2) 2.
Dividing (T + t0)(T + t0 + 1) ( 1 + 2µ0ηT−1 − 2η2T−1L20 ) on both sides of eq. (49) yields
E [ ‖θT − θ∗‖22 ] ≤ (t0 + 1)(t0 + 2)
(T + t0)(T + t0 + 1)
( 1 +
µ0η0 2
) ‖θ0 − θ∗‖22
+ 24σ2 + 48C2b ξ 2b 2approx µ20
1
T + t0 + 1 +
4CbBθ approxξ b
µ0
(T + t0 + 2) 2
(T + t0 + 1)(T + t0) = O ( ‖θ0 − θ2‖22
T 2
) +O ( σ2
T
) +O ( C2b ξ 2b
T
) +O ( Cbξ b ) . (50)
Based on different conditions of σ2, we pick different b and the convergence rate is as follows.
(a). γ2ρmax ≤ 1, Proposition 2 show that σ2 ≤ O(b). We specify
b = max
{⌈ log(µ0)−log(5CbBφ)
log(ξ)
⌉ , log T
log(1/ξ)
} ≤ O(log(T )).
Equation (50) yields,
E [ ‖θT − θ∗‖22 ] = O
( ‖θ0 − θ2‖22
T 2
) +O ( log(T )
T
) +O ( 1
T 2
) +O ( 1
T
) = Õ ( 1
T
) .
(b). γ2ρmax > 1, Proposition 2 show that σ2 = O ( (γ2ρmax) b ) . We specify
b = max {⌈
log(µ0)−log(5CbBφ) log(ξ) ⌉ , log(T )log(γ2ρmax)+log(1/ξ) } .
Equation (50) yields
E [ ‖θT − θ∗‖22 ] = O
( ‖θ0 − θ2‖22
T 2
) +O ( T 1−a
T
) +O ( C2b T 1+a ) +O ( Cb T a ) = O ( 1 T a ) .
E PROOFS OF PROPOSITIONS AND THEOREM FOR PER-ETD(λ)

heading: E.1 PROOF OF PROPOSITION 3
text: Define the matrix At := ρbte b t(φ b t − γφb+1t ) and ct := rbtρbtebt . We have
T̂ λt (θt) = Atθt − ct. (51)
Recall that θt is Ft−1-measurable. We have E [ T̂ λt (θt) ∣∣∣Ft−1] = E [At|Ft−1] θt − E [ct|Ft−1] .
To bound the bias error term ∥∥∥E [T̂ λt (θt)∣∣∣Ft−1]− T λ(θt)∥∥∥
2 , we first take conditional expectations
on At and ct, respectively, as following
E [At|Ft−1] = E [ ρbte b t(φ b t − γφb+1t )> ∣∣Ft−1] (i) =
∑ s∈S,a∈A,s′∈S P ( sbt = s, a b t = a, s b+1 t = s ′∣∣Ft−1) · E [ ρbte b t(φ b t − γφb+1t )>
∣∣Ft−1, sbt = s, abt = a, sb+1t = s′] (ii) = ∑ s,a,s′ P ( sbt = s ∣∣Ft−1)µ(a|s)P(s′|s, a) · π(a|s) µ(a|s) E [ ebt ∣∣sbt = s,Ft−1] (φ(s)− γφ(s′))>
= ∑ s∈S P ( sbt = s ∣∣Ft−1)E [ebt∣∣Ft−1, sbt = s] ∑ a∈A,s′∈S π(a|s)P(s′|s, a) (φ(s)− γφ(s′))>
= ∑ s∈S P ( sbt = s ∣∣Ft−1)E [ebt∣∣Ft−1, sbt = s] · ((Φ)(s,·) − γ(PπΦ)(s,·)) , (52) where (i) follows from the law of total probability and (ii) follows from the Markov property and the fact that ebt only depends on (s 0 t , a 0 t , s 1 t , . . . , s b t).
Define βτ (s) = P (sτt = s|Ft−1)E [ ebt ∣∣Ft−1, sτt = s]. We have
βb(s) = P ( sbt = s ∣∣Ft−1)E [ebt∣∣sbt = s,Ft−1] (i) = P ( sbt = s
∣∣Ft−1) · ∑
s̃∈S,ã∈A P ( sb−1t = s̃, a b−1 t = ã ∣∣sbt = s,Ft−1) · E [ γλρb−1t e b−1 t + (λ+ (1− λ)(1 + ρb−1t γF b−1t )φbt)
∣∣sb−1t = s̃, ab−1t = ã, sbt = s,Ft−1] (ii) = P ( sbt = s
∣∣Ft−1)φ(s) + P ( sbt = s
∣∣Ft−1) ∑ s̃∈S,ã∈A
P ( sb−1t = s̃ ∣∣Ft−1)µ(ã|s̃)P(s|s̃, ã) P ( sbt = s
∣∣Ft−1) · π(ã|s̃) µ(ã|s̃) · E [ γλeb−1t + (1− λ)γF b−1t φ(s)
∣∣sb−1t = s̃,Ft−1] = P ( sbt = s
∣∣Ft−1)φ(s) +∑ s̃∈S P ( sb−1t = s̃ ∣∣Ft−1)Pπ(s|s̃) · E [ γλeb−1t + (1− λ)γF b−1t φ(s)
∣∣sb−1t = s̃,Ft−1] (iii) = (λdµ,b(s) + (1− λ)fb(s)) · φ(s) + γλ(P>π βb−1)s, (53)
where (i) follows from the law of total probability, (ii) follows from the Bayes rule and the Markov property, and (iii) follows from the following definitions: dµ,b(s) = P ( sbt = s|Ft−1 ) , fb(s) = dµ,b(s)E [ F bt = s|sbt = s,Ft−1 ] , fb = dµ,b + γP>π fb−1, and βτ (s) =
P (sτt = s|Ft−1)E [ ebt ∣∣Ft−1, sτt = s].
Define the matrix βτ ∈ Rd×|S|, where βτ = (βτ (1), βτ (2), . . . , βτ (|S|)). Then, eq. (53) implies that
βb = λΦ >Dµ,b + (1− λ)Φ>Fb + γλβb−1Pπ, (54)
where Dµ,b := diag(dµ,b(1), dµ,b(2), . . . , dµ,b(|S|)) and Fb = diag(fb). Recursively applying the above equality yields
βb = (γλ) bβ0P b π + λ b−1∑ τ=0 (γλ)τΦ>Dµ,b−τP τ π + (1− λ) b−1∑ τ=0 (γλ)τΦ>Fb−τP τ π . (55)
Taking expectation of ct conditioned on Ft−1, we have E [ct|Ft−1] = E [ ρbte b tr b t ∣∣Ft−1] =
∑ s∈S,a∈A P ( sbt = s, a b t = a ∣∣Ft−1)E [ρbtebtrbt ∣∣sbt = s, abt = a,Ft−1] =
∑ s∈S,a∈A P ( sbt = s ∣∣Ft−1)µ(a|s) · π(a|s) µ(a|s) r(s, a)E [ ebt ∣∣sbt = s,Ft−1]
= ∑ s∈S rπ(s)P ( sbt = s ∣∣Ft−1)E [ebt∣∣sbt = s,Ft−1] = ∑ s∈S rπ(s)βb(s). (56)
Substituting eqs. (52) and (56) into eq. (51) yields E [ T̂ λt (θt) ∣∣∣Ft−1] = ∑ s∈S βb(s) (Φθt − γPπΦθt − rπ)s = βb (Φθt − γPπΦθt − rπ) .
Recall the definition of T λ(θ). We have T λ(θt)− E [ T̂ λt (θt) ∣∣∣Ft−1] = (Φ>M(I − γλPπ)−1 − βb) (Φθt − γPπΦθt − rπ) . (57) We then proceed to bound the term Φ>M(I − γλPπ)−1 − βb
Φ>M(I − γλPπ)−1 − βb (i) = Φ>M ( ∞∑ τ=0 (γλ)τP τπ ) − βb
(ii) = Φ> (λDµ + (1− λ)F ) ( ∞∑ τ=0 (γλ)τP τπ )
− ( (γλ)bβ0P b π + λ b−1∑ τ=0 (γλ)τΦ>Dµ,b−τP τ π + (1− λ) b−1∑ τ=0 (γλ)τΦ>Fb−τP τ π )
= λ b−1∑ τ=0 (γλ)τΦ> (Dµ −Dµ,b−τ )P τπ + (1− λ) b−1∑ τ=0 (γλ)τΦ> (F − Fb−τ )P τπ
+ ∞∑ τ=b (γλ)τΦ>(λDµ + (1− λ)F )P τπ − λ(γλ)bΦ>Dµ,0P bπ,
where (i) follows from the fact that (I − γPπ)−1 = ∑∞ τ=0 γ
τP τπ , and (ii) follows from eq. (55). Substituting the above equality into eq. (57) and taking `2 norm on the both sides yield∥∥∥T λ(θt)− E [T̂ λt (θt)∣∣∣Ft−1]∥∥∥
2
= ∥∥∥∥∥ ( λ b−1∑ τ=0 (γλ)τΦ> (Dµ −Dµ,b−τ )P τπ + (1− λ) b−1∑ τ=0 (γλ)τΦ> (F − Fb−τ )P τπ
+ ∞∑ τ=b (γλ)τΦ>(λDµ + (1− λ)F )P τπ − λ(γλ)bΦ>Dµ,0P bπ
) (Φθt − γPπθt − rπ) ∥∥∥∥∥ 2
≤ λ b−1∑ τ=0 (γλ)τ ∥∥Φ> (Dµ −Dµ,b−τ )P τπ (Φθt − γPπΦθt − rπ)∥∥2
+ (1− λ) b−1∑ τ=0 (γλ)τ ∥∥Φ> (F − Fb−τ )P τπ (Φθt − γPπΦθt − rπ)∥∥2
+ ∞∑ τ=b (γλ)τ ∥∥Φ> (λDµ + (1− λ)F )P τπ (Φθt − γPπΦθt − rπ)∥∥2
+ λ(γλ)b ∥∥Φ>Dµ,0P bπ (Φθt − γPπΦθt − rπ)∥∥2
(i) ≤ λ b−1∑ τ=0 (γλ)τBφ‖dµ − dµ,b−τ‖1(1 + γ) (Bφ‖θt − θ∗λ‖2 + approx)
+ (1− λ) b−1∑ τ=0 (γλ)τBφ ‖f − fb−τ‖1 (1 + γ) (Bφ‖θt − θ ∗ λ‖2 + C approx)
+ ∞∑ τ=b (γλ)τBφ (λ‖dµ‖1 + (1− λ)‖f‖1) (1 + γ) (Bφ‖θt − θ∗λ‖2 + approx)
+ λ(γλ)bBφ‖dµ,0‖1(1 + γ) (Bφ‖θt − θ∗λ‖2 + approx) (ii)
≤ ( B2φ‖θt − θ∗λ‖2 +Bφ approx ) ·
( b−1∑ τ=0 (γλ)τ ( λ(1 + γ)CMχ b−τ + (1− λ)(1 + γ) ( CM |γ−χ|ξ b−τ + γb−τ (1 + ‖f‖1) )))
+ (1 + γ) ( B2φ‖θt − θ∗λ‖2 +Bφ approx )((λ+ (1− λ)‖f‖1 1− γλ + λ ) (γλ)b ) (iii)
≤ ( B2φ‖θt − θ∗λ‖2 +Bφ approx ) · (1 + γ) ( λ
|χ−γλ|CMξ b + CM (1−λ)|γ−χ|(ξ−γλ)ξ b +(1 + ‖f‖1)γb + ( λ+(1−λ)‖f‖1 1−γλ + λ ) (γλ)b )
(iv)
≤ Cb,λ (Bφ‖θt − θ∗λ‖2 + approx) ξb, where (i) follows from Lemma 5 and eq. (29), (ii) follows from Lemma 1 and eq. (28), in (iii) we define
Cb,λ := Bφ(1 + γ) ( λ |χ−γλ|CM + CM (1−λ) |γ−χ|(ξ−γλ) + 1 + ‖f‖1 + ( λ+(1−λ)‖f‖1 1−γλ + λ )) ,
and (iv) follows from Lemma 3.

heading: E.2 PROOF OF PROPOSITION 4
text: According to the definition of T̂ λt , we have E [∥∥∥T̂ λt (θt)∥∥∥2
2 ∣∣∣∣Ft−1] = E [ (ρbt) 2 ( rbt + γθ > t φ b+1 t − θ>t φbt )2 (ebt) >ebt
∣∣∣Ft−1] (i) =
∑ s∈S,a∈A,s′∈S P ( sbt = s, a b t = a, s b+1 t = s ′∣∣Ft−1) · E [ (ρbt) 2 ( rbt + γθ > t φ b+1 t − θ>t φbt )2 (ebt) >ebt
∣∣∣sbt = s, abt = a, sb+1t = s′,Ft−1] (ii) =
∑ s∈S,a∈A,s′∈S P ( sbt = s ∣∣Ft−1)µ(a|s)P(s′|s, a) π2(a|s) µ2(a|s) (r(s, a) + γθ>t φ(s ′)− θ>t φ(s))2E [ (ebt) >ebt ∣∣sbt = s,Ft−1]
(iii) ≤ ∑ s∈S P ( sbt = s ∣∣Ft−1)E [(ebt)>ebt∣∣sbt = s,Ft−1] · ∑ s′∈S Pµ,π(s ′|s)(r(s, a) + γφ(s′)>θt − φ(s)>θt)2
(iv) ≤ ρmax ( 4(1 + γ2)B2φB 2 θ + 2r 2 max ) B2φ ∑ s∈S P ( sbt = s ∣∣Ft−1)E [(ebt)>ebt∣∣sbt = s,Ft−1] , (58)
where (i) follows from the law of total probability, (ii) follows from the Markov property and the fact that ebt only depends on (s 0 t , a 0 t , . . . , s b t), and (iii) follows from eq. (31) and the fact∑
s′ Pµ,π(s ′|s) ≤ ρmax. Define ∆b(s) = P ( sbt = s|Ft−1 ) E [ (ebt) >ebt ∣∣sbt = s,Ft−1]. We then proceed to bound the term ∆b(s). We have
∆b(s)
(i) = P ( sbt = s|Ft−1 )∑ s̃∈S,ã∈A P ( sb−1t = s̃, a b−1 t = ã
∣∣sbt = s,Ft−1)E [(ebt)>ebt∣∣sb−1t = s̃, ab−1t = ã, sbt = s,Ft−1] (ii) = P ( sbt = s|Ft−1
) ∑
s̃∈S,ã∈A
P ( sb−1t = s̃ ∣∣Ft−1)µ(ã|s̃)P(s|s̃, ã) P ( sbt = s|Ft−1 ) E [(ebt)>ebt∣∣sb−1t = s̃, ab−1t = ã, sbt = s,Ft−1] (iii) =
∑ s̃∈S,ã∈A P ( sb−1t = s̃ ∣∣Ft−1)µ(ã|s̃)P(s|s̃, ã) · E [( γλρb−1t e b−1 t + ( λ+ (1− λ) ( γρb−1t F b−1 t + 1 )) φbt )>
· ( γλρb−1t e b−1 t + ( λ+ (1− λ) ( γρb−1t F b−1 t + 1 )) φbt )∣∣sb−1t = s̃, ab−1t = ã, sbt = s,Ft−1]
= ∑ s̃∈S,ã∈A P ( sb−1t = s̃ ∣∣Ft−1)µ(ã|s̃)P(s|s̃, ã) E [ (γλ)2(ρb−1t ) 2(eb−1t ) >eb−1t + (1− λ)2γ2(ρb−1t F b−1t )2φ(s)>φ(s) + φ(s)>φ(s)
+2γ2λ(1− λ)(ρb−1t )2F b−1t φ(s)>eb−1t + 2γλρb−1t φ(s)>eb−1t +2(1− λ)γρb−1t F b−1t φ(s)>φ(s) ∣∣sb−1t = s̃, ab−1t = ã, sbt = s,Ft−1] = P ( sbt = s|Ft−1 ) ‖φ(s)‖22
+ φ>(s) ∑ s̃∈S Pπ(s|s̃)P ( sb−1t = s̃ ∣∣Ft−1)E [2γλeb−1t + 2γ(1− λ)F b−1t φ(s)∣∣sb−1t = s̃,Ft−1] + λ2γ2
∑ s̃∈S Pµ,π(s|s̃)P ( sb−1t = s̃ ∣∣Ft−1)E [(eb−1t )>eb−1t ∣∣sb−1t = s̃,Ft−1] + 2γ2λ(1− λ)
∑ s̃∈S Pµ,π(s|s̃)P ( sb−1t = s̃ ∣∣Ft−1)E [F b−1t φ(s)>eb−1t ∣∣sb−1t = s̃,Ft−1] + ‖φ(s)‖22γ2(1− λ)2
∑ s̃∈S Pµ,π(s|s̃)P ( sb−1t = s̃ ∣∣Ft−1)E [(F b−1t )2∣∣sb−1t = s̃,Ft−1] ≤ B2φdµ,b(s) + 2γλφ>(s)(βb−1Pπ)(·,s) + 2γ(1− λ)B2φ(P>π fb−1)s + λ2γ2(P>µ,π∆b−1)s + γ
2(1− λ)2B2φ(P>µ,πrb−1)s + 2γ2λ(1− λ) ∑ s̃∈S Pµ,π(s|s̃)P ( sb−1t = s̃ ∣∣Ft−1)E [F b−1t φ(s)>eb−1t ∣∣sb−1t = s̃,Ft−1] (iv) = B2φdµ,b(s) + λ
2γ2(P>µ,π∆b−1)s + 2γ(1− λ)B2φ(P>π fb−1)s + 2γλφ>(s)(βb−1Pπ)(·,s) + γ2(1− λ)2B2φ(P>µ,πrb−1)s + 2γ2λ(1− λ)φ(s)>(δb−1Pµ,π)(·,s), (59)
where (i) follows from the law of total probability, (ii) follows from the Bayes rule, (iii) follows the update rule of ebt and in (iv) we define
δτ (s) = P (sτt = s|Ft−1)E [F τt eτt |sτt = s,Ft−1] .
Summing eq. (59) over S yields 1>∆b = ∑ s ∆b(s)
≤ B2φ1>dµ,b(s) + λ2γ21>P>µ,π∆b−1 + 2γ(1− λ)B2φ1>P>π fb−1 + 2γλtrace (Φβb−1Pπ) + γ2(1− λ)2B2φ1>P>µ,πrb−1 + 2γ2λ(1− λ)trace (Φδb−1Pµ,π)
(i) ≤ λ2γ2ρmax1>∆b−1 +B2φ + 2γ(1− λ)B2φ1>fb−1 + 2γλtrace (Φβb−1Pπ) + γ2(1− λ)2B2φρmax1>rb−1 + 2γ2λ(1− λ)trace (Φδb−1Pµ,π) ,
where (i) follows from Lemma 4 with P = Pµ,π .
Recursively applying the above inequality, we have
1>∆b ≤ (λ2γ2)bρbmax1>∆0 + b∑
τ=1
(λ2γ2)b−τ (ρmax) b−τ (B2φ + 2γ(1− λ)B2φ1>fτ−1
+2γλtrace (Φβτ−1Pπ) + γ 2(1− λ)2B2φρmax1>rτ−1 + 2γ2λ(1− λ)trace (Φδτ−1Pµ,π)
) .
(60)
Substituting eq. (55) into trace (ΦβτPπ) with b and τ replaced by τ and m respectively yields
trace (ΦβτPπ)
(i) = (γλ)τ trace ( Φβ0P τ+1 π ) + λ
τ−1∑ m=0 (γλ)m ( trace ( ΦΦ>Dµ,τ−mP m+1 π ) + (1− λ)trace ( ΦΦ>Fτ−mP m+1 π )) (ii) = (γλ)τ trace ( P τ+1π ΦΦ >Dµ,0 )
+ λ τ−1∑ m=0 (γλ)m ( trace ( Pm+1π ΦΦ >Dµ,τ−m ) + (1− λ)trace ( Pm+1π ΦΦ >Fτ−m ))
(iii) ≤ (γλ)τB2φ1>dµ,0 +B2φ τ−1∑ m=0 (γλ)m (λ‖dµ,τ−m‖1 + (1− λ)‖fτ−m‖1)
(iv) ≤ (γλ)τB2φ + 1− (γλ)τ
1− γλ (λ+ (1− λ)(1 + ‖f‖1))B2φ
≤ B2φ
1− γλ (1 + (1− λ)‖f‖1) , (61)
where (i) follows from eq. (55), (ii) follows from the facts that trace(AB) = trace(BA) and δ0 = Φ >Dµ,0, (iii) follows from Lemma 6 with P = Pπ , and (iv) follows from eq. (38).
Next, we proceed to bound the term trace ( Φ>δτ−1Pµ,π ) .
δb−1(s̃) (i) = P ( sb−1t = s̃ ∣∣Ft−1)E [F b−1t (γλρb−2t eb−2t + (λ+ (1− λ)F b−1t )φ(s̃))∣∣sb−1t = s̃,Ft−1] (ii) = (1− λ)P ( sb−1t = s̃
∣∣Ft−1)E [(F b−1t )2∣∣sb−1t = s̃,Ft−1]φ(s̃) + λP ( sb−1t = s̃
∣∣Ft−1)E [F b−1t ∣∣sb−1t = s̃,Ft−1]φ(s̃) + γλP ( sb−1t = s̃
∣∣Ft−1)E [ρb−2t eb−2t ∣∣sb−1t = s̃,Ft−1]φ(s̃) + γ2λP ( sb−1t = s̃
∣∣Ft−1)E [(ρb−2t )2F b−2t eb−2t ∣∣sb−1t = s̃,Ft−1]φ(s̃) (iii) = (1− λ)rb−1(s̃)φ(s̃) + λfb−1(s̃)φ(s̃)
+ P ( sb−1t = s̃ ∣∣Ft−1) ∑ s′′,a′′ P ( sb−2t = s ′′, ab−2t = a ′′∣∣sb−1t = s̃,Ft−1)
· E [ γλρb−2t e b−2 t + γ 2λ(ρb−2t ) 2F b−2t e b−2 t ∣∣sb−2t = s′′, ab−2t = a′′, sb−1t = s̃,Ft−1] = (1− λ)rb−1(s̃)φ(s̃) + λfb−1(s̃)φ(s̃)
+ P ( sb−1t = s̃ ∣∣Ft−1) ∑ s′′,a′′
P ( sb−2t = s ′′ ∣∣Ft−1)µ(a′′|s′′)P(s̃|s′′, a′′)
P ( sb−1t = s̃ ∣∣Ft−1) · E [ γλ π(a′′|s′′) µ(a′′|s′′) eb−2t + γ 2λ π2(a′′|s′′) µ2(a′′|s′′) F b−2t e b−2 t
∣∣∣∣sb−2t = s′′,Ft−1] = (1− λ)rb−1(s̃)φ(s̃) + λfb−1(s̃)φ(s̃) + γλ(βb−2Pπ)(·,s) + γ2λ(δb−2Pµ,π)(·,s),
where (i) follows from the update of eb−1t , (ii) follows from the update rule of F b−1 t , and (iii) follows from the law of total probability.
The above equality implies that
δb−1 = (1− λ)Φ>diag(rb−1) + λΦ>diag(fb−1) + γλβb−2Pπ + γ2λδb−2Pπ,µ.
Recursively applying the above equality yields
δb−1 = b−1∑ m=1 (Φ>((1− λ)diag(rm) + λdiag(fm)) + γλβm−1Pπ)(Pπ,µ)b−1−m
+ (γ2λ)b−1δ0(Pπ,µ) b−1.
Note that the above inequality holds for any fixed b >= 2. As a result, by changing of notation, for all τ ≥ 1, we have
δτ = τ∑ m=1 (Φ>((1− λ)diag(rm) + λdiag(fm)) + γλβm−1Pπ)(Pπ,µ)τ−m + (γ2λ)τδ0(Pπ,µ)τ .
(62)
Substituting eq. (62) into trace (ΦδτPµ,π), we have
trace (ΦδτPµ,π)
= trace ( Φ ( τ∑
m=1
(Φ>((1− λ)diag(rm) + λdiag(fm)) + γλβm−1Pπ)(Pπ,µ)τ−m
+ (γ2λ)τδ0(Pπ,µ) τ ) Pµ,π ) (i) =
τ∑ m=1 trace ( (Pπ,µ) τ−m+1 (ΦΦ>((1− λ)diag(rm) + λdiag(fm)) + γλΦβm−1Pπ)) + trace ( (γ2λ)τ (Pπ,µ) τ+1Φδ0 ) , (63)
where (i) follows from the fact that trace(AB) = trace(BA) and trace(A + B) = trace(A) + trace(B).
Applying Lemma 6 with Q = Pµ,π , C = ρmax, P = Pπ and D = (1− λ)diag(rm), we have trace ( (Pπ,µ) τ−m+1ΦΦ>(1− λ)diag(rm) ) ≤ (1− λ)ρτ−m+1max B2φ‖rm‖1. (64)
Applying Lemma 6 with Q = Pµ,π , C = ρmax, P = Pπ and D = λdiag(fm), we have
trace ( (Pπ,µ) τ+1−mΦΦ>λdiag(fm) ) ≤ λρτ+1−mmax B2φ‖fm‖1 (i) ≤ λρτ+1−mmax B2φ(1 + ‖f‖1), (65)
where (i) follows from eq. (38). For the term trace ( (Pπ,µ) τ+1−mΦβm−1Pπ ) , we have
trace ( (Pπ,µ) τ+1−mΦβm−1Pπ )
(i) = (γλ)m−1trace ( Pmπ (Pπ,µ) τ+1−mΦΦ>Dµ,0 )
+ m−2∑ l=0 (γλ)l ( λtrace ( P l+1π (Pπ,µ) τ+1−mΦΦ>Dµ,m−1−l )
+(1− λ)trace ( P l+1π (Pπ,µ) τ−m+1ΦΦ>Fπ,m−1−l ))
(ii)
≤ B2φρτ+1−mmax ( (γλ)m−11>dµ,0 + m−2∑ l=0 (γλ)l ( λ1>dµ,m−1−l + (1− λ)1>fm−1−l )) (iii)
≤ B2φρ τ+1−m max
1− γλ (1 + (1− λ)‖f‖1) , (66)
where (i) follows from eq. (55) and the facts that trace(A + B) = trace(A) + trace(B) and trace(AB) = trace(BA), (ii) follows from Lemma 6 with Q = Pµ,π , P = Pπ , and D = Fm−1−l and Dπ,m−1−l respectively, and (iii) follow from the eq. (38).
Recall δ0 = Φ>Dµ,0. Applying Lemma 6 with Q = Pµ,π and D = Dµ,0 yields trace ( (γ2λ)τ (Pπ,µ) τ+1Φδ0 ) ≤ (γ2λ)τB2φρτ+1max. (67)
Substituting eqs. (64) to (67) into eq. (63), we have
trace (ΦδτPµ,π)
≤ (γ2λ)τB2φρτ+1max
+ τ∑ m=1 B2φρ τ−m+1 max ( λ(‖f‖1 + 1) + 1 + (1− λ)‖f‖1 1− γλ ) + τ∑ m=1 (1− λ)ρτ−m+1max B2φ‖rm‖1.
(68)
Substituting eqs. (61) and (68) into eq. (60), we have 1>∆b ≤ λ2bγ2bρbmaxB2φ + (1 + 2γ(1− λ)(1 + ‖f‖1) + 2γλCβ)B2φ b∑
τ=1
λ2(b−τ)γ2(b−τ)ρb−τmax
+ γ2(1− λ)2ρb+1maxB2φ b∑
τ=1
λ2b−2τγ2b−2τρ−τmax‖rτ−1‖1 + 2λbγ2b(1− λ)ρbmaxB2φ b∑
τ=1
λb−τ
+ 2γ2λ(1− λ)B2φ ( λ‖f‖1 + 1 +
1 + (1− λ)‖f‖1 1− γλ
) ρbmax b∑ τ=1 γ2b−2τλ2b−2τ τ−1∑ m=1 ρ−mmax
+ 2γ2λ(1− λ)2ρbmaxB2φ b∑
τ=1 γ2b−2τλ2b−2τ τ−1∑ m=1 ρ−mmax‖rm‖1, (69)
where we let Cβ := B2φ 1−γλ (1 + (1− λ)‖f‖1).
Under different conditions of ρmax, the term 1>∆b and E [∥∥∥T̂ λt (θt)∥∥∥2
2 ∣∣∣∣Ft−1] can be upper bounded differently as following:
(a). γ2ρmax < 1, substituting eq. (41) into eq. (69) yields
1>∆b ≤ λ2bγ2bρbmaxB2φ + (1 + 2γ(1− λ)(1 + ‖f‖1) + 2γλCβ)B2φ b∑
τ=1
λ2(b−τ)γ2(b−τ)ρb−τmax
+ γ2(1− λ)2ρb+1maxB2φ b∑
τ=1
λ2b−2τγ2b−2τρ−τmax
( 3 + 2γ‖f‖1
1− γ2 + 1
)
+ 2λbγ2b(1− λ)ρbmaxB2φ b∑
τ=1
λb−τ
+ 2γ2λ(1− λ)B2φ ( λ‖f‖1 + 1 +
1 + (1− λ)‖f‖1 1− γλ
) ρbmax
· b∑
τ=1 γ2b−2τλ2b−2τ τ−1∑ m=1 ρ−mmax
+ 2γ2λ(1− λ)2ρbmaxB2φ b∑
τ=1 γ2b−2τλ2b−2τ τ−1∑ m=1 ρ−mmax ( 3 + 2γ‖f‖1 1− γ2 + 1 )
≤ λ2bγ2bρbmaxB2φ + (1 + 2γ(1− λ)(1 + ‖f‖1) + 2γλCβ)B2φ
1− γ2ρmaxλ
+ γ2(1− λ)2ρmaxB2φ
1− γ2ρmaxλ
( 3 + 2γ‖f‖1
1− γ2 + 1
) + 2λ2bγbρbmaxB 2 φ
+ 2γ2λ(1− λ)B2φ
(1− γ2λ2)(1− ρ−1max)
( λ‖f‖1 + 1 +
1 + (1− λ)‖f‖1 1− γλ
) ρb+1max
+ 2γ2λ(1− λ)2B2φ
(1− γ2λ2)(1− ρ−1max)
( 3 + 2γ‖f‖1
1− γ2 + 1
) ρb+1max, (70)
where the last two terms of the above inequality are of the order O ( ρbmax ) . Therefore, we have 1>∆b ≤ Cρbmax for some C > 0. Substituting eq. (70) into eq. (58) yields
E [∥∥∥T̂ λt (θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ Cσ,λ,1ρbmax, where Cσ,λ,1 > 0 is a constant and is determined by eq. (70).
(b). γ2ρmax = 1, substituting eq. (40) into eq. (69) yields
1>∆b ≤ λ2bB2φ + (1 + 2γ(1− λ)(1 + ‖f‖1) + 2γλCβ)B2φ b∑
τ=1
λ2(b−τ)
+ γ2(1− λ)2ρmaxB2φ b∑
τ=1
λ2b−2τ (4 + 2γ‖f‖1) τ + 2λb(1− λ)B2φ b∑
τ=1
λb−τ
+ 2γ2λ(1− λ)B2φ ( λ‖f‖1 + 1 +
1 + (1− λ)‖f‖1 1− γλ
) ρbmax b∑ τ=1 γ2b−2τλ2b−2τ τ∑ m=1 ρ−mmax
+ 2γ2λ(1− λ)2 (4 + 2γ‖f‖1)B2φ b∑
τ=1
λ2b−2τ τ∑
m=1
ρτ−mmaxm
≤ λ2bB2φ + (1 + 2γ(1− λ)(1 + ‖f‖1) + 2γλCβ)B2φ
1− λ2 + 2λbB2φ
+
( γ2(1− λ)2ρmaxB2φ
1− λ2 (4 + 2γ‖f‖1) + 2γ2λ(1− λ)2 (4 + 2γ‖f‖1)B2φ (1− λ2)(1− ρ−1max)
) b
+ 2γ2λ(1− λ)B2φ
(1− γ2λ2)(1− ρ−1max)
( λ‖f‖1 + 1 +
1 + (1− λ)‖f‖1 1− γλ
) ρb+1max, (71)
where the last term of the above inequality is of the order O ( ρbmax ) . Therefore, we have 1>∆b ≤ Cρbmax for some C > 0. Substituting eq. (71) into eq. (58) yields
E [∥∥∥T̂ λt (θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ Cσ,λ,2ρbmax, where Cσ,λ,2 > 0 is a constant and is determined by eq. (71).
(c). γ2ρmax > 1, substituting eq. (39) into eq. (69) yields
1>∆b ≤ λ2bγ2bρbmaxB2φ + (1 + 2γ(1− λ)(1 + ‖f‖1) + 2γλCβ)B2φ b∑
τ=1
λ2(b−τ)γ2(b−τ)ρb−τmax
+γ2b+2(1− λ)2ρb+1maxB2φ (
3 + 2γ‖f‖1 γ2ρmax − 1 + 1 ) b∑ τ=1 λ2b−2τ + 2λbγ2b(1− λ)ρbmaxB2φ b∑ τ=1 λb−τ
+ 2γ2λ(1− λ)B2φ ( λ‖f‖1 + 1 +
1 + (1− λ)‖f‖1 1− γλ
) ρbmax b∑ τ=1 γ2b−2τλ2b−2τ τ−1∑ m=1 ρ−mmax
+ 2γ2λ(1− λ)2ρbmaxB2φ (
3 + 2γ‖f‖1 γ2ρmax − 1 + 1 ) b∑ τ=1 γ2b−2τλ2b−2τ τ−1∑ m=1 γ2m
≤ λ2bγ2bρbmaxB2φ + (1 + 2γ(1− λ)(1 + ‖f‖1) + 2γλCβ)B2φ
γ2ρmax − 1 · γ2bρbmax
+ γ2b+2(1− λ)2ρb+1maxB2φ
1− λ2
( 3 + 2γ‖f‖1 γ2ρmax − 1 + 1 ) + 2λbγ2bρbmaxB 2 φ
+ 2γ2λ(1− λ)B2φ
(1− γ2λ2)(1− ρ−1max)
( λ‖f‖1 + 1 +
1 + (1− λ)‖f‖1 1− γλ
) ρb+1max
+ 2γ2λ(1− λ)2
(1− γ2)(1− γ2λ2) B2φ ( 3 + 2γ‖f‖1 γ2ρmax − 1 + 1 ) ρbmax, (72)
where the last term of the above inequality is of the order O ( ρbmax ) . Therefore, we have 1>∆b ≤ Cρbmax for some C > 0. Substituting eq. (72) into eq. (58) yields
E [∥∥∥T̂ λt (θt)∥∥∥2
2 ∣∣∣∣Ft−1] ≤ Cσ,λ,3ρbmax, where Cσ,λ,3 > 0 is a constant and is determined by eq. (72).
To summarize, the variance term E [∥∥∥T̂t(θt)∥∥∥2
2 ∣∣∣∣Ft−1] can be bounded by σ2λ = O(ρbmax).

heading: E.3 PROOF OF THEOREM 2
text: Theorem 4 (Formal Statement of Theorem 2). Suppose Assumptions 1 and 2 hold. Consider PERETD(λ) specified in Algorithm 2. Let the stepsize ηt = 2µλ(t+tλ) , tλ = 8L2λ µ2λ
, where µλ is defined in Lemma 7 and Lλ is defined in Lemma 8 in Appendix C. Further let
b = max {⌈
log(µλ)−log(5Cb,λBφ) log(ξ) ⌉ , log(T )log(ρmax)+log(1/ξ) } ,
where Cb,λ is a constant defined in the proof of Proposition 3 in Appendix E.1, Bφ := maxs∈S ‖φ(s)‖2, and ξ := max{γ, χ}. Let the projection set Θ = { θ ∈ Rd : ‖θ‖2 ≤ Bθ } , where Bθ = ‖Φ>‖2rmax
(1−γ)µλ (which implies θ ∗ λ ∈ Θ). Then the output θT of PER-ETD(λ) satisfies
E [ ‖θT − θ∗λ‖22 ] ≤ O
( 1
T aλ
) ,
where aλ = 1log1/ξ(ρmax)+1 . Further, PER-ETD(λ) attains an -accurate solution with Õ ( 1 1/aλ ) samples.
Proof. The proof follows the same steps as Theorem 1 by replacing the terms T̂t, T , t0, L0, µ0, Cb, σ2 and θ∗ with T̂ λt , T λ, tλ, Lλ, µλ, Cb,λ, σ2λ and θ∗λ respectively. Specifically, Propositions 3 and 4 are applied to bound the bias and variance over the steps similarly to eq. (45). We then have the convergence as follows.
E [ ‖θT − θ∗λ‖22 ] ≤ O
( ‖θ0 − θ∗λ‖22
T 2
) +O ( σ2λ T ) +O ( ξ2b T ) +O ( ξb )
= O ( ‖θ0 − θ∗λ‖22
T 2
) +O ( ρbmax T ) +O ( ξ2b T ) +O ( ξb ) . (73)
We further specify b = {⌈
log(µ0)−log(5CbBφ) log(ξ) ⌉ , log(T )log(ρmax)+log(1/ξ) } . Then Equation (73) yields
E [ ‖θT − θ∗λ‖22 ] ≤ O
( ‖θ0 − θ∗λ‖22
T 2
) +O ( T 1−aλ
T
) +O ( 1
T 1+aλ
) +O ( 1
T aλ
) = O ( 1
T aλ
) .

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

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. 

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.