{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:59:15Z","timestamp":1762102755058,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001858","name":"VINNOVA","doi-asserted-by":"publisher","award":["2018-01937"],"award-info":[{"award-number":["2018-01937"]}],"id":[{"id":"10.13039\/501100001858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002835","name":"Chalmers University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002835","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study bottleneck identification in networks via extracting minimax paths. Many real-world networks have stochastic weights for which full knowledge is not available in advance. Therefore, we model this task as a combinatorial semi-bandit problem to which we apply a combinatorial version of Thompson Sampling and establish an upper bound on the corresponding Bayesian regret. Due to the computational intractability of the problem, we then devise an alternative problem formulation which approximates the original objective. Finally, we experimentally evaluate the performance of Thompson Sampling with the approximate formulation on real-world directed and undirected networks.<\/jats:p>","DOI":"10.1007\/s10994-022-06270-0","type":"journal-article","created":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T22:02:56Z","timestamp":1667944976000},"page":"131-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Online learning of network bottlenecks via minimax paths"],"prefix":"10.1007","volume":"112","author":[{"given":"Niklas","family":"\u00c5kerblom","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0766-0493","authenticated-orcid":false,"given":"Fazeleh Sadat","family":"Hoseini","sequence":"additional","affiliation":[]},{"given":"Morteza","family":"Haghir Chehreghani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,8]]},"reference":[{"unstructured":"Agrawal, S., Goyal, N. (2012) Analysis of thompson sampling for the multi-armed bandit problem. In: Mannor, S., Srebro, N., Williamson, R.C. (eds.) Proceedings of the 25th Annual Conference on Learning Theory. Proceedings of Machine Learning Research. vol. 23, pp. 39\u201313926. PMLR, Edinburgh, Scotland.","key":"6270_CR1"},{"doi-asserted-by":"crossref","unstructured":"\u00c5kerblom, N., Chen, Y., Haghir Chehreghani, M. (2020) An online learning framework for energy-efficient navigation of electric vehicles. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), pp. 2051\u20132057. 10.24963\/ijcai.2020\/284","key":"6270_CR2","DOI":"10.24963\/ijcai.2020\/284"},{"issue":"null","key":"6270_CR3","first-page":"397","volume":"3","author":"P Auer","year":"2003","unstructured":"Auer, P. (2003). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research., 3(null), 397\u2013422.","journal-title":"Journal of Machine Learning Research."},{"unstructured":"Batagelj, V., Mrvar, A. (2006) Pajek datasets. http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/. Accessed: 2021-09-08","key":"6270_CR4"},{"unstructured":"Beebe, N.H.F. (2002) Nelson H. F. Beebe\u2019s Bibliographies Page. http:\/\/www.math.utah.edu\/~beebe\/bibliographies.html. Accessed: 2021-09-08","key":"6270_CR5"},{"issue":"2","key":"6270_CR6","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1287\/trsc.21.2.115","volume":"21","author":"O Berman","year":"1987","unstructured":"Berman, O., & Handler, G. Y. (1987). Optimal minimax path of a single service unit on a network to nonservice destinations. Transportation Science, 21(2), 115\u2013122. https:\/\/doi.org\/10.1287\/trsc.21.2.115","journal-title":"Transportation Science"},{"issue":"5","key":"6270_CR7","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1016\/j.jcss.2012.01.001.JCSS","volume":"78","author":"N Cesa-Bianchi","year":"2012","unstructured":"Cesa-Bianchi, N., & Lugosi, G. (2012). Combinatorial bandits. Journal of Computer and System Sciences, 78(5), 1404\u20131422. https:\/\/doi.org\/10.1016\/j.jcss.2012.01.001.JCSS","journal-title":"Journal of Computer and System Sciences"},{"key":"6270_CR8","volume-title":"Advances in neural information processing systems","author":"O Chapelle","year":"2011","unstructured":"Chapelle, O., & Li, L. (2011). An empirical evaluation of thompson sampling. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, & K. Q. Weinberger (Eds.), Advances in neural information processing systems. London: Springer."},{"unstructured":"Chen, W., Hu, W., Li, F., Li, J., Liu, Y., Lu, P. (2016) Combinatorial multi-armed bandit with general reward functions. In: Lee, D, Sugiyama, M, Luxburg, U, Guyon, I, Garnett, R (eds) Advances in Neural Information Processing Systems. p 29","key":"6270_CR9"},{"unstructured":"Chen, W., Wang, Y., Yuan, Y. (2013) Combinatorial multi-armed bandit: General framework and applications. In: Dasgupta, S., McAllester, D. (eds.) Proceedings of the 30th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 28, pp. 151\u2013159. Atlanta, Georgia, USA","key":"6270_CR10"},{"issue":"2","key":"6270_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1287\/opre.9.2.145","volume":"9","author":"CE Clark","year":"1961","unstructured":"Clark, C. E. (1961). The greatest of a finite set of random variables. Operations Research, 9(2), 145\u2013162. https:\/\/doi.org\/10.1287\/opre.9.2.145","journal-title":"Operations Research"},{"unstructured":"DasGupta, A. (2021) A Formula for the Expected Value of the Maximum of Three Independent Normals and a Sparse High Dimensional Case. https:\/\/www.stat.purdue.edu\/~dasgupta\/orderstat.pdf. Accessed: 2021-09-07 (n.d.)","key":"6270_CR12"},{"issue":"1","key":"6270_CR13","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/bf01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269\u2013271. https:\/\/doi.org\/10.1007\/bf01386390","journal-title":"Numerische mathematik"},{"unstructured":"Du, Y., Kuroki, Y., Chen, W. (2021) Combinatorial Pure Exploration with Bottleneck Reward Function. arXiv. 1048550\/ARXIV.2102.12094","key":"6270_CR14"},{"issue":"3","key":"6270_CR15","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal ACM, 34(3), 596\u2013615. https:\/\/doi.org\/10.1145\/28869.28874","journal-title":"Journal ACM"},{"issue":"5","key":"6270_CR16","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. https:\/\/doi.org\/10.1109\/TNET.2011.2181864","journal-title":"IEEE\/ACM Transactions on Networking"},{"unstructured":"Graepel, T., Candela, J.Q.n., Borchert, T., Herbrich, R. (2010) Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft\u2019s bing search engine. In: Proceedings of the 27th International Conference on International Conference on Machine Learning. ICML\u201910, pp. 13\u201320. Omnipress, Madison, WI, USA","key":"6270_CR17"},{"issue":"11","key":"6270_CR18","doi-asserted-by":"publisher","first-page":"2063","DOI":"10.1007\/s10994-020-05886-4","volume":"109","author":"M Haghir Chehreghani","year":"2020","unstructured":"Haghir Chehreghani, M. (2020). Unsupervised representation learning with minimax distance measures. Machine Learning, 109(11), 2063\u20132097. https:\/\/doi.org\/10.1007\/s10994-020-05886-4","journal-title":"Machine Learning"},{"unstructured":"Handcock, M.S., Hunter, D., Butts, C.T., M., G.S., Morris, M. (2003) Statnet: An R package for the Statistical Modeling of Social Networks. http:\/\/www.csde.washington.edu\/statnet. Accessed: 2021-09-08","key":"6270_CR19"},{"key":"6270_CR20","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-48782-8_9","volume-title":"Multiple criteria decision making theory and application","author":"P Hansen","year":"1980","unstructured":"Hansen, P. (1980). Bicriterion path problems. In G. Fandel & T. Gal (Eds.), Multiple criteria decision making theory and application (pp. 109\u2013127). Berlin: Springer."},{"issue":"6","key":"6270_CR21","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1002\/(SICI)1098-2337(1999)25:6<409::AID-AB2>3.0.CO;2-0","volume":"25","author":"DA Hennessy","year":"1999","unstructured":"Hennessy, D. A., & Wiesenthal, D. L. (1999). Traffic congestion, driver stress, and driver aggression. Aggressive Behavior, 25(6), 409\u2013423. https:\/\/doi.org\/10.1002\/(SICI)1098-2337(1999)25:6<409::AID-AB2>3.0.CO;2-0","journal-title":"Aggressive Behavior"},{"issue":"2","key":"6270_CR22","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s11123-013-0381-8","volume":"43","author":"WC Horrace","year":"2015","unstructured":"Horrace, W. C. (2015). Moments of the truncated normal distribution. Journal of Productivity Analysis, 43(2), 133\u2013138. https:\/\/doi.org\/10.1007\/s11123-013-0381-8","journal-title":"Journal of Productivity Analysis"},{"key":"6270_CR23","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1287\/opre.9.6.898","volume":"9","author":"TC Hu","year":"1961","unstructured":"Hu, T. C. (1961). The maximum capacity route problem. Operations Research, 9, 898\u2013900. https:\/\/doi.org\/10.1287\/opre.9.6.898","journal-title":"Operations Research"},{"unstructured":"Jones, B. (2002) Computational geometry database. http:\/\/jeffe.cs.illinois.edu\/compgeom\/biblios.html. Accessed: 2021-09-08","key":"6270_CR24"},{"unstructured":"Kaufmann, E., Cappe, O., Garivier, A. (2012) On bayesian upper confidence bounds for bandit problems. In: Lawrence, N.D., Girolami, M. (eds.) Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 22, pp. 592\u2013600. La Palma, Canary Islands","key":"6270_CR25"},{"doi-asserted-by":"crossref","unstructured":"Kaufmann, E., Korda, N., Munos, R. (2012) Thompson sampling: An asymptotically optimal finite-time analysis. In: Algorithmic Learning Theory - 23rd International Conference, ALT, pp. 199\u2013213. 10.1007\/978-3-642-34106-9_18","key":"6270_CR26","DOI":"10.1007\/978-3-642-34106-9_18"},{"doi-asserted-by":"crossref","unstructured":"Kim, K.-H., Choi, S. (2007) Neighbor search with global geometry: A minimax message passing algorithm. In: Proceedings of the 24th International Conference on Machine Learning. ICML \u201907, pp. 401\u2013408, New York, NY, USA. 10.1145\/1273496.1273547","key":"6270_CR27","DOI":"10.1145\/1273496.1273547"},{"unstructured":"Kveton, B., Wen, Z., Ashkan, A., Szepesvari, C. (2015) Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits. In: Lebanon, G., Vishwanathan, S.V.N. (eds.) Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 38, pp. 535\u2013543. San Diego, California, USA","key":"6270_CR28"},{"issue":"1","key":"6270_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. https:\/\/doi.org\/10.1016\/0196-8858(85)90002-8","journal-title":"Advances in Applied Mathematics"},{"unstructured":"Lo, C. (2020) Improving hardware design reuse through design-space exploration. PhD thesis, University of Toronto (Canada)","key":"6270_CR30"},{"unstructured":"Liu, K., Zhao, Q. (2012) Adaptive shortest-path routing under unknown and stochastically varying link states. In: 2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt). pp. 232\u2013237.","key":"6270_CR31"},{"doi-asserted-by":"crossref","unstructured":"Nuara, A., Trovo, F., Gatti, N., Restelli, M. (2018) A combinatorial-bandit algorithm for the online joint bid\/budget optimization of pay-per-click advertising campaigns. In: Thirty-Second AAAI Conference on Artificial Intelligence. 10.1609\/aaai.v32i1.11888","key":"6270_CR32","DOI":"10.1609\/aaai.v32i1.11888"},{"unstructured":"OpenStreetMap contributors (2017) Planet dump retrieved from. www.openstreetmap.org. Accessed: 2021-09-08","key":"6270_CR33"},{"unstructured":"Orabona, F., Pal, D. (2015) Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice. arXiv. 1048550\/ARXIV.1511.02176","key":"6270_CR34"},{"key":"6270_CR35","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.5.733","author":"M Pollack","year":"1960","unstructured":"Pollack, M. (1960). The maximum capacity through a network. Operations Research. https:\/\/doi.org\/10.1287\/opre.8.5.733","journal-title":"Operations Research"},{"issue":"6","key":"6270_CR36","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim, R. C. (1957). Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6), 1389\u20131401. https:\/\/doi.org\/10.1002\/j.1538-7305.1957.tb01515.x","journal-title":"The Bell System Technical Journal"},{"unstructured":"Riquelme, C., Tucker, G., Snoek, J. (2018) Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In: International Conference on Learning Representations.","key":"6270_CR37"},{"issue":"4","key":"6270_CR38","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1287\/moor.2014.0650","volume":"39","author":"D Russo","year":"2014","unstructured":"Russo, D., & Van Roy, B. (2014). Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4), 1221\u20131243. https:\/\/doi.org\/10.1287\/moor.2014.0650","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"6270_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000070","volume":"11","author":"DJ Russo","year":"2018","unstructured":"Russo, D. J., Roy, B. V., Kazerouni, A., Osband, I., & Wen, Z. (2018). A tutorial on thompson sampling. Foundations and Trends in Machine Learning., 11(1), 1\u201396. https:\/\/doi.org\/10.1561\/2200000070","journal-title":"Foundations and Trends in Machine Learning."},{"issue":"1","key":"6270_CR40","doi-asserted-by":"publisher","first-page":"83","DOI":"10.3141\/2196-09","volume":"2196","author":"R Seshadri","year":"2010","unstructured":"Seshadri, R., & Srinivasan, K. K. (2010). Algorithm for determining most reliable travel time path on network with normally distributed and correlated link travel times. Transportation research record, 2196(1), 83\u201392. https:\/\/doi.org\/10.3141\/2196-09","journal-title":"Transportation research record"},{"doi-asserted-by":"publisher","unstructured":"Shacham, N. (1992). Multicast routing of hierarchical data. In: [Conference Record] SUPERCOMM\/ICC 92 Discovering a New World of Communications, pp. 1217\u201312213. doi: https:\/\/doi.org\/10.1109\/ICC.1992.268047","key":"6270_CR41","DOI":"10.1109\/ICC.1992.268047"},{"issue":"1\u20132","key":"6270_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000068","volume":"12","author":"A Slivkins","year":"2019","unstructured":"Slivkins, A. (2019). Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1\u20132), 1\u2013286. https:\/\/doi.org\/10.1561\/2200000068","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"3\u20134","key":"6270_CR43","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2307\/2332286","volume":"25","author":"WR Thompson","year":"1933","unstructured":"Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3\u20134), 285\u2013294. https:\/\/doi.org\/10.2307\/2332286","journal-title":"Biometrika"},{"unstructured":"Wang, S., Chen, W. (2018) Thompson sampling for combinatorial semi-bandits. In: Dy, J., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research. vol. 80, pp. 5114\u20135122.","key":"6270_CR44"},{"doi-asserted-by":"crossref","unstructured":"Zou, Z., Proutiere, A., Johansson, M. (2014) Online shortest path routing: The value of information. In: 2014 American Control Conference. pp. 2142\u20132147. 10.1109\/ACC.2014.6859133","key":"6270_CR45","DOI":"10.1109\/ACC.2014.6859133"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06270-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06270-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06270-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T01:06:20Z","timestamp":1674349580000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06270-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,8]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["6270"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06270-0","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2022,11,8]]},"assertion":[{"value":"10 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2022","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing ESM file added to article","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Contact the authors for access to the code.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"The detailed proof of Theorem  is provided in Online Resource 1.","order":7,"name":"Ethics","group":{"name":"EthicsHeading","label":"Supplementary information"}}]}}