【RL】Actor-Critic Methods

Lecture 10: Actor-Critic Methods

The simplest actor-critic (QAC)

回顾 policy 梯度的概念：

1、标量指标 J(\theta)，可以是 \bar{v}_{\pi} 或 \bar{r}_{\pi}。

2、最大化 J(\theta) 的梯度上升算法为：
\begin{aligned} \theta_{t+1}& =\theta_t+\alpha\nabla_\theta J(\theta_t) \\ &=\theta_t+\alpha\mathbb{E}_{S\sim\eta,A\sim\pi}\Big[\nabla_\theta\ln\pi(A|S,\theta_t)q_\pi(S,A)\Big] \end{aligned}
3、随机梯度上升算法是：
\theta_{t+1}=\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t){q_t(s_t,a_t)}
从以上算法中，可以看到“actor”和”critic“：

• 这个算法对应的是actor。
• 估计q_t(s, a)的算法对应于critic。

How to get q_t(s_t, a_t)?

• Monte Carlo learning：如果使用MC，相应的算法称为REINFORCE或Monte Carlo policy gradient。

• Temporal-difference learning：如果使用TD，这种算法通常称为actor-critic。
  

• critic 对应的是“SARSA+价值函数近似”。

• actor 对应于 policy 更新算法。

• 该算法是 on-policy的。由于 policy 是随机的，因此无需使用 \varepsilon-greedy 等技术。

• 这种特定的 actor-citric 算法有时称为 Q Actor-Critic (QAC)。

• 该算法揭示了 actor-citric 方法的核心思想。 它可以扩展以生成许多其他算法。

Advantage actor-critic (A2C)

Baseline invariance

属性：policy 梯度对于附加 baseline 是不变的：
\begin{aligned} \nabla_\theta J(\theta)& =\mathbb{E}_{S\sim\eta,A\sim\pi}\bigg[\nabla_\theta\ln\pi(A|S,\theta_t)q_\pi(S,A)\bigg] \\ &=\mathbb{E}_{S\sim\eta,A\sim\pi}\left[\nabla_\theta\ln\pi(A|S,\theta_t)(q_\pi(S,A)-{b(S)})\right] \end{aligned}
其中，附加 baseline b(S) 是 S 的标量函数。

有效性证明：
\mathbb{E}_{S\sim\eta,A\sim\pi}\Big[\nabla_\theta\ln\pi(A|S,\theta_t)b(S)\Big]=0
上式的具体细节为：
\begin{aligned} \mathbb{E}_{S\sim\eta,A\sim\pi}\left[\nabla_\theta\ln\pi(A|S,\theta_t)b(S)\right]& =\sum_{s\in\mathcal{S}}\eta(s)\sum_{a\in\mathcal{A}}\pi(a|s,\theta_t)\nabla_\theta\ln\pi(a|s,\theta_t)b(s) \\ &\begin{aligned}&=\sum_{s\in\mathcal{S}}\eta(s)\sum_{a\in\mathcal{A}}\nabla_\theta\pi(a|s,\theta_t)b(s)\end{aligned} \\ &=\sum_{s\in\mathcal{S}}\eta(s)b(s)\sum_{a\in\mathcal{A}}\nabla_\theta\pi(a|s,\theta_t) \\ &=\sum_{s\in\mathcal{S}}\eta(s)b(s)\nabla_\theta\sum_{a\in\mathcal{A}}\pi(a|s,\theta_t) \\ &\begin{aligned}=\sum_{s\in\mathcal{S}}\eta(s)b(s)\nabla_\theta1=0\end{aligned} \end{aligned}
因此，在添加 baseline 后，对 policy 的期望没有影响。

有用性证明：

设梯度为 \nabla_\theta J(\theta)=\mathbb{E}[X]，其中：
X(S,A)\doteq\nabla_\theta\ln\pi(A|S,\theta_t)[q_\pi(S,A)-b(S)]
可得：

\mathbb{E}[X] 对于 b(S)是不变的。

\text{var}(X) 对于 b(S) 来说是变化的。

因为 \operatorname{tr}[\operatorname{var}(X)]=\mathbb{E}[X^TX]-\bar{x}^T\bar{x}，且
\begin{gathered} \mathbb{E}[X^TX] =\mathbb{E}\left[(\nabla_\theta\ln\pi)^T(\nabla_\theta\ln\pi)(q_\pi(S,A)-b(S))^2\right] \\ =\mathbb{E}\left[\|\nabla_\theta\ln\pi\|^2(q_\pi(S,A)-b(S))^2\right] \end{gathered}
因此，目标为选择最佳 baseline b 以最小化 \text{var}(X)。

这样做的优势是：当使用随机样本来近似 \mathbb{E}[X] 时，估计方差也会很小。

可以最小化\text{var}(X) 的最佳基线是，对于任何 s \in S：
b^*(s)=\frac{\mathbb{E}_{A\sim\pi}[\|\nabla_\theta\ln\pi(A|s,\theta_t)\|^2q_\pi(s,A)]}{\mathbb{E}_{A\sim\pi}[\|\nabla_\theta\ln\pi(A|s,\theta_t)\|^2]}.
尽管这个 baseline 是最佳的，但它很复杂。

可以删除权重 \|\nabla_\theta\ln\pi(A|s,\theta_t)\|^2 并选择次优 baseline：
b(s)=\mathbb{E}_{A\sim\pi}[q_\pi(s,A)]=v_\pi(s)
这是 s 的 state value。

The algorithm of advantage actor-critic

当 b(s)=v_\pi(s) 时，

梯度上升算法是：
\begin{aligned} \theta_{t+1}& =\theta_t+\alpha\mathbb{E}\Big[\nabla_\theta\ln\pi(A|S,\theta_t)[q_\pi(S,A)-v_\pi(S)]\Big] \\ &\dot{=}\theta_t+\alpha\mathbb{E}\Big[\nabla_\theta\ln\pi(A|S,\theta_t){\delta_\pi(S,A)}\Big] \end{aligned}
其中：
\delta_\pi(S,A)\doteq q_\pi(S,A)-v_\pi(S)
该算法的随机版本是：
\begin{aligned} \theta_{\boldsymbol{t}+1}& \begin{aligned}=\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)[q_t(s_t,a_t)-v_t(s_t)]\end{aligned} \\ &=\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)\delta_t(s_t,a_t) \end{aligned}
此外，该算法可以重新表示为：
\begin{aligned} \theta_{t+1}& =\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)\delta_t(s_t,a_t) \\ &=\theta_t+\alpha\frac{\nabla_\theta\pi(a_t|s_t,\theta_t)}{\pi(a_t|s_t,\theta_t)}\delta_t(s_t,a_t) \\ &=\theta_t+\alpha\underbrace{\left(\frac{ {\delta_t(s_t,a_t)}}{\pi(a_t|s_t,\theta_t)}\right)}_{\textbf{step size}}\nabla_\theta\pi(a_t|s_t,\theta_t) \end{aligned}
步长与相对值 \delta_t 成正比，而不是与绝对值 q_t 成正比，更合理。

它仍然可以很好地平衡探索和开发。

此外，优势函数由 TD error 近似：
\delta_t=q_t(s_t,a_t)-v_t(s_t)\rightarrow r_{t+1}+\gamma v_t(s_{t+1})-v_t(s_t)
这个近似是合理的，因为：
\mathbb{E}[q_\pi(S,A)-v_\pi(S)|S=s_t,A=a_t]=\mathbb{E}\Big[R+\gamma v_\pi(S')-v_\pi(S)|S=s_t,A=a_t\Big]
好处：只需要一个网络来近似 v_{\pi}(s)，而不需要两个网络来近似 q_{\pi}(s, a) 和 v_{\pi}(s)。

这是on-policy的。 由于策略 \pi(\theta_t) 是随机的，因此无需使用 \varepsilon-greedy等技术。

Off-policy actor-critic

Illustrative examples

考虑一个随机变量 X \in \mathcal{X} = \{+1, −1\}。

如果 X 的概率分布为 p_0：
p_0(X=+1)=0.5,\quad p_0(X=-1)=0.5
那么X的期望是：
\mathbb{E}_{X\sim p_0}[X]=(+1)\cdot0.5+(-1)\cdot0.5=0.
使用样本\{x_i\}估计\mathbb{E}[X]：

Case 1 ：

根据 p_0 生成样本 \{x_i\}：
\mathbb{E}[x_i]=\mathbb{E}[X],\quad\text{var}[x_i]=\text{var}[X]
然后，平均值可以收敛到期望值：
\bar{x}=\frac1n\sum_{i=1}^nx_i\to\mathbb{E}[X],\quad\text{as }n\to\infty
因为：
\mathbb{E}[\bar{x}]=\mathbb{E}[X],\quad\mathrm{var}[\bar{x}]=\frac1n\mathrm{var}[X]
Case 2 ：

样本 \{x_i\} 是根据另一个分布 p_1 生成的：
p_1(X=+1)=0.8,\quad p_1(X=-1)=0.2
期望是：
\mathbb{E}_{X\sim p_1}[X]=(+1)\cdot0.8+(-1)\cdot0.2=0.6
如果使用样本的平均值，那么；
\bar{x}=\frac{1}{n}\sum_{i=1}^{n}x_{i}\rightarrow\mathbb{E}_{X\sim p_{1}}[X]=0.6\neq\mathbb{E}_{X\sim p_{0}}[X]
使用 \{x_i\} \sim p_1 来估计 \mathbb{E}_{X\sim p_0}[X] ：

估计 \mathbb{E}_{A\sim \pi}[*]，其中 \pi 是基于行为policy（behavior policy） \beta 样本的目标policy（target policy）。

可以通过使用重要性采样（importance sampling）技术来实现这一点。

Importance sampling

因为：
{\mathbb{E}_{X\sim p_0}[X]}=\sum_xp_0(x)x=\sum_xp_1(x)\underbrace{\frac{p_0(x)}{p_1(x)}x}_{f(x)}={\mathbb{E}_{X\sim p_1}[f(X)]}
因此，我们可以估计 \mathbb{E}_{X\sim p_1}[f(X)] 来估计 \mathbb{E}_{X\sim p_0}[X]。

使，
\bar{f}\doteq\frac1n\sum_{i=1}^nf(x_i),\quad\text{ where }x_i\sim p_1
那么：
\begin{gathered} \mathbb{E}_{X\sim p_1}[\bar{f}] =\mathbb{E}_{X\sim p_1}[f(X)] \\ \operatorname{var}_{X\sim_{p_{1}}}[\bar{f}] =\frac1n\mathrm{var}_{X\thicksim p_1}[f(X)] \end{gathered}
因此， \bar{f} 是 \mathbb{E}_{X\sim p_1}[f(X)] = \mathbb{E}_{X\sim p_0}[X] 的良好近似：
{\mathbb{E}_{X\sim p_0}[X]}\approx\overline{f}=\frac1n\sum_{i=1}^nf(x_i){=\frac1n\sum_{i=1}^n\frac{p_0(x_i)}{p_1(x_i)}x_i}
\frac{p_0(x_i)}{p_1(x_i)}被称为重要性分数（importance weight）。

如果 p_1(x_i) = p_0(x_i)，则重要性权重为 1，而 \bar{f} 变为 \bar{x}。

如果 p_0(x_i) ≥ p_1(x_i)，则 p_0 比 p_1 更频繁地对 x_i 进行采样。 重要性权重（>1）可以强调这个样本的重要性。

其适用于给定x很容易计算p_0(x)，但计算期望却很困难的情况。

例如，连续情况、p_0 的复杂表达或 p_0 不表达（例如，p_0 由神经网络表示）。

总结：

如果 \{ x_1 \} \sim p_1，

那么：
\begin{gathered} \bar{x}=\frac{1}{n}\sum_{i=1}^{n}x_{i}\rightarrow\mathbb{E}_{X\sim p_{1}}[X] \\ \begin{aligned}\bar{f}=\frac{1}{n}\sum_{i=1}^{n}\frac{p_{0}(x_{i})}{p_{1}(x_{i})}x_{i}\to\mathbb{E}_{ {X\sim p_{0}}}[X]\end{aligned} \end{gathered}

The theorem of off-policy policy gradient

与之前的 on-policy 情况一样，需要推导 off-policy 情况下的 policy 梯度。

假设 \beta 是生成经验样本的 behavior policy。

目标是使用这些样本来更新target policy \pi，以最小化指标：
J(\theta)=\sum_{s\in\mathcal{S}}d_\beta(s)v_\pi(s)=\mathbb{E}_{S\sim d_\beta}[v_\pi(S)]
其中 d_{\beta} 是policy \beta 下的平稳分布。

Theorem (Off-policy policy gradient theorem) ：

在 discounted 情况下，\gamma \in (0, 1)，J(\theta) 的梯度为：
\nabla_\theta J(\theta)=\mathbb{E}_{S\sim\rho,A\sim\beta}\left[\frac{\pi(A|S,\theta)}{\beta(A|S)}\nabla_\theta\ln\pi(A|S,\theta)q_\pi(S,A)\right]
其中 \beta 是behavior policy，\rho 是 state 分布。

The algorithm of off-policy actor-critic

off-policy 的 policy 梯度对于 baseline b(s) 也是不变的。

特别来说：
\nabla_\theta J(\theta)=\mathbb{E}_{S\sim\rho,A\sim\beta}\left[\frac{\pi(A|S,\theta)}{\beta(A|S)}\nabla_\theta\ln\pi(A|S,\theta)\left(q_\pi(S,A)-{b(S)}\right)\right]
为了减少估计方差，我们可以选择 baseline 为 b(S) = v_{\pi}(S) 并得到：
\nabla_\theta J(\theta)=\mathbb{E}\left[\frac{\pi(A|S,\theta)}{\beta(A|S)}\nabla_\theta\ln\pi(A|S,\theta)\big(q_\pi(S,A)-{v_\pi(S)}\big)\right]
相应的随机梯度上升算法是：
\theta_{t+1}=\theta_t+\alpha_\theta\frac{\pi(a_t|s_t,\theta_t)}{\beta(a_t|s_t)}\nabla_\theta\ln\pi(a_t|s_t,\theta_t)\big(q_t(s_t,a_t)-v_t(s_t)\big)
与 on-policy 案例类似：
q_t(s_t,a_t)-v_t(s_t)\approx r_{t+1}+\gamma v_t(s_{t+1})-v_t(s_t)\doteq\delta_t(s_t,a_t)
那么算法就变成了：
\theta_{t+1}=\theta_t+\alpha_\theta\frac{\pi(a_t|s_t,\theta_t)}{\beta(a_t|s_t)}\nabla_\theta\ln\pi(a_t|s_t,\theta_t)\delta_t(s_t,a_t)
因此：
\theta_{t+1}=\theta_t+\alpha_\theta\left(\frac{\delta_t(s_t,a_t)}{\beta(a_t|s_t)}\right)\nabla_\theta\pi(a_t|s_t,\theta_t)

Deterministic actor-critic (DPG)

The theorem of deterministic policy gradient

之前介绍的 policy 梯度定理仅适用于随机 policy 。

如果 policy 必须是确定性的，必须推导出一个新的 policy 梯度定理。

考虑 discounted 情况下平均 state value 的指标：
J(\theta)=\mathbb{E}[v_\mu(s)]=\sum_{s\in\mathcal{S}}d_0(s)v_\mu(s)
其中 d_0(s) 是满足 \sum_{s\in\mathcal{S}}d_0(s)=1 的概率分布。

d_0 被选择为独立于 \mu。 这种情况下的梯度更容易计算。

选择 d_0 有两种特殊但重要的情况:

第一个特殊情况是 d_0(s_0) = 1 且 d_0(s \ne s_0) = 0，其中 s_0 是感兴趣的特定起始 state。

第二个特殊情况是 d_0 是与 \mu 不同的 behavior policy 的平稳分布。

Theorem (Deterministic policy gradient theorem in the discounted case) ：

在折扣情况下，\gamma \in (0, 1)，J(\theta) 的梯度为：
\begin{aligned} \nabla_{\theta}J(\theta)& =\sum_{s\in\mathcal{S}}\rho_{\mu}(s)\nabla_{\theta}\mu(s)\left(\nabla_{a}q_{\mu}(s,a)\right)|_{a=\mu(s)} \\ &=\mathbb{E}_{S\sim\rho_{\mu}}\left[\nabla_{\theta}\mu(S)\big(\nabla_{a}q_{\mu}(S,a)\big)|_{a=\mu(S)}\right] \end{aligned}

The algorithm of deterministic actor-critic

基于 policy 梯度，最大化 J(\theta) 的梯度上升算法为：
\theta_{t+1}=\theta_{t}+\alpha_{\theta}\mathbb{E}_{S\sim\rho_{\mu}}\left[\nabla_{\theta}\mu(S)\big(\nabla_{a}q_{\mu}(S,a)\big)|_{a=\mu(S)}\right]
相应的随机梯度上升算法是：
\theta_{t+1}=\theta_t+\alpha_\theta\nabla_\theta\mu(s_t)\big(\nabla_aq_\mu(s_t,a)\big)|_{a=\mu(s_t)}

这是一种 off-policy 实现，其中 behavior policy \beta 可能与 \mu 不同。

\beta 也可以用 \mu+ \text{noise} 代替。

选择函数来表示 q(s, a, w)：

• 线性函数：\begin{aligned}q(s,a,w)=\phi^T(s,a)w\end{aligned}，其中 \phi(s, a) 是特征向量。
• 神经网络：深度确定性策略梯度（DDPG）方法。

Summary

• The simplest actor-critic
• Advantage actor-critic
• Off-policy actor-critic
• Deterministic actor-critic

以上内容为B站西湖大学智能无人系统 强化学习的数学原理 公开课笔记。