Cascading Linear Submodular Bandits: Accounting for Position Bias and Diversity in Online Learning to Rank

Gaurush Hiranandani, Harvineet Singh, Prakhar Gupta, Iftikhar Ahamath Burhanuddin, Zheng Wen, Branislav Kveton
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:722-732, 2020.

Abstract

Online learning, position bias, and diversified retrieval are three crucial aspects in designing ranking systems based on user clicks. One simple click model which explains the position bias is the cascade model. Many online learning variants of the cascade model have been proposed, but none so far captures diversity. Similarly, online learning to rank methods which capture diversity do not handle position bias. Motivated by these limitations, we propose a novel click model, and the associated online learning variant to address both position bias and diversified retrieval in a unified framework. Despite the objective function not being a standard submodular set function, we prove that a greedy-approach is a reasonable approximation. We then propose, CascadeLSB, an algorithm whose goal is to recommend K most attractive items from a large set of L items with the attractiveness of items being modeled as a submodular utility function. We analyze the algorithm and prove a gap-free upper bound on its n-step regret. We comprehensively evaluate CascadeLSB on synthetic and real datasets, where it outperforms all the baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-hiranandani20a, title = {Cascading Linear Submodular Bandits: Accounting for Position Bias and Diversity in Online Learning to Rank}, author = {Hiranandani, Gaurush and Singh, Harvineet and Gupta, Prakhar and Burhanuddin, Iftikhar Ahamath and Wen, Zheng and Kveton, Branislav}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {722--732}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/hiranandani20a/hiranandani20a.pdf}, url = {https://proceedings.mlr.press/v115/hiranandani20a.html}, abstract = {Online learning, position bias, and diversified retrieval are three crucial aspects in designing ranking systems based on user clicks. One simple click model which explains the position bias is the cascade model. Many online learning variants of the cascade model have been proposed, but none so far captures diversity. Similarly, online learning to rank methods which capture diversity do not handle position bias. Motivated by these limitations, we propose a novel click model, and the associated online learning variant to address both position bias and diversified retrieval in a unified framework. Despite the objective function not being a standard submodular set function, we prove that a greedy-approach is a reasonable approximation. We then propose, CascadeLSB, an algorithm whose goal is to recommend K most attractive items from a large set of L items with the attractiveness of items being modeled as a submodular utility function. We analyze the algorithm and prove a gap-free upper bound on its n-step regret. We comprehensively evaluate CascadeLSB on synthetic and real datasets, where it outperforms all the baselines.} }
Endnote
%0 Conference Paper %T Cascading Linear Submodular Bandits: Accounting for Position Bias and Diversity in Online Learning to Rank %A Gaurush Hiranandani %A Harvineet Singh %A Prakhar Gupta %A Iftikhar Ahamath Burhanuddin %A Zheng Wen %A Branislav Kveton %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-hiranandani20a %I PMLR %P 722--732 %U https://proceedings.mlr.press/v115/hiranandani20a.html %V 115 %X Online learning, position bias, and diversified retrieval are three crucial aspects in designing ranking systems based on user clicks. One simple click model which explains the position bias is the cascade model. Many online learning variants of the cascade model have been proposed, but none so far captures diversity. Similarly, online learning to rank methods which capture diversity do not handle position bias. Motivated by these limitations, we propose a novel click model, and the associated online learning variant to address both position bias and diversified retrieval in a unified framework. Despite the objective function not being a standard submodular set function, we prove that a greedy-approach is a reasonable approximation. We then propose, CascadeLSB, an algorithm whose goal is to recommend K most attractive items from a large set of L items with the attractiveness of items being modeled as a submodular utility function. We analyze the algorithm and prove a gap-free upper bound on its n-step regret. We comprehensively evaluate CascadeLSB on synthetic and real datasets, where it outperforms all the baselines.
APA
Hiranandani, G., Singh, H., Gupta, P., Burhanuddin, I.A., Wen, Z. & Kveton, B.. (2020). Cascading Linear Submodular Bandits: Accounting for Position Bias and Diversity in Online Learning to Rank. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:722-732 Available from https://proceedings.mlr.press/v115/hiranandani20a.html.

Related Material