Reinforcement Learning

Posted Apr 28, 2025 Updated Sep 19, 2025

By AKatydid

36 min read

强化学习是一种通过智能体与环境交互来学习策略的机器学习范式。智能体通过探索（采取动作）获得经验（样本），并根据环境反馈的奖励（reward）来优化行为选择，最终目标是最大化累积奖励。

强化学习擅长解决序列决策问题，尤其是状态空间大、规则复杂的任务。大致过程描述为：智能体在一个状态下采取动作，影响未来状态和奖励，目标是找到最优策略，如 Fig 1 所示。

Fig 1. 强化学习交互过程

强化学习与其他机器学习范式的差异可总结为：监督学习学“从样本到标签的映射”，无监督学习学“数据的内在结构”，强化学习学“在交互环境中最大化长期奖励的策略”。

监督学习：数据带有明确标签，目标是最小化预测误差。
无监督学习：数据没有标签，目标是发现数据的潜在结构（聚类 / 降维）
强化学习：学习的样本是与环境交互产生的，没有标签，只有奖励信号（可能是延迟奖励或稀疏奖励），目标不是拟合标签或发现结构，而是学到能最大化长期回报的策略。

下面，将从强化学习的数学建模，经典算法，深度强化学习（DRL）和多智能体强化学习三个方面进行细致的介绍。

一、马尔可夫决策过程建模

强化学习中，决策过程可被形式化描述为一条轨迹 (trajectory)：$\tau=(s_1,a_1,r_1,….,s_n,a_n,r_n)$，整个决策过程简历在马尔可夫决策过程之上。

1.1 贝尔曼方程

首先，我们先介绍马尔可夫性质，其定义为：在给定过去所有的状态信息的条件下，未来状态的概率只依赖于当前的状态，而与过去的状态无关。

\[p(X_{t+1}=x_{t+1}|X_{0:t}=x_{0:t})=p(X_{t+1}=x_{t+1}|X_t=x_t)\]

其次，引入马尔科夫链概念，用于简化了马尔可夫性质的描述：给定随机状态序列 $s_1,…s_t$，未来状态 $s_{t+1}$，历史状态 $h_t={s_1,…,s_t}$ ，马尔可夫过程可表述为 $p(s_{t+1}|h_t) = p(s_{t+1}|s_t)$。

然后，在马尔科夫链状态转移时附加奖励，则形成马尔可夫奖励过程，其定义为：给定折扣因子 $\gamma\ (\le1)$，最终时间步 $T$，时刻 $t$ 后的奖励序列 $r_{t+1},r_{t+2},…r_T$，那么回报表示如下。

\[G_t=r_{t+1}+\gamma r_{t+2}+\gamma ^2r_{t+3}+···+\gamma ^{T-t-1}r_T\]

一般使用状态价值函数 $V^t(s)=E[G_t|s_t=s]$ 代表状态 $S_t$ 下的回报期望。由于回报的递推性质，状态价值函数之间存在递推关系：

根据回报的定义：

\[G_t = r_{t+1}+\gamma G_{t+1}\]

两边取期望可得：

\[V(s) = \mathbb{E}[r_{t+1}+\gamma G_{t+1}|s_t=s]\]

而下一步状态 $s_{t+1}$ 由转移概率 $P(s’|s)$ 决定（转移概率 $P(s’|s)$ 是环境中的动态规则，在理论中是给定的），从而上式可展开为：

\[V(s)=\sum_{s'}P(s'|s)[R(s,s')+\gamma V(s')]\]

上式即为贝尔曼方程，将复杂长期目标递归地分解成了“一步奖励+子问题”的形式。

1.2 马尔可夫决策过程

马尔可夫决策过程（MDP）在上述马尔可夫奖励过程中增加了一个 决策/采取action 过程，为序列决策问题提供了一个形式化建模框架，表示如下所示。

\[M = (S, A, P, R,\gamma)\]

符号解释如下表所示。

符号	详情
S (状态空间)	Agent 可能处于的所有状态的集合
A (动作空间)	所有可能动作的集合
P (状态转移概率函数)	在执行某个动作后，环境从一个状态转移到另一个状态的概率 $p(s_{t+1} \| s_t,a_t)$
R (奖励函数)	智能体在某个状态执行某个动作后获得的即时奖励
$\gamma$ (折扣因子)	表示对未来奖励的重视程度，取值范围 [0,1]

在 MDP 的建模下，智能体可以选择动作 $a\in A$，状态转移由 $P(s’|s,a)$ 决定，奖励由 $R(s,a,s’)$ 给出（状态转移和奖励都由环境给定），RL 的目标则是找到策略 $\pi(a|s)$，最大化回报（累积奖励）$G_t=\sum_{k=0}^{\infty}\gamma^{k}r_{t+k+1}$。

在给定策略 $\pi$ 的情况下，价值函数 $V^{\pi}(s)=\mathbb{E}[R_{t+1}+\gamma V^{\pi}(S_{t+1})|S_{t}=s]$，展开状态转移概率和策略：

\[V_\pi(s)=\sum_{a \in A}\pi(a|s)(R(s,a)+\gamma\sum_{s'\in S}p(s'|s,a)V(s'))\]

PS: 就是策略 $\pi$ 下，各个动作概率 * (即时奖励+状态转移后的未来奖励期望)，即期望的计算

一般使用动作价值函数 $Q_\pi(s,a)=E_\pi[G_t|s_t=s,a_t=a]$ 定义某个状态采取某个动作得到回报的期望，具体推理如下所示。

\[\begin{align*} Q(s,a)&=E[G_t|s_t=s,a_t=a] \\ &=E[r_{t+1}+\gamma r_{t+2}+\gamma ^2r_{t+3}+...+\gamma ^{T-t-1}r_T|s_t=s,a_t=a] \\ &=E[r_{t+1}|s_t=s,a_t=a]+\gamma E[r_{t+2}+\gamma r_{t+3}+...|s_t=s,a_t=a] \\ &=R(s,a)+\gamma E[G_{t+1}|s_t=s,a_t=a] \\ &=R(s,a)+\gamma E[V_{s_{t+1}}|s_t=s,a_t=a] \\ &=R(s,a)+\gamma\displaystyle\sum_{s'\in S}p(s'|s,a)V(s') \end{align*}\]

而动作价值函数 $Q_\pi(s,a)$ 同样具备递推性质，如下式子所示。

\[Q(s,a)=R(s,a)+\gamma\displaystyle\sum_{s'\in S}p(s'|s,a)\sum_{a' \in A}\pi(a'|s')Q_\pi(s',a')\]

现在，我们得到两种价值函数，根据它们的定义和期望计算公式，我们可以推出两种价值函数的关联：

$V_\pi(s)=\displaystyle\sum_{a \in A}\pi(a|s)Q_\pi(s,a)$
$Q(s,a)=R(s,a)+\gamma\displaystyle\sum_{s’\in S}p(s’|s,a)V(s’)$
$V_\pi(s)=\displaystyle\sum_{a\in A}\pi(a|s)Q_\pi(s,a)$

但是，我们的目标是得到一个策略，根据策略采取序列动作，最大化累积奖励，如何根据两种价值函数的指导得到最佳策略呢？

1.3 策略搜索

由于回报的递推性质，$T$ 时刻累积奖励最大，那么 $T-1$ 时刻的累积奖励也是最大的，求解最大奖励，即为求解最佳状态价值函数 $V^*(s) = \mathop{max}\limits_{\pi}\ V(s)$，而最佳策略可定义为 $\pi^*(s)=arg\ \mathop{max}\limits_{\pi}\ V_\pi(s)$，实际上二者是一回事。

那么如何搜索最佳策略呢？

穷举：如果 action space 和 state space 离散且有限，能将 policy 完整地穷举一遍
策略迭代
价值迭代

1.3.1 策略迭代

在 1.2 节，我们定义了 $Q(s,a)$ 和 $V(s)$，并推理出了它们之间的关系：

$V_\pi(s)=\sum_{a \in A}\pi(a|s)(R(s,a)+\gamma\sum_{s’\in S}p(s’|s,a)V(s’))$
$Q(s,a)=R(s,a)+\gamma\displaystyle\sum_{s’\in S}p(s’|s,a)V(s’)$
$V_\pi(s)=\displaystyle\sum_{a\in A}\pi(a|s)Q_\pi(s,a)$

假设给定策略 $\pi_i$，环境的条件概率 $P(s’|s)$ 和奖励函数 $R$ 条件下，我们很容易推理出策略更新的过程：

初始化
- 对所有状态 $s \in S$，初始化状态价值函数： $V(s) = 0$
- 随机初始化策略 $\pi_0(a|s)$
重复以下步骤直到策略收敛：
(a) 策略评估
- 对每个状态 $s$ 和动作 $a$，计算动作价值： $Q(s,a) = R(s,a) + \gamma \sum_{s'\in S} P(s'|s,a) V(s')$
- 更新状态价值函数： $V_{\text{new}}(s) = \sum_{a \in A} \pi_i(a|s) Q(s,a)$
- 检查收敛：若 $|V_{\text{new}}(s) - V(s)| < \epsilon \quad \forall s$
  则策略评估收敛，否则令 $V(s) \gets V_{\text{new}}(s)$ 并重复
(b) 策略改进
- 对每个状态 $s$，更新策略： $\pi_{i+1}(s) = \arg\max_{a \in A} Q(s,a)$
- 如果 $\pi_{i+1} = \pi_i$，则策略收敛，得到最优策略 $\pi^*$ 和最优价值函数 $V^*$
- 否则，令 $\pi_i \gets \pi_{i+1}$，返回策略评估步骤

由于一直采取 argmax 贪心操作，得到的策略总是更好或不变。当策略迭代停止时，取让 Q 函数最大化的 action，则：

\[Q_\pi(s,\pi'(s))=\mathop{max}\limits_{a\in A}\ Q_\pi(s,a)=Q_\pi(s,\pi(s))=V_\pi(s)\]

1.3.2 价值迭代

价值迭代将贝尔曼最优方程作为更新规则 $V(s)\gets\mathop{max}\limits_{a\in A}\ \Big(R(s,a)+\gamma\displaystyle\sum_{s’\in S}p(s’|s,a)V(s’)\Big)$，直接迭代状态价值函数，并隐式得到最优策略：

初始化
- 对所有状态 $s \in S$，初始化： $V_0(s) = 0$
迭代更新状态价值函数
- 对每个状态 $s$： $V_{k+1}(s) = \max_{a \in A} \left[ R(s,a) + \gamma \sum_{s'\in S} P(s'|s,a) V_k(s') \right]$
检查收敛
- 如果 $\max_s |V_{k+1}(s) - V_k(s)| < \epsilon$
  则收敛，得到最优状态价值函数 $V^*$
提取最优策略
$\pi^*(s) = \arg\max_{a \in A} \left[ R(s,a) + \gamma \sum_{s'\in S} P(s'|s,a) V^*(s') \right]$

二、经典算法

在状态转移函数 $P(s’|s,a)$ 和奖励函数 $R(s,a)$ 已知的情况下，理论上是能够直接通过 DP 直接求解最优值的，这就是 model-based 的方法。即，Agent 能推演每条轨迹，而不用与真实环境实时交互。而 model-free 则是 $P(s’|s,a)$ 和 $R(s,a)$ 未知，只能通过与环境交互获得的样本数据来逼近价值函数或策略。

在介绍之前，先引入两个概念：

on-policy：学习和行为使用同一策略 $\pi$
off-policy：学习和行为使用不同策略，行为策略 $\mu$ 用来采样动作，目标策略 $\pi$ 为学习的策略

下面，本章节将介绍如何在 model-free 的情况，逼近价值函数，并基于逼近价值函数的方法，迭代更新策略。

2.1 贝尔曼期望逼近

蒙特卡洛（MC）和时序差分（TD）是两种经典的逼近贝尔曼期望 model-free 方法（未涉及改进策略），下面依次介绍。

2.1.1 蒙特卡洛（MC）

蒙特卡洛核心思想是：通过与环境交互，整条轨迹走完后再计算回报来更新状态或动作价值函数。一般而言，MC 方法会采样多条轨迹，算平均回报 $G_t$，然后更新状态价值函数 / 动态价值函数，直至收敛。

\[V(s_t) \leftarrow V(s_t) + \alpha \left[ G_t - V(s_t) \right]\]

MC 是无偏采样，但是不适用于长回合或无限步数的环境。

2.1.2 时序差分（TD）

TD 方法则针对 MC 方法的缺点，用 “当前奖励 + 下一状态的估计值” 来更新当前状态，而不是等整条轨迹结束。

\[V(s_t) \leftarrow V(s_t) + \alpha \left[ r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \right]\]

其中，$r_{t+1}$ 是真实奖励，$V^\pi(s_{t+1}) - V^\pi(s_t)$ 则是一步时许差分的有偏估计，如下图 Fig 2 所示。

Fig 2. TD(0)

上面用一步时序差分来逼近状态价值函数 $V(s)$，同样能使用多步时序差分（n-TD）进行逼近：使用当前时刻 t 和第 n 步之后的估计值$V(s_t)$、$V(s_{t+n})$，来更新当前时刻 t 的值，公式如下所示。

\[V(s_t) \leftarrow V(s_t) + \alpha \left[ G_t^{(n)} - V(s_t) \right]\]

其中，$G_t^{(n)} = r_{t+1} + \gamma r_{t+2} + \ldots + \gamma^{n-1} r_{t+n} + \gamma^n V(s_{t+n})$

2.2 Sarsa: on-policy TD

由于 $Q_\pi(s)$ 同样具备递推过程，Sarsa 将原本 TD 中更新 V 的过程，变成更新 Q 的过程：

\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \right]\]

每次更新时，需要知道 $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$ 采样数据，而 model-free 下依赖 agent 去环境中执行 step，才能更新一次，过程如下图 Fig 3 所示。

Fig 3. Sarsa 逼近 Q(s,a) 过程

Sarsa 可以用于更新策略，周期性地将策略更新为贪心策略： $\pi(s)=arg\ \mathop{max}\limits_{a}\ Q(s,a)$。

由于 TD 逼近的是 $v_\pi(s)$，而 $Q(s,a)=R(s,a)+\gamma\displaystyle\sum_{s’\in S}p(s’|s,a)V(s’)$，model-free 情况下，我们不知道状态转移函数，从而无法用 TD 更新策略。

2.3 Q-learning: off-policy TD

在 Sarsa 基础上，周期性地更新 Q 函数，如果采样次数少的话，很难准确估计出 Q 分布，换句话说，Sarsa 学习的是当前行为策略下的 Q 值，效率很低。

如果有一个策略能采取一批数据，通过经验采样估计 Q 值，就能使用策略迭代的方法，学习 $\mathop{max}\limits_{a’}\ Q(s_{t+1}, a’)$。

Q-Learning 用 off policy 思想解决了这一问题：目标策略 $\pi$ 学习下一步价值最大策略：$\pi(s_{t+1})=arg\ \mathop{max}\limits_{a’}\ Q(s_{t+1},a’)$，行为策略 $\mu$ 是一个随机策略，可使用以下随机算法，如 $\epsilon-Greedy$ 随机策略

\[\begin{align*} \underline{\text{Epsilon Greedy}} \\ a &= \begin{cases} \arg \max_a Q(s,a), & p = 1-\epsilon \\ \text{random}, & \text{otherwise} \end{cases} \\[1em] \underline{\text{Boltzmann Exploration}} \\ P(a|s) &= \frac{\exp(Q(s,a))}{\sum_a \exp(Q(s,a))} \end{align*}\]

行为策略 μ 负责与环境交互，使用如 ε-贪心策略来进行探索，生成一批经验 $(s_t,a_t,r_{t+1},s_{t+1})$。然而在 Q-learning 更新中使用目标策略 π 的估计值 $\mathop{max}\limits_a\ Q(s_{t+1}, a)$，策略分离允许在交互和学习两个阶段实现并行。

所以，Q-learning 能够省略从环境中 smaple 出 $a_{t+1}$ ，而能得出差分的目标是 $r_{t+1}+\gamma \mathop{max}\limits_{a}Q(s_{t+1},a)$

\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_{t+1} + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t) \right]\]

但是，如果样本与策略差距过远，可能会导致训练不稳定。另外，Q-Learning 需要记录 (s, a) 值，不能处理过大的空间。

三、深度强化学习（DRL）

由于环境中 (S, A) 空间通常是巨大的，传统方法难以在巨大的空间中迭代求解（本质是难以采样拟合出价值函数），而神经网络强大的非线性表达能力，可以在庞大的空间内拟合出策略或价值函数。

在介绍具体 DRL 算法前，我们先对 Agent 分类，然后按照分类依次介绍各种 DRL 算法。

Actor 基于策略的 Agent，直接学习策略，给出一个 State，输出对应动作概率
Critic 基于价值的 Agent，显示学习价值函数，隐式学习策略
Actor-Critic 通过 Critic 和 Actor及二者交互，得到最佳策略

3.1 Actor

Actor 负责直接学习策略。具体而言，神经网络根据当前状态输出各个动作的概率分布，如下图 Fig. 4 所示。该策略函数 $\pi(a|s)$ 由神经网络参数 $\theta$ 控制，训练的目标就是不断优化 $\theta$，使得采样得到的动作能带来更高的期望奖励。

Fig 4. DRL 中 Agent 策略函数表示形式

3.1.1 Gradient Ascent

策略好坏的评价标准是：一个完整 episode 的累积奖励（Return）。奖励越高，说明策略越优。训练的核心目标可以表述为：

\[\theta^*=arg\ \mathop{max}\limits_{\theta}\stackrel{-}{R}_\theta\]

其中，$\stackrel{-}{R}_\theta$ 表示在 policy $\theta$ 下的期望累计奖励。

为此，Actor 使用策略梯度方法，通过梯度上升（gradient ascent）来更新参数 $\theta$，不断提升提升轨迹中带来高回报动作的概率，从而最大化期望奖励。

Fig 5. Policy Ascent 推理过程

实际计算梯度，需要收集多条轨迹 $\tau^{i}=<s_1^i,a_1^i,r_1^i,….,s_n^i,a_n^i,r_n^i>$，即需要先用参数为 $\theta^{old}$ 的 Agent 先去与环境互动，收集N条轨迹 $\tau^{[1:N]}$，再将数据代入梯度更新表达式中，更新一次 $\theta$。

由下图不难看出，策略梯度实际是 on-policy 算法，每完成一轮训练，由于$\theta$ 改变，需要 re-smaple 数据，供下一次的训练 $\Rightarrow$ 训练效率太低，如 Fig 6 所示。

Fig 6. Policy Ascent 采样-更新过程

3.1.2 PPO

policy gradient 策略梯度为 on-policy 算法，每轮更新参数 $\theta$ 均需要 smaple 一次，训练效率较低。如果将目标策略和行为策略分离，将 $\theta $ 换为 $\theta’$，用 $\pi_{\theta’}(s)$ 在参数 $\theta’$ 下多收集一些数据，来训练 $\theta$，实现用同一批数据多次更新参数。

重要性采样

采样的目的一般是评估一个概率分布函数在某个分布上的期望值。 $p$ 是一个概率分布，$f(x)$ 即为概率密度，假设不能对 $f(x)$ 求积分，则只能从分布 $p$ 中采集一些数据 $x^i$ 求平均值近似期望：

$E_{x\sim p}[f(x)]\approx\frac{1}{N}\displaystyle\sum_{i=1}^Nf(x^i),x\sim p$ 若不能从 $p$ 中 sample 数据，则需要做一个修改：

\[E_{x\sim p}[f(x)]= \int f(x)p(x) = \int f(x)\frac{p(x)}{q(x)}q(x) = E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]\]

上述式子即为重要性采样，其核心思想是利用一个已知的概率分布来近似计算目标概率分布的期望或积分，$\frac{p(x)}{q(x)}$ 即为重要性权重，用于修正两个分布之间的差异。

on-policy → off-policy

on-policy → off-policy 过程利用重要性采样，训练的是参数 $\theta$ 下的 Actor，参数 $\theta’$ 的 Actor 只是去与环境做互动。

\[\begin{align*} \nabla\stackrel{-}{R}_{\theta} &= E_{\tau\sim p_\theta(\tau)}[R(\tau) \nabla log\ p_\theta(\tau)] \\ &= E_{\tau\sim p_{\theta'}(\tau)}[\frac{p_\theta(\tau)}{p_{\theta'}(\tau)}R(\tau) \nabla log\ p_\theta(\tau)] \\ &=E_{(s_t,a_t)\sim \pi_{\theta'}}[\frac{p_\theta(s_t,a_t)}{p_{\theta'}(s_t,a_t)}A^{\theta'}(s_t,a_t) \nabla log\ p_\theta(a^n_t|s^n_t)] \\ &=E_{(s_t,a_t)\sim \pi_{\theta'}}[\frac{p_\theta(a_t|s_t)}{p_{\theta'}(a_t|s_t)}\frac{p_\theta(s_t)}{p_{\theta'}(s_t)}A^{\theta'}(s_t,a_t) \nabla log\ p_\theta(a^n_t|s^n_t)] \end{align*}\]

上面的推理需要解释一下，第二行中 $E_{\tau\sim p_{\theta’}(\tau)}[\frac{p_\theta(\tau)}{p_{\theta’}(\tau)}R(\tau) \nabla log\ p_\theta(\tau)]$ 是整个轨迹的更新公式，实际等价于 $E_{\tau\sim p_{\theta’}(\tau)}[\displaystyle\sum_{t=0}^{T}\frac{p_\theta(s_t,a_t)}{p_{\theta’}(s_t,a_t)}G_t \nabla log\ p_\theta(a_t|s_t)]$，将轨迹分到每一步中，所以求和符号可以消去。

而 $G_t$ 是给定了动作 $a_t$ 下的期望回报，可以使用 $Q(s_t, a_t)$ 表示，而为了稳定，通常减去 $V(s_t)$ 均值，从而使用优势函数 $A^\pi(s_t, a_t)=Q^\pi(s_t, a_t)-V^{\pi}(s_t)$ 替换 $G_t$（梯度上升优化的是当前动作的概率，$V(s_t)$ 与 $a_t$ 无关，不影响采取动作的奖励期望），从而得到第三行的表示，从 trajectory 层面的目标转换成单步优势函数。

令 $\frac{p_\theta(s_t)}{p_{\theta’}(s_t)}=1$ 表示 $\theta’$ 和 $\theta$ 看到的 state 一致。这一项很难计算，state 出现的概率是由数据控制，且 state 与 $\theta$ 关系并不大，得：

\[\nabla\stackrel{-}{R}_{\theta} = E_{(s_t,a_t)\sim \pi_{\theta'}}[\frac{\nabla p_\theta(a_t|s_t)}{p_{\theta'}(a_t|s_t)}A^{\theta'}(s_t,a_t)]\quad \nabla f(x)=f(x)\nabla log(f(x))\]

由于这是 grad 后的结果，两边除去 grad，得最终要优化的函数：

\[J^{\theta'}(\theta)=E_{(s_t,a_t)\sim \pi_{\theta'}}[\frac{ p_\theta(a_t|s_t)}{p_{\theta'}(a_t|s_t)}A^{\theta'}(s_t,a_t)]\]

重要性采样的问题

所选已知概率分布 $q$ 如果与原概率分布 $p$ 相差太大，会导致权重 $\frac{p(x)}{q(x)}$ 非常不均匀，部分样本的权重过大，导致方差急剧增加，从而在有限样本下完全不能逼近 $R(\tau)$，奖励波动大，梯度更新不稳定。

信任域策略优化（TRPO）[1] 通过引入约束，强制要求新旧策略相差不大，优化目标如下所示：

\[\begin{align*} \max_\theta \quad & \mathbb{E}_{(s_t,a_t) \sim \pi_{\theta'}} \Big[ \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta'}(a_t|s_t)} \, A^{\pi_{\theta'}}(s_t, a_t) \Big] \\ \text{s.t.} \quad & \mathbb{E}_{s_t \sim \pi_{\theta'}} \Big[ D_{KL}(\pi_{\theta'}(\cdot|s_t) \;\|\; \pi_\theta(\cdot|s_t)) \Big] \le \delta \end{align*}\]

其中，KL 散度约束计算公式为：

\[D_{KL}(\pi_{\theta'}(\cdot|s_t) \;\|\; \pi_\theta(\cdot|s_t)) = \sum_{a \in A} \pi_{\theta'}(a|s_t) \log \frac{\pi_{\theta'}(a|s_t)}{\pi_\theta(a|s_t)}\]

PPO Algorith 1

PPO1（Proximal Policy Optimization）是一种在 TRPO 基础上简化的策略优化方法，通过多次使用同一批样本进行更新，并引入 KL 惩罚控制策略变化。

初始化
- 初始化策略参数 $\theta^0$。
每轮迭代
对第 $k$ 轮迭代的策略参数 $\theta^k$：
1. 与环境交互
  - 使用当前策略 $\pi_{\theta^k}$ 采样状态-动作对 ${(s_t, a_t)}$；
  - 估计优势函数 $A^{\theta^k}(s_t, a_t)$。
2. 策略训练
  - 使用收集的数据多次更新策略参数 $\theta$，最大化以下目标函数： $J_{PPO}^{\theta^k}(\theta) = J^{\theta^k}(\theta) - \beta \, KL(\pi_{\theta^k} \;|\; \pi_\theta)$
    其中： $J^{\theta^k}(\theta) \approx \sum_{(s_t,a_t)} \frac{\pi_\theta(a_t\|s_t)}{\pi_{\theta^k}(a_t\|s_t)} A^{\theta^k}(s_t,a_t)$
    - $\beta$ 为 KL 惩罚系数，用于限制策略更新幅度；
    - 重要性采样比 $\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta^k}(a_t|s_t)}$ 用于调整旧策略数据对新策略的贡献。
3. 参数更新
  - 在适当时机，将训练后的 $\theta$ 赋值给 $\theta^k$，进入下一轮迭代。

PPO Algorith 2

而 PPO 算法则消除了 KL 散度函数，通过 $clip(\frac{p_\theta(a_t|s_t)}{p_{\theta^k(a_t|s_t)}},1-\epsilon,1+\epsilon)$ 函数约束$(\theta,\theta^k)$之间的差距，使二者比值落于 $[1-\epsilon,1+\epsilon]$ 区间内，如 Fig 7 所示。

Fig 7. PPO algorithm 2

3.2 Critic

3.2.1 DQN/DDQN

深度 Q 网络 (deep Q-network, DQN)：基于深度学习的 Q-learning，$Q_{\pi}$ 使用神经网络技术（替换原本的 Q-table），隐式地确定出 policy $\pi$。一般实现采用 DDQN，即分为行动策略 $\mu$ 和目标策略 $\pi$，网络如图 Fig 8 所示。

\[Q(s_t,a_t)↔r_t+Q'(s_{t+1},arg\ \mathop{max}\limits_{a'}\ Q(s_{t+1},a'))\]

Fig 8. DDQN

DDQN 实现能够解决 DQN 中因 $max_{a’} Q(s_{t+1},a’)$ 引入的偏差（overestimation bias）。在 DDQN 中，由于选 action 的 $\mu$【Q】和算 value 的 $\pi$ 【Q’】不是同一个函数，若 $Q$ over-estimate 所选动作a，只要 $Q’$ 没有高估动作 a 的值，就会回归正常；若 $Q’$ over-estimate 亦然，因为损失函数 $Loss=(y_i-Q_\theta(s_i,a_i))^2$，$y_i$ 代表目标网络固定值：

\[\begin{align*} y_i= \begin{cases} r_i &对于终止状态s_{i+1}\\ \\ r_i+\gamma\mathop{max}\limits_{a'}Q_\theta(s_{t+1},a')&对于非终止状态s_{i+1} \end{cases} \end{align*}\]

3.2.2 经验回放 (Replay Buffer)

智能体与环境交互生成的样本通常是高度相关的时间序列 $(s_t, a_t, s_{t+1}, a_{t+1})$，直接用这些序列去训练 Q 网络效率低且样本差异不大。

而 Replay Buffer 是一个缓存，用来存储智能体与环境交互得到的经验，训练时不是按时间顺序直接更新，而是随机从缓存中采样一小批样本，如图 Fig 9 所示。

Fig 9. Replay Buffer

3.2.3 Dueling DQN

$Q(s,a)$ 在离散动作空间中，可以被视作为一张表格。而已知 $Q(s,a)=V(s)+A(s,a)$，竞争深度 Q 网络对 $Q(s,a)$ 进行拆分，分成两个部分的加和：$V(s)$ 和 $A(s,a)$，$Q(s,a)$ 不再某个网络的直接输出，而是两个网络结构结果的加和，$A(s,a)$ 同样是一张表，$V(s)$ 是一个 scalar，$Q(s,a)$ 即 $A(s,a)$ 所有元素加上一个 scalar，具体结构如图 Fig 10 所示。

Fig 10. Replay Buffer

这样拆解的好处是不需要将所有 state-action都采样，未被采样的数据也会被更新，数据使用较为高效。但缺点也同样明显：

若 $V(s)=0$，dueling DQN 就回到 DDQN 的结构，多此一举
约束 $A(s,a)$ 每一列之和为0的真正目的是保留 $V(s)$ 的影响，希望确保状态值 $V(s)$ 不会完全被优势函数 $A(s,a)$ 所抵消，因为$A(s,a)$只要归一化操作，列和恒为0

3.3 Actor-Critic

3.3.1 A2C 算法

原始 A2C 算法如下图 Fig 11 所示。

Fig 11. A2C

原始 A2C 算法的缺点，需要估计 $Q^{\theta}(s_t,a_t)-V^\theta(s_t)$ 中两个 network 带来的双倍风险，而 policy gradient 中所有 reward 均有随机性，故做如下改进：

\[Q^\pi(s^n_{t+1})=E[r_t^n+V^\pi(s^n_{t+1})]\]

将期望符号去除 (A2C实验中此方式效果最好)，得 $Q^\pi(s^n_{t+1})=r_t^n+V^\pi(s^n_{t+1})$，再将表达式代入原A2C算法表达式，得：

$A^{\theta}(s_t,a_t)=\sum_{t'=t}^{T_n}\gamma^{t'-t}r_{t'}^n-b=r^n_t+V^\pi(s^n_{t+1})-V^\pi(s^n_t)$ 此时，A2C 方法只需 estimate V-function network 的风险。

3.3.2 A3C 算法

A2C 算法的缺点是训练太慢，A3C (Asynchronous Advantage Actor-Critic) 本质逻辑是开启多个 worker 共同训练，架构如 Fig 12 所示。A3C 不存储历史经验，虽然看起来是 off-policy 算法，但实际是 on-policy 算法，通过平行探索来保持训练稳定性。

Fig 12. A3C

3.3.3 DDPG 算法

深度确定性策略梯度 (deep deterministic policy gradient, DDPG) 目的是将 DQN 扩展到连续动作空间。所以在 DQN 基础上，用一个确定性的策略网络直接输出动作值。

在 DQN 中，目标 Q 值通过 $r+\gamma * max_{a’}Q(s’, a’)$ 更新，由于连续动作空间中，没法计算所有的 $a’$。因此，DDPG 的 Actor 直接输出当前最佳动作 $a’$ 数值，然后将 $s’$ 和 $a’$ 输入到 Critic 中。

\[Loss_{Critic} = \text{MSE}[ \underbrace{Q_w(s, a)}\_{\text{当前估计}}, \underbrace{r + \gamma Q_{w'}(s', \mu_{\theta'}(s'))}\_{\text{目标值}} ]\]

而 Actor 的目标则是最大化 $Q_w(s,\mu_{\theta}(s))$。

Fig 13. DDPG 算法

3.3.4 SAC 算法

Soft Actor-Critic (SAC) [2]

// TODO

四、多智能体强化学习（MARL）

4.1 QMIX

问题：信度分配，VDN 是通过简单求和累加进行拆分，拟合能力有限，不能体现团队每个 Agent 的具体贡献。

方法 / 网络架构：每个 Agent 的 $Q_a$ 网络，$Q_tot$ 由 Agent的独立网络混合而成，具体如图 Fig 14 所示。

智能体网络：接收该智能体的局部观测 $o_a$ 作为输入，输出其个体价值函数 $Q_a(o_a, u_a)$，用于评估自己采取每个可能动作 $u_a$ 的好坏；
混合网络：QMIX [3] 核心，是一个前馈神经网络，将所有智能体网络的输出 $Q_a$ 作为输入，并将它们非线性地混合，最终输出团队的联合价值 Q_tot；
超网络：将全局状态 $s_t$ 作为输入，输出混合网络的权重和偏置。巧妙地将全局信息融入值函数分解过程的方式。

Fig 14. QMIX 架构

QMIX 为了保证去中心化执行的有效性，不需要 $Q_tot$ 和 $Q_a$ 的值完全相等，只需要保证一个全局 argmax 操作在 $Q_tot$ 上的结果，与在一系列 $Q_a$ 上分别进行局部 argmax 的结果是一致的。

这个约束的直观解释是：如果某个智能体通过选择更好的动作提高了自己的 $Q_a$ 值，那么整个团队的 $Q_tot$ 值也必须随之增加（或保持不变），绝不能降低。

局限： 单调性的约束是有一定问题的，当团队最优解要求某个或某些智能体执行对其自身而言是次优的动作时，QMIX 会因其代表能力限制而无法学习到该最优解。

4.2 IPPO

每个智能体独立运行 PPO 算法，使用团队奖励 $r(s_t,a_t)$ 当作每个智能体奖励 $r(z_t^a,u_t^a)$，从而每个智能体的更新公式如下所示（其实和 PPO 没啥区别）。

\[A_t^a = \sum_{l=0}^{h} (\gamma\lambda)^l \delta_{t+l}^a\]

其中，TD Error $\delta_t^a = r_t(z_t^a, u_t^a) + \gamma V_{\phi}(z_{t+1}^a) - V_{\phi}(z_t^a)$。而每个智能体的更新公式为：

\[\mathcal{L}^a(\theta) = \mathbb{E}_{z_t^a, u_t^a}\left[\min\left(\frac{\pi_\theta(u_t^a|z_t^a)}{\pi_{\theta_{old}}(u_t^a|z_t^a)}A_t^a, \text{clip}\left(\frac{\pi_\theta(u_t^a|z_t^a)}{\pi_{\theta_{old}}(u_t^a|z_t^a)}, 1-\epsilon, 1+\epsilon\right)A_t^a\right)\right]\]

博客 [5] 中分析了 IPPO 的优势，总结是 Critic 估计的 Value值含有噪音扰动（每个agent的critic输入都不一样了），从而提升了算法的探索性能，避免收敛到局部最优。

现有大部分的 MARL 算法可能没有突破 IPPO 这个 Baseline，即使将 PPO 扩展到 MARL 的 MAPPO [3] 也未能完全突破 IPPO。

文末附上 RL 面试八股，具体链接见 [6] 。

Reference

[1] Schulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms[J]. arXiv preprint arXiv:1707.06347, 2017.

[2] Haarnoja T, Zhou A, Abbeel P, et al. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[C]//International conference on machine learning. Pmlr, 2018: 1861-1870.

[3] Rashid T, Samvelyan M, De Witt C S, et al. Monotonic value function factorisation for deep multi-agent reinforcement learning[J]. Journal of Machine Learning Research, 2020, 21(178): 1-51.

[4] Yu C, Velu A, Vinitsky E, et al. The surprising effectiveness of ppo in cooperative multi-agent games[J]. Advances in neural information processing systems, 2022, 35: 24611-24624.

[5] 简单分析MARL中为什么IPPO效果比MAPPO好？

[6] 强化学习面试题及答案

This post is licensed under CC BY 4.0 by the author.