History Filtering in Imperfect Information Games: Algorithms and Complexity
Authors: Christopher Solinas
Doug Rebstock
Nathan R. Sturtevant
Michael Buro
Venue: NeurIPS 2023 poster (2023)
Keywords: search
game theory
multi-agent
learning
markov chain monte carlo
complexity

Abstract: Historically applied exclusively to perfect information games, depth-limited search with value functions has been key to recent advances in AI for imperfect information games. Most prominent approaches with strong theoretical guarantees require *subgame decomposition* - a process in which a subgame is computed from public information and player beliefs. However, subgame decomposition can itself require non-trivial computations, and its tractability depends on the existence of efficient algorithms for either full enumeration or generation of the histories that form the root of the subgame. Despite this, no formal analysis of the tractability of such computations has been established in prior work, and application domains have often consisted of games, such as poker, for which enumeration is trivial on modern hardware.

Applying these ideas to more complex domains requires understanding their cost. In this work, we introduce and analyze the computational aspects and tractability of filtering histories for subgame decomposition. We show that constructing a single history from the root of the subgame is generally intractable, and then provide a necessary and sufficient condition for efficient enumeration. We also introduce a novel Markov Chain Monte Carlo-based generation algorithm for trick-taking card games - a domain where enumeration is often prohibitively expensive. Our experiments demonstrate its improved scalability in the trick-taking card game *Oh Hell*.
These contributions clarify when and how depth-limited search via subgame decomposition can be an effective tool for sequential decision-making in imperfect information settings.

History Filtering in Imperfect Information Games: Algorithms and Complexity
Christopher Solinas' Douglas Rebstock', Nathan Sturtevant 1.2 Michael Buro
DDpartmeett of Computing Science, University of Alberta 2 Alberta Machine Intelligence Institute (Amii)
{solinas, drebstoc, mathanst, hoctiianstmuuuro//oo
Abstract
Historically applied exclusively to perfect information games, depth-limited search with value functions has been key to recent advances in Al for imperfect information games. Most prominent approaches with strong theoretical guarantees require subgame decomposition-a process in which a subgame is computed from public information and player beliefs. However, subgame decomposition can itself require non-trivial computations, and its tractability depends on the existence of efficient algorithms for either full enumeration or generation of the histories that form the root of the subgame. Despite this, no formal analysis of the tractability of such computations has been established in prior work, and application domains have often consisted of games, such as poker, for which enumeration is trivial on modern hardware.
Applying these ideas to more complex domains requires understanding their cost. In this work, introduce and analyze the computational aspects and tractability of filtering histories for subgame decomposition. We show that constructing a single history from the root of the subgame is generally intractable, and then provide necessary and sufficient condition for efficient enumeration. We also introduce novel Markov Chain Monte Carlo-based generation algorithm for trick-taking card games-a domain where enumeration is often prohibitively expensive. Our experiments demonstrate its improved scalability the trick-taking card game Oh Hell. These contributions clarify when and how depth depth-limited search via subgame decomposition can be an effective tool for sequential decision-maie making imperfect information settings.
Introduction
Games standard model for sequential decision-making. As the number of sequential decisions needed to play increases, the size of the game's ' state space can grow exponentially-quiee large search exhaustively. Depth-limited search navigates this issue by replacing decision points below a certain depth with a value function that captures or approximates the value of playing the subgame from that position onward. This can massively boost scalability and has been key to several famous results in perfect information games including Checkers (Schaeffer and Lake (199)). Chess (Campbell al. [2002)) and Go (Silver er al. [2017]).
becoming
The same idea has recently been successfully applied to certain imperfect information games such as poker (Brown and Sandholm [2019]; Moravčík et at. (2017) achieving similarly impressive results by defeating human experts. In contrast to the perfect information setting, for which computing the value function only requires evaluating the current history, most successful depth-limited search algorithms in imperfect information games require evaluating whole sets of histories and their reach probabilities. This information is used to generalize the concept of subgame and its value
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

by decomposing the game tree into public belief states, which are analogous to belief states in Markov systems such as Hidden Markov Models (HMMs) and Partially Observable Markov Decision Processes (POMDPs). This approach is commonly referred to as subgame decomposition; we describe the associated history and reach probability computations as history filtering. Although current theory establishes the necessary information for theoretically sound depth- search in imperfect information games (Kovařík et al. (2020]), it is unclear how, or if, this information can be computed efficiently. Understanding these computations provides insight into scaling search to larger, more complex imperfect information games.
In this work, we define variants of history filtering for subgame decomposition that are useful for search-calle enumeration and generation- solving them. Efficient solutions should take at most polynomially many steps in the length of the input observation sequence. We show that, in general, such algorithms only exist if NP. From there, we investigate methods for efficient enumeration and generation. First, by identifying a structural property of the game tree that is both a necessary and sufficient condition for efficient enumeration, and then by introducing novel, unbiased generation algorithm for trick-taking card games, based on Markov Chain Monte Carlo. Through experiments in Oh Hell, we validate its improved scalability and highlight the potential advantages of this approach. Our contributions advance the theory of lepth-limited search in imperfect information domains.
also developing a suitable notion for efficiently
2 Background
In this section, summarize the concepts and algorithms related to history filtering and public belief states.
2.1 Factored Observation Stochastic Games
The recent introduction of Factored Observation Stochastic Games (FOSGs) (Kovařík et al. (2019) has helped clarify fundamental concepts about decomposing public and private observations and information in multi-agent, partially-observable sequential decision problems.
An FOSG is tuple
(N, W, P. w A,,, N {1. .... N) represents the set of players,
W is the set of world states, and A is the set of joint actions. p : W - 2 is the player function, which describes which players act in which world states. T W- x A + AW is the state transition function, where AW represents the set probability distributions over W. R : W x A + R assigns reward each player, and O W x AAx x W + O is the observation function which maps transitions (world state-action- world state triples) to private observations for each player and a public observation common to all players.
Games start at the initial world state wº. In any world state w W, player acts when i E P(w). The joint action set A == The A; is defined as the product of each player's individual action sets across all w E W. (w) C A, denotes the legal actions for in w, and A(w) = IIεP(w)) A((w) is the set of legal joint actions in w. Play proceeds when each i E P(w) chooses an action a; A(ww) (w) resulting in joint action a := (a: (a))EE(()); a E A(w). The next state w' is sampled from T T(w, a). while the reward is determined by evaluating R(w, a). Finally, Olw, a, w') is factored into public and private observations as (O (Opiv(1)(uu) (W) (w.a, a, w ), ..., O (N a, w w²), O Opb (w, a, w')).
2.2 Policies, Reach Probabilities, and Beliefs
A history sequence h (w a w² at ..., w²) of world states and actions for which w* W. at A(w=*, and IP[ a² w++l 0 for k, < k < t 1. We refer to [h] := as the length of ht The set of all legal histories is denoted as H. We use the standard notation N/ C h to denote that h' is a prefix history of h (i.e., h is subsequence of i starting w and ending in world state). A terminal history 2 E Z signifies that play has reached a world state where the game ends. The utility for player i, u, 2 IR is the of all rewards accumulated by over the world state and action sequence.
A history h produces a public state, which is the sequence of public observations Spus (h) (Oprd O2 Opubr.... ..., (prut) produced along the trajectory with 0 := Opusl (pus(w*= (w- a k-1 w². We

---

Figure 1: The same history viewed in the world state tree (left) and the public tree (right). Grey boxes are public states, which can be consistent with many histories from the world state tree.
player
hg
h
h2
player 1
S
Figure 2: (Left) An example public belief state in two-player game with ranges Tı and r2. S is consistent with set of 5 histories. Player I's range contains two private information states. (Right) player's beliefs (top) and joint range (bottom). Player I's beliefs, given the first private infostate, consist of reach probabilities for the individual histories in the infostate. The joint range consists of reach probabilities over all histories in S.
denote a public state generated by an unknown history as S E S, where S is the set of all public states (and the vertex set of the public tree, Figure [ Likewise, player i's pri- vate information state S; E S; similarly captures the sequence of observations seen only by that player: s:(h) :- (O), O.,...,0. O,), where O (prse(s) (w*=1, 1aok-1,a-1_, , Taken together, (h) (h)) represents all information available to player at history h, and is referred to the player's information state or infostate. S,(S) denotes the set of all infostates consistent with public state S and is partition of S. We use H.s (h H (h) = S} to denote the set of histories consistent with public state S. Since all players receive (possibly empty) observations at every world state transition, this formalism avoids non-timeabillty and thick infostates present in the extensive form. See Kovařík et al. 22200) for details.
- which maps player i's infostates to the set of probability distributions over action set A. A joint policy क = (#1, Tn) is a tuple consisting of every player's policy. The reach probability of history under is p (h) (h(h) PT (h) (h)...P7 (h) where each P.T (h) is product of action probabilities taken by player i to reach h from w and Pa(h) is the product of all probabilities from chance transitions taken according to the stochastic transition function T. The reach probability of an infostate (or public state) S; under can be expressed as PM (S;) EnES, PE (h)) Infostate reach probabilities can also be decomposed into pm (S.) p. (S.) (S.) where -i denotes all players except Since all h E S, are indistinguishable to i, P. (S.) = (h)),, whereas (S. Ene (h) (Koväřík) et al. (2020).
A player plays according
policy
Kovarik et al. 2020 define a belief under joint policy π as the probability of reaching a history h given the current infostate Sj: for any h E H.s. pa (h(S,) = pM (h) (h) pa (h'). The
contains each range for a joint policy и at public state S, r (S) == (S.)) (S.)) (.s()))sss...)))))1.............
player's reach probabilities for their infostate partition of S. The (normalized) joint range pa (M)S)) contains the normalized reach probabilities of all h E S. These concepts are visualized in an abstract game in Figure 2 Our analysis focuses on history filtering with respect to the joint range-assume the joint policy is constant and known by all players.
3

---

2.3 Depth-Limited Search, Subgames, and Belief State Computation
Several depth- limited search algorithms, such as Information Set Monte Carlo Tree Search (ISMCTS)
(Cowling al. [2012)) Player of Games (Schmid et al. (20TT). D. and ReBel (Brown et al. (2020)) require methods for simulating actions and state transitions. In these algorithms, search starts from a ground Iruth h plausible state of the game-and proceeds until depth limit; value functions
represent the players' expected reward in the subgame below.
Subgames and their value functions are intuitive in the perfect information setting because they can be rooted at any non-terminal history. However, the necessary information for computing value functions in the imperfect information setting is structured differently. Subgames are instead rooted at public belief states (PBS), which are tuples 3 := (S, r (S)) composed of a public state and a range. Searching from requires computing histories from Hs because the actions and transitions necessary for forward simulation are defined for world states, not public states, and computing optimal value functions the subgame leaves requires ranges defined over all histories in H.s (Kovařík er
al. 2020). Player of Games (Schmid et al. [222]) opts for the Monte Carlo approach, which generates h E Hyy for player by sampling an infostate from S, (() according to i's component r (S), and then sampling according to their beliefs Pa (h[S.) (see Figure 2 for the distinction).
ISMCTS (Cowling al. 2012)) is similar, but instead samples directly from the normalized joint range P (A])). Either case depends on solving a common computational problem: histories from His must be sampled according to TT (S), given only S and π.
Belief state computation is an important topic in general Markov systems with partial observability. As such, it appears frequently in areas such stochastic control (Nayyar et al. (2013), learning in decentralized POMDPs (Dibangoye et al. 2016]; Olichoek (201 D. and multi aggent reinforcement learning (Fickinger
generalization of POMDPs, search techniques that use public belief states have also been crucial to the development of superhuman poker AI (Brown and Sandholm [019]; ; Brown el al. (2020): MMoavčík et al. [2017); /Schmid el al. 202T)). ). In card game AI, Perfect Information Monte Carlo (PIMC) search was successfully applied to Contract Bridge (Levy] 1989); Ginsberg
al. [2021]). In FOSGs, which
(001]) and later Skat (Buro et al. (2009) ). Both applications rely on game-specific implementations for history filtering. Richards and Amir [2022] described the
problem as information set generation and provided the first generic, but exponential- time, algorithm for solving it. Seitz et al. [202T] provided an algorithm for approximating information set generation based on deep neural networks. Sustr el al. [2021] identified that exponential-sized Hy cause memory issues in methods that explicitly represent the range, and that efficient search requires the range be represented compactly.
Recently, the idea of fine-tuning has helped push the scalability of planning in POMDPs via reinforce- ment learning (Fickinger et al. (2021]) and search in FOSGs (Sokota et al. 2021)) by eliminating
the need explicitly represent the range. In reinforcement learning, tine-tuning consists of online updates to a parameterized model a blueprint policy or Q-value function using sample trajectories with fixed horizon. These local improvements to the model helped train policies which achieved new state-of-the-ard in self-play Hanabi (Fickinger et al. (202T). ). Belief fine-tuning (BFT) (Sokota ei al. 202T)) extended the idea to PBS approximation without pre-training the generative model function of the joint policy π.
In some domains, it is unclear how to structure dynamics model for fine-tuning such that only legal sample historics are produced. For example, in trick-taking card games, the public observation sequence could indicate that certain players cannot possibly have certain cards in their hands; all histories output by the model should satisfy this constraint. Our approach uses only the dynamics model defined by the game. It is parameter-free and instead calls for simple domain-specine algorithms for history construction and neighbor generation in a Markov chain. This results in unbiased history generation and guarantees that any sample history is legal according the game rules.
3 History Computation in Public Belief States
Our first contribution is to introduce a family of history filtering relations FILTER(G, x) which formalize this computation for given FOSG G and joint policy n. For simplicity, we limit our

---

analysis to FOSGs with finite world state sets W and action sets A, and joint policies that can be evaluated in polynomial time with respect history length.
3.1 Family Filtering Relations
Computing histories from given public state is special case of particle filtering, name family of relations FILTER.
Definition 1. (FILTER) For any FOSG G with finite W, A and joint policy n, let FILTER(G, m) = ((S,h) E Ex Σ" Spub(h)) S S, Pa (h|S) > 0}.
An FOSG G and a joint policy parameterize the relation-which pairs public states S E S and histories consistent with S. S is treated the problem input (encoded using alphabet Σ) and reachable histories from Hy are valid outputs.
Our definition treats the FOSG G and the joint policy fixed and assumes that the FOSG functions (T, A. etc.) and the policy can be evaluated in polynomial time with respect to their inputs, and are not encoded as inputs to the problem. Thus, the input and output sizes of problem instance the lengths of the encoded observation sequence and history, respectively.
A relation R C Σ" x Σ" over alphabet Σ is polynomially balanced if there exists polynomial such that for all () E R.
lyl S p((==) (i.e., the length of output y at most polynomial the input verifiable if the predicate (ar, y) E R (a: Ry for short) can tested polynomial time. Lemma] 7 states that this is the case for FILTER(G, T) with finite W and A. Finite W and A imply polynomial balance and polynomial-time verification is done using //| evaluations of the observation function and policy to check if is produced and the reach probability is nonzero. All proof's are in the appendix.
length) (Jerrum el al. (1866) R is polynomial-ting
Lemma 1. For any FOSG G with finite W. A and arbitrary joint policy FILTER(G, π) is polyno- mially balanced and polynomial-time verifiable.
3.2 Computational Problem Variants
For binary relation R, there are several naturally associated computational problems. Given problem instance x E Σ", some these are:
1. Existence: Is there a E Σ" such that x: Ryy?
2. Construction: Return y E Σ* such that #Ry if one exists.
3. Generation: Generate a y E Σ* such that Ry according to some predetermined distribution
over the solution set {y E Σ" xRyy if one exists.
4. Counting: Compute Hy E Σ" x Ryyy H-
5. Enumeration: Return all y Σ* such that zRy.
Of these, generation and enumeration are clearly relevant to history filtering. Prior work (Schmid er al. [021]): Brown al. [2020); Moravěík et al. (2017) Brown and Sandholm (2019) has generally relied on enumerative methods, i.e. filtering histories by explicitly representing the entire PBS. Generative methods for history filtering potentially have the advantage of avoiding explicit PBS representation. In the next section, we analyze the computational complexity of problem variants 1-5.
Complexity of Filtering Histories
Efficient (polynomial-tig and space) algorithms for history filtering enable scalable depth- limitei search in imperfect information games. In this section, we provide an FOSG instance where the construction variant of FILTER intractable and explain when efficient enumeration is possible.
4.1 FNP-Completeness of Construction
Consider the following two-player FOSG, based on Functional Boolean Satisfiability (FSAT):
5

---

Definition 2. (3-FSAT-GAME) For given integer m, world states are encoded as m-variable truth assignments. Starting at initial state w player I chooses an action a (y1, y2. .... Vm that represents truth assignment. This is followed by a transition to some encodes the same assignment. Opaalu" (w, d. , w) reveals no public information about the transition to except that the action and transition occurred. w has joint action set A(w) == {a} and T(w, a) := w for all u E W. Rewards are arbitrary. When action a is taken at time t, the public observation function puub (W, a, w) generates, random, a 3-CNF clause ct that is satisfied by w.
(11, U/,...... ..... ym that
Player I chooses m-variable truth assignment, and then player 2 repeatedly takes arbitrary actions- outputting 3-CNE clause satisfied by the assignment as public observation each time. The truth assignment is unknown to player so solving a 3-CNF Boolean formula is necessary to construct a history consistent with the public observations. Additionally, sequence of observations equivalent to any satisfiable 3-CNF formula over m variables can be generated by playing this game.
Theorem 1. There exists a joint policy π for which the construction problem associated with FILTER 3-FSAT- GAME, π)) is FNP-complete
Theorem ! implies that unless P = NP, computing even a single history corresponding to a given public state in the 3-FSAT-GAME is intractable in the worst case. It follows that the same applies to more complex computations such as generation and enumeration. However, there are several examples where these computations have been successfully performed in practical examples of games such as poker-we discuss where efficient enumeration is feasible next.
4.2 Efficient Enumeration in Games with Sparse Public States
Prior work has often limited application domains to games where the public state is trivially enumer- ated and beliefs can be represented explicitly in physical memory; the efficiency of these algorithms depends on structural property of the game tree that we call sparsity.
Definition 3. The public tree S of an FOSG G is sparse if and only if all public states S = (o+, oz ,..., o²) in S satisfy [Hsl S p(() for some polynomial p. Public trees that do not satisfy this property are dense.
Public states in games with sparse public trees can be enumerated in polynomial time using simple breadth-fire search that makes at most |A x Wlp(k) calls to the observation function at depth (see proof of Theorem 2 in the appendix for more details).
Theorem 2. For any FOSG G with finite W.A, the enumeration problem associated with FILTER(G, π) can be solved in polynomial time if and only if G's public tree is sparse.
As an example, consider the following variants of two-player poker. In Texas Hold' em, there is 52-card deck and two cards are dealt to each player; public states in this game are of constant size. With n cards in the deck where each player is dealt cards, the number of histories per public state polynomial in n. Both of these games have sparse public trees. However, with n cards in the deck and cards dealt to each player, the number of histories is exponential in k; so the public tree is dense.
Sparsity itself does not guarantee that enumeration is feasible on modern hardware. For instance, physical memory and time constraints still prevent enumeration in large trick-taking card games with constant-sizer public states such as Skat and Hearts. In the next section, we propose an algorithm for history generation in these games and validate empirically.
5
MCMC History Generation in Trick- Tikkig Card Games
Trick-taking card games (TTCGs) like Contract Bridge, Skat, and Hearts are played by millions of people worldwide and have historically been of significant interest to the Al community. However, superhuman-leww computer play in these games has yet to be achieved-ing part because of their large public belief states. Here, we devise a Gibbs sampler (Geman and Geman [1944)) for history generation in TTCGs that treats histories as states in a Markov chain and uses local computations to generate histories without explicit belief representation.

---

suits
players
6
3
t
3
2
6
Figure 3: A flow network constructed from a history in a TTCG with three suits and two players. The suits have three, one, and two unknown cards remaining, respectively, and each player must be dealt three more cards. The first player is void in the third suit, and the second player is void in the second suit.
5.1 Challenges of Filtering in TTCGs
Depending on the size of the deck and the number of cards dealt to each player, public states in TTCGs may be large early in the game: up to nl/(n - k)! for decks with cards and & cards dealt in total. They shrink as information is revealed because players must be dealt the cards they play, and void suits (when player reveals they cannot have a certain suit through play) imply certain cards cannot be dealt to certain players. These observations lead to two possible constraints on card being dealt to a player: either must have been dealt to player, or it cannot have been dealt to player. Both can be checked efficiently through single pass over the observation sequence.
5.2 History Construction in TTCGs
The solution to history construction for some S E S is a history h E Hs. This history can serve as an initial state for the Markov process we have designed to solve generation in TTCGs. As now describe, construction can solved in polynomial time using an algorithm for integer maximum flow such Addmonds-Kay (Edmonds and Karp 1972 along with some simple pre- and post-processe processocssiing steps.
Given history h with the subsequence of private actions that represent the deal, E h, we create flow network that captures the constraints of the cards in a. Cards revealed through play must be dealt to the player that played them, so we can ignore them when solving for deals that satisfy the other constraint: where player cannot have any more cards in suit. The source vertex is connected to k suit vertices via directed edges with capacity that corresponds to the number of unknown cards remaining in that suit, Each suit vertex is connected to player vertex if is possible for that player to hold cards of that suit in their hand. The edges connecting the player and suit vertices have capacity equal to the number of total unknown cards remaining in all suits. Finally, the player vertices are connected to the sink via edges that correspond to the number of cards remaining in that player's hand. See Figure for an example.
Lemma 2. For TTCG G and joint policy π with full support, FILTER(GG σ) can solved in polynomial-tine using a maximum flow computation.
Applying a maximum flow algorithm based on augmenting paths will construct integral flows that represent assignments of the number of unknown cards in each suit dealt to each player-which call a suit length assignment. We can select one of possibly many histories that satisfy the suit length assignment (and the cards that have been explicitly revealed through play) and construct history from H.s.
5.3 TTCG Gibbs Sampler
The TTCG Gibbs sampler is Markov Chain Monte Carlo method (see Häggström and others 2002 for an overview) for generative history filtering in TTCGs. It is based on two concepts: Markov chain states are histories from Hss and transitions use unnormalized reach probabilities and involve local modifications to the suit length assignment of the current state.
7

---

Algorithm 1: RingSwap
input : public state, deal consistent with S
output: :Ω2, - set of neighbors of a let Anxm be the suit assignment matrix for
2 Sig < {
for Row in rows( A) do
for Columns j. k. o k in colsí A) do
if void(S, (. void(S, k) or at, 0, continue
C+A
C.j Cij + 1;C, + C, -1
Sr + Ωt BFS((C,) to find all ways to make C valid suit length assignment
end
10 end
return 22
We start by describing the neighbor generation algorithm, RingSwap (Algorithm [ which operates on suit length assignment matrices. Constraints suit length assignments can be encoded using matrix with row and column sums equal to the number of unknown cards in each suit and player hand. Void suits are represented as entries fixed to zero. For example, the following is suit length assignment matrix that satisfies the max flow network in Figure 3
2
211 0 102 2
The rows sum to 3 because each player has 3 unknown cards, and the columns sum to the number of unknown cards in the corresponding suit.
With suit assignment matrix corresponding to a, RingSwap repeats the following for all players i. For every pair of non-void suits and k, perform swap by adding a card to Aij and removing one from Ai,k- The column sums of the matrix are now incorrect (j has too many cards and k has one too few), and must be corrected via a sequence of swaps in other rows. All sequences of swaps of length < n that lead to valid suit length assignments are then computed via BFS and a valid assignment is selected proportionally to the number of histories corresponds to.
We can now describe the TTCG Gibbs sampler. For public state S at time f, given X, = h, deal h, and joint policy with full support all infostates, consider the following Markov chain: At time
1:
1. Compute Ω2, the set of all neighbors of a using the procedure SingSwap(S,,
2. Sample of uniformly from Qg
3. Compute Ω2p and / such that o' J/ by replacing a with o' in form h
4. Let = min (= (=()) (h]R,
5. With probability 2, X W', otherwise X,-1 =
State transitions are done according the Metropolis-Hasting algorithm (Metropolis et al. [1953]: Hastings [970)) with unnormalized reach probabilities pa as μ³ and uniform selection over neighboring states. All computations are local to the current history at time i, and take at most polynomial time in the history length. The following theoretical details state that the chain is suitable for unbiased history generation.
Theorem 3. The TTCG Gibbs sampler is aperiodic and irreducible.
Theorem 3 implies that the TTCG Gibbs Sampler converges to some stationary distribution; the following theorem ensures that its stationary distribution is the desired p=
Theorem 4, The stationary distribution of the TTCG Gibbs sampler with input is Pa.
Given an initial history obtained by solving the construction problem for the game and policy with full support at all infostates, the TTCG Gibbs sampler correctly generates histories from Pd (: in

---

0.000
0.775
True
Importance
0.133
0.200
True
Importar peportancc
0.8
0.7
Importence
Thue
Eroe
0.100
0.125
burr
0.125
0.150
Cabba 2u
Cabdaa buarm
burm=20
0.5
GiEbs b0
GiEts summ13
0.200
0.100
0.4
bars
00/3
0.3
0,50
0.050
0.2
0,325
0.023
0.1
0.000
Samplis
0.000
200
420
Samplis
0.0
200
100
Somples
500
800
(a) 192 Histories
(b) 12,960 Histories
(c) 544,320 Histories
Figure 4: Value estimation error of TTCG Gibbs Sampler with specified burn-in and baselines on PBS of various sizes. Error bars show one standard error of the mean over 100 runs See the appendix for full game parameters.
0.200
0.200
Cibba bum-10
0375
0.1/5
Giebs bum-20
0.350-
bum-10
0.150
Gibbs tum-50
0.125-
0.125
0.25
0.100-
0.100
0.20
0.0r5
0.075
0.35
0.000
0.050
0.30
0.025
0.25
0.06
0.000
2000
4020
0000
8000
20020
0.000
5000
10000
15000
2000e
15000
trans
Thansiiooss
Transitions
(a) 192 Histories
(b) 12,960 Histories
(c) 544,320 Histories
Figure 5: The effect of the number of samples burned on the value estimation error of the TTCG Gibbs Sampler. Burning fewer samples can result in a lower value error after an equal number of transitions. Error bars show one standard error of the mean over 100 runs.
the limit. The next section validates the efficiency and approximation quality of the TTCG Gibbs sampler empirically in the domain of Oh Hell (Parlett) (2008)) )); we leave the theoretical analysis of its mixing time to future work.
5.4 Experiments
The TTCG Gibbs sampler we just described runs in polynomial-time with respect to history length and removes dependencies on explicit belief representation. Thus, the algorithm's scalability depends on the mixing time of the underlying Markov chain. The following empirical results suggest that the chains mix rapidly in this domain.
We evaluate the TTCG Gibbs sampler using a value estimation task in the trick-taking card game Oh Hell. Oh Hell is an N-player game with n cards in the deck, where each player is dealt between 1 and (n 1)/NJ cards. We control the size of randomly generated ids-staaring small and then scaling to Hss several orders of magnitude larger-
varying the number of cards in the deck and the number of cards dealt to players. The task is to estimate the expected value of S under π, V=(S)= = E>es P (*(h)VV* V (h), where the value of a history h, V*(h) = >'E PM (ht ==)(=) the expected utility of the terminal histories in 2 reachable from h. The initial state is chosen uniformly from H.s, and ranges are constructed using policies learned via independent Q-learning (Claus and Boutilier (1998) hyperparameters and other details can be found in the supplementary material. Strong performance in this task does not necessarily imply improved search performance; instead, it demonstrates the sampler's 's ability to generate histories from the correct public belief state.
Figure shows the value error curves of the TTCG Gibbs sampler with specified burn-in compared to two Monte Carlo baselines. True samples from the exact joint range, and Importance performs (biased) importance sampling with uniform proposal and unnormalized reach probabilities. The latter estimates the PBS value by correcting the weight of samples drawn uniformly from H.s In wractice-especinn be feasible without a generation algorithm that approximates a known proposal distribution in polynomial time. We see that the TTCG Gibbs sampler outperforms importance sampling and closely
at larger scales than these pnteriments-importaan
sampling may not

---

approximates sampling from the joint range in all cases while using burn-in orders of magnitude smaller than the size of the public belief states.
Figure the effect of burning samples on value estimation error. On one hand, our results show that burning fewer samples result in better value estimate with fewer state transitions. This is unsurprising because larger sample sizes generally lead to better estimates. However, evaluating sample could be several orders of magnitude more costly than performing state transition in the Markov chain in practice. Comparing Figures [5 and 4 shows that, if the estimation task is constrained by time or computational resources, fewer high-quality samples may produce better estimate. The appropriate burn-in depends both on the task and the available resources.
Our experiments show that the TTCG Gibbs Sampler leads increased scalability merative approach in this value estimation task. With a small burn-in of 20 state transitions, a good approximation of the PBS value is achieved after only 400 samples and therefore only 8,000 total state to the enumerative approach which must construct and calculate the reach probability for 544,320 histories. State transitions are computed locally to the current state (history) and do not require knowledge of the rest of the PBS, so memory requirements are dramatically reduced. These effects increase along with public state size; in Oh Hell with 52-card deck, public states can have over 1061 histories.
the enu-
cunsitions-compace
Discussion and Conclusions
In this paper, we analyzed the computational complexity of history filtering for subgame decomposi- tion and depth-limited search imperfect information games. Although even the simplest form of the computation is likely intractable in general, we have shown that depth-limited search remains viable option in certain classes of imperfect information games. Efficient enumeration is achievable in games with polynomially-sizze have this property. However, generative methods for history filtering may not require explicit belief' representation, and are therefore more scalable than enumeration. To this end, we have introduced novel generation algorithm for tick-taking card games for asymptotically correct and efficient history filtering that fits seamlessly with Monte Carlo-style search algorithms.
public states; many application domains from prior work seem to
Our TTCG Gibbs sampler needs method that constructs valid history from the public state but is otherwise flexible. It does not depend on knowing the size of the public state and does not require normalized reach probabilities to produce samples with the correct probability. Unlike the enumerative approach which front-loads all of its computation, our algorithm applies to the setting where the game-pe plateelpliggggg algorithm must return an action within a predefined time budget. It is also easy to parallelize; multiple samples can be generated simultancously by starting the process multiple times from the same initial state and running each for the desired burn-in time. We demonstrate its effectiveness empirically- apprically-thoughh future work should prove rapid mixing analytically.
Acknowledgements
This work was funded by the Canada CIFAR AI Chairs Program. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), Prairies DRI, and the Digital Research Alliance of Canada.
References
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456):885- 890, 2019.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for caaperfect-iffrmaatie games. Advances in Neural Information Processing Systems, 73:17757-77 2020.
Michael Buro, Jeffrey Richard Long, Timothy Furtak, and Nathan R Sturtevant. Improving state evaluation, inference, and search in trick-based card games. In ISCAI, pages 1407-1413, 2009.
Murray Camphell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep Blue, Artificial Intelligence, 134(1-2):57-83, 2002.
10

---

Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. AAAI/IAAI, 1998(746-752:2, 1998.
Peter I Cowling, Edward Powley, and Daniel Whitehouse. Information Set Monte Carlo Tree Search. IEEE Transactions on Computational Intelligence and Al in Games, 4(2): 2012.
Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Optimally solving dec-pomdps as continuous-ste mdps. Journal of Artificial Intelligence Research, 55:443- 497, 2016.
Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), (9(2):248-264) 1972.
Arnadd Fickinger, Hengyuan Hu, Brandon Amos, Stuart Russell, and Noam Brown. Scalable online planning via reinforcement learning fine-tuning, Advances in Neural Information Processing Systems, 34: 16951616999666 2021.
Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, pages 721-741, 1984.
Matthew L Ginsberg. GIB: Imperfect information in a computationally challenging game. Journal of Artificial Intelligence Research, 14:303-358, 2001.
Olle Häggström al. Finite Markov chains and algorithmic applications, volume 52. Cambridge University Press, 2002.
W Keith Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, pages 97-109, 1970.
Mark R Jerrum, Leslie Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from uniform distribution. Theoretical computer science, 13:169-188, 1986.
Vojtëch Kovařík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisý. Rethinking formal models partially observable multiagent decision making. arXiv preprint 1rXiv:1906.11100 2019.
Vojtëch Kovařík, Dominik Seitz, V Lisy, Jan Rudolf, Shuo Sun, and Karel Ha. Value functions for depth-limited solving in imperfect-infoone information games. arXiv preprint arXiv: 190..099000.11., 2020.
David NL Levy. The million pound bridge program. Heuristic Programming in Artificial Intelligence The First Computer Olympiad, pages 95-103. Ellis Horwood, 1989.
Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 2166):0087-1092, 1953.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-511 2017.
Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions on Automatic Control, 1847)1164411688 2013.
Frans Adriaan Oliehock. Sufficient plan-time statistics for decentralized pomdps. In Twenty- Third International Joint Conference on Artificial Intelligence, 2013.
David Parlett. The Penguin Book of Card Games. Penguin UK, 2008.
Mark Richards and Eyal Amir. Information set generation in partially observable games. In Twenty- Sixth AAAI Conference on Artificial Intelligence, 2012.
Jonathan Schaeffer and Robert Lake, Solving the game of Checkers. Games of no chance, 29:119-133, 1996.
11

---

Martin Schmid, Matej Moravcik, Neil Burch, Rudolf Kadlec, Josh Davidson, Kevin Waugh, Nolan Bard, Finbarr Timbers, Mare Lanctot, Zach Holland, et al. Player of games. arXiv preprint 12.0122/ 2021.
Dominik Seitz, Nikita Milyukov, and Viliam Lisy. Learning to guess opponent's s information in large partially observable games. In Proc. AAAI Workshop Reinforcement Learning in Games, 2021
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550(7676)3554339 2017.
Samuel Sokota, Hengyuan Hu, David Wu, Zico Kolter, Jakob Nicolaus Foerster, and Noam Brown. A fine-tuning approach belief state modeling. In International Conference on Learning Representations, 2021.
Michal Sustr, Vojtech Kovarík, and Viliam Lisy. Particle value functions in imperfect information games. In AAMAS Adaptive and Learning Agents Workshop, 2021.
12


Reviews:
[{"review_id": "r5pIhRGJLB", "reviewer": "Reviewer_684B", "summary": "The paper concerns history-filtering method to estimate values of imperfect-information subgames. Such a sub-task proved to be a crucial component of previous depth-limited solving algorithm developed in the related literature.\n\nThe contribution of the paper is twofold:\n- on one hand, the paper analyses the complexity of such a task from a theoretical perspective, proving its FNP-completeness in the general case, and proving that a specific condition is sufficient to make its complexity polynomial. Such a complexity is satisfied by many games customarily addressed in the literature.\n- on the other hand, the paper proposes an algorithm that performs history sampling for value estimation in trick-taking games, and experimentally evaluates the performance-quality tradeoff of such an approximation.", "questions": "I'm open to see the author's opinion on the weaknesses I've highlighted in the previous section. Other than that, I have two minor specific questions:\n- Is the *\"deal $\\sigma$\"* term employed on line 280 referring to a \"suit length assignment\"? If so, in which sense $\\sigma \\sqsubseteq h$ ?\n- TTCG sampler procedure:\n\t- what is intended as *\"replacing\"* a deal with another in a history? Is it always possible for any valid suit length assignment to be replaced in a given $h$? Can this be done efficiently?\n\t- why is it not the case that $|\\Omega_\\sigma| = |\\Omega_{\\sigma'}|$, considering that the swap operations are commutative?", "limitations": "Limitation of the current analysis are properly addressed.", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- Novel approach for value estimation in depth-limited computation\n- Technically sound and original paper\n- Possibly significant direction for future research\n- Clear, intuitive and on-point explanation of the background and the relations with previous literature", "weaknesses": "- The structure of the paper is unclear and bipartite. In particular:\n\t- the first half of the paper (up to section 4) takes a general view and provides general theoretical complexity results regarding any possible history-filtering-related technique\n\t- the second half of the paper provides a specific technique for a very specific type of game; moreover, the design of this technique is not informed by any specific actionable insight coming from the general theory developed in the previous sections\n\tThis bipartite structure has negative effects in highlighting the crucial properties of the proposed history-filtering framework. En fact, by reading the theoretical section one gets the idea that a crucial property for the applicability of the framework is that a sparse public tree is needed. However, I argue that the proposed technique is actually much more depending on the possibility of locally sampling $\\bar P^\\pi(h)$ (which is crucial for effectively guaranteeing an efficient sampling), while I don't see the possibly exponential number of histories in a public state to be an impossible obstacle (and actually it may be an opportunity given the scalability of the technique).\n\tI think this partition inside the paper critically worsens clarity when reading\n- The gain of the overall technique are not evaluated. While from the experiments it emerges that at least in trick-taking games Gibbs sampling is a useful technique with a good tradeoff in terms of performance and memory consumption, it is not clear whether sampling is worth in this context. How do the performance of subgame solving techniques worsen when the cutoff values are estimated in this way? (I.e. how bad is having a value error of 0.01? Is it possible that subgame solving algorithms are so \"delicate\" that sampling does not offer good enough approximation?)\n- the main gain from using the technique proposed by the paper becomes evident only at the experimental section (Lines 329-335): given that $\\bar P^\\pi(h)$ can be easily recomputed locally when needed given the current history $h$, one can avoid to keep in memory the whole vector of $\\bar P$. This should emerge more clearly in the previous sections (Final paragraph of Section 1, introduction to Section 5)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Valid criticisms of the bipartite nature of the paper has led to clarity issues regarding our contributions. First, we seek to formalize the problem of history filtering and show that it is hard in general (Theorem 1). Theorem 2 then provides a condition called sparsity which describes the domains where the enumerative approach can be successful. This helps explain where some well-known algorithms from prior work (DeepStack, Player of Games, ReBel, etc.) can be applied as-is. Finally, we discuss a new approach that is necessarily more scalable and can approximate history filtering in basic trick-taking card games - a domain of significant interest to the community where enumeration is not tractable.  \n\nThe Reviewer claims that the fact that $\\bar{P}(h)$ can only be recomputed from just $h$ emerges only in the experimental section. This is not true. However, we concede that the clarity issues discussed above could be responsible. Lines 230-233 discuss how our contribution does not depend on explicitly representing beliefs, and line 289 states that the reach probabilities can be unnormalized. We also note that the reviewer is correct that, with the scalability of our technique, the possible exponential size of the PBS is not an obstacle in domains where our algorithm applies. That is one of the main advantages of our algorithm.\n\nIn terms of experiments and the gain of our overall technique, we add that the algorithm outperforms importance sampling using a small burn-in for the Markov chain. The small burn-in is evidence that the Markov Chain is rapidly mixing, which implies that our MCMC approach as a whole is efficient (i.e. samples are generated in polynomial time). We agree that future work evaluating our approach in an end-to-end algorithm that learns via solving subgames is needed. \n\nIn the TTCG Gibbs Sampler procedure, a deal is a prefix history containing all \"dealing\" actions. One suit length assignment can correspond to many deals. As deals are prefixes of the histories, replacing is simply changing the prefixes while holding the rest of the history (the cardplay actions) constant. It is always possible unless only a single suit length assignment remains, and the procedure is efficient (see proof of Theorem 3). For neighbor generation, only a single unit is moved between two suits for any player, so $\\sigma$ and $\\sigma^\\prime$ have different neighbor sets. Additionally, different suit length assignments may have different numbers of corresponding deals."}, {"review_id": "XwzZlT1Fzt", "reviewer": "Reviewer_KG55", "summary": "The paper presents theoretical analysis on the hardness of history generation in public belief states, a concept used in imperfect information games (IIGs). Then for a game where enumeration is prohibitively expensive (trick-taking card game Oh hell), they devise a specialized Gibbs sampler to generate histories from the public belief state. The sampler uses a polynomial time algorithm based on solving integer maximum flow to generate history candidates from the corresponding public state. The candidates that are then filtered to correct their distribution, i.e. to find the public belief state. In experiments, they compare the Gibbs sampler with baselines.\n\n", "questions": "1. In experiments, how is the value of a history $V^\\pi(h)$ computed? I assume this is not part of the compared algorithms and it is exactly computed?\n2. Can the method be trivially applied to other trick-taking card games like the mentioned Contract Bridge, Skat, and Hearts, or it is applicable only to Oh Hell? Are there trick-taking card games that have sparse PBSs (i.e. are \"easy\")? If yes, it would make the paper a lot stronger if your algorithm is shown to be more general for a class of trick taking games, and that it can generate PBS in both \"easy\" and \"hard\" games.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "1. Clearly written and well motivated paper. It can serve as a reference for claiming whether a game is \"hard\" or \"easy\" to generate histories from a PBS.\n2. Introduces a practical generative algorithm without explicit range representation for estimating PBS value in game Oh Hell.\n3. Shows that Gibbs sampler can be indeed used for their setting.", "weaknesses": "\n1. A weakness of the paper is misrepresentation of prior work, specifically the claim that tractability has been ignored and that only games like poker were considered. \n\n   Consider the quote from the cited paper [Richards and Amir, 2012]:\n \n   > Identifying legal moves involves testing the satisfiability of arbitrary Boolean expressions and is therefore theoretically exponential in the size of the game description.\n\n   This paper involved history generation in the game of Racko, Battleship and GOPS.\n   \n   There is a missing citation to [1], which also claims the problem is difficult:\n   > Due to exponential branching of the opponent’s private information, a large portion, or even all, of the tracked states may suddenly become incompatible with a received observation.\n   \n   The paper involved history generation in the game Stratego, Phantom Tic-Tac-Toe, Goofspiel.\n   \n   I concede there were no _formal_ definitions on tractability. But the claim seems too strong, as previous quotes show there was awareness on the difficulty of the problem.\n\n2. Def 3 - I believe the definition of a sparse public state is not well formulated, for what Thm 2 attempts to state. For any game, we can take polynomial $p$ of high enough degree such that we can then claim any $G$ is always sparse.  Then, according to Thm 2., solving FILTER(G,$\\pi$) is always polynomial time. But this is inconsistent with Thm 1. I believe this could be resolved by adding a restriction on the degree of the polynomial $p$.\n\n3. The paper introduces the concept of sparse public states to show the enumuration for FILTER problem can be done in polynomial time. However, authors do not take advantage of this separation of \"easy\" and \"hard\" problems. I would expect authors to use the bound to separate some games based on their hardness and an experiment that shows performance of a general algorithm on the two classes and compare that to a baseline. Instead, they found a game that is \"hard\" according to the bound, and devised a domain-specific algorithm that can approximate PBSs in that game.\n\n4. For the PBS value error experiment I am missing a motivation for why this is a relevant metric. As far as I know, existing algorithms in prior work use rather infostate-value functions for approximating strategies and PBS values are not descriptive enough for the use in IIGs. Can you add a motivation, perhaps by a reference to a paper  where this would be relevant?\n\n[1] Learning to guess opponent’s information in large partially observable games. D Seitz*, N Milyukov, V Lisy. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our response to Reviewer 8l8p describes how we will address potential misrepresentations of prior work.\n\nIt's true that for any fixed, finite game, we can choose some polynomial with arbitrarily high degree to bound the size of PBS support. However, complexity arguments, such as sparsity, only apply when we consider games or family of games that scale in size.\n\nThe clarity problems in our work has lead to confusion about sparsity, the motivation for generative algorithms and our MCMC approach, and our experiments. The concept of sparsity is meant to explain when enumeration may be a viable approach in certain families of games because there PBS sizes only grow polynomially. It provides a rule of thumb to understand where important algorithms from prior work are applicable as-is.\n\nOh Hell is an example game where enumeration is not viable at scale, but our new MCMC approach can approximate beliefs. The domain is not chosen to be hard according to our bound, but rather to represent basic trick-taking card games, which have long been of significant interest to the community. Our experiments are in small versions of Oh Hell, and still enumerate the public state to provide an upper bound on what any sample-based generative method could hope to achieve. We also compare to an importance sampling baseline. \n\nThe rules of Contract Bridge introduce new constraints (other than 1. player must have card $c$ and 2. player cannot have suit $s$), and thus the game likely requires a different neighbor generation algorithm (and potentially a different construction algorithm as well). However, we see no reason why the algorithm would not apply to Skat and Hearts - where the constraints are the same as Oh Hell.\n\nReBel, introduced in Combining deep learning and search for imperfect information games (Brown et al., 2020), demonstrates that infostate values can be recovered from the expected values of public states that contain them.\n\n$V^\\pi(h)$ is indeed computed exactly in our experiments."}, {"review_id": "2DZ5UVx5MJ", "reviewer": "Reviewer_r9WW", "summary": "This paper studies the algorithmic complexity of history enumeration and generation in imperfect information games. The authors define these problems with a formal model of factored observation stochastic games (FOSGs). They proved computational complexity results, and empirically demonstrated the effectiveness of an MCMC algorithm for generating history in the domain of trick-taking card games.\n", "questions": "The general hardness of history enumeration for FOSGs is to be expected, as the analogous problems in a single-agent context are already understood to be hard. For example, in POMDP solving one of the challenges is to approximate belief states. Could results and methods from the POMDP literature directly apply to the FOSG setting? For example, what would any of these works have to say about the multiagent version of the problem:\n[1] Nonapproximability Results for Partially Observable Markov Decision Processes, Lusena et.al.\n[2] What Makes Some POMDP Problems Easy to Approximate? Tsu et.al.\n\nAdditional detailed questions:\n\nAs noted above, the MCMC empirical part reads as quite a bit detached from the theoretical part of the paper. Is the point really to exercise the theory, or is it a separate contribution to develop techniques for trick-taking card games? \nIs the MCMC algorithm specific to this  domain or can it be generalized to a broader class of imperfect information games? Can you come up with a more general characterization of world-state structures for which this will be applicable and effective?\n\n\n\n", "limitations": "Enumerating history in imperfect information games itself is indeed an interesting combinatorial problem that is worthwhile studying. However, will this “enumeration” approach be plausible for more complex games? Computing exact beliefs seems tractable for Poker, but what about games like Stratego? In fact, it is unclear the relationship between an accurate belief state representation and the strength of a depth-limited search algorithm. The IS-MCTS algorithm the authors cite actually used a uniform distribution over possible world states to approximate a belief (instead of the exact belief written by the authors), which also renders fairly good empirical results. More efficient ways could be to use particle filtering [1], or deep generative models [2, 3].\n\n[1] Monte-Carlo Planning in Large POMDPs, Silver & Veness\n[2] Generalized Beliefs for Cooperative AI, Muglich et. al.\n[3] Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning, Li et.al.\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem studied in this paper is interesting, and the authors take an original perspective. In particular, they observe the centrality of history enumeration and generation in state-of-the-art algorithms for depth-limited game solving, and provide rigorous definitions of the associated computational problems. \n\nThe work appears technically sound: both the theoretical complexity analysis and experimental study of MCMC methods for history generation.\n\nThe presentation is clear, both in prose and mathematical description.\n", "weaknesses": "The major theoretical conclusion is that enumerating history is algorithmically hard in general, but is feasible for games that are sparse in a well-defined sense. These results are not surprising, and the authors do not pull out any deeper insights from their demonstration.\n\nThe two parts of the paper—fundamental complexity analysis and application to card games—seem quite disjoint from each other. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The non-approximability results mentioned by the reviewer are of interest to our area of work in general, but concern the hardness of computing or approximating solutions to POMDPs (in the form of optimal policies) rather than finding the sequence of unobservable states corresponding to some input sequence of observations. Those results also apply to the FOSG setting, but not in the context of history filtering.\n\nWe note the clarity issues raised by the reviewer, and want to emphasize that the sparsity result is meant to explain when enumeration is a viable option. Since it is not always the case, we introduce an approximate, but unbiased, generative method, similar to particle filtering, in the second part of the paper. Our MCMC method is intended for domains where computing exact beliefs is intractable. Games like Stratego are an intended use case, and our experiments are evidence that it can be a viable approach in domains where we can develop efficient algorithms for construction and neighbor generation in the Markov chain."}, {"review_id": "pq7dVdljBs", "reviewer": "Reviewer_8L8P", "summary": "The submission considers the problem of approximating public belief states. The submission's main contributions are:\n- Showing that certain fundamental computational problems related to public belief states are generally FNP-complete.\n- Defining a subclass of games and showing that enumerating public belief states for these games can be done in polynomial time. \n- Introducing an MCMC algorithm for the computation of public belief states in trick-taking card games.", "questions": ">  Think of the things where a response from the author can change your opinion\n\nAs articulated above, my main concerns are regarding the presentation. (Despite the disproportionate amount of text in the weaknesses box, I liked the paper : ) !) A revised copy of the submission that addresses the presentation criticisms would change my opinion. If this is not allowed during the review period, a provision of detailed text that the authors commit to including in the paper may change my opinion.", "limitations": "I think the place where the submission is in most danger of not having acknowledged its weaknesses is in the experiments section. The submission makes claims such as \"We demonstrate its effectiveness empirically\" (it referring to the MCMC algorithm). \n\nHowever, as discussed in the weaknesses section, there are some significant limitations:\n- The randomly generated policies that the submission uses do not possess the kind of structure that policies that humans or neural network-based policies have -- empirical results won't necessarily extrapolate.\n- The relationship between value error and search performance is hard to quantify. Having low or high value error isn't always a good indicator of downstream search performance.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "I think that studying scalable mechanisms for approximating public belief states is an important direction, so I am partial to the direction of the submission. Each of (what I view as) the submission's main contributions is novel. Both Theorem 1 and Theorem 2 are nice results. The MCMC algorithm is also a good contribution.\n\n---\n\nI am disclosing here that I did not read the proofs of the theorems or check the details of the experimental setup.", "weaknesses": "My criticisms regarding the submission mostly hinge on presentation.\n\nI think the submission does a poor job with respect to existing work in two respects. \n\n**First, it does not motivate the importance of public belief states as well as it could.** The only motivating use cases provided in the introduction are DeepStack and Pluribus. There are so many more great works and lines of research that rely on public belief states:\n\n> Work in control literature: Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach (Nayyar et al., 2013)\n\nThe paper that introduced public belief states! There is a large body of work in decentralized stochastic control literature using public belief states derived from Nayyar et al.'s work.\n\n> Work in Dec-POMDP literature: Optimally solving Dec-POMDPs as continuous-state MDPs (Dibangoye et al., 2013); Sufficient Plan-Time Statistics for Decentralized POMDPs (Oliehoek 2013)\n\nIndependently discovered public belief state-like objects for Dec-POMDPs. There are large bodies of on how Dec-POMDPs can be solved using HSVI from this perspective.\n\n> Search algorithms for common-payoff games: Improving Policies via Search in Cooperative Partially Observable Games (Lerer et al., 2020); Scalable Online Planning via Reinforcement Learning Fine-Tuning (Fickinger et al. 2021); A Fine-Tuning Approach to Belief State Modeling (Sokota et al., 2022)\n\nThe best performing Hanabi AIs rely on search techniques that use public belief states!\n\n> Other poker AIs: Superhuman AI for heads-up no-limit poker: Libratus beats top professionals (Brown and Sandholm, 2017); Combining Deep Reinforcement Learning and Search for Imperfect-Information Games (Brown et al., 2020); Player of Games (Schmid et al., 2021)\n\nI'm sure the authors are aware of these. But it's still valuable to list them to emphasize to the reader the ubiquity of the role that public belief states have played in successful poker AI.\n\n> Other techniques for zero-sum games: HSVI can solve zero-sum Partially Observable Stochastic Games (Delage et al., 2022)\n Abstracting Imperfect Information Away from Two-Player Zero-Sum Games (Sokota et al., 2023)\n\nThese works give new techniques for solving and doing search that don't require gadget games.\n\n> Work for adversarial team games: A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving (Carminati et al., 2022); Team belief dag form: A concise representation for team-correlated game-theoretic decision making (Zhang et al., 2022)\n\nThese works show how adversarial team games can be solved using public belief states.\n\n---\n\nIt's to the benefit of everyone for the submission to motivate itself more completely:\n- Readers without extensive knowledge of literature will be left with a greater sense of the importance of public belief states. As is, the submission risks them being left with the impression that they have only been studied by a niche community mostly focused on poker.\n- Authors of these works who normally interact with mostly or entirely disjoint bodies of literature from that of the imperfect information game community (such as those who work on Dec-POMDPs or decentralized stochastic control) are more likely to be made aware of the submission and in turn promote it among their own communities.\n- The submission is made stronger because it is made clear that it impacts a much broader body of literature than the current version reads as impacting.\n\n**Second, the submission appears to be entirely unaware of the single most related work.** The submission claims that applications of \"theoretically-sound depth-limited search in imperfect information games ... have been limited to games in which the relevant information is\nsmall enough to be enumerated.\" **This is not true!** The main contribution of *A Fine-Tuning Approach to Belief State Modeling (Sokota et al., 2022)* introduces a technique (called belief fine-tuning) for approximating public belief states in settings where the relevant information cannot be enumerated. They show that belief fine-tuning facilitates strong performance in such settings (specifically, variants of Hanabi).\n\nI encourage the authors to compare/contrast it to their own work in a related work section. It would also be interesting to see a direct comparison with the TTCG Gibbs sampler in Oh Hell, but it would be a lot of work for a rebuttal period, so it is not a necessity.\n\n### re: theory\n\nI think the way that the theoretical results are summarized could be improved. In section 3.2, the submission states that the subsequent section examines problem variants 1-5. However, at a surface level read it is difficult to discern whether this is the case. The subsequent section states that the construction problem is FNP (and therefore more complex computations are, also). But what about existence? I think explicitly referring back to problem variants by number, where possible, would help to improve clarity.\n\n### re: experiments\n\nI would be careful in extrapolating too much from the results of the experiments. The policy class that the submission examines is not resemblant of policies that humans use or that RL models learn. Furthermore, value error does not necessarily translate well to search performance. (This is not to say that the experiments are not appreciated, just that the submission should caution the reader of these limitations.)\n\n### Specific comments I made while I was reading (some redundancy with above)\n\n>  Search in imperfect information games requires subgame decomposition—a process in which a subgame is computed from public information and player beliefs.\n\nThis isn't true. It's perfectly possible to perform search without subgame decomposition (for example, IS-MCTS). What you really ought to argue here is that the approaches that have been most successful/have the strongest guarantees require subgame decomposition.\n\n> Applications have therefore been limited to games in which the relevant information is small enough to be enumerated. Scaling to larger, more complicated imperfect information games requires a deeper theoretical understanding of history filtering.\n\nIt is not true that applications have been limited to games in which relevant information is small enough to be enumerated. See: *A Fine-Tuning Approach to Belief State Modeling* (ICLR 2022). Thus, it is also untrue that scaling to such games requires a deeper theoretical understanding of history filtering than existed prior to the submission.\n\n> Of these, generation and enumeration are clearly relevant to history filtering. Prior work (Schmid et al. [2021]; Brown et al. [2020]; Moravcík ˇ et al. [2017]; Brown and Sandholm [2019]) has generally relied on enumerative methods, i.e. filtering histories by explicitly representing the entire PBS. Generative methods for history filtering potentially have the advantage of avoiding explicit PBS representation.\n\nGenerative approaches in combination with public belief states in both of the works below:\n\n*Scalable Online Planning via Reinforcement Learning Fine-Tuning* (NeurIPS 2021)\n\n*A Fine-Tuning Approach to Belief State Modeling* (ICLR 2022)\n\nThe reason these works avoided explicit PBS representation was actually orthogonal to PBS representations. For the NeurIPS 2021 paper, it was because of the high computational expense of doing search for every information state supported by the PBS. For the ICLR 2022 paper, it was to scale to settings in which the support of the PBS is too large to enumerate.\n\n> Prior work has typically limited applications to games where the public state is trivially enumerated and beliefs can be represented explicitly in physical memory\n\nAgain, this is untrue -- see:\n\n*A Fine-Tuning Approach to Belief State Modeling* (ICLR 2022)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The reviewer's suggestions concerning related work and motivation have provided us with the means to significantly improve the presentation of the paper. This will be accomplished by modifying the abstract and introduction, replacing Sections 2.2 and 2.3 with text that motivates public belief states in a broader sense, and also text discussing the main differences between our approach and belief fine-tuning.\n\nFor the abstract and introduction, the impact of our submission does not necessarily depend on the untrue claims that 1) subgame decomposition is necessary for search in imperfect information and 2) generative methods are completely novel. For 1), as stated by the reviewer, algorithms with strong guarantees that tend to perform best require subgame decomposition. For 2), our generative approach is novel because it works in public states with support too large to enumerate and is unbiased without having to generate\nand reject inconsistent histories. Ideally, we would also compare empirically to belief fine-tuning to show that this makes a difference for search, but we have not yet done so.\n\nMoving the necessary notation to clearly explain Sections 3-5 that is currently in Section 2.2 and Section 2.3 to Section 2.1, while replacing those sections with more motivation related to HMMs, POMDPs, and Dec-POMDPs - as well as the recent work on zero-sum POSGs. FOSGs are generalizations of HMMs and POMDPs, so citing the mentioned papers is sufficient for those bodies of work. Likewise, the missing work on Poker and Hanabi AI will be mentioned for completeness.\n\nThe most important improvement our submission can make is comparing our method with BFT. BFT takes a pre-trained model as input, whereas our method is parameter-free, given the policy. One of the main advantages of BFT is that it doesn't require training the sequential generative model as a function of the policy. This is vital for the FOSG case that we focus on, and our method achieves the same goal by avoiding training that model altogether. Our approach instead requires efficient domain-specific algorithms for the construction problem and neighbor generation in the Markov chain that provably leads to irreducibility. This could be viewed as a shortcoming compared to BFT, but in domains where our approach applies, it is unbiased - unlike BFT. Another potential advantage of our approach is that it always produces valid histories according to the game rules. In some domains other than Hanabi, it is unclear how to structure the pre-trained model such that its output is always valid. Otherwise, the dynamics model needed for fine-tuning may be undefined. A concrete example of where this could happen is any trick-taking card game, where a naively structured belief state model could assign a player a card that they could not possibly hold according to the game's rules. As we show formally earlier in the paper, producing histories that correspond to observation sequences is a hard problem in itself. Our algorithm comes with clear requirements that guarantee it will apply correctly.\n\nWe will also caution the reader of the limitations of the experiments and emphasize that they are primarily intended to demonstrate the efficiency of the approach (in terms of mixing time) while still maintaining reasonable accuracy (by outperforming importance sampling). Though our experiments demonstrate that our approach is effective in the sense that we can use it to approximate PBS values in the example domain, it should be clear to the reader that this does not imply that the method will necessarily lead to better search performance.\n\nIn any case, the detail in this review is exceptionally helpful for the improvement of our paper."}]

Author rebuttal:

Meta-review: This paper presents two novel results on history filtering in imperfect information games:
- Complexity analysis
- A new Gibbs sampler for trick-taking card games along with an empirical analysis

The criticisms of the reviewers came in three main categories:
1. Misrepresentations / omissions of previous work
2. Clarity of presentation, and
3. Unconvincing empirical results. 

On the first point, two reviewers brought up several points. One reviewer, 8L8P, who was originally very critical based on these points changed their opinion based on the response of the reviewers and proceeded to champion the paper for acceptance. One of the main reasons I am recommending acceptance is that I am confident that the authors will address the problems identified for the camera-ready copy. I cannot overstate the importance of acting on this point. 

On the second point, I believe the presentation problem created by bundling two independent (but obviously related, in my opinion) contributions is overstated. It might feel abrupt on a first read, but I doubt will significantly affect long-term impact. Also, the effect can be mitigated by camera-ready copy. As such, I expect the authors to add a sentence or two to help with the transition from one topic to the other, and maybe a sentence earlier in the paper preparing the reader for the two disjoint content sections.

On the third point, reviewers seem unconvinced by the empirical results because the sampler is not employed in a subgame-solving algorithm or real agent, nor compared to any baseline, i.e. there's no demonstration of improved performance of a Oh Hell agent. I am too a bit disappointed by this, as it's clearly part of the work's motivation. But, the empirical results that are shown are designed to clearly support the practicality of the Gibbs sampler, which it does well. In light of the hardness results, this is good news, and trick-taking card games form a wide class of games that are both played regularly world-wide and have a long history of use within the AI / ML community.
Decision: Accept (poster)