Beyond 𝒪(√T) Regret: Decoupling Learning and Decision Making in Online Linear Programming
成果类型：
Article
署名作者：
Gao, Wenzhi; Ge, Dongdong; Sun, Chunlin; Xue, Chenyu; Ye, Yinyu
署名单位：
Stanford University; Shanghai Jiao Tong University; Shanghai Institute for Mathematics & Interdisciplinary Sciences; East China University of Science and Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2024.1575
发表日期：
2026
关键词：
摘要：
Online linear programming plays an important role in both revenue management and resource allocation, and recent research has focused on developing efficient firstorder online learning algorithms. Despite the empirical success of first-order methods, they root ffiffiffi typically achieve a regret no better than O( T ), which is suboptimal compared with the O(log T) bound guaranteed by the state-of-the-art linear programming (LP)-based online root ffiffiffi algorithms. This paper establishes a general framework that improves on the O( T ) result when the LP dual problem exhibits certain error bound conditions. For the first time, we root ffiffiffi show that first-order learning algorithms achieve o( T ) regret in the continuous support setting and O(log T) regret in the finite support setting beyond the nondegeneracy assumption. Our results significantly improve the state-of-the-art regret results and provide new insights for sequential decision making.