• Dual Mirror Descent for Online Allocation Problems


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

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

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

    对比现有算法
    基于对偶。含有拉格朗日变量对每种资源
    现有方法:为对抗输入设计、需要求解线性规划或者凸优化。本文简单快速、不用解凸优化。
    模型
    有限范围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,所以后面用5步算法,镜像下降等*
    挑战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
    如果奖励消耗超过了预算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合并正则项来最大化二阶目标(公平或负载均衡)

    论文

    问题描述和算法
    ft 是xt的奖励函数,非负非凸
    bt是资源消耗函数,非负非线性
    Xt是非凸完备的紧集,是当前步所有实时xt的集合
    S是所有可能需求的集合
    Tp pj资源大于零
    xt=0 和bt=0 就是空操作
    γ 向量,表示T个阶段的输入
    Ht-1 = {fs,bs,Xs,xs}
    xt是 (ft,bt,Xt|Ht-1) 是基于历史、奖励、消耗、Xt 经过算法A选出的动作
    γ-> 是多个阶段的输入
    多个阶段输入,决策之后,奖励和= ∑ft(xt)
    pT 和 Tp? 可能是坐着笔误,表示总容量。

    算法A不知道当前面对的是哪种输入

    随机IID:
    S是支撑集, △(S)是概率分布空间?,在△(S)中选一个最差的分布,为什么不直接在S中选?,如果是次线性那么是低regret
    对抗输入:
    是线性的,所以α渐进。
    2.1对偶问题
    公式(2)就是需求γt的 最优-机会成本-调整 奖励。 最大化(2)就是最优。γt是考虑了消耗和xt约束后奖励函数的凸共轭。
    用了新的x∈Xt 不用xt了。 bt(x) 为什么等于x,表示都用完了吗。x是求和以后的吗,公式γt中已经没有求和了。因为它是一个阶段一个阶段看了
    弱对偶找到了上界
    2.2算法
    每个资源都有一个对偶变量,根据输入f b x ,基于对偶解ut ,决策xt ,目标是γt最大。


    初始化
    for T 阶段循环
    输入ft bt Xt
    求出γt最大的决策:xt
    判断资源够不够
    更新资源
    获得次线性对偶函数gt=-bt(xt)+ρ
    用镜像下降更新对偶函数
    μt+1=gtμ+1/ηVh(u,ut):另函数最小选出对偶变量u
    (其中v是bregman散度)


    对偶函数 找决策xt用了,为什么还要次线性的gt呢
    参考函数是bregman散度用的?

    基本就是梯度下降,就两点区别

    1.在线,只用当前数据,这样好处是比离线用的数据少速度快,坏处是可能不准。
    2.加了约束,约束限制了 梯度优化 的方向,之后就正常更新对偶变量,也用了bergman散度

  • 相关阅读:
    英诺森 “供应链智能数据平台”荣获“科技进步奖”
    webrtc-stream编译报错记录
    TIM_CCxChannelCmd函数无法关闭互补通道输出
    小白还不懂电脑图片转PDF格式怎么弄吗?这些方法你都试过吗?
    Modbus调试软件使用教程
    C语言第三十六弹---文件操作(中)
    吴恩达深度学习笔记——结构化机器学习项目(Structuring Machine Learning Projects)
    香港写字楼等级如何划分?从3A到C级一文讲明白
    云计算OpenStack KVM迁移
    使用四则运算实现异或
  • 原文地址:https://blog.csdn.net/weixin_43889128/article/details/127135013