The Bayesian Prophet: A Low-Regret Framework for Online Decision Making

References

• Agrawal S, Devanur NR (2014) Fast algorithms for online stochastic convex programming. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms, 1405–1424.Google Scholar
• Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multi-secretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Augustine J, Irani S, Swamy C (2004) Optimal power-down strategies. 45th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 530–539.Google Scholar
• Badanidiyuru A, Kleinberg R, Slivkins A (2013) Bandits with knapsacks. 2013 IEEE 54th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 207–216.Google Scholar
• Bertsekas DP (1995) Dynamic Programming and Optimal Control (Athena Scientific, Belmont, MA).Google Scholar
• Borrelli F (2003) Constrained Optimal Control of Linear and Hybrid Systems, vol. 290 (Springer, Berlin, Heidelberg).Google Scholar
• Brown DB, Smith JE (2013) Optimal sequential exploration: Bandits, clairvoyants, and wildcats. Oper. Res. 61(3):644–665.Link, Google Scholar
• Brown DB, Smith JE (2014) Information relaxations, duality, and convex stochastic dynamic programs. Oper. Res. 62(6):1394–1415.Link, Google Scholar
• Brubach B, Sankararaman KA, Srinivasan A, Xu P (2016) Online stochastic matching: New algorithms and bounds.Google Scholar
• Buchbinder N, Naor JS (2009a) The design of competitive online algorithms via a primal–dual approach. Foundations Trends Theoretical Comput. Sci. 3(2–3):93–263.Google Scholar
• Buchbinder N, Naor J (2009b) Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2):270–286.Link, Google Scholar
• Bumpensanti P, Wang H (2019) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Sci. Forthcoming.Google Scholar
• Chen N, Agarwal A, Wierman A, Barman S, Andrew LLH. (2015) Online convex optimization using predictions. ACM SIGMETRICS Performance Evaluation Rev. 43(1):191–204.Google Scholar
• Chen N, Comden J, Liu Z, Gandhi A, Wierman A (2016) Using predictions in online optimization: Looking forward with an eye on the past. Performance Evaluation Rev. 44(1):193–206.Google Scholar
• Chung K-M, Lam H, Liu Z, Mitzenmacher M (2012) Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified. Sympos. Theoretical Aspects Comput. Sci., vol. 14, 124–135.Google Scholar
• Ciocan DF, Farias V (2012) Model predictive control for dynamic resource allocation. Math. Oper. Res. 37(3):501–525.Link, Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Conf. Econom. Comput., (ACM), 169–186.Google Scholar
• Desai VV, Farias VF, Moallemi CC (2012) Pathwise optimization for optimal stopping problems. Management Sci. 58(12):2292–2308.Link, Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1).Crossref, Google Scholar
• Devroye L (1983) The equivalence of weak, strong and complete convergence in l1 for kernel density estimates. Ann. Statist. 11(3):896–904.Crossref, Google Scholar
• Dubhashi DP, Panconesi A (2009) Concentration of Measure for the Analysis of Randomized Algorithms (Cambridge University Press).Crossref, Google Scholar
• Düetting P, Feldman M, Kesselheim T, Lucier B (2017) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. Foundations of Computer Science (IEEE), 540–551.Google Scholar
• Gupta A, Molinaro M (2014) How experts can solve LPs online. Eur. Sympos. Algorithms (Springer), 517–529.Google Scholar
• Haeupler B, Mirrokni VS, Zadimoghaddam M (2011) Online Stochastic Weighted Matching: Improved Approximation Algorithms (Internet and Network Economics).Google Scholar
• Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of iid random variables. Ann. Probab. 10(2):336–345.Crossref, Google Scholar
• Huang L (2015) Receding learning-aided control in stochastic networks. Performance Evaluation 91(C):150–169.Crossref, Google Scholar
• Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Kesselheim T, Radke K, Tönnis A, Vöcking B (2018) Primal beats dual on online packing LPs in the random-order model. SIAM J. Comput. 47(5):1939–1964.Crossref, Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. ACM Sympos. Theory Comput. (ACM), 123–136.Crossref, Google Scholar
• Mangasarian OL, Shiau TH (1987) Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM J. Control Optim. 25(3):583–595.Crossref, Google Scholar
• Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
• Morari M, Garcia CE, Lee JH, Prett DM (1993) Model Predictive Control (Prentice Hall, Englewood Cliffs, NJ).Google Scholar
• Powell WB (2011) Approximate Dynamic Programming: Solving the Curses of Dimensionality, vol. 842 (John Wiley & Sons).Crossref, Google Scholar
• Reiman MI, Wang Q (2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Math. Oper. Res. 33(2):257–282.Link, Google Scholar
• Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management, vol. 68 (Springer Science & Business Media, Boston).Google Scholar
• Tsitsiklis JN, Van Roy B (2001) Regression methods for pricing complex American-style options. IEEE Trans. Neural Networks 12(4):694–703.Crossref, Google Scholar
• Van Hentenryck P, Bent R (2009) Online Stochastic Combinatorial Optimization (MIT Press, Boston).Google Scholar
• Vera A, Banerjee S (2019) The Bayesian prophet: A low-regret framework for online decision making. Performance Evaluation Rev. 47(1):81–82.Crossref, Google Scholar
• Wang X, Truong VA, Bank D (2018) Online advance admission scheduling for services with customer preferences.Google Scholar
• Wu H, Srikant R, Liu X, Jiang C (2015) Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Advances in Neural Information Processing Systems, 433–441.Google Scholar
• Zhang H, Shi C, Qin C, Hua C (2016) Stochastic regret minimization for revenue management problems with nonstationary demands. Naval Res. Logist. 63(6):433–448.Crossref, Google Scholar