Semibandit Learning for Monotone Stochastic Optimization

References

• Adamczyk M, Sviridenko M, Ward J (2016) Submodular stochastic probing on matroids. Math. Oper. Res. 41(3):1022–1038.Link, 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
• Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Auer P, Cesa-Bianchi N, Fischer P (2002) Finite time analysis of the multiarmed bandit problem. Machine Learn. 47(2–3):235–256.Crossref, Google Scholar
• Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1358–1377.Google Scholar
• Azar MG, Osband I, Munos R (2017) Minimax regret bounds for reinforcement learning. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (PMLR), 263–272.Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Bernstein S (1924) On a modification of Chebyshev’s inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine Sect. Math. 1(4):38–49.Google Scholar
• Bhalgat A, Goel A, Khanna S (2011) Improved approximation results for stochastic knapsack problems. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms, 1647–1665.Google Scholar
• Boodaghians S, Fusco F, Lazos P, Leonardi S (2023) Pandora’s box problem with order constraints. Math. Oper. Res. 48(1):498–519.Link, Google Scholar
• Butterworth R (1972) Some reliability fault-testing models. Oper. Res. 20(2):335–343.Link, Google Scholar
• Caramanis C, Dütting P, Faw M, Fusco F, Lazos P, Leonardi S, Papadigenopoulos O, Pountourakis E, Reiffenhäuser R (2022) Single-sample prophet inequalities via greedy-ordered selection. ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1298–1325.Google Scholar
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press).Crossref, Google Scholar
• Chakraborty T, Even-Dar E, Guha S, Mansour Y, Muthukrishnan S (2010) Approximation schemes for sequential posted pricing in multi-unit auctions. Saberi A, ed. Internet Network Econom. Sixth Internat. Workshop, Lecture Notes in Computer Science, vol. 6484 (Springer), 158–169.Crossref, Google Scholar
• Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput. (ACM), 311–320.Google Scholar
• Chen W, Wang Y, Yuan Y, Wang Q (2016a) Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. J. Machine Learn. Res. 17:50:1–50:33.Google Scholar
• Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Thirty-Sixth Internat. Colloquium Automata Languages Programming (Springer), 266–278.Google Scholar
• Chen W, Hu W, Li F, Li J, Liu Y, Lu P (2016b) Combinatorial multi-armed bandit with general reward functions. Adv. Neural Inform. Processing Systems, 1651–1659.Google Scholar
• Cole R, Roughgarden T (2014) The sample complexity of revenue maximization. Proc. 46th Annual ACM Sympos. Theory Comput., 243–252.Google Scholar
• Correa J, Dütting P, Fischer F, Schewior K (2019) Prophet inequalities for IID random variables from an unknown distribution. Proc. 2019 ACM Conf. Econom. Comput., 3–17.Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Deshpande A, Hellerstein L, Kletenik D (2016) Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack. ACM Trans. Algorithms 12(3):1–28.Crossref, Google Scholar
• Ezra T, Feldman M, Gravin N, Tang ZG (2022) Prophet matching with general arrivals. Math. Oper. Res. 47(2):878–898.Link, Google Scholar
• Feldman M, Svensson O, Zenklusen R (2021) Online contention resolution schemes with applications to Bayesian selection problems. SIAM J. Comput. 50(2):255–300.Crossref, Google Scholar
• Fu H, Lu P, Tang ZG, Wu H, Wu J, Zhang Q (2024) Sample-based matroid prophet inequalities. Proc. 25th ACM Conf. Econom. Computat. (ACM), 781.Google Scholar
• Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, International Series in Operations Research & Management Science (Springer).Crossref, Google Scholar
• Gatmiry K, Kesselheim T, Singla S, Wang Y (2024) Bandit algorithms for prophet inequality and Pandora’s box. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM).Google Scholar
• Ghosal S, Van der Vaart A (2017) Fundamentals of Nonparametric Bayesian Inference, vol. 44 (Cambridge University Press).Crossref, Google Scholar
• Goemans M, Vondrák J (2006) Stochastic covering and adaptivity. Latin Amer. Sympos. Theoret. Informatics (Springer), 532–543.Google Scholar
• Gordon R (1994) The Integrals of Lebesgue, Denjoy, Perron, and Henstock, Graduate Studies in Mathematics (American Mathematical Society).Crossref, Google Scholar
• Guo C, Huang Z, Zhang X (2019) Settling the sample complexity of single-parameter revenue maximization. Charikar M, Cohen E, eds. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (ACM), 662–673.Google Scholar
• Guo C, Huang Z, Tang ZG, Zhang X (2021) Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and Pandora’s problem. Conf. Learn. Theory (PMLR), 2248–2288.Google Scholar
• Gupta A, Nagarajan V (2013) A stochastic probing problem with applications. Integer Programming Combin. Optim. 16th Internat. Conf., 205–216.Crossref, Google Scholar
• Gupta A, Nagarajan V, Singla S (2017) Adaptivity gaps for stochastic probing: Submodular and XOS functions. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1688–1702.Google Scholar
• Gupta A, Krishnaswamy R, Molinaro M, Ravi R (2011) Approximation algorithms for correlated knapsacks and non-martingale bandits. Ostrovsky R, ed. IEEE 52nd Annual Sympos. Foundations Comput. Sci., 827–836.Google Scholar
• Gupta A, Krishnaswamy R, Nagarajan V, Ravi R (2015) Running errands in time: Approximation algorithms for stochastic orienteering. Math. Oper. Res. 40(1):56–79.Link, Google Scholar
• Hazan E (2022) Introduction to Online Convex Optimization (MIT Press).Google Scholar
• Heil C (2019) Introduction to Real Analysis, Graduate Texts in Mathematics (Springer International Publishing).Crossref, Google Scholar
• Huh WT, Rusmevichientong P (2006) Adaptive capacity allocation with censored demand data: Application of concave umbrella functions. Technical report, Cornell University, School of Operations Research and Industrial Engineering, Ithaca, NY.Google Scholar
• Im S, Nagarajan V, Zwaan RVD (2016) Minimum latency submodular cover. ACM Trans. Algorithms 13(1):1–28.Crossref, Google Scholar
• Jaksch T, Ortner R, Auer P (2010) Near-optimal regret bounds for reinforcement learning. J. Machine Learn. Res. 11:1563–1600.Google Scholar
• Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1221–1246.Google Scholar
• Jin C, Allen-Zhu Z, Bubeck S, Jordan MI (2018) Is q-learning provably efficient? Adv. Neural Inform. Processing Systems, 4868–4878.Google Scholar
• Jin C, Jin T, Luo H, Sra S, Yu T (2020) Learning adversarial Markov decision processes with bandit feedback and unknown transition. Proc. 37th Internat. Conf. Machine Learn., vol. 119 (PMLR), 4860–4869.Google Scholar
• Kakade SM, Kalai AT, Ligett K (2009) Playing games with approximation algorithms. SIAM J. Comput. 39(3):1088–1106.Crossref, Google Scholar
• Kalai AT, Vempala SS (2005) Efficient algorithms for online decision problems. J. Comput. Systems Sci. 71(3):291–307.Crossref, Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. Theory Comput., 123–136.Google Scholar
• Kleinberg R, Weinberg SM (2019) Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econom. Behav. 113:97–115.Crossref, Google Scholar
• Kleinberg RD, Waggoner B, Weyl EG (2016) Descending price optimally coordinates search. ACM Conf. Econom. Comput. (ACM), 23–24.Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83:745–747.Crossref, Google Scholar
• Kveton B, Wen Z, Ashkan A, Szepesvári C (2015) Tight regret bounds for stochastic combinatorial semi-bandits. Proc. 18th Internat. Conf. Artificial Intelligence Statist.Google Scholar
• Kveton B, Wen Z, Ashkan A, Eydgahi H, Eriksson B (2014) Matroid bandits: Fast combinatorial optimization with learning. Proc. 30th Conf. Uncertainty Artificial Intelligence, 420–429.Google Scholar
• Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press).Crossref, Google Scholar
• Liggett TM, Liggett TM (1985) Interacting Particle Systems, vol. 2 (Springer).Google Scholar
• Liu J, Chen Z, Wang K, Luo H, Ratliff LJ (2025) Improved regret and contextual linear extension for Pandora’s box and prophet inequality. Thirty-Ninth Annual Conf. Neural Inform. Processing Systems.Google Scholar
• Ma W (2018) Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms. Math. Oper. Res. 43(3):789–812.Link, Google Scholar
• Massart P (1990) The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Ann. Probab. 18(3):1269–1283.Crossref, Google Scholar
• Myerson R (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• Niazadeh R, Golrezaei N, Wang JR, Susan F, Badanidiyuru A (2021) Online learning via offline greedy algorithms: Applications in market design and optimization. Proc. 22nd ACM Conf. Econom. Comput., 737–738.Google Scholar
• Nie G, Nadew YY, Zhu Y, Aggarwal V, Quinn CJ (2023) A framework for adapting offline algorithms to solve combinatorial multi-armed bandit problems with bandit feedback. Internat. Conf. Machine Learn., vol. 202 (PMLR), 26166–26198.Google Scholar
• Osband I, Roy BV (2016) On lower bounds for regret in reinforcement learning. CoRR abs/1608.02732.Google Scholar
• Roughgarden T, Schrijvers O (2016) Ironing in the dark. Proc. 2016 ACM Conf. Econom. Comput., 1–18.Google Scholar
• Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1671–1687.Google Scholar
• Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Eleventh Innovations Theoret. Comput. Sci. Conf., LIPIcs, vol. 151, 60:1–60:10.Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• Singla S (2018) The price of information in combinatorial optimization. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 2523–2532.Google Scholar
• Singla S, Wang Y (2024) Bandit sequential posted pricing via half-concavity. Bergemann D, Kleinberg R, Sabán D, eds. Proc. 25th ACM Conf. Econom. Comput. (ACM), 922–939.Google Scholar
• Strassen V (1965) The existence of probability measures with given marginals. Ann. Math. Statist. 36(2):423–439.Crossref, Google Scholar
• Tajdini A, Jain L, Jamieson K (2024) Nearly minimax optimal submodular maximization with bandit feedback. Adv. Neural Inform. Processing Systems, vol. 38.Google Scholar
• Van Ryzin G, McGill J (2000) Revenue management without forecasting or optimization: An adaptive algorithm for determining airline seat protection levels. Management Sci. 46(6):760–775.Link, Google Scholar
• Weitzman ML (1979) Optimal search for the best alternative. Econometrica 47(3):641–654.Crossref, Google Scholar
• Yan Q (2011) Mechanism design via correlation gap. SODA, 710–719.Google Scholar
• Zhuo Z, Gupta A, Nagarajan V (2026) Learning Markov decision processes under fully bandit feedback. Preprint, submitted February 2, https://arxiv.org/abs/2602.02260.Google Scholar