{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:11Z","timestamp":1781077751538,"version":"3.54.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,18]],"date-time":"2022-11-18T00:00:00Z","timestamp":1668729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["IIS-1718457, IIS-1617590, IIS-1901403, and CCF-1733556"],"award-info":[{"award-number":["IIS-1718457, IIS-1617590, IIS-1901403, and CCF-1733556"]}]},{"name":"ARO","award":["W911NF-17-1-0082 and W911NF2010081"],"award-info":[{"award-number":["W911NF-17-1-0082 and W911NF2010081"]}]},{"name":"Italian MIUR PRIN 2017"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            The existence of simple uncoupled no-regret learning dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their\n            <jats:italic>internal<\/jats:italic>\n            regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form (that is, tree-form) games generalize normal-form games by modeling both sequential and simultaneous moves, as well as imperfect information. Because of the sequential nature and presence of private information in the game, correlation in extensive-form games possesses significantly different properties than in normal-form games, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to the classical notion of correlated equilibrium in normal-form games. Compared to the latter, the constraints that define the set of EFCEs are significantly more complex, as the correlation device (a.k.a. mediator) must take into account the evolution of beliefs of each player as they make observations throughout the game. Due to that significant added complexity, the existence of uncoupled learning dynamics leading to an EFCE has remained a challenging open research question for a long time. In this article, we settle that question by giving the first uncoupled no-regret dynamics that converge to the set of EFCEs in\n            <jats:italic>n<\/jats:italic>\n            -player general-sum extensive-form games with perfect recall. We show that each iterate can be computed in time polynomial in the size of the game tree, and that, when all players play repeatedly according to our learning dynamics, the empirical frequency of play after\n            <jats:italic>T<\/jats:italic>\n            game repetitions is proven to be a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( O(1\/\\sqrt {T}) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximate EFCE with high probability, and an EFCE almost surely in the limit.\n          <\/jats:p>","DOI":"10.1145\/3563772","type":"journal-article","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T11:49:46Z","timestamp":1666266586000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3976-0061","authenticated-orcid":false,"given":"Gabriele","family":"Farina","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2046-4019","authenticated-orcid":false,"given":"Andrea","family":"Celli","sequence":"additional","affiliation":[{"name":"Bocconi University, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8284-5757","authenticated-orcid":false,"given":"Alberto","family":"Marchesi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7349-3932","authenticated-orcid":false,"given":"Nicola","family":"Gatti","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,18]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90037-8"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aao1733"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011829"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s001820400182"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11462"},{"key":"e_1_3_2_8_2","first-page":"13055","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Celli Andrea","year":"2019","unstructured":"Andrea Celli, Alberto Marchesi, Tommaso Bianchi, and Nicola Gatti. 2019. Learning to correlate in multi-player general-sum sequential games. In Proceedings of the International Conference on Advances in Neural Information Processing Systems. 13055\u201313065."},{"key":"e_1_3_2_9_2","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Celli Andrea","year":"2020","unstructured":"Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. 2020. No-regret learning dynamics for extensive-form correlated equilibrium. In Proceedings of the International Conference on Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/1137817"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.69"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_35"},{"key":"e_1_3_2_14_2","first-page":"151","volume-title":"Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence","author":"Dud\u00edk Miroslav","year":"2009","unstructured":"Miroslav Dud\u00edk and Geoffrey J. Gordon. 2009. A sampling-based approach to computing equilibria in succinct extensive-form games. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. 151\u2013160."},{"key":"e_1_3_2_15_2","first-page":"1863","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Farina Gabriele","year":"2019","unstructured":"Gabriele Farina, Christian Kroer, and Tuomas Sandholm. 2019. Regret circuits: Composability of regret minimizers. In Proceedings of the International Conference on Machine Learning. 1863\u20131872."},{"key":"e_1_3_2_16_2","first-page":"9229","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Farina Gabriele","year":"2019","unstructured":"Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. 2019. Correlation in extensive-form games: Saddle-point formulation and benchmarks. In Proceedings of the International Conference on Advances in Neural Information Processing Systems. 9229\u20139239."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0595"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1889(94)00819-4"},{"key":"e_1_3_2_19_2","volume-title":"The Theory of Learning in Games","author":"Fudenberg Drew","year":"1998","unstructured":"Drew Fudenberg and David K. Levine. 1998. The Theory of Learning in Games, Vol. 2. MIT Press."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1998.0705"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390202"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_2"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.2000.2746"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322655581"},{"key":"e_1_3_2_26_2","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Hazan Elad","year":"2008","unstructured":"Elad Hazan and Satyen Kale. 2008. Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria. In Proceedings of the International Conference on Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_56"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.02.002"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779934"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0051"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764944"},{"key":"e_1_3_2_33_2","first-page":"193","volume-title":"Extensive Games and the Problem of Information","author":"Kuhn H. W.","year":"1953","unstructured":"H. W. Kuhn. 1953. Extensive Games and the Problem of Information. Princeton University Press, 193\u2013216."},{"key":"e_1_3_2_34_2","first-page":"1078","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Lanctot Marc","year":"2009","unstructured":"Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H. Bowling. 2009. Monte Carlo sampling for regret minimization in extensive games. In Proceedings of the International Conference on Advances in Neural Information Processing Systems. 1078\u20131086."},{"key":"e_1_3_2_35_2","first-page":"195","volume-title":"Concentration","author":"McDiarmid Colin","year":"1998","unstructured":"Colin McDiarmid. 1998. Concentration. Springer, Berlin, 195\u2013248."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aam6960"},{"key":"e_1_3_2_37_2","series-title":"Proceedings of the 38th International Conference on Machine Learning","first-page":"7818","volume":"139","author":"Morrill Dustin","year":"2021","unstructured":"Dustin Morrill, Ryan D\u2019Orazio, Marc Lanctot, James R. Wright, Michael Bowling, and Amy R. Greenwald. 2021. Efficient deviation types and learning for hindsight rationality in extensive-form games. In Proceedings of the 38th International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 139). PMLR, 7818\u20137828."},{"key":"e_1_3_2_38_2","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI\u201920)","author":"Morrill Dustin","year":"2020","unstructured":"Dustin Morrill, Ryan D\u2019Orazio, Reca Sarfati, Marc Lanctot, James Wright, Amy Greenwald, and Michael Bowling. 2020. Hindsight and sequential rationality of correlated play. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI\u201920)."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1080\/00949657508810122"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"e_1_3_2_42_2","article-title":"Reduction of a game with complete memory to a matrix game","volume":"3","author":"Romanovskii I.","year":"1962","unstructured":"I. Romanovskii. 1962. Reduction of a game with complete memory to a matrix game. Soviet Math. 3 (1962).","journal-title":"Soviet Math."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811654"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2006.04.007"},{"key":"e_1_3_2_46_2","article-title":"Solving large imperfect information games using CFR+","author":"Tammelin Oskari","year":"2014","unstructured":"Oskari Tammelin. 2014. Solving large imperfect information games using CFR+. arXiv preprint arXiv:1407.5042 (2014).","journal-title":"arXiv preprint arXiv:1407.5042"},{"key":"e_1_3_2_47_2","first-page":"645","volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence","author":"Tammelin Oskari","year":"2015","unstructured":"Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. 2015. Solving heads-up limit Texas hold\u2019em. In Proceedings of the International Joint Conferences on Artificial Intelligence. 645\u2013652."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0050"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0340"},{"key":"e_1_3_2_50_2","first-page":"1729","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Zinkevich Martin","year":"2008","unstructured":"Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. 2008. Regret minimization in games with incomplete information. In Proceedings of the International Conference on Advances in Neural Information Processing Systems. 1729\u20131736."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563772","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563772","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:07Z","timestamp":1750186807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,18]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3563772"],"URL":"https:\/\/doi.org\/10.1145\/3563772","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,18]]},"assertion":[{"value":"2021-04-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}