# Approximate exploitability: Learning a best response in large games

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2020.

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

- [Evaluating Superhuman Models with Consistency Checks](https://mlsanity.com/paper/2306.09983/) (2023)
- [Diversifying AI: Towards Creative Chess with AlphaZero](https://mlsanity.com/paper/2308.09175/) (2023)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Search in Imperfect Information Games](https://mlsanity.com/paper/2111.05884/) (2021)
- [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022)
- [Population-based Evaluation in Repeated Rock-Paper-Scissors as a Benchmark for Multiagent Reinforcement Learning](https://mlsanity.com/paper/2303.03196/) (2023)
- [The Adaptive Arms Race: Redefining Robustness in AI Security](https://mlsanity.com/paper/2312.13435/) (2023)
- [Multi-Agent Diagnostics for Robustness via Illuminated Diversity](https://mlsanity.com/paper/2401.13460/) (2024)
- [The Update-Equivalence Framework for Decision-Time Planning](https://mlsanity.com/paper/2304.13138/) (2023)
- [BRExIt: On Opponent Modelling in Expert Iteration](https://mlsanity.com/paper/2206.00113/) (2022)
- [JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2308.04719/) (2023)
- [Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery](https://mlsanity.com/paper/2601.22896/) (2026)
- [Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks](https://mlsanity.com/paper/2211.15936/) (2022)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Offline Fictitious Self-Play for Competitive Games](https://mlsanity.com/paper/2403.00841/) (2024)
- [Learning to Beat ByteRL: Exploitability of Collectible Card Game Agents](https://mlsanity.com/paper/2404.16689/) (2024)
- [On the Power of Perturbation under Sampling in Solving Extensive-Form Games](https://mlsanity.com/paper/2501.16600/) (2025)
- [How Much Due Diligence Before You Bid? Learning in Intractable Takeover Auctions](https://mlsanity.com/paper/2606.29457/) (2026)
- [Combining a Meta-Policy and Monte-Carlo Planning for Scalable Type-Based Reasoning in Partially Observable Environments](https://mlsanity.com/paper/2306.06067/) (2023)
- [Beyond Game Theory Optimal: Profit-Maximizing Poker Agents for No-Limit Holdem](https://mlsanity.com/paper/2509.23747/) (2025)
- [Outbidding and Outbluffing Elite Humans: Mastering Liar's Poker via Self-Play and Reinforcement Learning](https://mlsanity.com/paper/2511.03724/) (2025)
- [A Structural Threshold in Decision Capacity Governs Collapse in Self-Play Reinforcement Learning](https://mlsanity.com/paper/2605.16315/) (2026)
- [Communicating Chess Strategies in Natural Language](https://mlsanity.com/paper/2607.11486/) (2026)

## Abstract (arXiv)

Researchers have demonstrated that neural networks are vulnerable to adversarial examples and subtle environment changes, both of which one can view as a form of distribution shift. To humans, the resulting errors can look like blunders, eroding trust in these agents. In prior games research, agent evaluation often focused on the in-practice game outcomes. While valuable, such evaluation typically fails to evaluate robustness to worst-case outcomes. Prior research in computer poker has examined how to assess such worst-case performance, both exactly and approximately. Unfortunately, exact computation is infeasible with larger domains, and existing approximations rely on poker-specific knowledge. We introduce ISMCTS-BR, a scalable search-based deep reinforcement learning algorithm for learning a best response to an agent, thereby approximating worst-case performance. We demonstrate the technique in several two-player zero-sum games against a variety of agents, including several AlphaZero-based agents.