Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Models

Thank you for reviewing this work! Please find a point-by-point response provided in the following, with the reviews compressed due to the length limit.

Weakness 1. The paper ... the analysis of in-context learning in game theory ... why this research problem is important.

Response 1. As the reviewer noted, previous works on in-context RL are mostly focused on the single-agent RL tasks. In reality, however, RL has found successful applications in broader applications, especially multi-agent tasks. Exploring the possibilities of in-context learning in multi-agent RL, as done in this work, can contribute to a deeper theoretical understanding of the capabilities of pre-trained transformers. Moreover, it also provides design guidance for practical utilization of transformers in these tasks. Given these aspects, we believe this research problem is of both theoretical and practical importance.

Weakness 2. ... the empirical experiments are conducted on relatively simple two-player zero-sum normal-form games ...

Question 1. The empirical experiments are currently limited to simple two-player zero-sum normal-form games ...

Response 2. During the rebuttal period, we have performed further experiments on a more complex environment with state transitions. The results are reported in the attached PDF. It can be observed that in this more complex environment, the pre-trained transformer can still learn to approximate NE in an in-context manner and have a performance similar to that of the context algorithm, corroborating the results in the paper. We believe this empirical evidence can alleviate the reviewer's concerns, and as mentioned in Lines 581-585, it is also our hope to encourage further experiments.

Weakness 3. The paper lacks a more detailed discussion of the practical implications ...

Response 3. We will incorporate additional discussions on the practical implications in the revised paper. Here we briefly discuss the following aspects.

• First, this work can serve as an initial feasibility validation to employ transformers in performing multi-agent competitive RL tasks via an in-context fashion. Such guarantees and validations may encourage further attempts to benefit practical applications.

• Moreover, our current theoretical results have the following useful implications for practical considerations.

  • The context algorithm quality and the data volume are the key factors to obtain a well-performed pre-trained model. As in Theorems 3.3 and C.3, the pre-trained model will behave similarly to the context algorithm, with an error inversely related to the volume of pre-training data. The empirical results in Fig. 2 also corroborate the usefulness of involving more training data.

  • The size of the adopted transformer model should scale with the complexity of the targeted game environment. The required parameterization in Theorems 3.4 and 4.1 indicates that the transformer model should have a size comparable to that of the game environment (e.g., state and action space, horizon, etc.).

  • The adopted tokenizer should embed sufficiently expressive information about the game-playing trajectory. The theoretically constructed embeddings in the proofs of Theorems 3.4 and 4.1 are representative examples containing information about trajectories in different parts.

Question 2. ... Could your method be applied to other types of games, such as cooperative or general-sum games ...

Response 4. As the first attempt in this direction, this work focuses on the two-player zero-sum Markov games due to their representativeness in game-theoretic studies. We believe the results, especially the in-context game-playing capabilities of pre-trained transformers, can potentially extend to other types of games.

It is conceivable that general-sum games can be built upon the obtained results, together with an equilibrium solver powered by transformers. The extension to the cooperative games would also conceptually benefit from our study in the centralized setup and the previous single-agent investigations. As has been noted in Lines 564-570, it is our hope that this work can be a starting point and valuable foundation for exploring the pre-trained transformers in game-theoretical scenarios. We will highlight this extension as an important future direction in the revised paper.

Question 3. ... more about the broader impacts and potential limitations ...

Response 5. Thank you for this suggestion. We will incorporate more discussions on these aspects in the revised paper, on top of those currently appearing in Appendices B.2 and B.3. Here we would like to briefly note the following aspects.

• [Broader impact] The obtained theoretical guarantees and empirical evidences are helpful feasibility validations for further utilization of pre-trained transformers in multi-agent tasks, which we believe could guide practical implementations. While we do not foresee major negative social impacts due to the theoretical nature of this work, we would like to acknowledge the need for responsible usage of the practical implementation of the proposed game-playing transformers due to their high capability in various environments.

• [Limitations] Appendix B.3 has discussed that it would be interesting to future investigate different game forms (as also suggested by the reviewer), pre-training dataset construction, and large-scale empirical evaluations. In addition, from the theoretical perspective, it would be valuable to investigate how to extend the current study on the tabular setting to incorporate function approximation, while another attractive question is how to learn from a dataset collected by multiple context algorithms. From the practical perspective, a future study on the impact of the practical training recipe (e.g., model structure, training hyperparameters, etc.) would be desirable to bring additional insights.

We would like to first express our appreciation to the reviewer for reviewing this work. A point-by-point response is provided in the following, which hopefully can answer and clarify the raised questions and concerns.

Weakness 1. In this work, the game instances are assumed to have the same length of time horizon H, which may not be always the case. For example, when playing SMAC, each game-play could terminate at any time. In this case, will the results of this work still be applicable?

Response 1. Yes, the results of this work are general and still applicable in the mentioned scenario. The same horizon is adopted only for theoretical convenience. A standard treatment in RL theory is to define one termination state in the state space, which provides no rewards and can only transit to itself once entered (i.e., marking that the game has ended). Then, the different plays of games can be padded with the termination state to be the same length.

Weakness 2. In the current setup, the results seem only suitable for games with small state spaces because the augmented component (Line 163) needs to enumerate all the states. This could be impractical for more realistic and complex games.

Response 2. We would like to provide the following discussions on the augmented component.

• We first note that, as mentioned in Lines 164-166, this augmentation is purely computational, i.e., to sample actions from the context algorithm. It requires no real interactions with the game environment. As a result, it is relatively simple to perform this operation during empirical implementations.

• The reason behind the concerned enumeration over all states is essentially that the current setup is a tabular RL one, i.e., no relationships are assumed among state-action pairs. In other words, to provide a diverse dataset, we have to cover all states since information about one state cannot be provided by other states, as required by the tabular RL setup.

  • In more complex games and real-world applications, function approximations via features are typically utilized to share information among state-action pairs. Thus, covering information of certain representative states should be conceivably sufficient (e.g., a well-coverage of the feature space). Similar evidences have been observed comparing the coverage requirement of tabular [R1] and function approximation [R2] setups in offline learning for Markov games. This investigation is out of the scope of this paper, and we will include these discussions in the revised paper to encourage future investigations.

[R1] Cui, Q., and Du, S. S. (2022). When are offline two-player zero-sum Markov games solvable?.

[R2] Zhong, H., Xiong, W., et al. (2022). Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets.

Weakness 3. The experiments are only conducted using normal-form games, which is simple. The performance of the proposed framework for more complex Markov games is unclear. I would have guessed that it is not very practical for the current framework as one needs to sample actions over the state space which could be extremely large.

Response 3. Please refer to Response 2 for discussions on the action sampling, which, as noted there, requires no real interactions with the environment. In terms of empirical performance, during the rebuttal period, we have performed further experiments on a more complex environment with state transitions. The setup details and the results are provided in the uploaded PDF. From the figure, we can observe that in this more complex scenario, the pre-trained transformer can still learn to approximate NE in an in-context manner and have a performance similar to that of the context algorithm, corroborating the theoretical and empirical results in the paper. We believe this empirical evidence can alleviate the reviewer's concerns, and as mentioned in Lines 581-585, it is our hope that this work can encourage further experiments on this direction.

Thank you for reviewing this work! We are happy to hear your recognition of the new insights and contributions of this work. The following point-by-point response is provided, which hopefully can address the raised questions and concerns.

Weakness 1. I have concerns that since the pre-training dataset is collected from a context algorithm that the transformers are simply learning to mimic this algorithm.

Question 1: Do you believe that this implementation might have different results given a different pre-training dataset (produced from a different algorithm)?

Response 1. As weakness 1 and question 1 are both related to pre-training the transformer with data from the context algorithms, we would like to discuss them together in the following.

• Before further discussions, we note that the utilization of a context algorithm to collect pre-training data is a standard approach in in-context RL studies, pioneered by [R1]. This work extends this well-established framework to the multi-agent scenario and provides corresponding theoretical/empirical studies.

• The main goal of this paper is to show that the transformer, pre-trained from pre-collected game-playing data, can behave as a game-playing algorithm in an in-context manner. The context algorithms are introduced to provide distributional properties of the pre-training dataset. Thus, if the context algorithm changes, then the distribution of pre-training data changes, which intuitively results in that the pre-trained transformer and its induced game-playing algorithm also change.

  The main result of our paper is the theoretical characterization of the transformer-powered game-playing algorithm extracted from the pre-training data. We would like to highlight that this is a highly nontrivial task in the game-playing setting that has not been investigated in previous works, with its major challenges emphasized in the following.

  1. The game-playing data to be learned from contain complicated strategic interactions between the context algorithms and the environment. In the decentralized setting, there are also interactions between two separate context algorithms, further complicating the pre-training data distributions. It is a highly challenging task to extract the game-playing algorithm from such complex data distributions.
  2. Given the complicated data, even imitation learning in game-theoretical environments are rarely studied. In this work, we take an even bigger step as the to-be-trained game-playing algorithm must be confined to the practically-adopted transformer architecture instead of any other neural nets. As an illustration, the theoretical proofs of Theorems 3.4 and 4.1 are performed strictly under the transformer architecture described in Section 2.3, while the empirical experiments also use a transformer-based minGPT model (see details in Appendix J.3).

[R1] Laskin, M., Wang, L., et al. (2022). In-context reinforcement learning with algorithm distillation.

Weakness 2. The fact that empirical results are only collected from bandit settings, I have concerns that this may not hold in a setting where there are state transitions. I would have hoped that there would have been a more complex domain than just matrix games.}

Question 2. Do you believe that in more complex domains, with state transitions, we will still observe similar results? Or is this a factor that might break the current state of this work?}

Response 2. Thank you for your comments! During the rebuttal period, we have performed further experiments on a more complex environment with state transitions. The setup details and the results are provided in the uploaded PDF. From the figure, we can observe that in this more complex environment, the pre-trained transformer can still learn to approximate Nash equilibrium in an in-context manner and achieve a performance similar to that of the context algorithm, which corroborates the theoretical and empirical results in the paper. This and additional results will be added to the revised paper. We hope this empirical evidence can alleviate the reviewer's concerns.

Thank you for reviewing this paper! The following responses are provided with the reviews compressed due to the length limit.

W1. (Lines 157-170) If the data collected ... a limited range of strategic interactions ... might lack the necessary diversity ...

Q1. Given ... the diversity and distributional properties of the training data do not adversely ...

R1. Theorems 3.3 and C.3 are theoretical supports that better data coverage leads to better pre-trained models. The intuition that more data provides a better characterization of the context algorithm is rigorously captured by the error's $\sqrt{1/N}$ dependency on the data volume $N$.

Also, Theorems 3.3 and C.3 are high-probability guarantees. It means that the performance can be abnormal under small-probability events, e.g., a badly sampled dataset. Nevertheless, these undesirable events are statistically rare occurrences within the data collection process.

W2. (Lines 200-202) Take into account ... This assumption may not hold ...

R2. Assumption 3.2 introduced the realization error, i.e., $\varepsilon_{real,+}$, to model the capability of the learning model $Alg_{\theta_+}$ in approximating $Alg_{0,+}$. We first clarify that its core part is a definition: any $Alg_{\theta_+}$ satisfies the condition with its own scale of $\varepsilon_{real,+}$.

Through this notation, Theorem 3.3 showed a pre-training guarantee depending on $\sqrt{\varepsilon_{real,+}}$, i.e., sublinearly. Thus, a reasonable $\varepsilon_{real,+}$ (i.e., a suitably strong model) ensures a good pre-training model.

Theorem 3.4 and 4.1 further demonstrated that the transformer architecture is indeed strong enough to realize V-learning and VI-ULCB, two representative game-playing algorithms, i.e., $\varepsilon_{real,+} = 0$. These are the first results on the strong capability of transformers in competitive games.

W3. (Lines 195-190) Potential convergence/generalization problems ... if the covering number $\Theta$ is underestimated ...

Q2. The clipping operation $\text{clip}_R$ ... affect the learning dynamics ...

R3. The covering number of $\Theta$ is a definition (i.e., Definition 3.1) to theoretically capture the size of the parameterization space. Due to its entirely theoretical purpose, it is not used/required empirically.

The clipping operation is to bound the covering number (as in Appendix I) for theoretical completeness. As in Lines 972-974, setting $R$ on the order of $\tilde{O}(1)$ is sufficient to not impact the theoretically required transformer operations. With its entirely theoretical propose, this clipping is also not used/required empirically.

W4. (Lines 182-185) The use of linear extraction mappings followed by a projection to the probability simplex ... not suitable ...

R4. This work focuses on linear extraction mappings followed by a projection to probability simplex for theoretical analyses. It is always a valid approach to convert vector outputs from transformers to action distributions. Theorems 3.4 and 4.1 rigorously illustrate its sufficiency, as combining it with other operations exactly realizes the complex game-playing algorithms. Of course, in practice, we can leverage other operations, e.g., a non-linear mapping, which would provide higher flexibilities.

W5. (Lines 307-309) The required dimensions ... indicate a high computational complexity and dependency on specific game parameters ...

R5. The dimensional specifications in Theorem 4.1 are curial results, showing that such a model size is already sufficient to realize VI-ULCB. The polynomial dependency on the game parameters is a very mild requirement, especially considering that practical transformers with millions to billions of parameters. We will encourage future investigations on lowering these requirements.

W6. (Lines 307-309) This performance requirement ... assumes an ideal alignment ... any deviation ...

R6. Theorem 4.1 demonstrates that the transformer is capable of exactly realizing VI-ULCB, i.e., ensuring $Alg_{\theta}(\cdot, \cdot|D_{t-1},s) = Alg_{\text{VI-ULCB}}(\cdot, \cdot|D_{t-1},s)$. It is not an assumption, but a novel theoretical guarantee of the strong capability of transformers, which applies to any two-player zero-sum game. Hopefully this alleviates the concern on model capabilities.

The mentioned training error is independent of this theorem (which focuses on the existence). We can handle it via pre-training results in Sections 3.1, 4.1 and Appendix C by modeling it as one part of the realization error, which is further discussed R2.

W7. (Lines 321-322) Note that the assumption ... uniformly sampled ... might not hold ...

R7. The uniformly sampled $\hat{\mu}$ and $\hat{\nu}$ is the standard online-to-batch conversion, to theoretically translate the cumulative regret to a sample complexity guarantee. It is a relatively simple process, i.e., sample a random episode from $1, \cdots, G$ and use the policy of that episode.

Q3. In Appendix G.3, ... embedding and extraction mappings ... specific state spaces where these mappings prove particularly beneficial/limited?

R8. The mappings designed in theoretical proofs are indeed to encode sufficient information (i.e., step, state, action, reward, etc.) as the input. Although we did not notice states particularly special in terms of this mapping, it is generally a good mapping strategy to contain sufficient information to facilitate decision-making.

Q4. Have you observed any sudden shifts ... based on ...

R9. We will cite and discuss this interesting reference! During the previous experiments, we have not examined the training process as delicately as it. We are currently following its reported procedures to conduct further examinations, which have not yet completed due to the limited time but will be reported in the revised paper.

Thanks for your detailed rebuttal. I am happy with the clarifications the authors provided. As Reviewer h1zf mentioned, I want to highlight that this work is not only important for the MARL community but also for the broader research community focused on advancing our understanding of ICL. Congratulations on this great work.