Safe and Efficient Off-Policy Reinforcement Learning

Notation

The value function for a policy $\pi$, $Q^{\pi}$, describes the expected discounted sum of rewards associated with following $\pi$ from a given state-action pair. Using operator notation, we write this as

The Bellman operator $\mathcal{T}^{\pi}$ for a policy $\pi$ is defined as $\mathcal{T}^{\pi}Q:=r+\gamma P^{\pi}Q$ and its fixed point is $Q^{\pi}$, i.e. $\mathcal{T}^{\pi}Q^{\pi}=Q^{\pi}=(I-\gamma P^{\pi})^{-1}r$. The Bellman optimality operator introduces a maximization over the set of policies:

Its fixed point is $Q^{*}$, the unique optimal value function (Puterman,, 1994). It is this quantity that we will seek to obtain when we talk about the “control setting”.

The $\lambda$-return extension (Sutton,, 1988) of the Bellman operators considers exponentially weighted sums of $n$-steps returns:

where $\mathcal{T}^{\pi}Q-Q$ is the Bellman residual of $Q$ for policy $\pi$. Examination of the above shows that $Q^{\pi}$ is also the fixed point of $\mathcal{T}_{\lambda}^{\pi}$. At one extreme ($\lambda=0$) we have the Bellman operator $\mathcal{T}_{\lambda=0}^{\pi}Q=\mathcal{T}^{\pi}Q$, while at the other ($\lambda=1$) we have the policy evaluation operator $\mathcal{T}_{\lambda=1}^{\pi}Q=Q^{\pi}$ which can be estimated using Monte Carlo methods (Sutton and Barto,, 1998). Intermediate values of $\lambda$ trade off estimation bias with sample variance (Kearns and Singh,, 2000).

We seek to evaluate a target policy $\pi$ using trajectories drawn from a behaviour policy $\mu$. If $\pi=\mu$, we are on-policy; otherwise, we are off-policy. We will consider trajectories of the form:

Off-Policy Algorithms

We are interested in two related off-policy learning problems. In the policy evaluation setting, we are given a fixed policy $\pi$ whose value $Q^{\pi}$ we wish to estimate from sample trajectories drawn from a behaviour policy $\mu$. In the control setting, we consider a sequence of policies that depend on our own sequence of Q-functions (such as $\varepsilon$-greedy policies), and seek to approximate $Q^{*}$.

The general operator that we consider for comparing several return-based off-policy algorithms is:

Importance sampling is the simplest way to correct for the discrepancy between $\mu$ and $\pi$ when learning from off-policy returns (Precup et al.,, 2000, 2001; Geist and Scherrer,, 2014). The off-policy correction uses the product of the likelihood ratios between $\pi$ and $\mu$. Notice that $\mathcal{R}Q$ defined in (3) with this choice of $(c_{s})$ yields $Q^{\pi}$ for any $Q$. For $Q=0$ we recover the basic IS estimate \sum_{t\geq 0}\gamma^{t}\big{(}\prod_{s=1}^{t}c_{s}\big{)}r_{t}, thus (3) can be seen as a variance reduction technique (with a baseline $Q$). It is well known that IS estimates can suffer from large – even possibly infinite – variance (mainly due to the variance of the product $\frac{\pi(a_{1}|x_{1})}{\mu(a_{1}|x_{1})}\cdots\frac{\pi(a_{t}|x_{t})}{\mu(a_{t}|x_{t})}$), which has motivated further variance reduction techniques such as in (Mahmood and Sutton,, 2015; Mahmood et al.,, 2015; Hallak et al.,, 2015).

A recent alternative proposed by Harutyunyan et al., (2016) introduces an off-policy correction based on a $Q$-baseline (instead of correcting the probability of the sample path like in IS). This approach, called Qπ($\lambda$) and Q∗($\lambda$) for policy evaluation and control, respectively, corresponds to the choice $c_{s}=\lambda$. It offers the advantage of avoiding the blow-up of the variance of the product of ratios encountered with IS. Interestingly, this operator contracts around $Q^{\pi}$ provided that $\mu$ and $\pi$ are sufficiently close to each other. Defining $\varepsilon:=\max_{x}\|\pi(\cdot|x)-\mu(\cdot|x)\|_{1}$ the level of “off-policyness”, the authors prove that the operator defined by (3) with $c_{s}=\lambda$ is a contraction mapping around $Q^{\pi}$ for $\lambda<\frac{1-\gamma}{\gamma\varepsilon}$, and around $Q^{*}$ for the worst case of $\lambda<\frac{1-\gamma}{2\gamma}$. Unfortunately, Qπ($\lambda$) requires knowledge of $\varepsilon$, and the condition for Q∗($\lambda$) is very conservative. Neither Qπ($\lambda$), nor Q∗($\lambda$) are safe as they do not guarantee convergence for arbitrary $\pi$ and $\mu$.

The TB($\lambda$) algorithm of Precup et al., (2000) corrects for the target/behaviour discrepancy by multiplying each term of the sum by the product of target policy probabilities. The corresponding operator defines a contraction mapping for any policies $\pi$ and $\mu$, which makes it a safe algorithm. However, this algorithm is not efficient in the near on-policy case (where $\mu$ and $\pi$ are similar) as it unnecessarily cuts the traces, preventing it to make use of full returns: indeed we need not discount stochastic on-policy transitions (as shown by Harutyunyan et al.,’s results about Qπ).

Our contribution is an algorithm – Retrace$(\lambda)$ – that takes the best of the three previous algorithms. Retrace$(\lambda)$ uses an importance sampling ratio truncated at $1$. Compared to IS, it does not suffer from the variance explosion of the product of IS ratios. Now, similarly to $Q^{\pi}(\lambda)$ and unlike TB($\lambda$), it does not cut the traces in the on-policy case, making it possible to benefit from the full returns. In the off-policy case, the traces are safely cut, similarly to TB($\lambda$). In particular, \min\big{(}1,\frac{\pi(a_{s}|x_{s})}{\mu(a_{s}|x_{s})}\big{)}\geq\pi(a_{s}|x_{s}): Retrace($\lambda$) does not cut the traces as much as TB($\lambda$). In the subsequent sections, we will show the following:

For any traces $0\leq c_{s}\leq\pi(a_{s}|x_{s})/\mu(a_{s}|x_{s})$ (thus including the Retrace($\lambda$) operator), the return-based operator (3) is a $\gamma$-contraction around $Q^{\pi}$, for arbitrary policies $\mu$ and $\pi$

In the control case (where $\pi$ is replaced by a sequence of increasingly greedy policies) the online Retrace($\lambda$) algorithm converges a.s. to $Q^{*}$, without requiring the GLIE assumption.

As a corollary, Watkins’s Q$(\lambda)$ converges a.s. to $Q^{*}$.

Analysis of Retrace(λ𝜆\lambda)

We will in turn analyze both off-policy policy evaluation and control settings. We will show that $\mathcal{R}$ is a contraction mapping in both settings (under a mild additional assumption for the control case).

Our first result states the $\gamma$-contraction of the operator (3) defined by any set of non-negative coefficients $c_{s}=c_{s}(a_{s},\mathcal{F}_{s})$ (in order to emphasize that $c_{s}$ can be a function of the whole history $\mathcal{F}_{s}$) under the assumption that $0\leq c_{s}\leq\frac{\pi(a_{s}|x_{s})}{\mu(a_{s}|x_{s})}$.

The operator $\mathcal{R}$ defined by (3) has a unique fixed point $Q^{\pi}$. Furthermore, if for each $a_{s}\in\mathcal{A}$ and each history $\mathcal{F}_{s}$ we have c_{s}=c_{s}(a_{s},\mathcal{F}_{s})\in\big{[}0,\frac{\pi(a_{s}|x_{s})}{\mu(a_{s}|x_{s})}\big{]}, then for any Q-function $Q$

The following lemma will be useful in proving Theorem 1 (proof in the appendix).

The difference between $\mathcal{R}Q$ and its fixed point $Q^{\pi}$ is

Now since $\pi(a|x_{t})-\mu(a|x_{t})c_{t}(b,\mathcal{F}_{t})\geq 0$, we have that $\mathcal{R}Q(x,a)-Q^{\pi}(x,a)=\sum_{y,b}w_{y,b}\Delta Q(y,b)$, i.e. a linear combination of $\Delta Q(y,b)$ weighted by non-negative coefficients:

Thus $\eta(x,a)\in[0,\gamma]$ is a $(x,a)$-specific contraction coefficient, which is $\gamma$ when $c_{1}=0$ (the trace is cut immediately) and can be close to zero when learning from full returns ($c_{t}\approx 1$ for all $t$).

2 Control

In the control setting, the single target policy $\pi$ is replaced by a sequence of policies $(\pi_{k})$ which depend on $(Q_{k})$. While most prior work has focused on strictly greedy policies, here we consider the larger class of increasingly greedy sequences. We now make this notion precise.

Intuitively, this means that each $\pi_{k+1}$ is at least as greedy as the previous policy $\pi_{k}$ for $Q_{k+1}$. Many natural sequences of policies are increasingly greedy, including $\varepsilon_{k}$-greedy policies (with non-increasing $\varepsilon_{k}$) and softmax policies (with non-increasing temperature). See proofs in the appendix.

We will assume that $c_{s}=c_{s}(a_{s},\mathcal{F}_{s})=c(a_{s},x_{s})$ is Markovian, in the sense that it depends on $x_{s},a_{s}$ (as well as the policies $\pi$ and $\mu$) only but not on the full past history. This allows us to define the (sub)-probability transition operator

Finally, an additional requirement to the convergence in the control case, we assume that $Q_{0}$ satisfies $\mathcal{T}^{\pi_{0}}Q_{0}\geq Q_{0}$ (this can be achieved by a pessimistic initialization $Q_{0}=-R_{MAX}/(1-\gamma)$).

Consider an arbitrary sequence of behaviour policies $(\mu_{k})$ (which may depend on $(Q_{k})$) and a sequence of target policies $(\pi_{k})$ that are increasingly greedy w.r.t. the sequence $(Q_{k})$:

where the return operator $\mathcal{R}_{k}$ is defined by (3) for $\pi_{k}$ and $\mu_{k}$ and a Markovian $c_{s}=c(a_{s},x_{s})\in[0,\frac{\pi_{k}(a_{s}|x_{s})}{\mu_{k}(a_{s}|x_{s})}]$. Assume the target policies $\pi_{k}$ are $\varepsilon_{k}$-away from the greedy policies w.r.t. $Q_{k}$, in the sense that $\mathcal{T}^{\pi_{k}}Q_{k}\geq\mathcal{T}Q_{k}-\varepsilon_{k}\|Q_{k}\|e$, where $e$ is the vector with 1-components. Further suppose that $\mathcal{T}^{\pi_{0}}Q_{0}\geq Q_{0}$. Then for any $k\geq 0$,

In consequence, if $\varepsilon_{k}\to 0$ then $Q_{k}\to Q^{*}$.

Using $P^{c\mu_{k}}$, the Retrace$(\lambda)$ operator rewrites

We now lower- and upper-bound the term $Q_{k+1}-Q^{*}$.

Upper bound on $Q_{k+1}-Q^{*}$. We prove that $Q_{k+1}-Q^{*}\leq A_{k}(Q_{k}-Q^{*})$ with A_{k}:=\gamma(I-\gamma P^{c\mu_{k}})^{-1}\big{[}P^{\pi_{k}}-P^{c\mu_{k}}\big{]}. Since $c_{t}\in[0,\frac{\pi(a_{t}|x_{t})}{\mu(a_{t}|x_{t})}]$ we deduce that $A_{k}$ has non-negative elements, whose sum over each row, is at most $\gamma$. Thus

Lower bound on $Q_{k+1}-Q^{*}$. Using the fact that $\mathcal{T}^{\pi_{k}}Q_{k}\geq\mathcal{T}^{\pi^{*}}Q_{k}-\varepsilon_{k}\|Q_{k}\|e$ we have

Lower bound on $\mathcal{T}^{\pi_{k}}Q_{k}-Q_{k}$. Since the sequence $(\pi_{k})$ is increasingly greedy w.r.t. $(Q_{k})$, we have

where $B_{k}:=\gamma[P^{\pi_{k}}-P^{c\mu_{k}}](I-\gamma P^{c\mu_{k}})^{-1}$. Since $P^{\pi_{k}}-P^{c\mu_{k}}$ and $(I-\gamma P^{c\mu_{k}})^{-1}$ are non-negative matrices, so is $B_{k}$. Thus $\mathcal{T}^{\pi_{k}}Q_{k}-Q_{k}\geq B_{k-1}B_{k-2}\dots B_{0}(\mathcal{T}^{\pi_{0}}Q_{0}-Q_{0})\geq 0,$ since we assumed $T^{\pi_{0}}Q_{0}-Q_{0}\geq 0$. Thus, (5) implies that

Combining the above with (4) we deduce $\|Q_{k+1}-Q^{*}\|\leq\gamma\|Q_{k}-Q^{*}\|+\varepsilon_{k}\|Q_{k}\|$. When $\varepsilon_{k}\rightarrow 0$, we further deduce that $Q_{k}$ are bounded, thus $Q_{k}\to Q^{*}$. ∎

3 Online algorithms

So far we have analyzed the contraction properties of the expected $\mathcal{R}$ operators. We now describe online algorithms which can learn from sample trajectories. We analyze the algorithms in the every visit form (Sutton and Barto,, 1998), which is the more practical generalization of the first-visit form. In this section, we will only consider the Retrace($\lambda$) algorithm defined with the coefficient $c=\lambda\min(1,\pi/\mu)$. For that $c$, let us rewrite the operator $P^{c\mu}$ as $\lambda P^{\pi\wedge\mu}$, where $P^{\pi\wedge\mu}Q(x,a):=\sum_{y}\sum_{b}\min(\pi(b|y),\mu(b|y))Q(y,b)$, and write the Retrace operator $\mathcal{R}Q=Q+(I-\lambda\gamma P^{\pi\wedge\mu})^{-1}(\mathcal{T}^{\pi}Q-Q)$. We focus on the control case, noting that a similar (and simpler) result can be derived for policy evaluation.

Consider a sequence of sample trajectories, with the $k^{th}$ trajectory $x_{0},a_{0},r_{0},x_{1},a_{1},r_{1},\dots$ generated by following $\mu_{k}$: $a_{t}\sim\mu_{k}(\cdot|x_{t})$. For each $(x,a)$ along this trajectory, with $s$ being the time of first occurrence of $(x,a)$, update

The proof extends similar convergence proofs of TD($\lambda$) by Bertsekas and Tsitsiklis, (1996) and of optimistic policy iteration by Tsitsiklis, (2003), and is provided in the appendix. Notice that compared to Theorem 2 we do not assume that $\mathcal{T}^{\pi_{0}}Q_{0}-Q_{0}\geq 0$ here. However, we make the additional (rather technical) assumption that $P^{\pi_{k}}$ and $P^{\pi_{k}\wedge\mu_{k}}$ commute at the limit. This is satisfied for example when the probability assigned by the behavior policy $\mu_{k}(\cdot|x)$ to the greedy action $\pi_{Q_{k}}(x)$ is independent of $x$. Examples include $\varepsilon$-greedy policies, or more generally mixtures between the greedy policy $\pi_{Q_{k}}$ and an arbitrary distribution $\mu$ (see Lemma 5 in the appendix for the proof):

Notice that the mixture coefficient $\varepsilon$ needs not go to .

Discussion of the results

Theorems 1 and 2 ensure convergence to $Q^{\pi}$ and $Q^{*}$ for any trace coefficient $c_{s}\in[0,\frac{\pi(a_{s}|x_{s})}{\mu(a_{s}|x_{s})}]$. However, to make the best choice of $c_{s}$, we need to consider the speed of convergence, which depends on both (1) the variance of the online estimate, which indicates how many online updates are required in a single iteration of $\mathcal{R}$, and (2) the contraction coefficient of $\mathcal{R}$.

Contraction speed: The contraction coefficient $\eta\in[0,\gamma]$ of $\mathcal{R}$ (see Remark 1) depends on how much the traces have been cut, and should be as small as possible (since it takes $\log(1/\varepsilon)/\log(1/\eta)$ iterations of $\mathcal{R}$ to obtain an $\varepsilon$-approximation). It is smallest when the traces are not cut at all (i.e. if $c_{s}=1$ for all $s$, $\mathcal{R}$ is the policy evaluation operator which produces $Q^{\pi}$ in a single iteration). Indeed, when the traces are cut, we do not benefit from learning from full returns (in the extreme, $c_{1}=0$ and $\mathcal{R}$ reduces to the (one step) Bellman operator with $\eta=\gamma$).

A reasonable trade-off between low variance (when $c_{s}$ are small) and high contraction speed (when $c_{s}$ are large) is given by Retrace($\lambda$), for which we provide the convergence of the online algorithm.

If we relax the assumption that the trace is Markovian (in which case only the result for policy evaluation has been proven so far) we could trade off a low trace at some time for a possibly larger-than-$1$ trace at another time, as long as their product is less than $1$. A possible choice could be

2 Other topics of discussion

The crucial point of Theorem 2 is that convergence to $Q^{*}$ occurs for arbitrary behaviour policies. Thus the online result in Theorem 3 does not require the behaviour policies to become greedy in the limit with infinite exploration (i.e. GLIE assumption, Singh et al.,, 2000). We believe Theorem 3 provides the first convergence result to $Q^{*}$ for a $\lambda$-return (with $\lambda>0$) algorithm that does not require this (hard to satisfy) assumption.

Proof of Watkins’ Q(λ𝜆\lambda).

As a corollary of Theorem 3 when selecting our target policies $\pi_{k}$ to be greedy w.r.t. $Q_{k}$ (i.e. $\varepsilon_{k}=0$), we deduce that Watkins’ Q($\lambda$) ( e.g., Watkins,, 1989; Sutton and Barto,, 1998) converges a.s. to $Q^{*}$ (under the assumption that $\mu_{k}$ commutes asymptotically with the greedy policies, which is satisfied for e.g. $\mu_{k}$ defined by (8)). We believe this is the first such proof.

Increasingly greedy policies

The assumption that the sequence of target policies $(\pi_{k})$ is increasingly greedy w.r.t. the sequence of $(Q_{k})$ is more general that just considering greedy policies w.r.t. $(Q_{k})$ (which is Watkins’s Q($\lambda$)), and leads to more efficient algorithms. Indeed, using non-greedy target policies $\pi_{k}$ may speed up convergence as the traces are not cut as frequently. Of course, in order to converge to $Q^{*}$, we eventually need the target policies (and not the behaviour policies, as mentioned above) to become greedy in the limit (i.e. $\varepsilon_{k}\to 0$ as defined in Theorem 2).

Unlike Retrace($\lambda$), $Q^{\pi}(\lambda)$ does not need to know the behaviour policy $\mu$. However, it fails to converge when $\mu$ is far from $\pi$. Retrace($\lambda$) uses its knowledge of $\mu$ (for the chosen actions) to cut the traces and safely handle arbitrary policies $\pi$ and $\mu$.

Comparison to TB(λ𝜆\lambda).

Similarly to $Q^{\pi}(\lambda)$, TB($\lambda$) does not need the knowledge of the behaviour policy $\mu$. But as a consequence, TB($\lambda$) is not able to benefit from possible near on-policy situations, cutting traces unnecessarily when $\pi$ and $\mu$ are close.

Estimating the behavior policy.

In the case $\mu$ is unknown, it is reasonable to build an estimate $\widehat{\mu}$ from observed samples and use $\widehat{\mu}$ instead of $\mu$ in the definition of the trace coefficients $c_{s}$. This may actually even lead to a better estimate, as analyzed by LiAistats2015.

Continuous action space.

Let us mention that Theorems 1 and 2 extend to the case of (measurable) continuous or infinite action spaces. The trace coefficients will make use of the densities $\min(1,d\pi/d\mu)$ instead of the probabilities $\min(1,\pi/\mu)$. This is not possible with TB($\lambda$).

Open questions include:

(1) Removing the technical assumption that $P^{\pi_{k}}$ and $P^{\pi_{k}\wedge\mu_{k}}$ asymptotically commute, (2) Relaxing the Markov assumption in the control case in order to allow trace coefficients $c_{s}$ of the form (9).

Experimental Results

To validate our theoretical results, we employ Retrace$(\lambda)$ in an experience replay (Lin,, 1993) setting, where sample transitions are stored within a large but bounded replay memory and subsequently replayed as if they were new experience. Naturally, older data in the memory is usually drawn from a policy which differs from the current policy, offering an excellent point of comparison for the algorithms presented in Section 2.

Our agent adapts the DQN architecture of Mnih et al., (2015) to replay short sequences from the memory (details in the appendix) instead of single transitions. The Q-function target update for a sample sequence $x_{t},a_{t},r_{t},\cdots,x_{t+k}$ is

We compare our algorithms’ performance on 60 different Atari 2600 games in the Arcade Learning Environment (Bellemare et al.,, 2013) using Bellemare et al.,’s inter-algorithm score distribution. Inter-algorithm scores are normalized so that 0 and 1 respectively correspond to the worst and best score for a particular game, within the set of algorithms under comparison. If $g\in\{1,\dots,60\}$ is a game and $z_{g,a}$ the inter-algorithm score on $g$ for algorithm $a$, then the score distribution function is $f(x):=|\{g:z_{g,a}\geq x\}|/60$. Roughly, a strictly higher curve corresponds to a better algorithm.

Across values of $\lambda$, $\lambda=1$ performs best, save for $Q^{*}(\lambda)$ where $\lambda=0.5$ obtains slightly superior performance. However, is highly sensitive to the choice of $\lambda$ (see Figure 1, left, and Table 2 in the appendix). Both Retrace($\lambda$) and TB$(\lambda)$ achieve dramatically higher performance than Q-Learning early on and maintain their advantage throughout. Compared to TB($\lambda$), Retrace($\lambda$) offers a narrower but still marked advantage, being the best performer on 30 games; TB($\lambda$) claims 15 of the remainder. Per-game details are given in the appendix.

Retrace($\lambda$) can be seen as an algorithm that automatically adjusts – efficiently and safely – the length of the return to the degree of ”off-policyness” of any available data.

Acknowledgments.

The authors thank Daan Wierstra, Nicolas Heess, Hado van Hasselt, Ziyu Wang, David Silver, Audrunas Grūslys, Georg Ostrovski, Hubert Soyer, and others at Google DeepMind for their very useful feedback on this work.

References

Appendix A Proof of Lemma 1

Let $\Delta Q:=Q-Q^{\pi}$. We begin by rewriting (3):

Since $Q^{\pi}$ is the fixed point of $\mathcal{R}$, we have

Appendix B Increasingly greedy policies

Recall the definition of an increasingly greedy sequence of policies.

We say that a sequence of policies $(\pi_{k})$ is increasingly greedy w.r.t. a sequence of functions $(Q_{k})$ if the following property holds for all $k$:

It is obvious to see that this property holds if all policies $\pi_{k}$ are greedy w.r.t. $Q_{k}$. Indeed in such case, $\mathcal{T}^{\pi_{k+1}}Q_{k+1}=\mathcal{T}Q_{k+1}\geq\mathcal{T}^{\pi}Q_{k+1}$ for any $\pi$.

We now prove that this property holds for $\varepsilon_{k}$-greedy policies (with non-increasing $(\varepsilon_{k})$) as well as soft-max policies (with non-decreasing $(\beta_{k})$), as stated in the two lemmas below.

Of course not all policies satisfy this property (a counter-example being $\pi_{k}(a|x):=\arg\min_{a^{\prime}}Q_{k}(x,a^{\prime})$).

Let $(\varepsilon_{k})$ be a non-increasing sequence. Then the sequence of policies $(\pi_{k})$ which are $\varepsilon_{k}$-greedy w.r.t. the sequence of functions $(Q_{k})$ is increasingly greedy w.r.t. that sequence.

From the definition of an $\varepsilon$-greedy policy we have:

where we used the fact that $\varepsilon_{k+1}\leq\varepsilon_{k}$. ∎

Let $(\beta_{k})$ be a non-decreasing sequence of soft-max parameters. Then the sequence of policies $(\pi_{k})$ which are soft-max (with parameter $\beta_{k}$) w.r.t. the sequence of functions $(Q_{k})$ is increasingly greedy w.r.t. that sequence.

For any $Q$ and $y$, define $\pi_{\beta}(b)=\frac{e^{\beta Q(y,b)}}{\sum_{b^{\prime}}e^{\beta Q(y,b^{\prime})}}$ and $f(\beta)=\sum_{b}\pi_{\beta}(b)Q(y,b).$ Then we have

Thus $\beta\mapsto f(\beta)$ is a non-decreasing function, and since $\beta_{k+1}\geq\beta_{k}$, we have

Appendix C Proof of Theorem 2

As mentioned in the main text, since $c_{s}$ is Markovian, we can define the (sub)-probability transition operator

The Retrace$(\lambda)$ operator then writes

We now lower- and upper-bound the term $Q_{k+1}-Q^{*}$.

where A_{k}:=\gamma(I-\gamma P^{c\mu_{k}})^{-1}\big{[}P^{\pi_{k}}-P^{c\mu_{k}}\big{]}.

Now let us prove that $A_{k}$ has non-negative elements, whose sum over each row is at most $\gamma$. Let $e$ be the vector with 1-components. By rewriting $A_{k}$ as $\gamma\sum_{t\geq 0}\gamma^{t}(P^{c\mu_{k}})^{t}(P^{\pi_{k}}-P^{c\mu_{k}})$ and noticing that

it is clear that all elements of $A_{k}$ are non-negative. We have

(since $\sum_{t\geq 0}\gamma^{t}(P^{c\mu_{k}})^{t}e\geq e$). Thus $A_{k}$ has non-negative elements, whose sum over each row, is at most $\gamma$. We deduce from (10) that $Q_{k+1}-Q^{*}$ is upper-bounded by a sub-convex combination of components of $Q_{k}-Q^{*}$; the sum of their coefficients is at most $\gamma$. Thus

Now, from the definition of $\varepsilon_{k}$ we have $\mathcal{T}^{\pi_{k}}Q_{k}\geq\mathcal{T}Q_{k}-\varepsilon_{k}\|Q_{k}\|\geq\mathcal{T}^{\pi^{*}}Q_{k}-\varepsilon_{k}\|Q_{k}\|,$ thus

By hypothesis, $(\pi_{k})$ is increasingly greedy w.r.t. $(Q_{k})$, thus

where $B_{k}:=\gamma[P^{\pi_{k}}-P^{c\mu_{k}}](I-\gamma P^{c\mu_{k}})^{-1}$. Since $P^{\pi_{k}}-P^{c\mu_{k}}$ has non-negative elements (as proven in (11)) as well as $(I-\gamma P^{c\mu_{k}})^{-1}$, then $B_{k}$ has non-negative elements as well. Thus

since we assumed $T^{\pi_{0}}Q_{0}-Q_{0}\geq 0$. Thus (15) implies that

and combining the above with (13) we deduce

Now assume that $\varepsilon_{k}\rightarrow 0$. We first deduce that $Q_{k}$ is bounded. Indeed as soon as $\varepsilon_{k}<(1-\gamma)/2$, we have

Thus $\limsup\|Q_{k}\|\leq\frac{1+\gamma}{1-(1+\gamma)/2}\|Q^{*}\|$. Since $Q_{k}$ is bounded, we deduce that $\limsup Q_{k}=Q^{*}$. ∎

Appendix D Proof of Theorem 3

We first prove convergence of the general online algorithm.

and assume that (1) $\omega_{k}$ is a centered, ${\cal F}_{k}$-measurable noise term of bounded variance, and (2) $\upsilon_{k}$ is bounded from above by $\theta_{k}(\|Q_{k}\|+1)$, where $(\theta_{k})$ is a random sequence that converges to 0 a.s. Then, under the same assumptions as in Theorem 3, we have that $Q_{k}\rightarrow Q^{*}$ almost surely.

We write $\mathcal{R}$ for $\mathcal{R}_{k}$. Let us prove the result in three steps.

Upper bound on $\mathcal{R}Q_{k}-Q^{*}$. The first part of the proof is similar to the proof of (13), so we have

Lower bound on $\mathcal{R}Q_{k}-Q^{*}$. Again, similarly to (15) we have

Lower-bound on $\mathcal{T}^{\pi_{k}}Q_{k}-Q_{k}$. Since the sequence of policies $(\pi_{k})$ is increasingly greedy w.r.t. $(Q_{k})$, we have

where $\omega^{\prime}_{k}:=(\gamma P^{\pi_{k}}-I)\omega_{k}$ and $\upsilon^{\prime}_{k}:=(\gamma P^{\pi_{k}}-I)\upsilon_{k}$. It is easy to see that both $\omega^{\prime}_{k}$ and $\upsilon^{\prime}_{k}$ continue to satisfy the assumptions on $\omega_{k}$, and $\upsilon_{k}$. Now, from the definition of the $\mathcal{R}$ operator, we have

Using this equality into (20) and writing $\xi_{k}:=\mathcal{T}^{\pi_{k}}Q_{k}-Q_{k}$, we have

where $B_{k}:=\gamma(P^{\pi_{k}}-\lambda P^{\pi_{k}\wedge\mu_{k}})(I-\gamma\lambda P^{\pi_{k}\wedge\mu_{k}})^{-1}$. The matrix $B_{k}$ is non-negative but may not be a contraction mapping (the sum of its components per row may be larger than $1$). Thus we cannot directly apply Proposition 4.5 of Bertsekas and Tsitsiklis, (1996). However, as we have seen in the proof of Theorem 2, the matrix $A_{k}:=\gamma(I-\gamma\lambda P^{\pi_{k}\wedge\mu_{k}})^{-1}(P^{\pi_{k}}-\lambda P^{\pi_{k}\wedge\mu_{k}})$ is a $\gamma$-contraction mapping. So now we relate $B_{k}$ to $A_{k}$ using our assumption that $P^{\pi_{k}}$ and $P^{\pi_{k}\wedge\mu_{k}}$ commute asymptotically, i.e. $\|P^{\pi_{k}}P^{\pi_{k}\wedge\mu_{k}}-P^{\pi_{k}\wedge\mu_{k}}P^{\pi_{k}}\|=\eta_{k}$ with $\eta_{k}\rightarrow 0$. For any (sub)-transition matrices $U$ and $V$, we have

Replacing $U$ by $P^{\pi_{k}}$ and $V$ by $P^{\pi_{k}\wedge\mu_{k}}$, we deduce

where $\upsilon^{\prime\prime}_{k}:=\upsilon^{\prime}_{k}+\gamma\sum_{t\geq 0}t(\lambda\gamma)^{t}\eta_{k}\|\xi_{k}\|$ continues to satisfy the assumptions on $\upsilon_{k}$ (since $\eta_{k}\rightarrow 0$).

Now, let us define another sequence $\xi^{\prime}_{k}$ as follows: $\xi^{\prime}_{0}=\xi_{0}$ and

We can now apply Proposition 4.5 of Bertsekas and Tsitsiklis, (1996) to the sequence $(\xi^{\prime}_{k})$. The matrices $A_{k}$ are non-negative, and the sum of their coefficients per row is bounded by $\gamma$, see (12), thus $A_{k}$ are $\gamma$-contraction mappings and have the same fixed point which is . The noise $\omega^{\prime}_{k}$ is centered and $\mathcal{F}_{k}$-measurable and satisfies the bounded variance assumption, and $\upsilon^{\prime\prime}_{k}$ is bounded above by $(1+\gamma)\theta^{\prime}_{k}(\|Q_{k}\|+1)$ for some $\theta^{\prime}_{k}\rightarrow 0$. Thus $\lim_{k}\xi^{\prime}_{k}=0$ almost surely.

Now, it is straightforward to see that $\xi_{k}\geq\xi^{\prime}_{k}$ for all $k\geq 0$. Indeed by induction, let us assume that $\xi_{k}\geq\xi^{\prime}_{k}$. Then

since all elements of the matrix $A_{k}$ are non-negative. Thus we deduce that

Conclusion. Using (23) in (19) we deduce the lower bound:

almost surely. Now combining with the upper bound (18) we deduce that

The last two terms can be incorporated to the $\upsilon_{k}(x,a)$ and $\omega_{k}(x,a)$ terms, respectively; we thus again apply Proposition 4.5 of Bertsekas and Tsitsiklis, (1996) to the sequence $(Q_{k})$ defined by (17) and deduce that $Q_{k}\rightarrow Q^{*}$ almost surely. ∎

It remains to rewrite the update (7) in the form of (17), in order to apply Theorem 4.

Let $z^{k}_{s,t}$ denote the accumulating trace (Sutton and Barto,, 1998):

Let us write $Q^{o}_{k+1}(x_{s},a_{s})$ to emphasize the online setting. Then (7) can be written as

Using our assumptions on finite trajectories, and $c_{i}\leq 1$, we can show that:

Finally, using the above, and writing $\alpha_{k}=\alpha_{k}(x_{s},a_{s})$, (25) can be rewritten in the desired form:

We can thus apply Theorem 4 to (27), and conclude that the iterates $Q^{o}_{k}\rightarrow Q^{*}$ as $k\rightarrow\infty$, w.p. 1.

Let $(\pi_{k})$ and $(\mu_{k})$ two sequences of policies. If there exists $\alpha$ such that for all $x,a$,

then the transition matrices $P^{\pi_{k}}$ and $P^{\pi_{k}\wedge\mu_{k}}$ asymptotically commute: $\|P^{\pi_{k}}P^{\pi_{k}\wedge\mu_{k}}-P^{\pi_{k}\wedge\mu_{k}}P^{\pi_{k}}\|=o(1)$.

Let $(\pi_{Q_{k}})$ a sequence of (deterministic) greedy policies w.r.t. a sequence $(Q_{k})$. Let $(\pi_{k})$ a sequence of policies that are $\varepsilon_{k}$ away from $(\pi_{Q_{k}})$, in the sense that, for all $x$,

Let $(\mu_{k})$ a sequence of policies defined by:

for some arbitrary policy $\mu$ and $\alpha\in$. Assume $\varepsilon_{k}\rightarrow 0$. Then the transition matrices $P^{\pi_{k}}$ and $P^{\pi_{k}\wedge\mu_{k}}$ asymptotically commute.

The intuition is that asymptotically $\pi_{k}$ gets very close to the deterministic policy $\pi_{Q_{k}}$. In that case, the minimum distribution $(\pi_{k}\wedge\mu_{k})(\cdot|x)$ puts a mass close to $1-\alpha$ on the greedy action $\pi_{Q_{k}}(x)$, and no mass on other actions, thus $(\pi_{k}\wedge\mu_{k})$ gets very close to $(1-\alpha)\pi_{k}$, and Lemma 4 applies (with multiplicative constant $1-\alpha$).

Indeed, from our assumption that $\pi_{k}$ is $\varepsilon$-away from $\pi_{Q_{k}}$ we have:

Thus Lemma 4 applies (with a multiplicative constant $1-\alpha$) and $P^{\pi_{k}}$ and $P^{\pi_{k}\wedge\mu_{k}}$ asymptotically commute. ∎

Appendix F Experimental Methods

Although our experiments’ learning problem closely matches the DQN setting used by Mnih et al., (2015) (i.e. single-thread off-policy learning with large replay memory), we conducted our trials in the multi-threaded, CPU-based framework of Mnih et al., (2016), obtaining ample result data from affordable CPU resources. Key differences from the DQN are as follows. Sixteen threads with private environment instances train simultaneously; each infers with and finds gradients w.r.t. a local copy of the network parameters; gradients then update a “master” parameter set and local copies are refreshed. Target network parameters are simply shared globally. Each thread has private replay memory holding 62,500 transitions (1/16th of DQN’s total replay capacity). The optimizer is unchanged from (Mnih et al.,, 2016): “Shared RMSprop” with step size annealing to 0 over $3\times 10^{8}$ environment frames (summed over threads). Exploration parameter ($\varepsilon$) behaviour differs slightly: every 50,000 frames, threads switch randomly (probability 0.3, 0.4, and 0.3 respectively) between three schedules (anneal $\varepsilon$ from 1 to 0.5, 0.1, or 0.01 over 250,000 frames), starting new schedules at the intermediate positions where they left old ones.We evaluated a DQN-style single schedule for $\varepsilon$, but our multi-schedule method, similar to the one used by Mnih et al.,, yielded improved performance in our multi-threaded setting.

Our experiments comprise 60 Atari 2600 games in ALE (Bellemare et al.,, 2013), with “life” loss treated as episode termination. The control, minibatched (64 transitions/minibatch) one-step Q-learning as in (Mnih et al.,, 2015), shows performance comparable to DQN in our multi-threaded setup. Retrace, TB, and Q* runs use minibatches of four 16-step sequences (again 64 transitions/minibatch) and the current exploration policy as the target policy $\pi$. All trials clamp rewards into $$. In the control, Q-function targets are clamped into$$ prior to gradient calculation; analogous quantities in the multi-step algorithms are clamped into $$, then scaled (divided by) the sequence length. Coarse, then fine logarithmic parameter sweeps on the games Asterix, Breakout, Enduro, Freeway, H.E.R.O, Pong, Q*bert, and Seaquest yielded step sizes of 0.0000439 and 0.0000912, and RMSprop regularization parameters of 0.001 and 0.0000368, for control and multi-step algorithms respectively. Reported performance averages over four trials with different random seeds for each experimental configuration.

We compared our algorithms for different values of $\lambda$, using the DQN score as a baseline. As before, for each $\lambda$ we compute the inter-algorithm scores on a per-game basis. We then averaged the inter-algorithm scores across games to produce Table 2 (see also Figure 2 for a visual depiction). We first remark that Retrace always achieve a score higher than TB, demonstrating that it is efficient in the sense of Section 2. Next, we note that $Q^{*}$ performs best for small values of $\lambda$, but begins to fail for values above $\lambda=0.5$. In this sense, it is also not safe. This is particularly problematic as the safe threshold of $\lambda$ is likely to be problem-dependent. Finally, there is no setting of $\lambda$ for which Retrace performs particularly poorly; for high values of $\lambda$, it achieves close to the top score in most games. For Retrace($\lambda$) it makes sense to use a values $\lambda=1$ (at least in deterministic environments) as the trace cutting effect required in off-policy learning is taken care of by the use of the $\min(1,\pi/\mu)$ coefficient. On the contrary, $Q^{*}(\lambda)$ only relies on a value $\lambda<1$ to take care of cutting traces for off-policy data.