{"id":2401,"date":"2019-08-04T08:46:48","date_gmt":"2019-08-04T08:46:48","guid":{"rendered":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/?p=2401"},"modified":"2019-09-15T10:03:12","modified_gmt":"2019-09-15T10:03:12","slug":"ijcai-2019-paper-on-cascading-non-stationary-bandits-online","status":"publish","type":"post","link":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/ijcai-2019-paper-on-cascading-non-stationary-bandits-online\/","title":{"rendered":"IJCAI 2019 papers online"},"content":{"rendered":"\n<p><em>Cascading non-stationary bandits: Online learning to rank in the non-stationary cascade model<\/em> by Chang Li and Maarten de Rijke is online now <a href=\"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-content\/papercite-data\/pdf\/li-2019-cascading.pdf\">at this location<\/a>. <\/p>\n\n\n\n<p>In the paper, we argue that non-stationarity appears in many online applications such as web search and advertising. We study the online learning to rank problem in a&nbsp;<em>non-stationary&nbsp;<\/em>environment where user preferences change abruptly at an unknown moment in time. We consider the problem of identifying the K&nbsp;most attractive items and propose&nbsp;<em>cascading non-stationary bandits<\/em>, an online learning variant of the cascading model, where a user browses a ranked list from top to bottom and clicks on the first attractive item. We propose two algorithms for solving this non-stationary problem:&nbsp;CascadeDUCB&nbsp;andCascadeSWUCB. We analyze their performance and derive gap-dependent upper bounds on the&nbsp;$n$-step regret of these algorithms. We also establish a lower bound on the regret for cascading non-stationary bandits and show that both algorithms match the lower bound up to a logarithmic factor. Finally, we evaluate their performance on a real-world web search click dataset.<\/p>\n\n\n\n<p><ul class=\"papercite_bibliography\">       <li>           Chang Li and Maarten de Rijke. Cascading non-stationary bandits: Online learning to rank in the non-stationary cascade model. In <em>IJCAI 2019: Twenty-Eighth International Joint Conference on Artificial Intelligence<\/em>, page 2859\u20132865, August 2019.      <a href=\"javascript:void(0)\" id=\"papercite_0\" class=\"papercite_toggle\"><span style=\"color: #898989;\">Bibtex<\/span><\/a>, <a href=\"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-content\/papercite-data\/pdf\/li-2019-cascading.pdf\" title='Download PDF' class='papercite_pdf'>PDF<\/a>    <div class=\"papercite_bibtex\" id=\"papercite_0_block\"><pre><code class=\"tex bibtex\">@inproceedings{li-2019-cascading,\nauthor = {Li, Chang and de Rijke, Maarten},\nbooktitle = {IJCAI 2019: Twenty-Eighth International Joint Conference on Artificial Intelligence},\ndate-added = {2019-05-30 22:36:52 +0200},\ndate-modified = {2019-08-04 15:53:45 +0200},\nmonth = {August},\npages = {2859--2865},\ntitle = {Cascading non-stationary bandits: Online learning to rank in the non-stationary cascade model},\nyear = {2019}}<\/code><\/pre><\/div>         <\/li>           <\/ul><\/p>\n\n\n\n<p>Other papers and presentations at IJCAI are part of the SCAI workshop:<br><ul class=\"papercite_bibliography\">       <li>           Jiahuan Pei, Arent Stienstra, Julia Kiseleva, and Maarten de Rijke. SEntNet: Source-aware Recurrent Entity Networks for Dialogue Response Selection. In <em>4th International Workshop on Search-Oriented Conversational AI (SCAI)<\/em>, August 2019.      <a href=\"javascript:void(0)\" id=\"papercite_1\" class=\"papercite_toggle\"><span style=\"color: #898989;\">Bibtex<\/span><\/a>, <a href=\"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-content\/papercite-data\/pdf\/pei-2019-sentnet.pdf\" title='Download PDF' class='papercite_pdf'>PDF<\/a>    <div class=\"papercite_bibtex\" id=\"papercite_1_block\"><pre><code class=\"tex bibtex\">@inproceedings{pei-2019-sentnet,\nauthor = {Pei, Jiahuan and Stienstra, Arent and Kiseleva, Julia and de Rijke, Maarten},\nbooktitle = {4th International Workshop on Search-Oriented Conversational AI (SCAI)},\ndate-added = {2019-06-06 11:55:06 +0200},\ndate-modified = {2019-06-06 11:56:16 +0200},\nmonth = {August},\ntitle = {SEntNet: Source-aware Recurrent Entity Networks for Dialogue Response Selection},\nyear = {2019}}<\/code><\/pre><\/div>         <\/li>           <\/ul><ul class=\"papercite_bibliography\">       <li>           Yangjun Zhang, Pengjie Ren, and Maarten de Rijke. Improving Background Based Conversation with Context-aware Knowledge Pre-selection. In <em>4th International Workshop on Search-Oriented Conversational AI (SCAI)<\/em>, August 2019.      <a href=\"javascript:void(0)\" id=\"papercite_2\" class=\"papercite_toggle\"><span style=\"color: #898989;\">Bibtex<\/span><\/a>, <a href=\"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-content\/papercite-data\/pdf\/zhang-2019-improving.pdf\" title='Download PDF' class='papercite_pdf'>PDF<\/a>    <div class=\"papercite_bibtex\" id=\"papercite_2_block\"><pre><code class=\"tex bibtex\">@inproceedings{zhang-2019-improving,\nauthor = {Zhang, Yangjun and Ren, Pengjie and de Rijke, Maarten},\nbooktitle = {4th International Workshop on Search-Oriented Conversational AI (SCAI)},\ndate-added = {2019-06-06 11:53:36 +0200},\ndate-modified = {2019-06-06 11:55:01 +0200},\nmonth = {August},\ntitle = {Improving Background Based Conversation with Context-aware Knowledge Pre-selection},\nyear = {2019}}<\/code><\/pre><\/div>         <\/li>           <\/ul><\/p>\n\n\n\n<ul><li>Maarten de Rijke and Pengjie Ren. SERP-based Conversations. In&nbsp;<em>4th International Workshop on Search-Oriented Conversational AI (SCAI)<\/em>, August 2019.&nbsp;<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Cascading non-stationary bandits: Online learning to rank in the non-stationary cascade model by Chang Li and Maarten de Rijke is online now at this location. In the paper, we argue that non-stationarity appears in many online applications such as web search and advertising. We study the online learning to rank problem in a&nbsp;non-stationary&nbsp;environment where user&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/posts\/2401"}],"collection":[{"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/comments?post=2401"}],"version-history":[{"count":6,"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/posts\/2401\/revisions"}],"predecessor-version":[{"id":2437,"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/posts\/2401\/revisions\/2437"}],"wp:attachment":[{"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/media?parent=2401"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/categories?post=2401"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/staff.fnwi.uva.nl\/m.derijke\/wp-json\/wp\/v2\/tags?post=2401"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}