A Sharp Analysis of Model-based Reinforcement Learning with Self-Play

Introduction

This paper is concerned with the problem of multi-agent reinforcement learning (multi-agent RL), in which multiple agents learn to make decisions in an unknown environment in order to maximize their (own) cumulative rewards. Multi-agent RL has achieved significant recent success in traditionally hard AI challenges including large-scale strategy games (such as GO) (Silver et al., 2016, 2017), real-time video games involving team play such as Starcraft and Dota2 (OpenAI, 2018; Vinyals et al., 2019), as well as behavior learning in complex social scenarios (Baker et al., 2020). Achieving human-like (or super-human) performance in these games using multi-agent RL typically requires a large number of samples (steps of game playing) due to the necessity of exploration, and how to improve the sample complexity of multi-agent RL has been an important research question.

One prevalent approach towards solving multi-agent RL is model-based methods, that is, to use the existing visitation data to build an estimate of the model (i.e. transition dynamics and rewards), run an offline planning algorithm on the estimated model to obtain the policy, and play the policy in the environment. Such a principle underlies some of the earliest single-agent online RL algorithms such as E3 (Kearns and Singh, 2002) and RMax (Brafman and Tennenholtz, 2002), and is conceptually appealing for multi-agent RL too since the multi-agent structure does not add complexity onto the model estimation part and only requires an appropriate multi-agent planning algorithm (such as value iteration for games (Shapley, 1953)) in a black-box fashion. On the other hand, model-free methods do not directly build estimates of the model, but instead directly estimate the value functions or action-value (Q) functions of the problem at the optimal/equilibrium policies, and play the greedy policies with respect to the estimated value functions. Model-free algorithms have also been well developed for multi-agent RL such as friend-or-foe Q-Learning (Littman, 2001) and Nash Q-Learning (Hu and Wellman, 2003).

How sample-efficient are model-based algorithms in multi-agent RL?

In this paper, we advance the theoretical understandings of multi-agent RL by presenting a sharp analysis of model-based algorithms on Markov games. Our core contribution is the design of a new model-based algorithm Optimistic Nash Value Iteration (Nash-VI) that achieves an almost optimal sample complexity for zero-sum Markov games and improves significantly over existing model-based approaches. We summarize our main contributions as follows. A comparison between our and prior results can be found in Table 1.

Markov games (or stochastic games) are proposed in the early 1950s (Shapley, 1953). They are widely used to model multi-agent RL. Learning the Nash equilibria of Markov games has been studied in Littman (1994, 2001); Hu and Wellman (2003); Hansen et al. (2013); Lee et al. (2020), where the transition matrix and reward are assumed to be known, or in the asymptotic setting where the number of data goes to infinity. These results do not directly apply to the non-asymptotic setting where the transition and reward are unknown and only a limited amount of data are available for estimating them.

Another line of works make certain strong reachability assumptions under which sophisticated exploration strategies are not required. A prevalent approach is to assume access to simulators (generative models) that enable the agent to directly sample transition and reward information for any state-action pair. In this setting, Jia et al. (2019); Sidford et al. (2019); Zhang et al. (2020a) provide non-asymptotic bounds on the number of calls to the simulator for finding an $\epsilon$-approximate Nash equilibrium. Wei et al. (2017) study Markov games under an alternative assumption that no matter what strategy one agent sticks to, the other agent can always reach all states by playing a certain policy.

Recent works of Bai and Jin (2020); Xie et al. (2020) provide the first line of non-asymptotic sample complexity guarantees for learning Markov games without reachability assumptions. More recently, Bai et al. (2020) propose two model-free algorithms—Nash Q-Learning and Nash V-Learning with better sample complexity guarantees. In particular, the Nash V-learning algorithm achieves near-optimal dependence on $S$, $A$ and $B$. However, the dependence on $H$ is worse than our results and the output policy is a nested mixture, which is hard to implement. We compare our results with existing non-asymptotic guarantees in Table 1.

We remark that the classic R-max algorithm (Brafman and Tennenholtz, 2002) also provides provable guarantees for learning Markov games. However, Brafman and Tennenholtz (2002) use a weaker definition of regret (similar to the online setting in Xie et al., 2020), and consequently their result does not imply any sample complexity guarantee for finding Nash equilibrium policies.

Another way to model the multi-player bahavior is to use adversarial MDPs. Most works in this line consider the setting with adversarial reward (Zimin and Neu, 2013; Rosenberg and Mansour, 2019; Jin et al., 2019), where the reward can be manipulated by an adversary arbitrarily and the goal is to compete with the optimal (stationary) policy in hindsight. Learning adversarial MDPs with changing dynamics is computationally hard even under full-information feedback (Yadkori et al., 2013). Notice these results also do not imply provable algorithms in our setting, because the opponent in Markov games can affect both the reward and the transition.

Jin et al. (2020) study a new paradigm of learning MDPs called reward-free learning, which is also known as the task-agnostic (Zhang et al., 2020b) or reward-agnostic setting. In this setting, the agent goes through a two-stage process. In the exploration phase the agent interacts with the environment without the guidance of any reward information, and in the planning phase the reward information is revealed and the agent computes a policy based on the transition information collected in the exploration phase and the reward information revealed in the planning phase.

Jin et al. (2020) also propose an algorithm, which first finds a covering policy by maximizing the probability to reach each state separately and then collects data following this policy. Zhang et al. (2020b) take a different approach by first running the optimistic Q-learning algorithm (Jin et al., 2018) with zero reward to explore the environment, and then utilizing the trajectories collected to compute a policy in an incremental manner. Wang et al. (2020) follow a similar scheme, but study reward-free exploration in linear-parametrized MDPs.

Preliminaries

In this paper, we consider Markov Games (MGs, Shapley, 1953; Littman, 1994), which are also known as stochastic games in the literature. Markov games are the generalization of standard Markov Decision Processes (MDPs) into the multi-player setting, where each player seeks to maximize her own utility. For simplicity, in this section we describe the important special case of two-player zero-sum games, and return to the general formulation in Section 5.

A (Markov) policy $\mu$ of the max-player is a collection of $H$ functions $\{\mu_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\}_{h\in[H]}$, each mapping from a state to a distribution over actions. (Here $\Delta_{\mathcal{A}}$ is the probability simplex over action set $\mathcal{A}$.) Similarly, a policy $\nu$ of the min-player is a collection of $H$ functions $\{\nu_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{B}}\}_{h\in[H]}$. We use the notation $\mu_{h}(a|s)$ and $\nu_{h}(b|s)$ to represent the probability of taking action $a$ or $b$ for state $s$ at step $h$ under Markov policy $\mu$ or $\nu$ respectively.

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, and at the $(H+1)^{\text{th}}$ step we have $V^{\mu,\nu}_{H+1}(s)=0$ for all $s\in\mathcal{S}$.

For any policy of the max-player $\mu$, there exists a best response of the min-player, which is a policy $\nu^{\dagger}(\mu)$ satisfying $V_{h}^{\mu,\nu^{\dagger}(\mu)}(s)=\inf_{\nu}V_{h}^{\mu,\nu}(s)$ for any $(s,h)\in\mathcal{S}\times[H]$. We denote $V_{h}^{\mu,\dagger}\mathrel{\mathop{:}}=V_{h}^{\mu,\nu^{\dagger}(\mu)}$. By symmetry, we can also define $\mu^{\dagger}(\nu)$ and $V_{h}^{\dagger,\nu}$. It is further known (cf. Filar and Vrieze, 2012) that there exist policies $\mu^{\star}$, $\nu^{\star}$ that are optimal against the best responses of the opponents, in the sense that

We call these optimal strategies $(\mu^{\star},\nu^{\star})$ the Nash equilibrium of the Markov game, which satisfies the following minimax equation The minimax theorem here is different from the one for matrix games, i.e. $\max_{\phi}\min_{\psi}\phi^{\top}A\psi=\min_{\psi}\max_{\phi}\phi^{\top}A\psi$ for any matrix $A$, since here $V^{\mu,\nu}_{h}(s)$ is in general not bilinear in $\mu,\nu$.:

Intuitively, a Nash equilibrium gives a solution in which no player has anything to gain by changing only her own policy. We further abbreviate the values of Nash equilibrium $V_{h}^{\mu^{\star},\nu^{\star}}$ and $Q_{h}^{\mu^{\star},\nu^{\star}}$ as $V_{h}^{{\star}}$ and $Q_{h}^{{\star}}$. We refer readers to Appendix A for Bellman optimality equations for (the value functions of) the best responses and the Nash equilibrium.

We measure the suboptimality of any pair of general policies $(\hat{\mu},\hat{\nu})$ using the gap between their performance and the performance of the optimal strategy (i.e., Nash equilibrium) when playing against the best responses respectively:

A pair of general policies $(\hat{\mu},\hat{\nu})$ is an $\epsilon$-approximate Nash equilibrium, if $V^{\dagger,\hat{\nu}}_{1}(s_{1})-V^{\hat{\mu},\dagger}_{1}(s_{1})\leq\epsilon$.

Let $(\mu^{k}$, $\nu^{k})$ denote the policies deployed by the algorithm in the $k^{\text{th}}$ episode. After a total of $K$ episodes, the regret is defined as

One goal of reinforcement learning is to design algorithms for Markov games that can find an $\epsilon$-approximate Nash equilibrium using a number of episodes that is small in its dependency on $S,A,B,H$ as well as $1/\epsilon$ (PAC sample complexity bound). An alternative goal is to design algorithms for Markov games that achieves regret that is sublinear in $K$, and polynomial in $S,A,B,H$ (regret bound). We remark that any sublinear regret algorithm can be directly converted to a polynomial-sample PAC algorithm via the standard online-to-batch conversion (see e.g., Jin et al., 2018).

Optimistic Nash Value Iteration

In this section, we present our main algorithm—Optimistic Nash Value Iteration (Nash-VI), and provide its theoretical guarantee.

We describe our Nash-VI Algorithm 1. In each episode, the algorithm can be decomposed into two parts.

At a high-level, this two-phase strategy is standard in the majority of model-based RL algorithms, and also underlies provably efficient model-based algorithms such as UCBVI for single-agent (MDP) setting (Azar et al., 2017) and VI-ULCB for the two-player Markov game setting (Bai and Jin, 2020). However, VI-ULCB has two undesirable drawbacks: the sample complexity is not tight in any of $H$, $S$, and $A,B$ dependency, and its computational complexity is PPAD-complete (a complexity class conjectured to be computationally hard (Daskalakis, 2013)).

As we elaborate in the following, our Nash-VI algorithm differs from VI-ULCB in a few important technical aspects, which allows it to significantly improve the sample complexity over VI-ULCB, and ensures that our algorithm terminates in polynomial time.

Before digging into explanations of techniques, we remark that line 14-15 is only used for computing the output policies. It chooses policy $\pi^{\text{out}}$ to be the policy in the episode with minimum gap $(\overline{V}_{1}-\underline{V}_{1})(s_{1})$. Our final output policies $(\mu^{\text{out}},\nu^{\text{out}})$ are simply the marginal policies of $\pi^{\text{out}}$. That is, for all $(s,h)\in\mathcal{S}\times[H]$, $\mu_{h}^{\text{out}}(\cdot|s):=\sum_{b\in\mathcal{B}}\pi_{h}^{\text{out}}(\cdot,b|s)$, and $\nu_{h}^{\text{out}}(\cdot|s):=\sum_{a\in\mathcal{A}}\pi_{h}^{\text{out}}(a,\cdot|s)$.

Our Nash-VI allows two choices of the bonus function $\beta=\textsc{Bonus}(t,\hat{\sigma}^{2})$:

The prior algorithm VI-ULCB (Bai and Jin, 2020) computes the “greedy” policy with respect to the estimated value functions by directly computing the Nash equilibrium for the $Q$-value at each step $h$. However, since the algorithm maintains both the upper confidence bound and lower confidence bound of the $Q$-value, this leads to the requirement to compute the Nash equilibrium for a two-player general-sum matrix game, which is in general PPAD-complete (Daskalakis, 2013).

To overcome this computational challenge, we compute a relaxation of the Nash equilibrium—Coarse Correlated Equalibirum (CCE)—instead, a technique first introduced by Xie et al. (2020) to address reinforcement learning problems in Markov Games. Formally, for any pair of matrices $\overline{Q},\underline{Q}\in[0,H]^{A\times B}$, $\textsc{CCE}(\overline{Q},\underline{Q})$ returns a distribution $\pi\in\Delta_{\mathcal{A}\times\mathcal{B}}$ such that

Intuitively, in a CCE the players choose their actions in a potentially correlated way such that no one can benefit from unilateral unconditional deviation. A CCE always exists, since Nash equilibrium is also a CCE and a Nash equilibrium always exists. Furthermore, a CCE can be computed by linear programming in polynomial time. We remark that different from Nash equilibrium where the policies of each player are independent, the policies given by CCE are in general correlated for each player. Therefore, executing such a policy (line 17) requires the cooperation of two players.

2 Theoretical guarantees

Now we are ready to present the theoretical guarantees for Algorithm 1. We let $\pi^{k}$ denote the policy computed in line 12 in the $k^{\text{th}}$ episode, and $\mu^{k},\nu^{k}$ denote the marginal policy of $\pi^{k}$ for each player.

For any $p\in(0,1]$, letting $\iota=\log(SABT/p)$, then with probability at least $1-p$, Algorithm 1 with Hoeffding type bonus (3) (with some absolute $c>0$) achieves:

$(V_{1}^{\dagger,\nu^{\text{out}}}-V_{1}^{\mu^{\text{out}},\dagger})(s_{1})\leq\epsilon$, if the number of episodes $K\geq\Omega(H^{4}SAB\iota/\epsilon^{2}+H^{3}S^{2}AB\iota^{2}/\epsilon)$.

${\rm Regret}(K)=\sum_{k=1}^{K}(V^{\dagger,\nu^{k}}_{1}-V^{\mu^{k},\dagger}_{1})(s_{1})\leq\mathcal{O}(\sqrt{H^{3}SABT\iota}+H^{3}S^{2}AB\iota^{2})$.

Our next theorem states that when using Bernstein bonus instead of Hoeffding bonus as in (3), the sample complexity of Nash-VI algorithm can be further improved by a $H$ factor in the leading order term (and the regret improved by a $\sqrt{H}$ factor).

For any $p\in(0,1]$, letting $\iota=\log(SABT/p)$, then with probability at least $1-p$, Algorithm 1 with Bernstein type bonus (3) (with some absolute $c>0$) achieves:

$(V_{1}^{\dagger,\nu^{\text{out}}}-V_{1}^{\mu^{\text{out}},\dagger})(s_{1})\leq\epsilon$, if the number of episodes $K\geq\Omega(H^{3}SAB\iota/\epsilon^{2}+H^{3}S^{2}AB\iota^{2}/\epsilon)$.

${\rm Regret}(K)=\sum_{k=1}^{K}(V^{\dagger,\nu^{k}}_{1}-V^{\mu^{k},\dagger}_{1})(s_{1})\leq\mathcal{O}(\sqrt{H^{2}SABT\iota}+H^{3}S^{2}AB\iota^{2})$.

Compared with the information-theoretic sample complexity lower bound $\Omega(H^{3}S(A+B)\iota/\epsilon^{2})$ and regret lower bound $\Omega(\sqrt{H^{2}S(A+B)T})$ (Bai and Jin, 2020), when $\epsilon$ is small, Nash-VI with Bernstein bonus achieves the optimal dependency on all of $H,S,\epsilon$ up to logarithmic factors in both the sample complexity and the regret, and the only gap that remains open is a $AB/(A+B)\leq\min{\left\{A,B\right\}}$ factor. The proof of Theorem 4 can be found in Appendix C.2.

Reward-free Learning

In this section, we modify our model-based algorithm Nash-VI for the reward-free exploration setting. Formally, reward-free learning has two phases: In the exploration phase, the agent collects a dataset of transitions $\mathcal{D}=\{(s_{k,h},a_{k,h},b_{k,h},s_{k,h+1})\}_{(k,h)\in[K]\times[H]}$ from a Markov game $\mathcal{M}$ without the guidance of reward information. After the exploration, in the planning phase, for each task $i\in[N]$, $\mathcal{D}$ is augmented with stochastic reward information to become $\mathcal{D}^{i}=\{(s_{k,h},a_{k,h},b_{k,h},s_{k,h+1},r_{k,h})\}_{(k,h)\in[K]\times[H]}$, where $r_{k,h}$ is sampled from some unknown reward distribution with expectation equal to $r^{i}_{h}(s_{k,h},a_{k,h},b_{k,h})$. Here, $r^{i}$ denotes the unknown reward function of the $i^{\rm th}$ task. The goal is to compute nearly-optimal policies for $N$ tasks under $\mathcal{M}$ simultaneously given the augmented datasets $\{\mathcal{D}^{i}\}_{i\in[N]}$.

There are strong practical motivations for considering the reward-free setting. First, in applications such as robotics, we face multiple tasks in sequential systems with shared transition dynamics (i.e. the world) but very different rewards. There, we prefer to learn the underlying transition independent of reward information. Second, from the algorithm design perspective, decoupling exploration and planning (i.e. performing exploration without reward information) can be valuable for designing new algorithms in more challenging settings (e.g., with function approximation).

We now describe our algorithm for reward-free learning in zero-sum Markov games.

2 Theoretical guarantees

Since MDPs are special cases of Markov games, our algorithm VI-Zero directly applies to the single-agent setting, and yields a sample complexity similar to existing results (Zhang et al., 2020b; Wang et al., 2020). However, distinct from existing results which require both the exploration algorithm and the planning algorithm to be specially designed to work together, our algorithm allows an arbitrary planning algorithm as long as it computes the Nash equilibrium of a Markov game with known transition and reward. Therefore, our results completely decouple the exploration and the planning.

Finally, we comment that despite the sample complexity in Theorem 5 scaling as $AB$ instead of $A+B$, our next theorem states that unlike the general reward-aware setting, this $AB$ scaling is unavoidable in the reward-free setting. This reveals an intrinsic gap between the reward-free and reward-aware learning: An $A+B$ dependency is only achievable via sampling schemes that are reward-aware. A similar lower bound is also presented in Zhang et al. (2020a) for the discounted setting with a different hard instance construction.

There exists an absolute constant $c>0$ such that for any $\epsilon\in(0,c]$, there exists a family of Markov games $\mathfrak{M}(\epsilon)$ satisfying that: for any reward-free algorithm $\mathfrak{A}$ using $K\leq cH^{2}SAB/\epsilon^{2}$ episodes, there exists a Markov game $\mathcal{M}\in\mathfrak{M}(\epsilon)$ such that if we run $\mathfrak{A}$ on $\mathcal{M}$ and output policies $(\hat{\mu},\hat{\nu})$, then with probability at least $1/4$, we have $(V_{1}^{\dagger,\hat{\nu}}-V_{1}^{\hat{\mu},\dagger})(s_{1})\geq\epsilon$.

This lower bound shows that the sample complexity in Theorem 5 is optimal in $S$, $A,B$, and $\epsilon$. The proof of Theorem 6 can be found in Appendix D.3.

Multiplayer General-sum Markov Games

In this section, we extend both our model-based algorithms (Algorithm 1 and Algorithm 2) to the setting of multiplayer general-sum Markov games, and present corresponding theoretical guarantees.

In this section, we consider three versions of equlibrium for general-sum MGs: Nash equilibrium (NE), correlated equilibrium (CE), and coarse correlated equilibrium (CCE), all being standard solution notions in games (Nisan et al., 2007). These three notions coincide on two-player zero-sum games, but are not equivalent to each other on multi-player general-sum games; any one of them could be desired depending on the application at hand. Below we introduce their definitions.

The policy of the $i^{\text{th}}$ player is denoted as \pi_{i}\mathrel{\mathop{:}}=\big{\{}\pi_{h,i}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}_{i}}\big{\}}_{h\in[H]}. We denote the product policy of all the players as $\pi:=\pi_{1}\times\cdots\times\pi_{M}$, and denote the policy of all the players except the $i^{\text{th}}$ player as $\pi_{-i}$. We define $V^{\pi}_{h,i}(s)$ as the expected cumulative reward that will be received by the $i^{\text{th}}$ player if starting at state $s$ at step $h$ and all players follow policy $\pi$. For any strategy $\pi_{-i}$, there also exists a best response of the $i^{\text{th}}$ player, which is a policy $\mu^{\dagger}(\pi_{-i})$ satisfying $V_{h,i}^{\mu^{\dagger}(\pi_{-i}),\pi_{-i}}(s)=\sup_{\pi_{i}}V_{h,i}^{\pi_{i},\pi_{-i}}(s)$ for any $(s,h)\in\mathcal{S}\times[H]$. We denote $V_{h,i}^{\dagger,\pi_{-i}}\mathrel{\mathop{:}}=V_{h,i}^{\mu^{\dagger}(\pi_{-i}),\pi_{-i}}$. The Q-functions of the best response can be defined similarly.

Our first objective is to find an approximate Nash equilibrium of Markov games.

A product policy $\pi$ is an $\epsilon$-approximate Nash equilibrium if $\max_{i\in[m]}{(V_{1,i}^{{\dagger},\pi_{-i}}-V_{1,i}^{\pi})}(s_{1})\leq\epsilon$.

The above definition requires the suboptimality gap $(V_{1,i}^{{\dagger},\pi_{-i}}-V_{1,i}^{\pi})(s_{1})$ to be less than $\epsilon$ for all player $i$. This is consistent with the two-player case (Definition 1) up to a constant of 2, since in the two-player zero-sum setting, we have $V_{1,1}^{\pi}(s_{1})=-V_{1,2}^{\pi}(s_{1})$ for any product policy $\pi=(\mu,\nu)$, and therefore $(V_{1,1}^{{\dagger},\nu}-V_{1,1}^{\mu,{\dagger}})(s_{1})\leq 2\max_{i\in}{(V_{1,i}^{{\dagger},\pi_{-i}}-V_{1,i}^{\pi})}(s_{1})\leq 2(V_{1,1}^{{\dagger},\nu}-V_{1,1}^{\mu,{\dagger}})(s_{1})$.We can similarly define the regret.

Let $\pi^{k}$ denote the (product) policy deployed by the algorithm in the $k^{\text{th}}$ episode. After a total of $K$ episodes, the regret is defined as

The coarse correlated equilibrium (CCE) is a relaxed version of Nash equilibrium in which we consider general correlated policies instead of product policies. Let $\mathcal{A}=\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{m}$ denote the joint action space.

A (correlated) policy $\pi:=\{\pi_{h}(s)\in\Delta_{\mathcal{A}}:\ (h,s)\in[H]\times\mathcal{S}\}$ is a CCE if $\max_{i\in[m]}V^{\dagger,\pi_{-i}}_{h,i}(s)\leq V^{\pi}_{h,i}(s)$ for all $(s,h)\in\mathcal{S}\times[H]$.

Compared with a Nash equilibrium, a CEE is not necessarily a product policy, that is, we may not have $\pi_{h}(s)\in\Delta_{\mathcal{A}_{1}}\times\cdots\times\Delta_{\mathcal{A}_{m}}$. Similarly, we also define $\epsilon$-approximate CCE and CCE-regret below.

A policy $\pi:=\{\pi_{h}(s)\in\Delta_{\mathcal{A}}:\ (h,s)\in[H]\times\mathcal{S}\}$ is an $\epsilon$-approximate CCE if $\max_{i\in[m]}{(V_{1,i}^{{\dagger},\pi_{-i}}-V_{1,i}^{\pi})}(s_{1})\leq\epsilon$.

Let policy $\pi^{k}$ denote the (correlated) policy deployed by the algorithm in the $k^{\text{th}}$ episode. After a total of $K$ episodes, the regret is defined as

The correlated equilibrium (CE) is another relaxation of the Nash equilibrium. To define CE, we first introduce the concept of strategy modification: A strategy modification $\phi:=\{\phi_{h,s}\}_{(h,s)\in[H]\times\mathcal{S}}$ for player $i$ is a set of $S\times H$ functions from $\mathcal{A}_{i}$ to itself. Let $\Phi_{i}$ denote the set of all possible strategy modifications for player $i$.

One can compose a strategy modification $\phi$ with any Markov policy $\pi$ and obtain a new policy $\phi\diamond\pi$ such that when policy $\pi$ chooses to play $\bm{a}:=(a_{1},\ldots,a_{m})$ at state $s$ and step $h$, policy $\phi\diamond\pi$will play $(a_{1},\ldots,a_{i-1},\phi_{h,s}(a_{i}),a_{i+1},\ldots,a_{m})$ instead.

A policy $\pi:=\{\pi_{h}(s)\in\Delta_{\mathcal{A}}:\ (h,s)\in[H]\times\mathcal{S}\}$ is a CE if $\max_{i\in[m]}\max_{\phi\in\Phi_{i}}V^{\phi\diamond\pi}_{h,i}(s)\leq V^{\pi}_{h,i}(s)$ holds for all $(s,h)\in\mathcal{S}\times[H]$.

Similarly, we have an approximate version of CE and CE-regret.

A policy $\pi:=\{\pi_{h}(s)\in\Delta_{\mathcal{A}}:\ (h,s)\in[H]\times\mathcal{S}\}$ is an $\epsilon$-approximate CE if $\max_{i\in[m]}\max_{\phi\in\Phi_{i}}(V^{\phi\diamond\pi}_{1,i}-V^{\pi}_{1,i})(s_{1})\leq\epsilon$.

Let policy $\pi^{k}$ denote the policy deployed by the algorithm in the $k^{\text{th}}$ episode. After a total of $K$ episodes, the regret is defined as

For general-sum MGs, we have ${\left\{{\rm Nash}\right\}}\subseteq{\left\{{\rm CE}\right\}}\subseteq{\left\{{\rm CCE}\right\}}$, so that they form a nested set of notions of equilibria (Nisan et al., 2007). Indeed, one can easily verify that if we restrict the choice of strategy modification $\phi$ to those consisting of only constant functions, i.e., $\phi_{h,s}(a)$ being independent of $a$, Definition 12 will reduce to the definition of CCE policy. In addition, any Nash equilibrium is a CE by definition. Finally, since a Nash equilibrium always exists, so does CE and CCE.

2 Multiplayer optimistic Nash value iteration

Here we present the Multi-Nash-VI algorithm, which is an extension of Algorithm 1 for multi-player general-sum Markov games.

Our Equilibrium subroutine in Line 11 could be taken from either one of the $\{\textsc{Nash},\textsc{CE},\textsc{CCE}\}$ subroutines for one-step games. When using Nash, we compute the Nash equilibrium of a one-step multi-player game (see, e.g., Berg and Sandholm (2016) for an overview of the available algorithms); the worst-case computational complexity of such a subroutine will be PPAD-hard (Daskalakis, 2013). When using CE or CCE, we find CEs or CCEs of the one-step games respectively, which can be solved in polynomial time using linear programming. However, the policies found are not guaranteed to be a product policy. We remark that in Algorithm 1 we used the CCE subroutine for finding Nash in two-player zero-sum games, which seemingly contrasts the principle of using the right subroutine for finding the right equilibrium, but nevertheless works as the Nash equilibrium and CCE are equivalent in zero-sum games.

Now we are ready to present the theoretical guarantees for Algorithm 3. We let $\pi^{k}$ denote the policy computed in line 11 of Algorithm 3 in the $k^{\text{th}}$ episode.

There exists an absolute constant $c$, for any $p\in(0,1]$, let $\iota=\log(SABT/p)$, then with probability at least $1-p$, Algorithm 3 with bonus $\beta_{t}=c\sqrt{SH^{2}\iota/t}$ and Equilibrium being one of $\{\textsc{Nash},\textsc{CE},\textsc{CCE}\}$ satisfies (repsectively):

$\pi^{\text{out}}$ is an $\epsilon$-approximate {Nash,CE,CCE}, if the number of episodes $K\geq\Omega(H^{4}S^{2}(\prod_{i=1}^{m}A_{i})\iota/\epsilon^{2})$.

${\rm Regret}_{\{\sf Nash,CE,CCE\}}(K)\leq\mathcal{O}(\sqrt{H^{3}S^{2}(\prod_{i=1}^{m}A_{i})T\iota})$.

In the situation where the Equilibrium subroutine is taken as Nash, Theorem 15 provides the sample complexity bound of Multi-Nash-VI algorithm to find an $\epsilon$-approximate Nash equilibrium and its regret bound. Compared with our earlier result in two-player zero-sum games (Theorem 3), here the sample complexity scales as $S^{2}H^{4}$ instead of $SH^{3}$. This is because the auxiliary bonus and Bernstein concentration technique do not apply here. Furthermore, the sample complexity is proportional to $\prod_{i=1}^{m}A_{i}$, which increases exponentially as the number of players increases.

We remark that while the Nash guarantee is the strongest among the three guarantees presented in Theorem 15, the runtime of Algorithm 3 in the Nash case is not guaranteed to be polynomial and in the worst case PPAD-hard (due to the hardness of the Nash subroutine). In contrast, the CE and CCE guarantees are weaker, but the corresponding algorithms are guaranteed to finish in polynomial time.

3 Multiplayer reward-free learning

We can also generalize VI-Zero to the multiplayer setting and obtain Algorithm 4, Multi-VI-Zero, which is almost the same as VI-Zero except that its exploration bonus $\beta_{t}$ is larger than that of VI-Zero by a $\sqrt{S}$ factor.

Conclusion

References

Appendix A Bellman Equations for Markov Games

In this section, we present the Bellman equations for different types of values in Markov games.

For any pair of Markov policy $(\mu,\nu)$, by definition of their values in (1) (2), we have the following Bellman equations:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{\mu,\nu}_{H+1}(s)=0$ for all $s\in\mathcal{S}$.

For any Markov policy $\mu$ of the max-player, by definition, we have the following Bellman equations for values of its best response:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{\mu,\dagger}_{H+1}(s)=0$ for all $s\in\mathcal{S}$.

Similarly, for any Markov policy $\nu$ of the min-player, we also have the following symmetric version of Bellman equations for values of its best response:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{\dagger,\nu}_{H+1}(s)=0$ for all $s\in\mathcal{S}$.

Finally, by definition of Nash equilibria in Markov games, we have the following Bellman optimality equations:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{{\star}}_{H+1}(s)=0$ for all $s\in\mathcal{S}$.

Appendix B Properties of Coarse Correlated Equilibrium

Recall the definition for CCE in our main paper (4), we restate it here after rescaling. For any pair of matrices $P,Q\in^{n\times m}$, the subroutine $\textsc{CCE}(P,Q)$ returns a distribution $\pi\in\Delta_{n\times m}$ that satisfies:

We make three remarks on CCE. First, a CCE always exists since a Nash equilibrium for a general-sum game with payoff matrices $(P,Q)$ is also a CCE defined by $(P,Q)$, and a Nash equilibrium always exists. Second, a CCE can be efficiently computed, since above constraints (5) for CCE can be rewritten as $n+m$ linear constraints on $\pi\in\Delta_{n\times m}$, which can be efficiently resolved by standard linear programming algorithm. Third, a CCE in general-sum games needs not to be a Nash equilibrium. However, a CCE in zero-sum games is guaranteed to be a Nash equalibrium.

Let $\pi=\textsc{CCE}(Q,Q)$, and $(\mu,\nu)$ be the marginal distribution over both players’ actions induced by $\pi$. Then $(\mu,\nu)$ is a Nash equilibrium for payoff matrix $Q$.

Let $N^{\star}$ be the value of Nash equilibrium for $Q$. Since $\pi=\textsc{CCE}(Q,Q)$, by definition, we have:

Intuitively, a CCE procedure can be used in Nash Q-learning for finding an approximate Nash equilibrium, because the values of upper confidence and lower confidence ($\overline{Q}$ and $\underline{Q}$) will be eventually very close, so that the preconditions of Proposition 17 becomes approximately satisfied.

Appendix C Proof for Section 3 – Optimistic Nash Value Iteration

As a result, the bonus terms can be written as

Let $c_{1}$ be some large absolute constant. Define event $E_{0}$ to be: for all $h,s,a,b,s^{\prime}$ and $k\in[K]$,

The proof is standard and folklore: apply standard concentration inequalities and then take a union bound. For completeness, we provide the proof of the second one here.

Now we can take a union bound over all $s,a,b,h,s^{\prime}$ and $t\in[K]$, and obtain that with probability at least $1-p$, for all $s,a,b,h,s^{\prime}$ and $t\in[K]$,

Note that the agent can reach each $(s,a,b,h)$ for at most $K$ times, this directly implies that the third inequality also holds with probability at least $1-p$. ∎

We begin with an auxiliary lemma bounding the lower-order term.

Suppose event $E_{0}$ holds, then there exists absolute constant $c_{2}$ such that: if function $g(s)$ satisfies $|g|(s)\leq(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s)$ for all $s$, then

where $(i)$ is by the second inequality in event $E_{0}$ and $(ii)$ is by AM-GM inequality. This proves the empirical version. Similarly, we can show

Combining the two bounds completes the proof. ∎

Now we can prove the upper and lower bounds are indeed upper and lower bounds of the best reponses.

Suppose event $E_{0}$ holds. Then for all $h,s,a,b$ and $k\in[K]$, we have

The proof is by backward induction. Suppose the bounds hold for the $Q$-values in the $(h+1)^{\rm th}$ step, we now establish the bounds for the $V$-values in the $(h+1)^{\rm th}$ step and $Q$-values in the $h^{\rm th}$-step. For any state $s$:

Similarly, we can show $\underline{V}^{k}_{h+1}(s)\leq V^{\mu^{k},\dagger}_{h+1}(s)$. Therefore, we have: for all $s$,

Now consider an arbitrary triple $(s,a,b)$ in the $h^{\rm th}$ step. We have

Invoking Lemma 19 with $g=V^{\dagger,\nu^{k}}_{h+1}-V^{\star}_{h+1}$,

By the first inequality in event $E_{0}$,

Plugging the two inequalities above back into (10) and recalling the definition of $\beta_{h}^{k}$ and $\gamma_{h}^{k}$, we obtain $\overline{Q}^{k}_{h}(s,a,b)\geq Q^{\dagger,\nu^{k}}_{h}(s,a,b)$. Similarly, we can show $\underline{Q}^{k}_{h}(s,a,b)\leq Q^{\mu^{k},\dagger}_{h}(s,a,b)$. ∎

Finally we come to the proof of Theorem 3.

Suppose event $E_{0}$ holds. We first upper bound the regret. By Lemma 20, the regret can be upper bounded by

For brevity’s sake, we define the following notations:

Let $\mathcal{F}_{h}^{k}$ be the $\sigma$-field generated by the following random variables:

It’s easy to check $\zeta_{h}^{k}$ and $\xi_{h}^{k}$ are martingale differences with respect to $\mathcal{F}_{h}^{k}$. With a slight abuse of notation, we use $\beta_{h}^{k}$ to refer to $\beta_{h}^{k}(s_{h}^{k},a_{h}^{k},b_{h}^{k})$ and $N_{h}^{k}$ to refer to $N_{h}^{k}(s_{h}^{k},a_{h}^{k},b_{h}^{k})$ in the following proof.

where $(i)$ and $(ii)$ follow from Lemma 19.

Define $c_{3}:=1+2c_{2}C$ and $\kappa:=1+c_{3}/H$. Recursing this argument for $h\in[H]$ and summing over $k$,

By Azuma-Hoeffding inequality, with probability at least $1-p$,

For the PAC guarantee, recall that we choose $\pi^{\text{out}}=\pi^{k^{\star}}$ such that $k^{\star}=\mathop{\rm argmin}_{k}\left(\overline{V}_{1}^{k}-\underline{V}_{1}^{k}\right)\left(s_{1}\right)$. As a result,

C.2 Proof of Theorem 4

We use the same notation as in Appendix C.1 except the form of bonus. Besides, we define the empirical variance operator

and the true (population) variance operator

As a result, the bonus terms can be written as

Let $c_{1}$ be some large absolute constant. Define event $E_{1}$ to be: for all $h,s,a,b,s^{\prime}$ and $k\in[K]$,

The proof of Lemma 21 is highly similar to that of Lemma 18. Specifically, the first two can be proved by following basically the same argument in Lemma 18; the third one is standard (e.g., equation (12) in Azar et al. (2017)). We omit the proof here.

Since the proof of Lemma 19 does not depend on the form of the bonus, it can also be applied in this section. As in Appendix C.1, we will prove the upper and lower bounds are indeed upper and lower bounds of the best reponses.

Suppose event $E_{1}$ holds. Then for all $h,s,a,b$ and $k\in[K]$, we have

The proof is by backward induction and very similar to that of Lemma 20. Suppose the bounds hold for the $Q$-values in the $(h+1)^{\rm th}$ step, we now establish the bounds for the $V$-values in the $(h+1)^{\rm th}$ step and $Q$-values in the $h^{\rm th}$-step.

The proof for the $V$-values is the same as (9).

For the $Q$-values, the decomposition (10) still holds and $(A)$ is bounded using Lemma 19 as before. The only difference is that we need to bound $(B)$ more carefully.

First, by the first inequality in event $E_{1}$,

By the relation of $V$-values in the $(h+1)^{\rm th}$ step,

Plugging the above inequalities back into (10) and recalling the definition of $\beta_{h}^{k}$ and $\gamma_{h}^{k}$ completes the proof. ∎

We need one more lemma to control the error of the empirical variance estimator:

Suppose event $E_{1}$ holds. Then for all $h,s,a,b$ and $k\in[K]$, we have

By Lemma 22, we have $\overline{V}^{k}_{h}(s)\geq V_{h}^{\pi^{k}}(s)\geq\underline{V}^{k}_{h}(s)$. As a result,

These terms can be bounded separately by using event $E_{1}$:

Combining with $H^{2}\sqrt{\frac{S\iota}{\max\{N_{h}^{k}(s,a,b),1\}}}\leq 1+\frac{H^{4}S\iota}{\max\{N_{h}^{k}(s,a,b),1\}}$ completes the proof. ∎

Finally we come to the proof of Theorem 4.

Suppose event $E_{1}$ holds. We define $\Delta_{h}^{k}$, $\zeta_{h}^{k}$ abd $\xi_{h}^{k}$ as in the proof of Theorem 3. As before we have

where $c_{4}$ is some absolute constant. Define $c_{5}:=4c_{2}c_{4}C+c_{3}$ and $\kappa:=1+c_{5}/H$. Plugging (18) back into (17), we have

Recursing this argument for $h\in[H]$ and summing over $k$,

The remaining steps are the same as that in the proof of Theorem 3 except that we need to bound the sum of variance term.

By the Law of total variation and standard martingale concentration (see Lemma C.5 in Jin et al. (2018) for a formal proof), with probability at least $1-p$, we have

Appendix D Proof for Section 4 – Reward-Free Learning

In this section, we prove Theorem 5 for the single reward function case, i.e., $N=1$. The proof for multiple reward functions ($N>1$) simply follows from taking a union bound, that is, replacing the failure probability $p$ by $Np$.

where $\iota=\log(SABT/p)$ and $C$ is some large absolute constant.

We use $\widehat{Q}^{k}$ and $\widehat{V}^{k}$ to denote the empirical optimal value functions of $\widehat{\mathcal{M}}^{k}$ as following.

We begin with stating a useful property of matrix game that will be frequently used in our analysis. Since its proof is quite simple, we omit it here.

Let $c_{1}$ be some large absolute constant such that $c_{1}^{2}+c_{1}\leq C$. Define event $E_{1}$ to be: for all $h,s,a,b,s^{\prime}$ and $k\in[K]$,

The proof is standard: apply concentration inequalities and then take a union bound. For completeness, we provide the proof of the third one here.

Now we can take a union bound over all $s,a,b,h,s^{\prime}$ and $t\in[K]$, and obtain that with probability at least $1-p$, for all $s,a,b,h,s^{\prime}$ and $t\in[K]$,

Note that the agent can reach each $(s,a,b,h)$ for at most $K$ times, so we conclude the third inequality also holds with probability at least $1-p$. ∎

The following lemma states that the empirical optimal value functions are close to the true optimal ones, and their difference is controlled by the exploration value functions calculated in Algorithm 2.

Suppose event $E_{1}$ (defined in Lemma 25) holds. Then for all $h,s,a,b$ and $k\in[K]$, we have,

Let’s prove by backward induction on $h$. The case of $h=H+1$ holds trivially.

Assume the conclusion hold for $(h+1)$’th step. For $h$’th step,

where $(i)$ follows from the induction hypothesis and event $E_{1}$, and $(ii)$ follows from the definition of ${\widetilde{Q}}^{k}_{h}$. By Lemma 24, we immediately obtain $|\widehat{V}_{h}^{k}(s)-V_{h}^{\star}(s)|\leq{\widetilde{V}}_{h}^{k}(s)$. ∎

Now, we are ready to establish the key lemma in our analysis using Lemma 26.

Suppose event $E_{1}$ (defined in Lemma 25) holds. Then for all $h,s,a,b$ and $k\in[K]$, we have

where $\alpha_{H+1}=0$ and $\alpha_{h}=[(1+\frac{1}{H})\alpha_{h+1}+\frac{1}{H}]\leq 4$.

We only prove the first set of inequalities. The second one follows exactly the same. Again, the proof is by performing backward induction on $h$. It is trivial to see the conclusion holds for $(H+1)$’th step with $\alpha_{H+1}=0$. Now, assume the conclusion holds for $(h+1)$’th step. For $h$’th step,

where the second inequality follows from the definition of event $E_{1}$.

We can control the term $(T_{1})$ by combining Lemma 26 and the induction hypothesis to bound $|V_{h+1}^{\dagger,\nu^{k}}-V^{\star}_{h+1}|$, and then applying the third inequality in event $E_{1}$:

The term $(T_{2})$ is bounded by directly applying the induction hypothesis

Plugging (29) and (30) into (28), we obtain

where $(i)$ follows from the definition of $\beta_{h}^{k}$, and $(ii)$ follows from the definition of ${\widetilde{Q}}^{k}_{h}$. Therefore, by (31), choosing $\alpha_{h}=[(1+\frac{1}{H})\alpha_{h+1}+\frac{1}{H}]$ suffices for the purpose of induction.

Now, let’s prove the inequality for $V$ functions.

where $(i)$ follows from the definition of $\widehat{V}_{h}^{k}$ and $V^{\dagger,\nu^{k}}_{h}$, and $(ii)$ uses (31) and Lemma 24. ∎

For any $p\in(0,1]$, choose the exploration bonus $\beta_{t}$ in Algrothm 2 as (20). Then, with probability at least $1-p$,

Recall that $\text{out}=\arg\min_{k\in[K]}{\widetilde{V}}^{k}_{h}(s)$. By Lemma 27 and Theorem 28, with probability at least $1-2p$,

D.2 Vanilla Nash Value Iteration

Here, we provide one optional algorithm, Vanilla Nash VI, for computing the Nash equilibrium policy for a known model. Its only difference from the value iteration algorithm for MDPs is that the maximum operator is replaced by the minimax operator in Line 7. We remark that the Nash equilibrium for a two-player zero-sum game can be computed in polynomial time.

By recalling the definition of best responses in Appendix A, one can directly see that the output policy $(\hat{\mu},\hat{\nu})$ is a Nash equilibrium for $\widehat{\mathcal{M}}$.

D.3 Proof of Theorem 6

In this section, we first prove a $\Theta(AB/\epsilon^{2})$ lower bound for reward-free learning of matrix games, i.e., $S=H=1$, and then generalize it to $\Theta(SABH^{2}/\epsilon^{2})$ for reward-free learning of Markov games.

In the matrix game, let the max-player pick row and the min-player pick column. We consider the following family of Bernoulli matrix games:

where in matrix game $\mathcal{M}^{a^{\star}b^{\star}}$, the reward is sampled from ${\rm Bernoulli}(\mathcal{M}^{a^{\star}b^{\star}}_{ab})$ if the max-player picks the $a$’th row and the min-player picks the $b$’th column.

Above, we visualize $\mathcal{M}^{a^{\star}b^{\star}}$ by using {\color[rgb]{1,0,0}+} and {\color[rgb]{0,0,1}-} to represent $1/2+\epsilon$ and $1/2-\epsilon$, respectively. It is direct to see that the optimal (Nash equilibrium) policy for the max-player is always picking the $a^{\star}$’th row. If the max-player picks the $a^{\star}$’th row with probability smaller than $2/3$, it is at least $\epsilon/10$ suboptimal.

We simply define $\hat{\mathcal{A}}$ as running algorithm $\mathcal{A}$ and choosing the most played row by its output policy as the guess for $a^{\star}$. Because any $\epsilon/10$-optimal policy must play $a^{\star}$ with probability at least $2/3$, we obtain $\hat{\mathcal{A}}$ will correctly identify $a^{\star}$ with probability at least $p$. ∎

Lemma 29 directly implies that in order to prove the desired lower bound for reward-free matrix games:

for any reward-free algorithm $\mathcal{A}$ using at most $N=AB/(10^{3}\epsilon^{2})$ samples, there exists a matrix game $\mathcal{M}^{a^{\star}b^{\star}}$ in $\mathfrak{M}(\epsilon)$ such that when running $\mathcal{A}$ on $\mathcal{M}^{a^{\star}b^{\star}}$, it will output a policy that is at least $\epsilon/10$ suboptimal for the max-player with probability at least $1/4$,

it suffices to prove the following claim:

for any reward-free algorithm $\hat{\mathcal{A}}$ using at most $N=AB/(10^{3}\epsilon^{2})$ samples, there exists a matrix game $\mathcal{M}^{a^{\star}b^{\star}}$ in $\mathfrak{M}(\epsilon)$ such that when running $\hat{\mathcal{A}}$ on $\mathcal{M}$, it will fail to identify the optimal row with probability at least $1/4$.

By Lemma 29, the existence of such ’ideal’ $\mathcal{A}$ implies the existence of an ’ideal’ $\hat{\mathcal{A}}$, so to prove such ’ideal’ $\mathcal{A}$ does not exist (Claim 30), it suffices to show such ’ideal’ $\hat{\mathcal{A}}$ does not exist (Claim 31).

WLOG, we assume $\hat{\mathcal{A}}$ is deterministic. Since $\hat{\mathcal{A}}$ is reward-free, being deterministic means that in the exploration phase algorithm $\hat{\mathcal{A}}$ always pulls each arm $(a,b)$ for some fixed $n(a,b)$ times (because there is no information revealed in this phase), and in the planning phase it outputs a guess for $a^{\star}$, which is a deterministic function of the reward information revealed.

$L$: the stochastic reward information revealed after algorithm $\hat{\mathcal{A}}$’s pulling.

$f(L)$: the output of $\hat{\mathcal{A}}$ based on the stochastic reward information $L$ revealed. More precisely, $f$ is function mapping from $^{N}$ to $[A]$.

The arguments in proving Claim 31 basically follows the same line in proving lower bounds for multi-arm bandits (e.g., see Lattimore and Szepesvári, 2018).

D.3.2 Reward-free learning of Markov games

Now let’s generalize the $\Theta(AB/\epsilon^{2})$ lower bound for reward-free learning of matrix games to $\Theta(SABH^{2}/\epsilon^{2})$ for reward-free learning of Markov games. We can follow the same way of generalizing a lower bound for multi-arm bandits to a lower bound for MDPs (see e.g., Dann and Brunskill, 2015; Lattimore and Szepesvári, 2018; Zhang et al., 2020b).

Proof sketch. Given the family of Bernoulli matrix games $\mathfrak{M}(\cdot)$ defined in (34), we simply construct a Markov game to consist of $SH$ Bernoulli matrix games $\{M^{s,h}\}_{(s,h)\in[S]\times[H]}$ where $M^{s,h}$’s are sampled independently and identically from the uniform distribution over $\mathfrak{M}(\epsilon/H)$. We will define the transition measure to be totally ’uniform at random’ so that in each episode the agent will always reach each $M^{s,h}$ with probability $1/S$ (it is not $1/(SH)$ because in each episode the agent can visit $H$ matrix games). As a result, to guarantee $\epsilon$-optimality, the output policy must be at least $2\epsilon/H$-optimal for at least $SH/2$ different $M^{s,h}$’s. Recall Claim 30 shows learning a $2\epsilon/H$-optimal policy for a single $M^{s,h}$ requires $\Omega(H^{2}AB/\epsilon^{2})$ samples. Therefore, we need $\Omega(H^{3}AB/\epsilon^{2})$ samples in total for learning $SH/2$ different $M^{s,h}$’s.

Below, we provide a rigorous proof where the constants may be slightly different from those in our sketch. We remark that although the notations we will use are involved, they are only introduced for rigorousness and there is no real technical difficulty or new informative idea in the following proof.

We define the following family of Markov games:

where MG $\mathcal{J}(\bm{a}^{\star},\bm{b}^{\star})$ is defined as

States and actions: $\mathcal{J}(\bm{a}^{\star},\bm{b}^{\star})$ is a finite-horizon MG with $S+1$ states and of length $H+1$. There is a fixed initial state $s_{0}$ in the first step, $S$ states $\{s_{1},\ldots,s_{S}\}$ in the remaining steps. The two players have $A$ and $B$ actions, respectively.

Rewards: there is no reward in the first step. For the remaining steps $h\in\{2,\ldots,H+1\}$, if the agent takes action $(a,b)$ at state $s_{i}$ in the $h^{\rm th}$ step, it will receive a binary reward sampled from

Transitions: The agent always starts at a fixed initial state $s_{0}$ in the first step Regardless of the current state, actions and index of steps, the agent will always transit to one of $s_{1},\ldots,s_{S}$ uniformly at random.

It is direct to see that $\mathcal{J}(\bm{a}^{\star},\bm{b}^{\star})$ is a collection of $SH$ matrix games from $\mathfrak{M}(\epsilon/H)$. Therefore, the optimal policy for the max-player is to always pick action $\bm{a}^{\star}_{h-1,i}$ whenever it reaches state $s_{i}$ at step $h$ ($h\geq 2$).

Now, let’s use $\mathfrak{J}(\epsilon)$ to prove the $\Theta(SABH^{2}/\epsilon^{2})$ lower bound (in terms of number of episodes) for reward-free learning of Markov games. We start by proving an analogue of Lemma 29.

Denote by $\pi$ the output policy for the max player. Denote by $Z$ the collection of $(h,i)$’s in $[H]\times[S]$ such that $\pi_{h+1}(\bm{a}^{\star}_{h,i}\mid s_{i})\leq 2/3$.

Observe that each time the max player picks a suboptimal action, it will incur an $2\epsilon/H$ suboptimality in expectation. As a result, if $\pi$ is at most $\epsilon/10^{3}$-suboptimal, we must have

which implies $|Z|\leq SH/500$, that is, for at most $\left\lfloor SH/500\right\rfloor$ different $(h,i)$’s, $\pi_{h+1}(\bm{a}^{\star}_{h,i}\mid s_{i})\leq 2/3$. Therefore, we can simply pick $\mathop{\rm argmax}_{a}\pi_{h+1}(a\mid s_{i})$ as the guess for $\bm{a}^{\star}_{h,i}$. Since policy $\pi$ is at most $\epsilon/10^{3}$ suboptimal with probability at least $p$, our guess will be correct for at least $SH-\left\lfloor SH/500\right\rfloor$ different $(s,h)$ pairs also with probability no smaller than $p$. ∎

Similar to the funtion of Lemma 29, Lemma 34 directly implies that in order to prove the desired lower bound for reward-free learning of Markov games:

for any reward-free algorithm $\mathcal{A}$ that interacts with the environment for at most $K=SABH^{2}/(10^{4}\epsilon^{2})$ episodes, there exists $\mathcal{J}\in\mathfrak{J}(\epsilon)$ such that when running $\mathcal{A}$ on $\mathcal{J}$, it will output a policy that is at least $\epsilon/10^{3}$ suboptimal for the max-player with probability at least $1/4$,

it suffices to prove the following claim:

for any reward-free learning algorithm $\hat{\mathcal{A}}$ that interacts with the environment for at most $K=ABSH^{2}/(10^{4}\epsilon^{2})$ episodes, there exists $\mathcal{J}\in\mathfrak{J}(\epsilon)$ such that when running $\hat{\mathcal{A}}$ on $\mathcal{J}$, it will fail to correctly identify $\bm{a}^{\star}_{h,i}$ for at least $\left\lfloor SH/500\right\rfloor+1$ different $(h,i)$ pairs with probability at least $1/4$.

We prove by contradiction. Suppose for any $\mathcal{J}\in\mathfrak{J}(\epsilon)$, $\hat{\mathcal{A}}$ can identify the optimal actions for at least $SH-\left\lfloor SH/500\right\rfloor$ different $(s,h)$ pairs with probability larger than $3/4$. Then we have

For technical reason, we introduce a new MG $\mathcal{J}_{-(h^{\prime},i^{\prime})}(\bm{a}^{\star},\bm{b}^{\star})$ as below:

States, actions and transitions: same as $\mathcal{J}(\bm{a}^{\star},\bm{b}^{\star})$.

Rewards: there is no reward in the first step. For the remaining steps $h\in\{2,\ldots,H+1\}$, if the agent takes action $(a,b)$ at state $s_{i}$ in the $h^{\rm th}$ step such that $(h-1,i)\neq(h^{\prime},i^{\prime})$, it will receive a binary reward sampled from