For its own sake or as part of a policy iteration scheme, evaluating policies is an important matter. This post is concerned with off-policy policy evaluation, or evaluating policies with data generated by others. The ambition is to provide a smooth progression towards the Retrace estimator and some of its extensions, with a focus on each operator’s properties and stochastic approximation variant.

Setting and notations

We work with finite MDPs $\mathcal{M}:=(\mathcal{S}, \mathcal{A}, p, r)$ for simplicity. All arguments extend to continuous settings. Under a discounted objective, we will develop policy evaluation operators for state-action values $q\in\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$ (exception made of Vtrace [6] which operates on state values). For any policy $\pi$ and $(s, a)\in\mathcal{S}\times\mathcal{A}$: $$ q_\lambda^\pi(s, a) := \mathbb{E}_{s,a}^\pi\big[\sum_{t\geq 1}\lambda^{t-1}r(s_t, a_t)\big]\;. $$ We recall below some state-action values vectorial notations, for completeness. The state-action values $q$ and the reward $r$ are considered as vectors in $\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$. For any stationary policy $\pi$, the right-stochastic matrix $\mathbf{P}_\pi\in\mathbb{R}^{(\mathrm{S}\times\mathrm{A})\times(\mathrm{S}\times\mathrm{A})}$ collects the transition kernel coupled with $\pi$; for any $(s,a,s^\prime,a^\prime) \in (\mathcal{S}\times\mathcal{A})^2$: $$ [\mathbf{P}_\pi]_{(s,a),(s’,a’)} := p(s’\vert s,a)\pi(a’\vert s’)\;. $$

On-policy warm-up

Bellman operator

Let $\pi$ some stationary policy. The Bellman evaluation operator writes, for $q\in\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$: $$ \begin{aligned} \mathcal{T}_\lambda^\pi : q &\mapsto \mathbf{r} + \lambda \mathbf{P}_\pi q \;. \end{aligned} $$ Analogously to the state-value case (see this post) $\mathcal{T}_\lambda^\pi$ defines a contractive operator (wrt the sup-norm) whose unique fixed point is $q_\lambda^\pi$. This guarantees that for any $q\in\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$ the fixed-point algorithm $q_{k+1} = \mathcal{T}_\lambda^\pi q_k$ converges linearly fast to $q_\lambda^\pi$—but applying this operator requires knowledge of the transition kernel $p$ and, for large state-action spaces, involves large matrix-vector products.

In practice, one resorts to stochastic approximations (à la Robbins-Monroe) of fixed point algorithms. Concretely, given some experience $(s_k, a_k, s_{k+1}, a_{k+1})$ and triggered by $\pi$ and some estimator $q\in\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$, denote $\delta_k^\pi := r(s_k, a_k) + \lambda q(s_{k+1}, a_{k+1}) - q(s_k, a_k)$ its associated temporal difference error (also known as the Bellman residual). Provided a step-size $\alpha>0$, the estimator $q$ can be updated according to the SARSA rule: $$ \tag{1} q(s_k, a_k) \leftarrow q(s_k, a_k) + \alpha\delta_k^\pi\;. $$

Multi-steps operators

The update rule exposed in (1) is essentially the SARSA algorithm. It looks at single transitions to update the current estimate $q_k$—we now extend it to handle sequences of experience. For any $n\geq 1$, we override our notations to write $\mathcal{T}_{\lambda,n}^\pi := (\mathcal{T}_\lambda^\pi)^n$. The operator $\mathcal{T}_{\lambda,n}^\pi$ is multisteps and expands over several transitions: $$ \tag{2} \mathcal{T}_{\lambda, n}^\pi q = \sum_{t=0}^{n-1} \lambda^t \mathbf{P}_\pi^t \mathbf{r} + \lambda^{n}\mathbf{P}_\pi^{n}q\;. $$ Observe that $q_\lambda^\pi$ is still a fixed-point for this operator. Further, $\mathcal{T}_{\lambda,n}^\pi$ contracts wrt. the sup-norm—which guarantees the uniqueness of the fixed point, and the healthiness of (sampled) fixed-point iterations.

For stochastic approximations, using larger values for $n$ reduces the bias (wrt the true $q_\lambda^\pi$) introduced by bootstrapping over the current estimator $q$. That comes with a price: updates that rely on longer trajectories have more variance. In the limit where $n\to\infty$ we will recover the (unbiased) Monte-Carlo estimator for $q_\lambda^\pi$.

Exponential averaging

To avoid settling for a single value for $n$ when using updates like (2), one can average them—typically, according to an exponential schedule. Going back to the Bellman operator; for any $\gamma\in[0,1)$ define: $$ \tag{3} \mathcal{T}_{\lambda,\gamma}^\pi := (1-\gamma)\sum_{n\geq 1} \gamma^{n-1} \mathcal{T}_{\lambda,n}^\pi\;. $$ This operator contracts wrt. sup-norm, and its unique fixed-point is still $q_\lambda^\pi$. A useful identity to analyse $\mathcal{T}_{\lambda,\gamma}^\pi$ is given in (4) and holds for any $q\in\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$. It is direct from this expression that picking $\gamma=0$ falls back to the single-step operator $\mathcal{T}_\lambda^\pi$, while $\gamma=1$ yields the Monte-Carlo estimator.

$$ \tag{4} \mathcal{T}_{\lambda, \gamma}^\pi q = q + (\mathbf{I}-\lambda\gamma\mathbf{P}_\pi)^{-1}(\mathcal{T}_\lambda^\pi q -q)\;. $$

The state-action indexed version of (4) will be useful later; it writes that for any $(s, a)\in\mathcal{S}\times\mathcal{A}$: $$ \mathcal{T}_{\lambda, \gamma}^\pi q(s, a) = q(s, a) + \mathbb{E}_{s, a}^\pi\big[\sum_{t\geq 0}\lambda^t\gamma^t \big(r_t + \lambda q(s_{t+1}, a_{t+1}) - q(s_t, a_t)\big)\big]\;. $$ The associated stochastic approximation algorithm writes $ q(s_k, a_k) \leftarrow q(s_k, a_k) + \alpha\sum_{t\geq k} (\lambda\gamma)^{t-k}\delta_t^\pi\;. $ It assumes access to an infinite sequence—or at least one that reaches an absorbing state. This implementation is known as the forward view of SARSA($\lambda$) and is hardly practical. Much more appropriate is its backward view alternative, which uses eligibility traces to update the estimator (not covered here).

Importance Sampling

So far we assumed online access to experience generated by the policy $\pi$ we wish to evaluate. Below, we consider the off-policy setting: experience is generated instead by a fixed behavioural policy $\mu$. Observe that Monte-Carlo estimators can easily be provided in that off-policy context. Indeed, under some regularity assumptions, trajectory-level importance sampling yields:

$$ q_\lambda^\pi(s, a) = \mathbb{E}_{s,a}^\mu\Big[\sum_{t\geq 1} \lambda^{t-1}r(s_t, a_t)\prod_{j=2}^t\frac{\pi(a_j\vert s_j)}{\mu(a_j\vert s_j)} \Big]\;, $$ with the convention that an empty product resolves to the constant $1$ (at $t=1$).

This estimator is unbiased but its variance grows exponentially fast wrt. the horizon. The operators introduced in the next sections precisely aim at taming this variance by bootstrapping and/or clipping the per-step importance ratios. We will discuss several approaches; for each we will follow the same protocol: introduce an off-policy operator, show that $q_\lambda^\pi$ is its unique fixed-point (uniqueness being guaranteed by each operator’s contractive nature), and derive its stochastic approximation before discussing some key properties.

Off-policy $Q(\lambda)$ [3]

Our starting point for the off-policy $Q(\lambda)$ operator is the on-policy exponential average formula of (4). The idea for this operator is to ‘ignore’ that trajectories are sampled by $\mu$ and keep the Bellman residual of $\pi$ without any probabilistic correction. Concretely, for any $\gamma\in[0, 1)$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$: $$ \tag{5} \mathcal{Q}_{\lambda, \gamma}^{{\color{black}\pi}, {\color{black}\mu}} q(s, a) := q(s, a) + \mathbb{E}_{s, a}^{\color{black}\mu}\big[\sum_{t\geq 0} \gamma^t\lambda^t \big(r_t + \lambda\mathbb{E}_{a^\prime\sim{\color{black}\pi}(s_{t+1})}[q(s_{t+1}, a^\prime)] - q(s_t, a_t)\big)\big]\;. $$ The equivalent vectorial form (5) can be also compared to the on-policy case of (4); observe that the kernel $\mathbf{P}_\pi$ is replaced by $\mathbf{P}_\mu$—the one we can actually use for sampling experience under the off-policy constraint: $$ \tag{6} \mathcal{Q}_{\lambda, \gamma}^{\pi, \mu} q = q + (\mathbf{I}-\lambda\gamma\mathbf{P}_\mu)^{-1}(\mathcal{T}_\lambda^\pi q -q)\;. $$

It is direct from (6) that $q_\lambda^\pi$ is a fixed-point of $\mathcal{Q}_{\lambda, \gamma}^{\pi, \mu}$. Contraction, however, is more delicate: it only holds when $\pi$ and $\mu$ are close enough—where ’enough’ is captured by the discount factor $\lambda$. This is not surprising given that no effort was made to correct the bias introduced by following $\mu$ (via, e.g., importance sampling). Concretely, if $\pi$ and $\mu$ satisfy $\max_{s}\| \pi(s) - \mu(s) \|_1 < \frac{1-\lambda}{\lambda\gamma}$ then for any $q_1, q_2 \in\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$: $$ \| \mathcal{Q}_{\lambda, \gamma}^{\pi, \mu}q_1 - \mathcal{Q}_{\lambda, \gamma}^{\pi, \mu}q_2\|_\infty < \|q_1-q_2\|_\infty\;. $$

Altogether we get the guarantee that when the behavioural policy resembles the target policy, the operator $\mathcal{Q}_{\lambda, \gamma}^{\pi, \mu}$ and a fixed-point algorithm will lead us to the computation of its fixed point $q_\lambda^\pi$. Regarding the stochastic approximation, let us denote $\delta_k^{\pi} = r_k + \lambda\mathbb{E}_{a\sim\pi(s_{k+1})} q(s_{k+1}, a) - q(s_k, a_k)$. The forward view writes: $$ q(s_k, a_k) \leftarrow q(s_k, a_k) + \alpha \sum_{t\geq k} \gamma^{t-k} \lambda^{t-k} \delta_t^\pi \;. $$ This is an immediate consequence of (5). Again, observe the resemblance with the on-policy SARSA($\lambda$) update—but with the trace generated by $\mu$ and the Bellman residual taken under $\pi$.

Retrace [4]

The main issue with $Q(\lambda)$ is that it is unsafe: contraction is only guaranteed when $\pi$ and $\mu$ are close enough. Whenever the proximity condition is not checked, we lose convergence guarantees. The Retrace operator aims at getting the best-of-both-worlds from the importance sampling and $Q(\lambda)$ approaches. We introduce Retrace directly in the same exponential-average form as (5): $$ \tag{7} \mathcal{R}_{\lambda, \gamma}^{\pi, \mu} q(s, a) := q(s, a) + \mathbb{E}_{s, a}^{\mu}\big[\sum_{t\geq 0} \lambda^t \big(\prod_{s=1}^t c^\gamma_s\big)\big(r_t + \lambda\mathbb{E}_{a^\prime\sim \pi(s_{t+1})}[q(s_{t+1}, a^\prime)] - q(s_t, a_t)\big)\big]\;, $$ where $c^\gamma_t := \gamma \min(1, \pi(a_t\vert s_t)/\mu(a_t\vert s_t))$, and where by convention the empty product equals 1 (for $t=0$). Before interpreting the operator’s definition, we start with a few key properties; first, that it contracts wrt the supremum norm and without any condition between $\pi$ and $\mu$. For any $q_1, q_2\in\mathbb{R}^{\mathrm{S}\times\mathrm{A}}$: $$ \| \mathcal{R}_{\lambda, \gamma}^{\pi, \mu} q_1 - \mathcal{R}_{\lambda, \gamma}^{\pi, \mu} q_2 \|_\infty < \| q_1-q_2\|_\infty\;. $$ Second, that $q_\lambda^\pi$ is its (unique) fixed point—which clears the (stochastic) fixed-point algorithms’ healthiness.

Observe the contrast between (5) and (7); the ‘rectified’ Bellman error at round $t$ is now multiplicatively weighted by $\prod_{s=1}^t c^\gamma_s$. This multiplicative correction matches the $\gamma^t$ factor of $Q(\lambda)$ whenever the importance ratios are not clipped by the $\text{min}$ operator; otherwise, the importance ratio kicks in to softly ‘cut’ the trace. That importance ratios are clipped is a classical way of reducing variance, by trading it off with bias. The forward view of the associated stochastic approximation writes: $$ q(s_k, a_k) \leftarrow q(s_k, a_k) + \alpha \sum_{t\geq k} \lambda^{t-k}\big(\prod_{u=k+1}^t c_u^\gamma\big) \delta_t^\pi\;, $$ with $\delta_t^\pi$ the same Bellman residual as for $Q(\lambda)$. This is an immediate consequence of (7).

Qtrace [5]

Both $Q(\lambda)$ and Retrace require sampling new actions from $\pi$—either to materialise $\mathbb{E}_{a\sim\pi(s)}[q(s, a)]$ or an unbiased estimator thereof. To avoid this and rely only on the experience gathered by $\mu$, one can further rely on importance sampling—with some clipping to control variance. This gives rise to the Qtrace estimator: $$ \mathcal{K}_{\lambda, \gamma}^{\pi, \mu} q (s, a) := q(s, a) + \mathbb{E}_{s, a}^{\pi, \mu} \big[\sum_{t\geq 0} \lambda^t \big(\prod_{s=1}^t c_s^\gamma\big) \big(r_t + \lambda \rho_{t+1} q(s_{t+1}, a_{t+1}) - q(s_t, a_t) \big)\big]\;, $$ with $\rho_t = \min(\rho, \pi(a_{t}\vert s_{t})/\mu(a_{t}\vert s_{t}))$ and $\rho>1$. Observe that for $\rho\to\infty$, we recover essentially the Retrace operator (the stochastic approximation will differ because of the importance ratio, though). While this operator does have a fixed point, it is not the value function of an actual policy—and clearly not $q_\lambda^\pi$. The authors of [5] provide upper-bounds on the error between said fixed-point and the actual $q_\lambda^\pi$ we are after.

Vtrace [6]

Surely a better way to appreciate Qtrace is via its predecessor Vtrace—which is a state value function operator. Reusing notations, the operator writes for any $v\in\mathbb{R}^\mathrm{S}$: $$ \mathcal{V}_{\lambda, \gamma}^{\pi, \mu}v(s) = v(s) + \mathbb{E}_s^\mu\big[\sum_{t\geq 0} \lambda^t \big(\prod_{s=1}^{t-1} c_s^\gamma\big)\rho_t\big(r_t + \lambda v(s_{t+1}) - v(s_t)\big) \big]\;. $$ Similar to Qtrace, its unique fixed-point is not $v_\lambda^\pi$—but the value function $v_\lambda^{\pi_\rho}$ of the policy $\pi_\rho$ that interpolates between $\mu$ and $\pi$; with $\eta(s)$ the suitable normalisation constant, for any $s, a\in\mathcal{S}\times\mathcal{A}$: $$ \pi_\rho(a\vert s) := \eta(s) \min(\rho \mu(a\vert s), \pi(a\vert s))\;. $$ For $\rho\to\infty$, we recover a state-value version of Retrace, and the fixed-point policy $\pi_\rho$ collapses to $\pi$. At the other side of the spectrum, for $\rho\to 0$, $\pi_\rho$ falls back to $\mu$ (to see this, materialise the normalising constant $\eta$).

Clearly, in the general case $\rho \in (0, +\infty)$ this falls short of our goal, which was to estimate $q_\lambda^\pi$. To understand the practical use of Vtrace, it needs to be replaced in a broader policy iteration context (in the case of [6] , the Impala algorithm). On top of the evaluation performed by Vtrace, a policy improvement step can prefer to improve over the safer $\pi_\rho$—slightly ’less off-policy’ than $\pi$, wrt the behavioural $\mu$.

Summary

The off-policy operators covered in this post can be compared along a handful of axes: the trace factor $c_t$, the fixed point they target, whether contraction holds unconditionally, and whether the stochastic approximation requires sampling from $\pi$. We summarise the key differences in the table below.

References