TopRank: A practical algorithm for online stochastic ranking

TopRank: A practical algorithm for online stochastic ranking. Lattimore, T., Kveton, B., Li, S., & Szepesvári, C. In Advances in Neural Information Processing Systems, 09, 2018.

Paper abstract bibtex 1 download

Online learning to rank is a sequential decision-making problem where in each round the learning agent chooses a list of items and receives feedback in the form of clicks from the user. Many sample-efficient algorithms have been proposed for this problem that assume a specific click model connecting rankings and user behavior. We propose a generalized click model that encompasses many existing models, including the position-based and cascade models. Our generalization motivates a novel online learning algorithm based on topological sort, which we call TopRank. TopRank is (a) more natural than existing algorithms, (b) has stronger regret guarantees than existing algorithms with comparable generality, (c) has a more insightful proof that leaves the door open to many generalizations, (d) outperforms existing algorithms empirically.

@inproceedings{LKLSz18,
	abstract = {Online learning to rank is a sequential decision-making problem where in each round the learning agent chooses a list of items and receives feedback in the form of clicks from the user. Many sample-efficient algorithms have been proposed for this problem that assume a specific click model connecting rankings and user behavior. We propose a generalized click model that encompasses many existing models, including the position-based and cascade models. Our generalization motivates a novel online learning algorithm based on topological sort, which we call TopRank. TopRank is (a) more natural than existing algorithms, (b) has stronger regret guarantees than existing algorithms with comparable generality, (c) has a more insightful proof that leaves the door open to many generalizations, (d) outperforms existing algorithms empirically.},
	acceptrate = {1011 out of 4856=21\%},
	author = {Lattimore, T. and Kveton, B. and Li, S. and Szepesv{\'a}ri, Cs.},
	booktitle = {Advances in Neural Information Processing Systems},
	keywords = {ranking, online learning, partial information, stochastic online learning, online learning to rank},
	month = {09},
	title = {TopRank: A practical algorithm for online stochastic ranking},
	url_paper = {NeurIPS2018-toprank.pdf},
	year = {2018}}

Downloads: 1