# Near-Optimal Phi-Regret Learning in Extensive-Form Games

arXiv: https://arxiv.org/abs/2208.09747 · HTML: https://mlsanity.com/paper/2208.09747/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 67 references that are in the map.
- First posted on arXiv 20 Aug 2022.

## Builds on (most cited first, 30 of 30)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [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)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021)
- [Hindsight and Sequential Rationality of Correlated Play](https://mlsanity.com/paper/2012.05874/) (2020)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [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)
- [Coarse Correlation in Extensive-Form Games](https://mlsanity.com/paper/1908.09893/) (2019)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibria](https://mlsanity.com/paper/2202.05446/) (2022)
- [Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games](https://mlsanity.com/paper/2205.07223/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [A Simple Adaptive Procedure Converging to Forgiving Correlated Equilibria](https://mlsanity.com/paper/2207.06548/) (2022)

## Built on by (most cited first, 3 of 3)

- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)

## Abstract (arXiv)

In this paper, we establish efficient and uncoupled learning dynamics so that, when employed by all players in multiplayer perfect-recall imperfect-information extensive-form games, the trigger regret of each player grows as O(log T) after T repetitions of play. This improves exponentially over the prior best known trigger-regret bound of O(T1/4), and settles a recent open question by Bai et al. (2022). As an immediate consequence, we guarantee convergence to the set of extensive-form correlated equilibria and coarse correlated equilibria at a near-optimal rate of fraclog TT. Building on prior work, at the heart of our construction lies a more general result regarding fixed points deriving from rational functions with polynomial degree, a property that we establish for the fixed points of (coarse) trigger deviation functions. Moreover, our construction leverages a refined regret circuit for the convex hull, which -- unlike prior guarantees -- preserves the RVU property introduced by Syrgkanis et al. (NIPS, 2015); this observation has an independent interest in establishing near-optimal regret under learning dynamics based on a CFR-type decomposition of the regret.