10.3 Off-policy actor-critic

The policy gradient methods that we have studied so far, including REINFORCE, QAC, and A2C, are all on-policy. The reason for this can be seen from the expression of the true gradient:

To use samples to approximate this true gradient, we must generate the action samples by following $\pi(\theta)$ . Hence, $\pi(\theta)$ is the behavior policy. Since $\pi(\theta)$ is also the target policy that we aim to improve, the policy gradient methods are on-policy.

In the case that we already have some samples generated by a given behavior policy, the policy gradient methods can still be applied to utilize these samples. To do that, we can employ a technique called importance sampling. It is worth mentioning that the importance sampling technique is not restricted to the field of reinforcement learning. It is a general technique for estimating expected values defined over one probability distribution using some samples drawn from another distribution.

10.3.1 Importance sampling

We next introduce the importance sampling technique. Consider a random variable $X \in \mathcal{X}$ . Suppose that $p_0(X)$ is a probability distribution. Our goal is to estimate $\mathbb{E}_{X \sim p_0}[X]$ . Suppose that we have some i.i.d. samples $\{x_i\}_{i=1}^n$ .

$\diamond$ First, if the samples $\{x_{i}\}_{i = 1}^{n}$ are generated by following $p_0$ , then the average value $\bar{x} = \frac{1}{n}\sum_{i = 1}^{n}x_{i}$ can be used to approximate $\mathbb{E}_{X\sim p_0}[X]$ because $\bar{x}$ is an unbiased estimate of $\mathbb{E}_{X\sim p_0}[X]$ and the estimation variance converges to zero as $n\to \infty$ (see the law of large numbers in Box 5.1 for more information).
$\diamond$ Second, consider a new scenario where the samples $\{x_{i}\}_{i = 1}^{n}$ are not generated by $p_0$ . Instead, they are generated by another distribution $p_1$ . Can we still use these samples to approximate $\mathbb{E}_{X\sim p_0}[X]$ ? The answer is yes. However, we can no longer use $\bar{x} = \frac{1}{n}\sum_{i = 1}^{n}x_{i}$ to approximate $\mathbb{E}_{X\sim p_0}[X]$ since $\bar{x}\approx \mathbb{E}_{X\sim p_1}[X]$ rather than $\mathbb{E}_{X\sim p_0}[X]$ .

In the second scenario, $\mathbb{E}_{X\sim p_0}[X]$ can be approximated based on the importance sampling technique. In particular, $\mathbb{E}_{X\sim p_0}[X]$ satisfies

Thus, estimating $\mathbb{E}_{X\sim p_0}[X]$ becomes the problem of estimating $\mathbb{E}_{X\sim p_1}[f(X)]$ . Let

Since $\bar{f}$ can effectively approximate $\mathbb{E}_{X\sim p_1}[f(X)]$ , it then follows from (10.9) that

Equation (10.10) suggests that $\mathbb{E}_{X\sim p_0}[X]$ can be approximated by a weighted average of $x_{i}$ . Here, $\frac{p_0(x_i)}{p_1(x_i)}$ is called the importance weight. When $p_1 = p_0$ , the importance weight is 1 and $\bar{f}$ becomes $\bar{x}$ . When $p_0(x_i)\geq p_1(x_i)$ , $x_{i}$ can be sampled more frequently by $p_0$ but less frequently by $p_1$ . In this case, the importance weight, which is greater than one, emphasizes the importance of this sample.

Some readers may ask the following question: while $p_0(x)$ is required in (10.10), why do we not directly calculate $\mathbb{E}_{X \sim p_0}[X]$ using its definition $\mathbb{E}_{X \sim p_0}[X] = \sum_{x \in \mathcal{X}} p_0(x)x$ ? The answer is as follows. To use the definition, we need to know either the analytical expression of $p_0$ or the value of $p_0(x)$ for every $x \in \mathcal{X}$ . However, it is difficult to obtain the analytical expression of $p_0$ when the distribution is represented by, for example, a neural network. It is also difficult to obtain the value of $p_0(x)$ for every $x \in \mathcal{X}$ when $\mathcal{X}$ is large. By contrast, (10.10) merely requires the values of $p_0(x_i)$ for some samples and is much easier to implement in practice.

An illustrative example

We next present an example to demonstrate the importance sampling technique. Consider $X \in \mathcal{X} \doteq \{+1, -1\}$ . Suppose that $p_0$ is a probability distribution satisfying

The expectation of $X$ over $p_0$ is

Suppose that $p_1$ is another distribution satisfying

The expectation of $X$ over $p_1$ is

Suppose that we have some samples $\{x_{i}\}$ drawn over $p_1$ . Our goal is to estimate $\mathbb{E}_{X \sim p_0}[X]$ using these samples. As shown in Figure 10.2, there are more samples of $+1$ than $-1$ . That is because $p_1(X = +1) = 0.8 > p_1(X = -1) = 0.2$ . If we directly calculate the average value $\sum_{i=1}^{n} x_i / n$ of the samples, this value converges to $\mathbb{E}_{X \sim p_1}[X] = 0.6$ (see the dotted line in Figure 10.2). By contrast, if we calculate the weighted average value as in (10.10), this value can successfully converge to $\mathbb{E}_{X \sim p_0}[X] = 0$ (see the solid line in Figure 10.2).

Figure 10.2: An example for demonstrating the importance sampling technique. Here, $X \in \{+1, -1\}$ and $p_0(X = +1) = p_0(X = -1) = 0.5$ . The samples are generated according to $p_1$ where $p_1(X = +1) = 0.8$ and $p_1(X = -1) = 0.2$ . The average of the samples converges to $E_{X \sim p_1}[X] = 0.6$ , but the weighted average calculated by the importance sampling technique in (10.10) converges to $E_{X \sim p_0}[X] = 0$ .

Finally, the distribution $p_1$ , which is used to generate samples, must satisfy that $p_1(x) \neq 0$ when $p_0(x) \neq 0$ . If $p_1(x) = 0$ while $p_0(x) \neq 0$ , the estimation result may be problematic. For example, if

then the samples generated by $p_1$ are all positive: $\{x_i\} = \{+1, +1, \ldots, +1\}$ . These samples cannot be used to correctly estimate $\mathbb{E}_{X \sim p_0}[X] = 0$ because

no matter how large $n$ is.

10.3.2 The off-policy policy gradient theorem

With the importance sampling technique, we are ready to present the off-policy policy gradient theorem. Suppose that $\beta$ is a behavior policy. Our goal is to use the samples generated by $\beta$ to learn a target policy $\pi$ that can maximize the following metric:

where $d_{\beta}$ is the stationary distribution under policy $\beta$ and $v_{\pi}$ is the state value under policy $\pi$ . The gradient of this metric is given in the following theorem.

Theorem 10.1 (Off-policy policy gradient theorem). In the discounted case where $\gamma \in (0,1)$ , the gradient of $J(\theta)$ is

where the state distribution $\rho$ is

where $\operatorname{Pr}_{\pi}(s|s') = \sum_{k=0}^{\infty} \gamma^{k}[P_{\pi}^{k}]_{s's} = [(I - \gamma P_{\pi})^{-1}]_{s's}$ is the discounted total probability of transitioning from $s'$ to $s$ under policy $\pi$ .

The gradient in (10.11) is similar to that in the on-policy case in Theorem 9.1, but there are two differences. The first difference is the importance weight. The second difference is that $A \sim \beta$ instead of $A \sim \pi$ . Therefore, we can use the action samples

generated by following $\beta$ to approximate the true gradient. The proof of the theorem is given in Box 10.2.

Box 10.2: Proof of Theorem 10.1

Since $d_{\beta}$ is independent of $\theta$ , the gradient of $J(\theta)$ satisfies

According to Lemma 9.2, the expression of $\nabla_{\theta}v_{\pi}(s)$ is

where $\operatorname{Pr}_{\pi}(s'|s) \doteq \sum_{k=0}^{\infty} \gamma^{k}[P_{\pi}^{k}]_{ss'} = [(I_{n} - \gamma P_{\pi})^{-1}]_{ss'}$ . Substituting (10.13) into (10.12) yields

By using the importance sampling technique, the above equation can be further rewritten as

The proof is complete. The above proof is similar to that of Theorem 9.1.

10.3.3 Algorithm description

Based on the off-policy policy gradient theorem, we are ready to present the off-policy actor-critic algorithm. Since the off-policy case is very similar to the on-policy case, we merely present some key steps.

First, the off-policy policy gradient is invariant to any additional baseline $b(s)$ . In particular, we have

because $\mathbb{E}\left[\frac{\pi(A|S,\theta)}{\beta(A|S)}\nabla_{\theta}\ln \pi (A|S,\theta)b(S)\right] = 0$ . To reduce the estimation variance, we can select the baseline as $b(S) = v_{\pi}(S)$ and obtain

The corresponding stochastic gradient-ascent algorithm is

where $\alpha_{\theta} > 0$ . Similar to the on-policy case, the advantage function $q_{t}(s,a) - v_{t}(s)$ can be replaced by the TD error. That is

Then, the algorithm becomes

The implementation of the off-policy actor-critic algorithm is summarized in Algorithm 10.3. As can be seen, the algorithm is the same as the advantage actor-critic algorithm except that an additional importance weight is included in both the critic and the actor. It must be noted that, in addition to the actor, the critic is also converted from on-policy to off-policy by the importance sampling technique. In fact, importance sampling is a general technique that can be applied to both policy-based and value-based algorithms. Finally, Algorithm 10.3 can be extended in various ways to incorporate more techniques such as eligibility traces [73].

Algorithm 10.3: Off-policy actor-critic based on importance sampling

Initialization: A given behavior policy $\beta (a|s)$ . A target policy $\pi (a|s,\theta_0)$ where $\theta_0$ is the initial parameter. A value function $v(s,w_0)$ where $w_{0}$ is the initial parameter. $\alpha_w,\alpha_\theta >0$ .

Goal: Learn an optimal policy to maximize $J(\theta)$ .

At time step $t$ in each episode, do

Generate $a_{t}$ following $\beta (s_t)$ and then observe $r_{t + 1},s_{t + 1}$

Advantage (TD error):

Actor (policy update):

Critic(valueupdate):