Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Models
Authors: Chengshuai Shi
Kun Yang
Jing Yang
Cong Shen
Venue: NeurIPS 2024 poster (2024)
Keywords: In-context Learning; Multi-agent Competitive Games; Transformers; Decision-making
Primary area: reinforcement_learning
TL;DR: This work provides a theoretical understanding of the in-context game-playing capabilities of pre-trained transformers, broadening the research scope of in-context RL from the single-agent scenario to the multi-agent competitive games.

Abstract: The in-context learning (ICL) capability of pre-trained models based on the transformer architecture has received growing interest in recent years. While theoretical understanding has been obtained for ICL in reinforcement learning (RL), the previous results are largely confined to the single-agent setting. This work proposes to further explore the in-context learning capabilities of pre-trained transformer models in competitive multi-agent games, i.e., in-context game-playing (ICGP). Focusing on the classical two-player zero-sum games, theoretical guarantees are provided to demonstrate that pre-trained transformers can provably learn to approximate Nash equilibrium in an in-context manner for both decentralized and centralized learning settings. As a key part of the proof, constructional results are established to demonstrate that the transformer architecture is sufficiently rich to realize celebrated multi-agent game-playing algorithms, in particular, decentralized V-learning and centralized VI-ULCB.

Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Models
Chengshuai Shi University of Virginia cs7yyc@virginia.o edu
Kun Yang University of Virginia kyStc@virginia. edu
Jing Yang
Cong Shen University of Virginia cong@virginia. edu
The Pennsylvania State University yangj ing@psu. edu
Abstract
The in-context learning (ICL) capability of pre-trained models based on the trans- former architecture has received growing interest in recent years. While theoretical understanding has been obtained for ICI. in reinforcement learning (RL), the pre- vious results are largely confined to the single-agent setting. This work proposes to further explore the in-context learning capabilities of pre-trained transformer models in competitive multi-agent games, i.e., in-context game-playing (ICGP). Focusing on the classical two-player zero-sum games, theoretical guarantees are provided to demonstrate that pre-trained transformers can provably learn to ap- proximate Nash equilibrium in an in-context manner for both decentralized and centralized learning settings. As a key part of the proof, constructional results are established to demonstrate that the transformer architecture is sufficiently rich to realize celebrated multi-agent game-playing algorithms, particular, decentralized V-learning and centralized VI-ULCB.
Introduction
Since proposed in Vaswani et al. [57]. the transformer architecture has received significant interest.
has powered many recent breakthroughs in artificial intelligence [I]] 12 21 23), including the extremely powerful large language models such as GPT [42] and Llama (55 56]. One of the most striking observations from the research of these transformer-powered models that they demonstrate remarkable in-context learning (ICL) capabilities. In particular, after appropriate pre-training, the models can handle new tasks when prompted by a few descriptions or demonstrations without any parameter updates, e.g., Brown et al. [ Chowdhery et al. [15], Liu et al. 339
ICL is practically attractive provides strong generalization capabilities across different down- stream tasks without requiring further training or a large amount of task-specific data. These appealing properties have motivated many empirical studies to better understand ICL [18] 26 [9); see the survey by Dong et al. [22] for key findings and results. In addition to the empirical investigations, recent years have witnessed growing efforts in gaining deeper theoretical insights into ICL, e.g., Ahn et al. 2]. Akyürek et al. [3]. Bai et al. 77]. Cheng et al. [14], Li et al. 377. Raventós et al. Wu
al. Xie et 66 Zhang et
Among these empirical and theoretical studies, one emerging direction focuses on the capability of pre-
trained transformer models to perform in-context reinforcement learning (ICRL) (28 In particular, the transformer's is pre-trained with interaction data from diverse environments, modeling
34
35 50 73).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the interaction as sequential prediction task. During inference, the pre- pre-trained transformer is prompted via the interaction trajectory in the current environment for to select actions. The work by Lin et al. 38 provides some theoretical understanding of ICRI, including both general pre- training guarantee and specific constructions of transformers to realize some well-known designs in multi-armed bandits and RL (especially, LinUCB M, Thompson sampling [54), and UCB-VI [6]). Wang et al. [62 further provides understandings on the capability of transformers learning temporal difference (TD) methods [52] via an in-context fashion. A detailed literature review can be found in Sec. 6
The insights from Lin et al. [38] Wang et al. 62 are largely confined to the single-agent scenario, i.e., single-agent multi-armed bandit or Markov decision process (MDP). The power of RL. however, extends to the much broader multi-agent scenario, especially the multi mallir competitive games such as GO [49], Starcraft [58], and Dota 2 [0]. To provide a more comprehensive understanding of ICRI, this work targets further studying the in-context game- somee-laying (ICGP) capabilities of transformers in multi-agent competitive settings. To the best of our knowledge, this the first work providing theoretical analyses and empirical pieces of evidence on the ICGP capabilities of transformers. The contributions of this work are further summarized as follows.
A general framework is proposed to model in in-context game-playing via transformers, where we focus on the representative two-player zero-sum Markov games and target learning Nash equilibrium (NE), Compared with the single-agent scenario [38, the multi-agent setting considered in this work broadens the ICRL research scope while it is also more complicated due its thee-the nature.
The challenging decentralized learning setting is first studied, where two distinct transformers trained to learn NE, one for each player, without observing the opponent's actions. A general caalizabilty--condiiooo guarantee is first derived that characterizes the generalization error of the pre-trained transformers. Then, the capability of the transformer architecture demonstrated by providing a concrete construction so that the famous V-learning algorithm [8] can be exactly realized. Lastly, finite-sample upper bound on the approximation error of NE is proved establish the ICGP capability of transformers. As a further implication, the result of realizing V-learning demonstrates the capability of pre-trained transformers to perform model- free RL designs, in addition to the model-based ones (e.g., UCB-VI VI 66 as studied in Lin et al. 38
To obtain complete understanding, the centralized learning setting is also investigated, where one transformer is pre-trained to control both players' actions. A similar set of results is provided: a general pre-training guarantee, constructional result to demonstrate realizability, and finite-sample upper bound on the approximation error of NE. Distinctly, the transformer construction is presented as specific parameterization implement the renowned centralized VI-ULCB algorithm (8).
Furthermore, experiments are also performed to practically test the ICGP capabilities of the pre- trained transformers. The obtained results not only corroborate the derived theoretical claims, but also empirically motivate this and further studies on the interesting direction of pre-trained models in theorete settings.
A Theoretical Framework for In-Context Game Playing
2.1 The Basic Setup of Environments
To demonstrate the ICGP capability of transformers, we focus one of the most basic game- theoretic settings: two-player zero-sum Markov games [47], while the discussions provided later conceivably extend to more general games. An illustration of the different settings (i.c., decentralized and centralized) considered in this work (with details explained later) is given in Fig. T The overall framework is introduced in the following, which extends Lin et al. (3 from the single-agent decision-making setting to the competitive multi-agent domain.
Considering set of two-player zero-sum Markov games denoted as M. Each environment M E M shares the number of episodes G, the number of steps H each episode, the state space (with |S] = S), the action spaces/ {A, B} (with |A| A and [|]] = B), and the reward space R. Here A and B denote the action spaces of two players, respectively, which are referred as the max max-player and the min-player for convenience.
2

---

Centralized Learning
In-context Game-playing
Decentralized Learning
Pre-trained
Inference
Erw. Prior Dist. A
Inference M
Pre-trained Transformer,
Transformer
Pre-trained Transformer
kad
Finite Interaction
Finite Samples
Individual Context Alg. &
Dataset [D) E [N]
Dataset
Context
[D.I E [M]
Alg
Individual Alg.
2
Dalaset [0,_il [M]
An overall view the framework, where the in-context game-playine (ICGP) capabilities of transformers are studied both decentralized and centralized learning settings. The orange arross denote the supervised pre-training procedure and the blue arrows mark the inference procedure.
Figure
Each environment M -Th R and reward functions R A B A(R), where T (-) denotes the initial state distribution. Particularly, overall G episodes of H steps happen in each environment M, with each episode starting s0.1 M (-). If the action pair (a ba. is taken upon state s at step in episode g. the state transited to g9.h+1 Th (-1s9th, asih ,68.h), and reward rshh 3y (s8hh as.h bo.h) (respectively, -rs.h) is collected by the max-player (respectively, the min-player). For simplicity, we assume that the max-player rewards are bounded in [0, 1] and deterministic, i.e. for each (s, a, b, h). there exists M (r|s,a, a,)s, b) = 1. Also, the initial state gall is assumed to be fixed one s!,
/ E [m1]] has its transition model Th 8 A ((8)
E [0. 1] such that Rg. i.., (s = 1.
We further leverage the notation T = GH, while using time t and episode-step pair (g. h) in an interleaving manner with L = (g - 1)H + h. The partial interaction trajectory up to time is then denoted D := {(s ,,,,""",,"r ,r": : [t) and
the abbreviated notation D D) Individually, for the max-player, we denote her observed interaction trajectory up to time by
D4 = {(sT, aarrr")) ,r") T [t]) and write D+ = D for short. Similarly, for the min-player, we denote D == {(s b7, brrr")) : [t] and D_ D
2.2 Game-playing Algorithms and Nash Equilibrium
A game-playing algorithm Alg can map partial trajectory D³~1 and state sf to distribution over the actions, i.e., Alg(---1D+1 st) A(A B). If one algorithm Alg is decoupled for the two players (as in the later decentralized setting), we denote it as Alg = (Alg Alg-), where Alg, (-ID'=1, s¹)
((A) and Alg (-IDi-1,s') A(B). Given environment M and an algo- rithm Alg, the distribution over a full trajectory D can be expressed as
pAA M (D) = II
L Th (s'Is'-1 a (--,b--1) Alg(a', D'ID'-1, ,8') (ry).
If further considering environment prior distribution A E A(M) such that M ~ A, the joint distribution of (M, D) is denoted 1 ( where M A(-) and D (.)
For environment M and game-playing algorithm æ, we define its value function over one episode as V (st) = EE [ΣIE r"], With the marginalized policies of π denoted as (μ,, v), we define their best responses as
v4(n)= == arg min, Vu (s*), p4(v)= = arg max, Val M
(s>))
whose corresponding values are
Vusi (s*) VM V(NPP(()) (** = (ur
With the notion of best responses, the following classical definition of approximate Nash equilibrium (NE) can be introduced [8] 32
40, 47).
Definition 2.1 (Approximate Nash equilibrium). decoupled policy pair (p. 8) is an e-approximate Nash equilibrium for environment M if VB + 2 V&. (s') 2 vl. (s - E, i.e., the Nash equilibrium gap Vi (s+) viLit v < 2s.
3

---

For each environment, our learning goal is to approximate its NE policy pair. In other words, we target outputting a policy pair ()) 2) that e-approximate NE with an enror e that is as small as possible, after interacting with the environment for an overall 7 rounds.
2.3 The Transformer Architecture
With the basics of the game-playing environment and the learning target established, we now introduce the transformer architecture [57). which has demonstrated great potential in processing sequential max 0} Rd as
inputs. First, for input vector æ: Rd, denote (x == (eLU(())
the entry-wise ReLU activation function and o, (ar) softmax (a:) IR the softmax activation function, while using (.)) to refer to a non-specified activation function (i.e., both ReL.U and softmax may be used). Then, the masked attention layer and the MLP layer be defined as follows.
Definition 2.2 (Masked Attention Layer). A masked attention layer with M heads is denoted as {(Vm, Qm: Knn) {m))mE((M) C RRddd On any imput sequence H
(-) with parameters [h1: ... hy] E IRdxN, we have H = Attng H) [11, ... hN] E RdxN, where
h T h, + Σ EmElm Eyets or( Kmhh)) Vmnhg.
Definition 2.3 (MLP Layer). An MLP layer with hidden dimension d' is denoted as MLPo with parameters (W1, W2) TRd xd RRdxdd On any input sequence [h1,".. _xx] E RRdx we have H MLPo(H) = (h..... hN] RaxN where
h
W2 (W, -h,).
The combination of masked attention layers and MLP layers leads to the overall decoder-bases transformer architecture studied this work, defined in the following.
Definition 2.4 (Decoder-based Transformer). An I--aaee decoder-based transformer, denoted as (Fo()), is a composition of L masked attention layers, each followed by an MLP layer and a clip operation: (H) = (L)) E RdxN where HLL) is defined iteratively by taking ( BaxN for 1 [L].
H (1) MLP ((!) Attnn g
(A(-1))
TR
where parameter 0 { mattn: mlp) [T]]] consists of (!!) matnn
((Vil) Q K!))
[M]] dd and ((4) mlp (w(") ! E Rd x gaxd'
We further define the parameter class of transformers as Od, = {0 (e (1:L)) e (
mlp
||||| < F}. where the norm of a transformer TFg denoted as
||0|
max max [E
{110 llop. ME[M]
| [op]
Σ
mE[M] Vi( lop
(1 lp 1| 1lop
Other Notations. The total variation distance between algorithms (πT, m') upon Dz-1 (8) is denoted as TV(T,, x x'|D(_1,s) 8) == (V( (.)'= Also, the notation x $ indicates that x is lower or equivalent order term compared with y, i.e., x = O(y), Ō(-) hides poly-logarithmie terms in H, S, A, B, and poly(-) compactly denotes polynomial term with respect to the input.
3 Decentralized Learning
First, we study the decentralized learning setting, i.e., each player takes actions following her own model independently without observing the opponent's actions, as it better captures the unique game-playing scenario considering in this work. This setting is aligned with the canonical study of normal-form games 20 (53] and has been extended to Markov games in recent years 332
In the following, we start by introducing the basic setup of supervised pre-training and provide general performance guarantec relying realizability assumption. Then, provide constructional result
41 51

---

to demonstrate that the algorithms induced by transformers are rich enough to realize the celebrated V-learning algorithm [32]. With these results, we finally establish that with V-learning providing training data, the pre-trained transformer can effectively approximate NE when interacting with different environments in an in-context fashion.
3.1
Supervised Pre-training Results
3.1.1
Basic Setups
Training Dataset. the supervised pre-training, we use a context algorithm Algo to collect the offline trajectories. For the decentralized setting. the context algorithm Algo used for data collection is assumed to be consisted of two decoupled algorithms (Alg+,0 Alg-,o) for the max- and min-players,
respectively. With the context algorithm, we consider N i.i.d. offline trajectories (D; : E [N]} collected, where D; D; U U, with
D: = {(s) ai bl r tE [T) PA A180 (.); DJ = {(ai,: (/,)) Alga(: (-
L
It can be observed that D; is the commonly considered offline interaction trajectory of Algo- while D the sampled actions of each state at each step with Algo. Compared with Lin et al. (38, D is an augmented component. We first note that collecting D is relatively easy in practical applications, as it only needs to additionally sample from the distribution Alga (:, -D( s) for each s E S (i.e., no additional interactions with the environment). Moreover, the reason to incorporate such an augmentation is to provide additional diverse pre-training data due to the unique game-theoretic
environment, with further discussions provided after the later Lemma (36] has also been recognized previously [16] 722 that the data requirement for learning Markov games is typically much stronger than that for single-agent RL.
To facilitate the decentralized training, the overall dataset is further split into two parts: (D+,:iE [N]] and (D_,:: i E [N]}, where
D+,: D+. U D4433 : : e [T)}, D4, = {af, : LE [T], E ES: D-, D=,==-,UDD.
(6)) it :e [2]}, D²,, = {6) E [T]. E S}.
In other words, Di++ denotes the observations of the max-player, while D. those of the min-layer. Note that neither player can observe the opponent's 's actions.
Algorithm Induced by Transformers. Due the decentralized nature, two embedding mappings of d and d_ dimensions are considered as h4 U (A x R) - Rd+ and h : S (B x R) - Rd-, together with two transformers TFa, and TF Taking the max-player's transformer representa- (a²,
h4 (s') }] be the input to TF and the obtained output is H = TFa (H-) = h h h 2, h1, which has the same shape as H. Similarly, the mapping used for the min- tun-pllyer's 's transformer TFe_ embed trajectory (D'-1,s').
tive, for trajectory (D+-1,s) s²), let H = h, (D ,t) = [h+
We further assume that two fixed linear extraction mappings, A E R RAxd, and B Bxd-, are used to induce algorithms Alga.. and Alge_ over the action spaces and B of the max- and min-players, respectively, as
Alge, (ID 8²) = proj (A- (A-,Fo, (D=-1,
Algo. Algo_ (-10"-1, ,s') = proj (B TFg (w- ( -1)
where ProjA denotes the projection probability simplex.
Training Scheme. consider the standard supervised pre-training to maximize the log-likelihood
of observing training datasets D+ (resp., D_) over algorithms (Alge, :+ E O+) (resp., (Alge_
0_ E )_)) with O = Od., F+ (resp., e_ = Oa_ -.L_,t,._.dde M_ F_). In particular, the
pre- pre-training outputs 04 and θ_ are determined as
θ_ arg max maxg_ce. c0+ N EiE(N) EneTry Eoes log AAgg, (a 1D s)):
5

---

0_ = arg m co.
N EiEI E E.es log Algo (bi,1D=,,, .s)
3.1.2 Theoretical Guarantees
In this section, we provide a generalization guarantee of the algorithms Algø and Algø pre-trained following the scheme introduced above. First, the standard definition regarding the covering number and an assumption of approximate realizability are introduced to facilitate the analysis, which are also leveraged in Lin et al. (38)
Definition 3.1 (Decentralized Covering Number). For a class of algorithms {Algo, :04 E ++},.
we say ④ C a p4-cover of + i is a finite set such that for any 0+ E Q+, there exists 0+ 0+ such that for all D :8 E S, E [T], holds that
log Algø_ (1D4 8) log Algo (-144 ,8) .0)
S St.
The covering number Ne_ (p+) is the minimal cardinality of θ+ such that θ+ is a p+ p + Similarly, we can define the p -coor of and the covering number No (p-). Assumption 3.2 (Decentralized Approximate Realizability). There exist 04 04 and &e such that for all t E [T), E ES E A, it holds that
Alg D ,5) Algo: (a)D4 1) E+,rcal.
log
E P
We also similarly assume ----ell- -paproiippoo realizability of Alg-,o via Alga- with 0- O...
Then, we can establish the following generalization guarantee on the TV distance between (Algø, Algø_) and Algo = (Algo,+ Algo,)), capturing their similarities.
Theorem 3.3 (Decentralized Pre-training Guarantee). Let 0. be the max-player's pre-training output defined in Sec. 3.1.1 Take Ne. = =Ne, (1/N) as in Def. 3.1 Then, under Assumption 3.2 with probability at least - 6, it holds tha
[EvET TV (AIS+... Algō D :)) ) Z STSE+.to + +TSV
log (Ne, TS/6)
E D
N
A similar result holds for the min-players' pre-training output θ_.
Theorem 3.3 demonstrates that in expectation of the pre-training data distribution, i.e., PAA (D), the TV distance between the pre-trained algorithm Algø, (resp, Algg and the context algorithm Alg+,0 (resp, Alg_.o) can be bounded via two terms: one from the approximate realizability, i.e., &eareal (resp, re.re),,, and the other from the limited amount pre-training trajectories, i.e., finite N. While we can diminish the second term via large pre-training dataset (i.e., sufficient pre-training games), the key question whether the transformer structure is sufficiently expressive to realize the context algorithm, i.c., having small 4..r which we affirmatively answer via example of realizing V-Icarning 32 in the next subsection.
3.2 Realizing V-learning
To demonstrate the capability of transformers in the decentralized game-playing setting, we choose prove that they can realize the renowned V-learning algorithm [32]. the first design that breaks the curse of multiple agents in learning Markov games. Particularly, V-learning leverages techniques from adversarial bandits 5 to perform policy updates without observing the opponent's actions. The details of V-learning are provided in Appendix G.1 where its unique output rule is also elaborated.
In the following theorem, demonstrate that a transformer can be constructed exactly perform V-learning with a suitable parameterization. One additional Assumption G.2 on the existence of
'The covering number Ne, in Theorem 3.3 (and also the later Theorem C3 is not concretely discussed in the main paper ease the presentation. A detailed illustration is provided in Appendix

---

a transformer parameterized by the class of Mp. to perform exact division is adopted for the convenience of the proof, while in Appendix [..2] we further demonstrate that the required division operation can be approximated to any arbitrary precision.
Theorem 3.4. With embedding mapping b4 and extraction mapping á defined in Appendix G.3 under Assumption G.2 there exists a transformer TFo, with
d SHSA L LS GHLD.
max M S HS + +HSA+ MD. (E
d' G do, 100| S GH'S + G + FD,
which satisfies that for all Di', E S,t E [T], Algo_ (-D4 .s) glg (-ID==1,) ,). A similar construction TFg_ exists for the min-player's transformer such that for all D'=1, E S E (T), Algo (-ID-=1 8) = Algy.nngiing (-1D- 5).
The proof of Theorem 3.4 (presented in Appendix G.3 is challenging because V-learning is model- free design, while UCB-V VI 66] studied in Lin et al. B8 and VI-ULCB [8] later presented in Sec. [4.2] are both model-based ones. We believe this result deepens our understanding of the capability of pre-trained transformers in decision-make
i.e., they can realize both model-based and model-free designs, showcasing their further potentials.
More specifically, with the embedded trajectory as the input, the model-based philosophy is natural for the masked attention mechanism, i.c. the value computation at each step is directly over all raw inputs in previous steps. Thus, the construction procedure is straightforward as (input,, inputz, imput,) + (value1, value2, value,). However, the model-free designs are different, where value computation at one step requires previous values (instead of raw inputs). In other words, the construction procedure is a recursive one as (input,, inputy, input,) - (value1, inputz, input,) (value,, valuez, ... input,) + ... (value,, value2, .... value,), whose realization requires carefully crafted constructions.
3.3 The Overall ICGP Capablity
Finally, built upon the obtained results, the following theorem demonstrates the ICGP capability of pre-trained transformers in the decentralized setting.
Theorem 3.5. Let O4 and O_ be the classes of transformers satisfying the requirements in Theo- remb 3.4 and (Alg+ . Alg- both be V-learning. Let (β, D) be the output policies via the output rule of V-leaninn. Denoting Algg = (Algā. Algg_) and No = No_. Then, with probability
at least - 5, it holds that
H*S(AV (OB(ST + +THSV
log (TSNe/8) N
I D
V
G
With the obtained upper bound on the approximation error of NE, Theorem 3.5 demonstrates the ICGP capability of pre-trained transformers as the algorithms Algø, and Alg are fixed during interactions with varying inference games (i.e., no parameter updates). When prompted by the interaction trajectory in the current game, they capable of deciding the future interaction strategy and finally provide policy pairs that are approximate NE. We further note that during both pre-training and inference, each player's transformer takes inputs of its own observed trajectories, but not the opponent's 's actions, which reflects the decentralized requirement. Moreover, the approximation eтror in Theorem 3.5 depends on A V B instead of AB as the later Theorem 4.2 evidencing the benefits of decentralized learning.
Proof Sketch. The proof of Theorem 3.5 (presented in Appendix rely the following, decompo- sition, where Eo[-] and Eg[[] are with respect to PAl and PAlks respectivelyy
Eg M (s') (7ltt(s") E. [v (s') v((t((s))
(2)
v (s') Eo 1 (st) + Eo (V Eg (V
+ 16
can be observed that the first decomposed term the performance of the considered V-learning, which can be obtained following Jin et al. [32) in Theorem G.I
7

---

Then, the remaining terms concern the performance of the policy pair (p, D) learned from Algo and Algg against their own best responses, respectively. This is drastically different from the consideration in Lin et al. [38], which only bounds the performance of the learned policies, i.e.,
Eg
3 Vii (s")
The involvement of best responses complicates the analysis. After careful treatments in Appendix H we obtain the following lemma characterize these terms.
Lemma 3.6. For any two decentralized algorithmss Alga and Algg. we denote their performed policies for episode y are (p& vā) and (1gg v2), and their final oulput policies via the output rule of V-learning (see Appendix G.1 1) are (Pa: Pa) and (Da, For {pas Pa), holds that
.t (s') - Es Bo (s') SH. E EieMssss Bu [VV (Ha 1r/lD(1,)) M
En
+H EETT.EES
Bn [TV (Va "gDD , ,
where Ex1t and [+ are with respect to Ipls, and PA A188 A similar result holds for (Ver D33).
to upper bound the TV distance between Algo and Algg. which together with Theorem 3.4 establish Ereal.+ = Syeal - = 0 in this case, leading to the desired performance guarantee in Theorem 3.5 We here further note that the effectiveness of Theorem 3.3 in capturing the bound in Lemma
With Lemma 3.6
can incorporate Theorem 3.3
3.6 over all E S credits to the augmented dataset
D', which provides diverse data of all S.
Centralized Learning
In this section, discuss the scenario of centralized learning, i.e., training one joint model control
both players' interactions. This is also known as the self-play setting [8] 9 33 40, 67). Following a similar procedure the decentralized discussions, and then demonstrate that transformers are capable of realizing the renowned VI-ULCB algorithm []] It is thus established that in centralized learning setting, the pre-trained transformer still effectively perform ICGP and approximate NE.
first provide supervised pre- trainrainin guarantees
4.1 Supervised Pre-training Results
The same training dataset (D, : [N]] in Section 3.1.1 is considered. As the centralized setting is studied here, no further split of the dataset is needed. Moreover, one d-dimensional mapping h S U (A x B x R) - IRd can be designed embed the trajectories, and the induced algorithm (- - DD , s²) from the transformer TFg can be obtained via a fixed linear extraction mapping similarly as Eqn. (I). Finally, the MLE training performed with θ Od,L,M, FF as
arg maxgge N ΣiE[N] Eie(r] Exes log (Alge (a) 1D! .)).
Then, a generalization guarantee Algø can provided similarly as Theorem 3.3 which is deferred to Theorem C.3 This centralized result also implies that the pre-trained centralized algorithm performs similarly as the context algorithm, with errors caused by the approximate realizability and the finite praitigin data.
4.2 Realizing VI-ULCB
The VI-ULCB algorithm g is one of the first provably efficient centralized learning designs for Markov games. It extends the key idea of using confidence bounds to incorporate uncertainties from stochastic bandits and MDPs [4] 6 to handle competitive environments, and has further inspired many extensions in Markov games [9] 30 33 40 65). As VI-ULCB is highly representative, choose as the example for realization in the centralized setting to demonstrate the capability of transformers.
To make VI-ULCB practically implementable, we adopt an approximate CCE solver powered by multiplicative weight update (MWU) in the place of its originally required general-sum NE solver

---

(which is computationally demanding). This modification is demonstrated as provably efficient in later works (9 40 65]. Then, the following result illustrates that a transformer can be constructed to exactly perform the MWU-version of VI-ULCB.
Theorem 4.1. With embedding mapping h and extraction mapping E defined in Appendix D.2 there exists transformer TFo with
d HS d' x HS AB,
L L GHS, [ M HS AB, &HSABB,
|0] S HS AB GH,
which satisfies that for all D E S, [T], Algol 1D-1),)))))) Algo(1-1D''1
AlEviuLCa(s D ,s).
One observation from the proof of Theorem 4.1 (presented in Appendix D.2) is that transformer layers perform MWU that approximate CCE can be found, which not reported in Lin et al. (38] and further demonstrates the in-context learning capability of transformers in playing normal-form games (since MWU is one of the most basic designs).
4.3 The Overall ICGP Capability
showing VI-ULCB can be exactly realized (i.e., Ercal = in Assumption C.2 we further prove overall upper bound of the approximation enror of NE by Algg via the following theorem, demonstrating the ICGP capability of transformers.
With Theorem 4.1
Theorem 4.2. Let θ be the class of transformers satisfying the requirements in Theorem 4. and Algo be VI-ULCB. For all (g. s) E [G] x [H] x S, let (1s=) (-Iss) ) be the marginalized policies of (. .). Then, with probability at least 6, it holds that
log(TSNN)//) N where is and è are uniformly sampled as js ~ Uniflut ... ,1C) and i ~ Uniflut, .G., with 2 = (- : (h, s) E [H] x S} and v == (1och (-18): (h, [H] x S), and Eg e is with respect to the process of policy sampling.
H AB (SAB))
v ( S
E nen .0.0
+ THS
This result demonstrates the ICGP capability of pre-trained transformers in the centralized setting, complementing the discussions in the decentralized results.
5 Empirical Experiments
Experiments are performed on two-pll -wo-player zero-sum normal-form games (H = 1) and Markov games (H = 2), with the decentralized EXP3 [5] (which can be viewed one-step V-learning) and the centralized VI-ULCB being the context algorithms as demonstrations, respectively. Additional experimental setups and details can be found in Appendix [] It can be first observed from Fig. that, the transformers pre-trained with N = 20 games performs better on the inference tasks than the ones pre-trained with N 10 games. This observation empirically validates the theoretical result that more pre-training games benefit the final game-playing performance during inference (i.e., the / /I/N-ddpeene -dpeendnneess established in Theorems 3.5 and 4.2). Moreover, when the number of pre-training games is sufficient (i.e., N 20 in Fig. 2 the obtained transformers can indeed learn to approximate NE in an in-context manner (i.c., having gradually decaying NE gap), and also the obtained performance is similar to the context algorithm, i.e., EXP3 or VI-ULCB. These observations provide empirical pieces of evidence to support the ICGP capabilities of pre-traie ireetrained transformers, motivating and validating the theoretical analyses performed in this work.
Related Works
In-context Learning. Since GPT-3 [1]] demonstrates the ICL capability of pre-trained transformers, growing attention has been paid to this direction. particular, an emerging line of work targets providing deeper understanding of the fundamental mechanism behind the ICI. capability 3 24 66 68), where many interesting results have been obtained. particular, transformers have been shown to be capable of performing in-context gradient descent so that
29 RT

---

0.400
Transforer (10 envs)
Transfommer (20 cmus)
0.85
Trassormer (10 enco) VIHILG
Transormerr (20 cniv)
0.00
0.350
0.325
8
0.70
0.275
0.60
0.25
0.50
(a) Decentralized Comparisons With EXP3.
(b) Centralized Comparisons With VI-ULCB.
Figure 2: Comparisons of Nash equilibrium (NE) gaps over episodes in both decentralized and centralized learning scenarios, averaged over 10 inference games.
varying optimization-hann baaed algorithms be realized 2 demonstrates that looped transformers can emulate basic computing blocks, whose combinations can
26 59
Also, Giannou et al. [27
lead to complex operations.
This work is more focused on the in-context reinforcement learning (ICRL) capability of pre-trained transformers, demonstrated in Grigsby et al. (28). Laskin et al. [34]. Lee et al. [35). Wang al. [62] The recent work by Lin et al. (38) initiates the theoretical investigation this topic. In particular, Lin al. (38) provides generalization guarantees after pre-training in the single-agent RL scenario, and
further constructs transformers to realize provably efficient single-agent bandits and RL algorithms (in particular, LCn [1] Thompson sampling [54] UCB-VI (6). This work extends Lin al. (38) to the domain of competitive multi-agent RI by studying the in-context game-playing setting. A recent concurrent work (36] also touches upon the in-context game- same-playing capability of pre-trained transformers, while focusing on practical aspects and exploiting different opponents.
Competitive Multi-agent RL. The study of RL in the competitive multi-agent domain has a long and fruitful history [TO 47
58 770. In recent years, researchers have gained a deeper theoretical understanding of this topic. The centralized setting (also known self-pl fulf-play has been investigated in
49
Bai and Jin 88. Bai et al. (9), Cui et al. [17], Huang et al. [30]. . Jin et al. [33], Liu et al. [40]. Wang al. 663] Xiong al. [67]. Zhang et al. [69]. and this work focuses the representative VI-ULCB design [9. On the other hand, decentralized learning more challenging, and the major breakthrough made by V-learning
32 41 51
which is thus adopted the target algorithm in this work.
7 Conclusions
This work investigated the in-context game-playing (ICGP) capabilities of pre-trained transformers, broadening the research scope of in-ontexxt RL from the single-agent scenario to the more challenging multi-agent competitive games. Focusing on the classical two-player zero-sum Markov games, general learning framework was first introduced, laying down solid ground for this and later studies. Through concrete theoretical results, this work further demonstrated that in both decentralized and centralized learning settings, properly pre-trained transformers are capable of approximating Nash equilibrium in in-context manner. As key part of the proof, concrete sets of parameterization were provided to demonstrate that the transformer architecture can realize two famous designs, decentralized V-learning and centralized VI-ULCB, Empirical experiments further validate the theoretical results (especially that pre-trained transformers can indeed approximate NE in an in- context manner) and motivate future studies this under- experrexplored research direction.
10

---

Acknowledgments and Disclosure of Funding
The work of CSs and KY was supported in part by the US National Science Foundation (NSF) under awards CNS-2002902, ECCS- 2029978, ECCS-2143559, and CNS-2313110 100, and the Bloomberg Data Science Ph.D. Fellowship. The work of JY was supported in part by the US NSF under awards CNS-1956276 and CNS-2114542.
References
[1] Aabasi-Yakkori Y., Pál, D.. and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
[2] Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. (2023). Transformers learn to implement preconditioned gradient descent for in-context learning. arXiv preprint arXiv:2306.00297,
[3] Akyürek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. (2022). What learning algorithm is in-context learning? investigations with linear models. arXiv preprini arXiv:2211. 15661.
[4] Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002a). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256.
[5] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002b). The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(17)48-77.
[6] Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR.
[7] Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection. arXiv preprint arXiv:2306. 044.:7300..06377. 04637.
[8] Bai, Y. and Jin, C. (2020). Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR.
[9] Bai, Y., Jin, C., and Yu, T. (2020). Near-optimal reinforcement learning with self-play. Advances neural information processing systems, 33:2159-2170.
[10] Berner, C., Brockman, G., Chan, B., Cheung, V., Dębiak, P., Dennison, C., Farhi, D., Fischer,
Q. Hashme, S., Hesse, C., et al. (2019). Dota with large scale deep reinforcement learning. arXiv preprint 1912::911.006688
[11] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances neural information processing systems, 33:1877-1901.
[12] Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A., and Zagoruyko, S. (2020). End-to-end object detection with transformers. In European conference on computer vision, pages 213 229.. Springer.
[13] Cesa-Biand N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
[14] Cheng, X., Chen, Y., and Sra, S. (2023), Transformers implement functional gradient descent to learn non-linear functions context. arXiv preprint arXiv.2312.06528.
[15] Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung,
H. W., Sutton, C., Gehrmann, S., et al. (2023). Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113.
[16] Cui, Q and Du, S. (2022). When are offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 35.25779-25791.
[17] Cui, Q. Zhang, K., and Du, S. (2023). Breaking the curse of multiagents in large state space: RI in markov games with independent linear function approximation. The Thirty Sixh Annual Conference on Learning Theory, pages 2651-2652. PMLR.

---

[18] Dai, D., Sun, Y., Dong, L., Hao, Y.. Ma, S., Sui, Z., and Wei, F. (2023). Why can gpt learn in-context? language models secretly perform gradient descent as meta-optimizers. In Findings of the Association for Computational Linguistics: ACI. 2023, pages 4005-4019.
[19] Daskalakis, C. (2013). On the complexity of approximating nash equilibrium. ACM Transac- tions on Algorithms (TALG), 9(3):1-35.
[20] Daskalakis, C., Fishelson, M., and Golowich, N. (2021). Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-7616.
[21] Devlin, J., Chang, M.-W,, Lee, K., and Toutanova, K. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:/810.04880
[22] Dong, Q., Li, L., Dai, D., Zheng, C., Wu, Z., Chang. B., Sun, X., Xu, J., and Sui, Z. (2022). A survey for in-context learning. arXiv preprini urXiv:230.00234.
[23] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., De- hghani, M., Minderer, M., Heigold, G., Gelly, S., al. (2020). An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1999. 1929.
[24] Fu, D., Chen, T.-Q.. Jia, R., and Sharan, V. (2023). Transformers learn higher-order optimization methods for in-context learning: A study with linear models. arXiv preprint arXiv:2310. 17086.
[25] Gao, B. and Pavel, L. (2017). On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv:1704.00805.
[26] Garg, S., Tsipras, D., Liang, P. S., and Valiant, G. (2022). What can transformers learn in- context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30599
[27] Giannou, A., Rajput, S., Sohn, J.-y., Lee, K., Lee, D., and Papailiopoulos, D. (2023). Looped transformers as programmable computers. In International Conference on Machine Learning. pages 11398-11442. PMLR.
[28] Grigsby, J., Fan, L., and Zhu, Y. (2023). Amago: Scalable in-context reinforcement learning for adaptive agents. arXiv preprint arXiv:2310.0997.
[29] Guo, T., Hu, W., Mei, S., Wang, H., Xiong, C.,, Savarese, S., and Bai, Y. (2023). How do trans- formers learn in-context beyond simple functions? a case study on learning with representations. arXiv preprint arXiv:2310. 10616.
[30] Huang, B., Lee, J. D., Wang, Z., and Yang, Z. (2021). Towards general function approximation in zero-sum markov games. arXiv preprint arXiv:2107.14700)
[31] Huang, Y., Cheng, Y., and Liang, Y. (2023). In-context convergence of transformers. arXiv preprint arXiv:2310.05249.
[32] Jin, C., Liu, Q. Wang, Y., and Yu, T. (2023). V-leariig simple, efficient, decentralized algorithm for multiagent reinforcement learning. Mathematics of Operations Research.
[33] Jin, C., Liu, Q., and Yu, T. (2022). The power of exploiter: Provable multi-agent rl in large state spaces. In International Conference on Machine Learning, pages 10251-10279. PMLR.
[34] Laskin, M., Wang, L.,, Oh, J., Parisotto, E., Spencer, S., Steigerwald, R., Strouse, D., Hansen, S., Filos, A., Brooks, E., al. (2022). In-context reinforcement learning with algorithm distillation. arXiv preprint arXiv:22100 10. 14215.
[35] Lee, J. N., Xie, A., Pacchiano, A., Chandak. Y., Finn, C., Nachum, O., and Brunskill, E. (2023). Supervised pretraining can learn in-context reinforcement learning. arXiv preprint arXiv:2306. 14892.
[36] Li, S., Yang. C., Zhang, Y., Li, P., Wang, X., Huang, X., Chan, H., and An, B. (2024). In-context exploiter for extensive-form games. arXiv preprint
12

---

[37] Li, Y., Ildiz, M. E.. Papailiopoulos, D., and Oymak. S. (2023). Transformers algorithms: Generalization and stability in-context learning. International Conference on Machine Learning, pages 19565-19594. PMLR.
[38] Lin, L., Bai, Y., and Mei, S. (2023). Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining. arXiv preprint arXi:2310.08556.
[39] Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W. (2021a). What makes good in-context examples for gpt-3? arXiv preprint Saki::2011008000
[40] Liu, Q. Yu, T., Bai, Y., and Jin, C. (2021b). A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR.
[41] Mao, W. and Başar, T. (2023). Provably efficient reinforcement learning in decentralized general-sum markov games. Dynamic Games and Applications, 13(1):165-186.
[42] OpenAl (2023). GPT-4 technical report. arXiv preprint, arXiv:2303.08774
[43] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2019). Language models are unsupervised multitask learners.
[44] Raventós, A., Paul, M., Chen, F., and Ganguli, (2023). Pretraining task diversity and the emergence of non-bayesian in-context learning for regression. arXiv preprint arXiv:2306. /5063.
[45] Reddy, G. (2023). The mechanistic basis of data dependence and abrupt learning in an in-context classification task. In The Twelfth International Conference on Learning Representations.
[46] Roughgarden, T. (2010). Algorithmic game theory. Communications of the ACM, 53(7):78-86.
[47] Shapley, L. S. (1953). Stochastic games. Proceedings of the national academy of sciences, 19500):095511100
[48] Shoham, Y. and Brown, K. (2008). Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press.
[49] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T. Baker, L., Lai, M., Bolton, A., et al. (2017). Mastering the game of go without human knowledge. nature, 550(7676):55-359)
[50] Sinii, V., Nikulin, A., Kurenkov, V., Zisman, I., and Kolesnikov, S. (2023). In-context reinforce- ment learning for variable action spaces. arXiv preprint arXiv:2312.1332
[51] Song, Z., Mei, S., and Bai, (2021). When can we learn general-sume markov games with large number of players sample-efficiently) arXiv preprint arXiv:2110.04184.
[52] Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine learning, 3:9-44.
[53] Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. (2015). Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28.
[54] Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 294.
[55] Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. (2023a). Llama: Open and efficient foundation language models. arXiv preprint 2rXnn:2302.13997 13971.
[56] Touvron, H., Martin, L.. Stone, K., Albert, P., Almahairi, A., Babaci, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. (2023b). Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288
[57]
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.,, Gomez, A. N., Kaiser, t.., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems, 30.
13

---

[58] Vinyals, O., Babuschkin, I., Czarnecki, W. M.. Mathieu, M., Dudzik, A., Chung, J., Choi, H., Powell, R., Ewalds, T., Georgiev, P., al. (2019). Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782)3350-333)
[59] Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. (2023a). Transformers learn in-context by gradient descent. International Conference Machine Learming. pages 35151-351770 PMLR.
[60] Von Oswald, J., Niklasson, E., Schlegel, M., Kobayashi, S., Zucchet, N., Scherrer, N., Miller,
N., Sandler, M., Vladymyrov, M., Pascanu, R., et al. (2023b). Uncovering mesa-optimizztion algorithms in transformers. arXiv preprini arXiv:3309.08858
[61] Wainwright, J. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48.
Cambridge university press.
[62] Wang, J., Blaser, E., Daneshmand, H., and Zhang, S. (2024). Transformers learn temporal difference methods for in-context reinforcement learning. arXiv preprint arXiv:2405. 13861.
[63] Wang. Y., Liu, Q., Bai, Y., and Jin, C. (2023). Breaking the curse of multiagency: Provably effi- cient decentralized multi-agent with function approximation. arXiv preprint arXiv:2302.06660 0666000000006
[64] Wu, J., Zou, D., Chen, Z., Braverman, V., Gu, Q.. and Bartlett, P. L. (2023). How many pretrain- ing tasks are needed for in-context learning of linear regression? arXiv preprini arXiv:2310.0832
[65] Xie, Q. Chen, Y., Wang. Z., and Yang, Z. (2020). Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Conference on learning theory, pages 3682-3682. PMLR.
[66] Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. (2021). An explanation of in-context learning as implicit bayesian inference. arXiv preprint arXiv:2111.02088
[67] Xiong. W., Zhong, H., Shi, C., Shen, C.,, and Zhang. T. (2022). A self-play posterior sampling algorithm for zero-sum markov games. In International Conference Machine Learning, pages PMLR.
[68] Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. (2019). Are transformers universal approximators of sequence-to-sseuuecee functions? arXiv preprint arXiv: 1912. 10077.
[69] Zhang, K., Kakade, S., Basar, T., and Yang, L. (2020). Model-based multi-agent zero-sum markov games with nparmoptimal sample complexity. Advances in Neural Information Processing Systems, 33:1166-1111
[70] Zhang, K., Yang, Z., and Başar, T. (2021). Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384.
[71] Zhang, R., Frei, S., and Bartlett, P. L. (2023). Trained transformers leam linear models in-context. arXiv preprint 20X.v22306.09927.
[72] Zhong, H., Xiong, W. Tan, J., Wang, L., Zhang, T.. Wang. Z., and Yang, Z. (2022). Pes- simistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning, pages 27117-27142 PMLR.
[73] Zisman, I., Kurenkov, V., Nikulin, A., Sinii, V., and Kolesnikov, S. (2023). Emergence of in-context reinforcement learning from noise distillation, arXiv preprint arXiv:2312.12275
14

---

A An Overview of the Appendix
In this section, an overview of the appendix provided. First, additional discussions are presented in Appendix B which cover broader impacts of this work and thoughts the future directions.
Then, the proof details omitted in this main paper are provided. While the decentralized learning setting is the major focus in the main paper, the discussions and proofs for the centralized learning setting are first provided to facilitate the presentation and understanding as the decentralized learning setting is more challenging.
The supervised rre-tranning guarantee (i.e., Theorem C.3) for the centralized learning setting is
proved in Appendix The details and realization of VI-ULCB (i.e.. Theorem 4. presented in
Appendix The proof' for the overall performance guarantee (i.e., Theorem can be found in
Appendix
Subsequently, the proofs for the supervised pre-training guarantee (i.c.. Theorem 3.3 in the decentralized learning setting are provided in Appendix [F] Appendix Conttains the details and realization of V-learning (i.e., Theorem 3.4p. The overall performance guarantee (i.c., Theorem 3.5 is proved in Appendix H
A detailed discussion of the covering number is provided in Appendix
Finally, the setups and details of the experiments presented in Sec. 5 are reported Appendix J
B
Additional Discussions
B.1
Broader Impacts
This work mainly provides a theoretical understanding of the in-context game-playing capabilities of pre-trained transformers, broadening the research scope of in-context reinforcement learning from single-agent settings to multi-agent competitive games. Due to its theoretical nature, we do not foresee major negative societal impacts; however, still 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.
B.2 Limitations and Future Works
The research direction of in-context game-playine is currently under-explored, and we believe that there are many interesting topics to be further investigated.
Different game forms and gume-solving algorithms. This work mainly studies the classical two- player zero-sum Markov games, which can be viewed as the most basic form of competitive games, and has particular focuses on constructing transformers realize V-learning [32] and VI-ULCB (8). The cooperative games, on the other hand, are conceptually more similar to the single-agent setting pyperrativ-competitvy
38 There are more complicated game forms [46] 48), e.g., the mixed
games, which requires different game-solving algorithms. We believe the framework built in this work beneficial to further explore the capabilities of pre-trained models in game game-theoree theee-theoeeticl scenarios.
Pre-training dataset construction. This work considering the pre-training dataset is collected from the context algorithm with additional augmentation. First, while the current proofs rely on the augmentation, it will be an interesting topic to understand whether is necessary. As mentioned Sec. I. learning in Markov games typically require more diverse data than learning in single- agent settings; however, the minimum requirement to perform effective pre- pre-training worth further exploring. Moreover, in the study of single-agent RL (35), it is shown that pre-training with the data from the optimal policy is more efficient, which is further thcoretically investigated in Lin et al. [38. In multi-agent competitive games, it is currently unclear whether similar strategies can be incorporated, e.g., pre-training with data collected by Nash equilibrium policies or best responses for certain other policies.
Large-scale empiricul evaluations. Due to the limited computation resources, the experiments reported in Sec. are relatively small-scale compared with the current size of practically adopted transformers. would be an important and interesting direction to further evaluate the ICGP capabilities of pre-trained transformers in large-scale experiments and practical camerthccoettc
15

---

applications. Also, the training dynamics are also worth further investigation, e.g., the sudden shifts learning effectiveness reported by Reddy (45]
Besides these directions, from the theoretical perspective, we believe would be valuable to investi- gate how extend the current study the tabular setting to incorporate function approximation, where we conjecture it is sufficient for the pre-training dataset to cover information of certain rep- resentative states and actions (e.g., a well-coverage theoretical question is how to learn from a dataset collected by multiple context algorithms. From the practical perspective, future study on the impact of the practical training recipe (e.g.. model structure, training hyperparameters, etc.) would be desirable to bring additional insights.
the feature space) 722 Another attractive
C Proofs for the Centralized Supervised Pre-training Guarantees
First, the definition of the centralized covering number and an assumption of centralized approximate realizability are introduced to facilitate the analysis, which are also leveraged in Lin et al. (38].
Definition C.1 (Centralized Covering Number). For a class of algorithms {Algo 0 E θ}. we say Ô C is a p-cover of O if is a finite set such that for any E O there exists A E such that for all D' E S,t [T). it holds that
||og Algg(:,-1D''
log
())l S
The covering number (p( the minimal cardinality of such that is a p-cover O Assumption C.2 (Centralized Approximate Realizability). There exist l 2 and Greal 0 such that for all E Stte [2], (a, b) E A x B, it holds that
Algo (a, b(D(
.s) ( 1)
log
D
Alge- (a, b
Ereal.
Then, the following pre-training guarantee can be established.
Theorem C.3 (Centralized Pre- tre-training Guarantee). Let θ be the maximum likelihood pre-training
output. Take Ne = Ne (1/N) as in Definition C.1 Then, under Assumption C.2 with probability at least 1 - 8, it holds that
log (NoTS/5)
E D
[ TV(A1g, Algal .s)
V Ereal + TS
Proof of Theorem C.3 This proof extends that of Theorem 6 in Lin et al. 38 to the multi-agent scenario. Let è be a p-covering set of θ with covering number Ne. = NN as defined in Definition C.I With Lemma 15 Lin et al. [38], we can obtain that for any @ e O, there exists
such that for all D t [T] and S.
TV (Alga, Algel DC A S
For m E [We), E (T), E [N], E S, we define that
Algo (af by 1 .)
a. (s) log
Alge... (a) 6/ 1D .s)
According to Lemma 14 in Lin et al. [T), E S, it holds that
38 with probability at least 1 - 6, for all m E [We)
i.m (5)
))
Σ 1og(NN//))) KE[N]
Σ TE(N]
log
E
exp
2
Furthermore, it can be established that
E C (s)
Algo... (af 1/ 1
exp
2
=E
(V
Algo (ai b% D. D.-11
D
16

---

=E (a.jjEAxB
VALgom. (a,blD ,5 Algo (a, b
which implies that
E exp
i.m
(5)
=
E
Σ
(VALEO,, (a,blDt .8) v Algo (a, (a, .8)
2
2
(o,b)EAXB
TV (Alge,,, (. .
E
where the inequality is from the fact that the Hellinger distance is smaller than the TV distance. Then, we can obtain that for any 0 covered by Om, it holds that
ED TV (Algo Algo D 1
,s)])²
(0(+ {)] + ED [TV (Alge... Algo D $ (Ep [TV (Algo: Alge... D
$ 2 (ED [VV (Algo Algo | ,))) + (ED [TV (Algo... Algo D' D'-11
s)))² ,)]]
< 2
TV (Algo: Algol
|D-_1,)) .8) 2
+ 2p²
(s)
4E
exp
+
E ())
)1) + 2p²
S 4-4log
cxp
2
which further implies that
N
EEn TVV (Algo-
D'g 1'
SES [T
)1
Σ E
log E exp
2NST
2
#ES (E(T] KE[N
Σ
Σ
(s) + 2N + 4ST LogT
#ES (T iE[M
Alga ( 1D ,6)
Σ E Σ
log
+ +2NSTp² + 4 log(e1/9)))))
Algom. (o) 1/ 1D
SES
Alga (0) D. i. 1D
2
ΣΣΣ log
+ 2NST +
Algo (a by ( (D/-1110
SES TEIT
Thus, for the obtained O, with probability at least 1 - 5, it holds that
N
ED [TV (Algo- Alggl Dlgg(D'-1, s)))
SES [E[2]
Algo (a Dy D1. D.-11 ,)
Σ log
+ +2NST + 1
Alga (a) by 1D--1 .8)
#ES (E( KE(N
Algo (af 2,0 1D
Σ log
Algo (a b1 DD .8)
#ES (E(TT KE(N)
Algo (af b 1/ 5)
))
Σ log
E
ST log())/))
Algo- (a bb
SES dE[T]VE[N)
+ SN 2NST + 4ST LoTToggNo
17

---

< 2N STlog(TT/0) + 2NST + + 1ogg
Further by Cauchy-Schwarzz inequality, we can obtain that
ΣD SESTE
E
TV (Algo-
Algg ( AlgglD'-1
ST sES tE|T
D TV (Algo. Alga ,
log SG
ST Ercal STV
+ ST ST - STP
Taking p = 1/N concludes the proof.
D Proofs for Realizing VI-ULCB
D.1 Details of MWU VI-ULCB
We here note one distinction from the VI-ULCB design considered in this work from its vanilla version proposed in Bai and Jin [8], which makes VI-ULCB practically implementable. Especially, Bai and Jin [ requires an oracle solver that can provide the exact NE policy pair (1² v²*) from any two general input payoff matrices (Q, E RA x RAX However, is known that approximating such general-sum NE is computationally hard (specifically, PPAD-complete) [19], which makes this vanilla version impractical. Luckily, later studies (9 [40 65 have demonstrated that a solver finding one weaker notation of equilibrium, i.e., coarse correlated equilibrium (CCE), is already sufficient. Following these recent results, we replace the NE solver with an approximate CCE solver in VI-ULCB. Moreover, consider finding such CCEs via no-regret learning In particular, both players virtually run multiplicative weight update (MWU) (which also known as Hedge), a classical no-regret algorithm, with payoff matrices (Q, Q) for several rounds; then, an aggregated policy can be generated as approximate CCE. The details of the VI-ULCB algorithm are provided in Alg, []]
More specifically, we consider that an approximate CCE solver adopted such that with each pair of inputs (Q" (s,+))) (8,.)))) -)), we can obtain an apcr-appro CCE policy <<(,, -ls) which satisfies that
E (..l)e) Q a, b)] max (a. (v-la) [(s a", 6)] ECCE
EESS
((a.))>>*'(>l (v)s)) Q a, b)]
S min B(aM)a Q(ss, a, b*)] + ECCE-
bEES
We also specifically choose obtain such approximate CCEs by having both players (virtually) perform MWU against each other. The details of MWU are included in Alg 2 where we use the following notations denote normalized losses:
L L"(s,a,b)= H 4-Q" (s, a. b)
Q",
(s),,, =
H
H
Standard online learning results 13 guarantee that using learning rates 11 Vlog(A) (log(A)/NMo) and BB /log( (log(B)/NMww/ after NMwu rounds of MWU, the policy
x² (1()=18)=
1
Σ ((((1)))2((1)))))
NMMU nE[M]
is an accr-appro CCE policy, with
log(A + B)
H1,
NMwL
2 Another common method to find CCEs is through linear programming (LP). It will be an interesting direction investigate whether transformers can be LP solvers, which however out of the scope of this paper.
18

---

Algorithm 1 VI-ULCB
1: Initialize: for any (s) (s, H. (" O, (s,
N"(s, b, 8') f- 0
2: for episode g 1.... do
3: for (s, b) E S x Ax B do
4: Compute Q (s. + min { مh (8, a,a) b)+ + ppuph+1]
(8, a, b) + cV
HRSe
5: Compute Q" (s. max ph (8, a +
H2 foh (8, CV N" .a" ,85)
6: end for
7: for S do
8: Update Th (+, 1s) + Ex-approximate CCE (Q"(6..)))Q"(()))) (s....)) solved by N-round
MWU
9: Compute V" (s) t (" bls) (s
Compute (*) f E.,b (a. ((s) (s,0,
end for
12:
for step h 1, .H ..do do
13:
Take action (a b²)) ~ nhh (1-11)
Observe reward Thh and next state sh++1
15:
Update (A(s", a², b²) and (s a", oa shtl)
Update 5sh (-|sh, a² th) and ph ph(s ah bh)
16:
17:
end for
18: end for
Algorithm 2 MWU
1: Input: learning rates 11A //og(AA//N and na vlog B)/N, action sets AA and B with size
A and B, loss matrices I" (s, , and L (s..))
2: Initialize: cumulative loss 0+ + 0,4 and 0_ + OA
3: for 1,....N do
4: Compute (-(s) < 02 a3(-n404) E ((A)
5: Compute v (1())))) <- 03( (3(-1100] E A(B)
6: Observe vectors ++,n R with (+,(aa) (a) (-15) T. as,
7: Observe vectors O_,n E B with 0 o, (b) = (-((s) ,s,,,,
8: Update O+ = 0+ 0+, and O_ O_ o_m
9: end for
10: Output: policy EnE[Ny 1 (1)())))))))))/)
Furthermore, for certain bounded ECCE, Xie et al. 65 demonstrated that the performance degra- dation can still be controlled. Following the results therein, the following theorem can be easily established.
Theorem D.1 (Modified from Theorem from Bai and Jin 8 With probability at least 1 - 6, in any environment M, the output policies (11 v&) (9: : [G]] from the MWU-version of VI-ULCB satisfy that
Σ Egetor vitea (s')
VHL (x') ABT (
TecCk).
With 8 = 1/T, to have non-dominant loss caused by the approximate CCE solver, can choose NMwu = G. Then, for any environment M, holds that
Egetor Vl.e ViluO (s!) - VM (s)) = H3S AV lBTToo
19

---

D.2 Proof of Theorem 4.1 The Realization Construction
D.2.1 Embeddings and Extraction Mapping
We consider each episode of observations be embedded in 2H/ tokens. In particular, for each t [T], we construct that
0.4
0
pre.a h 1re,5 1 prece
h2--1 h(s9.h)
39.7
hog
OAB
pre.d
pos 21
a8.h
69.h
h pre,a
y9hh
h A
h2 h(a9th 63. ,1.h))=
0g
ÜAB
pos
where 59th a9th Boih are represented via one-hot embedding. The positional embedding pos; is defined as
g
h
t Ej
pos;
V;
i
12
1
where en is one-hot vector with the h-th element being 1 and 11 [hg 0) denote the tokens that do not embed actions and rewards.
In summary, for observations D 10--uss (s'), we obtain the following tokens of length 2/ 1:
. H = h(D'11, = [h1. h2.... h2-11 = [h(s*), n(a", b², (,,r"))....... "l....,,sss)))).. h(s*)]
With the above input H, the transformer outputs H TFo, (H) of the same size H. The extraction mapping E is directly set to satisfy the following
E h h = h
R AB
i.c., the part of the output tokens is used to store the learned policy.
D.2.2 An Overview of the Proof
In the following, for the convenience of notations, will consider step t i.e., with observations U (s(+1). Given an input token matrix
H h(D*, ++) [h, he
h2
we construct a transformer to perform the following steps
b,b.), hare N" a, b)
h b.c.)
h fa..ba Q (,,,
22t44 b pre.c h 20+11
por (s) (s'ls' b) ptt ())
(" b. Nh (s,
step
step
step
("
h
0 pos
0
pos
pos
20

---

Apee,fad (a,b,ct
h 1
(a.
th bls)
f2 21-+-1
(s) (8)
1
(a,b)
h b
1 post
stop
stop 5
(*)))
stop
n h (.. ght1)
0 p0$21+1
h2241
O
heee1
p0s2++1
use (s, b), (s,a,,,,,)) (" a, (s," b), io (s'1s,,,)); (",s,, b). Q" as,,,,b), us, and (" to denote their entire vectors over h E [H] E S,a E A, B,s' E S. The notation denotes other quantities in hd (((42))
where
The following provides sketch of the proof.
Step There exists an attention-only transformer TFa to complete Step with
L = = max M = A(HSAA)), ||0]| HS [E(2]
Step There exists a transformer TFg to complete Step 2 with
L = 0(1,, max M O(HS AB), d' OC [E[L]
||||| O(HS AB G GH).
Step There exists a transformer TFg to complete Step 3 with
== L max M0 O(SAB), d²(1) O(SAB), |0] O(H SAB).
[E|L]
Step There exists a transformer TFg to complete Step 4 with L= OGHS),
max M O(A)), d' O(AB), ||||| O(H AB). lE(L]
Step There exists an attention-only transformer TFa to complete Step 5 with
O(), max (1) O(HS), |0|| ((H)).
[E[L]
Step 6 There exists an attention- only transformer TFa to complete Step 6 with
0(), max ( O(H)) ||0|| OHS GH).
[E[L]
Thus, the overall transformer TF, can be summarized as = O(HS)) max (1) 0 OHSS = O( [E[L]
|0| = OH
AB O
G + GH).
Also, from the later construction, we can observe that log R) Ö(1)
D.2.3 Proof of Step 1: Update \ a, 6), N² (s, a, 6, a,
and (s1 b),"
This can be similarly completed by attention-only transformer constructed in Step 1 of realizing UCB-VI in Lin et al. [38].
D.2.4 Proof Step 2: Update (6''|,, a, b) and f(s, a,
This can be similarly completed by transformer constructed in Step of realizing UCB-VI in Lin et al. (38
D.2.5 Proof of Step 3: Compute Q" (s'ls, a, b) and ("sls,, b)
The computation of Q" (s'ls, a, b) can be similarly completed by transformer constructed in Step
3 of realizing UCB-V VI in Lin al. (88 The Q part can also be obtained by modifying few plus signs to minuses.
21

---

D.2.6 Proof of Step 4: Compute CCE
This is the most challenging part of realizing the VI-ULCB design, which distinguishes it from the single-agent algorithms, e.g.. UCB-VI VI (6. mentioned Appendix [.T] we obtain an approximate CCE via virtually playing MWU. In the following, for one tuple (s, h), prove that one transformer can be constructed perform one-step MWU update with that
= 0();
max M O(AB), = O(B)), |||| O(H AB). tE[L]
To obtain this result, we construct a transformer to perform the following computation from inputs to output for all L' S l:
(s
L (s,,r))
ren O+,T
h2: [0], h2141
Eren O-it
Hall1s)
(n(-ss)
Σ
ter (-)+(()
(",,)))
I (s
ren+1 --
compute
h22 = =[ hx41
+cnt1 O-iT
Mat1 (1ss)
(xti(-(s)
Σ Et Mr (-)ux(-)
Note that here we again use the notations I' (s.-.)) H H- and (s...) (a..s) to denote the normalized losses. It can be seen that this computation can be performed via one ReLU MIP layer.
Step 4.1: Get 0+,a and 0_
First, we can construct that for all t' St
U22
1
U2
Q hzg
0
Q (1) hwr1
Pn (:1s)
L'
++111
H
H
H
H
K
h2g
0
K 0,1
h2e41 =
I (a,) - -H
a,1
H
t'
+1
a.1 hav 26',
h2
21'
With ReLU activation, this constructed transformer leads to updates that h and h o+,((a) (a). With another 1 paralleling heads, the whole vector 0+.z can be computed. Similarly, with B more paralleling heads, the whole vector o-,n can be computed.
Then, with ReLU MLP layer,
obtain that
Iren 0+.7 + w
Erent1 0+, =
].
h O, h6r+1
0-,
Erentio 0-
The required transformer can be summarized
= () 0(A + B), d' 0
||0|| O(H).
22

---

Step 4.2: Get (n+1(-(s) and Bx+1(-18)
We construct softmax MLP layer such that
1 (2) h2c) 1a w h2r OA, o. (W1
(1)
w h2 = IA Erenti of m |. ( h20+1) (-1s( ]
where 7A = v (lg(A) Thus, (n+1(-1s) can be provided. Similarly, another MLP layer
(W13), W } with softmax activation can provide (-41(-1s). The current output can be expressed
M4n (.(s))
0
V/((1 (s)
22
A
1
14
R220+1
Pn++1 88)
1n
B
Un+ 1 (-18)
We can further construct one more attention layer as
022
U26+1
Q h2r
(3)
h20'+1
I'
1
K h22
(3)
-1
K 33) h22+11
-1 1
t' + 1
V
(3) hzg
2t'
14
V, (3) h2e'1 = (2t' + +1)
14
1B
1B
B
With ReLU activation, this construction would result that
1/4
1
1
(-1s) Vn+1 (-18)
Mn+1 (-15)
h2e
1B
+
3
1B
= 0, h2041
+ 0
Ma+1 (-1s)
B
B
At last, one ReLU MLP layer (W(S)
w be constructed to replace pe (-1s) and un (-|s) with
Mn+1 (-1s) and Un+1 (-1s):
Un+1 (-1s) - Hn( Un+1 (1)) un (-18) ].
3 oF W h2e 0, 3 of (3(3)2222))
h2042)
The required transformer can be summarized as
3, max ( = O(1,, d' O(A+B)) |10| 0( O(vloo(())/+++++ //gg 1).
SE(L]
Step 4.3: Get M (11()))
We construct
0
An+1
Q have
Q
(0)122241 h2:41
t' + 1 1
1
0
Un+1 (b|s)
K
(1) h22
1
hgr+1 K
t'
1' + 1
Vd har 21', (6)
h2 21' 1.
With ReLU activation, this construction can update that
h2 0, hw Mn+1 (als)
Using an overall AB paralleling heads, we can then obtain pn+ (+ (1) Then, with a ReLU MIP layer (w(55, w ), we can obtain (1)))
Mr
The required transformer can be summarized as 1, (1) O(AB), d' O(AB) ||||| O(AB).
Combining all the sub-steps provides proof of one-step MWU update. The same transformer can be stacked for G times, which completes the G-step MWU.
23

---

D.2.7 Proof of Step 5: Compute V
(s) and (s)
We construct that
n (+,-1s)
Q
11) h22
E'
Q
h22++1
l' + 1
H
0
2 (8, :)
K(D (1)
K(
- H
h22441
H
1'
t' +1
V1 ( h2r = 2t', V1 h2e+1 = 26' + 1.
With ReLU activation, this construction leads to that
h2 = 0, hwr+1 = n (-, 1s) Q= (s.,,.) = (s. (s).
Thus, with overall 2HS paralleling heads, the values of (V (s), computed.
(8), (s) h E [H] E S} can be
The required transformer can be summarized
L 1, =²)=
= OHS)) ||0|| O(HS).
D.2.8 Proof of Step 6: Obtain n (.,-
We can construct one H. Shhad transformer that for all (s, E S x [
0
s''1
eN
e
Viea h2g
t'
Q 11)
h20+1
t' +1
1
1
Es
e,
en
en
K (1)
h.s hay
-1
K
(1) his h2
-1
;
t'
t' ++1
(1) hav O,
his h2 x (1,))))
B.s
With ReLU activation, this construction leads to the update that
1
h = 0, h20+1
N
21' +
Then, we can construct that
2 2GHt'
2 +1 2G +1)
Q hoze
h2e41
1
(1()) haw
-1 2GHt'
-1 2G +1) 2 +
v h2g 0, V h22+1
+1 (., (11
With ReLU activation, this construction leads to the update that
hay O, h2 = n hh-1 (., (,,11t+++1
The required transformer can be summarized
= 2, max (1) = O(HS), | = O
[E[L]
24

---

E Proofs for the Centralized Overall Performance
Proof of Theorem 4.2
First, obtain the decomposition that
E MMA.DWE
Vitee
(st) Vue (s22) M
og [c]
Σ gelGl
vitue (s') (t
110
E
M~A,D=P
Aino
Σ [E|[G
Viuo (st)
T. AA
Σ Villa (8t)
9E
((5))
B +BA.A.D.PAP
- E
-W.
DwP
9EIG
0E|G)
Via Theorem D.I it holds that
vile
(
0 (v HSS 1og
E M.A.D
Then, via Lemma E and Theorem C.3
we can obtain that
EE M
Σ
EE MaA.DNP
Σ vuaatss (s!)
9E|G)
gE|GI
=0 T A.AMAADDEtHO +E(T)
ΣΣ
TV (Algo: Algol D [8)]
log (S/0)
0 T V + sT
N
and similarly,
vituo((o))
Ma 4i
Σ vtua (s')
E Dwr
Σ [
Vive (8')
LAE|G
- ( + Tesy log (NoTS/8)
N
With Theorem 4.1 providing that Graal = 0, combining the above terms completes the proof of the regret bound. The bound the covering number, i.e., log(Ne) can be obtained via Lemma I.4 O
Lemma E.1. For any two centralized algorithms Alga and Algg, we denote their performed policies for episode y are (Nā :.)). whose marginal policies are (pa, va) and (ug, vg). For {uā, ug). holds that
E. Σ
Enetor V4 (s)) -Es
EB Eneeta
v
VM
(s')
< T-Ea
Enery TV (Tà D"/ .s)
where Eal. and Eo[-] are with respect to PA and PA
Algs
A similar result holds for {va. vg).
Proof of Lemma E. It holds that
E D~
Σ
D
nep
Σ
v (st)
as
9E
25

---

E Durdeen
vagi (s')
Σ
(81)
9E|G)
DE|G]
=(term
+ E Dwptt
Vitfi((s)) (s²)
B D
Σ
(8))
DE|C)
[-lermn
Denoting DH = D(0-1))H+1:g and S(DH) = Ene(my r9.h we can further obtain that
VHO
(s
(s')
M
(a)
I M
(s')
Vi
(1 (s))
E
uh (18))
[S(D")]
D p [S(D))
DRAP
Σ
E
D (ug) [f(D))
Dish
hE[H]
31
Σ
E
D [S(D")]
Dich-1
kE[m]
(6)
2H
Σ
E
(a
TV ( of (mt)( ). (48) (-19sa)))]
D
be[H]
(c)
TV (ug (H(sou)))) p. (119211))
2H
E
D 1-
hE(m)
M
(d)
2H Σ
Σ hE(F))
TV
Ta g (T-)) (c-15)
SES
where (a) is from the definition of best responses, (b) is from the variational representation of the
TV distance, (c) is from the fact that TV(# x v. x v) = TV(u, ('), and (d) is from the fact that
T6 (., E. n' ()) TV(x(,)) (:; ()) The above relationship further leads to that
(term E D. M
Σ VA (5 [E(C
Σ
(st)
zEGG)
< 2H E DNEgye
ΣΣ
TV a T3) DC-11 .8)
KE|TY RES
Also, denoting (D) = Egeron Vagii (st), it holds that
(term II) ED D
Σ V2 |E|G)
Dwintlen
Alea
Σ
V4'zl (s!)
0E(G)
E Di DUII: Min [o(D)] -
E De- In Du.== uig [D(
EE[T]
(E|T]
< 2T
E Ep-- of (ALg. Alge 1* ,
(E[T]
< 2T E
Mgo D-p
[E[T)
Combining (term 1) and (term II) finishes the proof.
26

---

Proofs for the Decentralized Supervised Pre-training Guarantees
Definition F.1 (The Complete Version of Definition 3.1 For class of algorithms {Algo, : 0+ b+). we say O O+ is p+-cover of @+, if θ is finite such that for any 0+ Q4, there exists 0+ O+ such that for all D'_ S,t [T], holds that
[lo Algø, (:, (--1DD4-,, log go, (1D4;
.)) S pt.
The covering number No. (p+) is the minimal cardinality of O+ such that θ+ is a p+ -over of +
Similarly. for a class of algorithms {Alge_ e__ E -- we say Ô_ C θ_ is povco of
__ if @_ is a finite set such that for any 0_ E e_, there exists O_ E θ such that for all
D² E S [T], it holds that
log Algo_ (,, (,-1D=-- log Alga (1D= 8)) p
The covering number No (p_) is the minimal cardinality of θ such that θ_ is -cver of O Assumption F.2 (The Complete Version of Assumption 3.2 There exists O E O such that there exists Eeal > for all t [T], S. a E it holds that
Alg+.0 D4 ,8) &..rell-
log
E B
Algo: (a (a|D4
Similarly, there exists 0 E e such that there exists rcal > 0, for all t E [T), S, b. B, holds that log E DwP.D 100
Alg (bb
S reall
Algo- (b)
Theorem F.3 (The Complete Version of Theorem 3.3 Let 04 the max-player's pre-training output
defined in Section 3.1.1 Take Ne_. = Ne__ (1/N) as in Definition F.l Then, under Assumption F2 with probability at least it holds that
E M~A.DaPHH
Σ TV (A18+.0 Algø ID ,5) (E(T),NES
log (Na, TS/0) TS Ve+
=0
+TS
N
Let θ_ be the min-player's pre-training output defined in Section 3.1.1 with probability at least - 5, it holds that
Take No. = N (1/N) as
in Definition F.l Then, under Assumption F22
E DaA.D
Aioo
Σ
TV (A1g_.u Algø 1D+11 (0))
rE(T),SES
log WNe_S//0
=0
TS TS real + TS
Proof of Theorem
F3
This theorem can be similarly proved as Theorem 3.3
G Proofs for Realizing V-learning
In the following proof, we focus on the max-player's perspective, which can easily extended for the min-player.
27

---

G.1 Details of V-learning
The details of V-learning notations are adopted
32 discussed in Sec.
are presented in Alg.
where the following
H++1 + n²
11 A Al (ISAA/A)))))
O1
Bn
n
H (o) An
Y2 [I(1-a+) ac))
7n Vh-
wp
On
After the learning process, V-learning requires an additional procedure to provide the output policy. We include this procedure in Alg. where the following notations are adopted
(s) the number of times is visited at step h before episode g, 9. (s) the index of the episode is visited step for the i-th time,
II a5)))). j=i-1
On
Following the results in Jin et al. 32 we can obtain the following performance guarantee of V-learning.
Theorem G.1 (Theorem in Jin et al. 332). With probability at least - 6, in any environment M, the output policies (ft, D) from V-learning satisfy that
IPS(A+ B) log SABT/O)
vti² (s (
G
Thus, with 8 1/T, we can obtain that
=0 E Dw - = (
H B) log SABT)
G
Algorithm 3 V-learning
32
1: Initialize: for any (s, a, E SSx Ax
H H 2- + 1/A
2: for episode g 1, Go
3: receive s!.1
4: for step h = 1, H do
5: Take action ag.h ~ T (-1s91h), observe reward r and next state $9.4+1
6: Update n = (s9.h) f- Nh (ss.h) )
Update V' + - a1-a Tr (sa.h)) + an (pesh + vh+ (santt)) + 3n)
7:
Update ("s.s))) t min H +1 h vn (sortt)
8:
9: Compute el (s a) + H-pooh phth-
1aa=aria wh phaaninpo for all a E A
11
10: Update (a) xc exp (- Ia. Eremn Wr (sarh a)) for all a e A
end for
12:
end for
G.2
An Additional Assumption About Transformers Performing Division
Before digging into the proof Theorem 3.4 we first state the following assumption that there exists one transformer that can perform the division operation.
Assumption G.2. There exists one transformer TFg with
L Lp.
max max (1)
MD, = dp, | Fp.
[e
28

---

Algorithm 4 V-learning Executing Output Policy j 32
Sample g Unif (1,
.G)
2: for step h = 1, ... H. do
3: Observe sh and set +- (s"
4: Set + o: (s") where [x] is sampled with probability On,
5: Take action a (-(s(11sh))
6: end for
such that for any E [0, 10, E l/log(A)/(AG), hi.... .e...... where
Vlog(A)AA (lgp:/AAA)))//(((///)// + 11. > 0, with input H
h: =
vi + e; he =
the transformer can provide output H = h1
he :..
x
h;
Vi + he
y
J x/y
0
We note that this assumption on performing exact division is only for the convenience of the proof one can approximate the division any arbitrary precision only via one MLP layer with ReLU activation.
In particular, let Ball (R) [- R denote the standard foo ball in R with radius R > 0, introduce the following definitions and result.
Definition G.3 (Approximability by Sum of ReLUs, Definition 12 Bai et al. 77. function g: R + R is (Sappox, Rt M, C')approximuble by sum of ReLUs, if there exists "(M, C)-sum of ReLUs" function
M
fM,c(2)) = Σ
Gm (a 1]]
m=1
with
1mll
C,
||am|li S 1, E BR+ Cm E IK me(M]
max
m=1
such that
sup [g(2) - fM,,C()) & zeBlll (R)
Eapprox
Definition G.4 (Sufficiently Smooth k-variable Function, Definition A.1 Bai et al. 7). We say function g R IR: is (R, C&) -mooth for [(k 1)/27 g is C* function on Ball (R), and
sup BcBallk (R)
V (=)(=)) =
sup #EBall (R) Ji. (
max
10 ... g(2)l S Li
for all i (0,1, ,8, with
max L S Cr. OSESA
Proposition G.5 (Approximating Smooth k-variable Functions, Proposition A.I in Bai et al. 77). For
any Eapprox > 0. R 2 C, > have the following: Any (R, Ce)-smooth function g R RR (Eapproxs R, M, C) approximable by sum of ReLUs with M S C(k) log(1 Ct/ Ce/Eappmu Eappma) ) / and C < C(k)Ce, where C(k) 0 is constant that depends only on k.
29

---

C₁ Then, we can consider g y) = (c1 + x:/(c2 + with ci 21, 2 y E 1, 1]. It can be verified that
1, |-1, and
C1 + 2 1 + C2
1
+
1 C1
(0(2, v)
1mg(a, 2/1
2
1,0(2,0)1
C
c+ y/
2
(c2 y)
(c))
2(c1 +
2(1+ + cI)
(g v)1 0; 10
(0,0g
(c + y)² S
(02 +)
(c2)
(c))
6(c1 +x)
6(1 + +c)
10,0(1, v)1 = 0: 10)((,,))
(02 41
(c2)
00000(2 v) = 0; 10,03((z v)
(c y)3 S (c2)
Then, from Definition G.4 there exists one Cj such that g(x, y) is (1, -mmoooth Thus, by Proposi- tion G.5 this function can be approximated by sum of ReLUs (defined in SefinitionG..3) With this observation, the division operation required Assumption G.2 can be approximated.
G.3 Proof Theorem 3.4 The Realization Construction
G.3.1 Embeddings and Extraction Mappings
We consider each episode of the max-player's observations to be embedded in 2H tokens. In particular, for each [T], we construct that
A
$9.4
h h+ (s
0
2
0
pre,
2r-11
pos
a9.h
h pre.o
pree R
h2: = h4 (asch ,rch)
Os
0
h
pos
where 59th ag.h represented via one-hot embedding. The positional embedding pos, is defined as
g
h
t
pos; :
U;
i
;2
1
where U == 1[h;- = 0} denote the tokens that do not embed actions and rewards.
In summary, for observations D4-1 U {8*}, we obtain the tokens of length 2/ which can be expressed as the following form:
H (D
[h1, 1/,,,,... h2. hx-11] 1] (s'),, (a',r)) h.......,))))) h+))).
With the above input H. the transformer outputs H TFa, (H) of the same size as H. The extraction mapping A is directly set to satisfy the following
A h-1 h2.-1 h RA
i.c., the part of the output tokens is used to store the learned policy.
30

---

G33.2 An Overview of the Proof
In the following, for the convenience of notations, we will consider step t + 1, i.e., with observations
D u {. Given an input token matrix
h+ (D*, st++) [h1, h2. ...
h2241),
construct transformer to perform the following steps
1 (a,b(a
pep (a.bec) (n(st Re (-(s*)
(a,
2 hrreeb ha hpreed
h N (*
(*
step 1
stop
((()
stop
O p0S2++1
0 p0S2++1
pos21+1
h 2
h pre, (a.b)
step
20+1 1 ( ( ((stt))
h 2
2t pest,d
h2
where n := (s9.A).
To the notations, in the proof, will slightly abuse TFg as TFa.- The following provides sketch of the proof.
Step There exists an attention-only transformer TFg to complete Step with
- 0(1,, max M = O(1,, ||]|| O(H)) [E[r]
Step 2 There exists a transformer TFa to complete Step 2 with
== O(H)), max M (1) O d' = OGG), |||| = O + GH), [E[L]
Step There exists transformer TFg to complete Step 3 with
L O(GHL))
max M O(HSA+ MD), d'= + G LE[L]
|||| = OGHHS
Step There exists a transformer TFa to complete Step with
L = 0(1,, max (1) = O(HS), ||0|| = O(HS
[E[L]
Thus, the overall transformer TFg can be summarized as
L= O(GHT)) max ( = O(H5² + HSA MD), d' = O(G A A dd), (E = O G3 FD).
Also, from the later construction, we can observe that log R) Ö(1). The bound on the covering number, i.c., log(No (og(NN,)) can be obtained via Lemma I.4
G.3.3 Proof of Step 1: Update (sahh)))
From the proof of Step in realizing UCB-VI in Lin et al. (38). we know that there exists transformer with 3 heads that for all E'
move s" (a", r²)) from h and h to h while maintaining heg updated. This constructed transformer is shown in Lin al. 38 be an attention-ons only one with ReLU activation and
L = 2, max M < 3, ||||| < O(H)).
[E[Z]
31

---

Then, still following Lin et al. [3]. another attention only transformer can be constructed so that (s)s") can be computed in h The constructed transformer has ReLU activation and
L 2,
max M = O(1,, |00| = O(H).
[E[4]
In summary, at the end of Step 1, we can obtain that for all 1' S t,
se
ar
0
pe
h
h
pos2r'
Ne
(ser
pos
with an attention-only transformer that uses ReLU activation and == M O(1), ||o]] = O
[E(L.
G.3.4 Proof of Step 2: Compute (s and V (sa.k)
In Step 2, let n² = (s*), the following computations will be performed:
now (8") - (1 -On't (ola + ane (r" + 1 (s²tt) Bnt),
V2 (8*) + min {11 h, Vic ( (8))
First, similar Step 2 in realizing UCB-VI VI in Lin al. [38,, can obtain an and 8n in each h 22 via transformer with ReLU activation and
L 0(1,, max M O(), d' O ||]|| O(G*).
[E[4]
Then, we can assume that the values { old (s), Vah (s) h e [M], s E S} is already computed in token h and prove via induction show that the of new values can be computed in token hd h2 i.e.,
VIR (-) VEH old O
(-)
h
h
pos
pos
po
FIIH Dow V VI-H noW O
compute
hd
hd h22+1
pos
poS
In the following, we will show that this one-step update can be completed via transformer that requires
L 0(),
M O(HS)), d' O(G), ||0| O GH),
(E[z]
and the overall updates can completed via stacking similar transformers. Step 2.1:
- T|-
First, we obtain an auxiliary value -- ||'
7 in each h4 - and hd for all particular, we can construet three MLP layers with ReLU activation, i.e. } to sequentially compute that
( will) (2) w wr(3) w(())
[ 10 or ([ - 1 1);
32

---

(1 (11--1-1 1) + or ([ -
-
[1'-1-10 + | T - 1I' 1
be observed that - The required transformer can be summarized as
7| reaches its maximum at L' = r +1.
=, |0| = O(GH).
Step 2.2: Move Vili (.) and V1:# (.). Then, we move V (-) and VIl old (-) from h2 to h2r41. In particular, we can construct that
U2
122'
1
Q2h2r
Q1h20+1
t'
t' +
1
1
K
T
K K/h2r+1
T
-1
-1
t' +
+
Vishg (.) VEl (.)
vih2r-1 (2T -2F-1=
Vih2 = Vih2r+1 =0.
With ReLU activation, this construction leads to that
h22 hay + Σ
a-11 - -1- + V1h, =0 V St
21
$$28
h2241 h2241 + 2t'
Σ or (- - - + +1 Vih,
i52t'41
VI- old (.) ]
Vi-h(1 (-)
2441 (Vih2r-1 + Vihw + 2V1h2041)
if =T
otherwise
The transformer required in Step 2.3 can be summarized as
L = M = 0(1), |00| = O
Step 2.3: Compute
V1: new
(.) and vl:H (-)- new
Finally, we get to compute F-1:1 new
(-) and V-llf (.), where
new
Vsta("" Csnr (sT((") + Oxp (r + VTT (87+1) + Bar)
new
We can have HS hhad transformer that
U21
1
7
-1
+1
Qhe
Qnehge+1=
Se
Cx
eM1+1
1
0
33

---

1
Kin
K2.
1'+1
Es
6,
eh+1 -2
eh+1
-2
1
1
V2. (2r + 1) (s) Chas ].
It holds that for all t'' t,
1 Σ
h22 h2r +
Σ
or (-1
+(() ew Ex+1 - 2) Vn,
21'
h,s i520
h21411 h21+11 +
Σ
Σ or (-10' - - (1)) + 8t -es + eww+1 eb + a -2) Vish:
21' +1
h,8 i520+1
Vill (>) Ond Voli (st))
ift' =T otherwise
which completes the computation (1 Ohnz (s")
Two similar HSShead transformers can further perform (1 Onr V (87) anr + Onr Pn. and similar H H head transformer can finalize View (s") as Oxe Vold (s") + an r Onr Bnr Our V old (s*+1).
Finally, from the proof of Step 3 in realizing UCB-VI in Lin et al.
38 one MLP layer can perform
Vola (s*) min
new (s").
The required transformer in step 2.4 can be summarized
L 4, max M = O(HS²) d' = 0(1), ||0|| O(GH).
[E[L]
Thus, can see that the update of h2r+1 can be done. Repeating the similar step for each [2] would complete the overall updates.
G.3.5 Proof of Step 3: Compute (s9th,, a) and n² (alss.h))
In step 3, let n² (s")") for step 1, we update
H rt V4+ (81-1)
1fa = a²) Va (aa (a (0)55)) 7nd
L (s' a)
H
(_ Yhe
Mhew (als") exp
Wi (s a)
Wny
*E(n"
First, similar to Step 2, we can obtain w Thy / /ww,"' and N in each h6p41 via a transformer with ReLU activation and
L O(1), max M = 0(1), d' OGG), | = ((9))
[E[L]
Denoting vectors L I HSA and μ RSA containing the cumulative losses and policies, i.e., Eie(n) with (s, a) and {²(a)s) Similar to step 2, we will assume that the values of [Cold M
34

---

which are computed via information before time are already contained in token h and prove via induction to show that the set of new values can be computed in token h 2 i..,
Cold
hg
21
Hold O
hg
h h
20
poS27+1
pos2r-1
Lnow Mnew 0
compute
h
hd
h2r+1
20
p0S
In the following, will show that this one-step update can be completed via transformer that requires
L O(DD),
max M O(HSA+ MD), d' d' O A), |0| - O [E[L]
and the overall updates can be completed via stacking T similar transformers. Step 3.1: Obtain T -
T
First, similar step 2.1, we can have an auxiliary value -- 1t' 1 -| in each h and h for all / < via three MIP layers. The required transformer can be summarized
d'
||0| O(GH).
Step 3.2: Compute ' (E=ss a).
First, similar Step 2.2, we can move Cold and Hold from h hdr+1 while keeping other tokens unchanged. In particular, we can construct that
U2
Q1h2r=
Q1hw++1
1
K h2g
K h224+1 =
T
-1
-1
+1
+'+2
Lold Hold
Viher-1 = (2T +
Vih2r = 0, Vi 0.
With ReLU activation, this construction leads to that
Lold
if =
h2 = 0, Vt < t: h22441
Hold
0
otherwise
Then, using similar constructions as Step 2.3, we can specifically extract VT+1 and (aa(a")s" h while keeping other tokens unchanged. Following the extraction, one MLP layer can com- pute the value # - (x)+)) and add h The required transformer can be summarized
H
as
L= 0(1), max M = O(HSA), d'=1, ||0|| - OGG)) [E[L]
35

---

With Assumption G.2 for token her+1. we can further have one transformer to compute
(5 a²) - VT+ (T
H
Mola (a" (a"(s)) + 7n2
The overall required transformer be summarized
O(LD), max M OHHSA+ Mn), 0 |0| - + Fn).
Step 3.3: Update y² (als").
First, one transformer can constructed to update Lold to Leew h2r+1
In particular, we can have
U2H
22 +1
l' - 1
Q2,
Qu.
h28411
se'
eh-+1 1
-T
-T
-1
K K2r
K Knr
1'+1
es
e,
Ch+1
Ch+l
-1
Vn. -(2 + 1) Lotd Lo s,
With ReLU activation, this construction leads to that
h2v 0, vt' < t; h2 (ol(()()),
if =T otherwise
With a similar A-head transformer, we can add wa, E (s a²) to Lota (N(T), s" a²) and thus obtain the new values ( (N(T), sT ..). Furthermore, a one-head transformer can obtain
h2r41
Tn
Lnew (
Why
Finally, with another softmax MLP layer, we can obtain Piew ( (.1sT).
The required transformer can be summarized
L = 0(1), max (1) O(HS A), d' = O(A), |0|| = O(GH'S)
TE[L]
G.3.6 Proof of Step 4: Obtain μ / (-|s/+1)
This step is essentially the same as Step 6 in realizing VI-ULCB, which can be completed with transformer that
- M HS, ||||| O(HS).
H Proofs for the Decentralized Overall Performance
Proof of Theurem 3.5
We use the decomposition that
E Mig
vile M
(s)) (st))
E M. (1 -V (82)
M~A.D~I
36

---

V (st)
E3 PM (ot)
1158 MWA. M
E A
- E M NEW
(
First, via Theorem G.1 holds that
( =0
(V
H B) log (SAB))
E M VMr (s*)
Vp. M
G
Then, via Lemma and and Theorem 3.3 we can obtain that
VM (it)
Aing [V (st)
M Also
E
=0 H Σ
Ea TV (Ma
uggl + TV (Va v// 13110=11,,
1E(T]
log (Ne,, TS/6)
log (Ne_ TS/6)
=0 THSVE+.m THS VE + THSV
+ THS
N
N
and similarly,
V (s!) PWA.D 3600 M
as (s
M~A.D=F Alg m
log (Ne, TS/6) + THS
log (Ne_ T5/8)
=0 THS +HS VS-SVS-.rann + THS
N
N
With Theorem 3.4 providing that & E-areal 0, combining the above terms completes the proof the regret bound. The bound on the covering number, i.c., log(Ne,) and log(Ne-) can be obtained via Lemma I.4
In the following, we provide the proof for the Lemma 3.6 which plays key role in the above proof of the overall performance.
Proof of Lemma 3.6
holds that
V [s))) E Diipito [vár (s!))
E p
=EDwft [viuut (s') v&gil (s') + E E
(yinnl(ss)) E
((())((ss)
D
Meg 31
==(torn D)
:=ttemn II)
Denoting f(D Ene(m rh, we can obtain that
V. - (pfoo(('))
(a)
Vi (102) (s!) V ((s))(as)) (s!)
b
V ((Rs))( (st) - v Rg (6o) (100) (s2)
G
M
Σ
E
DOITH 33 (o( [S(D*)]
G
DiShWNe (ig))
|
hE[H]
Σ
Σ
Dihhiapl p0 (g pa. og )1 [F(D*1)
G
gE|G] AE[H]
e 2H
Σ
E
68 (Ggg) TV (ga x (A )s" (4(G0)).
D h
|
AE[H]
37

---

2H
G
Σ [E|C] he(M]
Σ
E
Dish
Iap ((02)
TV (-1o"), P3 (-1s))
Onn eugiigg (110%) )
@ 2H
G
Σ
Σ
E
D
(( p
TV
aniitaa (-1s²),
gE|G] hE(H)
iE|ml
sE(n]
( 2H
E
E
Dach Dach- A8 (100))
Σ EEIm
Onn TV (18""(110")) 12 (116"")))
TV
G
|E(G] he(m)]
2H
E ΣEE
On TV TV
(-as) (g)))
gE|C) hE[H] iE|m
2H
ΣE
TV (ua (1)) (1)6))
GE(G] NE(H] SES
where (a) is from the definition of best responses, (b) uses the notation ğ to denote the output policy from Alg. wiith the initial random sampling result to be g. (c) uses the variational representation of the TV distance, (d) uses the abbreviations n NN.h(s") and gi = (s*), (e) leverages the property of TV distance, and (f) uses the fact that On,i 1.
With the above result, we can further obtain that
(term I) == E D St
VV - -i (st) S E Duieten
2H Σ TV EVV (1d((1))
[E[T] $ES
Also, for term (II), denoting g(D) = V/ag.1 (s!), it holds that
Du [vRgai (st) - D Mle
(v (st)
(term II) := E
E Di A DUIIIN [o(D)] - Σ
De Luptle DITT Alea [g(D)
tE[T]
1E|T]
< 2H
E D Dua
TV (. s¹), Alga 1 ,)))]]
NE(T]
< 2H Σ
E
[TV (va(11D4) , 33), ,*))
TE(T] SES
+ 2H
Σ
E
[TV (va(1Dt') 3). 1/. 10- [
(E[T]
SES
Combining (term and (term II) concludes the proof.
I Discussions on the Covering Number
In the following, we characterize the covering number of algorithms induced by transformers parame- terized by 0 L.,L,M. FF, i..., {Alg, 0 L,, Here we will mainly take the perspective of the centralized setting, while the extension to the decentralized setting is straightforward.
To facilitate the discussion, we introduce the following clipped transformer, where an additional clip operator is adopted to bound the output of the transformer.
Definition I.1 (Clipped Decoder-basee Transformer). An T--ayer clipped decoder- based transformer, denoted as (-) is a composition of L masked attention layers, each followed by an MLP layer and a clip operation: (FR(H) = (LL) E RdxN, where H
(L) (L) is defined iteratively by taking
( clip, (H) E RdxN and I E [T.]
clip
MLP
(Aun 20
(H*- "
mip
where clipx((H) |projjhllass (h.)
[N]].
38

---

Furthermore, for E (0, 1|, we define the following Ç-biased algorithm induced by transformer TE (H)
as
ID' st () p (E TF, (n(D" ()))=)
AB 1AB.
with LAB denoting an all-one vector of dimension AB, which introduces a lower bound C/AB for probably each pair (a, b) E A to be sampled.
Finally, for any H -/ ,hv] Rd*,, we denote
2,00 = max hh:l22
se[N]
Proposition 1.2 (Modified from Proposition J.1 in Bai et al. have
77). For any 01, 02 E &d,.,M.d'.R we
[ R 8,
(H) TF H 1,,0 S LFL Fel 0 0211,
where Fe = FR FR + FR and FH == (1 F1) F²
Proof. This proposition can be obtained similarly Proposition J.1 in Bai al. 7 with the following Lemma L.3 in the place of Lemma J.1 in Bai et al.
Lemma L.3 (Modified from Lemma J.1 in Bai et al. 77. For a single MLP layer Omlp (W1, W2). we introduce its norm
0 Wi llop
2|
For any fixed hidden dimension D' we consider
Omlp.F == {0mlp 11mmpl S F}.
Then, for any H E Hn, mll mlp,, it holds that MLP (H) is 2F R-Liisschit in m and + Lipsscitt in H.
Proof. It holds that
[|LP Bulp
(H) MLPe (H)
max W20 - Wio(Wiho)le
< max W2 - lo |/ [k)) o (W(h,))
(0)
max
I Wallop max |W| + Wol W,h, Wihhlla
$ (1 FR) W2 Wollop + FR Will.
Inequality (a) is from that
|a(()]12 < ||1| ||a.(x)]|2 < 1,
and
||a((x) - (1))l2 < || vll2. [,. av(il122 S || - vll2.
where the last result the Lipschitzness of softmax is adopted from Gao and Pavel 25 Similarly, we can obtain that
MLPP Omm (H) - MLP (H') 112,00
max hh; + (1o(W,h, - h! Wig(W
H H' ||,000 W ol max (o o(Wsh()l
H H' 2,,00 + || ooo max max W2h
W
и H' 2,,0 + F2 H H' 1,,00
which concludes the proof.
39

---

Lemma 1.4 (Modified from Lemma 16 in Lin et al. [8]). For the space of transformers {TF) 0 E d, FF the covering number of the induced algorithms {Alge d, ,F) satisfies that log logNess..M.... (P) O (T,0011770000000 (Pd(Md+d')lo
(1+ (1+ max (,,
Sp
Proof. First, similar to Lemma 16 in Lin et al. to obtain that the 8-covering number of the ball (F) with radius F under norm
38 we can use Example 5.8 Wainwright [1]
i.e.,
B (F) = (0: |0| s F), can be bounded as
log (6; BII (F), ll- I1I S L(3Md + 2dd") log(1 2F/8).
Recall that the projection operation to probability simplex is Lipschitz continuous, i.e. |proja (æ) proja (3)1l2 I x y222-
Then, we can see that there exists a subset Ô C &. F with size
log 19..LM,,''Fl & L(3Md + 2dd") log(1 1 + 2F/6) such that for any d,L,,M, F, there exists 0 E θ with
110 :8) log Alg (. 11:10"1,00 s) - log Al -
AB
Alg ( . (D" Algo (
AB
|TR H) -TF (H) 2,00
AB
I.FL-11 Fe: 110 0
AB
I.FL-1 Foō.
Let 8
Cp
we can obtain
log Alg 8)) -))ggggg)) A1g solloo S which
ABLF
proves that
log(Ne (p))
< L(3Md + 2dd") log(1 + 2F/5)
ABLFH ABLFL-IFA Fe
L(3Md + 2dd") log 1+
Sp
[(33M + 2dd'd log
ABL(1 + (1R) FR F F
1+
Sp
- (f + dd') log
max Mox((A,B. (,
1
which concludes the proof.
From the transformer construction in the proofs for Theorems 3.4 and 4.1 we can observe that sufficient specify one R with log (R) Õ(1) without impacting the transformers' operations. is taken to be 1/N.
Also, in Theorems 3.3 and C.3
Finally, for the introduced Ç parameter, it can be recognized that the induced algorithms discussed in the main paper, i.e. Alge- can be interpreted as Ç = 0, which does not lead to a meaningful Log(Ne m...". (p)) provided in Lemma I.4 However, non-zero Ç can tackle this situation by only introducing an additional realization enror. Especially, assuming Assumption
can be achieved
with Ereal = 0, i.c., exactly realizing the context algorithm (as in Theorem we can obtain that
Aag. b(Di Algs (a, 11- 1,
log
E PAPANis
40

---

Algo (a, (a, 6( ,) Alg (a, ((.b
log
Dew
Algg. (a, b1 D 1)) Alg (a, D1
Al (a, b1 11111,11
log
E Du
(1 - () Alga- (a, by Dr 1 + (/B)
1
s log
(1 - () +C((BB)
$ log
With < O(1/N), additional realization error Eraal O(1/N) occurs, whose impact on the overall performance bound (i.e.. Theorems 3.5 and (42) is non-dominating. As a re- sult, for the parameterization provided in Theorem 4.1 covering number satisfies log(Ne) (polyyGG log(N)) can be obtained. Similarly, the results be extended to the decen- tralized setting, where for the parameterization provided in Theorem 3.4 holds that log(Ne,) = AL. log((N))
J Details of Experiments
J.1 Detail of Games
The normal-form games for the decentralized setting. The normal-form games (i.e., matrix games) used in decentralized experiments of Sec. have A = B 5 actions for both players and G 3000 episodes (i.e., horizon of T 3000 with H = 1), which can be interpreted as having state.
The Markov games for the centralized setting. The Markov games used in centralized exper- iments of Sec. 5 have A B actions for both players, S states, H = steps in each episode and G = 300 episodes (i.e., a horizon of T' = GH = 600). The transitions are fixed for different games: when both players take the same actions, the state transits to the next one (i.e., 1 + 2, + 1); otherwise, the state stays the same.
At the start of each game (during both training and inference), A x B reward matrix (s. is generated for each step h E [H] and state E S with its elements independently sampled from standard Gaussian distribution truncated [0, 1]. Then, the interactions proceed as follows: each time step h E [H]. the players select action a and i on state & based on their computed policy distributions. After selecting their actions, the players receive rewards (s, a, b) and RR a, b). respectively, while the state transits to the new one.
J.2 Collection of Pre-training Data
The EXP3 algorithm for the decentralized setting. In the decentralized setting, both players are equipped with the EXP3 algorithm [5] to collect pre-training data. Up to time step t. the trajectory of the max-player recorded "a1,T1," "t,T;"" ", and that of the min- min-player as "b,, Ti, b,, Tt"
The VI-ULCB algorithm for the centralized setting, In the centralized setting, both players jointly follow the VI-ULCB algorithm [8] collect pre- data. Up to time step f, the trajectory is recorded as "s1, a1, bi, TI, St, Oe, bt, Tt, rr.".
We note that the decimal digits of the rewards limited to facilitate tokenization, while 1 -- r3 instead of -rę is adopted for the min-player to avoid the additional complexity of negative numbers.
J.3 Transformer Structure and Training
The transformer architecture employed in our experiments is primarily based on the well-known GPT-2 model 43 and our implementation follows the miniGPT realization for simplicity. The
41

---

numbers of transformer layers and attention heads have been modified to make the entire transformer much smaller. In particular. we utilize a transformer with 2 layers and heads. Given that the transformer is used to compute the policy, we modify the output layer of the transformer to make it aligned with the action dimension. We focus solely on the last output from this layer to determine the action according to the computed transformer policy.
For the training procedure, use Nvidia 6000 Ada train the transformer with batch size of 32, trained for 100 epochs, and we set the learning rate as x 10-4. The experimental codes are available at
www coon/She@@roup/cGPPP
J.4 Performance Measurement
To test the performance of the pre-trained transformer (in particular, how well it approximates EXP3 and VI-ULCB), adopt the measurement of Nash equilibrium gap. In particular, for either the transformer induced policy or EXP3, we denote the max-player's s policy at time step as μ², and the min-player's policy time step v². Furthermore, the average policy is computed
Σ TET
Σ TELL
The NE gap at step is computed
max
RJ aEA
min (annnaa) (a")T R. BEB
For VI-ULCB, the process is similar except that p¹ and st are taken as the marginalized policies of the joint policy learned at step t while the NE gap is cumulated over one episode. The NE gaps averaged over 10 randomly realized games each step are plotted in Fig.
42

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
This work investigates the in-context game- game-playing (ICGP) capabilities of pre- trained transformers, where both the decentralized and centralized settings are considered. The abstract and introduction (i.e., Sec. [ accurately reflect the considered problem and the obtained main results, highlighting our contributions in providing a comprehensive understanding of ICGP.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The major limitations of this work in our mind are illustrated in Appendix B.2 In particular, it emphasized that this work mainly focuses on the two-player zero-sum Markov games and two specific game-solving algorithms. Also, the construction of the pre-trained dataset and the need of further large-scale experiments are discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
43

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The main paper (particularly, Sec. 3.1.] and the beginning of Sec. 4.1 provides the main setups and assumptions considered in this work. Additional Assumptions
and G.2 are deferred to the appendix due the page limits while being noted in the main paper with corresponding pointers. The complete proofs are provided in the appendix (see Appendix A for an overview), which have been carefully checked multiple times and are correct to the best of our knowledge. A proof sketch is included in Sec. 4.3 to facilitate the readers' understanding.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: A detailed description of the experimental setups and details is provided in Appendix J The complete set of codes for the experiments are available at https
//github. com wtt.auu..coom/eenoooo////oo/// ShenGroup/ICGP
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
44

---

(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The complete set of codes can be found https://githinn com/
PMenCroup/ICGP
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwtppbliccgguueeeeeeeeeeeepeeeee hww.liiccuuddss/ddddbbbiissssss SoboeeSubiissioPolle
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: A detailed deseription of the experimental setups and details is provided in Appendix D The experimental codes are available at httttss://githi com/ ShenCroup/
ICGP]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
45

---

Answer: [Yes]
Justification: Error bars have been provided in Fig. 2 which is the main experimental results in this work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2- 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етгог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computer resources used to perform the experiments reported this work are described in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 'tdn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http::///hnanrescccpppppccccccct
Answer: [Yes]
Justification: All the authors have reviewed the NeurlPS Code of Ethics and practiced during this submission.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
46

---

10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Discussions on the broader impacts of this work are provided in Appendix B.I Due to the theoretical focus of this work, we do not foresee major negative social impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The transformers trained in this work are only for the purpose of validating the theoretical claims, which we do not foresee risks of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
47

---

Justification:
We have included the URL of the adopted transformer model in Appendix J which under standard MIT license.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com /daaaset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets have been released with this work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: No crowdsourcing and research with human subjects has been performed during this work.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
48

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing and research with human subjects has been performed during this work.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "hieX0LTYtT", "reviewer": "Reviewer_h1zf", "summary": "The paper proposes a framework for pre-trained transformers to approximate Nash equilibrium in two-player zero-sum normal-form games and provides theoretical guarantees to show that these pre-trained transformers can learn to approximate Nash equilibrium in an in-context manner. This is shown for both the decentralized and centralized learning settings. The decentralized case follows the idea that each agent will have it's own model, and uses V-learning. The centralized case uses a centralized joint model to control both players, and uses VI-ULCB. The paper shows that there is a provable upper bound to the approximation error of the Nash equilibrium which demonstrates the in-context game player capability of transformers. Further more, empirical results show that given a sufficiently well pre-trained transformer that it can approximate Nash equilibrium in an in context manner, similar to that of decentralized EXP3 in two-player zero-sum normal-form games, that is it has a similar profile of the gradually decaying Nash equilibrium gap.", "questions": "1) Do you believe that this implementation might have different results given a different pre-training dataset (produced from a different algorithm)?\n\n2) 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?", "limitations": "The authors have identified the limitations and have stated that there should be no negative societal impact due to the theoretical nature of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\nThis work offers new insights into the the theoretical analyses and empirical evidence for the in context game player capabilities of transformers.\n\nClarity and Quality:\nThe paper is well cited and explains the concepts it is conveying quite well, with the appendix showing the details of the proofs and supporting code demonstrating the reproducibility of the empirical work.\n\nSignificance:\nThe paper shows the theoretical capabilities of transformers adapted to V-learning (and thus aiding in the scalability of MARL) as well as approximating Nash equilibrium are important to MARL settings.", "weaknesses": "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n>**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.\n\n>**Question 1:** Do you believe that this implementation might have different results given a different pre-training dataset (produced from a different algorithm)?\n\n**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.\n\n- 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.\n\n- 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. \n\n  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.\n\n  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. \n  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).\n\n[R1] Laskin, M., Wang, L., et al. (2022). In-context reinforcement learning with algorithm distillation.\n\n---\n\n> **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.}\n\n>**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?}\n\n**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.\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yVaOObJYQT", "reviewer": "Reviewer_kZH2", "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.\n\nThe 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).\n\nThe 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", "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?\n* 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.\n* 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?\n\nJust out of curiosity:\n* 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)?", "limitations": "Yes.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. **Soundness of the Claims**\n\n   a) **Theoretical Grounding**\n\n   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.\n\n   b) **Empirical Evaluation**\n\n   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.\n\n   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.\n\n2. **Significance**\n\n   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.\n\n3. **Novelty**\n\n   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**\n\n   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.\n\n   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. \n\n   a) **Theoretical grounding**\n\n      a1) **Decentralized learning scenario**\n\n   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.\n\n* (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.\n* (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.\n* (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\n* (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.\n\n   a2) **Centralized learning scenario**\n\n   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\n\n* (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.\n* (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...\n* (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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this paper! The following responses are provided with the reviews compressed due to the length limit.\n\n---\n>**W1.** (Lines 157-170) If the data collected ... a limited range of strategic interactions ... might lack the necessary diversity ...\n\n>**Q1.** Given ... the diversity and distributional properties of the training data do not adversely ...\n\n**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$. \n\nAlso, 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.\n\n---\n\n>**W2.** (Lines 200-202) Take into account ... This assumption may not hold ...\n\n**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,+}$.\n\nThrough 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.\n\nTheorem 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.\n\n---\n\n> **W3.** (Lines 195-190) Potential convergence/generalization problems ... if the covering number $\\Theta$ is underestimated ...\n\n>**Q2.** The clipping operation $\\text{clip}_R$ ... affect the learning dynamics ...\n\n**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.\n\nThe 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.\n\n---\n\n>**W4.** (Lines 182-185) The use of linear extraction mappings followed by a projection to the probability simplex ... not suitable ...\n\n**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.\n\n---\n\n>**W5.** (Lines 307-309) The required dimensions ... indicate a high computational complexity and dependency on specific game parameters ...\n\n**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.\n\n---\n>**W6.** (Lines 307-309) This performance requirement ... assumes an ideal alignment ...  any deviation ...\n\n**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.\n\nThe 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.\n\n---\n>**W7.** (Lines 321-322) Note that the assumption ... uniformly sampled ... might not hold ...\n\n**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.\n\n---\n>**Q3.** In Appendix G.3, ... embedding and extraction mappings ... specific state spaces where these mappings prove particularly beneficial/limited?\n\n**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.\n\n---\n>**Q4.** Have you observed any sudden shifts ... based on ...\n\n**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.\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6aIrC7LqEr", "reviewer": "Reviewer_beky", "summary": "This paper explores the in-context learning capabilities of pre-trained transformer models in two-player zero-sum games. The authors provide the theoretical guarantees that pre-trained transformers can learn the approximate Nash equilibrium in an in-context manner, both in decentralized and centralized settings.", "questions": "See Weaknesses.", "limitations": "The authors have discussed the limitations and future directions of the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Considering multi-agent settings (two-player zero-sum games in this work) is well-motivated compared to previous works that focused on single-agent settings.\n\n2. The theoretical results in this work provide a deeper understanding of how the pre-trained transformers can approximate NE in an in-context manner.\n\n3. The paper is well-written, easy to follow, and makes non-trivial contributions to the relevant communities. However, because I am not an expert in theory, so it is quite difficult for me to check all the details of the proofs of all the theoretical results. Therefore, I am positive for acceptance but with relatively low confidence.", "weaknesses": "There are some questions:\n\n1. 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?\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n>**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?\n\n**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.\n\n---\n>**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.\n\n**Response 2.** We would like to provide the following discussions on the augmented component.\n\n- 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.\n\n- 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.\n\n  - 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.\n\n[R1] Cui, Q., and Du, S. S. (2022). When are offline two-player zero-sum Markov games solvable?.\n\n[R2] Zhong, H., Xiong, W., et al. (2022). Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets.\n\n\n---\n>**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.\n\n**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.\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BflEay9t1T", "reviewer": "Reviewer_yLUv", "summary": "This paper investigates the in-context learning capabilities of pre-trained transformer models in competitive multi-agent games, i.e., in-context game-playing (ICGP). The authors provide extensive theoretical guarantees to validate that pre-trained transformers can approximate NE in an in-context manner for both decentralized and centralized learning settings. They also demonstrate that the transformer architecture can realize well-known multi-agent game-playing algorithms. Finally, experimental results support their theoretical findings, showing that transformers can effectively approximate NE in an in-context manner.", "questions": "1. The empirical experiments are currently limited to simple two-player zero-sum normal-form games. Have you considered testing your methods in more complex environments, such as multi-player games or games with larger state-action spaces? If so, what were the results, and if not, why?\n\n2. This paper focuses on two-player zero-sum Markov games. Could your method be applied to other types of games, such as cooperative or general-sum games? Do you have any insights or challenges you anticipate in these games?\n\n3. Could you discuss more about the broader impacts and potential limitations of your work?", "limitations": "Yes, the authors provide limitations in the Appendix.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strengths of this paper are:\n\n1. The paper focuses on a novel and important aspect of in-context learning in competitive multi-agent settings. Specifically, they introduce a framework for modeling ICGP via transformers. \n\n2. This paper provides strong theoretical guarantees and backs them with empirical validation.\n\n3. The methodology is sound, and the paper is well-structured, with clear explanations and thorough analyses.", "weaknesses": "1. The paper seems to be an extended work that generalizes the analysis of in-context learning in RL to the analysis of in-context learning in game theory. Certainly, this setting has not been explored before. However, this paper did not explain why this research problem is important. \n\n2. Although the paper provides strong theoretical results, the empirical experiments are conducted on relatively simple two-player zero-sum normal-form games. This limits the generalizability of the findings.\n\n3. The paper lacks a more detailed discussion of the practical implications.  Including such a discussion would provide a more comprehensive understanding of the applicability of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n>**Weakness 1.** The paper ... the analysis of in-context learning in game theory ... why this research problem is important.\n\n**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.\n\n\n---\n>**Weakness 2.** ... the empirical experiments are conducted on relatively simple two-player zero-sum normal-form games ...\n\n>**Question 1.** The empirical experiments are currently limited to simple two-player zero-sum normal-form games ...\n\n**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.\n\n---\n\n>**Weakness 3.** The paper lacks a more detailed discussion of the practical implications ...\n\n**Response 3.** We will incorporate additional discussions on the practical implications in the revised paper. Here we briefly discuss the following aspects. \n\n- 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. \n\n- Moreover, our current theoretical results have the following useful implications for practical considerations.\n\n   - 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.\n\n   - 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.).\n\n  - 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.\n\n---\n\n>**Question 2.** ... Could your method be applied to other types of games, such as cooperative or general-sum games ... \n\n**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. \n\nIt 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.\n\n---\n\n>**Question 3.** ... more about the broader impacts and potential limitations ...\n\n**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.\n\n- [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.\n\n- [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.\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We would like to express our gratitude for all your time and effort in reviewing this work. Point-by-point responses have been provided, which hopefully can address the raised questions and comments. It would be our pleasure to engage in further discussions and incorporate any suggestions that you may have.

Along with this response, one PDF is uploaded, containing additional experimental results on the in-context game-playing capabilities of pre-trained transformers in a more complex environment (with state transitions). These results will be added to the revised paper. We believe they provide further evidences of the obtained theoretical and empirical results.

Our appreciations again!

Best regards,
Authors of Submission 13525

Meta-review: This paper extends our theoretical understanding of transformers’ in-context learning results from single agent to two-player, zero-sum settings. In particular, it establishes precise bounds on the sizes of the transformer architectures needed to represent two convergent, no-regret game playing algorithms: decentralized V-learning and centralized VI-ULCB. The paper can be improved by adding:

*References to background literature and context for readers*:
- In-context game playing has been previously explored empirically in complex settings, for example, extensive-form [1].
- Transformers have been proven to be universal function approximators of sequence-to-sequence mappings [2]. Applying this to the game setting here, it is expected that transformers can map action histories to distributions over next actions given enough training data and a large enough network.

*More Extensive Experiments on Markov Games*:
- The authors initially included only results averaged over 10 randomly generated zero-sum, bi-matrix games, providing additional results on randomly generated Markov games in the rebuttal which was appreciated. Given the setting of the theoretical results, it would be beneficial to see 1) additional experiments on Markov games with longer horizons, 2) more trials, and 3) a normalized NE-gap to account for randomly generated games with small payoff ranges. If longer horizons (1) are not practically possible, please discuss this as a limitation in the paper.

The general consensus among the reviewers is that the generalization from single agent to two player zero sum games is a non-trivial task, especially in the decentralized version, therefore, we recommend accepting this paper.

- [1] Gandhi, Kanishk, Dorsa Sadigh, and Noah Goodman. "Strategic Reasoning with Language Models." NeurIPS 2023 Foundation Models for Decision Making Workshop. https://arxiv.org/pdf/2305.19165
- [2] Yun, Chulhee, et al. "Are Transformers universal approximators of sequence-to-sequence functions?." International Conference on Learning Representations. https://arxiv.org/abs/1912.10077
Decision: Accept (poster)