Summary
The authors built on the recent work of Lin et. al 2023, extending their ICLR framework so that instead of being for one agent, it is for multi-agent systems; at the same time, they also analyze and provide evidence of "ICGP" (in-context game-playing) capabilities in transformers.
The paper analyzes zero-sum Markov games for two players and explores learning the Nash Equilibrium. In these games, two setups are studied: one of decentralized learning (where the Nash Equilibrium must be reached without each player observing the opponent's actions) and another of centralized learning (where a transformer controls the actions of both players).
The authors find important theoretical results related to transformers in decision-making, e.g., that pre-trained transformers can realize both model-based and model-free designs, and the in-context learning capability of transformers in playing normal-form games
Strengths
1. **Soundness of the Claims**
a) **Theoretical Grounding**
The paper does a great job of formalizing and mathematically demonstrating decentralized and centralized training of transformers to achieve ICGP, and I think it is a high-impact contribution. One could argue that it is also necessary to provide more empirical evidence (which is scarce in this paper) of the dynamics being modeled, but results like Theorem 4.1 are, in my opinion, a sufficient contribution. Among other things, this work shows the capability of transformers to not only implement existing algorithms (not new in the literature) but also to adapt them to the needs of model-free designs (as far as I know, new), demonstrated by the transformer’s ability to perform exact and approximate implementations, which is important as we move to real-world applications.
b) **Empirical Evaluation**
The methodology followed by the authors ("J. Details of the Experiments") seems to be solid. They use the EXP3 algorithm to collect pre-training data to ensure that the data is reflective of competitive strategies and behaviors. They also customize GPT-2, with only 2 layers and 4 attention heads, tailored to match the action dimensionality in its output layer, which directly supports computing policies from the model outputs (Lines 1002-1008). The Nash Equilibrium (NE) gap is calculated by comparing the expected rewards of the max player's policy against the min player's policy over time. The gap measures how close the transformer’s induced policy is to an ideal Nash Equilibrium.
Since the area of applied game theory for LLMs/multi-agent LLMs is still largely unexplored, providing such detailed information about the experiments and the code is likely going to be useful and impactful for the community.
2. **Significance**
In general, I think that ICL work has a lot of impact; at this point, it is folk knowledge that ICL > fine-tuning, so papers like this one have a lot of significance for the advancement of the state of the art. In particular, Theorems 3.4 and 4.1 can prove to be of great impact.
3. **Novelty**
This paper is timely and tackles a timely and interesting topic. To the best of my knowledge, it is the first paper providing a theoretical analysis of this level on game theory applied to LLMs.
Weaknesses
1. **Soudness of the claims**
My concerns about the paper relate to whether this theoretical framework might struggle with generalization and performance in more complex games. In this section, I provide some examples of limitations that suggest this possibility. I'm concerned that it may excel in controlled environments but not in more complex scenarios, which are typical in the multi-agent literature.
Also, please note that the improved performance of transformers trained with 20 games compared to those trained with 10 (Lines 336-341) suggests a heavy dependence on the volume of training data. Thus, I'm also highlighting some potential problems related to this aspect.
a) **Theoretical grounding**
a1) **Decentralized learning scenario**
In the decentralized setting, my primary concerns revolve around the diversity and representativeness of the training data, overly optimistic assumptions about model approximation capabilities, and potential issues with the suitability of transformer outputs for generating valid action probabilities.
* (Lines 157-170) If the data collected through $Alg+,0$ and $Alg−,0$ only captures a limited range of strategic interactions (e.g., typical or frequent scenarios but not edge cases or unusual strategies) the training data might lack the necessary diversity, leading to overfitting/lack of robustness. If the data does not sufficiently cover the state-action space, the expected log probability of correct actions given the state, as modeled by the transformer, may not reflect true gameplay dynamics and $\mathbb{E}\left[\log P(\text{actual action} \mid \text{state})\right]$ may overestimate actual performance.
* (Lines 200-202) Take into account that with Assumption "3.2. Decentralized Approximate Realizability" you assume that the true data-generating distribution ($Alg_0^+$) can be closely approximated by the learned model ($Alg_\theta^+$). This assumption may not hold if the real complexity of strategies in the environment cannot be captured by the model's architecture or training data -- causing the models have generalization issues.
* (Lines 195-190) Potential convergence/generalization problems with the learning algorithm if the covering number $\Theta$ is underestimated. The clipping operation (Lines 936-938), which is designed to maintain the norm of activations within bounds, can significantly impact the parameter sensitivity and the gradient flow during backpropagation. So, if $\Theta$ is underestimated, it might not sufficiently account for the reduced effective parameter space available for optimization, possibly leading to convergence on local minima that do not generalize well
* (Lines 182-185) The use of linear extraction mappings followed by a projection to the probability simplex to determine action probabilities assumes that the transformer’s outputs can be linearly mapped to form valid probability distributions. Buuut, if the transformer outputs are not suitable for this kind of linear transformation due to scale, bias, or other distributional issues, the resulting action probabilities may not be valid or optimal --> leading to suboptimal decisions and erratic behavior, especially in complex games.
a2) **Centralized learning scenario**
For the centralized learning scenario, I want to provide feedback on some specific concerns related to computational demands, dependency on precise model and algorithm alignment, and assumptions about uniform sampling that may not adequately capture the complexity of strategic behaviors across varied game states
* (Lines 307-309) The required dimensions and mappings such as $d⪅HS^2AB,L⪅GHSd⪅HS^2AB,L⪅GHS$ etc., indicate a high computational complexity and dependency on specific game parameters (like $S,A,B,G,HS,A,B,G,H$). As a result, this could make the model computationally expensive and potentially overfit to specific types of game environments.
* (Lines 307-309) This performance requirement: $Algθ(⋅,⋅∣Dt−1,s)=AlgVI−ULCB(⋅,⋅∣Dt−1,s)Algθ(⋅,⋅∣Dt−1,s)=AlgVI−ULCB(⋅,⋅∣Dt−1,s)$ assumes an ideal alignment between the transformer’s output and the algorithm’s requirements; note that any deviation in this alignment due to model approximation errors or misestimations in the transformer's training could lead to significant performance drops...
* (Lines 321-322) Note that the assumption that $\hat{\mu}\$ and $\hat{\nu}\$ are uniformly sampled and provide an effective representation of strategic options in every game state might not hold if some strategies are inherently more complex or contextually sensitive than others.
Questions
* Given that the decentralized setup involves collecting offline trajectories using different algorithms for max- and min-players (Section "3.1 Supervised Pre-training Results") -- how do you ensure that the diversity and distributional properties of the training data do not adversely affect the learning outcomes?
* The clipping operation $clip_R$ is defined to constrain the norm of each vector (Lines 936 - 938). How does this norm constraint affect the learning dynamics, particularly in terms of gradient propagation and stability during backpropagation? This seems to be important as it directly affects the model's ability to learn and fine-tune strategies based on gameplay experience.
* In Appendix G.3, you detail the use of embedding and extraction mappings within the transformer architecture for implementing V-learning (Lines 810-819). These mappings essentially allow the transformer to understand and manipulate game states and decisions effectively. Are there specific state spaces where these mappings prove particularly beneficial/limited?
Just out of curiosity:
* Have you observed any sudden shifts in learning effectiveness or strategy adaptation in your decentralized learning models, based on the results from "The Mechanistic Basis of Data Dependence and Abrupt Learning in an In-Context Classification Task" by Gautam Reddy (2023)?