Certainty equivalent (CE) is a classical heuristic building on the intuition of replacing uncertainties with their average values, and making accept/reject decisions accordingly. Despite being the workhorse algorithm for online linear programming, the performance guarantee of CE measured by the additive regret against the prophet benchmark, remains largely unclear. Existing results typically rely on strong technical conditions called non-degeneracy conditions, which are not imposed on problem primitives, hard to intuit and very restrictive.

In this work, we show the (near) optimality of certainty equivalent (CE) for a fairly general class of instances, specified only by natural and mild assumptions on problem primitives, in particular, boundedness and smoothness on the (conditional) distribution of the reward. For centain class of instances, we prove that CE achieves an $O((\log T)^2)$ regret, which is near optimal (with an additional $\log T$ factor). En route characterizing the regret scaling, we borrow techniques such as the peeling device from the empirical processes and statistical theory, and establish concentration analysis of the solution to an optimization problem with large-size i.i.d. input, which may be of independent theoretical interest.

Wenjia Wang is an assistant professor in the Data Science and Analysis Thrust at the Information Hub of the Hong Kong University of Science and Technology (Guangzhou). He obtained his Ph.D. in the School of Industrial & Systems Engineering at Georgia Institute of Technology. Wenjia Wang's research interests include uncertainty quantification, computer experiments, machine learning, stochastic simulation, and nonparametric statistics.