Online Resource Allocation with Convex-Set Machine-Learned Advice
Negin Golrezaei, Patrick Jaillet, Zijie Zhou
Operations Research · Thu
Abstract
Decision makers often have access to a machine-learned (ML) prediction about demand, referred to as advice, which can potentially be utilized in online decision-making processes for resource allocation. However, exploiting such advice poses challenges due to its potential inaccuracy. To address this issue, we propose a framework that enhances online resource allocation decisions with potentially unreliable ML advice. We assume here that this advice is represented by a general convex uncertainty set for the demand vector. We introduce a parameterized class of Pareto optimal online resource allocation algorithms that strike a balance between consistent and robust ratios. The consistent ratio measures the algorithm’s performance (compared with the optimal hindsight solution) when the ML advice is accurate, whereas the robust ratio captures performance under an adversarial demand process when the advice is inaccurate. Specifically, in a C-Pareto optimal setting, we maximize the robust ratio while ensuring that the consistent ratio is at least C. Our proposed C-Pareto optimal algorithm is an adaptive protection level algorithm, which extends the classical fixed protection level algorithm introduced in Littlewood (2005) and Ball and Queyranne (2009). Solving a complex nonconvex continuous optimization problem characterizes the adaptive protection level algorithm. To complement our algorithms, we present a simple method for computing the maximum achievable consistent ratio, which serves as an estimate for the maximum value of the ML advice. Additionally, we present numerical studies to evaluate the performance of our algorithm in comparison with benchmark algorithms. The results demonstrate that, by adjusting the parameter C, our algorithms effectively strike a balance between worst-case and average performance. In fact, they surpass the benchmark algorithms, including those that solely depend on a single point estimate advice, rather than leveraging the advantages of an uncertainty set advice. Funding: N. Golrezaei acknowledges support from the Massachusetts Institute of Technology [Research Support Award and Junior Faculty Research Assistance Grant]. P. Jaillet acknowledges support from the Office of Naval Research [Grant N00014-18-1-2122] and the Air Force Office of Scientific Research [Grant FA9550-23-1-0190]. Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2023.0338 .
Keywords
Market Analytics and Revenue Management, online resource allocation, machine-learned advice, convex uncertainty set, Pareto optimal algorithms, robust ratio, consistent ratio
Enable JavaScript for citation tools and additional paper interactions.