{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:58Z","timestamp":1781031418975,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":78,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-234264"],"award-info":[{"award-number":["CCF-234264"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["IS-1943607"],"award-info":[{"award-number":["IS-1943607"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"research fellowship from the Center for Algorithms, Data, and Market Design at Yale (CADMY)","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800871","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1639-1650","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5426-1324","authenticated-orcid":false,"given":"Yang","family":"Cai","sequence":"first","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5451-0490","authenticated-orcid":false,"given":"Constantinos","family":"Daskalakis","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4142-3627","authenticated-orcid":false,"given":"Haipeng","family":"Luo","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3890-8260","authenticated-orcid":false,"given":"Chen-Yu","family":"Wei","sequence":"additional","affiliation":[{"name":"University of Virginia, Charlottesville, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9989-4697","authenticated-orcid":false,"given":"Weiqiang","family":"Zheng","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Mete \u015eeref Ahunbay. 2024. First-order (coarse) correlated equilibria in non-concave games."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3736252.3742500"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520031"},{"key":"e_1_3_2_1_4_1","unstructured":"Ioannis Anagnostides Gabriele Farina Maxwell Fishelson Haipeng Luo and Jon Schneider. 2026. Swap Regret Minimization Through Response-Based Approachability."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Ioannis Anagnostides Gabriele Farina Christian Kroer Chung-Wei Lee Haipeng Luo and Tuomas Sandholm. 2022. Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games. In Advances in Neural Information Processing Systems (NeurIPS).","DOI":"10.52202\/068431-0238"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718250"},{"key":"e_1_3_2_1_7_1","unstructured":"Anastasios N Angelopoulos Michael I Jordan and Ryan J Tibshirani. 2025. Gradient Equilibrium in Online Learning: Theory and Applications."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3736252.3742511"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673517"},{"key":"e_1_3_2_1_10_1","first-page":"1","article-title":"Correlated equilibrium as an expression of Bayesian rationality","author":"Aumann Robert J","year":"1987","unstructured":"Robert J Aumann. 1987. Correlated equilibrium as an expression of Bayesian rationality. JSTOR, 1-18.","journal-title":"JSTOR"},{"key":"e_1_3_2_1_11_1","volume-title":"International conference on machine learning. 551-560","author":"Bai Yu","year":"2020","unstructured":"Yu Bai and Chi Jin. 2020. Provable self-play algorithms for competitive reinforcement learning. PMLR, In International conference on machine learning. 551-560."},{"key":"e_1_3_2_1_12_1","first-page":"6","article-title":"From external to internal regret","volume":"8","author":"Blum Avrim","year":"2007","unstructured":"Avrim Blum and Yishay Mansour. 2007. From external to internal regret.. Journal of Machine Learning Research, 8, 6.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_13_1","volume-title":"Convex optimization: Algorithms and complexity","author":"Bubeck S\u00e9bastien","unstructured":"S\u00e9bastien Bubeck. 2015. Convex optimization: Algorithms and complexity. Now Publishers, Inc., Foundations and Trends\u00ae in Machine Learning, 8, 3-4, 231-357."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.52202\/079017-4456"},{"key":"e_1_3_2_1_15_1","unstructured":"Yang Cai Constantinos Daskalakis Haipeng Luo Chen-Yu Wei and Weiqiang Zheng. 2025. Proximal regret and proximal correlated equilibria: A new tractable solution concept for online learning and games."},{"key":"e_1_3_2_1_16_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 3889-3897","author":"Cai Yang","year":"2024","unstructured":"Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. 2024. Near-optimal policy optimization for correlated equilibrium in general-sum markov games. PMLR, In International Conference on Artificial Intelligence and Statistics. 3889-3897."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Yang Cai Argyris Oikonomou and Weiqiang Zheng. 2022. Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games. In Advances in Neural Information Processing Systems (NeurIPS).","DOI":"10.52202\/068431-2457"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_20_1","first-page":"18990","article-title":"Hedging in games: Faster convergence of external and swap regrets","volume":"33","author":"Chen Xi","year":"2020","unstructured":"Xi Chen and Binghui Peng. 2020. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems (NeurIPS), 33, 18990-18999.","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649681"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. 235-254","author":"Daskalakis Constantinos","year":"2011","unstructured":"Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. 2011. Near-optimal no-regret algorithms for zero-sum games. SIAM, In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. 235-254."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718307"},{"key":"e_1_3_2_1_24_1","unstructured":"Constantinos Daskalakis Gabriele Farina Noah Golowich Tuomas Sandholm and Brian Hu Zhang. 2024. A Lower Bound on Swap Regret in Extensive-Form Games."},{"key":"e_1_3_2_1_25_1","unstructured":"Constantinos Daskalakis Maxwell Fishelson and Noah Golowich. 2021. Near-optimal no-regret learning in general games."},{"key":"e_1_3_2_1_26_1","unstructured":"Constantinos Daskalakis Dylan J Foster and Noah Golowich. 2020. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems 33 5527-5540."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1461928.1461951"},{"key":"e_1_3_2_1_28_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 4180-4234","author":"Daskalakis Constantinos","year":"2023","unstructured":"Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. 2023. The complexity of markov equilibrium in stochastic games. PMLR, In The Thirty Sixth Annual Conference on Learning Theory. 4180-4234."},{"key":"e_1_3_2_1_29_1","volume-title":"Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. In 10th Innovations in Theoretical Computer Science Conference (ITCS).","author":"Daskalakis Constantinos","year":"2019","unstructured":"Constantinos Daskalakis and Ioannis Panageas. 2019. Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. In 10th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_1_30_1","unstructured":"Yuan Deng Jon Schneider and Balasubramanian Sivan. 2019. Strategizing against no-regret learners. Advances in neural information processing systems 32."},{"key":"e_1_3_2_1_31_1","first-page":"39076","article-title":"Near-optimal no-regret learning dynamics for general convex games","volume":"35","author":"Farina Gabriele","year":"2022","unstructured":"Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. 2022. Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35, 39076-39089.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563772"},{"key":"e_1_3_2_1_33_1","volume-title":"International Conference on Machine Learning. 6337-6357","author":"Farina Gabriele","year":"2022","unstructured":"Gabriele Farina, Chung-Wei Lee, Haipeng Luo, and Christian Kroer. 2022. Kernelized multiplicative weights for 0\/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. PMLR, In International Conference on Machine Learning. 6337-6357."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54110-4_10"},{"key":"e_1_3_2_1_35_1","volume-title":"The Thirty-ninth Annual Conference on Neural Information Processing Systems.","author":"Fishelson Maxwell","year":"2025","unstructured":"Maxwell Fishelson, Noah Golowich, Mehryar Mohri, and Jon Schneider. 2025. High-Dimensional Calibration from Swap Regret. In The Thirty-ninth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_3_2_1_36_1","volume-title":"Full Swap Regret and Discretized Calibration. In 36th International Conference on Algorithmic Learning Theory.","author":"Fishelson Maxwell","year":"2025","unstructured":"Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, and Yifeng Teng. 2025. Full Swap Regret and Discretized Calibration. In 36th International Conference on Algorithmic Learning Theory."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0595"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_2_1_39_1","volume-title":"The theory of learning in games","author":"Fudenberg Drew","unstructured":"Drew Fudenberg and David K Levine. 1998. The theory of learning in games. MIT press. 2."},{"key":"e_1_3_2_1_40_1","first-page":"1660","article-title":"Adaptive conformal inference under distribution shift","volume":"34","author":"Gibbs Isaac","year":"2021","unstructured":"Isaac Gibbs and Emmanuel Candes. 2021. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34, 1660-1672.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390202"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_2"},{"key":"e_1_3_2_1_43_1","volume-title":"\u201cBayesian","author":"Harsanyi John C","unstructured":"John C Harsanyi. 1967. Games with incomplete information played by \u201cBayesian\u201d players, I\u2013III Part I. The basic model. INFORMS, Management science, 14, 3, 159-182."},{"issue":"5","key":"e_1_3_2_1_44_1","first-page":"1127","article-title":"A simple adaptive procedure leading to correlated equilibrium","volume":"68","author":"Hart Sergiu","year":"2000","unstructured":"Sergiu Hart and Andreu Mas-Colell. 2000. A simple adaptive procedure leading to correlated equilibrium. Wiley Online Library, Econometrica, 68, 5, 1127-1150.","journal-title":"Wiley Online Library, Econometrica"},{"key":"e_1_3_2_1_45_1","unstructured":"Jason Hartline Vasilis Syrgkanis and Eva Tardos. 2015. No-regret learning in Bayesian games. Advances in Neural Information Processing Systems 28."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3614407.3643706"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709025.3712217"},{"key":"e_1_3_2_1_48_1","unstructured":"Chi Jin Qinghua Liu Yuanhao Wang and Tiancheng Yu. 2021. V-Learning\u2013A Simple Efficient Decentralized Algorithm for Multiagent RL."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617902"},{"key":"e_1_3_2_1_50_1","volume-title":"Annual symposium on theoretical aspects of computer science. 404-413","author":"Koutsoupias Elias","year":"1999","unstructured":"Elias Koutsoupias and Christos Papadimitriou. 1999. Worst-case equilibria. Springer, In Annual symposium on theoretical aspects of computer science. 404-413."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.2307\/2309332"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0112033"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2305349120"},{"key":"e_1_3_2_1_54_1","first-page":"48","volume-title":"Proceedings of the national academy of sciences, 36","volume":"1","author":"Nash John F","year":"1950","unstructured":"John F Nash Jr. 1950. Equilibrium points in n-person games. National Acad Sciences, Proceedings of the national academy of sciences, 36, 1, 48-49."},{"key":"e_1_3_2_1_55_1","volume-title":"Problem complexity and method efficiency in optimization","author":"Nemirovskij Arkadij Semenovi\u010d","unstructured":"Arkadij Semenovi\u010d Nemirovskij and David Borisovich Yudin. 1983. Problem complexity and method efficiency in optimization. Wiley-Interscience."},{"key":"e_1_3_2_1_56_1","unstructured":"Francesco Orabona. 2019. A modern introduction to online learning."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597812"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601987174"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649691"},{"key":"e_1_3_2_1_61_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory. 4158-4184","author":"Peng Binghui","year":"2024","unstructured":"Binghui Peng and Aviad Rubinstein. 2024. The complexity of approximate (coarse) correlated equilibrium for incomplete information games. PMLR, In The Thirty Seventh Annual Conference on Learning Theory. 4158-4184."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-1617"},{"key":"e_1_3_2_1_63_1","unstructured":"Sasha Rakhlin and Karthik Sridharan. 2013. Optimization learning and games with predictable sequences."},{"key":"e_1_3_2_1_64_1","unstructured":"Ramya Ramalingam Shayan Kiyani and Aaron Roth. 2025. The Relationship between No-Regret Learning and Online Conformal Prediction."},{"key":"e_1_3_2_1_65_1","first-page":"520","article-title":"Existence and uniqueness of equilibrium points for concave n-person games","author":"Rosen J Ben","year":"1965","unstructured":"J Ben Rosen. 1965. Existence and uniqueness of equilibrium points for concave n-person games. JSTOR, 520-534.","journal-title":"JSTOR"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055589.3055596"},{"key":"e_1_3_2_1_67_1","volume-title":"The Thirty-ninth Annual Conference on Neural Information Processing Systems.","author":"Skoulakis Stratis","year":"2025","unstructured":"Stratis Skoulakis. 2025. Explaining the Law of Supply and Demand via Online Learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718242"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2006.04.007"},{"key":"e_1_3_2_1_70_1","unstructured":"Vasilis Syrgkanis Alekh Agarwal Haipeng Luo and Robert E Schapire. 2015. Fast convergence of regularized learning in games."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488635"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"e_1_3_2_1_73_1","unstructured":"John Von Neumann and Oskar Morgenstern. 1944. Theory of games and economic behavior: 60th anniversary commemorative edition. In Theory of games and economic behavior."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0340"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"crossref","unstructured":"Brian Hu Zhang Ioannis Anagnostides Gabriele Farina and Tuomas Sandholm. 2024. Efficient \u03a6 -Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games. In Advances in Neural Information Processing Systems.","DOI":"10.52202\/079017-3976"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3736252.3742670"},{"key":"e_1_3_2_1_77_1","volume-title":"Proceedings of the 20th international conference on machine learning (ICML).","author":"Zinkevich Martin","year":"2003","unstructured":"Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ICML)."},{"key":"e_1_3_2_1_78_1","unstructured":"Martin Zinkevich Michael Johanson Michael Bowling and Carmelo Piccione. 2007. Regret minimization in games with incomplete information. Advances in neural information processing systems 20."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800871","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800871","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:59:08Z","timestamp":1781027948000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800871"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":78,"alternative-id":["10.1145\/3798129.3800871","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800871","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}