在线分配问题
需求重复到达—>每个需求都要决策动作：获得奖励和消耗资源。
问题：在资源约束下最大化奖励
挑战：未来需求未知

提出一种算法：
每个资源有权重
用调整权重奖励的贪婪方法来执行动作。
用镜像下降更新权重

算法
镜像下降允许
乘法权重更新

对比现有算法
基于对偶。含有拉格朗日变量对每种资源
现有方法：为对抗输入设计、需要求解线性规划或者凸优化。本文简单快速、不用解凸优化。
模型
有限范围T个阶段、
j=1…m 有Bj容量限制
在每个阶段：
接受一个凹的、有界的奖励函数ft
接受一个消耗矩阵bt
在一些凸的紧凑的集合X中采取动作xt
收集奖励ft(xt)和消耗bt(xt)

离线问题：
目标是max ft(xt)，就一个约束小于容量约束。

在线问题：
假设需求(ft,bt)服从未知独立同分布
用P表示需求的未知分布

基于历史观察数据做决策
已知T的长度和容量B
不知道输入的分布
需要满足资源约束

在输入分布P下算法A的累计期望奖励 R(A|P)
输入P的离线期望奖励 OPT§
输入分布最坏情况的Regret(A) 是以上两者相减。

拉格朗日对偶抢救？

从资源约束引入拉格朗日乘子 u ∈Rm 得到
公式D(u|P) （关键点：决策分解across time）
对于任意u>0 ，对偶函数提供了一个上界。
公式OPT§ < D(u|p)（关键点：对于最优对偶变量，上界是无症状asymptotically紧,当T和B很大时）

拉格朗日对偶抢救？（连续）
挑战1：如何决策
如果最优对偶变量u已知，我们能采取action 来最大化对偶变量调整后的奖励。
xt=argmax（ft(x)-(u)Tbtx）
但是我们事先不知道u*
挑战2：我们如何计算好的对偶变量
我们能获得对偶函数的次梯度的噪音，无偏的观察。
通过使用镜像下降最小化对偶函数来计算对偶变量。

在线对偶镜像下降算法
初始化对偶解uo∈Rm ，η步，参考函数
循环 t=1…T
1观察需求(ft,bt)
2决定一个动作：xt=argmax(ftx-utbtx)
3如果资源够：执行一个动作xt。如果执行空动作
4更新资源：Bt+1=Bt-btxt
5更新对偶变量μt+1=argmin(随机对偶次梯度μ+1/η贝格曼散度)

举例
投影梯度下降：如果参考函数是l2范数，对偶的更新是：
公式（）
乘法权：如果参考函数是负交叉熵，更新是
公式（）
如果奖励消耗超过了预算B/T —> 对偶变量上升并且资源价格提高 —>未来动作消耗资源更谨慎。
理论结果
定理：假设参考函数是坐标可分并强凸的。如果η约等于T-1/2 次，B和T成比例，那么在线对偶镜像下降算法的regret满足
公式（）
可能的结果：
1算法是渐进最优的，例如1/T Regret（A）->0 as T->∞
2界是紧的，更好的regret界是不可能的
3这个界在其他约束可能不紧，尤其是对比周期性求解凸优化的算法。
证明的主要两步
1算法不过早耗尽资源
公式（）
2在用完资源前，平均累计奖励接近于对偶目标值：
公式（）

结论
1有预算的重复拍卖的投标；有差异的在线匹配
2简单快速的求解随机输入，不用解凸优化
未来工作
1分析不同输入的表现
2合并正则项来最大化二阶目标（公平或负载均衡）