{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:47Z","timestamp":1750221287066,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,12,19]],"date-time":"2017-12-19T00:00:00Z","timestamp":1513641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC FSA","award":["308267"],"award-info":[{"award-number":["308267"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,12,19]]},"abstract":"<jats:p>Search engines answer users' queries by listing relevant items (e.g. documents, songs, products, web pages, ...). These engines rely on algorithms that learn to rank items so as to present an ordered list maximizing the probability that it contains relevant item. The main challenge in the design of learning-to-rank algorithms stems from the fact that queries often have different meanings for different users. In absence of any contextual information about the query, one often has to adhere to the {\\it diversity} principle, i.e., to return a list covering the various possible topics or meanings of the query. To formalize this learning-to-rank problem, we propose a natural model where (i) items are categorized into topics, (ii) users find items relevant only if they match the topic of their query, and (iii) the engine is not aware of the topic of an arriving query, nor of the frequency at which queries related to various topics arrive, nor of the topic-dependent click-through-rates of the items. For this problem, we devise LDR (Learning Diverse Rankings), an algorithm that efficiently learns the optimal list based on users' feedback only. We show that after $T$ queries, the regret of LDR scales as $O((N-L)\\log(T))$ where $N$ is the number of all items. We further establish that this scaling cannot be improved, i.e., LDR is order optimal. Finally, using numerical experiments on both artificial and real-world data, we illustrate the superiority of LDR compared to existing learning-to-rank algorithms.<\/jats:p>","DOI":"10.1145\/3154490","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Online Learning of Optimally Diverse Rankings"],"prefix":"10.1145","volume":"1","author":[{"given":"Stefan","family":"Magureanu","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandre","family":"Proutiere","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Isaksson","sequence":"additional","affiliation":[{"name":"Spotify AB, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boxun","family":"Zhang","sequence":"additional","affiliation":[{"name":"Spotify AB, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835804"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745852"},{"key":"e_1_2_1_4_1","first-page":"767","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML-15)","author":"Kveton Branislav","year":"2015"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513150.2513162"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281254"},{"volume-title":"AAAI","year":"2013","author":"Kohli Pushmeet","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19066-2_35"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390255"},{"key":"e_1_2_1_10_1","first-page":"1577","volume-title":"Advances in Neural Information Processing Systems","author":"Streeter Matthew","year":"2009"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2502595"},{"key":"e_1_2_1_12_1","first-page":"2483","volume-title":"Advances in Neural Information Processing Systems","author":"Yue Yisong","year":"2011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3015812.3016015"},{"key":"e_1_2_1_14_1","first-page":"461","volume-title":"SDM","author":"Qin Lijing","year":"2014"},{"key":"e_1_2_1_15_1","first-page":"1245","volume-title":"Proceedings of The 33rd International Conference on Machine Learning","author":"Li Shuai","year":"2016"},{"key":"e_1_2_1_16_1","first-page":"359","volume-title":"COLT","author":"Garivier Aur\u00e9lien","year":"2011"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2013.6691311"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012994275440"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154490","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154490","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:26Z","timestamp":1750212686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154490"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,19]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,12,19]]}},"alternative-id":["10.1145\/3154490"],"URL":"https:\/\/doi.org\/10.1145\/3154490","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2017,12,19]]},"assertion":[{"value":"2017-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}