Cascading Bandits: Learning to Rank in the Cascade Model
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 CascadeKL-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 CascadeKL-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.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning-To-RankSimilar Papers 제목 키워드 기반
Cascading Non-Stationary Bandits: Online Learning to Rank in the Non-Stationary Cascade Model
Non-stationarity appears in many online applications such as web search and advertising. In this paper, we study the online learning to rank problem in a non-stationary environment where user preferences change abruptly …
Learning-To-RankCascading Bandits Robust to Adversarial Corruptions
Online learning to rank sequentially recommends a small list of items to users from a large candidate set and receives the users' click feedback. In many real-world scenarios, users browse the recommended list in order a…
Learning-To-RankCascading Hybrid Bandits: Online Learning to Rank for Relevance and Diversity
Relevance ranking and result diversification are two core areas in modern recommender systems. Relevance ranking aims at building a ranked list sorted in decreasing order of item relevance, while result diversification f…
DiversityLearning-To-RankRecommendation SystemsCascading Contextual Assortment Bandits
We present a new combinatorial bandit model, the \textit{cascading contextual assortment bandit}. This model serves as a generalization of both existing cascading bandits and assortment bandits, broadening their applicab…
Thompson Sampling Algorithms for Cascading Bandits
Motivated by the pressing need for efficient optimization in online recommender systems, we revisit the cascading bandit model proposed by Kveton et al. (2015). While Thompson sampling (TS) algorithms have been shown to …
Efficient ExplorationMulti-Armed BanditsRecommendation SystemsThompson Sampling