Online platforms such as Q&A forums (e.g. StackExchange, Reddit) receive high volume content that streams in from different sources at high speed. These platforms need to rapidly identify and display high quality content\u00a0 to the users after weeding out garbage content.\u00a0 We formulate this problem using\u00a0 Multi-Armed Bandits (MAB) with arms modeling arriving content. We\u00a0 call the model\u00a0 \u201cBallooning MAB\u201d since the arms (streaming inputs) grow with time.\u00a0 The objective is to achieve extremely low, sublinear regret in being able to display the highest quality content by observing the user reactions to the content.\u00a0 First, we show that when\u00a0 new content arrives with unknown, uniformly distributed\u00a0 quality, it is impossible to achieve a sublinear regret guarantee.\u00a0 \u00a0\u00a0We then make a realistic assumption, motivated by several empirical studies in the literature, that the best (highest quality) arms are expected to arrive \u201cearly.\u201d\u00a0 This enables to\u00a0 drop \u201clater\u201d arms without exploring them at all and we design a threshold-based algorithm that achieves sublinear regret. In particular, we exactly quantify the sublinear regret when the best arm arrival follows a sub-exponential or sub-Pareto tail distribution and show that the algorithms achieve substantially low sublinear regret. <\/p>\n\n\n\n
This is joint work with Ganesh Ghalme (Postdoc, Technion); Swapnil Dhamal (Postdoc, Chalmers); Shweta Jain (IIT-Ropar); and Sujit Gujar (IIIT-Hyderabad).<\/p>\n\n\n\n
References:<\/strong><\/p>\n\n\n\n Ganesh Ghalme, Swapnil Dhamal, Shweta Jain, Sujit Gujar, Y. Narahari. Ballooning Multi-Armed Bandits, Artificial Intelligence<\/strong>,\u00a0Volume 296, 2021, 31 pages.<\/p>\n","protected":false},"excerpt":{"rendered":" Online platforms such as Q&A forums (e.g. StackExchange, Reddit) receive high volume content that streams in from different sources at high speed. These platforms need to rapidly identify and display high quality content\u00a0 to the users after weeding out garbage content.\u00a0 We formulate this problem using\u00a0 Multi-Armed Bandits (MAB) with arms modeling arriving content. We\u00a0 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5372,"menu_order":16,"comment_status":"closed","ping_status":"closed","template":"template-researchsnippets.php","meta":{"kt_blocks_editor_width":""},"acf":[],"_links":{"self":[{"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/pages\/5384"}],"collection":[{"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/comments?post=5384"}],"version-history":[{"count":4,"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/pages\/5384\/revisions"}],"predecessor-version":[{"id":5654,"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/pages\/5384\/revisions\/5654"}],"up":[{"embeddable":true,"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/pages\/5372"}],"wp:attachment":[{"href":"https:\/\/gtl.csa.iisc.ac.in\/hari\/wp-json\/wp\/v2\/media?parent=5384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}