Contextual Search in the Presence of Adversarial Corruptions

References

• Agarwal A, Agarwal S, Patil P (2021) Stochastic dueling bandits with adversarial corruption. Feldman V, Ligett K, Sabato S, eds. Algorithmic Learn. Theory, March 16–19, Virtual Conference, Worldwide, vol. 132 (PMLR), 217–248.Google Scholar
• Amin K, Rostamizadeh A, Syed U (2013) Learning prices for repeated auctions with strategic buyers. Burges CJC, Bottou L, Ghahramani Z, Weinberger KQ, eds. Proc. 27th Annual Conf. on Neural Inform. Processing Systems, 1169–1177.Google Scholar
• Amin K, Rostamizadeh A, Syed U (2014) Repeated contextual auctions with strategic buyers. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Proc. Annual Conf. Adv. Neural Inform. Processing Systems, vol. 27, 622–630.Google Scholar
• Amir I, Attias I, Koren T, Livni R, Mansour Y (2020) Prediction with corrupted expert advice. Larochelle H, Ranzato M, Hadsell R, Balcan M-F, Lin H-T, eds. Proc. 32nd Adv. Neural Processing Systems. https://proceedings.neurips.cc/paper/2020/hash/a512294422de868f8474d22344636f16-Abstract.html.Google Scholar
• Aslam JA, Dhagat A (1991) Searching in the presence of linearly bounded errors. Koutsougeras C, Vitter JS, eds. Proc. 23rd Annual ACM Sympos. on Theory of Comput. (ACM, New York), 486–493.Google Scholar
• Auer P, Cesa-Bianchi N, Freund N, Schapire RE (2002) The nonstochastic multiarmed bandit problem. SIAM J. Comput. 32(1):48–77.Crossref, Google Scholar
• Ban G-Y, Keskin NB (2021) Personalized dynamic pricing with machine learning: High-dimensional features and heterogeneous elasticity. Management Sci. 67(9):5549–5568.Google Scholar
• Bastani H, Bayati M (2020) Online decision making with high-dimensional covariates. Oper. Res. 68(1):276–294.Link, Google Scholar
• Besbes O, Gur Y, Zeevi A (2015) Non-stationary stochastic optimization. Oper. Res. 63(5):1227–1244.Link, Google Scholar
• Blum A, Hopcroft J, Kannan R (2016) Foundations of Data Science (Cambridge University Press, Cambridge, UK).Google Scholar
• Bogunovic I, Krause A, Scarlett J (2020) Corruption-tolerant gaussian process bandit optimization. Chiappa S, Calandra R, eds. Proc. Internat. Conf. Artificial Intelligence Statist., vol. 108 (PMLR), 1071–1081.Google Scholar
• Bubeck S, Slivkins A (2012) The best of both worlds: Stochastic and adversarial bandits. Mannor S, Srebro N, Williamson RC, eds. Proc. 25th Annual Conf. on Learn. Theory, vol. 23 (JMLR), 42.1–42.23.Google Scholar
• Cesa-Bianchi N, Cesari T, Perchet V (2019) Dynamic pricing with finitely many unknown valuations. Garivier A, Kale S, eds. Proc. Algorithmic Learn. Theory, vol. 98 (PMLR), 247–273.Google Scholar
• Chen X, Wang Y (2022) Robust dynamic pricing with demand learning in the presence of outlier customers. Oper. Res., ePub ahead of print April 14, https://doi.org/10.1287/opre.2022.2280.Link, Google Scholar
• Chen X, Krishnamurthy A, Wang Y (2019) Robust dynamic assortment optimization in the presence of outlier customers. Preprint, submitted October 9, https://arxiv.org/abs/1910.04183.Google Scholar
• Chen X, Owen Z, Pixton C, Simchi-Levi D (2021) A statistical learning approach to personalization in revenue management. Management Sci. 68(3):1923–1937.Google Scholar
• Cheung WC, Simchi-Levi D, Zhu R (2021) Hedging the drift: Learning to optimize under non-stationarity. Management Sci. 68(3):1696–1713.Google Scholar
• Cohen MC, Lobel I, Leme RP (2020) Feature-based dynamic pricing. Management Sci. 66(11):4921–4943.Link, Google Scholar
• Dagan Y, Filmus Y, Kane D, Moran S (2021) The entropy of lies: Playing twenty questions with a liar. Lee JR, ed. Proc. 12th Innovations in Theoretical Comput. Sci. Conf., vol. 185 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany), 1:1–1:16.Google Scholar
• Drutsa A (2017) Horizon-independent optimal pricing in repeated auctions with truthful and strategic buyers. Barrett R, Cummings R, Agichtein E, Gabrilovich E, eds. Proc. 26th Internat. Conf. on World Wide Web, 33–42.Google Scholar
• Feldman M, Koren T, Livni R, Mansour Y, Zohar A (2016) Online pricing with strategic and patient buyers. Lee DD, Sugiyama M, von Luxburg U, Guyon I, Garnett R, eds. Proc. Annual Conf. Adv. Neural Inform. Processing Systems, vol. 29, 3864–3872.Google Scholar
• Goldenshluger A, Zeevi A (2013) A linear response bandit problem. Stochastic Systems 3(1):230–261.Link, Google Scholar
• Golrezaei N, Jaillet P, Jason CNL (2019a) Incentive-aware contextual pricing with non-parametric market noise. Preprint, submitted, November 8 https://arxiv.org/abs/1911.03508.Google Scholar
• Golrezaei N, Javanmard A, Mirrokni V (2019b) Dynamic incentive-aware learning: Robust pricing in contextual auctions. Adv. Neural Inform. Processing Systems. 69(1):297–314.Google Scholar
• Golrezaei N, Manshadi V, Schneider J, Sekar S (2021) Learning product rankings robust to fake users. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. on Econom. and Comput. (ACM, New York), 560–561.Google Scholar
• Gupta A, Koren T, Talwar K (2019) Better algorithms for stochastic bandits with adversarial corruptions. Beygelzimer A, Hsu D, eds. Proc. Conf. on Learn. Theory, vol. 99 (PMLR), 1562–1578.Google Scholar
• Gur Y, Zeevi AJ, Besbes O (2014) Stochastic multi-armed-banditproblem with non-stationary rewards. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Proc. 27th Annual Conf. Neural Inform. Processing Systems, 199–207.Google Scholar
• Herbster M, Warmuth MK (1998) Tracking the best expert. Machine Learn. 32(2):151–178.Crossref, Google Scholar
• Javanmard A, Nazerzadeh H (2019) Dynamic pricing in high-dimensions. J. Machine Learn. Res. 20:9:1–9:49.Google Scholar
• Kanoria Y, Nazerzadeh H (2021) Incentive-compatible learning of reserve prices for repeated auctions. Oper. Res. 69(2):509–524.Link, Google Scholar
• Karp RM, Kleinberg R (2007) Noisy binary search and its applications. Bansal N, Pruhs K, Stein C, eds. Proc. 18th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 881–890.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
• Keskin NB, Zeevi A (2017) Chasing demand: Learning and earning in a changing environment. Math. Oper. Res. 42(2):277–307.Link, Google Scholar
• Kleinberg R, Leighton T (2003) The value of knowing a demand curve: Bounds on regret for online posted-price auctions. Proc. 44th Annual IEEE Sympos. on Foundations of Comput. Sci. (IEEE, New York), 594–605.Google Scholar
• Krishnamurthy A, Lykouris T, Podimata C, Schapire R (2021) Contextual search in the presence of irrational agents. Khuller S, Williams VV, eds. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 910–918.Google Scholar
• Leme RP, Schneider J (2022) Contextual search via intrinsic volumes. SIAM J. Comput. 51(4):1096–1125.Google Scholar
• Li Y, Lou EY, Shan L (2019) Stochastic linear optimization with adversarial corruption. Preprint, submitted, https://arxiv.org/abs/1909.02109.Google Scholar
• Liu A, Leme RP, Schneider J (2021) Optimal contextual pricing and extensions. Marx D, ed. Proc. ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1059–1078.Google Scholar
• Liu J, Huang Z, Wang X (2018) Learning optimal reserve price against non-myopic bidders. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Proc. Annual Conf. Adv. Neural Inform. Processing Systems, vol. 31, 2042–2052.Google Scholar
• Lobel I, Leme RP, Vladu A (2018) Multidimensional binary search for contextual decision-making. Oper. Res. 66(5):1346–1361.Google Scholar
• Lykouris T, Mirrokni V, Leme RP (2018) Stochastic bandits robust to adversarial corruptions. Diakonikolas I, Kempe D, Henzinger M, eds. Proc. 50th Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 114–122.Google Scholar
• Lykouris T, Simchowitz M, Slivkins A, Sun W (2021) Corruption-robust exploration in episodic reinforcement learning. Belkin M, Kpotufe S, eds. Proc. Conf. Learn. Theory, vol. 134 (PMLR), 3242–3245.Google Scholar
• Mao J, Leme R, Schneider J (2018) Contextual pricing for lipschitz buyers. Bengio S, Wallach HM, Larochelle H, Grauman K, and Cesa-Bianchi N, Garnett R, eds. Proc. Annual Conf. Adv. Neural Inform. Processing Systems, vol. 31, 5648–5656.Google Scholar
• Mohri M, Munoz A (2014) Optimal regret minimization in posted-price auctions with strategic buyers. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Proc. Annual Conf. Adv. Neural Inform. Processing Systems, vol. 27, 1871–1879.Google Scholar
• Mohri M, Munoz A (2015) Revenue optimization against strategic buyers. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Proc. Annual Conf. Adv. Neural Inform. Processing Systems, vol. 28, 2530–2538.Google Scholar
• Nambiar M, Simchi-Levi D, Wang H (2019) Dynamic learning and pricing with model misspecification. Management Sci. 65(11):4980–5000.Link, Google Scholar
• Nowak R (2008) Generalized binary search. Proc. 46th Annual Allerton Conf. on Communication, Control, and Comput. (IEEE, New York), 568–574.Google Scholar
• Nowak R (2009) Noisy generalized binary search. Bengio Y, Schuurmans D, Lafferty JD, Williams CKI, Culotta A, eds. Proc. 23rd Annual Conf. Adv. Neural Inform. Processing Systems, vol. 22 (Curran Associates, Red Hook, NY), 1366–1374.Google Scholar
• Pelc A (1987) Coding with bounded error fraction. Ars Combin. 24:17–22.Google Scholar
• Pelc A (2002) Searching games with errors-fifty years of coping with liars. Theoretical Comput. Sci. 270(1-2):71–109.Crossref, Google Scholar
• Qiang S, Bayati M (2016) Dynamic pricing with demand covariates. Preprint, submitted April 25, https://arxiv.org/abs/1604.07463.Google Scholar
• Rademacher LA (2007) Approximating the centroid is hard. Proc. 23rd Annual Sympos. on Comput. Geometry. 302–305.Google Scholar
• Rhuggenaath J, de Oliveira da Costa PR, Zhang Y, Akcay A, Kaymak U (2020) Low-regret algorithms for strategic buyers with unknown valuations in repeated posted-price auctions. Joint European Conference on Machine Learning and Knowledge Discovery in Databases (Springer, Berlin), 416–436.Google Scholar
• Rivest RL, Meyer AR, Kleitman DJ, Winklmann K, Spencer J (1980) Coping with errors in binary search procedures. J. Comput. System Sci. 20(3):396–404.Crossref, Google Scholar
• Romano G, Tartaglia G, Marchesi A, Gatti N (2021) Online posted pricing with unknown time-discounted valuations. Proc. Conf. AAAI Artificial Intelligence 6:5682–5689.Crossref, Google Scholar
• Rosenblatt F (1958) The perceptron: A probabilistic model for information storage and organization in the brain. Psych. Rev. 65(6):386–408.Crossref, Google Scholar
• Shah V, Johari R, Johari R (2019) Semi-parametric dynamic contextual pricing. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, Garnett R, eds. Proc. 32nd Adv. Neural Inform. Processing Systems, 2360–2370.Google Scholar
• Slivkins A, Upfal E (2008) Adapting to a changing environment: The Brownian restless bandits. Rocco A. Servedio RA, Zhang T, eds. 21st COLT Conf. (Omni Press) 343–354.Google Scholar
• Spencer J (1992) Ulam’s searching game with a fixed number of lies. Theoretical Comput. Sci. 95(2):307–321.Crossref, Google Scholar
• Spencer J, Winkler P (1992) Three thresholds for a liar. Combinatorial Probability Comput. 1:81–93.Crossref, Google Scholar
• Ulam SM (1976) Adventures of a Mathematician (Charles Scribner’s Sons, New York).Crossref, Google Scholar
• Wei C-Y, Luo H (2021) Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. Belkin M, Kpotufe S, eds. Proc. Conf. Learn. Theory, vol. 134, (PMLR), 4300–4354.Google Scholar
• Zhiyanov A, Drutsa A (2020) Bisection-based pricing for repeated contextual auctions against strategic buyer. Hal Daumé III H, Aarti S, eds. Proc. Internat. Conf. Machine Learn., vol. 119 (PMLR), 11469–11480.Google Scholar
• Zimmert J, Seldin Y (2021) Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. J. Machine Learn. Res. 22:28:1–28:49.Google Scholar