Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

References

• Abernethy J, Hazan EE, Rakhlin A (2008) Competing in the dark: An efficient algorithm for bandit linear optimization. Proc. 21st Annual Conf. on Learn. Theory, 263–273.Google Scholar
• Abernethy J, Bartlett PL, Hazan E (2011) Blackwell approachability and no-regret learning are equivalent. Proc. 24th Annual Conf. on Learn. Theory, 27–46.Google Scholar
• Agrawal S, Avadhanula V, Goyal V, Zeevi A (2019) Mnl-bandit: A dynamic learning approach to assortment selection. Oper. Res. 67(5):1453–1485.Link, Google Scholar
• Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1-2):149–169.Crossref, Google Scholar
• Alaei S, Hartline J, Niazadeh R, Pountourakis E, Yuan Y (2019) Optimal auctions vs. anonymous pricing. Games Econom. Behav. 118:494–510.Crossref, Google Scholar
• Aouad A, Segev D (2021) Display optimization for vertically differentiated locations under multinomial logit preferences. Management Sci. 67(6):3519–3550.Link, Google Scholar
• Asadpour A, Niazadeh R, Saberi A, Shameli A (2022) Sequential submodular maximization and applications to ranking an assortment of products. Oper. Res., ePub ahead of print September 29, https://doi.org/10.1287/opre.2022.2370.Google Scholar
• Athey S, Ellison G (2011) Position auctions with consumer search. Quart. J. Econom. 126(3):1213–1270.Crossref, Google Scholar
• Audibert J-Y, Bubeck S, Lugosi G (2014) Regret in online combinatorial optimization. Math. Oper. Res. 39(1):31–45.Link, Google Scholar
• Beyhaghi H, Golrezaei N, Leme RP, Pál M, Sivan B (2021) Improved revenue bounds for posted-price and second-price mechanisms. Ope. Res. 69(6):1805–1822.Google Scholar
• Bian AA, Mirzasoleiman B, Buhmann J, Krause A (2017) Guaranteed non-convex optimization: Submodular maximization over continuous domains. Artificial Intelligence and Statistics (PMLR), 111–120.Google Scholar
• Blackwell D (1956) An analog of the minimax theorem for vector payoffs. Pacific J. Math. 6(1):1–8.Crossref, Google Scholar
• Bubeck S, Cesa-Bianchi N, Kakade SM (2012) Toward minimax policies for online linear optimization with bandit feedback. Proc. Conf. on Learn. Theory, 41–51.Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3-4):231–357.Google Scholar
• Buchbinder N, Feldman M (2018) Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3):32.Crossref, Google Scholar
• Cesa-Bianchi N, Lugosi G (2012) Combinatorial bandits. J. Comput. System Sci. 78(5):1404–1422.Crossref, Google Scholar
• Cesa-Bianchi N, Gentile C, Mansour Y (2014) Regret minimization for reserve prices in second-price auctions. IEEE Trans. Inform. Theory 61(1):549–564.Crossref, Google Scholar
• Chen L, Hassani H, Karbasi A (2018a) Online continuous submodular maximization. Proc. Internat. Conf. on Artificial Intelligence and Statist., 1896–1905.Google Scholar
• Chen L, Harshaw C, Hassani H, Karbasi A (2018b) Projection-free online optimization with stochastic gradient: From convexity to submodularity. Proc. Internat. Conf. on Machine Learn., 814–823.Google Scholar
• Chen L, Zhang M, Hassani H, Karbasi A (2020) Black box submodular maximization: Discrete and continuous settings. Proc. Internat. Conf. on Artificial Intelligence and Statist., 1058–1070.Google Scholar
• Chen W, Wang Y, Yuan Y (2013) Combinatorial multi-armed bandit: General framework and applications. Proc. Internat. Conf. on Machine Learn., 151–159.Google Scholar
• Combes R, Talebi MS, Proutiere A, Lelarge M (2015) Combinatorial bandits revisited. Advances in Neural Information Processing Systems, 2116–2124.Google Scholar
• Derakhshan M, Golrezaei N, Leme RP (2019) Lp-based approximation for personalized reserve prices. Proc. ACM Conf. on Econom. and Comput., 589–589.Google Scholar
• Derakhshan M, Golrezaei N, Manshadi V, Mirrokni V (2020) Product ranking on online platforms. Proc. 21st ACM Conf. on Econom. and Comput., 459–459.Google Scholar
• Désir A, Goyal V, Segev D, Ye C (2020) Capacity constrained assortment optimization under the markov chain based choice model. Management Sci. 66(2):698–721.Google Scholar
• Dobzinski S, Schapira M (2006) An improved approximation algorithm for combinatorial auctions with submodular bidders. Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithm, 1064–1073.Google Scholar
• Dudík M, Haghtalab N, Luo H, Schapire RE, Syrgkanis V, Vaughan JW (2017) Oracle-efficient online learning and auction design. Proc. IEEE 58th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 528–539.Google Scholar
• Even-Dar E, Kleinberg R, Mannor S, Mansour Y (2009) Online learning for global cost functions. Conf. Learn. Theory, COLT.Google Scholar
• Ferreira KJ, Parthasarathy S, Sekar S (2022) Learning to rank an assortment of products. Management Sci. 68(3):1828–1848.Google Scholar
• Garber D (2021) Efficient online linear optimization with approximation algorithms. Math. Oper. Res. 46(1):204–220.Link, Google Scholar
• Golrezaei N, Javanmard A, Mirrokni V (2021a) Dynamic incentive-aware learning: Robust pricing in contextual auctions. Oper. Res. 69(1):297–314.Link, Google Scholar
• Golrezaei N, Manshadi V, Schneider J, Sekar S (2021b) Learning product rankings robust to fake users. Proc. 22nd ACM Conf. on Econom. and Comput., 560–561.Google Scholar
• Hartline JD, Roughgarden T (2009) Simple vs. optimal mechanisms. Proc. 10th ACM Conf. on Electronic Commerce, 225–234.Google Scholar
• Hassani H, Soltanolkotabi M, Karbasi A (2017) Gradient methods for submodular maximization. Advances in Neural Information Processing Systems, 5841–5851.Google Scholar
• Hassani H, Karbasi A, Mokhtari A, Shen Z (2020) Stochastic conditional gradient++:(non) convex minimization and continuous submodular maximization. SIAM J. Optim. 30(4):3315–3344.Crossref, Google Scholar
• Hazan E, Karnin Z (2016) Volumetric spanners: an efficient exploration basis for learning. J. Machine Learn. Res. 17(1):4062–4095.Google Scholar
• Hazan E, Koren T (2016) The computational power of optimization in online learning. Proc. 48th Annual ACM Sympos. on Theory of Comput. (ACM, New York), 128–141.Google Scholar
• Hazan E, Hu W, Li Y, Li Z (2018) Online improper learning with an approximation oracle. Proc. 32nd Internat. Conf. on Neural Inform. Processing Systems, 5657–5665.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 A, Vempala S (2005) Efficient algorithms for online decision problems. J. Comput. System Sci. 71(3):291–307.Crossref, Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Proc. 9th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining, 137–146.Google Scholar
• Kök AG, Fisher ML, Vaidyanathan R (2008) Assortment planning: Review of literature and industry practice. Retail Supply Chain Management (Springer, Berlin), 99–153.Crossref, Google Scholar
• Kwon J, Perchet V (2017) Online learning and blackwell approachability with partial monitoring: optimal convergence rates. Artificial Intelligence and Statistics, 604–613.Google Scholar
• Lehrer E (2003) Approachability in infinite dimensional spaces. Internat. J. Game Theory 31(2):253–268.Crossref, Google Scholar
• Mannor S, Shimkin N (2006) Online learning with variable stage duration. Proc. Internat. Conf. on Comput. Learn. Theory (Springer, Berlin), 408–422.Google Scholar
• Mannor S, Perchet V, Stoltz G (2011) Robust approachability and regret minimization in games with partial monitoring. Proc. 24th Annual Conf. on Learn. Theory, 515–536.Google Scholar
• Mannor S, Perchet V, Stoltz G (2014) Set-valued approachability and online learning with partial monitoring. J. Machine Learn. Res. 15(1):3247–3295.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.Google Scholar
• Milman E (2006) Approachable sets of vector payoffs in stochastic games. Games Econom. Behav. 56(1):135–147.Crossref, Google Scholar
• Mitrovic M, Feldman M, Krause A, Karbasi A (2018) Submodularity on hypergraphs: From sets to sequences. Proc. Internat. Conf. on Artificial Intelligence and Statist., 1177–1184.Google Scholar
• Mokhtari A, Hassani H, Karbasi A (2020) Stochastic conditional gradient methods: From convex minimization to submodular maximization. J. Machine Learn. Res.Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—i. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Niazadeh R, Roughgarden T, Wang J (2018) Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization. Advances in Neural Information Processing Systems, 9594–9604.Google Scholar
• Roughgarden T, Wang JR (2018) An optimal learning algorithm for online unconstrained submodular maximization. Proc. Conf. on Learn. Theory, 1307–1325.Google Scholar
• Roughgarden T, Wang JR (2019) Minimizing regret with multiple reserves. ACM Trans. Econom. Comput. 7(3):1–18.Crossref, Google Scholar
• Shalev-Shwartz S (2012) Online learning and online convex optimization. Foundations Trends Machine Learn. 4(2):107–194.Google Scholar
• Spinat X (2002) A necessary and sufficient condition for approachability. Math. Oper. Res. 27(1):31–44.Link, Google Scholar
• Streeter M, Golovin D (2007) An online algorithm for maximizing submodular functions. Technical Report cmu-cs-07-171.Google Scholar
• Streeter M, Golovin D (2008) An online algorithm for maximizing submodular functions. Advances in Neural Information Processing Systems, 1577–1584.Google Scholar
• Thang NK, Srivastav A (2021) Online non-monotone dr-submodular maximization. Proc. Conf. AAAI Artificial Intelligence 35:9868–9876.Crossref, Google Scholar
• Tschiatschek S, Singla A, Krause A (2017) Selecting sequences of items via submodular maximization. Proc. 31st AAAI Conf. on Artificial Intelligence.Google Scholar
• Uchiya T, Nakamura A, Kudo M (2010) Algorithms for adversarial bandit problems with multiple plays. Proc. Internat. Conf. on Algorithmic Learn. Theory (Springer, Berlin), 375–389.Google Scholar
• Ursu RM (2016) The power of rankings: Quantifying the effect of rankings on online consumer search and purchase decisions.Google Scholar
• Vieille N (1992) Weak approachability. Math. Oper. Res. 17(4):781–791.Link, Google Scholar
• Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Proc. 40th Annual ACM Sympos. on Theory of Comput., 67–74.Google Scholar
• Weingartner MH (1967) Mathematical Programming and the Analysis of Capital Budgeting Problems (Markham Publishing Company).Google Scholar
• Zhang M, Chen L, Hassani H, Karbasi A (2019) Online continuous submodular maximization: From full-information to bandit feedback. Advances in Neural Information Processing Systems, 9206–9217.Google Scholar
• Zhang M, Shen Z, Mokhtari A, Hassani H, Karbasi A (2020) One sample stochastic Frank-Wolfe. Proc. Internat. Conf. on Artificial Intelligence and Statist., 4012–4023.Google Scholar
• Zimmert J, Luo H, Wei C-Y (2019) Beating stochastic and adversarial semi-bandits optimally and simultaneously. Proc. Internat. Conf. on Machine Learn., 7683–7692.Google Scholar