Wenjia Wang, Doctor, National University of Singapore

唐贻发 研究员

Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Resource Allocation

6月16日 (周二) 16:00-17:00，南楼733

The Certainty Equivalent (CE) heuristic is a widely-used algorithm for various online resource allocation problems in OR and OM. Despite its popularity, existing theoretical guarantees of CE are limited to settings satisfying restrictive fluid regularity conditions, particularly, the non-degeneracy conditions, under the widely held belief that the violation of such conditions leads to performance deterioration and necessitates algorithmic innovation beyond CE. In this work, we conduct a refined performance analysis of CE within the general framework of online linear programming. We show that CE achieves uniformly near-optimal regret (up to a polylogarithmic factor in $T$) under only mild assumptions on the underlying distribution, without relying on any fluid regularity conditions. Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances with continuous conditional reward distributions, highlighting the distinction of the problem's structure between discrete and non-discrete settings. Our explicit regret bound interpolates between the mild $(\log T)^2$ regime and the worst-case $\sqrt{T}$ regime with a parameter $\beta$ quantifying the minimal rate of probability accumulation of the conditional reward distributions, generalizing prior findings in the multisecretary setting.

Bio: Wenjia Wang is an Assistant Professor (Presidential Young Professorship) in the Department of Industrial Systems Engineering & Management at National University of Singapore. He obtained his BS in Yuanpei College at Peking University in 2013, and PhD in the School of Industrial & Systems Engineering at Georgia Institute of Technology in 2018. Wenjia Wang's research interests include uncertainty quantification, stochastic simulation, machine learning, computer experiments, and nonparametric statistics.