{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T13:26:17Z","timestamp":1708608377479},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T00:00:00Z","timestamp":1626393600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T00:00:00Z","timestamp":1626393600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s11704-020-9519-9","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T13:03:06Z","timestamp":1626440586000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization"],"prefix":"10.1007","volume":"15","author":[{"given":"Feidiao","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jialin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,16]]},"reference":[{"issue":"10","key":"9519_CR1","first-page":"2369","volume":"8","author":"A Gy\u00f6rgy","year":"2007","unstructured":"Gy\u00f6rgy A, Linder T, Lugosi G, Ottucs\u00e1k G. The on-line shortest path problem under partial monitoring. Journal of Machine Learning Research, 2007, 8(10): 2369\u20132403","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"9519_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.2013.0598","volume":"39","author":"J Y Audibert","year":"2013","unstructured":"Audibert J Y, Bubeck S, Lugosi G. Regret in online combinatorial optimization. Mathematics of Operations Research, 2013, 39(1): 31\u201345","journal-title":"Mathematics of Operations Research"},{"key":"9519_CR3","doi-asserted-by":"crossref","unstructured":"Neu G, Bart\u00f3k G. An efficient algorithm for learning with semi-bandit feedback. In: Prodeedings of International Conference on Algorithmic Learning Theory. 2013, 234\u2013248","DOI":"10.1007\/978-3-642-40935-6_17"},{"issue":"154","key":"9519_CR4","first-page":"1","volume":"17","author":"G Neu","year":"2016","unstructured":"Neu G, Bart\u00f3k G. Importance weighting without importance weights: an efficient algorithm for combinatorial semi-bandits. Journal of Machine Learning Research, 2016, 17(154): 1\u201321","journal-title":"Journal of Machine Learning Research"},{"issue":"3","key":"9519_CR5","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.jcss.2004.10.016","volume":"71","author":"A Kalai","year":"2005","unstructured":"Kalai A, Vempala S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 2005, 71(3): 297\u2013307","journal-title":"Journal of Computer and System Sciences"},{"issue":"11","key":"9519_CR6","first-page":"1","volume":"58","author":"W Wang","year":"2015","unstructured":"Wang W, Zhou Z H. Crowdsourcing label quality: a theoretical analysis. Science China Information Sciences, 2015, 58(11): 1\u201312","journal-title":"Science China Information Sciences"},{"issue":"3\/4","key":"9519_CR7","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2307\/2332286","volume":"25","author":"W Thompson","year":"1933","unstructured":"Thompson W. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933, 25(3\/4): 285\u2013294","journal-title":"Biometrika"},{"issue":"5","key":"9519_CR8","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1090\/S0002-9904-1952-09620-8","volume":"58","author":"H Robbins","year":"1952","unstructured":"Robbins H. Some aspects of the sequential design of experiments. Bulletin of the America Mathematical Society, 1952, 58(5): 527\u2013535","journal-title":"Bulletin of the America Mathematical Society"},{"issue":"2\u20133","key":"9519_CR9","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1013689704352","volume":"47","author":"P Auer","year":"2002","unstructured":"Auer P, Cesa-Bianchi N, Fischer P. Finite-time analysis of the multi-armed bandit problem. Machine Learning, 2002, 47(2\u20133): 235\u2013256","journal-title":"Machine Learning"},{"issue":"1","key":"9519_CR10","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539701398375","volume":"32","author":"P Auer","year":"2002","unstructured":"Auer P, Cesa-Bianchi N, Freund Y, Schapire R. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 2002, 32(1): 48\u201377","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"9519_CR11","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. Combinatorial network optimization with unknown variables: multi-armed bandits with linear rewards and individual observations. IEEE\/ACM Transactions on Networking, 2012, 20(5): 1466\u20131478","journal-title":"IEEE\/ACM Transactions on Networking"},{"issue":"50","key":"9519_CR12","first-page":"1","volume":"17","author":"W Chen","year":"2016","unstructured":"Chen W, Wang Y, Yuan Y, Wang Q. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research, 2016, 17(50): 1\u201333","journal-title":"Journal of Machine Learning Research"},{"key":"9519_CR13","unstructured":"Kveton B, Wen Z, Ashkan A, Szepesvari C. Tight regret bounds for stochastic combinatorial semi-bandits. In: Proceedings of International Conference on Artificial Intelligence and Statistics. 2015, 535\u2013543"},{"key":"9519_CR14","unstructured":"Sankararaman K A, Slivkins A. Combinatorial semi-bandits with knapsacks. In: Proceedings of International Conference on Artificial Intelligence and Statistics. 2018, 1760\u20131770"},{"key":"9519_CR15","unstructured":"Kveton B, Wen Z, Ashkan A, Eydgahi H, Eriksson B. Matroid bandits: fast combinatorial optimization with learning. In: Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence. 2014, 420\u2013429"},{"issue":"5","key":"9519_CR16","first-page":"773","volume":"4","author":"E Takimoto","year":"2003","unstructured":"Takimoto E, Warmuth M. Path kernels and multiplicative updates. Journal of Machine Learning Research, 2003, 4(5): 773\u2013818","journal-title":"Journal of Machine Learning Research"},{"key":"9519_CR17","doi-asserted-by":"crossref","unstructured":"Awerbuch B, Kleinberg R. Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing. 2004, 45\u201353","DOI":"10.1145\/1007352.1007367"},{"key":"9519_CR18","doi-asserted-by":"crossref","unstructured":"McMahan H B, Blum A. Online geometric optimization in the bandit setting against an adaptive adversary. In: Proceedings of International Conference on Computational Learning Theory. 2004, 109\u2013123","DOI":"10.1007\/978-3-540-27819-1_8"},{"key":"9519_CR19","unstructured":"Dani V, Kakade S, Hayes T. The price of bandit information for online optimization. In: Proceedings of the 20th International Conference on Neural Information Processing Systems. 2007, 345\u2013352"},{"key":"9519_CR20","unstructured":"Abernethy J, Hazan E, Rakhlin A. Competing in the dark: an efficient algorithm for bandit linear optimization. In: Proceedings of the 21st Annual Conference on Learning Theory. 2008, 263\u2013273"},{"issue":"5","key":"9519_CR21","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1016\/j.jcss.2012.01.001","volume":"78","author":"N Cesa-Bianchi","year":"2012","unstructured":"Cesa-Bianchi N, Lugosi G. Combinatorial bandits. Journal of Computer and System Sciences, 2012, 78(5): 1404\u20131422","journal-title":"Journal of Computer and System Sciences"},{"key":"9519_CR22","unstructured":"Bubeck S, Cesa-Bianchi N, Kakade S. Towards minimax policies for online linear optimization with bandit feedback. In: Proceedings of Annual Conference on Learning Theory. 2012"},{"key":"9519_CR23","unstructured":"Combes R, Talebi M, Proutiere A, Lelarge M. Combinatorial bandits revisited. In: Proceedings of the 29th Annual Conference on Neural Information Processing Systems. 2015, 2116\u20132124"},{"key":"9519_CR24","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/BFb0029575","volume-title":"Online Algorithms","author":"A Blum","year":"1998","unstructured":"Blum A. On-line algorithms in machine learning. In: Fiat A, Woeginger G L, eds. Online Algorithms. Berlin: Springer, 1998, 306\u2013325"},{"key":"9519_CR25","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1006\/game.1999.0740","volume":"29","author":"D Foster","year":"1999","unstructured":"Foster D, Vohra R. Regret in the on-line decision problem. Games and Economic Behavior, 1999, 29: 7\u201335","journal-title":"Games and Economic Behavior"},{"key":"9519_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, Learning, and Games","author":"N Cesa-Bianchi","year":"2006","unstructured":"Cesa-Bianchi N, Lugosi G. Prediction, Learning, and Games. New York: Cambridge University Press, 2006"},{"key":"9519_CR27","first-page":"97","volume":"3","author":"J Hannan","year":"1957","unstructured":"Hannan J. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 1957, 3: 97\u2013139","journal-title":"Contributions to the Theory of Games"},{"key":"9519_CR28","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani V. Approximation Algorithms. Berlin: Springer, 2001"},{"key":"9519_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D Williamson","year":"2011","unstructured":"Williamson D, Shmoys A. The Design of Approximation Algorithms. New York: Cambridge University Press, 2011"},{"key":"9519_CR30","doi-asserted-by":"crossref","unstructured":"Poland J. FPL analysis for adaptive bandits. In: Proceedings of International Symposium on Stochastic Algorithms. 2005, 58\u201369","DOI":"10.1007\/11571155_7"},{"issue":"3","key":"9519_CR31","doi-asserted-by":"publisher","first-page":"1088","DOI":"10.1137\/070701704","volume":"39","author":"S Kakade","year":"2009","unstructured":"Kakade S, Kalai A, Ligett K. Playing games with approximation algorithms. SIAM Journal on Computing, 2009, 39(3): 1088\u20131106","journal-title":"SIAM Journal on Computing"},{"key":"9519_CR32","unstructured":"Garber D. Efficient online linear optimization with approximation algorithms. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 627\u2013635"},{"key":"9519_CR33","unstructured":"Hazan E, Hu W, Li Y, Li Z. Online improper learning with an approximation oracle. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, 5652\u20135660"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-020-9519-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-020-9519-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-020-9519-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T21:54:56Z","timestamp":1668894896000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-020-9519-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,16]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["9519"],"URL":"https:\/\/doi.org\/10.1007\/s11704-020-9519-9","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,16]]},"assertion":[{"value":"25 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"155404"}}