在在线广告竞价、云计算资源调度等场景中，决策者如何在毫秒级时间内做出兼顾效率与质量的资源分配决策？聚焦在线线性规划这一在线决策的核心问题，华理商学院教师薛晨予与上海交通大学葛冬冬教授、叶荫宇教授和美国斯坦福大学孙椿淋博士、博士生高文智合作，于近日在管理科学与工程顶级期刊Operations Research发表论文“Beyond Regret: Decoupling Learning and Decision Making in Online Linear Programming”，提出了一种通用的一阶算法框架，改进了现有的遗憾界。

       在线线性规划（Online Linear Programming, OLP）是描述资源约束下在线决策的标准框架，广泛应用于收益管理、在线广告及云计算等领域。在该问题中，决策者面对依次到达的客户请求须即时作出不可撤销的接受或拒绝决策，目标是在资源约束下最大化累积收益。经典算法大多基于离线线性规划，通过反复求解一系列线性规划问题来作出决策。虽能取得接近最优的 遗憾界，但计算成本较高，难以满足毫秒级决策的现实需求。因此，近年来一阶算法受到广泛关注，其仅依赖梯度信息进行决策，计算高效且易于扩展，但其已有遗憾上界仅为。一阶算法的遗憾界能否突破这一上界尚不明确。

       该研究对上述问题给出了肯定答复。文中指出，当对偶问题满足某种误差界条件时，一阶算法即可获得严格优于 的遗憾界保证。为此，该研究构建了一个“探索-利用”框架：先利用前期数据学习对偶最优解的高精度近似，再在该近似解附近进行局部决策，从而显著降低决策误差。然而研究发现，优秀的学习算法往往是糟糕的决策算法。为精确逼近最优解，学习算法在后期需采用极小的步长，但这种步长会使其面对噪声扰动时丧失自适应能力，从而在决策过程中累积大量遗憾。基于此，文章提出解耦学习与决策的设计思路：在探索阶段同时维护两条互不干扰的一阶算法路径，一条专注精准学习对偶最优解，另一条以适当步长承担决策任务；进入利用阶段后，将学习路径的输出作为决策路径的“热启动”，并通过精细化的步长选取实现收敛，从而取得理论上更优的遗憾界。

       在该统一框架下，该研究在连续支撑分布下建立了的遗憾界，所需假设严格弱于现有算法；在有限支撑分布下建立了 的遗憾界，改进了此前 的遗憾界界；对更一般的Hölder增长条件，给出了统一的遗憾界。数值实验显示，所提算法在遗憾界与离线线性规划方法相当的情况下，计算时间大为缩短。该研究提出的“学习-决策解耦”原则，为在线决策问题的算法设计提供了新视角，对构建可扩展、可部署的高速在线决策系统具有一定参考价值。

       薛晨予，华东理工大学商学院管理科学与工程系教师，主要研究方向为：收益管理，优化理论与算法

       论文信息：Wenzhi Gao, Dongdong Ge, Chunlin Sun, Chenyu Xue, Yinyu Ye. Beyond  Regret: Decoupling Learning and Decision Making in Online Linear Programming. Operations Research, In Press.

       论文链接：https://pubsonline.informs.org/doi/abs/10.1287/opre.2024.1575

撰稿：管理科学与工程系

审核：吴一帆