Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds

References

• Agrawal S, Devanur NR (2014a) Bandits with concave rewards and convex knapsacks. Proc. 15th ACM Conf. on Econom. and Comput. (Palo Alto, CA, USA), 989–1006.Google Scholar
• Agrawal S, Devanur NR (2014b) Fast algorithms for online stochastic convex programming. Proc. 26th Annual ACM-SIAM Sympos. on Discrete Algorithms (Portland, Oregan, USA), 1405–1424.Google Scholar
• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Asadpour A, Wang X, Zhang J (2019) Online resource allocation with limited flexibility. Management Sci. 66(2):642–666.Link, Google Scholar
• Asmussen S, Glynn PW (2007) Stochastic Simulation: Algorithms and Analysis, vol. 57 (Springer Science & Business Media, New York).Crossref, Google Scholar
• Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, Google Scholar
• Bartlett PL, Bousquet O, Mendelson S, et al. (2005) Local rademacher complexities. Ann. Statist. 33(4):1497–1537.Crossref, Google Scholar
• Besbes O, Muharremoglu A (2013) On implications of demand censoring in the newsvendor problem. Management Sci. 59(6):1407–1424.Link, Google Scholar
• Besbes O, Zeevi A (2009) Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Oper. Res. 57(6):1407–1420.Link, Google Scholar
• Borodin A, El-Yaniv R (2005) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Bray RL (2019) Does the multisecretary problem always have bounded regret? Preprint, submitted December 16, https://arxiv.org/abs/1912.08917.Google Scholar
• Buchbinder N, Naor J (2009) Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2):270–286.Link, Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. Eur. Sympos. on Algorithms, 253–264.Google Scholar
• Buchbinder N, Naor JS (2009) The design of competitive online algorithms via a primal–dual approach. Foundations Trends Theoretical Comput. Sci. 3(2–3):93–263.Crossref, Google Scholar
• Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. (INFORMS) Management Sci. 66(7):2993–3009.Google Scholar
• Chen N, Gallego G (2018) A primal-dual learning algorithm for personalized dynamic pricing with an inventory constraint. Working paper, Hong Kong University of Science and Technology, Hong Kong.Google Scholar
• De Farias DP, Van Roy B (2004) On constraint sampling in the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3):462–478.Link, Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. on Electronic Commerce (Palo Alto, CA, USA), 71–78.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2011) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Proc. 12th ACM Conf. on Electronic Commerce (San Jose, CA, USA), 29–38.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):7.Crossref, Google Scholar
• Ferreira KJ, Simchi-Levi D, Wang H (2018) Online network revenue management using thompson sampling. Oper. Res. 66(6):1586–1602.Link, Google Scholar
• Gill RD, Levit BY (1995) Applications of the van trees inequality: A Bayesian Cramér-Rao bound. Bernoulli 1(1-2):59–79.Crossref, Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. on Discrete Algorithms (San Francisco, CA, USA), 982–991.Google Scholar
• Gupta A, Molinaro M (2014) How experts can solve LPS online. Proc. Eur. Sympos. on Algorithms, 517–529.Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3-4):157–325.Crossref, Google Scholar
• Huber PJ (1967) The behavior of maximum likelihood estimates under nonstandard conditions. Berkeley Symposium on Mathematical Statistics and Probability (Berkeley, CA, USA), 221–233.Google Scholar
• Jasin S (2015) Performance of an LP-based control for revenue management with unknown demand parameters. Oper. Res. 63(4):909–915.Link, 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
• Jasin S, Kumar S (2013) Analysis of deterministic LP-based booking limit and bid price controls for revenue management. Oper. Res. 61(6):1312–1320.Link, Google Scholar
• Keskin NB, Zeevi A (2014) Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. Oper. Res. 62(5):1142–1167.Link, Google Scholar
• Kesselheim T, Tönnis A, Radke K, Vöcking B (2014) Primal beats dual on online packing lps in the random-order model. Proc. 46th Annual ACM Sympos. on Theory of Computing (New York, NY, USA), 303–312.Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Sympos. on Discrete Algorithms (Vancouver, BC, Canada), 630–631.Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Knight K (1998) Limiting distributions for l1 regression estimators under general conditions. Ann. Statist. 26(2):755–770.Google Scholar
• Lakshminarayanan C, Bhatnagar S, Szepesvári C (2017) A linearly relaxed approximate linear program for Markov decision processes. IEEE Trans. Automated Control 63(4):1185–1191.Crossref, Google Scholar
• Lei YM, Jasin S, Sinha A (2014) Near-optimal bisection search for nonparametric dynamic pricing with inventory constraint. Working paper, Ross School of Business Paper (1252), University of Michigan, Ann Arbor.Google Scholar
• Mahdavi M, Jin R, Yang T (2012) Trading regret for efficiency: Online convex optimization with long term constraints. J. Machine Learning Res. 13(Sept):2503–2528.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2005) Adwords and generalized on-line matching. Proc. 46th Annual IEEE Sympos. on Foundations of Computer Science (Pittsburgh, PA, USA),264–273.Google Scholar
• Molinaro M, Ravi R (2013) The geometry of online packing linear programs. Math. Oper. Res. 39(1):46–59.Link, 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
• Shapiro A (1993) Asymptotic behavior of optimal solutions in stochastic programming. Math. Oper. Res. 18(4):829–845.Link, Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Talluri K, Van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Sci. 44(11 part 1):1577–1593.Link, Google Scholar
• Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management, vol. 68 (Springer Science & Business Media, New York).Google Scholar
• Vu K, Poirion PL, Liberti L (2018) Random projections for linear programming. Math. Oper. Res. 43(4):1051–1071.Link, Google Scholar
• Wang Z, Deng S, Ye Y (2014) Close the gaps: A learning-while-doing algorithm for single-product revenue management problems. Oper. Res. 62(2):318–331.Link, Google Scholar
• Wu H, Srikant R, Liu X, Jiang C (2015) Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Adv. Neural Inform. Processing Systems, vol. 28 (Montreal, Canada), 433–441.Google Scholar
• Yu H, Neely M, Wei X (2017) Online convex optimization with stochastic constraints. Adv. Neural Inform. Processing Systems, vol. 30 (Long Beach, CA, USA), 1428–1438.Google Scholar
• Yuan J, Lamperski A (2018) Online convex optimization for cumulative constraints. Adv. Neural Inform. Processing Systems, vol. 31 (Montreal, Canada) 6137–6146.Google Scholar