{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:02Z","timestamp":1750220702491,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384341","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1237-1250","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen","family":"Wang","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017","author":"Agarwal Arpit","year":"2017","unstructured":"Arpit Agarwal , Shivani Agarwal , Sepehr Assadi , and Sanjeev Khanna . 2017 . Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons . In Proceedings of the 30th Conference on Learning Theory, COLT 2017 , Amsterdam, The Netherlands , 7-10 July 2017. 39\u201375. Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. 2017. Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017. 39\u201375."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems","author":"Agarwal Deepak","year":"2008","unstructured":"Deepak Agarwal , Bee-Chung Chen , Pradheep Elango , Nitin Motgi , Seung-Taek Park , Raghu Ramakrishnan , Scott Roy , and Joe Zachariah . 2008 . Online Models for Content Optimization. In Advances in Neural Information Processing Systems 21 , Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems , Vancouver, British Columbia, Canada , December 8-11, 2008. 17\u201324. Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, Nitin Motgi, Seung-Taek Park, Raghu Ramakrishnan, Scott Roy, and Joe Zachariah. 2008. Online Models for Content Optimization. In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008. 17\u201324."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Yossi Matias and Mario Szegedy. 1996. The space complexity of approximating the frequency moments. In STOC. 20\u201329.  Noga Alon Yossi Matias and Mario Szegedy. 1996. The space complexity of approximating the frequency moments. In STOC. 20\u201329.","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi and Chen Wang. 2020. Exploration with Limited Memory: Streaming Algorithms for Coin Tossing Noisy Comparisons and Multi-Armed Bandits. arxiv:2004.04666.  Sepehr Assadi and Chen Wang. 2020. Exploration with Limited Memory: Streaming Algorithms for Coin Tossing Noisy Comparisons and Multi-Armed Bandits. arxiv:2004.04666.","DOI":"10.1145\/3357713.3384341"},{"key":"e_1_3_2_1_6_1","volume-title":"Best Arm Identification in Multi-Armed Bandits. In COLT 2010 - The 23rd Conference on Learning Theory","author":"Audibert Jean-Yves","year":"2010","unstructured":"Jean-Yves Audibert , S\u00e9bastien Bubeck , and R\u00e9mi Munos . 2010 . Best Arm Identification in Multi-Armed Bandits. In COLT 2010 - The 23rd Conference on Learning Theory , Haifa, Israel , June 27-29, 2010. 41\u201353. Jean-Yves Audibert, S\u00e9bastien Bubeck, and R\u00e9mi Munos. 2010. Best Arm Identification in Multi-Armed Bandits. In COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010. 41\u201353."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_2_1_8_1","volume-title":"Collaborative PAC Learning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Blum Avrim","year":"2017","unstructured":"Avrim Blum , Nika Haghtalab , Ariel D. Procaccia , and Mingda Qiao . 2017 . Collaborative PAC Learning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 , 4-9 December 2017, Long Beach, CA, USA. 2392\u20132401. Avrim Blum, Nika Haghtalab, Ariel D. Procaccia, and Mingda Qiao. 2017. Collaborative PAC Learning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. 2392\u20132401."},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016","author":"Braverman Mark","year":"2016","unstructured":"Mark Braverman , Jieming Mao , and S. Matthew Weinberg . 2016. Parallel algorithms for select and partition with noisy comparisons . In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 , Cambridge, MA, USA , June 18-21, 2016 . 851\u2013862. Mark Braverman, Jieming Mao, and S. Matthew Weinberg. 2016. Parallel algorithms for select and partition with noisy comparisons. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. 851\u2013862."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.059"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning, ICML 2013","author":"Bubeck S\u00e9bastien","year":"2013","unstructured":"S\u00e9bastien Bubeck , Tengyao Wang , and Nitin Viswanathan . 2013 . Multiple Identifications in Multi-Armed Bandits . In Proceedings of the 30th International Conference on Machine Learning, ICML 2013 , Atlanta, GA, USA , 16-21 June 2013. 258\u2013265. S\u00e9bastien Bubeck, Tengyao Wang, and Nitin Viswanathan. 2013. Multiple Identifications in Multi-Armed Bandits. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013. 258\u2013265."},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning, ICML 2013","author":"Busa-Fekete R\u00f3bert","year":"2013","unstructured":"R\u00f3bert Busa-Fekete , Bal\u00e1zs Sz\u00f6r\u00e9nyi , Weiwei Cheng , Paul Weng , and Eyke H\u00fcllermeier . 2013 . Top-k Selection based on Adaptive Sampling of Noisy Preferences . In Proceedings of the 30th International Conference on Machine Learning, ICML 2013 , Atlanta, GA, USA , 16-21 June 2013. 1094\u20131102. R\u00f3bert Busa-Fekete, Bal\u00e1zs Sz\u00f6r\u00e9nyi, Weiwei Cheng, Paul Weng, and Eyke H\u00fcllermeier. 2013. Top-k Selection based on Adaptive Sampling of Noisy Preferences. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013. 1094\u20131102."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT 2016","author":"Carpentier Alexandra","year":"2016","unstructured":"Alexandra Carpentier and Andrea Locatelli . 2016 . Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem . In Proceedings of the 29th Conference on Learning Theory, COLT 2016 , New York, USA , June 23-26, 2016. 590\u2013604. Alexandra Carpentier and Andrea Locatelli. 2016. Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016. 590\u2013604."},{"key":"e_1_3_2_1_14_1","volume-title":"Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory. CoRR, abs\/1901.08387","author":"Chaudhuri Arghya Roy","year":"2019","unstructured":"Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan . 2019. Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory. CoRR, abs\/1901.08387 ( 2019 ). Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. 2019. Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory. CoRR, abs\/1901.08387 (2019)."},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT 2016","author":"Chen Lijie","year":"2016","unstructured":"Lijie Chen , Anupam Gupta , and Jian Li . 2016 . Pure Exploration of Multi-armed Bandit Under Matroid Constraints . In Proceedings of the 29th Conference on Learning Theory, COLT 2016 , New York, USA , June 23-26, 2016. 647\u2013669. Lijie Chen, Anupam Gupta, and Jian Li. 2016. Pure Exploration of Multi-armed Bandit Under Matroid Constraints. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016. 647\u2013669."},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017","author":"Chen Lijie","year":"2017","unstructured":"Lijie Chen , Jian Li , and Mingda Qiao . 2017 . Towards Instance Optimal Bounds for Best Arm Identification . In Proceedings of the 30th Conference on Learning Theory, COLT 2017 , Amsterdam, The Netherlands , 7-10 July 2017. 535\u2013592. Lijie Chen, Jian Li, and Mingda Qiao. 2017. Towards Instance Optimal Bounds for Best Arm Identification. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017. 535\u2013592."},{"key":"e_1_3_2_1_17_1","volume-title":"Combinatorial Pure Exploration of Multi-Armed Bandits. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Chen Shouyuan","year":"2014","unstructured":"Shouyuan Chen , Tian Lin , Irwin King , Michael R. Lyu , and Wei Chen . 2014 . Combinatorial Pure Exploration of Multi-Armed Bandits. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014 , December 8-13 2014, Montreal, Quebec, Canada. 379\u2013387. Shouyuan Chen, Tian Lin, Irwin King, Michael R. Lyu, and Wei Chen. 2014. Combinatorial Pure Exploration of Multi-Armed Bandits. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada. 379\u2013387."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433420"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039767"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.160"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015","author":"Chen Yuxin","year":"2015","unstructured":"Yuxin Chen and Changho Suh . 2015 . Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons . In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015 , Lille, France , 6-11 July 2015. 371\u2013380. Yuxin Chen and Changho Suh. 2015. Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015. 371\u2013380."},{"key":"e_1_3_2_1_22_1","volume-title":"Instance-Optimality in the Noisy Value-and Comparison-Model. In In SODA 2020 (to appear).","author":"Cohen-Addad Vincent","year":"2020","unstructured":"Vincent Cohen-Addad , Frederik Mallmann-Trenn , and Claire Mathieu . 2020 . Instance-Optimality in the Noisy Value-and Comparison-Model. In In SODA 2020 (to appear). Vincent Cohen-Addad, Frederik Mallmann-Trenn, and Claire Mathieu. 2020. Instance-Optimality in the Noisy Value-and Comparison-Model. In In SODA 2020 (to appear)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90382-3"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684066"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"e_1_3_2_1_26_1","volume-title":"15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings. 255\u2013270","author":"Even-Dar Eyal","year":"2002","unstructured":"Eyal Even-Dar , Shie Mannor , and Yishay Mansour . 2002 . PAC Bounds for Multi-armed Bandit and Markov Decision Processes. In Computational Learning Theory , 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings. 255\u2013270 . Eyal Even-Dar, Shie Mannor, and Yishay Mansour. 2002. PAC Bounds for Multi-armed Bandit and Markov Decision Processes. In Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings. 255\u2013270."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814623"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a006"},{"key":"e_1_3_2_1_30_1","volume-title":"Clustering Data Streams. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000","author":"Guha Sudipto","year":"2000","unstructured":"Sudipto Guha , Nina Mishra , Rajeev Motwani , and Liadan O\u2019Callaghan . 2000 . Clustering Data Streams. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000 , 12-14 November 2000, Redondo Beach, California, USA. 359\u2013366. Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O\u2019Callaghan. 2000. Clustering Data Streams. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA. 359\u2013366."},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of a DIMACS Workshop","author":"Henzinger Monika Rauch","year":"1998","unstructured":"Monika Rauch Henzinger , Prabhakar Raghavan , and Sridhar Rajagopalan . 1998 . Computing on data streams. In External Memory Algorithms , Proceedings of a DIMACS Workshop , New Brunswick, New Jersey, USA , May 20-22, 1998. 107\u2013118. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. 1998. Computing on data streams. In External Memory Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, May 20-22, 1998. 107\u2013118."},{"key":"e_1_3_2_1_32_1","volume-title":"Tomer Koren, Ronny Lempel, and Oren Somekh.","author":"Hillel Eshcar","year":"2013","unstructured":"Eshcar Hillel , Zohar Shay Karnin , Tomer Koren, Ronny Lempel, and Oren Somekh. 2013 . Distributed Exploration in Multi-Armed Bandits. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States .. 854\u2013862. Eshcar Hillel, Zohar Shay Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. 2013. Distributed Exploration in Multi-Armed Bandits. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States.. 854\u2013862."},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of The 27th Conference on Learning Theory, COLT 2014","author":"Jamieson Kevin G.","year":"2014","unstructured":"Kevin G. Jamieson , Matthew Malloy , Robert D. Nowak , and S\u00e9bastien Bubeck . 2014 . lil\u2019 UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits . In Proceedings of The 27th Conference on Learning Theory, COLT 2014 , Barcelona, Spain , June 13-15, 2014. 423\u2013439. Kevin G. Jamieson, Matthew Malloy, Robert D. Nowak, and S\u00e9bastien Bubeck. 2014. lil\u2019 UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014. 423\u2013439."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3104322.3104388"},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning, ICML 2012","author":"Kalyanakrishnan Shivaram","year":"2012","unstructured":"Shivaram Kalyanakrishnan , Ambuj Tewari , Peter Auer , and Peter Stone . 2012 . PAC Subset Selection in Stochastic Multi-armed Bandits . In Proceedings of the 29th International Conference on Machine Learning, ICML 2012 , Edinburgh, Scotland, UK, June 26 - July 1, 2012. Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. 2012. PAC Subset Selection in Stochastic Multi-armed Bandits. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012."},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning, ICML 2013","author":"Karnin Zohar Shay","year":"2013","unstructured":"Zohar Shay Karnin , Tomer Koren , and Oren Somekh . 2013 . Almost Optimal Exploration in Multi-Armed Bandits . In Proceedings of the 30th International Conference on Machine Learning, ICML 2013 , Atlanta, GA, USA , 16-21 June 2013. 1238\u20131246. Zohar Shay Karnin, Tomer Koren, and Oren Somekh. 2013. Almost Optimal Exploration in Multi-Armed Bandits. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013. 1238\u20131246."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.2946646"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"Kazemi Ehsan","year":"2019","unstructured":"Ehsan Kazemi , Marko Mitrovic , Morteza Zadimoghaddam , Silvio Lattanzi , and Amin Karbasi . 2019 . Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , 9-15 June 2019, Long Beach, California, USA. 3311\u20133320. Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. 2019. Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. 3311\u20133320."},{"key":"e_1_3_2_1_39_1","volume-title":"Stochastic Multi-armed Bandits in Constant Space. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018","author":"Liau David","year":"2018","unstructured":"David Liau , Zhao Song , Eric Price , and Ger Yang . 2018 . Stochastic Multi-armed Bandits in Constant Space. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018 , 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain. 386\u2013394. David Liau, Zhao Song, Eric Price, and Ger Yang. 2018. Stochastic Multi-armed Bandits in Constant Space. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain. 386\u2013394."},{"key":"e_1_3_2_1_40_1","unstructured":"[n.d.]. List of Open Problems in Sublinear Algorithms. Problem 73: Streaming Online Algorithms. https:\/\/sublinear.info\/73  [n.d.]. List of Open Problems in Sublinear Algorithms. Problem 73: Streaming Online Algorithms. https:\/\/sublinear.info\/73"},{"volume-title":"16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT\/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings. 418\u2013432","author":"Mannor Shie","key":"e_1_3_2_1_41_1","unstructured":"Shie Mannor and John N. Tsitsiklis . 2003. Lower Bounds on the Sample Complexity of Exploration in the Multi-armed Bandit Problem. In Computational Learning Theory and Kernel Machines , 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT\/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings. 418\u2013432 . Shie Mannor and John N. Tsitsiklis. 2003. Lower Bounds on the Sample Complexity of Exploration in the Multi-armed Bandit Problem. In Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT\/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings. 418\u2013432."},{"key":"e_1_3_2_1_42_1","volume-title":"Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Mitrovic Slobodan","year":"2017","unstructured":"Slobodan Mitrovic , Ilija Bogunovic , Ashkan Norouzi-Fard , Jakub Tarnawski , and Volkan Cevher . 2017 . Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 , 4-9 December 2017, Long Beach, CA, USA. 4557\u20134566. Slobodan Mitrovic, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevher. 2017. Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. 4557\u20134566."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_3_2_1_44_1","volume-title":"Computing in Fault Tolerance Broadcast Networks. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004)","author":"Newman Ilan","year":"2004","unstructured":"Ilan Newman . 2004 . Computing in Fault Tolerance Broadcast Networks. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004) , 21-24 June 2004, Amherst, MA, USA. 113\u2013122. Ilan Newman. 2004. Computing in Fault Tolerance Broadcast Networks. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA. 113\u2013122."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185425"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1952-09620-8"},{"key":"e_1_3_2_1_47_1","article-title":"Simple, Robust and Optimal Ranking from Pairwise Comparisons","volume":"18","author":"Shah Nihar B.","year":"2017","unstructured":"Nihar B. Shah and Martin J. Wainwright . 2017 . Simple, Robust and Optimal Ranking from Pairwise Comparisons . J. Mach. Learn. Res. , 18 (2017), 199:1\u2013199:38. Nihar B. Shah and Martin J. Wainwright. 2017. Simple, Robust and Optimal Ranking from Pairwise Comparisons. J. Mach. Learn. Res., 18 (2017), 199:1\u2013199:38.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2747409"},{"key":"e_1_3_2_1_49_1","volume-title":"Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits. In In FOCS 2019 (to appear).","author":"Tao Chao","year":"2019","unstructured":"Chao Tao , Qin Zhang , and Yuan Zhou . 2019 . Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits. In In FOCS 2019 (to appear). Chao Tao, Qin Zhang, and Yuan Zhou. 2019. Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits. In In FOCS 2019 (to appear)."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAHCN.2016.7732984"},{"key":"e_1_3_2_1_51_1","volume-title":"Proceedings of the 31th International Conference on Machine Learning, ICML 2014","author":"Zhou Yuan","year":"2014","unstructured":"Yuan Zhou , Xi Chen , and Jian Li . 2014 . Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing . In Proceedings of the 31th International Conference on Machine Learning, ICML 2014 , Beijing, China , 21-26 June 2014. 217\u2013225. Yuan Zhou, Xi Chen, and Jian Li. 2014. Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014. 217\u2013225."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384341","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384341","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:57Z","timestamp":1750199577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":51,"alternative-id":["10.1145\/3357713.3384341","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384341","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}