RL——AlphaGo系列算法

AlphaGo整体说明

AlphaGo是强化学习的阶段性集大成者，其核心思想值得细细推敲

AlphaGo棋局介绍

AlphaGo 的目标是解决围棋对弈问题 ，即在标准的 19×19 围棋棋盘上（共381维），通过观察棋盘情况选择最优的落子动作，击败对手
输入：当前棋盘状态（包括棋子分布和历史信息）
输出：下一步落子的最优位置（或概率分布）
挑战：
- 围棋的状态空间复杂度高达 $3^{361}$（约$10^{172}$量级），无法暴力搜索
- 围棋的决策步长约100+步，决策需要结合长期策略收益
- 围棋的评估函数难以设计（难以量化当前局面是否有“局面优势”）

ALphaGo问题建模

状态空间：$19 \times 19 \times N$，这里的N在不同版本不一样，比如17=16+1时，16是用于记录最近 8 步的状态（相当于记录了窗口），1则表示该哪一方下棋，其他还有一些需要理解围棋规则才能解释
动作空间：离散动作空间，362个动作可选（361位置 + 1 Pass）
奖励函数：对局结束时，胜利方奖励+1，失败方-1，平局为0（围棋通常无平局）

AlphaGo 训练过程（分三个阶段）

第一阶段：行为克隆（监督学习模仿人类专家）

基于 KGS 围棋平台上的 3000 万局人类对弈棋谱，学习人类专家的落子的模式
通过监督学习训练一个策略网络（Policy Network） ，输入棋盘状态，输出人类选手的落子概率分布
- 网络结构：13 层卷积神经网络（CNN）
- 准确率：57%（预测人类下一步动作）

第二阶段：强化学习（自我对弈优化，策略梯度优化）

通过策略梯度法，进一步优化策略网络，超越人类水平
- 自我对弈 ：使用初始策略网络生成大量自我对局数据
- 策略梯度 ：通过胜负结果优化策略网络（即强化学习策略网络），使其更倾向于获胜的走法
- 回报函数 ：对局结束时获胜方获得 +1 奖励，失败方获得 -1

第三阶段：价值网络学习（局面评估）

价值网络学习阶段的目标是训练一个价值网络（Value Network） ，预测当前局面的胜率（替代蒙特卡洛rollout的耗时评估）
通过自我对弈生成 3000 万组棋盘状态及最终胜负结果，学习一个标量值（-1 到 +1），表示当前玩家获胜的概率

AlphaGo 决策过程

AlphaGo 的实时决策基于蒙特卡洛树搜索（MCTS） ，结合神经网络的输出：
选择（Selection） ：从根节点（当前棋盘状态）出发，通过树策略（如UCT算法）选择子节点，平衡探索与利用，使用策略网络优先选择高概率的落子分支
扩展（Expansion） ：当遇到未探索的节点时，用策略网络生成可能的落子概率，扩展树结构
Evaluation 对价值网络评估胜率，和策略网络模拟rollout到终局得到的奖励两者做加权结合
回溯（Backup） ：将叶子节点的评估结果反向传播更新路径上的节点统计量（访问次数、平均胜率）
最终决策（Decision） ：搜索结束后，选择访问次数最多的节点对应的落子动作

AlphaGo 相关思考

以模仿学习作为强化学习策略的冷启动是个不错的想法
使用MCTS来决策有助于提升模型决策能力，在MCTS下，随着围棋的进行，搜索空间变小，AlphaGo相对人类的优势会越来越明显

附录：AlphaGo 的迭代版本

版本	发版时间	训练数据	核心算法	计算需求	棋力提升
AlphaGo Fan	2015年10月	人类棋谱（监督学习）	SL + MCTS	中等（分布式计算）	首次击败职业棋手（樊麾）
AlphaGo Lee	2016年3月	人类棋谱 + 自我对弈	SL + RL + MCTS + 价值网络	高（1202 CPU + 176 GPU）	超越人类顶尖（李世石）
AlphaGo Master	2017年1月（Master） 2017年5月（正式对战柯洁）	纯自我对弈	纯RL + 深度网络	低（单机）	完胜人类第一柯洁
AlphaGo Zero	2017年10月	从零开始自我对弈	纯RL + ResNet + MCTS	极低（4 TPU）	100:0击败AlphaGo Lee
AlphaZero	2017年12月	多棋类自我对弈	通用RL + 高效搜索	低（单机）	8小时超越AlphaGo Zero

RL——BCQ

参考链接：【笔记】BCQ详解
- 原作者的PPT
参考链接：BCQ姊妹篇：Discrete BCQ - Metaqiang的文章 - 知乎
参考链接：【代码速读】（RL）1.BCQ - 一条的文章 - 知乎

BCQ 整体介绍

BCQ（Batch-Constrained deep Q-learning）分为连续版本（Off-Policy Deep Reinforcement Learning without Exploration，2019年8月）和离散版本（Benchmarking Batch Deep Reinforcement Learning Algorithms，2019年10月）两篇文章，一作是同一个作者
外推误差(Extrapolation Error)的定义：off-policy值学习中，当前策略真实状态动作访问分布和数据集中的状态动作分布不匹配导致的一种误差

Extrapolation error is an error in off-policy value learning which is introduced by the mismatch between the dataset and true state-action visitation of the current policy
背景：off-policy的策略理论上可以从任意行为策略采样的数据中学习最优策略，但是直接将off-policy策略应用到Offline RL（也称为Batch RL）场景中可能面临，Absent Data（状态动作对缺失），Training Mismatch（训练预测分布不一致），Model Bias（随机MDP的状态转移概率有偏差）等问题
BCQ的基本思想：采取保守策略，让学到的策略对应的状态动作访问空间尽量只在出现过的数据集上，或者相近的数据上
- 基本方法：主要通过限制 $Q(s’,\pi(s’))$ 中的 $\pi(s’)$ 不要偏离数据集太多来实现

BCQ 连续版本

关键实验

实验设置：
- 第一个实验(Final Buffer)，使用DDPG算法在线训练一个智能体，将智能体训练过程中与环境交互的所有数据保存下来，利用这些数据训练另一个离线DDPG智能体
- 第二个实验(Concurrent)，使用DDPG算法在线训练一个智能体，训练时每次从经验回放池中采样，并用相同的数据同步训练离线DDPG智能体，甚至保持训练时使用的数据和数据顺序都完全相同
- 第三个实验(Imitation)，使用DDPG算法在线训练一个智能体，将该智能体作为专家，与环境交互采集大量数据，利用这些数据训练另一个离线DDPG智能体
实验结果：
- 第三个实验中使用的样本最好，但是训练得到的离线智能体效果最差，原因分析主要是外推误差导致
- 三个实验的离线DDPG智能体都有不同情况的Q值高估问题，其中第三个实验的Q值高估问题最为严重（注意图2中看起来高估问题大于图1中，其实不是，是因为图二的量纲较小导致的）

理论推导

对于给定的真实MDP和数据集 $\mathcal{B}$，定义外推误差
$$\epsilon_\text{MDP}(s,a) = Q^\pi(s,a) - Q_{\mathcal{B}}^\pi(s,a)$$
则有外推误差可推导得到如下结论：

训练流程

整体流程概览:
训练流程解释：
- 训练时，使用4个Q网络（其中两个是Target Q网络），1个策略网络和扰动网络
- 两个Q网络的用途是在计算Q值目标时做他们最大最小值的凸组合（实际上就是最大最小值的加权平均），类似Twin Q中取两个Q的最小值的方法， $y$ 值计算方法（流程中 $\color{red}{\text{公式(13)}}$ ）
  $$ y = r + \gamma \max_{a_i}\Big[ \lambda \min_{j=1,2}Q_{\theta_j}(s’,a_i) + (1-\lambda)\max_{j=1,2}Q_{\theta_j}(s’,a_i) \Big] $$

Serving步骤

给定一个状态 $s$
$\{ a_i \sim G_w(s) \}_{i=1}^n$：通过conditional VAE网络 $G_w(s)$ 采样 $n$ 个动作
$\xi_{\phi}(s,a_i,\Phi)$：将这些状态和动作经过扰动网络，扰动网络输出是在 $[-\Phi,\Phi]$ 内的，得到的扰动值
将扰动添加到原始动作上，再将动作经过Q网络，选取能使Q value最大的动作
最终总结如下：
$$ \pi(s) = \mathop{\arg\max}_{a_i + \xi_{\phi}(s,a_i,\Phi)} Q_\theta(s, a_i + \xi_{\phi}(s,a_i,\Phi)), \quad with \quad \{ a_i \sim G_w(s) \}_{i=1}^n $$
训练流程解释：
- 相对普通的DQN，主要改进点在于学习Q的目标值选择时动作受到限制，动作与行为策略（离线数据集）的动作差异不能太大
- 学习Q值时，使用的是Huber Loss
  $$
  l_{\mathcal{k}}(\delta) =
  \begin{cases}
  \ 0.5\delta^2& \text{if}\ \delta \le \mathcal{k}\\
  \mathcal{k}(|\delta| - 0.5\mathcal{k})& \text{otherwise.}
  \end{cases}
  $$

BCQ 离散版本

训练流程

整体流程概览:

Serving 步骤

按照如下策略决策：
$$ \pi(s) = \mathop{\arg\max}_{a\vert\frac{G_w(a|s)}{\max_\hat{a} G_w(\hat{a}|s)} \gt \tau} Q_\theta(s,a) $$

RL——CQL

参考链接：
- 原始论文：NIPS 2020, Conservative q-learning for offline reinforcement learning
- 【论文分享】Conservative Q-Learning for Offline Reinforcement Learning
- Conservative Q-Learning for Offline Reinforcement Learning：手打公式
- 离线强化学习系列3(算法篇): 值函数约束-CQL算法详解与实现：手打公式
- github.com/aviralkumar2907/CQL：CQL实现源码

CQL 在解决什么问题？

分布偏移（distribution shift） ：分布偏移主要是模型训练和预测时的分布存在差异，即训练数据集中的数据分布（训练）与实际决策策略下环境反馈的数据分布（预测）之间的差异。
- 这种差异可能导致学习到的策略在实际应用中表现不佳，因为该策略是在一个与实际环境不完全相同的数据分布上学习得到的
- 离线强化学习中这种问题会放大，特别地，会导致OOD问题
OOD（Out-of-distribution） ：OOD通常指在训练集中没有被观察到过的样本（状态或状态-动作对），实际上，出现频率极低的样本也可以算作一定程度上的OOD样本
- OOD问题是由于分布偏移导致的，理论上，没有分布偏移问题就不存在OOD问题 ，因为模型不会遇到这些未观察过的样本
OOD 问题容易导致值高估（Overestimation of values）问题 ：强化学习的迭代公式一般都是找时的动作最大的动作，这本身导致的容易值高估的现象

CQL 相关推导

一些定义

数据集 $\mathcal{D} \sim d^{\pi_{\beta}}(\mathbf{s})\pi_{\beta}(\mathbf{a} \mid \mathbf{s})$，即数据是行为策略 $\pi_\beta$ 与环境交互来得到的
对于任意 $(s_0, a_0) \in \mathcal{D}$，有经验行为策略（empirical behavior policy）为：
$$ \hat{\pi}_\beta(a_0\vert s_0) = \frac{\sum_{(s,a) \in \mathcal{D}}\mathbf{1}(s=s_0,a=a_0)}{\sum_{s\in \mathcal{D}}\mathbf{1}(s=s_0)} $$

回顾贝尔曼算子

一般的贝尔曼算子(Bellman Operator)，写作 $\mathcal{B}^\pi$，重复对 $Q(s,a)$ 使用 $\mathcal{B}^\pi$，持续迭代可收敛到策略 $\pi$ 对应的Q值 $Q^{\pi}(s,a)$ 值:
$$
\mathcal{B}^\pi Q = r(s, a) + \gamma \mathbb{E}_{s^\prime \sim p(s^\prime \vert s, a), a^\prime \sim \pi(a^\prime\vert s^\prime)}[Q (s^\prime, a^\prime)]
$$
Q-Learning的迭代公式，相当于策略是找Q值最优的那个动作，通过对Q重复使用如下贝尔曼最优算子（Bellman Optimality Operator），写作 $\mathcal{B}^{\pi^*}$ 或者 $\mathcal{B}^*$：
$$ \mathcal{B}^{*} Q(\mathbf{s}, \mathbf{a})=r(\mathbf{s}, \mathbf{a})+\gamma \mathbb{E}_{\mathbf{s}^{\prime} \sim P\left(\mathbf{s}^{\prime} \mid \mathbf{s}, \mathbf{a}\right)}\left[\max _{\mathbf{a}^{\prime}} Q\left(\mathbf{s}^{\prime}, \mathbf{a}^{\prime}\right)\right] $$

Offline RL 中的贝尔曼算子

在 Offline RL 中，我们定义新的贝尔曼算子 $\hat{\mathcal{B}}^\pi$，即更新只在固定数据集上进行，即对于给定的数据集 $\mathcal{D} = { (s,a,r,s’)} \sim \pi_\beta$， $\hat{\mathcal{B}}^\pi$ 的更新都发生在数据集上
对于给定数据集 $\mathcal{D} \sim \pi_\beta$ 上的贝尔曼算子 $\hat{\mathcal{B}}^\pi$，我们定义 $\hat{\mathcal{B}}^\pi$ 如下：
$$
\hat{\mathcal{B}}^\pi \hat{Q} = r(s, a) + \gamma \mathbb{E}_{s^\prime \sim \mathcal{D}, a^\prime \sim \pi(a^\prime\vert s^\prime)}[\hat{Q} (s^\prime, a^\prime)]
$$

如果在 Offline RL 中使用常规AC方法会发生什么？

Actor-Critic的策略迭代定义为（这种限定数据集的做法是被迫的，因为没法与环境交互）：
$$
\begin{align}
\hat{Q}^{k+1} &\leftarrow \mathop{\arg\min}_{Q} \mathbb{E}_{s,a,s^\prime \sim \mathcal{D}}\left[ \left( r(s,a) + \gamma\mathbb{E}_{a^\prime \sim \hat{\pi}^{k}(a^\prime| s^\prime)}[\hat{Q}^k(s^\prime, a^\prime)] - Q(s, a) \right)^2 \right] \ &\text{(policy evaluation)}\\
\hat{\pi}^{k+1} &\leftarrow \mathop{\arg\max}_{\pi} \mathbb{E}_{s\sim \mathcal{D}, a\sim \pi(a\vert s)}\left[ \hat{Q}^{k+1} (s,a) \right] \ &\text{(policy improvement)}
\end{align}
$$
- 以上公式来自论文，原始论文中使用的是 $a \sim \pi^k(a|s)$，这里应该改成 $a \sim \pi(a|s)$ 更合适，因为argmax的目标参数是 $\pi$，所以我改成了 $a \sim \pi(a|s)$ 表示找到最优的策略 $\pi$，使得按照这个策略决策（采样或者选择动作）得到的期望收益Q值是最大的
- 其实AC方法中，包含了DQN的迭代思路，策略迭代部分， $a’$ 始终取上一轮Q值最大的动作即可
- policy evaluation实际上就是在重复对Q使用贝尔曼算子，只是使用最小化均方误差的形式去实现了
问题：Offline RL场景中直接使用上面的策略迭代会面临分布偏移问题 ，从而导致高估：
- 理解：1）目标Q值的计算应该使用当前策略 $\pi^k$，但是数据集中只有从数据集 $\mathcal{D}$ 中采样到的样本，对应策略 $\pi_\beta$，极端情况下，策略 $\pi^k$ 采样到的动作 $a’ \sim \pi^k$ 可能从未在数据集中出现过，此时模型是无法准确评估 $Q(s’,a’)$ 的；2）常规的迭代方法中，一般都包含着 $a’ = \mathop{\arg\max}_a Q(s,a)$ 或者隐式的包含了 $Q(s, a) = r + \max_{a} Q(s^\prime, a)$ 这样的思想，此时预估值 $Q(s’,a’)$ 低估不会出现问题，但是 $Q(s’,a’)$ 一旦高估，该动作就会被选中作为目标值；3）Offline RL场景中没有机会引入新样本来重新修正 $Q(s’,a’)$ 的高估
- 在Online RL的场景中，一般不存在该问题，因为一个动作被错误的高估以后，往往会在策略跟环境的交互中选中该动作，从而使得该动作被修正
总结一下：对于策略 $\pi$，我们的真实Q值是 $Q^\pi$，在固定的数据集下学到的是 $\hat{Q}^\pi$，但该值一般往往会高估，我们的目标是让 $\hat{Q}^\pi$ 尽量接近真实值 $Q^\pi$，那么面临的往往是高估这个问题，CQL算法的核心思想就是解决这个问题

改进一：打压未知动作的Q值

对于任意的未知策略 $\mu$，在行为策略 $\pi_\beta$ 交互收集到的数据集 $\mathcal{D}$ 中进行训练，其状态动作对访问分布为 $\mu(s, a)=d^{\pi_\beta}(s) \mu(a \mid s)$，我们的目标通过最小化未知策略采样到的动作对应的Q值，来实现Q值的保守学习：
$$\hat{Q}^{k+1} \leftarrow \arg \min_{Q} \color{red}{\alpha} \mathbb{E}_{\mathbf{s} \sim \mathcal{D}, \mathbf{a} \sim \mu(\mathbf{a} \mid \mathbf{s})}[Q(\mathbf{s}, \mathbf{a})]+\frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]$$
使用 $\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}$ 的原因是因为想强调 $\hat{\mathcal{B}}^{\pi}$ 使用的 $s’$ 不是按照环境的状态转移概率算的，而是直接使用的数据集中的内容
上面的迭代公式学到的是 $\hat{Q}^\pi$ (其中 $\hat{Q}^\pi := \lim_{k\rightarrow \infty}\hat{Q}^k$)
为了方便表达，一些论文或博客会使用 $\mathcal{L}_{Bellman}(Q) = \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]$ 来替换等号后面的式子
这里论文中给出了证明（Theorem 3.1）：
- 上式说明：
  - 当 $supp\ \mu \subset supp\ \pi$ （ $supp\ \mu$ 表示支持集），且 $\alpha$ 足够大时， $\forall \ s\in\mathcal{D},a\in \mathcal{A}$，均有 $\hat{Q}^\pi(s,a) \le Q^\pi(s,a)$ 成立。即对于任意的分布 $\mu$，只要我们这里 $\alpha$ 取得足够大，总能学到一个比真实值 $Q^\pi(s,a)$ 小的Q值
  - 当 $supp\ \mu \subset supp\ \pi$，且 $\hat{B^\pi} = \mathcal{B}^\pi, \ \alpha > 0$ 时，对 $\forall \ s\in\mathcal{D},a\in \mathcal{A}$，均有 $\hat{Q}^\pi(s,a) \le Q^\pi(s,a)$ 成立。即如果我们的数据集可以反映真实的数据分布，那么数据偏移就不存在了，我们直接令 $\alpha=0$，退化到常规的贝尔曼算子对应的损失函数即可（注：此时的数据集 $\mathcal{D}$ 是从当前策略采样的，故 $\alpha=0$ 后的式子就是常规贝尔曼算子对应的损失函数）
- 在概率论和机器学习中，当我们说两个离散概率分布 $\mu(a|s)$ 和 $\pi(a|s)$ 满足 $supp\ \mu \subset supp\ \pi$，这意味着 $\mu(a|s)$ 的支持集（即 $\mu(a|s)$ 分配了正概率的所有动作 $a$ 的集合）是 $\pi(a|s)$ 支持集的子集。换句话说，对于所有 $\mu(a|s)$ 给予正概率的动作 $a$， $\pi(a|s)$ 也必须给予正概率。简而言之，如果某个动作在 $\mu(a|s)$ 下是可能发生的（即它有非零的概率），那么在 $\pi(a|s)$ 下这个动作也是可能发生的。但是， $\pi(a|s)$ 可能包括一些 $\mu(a|s)$ 不考虑的动作，这些动作在 $\pi(a|s)$ 中有正概率但在 $\mu(a|s)$ 中没有或者为零概率

改进二：打压补偿

改进一学到了 $Q^\pi(s,a)$ 的逐点下界 $\forall \ s\in\mathcal{D},a\in \mathcal{A}$，均有 $\hat{Q}^\pi(s,a) \le Q^\pi(s,a)$，但直观上看，打压过于严格了，甚至行为策略采样到的状态动作对都会打压（其实这些地方我们能估准的），为了缓解这个问题，我们对改进一的打压做一些补偿：
$$\hat{Q}^{k+1} = \mathop{\arg\min}_Q \color{red}{\alpha} \left(\mathbb{E}_{s\sim \mathcal{D}, a\sim \mu(a\vert s)}[Q(s, a)] - \color{red} { \mathbb{E}_{s\sim \mathcal{D}, a\sim\hat{\pi}_\beta(a\vert s)}[Q(s, a)] } \right) + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]$$
这里论文中给出了证明（Theorem 3.2）：
- 上式说明：
  - 当 $\mu=\pi$ （注意，改进一种不需要这个约束），且 $\alpha$ 较大时，有 $\forall \ s\in\mathcal{D}$，均有 $\hat{V}^\pi(s) \le V^\pi(s)$
  - 当 $\mu=\pi$，且 $\hat{B^\pi} = \mathcal{B}^\pi, \ \alpha > 0$ 时，有 $\forall \ s\in\mathcal{D}$，均有 $\hat{V}^\pi(s) \le V^\pi(s)$
- 此时虽然不能再保证学到了 $Q^\pi(s,a)$ 的逐点下界： $\forall \ s\in\mathcal{D},a\in \mathcal{A}$，均有 $\hat{Q}^\pi(s,a) \le Q^\pi(s,a)$
- 但可以保证学到了 $Q^\pi(s,a)$ 的期望下界： $\mathbb{E}_{\pi(a|s)}[\hat{Q}^\pi(s,a)] \le V^\pi(s) = \mathbb{E}_{\pi(a|s)}[Q^\pi(s,a)]$

改进三：CQL($\mathcal{R}$)

一个遗留问题：论文中提到改进二需要进一步改进，但为什么不能直接用策略二，令 $\mu=\pi$，然后直接使用改进二的公式更新？原始论文关于改进二的缺点描述（原始论文中对这里的描述不够具体，缺乏说服力）
- 改进二已经说明了在 $\mu=\pi$ 时，可以学到一个合适的下界，但是由于改进二中需要对策略 $\mu$ （ $\mu=\pi$ ）进行采样，即每次迭代Q值时都需要上一轮的策略 $\pi$ 来采样，这样的话，智能交替进行策略评估和策略提升，且策略评估需要迭代足够长的步骤才能收敛，所以非常耗时（问题，常规的AC不都是这么实现的吗？其实也没有问题吧）
- 补充：CQL原始论文的描述截图
接下来，我们先假定论文中提到的改进二中的公式确实存在缺点，需要改进，那么可以做如下改进
我们可以进一步地优化，考虑到 $\pi$ 是使得Q值最大的策略，所以我们使用使得Q值最大的 $\mu$ 去拟合，改进二的公式可以优化为下面这样：
$$\hat{Q}^{k+1} = \min_Q \max_\mu \color{red}{\alpha} (\mathbb{E}_{s\sim \mathcal{D}, a\sim \color{red}{\mu(a\vert s)} }[Q(s, a)] - \mathbb{E}_{s\sim \mathcal{D}, a\sim\hat{\pi}_\beta(a\vert s)}[Q(s, a)]) + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right] + \color{red}{\mathcal{R}(\mu)} $$
- 为了防止寻找Q值最大化的 $\mu$ 时出现过拟合，我们增加正则项 $\mathcal{R}(\mu)$，一般取 $\mathcal{R}(\mu) = - D_{KL} (\mu| \rho)$，其中 $\rho$ 是一个已知分布

改进四：CQL($\mathcal{\rho}$)

在CQL($\mathcal{R}$)中，求解 $\mu$ 相当于要求解下面的优化问题
$$
\begin{align}
\max_{\mu} \mathbb{E}_{a \sim \mu(a|s)}[Q(s,a)]&\color{red}{-}D_{\mathrm{KL}}(\mu | \rho) \\
\text { s.t. } \quad \sum_{a} \mu(a|s)&=1 \\
\mu(a|s) &\geq 0, \ \forall \mathbf{a} .
\end{align}
$$
- 注意：论文附录中错误地将 $-D_{\mathrm{KL}}(\mu | \rho)$ 写成了 $+D_{\mathrm{KL}}(\mu | \rho)$ （因为上述公式的本意是最小化KL散度），需要修正过来
上述优化问题的最优解是：
$$
\mu^{*}(a|s)=\frac{1}{Z} \rho(a|s) \exp (Q(s,a))
$$
- 其中 $Z=\sum_a \rho(a\vert s)\cdot \exp(Q(s, a))$， $Z$ 也被称为归一化因子（normalizing factor）
- 以上优化问题求解的详细证明与AWR论文相似。更一般地，将以上变量 $a$ 替换成 $x$，即 $Q(s,a)$ 替换成 $f(x)$ 均可成立
最终我们有CQL($\mathcal{\rho}$)的表达形式：
$$
\hat{Q}^{k+1} = \min_Q \color{red}{\alpha} \mathbb{E}_{s\sim d^{\pi_\beta}(s)} \left[ \mathbb{E}_{a\sim \rho(a\vert s)} \left[ Q(s, a) \cfrac{\exp(Q(s, a))}{Z} \right ] - \mathbb{E}_{a \sim \hat{\pi}_\beta(a\vert s)}[Q(s, a)] \right] + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]
$$
- 原始论文中使用 $s\sim d^{\pi_\beta}(s)$，实际上与 $s \sim \mathcal{D}$ 等价，其他形式都是使用 $s \sim \mathcal{D}$
- 论文中，实验时取 $\rho(a \vert s) = \hat{\pi}^{k-1}(a \vert s)$，实验表格中的CQL($\mathcal{\rho}$)就是这个含义

改进五：CQL($\mathcal{H}$)

当CQL($\mathcal{\rho}$)中的 $\rho$ 是均匀分布时，有最优解：
$$
\begin{align}
\mu^*(a\vert s) &= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\sum_a \rho(a\vert s)\cdot \exp(Q(s, a))} \\
&= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\rho(a\vert s) \sum_a \exp(Q(s, a))} \\
&= \cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))}
\end{align}
$$
将 $\mu^*(a\vert s) = \cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))} $ 带入CQL($\mathcal{R}$)，可得CQL($\mathcal{H}$)：
$$
\hat{Q}^{k+1} = \min_Q \color{red}{\alpha} \mathbb{E}_{s\sim\mathcal{D}} \left[ \log \sum_a \exp(Q(s, a)) - \mathbb{E}_{a \sim \hat{\pi}_\beta(a\vert s)}[Q(s, a)] \right] + \frac{1}{2} \mathbb{E}_{\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]
$$
- 论文中，取 $\rho(a \vert s)$ 是均匀分布(即 $\rho(a|s)=\text{Unif}(a)$)时，相当于最大化策略熵，故称此时的更新方式为CQL($\mathcal{H}$)

CQL 伪代码

伪代码流程如下，其中CQL($\mathcal{R}$)可以是CQL($\mathcal{H}$)，也可以是CQL($\mathcal{\rho}$)：
如果是Q-learning模式：仅更新Q值即可，最后定义 $\mu(s) = \mathop{\arg\max}_a Q(s,a)$ 作为最终的策略
如果是Actor-Critic模式：需要使用SAC的训练方式额外训练actor

实践说明

$\alpha$ 的选择：
$\alpha$ 可以变成可学习的值？
$\log\sum_a \exp(Q(s,a))$ 的计算：
CQL($\mathcal{H}$)和CQL($\mathcal{\rho}$)谁更好？
- 一般来说 CQL($\mathcal{H}$)优于CQL($\mathcal{\rho}$)，当动作空间特别大时logsumexp预测方差变得很大，此时使用CQL($\mathcal{\rho}$)效果更好
一些超参数的设置：

一些说明和思考

CQL原始论文中符号使用有点混乱比如CQL($\mathcal{R}$),CQL($\mathcal{H}$)和CQL($\mathcal{\rho}$)三者的定义不清晰，特别是CQL($\mathcal{\rho}$)在正文中没有得到明确的定义，附录里面才有定义，而伪代码中强调的公式4：CQL($\mathcal{R}$)，实际上公式4是CQL($\mathcal{H}$)，这里我们特别对三个方法的定义进行辨析：
- CQL($\mathcal{R}$)：CQL原始形式
- CQL($\mathcal{\rho}$)：CQL变体，对任意 $\rho$ 均可使用这个表述，包含了后面的CQL($\mathcal{H}$)，论文中实验时使用的是 $\rho(a \vert s) = \hat{\pi}^{k-1}(a \vert s)$
- CQL($\mathcal{H}$)：CQL变体，当CQL($\mathcal{\rho}$)中 $\rho$ 取均匀分布时的更新形式
原始论文中 $s\sim d^{\pi_\beta}(s)$ 和 $s \sim \mathcal{D}$ 混用，比较公式时容易对不齐，实际上两者是等价的
从推导可以看出，数据越充足，需要的 $\alpha$ 就越小
问题：为什么直接更新改进二中的更新公式不可以？为什么训练耗时长？普通的AC不都是这么实现的吗？
- 普通AC确实是这样实现的，但是在Offline RL场景，不希望迭代效率过慢？
问题：为什么使用均匀分布以后，可以推导出CQL($\mathcal{H}$)的形式?
- 详请见附录推导
CQL算法得到的策略一定很优秀吗？答案是不会比行为策略差太多
- 具体来说(Theorem 3.6)：CQL算法得到的策略 $\pi^*(a|s)$ 是一个策略 $\hat{\pi}_\beta$ 的 $\zeta$ -safe policy improvement，即有 $1-\zeta$ 的概率可以保证 $J(\pi^*, M) \ge J(\hat{\pi}_\beta, M) - \zeta$

附录：证明约束优化问题

目标是求解下面的约束问题
$$
\begin{align}
\max {\mu} \mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[f(\mathbf{x})]&-D_{\mathrm{KL}}(\mu | \rho) \\
\text { s.t. } \quad \sum_{\mathbf{x}} \mu(\mathbf{x})&=1\\
\mu(\mathbf{x}) &\geq 0, \ \forall \mathbf{x}.
\end{align}
$$
需要证明上述式子的最优解为：
$$\mu^{*}(\mathbf{x})=\frac{1}{Z} \rho(\mathbf{x}) \exp (f(\mathbf{x}))$$
- 其中 $Z = \sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (f(\mathbf{x}))$
证明前，我们先将上述问题修改成更一般的形式（更一般的形式更常用一些），在更一般的形式下， $D_{\mathrm{KL}}(\mu | \rho)$ 经常会加上温度系数 $\alpha$ 或出现在约束中：
$$
\begin{align}
\max_{\mu} \mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[&f(\mathbf{x})] \\
\text { s.t. } \quad D_{\mathrm{KL}}(\mu | \rho) &\le \epsilon \\
\quad \sum_{\mathbf{x}} \mu(\mathbf{x})&=1\\
\mu(\mathbf{x}) &\geq 0, \ \forall \mathbf{x}.
\end{align}
$$
求解上面的问题可以先转换成构造拉格朗日函数
- 原始问题变形
  $$
  \begin{align}
  \min_{\mu} - \mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[&f(\mathbf{x})] \\
  \text { s.t. } \quad D_{\mathrm{KL}}(\mu | \rho) - \epsilon &\le 0 \\
  \quad \sum_{\mathbf{x}} \mu(\mathbf{x}) - 1 &= 0 \\
  \mu(\mathbf{x}) &\geq 0, \ \forall \mathbf{x}.
  \end{align}
  $$
- 拉格朗日函数如下
  $$
  \begin{align}
  L(\mu,\alpha,\beta) &= -\mathbb{E}_{\mathbf{x} \sim \mu(\mathbf{x})}[f(\mathbf{x})] + \alpha(D_{\mathrm{KL}}(\mu | \rho)-\epsilon) + \beta(\sum_{\mathbf{x}} \mu(\mathbf{x})-1) \\
  L(\mu,\alpha,\beta) &= -\sum_x \mu(\mathbf{x})f(\mathbf{x}) + \alpha( \sum_x \mu(\mathbf{x}) \log\frac{\mu(\mathbf{x})}{\rho(\mathbf{x})} -\epsilon) + \beta(\sum_{\mathbf{x}} \mu(\mathbf{x})-1) \\
  L(\mu,\alpha,\beta) &= -\sum_x \mu(\mathbf{x})f(\mathbf{x}) + \alpha( \sum_x \mu(\mathbf{x}) \log \mu(\mathbf{x}) - \sum_x \mu(\mathbf{x}) \log \rho(\mathbf{x}) -\epsilon) + \beta(\sum_{\mathbf{x}} \mu(\mathbf{x})-1) \\
  \end{align}
  $$
对上式微分并令微分结果等于0有:
$$
\begin{align}
\frac{\partial L(\mu,\alpha,\beta)}{\partial \mu(x)} &= -\sum_x f(\mathbf{x}) + \alpha \sum_x ( \log \mu(\mathbf{x}) + 1) - \alpha \sum_x \log \rho(\mathbf{x}) + \sum_x \beta \\
&= \sum_x (- f(\mathbf{x}) + \alpha \log \mu(\mathbf{x}) + 1 - \alpha \log \rho(\mathbf{x}) + \beta) \\
&= 0
\end{align}
$$
- 上式中求导使用到了 $\frac{\partial \log \mu(x)}{\partial \mu(x)} = \frac{1}{\mu(x)}$
进一步可以得到
$$
- f(\mathbf{x}) + \alpha \log \mu(\mathbf{x}) + 1 - \alpha \log \rho(\mathbf{x}) + \beta = 0
$$
即
$$
\begin{align}
\alpha \log \mu(\mathbf{x}) &= f(\mathbf{x}) + \alpha \log \rho(\mathbf{x}) - (\beta + 1) \\
\log \mu(\mathbf{x}) &= \frac{1}{\alpha}f(\mathbf{x}) + \log \rho(\mathbf{x}) + \frac{- (\beta + 1)}{\alpha} \\
\mu(\mathbf{x}) &= exp(\frac{1}{\alpha}f(\mathbf{x}) + \log \rho(\mathbf{x}) + \frac{- (\beta + 1)}{\alpha}) \\
\mu(\mathbf{x}) &= exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\log \rho(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha}) \\
\mu(\mathbf{x}) &= \rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha}) \\
\end{align}
$$
由于 $exp(\frac{- (\beta + 1)}{\alpha})$ 包含拉格朗日乘子，是未知的，所以我们进一步化简，尝试将这部分替换为已知式子，对上述结果最后一步两边同时积分有
$$
\begin{align}
\sum_x \mu(\mathbf{x}) &= \sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha})) \\
1 &= exp(\frac{- (\beta + 1)}{\alpha}) \sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x}))) \\
exp(\frac{- (\beta + 1)}{\alpha}) &= \frac{1}{\sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})))} \\
\end{align}
$$
将 $exp(\frac{- (\beta + 1)}{\alpha}) = \frac{1}{\sum_x (\rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})))}$ 的结果带入 $\mu(\mathbf{x}) = \rho(\mathbf{x})exp(\frac{1}{\alpha}f(\mathbf{x})) \cdot exp(\frac{- (\beta + 1)}{\alpha})$ 可以解的最终解：
$$\mu^{*}(\mathbf{x})=\frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))$$
- 其中 $Z = \sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))$
回到最初的问题：我们令 $\alpha=1$ 即可退回到原始问题

附录：最优策略形式的使用方式

从上面的证明，我们已经得到了最优策略的一般形式 $\mu^{*}(\mathbf{x})=\frac{\rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))}{\sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))} $，但这个形式难以直接使用
- 难以直接使用的原因（个人理解）：
  - 离线强化场景中 $\rho$ 未知，无法直接使用；
  - 在线强化学习场景中，难以用于状态维度高或动作空间大（包括连续状态或动作）的场景。状态和动作空间有限时， $\rho$ 是上一布步的策略或者历史混合策略 $f(\mathbf{x})$ 一般是 $A^\rho(s,a)$，理论上如果按照on-policy更新或者记录policy和样本以后按照off-policy更新均可，但是实际更新时，这种非参数化的策略，不同状态的策略是隔离的（没有状态泛化能力），针对每个状态都要更行才能做到该状态上的策略迭代 $\mu^{*}(\mathbf{a|s})=\frac{\rho(\mathbf{a|s}) \exp (\frac{1}{\alpha}f(\mathbf{a|s}))}{\sum_{\mathbf{a}} \rho(\mathbf{a|s}) \exp (\frac{1}{\alpha}f(\mathbf{a|s}))} $，相当于每次迭代需要收集大量的样本才能足够更新各个状态上的效果，否则在下一轮中遇到其他状态时，这里相当于没有被更新
一般来说，可以用神经网络去表示策略，实际上还可以进一步推导，不同的算法，目标函数不同，推导得到的结果也不同
对于CQL来说，由于目标是两步min max，需要进一步将最优解带入原始目标得到最终的目标
对于AWR，AWAC和IQL(复用了AWR方法)等论文，这里会直接使用一个神经网络去拟合策略，并尝试求这个策略的参数更新公式
$$
\begin{align}
\theta^* &= \mathop{\arg\min}_{\theta} D_{\mathrm{KL}}(\mu^*(\mathbf{x}) | \pi_\theta(\mathbf{x})) \\
&= \mathop{\arg\min}_{\theta} D_{\mathrm{KL}}\Big( \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) | \pi_\theta(\mathbf{x})\Big) \\
&= \mathop{\arg\min}_{\theta} \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \frac{ \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x}))} {\pi_\theta(\mathbf{x})} \\
&= \mathop{\arg\min}_{\theta} \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) - \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \\
&= \mathop{\arg\min}_{\theta} - \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \\
&= \mathop{\arg\max}_{\theta} \sum_{\mathbf{x}} \frac{1}{Z} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \\
&= \mathop{\arg\max}_{\theta} \sum_{\mathbf{x}} \rho(\mathbf{x}) \exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \quad \quad \text{Z与策略参数\theta无关，可以消掉} \\
&= \mathop{\arg\max}_{\theta} \mathbb{E}_{\mathbf{x} \sim \rho(\mathbf{x})} \Big[\exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x}) \Big] \\
\end{align}
$$
此时，最优解求解目标变成了从已知策略 $\rho(\mathbf{x} )$ 中采样，并最大化 $\exp (\frac{1}{\alpha}f(\mathbf{x})) \log \pi_\theta(\mathbf{x})$ 即可，此时的目标是可以直接对策略求梯度的，非常容易迭代

附录：证明 logsumexp 公式

参考：CQL算法logsumexp公式推导
当CQL($\mathcal{\rho}$)中的 $\rho$ 是均匀分布时，有最优解：
$$
\begin{align}
\mu^*(a\vert s) &= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\sum_a \rho(a\vert s)\cdot \exp(Q(s, a))} \\
&= \cfrac{\rho(a\vert s)\cdot \exp(Q(s, a))}{\rho(a\vert s) \sum_a \exp(Q(s, a))} \\
&= \cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))}
\end{align}
$$
带入CQL($\mathcal{R}$)形式有
$$
\begin{align}
\mathbb{E}_{a \sim \mu^*} [Q(s, a)] - D_{\mathrm{KL}}(\mu^* | \rho) &= \mathbb{E}_{a \sim \mu^*} \left[ \exp(Q(s, a)) - \log(\mu^*) + \log(\rho)\right]\\
&= \mathbb{E}_{a \sim \mu^*} \left[Q(s, a) - \log(\cfrac{\exp(Q(s, a))}{\sum_a \exp(Q(s, a))} ) +\log(\rho)\right]\\
&= \mathbb{E}_{a \sim \mu^*} \left[Q(s, a) - \log(\exp(Q(s, a))) + \log(\sum_a \exp(Q(s, a))) +\log(\rho)\right]\\
&= \mathbb{E}_{a \sim \mu^*} \left[\log(\sum_a \exp(Q(s, a))) + \log(\rho)\right]\\
\end{align}
$$
显然 $\log(\sum_a \exp(Q(s, a))) + \log(\rho)$ 此时与策略 $\mu^*$ 无关，期望可以消掉，同时 $\rho$ 是均匀分布时，有 $\rho(a|s) = \frac{1}{|A|}$， $\log(\rho) = -\log(|A|)$，于是有：
$$
\begin{align}
\mathbb{E}_{a \sim \mu^*} [Q(s, a)] - D_{\mathrm{KL}}(\mu^* | \rho) &= \log \sum_a \exp(Q(s, a)) -\log(|A|)
\end{align}
$$
- 注意，这里需要的是一个 $\max_Q f(Q)$ 的形式，而 $-\log(|A|)$ 这个值是个常数，与优化目标Q无关，可以消去
补充问题：为什么 CQL($\mathcal{\rho}$) 中可以直接消掉 $\mathcal{R}(\mu)$，但是 CQL($\mathcal{H}$) 中不行？
- 理论上，CQL($\mathcal{\rho}$)中不能直接消掉 $\mathcal{R}(\mu)$，CQL($\mathcal{H}$)中推导才是对的，论文中没有提这一点，实际上，把 $\mathcal{R}(\mu)$ 从目标挪到约束上 $\mathcal{R}(\mu) \le \epsilon$，最终推导的结果可以没有 $\mathcal{R}(\mu)$，指数权重上会有个温度系数（因为新增约束引入的拉格朗日乘子）

RL——IMPALA

注：本文包含 AI 辅助创作

参考链接
- 原始论文：IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
- 补充材料（附录）：IMPALA Supplemental Material
- 其他参考博客：【强化学习 44】IMPALA/V-trace - 张海抱的文章 - 知乎

Paper Summary

论文的目标是使用一个具有单一参数集的单一强化学习智能体来解决大量任务
- 一个关键挑战是处理增加的数据量和延长的训练时间
论文开发了一种新的分布式智能体 IMPALA（重要性加权 Actor-Learner 架构，Importance Weighted Actor-Learner Architecture），
- IMPALA 不仅能在单机训练中更有效地使用资源，而且可以扩展到数千台机器，同时不牺牲数据效率或资源利用率
论文通过将解耦的执行与学习相结合，并采用一种称为 V-trace 的新型 Off-policy 校正方法，实现了高吞吐量下的稳定学习
论文在 DMLab-30（来自 DeepMind Lab 环境 (2016) 的 30 个任务集）和 Atari-57（Arcade Learning Environment (2013b) 中所有可用的 Atari 游戏）上展示了 IMPALA 在多任务强化学习中的有效性
论文的结果表明，IMPALA 能够用更少的数据实现比先前智能体更好的性能，并且由于其多任务方法，关键地展示了任务间的正向迁移

Introduction and Discussion

深度强化学习方法通过试错学习掌握了多种领域 (2015; 2016; 2017; 2013a; 2014)
- 虽然在围棋 (2016) 和 Atari 游戏 (2015) 等任务上的改进是显著的，但进展主要是在单任务性能上，即每个任务分别训练一个智能体
论文感兴趣的是开发能够同时掌握多种多样任务的新方法，以及适合评估此类方法的环境
在多个任务上同时训练单个智能体的一个主要挑战是可扩展性
- 由于当前 SOTA 方法如 A3C (2016) 或 UNREAL (2017) 可能需要多达十亿帧数据和数天时间来掌握一个单一领域，同时在数十个领域上训练它们就太慢而不实用
论文提出了如图 1 所示的重要性加权 Actor-Learner 架构（Importance Weighted Actor-Learner Architecture, IMPALA）
IMPALA 能够扩展到数千台机器，同时不牺牲训练稳定性或数据效率
- 与流行的基于 A3C 的智能体（其工作进程向中央参数服务器通信关于策略参数的梯度）不同，IMPALA 的执行者（actor）将经验轨迹（状态、动作和奖励的序列）通信给一个集中化的 Learner
  - 由于 IMPALA 中的 Learner 可以访问完整的经验轨迹，论文使用 GPU 对轨迹的小批量进行更新，同时积极并行化所有时间无关的操作
- 这种解耦架构可以实现非常高的吞吐量
然而，因为在梯度计算时，用于生成轨迹的策略可能落后于 Learner 上的策略若干次更新，学习就变成了 Off-policy 的
- 因此，论文引入了 V-trace Off-policy Actor-Critic 算法来校正这种有害的差异
结合可扩展架构和 V-trace，IMPALA 实现了每秒 250,000 帧的极高数据吞吐率，使其比单机 A3C 快 30 多倍
关键的是，IMPALA 也比基于 A3C 的智能体更具数据效率，并且对超参数值和网络架构更具鲁棒性，使其能够更好地利用更深的神经网络
论文通过在 DMLab-30（一个新的挑战集，包含在 3D DeepMind Lab (2016) 环境中的 30 个多样化认知任务）上训练单个智能体来解决多任务问题，以及在 Atari-57 任务集中的所有游戏上训练单个智能体，来展示 IMPALA 的有效性

最早扩展深度强化学习的尝试依赖于具有多个工作进程的分布式异步随机梯度下降（SGD）(2012)
- 比如分布式 A3C (2016) 和 Gorila (2015)（深度 Q 网络 (2015) 的分布式版本）
最近用于强化学习的异步 SGD 的替代方案
- 包括使用进化过程 (2017)、分布式 BA3C (2018) 和 Ape-X (2018)（其具有分布式回放但同步 Learner ）
也有多项工作通过利用 GPU 来扩展强化学习
- 其中最简单的方法之一是批处理 A2C (2017)
  - 在每一步，批处理 A2C 产生一批动作并将其应用于一批环境
  - 每批中最慢的环境决定了执行整批步骤所需的时间（见图 1(a) 和 1(b)）
  - 换句话说，环境速度的高方差会严重限制性能
- 批处理 A2C 在 Atari 环境中特别有效，因为与强化学习智能体执行的昂贵张量操作相比，渲染和游戏逻辑在计算上非常便宜
  - 但视觉或物理上更复杂的环境可能模拟速度较慢，并且每一步所需的时间可能具有高方差
  - 环境也可能具有可变长度的（子）片段，导致初始化片段时速度减慢
与 IMPALA 最相似的架构是 GA3C (2016)，它也使用异步数据收集来更有效地利用 GPU
- GA3C 通过使用动态批处理将执行/前向传递与梯度计算/后向传递解耦
- GA3C 中的 Actor/Learner 异步性导致学习期间的不稳定性，(2016) 仅通过在策略梯度估计期间向动作概率添加一个小常数来部分缓解
- 相比之下，IMPALA 使用了更原则性的 V-trace 算法
先前关于 Off-policy 强化学习的相关工作包括 (2000, 2001); (2009); (2014); (2017) 和 (2016)
- 与论文工作最接近的是 Retrace 算法 (2016)，它引入了多步强化学习的 Off-policy 校正，并已在多种智能体架构中使用 (2017); (2018)
- Retrace 需要学习状态-动作值（state-action-value）函数 $Q$ 以进行 Off-policy 校正
- 然而，许多 Actor-Critic 方法（如 A3C）学习状态值（state-value）函数 $V$ 而不是状态-动作值函数 $Q$
- V-trace 基于状态值函数

IMPALA

IMPALA (图 1) 使用 Actor-Critic 设置来学习一个策略 $\pi$ 和一个基线函数 $V^{\pi}$
生成经验的过程与学习 $\pi$ 和 $V^{\pi}$ 的参数是解耦的
该架构由一组 Actor 和一个或多个 Learner 组成， Actor 反复生成经验轨迹， Learner 使用 Actor 发送的经验来 Off-policy 地 (off-policy) 学习 $\pi$
- 在每个轨迹开始时，一个 Actor 会将其自身的本地策略 $\mu$ 更新为最新的 Learner 策略 $\pi$ （$\mu \leftarrow \pi$），并在其环境中运行 $n$ 步
- 在 $n$ 步之后， Actor 将状态、动作和奖励的轨迹 $x_{1},a_{1},r_{1},\ldots,x_{n},a_{n},r_{n}$ 连同相应的策略分布 $\mu(a_{t}|x_{t})$ 和初始 LSTM 状态通过一个队列发送给 Learner
- Learner 持续地在来自许多 Actor 的轨迹批次上更新其策略 $\pi$
这种简单的架构使得 Learner 能够使用 GPU 进行加速，并且 Actor 可以轻松地分布在多台机器上
- 但在更新时， Learner 策略 $\pi$ 可能比 Actor 的策略 $\mu$ 领先若干次更新，因此在 Actor 和 Learner 之间存在策略滞后 (policy-lag)
V-trace 算法校正了这种滞后，从而在保持数据效率的同时实现了极高的数据吞吐量
- 使用 Actor-Learner 架构，提供了像分布式 A3C 那样的容错能力，但通常具有更低的通信开销，因为 Actor 发送的是观测值而不是参数/梯度
随着模型架构越来越深，单个 GPU 的速度常常成为训练期间的 limiting factor (限制因素)
如图 1 所示，IMPALA 可以与分布式的 Learner 集合一起使用，以高效地训练大型神经网络
参数分布在各个 Learner 之间， Actor 并行地从所有 Learner 检索参数，同时只将观测值发送给单个 Learner
IMPALA 使用同步参数更新，这在扩展到多台机器时对于保持数据效率至关重要 (2016)

Efficiency Optimisations

GPU 和 many-core CPU 通过运行少量大型、可并行化的操作而不是许多小操作而受益匪浅
由于 IMPALA 中的 Learner 在整个轨迹批次上执行更新，因此它能够比像 A3C 这样的在线智能体并行化更多的计算
- 例如，一个典型的深度 RL 智能体包含一个卷积网络，后接一个长短期记忆网络 (Long Short-Term Memory, LSTM) (1997) 和一个在 LSTM 之后的全连接输出层
- IMPALA Learner 通过将时间维度折叠到批次维度中，将卷积网络并行地应用于所有输入
类似地，一旦所有 LSTM 状态计算完毕，它也将输出层并行地应用于所有时间步
- 这种优化将有效批次大小增加到数千
- 基于 LSTM 的智能体还通过利用网络结构依赖性和操作融合 (2016) 在 Learner 上获得了显著的加速
最后，论文还利用了 TensorFlow (2017) 中提供的几种现成的优化，例如在执行计算的同时为 Learner 准备下一批数据、使用 XLA（一个 TensorFlow 即时编译器）编译部分计算图，以及优化数据格式以从 cuDNN 框架 (2014) 获得最大性能

V-trace

在解耦的分布式 Actor-Learner 架构中， Off-policy 学习非常重要，因为 Actor 生成动作与 Learner 估计梯度之间存在滞后
为此，论文为 Learner 引入了一种新颖的 Off-policy Actor-Critic 算法，称为 V-trace
论文考虑马尔可夫决策过程 (Markov Decision Processes, MDP) (1994; 1998) 中的 discounted infinite-horizon 强化学习问题，目标是找到一个策略 $\pi$，以最大化未来折扣奖励的期望和：
$$ V^{\pi}(x)\stackrel{ {\mathrm{def} } }{ {=} }\mathbb{E}_{\pi}\big{[} \sum_{t\geq 0}\gamma^{t}r_{t}\big{]} $$
- 其中 $\gamma\in[0,1)$ 是折扣因子，$r_{t}=r(x_{t},a_{t})$ 是时间 $t$ 的奖励，$x_{t}$ 是时间 $t$ 的状态（初始化为 $x_{0}=x$），$a_{t}\sim\pi(\cdot|x_{t})$ 是通过遵循某个策略 $\pi$ 生成的动作
Off-policy RL 算法的目标是使用由某个策略 $\mu$（称为行为策略 (behaviour policy)）生成的轨迹，来学习另一个策略 $\pi$（可能与 $\mu$ 不同，称为目标策略 (target policy)）的价值函数 $V^{\pi}$

V-trace 目标 (V-trace target)

考虑一个由 Actor 遵循某个策略 $\mu$ 生成的轨迹 $(x_{t},a_{t},r_{t})_{t=s}^{t=s+n}$
- 论文为 $V(x_{s})$（论文在状态 $x_{s}$ 的价值近似值）定义 $n$-step V-trace 目标为：
  $$v_{s}\stackrel{ {\mathrm{def} } }{ {=} } V(x_{s})+\sum_{t=s}^{s+n-1}\gamma^{t-s}\Big{(}\prod_{i=s}^{t-1 }c_{i}\Big{)}\delta_{t}V \tag{1}$$
  - 理解：这里是贝尔曼目标而不是 Advantage，类似 $r_t + V(s_t)$ 的角色
  - 其中 $\delta_{t}V$ 是 $V$ 的时序差分：
    $$ \delta_{t}V\stackrel{ {\mathrm{def} } }{ {=} }\rho_{t}\big{(}r_{t}+ \gamma V(x_{t+1})-V(x_{t})\big{)} $$
  - $\rho_{t}$ 和 $c_{i}$ 是截断的重要性采样 (Importance Sampling, IS) 权重（论文使用符号约定 $\prod_{i=s}^{t-1}c_{i}=1$ 当 $s=t$）
    $$
    \rho_{t}\stackrel{ {\mathrm{def} } }{ {=} }\min\big{(}\bar{\rho},\frac {\pi(a_{t}|x_{t})}{\mu(a_{t}|x_{t})}\big{)} \\
    c_{i}\stackrel{ {\mathrm{def} } }{ {=} }\min\big{(}\bar{c},\frac{\pi(a_{ t}|x_{t})}{\mu(a_{t}|x_{t})}\big{)}
    $$
  - 此外，论文假设截断水平满足 $\bar{\rho}\geq\bar{c}$
在 On-policy 的情况下（当 $\pi=\mu$），并假设 $\bar{c}\geq 1$，那么所有的 $c_{i}=1$ 且 $\rho_{t}=1$，因此 (1) 式重写为
$$
\begin{align}
v_{s} &=V(x_{s})+\sum_{t=s}^{s+n-1}\gamma^{t-s}\big{(}r_{t}+\gamma V(x_{t +1})-V(x_{t})\big{)}\\
&=\sum_{t=s}^{s+n-1}\gamma^{t-s}r_{t}+\gamma^{n}V(x_{s+n})
\end{align} \tag{2}
$$
- 这是 On-policy $n$-step Bellman 目标
- 因此，在 On-policy 情况下，V-trace 简化为 On-policy $n$-step Bellman 更新
  - 这个属性（是 Retrace (2016) 所不具备的）允许人们对离线和 On-policy 数据使用相同的算法
（截断的）IS 权重 $c_{i}$ 和 $\rho_{t}$ 扮演不同的角色
权重 $\rho_{t}$ 出现在时序差分 $\delta_{t}V$ 的定义中，并定义了此更新规则的固定点
- 在表格情况下，即函数可以被完美表示时，此更新的固定点（即，当对所有状态都有 $V(x_{s})=v_{s}$ 时），其特征是在期望下（在 $\mu$ 下）$\delta_{t}V$ 等于零，它是某个策略 $\pi_{\bar{\rho} }$ 的价值函数 $V^{\pi_{\bar{\rho} } }$，该策略由下式定义：
  $$\pi_{\bar{\rho} }(a|x)\stackrel{ {\mathrm{def} } }{ {=} }\frac{\min\big{(}\bar{\rho}\mu(a|x),\pi(a|x)\big{)} }{\sum_{b\in A}\min\big{(}\bar{\rho}\mu(b|x ),\pi(b|x)\big{)} } \tag{3}$$
- （参见附录 A 中的分析）
- 所以当 $\bar{\rho}$ 是无限的（即没有对 $\rho_{t}$ 进行截断）时，这就是目标策略 $\pi$ 的价值函数 $V^{\pi}$
- 然而，如果论文选择一个截断水平 $\bar{\rho}<\infty$，论文的固定点就是策略 $\pi_{\bar{\rho} }$ 的价值函数 $V^{\pi_{\bar{\rho} } }$，该策略介于 $\mu$ 和 $\pi$ 之间
- 在 $\bar{\rho}$ 接近零的极限情况下，论文得到行为策略 $\mu$ 的价值函数 $V^{\mu}$
- 在附录 A 中，论文证明了相关 V-trace 算子的收缩性以及相应在线 V-trace 算法的收敛性
权重 $c_{i}$ 类似于 Retrace 中的“迹切割”系数
- 它们的乘积 $c_{s}\dots c_{t-1}$ 衡量了在时间 $t$ 观察到的时序差分 $\delta_{t}V$ 对先前时间 $s$ 的价值函数更新的影响程度
- $\pi$ 和 $\mu$ 越不相似（论文越是 Off-policy ），该乘积的方差就越大
- 论文使用截断水平 $\bar{c}$ 作为一种方差缩减技术
- 但请注意，这种截断不会影响论文收敛到的解（该解仅由 $\bar{\rho}$ 表征）
因此，论文看到截断水平 $\bar{c}$ 和 $\bar{\rho}$ 代表了算法的不同特征：
- $\bar{\rho}$ 影响 IMPALA 收敛到的价值函数的性质
- $\bar{c}$ 影响 IMPALA 收敛到该函数的速度
Remark 1 ：V-trace 目标可以递归地计算：
$$v_{s}=V(x_{s})+\delta_{s}V+\gamma c_{s}\big{(}v_{s+1}-V(x_{s+1})\big{)}.$$
Remark 2 ：
- 与 Retrace$(\lambda)$ 类似，也可以在 V-trace 的定义中考虑一个额外的折扣参数 $\lambda\in[0,1]$，通过设置 $c_{i}=\lambda\min\big{(}\bar{c},\frac{\pi(a_{i}|x_{i})}{\mu(a_{i}|x_{i})}\big{)}$ 来实现
- 在 On-policy 情况下，当 $n=\infty$ 时，V-trace 则简化为 TD$(\lambda)$

Actor-Critic algorithm

策略梯度 (Policy gradient)

在 On-policy 情况下，价值函数 $V^{\mu}(x_{0})$ 关于策略 $\mu$ 的某个参数的梯度是
$$\nabla V^{\mu}(x_{0})=\mathbb{E}_{\mu}\Big{[}\sum_{s\geq 0}\gamma^{s}\nabla\log \mu(a_{s}|x_{s})Q^{\mu}(x_{s},a_{s})\Big{]},$$
- 其中 $Q^{\mu}(x_{s},a_{s})\stackrel{ {\textrm{def} } }{ {=} }\mathbb{E}_{\mu} \big{[}\sum_{t\geq s}\gamma^{t-s}r_{t}|x_{s},a_{s}\big{]}$ 是策略 $\mu$ 在 $(x_{s},a_{s})$ 的状态-动作价值
- 这通常通过随机梯度上升来实现，该上升沿 $\mathbb{E}_{a_{s}\sim\mu(\cdot|x_{s})}\Big{[}\nabla\log\mu(a_{s}|x_{s})q_{s}|x_ {s}\Big{]}$ 的方向更新策略参数，其中 $q_{s}$ 是 $Q^{\mu}(x_{s},a_{s})$ 的一个估计值，并在某个行为策略 $\mu$ 下访问到的一组状态 $x_{s}$ 上取平均
现在，在论文考虑的 Off-policy 设置中，我们可以使用被评估的策略 $\pi_{\bar{\rho} }$ 和行为策略 $\mu$ 之间的 IS 权重，沿以下方向更新论文的策略参数
$$\mathbb{E}_{a_{s}\sim\mu(\cdot|x_{s})}\Big{[}\frac{\pi_{\bar{\rho} }(a_{s}|x_{s })}{\mu(a_{s}|x_{s})}\nabla\log\pi_{\bar{\rho} }(a_{s}|x_{s})q_{s}\big{|}x_{s} \Big{]} \tag{4}$$
- 其中 $q_{s}\stackrel{ {\textrm{def} } }{ {=} }r_{s}+\gamma v_{s+1}$ 是从下一个状态 $x_{s+1}$ 的 V-trace 估计 $v_{s+1}$ 构建的 $Q^{\pi_{\bar{\rho} } }(x_{s},a_{s})$ 的估计值
- 论文使用 $q_{s}$ 而不是 $v_{s}$ 作为论文的 Q 值 $Q^{\pi_{\bar{\rho} } }(x_{s},a_{s})$ 的目标的原因是：
  - 假设论文的价值估计在所有状态下都是正确的，即 $V=V^{\pi_{\bar{\rho} } }$，那么论文有 $\mathbb{E}[q_{s}|x_{s},a_{s}]=Q^{\pi_{\bar{\rho} } }(x_{s},a_{s})$（而如果论文选择 $q_{t}=v_{t}$ 则不具备此性质）。有关分析请参见附录 A，关于估计 $q_{s}$ 的不同方法的比较请参见附录 E.3
为了降低策略梯度估计 (4) 的方差，论文通常从 $q_{s}$ 中减去一个依赖于状态的基线，例如当前的价值近似值 $V(x_{s})$
最后请注意，(4) 式估计的是 $\pi_{\bar{\rho} }$ 的策略梯度，这是在使用截断水平 $\bar{\rho}$ 时 V-trace 算法所评估的策略
- 然而，假设偏差 $V^{\pi_{\bar{\rho} } }-V^{\pi}$ 很小（例如，如果 $\bar{\rho}$ 足够大），那么我们可以期望 $q_{s}$ 为论文提供 $Q^{\pi}(x_{s},a_{s})$ 的良好估计
- 考虑到这些 Remarks，论文推导出以下规范的 V-trace Actor-Critic 算法

V-trace actor-critic algorithm

考虑价值函数 $V_{\theta}$ 和当前策略 $\pi_{\omega}$ 的参数化表示
轨迹是由 Actor 遵循某个行为策略 $\mu$ 生成的
V-trace 目标 $v_{s}$ 由 (1) 定义
在训练时间 $s$，价值参数 $\theta$ 通过梯度下降法在 $l2$ 损失上朝着目标 $v_{s}$ 更新，即，沿着下面的方向更新
$$\big{(}v_{s}-V_{\theta}(x_{s})\big{)}\nabla_{\theta}V_{\theta}(x_{s})$$
而策略参数 $\omega$ 则沿着策略梯度的方向更新：
$$\rho_{s}\nabla_{\omega}\log\pi_{\omega}(a_{s}|x_{s})\big{(}r_{s}+\gamma v_{s+1}- V_{\theta}(x_{s})\big{)}$$
为了防止过早收敛，我们可以像在 A3C 中那样，沿着以下方向添加一个熵奖励 (entropy bonus)
$$-\nabla_{\omega}\sum_{a}\pi_{\omega}(a|x_{s})\log\pi_{\omega}(a|x_{s})$$
总的更新是通过将这三个梯度按适当的系数重新缩放后相加得到的，这些系数是算法的超参数

Experiments

论文研究了 IMPALA 在多种设置下的性能
为了评估数据效率、计算性能和 Off-policy 校正的有效性，论文观察了在单个任务上训练的 IMPALA 智能体的学习行为
对于多任务学习，论文在一个新引入的包含 30 个 DeepMind Lab 任务的集合以及 Atari 学习环境 (2013a) 的所有 57 个游戏上训练智能体，每个智能体对所有任务使用同一组权重
在所有实验中，论文使用了两种不同的模型架构：
- 一个类似于 (2016) 的浅层模型，在策略和价值函数之前有一个 LSTM（如图 3（左）所示）；
- 一个更深的残差模型 (2016)（如图 3（右）所示）
对于有语言通道的任务，论文使用了一个以文本嵌入作为输入的 LSTM

计算性能 (Computational Performance)

高吞吐量、计算效率和可扩展性是 IMPALA 的主要设计目标
为了证明 IMPALA 在这些指标上优于当前算法，论文比较了 A3C (2016)、批处理 A2C 变体以及具有各种优化的 IMPALA 变体
- 对于使用 GPU 的单机实验，论文在前向传播中使用动态批处理来避免多次批大小为 1 的前向传播
- 论文的动态批处理模块由专门的 TensorFlow 操作实现，但在概念上类似于 GA3C 中使用的队列
表 1 详细列出了使用图 3 中浅层模型的单机和多机版本的结果
- 在单机情况下，IMPALA 在两个任务上都实现了最高性能，领先于所有批处理 A2C 变体以及 A3C
- 且分布式多机设置才是 IMPALA 真正展示其可扩展性的地方
- 通过第 3.1 节中的优化来加速基于 GPU 的学习器，IMPALA 智能体实现了 250,000 帧/秒或 210 亿帧/天的吞吐率
- 为了减少每个学习器所需的执行器数量，可以使用辅助损失、来自经验回放的数据或其他仅在学习器上进行的昂贵计算

单任务训练 (Single-Task Training)

为了研究 IMPALA 的学习动态，论文采用了单任务场景，在 5 个不同的 DeepMind Lab 任务上分别训练智能体
- 该任务集包括一个规划任务、两个迷宫导航任务、一个带有脚本机器人的激光标签任务和一个简单的水果收集任务
论文对熵正则化的权重、学习率和RMSProp epsilon进行了超参数扫描
- 对于每个实验，论文使用一组相同的 24 个从附录 D.1 范围内预采样的超参数组合
- 其他超参数固定为附录 D.3 中指定的值

收敛性与稳定性 (Convergence and Stability)

图 4 显示了 IMPALA、A3C 和使用图 3 中浅层模型的批处理 A2C 之间的比较
在所有 5 个任务中，要么是批处理 A2C 要么是 IMPALA 达到了最佳最终平均回报
- 并且在除 seekavoid_arena_01 之外的所有任务中，它们在整个训练过程中都领先于 A3C
- 理解：
  - A2C 是严格 On-policy 的，且参数是同步更新，所以是理论上的性能最优；
  - 对比来看，虽然 A3C 是 On-policy 的，但是存在参数的异步更新（有一定的滞后性），会导致一定的导致不稳定性
IMPALA 在 5 个任务中的 2 个上优于同步批处理 A2C，同时实现了更高的吞吐量（见表 1）
- 论文推测这种行为可能源于
  - 1）V-trace Off-policy 校正的作用类似于广义优势估计 (2016)
  - 2）异步数据收集产生了更多样化的经验批次
除了达到更好的最终性能外，IMPALA 对超参数选择的鲁棒性也比 A3C 更强
图 4 比较了上述方法在不同超参数组合下的最终性能，这些组合按平均最终回报从高到低排序
- IMPALA 在更多的组合上取得了更高的分数

V-trace 分析 (V-trace Analysis)

为了分析 V-trace，论文研究了四种不同的算法：
- 1. 无校正 (No-correction) ：无 Off-policy 校正
- 2. $\varepsilon$-校正 ($\varepsilon$-correction) ：在梯度计算期间添加一个小的常数值（$\varepsilon=1e-6$），以防止 $\log\pi(a)$ 变得非常小并导致数值不稳定，类似于 (2016)
- 3. 1-step 重要性采样 (1-step importance sampling) ：优化 $V(x)$ 时不进行 Off-policy 校正
  - 对于策略梯度，将每个时间步的优势（advantage）乘以相应的重要性采样权重
  - 此变体类似于没有“迹（traces）”的 V-trace，包含它是为了研究“迹”在 V-trace 中的重要性
- 4. V-trace ：如第 4 节所述
对于 V-trace 和 1-step 重要性采样，论文将每个重要性权重 $\rho_{t}$ 和 $c_{t}$ 裁剪为 $1$（即 $\bar{c}=\bar{\rho}=1$）
- 这降低了梯度估计的方差但引入了偏差
- 在 $\bar{\rho}\in[1,10,100]$ 中，论文发现 $\bar{\rho}=1$ 效果最好
论文在上一节的 5 个 DeepMind Lab 任务集上评估了所有算法
- 论文还在学习器上添加了一个经验回放缓冲区，以增加 $\pi$ 和 $\mu$ 之间的 Off-policy 差距
- 在经验回放实验中，论文从回放缓冲区中均匀随机抽取每批中 50% 的项目
表 2 分别显示了每种算法在有回放和无回放情况下的最终性能
在无回放设置中，V-trace 在 5 个任务中的 3 个上表现最佳，其次是 1-step 重要性采样、$\varepsilon$-校正和无校正
- 尽管 1-step 重要性采样在无回放设置中表现与 V-trace 相似，但在使用经验回放时，在 5 个任务中的 4 个上差距扩大了
  - 这表明，当目标策略和行为策略偏离更严重时，粗糙的 1-step 重要性采样近似变得不足
- 还要注意，V-trace 是唯一一个始终受益于添加经验回放的变体
- $\varepsilon$-校正在两个任务上比无校正有显著改进，但远远落后于基于重要性采样的方法，特别是在使用经验回放的更 Off-policy 的设置中
- 图 E.1 显示了更详细分析的结果
- 图 E.2 显示基于重要性采样的方法在所有超参数下也表现更好，并且通常更鲁棒

多任务训练 (Multi-Task Training)

IMPALA 的高数据吞吐量和数据效率使论文不仅可以在一个任务上训练，还可以在多个任务上并行训练，只需对训练设置进行最小更改
论文没有在所有执行器上运行相同的任务，而是将固定数量的执行器分配给多任务套件中的每个任务
注意，模型不知道它正在被训练或评估的是哪个任务

DMLab-30

为了测试 IMPALA 在多任务设置中的性能，论文使用 DMLab-30，这是一个基于 DeepMind Lab 构建的包含 30 个多样化任务的集合
该套件中的众多任务类型包括具有自然外观地形的视觉复杂环境、基于指令的接地语言任务 (2017)、导航任务、认知任务 (2018) 以及以脚本机器人作为对手的第一人称标签任务
DMLab-30 和任务的详细描述可在 github.com/deepmind/lab 和 deepmind.com/dm-lab-30 获取
论文比较了多种 IMPALA 变体与分布式 A3C 实现
- 除了使用基于群体的训练 (Population-Based Training, PBT) (2017a) 的智能体外，所有智能体都在附录 D.1 给出的相同范围内进行了超参数扫描
- 论文报告了平均上限人类标准化分数（mean capped human normalised score），其中每个任务的分数上限为 100%（见附录 B）
- 使用平均上限人类标准化分数强调了解决多个任务的需要，而不是专注于在单个任务上变得超人类
- 对于 PBT，论文使用平均上限人类标准化分数作为适应度函数，并调整熵成本、学习率和 RMSProp $\varepsilon$
- PBT 设置的具体细节见附录 F
具体来说，论文比较了以下智能体变体
- A3C,deep ，一个具有 210 个工作者（每个任务 7 个）的分布式实现，采用深度残差网络架构（图 3（右））
- IMPALA,shallow 具有 210 个执行器
- IMPALA,deep 具有 150 个执行器，两者都使用单个学习器
- IMPALA,deep,PBT ，与 IMPALA,deep 相同，但额外使用 PBT (2017a) 进行超参数优化
- IMPALA,deep,PBT,8 learners ，它利用 8 个学习器 GPU 来最大化学习速度
论文还在专家设置中训练了 IMPALA 智能体，IMPALA-Experts,deep ，其中每个任务训练一个单独的智能体
- 在这种情况下，论文没有为每个任务单独优化超参数，而是在训练 30 个专家智能体的所有任务上进行了优化
表 3 和图 5 显示所有 IMPALA 变体的性能都远优于深度分布式 A3C
- 此外，深度 IMPALA 变体不仅在最终性能上优于浅层网络版本，而且在整个训练过程中都表现更好
- 注意在表 3 中， IMPALA,deep,PBT,8 learners 虽然提供了更高的吞吐量，但在相同步数下达到了与 1 GPU 的 IMPALA,deep,PBT 相同的最终性能
特别地，在每个任务上单独训练的IMPALA-Experts 与同时在所有任务上训练的 IMPALA,deep,PBT 之间的差距
- 如图 5 所示，多任务版本在整个训练过程中都优于IMPALA-Experts ，附录 B 中的个体分数细分显示在语言任务和激光标签任务等任务上存在正向迁移（positive transfer）
将 A3C 与 IMPALA 在挂钟时间（wall clock time）上进行比较（图 6）进一步凸显了两种方法之间的可扩展性差距
- 使用 1 个学习器的 IMPALA 仅需约 10 小时即可达到 A3C 在 7.5 天后才接近的性能
- 使用 8 个学习器 GPU 而不是 1 个，将深度模型的训练速度进一步提高了 7 倍，达到 210K 帧/秒，高于原来的 30K 帧/秒

Atari

Atari 学习环境 (ALE) (2013a) 是大多数近期深度强化学习智能体的测试平台
- Atari 中的 57 个任务提出了具有挑战性的强化学习问题，包括探索、规划、反应性游戏和复杂的视觉输入
- 大多数游戏具有非常不同的视觉效果和游戏机制，这使得该领域对多任务学习尤其具有挑战性
论文在每个游戏上单独训练 IMPALA 和 A3C 智能体，并使用第 5 节介绍的深度网络（不含 LSTM）比较它们的性能
论文还提供了使用浅层网络的结果，该网络等效于 (2016) 中使用的前馈网络，包含三个卷积层
- 该网络通过在每个步骤堆叠最近的 4 个观察值来提供短期历史信息
- 有关预处理和超参数设置的详细信息，请参阅附录 G
除了使用固定超参数集训练 2 亿帧的个体每游戏专家外，论文还训练了一个 IMPALA Atari-57 智能体（一个智能体，一组权重），同时在所有 57 个 Atari 游戏上训练，每个游戏 2 亿帧，总计 114 亿帧
对于 Atari-57 智能体，论文使用群体大小为 24 的基于群体的训练，在整个训练过程中调整熵正则化、学习率、RMSProp $\varepsilon$ 和全局梯度范数裁剪阈值
论文比较了所有算法在 57 个 Atari 游戏上的中位数人类标准化分数
- 评估遵循标准协议，每个游戏分数是 200 个评估回合的平均值，每个回合开始时执行随机数量的无操作动作（从 [1, 30] 中均匀选择）以对抗 ALE 环境的确定性
如表 4 所示，IMPALA 专家在深度和浅层配置下都提供了比其 A3C 对应物更好的最终性能和数据效率
- 正如在论文的 DeepMind Lab 实验中一样，深度残差网络比浅层网络导致更高的分数，与使用的强化学习算法无关
- 浅层 IMPALA 实验在不到一小时内完成了超过 2 亿帧的训练
作者特别强调，IMPALA, deep, multi-task ，一个同时在所有 57 个 ALE 游戏上训练的单一智能体，达到了 59.7% 的中位数人类标准化分数
- 尽管 ALE 套件内的视觉外观和游戏机制具有高度多样性，IMPALA 多任务版本仍然设法与相关工作中常用作基线的 A3C, shallow, experts 保持竞争力
- ALE 通常被认为是一个困难的多任务环境，常常伴随着任务间的负迁移（negative transfer）(2016)
- 据论文所知，IMPALA 是第一个在 ALE 所有 57 个游戏的多任务设置下进行训练、并能与标准专家基线竞争的智能体

Conclusion

论文引入了一种新的高度可扩展的分布式智能体 IMPALA 以及一种新的 Off-policy 学习算法 V-trace
- 凭借其简单但可扩展的分布式架构，IMPALA 能够高效地利用小规模和大规模场景下的可用计算资源
- 这直接转化为研究新想法时非常快的周转时间，并开启了未被探索的机会
V-trace 是一种通用的 Off-policy 学习算法，与其他用于 Actor-Critic 智能体的 Off-policy 校正方法相比，它更加稳定和鲁棒
论文已经证明，在数据效率、稳定性和最终性能方面，IMPALA 实现了比 A3C 变体更好的性能
论文进一步在新的 DMLab-30 任务集和 Atari-57 任务集上评估了 IMPALA
据论文所知，IMPALA 是第一个在此类大规模多任务设置中成功测试的深度强化学习（Deep-RL）智能体，并且与基于 A3C 的智能体相比，它显示出卓越的性能（在 DMLab-30 上，标准化人类分数为 49.4% 对比 23.8%）
最重要的是，论文在 DMLab-30 上的实验表明，在多任务设置中，个体任务之间的正向迁移（positive transfer）使得 IMPALA 实现了比专家训练设置更好的性能
作者相信，IMPALA 为构建更好的深度强化学习智能体提供了一个简单、可扩展且鲁棒的框架，并具有激发新挑战研究的潜力

附录：【待补充】

补充材料（附录）：IMPALA Supplemental Material

RL——Eligibility-Traces-for-Off-Policy-Policy-Evaluation

参考链接：
- 原始论文：Eligibility Traces for Off-Policy Policy Evaluation, 2000, Sutton Richard

整体总结

一篇很古早的论文，主要探讨了如何在 Off-policy 场景下使用 资格迹（eligibility traces） 进行策略评估
包含了同一个轨迹来自不同行为策略的处理方式

研究背景与动机

在强化学习中，策略评估是指估计一个策略 $\pi$ 的值函数 $Q^\pi(s,a)$
传统方法如 TD(0) 和 TD($\lambda$) 通常是在 On-policy Setting 下工作，即数据由当前正在评估的策略生成
在许多实际场景中，我们希望从由 行为策略（behavior policy） $b$ 生成的数据中学习 目标策略（target policy） $\pi$ 的值函数，这就是 Off-policy learning
本文就聚焦于Off-policy 评估这一子问题，提出并分析了几种基于资格迹的算法，重点研究了它们与 重要性采样（importance sampling） 的关系

问题定义与符号说明

环境为 episodic MDP ，每幕从初始状态开始，直到终止状态
行为策略 $b$ 满足对所有状态-动作对，$b(s,a) > 0$
目标策略 $\pi$ 可以是任意的
目标：估计 $Q^\pi(s,a)$，即在状态 $s$ 下执行动作 $a$ 后，按照 $\pi$ 行动的期望折扣累积奖励

重要性采样方法

经典重要性采样（Importance Sampling, IS）

对于每个包含 $(s,a)$ 的幕 $m$，定义：
- $R_m$：从 $(s,a)$ 之后的折扣回报
- $w_m$：重要性权重，表示从该点之后，按照 $\pi$ 而非 $b$ 行动的概率比
  $$
  Q^{IS}(s,a) = \frac{1}{M} \sum_{m=1}^{M} R_m w_m
  $$
- 该估计是无偏且一致的，但方差大

加权重要性采样（Weighted Importance Sampling, WIS）

WIS 的定义
$$
Q^{WIS}(s,a) = \frac{\sum_{m=1}^{M} R_m w_m}{\sum_{m=1}^{M} w_m}
$$
- 该估计是有偏但一致的，方差更小，实践中更稳定

Per-Decision 重要性采样算法

核心思想

将回报分解为每一步的奖励，并对每个奖励单独加权：
$$
Q^{PD}(s,a) = \frac{1}{M} \sum_{m=1}^{M} \sum_{k=1}^{T_m - t_m} \gamma^{k-1} r_{t_m + k} \prod_{i=t_m+1}^{t_m+k-1} \frac{\pi_i}{b_i}
$$
Theorem 1 ：该估计是 $Q^\pi$ 的无偏一致估计
注：在此之前，人们通常对整条轨迹计算一个总的重要性权重
$$ W = \prod \frac{\pi(a_i|s_i)}{\mu(a_i|s_i)}$$
- 如果轨迹很长，方差会爆炸
本文没有明确提到，但事实上作者的证明不要求同一个轨迹来自同一个策略，即不需要整条轨迹都来自同一个策略（同一轨迹可以不同策略/不同行为策略）
- 只要在每一个时间步 $t$，都知道生成该动作 $a_t$ 的特定策略 $\mu_t$ 的概率，就可以通过累积乘积的方式来修正价值估计
- 即，作者从数学上证明了，即使 $t=1$ 的 $\mu_1$ 和 $t=2$ 的 $\mu_2$ 不同，只要记录了各自的概率，就可以通过加权来无偏地估计目标策略 $\pi$ 的 Value
- 核心：将回报分解为每个时间步的奖励，并对每个奖励单独加权，权重只依赖于到该奖励为止的轨迹，而不依赖于未来的行为策略

加权版本

Per-Decision 重要性采样算法的加权版本
$$
Q^{PDW}(s,a) = \frac{\sum_{m=1}^{M} \sum_{k=1}^{T_m - t_m} \gamma^{k-1} r_{t_m + k} \prod_{i=t_m+1}^{t_m+k-1} \frac{\pi_i}{b_i} }{\sum_{m=1}^{M} \sum_{k=1}^{T_m - t_m} \gamma^{k-1} \prod_{i=t_m+1}^{t_m+k-1} \frac{\pi_i}{b_i} }
$$
该估计是有偏一致估计

算法1：Per-Decision 重要性采样的资格迹版本

每个状态-动作对维护一个 eligibility trace $e_t(s,a)$
每一步更新：
$$
\begin{align}
e_t(s,a) &= e_{t-1}(s,a) \cdot \gamma \lambda \cdot \frac{\pi(s_t,a_t)}{b(s_t,a_t)} \\
\delta_t &= r_{t+1} + \gamma \frac{\pi(s_{t+1},a_{t+1})}{b(s_{t+1},a_{t+1})} Q_t(s_{t+1},a_{t+1}) - Q_t(s_t,a_t) \\
Q_{t+1}(s,a) &= Q_t(s,a) + \alpha e_t(s,a) \delta_t
\end{align}
$$
Theorem 2 ：在离线更新下，该算法收敛到 $Q^\pi$

Tree Backup 算法

核心思想

Tree Backup 不依赖于行为策略的显式概率，只需行为策略非饥饿（non-starving） ，即每个状态-动作对都会被无限次访问
在每一步，它考虑所有可能的动作，并根据目标策略的概率加权更新：
$$
Q_n^{TB}(s,a) = \frac{1}{M} \sum_{m=1}^{M} \left[ \gamma^n Q(s_{t_m+n}, a_{t_m+n}) \prod_{i=t_m+1}^{t_m+n} \pi_i + \sum_{k=t_m+1}^{t_m+n} \gamma^{k-t_m+1} \prod_{i=t_m+1}^{k-1} \pi_i \left( r_k + \gamma \sum_{a \neq a_k} \pi(s_k,a) Q(s_k,a) \right) \right]
$$
当 $n=1$ 时，退化为 TD(0)

算法2：Tree Backup 的资格迹版本

更新 eligibility trace：
$$
e_t(s,a) = e_{t-1}(s,a) \cdot \gamma \lambda \pi(s_t,a_t) \\
e_t(s,a) = 1 \quad \text{If } \quad (s,a) \text{ is current state-action pair}
$$
TD 误差：
$$
\delta_t = r_{t+1} + \gamma \sum_{a} \pi(s_{t+1},a) Q(s_{t+1},a) - Q(s_t,a_t)
$$
更新 Q：
$$
Q_{t+1}(s,a) = Q_t(s,a) + \alpha e_t(s,a) \delta_t
$$
Theorem 3 ：对于任意非饥饿行为策略，算法收敛到 $Q^\pi$

作者实验结果

作者在 100 个随机生成的 MDP 上比较了以下方法：
- 重要性采样（IS）
- 加权重要性采样（WIS）
- 每决策重要性采样（PD）
- 加权每决策重要性采样（PDW）
- 单步 TD（TD(0)）
- Tree Backup（TB）

作者的结果总结

IS 收敛慢，方差大
WIS 显著优于 IS，更稳定
PD 在行为策略均匀时表现良好，但在行为策略与目标策略差异大时表现较差
PDW 在差异大的情况下优于 PD，但整体不如 TB
Tree Backup（TB） 在所有设置中表现最好 ，尤其在中长期收敛速度和稳定性方面

建议：理论统一与扩展

论文还提出了 Tree Backup 和 Per-Decision 方法的统一视角：
- 在已知行为策略的地方，使用 Per-Decision 方法；
- 在未知或非平稳行为策略的地方，使用 Tree Backup；
- 两者可以结合，形成更鲁棒的 Off-policy 评估算法

RL——AC、A2C和A3C

策略梯度法的推导结论

策略梯度法推导结论是
$$
\begin{align}
\nabla_\theta J(\theta) &= \mathbb{E}_{\tau \sim p_\theta(\tau)} [R(\tau) \nabla_\theta \log p_\theta(\tau)] \\
& = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[\sum_t \nabla_\theta \log \pi_\theta(a_t|s_t) R(\tau) \right] \\
& = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[\sum_t \psi_t \nabla_\theta \log \pi_\theta(a_t|s_t) \right] \\
\end{align}
$$
- 推导详情见RL——策略梯度法推导
- $\psi_t$ 来替换 $R(\tau)$ 的理由是可以考虑用一个与时间相关的变量来替换与时间无关的累计收益
进一步地，其中的 $\psi_t$ 可以换成不同的形式，包括：
- $\sum_{t’=0}^T \gamma^t r_{t’}$：完成的轨迹收益
- $\sum_{t’=t}^T \gamma^{t’-t} r_{t’}$：从第 $t$ 步开始的轨迹收益，理由是策略主要影响的是 $t$ 步开始收益，对前面步骤的收益影响不大
- $\sum_{t’=t}^T \gamma^{t’-t} r_{t’} - b(s_t)$：进一步降低方差，详细证明见RL——策略梯度法
- $Q^{\pi_\theta}(s_t,a_t)$：动作价值函数，是 $\sum_{t’=t}^T \gamma^{t’-t} r_{t’}$ 的估计值
- $A^{\pi_\theta}(s_t,a_t)$：优势函数，仅考虑当前状态 $s_t$ 下不同动作带来的收益，忽略状态本身的价值
- $ r_t + \gamma V^{\pi_\theta}(s_{t+1}) - V^{\pi_\theta}(s_{t}) $： V 值的TD-Error形式，即贝尔曼残差，本质等价于优势函数
问题：将 $\psi_t$ 换成 $ r_t + \gamma Q^{\pi_\theta}(s_{t+1}, a_{t+1}) - Q^{\pi_\theta}(s_{t}, a_t) $ 可以吗？
- 答案是不可以。理由是 $ r_t + \gamma Q^{\pi_\theta}(s_{t+1}, a_{t+1}) - Q^{\pi_\theta}(s_{t}, a_t) $ 本身不是优势函数 $A(s,a)$，也不是 $Q(s,a)$ 没有别的含义，只有 Q 值自身更新时的TD-Error
- 证明：如果 $a_{t+1} \sim \pi_\theta$，则 $Q^{\pi_\theta}(s_{t+1}, a_{t+1}) = V^{\pi_\theta}(s_{t+1})$ ；但是因为 $Q^{\pi_\theta}(s_{t}, a_t) \neq V^{\pi_\theta}(s_{t})$ （因为 $a_t$ 是已经发生的事实），故而 $ r_t + \gamma Q^{\pi_\theta}(s_{t+1}, a_{t+1}) - Q^{\pi_\theta}(s_{t}, a_t) $ 本身不是优势函数，也能等价于优势函数
- 改进：如果非要用 Q 值来作为 Actor Critic 的价值网络，则需要求解策略 $\pi_{\theta^*} = \mathop{\arg\max}_{\pi_\theta} \mathbb{E}_{a_t \sim \pi_\theta(\cdot|s_t)} [Q(s_t, a_t)]$，比如DDPG就是如此

AC 算法

普通 AC（Actor Critic）算法一般是直接使用 $Q(s_t,a_t)$ 来替换 $\psi_t$

Critic 网络的更新

Critic 网络更新方式
$$
Loss_{\text{critic}} = \sum (r_t + \gamma Q^{\bar{w}}(s_{t+1}, a_{t+1}) - Q^{w}(s_{t}, a_t)) ^ 2
$$
- 这里要求 $a_{t+1} \sim \pi_\theta$（实际上是 SARSA 的更新方式）， $Q^{w}$ 值拟合的目标是策略 $\pi_\theta$ 对应的 Q 值 $Q^{\pi_\theta}(s_{t}, a_t)$
这里虽然使用 Target 网络的表达，但 AC 算法一般不需要 Target 网络，加入 Target 网络可能会导致收敛变慢
Critic 网络往往可以使用比 Actor 网络更大的学习率或更多的更新次数，这称为双时间尺度 AC 算法（Two-time Scale Actor-Critic Algorithms），该算法中，使用两种不同的学习速率（或时间尺度）来更新 Actor 和 Critic

Actor 网络的更新

Actor 网络的损失函数
$$
\begin{align}
Loss_{\text{actor}} &= - \sum Q^{w}(s_{t}, a_t) \log \pi_\theta(a_t|s_t) \\
Q^{w}(s_{t}, a_t) &= \text{Stop_Gradient}(Q^{w}(s_{t}, a_t))
\end{align}
$$
这里面的 $Q^{w}(s_{t}, a_t)$ 是不参与 Actor 参数的更新的
$a_t \sim \pi_\theta(\cdot|s_t)$

AC 算法的问题

AC 算法虽然是直接优化策略的，但是由于它是 on-policy 的，样本利用率很低，导致训练缓慢

A2C 算法

A2C（Advantage Actor Critic）算法引入了优势函数（Advantage），这也是 A2C 名字的由来
- 即使用 $ r_t + \gamma V^{\pi_\theta}(s_{t+1}) - V^{\pi_\theta}(s_{t}) $ 来替换 $\psi_t$ 的方法
很多书籍里面会直接默认使用 A2C 算法作为 AC 算法的等价表述

Critic 网络的更新

Critic 网络的损失函数：
$$
Loss_{\text{critic}} = \sum (r_t + \gamma V^{\bar{w}}(s_{t+1}) - V^{w}(s_{t})) ^ 2
$$
这里 V 值拟合的目标是策略 $\pi_\theta$ 对应的 V 值 $V^{\pi_\theta}$
这里虽然使用 Target 网络的表达，但A2C 算法一般不需要 Target 网络，加入 Target 网络可能会导致收敛变慢
Critic 网络往往可以使用比Actor 网络更大的学习率或更多的更新次数

Actor 网络的更新

Actor 网络损失函数：
$$
\begin{align}
Loss_{\text{actor}} &= - \sum \delta \log \pi_\theta(a_t|s_t) \\
\delta &= \text{Stop_Gradient}(r_t + \gamma V^{w}(s_{t+1}) - V^{w}(s_{t}))
\end{align}
$$
这里面的 $r_t + \gamma V^{w}(s_{t+1}) - V^{w}(s_{t})$ 是不参与 Actor 参数的更新的

A2C 算法的问题

A2C 算法是同步更新的，需要每个 Worker 都收集完成数据才能执行一次更新，很多时候数据交互完成的时间是很不一致的，训练也较慢

A3C 算法

A3C（Asynchronous Advantage Actor Critic），是 Actor Critic 方法的异步版本
注意：这里的异步是参数更新的异步，类似 PS 架构，不会导致 A3C 变成 Off-Policy 的
- 也就是说：A3C 始终是 On-Policy 的

A3C 的主要优化点

异步训练框架优化：

一个全局网络（包括V网络和Actor 网络）和多个相互独立的 Local 网络（即 Worker）
训练时：使用多个 Worker 并行的和环境分别交互，各自收集数据、计算梯度、异步更新全局网络参数
inference 时：仅适用全局网络中的 Actor 网络就可以

A3C 的“异步”更新流程

A3C 的“异步”特指 “多线程并行更新全局网络的方式” ，而非“采样策略与更新策略的分离”
- 其核心逻辑是通过“多个本地线程独立采样+异步向全局网络传梯度”提升训练效率
A3C 具体流程如下：
- 全局网络（Global Network） ：
  - 存储共享的策略参数$ \theta $（Actor和Critic共享一套参数），是最终需要优化的目标网络
- Local Workers ：通常有多个独立线程，每个线程的工作流程是：
  - 同步参数 ：先从全局网络复制当前最新的参数$ \theta $到本地（此时本地策略=全局策略）；
  - 采样轨迹 ：用本地策略$ \pi_\theta $与环境交互，采样一段短轨迹（如n-step，5~20步）；
  - 计算梯度 ：基于采样轨迹计算 Actor（策略）和 Critic（价值）的损失梯度（此时本地行为策略=本地待更新策略）；
    - 注意：这一步计算梯度时是在行为策略的基础上计算的，所以是 On-policy，不是 Off-policy
  - 异步更新 ：将本地梯度发送给全局网络，全局网络用这些梯度更新参数$ \theta $（无需等待其他线程，即“异步”）；
  - 重置本地参数 ：下一轮循环前，再次从全局网络同步最新的$ \theta $，覆盖本地旧参数
注：A3C 的“异步”仅描述“多个本地线程与全局网络的交互方式”，不改变“每个线程采样时用的策略=当前待更新的全局策略”这一核心事实

策略更新损失增加熵

增加熵的损失函数定义如下：
$$
\begin{align}
Loss_{\text{actor}} &= - \sum \delta \log \pi_\theta(a_t|s_t) + c H(\pi_\theta(a|s)) \\
\delta &= \text{Stop_Gradient}(r_t + \gamma V^{w}(s_{t+1}) - V^{w}(s_{t}))
\end{align}
$$
增加熵相当于是一种正则，与 SAC 思想相似

AC/A2C/A3C的区别

AC（Actor-Critic）、A2C（Advantage Actor-Critic）和 A3C（Asynchronous Advantage Actor-Critic）三者可以从名字上看出来算法的区别

AC（Actor-Critic）

Actor-Critic 方法结合了值函数方法和策略梯度方法的优点。它由两部分组成：一个称为“actor”的网络负责学习采取什么行动；另一个称为“critic”的网络评估采取的动作的好坏，即这个动作的价值

A2C（Advantage Actor-Critic）

关键词：Advantage
A2C 是 Actor-Critic 方法的一个变种，它引入了优势函数（advantage function）的概念来代替直接使用价值函数
优势函数 (A(s, a)) 定义为执行特定动作相对于遵循当前策略下的平均行为所能获得的优势或劣势。这种方法有助于更准确地估计哪些动作比其他动作更好，从而提高学习效率

更新方式 ：A2C 使用同步的方式更新参数，可以考虑使用多个网Actor分别于环境进行交互，然后共同的样本一起同步更新主网络 ，这意味着所有代理（agents）共享同一个模型，并且在每个训练步骤结束时同步更新模型权重

A3C（Asynchronous Advantage Actor-Critic）

关键词：Asynchronous
A3C 是 A2C 的异步版本，它允许多个代理同时在不同的环境中学习
更新方式 ：每个代理都有自己的环境副本和局部模型副本，它们独立地探索环境并收集经验。然后，这些经验被用来异步地更新全局模型，这样可以增加数据多样性并加快学习速度
优点：通过异步更新，A3C 可以有效利用多核处理器的能力，实现更快的学习速度和更好的性能

附录：为什么 A3C 不需要重要性采样？

标准 A3C 不需要重要性采样，因为其 “本地线程采样的策略” 与 “全局网络待更新的策略” 完全一致，无分布偏差
A3C 的“异步”是工程实现层面的并行更新方式 ，解决“单线程采样慢”的问题；
“On/Off-policy” 是算法理论层面的策略更新逻辑 ，解决“采样数据是否匹配目标策略”的问题
A3C 中“异步（Asynchronous）”与“Off-policy”的概念辨析
- A3C 的“异步”是“更新方式的异步”，而非“采样与更新策略的偏离（即Off-policy）”
- 正因为 A3C 本质上仍是On-policy（同策略） 算法，所以依然不需要重要性采样
对 A3C 而言，每个本地线程的采样过程完全满足 On-policy：
- 1）线程在采样前，会强制同步全局网络的最新参数$ \theta $到本地采样用的策略$ \pi_\theta $，就是当前全局网络正在优化的“目标策略”；
- 2）采样得到的轨迹，仅用于更新“产生该轨迹的策略$ \pi_\theta $”（即全局网络的$ \theta $）；
  - 旧轨迹不会被重复用于更新新策略
- 3）A3C 的异步可以保证每个 Local Worker 上计算得到的梯度是 On-policy 的，但是这个参数更新的异步会导致更新使用的参数是过期的（比如使用到上一个版本的 Actor 计算的梯度来更新这个版本）
  - 再次强调：这里不是 Off-policy，只是参数梯度更新存在一定的滞后性，这是 A3C 为了效率使用异步导致的，是可以容忍的

RL——COMBO

本文简单介绍COMBO模型

参考链接：
- 原始论文：COMBO: Conservative Offline Model-Based Policy Optimization, Stanford & UC Berkeley & Facebook AI Research, NeurIPS 2021

COMBO 基本思想

主要用于解决Offline RL的问题，属于Model-based方法
COMBO是结合了CQL思想的一种Model-based方法

原始 CQL 的更新公式

策略评估更新公式：
$$\hat{Q}^{k+1} = \mathop{\arg\min}_Q \alpha \left(\mathbb{E}_{\color{red}{s\sim \mathcal{D}, a\sim \mu(a\vert s)}}[Q(s, a)] - \mathbb{E}_{\color{blue} {s\sim \mathcal{D}, a\sim\hat{\pi}_\beta(a\vert s)}}[Q(s, a)] \right) + \frac{1}{2} \mathbb{E}_{\color{red} {\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{D}}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]$$
注，以上更新公式并不直接用于CQL的训练，是损失函数的中间结果

COMBO 的训练流程

COMBO 训练代码：
模型的训练：
- 模型输入是 $s,a$，预估目标是 $s’,r$，上面的训练代码中将输出建模成表达成高斯分布的形式（适用于连续型的场景），如果是离散型的场景，可以使用分类模型
策略评估更新公式：
$$\hat{Q}^{k+1} = \mathop{\arg\min}_Q \color{red}{\beta} \left(\mathbb{E}_{\color{red} {s,a\sim\rho(s,a)}}[Q(s, a)] - \mathbb{E}_{\color{blue} {s,a\sim\mathcal{D}}}[Q(s, a)] \right) + \frac{1}{2} \mathbb{E}_{\color{red} {\mathbf{s}, \mathbf{a}, \mathbf{s’} \sim \mathcal{d_f}}}\left[\left(Q(\mathbf{s}, \mathbf{a})-\hat{\mathcal{B}}^{\pi} \hat{Q}^{k}(\mathbf{s}, \mathbf{a})\right)^{2}\right]$$
以上红色部分是COMBO和CQL的核心区别，蓝色部分表达不同，但是本质是相同的，都是从离线的数据集中采样样本
- 第一部分：$\rho(s,a) = \color{red}{\mathcal{d}^\pi_{\hat{\mathcal{M}}}(s)}\pi(a|s)$，其中 $\color{red}{\mathcal{d}^\pi_{\hat{\mathcal{M}}}(s)}$ 表示策略 $\pi$ 与模型 $\hat{\mathcal{M}}$ 交互时的状态 $s$ 的访问概率
  - 注意这里只有状态的概率 $\color{red}{\mathcal{d}^\pi_{\hat{\mathcal{M}}}(s)}$ 选取与CQL的 $\color{red}{\mathcal{D}}$ 不同，后面的策略还是当前策略 $\pi(a|s)$，策略这个点与CQL是相同的
- 第二部分：$\mathcal{d}^\mu_f := f\ \mathcal{d}(s,a) + (1-f)\ \mathcal{d}^\mu_{\hat{\mathcal{M}}}(s,a)$，其中 $f\in [0,1]$ 表示数据混合比例
  - CQL中使用的全是真实数据集，在COMBO中则使用到了部分当前策略与模型交互生成的结果
  - COMBO论文中关于 $f$ 的选取一般在0.5或0.8不等，个人理解：在真实数据集较多的场景，这个混合比例不宜过低

实验结果

COMBO实验结果

RL——DDPG和TD3

参考链接：
- 强化学习之图解PPO算法和TD3算法

DPG

原始论文：Deterministic Policy Gradient Algorithms（论文中详细描述了 SGD，DPG 两种算法的 off-policy，on-policy 版本的分析）

Stochastic Actor-Critic Algorithms

Critic 网络损失函数
$$
Loss_{\text{critic}} = \sum_t (r_t + \gamma Q^{\bar{w}}(s_{t+1}, a_{t+1}) - Q^{w}(s_{t}, a_t)) ^ 2
$$
- 这里要求 $a_{t+1} \sim \pi_\theta$， $Q^w(s_t,a_t)$ 值拟合的目标是策略 $\pi_\theta$ 对应的Q值 $Q^{\pi_\theta}(s_{t}, a_t)$ ，代码中使用next_action = self.actor(next_states)代替动作即可
- 这里训练使用的 $(s_t,a_t,s_{t+1})$ 是当前策略采样到的数据（实际上，Q值的学习样本保证 $a_{t+1}$ 的采样策略即可，样本可以是任意策略采样的，当然，用当前策略采样的会更好些）
Actor 网络优化梯度：
$$
\nabla_\theta J(\pi_\theta) = \mathbb{E}_{s\sim \rho^{\pi},a\sim\pi_\theta}\left[ \nabla_\theta \log \pi_\theta(a|s)Q^w(s,a) \right]
$$
- 问题： $s\sim \rho^{\pi}$ 中的 $\pi$ 必须是 $\pi_\theta$ 吗？
  - 回答：是的，原始推导中，回合 $\tau$ 必须是来自当前策略的

Off-Policy Actor Critic

Critic 网络损失函数
$$
Loss_{\text{critic}} = \sum_t (r_t + \gamma Q^{\bar{w}}(s_{t+1}, a_{t+1}) - Q^{w}(s_{t}, a_t)) ^ 2
$$
- 这里要求 $a_{t+1} \sim \pi_\theta$， $Q^w(s_t,a_t)$ 值拟合的目标是策略 $\pi_\theta$ 对应的Q值 $Q^{\pi_\theta}(s_{t}, a_t)$ ，代码中使用next_action = self.actor(next_states)代替动作即可
- 这里训练使用的 $(s_t,a_t,s_{t+1})$ 是当前其他行为策略采样到的数据
Actor 网络优化梯度：
$$
\nabla_\theta J(\pi_\theta) = \mathbb{E}_{s\sim \rho^\beta,a\sim \beta}\left[ \frac{\pi_\theta(a|s)}{\beta_\theta(a|s)} \nabla_\theta \log \pi_\theta(a|s)Q^w(s,a) \right]
$$
- 问题：动作的偏移通过重要性采样 $\frac{\pi_\theta(a|s)}{\beta_\theta(a|s)} $ 来解决，但是状态也可以吗？
  - 回答：不可以，这里状态采用行为策略采样是因为off-policy场景下，策略梯度的目标就是在行为策略采样的状态上最大化目标函数（这样得到的不是最优策略，线上serving时的状态分布肯定与当前行为策略采样的状态不一致，所以是一个妥协的次优解）
- 思考：off-policy AC 与 DQN 的区别
  - 对于DQN，我们通过在每一个状态上让Q值拟合到最优策略对应的Q值（与状态分布无关，任意的状态我们都可以找到最优策略对应的Q值），然后通过 $\mathop{\arg\max}_a Q(s,a)$ 来找到最优策略
  - 对于off-policy AC，如果不考虑状态的分布，这里带来的偏差是从优化目标上出现的，即off-policy AC最大化的目标是，在行为策略采样的状态分布下，寻找一个策略，最大化累计策略收益期望。这里的目标显然与on-policy的原始目标不同了，状态分布线上线下不一致问题会导致天然的偏差
  - 问题：为什么不可以理解为与DQN一样？任意给定的状态我都做到策略最大化了，实际上就已经求到了最优策略了？（按照这个理解，除了off-policy都会遇到的训练评估数据分布不一致外，没有别的问题？）
    - 回答：不可以，因为DQN的目标是拟合 $Q^*(s,a)$，与状态分布无关；而策略梯度法的目标找到一个最优策略 $\pi^*$，最大化策略该策略下的累计收益，这里要求状态分布和动作分布均来自求解到的最优策略 $\pi^*$ ，off-policy AC下的状态分布是行为策略的，存在偏差
注：off-policy AC方法中，若使用n-step回报，则每一步都需要重要性采样，使用连乘方式将新旧策略的重要性采样比值乘上去即可
off-policy AC方法不常用，因为从目标上天然旧带着偏差

Off-Policy AC如何对混合策略采样的样本进行重要性采样？

在 Replay Buffer 中记录下每个样本的采样策略（代码示例），并在更新时逐个样本计算动作概率比值（代码示例），参见：

## 策略记录
memory.append(state, action, reward, policy.detach()) 

## 动作概率比值计算
if off_policy:
    rho = policies[i].detach() / old_policies[i]
else:
    rho = torch.ones(1, action_size)

上面的代码是 ACER（Actor-Critic with Experience Replay）方法的样例
- ACER 基于 Actor-Critic 框架
- ACER 利用经验回放技术来提高样本效率
- ACER 使用通过重要性采样权重来修正策略更新时的偏差，确保梯度估计的无偏性

On-Policy Deterministic Actor-Critic

优化目标
$$ J(\theta) = \int_\mathcal{S} \rho^{\mu_\theta}(s) Q^{\mu_\theta}(s, \mu_\theta(s)) ds $$
- 其中 $\rho^{\mu_\theta}(s’) = \int_\mathcal{S} \sum_{k=1}^\infty \gamma^{k-1} \rho_0(s) \rho^\mu(s \to s’, k) ds$
确定性梯度定理：
$$
\begin{aligned}
\nabla_\theta J(\theta)
&= \int_\mathcal{S} \rho^{\mu_\theta}(s) \nabla_a Q^{\mu_\theta}(s, a) \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)} ds \\
&= \mathbb{E}_{s \sim \rho^{\mu_\theta}} [\nabla_a Q^{\mu_\theta}(s, a) \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)}]
\end{aligned}
$$
确定性策略看作是随机策略的一种特殊形式，也就是策略的概率分布仅在某一个动作上有非零概率(该动作概率为1)
实际上，在 DPG 的论文中，作者指出：如果对随机策略，通过确定性策略和一个随机变量进行重参数化(re-parameterize)，那么随机策略最终会在方差 $\sigma=0$ 时与确定性策略等价
- 由于随机策略需要对整个状态和动作空间进行积分，我们可以预计随机策略的学习需要比确定性策略更多的样本（这里只是猜测，没有证据证明）

Off-Policy Deterministic Actor-Critic

优化目标
$$ J_\beta(\theta) = \int_\mathcal{S} \rho^\beta(s) Q^{\mu_\theta}(s, \mu_\theta(s)) ds $$
- 其中 $\rho^\beta(s)$ 是行为策略上采样得到的样本状态分布，这里直接导致了优化目标不是在最优策略下的回合（回合包含状态和动作）分布下的奖励期望最大，相对on-policy Deterministic AC算是次优解
推导结果：
$$
\begin{aligned}
\nabla_\theta J_\beta(\theta) &= \mathbb{E}_{s \sim \rho^\beta(s)} \left[\nabla_a Q^{\mu_\theta}(s, a) \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)} \right]
\end{aligned}
$$

Critic 网络更新（TD-Error）
$$
Loss_{\text{critic}} = \sum_t (r_t + \gamma Q^{\bar{w}}(s_{t+1}, a_{t+1}) - Q^{w}(s_{t}, a_t)) ^ 2
$$

这里要求 $a_{t+1} = \mu_\theta(s_{t+1})$， $Q^w(s_t,a_t)$ 值拟合的目标是策略 $\mu_\theta$ 对应的Q值 $Q^{\mu_\theta}(s_{t}, a_t)$，实际更新中常使用Target网络 $\bar{\theta}$ 一个简单的实现示例如下（参考自《动手学强化学习书籍》）：

1
2
3

next_q_values = self.target_critic(next_states, self.target_actor(next_states))
q_targets = rewards + self.gamma * next_q_values * (1 - dones)
critic_loss = torch.mean(F.mse_loss(self.critic(states, actions), q_targets))

这里训练使用的 $(s_t,a_t,s_{t+1})$ 是行为策略采样到的数据（Q值 $Q^{\mu_\theta}(s_{t}, a_t)$ 的学习样本保证 $a_{t+1}$ 的采样策略是 $\mu_\theta$ 即可，样本可以是任意策略采样的，当然，用当前策略采样的会更好些）

Actor 网络更新
$$
\begin{aligned}
Loss_{\text{actor}} = - \mathbb{E}_{s_t \sim \rho^\beta(s)} [Q_w(s_t,\mu_\theta(s_t))]
\end{aligned}
$$
- 上面的Loss求导就可以得到梯度是 $\mathbb{E}_{s \sim \rho^\beta(s)} \left[\nabla_a Q^{\mu_\theta}(s, a) \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)} \right]$，与之前推导结论一致
- 直观上理解，这里的目标是对于任意给定的状态 $s_t$ 下（这个状态样本是行为策略采样得到的），找到一个最大最大化当前 $Q_w(s_t,\mu_\theta(s_t)) $ 的动作参数 $\mu_\theta$

DDPG

Deep Deterministic Policy Gradient Algorithms，是 DPG 的 Deep 网络版本，原始论文地址CONTINUOUS CONTROL WITH DEEP REINFORCEMENT LEARNING

DDPG训练流程

伪代码如下（其中 $\theta^{\mu’}$ 和 $\theta^{Q’}$ 分别表示策略 $\mu’$ 和价值 $Q’$ 的参数）：
随机探索 ：做选择动作 $a_t$ 时，添加一个随机噪声，可以增强探索能力，使得模型更加鲁棒，如果没有随机噪声，可能会很快收敛到局部最优
软更新 ：Target网络的更新选择软更新，DQN中是硬更新

DDPG 为什么可以是 off-policy 的？

DDPG 是 off-policy 的，原因如下：
- Q函数的学习 ：DQN 和 DDPG 本质都是基于贝尔曼最优公式迭代Q值的，因为 Q 函数都是在学习某个策略 $\pi_0$ （$\pi_0$ 实际上就是截止到当前的最优策略）下对应的 Q 值，只要 TD-Error中的 Q 值目标 $r(s,a)+\gamma Q(s’,a’) - Q(s, a)$ 中的 $a’$ 是策略 $\pi_0$ 采样的，即服从策略 $a\sim\pi_0(\cdot|s’)$ 即可保证学到的Q值是 $Q^{\pi_0}(s,a)$，与 $(s,a,s’)$ 本身的采样策略无关
- 策略的学习 ：在保证Q函数预估的是当前策略（即截止到目前的最优策略）对应的Q值以后，我们只需要求解一个策略，保证当前策略对应的动作分布下的Q值最大即可，此时有：
  - DDPG如何找到最优策略？ ：目标是找到一个确定性策略 $\pi_\theta(s)$，最大化 $Q(s,\pi_\theta(s))$ （本质可以理解为Q值在策略下的期望 $\pi_\theta(s)$，确定性策略的期望就是这个策略对应的Q值），可采用梯度直接回传的方式链式求导；
  - 注意：DDPG/SAC等方法中 ，策略学习的目标是找到使得当前 $Q(s,a)|a\sim\pi_\theta(s)$ 值最大的策略 $\pi_\theta$，学习时状态 $s$ 是从什么策略采样来的无关，即任意给我一个状态 $s$，目标策略都能使得该状态下的 $Q$ 值最大化（这里的Q值在学习中拟合目标是在当前策略下的Q值）；但普通的AC方法中 ，Actor是直接对Reward的期望求梯度来更新的，这个期望是需要在当前策略下的期望，故而状态和动作都需要是当前状态下采样得到的，否则梯度有偏，而DDPG/SAC中则因为直接最大化Q值(该Q值是当前策略下的Q值)来实现了，绕过了必须保证状态 $s$ 是当前策略采样得到的这一步了
更多详情讨论可参考：RL——强化学习相关笔记

TD3

TD3 是对 DDPG 的改进，全称为 Twin Delayed Deep Deterministic Policy Gradient Algorithm，原始论文：Addressing Function Approximation Error in Actor-Critic Methods，ICML 2018，Google Research, Brain Team，代码地址：github.com/sfujim/TD3
有两个改进包含在名字中，Twin和Delayed
其他改进是在Actor 的target网络输出中，增加噪声

TD3 训练流程

伪代码如下（其中， $t \ \text{mod} \ d$ 表示策略更新比Q值更新慢一些， $d$ 次Q值更新对应一次策略更新）：

改进1：Twin

采用双Critic网络（训练网络和target网络均为双网络），缓解Q值高估问题

改进2：Delayed

Actor的目标是在Q值更新时，寻找最优的策略，如果Q值更新太快，容易波动，可以让Q值比较稳定了再更新Actor网络
具体做法，Critic网络更新 $d$ 次再更新一次Actor

改进3：Target 策略网络增加噪声

在Actor 的target策略网络输出的策略中，增加噪声，可以缓解Q值高估问题

TD3+BC（TD3 with behavior cloning，for Offline RL）

原始论文(与TD3同一个作者)：A Minimalist Approach to Offline Reinforcement Learning，NeurIPS 2021，Google Research, Brain Team，开源代码：github.com/sfujim/TD3_BC
TD3+BC，在 TD3 的基础上，增加策略模仿，即对策略进行迭代时，损失函数中增加 $loss_{\text{BC}} = (\pi_{\theta}(s) - a)^2$
论文中提到三个改进点：
- 加入带权重的 BC 正则项
- 状态归一化（不一定很重要）
- 提出对权重的一种设定方式
DDPG 是 Online RL 的算法，TD3+BC 是 Offline RL 的算法

RL——HER技术

Hindsight Experience Replay，简称HER，一种用于解决奖励稀疏问题的方法

参考链接：
- 原始论文：Hindsight Experience Replay，NIPS 2017，OpenAI
- 论文解读：Hindsight Experience Replay，Kenvnn’s Blog，论文的许多笔记参考自该博客

Background

在机器人领域，要想使强化学习训练它完美执行某任务，往往需要设计合理的奖励函数，但是设计这样的奖励函数工程师不仅需要懂得强化学习的领域知识，也需要懂得机器人、运动学等领域的知识。而且，有这些知识也未必能设计出很好的奖励函数供智能体进行学习
因此，如果可以从简单的奖励函数（如二分奖励）学习到可完成任务的模型，那就不需要费心设计复杂的奖励函数了

HER 技术思路

奖励函数的设计往往需要很强的先验知识，且往往比较难，特别在稀疏奖励和二分奖励场景中
- 系数奖励：完成目标的episode太少或者完成目标的步数太长，导致负奖励的样本数过多
- 二分奖励：完成目标时，奖励为A值，完不成目标时，奖励为B值
一句话说：通过在经验池中引入“Hindsight”（事后聪明）来解决稀疏奖励和二分奖励中的问题
- Hindsight的理解：hind表示“后面的”，sight则表示“看见；视力；视野等”，综合起来表示“事后聪明；事后的领悟”。与Foresight表示“先见之明”对比来看，翻译Hindsight为“后见之明”可能更为合适
可以用于所有Off-policy方法中

A motivating example

一个来自HER论文中的例子：bit-flipping environment
- 状态空间 $\mathcal{S}=\left \{ 0,1 \right \}^{n}$，维度为n
- 动作空间 $\mathcal{A}=\left \{ 0,1,\cdots,n-1 \right \}$，动作空间大小也为n
- 规则：对于每个episode，给定目标状态 $s_{g}$，从任意初始状态 $s_{0}$ （如 $n=5，s_{0}=10101$ ）每一步从动作空间中选取一个动作 $a$，翻转 $s_{0}$ 第 $a$ 个位置的值，如 $a=1\Rightarrow s_{1}=11101$，直到回合结束或者翻转后的状态与 $s_{g}$ 相同
- 奖励函数： $r_{g}(s,a)=-\left [ s \neq g \right ]$，即达到目标状态则为0，未达到目标状态则为-1。（ $s \neq g \Rightarrow true \doteq 1，s = g \Rightarrow false \doteq 0$ ）
- 注：后续将目标状态 $s_{g}$ 简化为 $g$
数组长度越长，反馈越稀疏，当 $n>40$ 时，几乎没有除了-1以外的奖励，标准的强化学习算法很难求解该问题。即使使用一些探索技术也不行，因为这个问题完全不是缺乏探索，而是状态太多，探索不完，导致奖励极其稀疏，算法根本不知道需要优化的目标在哪里

解决方法

reward shaping

将reward设计成某些变量的函数，如 $r_{g}(s,a)=-\left || s-g \right ||^{2}$，将训练的算法逐步引导至奖励函数增大的决策空间
- 该方案在这种场景中可以使用，但是不通用，无法应用到其他更加复杂的现实问题中

任务分解

将目标分解成多个粒度更小的，更容易解决的任务，使用类似层次强化学习（Hierarchical reinforcement learning）的方法去解决
这个文章中没有提到，一些书籍会提到

HER的做法

HER的主要思想就是：
- 通过修改目标简化问题，从而让奖励变得稠密。具体地，假定序列为 $s_{0},s_{1},s_{2}, \cdots ,s_{T}$，目标为 $g$，如果将目标状态 $g$ 修改为 $s_{T}$，即 $g=s_{T}$，那么这样看来智能体就可以获得奖励了
- 利用这个思想对经验池进行扩充即可，可以将稀疏奖励问题给转化成非稀疏奖励，使得奖励变得稠密
HER具体做法：
- 将经验池中的状态 $s$ 改为 $s||g$，也就是tf.concat(s,g)
- 训练算法的输入也是 $s||g$，也就是需要在当前状态后边连结上每个episode的目标状态，每个episode的目标状态可能不同
- HER对经验池进行了扩充，不仅存入实际采样得到的transition/experience， $\left ( s_{t}||g,a_{t},r_{t},s_{t+1}||g \right )$，也要在回合结束时重新设置目标状态，得到相应的奖励值（在二分奖励问题中，只有在 $s=g$ 时奖励才需要更改），存入“事后”（当初如果这样就好啦！）的经验 $\left ( s_{t}||g’,a_{t},r_{t}’,s_{t+1}||g’ \right )$，详见伪代码，这个事后经验究竟存入多少份、多少种，由超参数 $k$ 控制，下文讲解
- HER更适合解决多目标问题，多目标的意思为，目标点非固定，每个episode的目标状态可以不相同。详见实验部分
HER的几种扩展方式：
- 未来模式——future：在一个序列 $s_{0},s_{1},s_{2},\cdots,s_{T}$ 中，如果遍历到状态 $s_{2}$，则在 $s_{3},\cdots,s_{T}$ 之间随机抽取 $k$ 个状态作为目标状态 $g’$，并依此向经验池中存入 $\left ( s_{2}||g’,a_{2},r_{2}’,s_{3}||g’ \right )$，特点：一个episode的后续部分
- 回合模式——episode：在一个序列 $s_{0},s_{1},s_{2},…,s_{T}$ 中，如果遍历到状态 $s_{2}$，则在整个序列中随机抽取 $k$ 个状态作为目标状态 $g’$，并依此向经验池中存入 $\left ( s_{2}||g’,a_{2},r_{2}’,s_{3}||g’ \right )$，特点：一个episode
- 随机模式——random：在一个序列 $s_{0},s_{1},s_{2},…,s_{T}$ 中，如果遍历到状态 $s_{2}$，则在多个序列 $\tau_{0},\tau_{1},\tau_{2},\cdots$ 中随机抽取 $k$ 个状态作为目标状态 $g’$，并依此向经验池中存入 $\left ( s_{2}||g’,a_{2},r_{2}’,s_{3}||g’ \right )$，特点：多个episode
- 最终模式——final：在一个序列 $s_{0},s_{1},s_{2},\cdots,s_{T}$ 中，如果遍历到状态 $s_{2}$，则之间令 $g’=s_{T}$，并向经验池中存入 $\left ( s_{2}||g’,a_{2},r_{2}’,s_{3}||g’ \right )$，特点：一个episode的最后一个状态，如果设置k，则存入k个相同的经验
- 注：上面的 $s_{T}$ 不一定是当前episode的最终目标值，因为此时我们拟合的本意已经变成了“任意给定一个起始状态 $s_0$ 和目标状态 $s_i$，找到一个动作来实现将动作从 $s_0$ 变化到 $s_i$ ”
伪代码及其解析
- $r(s,a,g)$ 表示奖励不仅仅与当前状态和动作有关，还与最终的目标状态有关
- 伪代码中没有提到超参数 $k$，其实在循环条件 $\textbf{for} \ g’ \in G \ \textbf{do}$ 中循环执行了 $k$ 次
- $||$ 操作为连结操作，简言之，将两个长度为5的向量合并成一个长度为10的向量
- $G:=\mathbb{S}(\textbf{current episode})$ 即为上文提到的四种扩展模式：future、episode、random、final
- 奖励函数 $r(s,a,g)=-\left [ f_{g}(s)=0 \right ]$ 即为前文提到的 $r_{g}(s,a)=-\left [ s \neq g \right ]$，即完成为0，未完成为-1，具体奖励函数可以根据我们的使用环境设计
- $a_{t} \leftarrow \pi_{b}(s_{t}||g)$ 表示神经网络的输入为当前状态与目标状态的连结
HER的优点
- 可解决稀疏奖励、二分奖励问题
- 可适用于所有的Off-Policy算法
- 提升了数据采样效率

如何选择 HER 的模式？

实验结果：
- 效果：future>final>episode>random>no HER
- 稳定性：final(好)=no-HER(差)>future>episode>random

超参数的设置

$k$ 值不能太大，太大了会导致数据集中真实样本减少，出现问题

其他理解

问题：HER从 $s_{2}$ 扩展成 $s_{2}||g’$ 的过程中，相当于增加了MDP的数量（虽然MDP可能变得更短了），是否会导致MDP数量太多，模型难以收敛呢？

RL——MBPO

本文简单介绍 MBPO（Model-Based Policy Optimization）模型

参考链接：
- 原始论文：When to Trust Your Model: Model-Based Policy Optimization, UC Berkeley, NeurIPS 2019

MBPO 基本思想

主要用于解决 Online RL 的问题，属于 Model-based 方法

MBPO 方法详情

MBPO 训练代码
- 在收集到的奖励上减去一个误差项
- 训练时，Policy Optimization使用的是SAC方法：
其中，关键变量定义如下：

$\eta[\pi]$ denotes the returns of the policy in the true MDP, whereas $\hat{\eta}[\pi]$ denotes the returns of the policy under our model. Such a statement guarantees that, as long as we improve by at least C under the model, we can guarantee improvement on the true MDP.
- $\eta[\pi]$ 定义为真实MDP的累计折扣收益：
  $$ \eta[\pi] = \mathbb{E}_\pi\Big[ \sum_{t=0}^\infty \gamma^t r(s_t, a_t) \Big]$$
- $\hat{\eta}[\pi]$ 定义为模型返回的累计折扣收益
- $\eta[\pi]$ 和 $\hat{\eta}[\pi]$ 的关系：
  $$ \eta[\pi] \gt \hat{\eta}[\pi] - C $$
- 关于 $C(\epsilon_m, \epsilon_\pi)$ 的定义：
- $\epsilon_m$ : 模型误差
  $$ \epsilon_m = \max_t\mathbb{E}_{s\sim \pi_\text{D,t}} [D_{TV}(p(s’,r|s,a)\Vert p_\theta(s’,r|s,a))] $$
  - $s\sim \pi_\text{D,t}$ 表示时间步 $t$ 采样到状态 $s$
- $ \epsilon_\pi$ : 策略偏移
  $$ \max_s D_{TV}(\pi \Vert \pi_\text{D}) \lt \epsilon_\pi $$

附录：动手学强化学习中介绍的 MBPO

训练流程
- 没有考虑减去误差项

Joe Zhou

Stay Hungry. Stay Foolish.

GitHub E-Mail

AlphaGo整体说明

AlphaGo棋局介绍

ALphaGo问题建模

AlphaGo 训练过程（分三个阶段）

第一阶段：行为克隆（监督学习模仿人类专家）

第二阶段：强化学习（自我对弈优化，策略梯度优化）

第三阶段：价值网络学习（局面评估）

AlphaGo 决策过程

AlphaGo 相关思考

附录：AlphaGo 的迭代版本

BCQ 整体介绍

BCQ 连续版本

关键实验

理论推导

训练流程

Serving步骤

BCQ 离散版本

训练流程

Serving 步骤

CQL 在解决什么问题？

CQL 相关推导

一些定义

回顾贝尔曼算子

Offline RL 中的贝尔曼算子

如果在 Offline RL 中使用常规AC方法会发生什么？

改进一：打压未知动作的Q值

改进二：打压补偿

改进三：CQL(\(\mathcal{R}\))

改进四：CQL(\(\mathcal{\rho}\))

改进五：CQL(\(\mathcal{H}\))

CQL 伪代码

实践说明

一些说明和思考

附录：证明约束优化问题

附录：最优策略形式的使用方式

附录：证明 logsumexp 公式

Introduction and Discussion

Related Work

IMPALA

Efficiency Optimisations

V-trace

V-trace 目标 (V-trace target)

Actor-Critic algorithm

策略梯度 (Policy gradient)

V-trace actor-critic algorithm

Experiments

计算性能 (Computational Performance)

单任务训练 (Single-Task Training)

收敛性与稳定性 (Convergence and Stability)

V-trace 分析 (V-trace Analysis)

多任务训练 (Multi-Task Training)

DMLab-30

Atari

Conclusion

附录：【待补充】

整体总结

研究背景与动机

问题定义与符号说明

重要性采样方法

经典重要性采样（Importance Sampling, IS）

加权重要性采样（Weighted Importance Sampling, WIS）

Per-Decision 重要性采样算法

核心思想

加权版本

算法1：Per-Decision 重要性采样的资格迹版本

Tree Backup 算法

核心思想

算法2：Tree Backup 的资格迹版本

作者实验结果

作者的结果总结

建议：理论统一与扩展

策略梯度法的推导结论

AC 算法

Critic 网络的更新

Actor 网络的更新

AC 算法的问题

A2C 算法

Critic 网络的更新

Actor 网络的更新

A2C 算法的问题