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_cc_2024_Conference
Published: 2024-05-15 04:33:02

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.

Main paper: 
 introduction: 
 Since proposed in Vaswani et al. [57] , the transformer architecture has received significant interest. It has powered many recent breakthroughs in artificial intelligence [11, 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 is 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. [11] , Chowdhery et al. [15] , Liu et al. [39] .ICL is practically attractive as it provides strong generalization capabilities across different downstream 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, 59] ; 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. [7] , Cheng et al. [14] , Li et al. [37] , Raventós et al. [44] , Wu et al. [64] , Xie et al. [66] , Zhang et al. [71] . Among these empirical and theoretical studies, one emerging direction focuses on the capability of pretrained transformer models to perform in-context reinforcement learning (ICRL) [28, 34, 35, 50, 73] . In particular, the transformer is pre-trained with interaction data from diverse environments, modeling the interaction as a sequential prediction task. During inference, the pre-trained transformer is prompted via the interaction trajectory in the current environment for it to select actions. The work by Lin et al. [38] provides some theoretical understanding of ICRL, including both a general pretraining guarantee and specific constructions of transformers to realize some well-known designs in multi-armed bandits and RL (especially, LinUCB [1] , 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., a 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-player competitive games such as GO [49] , Starcraft [58] , and Dota 2 [10] . To provide a more comprehensive understanding of ICRL, this work targets further studying the in-context game-playing (ICGP) capabilities of transformers in multi-agent competitive settings. To the best of our knowledge, this is 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-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 to its game-theoretic nature.• The challenging decentralized learning setting is first studied, where two distinct transformers are trained to learn NE, one for each player, without observing the opponent's actions. A general realizability-conditioned guarantee is first derived that characterizes the generalization error of the pre-trained transformers. Then, the capability of the transformer architecture is demonstrated by providing a concrete construction so that the famous V-learning algorithm [8] can be exactly realized. Lastly, a finite-sample upper bound on the approximation error of NE is proved to 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 [6] as studied in Lin et al. [38] ).• To obtain a 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, a constructional result to demonstrate realizability, and a finite-sample upper bound on the approximation error of NE. Distinctly, the transformer construction is presented as a specific parameterization to implement the renowned centralized VI-ULCB algorithm [8] .• Furthermore, experiments are also performed to practically test the ICGP capabilities of the pretrained 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 game-theoretic settings.We consider each episode of observations to be embedded in 2H tokens. In particular, for each t ∈ [T ], we construct thath 2t-1 = h(s g,h ) =          0 A 0 B 0 s g,h 0 AB 0 pos 2t-1          =:     h pre,a 2t-1 h pre,b 2t-1 h pre,c 2t-1 h pre,d 2t-1     , h 2t = h(a g,h , b g,h , r g,h ) =          a g,h b g,h r g,h 0 S 0 AB 0 pos 2t          =:     h pre,a 2t h pre,b 2t h pre,c 2t h pre,d 2t     ,where s g,h , a g,h , b g,h are represented via one-hot embedding. The positional embedding pos i is defined aspos i :=           g h t e h v i i i 2 1          , where e h is a one-hot vector with the h-th element being 1 and v i := 1{h a i = 0} denote the tokens that do not embed actions and rewards.In summary, for observations D t-1 ∪ {s t }, we obtain the following tokens of length 2t -1:H := h(D t-1 , s t ) = [h 1 , h 2 , • • • , h 2t-1 ] = [h(s 1 ), h(a 1 , b 1 , r 1 ), • • • , h(s t )].With the above input H, the transformer outputs H = TF θ+ (H) of the same size as H. The extraction mapping E is directly set to satisfy the followingE • h -1 = E • h 2t-1 = h c 2t-1 ∈ R AB , i.e., the part c of the output tokens is used to store the learned policy. 
a theoretical framework for in-context game playing 2.1 the basic setup of environments: 
 To demonstrate the ICGP capability of transformers, we focus on one of the most basic gametheoretic 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.e., decentralized and centralized) considered in this work (with details explained later) is given in Fig. 1 . The overall framework is introduced in the following, which extends Lin et al. [38] from the single-agent decision-making setting to the competitive multi-agent domain.Considering a set of two-player zero-sum Markov games denoted as M. Each environment M ∈ M shares the number of episodes G, the number of steps H in each episode, the state space S (with |S| = S), the action spaces {A, B} (with |A| = A and |B| = B), and the reward space R. Here A and B denote the action spaces of two players, respectively, which are referred to as the max-player and the min-player for convenience. ) is taken upon state s g,h at step h in episode g, the state is transited to s g,h+1 ∼ T h M (•|s g,h , a g,h , b g,h ), and reward r g,h ∼ R h M (s g,h , a g,h , b g,h ) (respectively, -r g,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 r ∈ [0, 1] such that R g,h M (r|s, a, b) = 1. Also, the initial state s g,1 is assumed to be a fixed one s 1 , i.e., T 0 M (s 1 ) = 1. We further leverage the notation T := GH, while using time t and episode-step pair (g, h) in an interleaving manner with t := (g -1)H + h. The partial interaction trajectory up to time t is then denoted as D t := {(s τ , a τ , b τ , r τ ) : τ ∈ [t]) and we use the abbreviated notation D := D T . Individually, for the max-player, we denote her observed interaction trajectory up to time t by D t + := {(s τ , a τ , r τ ) : τ ∈ [t]) and write D + := D T + for short. Similarly, for the min-player, we denote D t -:= {(s τ , b τ , r τ ) : τ ∈ [t]) and D -:= D T -.A game-playing algorithm Alg can map a partial trajectory D t-1 and state s t to a distribution over the actions, i.e., Alg(•, •|D t-1 , s t ) ∈ ∆(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 + (•|D t-1 + , s t ) ∈ ∆(A) and Alg -(•|D t-1 -, s t ) ∈ ∆(B). Given an environment M and an algorithm Alg, the distribution over a full trajectory D can be expressed asP Alg M (D) = t∈[T ] T t-1 M (s t |s t-1 , a t-1 , b t-1 ) • Alg(a t , b t |D t-1 , s t ) • R t M (r t ).If further considering an environment prior distribution Λ ∈ ∆(M) such that M ∼ Λ, the joint distribution of (M, D) is denoted as P Alg Λ (D), where M ∼ Λ(•) and D ∼ P Alg M (•). For environment M and a game-playing algorithm π, we define its value function over one episode asV π M (s 1 ) = E D H ∼P π M [ t∈[H] r t ].With the marginalized policies of π denoted as (µ, ν), we define their best responses asν † (µ) := arg min ν ′ V µ,ν ′ M (s 1 ), µ † (ν) := arg max µ ′ V µ ′ ,ν M (s 1 ), whose corresponding values are V µ, † M (s 1 ) := V µ,ν † (µ) M (s 1 ), V †,ν M (s 1 ) := V µ † (ν),ν M (s 1 ).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). A decoupled policy pair (μ, ν) is an ε-approximate Nash equilibrium for environmentM if V μ, † M (s 1 ) + ε ≥ V μ,ν M (s 1 ) ≥ V †,ν M (s 1 ) -ε, i.e., the Nash equilibrium gap V †,ν M (s 1 ) -V μ, † M (s 1 ) ≤ 2ε.For each environment, our learning goal is to approximate its NE policy pair. In other words, we target outputting a policy pair (μ, ν) that is ε-approximate NE with an error ε that is as small as possible, after interacting with the environment for an overall T rounds.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 inputs. First, for an input vector x ∈ R d , we denote σ r (x) := ReLU(x) := max{x, 0} ∈ R d as the entry-wise ReLU activation function and σ s (x) := softmax(x) ∈ R d as the softmax activation function, while using σ(•) to refer to a non-specified activation function (i.e., both ReLU and softmax may be used). Then, the masked attention layer and the MLP layer can be defined as follows. Definition 2.2 (Masked Attention Layer). A masked attention layer with M heads is denoted asAttn θ (•) with parameters θ = {(V m , Q m , K m )} m∈[M ] ⊂ R d×d . On any input sequence H = [h 1 , • • • , h N ] ∈ R d×N , we have H = Attn θ (H) = [h 1 , • • • , h N ] ∈ R d×N, whereh i = h i + m∈[M ] 1 i j∈[i] σ r (⟨Q m h i , K m h j ⟩) • V m h j .). An MLP layer with hidden dimension d ′ is denoted asMLP θ with parameters θ = (W 1 , W 2 ) ∈ R d ′ ×d × R d×d ′ . On any input sequence H = [h 1 , • • • , h N ] ∈ R d×N , we have H = MLP θ (H) = [h 1 , • • • , h N ] ∈ R d×N, whereh i = h i + W 2 • σ(W 1 • h i ).The combination of masked attention layers and MLP layers leads to the overall decoder-based transformer architecture studied in this work, as defined in the following. Definition 2.4 (Decoder-based Transformer). An L-layer decoder-based transformer, denoted as TF θ (•), is a composition of L masked attention layers, each followed by an MLP layer and a clip operation:TF θ (H) = H (L) ∈ R d×N, where H (L) is defined iteratively by taking H (0) = H ∈ R d×N and for l ∈ [L],H (l) = MLP θ (l) mlp Attn θ (l) mattn H (l-1) ∈ R d×N ,where parameter θ = {(θ(l) mattn , θ (l) mlp ) : l ∈ [L]} consists of θ (l) mattn = {(V (l) m , Q (l) m , K (l) m ) : m ∈ [M ]} ⊂ R d×d and θ (l) mlp = (W (l) 1 , W (l) 2 ) ∈ R d ′ ×d × R d×d ′ .We further define the parameter class of transformers as Θ d,L,M,d ′ ,F := {θ = (θ(1:L) mattn , θ (1:L) mlp ) : ∥θ∥ ≤ F },where the norm of a transformer TF θ is denoted as∥θ∥ := max l∈[L] max m∈[M ] ∥Q (l) m ∥ op , ∥K (l) m ∥ op + m∈[M ] ∥V (l) m ∥ op + ∥W (l) 1 ∥ op + ∥W (l) 2 ∥ op .Other Notations. The total variation distance between two algorithms {π,π ′ } upon D t-1 ∪ {s} is denoted as TV(π, π ′ |D t-1 , s) := TV(π(•|D t-1 , s), π ′ (•|D t-1 , s)). Also, the notation x ≲ y indicates that x is a lower or equivalent order term compared with y, i.e., x = O(y), Õ(•) hides poly-logarithmic terms in H, G, S, A, B, and poly(•) compactly denotes a polynomial term with respect to the input. 
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 [32, 41, 51] . In the following, we start by introducing the basic setup of supervised pre-training and provide a general performance guarantee relying on a realizability assumption. Then, we provide a constructional result 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.Training Dataset. In the supervised pre-training, we use a context algorithm Alg 0 to collect the offline trajectories. For the decentralized setting, the context algorithm Alg 0 used for data collection is assumed to be consisted of two decoupled algorithms (Alg +,0 , Alg -,0 ) for the max-and min-players, respectively. With the context algorithm, we consider N i.i.d. offline trajectories{D i : i ∈ [N ]} are collected, where D i := D i ∪ D ′ i with D i := {(s t i , a t i , b t i , r t i ) : t ∈ [T ]} ∼ P Alg 0 Λ (•); D ′ i := {(a t i,s , b t i,s ) ∼ Alg 0 (•, •|D t-1 i , s) : t ∈ [T ], s ∈ S}.It can be observed that D i is the commonly considered offline interaction trajectory of Alg 0 , while D ′ i is the sampled actions of each state s at each step t with Alg 0 . Compared with Lin et al. [38] , D ′ i is an augmented component. We first note that collecting D ′ i is relatively easy in practical applications, as it only needs to additionally sample from the distribution Alg 0 (•, •|D t-1 i , s) for each s ∈ 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 3.6. It has also been recognized previously [16, 72] 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 +,i : i ∈ [N ]} and {D -,i : i ∈ [N ]}, where D +,i := D +,i ∪ D ′ +,i , D +,i := {(s t i , a t i , r t i ) : t ∈ [T ]}, D ′ +,i := {a t i,s : t ∈ [T ], s ∈ S}; D -,i := D -,i ∪ D ′ -,i , D -,i := {(s t i , b t i , r t i ) : t ∈ [T ]}, D ′ -,i := {b t i,s : t ∈ [T ], s ∈ S}. In other words, D i,+ denotes the observations of the max-player, while D i,-those of the min-layer. Note that neither player can observe the opponent's actions.Algorithm Induced by Transformers. Due to the decentralized nature, two embedding mappings of d + and d -dimensions are considered as h + : S ∪ (A × R) → R d+ and h -: S ∪ (B × R) → R d-, together with two transformers TF θ+ and TF θ-. Taking the max-player's transformer as representative, for trajectory(D t-1 + , s t ), let H + = h + (D t-1 + , s t ) = [h + (s 1 ), h + (a 1 , r 1 ), • • • , h + (s t )]be the input to TF θ+ , and the obtained output isH + = TF θ+ (H + ) = [h +,1 , h +,2 , • • • , h +,-2 , h +,-1 ],which has the same shape as H + . Similarly, the mapping h -is used for the min-player's transformer TF θ-to embed trajectory (D t-1 -, s t ). We further assume that two fixed linear extraction mappings, A ∈ R A×d+ and B ∈ R B×d-, are used to induce algorithms Alg θ+ and Alg θ-over the action spaces A and B of the max-and min-players, respectively, asEQUATIONwhere proj ∆ denotes the projection to a probability simplex.Training Scheme. We consider the standard supervised pre-training to maximize the log-likelihood of observing training datasets D + (resp., D -) over algorithms {Alg θ+ : θ + ∈ Θ + } (resp., {Alg θ-:θ -∈ Θ -}) with Θ + := Θ d+,L+,M+,d ′ + ,F+ (resp., Θ -:= Θ d-,L-,M-,d ′ -,F-).In particular, the pre-training outputs θ + and θ -are determined asθ + = arg max θ+∈Θ+ 1 N i∈[N ] t∈[T ] s∈S log Alg θ+ (a t i,s |D t-1 +,i , s) ; θ -= arg max θ-∈Θ- 1 N i∈[N ] t∈[T ] s∈S log Alg θ-(b t i,s |D t-1 -,i , s) .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] . ≤ ε +,real .We also similarly assume ε -,real -approximate realizability of Alg -,0 via Alg θ * -with θ * -∈ Θ -.Then, we can establish the following generalization guarantee on the TV distance between (Alg θ+ , Alg θ-) and Alg 0 = (Alg 0,+ , Alg 0,-), capturing their similarities. 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., P Alg 0 Λ (D), the TV distance between the pre-trained algorithm Alg θ+ (resp, Alg θ-) and the context algorithm Alg +,0 (resp, Alg -,0 ) can be bounded via two terms: one from the approximate realizability, i.e., ε +,real (resp, ε -,real ), and the other from the limited amount of pre-training trajectories, i.e., finite N . While we can diminish the second term via a large pre-training dataset (i.e., sufficient pre-training games), the key question is whether the transformer structure is sufficiently expressive to realize the context algorithm, i.e., having a small ε +,real , which we affirmatively answer via an example of realizing V-learning [32] in the next subsection.To demonstrate the capability of transformers in the decentralized game-playing setting, we choose to 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, we demonstrate that a transformer can be constructed to exactly perform V-learning with a suitable parameterization. One additional Assumption G.2 on the existence of a transformer parameterized by the class of Θ d,L D ,M D ,d D ,F D to perform exact division is adopted for the convenience of the proof, while in Appendix G.2, we further demonstrate that the required division operation can be approximated to any arbitrary precision. Theorem 3.4. With embedding mapping h + and extraction mapping A defined in Appendix G.3, under Assumption G.2, there exists a transformer TF θ+ withd ≲HSA, L ≲ GHL D , max l∈[L] M (l) ≲ HS 2 + HSA + M D , d ′ ≲ G + A + d D , ∥θ∥ ≲ GH 2 S + G 3 + F D , which satisfies that for all D t-1 + , s ∈ S, t ∈ [T ], Alg θ+ (•|D t-1 + , s) = Alg V-learning (•|D t-1 + , s).A similar construction TF θ-exists for the min-player's transformer such that for allD t-1 -, s ∈ S, t ∈ [T ], Alg θ-(•|D t-1 -, s) = Alg V-learning (•|D t-1 -, s).The proof of Theorem 3.4 (presented in Appendix G.3) is challenging because V-learning is a modelfree design, while UCB-VI [6] studied in Lin et al. [38] 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-making, 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.e., the value computation at each step is directly over all raw inputs in previous steps. Thus, the construction procedure is straightforward as (input 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 Θ + and Θ -be the classes of transformers satisfying the requirements in Theorem 3.4 and (Alg +,0 , Alg -,0 ) both be V-learning. Let (μ, ν) be the output policies via the output rule of V-learning. Denoting Alg θ = (Alg θ+ , Alg θ-) and N Θ = N Θ+ N Θ-. Then, with probability at least 1 -δ, it holds thatE D∼P Alg θ Λ V †,ν M (s 1 ) -V μ, † M (s 1 ) ≲ H 5 S(A ∨ B) log(SABT ) G + T HS log (T SN Θ /δ) N .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 are 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 actions, which reflects the decentralized requirement. Moreover, the approximation error in Theorem 3.5 depends on A ∨ B instead of AB as in the later Theorem 4.2, evidencing the benefits of decentralized learning.Proof Sketch. The proof of Theorem 3. , respectively:EQUATION+ E θ V †,ν M (s 1 ) -E 0 V †,ν M (s 1 ) + E 0 V μ, † M (s 1 ) -E θ V μ, † M (s 1 ), . It can be observed that the first decomposed term is the performance of the considered V-learning, which can be obtained following Jin et al. [32] as in Theorem G.1.Then, the remaining terms concern the performance of the policy pair (μ, ν) learned from Alg 0 and Alg θ 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.,E 0 V μ,ν M (s 1 ) -E θ V μ,ν M (s 1 ) .The involvement of best responses complicates the analysis. After careful treatments in Appendix H, we obtain the following lemma to characterize these terms. Lemma 3.6. For any two decentralized algorithms Alg α and Alg β , we denote their performed policies for episode g are (µ g α , ν g α ) and (µ g β , ν g β ), and their final output policies via the output rule of V-learning (see Appendix G.1) are (μ α , να ) and (μ β , νβ ). For {μ α , μβ }, it holds thatE α V μα, † M (s 1 ) -E β V μβ , † M (s 1 ) ≲H • t∈[T ],s∈S E α TV µ t α , µ t β |D t-1 + , s +H • t∈[T ],s∈S E α TV ν t α , ν t β |D t-1 -, s ,whereE α [•] and E β [•] are with respect to P Alg α Λ and P Alg β Λ. A similar result holds for {ν α , νβ }.With Lemma 3.6, we can incorporate Theorem 3.3 to upper bound the TV distance between Alg 0 and Alg θ , which together with Theorem 3.4 establish ε real,+ = ε real,-= 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 3.6 over all s ∈ S credits to the augmented dataset D ′ , which provides diverse data of all s ∈ S. 
centralized learning: 
 In this section, we discuss the scenario of centralized learning, i.e., training one joint model to control both players' interactions. This is also known as the self-play setting [8, 9, 33, 40, 67] . Following a similar procedure as the decentralized discussions, we first provide supervised pre-training guarantees and then demonstrate that transformers are capable of realizing the renowned VI-ULCB algorithm [8] . It is thus established that in a centralized learning setting, the pre-trained transformer can still effectively perform ICGP and approximate NE.The same training dataset {D i : i ∈ [N ]} as 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 ∪ (A × B × R) → R d can be designed to embed the trajectories, and the induced algorithm Alg θ (•, •|D t , s t ) from the transformer TF θ can be obtained via a fixed linear extraction mapping E similarly as Eqn. (1) . Finally, the MLE training is performed withΘ := Θ d,L,M,d ′ ,F as θ = arg max θ∈Θ 1 N i∈[N ] t∈[T ] s∈S log Alg θ (a t i,s , b t i,s |D t-1 i , s) .Then, a generalization guarantee of Alg θ can be 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 pre-training data.The VI-ULCB algorithm [8] 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, we choose it 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 a transformer TF θ withd ≲ HS 2 AB, L ≲ GHS, max l∈[L] M (l) ≲ HS 2 AB, d ′ ≲ G 2 HS 2 AB, ∥θ∥ ≲ HS 2 AB + G 3 + GH, which satisfies that for all D t-1 , s ∈ S, t ∈ [T ], Alg θ (•, •|D t-1 , s) = Alg VI-ULCB (•, •|D t-1 , s).One observation from the proof of Theorem 4.1 (presented in Appendix D.2) is that transformer layers can perform MWU so that an approximate CCE can be found, which is 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).With Theorem 4.1 showing VI-ULCB can be exactly realized (i.e., ε real = 0 in Assumption C.2), we can further prove an overall upper bound of the approximation error of NE by Alg θ via the following theorem, demonstrating the ICGP capability of transformers. Theorem 4.2. Let Θ be the class of transformers satisfying the requirements in Theorem 4.1 and Alg 0 be VI-ULCB. For all (g, h, s)∈ [G] × [H] × S, let (µ g,h (•|s), ν g,h (•|s)) be the marginalized policies of Alg θ (•, •|D t-1 , s).Then, with probability at least 1 -δ, it holds thatE P Alg θ Λ ,μ,ν V †,ν M (s 1 ) -V μ, † M (s 1 ) ≲ H 4 S 2 AB log(SABT ) G + T HS log(T SN Θ )/δ) N ,where μ and ν are uniformly sampled asμ ∼ Unif{µ 1 , • • • , µ G } and ν ∼ Unif{ν 1 , • • • , ν G }, with µ g := {µ g,h (•|s) : (h, s) ∈ [H] × S} and ν g := {ν g,h (•|s) : (h, s) ∈ [H] × S}, and E μ,ν is with respect to the process of policy sampling.This result demonstrates the ICGP capability of pre-trained transformers in the centralized setting, complementing the discussions in the decentralized results. 
empirical experiments: 
 Experiments are performed on two-player zero-sum normal-form games (H = 1) and Markov games (H = 2), with the decentralized EXP3 [5] (which can be viewed as a 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 J. It can be first observed from Fig. 2 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 1/N -dependencies 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.e., having a 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-trained transformers, motivating and validating the theoretical analyses performed in this work. 
related works: 
 In-context Learning. Since GPT-3 [11] demonstrates the ICL capability of pre-trained transformers, growing attention has been paid to this direction. In particular, an emerging line of work targets providing a deeper understanding of the fundamental mechanism behind the ICL capability [3, 24, 29, 31, 37, 44, 59, 60, 64, 66, 68] , where many interesting results have been obtained. In particular, transformers have been shown to be capable of performing in-context gradient descent so that varying optimization-based algorithms can be realized [2, 3, 7, 26, 59] . Also, Giannou et al. [27] demonstrates that looped transformers can emulate basic computing blocks, whose combinations can lead to complex operations.This work is more focused on the in-context reinforcement learning (ICRL) capability of pre-trained transformers, as demonstrated in Grigsby et al. [28] , Laskin et al. [34] , Lee et al. [35] , Wang et al. [62] .The recent work by Lin et al. [38] initiates the theoretical investigation of this topic. In particular, Lin et 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, LinUCB [1] , Thompson sampling [54] , UCB-VI [6] ). This work extends Lin et al. [38] to the domain of competitive multi-agent RL by studying the in-context game-playing setting. A recent concurrent work [36] also touches upon the in-context game-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 [10, 47, 49, 58, 70] . In recent years, researchers have gained a deeper theoretical understanding of this topic. The centralized setting (also known as self-play) has been investigated in Bai and Jin [8] , Bai et al. [9] , Cui et al. [17] , Huang et al. [30] , Jin et al. [33] , Liu et al. [40] , Wang et al. [63] , Xiong et al. [67] , Zhang et al. [69] , and this work focuses on the representative VI-ULCB design [9] . On the other hand, decentralized learning is more challenging, and the major breakthrough is made by V-learning [9, 32, 41, 51] , which is thus adopted as the target algorithm in this work. 
conclusions: 
 This work investigated the in-context game-playing (ICGP) capabilities of pre-trained transformers, broadening the research scope of in-context RL from the single-agent scenario to the more challenging multi-agent competitive games. Focusing on the classical two-player zero-sum Markov games, a general learning framework was first introduced, laying down a 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 an in-context manner. As a 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 incontext manner) and motivate future studies on this under-explored research direction. 
 
 Appendix: 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, we 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.The research direction of in-context game-playing is currently under-explored, and we believe that there are many interesting topics to be further investigated.• Different game forms and game-solving algorithms. This work mainly studies the classical twoplayer zero-sum Markov games, which can be viewed as the most basic form of competitive games, and has particular focuses on constructing transformers to realize V-learning [32] and VI-ULCB [8] .The cooperative games, on the other hand, are conceptually more similar to the single-agent setting [38] . There are more complicated game forms [46, 48] , e.g., the mixed cooperative-competitive games, which requires different game-solving algorithms. We believe the framework built in this work is beneficial to further explore the capabilities of pre-trained models in game-theoretical scenarios.• Pre-training dataset construction. This work considering the pre-training dataset is collected from the context algorithm with an additional augmentation. First, while the current proofs rely on the augmentation, it will be an interesting topic to understand whether it is necessary. As mentioned Sec. 3.1.1, learning in Markov games typically require more diverse data than learning in singleagent settings; however, the minimum requirement to perform effective pre-training is 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 theoretically 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 empirical evaluations. Due to the limited computation resources, the experiments reported in Sec. 5 are relatively small-scale compared with the current size of practically adopted transformers. It would be an important and interesting direction to further evaluate the ICGP capabilities of pre-trained transformers in large-scale experiments and practical game-theoretic applications. Also, the training dynamics are also worth further investigation, e.g., the sudden shifts in learning effectiveness reported by Reddy [45] .Besides these directions, from the theoretical perspective, we believe it would be valuable to investigate how to extend the current study on the tabular setting to incorporate function approximation, where we conjecture it is sufficient for the pre-training dataset to cover information of certain representative states and actions (e.g., a well-coverage of the feature space) [72] . Another attractive theoretical 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.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 {Alg θ : θ ∈ Θ}, we sayΘ ⊆ Θ is a ρ-cover of Θ, if Θ is a finite set such that for any θ ∈ Θ, there exists θ ∈ Θ such that for all D t-1 , s ∈ S, t ∈ [T ], it holds that log Alg θ (•, •|D t-1 , s) -log Alg θ (•, •|D t-1 , s) ∞ ≤ ρ.The covering number N Θ (ρ) is the minimal cardinality of Θ such that Θ is a ρ-cover of Θ. Assumption C.2 (Centralized Approximate Realizability). There exist θ * ∈ Θ andε real > 0 such that for all s ∈ S, t ∈ [T ], (a, b) ∈ A × B, it holds that log E D∼P Alg 0 Λ Alg 0 (a, b|D t-1 , s) Alg θ * (a, b|D t-1 , s) ≤ ε real .Then, the following pre-training guarantee can be established. E D∼P Alg 0 Λ t∈[T ],s∈S TV(Alg 0 , Alg θ |D t-1 , s) ≲ T S √ ε real + T S log (N Θ T S/δ) N .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 ρ-covering set of Θ with covering number N Θ = N Θ (ρ) as defined in Definition C.1. With Lemma 15 in Lin et al. [38] , we can obtain that for any θ ∈ Θ, there exists θ ∈ Θ such that for all D t-1 , t ∈ [T ] and s ∈ S,TV Alg θ , Alg θ |D t-1 , s) ≤ ρ For m ∈ [N Θ ], t ∈ [T ], i ∈ [N ], s ∈ S, we define that ℓ t i,m (s) := log Alg 0 a t i,s , b t i,s |D t-1 i , s Alg θm a t i,s , b t i,s |D t-1 i , s .According to Lemma 14 in Lin et al. [38] , with probability at least1 -δ, for all m ∈ [N Θ ], t ∈ [T ], s ∈ S, it holds that 1 2 i∈[N ] ℓ t i,m (s) + log(N Θ T S/δ) ≥ i∈[N ] -log E exp - ℓ t i,m (s) 2 .Furthermore, it can be established thatE exp - ℓ t i,m (s) 2 |D t-1 i = E   Alg θm a t i,s , b t i,s |D t-1 i , s Alg 0 a t i,s , b t i,s |D t-1 i , s |D t-1 i   = (a,b)∈A×B Alg θm a, b|D t-1 i , s Alg 0 a, b|D t-1 i , s , which implies that E exp - ℓ t i,m (s) 2 = 1 - 1 2 • E   (a,b)∈A×B Alg θm a, b|D t-1 i , s -Alg 0 a, b|D t-1 i , s 2   ≤ 1 - 1 2 • E TV Alg θm , Alg 0 |D t-1 i , s 2 ,where the inequality is from the fact that the Hellinger distance is smaller than the TV distance.Then, we can obtain that for any θ covered by θ m , it holds thatE D TV Alg 0 , Alg θ |D t-1 , s 2 ≤ E D TV Alg 0 , Alg θm |D t-1 , s + E D TV Alg θm , Alg θ |D t-1 , s 2 ≤ 2 E D TV Alg 0 , Alg θm |D t-1 , s 2 + 2 E D TV Alg θm , Alg θ |D t-1 , s 2 ≤ 2E D TV Alg 0 , Alg θ |D t-1 , s 2 + 2ρ 2 ≤ 4 -4E exp - ℓ t i,m (s) 2 + 2ρ 2 ≤ -4 log E exp - ℓ t i,m (s) 2 + 2ρ 2 ,which further implies thatN s∈S t∈[T ] E D TV Alg 0 , Alg θ |D t-1 , s 2 ≤ -4 s∈S t∈[T ] i∈[N ] log E exp - ℓ t i,m (s) 2 + 2N ST ρ 2 ≤ 2 s∈S t∈[T ] i∈[N ] ℓ t i,m (s) + 2N ST ρ 2 + 4ST log(N Θ T S/δ) = 2 s∈S t∈[T ] i∈[N ] log Alg 0 a t i,s , b t i,s |D t-1 i , s Alg θm a t i,s , b t i,s |D t-1 i , s + 2N ST ρ 2 + 4ST log(N Θ T S/δ) ≤ 2 s∈S t∈[T ] i∈[N ] log Alg 0 a t i,s , b t i,s |D t-1 i , s Alg θ a t i,s , b t i,s |D t-1 i , s + 2N ST ρ 2 + 2N ST ρ + 4ST log(N Θ T S/δ).Thus, for the obtained θ, with probability at least 1 -δ, it holds thatN s∈S t∈[T ] E D TV Alg 0 , Alg θ |D t-1 , s 2 ≤ 2 s∈S t∈[T ] i∈[N ] log Alg 0 a t i,s , b t i,s |D t-1 i , s Alg θ a t i,s , b t i,s |D t-1 i , s + 2N ST ρ 2 + 2N ST ρ + 4ST log(N Θ T S/δ) ≤ 2 s∈S t∈[T ] i∈[N ] log Alg 0 a t i,s , b t i,s |D t-1 i , s Alg θ * a t i,s , b t i,s |D t-1 i , s + 2N ST ρ 2 + 2N ST ρ + 4ST log(N Θ T S/δ) ≤ 2 s∈S t∈[T ] i∈[N ] log E Alg 0 a t i,s , b t i,s |D t-1 i , s Alg θ * a t i,s , b t i,s |D t-1 i , s + ST log(T S/δ) + 2N ST ρ 2 + 2N ST ρ + 4ST log(N Θ T S/δ) ≤ 2N ST ε real + ST log(T S/δ) + 2N ST ρ 2 + 2N ST ρ + 4ST log(N Θ T S/δ),Further by Cauchy-Schwarz inequality, we can obtain thats∈S t∈[T ] E D TV Alg 0 , Alg θ |D t-1 , s ≤ ST s∈S t∈[T ] E D TV Alg 0 , Alg θ |D t-1 , s 2 = O ST √ ε real + ST log(N Θ ST ) N + ST √ ρ + ST ρTaking ρ = 1/N concludes the proof.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 [8] requires an oracle solver that can provide the exact NE policy pair (µ * , ν * ) from any two general input payoff matrices (Q, Q) ∈ R A×B ×R A×B . However, it is known that approximating such a 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, we consider finding such CCEs via no-regret learning. 2 In particular, both players virtually run multiplicative weight update (MWU) (which is 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 an approximate CCE. The details of the VI-ULCB algorithm are provided in Alg. 1.More specifically, we consider that an approximate CCE solver is adopted such that with each pair of inputs(Q h (s, •, •), Q h (s, •, •)), we can obtain an ε CCE -approximate CCE policy π h (•, •|s) which satisfies that E (a,b)∼π h (•,•|s) Q(s, a, b) ≥ max a * ∈S E (a,b)∼π h (•,•|s) Q(s, a * , b) -ε CCE E (a,b)∼π h (•,•|s) Q(s, a, b) ≤ min b * ∈S E (a,b)∼π h (•,•|s) Q(s, a, b * ) + ε CCE .We also specifically choose to 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 to denote normalized losses:L h (s, a, b) := H -Q h (s, a, b) H , L h (s, a, b) := H -Q h (s, a, b) H .Standard online learning results [13] guarantee that using learning rates η A = log(A)/N MWU and η B = log(B)/N MWU , after N MWU rounds of MWU, the policyπ h (•, •|s) = 1 N MWU n∈[N ] µ h n (•|s)ν h n (•|s)is an ε CCE -approximate CCE policy, withε CCE = H log(A + B) N MWU . Algorithm 1 VI-ULCB 1: Initialize: for any (s, a, b, h), Q h (s, a, b) ← H, Q h (s, a, b) ← 0, N h (s, a, b) ← 0, N h (s, a, b, s ′ ) ← 0 2: for episode g = 1, • • • , G do 3: for (s, a, b) ∈ S × A × B do 4: Compute Q h (s, a, b) ← min rh (s, a, b) + Ph V h+1 (s, a, b) + c H 2 Sι N h (s h ,a h ,b h ) , H 5: Compute Q h (s, a, b) ← max rh (s, a, b) + Ph V h+1 (s, a, b) -c H 2 Sι N h (s h ,a h ,b h ) , 0 6:end for 7:for s ∈ S do8: Update π h (•, •|s) ← ε N -approximate CCE Q h (s, •, •), Q h (s, •, •) solved by N -round MWU 9: Compute V h (s) ← a,b π h (a, b|s)Q h (s, a, b) 10: Compute V h (s) ← a,b π h (a, b|s)Q h (s, a, b) 11:end for 12:for step h = 1, • • • , H do 13:Take action(a h , b h ) ∼ π h (•, •|s h ) 14:Observe reward r h and next state s h+1 ComputeEQUATIONUpdateO + = O + + o +,n and O -= O -+ o -,n 9: end for 10: Output: policy n∈[N ] µ h n (•|s)ν h n (•|s)/NFurthermore, for a certain bounded ε CCE , Xie et al. [65] demonstrated that the performance degradation can still be controlled. Following the results therein, the following theorem can be easily established.Theorem D.1 (Modified from Theorem 2 from Bai and Jin [8] ). With probability at least 1 -δ, in any environment M , the output policies {(µ g , ν g ) :g ∈ [G]} from the MWU-version of VI-ULCB satisfy that g∈[G] V †,ν g M (s 1 ) -V µ g , † M (s 1 ) = O H 3 S 2 ABT log(SABT /δ) + T ε CCE .With δ = 1/T , to have a non-dominant loss caused by the approximate CCE solver, we can choose N MWU = G. Then, for any environment M , it holds that E D∼P VI-ULCB M g∈[G] V †,ν g M (s 1 ) -V µ g , † M (s 1 ) = O H 3 S 2 ABT log(SABT ) .In the following, for the convenience of notations, we will consider step t + 1, i.e., with observations D t ∪ {s t+1 }. Given an input token matrixH = h(D t , s t+1 ) = [h 1 , h 2 , • • • , h 2t+1 ],we construct a transformer to perform the following steps . The following provides a sketch of the proof.    h pre,a 2t+1 h pre,b 2t+1 h pre,c 2t+1 h pre,d 2t+1     step 1 ---→          h pre,{a,b,c} 2t+1 N h (s, a, b) N h (s, a, b, s ′ ) N h (s, a, b)r h (s, a, b) ⋆ 0 pos 2t+1          step 2 ---→         h pre,{a,b,c} 2t+1 Ph (s ′ |s, a, b) rh (s, a, b) ⋆ 0 pos 2t+1         step 3 ---→         h pre,{a,b,c} 2t+1 Q h (s, a, b) Q h (s, a, b) ⋆ 0 pos 2t+1         step 4 ---→      h pre,{a,b,c} 2t+1 π h (a, b|s) ⋆ 0 pos 2t+1      step 5 ---→         h pre,{a,b,c} 2t+1 V h (s) V h (s) ⋆ 0 pos 2t+1         step 6 ---→   h pre,{a,b} 2t+1 π h+1 (•, •|s h+1 ) h post,d 2t+1   :=     h post,aStep 1 There exists an attention-only transformer TF θ to complete Step 1 withL = O(1), max l∈[L] M (l) = O(HS 2 AB), ∥θ∥ = O(HG + HS 2 AB).Step 2 There exists a transformer TF θ to complete Step 2 withL = O(1), max l∈[L] M (l) = O(HS 2 AB), d ′ = O(G 2 HS 2 AB) ∥θ∥ = O(HS 2 AB + G 3 + GH).Step 3 There exists a transformer TF θ to complete Step 3 withL = O(H), max l∈[L] M (l) = O(SAB), d ′(l) = O(SAB), ∥θ∥ = O(H + SAB).Step 4 There exists a transformer TF θ to complete Step 4 withL = O(GHS), max l∈[L] M (l) = O(AB), d ′(l) = O(AB), ∥θ∥ = O(H + AB).Step 5 There exists an attention-only transformer TF θ to complete Step 5 withL = O(1), max l∈[L] M (l) = O(HS), ∥θ∥ = O(Step 6 There exists an attention-only transformer TF θ to complete Step 6 withL = O(1), max l∈[L] M (l) = O(HS), ∥θ∥ = O(HS + GH).Thus, the overall transformer TF θ can be summarized asL = O(GHS), max l∈[L] M (l) = O(HS 2 AB), d ′ = O(G 2 HS 2 AB), ∥θ∥ = O(HS 2 AB + G 3 + GH).Also, from the later construction, we can observe that log(R) = Õ(1).N h (s, a, b), N h (s, a, b, s ′ ) and N h (s, a, b)r h (s, a, b)This can be similarly completed by an attention-only transformer constructed in Step 1 of realizing UCB-VI in Lin et al. [38] . This can be similarly completed by a transformer constructed in Step 2 of realizing UCB-VI in Lin et al. [38] .Q h (s ′ |s, a, b) and Q h (s ′ |s, a, b)The computation of Q h (s ′ |s, a, b) can be similarly completed by a transformer constructed in Step 3 of realizing UCB-VI in Lin et al. [38] . The Q part can also be obtained by modifying a few plus signs to minuses.This is the most challenging part of realizing the VI-ULCB design, which distinguishes it from the single-agent algorithms, e.g., UCB-VI [6] . As mentioned in Appendix D.1, we obtain an approximate CCE via virtually playing MWU. In the following, for one tuple (s, h), we prove that one transformer can be constructed to perform a one-step MWU update with thatL = O(1), max l∈[L] M (l) = O(AB), d ′ = O(AB), ∥θ∥ = O(H + AB).To obtain this result, we construct a transformer to perform the following computation from inputs to output for all t ′ ≤ t:h 2t = [ 0 ] , h 2t+1 =            L h (s, •, •) L h (s, •, •) τ <n o +,τ τ <n o -,τ µ n (•|s) ν n (•|s) τ ≤n µ τ (•)ν τ (•) 0            compute ----→ h 2t = [ 0 ] , h 2t+1 =            L h (s, •, •) L h (s, •, •) τ <n+1 o +,τ τ <n+1 o -,τ µ n+1 (•|s) ν n+1 (•|s) τ ≤n+1 µ τ (•)ν τ (•) 0           .Note that here we again use the notations L h (s,•, •) = H-Q h (s,•,•) H and L h (s, •, •) = H-Q h (s,•,•) Hto denote the normalized losses. It can be seen that this computation can be performed via one ReLU MLP layer.Step 4.1: Get o +,n and o -,n .First, we can construct that for all t ′ ≤ tEQUATIONEQUATIONEQUATIONEQUATIONa,1 h 2t ′ +1 = 2t ′ + 1.With ReLU activation, this constructed transformer leads to updates that h d 2t ′ = 0 and h d 2t ′ +1 = o +,n (a). With another A -1 paralleling heads, the whole vector o +,n can be computed. Similarly, with B more paralleling heads, the whole vector o -,n can be computed.Then, with one ReLU MLP layer, we can obtain thath d 2t ′ = 0, h d 2t ′ +1 = τ <n o +,τ τ <n o -,τ + W (1) 2 σ r W (1) 1 h 2t ′ +1 = τ <n+1 o +,τ τ <n+1 o -,τ.The required transformer can be summarized asL = 1, M (1) = O(A + B), d ′ = O(A + B), ∥θ∥ = O(H).V h (s) and V h (s)We can construct thatEQUATIONEQUATIONEQUATION1 h 2t ′ +1 = 2t ′ + 1. With ReLU activation, this construction leads to thath 2t ′ = 0, h 2t ′ +1 = π h (•, •|s) • Q h (s, •, •) = V h (s).Thus, with overall 2HS paralleling heads, the values of{V h (s), V h (s) : h ∈ [H], s ∈ S} can be computed.The required transformer can be summarized asL = 1, M (1) = O(HS), ∥θ∥ = O(HS). D.2.8 Proof of Step 6: Obtain π h+1 (•, •|s h+1 )We can construct one HS-head transformer that for all (s, h)EQUATIONEQUATIONh,s h 2t ′ +1 =      e s e h -1 t ′ + 1 -1      ; V (1) h,s h 2t ′ = 0, V (1) h,s h 2t ′ +1 = π h (•, •|s).With ReLU activation, this construction leads to the update thath 2t ′ = 0, h 2t ′ +1 = 1 2t ′ + 1 • π h ′ +1 (•, •|s t ′ +1 ).Then, we can construct thatEQUATION1 h 2t ′ +1 = 2t ′ + 1 2GH(t ′ + 1) 1 ; K (1) 1 h 2t ′ = 1 -1 2GHt ′ , K (1) 1 h 2t ′ +1 = 1 -1 2GH(t ′ + 1) ; V (1) 1 h 2t ′ = 0, V (1) h,s h 2t ′ +1 = 1 2t ′ + 1 • π h ′ +1 (•, •|s t ′ +1 ).With ReLU activation, this construction leads to the update thath 2t ′ = 0, h 2t ′ +1 = π h ′ +1 (•, •|s t ′ +1 ).The required transformer can be summarized asL = 2, max l∈[L]M (l) = O(HS), ∥θ∥ = O(HS + GH).Proof of Theorem 4.2. First, we can obtain the decomposition thatE M ∼Λ,D∼P Alg θ M   g∈[G] V †,ν g M (s 1 ) -V µ g , † M (s 1 )   = E M ∼Λ,D∼P Alg 0 M   g∈[G] V †,ν g M (s 1 ) -V µ g , † M (s 1 )   + E M ∼Λ,D∼P Alg θ M   g∈[G] V †,ν g M (s 1 )   -E M ∼Λ,D∼P Alg 0 M   g∈[G] V †,ν g M (s 1 )   + E M ∼Λ,D∼P Alg 0 M   g∈[G] V µ g , † M (s 1 )   -E M ∼Λ,D∼P Alg θ M   g∈[G] V µ g , † M (s 1 )   .Via Theorem D.1, it holds thatE M ∼Λ,D∼P Alg 0 M   g∈[G] V †,ν g M (s 1 ) -V µ g , † M (s 1 )   = O H 3 S 2 ABT log(SABT ) .Then, via Lemma E.1 and Theorem C.3, we can obtain thatE M ∼Λ,D∼P Alg 0 M   g∈[G] V µ g , † M (s 1 )   -E M ∼Λ,D∼P Alg θ M   g∈[G] V µ g , † M (s 1 )   = O   T • E M ∼Λ,D∼P Alg 0 M   t∈[T ] s∈S TV Alg 0 , Alg θ |D t-1 , s     = O T 2 S √ ε real + T 2 S log (N Θ T S/δ) N ,and similarly,E M ∼Λ,D∼P Alg θ M   g∈[G] V †,ν g M (s 1 )   -E M ∼Λ,D∼P Alg 0 M   g∈[G] V †,ν g M (s 1 )   = O T 2 S √ ε real + T 2 S log (N Θ T S/δ) N .With Theorem 4.1 providing that ε real = 0, combining the above terms completes the proof of the regret bound. The bound on the covering number, i.e., log(N Θ ) can be obtained via Lemma I.4.Lemma E.1. For any two centralized algorithms Alg α and Alg β , we denote their performed policies for episode g are (π g α , π g β ), whose marginal policies are (µ g α , ν g α ) and (µ g β , ν g β ). For {µ g α , ν g β }, it holds that . A similar result holds for {ν g α , ν g β }.E α g∈[G] V µ g α , † M (s 1 ) -E β g∈[G] V µ g β , † M (s 1 ) ≲ T •E α t∈[T ],s∈S TV π t α , π t β |D t-Proof of Lemma E.1. It holds thatE D∼P Alg α M   g∈[G] V µ g α , † M (s 1 )   -E D∼P Alg β M   g∈[G] V µ g β , † M (s 1 )   = E D∼P Alg α M   g∈[G] V µ g α , † M (s 1 ) - g∈[G] V µ g β , † M (s 1 )   :=(term I) + E D∼P Alg α M   g∈[G] V µ g β , † M (s 1 )   -E D∼P Alg β M   g∈[G] V µ g β , † M (s 1 )   :=(term II)Denoting D H := D (g-1)H+1:gH and f (D H ) = h∈[H] r g,h , we can further obtain that V µ g α , † M (s 1 ) -V µ g β , † M (s 1 ) (a) ≤ V µ g α ,ν † (µ g β ) M (s 1 ) -V µ g β ,ν † (µ g β ) M (s 1 ) = E D H ∼P µ g α ,ν † (µ g β ) M f (D H ) -E D H ∼P µ g β ,ν † (µ g β ) M f (D H ) = h∈[H] E D 1:h ∼P µ g α ,ν † (µ g β ) M ,D h+1:H ∼P µ g β ,ν † (µ g β ) M f (D H ) - h∈[H] E D 1:h-1 ∼P µ g α ,ν † (µ g β ) M ,D h:H ∼P µ g β ,ν † (µ g β ) M f (D H ) (b) ≤ 2H h∈[H] E D 1:h-1 ∼P µ g α ,ν † (µ g β ) M ,s g,h TV µ g,h α × ν h † (µ g β )(•, •|s g,h ), µ g,h β × ν h † (µ g β )(•, •|s g,h ) (c) = 2H h∈[H] E D 1:h-1 ∼P µ g α ,ν † (µ g β ) M ,s g,h TV µ g,h α (•|s g,h ), µ g,h β (•|s g,h ) (d) ≤ 2H h∈[H] s∈S TV π g,h α (•, •|s), π g,h β (•, •|s) ,(term I) := E D∼P Alg α M   g∈[G] V µ g α , † M (s 1 ) - g∈[G] V µ g β , † M (s 1 )   ≤ 2H • E D∼P Alg α M   t∈[T ] s∈S TV π t α , π t β |D t-1 , s   . Also, denoting g(D) = g∈[G] V µ g β , † (s 1 ), it holds that (term II) := E D∼P Alg α M   g∈[G] V µ g β , † (s 1 )   -E D∼P Alg β M   g∈[G] V µ g β , † (s 1 )   = t∈[T ] E D t ∼P Alg α M ,D t+1:T ∼P Alg β M [g(D)] - t∈[T ] E D t-1 ∼P Alg α M ,D t:T ∼P Alg β M [g(D)] ≤ 2T t∈[T ] E D t-1 ∼P Alg α M ,s t TV Alg α , Alg β |D t-1 , s t ≤ 2T • E D∼P Alg α M   t∈[T ] s∈S TV π t α , π t β |D t-1 , s   .Combining (term I) and (term II) finishes the proof.Definition F.1 (The Complete Version of Definition 3.1). For a class of algorithms {Alg θ+ : θ + ∈ Θ + }, we say Θ+ ⊆ Θ + is a ρ + -cover of Θ + , if Θ+ is a finite set such that for any θ + ∈ Θ + , there exists θ+ ∈ Θ+ such that for all D t-1 + , s ∈ S, t ∈ [T ], it holds thatlog Alg θ+ (•, •|D t-1 + , s) -log Alg θ+ (•|D t-1 + , s) ∞ ≤ ρ + .The covering number N Θ+ (ρ + ) is the minimal cardinality of Θ+ such that Θ+ is a ρ + -cover of Θ + .Similarly, for a class of algorithms {Alg θ-: θ -∈ Θ -}, we say Θ-⊆ Θ -is a ρ --cover of Θ -, if Θis a finite set such that for any θ -∈ Θ -, there exists θ-∈ Θsuch that for allD t-1 -, s ∈ S, t ∈ [T ], it holds that log Alg θ-(•, •|D t-1 -, s) -log Alg θ-(•|D t-1 -, s) ∞ ≤ ρ -.The covering numberN Θ-(ρ -) is the minimal cardinality of Θ-such that Θ-is a ρ --cover of Θ -.Assumption F.2 (The Complete Version of Assumption 3.2). There exists θ * + ∈ Θ + such that there exists ε +,real > 0, for all t ∈ [T ], s ∈ S, a ∈ A, it holds thatlog E M ∼Λ,D∼P Alg 0 M Alg +,0 (a|D t-1 + , s) Alg θ * + (a|D t-1 + , s) ≤ ε +,real .Similarly, there exists θ * -∈ Θ -such that there exists ε -,real > 0, for all t∈ [T ], s ∈ S, b ∈ B, it holds that log E M ∼Λ,D∼P Alg 0 M Alg -,0 (b|D t-1 -, s) Alg θ * - (b|D t-1 -, s) ≤ ε -,real .Theorem F.3 (The Complete Version of Theorem 3.3). Let θ + be the max-player's pre-training output defined in Section 3.1.1. Take N Θ+ = N Θ+ (1/N ) as in Definition F.1. Then, under Assumption F.2, with probability at least 1 -δ, it holds thatE M ∼Λ,D∼P Alg 0 M   t∈[T ],s∈S TV Alg +,0 , Alg θ+ |D t-1 + , s   = O   T S √ ε +,real + T S log N Θ+ T S/δ N   .Let θ -be the min-player's pre-training output defined in Section 3.1.1. Take N Θ-= N Θ-(1/N ) as in Definition F.1. Then, under Assumption F.2, with probability at least 1 -δ, it holds thatE M ∼Λ,D∼P Alg 0 M   t∈[T ],s∈S TV Alg -,0 , Alg θ-|D t-1 + , s   = O   T S √ ε -,real + T S log N Θ-T S/δ N   .Proof of Theorem F.3. This theorem can be similarly proved as Theorem 3.3.In the following proof, we focus on the max-player's perspective, which can be easily extended for the min-player.The details of V-learning [32] , discussed in Sec. 3.2, are presented in Alg. 3, where the following notations are adoptedα n = H + 1 H + n , β n = c • H 3 A log(HSAG/δ) n , γ n = η n = H log(A) An , ω n = α n n τ =2 (1 -α τ ) -1.After the learning process, V-learning requires an additional procedure to provide the output policy.We include this procedure in Alg. 4 , where the following notations are adopted N g,h (s) = the number of times s is visited at step h before episode g, g h i (s) = the index of the episode s is visited at step h for the i-th time,α n,i = α i n j=i+1(1 -α j ).Following the results in Jin et al. [32] , we can obtain the following performance guarantee of V-learning. Theorem G.1 (Theorem 4 in Jin et al. [32] ). With probability at least 1 -δ, in any environment M , the output policies (μ, ν) from V-learning satisfy thatV †,ν M (s 1 ) -V μ, † M (s 1 ) = O H 5 S(A + B) log(SABT /δ) G .Thus, with δ = 1/T , we can obtain thatE D∼P V-learning M V †,ν M (s 1 ) -V μ, † M (s 1 ) = O H 5 S(A + B) log(SABT ) G .Algorithm 3 V-learning [32] 1: Initialize: for any (s, a, h)EQUATION:for step h = 1, • • • , H do 5:Take action a g,h ∼ π h (•|s g,h ), observe reward r g,h and next state s g,h+16:Update n = N h (s g,h ) ← N h (s g,h ) + 17: Update Ṽ h (s g,h ) ← (1 -α n ) Ṽ h (s g,h ) + α n r g,h + V h+1 (s g,h+1 ) + β n 8: Update V h (s g,h ) ← min H + 1 -h, Ṽ h (s g,h ) 9: Compute lh n (s g,h , a) ← H-r g,h -V h+1 (s g,h+1 ) H • 1{a=a g,h } µ h (a g,h |s g,h )+γn for all a ∈ A 10: Update µ h (a|s g,h ) ∝ exp -ηn ωn • τ ∈[n] ω τ • lh τ (s g,h , a) for all a ∈ A 11:end for 12: end forBefore digging into the proof of 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 TF θ withL = L D , max l∈[L] M (l) = M D , d ′ = d D , ∥θ∥ = F D , Algorithm 4 V-learning Executing Output Policy μ [32] 1: Sample g ∼ Unif(1, 2, • • • , G) 2: for step h = 1, • • • , H do 3: Observe s h and set n ← N g,h (s h ) 4: Set g ← g h i (s h ) where i ∈ [n] is sampled with probability α n,i 5:Take action a h ∼ µ g,h (•|s h ) 6: end forsuch that for any x ∈ [0, 1], y ∈ [ log(A)/(AG), log(A)/A + 1], φ > 0, with input H = [h 1 , • • • , h e , • • • ],whereh i = 0 φ 0 , ∀i ̸ = e; h e = x y 0 , the transformer can provide output H = [h 1 , • • • , h e , • • • ] h i =    0 φ 0 0    , ∀i ̸ = e; h e =    x y x/y 0    .We note that this assumption on performing exact division is only for the convenience of the proof as one can approximate the division to any arbitrary precision only via one MLP layer with ReLU activation.k ∞ (R) = [-R, R] ∞ denote the standard ℓ ∞ ball in R kwith radius R > 0, we introduce the following definitions and result. Definition G.3 (Approximability by Sum of ReLUs, Definition 12 in Bai et al. [7] ). A function g : R k → R is (ε approx , R, M, C)-approximable by sum of ReLUs, if there exists a "(M, C)-sum of ReLUs" functionf M,C (z) = M m=1 c m σ(a ⊤ m [z; 1]) with M m=1 |c m | ≤ C, max m∈[M ] ∥a m ∥ 1 ≤ 1, a m ∈ R k+1 , c m ∈ R such that sup z∈Ball k ∞ (R) |g(z) -f M,C (z)| ≤ ε approx .Definition G.4 (Sufficiently Smooth k-variable Function, Definition A.1 in Bai et al. [7] ). We say a function g :EQUATIONsup z∈Ball k ∞ (R) ∥∇ i g(z)∥ ∞ = sup z∈Ball k ∞ (R) max j1,••• ,ji∈[k] |∂ zj 1 •••zj i g(z)| ≤ L i for all i ∈ {0, 1, • • • , s}, with max 0≤i≤s L i R i ≤ C ℓ .Proposition G.5 (Approximating Smooth k-variable Functions, Proposition A.1 in Bai et al. [7] ). For any ε approx > 0, R ≥ 1, C ℓ > 0, we have the following:Any (R, C ℓ )-smooth function g : R k → R is (ε approx , R, M, C) approximable by sum of ReLUs with M ≤ C(k)C 2 ℓ log(1 + C ℓ /ε approx )/ε 2 approx and C ≤ C(k)C ℓ , where C(k) > 0 is a constant that depends only on k.Then, we can consider g(x, y)= (c 1 + x)/(c 2 + y) with c 1 ≥ 1, c 2 ≥ 1 + c ′ 2 > 1, x ∈ [-1, 1] and y ∈ [-1, 1]. It can be verified that |g(x, y)| = c 1 + x c 2 + y ≤ 1 + c 1 c ′ 2 ; |∂ x g(x, y)| = 1 c + y ≤ 1 c ′ 2 ; |∂ y g(x, y)| = c 1 + x (c 2 + y) 2 ≤ 1 + c 1 (c ′ 2 ) 2 ; |∂ 2 x g(x, y)| = 0; |∂ 2 y g(x, y)| = 2(c 1 + x) (c 2 + y) 3 ≤ 2(1 + c 1 ) (c ′ 2 ) 3 ; |∂ x ∂ y g(x, y)| = 1 (c + y) 2 ≤ 1 (c ′ 2 ) 2 ; |∂ 3 x g(x, y)| = 0; |∂ 3 y g(x, y)| = 6(c 1 + x) (c 2 + y) 4 ≤ 6(1 + c 1 ) (c ′ 2 ) 4 ; |∂ 2 x ∂ y g(x, y)| = 0; |∂ x ∂ 2 y g(x, y)| = 2 (c + y) 3 ≤ 2 (c ′ 2 ) 3 .Then, from Definition G.4 there exists one C l such that g(x, y) is (1, C l )-smooth. Thus, by Proposition G.5, this function can be approximated by a sum of ReLUs (defined in Definition G.3). With this observation, the division operation required in Assumption G.2 can be approximated.We consider each episode of the max-player's observations to be embedded in 2H tokens. In particular, for each t ∈ [T ], we construct thath 2t-1 = h + (s g,h ) =        0 A 0 s g,h 0 A 0 pos 2t-1        =:     h pre,a 2t-1 h pre,b 2t-1 h pre,c 2t-1 h pre,d 2t-1     , h 2t = h + (a g,h , r g,h ) =        a g,h r g,h 0 S 0 A 0 pos 2t        =:     h pre,a 2t h pre,b 2t h pre,c 2t h pre,d 2t     ,where s g,h , a g,h are represented via one-hot embedding. The positional embedding pos i is defined aspos i :=           g h t e h v i i i 2 1          , where v i := 1{h a i = 0} denote the tokens that do not embed actions and rewards. In summary, for observations D t-1 + ∪ {s t }, we obtain the tokens of length 2t -1 which can be expressed as the following form:H := h + (D t-1 + , s t ) = [h 1 , h 2 , • • • , h 2t-1 ] = [h + (s 1 ), h + (a 1 , r 1 ), • • • , h + (s t )].With the above input H, the transformer outputs H = TF θ+ (H) of the same size as H. The extraction mapping A is directly set to satisfy the followingA • h -1 = A • h 2t-1 = h c 2t-1 ∈ R A , i.e., the part c of the output tokens is used to store the learned policy.In the following, for the convenience of notations, we will consider step t + 1, i.e., with observations D t + ∪ {s t+1 }. Given an input token matrixH = h + (D t + , s t+1 ) = [h 1 , h 2 , • • • , h 2t+1 ],we construct a transformer to perform the following steps    h pre,a 2t+1 h pre,b 2t+1 h pre,c 2t+1 h pre,d 2t+1     step 1 ---→      h pre,{a,b,c} 2t+1 N t (s t ) ⋆ 0 pos 2t+1      step 2 ---→        h pre,{a,b,c} 2t+1 Ṽ t (s t ) V t (s t ) ⋆ 0 pos 2t+1        step 3 ---→        h pre,{a,b,c} 2t+1 ln (s t , •) µ t (•|s t ) ⋆ 0 pos 2t+1        step 4 ---→   h pre,{a,b} 2t+1 µ t+1 (•|s t+1 ) h d 2t+1   :=     h post,a 2t+1 h post,b 2t+1 h post,c 2t+1 h post,d 2t+1     ,where n := N h (s g,h ).To ease the notations, in the proof, we will slightly abuse TF θ as TF θ+ . The following provides a sketch of the proof.Step 1 There exists an attention-only transformer TF θ to complete Step 1 withL = O(1), max l∈[L] M (l) = O(1), ∥θ∥ = O(HG)Step 2 There exists a transformer TF θ to complete Step 2 withL = O(HG), max l∈[L] M (l) = O(HS 2 ), d ′ = O(G), ∥θ∥ = O(G 3 + GH),Step 3 There exists a transformer TF θ to complete Step 3 withL = O(GHL D ), max l∈[L] M (l) = O(HSA + M D ), d ′ = O(d D + A + G), ∥θ∥ = O(GH 2 S + F D + G 3 ),Step 4 There exists a transformer TF θ to complete Step 4 withL = O(1), max l∈[L] M (l) = O(HS), ∥θ∥ = O(HS + GH).Thus, the overall transformer TF θ can be summarized asL = O(GHL D ), max l∈[L] M (l) = O(HS 2 + HSA + M D ), d ′ = O(G + A + d D ), ∥θ∥ = O(GH 2 S + G 3 + F D ).Also, from the later construction, we can observe that log(R) = Õ(1). The bound on the covering number, i.e., log(N Θ+ ) can be obtained via Lemma I.4.Step 1: Update N h (s g,h ).From the proof of Step 1 in realizing UCB-VI in Lin et al. [38] , we know that there exists a transformer with 3 heads that for all t ′ ≤ t, can moves t ′ , (a t ′ , r t ′ ) from h a 2t ′ -1 and h b 2t ′ to h d 2t ′ +1while maintaining h d 2t ′ not updated. This constructed transformer is shown in Lin et al. [38] to be an attention-only one with ReLU activation andL = 2, max l∈[L] M (l) ≤ 3, ∥θ∥ ≤ O(HG).Then, still following Lin et al. [38] , another attention-only transformer can be constructed so that N t (s t ) can be computed in h d 2t+1 . The constructed transformer has ReLU activation andL = 2, max l∈[L] M (l) = O(1), ∥θ∥ = O(H).In summary, at the end of Step 1, we can obtain that for all t ′ ≤ t,h d 2t ′ = 0 pos 2t ′ , h d 2t ′ +1 =         s t ′ a t ′ r t ′ N t ′ (s t ′ ) 0 pos 2t ′ +1        , with an attention-only transformer that uses ReLU activation andL = 4, max l∈[L] M (l) = O(1), ∥θ∥ = O(HG). G.3.4 Proof of Step 2: Compute Ṽ h (s g,h ) and V h (s g,h )In Step 2, let n t = N t (s t ), the following computations will be performed:Ṽ t new (s t ) ← (1 -α n t ) Ṽ t old (s t ) + α n t r t + V t+1 old (s t+1 ) + β n t , V t new (s t ) ← min H + 1 -h, Ṽ t new (s t ) .First, similar to Step 2 in realizing UCB-VI in Lin et al. [38] , we can obtain α n t ′ and β n t ′ in each h d 2t ′ +1 via a transformer with ReLU activation andL = O(1), max l∈[L] M (l) = O(1), d ′ = O(G), ∥θ∥ = O(G 3 ).Then, we can assume that the values of { Ṽ h old (s), V h old (s) : h ∈ [H], s ∈ S} is already computed in token h d 2τ -1 , and prove via induction to show that the set of new values can be computed in token h d 2τ +1 , i.e.,h d 2τ -1 =      ⋆ Ṽ 1:H old (•) V 1:H old (•) 0 pos 2τ -1      , h d 2τ = 0 pos 2τ , h d 2τ +1 = 0 pos 2τ +1 compute ----→ h d 2τ = 0 pos 2τ , h d 2τ +1 =      ⋆ Ṽ 1:H new (•) V 1:H new (•) 0 pos 2τ +1      .In the following, we will show that this one-step update can be completed via a transformer that requiresL = O(1), max l∈[L] M (l) = O(HS 2 ), d ′ = O(G), ∥θ∥ = O(G 3 + GH),and the overall updates can be completed via stacking T similar transformers.Step 2.1: Obtain τ -|t ′ -1 -τ |.τ -|t ′ -1 -τ | in each h d 2t ′ -1 and h d 2t ′ for all t ′ ≤ t.In particular, we can construct three MLP layers with ReLU activation, i.e., {WEQUATIONThe required transformer can be summarized asd ′ = 1, ∥θ∥ = O(GH). Step 2.2: Move Ṽ 1:H old (•) and V 1:H old (•). Then, we move Ṽ 1:H old (•) and V 1:H old (•) from h 2τ -1 to h 2τ +1 .In particular, we can construct thatQ 1 h 2t ′ =      v 2t ′ -1 τ -|t ′ -1 -τ | -1 t ′ 1      , Q 1 h 2t ′ +1 =      v 2t ′ +1 -1 τ -|t ′ -τ | -1 t ′ + 1 1      ; K 1 h 2t ′ =      1 1 τ -1 t ′ + 1      , K 1 h 2t ′ +1 =      1 1 τ -1 t ′ + 2      ; V 1 h 2τ -1 = (2τ + 1) Ṽ 1:h old (•) V 1:H old (•) , V 1 h 2τ = 0, V 1 h 2τ +1 = 0.With ReLU activation, this construction leads to thath 2t ′ = h 2t ′ + 1 2t ′ i≤2t ′ σ r (-1 -|t ′ -1 -τ | -t ′ + t(i) + 1) • V 1 h i = 0, ∀t ′ ≤ t h 2t ′ +1 = h 2t ′ +1 + 1 2t ′ + 1 i≤2t ′ +1 σ r (-|t ′ -τ | -t ′ + t(i) + 1) • V 1 h i =    1 2t ′ +1 (V 1 h 2t ′ -1 + V 1 h 2t ′ + 2V 1 h 2t ′ +1 ) = Ṽ 1:h old (•) V 1:H old (•) if t ′ = τ 0 otherwise .The transformer required in Step 2.3 can be summarized asL = 1, M (1) = O(1), ∥θ∥ = O(GH).Step 2.3:Compute Ṽ 1:H new (•) and V 1:H new (•). Finally, we get to compute Ṽ 1:H new (•) and V 1:H new (•), where Ṽ τ new (s τ ) = Ṽ τ old (s τ ) -α n τ Ṽ τ old (s τ ) + α n τ r τ + V τ +1 old (s τ +1 ) + β n τ .We can have a HS-head transformer thatQ h,s h 2t ′ =             v 2t ′ -1 τ -|t ′ -1 -τ | -1 t ′ 1 0 e h ′ 1 0             , Q h,s h 2t ′ +1 =             v 2t ′ +1 -1 τ -|t ′ -τ | -1 t ′ + 1 1 s t ′ e h ′ +1 1 α n t ′             , K h,s h 2t ′ =             1 1 τ -1 t ′ e s e h+1 -2 1             , K h,s h 2t ′ +1 =             1 1 τ -1 t ′ + 1 e s e h+1 -2 1             , V h,s h 2τ +1 = -(2τ + 1) • V h old (s) • [ e h,s] . It holds that for all t ′ ≤ t,h 2t ′ = h 2t ′ + 1 2t ′ h,s i≤2t ′ σ r (-1 -|t ′ -1 -τ | -t ′ + t(i) + e h ′ • e h+1 -2) V h,s h i = 0 h 2t ′ +1 = h 2t ′ +1 + 1 2t ′ + 1 h,s i≤2t ′ +1 σ r -|t ′ -τ | -t ′ -1 + t(i) + s t ′ • e s + e h ′ +1 • e h + α n t ′ -2 V h,s h i = V 1:H old (•) -α n t ′ V h ′ old (s t ′ ) • e h ′ ,s t ′ if t ′ = τ 0 otherwise ,which completes the computation (1 -α n τ ) Ṽ τ old (s τ ). Two similar HS-head transformers can further perform (1 -α n τ ) Ṽ τ old (s τ ) + α n τ r τ + α n τ β n τ . and a similar HS 2 -head transformer can finalizeṼ τ new (s τ ) as (1 -α n τ ) Ṽ τ old (s τ ) + α n τ r τ + α n τ β n τ + α n τ V τ +1old (s τ +1 ). Finally, from the proof of Step 3 in realizing UCB-VI in Lin et al. [38] , one MLP layer can performV τ old (s τ ) = min Ṽ τ new (s τ ), H -h + 1 .The required transformer in step 2.4 can be summarized asL = 4, max l∈[L] M (l) = O(HS 2 ), d ′ = O(1), ∥θ∥ = O(GH).Thus, we can see that the update of h 2τ +1 can be done. Repeating the similar step for each τ ∈ [T ] would complete the overall updates.Step 3: Compute ln t (s g,h , a) and µ h (a|s g,h )In step 3, let n t = N t (s t ), for step t, we updatelt n t (s t , a) ← H -r t -V t+1 (s t+1 ) H • 1{a = a t } µ t old (a t |s t ) + γ n t ; µ t new (a|s t ) ∝ exp   - η n t ω n t • i∈[n t ] ω i • lt i (s t , a)   .First, similar to Step 2, we can obtain ω n t ′ , η n t ′ /ω n t ′ and γ n t ′ in each h d 2t ′ +1 via a transformer with ReLU activation andL = O(1), max l∈[L] M (l) = O(1), d ′ = O(G), ∥θ∥ = O(G 3 ).Denoting vectors L ∈ R HSA and µ ∈ R HSA containing the cumulative losses and policies, i.e., i∈[n] ω i lh i (s, a) and µ h (a|s). Similar to step 2, we will assume that the values of {L old , µ old }, which are computed via information before time τ , are already contained in token h d 2τ -1 , and prove via induction to show that the set of new values can be computed in token h d 2τ +1 , i.e.,h d 2τ -1 =      ⋆ L old µ old 0 pos 2τ -1      , h d 2τ = 0 pos 2τ , h d 2τ +1 = 0 pos 2τ +1 compute ----→ h d 2τ = 0 pos 2τ , h d 2τ +1 =      ⋆ L new µ new 0 pos 2τ +1      .In the following, we will show that this one-step update can be completed via a transformer that requiresL = O(L D ), max l∈[L] M (l) = O(HSA + M D ), d ′ = O(d D + A), ∥θ∥ = O(GH 2 S + F D ),and the overall updates can be completed via stacking T similar transformers.Step 3.1: Obtain τ -|t ′ -1 -τ |.First, similar to step 2.1, we can have an auxiliary value τ -|t ′ -1 -τ | in each h d 2t ′ -1 and h d 2t ′ for all t ′ < t via three MLP layers. The required transformer can be summarized asd ′ = 1, ∥θ∥ = O(GH).Step 3.2: Compute lτ n τ (s τ , a). First, similar to Step 2.2, we can move L old and µ old from h d 2τ -1 to h d 2τ +1 while keeping other tokens unchanged. In particular, we can construct thatQ 1 h 2t ′ =      v 2t ′ -1 τ -|t ′ -1 -τ | -1 t ′ 1      , Q 1 h 2t ′ +1 =      v 2t ′ +1 -1 τ -|t ′ -τ | -1 t ′ + 1 1      ; K 1 h 2t ′ =      1 1 τ -1 t ′ + 1      , K 1 h 2t ′ +1 =      1 1 τ -1 t ′ + 2      ; V 1 h 2τ -1 = (2τ + 1) L old µ old , V 1 h 2τ = 0, V 1 h 2τ +1 = 0.With ReLU activation, this construction leads to thath 2t ′ = 0, ∀t ′ ≤ t; h 2t ′ +1 =    L old µ old if t ′ = τ 0 otherwise .Then, using similar constructions as Step 2.3, we can specifically extract V τ +1 (s τ +1 ) and µ τ old (a τ |s τ ) to h d 2τ +1 while keeping other tokens unchanged. Following the extraction, one MLP layer can compute the value H-r τ -V τ +1 (s τ +1 ) H and add it to h d 2τ +1 . The required transformer can be summarized asL = O(1), max l∈[L] M (l) = O(HSA), d ′ = 1, ∥θ∥ = O(GH).With Assumption G.2, for token h 2τ +1 , we can further have one transformer to computelτ n τ (s τ , a τ ) = H -r τ -V τ +1 (s τ +1 ) H • 1 µ τ old (a τ |s τ ) + γ n τ .The overall required transformer can be summarized asL = O(L D ), max l∈[L] M (l) = O(HSA + M D ), d ′ = O(d D ), ∥θ∥ = O(GH + F D ).Step 3.3: Update µ τ (a|s τ ).First, one transformer can be constructed to update L old to L new in h d 2τ +1 . In particular, we can haveQ h,s h 2t ′ =           v 2t ′ -1 τ -|t ′ -1 -τ | 1 t ′ 1 0 e h ′ 1           , Q h,s h 2t ′ +1 =            v 2t ′ +1 -1 τ -|t ′ -τ | 1 t ′ + 1 1 s t ′ e h ′ +1 1            , K h,s h 2t ′ =           1 1 -τ -1 t ′ e s e h+1 -1           , K h,s h 2t ′ +1 =           1 1 -τ -1 t ′ + 1 e s e h+1 -1           , V h,s h 2τ +1 = -(2τ + 1) • L old (h, s, •).With ReLU activation, this construction leads to thath 2t ′ = 0, ∀t ′ ≤ t; h 2t ′ +1 = L old (h(τ ), s τ , •) if t ′ = τ 0 otherwise .With a similar A-head transformer, we can add ω n τ • lτ n τ (s τ , a τ ) to L old (h(τ ), s τ , a τ ) and thus obtain the new values L new (h(τ ), s τ , •). Furthermore, a one-head transformer can obtainh 2τ +1 = η n τ ω n τ • L new (h(τ ), s τ , •)Finally, with another softmax MLP layer, we can obtain µ τ new (•|s τ ). The required transformer can be summarized asL = O(1), max l∈[L] M (l) = O(HS + A), d ′ = O(A), ∥θ∥ = O(GH 2 S). G.3.6 Proof of Step 4: Obtain µ h+1 (•|s h+1 )This step is essentially the same as Step 6 in realizing VI-ULCB, which can be completed with a transformer that L = 1, M (1) = HS, ∥θ∥ = O(HS).Proof of Theorem 3.5. We use the decomposition thatE M ∼Λ,D∼P Alg θ M V †,ν M (s 1 ) -V μ, † M (s 1 ) = E M ∼Λ,D∼P Alg 0 M V †,ν M (s 1 ) -V μ, † M (s 1 ) V μ, † M (s 1 ) = O   H • t∈[T ],s∈S E α TV µ t α , µ t β |D t-1 + , s + TV ν t α , ν t β |D t-1 -, s   = O   T HS √ ε +,real + T HS √ ε -,real + T HS log N Θ+ T S/δ N + T HS log N Θ-T S/δ N   ,and similarly,E M ∼Λ,D∼P Alg θ M V †,ν M (s 1 ) -E M ∼Λ,D∼P Alg 0 M V †,ν M (s 1 ) = O   T HS √ ε +,real + T HS √ ε -,real + T HS log N Θ+ T S/δ N + T HS log N Θ-T S/δ N   .With Theorem 3.4 providing that ε +,real = ε -,real = 0, combining the above terms completes the proof of the regret bound. The bound on the covering number, i.e., log(N Θ+ ) and log(N Θ-) can be obtained via Lemma I.4.In the following, we provide the proof for the Lemma 3.6, which plays a key role in the above proof of the overall performance.Proof of Lemma 3.6. It holds thatE D∼P Alg α M V μα, † M (s 1 ) -E D∼P Alg β M V μβ , † M (s 1 ) = E D∼P Alg α M V μα, † M (s 1 ) -V μβ , † M (s 1 ) :=(term I) + E D∼P Alg α M V μβ , † M (s 1 ) -E D∼P Alg β M V μβ , † M (s 1 ) :=(term II) . Denoting f (D H ) = h∈[H] r h , we can obtain that V μα, † M (s 1 ) -V μβ , † M (s 1 ) (a) ≤ V μα,ν †(μβ ) M (s 1 ) -V μβ ,ν † (μ β ) M (s 1 ) (b) = 1 G g∈[G] V μg α ,ν † (μ β ) M (s 1 ) -V μg β ,ν † (μ β ) M (s 1 ) ≤ 1 G g∈[G] h∈[H] E D 1:h ∼P μg α ,ν † ( μβ ) M ,D h+1:H ∼P μg β ,ν † ( μβ ) M f (D H ) - 1 G g∈[G] h∈[H] E D 1:h-1 ∼P μg α ,ν † ( μβ ) M ,D h:H ∼P μg β ,ν † ( μβ ) M f (D H ) (c) ≤ 2H G g∈[G] h∈[H] E D 1:h-1 ∼P μg α ,ν † ( μβ ) M ,s h TV μg,h α × ν h † (μ β )(•, •|s h ), μg,h β × ν h † (μ β )(•, •|s h ) = 2H G g∈[G] h∈[H] E D 1:h-1 ∼P μg α ,ν † ( μβ ) M ,s h TV μg,h α (•|s h ), μg,h β (•|s h ) (d) = 2H G g∈[G] h∈[H] E D 1:h-1 ∼P μg α ,ν † ( μβ ) M ,s h   TV   i∈[n] α n,i µ gi,h α (•|s h ), i∈[n] α n,i µ gi,h β (•|s h )     (e) ≤ 2H G g∈[G] h∈[H] E D 1:h-1 ∼P μg α ,ν † ( μβ ) M ,s h   i∈[n] α n,i TV µ gi,h α (•|s h ), µ gi,h β (•|s h )   ≤ 2H G g∈[G] h∈[H] s∈S i∈[n] α n,i TV µ gi,h α (•|s), µ gi,h β (•|s) (f ) ≤ 2H g∈[G] h∈[H] s∈S TV µ g,h α (•|s), µ g,h β (•|s) ,where (a) is from the definition of best responses, (b) uses the notation μg to denote the output policy from Alg. 4 with the initial random sampling result to be g, (c) uses the variational representation of the TV distance, (d) uses the abbreviations n = N g,h (s h ) and g i = g h i (s h ), (e) leverages the property of TV distance, and (f) uses the fact that α n,i < 1.With the above result, we can further obtain that(term I) := E D∼P Alg α M V μα, † M (s 1 ) -V μβ , † M (s 1 ) ≤ E D∼P Alg α M   2H t∈[T ] s∈S TV µ t α (•|s), µ t β (•|s)   .Also, for term (II), denoting g(D) = V μβ , † M (s 1 ), it holds that (term II) := E D∼P Alg α M V μβ , † M (s 1 ) -E D∼P Alg β M V μβ , † M (s 1 ) = t∈[T ] E D t ∼P Alg α M ,D t+1:T ∼P Alg β M [g(D)] - t∈[T ] E D t-1 ∼P Alg α M ,D t:T ∼P Alg β M [g(D)] ≤ 2H t∈[T ] E D t-1 ∼P Alg α M ,s t TV Alg α (•, •|D t-1 , s t ), Alg β (•, •|D t-1 , s t ) ≤ 2H t∈[T ] s∈S E D t-1 ∼P Alg α M TV µ t α (•|D t-1 + , s t ), µ t β (•, •|D t-1 + , s h ) + 2H t∈[T ] s∈S E D t-1 ∼P Alg α M TV ν t α (•|D t-1 + , s), ν t β (•, •|D t-1 + , s) .Combining (term I) and (term II) concludes the proof.In the following, we characterize the covering number of algorithms induced by transformers parameterized by θ ∈ Θ d,L,M,d ′ ,F , i.e., {Alg θ : θ ∈ Θ d,L,M,d ′ ,F }. 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-based Transformer). An L-layer clipped decoder-based transformer, denoted as TF R θ (•), is a composition of L masked attention layers, each followed by an MLP layer and a clip operation: TF R θ (H) = H (L) ∈ R d×N , where H (L) is defined iteratively by takingH (0) = clip R (H) ∈ R d×N and for l ∈ [L], H (l) = clip R MLP θ (l) mlp Attn θ (l) mattn H (l-1) ∈ R d×N , where clip R (H) = [proj ∥h∥2≤R (h i ) : i ∈ [N ]].Furthermore, for ζ ∈ (0, 1], we define the following ζ-biased algorithm induced by transformer TF R θ (H) asEQUATIONAB denoting an all-one vector of dimension AB, which introduces a lower bound ζ/AB for the probably each pair (a, b) ∈ A × B to be sampled.= [h 1 , • • • , h N ] ∈ R d×N , we denote ∥H∥ 2,∞ := max i∈[N ] ∥h i ∥ 2 .Proposition I.2 (Modified from Proposition J.1 in Bai et al. [7] ). For anyθ 1 , θ 2 ∈ Θ d,L,M,d ′ ,F , we have ∥TF R θ1 (H) -TF R θ2 (H)∥ 2,∞ ≤ LF L-1 H F Θ ∥θ 1 -θ 2 ∥,whereF Θ := F R(2 + F R 2 + F 3 R 2 ) and F H := (1 + F 2 )(1 + F 2 R 3 ).Proof. This proposition can be obtained similarly as Proposition J.1 in Bai et al. [7] with the following Lemma I.3 in the place of Lemma J.1 in Bai et al. [7] .Lemma I.3 (Modified from Lemma J.1 in Bai et al. [7] ). For a single MLP layer θ mlp = (W 1 , W 2 ), we introduce its norm∥θ mlp ∥ = ∥W 1 ∥ op + ∥W 2 ∥ op .For any fixed hidden dimension D ′ , we considerΘ mlp,F := {θ mlp : ∥θ mlp ∥ ≤ F }.Then, for anyH ∈ H R , θ mlp ∈ Θ mlp,F , it holds that MLP θmlp (H) is 2F R-Lipschitz in θ mlp and (1 + F 2 )-Lipschitz in H.Proof. It holds that∥MLP θmlp (H) -MLP θ ′ mlp (H)∥ 2,∞ = max i ∥W 2 σ(W 1 h i ) -W ′ 2 σ(W ′ 1 h i )∥ 2 ≤ max i ∥W 2 -W ′ 2 ∥ op ∥σ(W ′ 1 h i )∥ 2 + ∥W ′ 2 ∥ op ∥σ(W 1 h i ) -σ(W ′ 1 h i )∥ 2 (a) ≤ max i ∥W 2 -W ′ 2 ∥ op max{1, ∥W 1 h i ∥ 2 } + ∥W ′ 2 ∥ op ∥W 1 h i -W ′ 1 h i ∥ 2 ≤ (1 + F R)∥W 2 -W ′ 2 ∥ op + F R∥W 1 -W ′ 1 ∥ 2 . Inequality (a) is from that ∥σ r (x)∥ 2 ≤ ∥x∥ 2 , ∥σ s (x)∥ 2 ≤ 1, and ∥σ r (x) -σ r (y)∥ 2 ≤ ∥x -y∥ 2 , ∥σ s (x) -σ s (y)∥ 2 ≤ ∥x -y∥ 2 ,where the last result on the Lipschitzness of softmax is adopted from Gao and Pavel [25] .Similarly, we can obtain that∥MLP θmlp (H) -MLP θmlp (H ′ )∥ 2,∞ = max i ∥h i + W 1 σ(W 2 h i ) -h ′ i -W 1 σ(W 2 h ′ i )∥ ≤ ∥H -H ′ ∥ 2,∞ + ∥W 1 ∥ op max i ∥σ(W 2 h i ) -σ(W 2 h ′ i )∥ 2 ≤ ∥H -H ′ ∥ 2,∞ + ∥W 1 ∥ op max i ∥W 2 h i -W 2 h ′ i ∥ 2 ≤ ∥H -H ′ ∥ 2,∞ + F 2 ∥H -H ′ ∥ 2,∞ ,which concludes the proof.Lemma I.4 (Modified from Lemma 16 in Lin et al. [38] ). For the space of transformers {TF R θ : θ ∈ Θ d,L,M,d ′ ,F }, the covering number of the induced algorithms {Algζ θ : θ ∈ Θ d,L,M,d ′ ,F } satisfies that log N Θ d,L,M,d ′ ,F (ρ) = O L 2 d(M d + d ′ ) log 1 + max{F, R, L} ζρ .Proof. First, similar to Lemma 16 in Lin et al. [38] , we can use Example 5.8 in Wainwright [61] to obtain that the δ-covering number of the ball B ∥•∥ (F ) with radius F under norm ∥ • ∥, i.e., B ∥•∥ (F ) = {θ : ∥θ∥ ≤ F }, can be bounded aslog N (δ; B ∥•∥ (F ), ∥ • ∥) ≤ L(3M d 2 + 2dd ′ ) log(1 + 2F/δ).Recall that the projection operation to a probability simplex is Lipschitz continuous, i.e., ∥proj ∆ (x)proj ∆ (y)∥ 2 ≤ ∥x -y∥ 2 .Then, we can see that there exists a subsetΘ ⊂ Θ d,L,M,d ′ ,F with size log |Θ d,L,M,d ′ ,F | ≤ L(3M d 2 + 2dd ′ ) log(1 + 2F/δ) such that for any θ ∈ Θ d,L,M,d ′ ,F , there exists θ ∈ Θ with log Alg ζ θ (•, •|D t-1 , s) -log Alg ζ θ (•, •|D t-1 , s) ∞ ≤ AB ζ Alg ζ θ (•, •|D t-1 , s) -Alg ζ θ (•, •|D t-1 , s) ∞ ≤ AB ζ TF R θ (H) -TF R θ (H) 2,∞ ≤ AB ζ • LF L-1 H F Θ • ∥θ -θ∥ ≤ AB ζ LF L-1 H F Θ δ. Let δ = ζρ ABLF L-1 H FΘ , we can obtain ∥ log Alg ζ θ (•, •|D t-1 , s) -log Alg ζ θ (•, •|D t-1 , s)∥ ∞ ≤ ρ, which proves that log(N Θ d,L,M,d ′ ,F (ρ)) ≤ L(3M d 2 + 2dd ′ ) log(1 + 2F/δ) = L(3M d 2 + 2dd ′ ) log 1 + ABLF L-1 H F Θ ζρ = O L(3M d 2 + 2dd ′ ) log 1 + ABL(1 + F 2 ) L-1 (1 + F 2 R 3 ) L-1 F R(2 + F R 2 + F 3 R 2 ) ζρ = O L 2 (M d 2 + dd ′ ) log 1 + max{A, B, F, R, L} ζρ ,which concludes the proof.From the transformer construction in the proofs for Theorems 3.4 and 4. Alg ζ θ * (a, b|D t-1 , s) = log E D∼P Alg 0 Λ Alg 0 (a, b|D t-1 , s) Alg θ * (a, b|D t-1 , s) • Alg θ * (a, b|D t-1 , s) Alg ζ θ * (a, b|D t-1 , s) = log E D∼P Alg 0 Λ Alg θ * (a, b|D t-1 , s) (1 -ζ) • Alg θ * (a, b|D t-1 , s) + ζ/(AB) ≤ log 1 (1 -ζ) + ζ/(AB) ≤ log 1 1 -ζ .• 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 is recorded as "a 1 , r 1 , • • • , a t , r t ", and that of the min-player as "b 1 , 1 -r 1 , • • • , b t , 1 -r t ",• The VI-ULCB algorithm for the centralized setting. In the centralized setting, both players jointly follow the VI-ULCB algorithm [8] to collect pre-training data. Up to time step t, the trajectory is recorded as "s 1 , a 1 , b 1 , r 1 , 1 -r 1 , • • • , s t , a t , b t , r t , 1 -r t ".We note that the decimal digits of the rewards are limited to two to facilitate tokenization, while 1 -r i instead of -r i is adopted for the min-player to avoid the additional complexity of negative numbers.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 3 for simplicity. The 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 4 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, we use one Nvidia 6000 Ada to train the transformer with a batch size of 32, trained for 100 epochs, and we set the learning rate as 5 × 10 -4 . The experimental codes are available at https://github.com/ShenGroup/ICGP.To test the performance of the pre-trained transformer (in particular, how well it approximates EXP3 and VI-ULCB), we adopt the measurement of Nash equilibrium gap. In particular, for either the transformer induced policy or EXP3, we denote the max-player's policy at time step t as µ t , and the min-player's policy at time step t as ν t . Furthermore, the average policy is computed asμt = 1 t τ ∈[t] µ t , νt = 1 t τ ∈[t] ν t .The NE gap at step t is computed asmax a∈A Rν t -min b∈B (μ t ) ⊤ R.For VI-ULCB, the process is similar except that µ t and ν t 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 at each step are plotted in Fig. 2 .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, confidence intervals, or statistical significance tests, at 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).The covering number NΘ + in Theorem 3.3 (and also the later Theorem C.3) is not concretely discussed in the main paper to ease the presentation. A detailed illustration is provided in Appendix I.Another common method to find CCEs is through linear programming (LP). It will be an interesting direction to investigate whether transformers can be LP solvers, which is however out of the scope of this paper.https://github.com/karpathy/minGPT 


Decision: 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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.
questions: questions: 1) Do you believe that this implementation might have different results given a different pre-training dataset (produced from a different algorithm)?

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?
limitations: 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.
paper_summary: paper_summary: The authors built on the recent work of Lin et. al 2023, extending their ICLR framework so that instead of being for one agent, it is for multi-agent systems; at the same time, they also analyze and provide evidence of "ICGP" (in-context game-playing) capabilities in transformers.

The paper analyzes zero-sum Markov games for two players and explores learning the Nash Equilibrium. In these games, two setups are studied: one of decentralized learning (where the Nash Equilibrium must be reached without each player observing the opponent's actions) and another of centralized learning (where a transformer controls the actions of both players).

The authors find important theoretical results related to transformers in decision-making, e.g., that pre-trained transformers can realize both model-based and model-free designs, and the in-context learning capability of transformers in playing normal-form games
strength_weakness: strength_weakness: 1. **Soudness of the claims**

   My concerns about the paper relate to whether this theoretical framework might struggle with generalization and performance in more complex games. In this section, I provide some examples of limitations that suggest this possibility. I'm concerned that it may excel in controlled environments but not in more complex scenarios, which are typical in the multi-agent literature.

   Also, please note that the improved performance of transformers trained with 20 games compared to those trained with 10 (Lines 336-341) suggests a heavy dependence on the volume of training data. Thus, I'm also highlighting some potential problems related to this aspect. 

   a) **Theoretical grounding**

      a1) **Decentralized learning scenario**

   In the decentralized setting, my primary concerns revolve around the diversity and representativeness of the training data, overly optimistic assumptions about model approximation capabilities, and potential issues with the suitability of transformer outputs for generating valid action probabilities.

* (Lines 157-170) If the data collected through $Alg+,0$ and $Alg−,0$ only captures a limited range of strategic interactions (e.g., typical or frequent scenarios but not edge cases or unusual strategies) the training data might lack the necessary diversity, leading to overfitting/lack of robustness. If the data does not sufficiently cover the state-action space, the expected log probability of correct actions given the state, as modeled by the transformer, may not reflect true gameplay dynamics and $\mathbb{E}\left[\log P(\text{actual action} \mid \text{state})\right]$ may overestimate actual performance.
* (Lines 200-202) Take into account that with Assumption "3.2. Decentralized Approximate Realizability" you assume that the true data-generating distribution ($Alg_0^+$) can be closely approximated by the learned model ($Alg_\theta^+$). This assumption may not hold if the real complexity of strategies in the environment cannot be captured by the model's architecture or training data -- causing the models have generalization issues.
* (Lines 195-190) Potential convergence/generalization problems with the learning algorithm if the covering number $\Theta$ is underestimated. The clipping operation (Lines 936-938), which is designed to maintain the norm of activations within bounds, can significantly impact the parameter sensitivity and the gradient flow during backpropagation. So, if $\Theta$ is underestimated, it might not sufficiently account for the reduced effective parameter space available for optimization, possibly leading to convergence on local minima that do not generalize well
* (Lines 182-185) The use of linear extraction mappings followed by a projection to the probability simplex to determine action probabilities assumes that the transformer’s outputs can be linearly mapped to form valid probability distributions. Buuut, if the transformer outputs are not suitable for this kind of linear transformation due to scale, bias, or other distributional issues, the resulting action probabilities may not be valid or optimal --> leading to suboptimal decisions and erratic behavior, especially in complex games.

   a2) **Centralized learning scenario**

   For the centralized learning scenario, I want to provide feedback on some specific concerns related to computational demands, dependency on precise model and algorithm alignment, and assumptions about uniform sampling that may not adequately capture the complexity of strategic behaviors across varied game states

* (Lines 307-309) The required dimensions and mappings such as $d⪅HS^2AB,L⪅GHSd⪅HS^2AB,L⪅GHS$ etc., indicate a high computational complexity and dependency on specific game parameters (like $S,A,B,G,HS,A,B,G,H$). As a result, this could make the model computationally expensive and potentially overfit to specific types of game environments.
* (Lines 307-309) This performance requirement: $Algθ(⋅,⋅∣Dt−1,s)=AlgVI−ULCB(⋅,⋅∣Dt−1,s)Algθ​(⋅,⋅∣Dt−1​,s)=AlgVI−ULCB​(⋅,⋅∣Dt−1​,s)$ assumes an ideal alignment between the transformer’s output and the algorithm’s requirements; note that any deviation in this alignment due to model approximation errors or misestimations in the transformer's training could lead to significant performance drops...
* (Lines 321-322) Note that the assumption that $\hat{\mu}\$ and $\hat{\nu}\$ are uniformly sampled and provide an effective representation of strategic options in every game state might not hold if some strategies are inherently more complex or contextually sensitive than others.
questions: questions: * Given that the decentralized setup involves collecting offline trajectories using different algorithms for max- and min-players (Section "3.1 Supervised Pre-training Results") -- how do you ensure that the diversity and distributional properties of the training data do not adversely affect the learning outcomes?
* The clipping operation $clip_R$ is defined to constrain the norm of each vector (Lines 936 - 938). How does this norm constraint affect the learning dynamics, particularly in terms of gradient propagation and stability during backpropagation? This seems to be important as it directly affects the model's ability to learn and fine-tune strategies based on gameplay experience.
* In Appendix G.3, you detail the use of embedding and extraction mappings within the transformer architecture for implementing V-learning (Lines 810-819). These mappings essentially allow the transformer to understand and manipulate game states and decisions effectively. Are there specific state spaces where these mappings prove particularly beneficial/limited?

Just out of curiosity:
* Have you observed any sudden shifts in learning effectiveness or strategy adaptation in your decentralized learning models, based on the results from "The Mechanistic Basis of Data Dependence and Abrupt Learning in an In-Context Classification Task" by Gautam Reddy (2023)?
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: There are some questions:

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?

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.

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.
questions: questions: See Weaknesses.
limitations: limitations: The authors have discussed the limitations and future directions of the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

2. 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.

3. 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.
questions: 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?

2. 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?

3. Could you discuss more about the broader impacts and potential limitations of your work?
limitations: limitations: Yes, the authors provide limitations in the Appendix.

Comments: title: I am happy with the author responses, and they have addressed my concerns.
comment: It is a great pleasure to hear the recognition that this work brings valuable contributions to communities of both MARL and ICL. Thank you for reviewing this work and providing the detailed comments! We will carefully incorporate your suggestions into the revised paper.
Thanks for your detailed rebuttal. I am happy with the clarifications the authors provided. As Reviewer h1zf mentioned, I want to highlight that this work is not only important for the MARL community but also for the broader research community focused on advancing our understanding of ICL. Congratulations on this great work.
Thank you for recognizing the contributions of this work! We will carefully incorporate your helpful suggestions into the revised paper.
It is our pleasure to hear that the responses addressed your concerns. The new experiment will be described with full details in the revised paper. Thank you for recognizing the contributions of this work!
I am happy with the author responses and I believe the authors have addressed my concerns.
I would like to see the details of the new experiment expanded upon in the revised paper.
Overall I believe this work will be valuable to the greater MARL community.
Thanks for your responses. I believe my concerns can be easily addressed in the revision. I’m happy to increase my score.
We are glad to hear that our response addressed your concerns. Thank you for recognizing the contributions of this work!
Thanks for the authors' responses, and my concerns have been addressed. So, I am happy to increase my score.