Beyond O(T) Regret: Decoupling Learning and Decision Making in Online Linear Programming
Operations Research · 2026-07 · 74 (4) · 1932-1944
DOI: 10.1287/opre.2024.1575 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, 2026-07. Verfasst von Wenzhi Gao und 4 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben.
Abstract (Originalsprache)
Breaking the [Formula: see text] Barrier in Online Linear Programming How can fast first-order methods for online linear programming (OLP) match the performance of more computationally intensive LP-based approaches? In the paper “Beyond [Formula: see text] Regret: Decoupling Learning and Decision Making in Online Linear Programming,” the authors develop a new framework that improves the regret guarantees of scalable first-order algorithms for online linear programming. They show that when the dual problem satisfies a mild error bound condition, first-order methods can achieve [Formula: see text] regret, including [Formula: see text] in continuous support settings and [Formula: see text] in finite support settings. The key insight is to decouple learning and decision making. The algorithm first learns an approximate dual solution and then localizes decisions to a neighborhood around that solution using an adaptive procedure. This decoupling narrows the gap between efficient gradient-based methods and LP-based benchmarks, providing strong theoretical guarantees while maintaining scalability for applications such as revenue management, online advertising, and cloud computing.
Zitieren
APA
Gao, W., Ge, D., Sun, C., Xue, C., & Ye, Y. (2026). Beyond O(T) Regret: Decoupling Learning and Decision Making in Online Linear Programming. Operations Research, 74(4), 1932-1944. https://doi.org/10.1287/opre.2024.1575
Vancouver
Gao W, Ge D, Sun C, Xue C, Ye Y. Beyond O(T) Regret: Decoupling Learning and Decision Making in Online Linear Programming. Operations Research. 2026;74(4):1932-1944. doi:10.1287/opre.2024.1575
BibTeX
@article{Gao2026,
author = {Gao, Wenzhi and Ge, Dongdong and Sun, Chunlin and Xue, Chenyu and Ye, Yinyu},
title = {Beyond O(T) Regret: Decoupling Learning and Decision Making in Online Linear Programming},
journal = {Operations Research},
year = {2026},
volume = {74},
number = {4},
pages = {1932--1944},
doi = {10.1287/opre.2024.1575}
}
EUVIMED