Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games

Technical Summary: Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games

Problem Statement
In two-player zero-sum imperfect-information games (IIGs), agents often benefit from reasoning about their own and their opponents' policies. While depth-limited lookahead search is feasible in small games using tabular representations (e.g., Counterfactual Regret Minimization), this approach becomes intractable in games with large public belief states where enumerating all possible policies is impossible. Consequently, there is a need for compact, useful representations (embeddings) of policies that allow agents to reason about strategic intent without accessing full policy tables. However, existing research on learning such policy embeddings in IIGs is sparse, lacking both systematic methods for generating policy datasets and standardized downstream tasks for evaluation.

Methodology
The authors propose a systematic framework comprising three core components: dataset generation, embedding learning, and downstream evaluation.

1. Dataset Generation: The paper introduces three methods to create diverse datasets of policies for a given game:

   • Random Initialization: Randomly initializing policy neural networks with a custom scheme to ensure behavioral diversity, avoiding the homogeneity of standard PyTorch initializations.
   • Policy Space Response Oracle (PSRO): Iteratively training best-responses to mixtures of existing policies to generate an expanding pool of diverse strategies.
   • Neural Population Learning (NeuPL): Training a single conditional neural network shared by all agents; new policies are generated by sampling from the network's latent embedding space.

2. Embedding Learning: Several methods are proposed to map policies to vector representations:

   • Weight Autoencoder: A naive baseline that attempts to reconstruct the flattened weight vector of a policy network from a bottleneck layer.
   • Functional Encoder: Similar to the weight autoencoder but minimizes the KL divergence between the action distributions of the original and reconstructed networks on sampled information states, focusing on behavioral reconstruction rather than weight reconstruction.
   • Trajectory Encoder: A contrastive learning approach (inspired by SimCLR) that maps variable-length trajectories (collected by rolling out policies against random opponents) to a fixed-dimensional latent space. This method does not require access to network internals.
   • NeuPL-style Conditional Embeddings: A generative approach where a conditional network learns to decode any vector from the latent space into a policy, jointly generating the population and embeddings.
   • Grover et al. Baseline: A hybrid generative-discriminative model using an MLP encoder and a conditional policy network trained with imitation and triplet identification losses.
   • Baselines: Includes a Tabular Baseline (concatenating action distributions at all information states) and an Identity Baseline (using raw network weights directly).

3. Downstream Evaluation Tasks: The effectiveness of representations is evaluated using five tasks:

   • Task A & B (Payoff Prediction): Predicting expected payoffs against a uniform random opponent (Task A) or between two specific policies (Task B) using a linear predictor.
   • Task C (Exploitability Prediction): Predicting the payoff of an opponent's best-response to a given policy.
   • Task D (Zero-Shot Best-Response): Training a conditional policy network to approximate a best-response to a policy given only its embedding.
   • Task E (Agent Identification): Classifying which policy generated a given trajectory using k-NN or linear probes.

Experimental Results
Experiments were conducted on Kuhn Poker (12 information states) and Leduc Poker (936 information states), with preliminary results on larger games (Liar's Dice, Phantom Tic-Tac-Toe).

• Payoff Prediction (Tasks A & B): In Kuhn Poker, the tabular baseline dominated due to the game's small size. However, in Leduc Poker, learned encoders (Trajectory, Grover, NeuPL) outperformed the tabular baseline, which suffered from high dimensionality (2808 dimensions). The Grover and Trajectory encoders achieved the highest improvements (up to 32.3% reduction in MSE) on Task A in Leduc. Simple Weight and Functional autoencoders generally failed to improve over predicting the mean.
• Exploitability and Zero-Shot Response (Tasks C & D): The NeuPL method significantly outperformed baselines in predicting best-response payoffs (Task C) and training zero-shot responders (Task D), particularly on NeuPL-generated policy populations. Identity and Weight baselines performed poorly, often worse than the mean baseline.
• Agent Identification (Task E): The Trajectory Encoder (using a linear classifier) substantially outperformed the Grover baseline, achieving 47.9% top-1 accuracy on Kuhn and 57.8% on Leduc, compared to Grover's 25.7% and 38.9% respectively.
• Visualization: t-SNE visualizations of Kuhn Poker embeddings revealed that the Trajectory Encoder successfully separated aggressive and passive strategies, whereas Weight Autoencoder embeddings showed no such structure.

Key Contributions

1. Dataset Creation: Introduction of three distinct methods (Random, PSRO, NeuPL) for generating diverse policy datasets in IIGs.
2. Representation Learning: Proposal and comparison of multiple embedding techniques, ranging from naive weight reconstruction to contrastive trajectory learning and conditional generative models.
3. Evaluation Suite: Definition of a comprehensive set of downstream tasks (payoff prediction, exploitability, zero-shot response, agent identification) to rigorously evaluate policy representations.
4. Systematic Comparison: To the authors' knowledge, this is among the first works to systematically compare self-supervised learning techniques for policy representations in games.

Significance and Claims
The paper claims to be a foundational step toward learning compact, useful behavioral representations in imperfect-information games. While the methods are described as "very basic," the results demonstrate that useful behavioral semantics are present in the learned embeddings, particularly when using contrastive trajectory learning or NeuPL-style conditioning. The work highlights that while tabular representations are sufficient for small games, learned embeddings become superior as game complexity increases. The authors position this work as an open framework (code available) to facilitate further research into policy representation learning, noting that future work could involve refining loss terms or integrating these representations with decision-time planning.