基于策略的强化学习

发表于 更新于 本文字数： 11k 阅读时长 ≈ 10 分钟
基于策略的强化学习

参考资料：Proximal Policy Optimization (PPO) 算法理解：从策略梯度开始

如果LaTeX挂了：

传统策略梯度算法

策略近似

设θ\theta为神经网络参数，基于策略的强化学习用参数化概率分布πθ(a∣s)=P(a∣s;θ)\pi_{\theta}(a | s) = P(a | s; \theta)确定策略，在返回的动作概率列表中对不同的动作进行抽样选择。

定义目标函数

目标就是找到那些可能获得更多奖励期望值的动作，使它们对应的概率更大，从而策略就更有可能选择这些动作。

定义的最大化目标函数：

max⁡θJ(θ)=max⁡θEτ∼πθ(R(τ))=max⁡θ∑τP(τ;θ)R(τ) \max_{\theta} J(\theta) = \max_{\theta} E_{\tau \sim \pi_{\theta} } (R(\tau)) = \max_{\theta} \sum_{\tau} P(\tau; \theta) R(\tau)

其中τ\tau是agent与环境交互产生的状态-动作轨迹τ=(s1,a1,…,sT,aT)\tau = (s_1, a_1, \dots, s_T, a_T)。我们的目标是通过调整θ\theta，使得获得更大奖励期望的轨迹出现的概率更高。

其中，轨迹τ\tau在策略πθ(a∣s)\pi_{\theta}(a | s)下发生的概率为：

P(τ;θ)=[∏t=0TP(st+1∣st,at)⋅πθ(at∣st)] P(\tau; \theta) = \left[ \prod_{t = 0}^T P(s_{t + 1} | s_t, a_t) \cdot \pi_{\theta} (a_t | s_t) \right]

实际枚举所有可能的轨迹是很困难的，基本都需要通过大量采样得到样本求期望值近似。

策略梯度

∇θJ(θ)=∑τ∇θP(τ;θ)⋅R(τ)=∑τP(τ;θ)∇θP(τ;θ)P(τ;θ)R(τ)=∑τP(τ;θ)⋅∇θlog⁡P(τ;θ)⋅R(τ) \begin{aligned} \nabla_{\theta} J(\theta) &= \sum_{\tau} \nabla_{\theta} P(\tau; \theta) \cdot R(\tau) \\\\ &= \sum_{\tau} P(\tau; \theta) \frac{\nabla_{\theta} P(\tau; \theta)}{P(\tau; \theta)} R(\tau) \\\\ &= \sum_{\tau} P(\tau; \theta) \cdot \nabla_{\theta} \log P(\tau; \theta) \cdot R(\tau) \end{aligned}

根据P(τ;θ)P(\tau; \theta)可得：

∇θlog⁡P(τ;θ)=∇θ[∑t=0Tlog⁡P(st+1∣st,at)+∑t=0Tlog⁡πθ(at∣st)]=∑t=0T∇θlog⁡πθ(at∣st) \begin{aligned} \nabla_{\theta} \log P(\tau; \theta) &= \nabla_{\theta} \left[ \sum_{t = 0}^T \log P(s_{t + 1} | s_t, a_t) + \sum_{t = 0}^T \log \pi_{\theta} (a_t | s_t) \right] \\\\ &= \sum_{t = 0}^T \nabla_{\theta} \log \pi_{\theta} (a_t | s_t) \end{aligned}

假设当前有mm条轨迹的样本：

∇θJ(θ)≈1m∑i=1m∇θlog⁡P(τ(i);θ)⋅R(τ(i))=1m∑i=1m[∑t(i)=0T(i)∇θlog⁡πθ(at(i)∣st(i))]⋅R(τ(i))=1n∑i=1n∇θlog⁡πθ(ai∣si)⋅R(τi)(n=∑i=1m(T(i)+1)) \begin{aligned} \nabla_{\theta} J(\theta) &\approx \frac{1}{m} \sum_{i = 1}^{m} \nabla_{\theta} \log P(\tau^{(i)}; \theta) \cdot R(\tau^{(i)}) \\\\ &= \frac{1}{m} \sum_{i = 1}^{m} \left[ \sum_{t^{(i)} = 0}^{T^{(i)}} \nabla_{\theta} \log \pi_{\theta} (a_{t^{(i)}} | s_{t^{(i)}}) \right] \cdot R(\tau^{(i)}) \\\\ &= \frac{1}{n} \sum_{i = 1}^{n} \nabla_{\theta} \log \pi_{\theta} (a_i | s_i) \cdot R(\tau_i) \quad \left( n = \sum_{i = 1}^{m} (T^{(i)} + 1) \right) \end{aligned}

策略梯度的更新规则：

θ←θ+α⋅∇θJ(θ) \theta \leftarrow \theta + \alpha \cdot \nabla_{\theta} J(\theta)

Softmax策略

对于离散动作空间：

πθ(a∣s)=eϕ(s,a)Tθ∑a′∈Aeϕ(s,a′)Tθ \pi_{\theta}(a | s) = \frac{e^{\phi(s, a)^T \theta}}{\sum_{a' \in A} e^{\phi(s, a')^T \theta}}

对应的策略梯度：

∇θlog⁡πθ(a∣s)=∇θ(ϕ(s,a)Tθ−log⁡∑a′∈Aeϕ(s,a′)Tθ)=ϕ(s,a)−∑a′∈Aϕ(s,a′)⋅eϕ(s,a′)Tθ∑a′∈Aeϕ(s,a′)Tθ=ϕ(s,a)−∑a′∈Aϕ(s,a′)⋅πθ(a′∣s) \begin{aligned} &\quad \nabla_{\theta} \log \pi_{\theta}(a | s) \\\\ &= \nabla_{\theta} \left(\phi(s, a)^T \theta - \log \sum_{a' \in A} e^{\phi(s, a')^T \theta} \right) \\\\ &= \phi(s, a) - \frac{\sum_{a' \in A} \phi(s, a') \cdot e^{\phi(s, a')^T \theta}}{\sum_{a' \in A} e^{\phi(s, a')^T \theta}} \\\\ &= \phi(s, a) - \sum_{a' \in A} \phi(s, a') \cdot \pi_{\theta}(a' | s) \end{aligned}

如果奖励信号很高并且观察到的向量与平均向量相差很大，就会有增加该动作概率的强烈趋势。

高斯策略

对于连续动作空间：

πθ(a∣s)=12πσθe−(a−μθ)22σθ2 \pi_{\theta}(a | s) = \frac{1}{\sqrt{2 \pi} \sigma_{\theta}} e^{- \frac{(a - \mu_{\theta})^2}{2 \sigma_{\theta}^2}}

其中正态分布的均值μθ=ϕ(s,a)Tθ\mu_{\theta} = \phi(s, a)^T \theta。

对应的策略梯度：

∇θlog⁡πθ(a∣s)=∇θ(−12⋅log⁡(2πσθ2)−(a−μθ)22σθ2)=(a−μθ)ϕ(s,a)σθ2 \begin{aligned} &\quad \nabla_{\theta} \log \pi_{\theta}(a | s) \\\\ &= \nabla_{\theta} \left(-\frac{1}{2} \cdot \log (2 \pi \sigma_{\theta}^2) - \frac{(a -\mu_{\theta})^2}{2 \sigma_{\theta}^2} \right) \\\\ &= \frac{(a - \mu_{\theta})\phi(s, a)}{\sigma_{\theta}^2} \end{aligned}

在高回报的情况下，远离均值的动作会触发强烈的更新信号。

在实际任务中，我们没有必要手动计算偏导数，使用深度学习框架的自动求导。定义损失函数：

L(a,s,r)=−log⁡(πθ(a∣s))r \mathcal{L}(a, s, r) = -\log(\pi_\theta(a | s)) r

即可让计算机自动求导。

算法实现

1
2
3
4
5
6
Network: theta := R^(|theta|)
for n = 1 to N:
    tau <- pi(theta)
    for t = 1 to T:
        R(tau | t) = R[t] + R[t + 1] + ... + R[T]
        theta <- theta - alpha * R(tau | t) * grad(theta, pi(theta, a | s))

这里对于一条路径，将路径上每一个状态都进行了计算，对信息的利用最大化。

自然策略梯度算法

传统策略梯度算法的缺陷

在传统的策略梯度算法中，权重更新会遇到两个问题：

  • 过冲（Overshooting）: 更新错过了奖励峰值并落入了次优策略区域
  • 下冲（Undershooting）: 在梯度方向上采取过小的更新步长会导致收敛缓慢

在监督学习问题中，overshooting不是什么问题，因为数据是固定的，我们可以在下一个epoch中重新纠正；但在强化学习问题中，如果因为overshooting陷入了一个较差的策略区域，则未来的样本批次可能不会提供太多有意义的信息，用较差的数据样本再去更新策略，从而陷入了糟糕的正反馈中无法恢复。较小的学习率可能会解决这个问题，但会导致收敛速度变慢的undershooting问题。

限制策略更新的差异

我们需要表示策略（分布）之间的差异，而不是参数本身的差异。计算两个概率分布之间的差异，最常见的是KL散度，也称为相对熵，描述了两个概率分布之间的距离：

DKL(πθ∣∣πθ+Δθ)=∑x∈Xπθ(x)log⁡(πθ(x)πθ+Δθ(x)) \mathcal{D}_{KL}(\pi_{\theta} || \pi_{\theta + \Delta \theta}) = \sum_{x \in \Chi} \pi_{\theta}(x) \log \left( \frac{\pi_{\theta}(x)}{\pi_{\theta + \Delta \theta}(x)} \right)

调整后的策略更新限制为：

Δθ∗=arg max⁡Δθ,DKL(πθ∣∣πθ+Δθ)≤ϵJ(θ+Δθ) \Delta \theta^{*} = \argmax_{\Delta \theta, \mathcal{D}_{KL}(\pi_{\theta} || \pi_{\theta + \Delta \theta}) \le \epsilon} J(\theta + \Delta \theta)

然而，计算KL散度需要遍历所有的状态-动作对，因此我们需要一些化简来处理现实的RL问题。

首先，我们使用拉格朗日松弛将原表达式的发散约束转化为惩罚项，得到一个更容易求解的表达式：

Δθ∗=arg max⁡ΔθJ(θ+Δθ)−λ(DKL(πθ∣∣πθ+Δθ)−ϵ) \Delta \theta^{*} = \argmax_{\Delta \theta} J(\theta + \Delta \theta) - \lambda(\mathcal{D}_{KL}(\pi_{\theta} || \pi_{\theta + \Delta \theta}) - \epsilon)

用近似方法来化简。通过泰勒展开：

Δθ∗≈arg max⁡ΔθJ(θ)+∇θJ(θ)⋅Δθ−12λ(ΔθTF(θ)Δθ)+λϵ≈arg max⁡Δθ∇θJ(θ)⋅Δθ−12λ(ΔθTF(θ)Δθ)F(θ)=Eθ[∇θlog⁡πθ(x)∇θlog⁡πθ(x)T] \begin{aligned} \Delta \theta^{*} &\approx \argmax_{\Delta \theta} J(\theta) + \nabla_{\theta} J(\theta) \cdot \Delta \theta - \frac{1}{2} \lambda (\Delta \theta^{T} F(\theta) \Delta \theta) + \lambda \epsilon \\\\ &\approx \argmax_{\Delta \theta} \nabla_{\theta} J(\theta) \cdot \Delta \theta - \frac{1}{2} \lambda (\Delta \theta^{T} F(\theta) \Delta \theta) \\\\ F(\theta) &= \mathbb{E}_{\theta} [ \nabla_{\theta} \log \pi_{\theta}(x) \nabla_{\theta} \log \pi_{\theta}(x)^{T} ] \end{aligned}

KL散度近似于二阶泰勒展开。用Fisher信息矩阵代替二阶导数，除了符号紧凑性外，还可以大大减少计算开销。

解决KL约束问题

对于近似简化后的表达式，可以通过将关于Δθ\Delta \theta的梯度设置为0，来找到最优的权重更新Δθ\Delta \theta：

0=∂∂Δθ(∇θJ(θ)Δθ−12λΔθTF(θ)Δθ)=∇θJ(θ)−12λF(θ)ΔθΔθ=−2λF(θ)−1∇θJ(θ) \begin{aligned} 0 &= \frac{\partial}{\partial \Delta \theta} \left( \nabla_{\theta} J(\theta) \Delta \theta - \frac{1}{2} \lambda \Delta \theta^{T} F(\theta) \Delta \theta \right) \\\\ &= \nabla_{\theta} J(\theta) - \frac{1}{2} \lambda F(\theta) \Delta \theta \\\\ \Delta \theta &= - \frac{2}{\lambda} F(\theta)^{-1} \nabla_{\theta} J(\theta) \end{aligned}

其中，λ\lambda是一个常数，可以吸收到学习率α\alpha中。根据DKL(πθ∣∣πθ+Δθ)≤ϵ\mathcal{D}_{KL}(\pi_{\theta} || \pi_{\theta + \Delta \theta}) \le \epsilon，我们可以推出动态学习率：

α=2ϵ∇J(θ)TF(θ)−1∇J(θ) \alpha = \sqrt{\frac{2 \epsilon}{\nabla J(\theta)^T} F(\theta)^{-1} \nabla J(\theta)}

可以确保每次更新的KL散度（近似）等于ϵ\epsilon。

自然策略梯度：

∇~J(θ)=F(θ)−1∇J(θ) \tilde{\nabla} J(\theta) = F(\theta)^{-1} \nabla J(\theta)

最终的权重更新方案为：

Δθ=2ϵ∇J(θ)TF(θ)−1∇J(θ)∇~J(θ) \Delta \theta = \sqrt{\frac{2 \epsilon }{\nabla J(\theta)^T F(\theta)^{-1} \nabla J(\theta)}} \tilde{\nabla} J(\theta)

该方案的强大之处在于，无论分布的表示如何，它总是以相同的幅度改变策略。

信赖域策略优化算法（TRPO）

自然策略梯度算法的缺陷

  • 近似值可能会违反KL约束，从而导致分析得出的步长过大，超出限制要求
  • 矩阵FF的计算时间太长，是O(N3)O(N^3)复杂度的运算
  • 我们没有检查更新是否真的改进了策略。由于存在大量的近似过程，策略可能并没有优化

算法理论

针对自然策略梯度算法的问题，我们希望可以对策略的优化进行量化，从而保证每次的更新一定是优化作用的。为此，我们需要计算两种策略之间预期回报的差异。这里采用的是原策略预期回报添加新策略预期优势的方式。该表达式在原策略下计算优势函数，无需重新采样：

J(πθ+Δθ)=J(πθ)+Eτ∼πθ+Δθ∑t=0∞γtAπθ(st,at) J(\pi_{\theta + \Delta \theta}) = J(\pi_{\theta}) + \mathbb{E}_{\tau \sim \pi_{\theta + \Delta \theta}} \sum_{t = 0}^{\infin} \gamma^{t} A^{\pi_{\theta}}(s_t, a_t)

其中优势函数的定义为：

Aπθ(s,a)=E(Qπθ(s,a)−Vπθ(s)) A^{\pi_{\theta}}(s, a) = \mathbb{E}(Q^{\pi_{\theta}}(s, a) - V^{\pi_{\theta}}(s))

由于时间范围是无限的，引入状态的折扣分布：

ρπ(s)=∑k=0∞γkP(sk=s) \rho_{\pi}(s) = \sum_{k = 0}^{\infin} \gamma^{k} P(s_k = s)

原差异表达式可重新表示为：

J(πθ+Δθ)=J(πθ)+∑s∈Sρπθ+Δθ(s)∑a∈Aπθ+Δθ(a∣s)Aπθ(s,a) J(\pi_{\theta + \Delta \theta}) = J(\pi_{\theta}) + \sum_{s \in \mathcal{S}} \rho_{\pi_{\theta + \Delta \theta}}(s) \sum_{a \in \mathcal{A}} \pi_{\theta + \Delta \theta}(a | s) A^{\pi_{\theta}}(s, a)

引入近似误差，使用当前策略近似：

J(πθ+Δθ)≈J(πθ)+∑s∈Sρπθ(s)∑a∈Aπθ+Δθ(a∣s)Aπθ(s,a) J(\pi_{\theta + \Delta \theta}) \approx J(\pi_{\theta}) + \sum_{s \in \mathcal{S}} \rho_{\pi_{\theta}}(s) \sum_{a \in \mathcal{A}} \pi_{\theta + \Delta \theta}(a | s) A^{\pi_{\theta}}(s, a)

将状态分布求和替换为期望，方便实际计算时使用蒙特卡洛模拟进行采样，同时将动作求和替换为重要性采样。通过重要性采样，可以有效利用当前策略的行动期望，并针对新策略下的概率进行了修正：

J(πθ+Δθ)=J(πθ)+∑s∈Sρπθ+Δθ(s)∑a∈Aπθ+Δθ(a∣s)Aπθ(s,a)=J(πθ)+Es∼ρπθ+Δθπθ+Δθ(a∣s)Aπθ(s,a)≈J(πθ)+Es∼ρπθπθ+Δθ(a∣s)πθ(a∣s)Aπθ(s,a) \begin{aligned} J(\pi_{\theta + \Delta \theta}) &= J(\pi_{\theta}) + \sum_{s \in \mathcal{S}} \rho_{\pi_{\theta + \Delta \theta}}(s) \sum_{a \in \mathcal{A}} \pi_{\theta + \Delta \theta}(a | s) A^{\pi_{\theta}}(s, a) \\\\ &= J(\pi_{\theta}) + \mathbb{E}_{s \sim \rho_{\pi_{\theta + \Delta \theta}}} \pi_{\theta + \Delta \theta}(a | s) A^{\pi_{\theta}}(s, a) \\\\ &\approx J(\pi_{\theta}) + \mathbb{E}_{s \sim \rho_{\pi_{\theta}}} \frac{\pi_{\theta + \Delta \theta}(a | s)}{\pi_{\theta}(a | s)} A^{\pi_{\theta}}(s, a) \end{aligned}

描述更新策略相对于原策略的预期优势称为替代优势：

J(πθ+Δθ)−J(πθ)≈Es∼ρπθπθ+Δθ(a∣s)πθ(a∣s)Aπθ(s,a)=Lπθ(πθ+Δθ) J(\pi_{\theta + \Delta \theta}) - J(\pi_{\theta}) \approx \mathbb{E}_{s \sim \rho_{\pi_{\theta}}} \frac{\pi_{\theta + \Delta \theta}(a | s)}{\pi_{\theta}(a | s)} A^{\pi_{\theta}}(s, a) = \mathcal{L}_{\pi_{\theta}}(\pi_{\theta + \Delta \theta})

之前产生的近似误差可以用两种策略之间最坏情况的KL散度表示：

J(πθ+Δθ)−J(πθ)≥Lπθ(πθ+Δθ)−CDKLmax⁡(πθ∣∣πθ+Δθ) J(\pi_{\theta + \Delta \theta}) - J(\pi_{\theta}) \ge \mathcal{L}_{\pi_{\theta}}(\pi_{\theta + \Delta \theta}) - C \mathcal{D}_{KL}^{\max} (\pi_{\theta} || \pi_{\theta + \Delta \theta})

论文中推导出CC的值以及目标函数改进的下限。如果我们改进右侧，可以保证左侧也得到改进。本质上，如果替代优势Lπθ(πθ+Δθ)\mathcal{L}_{\pi_{\theta}}(\pi_{\theta + \Delta \theta})超过最坏情况下的近似误差CDKLmax⁡(πθ∣∣πθ+Δθ)C \mathcal{D}_{KL}^{\max} (\pi_{\theta} || \pi_{\theta + \Delta \theta})，我们一定会改进目标。

这就是单调改进定理。相应的过程是最小化最大化算法（MM）。即如果我们改进下限，我们也会将目标改进至少相同的量。

算法实现

在实际的算法实现方面，TRPO和自然策略梯度算法没有太大的区别。TRPO的核心是利用单调改进定理，验证更新是否真正改进了我们的策略。

咕咕咕