{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T21:08:32Z","timestamp":1775423312233,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1901057"],"award-info":[{"award-number":["CNS-1901057"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS- 2007231"],"award-info":[{"award-number":["CNS- 2007231"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1618520"],"award-info":[{"award-number":["CNS-1618520"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1409336"],"award-info":[{"award-number":["CNS-1409336"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"crossref","award":["SRG\/2021\/002308"],"award-info":[{"award-number":["SRG\/2021\/002308"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2024,1]]},"DOI":"10.1007\/s10994-023-06457-z","type":"journal-article","created":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T19:02:15Z","timestamp":1700506935000},"page":"45-71","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Multi-armed bandits with dependent arms"],"prefix":"10.1007","volume":"113","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0363-3666","authenticated-orcid":false,"given":"Rahul","family":"Singh","sequence":"first","affiliation":[]},{"given":"Fang","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Yin","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Ness","family":"Shroff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,20]]},"reference":[{"key":"6457_CR1","unstructured":"Abbasi-Yadkori, Y., P\u00e1l, D., & Szepesv\u00e1ri, C. (2011). Improved algorithms for linear stochastic bandits. In: Advances in Neural Information Processing Systems, (pp. 2312\u20132320)"},{"key":"6457_CR2","unstructured":"Akshay D Kamath, S.G. (2016). Cs 395t: Sublinear algorithms, lecture notes. https:\/\/www.cs.utexas.edu\/~ecprice\/courses\/sublinear\/notes\/lec12.pdf"},{"key":"6457_CR3","unstructured":"Atan, O., Tekin, C., & Schaar, M. (2015). Global multi-armed bandits with H\u00f6lder continuity. In: Artificial Intelligence and Statistics, (pp. 28\u201336)"},{"key":"6457_CR4","first-page":"397","volume":"3","author":"P Auer","year":"2002","unstructured":"Auer, P. (2002). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3, 397\u2013422.","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"6457_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jcss.2007.04.016","volume":"74","author":"B Awerbuch","year":"2008","unstructured":"Awerbuch, B., & Kleinberg, R. (2008). Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1), 97\u2013114.","journal-title":"Journal of Computer and System Sciences"},{"issue":"10","key":"6457_CR6","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1080\/00029890.1974.11993738","volume":"81","author":"R Ayoub","year":"1974","unstructured":"Ayoub, R. (1974). Euler and the zeta function. The American Mathematical Monthly, 81(10), 1067\u20131086.","journal-title":"The American Mathematical Monthly"},{"key":"6457_CR7","unstructured":"Berry, D.A., & Fristedt, B. (1985). Bandit problems: Sequential allocation of experiments (monographs on statistics and applied probability). (vol. 5(71-87), pp. 7\u20137). Chapman and Hall."},{"issue":"7","key":"6457_CR8","doi-asserted-by":"publisher","first-page":"4094","DOI":"10.1109\/TIT.2019.2896192","volume":"65","author":"O Binette","year":"2019","unstructured":"Binette, O. (2019). A note on reverse pinsker inequalities. IEEE Transactions on Information Theory, 65(7), 4094\u20134096. https:\/\/doi.org\/10.1109\/TIT.2019.2896192","journal-title":"IEEE Transactions on Information Theory"},{"key":"6457_CR9","doi-asserted-by":"publisher","unstructured":"Bouneffouf, D., Parthasarathy, S., Samulowitz, H., & Wistuba, M. (2019). Optimal exploitation of clustering and history information in multi-armed bandit. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, International Joint Conferences on Artificial Intelligence Organization, (pp. 2016\u20132022). https:\/\/doi.org\/10.24963\/ijcai.2019\/279","DOI":"10.24963\/ijcai.2019\/279"},{"key":"6457_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"SP Boyd","year":"2004","unstructured":"Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge University Press."},{"key":"6457_CR11","doi-asserted-by":"crossref","unstructured":"Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint arXiv:1204.5721","DOI":"10.1561\/9781601986276"},{"key":"6457_CR12","doi-asserted-by":"crossref","unstructured":"Buccapatnam, S., Eryilmaz, A., & Shroff, N.B. (2014). Stochastic bandits with side observations on networks. In: The 2014 ACM international conference on Measurement and modeling of computer systems, (pp. 289\u2013300)","DOI":"10.1145\/2591971.2591989"},{"key":"6457_CR13","doi-asserted-by":"publisher","unstructured":"Carlsson, E., Dubhashi, D., & Johansson, F.D. (2021). Thompson sampling for bandits with clustered arms. In: Zhou ZH (ed) Proceedings of the thirtieth international joint conference on artificial intelligence, IJCAI-21, International joint conferences on artificial intelligence organization, (pp. 2212\u20132218). https:\/\/doi.org\/10.24963\/ijcai.2021\/305,main Track","DOI":"10.24963\/ijcai.2021\/305,"},{"key":"6457_CR14","unstructured":"Caron, S., Kveton, B., Lelarge, M., & Bhagat, S. (2012). Leveraging side observations in stochastic bandits. arXiv preprint arXiv:1210.4839"},{"key":"6457_CR15","unstructured":"Cesa-Bianchi, N., Gentile, C., & Zappella, G. (2013). A gang of bandits. Advances in Neural Information Processing Systems 26"},{"key":"6457_CR16","unstructured":"Chu, W., Li, L., Reyzin, L., & Schapire, R. (2011). Contextual bandits with linear payoff functions. In: Proceedings of the fourteenth international conference on artificial intelligence and statistics, (pp. 208\u2013214)."},{"key":"6457_CR17","unstructured":"Combes, R., Magureanu, S., & Proutiere, A. (2017). Minimal exploration in structured stochastic bandits. In: Advances in Neural Information Processing Systems, (pp. 1763\u20131771)"},{"key":"6457_CR18","volume-title":"Elements of information theory","author":"TM Cover","year":"1999","unstructured":"Cover, T. M. (1999). Elements of information theory. John Wiley & Sons."},{"issue":"5","key":"6457_CR19","doi-asserted-by":"publisher","first-page":"1466","DOI":"10.1109\/TNET.2011.2181864","volume":"20","author":"Y Gai","year":"2012","unstructured":"Gai, Y., Krishnamachari, B., & Jain, R. (2012). Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE\/ACM Transactions on Networking, 20(5), 1466\u20131478.","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"6457_CR20","unstructured":"Garivier, A., & Capp\u00e9, O. (2011). The kl-ucb algorithm for bounded stochastic bandits and beyond. In: Proceedings of the 24th annual conference on learning theory, (pp. 359\u2013376)."},{"key":"6457_CR21","unstructured":"Gentile, C., Li, S., & Zappella, G. (2014). Online clustering of bandits. In: International conference on machine learning, PMLR, pp 757\u2013765"},{"key":"6457_CR22","unstructured":"Gentile, C., Li, S., Kar, P., Karatzoglou, A., Zappella, G., & Etrue, E. (2017). On context-dependent clustering of bandits. In: International conference on machine learning, PMLR, (pp. 1253\u20131262)."},{"key":"6457_CR23","doi-asserted-by":"publisher","DOI":"10.1002\/9780470980033","volume-title":"Multi-armed bandit allocation indices","author":"J Gittins","year":"2011","unstructured":"Gittins, J., Glazebrook, K., & Weber, R. (2011). Multi-armed bandit allocation indices. John Wiley & Sons."},{"key":"6457_CR24","doi-asserted-by":"crossref","unstructured":"G\u00f6tze, F., Sambale, H., & Sinulis, A. (2019). Higher order concentration for functions of weakly dependent random variables","DOI":"10.1214\/19-EJP338"},{"key":"6457_CR25","unstructured":"Gupta, S., Joshi, G., & Yagan, O. (2018). Exploiting correlation in finite-armed structured bandits. arXiv preprint arXiv:1810.08164"},{"key":"6457_CR26","doi-asserted-by":"crossref","unstructured":"Gupta, S., Joshi, G., & Ya\u011fan, O. (2020). Correlated multi-armed bandits with a latent random source. ICASSP 2020\u20132020 IEEE international conference on acoustics (pp. 3572\u20133576). IEEE: Speech and Signal Processing (ICASSP).","DOI":"10.1109\/ICASSP40776.2020.9054429"},{"key":"6457_CR27","unstructured":"Kakade, S., & Tewari, A. (2008). Cmsc 35900 (spring 2008) learning theory, lecture notes: Massart\u2019s finite class lemma and growth function. https:\/\/ttic.uchicago.edu\/~tewari\/lectures\/lecture10.pdf"},{"key":"6457_CR28","unstructured":"Kontorovich, A. (2014). Concentration in unbounded metric spaces and algorithmic stability. In: International conference on machine learning, (pp. 28\u201336)"},{"issue":"1","key":"6457_CR29","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/0196-8858(85)90002-8","volume":"6","author":"TL Lai","year":"1985","unstructured":"Lai, T. L., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1), 4\u201322.","journal-title":"Advances in Applied Mathematics"},{"key":"6457_CR30","unstructured":"Langford, J., & Zhang, T. (2008). The epoch-greedy algorithm for multi-armed bandits with side information. In: Advances in neural information processing systems, (pp. 817\u2013824)."},{"key":"6457_CR31","unstructured":"Lattimore, T., & Munos, R. (2014). Bounded regret for finite-armed structured bandits. In: Advances in neural information processing systems, (pp. 550\u2013558)."},{"key":"6457_CR32","unstructured":"Lattimore, T., & Szepesvari, C. (2017). The end of optimism? an asymptotic analysis of finite-armed linear bandits. In: Artificial intelligence and statistics, PMLR, (pp. 728\u2013737)"},{"key":"6457_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401","volume-title":"Bandit algorithms","author":"T Lattimore","year":"2020","unstructured":"Lattimore, T., & Szepesv\u00e1ri, C. (2020). Bandit algorithms. Cambridge University Press."},{"key":"6457_CR34","unstructured":"Ledoux, M., & Talagrand, M. (2013). Probability in banach spaces: Isoperimetry and processes. Springer Science & Business Media"},{"key":"6457_CR35","doi-asserted-by":"crossref","unstructured":"Li, L., Chu, W., Langford, J., & Schapire, R.E. (2010). A contextual-bandit approach to personalized news article recommendation. In: Proceedings of the 19th international conference on World Wide Web, (pp. 661\u2013670).","DOI":"10.1145\/1772690.1772758"},{"key":"6457_CR36","unstructured":"Mannor, S., & Shamir, O. (2011). From bandits to experts: On the value of side-observations. In: Advances in neural information processing systems, (pp. 684\u2013692)"},{"issue":"10","key":"6457_CR37","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1016\/j.aml.2010.06.019","volume":"23","author":"Y Miao","year":"2010","unstructured":"Miao, Y. (2010). Concentration inequality of maximum likelihood estimator. Applied Mathematics Letters, 23(10), 1305\u20131309.","journal-title":"Applied Mathematics Letters"},{"key":"6457_CR38","doi-asserted-by":"crossref","unstructured":"Pandey, S., Chakrabarti, D., & Agarwal, D. (2007). Multi-armed bandit problems with dependent arms. In: Proceedings of the 24th international conference on machine learning, (pp. 721\u2013728).","DOI":"10.1145\/1273496.1273587"},{"key":"6457_CR39","volume-title":"A probability path","author":"S Resnick","year":"2019","unstructured":"Resnick, S. (2019). A probability path. Springer."},{"key":"6457_CR40","unstructured":"Rudin, W. (2006). Real and complex analysis. Tata McGraw-hill education."},{"issue":"2","key":"6457_CR41","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/moor.1100.0446","volume":"35","author":"P Rusmevichientong","year":"2010","unstructured":"Rusmevichientong, P., & Tsitsiklis, J. N. (2010). Linearly parameterized bandits. Mathematics of Operations Research, 35(2), 395\u2013411.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"6457_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000070","volume":"11","author":"DJ Russo","year":"2018","unstructured":"Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z., et al. (2018). A tutorial on thompson sampling. Foundations and Trends \u00aein Machine Learning, 11(1), 1\u201396.","journal-title":"Foundations and Trends \u00aein Machine Learning"},{"key":"6457_CR43","unstructured":"Vaswani, S., Schmidt, M., & Lakshmanan, L. (2017). Horde of Bandits using Gaussian Markov Random Fields. In: Singh A, Zhu J (eds) Proceedings of the 20th international conference on artificial intelligence and statistics, PMLR, proceedings of machine learning research, (vol\u00a054, pp. 690\u2013699). https:\/\/proceedings.mlr.press\/v54\/vaswani17a.html"},{"key":"6457_CR44","volume-title":"High-dimensional statistics: A non-asymptotic viewpoint","author":"MJ Wainwright","year":"2019","unstructured":"Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint (Vol. 48). Cambridge University Press."},{"key":"6457_CR45","unstructured":"Wang, Z., Zhou, R., & Shen, C. (2018a). Regional multi-armed bandits. In: International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, PMLR, Proceedings of Machine Learning Research, (vol.\u00a084, pp. 510\u2013518)"},{"key":"6457_CR46","doi-asserted-by":"crossref","unstructured":"Wang, Z., Zhou, R., & Shen, C. (2018b). Regional multi-armed bandits with partial informativeness. IEEE Transactions on Signal Processing, 66(21), 5705\u20135717.","DOI":"10.1109\/TSP.2018.2870383"},{"key":"6457_CR47","unstructured":"Yang, X., Liu, X., & Wei, H. (2022). Concentration inequalities of mle and robust mle. arXiv preprint arXiv:2210.09398"},{"key":"6457_CR48","unstructured":"Yang, Y. (2016). Ece598: Information-theoretic methods in high-dimensional statistics. http:\/\/www.stat.yale.edu\/~yw562\/teaching\/598\/lec14.pdf"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06457-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-023-06457-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06457-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T18:11:03Z","timestamp":1764267063000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-023-06457-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,20]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["6457"],"URL":"https:\/\/doi.org\/10.1007\/s10994-023-06457-z","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,20]]},"assertion":[{"value":"30 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The authors of this manuscript consent to its publication.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}