Cascading Bandits: Learning to Rank in the Cascade Model

By Branislav Kveton, Csaba Szepesvari, Zheng Wen, Azin Ashkan. International Conference on Machine Learning, 2015

304 citations recorded by the source corpus.

A search engine usually outputs a list of K web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify K most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and Cascade KL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of Cascade KL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/5171da66f87d735987bfe8515fe5237307f82596

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Adversarial Attacks on Stochastic Bandits (2018, background): “This is potentially hazardous since stochastic MABs are widely used in the industry to recommend news articles [18], display advertisements [9], improve search results [17], allocate medical treatment [16], and promote users’ well-being [13], among many others.”
Bandit Algorithms (2020, methodology): “The policy and analysis presented in this chapter is by the authors and others [Lattimore et al., 2018]. The most related work is by Zoghi et al. [2017], who assumed a factorisation of the click probabilities v(a, k) = α(a(k))χ(a, k) and then made assumptions on χ.”
Advances and Challenges in Conversational Recommender Systems: A Survey (2021, background): “Cascading bandits providing reliable negative samples [84, 228]”
A Tutorial on Thompson Sampling (2017, background): “A standard form of UCB, known as UCB1, which is considered and analyzed in the context of cascading bandits in [29], takes the form”