SPEAKER: 李国凯博士，香港中文大学（深圳）

TIME/DATE: 2025.7.3   13：30

CLASSROOM: A408

ABSTRACT:

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications, such as online auction, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former one typically guarantees better performance, even offering a constant regret, but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithm only requires first-order computations but induces a worse performance, lacking a constant regret bound. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm, that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard “degenerate” case) while solving LPs only O(log log T) times over the time horizon T. Moreover, when we are allowed to solve LPs only M times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly O(T^(1/2)^(M−1)) regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Furthermore, when the arrival probabilities are known at the beginning, our algorithm can guarantee a constant regret by solving LPs O(log log T) times, and a nearly O(T^(1/2)^M) regret by solving LPs only M times. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

GUEST BIO:

Dr. Guokai Li is an incoming Postdoctoral Fellow at McGill University and Queens University, where he will work with Professors Stefanus Jasin, Murray Lei and Alys Liang. He received his B.S. in Industrial Engineering from Xi’an Jiaotong University and his Ph.D. in Data Science from The Chinese University of Hong Kong, Shenzhen. Dr. Li’s research interests lie in online resource allocation, revenue management, and OM-marketing interface. His papers have been published in M&SOM, WINE conference (CCF-A), and NRL. He has received research awards such as the POMS-HK Student Paper Competition (Finalist) and the ORSC-DS Student Paper Competition (Winner). He also serves as ad hoc reviewers for several leading journals, including OR, M&SOM and POM.