No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embedding

AI summary

Overview

Research area: Artificial Intelligence / computational game theory — specifically no-regret learning for solving large-scale imperfect-information extensive-form games (IIEFGs), with poker (no-limit and limit Texas Hold'em) as the test domain.

Technical level: Advanced. The paper assumes familiarity with Counterfactual Regret Minimization (CFR), regret matching, information set abstraction, Nash equilibrium, and exploitability.

One-sentence scope: The paper proposes Embedding CFR, which replaces discrete many-to-one information set clustering with a pre-trained low-dimensional embedding of information sets, and shows faster exploitability convergence than cluster-based abstraction algorithms at equal spatial overhead.

What This Paper Is About

Solving huge games such as no-limit Texas Hold'em is blocked by a space problem: heads-up limit Texas Hold'em alone has approximately 10^13 information sets and would demand 523 terabytes of RAM for direct CFR (Johanson 2013). The dominant workaround, information set abstraction, groups similar information sets into discrete equivalence classes, but its hard many-to-one mapping discards the quantifiable subtle differences between information sets and introduces arbitrary classification boundaries. This paper's goal is to preserve those subtle distinctions by pre-training each information set into a low-dimensional continuous vector — an embedding coordinate forming a probability distribution — and then running regret accumulation and strategy updates inside that embedding space.

Key Contributions

1. First pre-trained embedding abstraction for poker AI. To the authors' knowledge, this is the first work in poker AI development to use a pre-trained embedding approach for information set abstraction, rather than discrete clustering.
2. A no-regret solving framework under information set embedding. The paper formalizes strategy solving inside an advisor/embedding space and provides an approximate analysis of its ability to decrease regret (Proposition 1).
3. A concrete poker instantiation. The authors apply Embedding CFR to poker AI and propose an embedding construction algorithm for poker, including an info-block partitioning rule based on chance actions and the reuse of embedding matrices across corresponding info-blocks.
4. Empirical comparison against existing abstraction methods. Experiments compare Embedding CFR against EHS, PaEmd (the information set abstraction algorithm adopted by Libratus), and the recent KrwEmd.

Main Findings

• Embedding outperforms clustering at equal cost. With the same spatial overhead, Embedding CFR achieves significantly faster exploitability convergence compared to cluster-based abstraction algorithms.
• Lower exploitability under matched budgets. The strategy solved by Embedding CFR has lower exploitability than the compared abstraction algorithms under the same spatial overhead and the same number of update iterations.
• Continuous coordinates preserve similarity and distinction simultaneously. Embedding coordinates let similar hands (e.g., the flop hands 9s^p As^p 9h Js Qs and Ts^p As^p Th Js Qs, both pairs) sit close together and yield similar strategies, while remaining distinguishable from a much stronger hand (Ks^p As^p Ts Js Qs, a straight flush at the flop).
• Space complexity is reduced from O(n·|A(J)|) to O(m·|A(J)|). Instead of storing n distinct strategies per info-block J, the extended abstraction stores m advisor strategies; when m < n this is a strict saving. The full Embedding CFR iteration operates with O(m) space complexity.
• Traditional abstraction is a special case. If each infoset's aggregation function is an identity mapping onto a single advisor, extended information set abstraction coincides exactly with traditional information set abstraction.
• Regret decrease is provable for an isolated advisor. Proposition 1 shows that when S_p^T (the summed squared embedded positive cumulative regret of advisor e_p) is at or below the threshold n|A(J)|·Δ_J^2·||Φ_{p,·}||2^2 / T, then S_p^{T+1} is bounded by n|A(J)|·Δ_J^2·||Φ{p,·}||_2^2 / (T+1); otherwise S_p^{T+1} ≤ (T/(T+1))·S_p^T, i.e., still decreasing.
• Convergence guarantees in the full setting are explicitly not claimed. The authors state that establishing convergence of cumulative regret in the original space is non-trivial (embedding loses information), and that proving stable convergence to zero for a single advisor when all advisors interact simultaneously is also challenging, because advisor updates are mutually interdependent.
• Advisor strategy is approximated by sampling. Regret embedding is framed as a sampling process and strategy recovery as a query procedure, activating only a subset of l < n infosets per iteration.
• Specific experimental numbers are not reported in the provided content. The truncated text does not give the game variant used in experiments, the number of iterations, the embedding dimension m, or numeric exploitability values.

Methodology in Plain English

The authors keep CFR's basic loop — interact with the game, accumulate regret, update strategies by regret matching — but change what the strategies are stored against.

• Replace buckets with advisors. Instead of mapping many information sets to one bucket with one shared strategy, they associate a group of information sets (an "info-block" J) with m "advisors" E = {e_1, …, e_m}, each holding its own strategy over the shared action space A(J). An info-block is a partition of a player's infosets that all share the same action space.
• Attach each information set to the advisors by confidence weights. An m × n embedding matrix Φ holds non-negative entries φ_{p,q} summing to 1 over p for each infoset q. This vector Φ_{·,q} is the infoset's embedding coordinate — a probability distribution over which advisors to trust, exactly like a word embedding vector.
• Map between the two spaces. The strategy at an original infoset is recovered as σ_i^T(J,a) = Φ^T σ_i^T(E,a); regrets are pushed into the advisor space as R^T(E,a) = Φ R^T(J,a), and each advisor updates via regret matching on its own embedded cumulative regret.
• Avoid the full matrix cost. Rather than touching all n infosets each iteration, they sample a small subset of l < n infosets and use an incremental update R̃^T(E,a) = ((T−1)/T)·R̃^{T−1}(E,a) + (1/T)·Σ_k Φ_{·,j_k} r^T(I_k,a). Only advisor-space quantities are stored, giving O(m) space complexity, and each embedding lookup costs O(m).
• Build info-blocks from chance actions. In poker, uncertainty within an infoset comes from chance (card dealing), while betting actions are public. So info-blocks are defined as infosets whose histories share the same non-chance action trace H_{−c}(h). Because two info-blocks linked by identical chance traces are in one-to-one correspondence, the embedding matrix built for one can be directly reused for the other, cutting construction work.
• Validate by experiment. The method is tested on poker against EHS, PaEmd, and KrwEmd using exploitability as the metric (exploitability ε^σ = b_1(σ_2) + b_2(σ_1), lower being closer to equilibrium).

Why This Matters

Impact on research. The paper reframes information set abstraction from a hard classification problem into a representation learning problem, importing the word-embedding paradigm from NLP into game solving. It also supplies an extension of the abstraction definition (advisors plus aggregation functions) in which traditional clustering is a strict special case, giving the field a more general formalism to build on. If the reported convergence gains hold, this suggests that the "abstraction–solving–translation" paradigm's losses are partly attributable to binarized grouping rather than to abstraction itself.

Real-world applications:

• Poker AI and computer poker agents — building or improving bots for limit and no-limit Texas Hold'em, and benchmarking them against systems such as DeepStack, Libratus, and Pluribus.
• Security and resource allocation games — the same IIEFG equilibrium machinery is used for randomized patrol scheduling, airport and port screening, and other Stackelberg-style security games where huge decision spaces must be compressed.
• Negotiation and auction agents — bidding and bargaining scenarios with private information have the same imperfect-information extensive-form structure.
• Memory-constrained decision systems — any setting where an equilibrium-quality policy must fit into a fixed memory budget and per-decision lookup cost matters.

Industry relevance. The core selling point is a better quality-per-byte trade-off. Any deployment that must store strategies for millions of decision points under a memory cap — game AI, automated negotiation, security randomization — benefits from replacing fixed buckets with compact continuous vectors. The released code at https://github.com/PhilEnchan/EmbeddingCFR lowers the barrier to reproducing and extending the approach.

Future Directions

• Close the convergence gap. The authors flag two unresolved challenges: bounding cumulative regret in the original space (which depends on how well Φ is constructed, and degenerates when all infosets trust a single advisor), and proving stable convergence to zero for a single advisor while all advisors interact.
• Learn the embedding matrix instead of hand-building it. The current pipeline pre-trains Φ from poker domain knowledge and chance actions; whether Φ could be learned end-to-end, or adapted per game, is left open.
• Generalize beyond poker. The info-block partitioning rule exploits poker's structure (public non-chance actions, chance-driven uncertainty) and the paper notes that constructing partitions is non-unique and requires game-specific analysis. Extending the rule to other IIEFGs is an open question.
• Tune and characterize the embedding dimension and advisor count. The relationship between m, the number of advisors per info-block, and solution quality is a natural axis to explore, especially since the paper's failure case is precisely when infosets collapse onto too few advisors.

Target Audience

Researchers and graduate students in computational game theory, multi-agent reinforcement learning, and equilibrium computation who already know CFR and information set abstraction. It is also relevant to engineers building memory-constrained poker or security-game solvers who want a drop-in abstraction improvement, and to NLP-adjacent readers interested in seeing the embedding paradigm transferred to a non-language domain. Readers without a background in extensive-form games and regret minimization will find the notation-heavy formalism hard going.

Authors’ abstract

High-quality information set abstraction remains a core challenge in solving large-scale imperfect-information extensive-form games (IIEFGs)--such as no-limit Texas Hold'em--where the finite nature of spatial resources hinders solving strategies for the full game. State-of-the-art AI methods rely on pre-trained discrete clustering for abstraction, yet their hard classification irreversibly discards critical information: specifically, the quantifiable subtle differences between information sets--vital for strategy solving--thus compromising the quality of such solving. Inspired by the word embedding paradigm in natural language processing, this paper proposes the Embedding CFR algorithm, a novel approach for solving strategies in IIEFGs within an embedding space. The algorithm pre-trains and embeds the features of individual information sets into an interconnected low-dimensional continuous space, where the resulting vectors more precisely capture both the distinctions and connections between information sets. Embedding CFR introduces a strategy-solving process driven by regret accumulation and strategy updates in this embedding space, with supporting theoretical analysis verifying its ability to reduce cumulative regret. Experiments on poker show that with the same spatial overhead, Embedding CFR achieves significantly faster exploitability convergence compared to cluster-based abstraction algorithms, confirming its effectiveness. Furthermore, to our knowledge, it is the first algorithm in poker AI that pre-trains information set abstractions via low-dimensional embedding for strategy solving.