2022 年 12 月论文笔记

12 月开始就得准备做毕设了，先要充分阅读文献，确定自己要做的方向有什么要解决的问题，以及目前已经有的探索和目前还存在的困难。

\[ \newcommand{\b}{\boldsymbol} \]

Learning Tailored Adaptive Bitrate Algorithms to Heterogeneous Network Conditions - A Domain-Specific Priors and Meta-Reinforcement Learning Approach

黄老师的文章，作为起手还是需要好好看看的。

这篇文章的基本概念是，基于学习的 ABR 已经能够实现一个平均而言优秀的 ABR 算法，但是对于部分特殊的网络环境其依然表现不佳，而这也就是所谓的个性化。然后这篇文章使用了 meta RL 的方式实现了 AABR（其实应当是 \(A^2BR\)，但是我真的不想打公式了，AABR 表示 Adaptation of ABR）。

AABR 首先离线学习一个元算法，之后再在在线的个性化环境下学习一个针对当前网络环境的个性化算法。另外，还需要不断优化离线学习来保证元算法的优势。

Introduction

首先对 ABR 算法做了总结，启发式算法根据当前网络情况和一部分状态变量给出决策，但是只有在选定较好的算法参数的时候这种算法才能表现较好。基于学习的算法则根据网络情况学习这些参数。然而总而言之，这些算法都不会自动调节自己的算法参数，尤其在面对变化较多的网络环境下时，这些算法表现较差。

之后是通过实验说明了现在的网络状况不仅是多样性（diverse）的，更多的是独一无二（unique）的。基于这一点，这篇文章认为做用户个性化是一个重要的提升。

所以基于 Input-driven Markov Decision Process (IMDP)，本文提出了 AABR。分为离线和在线两步，具体的训练方式见后续。

总结一下这篇文章的工作就是确认了当今网络环境的独特性，并通过 meta RL 解决了 ABR 的个性化问题。

Background & Motivation

关于 ABR 之类的介绍这里忽略，主要看这篇文章如何论证当今网络的多样性。

多样性分为三个方向去论证，即不同用户间差异、不同场景间差异以及已有的部分 ABR 算法在这些网络环境下的表现。

用户间差异和场景间差异可以关注下图：

可以首先注意到网络吞吐率和 RTT 的变动是相当大的，而如果观察具体的用户，也可以发现用户之间的网络状况差异也很大，部分用户网络稳定（整体带宽 CDF 陡峭）而部分用户的网络波动较大，而且各个用户的网络指标平均值也差异较大。

对于场景，也可以注意到步行、地铁、公交、汽车的网络情况也各有不同，并不能一概而论。

如果从 ABR 的角度出发，这篇文章在两个不同环境下测试了若干个 ABR 算法的性能，得到的结果是：

显然可以注意到已有的算法都很难兼顾两种情况，常常顾此失彼。这就意味着不稳定的网络情况很容易导致这些算法失效，从而也难以实现用户个性化。

Methods

Input-driven Markov Decision Process

基本而言是在正常的 MDP 中引入了 input process \(\mathcal{Z}\)，这个时候环境的转移概率定义为：

\[ \mathbb{T}[s' \mid s, a, z] := \mathbb{P}[s_{t + 1} = s' \mid s_t = s, a_t = a, z_t = z] \]

此外，决策依然仅仅和 \(s_t \in \mathcal{S}\) 有关，也就是说具体行为 \(a_t \in \mathcal{A}\) 与 \(z_t \in \mathcal{Z}\) 是独立的。

进一步的价值函数定义为：

\[ Q(s, a, z) := \sum_{s' \in \mathcal{S}} \mathbb{T}[s' \mid s, a, z](r(s, a, z) + \gamma V(s', z')) \]

在 IMDP 下，最优策略也就定义为：

\[ \pi^*(s, z) := \mathop{\rm argmax}_{a \in \mathcal{A}} \sum_{s' \in \mathcal{S}} \mathbb{T}[s', z' \mid s, a, z]\left[r(s, a, z) + \gamma \max_{a' \in \mathcal{A}} Q(s', a', z')\right] \]

可以注意到，如果两个 agent 运行相同的 policy \(\pi\)，其不同之处仅仅是 input process \(\mathcal{Z}_{1, 2}\) 不同。可以注意到这两个 agent 将会始终保持相同的决策，所以其价值函数相同当且仅当 \(\mathcal{Z}_1 = \mathcal{Z}_2\)。

如果在完全得知 input process \(\mathcal{Z}\) 的条件下，求解最优策略相当于一般的强化学习问题，可以通过大量的强化学习方法完成。但是我们现在需要假定 input process 是完全不可感知的，在这种条件下，一般强化学习方法学习到的最优策略 \(\hat\pi^*\) 的价值函数实际上是与 input process 无关的，其价值函数用 \(Q(s', a')\) 表示，其满足：

\[ \max_{a' \in \mathcal{A}} Q(s', a') = \mathbb{E}_{z'} \max_{a' \in \mathcal{A}} Q(s', a', z') \]

所以现在解决 input process 未知条件下的最优策略求解问题就是最重要的。

Meta RL with Domain Knowledge

总之就是又阐述了一边 AABR 分为离线和在线两个训练过程，离线训练一个元算法之后在线训练一个个性化 ABR 算法。那么两个问题就是：

1. How to obtain a good parameter initialization for fast-learning?

2. How to efficiently learn tailor-made ABR algorithms online?

Model Agnostic Meta-Learning

总之就是选定了 MAML 作为 AABR 的核心算法，MAML 的论文后面慢慢推着看。

不过这一部分也阐释了为何 MAML 适合用于这个场景，原文是：

We find that model agnostic meta learning (MAML) is quite suitable in personalized ABR scenarios where the network traces on each user are quite limited.

Specifically, MAML consists of an inner loop and an outer loop.

也就是说从数据集的角度和训练流程的角度上说，MAML 和这个实验场景的契合度比较高。

Leveraging Domain Knowledge

总体的含义是设计了一个模拟器用于生成数据以及相关的启发式算法，一方面补充了现实世界中数据量不足的问题，另外一方面其代表的启发式算法可以在 policy 无法处理某些状态的时候作为 backup 使用。

注：这一部分可能需要结合下面的 overview 仔细学一下，然后对这里做一些扩充，因为这里模拟器的细节应该是做数据扩充的重要部分。

AABR Overview

系统的大致结构为：

Basic Training Algorithm

在设计网络的输入的时候首先需要考虑的是什么才是真正需要考虑的状态，这篇文章采用的方式是首先将所有可以使用的状态都作为输入以训练一个 teacher network，之后采用类似模仿学习的方式，采用类似决策树等较为轻量级的模型去模仿神经网络的策略，之后再使用决策树剪枝的方式去获取真正有意义的非平凡状态。

这个方法似乎是比较好玩的一个方法，用于筛选真正有用的输入状态。

这里剪枝的目的也是为了压缩最后的成本。

最后筛选出来的状态包括：

• 上一次选定的视频块质量 \(q_t\)
• 目前的缓冲区占用率 \(b_t\)
• 前 \(k\) 个视频块传输时网络吞吐率 \(C_t\)
• 前 \(k\) 个视频块的下载时间 \(D_t\)
• 前 \(k\) 个视频块的应答时间 \(P_t\)

这里为了控制成本，实验中选取 \(k = 5\)。

另外，为了保证模型的泛化性，这里需要将参数正则化，这样至少能保证模型面对完全没有经历过的网络环境不至于将其认为非法输入。

模型的输出和正常的 AC 网络没有很大的差别，都是 Actor 网络输出一个 softmax 后的概率张量表示各个行为的决策概率，而 Critic 网络输出一个标量表示对当前状态的价值评估。

Maximum Entropy PPO (ME-PPO)

这里的训练策略是 ME-PPO，其与 PPO 的差别在于最优行为的定义里纳入了熵：

\[ a_t^* := \mathop{\rm argmax}_a \hat{\mathbb{E}}_t\left[\sum_t \gamma^t(r_t + \lambda H^{\pi_\theta}(s_t))\right] \]

这里定义熵为：

\[ H^{\pi_\theta}(s_t) = -\sum_{a \in \mathcal{A}} \pi_\theta(a \mid s_t) \ln\pi_\theta(a \mid s_t) \]

元学习要求在离线环境下更重视 exploration 而在线环境下更重视 exploitation。这里将熵纳入考虑，如果策略 \(\pi_\theta\) 对动作空间 \(\mathcal{A}\) 中的所有动作给出的概率约趋向于平均，则熵越高，从而越会支持这样的选择。

ME-PPO 的具体策略是基于 Dual-PPO 的 double clip 策略，具体如下：

\[ \begin{aligned} \mathcal{L}^{\rm PPO} &:= \min\left(\frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\rm old}}(a_t \mid s_t)}(\theta) \hat A_t, {\rm clip}\left(\frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\rm old}}(a_t \mid s_t)}(\theta), 1 - \varepsilon, 1 + \varepsilon\right)\hat A_t\right) \\ \mathcal{L}^{\rm Actor} &:= \begin{cases} \hat{\mathbb{E}}_t[\max(\mathcal{L}^{\rm PPO}, c\hat A_t)] & \hat A_t < 0 \\ \hat{\mathbb{E}}_t[\mathcal{L}^{\rm PPO}] & \hat A_t \geq 0 \\ \end{cases} \end{aligned} \]

这里 \(\hat A_t\) 是优势函数，定义为：

\[ \hat A_t := r_t + \gamma(V^{\pi_\theta}(s_{t + 1}) + \lambda H^{\pi_\theta}(s_{t + 1})) - V^{\pi_\theta}(s_t) \]

这里 \(c, \varepsilon\) 是用来控制梯度的超参数。

AABR 中的 Critic 网络的训练策略就是最小化优势函数的均方误差：

\[ \mathcal{L}^{\rm Critic} := \frac12 \hat{\mathbb{E}}_t[A_t]^2 \]

从而整体的 loss 可以总结为：

\[ \nabla\mathcal{L}^{\rm MEPPO} := -\nabla_\theta \mathcal{L}^{\rm Actor}(\pi_\theta, \hat A_t) + \nabla_{\theta_v} \mathcal{L}^{\rm Critic} \]

---

此外，由于算法对 \(\lambda\) 较为敏感，我们需要在训练过程中不断调节 \(\lambda\)，调节方式较为简单：

\[ \lambda \leftarrow \lambda + \alpha[H^{\pi_\theta}(s_t) - H^{\rm Target}] \]

这个目标在于熵逐步接近目标的时候衰减 \(\lambda\) 以减缓接近速度。

Meta-Learned Policies for Offline Stage

注：具体的训练方式后续补充。

Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks

这是 MAML 训练方法的原始论文，看情况有没有时间做一个复现。

文章的主要贡献就是一个元学习方式，并且似乎泛用性很广：

In this work, we propose a meta-learning algorithm that is general and model-agnostic, in the sense that it can be directly applied to any learning problem and model that is trained with a gradient descent procedure.

元学习的核心在于训练好的模型能够迅速通过少量数据学习到新的任务，并且其能够应用到大量的下游任务中。这篇文章将训练模型理解为在模型内部建立起适用于某种任务的特征表示，如果这种表示能够适合于多种任务，那么我们只需要进行合适的微调就可以迅速适应新的任务。如果从动力系统的角度理解，我们需要提高需要完成的任务的 loss 对参数的敏感度，这个敏感度越高，参数的变化对 loss 的提升的影响越大。

Model-Agnostic Meta-Learning

Meta-Learning Problem Set-Up

这里严格定义了元学习需要解决的问题。

首先我们需要形式化定义什么是任务，这篇文章定义为：

\[ \mathcal{T} := \{\mathcal{L}(\b x_1, \b a_1, \cdots, \b x_H, \b a_H), q(\b x_1), q(\b x_{t + 1} \mid \b x_t, \b a_t), H\} \]

这里 \(\mathcal{L}\) 表示 loss，\(q(\b x_1)\) 是初始状态的分布，\(q(\b x_{t + 1} \mid \b x_t, \b a_t)\) 是状态转移的概率分布，\(H\) 是 episode 的长度。这个定义同时涵盖了普通的强化学习和监督学习，其中监督学习中 \(H = 1\)。

模型本身描述为一个函数 \(f\)，其接受当前状态 \(\b x\) 并给出输出 \(\b a\)，即 \(\b a = f(\b x)\)。模型不断在该任务中给定 \(\b a_1, \b a_2, \cdots, \b a_H\)，而 loss \(\mathcal{L}\) 则给出了实际的反馈，这种反馈可以是分类问题中的失配损失或者 Markov 决策过程中的负收益。

在元学习中我们需要考虑一系列的任务的分布，这里记作 \(p(\mathcal{T})\)。如果我们要求 \(K\) shot learning，对于每一个从 \(p(\mathcal{T})\) 抽取的具体任务 \(\mathcal{T}_i\)，我们需要再通过 \(q_i\) 抽取 \(K\) 个样本，并且考虑 \(\mathcal{L}_{\mathcal{T}_i}\) 的反馈。

之后直接搬一个论文原句，也应该是论文后面算法设计的主要出发点：

The model \(f\) is then improved by considering how the test error on new data from \(q_i\) changes with respect to the parameters.

A Model-Agnostic Meta-Learning Algorithm

这里提供了算法设计，一个关键词就是之前提到的敏感度。

考虑用参数 \(\theta\) 表示的模型 \(f_\theta\)。在学习具体的任务 \(\mathcal{T}_i\) 的时候，参数的更新方式为：

\[ \theta \leftarrow \theta - \alpha\nabla_\theta\mathcal{L}_{\mathcal{T}_i}(f_\theta) \]

为了简化记号，我们假设在元学习之后学习具体任务仅用了一次梯度更新，此时任务 \(\mathcal{T}_i\) 的最优参数就是 \(\theta_i' := \theta - \alpha\nabla_\theta\mathcal{L}_{\mathcal{T}_i}(f_\theta)\)，那么元学习的目标是：

\[ \min_\theta \sum_{\mathcal{T}_i \in p(\mathcal{T})} \mathcal{L}_{\mathcal{T}_i}(f_{\theta_i'}) = \min_\theta \sum_{\mathcal{T}_i \in p(\mathcal{T})} \mathcal{L}_{\mathcal{T}_i}(f_{\theta - \alpha\nabla_\theta\mathcal{L}_{\mathcal{T}_i}(f_\theta)}) \]

那么还是使用简单的梯度下降，元学习中的参数更新就是：

\[ \theta \leftarrow \theta - \beta\nabla_\theta \sum_{\mathcal{T}_i \in p(\mathcal{T})} \mathcal{L}_{\mathcal{T}_i}(f_{\theta_i'}) \]

在这里我们注意到出现了二阶梯度，部分深度学习框架能够支持这一操作，但本文也同样指出作一阶近似（即舍去二阶及以上的高阶项）是可行的。

基于此，MAML 的整体框架为：

Species of MAML

本文这里举出了监督学习和强化学习中运用 MAML 的例子，这里我们只关注强化学习。

强化学习特化的 MAML 主要关注的是 loss 的选定，这里选定的就是最经典的负收益。另外，此时 \(q_{\mathcal{T}_i}\) 实际上就是环境中的状态转移概率分布：

\[ \mathcal{L}_{\mathcal{T}_i}(f_\phi) = -\mathbb{E}_{(\b x_t, \b a_t) \sim (f_\phi, q_{\mathcal{T}_i})} \left[\sum_{t = 1}^H R(\b x_t, \b a_t)\right] \]

从而，强化学习特化的 MAML 算法为：

这之后就是一些实验结果了，感觉没啥意思了。

Learning to Adapt in Dynamic, Real-World Environments through Meta Reinforcement Learning

这篇文章似乎没有官方的 code base，只有两个 community code base，现在可以在 这个链接 获取，分别是 Tensorflow 和 Pytorch 版本。

Abstract & Introduction

需要解决的问题依然是生成数据很困难以及测试环境中无法预料到的数据可能导致所训练的策略失效，引言之中也基本上叙述了人类可以很快适应自身机体发生的变化和外界环境发生的变化，提出了如果模型经历了足够多的环境微扰，其就可以很快学习适应新环境。

相比较于原先的 meta RL 对任务的定义，这篇文章提出的模型能够处理每个时间步环境或者任务都在变化的情景。也就是说，原先的 meta RL 不过是提前预设好了需要解决什么样的任务，并且每一个 RL trajectory 仅会属于一个任务，而这篇文章的 RL trajectory 中可以涵盖多种任务并且任何时间都可以切换。所以这篇文章的 meta RL 更为 general。

本文也是有 trade off 的，主要表达如下：

By specifically training a neural network model to require only a small amount of experience to adapt, we can enable effective online adaptation in complex environments while putting less pressure on needing a perfect global model.

也就是说，这篇文章为了能够在少数据条件下快速适应新环境，并不会强制要求这个模型在 global 环境下表现到 perfect。

总而言之，这篇文章主要强调学得快，学习速度大约是每个新任务需要在真实世界中经历 1.5 到 3 小时，不到原有 model-free RL 方法学习时间的十分之一。并且，在同等数据量条件下，这篇文章的模型效果也比其他方法优越。此外，为了展示本文模型的学习能力，其将其真实部署在了机器人上，来学习真实世界的情况。

Related Works

首先提到最原始的强化学习方法没有泛用性，以及 model-free RL 往往需要大量和真是环境交互从而不实际。发展为 model-based RL 之后，就需要面临对环境建模的 model 需要在不同的任务之间调整的问题，首先否决了单一的全局模型，而先前有人尝试通过 GP 方法合并模型不确定性从而让模型能够表示不同的环境，然而这个方法做出了额外的假设且拓展性差且难以运用到高维空间，而本文提出的结果能够通过观察从而快速切换到新的环境。

这里的问题就是我是真的没有太看懂这个 model 到底是对环境建模的模型还是最后要学习的 policy。

还有一种处理方式是首先学习一个全局模型，在测试的时候通过梯度下降进行微调。此外，还有工作表明不需要完美的全局模型，可以微调先验知识来处理小变化。然而，这些方法面临着模型的训练目的与测试时的使用方式之间的不匹配的问题。本文通过明确训练一个能快速有效适应的模型来弥合这一差距。

Preliminaries

Model-Based Reinforcement Learning

马尔可夫决策过程在这里建模为 \((\mathcal{S}, \mathcal{A}, p, r, \gamma, \rho_0, H)\)。这里 \(\mathcal{S}\) 是状态空间，\(\mathcal{A}\) 是动作空间，\(p(s' \mid s, a)\) 是环境状态转移概率，\(r: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\) 是奖励函数，\(\rho_0: \mathcal{S} \to \mathbb{R}^+\) 是初始状态概率分布，\(\gamma\) 是奖励衰减常数，\(H\) 是轨迹长度。

一条轨迹描述为 \(\tau(i, j) := (s_i, a_i, \cdots, s_j, a_j, s_{j + 1})\)，我们的目标是求取最优策略 \(\pi: \mathcal{S} \to \mathcal{A}\) 使得累计收益期望最大。

model-based RL 目标是近似处理 \(p(s' \mid s, a)\)，这个模型也被称为 dynamics model。

Meta Learning

一般的元学习需要给定假设，即训练用的任务和最终的测试任务都是从同一个任务分布 \(\rho(\mathcal{T})\) 中抽取。元学习的目标是获取一个学习流程 \(\theta' := u_\psi(\mathcal{D}^{\rm tr}_{\mathcal{T}}, \theta)\) 以通过小数据集 \(\mathcal{D}^{\rm tr}_{\mathcal{T}}\) 来学习任务 \(\mathcal{T}\)，学习过程可以表示为：

\[ \min_{\theta, \psi} \mathbb{E}_{\mathcal{T} \sim \rho(\mathcal{T})}\left[\mathcal{L}(\mathcal{D}^{\rm test}_{\mathcal{T}}, \theta')\right] \]

其中 \(\theta' := u_\psi(\mathcal{D}^{\rm tr}_{\mathcal{T}}, \theta)\)。

这里的记号是真的复杂，事实上训练过程应该是函数 \(u_\psi\)，训练过程用参数 \(\psi\) 代表，其输出为训练后的最优参数 \(\theta'\)，而 \(\theta\) 表示初始化参数。

另外注意，\(\theta\) 这里是模拟环境的模型的参数，而非 policy 的参数。

Gradient Based Meta Learning

MAML 就是一种基于梯度的元学习方法，其最主要的目标是学习一个较好的参数初始化保证在少数调整中即可实现较好的下游任务。

MAML 的 \(u_\psi\) 就是一般的梯度下降：

\[ u_\psi(\mathcal{D}^{\rm tr}_{\mathcal{T}}, \theta) = \theta - \alpha\nabla_\theta \mathcal{L}(\mathcal{D}^{\rm tr}_{\mathcal{T}}, \theta) \]

如果学习率 \(\alpha\) 是一个固定参数，那么 \(\psi = \varnothing\)，如果 \(\alpha\) 是一个元学习过程中需要学习的参数，那么 \(\psi = \alpha\)。

即使看起来 \(u_\psi\) 是平凡的，但是这种方法的表达能力和下面介绍的方法是持平的。

Recurrence Based Meta Learning

这里借用了 RNN 的思想，在这个方法中，更新函数 \(u_\psi\) 始终需要不断学习，其中 \(\psi\) 是用于更新 RNN 隐含层状态的参数，而 \(\theta\) 是余下的参数。

这里是真的真的真的没看懂，这在说啥？是我前置知识欠缺太多了？

只能希望下面能有个稍微好一点的说明。

Meta Learning for Online Model Adaptation

之前提到过本文的 trajectory 中任务可以随着时间步推进而变化，所以本文设定的目标是根据前 \(M\) 个时间步的数据预测未来 \(K\) 个时间步情况，这里 \(M, K\) 都是固定的超参数。

所以在这样的设定下，训练目标就是：

\[ \begin{aligned} \theta_{\mathcal{E}}' &= u_\psi(\tau_{\mathcal{E}}(t - M, t - 1), \theta) \\ \min_{\theta, \psi}& \mathbb{E}_{\tau_{\mathcal{E}}(t - M, t + K)} [\mathcal{L}(\tau_{\mathcal{E}}(t, t + K), \theta_{\mathcal{E}}')] \end{aligned} \]

而这里 loss 定义为：

\[ \mathcal{L}(\tau_{\mathcal{E}}(t, t + K), \theta_{\mathcal{E}}') := -\frac{1}{K} \sum_{k = t}^{t + K} \log\hat{p}_{\theta_{\mathcal{E}'}}(s_{k + 1} \mid s_k, a_k) \]

GrBAL 采取的更新策略为：

\[ \theta_{\mathcal{E}}' = u_\psi(\tau_{\mathcal{E}}(t - M, t - 1), \theta) = \theta_{\mathcal{E}} + \psi\nabla_\theta\frac{1}{M} \sum_{m = t - M}^{t - 1} \log\hat{p}_{\theta_{\mathcal{E}}}(s_{m + 1} \mid s_m, a_m) \]

ReBAL 这里又是没看懂，所以这个基于循环模型的到底是个什么东西。

Model Based Meta Reinforcement Learning

这一部分就是在讲解如何在线上做 adaptation，我觉得整体不如直接看算法直观：