Good Prophets Know When the End Is Near
Top Cited Papers
- 1 June 2025
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 71 (6) , 4877-4894
Abstract
We consider a class of online decision-making problems with exchangeable actions, where in each period a controller is presented an input type drawn from some stochastic arrival process. The controller must choose an action, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems with knapsack, bin packing, and generalized assignment as canonical examples. In such settings, we study a natural model-predictive control algorithm. We introduce general conditions under which this algorithm obtains uniform additive loss (independent of the horizon) compared with an optimal solution with full knowledge of arrivals. Our condition builds on the recently introduced compensated coupling technique, providing a unified view of how uniform additive loss arises as a consequence of the geometry of the underlying decision-making problem. Our characterization allows us to derive uniform loss algorithms for several new settings, including the first such algorithm for online stochastic bin packing. It also lets us study the effect of other modeling assumptions, including choice of horizon, batched decisions, and limited computation. In particular, we show that our condition is fulfilled by the above-mentioned problems when the end of the time horizon is known sufficiently long before the end. In contrast, if at a late stage, there is still uncertainty about the end of the time horizon we show that such uniform loss guarantees are impossible to achieve. We use real and synthetic data to illustrate our findings. This paper was accepted by J. George Shanthikumar, data science. Funding: This work was supported by the Division of Mathematical Sciences [Grant 1839346]; the Division of Electrical, Communications and Cyber Systems [Grant 1847393]; and the Army Research Laboratory [Grant W911NF-17-1-0094]. The authors also gratefully acknowledge support from the NSF [Grants ECCS-1847393, CNS-195599, and DMS-1839346], AFOSR [Grant FA9550-23-1-0068], an ARL award [Grant W911NF-17-1-0094], and ARO MURI [Grant W911NF-19-1-0217]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.04307 .Keywords
This publication has 26 references indexed in Scilit:
- Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation ProblemsJournal of the ACM, 2019
- The Online Stochastic Generalized Assignment Problem2013
- On the Sum-of-Squares algorithm for bin packingJournal of the ACM, 2006
- Average-case analyses of first fit and random fit bin packingRandom Structures & Algorithms, 2000
- Optimal Stopping with Random Horizon with Application to the Full-Information Best-Choice Problem with Random FreezeJournal of the American Statistical Association, 1996
- Probability Inequalities for sums of Bounded Random Variables1994
- Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity ProblemsSIAM Journal on Control and Optimization, 1987
- The average-case analysis of some on-line algorithms for bin packingCombinatorica, 1986
- A moment inequality with an application to the central limit theoremScandinavian Actuarial Journal, 1956
- The accuracy of the Gaussian approximation to the sum of independent variatesTransactions of the American Mathematical Society, 1941