Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games
Authors: Wenhao Zhan
Jason D. Lee
Zhuoran Yang
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement learning theory (statistical learning theory)

Abstract: We study decentralized policy learning in Markov games where we control a single agent to play with nonstationary and possibly adversarial opponents. Our goal is to develop a no-regret online learning algorithm that (i) takes actions based on the local information observed by the agent and (ii) is able to find the best policy in hindsight. For such a problem, the nonstationary state transitions due to the varying opponent pose a significant challenge. In light of a recent hardness result (Liu et al., 2022), we focus on the setting where the opponent's previous policies are revealed to the agent for decision making. With such an information structure, we propose a new algorithm, Decentralized Optimistic hypeRpolicy mIrror deScent (DORIS), which achieves $\sqrt{K}$-regret in the context of general function approximation, where $K$ is the number of episodes. Moreover, when all the agents adopt DORIS, we prove that their mixture policy constitutes an approximate coarse correlated equilibrium. In particular, DORIS maintains a hyperpolicy which is a distribution over the policy space. The hyperpolicy is updated via mirror descent, where the update direction is obtained by an optimistic variant of least-squares policy evaluation. Furthermore, to illustrate the power of our method, we apply DORIS to constrained and vector-valued MDPs, which can be formulated as zero-sum Markov games with a fictitious opponent. 

Under review as a conference paper at ICLR 2023
DECENTRALIZED OPTIMISTIC HYPERPOLICY MIRROR DESCENT: PROVABLY NO-REGRET LEARNING IN MARKOV GAMES
Anonymous authors Paper under double-biee baind review
ABSTRACT
We study decentralized policy learning in Markov games where we control a single agent to play with nonstationary and possibly adversarial opponents. Our goal is to develop a no-regret online learning algorithm that (i) takes actions based on the local information observed by the agent and (ii) is able to find the best policy in hindsight. For such a problem, the nonstationary state transitions due to the varying opponent pose a significant challenge. In light of recent hardness result [33], we focus on the setting where the opponent's 's previous policies are revealed to the agent for decision making. With such an information structure, we propose a new algorithm, Decentralized Optimistic hypeRpolicy mirror deScent (DORIS), which achieves v -rerrtt in the context of general function approximation, where K is the number of episodes. Moreover, when all the agents adopt DORIS, prove that their mixture policy constitutes an approximate coarse correlated equilibrium. In particular, DORIS maintains a hyperpolicy which is distribution over the policy space. The hyperpolicy updated via mirror descent, where the update direction is obtained by an optimistic variant of least-squares policy evaluation. Furthermore, to illustrate the power of our method, we apply DORIS to constrained and vector-valued MDPs, which can be formulated as zero-sum Markov games with a fictitious opponent.
INTRODUCTION
Multi-agent reinforcement learning (MARL) studies how each agent learns to maximize its cumulative rewards by interacting with the environment as well as other agents, where the state transitions and rewards are affected by the actions of all the agents. Equipped with powerful function approximators
such as deep neural networks [31] J. MARL has achieved significant empirical success in various domains including the game of Go [47], StarCraft [50], DOTA2 [5], Atari [38], multi-agent robotics systems [8] and autonomous driving [45]. Compared with the centralized setting where a central controller collects the information of all agents and coordinates their behaviors, decentralized algo- rithms [19, 42] where each agent autonomously chooses its action based on its own local information are often more desirable in MARL applications. In specific, decentralized methods (I) are easier to implement and enjoy better scalability, (2) are more robust to possible adversaries, and (3) require less communication overhead [21, 22, 9, 59, 18].
In this work, we aim to design a provably efficient decentralized reinforcement learning (RL) algorithm in the online setting with function approximation. In the sequel, for the ease of presentation, we refer to the controllable agent as the player and regard the rest of the agents as a meta-agent, called the opponent, which specifies its policies arbitrarily. Our goal is maximize the cumulative rewards of the player in the face of a possibly adversarial opponent, in the online setting where the policies of the player and opponent can be based adaptively gathered local information.
From a theoretical perspective, arguably the most distinctive challenge of the decentralized setting is nonstationarity. That is, from the perspective of any agent, the states transitions affected by the policies of other agents in an unpredictable and potentially adversarial way and are thus nonstationary. This is in stark contrast the centralized setting which can be regarded the central controller which decides the actions for all the players. Furthermore, in the online setting, the environment unknown, achieve sample efficiency, the player needs to strike balance
standard RL problem for

---

Under review as a conference paper at ICLR 2023
between exploration and exploitation in the context of function approximation and in the presence of an adversarial opponent. The dual challenges of nonstationarity and efficient exploration are thus intertwined, making it challenging to develop provably efficient decentralized MARL algorithms.
Consequently, there seem only limited theoretical understanding of the decentralized MARL setting with a possibly adversarial opponent. Most of the existing algorithms [7, 53, 49, 27, 23] can only compete against the Nash value of the Markov game when faced with an arbitrary opponent. This is much weaker baseline compared with the results in classic matrix games [17, 1] where the player is required to compete against the best fixed policy in hindsight. Meanwhile, [33] seems the only work we know that can achieve no-regret learning in MARL against the best hindsight policy, which focuses on the policy revealing setting where the player observes the policies played by the opponent in previous episodes. However, the algorithm and theory in this work are limited to tabular cases and fail to deal with large or even continuous state and action space. To this end, we would like to answer the following question:
Can we design a decentralized MARL algorithm that provably achieves no-regret against the best fixed policy hindsight in the context of function approximation?
In this work, we provide a positive answer to the above question under the policy revealing setting with general function approximation. In specific, we propose an actor-critic-type algorithm [29] called DORIS, which maintains a distribution over the policy space, named hyperpolicy, for decision- making. To combat the nonstationarity, DORIS updates the hyperpoliey via mirror descent (or equivalently, Hedge [16]). Furthermore, to encourage exploration, the descent directions of mirror descent are obtained by solving optimistic variants of policy evaluation subproblems with general function approximation, which only involve the local information of the player. Under standard regularity assumptions on the underlying function classes, we prove that DORIS achieves a sublinear regret in the presence of an adversarial opponent. In addition, when the agents all adopt DORIS independently, we prove that their average policy constitutes an approximate coarse correlated equilibrium. At the core of our analysis is a new complexity measure of function classes that is tailored to the decentralized MARL setting. Furthermore, demonstrate the power of DORIS, we adapt it for solving constrained Markov decision process (CMDP) and vector-values Markov decision process (VMDP), which can both be formulated as a zero-sum Markov game with a fictitious opponent.
Our Contributions. Our contributions are four-fold. First, we propose new decentralized policy optimization algorithm, DORIS, that provably achieves no-regret in the context of general function approximation. As a result, when all agents adopt DORIS, their average policy converges to CCE of the Markov game. Secondly, we propose new complexity measure named Bellman Evaluation Eluder dimension, which generalizes Bellman Eluder dimension [25] for single-agent MDP to decentralized learning in Markov games, which might be of independent interest. Third, we modify DORIS for solving CMDP with general function approximation, which shown achieve sublinear regret and constraint violation. Finally, we extend DORIS to solving the approchability task [36] in valuud Markov decision process (VMDP) and attain near-optimal solution. To our best knowledge, DORIS seems the first provably efficient decentralized algorithm for achieving no-regret in MARL with general function approximation.
Notations, In this paper we let [n]] [1.-.. .n} for any integer n. We denote the set of probability distributions over any set S by As or A(S). We also let || denote the noom by default.
Related works. Our work is related to the bodies of literature on decentralized learning with an adversarial opponent, finding equílibria in self-play Markov games, CMDPs and VMDPs. These works either consider centralized setting or do not have function approximation in decentralized online setting. Due to the page limit, compare to these works in Appendix B.
2 PRELIMINARIES
2.1 MARKOV GAMES
Let us consider an n-agent general-sum Markov game (MG) MMG = (S, (A.) (Pr) 1 (ra,)) H), where S is the state space, A; is the action space of the i-th agent, Pa : S x Ih Ai- + ASS) is the transition function at the h-th step, Th,; S x II A, - R is the reward function of the i-th agent at the h-th step and H is the length of each episode. We assume
2

---

Under review as a conference paper at ICLR 2023
each episode starts at fixed start state $1 and terminates at sH+1. At step h [H] each agent i observes the state 8h and takes action agss simultaneously. After that, agent receives its own reward (5, an) where an = (an,1, .hhn) is the joint action and the environment transits to new state 8/+1 ~ Pr.(-sn, an).
Policy. A policy of the i-th agent μi, [un, S - AA. heee specifies the action selection probability of agent i each state at each step. In the following discussion we will drop the h in Mn, when it is clear from the context. We use to represent the joint policy of all agents and p-; to denote the joint policy of all agents other than Further, we assume each agent chooses its policy from policy class II, Similarly, let II=; : [I 11 denote the product of all agents' policy classes excluding the i-th agent.
Value functions and Bellman operators. Given any joint policy n, the i-th agent's value function VV. S - IR and action-value (or Q) function Q%, S IT== A; - IR characterize its expected cumulative rewards given a state or a state-action pair, which are defined as below:
H
3] Qh. (h.. = E.
H
Vr, = E
Σ
rL, ai) 8n 8n =8
Σ I=A
(1, ai) 8, an a
1=h
where the expectation is w.r.t to the distribution of the trajectory induced by executing the joint policy ı in MMG. Here we suppose the action-value function bounded:
Q7, (s, a) Vmaax Vs, a, h, i,
Notice that when the reward function is bounded in [0, 1]. Vinxx H naturally.
2.2 DECENTRALIZED POLICY LEARNING
In this paper we consider the decentralized learning setting [27, 23, 33] where only one agent under our control, which we call player, and the other agents can be adversarial. Without loss of generality, assume that can only control agent and view the other agents writing, we use A, Thy p. 11, VE QJ, to denote M4.1.A1, Th, P1, 111, Vi, Q7, respectively. We also use ,y, B, v, II' to represent the action, the action space, the policy and the policy class of the meta opponent.
meta opponent. To simplify
By decentralized we mean during the episode, the player can only observe its own rewards, actions and some information of the opponent specified by the protocol, i.e., {sf af, Thi h= where (Jr) is the information revealed by the opponent in each episode and we will specify it later. At the beginning of the (-th episode, the player chooses a policy μe' from its policy class II based only on its local information collected from previous episodes, without any coordination from centralized controller. Meanwhile, the opponent selects n² from II' secretly and probably adversely.
The learning objective is minimize the regret of the player by comparing its performance against the best fixed policy in hindsight as standard in online learning literature [1, 20]:
Definition (Regret). Suppose (n': v²) are the policies played by the player and the opponent the I-th episode. Then the regret for K episodes is defined
K vul
Regret K)
V.XU (51)
Σv
xv²
(S1);
PETT
t=1
where y X denotes the joint policy where the player and the opponent play and independently. We also use to denote pº x v².
Achieving low regrets defined in (1) indicates that if sample policy p uniformly from {u KKK at random, the resulting mixture policy will be close to the best fixed policy in hindsight.
Relation between Definition 1 and equilibria. An inspiration for definition of regrets comes from the tight connection between low regrets and equilibria the matrix game [17, 6, 10]. By viewing each policy in the policy class pure strategy in the matrix game, notion of equílibria in matrix games to Markov games naturally. In particular, a correlated mixed strategy profile मे can be defined mixture of the joint policy of all agents, i.e., म E A(T II,) Suppose the marginal distribution of a over the policy of agent i is p4, then
generalize the
that μ4 is
3

---

Under review as a conference paper at ICLR 2023
mixture of the policies in II, For correlated profile, the agents might not play their mixed policies H. independently, which means that स might not be the product of T.. A coarse correlated equilibrium (CCE) is correlated profile that all the agents have no incentive to deviate from by playing different independent policy:
Definition 2 (e-approximate coarse correlated equilibrium (CCE) for n-player MG), A correlated stralegy profile म is an e e-approximate course correlated equilibrium if we have for all i E [m]
((1)
Z max p'Ell.
Vi (81) -,
(2)
where Pi is the marginal distribution of H over the joint policy of all agents other than i.
Remark 1. Our definition of correlated strategy profile and CCEs is slightly different from [35].
This is because we are considering with policy classes while [35] does not. In fact, our definition is more strict in the sense that correlated profile satisfying our definition must also satisfy theirs.
II( Pt. is also called Nash Equilibrium (NE). We will use our algorithm as an example to show that if decentralized algorithm can achieve low regrets under Definition 1, we will be able to find CCE by running the algorithm independently for each agent just like in classic matrix games.
Specially, if a CCE satisfies
2.3 FUNCTION APPROXIMATION
To deal with the potentially large or even infinite state and action space, we consider learning with general value function upproximation in this paper [24, 25]. We assume the player is given a function class F = Fi x... FH+1 (Fr S. (S x x B + [0, V Vmaxx) 1) to approximate action-value functions. Since there is no reward in state sH+1, we let (s, a, b) = 0 for all s E S, a E A, E B, f F.
To measure the size of F, we use F to denote its cardinality when F is finite. For infinite function classes, we use e-covering number to measure its size, which is defined as follows:
Definition 3 (e-covering number). The e-covering number of F, denoted by NN((), is the minimum integer n such that there exists a subset F' C F with |Fl = n and for any I E F there exists I' E F' such that [H fl fl S.
In addition to the size, we also need to impose some complexity assumption on the structure of the function class to achieve small generalization error. Here we introduce one of such structure complexity measures called Distributional Eluder (DE) dimension [25], which we will utilize in our subsequent analysis. First let us define independence between distributions:
Definition 4 (e-independence between distributions). Let W be function class defined on X, and P. ... Pn be probability measures over X. We say P is e-independent of (pr." ... Paa} with respect to W if there exists w E W such that VE (Ep, I &but [p[w]] c.
From the definition we can see that a probability distribution p is independent from {p).-.. : Pa3 if there exists a discriminator function in W such that the function values are small at {pi. pn while large at p. DE dimension is simply the length of the longest sequence of independent probability measures that the function class can discriminate:
Definition 5 (Distributional Eluder (DE) dimension). Let W be a function class defined on X, and Q be a family of probability measures over X. The distributional Eluder dimension dimpe (W. Q, c) is the length of the longest sequence {p1, ) Q such that there exists c' 2 c @where pa is é' <-independent of {Pr,".. pi- 1 } for all i E [m].
Eluder dimension, another commonly-used complexity measure proposed by [43], is special case of DE dimension. we choose @ (d. (-)læ X where (-) is the dirac measure centered at x. then the Eluder dimension can be formulated as
dimg (W, c) dimpe - W, Q.
where W - W = {wi W2 : W1, E WJ. Many function classes in MDPs are known to have low Eluder dimension, including linear MDPs [28], generalized linear complete models [52] and kernel MDPs [25].
We also assume the existence of an auxiliary function class G = 91 .... Gnr (Gn C Ax [0, Vmax))) )) to capture the results of applying Bellman operators on F as in [25, 27). When F satisfies completeness (Assumption 3). we can simply choose = F.
4

---

Under review as a conference paper at ICLR 2023
3 ALGORITHM: DORIS
Policy revealing setting. Recall that in decentralized policy learning setting, the player is also able observe some information of the opponent, denoted by Th, aside from its own actions and rewards.
There have been works studying the case where Th = 0 [49] and Jn = bn [27, 23J in two-player zero-sum games. However, their benchmark is the Nash value of the Markov game, i.c. Vi2 xx" (s1)
where μ x v² is an NE, which is strictly weaker than our benchmark max Σ Vuxu" (s1) in two-player zero-sum games. fact, [33] has showed achieving low regrets under Definition is exponentially hard in tabular cases when the opponent's 's policies are not revealed (see Appendix E.2
for details). Therefore in this paper we let Jh {bn, } just like [33] and call this information
structure policy revealing setting.
That said, even in policy revealing setting, the challenge of nonstationarity still exists because the opponent's policy can be adversarial and only gets revealed after the player plays a policy. Thus from the perspective of the player, the transition kernel ( a) == Es (a) Pa (-1e a, b) still changes in an unpredictable way across episodes. In addition, the problem of how to balance exploration
and exploitation with general function approximation also remains due to the unknown transition probability. In this section we propose DORIS, an algorithm that is capable of handling both these challenges and achieving a v K regret upper bound in policy revealing setting.
Remark 2. When the opponent's 's policy is not revealed but changes slowly, we indeed can infer the opponent's 's policy approximately via the procedures in [39, 46] and this can be viewed as an #ppproximmae policy revealing condition in practice.
DOIIS. Intuitively, our algorithm is an actor-critic/ mirror descent (Hedge) algorithm where each expert and the performance of each expert episode t is given by
policy f in II is regarded the value function of Viux"" (s1). We call it Decentralized Optimistic hypeRpolicy mIrror deScent (DORIS). DORIS possesses three important features, whose details are shown in Algorithm 1:
Motivated from the adversarial bandit literature [1, 20, 30] and no-regret learning works [33], DORIS maintains a distribution p over the policies II, which we call hyperpolicy, to combat the nonstaionarity. The hyperpolicy is updated using Hedge, with the reward of each policy μ being an estimation of the value function V.uX"' (s1). This is equivalent to running mirror ascent algorithm over the policy space IT with the gradient being Vi (81).
Hyperpolicy and Hedge:
Optimism: However, do not have access the exact value function since the transition probability is unknown, which forces us to deal with the exploration-exploitatio tradeoff. Here we utilize the Optimism in the Face of Uncertainty principle [2, 28, 25, 27, 23] and choose our estimation V'(1) to be optimistic with respect to the true value V/uXa (s1). In this way DORIS will prefer policies with more uncertainty and thus encourage exploration in the Markov game.
Optimistic policy evaluation with general function approximation: Finally we need to design
an efficient method to obtain such optimistic estimation V (p)) with general function approximation. Here propose OptL to accomplish this task. In short, LStL constructs confidence set for the target action-value function Q"*" based on the player's local information and chooses optimistic estimation from the confidence set, as shown in Algorithm 2. The construction of the confidence set utilizes the fact that Q satisfies the Bellman equation [41]:
2 (s, ( b) = (T Th Q (s, = ra,3, a, b) + Eg (-I..s.. Q (s' (8', v)]:
where Quxi (5', (,,)). = -D) Ea--m((1>)) (.0 1 a', B'). We call The the Bellman operator induced by a x и at the fi-th step. Then the construction rule of Bo(u, v) is based on least-squares policy evaluation with slackness 3 as below:
BD(u,v) + {SEF: (
CDlfa, fut S inf Co(gn, fn+1, + 8, E [m1] (3)
gEg
where LD is the empirical Bellman residuals on D:
LolEn, p))=
Σ
(sh. an, bn) - rh (,)
5

---

Under review as a conference paper at ICLR 2023
Algorithm DORIS
Input:
learning rate confidence parameter 3.
Initialize p E Ån be uniform over II.
1,. K do
Collect samples:
The player samples n² from p'.
The player runs 1² against the opponent and collects D, = (6), ff,,0f. 0f.rrf ,441)
Update policy distribution:
The opponent reveals policy s' the player.
('() + OptLSPE((, v', D1
Ay E II.
(1) x (')) exp(1) V (A)), EI.
end for
Algorithm 2 OptLSPE 11, U, D,F,
Construct (p, v) based on DD via (3). Select V <- maX U,,
return V.
Decentralized Algorithm. Here want to highlight that DORIS is decentralized algorithm because the player can run DORIS based only on its local information, i.e., {sh, ah Th, Th J. and we do not make any assumptions the policies of the opponent. We also discuss the computational complexity of DORIS in Appendix E.3.
Comparison with OPMD [33]. The hyperpolicy and Hedge part of DORIS indeed follows OPMD proposed by [33], which is an algorithm for no-regret learning in tabular MG. The novelty of DORIS lies in the new policy evaluation algorithm specially designed for the policy revealing setting that can tackle general function approximation. We also need to propose new techniques to analyze the performance of DORIS, which is more complicated than tabular cases. See Appendix E. for more detailed comparison.
3.1 DORIS IN SELF-PLAY SETTING
Apart from decentralized learning setting with possibly adversarial opponent, we are also interested in the self-play setting where we can control all the agents and need to find an equilibrium for the n- agent general-sum Markov game. Inspired by the existing relationships between no-regret learning and CCES in matrix games [17, 6, 10], natural idea is to simply let all agents run DORIS independently. To achieve this, we assume each agent given a value function class F, Fi, X
FH,, and an auxiliary function class G. G1.> X x... x GH, in DCRIS, and run DORIS with learning rate m
and confidence parameter 3, by viewing the other agents as opponent. Suppose the policies played by agent during K episodes are [m{)/ then we output the final joint policy as uniform mixture:
म Unif ((ILET uh.... ... IIe m }).
See Algorithm 3 for more details.
Remark 3. Algorithm 3 is also decentralized algorithm since every agent runs their local algorithm independently without coordination. The only step that requires centralized control is the output process where all the agents need to share the same iteration index, which is also required in the existing decentralized algorithms [35, 26).
THEORETICAL GUARANTEES
In this section we analyze the theoretical performance of DORIS in decentralized policy learning and self-play setting. We first introduce new complexity measure for function classes, called Bellman Evaluation Eluder (BEE) dimension, and then illustrate the regret and sample complexity bounds based on this new measure.
4.1 BELLMAN EVALUATION ELUDER DIMENSION
Motivated from Bellman Eluder (BE) dimension in classic MDPs and its variants in MGs [25, 27, 23), propose measure specifically tailored the decentralized policy learning setting, called

---

Under review as a conference paper at ICLR 2023
Bellman Evaluation Eluder (BEE) dimension. First, for any function class F, we define (I- T. )F to be the Bellman residuals induced by the policies in II and II':
(I Th ) Un - Jn+1 J E F (I,EE
Then Bellman Evaluation Eluder (BEE) dimension is the DE dimension of the Bellman residuals induced by the policy class II and 11' on function class F:
Definition 6. The e- e-Bellman Evaluation Eluder dimension of function class F on distribution family Q with respect to the policy class IT TT' is defined as follows:
dimBEr (F, e, II, Q) == max dimpr((I - 11,111 Qh.c). [M(M)
-Thh
BEE dimension is able to capture the generalization error of evaluating value function Vaxe where J IV E II', which is of the most essential tasks in decentralized policy space optimization as shown in D.RIS. Similar to [25, 27, 23), we mainly consider two distribution families for Q here:
o ketri the collection of all probability measures over S A x B each step when executing (1, 1) E II IT'.
Q² = (2% h the collection of all probability measures that put measure on single state-action pair (s, a, b) at each step.
We also use dimBEr (F. II, IT') denote min (ondimmBEeFF.co II, IT', Q²), dimBEr (F, c, IT' Q?)} for simplicity in the following discussion.
Relation with Eluder dimension. To illustrate the generality of BEE dimension, we show that all function classes with low Eluder dimension also have low BEE dimension. as long as completeness (Assumption is satisfied. More specifically, we have the following proposition and its proof is deferred to Appendix F:
Proposition 1. Assume F satisfies completeness, i.e. The fati E FF. F, I., [H]. Then for all 0, we have
dimBEE (F.BEE(FFcCM F,,,IIIIII), S max dimg(Fn,,))
(4)
he[#]
Inequality (4) shows that BEE dimension is always upper bounded by Eluder dimension when completeness is satisfied. With Proposition 1, Appendix validates that kernel Markov games (including tabular Markov games and linear Markov games) and generalized linear complete models all have small Bellman Evaluation Eluder Dimension. Furthermore, in this case the upper bound of BEE dimension does not depend on II and II', which is desirable property when II and II' is large.
Comparison with multi-agent BE dimension. Jin et al. [27], Huang et al. [23] also propose a variant of BE dimension for Markov games called multi-agent BE dimension. However, this complexity measure and its analysis techniques are not applicable our setting because DORTS 5 is different from their algorithms in terms of confidence set construction and optimism. See Appendix E. for details.
4.2 DECENTRAL ALIZED POLICY LEARNING REGRET
Next we present the regret analysis for DORIS in decentralized policy learning setting, For simplicity, we focus on finite 11 here:
Assumption 1 (Finite player's policy class). We assume 1I is finite.
We consider two cases, the oblivious opponent (i.c., the opponent determines {M*} K secretly before the game starts) and the adaptive opponent (i.c., the opponent determines its policy adaptively as the game goes on) separately. The difference between these two cases lies in the policy evaluation step DORIS. The policy n² of an oblivious opponent does not depend on the collected dataset D Pi:r-1 and thus VP.. easier to evaluate. However, for an adaptive opponent, D² will chosen adaptively based Dia-1 and we need to introduce an additional union bound over II' when analyzing the evaluation error of Ve.."
Oblivious opponent. To attain accurate value function estimation, we first need to introduce two standard assumptions, realizability and generalized completeness, on F and G [25, 27]. Here realizability refers to that all the true action value functions belong to F and generalized completeness means that G contains all the results of applying Bellman operator the functions in F.
7

---

Under review as a conference paper at ICLR 2023
Assumption 2 (Realizability and generalized completeness). Assume that for any h [H]
I E (u',..., ,vk), JuK], fh+1 E Fn+1, we have Qh E Fn; Th fu+1 9h-
Remark 4. Some existing works [57, 23] assume the completeness assumption, which can also be generalized our setting:
Assumption 3. Assume for any h E [ E I1, II' fu+1 E Fiut1, we have The fu+1 E Fi.
We want to clarify that Assumption 3 is stronger than generalized completeness in Assumplion 2 since if Assumption 3 holds, we can simply let G = F to satisfy generalized completeness.
Appendix G shows that realizability and generalized completeness are satisfied in many examples including tabular MGs, linear MGs and kernel MGs. With the above assumptions, we have Theorem to characterize the regret of DORIS when the opponent oblivious, whose proof sketch is deferred to Appendix I. To simplify writing, we use the following notations in Theorem 1:
dBEE dimBEE (F, V1/K,IIIII) NNow := NNFug(Vuaas K)KH.
Theorem 1 (Regret of Oblivious Adversary). Under Assumption 1,2, there exists an absolute constant such that for any 5 (0, K E N, if we choose
cV2 max log(NNov /T))) and
77 vlog [I]
mixx) DORIS, then with probability at least 1, 5, we have:
Regret(K) < O (HVmax v K KdBEF log (Noww (
(5)
The VK regret bound in Theorem 1 is consistent with the rate in tabular case [33] and suggests that the uniform mixture of the output policies { 1= is an e-approximate best policy in hindsight when K Ō(L/E)). The complexity of the problem affects the regret through the covering number and the BEE dimension, implying that BEE dimension indeed captures the essence of this problem. Further, in oblivious setting. the regret bound in (5) does not depend on II' directly (the upper bound of the BEE dimension also independent of IT' in some special cases as shown Proposition 1) and thus Theorem can still hold when IT' is infinite, as long as Assumptions 2 is satisfied.
Adaptive Opponent. the adaptive setting, we first need to modify Assumption to hold for all E IT' since o' depends on the collected data (recall that II is the player's policy class and IT' is the opponent's 's policy class):
Assumption 4 (Uniform realizability and generalized completeness). Assume that for any h [H] μ II, E II', fu41 Fh+1,, we have QK*" E Fh,
fu+1 Gi-
Further, as we have mentioned before, we need to introduce a union bound over the policies in II' in our analysis and thus we also assume II' be finite for simplicity.
Assumption 5 (Finite opponent's ' policy class). We assume I1' is finite.
Remark 5. It is straightforward to generalize our analysis to infinite 11' by replacing [1I' with the covering number of 11', However, the regret still depends on the size of 11', which not the case in tabular setting [33]. This dependency originates from our model-free type of policy evaluation algorithm (Algorithm 2) and is inevitable for DORIS in general. That said, when the Markov game has special structures (e.g., the Markov games in Appendix C and D), we can avoid this dependency.
With the above assumptions, we have Theorem 2 to show that DORIS can still achieve sublinear regret in adaptive setting, whose proof is deferred to Section I:
Theorem 2 (Regret of Adaptive Adversary). Under Assumption 1,4,5, there exists an absolute
constant such that for any 8 (0, 11, K N, choosing = cV2 max log(Non ( and
17 / /log [K]/(KV
V2nax) in DORIS, then with probability at least 8 we have:
Regret( K) S O HV v KdBEE log (Ncov (17)))))
(6)
We can that in adaptive setting the regret also scales with VK, implying that DORIS can still find an e-approximate best policy in hindsight with Ō(1/²2) episodes even when the opponent is adaptive. Compared to Theorem 1, Theorem 2 has an additional log [II'] in the upper bound (6), which comes from the union bound over II' in the analysis.
Intuitions the regret bounds. The regrets in Theorem and Theorem can be decomposed to two parts, the online learning error incurred by Hedge and the cumulative value function estimation error incurred by OptL..E.. From the online learning literature [20], the online learning error is
8

---

Under review as a conference paper at ICLR 2023
O(V V K log [I]) by viewing the policies in II experts and V (1)) as the reward function of expert μ.. For the estimation error, we utilize BEE dimensions to bridge V (²(x)) Vi with the function's empirical Bellman residuals on Pi--1. This further incurs O(V V KdBE)) in the results. Our technical contribution mainly lies in bounding the cumulative value function estimation error with the newly proposed BEE dimensions, which different from [25] where they focus on bounding the cumulative distance from the optimal value function.
Comparison with existing works. There have been works studying decentralized policy learning. However, most of them [7, 53, 49, 27, 23] only competes against the Nash value in two-player zero-sum games, which is much weaker baseline than ours. [33] can achieve VK regret under Definition 1, but they are restricted in tabular cases and the bound becomes vacuous with more complicated cases like linear MGs and kernel MGs in Appendix H. DORIS is the first algorithm that can achieve vK regret under Definition 1 with general function approximation and is capable of tackling all models with low BEE dimension, including linear MGs, kernel MGs and generalized linear complete models. More details are deferred to Appendix E.I.
4.3 SELF-PLAY SAMPLE COMPLEXITY
Our previous discussion assumes the opponent arbitrary or even adversary. A natural question is to ask whether there are any additional guarantees if the player and opponent run DORIS simultaneously. which is exactly the self self-play setting. The following corollary answers this question affirmatively and shows that Algorithm 3 can find an approximate CCE т efficiently:
Corollary 1. Suppose Assumption 1,4 hold for all the agents i and its corresponding F,, Gc, II,, II Then for any 5 E (0, 11, > 0, if we choose
K K2 0 H2
max ve(n
dBEE,
(log/Coons
+
Σ log [1 log(n/6)) 10g((//1))//)) j=1
(7)
max
where dBEE, and Noov.s are defined respectively as
dBEE, == dimBEE (Fe, VI/K, 11, I1_;,, Noov, := Nu (Vmax/ K))/KKKKKK H,
and set Br = cV2
max log(Noov
Vlog [L, m then with probability at
=
least 1 8, ât is e-approximate CCE.
The proof is deferred to Appendix K. Corollary shows that if we run DCRIS independently for each agent, we are able to find e-approximate CCE with ((1/c²) samples. This can be regarded as counterpart in Markov games to the classic connection between no-regret learning algorithms and equilibria in matrix games. However, this guarantee does not hold if an algorithm can only achieve low regrets with respect to the Nash values.
Avoiding curse of multiagents. The sample complexity in (7) avoids exponential scaling with the number of agents n and only scales with max dBEE,,, maxieja] Noov, and Σÿ log [II suggesting that statistically Algorithm 3 is able to escape the curse-of-mulliagenn problem in the literature [26]. Nevertheless, the input dimension of functions in F; and Gi may scale with the number of agents, leading to the computational inefficiency of OptLSPE. We comment that finding computational efficient algorithms is beyond the scope of this paper and we leave future works.
Comparison with existing algorithms. There have been many works studying how to find equi- libria in Markov games. However, most of them are focused on centralized two-player zero-sum games [3, 56, 27, 23] rather than decentralized algorithms. For decentralized algorithms, existing literature mainly handle with potential Markov games [60, 32, 12] and two-player zero-sum games [11, 44, 54]. [35, 26] are able tackle decentralized multi-agent general-sum Markov games while their algorithms are restricted to tabular cases. Algorithm 3 can deal with more general cases with function approximation and policy classes in multi-agent general-sum games. Furthermore, compared to the above works. DORIS has an additional advantage of robustness to adversaries since all the benign agents can exploit the opponents and achieve no-regret learning.
Extensions. Although Theorem 1, Theorem 2 and Corollary 1 are aimed at Markov games, DORIS can be applied to a much larger scope of problems. Two such problems are finding the optimal policy in constrained MDPs and vector-valued MDPs. We will investigate these two problems in Appendix C and D, where we demonstrate how to convert such problems into Markov games with a fictitious opponent by duality that DORIS is ready to use.

---

Under review as a conference paper at ICLR 2023
REFERENCES
[1] Anderson, T. (2008). The theory and practice of online learning. Athabasca University Press.
[2] Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In Proceedings the 34th International Conference on Machine Learning Volume 70, pages 263-272. JMLR. org.
Soitninng-Volmme
[3] Bai, Y. and Jin, C. (2020). Provable self-play algorithms for competitive reinforcement learning. In International conference machine learning, pages 551-560. PMLR.
[4] Bai, Y., Jin, C., and Yu, T. (2020). Near-optimal reinforcement learning with self- Advances neural information processing systems, 33:2159-2170.
[5] Berner, C., Brockman, G., Chan, B., Cheung. V., Dębiak, P., Dennison, C., Farhi, D., Fischer, Q.. Hashme, S., Hesse, C., et al. (2019). Dota 2 with large scale deep reinforcement learning, arXiv preprint arXiv: 1912.06680....
[6] Blum, A. and Monsour, (2007). Learning, regret minimization, and equilibria.
[7] Brafman, I. and Tennenholtz, M. (2002). R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-231,
[8] Brambilla, M., Ferrante, E., Birattari, M., and Dorigo, M. (2013). Swarm robotics: review from the swarm engineering perspective. Swarm Intelligence, 7(1):1441
[9] Canese, L., Cardarilli, G. C., Di Nunzio, L., Fazzolari, R., Giardino, D., Re. M., and Spanò, (2021). Multi-agent reinforcement learning: A review of challenges and applications. Applied Sciences, I(11))4
[10] Daskalakis, C., Deckelbaum, A., and Kim, A. (2011). Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms,, pages 235-254. SIAM.
[11] Daskalakis, C., Foster, D. J., and Golowich, N. (2020). Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540.
[12] Ding, D., Wei, C.-Y., Zhang, K., and Jovanović, M. R. (2022). Independent policy gradient for large-scale scale markov potential games: Sharper rates, function approximation, and game game-agnostic convergence. arXiv preprint arXiv:2202.04129,
[13] Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovie, M. (2021), Provably efficient safe explo- ration via primal-dual policy optimization. International Conference on Artificial Intelligence and Statistics, pages 32223312. PMLR.
[14] Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization in rl.
[15] Efroni, Y., Mannor, S., and Pirotta, M. (2020). Exploration-explootation in constrained MDPs. arXiv preprini 20X0:20033002189
[16] Freund, Y. and Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 159199119-139,
[17] Fudenberg, D. and Tirole, (1991). Game theory. MIT press.
[18] Gronauer, S. and Diepold, K. (2022). Multi-agent deep reinforcement learning: survey. Artificial Intelligence Review, 55(2):895-943.
[19] Gupta, J. K., Egorov, M., and Kochenderfer, M. (2017). Cooperative multi-agent control using deep reinforcement learning. In International conference on autonomous agents and multiagent systems, pages 66-83. Springer.
[20] Hazan, F. et al. (2016). Introduction to online convex optimization. Foundations and Trends Optimization, 257-4):
10

---

Under review as a conference paper at ICLR 2023
[21] Hernandez-Leal, P., Kartal, B., and Taylor, M. E. (2018). Is multiagent deep reinforcement learning the answer or the question? brief survey. learning, 21:22.
[22] Hernandez-Leal, P., Kartal, B., and Taylor, M. E. (2019). A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 33(6):750-777,
[23] Huang, B., Lee, J. D., Wang. Z., and Yang, Z. (2021). Towards general function approximation in zero-sum markov games. arXiv preprint arXiv:2107.14702.
[24] Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, E. (2017). Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, volume 70, pages 1704-1713. PMLR.
[25] Jin, C., Liu, Q. and Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34.
[26] Jin, C., Liu, Q., Wang, Y., and Yu, T. (2021b). V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint 10.55521
[27] Jin, C., Liu, Q., and Yu, T. (2021c). The power of exploiter: Provable multi-agent rl in large state spaces. arXiv preprint arXiv:2106.03335
[28] Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137-2143. PMLR.
[29] Konda, V. and Tsitsiklis, (1999). Actor-critic algorithms. Advances in neural information processing systems, 12.
[30] Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
[31] LeCun, Y., Bengio, Y., and Hinton, G. (2015). Deep learning. Nature, (21 444.
[32] Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. (2021). Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2/06.01969,
[33] Liu, Q., Wang, Y., and Jin, C. (2022). Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. arXiv preprint arXiv:2203.00 06803
[34] Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. (2021). Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34.
[35] Mao, W., Yang. L. F., Zhang, K., and Başar, T. (2021). On improving model-free algorithms for decentralized multi-agent reinforcement learning.
[36] Miryoosefi, S., Brantley, K., Daume III, H., Dudik, M., and Schapire, R. E. (2019). Rein- forcement learning with convex constraints. Advances in Neural Information Processing Systems, 32.
[37] Miryoosefi, S. and Jin, C. (2021). A simple reward-free approach to constrained reinforcement learning. arXiv preprint arXiv:2107.05216.
[38] Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv: 1312.5602.
[39] Nakamura, M. and Ohtsuki, H. (2016). Optimal decision rules in repeated games where players infer an opponent's mind via simplified belief calculation. Games, 7(3):99.
[40] Paternain, S., Chamon, I.., Calvo-Fullana, M., and Ribeiro, A. (2019). Constrained rein- forcement learning has zero duality gap. Advances Neural Information Processing Systems, 32.
[41] Puterman, M. I.. (1994). Markov decision processes: Discrete stochastic dynamic programming.

---

Under review as a conference paper at ICLR 2023
[42] Rashid, T., Samvelyan, M., Schroeder, C., Farquhar, G., Foerster, J., and Whiteson, S. (2018). Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4295-4304. PMLR.
[43] Russo, D. and Van Roy. B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26.
[44] Sayin, M.. Zhang, K., Leslie, D., Basar, T., and Ozdaglar, A. (2021). Decentralized q-learning in zero-sum markov games. Advances in Neural Information Processing Systems, 34.
[45] Shalev-Shwartz, S., Shammah, S., and Shashua, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1110003295.
[46] Shen, M. and How, J. P. (2021). Robust opponent modeling via adversarial ensemble rein- forcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 31, pages 578-587.
[47] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser,
J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):4844455
[48] Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. (2009). Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995.
[49] Tian, Y., Wang, Y., Yu, T., and Sra, S. (2021). Online learning in unknown markov games. In International conference on machine learning, pages 10279-10288. PMLR.
[50] Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. (2019). Grandmaster level in starcraft using multi-agen reinforcement learning. Nature, 575(7782):350335
[51] Wainwright, M. (2019). High-Dimensional Statistics: Non-Asymptotii Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
[52] Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. (2019). Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint 1r1iv: 36.
[53] Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. (2017). Online reinforcement learning in stochastic games. Advances in Neural Information Processing Systems, 30.
[54] Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. (2021a). Last-iterate convergence of decen- tralized optimistic gradient descent/ascent in aafinitehhorizon competitive markov games. In Conference on Learning Theory, pages 4259-4299. PMLR.
[55] Wei, H., Liu, X., and Ying, L. (2021b). provably-efficien model-free algorithm for constrained markov decision processes. arXiv preprint arxiv:2106.01577.
[56] Xie, Q. Chen, Y., Wang. Z., and Yang, Z. (2020). Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibruum. In Conference on learning theory, pages 3674-3682, PMLR.
[57] Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint arXiv:2106.06926
[58] Yu, T., Tian, Y., Zhang, J., and Sra, S. (2021). Provably efficient algorithms for multi-objective competitive rl. In International Conference on Machine Learning, pages 12167-12176. PMLR.
[59] Zhang, K., Yang, Z., and Başar, T. (2021a). Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384.
[60] Zhang, R., Ren, Z., and Li, N. (2021b). Gradient play in multi-agent markov stochastic games: Stationary points and convergence. arXiv e-prints, pages arXiv-2106
12

---

Under review as a conference paper at ICLR 2023
A DORIS IN SELF-PLAY SETTING
Here we present the pseudocode of Algorithm 3,
Algorithm 3 DORIS self-play setting
Input: learning rate {n% Ji=i confidence parameter { }
Initialize p E Amn
n. to be uniform over 11, for all [n].
for = 1,..., K do
Collect samples:
Agent i samples μ² from pf.
Run μ² T j and collect Di,; = ai. . s for each agent i.
Update policy distribution:
All agents reveal their policies 14:
V((m)) + OptLSPE( u'ss Fi,
Vyu E H1, e [n].
p. ++1 (m4) x p((())) exp(n: V.(m)),, V/4 E II,, [n].
end for
Output: ß ~ Unif( (nif((IIseEv) M..... [Ieejo M 1).
B RELATED WORKS
In this section we supplement the related literature.
Decentralized learning with an adversarial opponent. There have been few works studying decentralized policy learning in the presence of a possibly adversarial opponent. [7] proposes R-max and is able attain an average game value close to the Nash value in tabular MGs. More recently, [53, 49] improve the regret bounds in tabular cases and [27, 23] extend the results to general function approximation setting. However, these works only compete against the Nash value of the game and are unable to exploit the opponent. A more related paper is [33], which develops provably efficient algorithm that achieves a sublinear regret against the best fixed policy in hindsight. But there results are only limited to the tabular case. Our work extends the results in [33] to the setting with general function approximation, which requires novel technical analysis.
Finding equilibria in self-play Markov games. Our work is closely related to the recent literature on finding equilibria in Markov games via reinforcement learning. Most of the existing works focus two-player zero-sum games and consider centralized algorithms with unknown model dynamics. For example, [53, 3] utilize optimism to tackle the exploration-expoiiatio tradeoff and find Nash equilibria in tabular cases, and [56, 27, 23] extend the results linear and general function approximation setting. Furthermore, under the decentralized setting with well-explored data, [11, 60, 44, 54, 32, 12] utilize independent policy gradient algorithms deal with potential Markov games and two-player zero-sum games. Meanwhile, under the online setting, [4, 35, 26] have designed algorithms named V-learning, which are able to find CCE in multi-agent general-sum games. However, there results are only limited to the tabular case.
Constrained Markov decision process. [15, 13] propose a series of primal-dual algorithms for CMDPs which achieve VK bound on regrets and constraint violations in tabular and linear approxi- mation cases. [34] reduces the constraint violation to Õ(1) by adding slackness to the algorithm and achieves zero violation when strictly safe policy is known; [55] further avoids such requirement with the price of worsened regrets. Nevertheless, these improvements are only discussed in the tabular case.
Approchability for vector-valued Markov decision process. [36] first introduces the approacha- bility task for VMDPs but does not provide an algorithm with polynomial sample complexity. Then (58) proposes a couple of primal-dual algorithms to solve this task and achieves a (c-22) sample complexity in the tabular case. More recently, [37] utilizes reward-free reinforcement learning to
13

---

Under review as a conference paper at ICLR 2023
tackle the problem and studies both the tabular and linear approximation cases, achieving roughly the same sample complexity as [58].
C EXTENSION: CONSTRAINED MARKOV DECISION PROCESS
Although DORIS is designed to solve Markov games, there are quite a lot of other problems which DORTS tackle with small adaptation. In this section investigate important scenario in practice called constrained Markov decision process (CMDP). By converting CMDPs into a maximin problem via Lagrangian multiplier, we will be able view it zero-sum Markov game and apply DORIS readily.
Constrained Markov decision process. Consider the Constrained Markov Decision Process 1 hh=
(CMDP) [13] McMDP = (S,A, ( | [ra) the action space, is the length of each episode, Ph : x A + (S)) the transition function at the h-th step, function at the h-th step. We assume the reward ry also bounded in [o. 1] for simplicity and thus Vinxx H. Then given policy μ. {Pr S + AahNE(M) we can define the value function r.
{Pr
{gt ) h= H) where S is the state space, A
ff
S x A + R+ is the reward function and Jh. S x A + [0, 1| is the utility
and action-value function Or",, with respect the reward function follows:
s)
VA (s) E,, > (s as) 9n _) Of (s, E, E ri(si, oi) Sh
The value function VK and action-value function Qÿ with respect to the utility function g can be defined similarly. Another related concept is the state-action visitation distribution, which can be defined as
9.h
(s, a) = Pr, (ss, aa) = a)},
where Pr,, denotes the distribution of the trajectory induced by executing policy μ in MCMDP.
Learning objective. In CMDPs, the player aims to solve a constrained problem where the objective function is the expected total rewards and the constraint is on the expected total utilities:
Problem 1: Optimization problem of CMDP
max Va (s1) subject to Vgl (s1) 2 b,
(8)
HEll
where b e (0, to avoid triviality.
Denote the optimal policy for (8) by HCMDP- then the regret be defined the performance gap with respect to #CMDP=
Regret(K) K)
Σ ViHoome (s1) V.4((ss)) (s1)).
(9)
However, since utility information is only revealed after policy is decided, it is impossible for each policy to satisfy the constraints. Therefore, like [13], we allow each policy violate the constraint in each episode and focus minimizing total constraint violations over K episodes:
Violation K)
Σ
b Vul (=i(
(10)
Achieving sublinear violations in (10) implies that if we sample policy uniformly from {,t), its constraint violation can be arbitrarily small given large enough K. Therefore, if an algorithm can achieve sublinear regret in (9) and sublinear violations in (10) at the same time, this algorithm will be able to find good approximate policy to HCMDP-
14

---

Under review as a conference paper at ICLR 2023
C.I ALGORITHM: DORIS-C
To solve Problem with DORIS, we first need to convert it into a Markov game. A natural idea is to apply the Lagrangian multiplier Y E R+ Problem which brings about the equivalent maximin problem below:
max min LCMDP( Y) V,A ($1) (VV)) (51) b). eet Y20
(11)
Although Problem is non-concave in J., there have been works indicating that strong duality still holds for Problem when the policy class is described by good parametrization [40]. Therefore, here we assume strong duality holds and it is straightforward to generalize our analysis to the case where there exists a duality gap:
Assumption (Strong duality). Assume strong duality holds for Problem 1, i.e.,
max min LCMDP Y) min max LCMDP(H,Y) Y20 pell
(12)
H Y20
Remark 6. One example case where strong duality (12) holds is when policy class 11 satisfies global realizability. Let Uigoo denote the solution to A miny20 CCMDP(μ, Y). [13] shows that maxpe((A (a))e(A))) miny LCMDP(U, Y) satisfies strong duality, and thus as long as Piloo E II, Problem I also has strong duality.
Further, let D(Y) == max LCMDP (,, Y) denote the dual function and suppose the optimal dual variable is Y* arg miny2o 20 D(Y). To ensure Y* is bounded, we need to assume the standard Slater's Condition holds:
Assumption 7. There exists Asta > 0 and ğí E Il such that V (81) 2 b Asta-
Then the following lemma shows that Assumption 7 impliis bounded optimal dual variable, whose proof is deferred to Appendix L.I:
Lemma 1. Suppose Assumption 6,7 hold, then we have 0 S Y S HH/Ai Acta-
Now we are ready to adapt DORTS into a primal-dual algorithm to solve Problem 1. Notice that the maximin problem (11) can be viewed as a zero-sum Markov game where the player's policy is μ and the reward function for the player is r4 (s, a) Y gh (s, a). The opponent's action is Y E IR+ which remains the same throughout a single episode. With this formulation, we can simply run DORIS on the player, assuming the player is given function classes {F" 9"} and (F) } to approximate Q and Q" respectively. In the meanwhile, we run online projected gradient descent the opponent so that its action Y can capture the total violation so far.
This new algorithm called DORIS CC and shown in Algorithm 4. consists of the three steps below in each iteration. For the policy evaluation task in the second step, DORIS-C C runs single-agent version of OptLSPE to estimate V (#1) and 1/2 (81) separately, which essential for DORIS-C deal with the infinity of the opponent's policy class, i.c., Rt.
The player plays a policy 1e sampled from its hyperpolicy p' and collects trajectory.
The player runs OptLSPE-C to obtain optimistic value function estimations V (H),,, V g (H) for all
f E and updates the hyperpolicy using Hedge with the rewards being V²(1)) + Y (n). The construction rule for Bp (1) is still based on relaxed least-squares policy evaluation:
BD( + (s E F LD(sn, Jh+1, 1) & inf Lo(gh; Jb+1, + 3, E [H]} (13)
geg
where LD is the empirical Bellman residuals on D:
Lo(En, (h)
Σ
(n(Sh, an) (1+1(8411,11)3
The dual variable is updated using online projected gradient descent.
15

---

Under review as a conference paper at ICLR 2023
Algorithm 4 DORIS-C
Input: learning rate confidence parameter 3r, Pg. projection length X. Initialize p² R! to be uniform over II, Y1 t- 0.
for f 1,........ do
Collect samples:
The player samples jl from p'.
Run μ² and collect D {sf di ri. S 1.Dy ai. 11144)))
Update policy distribution:
(n) < OptISPE-C(1, Di 111-1: F", " ;r), ET. Vpe II. Vp ET.
(H) t Opt 11 F9, ,9,
(n) x p'()) exp(1) (V (1) + V.V (1))),
Update dual variable:
Y2+1 < xY, + arb - ( (1¹))).
end for
Algorithm 5 OptLSPE-C(u, D,
Construct (p) based on D via (13). Select V +- mmxxeeBpla) (s1.
return V.
C.2
THEORETICAL GUARANTEES
Next we provide the regret and constraint violation bounds for DORIS C. Here we also consider the case where II is finite, i.e., Assumption is true. However, we can see that here the opponent adaptive and its policy class is infinite, suggesting that Assumption 5 is violated. Fortunately, since the opponent only affects the reward function, the player can simply first estimate V (81) and V (s1) respectively and then use their weighted sum to approximate the target value function V; (s1) + V (s1). (s1). In this way. DORIS-C circumvents introducing a union bound on and thus can work even when the number of possible values for Y is infinite.
We also need to introduce the realizability and general completeness assumptions on the function classes as before:
Assumption (Realizability and generalized completeness CMDP), Assume that for any h E
[H] μ II, fh+1 E Fitt f E F9, we have
O E F
E FR. Th E G. Sh E 9h.
(14)
Here The is the Bellman operator at step with respect to r:
(Th" (nt1)(s, = (s, + Pa (s', ut)
where fn+1 (s', Ea' (ss) [fff+11155 (s', d²)] Th is defined similarly. We can see that (14) simply says that all the action value functions with respect to (g) belong to F" (F9) and g" (G9) contains all the results of applying Bellman operator with respect to (g) to the functions in F (F*).
In addition, as simplified case of Definition 6, BEE dimension for single-agent setting can be defined as follows:
Definition 7. The single-agent e-Bellman Evaluation Eluder dimension of function class F on distribution family Q with respect to the policy class II and the reward function r is defined as follows:
dimBEe F,,, (F, Q) = max dimpe((I ( -,, 2h,
he[H]
where (I- (I-T!l.)) = (fn- Thh f
We also let dimBer(F r) denote min Sainddimner(A e, II, Q*), dimmEr (F, I, Q²) as before. (imBer(FFe g, Q) and dimBEr e, II, g) are defined similarly but with respect to the utility function g.
16

---

Under review as a conference paper at ICLR 2023
Now can present Theorem 3 which shows that DORIS-C is capable of achieving sublinear regret and constraint violation for Problem 1. We also use the following notations to simplify writing:
dBEE dimBEE (F), VV/K,,I,r) r), Neov.r Nrrug- Nruug-HH/KKKR
dBEE,, == dimBER (F V 1/K,11,g) Noov, := (
Theorem 3. Under Assumption 6,7,1,8, there exists absolute constant such that for any d E (0. 1].
K E N, if we choose B3 cH2 log(Neave [T]/5), Bg cH22 log(Neov / /5), 1/vK, 22/2H/o Vata and 1l = Vlog [ H)2 in DORIS-C, then with probability least 8.
we have:
Regret(K) 50 =0((p++
11a
K dAEER log (Noov, (T1/0)
(15)
Asta
Violation K) S 50
H
v KeEEE
(16)
Asla
where
BEE = max dBBER log (N)ov.rlII/0)) dBEE, log (Noov.g [1|/5)
The bounds in (15) and (16) show that both the regret and constraint violation of DORIS-C scale with VK. This implies that for any >> 0, if fi is sampled uniformly from {u*) will be an near-optimal policy with high probability in the sense that Tt=1 and K 2 O(1/e2), jr
VP r.1 (s)) Viltouur (s)) -,
V (s)) 2
In addition, compared to the results in Theorem and Theorem (15) and (16) have an term scaling with 1/ 1/Dala- This is because DORIS-C is primal-dual algorithm and Aata characterizes the regularity of this constrained optimization problem.
The proof of the regret bound is similar to Theorem 1 and Theorem by viewing V V7 (81) (81)+ YVL (81) as the target value function and decomposing the regret into cumulative estimation error and online learning error. To bound the constraint violation, we need to utilize the strong duality and the property of online projected gradient descent. See Appendix L for more details.
g.1
Comparison with existing algorithms. There has been a line of works studying the exploration and exploitation CMDPs. [15, 13] propose a series of algorithms which can achieve /K bound on regrets and constraint violations. However, they focus on tabular cases or linear function ap- proximation and do not consider policy classes while DORIS-C can deal with nonlinear function approximation and policy classes. As an interesting follow-up, [34] reduces the constraint violation to ((1) by adding slackness to the algorithm and achieves zero violation when strictly safe policy is known; [55] further avoids such requirement with the price of worsened regrets. However, these improvements are all limited in tabular cases and we leave the consideration of their general function approximation counterpart to future works.
D EXTENSION: VECTOR- MARKOV DECISION PROCESS
Another setting where DORIS can play a role is the approachability task for vector-valued Markov decision process (VMDP) [36, 58, 37J. Similar to CMDP, we convert it into zero-sum Markov game by Fenchel's duality and then adapt DORIS properly to solve it.
Vector-valued Markov decision process. Consider the Vector-valued Markov decision process (VMDP) [58] MVMDE = (S, A, (P H) where r (rr S x A - [0. ]] collection of d-dimensional reward functions and the rest of the components are defined the same as in Section C. Then given a policy μ E 11, we can define the corresponding d-dimensional value function V S [0, H1) and action-value function Q S x - [0, H| follows:
H
H
(s) = E
(1 a1) a))
8h =8
Q" () = E,
Σ 1=h
r (1 ai) ( 8h = 8, a, =0
17

---

Under review as a conference paper at ICLR 2023
Learning objective. In this paper study the approachability task [36] in VMDP where the player needs to learn policy whose expected cumulative reward vector lies convex target set We consider general agnostic version [58, 37] where do not assume the existence of such policies and the player learns to minimize the Euclidean distance between expected reward and the target set C:
Problem 2: Approachability for VMDP
min dist (V)),,
pell
where dist(x, C) is the Euclidean distance between point æ and set C.
The approachability for VMDP is natural objective in multi-task reinforcement learning where each dimension of the reward can be regarded as task. It important in many practical domains such as robotics, autonomous vehicles and recommendation systems [58]. Therefore, finding the optimal policy for Problem 2 efficiently is of great significance in modern reinforcement learning.
D.1 ALGORITHM: DORIS-V
To deal with Probelm 2, we first convert Problem 2 into a Markov game as we have done in Appendix C. By Fenchel's duality the distance function, we know Problem is equivalent to the following minimax problem:
min max LVMDP (n, 0) (0, Vir max =
(0, 2),
pell OEB(1)
where B(r) is the d-dimensional Euclidean ball of radius centered the origin. Regarding μ the player's policy and 0 as the opponent, we can again view this minimax problem as a Markov game where the reward function for the player is (0, TT a)). Consider the general function approximation case where the player is given function classes F ( G (g h.j=
approximate 0% (F)) and GJ are the j-th dimension of Fr and Gr)), we can run DORIS for the player while the opponent will update via online projected gradient ascent just like DORIS-C.
( H.d
We call this new algorithm DORTS-V, which is shown in Algorithm 6 and also consists of three steps in each iteration. For the policy evaluation task here, we apply Opt OPtLSPEVV v and construct confidence set for each dimension of the function class separately, and let the final confidence set be their intersection. Therefore the construction rule for (p( is given as:
Br(u) - EF Los 11) S inf LD (or Sha1: + 3,4h E [M].j E (d]) (17)
9Eg
where for any E [d] and h E [H],
Lops (Sh (h
Σ (sh.0n SR41))D
(s),
and ri is the j-the dimension of In addition, since here want to minimize the distance, OptLSPE-V will output a pessimistic estimation the target value function instead of an optimistic one.
The player plays a policy μt sampled from its hyperpolicy p' and collects a trajectory.
The player runs OptLSPE-V obtain pessimistic value function estimations (0', v2'(n) for all I E II and updates the hyperpolicy using Hedge.
The dual variable updated using online projected gradient ascent.
D.2 THEORETICAL GUARANTEES
We still consider finite policy class II here. Notice that in the fictitious MG of VMDP, the opponent's policy class is also infinite, i.e., B(1). However, since the player only needs to estimate Vi((8)), which is independent of 0, DORTS-DR also circumvent the union bound 0 just like DORTS-C.
18

---

Under review as a conference paper at ICLR 2023
Algorithm 6 DORIS-V
Input: learning rate 7) a, confidence parameter B. Initialize p' E R to be uniform over II, 01 t- 0. fort 1, do
Collect samples:
The learner samples n² from p²
Run n² and collect D, = { di ri , HH+...
Update policy distribution:
V (p) + OptLSPE-V(u, (11 F,9,3,3 Vu el. 0),, E
(1) x p'(n)
Update dual variable:
0.-1- + Proj (02 + (V' (14) - arg m (0,, x))).
end for
Output: uniformly sampled from p²,'... .... k
Algorithm 7 OptLSPE-V(H, D, 3,0
Construct (p( based on D via (17).
Select V < fi( /), where f arg min r (81,
return V.
In addition, we need to introduce the realizability and generalized completeness assumptions in this specific setting, which is simply a vectorized version as before: Assumption (Realizability and generalized completeness in VMDP), Assume that for any h E [M].] E [4], f E 11, fh+1 E Fh+1, we have Q E Fn.s This fhrt E 9% where Qh is the j-the dimension of Q and Thts is the j-th dimensional Bellman operator at step h defined in (18).
Here T detined as:
(Th (, := E.g.
(18)
In addition, the BEE dimension for VMDP can be defined the maximum BEE dimension among all d dimensions:
Definition 8. The d-dimensional e-Bellman Evaluation Eluder dimension of function class F on distribution family Q with respect to the policy class II is defined as follows:
dimBEE(F, 11, 2)
max )E(A)
dimpe((I T1 ) 2n.e),
where (I -T!lD))) (8h THes S
FE
We also use dimmer (F, e, II) to denote min min (dimmnd(FFFFF... e, II, 2+), dimmer 24) be- fore.
The next theorem shows that DORIS-V is able find near optimal policy for Problem 2 with polynomial samples, where we use the following notations to simplify writing:
dBEE == dimBER (F, V)/ NNov, max
NaxxN (H/K)KH.
jEld
Theorem 4. Under Assumption 1,9, there exists an absolute constant e. such that for any 5 E (0, 1).
K N, we choose 2H2 log(Nwwe, [[d/)), a4 2/ (H-ddt),, and nj Vlog II [1/(KH2))
in DORIS-V, then with probability at least 6, we have:
dist(V (s), < min dist dist((( ( (a / /BBE, log (N (ll//)//) (19)
o
wen
The bound in (19) shows that for any 0, K > Oddee), f will be an near-optimal policy with high probability, Compared to the results in Theorem I and Theorem 2, there is an additional term d. This is because the reward is d-dimensional and are indeed evaluating d scalar value functions in OptLSPE-V.
The proof is similar to that of Theorem 3 and utilizes the fact that both μ and 0 are updated via no-regret online learning algorithms (Hedge for and online projected gradient ascent for 0). See Appendix M for more details.
19

---

Under review as a conference paper at ICLR 2023
Paper
Setting Tabular
Decentralized?
Baseline
Optimism Local, w.r.t. (s), wh,
Tian et al. [49]
Yes
Nash Value
Best policy
Local, w.r.t. Vh, 8, a,
Liu et [33]
Tabular
Yes
in hindsight
Q (s, a. b)
Jin et al. [27]
General FA
Yes
Nash value
Global, w.r.t. ViT(
Huang et [23]
Yes Best policy in hindsight
Global, w.r.t. Vikia ($1)
This work
General FA
Table I: Comparison with related works on decentralized learning with an adversarial opponent. Here
that Tian et al. [49] focuses on tabular cases and can only compete agasint the Nash value of the game. Liu et al. [33] also works on tabular cases but the baseline is much stronger, i.e., the best policy in hindsight. Jin et al. [27], Huang et al. [23] are able to deal with general function approximation, but they can work considers general function approximation and the baseline is the strongest (the same as Liu et al. [33]).
General FA means general function approximation setting. From the table we
only compete against Nash value. In contrast,
Number of players
Paper
Setting
Decentralized?
Optimism
Jin al. [26]
Local, w.r.t. vh, max, VR..D (s)
Tabular
Yes
2 2
Mao al. [35]
Jin et al. [27]
General FA
No
Global, w.r.t. V (81)
Huang et al. [23]
This work
General FA
Yes
> 2 Global, w.r.t Vuu (s1)
Table 2: Comparison with related works on finding equilibria in self-play Markov games. Here General FA means general function approximation setting. We can see that Jin et al. [26]. Mao et al. [35] studies tabular cases. Their algorithms are decentralized and can still work when the number of players is larger than 2. Jin et al. [27]. Huang et al. [23] works on general function approximation setting but their algorithms are centralized and limited to two-player zero-sum games. In comparison, our work can handle multi-agent (2 2 players) general-sum games with general function approximation and the algorithm is decentralized.
Comparison with existing algorithms. [58] has also proposed algorithms for approachability tasks tabular cases and achieve the same sub-optimality gap with respect and K as Theorem [37] studies the tabular and linear approximation cases, achieving VK regret as well. Their sample complexity does not scale with d because they have normalized the reward vector to lie in (B() in tabular cases and B / ddin) in dim-dnimnio linear VMDPs. Compared to the above works, DORIS-2 is able to tackle the general cases with nonlinear function approximation and policy classes while retaining the sample efficiency.
E DISCUSSION
E. COMPARISON WITH CLOSELY-RELATED RELATED WORKS
In this section we provide a more detailed comparison between DORIS and some closely-related works in this section. First would like summarize the comparison with decentralized learning literature and self-play literature in Table and 2. Next we will clarify the novelty of our work given some relarted works.
Novelty given Liu et al. [33]. The idea of maintaining a hyperpolicy and utilizing Hedge to update it in DORIS is inspired from OPMD proposed in Liu et al. [33]. However, the policy evaluation algorithm in Liu et al. [33] can only work in tabular cases and our novelty lies in the new optimism and policy evaluation step (Algorithm 2) specially designed for the policy revealing setting. Note that the extension to the setting of general function approximation is not trivial. Combining existing techniques on reinforcement learning with general function approxiamtion (for example, Bellman Eluder dimension in Jin et al. [25]) with Liu et al. [33] does not lead to our work because the optimism in DORTS S is (i) global (in the sense that optimism only true for 81, which differs from
20

---

Under review as a conference paper at ICLR 2023
Liu et al. (33]) and (ii) policy-pair specific (that is, confidence set is only optimistic with respect to Vil.a (s1), which differs from Jin et al. [25]).
More specifically, Liu et al. [33] attains optimism via adding bonus term | for each step h and state-action pair (s, a, b) in value iteration as follows:
Qha (s, b) P( V7 (6') + ((,,,,b) + 8,
Vil (s) (a) (s), (s) 10) 12 (s,a,
This guarantees that V (s, a, b) is optimistic with respect to the true value function Vi (s, a, 6) for each h, 8, a, b. However, DORIS picks the most optimistic estimation from the constructed confidence set directly:
VR
f(1,
max SEB(y,ut)
This can only guarantee that Va."" is optimistic with respect to Via. ($1). Thus bounding the regret will be harder in our case with only global optimism.
In addition, although Jin et al. [25] also uses global optimism, it is optimistic with respect to the fixed optimal value function V/2 (s)) and only needs to construct one confidence set it. Nevertheless, to tackle the non-stationary optimal policy in the decentralized setting which keeps changing across
episodes due to the adversarial opponent, DORTS needs to construct a confidence set of Vi ($1) for
each policy μ in the policy class and the estimation Va.e* is only optimistic with respect to Vi (s1)
for each respectively. Therefore, the analysis techniques in Jin et al. [25] cannot be applied directly here. We need to decompose the regret in a different way and propose a new complexity measure (i.e., BEE dimension) to bound the regret.
Novelty given Jin et al. [27], Huang et al. [23]. Jin et al. [23], Huang et al. [23] also design algorithms and utilize analysis techniques based Bellman-eluder-tyye complexity (i.e., multi-agent BE dimension [27, 23]) in Markov games. Here we want to clarify that although the BEE dimension is also inspired from Bellman Eluder dimension proposed in Jin al. [25], DORIS S is very different from Jin et al. [27], Huang et al. [23] in terms of confidence set construction and optimism, which makes their analysis techniques not applicable here either.
Jin et al. [27], Huang et al. [23] consider zero-sum Markov games in the centralized setting with gen- eral function approximation. The algorithms in these works are based on (i) constructing confidence regions of the optimal value function (i.e., Nash value function in zero-sum games) or model and (ii) solving the Nash equilibrium with respect to the optimistic function/model. As result, their algorithms can be regarded as running optimistic greedy policies in games and the estimated value functions are always optimistic estimates of the optimal value function V (s1) of the underlying game.
In contrast, in the decentralized setting, one unique challenge faced by DORIS is that the optimal policy is indeed changing across the episodes because we cannot control the opponent and the opponent be adversarially adjusting its own policy. Therefore, there does not exist such fixed optimal value function that we can run optimism with respect to. More importantly, from the view of the single agent, the environment is adversarially changing due to the opponent. Such nonstationarity does not appear in these works. To deal with this challenge, DORIS is based on (i) constructing the confidence region for policy evaluation problems, (ii) running mirror descent over the space of policies. As a result, DORIS is more like a decentralized policy optimization algorithm and the value functions maintained by the DORIS are only optimistic with respect to the value functions associated with the current policy pair (H4, v*), which changes at each iteration.
More importantly, such different version of optimism leads to a different regret decomposi- tion. Specificallyy, (22), we show that the regret is upper bounded by the policy evaluation error Σx (V'((()) VT" (s1)) and online learning error induced Et "V"((""")) - V*(x") by mirror descent. Bounding the evaluation error "K ing optimism in policy evaluation has not been considered in Jin et al. [27], Huang et al.
Vi" (s1) incurred by achiev-
[23]. Multi-agent BE dimension [27, 23] cannot be applied here either because it measures
21

---

Under review as a conference paper at ICLR 2023
the Bellman residuals fü (s, 0) r as miny f1+41s, (1, and can only help bound 1 (V") - min, V/ (s))) when the policy v² played by the opponent a pessimistic best response of ju", In our case u¹ arbitrary (typically not the best response of (z') and the value we want bound is also different, therefore multi-agent BE dimension is not applicable and we have to propose BEE dimension to evaluate the complexity of policy evaluation tasks with general function approximation. Along with the measure, have also identified common function classes with low BEE dimension in the paper to illustrate the capacity of BEE dimension.
E.2 LOWER BOUND IN LIU BT AL. [33]
Here present a lower bound from Liu et al. [33]:
Theorem (Liu et [33, Theorem 4)). There exists Markov game with S, A O(H) and an opponent who chooses policy uniformly at random from an unknown set of H Markov policies in each episode, such that when the opponent's 's policy is not revealed, the regret for competing with the best fixed Markov policy in hindsight is Mminn 2/ HHH).
The above lower bound shows that if the opponent's policy is not revealed, even when the opponent only plays a finite number of Markov policies, the exponential regret lower bound for competing with the best Markov policy hindsight is inevitable, which validates the necessity of policy revealing condition.
E.3 COMPUTATIONAL COMPLEXITY DORIS
There are mainly two steps in DORIS that require computation, optimistic policy evaluation via OptLSPE and hyperpolicy update via Hedge. Assuming the policy class is finite facilitates the second step. but even with finite policy class, OptLSPE is still computationally inefficient. This is due to the global optimism step in OptLSPE, i... constructing the confidence set (Equation (3)) and finding the most optimistic estimation. This is common issue of algorithms with general function approximation even in single-agent MDPs. For example, the global optimism step of the algorithms in [24, 25, 14, 23, 27] are all computationally inefficient and hard implement. However, if we only consider linear MGs, computationally efficient algorithms are possible since we can use local optimism and implement OpE by an analog of LSVI-UCB [28], which is computationally efficient. In addition. if there is a computationally efficient solver for optimistic policy evaluation with general function approximation in single-agent MDPs, we believe that we can also utilize here since the confidence set update rule (Equation (3)) is similar to single-agent MDPs. That said, in this work we mainly focus on the statistical complexity of learning the Markov game and thus computationally efficient algorithms are left as future works.
F PROOFS OF PROPOSITION
From the completeness assumption, we know that there exists 9n. E F, such that 9n. = The fhtl which implies that
fn Thilfh4 fh+1 E Fr F.
In other words. (I - T TI,II' }F C Fr Fr. Therefore, from the definition of dimBee (F,e
11, II') we have
dimBER (F,,, < dimpge (F, F,6 II,,, Ø²) max dimpe - ( )FF hE(H)
}F, c) max dimpe ((Fr Fi), 2h c) max dimg dimg)Fn,e),, ke[H]
be(#]
where the last step comes from the definition of dimg and Q3 is the dirac distribution family. This concludes our proof.
22

---

Under review as a conference paper at ICLR 2023
G EXAMPLES FOR REALIZABILITY, GENERALIZED COMPLETENESS AND COVERING NUMBER
In this section we illustrate practical examples where realizability and generalized completeness hold and the covering number is upper bounded at the same time. In specific, we will consider tabular MGs, linear MGs and kernel MGs.
G.1 TABULAR MGS
For tabular MGs, we let Fn = :fff:S Ax [0, mmax]] and Gr. Fr, for all [H]. Then it is obvious that Q Fn and TV." fn+1 9n for any f E F, [H] μ. v, which implies that realizability and generalized completeness are satisfied. In addition, notice that in this case we have
log NY,, (E) log No, (E) - | log(Vmaae/
This suggests that the size of FF and G is also not too large.
G.2 LINEAR MGS
In this subsection we consider linear MGs. Here we generalize the definition of linear MDPs in classic MDPs [28] Markov games:
Definition (Linear MGs). We say an MG is linear of dimension d for each h [H] there exists feature mapping db S x A x + IRd and unknown signed measures unn (wh 1 over and an unknown vector On E IRd such that Pr(-11, a, b) = dr (s, a, b) 1/ (-) and Th (1(8,00 a, = 65(5, a, b) for all (s, a, b) E S A.B.
Without loss of generality, we assume || (s, a, b)ll S 1 for all E S,a E A,b E B and [ S Vd, 0, < for all h. Let Fr = Sr = (Φr()) Tw/w E [R, s I Tn(.)) H - 1+.
Realizability. We have for any μ. V.
Q (s, (,, a, Es P( V (x))
(dn a, b). + (on(s, a)) / VH ( (d))))((s))
a, b), a,, (sn a, b), wxx")
+ Is VirT" (s')dennss)
where w = 0n + J's " (sn' (s') and thus ||w S (H 1)vd. Therefore, Q E Fr. which means that realizability holds.
Generalized completeness. For any fat1 E F1t1, we have
They fnt1(s, rn(s, a, b) Eas (n al b), ())
1 Intils', 1 (,
Since [| 1loo < H h, we have |10, + Jg I u, v)dvn(ss)) < (H h + 1)vd, which indicates T fh+1 E Gn and thus generalized completeness satisfied.
Covering number. First notice that from the literature [51], the covering number of norm ball can be bounded as log 1+ (c) S ( Therefore, there exists W c B(H h + 1)vd) where log [ < d (3H such that for any E B(H 1)vd), there exists w' W satisfying ||w/ w|ll I Now let F (Tu(.)Tun Twww W). For any
23

---

Under review as a conference paper at ICLR 2023
fn Fh, suppose f.) dn(()) wn. Then we know there exists f%(() (n(:) Fh where ll,/ Wf, ll S which implies
[s [, a, b) S (1, a, a,blllll/.... -wall Se.
Therefore log,Nr, (c) S log F log [W] - dlog(3H
G.3 KERNEL MGS
In this subsection we show that kernel MGs also satisfy realizability and generalized completeness naturally. In addition, when kernel MG has a bounded effective dimension, its covering number will also be bounded. First generalize the definition of kernel MDPs [25] to MGs follows.
Definition 10 (Kernel MGs). In a kernel MDP, for each step h E [H], there exist feature mapping @h x
- H and th S - H where H is a separable Hilbert space such that Pa a. b) = (dn(s, b), th (s))
all s E S,a a E A, E B, E S. Besides, the reward
function os linear in ó, i.e. Th(8, a, = (ón,s,, a, b), On) for some On E H. Moreover, kernel
MG satisfies the following regularization conditions:
10x1læ S 1, 1,, a, b) S for all E E E AbE,
+I 1EEees (s))x S for all function 8 [0, 1], hl [H].
Remark 7. It can be observed that tabular and linear MGs are special cases of kernel MGs. Therefore, the following discussion applies to tabular and linear MGs as well.
Then we let Fr Gn {-) w/w e Bx(H h + 1)} where (x(r) ball with radius r in H. Following the same arguments in linear MGs, we can validate that realizability and generalized completeness are satisfied in kernel MGs.
Covering number. Before bounding the covering number of Fi. we need introduce new measure evaluate the complexity of a Hilbert space since H. might be infinite dimensional. Here we use the effective dimension [14, 25], which is defined as follows:
Definition (e-effective dimension of a set). The e-effective dimension of a set is the minimum integer dest (X, e) = n such that
log det I 1
Σ x
12
Se-
sup
7
Remark 8. When X is finite dimensional, suppose its dimension is d. Then its effective dimension can be upper bounded by Od (1 R² /E)) where R is the norm bound of X [14]. In addition. even when X is infinite dimensional, if the eigenspectrun of the covariance matrices concentrates in a low-dimension subspace, the effective dimension of X can still be small [48].
We call kernel MG is of effective dimension d(c)) if dest (A S d(c) for all h and where X, (or (s, a, b) (s, a, b) E A x B). Then the following proposition shows that the covering number of Fn is upper bounded by the effective dimension of the kernel MG:
Proposition 2. If the kernel MG has effective dimension d(e), then
log,Nr, s (d((c/2H) log(1 + Hd(c/2H)/e)).
n. Then by the definition of Eluder dimension, there exists sequence ) such that for any w1. W2 E (H-h+1)) ó E Xr, if if ( ww))) < 22, then (60, w11 w2)l < c. Therefore, the covering number of kernel MGs can be reduced to covering the projection of B (H - h + 1) onto the space spanned by {Ø: } 1. whose dimension is at most From the literature [51], the covering number of such space is log (1 nH /e)), which implies
(Fr,e) Proof. Suppose dimg(Fr,
log F, (e) S On + nlH/e)).
Finally, by the proof of Proposition 3, we know n S die A(//HH), which concludes the proof.
24

---

Under review as a conference paper at ICLR 2023
H EXAMPLES FOR BEE DIMENSION
In this section we will show that kernel MGs (including tabular MGs and linear MGs) and generalized linear complete models have low BEE dimensions.
H.1 KERNEL MGS
Consider the kernel MG defined in Definition 10 and Fn = (T) have the following proposition showing that the BEE dimension of kernel MG is upper bounded by its effective dimension (Definition 11):
w/w E Bx - + 1)}, then
Proposition 3. If the kernel MG has effective dimension d(e). then for any policy classes II and II', we have dBEE (F, 11,1I1) S d(e/2H).
Proof. First in Appendix G we have showed that J satisfies completeness. By Proposition 1, we have (FFR((F, e, II, IT') [а dimm e). Therefore we only need to bound dimm((Fn. t) for each h E [H.. Suppose dimg(Fn; = = d(e/2Hl Then by the definition of Eluder dimension, there exists a sequence 01, 6R and {w1,}]==
(s, a, E S x A B}, w1,s 22,1 E Bx (1l - 1=1 (22,) where Φ; E Xr. = {or a, a) 1) for all such that for any E [A]]
E (10i, W1,1 - - (e')²
(20)
16 w1,t w2,1)1 2 t', 2²
(21)
where è' 2 6. Let E, denote Σ 2:0
+ TH I. Then we have for any E [k]
- 2 s (E)) +
On the other hand, by Seuuch-SShhwarzz inequality know
| |wi. - W2 2 (0r, w1,t - w2,i) 2 '.
This implies for all E [k]
V (e)p
22
Therefore, applying elliptical potential lemma (c.g., Lemma 5.6 and Lemma F.3 in [14]), have for any e [k]
(I
4H²
010 = Σ log(1 + 110.113--11 2 t. tloog 2
log det
However, by the definition of effective dimension, know when n dott (2t 2
log det (I+ 4H² 2 Σ 0:0.
sup
< -1
This is contradiction since I d(c/2H) < k and log 3 d(H/2H) for all E [H], which implies
2 > el_ Therefore we have dimg(Fn, c) S
dBEe (F,, S d(e/2H).
This concludes our proof.
Tabular MGs. Tabular MGs special of kernel MGs where the feature vectors B| one-hot vectors. From the standard elliptical potential lemma, we know
d(c) ([[S]|AA|BB)) for tabular MDPs, suggesting their BEE dimension is also upper bounded (B))
25

---

Under review as a conference paper at ICLR 2023
Linear MGs. When the feature vectors d-dimensional, recover linear MGs. Similarly, by the standard elliptical potential lemma, we have the BEE dimension of linear MGs is upper bounded (dd)
H.2 GENERALIZED LINEAR COMPLETE MODELS
An important variant of linear MDPs is the generalized linear complete models proposed by [52]. Here we also generalize it into Markov games:
Definition 12 (Generalized linear complete models). In d-dimensional generalized linear complete
models, for each step [H], there exists a feature mapping 0% S x A B IR and a link
function such that:
for the generalized linear function class Fn (-((d(()) W] where W C R.,, realizability and completeness are both satisfied;
the link function is strictly monotone, i.e., there exist 0 < < c2 < oc such that a' E [c1, c2).
Φn, w satisfy the regularization conditions: [10%,,, a, b]ll < R ||l||| < for all 8, a, b, h where a constant.
When the link function is (2) = I, the generalized linear complete models reduce to the linear complete models, which contain instances such as linear MGs and LQRs. The following proposition shows that generalized linear complete models also have low BEE dimensions:
Proposition 4. If a generalized linear complete model has dimension d, then for any policy classes and IT, its BEE dimension can be bounded as follows:
dREF(FF ,e II' S (dde//c))
Proof. The proof is similar Proposition except (20) and (21) become
Σ Eillon Wi, w2,))) < (a w1.)) وá. w2.))) s (e')2,
o2, Wi,t w2,1)l 2 ( w1.1) ( w2,1)l 2
Then repeat the arguments the proof of Proposition E [H]. Since F satisfies completeness, we can use Proposition and obtain
have dimp((F,e Ö(de//)) for all
(F,r((F,,,I,I'))) < Odde/
I PROOF OF THEOREM I AND THEOREM 2
In this section present the proof for Theorem and Theorem 2. We first consider the oblivious setting. Let μ² = arg ma E Vexx* (s1) and we can decompose the regret into the following terms:
K
K
K
K
max PEll
Vi
(81)
Σ [m/
Vi (81)
=
Σ
va xv²
(81)
Σ
V'(rn)
(1)
K
(4*)
Σ
V
+
p
V
(u')
1=1
1=1
1=1
1=1
(2)
(3)
K
K
V (4²)
Σ
V (s1)
(22)
1=1
(4)
26

---

Under review as a conference paper at ICLR 2023
Our proof bounds these terms separately and mainly consists of three steps:
Prove V (1) an optimistic estimation of Viux" ($1) for all t E [K] and ja E II, which implies that term (1) I O.
Bound term (4), the cumulative estimation error >t=1 the newly proposed complexity measure BEE dimension to bridge the cumulative estimation error and the empirical Bellman residuals occurred in OptLSPE.
K V (u²)
VT (s1). In this step utilize
Bound term (2) using the existing results of online learning error induced by Hedge and bound (3) by noticing that it martingale difference sequence.
I.1 STEP 1: PROVE OPTIMISM
First we can show that the constructed set Bp...-, (p, v²) is not vacuous in the sense that the true action-value function Qui'' belongs to it with high probability
Lemma 2.
With probability at least - 6/4 4, we have for all E [K], a E II, Qua'' E B v.).
Proof. See Appendix J.1.
Then since ('()) max f(1 M, 2²), we know for all t [K] and II,
V'(H) 2 Qui'' (81, (82,H1,22) = vuxu (81).
In partieular, we have for all t [K],
v' (a*) vuixxe' xv (s1).
(23)
1.2 STEP 2: BOUND ESTIMATION ERROR
Next we need show the estimation error (4') (s1) small. Let ftu
arg max (1,2)) f(11, nb, v²). Then using standard concentration inequalities, can have the following lemma which says that empirical Bellman residuals are indeed close to true residuals with high probability. Recall that here n= = 1st x²
Lemma 3. With probability at least 8/4, we have for all t E [K]. h E [H] and μ E II,
(a)
Expt
(Fh an bn) - (Th ct-t 5h+11) (sh, an. (sh.
an.
bn)) S 0(3),
(24)
(b)
fh ohi b/) (THi"" s4tt)) ai b9)) 50())
(25)
Proof. See Appendix J.2.
Besides, using performance difference lemma we can easily bridge V'(2²) Va (s1) with Bellman residuals, whose proof is deferred to Appendix J.3:
Lemma 4, For any E [K], we have
H
V(4 - (T'((1)
(s1) = --E, Ex [Ath"" - -Tpi '' pha (sn.
Therefore, from Lemma 4 we can obtain
K
K
Σ ('(n') - VT (s1) = ΣΣ E [[ttin -TH' -.p Mon an, bw)].
(26)
27

---

Under review as a conference paper at ICLR 2023
Notice that (26) we need to bound the Bellman residuals of ft weighted by policy T'. However, Lemma 3, can only bound the Bellman residuals weighted by n Fortunately, we can utilize the inherent low BEE dimension to bridge these two values with the help of the following technical lemma:
Lemma 5 ([25)). Given a function class o defined on X' with Φ(x) I C for all (0, E + x X, and a family of probability measures Q over X. Suppose sequence {6rJi=1 1K C and {pr)e= C satisfy that for all E [K], Σi=1 ( (x)))) S 3. Then for all L. E [K] and w > 0.
(Vvimmpe pa [ox|l S <0(v //imp 2 wt + minft, dimpe ( 2, W + tw)
Invoking Lemma with Q 2 1 = (1 III }F and w = VI/K, conditioning on the event (24) in Lemma 3 holds true, we have
K
Ex [1Th Thei"" (infi) an bn.]
s =0vv KdimaEr (F, (IV,IKK 2¹) log (Nrus(Vmax/ ( (27)
Similarly, invoking Lemma with Q = 2 = -1- the event (25) in Lemma holds true, have with probability least 8/4.
" )F and w = VI/K, conditioning on
E [1 -Th (sn, bn)]
$ ptal' (sh, (sh,ah,bi bn) ) (Thiee (s oh. + O(v log(K/8)
<0
( V2 KdimBEE
F. VI/K, II,
(28)
where the first inequality comes from standard martingale difference concentration. Therefore. combining (27) and (28).we have:
K
Ex [fShi'"
Thu'
(hiti an bn)
0
Vann F, /1,KK,
Substitute the above bounds into (26) and we have:
(n') VI (51)
< 00 HV HVmaxy
KdimBEE F, VI/K,I,II')
(29)
I.3 STEP 3: BOUND THE REGRET
Now only need to bound the online learning error. Notice that p' is updated using Hedge with
reward V Since 0 < V < Viux and there are [I] policies, we have from the online learning
literature [20] that
K
K (p²)) ) Σ (v' pp) < Vmax V K log III]
Σ ('(p")
(30)
1=1
28

---

Under review as a conference paper at ICLR 2023
In addition, suppose 8& denotes the filtration induced by {u' } U ii', D,, observe that (V' pp) - V (4²) E 8t. In addition, we have V E Sc-1 since the estimation of V
( Then
only utilizes D1.-11 which implies
BIV -p))
Therefore (3) is a martingale difference sequence and by Azuma-Hoefiding'ss inequality we have with probability at least
8/4,
K
(p') S O( (1g()
(31)
Substituting (23), (29), (30), and (31) into (22) concludes our proof for Theorem 1. For the adaptive setting, can simply repeat the above arguments. The only difference is that now of can depend on Dia-1 and thus we need to introduce a union bound over II' when proving Lemma 2 and Lemma 3. This will incur additional log II'I in 3 and thus also in the regret bound. This concludes our proof.
J PROOFS OF LEMMAS IN APPENDIX I
J.1 PROOF OF LEMMA 2
Let VP be p-cover of G with respect to || llae. Consider an arbitrary fixed tuple (n, (,,t,h,9) Define W (h, 9- pi) as follows:
II [K] [H]
Wh, p) (gg (sh ar, b%) r Quiti (oh)
1Qh (sh by)) -rh Oitii (s (
and Sash be the filtration induced by {vl, ".....,,KK" uKKUUs bi, f at, by. ah. b... Then we have for all k S t- t-
B 9. 1) mk [(gn- Qh (sh az b/)13
and
VarlWe, g. 10 k S 4v2 V...EEWaa a (h, 9, kk.
By Freedman's inequality, with probability at least 1 - 8/4, we have
W Wh,hh, p)
Elen Q Moh, at 6/)1
1
1-1
I o
Vinax
Vina
log
Σ
[gn -hh1") (s ar, b/]12 + Vilax log
By taking union bound over II x [K] x [H] x Vp and the non-negativity of Σ (9h Quie (sh, at, b/)), we have with probability at least 5/4, for all (n,k,
h, g) E II [K] x [ V
(h g. (V
where log(HH (T)88). This implies for (n, 1, h) E II [K] [ x9,
t-1
(Q
(sti at, btt) - r (st 1
(on "(n of bt) - -
+ 0 max! + Vmaxtp).
1=
Choose p Vmax/ IK and we know that with probability at least 1 - 5 for all μ E II and t E [K]. Quie' E BBD,L,, (4, This concludes our proof.
29

---

Under review as a conference paper at ICLR 2023
J.2 PROOF OF LEMMA 3
Let 2p be a p-cover of F with respect to || lloc. Consider an arbitrary fixed tuple (,,t,h.f. E II [K] [H] x F. Let
(h, (fh oh bl) rh fn-1 -s
-(TTh fn+1)($hh at b%) - r 1 (h v²))
and RR. be the filtration induced by {ur ,.. , Juto ai, 61, ri 5 ust 6 rf,
at b. Then we have for all k $ 1,
E[X (1) = 11/n Thu (5h.)) 401.
and
(M, S 4V max (h, (,,)BAAA By Freedman's inequality, with probability at least 1 6, 6,
(h,
f.P)
I(f The fn+1) b111
[[ ElJh -h In+1) a2 1/)2 + Vilax log 1 !
o Vinx
log
z
8
k=1
By taking union bound over II [K] [H] Zp, we have with probability least - 8, for all
f) E x [K] x [H] x Zp.
Σ (e,(h,
I(h - The fn+1)(sh, ar bb)1
k=1
< 0
Vmmx
Σ
10h 1luh
-hh fn+1 an 12112 + Vil
(32)
where log( [ 2
Conditioned on the above event being true, we consider an arbitrary pair (h,t, 11) E [H] x [K] x II.
By the definition of BD..., (1, v") and Assumption 2, we have:
Σ (h, (hip k=1
(f ai b%) - - ( k=1
((TH fn+t) (b) r Shtz (5 (sh
(f ai b/))))) r fn+1 (8h+2,
inf (gn (sh ah bt)) th Sh41
33.
Let ['' = arg miniez, max w) 115
loc. 1.l loc. By the definition of 3p, we have
(h, pra ,1) s O(Vmaxtp + 13.
(33)
By (32), we know:
[-1 Σ
4 - -
Xe, Pun (", ,1)
-
1142 at, btt)1
k=
30

---

Under review as a conference paper at ICLR 2023
S o Vinx
L.
10
(4 of 61 2 + V (34)
k=1
Combining (33) and (34), obtain
1-1
1. Σ 10/0 -Th
(s 62]3 O(V + Vmaxtp + B).
This implies that
2-1 E EU
Thi Iu (5% ae b/o13 s D(Viax! + Vmaxlp 3).
Choose p = Vmax/H and we can obtain (b). For (a), simply let 3k,s be the filtration induced by {v' ,..., ,v* fn', si bi " 1k-1 concludes proof.
U nM and repeat the above arguments, which #4thh=
J.3 PROOF OF LEMMA 4
First notice that V (ut) fli1" (s1, v²). Therefore, we have
V (n²) VI (s1)
(1ss)) (s1, b1) Qi (s1, Barny' (-lem (l [ [B on 21, (s2,n', v''l Ese E (sa)1]
+ Fas ou (111) (1911) 101 -TH 12" (s1,
= Es Ifz (82, p. v²) - Va" (s2)] B, - -Tpl ve slil (s1, a1, b1)b
Repeat the above procedures and we can obtain Lemma 4. This concludes our proof.
K PROOF OF COROLLARY
From Theorem 2, we have with probability at least
6, for all E [n]
K
K
v x
MLETT
mIX
K
1.3
(81)
K
1,
(81) +e.
By the definition of म, this equivalent to
VM, x (SS) Vi. te,
AlEll,
where f=5 uniformly sampled from {p" R and thus is the marginal distribution of over the agents other than i. Therefore, by the definition of CCE in (2), a is e-approximate CCE with probability least 1 5, which concludes our proof.
L PROOF OF THEOREM 3
In this section present the proof for Theorem 3. Our proof mainly consists of four steps:
Prove (2) and V (1) are optimistic estimations of V (s1) and VK (s1) for all t E [K] and
μ E
Bound the total estimation error ΣK V'('") V/ (s) and E (+')) (s1).
(s1) Bound the regret by decomposing it into estimation error and online learning error induced by
Hedge.
Bound the constraint violation by strong duality.
31

---

Under review as a conference paper at ICLR 2023
Step 1: Prove optimism. First show that the constructed set Bpi.- (a) ( (n)) is not vacuous in the sense that the true action-value function Q (Q2) belongs to it with high probability: Lemma 6, With probability at least -8/4, we have for all E [K] and μ e IT.
in-1
O E BD (4), E BD, BD,,,,())) (1).
Proof. The proof is almost the same as Lemma 2 and thus is omitted here.
Then since (n()) = max EB (w) 1(11, 1)), we know for all & E [K] and μ E II,
((()) 2 Q% (s))
Similarly, we know (p( 2 VA (s1).
Step 2: Bound estimation error. Next we need to show the estimation error E 1 V((())
V (s1) and Σ V (a(t)) (si( are small. Let fr arg max (m) (81, and ft- arg ye (x) f(1, p)). Then we have
Lemma 7, With probability at least
5/4 we have for all t E [K], h E [H] and μ E ETT,
Σ E (Aa
(sn, an) (Th " (8n, 2) s 50(3,),
(a)
psh
(
(sh. (s): (Thi. 11er)) S (0(3)),
E
(b)
Shilli (5) (Th" (ot 0(8)),
MM
(
- ( S O(3,).
Proof. The proof is almost the same as Lemma 3 and thus omitted here.
Besides, using performance difference lemma easily bridge V+() - V (s1) and V
vii (s1) with Bellman residuals, whose proof is also omitted:
Lemma 8. For any & E [K], we have
H [(ftaarrr
Vi(u²)) -i'h
Σ
En
Tu'r fu'tthhhi shit' (sn an),
h=1
11
V (2( vol(s)) =
B [f
Tu' f pt. pt.t"
()sh an)l
Jh+1
h=1
Therefore, from Lemma 8 we can obtain for any t E [K].
H Σ A=1
V'(H") V/4
E
[[
Tu', plaa (sh, (sh, anl,
which implies
K Σ T (1')
H K
(s) -1
Σ Σ
The shit
"lat" """"""") (sh.
(35)
t=1
h=
32

---

Under review as a conference paper at ICLR 2023
Similar to Section I, from Lemma 5, conditioning the event in Lemma holds true, have with probability at least 1 - 6/4
K
d.1. Eps (1 -Th
Jh41 (8h,
" 04)]
s <0
H2 dimmBe (F, II, (H|[))o)-(H/KKKH]H]]]
Substitute the above bounds into (35) and we have:
(n') VV (81)
$ o H2 KdimBEE (F', II, (og())))
(36)
Similarly, we have
K
(((²) vul (s1)
0 112 MPv KdimnER (Js, VI/K, II,9) (H/K)
(37)
Step 3: Bound the regret. Now can bound the regret. We first decompose the fictitious total
regret Σ (V/tionr (s1) + Yv V.V +VVV' (HCumpP) ΣK E + Y.V (u')) to the following terms:
K E(vi((s) (s1) Y, (x9))
Hémee (s1) + Y (eVVg((nnn (HČMDP))
K
Σ VoMDe (81) Σ
V (HCMDP)
1=1
(1)
V (MCMDP) + Y,V' (HCMDP))
vV + Y.V! D2
(2)
( + Y,V* p'
Σ (V'((')) Y.v
(3)
K
K
V (1²)
Vi (s1)
+
(4)
From Lemma 6, we know (1) O. Since p' is updated using Hedge with loss function V have (2) H(1 X) log mT (3) is martingale difference sequence, which implies (3) S O( + / log(1/0)) with probability at least - 5/4. Finally, Step 2 has bounded term (4) in (36), which implies
K
K
( Homor (s1) + Y, (HCMMD)) - E(va' (s1) + Y.V
r.1
33

---

Under review as a conference paper at ICLR 2023
0
H² Asla
H
K log (Ncov, (1]
(38)
Now only need to bound
V (2())) if we want to bound the regret (V (V - (s1)). In fact, updating the dual variable Y with projected gradient descent guarantees us the following lemma:
Et= Di=IY((V Yi(V
(UCMDP) ((V
Lemma 9. Suppose the events in Lemina 6 hold true, we have
K
aH²K HVVK
Σ
V (n()) - 2
Proof. See Appendix L.2.
Substituting Lemma 9 into (38), obtain the bound Regret(K):
- Σ (V (s1) - Vi (a1)) &
K
H²2
V
KdREE, log (Neov.r (6))
Asta
Step 4: Constraint Violation Analysis. Next we need to bound the constraint violation. First
notice that Σ Yi V (x")) is indeed not far from Σ Y V (n²)) for any Y [0, X]. as shown in the following lemma whose proof is deferred to Appendix L.3:
Lemma 10. For any [0, x), we have
Σ Y Yi) - -V,(0) (H2 + +
2
Substituting Lemma 10 into (38) and notice that b < Vitism (81) 1 V V (HCMDD)) we have for any Y E [0,X], x].
K
Σ (V (s1)
(s1)) + Y Σ (6 V Vy(''))
0 c(((11
H²
V KdBEE, log (TTr.r[[T//0)
X2
Combining the above inequality with (37), we have
EV. (51) (ir( + Y
K
Σ (b ((()s)))
H2 X2
+ H3
/ /KEBEE)
Asta
where
BBEE
max
dimBEE F", VI/K,
/8),
dimpEE Fr, VP.VV/K/ 1/K, 11. (Hg(
Choose Y
fo 0
if E6- vo (s)))
y Y= v x otherwise.
then we can bound the summation of regret and constraint violation follows:
V.HOOne (81)
E Val (01)
K
+ xx
1
K
vaitor)
<0((p
H2
+
H3
/CBEE/ K
K
K
R2
dala
(39)
34

---

Under review as a conference paper at ICLR 2023
Further, when Assumption 6 and Assumption 7 hold, have the following lemma showing that an upper bound on (V (V-limme ($1) - k Σ V (s)) + X(b E Val (s)]++ implies an upper
bound on [b K Et Va (s)(s:)]=
Lemma 11. Suppose Assumption 6 and Assumption 7 hold and 2Y S C If (1'
Jt=1 C
II satisfies
K
ViHieuor (61) - K
Σ
C*
1
Σ
5ó
K
Then
1
vut (s1)
28
S
K
C
See Appendix L.4 for the proof. Combining Lemma 11, Lemma 1 and (39), we have
Σ
-0-vni(ss))
Vui 9.1
(
so(
(
H
v
KEBER
Auta
This concludes our proof.
L.1
PROOF LEMMA
Notice that D(Y*)= Viltume (s1), which suggests:
Viliimn (s1) D(Y") 2 LCMDP((H,") Y*)
= (s1) + Y (v (51) (V) b) 2 V (s1) + Y'Aala
This implics that
VIHTaor (81) - V (s1)
H
Y x
r.
Asla
Asta
which concludes our proof.
L.2
PROOF OF LEMMA
Notice that have:
K
0 0 K+1 ΣΣ (Y - YY,)
Y
1=1
(Projjo.x] (Ye+ (X, aab 1000--VV(4))) -V((())))) - xx?
(Y + a(b- V (2))))) y??
K
K
2aYi(b - v₂((t) + Σ a²(b 12(1))2
K VV (HŌMDP) - V v2((")) + a² KH2
where the last step is due optimism and Vuicee (s1) 2 b. This implies that
Σ VVV (HCMDe) (2((()) -V < aH2K
H² H2VK
2
This concludes proof.
35

---

Under review as a conference paper at ICLR 2023
L.3 PROOF OF LEMMA 10
Notice that we have for any E [ and Y E [0;
11+1 YI - 1 + ab v2()))) Y12
(Y, Y)² + 2a(b - -V)'(v)))))) -x)
Repeating the above expansion procedures, we have
0 S YK+1 2/2 s (Y - 2)² + 2a > (b (b- -V
which is equivalent to
(H2 (H²
Σe- -X) 1 5 2a
(Y1 - Y)² + a H²K v
2
This concludes our proof.
L.4
PROOF LEMMA
First we extend II in reasonable way to make the policy class more structured while not changing
its optimal policy. Define the set of state-action visitation distributions induced by the policy as follows:
Pn = (s, ()) E (AIS)x(AI) :p II].
Let conv((p) denote the convex hull of i.., for any d E conv(Pn), there exists (wptee 2 such that for any h [H] S.a E A, we have
dn(s,
Σ
w. a),
Σ w =1
NETT
NETT
As special case, there exists d' a) conv(Pn) such that for any h [H),s S.a A.
(s,
dh (s,
Notice that there exists one-to-one mapping from state-action visitation distributions to policies [41]. Let c11v(ll) denote the policy class that induces conv(Pn)) and then there exists μ such that = d" which implies
K Σ (s)),
K
(81)
Vul (s1)
Vut
(s)).
K
K
Therefore, the condition of this lemma says
(V."fsur (s1) - (st) (1)))))+** +C Vir(())) - 5.
(40)
Next show that PEMpP is still the optimal policy in conv(ll) when Assumption 6, i... strong duality, holds, First notice that
max min LCMDP (1, Y) Y20 (Eronv(((
min max LCMDP( Y)
min max Y20 dEconv(Pn)
LCMDP (d, Y).
|Econv (T)) Y'2
(41)
However, given Y > O.LoMpp(d, Y) is linear in d, which means the maximum is always attained at the vertices conv conv(Pn), i.e., Pn. Therefore we know
LCMDP(), Y) D(Y),
(IIo
36

---

Under review as a conference paper at ICLR 2023
which suggests
min max LCMDP(d,Y) (d, min max LCMDP(d,Y) = min max LCMDP(H,)), Y20 pell
(42)
Y20 dEconv(Pn)
Y20 dEPn
By strong duality, we have
min max (CMDP(H, Y) max min CCMDP(44 (u, Y) Y20 MEN
max min CCMDP (H, (E)onv( Y20
(43)
MEt Y20
Combining (41).(4)) and (43), know all the inequalities have take equality, which implies
PCMDP = arg max min LCMDP(H, Y),Y Y = arg min max (CMDP Y). (E)onv([) Y20
Y20 pEconv(1I)
Besides, strong duality also holds for maXpeconv(I)) miny COMDP(A,Y)
Now let U(T) = (aXperonv(T) (V71 (s 9.1 (51) 2 b+ r}, then we have for any μ E conv(II),
LCMDF(u, Y*) S
LCMDP (14, Y*) D(Y*) Villeame (s1): (EConv([I)
max
where the third step comes from strong duality. Therefore, for any μ E conv(II) and R which satisfies V. ($1) 2 b b+ T, we have
Villamee (s1) - TY* 2 LCMDr (14, V*) TY-
= =V, + Y ('VV (11)(11))) - -b-7) 2
This implies that for any E I, V.llnme (31) - TY 2 v(T). Pick F -16 v (s1)]+, then we have
(s V/HCMe (s1) 7Y ml
On the other hand, (40) is equivalent to
Vitiaa (s1) (=i(s)) C*7 S 8.
r1l
Thus have "C* < 8, which means that
1b vi (s1)1+ S Y² < C
25
Recall that Viil(s))
R EK V which concludes our proof.
M PROOF OF THEOREM 4
In this section we present the proof for Theorem 4. Our proof mainly consists of four steps:
Prove (H) 0.) is a pessimistic estimations of (s1), 0₂) for all f [K] and e II.
Bound the total estimation error + ΣK V (1() vi (s1)]..
Bound dist V (s1).
Step 1: Prove pessimism. First we can show that the true action-value function Q" belongs to the constructed set Bp...,(p)) (μ) with high probability:
Lemma 12. With probability at least 1 6/4, 44 we have for all t [K] and II, Q" E BD , (n).
Proof. Repeat the arguments the proof of Lemma 2 for each dimension j E [d] and the lemma follows directly.
Then since ('()) = f1(11. where f = arg y (f 0i), we know for all t [K] and μ II.
V'(n), 0.) < (sL, (8))
37

---

Under review as a conference paper at ICLR 2023
Step 2: Bound estimation error. Next need show the estimation error || E L'(x')
VI" (si)ll is small. Let f = arg (4) Oz). Let fhA) denotes the j-the
dimension of fiJ Then we have
Lemma 13. With probability at least 1 8/4, we have for all E [K], [H], j E [d] and p 11,
(shm)(sh, (
(s) (Th sht1 (( 27
(a)
Bic
< (0).).
(b)
(sh ax) (Th s1:11) oht) S (3))
Proof. Repeat the arguments in the proof of Lemma 3 for each dimension [d] and the lemma follows directly.
Besides, using performance difference lemma we have:
Lemma 14. For any t [K] and j E [d]. have
H
(2) V (81) Σ
Ba [C -Tu'al s (5h, on)],
where Vtd (p²) is the j-th dimension of V'(x).
Therefore, from Lemma 14 we can obtain for any E [K] and j [d]
H
K
Σ (1) V (81)
E (
The shift ") an)]-
(44)
h=1m= 1m1
Similar Section I, from Lemma 5, conditioning on the event in Lemma 13 holds true, with probability at least 1 - 5/4, we have for any j E [d] and h E [H].
K
Bas [Crt -Th" sartd andi] (sn.))))] s so( H22 H2KKdBEE log (Neov,v (Ild/))
Substitute the above bounds into (44) and we have for any j [d]:
Σ ( (8L) s sO(H2
KdBEE, Log(Noor.v/IIl///
which implies if the event in Lemma 13 true,
K ΣK'(a)) Vi vt < O(IIVa: v de (1
Step 3: Bound the distance. Now we can bound the distance dist( (²(ss) First since ç is sampled uniformly from {u0} KK, we know
K v
dist (V = dist
1
(51).
K
T=1
By Fenchel's duality, we know
dist
1
K
vi (s1)).)
max
K
Σ
vu
(81)
max (0, x)
K
0E
#EC
t=1
38

---

Under review as a conference paper at ICLR 2023
K
K
k
s max ()
v
(1t)
00 #EC
x)
+ max OEB(1)
0,
Vi
(81)
v'((t)
K
K 1=1
where the second step is due to max(fi + f2] S max fi + max f2.
Notice by Cauchy-Schwartz inequality and Step 2, we have
1 K K
1 K
max @EB(1)
0,
V (s1) - v'(a")
L
-
v7 (s1)
K 1=1
v dBEE. v log(Neovv [lll/6/KK)
Now we only need to bound max update O: using online gradient descent. Using the conclusions from the online learning literature [20]. we know
(0, K Σ v'())) max (0, x) Recall that we
K
1
K r (ua))
max OEB(I)
(0,x0, DEC
K
1=1
1 K
V'(''
max O(HVA/VKK.
ZEC
Further, notice that p' is updated via Hedge with loss function being (0,, (4)),, similarly to the analysis in Section we have with probability at least 1-6, 6,
K
K
O. 1=1
Σ
0r (HVMDP)) + O(HVd (log([II/8/KX))
K
K
where PVMDP arg minnen dist V1" Cs) Let P(V."inDe denote the projection of V.UiNDE (81) onto C.
Conditioning on the event of Lemma 12 holds, we have
K
K
Σ
Or. ('(UMDD)) < E(0,, (r, V VouDD (s1)).
1=1
Therefore we have
K
(Oc. V'(+²))
- (0, x))
sEC
K
1
(0c. V.KiMMD (81)) - max 2)) + O(HVd Vlog( (I/8)/K)
K
ZEc
K
1
(0e. V.HNMD (s1)) (0r, P(V ((V)tnnD(si))) + (IIVV /0))(1110)/KK)
K
1=1
VIiNADe (s1) - P(V (s:)) +O(HV [o
= min dist (VI' O (log(111/8//K)
Nen
where the second step is due to P(V (s1)) E C, the third step is from Cauchy-Schwand inequality, and the last step is from the definition of pAMDP-
In conclusion, we have with probability at least - 8,
dist (F) < min dist (issttVv(sss)))))))) O v dBEE, log (Noor, v II//6)/ K)
wenl
This concludes proof.
39


Reviews:
[{"review_id": "zpLwa5JKvB", "reviewer": "Reviewer_HFvo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper investigates Markov games with adversarial opponents with general function approximation. It proposes provably efficient algorithm $\\mathsf{DORIS}$ and a new complexity measure called Bellman Evaluation Eluder (BEE) dimension to aid its analysis. Finally, this algorithm is also extended to Constrained MDPs and Vector-valued MDPs.", "summary_of_the_review": "This paper proposes the first provably efficient algorithm for Makrov games under adversarial opponents with general function approximation. This algorithm has wide application and its analysis also contains novel tools called BEE dimension.", "strength_and_weaknesses": "### Strengths\nThis paper extends algorithms for Markov games under adversarial opponents from tabular MDPs to thos with general function approximation, which is considered to be significant. Meanwhile, it proposes the novel Distributional Eluder dimension and corresponding BEE dimension to aid its regret analysis, which may be of independent intereest. Meanwhile, the proposed algorithm $\\mathsf{DORIS}$ also has wide application including self-play scenario, CMDPs and VMDPs.\n\n### Weaknesses\nIt would be idea to have infinite policy class by imposing more assumptions. However, from my perspective, it is okay to leave it as future work for now.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "c38oxVXjnuI", "reviewer": "Reviewer_pavp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes an algorithm Decentralized Optimistic hypeRpolicy mIrror deScent (DORIS) for decentralized policy learning in Markov games with function approximations. The setting is \"policy revealing\", where the opponents (could be adversarial) would reveal its previous policies to the agent for making decisions.\n\nTo combat non-stationarity, DORIS (Algorithm 1) mains a \"hyperpolicy\", which is a probability distribution over policies of the agent, and uses Hedge / mirror descent (MD) to update the hyperpolicy, with estimated value functions. The value function is estimated using optimism in LSPE, as shown in Algorithm 2.\n\nTo upper bound the value function estimation errors, the authors proposed a new complexity measure called Bellman Evaluation Eluder (BEE) dimension of function classes, with discussions of its relation to existing measures like Eluder dimension.\n\nUnder finite policy class Assumptions 1 and 5, and realizability and completeness Assumptions 2, 3 and 4, the authors proved that the proposed DORIS algorithm achieves $\\sqrt{K}$ regret comparing to best policy in hindsight in both oblivious and adversarial opponent settings, as shown in Theorems 1 and 2, where $K$ is the number of episodes.\n\nFinally, Corollary shows that if every agent is playing DORIS algorithm simultaneously, then with high probability the uniformly mixed policy can find a $\\epsilon$-approximate coarse correlated equilibrium (CCE) in $\\mathcal{O}(1/\\epsilon^2)$ iterations.\n\nIn the appendix, the authors also studied using DORIS in constrained MDPs and vector-valued MDPs, where similar regret bounds can be obtained.", "summary_of_the_review": "Overall, I found both the results and the technical contributions interesting and sound.", "strength_and_weaknesses": "**Strength**:\n\n1. DORIS achieves $\\sqrt{K}$ regret in terms of Definition 1, using function approximations with low BEE dimensions, which is a stronger result than NEs.\n2. The proposed BEE dimension seems a reasonable complexity measure in this setting, and the authors provided calculations to show the BEE dimensions for kernel MGs and generalized linear complete models.\n3. Comparison with existing works are also discussed clearly.\n\n**Weaknesses**:\n\n1. The current results are for episodic settings. How do you generalize the techniques to other scenarios like discounted settings?\n2. As noted in the paper, computational efficiency could be a problem for Algorithm 2. Is it possible that for some specific models (such as the generalized linear complete models mentioned), Algorithm 2 can be implemented in practice?\n3. I found the policy revealing assumption kind of strong. Revealing the opponents' policies seems weaken the results for adversarial settings studied in the paper. I feel this part needs better argument, such as using examples to show that policy revealing does appear in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "K-HedqN2nfk", "reviewer": "Reviewer_8Rj7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the decentralized Markov games with possibly adversarial opponents. Specifically, only one agent in the game can be controlled and others are regarded as adversarial opponents. The paper first considers the general function approximation problem in this setting with the bounded Bellman Evaluation Eluder dimension. To deal with the problem, it proposes an algorithm that is a variant of Online Mirror Descent with optimistic estimated V values. The regret bounds for both oblivious and adaptive adversarial settings are provided. When all agents run this algorithm simultaneously, the mixed policy is also an epsilon-CCE with sample complexity 1/epsilon^2. The paper finally discusses the application of the algorithm in the case of constrained MDP (CMDP) and vector-valued MDP (VMDP).", "summary_of_the_review": "In general, this paper generalizes previous works for decentralized Markov games in tabular case to general function approximation with bounded Bellman Evaluation Eluder dimension. Though the technique is not novel, the results are good compliments of existing literature.", "strength_and_weaknesses": "Strength:\n\nThe paper first studies the general function approximation problem in the decentralized Markov games, which generalizes previous works [33] for the tabular setting. The work provides complete results including regret bounds for oblivious and adaptive adversaries,\nguarantee for CCE results, and also discusses other generalizations to CMDP and VMDP.\n\nWeakness:\n\n1. More comparisons on the regret order with previous works for decentralized Markov games in tabular case (when reducing the current setting to the tabular case) and single-agent MDP with bounded BE dimension.\n\n2. Given previous works for decentralized Markov games in tabular settings and MDP with the bounded BE dimension, the theoretical contribution seems to be weak. The authors discussed in Appendix E that the difference between these works lies in the construction of optimism. Though the learner should build confidence sets for each \\mu when faced with each \\nu_k, the global optimism seems to hold by modifying the complexity with respect to the two policies of the agent itself and adversarial opponents.\n\n3. Minor: The notation is not easy to follow. The paper uses \\mu_i and \\mu_{-i} to represent the policy of agent i and the joint policy of other agents while using \\pi to represent the joint policy of all agents. Why not use \\mu to represent the joint policy? I think it will be more consistent. The paper uses t to represent the index of both epoch and step in Section 2. Perhaps it would be better only use it to represent epoch but use h to represent step. Algorithm 1 shows “run \\pi_t =\\mu_t \\times \\nu_t” to collect data. In fact \\nu_t is not run by\nthe controlled agent. \n\nQuestion:\nSince the paper regards all of other agents as adversarial opponents whose actions cause the non-stationarity of the transition, I am wondering whether such a technique can deal with single-agent MDP with adversarial transitions. Could the authors give some intuitions?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BB5Sf5I6dRD", "reviewer": "Reviewer_RXcH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Paper Summary\n\nThis paper considers decentralized (i.e. control over a single agent) learning in Markov games with adversarial multiple opponents.  At a high level, the fundamental goal is to design a no-regret learning policy, i.e. sublinear regret to converge towards the best fixed policy in hindsight.  This is complicated in this model for two reasons (1) the system is non-stationary since the opponents are adversarial and can change over time (2) the algorithm still needs to efficiently generalize through the use of a function class.  The authors tackle this problem by designing a decentralized multi-agent reinforcement learning algorithm with function approximation which has provably sublinear no-regret learning guarantees.  The algorithm, coined DORIS, uses a technical combination of Hedge (for adapting over the adversarial nature of the problem) alongside a novel value function estimation step within the multi-agent environment.  The authors show sublinear regret guarantees with respect to a new complexity measure, the Bellman Evaluation Eluder dimension, which generalizes to multi-agent problems.  The complement these results with special guarantees for the constrained MDP and vector-valued MDP setup (although these results are not discussed in the main paper).\n\nMore concretely the authors consider an n-agent MDP $(S, A_i, r_i, P, H)$ where $S$ is the state space, $A_i$ the actions for player $i$, $r_i$ the individual reward function, $P$ the global transition distribution, and $H$ is the horizon.  Policies are decentralized (i.e. agent $i$ observes state and picks only action in $A_i$.  The authors consider the decentralized setting which means that the player only controls (let's say the first action sets $A_1$) and the rest are chosen by potential adversary.  However, the authors consider the policy revealing setting, meaning that at the end of an episode the algorithm observes the policies that were played by the other agents (i.e. distribution over actions instead of just the observed action selected).  The goal is to achieve sublinear regret guarantees, where regret is measured as:\n\n$R(K) - \\max_{\\pi} \\sum_k V_1^{\\pi} - V_1^{\\pi^k}$\n\nwhere I have omitted the dependence on the policy for the other agents.  Note that this is fundamentally different from prior settings which just hope to converge to a Nash policy, this is instead attempting to compete against the best fixed policy in hindsight.\n\nThe algorithm works as follows.  First we maintain a distribution $p_t$ over the space of all possible policies $\\Pi$ which is updated with exponential weights via Hedge.  The estimates or \"losses\" which are used in the Hedge updates are collected via an optimistic policy estimation technique, which is novel to this work over prior literature, which uses advances in optimistic policy estimation over general function classes.\n\nThe authors complement the algorithm formulation with several regret bounds under different adversarial assumptions on the problem.\n\n## Questions\n- Can you comment on the assumption that the function class for other agents is required for the algorithm? It seems a bit strange - especially since the reward functions could be modelled with different features for different agents?\n- Can you comment more on the computational feasibility of the algorithm? Or are some of these issues avoided with the assumption of finite policy class?\n\n## Minor Comments\n- The hardness results in [33] are cited frequently with no formal description.  It is relatively easy to understand form context, but it would be helpful to describe that result more thoroughly\n- Space before citation [44] in introduction\n- On page 2 the discussion before the bolded question makes it seem as though your paper does not consider policy revealing - but that is exactly the model which is studied\n- On page 8 before Adaptive Opponent maybe add some signaling for $\\Pi$ being policy for controlled agent and $\\Pi'$ being other agents - found the assumptions a bit hard to keep track of\n\nEDIT: Thanks to the authors for addressing all of my comments. I have no further concerns, but still suggest that the hardness results be expanded in the revisions.", "summary_of_the_review": "The paper provides strong theoretical contributions for understanding no-regret learning in decentralized Markov Games.  The paper is extremely well written, highlighting the main differences and contributions between the paper and the related work.  However, the paper offers no empirical results (or discussion on computational tractability of their algorithm).", "strength_and_weaknesses": "## Strengths\n1. The authors study a novel model for learning in Markov Games - providing the first study of no-regret learning (i.e. benchmarking against best fixed policy in hindsight) with general function approximation.\n2. The theoretical contributions include developing a novel problem complexity measure similar to the Eluder dimension extended to the multi-player setting\n\n\n## Weaknesses\n1. The authors include no discussion on the computational complexity of the algorithm.\n2. There are no theoretical matching lower bounds (or discussion along this point)\n3. The authors provide no empirical results of their algorithm's performance\n4. The theoretical contributions and algorithm design seems like a straightforward extension of the algorithm presented in [33] with prior mechanisms for estimating the value function with general function approximation techniques.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster