Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis

Introduction

In Reinforcement Learning (RL; Sutton and Barto 1998), policy-evaluation refers to the problem of evaluating the value function – a mapping from states to their long-term discounted return under a given policy, using sampled observations of the system dynamics and reward. Policy-evaluation is important both for assessing the quality of a policy, but also as a sub-procedure for policy optimization.

For systems with large or continuous state-spaces, an exact computation of the value function is often impossible. Instead, an approximate value-function is sought using various function-approximation techniques (a.k.a. approximate dynamic-programming; Bertsekas 2012). In this approach, the parameters of the value-function approximation are tuned using machine-learning inspired methods, often based on temporal-differences (TD;Sutton and Barto 1998).

The source generating the sampled data divides policy evaluation into two cases. In the on-policy case, the samples are generated by the target-policy – the policy under evaluation; In the off-policy setting, a different behavior-policy generates the data. In the on-policy setting, TD methods are well understood, with classic convergence guarantees and approximation-error bounds, based on a contraction property of the projected Bellman operator underlying TD (Bertsekas and Tsitsiklis, 1996). These bounds guarantee that the asymptotic error, or bias, of the algorithm is contained. For the off-policy case, however, standard TD methods no longer maintain this contraction property, the error bounds do not hold, and these methods might even diverge (Baird, 1995).

The standard error-bounds may be shown to hold for an importance-sampling TD method (IS-TD), as proposed by Precup, Sutton, and Dasgupta (2001). However, this method is known to suffer from a high variance of its importance-sampling estimator, limiting its practicality.

Lately, Sutton, Mahmood, and White (2015) proposed the emphatic TD (ETD) algorithm: a modification of the TD idea, which converges off-policy (Yu, 2015), and has a reduced variance compared to IS-TD. This variance reduction is achieved by incorporating a certain decay factor over the importance-sampling ratio. However, to the best of our knowledge, there are no results that bound the bias of ETD. Thus, while ETD is assured to converge, it is not known how good its limit actually is.

In this paper, we propose the ETD($\lambda$, $\beta$) framework – a modification of the ETD($\lambda$) algorithm, where the decay rate of the importance-sampling ratio, $\beta$, is a free parameter, and $\lambda$ is the same bootstrapping parameter employed in TD($\lambda$) and ETD($\lambda$). By varying the decay rate, one can smoothly transition between the IS-TD algorithm, through ETD, to the standard TD algorithm.

We investigate the bias of ETD($\lambda$, $\beta$), by studying the conditions under which its underlying projected Bellman operator is a contraction. We show that the original ETD possesses a contraction property, and present the first error bounds for ETD and ETD($\lambda$, $\beta$). In addition, our error bound reveals that the decay rate parameter balances between the bias and variance of the learning procedure. In particular, we show that selecting a decay equal to the discount factor as in the original ETD may be suboptimal in terms of the mean-squared error.

The main contributions of this work are therefore a unification of several off-policy TD algorithms under the ETD($\lambda$, $\beta$) framework, and a new error analysis that reveals the bias-variance trade-off between them.

In recent years, several different off-policy policy-evaluation algorithms have been studied, such as importance-sampling based least-squares TD (Yu, 2012), and gradient-based TD (Sutton et al., 2009; Liu et al., 2015). These algorithms are guaranteed to converge, however, their asymptotic error can be bounded only when the target and behavior policies are similar (Bertsekas and Yu, 2009), or when their induced transition matrices satisfy a certain matrix-inequality suggested by Kolter (2011), which limits the discrepancy between the target and behavior policies. When these conditions are not satisfied, the error may be arbitrarily large (Kolter, 2011). In contrast, the approximation-error bounds in this paper hold for general target and behavior policies.

Preliminaries

We consider an MDP $M=(S,A,P,R,\gamma)$, where $S$ is the state space, $A$ is the action space, $P$ is the transition probability matrix, $R$ is the reward function, and $\gamma\in[0,1)$ is the discount factor.

Given a target policy $\pi$ mapping states to a distribution over actions, our goal is to evaluate the value function:

Linear temporal difference methods (Sutton and Barto, 1998) approximate the value function by

Let $T$ denote the Bellman operator for policy $\pi$, given by

For $\lambda=0$, the ETD(, $\beta$) (Sutton, Mahmood, and White, 2015) algorithm seeks to find a good approximation of the value function by iteratively updating the weight vector $\theta$:

where $F_{t}$ is a decaying trace of the importance-sampling ratios, and $\beta\in(0,1)$ controls the decay rate.

The algorithm of Sutton, Mahmood, and White (2015) selects the decay rate equal to the discount factor, i.e., $\beta=\gamma$. Here, we provide more freedom in choosing the decay rate. As our analysis reveals, the decay rate controls a bias-variance trade-off of ETD, therefore this freedom is important. Moreover, we note that for $\beta=0$, we obtain the standard TD in an off-policy setting Yu (2012), and when $\beta=1$ we obtain the full importance-sampling TD algorithm Precup, Sutton, and Dasgupta (2001).

The ETD(, $\gamma$) algorithm of Sutton, Mahmood, and White (2015) also includes a state-dependent emphasis weight $i(s)$, and a state-dependent discount factor $\gamma(s)$. Here, we analyze the case of a uniform weight $i(s)=1$ and constant discount factor $\gamma$ for all states. While our analysis can be extended to their more general setting, the insights from the analysis remain the same, and for the purpose of clarity we chose to focus on this simpler setting.

An important term in our analysis is the emphatic weight vector $f$, defined by

It can be shown (Sutton, Mahmood, and White, 2015; Yu, 2015), that ETD(, $\beta$) converges to $\theta^{*}$ - a solution of the following projected fixed point equation:

For the fixed point equation (3), a contraction property of $\Pi_{f}T$ is important for guaranteeing both a unique solution, and a bias bound (Bertsekas and Tsitsiklis, 1996).

It is well known that $T$ is a $\gamma$-contraction with respect to the $d_{\pi}$-weighted Euclidean norm (Bertsekas and Tsitsiklis, 1996), and by definition $\Pi_{f}$ is a non-expansion in $f$-norm, however, it is not immediate that the composed operator $\Pi_{f}T$ is a contraction in any norm. Indeed, for the TD(0) algorithm (Sutton and Barto 1998; corresponding to the $\beta=0$ case in our setting), a similar representation as a projected Bellman operator holds, but it may be shown that in the off-policy setting the algorithm might diverge (Baird, 1995). In the next section, we study the contraction properties of $\Pi_{f}T$, and provide corresponding bias bounds.

Bias of ETD(00, β𝛽\beta)

In this section we study the bias of the ETD(, $\beta$) algorithm. Let us first introduce the following measure of discrepancy between the target and behavior policies:

The measure $\kappa$ obtains values ranging from $\kappa=0$ (when there is a state visited by the target policy, but not the behavior policy), to $\kappa=1-\beta$ (when the two policies are identical).

The technical proof is given in the supplementary material. The following theorem shows that for ETD(, $\beta$) with a suitable $\beta$, the projected Bellman operator $\Pi_{f}T$ is indeed a contraction.

where (a) follows from Jensen inequality:

and (b) is by the definition of $f$ in (2).

Hence, $T$ is a $\sqrt{\frac{\gamma^{2}}{\beta}(1-\kappa)}$-contraction. Since $\Pi_{f}$ is a non-expansion in the $f$-weighted norm (Bertsekas and Tsitsiklis, 1996), $\Pi_{f}T$ is a $\sqrt{\frac{\gamma^{2}}{\beta}(1-\kappa)}$-contraction as well. ∎

Recall that for the original ETD algorithm (Sutton, Mahmood, and White, 2015), we have that $\beta=\gamma$, and the contraction modulus is $\sqrt{\gamma(1-\kappa)}<1$, thus the contraction of $\Pi_{f}T$ always holds.

Also note that in the on-policy case, the behavior and target policies are equal, and according to Lemma 1 we have $1-\kappa=\beta$. In this case, the contraction modulus in Theorem 1 is $\gamma$, similar to the result for on-policy TD Bertsekas and Tsitsiklis (1996).

We remark that Kolter (2011) also used a measure of discrepancy between the behavior and the target policy to bound the TD-error. However, Kolter (2011) considered the standard TD algorithm, for which a contraction could be guaranteed only for a class of behavior policies that satisfy a certain matrix inequality criterion. Our results show that for ETD(, $\beta$) with a suitable $\beta$, a contraction is guaranteed for general behavior policies. We now show in an example that our contraction modulus bounds are tight.

Consider an MDP with two states: Left and Right. In each state there are two identical actions leading to either Left or Right deterministically. The behavior policy will choose Right with probability $\varepsilon$, and the target policy will choose Left with probability $\varepsilon$, hence $1-\kappa\approx 1$. Calculating the quantities of interest:

and for small $\varepsilon$ we obtain that $\frac{\left\lVert\gamma Pv\right\rVert^{2}}{\left\lVert v\right\rVert^{2}_{f}}\approx\frac{\gamma^{2}}{\beta}$.

An immediate consequence of Theorem 1 is the following error bound, based on Lemma 6.9 of Bertsekas and Tsitsiklis (1996):

Up to the weights in the norm, the error $\left\lVert\Pi_{f}V^{\pi}-V^{\pi}\right\rVert_{f}$ is the best approximation we can hope for, within the capability of the linear approximation architecture. Corollary 1 guarantees that we are not too far away from it.

Notice that the error $\left\lVert\Phi^{\top}\theta^{*}-V^{\pi}\right\rVert_{d_{\mu}}$ uses a measure $d_{\mu}$ which is independent of the target policy; This could be useful in further analysis of a policy iteration algorithm, which iteratively improves the target policy using samples from a single behavior policy. Such an analysis may proceed similarly to that in Munos (2003) for the on-policy case.

We illustrate the importance of the ETD(, $\beta$) bias bound in a numerical example. Consider the 2-state MDP example of Kolter (2011), with transition matrix $P=(1/2)\underline{\underline{\textbf{1}}}$ (where $\underline{\underline{\textbf{1}}}$ is an all $1$ matrix), discount factor $\gamma=0.99$, and value function $V=[1,1.05]^{\top}$ (with $R=(I-\gamma P)V$). The features are $\Phi=[1,1.05+\varepsilon]^{\top}$, with $\varepsilon=0.001$. Clearly, in this example we have $d_{\pi}=[0.5,0.5]$. The behavior policy is chosen such that $d_{\mu}=[p,1-p]$.

In Figure 1 we plot the mean-squared error $\left\lVert\Phi^{\top}\theta^{*}-V^{\pi}\right\rVert_{d_{\pi}}$, where $\theta^{*}$ is either the fixed point of the standard TD equation $V=\Pi_{d_{\mu}}TV$, or the ETD(, $\beta$) fixed point of (3), with $\beta=\gamma$. We also show the optimal error $\left\lVert\Pi_{d_{\pi}}V-V^{\pi}\right\rVert_{d_{\pi}}$ achievable with these features. Note that, as observed by Kolter (2011), for certain behavior policies the bias of standard TD is infinite. This means that algorithms that converge to this fixed point, such as the GTD algorithm (Sutton et al., 2009), are hopeless in such cases. The ETD algorithm, on the other hand, has a bounded bias for all behavior policies.

The Bias-Variance Trade-Off of ETD(00, β𝛽\beta)

From the results in Corollary 1, it is clear that increasing the decay rate $\beta$ decreases the bias bound. Indeed, for the case $\beta=1$ we obtain the importance sampling TD algorithm (Precup, Sutton, and Dasgupta, 2001), which is known to have a bias bound similar to on-policy TD. However, as recognized by Precup, Sutton, and Dasgupta (2001) and Sutton, Mahmood, and White (2015), the importance sampling ratio $F_{t}$ suffers from a high variance, which increases with $\beta$. The quantity $F_{t}$ is important as it appears as a multiplicative factor in the definition of the ETD learning rule, so its amplitude directly impacts the stability of the algorithm. In fact, the asymptotic variance of $F_{t}$ may be infinite, as we show in the following example:

Consider the same MDP given in Example 1, only now the behavior policy chooses Left or Right with probability $0.5$, and the target policy chooses always Right. For ETD(, $\beta$) with $\beta\in[0,1)$, we have that when $S_{t}=\text{Left}$ then $F_{t}=1$ (since $\rho_{t-1}=0$). When $S_{t}=\text{Right}$, $F_{t}$ may take several values depending on how many steps, $\tau(t)$, was the last transition from Left to Right, i.e. $\tau(t)\stackrel{{\scriptstyle\rm def}}{{=}}\min\{i\geq 0:S_{t-i}=Left\}$. We can write this value as $F^{\tau(t)}$ where:

if $2\beta\neq 1$. Let us assume that $2\beta>1$ since interesting cases happen when $\beta$ is close to 1.

Let’s compute $F_{t}$’s average over time: Following the stationary distribution of the behavior policy, $S_{t}=\text{Left}$ with probability $1/2$. Now, conditioned on $S_{t}=\text{Right}$ (which happens with probability $1/2$), we have $\tau(t)=i$ with probability $2^{-i-1}$. Thus the average (over time) value of $F_{t}$ is

Thus $F_{t}$ amplifies the TD update by a factor of $\frac{1}{2(1-\beta)}$ in average. Unfortunately, the actual values of the (random variable) $F_{t}$ does not concentrate around its expectation, and actually $F_{t}$ does not even have a finite variance. Indeed the average (over time) of $F_{t}^{2}$ is

So although ETD(, $\beta$) converges almost surely (as shown by Yu 2015), the variance of the estimate may be infinite, which suggests a prohibitively slow convergence rate.

In the following proposition we characterize the dependence of the variance of $F_{t}$ on $\beta$.

For the first summand, we get $d_{\mu}(s)$. For the second summand, we get:

Proposition 1 and Corollary 1 show that the decay rate $\beta$ acts as an implicit trade-off parameter between the bias and variance in ETD. For large $\beta$, we have a low bias but suffer from a high variance (possibly infinite if $\beta\geq 1/\sqrt{\lambda(\mu,\pi)}$), and vice versa for small $\beta$. Notice that for the on-policy case, $\lambda(\mu,\pi)=1$ thus for any $\beta<1$ the variance is finite.

Originally, ETD(, $\beta$) was introduced with $\beta=\gamma$, and from our perspective, it may be seen as a specific choice for the bias-variance trade-off. However, there is no intrinsic reason to choose $\beta=\gamma$, and other choices may be preferred in practice, depending on the nature of the problem. In the following numerical example, we investigate the bias-variance dependence on $\beta$, and show that the optimal $\beta$ in term of mean-squared error may be quite different from $\gamma$.

We revisit the 2-state MDP described in Section 3.1, with $\gamma=0.9$, $\varepsilon=0.2$ and $p=0.95$. For these parameter settings, the error of standard TD is $42.55$ ($p$ was chosen to be close to a point of infinite bias for these parameters).

In Figure 2 we plot the mean-squared error $\left\lVert\Phi^{\top}\theta^{*}-V^{\pi}\right\rVert_{d_{\pi}}$, where $\theta^{*}$ was obtained by running ETD(, $\beta$) with a step size $\alpha=0.001$ for $10,000$ iterations, and averaging the results over $10,000$ different runs.

First of all, note that for all $\beta$, the error is smaller by two orders of magnitude than that of standard TD. Thus, algorithms that converge to the standard TD fixed point such as GTD Sutton et al. (2009) are significantly outperformed by ETD(, $\beta$) in this case. Second, note the dependence of the error on $\beta$, demonstrating the bias-variance trade-off discussed above. Finally, note that the minimal error is obtained for $\gamma=0.8$, and is considerably smaller than that of the original ETD with $\beta=\gamma=0.9$.

Contraction Property for ETD(λ𝜆\lambda, β𝛽\beta)

We now extend our results to incorporate eligibility traces, in the style of the ETD($\lambda$) algorithm (Sutton, Mahmood, and White, 2015), and show similar contraction properties and error bounds.

The ETD($\lambda$, $\beta$) algorithm iteratively updates the weight vector $\theta$ according to

where $e_{t}$ is the eligibility trace (Sutton, Mahmood, and White, 2015). In this case, we define the emphatic weight vector $m$ by

The Bellman operator for general $\lambda$ and $\gamma$ is given by:

For $\lambda=0$ we have $P^{\lambda,\beta}_{\pi}=\beta P$, $P^{\lambda,\gamma}_{\pi}=\gamma P$, and $m=f$ so we recover the definitions of ETD(, $\beta$).

Recall that our goal is to estimate the value function $V^{\pi}$. Thus, we would like to know how well the ETD($\lambda$, $\beta$) solution approximates $V^{\pi}$. Mahmood et al. (2015) show that, under suitable step-size conditions, ETD converges to some $\theta^{*}$ that is a solution of the projected fixed-point equation:

In their analysis, however, Mahmood et al. (2015) did not show how well the solution $\Phi^{\top}\theta^{*}$ approximates $V^{\pi}$. Next, we establish that the projected Bellman operator $\Pi_{m}T^{(\lambda)}$ is a contraction. This result will then allow us to bound the error $\left\lVert\Phi^{\top}\theta^{*}-V^{\pi}\right\rVert_{m}$.

$\Pi_{m}T^{(\lambda)}$ is an $\omega$-contraction with respect to the Euclidean $m$-weighted norm where:

(sketch) The proof is almost identical to the proof of Theorem 1, only now we cannot apply Jensen’s inequality directly, since the rows of $P^{\lambda,\beta}$ do not sum to $1$. However:

where $\zeta=\frac{\beta(1-\lambda)}{1-\lambda\beta}$. Notice that each entry of $P^{\lambda,\beta}$ is positive. Therefore $\frac{P^{\lambda,\beta}}{\zeta}$ will hold for Jensen’s inequality. Let $M=diag(m)$, we have

where (a) follows from the Jensen inequality and (b) from Equation (4). Therefore:

The inequalities depending on the two cases originate from the fact that the two matrices $P^{\lambda,\beta},P^{\lambda,\gamma}$ are polynomials of the same matrix $P_{\pi}$, and mathematical manipulation on the corresponding eigenvalues decomposition of $(v_{1}-v_{2})$. The details are given in Lemma 3 of the supplementary material.

Now, for a proper choice of $\beta$, the operator $T^{(\lambda)}$ is a contraction, and since $\Pi_{m}$ is a non-expansion in the $m$-weighted norm, $\Pi_{m}T^{(\lambda)}$ is a contraction as well. ∎

In Figure 3 we illustrate the dependence of the contraction moduli bound on $\lambda$ and $\beta$. In particular, for $\lambda\to 1$, the contraction modulus diminishes to 0. Thus, for large enough $\lambda$, a contraction can always be guaranteed (this can also be shown mathematically from the contraction results of Theorem 2). We remark that a similar result for standard TD($\lambda$) was established by Yu 2012. However, as is well-known (Bertsekas, 2012), increasing $\lambda$ also increases the variance of the algorithm, and we therefore obtain a bias-variance trade-off in $\lambda$ as well as $\beta$. Finally, note that for $\beta=\gamma$, the contraction modulus equals $\sqrt{\frac{\gamma(1-\lambda)}{1-\gamma\lambda}}$, and that for $\lambda=0$ the result is the same as in Theorem 1.

Conclusion

In this work we unified several off-policy TD algorithms under the ETD($\lambda$, $\beta$) framework, which flexibly manages the bias and variance of the algorithm by controlling the decay-rate of the importance-sampling ratio. From this perspective, we showed that several different methods proposed in the literature are special instances of this bias-variance selection.

Our main contribution is an error analysis of ETD($\lambda$, $\beta$) that quantifies the bias-variance trade-off. In particular, we showed that the recently proposed ETD algorithm of Sutton, Mahmood, and White (2015) has bounded bias for general behavior and target policies, and that by controlling the decay-rate in the ETD($\lambda$, $\beta$) algorithm, an improved performance may be obtained by reducing the variance of the algorithm while still maintaining a reasonable bias.

Possible future extensions of our work includes finite-time bounds for off-policy ETD($\lambda$, $\beta$), an error propagation analysis of off-policy policy improvement, and solving the bias-variance trade-off adaptively from data.

References

Appendix A Proof of Lemma 1

Notice that $\kappa$ obtains non-negative values since $d_{\mu}(s),f(s)\geq 0$. Now, if there is a state $s$ visited by the target policy, but not the behavior policy, this means that $d_{\mu}(s)=0$, and that there is some $t$ such that $[d_{\mu}^{\top}P^{t}_{\pi}](s)>0$, and by definition $f(s)\geq[\beta^{t}d_{\mu}^{\top}P^{t}_{\pi}](s)$, so we can get $\kappa=0$.

Next, we prove the upper bound on $\kappa$. Notice that $f(s)\geq 0$, and that $\sum_{s}f(s)=1/(1-\beta)$. Hence, if $d_{\mu}\neq(1-\beta)f$, then there must exist some $s$ such that $d_{\mu}(s)<(1-\beta)f(s)$ so $\kappa<1-\beta$. Now, when $d_{\mu}=d_{\pi}$, by definition $d_{\mu}=(1-\beta)f$ and we obtain this upper bound.

Appendix B Technical Part of Proposition 1

Where (a) comes from the inequality on $f$, (b) also removes the negative summand $\beta^{2}d^{\top}_{\mu}P_{\pi}D^{-1}_{\mu}P^{\top}_{\pi}d_{\mu}$, and swaps sum with $l_{1}$ norm (all coordinates are non-negative), (c) and (d) are from the sub-multiplicative property of induced norms (the $l_{\infty}$ norm originates from the transpose). ∎

So if we can find a constant $\alpha$ such that:

then could swap $\left\lVert P^{\lambda,\gamma}_{\pi}v\right\rVert^{2}_{m}\leq\left\lVert\alpha P^{\lambda,\gamma}_{\pi}v\right\rVert^{2}_{m}$. The expression we want to maximize is:

Taking the derivative with respect to $Re(t_{j}),Im(t_{j})$, shows that there are no extrema points inside the ball $\left|t_{j}\right|\leq 1$ (we know the eigenvalues are inside this ball since they belong to a stochastic matrix), which means we can look at the boundary of this ball $\left|t_{j}\right|=1$ to find the maximum value. Since now we get dependence only on $Re(t_{j})$, the maximum must be on $t_{j}=\pm 1$:

where when $\beta\geq\gamma$ the plus is larger and vice versa. ∎