$d_{\mathsf{b}}\left(s,a,b\right)=\begin{cases}\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)},&\text{if
}s=0\\\
\frac{1}{AB}\left(1-\frac{AB}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\right),&\text{if
}s=1\\\ 0,&\text{if }s\geq 2\end{cases}$ (D.6)

for all $(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$, where
$C_{\mathsf{clipped}}^{\star}$ is allowed to be any given quantity satisfying
$C_{\mathsf{clipped}}^{\star}\geq\frac{2AB}{S(A+B)}$. In other words, for any
given $s\in\mathcal{S}$, each action pair
$(a,b)\in\mathcal{A}\times\mathcal{B}$ is sampled with the same rate.

Owing to the simple structure of the above $\mathcal{MG}_{\theta}$, we are
able to compute its value functions and the Nash equilibrium. Before
proceeding, we find it convenient to define two action subsets

$\mathcal{A}_{p,\theta}\coloneqq\left\\{a\in\mathcal{A}:\theta_{a}=p\right\\}\qquad\text{and}\qquad\mathcal{A}_{q,\theta}\coloneqq\left\\{a\in\mathcal{A}:\theta_{a}=q\right\\}.$
(D.7)

######  Lemma 6.

Consider the Markov game $\mathcal{MG}_{\theta}$. For any policy pair
$(\mu,\nu)$, the value function in $\mathcal{MG}_{\theta}$ obeys

$\displaystyle V^{\mu,\nu}\left(0\right)$
$\displaystyle=\frac{1}{1-\gamma+\gamma\mu_{p,\theta}\nu_{0}\left(1-p\right)+\gamma\left(1-\mu_{p,\theta}\right)\nu_{0}\left(1-q\right)},$
$\displaystyle V^{\mu,\nu}\left(s\right)$
$\displaystyle=0\qquad\qquad\text{for all }s\geq 1,$

where

$\mu_{p,\theta}\coloneqq\sum_{a\in\mathcal{A}_{p,\theta}}\mu(a\,|\,0)\qquad\text{and}\qquad\nu_{0}\coloneqq\nu(0\,|\,0).$
(D.8)

In addition, if we define two policies $\mu_{\theta}^{\star}$ and
$\nu_{\theta}^{\star}$ as follows

$\displaystyle\mu_{\theta}^{\star}\left(a\,|\,s\right)$
$\displaystyle=\frac{1}{|\mathcal{A}_{p,\theta}|}\operatorname{\mathds{1}}\left\\{a\in\mathcal{A}_{p,\theta}\right\\},\qquad\forall\,s\in\mathcal{S},a\in\mathcal{A},$
(D.9a) $\displaystyle\nu_{\theta}^{\star}\left(b\,|\,s\right)$
$\displaystyle=\operatorname{\mathds{1}}\left\\{b=0\right\\},\qquad\qquad\quad\quad\forall\,s\in\mathcal{S},b\in\mathcal{B},$
(D.9b)

then the policy pair $(\mu_{\theta}^{\star},\nu_{\theta}^{\star})$ is a Nash
equilibrium of $\mathcal{MG}_{\theta}$. Furthermore, we have

$\big{\\{}\mathcal{MG}_{\theta},\rho,d_{\mathsf{b}}\big{\\}}\in\mathsf{MG}\big{(}C_{\mathsf{clipped}}^{\star}\big{)}.$

###### Proof.

See Appendix E.1. ∎

We shall also make note of two immediate consequences of Lemma 6. First, Lemma
6 allows us to compute the corresponding value function $V^{\star}$ of the
unique Nash equilibrium in $\mathcal{M\mathcal{G}_{\theta}}$ as follows:

$V^{\star}\left(0\right)=\frac{1}{1-\gamma p},$ (D.10a) given that
$\mu_{p,\theta}=1$ and $\nu_{0}=1$ hold under the NE
$(\mu_{\theta}^{\star},\nu_{\theta}^{\star})$. In addition, Lemma 6 tells us
that for any policy $\mu$ of the max-player, the optimal value function for
the min-player obeys $V^{\mu,\star}(0)=\frac{1}{1-\gamma
p+\gamma\left(1-\mu_{p,\theta}\right)\left(p-q\right)},$ (D.10b)

given that the best response of the min-player is to set $\nu_{0}=1$.

###  D.2 Identifying sufficient statistics for the parameter $\theta$

Denote by $f_{\theta}$ the probability mass function of a single sample
transition $(s_{i},a_{i},b_{i},s_{i}^{\prime})$ such that

$\left(s_{i},a_{i},b_{i}\right)\sim d_{\mathsf{b}},\qquad s_{i}^{\prime}\sim
P_{\theta}\left(\cdot\,|\,s_{i},a_{i},b_{i}\right).$

In view of the definition of $d_{\mathsf{b}}$ in (D.6), we can write

$f_{\theta}\left(s_{i},a_{i},b_{i},s_{i}^{\prime}\right)=\begin{cases}\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\theta_{a_{i}}&\text{if
}s_{i}=0,b_{i}=0,s_{i}^{\prime}=0,\\\
\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\left(1-\theta_{a_{i}}\right)&\text{if
}s_{i}=0,b_{i}=0,s_{i}^{\prime}=1,\\\
\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}&\text{if
}s_{i}=0,b_{i}\geq 1,s_{i}^{\prime}=0,\\\
\frac{1}{AB}\left(1-\frac{AB}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\right)&\text{if
}s_{i}=s_{i}^{\prime}=1,\\\ 0&\text{otherwise}.\end{cases}$

Therefore, the probability mass function of the offline dataset
$\\{(s_{i},a_{i},b_{i},s_{i}^{\prime})\\}_{i=1}^{N}$ containing $N$
independent data is given by

$\displaystyle\prod_{i=1}^{N}f_{\theta}\left(s_{i},a_{i},b_{i},s_{i}^{\prime}\right)$
$\displaystyle=\left[\frac{1}{AB}\left(1-\frac{AB}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\right)\right]^{L}\left[\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\right]^{J}$
$\displaystyle\qquad\cdot\prod_{a\in\mathcal{A}}\left[\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\theta_{a}\right]^{X_{a}}\left[\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\left(1-\theta_{a}\right)\right]^{M_{a}-X_{a}}$
$\displaystyle=\left[\frac{1}{AB}\left(1-\frac{AB}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\right)\right]^{L}\left[\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\right]^{N+J-L}\prod_{a\in\mathcal{A}}\theta_{a}^{X_{a}}\left(1-\theta_{a}\right)^{M_{a}-X_{a}},$
(D.11)

where we define

$\displaystyle J$
$\displaystyle\coloneqq\sum_{i=1}^{N}\operatorname{\mathds{1}}\\{s_{i}=s_{i}^{\prime}=0,b_{i}\geq
1\\},$ $\displaystyle L$
$\displaystyle\coloneqq\sum_{i=1}^{N}\operatorname{\mathds{1}}\\{s_{i}=s_{i}^{\prime}=1\\},$
$\displaystyle X_{a}$
$\displaystyle\coloneqq\sum_{i=1}^{N}\operatorname{\mathds{1}}\left\\{s_{i}=0,a_{i}=a,b_{i}=0,s_{i}^{\prime}=0\right\\},\qquad\forall
a\in\mathcal{A},$ $\displaystyle M_{a}$
$\displaystyle\coloneqq\sum_{i=1}^{N}\operatorname{\mathds{1}}\left\\{s_{i}=0,a_{i}=a,b_{i}=0\right\\},\qquad\forall
a\in\mathcal{A}.$

By the factorization theorem (see, e.g., Shao, (2003, Theorem 2.2)), the
expression (D.11) implies that

$(X,M)\qquad\text{with }X=[X_{a}]_{a\in\mathcal{A}}\text{ and
}M=[M_{a}]_{a\in\mathcal{A}}$ (D.12)

forms a sufficient statistic for the underlying parameter $\theta$.

###  D.3 Establishing the minimax lower bound

In view of (D.10) and our choice of $\rho$ (cf. (D.5)), we can obtain — for
any policy $\mu$ of the max-player — that

$\displaystyle V^{\star}\left(\rho\right)-V^{\mu,\star}\left(\rho\right)$
$\displaystyle=V^{\star}\left(0\right)-V^{\mu,\star}\left(0\right)=\frac{1}{1-\gamma
p}-\frac{1}{1-\gamma p+\gamma\left(1-\mu_{p,\theta}\right)\left(p-q\right)}$
$\displaystyle=\frac{\gamma\left(1-\mu_{p,\theta}\right)\left(p-q\right)}{\left(1-\gamma
p\right)\left[1-\gamma
p+\gamma\left(1-\mu_{p,\theta}\right)\left(p-q\right)\right]}$
$\displaystyle=\left(1-\mu_{p,\theta}\right)\frac{28\left(1-\gamma\right)^{2}\varepsilon}{\left[1-\gamma\left(\gamma+14\frac{\left(1-\gamma\right)^{2}\varepsilon}{\gamma}\right)\right]\left[1-\gamma\left(\gamma+14\frac{\left(1-\gamma\right)^{2}\varepsilon}{\gamma}\right)+\left(1-\mu_{p,\theta}\right)28\left(1-\gamma\right)^{2}\varepsilon\right]}$
$\displaystyle=\left(1-\mu_{p,\theta}\right)\frac{28\varepsilon}{\left[1+\gamma-14\left(1-\gamma\right)\varepsilon\right]\left[1+\gamma+\left(1-2\mu_{p,\theta}\right)14\left(1-\gamma\right)\varepsilon\right]}$
$\displaystyle\geq\left(1-\mu_{p,\theta}\right)6\varepsilon=6\varepsilon\sum_{a\in\mathcal{A}_{q,\theta}}\mu\left(a\,|\,0\right)=6\varepsilon\sum_{a\in\mathcal{A}}\mu\left(a\,|\,0\right)\operatorname{\mathds{1}}\left\\{\theta_{a}=q\right\\},$
(D.13)

where the penultimate relation holds provided that
$\varepsilon\leq\frac{1}{42(1-\gamma)}$. As a consequence, we have

$\displaystyle\underset{(\widehat{\mu},\widehat{\nu})}{\inf}\underset{\\{\mathcal{MG},\rho,d_{\mathsf{b}}\\}\in\mathsf{MG}(C_{\mathsf{clipped}}^{\star})}{\sup}\mathbb{E}\left[V^{\star,\widehat{\nu}}\left(\rho\right)-V^{\widehat{\mu},\star}\left(\rho\right)\right]$
$\displaystyle\geq\underset{\widehat{\mu}}{\inf}\underset{\\{\mathcal{MG},\rho,d_{\mathsf{b}}\\}\in\mathsf{MG}(C_{\mathsf{clipped}}^{\star})}{\sup}\mathbb{E}\left[V^{\star}\left(\rho\right)-V^{\widehat{\mu},\star}\left(\rho\right)\right]$
$\displaystyle\geq\underset{\widehat{\mu}}{\inf}\underset{\mathcal{MG}_{\theta}:\theta\in\left\\{p,q\right\\}^{A}}{\sup}\mathbb{E}\left[V^{\star}\left(\rho\right)-V^{\widehat{\mu},\star}\left(\rho\right)\right]$
$\displaystyle\geq
6\varepsilon\,\underset{\widehat{\mu}}{\inf}\underset{\mathcal{MG}_{\theta}:\theta\in\left\\{p,q\right\\}^{A}}{\sup}\mathbb{E}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\operatorname{\mathds{1}}\left\\{\theta_{a}=q\right\\}\right],$
(D.14)

where the first relation holds since $V^{\star,\widehat{\nu}}(s)\geq
V^{\mu^{\star},\widehat{\nu}}(s)\geq
V^{\mu^{\star},\nu^{\star}}(s)=V^{\star}(s)$, and the last line follows from
(D.13). Here, the expectation is taken over the randomness of the data
distribution induced by $d_{\mathsf{b}}$ and that of the transition kernel of
the corresponding Markov game.

To further lower bound (D.14), we define $\mathcal{U}$ to be the uniform
distribution over $\\{p,q\\}^{A}$ (namely, a random vector
$\theta\sim\mathcal{U}$ obeys
$\theta_{a}\overset{\text{i.i.d.}}{=}\begin{cases}p&\text{w.p. }0.5\\\
q&\text{w.p. }0.5\end{cases}$ for all $a\in\mathcal{A}$). It is readily seen
that

$\displaystyle\underset{\widehat{\mu}}{\inf}\underset{\mathcal{MG}_{\theta}:\theta\in\left\\{p,q\right\\}^{A}}{\sup}\mathbb{E}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\operatorname{\mathds{1}}\left\\{\theta_{a}=q\right\\}\right]$
$\displaystyle\overset{\text{(i)}}{\geq}\underset{\widehat{\mu}}{\inf}\,\mathbb{E}_{\theta\sim\mathcal{U}}\left[\mathbb{E}_{\mathcal{MG}_{\theta}}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\operatorname{\mathds{1}}\left\\{\theta_{a}=q\right\\}\right]\right]$
$\displaystyle=\underset{\widehat{\mu}}{\inf}\,\mathop{\mathbb{E}}\limits_{\mathcal{MG}_{\theta},\theta\sim\mathcal{U}}\left[\mathbb{E}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\operatorname{\mathds{1}}\left\\{\theta_{a}=q\right\\}\,|\,X,M\right]\right]$
$\displaystyle\overset{\text{(ii)}}{=}\underset{\widehat{\mu}}{\inf}\,\mathop{\mathbb{E}}\limits_{\mathcal{MG}_{\theta},\theta\sim\mathcal{U}}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\mathbb{E}\Big{[}\operatorname{\mathds{1}}\left\\{\theta_{a}=q\right\\}\,|\,X,M\Big{]}\right]$
$\displaystyle\overset{\text{(iii)}}{=}\underset{\widehat{\mu}}{\inf}\,\mathop{\mathbb{E}}\limits_{\mathcal{MG}_{\theta},\theta\sim\mathcal{U}}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\mathbb{P}\left(\theta_{a}=q\,|\,X_{a},M_{a}\right)\right],$
(D.15)

where the expectations appear after (i) are taken w.r.t. the randomness of
data distribution induced by $d_{\mathsf{b}}$ and the transition kernel of
$\mathcal{MG}_{\theta}$, with $\theta$ following a prior distribution
$\mathcal{U}$. To see why (ii) holds, note that it suffices to consider
$\widehat{\mu}$ that is a measurable function of the sufficient statistic
$(X,M$) (see Johnstone, (2017, Proposition 3.13)); with regards (iii), we note
that it holds since $\\{X_{a^{\prime}},M_{a^{\prime}}\\}_{a^{\prime}\neq a}$
is independent of $\theta_{a}$ conditional on $(X_{a},M_{a})$. To further
lower bound (D.15), we look at the following two cases separately.

##### Case 1: when the sample size $N$ is not too small.

Consider the case where

$N\geq\widetilde{C}\frac{S\left(A+B\right)C_{\mathsf{clipped}}^{\star}\log\left(A+B\right)}{1-\gamma}=\frac{1}{d_{\mathsf{b}}\left(0,a,0\right)}\cdot\frac{\widetilde{C}\log\left(A+B\right)}{1-\gamma}$
(D.16)

holds for some sufficiently large constant $\widetilde{C}>0$. In order to be
compatible with the assumption

$N<\frac{c_{2}S\left(A+B\right)C_{\mathsf{clipped}}^{\star}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log\left(A+B\right)}=\frac{1}{d_{\mathsf{b}}\left(0,a,0\right)}\cdot\frac{c_{2}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log\left(A+B\right)},$
(D.17)

it suffices to focus on the regime where

$\varepsilon\leq\varepsilon_{0}\coloneqq\sqrt{\frac{c_{2}}{2\widetilde{C}}}\frac{1}{\left(1-\gamma\right)\log\left(A+B\right)}.$
(D.18)

In order to understand (D.15), we need to take a look at $M_{a}$ and $X_{a}$.
To begin with, it is straightforward to check that
$M_{a}\sim\mathsf{Binomial}\big{(}N,d_{\mathsf{b}}(0,a,0)\big{)}$. When $N$ is
sandwiched between (D.16) and (D.17), we can establish the following high-
probability bound on $M_{a}$.

######  Lemma 7.

Suppose that $\widetilde{C}$ is sufficiently large, and
$\varepsilon\leq\frac{1}{(1-\gamma)\log A}$. Then we have

$\mathbb{P}\left(\frac{c_{3}\log A}{1-\gamma}\leq
M_{a}\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}\right)\geq 1-\frac{2}{A^{4}},$ (D.19)

where $c_{3}=\widetilde{C}/2$ and $c_{4}=c_{2}+\sqrt{8c_{2}/c_{\mathsf{ch}}}$,
with $c_{\mathsf{ch}}>0$ some universal constant independent of $c_{2}$.

###### Proof.

See Appendix E.2.∎

In words, $M_{a}$ is guaranteed to reside within an interval
$\big{[}\frac{c_{3}\log
A}{1-\gamma},\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}\big{]}$. In addition, in order to bound
$\mathbb{P}\left(\theta_{a}=q\,|\,X_{a},M_{a}\right)$ in (D.15), we seek to
first investigate the properties of $X_{a}\mid\\{\theta_{a},M_{a}=M\\}$ for
some $M\in\big{[}\frac{c_{3}\log
A}{1-\gamma},\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}\big{]}$. Clearly, conditional on $\theta_{a}$ and $M_{a}=M$, the random
variable $X_{a}$ is distributed as $\mathsf{Binomial}(M,\theta_{a})$. We make
note of the following useful result regarding binomial random variables.

######  Lemma 8.

Suppose that $\widetilde{C}$ is sufficiently large and $c_{2}$ is sufficiently
small. Consider any integer $M$ satisfying

$\frac{c_{3}\log A}{1-\gamma}\leq
M\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log A},$ (D.20)

and generate $B_{p}\sim\mathsf{Binomial}(M,p)$ and
$B_{q}\sim\mathsf{Binomial}(M,q)$. Then there exists a set $E_{M}\subseteq[M]$
such that

$\mathbb{P}\left(B_{p}\in E_{M}\right)\geq
1-\frac{2}{A^{4}},\qquad\mathbb{P}\left(B_{q}\in E_{M}\right)\geq
1-\frac{2}{A^{4}},$ (D.21)
$\text{and}\qquad\frac{\mathbb{P}\left(B_{q}=n\right)}{\mathbb{P}\left(B_{p}=n\right)}\geq\frac{1}{2},\qquad\forall
n\in E_{M}.$ (D.22)

###### Proof.

See Appendix E.3.∎

In words, when $M$ falls within the range (D.20), there exists a high-
probability set $E_{M}$ such that it is not that easy to differentiate
$\mathsf{Binomial}(M,p)$ and $\mathsf{Binomial}(M,q)$. This result motivates
us to pay particular attention the following set $E\subseteq\mathbb{N}^{2}$:

$E\coloneqq\left\\{\left(x,m\right)\in\mathbb{N}^{2}:x\in
E_{m},\frac{c_{3}\log A}{1-\gamma}\leq
m\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log A}\right\\}.$

It is seen that

$\displaystyle\mathbb{P}\Big{(}\left(X_{a},M_{a}\right)\in
E\,|\,\theta_{a}=p\Big{)}$
$\displaystyle=\mathbb{E}\Big{[}\mathbb{P}\big{(}\left(X_{a},M_{a}\right)\in
E\,|\,M_{a},\theta_{a}=p\big{)}\,|\,\theta_{a}=p\Big{]}=\mathbb{E}\Big{[}\mathbb{P}\left(X_{a}\in
E_{M_{a}}\,|\,M_{a},\theta_{a}=p\right)\,|\,\theta_{a}=p\Big{]}$
$\displaystyle\geq\mathbb{E}\left[\mathbb{P}\left(X_{a}\in
E_{M_{a}}\,|\,M_{a},\theta_{a}=p\right)\operatorname{\mathds{1}}\left\\{\frac{c_{3}\log
A}{1-\gamma}\leq
M_{a}\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}\right\\}\,|\,\theta_{a}=p\right]$
$\displaystyle\overset{\text{(i)}}{\geq}\mathbb{E}\left[\left(1-\frac{2}{A^{4}}\right)\operatorname{\mathds{1}}\left\\{\frac{c_{3}\log
A}{1-\gamma}\leq
M_{a}\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}\right\\}\,|\,\theta_{a}=p\right]$
$\displaystyle\overset{\text{(ii)}}{=}\left(1-\frac{2}{A^{4}}\right)\mathbb{P}\left(\frac{c_{3}\log
A}{1-\gamma}\leq
M_{a}\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log A}\right)$
$\displaystyle\overset{\text{(iii)}}{\geq}\left(1-\frac{2}{A^{4}}\right)^{2}\geq
1-\frac{4}{A^{4}}.$ (D.23)

Here, (i) utilizes Lemma 8, (ii) is valid since $\theta_{a}$ is independent of
$M_{a}$, whereas (iii) follows from (E.9) and (E.10). Similarly, one can show
that

$\mathbb{P}\Big{(}\left(X_{a},M_{a}\right)\in E\,|\,\theta_{a}=q\Big{)}\geq
1-\frac{4}{A^{4}}.$ (D.24)

Taking (D.23) and (D.24) collectively yields

$\displaystyle\mathbb{P}\Big{(}\left(X_{a},M_{a}\right)\in E\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\left(X_{a},M_{a}\right)\in
E\,|\,\theta_{a}=p\Big{)}\mathbb{P}\left(\theta_{a}=p\right)+\mathbb{P}\Big{(}\left(X_{a},M_{a}\right)\in
E\,|\,\theta_{a}=q\Big{)}\mathbb{P}\left(\theta_{a}=q\right)$
$\displaystyle\geq\frac{1}{2}\left(1-\frac{4}{A^{4}}\right)+\frac{1}{2}\left(1-\frac{4}{A^{4}}\right)=1-\frac{4}{A^{4}}.$
(D.25)

A little calculation shows that: when $(x_{a},m_{a})\in E$, we have

$\displaystyle\mathbb{P}\left(\theta_{a}=q\,|\,X_{a}=x_{a},M_{a}=m_{a}\right)=\frac{\mathbb{P}\left(\theta_{a}=q,X_{a}=x_{a}\,|\,M_{a}=m_{a}\right)}{\mathbb{P}\left(X_{a}=x_{a}\,|\,M_{a}=m_{a}\right)}$
$\displaystyle=\frac{\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=q,M_{a}=m_{a}\right)\mathbb{P}\left(\theta_{a}=q\,|\,M_{a}=m_{a}\right)}{\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=p,M_{a}=m_{a}\right)\mathbb{P}\left(\theta_{a}=p\,|\,M_{a}=m_{a}\right)+\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=q,M_{a}=m_{a}\right)\mathbb{P}\left(\theta_{a}=q\,|\,M_{a}=m_{a}\right)}$
$\displaystyle\overset{\text{(i)}}{=}\frac{\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=q,M_{a}=m_{a}\right)\mathbb{P}\left(\theta_{a}=q\right)}{\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=p,M_{a}=m_{a}\right)\mathbb{P}\left(\theta_{a}=p\right)+\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=q,M_{a}=m_{a}\right)\mathbb{P}\left(\theta_{a}=q\right)}$
$\displaystyle\overset{\text{(ii)}}{=}\frac{\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=q,M_{a}=m_{a}\right)}{\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=p,M_{a}=m_{a}\right)+\mathbb{P}\left(X_{a}=x_{a}\,|\,\theta_{a}=q,M_{a}=m_{a}\right)}$
$\displaystyle\overset{\text{(iii)}}{=}\frac{\mathbb{P}\left(B_{q}=x_{a}\right)}{\mathbb{P}\left(B_{p}=x_{a}\right)+\mathbb{P}\left(B_{q}=x_{a}\right)}\overset{\text{(iv)}}{\geq}\frac{1/2}{1+1/2}=\frac{1}{3},$
(D.26)

where we let $B_{p}$ and $B_{q}$ be two random variables distributed as
$B_{p}\sim\mathsf{Binomial}(m_{a},p)$ and
$B_{q}\sim\mathsf{Binomial}(m_{a},q)$. Here, (i) relies on the fact that
$\theta_{a}$ is independent from $M_{a}$; (ii) comes from the fact that
$\mathbb{P}\left(\theta_{a}=p\right)=\mathbb{P}\left(\theta_{a}=q\right)=1/2$;
(iii) follows since conditional on $M_{a}=m_{a}$ and $\theta_{a}=p$ (resp.
$\theta_{a}=q$), the distribution of $X_{a}$ is $\mathsf{Binomial}(m_{a},p)$
(resp. $\mathsf{Binomial}(m_{a},q)$); and (iv) follows from Lemma 8 given that
$(x_{a},m_{a})\in E$. We can thus conclude that

$\displaystyle\underset{(\widehat{\mu},\widehat{\nu})}{\inf}\underset{\\{\mathcal{MG},\rho,d_{\mathsf{b}}\\}\in\mathsf{MG}(C^{\star})}{\sup}\mathbb{E}\left[V^{\star,\widehat{\nu}}\left(\rho\right)-V^{\widehat{\mu},\star}\left(\rho\right)\right]$
$\displaystyle\quad\overset{\text{(i)}}{\geq}6\varepsilon\,\underset{\widehat{\mu}}{\inf}\,\mathbb{E}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\mathbb{P}\left(\theta_{a}=q\,|\,X_{a},M_{a}\right)\right]$
$\displaystyle\quad\geq
6\varepsilon\,\underset{\widehat{\mu}}{\inf}\,\mathbb{E}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\mathbb{P}\left(\theta_{a}=q\,|\,X_{a},M_{a}\right)\operatorname{\mathds{1}}\left\\{\left(X_{a},M_{a}\right)\in
E\right\\}\right]$
$\displaystyle\quad\overset{\text{(ii)}}{\geq}2\varepsilon\,\underset{\widehat{\mu}}{\inf}\,\mathbb{E}\left[\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\operatorname{\mathds{1}}\left\\{\left(X_{a},M_{a}\right)\in
E\right\\}\right]$
$\displaystyle\quad=2\varepsilon\,\underset{\widehat{\mu}}{\inf}\,\mathbb{E}\left[1-\sum_{a\in\mathcal{A}}\widehat{\mu}\left(a\,|\,0\right)\operatorname{\mathds{1}}\left\\{\left(X_{a},M_{a}\right)\notin
E\right\\}\right]$ $\displaystyle\quad\geq
2\varepsilon\,\mathbb{E}\left[1-\sum_{a\in\mathcal{A}}\operatorname{\mathds{1}}\left\\{\left(X_{a},M_{a}\right)\notin
E\right\\}\right]=2\varepsilon\left[1-\sum_{a\in\mathcal{A}}\mathbb{P}\Big{(}\left(X_{a},M_{a}\right)\notin
E\Big{)}\right]$
$\displaystyle\quad\overset{\text{(iii)}}{\geq}2\varepsilon\left(1-\frac{4}{A^{3}}\right)\overset{\text{(iv)}}{\geq}\varepsilon.$

Here, (i) follows from (D.14) and (D.15); (ii) makes use of (D.26); (iii)
follows from (D.25); and (iv) is valid when $A\geq 2$.

##### Case 2: when the sample size $N$ is small.

We now turn attention to the complement case where

$N<\widetilde{C}\frac{S\left(A+B\right)C_{\mathsf{clipped}}^{\star}\log\left(A+B\right)}{1-\gamma}\leq\frac{c_{2}S\left(A+B\right)C_{\mathsf{clipped}}^{\star}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log\left(A+B\right)}.$

Given that the sample size is smaller than the one in Case 1, it is trivially
seen that the minimax lower bound cannot be better than the former case,
namely, we must have

$\underset{(\widehat{\mu},\widehat{\nu})}{\inf}\underset{\\{\mathcal{MG},\rho,d_{\mathsf{b}}\\}\in\mathsf{MG}(C^{\star})}{\sup}\mathbb{E}\left[V^{\star,\widehat{\nu}}\left(\rho\right)-V^{\widehat{\mu},\star}\left(\rho\right)\right]\geq\varepsilon_{0}=\sqrt{\frac{c_{2}}{2\widetilde{C}}}\frac{1}{\left(1-\gamma\right)\log\left(A+B\right)},$

where $\varepsilon_{0}$ is defined in (D.18).

##### Putting Case 1 and Case 2 together.

Combining the above two cases reveals that: for any
$\varepsilon\leq\varepsilon_{0}=\sqrt{\frac{c_{2}}{2\widetilde{C}}}\frac{1}{\left(1-\gamma\right)\log\left(A+B\right)}$
, one necessarily has

$\underset{(\widehat{\mu},\widehat{\nu})}{\inf}\underset{\\{\mathcal{MG},\rho,d_{\mathsf{b}}\\}\in\mathsf{MG}(C^{\star})}{\sup}\mathbb{E}\left[V^{\star,\widehat{\nu}}\left(\rho\right)-V^{\widehat{\mu},\star}\left(\rho\right)\right]\geq\varepsilon$

if the sample size
$N\leq\frac{c_{2}S\left(A+B\right)C_{\mathsf{clipped}}^{\star}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log\left(A+B\right)}$.
This concludes the proof of Theorem 2.

##  Appendix E Auxiliary lemmas for Theorem 2

###  E.1 Proof of Lemma 6

First of all, it is straightforward to verify that: when initialized to any
state $s\neq 0$, the MG will never leave the state $s$ (by construction of
$P_{\theta}$). This combined with the fact that the rewards are zero whenever
$s\neq 0$ gives

$V^{\mu,\nu}\left(s\right)=0\qquad\text{for all}\,s\neq 0.$ (E.1)

As a consequence, it suffices to compute $V_{\theta}^{\mu,\nu}(0)$. By virtue
of the Bellman equation, we obtain

$\displaystyle V^{\mu,\nu}\left(0\right)$
$\displaystyle=\underset{a\sim\mu(0),b\sim\nu(0)}{\mathbb{E}}\left[r\left(0,a,b\right)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P\left(s^{\prime}\,|\,0,a,b\right)V^{\mu,\nu}\left(s^{\prime}\right)\right]$
$\displaystyle\overset{\text{(i)}}{=}1+\gamma\underset{a\sim\mu(0),b\sim\nu(0)}{\mathbb{E}}\big{[}P_{\theta}\left(0\,|\,0,a,b\right)V^{\mu,\nu}\left(0\right)\big{]}$
$\displaystyle=1+\gamma\sum_{a\in\mathcal{A}_{p,\theta}}\mu\left(a\,|\,0\right)\nu\left(0\,|\,0\right)P_{\theta}\left(0\,|\,0,a,0\right)V^{\mu,\nu}\left(0\right)$
$\displaystyle\quad+\gamma\sum_{a\in\mathcal{A}_{p,\theta}}\mu\left(a\,|\,0\right)\sum_{b\neq
0}\nu\left(b\,|\,0\right)P_{\theta}\left(0\,|\,0,a,b\right)V^{\mu,\nu}\left(0\right)$
$\displaystyle\quad+\gamma\sum_{a\in\mathcal{A}_{q,\theta}}\mu\left(a\,|\,0\right)\nu\left(0\,|\,0\right)P_{\theta}\left(0\,|\,0,a,0\right)V^{\mu,\nu}\left(0\right)$
$\displaystyle\quad+\gamma\sum_{a\in\mathcal{A}_{q,\theta}}\mu\left(a\,|\,0\right)\sum_{b\neq
0}\nu\left(b\,|\,0\right)P_{\theta}\left(0\,|\,0,a,b\right)V^{\mu,\nu}\left(0\right)$
$\displaystyle\overset{\text{(ii)}}{=}1+\gamma\mu_{p,\theta}\nu_{0}pV^{\mu,\nu}\left(0\right)+\gamma\mu_{p,\theta}\left(1-\nu_{0}\right)V^{\mu,\nu}\left(0\right)$
$\displaystyle\quad+\gamma\left(1-\mu_{p,\theta}\right)\nu_{0}qV^{\mu,\nu}\left(0\right)+\gamma\left(1-\mu_{p,\theta}\right)\left(1-\nu_{0}\right)V^{\mu,\nu}\left(0\right),$

where we remind the readers of the quantities
$\mu_{p,\theta}\coloneqq\sum_{a\in\mathcal{A}_{p,\theta}}\mu(a\,|\,0)$ and
$\nu_{0}\coloneqq\nu(0\,|\,0)$. Here, (i) makes use of the fact that
$r(0,a,b)=1$ for all $(a,b)\in\mathcal{A}\times\mathcal{B}$ and (E.1), while
(ii) follows from the definition of $P_{\theta}$ in (D.3). Rearrange terms to
arrive at

$\displaystyle V^{\mu,\nu}\left(0\right)$
$\displaystyle=\frac{1}{1-\gamma\mu_{p,\theta}\nu_{0}p-\gamma\mu_{p,\theta}\left(1-\nu_{0}\right)-\gamma\left(1-\mu_{p,\theta}\right)\nu_{0}q-\gamma\left(1-\mu_{p,\theta}\right)\left(1-\nu_{0}\right)}$
$\displaystyle=\frac{1}{1-\gamma+\gamma\mu_{p,\theta}\nu_{0}\left(1-p\right)+\gamma\left(1-\mu_{p,\theta}\right)\nu_{0}\left(1-q\right)}.$

Next, let us rewrite $V^{\mu,\nu}(0)$ as follows

$\displaystyle V^{\mu,\nu}\left(0\right)$
$\displaystyle=\frac{1}{1-\gamma+\gamma\nu_{0}\left(1-p\right)-\gamma(1-\mu_{p,\theta})\nu_{0}\left(1-p\right)+\gamma\left(1-\mu_{p,\theta}\right)\nu_{0}\left(1-q\right)}$
$\displaystyle=\frac{1}{1-\gamma+\gamma\nu_{0}\left(1-p\right)+\gamma\left(1-\mu_{p,\theta}\right)\nu_{0}\left(p-q\right)}.$

Given that $p>q$, we see that: for any policy $\mu$, the best response of the
min-player would be to take $\nu_{0}=1$; and for any policy $\nu$ with
$\nu_{0}\neq 0$, the best response of the max-player would be to set
$\mu_{p,\theta}=1$. As a result, it is seen that $(\mu,\nu)$ is an NE if and
only if $\mu_{p,\theta}=1$ and $\nu_{0}=1$. This readily implies that the
policy pair $(\mu_{\theta}^{\star},\nu_{\theta}^{\star})$ defined in (D.9) is
an NE of $\mathcal{MG}_{\theta}$.

We are left with justifying that
$\\{\mathcal{MG}_{\theta},\rho,d_{\mathsf{b}}\\}\in\mathsf{MG}(C_{\mathsf{clipped}}^{\star})$.
Towards this, we first note that: for any $a\in\mathcal{A}$,
$b\in\mathcal{B}$, and any policy pair $(\mu,\nu)$, we can invoke (D.6) to
show that

$\displaystyle\frac{\min\left\\{d^{\mu,\nu}\left(0,a,b;\rho\right),\frac{1}{S\left(A+B\right)}\right\\}}{d_{\mathsf{b}}\left(0,a,b\right)}$
$\displaystyle\leq\frac{\frac{1}{S\left(A+B\right)}}{\frac{1}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}}=C_{\mathsf{clipped}}^{\star},$
(E.2)

and

$\frac{\min\left\\{d^{\mu,\nu}\left(1,a,b;\rho\right),\frac{1}{S\left(A+B\right)}\right\\}}{d_{\mathsf{b}}\left(1,a,b\right)}\leq\frac{\frac{1}{S\left(A+B\right)}}{\frac{1}{AB}\left(1-\frac{AB}{C_{\mathsf{clipped}}^{\star}S\left(A+B\right)}\right)}=\frac{1}{\frac{S\left(A+B\right)}{AB}-\frac{1}{C_{\mathsf{clipped}}^{\star}}}\leq
C_{\mathsf{clipped}}^{\star},$ (E.3)

where the last inequality holds as long as
$C_{\mathsf{clipped}}^{\star}\geq\frac{2AB}{S(A+B)}$. In addition, for any
$s\geq 2$, it is readily seen that $d^{\mu,\nu}(s,a,b;\rho)=0$, and therefore,

$\frac{\min\left\\{d^{\mu,\nu}\left(s,a,b;\rho\right),\frac{1}{S\left(A+B\right)}\right\\}}{d_{\mathsf{b}}\left(s,a,b\right)}=0.$
(E.4)

Taking (E.2), (E.3) and (E.4) collectively gives

$\max\left\\{\sup_{\mu,s,a,b}\frac{\min\left\\{d^{\mu,\nu_{\theta}^{\star}}\left(s,a,b;\rho\right),\frac{1}{S\left(A+B\right)}\right\\}}{d_{\mathsf{b}}\left(s,a,b\right)},\sup_{\nu,s,a,b}\frac{\min\left\\{d^{\mu_{\theta}^{\star},\nu}\left(s,a,b;\rho\right),\frac{1}{S\left(A+B\right)}\right\\}}{d_{\mathsf{b}}\left(s,a,b\right)}\right\\}\leq
C_{\mathsf{clipped}}^{\star}.$ (E.5)

We still need to justify that the inequality in (E.5) is tight. To do so,
observe that for any $a\in\mathcal{A}_{p}$, one has

$\displaystyle
d^{\mu_{\theta}^{\star},\nu_{\theta}^{\star}}\left(0,a,0\right)$
$\displaystyle=\left(1-\gamma\right)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}\left(s_{t}=0,a_{t}=a,b_{t}=0\,|\,s_{0}\sim\rho;\mu_{\theta}^{\star},\nu_{\theta}^{\star}\right)$
$\displaystyle\overset{\text{(i)}}{=}\left(1-\gamma\right)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}\left(s_{t}=0\,|\,s_{0}\sim\rho;\mu_{\theta}^{\star},\nu_{\theta}^{\star}\right)\frac{1}{|\mathcal{A}_{p,\theta}|}$
$\displaystyle\overset{\text{(ii)}}{\geq}\frac{1-\gamma}{\big{|}\mathcal{A}_{p,\theta}\big{|}}\sum_{t=0}^{\infty}\gamma^{t}p^{t}\overset{\text{(iii)}}{\geq}\frac{1-\gamma}{\big{|}\mathcal{A}_{p,\theta}\big{|}}\sum_{t=0}^{\infty}\gamma^{2t}$
$\displaystyle=\frac{1-\gamma}{\big{|}\mathcal{A}_{p,\theta}\big{|}}\frac{1}{1-\gamma^{2}}=\frac{1}{\big{|}\mathcal{A}_{p,\theta}\big{|}}\frac{1}{1+\gamma}\geq\frac{1}{2\big{|}\mathcal{A}_{p,\theta}\big{|}}.$
(E.6)

Here, (i) is valid since according to (D.9),
$\mathbb{P}(a_{t}=a\,|\,s_{t}=0;\mu_{\theta}^{\star})=1/|\mathcal{A}_{p,\theta}|$
for $a\in\mathcal{A}_{p,\theta}$ and
$\mathbb{P}(b_{t}=0\,|\,s_{t}=0;\nu_{\theta}^{\star})=1$; (ii) follows since

$\mathbb{P}\left(s_{t}=0\,|\,s_{0}\sim\rho;\mu_{\theta}^{\star},\nu_{\theta}^{\star}\right)\geq\mathbb{P}\left(s_{t}=s_{t-1}=\cdots=s_{0}=0\,|\,\mu_{\theta}^{\star},\nu_{\theta}^{\star}\right)=p^{t};$

and (iii) relies on the fact that $p\geq\gamma$ (cf. (D.1)). Then we can
invoke (E.6) and (D.6) to demonstrate that

$\displaystyle\frac{\min\big{\\{}d^{\mu_{\theta}^{\star},\nu_{\theta}^{\star}}\left(0,a,0\right),\frac{1}{S\left(A+B\right)}\big{\\}}}{d_{\mathsf{b}}\left(0,a,0\right)}$
$\displaystyle=\frac{\frac{1}{S\left(A+B\right)}}{\frac{1}{C_{\mathsf{clipped}}^{\star}S(A+B)}}=C_{\mathsf{clipped}}^{\star}\qquad\text{for
any }a\in\mathcal{A}_{p,\theta}.$ (E.7)

Taking collectively (E.5) and (E.7) gives

$\max\left\\{\sup_{\mu,s,a,b}\frac{\min\left\\{d^{\mu,\nu_{\theta}^{\star}}\left(s,a,b;\rho\right),\frac{1}{S\left(A+B\right)}\right\\}}{d_{\mathsf{b}}\left(s,a,b\right)},\sup_{\nu,s,a,b}\frac{\min\left\\{d^{\mu_{\theta}^{\star},\nu}\left(s,a,b;\rho\right),\frac{1}{S\left(A+B\right)}\right\\}}{d_{\mathsf{b}}\left(s,a,b\right)}\right\\}=C_{\mathsf{clipped}}^{\star}.$

This allows one to conclude that
$\\{\mathcal{MG}_{\theta},\rho,d_{\mathsf{b}}\\}\in\mathsf{MG}(C_{\mathsf{clipped}}^{\star})$.

###  E.2 Proof of Lemma 7

Recall that $M_{a}\sim\mathsf{Binomial}(N,d_{\mathsf{b}}(0,a,0))$. Invoke the
Chernoff bound (e.g., Vershynin, (2018, Exercise 2.3.5)) to show the existence
of some universal constant $c_{\mathsf{ch}}>0$ such that

$\displaystyle\mathbb{P}\Big{(}\left|M_{a}-Nd_{\mathsf{b}}\left(0,a,0\right)\right|\geq\delta
Nd_{\mathsf{b}}\left(0,a,0\right)\Big{)}$ $\displaystyle\leq
2\exp\left(-c_{\mathsf{ch}}Nd_{\mathsf{b}}\left(0,a,0\right)\delta^{2}\right)$
(E.8)

holds for any $\delta\in(0,1]$. For $\widetilde{C}$ sufficiently large, one
has (see (D.16))

$N\geq\frac{4}{c_{\mathsf{ch}}}C_{\mathsf{clipped}}^{\star}S\left(A+B\right)\log
A,$

or equivalently,

$Nd_{\mathsf{b}}\left(0,a,0\right)\geq\frac{4}{c_{\mathsf{ch}}}\log A.$

Take

$\delta\coloneqq\sqrt{\frac{4\log
A}{c_{\mathsf{ch}}Nd_{\mathsf{b}}\left(0,a,0\right)}}\leq 1$

in (E.8) to show that with probability exceeding $1-2A^{-4}$,

$\displaystyle M_{a}$ $\displaystyle\leq
Nd_{\mathsf{b}}\left(0,a,0\right)+\sqrt{Nd_{\mathsf{b}}\left(0,a,0\right)}\sqrt{\frac{4\log
A}{c_{\mathsf{ch}}}}\overset{\mathrm{(i)}}{\leq}\frac{c_{2}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}+\sqrt{\frac{8c_{2}}{c_{\mathsf{ch}}\left(1-\gamma\right)^{3}\varepsilon^{2}}}$
$\displaystyle\overset{\mathrm{(ii)}}{\leq}\frac{c_{2}+\sqrt{8c_{2}/c_{\mathsf{ch}}}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}=\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log A}$ (E.9)

holds for some universal constant $c_{4}=c_{2}+\sqrt{8c_{2}/c_{\mathsf{ch}}}$,
where (i) makes use of Condition (D.17), and (ii) is valid as long as
$\varepsilon\leq\frac{1}{(1-\gamma)\log A}$. Moreover, we can also invoke
(E.8) and (D.16) to show that with probability exceeding $1-2A^{-4}$,

$\displaystyle M_{a}$ $\displaystyle\geq
Nd_{\mathsf{b}}\left(0,a,0\right)-\sqrt{Nd_{\mathsf{b}}\left(0,a,0\right)}\sqrt{\frac{2\log
A}{c_{\mathsf{ch}}}}\overset{\text{(iii)}}{\geq}\widetilde{C}\frac{\log
A}{1-\gamma}-\sqrt{\frac{2\widetilde{C}}{c_{\mathsf{ch}}}\frac{\log^{2}A}{1-\gamma}}\overset{\text{(iv)}}{\geq}\frac{c_{3}\log
A}{1-\gamma}$ (E.10)

for some universal constant $c_{3}=\widetilde{C}/2$. Here, (iii) holds since
the function $x^{2}-\sqrt{\frac{2\log A}{c_{\mathsf{ch}}}}x$ is monotonically
increasing when $x\geq\sqrt{\frac{\log A}{c_{\mathsf{ch}}}}$, and

$Nd_{\mathsf{b}}\left(0,a,0\right)\geq\widetilde{C}\frac{\log
A}{1-\gamma}\geq\sqrt{\frac{\log A}{c_{\mathsf{ch}}}}$

when $\widetilde{C}>0$ is sufficiently large; (iv) holds for $\widetilde{C}>0$
sufficiently large. Taking (E.9) and (E.10) collectively gives

$\mathbb{P}\left(\frac{c_{3}\log A}{1-\gamma}\leq
M_{a}\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log
A}\right)\geq 1-\frac{2}{A^{4}}.$

###  E.3 Proof of Lemma 8

Given that $B_{p}\sim\mathsf{Binomial}(M,p)$, we have
$M-B_{p}\sim\mathsf{Binomial}(M,1-p)$. In view of the Chernoff bound (cf.
Vershynin, (2018, Exercise 2.3.5)), we know that for any $\delta\in(0,1]$

$\displaystyle\mathbb{P}\Big{(}\left|B_{p}-Mp\right|>\delta
M\left(1-p\right)\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\left|M-B_{p}-M\left(1-p\right)\right|>\delta
M\left(1-p\right)\Big{)}$ $\displaystyle\leq
2\exp\left(-c_{\mathsf{ch}}M\left(1-p\right)\delta^{2}\right)$ (E.11)

for some universal constant $c_{\mathsf{ch}}>0$. Recall that
$M\geq\frac{c_{3}\log A}{1-\gamma}$. By taking

$\delta\coloneqq\sqrt{\frac{4\log A}{c_{\mathsf{ch}}M\left(1-p\right)}}$

we can guarantee that

$\delta\leq\sqrt{\frac{4\left(1-\gamma\right)}{c_{\mathsf{ch}}c_{3}\left(1-p\right)}}=\sqrt{\frac{4\left(1-\gamma\right)}{c_{\mathsf{ch}}c_{3}\left(1-\gamma-14\frac{\left(1-\gamma\right)^{2}\varepsilon}{\gamma}\right)}}\leq\sqrt{\frac{4}{c_{\mathsf{ch}}c_{3}\left(1-14\frac{\left(1-\gamma\right)\varepsilon}{\gamma}\right)}}\overset{\text{(i)}}{\leq}\sqrt{\frac{8}{c_{\mathsf{ch}}c_{3}}}\overset{\text{(ii)}}{\leq}1.$

Here, (i) holds when $\varepsilon\leq\frac{1}{42(1-\gamma)}$ and $\gamma\geq
2/3$, while (ii) is valid as long as $c_{3}=\widetilde{C}/2\geq
8/c_{\mathsf{ch}}$ (a condition that can be guaranteed as long as
$\widetilde{C}$ is sufficiently large). Then the inequality (E.11) tells us
that

$\displaystyle\mathbb{P}\left(\left|B_{p}-Mp\right|>\sqrt{\frac{4\log
A}{c_{\mathsf{ch}}}M\left(1-p\right)}\right)$
$\displaystyle\leq\frac{2}{A^{4}}.$

A similar argument leads to

$\mathbb{P}\left(\left|B_{q}-Mq\right|\geq\sqrt{\frac{4\log
A}{c_{\mathsf{ch}}}M\left(1-q\right)}\right)\leq\frac{2}{A^{4}}.$

In view of these concentration bounds, we can take

$E_{M}\coloneqq\Big{\\{}0\leq n\leq
M:\left\lfloor\min\left\\{Mp-\Delta_{p},Mq-\Delta_{q}\right\\}\right\rfloor\leq
n\leq\left\lceil\max\left\\{Mp+\Delta_{p},Mq+\Delta_{q}\right\\}\right\rceil\Big{\\}},$

where we define, for every $x\in(0,1)$,

$\Delta_{x}\coloneqq\sqrt{\frac{4\log A}{c_{\mathsf{ch}}}M\left(1-x\right)}.$

It is clear from the above argument that (D.21) is guaranteed to hold.

We are left with checking (D.22). Towards this, we first make the observation
that

$\displaystyle\frac{\mathbb{P}\left(B_{q}=m\right)}{\mathbb{P}\left(B_{p}=m\right)}$
$\displaystyle=\frac{q^{m}\left(1-q\right)^{M-m}}{p^{m}\left(1-p\right)^{M-m}}=\exp\left(-m\log\frac{p}{q}-\left(M-m\right)\log\frac{1-p}{1-q}\right)$
$\displaystyle=\exp\left(-M\left[\mathsf{KL}\left(p\,\|\,q\right)+\left(\frac{m}{M}-p\right)\log\frac{p\left(1-q\right)}{q\left(1-p\right)}\right]\right),$

where $\mathsf{KL}(p\,\|\,q)$ denotes the Kullback-Leibler (KL) divergence
between $\mathsf{Bernoulli}(p)$ and $\mathsf{Bernoulli}(q)$ (Tsybakov and
Zaiats,, 2009):

$\mathsf{KL}\left(p\,\|\,q\right)\coloneqq
p\log\frac{p}{q}+\left(1-p\right)\log\frac{1-p}{1-q}.$

Moreover, it is seen that

$\mathsf{KL}\left(p\,\|\,q\right)\overset{\text{(i)}}{\leq}\frac{\left(p-q\right)^{2}}{p\left(1-p\right)}=\frac{784\left(1-\gamma\right)^{4}\varepsilon^{2}}{p\left(1-\gamma-14\frac{\left(1-\gamma\right)^{2}\varepsilon}{\gamma}\right)\gamma^{2}}\overset{\text{(ii)}}{\leq}\frac{3528\left(1-\gamma\right)^{3}\varepsilon^{2}}{1-14\frac{\left(1-\gamma\right)\varepsilon}{\gamma}}\leq
7056\left(1-\gamma\right)^{3}\varepsilon^{2},$ (E.12)

where (i) follows from Li et al., 2022c (, Lemma 10) and (ii) relies on (D.2).
In addition, for any $m\in E_{M}$, we have $m\leq Mp+\Delta_{q}$, which in
turn reveals that

$\frac{m}{M}-p\leq\frac{\Delta_{q}}{M}\leq\sqrt{\frac{4\log
A}{c_{\mathsf{ch}}M}\left(1-\gamma+14\frac{\left(1-\gamma\right)^{2}\varepsilon}{\gamma}\right)}\leq\sqrt{\frac{6\left(1-\gamma\right)\log
A}{c_{\mathsf{ch}}M}}$ (E.13)

provided that $\varepsilon\leq\frac{1}{42(1-\gamma)}$ and $\gamma\leq 2/3$.
Recalling that $p>q$, we can also see that

$\displaystyle 0$
$\displaystyle<\log\frac{p\left(1-q\right)}{q\left(1-p\right)}=\log\left(1+\frac{p-q}{q\left(1-p\right)}\right)\overset{\text{(i)}}{\leq}\frac{p-q}{q\left(1-p\right)}\overset{\text{(ii)}}{\leq}\frac{28\left(1-\gamma\right)^{2}\varepsilon}{\gamma\left(1-\gamma-14\frac{\left(1-\gamma\right)^{2}\varepsilon}{\gamma}\right)}$
$\displaystyle\leq\frac{42\left(1-\gamma\right)\varepsilon}{1-14\frac{\left(1-\gamma\right)\varepsilon}{\gamma}}\leq\frac{42\left(1-\gamma\right)\varepsilon}{1-\frac{1}{3\gamma}}\leq
84\left(1-\gamma\right)\varepsilon,$ (E.14)

where (i) exploits the elementary inequality $\log(1+x)\leq x$ for all $x\geq
0$, and (ii) follows from (D.2). Taking (E.12), (E.13) and (E.14) collectively
yields

$\displaystyle\frac{\mathbb{P}\left(B_{q}=m\right)}{\mathbb{P}\left(B_{p}=m\right)}$
$\displaystyle\geq\exp\left[-M\left(7056\left(1-\gamma\right)^{3}\varepsilon^{2}+84\left(1-\gamma\right)\varepsilon\sqrt{\frac{6\left(1-\gamma\right)\log
A}{c_{\mathsf{ch}}M}}\right)\right]$
$\displaystyle\overset{\text{(i)}}{\geq}\exp\left[-\left(\frac{7056c_{4}}{\log
A}+84\sqrt{\frac{6c_{4}}{c_{\mathsf{ch}}}}\right)\right]\overset{\text{(ii)}}{\geq}\exp\left[-\left(\frac{7056c_{4}}{\log
2}+84\sqrt{\frac{6c_{4}}{c_{\mathsf{ch}}}}\right)\right]\overset{\text{(iii)}}{\geq}\frac{1}{2}.$

Here, (i) follows from the condition that

$M\leq\frac{c_{4}}{\left(1-\gamma\right)^{3}\varepsilon^{2}\log A},$

(ii) holds when $A\geq 2$, and (iii) holds with the proviso that
$c_{4}=2c_{2}+\sqrt{8c_{2}/c_{\mathsf{ch}}}$ is sufficiently small, which can
happen as long as $c_{2}$ is sufficiently small.

## References

  * Abe and Kaneko, (2020) Abe, K. and Kaneko, Y. (2020).  Off-policy exploitability-evaluation in two-player zero-sum markov games.  arXiv preprint arXiv:2007.02141.
  * Agarwal et al., (2020) Agarwal, A., Kakade, S., and Yang, L. F. (2020).  Model-based reinforcement learning with a generative model is minimax optimal.  In Conference on Learning Theory, pages 67–83. PMLR.
  * Azar et al., (2013) Azar, M. G., Munos, R., and Kappen, H. J. (2013).  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  Machine learning, 91(3):325–349.
  * Azar et al., (2017) Azar, M. G., Osband, I., and Munos, R. (2017).  Minimax regret bounds for reinforcement learning.  In International Conference on Machine Learning, pages 263–272. PMLR.
  * Bai and Jin, (2020) Bai, Y. and Jin, C. (2020).  Provable self-play algorithms for competitive reinforcement learning.  In International conference on machine learning, pages 551–560. PMLR.
  * Bai et al., (2020) Bai, Y., Jin, C., and Yu, T. (2020).  Near-optimal reinforcement learning with self-play.  Advances in neural information processing systems, 33:2159–2170.
  * Baker et al., (2019) Baker, B., Kanitscheider, I., Markov, T., Wu, Y., Powell, G., McGrew, B., and Mordatch, I. (2019).  Emergent tool use from multi-agent autocurricula.  In International Conference on Learning Representations.
  * Berner et al., (2019) Berner, C., Brockman, G., Chan, B., Cheung, V., Dębiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., et al. (2019).  Dota 2 with large scale deep reinforcement learning.  arXiv preprint arXiv:1912.06680.
  * Bertsekas, (2017) Bertsekas, D. P. (2017).  Dynamic programming and optimal control (4th edition).  Athena Scientific.
  * Brown and Sandholm, (2019) Brown, N. and Sandholm, T. (2019).  Superhuman AI for multiplayer poker.  Science, 365(6456):885–890.
  * Cen et al., (2021) Cen, S., Wei, Y., and Chi, Y. (2021).  Fast policy extragradient methods for competitive games with entropy regularization.  Advances in Neural Information Processing Systems, 34.
  * Chang et al., (2021) Chang, J. D., Uehara, M., Sreenivas, D., Kidambi, R., and Sun, W. (2021).  Mitigating covariate shift in imitation learning via offline data without great coverage.  arXiv preprint arXiv:2106.03207.
  * (13) Chen, Y., Chi, Y., Fan, J., Ma, C., et al. (2021a).  Spectral methods for data science: A statistical perspective.  Foundations and Trends® in Machine Learning, 14(5):566–806.
  * (14) Chen, Z., Zhou, D., and Gu, Q. (2021b).  Almost optimal algorithms for two-player markov games with linear function approximation.  arXiv preprint arXiv:2102.07404.
  * Ciesielski, (2007) Ciesielski, K. (2007).  On stefan banach and some of his results.  Banach Journal of Mathematical Analysis, 1(1):1–10.
  * (16) Cui, Q. and Du, S. S. (2022a).  Provably efficient offline multi-agent reinforcement learning via strategy-wise bonus.  arXiv preprint arXiv:2206.00177.
  * (17) Cui, Q. and Du, S. S. (2022b).  When is offline two-player zero-sum markov game solvable?  arXiv preprint arXiv:2201.03522.
  * Cui and Yang, (2021) Cui, Q. and Yang, L. F. (2021).  Minimax sample complexity for turn-based stochastic game.  In Uncertainty in Artificial Intelligence, pages 1496–1504. PMLR.
  * Daskalakis, (2013) Daskalakis, C. (2013).  On the complexity of approximating a nash equilibrium.  ACM Transactions on Algorithms (TALG), 9(3):1–35.
  * Daskalakis et al., (2020) Daskalakis, C., Foster, D. J., and Golowich, N. (2020).  Independent policy gradient methods for competitive reinforcement learning.  Advances in neural information processing systems, 33:5527–5540.
  * Daskalakis et al., (2009) Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. (2009).  The complexity of computing a nash equilibrium.  SIAM Journal on Computing, 39(1):195–259.
  * Daskalakis et al., (2022) Daskalakis, C., Golowich, N., and Zhang, K. (2022).  The complexity of Markov equilibrium in stochastic games.  arXiv preprint arXiv:2204.03991.
  * Freund and Schapire, (1999) Freund, Y. and Schapire, R. E. (1999).  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103.
  * Hansen et al., (2013) Hansen, T. D., Miltersen, P. B., and Zwick, U. (2013).  Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor.  Journal of the ACM (JACM), 60(1):1–16.
  * Hu and Wellman, (2003) Hu, J. and Wellman, M. P. (2003).  Nash q-learning for general-sum stochastic games.  Journal of machine learning research, 4(Nov):1039–1069.
  * Jaderberg et al., (2019) Jaderberg, M., Czarnecki, W. M., Dunning, I., Marris, L., Lever, G., Castaneda, A. G., Beattie, C., Rabinowitz, N. C., Morcos, A. S., and Ruderman, A. (2019).  Human-level performance in 3D multiplayer games with population-based reinforcement learning.  Science, 364(6443):859–865.
  * Jia et al., (2019) Jia, Z., Yang, L. F., and Wang, M. (2019).  Feature-based q-learning for two-player stochastic games.  arXiv preprint arXiv:1906.00423.
  * (28) Jin, C., Liu, Q., Wang, Y., and Yu, T. (2021a).  V-learning–a simple, efficient, decentralized algorithm for multiagent rl.  arXiv preprint arXiv:2110.14555.
  * Jin et al., (2022) Jin, Y., Muthukumar, V., and Sidford, A. (2022).  The complexity of infinite-horizon general-sum stochastic games.  arXiv preprint arXiv:2204.04186.
  * Jin and Sidford, (2021) Jin, Y. and Sidford, A. (2021).  Towards tight bounds on the sample complexity of average-reward MDPs.  In International Conference on Machine Learning, pages 5055–5064. PMLR.
  * (31) Jin, Y., Yang, Z., and Wang, Z. (2021b).  Is pessimism provably efficient for offline RL?  In International Conference on Machine Learning, pages 5084–5096.
  * Johnstone, (2017) Johnstone, I. M. (2017).  Gaussian estimation: Sequence and wavelet models.  Unpublished manuscript.
  * Kidambi et al., (2020) Kidambi, R., Rajeswaran, A., Netrapalli, P., and Joachims, T. (2020).  Morel: Model-based offline reinforcement learning.  arXiv preprint arXiv:2005.05951.
  * Kumar et al., (2020) Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020).  Conservative Q-learning for offline reinforcement learning.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 1179–1191. Curran Associates, Inc.
  * Lagoudakis and Parr, (2002) Lagoudakis, M. G. and Parr, R. (2002).  Value function approximation in zero-sum markov games.  In Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence, pages 283–292.
  * Levine et al., (2020) Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020).  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  arXiv preprint arXiv:2005.01643.
  * (37) Li, G., Chi, Y., Wei, Y., and Chen, Y. (2022a).  Minimax-optimal multi-agent RL in zero-sum Markov games with a generative model.  in preparation.
  * (38) Li, G., Ma, C., and Srebro, N. (2022b).  Pessimism for offline linear contextual bandits using $\ell_{p}$ confidence sets.  arXiv preprint arXiv:2205.10671.
  * (39) Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2022c).  Settling the sample complexity of model-based offline reinforcement learning.  arXiv preprint arXiv:2204.05275.
  * Li et al., (2021) Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. (2021).  Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning.  Advances in Neural Information Processing Systems, 34.
  * Li et al., (2020) Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020).  Breaking the sample size barrier in model-based reinforcement learning with a generative model.  In Advances in Neural Information Processing Systems, volume 33.
  * Littman, (1994) Littman, M. L. (1994).  Markov games as a framework for multi-agent reinforcement learning.  In Machine learning proceedings 1994, pages 157–163. Elsevier.
  * Littman et al., (2001) Littman, M. L. et al. (2001).  Friend-or-foe q-learning in general-sum games.  In ICML, volume 1, pages 322–328.
  * Liu et al., (2021) Liu, Q., Yu, T., Bai, Y., and Jin, C. (2021).  A sharp analysis of model-based reinforcement learning with self-play.  In International Conference on Machine Learning, pages 7001–7010. PMLR.
  * Liu et al., (2020) Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E. (2020).  Provably good batch reinforcement learning without great exploration.  arXiv preprint arXiv:2007.08202.
  * Lu et al., (2022) Lu, M., Min, Y., Wang, Z., and Yang, Z. (2022).  Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision processes.  arXiv preprint arXiv:2205.13589.
  * Ma et al., (2020) Ma, C., Wang, K., Chi, Y., and Chen, Y. (2020).  Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution.  Foundations of Computational Mathematics, 20(3).
  * Mao and Başar, (2022) Mao, W. and Başar, T. (2022).  Provably efficient reinforcement learning in decentralized general-sum Markov games.  Dynamic Games and Applications, pages 1–22.
  * Munos, (2003) Munos, R. (2003).  Error bounds for approximate policy iteration.  In ICML, volume 3, pages 560–567.
  * Munos, (2007) Munos, R. (2007).  Performance bounds in $\ell_{p}$-norm for approximate value iteration.  SIAM journal on control and optimization, 46(2):541–561.
  * Nash, (1951) Nash, J. (1951).  Non-cooperative games.  Annals of mathematics, pages 286–295.
  * Perolat et al., (2015) Perolat, J., Scherrer, B., Piot, B., and Pietquin, O. (2015).  Approximate dynamic programming for two-player zero-sum markov games.  In International Conference on Machine Learning, pages 1321–1329. PMLR.
  * Raghavan, (1994) Raghavan, T. (1994).  Zero-sum two-person games.  Handbook of game theory with economic applications, 2:735–768.
  * Rakhlin and Sridharan, (2013) Rakhlin, S. and Sridharan, K. (2013).  Optimization, learning, and games with predictable sequences.  Advances in Neural Information Processing Systems, 26.
  * Rashidinejad et al., (2021) Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021).  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  Neural Information Processing Systems (NeurIPS).
  * Roughgarden, (2016) Roughgarden, T. (2016).  Twenty lectures on algorithmic game theory.  Cambridge University Press.
  * Shalev-Shwartz et al., (2016) Shalev-Shwartz, S., Shammah, S., and Shashua, A. (2016).  Safe, multi-agent, reinforcement learning for autonomous driving.  arXiv preprint arXiv:1610.03295.
  * Shao, (2003) Shao, J. (2003).  Mathematical Statistics.  Springer Texts in Statistics. Springer.
  * Shapley, (1953) Shapley, L. S. (1953).  Stochastic games.  Proceedings of the national academy of sciences, 39(10):1095–1100.
  * Shi et al., (2022) Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022).  Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity.  accepted to International Conference on Machine Learning (ICML).
  * Sidford et al., (2020) Sidford, A., Wang, M., Yang, L., and Ye, Y. (2020).  Solving discounted stochastic two-player games with near-optimal time and sample complexity.  In International Conference on Artificial Intelligence and Statistics, pages 2992–3002. PMLR.
  * Song et al., (2021) Song, Z., Mei, S., and Bai, Y. (2021).  When can we learn general-sum markov games with a large number of players sample-efficiently?  arXiv preprint arXiv:2110.04184.
  * Tian et al., (2021) Tian, Y., Wang, Y., Yu, T., and Sra, S. (2021).  Online learning in unknown markov games.  In International conference on machine learning, pages 10279–10288. PMLR.
  * Tsybakov and Zaiats, (2009) Tsybakov, A. B. and Zaiats, V. (2009).  Introduction to nonparametric estimation, volume 11.  Springer.
  * Uehara and Sun, (2021) Uehara, M. and Sun, W. (2021).  Pessimistic model-based offline reinforcement learning under partial coverage.  arXiv preprint arXiv:2107.06226.
  * Vershynin, (2018) Vershynin, R. (2018).  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press.
  * Vinyals et al., (2019) Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., and Georgiev, P. (2019).  Grandmaster level in Starcraft II using multi-agent reinforcement learning.  Nature, 575(7782):350–354.
  * Wang et al., (2021) Wang, B., Yan, Y., and Fan, J. (2021).  Sample-efficient reinforcement learning for linearly-parameterized mdps with a generative model.  Advances in Neural Information Processing Systems, 34.
  * Wang et al., (2022) Wang, X., Cui, Q., and Du, S. S. (2022).  On gap-dependent bounds for offline reinforcement learning.  arXiv preprint arXiv:2206.00177.
  * Wei et al., (2017) Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. (2017).  Online reinforcement learning in stochastic games.  Advances in Neural Information Processing Systems, 30.
  * Wei et al., (2021) Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. (2021).  Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games.  In Conference on Learning Theory, pages 4259–4299. PMLR.
  * Xie et al., (2020) Xie, Q., Chen, Y., Wang, Z., and Yang, Z. (2020).  Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium.  In Conference on learning theory, pages 3674–3682. PMLR.
  * Xie et al., (2021) Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. (2021).  Policy finetuning: Bridging sample-efficient offline and online reinforcement learning.  arXiv preprint arXiv:2106.04895.
  * Xiong et al., (2022) Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. (2022).  Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game.  arXiv preprint arXiv:2205.15512.
  * Yan et al., (2022) Yan, Y., Li, G., Chen, Y., and Fan, J. (2022).  The efficacy of pessimism in asynchronous Q-learning.  arXiv preprint arXiv:2203.07368.
  * Yang and Wang, (2020) Yang, Y. and Wang, J. (2020).  An overview of multi-agent reinforcement learning from game theoretical perspective.  arXiv preprint arXiv:2011.00583.
  * (77) Yin, M., Bai, Y., and Wang, Y.-X. (2021a).  Near-optimal offline reinforcement learning via double variance reduction.  arXiv preprint arXiv:2102.01748.
  * (78) Yin, M., Bai, Y., and Wang, Y.-X. (2021b).  Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning.  In International Conference on Artificial Intelligence and Statistics, pages 1567–1575. PMLR.
  * (79) Yin, M., Duan, Y., Wang, M., and Wang, Y.-X. (2021c).  Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism.  In International Conference on Learning Representations.
  * Yin and Wang, (2021) Yin, M. and Wang, Y.-X. (2021).  Towards instance-optimal offline reinforcement learning with pessimism.  Advances in neural information processing systems, 34.
  * (81) Yu, T., Kumar, A., Chebotar, Y., Hausman, K., Levine, S., and Finn, C. (2021a).  Conservative data sharing for multi-task offline reinforcement learning.  arXiv preprint arXiv:2109.08128.
  * (82) Yu, T., Kumar, A., Rafailov, R., Rajeswaran, A., Levine, S., and Finn, C. (2021b).  Combo: Conservative offline model-based policy optimization.  arXiv preprint arXiv:2102.08363.
  * Yu et al., (2020) Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J., Levine, S., Finn, C., and Ma, T. (2020).  MOPO: Model-based offline policy optimization.  arXiv preprint arXiv:2005.13239.
  * Zanette et al., (2021) Zanette, A., Wainwright, M. J., and Brunskill, E. (2021).  Provable benefits of actor-critic methods for offline reinforcement learning.  arXiv preprint arXiv:2108.08812.
  * (85) Zhang, K., Kakade, S., Basar, T., and Yang, L. (2020a).  Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity.  Advances in Neural Information Processing Systems, 33:1166–1178.
  * (86) Zhang, K., Yang, Z., and Başar, T. (2021a).  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  Handbook of Reinforcement Learning and Control, pages 321–384.
  * (87) Zhang, K., Yang, Z., Liu, H., Zhang, T., and Başar, T. (2021b).  Finite-sample analysis for decentralized batch multiagent reinforcement learning with networked agents.  IEEE Transactions on Automatic Control, 66(12):5925–5940.
  * (88) Zhang, X., Chen, Y., Zhu, J., and Sun, W. (2021c).  Corruption-robust offline reinforcement learning.  arXiv preprint arXiv:2106.06630.
  * (89) Zhang, Z., Zhou, Y., and Ji, X. (2020b).  Almost optimal model-free reinforcement learning via reference-advantage decomposition.  Advances in Neural Information Processing Systems, 33.
  * Zhao et al., (2021) Zhao, Y., Tian, Y., Lee, J. D., and Du, S. S. (2021).  Provably efficient policy gradient methods for two-player zero-sum Markov games.  arXiv preprint arXiv:2102.08903.
  * Zhong et al., (2022) Zhong, H., Xiong, W., Tan, J., Wang, L., Zhang, T., Wang, Z., and Yang, Z. (2022).  Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets.  arXiv preprint arXiv:2202.07511.