workload白天和晚上不一样，不同的日子也不一样（例如双十一）
因为没有办法对workload估计得很准，云系统用户总是申请比所需要的多的资源，这些“slack”是一种浪费
Autopilot目标：减少slack的同时最小化OOM
Autopilot操作：调整并行任务数，调整单个任务的资源使用量
scaling分为水平scaling和垂直scaling，水平scaling是调整并行任务数，垂直scaling是调整单个任务的资源使用量，这篇文章主要讨论内存的垂直scaling
Preprocessing:
每秒记录一个usage数据点；
CPU per-task histogram: 一个向量，每个分量表示在这个time window内每个usage buckets的usage数据点数量；
memory per-task histogram: peak memory usage in a time window；
per-job histogram: sum over per-task histogram；
Moving window recommenders 希望需求上升时能很快上升，需求下降时能慢慢下降
提出了三种滑动窗口的方法，都比较保守，而且会在推荐值的基础上加一点余量
大概的思想是，不只根据数量去做平均，还要根据load的大小 (magnitude) 去做平均
max适合OOM最敏感的任务，Spj适合比较敏感的任务，Savg适合不敏感的任务
Recommenders based on machine learning 构造了一个损失函数包括过去采样的overrun，underrun，以及switching cost。
同时存在多个arg min的模型，它们的超参不一样，用的时候选择损失函数最小的。
这些模型是离线+A/B test调出来的，没有给具体方法，只有loss function。
horizontal 指定一个目标平均util，通过伸缩replica来维持这个值。
策略
实验结果是滑动窗口在减少OOM上更好，ML方法在减少slack上更好。
后面主要是讨论用户体验。
有一篇值得follow的工作：Hydra: a federated resource manager for data-center scale analytics，是微软的资源管理系统，在这篇论文之前。
这是hkust Kai Chen老师组和北大Xin Jin老师的工作。如果把RL用在拥塞控制里，现有的做法是把算法的优化目标，比如吞吐率，延迟，丢包等作为reward。不同目标对应的权重是预先设置好的，但不同的应用会有不同的目标。这篇论文用了一个多目标的RL算法，除了网络状态之外，把reward的权重也作为RL的状态输入，期待网络能学到根据当前reward权重来选择对现在来说更好的action。reward的权重会随环境变化，计算reward的时候就用当前的权重。用的RL算法是PPO再加了一个entropy项的连续算法，预测下个时间发送速率的变化值。
感觉这个MORL是挺靠谱的，如果实际上训练时候的reward weight pattern不会太影响实际场景的预测的话。拥塞控制对机器资源的要求也没有做资源调度的多，只要有网络就可以在线训练。
离线训练先选几个点训练到收敛，然后找到一条最短路径，以此选择路径上的点对应的权重训练，每个点上的训练不必训练到收敛才去下一个点，而是一直遍历训练直到所有点都收敛。
作者提出的是一个RL和Constraint Programming结合的求解组合优化问题的模型，在RL环境和约束规划模型中引入了基于动态规划模型的编码，编码后学习部分用强化学习进行，求解部分用约束规划进行。简单来说是用RL来辅助约束规划在搜索解空间时的分支决策。
为什么可以用动态规划呢？强化学习应用于组合优化问题是model-base的，既知道状态转移的情况，也知道reward函数。但是我觉得不是deterministic transition的情况下也是可以的，因为现在有很多model free的模型（AC）。
论文正文中给的例子是用RL的结果辅助分支界定法，RL的结果作为新的分支，分支界定法是会舍弃掉不可行解的，所以处理了约束问题。附录中还提到RL与另外两种搜索策略的结合。
框架：
DQN辅助分支界定法：
对于有时间窗口约束的旅行商问题，这篇文章是用GAT去编码。最后实验结果比单纯的DRL或者CP要好，与DRL做组合优化的其他文章相比也更好，而且与现行的工业组合优化求解器相比也有优势。
有时间窗口约束的旅行商问题的SOTA heuristic是A General VNS heuristic for the traveling salesman problem with time windows，前人已经用可变邻域搜索(VNS)的方法解决得很好了，能不能强化学习+VNS？
代码写得挺好的，RL和CP的主要结合点在这里，分支定界法取分支的时候，由DQN给出一系列Q值，CP选择最大的那个Q值对应的action，把domain分成采取这个action和采取其他action。
基于这种方法，有人还做了一个叫SeaPearl的CP求解器框架，用强化学习作为value-selection heuristics，用图作为输入。
https://github.com/corail-research/SeaPearl.jl
简单介绍 网络规划传统是用线性规划的解法，但是线性规划没有办法scale，设计几十个节点就很难求解，所以一般会加入一些人为的constraint，就需要在解的最优性和问题的易解性上做权衡。而且这些启发性的求解方法不通用，需要专家进行很多检验和重复的工作。
因为网络规划包括多步骤决策和cost的优化，很适合转化为DRL求解，损失函数优化是基于全局的，而人工的决策很多时候都是局部的。DRL需要很高的样本复杂性，不过很多现实中的网络规划都可以用来训练DRL。网络规划评估很方便，检查在所有网络故障情况下是否还能达到了服务的要求，作者的实现是解一个线性规划问题。
论文用一种domain-specific node-link transformation的方法，使用GNN来编码网络图，先用DRL来代替人工操作对搜索空间进行剪枝，然后再求解线性规划问题。我认为本质上是用强化学习辅助解决大型的线性规划问题。
Network Planning 文中的网络规划主要面向的是内容提供商的广域网网络规划，连接不同的机房和数据中心。
网络规划需要同时考虑网络层和物理层。在网络层，网络规划需要决定ip连接的容量，以及路由器和转发器需要配置的数量；在物理层，网络规划需要考虑启动多少条光缆，以及之后应该铺设和购买的光缆。
网络规划是分阶段的，分为短期规划和长期规划。因为网络建设需要的时间周期很长，不能一次就建成最优的网络拓扑结构。短期规划要能够符合之后的长期规划。虽然分为了长期和短期的规划，但是它们的求解方法是可以合并的，具体后面会讲到。
提出优化问题 目的是优化总的网络开销，包括网络层和物理层，还可以根据应用需要，把数据流的时延等因素也考虑进去。为了简化问题，将网络开销抽象为所有ip连接的开销总和，单个ip连接的开销包括ip连接底层用到的光缆的全部开销和实现指定ip容量的每公里开销。
注：spectrum efficiency是指在给定频段上可以传输的信息速率，通常的单位是bit/s/Hz，但是这里的单位是Hz/bit/s。
以往的痛点是网络拓扑太大，求解器无法求解，需要手工做一些剪枝的工作，例如分成几个子拓扑分别求解，合并一些边和点，限制条件一点一点加等，使得整个优化不是基于全局的。同时这些求解的启发性工作也不是通用的，不同的网络规划又需要不同的启发性工作。
NEUROPLAN 对于长期的网络规划，就算一个action的影响只能在后几个周期才会被评估，但是DRL可以设计延迟奖励，学习中会朝着全局目标去采取action。在RL求得该方法的最优值后，引入α因子去得到一个子搜索空间，对优化效果和易处理性上做权衡。
挑战 1. 动态网络拓扑 在网络规划问题上，环境的结构是动态变化的。DRL的输入是一个图，而不是一些向量，而且这个图会根据agent与环境的交互而发生变化。
解决方案：使用GNN将动态的网络拓扑编码成一个向量，作为agent的输入。
2. 优化效果和易处理性的权衡 RL的结果不一定是最优的。
解决方案：分成两个阶段。第一个阶段用DRL找一个较合理的解，第二个阶段在这个解附近的子搜索空间用线性规划尝试找一个最优解。给了一个α参数去调整想要子搜索空间的大小。
合并长短期规划的求解 短期规划是在已有ip连接的网络拓扑上做决策，而长期规划时事先不存在ip连接。在长期规划时，可以将一些之后可能会有的候选ip连接加进去，把他们的容量设为0，然后像短期规划那样求解。
算法 domain-specific node-link transformation 实际意思是将网络拓扑的边映射为点，对于这些点，如果对应的网络拓扑的边有相同的端点，就将这些点连接起来。就是简单的边和点互换身份。
state表示 用当前的容量作为ip连接的状态特征。并对状态每个维度的特征在全局上进行标准化。
action表示 action是给特定的ip连接加容量，每次容量增加有上限而且增加的值不是连续的，每次只增加一个ip连接的容量。就是说如果每次最多可以增加m个单位的容量，有n条ip连接可以选择，那么action空间就是m*n。
作者建议action只能增加容量不能减少，作者宣称只可增加和可增加可减少这两种方案的搜索空间是一样的，同时只可增加的方案action空间更小，而且只要当前情况通过失败检查，那么之后的step也就不用检查了，因为加容量更加容易通过失败检查。
一味增加容量会导致超出光纤的频谱限制，作者对action增加容量的超出部分应用一个action mask，我的理解是屏蔽掉超出限制的连接更新。
reward表示 如果只有一个final reward，训练会非常难，作者用的是dense reward，每次增加容量都给一个reward，但是把累计的final reward放到[-1, 0)。并且超出了预设的迭代次数后会有一个-1的penalty。
强化学习训练算法 Actor-Critic algorithm
值函数是为了解决信用分配问题，能够在延迟奖励到来之前判断动作的好坏
值函数使用状态值函数，而不是动作值函数，因为动作值函数有高偏差（？）
使用全部奖励来估计策略梯度，尽管无偏但是方差大；Actor-Critic方法使用值函数来估计奖励，能够降低偏差但是方差较大
advantage estimates: action相比于其他选择的优势程度，越大说明这一个action越好
GAE是generalize advantage estimator，几乎所有先进的policy gradient算法实现里面都会用到它
GCN 剪枝 把DRL的结果作为线性规划里面的对每个ip连接容量的最大值约束，并乘以一个≥1的α值，作为权衡优化效果和易处理性的参数。
规划评估 给定故障下的流量会不会超出约束，应该就是算一个线性规划问题有没有解。作者还做了些优化，一个是将相同源点的流约束合成一个；一个是“有状态的故障检测”即只要一个网络可以承受住故障，那么比它容量大的网络更加可以承受住故障。
实验 以纯线性规划求解和加入启发式设置的线性规划求解作为对照组。
结果是在纯线性规划求解的规模中，NEUROPLAN差不多持平；在纯线性规划不能求解的规模下，NEUROPLAN的cost可以低于人工启发式设置的线性规划求解。
GNN的层数不太影响结果，在简单问题上不用GNN层数为0也能收敛。
只有在容量更新集中于某些ip连接的情况下，每个step允许增加的单次最大容量才是越大越好。...
前言 现在大部分的边缘计算或者联邦学习的论文，都不免得会提出一个组合优化问题。但是我们现在做的很多组合优化问题都带有复杂的约束。
如果想直接用端到端的深度学习去做，无论是DL还是DRL，和传统的求解器相比，都是既没有办法保证能够得到可行解，也没有办法保证最优解。
提高解的可行性的一个很原始的方法是加惩罚项或者在目标函数上用拉格朗日乘数法。拉格朗日乘数法每有一个约束就要给目标函数加一项，最后一个目标函数有成千上万个项就尴尬了。又或者用更复杂的DRL网络结构（HDRL等），获得更好的性能。但是这和现在的计算机视觉任务或者自然语言处理任务刷分一样，在简单问题上你可能有100%的准确率，但是更复杂的问题又没有办法保证准确率100%，可行性和最优性也一样。
因此现在很多工作都喜欢多次采样取最优值，同时大大提高了可行性，但这也还是原始的做法，没有真正解决约束问题。
Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization (AAAI2021) 作者提出的是一个RL和Constraint Programming结合的求解组合优化问题的模型，在RL环境和约束规划模型中引入了基于动态规划模型的编码，编码后学习部分用强化学习进行，求解部分用约束规划进行。简单来说是用RL来辅助约束规划在搜索解空间时的分支决策。
为什么可以用动态规划，强化学习应用于组合优化问题是model-base的，既知道状态转移的情况，也知道reward函数。但是我觉得不是deterministic transition的情况下也是可以的，因为现在有很多model free的模型（AC）。
论文正文中给的例子是用RL的结果辅助分支界定法，RL的结果作为新的分支，分支界定法是会舍弃掉不可行解的，所以处理了约束问题。附录中还提到RL与另外两种搜索策略的结合。
和整数规划相比，约束规划可能小众一点，但不一定差，整数规划只能解线性问题和部分非线性问题，但约束规划可以解更general的问题。想讲这篇论文用的强化学习提供搜索heuristic的思路，这个思路是无关CP和MIP的，只是因为论文比较新才选的，因为新的论文，介绍和相关工作里面也能学到更多。
框架：
state: 点的特征，比如时间窗和坐标的静态特征，还有和DP相关的动态特征；边的特征，距离；
action: 对应DP的control；
transition: 也是DP的转移；
reward:
1+UB是一个严格上界，保证reward是正的，避免出现负reward导致提前结束。
DQN辅助分支界定法：
对于有时间窗口约束的旅行商问题，这篇文章是用GAT去编码。最后实验结果比单纯的DRL或者CP要好，与DRL做组合优化的其他文章相比也更好，而且与现行的工业组合优化求解器相比也有优势。
代码写得挺好的，RL和CP的主要结合点在这里，分支定界法取分支的时候，由DQN给出一系列Q值，CP选择最大的那个Q值对应的action，把domain分成采取这个action和采取其他action。
基于这种方法，有人还做了一个叫SeaPearl的CP求解器框架，用强化学习作为value-selection heuristics，用图作为输入
https://github.com/corail-research/SeaPearl.jl
A General VNS heuristic for the traveling salesman problem with time windows
这个应该是SOTA heuristic
前人已经用邻域搜索的方法解决得很好了，能不能强化学习+邻域搜索？
Solving mixed integer programs using neural networks（DeepMind和谷歌Research的团队） 提出了两个组件：Neural Diving和Neural Branching。
Neural Diving是通过深度神经网络生成一个partial assignments，然后交给solver去求解剩下的变量
Neural Branching是通过深度神经网络去模仿学习一个剪枝policy。
最先提出用二部图encode的应该是这篇文章(Exact Combinatorial Optimization with Graph Convolutional Neural Networks)。...