# On the Power of Perturbation under Sampling in Solving Extensive-Form Games

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 28 Jan 2025.

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

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent](https://mlsanity.com/paper/1903.05614/) (2019)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Approximate exploitability: Learning a best response in large games](https://mlsanity.com/paper/2004.09677/) (2020)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [Low-Variance and Zero-Variance Baselines for Extensive-Form Games](https://mlsanity.com/paper/1907.09633/) (2019)
- [Faster Game Solving via Hyperparameter Schedules](https://mlsanity.com/paper/2404.09097/) (2024)

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

- [Look-ahead Reasoning with a Learned Model in Imperfect Information Games](https://mlsanity.com/paper/2510.05048/) (2025)

## Abstract (arXiv)

We investigate how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in solving imperfect-information extensive-form games under sampling, where payoffs are estimated from sampled trajectories. While optimistic algorithms are effective under full feedback, they often become unstable in the presence of sampling noise. Payoff perturbation offers a promising alternative for stabilizing learning and achieving textitlast-iterate convergence. We present a unified framework for textitPerturbed FTRL algorithms and study two variants: PFTRL-KL (standard KL divergence) and PFTRL-RKL (Reverse KL divergence), the latter featuring an estimator with both unbiasedness and conditional zero variance. While PFTRL-KL generally achieves equivalent or better performance across benchmark games, PFTRL-RKL consistently outperforms it in Leduc poker, whose structure is more asymmetric than the other games in a sense. Given the modest advantage of PFTRL-RKL, we design the second experiment to isolate the effect of conditional zero variance, showing that the variance-reduction property of RKL improve last-iterate performance.