PaperlayerView exact revision on arXiv

Source-linked AI summary

Combining Deep Reinforcement Learning and Search for Imperfect-Information Games

Noam Brown, Anton Bakhtin, Adam Lerer, Qucheng Gong

arXiv:2007.13544v2cs.GTcs.AIcs.LG

TL;DR

Prior RL+Search algorithms cannot handle imperfect-information games because their assumptions fail when action values depend on selection probabilities. ReBeL combines self-play reinforcement learning with search over public belief states and provably converges toward equilibrium in two-player zero-sum games. It approximates Nash equilibrium in imperfect-information benchmarks and achieves superhuman heads-up no-limit Texas hold’em performance while using less expert knowledge than prior poker AI.

  • Problem

    Prior RL+Search algorithms cannot cope with imperfect-information games because action values may depend on the probability of selecting an action.

  • Method

    ReBeL trains value and policy networks through self-play and uses search over public belief states, solving depth-limited imperfect-information subgames.

  • Results

    ReBeL provably converges to a Nash equilibrium in two-player zero-sum games, approximates one in Liar’s Dice, and achieves superhuman heads-up no-limit Texas hold’em performance with less expert knowledge than prior poker AI.

  • Takeaways & Limitations

    ReBeL generalizes self-play reinforcement learning and search to imperfect-information games while retaining equilibrium guarantees within the two-player zero-sum setting.

  • Takeaways & Limitations

    ReBeL’s input grows linearly with the number of infostates in a public state, and its theoretical guarantees are limited to two-player zero-sum games.

Abstract

from arXiv · show

The combination of deep reinforcement learning and search at both training and test time is a powerful paradigm that has led to a number of successes in single-agent settings and perfect-information games, best exemplified by AlphaZero. However, prior algorithms of this form cannot cope with imperfect-information games. This paper presents ReBeL, a general framework for self-play reinforcement learning and search that provably converges to a Nash equilibrium in any two-player zero-sum game. In the simpler setting of perfect-information games, ReBeL reduces to an algorithm similar to AlphaZero. Results in two different imperfect-information games show ReBeL converges to an approximate Nash equilibrium. We also show ReBeL achieves superhuman performance in heads-up no-limit Texas hold'em poker, while using far less domain knowledge than any prior poker AI.

1 Introduction

RL+Search has succeeded in perfect-information games but prior methods fail in imperfect-information settings because action values can depend on action probabilities. ReBeL addresses this gap with self-play learning and search over expanded belief states, achieving equilibrium-related and poker results.

  • AlphaZero demonstrates the success of combining reinforcement learning with search in Go, chess, and shogi.
  • Prior RL+Search algorithms do not work in imperfect-information games because their perfect-information assumptions no longer hold.
  • In modified Rock-Paper-Scissors, the optimal policy chooses Rock and Paper with 40% probability each and Scissors with 20%, but one-ply lookahead lacks enough information to recover it.
  • In imperfect-information games, an action’s value may depend on its selection probability, so action-observation states lack unique values and AlphaZero-style methods are unsound.
  • ReBeL expands the state to include agents’ probabilistic beliefs, trains value and policy networks through self-play, and uses them for search during self-play.
  • ReBeL provably converges to Nash equilibrium in two-player zero-sum games, approximates equilibrium in Liar’s Dice, and defeats a top human professional in heads-up no-limit Texas hold’em with less expert knowledge than prior poker AI.

2 Related Work

ReBeL extends the self-play RL+Search paradigm to imperfect-information games by representing states as public belief states. It builds on prior poker approaches while combining search during both training and play.

  • Perfect-information RL+Search methods train value networks through self-play and use search, sometimes guided by policy networks, during training and evaluation.
  • A public belief state represents the common-knowledge distribution over possible states using public observations and all agents’ policies.
  • DeepStack used public-belief-state values during search, whereas ReBeL trains its value function through self-play reinforcement learning rather than random belief-state generation.
  • Pluribus searches at test time with a population of blueprint policies but does not use search during training and incurs search costs that grow linearly with population size.

3 Notation and Background

The paper formalizes imperfect-information games through histories, observations, infostates, policies, and equilibrium concepts. It also defines depth-limited search and the common-knowledge assumptions used by ReBeL.

  • ReBeL assumes game rules and agent policies, including search algorithms, are common knowledge, while stochastic outcomes such as random seeds remain unknown.
  • A game state transitions under joint actions and stochastic dynamics, producing private observations for individual agents and public observations shared by all agents.
  • A history records world states and actions, while an infostate records an agent’s observation-action history and may correspond to multiple histories.
  • Public states collect histories sharing the same public-observation sequence, making the set of possible underlying histories common knowledge among agents.
  • A Nash equilibrium is a policy profile from which no agent can improve expected value by unilaterally switching policies.
  • Depth-limited search extends a subgame a fixed number of actions and treats nonterminal bottom histories with legal full-game actions as leaf nodes.

4 From World States to Public Belief States

ReBeL converts imperfect-information games into continuous belief-representation games whose states encode agents’ beliefs over infostates. It trains and searches on these representations while using equilibrium structure to interpret values.

  • The belief representation converts an imperfect-information game into a continuous state-and-action perfect-information game containing all agents’ probabilistic beliefs.
  • A public belief state is a joint distribution over agents’ possible infostates conditioned on the public state; in perfect-information games, the two representations coincide.
  • A subgame can be rooted at a public belief state, corresponding to sampling a history from its joint belief distribution before continuing in the original game.
  • In two-player zero-sum games, every public belief state has a unique equilibrium value for each agent, with the players’ values summing to zero.
  • The belief representation can be high-dimensional and continuous, making direct search computationally difficult without an effective approximation.
  • ReBeL searches using infostate values and supergradients of the public-belief-state value function, so it learns an infostate-value function rather than a direct PBS value function.

5 Self Play Reinforcement Learning and Search for Public Belief States

ReBeL solves depth-limited subgames in a discrete representation while using learned PBS values, then trains value and policy networks from search during self-play. Its analysis establishes convergence guarantees under idealized approximation and discusses practical training choices.

  • Self-play reinforcement learning and search: ReBeL generates a depth-limited subgame at the root PBS and uses an iterative equilibrium-finding algorithm with the learned value network at leaf nodes.The resulting root infostate values become training examples for the value network.
  • Search in a depth-limited imperfect-information subgame: CFR-D updates a policy profile each iteration, recomputes policy-conditional leaf values, and stores the resulting root infostate value vector.Leaf values change with the current policy profile rather than remaining fixed throughout search.
  • Search in a depth-limited imperfect-information subgame: The average CFR-D policy, rather than the final iteration policy, converges to a Nash equilibrium as the number of iterations increases.CFR-AVG modifies CFR-D to address some of its weaknesses.
  • Self-play reinforcement learning: ReBeL trains its value network by adding searched root values to the dataset and can train a policy network from average subgame policies.The policy network can warm-start equilibrium finding and may narrow the domain over which the value network predicts PBS values.
  • Theoretical guarantee: Theorem 2 bounds the idealized value approximator’s error by O(1/√T) for any PBS encountered during play.Here, T is the number of CFR iterations used in each subgame, and the bound includes a game-dependent constant.
  • Self-play reinforcement learning: Bootstrapping the value network trades bias against variance relative to training from rewards actually received during on-policy games.The paper presents these as alternative value-training approaches.

6 Playing According to an Equilibrium at Test Time

At test time, ReBeL addresses the unknown-opponent-policy problem by using randomized search beliefs rather than unsafe belief propagation. The paper proves this procedure achieves equilibrium play in expectation, while noting risks from sampling poor early iterations.

  • The test-time PBS problem: At test time, an unknown opponent policy prevents exact identification of the root PBS required for search.The paper frames this as a central obstacle to applying the training procedure directly during play.
  • Unsafe search: Unsafe search can produce a non-equilibrium response by propagating beliefs from an approximate opponent policy, making the resulting policy exploitable.In the modified Rock-Paper-Scissors example, the opponent can exploit the deterministic response.
  • Safe search: Safe search requires equilibrium play in expectation, not that every policy sampled by the algorithm is itself a Nash equilibrium.This permits randomized outputs whose expected behavior satisfies the equilibrium requirement.
  • Safe search: ReBeL obtains safe search without additional constraints by randomly selecting an iteration and assuming all players’ policies match that iteration.The same search algorithm can therefore be used at training and test time.
  • Theoretical guarantee: Theorem 3 reports a (C1/√T)-Nash equilibrium guarantee for the test-time procedure, with game-specific constants.The supplied result passage states the bound in terms of T and C1.
  • Limitation: Random iteration selection may choose an extremely poor early policy, although Linear CFR can reduce the weight assigned to early iterations.The paper identifies this as a practical mitigation rather than eliminating the sampling issue entirely.

7 Experimental Setup

The experiments evaluate ReBeL on imperfect-information poker and Liar’s Dice using neural value and policy approximators. The setup combines action abstraction, randomized training conditions, and substantial distributed data generation.

  • Benchmarks: The evaluation covers heads-up no-limit Texas hold’em, turn endgame hold’em, and Liar’s Dice.Turn endgame hold’em automatically checks or calls during the first two of four betting rounds.
  • Action and environment setup: In HUNL and TEH, the action space contains at most nine actions based on typical bet sizes, while off-tree test-time actions are added to the subgame.Bet sizes and stack sizes are randomized during training.
  • Neural approximators: Both value and policy functions are approximated with MLPs using GeLU activations and LayerNorm, trained with Adam.The value uses pointwise Huber loss, while the policy uses probability-based MSE.
  • Compute: Data generation is the training bottleneck because CFR and fictitious-play procedures are sequential and evaluate every leaf node each iteration.The experiments use one training machine and up to 128 machines with eight GPUs each for data generation.

8 Experimental Results

ReBeL performs effectively across poker and Liar’s Dice, reaching low exploitability and strong head-to-head results while using search and learned value functions.

  • Turn Endgame Hold’em: ReBeL reaches TEH exploitability equivalent to about 125 iterations of full-game tabular CFR.A value network trained on randomly sampled PBSs fails to learn anything valuable, highlighting the importance of self-play training.
  • Heads-up No-limit Texas Hold’em: Table 1 evaluates ReBeL against BabyTartanian8, Slumbot, LBR, and top human expert Dong Kim in thousandths of a big blind per game.Kim played 7,500 hands, and AIVAT was used to reduce variance.
  • Liar’s Dice: ReBeL converges to an approximate Nash equilibrium across several Liar’s Dice variants.Table 2 covers four variants, comparing full-game tabular baselines with ReBeL using depth-2 subgames and 1,024 search iterations; reported exploitability values are upper bounds.
  • Liar’s Dice: Tabular CFR performs better than ReBeL with the same number of iterations, but quickly becomes intractable as the game grows.This comparison frames ReBeL’s practical advantage in larger games despite the tabular baseline’s stronger matched-iteration performance.
  • Turn Endgame Hold’em: Figure 2 compares perfect-value, self-play value, self-play value/policy, and random-belief techniques for convergence in TEH.The self-play value/policy method additionally uses a policy network to warm-start CFR, whereas random beliefs train from randomly sampled PBSs.

9 Conclusions

The paper presents ReBeL as a general self-play reinforcement-learning and search framework for imperfect-information games, with theoretical and empirical success. Its main scope limitation is computational scaling with public-state infostates and guarantees restricted to two-player zero-sum games.

  • Conclusion: ReBeL generalizes self-play reinforcement learning and search to imperfect-information games.The paper proves approximate Nash convergence in two-player zero-sum games and demonstrates convergence in Liar’s Dice and superhuman HUNL performance.
  • Limitations: ReBeL’s value and policy inputs grow linearly with the number of infostates in a public state, becoming intractable in games such as Recon Chess.Its theoretical guarantees are also limited to two-player zero-sum games.
  • Conclusion: ReBeL achieves low exploitability and superhuman HUNL performance while using far less expert knowledge than prior bots.The authors characterize this as a step toward universal techniques for multi-agent interactions.

Broader Impact

The paper positions ReBeL as a general approach for imperfect-information games, with theoretical and algorithmic contributions alongside broader applications and implementation choices.

  • Contributions: ReBeL is presented as the central contribution for reinforcement learning with search in general two-player zero-sum imperfect-information games.The paper contrasts this scope with prior work focused on perfect-information games, cooperative imperfect-information games, or limited zero-sum subsets.
  • Contributions: Theorem 3 provides an alternative to safe search techniques when an accurate PBS value function is available.Sampling a random iteration and passing down that iteration’s policy-generated beliefs can empirically produce Nash-equilibrium play.
  • Contributions: CFR-AVG offers a theoretically sound alternative to CFR-D for depth-limited subgame solving, although the experimentally modified version lacks a known soundness guarantee.The paper explicitly leaves the theoretical status of its efficient poker modification open.
  • Contributions: Theorem 1 connects PBS gradients with infostate values, showing that the algorithms can theoretically use V1 rather than a vector-valued ˆv.The connection suggests possible deployment in settings with billions or more infostates per PBS, but the paper says it has no immediate practical consequences.
  • Contributions: FLOP empirically achieves near-O(1/T) convergence in the limit in both poker and Liar’s Dice and outperforms previous fictitious-play variants.The paper also reports FLOP as a reasonable alternative to CFR in some domains.
  • Applications and implementation: The poker experiments use randomized stack sizes, bet sizes, and board cards during training while measuring exploitability on a fixed $20,000 setting.TEH still contains roughly 2 · 10^11 infostates without randomized stack and bet sizes; the implementation uses self-play data and poker-specific information-abstraction choices are discussed separately.

E.1 Human Experiments for HUNL

The human HUNL experiment evaluated ReBeL against professional player Dong Kim under a 7,500-hand setup. Kim’s reported scores were losses, with substantial uncertainty reflected by the standard errors.

  • Human evaluation: The evaluation compared the HUNL agent with Dong Kim, a top human professional who had previously played against Libratus.The paper notes that high variance prevented statistical comparison among the individual humans from that competition.
  • Experimental setup: 7,500 hands were played, with Kim choosing his schedule and playing up to four simultaneous games against the bot.Compensation was tied to the average win/loss rate in big blinds per hundred hands, subject to stated minimum and maximum payments.
  • Experimental setup: No decision required more than 5 seconds, and the bot averaged faster than 2 seconds per hand in self-play.Preflop subgames were cached so previously encountered subgames could reuse their computed solutions.
  • Value-function proof: The value function is treated as concave in player 1’s belief distribution, and policies attaining the equilibrium value are identified with Nash-equilibrium policies.The proof uses the fact that a minimum of linear functions is concave.
  • Value-function proof: Theorem 1 relates an infostate value to the PBS value and a supergradient evaluated in the infostate direction.The theorem’s formulation uses an extension of the value function to unnormalized belief distributions.

G Proofs Related to Subgame Solving (Theorems 2 and 3)

The proofs establish convergence guarantees for ReBeL’s depth-limited subgame solving: with increasing CFR iterations, the resulting policies approach Nash equilibrium, while test-time value error contributes additively to exploitability.

  • Theorem 2: As N →∞, Algorithm 1 computes an infostate value vector that is a C√T-Nash equilibrium for a game-dependent constant C.The result applies to a depth-limited subgame rooted at PBS βr.
  • Proof strategy: The proof relates Algorithm 1 to CFR-D by replacing value-network calls with recursive CFR-D calls and using induction over subgames.The base case is a subgame extending to the end of the game, where CFR provides the convergence guarantee.
  • Proof strategy: Leaf PBSs unreachable with positive probability do not affect CFR or root infostate values because CFR weights them by reach probability.This removes irrelevant leaf values from the inductive argument.
  • Theorem 2: With T CFR iterations per subgame, the idealized value approximator produces values corresponding to a C√T-Nash equilibrium.The guarantee follows by repeatedly applying the subgame result from the root through the game’s finite levels.
  • Theorem 3: At test time, value-network error at most δ and T CFR iterations yield a (δC1 + δC2√T)-Nash equilibrium.C1 and C2 are game-specific constants, and the guarantee assumes no off-policy exploration.
  • FLOP: FLOP is a generalized weakened fictitious-play variant that uses optimistic opponent-average policies and converges to Nash equilibrium as t →∞.It converges faster than standard fictitious play, although Linear CFR and Discounted CFR are usually faster in large-scale games.

I CFR-AVG: CFR Decomposition using Average Strategy

CFR-AVG decomposes search using average strategies, narrowing the value network’s relevant input distribution and preserving CFR-D’s convergence bound. A modified implementation performs better empirically but lacks a corresponding theoretical guarantee in depth-limited subgames.

  • CFR-AVG design: CFR-AVG samples leaf nodes according to πt while defining the sampled PBS using the average policy profile ¯πt.This separates the sampling distribution from the policy represented by the leaf PBS.
  • CFR-AVG design: CFR-AVG differs from CFR-D by rooting each solved subgame at the average policy profile rather than the current policy.Theorem 5 states that CFR-AVG achieves the same convergence bound as CFR-D.
  • Motivation: Because average policies converge toward equilibrium, CFR-AVG lets the value network focus on a narrower input subspace.Combining CFR-AVG with a policy network may narrow that subspace further.
  • Modified CFR-AVG: CFR-AVG’s input-output policy mismatch motivates the modified implementation, whose depth-limited theoretical guarantee is not established despite empirical success.The value-network input corresponds to ¯πt, while its output represents values under πt.
  • Modified CFR-AVG: The modified CFR-AVG uses πt = t¯πt −(t−1)¯πt−1 and is empirically convergent in every tested Turn Endgame Hold’em parameter setting.Its theoretical soundness remains open for depth-limited subgames.
  • Experiments: The modified CFR-AVG outperforms CFR-D with both an oracle value function and a self-play-trained value network in Turn Endgame Hold’em.The theoretically sound CFR-AVG performs worse than CFR-D with the oracle value function.
  • Experiments: On HUNL, the CFR-AVG model won against BabyTartanian8 by 9 ± 4, while the CFR-D model lost by 10 ± 3.Against Slumbot, CFR-AVG won by 45 ± 5 versus 39 ± 6 for CFR-D.
Loading 2007.13544v2…