Sample-Efficient Reinforcement Learning of Partially Observable Markov Games
Authors: Qinghua Liu
Csaba Szepesvari
Chi Jin
Venue: NeurIPS 2022 Accept (2022)
Keywords: RL theory

Abstract: This paper considers the challenging tasks of Multi-Agent Reinforcement Learning (MARL) under partial observability, where each agent only sees her own individual observations and actions that reveal incomplete information about the underlying state of system. This paper studies these tasks under the general model of multiplayer general-sum Partially Observable Markov Games (POMGs), which is significantly larger than the standard model of Imperfect Information Extensive-Form Games (IIEFGs). We identify a rich subclass of POMGs---weakly revealing POMGs---in which sample-efficient learning is tractable. In the self-play setting, we prove that a simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) is sufficient to find approximate Nash equilibria, correlated equilibria, as well as coarse correlated equilibria of weakly revealing POMGs, in a polynomial number of samples when the number of agents is small. In the setting of playing against adversarial opponents, we show that a variant of our optimistic MLE algorithm is capable of achieving sublinear regret when being compared against the optimal maximin policies. To our best knowledge, this work provides the first line of sample-efficient results for learning POMGs.

Sample-Efficient Reinforcement Learning of Partially Observable Markov Games
Qinghua Liu Princeton University
Csaba Szepesvári DeepMind and University of Alberta szepesvaQualberta.co
Chi Jin Princeton University chi j@princeton. edu
ginghual@princeton.. edu
Abstract
This paper considers the challenging tasks of Multi-Agent Reinforcement Learning (MARL) under partial observability, where each agent only sees her own individual observations and actions that reveal incomplete information about the underly- ing state of system. This paper studies these tasks under the general model of multiplayer general-sum Partially Observable Markov Games (POMGs), which is significantly larger than the standard model of Imperfect Information Extensive- Form Games (IEFGs).. We identify a rich subclass of POMGs-weakly revealing POMGs which sample-efficient learning is tractable. In the self-play setting, we prove that a simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) is sufficient to find approximate Nash equilibria, correlated equilibria, as well as coarse correlated equilibria weakly revealing POMGs, in a polynomial number of samples when the number of agents is small. In the setting playing against adversarial opponents, we show that a variant of our optimistic MLE algorithm is capable of achieving sublinear regret when being compared against the optimal maximin policies. To our best knowledge, this work provides the first line of sample-efficient results for learning POMGs.
Introduction
This paper studies Multi-Agent Reinforcement Learning (MARL) under partial observability, where each player tries to maximize her own utility via interacting with an unknown environment as well as other players. In addition, each agent only sees her own observations and actions, which reveal incomplete information about the underlying state of system. A large number of real-world applications can be cast into this framework: in Poker, cards in player's hand are hidden from the other players; in many real-time strategy games, players have only access to their local observations; in multi-agent robotic systems, agents with first-person cameras have to cope with noisy sensors and occlusions. While practical MARL systems have achieved remarkable success in a set partially observable problems including Poker (9, Starcraft [40), Dota (6] and autonomous driving [36]. the theoretical understanding of MARL under partial observability remains very limited.
The combination of partial observability with multiagency introduces a number of unique challenges. The non-Markovian nature of the observations forces the agent to maintain memory and reason about beliefs of the system state, all while exploring to collect information about the environment. Consequently, well-known complexity-thene -hhorreic results show that learning and planning partially observable environments is statistically and computationally intractable even in the single-agent setting B35 41 29. The presence interaction between multiple agents further complicates the partially observable problems. In addition to dealing with the adaptive nature of other players who can adjust their strategies according to the learner's past behaviors, the learner is further required to discover and exploit the information asymmetry due to the separate observations of each agent.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

As a result, prior theoretical works on partially observable MARL have been mostly focused on a small subset of problems with strong structural assumptions. For instance, the line of works on Imperfect Information Extensive-Form Games (IIEFG) [see, e.g. 14
assumes tree- structured transition with small depth as well as special type of emission which can represented as information sets. In contrast, this paper considers more general mathematical model known as Partially Observable Markov Games (POMGs). POMGs are the natural extensions of both Partially Observable Markov Decision Processes (POMDPs) standard model for single-agent partially observable RL, and Markov Games -he standard model for fully observable MARL. Despite the complexity barriers of learning partially observable systems apply to POMGs, they are of worst-case nature, which do not preclude efficient algorithms for learning interesting subclasses of POMGs. This motivates us to ask the following question:
13 24
Can we develop efficient algorithms that learn rich class of POMGs?
In this paper, we provide the first positive answer to the highlighted question in terms of the sample We identify a rich family of tractable POMGs-weakly revealing POMGs (see Section B.. The weakly revealing condition only requires the joint observations of all agents to reveal certain amount of information about the latent states, which is satisfied in many real-world applications. The condition rules out the pathological instances where no player has any information to distinguish latent states, which prevents efficient learninig in the worst case.
efficiency. Fl
In the self- play setting where the algorithm can control all the players learn the equilibria by playing against itself, this paper proposes a new simple gegorithm-Optimmiee Estimation for Learning Equilibria (OMLE- Equilibriuu)) As the name suggests, it combines opti- mism, MIE principles with equilibria finding subroutines. The algorithm provably finds approximate Nash equilibria, coarse correlated equilibria and correlate equilibria of any weakly-revealing POMGs using a number of samples polynomial in all relevant parameters.
Maximum Likelihood
In the setting of playing against adversarial opponents, we measure the performance of our algorithm by comparing against the optimal maximin policies. We first prove that learning in this setting is hard if each player can only see her own observations and actions. Nevertheless, if the agent is allowed to access other players' observations and actions after each episode of play (c.g.. watch the replays of the games from other players' perspectives afterwards), then we can design new algorithm AMver-ddersrry which achieves sublinear regret.
To our best knowledge, this is the first line of provably sample-efficient results for learning rich classes of POMGs. Importantly, the classes of problems that can be learned in this paper are significantly larger than known tractable classes of MARL problems under partial observability.
1.1 Technical novelty
This paper builds upon the recent progress in learning single-agent POMDPs (26]. which identifies the class of weakly revealing POMDPs and develops OMLE algorithm for learning the optimal policy. Besides obtaining a completely new set of results in the multi-agent setting, we here highlight a few contributions and technical novelties of this paper comparing to (26).
This paper rigorously formulates the models, related concepts and learning objectives of multi- player general-sum POMGs, and provides the first line of sample-effcientt learning results.
Extending the weakly revealing conditions into the multiagent setting lead to two natural candidates: either (a) joint observations or (b) individual observations are required to weakly reveal the state information. This paper shows the former (the weaker assumption) suffices to guarantee tractability.
Results in the self-play setting requires careful design of optimistic planning algorithms that effectively address the game-thene theoretctteti aspects of the problem under partial observability. We achieve this by Subroutine [ which is even distinct from the standard techniques for learning MGs.
The discussions and results in the setting of playing against adversarial opponents are completely new, and unique to the multiagent setup.
'The sample complexity of learning IIFGGs scale polynomially with respect to the number of information sets, which typically has an exponential growth in depth.
FFor computational efficiency, due to the inherent hardness of planning in POMDPs, all existing provable algorithms that learn large classes of POMDPs (single-agent version of POMGs) require super soper-oolynomil time. We leave the challenge of computationally efficient learning for future work.

---

1.2 Related Works
Reinforcement learning has been extensively studied in the single-agent obslr-bbberv setting [see, e.g.
18 23 44 20] and the references therein]. For the purpose of this paper, we focus on reviewing existing works on partially observable RL and multi-agent RL in the exploration setting.
In recent years, there has been growing interest in studying Markov games (37 the standard generalization of MDPs from the single-player setting to the multi-player setting. Various samplc-efticient algorithms have been designed for either two-player zero-sum MGs [e.g..
Markoy games
28 43 22 or pallirp general-sum MGs [e.g.. 28 38 IT]. However, all these works rely on the states being fully observable, while the POMGs studied in this paper allow states to be only partially observable, which strictly generalizes MGs.
42
POMDPs POMDPs generalize MDPs from the fully observable setting to the partially observable setting. is well-known that in POMDPs both planning [35] 41) and model estimation [29] are computationally hard in the worst case. Besides, reinforcement learning of POMDPs is also known to be statistically hard: (25] proved that finding a near-optimal policy of POMDP in the worst case requires a number of samples that is exponential in the episode length. The hard instances are those pathological POMDPs where the observations contain no useful information for identifying the system dynamics. Nonetheless, these hardness results are all in the worst-case sense and there are still many intriguing positive results on sample-efficient learning of subelasses of POMDPs. For example,
15 2 19 applied spectral methods to learning undercomplete POMDPs and (26) developed the
optimistic MLE approach for learning both undercomplete and overcomplete POMDPs. We refer interested readers to (26) for thorough review of existing results on POMDPs.
In terms of algorithmic design, our algorithms build upon the optimistic MLE methodology developed in (26). Compared to [26). our main algorithmic contribution lies in the design of the optimistic equilibrium computation subroutine in the self-play setting and the optimistic maximin policy design in the adversarial setting. In terms of analysis, our proofs requrie new techniques tailored to
controlling theertte regret, in addition to the OMLE guarantees imported from (26.. For more detailed explanations of our technical contribution, please refer to Section 1.1
cenperfect-iffrmaatee extensive-form games In the literature on game theory, there is a long history of learning
Inforrccttnnoo Extensive-Fone Games with perfect recall (IEFGs)) B 24 and the references therein. IIEGGs can be viewed as special cases of POMGs with tree-structured transition and deterministic emission (which are also known as information sets). As a result, IIEFGs can not efficiently represent POMGs with general transition and stochastic emission (see Appendix A). and thus sample-efficient learning results for IIFGGs does not imply sample-effiiien learning of POMGs. On the other hand, we show that all IEFGS can be efficiently represented by 1 1-weakly revealing POMGs (see Appendix AA). Therefore, all algorithms and theoretical results developed in this paper can immediately used to learn IIEFGs with a polynomial sample complexity.
[see, e.g.. 45 14
12
Decentralized POMDPs There is another classic model for studying multi-agent partially observ- able RI, named decentralized POMDPs [e.g.. 32 33 which is a special subclass of POMGs where all players share common reward target. Compared to general POMGs, decentralized POMDPs can only simulate cooperative relations among players, while general POMGs can model both cooperative and competitive relations. Besides, most works [c.g..Bl 31. 7 34 39 along this direction mainly focus on the computational complexity of planning with known models simulators instead of the sample efficiency in the exploration setting.
2 Preliminary
In this paper, we consider Partially Observable Markov Games (POMGs) in its most generic-
multiplayer general-sum form. Formally, we denote a tabular episodic POMG with n players by tuple S, [At] _ {O.), T,, O, M1i (r.). where H denotes the length of each episode, S the state space with |S| = S, A, denotes the action space for the 7th player with |Ai = A;. We denote by a = (a), .u..... a, ) the joint actions of all n players, and by A == A= X... x An the joint
action space with ||| = A II. A. T = (Th )EEAH] is the collection of transition matrices, that
3

---

Ta a) E As gives the distribution of the next state if joint actions a are taken at state at step h. N1 denotes the distribution of the initial state $1. O denotes the observation space for the zth player with [ = O.. We denote by o == (o),.. ... On) the joint observations of all n players. and by := 01 x... x On with |O| = O = O,, O = {OA (Ceje C ROXS is the collection of joint emission matrices, so that C2 (-ss) E Åo gives the emission distribution over the joint observation space O at state and step h. Finally r; = (e(H) is the collection of known reward functions for the hh player, so that (o,) [0. 1] gives the deterministic reward received by the ith player if she observes o; at step h. P We remark that since the relation among the rewards of different players can be arbitrary, this model of POMGs subsumes both the cooperative and the competitive settings in partially observable MARL.
In a POMG, the states are always hidden from all players, and each player only observes her own individual observations and actions. That is, each player can not see the observations and actions of the other players. At the beginning of each episode, the environment samlpes 81 from p41. At each step h [H] each player i observes her own observation 0., where O == (01,hs-.-. On,h) are jointly sampled from (x | sp.). Then each player receives reward Ti,s (o,,)) and picks action aith E A; simultaneously. After that the environment transitions the next state sh+11 1 ~ TA (-1sn, ai.)) where an :- (01,h) hn The current episode terminates immediately once 8 is reached.
Policy, value function To define different types of polices, we extend the conventions in fully observable Markov games [21 to the partially observable settings. A (random) policy т; of the 8th player is map IT : 12 x U (1O, x A+)a x O:) - As, which maps random seed w from space s2 and a history of length h E
say T.A == (o1,1, "q,1, "....... .t,h),, to an action in A,, To execute policy Ty we first draw random sample w at the beginning of the episode. Then, at each step h, the jth player simply takes action ग. T. ). We note here w is shared among all steps h E [H]. encodes both the correlation among steps and the individual randomness of each step. We further say policy n, is deterministic if (T(,, Ti,A) (Ti,,) which is independent of the choice of w.
By definition, random policy is equivalent to mixture of deterministic policies because given a fixed w the decision of π, on any history is deterministic. With slight abuse of notation, we use Ty (u(,, .) refer the deterministic policy realized by policy m, and fixed w. We denote the set of all policies of the 2th player by II, and the set of all deterministic ones by IIçlet.
A joint (potentially correlated) policy is a set of policies { where the same random seed w is shared among all agents, which we denote as π Ti @ π2 .... @ T.. We also denote T-: = T 3 ... TT- @ Mi+1 3 ..... @ Tr to be the joint policy excluding the 7th player. A special case of joint policy is the product policy where the random seed has special form w = (wi..... W,), and for any E [m]] n; only uses the randomness in wi, which is independent of remaining (w))iy which we denote as Ti X 12 X ... X k..
We define the value function V as the expected cumulative reward that the 7th player will receive if all players follow joint policy π:
T= E. EK
where the expectation is taken over the randomness in the initial state, the transitions, the emissions, and the random seed w in policy x.
Best response and strategy modification For any strategy --i, the best response of the 7th player is defined as a policy of the hth player, which is independent of the randomness in T and achieves the highest value for herself conditioned on all other players deploying --i. Formally, the best response is the maximizer of max;; x=( whose value we also denote as V.t.= for simplicity. By its definition, we know the best response can always be achieved by deterministic policies.
A strategy modification for the 7th player is a map Φb : ITdet + Mddet, which maps a deterministic policy in Melt to another one it. For any such strategy modification di, we can naturally extend its domain and image to include random policies, i.e., define its extension Φ;; II; - IT; as follows: by definition, a random policy ι can be expressed as a mixture of deterministic policies, i.e., as 7 (w, (a deterministic policy for a fixed w) with distribution over Then if we apply map Φ; on random
3 This is equivalent to assuming the reward information is contained in the observation.

---

policy π, we can define the resulting random policy (denoted as Ø, o Ti) as Øs (T; -) (again deterministic policy for fixed w) with the same distribution over w. For any joint policy n, we define the best strategy modification of the ith player as the maximizer of max,, V V
Different from the best response, which is completely independent of the randomness in n- the best strategy modification changes the policy of the 2th player while still utilizing the shared randomness among TH and -- Therefore, the best strategy modification is more powerful than the best response: formally one can show that maxs, V, (0 2 maxx; Vi xm= for any policy x.
2.1 Learning objectives
We foeus three classic equilibrium concepts in game mheory-Nshh Equilibrium, Correlated Equilibrium (CE) and Coarse Correlated Equilibrium (CCE). First, a Nash equilibrium defined as a product policy in which no player can increase her value by changing only her own policy. Formally,
Definition (Nash Equilibrium). product policy is a Nash equilibrium if V = V for all i [n]. A product policy x is an e-approximate Nash equilibrium if V. S VT + for all i [n].
The Nash-regret of a sequence of product policies is the cumulative violation of the Nash condition.
Definition 2 (Nash-regret). Let n denote the (product) policy deployed by an algorithm in the k episode. After a total of K episodes, the Nash-regret is defined
Regret (K) = =EK maxig[a]
(V.
Second, a coarse correlated equilibrium is defined as joint (potentially correlated) policy where no player can increase her value by unilaterally changing her own policy. Formally,
Definition 3 (Coarse Correlated Equilibrium). A joint policy π is a CCE if V. s V. for all i E [n]. A joint policy π is an e-approximate CCE V VV + e all [n].
The only difference between Definition I and Definition 3 is that Nash equilibrium has to be product policy while CCE can be correlated. Therefore, CCE a relaxed notion of Nash equilibrium, and Nash equilibrium is always CCE. Similarly, we can define the CCE-regret for sequence of potentially correlated policies as the cumulative vilolation of the CCE condition.
Definition 4 (CCE-regret). Let Te denote the policy deployed by algorithm in the kMh episode. After a total of K episodes, the CCE-regret is defined as
Regrel (K) k==
Ek max4e[n]
(V. (
Finally, a correlated equilibrium is defined as a joint (potentially correlated) policy where no player can increase her value by unilaterally applying any strategy modification. Formally,
Definition (Correlated Equilibrium). A joint policy x a CE if maxo. v((@io))@T-1 V." for all
i [n]. A joint policy स is an e-approximate CE if max,, v. ((dion)) V + efforall all E [m].
In Partially Observable Markov games, we always have that a Nash equilibrium is CE, and a CE is CCE. Finally, we define the CE-regret be the cumulative violation of the CE condition.
Definition 6 (CE-regreet, Let Let denote the policy deployed by algorithm in the h episode. After a total of K episodes, the CE-regret is defined as
(egretcn((K) = =K maXie[m] max6, (V (((hhstt)on v.*))
3 Weakly Revealing Partially Observable Markov Games
In this section, we define the class of weakly revealing POMGs. To begin with, we consider undercomplete POMGs where there are more observations than hidden states, i.e., O 2 S. Formally, the family of a-weakly revealing POMGs includes all POMGs, in which the 5th singular value of each emission matrix On is lower bounded by 0.
5

---

Algorithm 1 OMMEEEquillirium
1: Initialize: B' = ④ min, o9 (g(00)) 2 a). D
2: for k= .,..., K do
3: compute x² =Optimistic Equilibrium(B4)
4: follow x to collect a trajectory 7 (of, af 02 atr)
5: add (n xk into D and update
B
0 O
Σ
log P. (T)
max 0' E
Σ
log (T)
-+ B'
(H,))ED
(x,7)ED
6: output π out that sampled uniformly at random from
( }KE(K]
Assumption (o-weakly revealing condition). There exists >> O, such that min, as(On) 2 a.
Assumption D is simply a robust version of the condition that the rank of each emission matrix S, which guarantees that two different latent state mixtures can generate the same observation distribution, i... 0 # Dy for any different V1, 1/2 E Ag. Intuitively, this guarantees that the joint observations of all agents contain sufficient information to distinguish any two different state mixtures. We remark that this much weaker than requiring the individual observations of each agent contain sufficient information about the latent states. The weakly revealing condition is important in excluding those pathological POMGs where the observations contain no useful information for identifying the key parts of model dynamics.
Note that Assumption [ never holds in the overcomplete setting (S > O) as it is impossible to distinguish any two latent state mixtures by only inspecting the observation distribution in a single step. To address this issue, we can instead inspect the observations for m-consecutive steps. To proceed, we define the m-step emission- matrices
{MA E R ("")=""")xS) [hE[H-m+1]
follows: Given observation sequence of length m, initial state and action sequence a of length m - 1, we let [M,] (a.o).* be the probability of receiving o provided that the action sequence used from state and step lt:
[M.). P(oh:h+m-1
s/ = 0hchmm22 = a). v( E Am-1 O S. (2)
Similar the undercomplete setting, the weakly-revealing condition in the over-complete setting simply assumes the 5th singular value of each m--tep emission-action matrix lower bounded.
Assumption 2 (multistep a-weakly revealing condition). There exists m E N, >> such that ming ssMM) 2 a where M,, is the m-step emission matrix defined in 2
Assumption 2 ensures that m-step consecutive observations shall contain sufficient information to distinguish any two different latent state mixtures. Note that Assumption [ is a special case of Assumption with m 1. Finally, remark that the single-agent versions of Assumption [and] 2 were first identified
[19 and (66 as sufficient conditions for sample-efficient learning of single-step and multi-step weakly revealing POMDPs (the single-agent version of POMGs), respectively.
4 Learning Equilibria with Self-play
In this section, we study the self-play setting where the algorithm can control the players to learn the equilibria by playing against itself. We propose new algorithm Optimistic Maximum Likelihood Estimation for Learning Equilibria equilibria, coarse correlated equilibria and correlate equilibria in any weakly-revealing partially observable Markov games using a number of samples polynomial in all relevant parameters.
(quilE-iqullirium that can provably find Nash
4.1 Undercomplete partially observable Markov games
We first present the algorithm and results for learning undercomplete POMGs under Assumption We will see in the later section that with a minor modification the same algorithm also applies to learning overcomplete POMGs under Assumption

---

Subroutine Optimistic Optimistii_EEuullbbiung Equilibrium(B))
1: for E [n] do
2: let V. E Th TR x ( with its 7thh entry equal to supses (7) for E Th x x... x 7l
3: return EQUILIBRIUM
Algorithm description To condense notations, we will use 0= (T, O, (1) to denote the parameters of POMG. Given policy и and a trajectory т, we denote by (0) the 7th player's value and by (r) the probability of observing trajectory т, both under policy in the POMG model parameterized by We describe OMLE-Equilibriu in Algorithm
each episode, the algorithm
executes the following two key steps:
Optimistic equilibrium computation (Line We first invoke Optimistic Equilibrium (Subroutine I with confidence set B* to compute joint (potentially correlated) policy n². Formally, subroutine
Eatpriic___ulliiiiuumm"e.. consists of two components:
12 of Subroutine 1 For each player E [n] and X x 1lsht, we compute an upper bound V for the 1th player's value under policy by using the most optimistic POMG model in the confidence set B*
Optimisic value estimation (Line
deterministic joint policy E 11
Equilibira computation (Line Subroutine D Given the optimistic value estimates for all deterministic joint policies and all players, we can view the POMG normal- form game where the ith player's pure strategies consist of all her deterministic policies (i.e., 11( and the payoff she receives under a joint deterministic policy π E 11 x Th is equal to the corresponding optimistic value estimate V Then we compute EQUILIBRIUM n² for this normal-form game, which is mixture of all the deterministic joint policies in ITdett x ... x II
We first follow T² to collect a trajectory, and then utilize the newly collected data to update the model confidence set via MLE principle.
Confidence set update (Line 4 5)
Here we highlight two algorithmic designs OMLL-Equiiibrium: the flexibility of equilibrium computation and the MLE confidence set construction. In the step of equilibrium computation, we can choose EQUILIBRIUM to be Nash equilibrium or correlated equilibrium (CE) or corase correlated equilibrium (CCE) of the normal formll-fommga game depending on the target type of equilibrium we aim to learn for the POMG. With regard to the confidence set design, we adopt the idea from (26 to include all the POMG models whose likelihood on the historical data is close to the maximum likelihood. This can be viewed as a relaxation of the classic MLE method, with the degree of relaxation controlled by parameter 8. One important benefit of this relaxation is that although the groundtruth POMG model is in general not solution of MLE, its likelihood ratio is rather close to the maximal likelihood. By doing so, can guarantee the true model is included in the confidence set with high probability. Finally, we remark that Algorithm is computationally inefficient in general due to the steps of optimistic value estimation and equilibriu computation.
Theoretical guarantees Below we present the main theorem for OMLE-Equillbrium. Theorem 7. (Regret of OMLE-Equilbbrimm Under Assumption 7 there exists an abso- lute constant such that for any
(0. 1] and K N. Algorithm [ with 3 ((S2A+ + SO) log(SAOHH; + log (()) and EQUILIBRIUM being one of (Nash. CCE, CE}
satisfies (respectively) that with probability at least 1 - 5,
-1 log( K8 Vi for all l: E [K]. Regret (Nash, (CaEC,C (k)) & poly (S, A,A,O, H,
Theorem claims that if all players follow OMLE OMMLE-Equliirrumm then the cumulative (Nash,CCE,C) regret is upper bounded by Õ(VT)) for any weakly-revealing POMGs that satisfy Assumption where the growth rate w.r.t l is optimal. By the standard online-to-batch conversion, it directly implies the following sample complexity result:
Corollary 8. (Sample Complexity of EMLl-Equll)rrium) Under the same setting as Theorem 7 when 2 poly(S, (S, A, H, H,,--,.ogg log(e -18-1) then with probability at least 1/2, out an e- c-[Nash, CCE, CE} policy.
7

---

Algorithm 2 multi-step OMLE- OMLE-Equillbrium
1: Initialize: B'
{0 ④ min, 03 (M a). D {}
2: for k= .,....... K do
3: compute x Optimistic Equilibrium(B')
4: for h ...
m do
5: execute policy "L.,. (niform(A) to collect trajectory pkih
then add (I uniform Th:h) into D
6: update B i O Σ
log P (r) 2 max e
Σ
log (r) 83 R²
(T,T)ED
(F,F)ED
7: output π ouu that is sampled uniformly at random from ( ]RE(K]
Here the dependence on the precision parameter is optimal. Finally, notice that the upper bound in Theorem 7 deepend polynomially on the inverse of a - a lower bound for the minimal singular value of the joint emission matrix O₁ in Assumption [
This dependence is shown to be unavoidable even in the Lingl-player setting (POMDPs) (26].
4.2 Overcomplete partially observable Markov games
In this subsection, extend OMLE-Equllibrium the more challenging setting of learning over- complete POMGs, where there can be much less observations than latent states. We prove that simple variant of Euul-iqullibrium still enjoys polynomial sample-efficiency guarantee for learning any multi-step weakly revealing POMGs.
Algorithm description We describe the multi- step generalization of gorithm 2 which inherits the key designs from Algorithm| and additionally makes two important modifications to address the challenge of insufficient information from single-step observation. The first change is to utilize a more active sampling strategy for exploration. Instead simply following the optimistic policy n² will iteratively execute H m + policies of form TI.h o uniform(21 where the players first follow policy Th from step 1 to step h, then pick actions uniformly ran- h steps. Intuitively, by actively trying random action sequences
in Al-
dom to finish the remaining after executing policy n² the algorithm corresponding to those latent states that are frequently visited by π², and therefore help address the challenge of lacking sufficient information from single-step observation. The second change made by Algorithm 2 is that in constructing the confidence set, we require the minimal singular value of the multistep emission matrix to be lower bounded, which enforces the multistep weakly revealing condition in Assumption 2
acquire more information about the system dynamics
Theoretical guarantee Below we present the main theorem for multi-step OMLE OMLE-Equilibriin Equilibrium.
Theorem 9. (Total suboptimality of multi-step OMLE (Muulliqulir))mm Under Assumption 2 there exists an absolute constant such that for any E (0. 1] and K E N, Algorithm with (152 A + SO) log(SAO satisfies (respectively) that with probability at least 1 1 5,
AO HK) + log(K/)) K/8)) and EQUHIIRRIU being one of (Nash, CCE, CE)
Regret (Negrel(Naeh.coom (Nash, (k) S poly(S, AT O, H.Haaaa -1, log(K8-1)) Vi
for all [K],
where the regret is computed for policy .....,
Theorem claims that the total (aE,s,CC,,,C))"reggreee (that computed on policy n² ......, 7+
of multi-step OMLE- Equilibrii upper bounded by Ö(VI) for any multi-step weakly revealing POMGs satisfying Assumption 2 We remark that, strictly speaking, Theorem is is not a standard regret guarantee since the policies executed by multi-step OMLE- EQMLEEEquilibrium are compositions of and random actions, instead of purely . ) T² Nevertheless, we can still utilize the standard online-to-batee conversion obtain the following sample complexity guarantee:
_! . T
Corollary 10. (sample complexity of multi-step Equiliiqu)))) Under the same setting as then with probability at least
Theorem when 2 pSly(S, A , O, H, looge (oog(--18-1)) 1/2, x out an e- Nashh CCE, CE) policy.
8

---

Algorithm 3 OMLE-Adversary
1: Initialize: B² = 10 E ④ (s( 2 a). D 0
2: for k == ,. K do
3: learner computes (., x/)) je EI,, min Iell_, 1/ 12 (0)
4: opponents pick policies -²
5: execute policy n² = of x = to collect -K = (of at ....... o a/1)
6: add (n**, ,T* into D and update
B++ = 0 Q
Σ (T,T))D
log
P.T
max ('
Σ (x,7)ED
log P7 (T) - 8
(3)
Here the dependence on the precision parameter e is optimal up to poly-logarithmic factors. Finally, observe that the sample complexity has A dependency that is exponential in m, which is unavoid- able in general even the single-player setting (POMDPs) (26). Nonetheless, order to make min, vank(M,)
S possible (Assumption 2). we only need to make (OA)* 2 S, i.e., m Z log S
which is very small. In this paper, when we claim the sample complexity is polynomial, we consider m to be small enough so that n < poly(S, A, H.
5 Playing against Adversarial Opponents
In this section, we turn to the online setting where the learner only controls a single player and the remaining players can execute arbitrary strategies. In this setting, we no longer target at learning game-theoretic equilibria because if other players keep playing some highly suboptimal policies then the learner may never be able to explore the environment thoroughly and thus lacks sufficient information to compute equilibria. Instead, we consider the standard goal for online setting, which to achieve low regret in terms of cumulative rewards even if all other players play adversarially against the learner. Without loss generality, we assume the learner only controls the 1st player throughout this section.
5.1 Statistical hardness for the standard setting
We first consider the standard POMG setting where each player can only observe her own observations and actions. We prove that achieving low regret in this setting is impossible in general even if (i) the POMG two-player zero-sum and satisfies Assumption with a = 1, (ii) the opponent keeps playing fixed deterministic policy known to the learner, and (iil) the only parts of the model unknown the learner are the emission matrices.
Theorem 11. For any L, k E N+, there exist (i) two-player zero-sum POMG of size A,A,OH (I) and satisfying Assumption [ with a = 1, and (ūi a fixed opponent who keeps playing known deterministic policy T2, so that with probability at least 1/2
Ek (max.) ming, V V xma 2 (min(22.k3)
where x is the policy played by the learner in the t episode.
Theorem I1 claims that when the learner is not allowed to access the opponent's observations and actions, there exists exponential regret lower bound for competing with the max-min value (i.e., Nash value two-player zero-sum POMGs) even in the very benign scenario as described above. We remark that this lower bound directly implies competing with the best fixed policy in hindsight is also hard because the max max-min -in value is always no larger than the value of the best-response to T2:
max;, minsy V f max;, V x Vt.22
5.2 Positive results for the game-replay setting
In this section, we consider the game-replay setting where after each episode of play, every player will reveal their observations and actions in this episode to other players. In other words, every player

---

is able to observe the whole trajectory 7 = (of. af..... ; after the hthh episode is finished. The motivation for considering this setting is many real-workes games, e.g., Dota, StarCraft and Poker, players are usually allowed to watch the replays of the games they have played, in which they can freely view other players' observations and actions. Below, we show that simple variant of Oqulliqqil enjoys sublinear regret when playing against adversarial opponents.
Algorithm description We provide the formal description of Same as OMLE-Equilibriue the confidence set. The key modification lies in the computation of player I's (stochastic) policy of (Line 3 Specifically, the learner will compute the most optimistic model 0* in the confidence set B by examining player I's max-min value in each model. Then choose player I's policy to be the one with the highest value under 8², assuming all other players jointly play against player
in Algorithm 3
OMLE-Adversary utilizes the relaxed MLE approach to construct
Finally, we remark that although the confidence set construction in Line O seems to involve the joint policies π of all players, the confidence set itself is in fact independent of the joint policies Therefore, the 1st player can still construct the confidence set without knowledge of other players' policies. This is because the dependeney of the loglikelihood function on policy are equal both sides of (3), and thus they cancel with each other. Formally, for any 6, H' E O we have
E (log po (7*) - log Pay (74) Σ (log PogP&&Co Po
aa..)) log Fo Fo- (of. aa..r)).
Theoretical guarantees Below we present the main theorem for OMLE-Adversary.
Theorem 12. (Regret of OMLE-Adversary) Under Assumption 7 there exists an abso- lute constant с such that for any (152 A + log((SOHHH + log( (K()) satisfies that with probability least 1
(0. 1] and K N. Algorithm 3 with 3
Et maxx, ming, V VTT' & A,0,,, log((o-')))-- for all k E (K].
Theorem 12 claims that the regret of OMLE-Adversary is upper bounded by Ö(V)) in any weakly revealing POMGs that satisfy [ssumption[] no matter what adversarial strategies other players might take. Here the regret is defined by comparing the cumulative rewards received by player 1 to the max-min value maxa, mina, V&i that is the largest value she could receive if all other players jointly play against her. Notice that this regret is weaker than the typical version of regret considered in online learning literature, which typically competes with the best response in hindsight, i.e.,
max, Ei (vi a1 ( VT²'
Therefore, it is natural to ask whether can obtain similar sublinear regret in terms of the above regret definition. Unfortunately, previous work (27 proved that there exists exponential regret lower bound for competing with the best response in hindsight even in fully observable two-player zero-sum Markov games, which are special cases of POMGs satisfying Assumption with a = 1. As a result, achieving low regret in the above sense is also intractable in POMGs.
So far, we only derive the positve result (Theorem 12) for single-step weakly revealing POMGs. A reader might wonder whether similar results can be obtained in the more general setting of multi-step weakly revealing POMGs. Unfortunately, this generalization turns out be impossible in general, even if (i) the POMG satisfies Assumption
Generalization to multi-step weakly revealing POMGs
2 with m = 2 and a 2 1, and (ii) the learner can directly observe the opponents' actions and observations. We defer the formal statement of this hardness result and its proof Appendix
D.3
Acknowledgements
Csaba Szepesvári gratefully acknowledges the funding from Natural Sciences and Engineering Research Council (NSERC) of Canada, "Design.R Al-assisted CPS Design" (DARPA) project and the Canada CIFAR AI Chairs Program for Amii. Chi Jin gratefully acknowledges the Project X innovation fund from Princeton.
10

---

References
[1] M. G. Azar, Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272 PMLR, 2017.
[2] K. Azizzadenesheli, A. Lazaric, and A. Anandkumar. Reinforcement learning of POMDPs using spectral methods. In Conference on Learning Theory, pages 193-256. PMIR, 2016.
[3] Y. Bai and C. Jin. Provable eelf-pla algorithms for competitive reinforcement learning. arXiv preprint 2XXiv:0022.4411,, 2020.
[4] Y. Bai, C. Jin, S. Mei, and T. Yu. Near-optimal learning of extensive-form games with imperfect information. arXiv preprint (:Xi1:2202.01752, 2022.
[5] Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self-play. In Advances in Neural Information Processing Systems, 2020.
[6] C. Berner, G. Brockman, B. Chan, V. Cheung, P. Dkebiak, C. Dennison, D. Farhi, Q. Fischer,
S. Hashme, C. Hesse, al. Dota with large scale deep reinforcement learning. arXiv preprint arXiv:1912.0666 2019.
[7] S. Bernstein, E.. A. Hansen, and S. Zilberstein. Bounded policy iteration for decentralized pomdps. In Proceedings of the nineteenth international joint conference on artificial intelligence (IJCAI), pages 52-57, 2005.
[8] R. I. Brafman and M. Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, ((0ct):213-23) 2002.
[9] N. Brown and T. Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456))885-899, 2019.
[10] C. Dann, T. Lattimore, and E. Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
[11] C. Daskalakis, N. Golowich, and K. Zhang. The complexity of markov equilibrium in stochastic games. arXiv preprint arXiv:2204 .3991, 2022.
[12] G. Farina, Kroer, and Sandholm. Faster game solving via predictive Blackwell approach- ability: Connecting regret matching and mirror descent. arXiv preprint arXiv:2007.14358, 2020.
[13] G. Farina and Sandholm. Model-free online learning unknown sequential decision making problems and games. arXiv preprint arXiv:2 103. 045399 2021.
[14] G. J. Gordon. No-regret algorithms for online convex programs. In Advances in Neural Information Processing Systems, pages 489-496. Citeseer, 2007.
[15] Z. D. Guo, S. Doroudi, and E. Brunskill. A PAC RL algorithm for episodic POMDPs. In Artificial Intelligence and Statistics, pages 510-518. PMLR, 2016.
[16] S. K. Jakobsen, T. B. Sorensen, and V. Conitzer. Timeability of extensive-form games. In Proceedings of the 2016 ACM Conference Innovations in Theoretical Computer Science, pages 191-199, 2016.
[17] N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
[18] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. Jordan. Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[19] C. Jin, S. M. Kakade, A. Krishnamurthy, and Q. Liu. Sample-efficient reinforcement learning of undercomplete POMDPs. NeurIPS, 2020.
[20] C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of RI. problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34, 2021.
11

---

[21] C. Jin, Q. Liu, Y. Wang, and T. Yu. V-learning- simple, efficient, decentralized algorithm for multiagent RL. arXiv preprint arXiv:2110.14555, 2021.
[22] C. Jin, Q Liu, and T. Yu. The power of exploiter: Provable multi-agent rl in large state spaces. arXiv preprint A.Kv:2106.003355 2021.
[23] C. Jin, Z. Yang. Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, PMLR, 2020.
[24] T. Kozumo, P. Ménard. R. Mumos, and M. Valko. Model-free learning for two-player zero-sum partially observable Markov games with perfect recall. arXiv preprint arXiv:2 100.06296 2021.
[25] A. Krishnamurthy, A. Agarwal, and J. Langford. PAC reinforcement learning with rich observa- tions. Advances in Neural Information Processing Systems, 29, 2016.
[26] Q. Liu, A. Chung, C. Szepesvari, and C. Jin. When is partially observable reinforcement learning not scary? arXiv preprint, 2022.
[27] Q. Liu, Y. Wang, and C. Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. arXiv preprini urXiv:2203.06803 2022.
[28] Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self- self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
[29] E. Mossel and S. Roch. Learning nonsingular phylogenies and hidden Markov models. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 366-375, 2005.
[30] M. Mundhenk, J. Goldsmith, C. Lusena, and E. Allender. Complexity of finite-horizon Markov decision process problems. Journal of the ACM (JACM), 47(4):681-720, 2000.
[31] R. Nair, M. Tambe, M. Yokoo, D. Pynadath, and S. Marsella. Taming decentralized pomdps: Towards efficient policy computation for multiagent settings. In IJCAI, volume 3, pages 705-711. Citeseer, 2003.
[32] A. Olichock. Decentralized pomdps. In Reinforcement Learning, pages 471-503. Springer,
2012.
[33] F. A. Oliehoek and C. Amato. A concise introduction to decentralized POMDPs. Springer, 2016.
[34] A. Oliehoek, M. T. Spaan, and N. Vlassis. Optimal and approximate value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-353, 2008
[35] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of operations research, 12(3):441-450, 1987.
[36] S. Shalev-Shwartz, S. Shammah, and A. Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 1610.032900 2016.
[37] L. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10))1095 1 1100, 1953.
[38] Z. Song, S. Mei, and Y. Bai. When can we learn general-sum markov games with a large number of players sample-effiientlyy arXiv preprint 1rxiv.2110.04/844 2021.
[39] D. Szer, F. Charpillet, and S. Zilberstein, Maa*: A heuristic search algorithm for solving decentralized pomdps. arXiv preprint arXiv: 1207.1399 2012.
[40] O. Vinyals. I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)350-334 2019.
[41] N. Vlassis, M. L. Littman, and D. Barber. On the computational complexity of stochastic controller optimization in POMDPs. ACM Transactions on Computation Theory (TOCT), 4(4):1-8,
12

---

[42] C.-Y. Wei, Y.-T. Hong, and C.-J. Lu. Online reinforcement learning in stochastic games. In Advances Neural Information Processing Systems, pages 4987-4997, 2017.
[43] Q. Xie, Y. Chen, Wang. and Yang. Learning zero-sum simultaneous- moveraeeeouuoeeeeeeee move markov games using function approximation and correlated equilibrium. arXiv preprint arXiv:2002.0700 2020.
[44] A. Zanette, A. Lazarie, M. Kochenderfer, and Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, pages 10978- 10989. PMLR, 2020.
[45] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20:1 20:1729-1753 2007.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] This work
purely theoretical and we do not anticipate any potential negative social impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We provide all the proof' in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "aAFCqs2KJ_s", "reviewer": "Reviewer_9qur", "summary": "This paper considers a Multi-Agent Reinforcement Learning problem where participants have private observations that are only partially available to others. In a setting where a central learner can control all players' actions and aims to achieve an equilibrium, the authors develop algorithms to approximate equilibria with a sample-efficiency bound. Moreover, in a setting where a single player aims to optimize their reward against adversarial opponents, they also create an algorithm to achieve a sublinear upper regret bound under a weak definition of the regret.", "questions": "1. Can I have more interpretation of why the regret in Section 5 is used. Besides, are there any practical applications of this new version of regret? \n        \n2. There might be some typos and unclear parts. For example, in the definition of the POMG tuple, does $\\mathbb{T}$ means $\\mathbb{P}$? Moreover, in Definition 6, I wonder what the feasible set of strategy modifications is. Does it contain all maps from the deterministic action set to itself? ", "limitations": "I think there is no potential negative social impact of the work.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This is the first work that develops a sample efficiency algorithm to learn a large class of Partially Observable Markov Games. Moreover, the polynomial sample complexity is strong.\n\n2. The motivation of their algorithms is clear.\n\nWeakness:\n\n1. For the setting with adversarial opponents, it is better to give more intuition of the reason to use their new regret. \n        \n2. Their algorithms seems to be time-consuming.\n        \n3. There might be some typos and unclear parts that may affect understanding. Please see bullet 2 in the question section for more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_G7-cVBGUhq", "reviewer": "Reviewer_QFwE", "summary": "This paper considers the Partially Observed (general-sum) Markov Game (POMG) model, and proposes a sub-linear regret online learning algorithm that achieves a game theoretic equilibria. The algorithm is based on optimism ideas, and an assumption of weak revealing POMGs is made (which was first made in [27,37], and is quite strong actually - it implies full observability for point state distributions. The proposed algorithm achieves regret that grows as \\sqrt{K}, K=number of episodes.  ", "questions": "Q.1 Is there a way to design decentralized learning algorithms?", "limitations": "No limitations mentioned.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is nicely written, easy to understand and addresses a difficult problem.\n\nWeaknesses: \n1. I think this paper is just a bit beyond incremental, builds as it does on [27] and [37].\n2. There is a more fundamental issue whether these results are interesting at all: in a game setting, there are two types of results that are interesting: (i) offline (centralized or decentralized) algorithms that find the equilibrium, and (ii) online decentralized algorithms that minimize the regret w.r.t. the equilibrium. This paper proposes online  centralized algorithms for POMGs, which means in a game setting individual players can't really learn in a decentralized manner, i.e., learning of the equilibria is really happening via  centralized algorithm, which is hardly interesting. Actually, once you assume that an equilibria of the game can be computed by some algorithm, the results in this paper are hardly surprising building as they do on results for POMDPs in [27] and [37]. Thus, I would say the problem formulation in this paper is not interesting enough.\n3. Any way to do an empirical evaluation of your proposed algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XEqDV8hnGiT", "reviewer": "Reviewer_HtwJ", "summary": "The paper identifies a rich subclass of  Partially Observable Markov Games (POMGs), weakly revealing POMGs, and proposes algorithms for finding approximate Nash equilibria for them. The algorithm is proven to be sample efficient in this kind of game.", "questions": "In Algorithm 1, Why is the output strategy uniformly sampled from past strategies?", "limitations": "None.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The newly identified weakly revealing POMGs is interesting and practical.\n2. The proposed algorithms are intuitive and interesting. The theoretical results seem sound.\n3. The paper is well written, and the notation and definitions are clear.\n\nWeaknesses:\n1. Corollary 8 and Corollary 10, \"with probability at least 1/2\", I do not think a probability of at least 1/2 is enough.\n2. As stated in the paper, \"Algorithm 1 is computationally inefficient in general due to the steps of optimistic value estimation and equilibrium computation\". By the way, this does not harm the significance of the paper, and thanks to the authors for declaring the weakness.\n3. Lack of empirical results. Some experiments may help the readers to understand the algorithms better.\n4. line 90, $\\mathbb{T}$ is not defined, while $\\mathbb{P}$ is not introduced.\n5. line 113, the definition of $\\pi_i$ is not a bit informal.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1VrivWBlJbR", "reviewer": "Reviewer_7FnW", "summary": "This paper is the first attempt to theoretically analyze the general-sum Markov games under partial observability. The contributions of this paper are as follows:\n- It identify a rich subclass of POMGs, namely, the weakly revealing POMGs, which is statistically tackable (this is necessary as the POMGs are intackable in general as shown by the hardness results);\n- It proposes an algorithm that combines the optimism-in-face-of-uncertainty principle and MLE;\n- The proposed algorithm is shown to be efficient in the self-play setting, meaning that we can control all the agents' policies;\n- The results are extened to the adversarial setting, which is novel and also interesting.\n\nI believe that the topic of this paper is very interesting and is very relevant to the ML and RL community.", "questions": "See weakness part.", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nIdentifying a rich sub-class of tackable POMGs:\nRL problems under partial observability are known to be statistically intractable in general, even in the single-agent case, mainly due to the non-Markovian nature and resulting curse of history. However, the hardness is in a worst-case fashion. Then, it is natural to identify certain natural (well-motivated) structural assumption that empowers efficient learning. \n\nInstead of assuming the perfect-recall structure of Imperfect Information Extensive-Form Games (IIEFG), this paper considers the weakly revealing POMGs, extended from the single-agent scenario. To me, the two assumptions are natural. Intuitively, the assumption ensures that a short window of recent observations contains certain amount of information of the latent states, whose idea is natural and common under the partial observability [1-3]. Interestingly, in terms of the challenges from multi-agent scenario, the paper shows that this condition only requires to be true for the joint observations, which is new to my knowledge. I believe that this paper provides enough insights and is a good starting point for the study of POMGs.\n\nAlgorithmic novelty:\nI find that the proposed algorithms are quite clean, following the standard optimism-in-face-of-uncertainty principle. Although the algorithm is not computationally efficeint, but it seems this is a general problem on the literature, so I think this is acceptable. \n\nThe key design of the confidence set is extended from the single-agent counterpart [4] that contains the models whose likelihood is roughly consistent on the historical data (in the sense that itis close to MLE), which is also natural. The use of MLE seems to be extended from the recent result in single-agent setting [4]. But the game nature requires extra efforts to deal with, which accounts for the use of subroutines in different settings. This again is new and is complementary to the single-agent counterpart. \n\nWeakness:\nWhile I am satisfactory with the paper, I still have some minor comments and questions.\n\n1 I think some examples or hardness results are helpful to motivate the assumptions used in this paper, for a clearer presentation.\n\n2 The adversarial setting is interesting but it seems that the paper only considers the Assumption 1, which is true only for undercomplete case (O>=S). I am wondering whether efficient learning is possible for the overcomplete case? \n\nOverall, I enjoyed reading this paper and I think it contains enough insight, and interesting and non-trivial results, as compared to the single-agent works.\n\n[1] Du, S., Krishnamurthy, A., Jiang, N., Agarwal, A., Dudik, M., & Langford, J. (2019, May). Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning (pp. 1665-1674). PMLR.\n[2] Efroni, Yonathan, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. \"Provable reinforcement learning with a short-term memory.\" arXiv preprint arXiv:2202.03983 (2022).\n[3] Golowich, Noah, Ankur Moitra, and Dhruv Rohatgi. \"Learning in Observable POMDPs, without Computationally Intractable Oracles.\" arXiv preprint arXiv:2206.03446 (2022).\n[4] Qinghua Liu, Alan Chung, Csaba Szepesvari, and Chi Jin. When is partially observable reinforcement\nlearning not scary? arXiv preprint, 2022a.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept