# Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative
Model

Gen Li
UPenn
Department of Statistics and Data Science, Wharton School, University of
Pennsylvania, Philadelphia, PA 19104, USA. Yuejie Chi
CMU
Department of Electrical and Computer Engineering, Carnegie Mellon University,
Pittsburgh, PA 15213, USA. Yuting Wei11footnotemark: 1
UPenn
Yuxin Chen11footnotemark: 1
UPenn

###### Abstract

This paper is concerned with two-player zero-sum Markov games — arguably the
most basic setting in multi-agent reinforcement learning — with the goal of
learning a Nash equilibrium (NE) sample-optimally. All prior results suffer
from at least one of the two obstacles: the curse of multiple agents and the
barrier of long horizon, regardless of the sampling protocol in use. We take a
step towards settling this problem, assuming access to a flexible sampling
mechanism: the generative model. Focusing on non-stationary finite-horizon
Markov games, we develop a learning algorithm called Nash-Q-FTRL and an
adaptive sampling scheme that leverage the optimism principle in adversarial
learning (particularly the Follow-the-Regularized-Leader (FTRL) method), with
a delicate design of bonus terms that ensure certain decomposability under the
FTRL dynamics. Our algorithm learns an $\varepsilon$-approximate Markov NE
policy using

$\widetilde{O}\bigg{(}\frac{H^{4}S(A+B)}{\varepsilon^{2}}\bigg{)}$

samples, where $S$ is the number of states, $H$ is the horizon, and $A$ (resp.
$B$) denotes the number of actions for the max-player (resp. min-player). This
is nearly un-improvable in a minimax sense. Along the way, we derive a refined
regret bound for FTRL that makes explicit the role of variance-type
quantities, which might be of independent interest.

Keywords: Markov games, sample complexity, Nash equilibrium, adversarial
learning, Follow-the-Regularized-Leader

###### Contents

  1. 1 Introduction
  2. 2 Background and models
  3. 3 Sample-efficient learning for NE
    1. 3.1 Algorithm description
    2. 3.2 Main results
  4. 4 Regret bounds for FTRL via variance-type quantities
    1. 4.1 Setting: online learning for weighted linear optimization
    2. 4.2 Refined regret bounds for FTRL
  5. 5 Proof of Theorem 1
    1. 5.1 Preliminaries and notation
    2. 5.2 Proof outline
  6. 6 Discussion
  7. A Proof of Theorem 2
    1. A.1 Main steps of the proof
    2. A.2 Proof of claim (54)
    3. A.3 Proof of claim (55)
  8. B Proofs of auxiliary lemmas and details
    1. B.1 Proof of Lemma 3
    2. B.2 Proof of Lemma 4
    3. B.3 Minimax lower bound
    4. B.4 Freedman’s inequality

##  1 Introduction

The thriving field of multi-agent reinforcement learning (MARL) studies how a
group of interacting agents make decisions autonomously in a shared dynamic
environment (Zhang et al.,, 2021). The recent developments in game playing
(Vinyals et al.,, 2019; Brown and Sandholm,, 2019), self-driving vehicles
(Shalev-Shwartz et al.,, 2016), and multi-robot control (Matignon et al.,,
2012) are prime examples of MARL in action. In practice, there is no shortage
of situations where the agents involved have conflict of interest, and they
have to act competitively in order to promote their own benefits (possibly at
the expense of one another). Scenarios of this kind are frequently modeled via
Markov games (MGs) (Shapley,, 1953; Littman,, 1994), a framework that has been
a fruitful playground to formalize and stimulate the studies of competitive
MARL.

In view of the irreconcilable competition between individual players,
solutions of competitive MARL normally take the form of certain equilibrium
strategy profiles, which are perhaps best epitomized by the concept of Nash
equilibrium (NE). In a Nash equilibrium, no gain can be realized through a
unilateral change, and hence no player has incentives to deviate from her
current strategy/policy (assuming no coordination between players). A myriad
of research has been conducted surrounding NEs, which spans various aspects
like existence, learnability, computational hardness, and algorithm design,
among others (Shapley,, 1953; Daskalakis,, 2013; Chen et al.,, 2015;
Rubinstein,, 2016; Perolat et al.,, 2015; Daskalakis et al.,, 2020; Littman,,
1994; Hansen et al.,, 2013; Ozdaglar et al.,, 2021; Jin et al.,, 2022).

##### Sample efficiency in zero-sum Markov games.

One critical challenge impacting modern MARL applications is data efficiency.
The players involved often have minimal knowledge about how the environment
responds to their actions, and have to learn the dynamics and preferable
actions by probing the unknown environment. For MARL to expand into
applications with enormous dimensionality and long planning horizon, the
learning algorithms must manage to make efficient use of the collected data.

Nevertheless, how to learn NEs with optimal sample complexity remains by and
large unsettled, even when it comes to the most basic setting — two-player
zero-sum Markov games. In what follows, let us review two representative
algorithms developed on this front under two drastically different sampling
protocols, and discuss the shortfalls of these cutting-edge results. To
facilitate precise comparisons, our discussion concentrates on zero-sum Markov
games involving two players, where $S$ is the number of states, $H$ indicates
the horizon or effective horizon, and $A$ and $B$ denote respectively the
number of actions for the max-player and the min-player.

  * •

Model-based methods under either a generative model or online exploration.
Assuming access to a generative model (so that one can sample arbitrary state-
action combinations), Zhang et al., (2020) investigated a natural model-based
algorithm, which performs planning (e.g., value iteration) on an empirical MG
derived from samples produced by the generative model. Focusing on stationary
discounted infinite-horizon MGs, their algorithm finds an
$\varepsilon$-approximate NE with no more than

$\widetilde{O}\bigg{(}\frac{H^{3}SAB}{\varepsilon^{2}}\bigg{)}~{}~{}\text{samples}.$
(1)

In parallel, Liu et al., (2021) studied non-stationary finite-horizon MGs with
online exploration, and obtained similar sample complexity bounds, i.e.,

$\widetilde{O}\bigg{(}\frac{H^{4}SAB}{\varepsilon^{2}}\bigg{)}~{}~{}\text{samples}\qquad\text{or}\qquad\widetilde{O}\bigg{(}\frac{H^{3}SAB}{\varepsilon^{2}}\bigg{)}~{}~{}\text{episodes}$
(2)

for learning $\varepsilon$-approximate NEs. While these bounds achieve
minimax-optimal dependency on the horizon $H$, a major drawback emerges
commonly referred to as the curse of multiple agents; namely, these results
scale proportionally with the total number of joint actions (i.e., $AB$), a
quantity that blows up exponentially with the number of players.

  * •

V-learning for online exploration settings. Focusing on online exploration
settings, Bai et al., (2020); Jin et al., (2021) proposed an algorithm called
V-learning that leverages the advances in online adversarial learning (e.g.,
adversarial bandits) to circumvent the curse of multiple agents. This
algorithm provably yields an $\varepsilon$-approximate NE in non-stationary
finite-horizon MGs using

$\widetilde{O}\bigg{(}\frac{H^{6}S(A+B)}{\varepsilon^{2}}\bigg{)}~{}~{}\text{samples}\qquad\text{or}\qquad\widetilde{O}\bigg{(}\frac{H^{5}S(A+B)}{\varepsilon^{2}}\bigg{)}~{}~{}\text{episodes},$
(3)

which effectively brings down the sample size scaling (2) from $AB$ (i.e., the
number of joint actions) to $A+B$ (i.e., the sum of individual actions). It is
worth pointing out, however, that this theory appears sub-optimal in terms of
the horizon dependency, as it is a factor of $H^{2}$ above the minimax lower
bound.

The above results represent the state-of-the-art sample complexity theory thus
far for learning NEs in two-player zero-sum MGs. In summary, these existing
results — irrespective of the sampling mechanism in use — fall short of
overcoming at least one of the two major hurdles: (i) the curse of multiple
agents, and (ii) the barrier of long horizon. A natural question to pose is:

Question: can we learn Nash equilibria in a two-player zero-sum Markov game
in a sample-optimal and computation-efficient fashion?

To settle this question favorably, both of the above-mentioned hurdles need to
be crossed simultaneously.

##### Main contributions.

Recognizing that the above question remains open regardless of the sampling
scheme in use, this paper takes a first step towards solving it assuming
access to the most flexible sampling protocol: the generative model (or
simulator). In sharp contrast to the single-agent case where uniform sampling
of all state-action pairs suffices (Azar et al.,, 2013; Li et al.,, 2020), the
multi-agent scenario requires one to take samples intelligently and
adaptively, a crucial step to avoid inefficient use of data (otherwise one
cannot hope to break the curse of multiple agents). With the aim of computing
an $\varepsilon$-approximate NE in a non-stationary finite-horizon two-player
zero-sum MG, we come up with a learning algorithm (accompanied by an adaptive
sampling strategy) that accomplishes this goal with no more than

$\widetilde{O}\bigg{(}\frac{H^{4}S(A+B)}{\varepsilon^{2}}\bigg{)}~{}~{}\text{samples}$
(4)

drawn from the generative model. Encouragingly, this sample complexity bound
matches the minimax lower limit (up to a logarithmic factor). Our sample
complexity theory is valid for the full $\varepsilon$-range (i.e., any
$\varepsilon\in(0,H]$); this unveils that no burn-in cost whatsoever is needed
for our algorithm to achieve sample optimality, which lends itself well to
sample-hungry applications.

The proposed algorithm is inspired by two key algorithmic ideas in RL and
bandit literature: (1) optimism in the face of uncertainty (by leveraging
upper confidence bounds (UCBs) in value estimation), and (2) online and
adversarial learning (particularly the Follow-the-Regularized-Leader (FTRL)
algorithm). Note that the optimal design of bonus terms — typically based on
certain data-driven variance estimates — is substantially more challenging
than the single-agent case, as it requires intricate adaptation in response to
the policy changes of one another as well as compatibility with the FTRL
dynamics. Two points are worth emphasizing (which will be made precise later
on):

  * •

The efficacy of FTRL in breaking the curse of multiple agents has been proved
in Jin et al., (2021); Song et al., (2021). To improve horizon dependency, one
needs to exploit connections between the performance of FTRL and certain
variances. Towards this, we develop a refined regret bound for FTRL that
unveils the role of variance-style quantities, which was previously
unavailable.

  * •

The bonus terms entail Bernstein-style variance estimates that mimic the
variance-style quantities appearing in our refined FTRL regret bounds, and are
carefully chosen so as to ensure certain decomposability over steps. This is
crucial in optimizing the horizon dependency.

Additionally, the policy returned by our algorithm is Markovian (i.e., the
action selection probability depends only on the current state $s$ and step
$h$), and the algorithm can be carried out in a decentralized manner without
the need of directly observing the opponent’s actions.

##### Other related works.

Let us discuss in passing additional prior works on learning equilibrium
solutions in MARL, which have attracted an explosion of interest in recent
years. While the Nash equilibrium is arguably the most compelling solution
concept in Markov games, the finite-sample/finite-time studies of NE learning
concentrate primarily on two-player zero-sum MGs (e.g., Bai and Jin, (2020);
Chen et al., (2022); Mao and Başar, (2022); Wei et al., (2017); Tian et al.,
(2021); Cui and Du, 2022b ; Cui and Du, 2022a ; Zhong et al., (2022); Jia et
al., (2019); Yan et al., (2022); Dou et al., (2022)), mainly because computing
NEs becomes, for the most part, computationally infeasible (i.e., PPAD-
complete) when going beyond two-player zero-sum MGs (Daskalakis,, 2013;
Daskalakis et al.,, 2009). Roughly speaking, previous NE-finding algorithms
for two-player zero-sum Markov games can be categorized into model-based
algorithms (Perolat et al.,, 2015; Zhang et al.,, 2020; Liu et al.,, 2021),
value-based algorithms (Bai and Jin,, 2020; Bai et al.,, 2020; Xie et al.,,
2020; Sayin et al.,, 2021; Jin et al.,, 2021; Chen et al., 2021b, ), and
policy-based algorithms (Cen et al.,, 2021; Daskalakis et al.,, 2020; Wei et
al.,, 2021; Zhao et al.,, 2021; Chen et al., 2021a, ; Zhang et al.,, 2022). In
particular, Bai et al., (2020); Jin et al., (2021) developed the first
algorithms to beat the curse of multiple agents in two-player zero-sum MGs,
while Jin et al., (2021); Daskalakis et al., (2022); Mao and Başar, (2022);
Song et al., (2021) further demonstrated how to accomplish the same goal when
learning other computationally tractable solution concepts (e.g., coarse
correlated equilibria) in general-sum multi-player Markov games. The recent
works Cui and Du, 2022b ; Cui and Du, 2022a ; Yan et al., (2022) studied how
to alleviate the sample size scaling with the number of agents in the presence
of offline data, with Cui and Du, 2022a  providing a sample-efficient
algorithm that also learns NEs in multi-agent Markov games (despite
computational intractability). The studies of Markov games have recently been
extended to partially observable settings as well (Liu et al.,, 2022), which
are beyond the scope of the present work.

We shall also briefly remark on the prior works that concern RL with a
generative model. While there are multiple sampling mechanisms (e.g., online
exploratory sampling, offline data) that bear practical relevance, the
generative model (or simulator) serves as an idealistic sampling protocol that
has received much recent attention, covering the design of various model-
based, model-free and policy-based algorithms (Kearns et al.,, 2002; Wang et
al.,, 2021; Agarwal et al.,, 2020; Azar et al.,, 2013; Li et al.,, 2020; Jin
and Sidford,, 2021; Sidford et al., 2018a, ; Wainwright, 2019a, ; Wainwright,
2019b, ; Li et al., 2021a, ; Kakade,, 2003; Sidford et al., 2018b, ; Pananjady
and Wainwright,, 2020; Khamaru et al.,, 2021; Chen et al.,, 2020; Even-Dar and
Mansour,, 2003; Beck and Srikant,, 2012; Wei et al.,, 2021; Vaswani et al.,,
2022; Zanette et al.,, 2019; Weisz et al.,, 2021; Mou et al.,, 2020; Yang and
Wang,, 2019; Zanette et al.,, 2020; Du et al.,, 2020). In single-agent RL, the
model-based approach has been shown to be minimax-optimal for the entire
$\varepsilon$-range (Li et al.,, 2020; Agarwal et al.,, 2020; Azar et al.,,
2013). When it comes to multi-agent RL, sample-efficient solutions with a
generative model have been proposed in the recent works (Sidford et al.,,
2020; Cui and Yang,, 2021; Zhang et al.,, 2020), although a provably sample-
optimal strategy was previously unavailable.

##### Paper organization and notation.

The rest of the paper is organized as follows. Section 2 introduces the
background of Markov games, the preliminaries of the solution concepts of Nash
equilibrium, and formulates the sampling protocol. The proposed learning
algorithm and the sampling strategy are described in Section 3.1, with the
theoretical guarantees provided in Section 3.2. Section 4 takes a detour to
develop our refined regret bound for FTRL, which plays a crucial role in our
main sample complexity analysis in Section 5. Proof details (particularly
those for auxiliary lemmas) are postponed to the appendix.

Let us also gather several convenient notation that shall be used multiple
times. For any positive integer $n$, we write $[n]\coloneqq\\{1,\cdots,n\\}$.
We shall abuse notation and let $1$ and $0$ denote the all-one vector and the
all-zero vector, respectively. For a sequence $\\{\alpha_{k}\\}_{k\geq
1}\subseteq(0,1]$, we define

$\alpha_{i}^{k}\coloneqq\begin{cases}\alpha_{i}\prod_{j=i+1}^{k}(1-\alpha_{j}),&\text{if
}0<i<k\\\ \alpha_{k},&\text{if }i=k\end{cases}$ (5)

for any $1\leq i\leq k$. For a given vector $x\in\mathbb{R}^{SA}$ (resp.
$y\in\mathbb{R}^{SAB}$), we denote by $x(s,a)$ (resp. $y(s,a,b)$) the entry of
$x$ (resp. $y$) associated with the state-action combination $(s,a)$ (resp.
$(s,a,b)$), as long as it is clear from the context. Next, consider any two
vectors $a=[a_{i}]_{1\leq i\leq n}$ and $b=[b_{i}]_{1\leq i\leq n}$. We use
$a\leq b$ (resp. $a\geq b$) to indicate that $a_{i}\geq b_{i}$ (resp.
$a_{i}\leq b_{i}$) holds for all $i$; we allow scalar functions to take
vector-valued arguments in order to denote entrywise operations (e.g.,
$a^{2}=[a_{i}^{2}]_{1\leq i\leq n}$ and $a^{4}=[a_{i}^{4}]_{1\leq i\leq n}$);
and we denote by $a\circ b=[a_{i}b_{i}]_{1\leq i\leq n}$ the Hadamard product.
For a finite set $\mathcal{A}=\\{1,\cdots,A\\}$, we denote by
$\Delta(\mathcal{A})=\\{x\in\mathbb{R}^{A}\,|\,\sum_{i}x_{i}=1;x\geq 0\\}$ the
probability simplex over $\mathcal{A}$. For any function $f$ with domain
$\mathcal{A}$ (or $\mathcal{B}$), we adopt the convenient notation

$\displaystyle\mathbb{E}_{\pi}[f]$
$\displaystyle\coloneqq\sum\nolimits_{a}\pi(a)f(a)\qquad\text{and}\qquad\mathsf{Var}_{\pi}(f)\coloneqq\sum\nolimits_{a}\pi(a)\big{(}f(a)-\mathbb{E}_{\pi}[f]\big{)}^{2}.$
(6)

##  2 Background and models

In this section, we introduce the basics for two-player zero-sum Markov games
and the solution concept of Nash equilibrum.

##### Two-player Markov games.

A non-stationary finite-horizon two-player Markov game, denoted by
$\mathcal{MG}=\big{\\{}\mathcal{S},\mathcal{A},\mathcal{B},H,P,r\big{\\}}$,
involves two players competing against each other — with the first one called
a “max-player” and the second one called a “min-player” — and consists of
several key elements to be formalized below. To begin with, we denote by
$\mathcal{S}=\\{1,\cdots,S\\}$ a shared state space comprising $S$ different
states, and let $\mathcal{A}=\\{1,\cdots,A\\}$ (resp.
$\mathcal{B}=\\{1,\cdots,B\\}$) represent the action space of the max-player
(resp. min-player) containing $A$ (resp. $B$) different actions. The horizon
length of this finite-horizon Markov game is denoted by $H$. The probability
transition kernel of $\mathcal{MG}$ is denoted by $P=\\{P_{h}\\}_{1\leq h\leq
H}$ with $P_{h}\in\mathbb{R}^{SAB\times S}$; namely, for any
$(s,a,b,h,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]\times\mathcal{S}$,
we let $P_{h}(s^{\prime}\,|\,s,a,b)$ indicate the probability of
$\mathcal{MG}$ transitioning from state $s$ to state $s^{\prime}$ at step $h$
when the max-player takes action $a$ and the min-player takes action $b$.
Additionally, $r=\\{r_{h}\\}_{1\leq h\leq H}$ with $r_{h}\in\mathbb{R}^{SAB}$
represents the reward function; namely, for any
$(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$,
$r_{h}(s,a,b)$ stands for the immediate reward the max-player gains (or the
min-player loses) in state $s$ at step $h$, if the max-player (resp. min-
player) executes action $a$ (resp. $b$). Given that our focal point is the
family of zero-sum Markov games, it suffices to introduce a single reward
function $r$. We shall also assume normalized rewards throughout this paper in
the sense that $r_{h}(s,a,b)\in[0,1]$ for any
$(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$.

##### Value functions under product policies.

Let $\mu=\\{\mu_{h}\\}_{1\leq h\leq H}$ (resp. $\nu=\\{\nu_{h}\\}_{1\leq h\leq
H}$) denote the policy of the max-player (resp. min-player), where
$\mu_{h}(\cdot\,|\,s)\in\Delta(\mathcal{A})$ and
$\nu_{h}(\cdot\,|\,s)\in\Delta(\mathcal{B})$ for any $s\in\mathcal{S}$. More
specifically, $\mu_{h}(a\,|\,s)$ indicates the probability of the max-player
selecting action $a$ in state $s$ at step $h$; and $\nu_{h}(b\,|\,s)$ is
defined analogously. Consider a Markovian trajectory
$\\{(s_{t},a_{t},b_{t},r_{t})\\}_{1\leq t\leq H}$, where $s_{t}$ is the state
at time $t$, $a_{t}$ (resp. $b_{t}$) is the action of the max-player (resp.
min-player) at time $t$, and $r_{t}$ is the immediate reward observed at time
$t$. For any given policy $\mu$ (resp. $\nu$) of the max-player (resp. min-
player) and any step $h$, we define the value function
$V_{h}^{\mu,\nu}:\mathcal{S}\rightarrow\mathbb{R}$ under the product policy
$\mu\times\nu$ as follows:

$V_{h}^{\mu,\nu}(s)\coloneqq\mathbb{E}\left[\sum_{t=h}^{H}r_{t}\big{(}s_{t},a_{t},b_{t}\big{)}\mid
s_{h}=s\right],\qquad\forall s\in\mathcal{S},$ (7)

where the expectation is taken over the Markovian trajectory
$\\{(s_{t},a_{t},b_{t},r_{t})\\}$ with the max-player and the min-player
executing policies $\mu$ and $\nu$, respectively, in an _independent_ fashion;
that is, conditional on $s_{t}$, we draw $a_{t}\sim\mu_{t}(\cdot\,|\,s_{t})$
and $b_{t}\sim\nu_{t}(\cdot\,|\,s_{t})$ independently, and then $s_{t+1}\sim
P_{t}(\cdot\,|\,s_{t},a_{t},b_{t})$. In addition, conditional on the min-
player executing policy $\nu$, the optimal value function
$V^{\star,\nu}=\\{V_{h}^{\star,\nu}\\}_{1\leq h\leq H}$ (with
$V_{h}^{\star,\nu}:\mathcal{S}\rightarrow\mathbb{R}$) of the max-player is
defined as

$V_{h}^{\star,\nu}(s)\coloneqq\max_{\mu:\,\mathcal{S}\times[H]\rightarrow\Delta(\mathcal{A})}V_{h}^{\mu,\nu}(s),\qquad\forall(s,h)\in\mathcal{S}\times[H];$
(8a) similarly, when the max-player chooses to execute policy $\mu$, the
optimal value function $V^{\mu,\star}=\\{V^{\mu,\star}_{h}\\}_{1\leq h\leq H}$
(with $V^{\mu,\star}_{h}:\mathcal{S}\rightarrow\mathbb{R}$) of the min-player
is defined as
$V_{h}^{\mu,\star}(s)\coloneqq\min_{\nu:\,\mathcal{S}\times[H]\rightarrow\Delta(\mathcal{B})}V_{h}^{\mu,\nu}(s),\qquad\forall(s,h)\in\mathcal{S}\times[H].$
(8b)

Furthermore, if we freeze the policy of the min-player to $\nu$, then the
Bellman optimality condition for the max-player can be expressed as
(Bertsekas,, 2017)

$V_{h}^{\star,\nu}(s)=\max_{a\in\mathcal{A}}\left\\{\mathop{\mathbb{E}}\limits_{b\sim\nu_{h}(\cdot|s)}\left[r_{h}(s,a,b)+\Big{\langle}P_{h}(\cdot\,|\,s,a,b),\,V_{h+1}^{\star,\nu}\Big{\rangle}\right]\right\\},\qquad\forall(s,h)\in\mathcal{S}\times[H].$
(9)

##### Solution concept: Nash equilibrium.

In the zero-sum two-player Markov game, the max-player wishes to maximize the
value function, while the min-player aims to minimize the value function
instead. Due to the competing objectives, finding some sort of equilibrium —
particularly the Nash equilibrium (Nash,, 1951) — becomes a central topic in
the studies of Markov games. More precisely, a policy pair
$(\mu^{\star},\nu^{\star})\in\Delta(\mathcal{A})^{SH}\times\Delta(\mathcal{B})^{SH}$
is said to be a (mixed-strategy) Nash equilibrium of $\mathcal{MG}$ if the
resulting product policy $\mu^{\star}\times\nu^{\star}$ obeys

$V_{1}^{\mu^{\star},\nu^{\star}}(s)=V_{1}^{\star,\nu^{\star}}(s)\qquad\text{and}\qquad
V_{1}^{\mu^{\star},\nu^{\star}}(s)=V_{1}^{\mu^{\star},\star}(s),\qquad\text{for
all }s\in\mathcal{S}.$ (10)

In other words, conditional on the opponent’s current policy and the
assumption that the two players take actions independently, no player can
harvest any gain by unilaterally deviating from its current policy.

In practice, it might be challenging to compute an “exact” Nash equilibrium,
and instead one would seek to find approximate solutions. Towards this end, we
find it helpful to define the sub-optimality gap of a policy pair $(\mu,\nu)$
as follows (measured in an $\ell_{\infty}$-based manner)

$\mathsf{NE}\text{-}\mathsf{gap}(\mu,\nu)\coloneqq\max_{s\in\mathcal{S}}\,\mathsf{NE}\text{-}\mathsf{gap}(\mu,\nu;s),$
(11a) where
$\mathsf{NE}\text{-}\mathsf{gap}(\mu,\nu;s)\,\coloneqq\max\Big{\\{}V_{1}^{\star,\nu}(s)-V_{1}^{\mu,\nu}(s),\,V_{1}^{\mu,\nu}(s)-V_{1}^{\mu,\star}(s)\Big{\\}}.$
(11b)

With this sub-optimality measure in place, a policy pair $(\mu,\nu)$ is said
to be an $\varepsilon$-approximate Nash-equilibrium — or more concisely,
$\varepsilon$-Nash — if the resultant sub-optimality gap of the product policy
$\mu\times\nu$ obeys
$\mathsf{NE}\text{-}\mathsf{gap}(\mu,\nu)\leq\varepsilon$.

##### Generative model / simulator.

In reality, we oftentimes do not have access to perfect descriptions (e.g.,
accurate knowledge of the transition kernel $P$) of the Markov game under
consideration; instead, one has to learn the true model on the basis of a set
of data samples. When it comes to the data generating mechanism, this paper
assumes access to a generative model (also called a simulator) (Kearns et
al.,, 2002; Kakade,, 2003): in each call to the generative model, the learner
can choose an arbitrary quadruple
$(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$ and
obtain an independent sample generated based on the true transition kernel:

$s^{\prime}\sim P_{h}(\cdot\,|\,s,a,b).$

In words, a generative model facilitates query of arbitrary state-action-step
combinations, which helps alleviate the sampling constraints arising in online
episodic settings for exploration. The goal of the current paper is to compute
an $\varepsilon$-approximate Nash equilibrium of $\mathcal{MG}$ with as few
samples as possible, i.e., using a minimal number of calls to the generative
model.

##  3 Sample-efficient learning for NE

In this section, we put forward an algorithm aimed at finding an
$\varepsilon$-Nash policy pair with the assistance of a generative model, and
demonstrate its sample optimality for the full $\varepsilon$-range.

###  3.1 Algorithm description

We now describe the proposed algorithm, which is inspired by the optimism
principle and the FTRL algorithm for online/adversarial learning. Following
the dynamic programming approach (Bertsekas,, 2017), our algorithm employs
backward recursion from step $h=H$ back to $h=1$; in fact, we shall finish the
sampling and learning processes for step $h$ before moving backward to step
$h-1$. For each $h$, the max-player (resp. min-player) calls the generative
model for $K$ rounds, with each round drawing $SA$ (resp. $SB$) independent
samples; as a result, the total sample size is given by $KS(A+B)H$. In what
follows, let us first introduce some convenient notation that facilitates our
exposition of the algorithm.

##### Notation.

Consider any step $h\in[H]$, and any data collection round $k\in[K]$. The
algorithm maintains the following iterates, whose notation is gathered here
with their formal definitions introduced later.

  * •

$\overline{V}_{h}\in\mathbb{R}^{S}$ (resp.
$\underline{V}_{h}\in\mathbb{R}^{S}$) represents the final estimate of the
value function at step $h$ by the max-player (resp. min-player); in
particular, we set $\overline{V}_{H+1}=\underline{V}_{H+1}=0$.

  * •

$\overline{Q}_{h}^{k}\in\mathbb{R}^{SA}$ (resp.
$\underline{Q}_{h}^{k}\in\mathbb{R}^{SB}$) represents the Q-function estimate
of the max-player (resp. min-player) at step $h$ after the $k$-th round of
data collection.

  * •

$\overline{q}_{h}^{k}\in\mathbb{R}^{SA}$ (resp.
$\underline{q}_{h}^{k}\in\mathbb{R}^{SB}$) represents a certain “one-step-
look-ahead” Q-function estimate of the max-player (resp. min-player) at step
$h$ using samples collected in the $k$-th round.

  * •

$\overline{r}_{h}^{k}\in\mathbb{R}^{SA}$ (resp.
$\underline{r}_{h}^{k}\in\mathbb{R}^{SB}$) denotes the sample reward vector
for step $h$ received by the max-player (resp. min-player) in the $k$-th
round.

  * •

$\overline{P}_{h}^{k}\in\mathbb{R}^{SA\times S}$ (resp.
$\underline{P}_{h}^{k}\in\mathbb{R}^{SB\times S}$) denotes the empirical
probability transition matrix for step $h$ constructed using the samples
collected by the max-player (resp. min-player) in the $k$-th round.

  * •

$\overline{\beta}_{h,V}\in\mathbb{R}^{S}$ (resp.
$\underline{\beta}_{h,V}\in\mathbb{R}^{S}$) denotes the bonus (resp. penalty)
vector chosen by the max-player (resp. min-player) during final value
estimation.

  * •

$\mu_{h}^{k}:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ (resp.
$\nu_{h}^{k}:\mathcal{S}\rightarrow\Delta(\mathcal{B})$) denotes the policy
iterate of the max-player (resp. min-player) at step $h$ before the beginning
of the $k$-th round of data collection; in particular, we set both
$\mu_{h}^{1}$ and $\nu_{h}^{1}$ to be uniform, namely,
$\mu_{h}^{1}(a\,|\,s)=1/A$ for any $(s,a)\in\mathcal{S}\times\mathcal{A}$ and
$\nu_{h}^{1}(b\,|\,s)=1/B$ for any $(s,b)\in\mathcal{S}\times\mathcal{B}$.

Crucially, the above objects are all constructed from the perspective of a
single player (either the max-player or the min-player), and hence resemble
those needed to operate a “single-agent” MDP (as opposed to MARL). As such,
the complexity of storing/updating the above objects only scales with the
aggregate size of the individual action space, rather than the size of the
product action space.

##### Main steps of the proposed algorithm.

As mentioned above, our algorithm collects multiple rounds of independent
samples for each $h$. In what follows, let us describe the proposed procedure
for the max-player in the $k$-th round for step $h$; the procedure for the
min-player proceeds analogously.

  * 1.

Sampling and model estimation. For each
$(s,a)\in\mathcal{S}\times\mathcal{A}$, draw an independent sample as follows

$b_{k,h,s,a}\sim\nu_{h}^{k}(\cdot\,|\,s),\qquad s^{\prime}_{k,h,s,a}\sim
P_{h}(\cdot\,|\,s,a,b_{k,h,s,a})$ (12a) and receive the reward
$r_{k,h,s,a}=r_{h}\big{(}s,a,b_{k,h,s,a}\big{)}$. These samples are then
employed to construct the sample reward vector
$\overline{r}_{h}^{k}\in\mathbb{R}^{SA}$ and empirical probability transition
kernel $\overline{P}_{h}^{k}\in\mathbb{R}^{SA\times S}$ such that
$\overline{r}_{h}^{k}(s,a)=r_{k,h,s,a}\qquad\text{and}\qquad\overline{P}_{h}^{k}(s^{\prime}\,|\,s,a)=\begin{cases}1,&\text{if
}s^{\prime}=s^{\prime}_{k,h,s,a}\\\ 0,&\text{else}\end{cases}$ (12b)

for all $(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$.
Note that the max-player only needs to compute (12b), without the need of
directly observing the opponent’s actions (i.e., $\\{b_{k,h,s,a}\\}$).

  * 2.

Q-function estimation. Following the dynamic programming approach, we first
compute the “one-step-look-ahead” Q-function estimate as follows

$\displaystyle\overline{q}_{h}^{k}$
$\displaystyle=\overline{r}_{h}^{k}+\overline{P}_{h}^{k}\overline{V}_{h+1}.$
(13)

We then adopt the update rule of Q-learning:

$\displaystyle\overline{Q}_{h}^{k}$
$\displaystyle=(1-\alpha_{k})\overline{Q}_{h}^{k-1}+\alpha_{k}\overline{q}_{h}^{k},$
(14)

where $0<\alpha_{k}<1$ is the learning rate. Applying (14) recursively and
using the quantities defined in (5), we easily arrive at the following
expansion:

$\displaystyle\overline{Q}_{h}^{k}=\sum_{i=1}^{k}\alpha_{i}^{k}\overline{q}_{h}^{i}.$
(15)

  * 3.

Policy updates. Once the Q-estimates are updated, we adopt the exponential
weights strategy to update the policy iterate of the max-player as follows

$\displaystyle\mu_{h}^{k+1}(a\,|\,s)$
$\displaystyle=\frac{\exp\big{(}\eta_{k+1}\overline{Q}_{h}^{k}(s,a)\big{)}}{\sum_{a^{\prime}\in\mathcal{A}}\exp\big{(}\eta_{k+1}\overline{Q}_{h}^{k}(s,a^{\prime})\big{)}},\qquad\forall(s,a)\in\mathcal{S}\times\mathcal{A},$
(16)

where $\eta_{k+1}>0$ denotes another learning rate associated with policy
updates for the max-player (to be specified shortly). In fact, this subroutine
implements the Follow-the-Regularized-Leader update rule (Shalev-Shwartz,,
2012) with

$\displaystyle\mu_{h}^{k+1}(\cdot\,|\,s)$
$\displaystyle=\arg\min_{\pi\in\Delta(\mathcal{A})}~{}\bigg{\\{}-\big{\langle}\pi,\overline{Q}_{h}^{k}(s,\cdot)\big{\rangle}+\frac{1}{\eta_{k+1}}F(\pi)\bigg{\\}},$
(17)

where the regularizer $F(\cdot)$ is chosen to be the negative entropy function
$F(\pi)\coloneqq\sum_{a}\pi(a)\log\big{(}\pi(a)\big{)}$.

After carrying out $K$ rounds of the above procedure, our final policy
estimate $\widehat{\mu}:\mathcal{S}\times[H]\rightarrow\Delta(\mathcal{A})$
and the value estimate $\overline{V}_{h}:\mathcal{S}\rightarrow\mathbb{R}$ for
step $h$ are taken respectively to be

$\displaystyle\widehat{\mu}_{h}$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\mu_{h}^{k}\qquad\qquad\text{and}$
(18a) $\displaystyle\overline{V}_{h}(s)$
$\displaystyle=\min\left\\{\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(\cdot\,|\,s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}+\overline{\beta}_{h,V}(s),~{}H-h+1\right\\}$
(18b)

with $\\{\alpha_{k}^{K}\\}$ defined in (5), where
$\overline{\beta}_{h,V}(s)\geq 0$ is some bonus term (taking the form of some
data-driven upper confidence bound) to be specified momentarily. In
particular, the final policy (18a) is a mixture of the policy iterates
$\\{\mu_{h}^{k}\\}$ and is Markovian in nature (i.e., the action selection
rule depends only on the current state $s$ and step $h$).

The whole procedure, including the algorithm for the min-player, is summarized
in Algorithm 1.

##### Choices of learning rates.

Thus far, we have not yet specified the two sequences of learning rates, which
we describe now. The learning rates associated with Q-function updates are set
to be rescaled linear, namely,

$\displaystyle\alpha_{k}=\frac{c_{\alpha}\log K}{k-1+c_{\alpha}\log K},\qquad
k=1,2,\ldots$ (19)

for some absolute constant $c_{\alpha}\geq 24$. In addition, the learning
rates associated with policy updates are chosen to be:

$\displaystyle\eta_{k+1}$ $\displaystyle=\sqrt{\frac{\log
K}{\alpha_{k}H}},\qquad k=1,2,\ldots$ (20)

##### Choices of bonus terms.

It remains to specify the bonus terms, which are selected based on fairly
intricate upper confidence bounds and constitutes a key (and perhaps most
challenging) component of our algorithm design. Specifically, we take

$\displaystyle\overline{\beta}_{h,V}(s)$
$\displaystyle=c_{\mathsf{b}}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\sum_{k=1}^{K}\alpha_{k}^{K}\Bigg{\\{}\mathsf{Var}_{\mu_{h}^{k}(\cdot\mid
s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+H\Bigg{\\}}$ (21)

for any $(s,h)\in\mathcal{S}\times[H]$, where $c_{\mathsf{b}}>0$ is some
sufficiently large constant; see also (6) for the definition of the variance-
style term. As in previous works, the bonus term, which is chosen carefully in
a data-driven fashion, needs to compensate for the uncertainty incurred during
the estimation process.

1 Input: nmber of rounds $K$ for each step, learning rates $\\{\alpha_{k}\\}$
(see (19)) and $\\{\eta_{k+1}\\}$ (see (20)).

// set initial value estimates to 0, and initial policies to uniform
distributions.

2 Initialize: for all
$(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, set
$\overline{V}_{H+1}(s)=\underline{V}_{H+1}(s)=\overline{Q}_{h}^{0}(s,a)=\underline{Q}_{h}^{0}(s,b)=0$,
$\mu_{h}^{1}(a\,|\,s)=1/A$ and $\nu_{h}^{1}(b\,|\,s)=1/B$.

3 for  _$h=H$ to $1$_ do

4 for  _$k=1$ to $K$_ do

// draw independent samples, and construct empirical models.

$\big{(}\overline{r}_{h}^{k},\underline{r}_{h}^{k},\overline{P}_{h}^{k},\underline{P}_{h}^{k}\big{)}$
$\leftarrow$ sampling$\big{(}h,\mu_{h}^{k},\nu_{h}^{k}\big{)}$. /* see
Algorithm 2. */

5

// update Q-estimates with upper/lower confidence bounds.

6 Compute
$\overline{q}_{h}^{k}=\overline{r}_{h}^{k}+\overline{P}_{h}^{k}\overline{V}_{h+1}$,
$\underline{q}_{h}^{k}=\underline{r}_{h}^{k}+\underline{P}_{h}^{k}\underline{V}_{h+1}$,
and update
$\displaystyle\overline{Q}_{h}^{k}=(1-\alpha_{k})\overline{Q}_{h}^{k-1}+\alpha_{k}\overline{q}_{h}^{k},\quad\underline{Q}_{h}^{k}=(1-\alpha_{k})\underline{Q}_{h}^{k-1}+\alpha_{k}\underline{q}_{h}^{k}.$

// update policy estimates using FTRL.

7 for  _$(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$_ do

8
$\displaystyle\mu_{h}^{k+1}(a\,|\,s)=\frac{\exp\big{(}\eta_{k+1}\overline{Q}_{h}^{k}(s,a)\big{)}}{\sum_{a^{\prime}}\exp\big{(}\eta_{k+1}\overline{Q}_{h}^{k}(s,a^{\prime})\big{)}},~{}\nu_{h}^{k+1}(b\,|\,s)=\frac{\exp\big{(}-\eta_{k+1}\underline{Q}_{h}^{k}(s,b)\big{)}}{\sum_{b^{\prime}}\exp\big{(}-\eta_{k+1}\underline{Q}_{h}^{k}(s,b^{\prime})\big{)}}.$

9

// output the final policy estimate and value estimate for step $h$.

10 Update  $\displaystyle\widehat{\mu}_{h}$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\mu_{h}^{k},~{}~{}$
$\displaystyle\overline{V}_{h}(s)=\min\left\\{\sum_{k=1}^{K}\alpha_{k}^{K}\big{\langle}\mu_{h}^{k}(\cdot\,|\,s),\,\overline{q}_{h}^{k}(s,\cdot)\big{\rangle}+\overline{\beta}_{h,V}(s),~{}H-h+1\right\\},~{}\forall
s\in\mathcal{S},$ $\displaystyle\widehat{\nu}_{h}$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\nu_{h}^{k},$
$\displaystyle\underline{V}_{h}(s)=\max\left\\{\sum_{k=1}^{K}\alpha_{k}^{K}\big{\langle}\mu_{h}^{k}(\cdot\,|\,s),\,\underline{q}_{h}^{k}(s,\cdot)\big{\rangle}-\underline{\beta}_{h,V}(s),~{}0\right\\},~{}\forall
s\in\mathcal{S},$ where $\overline{\beta}_{h,V}^{k}$ is given in (21), and
$\underline{\beta}_{h,V}^{k}$ is obtained by replacing
($\mu_{h}^{k},\overline{q}_{h}^{k}$) in (21) with
($\nu_{h}^{k},\underline{q}_{h}^{k}$).

Output: $\widehat{\mu}=\\{\widehat{\mu}_{h}\\}_{1\leq h\leq H}$ and
$\widehat{\nu}=\\{\widehat{\nu}_{h}\\}_{1\leq h\leq H}$.

Algorithm 1 Nash-Q-FTRL.

1

2Initialize: $\overline{r}=0\in\mathbb{R}^{SA}$,
$\underline{r}=0\in\mathbb{R}^{SB}$, $\overline{P}=0\in\mathbb{R}^{SA\times
S}$, and $\underline{P}=0\in\mathbb{R}^{SB\times S}$.

3for  _$(s,a)\in\mathcal{S}\times\mathcal{A}$_ do

4 Draw an independent sample from the generative model:
$b_{h,s,a}\sim\nu_{h}(\cdot\,|\,s),\qquad s^{\prime}_{h,s,a}\sim
P_{h}(\cdot\,|\,s,a,b_{h,s,a}).$ (22)

5 set $\overline{r}(s,a)=r_{h}\big{(}s,a,b_{h,s,a}\big{)}$ and
$\overline{P}\big{(}s^{\prime}_{h,s,a}\,|\,s,a\big{)}=1$.

6

7for  _$(s,b)\in\mathcal{S}\times\mathcal{B}$_ do

8 Draw an independent sample from the generative model:
$a_{h,s,b}\sim\mu_{h}(\cdot\,|\,s),\qquad s^{\prime}_{h,s,a}\sim
P_{h}(\cdot\,|\,s,a_{h,s,b},b).$ (23)

9 set $\underline{r}(s,b)=r_{h}\big{(}s,a_{h,s,b},b\big{)}$ and
$\underline{P}\big{(}s^{\prime}_{h,s,a}\,|\,s,b\big{)}=1$.

10

11Return:
$\big{(}\overline{r},\underline{r},\overline{P},\underline{P}\big{)}$.

Algorithm 2 Auxiliary function sampling$\big{(}h,\mu_{h},\nu_{h}\big{)}$.

###  3.2 Main results

As it turns out, the proposed algorithm is provably sample-efficient, whose
sample complexity is characterized by the following theorem.

######  Theorem 1.

Consider any $\varepsilon\in(0,H]$ and any $0<\delta<1$. Suppose that

$K\geq\frac{c_{\mathsf{k}}H^{3}\log^{4}\frac{KS(A+B)}{\delta}}{\varepsilon^{2}}$
(24)

for some large enough universal constant $c_{\mathsf{k}}>0$. With probability
at least $1-\delta$, the sub-optimality gap (cf. (11)) of the policies
$(\widehat{\mu},\widehat{\nu})$ returned by Algorithm 1 obeys

$\displaystyle\mathsf{NE}\text{-}\mathsf{gap}\big{(}\widehat{\mu},\widehat{\nu}\big{)}\leq\varepsilon.$

Theorem 1 establishes a sample complexity upper bound for the proposed
algorithm, which we take a moment to interpret as follows. The proof of this
theorem is postponed to Section 5.

##### Sample complexity.

When a generative model is available, Theorem 1 asserts that the total number
of samples (i.e., $KS(A+B)H$) needed for Algorithm 1 to yield
$\varepsilon$-Nash policies is at most

$\displaystyle\text{(sample
complexity)}\qquad\widetilde{O}\bigg{(}\frac{H^{4}S(A+B)}{\varepsilon^{2}}\bigg{)}.$
(25)

As far as we know, this delivers the first result — for any sampling protocol
— that simultaneously overcomes the long-horizon barrier and the curse of
multiple agents. In comparison to Zhang et al., (2020) (cf. (1)), our result
reveals that what ultimately matters is the total number of individual actions
(i.e., $A+B$) as opposed to the total number $AB$ of possible joint actions.
Additionally, our result exhibits improved horizon dependency (by a factor of
$H^{2}$) compared to Bai et al., (2020); Jin et al., (2021) (see (3)),
although we remark that the online sampling protocol therein is more
restrictive than a generative model.

##### Minimax optimality.

In order to assess the tightness of our sample complexity bound (25), it is
helpful to take a look at the information theoretical limit. Suppose without
loss of generality that $A\geq B$. Consider the extreme scenario where $B=1$,
in which case the Nash-equilibrium reduces to the optimal policy of a single-
agent MDP with $S$ states and $A$ actions. It is well-known that for any given
accuracy level $\varepsilon\in(0,H]$, one can construct a non-stationary MDP
with $S$ states and $A$ actions such that no algorithm can learn an
$\varepsilon$-optimal policy with fewer than the order of
$\frac{H^{4}SA}{\varepsilon^{2}}$ samples (Azar et al.,, 2013; Li et al.,,
2022). This means that in general, the minimax sample complexity lower bound
(w.r.t. finding an $\varepsilon$-Nash policy pair) scales as

$\displaystyle\text{(minimax lower
bound)}\qquad\frac{H^{4}S(A+B)}{\varepsilon^{2}}$ (26)

modulo some logarithmic factor; see Appendix B.3 for a formal statement and
its proof. Taking this together with (25) confirms the minimax optimality of
our algorithm (up to logarithmic terms).

##### No burn-in sample size and full $\varepsilon$-range.

It is noteworthy that the validity of our sample complexity bound (25) is
guaranteed for the entire range of $\varepsilon$-levels (i.e., any
$\varepsilon\in(0,H]$). This feature is particularly appealing in the data-
starved applications, as it implies that there is no burn-in sample size
needed for our algorithm to work optimally.

##### Miscellaneous properties of our algorithm.

Finally, we would like to remark in passing that our learning algorithm enjoys
several properties that might be practically appealing. For instance, the
output policies are Markovian in nature, which depend only on the current
state $s$ and step number $h$. This is enabled thanks to the availability of
the generative model, which allows us to settle the sampling and learning
process for step $h+1$ completely before moving backward to step $h$; in
contrast, the online sampling protocol studied in Bai et al., (2020); Jin et
al., (2021) cannot be implemented in this way without incurring information
loss. In addition, our algorithm can be carried out in a decentralized
fashion, with two players acting in a symmetric and independent manner
(without the need of knowing each other’s individual action); and our
algorithm is “rational” in the sense that it converges to the best-response
policy if one of the players freezes its policy. All this is achieved under
minimal sample complexity with the aid of the generative model.

##  4 Regret bounds for FTRL via variance-type quantities

Before embarking on our analysis for Markov games, we take a detour to study
the celebrated Follow-the-Regularized-Leader algorithm for online weighted
linear optimization, which plays a central role in the analysis of Markov
games.

###  4.1 Setting: online learning for weighted linear optimization

Let $\ell_{1},\ldots,\ell_{n}\in\mathbb{R}^{A}$ represent an arbitrary
sequence of non-negative loss vectors. We focus on the following setting of
online learning or adversarial learning (Lattimore and Szepesvári,, 2020): in
each round $k$,

  * 1.

the learner makes a randomized prediction by choosing a distribution
$\pi_{k}\in\Delta(\mathcal{A})$ over the actions in
$\mathcal{A}=\\{1,\cdots,A\\}$;

  * 2.

subsequently, the learner observes the loss vector $\ell_{k}$, which is
permitted to be adversarially chosen.

To evaluate the performance of the learner, we resort to a regret metric
w.r.t. a certain weighted linear objective function. To be precise, consider a
non-negative sequence $\\{\alpha_{k}\\}_{1\leq k\leq n}$ with
$0\leq\alpha_{k}\leq 1$; for each $1\leq k\leq n$, we define recursively the
following weighted average of the loss vectors:

$\displaystyle L_{0}=0\qquad\text{and}\qquad
L_{k}=(1-\alpha_{k})L_{k-1}+\alpha_{k}\ell_{k},\quad k\geq 1,$

which can be easily shown to enjoy the following expression

$\displaystyle L_{k}=\sum_{i=1}^{k}\alpha_{i}^{k}\ell_{k}$

with $\alpha_{i}^{k}$ defined in (5). When the sequential predictions made by
the learner are $\\{\pi_{k}\\}_{k\geq 1}$, we define the associated regret
w.r.t. the above weighted sum of loss vectors as follows:

$\displaystyle R_{n}$
$\displaystyle\coloneqq\max_{a\in\mathcal{A}}R_{n}(a)\qquad\text{with
}\,R_{n}(a)\coloneqq\sum_{k=1}^{n}\alpha_{k}^{n}\langle\pi_{k},\ell_{k}\rangle-\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}(a),$
(27)

which compares the learner’s performance (i.e., the expected loss of the
learner over time if it draws actions based on $\pi_{k}$ in round $k$) against
that of the best fixed action in hindsight.

###  4.2 Refined regret bounds for FTRL

##### Follow-the-Regularized-Leader.

The FTRL algorithm (Shalev-Shwartz and Singer,, 2007; Shalev-Shwartz,, 2007)
tailored to the above online optimization setting adopts the following update
rule:

$\displaystyle\pi_{k+1}$
$\displaystyle=\arg\min_{\pi\in\Delta(\mathcal{A})}~{}\bigg{\\{}\langle\pi,L_{k}\rangle+\frac{1}{\eta_{k+1}}F(\pi)\bigg{\\}},\qquad
k=1,2,\ldots$ (28)

where $\eta_{k+1}>0$ denotes the learning rate, and $F(\cdot)$ is some convex
regularization function employed to stabilize the learning process (Shalev-
Shwartz,, 2012). Throughout this section, we restrict our attention to
negative-entropy regularization, namely,

$\displaystyle F(\pi)=\sum_{a\in\mathcal{A}}\pi(a)\log\big{(}\pi(a)\big{)},$

which allows one to express the FTRL update rule as the following exponential
weights strategy (see, e.g., Lattimore and Szepesvári, (2020, Section 28.1))

$\displaystyle\pi_{k+1}(a)=\frac{\exp\big{(}-\eta_{k+1}L_{k}(a)\big{)}}{\sum_{a^{\prime}\in\mathcal{A}}\exp\big{(}-\eta_{k+1}L_{k}(a^{\prime})\big{)}}\qquad\text{for
all }a\in\mathcal{A}.$ (29)

This update rule is also intimately connected to online mirror descent
(Lattimore and Szepesvári,, 2020).

##### Refined regret bounds via variance-style quantities.

As it turns out, the regret of FTRL can be upper bounded by certain (weighted)
variance-type quantities, as asserted by the following theorem.

######  Theorem 2.

Suppose that $0<\alpha_{1}\leq 1$ and $\eta_{1}=\eta_{2}(1-\alpha_{1})$. Also,
assume that $0<\alpha_{k}<1$ and $0<\eta_{k+1}(1-\alpha_{k})\leq\eta_{k}$ for
all $k\geq 2$. In addition, define

$\displaystyle\widehat{\eta}_{k}\coloneqq\begin{cases}\eta_{2},&\text{if
}k=1,\\\ \frac{\eta_{k}}{1-\alpha_{k}},\quad&\text{if }k>1.\end{cases}.$ (30)

Then the regret (cf. (27)) of the FTRL algorithm satisfies

$\displaystyle R_{n}$
$\displaystyle\leq\frac{5}{3}\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}\alpha_{k}\mathsf{Var}_{\pi_{k}}(\ell_{k})+\frac{\log
A}{\eta_{n+1}}+3\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\big{\|}\ell_{k}\big{\|}_{\infty}^{3}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)},$
(31)

where for any $\ell\in\mathbb{R}^{A}$ and any $\pi\in\Delta(\mathcal{A})$ we
define

$\displaystyle\mathsf{Var}_{\pi}(\ell)\coloneqq\sum_{a}\pi(a)\Big{(}\ell(a)-\sum_{a^{\prime}}\pi(a^{\prime})\ell(a^{\prime})\Big{)}^{2}.$

######  Remark 1.

Note that the FTRL algorithm and the data generating process in this section
are both described in a completely deterministic manner; no randomness is
involved in the above theorem even though we introduce the variance-style
quantities.

The proof of Theorem 2 is postponed to Appendix A. Let us take a moment to
discuss the key distinction between Theorem 2 and prior theory.

  * •

A key term in the regret bound (31) is a weighted sum of the “variance-style”
quantities $\\{\mathsf{Var}_{\pi_{k}}(\ell_{k})\\}$. In comparison, prior
regret bounds typically involve the norm-type quantities (e.g., the infinity
norms $\\{\|\ell_{k}\|_{\infty}^{2}\\}$) as opposed to the “variances”; see,
for instance, Lattimore and Szepesvári, (2020, Corollary 28.8) for a
representative existing regret bound that takes the form of the sum of
$\\{\|\ell_{k}\|_{\infty}^{2}\\}$ that takes the form of the sum of
$\\{\|\ell_{k}\|_{\infty}^{2}\\}$.111Note that the Bregman divergence
generated by the negative entropy function is the (generalized) KL divergence
(Beck,, 2017), which is strongly convex w.r.t. $\|\cdot\|_{1}$ due to
Pinsker’s inequality. Additionally, the dual norm of $\|\cdot\|_{1}$ is the
infinity norm. While $\mathsf{Var}(\ell_{k})\leq\|\ell_{k}\|_{\infty}^{2}$ is
orderwise tight in the worst-case scenario for a given iteration $k$,
exploiting the problem-specific variance-type structure across time is crucial
in sharpening the horizon dependence in many RL problems (e.g., Azar et al.,
(2013); Jin et al., (2018); Li et al., (2022); Li et al., 2021c ).

  * •

The careful reader would remark that the final term of (31) relies on the
infinity norm $\|\ell_{k}\|_{\infty}$ as well. Fortunately, when the products
of the learning rates $\widehat{\eta}_{k}\alpha_{k}$ are chosen to be
diminishing (which is the case in our analysis for Markov games), the number
of iterations obeying $\widehat{\eta}_{k}\alpha_{k}\|\ell_{k}\|_{\infty}>1/3$
is reasonably small, thus ensuring that this term does not exert too much of
an influence on the regret bound.

##  5 Proof of Theorem 1

In this section, we present the proof of Theorem 1, following some preliminary
facts and notation.

###  5.1 Preliminaries and notation

Given that $\varepsilon\leq H$, the assumption (24) necessarily requires that

$\displaystyle K\geq c_{\mathsf{k}}H\log^{4}\frac{KS(A+B)}{\delta}$ (32)

for some large enough constant $c_{\mathsf{k}}>0$, which will be a condition
assumed throughout the proof. We also gather below several basic facts about
our choices of learning rates $\\{\alpha_{i}\\}$ (cf. (19)) and the
corresponding quantities $\\{\alpha_{i}^{k}\\}$ (cf. (5)).

######  Lemma 1.

For any $k\geq 1$, one has

$\alpha_{1}=1,\qquad\sum_{i=1}^{k}\alpha_{i}^{k}=1,\qquad\max_{1\leq i\leq
k}\alpha_{i}^{k}\leq\frac{2c_{\alpha}\log K}{k}.$ (33a) In addition, if $k\geq
c_{\alpha}\log K+1$ and $c_{\alpha}\geq 24$, then one has $\max_{1\leq i\leq
k/2}\alpha_{i}^{k}\leq 1/K^{6}.$ (33b)

###### Proof.

The result (33a) is standard and has been recorded in previous works (e.g.,
Jin et al., (2018, Appendix B)). Regarding (33b), we note that for any $i\leq
k/2$ and $k\geq c_{\alpha}\log K+1$,

$\alpha_{i}^{k}\leq\prod_{j=i+1}^{k}(1-\alpha_{j})\leq\prod_{j=k/2+1}^{k}(1-\alpha_{j})\leq(1-\alpha_{k})^{k/2}\leq\Big{(}1-\frac{c_{\alpha}\log
K}{2k}\Big{)}^{k/2}\leq\exp\Big{(}-\frac{c_{\alpha}\log
K}{4}\Big{)}\leq\frac{1}{K^{6}},$

where we have used the fact that $\alpha_{k}=\frac{c_{\alpha}\log
K}{k-1+c_{\alpha}\log K}\geq\frac{c_{\alpha}\log K}{2k}$ and the assumption
$c_{\alpha}\geq 24$. ∎

Additionally, recognizing the definition in (13) and the upper bound
$\overline{V}_{h+1}(s)\leq H-h+1$ (cf. (18b)), we make note of the range of
the iterates $\big{\\{}\overline{q}_{h}^{k}\big{\\}}$ as follows.

######  Lemma 2.

For any $(h,k,s,a)\in[H]\times[K]\times\mathcal{S}\times\mathcal{A}$, it holds
that

$\displaystyle 0\leq\overline{q}_{h}^{k}(s,a)\leq H-h+1.$ (34)

Next, we introduce several additional notation that helps simplify our
presentation of the proof. For any policy
$\mu:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ and any
$\nu:\mathcal{S}\rightarrow\Delta(\mathcal{B})$, we adopt the convenient
notation

$\displaystyle\mu(s)\coloneqq\mu(\cdot\,|\,s)\in\Delta(\mathcal{A})\qquad\text{and}\qquad\nu(s)\coloneqq\nu(\cdot\,|\,s)\in\Delta(\mathcal{B}),\qquad\qquad\forall
s\in\mathcal{S}.$

We shall also employ the expectation operator $\mathbb{E}_{h,k-1}[\cdot]$
(resp. variance operator $\mathsf{Var}_{h,k-1}[\cdot]$) to denote the
expectation (resp. variance) conditional on what happens before the beginning
of the $k$-th round of data collection for step $h$ (see Section 3.1 about the
data collection process).

###  5.2 Proof outline

With the above preliminaries in place, we are in a position to present our
analysis. Let us single out an intermediate value function that is intimately
connected to both $\widehat{\mu}$ and $\widehat{\nu}$ as follows:

$\displaystyle V_{H+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)$
$\displaystyle\coloneqq 0$ (35a) $\displaystyle
V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)$
$\displaystyle\coloneqq\sum_{k=1}^{K}\sum_{(a,b)\in\mathcal{A}\times\mathcal{B}}\alpha_{k}^{K}\mu_{h}^{k}(a\,|\,s)\nu_{h}^{k}(b\,|\,s)\Big{[}r_{h}(s,a,b)+\big{\langle}P_{h}(\cdot\,|\,s,a,b),V_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{\rangle}\Big{]}$
(35b)

for all $(s,h)\in\mathcal{S}\times[H]$. In other words, in each step $h$, the
joint policy pair generating the above value function is chosen to be the
mixture of product policies
$\sum_{k=1}^{K}\alpha_{k}^{K}\big{(}\mu_{h}^{k}\times\nu_{h}^{k}\big{)}$. We
remark that here and below, when we write the joint policy pair
$\widehat{\mu}\,\cdot\,\widehat{\nu}$, we allow them to be dependent of each
other, which should not be understood differently as the product measure
$\widehat{\mu}\times\widehat{\nu}$ when policy $\widehat{\mu}$ and
$\widehat{\nu}$ are executed independently.

It is easily seen that to establish Theorem 1, it suffices to prove the
following two inequalities:

$\displaystyle
V_{1}^{\star,\widehat{\nu}}(s)-V_{1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)\leq\varepsilon/2\qquad\text{and}\qquad
V_{1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)-V_{1}^{\widehat{\mu},\star}(s)\leq\varepsilon/2,$
(36)

In this subsection, we shall only prove the first inequality in (36); the
second one in (36) can be established in the same way and hence we omit the
proof for brevity.

Towards this, let us introduce the following policy:

$\displaystyle\widetilde{\mu}^{\star}=\arg\max_{\mu:\mathcal{S}\times[H]\rightarrow\Delta(\mathcal{A})}V_{1}^{\mu,\widehat{\nu}}.$

We observe the following key decomposition

$\displaystyle
V_{h}^{\star,\widehat{\nu}}-V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\leq\big{(}V_{h}^{\star,\widehat{\nu}}-\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}+\big{(}\overline{V}_{h}^{\star,\widehat{\nu}}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}+\big{(}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)},$
(37)

where we define

$\displaystyle\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}(s)$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}\limits_{a\sim\widetilde{\mu}^{\star}_{h}(s)}\Big{[}\overline{r}_{h}^{k}(s,a)+\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a),\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{\rangle}\Big{]},\qquad$
$\displaystyle\text{with
}\overline{V}_{H+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}=0,$ (38a)
$\displaystyle\overline{V}_{h}^{\star,\widehat{\nu}}(s)$
$\displaystyle\coloneqq\max_{a\in\mathcal{A}}\sum_{k=1}^{K}\alpha_{k}^{K}\Big{[}\overline{r}_{h}^{k}(s,a)+\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a),\overline{V}_{h+1}^{\star,\widehat{\nu}}\big{\rangle}\Big{]},\qquad$
$\displaystyle\text{with }\overline{V}_{H+1}^{\star,\widehat{\nu}}=0,$ (38b)
$\displaystyle\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{a\sim\mu_{h}^{k}(s)}\Big{[}\overline{r}_{h}^{k}(s,a)+\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a),\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{\rangle}\Big{]},\qquad$
$\displaystyle\text{with
}\overline{V}_{H+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}=0.$ (38c)

Here, we have used
$\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\leq\overline{V}_{h}^{\star,\widehat{\nu}}$
given that $\widetilde{\mu}^{\star}$ is a policy that does not change with the
index $k$. We shall establish bounds for the above terms, which is composed of
three steps as outlined below.

##### Step 1: showing that $\overline{V}_{h}$ is an entrywise upper bound on
$\overline{V}_{h}^{\star,\widehat{\nu}}$.

The following lemma ascertains that the value estimate $\overline{V}_{h}$ of
the max-player returned by Algorithm 1 is an optimistic estimate of the
auxiliary value $\overline{V}_{h}^{\star,\widehat{\nu}}$ defined in (38b).
Evidently, this result cannot happen unless the bonus terms are suitably
chosen.

######  Lemma 3.

With probability at least $1-\delta$, it holds that

$\displaystyle\overline{V}_{h}\geq\overline{V}_{h}^{\star,\widehat{\nu}},\qquad\quad\text{for
all }1\leq h\leq H.$ (39)

The proof of this lemma is postponed to Appendix B.1. Armed with Lemma 3, we
can further bound (37) as follows

$\displaystyle
V_{h}^{\star,\widehat{\nu}}-V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\leq\big{(}V_{h}^{\star,\widehat{\nu}}-\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}+\big{(}\overline{V}_{h}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}+\big{(}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}.$
(40)

##### Step 2: establishing a key recurrence.

Let us define the auxiliary reward vectors
$r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}},r_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}},\overline{r}_{h}\in\mathbb{R}^{S}$
and auxiliary probability transition matrices
$P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}},P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}},\overline{P}_{h}\in\mathbb{R}^{S\times
S}$ such that: for any $s,s^{\prime}\in\mathcal{S}$,

$\displaystyle r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{(a,b)\sim\mu_{h}^{k}(s)\times\nu_{h}^{k}(s)}\big{[}r_{h}(s,a,b)\big{]},$
(41a) $\displaystyle
P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,s^{\prime})$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{(a,b)\sim\mu_{h}^{k}(s)\times\nu_{h}^{k}(s)}\big{[}P_{h}(s^{\prime}\,|\,s,a,b)\big{]},$
(41b) $\displaystyle r_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}(s)$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{(a,b)\sim\widetilde{\mu}^{\star}_{h}(s)\times\nu_{h}^{k}(s)}\big{[}r_{h}(s,a,b)\big{]},$
(41c) $\displaystyle
P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}(s,s^{\prime})$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{(a,b)\sim\widetilde{\mu}^{\star}_{h}(s)\times\nu_{h}^{k}(s)}\big{[}P_{h}(s^{\prime}\,|\,s,a,b)\big{]},$
(41d) $\displaystyle\overline{r}_{h}(s)$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\sum_{a\in\mathcal{A}}\mu_{h}^{k}(a\,|\,s)\overline{r}_{h}^{k}(s,a),$
(41e) $\displaystyle\overline{P}_{h}(s,s^{\prime})$
$\displaystyle\coloneqq\sum_{k=1}^{K}\alpha_{k}^{K}\sum_{a\in\mathcal{A}}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(s^{\prime}\,|\,s,a).$
(41f)

As it turns out, $\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}$
(resp. $\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}$,
$\overline{V}_{h}$) stays reasonably close to the “one-step-look-ahead”
expression
$r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}$
(resp.
$r_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}+P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}$,
$\overline{r}_{h}+\overline{P}_{h}\overline{V}_{h+1}$), as revealed by the
recursive relations stated in the following lemma; the proof of this lemma is
deferred to Appendix B.2.

######  Lemma 4.

There exists some universal constant $c_{3}>0$ such that with probability
exceeding $1-\delta$,

$\displaystyle\Big{|}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-\big{(}r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{|}\leq
c_{3}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1$
$\displaystyle\qquad\qquad+c_{3}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{]},$
(42a)
$\displaystyle\Big{|}\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}-\big{(}r_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}+P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}\Big{|}\leq
c_{3}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1$
$\displaystyle\qquad\qquad+c_{3}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\Big{[}P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\circ\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}\Big{]},$
(42b)
$\displaystyle\Big{|}\overline{V}_{h}-\big{(}\overline{r}_{h}+\overline{P}_{h}\overline{V}_{h+1}\big{)}\Big{|}\leq
c_{3}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1$
$\displaystyle\qquad\qquad+c_{3}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\Big{[}\overline{P}_{h}\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\big{(}\overline{P}_{h}\overline{V}_{h+1}\big{)}\circ\big{(}\overline{P}_{h}\overline{V}_{h+1}\big{)}\Big{]}$
(42c)

hold for all $h\in[H]$.

######  Remark 2.

The right-hand side of each of the bounds in (42) contains a variance-style
term (e.g., those terms taking the form of $P_{h}(V_{h+1}\circ
V_{h+1})-(P_{h}V_{h+1})\circ(P_{h}V_{h+1})$ for some probability transition
matrix $P_{h}$ and value vector $V_{h+1}$). Such variance-style terms are
direct consequences of our Bernstein-style bonus terms, and are crucial in
optimizing the horizon dependency.

With the above lemma in place, one can readily show that

$\displaystyle\Big{|}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\Big{|}$
$\displaystyle\leq
r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+c_{3}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1$
$\displaystyle\qquad+\frac{c_{3}}{H}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{]}$
$\displaystyle\leq\frac{c_{4}}{4}1+\frac{1}{4H}\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{]}\eqqcolon\zeta_{0}$
(43)

for some large enough constant $c_{4}>0$, where the last line holds due to the
condition (32), the basic fact
$P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\geq\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}$,
and the following fact (for large enough $c_{4}$)

$\displaystyle
c_{3}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1+r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\leq
c_{3}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1+1\leq\frac{c_{4}}{4}1.$

In addition, recalling that
$\|\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\|_{\infty},\|\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\|_{\infty}\leq
H$ (cf. (18b)) and recognizing that $\zeta_{0}\geq 0$ (see (43)), we can
demonstrate that

$\displaystyle\Big{|}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{|}=\Big{|}\big{(}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{|}$
$\displaystyle\qquad\leq\big{(}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\zeta_{0}\leq
2H\zeta_{0}$
$\displaystyle\qquad=\frac{c_{4}}{2}H1+\frac{1}{2}\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{]}.$
(44)

This further leads to

$\displaystyle
P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}$
$\displaystyle\quad=P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}$
$\displaystyle\quad\leq
P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+\frac{c_{4}}{2}H1+\frac{1}{2}\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{]},$

which can be rearranged to yield

$\displaystyle
P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\circ\big{(}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}$
$\displaystyle\leq
2\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\Big{]}+c_{4}H1.$

Substituting it into (42a) and combining terms give

$\displaystyle\Big{|}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-\big{(}r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{|}$
$\displaystyle\leq c_{5}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1$
$\displaystyle\qquad+2c_{3}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\Big{]},$
(45)

where we take $c_{5}=c_{3}+c_{3}c_{4}$.

An analogous argument (which is omitted here for brevity) also reveals that

$\displaystyle\Big{|}\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}-\big{(}r_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}+P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}\Big{|}$
$\displaystyle\leq c_{5}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1$
$\displaystyle\qquad+2c_{3}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\Big{[}P_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\circ\overline{V}_{h+1}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}-\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\circ\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\Big{]},$
(46)
$\displaystyle\Big{|}\overline{V}_{h}-\big{(}\overline{r}_{h}+\overline{P}_{h}\overline{V}_{h+1}\big{)}\Big{|}$
$\displaystyle\leq c_{5}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}1$
$\displaystyle\qquad+2c_{3}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\Big{[}\overline{P}_{h}\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\overline{V}_{h}\circ\overline{V}_{h}\Big{]}.$
(47)

##### Step 3: invoking the key recursion to establish the desired bound.

We find it helpful to introduce the following notation (please note the order
of the matrix product)

$\prod_{j:j<h}P_{j}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\coloneqq\begin{cases}P_{1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\cdots
P_{h-1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}},&\text{if }h>1,\\\ I,&\text{if
}h=1.\end{cases}$

Armed with this notation, we can invoke the relation (45) recursively and use
$\overline{V}_{H+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}={V}_{H+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}=0$
to obtain

$\displaystyle\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}$
$\displaystyle=r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+\Big{(}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-\big{(}r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{)}-\big{(}r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}V_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}$
$\displaystyle\leq
P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-V_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}+\Big{|}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-\big{(}r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}+P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\Big{|}$
(48) $\displaystyle\leq
c_{5}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}\left(\sum_{h=1}^{H}\prod_{j:j<h}P_{j}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\right)1$
$\displaystyle\qquad+2c_{3}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\sum_{h=1}^{H}\prod_{j:j<h}P_{j}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\Big{[}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{(}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\circ\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\Big{]}$
$\displaystyle\leq
c_{5}\sqrt{\frac{H\log^{3}\frac{KS(A+B)}{\delta}}{K}}\left(\sum_{h=1}^{H}\prod_{j:j<h}P_{j}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\right)1=c_{5}\sqrt{\frac{H^{3}\log^{3}\frac{KS(A+B)}{\delta}}{K}}1\leq\frac{\varepsilon}{6}1.$
(49)

Here, the first line uses the Bellman equation, the third inequality holds
since for any transition matrices $\\{P_{h}\\}$ and any sequence $\\{V_{h}\\}$
obeying $V_{H+1}=0$, one can use the telescoping sum to obtain

$\displaystyle\sum_{h=1}^{H}\prod_{j:j<h}P_{j}\Big{[}P_{h}\big{(}V_{h+1}\circ
V_{h+1}\big{)}-V_{h}\circ V_{h}\Big{]}$
$\displaystyle=\sum_{h=1}^{H}\prod_{j:j\leq h}P_{j}\big{(}V_{h+1}\circ
V_{h+1}\big{)}-\sum_{h=1}^{H}\prod_{j:j<h}P_{j}\big{(}V_{h}\circ V_{h}\big{)}$
$\displaystyle=\prod_{j:j\leq H}P_{j}\big{(}V_{H+1}\circ
V_{H+1}\big{)}-V_{1}\circ V_{1}$ $\displaystyle=-V_{1}\circ V_{1}\leq 0,$

whereas the last inequality in (49) arises from the assumption (24) when
$c_{\mathsf{k}}$ is large enough. Similarly, replacing $\widehat{\mu}$ with
$\widetilde{\mu}^{\star}$ in the above argument and recalling (46) directly
lead to

$\displaystyle
V_{h}^{\star,\widehat{\nu}}-\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}=V_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}-\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\leq\frac{\varepsilon}{6}1.$
(50)

In addition, recalling the definition of
$\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}$ (cf. (38c)),
$\overline{r}_{h}$ and $\overline{P}_{h}$ (see (41)), we can deduce that

$\displaystyle\overline{V}_{h}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}$
$\displaystyle=\overline{r}_{h}+\overline{P}_{h}\overline{V}_{h+1}+\Big{\\{}\overline{V}_{h}-\big{(}\overline{r}_{h}+\overline{P}_{h}\overline{V}_{h+1}\big{)}\Big{\\}}-\overline{r}_{h}-\overline{P}_{h}\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}$
$\displaystyle\leq\overline{P}_{h}\big{(}\overline{V}_{h+1}-\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}+\Big{|}\overline{V}_{h}-\big{(}\overline{r}_{h}+\overline{P}_{h}\overline{V}_{h+1}\big{)}\Big{|},$

which resembles (48). Thus, repeating the above argument for (49) and applying
(47) recursively, we reach

$\displaystyle\overline{V}_{h}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\leq\frac{\varepsilon}{6}1.$
(51)

Combining (49), (50), and (51) with (40), we arrive at

$\displaystyle
V_{h}^{\star,\widehat{\nu}}-V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\leq\big{(}V_{h}^{\star,\widehat{\nu}}-\overline{V}_{h}^{\widetilde{\mu}^{\star},\widehat{\nu}}\big{)}+\big{(}\overline{V}_{h}-\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}+\big{(}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}-V_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{)}\leq\frac{\varepsilon}{2}1.$

This establishes the first inequality in (36), while the second inequality in
(36) can be validated via the same argument. We have thus completed the proof
of Theorem 1.

##  6 Discussion

The primary contribution of this paper has been to develop a sample-optimal
paradigm that simultaneously overcomes the curse of multiple agents and
optimizes the horizon dependency when solving two-player zero-sum Markov
games. This goal was not accomplished in any of the previous works, regardless
of the sampling mechanism in use. The adoption of the adversarial learning
subroutine helps break the curse of multiple agents compared to the prior
model-based approach (Zhang et al.,, 2020; Liu et al.,, 2021), whereas the
availability of the generative model in conjunction with the variance-aware
bonus design enables sharpened horizon dependency compared to Bai et al.,
(2020); Jin et al., (2021). Our work opens further questions surrounding
sample efficiency in solving Markov games. For instance, how to attain
minimax-optimal sample complexity if we only have access to less idealistic
sampling protocol (e.g., local access models (Li et al., 2021b, ; Yin et al.,,
2022), and online sampling protocols (Azar et al.,, 2017; Jin et al.,, 2018))
as opposed to the flexible generative model? How can we optimize the horizon
dependency when computing (coarse) correlated equilibria in multi-agent
general-sum scenarios (Song et al.,, 2021; Jin et al.,, 2021; Daskalakis et
al.,, 2022) without compromising the dependency on the size of the action
spaces. In addition, our refined regret bound for FTRL (based on variance-type
quantities) only covers the full-information case; it would be of interest to
generalize it to the bandit-feedback setting (where only partial entries of
the loss vectors are observable each time).

## Acknowledgements

Y. Chen is supported in part by the Alfred P. Sloan Research Fellowship, the
Google Research Scholar Award, the AFOSR grant FA9550-22-1-0198, the ONR grant
N00014-22-1-2354, and the NSF grants CCF-2221009, CCF-1907661, IIS-2218713 and
IIS-2218773. Y. Wei is supported in part by the the NSF grants CCF-2106778,
DMS-2147546/2015447 and CAREER award DMS-2143215. Y. Chi are supported in part
by the grants ONR N00014-19-1-2404, NSF CCF-2106778 and DMS-2134080, and
CAREER award ECCS-1818571. Part of this work was done while G. Li, Y. Wei and
Y. Chen were visiting the Simons Institute for the Theory of Computing.

##  Appendix A Proof of Theorem 2

This section is devoted to presenting the proof of Theorem 2. Before embarking
on the analysis, let us introduce a convenient auxiliary iterate

$\displaystyle\pi_{k+1}^{-}=\arg\min_{\pi\in\Delta(\mathcal{A})}\,\bigg{\\{}\langle\pi,L_{k}\rangle+\frac{1}{\widehat{\eta}_{k}}F(\pi)\bigg{\\}},$
(52)

or equivalently,

$\displaystyle\pi_{k+1}^{-}(a)=\frac{\exp\big{(}-\widehat{\eta}_{k}L_{k}(a)\big{)}}{\sum_{a^{\prime}\in\mathcal{A}}\exp\big{(}-\widehat{\eta}_{k}L_{k}(a^{\prime})\big{)}}\qquad\text{for
all }a\in\mathcal{A},$ (53)

which differs from (29) only in the learning rates being used (namely,
$\pi_{k+1}$ uses $\eta_{k+1}$ while $\pi_{k+1}^{-}$ adopts
$\widehat{\eta}_{k}$).

###  A.1 Main steps of the proof

The key steps of the proof lie in justifying the following two claims:

$\displaystyle R_{n}$
$\displaystyle\leq\sum_{k=1}^{n}\alpha_{k}^{n}\big{\langle}\pi_{k}-\pi_{k+1}^{-},\ell_{k}\big{\rangle}+\frac{\log
A}{\eta_{n+1}};$ (54)

and for all $a\in\mathcal{A}$ and all $k\geq 1$,

$\displaystyle\pi_{k+1}^{-}(a)\geq\begin{cases}\big{[}1-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{]}\pi_{k}(a),&\text{if
}\widehat{\eta}_{k}\alpha_{k}\|\ell_{k}\|_{\infty}>\frac{1}{3},\\\
\Big{\\{}1-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}-2\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}\big{(}\ell_{k}\big{)}\Big{\\}}\pi_{k}(a),&\text{if
}\widehat{\eta}_{k}\alpha_{k}\|\ell_{k}\|_{\infty}\leq\frac{1}{3},\end{cases}$
(55)

where for any vector $\ell\in\mathbb{R}^{A}$ we define

$\mathbb{E}_{\pi_{k}}[\ell]\coloneqq\sum_{a\in\mathcal{A}}\pi_{k}(a)\ell(a).$

In words, the first claim (54) allows us to replace the action that appears
best in hindsight (cf. (27)) by the time-varying predictions
$\\{\pi_{k+1}^{-}\\}$ without incurring much cost, whereas the second claim
(55) controls the proximity of $\pi_{k+1}^{-}$ and $\pi_{k}$ in each round.
Let us assume the validity of these two claims for the moment, and return to
prove them shortly.

In view of the upper bound (54), we are in need of controlling
$\big{\langle}\pi_{k}-\pi_{k+1}^{-},\ell_{k}\big{\rangle}$. We divide into two
cases.

  * •

For any $k$ obeying $\widehat{\eta}_{k}\alpha_{k}\|\ell_{k}\|_{\infty}>1/3$,
invoke (55) and the non-negativity of $\ell_{k}$ to reach

$\displaystyle\big{\langle}\pi_{k}-\pi_{k+1}^{-},\ell_{k}\big{\rangle}$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\widehat{\eta}_{k}\alpha_{k}\pi_{k}(a)\big{[}\ell_{k}(a)\big{]}^{2}\leq\sum_{a\in\mathcal{A}}\widehat{\eta}_{k}\alpha_{k}\pi_{k}(a)\big{\|}\ell_{k}\big{\|}_{\infty}^{2}=\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}^{2}.$
(56)

  * •

In contrast, if $\widehat{\eta}_{k}\alpha_{k}\|\ell_{k}\|_{\infty}\leq 1/3$,
then it follows from (55) that

$\displaystyle\big{\langle}\pi_{k}-\pi_{k+1}^{-},\ell_{k}\big{\rangle}$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\bigg{\\{}\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}+2\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}(\ell_{k})\bigg{\\}}\pi_{k}(a)\ell_{k}(a)$
$\displaystyle=\widehat{\eta}_{k}\alpha_{k}\sum_{a\in\mathcal{A}}\pi_{k}(a)\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}\big{[}\ell_{k}\big{]}\big{)}\mathbb{E}_{\pi_{k}}\big{[}\ell_{k}\big{]}+\widehat{\eta}_{k}\alpha_{k}\sum_{a\in\mathcal{A}}\pi_{k}(a)\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}\big{[}\ell_{k}\big{]}\big{)}^{2}$
$\displaystyle\qquad+2\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}(\ell_{k})\sum_{a\in\mathcal{A}}\pi_{k}(a)\ell_{k}(a)$
$\displaystyle=\widehat{\eta}_{k}\alpha_{k}\sum_{a\in\mathcal{A}}\pi_{k}(a)\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}\big{[}\ell_{k}\big{]}\big{)}^{2}+2\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}(\ell_{k})\sum_{a\in\mathcal{A}}\pi_{k}(a)\ell_{k}(a)$
$\displaystyle\leq\widehat{\eta}_{k}\alpha_{k}\mathsf{Var}_{\pi_{k}}\big{(}\ell_{k}\big{)}+2\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}(\ell_{k})\big{\|}\ell_{k}\big{\|}_{\infty},$
(57)

where we invoke the elementary facts that
$\sum_{a}\pi_{k}(a)\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}\big{[}\ell_{k}\big{]}\big{)}=0$
and $\sum_{a}\pi_{k}(a)\ell_{k}(a)\leq\|\ell_{k}\|_{\infty}$.

Putting the above two cases together yields

$\displaystyle\sum_{k=1}^{n}\alpha_{k}^{n}\big{\langle}\pi_{k}-\pi_{k+1}^{-},\ell_{k}\big{\rangle}$
$\displaystyle\quad\leq\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}^{2}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)}+\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}\alpha_{k}\mathsf{Var}_{\pi_{k}}\big{(}\ell_{k}\big{)}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}\leq\frac{1}{3}\bigg{)}$
$\displaystyle\qquad+2\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}\big{(}\ell_{k}\big{)}\big{\|}\ell_{k}\big{\|}_{\infty}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}\leq\frac{1}{3}\bigg{)}$
$\displaystyle\quad\leq\frac{5}{3}\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}\alpha_{k}\mathsf{Var}_{\pi_{k}}\big{(}\ell_{k}\big{)}+3\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\big{\|}\ell_{k}\big{\|}_{\infty}^{3}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)},$
(58)

where the last inequality holds true since

$\displaystyle\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}^{2}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)}$
$\displaystyle\leq
3\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\big{\|}\ell_{k}\big{\|}_{\infty}^{3}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)},$
$\displaystyle\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\big{\|}\ell_{k}\big{\|}_{\infty}\mathsf{Var}_{\pi_{k}}(\ell_{k})\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}\leq\frac{1}{3}\bigg{)}$
$\displaystyle\leq\frac{1}{3}\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}\alpha_{k}\mathsf{Var}_{\pi_{k}}(\ell_{k}).$

Substituting (58) into (54), we can readily arrive at

$\displaystyle R_{n}$
$\displaystyle\leq\frac{5}{3}\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}\alpha_{k}\mathsf{Var}_{\pi_{k}}(\ell_{k})+\frac{\log
A}{\eta_{n+1}}+3\sum_{k=1}^{n}\alpha_{k}^{n}\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\big{\|}\ell_{k}\big{\|}_{\infty}^{3}\operatorname{\mathds{1}}\bigg{(}\widehat{\eta}_{k}\alpha_{k}\big{\|}\ell_{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)}.$

It thus remains to establish the claims (54) and (55), which we shall
accomplish next.

###  A.2 Proof of claim (54)

We claim that it suffices to prove that

$\displaystyle\alpha_{1}^{n}\langle\pi_{2}^{-},\ell_{1}\rangle+\frac{\alpha_{1}^{n}}{\eta_{2}\alpha_{1}}F(\pi_{2})+\sum_{k=2}^{n}\bigg{\\{}\alpha_{k}^{n}\langle\pi_{k+1}^{-},\ell_{k}\rangle+\Big{[}\frac{\alpha_{k}^{n}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n}}{\eta_{k}\alpha_{k-1}}\Big{]}F(\pi_{k+1})\bigg{\\}}$
$\displaystyle\qquad\qquad\leq\min_{\pi\in\Delta(\mathcal{A})}\left\\{\bigg{\langle}\pi,\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}\bigg{\rangle}+\frac{1}{\eta_{n+1}}F(\pi)\right\\}.$
(59)

In fact, suppose that this inequality (59) is valid, then one can easily
obtain

$\displaystyle\alpha_{1}^{n}\langle\pi_{2}^{-},\ell_{1}\rangle+\frac{\alpha_{1}^{n}}{\eta_{2}\alpha_{1}}F(\pi_{2})+\sum_{k=2}^{n}\bigg{\\{}\alpha_{k}^{n}\langle\pi_{k+1}^{-},\ell_{k}\rangle+\Big{[}\frac{\alpha_{k}^{n}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n}}{\eta_{k}\alpha_{k-1}}\Big{]}F(\pi_{k+1})\bigg{\\}}$
$\displaystyle\qquad\leq\min_{\pi\in\Delta(\mathcal{A})}\left\\{\bigg{\langle}\pi,\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}\bigg{\rangle}+\frac{1}{\eta_{n+1}}F(\pi)\right\\}\leq\min_{\pi\in\\{e_{a}\,|\,a\in\mathcal{A}\\}}\left\\{\bigg{\langle}\pi,\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}\bigg{\rangle}+\frac{1}{\eta_{n+1}}F(\pi)\right\\}$
$\displaystyle\qquad=\min_{\pi\in\\{e_{a}\,|\,a\in\mathcal{A}\\}}\bigg{\langle}\pi,\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}\bigg{\rangle}=\min_{a\in\mathcal{A}}\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}(a)$

with $e_{a}$ the $a$-th standard basis vector in $\mathbb{R}^{A}$, where the
last line holds true since the negative entropy obeys $F(e_{a})=0$ for any
$a\in\mathcal{A}$. In turn, this implies that

$\displaystyle R_{n}$
$\displaystyle=\sum_{k=1}^{n}\alpha_{k}^{n}\big{\langle}\pi_{k},\ell_{k}\big{\rangle}-\min_{a\in\mathcal{A}}\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}(a)$
$\displaystyle\leq\sum_{k=1}^{n}\alpha_{k}^{n}\big{\langle}\pi_{k}-\pi_{k+1}^{-},\ell_{k}\big{\rangle}-\sum_{k=2}^{n}\Big{[}\frac{\alpha_{k}^{n}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n}}{\eta_{k}\alpha_{k-1}}\Big{]}F(\pi_{k+1})+\frac{\alpha_{1}^{n}}{\eta_{2}\alpha_{1}}\log
A,$ (60)

where the last inequality invokes the elementary fact $-F(\pi)\leq\log A$ for
any $\pi\in\Delta(\mathcal{A})$. Additionally, under the assumptions that
$\eta_{k+1}(1-\alpha_{k})\leq\eta_{k}$ ($k\geq 1$), we can use the definition
(5) to obtain

$\frac{\alpha_{k}^{n}}{\eta_{k+1}\alpha_{k}}=\frac{\prod_{j=k+1}^{n}(1-\alpha_{j})}{\eta_{k+1}}\geq\frac{\prod_{j=k}^{n}(1-\alpha_{j})}{\eta_{k}}=\frac{\alpha_{k-1}^{n}}{\eta_{k}\alpha_{k-1}},$

for any $k\geq 2$, which together with the basic fact $0\leq-F(\pi)\leq\log A$
yields

$\displaystyle-\sum_{k=2}^{n}\Big{[}\frac{\alpha_{k}^{n}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n}}{\eta_{k}\alpha_{k-1}}\Big{]}F(\pi_{k+1})+\frac{\alpha_{1}^{n}}{\eta_{2}\alpha_{1}}\log
A$
$\displaystyle\leq\sum_{k=2}^{n}\Big{[}\frac{\alpha_{k}^{n}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n}}{\eta_{k}\alpha_{k-1}}\Big{]}\log
A+\frac{\alpha_{1}^{n}}{\eta_{2}\alpha_{1}}\log A$
$\displaystyle=\frac{\alpha_{n}^{n}}{\eta_{n+1}\alpha_{n}}\log A=\frac{\log
A}{\eta_{n+1}}.$ (61)

Substitution into (60) leads to

$\displaystyle R_{n}$
$\displaystyle\leq\sum_{k=1}^{n}\alpha_{k}^{n}\big{\langle}\pi_{k}-\pi_{k+1}^{-},\ell_{k}\big{\rangle}+\frac{\log
A}{\eta_{n+1}}$ (62)

as advertised. As a consequence, everything boils down to establishing (59).

Towards this end, we would like to proceed with an induction argument, with
the induction hypothesis w.r.t. $n$ given by (59). Firstly, the base case with
$n=1$ simplifies to

$\alpha_{1}^{1}\langle\pi_{2}^{-},\ell_{1}\rangle+\frac{1}{\eta_{2}}F(\pi_{2})\leq\min_{\pi\in\Delta(\mathcal{A})}\left\\{\langle\pi,\alpha_{1}^{1}\ell_{1}\rangle+\frac{1}{\eta_{2}}F(\pi)\right\\}$

given that $\alpha_{1}=\alpha_{1}^{1}$; this inequality clearly holds since,
according to (28) and (52),

$\pi_{2}^{-}=\pi_{2}=\arg\min_{\pi\in\Delta(\mathcal{A})}\left\\{\langle\pi,L_{1}\rangle+\frac{1}{\eta_{2}}F(\pi)\right\\}=\arg\min_{\pi\in\Delta(\mathcal{A})}\left\\{\langle\pi,\alpha_{1}\ell_{1}\rangle+\frac{1}{\eta_{2}}F(\pi)\right\\}.$

Secondly, suppose that (59) holds w.r.t. $n$, and we intend to justify it
w.r.t. $n+1$. To do so, we observe that

$\displaystyle\alpha_{1}^{n+1}\langle\pi_{2}^{-},\ell_{1}\rangle+\frac{\alpha_{1}^{n+1}}{\eta_{2}\alpha_{1}}F(\pi_{2})+\sum_{k=2}^{n}\bigg{\\{}\alpha_{k}^{n+1}\langle\pi_{k+1}^{-},\ell_{k}\rangle+\Big{(}\frac{\alpha_{k}^{n+1}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n+1}}{\eta_{k}\alpha_{k-1}}\Big{)}F(\pi_{k+1})\bigg{\\}}+\alpha_{n+1}\langle\pi_{n+2}^{-},\ell_{n+1}\rangle$
$\displaystyle\quad\overset{(\mathrm{i})}{=}(1-\alpha_{n+1})\left\\{\alpha_{1}^{n}\langle\pi_{2}^{-},\ell_{1}\rangle+\frac{\alpha_{1}^{n}}{\eta_{2}\alpha_{1}}F(\pi_{2})+\sum_{k=2}^{n}\bigg{\\{}\alpha_{k}^{n}\langle\pi_{k+1}^{-},\ell_{k}\rangle+\Big{(}\frac{\alpha_{k}^{n}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n}}{\eta_{k}\alpha_{k-1}}\Big{)}F(\pi_{k+1})\bigg{\\}}\right\\}$
$\displaystyle\qquad\qquad+\alpha_{n+1}\langle\pi_{n+2}^{-},\ell_{n+1}\rangle$
$\displaystyle\quad\overset{\mathrm{(ii)}}{\leq}(1-\alpha_{n+1})\left\\{\bigg{\langle}\pi_{n+2}^{-},\sum_{k=1}^{n}\alpha_{k}^{n}\ell_{k}\bigg{\rangle}+\frac{1}{\eta_{n+1}}F(\pi_{n+2}^{-})\right\\}+\alpha_{n+1}\langle\pi_{n+2}^{-},\ell_{n+1}\rangle$
$\displaystyle\quad\overset{\mathrm{(iii)}}{=}\bigg{\langle}\pi_{n+2}^{-},\sum_{k=1}^{n+1}\alpha_{k}^{n+1}\ell_{k}\bigg{\rangle}+\frac{1-\alpha_{n+1}}{\eta_{n+1}}F(\pi_{n+2}^{-})=\min_{\pi\in\Delta(\mathcal{A})}\left\\{\bigg{\langle}\pi,\sum_{k=1}^{n+1}\alpha_{k}^{n+1}\ell_{k}\bigg{\rangle}+\frac{1}{\widehat{\eta}_{n+1}}F(\pi)\right\\}.$
(63)

Here, (i) and (iii) invoke the fact
$\alpha_{k}^{n+1}=(1-\alpha_{n+1})\alpha_{k}^{n}$ and
$\alpha_{n+1}^{n+1}=\alpha_{n+1}$ (according to (5)), (ii) relies on the
induction hypothesis (59) w.r.t. $n$. To finish up, invoke (63) and the
definition (5) to arrive at

$\displaystyle\alpha_{1}^{n+1}\langle\pi_{2}^{-},\ell_{1}\rangle+\frac{\alpha_{1}^{n+1}}{\eta_{2}\alpha_{1}}F(\pi_{2})+\sum_{k=2}^{n+1}\bigg{\\{}\alpha_{k}^{n+1}\langle\pi_{k+1}^{-},\ell_{k}\rangle+\Big{[}\frac{\alpha_{k}^{n+1}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n+1}}{\eta_{k}\alpha_{k-1}}\Big{]}F(\pi_{k+1})\bigg{\\}}$
$\displaystyle=\left\\{\alpha_{1}^{n+1}\langle\pi_{2}^{-},\ell_{1}\rangle+\frac{\alpha_{1}^{n+1}}{\eta_{2}\alpha_{1}}F(\pi_{2})+\sum_{k=2}^{n}\bigg{\\{}\alpha_{k}^{n+1}\langle\pi_{k+1}^{-},\ell_{k}\rangle+\Big{[}\frac{\alpha_{k}^{n+1}}{\eta_{k+1}\alpha_{k}}-\frac{\alpha_{k-1}^{n+1}}{\eta_{k}\alpha_{k-1}}\Big{]}F(\pi_{k+1})\bigg{\\}}+\alpha_{n+1}\langle\pi_{n+2}^{-},\ell_{n+1}\rangle\right\\}$
$\displaystyle\qquad\qquad+\Big{[}\frac{1}{\eta_{n+2}}-\frac{1-\alpha_{n+1}}{\eta_{n+1}}\Big{]}F(\pi_{n+2})$
$\displaystyle\leq\left\\{\bigg{\langle}\pi_{n+2},\sum_{k=1}^{n+1}\alpha_{k}^{n+1}\ell_{k}\bigg{\rangle}+\frac{1-\alpha_{n+1}}{\eta_{n+1}}F(\pi_{n+2})\right\\}+\Big{[}\frac{1}{\eta_{n+2}}-\frac{1-\alpha_{n+1}}{\eta_{n+1}}\Big{]}F(\pi_{n+2})$
$\displaystyle=\bigg{\langle}\pi_{n+2},\sum_{k=1}^{n+1}\alpha_{k}^{n+1}\ell_{k}\bigg{\rangle}+\frac{1}{\eta_{n+2}}F(\pi_{n+2})=\min_{\pi\in\Delta(\mathcal{A})}\left\\{\bigg{\langle}\pi,\sum_{k=1}^{n+1}\alpha_{k}^{n+1}\ell_{k}\bigg{\rangle}+\frac{1}{\eta_{n+2}}F(\pi)\right\\},$

where the inequality above makes use of (63), and the last identity comes from
(28). This justifies the induction hypothesis w.r.t. $n+1$. Applying the
induction argument in turn establishes (59) for all $n$, thereby concluding
the proof.

###  A.3 Proof of claim (55)

We first make the observation that

$\displaystyle\sum_{a}\exp\big{(}-\widehat{\eta}_{k}L_{k}(a)\big{)}$
$\displaystyle=\sum_{a}\exp\big{(}-\eta_{k}L_{k-1}(a)\big{)}\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{)}$
$\displaystyle=\sum_{a}\left\\{\pi_{k}(a)\sum_{a^{\prime}}\exp\big{(}-\eta_{k}L_{k-1}(a^{\prime})\big{)}\right\\}\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{)}$
$\displaystyle=\sum_{a^{\prime}}\exp\big{(}-\eta_{k}L_{k-1}(a^{\prime})\big{)}\sum_{a}\left\\{\pi_{k}(a)\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{)}\right\\},$

where the second equality follows from (29). This in turn allows us to
demonstrate that

$\displaystyle\pi_{k+1}^{-}(a)$
$\displaystyle=\frac{\exp\big{(}-\widehat{\eta}_{k}L_{k}(a)\big{)}}{\sum_{a^{\prime}}\exp\big{(}-\widehat{\eta}_{k}L_{k}(a^{\prime})\big{)}}=\frac{\exp\big{(}-\eta_{k}L_{k-1}(a)\big{)}}{\sum_{a^{\prime}}\exp\big{(}-\eta_{k}L_{k-1}(a^{\prime})\big{)}}\cdot\frac{\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{)}}{\sum_{a^{\prime}}\pi_{k}(a^{\prime})\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a^{\prime})\big{)}}$
$\displaystyle=\pi_{k}(a)\frac{\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{)}}{\sum_{a^{\prime}}\pi_{k}(a^{\prime})\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a^{\prime})\big{)}}\geq\big{[}1-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{]}\pi_{k}(a),$

where the last inequality holds since $\exp(-x)\geq 1-x$ and
$\sum_{a}\pi_{k}(a)\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{)}\leq\sum_{a}\pi_{k}(a)=1$.

Next, suppose that $\widehat{\eta}_{k}\alpha_{k}\|\ell_{k}\|_{\infty}\leq
1/3$. In this case, it is self-evident that
$\widehat{\eta}_{k}\alpha_{k}|\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]|\leq
2/3$ for all $a\in\mathcal{A}$. Recalling that
$\mathbb{E}_{\pi_{k}}[\ell_{k}]=\sum_{a}\pi_{k}(a)\ell_{k}(a)$, one can derive

$\displaystyle\pi_{k+1}^{-}(a)$
$\displaystyle=\pi_{k}(a)\frac{\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a)\big{)}}{\sum_{a^{\prime}}\pi_{k}(a^{\prime})\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\ell_{k}(a^{\prime})\big{)}}=\frac{\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}\big{)}}{\sum_{a^{\prime}}\pi_{k}(a^{\prime})\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a^{\prime})-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}\big{)}}\pi_{k}(a)$
$\displaystyle\geq\frac{1-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}}{\sum_{a^{\prime}}\pi_{k}(a^{\prime})\exp\big{(}-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a^{\prime})-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}\big{)}}\pi_{k}(a)$
$\displaystyle\geq\frac{1-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}}{1+\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}(\ell_{k})}\pi_{k}(a);$
(64)

here, the first inequality arises since $\exp(-x)\geq 1-x$, while the second
inequality can be shown via the elementary inequality $\exp(-x)\leq 1-x+x^{2}$
for any $x\geq-1.5$ and therefore

$\displaystyle\sum_{a}\pi_{k}(a)\exp\Big{(}-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}\Big{)}$
$\displaystyle\qquad\leq\sum_{a}\pi_{k}(a)\bigg{\\{}1-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}+\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}^{2}\bigg{\\}}$
$\displaystyle\qquad=\sum_{a}\pi_{k}(a)\bigg{\\{}1+\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}^{2}\bigg{\\}}$
$\displaystyle\qquad=1+\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}(\ell_{k}).$

Applying the elementary inequality $\frac{1-a}{1+b}\geq(1-a)(1-b)=1-a-b+ab\geq
1-a-2b$ for any $a\in[-1,1]$ and $b>0$, we can continue to lower bound (64) as
follows

$\displaystyle\eqref{eq:pi-kplus1-a-LB1}$
$\displaystyle\geq\bigg{\\{}1-\widehat{\eta}_{k}\alpha_{k}\big{(}\ell_{k}(a)-\mathbb{E}_{\pi_{k}}[\ell_{k}]\big{)}-2\widehat{\eta}_{k}^{2}\alpha_{k}^{2}\mathsf{Var}_{\pi_{k}}\big{(}\ell_{k}\big{)}\bigg{\\}}\pi_{k}(a),$

thereby completing the proof.

##  Appendix B Proofs of auxiliary lemmas and details

###  B.1 Proof of Lemma 3

This section aims to prove Lemma 3, which establishes the inequality
$\overline{V}_{h}\geq\overline{V}_{h}^{\star,\widehat{\nu}}$. In what follows,
we shall proceed with an induction argument. The base case with step $H+1$ is
trivially true, given that

$\overline{V}_{H+1}=\overline{V}_{H+1}^{\star,\widehat{\nu}}=0$

holds for any $\nu$. Next, let us assume that the claim (39) is valid for step
$h+1$, namely,

$\displaystyle\overline{V}_{h+1}\geq\overline{V}_{h+1}^{\star,\widehat{\nu}},$
(65)

and attempt to justify the validity of this result when $h+1$ is replaced with
$h$.

This step is mainly accomplished by applying our refined theory (cf. Theorem
2) for FTRL (see (17)). More precisely, we claim that

$\displaystyle\max_{a}\overline{Q}_{h}^{K}(s,a)$
$\displaystyle\leq\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}$
$\displaystyle\quad+10\sqrt{\frac{c_{\alpha}\log^{3}(KA)}{KH}}\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+2\sqrt{\frac{c_{\alpha}H\log^{3}(KA)}{K}}$
(66)

for any $s\in\mathcal{S}$, whose proof is deferred to Appendix B.1.1. Recall
the construction (18b) of $\overline{V}_{h}$. If $\overline{V}_{h}=H-h+1$,
then the claimed result
$\overline{V}_{h}\geq\overline{V}_{h}^{\star,\widehat{\nu}}$ holds trivially.
Therefore, it suffices to focus on the case where

$\overline{V}_{h}(s)=\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}+\overline{\beta}_{h,V}(s).$

In this case, recalling the definition of
$\overline{V}_{h}^{\star,\widehat{\nu}}(s)$ in (38b) gives

$\displaystyle\overline{V}_{h}^{\star,\widehat{\nu}}(s)$
$\displaystyle=\max_{a}\sum_{k=1}^{K}\alpha_{k}^{K}\big{(}\overline{r}_{h}^{k}(s,a)+\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}^{\star,\widehat{\nu}}\big{)}$
$\displaystyle\leq\max_{a}\sum_{k=1}^{K}\alpha_{k}^{K}\big{(}\overline{r}_{h}^{k}(s,a)+\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}\big{)}=\max_{a}\overline{Q}_{h}^{K}(s,a)$
$\displaystyle\leq\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}+10\sqrt{\frac{c_{\alpha}\log^{3}(KA)}{KH}}\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+2\sqrt{\frac{c_{\alpha}H\log^{3}(KA)}{K}}$
$\displaystyle\leq\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}+\overline{\beta}_{h,V}(s)=\overline{V}_{h}(s)$

holds simultaneously for all $(s,h)\in\mathcal{S}\times[H]$. Here, the second
line follows from the induction hypothesis (65) and the definition of
$\overline{Q}_{h}^{K}$ in (15), the third line invokes the claim (66), whereas
the last line comes from our choice (21) of $\overline{\beta}_{h,V}$ (provided
that $c_{\mathsf{b}}$ is sufficiently large).

####  B.1.1 Proof of claim (66)

Consider any state $s\in\mathcal{S}$. By virtue of the identity
$\overline{Q}_{h}^{k}=\sum_{i=1}^{k}\alpha_{i}^{k}\overline{q}_{h}^{i}$ (see
(15)), the policy update rule (16) (or (17)) for $\mu_{h}^{k}(s)$ can
essentially be viewed as the FTRL algorithm applied to the sequence of loss
vectors

$\ell_{k}=-\overline{q}_{h}^{k}(s,\cdot),\qquad k\geq 1.$

Moreover, recalling the definition (20) of $\eta_{k+1}$ and the definition
(19) of $\alpha_{k}$ (with $c_{\alpha}\geq 24$), we have

$\displaystyle\bigg{(}\frac{\eta_{k}}{\eta_{k+1}}\bigg{)}^{2}$
$\displaystyle=\frac{\alpha_{k}}{\alpha_{k-1}}=\frac{k-2+c_{\alpha}\log
K}{k-1+c_{\alpha}\log K}\geq\frac{k-1}{k-1+c_{\alpha}\log
K}=1-\alpha_{k}>(1-\alpha_{k})^{2}.$ (67)

This property (67) permits us to invoke Theorem 2 to obtain

$\displaystyle\max_{a\in\mathcal{A}}\overline{Q}_{h}^{K}(s,a)-\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}=\max_{a\in\mathcal{A}}\left\\{\sum_{k=1}^{K}\alpha_{k}^{K}\big{\langle}\mu_{h}^{k}(s),\,\ell_{k}\big{\rangle}-\sum_{k=1}^{K}\alpha_{k}^{K}\ell_{k}(a)\right\\}$
$\displaystyle\quad\leq\frac{5}{3}\sum_{k=2}^{K}\alpha_{k}^{K}\frac{\eta_{k}\alpha_{k}}{1-\alpha_{k}}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+\frac{\log
A}{\eta_{K+1}}+\xi_{h}$
$\displaystyle\quad\overset{(\mathrm{i})}{\leq}\frac{5}{3}\sum_{k=2}^{K/2}\frac{\big{(}2c_{\alpha}\big{)}^{1.5}\log^{2}K}{\sqrt{kH}}\alpha_{k}^{K}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}$
$\displaystyle\qquad\quad+\frac{20}{3}\sum_{k=K/2+1}^{K}\alpha_{k}^{K}\sqrt{\frac{c_{\alpha}\log^{2}K}{KH}}\,\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+\frac{\log
A}{\eta_{K+1}}+\xi_{h},$ (68)

where $\xi_{h}$ is defined as

$\displaystyle\xi_{h}$
$\displaystyle\coloneqq\frac{5}{3}\alpha_{1}^{K}\eta_{2}\big{\|}\overline{q}_{h}^{1}\big{\|}_{\infty}^{2}+\left\\{3\sum_{k=2}^{K}\alpha_{k}^{K}\frac{\eta_{k}^{2}\alpha_{k}^{2}}{(1-\alpha_{k})^{2}}\big{\|}\overline{q}_{h}^{k}\big{\|}_{\infty}^{3}\operatorname{\mathds{1}}\bigg{(}\frac{\eta_{k}\alpha_{k}}{1-\alpha_{k}}\big{\|}\overline{q}_{h}^{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)}\right\\}+3\alpha_{1}^{K}\eta_{2}^{2}\big{\|}\overline{q}_{h}^{1}\big{\|}_{\infty}^{3}.$
(69)

Here, to see why (i) holds, we make use of the facts that

$\displaystyle 1-\alpha_{k}$ $\displaystyle=1-\frac{c_{\alpha}\log
K}{k-1+c_{\alpha}\log K}\geq\begin{cases}1-\frac{c_{\alpha}\log
K}{1+c_{\alpha}\log K}=\frac{1}{1+c_{\alpha}\log
K}\geq\frac{1}{2c_{\alpha}\log K},&\text{if }k\geq 2,\\\
1-\frac{c_{\alpha}\log K}{K/2+c_{\alpha}\log K}=\frac{K}{K+2c_{\alpha}\log
K}\geq\frac{1}{2},&\text{if }k\geq K/2+1,\end{cases}$ (70a)
$\displaystyle\eta_{k}\alpha_{k}$ $\displaystyle=\sqrt{\frac{\log
K}{\alpha_{k-1}H}}\cdot\alpha_{k}\leq\sqrt{\frac{\log
K}{\alpha_{k}H}}\cdot\alpha_{k}=\sqrt{\frac{\alpha_{k}\log
K}{H}}\leq\sqrt{\frac{2c_{\alpha}\log^{2}K}{kH}},$ (70b)

where the first line makes use of (32) for large enough $c_{\mathsf{k}}$, and
the second line relies on (33a) in Lemma 1.

To proceed, let us control the terms in (68) separately.

  * •

We start with the first term in (68). The elementary bound
$\big{\|}\overline{q}_{h}^{k}\big{\|}_{\infty}\leq H$ in Lemma 2 taken
together with (33b) in Lemma 1 helps us derive

$\displaystyle\sum_{k=2}^{K/2}\frac{\alpha_{k}^{K}\log^{2}K}{\sqrt{kH}}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}$
$\displaystyle\leq\sum_{k=2}^{K/2}\frac{\log^{2}K}{K^{6}\sqrt{kH}}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}$
$\displaystyle\leq\sum_{k=2}^{K/2}\frac{\log^{2}K}{K^{6}\sqrt{kH}}\big{\|}\overline{q}_{h}^{k}(s,\cdot)\big{\|}_{\infty}^{2}\leq\frac{H^{3/2}\log^{2}K}{K^{6}}\sum_{k=2}^{K/2}\frac{1}{\sqrt{k}}$
$\displaystyle\leq\frac{2H^{3/2}\log^{2}K}{K^{6}}\cdot\sqrt{K/2}\leq\frac{2H^{3/2}\log^{2}K}{K^{5}}.$
(71)

  * •

Turning to the third term in (68), we recall the definition of $\eta_{K+1}$
(cf. (20)) to obtain

$\displaystyle\frac{\log A}{\eta_{K+1}}$ $\displaystyle=\log
A\sqrt{\frac{\alpha_{K}H}{\log K}}\leq\sqrt{\frac{2c_{\alpha}H\log^{2}A}{K}},$
(72)

where the inequality comes from Lemma 1.

  * •

Finally, we move on to the last term in (68). For any $k\geq 2$, one can
combine Lemma 2 with (70) to deduce that

$\displaystyle\frac{\eta_{k}\alpha_{k}}{1-\alpha_{k}}\big{\|}\overline{q}_{h}^{k}\big{\|}_{\infty}$
$\displaystyle\leq\frac{\sqrt{\frac{2c_{\alpha}\log^{2}K}{kH}}}{\frac{1}{2c_{\alpha}\log
K}}\cdot H=\sqrt{\frac{8c_{\alpha}^{3}H\log^{4}K}{k}}.$ (73)

Clearly, the right-hand side of (73) is upper bounded by $1/3$ for all $k$
obeying $k\geq c_{9}H\log^{4}\frac{K}{\delta}$ for some large enough constant
$c_{9}>0$ (see also (32)). Consequently, one can derive

$\displaystyle\xi_{h}$
$\displaystyle=\frac{5}{3}\alpha_{1}^{K}\eta_{2}\big{\|}\overline{q}_{h}^{1}\big{\|}_{\infty}^{2}+\left\\{3\sum_{k=2}^{K}\alpha_{k}^{K}\frac{\eta_{k}^{2}\alpha_{k}^{2}}{(1-\alpha_{k})^{2}}\big{\|}\overline{q}_{h}^{k}\big{\|}_{\infty}^{3}\operatorname{\mathds{1}}\bigg{(}\frac{\eta_{k}\alpha_{k}}{1-\alpha_{k}}\big{\|}\overline{q}_{h}^{k}\big{\|}_{\infty}>\frac{1}{3}\bigg{)}\right\\}+3\alpha_{1}^{K}\eta_{2}^{2}\big{\|}\overline{q}_{h}^{1}\big{\|}_{\infty}^{3}$
$\displaystyle\leq\frac{5}{3K^{6}}\sqrt{\frac{\log
K}{H}}\big{\|}\overline{q}_{h}^{1}\big{\|}_{\infty}^{2}+\frac{\big{(}2c_{\alpha}\log
K\big{)}^{2}}{K^{6}}\left\\{3\sum_{k=2}^{c_{9}H\log^{4}\frac{K}{\delta}}\eta_{k}^{2}\alpha_{k}^{2}\big{\|}\overline{q}_{h}^{k}\big{\|}_{\infty}^{3}\right\\}+\frac{3}{K^{6}}\frac{\log
K}{H}\big{\|}\overline{q}_{h}^{1}\big{\|}_{\infty}^{3}$
$\displaystyle\leq\frac{24c_{\alpha}^{3}\log^{4}K}{K^{6}H}\left\\{\sum_{k=1}^{K}\frac{1}{k}H^{3}\right\\}$
$\displaystyle\leq\frac{24c_{\alpha}^{3}H^{2}\log^{5}K}{K^{6}}\leq\frac{1}{K^{4}},$
(74)

where the second line comes from (70) and the fact that
$K/2>c_{9}H\log^{4}\frac{K}{\delta}$ (as a consequence of (32)), and the third
line holds due to Lemma 2.

Putting the preceding bounds together and substituting them into (68), we
arrive at

$\displaystyle\max_{a}\overline{Q}_{h}^{K}(s,a)-\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}$
$\displaystyle\quad\leq\frac{5(2c_{\alpha})^{1.5}}{3}\cdot\frac{2H^{3/2}\log^{2}K}{K^{5}}+\frac{20}{3}\sqrt{\frac{c_{\alpha}\log^{2}K}{KH}}\sum_{k=K/2+1}^{K}\alpha_{k}^{K}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+\sqrt{\frac{2c_{\alpha}H\log^{2}A}{K}}+\frac{1}{K^{4}}$
$\displaystyle\quad\leq
10\sqrt{\frac{c_{\alpha}\log^{3}(KA)}{KH}}\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+2\sqrt{\frac{c_{\alpha}H\log^{3}(KA)}{K}},$
(75)

where the last line is valid under Condition (32). This completes the proof of
Claim (66).

###  B.2 Proof of Lemma 4

In this section, we present the proof of Lemma 4. To begin with, we introduce
the auxiliary quantities

$\displaystyle\widetilde{q}_{h}^{k}(s,a)\coloneqq\overline{r}_{h}^{k}(s,a)+\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}},\qquad\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$

It is also helpful to introduce an auxiliary random action
$a_{k,s}\in\mathcal{A}$ generated in a way that

$\displaystyle a_{k,s}\sim\mu_{h}^{k}(s),$

which is independent from $\widetilde{q}_{h}^{k}$ conditional on
$\mu_{h}^{k}$. This allows us to define another set of random variables

$\displaystyle\widehat{q}_{h}^{k}(s)\coloneqq\widetilde{q}_{h}^{k}\big{(}s,a_{k,s}),\qquad\forall
s\in\mathcal{S},$ (76)

which plays a central role in our analysis. It is readily seen from the facts
$\overline{V}_{h+1}(s)\leq H-h$ (cf. (18b)) and
$\overline{r}_{h}^{k}(s,a)\in[0,1]$ that

$\displaystyle 0\leq\widehat{q}_{h}^{k}(s),\widetilde{q}_{h}^{k}(s,a)\leq
H-h+1,\qquad\forall(s,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K].$
(77)

Letting $e(i)\in\mathbb{R}^{A}$ denote the $i$-th standard basis vector, we
learn from the law of total variance that

$\displaystyle\mathsf{Var}_{h,k-1}\Big{(}\widehat{q}_{h}^{k}(s)\Big{)}$
$\displaystyle=\mathsf{Var}_{h,k-1}\Big{(}\big{\langle}e(a_{k,s}),\,\widetilde{q}_{h}^{k}(s,\cdot)\big{\rangle}\Big{)}$
$\displaystyle\geq\mathsf{Var}_{h,k-1}\Big{(}\mathbb{E}_{h,k-1}\Big{[}\big{\langle}e(a_{k,s}),\,\widetilde{q}_{h}^{k}(s,\cdot)\big{\rangle}\mid\widetilde{q}_{h}^{k}\Big{]}\Big{)}$
$\displaystyle=\mathsf{Var}_{h,k-1}\Big{(}\big{\langle}\mu_{h}^{k}(s),\,\widetilde{q}_{h}^{k}(s,\cdot)\big{\rangle}\Big{)}.$
(78)

With these preparations in place, we are ready to embark on the proof.

####  B.2.1 Proof of inequalities (42a) and (42b)

Recall the definition of
$\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)$ in (38c) that

$\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)=\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}\limits_{a\sim\mu_{h}^{k}(s)}\Big{[}\overline{r}_{h}^{k}(s,a)+\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\Big{]}=\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\,\widetilde{q}_{h}^{k}(s,\cdot)\Big{\rangle}.$
(79)

It is first observed that

$\displaystyle\sum_{k=1}^{K}\mathbb{E}_{h,k-1}\Big{[}\alpha_{k}^{K}\big{\langle}\mu_{h}^{k}(s),\widetilde{q}_{h}^{k}(s,\cdot)\big{\rangle}\Big{]}$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{(a,b)\sim\mu_{h}^{k}(s)\times\nu_{h}^{k}(s)}\Big{[}r_{h}(s,a,b)+\big{\langle}P_{h}(\cdot\,|\,s,a,b),\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{\rangle}\mid\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}},\mu_{h}^{k},\nu_{h}^{k}\Big{]}$
$\displaystyle=r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)+\big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{\rangle},$
(80)

where the second identity arises from the definitions (41) of
$r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}$ and
$P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}$. It is also seen that

$\displaystyle R_{1}$
$\displaystyle\coloneqq\max_{k}\Big{|}\alpha_{k}^{K}\big{\langle}\mu_{h}^{k}(s),\widetilde{q}_{h}^{k}(s,\cdot)\big{\rangle}\Big{|}\leq\Big{\\{}\max_{k}\alpha_{k}^{K}\Big{\\}}\Big{\\{}\max_{k}\big{\|}\mu_{h}^{k}(s)\big{\|}_{1}\big{\|}\widetilde{q}_{h}^{k}\big{\|}_{\infty}\Big{\\}}\leq\frac{2c_{\alpha}H\log
K}{K},$

where the first line invokes Lemma 1, (77) and the fact
$\|\mu_{h}^{k}(s)\|_{1}=1$. Another observation is that

$\displaystyle
W_{1}=\sum_{k=1}^{K}\big{(}\alpha_{k}^{K}\big{)}^{2}\mathsf{Var}_{h,k-1}\Big{(}\big{\langle}\mu_{h}^{k}(s),\widetilde{q}_{h}^{k}(s,\cdot)\big{\rangle}\Big{)}$
$\displaystyle\leq\left\\{\max_{k}\alpha_{k}^{K}\right\\}\left\\{\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{h,k-1}\Big{(}\big{\langle}\mu_{h}^{k}(s),\widetilde{q}_{h}^{k}(s,\cdot)\big{\rangle}\Big{)}\right\\}$
$\displaystyle\leq\frac{2c_{\alpha}\log
K}{K}\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{h,k-1}\Big{(}\widehat{q}_{h}^{k}(s)\Big{)},$
(81)

where the second line makes use of Lemma 1 and the inequality (78). With the
definitions (79) and (80) in mind, invoking Freedman’s inequality (i.e.,
Theorem 4) with $\kappa_{1}=\sqrt{\frac{K\log\frac{K}{\delta}}{H}}$ then leads
to

$\displaystyle\bigg{|}\overline{V}_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)-\Big{(}r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)+\big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\,\overline{V}_{h+1}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}\big{\rangle}\Big{)}\bigg{|}$
$\displaystyle\quad\quad=\bigg{|}\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\widetilde{q}_{h}^{k}(s,\cdot)\Big{\rangle}-\sum_{k=1}^{K}\mathbb{E}_{h,k-1}\Big{[}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(s),\widetilde{q}_{h}^{k}(s,\cdot)\Big{\rangle}\Big{]}\bigg{|}$
$\displaystyle\quad\quad\leq\kappa_{1}W_{1}+\left(\frac{2}{\kappa_{1}}+5R_{1}\right)\log\frac{3K}{\delta}$
$\displaystyle\quad\quad\leq
2c_{\alpha}\sqrt{\frac{\log^{3}\frac{K}{\delta}}{KH}}\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{h,k-1}\Big{(}\widehat{q}_{h}^{k}(s)\Big{)}+\left(2\sqrt{\frac{H}{K\log\frac{K}{\delta}}}+\frac{10c_{\alpha}H\log
K}{K}\right)\log\frac{3K}{\delta}$ $\displaystyle\quad\quad\leq
2c_{\alpha}\sqrt{\frac{\log^{3}\frac{K}{\delta}}{KH}}\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{h,k-1}\Big{(}\widehat{q}_{h}^{k}(s)\Big{)}+4\sqrt{\frac{H\log\frac{3K}{\delta}}{K}}$
(82)

with probability at least $1-\delta$, where the last relation holds true under
Condition (32).

To continue, we note the first term in (82) can be bounded by Cauchy-Schwarz
as follows:

$\displaystyle\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{h,k-1}\Big{(}\widehat{q}_{h}^{k}(s)\Big{)}$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\left[\big{(}\widehat{q}_{h}^{k}(s)\big{)}^{2}\right]-\sum_{k=1}^{K}\alpha_{k}^{K}\Big{(}\mathbb{E}_{h,k-1}\left[\widehat{q}_{h}^{k}(s)\right]\Big{)}^{2}$
$\displaystyle\leq\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\left[\big{(}\widehat{q}_{h}^{k}(s)\big{)}^{2}\right]-\bigg{(}\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\left[\widehat{q}_{h}^{k}(s)\right]\bigg{)}^{2}.$
(83)

Further, we make note of two additional facts:

  * •

The weighted mean of $\widehat{q}_{h}^{k}(s)$ obeys

$\displaystyle\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\left[\widehat{q}_{h}^{k}(s)\right]$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{(a,b)\sim\mu_{h}^{k}(s)\times\nu_{h}^{k}(s)}\big{[}r_{h}(s,a,b)\big{]}+\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}_{(a,b)\sim\mu_{h}^{k}(s)\times\nu_{h}^{k}(s)}\Big{[}\big{\langle}P_{h}(\cdot\,|\,s,a,b),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{]}$
$\displaystyle=r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)+\big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\geq\big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle};$
(84)

  * •

Regarding the square of $\widehat{q}_{h}^{k}(s)$, one has (see (76))

$\displaystyle\big{(}\widehat{q}_{h}^{k}(s)\big{)}^{2}$
$\displaystyle=\Big{(}\overline{r}_{h}^{k}(s,a_{k,s})+\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a_{k,s}),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{)}^{2}$
$\displaystyle=\Big{(}\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a_{k,s}),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{)}^{2}+\Big{(}\overline{r}_{h}^{k}(s,a_{k,s})\Big{)}^{2}+2\overline{r}_{h}^{k}(s,a_{k,s})\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a_{k,s}),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}$
$\displaystyle\leq\Big{(}\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a_{k,s}),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{)}^{2}+3H$
$\displaystyle\leq\Big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a_{k,s}),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\circ\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\Big{\rangle}+3H,$

where we have used the fact that
$\|\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\|_{\infty}\leq H$
and $\|\overline{r}_{h}^{k}\|_{\infty}\leq 1$; consequently,

$\displaystyle\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\Big{[}\big{(}\widehat{q}_{h}^{k}(s)\big{)}^{2}\Big{]}$
$\displaystyle\leq\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\Big{[}\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a_{k,s}),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\circ\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{]}+3H$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\sum_{a}\mu_{k}^{h}(a\,|\,s)\mathbb{E}_{h,k-1}\Big{[}\big{\langle}\overline{P}_{h}^{k}(\cdot\,|\,s,a),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\circ\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{]}+3H$
$\displaystyle=\Big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\circ\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\Big{\rangle}+3H.$
(85)

Taking (84) and (85) together with (83) yields

$\displaystyle\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{h,k-1}\Big{(}\widehat{q}_{h}^{k}(s)\Big{)}$
$\displaystyle\leq\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\left[\big{(}\widehat{q}_{h}^{k}(s)\big{)}^{2}\right]-\bigg{(}\sum_{k=1}^{K}\alpha_{k}^{K}\mathbb{E}_{h,k-1}\left[\widehat{q}_{h}^{k}(s)\right]\bigg{)}^{2}$
$\displaystyle\leq\Big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\circ\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\Big{\rangle}-\Big{(}\big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{)}^{2}+3H.$

To finish up, substituting these into (82) and making use of the assumption
(32) give

$\displaystyle\bigg{|}\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h}(s)-\Big{(}r_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s)+\big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\,\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{)}\bigg{|}$
$\displaystyle\qquad\leq
2c_{\alpha}\sqrt{\frac{\log^{3}\frac{K}{\delta}}{KH}}\left[\Big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\circ\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\Big{\rangle}-\Big{(}\big{\langle}P_{h}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}(s,\cdot),\overline{V}^{\widehat{\mu}\,\cdot\,\widehat{\nu}}_{h+1}\big{\rangle}\Big{)}^{2}\right]+\left(6c_{\alpha}+4\right)\sqrt{\frac{H\log^{3}\frac{K}{\delta}}{K}}$

for any $s\in\mathcal{S}$, thus concluding the proof of the first claim (42a)
of Lemma 4.

The second claim (42b) of Lemma 4 can be established using exactly the same
argument, and hence we omit the proof here for the sake of brevity.

####  B.2.2 Proof of inequality (42c)

We then turn to the last advertised inequality (42c). Given that
$\overline{r}_{h}(s)+\overline{P}_{h}(s,\cdot)\overline{V}_{h+1}\in[0,H-h+1]$
for all $s\in\mathcal{S}$, we can recall the definition (18b) of
$\overline{V}_{h}$ to obtain

$\Big{|}\overline{V}_{h}(s)-\big{(}\overline{r}_{h}(s)+\overline{P}_{h}(s,\cdot)\overline{V}_{h+1}\big{)}\Big{|}\leq\bigg{|}\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(\cdot\,|\,s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}+\overline{\beta}_{h,V}(s)-\big{(}\overline{r}_{h}(s)+\overline{P}_{h}(s,\cdot)\overline{V}_{h+1}\big{)}\bigg{|}$
(86)

for all $s\in\mathcal{S}$. The remaining analysis is dedicated to bounding the
right-hand side of (86).

Let us begin with the following identity:

$\displaystyle\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\langle}\mu_{h}^{k}(\cdot\,|\,s),\,\overline{q}_{h}^{k}(s,\cdot)\Big{\rangle}+\overline{\beta}_{h,V}(s)$
$\displaystyle=\sum_{k=1}^{K}\alpha_{k}^{K}\mathop{\mathbb{E}}\limits_{a\sim\mu_{h}^{k}(s)}\Big{[}\overline{r}_{h}^{k}(s,a)+\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}\Big{]}+\overline{\beta}_{h,V}(s)$
$\displaystyle=\overline{r}_{h}(s)+\big{\langle}\overline{P}_{h}(s,\cdot),\overline{V}_{h+1}\big{\rangle}+\overline{\beta}_{h,V}(s),$
(87)

where we recall the definitions of $\overline{r}_{h}\in\mathbb{R}^{S}$ and
$\overline{P}_{h}\in\mathbb{R}^{S\times S}$ in (41). The key step boils down
to bounding the bonus term defined in (21), towards which first we claim that

$\displaystyle\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{\mu_{h}^{k}(s)}\big{(}\overline{q}_{h}^{k}(s,\cdot)\big{)}$
$\displaystyle\leq
2+2\Big{[}\overline{P}_{h}(s,\cdot)\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\big{(}\overline{P}_{h}(s,\cdot)\overline{V}_{h+1}\big{)}^{2}\Big{]}$
(88)

holds for all $s\in\mathcal{S}$. Assuming the validity of this claim, we can
then demonstrate that

$\displaystyle\overline{\beta}_{h,V}(s)$
$\displaystyle=c_{\mathsf{b}}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\sum_{k=1}^{K}\alpha_{k}^{K}\Big{\\{}\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\overline{q}_{h}^{k}(s,\cdot)\Big{)}+H\Big{\\}}$
$\displaystyle\leq
2c_{\mathsf{b}}\sqrt{\frac{\log^{3}\frac{KS(A+B)}{\delta}}{KH}}\Big{\\{}\overline{P}_{h}(s,\cdot)\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\big{(}\overline{P}_{h}(s,\cdot)\overline{V}_{h+1}\big{)}^{2}+H\Big{\\}},$
(89)

where we have used the identity $\sum_{k=1}^{K}\alpha_{k}^{K}=1$. Hence, we
can readily establish the desired result (42c) by combining (89) with (87) and
(86), provided that $c_{3}>0$ is sufficiently large.

It remains to justify the claim (88). Towards this end, we make the
observation that

$\displaystyle\mathsf{Var}_{\mu_{h}^{k}(s)}\big{(}\overline{q}_{h}^{k}(s,\cdot)\big{)}$
$\displaystyle\leq
2\mathsf{Var}_{\mu_{h}^{k}(s)}\big{(}\overline{r}_{h}^{k}(s,\cdot)\big{)}+2\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\sum_{s^{\prime}}\overline{P}_{h}^{k}(s^{\prime}\mid
s,\cdot)\overline{V}_{h+1}(s^{\prime})\Big{)}$ $\displaystyle\leq
2+2\left[\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(s,a)\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\bigg{(}\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(s,a)\overline{V}_{h+1}\bigg{)}^{2}\right],$

which results from $\|\overline{r}_{h}^{k}\|_{\infty}\leq 1$ and the following
relation:

$\displaystyle\mathsf{Var}_{\mu_{h}^{k}(s)}\Big{(}\sum_{s^{\prime}}\overline{P}_{h}^{k}(s^{\prime}\mid
s,\cdot)\overline{V}_{h+1}(s^{\prime})\Big{)}$
$\displaystyle=\sum_{a}\mu_{h}^{k}(a\,|\,s)\Big{(}\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}\Big{)}^{2}-\bigg{(}\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}\bigg{)}^{2}$
$\displaystyle\leq\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(\cdot\,|\,s,a)\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\bigg{(}\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(\cdot\,|\,s,a)\overline{V}_{h+1}\bigg{)}^{2}.$

This taken together with the fact $\sum_{k=1}^{K}\alpha_{k}^{K}=1$ and
Jensen’s inequality yields

$\displaystyle\sum_{k=1}^{K}\alpha_{k}^{K}\mathsf{Var}_{\mu_{h}^{k}(s)}\big{(}\overline{q}_{h}^{k}(s,\cdot)\big{)}$
$\displaystyle\leq\sum_{k=1}^{K}\alpha_{k}^{K}\left\\{2+2\left[\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(s,a)\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\bigg{(}\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(s,a)\overline{V}_{h+1}\bigg{)}^{2}\right]\right\\}$
$\displaystyle\leq
2+2\overline{P}_{h}(s,\cdot)\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-2\bigg{(}\sum_{k=1}^{K}\alpha_{k}^{K}\sum_{a}\mu_{h}^{k}(a\,|\,s)\overline{P}_{h}^{k}(s,a)\overline{V}_{h+1}\bigg{)}^{2}$
$\displaystyle=2+2\Big{[}\overline{P}_{h}(s,\cdot)\big{(}\overline{V}_{h+1}\circ\overline{V}_{h+1}\big{)}-\big{(}\overline{P}_{h}(s,\cdot)\overline{V}_{h+1}\big{)}^{2}\Big{]}$

as claimed.

###  B.3 Minimax lower bound

In this section, we formalize the minimax lower bound claimed in (26).

######  Theorem 3 (Minimax lower bound).

Consider any $0<\varepsilon\leq c_{1}H$ for some small enough constant
$c_{1}>0$. Then one can construct a collection of Markov games
$\\{\mathcal{MG}_{\theta}\mid\theta\in\Theta\\}$ such that

$\displaystyle\inf_{\widehat{\mu},\widehat{\nu}}\max_{\theta\in\Theta}\mathbb{P}^{\mathcal{MG}_{\theta}}\left\\{\mathsf{NE}\text{-}\mathsf{gap}\big{(}\widehat{\mu},\widehat{\nu}\big{)}>\varepsilon\right\\}\geq\frac{1}{4},$
(90)

provided that the total sample size obeys

$\displaystyle N\leq\frac{c_{2}H^{4}S(A+B)}{\varepsilon^{2}}$ (91)

for some sufficiently small constant $c_{2}>0$. Here, the infimum is over all
policy estimator $(\widehat{\mu},\widehat{\nu})$, and
$\mathbb{P}^{\mathcal{MG}_{\theta}}$ denotes the probability when the Markov
game is $\mathcal{MG}_{\theta}$.

###### Proof.

Suppose without loss of generality that $A\geq B$. Let us begin by considering
the special scenario with $B=1$; in this case, computing the Nash-equilibrium
reduces to finding the optimal policy of a single-agent MDP with $S$ states
and $A$ actions. It is well-known that for any given accuracy level
$\varepsilon\in(0,H]$, there exists a non-stationary MDP with $S$ states and
$A$ actions such that no algorithm can learn an $\varepsilon$-optimal policy
with ${o}\big{(}\frac{H^{4}SA}{\varepsilon^{2}}\big{)}$ samples (Azar et al.,,
2013; Li et al.,, 2022). More precisely, for any given $0<\varepsilon\leq
c_{1}H$ for some small enough constant $c_{1}>0$, one can construct a
collection of MDPs $\\{\mathcal{M}_{\theta}\mid\theta\in\Theta\\}$ such that

$\displaystyle\inf_{\widehat{\mu}}\max_{\theta\in\Theta}\mathbb{P}^{\mathcal{M}_{\theta}}\left\\{\max_{s}\big{(}V_{1}^{\star}(s)-V_{1}^{\widehat{\mu}}(s)\big{)}>\varepsilon\right\\}\geq\frac{1}{4},$
(92)

with the proviso that the total sample size

$\displaystyle N\leq\frac{c_{2}H^{4}SA}{\varepsilon^{2}}$ (93)

for some small enough constant $c_{2}>0$. Here, the infimum is over all policy
estimate $\widehat{\mu}$ in this single-agent scenario, and
$\mathbb{P}^{\mathcal{M}_{\theta}}$ denotes the probability when the MDP is
${\mathcal{M}}_{\theta}$.

Next, let us construct a collection of Markov games by augmenting each of the
single-agent MDPs $\mathcal{M}_{\theta}$ with $B$ completely identical actions
for the min-player; that is, to construct $\mathcal{MG}_{\theta}$, we take its
reward function and probability transition kernel to be

$\displaystyle
r_{h}^{\mathcal{MG}_{\theta}}(s,a,b)=r_{h}^{{\mathcal{M}}_{\theta}}(s,a)\qquad\text{and}\qquad
P_{h}^{\mathcal{MG}_{\theta}}(\cdot\,|\,s,a,b)=P_{h}^{{\mathcal{M}}_{\theta}}(\cdot\,|\,s,a)$
(94)

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$.
Evidently, finding the Nash-equilibrium of $\mathcal{MG}_{\theta}$ is
equivalent to computing the optimal policy of ${\mathcal{M}}_{\theta}$, given
the non-distinguishability of the actions of the min-player in
$\mathcal{MG}_{\theta}$. This in turn immediately establishes the advertised
lower bound. ∎

###  B.4 Freedman’s inequality

In this section, we record the Freedman inequality for martingales (Freedman,,
1975) with slight modification, which is a crucial concentration bound for our
analysis.

######  Theorem 4.

Suppose that $Y_{n}=\sum_{k=1}^{n}X_{k}\in\mathbb{R}$, where $\\{X_{k}\\}$ is
a real-valued scalar sequence obeying

$\left|X_{k}\right|\leq
R\qquad\text{and}\qquad\mathbb{E}\left[X_{k}\mid\left\\{X_{j}\right\\}_{j:j<k}\right]=0\quad\quad\quad\text{for
all }k\geq 1$

for some quantity $R>0$. Define

$W_{n}\coloneqq\sum_{k=1}^{n}\mathbb{E}_{k-1}\left[X_{k}^{2}\right],$

where $\mathbb{E}_{k-1}$ stands for the expectation conditional on
$\left\\{X_{j}\right\\}_{j:j<k}$. Consider any arbitrary quantity $\kappa>0$.
With probability at least $1-\delta$, one has

$\displaystyle\left|Y_{n}\right|$
$\displaystyle\leq\sqrt{8W_{n}\log\frac{3n}{\delta}}+5R\log\frac{3n}{\delta}\leq\kappa
W_{n}+\Big{(}\frac{2}{\kappa}+5R\Big{)}\log\frac{3n}{\delta}.$ (95)

###### Proof.

Suppose that $W_{n}\leq\sigma^{2}$ holds deterministically for some quantity
$\sigma^{2}$. As has been demonstrated in Li et al., 2021a (, Theorem 5), with
probability at least $1-\delta$ we have

$\displaystyle\left|Y_{n}\right|$
$\displaystyle\leq\sqrt{8\max\bigg{\\{}W_{n},\frac{\sigma^{2}}{2^{K}}\bigg{\\}}\log\frac{2K}{\delta}}+\frac{4}{3}R\log\frac{2K}{\delta}$
(96)

for any positive integer $K\geq 1$. Recognizing the trivial bound $W_{n}\leq
nR^{2}$, one can take $\sigma^{2}=nR^{2}$ and $K=\log_{2}n$ to obtain

$\displaystyle\left|Y_{n}\right|$
$\displaystyle\leq\sqrt{8\max\big{\\{}W_{n},R^{2}\big{\\}}\log\frac{4\log_{2}n}{\delta}}+\frac{4}{3}R\log\frac{4\log_{2}n}{\delta}$
$\displaystyle\leq\sqrt{8W_{n}\log\frac{3n}{\delta}}+\sqrt{8R^{2}\log\frac{3n}{\delta}}+\frac{4}{3}R\log\frac{3n}{\delta}$
$\displaystyle\leq\sqrt{8W_{n}\log\frac{3n}{\delta}}+5R\log\frac{3n}{\delta},$

where we have used $4\log_{2}n\leq 3n$ for any integer $n\geq 1$. This
establishes the first inequality in (95). The second inequality in (95) is
then a direct consequence of the elementary inequality $2ab\leq a^{2}+b^{2}$.
∎

## References

  * 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.