2022 年 9 月论文笔记

这个月正式参与进入了实验室和快手的一个合作项目，依然还是需要从论文先开始。

CausalSim - Unbiased Trace-Driven Network Simulation

Abstract & Introduction

在测评网络协议在线上的实际性能的时候，虽然 RCT 方法是最为标准的，但是由于其极其昂贵，对周边基础设施的要求也很高，所以只有若干大型网络运营方才能支持这种测评方法。基于此，一般的研究所会选择网络模拟器或者 trace-based simulation。但是网络模拟器往往难以模拟出真实网络环境中的复杂情况，并且这类模拟器需要对网络环境的极其详细的掌握。而 trace-based simulation 又常常因为数据质量不高或者有偏导致测评不精确。

【RCT 方法之后看论文】

应用反事实模拟以利用离线历史数据的主要思路为，首先获取在某一个给定网络条件下使用某一个网络协议时的 trajectory，而我们需要训练一个模型来预测在这个网络条件下使用其他网络协议的时候的 trajectory。基于这个模型，我们只需要已知一个协议的性能，就能够得知新协议的性能表现而不需要实际部署该协议。

使用反事实模拟的好处包括：

• 节省部署协议和使用 RCT 方法评测的成本
• 能够在完全一致的网络条件下比较不同协议的差异
• 使用模型进行反事实模拟得到的数据可在社区内交流，帮助无法访问大型网络以测试其协议设计的开发者

当然，反事实模拟的方法是困难的，原因之一是用于采集观测数据的策略可能破坏无偏性，这一点我们后续阐述。

那么本文的核心成果就是：

We present CausalSim, a framework for learning unbiased trace-driven counterfactual simulation models for network protocols.

Motivation

总体而言，该文章尝试解决的问题依然是，考虑到直接线上测试算法性能较为耗时且代价较大，能否：

• 使用历史数据预测算法的性能
• 服务运营商能否使用历史数据构建一个模拟器使得开发者可以在不接触实际网络环境的条件下评测算法

The problem of trace-driven network simulation

这一部分假设了一个新算法 FabABR，然后在 Puffer 数据集上收集了类似 BOLA-BASIC、BBA、Fugu 等已知的算法在给定的网络条件下的 buffer occupancy，令 BOLA-BASIC v1 充当新算法 FabABR，之后构建了两个模型来通过其他已知算法的 buffer occupancy 预测 FabABR 的 buffer occupancy，并和 ground truth 比较。

当然，在实际环境中，我们是没有 ground truth 的，因为我们没有新算法通过 RCT 方法评测得到的 buffer occupancy 作为 ground truth。

第一个模型是 ExpertSim。其原理为，在某个网络条件下，如果某个算法在时刻 \(t\) 达成的吞吐率为 \(\hat c_t\)，那么我们假设在该网络条件下，新算法达成的吞吐率也是 \(\hat c_t\)。这也是该模型的首要假设，即不同算法对码率的决策不影响观测到的网络吞吐率，而这个假设广泛应用于各种模型。

在这个假设下，记时刻 \(t\) 时的 buffer size 为 \(b_t\)，而时刻 \(t + 1\) 时的 buffer size 为 \(b_{t + 1}\)，时刻 \(t\) 的视频块时间为 \(T\)，根据 FabABR 选择的码率该视频块的大小为 \(s_t\)，那么：

\[ b_{t + 1} = \max\left(0, b_t - \frac{s_t}{\hat c_t}\right) + T \]

第二个模型为 SLSim。其模型为两层全链接层，每层 128 个 ReLU 激活的神经元。该网络的输入为 \(b_t, \hat c_t, s_t\)，输出为 \(b_{t + 1}\)，符号的意义同上。由于我们具有 ground truth，我们就将其作为 supervisor 进行训练，loss 设定为 L2 loss。最后的实验结果为：

这里可以看见两种模型都不及 CausalSim 做出的预测。而这一差距的本质就是这两个模型都默认了不同算法对码率的决策不影响观测到的网络吞吐率，但实际上由于类似于 TCP 慢启动、和其他流量竞争等因素，不同的码率选择实际上会影响实际的吞吐率。而 Puffer 数据集实际上就能证明该假设错误：

可见不同算法影响了吞吐率的分布。这种错误的假设导致了数据的有偏。

Causal inference to the rescue

如果我们能够获取更深层次的网络情况而非仅仅是表层的吞吐率，我们完全就能修正原先的错误假设，这是因为我们可以将这些底层的网络情况视作独立于 ABR 算法的因素。

但是这些底层网络情况并不出现在数据集中，我们需要通过表层数据推测这些底层情况，而这也就是反事实推理介入的地方。

具体的设计见下述部分。

Model

Causal dynamics

我们给出这样的建模，令 \(o_t^\star\) 表示时刻 \(t\) 的时候系统观测到的表层数据，\(u_t\) 表示时刻 \(t\) 的时候系统的底层数据，\(a_t\) 表示时刻 \(t\) 时我们对系统做出的决策，那么系统行为可以建模为：

\[ o_{t + 1}^\star = \mathcal{F}_{\rm evolution}(o_t^\star, u_t, a_t) \]

在 ABR 问题中，\(o_t^\star\) 包括的因素有 buffer size、实际吞吐率、Min RTT、可选视频块大小，而 \(u_t\) 包括的因素有瓶颈连接时间、竞争流量的数量、竞争流量的 congestion control。

此外，我们可以将 \(o_t^\star\) 拆分为 \(o_t\) 和 \(m_t\)，这里 \(m_t\) 是观测数据中受到底层数据所影响的部分，从而我们可以拆分出纯外部数据 \(o_t\)，而后续我们所称呼的“观测数据”即指代 \(o_t\)。这一步拆分后，建模可以变为：

\[ \begin{aligned} m_t &= \mathcal{F}_{\rm mediation}(a_t, u_t) \\ o_{t + 1} &= \mathcal{F}_{\rm system}(o_t, m_t, a_t) \\ o_t^\star &= [o_t, m_t] \end{aligned} \]

这里，我们需要说明的是 \(m_t\) 是可观测的，而 \(u_t\) 是潜在而不可观测的。另外，\(m_t\) 受到决策的影响，而 \(u_t\) 不受到决策的影响。

在 ABR 问题中，\(m_t\) 就是我们实现的吞吐率，其不仅受到潜在网络环境影响，还受到 ABR 码率决策的影响，而这也就是先前两个策略失败的核心原因。此外，根据该建模，在得知吞吐率 \(m_t\) 的信息之后，我们完全不需要了解其他信息即可推断出其他可观测的信息 \(o_t\)。

Trace-driven simulation is counterfactual estimation

首先统一符号，我们假设数据集一共采用了 \(K\) 种不同算法，一共生成了 \(N\) 条 trajectory，我们记第 \(i\) 个 trajectory 的长度为 \(H_i\)。

那么我们的训练策略可以描述为，首先对于任何 \(i\)，我们给出决策序列 \(\{\tilde a_t^i\}_{t = 1}^{H_i}\)，给定初始观测 \(o_1^i\)，并且我们确定所有 trajectory 均基于同一个潜在状态序列 \(\{u_t^i\}_{t = 1}^{H_i}\)，我们的目的是预测出观测序列 \(\{\tilde o_t^i\}_{t = 1}^{H_i}\)。

此外，我们注意到学习 \(\mathcal{F}_{\rm system}\) 是完全监督的，因为所有需要的数据均可以观测。所以最终的困难点在于估计 \(\{u_t^i\}_{t = 1}^{H_i}, \{m_t^i\}_{t = 1}^{H_i}\) 以及学习 \(\mathcal{F}_{\rm mediation}\)。

CausalSim - Key insights

Counterfactual estimation as matrix completion

这一步的核心在于将反事实推理等效为矩阵填充问题。我们假设动作空间大小为 \(A\)，即 \(a_t^i \in \{1, 2, \cdots, A\}\)，另外记：

\[ U := \sum_{i = 1}^NH_i \]

那么我们考虑一个 \(A \times U\) 的矩阵，其中每一行代表一种决策，每一列代表潜在状态。这里我们将第 \(i\) 个 trajectory 的第 \(t\) 时刻中所有的 \((i, t)\) 按 \(i\) 为主序数排列为长度为 \(U\) 的序列，从而每一个 \((i, t)\) 都能对应到 \(M\) 中的某一列。

在第 \(i\) 个 trajectory 的第 \(t\) 时刻，我们观测到 \(m_t^i = \mathcal{F}_{\rm mediation}(a_t^i, u_t^i)\)，而 \(m_t^i\) 就是矩阵 \(M\) 中 \(a_t^i\) 所对应的行和 \((i, t)\) 所对应的列处的已知元素，该列其余元素均为未知元素。也就是说我们在初始条件下，每一列都会有一个已知元素。

而现有的矩阵填充算法并不能直接应用到本问题上，因为本问题中的 \(M\) 元素缺失的 pattern 并不随机并且缺失元素数量过多。但是另外一方面，矩阵 \(M\) 显然具有更为优越的结构，因为元素缺失的 pattern 和已知的 ABR 算法决策流程相关，并且 \(N\) 个 trajectory 的网络潜在条件是一致的。

Exploiting the policy invarience of latent factors

我们这里考虑一个简单情况，即 \(A = 2, U = 2n\)，并且矩阵 \(M\) 秩为 \(1\)。这说明存在 \(a \in \mathbb{R}^2, u \in \mathbb{R}^{2n}\) 满足 \(M = au^T\)。之后我们令 \(K = 2\)。

考虑到：

\[ \frac{M_{1, j}}{M_{2, j}} = \frac{a_1u_j}{a_2u_j} = \frac{a_1}{a_2} \]

并且每一列必然有一个已知元素，所以我们只需要估计 \(a_1 / a_2\)。

另外，基于两个 trajectory 均基于一致的网络潜在条件，所以对于较大的 \(n\)，每一列的期望应当类似，所以有以下估计（这个估计我感觉比较奇怪，说理也比较不充分）：

\[ \frac{1}{n}\sum_{j = 1}^n u_j \approx \frac{1}{n}\sum_{j = n + 1}^{2n} u_j \]

之后我们就可以得到下述估计：

\[ \frac{\sum_{j = 1}^n M_{1, j}}{\sum_{j = n + 1}^{2n} M_{2, j}} = \frac{\sum_{j = 1}^n a_1u_j}{\sum_{j = n + 1}^{2n} a_2u_j} \approx \frac{a_1}{a_2} \]

从而我们得到了我们需要的估计，从而我们就能补充完整整个矩阵。

CausalSim - Details

最后采用了这样的一个网络结构：

该网络的目标是为了获取不变的潜在条件 \(\{u_t^i\}_{t = 1}^{H_i}\)，而完成这项任务的网络是 Policy Discriminator，其接受 \(\{u_t^i\}_{t = 1}^{H_i}\) 作为输入，输出为其认为该行为决策是由哪一个算法做出的。由于其为一个简单的多分类任务，所以其 loss 就采用简单的交叉熵表示为：

\[ \mathcal{L}_{\rm disc} := \mathbb{E}_D[-\ln \mathbb{P}(\pi \mid \hat u)] \]

而我们的目标是让 Policy Discriminator 的 loss 尽可能大，从而通过分类器无法区分各类算法保证抽取的潜在不变条件确实和具体的算法无关。

整个网络采用的 loss 为：

\[ \mathcal{L}_{\rm total} := \mathbb{E}_D[\delta(m_t^i - \hat m_t^i)^2 + (o_t^i - \hat o_t^i)^2] - \kappa\mathcal{L}_{\rm disc} \]

Evaluation

A real-world ABR experiment

实验过程比较简单，问题出现在如何评测。因为 Puffer 数据集里每一个 trajectory 仅使用了一种算法跑过，所以实际上是无法对多个新算法进行评测的。所以其采用了评价变量分布的方式进行评测。即，不同的算法在不同的 trajectory 上运行，只要潜在网络因素不变，各类变量的分布应该是类似的。那么基于此，我们只要再做一次模拟，之后指定一个变量，评价两次模拟中该变量分布之间的差距。这里评价分布的差距使用 EMD：

\[ {\rm EMD}(\mathcal{P}, \mathcal{Q}) := \int_{-\infty}^{+\infty} |\mathcal{P}(x) - \mathcal{Q}(x)| {\rm d}x \]

这里 \(\mathcal{P}, \mathcal{Q}\) 都是累积分布函数。

评测结果自然是 CausalSim 很厉害：

Learning ABR policies with CausalSim

既然现在已经具有了工作良好的模拟器，我们就可以利用该模拟器训练 ABR，具体的过程不阐述，结果如下：

总体而言，CausalSim 显然和真实环境下训练的结果贴近，而其他的模拟器均有很大偏差。并且对于高 RTT 的 Agent，这个差距更大。这个差距的根本原因依然是其他模拟器都是有偏的，在例如慢启动等条件下，容易选择保守的码率。

Server load balancing

【PASS】

Final analysis

读这一篇论文目的是为了研究怎么离线评测算法，也就是训练一个合理的环境模拟器出来。但感觉本文的一个核心思想为将网络吞吐率等因素视作和 ABR 决策有关的变量，将其纳入考虑。严格而言就是更新了对环境内部逻辑的建模，使之更为贴近真实环境。而如果不把网络吞吐率纳入考虑，则前一时刻无论做出什么选择，下一时刻环境都会要求算法实现同样的吞吐率，从而导致算法趋近于保守，在高 RTT Agent 上表现出仅选择较低码率。

方法上的话，感觉 Policy Discriminator 没有太见过，是一个训练无关性的好方法。

Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimization

Abstract & Introduction

离线 RL 的问题在于在线和环境交互可能导致较大开销，为了解决这一问题，主要的策略分为：

• 限制 agent 的行为，防止其做出错误举动。这里 BCQ 就采用了这样的做法（但是 BCQ 论文实在是需要慢慢看）
• 强化 agent 的 exploitation 能力，令其最大化利用有限的数据

本文的成果是提出了衡量 RL 算法的一个指标，即 deployment efficiency，其基于了 RL 学习过程中数据采集策略发生变化的次数（因为策略发生变化意味着需要一次新的部署）。完全离线的 RL 算法如 BCQ、BRAC 具有很高的 deployment efficiency，而完全在线的 RL 算法如 DDPG、SAC 则较低。

论文特别指出，deployment efficiency 和已有的 data efficiency 并不完全类似，这里后者衡量了 RL 学习过程中采集数据的次数。这意味着，即使 data efficiency 很低（数据采样次数极大），只要收集数据的策略没变，那么 deployment efficiency 依然较高。

目前大部分的离线 RL 算法都在大数据集上进行训练和评测，以保证 deployment efficiency 和 data efficiency 都很高。但实际上我们注意到由于 extrapolation error，这种简单直接的算法其实并不优越。而对于在线算法，虽然可以克服数据集数据分布不符合真实数据分布的问题，但实际上会限制 policy 的表达能力【Question #1：这里没有特别明白】。

此外，本文还提出了 BREMEN，即 Behavior Regularized Model ENsemble。

We propose Behavior-Regularized Model-ENsemble (BREMEN), which learns an ensemble of dynamics models in conjunction with a policy using imaginary rollouts while implicitly regularizing the learned policy via appropriate parameter initialization and conservative trust-region learning updates.

自然，BREMEN 在高维连续决策空间上也表现很好。

Preliminaries

首先定义 MDP \((\mathcal{S}, \mathcal{A}, p, r, \gamma)\)，而 policy \(\pi\) 定义了 agent 的行为，\(\pi\) 接受一个状态，输出一个状态空间 \(\mathcal{A}\) 上的概率分布，表示 agent 做出给定行为的概率。我们的目标是获取下述最优 policy：

\[ \pi^* = \mathop{\rm argmax}_\pi \eta[\pi] = \mathop{\rm argmax}_\pi \mathbb{E}_\pi\left[\sum_{t = 0}^{+\infty} \gamma^tr(s_t)\right] \]

而所谓 model-based 的 RL 方法，就需要对 MDP 中的 \(p(s' \mid s, a)\) 建模估计。

RL 的学习过程中包含两种行为，分别为获取 MDP 转移对（即 deployment）与更新 policy 参数（即 learning）。如果学习过程中每次更新参数后均将收集到的数据舍弃，那么该学习就是 on-policy 的。反之，如果不断积累数据形成 replay dataset \(\mathcal{D}\)，那么该学习就是 off-policy 的，因为用于更新 policy 的数据并不一定通过当前 policy 收集。

但是上述的学习过程都是 online 的，因为其 deployment 和 learning 是混合进行的，而纯 offline 算法中 agent 不会直接与环境进行任何的交互，agent 只能从固定的数据集之中学习。当然，介于 online 和 offline 之间有 semi-batch RL，其实现了较高的 deployment efficiency，当然这种方法并没有完全研究过。

Deployment efficiency

这里主要阐述这样的观点，即对于 online RL，无论其是 on-policy 还是 off-policy，在一次迭代之后，必然会部署新的 policy 并获取数据，这显然是 deployment unefficient 的。相反，纯 offline RL 只会学习一次部署得到的数据。而一个理想的平衡算法应当位于这两个极端之间。

论文认为现在的 RL 算法忽视了 deployment efficiency，并且现行的部分 SOTA 算法甚至需要百万量级的部署次数（如 SAC）。本文提出了只需要五次到十次部署即可有效学习的算法。

Behavior regularized model ensemble

Imaginary rollout from model ensemble

为了解决 model bias 的问题，BREMEN 使用了包含 \(K\) 个 deterministic dynamic model 的 \(\hat f_\phi := \left\{\hat f_{\phi_1}, \cdots, \hat f_{\phi_K}\right\}\)，其中 \(\phi_i\) 表示模型参数。这些模型的训练方式都是最小化下述均方误差，即 model 预测的后续状态和数据集 \(\mathcal{D}\) 指示的后续状态：

\[ \min_{\phi_i} \frac{1}{|\mathcal{D}|} \sum_{(s_t, a_t; s_{t + 1}) \in \mathcal{D}} \frac{1}{2} \left\|s_{t + 1} - \hat f_{\phi_i}(s_t, a_t)\right\|_2^2 \]

在实际训练 policy \(\pi_\theta\) 的时候，会从这 \(K\) 个 model 中随机选择一个来提供下一状态：

\[ a_t \sim \pi_\theta(\cdot \mid \hat s_t), \hat s_{t + 1} = \hat f_{\phi_t}(\hat s_t, a_t), i \sim \{1, 2, \cdots, K\} \]

Policy update with behavior regularization

这里训练具体的 policy 的时候，需要使用置信区间约束来解决 distribution shift 的问题，即在每一次部署之后都使用 behavior clone 得到的 policy \(\hat\pi_\beta\) 对 \(\pi_\theta\) 重新初始化。具体而言，在每一次部署之后我们都能得到一个更新过的数据集 \(\mathcal{D}\)，从而我们使用 BC 对真实的 policy \(\pi_b\) 进行估计。具体的训练方式为下述，这里论文作了 fixed variance 假设：

\[ \min_\beta \frac{1}{|\mathcal{D}|} \sum_{(s_t, a_t) \in \mathcal{D}} \frac{1}{2} \left\|a_t - \hat\pi_\beta(s_t)\right\|_2^2 \]

好像 behavior clone 和 distribution shift 都是模仿学习的东西，这里还真的不太会，后面补。

一个可能有用的 slide。

---

似乎学明白了一点东西，模仿学习是一种改进的 RL，其面对的是无法合理得到 reward signal 的 RL 环境，但是其可以获得部分专家数据，那么我们就可以模仿专家数据进行学习，这就是 behavior clone。

behavior clone 的基本思想借鉴了监督学习。例如我们获得了专家数据集 \(\mathcal{D}\)，那么我们的训练方式就是：

\[ \theta^* := \mathop{\rm argmin}_\theta \mathbb{E}_{(s, a) \sim \mathcal{D}} \mathcal{L}(\pi_\theta(s), a) \]

这里 \(\mathcal{L}\) 是 loss，可以设定为负 reward 等。

但这个方法有很多问题，包括在数据集较小的时候学习效率极低、无法分辨真正导致 reward 上升的行为等，但是更为致命的问题是 distribution shift。

这个问题指的是专家数据和实际数据分布不一致，尤其指训练集和测试集分布之间有偏差。由于我们参考了监督学习的思想，behavior clone 实际上也继承了监督学习的一个假设，即数据集分布和真实数据分布一致。但是，即使这个假设并不严格成立，监督学习也是可以忽略的，因为监督学习的各个数据之间独立，可以忽略。然而 RL 是逐步决策的，某一步的偏差可能导致后续误差的累积导致后续决策的极大偏移。

有一种解决方式是数据聚合，这里就和论文无关了，故不做讨论。

而通过 \(\hat\pi_\beta\) 重新初始化 \(\pi_\theta\) 的方式为正态分布初始化，均值设定为 \(\hat\pi_\beta\) 而标准差置 \(1\)。论文认为在这里将 BC 和普通的梯度下降相结合可以使得 \(\pi_\theta\) 趋向于新数据集 \(\mathcal{D}\) 代表的 policy，可以认为是一种 distribution shift 问题的补救措施。

为了进一步补救，其进一步使用 KL-based trust region optimization。总体上 BREMEN 的 policy 更新策略就是：

\[ \theta_{k + 1} = \mathop{\rm argmax}_\theta \mathbb{E}_{(s, a) \sim (\pi_{\theta_k}, \hat f_{\phi_i})} \left[\frac{\pi_\theta(a \mid s)}{\pi_{\theta_k}(a \mid s)} A^{\pi_{\theta_k}}(s, a)\right] \]

这里要求：

\[ \mathbb{E}_{s \sim (\pi_{\theta_k}, \hat f_{\phi_i})} D_{\rm KL}(\pi_\theta(\cdot \mid s) \parallel \pi_{\theta_k}(\cdot \mid s)) \leq \delta \]

此外定义初始值：

\[ \pi_{\theta_0} := \mathcal{N}(\hat\pi_\beta, 1) \]

得到的 BREMEN 算法流程为：

总体来看，简化了部署的过程，然后使用类似 TRPO 中信任域的方式约束了 agent 的行为。

Experiments

既然 BREMEN 的优势在于少量部署条件下能高效学习，其第一个实验就是和其余 RL 在约束部署次数的条件下比较 reward，效果是明显的：

这里每一条竖直虚线都代表一次部署，部署次数约束在五次到十次之间，每次 batch size 约束在 200k 到 100k。可见 BREMEN 明显优于大部分算法，而几乎仅劣于完全在线的 SAC，但是 SAC 可能需要近百万量级的部署次数。

此外，为了测试 data efficiency，论文采用的方法是训练一个 SAC 后用该 policy 采集一个 dataset 并用该 dataset 训练各种离线算法，根据下述结果可以看出 BREMEN 能在很小的数据集下就能超越 BC 的 baseline，而其余类似 BCQ 等的方法甚至无法超越 baseline，这说明了 BREMEN 不仅 deployment efficient 而且是 data efficient 的：

Final analysis

说实话由于 RL 基础还是有点欠缺，自己不是很了解信任域相关方法的数学基础，所以对其数学论证也没看很细致，尤其是涉及到 implicit KL regularization 的部分。

但总体而言这篇文章提出的核心思想是需要考虑部署带来的开销，并且提出了利用 BC 等方法来强化模型的 exploitation 能力并且尝试使用信任域的想法约束 agent 的行为，总体上依然符合离线 RL 的两大思路。

数学证明之类的可能真的要等到补补 TRPO 之类 RL 方法之后写，目前打算基于 Sutton 把博客里面这些有关 RL 的一些东西串起来。