# Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent arXiv: https://arxiv.org/abs/2205.15294 · HTML: https://mlsanity.com/paper/2205.15294/ ## Key facts - Cited by 15 papers in the map (data through 14 Oct 2026). - Builds on 22 of its 49 references that are in the map. - First posted on arXiv 30 May 2022. ## Builds on (most cited first, 22 of 22) - [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014) - [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021) - [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020) - [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021) - [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022) - [No-Press Diplomacy from Scratch](https://mlsanity.com/paper/2110.02924/) (2021) - [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022) - [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019) - [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021) - [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021) - [Revisiting CFR+ and Alternating Updates](https://mlsanity.com/paper/1810.11542/) (2018) - [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020) - [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022) - [Stochastic Regret Minimization in Extensive-Form Games](https://mlsanity.com/paper/2002.08493/) (2020) - [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021) - [Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games](https://mlsanity.com/paper/2103.04546/) (2021) - [Joint Policy Search for Multi-agent Collaboration with Imperfect Information](https://mlsanity.com/paper/2008.06495/) (2020) - [Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games](https://mlsanity.com/paper/2103.04539/) (2021) - [Learning to Correlate in Multi-Player General-Sum Sequential Games](https://mlsanity.com/paper/1910.06228/) (2019) - [Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect information](https://mlsanity.com/paper/1810.04433/) (2018) - [Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games](https://mlsanity.com/paper/2205.07223/) (2022) - [Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Games](https://mlsanity.com/paper/2009.07384/) (2020) ## Built on by (most cited first, 15 of 15) - [Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning](https://mlsanity.com/paper/2407.00617/) (2024) - [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023) - [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023) - [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022) - [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025) - [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023) - [Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach](https://mlsanity.com/paper/2510.20235/) (2025) - [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024) - [Rate-Preserving Reductions for Blackwell Approachability](https://mlsanity.com/paper/2406.07585/) (2024) - [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025) - [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022) - [On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games](https://mlsanity.com/paper/2410.23398/) (2024) - [On the Universal Near Optimality of Hedge in Combinatorial Settings](https://mlsanity.com/paper/2510.17099/) (2025) - [Learning Rationalizable Equilibria in Multiplayer Games](https://mlsanity.com/paper/2210.11402/) (2022) - [Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games](https://mlsanity.com/paper/2406.04201/) (2024) ## Abstract (arXiv) A conceptually appealing approach for learning Extensive-Form Games (EFGs) is to convert them to Normal-Form Games (NFGs). This approach enables us to directly translate state-of-the-art techniques and analyses in NFGs to learning EFGs, but typically suffers from computational intractability due to the exponential blow-up of the game size introduced by the conversion. In this paper, we address this problem in natural and important setups for the Phi-Hedge algorithm -- A generic algorithm capable of learning a large class of equilibria for NFGs. We show that Phi-Hedge can be directly used to learn Nash Equilibria (zero-sum settings), Normal-Form Coarse Correlated Equilibria (NFCCE), and Extensive-Form Correlated Equilibria (EFCE) in EFGs. We prove that, in those settings, the Phi-Hedge algorithms are equivalent to standard Online Mirror Descent (OMD) algorithms for EFGs with suitable dilated regularizers, and run in polynomial time. This new connection further allows us to design and analyze a new class of OMD algorithms based on modifying its log-partition function. In particular, we design an improved algorithm with balancing techniques that achieves a sharp widetildeO(√XAT) EFCE-regret under bandit-feedback in an EFG with X information sets, A actions, and T episodes. To our best knowledge, this is the first such rate and matches the information-theoretic lower bound.