Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games

Ondřej Kubíček, Viliam Lisý, Tuomas Sandholm · 2026

Read Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games by Ondřej Kubíček, Viliam Lisý, Tuomas Sandholm (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17131.txt.

Introduction

Ondřej Kubíček, Viliam Lisý, and Tuomas Sandholm sharpen game play by use of fine tie rules. Big games are played from a pre-set plan, then tuned live. In hid-fact games, the live tune must weigh unseen states. It must also weigh the foe's past plan. Their 2026 preprint adds equilibrium refinements to that tune step. Such refinements pick the best of tied best replies.

Fine picks can lift the tune past the base plan. They curb plays that a smart foe could exploit. Games here span cards, bids, and guard work. Sharp subgame tools push AI skill in all three.

Catalog record

CREATOROndřej Kubíček, Viliam Lisý, Tuomas Sandholm
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-17131

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games Ondřej Kubíček, Viliam Lisý, Tuomas Sandholm Abstract Subgame solving is a technique for scaling algorithms to large games by locally refining a precomputed blueprint strategy during gameplay. While straightforward in perfect-information games where search starts from the current state, subgame solving in imperfect-information games must account for hidden states and uncertainty about the opponent’s past strategy. Gadget games were developed to ensure that the improved subgame strategy is robust against any possible opponent’s strategy in a zero-sum game. Gadget games typically contain infinitely many Nash equilibria. We demonstrate that while these equilibria are equivalent in the gadget game, they yield vastly different performance in the full game, even when facing a rational opponent. We propose gadget game sequential equilibria as the preferred solution concept. We introduce modifications to the sequence-form linear program and counterfactual regret minimization that converge to these refined solutions with only mild additional computational cost. Additionally, we provide several new insights into the surprising superiority of the resolving gadget game over the max-margin gadget game . Our experiments compare different Nash equilibria of gadget games in several standard benchmark games, showing that our refined equilibria consistently outperform unrefined Nash equilibria, and can reduce the exploitability of the overall strategy by more than 50%. 1 Introduction Settings where parties such as people, companies, or nations interact are ubiquitous, and game theory provides the solution concepts of how the parties should act rationally. It is therefore of significant real-world importance to be able to compute (approximate) game-theoretic solutions to large games. Recreational games have often served as computational benchmarks for this purpose. In perfect-information games, real-time subgame solving techniques have been the core of game-solving algorithms since the beginning of AI. Algorithms like minimax, alpha-beta search, or Monte Carlo tree search, explore the subgame tree from the single current state of the game forward ( 24 ; 25 ) . However, most real-world settings are imperfect-information games. They present challenges that those algorithms cannot address. There are several real states consistent with a single decision point. Consider poker as an example. The player can see their own cards but not the opponent’s. So, each possible opponent hand defines a different state, yet they appear the same from the player’s perspective. Furthermore, changing a part of an agent’s strategy at some point of a game typically changes what that agent’s optimal strategy is later and earlier in the game. Thus, a subgame cannot be solved based solely on information from that subgame. Therefore, unlike in perfect-information games where subgame solving was a core technique from the outset, imperfect-information games where approached as a monolithic whole for the longest time. Real-time subgame solving started relatively recently ( 9 ) . Since then, a host of better and better subgame solving techniques have been developed ( 10 ; 5 ; 8 ; 20 ; 19 ; 2 ; 3 ; 4 ; 29 ; 13 ; 22 ; 30 ) . In fact, subgame solving has made the central difference in achieving superhuman play in games such as two-player no-limit Texas hold’em poker ( 3 ) , multi-player no-limit Texas hold’em ( 4 ) , and dark chess (aka. Fog-of-War chess) ( 30 ) . A common approach is to compute a coarse blueprint strategy for each agent for the entire game, and then to conduct subgame solving on the fly to refine the blueprint strategy. Gadget games were developed to compute robust strategies in the subgames. These are modifications of the subgame that allow the opponent to adversarially choose a strategy it could have played in the past. The resulting optimal strategy of the player in such a gadget game is robust against any past strategy of the opponent ( 5 ; 20 ; 2 ) . However, existing gadget constructions, such as resolving and max-margin , only ensure that the player’s strategy, in the worst case, is no worse than the blueprint. As a result, if the blueprint is poor, all of these methods may yield poor results. We make the following contributions. 1. We show that different equilibria, which all yield the same value in the gadget game, have vastly different performance (exploitability) in the full game, when combined with the blueprint. We introduce a weaker notion of sequential equilibrium, gadget game sequential equilibrium , which is easier to compute, and propose that gadget games should be solved according to this concept. 2. We disprove the widely held belief that max-margin gadget games are strictly superior to resolving gadget games. This provides a new understanding of some prior works that have used the resolving gadget game for subgame solving rather than max-margin ( 19 ; 30 ) . 3. We introduce efficient modifications to the sequence-form linear program (SQF) and counterfactual regret minimization (CFR) that converge to these refined equilibria with minimal additional computational overhead. 4. We empirically evaluate different types of Nash equilibria in several standard benchmark games. The results show that converging to gadget game sequential equilibria can reduce exploitability by more than 50% compared to vanilla SQF and CFR. Moreover, the results show that in resolving gadget games, these equilibria exhibit similar performance gains as using unsafe subgame solving, but provably without the risk of performing worse than blueprint. 2 Background and Notation Two-player zero-sum factored-observation stochastic game is \mathcal{G}=(\mathcal{N},\mathcal{W},w^{\text{INIT}},p,\mathcal{A},\mathcal{T},\mathcal{R}_{1},\mathcal{O}) , where \mathcal{N}=\{1,2,c\} is a set of players and c is a chance player, which plays fixed strategy and it is used to model stochasticity of the environment. \mathcal{W} is the set of world states and w^{\text{INIT}}\in\mathcal{W} is an initial world state. p:\mathcal{W}\to 2^{\mathcal{N}} is a function that assigns acting players to a given world state w . \mathcal{A}=\prod_{i\in\mathcal{N}}\mathcal{A}_{i} is the set of joint actions, we also use \mathcal{A}_{i}(w)\subseteq\mathcal{A}_{i} to denote legal actions of i in state w . \mathcal{T}:\mathcal{W}\times\mathcal{A}\to\mathcal{W} is a transition function and \mathcal{R}_{1}:\mathcal{W}\times\mathcal{A}\to\mathbb{R} is a reward function of player 1 . In a zero-sum setting following holds \mathcal{R}_{2}(w,a)=-\mathcal{R}_{1}(w,a) . \mathcal{O}:\mathcal{W}\times\mathcal{A}\times\mathcal{W}\to\mathbb{O} is the observation function and \mathbb{O}:\mathbb{O}_{0}\times\mathbb{O}_{1}\times\mathbb{O}_{2} is the set of joint public observations and private observations. Similarly, observation function can be factored as \mathcal{O}=(\mathcal{O}_{0},\mathcal{O}_{1},\mathcal{O}_{2}) , where \mathcal{O}_{0} is a public observation given to each player and \mathcal{O}_{1},\mathcal{O}_{2} are private observations available to their respective players ( 12 ) . History h=w^{0}a^{0}\dots a^{l-1}w^{l}\in(\mathcal{W}\mathcal{A})^{*}\mathcal{W} is a finite sequence of world states and actions, which starts in the initial state w^{0}=w^{\text{INIT}} and each timestep t\in\{0,\dots,l-1\} is a valid transition w^{t+1}=\mathcal{T}(w^{t},a^{t}) . \mathcal{H} is a set of all possible histories in a game \mathcal{G} . We use h\sqsubseteq h^{\prime} to denote h^{\prime} that contains h as a prefix and we will denote the initial history as h^{\text{INIT}}:=w^{\text{INIT}} . Every history ends with some world state w^{l} , we will often use history in the game functions instead of that world state, for example \mathcal{A}(h):=\mathcal{A}(w^{l}) . The players do not observe the whole world state at each timestep, but they only observe public and their corresponding private observations. As a result, the player may not distinguish several different histories. s_{i} is an information set of the player, which is a set of all histories consistent with the observations of player i . \mathcal{S}_{i} is then set of all information sets.

Read the complete text