IFlowNets: Extending Generative Samplers to Learn Strategies in Incomplete Information Games

AI summary

Overview

Research area: Machine learning for game-theoretic decision-making, specifically generative flow networks (GFlowNets) applied to extensive-form games with incomplete information.

Technical level: Advanced. The paper assumes familiarity with extensive-form game theory (histories, information sets, utility functions), counterfactual regret minimization, and the flow-matching formalism of GFlowNets, EFlowNets and AFlowNets.

One-sentence scope: The paper proves that the existing expectation-based flow constraints used by Adversarial Flow Networks are mathematically invalid in incomplete information games, proposes corrected constraints called Generalized Expected Detailed Balance, and reports preliminary benchmark results for the resulting "Information Flow Networks" in three standard games.

What This Paper Is About

Generative flow networks learn samplers over directed acyclic graphs by turning flow-matching constraints into a training objective. Jiralerspong et al. (2024) adapted this idea to complete information games as Adversarial Flow Networks (AFlowNets), where alternating samplers smooth over environment uncertainty by taking expectations. This paper asks whether that same expectation-smoothing trick can be carried over to incomplete information games, where a player cannot tell which history inside an information set they are actually in. The authors show the direct extension fails and then supply corrected constraints that restore the properties needed to learn valid player strategies.

Key Contributions

1. A negative result: The authors prove that directly re-applying Jiralerspong et al. (2024)'s expectation-based aggregation approach — which they call Double Expected Detailed Balance (DEDB) constraints — is impossible in incomplete information settings, because it invalidates the properties required for expected reward-proportional sampling.
2. A generalization: They extend AFlowNets to incomplete information games with new Generalized Expected Detailed Balance (GEDB) constraints, and show these strictly generalize AFlowNets.
3. Preservation of key properties: They demonstrate that the GEDB constraints induce expected flow matching over information sets (making the standard trajectory balance objective valid over infostates), and that they automatically recover the original Expected Detailed Balance constraints when information sets collapse to single states in complete information games.
4. Preliminary empirical evaluation: They test IFlowNets in three standard incomplete information environments — Weighted Rock-Paper-Scissors (RPS+), Kuhn Poker, and Leduc Poker — comparing against Outcome Sampling Monte Carlo CFR, Deep CFR, and Neural Fictitious Self Play (NFSP).

Main Findings

• Two new structural gaps are identified. Incomplete information introduces (a) a need for an infostate aggregation property, written F(I) = sum over h in I of F(h), which the authors describe as a self-consistency condition distinct from flow matching; and (b) "double intragraph uncertainty," because an agent is uncertain both about the environment's transitions and about which history within an infostate they occupy.

• The naive extension is provably broken. Theorem 1 shows that expectation-based aggregation over infosets via DEDB invalidates flow matching. The proof shows that satisfying flow matching under DEDB would force P_env(h) = 1 for all h, which cannot hold because P_env must be a probability distribution summing to 1. Consequently, P_env ceases to be a valid probability mass function, and valid sampling strategies cannot be learned.

• The fix substitutes a sum for an expectation in the agent constraint. The GEDB constraints replace the expectation in constraint D3 with a summation over successor histories (C3), while keeping the terminal, environment-expectation, and aggregation constraints. Lemma 2 shows these imply flow matching over infosets; Lemma 3 shows they recover the EDB constraints in complete information settings.

• A unique solution exists. Theorem 7 establishes that for n = 1 player against a Nature player there exists a unique (F, P_agent) pair satisfying GEDB, and Theorem 9 extends existence and uniqueness to all players i in [n]. A remark notes that the DEDB alternative admits no unique (F, P_agent) pair.

• Two-player zero-sum joint flow is valid. Theorem 10 shows that when two players' policies and flows jointly satisfy existence and uniqueness under GEDB, the product F(I) = F_1(I)F_2(I) satisfies flow matching with respect to the joint reward R(x) = R_1(x)R_2(x).

• Weighted RPS (RPS+). Wins and losses are doubled when Scissors is played; Player 1 moves first and Player 2 observes Player 1's choice only after the game ends, so Player 2 is always at an incomplete information state. The Nash equilibrium is (R, P, S) = (.4, .4, .2) for both players. IFlowNets find the Nash strategy, and approach minimal exploitability (reported in Figure 3). The authors note RPS+ is a benchmark for multi-agent learners' ability to adapt in non-stationary, incomplete information environments.

• Kuhn Poker (n = 2 players, 10,000 iterations). IFlowNet exploitability 0.087 at 340 iterations/sec; OS-MCCFR 0.068 at 1211 iterations/sec; NFSP 0.417 at 0.35 iterations/sec; DeepCFR 0.451 at 0.008 iterations/sec. The authors summarize this as comparable to OS-MCCFR in exploitability but slower.

• Leduc Poker (n = 2 players, 10,000 iterations). IFlowNet exploitability 1.287 at 55 iterations/sec; OS-MCCFR 2.725 at 7.62 iterations/sec; NFSP 2.691 at 0.09 iterations/sec; DeepCFR 1.431 at 0.01 iterations/sec. The authors summarize this as the best performance and faster to compute compared with the relevant CFR and deep RL variants.

• Connection to quantal response equilibria is sketched but not tested. Appendix D argues that if all agent policies follow P_i(I_i) proportional to the expected flow, the result is some agent quantal response equilibrium (AQRE), and that IFlowNets encode the subset of AQREs expressible by the choice of branching factor B_i and reward R_i. The authors explicitly state they do not empirically or theoretically study AQRE properties of IFlowNets in this work and defer rigorous analysis to future work.

• No confidence intervals, variance estimates, or repeated-seed statistics are reported. The paper reports single exploitability and iterations-per-second values per algorithm per environment.

Methodology in Plain English

The researchers start from an existing recipe for learning game strategies as flow networks. That recipe treats a game as a graph and requires the "flow" entering any node to equal the flow leaving it. When an agent cannot control what the environment or the opponent does, the original method handles the uncertainty by averaging over the possible next nodes — taking an expectation.

The paper's first move is analytical: apply that same averaging trick inside information sets and check whether the resulting equations can still be satisfied. Writing out the algebra, the authors show that satisfying flow matching would require the environment's transition probability for each history to equal 1, which is impossible for a distribution that must sum to 1. In other words, the equations have no valid solution, so no valid sampling strategy can come out of them.

The second move is a repair. The authors keep the averaging for environment-controlled transitions but replace the expected term in the agent's own constraint with a direct sum over the histories reachable by a given action. They add an explicit constraint that the flow of an information set equals the sum of the flows of the histories inside it. They then prove three things about this repaired set of equations: it forces flow matching over information sets, it collapses back to the original complete-information equations when every information set contains exactly one history, and it yields a unique flow-and-policy pair (first for one player against nature, then for every player in a multi-player game, and finally as a valid joint object for two-player zero-sum games).

The empirical component uses a straightforward setup. Agent policies are independent multilayer perceptrons: 3 layers with 32 hidden units for RPS+, and 3 layers with 512 hidden units for Kuhn and Leduc Poker. Training uses the trajectory balance objective over infostates (justified by the flow-matching result), resampling trajectories from an online replay buffer in PyTorch with the Adam optimizer at default settings. Hyperparameters were selected by grid search over ranges described by Keshavarzi and Navidi (2025), choosing the model with the best exploitability; all models were then run for 10,000 model-specific training iterations and scored on exploitability and iterations per second. All environments came from the OpenSpiel Python library.

Why This Matters

Impact on research. The paper's central result is a limitation result: an approach that works in complete information games does not transfer to incomplete information games, and the failure is not a tuning problem but a mathematical impossibility. By identifying exactly which constraint breaks and supplying a corrected version that provably generalizes the original, the work gives other researchers a validated foundation for applying generative flow network methods to the much larger class of games with hidden information. It also explicitly connects the framework to agent quantal response equilibria, which the authors flag as a promising but unexplored direction.

Real-world applications. The paper itself does not enumerate applications; the following are areas implied by its framing of zero-sum extensive-form games with incomplete information, including the authors' affiliation with a strategic competition analysis group.

• Security and defense decision-making, where an adversary's private information and intentions are not observable.
• Auctions, bidding, and market negotiation, which are naturally modeled as extensive-form games with hidden valuations.
• Automated negotiation and resource allocation between agents that cannot observe each other's internal state.
• Benchmarking and evaluating multi-agent reinforcement learning algorithms, since RPS+, Kuhn Poker, and Leduc Poker are standard difficulty probes for adaptation under non-stationarity and hidden information.

Industry relevance. Practitioners building game-playing or decision-support systems currently rely heavily on inference-time search such as Monte Carlo Tree Search. The paper highlights that flow-network approaches learn effective strategies from generated trajectories and observed outcomes alone, without approximate recursive search or human heuristics — a characteristic that matters for systems where search budget at deployment time is limited. The reported iterations-per-second figures, particularly on Leduc Poker, also bear on practical compute cost.

Future Directions

• Rigorous study of the quantal response equilibrium connection. The paper sketches in Appendix D that IFlowNets encode a subset of agent QREs selectable through the branching factor and reward transformation, but explicitly defers empirical and theoretical analysis of these properties.
• Stronger and broader empirical evaluation. The reported results are described as preliminary, covering three games with two-player settings and single reported exploitability values after 10,000 iterations, with no variance or seed analysis.
• Extending beyond two-player zero-sum. The theory covers n >= 1 players (Theorem 9) and the joint-flow result is stated for n = 2 zero-sum games (Theorem 10); general-sum and larger multiplayer settings remain to be explored.
• Addressing the speed gap in some environments. In Kuhn Poker, IFlowNets are comparable to OS-MCCFR in exploitability but notably slower (340 versus 1211 iterations per second), which the authors report without resolving.

Target Audience

This paper is aimed at researchers working on generative flow networks, game-theoretic equilibrium computation, and multi-agent reinforcement learning. It will be most useful to readers who already understand flow matching and extensive-form game notation, since much of the technical machinery — the Expected Detailed Balance constraints, the trajectory balance objective, and the optimality-criteria proofs — is developed in appendices and referenced rather than restated. Readers interested in the practical performance of CFR and deep RL baselines on Kuhn and Leduc Poker will find the two benchmark tables directly useful; readers looking for a gentle introduction to the topic will not, as the paper assumes substantial background.

Authors’ abstract

While many algorithms blend reinforcement learning (RL) with counterfactual regret (CFR) methods to leverage tradeoffs in computational speed and performance, there are fewer investigations into generative sampling frameworks in game theoretic applications in incomplete information games. We extend a generative flow network framework, Adversarial Flow Networks (AFlowNets), to incomplete information games, called Information Flow Networks (IFNs). We prove that previously established constraints for generative flow networks in complete information games are inadmissible for obtaining valid densities (corresponding to player strategies) and a valid training objective. We show that our proposed generalization, IFlowNets, alleviates this issue and strictly generalizes AFlowNets. In preliminary results for three standard game environments, IFlowNets perform comparably to or better than Outcome Sampling Monte Carlo Counterfactual Regret (OSMCCFR) and standard RL-based methods in performance and speed.