{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T17:13:48Z","timestamp":1746551628147,"version":"3.30.2"},"reference-count":41,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T00:00:00Z","timestamp":1734393600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Research Foundation Singapore, A*STAR","award":["NRF2021-QEP2-02-P05"],"award-info":[{"award-number":["NRF2021-QEP2-02-P05"]}]},{"name":"National Research Foundation Singapore, DSO National Laboratories","award":["AISG2-RP-2020-016"],"award-info":[{"award-number":["AISG2-RP-2020-016"]}]},{"award":["PIESGP-AI-2020-01"],"award-info":[{"award-number":["PIESGP-AI-2020-01"]}]},{"name":"AME Programmatic Fund, A*STAR","award":["A20H6b0151"],"award-info":[{"award-number":["A20H6b0151"]}]},{"name":"Provost's Chair Professorship Grant","award":["RGEPPV2101"],"award-info":[{"award-number":["RGEPPV2101"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"As quantum processors advance, the emergence of large-scale decentralized systems involving interacting quantum-enabled agents is on the horizon. Recent research efforts have explored quantum versions of Nash and correlated equilibria as solution concepts of strategic quantum interactions, but these approaches did not directly connect to decentralized adaptive setups where agents possess limited information. This paper delves into the dynamics of quantum-enabled agents within decentralized systems that employ no-regret algorithms to update their behaviors over time. Specifically, we investigate two-player quantum zero-sum games and polymatrix quantum zero-sum games, showing that no-regret algorithms converge to separable quantum Nash equilibria in time-average. In the case of general multi-player quantum games, our work leads to a novel solution concept, that of the separable quantum coarse correlated equilibria (QCCE), as the convergent outcome of the time-averaged behavior no-regret algorithms, offering a natural solution concept for decentralized quantum systems. Finally, we show that computing QCCEs can be formulated as a semidefinite program and establish the existence of entangled (i.e., non-separable) QCCEs, which are unlearnable via the current paradigm of no-regret learning.<\/jats:p>","DOI":"10.22331\/q-2024-12-17-1569","type":"journal-article","created":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T14:46:01Z","timestamp":1734446761000},"page":"1569","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["No-Regret Learning and Equilibrium Computation in Quantum Games"],"prefix":"10.22331","volume":"8","author":[{"given":"Wayne","family":"Lin","sequence":"first","affiliation":[{"name":"Singapore University of Technology and Design, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georgios","family":"Piliouras","sequence":"additional","affiliation":[{"name":"Singapore University of Technology and Design, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryann","family":"Sim","sequence":"additional","affiliation":[{"name":"Singapore University of Technology and Design, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonios","family":"Varvitsiotis","sequence":"additional","affiliation":[{"name":"Singapore University of Technology and Design, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2024,12,17]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Gus Gutoski and John Watrous. ``Toward a general theory of quantum games''. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. Pages 565\u2013574. (2007).","DOI":"10.1145\/1250790.1250873"},{"key":"1","doi-asserted-by":"publisher","unstructured":"John Bostanci and John Watrous. ``Quantum game theory and the complexity of approximating quantum Nash equilibria''. Quantum 6, 882 (2022).","DOI":"10.22331\/q-2022-12-22-882"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Shengyu Zhang. ``Quantum strategic game theory''. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Pages 39\u201359. (2012).","DOI":"10.1145\/2090236.2090241"},{"key":"3","unstructured":"Jinshan Wu. ``A new mathematical representation of game theory, I'' (2004). arXiv:quant-ph\/0404159."},{"key":"4","doi-asserted-by":"publisher","unstructured":"Faisal Shah Khan, Neal Solmeyer, Radhakrishnan Balu, and Travis S Humble. ``Quantum games: a review of the history, current state, and interpretation''. Quantum Information Processing 17, 1\u201342 (2018).","DOI":"10.1007\/s11128-018-2082-8"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Jens Eisert and Martin Wilkens. ``Quantum games''. Journal of Modern Optics 47, 2543\u20132556 (2000).","DOI":"10.1080\/09500340008232180"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Luca Marinatto and Tullio Weber. ``A quantum approach to static games of complete information''. Physics Letters A 272, 291\u2013303 (2000).","DOI":"10.1016\/S0375-9601(00)00441-2"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Rahul Jain and John Watrous. ``Parallel approximation of non-interactive zero-sum quantum games''. In 2009 24th Annual IEEE Conference on Computational Complexity. Pages 243\u2013253. IEEE (2009).","DOI":"10.1109\/CCC.2009.26"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Zhaohui Wei and Shengyu Zhang. ``Full characterization of quantum correlated equilibria''. Quantum Inf. Comput. 13, 846\u2013860 (2013).","DOI":"10.26421\/QIC13.9-10-7"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Nicolo Cesa-Bianchi and G\u00e1bor Lugosi. ``Prediction, learning, and games''. Cambridge university press. (2006).","DOI":"10.1017\/CBO9780511546921"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. ``Algorithmic game theory''. Cambridge university press. (2007).","DOI":"10.1017\/CBO9780511800481"},{"key":"11","unstructured":"Kyriakos Lotidis, Panayotis Mertikopoulos, and Nicholas Bambos. ``Learning in quantum games'' (2023). arXiv:2302.02333."},{"key":"12","unstructured":"Rahul Jain, Georgios Piliouras, and Ryann Sim. ``Matrix multiplicative weights updates in quantum zero-sum games: Conservation laws & recurrence'' (2022). arXiv:2211.01681."},{"key":"13","unstructured":"Wayne Lin, Georgios Piliouras, Ryann Sim, and Antonios Varvitsiotis. ``Quantum potential games, replicator dynamics, and the separability problem'' (2023). arXiv:2302.04789."},{"key":"14","doi-asserted-by":"publisher","unstructured":"Yoav Freund and Robert E Schapire. ``Adaptive game playing using multiplicative weights''. Games and Economic Behavior 29, 79\u2013103 (1999).","DOI":"10.1006\/game.1999.0738"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Yang Cai and Constantinos Daskalakis. ``On minmax theorems for multiplayer games''. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms. Pages 217\u2013234. SIAM (2011).","DOI":"10.1137\/1.9781611973082.20"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Constantinos Daskalakis and Christos H Papadimitriou. ``On a network generalization of the minmax theorem''. In International Colloquium on Automata, Languages, and Programming. Pages 423\u2013434. Springer (2009).","DOI":"10.1007\/978-3-642-02930-1_35"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Amy Greenwald and Amir Jafari. ``A general class of no-regret learning algorithms and game-theoretic equilibria''. In COLT. Volume 3, pages 2\u201312. (2003).","DOI":"10.1007\/978-3-540-45167-9_2"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The multiplicative weights update method: a meta-algorithm and applications''. Theory of computing 8, 121\u2013164 (2012).","DOI":"10.4086\/toc.2012.v008a006"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Georgios Piliouras and Jeff S Shamma. ``Optimization despite chaos: Convex relaxations to complex limit sets via Poincar\u00e9 recurrence''. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Pages 861\u2013873. SIAM (2014).","DOI":"10.1137\/1.9781611973402.64"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Victor Boone and Georgios Piliouras. ``From Darwin to Poincar\u00e9 and von Neumann: Recurrence and cycles in evolutionary and algorithmic game theory''. In Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10\u201312, 2019, Proceedings 15. Pages 85\u201399. Springer (2019).","DOI":"10.1007\/978-3-030-35389-6_7"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. ``Cycles in adversarial regularized learning''. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 2703\u20132717. SIAM (2018).","DOI":"10.1137\/1.9781611975031.172"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Geoffrey J Gordon, Amy Greenwald, and Casey Marks. ``No-regret learning in convex games''. In Proceedings of the 25th international conference on Machine learning. Pages 360\u2013367. (2008).","DOI":"10.1145\/1390156.1390202"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Gilles Stoltz and G\u00e1bor Lugosi. ``Learning correlated equilibria in games with compact sets of strategies''. Games and Economic Behavior 59, 187\u2013208 (2007).","DOI":"10.1016\/j.geb.2006.04.007"},{"key":"24","unstructured":"Constantin Ickstadt, Thorsten Theobald, and Elias Tsigaridas. ``Semidefinite games'' (2022). arXiv:2202.12035."},{"key":"25","doi-asserted-by":"publisher","unstructured":"Michael Johanson, Kevin Waugh, Michael Bowling, and Martin Zinkevich. ``Accelerating best response calculation in large extensive games''. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume One. Page 258\u2013265. IJCAI'11. AAAI Press (2011).","DOI":"10.5591\/978-1-57735-516-8\/IJCAI11-054"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Tim Roughgarden. ``Twenty lectures on algorithmic game theory''. Cambridge University Press. (2016).","DOI":"10.1017\/CBO9781316779309"},{"key":"27","doi-asserted-by":"publisher","unstructured":"John Nash. ``Non-cooperative games''. Annals of Mathematics 54, 286\u2013295 (1951).","DOI":"10.4324\/9781003547983-16"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Robert J Aumann. ``Subjectivity and correlation in randomized strategies''. Journal of mathematical Economics 1, 67\u201396 (1974).","DOI":"10.1142\/9789811227332_0007"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Herv\u00e9 Moulin and J P Vial. ``Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon''. International Journal of Game Theory 7, 201\u2013221 (1978).","DOI":"10.1007\/BF01769190"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Elad Hazan et al. ``Introduction to online convex optimization''. Foundations and Trends\u00ae in Optimization 2, 157\u2013325 (2016).","DOI":"10.1561\/2400000013"},{"key":"31","unstructured":"Satyen Kale. ``Efficient algorithms using the multiplicative weights update method''. PhD thesis. Princeton University. (2007). url: www.proquest.com\/dissertations-theses\/efficient-algorithms-using-multiplicative-weights\/docview\/304824121\/se-2."},{"key":"32","unstructured":"Koji Tsuda, Gunnar R\u00e4tsch, and Manfred K Warmuth. ``Matrix exponentiated gradient updates for on-line learning and Bregman projection''. Journal of Machine Learning Research 6, 995\u20131018 (2005). url: http:\/\/jmlr.org\/papers\/v6\/tsuda05a.html."},{"key":"33","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Satyen Kale. ``A combinatorial, primal-dual approach to semidefinite programs''. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. Pages 227\u2013236. (2007).","DOI":"10.1145\/1250790.1250823"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. ``QIP=PSPACE''. Journal of the ACM (JACM) 58, 1\u201327 (2011).","DOI":"10.1145\/1806689.1806768"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. ``Spectral sparsification and regret minimization beyond matrix multiplicative updates''. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing. Pages 237\u2013245. (2015).","DOI":"10.1145\/2746539.2746610"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Sergiu Hart and Andreu Mas-Colell. ``A simple adaptive procedure leading to correlated equilibrium''. Econometrica 68, 1127\u20131150 (2000).","DOI":"10.4159\/9780674915343-010"},{"key":"37","doi-asserted-by":"publisher","unstructured":"J v. Neumann. ``Zur theorie der gesellschaftsspiele''. Mathematische annalen 100, 295\u2013320 (1928).","DOI":"10.1007\/BF01448847"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Luigi Accardi and Andreas Boukas. ``von Neumann's minimax theorem for continuous quantum games'' (2020). arXiv:2006.11502.","DOI":"10.31390\/josa.1.2.05"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. ``Circumventing the price of anarchy: Leading dynamics to good behavior''. SIAM Journal on Computing 42, 230\u2013264 (2013).","DOI":"10.1137\/110821317"},{"key":"40","unstructured":"Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides, Federico Cacciamani, Stephen Marcus McAleer, Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. ``Steering no-regret learners to a desired equilibrium'' (2023). arXiv:2306.05221."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-17-1569\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T14:47:13Z","timestamp":1734446833000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-17-1569\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,17]]},"references-count":41,"URL":"https:\/\/doi.org\/10.22331\/q-2024-12-17-1569","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,17]]},"article-number":"1569"}}