Improving the Efficiency of Off-Policy Reinforcement Learning
by Accounting for Past Decisions

In our work, we are particularly interested in the off-policy learning case, where trajectories of the form $((s,a),(s_{1},a_{1}),(s_{2},a_{2}),\dots)$, $(s_{k},a_{k})\in\mathcal{S}\times\mathcal{A}$, are generated by interacting with the MDP using a behavior policy $\mu\in\Pi$, $\mu\neq\pi$. Let $\mathcal{F}_{t}$ denote the first $t+1$ terms of this sequence. We define the TD error for policy $\pi$ at timestep $t$ as

Let $\rho_{k}\coloneqq\frac{\pi(a_{k}|s_{k})}{\mu(a_{k}|s_{k})}$ for brevity. [14] introduced the following off-policy operator:

where $c(s_{k},a_{k})\in[0,\rho_{k}]$ are arbitrary nonnegative coefficients, or traces. When $c(s_{k},a_{k})<\rho_{k}$, we say that the trace has been (partially) cut. Note that the traces are Markov in the sense that they depend only on the state-action pair $(s_{k},a_{k})$ and are otherwise independent of $\mathcal{F}_{k}$. In other words, the traces for $\mathcal{R}$ can be calculated per decision [16], thereby permitting an efficient online implementation with eligibility traces.

While per-decision traces are convenient from a computational perspective, they require making choices about how much to cut a trace without direct consideration of the past. This can lead to locally optimal decisions; for example, if the trace is cut by setting $c(s_{k},a_{k})=0$ at some timestep, then the effect cannot be reversed later. Regardless of whatever new experiences are encountered by the agent, experiences before timestep $k$ will be ineligible for credit assignment, resulting in an opportunity cost. In fact, this exact phenomenon is why Watkins’ Q($\lambda$) [29] often learns more slowly than Peng’s Q($\lambda$) [15] even though the former avoids off-policy bias [23, 4, 9]. The same effect (but to a lesser extent) impacts Tree Backup and Retrace where $c(s_{k},a_{k})\leq 1$ always, implying that the eligibilities for past experiences can never increase.

For this reason, it may be desirable to expend some additional computation in exchange for better decisions regarding credit assignment. Our principal contribution is the proposal and analysis of the following off-policy operator that encompasses this possibility:

where each $\beta(\mathcal{F}_{t})$ is an arbitrary nonnegative coefficient that generally depends on the history $\mathcal{F}_{t}$. By analogy to TD(0) [22], we define $\beta(\mathcal{F}_{0})\coloneqq 1$. The principal goal of Section 3 is to characterize the values of $\beta(\mathcal{F}_{t})$ for $t\geq 1$ that lead to convergence in the policy evaluation and control settings.

The major analytical challenge of our operator, and its main novelty, is the complex dependence on the sequence $\mathcal{F}_{t}$. Our operator is therefore inherently non-Markov, in spite of the fact that the MDP dynamics are Markov by definition. Mathematically, this makes the $\mathcal{M}$ operator difficult to analyze, as the terms in the series $1+\beta(\mathcal{F}_{1})+\beta(\mathcal{F}_{2})+\cdots$ generally share no common factors that would allow a per-decision update for eligibility traces. Nevertheless, removing the Markov assumption is necessary to understand important existing algorithms (see Section 2.2) while also paving the way for new credit assignment algorithms.

A special case arises when $\beta(\mathcal{F}_{t})$ does factor into traces: that is, $\beta(\mathcal{F}_{t})=\prod_{k=1}^{t}c(s_{k},a_{k})$ for every history $\mathcal{F}_{t}$. Equation (2) therefore reduces to equation (1), taking us back to the Markov setting studied by [14]. As such, our $\mathcal{M}$ operator subsumes the $\mathcal{R}$ operator as a specific case, and our later theoretical developments have implications for Retrace and related off-policy algorithms. We discuss these implications in Section 4.

By weighting each TD error with an arbitrary history-dependent coefficient $\beta(\mathcal{F}_{t})$, the $\mathcal{M}$ operator is remarkably general, but this also makes it abstract. To help concretize it, we describe several existing off-policy algorithms below and how they can be described in the notation of our operator. This should aid with understanding and illuminate cases where our operator is necessary to explain convergence.

Importance Sampling (IS): $\beta(\mathcal{F}_{t})=\prod_{k=1}^{t}\rho_{k}$.
The standard approach for correcting off-policy experience. Although it is the only unbiased estimator in this list, it suffers from high variance when $\mu(a_{k}|s_{k})\approx 0$ that makes it difficult to utilize effectively in practice.

Q($\lambda$) with Off-Policy Corrections [5]: $\beta(\mathcal{F}_{t})=\prod_{k=1}^{t}\lambda$.
A straightforward algorithm that decays the TD errors by a fixed constant $\lambda\in[0,1]$. In the on-policy ($\mu=\pi$) policy evaluation case, this is equivalent to the TD($\lambda$) extension [22] of Expected Sarsa [23]. The algorithm does not require explicit knowledge of the behavior policy $\mu$, which is desirable; however, it is not convergent when $\pi$ and $\mu$ differ too much, and this criterion is restrictive in practice.

Tree Backup (TB) [16]: $\beta(\mathcal{F}_{t})=\prod_{k=1}^{t}\lambda\pi(a_{k}|s_{k})$.
A method that automatically cuts traces according to the product of probabilities under the target policy $\pi$, which forms a conservative lower bound on the IS ratio product. As a result, TB converges for any behavior policy $\mu$, but it is not efficient since traces are cut excessively—especially in the on-policy case.

Retrace [14]: $\beta(\mathcal{F}_{t})=\prod_{k=1}^{t}\lambda\min(1,\rho_{k})$.
A convergent algorithm for arbitrary policies $\pi$ and $\mu$ that remains efficient in the on-policy case because it does not cut traces (if $\lambda=1$); however, the fact that $\beta(\mathcal{F}_{t})$ is monotone non-increasing can cause the trace products to decay too quickly in practice [12, 17].

Non-Markov Retrace [14]: $\beta(\mathcal{F}_{t})=\lambda\min(1,\beta(\mathcal{F}_{t-1})\rho_{t})$.
A modification to Retrace proposed by [14] and conjectured to lead to faster learning. It permits trace values larger than $1$ by relaxing the clipping bound when the historical trace product $\beta(\mathcal{F}_{t-1})$ is small (see Section 4.3). The algorithm is recursive, which makes it difficult to analyze, and its convergence for control is an open question.

Truncated Importance Sampling [6]: $\beta(\mathcal{F}_{t})=\min(d_{t},\prod_{k=1}^{t}\rho_{k})$.
A simple but effective method to combat the variance of the IS estimator. For any value of $d_{t}\geq 0$, the obtained variance is finite. Variations of this algorithm have been applied in the reinforcement learning literature [e.g. 27, 31, 30, 28], but to our knowledge its convergence in an MDP setting has not been studied.

We conclude with some remarks about the interpretation of our result. Note that when $\beta(\mathcal{F}_{t})=0$ for $t\geq 1$, we have the slowest contraction rate of $\gamma$, which corresponds to TD(0). When $\beta(\mathcal{F}_{t})=\prod_{k=1}^{t}\rho_{k}$, we get an optimal contraction rate of $0$, which corresponds to the standard IS estimator. (Of course, this is only in expectation.) Between these two extremes lies a vast spectrum of convergent algorithms, which includes the examples mentioned in Section 2.2 as well as an infinitude of other possibilities. In Section 4.2, we discuss practical considerations for choosing $\beta(\mathcal{F}_{t})$ and how to efficiently implement history-dependent algorithms.

We now consider the more-difficult setting of control. Given a sequence of target policies $(\pi_{k})_{k\geq 0}$, $\pi_{k}\in\Pi$, and a sequence of behavior policies $(\mu_{k})_{k\geq 0}$, $\mu_{k}\in\Pi$, we aim to show that the sequence of Q-functions $(Q_{k})$ given by $Q_{k+1}\coloneqq\mathcal{M}_{k}Q_{k}$ converges to $Q^{*}$. (Here, $\mathcal{M}_{k}$ is the $\mathcal{M}$ operator defined for $\pi_{k}$ and $\mu_{k}$.)

Unlike [14], we do not assume that the target policies are increasingly greedy with respect to $(Q_{k})$. Instead, we require only that the policies become greedy in the limit. We say that the sequence of policies $(\pi_{k})$ is greedy in the limit if and only if $T_{\pi_{k}}Q_{k}\to TQ_{k}$ as $k\to\infty$. Intuitively, this means that each policy need not be greedier than its predecessors, so long as the sequence of policies eventually does become greedy. We discuss the significance of this assumption more in Section 4.1.

We see that the convergence criterion of $\beta(\mathcal{F}_{t})\leq\prod_{k=1}^{t}\rho_{k}$ in the control setting is the same as that for the policy evaluation. In fact, the only additional assumption we needed is the greedy-in-the-limit target policies. Crucially, the proof allows arbitrary behavior policies and arbitrary initialization of the Q-function, which we discuss further in the next section.

Removal of Markov assumption. As we stated in the introduction, removing the Markov assumption of the $\mathcal{R}$ operator [14] was our primary theoretical goal. With Markov traces, the operator $B_{t}$ is independent of $t$, allowing the sum $C=\sum_{t\geq 0}\gamma^{t}P_{\mu}^{t}B_{t}$ to be reduced to $\sum_{t\geq 0}\gamma^{t}P_{c\mu}^{t}$ for the linear operator $P_{c\mu}\coloneqq\sum_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}P(s^{\prime}|s,a)\mu(a^{\prime}|s^{\prime})c(s^{\prime},a^{\prime})Q(s^{\prime},a^{\prime})$. The resulting geometric series can then be evaluated analytically: $(I-\gamma P_{c\mu})^{-1}$. This technique was used by [14]. In our proofs, we avoided the Markov assumption by directly analyzing the infinite summation $C$, which generally does not have a closed-form expression. We believe our work is the first to do this, and it should have far-reaching consequences for existing on- and off-policy algorithms (see Sections 4.3 and 5) as well as yet-undiscovered algorithms.

Arbitrary initialization of Q-function. Our proof of Theorem 2 permits any initialization of $Q_{0}$ in the control setting. In contrast, [14] made the assumption that $T_{\pi_{0}}Q_{0}-Q_{0}\geq 0$ in order to produce a lower bound on $\mathcal{R}Q_{k+1}-Q^{*}$. This is accomplished in practice by a pessimistic initialization of the Q-function: $Q_{0}(s,a)=-\norm{R}\mathbin{/}(1-\gamma)$, $\forall(s,a)\in\mathcal{S}\times\mathcal{A}$. Since $\mathcal{R}$ is a special case of our operator $\mathcal{M}$ where each $\beta(\mathcal{F}_{t})$ factors into Markov traces, we deduce as a corollary that Retrace and all other algorithms described by $\mathcal{R}$ do not require this pessimistic initialization for convergence.

Greedy-in-the-limit policies. Our requirement of greedy-in-the-limit target policies for the control setting is significantly less restrictive than the increasingly greedy policies proposed by [14]. We need only that $\lim_{k\to\infty}T_{\pi_{k}}Q_{k}=TQ_{k}$, and we do not force the sequence of target policies to satisfy $P_{\pi_{k+1}}Q_{k+1}\geq P_{\pi_{k}}Q_{k+1}$. This implies that the agent may target non-greedy policies for an arbitrarily long period of time, as long as the policies do eventually become arbitrarily close to the greedy policy. This could lead to faster learning since targeting greedy policies causes excessive trace cutting (e.g. Watkins’ Q($\lambda$)). Our greedy-in-the-limit policies are closely related to the Greedy-in-the-Limit with Infinite Exploration (GLIE) assumption of [19]; however, we are able to remove the need for infinite exploration by allowing an arbitrary sequence of behavior policies, as did [14]. Once again, our theory implies as a corollary that neither increasingly greedy policies nor the GLIE assumption are strictly necessary for the convergence of Retrace and other Markov algorithms.

Implementation with eligibility traces. The fact that the coefficient $\beta(\mathcal{F}_{t})$ does not generally factor into traces $c(s_{1},a_{1}),\dots,c(s_{t},a_{t})$ means that eligibility traces in the traditional sense are not possible. The problem occurs when the same state-action pair appears more than once in $\mathcal{F}_{t}$; afterwards, there does not exist a constant factor by which to decay the eligibility for that state-action pair that would produce the correct updates according to (3). We can rectify this by modifying the eligibility trace to remember each individual occurrence of the state-action pairs: a Non-Markov Eligibility Trace (see Algorithm 1). By tracking a separate eligibility for each repeated visitation, the algorithm is able to generate the correct coefficients $\beta(\mathcal{F}_{t})$ even though they do not factor into traces. In terms of computation, our algorithm is efficient when episodes are not extremely long, and is reminiscent of the practical linked-list implementation of the eligibility trace described by [23].

Online convergence. Algorithm 1 is presented as an online eligibility-trace algorithm. In practice, we expect that the updates will be calculated and accumulated offline, akin to the offline $\lambda$-return algorithm [23], for the sake of efficiency and compatibility with deep function approximation [4]. As such, the analysis of the online variant is beyond the scope of our work and we leave its convergence as an open question. Nevertheless, the fact that the expected $\mathcal{M}$ operator is convergent would make it surprising (although not impossible) that the online version diverges in the presence of zero-mean, finite-variance noise with appropriately annealed stepsizes [3].

Choice of coefficients $\beta(\mathcal{F}_{t})$. Our theorems guarantee convergence provided that $\beta(\mathcal{F}_{t})\leq\prod_{k=1}^{t}\rho_{k}$ for every $\mathcal{F}_{t}$. Of course, not all choices of $\beta$ will perform well in practice. At one extreme, when $\beta(\mathcal{F}_{t})=\prod_{k=1}^{t}\rho_{k}$ for every $\mathcal{F}_{t}$, we recover the standard IS estimator, which we know suffers from high variance and is often ineffectual. At the other extreme, if $\beta(\mathcal{F}_{t})<\prod_{k=1}^{t}\pi(a_{k}|s_{k})$ for every $\mathcal{F}_{t}$, then we have a method that cuts traces more than Tree Backup does; it seems unlikely that such a method would learn faster than Tree Backup, making it difficult to justify the extra complexity of the non-Markov coefficients in this case.

We therefore see that while it is important to control the overall variance of the coefficients $\beta(\mathcal{F}_{t})$, it is also important to maintain some minimum efficiency by avoiding unnecessary trace cuts, and to leverage the non-Markov capabilities of the operator. Effective algorithms will likely compute the full IS ratio product $\prod_{k=1}^{t}\rho_{k}$ first and then apply some nonlinear transformation (e.g. clipping) to control the variance. This ensures that the coefficients are cut only when necessary.

One final yet pertinent consideration is the discounted sum of coefficients $\sum_{t\geq 0}\gamma^{t}\beta(\mathcal{F}_{t})$. Roughly speaking, this sum represents the potential magnitude of an update to a state-action pair. If its value is extremely large along some trajectories with nonzero probability of occurrence, then the algorithm may not be stable. This suggests that a constant bound on each $\beta(\mathcal{F}_{t})$, or a recency heuristic that guarantees $\beta(\mathcal{F}_{t})\geq\beta(\mathcal{F}_{t+1})$, may be desirable to control the update magnitude.

In Section 2.2, we mentioned some algorithms that cannot be modeled by the $\mathcal{R}$ operator can, in fact, be modeled by the $\mathcal{M}$ operator. It remains to show that their coefficients always satisfy our condition of $\beta(\mathcal{F}_{t})\leq\prod_{k=1}^{t}\rho_{k}$ to prove that they converge according to Theorems 1 and 2.

Truncated IS. Clearly, $\min(d_{t},\prod_{k=1}^{t}\rho_{k})\leq\prod_{k=1}^{t}\rho_{k}$ for any choice of $d_{t}$, hence the algorithm converges.

Non-Markov Retrace. [14] define the traces for the algorithm as $c(s_{t},a_{t})=\lambda\min(1\mathbin{/}\beta(\mathcal{F}_{t-1}),\rho_{t})$, so $\beta(\mathcal{F}_{t-1})=\prod_{k=1}^{t-1}c(s_{k},a_{k})$. This means that

We can now prove by induction that the required bound always holds. Assume that $\beta(\mathcal{F}_{t-1})\leq\prod_{k=1}^{t-1}\rho_{k}$. Our base case is $\beta(\mathcal{F}_{0})=1$ by definition, which clearly holds. Then, by hypothesis,

and the non-Markov variant of Retrace therefore converges.