{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T08:25:49Z","timestamp":1774599949579,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-2148183"],"award-info":[{"award-number":["CNS-2148183"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ONR","award":["N00014-20-1-2119"],"award-info":[{"award-number":["N00014-20-1-2119"]}]},{"name":"NSF","award":["CNS-2148128"],"award-info":[{"award-number":["CNS-2148128"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>\n            We study the optimal control problem in stochastic queueing networks with a set of job dispatchers connected to a set of parallel servers with queues. Jobs arrive at the dispatchers and get routed to the servers following some routing policy. The arrival processes of jobs and the service processes of servers are stochastic with unknown arrival rates and service rates. Upon the completion of each job from dispatcher\n            <jats:italic>\n              u\n              <jats:sub>n<\/jats:sub>\n            <\/jats:italic>\n            at server\n            <jats:italic>\n              s\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            , a random utility whose mean is unknown is obtained. We seek to design a control policy that makes routing decisions at the dispatchers and scheduling decisions at the servers to maximize the total utility obtained by the end of a finite time horizon\n            <jats:italic>T<\/jats:italic>\n            . The performance of policies is measured by regret, which is defined as the difference in total expected utility with respect to the optimal dynamic policy that has access to arrival rates, service rates and underlying utilities.\n          <\/jats:p>\n          <jats:p>\n            We first show that the expected utility of the optimal dynamic policy is upper bounded by\n            <jats:italic>T<\/jats:italic>\n            times the solution to a static linear program, where the optimization variables correspond to rates of jobs from dispatchers to servers and the feasibility region is parameterized by arrival rates and service rates. We next propose a policy for the optimal control problem that is an integration of a learning algorithm and a control policy. The learning algorithm seeks to learn the optimal extreme point solution to the static linear program based on the information available in the optimal control problem. The control policy, a mixture of priority-based and Joint-the-Shortest-Queue routing at the dispatchers and priority-based scheduling at the servers, makes decisions based on the graphical structure induced by the extreme point solutions provided by the learning algorithm. We prove that our policy achieves logarithmic regret whereas application of existing techniques to the optimal control problem would lead to \u03a9(\u221a\n            <jats:italic>T<\/jats:italic>\n            )-regret. The theoretical analysis is further complemented with simulations to evaluate the empirical performance of our policy.\n          <\/jats:p>","DOI":"10.1145\/3570619","type":"journal-article","created":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T20:20:10Z","timestamp":1670530810000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Joint Learning and Control in Stochastic Queueing Networks with Unknown Utilities"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4425-3881","authenticated-orcid":false,"given":"Xinzhe","family":"Fu","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8238-8130","authenticated-orcid":false,"given":"Eytan","family":"Modiano","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Queueing system topologies with limited flexibility.\" in Proceedings of the ACM SIGMETRICS, pp: 167--178","author":"Tsitsiklis J.","year":"2013","unstructured":"J. Tsitsiklis and K. Xu . \" Queueing system topologies with limited flexibility.\" in Proceedings of the ACM SIGMETRICS, pp: 167--178 . 2013 . J. Tsitsiklis and K. Xu. \"Queueing system topologies with limited flexibility.\" in Proceedings of the ACM SIGMETRICS, pp: 167--178. 2013."},{"key":"e_1_2_1_2_1","volume-title":"Optimal load balancing in bipartite graphs.\" arXiv preprint arXiv:2008.08830","author":"Weng W.","year":"2020","unstructured":"W. Weng , X. Zhou , and R. Srikant . \" Optimal load balancing in bipartite graphs.\" arXiv preprint arXiv:2008.08830 ( 2020 ). W. Weng, X. Zhou, and R. Srikant. \"Optimal load balancing in bipartite graphs.\" arXiv preprint arXiv:2008.08830 (2020)."},{"key":"e_1_2_1_3_1","volume-title":"State dependent control of closed queueing networks.\" in ACM SIGMETRICS Performance Evaluation Review","author":"Banerjee S.","unstructured":"S. Banerjee , Y. Kanoria , and P. Qian . \" State dependent control of closed queueing networks.\" in ACM SIGMETRICS Performance Evaluation Review , Vol. 46 , No. 1, pp: 2--4, 2018. S. Banerjee, Y. Kanoria, and P. Qian. \"State dependent control of closed queueing networks.\" in ACM SIGMETRICS Performance Evaluation Review, Vol. 46, No. 1, pp: 2--4, 2018."},{"key":"e_1_2_1_4_1","volume-title":"Optimal power allocation in server farms.\" in ACM SIGMETRICS Performance Evaluation Review","author":"Gandhi A.","unstructured":"A. Gandhi , M. Harchol-Balter , R. Das , and C. Lefurgy . \" Optimal power allocation in server farms.\" in ACM SIGMETRICS Performance Evaluation Review , Vol. 37 , No. 1, pp: 157--168, 2009. A. Gandhi, M. Harchol-Balter, R. Das, and C. Lefurgy. \"Optimal power allocation in server farms.\" in ACM SIGMETRICS Performance Evaluation Review, Vol. 37, No. 1, pp: 157--168, 2009."},{"key":"e_1_2_1_5_1","volume-title":"Online convex optimization with stochastic constraints.\" in Advances in Neural Information Processing Systems","author":"Yu H.","year":"2017","unstructured":"H. Yu , M. Neely , and X. Wei . \" Online convex optimization with stochastic constraints.\" in Advances in Neural Information Processing Systems , 2017 . H. Yu, M. Neely, and X. Wei. \"Online convex optimization with stochastic constraints.\" in Advances in Neural Information Processing Systems, 2017."},{"key":"e_1_2_1_6_1","volume-title":"pp: 107--194","author":"Shalev-Shwartz S.","year":"2012","unstructured":"S. Shalev-Shwartz , \" Online learning and online convex optimization.\" in Foundations and Trends in Machine Learning , Vol. 4, No. 2 , pp: 107--194 , 2012 . S. Shalev-Shwartz, \"Online learning and online convex optimization.\" in Foundations and Trends in Machine Learning, Vol. 4, No. 2, pp: 107--194, 2012."},{"key":"e_1_2_1_7_1","volume-title":"Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.\" in Conference on Learning Theory, pp: 28--40","author":"Agarwal A.","year":"2010","unstructured":"A. Agarwal , O. Dekel , and L. Xiao . \" Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.\" in Conference on Learning Theory, pp: 28--40 , 2010 . A. Agarwal, O. Dekel, and L. Xiao. \"Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.\" in Conference on Learning Theory, pp: 28--40, 2010."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2018.2839563"},{"issue":"1","key":"e_1_2_1_9_1","first-page":"213","volume":"23","author":"Agarwal A.","year":"2013","unstructured":"A. Agarwal , D. P. Foster , D. Hsu , S. M. Kakade , and A. Rakhlin . \"Stochastic convex optimization with bandit feedback.\" in SIAM Journal on Optimization , Vol. 23 , No. 1 , pp: 213 -- 240 , 2013 . A. Agarwal, D. P. Foster, D. Hsu, S. M. Kakade, and A. Rakhlin. \"Stochastic convex optimization with bandit feedback.\" in SIAM Journal on Optimization, Vol. 23, No. 1, pp: 213--240, 2013.","journal-title":"\"Stochastic convex optimization with bandit feedback.\" in SIAM Journal on Optimization"},{"key":"e_1_2_1_10_1","volume-title":"Competing in the dark: An efficient algorithm for bandit linear optimization","author":"Abernethy J.","year":"2009","unstructured":"J. Abernethy , E. Hazan , and A. Rakhlin . \" Competing in the dark: An efficient algorithm for bandit linear optimization .\" 2009 . J. Abernethy, E. Hazan, and A. Rakhlin. \"Competing in the dark: An efficient algorithm for bandit linear optimization.\" 2009."},{"key":"e_1_2_1_11_1","volume-title":"Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.\" in Machine Learning","author":"Bubeck S.","unstructured":"S. Bubeck and N. Cesa-Bianchi , \" Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.\" in Machine Learning , Vol. 5 , No. 1, pp: 1--122, 2012. S. Bubeck and N. Cesa-Bianchi, \"Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.\" in Machine Learning, Vol. 5, No. 1, pp: 1--122, 2012."},{"key":"e_1_2_1_12_1","volume-title":"Logarithmic regret for reinforcement learning with linear function approximation.\" in International Conference on Machine Learning, pp: 4171--4180","author":"He J.","year":"2021","unstructured":"J. He , D. Zhou , and Q. Gu . \" Logarithmic regret for reinforcement learning with linear function approximation.\" in International Conference on Machine Learning, pp: 4171--4180 , 2021 . J. He, D. Zhou, and Q. Gu. \"Logarithmic regret for reinforcement learning with linear function approximation.\" in International Conference on Machine Learning, pp: 4171--4180, 2021."},{"key":"e_1_2_1_13_1","volume-title":"Constrained upper confidence reinforcement learning.\" in Learning for Dynamics and Control, pp: 620--629","author":"Zheng L.","year":"2020","unstructured":"L. Zheng and L. Ratliff . \" Constrained upper confidence reinforcement learning.\" in Learning for Dynamics and Control, pp: 620--629 , 2020 . L. Zheng and L. Ratliff. \"Constrained upper confidence reinforcement learning.\" in Learning for Dynamics and Control, pp: 620--629, 2020."},{"key":"e_1_2_1_14_1","unstructured":"I. Osband and B. Van Roy. \"Near-optimal reinforcement learning in factored mdps.\" in Advances in Neural Information Processing Systems 2014.  I. Osband and B. Van Roy. \"Near-optimal reinforcement learning in factored mdps.\" in Advances in Neural Information Processing Systems 2014."},{"key":"e_1_2_1_15_1","volume-title":"Minimax regret bounds for reinforcement learning.\" in International Conference on Machine Learning, pp: 263--272","author":"Azar M.","year":"2017","unstructured":"M. Azar , I. Osband , and R. Munos . \" Minimax regret bounds for reinforcement learning.\" in International Conference on Machine Learning, pp: 263--272 , 2017 . M. Azar, I. Osband, and R. Munos. \"Minimax regret bounds for reinforcement learning.\" in International Conference on Machine Learning, pp: 263--272, 2017."},{"key":"e_1_2_1_16_1","volume-title":"Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.\" in International Conference on Machine Learning, pp: 10746--10756","author":"Yang L.","year":"2020","unstructured":"L. Yang and M. Wang . \" Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.\" in International Conference on Machine Learning, pp: 10746--10756 , 2020 . L. Yang and M. Wang. \"Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.\" in International Conference on Machine Learning, pp: 10746--10756, 2020."},{"key":"e_1_2_1_17_1","volume-title":"Conference on Learning Theory","author":"Dani V.","year":"2008","unstructured":"V. Dani , T. Hayes , and S. Kakade . \" Stochastic linear optimization under bandit feedback .\", in Conference on Learning Theory , 2008 . V. Dani, T. Hayes, and S. Kakade. \"Stochastic linear optimization under bandit feedback.\", in Conference on Learning Theory, 2008."},{"key":"e_1_2_1_18_1","volume-title":"Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic.\" in Proceedings of ACM SIGMETRICS, pp: 431--432","author":"Singh R.","year":"2015","unstructured":"R. Singh and A. Stolyar . \" Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic.\" in Proceedings of ACM SIGMETRICS, pp: 431--432 , 2015 . R. Singh and A. Stolyar. \"Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic.\" in Proceedings of ACM SIGMETRICS, pp: 431--432, 2015."},{"key":"e_1_2_1_19_1","volume-title":"pp: 1--211","author":"Neely M.","year":"2010","unstructured":"M. Neely . \" Stochastic network optimization with application to communication and queueing systems.\" in Synthesis Lectures on Communication Networks , Vol. 3, No. 1 , pp: 1--211 , 2010 . M. Neely. \"Stochastic network optimization with application to communication and queueing systems.\" in Synthesis Lectures on Communication Networks, Vol. 3, No. 1, pp: 1--211, 2010."},{"issue":"8","key":"e_1_2_1_20_1","first-page":"1452","volume":"24","author":"Lin X.","year":"2006","unstructured":"X. Lin , N. B. Shroff , and R. Srikant . \"A tutorial on cross-layer optimization in wireless networks.\" in IEEE Journal on Selected areas in Communications , Vol. 24 , No. 8 , pp: 1452 -- 1463 , 2006 . X. Lin, N. B. Shroff, and R. Srikant. \"A tutorial on cross-layer optimization in wireless networks.\" in IEEE Journal on Selected areas in Communications, Vol. 24, No. 8, pp: 1452--1463, 2006.","journal-title":"\"A tutorial on cross-layer optimization in wireless networks.\" in IEEE Journal on Selected areas in Communications"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3054854"},{"key":"e_1_2_1_22_1","volume-title":"Learning unknown service rates in queues: A multiarmed bandit approach.\" in Operations Research","author":"Krishnasamy S.","unstructured":"S. Krishnasamy , R. Sen , R. Johari , and S. Shakkottai . \" Learning unknown service rates in queues: A multiarmed bandit approach.\" in Operations Research , Vol. 69 , No. 1, pp: 315--330, 2021. S. Krishnasamy, R. Sen, R. Johari, and S. Shakkottai. \"Learning unknown service rates in queues: A multiarmed bandit approach.\" in Operations Research, Vol. 69, No. 1, pp: 315--330, 2021."},{"key":"e_1_2_1_23_1","first-page":"21","author":"Fu X.","year":"2021","unstructured":"X. Fu , and E. Modiano . \"Learning-NUM: Network Utility Maximization with Unknown Utility Functions and Queueing Delay.\" in Proceedings of ACM Mobihoc , pp. 21 -- 30 . 2021 . X. Fu, and E. Modiano. \"Learning-NUM: Network Utility Maximization with Unknown Utility Functions and Queueing Delay.\" in Proceedings of ACM Mobihoc, pp. 21--30. 2021.","journal-title":"\"Learning-NUM: Network Utility Maximization with Unknown Utility Functions and Queueing Delay.\" in Proceedings of ACM Mobihoc"},{"key":"e_1_2_1_24_1","volume-title":"Elastic job scheduling with unknown utility functions.\" in Performance Evaluation","author":"Fu X.","year":"2021","unstructured":"X. Fu , and E. Modiano . \" Elastic job scheduling with unknown utility functions.\" in Performance Evaluation , 2021 . X. Fu, and E. Modiano. \"Elastic job scheduling with unknown utility functions.\" in Performance Evaluation, 2021."},{"key":"e_1_2_1_25_1","volume-title":"The bayesian prophet: A low-regret framework for online decision making.\" in Management Science","author":"Vera A.","unstructured":"A. Vera and S. Banerjee . \" The bayesian prophet: A low-regret framework for online decision making.\" in Management Science , Vol. 67 , No. 3, pp: 1368--1391, 2021 A. Vera and S. Banerjee. \"The bayesian prophet: A low-regret framework for online decision making.\" in Management Science, Vol. 67, No. 3, pp: 1368--1391, 2021"},{"key":"e_1_2_1_26_1","volume-title":"Mechanism design for online resource allocation: A unified approach.\" in Proceedings of the ACM on Measurement and Analysis of Computing Systems","author":"Tan X.","unstructured":"X. Tan , B. Sun , A. Leon-Garcia , Y. Wu , and D. Tsang . \" Mechanism design for online resource allocation: A unified approach.\" in Proceedings of the ACM on Measurement and Analysis of Computing Systems , Vol. 4 , No. 2, pp: 1--46, 2020. X. Tan, B. Sun, A. Leon-Garcia, Y. Wu, and D. Tsang. \"Mechanism design for online resource allocation: A unified approach.\" in Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 4, No. 2, pp: 1--46, 2020."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1289"},{"key":"e_1_2_1_28_1","volume-title":"pp: 1489--1501","author":"Neely M.","year":"2006","unstructured":"M. Neely . \"Super-fast delay tradeoffs for utility optimal fair scheduling in wireless networks.\" in IEEE Journal on Selected Areas in Communications , Vol. 24, No. 8 , pp: 1489--1501 , 2006 . M. Neely. \"Super-fast delay tradeoffs for utility optimal fair scheduling in wireless networks.\" in IEEE Journal on Selected Areas in Communications, Vol. 24, No. 8, pp: 1489--1501, 2006."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/548834"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"V. Pesic and R. Williams. \"Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure decoupled workload matrix and some sufficient conditions for solvability of the Brownian control problem.\" in Stochastic Systems Vol. 6 No. 1 pp:  26--89 2016.  V. Pesic and R. Williams. \"Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure decoupled workload matrix and some sufficient conditions for solvability of the Brownian control problem.\" in Stochastic Systems Vol. 6 No. 1 pp: 26--89 2016.","DOI":"10.1287\/14-SSY163"},{"key":"e_1_2_1_31_1","volume-title":"Heavy traffic resource pooling in parallel-server systems.\" in Queueing systems","author":"Harrison J. M.","unstructured":"J. M. Harrison and M. J. L\u00f3pez . \" Heavy traffic resource pooling in parallel-server systems.\" in Queueing systems , Vol. 33 , No. 4, pp: 339--368, 1999. J. M. Harrison and M. J. L\u00f3pez. \"Heavy traffic resource pooling in parallel-server systems.\" in Queueing systems, Vol. 33, No. 4, pp: 339--368, 1999."},{"key":"e_1_2_1_32_1","volume-title":"pp: 157--325","author":"Hazan E.","year":"2016","unstructured":"E. Hazan . \" Introduction to online convex optimization.\" in Foundations and Trends in Optimization , Vol. 2, No. 3--4 , pp: 157--325 , 2016 . E. Hazan. \"Introduction to online convex optimization.\" in Foundations and Trends in Optimization, Vol. 2, No. 3--4, pp: 157--325, 2016."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570619","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570619","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570619","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:17Z","timestamp":1750178777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570619"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1145\/3570619"],"URL":"https:\/\/doi.org\/10.1145\/3570619","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2022-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}