Learning to Cover: Online Learning and Optimization with Irreversible Decisions

References

• Agarwal A, Balkanski E (2023) Learning-augmented dynamic submodular maximization. Preprint, submitted November 21, https://arxiv.org/abs/2311.13006.Google Scholar
• Agarwal A, Assadi S, Khanna S (2019) Stochastic submodular cover with limited adaptivity. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 323–342.Google Scholar
• Agarwal A, Dudík M, Kale S, Langford J, Schapire R (2012) Contextual bandit learning with predictable rewards. Lawrence ND, Girolami M, eds. Proc. 15th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 22 (PMLR, New York), 19–26.Google Scholar
• Agrawal S, Goyal N (2012) Analysis of Thompson sampling for the multi-armed bandit problem. Mannor S, Srebro N, Williamson RC, eds. Proc. 25th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 23 (PMLR, New York), 1–26.Google Scholar
• Almanza M, Chierichetti F, Lattanzi S, Panconesi A, Re G (2021) Online facility location with multiple advice. Adv. Neural Inform. Processing Systems 34:4661–4673.Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Auer P (2002) Using confidence bounds for exploitation-exploration trade-offs. J. Machine Learn. Res. 3(v):397–422.Google Scholar
• Banerjee S, Freund D (2025) Good prophets know when the end is near. Management Sci. 71(6):4877–4894.Google Scholar
• Bardenet R, Maillard OA (2015) Concentration inequalities for sampling without replacement. Bernoulli 21(3):1361–1385.Google Scholar
• Baxi S, Cummings K, Jacquillat A, Lo S, McDonald R, Mellou K, Menache I, Molinaro M (2025) Online rack placement in large-scale data centers: Online sampling optimization and deployment. Preprint, submitted January 22, https://arxiv.org/abs/2501.12725.Google Scholar
• Bertsimas D, Digalakis V Jr, Jacquillat A, Li ML, Previero A (2022) Where to locate COVID-19 mass vaccination facilities? Naval Res. Logist. 69(2):179–200.Crossref, Google Scholar
• Boucheron S, Bousquet O, Lugosi G (2005) Theory of classification: A survey of some recent advances. ESAIM: Probab. Statist. 9:323–375.Crossref, Google Scholar
• Brøgger-Mikkelsen M, Zibert JR, Andersen AD, Lassen U, Hædersdal M, Ali Z, Thomsen SF (2022) Changes in key recruitment performance metrics from 2008–2019 in industry-sponsored phase III clinical trials registered at ClinicalTrials.gov. PLoS One 17(7):e0271819.Crossref, Google Scholar
• Brown DB, Uru C (2024) Sequential search with acquisition uncertainty. Management Sci. 70(11):7712–7729.Link, Google Scholar
• Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Sci. 66(7):2993–3009.Link, Google Scholar
• Cao J, Qi W, Zhang Y (2026) Online facility location: Running stores on wheels with spatial demand learning. Manufacturing Service Oper. Management 28(3):935–955.Google Scholar
• Carlisle B, Kimmelman J, Ramsay T, MacKinnon N (2015) Unsuccessful trial accrual and human subjects protections: An empirical analysis of recently closed trials. Clinical Trials 12(1):77–83.Crossref, Google Scholar
• Challapally A, Pease C, Raskar R, Chari P (2019) The GenAI divide: State of AI in business. Technical report, MIT NANDA, Cambridge, MA.Google Scholar
• Che E, Namkoong H (2023) Adaptive experimentation at scale: A computational framework for flexible batches. Preprint, submitted March 21, https://arxiv.org/abs/2303.11582.Google Scholar
• Cheng C, Adulyasak Y, Rousseau LM (2021) Robust facility location under disruptions. INFORMS J. Optim. 3(3):298–314.Link, Google Scholar
• Combes R, Magureanu S, Proutiere A (2017) Minimal exploration in structured stochastic bandits. Guyon I, von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates, Red Hook, NY), 1763–1771.Google Scholar
• Cui T, Ouyang Y, Shen ZJM (2010) Reliable facility location design under the risk of disruptions. Oper. Res. 58(4-part-1):998–1011.Link, Google Scholar
• Daskin MS (1983) A maximum expected covering location model: Formulation, properties and heuristic solution. Transportation Sci. 17(1):48–70.Link, Google Scholar
• Farias VF, Madan R (2011) The irrevocable multiarmed bandit problem. Oper. Res. 59(2):383–399.Link, Google Scholar
• Feldman V, Vondrak J (2019) High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. Beygelzimer A, Hsu D, eds. Proc. 32nd Conf. Learn. Theory, Proceedings of Machine Learning Research (PMLR, New York), 1270–1279.Google Scholar
• Fotakis D (2008) On the competitive ratio for online facility location. Algorithmica 50(1):1–57.Crossref, Google Scholar
• Fotakis D (2011) Online and incremental algorithms for facility location. ACM SIGACT News 42(1):97–131.Crossref, Google Scholar
• Fotakis D, Gergatsouli E, Gouleakis T, Patris N (2021) Learning augmented online facility location. Preprint, submitted July 17, https://arxiv.org/abs/2107.08277.Google Scholar
• Ghuge R, Gupta A, Nagarajan V (2024) The power of adaptivity for stochastic submodular cover. Oper. Res. 72(3):1156–1176.Link, Google Scholar
• Goemans M, Vondrák J (2006) Stochastic covering and adaptivity. Correa JR, Hevia A, Kiwi M, eds. LATIN 2006 Theoret. Informatics, Lecture Notes in Computer Science (Springer, Berlin, Heidelberg), 532–543.Google Scholar
• Guo X, Kulkarni J, Li S, Xian J (2020) On the facility location problem in online and dynamic models. Byrka J, Meka R, eds. Approximation, Randomization, and Combinatorial Optim. Algorithms and Techniques, Leibniz International Proceedings in Informatics, vol. 176 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 1–23. Google Scholar
• Jacquillat A, Li ML, Ramé M, Wang K (2025) Branch-and-price for prescriptive contagion analytics. Oper. Res. 73(3):1558–1580.Link, Google Scholar
• Janisch M, Lehéricy T (2024) Berry–Esseen-type estimates for random variables with a sparse dependency graph. J. Theoret. Probability 37(4):3627–3653.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
• Jiang SHC, Liu E, Lyu Y, Tang ZG, Zhang Y (2021) Online facility location with predictions. Preprint, submitted October 17, https://arxiv.org/abs/2110.08840.Google Scholar
• Johnson O (2015) An evidence-based approach to conducting clinical trial feasibility assessments. Clinical Investigation (London) 5(5):491–499.Crossref, Google Scholar
• Laporte G, Louveaux FV, van Hamme L (1994) Exact solution to a location problem with stochastic demands. Transportation Sci. 28(2):95–103.Link, Google Scholar
• Lattanzi S, Mitrović S, Norouzi-Fard A, Tarnawski JM, Zadimoghaddam M (2020) Fully dynamic algorithm for constrained submodular optimization. Adv. Neural Inform. Processing Systems 33:12923–12933.Google Scholar
• Lim MK, Bassamboo A, Chopra S, Daskin MS (2013) Facility location decisions with random disruptions and imperfect estimation. Manufacturing Service Oper. Management 15(2):239–249.Link, Google Scholar
• Lu T, Pál D, Pál M (2010) Contextual multi-armed bandits. Teh YW, Titterington M, eds. Proc. 13th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 9 (PMLR, New York), 485–492.Google Scholar
• Lu M, Ran L, Shen ZJM (2015) Reliable facility location design under uncertain correlated disruptions. Manufacturing Service Oper. Management 17(4):445–455.Link, Google Scholar
• Magureanu S, Combes R, Proutiere A (2014) Lipschitz bandits: Regret lower bound and optimal algorithms. Balcan MF, Feldman V, Szepesvári C, eds. Proc. 27th Conf. Learn. Theory, Proceedings of Machine Learning Research (PMLR, New York), 975–999.Google Scholar
• Meyerson A (2001) Online facility location. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 426–431.Google Scholar
• Monemizadeh M (2020) Dynamic submodular maximization. Adv. Neural Inform. Processing Systems 33:9806–9817.Google Scholar
• Neu G, Olkhovskaia I, Papini M, Schwartz L (2022) Lifting the information ratio: An information-theoretic analysis of thompson sampling for contextual bandits. Adv. Neural Inform. Processing Systems 35:9486–9498.Google Scholar
• Neyman J (1934) On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection. J. Roy. Statist. Soc. 97(4):558–625.Crossref, Google Scholar
• Osband I, Van Roy B, Russo DJ, Wen Z (2019) Deep exploration via randomized value functions. J. Machine Learn. Res. 20(124):1–62.Google Scholar
• Rusmevichientong P, Tsitsiklis JN (2010) Linearly parameterized bandits. Math. Oper. Res. 35(2):395–411.Link, Google Scholar
• Russo D, Van Roy B (2018) Learning to optimize via information-directed sampling. Oper. Res. 66(1):230–252.Link, Google Scholar
• Ryzhov IO, Powell WB, Frazier PI (2012) The knowledge gradient algorithm for a general class of online learning problems. Oper. Res. 60(1):180–195.Link, Google Scholar
• Särndal CE, Swensson B, Wretman J (1992) Model Assisted Survey Sampling, Springer Series in Statistics (Springer, New York).Crossref, Google Scholar
• Sarykalin S, Serraino G, Uryasev S (2008) Value-at-risk vs. conditional value-at-risk in risk management and optimization. Hillier FS, Price CC, eds. Tutorials in Operations Research (INFORMS, Cantonsville, MD), 270–294.Google Scholar
• Serfling R (1974) Probability inequalities for the sum in sampling without replacement. Ann. Statist. 2(1):39–48.Crossref, Google Scholar
• Shen ZJM, Zhan RL, Zhang J (2011) The reliable facility location problem: Formulations, heuristics, and approximation algorithms. INFORMS J. Comput. 23(3):470–482.Link, Google Scholar
• Slivkins A (2011) Contextual bandits with similarity information. Kakade SM, von Luxburg U, eds. Proc. 24th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 19 (PMLR, New York), 679–702.Google Scholar
• Snyder LV, Daskin MS (2005) Reliability models for facility location: The expected failure cost case. Transportation Sci. 39(3):400–416.Link, Google Scholar
• Tsybakov AB (2004) Optimal aggregation of classifiers in statistical learning. Ann. Statist. 32(1):135–166.Crossref, Google Scholar
• University of California at Irvine (UCI) (2020) UC Irvine machine learning repository. Accessed October 12, 2025, http://archive.ics.uci.edu/ml.Google Scholar
• Van Der Vaart AW, Wellner JA (1996) Weak convergence. Weak Convergence and Empirical Processes: With Applications to Statistics (Springer, Berlin, Heidelberg), 16–28. Crossref, Google Scholar
• Van Parys B, Golrezaei N (2024) Optimal learning for structured bandits. Management Sci. 70(6):3951–3998.Link, Google Scholar
• Vapnik VN, Chervonenkis AY (2015) On the uniform convergence of relative frequencies of events to their probabilities. Vovk V, Papadopoulos H, Gammerman A, eds. Measures of Complexity: Festschrift for Alexey Chervonenkis (Springer, Berlin, Heidelberg), 11–30.Crossref, Google Scholar
• Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar