Posterior Sampling for Competitive RL: Function Approximation and Partial Observation
Authors: Shuang Qiu
Ziyu Dai
Han Zhong
Zhaoran Wang
Zhuoran Yang
Tong Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Markov game
Partial observation
Function approximation
Posterior sampling
Reinforcement Learning

Abstract: This paper investigates posterior sampling algorithms for competitive reinforcement learning (RL) in the context of general function approximations. Focusing on zero-sum Markov games (MGs) under two critical settings, namely self-play and adversarial learning, we first propose the self-play and adversarial generalized eluder coefficient (GEC) as complexity measures for function approximation, capturing the exploration-exploitation trade-off in MGs. Based on self-play GEC, we propose a model-based self-play posterior sampling method to control both players to learn Nash equilibrium, which can successfully handle the partial observability of states. Furthermore, we identify a set of partially observable MG models fitting MG learning with the adversarial policies of the opponent. Incorporating the adversarial GEC, we propose a model-based posterior sampling method for learning adversarial MG with potential partial observability. We further provide low regret bounds for proposed algorithms that can scale sublinearly with the proposed GEC and the number of episodes $T$. To the best of our knowledge, we for the first time develop generic model-based posterior sampling algorithms for competitive RL that can be applied to a majority of tractable zero-sum MG classes in both fully observable and partially observable MGs with self-play and adversarial learning.

Posterior Sampling for Competitive RL: Function Approximation and Partial Observation
Shuang Qiu" HKUST
Ziyu Dai" New York University zd23650cims nyu. edu
Han Zhong
Peking University
masqiuOust.
hanzhong@stu, pku, edu.edu.com en
Zhaoran Wang
Zhuoran Yang
Tong Zhang HKUST
Northwestern University
Yale University
zhaoranvang@gmiil.coom
Mauorynn.yag@yallee edu
tongzhang@ust. hk
Abstract
This paper investigates posterior sampling algorithms for competitive reinforce- ment learning (RL) in the context of general function approximations, Focusing on zero-sum Markov games (MGs) under two critical settings, namely self-play and adversarial learning, we first propose the self self-play and adversarial generalized eluder coefficient (GEC) as complexity measures for function approximation, cap- turing the iewoorattio-eeploiatttti
trade-off in MGs. Based on self-play GEC, we propose moodel-based self-play posterior sampling method control both players to learn Nash equilibrium, which can successfully handle the partial observability of states. Furthermore, we identify a set of partially observable MG models fitting MG learning with the adversarial policies of the opponent. Incorporating the ad- versarial GEC, we propose a model-based posterior sampling method for learning adversarial MG with potential partial observability. We further provide low regret bounds for proposed algorithms that can scale sublinearly with the proposed GEC and the number of episodes T'. To the best of our knowledge, develop generic model- bbseed posterior sampling algorithms for competitive RL that can be applied to majority of tractable zero-sum MG classes in both fully observable and partially observable MGs with self-play and adversarial learning.
for the first time
Introduction
Multi-agen reinforcement learning (MARL) tackles sequential Aecision-making problems where multiple players sinultaneously interact with the shared environment, affecting each other's behavior in coupled manner. Under competitive reinforcement learning (RL. setting, the goal of each player to maximize (resp. minimize) her own cumulative gains (resp. losses) the presence of other agents. Recent years have been tremendous practical successes of MARL in variety of application domains, such as autonomous driving [56], Go [58], StarCraft [65], Dota2 [8] and Poker [10]. These successes attributed to advanced MARL algorithms that can coordinate multiple players by exploiting potentially partial observations
latent states and employ powerful function approximators (neural networks in particular), which empower tackle practical problems with large state spaces.
Apart from the empirical success, there is growing body of literature establishing theoretical guarantees for Markov games (MGs) [57] - standard framework for describing the dynamics of competitive RI. In particular, [71, 16, 33, 28, 77] extend the works in single-agent reinforcement
"Equal Contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

learning (RL) with function approximation [29, 60, 67, 34, 5, 11, 19, 21] by developing sample- efficient algorithms that are capable to solve two-player zero-sum MGs with function approximation. In addition, as opposed to the aforementioned literature on MGs assuming the state of players is fully observable, the recent work [41] analyze Markov games under partial observability [41], i.e., the complete information about underlying states is lacking. However, most of the existing works are built upon the principle of "optimism in the face of uncertainty" (OFU) [38] for exploration. Furthermore, from practical perspective, achieving optimism often requires explicit construction of bonus functions, which are often designed in a model-specific fashion and computationally challenging implement.
Another promising strand of exploration techniques is based on posterior sampling, which is shown by previous works on bandits [12] and RL [48] to perform better than OFU-based algorithms. Meanwhile, posterior sampling methods, unlike OFU-based algorithms [31, 21] that need to solve complex optimization problems to achieve optimism, can be efficiently implemented by ensemble approximations [48, 44, 17, 46] and stochastic gradient Langevin dynamics (SGLDD [70]. Despite the superiority of posterior sampling, its theoretical understanding in MARL remains limited. The only exception is [73], which proposes a model-free posterior sampling algorithm for zero-sum MGs with general function approximation. However, [73] cannot capture some common tractable competitive RL models with a model--bsed nature, such as linear mixture MGs [16] and low witness rank MGs [28]. Moreover, their result is restricted to the fully observable MGs without handling the partial observability of the players' states. Therefore, we raise the following question:
Can we design provably sample-eficcient posterior sampling algorithms for competitive RI. with even partial observations under general
generalfunction function approximation?
Concretely, the above question poses three major challenges. First, despite the success of the OFU principle in partially observable Markov games (POMGs), it remains elusive how to incorporate the partial observations into the posterior sampling framework under a MARL setting with provably efficient exploration. Second, it is also unclear whether there is generic function approximation condition that can cover more known classes in both full and partial observable MARL and is meanwhile compatible with the posterior sampling framework. Third, with the partial observation and function approximation, it is challenging to explore how we can solve MGs under the setups of self- play, where all players can be coordinated together, and adversarial learning, where the opponents" policies are adversarial and uncontrollable by the learner. Our work takes an initial step towards tackling such challenges by concentrating on the typical competitive RL scenario, the two-player zero-sum MG, and proposing statistically efficient posterior sampling algorithms under function approximation that can solve both self-play and adversarial MGs with full and partial observations.
Contributions. Our contributions are four-fold: (1) We first propose the two generalized eluder coefficient (GEC) as the complexity measure for the competitive RL with function approximation, namely self-play GEC and adversarial GEC, that captures the wwwoorrttioonxpoiitatttttooooeet many existing MGs, including linear MGs, linear mixture MGs, weakly revealing POMGs, decodable POMGs. The proposed measures also generalize the recently developed GEC condition [83] from single-agent RL to MARL, suitably adjusting the exploration policy particularly for the adversarial setting, (2) Incorporating the proposed self-play GEC for general function approximation, we propose a model-based posterior sampling algorithm with self-play to learn the Nash equilibrium (NE), which successfully handles the partial observability of states along with full observable setup by carefully designed likelihood functions. (3) We identify POMG models aligned with the form of the adversarial GEC, which fit MG learning with adversarially-varyy further propose a model-basee posterior sampling algorithm for adversarial learning with general function approximation. (4) We prove regret bounds for our proposed algorithms that scale sublincarly with the number of episodes T, the corresponding GEC deEC. and a quantity measuring the coverage of the optimal model by the initial model sampling distribution. To the best of our knowledge, present the first model-based posterior sampling approaches to sample-efficieme function approximation, handling partial observability in both self-play and adversarial settings.
tradeoff in
policies of the opponent. We
learn MGs with
Related Works. There is a large body of literature studying MGs, especially zero-sum MGs. In the self-play setting, many papers have focused on solving approximate NE in tabular zero-sum MGs [6, 7, 71, 51, 43], zero-sum MGs with linear function approximation [71, 16), zero-sum MGs with low-rank structures [50, 79, 47], and zero-sum MGs with general function approximation [33, 28, 73]. On the other hand, there are also several recent papers focusing on the adversarial setting
2

---

[71, 61, 28] aim to learn the Nash value under the setting of unrevealed opponent's 's policies, where the adversarial policies of the opponent are unobservable. In addition, another line of adversarial MGs concentrates on revealed policy setting, where the opponent's 's full policy can be observed, leading to efficiently learning a sublinear regret comparing against the best policy hindsight. Particularly, [42] and [77] develop efficient algorithms in tabular and function approximation settings, respectively. Our approach focuses on the unrevealed policy setting, which is considered to be more practical setup. There are also works studying MGs from various aspects [59, 32, 45, 84, 35, 20, 52, 9, 82, 18, 72, 74], such as multi-player general-sum MGs, reward-free MGs, MGs with delayed feedback, and offline MGs, which are beyond the scope of our work. Most of the aforementioned works follow the OFU principle and differ from our posterior sampling methods. The recent work [73] proposes a model-free posterior sampling algorithm for two-player zero-sum MGs but is limited to the self-play setting with fully observable states. Moreover, their work requires a strong Bellman completeness assumption that is restrictive compared only requiring realizability in our work, mainly due the monotonicity, meaning that adding a new function to the function class may violate it. Many model- based models like linear mixture MGs [16] and low witness rank MGs [28] are not Bellman-complete. so they cannot be captured by [73]. Without the completeness assumption, our model-based posterior sampling approaches can solve a rich class of tractable MGs, including linear mixture MGs, low witness rank MGs [28], and even POMGs, tackling both self-play and adversarial learning settings.
Our work is related to line of research on posterior sampling methods in RL. For Ainll-ageet RL, most existing works such as [54] analyze the Bayesian regret bound. There are also some works [4, 53, 76] focusing on the frequentist (worst-case) regret bound. Our work is more closely related to the recently developed feel-good Thompson sampling technique proposed by [81] for the frequentist regret bound, and its extension to single-agent RL [19, 2, 3] and two-player zero-sum MGs [73].
Our work is also closely related to the line of research on function approximation in RL. Such a line of works proposes algorithms for efficient policy learning under diverse function approximation classes, spanning from linear Markov decision processes (MDPs) [34], linear mixture MDPs [5, 85) to nonlinear and general function classes, including, for instance, generalized linear MDPs [69]. kemel and neural function classes [75], bounded eluder dimension [49, 68]. Bellman rank [29], witness rank [60]. bellman eluder dimension [31], bilinear [21].
coefficient [24, 14),
decoupling coefficient [19]. admissible Bellman characterization [15], and GEC [83] classes.
The research on partial observability in RL [27] is closely related to our work. The works [36, 30] show that learning history-dependent policies generally can cause an exponential sample complexity. Thus, many recent works focus analyzing tractable subclasses of partially observable Markov decision processes (POMDPs), which includes weakly revealing POMDPs [30, 39J, observable POMDPs [26. 25], decodable POMDPs [22, 23], low-rank POMDPs[66], regular PSR [78), PO- bilinear class [63], latent MDP with sufficient tests [37], B-stable PSR [13], well-conditioned PSR [40], POMDPs with deterministic transition kernels [30, 62], and GEC [83]. Nevertheless, in contrast to our work which focuses on the two-player competitive setting with partial observation, these papers merely consider the single-agent setting. The recent research [41] further generalizes weakly revealing POMDPs to its multi-agent counterpart, weakly revealing POMGs, in a general-sum multi- player setting based on the OFU principle. But when specialized the two-player case, our work proposes a general function class that can subsume the class of weakly revealing POMGs as a special case. It would be intriguing to generalize our framework to the general-sum settings in the future.
Notations. We denote by (L(PII)= = Ex- (oog)lll((((())/((((()))) the KL divergence and Di (P.Q)= Expr( (Vdppv/) - 1)2 the Hellinger distance. We denote by Ax the set of all distributions over X' and (2) the uniform distribution over X., We let x A y be min (2. y)-
2 Problem Setup
We introduce the basic concept of the two-player zero-sum Markov game (MG), function approxi- mation, and the new complexity conditions for function approximation. Concretely, we study two typical classes of MGs, i.e., fully observable MGs and partially observable MGs, as defined below.
Fully Observable Markoy Game. We consider an episodic two-player zero-sum fully observable Markov game (FOMG) specified by a tuple A, rr H), where S is the state space, A and
FFMG is typically referred to MG by most literature. We adopt FOMG to differentiate it from POMG.
3

---

B are the action spaces of Players and 2 respectively, H is the length of the episode. We denote by P. := {P the transition kernel with (s s, a. b) specifying the probability (density) of transitioning from state to state s' given Players and 2's actions E A and & E B at step h. We denote the reward function as r = {ra) with rh S x A B - [0, 1] being the reward received by players at step h. We define π = { and v = {vn)n=] h=1 as Markovian policies for Players and 2, i.e., TA (a]s) and 2/ (b[s) are the probability of taking action a and b conditioned on the current state 8 at step h. Without loss of generality, we assume the initial state 81 is fixed for each episode. We consider realistic setting where the transition kernel IP is unknown and thereby needs to be approximated using the collected data.
Partially Observable Markov Game This paper further studies an episodic zero-sum partially observable Markov game (POMG), which is distinet from the FOMG setup in that the state s is not directly observable. In particular, a POMG is represented by a tuple AS,A, B, O, P, O, U, r, H), where S, A. B, H. and P are similarly the state and action spaces, the episode length, and the transition kernel. Here (1(+) denotes the initial state distribution. We denote by 0 == fO, 1== the emission kernel so that (ols) is the probability of having a partial observation E at state with O being the observation space. Since we only have an observation of state, the reward function is defined as r == [r with vn (o, a, b) E [0. 1] depending on actions a, b and the observation o, and the policies for players are defined as æ = { )= and v =
where nA (T 11 o%) and 1/, (T.. 08.) is viewed as the probability of taking actions an and by depending on all histories (7
Here we let Ty == (01, (01,a1.0 a1, by . an. bz). Then, in contrast to FOMGs, the policies in POMGs are history-dependemt, defined on all prior PT"((T)) observations and actions rather than the current state 8. We define Ph (TT) = Ss- MI (s1)
Wh==[0ae (on (8t>) T (bw -1y ore (bw Thr-1: Oh (hr which is the joint distribution of Tr under the policy pair (T, v)) Removing policies in P..." we define h--1
Ore. by [Oy dsss:
fS* f4 (81) I [Ozz (ow- |sw PT (S8 88', aw,, by O (on (sp) (1sss- We assume that the parameters 0 == (u1, P, O) are unknown and thus Py, is unknown as well, which should be approximated in algorithms via online interactions.
the function (T.)))
Online Interaction with the Environment. In POMGs, at step h of episode t of the interaction, players take actions af, ~ क (-IT of)) and bf, 1/ bf. depending on their action and observation histories, receiving a reward ra a b).) and transitions from the latent state st, to $/+1 ~ (- s/, o/.- b/,) with an observation o/41 ~ 0n(-Isf generated. When the underlying state %% is observable and the policies become Markovian, we have actions oj ~ TH. (ef)) and bJ. o (sf) and the reward (sh ah, b/,)) Then, it reduces to the interaction process under the FOMG setting.
Value F Function, Best Response, and Nash Equilibrium. To characterize the learning objective and the performance of the algorithms, we define the value function as the expected cumulative rewards under the policy pair (xt, v) starting from the initial step h = 1. For FOMGs, we define the value function V*."" ;= E ===1 Th an. bn) $1, n., M, P.P., where the expectation is taken over all the randomness induced by π, U, and IP. For POMG, we define the value function as V = BI N=1 (o(o,, on, on,b,)) bn) |T, 0), with the expectation taken for т, V. and 8.
H
Our work studies the competitive setting of RL, where Player (max-player) aims to maximize the value function V=." while Player 2 (min-player) aims to minimize it. With the defined value function, given a policy pair (T, we define their best responses respectively as br(z)) E arg min, V and br(v) E arg max V*. Then, we say a policy pair (T"", ) is a Nash equilibrium (NE) if
V max min V = min max VT."
Thus, it always holds that n² br(v") and 1/ br (rr)) ). For abbreviation, we denote V V V = min, V=." and V max, Va, which implies V = V=*,* V*."" for NE (I v²). Moreover, we define the policy pair (IT, 1/) as an e-approximate NE if it satisfies V V < E.
Function Approximation. Since the environment is unknown to players, the model-based RL setting requires us to learn the true model of the environment, f", via (general) function approximation. We use the functions f lying in general model function class F to approximate the environment. We make a standard realizability assumption on the relationship between the model class and the true model.
Assumption 1 (Realizabilitty) For model class F. the true model f satisfies F.
4

---

In our work, the true model f represents the transition kernel P for the FOMG and 0 for the POMG. For any f E F. we let , and , = ( f, D2) be the models under the approximation function and V the value function associated with f. For POMGs, we denote P n. and P f.h as P and f.h
Pt. under the model f-
MGs with Self-Play and Adversarial Learning. Our work investigates two important MG setups for competitive RL, which are the self-play setting and the adversarial setting. In the self-play setting, the learner can control both players together to execute the proposed algorithms learn an approximate NE. Therefore, our objective is to design sample-efficient algorithms to generate a sequence of policy pairs {(T', v²) in T episodes such that the following regret can be minimized,
(T) =1= [V 1i="-V -V.
In the adversarial setting, we can no longer coordinate both players, and only single player is controllable. Under such a circumstance, the opponent plays arbitrary and even adversarial policies. Wlog, suppose that the main player is the max- max-player with the policies (r'} generated by a carefully designed algorithm and the opponent is min-player with arbitrary policies {v'}T= The objective of the algorithm is to learn policies { } to maximize the overall cumulative rewards in the presence of an adversary. To measure the performance of algorithms, we define the following regret for the adversarial setting by comparing the learned value against the Nash value, i.e.,
Ji=1-
Regad adv (T) = Ei= (V-
V
3 Model-Based Posterior Sampling for the Self-Play Setting
We propose algorithms aiming to generate sequence of policy pairs {(T','')] ,²)][== by controlling the learning process of both players such that the regret Reg (T) is small. Such a regret can be decomposed into two parts, namely ΣT [VV- V "] and
- VV-J. which inspires our to design algorithms for learning {= and == separately by targeting at minimizing these two parts respectively. Due to the symmetric structure of such a game learning problem, we propose the algorithm to learn {x (= as summarized in Algorithm 1. The algorithm for learning { can be proposed in a symmetric way in Algorithm 3, which is deferred to Appendix A. Our proposed algorithm features an integration of the model-based posterior sampling and the exploiter- guided self-play in multi-agent learning scenario. In Algorithm I, Player I is the main player, while Player 2 is called the exploiter, who assists the learning of the main player by exploiting her weakness.
Posterior Sampling for the Main Player. The posterior sampling constructs a posterior distribution 1²(-12"-1) over the function class F each round based on collected data and a pre-specified prior distribution (.).). where - denotes the random history up to the end of the (t 1 1-th episode. For ease of notation, hereafter, we omit Z in the posterior distribution. Most recent literature shows that adding an optimism term in the posterior distribution can lead to sample-efficient RL algorithms. Thereby, we define the distribution p²(+) over the function class JE for the main player as in Line
of Algorithm 1, which is proportional to p² (f) expl>V/ + Σ Σ (f). Here, VV₁ serves as the optimism term, and (f) is the likelihood function built upon the pre-collected data. Such a construction of p²(.) indicates that we will assign higher probability (density) to function f. which results in higher values of the combination of the optimism term and the likelihood function.
We sample a model j from the distribution p-()) over the model class and learn the policy nt for the main player such that (T² D²) is the NE of the value function under the model f in Line 4, where D is a dummy policy and only used in our theoretical analysis.
Posterior Sampling for the Exploiter. The exploiter aims to track the best response of 7' to assist learning low regret. The best response of n' generated by the exploiter is nevertheless based on value function under a different model than f Specifically, for the exploiter, we define the posterior sampling distribution (-) using an optimism term ~>17 and the summation of likelihood functions, i.e., Σ Ex= [T),), along with a prior distribution (-)), in Line 5 of Algorithm 1. The negative term- -7V;" favors a model with a low value and is thus optimistic from the exploiter's 's perspective but pessimistic for the main player. We then sample a model fe from (-) and compute the best response of x", denoted as nz, under the model f² as in Line 7.
5

---

Algorithm 1 Model-Based Posterior Sampling for Self-Play (Max-Player)
1: Input: Model class F, prior distributions p" and q², 71, and 72.
2: for f ===,, =1....,? do
3: Draw model I" ~p (-) with defining (f) p explin + E En (7)
4: Compute Te by letting (x²,v²) v²) be the NE of V
y
5: Draw model [ (-) with defining (J) (f) expl - 22
# -h= LIOI
6: Compute y² by letting y¹ be the best response of x' w.r.t. V
7: Collect data D' by executing the joint exploration policy o²
8: Define the likelihood functions {f) using the collected data D
9:
end for
10:
Return: (I),...,, )))
Data Sampling and Likelihood Function. With the learned n' and n², we define a joint exploration policy of in Line 7 of Algorithm I, by executing which we can collect a dataset Dt. We are able to further construct the likelihood functions (f))) in Line 8 using D Different game settings require specifying diverse exploration policies of and likelihood functions {L) Particularly, for the game classes mainly discussed in this work, we set of (T', =²) for both FOMGs and POMGs. In FOMGs, we let D' {(s}, a/ b/ s((+1)) where for each h [H]. the data point
(5%, aj, b/, 1)) is collected by executing a¹ to the h-th step of the game. The corresponding likelihood function is defined using the transition kernel as
[ = v log (),((1/11 8// 4/ b(,))
Furthermore, under the POMG setting, we let the dataset be D = {T)) where the data point T/ (of, a by ....... of aj. bb,) is collected by executing o² to the h-th step of the game for each h E [H). We further define the associated likelihood function as
[ = rj log P P,,
(2)
Such a construction of the likelihood function log-likelihood form can result in learning a model f well approximating the true model I" measured via the Hellinger distance.
3.1 Regret Analysis for the Self-play Setting
Our regret analysis based on a novel structural complexity condition for multi-agent RL and quantity to measure how the well the prior distributions cover the optimal model f", We first define the following condition for the self-play setting.
Definition 1 (Self-Play GEC). For any sequences of functions ft g. F,, suppose that a pair of policies (T', v²) satisfies: (a) n² = argmax, min, Vial and v² argmin, Vg. or (b) v' argmin, max, Vis" and Ne' argmax, VTT"" Denoting the joint exploration policy as at depending on Ie and for any p E (f.g) and (n², (v)) following (a) and (b), the self-play GEC deEc is defined as the minimal constant dl satisfying
ET (VT'
V3 v
S
d d EL, Eor ) 2H()HT)) eHT.
Our definition of self-play GEC is inspired by [83] for the single-agent RL. Then, it shares an analogous meaning to the single-agent GEC. Here (a", h) implies running the joint exploration policy o" to step h to collect data point ET. The LHS of the inequality is viewed as the prediction error and the RHS is the training error defined is non-dominating when e is small. The loss function and e can be problem- -pecificcc....c. We determine {(f Ex) for FOMGs with & (sh, .x) and POMGs with & = Tr respectively
loss function plus burn-in error 2H (dHT) + cHT that
POMG: 1/2 1 (VPra(es)/Prr.(G., -1)² (3)
FOMG: (B))

---

such that (oo.))(((ff.))) De "r sh: pT,,) for POMGs. ses have a small training error on a well-explored dataset, then the out-of-sample prediction error is also small, which characterizes the hardness of environment exploration.
The intuition for GEC is that if hypothe-
Since the posterior sampling steps in our algorithms depend on the initial distributions p" and g", we define the following quantity to measure how well the prior distributions p" and qº cover the optimal model f E F, which is also a multi multi-agent generalization of its single-agent version [2. 83].
Definition (Prior around True Model), Given and any distribution p" E Ay, we define
w(B.
inf {Bc (ne)( <>0
where F(e) = FF su KL (. b)lPP f.1(. 8, b)) S Se) for FOMGs and F(E) = =f sup,, KL (P7 (TH)) - for POMGs.
When the model class F is a finite space, if let p" = (n), we simply know that w(3.p' S log | where |F is the cardinality of F. Furthermore, for an infinite function class F, the term log [F] can be substituted by a quantity having logarithmic dependence on the covering number of the function class FF. With the multi- agget- GEC condition and the definition of w, we have the following regret bound for both FOMGs and POMGs.
Proposition 1. Letting A 1/2, 7
72 -2/ ; /dGGE....
e 1/VHT in Definition 1, when T 2 max (AHHT, (((HTTT'))) "OMTTTp")/dar / w/ (AHT, / dGEC/ H}, under both FOMG and POMG settings, Algorithm admits the following regret bound,
E[Regi (T)) = : - 1)."") (/5/////o/ / HT - p9) + w(HH (4)..
This proposition gives the upper bound [E[Reg," (T)) following the updating rules in Algorithm when the max-player is the main player. As Algorithm 3 is symmetric to Algorithm 1, we obtain the following regret bound of E[Reg (T) for Algorithm when the min- min-player the main player.
Proposition 2. Under the same parameter settings Proposition 1, Algorithm 3 admits the following regret bound,
E[Reg (T) (T) =
-y-1] 6 TwIHHHTTWWW(FFFF (WHH,, po)
((HT, 1))-
sP (T) + Rog2 4p (T), we obtain the following overall regret when running Algorithms and 3 together.
Combining the results of Propositions and 2, due to Reg" (T) = Reg
Theorem 1. Under the settings of Propositions I and 2, executing both Algorithms I and 3 leads to
E[Reg*P (T) < / dC [WHHT + (4HT, gd)]
The above results indicate that the proposed posterior sampling self-play algorithms (Algorithms I and 3) separately admit a sublinear dependence on GEC deEc- the number of learning episodes T. as well as w4HHT, p²) and w(HHT, qa)) for both FOMG and POMG settings. They lead to the same overall regret bound combining Propositions and 2. In particular, when F is finite with pd = qd = (F), Algorithms and 3 admit regrets of deecHTT log [F). The quantity w can be associated with the log-covering number if F is infinite. Please see Appendix C for analysis.
Posterior Sampling for the Adversarial Setting
Without loss of generality, we assume that the max-player is the main agent and the min-player is the opponent. Under this setting, the goal the main player is to maximize her cumulative rewards as much possible, comparing against the value under the NE, i.e., Vj.. We develop novel algorithm for this setting as summarized in Algorithm 2. In our algorithm, the opponent's 's policy is assumed to be arbitrary and is also not revealed to the main player. The only information about the opponent the current state or the partial observation of her state as well as the actions taken.
We adopt the optimistic posterior sampling approach for the main player with defining an optimism term as >V2 motivated by the above learning target, and the likelihood function L (J) with L (f) = log F. a. (5/+41 1 sh, of, b),) in (1) for FOMGs and (f) n9 P (T,( in (2) for POMGs
7

---

Algorithm 2 Model-Based Posterior Sampling with Adversarial Opponent
1: Input: Model class F, prior distributions p", and y.
2: for ===,, =1,...,, ....,,T do
3: Draw model f* 1irpppp (-) with defining pl (f) x p)))) + E E 1 1,))
4: Compute T' by letting (x², v²) be NE of Vi.""
5: Opponent picks an arbitrary policy vt
6: Collect trajectory D' by executing the joint exploration policy of
7: Define the likelihood functions (f)) using the collected data D
8: end for
9: Return: (T "")
respectively. The policy x' learned by the main player is from computing the NE of the value function under the current model f sampled from the posterior distribution p². In addition, the joint exploration policy is set to be a² (ST', v²) where v² the potentially adversarial policy played by the opponent. Thus, we can collect the data defined as DD = {($,, a 0% 1) M and
D' (T with T = (of, at, bj :..,; obe a/s b))) for FOMGs and POMGs respectively, collected by executing a² to the h-th step of the game for each h E [H].
Remark 1. In Algorithm 2, we define the joint exploration policy o' (x', which is the key to the success of the algorithm design under the adversarial setting, especially for POMGs. Under the single-agent setting, the prior work [83] sets the exploration policy for range of partially observable models subsumed by the PSR model as क -i o Unif(A), i.e. running X¹ for steps 1 to h and then sampling the data at step by enforcing uniform policy. Such exploration scheme fails to work when facing an uncontrollable opponent who does not play a uniform policy at step h. Theoretically, uniform policy, the self-play play and adversarial GEC conditions in Definitions I and 3 are still satisfied for class of POMGs including weakly revealing and decodable POMGs. This eventually leads unified adversarial learning algorithm for both FOMGs and POMGs.
prove that employing policies (Ti vis)) for exploration without the
4.1 Regret Analysis for the Adversarial Setting
Before demonstrating our regret analysis, we first define a multi-agent GEC fitting the adversarial learning scenario. Considering that the opponent's policy is uncontrollable during the learning, we let {v² Y 1 be arbitrary, which is clearly distinguished from self-play GEC defined in Definition 1.
Definition 3 (Adversarial GEC). For any sequence of functions {f with f E F and any sequence of the opponent's 's policies {v²]T It=y suppose that the main player's policies {uy Ju'Jen are generated via μ¹ argmax, min, Vp:" Denoting the joint exploration policy as {a") depending on {
the adversarial GEC deFc is defined as the minimal constant d satisfying
ΣT,
(
- VF" v s [d h= ΣT. (E- E Eo xF((() {=) +HH(H)) +HH..
Our regret analysis for Algorithm 2 also depends on the quantity w(3,pt ((),p") that characterizes the coverage of the prior distribution p" the true model fr. Then, we have the following regret bound.
Theorem 2. Letting 1j 2 7 2/H(HT PT = 1/VHT in Definition 3, when T 2 2 ,"T,,""///// //)/)//drcc dero/ H), under both FOMG and POMG settings, Algorithm 2 admits the following regrel bound,
ElReg ady (T)) <
de COOECHT-WAAHT. pP).
The above result indicates that we can achieve meaningful regret bound by a posterior sampling algorithm with general function approximation, even when the opponent's policy is adversarial and her full policies v are not revealed. This regret has sublinear dependence on degc, the number of episodes T, as well as (4HT, pº). Similarly, when F is finite, Algorithm 2 admits regret of O ddec HT log [F). The term log F can be the log-covering number of JF if it is infinite.
8

---

5 Theoretical Analysis
This section presents several examples of tractable MG classes captured by the self-play and adver- sarial GEC, the discussion of the quantity wBB, p"), the proof sketches of main theorems, and the discussion of limitations.
Examples. We call the class with a low dGEC the low self-play GEC class and low adversarial GEC class. Next, we analyze the relation between the proposed classes and the following MG classes. We also propose a new decodable POMG class generalized from the single-agent POMDP. We note that except for the linear MG, the other classes cannot be analyzed by the recent posterior sampling work [73]. We defer detailed definitions and proofs to Appendix B.
Linear MG. This FOMG class admits linear structure of the reward and transition by feature vectors ((8, a, b) E Rd as r8,8, a, b) w Φ(8, a, b) and (s |8, a, b) = (s()) ((8 a, b) [71].
We then prove that "linear MG C low seffpplayladversarial GEC" with dGEC = Ö(Ho)..
Linear Mixture MG. This FOMG class admits a different type of the linear structure for the transition [16] as PA, (s'[s, a, b) = 0 Φ(s, a, s') with Φ(s, a. b, s') E R2d We prove that "linear mixture MG C. low self- play/aavvesaaaiiaaa GEC" with deeC O(Hd).
Low Self-Play Witness Rank. [28] defines this FOMG class for self-play by supposing that an inner product of specific vectors in I2 defined on current models can lower bound witnessed model misfit and upper bound the Bellman error with a coefficient liwit, which generalizes linear/linear mixture
MGs. We can prove "low self-play witness rank C low self-play GEC with dGEC = ((H d/ d/ wit) a-Weakly Revealing POMG. This POMG class assumes min, (On, 2 a where On E g|o||||| is the matrix by 0,,-1-) and øs is the S-th singular value [41]. We prove that "a-wlealyy revealing POMG C low relf-play/aveesariia GEC" with dGEC = Ō | ||A|||18| S|////))))))))/))))))))))))))S Decodable POMG. We propose decodable POMGs by generalizing decodable POMDPs [23, 22], assuming that an unknown decoder on recovers states from observations, i.c., (o) = s. We can prove "decodable POMG C low self-play/adversarial GEC" with dGgc = ((11 (()
Discussion of (1,,p"). We briefly discuss the upper bound of the quantity w(8,p') for FOMGs and POMGs. We refer readers to Appendix C for more detailed proofs. For FOMGs, according to Lemma 2 of [2], when F is finite, pd = Unif (F). then w(8,p) p²) S log [F by its definition. When F is infinite, it shows that under mild conditions, there exists a prior p" over F, B 2 log(6B2/d/ /c). and v' c/(6 (log((/B//))) such that w(3,p") p < Be + log ( (lo((B/o))) )), where NV(c) is the
covering number w.r.t. the distance d'), :- sup, s..... D ( 8, a, b), (-
b))
(P s. a. b). by. (-1 a, b))l. Since we have [D (P, R) (Q, R)I S v2 I Q for any distributions Q, and R, the covering number w.r.t. the distance d can connect to the more common covering number w.r.t. the & distance. Thus, the upper bound of w(B.r²) can be calculated for different cases. Additionally, for POMGs, inspired by [2], our work proves that under similar conditions, w(B,r") with finite and infinite F admit the same bounds as those for FOMGs. The difference is that the covering number is w.r.t. the distance d(f.f' = sup,,, D (P f.H. P
(Q,
D. {- D (P F. H.HP. ...,,)), which further connects to the L₁ distance de- Such covering number under l distance is further analyzed in [78]. Our work gives the first detailed proof for the upper bound of w pd) under the partially observable setting, which is thus of independent interest.
fined as (J, == sup [P P rH -
Next, we outline our proof sketches. Detailed proofs are deferred to Appendices D, E, and F.
Proof Sketch of Theorem 1. To prove Theorem 1, we only need to combine the result in Propositions 1 and via [P (T)) E[Reg, (T)+Reg?" (T)). We thus first give a proof sketch for Proposition 1. We decompose Reg
sp (T") = Term(i) + Term(ii) where
vp'r Intuitively, ([Term(i) is the main player's regret incurred Line 4 of Algorithm I and ([Term((i)) is the exploiter's regret incurred by Line 6. We further show
Term(i) = ΣT= [Vj- - vz. "y Term(i) ΣT.
[V
Termii < ΣT [- AV + +
".. Term(ii) = ET_ [vrl -Vz'
+ +
vy *].
9

---

Vi are associated with the optimism termss in posterior distributions. The inequality above for Term(i) is due Line 4 such that V oe min, V
where AVद : -V - Vi- and AV Vi r
J I SVT'e' and Ei=l (VF (ir can be bounded by
By Definition I for self-play GEC, we obtain that Σ (VT V iel
8r
dGEc E Ei= (Ei=i B (o
el :k))
1/2 + (d( + ll
where ot is chosen as 7 or f respectively. By Lemma 11 and Lemma 12, we prove that for both FOMGs and POMGs, the accumulation of the losses E(F', <h) in (3) connects the likelihood function f.j, defined in (1) and (2). Thus, we obtain E[Term(i)) & Ei= Bi (-
E EE [A(""]] + log p'(T)) (TG + eHT and ([ has pP)7")
similar bound based on q², where z is the randomness history. By Lemma 10, the posterior distributions p² and of following Lines 3 and 5 of Algorithm can minimize the above upper bounds for [[Term()) and [[Term(ii)]- Therefore, the true model fr to enlarge above bounds. When T is sufficiently large and 1/2, we have
relax p' and q' be distributions defined around
[[Term(i)] S w (HT,P")TT/m + TidgooH/44 + 2H (dGEcHT) à + +HT,
[[Term(ii] (HHTT + redGEcH /4 + 2H (dGEcHT)) + eHT.
Choosing proper values for 6,71, and 7/2 we obtain the bound for TE] [Reg (T) in Theorem via Reg, (T) Term(i) + Term(ii). In addition, we can prove the bound of E. Reg, sp (T) in symmetric manner. Finally, combining [[[eg]" (T') and E R[Reg2" (T)) gives the result in Theorem 1.
Proof Sketch of Theorem 2. Under the adversarial setting, the policy of the opponent 1¹ is not generated by the algorithm, which could be arbitrarily time-varying. We decompose Regady (T) ET AVF + ET EV-IVE Vj. "1 where AVJ. Vj- Vj+ relates to optimism. Since (x' (',,
NE of " as in Line of Algorithm 2, we have Vf. min, V S Vy which leads to
Regat (T) S Σx AV
[V V7.
We can bound Ets IV7
V y
via adversarial GEC in Definition 3 by
dGEC H Et=l
EE Boo Ay (((())((( (() + (dGEc cHT.
Connecting the loss E(T', :i) to the likelihood function L.,, defined in (1) and (2) via Lemmas 11 and 12, we obtain E[Reg adv (T)) S ET= Ez--EE {r ΣT= AVj. - E (E=(
(f*) + log 2'(()) + 2H (T) + eHT. Lemma 10 shows p² in Line 3 of Algorithm 2 can minimize this bound. Thus, relaxing p' to be distribution defined around the true model f", with sufficiently large T and 17 1/2, we have
[Reg adv (T)) < (OGHT.PP")T/ + H/4 2H (dGEc HT) + cHT.
Choosing proper values for and 7, we eventually obtain the bound for E[Regadv (T)) in Theorem 2.
Discussion of Limitations. Our work has studied several but a limited number of tractable MG classes in both FOMGs and POMGs. is interesting to further define new MG classes by generalizing their single-agent counterparts and explore the relation between these MG classes and low self- play/adversarial GEC classes. It also intriguing to generalize our method to general-sum settings.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their valuable comments. The authors would like to thank Wei Xiong for the helpful discussions. Shuang Qiu and Tong Zhang acknowledge the funding supported by the GRF 16310222.
10

---

References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Alekh Agarwal and Tong Zhang. Model-based with optimistic posterior sampling: Structural conditions and sample complexity. arXiv preprint arXiv:2206.07639) 2022.
[3] Alckh Agarwal and Tong Zhang. Non-linear reinforeement learning in large action spaces: Struc- tural conditions and sample-efficiency of posterior sampling. arXiv preprint arXiv:2203.08248; 2022.
[4] Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv preprint arXiv: 07041, 2017.
[5] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with targe-te regression. International Conference on Machine Learning, pages 4634474. PMLR, 2020.
[6] Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR, 2020.
[7] Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
[8] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota with large scale deep reinforcement learning. arXiv preprint 19/2. 2019.
[9] Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint arXiv:2305.0900 09659, 2023.
[10] Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):885- 2019.
[11] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
[12] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
[13] Fan Chen, Yu Bai, and Song Mei. Partially observable rl with b-stability: Unified structural condition and sharp sample-efficiee algorithms, 2022.
[14] Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision-essimmation coefficients: No-regret, pac, and reward-free learning. arXiv preprint arXiv:2209. 1774,
[15] Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael I Jordan. A general framework for sample-efficient function approximation reinforcement learning. arXiv preprint arXiv:2209. 15634, 2022.
[16] Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero-sum linear mixture markov games. In International Conference on Algorithmic Learning Theory, pages 227-261. PMLR, 2022.
[17] Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 2018.
[18) Qiwen Cui and Simon S Du. When offline two-player zero-sum markov game solvable? arXiv preprint arXiv:2201.03522 2022.

---

[19] Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 14:122 2021.
[20] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov equilibrium in stochastic games. arXiv preprint arXiv:2204. 039911, 2022.
[21] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-28233 PMLR, 2021.
[22] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674, PMLR, 2019.
[23] Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforce- ment learning with short-term memory. In International Conference on Machine Learning, pages 5832-5850. PMLR, 2022.
[24] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112. 13487, 2021.
[25] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in observable pomdps, without computationally intractable oracles. arXiv preprint arXiv:2206.03446, 2022.
[26] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning in observable pomdps in quasipoly- nomial time. arXiv preprint arXiv:2201.044 0.473,, 2022.
[27] Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pages 510-518. PMLR, 2016.
[28] Baihe Huang, Jason Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approximation in zero-sum markov games. arXiv preprint arXiv:2107.14000 2021.
[29] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
[30] Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforce- ment learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33:18530-1855 2020.
[31] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficiet algorithms. Advances in neural information processing systems, 34:13406-1344 2021.
[32] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555, 2021.
[33] Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent rl in large state spaces. arXiv preprint arXiv:2 (06.:2/006.3352,, 2021.
[34] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[35] Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The complexity of infinite-horizon general- sum stochastic games. arXiv preprint arXiv:2204.00 04.16. 2022.
[36] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
[37] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and lower bound. Advances Neural Information Processing Systems, 34:24523-24533 2021.
12

---

[38] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[39] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? In Conference on Learning Theory, pages 3175-5220.
PMLR, 2022.
[40] Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle-a a generic model-based algorithm for partially observable sequential decision making. arXiv preprint arXiv:2209. 14997, 2022.
[41] Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement learning of partially observable markov games. arXiv preprint arXiv:2206.013: 01315, 2022.
[42] Qinghua Liu, Yuanhao Wang, and Chi Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. arXiv preprint arXiv:2203.06800 066003 2022.
[43] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. sharp analysis of model-based reinforcement learning with self- eelf-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
[44] Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. Advances in neural information processing systems, 30, 2017.
[45] Weichao Mao and Tamer Başar. Provably efficient reinforcement learning in decentralized general-sum Markov games. arXiv preprint 1rX1v:2100.05682, 2021.
[46] Anusha Nagabandi, Kurt Konolige, Sergey Levine, and Vikash Kumar. Deep dynamics models for learning dexterous manipulation. In Conference on Robot Learning, pages 1101-1112. PMLR, 2020.
[47] Chengzhuo Ni, Yuda Song, Xuezhou Zhang, Chi Jin, and Mengdi Wang. Representation learning for general-sum sum low-rank markov games. arXiv preprint arXiv:2210. 16976, 2022.
[48] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016.
[49] Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
[50] Shuang Qiu, Lingxiao Wang, Chenjia Bai, Zhuoran Yang, and Zhaoran Wang. Contrastive ucb: Provably efficient contrastive self-supervised learning in online reinforcement learning. In International Conference Machine Learning, pages 18168-18210. PMLR, 2022.
[51] Shuang Qiu, Xiaohan Wei, Jieping Ye, Zhaoran Wang. and Zhuoran Yang. Provably efficient fictitious play policy optimization for zero-sum markov games with structured transitions. In International Conference on Machine Learning, pages 8715-8725. PMLR, 2021.
[52] Shuang Qiu, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. On reward-free rl with kernel and neural function approximations: Single-agent mdp and markov game. In International Conference on Machine Learning, pages 8737-8747. PMLR, 2021.
[53] Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019.
[54] Daniel Russo and Benjamin Van Roy, Learning to optimize via posterior sampling. Mathematics of Operations Research, 1221-13221 2014.
[55] Igal Sason and Sergio Verdú. f f-divergence inequalities. IEEE Transactions on Information Theory, 62(11):5573-6000 2016.
[56] Shai Shalev-Shward Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 1610.03295, 2016.
[57] Lloyd Shapley. Stochastic games. Proceedings of the national academy of sciences, 100001000 1953.
13

---

[58] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schritwieser, loannis Antonoglou, Veda Panneershelvam, and Mare Lanctot. Mas- tering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 2016.
[59] Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum Markov games with large number of players sumpleefficiently? arXiv preprint 1..iiv22100041844 2021.
[60] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898- 2898-2933. PMLR, 2019.
[61] Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning in unknown markov games. In International conference machine learning, pages 10279-10288, PMLR, 2021.
[62] Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings. arXiv preprint arXiv:2206. /2081, 2022.
[63] Masatoshi Uchara, Ayush Sckhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient reinforcement learning in partially observable dynamical systems. arXiv preprint arXiv:2206. 12020, 2022.
[64] Ramon Van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
[65] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittiiser,, et al. StarCraft II: A new challenge for reinforcement learning. arXiv preprint 14877.700 2017.
[66] Lingxiao Wang. Qi Cai, Zhuoran Yang, and Zhaoran Wang. Represent to control partially observed systems: Representation learning with provable sample efficiency. In The Eleventh International Conference on Learning Representations.
[67] Ruosong Wang, Ruslan Salakhutdinov, and Lin Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005. 2020.
[68] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:61 53:6123-6135, 2020.
[69] Yining Wang, Ruosong Wang, Simon Du, and Akshay Krishnamurthy. Optimism in reinforce- ment learning with generalized linear function approximation. arXiv preprint 16 2019.
[70] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-/1), pages 681-688, Citeseer, 2011.
[71] Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous move markov games using function approximation and correlated equilibrium. In Conference on learning theory, pages 3674-3682. PMLR, 2020.
[72] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single- agent mdp and markov game. arXiv preprini S..iv:2205..51122 2022.
[73] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, and Tong Zhang. A self-play posterior sampling algorithm for zero-sum markov games. In International Conference on Machine Learning, pages
PMLR, 2022.
[74] Yunchang Yang, Han Zhong, Tianhao Wu, Bin Liu, Liwei Wang, and Simon S Du. A reduction-based framework for sequential decision making with delayed feedback. arXiv preprint 20X1v:2332.01477,220 2023.
14

---

[75] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approximation in reinforcement learning: Optimism the face of large state spaces. arXiv preprini 1xXiv:201..06622 2020.
[76] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020.
[77] Wenhao Zhan, Jason D Lee, and Zhuoran Yang. Decentralized optimistic hyperpolicy mirror descent: Provably no-regret learning in markov games. arXiv preprinl arXiv:2206.01588 2022.
[78] Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D Lee. Pac reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05738 2022.
[79] Tianjun Zhang, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear mdps practical via contrastive representation learning. In International Conference on Machine Learning, pages 26447-26466 PMLR, 2022.
[80] Tong Zhang. From E-entropy to kl-entropy: Analysis of minimum information complexity density estimation. 2006.
[81] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-857, 2022.
[82] Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. arXiv preprint arXiv:2202.075// 2022.
[83] Han Zhong, Wei Xiong, Sirui Zheng. Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. arXiv preprint arXiv:2211.01992. 2022.
[84] Han Zhong, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Can reinforcement Iearn- ing find stackelberg- nash equilibria in general-sum markov games with myopically rational followers? Journal of Machine Learning Research, 24(35):1-52, 2023.
[85] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021.
15

---

Appendix
Contents
Omitted Algorithm in the Main Text
17
B Computation of Self-Play and Adversarial GEC
17
B.1 Linear MG
17
B.2
Linear Mixture MG
20
B.3
Low-Witness-Rant MG
21
B.4 Weakly Revealing POMG
24
B.5 Decodable POMG...
32
C Computation of pB)
34
C.1 Fully Observable Markov Game
34
C.2 Partially Observable Markov Game
35
D Technical Lemmas for Main Theorems
37
D.I Lemmas
37
D.2 Proof of Lemma 11
38
D.3 Proof of Lemma 12
40
D.4 Proof of Lemma
D.5 Proof of Lemma
42
E Proofs for Algorithms 1 and
43
E.1 Proof of Proposition
43
E.2 Proof of Proposition
47
E.3 Proof of Theorem
49
Proofs for Algorithm
50
F.1
Proof of Theorem 2
50
Other Supporting Lemmas
52
16

---

A Omitted Algorithm in the Main Text
Algorithm 3 Model-Based Posterior Sampling for Self-Play (Min-Player)
1: Input: Model class F, prior distributions p and q", Y1, and 72-
2: for = I,..., do
3: Draw model /" ~ p-) with defining p² x expl expl- E E 4TO
4: Compute y² by letting (T", v²) be NE of Vi""
5: Draw model I ~-gg g-(+) with defining (/) x (²) expla2
E Σ (00
6: Compute x' by letting x² be the best response of v' w.rt. Va
7: Collect data D' by executing the joint exploration policy o²
8: Define the likelihood functions (T(()))= using the collected data D
9:
end for Return: (u',...,
B Computation of Self-Play and Adversarial GEC
In this section, present the computation of the self-play and adversarial GEC for different FOMG and POMG classes, including linear MGs, linear mixture MGs, low-witness-rant MGs, weakly revealing POMGs, and novel POMG class, dubbed decodable POMGs, newly proposed by this work.
Note that the GEC dGEç essentially depends on as shown in Definition 1 and Definition such that should be expressed as d'gcc For convenience, we omit such a dependence in the notation. In our main theorems, we set 1/VHH /HT, and according to our derivation in this section, dGec has an (llo((1/e)) O(- log HT)) factor which only scales logarithmically in T.
B.1 Linear MG
In this subsection, we show that the linear MG is in the class of MGs with low self-play and adversarial GEC and further calculate dgEC for the linear MG. Definition 4 (Linear Markov Game [71]). The linear MG is FOMG admitting the following linear structures on the reward function and transition kernel,
rn(s, a, b) (s,,(s, PA(s' Pa(s'18,,,b) (8, = (s) ( ().,0,
where there exist a known feature map & : S x and (s') E Rdd that should be learned in algorithms. We assume that the feature map and the coefficients satisfy [| a, b)ll2 I 1, Js [) S Vd. and ||wall2 vd.
A B Rud and unknown coefficients wh. Red
Then, dGEC for the linear MG can be calculated in the following proposition. We can show that both low self self-play and adversarial GEC classes subsume the class of linear MGs.
Proposition 3 (Linear MG C Low Seff-Play/Adversariaa GEC). For linear MGs with ő(s, a, Rd as defined in Definition 4, and for O. when T is sufficiently large. choosing ((f. En) D2 (IP ( Pr,,P Ex)) as in (3) with &n. (8h, an, by), we have
linear MG MG with low self-play and adversarial GEC
with deec satisfying
dGEC = 16H (1+ HT -r)
Proof. Since the value function is defined as VT. f.h (sn) = Enp,, DW Twr ans bw [sn] V (s1) and we also have relation via
at step h with denoting V.
17

---

E...P.y , |Σ (s) f++ ( for any f' using the telescoping summation as well
V.
(.H+11)) 11) 0, thus decompose the value difference follows,
V ,e Vy."
H
H
= PP.y
Σ
E(vi
sih (sh) (sn)) V .² s4 (on+1))) B Bt
Σ h=
rh (8h, an. ba))
-==1
Σ Begt MA B3y-
V (8h) (0, + Valie
gehti (sh-1))
H
gn fihh"
(4)
where we define the following Bellman residual in expectation (ra(sh, Oh bn.) + y 1 (9+42))
Ca.
f,h == E....
[T (Sp, 0h,, bn) - (anesrrrrr,uullll..
The Bellman residual for the linear MG can be linearly represented, whose form
E. = Ex,,,,,- / (P,,(()sh an,bn) bn) (r an. bn an, (. (s)ds
Jhh
E.P,,,p / [ob(on an, bb. (0 (s) (s)ds
= Ex.., Øl on bn) / [[0),(()) ()-,n (7
(Br,,,, Φ0 (sn, an, bn), Qh (J,
where we let
n an n. v) = / [0)m(()) (+)) (s)ds,
such that we have (f, n, 1) S 2VdH according to the definition of the linear MG. Therefore, the value difference term also be rewritten
H
II @hh ah b),), qn (s", A w'))
where (5h, oh (6,) can be viewed as sampled data following nr, v., and Py.. For simplicity, we denote t% = Ex @lsh ah, by), gh == qa ( v²), and &h = (5h ah, Dy), and define $ = Ala El= @h(0)) with X > 0 and sh = 11 2--1- Note that we have
Σ (1h g + N1
(5)
where the term (d) y2 can be bounded
(1bh q = Ex S { (Pyr,t(s an, bn) P P. sh, an. bn)) Vst (s)ds
< H 2 s [P an, bn) - P- an, by. 11?
< " v f- Di (IP p an,
(-1 an. by))..
(6)
where the first inequality uses (s) < H and the second inequality uses P 1P-QQ1 QI 8D2 (P, Q). Moreover, using =b
<
also have
(0), qi)) (0h, g (1 [ (xt24))
H min | ai). 1o <a) + HI 1,/21
|aiilay- min(sh, 111 [ <1) H (622)))
18

---

where (() denotes an indicator function.
Plugging (5) into (7) and taking summation from / T, obtain
H
Σ
Σ
lgh aa min( 1/ (pt <a> + H [2/21]
4=1 t=1
H
100 op30 + 4AdH² min (0 + H (,,21)
H
koh aMP + V4xdIf
min(vh. 1),())))))))) + H. (0(21)
hml t=1
T 1-1
H T o MPP
m 1)1 ( (0),<1)
P=
H T
H T
T
min ((0))) 1)1 (ot<))) <n + H
min
Σ Σ
(0221)
(8)
h= t=
where the second incquality uses Va+bs Va + v and the last inequality is by Bauchy-Schware According to the elliptical potential lemma (Lemma 15), we have the following bound,
H
T
H
det $ det 4
< <Hddlg (1+ T)
min f ((hh)
S
Σ log
(9)
dd
1=1
where the first inequality uses Lemma 15, and the last inequality uses log det $ S dolog tr(*%) < dog Ad+T, We also note that of cannot exceed 1 too many times, as detailed in Lemma 16. By Lemma 16 and the fact that (0121) & 1, we obtain
3Hd log 2 log
1
(11211) min
1+
HT
(10)
llgg
Combining (6), (7), (9), and (10), we obtain
Vx ae je
T
2Hd log
1
dA
4XdH3T min
2Hollog
(1
T
HT
min
(3H2d
log
1 llo
1
HHTT
dA
logg
T
< H.
16lldl0g 1+
B A)) Di (P (1 (-))), Pr (((x))))))))))
di
+ XdH2 + min 21/2dlog
1+
T
.HTT + min
3HHdd
log
1 Alog
H2TT
dd
log2
T
1-1
16H
1+
Bi Diue (P (. (.)((())))) (
d)
T
+ AdH2 +2
2HHddoog
1
A
2TT
(11)
dA
19

---

which further leads to
H
Σ Var sec
Vg m
$
16H
HT
E am
HT E by A y vzy and setting XHd where À > O and e(f. := Di (. P/ with ET. = (8h, Oh, bn). Thus, we obtain that when 7 is sufficiently large, we have
eHT + 2H 1+
HT
dGEC = 16H
1+
Note that the above results hold for arbitrary policy pair (v', x²)). This implies that linear MGs with the dimension d is subsumed by the class of MGs with self-play and adversarial GEC dGEc 16/1 d log(1 + HT). This completes the proof.
B.2 Linear Mixture MG
In this subsection, we discuss the linear mixture MG setting, where the transition kernel is linear combination some basis transition kernels and thus admits linear structure. Specifically, we have the following definition of the linear mixture MG.
Definition 5 (Linear Mixture Markov Game [16]). There exists d-dimensional feature map x A x B x S + R² and an unknown coefficient O2 E IR,, such that the transition of the Markov game can be represented by
PR(SN41 8h; on, bn) 0% (5 88h Uh bn), where ||0x1l2 S B and Is a, b.')
H for any bounded function V [0, H].
In the context of linear mixture MGs, both self-play and adversarial GEC can be calculated. Proposition (Linear Mixture MG C Low Self-play/Adversariil GEC), For linear mixture MGs with (bs,, a, b, s¹) Id defined as in Definition 4, and for e O, when T is sufficiently large, choosing ((f,G)) Di 1 (...(-15),, y x(- [x)) as in (3) with En = (8h, On by), we have linear mixture MG C MG with low self-play and adversarial GEC
with dGEC satisfying
TB2
dGEC d
deH
The proof of GEC bound in a linear mixture Markov game is similar to the one in the linear Markov game case. We first define the Bellman residual in expectation as
Proof.
ET. = Py [77:% (Sh, Oh, bb)
Es an)
(ra(Sh, an bb) Vittt (
One can derive the following property of f.h by precisely the same derivation as in (4), which is
fihh
h=1
We next show that in a linear mixture Markov game, the Bellman residual represented, whose form is
Sn." fj can be linearly
f ER..P,
[Prn(ssss, an, on, P P/-,, (s|sn, an, an bn)) V.. 1 (s)ds
= Er,ep / [cp(s), on, 8) (0 0 VV.. f.h+ (s)ds
-(E..IP / Olon ah bn 8)
VT. V (s)ds, 0F~ 0y
= (dssn, an bn. f. v). (f))))
20

---

where we define Φ(SN, an, (T, == B- Is Φ( an b, V
fh++ ( and qn (f) ==
f f a Note that (1 an, bn, f. J, will _ H and (f) 2B by Definition 5.
We next define Φ == ((s), an oh x, w²) 9h. == qn $ PIK H Ei=1 (0)) and
v = | 1--1. Since we have
( qhil2 = En Byn [s (I (Pyr:(() ( 0h, P (s) 1/ di (/)) / (s)
1s)
S H Mr, p M (. 18 4i b/)) ( 1//- 4j D
< E. M,, p, De (IP st, s/c dj b)), yr , (-1 s/., a2 b4))
(12)
where the first inequality is due to 177 ./' f. (s) - H and the second inequality is due to || Q11
&ie (P, Q). By utilizing |1 (f)ll S 2B and (12), further obtain upper bound of || a
as follows,
[1
1 11 S
(1b, 2 + 11
SH2 FT. Di (1 1 ai, 1,), y- (-1s%
(,, ()), ) 4AB².
The rest of the proof is the same as the proof in the linear Markov game, from (5) to (11), except with a scaling factor. We provide the final result here as follows.
Vx des
(1
1+
T
T
H
16Hldlog
B ,..- Dito (P 18, ag P.,, 16 a/ b())
di
(=1
1=
+ >B2T + min 2HH'dlog
1
T d)
H²T + min
(3H2d
log
(1 ( Alog x1x1) H2T
log?
T
T
1-1
16H
1+
E B Dio (Prr 18 by), Py.
dA
1=1
R=
T dA
+ XB2T + 2002
|+
H2T
Note that here (²) can be any arbitrary policy pair, including the ones required as in Definitions I and 3. Moreover, will see that the above result satisfies the definitions of both self-play and adversarial GEC when using the inequality x A I vzy and choosing À = cH/B² and ((J,x)) = D2 (P
(.,),, (..),.PP p-ra ( (.)))) Therefore, we have
dGBC dd log (1+
TB²
dell
for T sufficiently large, which shows that linear mixture MGs with the dimension is subsumed by MGs with self-play and adversarial GEC dGEC 16/// proof.
TB² This completes the deff
B.3 Wore--iinnssaaaa MG
Witness rank is complexity measure that absorbs wide range of settings in single-agent RL[60]. The work [28] further studies the witness rank under the MG setting with self-play. In this subsection, we show that MGs with low self-play GEC subsumes the class of MGs with low witness rank in the
21

---

self-play setting. Since the witness rank under the adversarial setting was not investigated in prior works, we here only analyze the self-play setting,
Before presenting our main proposition, we first show the definitions of witnessed model misfit and witness rank in MGs with self-play [28].
Definition 6 (Witnessed model misfit in Markov game). Suppose that there exists a discriminator class U with u E u S x A x B x S + [0, H]. The witnessed model misfit in Markov games W(f.g. p. h) for the models f. F at step h is characterized by
p,
-su well
(= B bs, uu(sk ans bn:
Es pr a (nnnnan bw) ((hh on bn sh+1)
where ã a min, V and D == argmin, V with f.
The definition of (Ø, P) matches the requirement for the policy pair in the self-play GEC, i.c., condition (1) in Definition We note that condition (2) in our definition self-play GEC designed for Algorithm 3, which is thus symmetric condition to (1). We define the Bellman residual as
f.h = P. (7% on, on,ba) bb) E 1 de br) (ru(sh, Ons bb) + V (.h+1((h42)))
Then, we have the following definition of witness rank for MGs with self-play. Definition 7 (Witness Rank for Self-Play). There exist two functions Wn. F Rd and X1 F + Id and constant
such that
Kwit Kwitle 1 P.h. S (Wn(f.9), (n)),,
W(..gp.h) Z (W.(f.g).xx.))
where # = argmax, min, V and =- argmin, V with f.ge E F, [W S HB for constant B, and x|)l( S for any step Then, the witness rank of MGs with self-play defined as the dimension d of the range spaces for functions W and X.
We show that in the self-play setting, déEC is bounded for MGs with a low witness rank. It is worth noting that the proof of GEC bound for MGs with low witness rank generalizes the proof for linear MGs in Appendix B.
Proposition 5 (Low Self-Play Witness Rank C Low Self-play GEC). For a Markov game with witess rank d as defined in Definition 7, when T sufficiently large, choosing (n) = Di (IP yM En), Ek))
as in (3) with & (9h, an, by), we have MG with low self-play witness rank C MG with low self-play GEC
with dGEC satisfying
4H log
1+
THB²
dGEC
4dem2
Proof. We first give bound the model misfit the Hellinger distance. By 0 S u S H, we have
Eg Egg-Ppa ( (n. u(sn, an, bn. s²) E Eeati Pp ael an.an, ul(n an bn, sn+1)) 2
$ HP]1[pp.a( 8h, on, bn) - Ps (-1 8h, an, b1
2H 2H (Pp. St: ar. b... IP.. (e Sh, an. bi)):
where o can be f or g as in the definition of self-play GEC. By the definition of W(f,g, g. p,h) and Jensen's 's inequality, we further get
W(f.g.p.hy) h)² < 2H b. #, Di (Pp.n(:) sh, an, bn), P/ ( an bn)), (13)
where we use sup, Ex,, v) < E, sup, S v) and the definition of (i, B). Note that following our definition of self-play GEC, if we choose f= f and g = g² in the model misfit, then correspondingly we have # T² and & = v² as in the condition (1) of Definition 1.
22

---

By the definition of E we can decompose the value difference
T
T
H
V
17 V
gx De
hm
Hereafter we define W
= Wa(f'
X = Xa()'),
2/1
== 1K +
x and
9 = X
(xt)
S H, we obtain Using the definition W and X and v0'
H
H H min
(Wh(f".g') x()(0)))))()))))
Hkwit
1=1
1=1
H
(1 ",,")))))x(((')))111 1 xx((
H min
(Wa(f',
+ (1x
H
h=1
H
W Wills min
X
Kowit
Term(i)
Σ (oh
Term(ii)
where 1 denotes the indicator function. For Term(ii), we can apply Lemma 16 to obtain
[31f'd
(1 S min
(1
A Alog 2 H²T
log 2
It remains to bound Term(i). We first calculate the sum of W which is
W
T
AII Σ Wh, x;²²
H
< H
ΣΣΣ
W x
h=1
H-1
SHTBBA+2H
( mo D (Ppr sh, an, ba). fr ( ( shy an, bn)).
where the first incquality uses W < HB, and the second incquality uses the definition of witness rank and (13). We also let c == ( a b.). We next use Lemma 15 to obtain
H
T
min 1} < min 2Hdlog (1+
T dā
HT
Am
23

---

Finally, by using the inequality, we obtain the bound for Term(i) as
T
||
x|
( 51}
Kwit
[=1
h=1
min (on 1}
Rwit
T AHSBB 2
ΣΣΣ
( Di py
Kwit
T dd
min
2Hdlog
1+
HT
B2
2H
t-1
E
(r D (P (.)E)) P/,,
R wit
wit
h=1
min
2Hdlog
++
T dx
HT
where the first inequality is by Cauchy-Schwarr and the last inequality is by Va +bs vā + vvb. We further invoke vab S + b to obtain that
(i)m(i)
X2 4x
T
+ min
2H2 log
2H
1+ H2T
4/1'd 2 wit
T
T
log
1+
Σ
B
aa my
Di (Prr (h),P/-a((11)))
dd
h=1
Finally, we combine the bounds for term(i) and term(i)) to obtain that for T' sufficiently large,
.ut at
V
22
1+ 7
+2
2H log
4n wit
dd
4H3d
(1+
T
T 11
log
Er ( M) D (Prr (h), (())))
dA
Aiti
t=l
h= cm
where also the inequality x A y S Vay- Then, Definition I with choosing
that the above results satisfy Thus, conclude that under the self-play setting, have
X Aemi HB*
4H log (1+ THB
dGEC
R2
4dcx2
2 wit
This concludes the proof.
B.4 Weakly Revealing POMG
In this section, we consider a weakly revealing POMG. Recall that (Or H stands for the emission kernels, which can be viewed in the form of matrices O, E [R[O)([S], with the (o, s) element being Or (o) 8) for step h. Similarly, the transition matrix PP Pha [[SSX(S] such that the (8/,8) s)-th element is PA | b).
24

---

Here we consider undercomplete POMGs where there are more observations than hidden states,
[O] 2 |S). Formally, it can be defined as an a-revealing POMG follows:
Definition (a-Revealing POMG [41].. A POMG is o-revealing if satisfies that there exists > 0 such that ming as (On) 2 a, where a-()) denotes the S-th singular value of a matrix with S = |S].
The a-revealing condition measures how hard to recover states from observations. Before presenting the GEC bound for an a-revealing POMG, we first define some notations. We define Thcck = (0i, 04, bi) to be a set of observation-action tuples from step h to ht. For simplicity, we denote Ti:h as 7h- We define qo Ci E | where μ1 | is vector formed by the distribution of the initial state. We define ( == [Pr (o1:h, oh+1 do(a1:h. bash))loeo E R ol when Th (ot, ai b.) Here do(a1:1, b1.h) means executing actions aN and by step It. In other words, Pr (01sh, 0h+1 do(a ((aa)) describes the probability of receiving observations which is the concatenation of the probabilities under condition The We have (TT)) [Pr(o Tisk)loeo, where Pr(o) Ti:)) means the probability of receiving o = under the condition that the previous trajectory The
01ch given the actions fixed as (01:A-1, b1:1-1). We define ((T)) ==
Based on the above definitions, we then derive the GEC bound for an a-revealing POMG in the following proposition.
Proposition (a-Revealing POMG C Low Self-Play/Adversariid GEC). For an a-revealing POMG defined in Definition 8, with the loss l(f, defined in (3) for POMGs, we have
a-revealing POMG MG with low self-play and adversarial GEC
with dGEC satisfying
H 1800
dGEC = O
where 2oog (1 (1+ 41481311
For our proof of this proposition, we prove several supporting lemmas presented in Appendix B.4.1.
Proof. For ease of notation, let [8|, A |A|, B [8], and O |0| in proof. We define the following observed operator representation:
a, O : ain.,,
R
for 1 < h S H. One can verify that the previously defined MA (o, a, b) has the following property,
((Th) Ma(on, an, bn) M, (0 (o--
Mi (01, an, by b1)go-
Specifically, P(TH) = Mn (n an, ba) M, 01, by yoo For simplicity, we define
MWaaooos alek, bbak)) = (o aw, by - -1 -1, -1) Ma(on, an, bk).
We also rewrite Mi:h+1(0h+1.k 0141:H bx+1:H) as m 4h+1:H b)+1:)) to emphasize that M (0x+1:H, O1+1:HH bb41:H) is a vector since Mμ (Ои, az by) is vector.
We start by using Lemma 5 to decompose the regret follows
T
Σ
V fr
H
H Σ
Σ Th
[IME ab, bn) Mi(on, an, by bb)))(a))))11 (1))() ) + 11 9ulla
h=
25

---

Combine this with the fact that Vi ut
Vg.
Hew have
T
VJ-
)
H S
min
Σ
an bn)
MA (oh; ar (h. (1)) (Tm)
VS"
h=1
+ 11 20ll1]
where we define
(Thh) II Tw (aw (w-11,0c); v(T)) II us (W-1,)))) d'(n)) = (T())))(TT))
and Mt. and dó correspond to the model f sampled in time step L. We next focus on Σn, (on,, an, bn. Ma. (on, on, bn (l( By the definition of and q, we obtain
Σ (M, an, bn) - MA an, (1)
Σ
Σ
(o an, bn) Ma on, (T)) (on, On, bni Th-1)
A--iprr ind h-t Oh ,0 Dy
Σ
Σ
e,
(o an, bn) Mn (ono ahe by bz
Th-p-ppfe 1th Oh.dn,bn bn j=1
((Tn-))o'(on an, bui Tn-1)/
where ēÿ denotes the j-th standard basis vector in RO, and of (ThiiTh-1) = x (TaniiTT-))-
('TnuNNiTh-l where a' (Thah's 7h-1) I Th (T"--,ww"). (ThWitT--) Ihh 1h (ba") Ow")), For simplicity, we define Whasiad == (ē) (M,
MA a, (oo,a,b))00 On-) and Tr. 1,,0,,b ((7 a, by TT)) Then, we have
Σ
Σ
è (M, an, bm) Mn an, ba)) 0/_- a(T 1)00 an, bus Th-1)
Po-ipPPa go h- an. j=l
Σ
0,0 Th-
1
Next, we will apply the le eluder technique [13, 83] in Lemma 17 to derive the upper bound. We first analyze the upper bounds of Σ | 1|2 and E "- [ 1,0t,, for the usage
of the Eg eluder technique. According to Lemma 7, for any (o, a, E 1OX Ax B, we have
2ABAVS
E p- f-hh1
| 3.
www.t..o.bblll
26

---

According to Lemma 17, setting R= Vs and Ry Ryy S obtain
442 in the new 62 eluder technique,
a²
a
Σ
E
VS
Te- of
1=1 o,a
T
Σ
Os
E
(I(M) an bn) (n an b())4(
m=
(on, ans bks Th 1h-1))
where 5 = 2log (1
By Jensen's 's inequality, the last term above is further relaxed as
a²
OABaa
T t-1
0² ABs
T
+
ΣΣ
E
Σ
[[M an, bn) - (o an, bn)) (Th-)))((T111))
s
t=l
1=1
an,
(on, ah by; Th Th-1))
Then, invoking Lemma 6, we obtain
T
E
1w Wh..joo, -10 (ottjaa s000l
P pa j=l o,a.b
OABa²
D PF P )
2
ABS
T
(14)
S
a
t=1 1=1
We next focus on 11
20ll1- Using that |1gb
- 20l11
1 and 2(1 1) 2 1 when / 2 2, we obtain
2(t
11
4oll1 1
+
|/ 20ll
1=2
1
11+
Σ
1) (16 qn)
T 1-1
11+ log ΣΣ
D
Pi go)
(15)
t=
Thus, by invoking (14) and (15), we get the regret bound by
V
V w0
AR
H T H-1
$ H OABHVOCT+
D2 (P Ho fch p
a
H 4
T ΣΣΣ
2A
Die (P Patta P pi
(0''AB22H's
Since the above derivation is for any policy pair (T' v²), we can show that a-revealing POMG is subsumed by the classes of both self-play and adversarial GEC class with bounded dgEG. We finally prove
O² (0'A9191133))
dGBC o o
a
4.4 2 where 5 =2log (1+
This completes the proof.
a²
27

---

B.4.1 Lemmas for Proof of Proposition
Here, we present and prove all the lemmas used for the proof of Proposition 6. All the lemmas presented here follow the notations of Proposition 6.
Lemma 3. In an a-revealing POMG, for any policy pair (T,, v), any vector I R and any Th Th-1 we have
v5
Σ 7h:8
(m S
|2l|1-
Proof. We first obtain
Σ
mO 1
m((T::)0nee) le (7,
Th-
where e; E S denotes the standard basis vector whose i-th element is 1 and 0 for others. Note that Enar (m(Th: e (T 7h-1) - Pr (Thelt Tich-1, 8:) 8 = 1. Thus we obtain
(n(T.)))eee) le, (1
VS |=]|1.
10|=111 < 0f ||ж|| s VSllo/1la ||=||1 s
which completes the proof.
Lemma 4. In an a-revealing POMG, for any policy pair (x, v) and any RO, we have
[M (on, an by ( an, bn) s V5 |||||
Σ
Proof. We first obtain
Σ
MM. (or, an, bn)olllololoooooooooo an, bn.
(on ag xxAAAB
Σ
Σ
é
My (O%. an by bn) an, bb)
Oh by j=1
Σ ΣΣ
Ma an, On le? 0) an, bn),
Oh,Og, bb j=1
where ē, is the j-th standard basis vector in Ro and e, is the i-th standard basis vector in R that we have
Note
Σ Σ
T (On, an, by On)nnes an by)
on ba bn 1=1
Σ
Pr(oj, on, an, bn ss)o an, bn)
an by 1=1
Σ
Pr(on, an, bn (1) an. bb)
Σ
olon, an, bn)
Og.0k.bp
28

---

Combining the above result, we obtain
Σ
Ma on, en le, 1e, az.ba)
aa da
j=1
t=1
8 0
vS |
||
< |0
| s vs
||]|| s
which completes the proof.
Lemma 5. The value difference in a POMG can be decomposed as
Val f
V u
HVS
H
[|
(i)a((m-))))) + 11 gol11
Th
Proof. Denoting r(TH) as the sum of rewards from h = to H on THe we obtain
V f1
V.
(priiet .ut (TH) - Pj" "
Σ
TM
H Pf (TH) P7. (TH)l
H Mi - Maa aiz boooo (TH).
Σ
Using the triangle inequality, we further obtain
H Σ
MMaa(oo1 a1.H d1 M (OI.H, 01.H b
H
Σ Am1
m m' (TH4)))( an, bn) - Mn an bn)) (T) (FH)
TH
+ |m (Tn) (T)))
where m (h+1::H) Manss(7 and q(Th-1) = Mn-1a(7h-1190. Note that Lemma shows that
Σ Th41:2
m' (T (M, an, bn) - MA(on, an,
T1sk)
VS (on
an. bn) MA an, (T))
and
Σ m' (TH)(Gh - (T)) s V5 11 qullı. 1-
TM
29

---

Thus we obtain
1
m' m' (T++1::) an, bn) Mn
an, an, (1))
TH
m (TH)(G) - go)l qoo)
H
m (7h+1:H) (M an, by.) Mr (on. on, ba)) (T"=
h=l
mm (T)))(b (o))
7M
H H
H
IIM - Mi)a(m--))lloon)) - =1100 -goli
Th
which completes the proof.
The next lemma gives the bound training error by Hellinger distances. Lemma 6. For any model f and policy o', we have
E
Σ
[MM an, bn) - MA an (T)))((- (on, an, bp; Th
2
Oh Rhiba
S
1-1
D
where S omits absolute constants.
Proof. By using (a +b < 2a² + 20 and the triangle inequality, we decompose the LHS into two parts to bound them separately. We have
Σ
E
Σ Oh dn
[1(M an, bn) Mn un, bn)) (on, an, bas Th
2
A-1
[M an. bn) (Tn-1) Ma an, by () }
2
Term(i)
+ 2
Ma an, (n - a
Th
Term(ii)
For Term(i), we equivalently rewrite this term as
Σ M (on, an, bn)g' (Th-1) Mn an
(Tm)
ΣΣ
[M an. (n)) My ar bnhh(T)l)
P 1 On on.
- -ono,, Un, bns Th 1)
30

---

We first consider the case when h <
H. According to the definitions of g and qn. we obtain
Term(i) =
E
Σ
Σ
(M, On, by ) (Ta-1) - (on, on, bn ((Ta))(T)))))))))))) 1]
OK andba
o' (oh, ans bhi Th-1) 2
Σ
Σ
Pr pro or Timh 0 do(an;
Th 1.. ih oh, aar
Pry.(on Fh- do bn)) (on, an bu: 7n-1)
Σ
PPrfi us (T) Pry." uf (T)] 2
|| S&A jr (I S 8D (P (), PT ()),
where Prij" (Th-1, on) denotes the probability of (T) if the actions are taken following (T', v²) and the observations follow the omission and transition process in the model f The first inequality is by the fact that the L₁ difference of two marginal distributions is more than the L1 difference of two uniformed distributions, and the second inequality is due to | Qli s (P, Q). Similarly, when H, Term(i) can be bounded as
Term(i)=
E
Σ
[Prs(on TT-1 do(an, bn)) Pry- (on TH-1, do(an,bn))
Th
Oh .n
o' (oH, as, byr; TH-)
Σ
Prij o
(TH-1, -Pr ox))
TH-1,0w
||P HH P
O- S 8D (P (T
F
For Term(i), Lemma 4 is used to give upper bound. Specifically, we obtain that
Term(i)
Σ
|M an bn)
((Th-1)))))))))))))))))))()))) ((
S
(Tn-1)) 2
(na-T)
a
Th-1
85 a²
<
P
ll <
D (Pr
f& PTih))
a
Combining the above results completes the proof of this lemma. Lemma 7. For any (0, b) E x Ax we have
2ABdVS
E The put
| I $ SS
Σ I S
Proof. We prove the former statement first. By noting that the 00_00/////// ((Th-)) = [Pr(s: [1-1) and o² o'(on, an by: Th-1) < 1, we obtain
|1 1ir- on 11
= =100% ((Th (on, an, byi Th Th-
8
$ Σ
Pr(s: | TT-1)2 5
1m1
31

---

Therefore the first statement in Lemma 7 is proven. To prove the second statement, we write
wh..J.oaa.bll
wh..J....bblllll
o,a j=1
0
ΣΣ
0,a, j=1
ΣΣ> o,a.b
Σ
(M an, bn) Mo ane hn
where the second inequality is due to || 112 S || 111, and é, stands for the i-th standard basis vector RO. Then we apply Lemma to obtain
ΣV o,a,b ==1
(on, an, bn) - (o an bn) On
2ABVS S
2ABOVS
2ABOVS
10 -
10
a
where the second inequality is by ||xx|1 S |||||
The proof is completed.
B.5
Decodable POMG
In this section, propose new class of POMGs, dubbed decodable POMG, by generalizing decodable POMDPs [23, 22] from the single-agent setting to the multi-agent setting.
Definition 9 (Decodable POMG). We say a POMG is decodable POMG if an unknown decoder function oh exists, which recovers the state at step h from the observation at step h. We have for any 1 < h H that
dn (on) 8h.
Given the decoder, we can define the transition from observation to observation as follows,
Pa. (on++ On, an, by)
Σ
O(on+1
88 (n(on), Ohy by).
Sh+1ES
Our next proposition will show that the class of decodable POMGs subsumed by the class of MGs with low self-play and adversarial GEC.
Proposition 7 (Decodable POMG Low Self Saal-Plla/AAdvssariaall GEC). For decodable POMG as defined in Definition 9, with the loss E(f.Ex defined in Definition for POMGs, we have
Decodable POMG C POMG with low self-play and adversarial GEC
with dere satisfying
dG = (FF0000(01)))1118)))
where 5 2oo (1+ (1+4 414411111)))))
Proof. The proof of this proposition is largely the same the proof of Proposition 6, except that the coefficient before ||>||] in Lemma and is changed, from v5 1, as proved in Lemma 8 and Lemma 9, Following the proof of Proposition 6 and using Lemmas 8 and 9 yields our result. D
32

---

B.5.1 Lemmas for Poof of Proposition 7
We present the lemmas for Proposition 7. These lemmas are analogous to Lemma and Lemma 4. For convenience analysis, define some notations follows.
Similar to the case of a-revealing POMG in Appendix B.4, we define qo. Thes ((T)) and q(Tx). We now define different observable operator as follows,
Mn (o, a, b) == Pi,,,,i
where e, R2 the basis vector with only the o-th entry being 1. With these definitions, one can show that
((T)) = Mnn, on by M (on an bn-
We define Mwss (Olche, Obsh', bicce) = My (onc; Ous, bie) Ma ax- 11)- ... MA (On, ah bn) and rewrite MH (OH+1:H 0h-1:HH bh+1:HH m 11+1:H bx+1:H) to emphasize that (0N++1:H 41+1.H bb+1:H) is a vector since MH (OH, ag bh) is a vector.
Lemma 8. For any RO, any policy pair (x, v), and any Th-1, we have
||
Proof. We can first bound the LHS as
Σ
Th-1)
ThaM
a. Pr( ua Th-)
Thell
0
c a Pr(TN+1H (T))o Th-1),
Thal t=1
where é; the i-th basis vector of the space RO. Since Emarn Pr(Te+1: (h-) $1, we further obtain
ΣΣ je ae Pr( (ant
i=1
5 Σ
E x =
|x|||-
This completes the proof.
Lemma 9, For any RO, policy pair (H, and Th-1, we have
Σ
bM S ||]|
of BEB
Proof. We can first show that
Σ
[M, (
AEEE
Σ DE0,aEAAbES
द x Pr(a, 10, 0,
33

---

Since DEED Pr(o: o, lo,,b)a(o,,, 7--1) & 1, we further obtain
Σ
Σ
e x P( 0 ()o Ta-)
oEO, OEO ==1
0
e ø = --|=||1-
i=1
This concludes the proof.
C Computation of w(,
In this section, we discuss the upper bound of the quantity w33pp%) for both FOMGs and POMGs. For FOMGs, the analysis can be adopted from Lemma 2 in [2]. For POMGs, we give the detailed analysis to show the bound (B3 ("), which is the first proof for the partially observable setting.
C.1 Fully Observable Markov Game
We can adopt the result from Lemma in [2] to give a bound for w(3,y") in the context of fully observable Markov games.
Proposition 8 (Lemma 2 of [2]). When F is finite, y is uniform distribution over F, then w(3,7 < log F... When F is infinite, suppose transition kernel Po satisfies Py- < Po and
dP
$ B, for e - 2/3 and B 2 log(6B2 /c), there exists a prior ye on F such that
aPo
w(3,y") < Be log (N (N (N6111((1/1)))
where v = </(6log(BB" /e)) and N()) stands for the e-covering number w.E.. the distance
d(f.f) = sup D (. b) Pr Py.( - Dito (P (p. b), Py s.a.b.h
To apply Proposition in FOMGs, V2D (P.R) S v - Q|I for distributions P, P,Q. R, so that the covering number under the distance d can be bounded by the covering number w.r.t. the & distance denoted as N1 i.e.
further show that (P. (Q.R) <
N(() s WG(22c),
where (e) is defined w.r.t. the distance
d(f.f')= sup [| 17,l-11,,,, b) s.a.b.b
The covering number under the l distance is more common and readily applicable to many problems.
Taking linear mixture MGs for an instance (defined in Definition 5), we calculate w4HH, pº), which is the term quantifying the coverage of the initial sampling distribution in our theorems. We first obtain that
sup (Pr.(118,,)) P. (s,a, s,a,b,l
a(s'.s, 01,m 0r Dy ds'
sup
e.a PES
sup | 8, a, 122dds/ 05,0 - 0p
s.a.bhh s'ES
sup h
f pr
(16)
34

---

where the first inequality is by Cauchy- Sehwhy- and the second inequality is due to
fres llo(s', a, b)llads' I 1. Since the model space is {o sup,, 1 ll I B}. under the & distance measure of
d2(J. sup
p 0r 0r.n
we have
N(C NG(v2c) & 1+ 2/2B
(17)
according (16) and the covering number for an Euclidean ball. Combining this result (17) with Proposition together, we can show that there exists a prior distribution p" with sufficiently large T such that
w(HHT. S
Hdlog (1 BT log ( (Tlog(T)))
C.2 Partially Observable Markov Game
this subsection, we prove the bound of p²) for the partially observable setting, inspired by the proof of Proposition 8 (Lemma 2 in [2]).
Proposition 9. When F is finite, pe is uniform distribution over F, then w(B,1' < log Fl. When
F is infinite, suppose distribution Po satisfies that for any policy pair (T,, v). PT. f-.H1 < Po and
||dP"." fr / /dP bloc S B, where B 2 1. Then S. 2/3 and B 2 loo (Bg( /e), there exists prior 1e F such that
w(B,p") S Be + log (N (N((O((B//)))
where v (ollog/6B2/// /c)) and (()) is the covering number w.r.l. the distance
d(f. f') sup D (J f. H) Dio
P
The assumption the theorem above covers the case when finite, where we choose Po to be uniform on S regardless of the policy. We also note that
aP
(TH) (T))
dP dPFrH((T))(TT)) dPo(TH)O(TH)
dP fr, (r.H((H)
dP H /dP 1l sup
sup
sup
dP dPo(TH)
which does not depend on the joint policy a v).
To apply the above proposition in POMGs, by the relation between different distances: DD (P, DR (Q, R)] S V2D [P] < A p for distributions P, Q, R, can show the covering number under the distance can be bounded by the covering number w.r.t. the & distance denoted as (1(c), i.e.
N(e) (V(
where (c) is defined w.r.t. the distance
di(sf)) = sup P
P F.
Such a covering number under & distance is analyzed in the work [78], generalizing whose results gives that POMGs with different structures admit a log-covering number log = ([O), AA,, [8], [S], H, log(1/e)). We refer readers to [78] for detailed calculation of log- covering numbers under di (..).. Therefore, we can eventually show that w4HT,, pd) ploy([O), AA,, [B], [S], H, log( (T)). Next, we show the detailed proof for Proposition 9.
35

---

Proof. When F is finite and p" is the uniform distribution on F, the proof is straightforward as we have w(3, p") S BE + log |F] for any and a uniform distribution p". Setting approach 0* completes the proof.
When F is infinite, we start by setting up 7-covering C(7) F w.r.t. the distance d(J: (' P.
s Pi (P f.H.
F.H. (P P ('H where y 0 variable to be specified. Since
f is covered, an f E C()) satisfies ((f,f" sup=,v R, ( (P..v PJ I r. We further define (7) = (uPo o (1 - p) E ((+)) and also py = vPo o + (1 18-ve P We note that dP aP
" 1l L. Then, obtain
8uP
D (Pai P H )H
=1 / ValuPo +(1 vi )dP.
f. S:.11
$ 11 (v/ ddp dP j. + (1-v) /
v
dP dP
1, J.H
/ /dpau J. dp H - v / dappddpp.
Di (Prr PE. f. ( +U
S
where the first inequality uses Jensen's inequality and the second inequality by supT, Die (T PT... (r) S 7 and 0 vaPdQ I To connect the definition of F(e).
f.H
we further invoke Theorem 9 from [55] and obtain
(PT. KL(P)- f m f.n) S C(Bfu) (P p. PT.,))
for any policy pair (T, where ((b) S max {I, blogh ties together, obtain
[1-vop2 } for > 1. Plugging the above inequali-
KL(P
J. [P
P..) (BB/))(++M)
(18)
remains to find a proper choice of y and v to obtain ((B/v) + v) S E. We choose v = e/ (elog((BB//)) and 7 = (6 B/v)). Given the condition B 2 we have
v = 6 log
6B
so that
V
6 log 6
log(
P
(19)
Given E $ 2/3 and B 2 1, we obtain
V <
6B
9B 9
namely B/v 2 9. We note that when b > 9, it holds that
blog b
blog
((b) < (1 vD2 <
b-2 < 3oggb.
Thus we have ((B/v) < 3og (/v). Finally, we obtain
C(B/v)(+ + v) < 2x((B/)) = 3log( B)
C(B/u) S
where the first inequality uses (19), the first equation uses the choice of 7, and the second inequality
uses ((B/v) S Blv). Choosing yd be a uniform distribution on Cr) completes the proof.
D
36

---

D Technical Lemmas for Main Theorems
In this section, we first provide several important supporting lemmas used the proofs of Theorems I and 2. We then present detailed proof's for these lemmas.
D.1
Lemmas
Lemma 10. Let u be any probability distribution over f F where F is arbitrary set. Then, By-u()) + log (f)) is minimized at v(f) x exp(-G(f))
Proof. This lemma is corollary of Gibbs variational principle. For the detailed proof of this lemma, we refer the readers to the proof of Lemma 4.10 in [64]. This completes the proof.
The above lemma states that v(f) in the above-described form solves the minimization problem ((F) Ey (G() + log v(f)), which helps to understand the design of the posterior sampling steps in our proposed algorithms. This lemma is also used in the proofs of the following two lemmas.
The following two lemmas provide the upper bounds for the expectation the Hellinger distance by the likelihood functions defined in (I) and (2) for FOMGs and POMGs respectively.
Lemma 11. Under the FOMG setting, for any t 2 1, let Zz' be the system randomness history up to the t-th episode, p (-IZt-1) be any posterior distribution over the function class FF with (.) denoting an initial distribution, and (T', (T',²") be any Markovian policy pair for Player 1 and Player 2 depending on fe p¹. Suppose that (s a bi. s/+1) is data point sampled independently by executing the policy pair (I', v²) to the h-th step of the t-th episode. If we define I,,(5) = 17 log (rh((hh4 18h oh b8)) with 17 = 1/2 as in (1), we have the following relation
E a Be (o a)
oh bh), Ps tn (1 ab, b%))
S Bep ΣΣ (DXU))- - -(( + log pt()t)
1-1
pP(st)
where E(n".u',h) M) denotes taking an expectation over the data (sh, ah, bt)) sampled following the policy pair (x" ,v²) and the true model Py. up to the h-th step at any t.
Proof. Please see Appendix D.2 for detailed proof.
Under the POMG setting, for any 2 1, let Zt be the system randomness history up to the t-th episode, p² (-12t-1 be any posterior distribution over the function class F with pd denoting an initial distribution, and (v²,v') ) be any general history-dependen policy pair for Player I and Player depending on f "5~pp p'. Suppose that Th (of, of b .... of at bj) data point sampled independently by executing the policy pair (T" v²) to the h-th step of the t-th episode. If we define L (ʃ) = 1 log (T() with n = 1/2 as in (2), we have the following relation
Lemma 12.
Σ 4=1
E. E2 ppp D (P PT
fthh
H
P'(Ft)
I Ez-- I.
Σ h=1El
(L:(1) - (i(()) + log
(ft))
where f.h denotes the distribution for Tr. (01, a1, bi, .h....,,o.. Oh, an bn) under the model Oy and the policy pair (x, v) up to the h-th step.
Proof. Please see Appendix D.3 for detailed proof.
The next lemma shows that when the model is sufficiently close to / with the distances employed in Definition 2, the following value differences are small enough under both FOMG and POMG settings.
37

---

Lemma 13. If the model I satisfies su (PPr 1o.l-11,,00 s, f)(l s,,,,)) S for (P
FOMGs and supa,y KL2 (PT f (.H) S for POMGs, we have that their corresponding value function satisfies
Vi- S 3HE
sup - V7 & 3HE,
sup(Vp" - -V, 3HE.
Proof. Please see Appendix D.4 for detailed proof.
Finally, we show that when the model is sufficiently close to f*, will obtain that the following likelihood function difference is small under both FOMG and POMG settings.
Lemma 14. If the model f satisfies suph,a,a,b KL (IP ( fe (-1-
(o,,s,,,,, s,a, b)[lPp F s, a)) S for
FOMGs and supa.u KL (PT.", [P hood function defined in (1) and (2) satisfies
f.H f.H) S & POMGs, we have that their corresponding likeli-
B(L)()) I(((S) S nE?
where the expectation is taken with respect the randomness in L.
Proof. Please see Appendix D.5 for detailed proof.
D.2 Proof of Lemma 11
Proof. The proof Lemma can be viewed as multi-agent generalization of the proof for Lemma E.5 in [83]. We start our proof by first considering the following equality
p'()t)
E Sropt
ΣΣ
(LX(F)) (((())) + log p (f')
Ps- (p.,nss/+))) + 11/ aip 69))
2²(1")
= EE2-11B Finnpt pimpp
log
p A ( h+ 8/ O2 b%) + log
pft))
J=1
Next, we lower bound RHS of the above equality. We define
(8 1/ an (i,)) T. = log p M (s) (s/+1 // a/., D
T = T2
log Bar w we Py- (exp(expTptttt (f)).
where Ee ..).)) denotes taking an expectation over the data (s), 0j B/ sh+1) sampled following policy pair (I², v²) and the true model Py- to the h-th step with sh.11 ~ F , aj (g))) at round Then, will show that Ez.-1 ex ~E==1
H E [x((i)) by induction, following from
[80]. Suppose that for any k; we have at that E [exp(E === Σ (x)( = Then, at k. we have
11 ΣΣ (AA
)1
exp Σ (ACN) ]
Eza
exp
Ez -1
exp
Σ
M==
M1=1
H 1-1
H
Eza-1
cxp
Ix(f)
E Epaapk
Bi ut py
exp (ER(1)
Am
ΣΣ TA.C)) )
K-1
Ez
exp
-1,
where the second equality uses the fact that the data is sampled independently. the third equality
due to Exzx,x u .p, .N) (xp(I = E - Pyy..M .)) cxp(L,) (xp((x(()) (f)) (xt w [Ix (f)] =
by the definition of [f),), and the last equality by 1Ez-1 ee D E. [.) = in the
above assumption. Moreover, for & 1. we have trivial result that Ez (
38

---

Bytnp Ih== Ee p..h) exp(I) = 1. Consequently, we conclude that for any k. the above equality holds. Then, when k = t 1, we have
Σ
= V=1
E2 Ez--1
exp
(20)
Furthermore, we have
(1) + log D'(F")
Ezi ptne
(D(
T log p(f)
2 Ez--1 inf B
P
(f(
H t-1
= - log E fup exp
Σ
h=1
2 logo Be exp
ΣΣ I
=0,
1==1
where the last inequality is by Jensen's 's inequality and the last equality is due (20). For the first equality, we use the fact that the following distribution the minimizer
H ΣΣ TACT)
Tw(s) + logp" (oss((1)) -T(() exp
p() x exp
(f) exp
Et= (2(()) H C df
pf() exp
Et EE)T))
p(f (f) exp
Esppo exp
E E
according to Lemma 10, such that plugging in the above distribution leads to the first equality. Thus, according to the definitions of Eú and T. have
H
t-1
PP ( 8/, /3 b1.)
(t)) pa (ft)
E Era
n log
+ log
py ( h41 1/) o22 b%)
h=1 cml
11
P P aj. 1%h) log E (T) P exp (1log pP. (sh 10h, oi 0%,)
> Byp
h=1
Moreover, to further lower bound the RHS of the above inequality, by the inequality that log x S x-1 and the setting 77 = 1/ we have
P,, 1sh ah B8,) Praa(s 10h oh 0i) PP P. (8% 41 10h a 0%)
log ( P) exp
log
= log E E
18h ag 19,) TP yr
1/h aj 0%,) y.n ( (8h
2 1 E Pe
IP (8
18 ar. 0%,)
= 1 - E Fi wnnh)
IP (s)ss,
si, oh 62 )PP f (s|sf, 0% dss
= Be An (D (-1sh ahh bR), P. (:1s). ah b,1)),
39

---

where the last equality is by ( pa Here ((rt....)) denotes taking expectation over (s), a/ b/, sampled following the policy pair (T v2)
-
and the true model -- to the h-th step but without the next state $ generated by y- (-1s ai b/)
at round t. In the sequel, combining the above results, we have
ΣΣ 1=1
(LA()) IR(") + log p'() TP(St)
Ezt-1 pepp
H
E (m (P b)) b ah. 8(,))
This completes the proof.
D.3 Proof of Lemma 12
Proof. The proof of Lemma 12 is similar to the proof of Lemma 11. We will give a brief description of the main steps for our proof of Lemma 12. We start our proof by considering the following equality
H t-1 ΣΣ
(4A00) (M(F)) + log p((*) (f())
Ez ptmpp
log Pr.A(Th)) PyA((T))
+ log p((l9) pf()))
Bgg 1R prrpe
k=1
Next, we lower bound RHS of the above equality. We define
(T.( I2( = nog Py)
= log Bi J.) (exp (f))),
where (ur.....)) denotes taking an expectation over the data o sampled following the policy pair (x', v²) and the true model f-- to the h-th step at round 1. Then, we can show that
H ΣΣ
T4(0 log p'(S") (ff)))
E gt prnp'
0,
b=1==
following a similar derivation as (20) in the proof of Lemma 11. With setting = 2. this result further leads
log E B exp
log
Pp PP
pai.en f.h
(Th)
P
2
Ba M)
E
Be an
(P)xM(T))
/P7-: (PT
1 V Pi (TT)
f.h (T.)dd
In the sequel, combining the above results, we have
H
Σ
E Ez- 1 E (emp'
Di (P
fth 1))
A=1
+ log p((Pt) ((+t)
Ezi-1 Eypppt
Σ
h=1=l
This completes the proof.
40

---

D.4 Proof of Lemma 13
Proof. We first prove the upper bound of VV+"" - -V7 for any (T. and under FOMG and POMG settings separately.
For FOMGs, we let Vz." Vi and V = Vg Then, according to the Bellman equation that 17. (8, b, = a,, b) + (Prn(+s,,,, ())+(()) and also f.b. (s, -
(.))... 10, (s, b)], we have
VT:t" -V
Bn (-1s b1) (2) - (1, 52 (-))
s H (+Is,, (1,b) b1) F, a1, b1)1l, En,uyy (722(22) V7,2(s22)
(recursively applying the above derivation)
H
S &HE f
Σ
IP an, bn) - Py,a(-ss), an. bn)ll
hm
which further leads
V7
< HER u.P
| (111//1 an: bb) (t ar. bn)ll
$ H² sup
||P ( ss a, b) -Pyn(-ls, b)ll
b,saa,b
$ 3H sup KL KL (P)r,( b)l a, b)) s 3H h,s.a.b
where the third inequality is by Pinsker's inequality and the last inequality is by the assumption of this lemma. On the other hand, we can show that the above result also holds for POMGs. Then, for this setting, we have
VT- 17
lionAKB (PT. - (TR(TH)) НH
Σ hml
ralonn and bn) bn) dTH
[(oAAM6]" PT - P (T drH
drH
H||PT (TH) -P (Tm(ll
3H sup KL (r (n J. 3He.
n.
To unify our results, we enlarge the above bound by factor of H and eventually obtain that
V
V7* <
3He
for both FOMGs and POMGs. Moreover, by the properties of the operators min, max, and max min,
we have
V7. V7 max max V max min VT.
sup V V < 3H²s.
sup Vi*+t) min V min V
sup Vy+" V & 3Hf
sup(Ve." - VV sup f
Σ
V
sup J.y
V v < 3H'
This concludes the proof of this lemma.
41

---

D.5
Proof of Lemma 14
Proof. We first prove the upper bound under the FOMG setting. By (1), we know that (f - (f) = log P (s sh ai. bj,) 17 log f, 1// ag. b),)
Py (
s/ o/, b(,)
log
P yy, (s) 4
which further leads to
P Pr.a(shtt
((LA(F)) - -((f))]
E log
( 8/ oj (8,)
Py- Py 1// aj 8%,)
B aj M, E s PPrsallff .8) log Py ( 1 10 ah 69,)
S sup KL ( (. (.-s,, (- s, s.a.b
S
where we use the definition of KI. divergence the first inequality and the last inequality is by the condition that su,6, KL (P)- (
f- |,,
5)llP (-1 s, a, b)) E.
We next prove the upper bound under the POMG setting. According (2), we have
= 1 P (T)) 17 log P Py((Th) = 1o Pyrm(())) P (y.(
which further leads
Pr-((TH))
- E
log
P (T))
gith
f- (Th)
7)
E log
P o0
(Th)
KK
|P
f.A
where the definition of KL divergence and the relation between P S.b. and P Now consider lower bound (L
f-
||P
S.H
We have
F (TT))
KL(P w
|P p E T/
f.ll
(t
log
f.8 (T+)
pr
J-hh (Tf)
Pr (T+I (T)) Pry (Th (Th)
E +pppttot
log
+ loog
T/e p.
P7 (TH)
Pr.. .u
(144 ITA)
KL(P J-
+
T pr E Thit (ptt log Pr (Tee (T))
f.b
(112)
KL(PT' f-th
|P
+
Th ph-pp (Pr))) on (17))) (177))
fib
KKLPP f-Ah fA
where Pr af denote the probability under the model f and the policy pair T', v², the third equality is by the definition of KI. divergence, and the inequality is by the non-tieatiivty of KL divergence. Therefore, combining the above results and the condition sup..,. KL (PT..
Jr [ j,n) S E, we obtain of uu p 5r J.H S n
|EL) -((0")))((0)))) S mLLLPS
This concludes the proof of this lemma.
42

---

E Proofs for Algorithms and 3
In this section, we provide the detailed proof for Theorem 1. particular, our proof is compatible with both the FOMG and the POMG settings. Thus, we unify both setups in single theorem and present their proof together this section.
To characterize the value difference under models f and f we define the following terms, which are AVT (8) == V (8) (s),
(21)
and
(V;(s) VV
(22)
In addition, we define the difference of likelihood functions at step h of time as
( -i(()) - (f
(23)
Then, the updating rules of posterior distribution in Algorithm have the following equivalent forms
p²()) x (') mi +
Σ m
h=1
(-1
= p'(f) x (f) exp mAv +
(24)
c=1 h=1
and
d'(J) x expl
1-1 H ΣΣ ALTO A=1
- d'(f) x exp
(25)
since here adding or subtracting terms irrelevant to f, i.e., V Vy., and [f") within the power of all exponential terms will not change the posterior distribution of f.
To learning sublinear upper bound for the expected value of the total regret, i.e., E(Reg"((T)
ET= IV Vy- "] for the self-play setting, we need to execute both Algorithm and 3, which are two symmetric algorithms. We can decompose Reg (T) as
Rog (T) = Rog (T) + Reg (T))
where we define
Reg Reg := Σ Vj. V
Reg Peg)(()) = Eive - Vj-].
t=1
In fact, executing Algorithm leads to low regret upper bound for E[Regi (T)) while running Algorithm 3 incurs a low regret upper bound for E[Reg ric, the derivation of their respective regret bounds is thus similar. In the following subsections, present the proofs of Proposition 1, Proposition 2, and Theorem sequentially.
(P (T)). Since the two algorithms are symmet-
E.1
Proof of Proposition
Proof. We start our proof by first decomposing the regret as follows
Regip (T)
V7.
V
VT. *1.
Term(i)
TermCii)
43

---

Our goal is to give the upper bound for the expected value of the total regret, which is [T)] Thus, we need derive the upper bounds of [i]err(ii) and [[Term(ii) separately. Intuitively. according to our analysis below, E[Term(i)) can be viewed as the regret incurred by the updating rules for the main player in Line and Line 4 of Algorithm I, and E[Term((i)) is associated with the exploiter's updating rules in Line 5 and Line 6 of Algorithm 1,
Bound [[Tem((i). To bound (T)rm(())), we give the following decomposition
Tirm(i) =
Σ
IV3
V
VTL
V
y. 20
7
f
7
t=1
[V-
V
17
V
V .²
V
f=1
T
AV y
ul
V
where according to Algorithm 1, we have (T², x²) argmax, argmin, 7 iie., (t) is the NE of
7: V Thus, the second equality is by (22), and the inequality is due to
min V
According to the condition (1) in Definition for self-play GEC and the updating rules in Algorithm setting the exploration policy pair as of (T', 2²), and pt j for Definition 1, we have
T
T
my . <.)))²
dGEC
ΣΣ
E
+ (deEcH))) eHT
1=1
H T
Σ Bi
.(h)) .
+ NdGEC + +H + eHT,
where the second inequality is due to /oy
S 1x2 + 22². Combining the above results, we have
T
H
Term(i)
1
Σ E (
x) .ch)
Σ AV
71
1=1
tm1
+ ndGGEC
2H (dG +eHT.
We need to further bound the RHS of the above equality. Note that for FOMGs and POMGs, we have different definitions of {(f, Ex). Specifically, according to our definition of e(f, (,), for FOMGs, we define
es" (h) Die (Pyr (155)) ahe Uh), P in (-18% ajs Kj)),
and for POMGs, we have the relation
E or ue (.)) = Dise (F. p .00
T' s
On the other hand, for the two MG settings, we also define (f) as in (1) and (2). According to Lemmas 11 and 12, unifying their results, we can obtain
H
Ez-- Eegnppp
ΣΣ
E e An A shh)
H
EE4 - log p'(F")
<
Ezz-1 mpp
A=
44

---

which further gives
Ez--1 Rignn mpp
-M
B (a My Eye(T ,5))
1-
p' p²(F')
$ Ezt-i BBg'
n mAV
AL)(F)) + log
2
h=1
log (8)
-2t--1B7 upp
-MAV
- - log (5)) (00
h=
where == ((*) is defined in (23). Note that in the above analysis, we slightly abuse the notation of πO and u², which denote the Markovian policies for FOMG and history- dependent policies for POMGs. Therefore, according to Lemma 10, we obtain that the distribution
p'(f) x exp navy
(F + log logr'())
h=
=f exp
exp
nAV
Σ Σ (
minimizes the last term in the above inequality. discussed in (24), this distribution is an equivalent form of the posterior distribution updating rule for p' adopted in Line 3 of Algorithm 1. This result implies that
H
p'F
Ezi- E pinppt
-n
ALL
+ log
(F)
A=l
1=1
AIX(F) + log p(f)
Ez--1 inf EnFp
m
AV;
(f(
F
k=1
By Definition 2, further letting p. = (f) 1(f E F(e))/P"(F(e)) we have
p(f) ALI(F) + log (f(
Ez inf /Np
-nAVi
1=1
H 1-1
ALX(F) + log P()) pP())
$ EEz--EEAap
-MAV;
ΣΣ
h=11=1
$ (3H2m + 7HT) log (F(())
$ w4HHTT,p")
where the second inequality is by Lemma 13 and Lemma 14 as well as e S 1, and the last inequality by our setting that 17 and Ho1 T. Therefore, by combining the above results, we obtain
w wHH,,''0 AddFEcl + (dGEEc eHT 4
((Tem(()))
<
m
4 de
(26)
where set HT deec. 1/VHT for self-play GEC in Definition 1, and 71 2 (WHT, DTTTT Since ciated with = 1/VHT by Definition However, our analysis in Appendix shows that this setting only introduces log I factors in dGEC in the worst case.
1/VHT, the self-play GEC desc is defined asso-
45

---

Bound (i)).. Next, we consider to bound (i))).(i)). We start by decomposing Term(i)) as follows.
T
V
Tiim(ii)
+
1
T
T
1=1
where the second equality is by (21) and the fact that y argmin, 1
In addition, according to Definition and the updating rules in Algorithm 1, setting of = (Tr k2)), o² 1. we have
Vasee sec
E Rornself ( {m))]
1/2
dGEC
ΣΣ
2 (dGEcHTT) cHT
h=
E Mn (()))))))))))))) + 12dGEC + 2H (dGECHT)) + +HT,
where the second inequality is due vay S 72
x² + v22. Thus, obtain that
Term(ii)
ΣΣ
( My (('
7/2 A=1
T
+ 12dGEC + 2H (dGEcHH))) + eHT.
+ Σ
AV t=1
We further bound the RHS of the above equality. By the definitions of ((f.Ex) for FOMGs and POMGs and also the definitions (f) as in (1) and (2), according to Lemmas 11 and 12, we can obtain
E zc-1 J' J'mp: Br
AV
ΣV
E ml as my
4=1=11
AL log ('(L")
< Bz 1, Ngt Egerug
AVV
12
((((")
H H
(L) + log {(f) pP())
Ezt- npt inf Bing
12AVT
ΣΣ
where the expectation for / ~ p' exists due to that n' is computed based on I and also according to Lemma 10 and (25), the last equality can be achieved by that the updating rule for the distribution gf in Algorithm i.c., equivalently
(-mAVT + E ALE() + log
('()) x exp
= (~MAA
ΣΣ ALACA).
h=l
can minimize Eyng 22 Σ/= Σt=1 ALA + log a(f)
46

---

By Definition 2, further letting := : (f) 10 F(EE) with & S 1, we have
ALE log q(f) {
inf Bag Ezi 1J Apt
1241;"
ΣΣ
9
1=1
1-1 A + log {()) (f)
$ E 22- j'm Bug
12A1
h=1
$ (3H + nHT) - log (F(())
< w(HT,, ,
where the second inequality is by Lemma 13 and Lemma 14 as well as E S 1, and the last inequality by our setting that 17 and H I T. Therefore, combining the above results, we have
E (TTem(())) v w (HT.9))
72dGEc + 2T) + cHT
72
S 4G HT WAHT, 99).
(27)
where we set HT doEc. e = 1/vHT for self-play GEC in Definition 1, and "22 =
2 2 wAHH,, g
Combining Results. Finally, combining the results in (26) and (27), we eventually obtain
E[Regi (T)) = [[Term(i) + B[Term(ii) S (GV/dccHTT((AAHT) pP) + w(HHT,,9))
This completes the proof.
E,2 Proof of Proposition
Proof. Due to the symmetry of Algorithms 1 and 3, we can similarly bound E[Reg (T)) in the way of bounding E[Reg (T)) Therefore, this subsection, we only present the main steps for the proof. Specifically, by Algorithm 3, we have decomposition as
Reg
Ví-
Term(iv)
Term(Gii)
Bound E (Term)(i))). To bound (iTer)(iii)), we give the following decomposition
Term
V
Vzlee
+
VI
Vi-1 V lv +
V
V
Val
V7-1
T
AV
VI'
Vz
1=1
where according to Algorithm 3, we have (TT vn) argmax, argmin, Vir" which thus leads to
max
According to the condition (2) in Definition for self-play GEC and the updating rules in Algorithm 3, setting the exploration policy pair as of (x', v²), we have
( 'e f&.1
+ ndGECC + 2H (dcecHIT) + eHT.
E v en eSe(s"
4
h=
47

---

We need to further bound the RHS of the above equality. For FOMGs and POMGs, by their definitions of E(f.En as well as Lj (f), according to Lemmas 11 and 12, we obtain
Ez Byg upp
71 MAVE
B .Eh)
7
H ΣΣ A4A0) + log p'(F') pT(T))
< Eg 1
E,, s'mppt
MAV.
h=1==1
where (f) (f) (f is defined in (23). According to Lemma 10, we obtain that the distribution p¹ defined in Algorithm equivalently
H -M + E ALAA
(f) x (f)
k= c=1
minimizes the last term in the above inequality. This result implies that
t-1
log P'(F')
E Bzr- Ey
ALA
mpt
p²(F')
1-1 (f + log p(f)
Ezi- inf IE gmp
MAV
ΣΣ k=
(f)
By Definition 2, further letting p = (f()
1(f E ((=))/P((F(e)) we have
H 1-1
ALKU) + log p(f)
Ez--1 inf E SNp P
nAV
Σ
zP(S)
h=l ==1
1-1
ALI(F) + log p(S) (f)
< Ezt-IE JND /~D
AAVi ΣΣ
h=
$ (3H n HHH) log log (F(())
S (wHITT
where the second inequality is by Lemma 13 and Lemma 14 as well as e S 1, and the last inequality by our setting that 77 and H:1 T. Therefore, by combining the above results, we obtain
(ermmii < w HT. (HT HHGEC + (d) cHT
71
4
< (TW
(28)
where we set HT doEc. = 1/VHT for self-play GEC in Definition 1, and m
Bound B[Term(iv)). Next, we consider bound E[Term(iv)) as follows.
Term(iv) LivA
VH
VI'
f
T
T
AV
v
where the second equality is by the fact that x² argmax, V By Definition and the updating rules in Algorithm 3, we have
according to the updating rule.
f
( e
E o Joy ()(((( + 12dGEC + 2H (dGEcHI)) + eHT.
hm
48

---

By the definitions of (h) for FOMGs and POMGs and also the definitions of L (f) as in (1) and (2), have
H
E 21-1 J Nmpp' Bliing ~22V L
(a
e .sh)
A4 log d((())
3 E y I -
AV
(()
h=1
(T log {()) (f)
= - J Nur inf inf gigg
Σ
where the expectation for j ~ p² exists due to that v' is computed based on J and also according Lemma 10, the last equality can be achieved by that the updating rule for the distribution q' in Algorithm 3, i.e., equivalently
d'(f) x ('))
12
ΣΣ A
can minimize E -nav, - E ()) log a(f) q((
By Definition 2, further
letting q = (f) 1(s E ((s))/o((F(()) with 1, we have
H H- r-)
ALL + log {f)
Ezi-1 10--117ppp ~pp
inf in grg
A2
ΣΣ
ạ
4=1==1
H-
{() (f)
$ B 7' E Bg
AAV
ΣΣ (zR log
h=1 1=1
< (3H² + nHT)= log (((E)(F(E)
S (4HTT,
where the second inequality is by Lemma 13 and Lemma 14 well S and the last inequality is by our setting that and Ho S.T. Therefore, combining the above results, we have
w (HT,
12dGEcH HT) eHT
E(Term(iv)) <
72
S 44 w(HHT,
(29)
where we set HT > deEC, c = 1/VHT for self-play GEC in Definition 1, and 722 = 24H(T4 (IIGHH,TY//ddde PdYT/daRC.
Combining Results. Finally, combining the results in (28) and (29), eventually obtain
E[Rege = [i(erm(iii)) + E[Term(iv)) < ( (4HHT,
This completes the proof.
E.3
Proof of Theorem 1
The proof of Theorem is immediate by the relation that Reg*P(T) = ReggP(()) Reg (T). Thus, according to the above proofs of Proposition I and Proposition under the conditions in both propositions, we have that
Proof.
E[Reg RRgg E[
< 12 do (w(AHTT, #w (AHT,
This completes the proof.
49

---

Proofs for Algorithm 2
In this section, we provide the detailed proof for Theorem and unify the proofs for both the FOMG and POMG settings together.
We recall that the value difference and the likelihood function difference are already defined in (22) and (23), which are
AV7 V7 - Vi- ( IA()) - (1*)
Then, similar to (24), the updating rules of posterior distribution in Algorithm 2 have the following equivalent form as
r'(l) (f) exp exp [vvj
m
t- H
- p'()) x (f) exp hAV + Σ AE(
(30)
since adding or subtracting terms irrelevant to f. i.c. Vj. and (f,()), within the power of all exponential terms will not change the posterior distribution of f.
F.1 Proof of Theorem
Proof. bound the expected value of the adversarial regret Reg ady (T), i.e., E(Readd we first
decompose the regret Reg adv as follows
T
Reg Rdy (T) = Σ IV-
Vi.
Σ
Vy.
V
V
T
T
AV
+
Σ Ví. Vzt
1=1
Furthermore, for the term ΣT
Et=llV
V7-" we
we have
V vz
1=1
Vaveee we
where the above result by (I', argmax, argmin, V i.e. (x is) is the NE of VJ" according to Algorithm and also due the relation that
min Vx ft
V
fI
Thus, we have
T Reg adv (dggdv(T)::) - Σ
-V
AVE
tml
tml
50

---

According to Definition 3 and the updating rules in Algorithm 2, setting Txxp = (T x²), and ((f', = (IP (*M (. 0h Py a (-1sh, 0/ 6()) for Definition 1, we have
My c.)) bl 2 (dGECHH))) elTT
dGEC
ΣΣ
h=1t=
H T
tn M) (()) .5)) + ydGEC + (dGEcHH))) + +HH,,
4
h=1
where the second inequality is due to vay S x2 + 1v Combining the above results, we have
H ΣΣ
Regady
adv (I) S
B ( ((f
ΣAv
ydGEC
2H HT) cHT.
4
For FOMGs and POMGs, we have different definitions of (n) According to (3), for FOMGs, define
( = Die(eraalls ai b.). pr (-15h ar bj)),
and for POMGs, the definition of ensures
woy (h) Die (P fhh P ) For different MG settings, we also define (f) as in (1) and (2) which are
Lf(( 17 Po (, s/ aj b%)),
[ n log (T))
Then, combining Lemmas 11 and 12, we know that the following result holds for both FOMGs and POMGs,
H L-1
Ez 1 Eginpp
Σ
E
E
1-1
(2(0T)) + log D'(S2)
< Bzz- Bggnpp
(fft)
which further leads to
1-1
Ez 1 Bpa
~VV
B (( EEh
H
AL + log D'(Pt)
< E EEzi-1 Byenp'
AVV
(F(()
k=
H EEALOP
E Ezz-1Bpprpp
AV
log log log (ft
h=
where = - (1*) as in (23). Therefore, according to Lemma 10 and (30), we know
that the distribution
H t-1
p'( x exp 7AV ΣΣ
(L) + logr"(1)
h=1.m1
H t-1
=xx(
(ΛVV) +
ΣΣ ALL())
Aml 1
51

---

minimizes the last term in the above inequality, which is the posterior distribution updating rule for p' adopted in Algorithm This result implies that
p(()) pf()))
Ez E Agperp
-7VV3
ALA(F) + log
H t-1 (
log p(f) pP(F)
Ez--1 inf E Srup
~vv
ΣΣ k=1
For the adversarial setting, we define F(e) as in Definition 2 similar to the definition of F(s) in the self-play setting. Further letting p pO (f) 1(ʃ F(e))/p"(F(() with S 1 and be associated with F(e), we have
t-
(1) + log p(J) (f(
Ezz-1 inf Bypp
AAV
Σ
Σ
A= c
ALR(f) log p(f) pf(
$ Ez 1iy
-vAV7
$ (3H2 + nHT)E - log logp'((((F) (F(E))
S w(4HT..p )
where the second inequality is by Lemma 13 and Lemma 14 well E < and the last inequality is by our setting that and _ T. Therefore, by combining the above results, we obtain
E(Rog adv (T)) w (4HT, HdGECH (dGECH)) cHT 4
7
S 44v dGEc w(HTT
where we set HT > dGEC,
1/V/TT for adversarial GEC in Definition 3, and 2WHTT pdYT//GBC- Note that since we set 1/VHT, the adversarial GEC dGEc is now calculated associated with 1/vHT by Definition Further by our analysis in Appendix B, know that this setting only introduces log T factors in dgpc in the worst case. This concludes the proof.
G Other Supporting Lemmas
Lemma 15 (Elliptical Potential Lemma in [1], Lemma 11). Suppose {ár is sequence in Rd
satisfying || 1, and An is positive definite d d matrix. Let A Ao Ei Φ.0.. Then, the following inequalities hold
det Ar det Ag
det Ae det Ao
log
min {Ø) (A,-1)- S.,, 1) S 2 log
Lemma 16 (Estimation of Elliptical Potential [38]). Given X and (dete2o with l|oella S denoting A, = AI Ei=1 6.0, then o, (A--1) bb. is upper bounded by
3d
log 1+ Alogg) (
1
log 2
Lemma 17 (&2 Eluder Technique [13, 83]). Suppose that {wes E Rhhneemo {xr, e
Rd )n and distributions (pr Auj satisfy
E'=l Binp. (E/=1 I 1), n
Erapy 1.,,5113 < R2
52

---

Ej= 11 l12 S Rw.
for any 1 S & S T. Then, for R. > O, have
1/2
TR Re
min R2 E Esups
Σ ==1
2dl
RTT
+
Σ 71
llog (1
R
t=1
t=1
53


Reviews:
[{"review_id": "lW1kwbh95a", "reviewer": "Reviewer_Gu3i", "summary": "This paper investigates posterior sampling algorithms for competitive RL in the context of general function approximations. The authors propose the self-play and adversarial generalized eluder coefficient (GEC) as complexity measures for function approximation, capturing the exploration-exploitation trade-off in MGs. They further provide low regret bounds for proposed algorithms that can scale sublinearly with the proposed GEC and the number of episodes T.", "questions": "Please refer to the Weaknesses section.", "limitations": "No.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Two new generalized eluder coefficients are proposed as the complexity measure for the competitive RL with function approximation.\n2. The authors also propose a novel model-based posterior sampling algorithm with self-play to learn the Nash equilibrium with provable regret bounds.\n3. The technical contribution of the paper looks solid.", "weaknesses": "Currently, readers are hard to follow the technical results in the main paper. It will be better if the author could include some explanatory parts for explaining the technical details intuitively, so as to highlight their technical contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Gu3i for the valuable advice and questions. We will address your concerns below.\n\n**1. Explain the technical results intuitively and the associated contributions.**\n\nWe provide the intuitive explanation by elucidating connections between the subsequent four aspects:\n\n**(1) Complexity conditions:** Our paper defines two general complexity conditions, the Self-Play GEC and the Adversarial GEC, for competitive reinforcement learning (RL). Since we consider a Markov game setting, in contrast to the single-agent setting, our definitions of the complexity conditions in Definitions 1 and 3 reflect the competitive nature of the two players via the defined sequence of the policies and fit the two important Markov game scenarios, i.e., the self-play and the adversarial settings. These conditions are not proposed in prior works and cannot be directly generalized from the single-agent setting. The inequalities in these definitions have a particular meaning: the left-hand side of the inequality is the prediction error defined based on the value difference while the right-hand side is the training error with a multiplicative factor $d_\\mathrm{GEC}$ defined on a problem-specific loss function plus a small burnt-in error. We use these conditions to characterize the exploration hardness of online competitive RL. Let $\\mathcal{F}$ represent such model classes. Intuitively, a sequence of approximation functions in $\\mathcal{F}$ satisfies that under the self-play or adversarial scenarios, if they induce small in-sample training error on a collected well-explored dataset, then the out-of-sample prediction error on the next trajectory generated is also small. Interestingly, as we show in Section 5, we discover with detailed proofs that many well-known function classes for function approximation in both fully observable Markov games (FOMGs) and partially observable Markov games (POMGs) can be subsumed in our defined Self-Play GEC and Adversarial GEC function classes with different dimensional factor $d_\\mathrm{GEC}$. We can even propose a new function class named Decodable POMG that can be covered by our framework.\n\n**(2) Algorithms:** The definition of Self-Play/Adversarial GEC motivates us to design algorithms based on posterior sampling. In our proposed posterior sampling algorithms, we assign a larger probability to a model $f\\in \\mathcal{F}$ if its in-sample training error is small. Moreover, according to the characteristics of the self-play and the adversarial scenarios in a competitive setting, we design algorithms from different perspectives. In particular, in Algorithm 1 and Algorithm 2 for the self-play setting, where we can coordinate both players for learning, we have a two-step posterior sampling strategy, where the first sampling step for learning the Nash equilibrium policy and the second sampling step is for constructing the opponent's best response where the opponent assists by exploiting the main player's weakness. On the other hand, in Algorithm 3 for the adversarial setting, since the opponent's policy cannot be controlled by the learner, we do not have the second sampling step, which thus leads to different algorithm designs. We note that our self-play and adversarial learning algorithms are the first unified methods considering both full and partial observability.\nMoreover, in the construction of the posterior sampling distributions in all the algorithms, we add and customize the optimism terms in terms of the different learning scenarios, i.e., $V_f^*$, $V\\_f^{\\pi^t,\\*}$, $V_f^{*,\\nu^t}$, for learning efficiency in our proof. Moreover, proving the regret bound itself requires a careful analysis of integrating the Self-Play/Adversarial GEC, the loss functions for FOMGs and POMGs, optimistic posterior sampling, and the self-play and adversarial algorithm frameworks in a unified perspective.\n\n**(3) Main regret results:** For self-play and adversarial settings, under different learning regret metrics, we prove the upper bounds of the proposed posterior sampling algorithms by incorporating the newly proposed Self-Play and Adversarial GEC function classes and the associated complexity conditions. Intuitively, in both Theorem 1 and Theorem 2, we can achieve near-optimal $O(\\sqrt{T})$ bounds in terms of the number of episodes $T$, which justifies the statistical efficiency of our algorithms. Moreover, the results have a dependence on another two factors, $d_\\mathrm{GEC}$ and $\\omega$. The factor $d_\\mathrm{GEC}$ as defined in Definitions 1 and 3 represents the complexity of the Self-Play and Adversarial GEC function classes, whose value can be instantiated in concrete example subclasses as elaborated below. The quantity $\\omega$ measures how well the initial prior distributions cover the optimal model $f^*$, which thus further reveals the size of the function space $\\mathcal{F}$. In fact, we can prove in our supplement that when $\\mathcal{F}$ is finite, it equals the value of $\\log |\\mathcal{F}|$, and when $\\mathcal{F}$ is infinite, it is the log covering number of the space. \n\n**(4) Examples:** In Section 5, we present a bunch of examples for approximation function classes in both FOMGs and POMGs. In the supplement, we provide detailed and rigorous proofs to show that all these demonstrated classes are subsumed by our proposed Self-Play and Adversarial GEC classes, indicating the generality of the proposed GEC classes. We additionally provide a new function class named Decodable POMG and show that it can also be covered by our proposed function classes. We eventually calculate the concrete relation between $d_{\\mathrm{GEC}}$ and the specific complexity measure in each of these classes. Thus, plugging the calculated value $d_{\\mathrm{GEC}}$ into our main theorems leads to the theoretical guarantee for the instantiation of our proposed algorithms on each function class."}, {"review_id": "rJhVejJ5aT", "reviewer": "Reviewer_pkbQ", "summary": "This paper focuses on posterior sampling for competitive reinforcement learning, aiming to propose a model-based self-play posterior sampling method to approximate Nash equilibrium in the case of self-play and adversarial learning. The theoretical analysis indicates that the proposed method achieves a low regret bound that can scale sublinearly converge.", "questions": "line 56: \"... partial observations into the posterior sampling framework under a MARL ...\", so the question is what is the difficulty of using posterior sampling in POMDP?\n ", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-organized and gives a throughout survey of the related work.\n2. this paper seems to be a solid theoretical work, though I'm not entirely sure of that.", "weaknesses": "1. Too long a supplementary, so that the reviewer may miss some details", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer pkbQ for the valuable advice and questions. We will address your concerns below.\n\n**1. The supplementary material is long so that the reviewer may miss some details.**\n\nIn our version, we will carefully revise the whole paper and move additional important details from the supplementary to the main text to highlight our technical contribution. \n\n**2. What is the difficulty of using posterior sampling in partially observable RL?**\n\nOur work studies a more challenging partially observable Markov game (POMG) problem than the single-agent POMDP. When it comes to the multi-agent setting, i.e., POMGs, to the best of our knowledge, there are no prior works studying the posterior sampling methods, particularly when incorporating function approximation. The difficulties of using posterior sampling in POMGs lie in the following aspects:\n\n**(1)** First, as a different learning framework, posterior sampling diverges fundamentally from existing POMG methods in techniques. In posterior sampling methods, we need to propose a proper model sampling distribution incorporating a well-designed loss formulation fitting the POMG models, which does not exist in the non-posterior sampling POMG method. Thus, this leads to different proof methods. Before our work, it was unknown how to design a statistically efficient posterior sampling algorithm for POMGs with a provable guarantee.\n\n**(2)** Second, the posterior sampling POMG method is not a direct extension of existing single-agent POMDP methods. We now have two coupled agents with different policies competing with each other in a min-max way instead of one agent pursuing a single maximization objective. In the POMG setting, we need to consider a more challenging minimax optimization problem. Obtaining such a competitive learning algorithm requires a novel algorithmic design methodology.\n\n\n**(3)** Third, compared to the fully observable Markov games (FOMGs), the intrinsic model structure differences between FOMGs and POMGs bring the challenges of extra emission kernels, unknown underlying states, and history-dependent policies. Thus, POMGs cannot be solved by the existing FOMG posterior sampling approaches. \n\n**(4)** Finally, when considering a more general function approximation setting in POMGs, novel multi-agent general function approximation conditions should be proposed to cover a wide range of known function approximation approaches. The conditions were unclear before our work. \n\nWe tackle those challenges by successfully proposing unified statistically efficient posterior sampling algorithms for POMGs and FOMGs incorporating general function approximations. More importantly, our work covers both self-play and adversarial setups. We remark that the adversarial setting is not even studied in the existing posterior sampling method under full observability. "}, {"review_id": "b5m0T2B10Z", "reviewer": "Reviewer_DqQm", "summary": "This paper investigates posterior sampling algorithms for competitive reinforcement learning (RL) with general function approximations in zero-sum Markov games (MGs). It introduces complexity measures for function approximation and proposes model-based self-play and adversarial posterior sampling methods to learn Nash equilibrium in partially observable states. The algorithms provide low regret bounds and can be applied to various tractable zero-sum MG classes in both fully observable and partially observable settings.", "questions": "na", "limitations": "na", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I think this work really pushes the Multiagent+PORL community research efforts further by answering:\n\n> can we design a generic posterior sampling algorithm for MGRL in the context of function approximation?\n\nThe main contribution of model-based posterior sampling algorithm equipped with rigorous analyses is worthy for publication at NeurIPS.", "weaknesses": "I have only minor weaknesses for this work as follows:\n\n1. For the self-play, Algorithm 1 and 2 seems repetitive. One can essentially combine them for presentation.\n2. More discussion needs to be added comparing between Self-play and Adversarial results (Thm 1 and 2). For example, the self-play considered here is the zero-sum, hence the player 2 is the worst possible adversary. With this notion, comparing these two results will be helpful for future directions. It will be curious to see if the main player in Self-play (Thm 1 result) can handle the adversary in the Alg 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer DqQm for recognizing the contribution of our submission. We will address your concerns below.\n\n**1. Combine the presentation of Algorithm 1 and Algorithm 2.**\n\nWe will carefully polish our paper and revise the presentation of the algorithms in our next version.\n\n**2. More discussions on algorithms and the theoretical results for self-play and adversarial settings.**\n\nWe politely point out that although Algorithm 1 can also be viewed as a learning algorithm for Player 1 with a worst possible adversary Player 2, it cannot be used to handle the adversarial setting in Algorithm 3 directly. The main reason is that the execution of Algorithm 1 requires both players to be controlled by the learner due to the setting of self-play, while Algorithm 3 cannot control Player 2 and views Player 2 as an arbitrary player. In Line 5 and Line 6 of Algorithm 1, we need to compute a policy $\\underline{\\nu}^t$ for Player 2, and then the exploration policy $\\sigma^t$ is set to be $(\\pi^t, \\underline{\\nu^t})$ for data collection as shown in Line 239 of the main text. Thus, Algorithm 1 forces Player 2 to take a specific policy $\\underline{\\nu^t}$ instead of an arbitrary uncontrollable one $\\nu^t$ as in Algorithm 3. We will further highlight this difference in the revision.\n\nRegarding the theoretical result, the two different settings result in distinct regret metrics. We note that the result in Theorem 1 is inferred from Proposition 1 and Proposition 2, where Proposition 1 shows the regret for Algorithm 1 and Proposition 2 shows the regret for Algorithm 2 under the self-play setting. Then, to compare the results for Algorithm 1 and Algorithm 3, we focus on Proposition 1 and Theorem 2. The regret metric in Proposition 1 is defined as $\\mathrm{Reg\\_1^\\mathrm{sp}}(T):=\\sum_{t=1}^T(V_{f^\\*}^\\* - V\\_{f^\\*}^{\\pi^t,\\*}).$  And the regret metric in Theorem 2 is defined as $\\mathrm{Reg^{\\mathrm{adv}}}(T):=\\sum_{t=1}^T(V\\_{f^\\*}^\\* - V\\_{f^\\*}^{\\pi^t,\\nu^t}).$ Since $V_{f^*}^{\\pi^t,\\nu^t}\\geq \\min_\\nu V_{f^*}^{\\pi^t,\\nu}= V_{f^*}^{\\pi^t,*}$ always holds, we have $\\mathrm{Reg}^{\\mathrm{adv}}(T)\\leq \\mathrm{Reg}^{\\mathrm{sp}}_1(T)$, which indicates that $\\mathrm{Reg}^{\\mathrm{sp}}_1(T)$ is a tighter regret metric. Moreover, Proposition 1 and Theorem 2 have comparable upper bounds in the same order (ignoring the numerical factors) but under different regret metrics. This indicates that the self-play algorithm for Player 1, i.e., Algorithm 1, can induce a tighter theoretical result, which reflects the power of self-play. We will add this discussion in our revision. "}, {"review_id": "Zi9Co5pxyO", "reviewer": "Reviewer_qywY", "summary": "The paper considers a zero-sum Markov game with unknown dynamics in the case of full and partial observations. The authors propose algorithms for finding a Nash equilibrium in the games, in which, at each iteration, virtual games with dynamics sampled from certain distributions are solved. The paper's main result is theoretical and consists of estimates for the rate of the algorithms' convergence.", "questions": "On line 151, the authors introduce the reward function $r_h(o,a,b)$. It seems a bit exotic that it depends on an observation $o$ rather than on a state $s$. Is it important for the obtained results?\n", "limitations": "The paper does not have potentially negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is aimed at solving an important problem. It is well structured and written in clear mathematical language.", "weaknesses": "Unfortunately, as a non-specialist, it is rather difficult for me to assess the significance of the obtained theoretical results. It is not entirely clear what useful conclusion the reader can draw from them concerning practical methods for solving zero-sum Markov games. The proposed algorithms seem very abstract since it is difficult to calculate the indicated distributions in experimental tasks. If I'm wrong and this is feasible, an example confirming this would significantly strengthen the paper.\n\nOne more thing I doubt is the fact that in the algorithms, the authors apparently assume that a Nash equilibrium in Markov games exists. This is true if we consider games with an infinite horizon, but I'm not sure if this is true for games with a fixed number of steps $H$. Usually, in such games, it is assumed that the policy depends not only on the state but also on the step number. Otherwise, the existence of a Nash equilibrium is not obvious to me, and I would welcome a reference to this fact.\n\nThe paper also contains typos:\n\n178 - $V^*$ instead of $V_1^*$.\n189 - $P^{\\pi,\\nu}_f$ instead of $P^{\\pi,\\nu}_h$\n246 - “begin” instead of “bening”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer qywY for the valuable advice and questions. We will address your concerns below.\n\n**1. (1) The significance of the theoretical results? (2) Feasibility of the proposed algorithm.**\n\n**(1)** Our work studies this problem in alignment with the recent progress on developing reinforcement learning algorithms with **provable statistical efficiency**. In particular, we majorly focus on **a)** how to design posterior sampling algorithms, an important research direction in RL, with statistically low sample complexity, **b)** how to incorporate more general function classes that cover a wide range of function approximators. Both questions have attracted a lot of attention in RL theory works (e.g., [1,2,3]. Kindly find more details in Related Work). Concentrating on the competitive RL with full and even the harder partial observability, we successfully identify such function classes named Self-Play and Adversarial GEC and design the first posterior sampling algorithms based on them, which fills a gap in competitive RL theory. More importantly, our algorithm enjoys provable sample efficiency guarantees. The dependence on $O(\\sqrt{T})$ in our theorems indicates that our regrets are near-optimal.\n\n**(2)** Our algorithm remains feasible when instantiated for a concrete function class. To exemplify, consider a linear-mixture Markov game (MG) setting, which is subsumed by our framework. The transition model can be represented linearly as $\\theta_h^\\top \\phi(s,a,b,s')$ where $\\theta_h$ is the model parameter assumed lying in a finite set. Then, in the posterior sampling step, e.g., Line 3 of Algorithm 1, the function class $\\mathcal{F}$ is finite, and we can calculate $p^t(f)$ for each $f\\in \\mathcal{F}$. The optimism term $V^*_f$ in the distribution can be estimated by many existing iterative methods given any model $f$. This optimism term is unavoidable even in a single-agent setting due to the feel-good Thompson sampling framework [2,3]. In addition, [2] mentioned that posterior sampling is relatively amenable to tractable implementation via ensemble approximations or stochastic gradient Langevin dynamics. In fact, in contrast to sample efficiency, how to design provably computation-efficient RL methods with general function approximation [1] and under partial observability [4,8] remains not well explored in existing works so far. Further designing such algorithms is orthogonal to our contributions.\n\nWe deeply appreciate the reviewer making efforts to review our work and raise insightful questions. We humbly hope our work can also be assessed on the basis of its statistical results and theoretical contributions.\n\n**2. Existence of Nash equilibrium (NE)?**\n\nMany existing works, e.g., [5,6,7], show that NE exists for the finite-horizon fully observable MGs. These works show the existence using the finite-horizon property, the notion of best response, the Bellman equation, and the backward induction from the last step $H$ to the initial step $1$. For example, to find such a NE, for any state $s$ at step $H$, there always exists a NE $\\big(\\pi_H^*(\\cdot|s), \\nu_H^*(\\cdot|s)\\big)$ for a matrix game with the payoff matrix $[r\\_H(s,a,b)]\\_{a\\in\\mathcal{A},b\\in\\mathcal{B}}$. \n\nThen, for step $H-1$, given any state $s$, by the Bellman equation, we have a new payoff matrix as $[r\\_{H-1}(s,a,b)+\\mathbb{E}\\_{s'\\sim \\mathbb{P}\\_H(s'|s,a,b),a'\\sim \\pi\\_H^*(\\cdot|s'),b'\\sim\\nu\\_H^*(\\cdot|s')}(Q_H(s',a',b'))]\\_{a\\in\\mathcal{A},b\\in\\mathcal{B}}$ where $Q_H(s,a,b) = r_H(s,a,b)$. \n\nThus, we compute a NE for the above new payoff matrix as $\\big(\\pi_{H-1}^*(\\cdot|s), \\nu_{H-1}^*(\\cdot|s)\\big)$ for any $s$. Iterating from step $H$ to $1$, we obtain the NE for finite-horizon MGs as ${(\\pi^*\\_h,\\nu^*\\_h)}\\_{h=1}^H$. It indicates that we can find the NE of a finite-horizon MG by decomposition into multiple matrix games whose NE always exists.\nThe work [8] studies the finite-horizon tabular partially observable MG, where a similar idea of backward induction can be used to show its existence (consider the history-dependent policies and regard the history as the state in fully observable MGs). \n\n**3. Reward function depends on $o$ instead of $s$.**\n\nOur reward function is modeled following the recent works on the finite-horizon partially observable RL. Many existing works on partially observable MDPs (e.g., [4]) and MGs (e.g., [8]) defined the reward dependent on $o$. Such a definition is also natural since only the observation $o$ can be accessed by learners.\nMoreover, our definition does not conflict with a state-dependent reward function, denoted as $R_h(o,a,b)$.  At state $s$, we view $o$ as a random variable sampled from $\\mathbb{O}_h(\\cdot|s)$. We always have\n$$\nR\\_h(s,a,b) = \\sum\\_{o\\in \\mathcal{O}} \\mathbb{O}(o|s) r\\_h(o,a,b).\n$$\nThat is, $R_h(s,a,b)$ is intuitively an expectation of $r_h(o,a,b)$ based on the emission kernel. In this sense, whether the reward function depends on $s$ or $o$ does not introduce extra learning difficulty.\n\n\n**Reference**\n\n[1] Simon Du, et al. Bilinear classes: A structural framework for provable generalization in rl. ICML 2021.\n\n[2] Alekh Agarwal, and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. NeurIPS 2022.\n\n[3] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science 2022.\n\n[4] Chi Jin, et al. Sample-efficient reinforcement learning of undercomplete pomdps. NeurIPS 2020.\n\n[5] Yu Bai, Chi Jin. Provable Self-Play Algorithms for Competitive Reinforcement Learning. ICML 2020.\n\n[6] Qiwen Cui, and Simon S. Du. When are Offline Two-Player Zero-Sum Markov Games Solvable? NeurIPS 2022.\n\n[7] Qiaomin Xie, et al. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. COLT 2020.\n\n[8] Qinghua Liu, et al. Sample-efficient reinforcement learning of partially observable markov games. NeurIPS, 2022.\n"}]

Author rebuttal:

Meta-review: The paper extends the previous GEC complexity measure for single agent RL to the Markov game settings. The new measures look interesting and capture many existing examples. The proposed posterior sampling algorithms are reasonable and achieve near optimal regret in both self-play and adversarial learning settings.
Decision: Accept (poster)