# Off-Policy Actor-Critic

> [Off-Policy Actor-Critic](https://arxiv.org/pdf/1205.4839.pdf)

本文提出了第一个off-policy强化学习的actor-critic算法。我们的算法是在线的和增量的，并且每个时间步长的复杂度与学习的权重数量成线性比例。前期的actor-critic算法的局限于on-policy环境，没有利用off-policy的时间差分梯度的优势。off-policy技术，如Greedy-GQ，能够在跟踪和从另一个(行为)策略获取数据的同时学习目标策略。对于许多问题，无论如何，actor-critic方法更实用，因为它们清晰的代表了策略；因此，该策略可以是是随机的，并且可利用大的动作空间。本文阐述了如何将off-policy学习的通用性和学习潜力与actor-critic方法在行动选择中的灵活性相结合，这种灵活性是由actor-critic的方法决定的。我们导出了一个包含资格迹的线性时间和空间复杂度的算法，证明了在类似于以前的off-policy算法的假设下的收敛性，并且在标准强化学习基准问题上，实验显示了比现有算法更好或的性能。

最着名的off-policy方法是Q-learning。 然而，虽然Q-Learnings保证收敛到最优的非线性（非近似）情况，但在使用线性函数逼近时可能会有所不同（Baird，1995）。最小二乘法，如LSTD和LSPI 可以使用off-policy和线性函数，但是计算成本昂贵；它们的复杂度与特征和权重的数量成比例。 最近，这些问题已经被新的梯度-TD（时间差）方法所解决，例如Greedy-GQ，它们具有线性复杂性和收敛性， 具有函数逼近的off-policy学习下。

所有的动作值方法，包括梯度TD方法，如Greedy-GQ，都有三个重要的局限性。首先，他们的目标政策是确定性的，而许多问题都有随机的最优政策，其次，对于较大的动作空间来说，找到关于动作值函数的贪婪动作变得有问题。最后，动作值函数的小变化会导致策略的大变化，这给收敛性证明和一些实时应用带来困难。避免行动价值方法局限性的标准方法是使用策略梯度算法，例如actor-critic。

## 方法

### Off-PAC

价值函数定义

$$V^{\pi, \gamma}(s)=\mathrm{E}\left\[r\_{t+1}+\ldots+r\_{t+T} | s\_{t}=s\right] \forall s \in \mathcal{S}$$

动作值函数定义

$$\begin{array}{l}{Q^{\pi, \gamma}(s, a)=} \ {\sum\_{s^{\prime} \in S} P\left(s^{\prime} | s, a\right)\left\[\mathcal{R}\left(s, a, s^{\prime}\right)+\gamma\left(s^{\prime}\right) V^{\pi, \gamma}\left(s^{\prime}\right)\right]}\end{array}$$

我们的学习目标是找出一个能最大化下面函数的策略 $$u$$

$$J\_{\gamma}(\mathbf{u})=\sum\_{s \in \mathcal{S}} d^{b}(s) V^{\pi\_{\mathbf{u}}, \gamma}(s)$$

其中 $$d^{b}(s)=\lim *{t \rightarrow \infty} P\left(s*{t}=s | s\_{0}, b\right)$$ ，即在动作 $$b$$ 和初始状态 $$s\_0$$ 下的极限概率分布。用 $$d^{b}$$加权的原因是，在off-policy中，数据是从行为策略的分布获得。

#### The Critic: Policy Evaluation

用线性函数近似价值函数： $$\hat{V}(s)=\mathbf{v}^{\mathbf{T}} \mathbf{x}\_{s}$$

λ-weighted mean-squared projected Bellman error

$$\operatorname{MSPBE}(\mathbf{v})=\left|\hat{V}-\Pi T\_{\pi}^{\lambda, \gamma} \hat{V}\right|\_{D}^{2}$$

其中$$\hat{V}=X \mathbf{v}$$ ， $$X$$ 的每一行都是一个样本， $$λ$$ 是资格迹权重参数， $$D$$ 是一个矩阵（对角元素为$$d^{b}$$）， $$Π$$ 是一个投影操作， $$T\_{\pi}^{\lambda, \gamma}$$ 是λ-weighted Bellman operator(对于终止概率为 $$γ$$ 的策略 $$π$$ )。在线性情况下， $$\Pi=X\left(X^{\top} D X\right)^{-1} X^{\top} D$$ 。

请参考 $$GTD(λ)$$ 算法

#### Off-policy Policy-gradient Theorem

策略梯度为

$$\mathbf{u}*{t+1}-\mathbf{u}*{t} \approx \alpha\_{u, t} \nabla\_{\mathbf{u}} J\_{\gamma}\left(\mathbf{u}\_{t}\right)$$

展开得到

$$\begin{aligned} \nabla\_{\mathbf{u}} J\_{\gamma}(\mathbf{u})=& \nabla\_{\mathbf{u}}\left\[\sum\_{s \in \mathcal{S}} d^{b}(s) \sum\_{a \in \mathcal{A}} \pi(a | s) Q^{\pi, \gamma}(s, a)\right] \\=& \sum\_{s \in \mathcal{S}} d^{b}(s) \sum\_{a \in \mathcal{A}}\left\[\nabla\_{\mathbf{u}} \pi(a | s) Q^{\pi, \gamma}(s, a)\right.\ &+\pi(a | s) \nabla\_{\mathbf{u}} Q^{\pi, \gamma}(s, a) ] \end{aligned}$$

$$\nabla\_{\mathbf{u}} Q^{\pi, \gamma}(s, a)$$ 很难估计，所以忽略掉，得到近似梯度

$$\nabla\_{\mathbf{u}} J\_{\gamma}(\mathbf{u}) \approx \mathbf{g}(\mathbf{u})=\sum\_{s \in \mathcal{S}} d^{b}(s) \sum\_{a \in \mathcal{A}} \nabla\_{\mathbf{u}} \pi(a | s) Q^{\pi, \gamma}(s, a)$$

下面的定理证明了这个近似（证明见原文附录）

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-LaNII8X8nnM6zkOZPLK%2F-LaNIJTo5ZdnObM1HbmL%2Fimage%20\(6\).png?generation=1553038397602389\&alt=media)

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-LaNII8X8nnM6zkOZPLK%2F-LaNIJTqboSFVUuidy0s%2Fimage%20\(26\).png?generation=1553038397013496\&alt=media)

#### The Actor: Incremental Update Algorithm with Eligibility Traces

我们现在使用行为策略中的观察样本推导出增量更新算法，首先写出近似策略梯度的期望形式

$$
\begin{aligned} \mathbf{g}(\mathbf{u}) &=\mathrm{E}\left\[\sum\_{a \in \mathcal{A}} \nabla\_{\mathbf{u}} \pi(a | s) Q^{\pi, \gamma}(s, a) | s \sim d^{b}\right] \ &=\mathrm{E}\left\[\sum\_{a \in \mathcal{A}} b(a | s) \frac{\pi(a | s)}{b(a | s)} \frac{\nabla\_{\mathbf{u}} \pi(a | s)}{\pi(a | s)} Q^{\pi, \gamma}(s, a) | s \sim d^{b}\right] \ &=\mathrm{E}\left\[\rho(s, a) \psi(s, a) Q^{\pi, \gamma}(s, a) | s \sim d^{b}, a \sim b(\cdot | s)\right] \ &=\mathrm{E}*{b}\left\[\rho\left(s*{t}, a\_{t}\right) \psi\left(s\_{t}, a\_{t}\right) Q^{\pi, \gamma}\left(s\_{t}, a\_{t}\right)\right] \end{aligned}
$$

其中 $$\rho(s, a)=\frac{\pi(a | s)}{b(a | s)}, \psi(s, a)=\frac{\nabla\_{\mathbf{u}} \pi(a | s)}{\pi(a | s)}$$ ，这里引入了新的符号 $$\mathrm{E}\_{b}\[\cdot]$$期望 来隐含地表示条件，所有随机变量(按时间步长索引)都是从行为策略下它们的极限平稳分布中提取出来的。然后减去一个baseline减小方差：

$$\mathbf{g}(\mathbf{u})=\mathrm{E}*{b}\left\[\rho\left(s*{t}, a\_{t}\right) \psi\left(s\_{t}, a\_{t}\right)\left(Q^{\pi, \gamma}\left(s\_{t}, a\_{t}\right)-\hat{V}\left(s\_{t}\right)\right)\right]$$

下一步是替换动作值

$$\mathbf{g}(\mathbf{u}) \approx \widehat{\mathbf{g}(\mathbf{u})}=\mathrm{E}*{b}\left\[\rho\left(s*{t}, a\_{t}\right) \psi\left(s\_{t}, a\_{t}\right)\left(R\_{t}^{\lambda}-\hat{V}\left(s\_{t}\right)\right)\right]$$

其中off-policy λ-return定义的 $$R\_{t}^{\lambda}$$ 为：

$$\begin{aligned} R\_{t}^{\lambda}=& r\_{t+1}+(1-\lambda) \gamma\left(s\_{t+1}\right) \hat{V}\left(s\_{t+1}\right) \ &+\lambda \gamma\left(s\_{t+1}\right) \rho\left(s\_{t+1}, a\_{t+1}\right) R\_{t+1}^{\lambda} \end{aligned}$$

这就是前向视角的Off-PAC

### Convergence Proofs

请参考原文附录

## 伪代码

为了实现前面描述的算法，这里转换为后向视角，关键的一步是

$$\mathrm{E}*{b}\left\[\rho\left(s*{t}, a\_{t}\right) \psi\left(s\_{t}, a\_{t}\right)\left(R\_{t}^{\lambda}-\hat{V}\left(s\_{t}\right)\right)\right]=\mathrm{E}*{b}\left\[\delta*{t} \mathrm{e}\_{t}\right]$$

其中 $$\delta\_{t}=r\_{t+1}+\gamma\left(s\_{t+1}\right) \hat{V}\left(s\_{t+1}\right)-\hat{V}\left(s\_{t}\right)$$ 是时间差分误差， $$\mathbf{e}*{t} \in \mathbb{R}^{N*{\mathbf{u}}}$$ 是资格迹，由下式更新

$$\mathbf{e}*{t}=\rho\left(s*{t}, a\_{t}\right)\left(\psi\left(s\_{t}, a\_{t}\right)+\lambda \mathbf{e}\_{t-1}\right)$$

然后我们可以得到： $$\mathbf{u}*{t+1}-\mathbf{u}*{t}=\alpha\_{u, t} \delta\_{t} \mathbf{e}\_{t}$$

证明见原文附录或者参考资格迹的相关教程

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-LaNII8X8nnM6zkOZPLK%2F-LaNIJU-YWqrNZwgQcAc%2Fimage%20\(61\).png?generation=1553038397039634\&alt=media)