# Compound Returns Reduce Variance in Reinforcement Learning

Brett Daley  Martha White  Marlos C. Machado

###### Abstract

Multistep returns, such as $n$-step returns and $\lambda$-returns, are
commonly used to improve the sample efficiency of reinforcement learning (RL)
methods. The variance of the multistep returns becomes the limiting factor in
their length; looking too far into the future increases variance and reverses
the benefits of multistep learning. In our work, we demonstrate the ability of
compound returns—weighted averages of $n$-step returns—to reduce variance. We
prove for the first time that any compound return with the same contraction
modulus as a given $n$-step return has strictly lower variance. We
additionally prove that this variance-reduction property improves the finite-
sample complexity of temporal-difference learning under linear function
approximation. Because general compound returns can be expensive to implement,
we introduce two-bootstrap returns which reduce variance while remaining
efficient, even when using minibatched experience replay. We conduct
experiments showing that two-bootstrap returns can improve the sample
efficiency of $n$-step deep RL agents, with little additional computational
cost.

Reinforcement Learning, Temporal-Difference Learning, Credit Assignment,
Variance Reduction, Sample Efficiency

##  1 Introduction

Efficiently learning value functions is critical for reinforcement learning
(RL) algorithms. Value-based RL methods (e.g., Watkins, 1989; Rummery &
Niranjan, 1994; Mnih et al., 2015) encode policies implicitly in a value
function, and policy evaluation is the principal mechanism of learning. Even
when RL methods instead learn parametric policies, accurate value functions
are needed to guide policy improvement (e.g., Silver et al., 2014; Lillicrap
et al., 2016; Fujimoto et al., 2018; Haarnoja et al., 2018) or to serve as a
baseline (e.g., Barto et al., 1983; Sutton, 1984; Williams, 1992; Schulman et
al., 2015a). Quicker policy evaluation is therefore useful to many RL
algorithms.

One way to achieve faster value-function learning is through multistep
returns, in which more than one reward following an action is used to
construct a prediction target. Multistep returns are used extensively in deep
RL (e.g. Schulman et al., 2015b; Mnih et al., 2016; Munos et al., 2016;
Schulman et al., 2017; Hessel et al., 2018; Schrittwieser et al., 2020; Wurman
et al., 2022; Chebotar et al., 2023; Schwarzer et al., 2023), where the value
function is approximated by a neural network. In theory, multistep returns
incorporate more information regarding future outcomes, leading to faster
credit assignment and, in turn, faster learning. However, faster learning is
not guaranteed in practice because looking farther into the future increases
variance and can end up requiring more samples to estimate the mean. These two
opposing factors must be balanced to achieve fast and stable learning. The
most common multistep returns are $n$-step returns and $\lambda$-returns, both
of which span between standard temporal-difference (TD; Sutton, 1988) learning
($n=1$ or $\lambda=0$) and Monte Carlo learning ($n\to\infty$ or $\lambda=1$).

Implementation has generally been the main consideration in choosing which of
these return estimators to use. When the value function is a lookup table or a
linear parametric function, the $\lambda$-return is preferred for its
efficient implementation using TD($\lambda$) with eligibility traces (Sutton,
1988). However, in off-policy deep RL, the value function is a neural network
trained with an experience replay buffer (Lin, 1992), so the extra
bootstrapping performed by the $\lambda$-return becomes costly and $n$-step
returns are more common. Although recent work has explored ways to efficiently
train neural networks using replayed $\lambda$-returns (e.g., Munos et al.,
2016; Harb & Precup, 2016; Daley & Amato, 2019), $\lambda$-returns generally
remain more expensive or complex to implement than $n$-step returns.

Despite its more complicated implementation in deep RL, the $\lambda$-return
is interesting because it averages many $n$-step returns together. In this
paper, we show that this averaging reduces variance compared to $n$-step
returns and that the variance reduction leads to faster learning. More
generally, the $\lambda$-return is an example of a _compound_ return, or a
weighted average of two or more $n$-step returns (Sutton & Barto, 2018, Sec.
12.1). The $\lambda$-return is the most prevalent compound return, but others
such as the $\gamma$-return (Konidaris et al., 2011) and the $\Omega$-return
(Thomas et al., 2015) have also been shown to be effective. While compound
returns are known to be theoretically sound (Watkins, 1989, Sec. 7.2), they
have not been extensively analyzed. Compound returns are ideally suited for
deep RL because experiences are already stored in a replay memory, making it
easy to compute several $n$-step returns cheaply and then average them
together in any desired way.

In this paper, we formally investigate the variance of compound returns,
deriving the first variance model for arbitrary compound returns.
Additionally, we prove that all compound returns have a _variance-reduction
property_ : any compound return that achieves the same contraction modulus as
an $n$-step return has strictly lower variance if the TD errors are not
perfectly correlated. As a corollary, there exists a $\lambda$-return for
every $n$-step return with the same contraction modulus but lower variance,
implying a better bias-variance trade-off.

Our theoretical results suggest one should prefer $\lambda$-returns over
$n$-step returns, but these are expensive to implement for deep RL. Thus, we
also introduce an efficient approximation called Piecewise $\lambda$-Return
(Pilar). A Pilar is computed by averaging just two $n$-step returns
together—the most efficient compound return possible. The lengths of the
$n$-step returns are chosen to put weights on the TD errors that are close to
those assigned by TD($\lambda$), thereby achieving similar variance reduction
as the $\lambda$-return. We show that Pilars improve sample efficiency
compared to $n$-step returns when used to train Deep Q-Network (DQN; Mnih et
al., 2015), which is the foundation of many other value-based deep RL methods.

##  2 Background

Value-based RL agents interact with their environments to iteratively improve
estimates of their expected cumulative reward. By convention, the agent-
environment interaction is modeled as a Markov decision process (MDP)
described by the tuple $(\mathcal{S},\mathcal{A},p,r)$. At each time step $t$
of the process, the agent observes the environment state,
$S_{t}\in\mathcal{S}$, and selects an action, $A_{t}\in\mathcal{A}$,
accordingly. The environment then transitions to a new state,
$S_{t+1}\in\mathcal{S}$, with probability $p(S_{t+1}\mid S_{t},A_{t})$, and
returns a scalar reward, $\smash{R_{t}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}r(S_{t},A_{t},S_{t+1})}$. We assume the agent samples each action
with probability $\pi(A_{t}|S_{t})$, where $\pi$ is a stochastic policy.

In the standard prediction problem, the agent’s goal is to learn a value
function $v\colon\mathcal{S}\to\mathbb{R}$ that estimates the expected
discounted return $v_{\pi}(s)$ attainable in each state $s$. Letting
$\smash{G_{t}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{i=0}^{\infty}\gamma^{i}R_{t+i}}$ be the observed Monte Carlo
return at time $t$, where $\gamma\in[0,1]$ is a discount factor and actions
are implicitly sampled from $\pi$, then
$\smash{v_{\pi}(s)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\mathbb{E}\\!\left[G_{t}\mid S_{t}=s\right]}$.

The basic learning operation of value-based RL is a _backup_ , which has the
general form

$v(S_{t})\leftarrow v(S_{t})+\alpha_{t}\left(\hat{G}_{t}-v(S_{t})\right)\,,$
(1)

where $\smash{\hat{G}}_{t}$ is a return estimate (the _target_) and
$\alpha_{t}\in(0,1]$ is the step size. Substituting various estimators for
$\smash{\hat{G}}_{t}$ leads to different learning properties. For instance,
the Monte Carlo return could be used, but it suffers from high variance, and
delays learning until the end of an episode. To reduce the variance and delay,
return estimates can _bootstrap_ from the value function. Bootstrapping is the
fundamental mechanism underlying TD learning (Sutton, 1988), and the extent to
which the chosen estimator, $\hat{G}_{t}$, bootstraps is a major factor in
learning performance.

The most basic multistep version of TD learning uses the $n$-step return as
its target in Eq. 1:

$G^{n}_{t}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{i=0}^{n-1}\gamma^{i}R_{t+i}+\gamma^{n}v(S_{t+n})\,.$ (2)

Bootstrapping introduces bias in the update, since generally
$\mathbb{E}\left[v(S_{t+n})\mid S_{t}\right]\neq v_{\pi}(S_{t+n})$ before
convergence, but it greatly reduces variance. The case of $n=1$ corresponds to
the classic TD(0) algorithm, $v(S_{t})\leftarrow
v(S_{t})+\alpha_{t}\delta_{t}$, where
$\smash{\delta_{t}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}R_{t}+\gamma
v(S_{t+1})-v(S_{t})}$ is the TD error. However, bootstrapping after just one
time step is slow because long-term reward information must propagate
indirectly through the value function, requiring many behavioral repetitions
before $v$ approximates $v_{\pi}$ well. Larger values of $n$ consider more
rewards per update and assign credit faster, but at the price of increased
variance, with $n\to\infty$ reverting to the Monte Carlo return. The choice of
$n$ thus faces a bias-variance trade-off (Kearns & Singh, 2000), with
intermediate values typically performing best in practice (Sutton & Barto,
2018, Ch. 7).

Another type of multistep return is the $\lambda$-return, used by
TD($\lambda$) algorithms (Sutton, 1988), which is equivalent to an
exponentially weighted average of $n$-step returns:

$G^{\lambda}_{t}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G^{n}_{t}\,,$

where $\lambda\in[0,1]$. The $\lambda$-return is just one way to average
$n$-step returns together, but any weighted average is possible. Such averages
are known as _compound_ returns (Sutton & Barto, 2018, Ch. 12). Formally, a
compound return can be expressed as

$G^{{\bm{\mathsfit{w}}}}_{t}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{n=1}^{\infty}w_{n}G^{n}_{t}\,,$ (3)

where ${\bm{\mathsfit{w}}}$ is an infinite sequence of nonnegative weights
with the constraint $\sum_{n=1}^{\infty}w_{n}=1$. Eq. 3 is a strict
generalization of all of the aforementioned return estimators; however, it
technically constitutes a _compound_ return if and only if at least two of the
weights are nonzero—otherwise, it reduces to an $n$-step return. All choices
of weights that sum to $1$ are equally valid in the sense that using their
compound returns as the target in Eq. 1 will converge to $v_{\pi}$ under the
standard step-size criteria of Robbins & Monro (1951). However, in practice,
the choice of weights greatly affects the bias and variance of the estimator
and, as a consequence, the empirical rate of convergence to $v_{\pi}$.
Furthermore, different choices of weights will vary in the amount of
computation needed; sparse weights require less bootstrapping, and therefore
less computation when the value function is expensive. A principal
contribution of this paper is to shed light on the trade-offs between these
factors and to develop new compound returns that favorably balance all of
these considerations (see Section 4).

Many RL agents are control agents, meaning they do not just predict $v_{\pi}$
for a fixed policy, but also use these estimates to update the behavior policy
during training. One way to do this is Q-Learning (Watkins, 1989). Rather than
learning a state-value function $v$, the agent learns an action-value function
$q\colon\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ that estimates the expected
return $q_{*}(s,a)$ earned by following an optimal policy after taking action
$a$ in state $s$. The estimated value of a state is therefore
$v(s)=\max_{a\in\mathcal{A}}q(s,a)$, and all of the previously discussed
return estimators apply after making this substitution. Backups are conducted
as before, but now operate on $q(S_{t},A_{t})$ instead of $v(S_{t})$.

Learning is off-policy in this setting, since the agent now predicts returns
for a greedy policy that differs from the agent’s behavior. Any multistep
return is therefore biased unless the expectation is explicitly corrected,
e.g., by importance sampling (Kahn & Harris, 1951). However, it is common
practice to ignore this bias in deep RL, and recent research has even
suggested that doing so is more effective with both $n$-step returns
(Hernandez-Garcia & Sutton, 2019) and $\lambda$-returns (Daley & Amato, 2019;
Kozuno et al., 2021), the latter of which become Peng’s Q($\lambda$) (Peng &
Williams, 1996). We made similar observations in our early experiments; for
these reasons, we also forego off-policy corrections in our work.

##  3 Variance Analysis

Our main goal in this section is to derive conditions for when a compound
return reduces variance compared to a given $n$-step return. We call this the
_variance-reduction property_ of compound returns (see Theorem 3.5). An
important consequence of this property is that when these conditions are met
and both returns are chosen to have the same contraction modulus, the compound
return needs fewer samples than the $n$-step return to converge (see Theorem
3.6).

The outline of this section is as follows. We first derive variance models for
$n$-step returns and compound returns under generalized assumptions extending
prior work (Section 3.1) and then develop a way to pair different return
families by equating their worst-case bias (Section 3.2). This sets up our
principal theoretical result, the variance-reduction property of compound
returns (Section 3.3). We also conduct a finite-time analysis of TD learning
with compound returns to show that this variance reduction does improve
theoretical sample complexity (Section 3.4). Finally, we experimentally
demonstrate that $\lambda$-returns—which are an instance of compound
returns—outperform $n$-step returns in a prediction task as predicted by our
theory (Section 3.5).

###  3.1 Characterizing Compound Return Variance

We start by developing reasonable models for the variance of $n$-step returns
and compound returns, building on the work of Konidaris et al. (2011). We note
that our real quantity of interest in this section is the conditional variance
of the backup error $\smash{\hat{G}_{t}-v(S_{t})}$. The degree of this
quantity’s deviation from its expected value is what ultimately impacts the
performance of value-based RL methods in Eq. 1. Nevertheless, this turns out
to be the same as the conditional variance of the return
$\smash{\hat{G}_{t}}$, since $v(S_{t})$ contributes no randomness. Thus,
$\smash{\mathrm{Var}[\hat{G}_{t}-v(S_{t})\mid
S_{t}]}=\smash{\mathrm{Var}[\hat{G}_{t}\mid S_{t}]}$. This equivalence allows
us to interchange between the variances of a return and its error, depending
on which is more computationally convenient.

Modeling the variance of a compound return is challenging because it typically
requires making assumptions about how the variance of $n$-step returns
increase as a function of $n$, as well as how strongly correlated different
$n$-step returns are. If these assumptions are too strong, the derived
variances will fail to reflect reality and lead to poorly informed algorithmic
choices. For instance, consider the following example of a compound return,
which we call a _two-bootstrap return_ :

$(1-w)G^{n_{1}}_{t}+wG^{n_{2}}_{t},\text{where }w\in(0,1)\text{ and
}n_{1}<n_{2}\,.$ (4)

Let $\smash{\sigma_{n}^{2}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\mathrm{Var}[G^{n}_{t}\mid S_{t}]}$. The variance of the above
return is

$(1-w)^{2}\sigma_{1}^{2}+w^{2}\sigma_{2}^{2}+2w(1-w)\sigma_{1}\sigma_{2}\rho\,,$

where $\rho=\operatorname{Corr}[G^{n_{1}}_{t},G^{n_{2}}_{t}\mid S_{t}]$. To
evaluate this expression, it is tempting to assume either $\rho=0$ to remove
the covariance term, or $\rho=1$ because both returns are generated from the
same trajectory. However, neither assumption is fully correct. We can see this
more clearly by decomposing the returns into their constituent TD errors:

$\displaystyle G^{n_{1}}_{t}$
$\displaystyle=v(S_{t})+\sum_{i=0}^{n_{1}-1}\gamma^{i}\delta_{t+i}\,,$
$\displaystyle G^{n_{2}}_{t}$
$\displaystyle=v(S_{t})+\sum_{i=0}^{n_{1}-1}\gamma^{i}\delta_{t+i}+\sum_{i=n_{1}}^{n_{2}-1}\gamma^{i}\delta_{t+i}\,.$

Because the returns share the first $n_{1}$ TD errors, averaging them as in
Eq. 4 can only reduce the variance from the last $n_{2}-n_{1}$ TD errors. Two
different $n$-step returns are therefore neither uncorrelated nor perfectly
correlated; they consist of various random elements, some of which are shared
and cannot be averaged, and others which are not shared and can be averaged.
Models that fail to account for this partial averaging lead to poor variance
predictions.

To be accurate, our variance analysis should therefore start with the TD error
as the fundamental unit of randomness within a return. In the following
analysis, we generalize the $n$-step return variance assumptions made by
Konidaris et al. (2011, Sec. 3) to obtain an expression for the covariance
between two TD errors (see Appendix A). Letting $\mathbf{1}_{i=j}=1$ if $i=j$,
and $\mathbf{1}_{i=j}=0$ otherwise, we have

$\mathrm{Cov}[\delta_{t+i},\delta_{t+j}\mid
S_{t}]=((1-\rho)\mathbf{1}_{i=j}+\rho)\kappa\,,$ (5)

where $\kappa=\mathrm{Var}[\delta_{t}\mid S_{t}]$ and $\rho\in[0,1]$ is the
correlation coefficient. In the proposition below, we derive a variance model
for the $n$-step return by decomposing the return into a sum of discounted TD
errors and then adding up the pairwise covariances given by Eq. 5. For
brevity, we define a function
$\mathop{\Gamma_{\\!c}\\!\left(n\right)}\nolimits$ to represent the sum of the
first $n$ terms of a geometric series with common ratio $\gamma^{c}$, where
$c>0$:

$\mathop{\Gamma_{\\!c}\\!\left(n\right)}\nolimits\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\begin{cases}(1-\gamma^{cn})\mathbin{/}(1-\gamma^{c})\,,&\text{for
}0\leq\gamma<1\,,\\\ n\,,&\text{for }\gamma=1\,.\end{cases}$

######  Proposition 3.1.

The variance of an $n$-step return is

$\mathrm{Var}\left[G^{n}_{t}\mid
S_{t}\right]=(1-\rho)\mathop{\Gamma_{\\!2}\\!\left(n\right)}\nolimits\kappa+\rho\mathop{\Gamma_{\\!1}\\!\left(n\right)}\nolimits^{2}\kappa\,.$

###### Proof.

See Section C.1.1. ∎

Our $n$-step variance model linearly interpolates between an optimistic case
where TD errors are uncorrelated ($\rho=0$) and a pessimistic case where TD
errors are maximally correlated ($\rho=1$). In the maximum-variance scenario
of $\gamma=1$, we have
$\mathop{\Gamma_{\\!1}\\!\left(n\right)}\nolimits=\mathop{\Gamma_{\\!2}\\!\left(n\right)}\nolimits=n$,
so the model becomes $(1-\rho)n\kappa+\rho n^{2}\kappa$, i.e., it interpolates
between linear and quadratic functions. In Appendix B, we demonstrate that
these bounds are consistent with empirical data in real environments, even
when our assumptions do not fully hold.

Eq. 5 enables us to go beyond $n$-step returns and calculate variances for
arbitrary compound returns. We accomplish this by again decomposing the return
into a weighted sum of TD errors (see the next lemma) and then applying our
assumptions to derive a compound variance model in the following proposition.

######  Lemma 3.2.

A compound error can be written as a weighted summation of TD errors:

$G^{{\bm{\mathsfit{w}}}}_{t}-v(S_{t})=\sum_{i=0}^{\infty}\gamma^{i}W_{i}\delta_{t+i}\,,\enskip\text{where
}W_{i}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\smashoperator[]{\sum_{n=i+1}^{\infty}}w_{n}\,.$

######  Proposition 3.3.

The variance of a compound return is

$\\!\\!\mathrm{Var}\\!\left[G^{{\bm{\mathsfit{w}}}}_{t}\mid
S_{t}\right]\\!=(1\\!-\\!\rho)\\!\sum_{i=0}^{\infty}\gamma^{2i}W_{i}^{2}\kappa+\rho\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\gamma^{i+j}W_{i}W_{j}\kappa\,.$

###### Proofs.

See Sections C.1.2 and C.1.3. ∎

The cumulative weights $\\{W_{i}\\}_{i=0}^{\infty}$ fully specify the variance
of a compound return. For instance, the $\lambda$-return assigns a cumulative
weight of $W_{i}={\sum_{n=i+1}^{\infty}(1-\lambda)\lambda^{n-1}=\lambda^{i}}$
to the TD error $\delta_{t+i}$, which matches the TD($\lambda$) algorithm
(Sutton, 1988). Substituting this weight into Proposition 3.3 and solving the
geometric series yields the variance for the $\lambda$-return, which we show
in Appendix D.

###  3.2 Error-Reduction Property and Effective $n$-step

Proposition 3.3 provides a method for calculating variance, but we would still
like to show that compound returns reduce variance relative to $n$-step
returns. To do this, we first need a way to relate two returns in terms of
their expected performance. This is because low variance by itself is not
sufficient for fast learning; for example, the $1$-step return has very low
variance, but learns slowly.

In the discounted setting, a good candidate for expected learning speed is the
return’s contraction modulus. The contraction modulus is the constant factor
by which the maximum value-function error between $v$ and $v_{\pi}$ is
guaranteed to be reduced. When the contraction modulus is less than $1$, the
return estimator exhibits an _error-reduction property_ : i.e., the maximum
error decreases on average with every backup iteration of Eq. 1. This property
is commonly used in conjunction with the Banach fixed-point theorem to prove
that $v$ eventually converges to $v_{\pi}$ (see, e.g., Bertsekas & Tsitsiklis,
1996, Sec. 4.3). The error-reduction property of compound returns was first
identified by Watkins (1989, Sec. 7.2) and is expressed formally as

$\displaystyle\max_{s\in\mathcal{S}}\absolutevalue{\mathbb{E}\left[G^{{\bm{\mathsfit{w}}}}_{t}\mid
S_{t}=s\right]-v(s)}$
$\displaystyle\qquad\leq\left(\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}\gamma^{n^{\prime}}\right)\max_{s\in\mathcal{S}}\absolutevalue{v(s)-v_{\pi}(s)}\,.$
(6)

The contraction modulus is the coefficient on the right-hand side:
$\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}\gamma^{n^{\prime}}$ , a weighted
average of each individual $n$-step return’s contraction modulus,
$\gamma^{n}$. We can compare compound returns to $n$-step returns that have
equivalent error-reduction properties by solving the equation
${\gamma^{n}=\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}\gamma^{n^{\prime}}}$
for $n$. We call this the _effective $n$-step_ of the compound return, since
the compound return reduces the worst-case error as though it were an $n$-step
return whose length is the solution to the previous equation (see Proposition
3.4 below). In undiscounted settings, we cannot directly equate contraction
moduli like this because every contraction modulus becomes
${\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}=1}$, but we can still solve the
limit as $\gamma\to 1$ to define the effective $n$-step.

######  Proposition 3.4 (Effective $n$-step of compound return).

Let $G^{{\bm{\mathsfit{w}}}}_{t}$ be any compound return and let

$n=\begin{cases}\log_{\gamma}\left(\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}\gamma^{n^{\prime}}\right)\,,&\text{if
}0<\gamma<1\,,\\\
\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}n^{\prime}\,,&\text{if
}\gamma=1\,.\end{cases}$ (7)

When $n$ is an integer, $G^{{\bm{\mathsfit{w}}}}_{t}$ shares the same bound in
Eq. 6 as the $n$-step return $G^{n}_{t}$.

###### Proof.

See Section C.1.4. ∎

With or without discounting, an $n$-step return and a compound return that
satisfy Eq. 7 have the same error-reduction property. We refer to the quantity
$\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}n^{\prime}$ as the _center of mass_
(COM) of a return, since it is the first moment of the weight distribution
over $n$-step returns. Intuitively, this represents the average length into
the future considered by the return, and is the undiscounted analog of the
log-contraction modulus.

###  3.3 The Variance-Reduction Property of
Compound Returns

With the previous definition of effective $n$-step, we are now ready to
formalize the _variance-reduction property_ of compound returns.

######  Theorem 3.5 (Variance-reduction property of compound returns).

Consider a compound return $\smash{G^{{\bm{\mathsfit{w}}}}_{t}}$ and an
$n$-step return $\smash{G^{n}_{t}}$ with $n$ defined by Eq. 7. The inequality
$\smash{\mathrm{Var}[G^{{\bm{\mathsfit{w}}}}_{t}\mid
S_{t}]\leq\mathrm{Var}[G^{n}_{t}\mid S_{t}]}$ always holds, and is strict
whenever TD errors are not perfectly correlated.

###### Proof.

See Section C.1.5. ∎

Theorem 3.5 shows that whenever a compound return has the same contraction
modulus ($\gamma<1$) or COM ($\gamma=1$) as an $n$-step return, it has lower
variance as long as the TD errors are not perfectly correlated. Perfect
correlation between all TD errors would be unlikely to occur except in
contrived, maximum-variance MDPs; thus, compound returns reduce variance in
virtually all practical cases. Crucially, variance reduction is achieved for
any type of weighted average—although the magnitude of reduction does depend
on the specific choice of weights. The exact amount, in terms of $\kappa$, can
be calculated by subtracting the compound variance from the $n$-step variance
for a given contraction modulus or COM.

###  3.4 Finite-Time Analysis

It might not be obvious that reducing variance leads to faster learning;
indeed, in other settings such as direct policy optimization, this is not the
case (see Chung et al., 2021). We conduct a finite-time analysis of compound
TD learning to prove that lower variance does lead to faster learning in this
setting. We consider linear function approximation, where
$v_{\theta}(s)=\phi(s)^{\\!\top\\!}\theta$ for features
$\phi(s)\in\mathbb{R}^{d}$ and parameters $\theta\in\mathbb{R}^{d}$; note that
tabular methods can be recovered using one-hot features. The parameters are
iteratively updated according to

$\displaystyle\theta_{t+1}=\theta_{t}+\alpha
g^{\bm{\mathsfit{w}}}_{t}(\theta_{t})\,,$ (8) $\displaystyle\qquad\text{where
}g^{\bm{\mathsfit{w}}}_{t}(\theta)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\left(G^{{\bm{\mathsfit{w}}}}_{t}-\phi(S_{t})^{\\!\top\\!}\theta_{t}\right)\mathop{\phi(S_{t})}\,.$

Our theorem below generalizes recent analysis of $1$-step TD learning
(Bhandari et al., 2018, Theorem 2).

######  Theorem 3.6 (Finite-Time Analysis).

Suppose TD learning with linear function approximation is applied under an
i.i.d. state model with stationary distribution
$\smash{d\in\mathbb{R}^{|\mathcal{S}|}}$ (see Assumption C.1 in Section C.2)
using the compound return estimator $G^{{\bm{\mathsfit{w}}}}_{t}$ as its
target. Let $\beta\in[0,1)$ be the contraction modulus of the estimator and
let $\sigma^{2}\geq 0$ be the variance of the estimator. Assume that the
features are normalized such that $\smash{\norm{\phi(s)}_{2}^{2}\leq 1}$,
${\forall~{}s\in\mathcal{S}}$. Define
$\smash{C\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}(\norm{r}_{\infty}+(1+\gamma)\norm{\theta^{*}}_{\infty})\mathbin{/}(1-\gamma)}$,
where $\theta^{*}$ is the minimizer of the projected Bellman error for
$G^{{\bm{\mathsfit{w}}}}_{t}$. For any $T\geq(4\mathbin{/}(1-\beta))^{2}$ and
a constant step size $\alpha=1\mathbin{/}\sqrt{T}$,

$\displaystyle\mathbb{E}\\!\left[\norm{v_{\theta^{*}}-v_{\bar{\theta}_{T}}}_{D}^{2}\right]\leq\frac{\norm{\theta^{*}-\theta_{0}}_{2}^{2}+2(1-\beta)^{2}C^{2}+2\sigma^{2}}{(1-\beta)\sqrt{T}}\,,$
$\displaystyle\qquad\text{where }D\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\operatorname{diag}(d)\text{ and
}\bar{\theta}_{T}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\frac{1}{T}\sum_{t=0}^{T-1}\theta_{t}\,.$

###### Proof.

See Section C.2. ∎

With a constant step size, compound TD learning (and hence $n$-step TD
learning as a special case) reduces the value-function error at the same
asymptotic rate of $O(1/\sqrt{T})$ for any return estimator. However, both the
contraction modulus $\beta$ and the return variance $\sigma^{2}$ greatly
influence the magnitude of the constant that multiplies this rate. Given an
$n$-step return and a compound return with the same contraction modulus, the
compound return has lower variance by Theorem 3.5 and therefore converges
faster to its respective TD fixed point.

Figure 1:  Comparing $n$-step returns and $\lambda$-returns, paired by COM, in
a random walk. The dashed lines indicate the best error attained.

###  3.5 Case Study: $\lambda$-Returns

Although the $\lambda$-return is often motivated by its efficient
implementation using TD($\lambda$) and eligibility traces, our theory
indicates that $\lambda$-returns can also promote faster learning via variance
reduction. We provide empirical support for this by demonstrating faster
learning in the random walk experiment from Sutton & Barto (2018, Sec. 12.1).
In this environment, the agent begins in the center of a linear chain of 19
connected states and can move either left or right. The agent receives a
reward only if it reaches one of the far ends of the chain ($-1$ for the left,
$+1$ for the right), in which case the episode terminates. The agent’s policy
randomly moves in either direction with equal probability. We train the agents
for 10 episodes, updating the value functions after each episode with offline
backups like Eq. 1. To pair the $n$-step returns and $\lambda$-returns
together, we derive the effective $\lambda$ for an $n$-step return in the
following proposition.

######  Proposition 3.7 (Effective $\lambda$ of $n$-step return).

For any ${n\geq 1}$, when $\gamma<1$, the $\lambda$-return with
$\lambda=(1-\gamma^{n-1})\mathbin{/}(1-\gamma^{n})$ has the same contraction
modulus as the $n$-step return. When $\gamma=1$, the $\lambda$-return with
$\lambda=(n-1)\mathbin{/}n$ has the same COM as the $n$-step return.

###### Proof.

See Section C.1.6. ∎

Because this is an undiscounted task, we use the mapping
$n\mapsto{(n-1)\mathbin{/}n}$ to enumerate several $(n,\lambda)$-pairs with
equal COMs in Table 1. For our experiment, we choose four commonly used
$n$-step values, $\\{2,3,5,10\\}$, which correspond to
$\lambda\in\\{0.5,0.67,0.8,0.9\\}$. In Figure 1, we plot the average root-mean
square (RMS) value error (with respect to $v_{\pi}$) as a function of the step
size $\alpha$ over 100 trials. We also indicate 95% confidence intervals by
the shaded regions. For all of the tested $(n,\lambda)$-pairs, an interesting
trend emerges. In the left half of each plot, variance is not an issue because
the step size is small and has plenty of time to average out the randomness in
the estimates. Learning therefore progresses at a nearly identical rate for
both the $n$-step return and the $\lambda$-return since they have the same COM
(although there is a small discrepancy as $\lambda\to 1$ due to the truncation
of the episodic task, which reduces the $\lambda$-return’s COM). However, as
$\alpha\to 1$ in the right half of each plot, variance becomes a significant
factor as the step size becomes too large to mitigate the noise in the
updates. This causes the $n$-step return’s error to diverge sharply compared
to the $\lambda$-return’s as the $\lambda$-return manages variance more
effectively. The lowest error attained by each $\lambda$-return is also better
than that of its corresponding $n$-step return in all cases. Notably, neither
of our variance assumptions hold perfectly in this environment, demonstrating
that our variance model’s predictions are useful in practical settings.

Table 1: Common $n$-step returns and $\lambda$-returns with equal COMs. $n$ | 2 | 3 | 4 | 5 | 10 | 20 | 50 | 100
---|---|---|---|---|---|---|---|---
$\lambda$ | 0.5 | 0.67 | 0.75 | 0.8 | 0.9 | 0.95 | 0.98 | 0.99

##  4 Piecewise $\lambda$-Returns

Although the previous experiment shows that $\lambda$-returns can achieve
faster learning, they remain expensive for deep RL. This is because the
$\lambda$-return at time $t$ theoretically bootstraps on every time step after
$t$ (until the end of an episode), with each bootstrap requiring a forward
pass through the neural network. Even when truncating the $\lambda$-return to
a reasonable length, this is still several times more expensive than the
single bootstrap of an $n$-step return. Previous work has amortized the cost
of $\lambda$-returns over long trajectories by exploiting their recursive
structure (e.g., Munos et al., 2016; Harb & Precup, 2016; Daley & Amato,
2019), but the price to pay for this efficiency is the requirement that
experiences must be temporally adjacent. It can be seen from the ablation
experiment of Daley & Amato (2019, Fig. 2) that the resulting sample
correlations can hurt performance. Our preliminary experiments confirmed this,
indicating that the correlations within replayed trajectories counteract the
benefits of $\lambda$-returns when compared to minibatches of $n$-step returns
(with the batch size chosen to equalize computation).

We instead seek a compound return that approximates the variance-reduction
property of the $\lambda$-return while being computationally efficient for
random-minibatch replay. There are many ways we could average $n$-step returns
together, and so we constrain our search by considering compound returns that
1) comprise an average of only two $n$-step returns to minimize computational
cost, 2) preserve the contraction modulus or COM of the $\lambda$-return, and
3) place weights on the TD errors that are close to those assigned by the
$\lambda$-return, i.e., TD($\lambda$).

The first property constrains our estimator to have the two-bootstrap form of
Eq. 4: $\smash{(1-w)G^{n_{1}}_{t}+wG^{n_{2}}_{t}}$, where $w\in(0,1)$ and
${n_{1}<n_{2}}$. Let $n$ be our targeted effective $n$-step; the effective
$\lambda$ can be obtained from Proposition 3.7. Let us also assume $\gamma<1$,
although we include the case where $\gamma=1$ in Appendix E. To preserve the
contraction modulus as in the second property, we must satisfy
$(1-w)\gamma^{n_{1}}+w\gamma^{n_{2}}=\gamma^{n}$. Assuming that we have
freedom in the choice of $n_{1}$ and $n_{2}$, it follows that

$w=(\gamma^{n}-\gamma^{n_{1}})\mathbin{/}(\gamma^{n_{2}}-\gamma^{n_{1}})\,.$

Figure 2:  TD-error weights for a Pilar and a $\lambda$-return
(${\lambda=0.904}$). Both returns have the same contraction modulus as a
10-step return when $\gamma=0.99$.

We would thus like to find $n_{1}$ and $n_{2}$ such that the weights given to
the TD errors optimize some notion of closeness to the TD($\lambda$) weights,
in order to fulfill the third and final property. Although there are many ways
we could define the error, we propose to minimize the maximum absolute
difference between the weights, since this ensures that no individual weight
deviates too far from the TD($\lambda$) weight. Recall that the weight given
to TD error $\delta_{t+i}$ by $n$-step return $\smash{G^{n}_{t}}$ is
$\gamma^{i}$ if $i<n$, and is $0$ otherwise. It follows that the two-bootstrap
average assigns a weight of $\gamma^{i}$ if $i<n_{1}$; a weight of
$w\gamma^{i}$ if $n_{1}\leq i<n_{2}$, since $(1-w)\cdot
0+w\cdot\gamma^{i}=w\gamma^{i}$; and a weight of $0$ otherwise. In comparison,
TD($\lambda$) assigns a weight of $(\gamma\lambda)^{i}$. Our error function is
therefore

$\max_{i\geq 0}\absolutevalue{W_{i}-(\gamma\lambda)^{i}},\enskip\text{where
}W_{i}=\begin{cases}\gamma^{i}\,,&\text{if }i<n_{1}\,,\\\
w\gamma^{i}\,,&\text{else if }i<n_{2}\,,\\\ 0\,,&\text{else}.\end{cases}$ (9)

We call our approximation Piecewise $\bm{\lambda}$-Return (PiLaR, or Pilar)
because each weight $W_{i}$ is a piecewise function whose value depends on
where $i$ lies in relation to the interval $[n_{1},n_{2})$. Figure 2
illustrates how Pilar roughly approximates the TD($\lambda$) decay using a
step-like shape. Although a Pilar’s TD-error weights do not form a smooth
curve, they retain important properties like contraction modulus,
monotonicity, and variance reduction. Crucially, a Pilar is significantly
cheaper to compute than a $\lambda$-return, making it more suitable for
minibatch experience replay. In Appendix E, we describe a basic search
algorithm for finding the best $(n_{1},n_{2})$-pair according to Eq. 9, along
with a reference table of precomputed Pilars for $\gamma=0.99$.

Table 2: Pilar values used in our MinAtar experiments. $n$-step | $n_{1}$ | $n_{2}$ | $w$
---|---|---|---
3 | 1 | 6 | 0.406
5 | 2 | 9 | 0.437

##  5 Deep RL Experiments

We consider a multistep generalization of Deep Q-Networks (DQN) (Mnih et al.,
2015). The action-value function $q(s,a;\theta)$ is implemented as a neural
network to enable generalization over high-dimensional states, where
$\theta\in\mathbb{R}^{d}$ is the learnable parameters. A stale copy
$\theta^{-}$ of the parameters is used only for bootstrapping and is
infrequently updated from $\theta$ in order to stabilize learning. The agent
interacts with its environment and stores each transition
$(s,a,r,s^{\prime})$—where $s$ is the state, $a$ is the action, $r$ is the
reward, and $s^{\prime}$ is the next state—in a replay memory $\mathcal{D}$.
The network’s loss function is defined as

$\mathcal{L}(\theta,\theta^{-})\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\mathbb{E}\\!\left[\frac{1}{2}\left(\hat{G}(r,s^{\prime},\dots;\theta^{-})-q(s,a;\theta)\right)^{2}\right]\,,$

where $\hat{G}(r,s^{\prime},\dots;\theta^{-})$ is a multistep return estimator
for $q_{*}(s,a)$ and the expectation is taken over a uniform distribution on
$\mathcal{D}$. The network is trained by minimizing this loss using stochastic
gradient descent on random minibatches of experiences sampled from
$\mathcal{D}$.

Figure 3:  Learning curves for $n$-step returns and Pilars in five MinAtar
games.

We test our agents in all five MinAtar games (Young & Tian, 2019): Asterix,
Breakout, Freeway, Seaquest, and Space Invaders. The states are represented by
$10\times 10$ multi-channel images depicting object locations and velocity
trails. The agents’ network is a two-layer convolutional architecture with
rectified linear units (ReLUs). The agents execute an $\epsilon$-greedy policy
for 5M time steps (where $\epsilon$ is linearly annealed from $1$ to $0.1$
over the first 100k steps) and conduct a minibatch update of 32 samples on
every step. We provide more details in Appendix F.

For $n=3$ and $n=5$, we compare the $n$-step return against the corresponding
Pilar of the same contraction modulus with the given discount factor,
$\gamma=0.99$ (see Table 2 for specific values of $n_{1}$, $n_{2}$, and $w$).
We chose five Adam step sizes over a logarithmic grid search and generated
learning curves by plotting the 100-episode moving average of undiscounted
return (game score) versus time steps. We then chose the step size for each
game-estimator pair that maximized the area under the curve over the last 1M
steps, or 20% of training. We showcase the best results for each game in
Figure 3 but include all of the learning curves in Appendix F. Out of the five
games, Seaquest was the only one in which Pilar did not outperform $n$-step
returns in a statistically significant way. The results are averaged over 32
trials, with the shaded regions showing 95% confidence intervals.

In several cases, Pilars are able to significantly improve the agent’s best
performance compared to $n$-step returns. This is in spite of the fact that
each pair of $n$-step return and Pilar have the same contraction modulus,
suggesting that the performance increase is partially due to variance
reduction. Overall, Pilars significantly outperform $n$-step returns for 1 in
5 games (20%) when $n=3$, and 3 in 5 games (60%) when $n=5$. In the remaining
cases, the performance is not significantly different; thus, Pilars improve
the average performance of the agent’s best step size in these games. Because
the average performance gap between the estimators also widens as $n$
increases, the Pilars’ benefits appears to become more pronounced for
longer—and, hence, higher-variance—$n$-step returns.

These results help to corroborate our theory by showing that the variance
reduction from averaging $n$-step returns can accelerate learning, even with a
nontrivial network architecture. We do not claim that Pilars are necessarily
the best way to average $n$-step returns together to achieve variance
reduction, but our experiments still demonstrate the practical relevance of
the variance-reduction property of compound returns.

##  6 Conclusion

We have shown for the first time that compound returns, including
$\lambda$-returns, have a variance-reduction property. This is the first
evidence, to our knowledge, that $\lambda$-returns have a theoretical learning
advantage over $n$-step returns even in the absence of function approximation;
it was previously believed that both were different yet equivalent ways of
interpolating between TD and Monte Carlo learning. Our random walk experiments
confirm that an appropriately chosen $\lambda$-return performs as least as
well as—and often better than—a given $n$-step return across the entire range
of step sizes. In replay-based deep RL methods like DQN, where
$\lambda$-returns are difficult to implement efficiently, we demonstrated with
Pilar that a simpler average is still able to effectively reduce variance and
train neural networks with fewer samples. Since the average is formed from
only two $n$-step returns, the increase in computational cost is negligible
compared to $n$-step DQN—less expensive than adding a second target network,
as is often done in recent methods (e.g., Fujimoto et al., 2018; Haarnoja et
al., 2018).

A number of interesting extensions to our work are possible. For instance, we
derived Pilar under the assumption that the $\lambda$-return is a good
estimator to approximate. However, the exponential decay of the
$\lambda$-return originally arose from the need for an efficient online update
rule using eligibility traces, and is not necessarily optimal in terms of the
bias-variance trade-off. With experience replay, we are free to average
$n$-step returns in any way we want, even if the average would not be easily
implemented online. This opens up exciting possibilities for new families of
return estimators: e.g., those that minimize variance for a given contraction
modulus or COM. Based on our compound variance model (Proposition 3.3), a
promising direction in this regard appears to be weights that initially decay
faster than the exponential function, but then slower afterwards. Minimizing
variance becomes even more important for off-policy learning, where the
inclusion of importance-sampling ratios greatly exacerbates variance. Recent
works (Munos et al., 2016; Daley et al., 2023) have expressed arbitrary off-
policy corrections in terms of weighted sums of TD errors, and so our theory
could be extended to this setting with only minor modifications.

## References

  * Barto et al. (1983) Barto, A. G., Sutton, R. S., and Anderson, C. W.  Neuronlike adaptive elements that can solve difficult learning control problems.  _IEEE Transactions on Systems, Man, and Cybernetics_ , 13(5):834–846, 1983.
  * Bertsekas & Tsitsiklis (1996) Bertsekas, D. P. and Tsitsiklis, J. N.  _Neuro-Dynamic Programming_.  1996\.
  * Bhandari et al. (2018) Bhandari, J., Russo, D., and Singal, R.  A finite time analysis of temporal difference learning with linear function approximation.  In _Conference on Learning Theory (COLT)_ , 2018.
  * Chebotar et al. (2023) Chebotar, Y., Hausman, K., Xia, F., Lu, Y., Irpan, A., Kumar, A., Yu, T., Herzog, A., Pertsch, K., Gopalakrishnan, K., et al.  Q-Transformer: Scalable offline reinforcement learning via autoregressive Q-functions.  In _Conference on Robot Learning (CoRL)_ , 2023.
  * Chung et al. (2021) Chung, W., Thomas, V., Machado, M. C., and Le Roux, N.  Beyond variance reduction: Understanding the true impact of baselines on policy optimization.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Daley & Amato (2019) Daley, B. and Amato, C.  Reconciling $\lambda$-returns with experience replay.  In _Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Daley et al. (2023) Daley, B., White, M., Amato, C., and Machado, M. C.  Trajectory-aware eligibility traces for off-policy reinforcement learning.  In _International Conference on Machine Learning (ICML)_ , 2023.
  * Fujimoto et al. (2018) Fujimoto, S., Hoof, H., and Meger, D.  Addressing function approximation error in actor-critic methods.  In _International Conference on Machine Learning (ICML)_ , 2018.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International Conference on Machine Learning (ICML)_ , 2018.
  * Harb & Precup (2016) Harb, J. and Precup, D.  Investigating recurrence and eligibility traces in deep Q-networks.  In _NeurIPS Deep Reinforcement Learning Workshop_ , 2016.
  * Hernandez-Garcia & Sutton (2019) Hernandez-Garcia, J. F. and Sutton, R. S.  Understanding multi-step deep reinforcement learning: A systematic study of the DQN target.  In _Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Hessel et al. (2018) Hessel, M., Modayil, J., Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., and Silver, D.  Rainbow: Combining improvements in deep reinforcement learning.  In _AAAI Conference on Artificial Intelligence_ , 2018.
  * Kahn & Harris (1951) Kahn, H. and Harris, T. E.  Estimation of particle transmission by random sampling.  _National Bureau of Standards: Applied Mathematics Series_ , 12:27–30, 1951.
  * Kearns & Singh (2000) Kearns, M. J. and Singh, S.  Bias-variance error bounds for temporal difference updates.  In _Conference on Learning Theory (COLT)_ , 2000.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  In _International Conference on Representation Learning (ICLR)_ , 2015\.
  * Konidaris et al. (2011) Konidaris, G., Niekum, S., and Thomas, P. S.  $\text{TD}_{\gamma}$: Re-evaluating complex backups in temporal difference learning.  In _Neural Information Processing Systems (NeurIPS)_ , 2011.
  * Kozuno et al. (2021) Kozuno, T., Tang, Y., Rowland, M., Munos, R., Kapturowski, S., Dabney, W., Valko, M., and Abel, D.  Revisiting Peng’s Q($\lambda$) for modern reinforcement learning.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Lillicrap et al. (2016) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  In _International Conference on Learning Representations (ICLR)_ , 2016.
  * Lin (1992) Lin, L.-J.  Self-improving reactive agents based on reinforcement learning, planning and teaching.  _Machine Learning_ , 8:293–321, 1992.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _International Conference on Machine Learning (ICML)_ , 2016.
  * Munos et al. (2016) Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M.  Safe and efficient off-policy reinforcement learning.  In _Neural Information Processing Systems (NeurIPS)_ , 2016.
  * Peng & Williams (1996) Peng, J. and Williams, R. J.  Incremental multi-step Q-Learning.  _Machine Learning_ , 22:283–290, 1996.
  * Robbins & Monro (1951) Robbins, H. and Monro, S.  A stochastic approximation method.  _The Annals of Mathematical Statistics_ , pp. 400–407, 1951.
  * Rummery & Niranjan (1994) Rummery, G. A. and Niranjan, M.  On-line Q-Learning using connectionist systems.  Technical report, University of Cambridge, 1994.
  * Russell & Norvig (2009) Russell, S. J. and Norvig, P.  _Artificial Intelligence: A Modern Approach_.  2009\.
  * Schrittwieser et al. (2020) Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al.  Mastering Atari, Go, Chess and Shogi by planning with a learned model.  _Nature_ , 588(7839):604–609, 2020.
  * Schulman et al. (2015a) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _International Conference on Machine Learning (ICML)_ , 2015a.
  * Schulman et al. (2015b) Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P.  High-dimensional continuous control using generalized advantage estimation.  In _International Conference on Learning Representations (ICLR)_ , 2015b.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv_ , 1707.06347, 2017.
  * Schwarzer et al. (2023) Schwarzer, M., Ceron, J. S. O., Courville, A., Bellemare, M. G., Agarwal, R., and Castro, P. S.  Bigger, better, faster: Human-level Atari with human-level efficiency.  In _International Conference on Machine Learning (ICML)_ , 2023.
  * Silver et al. (2014) Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M.  Deterministic policy gradient algorithms.  In _International Conference on Machine Learning (ICML)_ , 2014.
  * Sutton (1984) Sutton, R. S.  _Temporal Credit Assignment in Reinforcement Learning_.  PhD thesis, University of Massachusetts Amherst, 1984.
  * Sutton (1988) Sutton, R. S.  Learning to predict by the methods of temporal differences.  _Machine Learning_ , 3:9–44, 1988.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement Learning: An Introduction_.  2018\.
  * Thomas et al. (2015) Thomas, P. S., Niekum, S., Theocharous, G., and Konidaris, G.  Policy evaluation using the $\Omega$-return.  _Neural Information Processing Systems (NeurIPS)_ , 2015.
  * Tsitsiklis & Van Roy (1996) Tsitsiklis, J. N. and Van Roy, B.  Analysis of temporal-diffference learning with function approximation.  In _Neural Information Processing Systems (NeurIPS)_ , 1996.
  * Watkins (1989) Watkins, C. J. C. H.  _Learning from Delayed Rewards_.  PhD thesis, University of Cambridge, 1989.
  * Williams (1992) Williams, R. J.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ , 8:229–256, 1992.
  * Wurman et al. (2022) Wurman, P. R., Barrett, S., Kawamoto, K., MacGlashan, J., Subramanian, K., Walsh, T. J., Capobianco, R., Devlic, A., Eckert, F., Fuchs, F., et al.  Outracing champion Gran Turismo drivers with deep reinforcement learning.  _Nature_ , 602(7896):223–228, 2022.
  * Young & Tian (2019) Young, K. and Tian, T.  MinAtar: An Atari-inspired testbed for thorough and reproducible reinforcement learning experiments.  _arXiv_ , 1903.03176, 2019.

##  Appendix A Variance Assumptions

Our variance assumptions are a significant relaxation and generalization of
the assumptions made by the $n$-step variance model of Konidaris et al. (2011,
Sec. 3). We show this by starting from their original assumptions and then
describing the steps taken to obtain our new assumptions.

Konidaris et al. (2011) begin by expanding the variance of an $n$-step return
in the following way:

$\displaystyle\mathrm{Var}[G^{n}_{t}\mid S_{t}]$
$\displaystyle=\mathrm{Var}[G^{n-1}_{t}+\gamma^{n-1}\delta_{t+n-1}\mid S_{t}]$
$\displaystyle=\mathrm{Var}[G^{n-1}_{t}\mid
S_{t}]+\gamma^{2(n-1)}\mathrm{Var}[\delta_{t+n-1}\mid
S_{t}]+2\;\mathrm{Cov}[G^{n-1}_{t},\gamma^{n-1}\delta_{t+n-1}\mid S_{t}]\,.$
(10)

The covariance term is equivalent to

$\displaystyle\mathrm{Cov}[G^{n-1}_{t},\gamma^{n-1}\delta_{t+n-1}\mid S_{t}]$
$\displaystyle=\mathrm{Cov}[G^{n-1}_{t},G^{n}_{t}-G^{n-1}_{t}\mid S_{t}]$
$\displaystyle=\mathrm{Cov}[G^{n-1}_{t},G^{n}_{t}\mid
S_{t}]-\mathrm{Cov}[G^{n-1}_{t},G^{n-1}_{t}\mid S_{t}]$
$\displaystyle=\mathrm{Cov}[G^{n-1}_{t},G^{n}_{t}\mid
S_{t}]-\mathrm{Var}[G^{n-1}_{t}\mid S_{t}]\,.$ (11)

With the rationale that $G^{n-1}_{t}$ and $G^{n}_{t}$ are generated from the
same trajectory and therefore highly correlated, the authors assume that

$\mathrm{Cov}[G^{n-1}_{t},G^{n}_{t}\mid
S_{t}]\approx\mathrm{Var}[G^{n-1}_{t}\mid S_{t}]\,,$ (12)

which makes Eq. 11 approximately zero. Consequently, Eq. 10 becomes

$\mathrm{Var}[G^{n}_{t}\mid
S_{t}]\approx\mathrm{Var}[G^{n-1}_{t}]+\gamma^{2(n-1)}\mathrm{Var}[\delta_{t+n-1}]\,.$
(13)

The authors additionally assume that the variance of each TD error is the
same:

######  Assumption A.1.

Each TD error has uniform variance: $\mathrm{Var}[\delta_{t+i}\mid
S_{t}]=\kappa$, $\forall~{}i\geq 0$.

Hence, Eq. 13 becomes $\mathrm{Var}[G^{n}_{t}\mid
S_{t}]\approx\mathrm{Var}[G^{n-1}_{t}]+\gamma^{2(n-1)}\kappa$ . Since
$\kappa=\mathrm{Var}[\delta_{t}\mid S_{t}]=\mathrm{Var}[G^{1}_{t}]$, unrolling
the recursion gives the final $n$-step variance model:

$\mathrm{Var}[G^{n}_{t}\mid S_{t}]\approx\sum_{i=0}^{n-1}\gamma^{2i}\kappa\,.$
(14)

This completes the derivation from Konidaris et al. (2011, Sec. 3), where the
two major assumptions are Eqs. 12 and A.1. Notice, however, that Eq. 14 could
be obtained more simply by assuming that TD errors are uncorrelated—in fact,
this is equivalent to assuming Eq. 12 holds. One way to see this is by
decomposing the $n$-step return into a sum of TD errors and applying standard
variance rules, assuming no correlations between the random variables:

$\mathrm{Var}[G^{n}_{t}\mid S_{t}]=\mathrm{Var}[G^{n}_{t}-v(S_{t})\mid
S_{t}]=\mathrm{Var}\\!\left[\sum_{i=0}^{n-1}\gamma^{i}\delta_{t+i}\Biggm{|}S_{t}\right]=\sum_{i=0}^{n-1}\gamma^{2i}\mathrm{Var}[\delta_{t+i}\mid
S_{t}]=\sum_{i=0}^{n-1}\gamma^{2i}\kappa\,,$

which is identical to Eq. 14. In our work, we directly make this uniform-
correlation assumption, while also generalizing it with an arbitrary
correlation coefficient $\rho\in[0,1]$. Note that we must have ${\rho\geq 0}$
because three or more TD errors cannot be negatively correlated
simultaneously.

######  Assumption A.2.

Distinct TD errors are uniformly correlated:
$\operatorname{Corr}[\delta_{t+i},\delta_{t+j}\mid S_{t}]=\rho$,
$\forall~{}i\geq 0$, $j\neq i$.

To summarize, our variance model makes Assumptions A.1 and A.2, which are
equivalent to the assumptions made by Konidaris et al. (2011) when $\rho=0$.
Since $\smash{\mathrm{Var}[\delta_{t+i}\mid
S_{t}]=\mathrm{Cov}[\delta_{t+i},\delta_{t+i}\mid S_{t}]}$, we are able to
combine Assumptions A.1 and A.2 into a single, concise expression—see Eq. 5 in
Section 3.

Although the assumptions here may not always hold in practice, they would be
difficult to improve without invoking information about the MDP’s transition
function or reward function. We show in Appendix B that our derived variances
based on these assumptions are nevertheless consistent with empirical data in
real environments.

##  Appendix B How Realistic Is the Proposed Variance Model?

Our assumptions state that all TD errors have uniform variance and are equally
correlated to one another. Since these assumptions may be violated in
practice, it is informative to test how well our $n$-step variance model
(Proposition 3.1) compares to the true $n$-step variances in several examples.

We consider three environments: the 19-state random walk (see Section 3), a
$4\times 3$ gridworld (Russell & Norvig, 2009, Fig. 17.1), and a $10\times 8$
gridworld (Sutton & Barto, 2018, Fig. 7.4). We choose these environments
because they have known dynamics and are small enough to exactly calculate
$v_{\pi}$ with dynamic programming. The two gridworlds are stochastic because
each of the four moves (up, down, left, right) succeeds with only probability
80%; otherwise, the move is rotated by 90 degrees in either direction with
probability 10% each. We let the agent execute a uniform-random behavior
policy for all environments.

To make the results agnostic to any particular learning algorithm, we use
$v_{\pi}$ to compute the TD errors. We apply a discount factor of
$\gamma=0.99$ to the $10\times 8$ gridworld (otherwise $v_{\pi}(s)$ would be
constant for all $s$ due to the single nonzero reward) and leave the other two
environments undiscounted. We then measure the variance of the $n$-step
returns originating from the initial state of each environment, for
$n\in\\{1,\dots,21\\}$. Figure 4 shows these variances plotted as a function
of $n$ and averaged over 10k episodes. The best-case (optimistic, $\rho=0$)
and worst-case (pessimistic, $\rho=1$) variances predicted by the $n$-step
model, assuming that $\kappa=\mathrm{Var}[\delta_{0}\mid S_{0}]$, are also
indicated by dashed lines.

For all of the environments, the measured $n$-step variances always remain
within the lower and upper bounds predicted by Proposition 3.1. These results
show that our $n$-step variance model can still make useful variance
predictions even when our assumptions do not hold. The variances also grow
roughly linearly as a function of $n$, corresponding more closely to the
linear behavior of the optimistic, uncorrelated case than the quadratic
behavior of the pessimistic, maximally correlated case. This further suggests
that the majority of TD-error pairs are weakly correlated in practice, which
makes sense because temporally distant pairs are unlikely to be strongly
related.

Figure 4:  Variances of the $n$-step returns originating from the initial
state in three environments. The solid green line indicates the true variance
while the dashed black lines indicate the lower and upper bounds predicted by
our $n$-step variance model (Proposition 3.1).

##  Appendix C Proofs

In this section, we include all proofs that were omitted from the main paper
due to space constraints.

###  C.1 Variance Modeling

This section contains proofs related to return-variance modeling and the
variance-reduction property.

####  C.1.1 Proposition 3.1

See 3.1

###### Proof.

The $n$-step error can be expressed as a finite summation of TD errors:

$G^{n}_{t}-v(S_{t})=\sum_{i=0}^{n-1}\gamma^{i}\delta_{t+i}\,.$ (15)

Using this, we calculate the covariance between two $n$-step returns with
lengths $n_{1}$, $n_{2}$:

$\displaystyle\mathrm{Cov}[G^{n_{1}}_{t},G^{n_{2}}_{t}\mid S_{t}]$
$\displaystyle=\mathrm{Cov}\Bigg{[}\sum_{i=0}^{n_{1}-1}\gamma^{i}\delta_{t+i},\sum_{j=0}^{n_{2}-1}\gamma^{j}\delta_{t+j}\Biggm{|}S_{t}\Bigg{]}$
$\displaystyle=\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}\mathrm{Cov}[\gamma^{i}\delta_{t+i},\gamma^{j}\delta_{t+j}\mid
S_{t}]$
$\displaystyle=\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}\gamma^{i+j}\mathrm{Cov}[\delta_{t+i},\delta_{t+j}\mid
S_{t}]$
$\displaystyle=\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}\gamma^{i+j}((1-\rho)\mathbf{1}_{i=j}+\rho)\kappa$
$\displaystyle=(1-\rho)\smashoperator[]{\sum_{i=0}^{\min(n_{1},n_{2})-1}}\gamma^{2i}\kappa+\rho\sum_{i=0}^{n_{1}-1}\sum_{j=0}^{n_{2}-1}\gamma^{i+j}\kappa$
$\displaystyle=(1-\rho)\smashoperator[]{\sum_{i=0}^{\min(n_{1},n_{2})-1}}\gamma^{2i}\kappa+\rho\sum_{i=0}^{n_{1}-1}\gamma^{i}\sum_{j=0}^{n_{2}-1}\gamma^{j}\kappa$
$\displaystyle=(1-\rho)\mathop{\Gamma_{\\!2}\\!\left(\min(n_{1},n_{2})\right)}\nolimits\kappa+\rho\mathop{\Gamma_{\\!1}\\!\left(n_{1}\right)}\nolimits\mathop{\Gamma_{\\!1}\\!\left(n_{2}\right)}\nolimits\kappa\,.$
(16)

Because $\mathrm{Var}[G^{n}_{t}\mid
S_{t}]=\mathrm{Cov}[G^{n}_{t},G^{n}_{t}\mid S_{t}]$, then by letting
$n_{1}=n_{2}=n$, we obtain the $n$-step variance formula and the proof is
complete. ∎

####  C.1.2 Lemma 3.2

See 3.2

###### Proof.

Let $W_{i}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{n=i+1}^{\infty}w_{n}$. We decompose the compound error into a
weighted average of $n$-step errors, and then decompose those $n$-step errors
into weighted sums of TD errors using Eq. 15:

$\displaystyle G^{{\bm{\mathsfit{w}}}}_{t}-v(S_{t})$
$\displaystyle=\left(\sum_{n=1}^{\infty}w_{n}G^{n}_{t}\right)-v(S_{t})$
$\displaystyle=\sum_{n=1}^{\infty}w_{n}\left(G^{n}_{t}-v(S_{t})\right)$
$\displaystyle=\sum_{n=1}^{\infty}w_{n}\sum_{i=0}^{n-1}\gamma^{i}\delta_{t+i}$
$\displaystyle=w_{1}\delta_{t}+w_{2}(\delta_{t}+\gamma\delta_{t+1})+w_{3}(\delta_{t}+\gamma\delta_{t+1}+\gamma^{2}\delta_{t+2})+\dots$
$\displaystyle=(w_{1}+w_{2}+\dots)\delta_{t}+\gamma(w_{2}+w_{3}+\dots)\delta_{t+1}+\gamma^{2}(w_{3}+w_{4}+\dots)\delta_{t+2}+\dots$
$\displaystyle=W_{0}\delta_{t}+\gamma
W_{1}\delta_{t+1}+\gamma^{2}W_{2}\delta_{t+2}+\dots$
$\displaystyle=\sum_{i=0}^{\infty}\gamma^{i}W_{i}\delta_{t+i}\,,$

which completes the lemma. ∎

####  C.1.3 Proposition 3.3

See 3.3

###### Proof.

From Lemma 3.2, the variance of the compound return is

$\displaystyle\mathrm{Var}\left[G^{{\bm{\mathsfit{w}}}}_{t}\right]$
$\displaystyle=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\mathrm{Cov}[\gamma^{i}W_{i}\delta_{t+i},\gamma^{j}W_{j}\delta_{t+j}\mid
S_{t}]$
$\displaystyle=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\gamma^{i+j}W_{i}W_{j}\mathrm{Cov}[\delta_{t+i},\delta_{t+j}\mid
S_{t}]$
$\displaystyle=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\gamma^{i+j}W_{i}W_{j}((1-\rho)\mathbf{1}_{i=j}+\rho)\kappa$
$\displaystyle=(1-\rho)\sum_{i=0}^{\infty}\gamma^{2i}W_{i}^{2}\kappa+\rho\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\gamma^{i+j}W_{i}W_{j}\kappa\,,$

which establishes Proposition 3.3. ∎

####  C.1.4 Proposition 3.4

See 3.4

###### Proof.

When $\gamma<1$, we can take the logarithm of both sides of
$\gamma^{n}=\sum_{n^{\prime}=1}^{\infty}w_{n}\gamma^{n^{\prime}}$ to get

$n=\log_{\gamma}\\!\left(\sum_{n^{\prime}=1}^{\infty}w_{n^{\prime}}\gamma^{n^{\prime}}\right)=\frac{\log\left(\sum_{n=1}^{\infty}w_{n}\gamma^{n}\right)}{\log\gamma}\,.$

For the undiscounted case, we would like to evaluate this expression at
$\gamma=1$; however, since $\sum_{n=1}^{\infty}w_{n}=1$ from the definition of
a compound return, we arrive at an indeterminate form, $\smash{\frac{0}{0}}$.
Instead, we can apply L’Hôpital’s rule to evaluate the limit as $\gamma\to 1$:

$\displaystyle\lim_{\gamma\to
1}\frac{\log\left(\sum_{n=1}^{\infty}w_{n}\gamma^{n}\right)}{\log\gamma}$
$\displaystyle=\lim_{\gamma\to
1}\frac{\frac{d}{d\gamma}\log\left(\sum_{n=1}^{\infty}w_{n}\gamma^{n}\right)}{\frac{d}{d\gamma}\log\gamma}$
$\displaystyle=\lim_{\gamma\to
1}\frac{(\sum_{n=1}^{\infty}w_{n}\gamma^{n-1}n)\mathbin{/}(\sum_{n=1}^{\infty}w_{n}\gamma^{n})}{1\mathbin{/}\gamma}$
$\displaystyle=\lim_{\gamma\to
1}\frac{\sum_{n=1}^{\infty}w_{n}\gamma^{n}n}{\sum_{n=1}^{\infty}w_{n}\gamma^{n}}$
$\displaystyle=\frac{\sum_{n=1}^{\infty}w_{n}n}{\sum_{n=1}^{\infty}w_{n}}$
$\displaystyle=\sum_{n=1}^{\infty}w_{n}n\,,$

where the last step follows again from the fact that
$\sum_{n=1}^{\infty}w_{n}=1$. This establishes the case where $\gamma=1$ and
completes the proof. ∎

####  C.1.5 Theorem 3.5

See 3.5

###### Proof.

Eq. 16 gives us an expression for the covariance between two $n$-step returns.
We use this to derive an alternative formula for the variance of a compound
return:

$\displaystyle\mathrm{Var}[G^{{\bm{\mathsfit{w}}}}_{t}\mid S_{t}]$
$\displaystyle=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}\mathrm{Cov}[w_{i}G^{i}_{t},w_{j}G^{j}_{t}\mid
S_{t}]$
$\displaystyle=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathrm{Cov}[G^{i}_{t},G^{j}_{t}\mid
S_{t}]$
$\displaystyle=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\big{(}(1-\rho)\mathop{\Gamma_{\\!2}\\!\left(\min(i,j)\right)}\nolimits)+\rho\mathop{\Gamma_{\\!1}\\!\left(i\right)}\nolimits\mathop{\Gamma_{\\!1}\\!\left(j\right)}\nolimits\\!\big{)}\kappa$
$\displaystyle=(1-\rho)\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathop{\Gamma_{\\!2}\\!\left(\min(i,j)\right)}\nolimits\kappa+\rho\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathop{\Gamma_{\\!1}\\!\left(i\right)}\nolimits\mathop{\Gamma_{\\!1}\\!\left(j\right)}\nolimits\kappa\,.$

We analyze both sums separately, starting with the first term. If we assume
$\gamma<1$ for now, then $\gamma^{n}=\sum_{i=1}^{\infty}w_{i}\gamma^{i}$ by
Proposition 3.4. Further note that $\min(i,j)\leq(i+j)\mathbin{/}2$, with the
inequality strict if $i\neq j$. Because $\Gamma_{\\!2}$ is monotonically
increasing, it follows that

$\displaystyle\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathop{\Gamma_{\\!2}\\!\left(\mathop{\min\\!\left(i,j\right)}\nolimits\right)}\nolimits$
$\displaystyle<\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathop{\Gamma_{\\!2}\\!\left(\frac{i+j}{2}\right)}\nolimits$
$\displaystyle=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\left(\frac{1-\gamma^{i+j}}{1-\gamma^{2}}\right)$
$\displaystyle=\frac{1-\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\gamma^{i+j}}{1-\gamma^{2}}$
$\displaystyle=\frac{1-\sum_{i=1}^{\infty}w_{i}\gamma^{i}\sum_{j=1}^{\infty}w_{j}\gamma^{j}}{1-\gamma^{2}}$
$\displaystyle=\frac{1-\gamma^{2n}}{1-\gamma^{2}}$
$\displaystyle=\mathop{\Gamma_{\\!2}\\!\left(n\right)}\nolimits\,.$

The inequality is strict because at least two weights in ${\bm{\mathsfit{w}}}$
are nonzero by definition of a compound return, guaranteeing at least one
element in the sum has $i\neq j$. If instead $\gamma=1$, then
${n=\sum_{i=1}^{\infty}w_{i}i}$ by Proposition 3.4 and also
$\mathop{\Gamma_{\\!2}\\!\left(\min(i,j)\right)}\nolimits=\min(i,j)$.
Therefore, by Jensen’s inequality, we have

$\displaystyle\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathop{\Gamma_{\\!2}\\!\left(\mathop{\min\\!\left(i,j\right)}\nolimits\right)}\nolimits$
$\displaystyle=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\min(i,j)$
$\displaystyle<\mathop{\min\\!\left(\sum_{i=1}^{\infty}w_{i}i,~{}\sum_{j=1}^{\infty}w_{j}j\right)}\nolimits$
$\displaystyle=\mathop{\min\\!\left(n,~{}n\right)}\nolimits$
$\displaystyle=\mathop{\Gamma_{\\!2}\\!\left(n\right)}\nolimits\,.$

Again, the inequality is strict by definition of a compound return, so we
conclude that

$\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathop{\Gamma_{\\!2}\\!\left(\mathop{\min\\!\left(i,j\right)}\nolimits\right)}\nolimits<\mathop{\Gamma_{\\!2}\\!\left(n\right)}\nolimits,\quad\text{for
}0<\gamma\leq 1\,.$

We now address the second term. We show that $\Gamma_{\\!1}$ is invariant
under a weighted average under our assumption that Eq. 7 holds. If $\gamma<1$,
then

$\sum_{i=1}^{\infty}w_{i}\mathop{\Gamma_{\\!1}\\!\left(i\right)}\nolimits=\sum_{i=1}^{\infty}w_{i}\left(\frac{1-\gamma^{i}}{1-\gamma}\right)=\frac{1-\sum_{i=1}^{\infty}w_{i}\gamma^{i}}{1-\gamma}=\frac{1-\gamma^{n}}{1-\gamma}=\mathop{\Gamma_{\\!1}\\!\left(n\right)}\nolimits\,.$
(17)

If $\gamma=1$, then

$\sum_{i=1}^{\infty}w_{i}\mathop{\Gamma_{\\!1}\\!\left(i\right)}\nolimits=\sum_{i=1}^{\infty}w_{i}i=n=\mathop{\Gamma_{\\!1}\\!\left(n\right)}\nolimits\,.$

Thus, regardless of $\gamma$, the second term becomes

$\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}w_{i}w_{j}\mathop{\Gamma_{\\!1}\\!\left(i\right)}\nolimits\mathop{\Gamma_{\\!1}\\!\left(j\right)}\nolimits=\sum_{i=1}^{\infty}w_{i}\mathop{\Gamma_{\\!1}\\!\left(i\right)}\nolimits\sum_{j=1}^{\infty}w_{j}\mathop{\Gamma_{\\!1}\\!\left(j\right)}\nolimits=\mathop{\Gamma_{\\!1}\\!\left(n\right)}\nolimits^{2}\,.$

Putting everything together, we have so far shown that

$\mathrm{Var}[G^{{\bm{\mathsfit{w}}}}_{t}\mid
S_{t}]\leq(1-\rho)\mathop{\Gamma_{\\!2}\\!\left(n\right)}\nolimits\kappa+\rho\mathop{\Gamma_{\\!1}\\!\left(n\right)}\nolimits^{2}\kappa\,,$

where the right-hand side is the $n$-step return variance given by Proposition
3.1. As we showed above, this inequality is strict whenever the first term is
active, i.e., $\rho<1$, which completes the proof. ∎

####  C.1.6 Proposition 3.7

See 3.7

###### Proof.

Case $\gamma<1$: We substitute $w_{n}=(1-\lambda)\lambda^{n-1}$ into the
weighted average in Eq. 6 to compute the contraction modulus of the
$\lambda$-return:

$\sum_{n=1}^{\infty}w_{n}\gamma^{n}=\sum_{n=1}^{\infty}(1-\lambda)\lambda^{n-1}\gamma^{n}=\gamma(1-\lambda)\sum_{n=1}^{\infty}(\gamma\lambda)^{n-1}=\frac{\gamma(1-\lambda)}{1-\gamma\lambda}\,.$

We therefore seek $\lambda$ such that

$\frac{\gamma(1-\lambda)}{1-\gamma\lambda}=\gamma^{n}$

in order to equate the $\lambda$-return’s contraction modulus to that of the
given $n$-step return. We multiply both sides of the equation by
$1-\gamma\lambda$ and isolate $\lambda$ to complete the case:

$\displaystyle\gamma(1-\lambda)$ $\displaystyle=\gamma^{n}(1-\gamma\lambda)$
$\displaystyle 1-\lambda$ $\displaystyle=\gamma^{n-1}(1-\gamma\lambda)$
$\displaystyle 1-\lambda$ $\displaystyle=\gamma^{n-1}-\gamma^{n}\lambda$
$\displaystyle\gamma^{n}\lambda-\lambda$ $\displaystyle=\gamma^{n-1}-1$
$\displaystyle\lambda(\gamma^{n}-1)$ $\displaystyle=\gamma^{n-1}-1$
$\displaystyle\lambda$
$\displaystyle=(1-\gamma^{n-1})\mathbin{/}(1-\gamma^{n})\,.$

Case $\gamma=1$: We use Proposition 3.4 with $w_{n}=(1-\lambda)\lambda^{n-1}$
to compute the effective $n$-step of the $\lambda$-return:

$n=\sum_{n^{\prime}=1}^{\infty}(1-\lambda)\lambda^{n^{\prime}-1}n^{\prime}=(1-\lambda)\sum_{n^{\prime}=1}^{\infty}\lambda^{n^{\prime}-1}n^{\prime}=(1-\lambda)\frac{1}{(1-\lambda)^{2}}=\frac{1}{1-\lambda}\,.$

Rearranging the equation $n=1\mathbin{/}(1-\lambda)$ for $\lambda$ gives the
final result of $\lambda=(n-1)\mathbin{/}n$. ∎

###  C.2 Finite-Time Analysis

In this section, we prove Theorem 3.6 to establish a finite-time bound on the
performance of multistep TD learning. We derive the bound in terms of the
return’s contraction modulus and variance, allowing us to invoke Theorem 3.5
and show an improved convergence rate.

At each iteration, TD learning updates the current parameters
$\theta_{t}\in\mathbb{R}^{d}$ according to Eq. 8. A value-function estimate
for any state $s$ is obtained by evaluating the dot product of the parameters
and the state’s corresponding feature vector:
$\smash{v_{\theta}(s)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\theta^{\\!\top\\!}\phi(s)}$. Following Bhandari et al. (2018), we
assume that $\smash{\norm{\phi(s)}_{2}^{2}}\leq 1$,
$\forall~{}s\in\mathcal{S}$. This can be guaranteed in practice by normalizing
the features and is therefore not a strong assumption.

In the prediction setting, the agent’s behavior policy is fixed such that the
MDP can be cast as a Markov reward process (MRP), where $r(s,s^{\prime})$
denotes the expected reward earned when transitioning from state $s$ to state
$s^{\prime}$. We adopt the i.i.d. state model from Bhandari et al. (2018, Sec.
3) and generalize it for multistep TD updates.

######  Assumption C.1 (i.i.d. state model).

Assume the MRP under the policy $\pi$ is ergodic. Let
$\smash{d\in\mathbb{R}^{|\mathcal{S}|}}$ represent the MRP’s unique stationary
distribution. Each iteration of Eq. 8 is calculated by first sampling a random
initial state $S_{t,0}\sim d$ and then sampling a trajectory of subsequent
states $S_{t,i+1}\sim\Pr(\cdot\mid S_{t,i})$, $\forall~{}i\in\mathbb{N}_{0}$.

That is, a state $S_{t,0}$ sampled from the steady-state MRP forms the root
node for the following trajectory $(S_{t,1},S_{t,2},\dots)$ that is generated
according to the MRP transition function. Notably, this setting closely models
the experience-replay setting utilized by many deep RL agents.

To facilitate our analysis, we decompose the compound TD updates into weighted
averages of $n$-step TD updates, where each $n$-step update has the form

$g^{n}_{t}(\theta)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\left(G^{n}_{t}-\mathop{\phi(S_{t})^{\\!\top\\!}}\theta\right)\mathop{\phi(S_{t})}\,.$

This allows us to conveniently express a compound TD update as

$g^{\bm{\mathsfit{w}}}_{t}(\theta)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{n=1}^{\infty}w_{n}g^{n}_{t}(\theta)\,.$

Our proofs also make use of the _expected_ $n$-step TD update:

$\bar{g}^{n}(\theta)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{s_{0}\in\mathcal{S}}\sum_{\tau\in\mathcal{S}^{n-1}}d(s_{0})\Pr(\tau\mid
s_{0})\left(G^{n}(s_{0},\tau,\theta)-\phi(s_{0})^{\\!\top\\!}\theta\right)\phi(s_{0})$

where $(s_{1},s_{2},\dots)=\tau$ and
$G^{n}(s_{0},\tau,\theta)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}r(s_{0},s_{1})+\dots+\gamma^{n-1}r(s_{n-1},s_{n})+\gamma^{n}\phi(s_{n})^{\\!\top\\!}\theta$
is the $n$-step return generated from $(s_{0},\tau)$.

For brevity, let $\smash{R_{i}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}r(S_{t,i},S_{t,i+1})}$ and
$\smash{\phi_{i}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\phi(S_{t,i})}$ be random variables sampled according to Assumption
C.1. We more conveniently write the expected $n$-step TD update as

$\bar{g}^{n}(\theta)=\mathbb{E}\\!\left[\phi_{0}(R_{0}+\gamma
R_{1}+\dots+\gamma^{n-1}R_{n-1})\right]+\mathbb{E}\\!\left[\phi_{0}(\gamma^{n}\phi_{n}-\phi_{0})^{\\!\top\\!}\right]\theta\,.$
(18)

The expected compound TD update easily follows as the weighted average

$\bar{g}^{\bm{\mathsfit{w}}}(\theta)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{n=1}^{\infty}w_{n}\bar{g}^{n}(\theta)\,.$

Finally, let $\theta^{*}$ be the fixed point of the compound TD update: i.e.,
$\bar{g}^{\bm{\mathsfit{w}}}(\theta^{*})=0$. This fixed point always exists
and is unique because the projected Bellman operator is a contraction mapping
(Tsitsiklis & Van Roy, 1996), and therefore so is any weighted average of the
$n$-iterated operators.

Before we prove Theorem 3.6, we must introduce two lemmas. The first
establishes a lower bound on the angle between the expected TD update and the
true direction toward the fixed point.

######  Lemma C.2.

Define the diagonal matrix $\smash{D\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\operatorname{diag}(d)}$. For any $\theta\in\mathbb{R}^{d}$,

$(\theta^{*}-\theta)^{\\!\top\\!}\bar{g}^{\bm{\mathsfit{w}}}(\theta)\geq(1-\beta)\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}\,.$
(19)

###### Proof.

Let $\xi_{i}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}v_{\theta^{*}}(S_{t,i})-v_{\theta}(S_{t,i})=(\theta^{*}-\theta)^{\\!\top\\!}\phi_{i}$
for $i\in\mathbb{N}_{0}$. By stationarity, each $\xi_{i}$ is a correlated
random variable with the same marginal distribution. Because $S_{t,0}$ is
drawn from the stationary distribution, we have
$\mathbb{E}\\!\left[\xi_{i}^{2}\right]=\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}$.

From Eq. 18, we show

$\displaystyle\bar{g}^{\bm{\mathsfit{w}}}(\theta)=\bar{g}^{\bm{\mathsfit{w}}}(\theta)-\bar{g}^{\bm{\mathsfit{w}}}(\theta^{*})$
$\displaystyle=\sum_{n=1}^{\infty}w_{n}\mathbb{E}\\!\left[\phi_{0}(\gamma^{n}\phi_{n}-\phi_{0})^{\\!\top\\!}(\theta-\theta^{*})\right]$
$\displaystyle=\sum_{n=1}^{\infty}w_{n}\mathbb{E}\\!\left[\phi_{0}(\xi_{0}-\gamma^{n}\xi_{n})\right]\,.$

It follows that

$\displaystyle(\theta^{*}-\theta)^{\\!\top\\!}\bar{g}^{\bm{\mathsfit{w}}}(\theta)$
$\displaystyle=\sum_{n=1}^{\infty}w_{n}\mathbb{E}\\!\left[\xi_{0}(\xi_{0}-\gamma^{n}\xi_{n})\right]$
$\displaystyle=\mathbb{E}\\!\left[\xi_{0}^{2}\right]-\sum_{n=1}^{\infty}w_{n}\gamma^{n}\mathbb{E}\\!\left[\xi_{0}\xi_{n}\right]$
$\displaystyle\geq\left(1-\sum_{n=1}^{\infty}w_{n}\gamma^{n}\right)\mathbb{E}\\!\left[\xi_{0}^{2}\right]$
$\displaystyle=(1-\beta)\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}\,.$

The inequality uses the Cauchy-Schwarz inequality along with the fact that
every $\xi_{i}$ has the same marginal distribution: thus,
$\mathbb{E}\\!\left[\xi_{0}\xi_{i}\right]\leq\sqrt{\mathbb{E}\\!\left[\xi_{0}^{2}\right]}\sqrt{\mathbb{E}\\!\left[\xi_{i}^{2}\right]}=\mathbb{E}\\!\left[\xi_{0}^{2}\right]$.
∎

The next lemma establishes a bound on the second moment of the squared norm of
the TD update in terms of the contraction modulus $\beta$ and the variance
$\sigma^{2}$ of the compound return.

######  Lemma C.3.

Define $\Delta^{*}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\norm{r}_{\infty}+(1+\gamma)\norm{\theta^{*}}_{\infty}$ and
$C\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\Delta^{*}\mathbin{/}(1-\gamma)$. For any
$\theta\in\mathbb{R}^{d}$,

$\mathbb{E}[\norm{g_{t}(\theta)}_{2}^{2}]\leq
2(1-\beta)^{2}C^{2}+2\sigma^{2}+4(1+\beta)\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}\,.$

###### Proof.

Let $\delta^{*}_{t,i}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}R_{i}+\gamma\phi_{i+1}^{\\!\top\\!}\theta^{*}-\phi_{i}^{\\!\top\\!}\theta^{*}$
and note that $\absolutevalue{\delta^{*}_{t,i}}\leq\Delta^{*}$ for all
$i\in\mathbb{N}_{0}$ by the triangle inequality and the bounded-feature
assumption. Denote the $n$-step and compound errors constructed from
$\theta^{*}$ by $\delta^{(n)}_{t}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{i=0}^{n-1}\gamma^{i}\delta^{*}_{t,i}$ and
$\delta^{\bm{\mathsfit{w}}}_{t}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sum_{n=1}^{\infty}w_{n}\delta^{(n)}_{t}$, respectively. We have

$\mathbb{E}\\!\left[\norm{g_{t}(\theta^{*})}_{2}^{2}\right]=\mathbb{E}\\!\left[\norm{\delta_{t}^{\bm{\mathsfit{w}}}\phi_{0}}_{2}^{2}\right]\leq\mathbb{E}\\!\left[(\delta_{t}^{\bm{\mathsfit{w}}})^{2}\right]=\mathbb{E}\\!\left[\delta^{\bm{\mathsfit{w}}}_{t}\right]^{2}+\sigma^{2}\,,$
(20)

where the inequality follows from the assumption that
$\norm{\phi_{0}}_{2}^{2}\leq 1$. The absolute value of the expectation can be
bounded using the triangle inequality:

$\displaystyle\absolutevalue{\mathbb{E}\\!\left[\delta^{\bm{\mathsfit{w}}}_{t}\right]}=\absolutevalue{\mathbb{E}\\!\left[\sum_{n=1}^{\infty}w_{n}\delta_{t}^{(n)}\right]}\leq\sum_{n=1}^{\infty}w_{n}\mathop{\Gamma_{\\!1}\\!\left(n\right)}\nolimits\Delta^{*}=\frac{1-\beta}{1-\gamma}\Delta^{*}=(1-\beta)C\,.$
(21)

The identity
$\sum_{n=1}^{\infty}w_{n}\Gamma_{1}(n)=(1-\beta)\mathbin{/}(1-\gamma)$ comes
from Eq. 17. Eqs. 20 and 21 imply

$\mathbb{E}\\!\left[\norm{g_{t}(\theta^{*})}_{2}^{2}\right]\leq(1-\beta)^{2}C^{2}+\sigma^{2}\,.$
(22)

Recall that
$\mathbb{E}\\!\left[\xi_{i}^{2}\right]=\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}$
for all $i\in\mathbb{N}_{0}$. Next, we show

$\displaystyle\mathbb{E}\\!\left[\norm{g_{t}(\theta)-g_{t}(\theta^{*})}_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\\!\left[\norm{\sum_{n=1}^{\infty}w_{n}\phi_{0}(\gamma^{n}\phi_{n}-\phi_{0})^{\\!\top\\!}(\theta-\theta^{*})}_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\\!\left[\norm{\sum_{n=1}^{\infty}w_{n}\phi_{0}(\xi_{0}-\gamma^{n}\xi_{n})}_{2}^{2}\right]$
$\displaystyle\leq\sum_{n=1}^{\infty}w_{n}\mathbb{E}\\!\left[\norm{\phi_{0}(\xi_{0}-\gamma^{n}\xi_{n})}_{2}^{2}\right]$
$\displaystyle\leq\sum_{n=1}^{\infty}w_{n}\mathbb{E}\\!\left[(\xi_{0}-\gamma^{n}\xi_{n})^{2}\right]$
$\displaystyle\leq
2\sum_{n=1}^{\infty}w_{n}\left(\mathbb{E}\\!\left[\xi_{0}^{2}\right]+\gamma^{2n}\mathbb{E}\\!\left[\xi_{n}^{2}\right]\right)$
$\displaystyle=2\sum_{n=1}^{\infty}w_{n}(1+\gamma^{2n})\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}$
$\displaystyle\leq
2\sum_{n=1}^{\infty}w_{n}(1+\gamma^{n})\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}$
$\displaystyle=2(1+\beta)\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}\,.$ (23)

The four inequalities respectively follow from Jensen’s inequality, the
bounded-feature assumption $\norm{\phi}_{2}^{2}\leq 1$, the triangle
inequality, and the fact that $\gamma^{2n}\leq\gamma^{n}$. The final equality
comes from the definition of the contraction modulus, the coefficient of the
left-hand side of Eq. 6. Combining Eqs. 22 and 23 gives the final result:

$\displaystyle\mathbb{E}\\!\left[\norm{g_{t}(\theta)}_{2}^{2}\right]$
$\displaystyle\leq\mathbb{E}\\!\left[\left(\norm{g_{t}(\theta^{*})}_{2}+\norm{g_{t}(\theta)-g_{t}(\theta^{*})}_{2}\right)^{2}\right]$
$\displaystyle\leq
2\mathbb{E}\\!\left[\norm{g_{t}(\theta^{*})}_{2}^{2}\right]+2\mathbb{E}\\!\left[\norm{g_{t}(\theta)-g_{t}(\theta^{*})}_{2}^{2}\right]$
$\displaystyle\leq
2(1-\beta)^{2}C^{2}+2\sigma^{2}+4(1+\beta)\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}\,,$

where the second inequality uses the algebraic identity $(x+y)^{2}\leq
2x^{2}+2y^{2}$. ∎

We are now ready to derive the finite-time bound. We restate Theorem 3.6 and
then provide the proof.

See 3.6

###### Proof.

TD learning updates the parameters according to Eq. 8. Therefore,

$\displaystyle\norm{\theta^{*}-\theta_{t+1}}_{2}^{2}$
$\displaystyle=\norm{\theta^{*}-\theta_{t}-\alpha\mathop{g_{t}(\theta_{t})}}_{2}^{2}$
$\displaystyle=\norm{\theta^{*}-\theta_{t}}_{2}^{2}-2\alpha\mathop{g_{t}(\theta_{t})^{\\!\top\\!}}(\theta^{*}-\theta_{t})+\alpha^{2}\norm{g_{t}(\theta)}_{2}^{2}\,.$

Taking the expectation and then applying Lemmas C.2 and C.3 gives

$\displaystyle\mathbb{E}\\!\left[\norm{\theta^{*}-\theta_{t+1}}_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\\!\left[\norm{\theta^{*}-\theta_{t}}_{2}^{2}\right]-2\alpha\mathbb{E}\\!\left[\mathop{g_{t}(\theta_{t})^{\\!\top\\!}}(\theta^{*}-\theta_{t})\right]+\alpha^{2}\mathbb{E}\\!\left[\norm{g_{t}(\theta)}_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\\!\left[\norm{\theta^{*}-\theta_{t}}_{2}^{2}\right]-2\alpha\mathbb{E}\\!\left[\mathbb{E}\\!\left[\mathop{g_{t}(\theta_{t})^{\\!\top\\!}}(\theta^{*}-\theta_{t})\right]\mid\theta_{t}\right]+\alpha^{2}\mathbb{E}\\!\left[\mathbb{E}\\!\left[\norm{g_{t}(\theta)}_{2}^{2}\right]\mid\theta_{t}\right]$
$\displaystyle\leq\mathbb{E}\\!\left[\norm{\theta^{*}-\theta_{t}}_{2}^{2}\right]-\left(2\alpha(1-\beta)-4\alpha^{2}(1+\beta)\right)\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}+2\alpha^{2}\left((1-\beta)^{2}C^{2}+\sigma^{2}\right)$
$\displaystyle\leq\mathbb{E}\\!\left[\norm{\theta^{*}-\theta_{t}}_{2}^{2}\right]-\alpha(1-\beta)\norm{v_{\theta^{*}}-v_{\theta}}_{D}^{2}+2\alpha^{2}\left((1-\beta)^{2}C^{2}+\sigma^{2}\right)\,.$

The first inequality is due to Lemmas C.2 and C.3, which are applicable due to
the i.i.d. setting (because the trajectory influencing $g_{t}$ is independent
of $\theta_{t}$). The second inequality follows from the assumption that
$\alpha\leq(1-\beta)\mathbin{/}4$. Rearranging the above inequality gives us

$\displaystyle\mathbb{E}\\!\left[\norm{v_{\theta^{*}}-v_{\theta_{t}}}_{D}^{2}\right]\leq\frac{\norm{\theta^{*}-\theta_{t}}_{2}^{2}-\norm{\theta^{*}-\theta_{t+1}}_{2}^{2}+2\alpha^{2}\left((1-\beta)^{2}C^{2}+\sigma^{2}\right)}{\alpha(1-\beta)}\,.$

Summing over $T$ iterations and then invoking the assumption that
$\alpha=1\mathbin{/}\sqrt{T}$:

$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}\\!\left[\norm{v_{\theta^{*}}-v_{\theta_{t}}}_{D}^{2}\right]$
$\displaystyle\leq\frac{\norm{\theta^{*}-\theta_{0}}_{2}^{2}-\norm{\theta^{*}-\theta_{T}}_{2}^{2}+2\alpha^{2}\left((1-\beta)^{2}C^{2}+\sigma^{2}\right)T}{\alpha(1-\beta)}$
$\displaystyle\leq\frac{\norm{\theta^{*}-\theta_{0}}_{2}^{2}+2\alpha^{2}\left((1-\beta)^{2}C^{2}+\sigma^{2}\right)T}{\alpha(1-\beta)}$
$\displaystyle=\frac{\norm{\theta^{*}-\theta_{0}}_{2}^{2}\sqrt{T}+2\left((1-\beta)^{2}C^{2}+\sigma^{2}\right)\sqrt{T}}{1-\beta}\,.$

We therefore conclude that

$\mathbb{E}\\!\left[\norm{v_{\theta^{*}}-v_{\bar{\theta}_{T}}}_{D}^{2}\right]\leq\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\\!\left[\norm{v_{\theta^{*}}-v_{\theta_{t}}}_{D}^{2}\right]\leq\frac{\norm{\theta^{*}-\theta_{0}}_{2}^{2}+2(1-\beta)^{2}C^{2}+2\sigma^{2}}{(1-\beta)\sqrt{T}}\,,$

which completes the bound. ∎

##  Appendix D $\lambda$-Return Variance

We calculate the variance of the $\lambda$-return under our assumptions. In
the main text, we showed that the $\lambda$-return assigns a cumulative weight
of $W_{i}=\lambda^{i}$ to the TD error at time $t+i$, which is also known from
the TD($\lambda$) algorithm. We can therefore apply Proposition 3.3 to obtain
the following variance expression:

$\displaystyle\mathrm{Var}[G^{\lambda}_{t}\mid S_{t}]$
$\displaystyle=(1-\rho)\sum_{i=0}^{\infty}(\gamma\lambda)^{2i}\kappa+\rho\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}(\gamma\lambda)^{i+j}\kappa$
$\displaystyle=(1-\rho)\sum_{i=0}^{\infty}(\gamma\lambda)^{2i}\kappa+\rho\sum_{i=0}^{\infty}(\gamma\lambda)^{i}\sum_{j=0}^{\infty}(\gamma\lambda)^{j}\kappa$
$\displaystyle=\frac{(1-\rho)\kappa}{1-(\gamma\lambda)^{2}}+\frac{\rho\kappa}{(1-\gamma\lambda)^{2}}\,.$
(24)

##  Appendix E Pilar: Piecewise $\lambda$-Return

Table 3: $n$-step returns and Pilars with equal contraction moduli when $\gamma=0.99$. effective |  |  |
---|---|---|---
$n$-step | $n_{1}$ | $n_{2}$ | $w$
2 | 1 | 4 | 0.337
3 | 1 | 6 | 0.406
4 | 2 | 7 | 0.406
5 | 2 | 9 | 0.437
10 | 4 | 16 | 0.515
20 | 6 | 35 | 0.519
25 | 8 | 43 | 0.530
50 | 13 | 79 | 0.640
100 | 22 | 147 | 0.760

We present a basic search algorithm for finding the corresponding Pilar for a
given $n$-step return (see Algorithm 1). The algorithm accepts the desired
effective $n$-step (which does not need to be an integer necessarily) as its
only argument and returns the values $(n_{1},n_{2},w)$ such that the two-
bootstrap return ${(1-w)G^{n_{1}}_{t}}+{wG^{n_{2}}_{t}}$ minimizes the maximum
absolute difference between its cumulative weights and those of the
$\lambda$-return with the same effective $n$-step. The algorithm proceeds as
follows. For each $n_{1}\in\\{1,\dots,\lfloor n\rfloor\\}$, scan through
$n_{2}\in\\{n_{1}+1,n_{1}+2,\dots,\\}$ until the error stops decreasing. Every
time a better $(n_{1},n_{2})$-pair is found, record the values, and return the
last recorded values upon termination. The resulting Pilar has the same
contraction modulus as the targeted $n$-step return; thus, their error-
reduction properties are the same, but the Pilar’s variance is lower by
Theorem 3.5. To modify the search algorithm for undiscounted rewards, we just
need to change $\lambda$ and $w$ such that they equate the COMs—rather than
the contraction moduli—of the two returns. We also include this case in
Algorithm 1.

We populate Table 3 with corresponding Pilar values for several common
$n$-step returns when $\gamma=0.99$. A discount factor of $\gamma=0.99$ is
extremely common in deep RL, and so it is hoped that this table serves as a
convenient reference that helps practitioners avoid redundant searches with
Algorithm 1.

Algorithm 1 Pilar($n$)

require$n\geq 1$,
$\gamma\in(0,1)$$\lambda=\begin{cases}(1-\gamma^{n-1})\mathbin{/}(1-\gamma^{n})\text{
if }\gamma<1\\\ (n-1)\mathbin{/}n\text{ if
}\gamma=1\end{cases}$$\text{best\\_error}\leftarrow\infty$$n_{1}=1,\dots,\lfloor
n\rfloor$$n_{2}\leftarrow\lfloor
n\rfloor$$\text{error}\leftarrow\infty$$n_{2}\leftarrow
n_{2}+1$$w=\begin{cases}(\gamma^{n}-\gamma^{n_{1}})\mathbin{/}(\gamma^{n_{2}}-\gamma^{n_{1}})\text{
if }\gamma<1\\\ (n-n_{1})\mathbin{/}(n_{2}-n_{1})\text{ if
}\gamma=1\end{cases}$$\text{prev\\_error}\leftarrow\text{error}$$\text{error}\leftarrow\Call{error}{\lambda,n_{1},n_{2},w}$$\text{error}<\text{best\\_error}$$\text{values}\leftarrow(n_{1},n_{2},w)$$\text{best\\_error}\leftarrow\text{error}$$\text{error}\geq\text{prev\\_error}$valueserror$\lambda,n_{1},n_{2},w$Let
$W_{i}=\begin{cases}\gamma^{i}&\text{if }i<n_{1}\\\ w\gamma^{i}&\text{else if
}i<n_{2}\\\ 0&\text{else}\\\ \end{cases}$$\max_{i\geq
0}\absolutevalue{W_{i}-(\gamma\lambda)^{i}}$

##  Appendix F Experiment Setup and Additional Results

Our experiment procedure closely matches that of Young & Tian (2019) for DQN.
The only differences in our methodology are the mean-squared loss (rather than
Huber loss), the Adam optimizer (Kingma & Ba, 2015), and multistep returns.
MinAtar represents states as $10\times 10\times 7$ binary images. The agents
process these with a convolutional network; the first layer is a 16-filter
$3\times 3$ convolutional layer, the output of which is flattened and then
followed by a dense layer with 128 units. Both layers use ReLU activations.

The agents were trained for 5 million time steps each. They executed a random
policy for the first 5k time steps to prepopulate the replay buffer (capacity:
100k transitions), and then switched to an $\epsilon$-greedy policy for the
remainder of training, with $\epsilon$ annealed linearly from $1$ to $0.1$
over the next 100k steps. Every step, the main network was updated using a
minibatch of 32 return estimates to minimize the loss in Section 5. The target
network’s parameters were copied from the main network every 1k time steps.

To obtain the $n$-step returns, the replay buffer is modified to return a
minibatch of sequences of $n+1$ experiences for each return estimate (instead
of the usual two experiences for DQN). The return is computed by summing the
first $n$ rewards and then adding the value-function bootstrap from the final
experience, with discounting if $\gamma<1$. If the episode terminates at any
point within this trajectory, then the return is truncated and no
bootstrapping is necessary, since the value of a terminal state is defined to
be zero. For Pilars, the idea is the same, but the trajectories must have
length $n_{2}+1$ to accommodate the lengths of both $n$-step returns. The two
returns are computed as above, and then combined by averaging them:
$(1-w)G^{n_{1}}+wG^{n_{2}}$.

We show the learning curves for each return estimator using its best step size
in Figure 5, where the step size was chosen from $\\{10^{-5},3\times
10^{-5},10^{-4},3\times 10^{-4},10^{-3}\\}$. We observe that Pilars perform no
worse than $n$-step returns in the MinAtar domain, and sometimes significantly
better. The relative improvement between Pilars and $n$-step returns tends to
widen for $n=5$, suggesting that Pilars are better tolerating the higher
variance in this setting.

Figure 5:  Learning curves for $n$-step returns and Pilars in five MinAtar
games.