在线分配问题的双镜面下降算法
本文研究具有随机约束的在线凸优化问题,提出了一种新的原始 - 对偶镜像下降算法,其可以在不需要 Slater 条件的情况下达到与先前的方法相似的性能并允许等式约束。
Aug, 2019
本文研究了一个多期的长期资源分配问题,其中每个周期需要一个多阶段的决策过程。我们将此问题定义为具有未知非平稳转换和随机非平稳奖励和资源消耗函数的离散时段有限马尔可夫决策过程的在线资源分配问题。我们提出了一种基于占用度量的等效在线线性规划重构方法,并开发了一种在线镜像下降算法。我们证明,在随机奖励和资源消耗函数下,在线镜像下降算法的期望遗憾值受到了限制。
May, 2023
本文提出了基于近似镜像下降的一类在线分布式优化算法,以 Bregman 距离为测量函数,包括欧几里得距离作为特例,考虑两种标准信息反馈模型,并通过在线分布式正则化线性回归问题的仿真结果验证了算法的性能。
Apr, 2020
该论文探讨了基于在线凸优化的强化学习的新框架,特别是镜像下降及相关算法,提出了一种新的类似于梯度下降的迭代方法。其中,基于不同 Bregman 散度的抛物线梯度强化学习法比常规 TD 学习更为普适。还提出了一种新型的稀疏镜像下降强化学习方法,相比之前基于二阶矩阵方法的方法,在寻找一个 l1 正则化 Bellman 方程的稀疏不动点时具有显著的计算优势。
Oct, 2012
本文研究了一种有多个容量有限库存的竞争性在线优化问题,提出了一种分治方法,能够有效应对在不同时间段内收益函数和分配约束的变化,并取得了优秀的最优解竞争比。
Feb, 2022
本文研究了一个在线资源预订问题,通过一个由两个计算节点组成的通信网络,在有限时间内最小化整体预订成本,并且保持累计违规与运输成本在一定预算限制下的在线重复博弈,提出了一个在线鞍点算法来解决该问题。
May, 2023
本文提出了一个实际高效的算法,具有最优理论遗憾度,可解决具有未知非参数需求的经典网络收益管理问题。通过引入一种称为需求平衡的技术贡献,该算法在每个时间段内将原始解与另一个价格配对,以抵消资源库存约束上互补松弛度的违反,从而进一步提高原先结果的表现。数值实验与多种基准算法的比较进一步说明了我们算法的有效性。
Apr, 2024
本文提出一种针对多个资源分配问题的算法体系,将在线请求建模为每次从未知的概率分布中独立抽取,给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法,并且探究了如何在任意情况下应对敌对分布。同时,文中提出了解决大型 LPs 混合装填覆盖问题的快速算法,并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。
Mar, 2019