Q($λ$) with Off-Policy Corrections

Introduction

In reinforcement learning (RL), learning is off-policy when samples generated by a behavior policy are used to learn about a distinct target policy. The usual approach to off-policy learning is to disregard, or altogether discard transitions whose target policy probabilities are low. For example, Watkins’s Q($\lambda$) cuts the trajectory backup as soon as a non-greedy action is encountered. Similarly, in policy evaluation, importance sampling methods weight the returns according to the mismatch in the target and behavior probabilities of the corresponding actions. This approach treats transitions conservatively, and hence may unnecessarily terminate backups, or introduce a large amount of variance.

Many off-policy methods, in particular of the Monte Carlo kind, have no other option than to judge off-policy actions in the probability sense. However, temporal difference methods in RL maintain an approximation of the value function along the way, with eligiblity traces providing a continuous link between one-step and Monte Carlo approaches. The value function assesses actions in terms of the following expected cumulative reward, and thus provides a way to directly correct immediate rewards, rather than transitions. We show in this paper that such approximate corrections can be sufficient for off-policy convergence, subject to a tradeoff condition between the eligibility trace parameter and the distance between the target and behavior policies. The two extremes of this tradeoff are one-step Q-learning, and on-policy learning. Formalizing the continuum of the tradeoff is one of the main insights of this paper.

In particular, we propose an off-policy return operator that augments the return with a correction term, based on the current approximation of the Q-function. We then formalize three algorithms stemming from this operator: (1) off-policy Qπ($\lambda$), and its special case (2) on-policy Qπ($\lambda$), for policy evaluation, and (3) Q∗($\lambda$) for off-policy control.

In policy evaluation, both on- and off-policy Qπ($\lambda$) are novel, but closely related to several existing algorithms of the TD($\lambda$) family. Section 7 discusses this in detail. We prove convergence of Qπ($\lambda$), subject to the $\lambda-\varepsilon$ tradeoff where $\varepsilon\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}\max_{x}\|\pi(\cdot|x)-\mu(\cdot|x)\|_{1}$ is a measure of dissimilarity between the behavior and target policies. More precisely, we prove that for any amount of “off-policy-ness” $\varepsilon\in$ there is an inherent maximum allowed backup length value $\lambda=\frac{1-\gamma}{\gamma\varepsilon}$, and taking $\lambda$ below this value guarantees convergence to $Q^{\pi}$ without involving policy probabilities. This is desirable due to the instabilities and variance introduced by the likelihood ratio products in the importance sampling approach .

In control, Q∗($\lambda$) is in fact identical to Watkins’s Q($\lambda$), except it does not cut the eligiblity trace at off-policy actions. Sutton and Barto 1998 mention such a variation, which they call naive Q($\lambda$). We analyze this algorithm for the first time and prove its convergence for small values of $\lambda$. Although we were not able to prove a $\lambda-\varepsilon$ tradeoff similar to the policy evaluation case, we provide empirical evidence for the existence of such a tradeoff, confirming the intuition that naive Q($\lambda$) is “not as naive as one might at first suppose” .

We first give the technical background, and define our operators. We then specify the incremental versions of our algorithms based on these operators, and state their convergence. We follow by proving convergence: subject to the $\lambda-\varepsilon$ tradeoff in policy evaluation, and more conservatively, for small values of $\lambda$ in control. We illustrate the tradeoff emerge empirically in the Bicycle domain in the control setting. Finally, we conclude by placing our algorithms in context within existing work in TD($\lambda$).

Preliminaries

To each policy $\pi$ corresponds a unique Q-function $Q^{\pi}$ which describes the expected discounted sum of rewards achieved when following $\pi$:

where for any operator $X$, $(X)^{t}$ denotes $t$ successive applications of $X$, and where we commonly treat $r$ as one particular Q-function. We write the Bellman operator $\mathcal{T}^{\pi}$, and the Bellman equation for $Q^{\pi}$:

The Bellman optimality operator $\mathcal{T}$ is defined as $\mathcal{T}Q\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}r+\gamma\max_{\pi}P^{\pi}Q,$ and it is well known [1, 10, e.g.] that the optimal Q-function $Q^{*}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}\sup_{\pi}Q^{\pi}$ is the unique solution to the Bellman optimality equation

We write $\textsc{Greedy}(Q)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}\{\pi|\pi(a|x)>0\Rightarrow Q(x,a)=\max_{a^{\prime}}Q(x,a^{\prime})\}$ to denote the set of greedy policies w.r.t. $Q$. Thus $\mathcal{T}Q=\mathcal{T}^{\pi}Q$ for any $\pi\in\textsc{Greedy}(Q)$.

Temporal difference (TD) learning rests on the fact that iterates of both operators $\mathcal{T}^{\pi}$ and $\mathcal{T}$ are guaranteed to converge to their respective fixed points $Q^{\pi}$ and $Q^{*}$. Given a sample experience $x,a,r,x^{\prime},a^{\prime}$, SARSA(0) updates its Q-function estimate at $k^{th}$ iteration as follows:

Naturally, $Q^{\pi}$ remains the fixed point of $\mathcal{T}_{\lambda}^{\pi}$. Taking $\lambda=0$ yields the usual Bellman operator $\mathcal{T}^{\pi}$, and $\lambda=1$ removes the recursion on the approximate Q-function, and restores $Q^{\pi}$ in the Monte Carlo sense. It is well-known that $\lambda$ trades off the bias from bootstrapping with an approximate Q-function, with the variance from using a sampled multi-step return , with intermediate values of $\lambda$ usually performing best in practice . The above $\lambda$-operator can be efficiently implemented in the online setting via a mechanism called eligibility traces. As we will see in Section 7, it in fact corresponds to a number of online algorithms, each subtly different, of which SARSA($\lambda$) is the canonical instance.

Off-Policy Return Operators

We will now describe the Monte Carlo off-policy corrected return operator $\mathcal{R}^{\pi,\mu}$ that is at the heart of our contribution. Given a target $\pi$, and a return generated by the behavior $\mu$, the operator $\mathcal{R}^{\pi,\mu}$ attempts to approximate a return that would have been generated by $\pi$, by utilizing a correction built from a current approximation $Q$ of $Q^{\pi}$. Its application to $Q$ at a state-action pair $(x,a)$ is defined as follows:

That is, $\mathcal{R}^{\pi,\mu}$ gives the usual expected discounted sum of future rewards, but each reward in the trajectory is augmented with an off-policy correction, which we define as the difference between the expected (with respect to the target policy) Q-value and the Q-value for the taken action. Thus, how much a reward is corrected is determined by both the approximation $Q$, and the target policy probabilities. Notice that if actions are similarly valued, the correction will have little effect, and learning will be roughly on-policy, but if the Q-function has converged to the correct estimates $Q^{\pi}$, the correction takes the immediate reward $r_{t}$ to the expected reward with respect to $\pi$ exactly. Indeed, as we will see later, $Q^{\pi}$ is the fixed point of $\mathcal{R}^{\pi,\mu}$ for any behavior policy $\mu$.

We define the $n$-step and $\lambda$-versions of $\mathcal{R}^{\pi,\mu}$ in the usual way:

Note that the $\lambda$ parameter here takes us from TD($0$) to the Monte Carlo version of our operator $\mathcal{R}^{\pi,\mu}$, rather than the traditional Monte Carlo form (1).

Algorithm

where $\pi_{k}$ is the $k^{th}$ interim target policy. We distinguish between three algorithms:

$\pi_{k}=\pi$ is the fixed target policy. We write the corresponding operator $\mathcal{R}^{\pi}_{\lambda}$.

for the special case of $\mu_{k}=\mu=\pi$.

We wish to write the update (6) in terms of a simulated trajectory $x_{0},a_{0},r_{0},\dots,$ $x_{T_{k}}$ drawn according to $\mu_{k}$. First, notice that (5) can be rewritten:

where $\delta^{\pi}_{t}$ is the expected TD-error. The offline forward view The true online version can be derived as given by van Seijen and Sutton 2014 is then

While (7) resembles many existing TD($\lambda$) algorithms, it subtly differs from all of them, due to $\mathcal{R}^{\pi,\mu}_{\lambda}$ (rather than $\mathcal{T}^{\pi}_{\lambda}$) being at its basis. Section 7 discusses the distinctions in detail. The practical every-visit form of (7) is written

and the corresponding online backward view of all three algorithms is summarized in Algorithm 1.

The following theorem states that when $\mu$ and $\pi$ are sufficiently close, the off-policy Qπ($\lambda$) algorithm converges to its fixed point $Q^{\pi}$.

Consider the sequence of Q-functions computed according to Algorithm 1 with fixed policies $\mu$ and $\pi$. Let $\varepsilon=\max_{x}\|\pi(\cdot|x)-\mu(\cdot|x)\|_{1}$. If $\lambda\varepsilon<\frac{1-\gamma}{\gamma}$, then under the same conditions required for the convergence of $TD(\lambda)$ (1–3 in Section 5.3) we have, almost surely:

We state a similar, albeit weaker result for Q∗($\lambda$).

Consider the sequence of Q-functions computed according to Algorithm 1 with $\pi_{k}$ the greedy policy with respect to $Q_{k}$. If $\lambda<\frac{1-\gamma}{2\gamma}$, then under the same conditions required for the convergence of TD($\lambda$) (1–3 in Section 5.3) we have, almost surely:

The proofs of these theorems rely on showing that $\mathcal{R}^{\pi}_{\lambda}$ and $\mathcal{R}^{*}_{\lambda}$ are contractions (under the stated conditions), and invoking classical stochastic approximation convergence to their fixed point (such as Proposition 4.5 from ). We will focus on the contraction lemmas, which are the crux of the proofs, then outline the sketch of the online convergence argument.

Theorem 4.1 states that for any $\lambda\in$ there exists some degree of “off-policy-ness” $\varepsilon<\frac{1-\gamma}{\lambda\gamma}$ under which $Q_{k}$ converges to $Q^{\pi}$. This is the $\lambda-\varepsilon$ tradeoff for the off-policy $Q^{\pi}(\lambda)$ learning algorithm for policy evaluation. In the control case, the result of Theorem 4.2 is weaker as it only holds for values of $\lambda$ smaller than $\frac{1-\gamma}{2\gamma}$. Notice that this threshold corresponds to the policy evaluation case for $\varepsilon=2$ (arbitrary off-policy-ness). We were not able to prove convergence to $Q^{*}$ for any $\lambda\in$ and some $\varepsilon>0$. This is left as an open problem for now.

The main technical difficulty lies in the fact that in control, the greedy policy with respect to the current $Q_{k}$ may change drastically from one step to the next, while $Q_{k}$ itself changes incrementally (under small learning steps $\alpha_{k}$). So the current $Q_{k}$ may not offer a good off-policy correction to evaluate the new greedy policy. In order to circumvent this problem we may want to use slowly changing target policies $\pi_{k}$. For example we could keep $\pi_{k}$ fixed for slowly increasing periods of time. This can be seen as a form of optimistic policy iteration where policy improvement steps alternate with approximate policy evaluation steps (and when the policy is fixed, Theorem 4.1 guarantees convergence to the value function of that policy). Another option would be to define $\pi_{k}$ as the empirical average $\pi_{k}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}\frac{1}{k}\sum_{i=1}^{k}\pi_{i}^{\prime}$ of the previous greedy policies $\pi^{\prime}_{i}$. We conjecture that defining $\pi_{k}$ such that (1) $\pi_{k}$ changes slowly with $k$, and (2) $\pi_{k}$ becomes increasingly greedy, then we could extend the $\lambda-\varepsilon$ tradeoff of Theorem 4.1 to the control case. This is left for future work.

Analysis

We begin by verifying that the fixed points of $\mathcal{R}^{\pi,\mu}_{\lambda}$ in the policy evaluation and control settings are $Q^{\pi}$ and $Q^{*}$, respectively. We then prove the contractive properties of these operators: $\mathcal{R}^{\pi}_{\lambda}$ is always a contraction and will converge to its fixed point, $\mathcal{R}^{*}_{\lambda}$ is a contraction for particular choices of $\lambda$ (given in terms of $\gamma$). The contraction coefficients depend on $\lambda$, $\gamma$, and $\varepsilon$: the distance between policies. Finally, we give a proof sketch for online convergence of Algorithm 1.

Before we begin, it will be convenient to rewrite (4) for all state-action pairs:

We can then write $\mathcal{R}^{\pi}_{\lambda}$ and $\mathcal{R}^{*}_{\lambda}$ from (5) as follows:

It is not surprising that the above along with the Bellman equations (2) and (3) directly yields that $Q^{\pi}$ and $Q^{*}$ are the fixed points of $\mathcal{R}_{\lambda}^{\pi}$ and $\mathcal{R}^{*}_{\lambda}$:

It then remains to analyze the behavior of $\mathcal{R}^{\pi,\mu}_{\lambda}$ as it gets iterated.

Consider the policy evaluation algorithm $Q_{k}=(\mathcal{R}^{\pi}_{\lambda})^{k}Q$. Assume the behavior policy $\mu$ is $\varepsilon$-away from the target policy $\pi$, in the sense that $\max_{x}\|\pi(\cdot|x)-\mu(\cdot|x)\|_{1}\leq\varepsilon$. Then for $\varepsilon<\frac{1-\gamma}{\lambda\gamma}$, the sequence $(Q_{k})_{k\geq 1}$ converges to $Q^{\pi}$ exponentially fast: $\|Q_{k}-Q^{\pi}\|=O(\eta^{k})$, where $\eta=\frac{\gamma}{1-\lambda\gamma}(1-\lambda+\lambda\varepsilon)<1$.

Let $B=(I-\lambda\gamma P^{\mu})^{-1}$ be the resolvent matrix. From (9) we have

Taking the sup norm, since $\mu$ is $\varepsilon$-away from $\pi$:

for $\eta=\frac{\gamma}{1-\lambda\gamma}(1-\lambda+\lambda\varepsilon)<1$. Thus $\|Q_{k}-Q^{\pi}\|=O(\eta^{k})$.

2 λ\lambda-return for control: Q∗(λ\lambda)

We next consider the case where the $k^{th}$ target policy $\pi_{k}$ is greedy with respect to the value estimate $Q_{k}$. The following Lemma states that is possible to select a small, but nonzero $\lambda$ and still guarantee convergence.

Consider the off-policy control algorithm $Q_{k}=(\mathcal{R}_{\lambda}^{*})^{k}Q$. Then

and for $\lambda<\frac{1-\gamma}{2\gamma}$ the sequence $(Q_{k})_{k\geq 1}$ converges to $Q^{*}$ exponentially fast.

Fix $\mu$ and let $B=(I-\lambda\gamma P^{\mu})^{-1}$. Using (10), we write

Taking the sup-norm, since $\|\mathcal{T}Q-Q^{*}\|\leq\gamma\|Q-Q^{*}\|$, we deduce the result:

3 Online Convergence

We are now ready to prove the online convergence of Algorithm 1. Let the following hold for every sample trajectory $\tau_{k}$ and all $x\in\mathcal{X},a\in\mathcal{A}$:

Bounded stepsizes: $\sum_{k\geq 0}\alpha_{k}(x,a)=\infty$, $\sum_{k\geq 0}\alpha_{k}^{2}(x,a)<\infty$.

Assumption 2 requires trajectories to be finite w.p. 1, which is satisfied by proper behavior policies. Equivalently, we may require from the MDP that all trajectories eventually reach a zero-value absorbing state. The proof closely follows that of Proposition 5.2 from , and requires rewriting the update in the suitable form, and verifying Assumptions (a) through (d) from their Proposition 4.5.

Experimental Results

Although we do not have a proof of the $\lambda-\varepsilon$ tradeoff (see Section 4) in the control case, we wished to investigate whether such a tradeoff can be observed experimentally. To this end, we applied Q∗($\lambda$) to the Bicycle domain . Here, the agent must simultaneously balance a bicycle and drive it to a goal position. Six real-valued variables describe the state – angle, velocity, etc. – of the bicycle. The reward function is proportional to the angle to the goal, and gives -1 for falling and +1 for reaching the goal. The discount factor is 0.99. The Q-function was approximated using multilinear interpolation over a uniform grid of size $10\times\dots\times 10$, and the stepsize was tuned to 0.1. We are chiefly interested in the interplay between the $\lambda$ parameter in Q∗($\lambda$) and an $\varepsilon$-greedy exploration policy. Our main performance indicator is the frequency at which the goal is reached by the greedy policy after 500,000 episodes of training. We report three findings:

Higher values of $\lambda$ lead to improved learning;

Very low values of $\varepsilon$ exhibit lower performance; and

The Q-function diverges when $\lambda$ is high relative to $\varepsilon$.

Together, these findings suggest that there is indeed a $\lambda-\varepsilon$ tradeoff in the control case as well, and lead us to conclude that with proper care it can be beneficial to do off-policy control with Q∗($\lambda$).

Learning speed and performance. Figure 1 (left) depicts the performance of Q∗($\lambda$), in terms of the goal-reaching frequency, for three values of $\varepsilon$. The agent performs best ($p<0.05$) for $\varepsilon\in[0.003,0.03]$ and high (w.r.t. $\varepsilon$) values of $\lambda$. Recall that Randløv and Alstrøm’s agent was trained using SARSA($\lambda)$ with $\lambda=0.95$.

Divergence. For each value of $\varepsilon$, we determined the highest safe choice of $\lambda$ which did not result in divergence. As Figure 1 (right) illustrates, there is a marked decrease in what is a safe value of $\lambda$ as $\varepsilon$ increases. Note the left-hand shaded region corresponding to the policy evaluation bound $\frac{1-\gamma}{\gamma\varepsilon}$. Supporting our hypothesis on the true bound on $\lambda$ (Section 5), it appears clear that the maximum safe value of $\lambda$ depends on $\varepsilon$. In particular, notice how $\lambda=1$ stops diverging exactly where predicted by this bound.

Related Work

In this section, we place the presented algorithms in context of the existing work in TD($\lambda$) , focusing in particular on action-value methods. As usual, let $(x_{t},a_{t},r_{t})_{t\geq 0}$ be a trajectory generated by following a behavior policy $\mu$, i.e. $a_{t}\sim\mu(\cdot|x_{t})$. At time $s$, SARSA($\lambda$) updates its $Q$-function as follows:

where $\Delta_{s}$ denotes the update made at time $s$, and can be rewritten in terms of one-step TD-errors:

SARSA($\lambda$) is an on-policy algorithm and converges to the value function $Q^{\mu}$ of the behavior policy. Different algorithms arise by instantiating $R^{(n)}_{s}$ or $\Delta_{s}$ from (11) differently. Table 1 provides the full details, while in text we will specify the most revealing components of the update.

This is the one-step update for General Q-Learning , which is a generalization of Expected SARSA to arbitrary policies. We refer to the direct eligibility trace extensions of these algorithms formed via Equations (11)-(13) by General Q($\lambda$) and Expected SARSA($\lambda$) (first mentioned by Sutton et al. 2014) Unfortunately, in an off-policy setting, General Q($\lambda$) will not converge to the value function $Q^{\pi}$ of the target policy, as stated by the following proposition.

The stable point of General Q($\lambda$) is $Q^{\mu,\pi}=(I-\lambda\gamma(P^{\mu}-P^{\pi})-\gamma P^{\pi})^{-1}r$ which is the fixed point of the operator $(1-\lambda)\mathcal{T}^{\pi}+\lambda\mathcal{T}^{\mu}$.

Writing the algorithm in operator form, we get

Thus the fixed point $Q^{\mu,\pi}$ of $\mathcal{R}$ satisfies the following:

Solving for $Q^{\mu,\pi}$ yields the result.

This is exactly our policy evaluation algorithm Qπ($\lambda$). Specifically, when $\pi=\mu$, we get the on-policy Qπ($\lambda$). The induced on-policy correction may serve as a variance reduction term for Expected SARSA($\lambda$) (it may be helpful to refer to the $n$-step return in Table 1 to observe this), but we leave variance analysis of this algorithm for future work. When $\pi\neq\mu$, we recover off-policy Qπ($\lambda$), which (under the stated conditions) converges to $Q^{\pi}$.

The algorithms above directly descend from basic SARSA($\lambda$), but often learning off-policy requires special treatment. For example, a typical off-policy technique is importance sampling (IS) . It is a classical Monte Carlo method that allows one to sample from the available distribution, but obtain (unbiased or consistent) samples of the desired one, by reweighing the samples with their likelihood ratio according to the two distributions. That is, the updates for the ordinary per-decision IS algorithm for policy evaluation are made as follows:

This family of algorithms converges to $Q^{\pi}$ with probability $1$, under any soft, stationary behavior $\mu$ . There are several (recent) off-policy algorithms that reduce the variance of IS methods, at the cost of added bias .

However, off-policy Qπ($\lambda$) is perhaps related closest to the Tree-Backup (TB) algorithm, also discussed by Precup et al. 2000. Its one-step TD-error is the same as (15), the algorithms back up the same tree, and neither requires knowledge of the behavior policy $\mu$. The important difference is in the weighting of the updates. As an off-policy precaution, TB($\lambda$) weighs updates along a trajectory with the cumulative target probability of that trajectory up until that point:

The weighting simplifies the convergence argument, allowing TB($\lambda$) to converge to $Q^{\pi}$ without further restrictions on the distance between $\mu$ and $\pi$ . The drawback of TB($\lambda$) is that in the case of near on-policy-ness (when $\mu$ is close to $\pi$) the product of the probabilities cuts the traces unnecessarily (especially when the policies are stochastic). What we show in this paper, is that plain TD-learning can converge off-policy with no special treatment, subject to a tradeoff condition on $\lambda$ and $\varepsilon$. Under that condition, Qπ($\lambda$) applies both on- and off-policy, without modifications. An ideal algorithm should be able to automatically cut the traces (like TB($\lambda$)) in case of extreme off-policy-ness while reverting to Qπ($\lambda$) when being near on-policy.

2 Control

Perhaps the most popular version of Q($\lambda$) is due to Watkins and Dayan 1992. Off-policy, it truncates the return and bootstraps as soon as the behavior policy takes a non-greedy action, as described by the following update:

Q($\lambda$) of Peng and Williams 1996 is meant to remedy this, by being a hybrid between SARSA($\lambda$) and Watkins’s Q($\lambda$). Its $n$-step return $\sum_{t=s}^{s+n}\gamma^{t-s}r_{t}+\gamma^{n+1}\max_{a}Q(x_{s+n+1},a)$ requires the following form for the TD-error:

This is, in fact, the same update rule as the General Q($\lambda$) defined in (14), where $\pi$ is the greedy policy. Following the same steps as in the proof of Proposition 1, the limit of this algorithm (if it converges) will be the fixed point of the operator $(1-\lambda)\mathcal{T}+\lambda\mathcal{T}^{\mu}$ which is different from $Q^{*}$ unless the behavior is always greedy.

Sutton and Barto 1998 mention another, naive version of Watkins’s Q($\lambda$) that does not cut the trace on non-greedy actions. That is exactly the Q∗($\lambda$) algorithm described in this paper. Notice that despite the similarity to Watkins’s Q($\lambda$), the equivalence representation for Q∗($\lambda$) is different from the one that would be derived by setting $\tau=\infty$ in (17), since the $n$-step return uses the corrected immediate reward $r_{t}+\gamma\max_{a}Q(x_{t},a)-Q(x_{t},a_{t})$ instead of the immediate reward alone. This correction is invisible in Watkins’s Q($\lambda$), since the behavior policy is assumed to be greedy, before the return is cut off.

Conclusion

We formulated new algorithms of the TD$(\lambda)$ family for off-policy policy evaluation and control. Unlike traditional off-policy learning algorithms, these methods do not involve weighting returns by their policy probabilities, yet under the right conditions converge to the correct TD fixed points. In policy evaluation, convergence is subject to a tradeoff between the degree of bootstrapping $\lambda$, distance between policies $\varepsilon$, and the discount factor $\gamma$. In control, determining the existence of a non-trivial $\varepsilon$-dependent bound for $\lambda$ remains an open problem. Supported by telling empirical results in the Bicycle domain, we hypothesize that such a bound exists, and closely resembles the $\frac{1-\gamma}{\gamma\varepsilon}$ bound from the policy evaluation case.

Acknowledgements

The authors thank Hado van Hasselt and others at Google DeepMind, as well as the anonymous reviewers for their thoughtful feedback on the paper.

References