{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:52Z","timestamp":1750220632181,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"US National Science Foundation","award":["CCF-2006526"],"award-info":[{"award-number":["CCF-2006526"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451004","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"74-87","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Linear bandits with limited adaptivity and learning distributional optimal design"],"prefix":"10.1145","author":[{"given":"Yufei","family":"Ruan","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6148-8738","authenticated-orcid":false,"given":"Jiaqi","family":"Yang","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}]},{"given":"Yuan","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"2312","article-title":"Improved Algorithms for Linear Stochastic Bandits","author":"Yasin","year":"2011","unstructured":"Yasin Abbasi-yadkori, D\u00e1vid P\u00e1l, Csaba Szepesv\u00e1ri, J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger. 2011. Improved Algorithms for Linear Stochastic Bandits. In Advances in Neural Information Processing Systems. 24, Curran Associates, Inc.. Pages 2312\u20132320.","journal-title":"Advances in Neural Information Processing Systems. 24, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1038-1"},{"volume-title":"Proceedings of the Sixteenth International Conference on Machine Learning. ICML '99","author":"Abe Naoki","key":"e_1_3_2_1_3_1","unstructured":"Naoki Abe and Philip M. Long. 1999. Associative Reinforcement Learning Using Linear Probabilistic Concepts. In Proceedings of the Sixteenth International Conference on Machine Learning. ICML '99. Morgan Kaufmann Publishers Inc.. Pages 3\u201311. isbn:1558606122"},{"key":"e_1_3_2_1_4_1","first-page":"75","volume-title":"Proceedings of the 2017 Conference on Learning Theory. Proceedings of Machine Learning Research. 65","author":"Agarwal Arpit","year":"2017","unstructured":"Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, Sanjeev Khanna, Satyen Kale, and Ohad Shamir. 2017. Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons. In Proceedings of the 2017 Conference on Learning Theory. Proceedings of Machine Learning Research. 65, PMLR. Pages 39\u201375."},{"key":"e_1_3_2_1_5_1","first-page":"40","volume-title":"Mathematical Programming","author":"Allen-Zhu Zeyuan","year":"2020","unstructured":"Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. 2020. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, 2020. Pages 1\u201340."},{"volume-title":"Optimum experimental designs, with SAS. 34","author":"Atkinson Anthony","key":"e_1_3_2_1_6_1","unstructured":"Anthony Atkinson, Alexander Donev, and Randall Tobias. 2007. Optimum experimental designs, with SAS. 34, Oxford University Press."},{"key":"e_1_3_2_1_7_1","first-page":"2003","article-title":"Using Confidence Bounds for Exploitation-Exploration Trade-Offs","volume":"3","author":"Auer Peter","year":"2003","unstructured":"Peter Auer. 2003. Using Confidence Bounds for Exploitation-Exploration Trade-Offs. Journal of Machine Learning Research, 3, March, 2003. Pages 397\u2013422. issn:1532-4435","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_8_1","first-page":"8004","article-title":"Provably Efficient Q-Learning with Low Switching Cost","author":"Bai Yu","year":"2019","unstructured":"Yu Bai, Tengyang Xie, Nan Jiang, Yu-Xiang Wang, H. Wallach, H. Larochelle, A. Beygelzimer, F. d\\textquotesingle Alch\u00e9-Buc, E. Fox, and R. Garnett. 2019. Provably Efficient Q-Learning with Low Switching Cost. In Advances in Neural Information Processing Systems. 32, Curran Associates, Inc.. Pages 8004\u20138013.","journal-title":"Advances in Neural Information Processing Systems. 32, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_9_1","first-page":"1160","article-title":"Online Learning with Switching Costs and Other Adaptive Adversaries","author":"Cesa-Bianchi Nicol\u00f2","year":"2013","unstructured":"Nicol\u00f2 Cesa-Bianchi, Ofer Dekel, Ohad Shamir, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger. 2013. Online Learning with Switching Costs and Other Adaptive Adversaries. In Advances in Neural Information Processing Systems. 26, Curran Associates, Inc.. Pages 1160\u20131168.","journal-title":"Advances in Neural Information Processing Systems. 26, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 15, JMLR Workshop and Conference Proceedings. Pages 208\u2013214","author":"Chu Wei","year":"2011","unstructured":"Wei Chu, Lihong Li, Lev Reyzin, Robert Schapire, Geoffrey Gordon, David Dunson, and Miroslav Dud\u00edk. 2011. Contextual Bandits with Linear Payoff Functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 15, JMLR Workshop and Conference Proceedings. Pages 208\u2013214."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.018"},{"key":"e_1_3_2_1_12_1","volume-title":"Conference on Learning Theory.","author":"Dani Varsha","year":"2008","unstructured":"Varsha Dani, Thomas P Hayes, and Sham M Kakade. 2008. Stochastic Linear Optimization under Bandit Feedback. In Conference on Learning Theory."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591868"},{"key":"e_1_3_2_1_14_1","first-page":"2615","volume-title":"Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research. 119","author":"Dong Kefan","year":"2020","unstructured":"Kefan Dong, Yingkai Li, Qin Zhang, Yuan Zhou, Hal Daum\u00e9 III, and Aarti Singh. 2020. Multinomial Logit Bandit with Low Switching Cost. In Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research. 119, PMLR. Pages 2607\u20132615."},{"key":"e_1_3_2_1_15_1","first-page":"3162","volume-title":"Proceedings of the 31st Conference On Learning Theory. Proceedings of Machine Learning Research. 75","author":"Duchi John","year":"2018","unstructured":"John Duchi, Feng Ruan, Chulhee Yun, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet. 2018. Minimax Bounds on Stochastic Batched Convex Optimization. In Proceedings of the 31st Conference On Learning Theory. Proceedings of Machine Learning Research. 75, PMLR. Pages 3065\u20133162."},{"key":"e_1_3_2_1_16_1","volume-title":"Regret Bounds for Batched Bandits. arXiv preprint arXiv:1910.04959","author":"Esfandiari Hossein","year":"2019","unstructured":"Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. 2019. Regret Bounds for Batched Bandits. arXiv preprint arXiv:1910.04959, 2019."},{"key":"e_1_3_2_1_17_1","first-page":"503","article-title":"Batched Multi-armed Bandits Problem","author":"Gao Zijun","year":"2019","unstructured":"Zijun Gao, Yanjun Han, Zhimei Ren, Zhengqing Zhou, H. Wallach, H. Larochelle, A. Beygelzimer, F. d\\textquotesingle Alch\u00e9-Buc, E. Fox, and R. Garnett. 2019. Batched Multi-armed Bandits Problem. In Advances in Neural Information Processing Systems. 32, Curran Associates, Inc.. Pages 503\u2013513.","journal-title":"Advances in Neural Information Processing Systems. 32, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886521.2886686"},{"key":"e_1_3_2_1_19_1","volume-title":"Sequential Batch Learning in Finite-Action Linear Contextual Bandits. arXiv preprint arXiv:2004.06321","author":"Han Yanjun","year":"2020","unstructured":"Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. 2020. Sequential Batch Learning in Finite-Action Linear Contextual Bandits. arXiv preprint arXiv:2004.06321, 2020."},{"key":"e_1_3_2_1_20_1","first-page":"854","article-title":"Distributed Exploration in Multi-Armed Bandits","author":"Hillel Eshcar","year":"2013","unstructured":"Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, Oren Somekh, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger. 2013. Distributed Exploration in Multi-Armed Bandits. In Advances in Neural Information Processing Systems. 26, Curran Associates, Inc.. Pages 854\u2013862.","journal-title":"Advances in Neural Information Processing Systems. 26, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_21_1","first-page":"148","volume-title":"Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 51","author":"Jun Kwang-Sung","unstructured":"Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, Xiaojin Zhu, Arthur Gretton, and Christian C. Robert. 2016. Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 51, PMLR. Pages 139\u2013148."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00024"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1960-030-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"e_1_3_2_1_25_1","first-page":"2174","volume-title":"Proceedings of Machine Learning Research. 99","author":"Li Yingkai","year":"2019","unstructured":"Yingkai Li, Yining Wang, Yuan Zhou, Alina Beygelzimer, and Daniel Hsu. 2019. Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits. In Proceedings of the Thirty-Second Conference on Learning Theory. Proceedings of Machine Learning Research. 99, PMLR. Pages 2173\u20132174."},{"key":"e_1_3_2_1_26_1","first-page":"2258","volume-title":"Proceedings of Machine Learning Research. 99","author":"Madan Vivek","year":"2019","unstructured":"Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, Weijun Xie, Alina Beygelzimer, and Daniel Hsu. 2019. Combinatorial Algorithms for Optimal Design. In Proceedings of the Thirty-Second Conference on Learning Theory. Proceedings of Machine Learning Research. 99, PMLR. Pages 2210\u20132258."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.84"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1381"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719109"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0446"},{"key":"e_1_3_2_1_31_1","first-page":"7523","article-title":"Phase Transitions and Cyclic Phenomena in Bandits with Switching Constraints","author":"Simchi-Levi David","year":"2019","unstructured":"David Simchi-Levi, Yunzong Xu, H. Wallach, H. Larochelle, A. Beygelzimer, F. d\\textquotesingle Alch\u00e9-Buc, E. Fox, and R. Garnett. 2019. Phase Transitions and Cyclic Phenomena in Bandits with Switching Constraints. In Advances in Neural Information Processing Systems. 32, Curran Associates, Inc.. Pages 7523\u20137532.","journal-title":"Advances in Neural Information Processing Systems. 32, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_32_1","volume-title":"Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability. Available at SSRN","author":"Simchi-Levi David","year":"2020","unstructured":"David Simchi-Levi and Yunzong Xu. 2020. Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability. Available at SSRN, 2020."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175450"},{"key":"e_1_3_2_1_34_1","first-page":"828","article-title":"Best-Arm Identification in Linear Bandits","author":"Soare Marta","year":"2014","unstructured":"Marta Soare, Alessandro Lazaric, Remi Munos, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger. 2014. Best-Arm Identification in Linear Bandits. In Advances in Neural Information Processing Systems. 27, Curran Associates, Inc.. Pages 828\u2013836.","journal-title":"Advances in Neural Information Processing Systems. 27, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722152"},{"key":"e_1_3_2_1_36_1","first-page":"4886","volume-title":"Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research. 80","author":"Tao Chao","year":"2018","unstructured":"Chao Tao, Sa\\'ul Blanco, Yuan Zhou, Jennifer Dy, and Andreas Krause. 2018. Best Arm Identification in Linear Bandits with Linear Dimension Dependency. In Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research. 80, PMLR. Pages 4877\u20134886."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00017"},{"key":"e_1_3_2_1_38_1","first-page":"143","article-title":"On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models","volume":"18","author":"Wang Yining","year":"2017","unstructured":"Yining Wang, Adams Wei Yu, and Aarti Singh. 2017. On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models. Journal of Machine Learning Research, 18, 143, 2017. Pages 1\u201341.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1080\/00949658208810560"},{"key":"e_1_3_2_1_40_1","first-page":"851","volume-title":"Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 84","author":"Xu Liyuan","year":"2018","unstructured":"Liyuan Xu, Junya Honda, Masashi Sugiyama, Amos Storkey, and Fernando Perez-Cruz. 2018. A fully adaptive algorithm for pure exploration in linear bandits. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research. 84, PMLR. Pages 843\u2013851."},{"key":"e_1_3_2_1_41_1","first-page":"15198","article-title":"Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition","author":"Zhang Zihan","year":"2020","unstructured":"Zihan Zhang, Yuan Zhou, Xiangyang Ji, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin. 2020. Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition. In Advances in Neural Information Processing Systems. 33, Curran Associates, Inc.. Pages 15198\u201315207.","journal-title":"Advances in Neural Information Processing Systems. 33, Curran Associates, Inc.. Pages"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451004","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451004","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":41,"alternative-id":["10.1145\/3406325.3451004","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451004","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}