Doubly Adaptive Cascading Bandits with User Abandonment

References

• Abbasi-Yadkori Y, Pál D, Szepesvári C (2011a) Improved algorithms for linear stochastic bandits. Adv. Neural Inform. Processing Systems, vol. 24 (Curran Associates Inc., Red Hook, NY), 2312–2320.Google Scholar
• Abbasi-Yadkori Y, Pál D, Szepesvári C (2011b) Online least squares estimation with self-normalized processes: An application to bandit problems. Preprint, submitted February 14, https://arxiv.org/abs/1102.2670.Google Scholar
• Abebe R, Adamic LA, Kleinberg J (2018) Mitigating overexposure in viral marketing. McIlraith SA, Weinberger KQ, eds. Proc. Thirty-Second AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 241–248.Google Scholar
• Agarwal D, Chen BC, Elango P, Motgi N, Park ST, Ramakrishnan R, Roy S, Zachariah J (2008) Online models for content optimization. Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Adv. Neural Inform. Processing Systems, vol. 21 (Curran Associates Inc., Red Hook, NY), 17–24.Google Scholar
• Agrawal P, Tulabandhula T, Avadhanula V (2023) A tractable online learning algorithm for the multinomial logit contextual bandit. Eur. J. Oper. Res. 310(2):737–750.Crossref, Google Scholar
• Agrawal S, Avadhanula V, Goyal V, Zeevi A (2017) Thompson sampling for the MNL-bandit. Kale S, Shamir O, eds. Proc. 2017 Conf. Learn. Theory, vol. 65 (PMLR, New York), 76–78.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
• Aouad A, Levi R, Segev D (2018) Greedy-like algorithms for dynamic assortment planning under multinomial logit preferences. Oper. Res. 66(5):1321–1345.Link, Google Scholar
• Auer P (2002) Using confidence bounds for exploitation-exploration trade-offs. J. Machine Learn. Res. 3(v):397–422.Google Scholar
• Ban GY, Keskin NB (2021) Personalized dynamic pricing with machine learning: High-dimensional features and heterogeneous elasticity. Management Sci. 67(9):5549–5568.Link, Google Scholar
• Barlow RE, Marshall AW, Proschan F (1963) Properties of probability distributions with monotone hazard rate. Ann. Math. Statist. 34(2):375–389.Crossref, Google Scholar
• Bastani H, Harsha P, Perakis G, Singhvi D (2022) Learning personalized product recommendations with customer disengagement. Manufacturing Service Oper. Management 24(4):2010–2028.Link, Google Scholar
• Byers JW, Mitzenmacher M, Zervas G (2012) The groupon effect on yelp ratings: A root cause analysis. Faltings B, Leyton-Brown K, Ipeirotis P, eds. Proc. 13th ACM Conf. Electronic Commerce (EC ’12) (Association for Computing Machinery, New York), 248–265.Google Scholar
• Cao J, Sun W (2019) Dynamic learning of sequential choice bandit problem under marketing fatigue. Van Hentenryck P, Zhou Z-H, eds. Proc. Thirty-Third AAAI Conf. Artificial Intelligence, vol. 33 (AAAI Press, Palo Alto, CA), 3264–3271.Google Scholar
• Cao J, Sun W (2024) Tiered assortment: Optimization and online learning. Management Sci. 70(8):5481–5501.Link, Google Scholar
• Cao J, Sun W, Shen ZJM, Ettl M (2020) Fatigue-aware bandits for dependent click models. Conitzer V, Sha F, eds. Proc. Thirty-Fourth AAAI Conf. Artificial Intelligence, vol. 34 (AAAI Press, Palo Alto, CA), 3341–3348.Google Scholar
• Caro F, Gallien J (2007) Dynamic assortment with demand learning for seasonal consumer goods. Managment. Sci. 53(2):276–292.Link, Google Scholar
• Cesa-Bianchi N, Lugosi G (2012) Combinatorial bandits. J. Comput. Systems Sci. 78(5):1404–1422.Crossref, Google Scholar
• Chan J, Pacchiano A, Tripuraneni N, Song YS, Bartlett P, Jordan MI (2021) Parallelizing contextual linear bandits. Preprint, submitted May 21, https://arxiv.org/abs/2105.10590.Google Scholar
• Chen N, Li A, Yang S (2021) Revenue maximization and learning in products ranking. Biró P, Chawla S, Echenique F, eds. EC ’21: Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 316–317.Google Scholar
• Chen W, Wang Y, Yuan Y (2013) Combinatorial multi-armed bandit: General framework and applications. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 28, no. 1 (PMLR, New York), 151–159.Google Scholar
• Chen X, Wang Y, Zhou Y (2020) Dynamic assortment optimization with changing contextual information. J. Machine Learn. Res. 21(1):8918–8961.Google Scholar
• Chen N, Cire AA, Hu M, Lagzi S (2023) Model-free assortment pricing with transaction data. Management Sci. 69(10):5830–5847.Link, Google Scholar
• Cheng J, Sun A, Zeng D (2010) Information overload and viral marketing: Countermeasures and strategies. Chai S-K, Salerno JJ, Mabry PL, eds. Adv. Social Comput. Third Internat. Conf. Social Comput. Behav. Modeling, Prediction (SBP 2010), Lecture Notes in Computer Science, vol. 6007 (Springer-Verlag, Berlin, Heidelberg), 108–117.Google Scholar
• Cheung WC, Simchi-Levi D (2017) Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models. Preprint, submitted November 21, http://dx.doi.org/10.2139/ssrn.3075658.Google Scholar
• Cheung WC, Tan V, Zhong Z (2019) A thompson sampling algorithm for cascading bandits. Chaudhuri K, Sugiyama M, eds. Proc. Twenty-Second Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 89 (PMLR, New York), 438–447.Google Scholar
• Chu W, Li L, Reyzin L, Schapire R (2011) Contextual bandits with linear payoff functions. Gordon GJ, Dunson DB, Dudík M, eds. Proc. Fourteenth Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 15 (PMLR, New York), 208–214.Google Scholar
• Chuklin A, Markov I, Md R (2015) Click models for web search. Synthesis Lectures Inform. Concepts, Retrieval, Services 7(3):1–115.Crossref, Google Scholar
• Combes R, Magureanu S, Proutiere A, Laroche C (2015a) Learning to rank: Regret lower bounds and efficient algorithms. ACM SIGMETRICS Performance Evaluation Rev. 43(1):231–244.Crossref, Google Scholar
• Combes R, Talebi MS, Proutiere A, Lelarge M (2015b) Combinatorial bandits revisited. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 28 (Curran Associates Inc., Red Hook, NY), 2116–2124.Google Scholar
• Craswell N, Zoeter O, Taylor M, Ramsey B (2008) An experimental comparison of click position-bias models. Najork M, Broder AZ, Chakrabarti S, eds. WSDM ’08: Proc. 2008 Internat. Conf. Web Search Data Mining (Association for Computing Machinery, New York), 87–94.Google Scholar
• Dani V, Hayes TP, Kakade SM (2008) Stochastic linear optimization under bandit feedback. Servedio RA, Zhang T, eds. Proc. 21st Annual Conf. Learn. Theory (COLT 2008) (Omnipress, Madison, WI), 355–366.Google Scholar
• de la Pena VH, Klass MJ, Lai TL (2004) Self-normalized processes: Exponential inequalities, moment bounds and iterated logarithm laws. Ann. Probability 32(3A):1902–1933.Crossref, Google Scholar
• de la Peña VH, Lai TL, Shao QM (2008) Self-Normalized Processes: Limit Theory and Statistical Applications (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• Derakhshan M, Golrezaei N, Manshadi V, Mirrokni V (2022) Product ranking on online platforms. Management Sci. 68(6):4024–4041.Link, Google Scholar
• Faury L, Abeille M, Calauzènes C, Fercoq O (2020) Improved optimistic algorithms for logistic bandits. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 119 (PMLR, New York), 3052–3060.Google Scholar
• Ferreira KJ, Parthasarathy S, Sekar S (2022) Learning to rank an assortment of products. Management Sci. 68(3):1828–1848.Link, Google Scholar
• Filippi S, Cappe O, Garivier A, Szepesvári C (2010) Parametric bandits: The generalized linear case. Adv. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 586–594.Google Scholar
• Gallo A (2014) The value of keeping the right customers. Harvard Bus. Rev. 29, https://hbr.org/2014/10/the-value-of-keeping-the-right-customers.Google Scholar
• Gao X, Jasin S, Najafi S, Zhang H (2022) Joint learning and optimization for multi-product pricing (and ranking) under a general cascade click model. Management Sci. 68(10):7362–7382.Link, 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. EC ’21: Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 560–561.Google Scholar
• Guo F, Liu C, Wang YM (2009) Efficient multiple-click models in web search. Baeza-Yates R, Boldi P, Ribeiro-Neto B, Cambazoglu BB, eds. WSDM ’09: Proc. Second ACM Internat. Conf. Web Search Data Mining (Association for Computing Machinery, New York), 124–131.Google Scholar
• Javanmard A, Nazerzadeh H (2019) Dynamic pricing in high-dimensions. J. Machine Learn. Res. 20(1):315–363.Google Scholar
• Joulani P, Gyorgy A, Szepesvári C (2013) Online learning under delayed feedback. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 28, no. 3 (PMLR, New York), 1453–1461.Google Scholar
• Kveton B, Szepesvari C, Wen Z, Ashkan A (2015a) Cascading bandits: Learning to rank in the cascade model. Bach F, Blei D, eds. Proc. 32nd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 37 (PMLR, New York), 767–776.Google Scholar
• Kveton B, Wen Z, Ashkan A, Szepesvari C (2015b) Combinatorial cascading bandits. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 28 (Curran Associates Inc., Red Hook, NY), 1450–1458.Google Scholar
• Kveton B, Wen Z, Ashkan A, Szepesvari C (2015c) Tight regret bounds for stochastic combinatorial semi-bandits. Lebanon G, Vishwanathan SVN, eds. Proc. Eighteenth Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 38 (PMLR, New York), 535–543.Google Scholar
• Kveton B, Zaheer M, Szepesvari C, Li L, Ghavamzadeh M, Boutilier C (2020) Randomized exploration in generalized linear bandits. Chiappa S, Calandra R, eds. Proc. Twenty Third Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 108 (PMLR, New York), 2066–2076.Google Scholar
• Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Lattimore T, Kveton B, Li S, Szepesvari C (2018) Toprank: A practical algorithm for online stochastic ranking. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY), 3949–3958.Google Scholar
• Li S, Zhang S (2018) Online clustering of contextual cascading bandits. McIlraith SA, Weinberger KQ, eds. Proc. Thirty-Second AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 3554–3561.Google Scholar
• Li L, Lu Y, Zhou D (2017) Provably optimal algorithms for generalized linear contextual bandits. Precup D, The YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (PMLR, New York), 2071–2080.Google Scholar
• Li L, Chu W, Langford J, Schapire RE (2010) A contextual-bandit approach to personalized news article recommendation. Rappa M, Jones P, Freire J, Chakrabarti S, eds. Proc. 19th Internat. Conf. World Wide Web (WWW ’10) (Association for Computing Machinery, New York), 661–670.Google Scholar
• Li S, Wang B, Zhang S, Chen W (2016) Contextual combinatorial cascading bandits. Balcan M-F, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 48 (PMLR, New York), 1245–1253.Google Scholar
• Li L, Chu W, Langford J, Moon T, Wang X (2012) An unbiased offline evaluation of contextual bandit algorithms with generalized linear models. Proc. Workshop On-Line Trading Exploration Exploitation 2 (PMLR, New York), 19–36.Google Scholar
• Miao S, Chao X (2022) Online personalized assortment optimization with high-dimensional customer contextual data. Manufacturing Service Oper. Management 24(5):2741–2760.Google Scholar
• Moriwaki D, Fujita K, Yasui S, Hoshino T (2019) Fatigue-aware ad creative selection. Preprint, submitted August 21, https://arxiv.org/abs/1908.08936.Google Scholar
• Newswire P (2020) Global digital advertising and marketing industry. Accessed September 5, 2020, https://www.prnewswire.com/news-releases/global-digital-advertising-and-marketing-industry-301093781.html.Google Scholar
• Oh M, Iyengar G (2019) Thompson sampling for multinomial logit contextual bandits. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates Inc., Red Hook, NY), 3151–3161.Google Scholar
• Oh M, Iyengar G (2021) Multinomial logit contextual bandits: Provable optimality and practicality. Leyton-Brown K, Mausam, eds. Proc. Thirty-Fifth AAAI Conf. Artificial Intelligence, vol. 35 (AAAI Press, Palo Alto, CA), 9205–9213.Google Scholar
• Ou M, Li N, Zhu S, Jin R (2018) Multinomial logit bandit with linear utility functions. Preprint, submitted May 8, https://arxiv.org/abs/1805.02971.Google Scholar
• Qiang S, Bayati M (2016) Dynamic pricing with demand covariates. Preprint, submitted April 25, https://arxiv.org/abs/1604.07463.Google Scholar
• Radlinski F, Kleinberg R, Joachims T (2008) Learning diverse rankings with multi-armed bandits. Cohen WW, McCallum A, Roweis ST, eds. Machine Learn., Proc. Twenty-Fifth Internat. Conf. (ICML 2008) (Association for Computing Machinery, New York), 784–791.Google Scholar
• Robbins H (1985) Some aspects of the sequential design of experiments. Herbert Robbins Selected Papers (Springer, New York), 169–177.Crossref, Google Scholar
• Rusmevichientong P, Tsitsiklis JN (2010) Linearly parameterized bandits. Math. Oper. Res. 35(2):395–411.Link, Google Scholar
• Rusmevichientong P, Shen ZJM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6):1666–1680.Link, Google Scholar
• Sauré D, Zeevi A (2013) Optimal dynamic assortment planning with demand learning. Manufacturing Service Oper. Management 15(3):387–404.Link, Google Scholar
• Schmit S, Johari R (2018) Learning with abandonment. Proc. Internat. Conf. Machine Learn., vol. 80 (PMLR, New York), 4516–4524.Google Scholar
• Sinha I, Foscht T (2007) Over-marketing and brand suicide. Reverse Psychology Marketing (Springer, London), 23–50.Crossref, Google Scholar
• Slivkins A, Radlinski F, Gollapudi S (2013) Ranked bandits in metric spaces: Learning diverse rankings over large document collections. J. Machine Learn. Res. 14(Feb):399–436.Google Scholar
• Sutton RS, Barto AG (1998) Reinforcement Learning: An Introduction, vol. 1, no. 1 (MIT Press, Cambridge, MA).Google Scholar
• Tropp JA (2011) User-friendly tail bounds for matrix martingales. Technical report, California Institute of Tech, Pasadena.Google Scholar
• Wang Y, Tulabandhula T (2019) Thompson sampling for a fatigue-aware online recommendation system. Preprint, submitted January 23, https://arxiv.org/abs/1901.07734.Google Scholar
• Zong S, Ni H, Sung K, Ke NR, Wen Z, Kveton B (2016) Cascading bandits for large-scale recommendation problems. Preprint, submitted March 17, https://arxiv.org/abs/1603.05359.Google Scholar