# Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2014.

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

- [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021)
- [Conjectural Online Learning with First-order Beliefs in Asymmetric Information Stochastic Games](https://mlsanity.com/paper/2402.18781/) (2024)
- [Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games](https://mlsanity.com/paper/2103.04539/) (2021)
- [Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess](https://mlsanity.com/paper/2110.01810/) (2021)
- [Local and adaptive mirror descents in extensive-form games](https://mlsanity.com/paper/2309.00656/) (2023)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)

## Abstract (arXiv)

This article discusses two contributions to decision-making in complex partially observable stochastic games. First, we apply two state-of-the-art search techniques that use Monte-Carlo sampling to the task of approximating a Nash-Equilibrium (NE) in such games, namely Monte-Carlo Tree Search (MCTS) and Monte-Carlo Counterfactual Regret Minimization (MCCFR). MCTS has been proven to approximate a NE in perfect-information games. We show that the algorithm quickly finds a reasonably strong strategy (but not a NE) in a complex imperfect information game, i.e. Poker. MCCFR on the other hand has theoretical NE convergence guarantees in such a game. We apply MCCFR for the first time in Poker. Based on our experiments, we may conclude that MCTS is a valid approach if one wants to learn reasonably strong strategies fast, whereas MCCFR is the better choice if the quality of the strategy is most important. Our second contribution relates to the observation that a NE is not a best response against players that are not playing a NE. We present Monte-Carlo Restricted Nash Response (MCRNR), a sample-based algorithm for the computation of restricted Nash strategies. These are robust best-response strategies that (1) exploit non-NE opponents more than playing a NE and (2) are not (overly) exploitable by other strategies. We combine the advantages of two state-of-the-art algorithms, i.e. MCCFR and Restricted Nash Response (RNR). MCRNR samples only relevant parts of the game tree. We show that MCRNR learns quicker than standard RNR in smaller games. Also we show in Poker that MCRNR learns robust best-response strategies fast, and that these strategies exploit opponents more than playing a NE does.