ZERO-SUM MARKOV GAMES
Year: 2021

Abstract:
This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. The study focuses on the challenging settings where the value function or the model is parameterized by general function classes. Provably efficient algorithms for both decoupled and coordinated settings are developed. In the decoupled setting where the agent controls a single player and plays against an arbitrary opponent, we propose a new model-free algorithm. The sample complexity is governed by the Minimax Eluder dimension—a new dimension of the function class in Markov games. As a special case, this method improves the state-of-the-art algorithm by a √ d factor in the regret when the reward function and transition kernel are parameterized with d-dimensional linear features. In the coordinated setting where both players are controlled by the agent, we propose a model-based algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample complexity can be bounded by a generalization of Witness rank to Markov games. The model-free algorithm enjoys a √ K-regret upper bound where K is the number of episodes.

text: √ d factor in the regret when the reward function and transition
kernel are parameterized with d-dimensional linear features. In the coordinated setting where both players are controlled by the agent, we propose a model-based algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample complexity can be bounded by a generalization of Witness rank to Markov games. The model-free algorithm enjoys a √ K-regret upper bound where K is the number of episodes.

heading: 1 INTRODUCTION
text: In competitive reinforcement learning, there are two agents competing against each other by taking actions. Their actions together determine the state evolutions and rewards. Function approximation, especially deep neural networks (LeCun et al., 2015), contributes to the success of RL in many real world applications, such as Atari (Mnih et al., 2013), Go (Silver et al., 2015), autonomous driving (Shalev-Shwartz et al., 2016), Texas holdem poker (Sandholm, 2017), and Dota (Berner et al., 2019).
The goal of competitive reinforcement learning aims to learn the Nash Equilibrium (NE) policy in a trial-and-error fashion. In a NE, no agent can be better off by unilaterally deviating from her policy. Most of the existing sample efficient competitive RL algorithms focus on the tabular or linear function approximation cases (Pérolat et al., 2017; Bai & Jin., 2020; Bai et al., 2021; 2020; Xie et al., 2020; Zhang et al., 2020). The huge empirical success of neural network based RL methods has remained largely unexplained. Thus, there exists a wide gap between theory and practice in competitive RL with general function approximation. One demanding question to ask is:
Can we establish provably efficient competitive RL algorithms with general function approximation?
In this paper, we make a step towards answering this question by providing structural conditions and complexity measures of Markov Games and function classes that allow for efficient learning. We focus on episodic zero-sum Markov Game (MG) with simultaneous move, where each episode consists of H time steps and two players act simultaneously at each time step. The state space is arbitrarily large and can be infinite. We consider two function approximation settings: 1) use a general function class F to approximate the action-value function (Q function); 2) use a general function classM to approximate the environment. To this end, we introduce algorithms based on optimistic principles. Due to subtle game-theoretic issues, naive optimism is no longer working in Markov games where minimax optimization is performed. To deal with this issue, we use the algorithmic idea called ‘alternate optimism’. Specifically, we develop algorithms for both coordinated and decoupled setting. In the decoupled setting, the agent controls one player and plays against an arbitrary and potentially adversarial opponent. The sample
efficiency is measured by the gap between the learned value and value of the Nash Equilibrium. In the coordinated setting, the agent controls both players and the goal is to find the approximate Nash Equilibrium, i.e. with small duality gap. We identify key complexity measures of function classes to examine the effectiveness of elimination. By doing so, we prove upper bounds on sample complexity and regrets of the presented procedures that are independent of the number of states.
Our contributions are summarized into the following two folds:
• In the decoupled setting, we introduce Minimax Eluder dimension–a new complexity measure for competitive RL problems. We propose an algorithm that incurs at most Õ(H √ dEK logNF ) 1 regret in K episodes where dE denotes the Minimax Eluder di-
mension NF denotes the covering number of function class, with probability at least 1− p. As a special case, this result improves Xie et al. (2020) by a √ d multiplicative factor in their setting when the reward function and transition kernel are linearly parameterized and d is the dimension of feature mapping.
• In coordinated settings, we propose both model-based and model free algorithms. In the model-based setting, we generalize the witness rank (Sun et al., 2019a) to competitive RL. We prove that Õ(H3W 2/ϵ2) samples are enough to learn a policy ϵ-close to the Nash Equilibrium, where W is witness rank. In the model-free setting, we develop algorithm for agnostic learning with a candidate policy class Π. The algorithm incurs at most Õ(H √ dK log(NFNΠ)) regret. Here d is a variant of Minimax Eluder dimension and NΠ
denotes the covering number of policy class.

heading: 1.1 RELATED WORKS
text: There is a rich literature studying the learning and decision-making of Markov Games (Littman & Szepesvari, 1996; Greenwald et al., 2003; Grau-Moya et al., 2018; Pérolat et al., 2018; Srinivasan et al., 2018; Sidford et al., 2020; Wei et al., 2017; Pérolat et al., 2017; Bai & Jin., 2020; Bai et al., 2021; 2020; Zhang et al., 2020; Zhao et al., 2021). The most related to us are perhaps (Xie et al., 2020; Chen et al., 2021; Jin et al., 2021b), where the authors address the challenge of explorationexploitation tradeoff in large state spaces. Due to space constraint, a detailed literature discussion is deferred to Appendix A.

heading: 1.2 TECHNICAL CHALLENGES
text: Previous work (Xie et al., 2020) imposes optimistic bonus on the action-value functions in every stateaction pairs and performs planning by the Coarse Correlated Equilibrium (CCE) on the optimistic value functions. To achieve improved rates, we leverage the idea of ‘global optimism’ (Zanette et al., 2020; Jin et al., 2021a; Du et al., 2021), which maintains a constraint set of candidate functions that do not deviate much from the empirical estimates and performs optimistic planning on the initial state. However, going beyond MDPs towards MGs, two problems arise. First, the concentration property of functions in constraint set is hard to characterize due to multi-agent interplay. For this, we use the concentration methods in Jin et al. (2021a) and extend it from MDPs to MGs. The second and more prominent issue is the exploration and exploitation tradeoff. Since ‘global optimism’ only obtains optimism along the trajectories of behaviour policies, it may not guarantee optimism on the trajectories of target policies (i.e. NE). As a result, directly using CCE to plan will cause the duality gaps to diverge. To deal with this problem, we apply ‘alternate optimism’ to guide explorations, which was previously used in Wei et al. (2017) for model-based methods. The ‘alternate optimism’ used in this work is slightly different for value-based methods. We prove two regret decomposition lemmata to support this optimism principle.

heading: 2 PRELIMINARIES
text: We consider two-player zero-sum simultaneous-moves episodic Markov game, defined by the tuple
(S,A1,A2, r,P, H)
1We use Õ to hide logarithmic terms in H , 1/p and K.
where S is the state space, Ai is a finite set of actions that player i ∈ {1, 2} can take, r is the reward function, P is the transition kernel and H is the number of time steps. At each time step h ∈ [H], player P1 and P2 take actions a ∈ A1 and b ∈ A2 respectively upon observing the state x ∈ S, and then both receive the reward rh(x, a, b). The system then transitions to a new state x′ ∼ Ph(·|x, a, b) according to the transition kernel P. Throughout this paper, we assume for simplicity that A1 = A2 = A and that the rewards rh(x, a, b) are deterministic functions of the tuple (x, a, b) taking values in [−1, 1]. Turn-based games are special cases of simultaneous games in the sense that at each state the reward and transition are independent of one player’s action (Xie et al., 2020). Generalizations to A1 ̸= A2 and stochastic reward are also straightforward. Denote by ∆ := ∆(A) the probability simplex over the action space A. A stochastic policy of P1 is a length-H sequence of functions π := {πh : S 7→ ∆}h∈[H]. At each step h ∈ [H] and state x ∈ S, P1 takes an action sampled from the distribution πh(x) over A. Similarly, a stochastic policy of P2 is given by the sequence ν := {νh : S 7→ ∆}h∈[H]. The learning happens in K episodes. In each episode k, each player P1 and P2 proposes a policy πk and νk respectively based on history up to the end of episode k − 1 and then executes the policy to observe the trajectories {xkh, akh, bkh}Hh=1. For a fixed policy pair (π, ν), the value function and Q functions for zero-sum game is defined by
V π,νh0 (x) := E
[ H∑
h=h0
rh(xh, ah, bh)|xh0 = x
] ,
Qπ,νh0 (x, a, b) := E
[ H∑
h=h0
rh(xh, ah, bh)|xh0 = x, ah0 = a, bh0 = b
] ,
where the expectation is over ah ∼ πh(xh), bh ∼ νh(xh) and xh+1 ∼ Ph(·|xh, ah, bh). V π,ν1 and Qπ,ν1 are often abbreviated to V
π,ν and Qπ,ν . In zero-sum games, PI aims to maximize V π,ν(x1) and P2 aims to minimize V π,ν(x1). Given policy π of P1, the best response policy of P2 is defined by ν∗π := argminνV
π,ν(x1). Similarly given policy ν of P2, the best response policy of P1 is defined by π∗ν := argmaxπV π,ν(x1). Then from definitions,
V π,ν ∗ π (x1) ≤ V π ∗,ν∗(x1) ≤ V π ∗ ν ,ν(x1)
and the equality holds for the Nash Equilibrium (NE) of the game (π∗, ν∗). We abbreviate V π ∗,ν∗(x1) as V ∗ and Qπ ∗,ν∗(x1) as Q∗. V ∗ is often referred to as the value of the game. As common in Markov games literature (Pérolat et al., 2015), we will use the following Bellman operator
ThQh+1(x, a, b) := r(x, a, b) + E x′∼Ph(·|x,a,b) [max π′ min ν′
V π ′,ν′
h+1 (x ′)], (1)
and the following Bellman operator for fixed P1’s policy
T πh Qh+1(x, a, b) := r(x, a, b) + E x′∼Ph(·|x,a,b) [min ν′
V π,ν ′
h+1 (x ′)]. (2)
Notations For a integer H , [H] denotes the set {1, 2, . . . ,H}. For a finite set S, |S| denotes its cardinality. For a matrix A ∈ Rd, Ai,∗ and A∗,j denote the i-th row and j-th column of A respectively. For a function f : S 7→ R, ∥f∥∞ denotes sups∈S |f(s)|. We use N (F , ϵ) to denote the ϵ-covering number of F under metric d(f, g) = maxh ∥fh − gh∥∞.

heading: 3 DECOUPLED SETTING
text: In decoupled setting, the algorithm controls P1 to play against P2. In k-th episode, P1 chooses a policy πk and P2 chooses a policy νk based on πk. Then P1 and P2 interact in the Markov Game by playing πk and νk respectively, and observe the rewards and states in this episode. Notice that P2 can be adversarial and its policy is never revealed, meaning that P1 can only maximize its reward by playing π∗. The goal is to thus minimize the following ‘value regret’
Reg(K) = K∑ k=1 [V ∗1 (x1)− V πk,νk 1 (x1)]. (3)
A small value regret indicates that we learn the value of MG. If an algorithm obtains an upper bound on value regret that scales sublinearly with K for all νk, then it can not be exploited by opponents.

heading: 3.1 FUNCTION APPROXIMATION
text: We consider function class F = F1×· · ·×FH where Fh ⊂ {f : S ×A1×A2 7→ [0, 1]} to provide function approximations for Q∗ — the Q-function of Nash Equilibrium. For a policy pair (π, ν) and function f we abuse the notations and use f(x, π, ν) = Ea∼π,b∼ν [f(x, a, b)] to denote the expected reward of executing (π, ν) in function f . We make the following assumptions about F . Assumption 3.1 (Realizability). We assume Q∗h ∈ Fh for all h ∈ [H]. Assumption 3.2 (Completeness). We assume for all h ∈ [H] and f ∈ Fh+1, Thf ∈ Fh.
Realizability means the function class contains the target Q function. Completeness says the function class is closed under the Bellman operator. These assumptions are common in value function approximation literature (e.g. Jin et al. (2020); Wang et al. (2020b); Jin et al. (2021a)). Note that they are weaker than Xie et al. (2020), as their setting satisfies Thf ∈ Fh for any action-value function f . For a function f ∈ F , we denote the max-min policy of P1 by πf . Specifically,
(πf )h(x) := argmaxπmin ν
fh(x, π, ν),∀h ∈ [H].
Similarly we denote the min-max policy of P2 by νf . Given policy π of P1, the best response policy of P2 in terms of function f is defined by
(νfπ)h(x) := argminνfh(x, πh, ν),∀h ∈ [H].
Similarly given policy ν of P2, the best response policy of P1 in terms of function f is denoted by πfν . When there is no confusion, we will drop the subscript h for simplicity.
Learnability requires the function class to have bounded complexity. We introduce Minimax Eluder dimension to capture the structural complexity of function classes in zero-sum games. To define, we use ϵ-independence of distributions and Distributional Eluder dimension (DE) from Jin et al. (2021a). Definition 3.3 (ϵ-independence of distributions). Let G be a function class defined on X , and ν, µ1, . . . , µn be probability measures over X . We say that ν is ϵ-independent of {µ1, . . . , µn} with respect to G if there exists g ∈ G such that √∑n i=1(Eµi [g])2 ≤ ϵ but |Eν [g]| ≥ ϵ. Definition 3.4 (Distributional Eluder dimension (DE)). Let G be a function class defined on X , and D be a family of probability measures over X . The distributional Eluder dimension dimDE(G,D, ϵ) is the length of the longest sequence {ρ1, . . . , ρn} ⊂ D such that there exists ϵ′ ≥ ϵ where ρi is ϵ′-independent of {ρ1, . . . , ρi−1} for all i ∈ [n].
Now we introduce Minimax Eluder dimension. Recall the minimax Bellman operator from Eq (1):
Thfh+1(x, a, b) := r(x, a, b) + E x′∼Ph(·|x,a,b) [max π′ min ν′ fh+1(x ′, π′, ν′)]
thus Minimax Eluder dimension is the Eluder dimension on the Bellman residues with respect to the above minimax Bellman operator. Definition 3.5 (Minimax Eluder dimension). Let (I −Th)F := {fh−Thfh+1 : f ∈ F} be the class of minimax residuals induced by function class F at level h and D∆ = {D∆,h}h∈[H] where D∆,h := {δ(x, a, b) : x ∈ S, a ∈ A1, b ∈ A2} is the set of Dirac measures on state-action pair (x, a, b). The ϵMinimax Eluder dimension of F is defined by dimME(F , ϵ) := maxh∈[H] dimDE((I−Th)F ,D∆, ϵ).

heading: 3.2 OPTIMISTIC NASH ELIMINATION FOR MARKOV GAMES
text: Now we introduce Optimistic Nash Elimination for Markov Games (ONEMG), presented in Algorithm 1. This algorithm maintains a confidence set Vk that always contains the Q∗, and sequentially eliminates inaccurate hypothesis from it. In k-th episode, P1 first optimally chooses a value function fk in Vk−1 that maximizes the value of the game. Intuitively, this step performs optimistic planning in the pessimistic scenarios, i.e. assuming P2 plays the best response. Next, it plays against P2 and augments the data from this episode into replay buffer B. The confidence set Vk is then updated by keeping the functions f with small minimax Bellman errors fh − Thfh+1, in Line 12. To estimate fh − Thfh+1, we use EBh(fh, fh+1) − infg∈Fh EBh(g, fh+1), a standard variance reduction trick to avoid the double-sample issue. It can be shown that when the value function class is complete, EBh(fh, fh+1)− infg∈Fh EBh(g, fh+1) is an unbiased estimator of fh − Thfh+1 (Lemma B.1).
Notice that unlike many previous works that add optimistic bonus on every state-action pairs (Xie et al., 2020; Chen et al., 2021), Algorithm 1 only takes optimism in the initial state. Instead, the constraint set contains every function that has low Bellman residue on all trajectories in the replay buffer. This ‘global optimism’ technique trades computational efficiency for better sample complexity, and can be found in many previous work in Markov Decision process (Zanette et al., 2020; Jin et al., 2021a). As we will see later, it is also useful in the coordinated setting.
Algorithm 1 Optimistic Nash Elimination for Markov Games (ONEMG) 1: Input: Function class F 2: Initialize Bh = ∅, h ∈ [H], V0 ← F 3: Set β ← C log(N (F , 1/K) ·HK/p) for some large constant C 4: for k = 1, 2, . . . ,K do 5: Compute fk ← argmaxf∈Vk−1f1(x1, πf , νf ), let πk ← πfk 6: for step h = 1, 2, . . . ,H do 7: Interact with environment by playing action akh ∼ πkh(xkh) 8: Observe reward rkh, opponent’s action b k h and move to next state x k h+1
9: end for 10: Update Bh ← Bh ∪ {(xkh, akh, bkh, rkh, xkh+1)},∀h ∈ [H] 11: For all ξ, ζ ∈ F and h ∈ [H], let
EBh(ξh, ζh+1) = k∑
τ=1
[ξh(x τ h, a τ h, b τ h)− rτh − ζh+1(xτh+1, πζh+1 , νζh+1)]2
12: Set Vk ← {f ∈ F : EBh(fh, fh+1) ≤ inf
g∈Fh EBh(g, fh+1) + β,∀h ∈ [H]}
13: end for

heading: 3.3 THEORETICAL RESULTS
text: In this section we present the theoretical guarantee for Algorithm 1. The proof is deferred to Appendix B. Theorem 3.6. Under Assumption 3.1 and Assumption 3.2, the regret Eq (3) of Algorithm 1 is upper bounded by
Reg(K) ≤ O ( H √ K · dME log(HKζ) )
with probability at least 1− p. Here dME = dimME(F , √ 1/K) and ζ = N (F , 1/K)/p.
As this theorem suggests, as long as the function class has finite Minimax Eluder dimension and covering number, P1 can achieve √ K-regret against P2. Notice that when P2 always plays the best response of P1’s policies, this regret guarantee indicates that algorithm eventually learns the Nash Equilibrium. In this case, the algorithm takes Õ(H2d log(|F|)/ϵ2) samples to learn a policy π that is ϵ-close to π∗.
When the opponent plays dummy actions, the Markov Game can be seen as an MDP and the value of the Markov Game is the maximum cumulative sum of rewards one can achieve in this MDP. In this case, our result reduces to Õ(H · √ K · dBE log(N (F , 1/K))) where dBE is the Bellman eluder dimension in Jin et al. (2021a).
In particular, when the function class is finite, the regret becomes O(H √ KdME log(HK|F|/p)) that depends logarithmically on the cardinality of F . Moreover, when the reward and transition kernel have linear structures, i.e. rh(x, a, b) = ϕ(x, a, b)⊤θh and Ph(·|x, a, b) = ϕ(x, a, b)⊤µh(·) where ϕ(x, a, b) ∈ Rd, then dME(F , √ 1/K) = logN (F , 1/K) = Õ(d) and the regret becomes
Õ ( Hd √ K ) 2. Thus we improve Xie et al. (2020) by a √ d factor. We also provide a simpler algorithm tailored for this setting, see Appendix B.1 for details. 2Here we use Õ to omit the logarithm factors in K, d, H and 1/p.
Algorithm 1 solves a non-convex optimization problem in Line 5 with highly non-convex constraint set (Line 12). In general, it is computationally inefficient. Even when reduced to linear MDP, i.e. the opponent plays dummy actions and the transition matrices and the rewards have low rank structures, it is not known if the same Õ(H √ d2K) regret can be achieved with computationally efficient algorithms (Zanette et al., 2020). Designing computationally efficient algorithms with near-optimal sample efficiency is an interesting further direction.

heading: 4 COORDINATED SETTING
text: In the coordinated setting, the agent can control both P1 and P2. The goal is to find the ϵ-approximate Nash equilibrium (π, ν) in the sense that
V π ∗ ν ,ν(x1)− V π,ν ∗ π (x1) ≤ ϵ (4)
by playing P1 and P2 against each other in the Markov game. In the following sections, we propose both model-based and model-free methods to deal with this problem.

heading: 4.1 MODEL-BASED ALGORITHM
text: In model-based methods, we make use of a model classM of candidate models to approximate the true model M∗. We are also given a test function class G to track model misfit. Given a model M ∈M, we use QM (x, a, b), rM (x, a, b) and PM (·|x, a, b) to denote the Q-function, reward function and transition kernel of executing action a and b at state x in model M . For simplicity, we use (r, x) ∼ M to represent r ∼ rM (x, a, b) and x ∼ PM (·|x, a, b). We denote the NE policy in model M as πM and νM . For policy π, ν and model M , we use νMπ to denote the best response of π in model M and πMν is defined similarly.

heading: 4.1.1 ALTERNATE OPTIMISTIC MODEL ELIMINATION (AOME)
text: The model-based method, Alternate Optimistic Model Elimination (AOME), is presented in Algorithm 4. It maintains a constraint setMk of candidate models. Throughout K iterations, AOME makes sure that the true model M∗ always belongsMk for all k ∈ [K], and sequentially eliminates incorrect models fromMk. However, the idea of being optimistic only at initial state (Zanette et al., 2020; Jin et al., 2021a) is not directly applicable to this scenario. Since the objective to be optimized is the duality gap, the target policies being considered are thus policies pairs (π∗ν , ν) and (π, ν ∗ π). However, π ∗ ν and ν∗π are not available to the agents. Therefore, the performances of proposed policies are evaluated on out-of-distribution trajectories, meaning that optimism can not be guaranteed. This causes the distribution shift issue. In worst cases, low Bellman errors in the collected trajectories provide no information for the trajectories collected by π∗ν , ν and π, ν ∗ π .
To address this issue, the algorithm performs global planning by applying the idea of alternate optimism to model-based methods. In k-th episode, the algorithm first solves the optimization problem Mk1 = argmaxM∈M Q M (x1, π M , νM ) and let πk = πM k 1 . This optimization problem corresponds to finding the optimistic estimate of the value of the game. Indeed, notice that M∗ ∈Mk
implies QM k 1 (x1, π k, νk) ≥ QMk1 (x1, πk, ν Mk1 πk ) ≥ V ∗(x1), by optimality of Mk1 . Next, it solves the second optimization problem Mk2 = argminM∈M Q M (x1, π Mk1 , νM ) and let νk ← νM k 2 πk . This corresponds to finding the pessimistic estimate of V π k,ν∗ πk (x1). In fact, we see that M∗ ∈ Mk implies QM k 2 (x1, π k, νk) ≤ V π k,ν∗
πk (x1), by optimality of Mk2 . This approach appears in Wei et al. (2017) to guarantee convergence to Nash equilibrium, where it is referred to as ‘Maximin-EVI’.
In Line 8, the algorithm checks if the values of model Mk1 and M k 2 are close to the value of the true model M∗ when executing policy πk and νk. If the condition holds, we have
V ∗(x1)− V π k,ν∗ πk (x1) ≤ QM k 1 (x1, π k, νk)−QM k 2 (x1, π k, νk) ≤ ϵ,
which means that AOME finds policy πk that is ϵ-close the NE. One can also switch the order of alternate optimism and obtain νk that is ϵ-close the NE. We then terminate the process and output πk
and νk. If the algorithm does not terminate in Line 8, it applies the witnessed model misfit checking method in Sun et al. (2019a). It starts by computing the empirical Bellman error of Markov games defined as follows
L̂(M1,M2,M, h) := n1∑ i=1 1 n1 [QMh (x i h, a i h, b i h)− (rih +QMh (xih+1, πM1 , ν M2 πM1 )]. (5)
As proved in Appendix D, in this case L̂(Mk1 ,Mk2 ,Mkj , hk) must be greater than ϵ/(8H) for some j ∈ [2] and hk ∈ [H]. Then the algorithm samples additional trajectories at level hk and shrinks the constraint set by eliminating models with large empirical model misfit, which is defined as follow
Ê(Mk1 ,Mk2 ,M, hk) = sup g∈G n∑ i=1 1 n E (rh,xh)∼M [g(xih, a i h, b i h, rh, xh)− g(xih, aih, bih, rih, xih+1)]. (6)
We will show that this constraint set maintains more and more accurate models of the environment. Due to space constraints, the algorithm and theory of our model-based method are deferred to Appendix C.

heading: 4.2 MODEL FREE ALGORITHM
text: In this section we propose a model-free algorithm. We consider a more general agnostic learning, where The algorithm is given a policy class Π = Π1 × · · ·ΠH with Πh ⊂ {πh : S 7→ ∆}, h ∈ [H]. Notice by letting Π to be the class of NE policies induced by the action-value function class F , we recover the original setup. The goal is to find policy π and ν from Π to minimize the duality gap: maxπ′∈Π V π ′,ν − minν′∈Π V π,ν ′ , by playing only policies from Π. Since only policies from Π are considered, we overload the notation and define the optimal solution in Π as π∗ = argmaxπ∈Π minν′∈Π V π,ν′ and ν∗ = argminν∈Π maxπ′∈Π V π ′,ν . When Π contains all possible policies, π∗ and ν∗ is then the Nash equilibrium.
Similar to Section 3, we consider general function class F = F1 × · · · × FH where Fh ⊂ {f : S × A1 × A2 7→ [0, 1]}. We overload the notations in Section 3 and use νfπ to denote the best response of π from Π, namely νfπ(x) := argminν∈Πf(x, π, ν). Similarly, we use πf (x) := argmaxπ∈Πminν∈Π f(x, π, ν). We also use ν ∗ π(x) := argminν∈ΠV
π,ν to denote the best response of π in the true model.

heading: 4.2.1 ALTERNATE OPTIMISTIC VALUE ELIMINATION (AOVE)
text: Notice that the duality gap can be decomposed as follows
gap = V π ∗ ν ,ν − V π ∗ ν∗ ,ν ∗︸ ︷︷ ︸ P2 +V π ∗ ν∗ ,ν ∗ − V π ∗,ν∗π∗︸ ︷︷ ︸ Optimal +V π ∗,ν∗π∗ − V π,ν ∗ π︸ ︷︷ ︸ P1
where the optimal part V π ∗ ν∗ ,ν ∗ − V π∗,ν∗π∗ is fixed. Therefore we can consider only the P1 part here and the P2 follows by symmetry. We are interested in the following policy regret
Reg(K) := K∑ k=1 (V π ∗,ν∗π∗ − V π k,ν∗ πk ).
Policy regret measures the extent that P1 can be exploited by policies in Π. Our algorithm Alternate Optimistic Value Elimination (AOVE), presented in Algorithm 2, works on minimizing this regret. Similar to Algorithm 1, it also uses optimism in the initial state to address exploration and exploitation trade-off and constructs a series of confidence sets of hypotheses with small Bellman errors. The differences primarily lie in a different choice of optimism and a different series of confidence sets constructed with the Bellman operator in Eq 2. Since the policy class Π is taken into consideration, the algorithm maintains a constraint set B ⊂ Π× F of policy-function pairs. We use the Bellman operator with regard to fixed P1’s policy, in Eq (2). Thus intuitively, this constraint set maintains (π, f) pairs such that fh − T πh fh+1 is small for all h ∈ [H]. We apply the ‘alternate optimistic’ principle, presented in Line 5 and Line 6. Intuitively, the algorithm finds an optimistic planning of π and pessimistic planning of ν, together corresponding to a max-min
procedure. As such, we form an upper bound f1(x1, π, νfπ) − g1(x1, πk, ν g πk ) of the duality gap. Note that it is different from the ‘alternate optimistic’ used in model-based settings Wei et al. (2017) in that the hypothesis chosen in Line 6 is constrained by the policy chosen in Line 5. This is because in model-based methods, ‘plausible’ models in the confidence set guarantee small simulation errors (Lemma C.6). However, this is not true for ‘plausible’ value functions in the confidence set.
The rest of the algorithm aims at minimizing this upper bound sequentially by eliminating bad hypothesis in the constraint set. The elimination process occurs in Line 13, where the algorithm uses history data to eliminate functions with large Bellman error. To estimate Bellman error, we use the similar method as in Algorithm 1, i.e. subtracting the variance of T πh fh+1 by g = arg infg∈Fh EDh(g, fh+1, π). Notice that a smaller value of fh−T πh fh+1 indicates that function approximation f is not easily exploited by P2 when P1 plays π.
As shown in Appendix D, (π∗, Q∗) is always in the constraint set, and the Bellman errors of the rest hypothesis keep shrinking. Thus in the presented algorithm of AOVE, the regret of P1 part V π
∗,ν∗π∗ − V π,ν∗π is controlled. By symmetry, we can perform the same procedures on P2 part and obtain an upper bound on V π ∗ ν ,ν − V π∗ν∗ ,ν∗ . Combining these together, we show sublinear regret rate of V π ∗ ν∗ ,ν
∗ − V π∗,ν∗π∗ . By regret to PAC conversion, this means that we find the policies that is the best achievable in Π.
Algorithm 2 Alternate Optimistic Value Elimination (AOVE) 1: Input: Function class F , policy class Π 2: Initialize B0 ← Π×F 3: Set β ← C log[N (F , 1/K) · N (Π, 1/K) ·HK/p] for some large constant C 4: for k = 1, 2, . . . ,K do 5: Find (πk, fk)← argmax(π,f)∈Vk−1f1(x1, π, νfπ) 6: Let g ← argmin
g:(πk,g)∈Vk−1 g1(x1, π
k, νg πk ) and set νk ← νg πk
7: for step h = 1, 2, . . . ,H do 8: P1 takes action akh ∼ πkh(xkh), P2 takes action bkh ∼ νkh(xkh) 9: Observe reward rkh and move to next state x k h+1
10: end for 11: Update Bh ← Bh ∪ {(xkh, akh, bkh, rkh, xkh+1)},∀h ∈ [H] 12: For all ξ, ζ ∈ F , π ∈ Π and h ∈ [H], let
EBh(ξh, ζh+1, π) = k∑
τ=1
[ξh(x τ h, a τ h, b τ h)− rτh − ζh+1(xτh+1, π, νζh+1π )]2
13: Update
Vk ← {(π, f) ∈ Π×F : EBh(fh, fh+1, π) ≤ inf g∈Fh EBh(g, fh+1, π) + β,∀h ∈ [H]}
14: end for

heading: 4.2.2 THEORETICAL RESULTS
text: This section presents our theoretical guarantees of Algorithm 2. First, we introduce two assumptions that take the policy class Π into consideration. Variants of these assumptions are also common in batch RL (Jin et al., 2021c; Xie et al., 2021). Assumption 4.1 (Π-realizability). For all π ∈ Π, Qπ,ν∗π ∈ F . Assumption 4.2 (Π-completeness). For all h ∈ [H], π ∈ Π, and f ∈ Fh+1, T πh f ∈ Fh holds.
Notice that Assumption 4.2 reduces to Q∗ realizability in MDP. Both two assumptions hold for linear-parameterized Markov games studied in Xie et al. (2020). In fact, Xie et al. (2020) satisfies a stronger property: for any policy pair π, ν and any h ∈ [H], there exists a vector w ∈ Rd such that
Qπ,νh (x, a, b) = w ⊤ϕ(x, a, b), ∀(x, a, b) ∈ S ×A1 ×A2.
Now we present the theory of Algorithm 2. First, we introduce the complexity measure in coordinated setting, which is a variant of Minimax Eluder dimension by replacing the Bellman operator Eq (1) with Eq (2). This Minimax Eluder dimension also allows a distribution family induced by function class F which is cheap to evaluate in large state space (Jin et al., 2021a).
Definition 4.3 (Minimax Eluder dimension in Coordinated setting). Let (I − T Πh+1h )F := {fh − T πh fh+1 : f ∈ F , π ∈ Πh+1} be the class of residuals induced by the Bellman operator T πh . Consider the following distribution families: 1) D∆ = {D∆,h}h∈[H] where D∆,h := {δ(x, a, b) : x ∈ S, a ∈ A1, b ∈ A2} is the set of Dirac measures on state-action pair (x, a, b); 2) DF = {DF,h}h∈[H] which is generated by executing (πf , νgπf ) for f, g ∈ F . The ϵ-Minimax Eluder dimension (in coordinated setting) of F is defined by dimME′(F , ϵ) := maxh∈[H] minD∈{D∆,DF} dimDE((I − T Πh+1 h )F ,D, ϵ).
Now we present our main theory of Algorithm 2, where we make use of a variant of Minimax Eluder dimension that depends on policy class Π. We useN (Π, ϵ) to denote the covering number of Π under metric d(π, π′) := maxh∈[H] maxf∈Fh,x∈S,b∈A |f(x, π, b)− f(x, π′, b)|.
Theorem 4.4. Suppose Assumption 4.1 and Assumption 4.2 holds. With probability at least 1− p we have
Reg(K) ≤ O ( H √ KdME′ log[N (F , 1/K)N (Π, 1/K)HK/p] ) where dME′ = dimME′(F , ϵ).
As shown in this theorem, the regret is sub-linear in number of episodes K and Eluder dimension dME′ which match the regret bound in Markov decision process, e.g. in Jin et al. (2021a). Through regret-to-PAC conversion, with high probability the algorithm can find ϵ-optimal policy with O ( H2KdME′ log[N (F , 1/K)N (Π, 1/K)HK/p]/ϵ2 ) sample complexity. When the reward and transition kernel have linear structures, we also recover the Õ( √ d3K) regret of Xie et al. (2020).
Although our upper bound depends on the logarithm of covering number of Π, there are some cases when it is small. For example, when the value-function class F is finite and Π is the induced policy class of F as defined by Π = {πf , νgπf : f, g ∈ F}, then logNΠ(ϵ) = log |F| and the regret is
Õ(H √ KdME′ log
2 |F|). Similarly, if the model classM is finite and Π is induced policy class of M as defined by Π = {πM , νM ′ πM : M,M ′ ∈ M}, then logNΠ(ϵ) = log |M| and the regret
is Õ(H √ KdME′ log
2 |M|). In agnostic setting which allows Π to have arbitrary structure, the term logN (Π, 1/K) reflects the difficulty of learning with complex candidate policy sets and we conjecture that this term is inevitable.
Similar to Algorithm 1, Algorithm 2 solves a non-convex optimization problem in Line 5-6 with highly non-convex constraint set (Line 13). This step is particularly difficult when the function class has complex structures. Algorithm 2 is in general computationally inefficient, even in cases of linear function approximations. Indeed, even when the model is known, solving for the NE is PPAD complete. Developing decentralized and provably efficient RL algorithm for multi-agent Markov game seems a challenging but interesting future direction.

heading: 5 DISCUSSION
text: In this paper we study function approximations in zero-sum simultaneous move Markov games. We design sample efficient algorithms for both decoupled and coordinated learning settings and propose Minimax Eluder dimension to characterize the complexity of decision making with value function approximation. The analysis shows √ T regret bounds and half-order dependence on the Minimax Eluder dimension, matching the results in MDPs and improving the linear function approximations. Our algorithms for coordinated setting are based on the idea of the ‘alternate optimism’, which also shows applicability in model-based methods.

heading: A ADDITIONAL RELATED WORKS
text: There is a rich literature on sample complexity for single agent RL, mostly focusing on the tabular cases (Strehl et al., 2006; Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018; Russo, 2019; Zanette & Brunskill, 2019) and the linear function approximations (Yang & Wang, 2020; Wang et al., 2021; Abbasi-Yadkori et al., 2019; Jin et al., 2020; Du et al., 2019b). For neural network function approximations, Agarwal et al. (2020); Liu et al. (2019); Wang et al. (2020a); Yang et al. (2020) builds provably efficient algorithms on over-parameterized models. The issue is complicated for general function approximation, as the Q function is hard to learn due to the double-sample issue (Baird, 1995). In recent years, a line of work studies the structural properties and corresponding complexity measures that allow generalization in RL. These work can be roughly grouped with two catagories. One studies structures with low information gain. Jiang et al. (2017) proposes Bellman rank and designs a sample efficient algorithm for a large family of MDPs. Later, Sun et al. (2019b) proposes Witness rank and uses this notion to provide a provably efficient model-based RL algorithm. Recently, Du et al. (2021) proposes Bilinear family and the corresponding Bilinear rank that encapsulates a wide variety of structural properties, spanning from both model-based to model-free function approximations. The other studies structures with low Eluder dimension (Russo & Van Roy, 2013). Osband & Van Roy (2014) extends Eluder dimension to reinforcement learning and provides a unified analysis of model based methods where the regret is controlled by the Kolmogorov dimension and Eluder dimension of model function class. Wang et al. (2020b) designs a model-free algorithm and shows that regret can be controlled by the Eluder dimension of the value function class. Recently, Jin et al. (2021a) proposes Bellman Eluder dimension and builds a new framework to capture a large amount of structures. It is noted that although lots of structures, such as linear MDP (Jin et al., 2020), fit in both two viewpoints, they are not equivalent. Among the above work, Jin et al. (2021a); Zanette et al. (2020) are more related. The method of placing uncertainty quantification on only initial states, previously appeared in Zanette et al. (2020); Jin et al. (2021a), greatly simplifies the argument and improves sample complexity. The Minimax Eluder dimension is inspired by the Bellman Eluder dimension in Jin et al. (2021a).
In competitive RL, the setting with access to a sampling oracle or well explored policies is well studied (Littman & Szepesvari, 1996; Greenwald et al., 2003; Grau-Moya et al., 2018; Pérolat et al., 2018; Srinivasan et al., 2018; Sidford et al., 2020). Under these assumptions, many works consider function approximations (Lagoudakis & Parr, 2002; Pérolat et al., 2015; Fan et al., 2020; Jia et al., 2019; Zhao et al., 2021). However, without strong sampling model or a well explored policy, the issue of exploration-exploitation tradeoff must be addressed. Most of these work focus on tabular setting (Wei et al., 2017; Pérolat et al., 2017; Bai & Jin., 2020; Bai et al., 2021; 2020; Zhang et al., 2020; Zhao et al., 2021) or linear function approximation settings (Xie et al., 2020; Chen et al., 2021). Among them, (Wei et al., 2017; Xie et al., 2020) are more related. The regret-decomposition method used in the decoupled setting is inspired by Xie et al. (2020). The ‘alternate optimism’ used in Algorithm 4 was previously used as ‘Maximin-EVI’ in Wei et al. (2017), although the ‘alternate optimism’ used in Algorithm 2 is different. Moreover, the concurrent work of Jin et al. (2021b) studies competitive RL with general function approximation. They reach a sublinear Õ( √ K) regret for MGs with low minimax Eluder dimensions in the decoupled setting. Their results in the coordinated setting are based on different assumptions and complexity measures. Specifically, they assume finite function class and an additional class of exploiters. It is noted that by letting the policy class be the class of optimal policies induced by the value function class, we have |Π| = |F| and our algorithm achieves on-par guarantee in their setup in terms of the covering numbers of function classes. In addition, we propose a first provably sample efficient and model-based algorithm for the coordinated setting with general function approximation.

heading: B PROOF OF THEOREM 3.6
text: We prove the Theorem 3.6 in the following five steps. In the first step, we show that Bellman error is small for function in the constraint set. In the second step, we show that Q∗ stays in the constraint set throughout the algorithm. In the third step, we decompose the regret into a summation of Bellman error and Martingale difference. We can then bound the summation of Bellman error using Minimax Eluder dimension in step 4. Finally we combine the aforementioned steps and complete the proof of Theorem 3.6.
We define ‘optimistic’ value function in step h and episode k as follows
V kh (x k h) := f k h (x k h, π k h, ν̂ k h)
where ν̂kh is the best response of π k h in value function f k, i.e., ν̂kh := argminνf k h (x k h, π k h, ν). We use νk = {νkh}Hh=1 to denote the policy adopted by P2 in the k-th episode. Notice that the agent obtains knowledge from ν only through its actions bkh, h ∈ [H].
Step 1: Low Bellman error in the constraint set We first use a standard concentration procedure (Agarwal et al., 2012; Jin et al., 2021a) to bound the Bellman error in constraint sets. Lemma B.1 (Concentration on Bellman error). Let ρ > 0 be an arbitrary fixed number. With probability at least 1− p for all (k, h) ∈ [K]× [H] we have
k−1∑ i=1 ( fkh (x i h, a i h, b i h)− rih − E x∼P(·|xih,a i h,b i h) fkh+1(x, π k h+1, ν̂ k h+1) )2 ≤ O(β). Proof. Consider a fixed (k, h, f) sample, let
Ut(h, f) := ( fh(x t h, a t h, b t h)− rth −min
ν′ max π′
fh+1(x t h+1, π
′, ν′) )2
− ( Thfh+1(xth, ath, bth)− rth −min
ν′ max π′
fh+1(x t h+1, π
′, ν′) )2
and Ft,h be the filtration induced by {xi1, ai1, bi1, ri1, . . . , xiH} t−1 i=1 ∪ {xt1, at1, bt1, rt1, . . . , xth, ath, bth}. Recall the minimax Bellman operator
Thfh+1(x, a, b) := r(x, a, b) + E x′∼Ph(·|x,a,b) [min ν′ max π′ fh+1(x ′, π′, ν′)].
We have
E[Ut(h, f)|Ft,h] = [(fh − Thfh+1)(xth, ath, bth)] · E[fh(xth, ath, bth) + Thfh+1(xth, ath, bth)− 2rth − 2min
ν′ max π′
fh+1(x t h+1, π ′, ν′)|Ft,h]
= [(fh − Thfh+1)(xth, ath, bth)]2
and
Var[Ut(h, f)|Ft,h] ≤ E[(Ut(h, f))2|Ft,h] = [(fh − Thfh+1)(xth, ath, bth)]2
· E[ ( fh(x t h, a t h, b t h) + Thfh+1(xth, ath, bth)− 2rth − 2min
ν′ max π′
fh+1(x t h+1, π ′, ν′) )2|Ft,h]
≤ 36[(fh − Thfh+1)(xth, ath, bth)]2 = 36E[Ut(h, f)|Ft,h].
By Freedman’s inequality, we have with probability at least 1− p,∣∣∣∣∣ k∑
t=1
Ut(h, f)− k∑
t=1
E[Ut(h, f)|Ft,h] ∣∣∣∣∣ ≤ O (√√√√log(1/p) k∑
t=1
E[Ut|Ft,h] + log(1/p) ) .
Let N (F , ρ) be a ρ-cover of F . Taking a union bound for all (k, h, g) ∈ [K] × [H] ×N (F , ρ), then with probability at least 1− p for all (k, h, g) ∈ [K]× [H]×N (F , ρ)∣∣∣∣∣ k∑ t=1 Ut(h, g)− k∑ t=1 [(gh − Thgh+1)(xth, ath, bth)]2 ∣∣∣∣∣
≤ O (√√√√ι k∑
t=1
[(gh − Thgh+1)(xth, ath, bth)]2 + ι )
(7)
where ι = log(HK|N (F , ρ)|/p). Let gk = argming∈N (F,ρ) maxh∈[H] ∥fkh − gkh∥∞. We immediately have ∣∣∣∣∣ k∑ t=1 Ut(h, g k)− k∑ t=1 [(gkh − Thgkh+1)(xth, ath, bth)]2 ∣∣∣∣∣
≤ O (√√√√ι k∑
t=1
[(gkh − Thgkh+1)(xth, ath, bth)]2 + ι ) . (8)
For all (h, k) ∈ [H]× [K], by the definition of Vk and fk ∈ Vk we have k∑
t=1
Ut(h, f k) = k∑ t=1 ( fkh (x t h, a t h, b t h)− rth −min ν′ max π′ fh+1(x t h+1, π ′, ν′) )2
− k∑
t=1
( Thfkh (xth, ath, bth)− rth −min
ν′ max π′
fh+1(x t h+1, π
′, ν′) )2
≤ k∑
t=1
( fkh (x t h, a t h, b t h)− rth −min
ν′ max π′
fh+1(x t h+1, π
′, ν′) )2
− inf g∈F k∑ t=1 ( gh(x t h, a t h, b t h)− rth −min ν′ max π′ fh+1(x t h+1, π ′, ν′) )2
≤ O(ι+ kρ). (9)
It thus follows that,
k∑ t=1 [(fkh − Thfkh+1)(xth, ath, bth)]2 ≤ k∑ t=1 [(gkh − Thgkh+1)(xth, ath, bth)]2 +O(ι+ kρ)
≤ O( k∑
t=1
Ut(h, g k) + ι+ kρ)
≤ O( k∑
t=1
Ut(h, f k) + ι+ kρ)
≤ O(ι+ kρ)
where the first step is due to gk is an ρ-approximation to fk, the second step comes from Eq (8), the third step is due to gk is an ρ-approximation to fk, and the final step comes from Eq (9).
By definition of πk and ν̂k, we have
Thfkh+1(x, a, b) := r(x, a, b) + E x′∼Ph(·|x,a,b) [fh+1(x ′, πkh+1, ν̂ k h+1)]
thus we conclude the proof.
Step 2: Q∗ is always in constraint set. Lemma B.2. With probability at least 1− p, we have Q∗ ∈ Vk for all k ∈ [K].
Proof. Consider a fixed (k, h, f) sample, let Ut(h, f) := ( fh(x t h, a t h, b t h)− rth −min
ν′ max π′
Q∗h+1(x t h+1, π
′, ν′) )2
− ( Q∗h(x t h, a t h, b t h)− rth −min
ν′ max π′
Q∗h+1(x t h+1, π
′, ν′) )2
and Ft,h be the filtration induced by {xi1, ai1, bi1, ri1, . . . , xiH} t−1 i=1 ∪ {xt1, at1, bt1, rt1, . . . , xth, ath, bth}.
We have
E[Ut(h, f)|Ft,h] = [(fh −Q∗h)(xth, ath, bth)]2
and
Var[Ut(h, f)|Ft,h] ≤ 36[(fkh − Thfkh+1)(xth, ath, bth)]2 = 36E[Ut(h, f)|Ft,h].
Let N (F , ρ) be a ρ-cover of F . By Freedman’s inequality, for all (k, h, f) ∈ [K]× [H]×N (F , ρ) we have with probability at least 1− p,∣∣∣∣∣ k∑ t=1 Ut(h, f)− k∑ t=1 [(fh −Q∗h)(xth, ath, bth)]2 ∣∣∣∣∣
≤ O (√√√√log(1/p) k∑
t=1
[(fh −Q∗h)(xth, ath, bth)]2 +O(ι) )
where ι = log(HK|N (F , ρ)|/p). Since [(fh −Q∗h)(xth, ath, bth)]2 ≥ 0, this implies
− k∑
t=1
Ut(h, g) ≤ O(ι).
Therefore for all (k, h, g) ∈ [K]× [H]×N (F , ρ) k∑
t=1
( Q∗h(x t h, a t h, b t h)− rth −min
ν′ max π′
Q∗h+1(x t h+1, π
′, ν′) )2
≤ k∑
t=1
( fh(x t h, a t h, b t h)− rth −min
ν′ max π′
Q∗h+1(x t h+1, π
′, ν′) )2 +O(ι+ kρ).
Thus we have proven that Q∗ ∈ Vk,∀k ∈ [K] with probability at least 1− p.
Remark B.3. This step implies that
V ∗ ≤ V k1 (xk1) (10)
which ensures optimism from the beginning state (‘global optimism’).
Step 3: Regret decomposition The following result is key to our analysis. It decomposes the deviation from the value of the game into Bellman errors across time steps and a martingale difference sequence.
Lemma B.4. Define
δkh := V k h (x k h)− V
πk,νk
h (x k h)
ζkh := E[δkh+1|xkh, akh, bkh]− δkh+1 γkh := E
a∼πkh(x k h) [fkh (x k h, a, b k h)]− fkh (xkh, akh, bkh)
γ̂kh := E a∼πkh(x k h),b∼ν k h(x k h) [Qπ
k,νk
h (x k h, a, b)]−Q
πk,νk h (x k h, a k h, b k h)
Then we have
δkh ≤ δkh+1 − ζkh + γkh − γ̂kh + ϵkh (11)
where ϵkh is the bellman error defined by
ϵkh := f k h (x k h, a k h, b k h)− rkh − E
x∼P(·|xkh,a k h,b k h) fkh+1(x, π k h+1, ν̂ k h+1).
Proof. By definition of ν̂kh = argminνf k h (x k h, π k h, ν), we have
fkh (x k h, π k h, ν̂ k h) ≤ fkh (xkh, πkh, bkh)
= fkh (x k h, a k h, b k h) + γ k h.
It thus follows that
δkh ≤ fkh (xkh, akh, bkh)−Q πk,νk h (x k h, a k h, b k h) + γ k h − γ̂kh
= rkh + E x∼P(·|xkh,a k h,b k h) fkh+1(x, π k h+1, ν̂ k h+1) + ϵ k h
− (rkh + E x∼P(·,xkh,a k h,b k h) [V π
k,νk
h+1 (x)|x k h, a k h, b k h]) + γ k h − γ̂kh
= fkh (x k h+1, π k h+1, ν̂ k h+1)− V
πk,νk
h+1 (x k h+1)− ζkh + ϵkh + γkh − γ̂kh
= δkh+1 − ζkh + γkh − γ̂kh + ϵkh.
Therefore we complete the proof.
Step 4: Bounding cumulative Bellman error using Minimax Eluder dimension. Recall that Lemma B.1 gives:
k−1∑ i=1 ( fkh (x i h, a i h, b i h)− rih − E x∼P(·|xih,a i h,b i h) fkh+1(x, π k h+1, ν̂ k h+1) )2 ≤ O(β). Combining this and Lemma F.1 with
gk = f k h (·, ·, ·)− rkh − E x∼P(·|·,·,·) fkh+1(x, π k h+1, ν̂ k h+1)
and ρk = δ(xkn, a k h, b k h), we have come to the following result.
Lemma B.5. For any (k, h) ∈ [K]× [H] we have K∑
k=1
|fkh (xkh, akh, bkh)− rkh − E x∼P(·|xkh,a k h,b k h) fkh+1(x, π k h+1, ν̂ k h+1)|
≤ O (√ K · dimME(F , √ 1/K) log(HKN (F , 1/K)/p) ) .
Thus K∑
k=1
ϵkh ≤ O (√ K · dimME(F , √ 1/K) log(HKN (F , 1/K)/p) ) . (12)
Step 5: Putting everything together By Eq (10) and Eq (11)
K∑ k=1 [V ∗1 (x1)− V πk,νk 1 (x1)] ≤ K∑ k=1 [V k1 (x1)− V πk,νk 1 (x1)]
≤ K∑
k=1 H∑ h=1 (−ζkh + γkh − γ̂kh + ϵkh)
= H∑ h=1 K∑ k=1 (−ζkh + γkh − γ̂kh) + H∑ h=1 K∑ k=1 ϵkh.
Notice that ∑H
h=1 ∑K k=1(−ζkh + γkh − γ̂kh) is a martingale difference sequence and can be bounded
by O(H √ KH log(HK/p)) with probability at least 1− p.
By Eq (12) the term ∑H
h=1 ∑K k=1 ϵ k h can be bounded by
O ( H √ K · dimME(F , √ 1/K) log(HKN (F , 1/K)/p) ) with probability at least 1− p. It thus follows that regret can be bounded by
Reg(K) ≤ O ( H √ K · dimME(F , √ 1/K) log(HKN (F , 1/K)/p) ) .
B.1 LINEAR FUNCTION APPROXIMATION
In the linear function approximation setting of Xie et al. (2020),
rh(x, a, b) = ϕ(x, a, b) ⊤θh, Ph(·|x, a, b) = ϕ(x, a, b)⊤µh(·)
where ϕ(·, ·, ·) ∈ Rd is known feature vector and θh ∈ Rd and µh(·) ∈ Rd are unknown with ∥θ∥2 ≤ √ d, ∥νh(·)∥2 ≤ √ d and ∥ϕ(·, ·)∥2 ≤ 1. In this case Algorithm 1 reduces to the following Algorithm 3. Notice that this algorithm can also be seen as a generalization of Zanette et al. (2020) to Markov games.
Algorithm 3 ONEMG for linear function approximation. 1: Input: Function class F 2: Set β ← C √ d log(HK/p) for some large constant C
3: for episode k = 1, 2, . . . ,K do 4: Receive initial state xk1 5: Set wkH+1 = θ k H+1 = 0 6: Find maxwkh,θkh,h∈[H] V k 1 (x k 1) such that for all h ∈ [H]:
(1) wkh = (Λ k h) −1 k−1∑ τ=1 ϕ(xτh, a τ h, b τ h)[r τ h + V k h+1(x τ h+1)]
(2) ∥θkh − wkh∥Λkh ≤ C ·Hβ (3) Qkh(·, ·, ·) = (θkh)⊤ϕ(·, ·, ·) (4) (πkh, B0) = NE(Q k h)
(5) V kh (·) = E a∼πkh,b∼B0 [Qkh(·, a, b)]
7: for step h = 1, 2, . . . ,H do 8: P1 plays action akh ∼ πkh(xkh) 9: P2 takes action bkh
10: Observe reward rkh and move to next state x k h+1 11: end for 12: end for
We will prove the following theoretical result of Algorithm 3. Notice the dependency on d of Algorithm 3 is d while the dependency on d of Xie et al. (2020) is d3/2, thus this result improves theirs by √ d factor.
Theorem B.6. Regret (Eq (3)) in Algorithm 3 is bounded by O(d √
H2K log(dHK/p)) with probability at least 1− p.
B.1.1 PROOF OF THEOREM B.6
We prove Theorem B.6 in the following five steps similar to the previous section.
Step 1: Low Bellman error in the constraint set We use some standard results from previous work. Notice that the N (F , ϵ) = O(d log(1/ϵ)) and our inherent Bellman error is zero, thus these lemmata can be directly adapted into our setting.
Lemma B.7 (Concentration, adapted from Lemma 1 of Zanette et al. (2020)). With probability at least 1− p, the following holds for all (k, h) ∈ [K]× [H],∥∥∥∥∥∥ ∑ τ∈[k−1] ϕτh[V k h+1(x τ h+1)− E x∼P(·|xτh,a τ h,b τ h) V kh+1(x)] ∥∥∥∥∥∥ (Λkh) −1 ≤ Hβ
where β = Ω( √ d log(dKH/p)).
Lemma B.8 (Least square error bound, adapted from Lemma 3 of Xie et al. (2020)). On the event of Lemma B.7, the following holds for all (x, a, b, h, k) ∈ S ×A×A× [H]× [K] and any policy pair (π, ν)∣∣∣∣⟨ϕ(x, a, b), θkh⟩ −Qπ,νh (x, a, b)− Ex∼P(·|x,a,b)(V kh+1 − V π,νh+1)(x)
∣∣∣∣ ≤ β∥ϕ(x, a, b)∥(Λkh)−1 Step 2: Q∗ always stays in the constraint set Lemma B.9 (Optimism). Let Q∗h(·, ·, ·) = ϕ(·, ·, ·)⊤θ∗h, then on the event of Lemma B.8 and Lemma B.7 there exists w∗h, h ∈ [H] such that w∗h, θ∗h, h ∈ [H] satisfies the constraints of Line 6 in Algorithm 3.
Proof. We prove by backward induction on h. The claim trivially holds for h = H +1. Now assume the inductive hypothesis holds at h+ 1. Let
w∗h = (Λ k h) −1 k−1∑ τ=1 ϕ(xτh, a τ h, b τ h)[r τ h + V k h+1(x τ h+1)]
= ( k−1∑ τ=1 ϕτh(ϕ τ h) ⊤ + I)−1 k−1∑ τ=1 ϕτh(r τ h + E x∼P(·|xτh,a τ h,b τ h) V kh+1(x) + η τ h)
where ϕτh = ϕ(x τ h, a τ h, b τ h) and η τ h = V k h+1(x τ h+1)− Ex∼P(·|xτh,aτh,bτh) V k h+1(x). Notice that inductive hypothesis implies rτh + Ex∼P(·|xτh,aτh,bτh) V k h+1(x) = ϕ(x τ h, a τ h, b τ h) ⊤θ∗h, therefore
w∗h = ( k−1∑ τ=1 ϕτh(ϕ τ h) ⊤ + I)−1 k−1∑ τ=1 ϕτh ( (ϕτh) ⊤θ∗h + η τ h ) = θ∗h − (Λkh)−1θ∗h + (Λkh)−1
k−1∑ τ=1 ϕτhη τ h.
It thus suffices to bound the following
∥(Λkh)−1θ∗h + (Λkh)−1 k−1∑ τ=1 ϕτhη τ h∥(Λkh) ≤ ∥θ ∗ h∥(Λkh)−1 + ∥ k−1∑ τ=1 ϕτhη τ h∥(Λkh)−1
≤ √ d+Hβ
≤ C ·Hβ
where the penultimate step comes from ∥θ∗h∥2 ≤ √ d and Lemma B.7.
Remark B.10. This fact implies that
V ∗(xk1) ≤ V k1 (xk1). (13)
Step 3: Recursive decomposition of regret Lemma B.11 (Regret decomposition). Define
δkh := V k h (x k h)− V
πk,νk
h (x k h)
ζkh := E[δkh+1|xkh, akh, bkh]− δkh+1 γkh := E
a∼πkh(x k h) [Qkh(x k h, a, b k h)]−Qkh(xkh, akh, bkh)
γ̂kh := E a∼πkh(x k h),b∼ν k h(x k h) [Qπ
k,νk
h (x k h, a, b)]−Q
πk,νk h (x k h, a k h, b k h)
Then we have
δkh ≤ δkh+1 − ζkh + γkh − γ̂kh + ϵkh (14)
where ϵkh is the width defined by ϵkh := 2β √ (ϕkh) ⊤(Λkh) −1ϕkh.
Proof. By definition of B0 = argminνf k h (x k h, π k h, ν), we have
V kh (x k h) = Q k h(x k h, π k h, B0)
≤ Qkh(xkh, πkh, bkh) = Qkh(x k h, a k h, b k h) + γ k h.
It thus follows that
δkh ≤ Qkh(xkh, akh, bkh)−Q πk,νk h (x k h, a k h, b k h) + γ k h − γ̂kh
≤ E x∼P(·|xkh,a k h,b k h) [V kh+1(x)]− E x∼P(·|xkh,a k h,b k h) [V π
k,νk
h+1 (x)] + ϵ k h + γ k h − γ̂kh
= V kh+1(x k h+1)− V
πk,νk
h+1 (x k h+1)− ζkh + ϵkh + γkh − γ̂kh
= δkh+1 − ζkh + γkh − γ̂kh + ϵkh
where the second step comes from Lemma B.8 by letting (x, a, b) = (xkh, a k h, b k h) (notice that ⟨ϕ(xkh, akh, bkh), θkh⟩ = Qkh(xkh, akh, bkh)).
Step 4: Bounding width by Elliptical Potential Lemma This step directly makes use of the following standard result. Lemma B.12 (Elliptical Potential Lemma, Lemma 10 of Xie et al. (2020)). Suppose {ϕt}t≥0 is a sequence in Rd satisfying ∥ϕt∥ ≤ 1,∀t. Let Λ0 ∈ Rd×d be a positive definite matrix, and Λt = Λ0 + ∑ i∈[t] ϕiϕ ⊤ i . If the smallest eigenvalue of Λ0 is lower bounded by 1, then
log( detΛt detΛ0 ) ≤ ∑ i∈[t] ϕ⊤i Λ −1 j−1ϕi ≤ 2 log( detΛt detΛ0 ).
Step 5: Putting everything together By Eq (13) and Eq (14) K∑
k=1
[V ∗1 (x1)− V πk,νk 1 (x1)] ≤ K∑
k=1
[V k1 (x1)− V πk,νk 1 (x1)]
≤ K∑
k=1 H∑ h=1 (−ζkh + γkh − γ̂kh + ϵkh)
= H∑ h=1 K∑ k=1 (−ζkh + γkh − γ̂kh) + H∑ h=1 K∑ k=1 ϵkh.
Notice that ∑H
h=1 ∑K k=1(−ζkh + γkh − γ̂kh) is a martingale difference sequence and can be bounded
by H √ KH log(HK/p) with probability at least 1− p.
By Lemma B.12 the term ∑H
h=1 ∑K k=1 ϵ k h can be bounded as follows
H∑ h=1 K∑ k=1 ϵkh = H∑ h=1 K∑ k=1 2β √ (ϕkh) ⊤(Λkh) −1ϕkh
≤ H∑
h=1
√ K · √√√√ K∑ k=1 2β(ϕkh) ⊤(Λkh) −1ϕkh
≤ 2β H∑
h=1
√ K · √ 2 log(
detΛkh detΛ0h )
≤ 2β H∑
h=1
√ K · √ 2 log
(λ+Kmaxk ∥ϕkh∥2)d λd
≤ O(dH √ K log(dHK/p)).
with probability at least 1− p. It thus follows that with probability at least 1− p regret can be upper bounded by
O(d √ H2K log(dHK/p)).

heading: C MODEL-BASED METHOD FOR THE COORDINATED SETTING
text: C.1 ALTERNATE OPTIMISTIC MODEL ELIMINATION (AOME)
Algorithm 4 Alternate Optimistic Model Elimination (AOME) 1: Input: Model classM, test function class G, precision ϵ, failure probability p 2: InitializeM0 ←M 3: for k = 1, 2, . . . ,K do 4: Find Mk1 ← argmaxM∈MQM (x1, πM , νM ), let πk ← πM k 1
5: Find Mk2 ← argminM∈MQM (x1, πk, νMπk), let ν k ← νM
k 1
πk
6: Execute πk, νk and collect n1 rewards {rih}h∈[H],i∈[n1] 7: Let V̂ k ← 1n1 ∑n1 i=1( ∑H h=1 r i h) 8: if max{|V̂ k −QMk1 (x1, πk, νk)|, |V̂ k −QM k 2 (x1, π
k, νk)|} ≤ ϵ/2 then 9: Terminate and output πk, νk.
10: else 11: Find hk such that maxi∈[2] |L̂(Mk1 ,Mk2 ,Mki , hk)| ≥ ϵ/(4H) by Eq (5). 12: Collect n trajectories {(xih, aih, bih, rih)Hh=1}ni=1 by executing ah, bh ∼ πkh, νkh ,∀h ∈ [H] 13: Update constraint set, where Ê is given by Eq (6)
Mk ← {M ∈Mk−1 : Ê(Mk1 ,Mk2 ,M, hk) ≤ ϕ}
14: end if 15: end for
C.2 THEORY FOR ALTERNATE OPTIMISTIC MODEL ELIMINATION (AOME)
In this section we prove that Algorithm 4 terminates in finite rounds. The technique bulk is then showing that in Step 13 the constraint set can only shrink for finite times. This is dependent on the complexity of model classM and discriminator function class G. We first generalize Witness rank (Sun et al., 2019b) to Markov games.
Definition C.1 (Witnessed model misfit in Markov games). For discriminator class G : S ×A1 × A2×R×S 7→ R, models M1,M2,M ∈M and level h ∈ [H], the witnessed model misfit of Markov game at level h is defined as follow E(M1,M2,M, h) := sup
g∈G E
(x,a,b)∼PM2M1
E (r,x)∼M [g(xh, ah, bh, r, x)− g(xh, ah, bh, rh, xh+1)]. (15)
where (x, a, b) ∼ PM2M1 denotes xτ+1 ∼ P(·|xτ , aτ , bτ ), aτ ∼ π M1 and bτ ∼ νM2πM1 for all τ ∈ [h].
Using g(xh, ah, bh, r, x) = r(xh, ah, bh) +QM (x, πM1 , νM2πM1 ), we can also give a generalization of Bellman error (Jiang et al., 2016) in Markov games by the following
L(M1,M2,M, h) := E (x,a,b)∼PM2M1
[ E
(r,x)∼M [g(xh, ah, bh, r, x))]− E (r,x)∼M∗ [g(xh, ah, bh, r, x)]
] .
(16)
The final components in our theory are two assumptions from Sun et al. (2019b). Define rank(A, β) to be the smallest integer k such that A = UV ⊤ with U, V ∈ Rn×k and ∥Ui,∗∥2 · ∥Vj,∗∥2 ≤ β for any pair of rows Ui,∗, Vj,∗. Assumption C.2 (Realizability). Assume M∗ ∈M. Assumption C.3 (Witness misfit domination). Assume G is finite, ∥g∥∞ ≤ 2,∀g ∈ G and ∀M1,M2,M ∈M : E(M1,M2,M, h) ≥ L(M1,M2,M, h).
Now we introduce the Witness rank for Markov games. Definition C.4 (Witness rank for Markov games). Given a model classM, a test function class G and κ ∈ (0, 1]. For h ∈ [H], we define Nκ,h ⊂ R|M|
2×|M| as the set of matrices such that any matrix A ∈ Nκ,h satisfies
κ|L(M1,M2,M, h)| ≤ A((M1,M2),M) ≤ E(M1,M2,M, h), ∀M1,M2,M ∈M. The Witness rank for Markov games is defined by
W (κ, β,M,G, h) := min A∈Nκ,h rank(A, β).
We are in the position to state the main theorem of this section. Theorem C.5. Under Assumption C.2 and Assumption C.3, set ϕ = κϵ
100H √ Wκ where Wκ = maxh∈[H] W (κ, β,M,G, h), let T = HWκ log(β/2ϕ), set n1 = C ·H2 log(HT/p)/ϵ2 and n = C ·H2Wκ|A| log(T |M||G|/p)/(κϵ)2 for large enough constant C. Then for all ϵ, p, κ ∈ (0, 1], with probability at least 1− p Algorithm 4 outputs a policy π such that V ∗(x1)− V π,ν ∗ π (x1) ≤ ϵ within at most O(H 3W 2κ |A| κ2ϵ2 log(T |G||M|/p)) trajectories.
As seen in the above theorem, Algorithm 4 has sample complexity that scales quadratic with Witness rank and logarithmically with cardinality of model class. This matches the sample complexity results in the Markov decision process setting (Sun et al., 2019b). When the test function is Q-function, the Witnessed model misfit reduced to Bellman error as seen in Eq (16) and witness rank reduce to Bellman rank.
C.3 PROOFS
We prove Theorem C.5 in the following steps. In the first step, we show a simulation lemma that generalize Jiang et al. (2017) to Markov games. In the second step we show concentration of empirical estimates of Bellman error, model misfit and value functions. In the third step we show that M∗ always stays in the constraint set. We examine the conditions when Algorithm 4 terminates or not in the fourth step. Using these conditions, we bound the number of rounds in the fifth step. Finally we combine everything and complete the proof of Theorem C.5.
From Definition C.4 we know that there exists Ah ∈ Nκ,h such that κ|L(M1,M2,M, h)| ≤ Ah((M1,M2),M) ≤ E(M1,M2,M, h), ∀M1,M2,M ∈M.
and we can factorize Ah((M1,M2),M) = ⟨ζh(M1,M2), χh(M)⟩ where ∥ζh(M1,M2)∥2, ∥χh(M)∥2 ≤ β.
Step 1: Simulation Lemma The analysis begins with a useful Lemma that decouples the value difference into a sum of Bellman errors across time steps.
Lemma C.6 (Simulation Lemma). Fix model M1,M2,M ∈ M. Let π = πM1 , ν = νM2πM1 . Under Assumption C.3, we have
QM (x1, π, ν)− V π,ν1 (x1) = H∑
h=1
L(M1,M2,M, h)
Proof. Let (x, a, b) ∼ PM2M1 denote xτ+1 ∼ P(·|xτ , aτ , bτ ), aτ ∼ π M1 and bτ ∼ νM2πM1 for all τ ∈ [h]. Using definition of Bellman error in Eq (16), we have QM (x1, π, ν)− V π,ν1 (x1)
= E (x,a,b)∼PM2M1
[ E
(r1,x2)∼M [r1 +QM (x2, π, ν)]− E (r1,x2)∼M∗ [r1 +QM∗(x2, π, ν)] ] = E
(x,a,b)∼PM2M1
[ E
(r1,x2)∼M [r1 +QM (x2, π, ν)]− E (r1,x2)∼M∗ [r1 +QM (x2, π, ν)] ] + E
(x,a,b)∼PM2M1
[ E
(r1,x2)∼M∗ [r1 +QM (x2, π, ν)]− E (r1,x2)∼M∗ [r1 +QM∗(x2, π, ν)] ] = L(M1,M2,M, 1) + E
(x,a,b)∼PM2M1
[QM (x2, π, ν)− V π,ν2 (x2)]
= · · ·
= H∑ h=1 L(M1,M2,M, h).
We thus complete the proof.
Step 2: Concentrations In this part we show some standard concentration results. Lemma C.7. With probability at least 1− p, we have the following event
1. ∣∣∣E(Mk1 ,Mk2 ,M, h)− Ê(Mk1 ,Mk2 ,M, h)∣∣∣ ≤ ϕ for all M ∈M and h ∈ [H],
2. ∣∣∣L̂(Mk1 ,Mk2 ,Mki , h)− L(Mk1 ,Mk2 ,Mki , h)∣∣∣ ≤ ϵ8H for all h ∈ [H] and i ∈ [2],
3. ∣∣∣V πk,νk − V̂ k∣∣∣ ≤ ϵ/8
holds for all k ≤ T rounds.
Proof. Fix one iteration. By Hoeffding’s inequality, with probability at least 1− p/3,∣∣∣L̂(Mk1 ,Mk2 ,Mki , h)− L(Mk1 ,Mk2 ,Mki , h)∣∣∣ ≤ √ log(2H/p)
n1 . (17)
Thus (2) follows from n1 = C ·H2 log(HT/p)/ϵ2 and union bound on all T iterations. Similarly we can verify (3). For (1), fix model M ∈M and g ∈ G, by Hoeffding’s inequality, with probability at least 1− p/3, ∣∣∣ E
(x,a,b)∼PM2M1
E (r,x)∼M [g(xh, ah, bh, r, x)− g(xh, ah, bh, rh, xh+1)] (18)
− n∑
i=1
1 n E (r,x)∼M [g(xih, a i h, b i h, r, x
′)− g(xih, aih, bih, rih, xih+1)] ∣∣∣ (19)
≤ √ log(2/p)
n . (20)
Thus (1) follows from n = C ·H2Wκ|A| log(T |M||G|/p)/(κϵ)2 and union bound on all k ∈ [T ], M ∈M and g ∈ G. We complete the proof.
Step 3: M∗ stays in the constraint set while it shrinks In this step, we show that the constraint set always contains the true environment. The result is displayed in the following. Lemma C.8. Suppose for each round k, the event in Lemma C.7 holds. Then M∗ ∈ Mk for all k. Furthermore, let M̂k = {M ∈ M̂k−1 : Ahk(Mk1 ,Mk2 ,M) ≤ 2ϕ} with M̂0 = M. We have Mk ⊂ M̂k for all k.
Proof. Since E(Mk1 ,Mk2 ,M∗, h) = 0,∀h ∈ [H], we have Ê(Mk1 ,Mk2 ,M∗, hk) ≤ E(Mk1 ,Mk2 ,M∗, hk) + ϕ ≤ ϕ, Thus M∗ is not eliminated. We prove the second result by induction. Firstly M̂0 = M0. Assume Mk−1 ⊂ M̂k−1. For all M ∈ Mk, we have Ahk(M k 1 ,M k 2 ,M) ≤ E(Mk1 ,Mk2 ,M, hk) ≤ Ê(Mk1 ,Mk2 ,M, hk) + ϕ ≤ 2ϕ by Line 13 of Algorithm 4. Therefore M ∈ M̂k, we complete the proof.
Step 4: Terminate or rank increase The following Lemma is key to the ‘alternate pessimism principle’. Intuitively, it indicates that the algorithm either terminates and outputs a pair of policies with small duality gap, or detects a time step that provides useful information (large Bellman error). Lemma C.9. Suppose for round k, the event in Lemma C.7 holds and M∗ is not eliminated. Then if the algorithm terminate, it outputs a policy pair πk such that V ∗(x1)− V π k,ν∗ πk (x1) ≤ ϵ; otherwise Ahk((M k 1 ,M k 2 ),M k i ) ≥ κϵ8H for some i ∈ [2].
Proof. Consider the situation that the algorithm does not terminate. Then with out loss of generality we can assume |V̂ k −QMk1 (x1, πk, νk)| ≥ ϵ/2. By Lemma C.7 and Lemma C.6, we have∣∣∣∣∣ H∑ h=1 L(Mk1 ,Mk2 ,Mk1 , h) ∣∣∣∣∣ = |QM (x1, π, ν)− V π,ν1 (x1)| ≥ |V̂ k −QM k 1 (x1, π k, νk)| − ∣∣∣V πk,νk − V̂ k∣∣∣
≥3ϵ/8.
By pigeonhole principle, these exists h ∈ [H] such that |L(Mk1 ,Mk2 ,Mk1 , h)| ≥ 3ϵ8H . For this h we have |L̂(Mk1 ,Mk2 ,Mk1 , h)| ≥ 3ϵ8H − ϵ 8H = ϵ 4H , thus the h
k in Line 11 is well defined and we have |L̂(Mk1 ,Mk2 ,Mk1 , hk)| ≥ ϵ/(4H). Using Lemma C.7 again, we have
Ahk((M k 1 ,M k 2 ),M k i ) ≥ κ · |L(Mk1 ,Mk2 ,Mk1 , hk)| ≥
κϵ
8H .
If the algorithm terminates, we have
QM k 1 (x1, π k, νk) ≥ QM k 1 (x1, π k, ν Mk1 πk ) ≥ V ∗(x1)
and QM k 2 (x1, π k, νk) ≤ V π k,ν∗ πk (x1). Therefore
V ∗(x1)− V π k,ν∗ πk (x1) ≤ QM k 1 (x1, π k, νk)−QM k 2 (x1, π k, νk)
≤ |QM k 1 (x1, π k, νk)− V̂ π k,νk |+ |V̂ π k,νk −QM k 2 (x1, π k, νk)| ≤ ϵ.
We thus complete the proof.
Step 5: Bounding the number of iterations. This step uses the technique of Jiang et al. (2017); Sun et al. (2019a), which uses the volume of minimum volume enclosing ellipsoid as a potential function to bound the number of iterations. The key result is presented in Lemma C.10. Lemma C.10. Suppose for every round k, the event in Lemma C.7 holds, then the number of iterations of Algorithm 4 is at most HWκ log( β2ϕ )/ log(5/3) for certain i ∈ [2].
Proof. If the algorithm does not terminate at round k, then by Lemma C.9, ⟨ζhk(Mk1 ,Mk2 ), χhk(Mki )⟩ = Ahk((Mk1 ,Mk2 ),Mki ) ≥ κϵ8H = 6 √ Wκϕ. Let Okh denote the origin-centered minimum volume enclosing ellipsoid of {χh(M) : M ∈ M̂k}. Let Ok−1,+h denote the origin-centered minimum volume enclosing ellipsoid of {v ∈ Ok−1h : ⟨ζhk(Mk1 ,Mk2 ), v⟩ ≤ 2ϕ}. By Lemma F.2, we have
vol(Okhk)
vol(Ok−1 hk
) ≤
vol(Ok−1,+ hk )
vol(Ok−1 hk
) ≤ 3/5.
Define Φ = supM1,M2∈M,h∈[H] ∥ζh(M1,M2)∥2 and Ψ = supM∈M,h∈[H] ∥χh(M)∥2. Then we have vol(O0h) ≤ VWκ(1) ·ΨWκ where VWκ(R) is the volume of Euclidean ball in RWκ with radius R. On the other hand, we have
vol(Okh) ≥ vol({q ∈ RWκ : ∥q∥2 ≤ 2ϕ/Φ}) ≥ VWκ(1) · (2ϕ/Φ)Wκ .
It thus follows that the number of iterations for each h is at most Wκ log(ΦΨ2ϕ )/ log(5/3). Using β ≥ ΦΨ, this completes the proof.
Step 6: Putting everything together. From Lemma C.7, with high probability the events holds. Therefore for the first T rounds, we can apply Lemma C.10 and know that the algorithm indeed terminates in at most T rounds. The number of trajectories is thus upper bounded by (n1 + n)T = O(
H3W 2κ |A| κ2ϵ2 log(T |G||M|/p)).

heading: D THEORY FOR ALTERNATE OPTIMISTIC VALUE ELIMINATION (AOVE)
text: We prove Theorem 4.4 in the following five steps. In the first step we show that the functions in the constraint set has low Bellman error. Notice that different from Lemma B.1, here we consider a different Bellman operator in Eq (2) and consider all policies in policy class Π. In the second step we show that Qπ,ν ∗ π belongs to the constraint set for all π ∈ Π and in particular Q∗ belongs to the constraint set. In the third step we perform a regret decomposition. Notice that here we consider two Bellman errors. We then bound the summation of these Bellman errors by Minimax Eluder dimension in step 4 and complete the proof in step 5.
Step 1: Low Bellman errors in the constraint set.
Lemma D.1 (Concentration on Bellman error). Let ρ > 0 be an arbitrary fixed number. With probability at least 1− p for all (k, h) ∈ [K]× [H] we have
(a) k−1∑ i=1 ( fkh (x i h, a i h, b i h)− rih − E x∼P(·|xih,a i h,b i h) fkh+1(x, π k h+1, (ν fk πk )h+1)) )2 ≤ O(β) (b)
k−1∑ i=1 ( gkh(x i h, a i h, b i h)− rih − E x∼P(·|xih,a i h,b i h) gkh+1(x, π k h+1, (ν gk πk )h+1)) )2 ≤ O(β) Proof. For simplicity we only proof (a), and (b) follows similarly.
Consider a fixed (k, h, f, π) tuple, let
Ut(h, f, π) := ( fh(x t h, a t h, b t h)− rth − fh+1(xth+1, π, νfπ) )2 − ( rth + E
x∼P(·|xth,a t h,b t h) fh+1(x, π, ν
f π)− rth − fh+1(xth+1, π, νfπ) )2 and Ft,h be the filtration induced by {xi1, ai1, bi1, ri1, . . . , xiH} t−1 i=1 ∪ {xt1, at1, bt1, rt1, . . . , xth, ath, bth}.
We have
E[Ut(h, f, π)|Ft,h] = [(fh(x t h, a t h, b t h)− rth − E
x∼P(·|·,·,·) fh+1(x, π, ν
f π))(x t h, a t h, b t h)]
· E[fh(xth, ath, bth) + rth + E x∼P(·|xth,a t h,b t h) fh+1(x, π, ν f π)− 2rth − 2fh+1(xth+1, π, νfπ)|Ft,h]
= [fh(x t h, a t h, b t h)− rth − E
x∼P(·|xth,a t h,b t h) fh+1(x, π, ν
f π)] 2
and
Var[Ut(h, f, π)|Ft,h] ≤ E[(Ut(h, f, π))2|Ft,h] = [(fh − rh − E
x∼P(·|·,·,·) fh+1(x, π, ν
f π))(x t h, a t h, b t h)] 2
· E[ ( fh(x t h, a t h, b t h) + r t h + E
x∼P(·|xth,a t h,b t h) fh+1(x, π, ν
f π)− 2rth − 2fh+1(xth+1, π, νfπ) )2|Ft,h] ≤ 36[fh(xth, ath, bth)− rth − E
x∼P(·|xth,a t h,b t h) fh+1(x, π, ν
f π)] 2 = 36E[Ut(h, f, π)|Ft,h].
By Freedman’s inequality, we have with probability at least 1− p,∣∣∣∣∣ k∑
t=1
Ut(h, f, π)− k∑
t=1
E[Ut(h, f, π)|Ft,h] ∣∣∣∣∣ ≤ O (√√√√log(1/p) k∑
t=1
E[Ut|Ft,h] + log(1/p) ) .
Let Nρ × Yρ be a ρ-cover of F ×Π. The covering of Π is in-terms of the distance of two policies defined as
d(π, π′) := max f∈F,x∈S,b∈A |f(x, π, b)− f(x, π′, b)|.
Taking a union bound for all (k, h, f, p) ∈ [K]× [H]×Nρ × Yρ, we have that with probability at least 1− p for all (k, h, f, p) ∈ [K]× [H]×Nρ × Yρ∣∣∣∣∣ k∑ t=1 Ut(h, f, p)− k∑ t=1 [fh(x t h, a t h, b t h)− rth − E x∼P(·|xth,a t h,b t h) fh+1(x, p, ν f p)] 2
∣∣∣∣∣ ≤ O
(√√√√ι k∑ t=1 [fh(xth, a t h, b t h)− rth − E x∼P(·|xth,a t h,b t h) fh+1(x, p, ν f p)]2 + ι ) (21)
where ι = log(HK|Nρ||Yρ|/p). For an arbitrary (h, k) ∈ [H] × [K] pair, by the definition of Vk and (πk, fk) ∈ Vk we have
k∑ t=1 Ut(h, f k, πk)
− k∑
t=1
( rth + E
x∼P(·|xth,a t h,b t h) fkh+1(x, π
k, νf k
πk )− rth − fkh+1(xth+1, πk, ν
fk πk ) )2
≤ k∑
t=1
( fkh (x t h, a t h, b t h)− rth − fkh+1(xth+1, πk, ν fk πk ) )2
− inf g∈F k∑ t=1 ( gkh(x t h, a t h, b t h)− rth − fkh+1(xth+1, πk, ν fk πk ) )2
≤ O(ι+ kρ) (22)
where in the first step we use Assumption 3.2.
Define fk = argminf∈Nρ maxh∈[H] ∥f k h − fkh∥∞, pk = argminp∈Yρd(π k, p). Since Nρ is a ρ-cover of F , ∣∣∣∣∣ k∑ t=1 Ut(h, f k, πk)− k∑ t=1 Ut(h, f k, pk) ∣∣∣∣∣ ≤ O(kρ). (23) Therefore combining Eq (22) and Eq (23)
k∑ t=1 Ut(h, f k, pk) ≤ O(ι+ kρ). (24)
Recall Eq (21) indicates∣∣∣∣∣ k∑
t=1
Ut(h, f k, pk)− k∑ t=1 [fkh(x t h, a t h, b t h)− rth − E x∼P(·|xth,a t h,b t h) fkh+1(x, p k, νf k pk )]2 ∣∣∣∣∣ ≤ O
(√√√√ι k∑ t=1 [fkh(x t h, a t h, b t h)− rth − E x∼P(·|xth,a t h,b t h) fkh+1(x, p k, νf k pk )]2 + ι ) (25)
Combining Eq (24) and Eq (25) we have
k∑ t=1 [fkh(x t h, a t h, b t h)− rth − E x∼P(·|xth,a t h,b t h) fkh+1(x, p k, νf k pk )]2 ≤ O(ι+ kρ).
Since fk is an ρ-approximation to fk and pk is an ρ-approximation to πk, we can conclude the proof of (a) with
k−1∑ i=1 ( fkh (x i h, a i h, b i h)− rih − E x∼P(·|xih,a i h,b i h) fkh+1(x, π k h+1, (ν fk πk )h+1)) )2 ≤ O(β).
Step 2: (π,Qπ,ν ∗ π ),∀π ∈ Π is always in constraint set.
Lemma D.2. With probability at least 1− p, we have (π∗, Q∗) and (π,Qπ,∗),∀π ∈ Π all belong to Vk for all k ∈ [K].
Proof. Consider a fixed (k, h, f, π) tuple, let Ut(h, f, π) := ( fh(x t h, a t h, b t h)− rth −Q π,ν∗π h+1 (x t h+1, π, ν ∗ π) )2
− ( Q
π,ν∗π h (x t h, a t h, b t h)− rth −Q π,ν∗π h+1 (x t h+1, π, ν ∗ π )2 and Ft,h be the filtration induced by {xi1, ai1, bi1, ri1, . . . , xiH} t−1 i=1 ∪ {xt1, at1, bt1, rt1, . . . , xth, ath, bth}.
We have
E[Ut(h, f, π)|Ft,h] = [(fh −Q π,ν∗π h )(x t h, a t h, b t h)] 2
and
Var[Ut(h, f, π)|Ft,h] ≤ 36[(fh −Q π,ν∗π h )(x t h, a t h, b t h)] 2 = 36E[Ut(h, f, π)|Ft,h].
By Freedman’s inequality, we have with probability at least 1− p,∣∣∣∣∣ k∑
t=1
Ut(h, f, π)− k∑
t=1
[(fh −Q π,ν∗π h )(x t h, a t h, b t h)] 2 ∣∣∣∣∣ ≤ O
(√√√√log(1/p) k∑ t=1 [(fh −Q π,ν∗π h )(x t h, a t h, b t h)] 2 + log(1/p) ) .
Let Nρ×Yρ be a ρ-cover of F ×Π. Taking a union bound for al (k, h, f, p) ∈ [K]× [H]×Nρ×Yρ, we have that with probability at least 1− p for all (k, h, f, p) ∈ [K]× [H]×Nρ × Yρ
− k∑
t=1
Ut(h, f, p) ≤ O(ι)
where ι = log(HK|Nρ|/p). This implies for all (k, h, f, p) ∈ [K]× [H]×Nρ × Yρ k∑
t=1
( Q p,ν∗p h (x t h, a t h, b t h)− rth −Q p,ν∗p h+1(x t h+1, p, ν ∗ p) )2
≤ k∑
t=1
( fh(x t h, a t h, b t h)− rth −Q p,ν∗p h+1(x t h+1, p, ν ∗ p) )2 +O(ι+ kρ).
Since Nρ × Yρ be a ρ-cover of F ×Π, for all pk ∈ Yρ k∑
t=1
( Q p,ν∗p h (x t h, a t h, b t h)− rth −Q p,ν∗p h+1(x t h+1, p, ν ∗ p) )2
≤ inf g∈F k∑ t=1 ( gh(x t h, a t h, b t h)− rth −Q p,ν∗p h+1(x t h+1, p, ν ∗ p) )2 +O(ι+ kρ).
Again using Nρ × Yρ be a ρ-cover of F ×Π, we have for all π ∈ Π k∑
t=1
( Q
π,ν∗π h (x t h, a t h, b t h)− rth −Q π,ν∗π h+1 (x t h+1, π, ν ∗ π) )2
≤ inf g∈F k∑ t=1 ( gh(x t h, a t h, b t h)− rth −Q π,ν∗π h+1 (x t h+1, π, ν ∗ π) )2 +O(ι+ kρ).
Therefore we have (π,Qπ,ν ∗ π ),∀π ∈ Π all belong to Vk for all k ∈ [K] with probability at least 1− p.
Remark D.3. An important implication of this fact is the following
V ∗ − V π k,ν∗ πk ≤ fk1 (xk1 , πk, ν fk πk )− gk1 (xk1 , πk, νk)
which gives an upper bound of the one-side duality gap.
Step 3: Bounding the regret by Bellman error and martingale. Lemma D.4. Define
δkh := f k h (x k h, π k h, (ν
fk πk )h)− gkh(xkh, πkh, νkh)
ζkh := E[δkh+1|xkh, akh, bkh]− δkh+1 γkh := E
a∼πkh,b∼ν k h
[fkh (x k h, a, b)]− fkh (xkh, akh, bkh)
γ̂kh := E a∼πkh,b∼ν k h [gkh(x k h, a, b)]− gkh(xkh, akh, bkh)
Then we have
δkh ≤ δkh+1 + ζkh + ϵkh − ϵ̂kh + γkh − γ̂kh where ϵkh, ϵ̂ k h are the bellman error defined by
ϵkh := f k h (x k h, a k h, b k h)− rkh − E
x∼P(·|xkh,a k h,b k h) fkh (x, π k h+1, (ν
fk πk )h+1)
ϵ̂kh := g k h(x k h, a k h, b k h)− rkh − E
x∼P(·|xkh,a k h,b k h) gkh(x, π k h+1, ν k h+1).
Proof. By definition of (νf k
πk )h = argminν∈Πhf k h (x k h, π k h, ν), we have
fkh (x k h, π k h, (ν
fk πk )h) ≤ fkh (xkh, πkh, νkh)
= fkh (x k h, a k h, b k h) + γ k h
It thus follows that
δkh = f k h (x k h, π k h, (ν
fk πk )h)− gkh(xkh, πkh, νkh)
≤ fkh (xkh, akh, bkh)− gkh(xkh, akh, bkh) + γkh − γ̂kh = ( rkh + E
x∼P(·|xkh,a k h,b k h) fkh (x, π k h+1, (ν
fk πk )h+1) + ϵ k h ) − ( rkh + E
x∼P(·|xkh,a k h,b k h) gkh(x, π k h+1, ν k h+1) + ϵ̂ k h
) + γkh − γ̂kh
= E x∼P(·|xkh,a k h,b k h) fkh (x, π k h+1, (ν
fk πk )h+1)− E
x∼P(·|xkh,a k h,b k h) gkh(x, π k h+1, ν k h+1)
+ ϵkh − ϵ̂kh + γkh − γ̂kh = δkh+1 + ζ k h + ϵ k h − ϵ̂kh + γkh − γ̂kh.
Thus we complete the proof.
Step 4: Bounding cumulative Bellman error using Minimax Eluder dimension. Lemma D.5 (Bounding Bellman error). For any (k, h) ∈ [K]× [H] we have
k∑ t=1 |ϵth| ≤ O (√ k · dimME′(F , √ 1/K) log[N (F , 1/K) · N (Π, 1/K) ·HK/p] )
k∑ t=1 |ϵ̂th| ≤ O (√ k · dimME′(F , √ 1/K) log[N (F , 1/K) · N (Π, 1/K) ·HK/p] ) .
Proof. Let
lt(·, ·, ·) = f th(·, ·, ·)− rh(·, ·, ·)− E x∼P(·,·,·) f th+1(x, π t, νf
t
πt )
and ρt = δ(xth, a t h, b t h). Similarly, we can also let ρt be generated by (π t, νt). Then Lemma D.1 indicates
k∑ t=1 l2k(ρt) ≤ O(β).
Based on this, we can apply Lemma F.1 to obtain the first inequality. The second follows similarly.
Step 5: Putting them all together. We can upper bound the regret as follows: K∑
k=1
[V ∗ − V π k,ν∗ πk ] ≤ K∑
k=1
[fk1 (x k 1 , π
k, νf k
πk )− gk1 (xk1 , πk, νk)]
≤ K∑
k=1 H∑ h=1 (ζkh + ϵ k h − ϵ̂kh + γkh − γ̂kh)
= H∑ h=1 K∑ k=1 (ζkh + γ k h − γ̂kh) + H∑ h=1 K∑ k=1 (ϵkh − ϵ̂kh) (26)
where the first step comes from Lemma D.2, the second step comes from Lemma D.4 and the last step comes from Fubini’s theorem. Notice that the first term in Eq (26) is a martingale difference sequence and can be bounded by O(H √ KH log(HK/p)) with probability at least 1− p and the second term can be bounded by Lemma D.5. We thus complete the proof.

heading: E EXAMPLES
text: In this section we give several examples of Markov games that possess low Minimax Eluder dimension, including tabular Markov Games, linear function approximation, reproducing kernel Hilbert space (RKHS) function approximation, overparameterized neural networks, and generalized linear models. We first consider reproducing kernel Hilbert space (RKHS) function approximation, which captures many existing models.
Reproducing kernel Hilbert space (RKHS) function approximation. In this setting, the function class of interest is given by
Fh = {⟨ϕh(x, a, b), θh⟩ : θ, ϕ(·, ·, ·) ∈ BR(H)}.
Here ϕ(·, ·, ·) : S × A ×A 7→ H is a feature map to H, θ ∈ H, and BR(H) is the ball centered at zero with radius R in a Hilbert space H. The effective dimension of a set D ⊂ H is characterized by the critical information gain d̃(γ,D). Specifically, for γ > 0 and D ⊂ H, we define dn(γ,D) = maxx1,...,xn∈D log det(I + 1 γ ∑n i=1 xix ⊤ i ). The critical information gain (Du et al., 2021) is thus defined by d̃(γ,D) = mink∈N:k≥dn(γ,D) k. The main result is given in the following theorem. Theorem E.1. In kernel function approximation, the Minimax Eluder dimensions dimME(F , ϵ) and dimME′(F , ϵ) are upper bounded by maxh∈[H] γ̃( ϵ9R ,Φh), where Φh = {ϕh(x, a, b) : x ∈ S, a, b ∈ A}.
Proof. We only show dimME′(F , ϵ) ≤ maxh∈[H] γ̃( ϵ9R ,Φh), and the other part is totally similar. Fix an h ∈ [H]. Due to completeness, for any π ∈ Π and f ∈ F we have (fh − T πh fh+1)(x, a, b) = ⟨ϕh(x, a, b), θh − T πh θh+1⟩ where T πh θh+1 is the unique feature in H such that T πh fh+1 = ⟨ϕh(x, a, b), T πh θh+1⟩. Consider the longest sequence ν1, . . . , νk ∈ D∆ such that each one item is ϵ-independent of its precedents, distinguished by a sequence of features θ(1)h , . . . , θ (k) h . To simplify notations, we define ϕi = Eνi [ϕh(x, a, b)] and θi = θ (i) h − T πh θ (i) h+1 for all i ∈ [k]. Let
Λi = ∑i−1 τ=1 ϕτϕ ⊤ τ + ϵ2 9R2 I . Then Definition 3.3 gives
∥ϕi∥Λ−1i ≥ 1 ϵ · ∥ϕi∥Λ−1i · ∥θi∥Λi ≥ 1 ϵ · |⟨ϕi, θi⟩| ≥ 1.
where the first step comes from θi ∈ BR(H) and ∑i−1
j=1⟨ϕj , θj⟩2 ≤ ϵ, the second step comes from Hölder’s inequality and the final step comes from |⟨ϕi, θi⟩| ≥ ϵ. Thus we have
k ≤ k∑
i=1
log(1 + ∥ϕi∥Λ−1i ) = log det(I + 9R2
ϵ2 k∑ i=1 ϕiϕ ⊤ i ).
By the definition of critical information gain, k must be less or equal than γ̃( ϵ9R ,Φh).
This result implies several important cases in general function approximation.
• Linear function approximation. In this setting rh(x, a, b) = ϕ(x, a, b)⊤θh and Ph(·|x, a, b) = ϕ(x, a, b)⊤µh(·) where ϕ(x, a, b) ∈ Rd. We have shown that this setting satisfies all the realizability and completeness assumptions in the previous sections. By standard Ellipsoid potential arguments, the critical information gain is upper bounded by O(d · log(R/ϵ)). Therefore, this setting also has low Minimax Eluder dimensions.
• Tabular Markov Games. This setting can be seen as a special case of linear function approximation where the feature vectors are chosen to be one-hot representations of stateactions pairs. In this case, d = |S| · |A|2 and thus Minimax Eluder dimensions is upper bounded by Õ(|S| · |A|2).
• Overparameterized neural networks. In overparameterized neural network function approximations, the functions are given by h(ϕ(x, a, b)) where h is the Neural Tangent Random Feature space defined in Cao & Gu (2019). We rewrite the information gain dn(γ,D) as maxx1,...,xn∈D log det(I + 1γKn) where (Kn)i,j = K(xi, xj) and K is the Neural Tangent Kernel. It has been shown (Jacot et al., 2018; Du et al., 2019c;a; Allen-Zhu
et al., 2019) that with proper initialization and learning rates, the function approximations approximately lie in the Reproducing kernel Hilbert space given by the neural tangent feature as above. Therefore the Minimax Eluder dimensions are bounded by γ̃( ϵ9R ,Φh)+λ, where γ̃ is the critical information gain defined by the dn(γ,D) rewritten above and λ is a term that vanishes as width tends to infinity.
Generalized linear models. Finally, we consider generalized linear model as an extension of the linear function approximations. Theorem E.2. Suppose (fh − T πh fh+1)(x, a, b) = g(ϕ(x, a, b)⊤θh) for any π ∈ Π and f ∈ F , where g is a differentiable and strictly increasing function and ϕ, θh ∈ Rd. Assume g′ ∈ (c1, c2) and ∥ϕ∥2, ∥θh∥2 ≤ R for c1, c2, R > 0. Then dimME′(F , ϵ) ≤ O(d(c2/c1)2 log( c2Rc1ϵ )).
Proof. The proof mirrors those in Theorem E.1. For the longest sequence ν1, . . . , νk ∈ D∆ such that each one item is ϵ-independent of its precedents, distinguished by a sequence of features θ (1) h , . . . , θ (k) h , we define ϕi = Eνi [ϕh(x, a, b)] and θi = θ (i) h − T πh θ (i) h+1 for all i ∈ [k]. Let
Λi = ∑i−1 τ=1 ϕτϕ ⊤ τ + ϵ2
9R2c21 I . Then Definition 3.3 gives
∥ϕi∥Λ−1i ≥ c1 ϵ · ∥ϕi∥Λ−1i · ∥θi∥Λi ≥ c1 ϵ · |⟨ϕi, θi⟩| ≥ c1 c2 .
This means det(Λk) ≥ (1 + c 2 1 c22 )k−1. But by Elliptic potential lemma, det(Λk) ≤ (R 2k d + ϵ2 9R2c21 )d. Combining these two inequalities gives k ≤ O(d(c2/c1)2 log( c2Rc1ϵ )).

heading: F TECHNICAL CLAIMS
text: This section lists the facts we use from the previous work. Lemma F.1 (Cumulative error control, Lemma 26 of Jin et al. (2021a)). Given a function class G defined on X with |g(x)| ≤ C for all (g, x) ∈ G ×X and a family of probability measures D over X . Suppose sequence {gk}Kk=1 ⊂ G and {ρk}Hk=1 ⊂ D such that for all k ∈ [K], ∑k−1 t=1 (Eρt [gk])2 ≤ β. Then for all k ∈ [K] and ω > 0, k∑
t=1
| E ρt [gt]| ≤ O
(√ dimDE(G,D, ϵ)βk +min{k, dimDE(G,D, ϵ)}C + kω ) .
Lemma F.2 (Lemma 11 of Jiang et al. (2017)). Consider a closed and bounded set V ⊂ Rd and a vector p ∈ Rd. Let B be any origin-centered enclosing ellipsoid of V . Suppose there exists v ∈ V such that p⊤v ≥ κ and define B+ as the minimum volume enclosing ellipsoid of {v ∈ B : |p⊤v| ≤ κ
3 √ d }. With vol(·) denoting the (Lebesgue) volume, we have:
vol(B+) vol(B) ≤ 3 5 .

Review summaries:
This paper presents sample efficient algorithms for learning in two-player zero-sum markov games. The algorithms are for decoupled and coordinated settings, the latter of which is based on 'alternate optimism'. The authors also extend the Eluder dimension of MDPs to to zero-sum markov games using the minimax Bellman operator. 

This paper studies efficient function approxiamtion in two-player zero-sum Markov games with general function classes. Both decoupled and coordinated settings for learning agents are considered. Model-free algorithms for both settings and model-based algorithm for the leter are provided, all with proved sample complexities.

This paper considers zero-sum Markov games in a general regime where the model is parameterized by general function classes. The goal of this research is to investigate reinforcement learning algorithms that learn a Nash policy in a trial-and-error fashion. The level of generality is achieved by introducing two complexity measures: The minimax Eluder dimension and the witness rank. The main result three algorithms with provable regret upper bounds involving covering numbers and the minimax Eluder dimension.