谈 RL，一个肯定绕不过去的话题就是 PPO，后续很多强化学习算法都是在 PPO 之上的改进，况且 PPO 本身的确也是介绍 RL 的良好例子。所以我们先讲 PPO。

强化学习与其目标

强化学习的目的在于让机器自行探索和学习一个策略 π\pi，能够根据当前环境做出决策，得到最多的收益。

我们将环境描述为状态集合 SS，策略可以反映为在状态间转移的概率矩阵 PP，这就形成了一个马尔科夫链。记状态 ss 上执行动作 aa 的奖励为 r(s,a)r(s,a)，定义γ\gamma为衰减系数，那策略的目标就是最大化从起始状态 t 出发的最终收益

Gt=∑i=0+∞γirt+iG_t=\sum_{i=0}^{+\infty} \gamma^i r_{t+i}

继续定义节点价值函数 Vπ(St)V^\pi(S_t)，反映在策略 \pi 下从节点 S_t 出发能获取的价值和

Vπ(s)=E(Gs∣St=s)\begin{aligned} V^\pi(s)&=\mathbb E(G_s \mid S_t=s) \\ \end{aligned}

以及在 s 上执行动作 a 的动作价值函数 Qπ(s,a)Q^\pi(s,a)

即当前执行动作的收益，加上可能转移到的新状态的状态价值。

Qπ(s,a)=r(s,a)+γ∑ap(s′∣s,a)Vπ(s′)Q^\pi(s,a)=r(s,a)+\gamma\sum_{a}p(s' \mid s,a)V^\pi(s')

另外，也可得Vπ(s)V^\pi(s)的一种表示

即在当前节点执行各个动作的动作价值期望

Vπ(s)=∑aπ(a∣s)Qπ(s,a)V^\pi(s)=\sum_a \pi(a|s)Q^\pi(s,a)

由此我们能够进一步得到两个递推公式，这个递推公式被称为贝尔曼期望方程，可以用来计算两个函数的值

Vπ(s)=Eπ(rt+γVπ(St+1)∣St=s)=∑aπ(a∣s)(r(s,a)+γ∑s′p(s′∣s,a)Vπ(s′))Qπ(s,a)=Eπ(rt+γQπ(St+1,At+1)∣St=s,At=a)=r(s,a)+∑s′p(s′∣s,a)∑a′π(a′∣s′)Qπ(s′,a′)\begin{aligned} V^\pi(s)&=\mathbb E_\pi\left(r_t+\gamma V^\pi(S_{t+1}) \mid S_t=s\right) \\ &=\sum_a\pi(a \mid s)\left( r(s,a)+\gamma\sum_{s'}p(s' \mid s,a)V^\pi(s') \right) \\ Q^\pi(s,a)&=\mathbb E_\pi(r_t+\gamma Q^\pi(S_{t+1},A_{t+1}) \mid S_t=s,A_t=a) \\ &=r(s,a)+\sum_{s'}p(s' \mid s,a)\sum_{a'}\pi(a' \mid s')Q^\pi(s',a') \end{aligned}

强化学习的优化目标是找到一个最优策略 π∗\pi^*，该策略下任何节点的价值都高于其他策略的。最优策略对应两个最优价值函数

V∗(s)=max⁡πVπ(s),∀sQ∗(s,a)=max⁡πQπ(s,a),∀s,a\begin{aligned} V^*(s)&=\max_\pi V^\pi(s), && \forall s \\ Q^*(s,a)&=\max_\pi Q^\pi(s,a), && \forall s,a \end{aligned}

因此又有贝尔曼最优价值函数

V∗(s)=max⁡aQ(s,a)Q∗(s,a)=r(s,a)+γ∑s′p(s′∣s,a)V∗(s′)\begin{aligned} V^*(s) &= \max_{a} Q(s,a) \\ Q^*(s,a) &= r(s,a)+ \gamma \sum_{s'}p(s' \mid s,a)V^*(s') \end{aligned}

现在，将二者继续展开，得到相互独立的递推式

V∗(s)=max⁡a(r(s,a)+γ∑s′p(s′∣s,a)V∗(s′))Q∗(s,a)=r(s,a)+γ∑s′p(s′∣s,a)max⁡a′Q∗(s′,a′)\begin{aligned} V^*(s)&=\max_a\left( r(s,a)+\gamma\sum_{s'}p(s' \mid s,a)V^*(s') \right) \\ Q^*(s,a)&=r(s,a)+\gamma\sum_{s'}p(s' \mid s,a)\max_{a'}Q^*(s',a') \end{aligned}

这个递推式就已经可以拿来求解最优价值函数并导出最优策略了。

环境已知：使用动态规划计算

鉴于本文并不是强化学习的入门文章，所以只是简单提及一下，以便有相关背景的人快速理解。

如果 PP 已知，我们能直接求解。

一种是计算 VπV^\pi，然后基于 VπV^\pi 更新策略。这被称作策略评估。上式视作子问题+转移方程后，可以迅速得到

Vk+1(s)=∑aπ(a∣s)(r(s,a)+γ∑s′p(s′∣s,a)Vk(s′))V^{k+1}(s)=\sum_a\pi(a \mid s)\left( r(s,a)+\gamma\sum_{s'}p(s' \mid s,a)V^k(s') \right)

  • 如果马尔科夫链无环，能够非常迅速地收敛到 VπV^\pi。
  • 如果有环，可以证明在多次迭代后 Vk(s)V^k(s) 会收敛到 Vπ(s)V^\pi(s)。

在得到 VπV^\pi 后，若想进一步增大，可以考虑整个决策过程中的某一步：如果 Qπ(s,a)>Vπ(s)Q^\pi(s,a)>V^\pi(s)，则我们就该更加倾向于执行动作 aa，这个策略至少不会变差。因此，可以得到

πk+1(a∣s)={1,if a=arg⁡max⁡aQπ(s,a)0,otherwiseQπ(s,a)=r(s,a)+γ∑s′p(s′∣s,a)Vπ(s′)\begin{aligned} \pi^{k+1}(a|s)&=\begin{cases} 1, & \text{if } a=\arg\max_a Q^\pi(s,a) \\ 0, & \text{otherwise} \end{cases} \\ Q^\pi(s,a)&=r(s,a)+\gamma\sum_{s'}p(s' \mid s,a)V^\pi(s') \end{aligned}

整个流程就比较显然了：先随机初始化一个策略 π0\pi^0，然后计算 VπV^\pi，再根据 QπQ^\pi 更新策略，如此反复，直到收敛。

另一种方法也是计算 V∗V^*，但不再显式构造策略，直到最后再从价值函数中导出策略。

Vk+1(s)=max⁡a(r(s,a)+γ∑s′p(s′∣s,a)Vk(s′))V^{k+1}(s)=\max_a\left( r(s,a)+\gamma\sum_{s'}p(s' \mid s,a)V^k(s') \right)

策略的导出也很显然

π(a∣s)={1,if a=arg⁡max⁡aQ(s,a)0,otherwise\pi(a|s)=\begin{cases} 1, & \text{if } a=\arg\max_a Q(s,a) \\ 0, & \text{otherwise} \end{cases}

对于熟悉动态规划的人来说，这个方法会更直观且更高效。

环境未知：时序差分

如果 PP 未知，我们根本无从得知概率 pp 的值，也就无法使用动态规划。此时只能转向估计 V∗V^* 或 Q∗Q^*。

时序差分（Temporal Difference）是一种估计价值函数的方法。假设我们有一个不够精准的 VπV^\pi，那么我们可以通过在环境中采样一组收益 GtG_t 来更新 VπV^\pi

G_t 与 V^\pi(s_t) 的定义是一致的，都是从 s_t 出发的收益。只不过 G_t 是采样，V^\pi(s_t) 是估计。

Vπ(st)←Vπ(st)+α(Gt−Vπ(st))V^\pi(s_t)\leftarrow V^\pi(s_t)+\alpha\left(G_t-V^\pi(s_t)\right)

但是直接这样采样，不但计算量很大，GtG_t 的方差也会很大（在计算的过程中有太多的随机性）。于是，我们引入时序差分，将 GtG_t 分解为 rt+γVπ(st+1)r_t+\gamma V^\pi(s_{t+1})，并使用 rtr_t 来更新 Vπ(st)V^\pi(s_t)

Vπ(st)←Vπ(st)+α(rt+γVπ(st+1)−Vπ(st))V^\pi(s_t)\leftarrow V^\pi(s_t)+\alpha\left(r_t+\gamma V^\pi(s_{t+1})-V^\pi(s_t)\right)

能够证明这个东西最终也会收敛。

由此我们也能对 QπQ^\pi 进行估计

Qπ(st,at)←Qπ(st,at)+α(rt+γQπ(st+1,a′)−Qπ(st,at))Q^\pi(s_t,a_t)\leftarrow Q^\pi(s_t,a_t)+\alpha\left(r_t+\gamma Q^\pi(s_{t+1},a')-Q^\pi(s_t,a_t)\right)

可以看到，只要我们选择使得 Qπ(st+1,a′)Q^\pi(s_{t+1},a') 最大的 a′a'，就能增大 Qπ(st,at)Q^\pi(s_t,a_t) 的值。这离 Sarsa 算法就很近了。为了在利用的同时保证探索，我们引入 ϵ\epsilon 贪心策略。

π(a∣s)={ϵ/∣A∣+1−ϵ,if a=arg⁡max⁡aQ(s,a)ϵ/∣A∣,otherwise\pi(a|s)=\begin{cases} \epsilon/|A|+1-\epsilon, & \text{if } a=\arg\max_a Q(s,a) \\ \epsilon/|A|, & \text{otherwise} \end{cases}

这样，策略就不会确定地陷落入可能次优的选择中，而是会以 ϵ\epsilon 的概率随机探索可能更好的选择。

整个 Sarsa 算法流程如下

1
2
3
4
5
6
7
8
for episode in range(episodes):
    s = env.reset()
    a = policy(s) # 根据策略选择动作，这里是 epsilon-greedy 策略
    while not done:
        # 在状态 s 执行动作 a，得到新的状态 s_ 和奖励 r
        s_, r, done, info = env.step(a)
        a_ = policy(s_) # 同样是 epsilon-greedy 策略
        Q(s,a) += alpha * (r + gamma * Q(s_, a_) - Q(s,a))

Sarsa 算法的一个改进是多步 Sarsa，即使用 kk 步的收益来更新 QπQ^\pi，而不是只使用一步。

Qπ(st,at)←Qπ(st,at)+α(rt+γrt+1+γ2rt+2+⋯+γk−1rt+k−1+γkQπ(st+k,at+k)−Qπ(st,at))Q^\pi(s_t,a_t)\gets Q^\pi(s_t,a_t)+\alpha\left(r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+\cdots+\gamma^{k-1} r_{t+k-1}+\gamma^k Q^\pi(s_{t+k},a_{t+k})-Q^\pi(s_t,a_t)\right)

另一个极其相似但不同的算法是 Q-learning，它最大的区别在于

Q(s,a)←Q(s,a)+α(r+γmax⁡a′Q(s′,a′)−Q(s,a))Q(s,a)\gets Q(s,a)+\alpha\left(r+\gamma\max_{a'}Q(s',a')-Q(s,a)\right)

算法流程如下

1
2
3
4
5
6
for episode in range(episodes):
    s = env.reset()
    while not done:
        a = policy(s) # 比如 epsilon-greedy 策略
        s_, r, done, info = env.step(a)
        Q(s,a) += alpha * (r + gamma * max(Q(s_,a)) - Q(s,a)) # max 取遍所有可能的 a

何为 on-policy 和 off-policy

on-policy 算法是指策略 π\pi 与价值函数 QQ 是相同的；off-policy 算法是指策略 π\pi 与价值函数 QQ 是不同的。如果用 Sarsa 和 Q-learning 来举例：Sarsa 的第 7 步使用当前 policy 选择动作，而 Q-learning 的第 6 步的更新公式与当前 policy 无关。

DQN：连续状态下 Q 函数的近似

如果状态空间连续，Q 函数就是连续的，再使用离散统计 Q 值的 Q-learning 就会非常困难。DQN 使用神经网络来近似 Q 函数，并使用经验回放来稳定训练。

回顾 Q-learning 的更新公式

Q(s,a)←Q(s,a)+α(r+γmax⁡a′Q(s′,a′)−Q(s,a))Q(s,a)\gets Q(s,a)+\alpha\left(r+\gamma\max_{a'}Q(s',a')-Q(s,a)\right)

优化目标就是让 Q(s,a) 逼近 r+γmax⁡a′Q(s′,a′)r+\gamma\max_{a'}Q(s',a')。于是对于每组数据 (s,a,r,s′)(s,a,r,s')，有均方损失函数

L(s,a)=E[(r+γmax⁡a′Q(s′,a′)−Q(s,a))2]\mathcal L(s,a)=\mathbb E\left[(r+\gamma\max_{a'}Q(s',a')-Q(s,a))^2\right]

在这个核心之外，DQN 还有两个改进：

  • 使用经验回放来稳定训练。简单而言就是将采集到的数据 (s,a,r,s′)(s,a,r,s') 存储起来，然后随机采样进行训练。
  • 使用目标网络来稳定训练。简单而言就是使用两个网络，训练网络用于采样 Q(s,a)Q(s,a)，目标网络用于计算 r+γmax⁡a′Q(s′,a′)r+\gamma\max_{a'}Q(s',a')。

策略梯度算法

除了以上介绍的基于价值的方法，强化学习中还有一类基于策略的方法。

首先将策略参数化，得到 πθ\pi_\theta，接受一个状态 ss，输出一个动作 aa。于是目标函数为

J(θ)=Es[Vπ(s)]J(\theta)=\mathbb E_{s}[V^\pi(s)]

对 θ\theta 求导，就能得到优化方向

∇θJ(θ)=Eπθ[Qπθ(s,a)∇θlog⁡πθ(a∣s)]\nabla_\theta J(\theta)=\mathbb E_{\pi_\theta}[Q^{\pi_\theta}(s,a)\nabla_\theta \log \pi_\theta(a \mid s)]

简单理解就是多采样 Q 值高的动作，然后更新策略。为了获取 Q 值，可以使用蒙特卡罗采样

∇θJ(θ)=Eπθ[∑t=0T∑t′=tTγt′−trt′∇θlog⁡πθ(a∣s)]\nabla_\theta J(\theta)=\mathbb E_{\pi_\theta}[ \sum_{t=0}^T\sum_{t'=t}^T \gamma^{t'-t}r_{t'} \nabla_\theta \log \pi_\theta(a \mid s)]

算法流程如下

1
2
3
4
5
初始化策略theta
for episode in range(episodes):
    使用策略theta采样得到轨迹{(s_0, a_0), (s_1, a_1), ..., (s_T, a_T)}，以及奖励r_0, r_1, ..., r_T
    计算策略奖励 \psi_t=\sum_{t'=t}^T \gamma^{t'-t} r_{t'}
    更新策略 theta=theta+alpha*\sum_{t'=t}^T \psi_{t'} \nabla_\theta \log \pi_\theta(a_{t'} \mid s_{t'})

Actor-Critic 算法

Actor-Critic 本质上是策略梯度算法的变种，囊括了一系列算法，很多高效的前沿算法都属于 Actor-Critic 算法。

如果我们将 REINFORCE 算法中的蒙特卡罗过程转为可学习的近似函数，就得到了 Actor-Critic 算法。
在实际运行时，

  • Actor 需要和环境交互，收集奖励信息，并在 Critic 的指导下更新更好的策略。
  • Critic 需要通过 Actor 收集的环境数据拟合一个价值函数，用于判断在当前状态的最优动作。

对于 Actor 的更新，它的策略梯度可以表示为更一般的形式

g=E[ψt∇θlog⁡πθ(at∣st)]g=\mathbb E\left[ \psi_t \nabla_\theta \log \pi_\theta(a_t|s_t) \right]

这个 ψ\psi 可以有很多形式，目前最为流行的是优势函数，即当前状态执行动作 ata_t 的 Q 值减去当前状态的 V 值，从而计算以状态价值为基线时各个动作的优势：

ψt=Aπθ(st,at)=Qπ(st,at)−Vπ(st)\psi_t = A^{\pi_\theta}(s_t, a_t)=Q^\pi(s_t, a_t)-V^\pi(s_t)

对于 Critic，遵循时序差分的形式定义 loss

L=12(r+γV(st+1)−V(st))2\mathcal L=\frac 12\left(r+\gamma V(s_{t+1})-V(s_t)\right)^2

PPO

上文说到 Actor-Critic 模型希望最大化

J(θ)=Es[Vπ(s)]J(\theta)=\mathbb E_{s}[V^\pi(s)]

这固然很好，但如果策略网络是一个深度网络，过大的梯度变化会影响优化过程的稳定性。为了解决这一问题，在一个信任区域内迭代策略，TRPO 被提出。我们不在此详细说明这个算法，只给出其优化目标

max⁡θEs∼VπθkEa∼πθ(a∣s)[πθ(a∣s)πθk(a∣s)Aπθk(s,a)] s.t. Es∼Vπθk[DKL(πθ(⋅∣s),πθk(⋅∣s))]≤ϵ\max_\theta \mathbb E_{\mathcal s \sim \mathcal V^{\pi_{\theta_k}}}\mathbb E_{a \sim \pi_\theta(a|s)}\left[\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}A^{\pi_{\theta_k}}(s,a)\right]\text{ s.t. }\mathbb E_{\mathcal s \sim \mathcal V^{\pi_{\theta_k}}}\left[ D_{KL}(\pi_\theta(\cdot|s),\pi_{\theta_k}(\cdot|s)) \right]\leq \epsilon

PPO 的惯用写法是将难以求解的信任区域近似为

max⁡θEs∼VπθkEa∼πθ(a∣s)[min⁡(πθ(a∣s)πθk(a∣s)Aπθk(s,a),clip(πθ(a∣s)πθk(a∣s),1+ϵ,1−ϵ)Aπθk(s,a))]\max_\theta \mathbb E_{\mathcal s \sim \mathcal V^{\pi_{\theta_k}}} \mathbb E_{a \sim \pi_\theta(a|s)}\left[ \min\left( \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}A^{\pi_{\theta_k}}(s,a), \mathrm{clip}\left(\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)},1+\epsilon,1-\epsilon \right)A^{\pi_{\theta_k}}(s,a) \right) \right]

RFT