Off-Policy Actor-Critic Methods

The policy gradient methods that we have studied so far, including REINFORCE, QAC, and $\mathrm{A}2\mathrm{C}$, are all on-policy. The reason for this can be seen from the expression of the true gradient: $${\mathrm{\nabla }}_{\theta }J(\theta )={\mathbb{E}}_{S\sim \eta ,A\sim \pi }[{\mathrm{\nabla }}_{\theta }\ln \pi (A\mid S,{\theta }_t)(q_{\pi }(S,A)-v_{\pi }(S))].$$

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 a general technique for estimating expected values defined over one probability distribution using some samples drawn from another distribution.

Sources:

1. Shiyu Zhao. Chapter 10: Actor-Critic Methods. Mathematical Foundations of Reinforcement Learning.

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 ${\left\{x_i\right\}}_{i=1}^n$.

Suppose the samples ${\left\{x_i\right\}}_{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. ${\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 $${\mathbb{E}}_{X\sim p_0}[X]=\sum _{x\in \mathcal{X}}{p}_0(x)x=\sum _{x\in \mathcal{X}}{p}_1(x)\underset{f(x)}{\underbrace{\frac{p_0(x)}{p_1(x)}x}}={\mathbb{E}}_{X\sim p_1}[f(X)].$$

Thus, estimating ${\mathbb{E}}_{X\sim p_0}[X]$ becomes the problem of estimating ${\mathbb{E}}_{X\sim p_1}[f(X)]$. Let $$\overline{f}\doteq \frac{1}{n}\sum _{i=1}^{n}f\left(x_i\right)$$

Since $\overline{f}$ can effectively approximate ${\mathbb{E}}_{X\sim p_1}[f(X)]$, we obtain $${\mathbb{E}}_{X\sim p_0}[X]={\mathbb{E}}_{X\sim p_1}[f(X)]\approx \overline{f}=\frac{1}{n}\sum _{i=1}^{n}f\left(x_i\right)=\frac{1}{n}\sum _{i=1}^n\underset{\begin{array}{c}\text{ importance }\\ \text{ weight }\end{array}}{\underbrace{\frac{p_0\left(x_i\right)}{p_1\left(x_i\right)}}}{x}_i.$$

Here, $\frac{p_0\left(x_i\right)}{p_1\left(x_i\right)}$ is called the importance weight. When $p_1=p_0$, the importance weight is 1 and $\overline{f}$ becomes $\overline{x}$. When $p_0\left(x_i\right)\ge p_1\left(x_i\right),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.

You may ask that while $p_0(x)$ is required in $$\begin{array}{}\text{(1)}& \frac{1}{n}\sum _{i=1}^n\frac{p_0\left(x_i\right)}{p_1\left(x_i\right)}{x}_i,\end{array}$$ 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, $\text{(1)}$ merely requires the values of $p_0\left(x_i\right)$ for some samples and is much easier to implement in practice.

The off-policy policy gradient theorem

Algorithm 10.3

Like the previous on-policy case, we need to derive the policy gradient in the off-policy case.

• Suppose $\beta$ is the behavior policy that generates experience samples.

• Our aim is to use these samples to update a target policy $\pi$ that can minimize the metric $$J(\theta )=\sum _{s\in \mathcal{S}}{d}_{\beta }(s)v_{\pi }(s)={\mathbb{E}}_{S\sim d_{\beta }}[v_{\pi }(S)]$$ 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 $${\mathrm{\nabla }}_{\theta }J(\theta )={\mathbb{E}}_{S\sim \rho ,A\sim \beta }[\underset{\begin{array}{c}\text{ importance }\\ \text{ weight }\end{array}}{\underbrace{\frac{\pi (A\mid S,\theta )}{\beta (A\mid S)}}}{\mathrm{\nabla }}_{\theta }\ln \pi (A\mid S,\theta )q_{\pi }(S,A)],$$ where the state distribution $\rho$ is $$\rho (s)\doteq \sum _{s^{\prime }\in \mathcal{S}}{d}_{\beta }\left(s^{\prime }\right){\mathrm{Pr}}_{\pi }(s\mid s^{\prime }),s\in \mathcal{S},$$ where $${\mathrm{Pr}}_{\pi }(s\mid s^{\prime })=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{\left[P_{\pi }^k\right]}_{s^{\prime }s}={\left[{(I-\gamma P_{\pi })}^{-1}\right]}_{s^{\prime }s}$$ is the discounted total probability of transitioning from $s^{\prime }$ to $s$ under policy $\pi$.

The gradient ${\mathrm{\nabla }}_{\theta }J(\theta )$ 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 the appendix.

The off-policy policy gradient is also invariant to a baseline $b(s)$. In particular, we have

$${\mathrm{\nabla }}_{\theta }J(\theta )={\mathbb{E}}_{S\sim \rho ,A\sim \beta }[\frac{\pi (A\mid S,\theta )}{\beta (A\mid S)}{\mathrm{\nabla }}_{\theta }\ln \pi (A\mid S,\theta )(q_{\pi }(S,A)-b(S))]$$ because $$\mathbb{E}[\frac{\pi (A\mid S,\theta )}{\beta (A\mid S)}{\mathrm{\nabla }}_{\theta }\ln \pi (A\mid S,\theta )b(S)]=0.$$

To reduce the estimation variance, we select the baseline as $b(S)=v_{\pi }(S)$ as in A2C and obtain $${\mathrm{\nabla }}_{\theta }J(\theta )=\mathbb{E}[\frac{\pi (A\mid S,\theta )}{\beta (A\mid S)}{\mathrm{\nabla }}_{\theta }\ln \pi (A\mid S,\theta )(q_{\pi }(S,A)-v_{\pi }(S))]$$

The corresponding stochastic gradient-ascent algorithm is $${\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }\frac{\pi (a_t\mid s_t,{\theta }_t)}{\beta (a_t\mid s_t)}{\mathrm{\nabla }}_{\theta }\ln \pi (a_t\mid s_t,{\theta }_t)(q_t(s_t,a_t)-v_t\left(s_t\right))$$

Similar to the on-policy case, $$q_t(s_t,a_t)-v_t\left(s_t\right)\approx r_{t+1}+\gamma v_t\left(s_{t+1}\right)-v_t\left(s_t\right)\doteq {\delta }_t(s_t,a_t)$$

Then, the algorithm becomes $${\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }\frac{\pi (a_t\mid s_t,{\theta }_t)}{\beta (a_t\mid s_t)}{\mathrm{\nabla }}_{\theta }\ln \pi (a_t\mid s_t,{\theta }_t){\delta }_t(s_t,a_t)$$ and hence $${\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }\left(\frac{{\delta }_t(s_t,a_t)}{\beta (a_t\mid s_t)}\right){\mathrm{\nabla }}_{\theta }\pi (a_t\mid s_t,{\theta }_t)$$

Appendix

Proof of Theorem 10.1

Since $d_{\beta }$ is independent of $\theta$, the gradient of $J(\theta )$ satisfies $${\mathrm{\nabla }}_{\theta }J(\theta )={\mathrm{\nabla }}_{\theta }\sum _{s\in \mathcal{S}}{d}_{\beta }(s)v_{\pi }(s)=\sum _{s\in \mathcal{S}}{d}_{\beta }(s){\mathrm{\nabla }}_{\theta }{v}_{\pi }(s).$$

According to Lemma 9.2, the expression of ${\mathrm{\nabla }}_{\theta }{v}_{\pi }(s)$ is $${\mathrm{\nabla }}_{\theta }{v}_{\pi }(s)=\sum _{s^{\prime }\in \mathcal{S}}{\mathrm{Pr}}_{\pi }(s^{\prime }\mid s)\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }\pi (a\mid s^{\prime },\theta )q_{\pi }(s^{\prime },a),$$ where $${\mathrm{Pr}}_{\pi }(s^{\prime }\mid s)\doteq \sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{\left[P_{\pi }^k\right]}_{s{s}^{\prime }}={\left[{(I_n-\gamma P_{\pi })}^{-1}\right]}_{s{s}^{\prime }}$$ Substituting ${\mathrm{\nabla }}_{\theta }{v}_{\pi }(s)$ into $\sum _{s\in \mathcal{S}}{d}_{\beta }(s){\mathrm{\nabla }}_{\theta }{v}_{\pi }(s)$ yields $$\begin{array}{rl}{\mathrm{\nabla }}_{\theta }J(\theta )=\sum _{s\in \mathcal{S}}{d}_{\beta }(s){\mathrm{\nabla }}_{\theta }{v}_{\pi }(s)& =\sum _{s\in \mathcal{S}}{d}_{\beta }(s)\sum _{s^{\prime }\in \mathcal{S}}{\mathrm{Pr}}_{\pi }(s^{\prime }\mid s)\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }\pi (a\mid s^{\prime },\theta )q_{\pi }(s^{\prime },a)\\ & =\sum _{s^{\prime }\in \mathcal{S}}(\sum _{s\in \mathcal{S}}{d}_{\beta }(s){\mathrm{Pr}}_{\pi }(s^{\prime }\mid s))\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }\pi (a\mid s^{\prime },\theta )q_{\pi }(s^{\prime },a)\\ & \doteq \sum _{s^{\prime }\in \mathcal{S}}\rho \left(s^{\prime }\right)\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }\pi (a\mid s^{\prime },\theta )q_{\pi }(s^{\prime },a)\\ & =\sum _{s\in \mathcal{S}}\rho (s)\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }\pi (a\mid s,\theta )q_{\pi }(s,a)\text{ (change }{s}^{\prime }\text{ to }s\text{ ) }\\ & ={\mathbb{E}}_{S\sim \rho }[\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }\pi (a\mid S,\theta )q_{\pi }(S,a)],\end{array}$$

where the 3rd equation is because $$\rho (s)\doteq \sum _{s^{\prime }\in \mathcal{S}}{d}_{\beta }\left(s^{\prime }\right){\mathrm{Pr}}_{\pi }(s\mid s^{\prime }),s\in \mathcal{S}.$$

By using the importance sampling technique, the above equation can be further rewritten as $$ $$\begin{array}{rl}{\mathbb{E}}_{S\sim \rho }[\sum _{a\in \mathcal{A}}{\mathrm{\nabla }}_{\theta }\pi (a\mid S,\theta )q_{\pi }(S,a)]& ={\mathbb{E}}_{S\sim \rho }\left[\sum _{a\in \mathcal{A}}\beta (a\mid S)\frac{\pi (a\mid S,\theta )}{\beta (a\mid S)}\frac{{\mathrm{\nabla }}_{\theta }\pi (a\mid S,\theta )}{\pi (a\mid S,\theta )}{q}_{\pi }(S,a)\right]\\ & ={\mathbb{E}}_{S\sim \rho }[\sum _{a\in \mathcal{A}}\beta (a\mid S)\frac{\pi (a\mid S,\theta )}{\beta (a\mid S)}{\mathrm{\nabla }}_{\theta }\ln \pi (a\mid S,\theta )q_{\pi }(S,a)]\\ & ={\mathbb{E}}_{S\sim \rho ,A\sim \beta }[\frac{\pi (A\mid S,\theta )}{\beta (A\mid S)}{\mathrm{\nabla }}_{\theta }\ln \pi (A\mid S,\theta )q_{\pi }(S,A)].\end{array}$$

$$

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