problemProblem

# Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret
Learning in Markov Games

Wenhao Zhan
Princeton University. Email<EMAIL_ADDRESS>Jason D. Lee Princeton
University. Email<EMAIL_ADDRESS>Zhuoran Yang
Yale University. Email<EMAIL_ADDRESS>
(August 27, 2024)

###### Abstract

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

##  1 Introduction

Multi-agent reinforcement learning (MARL) studies how each agent learns to
maximize its cumulative rewards by interacting with the environment as well as
other agents, where the state transitions and rewards are affected by the
actions of all the agents. Equipped with powerful function approximators such
as deep neural networks (LeCun et al.,, 2015), MARL has achieved significant
empirical success in various domains including the game of Go (Silver et al.,,
2016), StarCraft (Vinyals et al.,, 2019), DOTA2 (Berner et al.,, 2019), Atari
(Mnih et al.,, 2013), multi-agent robotics systems (Brambilla et al.,, 2013)
and autonomous driving(Shalev-Shwartz et al.,, 2016). Compared with the
centralized setting where a central controller collects the information of all
agents and coordinates their behaviors, decentralized algorithms (Gupta et
al.,, 2017; Rashid et al.,, 2018) where each agent autonomously chooses its
action based on its own local information are often more desirable in MARL
applications. In specific, decentralized methods (1) are easier to implement
and enjoy better scalability, (2) are more robust to possible adversaries, and
(3) require less communication overhead (Hernandez-Leal et al.,, 2018, 2019;
Canese et al.,, 2021; Zhang et al., 2021a, ; Gronauer and Diepold,, 2022).

In this work, we aim to design a provably efficient decentralized
reinforcement learning (RL) algorithm in the online setting with function
approximation. In the sequel, for the ease of presentation, we refer to the
controllable agent as the player and regard the rest of the agents as a meta-
agent, called the opponent, which specifies its policies arbitrarily. Our goal
is to maximize the cumulative rewards of the player in the face of a possibly
adversarial opponent, in the online setting where the policies of the player
and opponent can be based on adaptively gathered local information.

From a theoretical perspective, arguably the most distinctive challenge of the
decentralized setting is nonstationarity. That is, from the perspective of any
agent, the states transitions are affected by the policies of other agents in
an unpredictable and potentially adversarial way and are thus nonstationary.
This is in stark contrast to the centralized setting which can be regarded as
a standard RL problem for the central controller which decides the actions for
all the players. Furthermore, in the online setting, as the environment is
unknown, to achieve sample efficiency, the player needs to strike a balance
between exploration and exploitation in the context of function approximation
and in the presence of an adversarial opponent. The dual challenges of
nonstationarity and efficient exploration are thus intertwined, making it
challenging to develop provably efficient decentralized MARL algorithms.

Consequently, there seem only limited theoretical understanding of the
decentralized MARL setting with a possibly adversarial opponent. Most of the
existing algorithms (Brafman and Tennenholtz,, 2002; Wei et al.,, 2017; Tian
et al.,, 2021; Jin et al., 2021c, ; Huang et al.,, 2021) can only compete
against the Nash value of the Markov game when faced with an arbitrary
opponent. This is a much weaker baseline compared with the results in classic
matrix games (Fudenberg and Tirole,, 1991; Anderson,, 2008) where the player
is required to compete against the best fixed policy in hindsight. Meanwhile,
Liu et al., (2022) seems the only work we know that can achieve no-regret
learning in MARL against the best hindsight policy, which focuses on the
policy revealing setting where the player observes the policies played by the
opponent in previous episodes. Moreover, the algorithm and theory in this work
are limited to tabular cases and fail to deal with large or even continuous
state and action space. To this end, we would like to answer the following
question:

Can we design a decentralized MARL algorithm that provably achieves no-regret
against the best fixed policy in hindsight in the context of function
approximation?

In this work, we provide a positive answer to the above question under the
policy revealing setting with general function approximation. In specific, we
propose an actor-critic-type algorithm (Konda and Tsitsiklis,, 1999) called
DORIS, which maintains a distribution over the policy space, named
hyperpolicy, for decision-making. To combat the nonstationarity, DORIS updates
the hyperpolicy via mirror descent (or equivalently, Hedge (Freund and
Schapire,, 1997)). Furthermore, to encourage exploration, the descent
directions of mirror descent are obtained by solving optimistic variants of
policy evaluation subproblems with general function approximation, which only
involve the local information of the player. Under standard regularity
assumptions on the underlying function classes, we prove that DORIS achieves a
sublinear regret in the presence of an adversarial opponent. In addition, when
the agents all adopt DORIS independently, we prove that their average policy
constitutes an approximate coarse correlated equilibrium. At the core of our
analysis is a new complexity measure of function classes that is tailored to
the decentralized MARL setting. Furthermore, to demonstrate the power of
DORIS, we adapt it for solving constrained Markov decision process (CMDP) and
vector-valued Markov decision process (VMDP), which can both be formulated as
a zero-sum Markov game with a fictitious opponent.

#### Our Contributions.

Our contributions are four-fold. First, we propose a new decentralized policy
optimization algorithm, DORIS, that provably achieves no-regret in the context
of general function approximation. As a result, when all agents adopt DORIS,
their average policy converges to a CCE of the Markov game. Secondly, we
propose a new complexity measure named Bellman Evaluation Eluder dimension,
which generalizes Bellman Eluder dimension (Jin et al., 2021a, ) for single-
agent MDP to decentralized learning in Markov games, which might be of
independent interest. Third, we modify DORIS for solving CMDP with general
function approximation, which is shown to achieve sublinear regret and
constraint violation. Finally, we extend DORIS to solving the approchability
task (Miryoosefi et al.,, 2019) in vector-valued Markov decision process
(VMDP) and attain a near-optimal solution. To our best knowledge, DORIS seems
the first provably efficient decentralized algorithm for achieving no-regret
in MARL with general function approximation.

###  1.1 Notations

In this paper we let $[n]=\\{1,\cdots,n\\}$ for any integer $n$. We denote the
set of probability distributions over any set $\mathcal{S}$ by
$\Delta_{\mathcal{S}}$ or $\Delta(\mathcal{S})$. We also let $\|\cdot\|$
denote the $\ell_{2}$-norm by default.

###  1.2 Related works

#### Decentralized learning with an adversarial opponent.

There have been a few works studying decentralized policy learning in the
presence of a possibly adversarial opponent. Brafman and Tennenholtz, (2002)
proposes R-max and is able to attain an average game value close to the Nash
value in tabular MGs. More recently, Wei et al., (2017); Tian et al., (2021)
improve the regret bounds in tabular cases and Jin et al., 2021c ; Huang et
al., (2021) extend the results to general function approximation setting.
However, these works only compete against the Nash value of the game and are
unable to exploit the opponent. A more related paper is Liu et al., (2022),
which develops a provably efficient algorithm that achieves a sublinear regret
against the best fixed policy in hindsight. But there results are only limited
to the tabular case. Our work extends the results Liu et al., (2022) to the
setting with general function approximation, which requires novel technical
analysis.

#### Finding equilibria in self-play Markov games.

Our work is closely related to the recent literature on finding equilibria in
Markov games via reinforcement learning. Most of the existing works focus on
two-player zero-sum games and consider centralized algorithms with unknown
model dynamics. For example, Wei et al., (2017); Bai and Jin, (2020) utilize
optimism to tackle the exploration-expoitation tradeoff and find Nash
equilibria in tabular cases, and Xie et al., (2020); Jin et al., 2021c ; Huang
et al., (2021) extend the results to linear and general function approximation
setting. Furthermore, under the decentralized setting with well-explored data,
Daskalakis et al., (2020); Zhang et al., 2021b ; Sayin et al., (2021); Wei et
al., 2021a ; Leonardos et al., (2021); Ding et al., (2022) utilize independent
policy gradient algorithms to deal with potential Markov games and two-player
zero-sum games. Meanwhile, under the online setting, Bai et al., (2020); Mao
et al., (2021); Jin et al., 2021b  design algorithms named V-learning, which
are able to find CCE in multi-agent general-sum games. However, there results
are only limited to the tabular case.

#### Constrained Markov decision process.

Efroni et al., (2020); Ding et al., (2021) propose a series of primal-dual
algorithms for CMDPs which achieve $\sqrt{K}$ bound on regrets and constraint
violations in tabular and linear approximation cases. Liu et al., (2021)
reduces the constraint violation to $\widetilde{\mathcal{O}}(1)$ by adding
slackness to the algorithm and achieves zero violation when a strictly safe
policy is known; Wei et al., 2021b  further avoids such requirement with the
price of worsened regrets. Nevertheless, these improvements are only discussed
in the tabular case.

#### Approchability for vector-valued Markov decision process.

Miryoosefi et al., (2019) first introduces the approachability task for VMDPs
but does not provide an algorithm with polynomial sample complexity. Then Yu
et al., (2021) proposes a couple of primal-dual algorithms to solve this task
and achieves a $\widetilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity in
the tabular case. More recently, Miryoosefi and Jin, (2021) utilizes reward-
free reinforcement learning to tackle the problem and studies both the tabular
and linear approximation cases, achieving roughly the same sample complexity
as Yu et al., (2021).

##  2 Preliminaries

###  2.1 General-Sum Markov Games

Let us consider an $n$-agent general-sum Markov game (MG)
$\mathcal{M}_{\text{MG}}=(\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{n},\\{P_{h}\\}_{h=1}^{H},\break\\{r_{h,i}\\}_{h=1,i=1}^{H,n},H)$,
where $\mathcal{S}$ is the state space, $\mathcal{A}_{i}$ is the action space
of $i$-th agent,
$P_{h}:\mathcal{S}\times\prod_{i=1}^{n}\mathcal{A}_{i}\to\Delta(\mathcal{S})$
is the transition function at $h$-th step,
$r_{h,i}:\mathcal{S}\times\prod_{i=1}^{n}\mathcal{A}_{i}\to\mathbb{R}_{+}$ is
the reward function of $i$-th agent at $h$-th step and $H$ is the length of
each episode.

We assume each episode starts at a fixed start state $s_{1}$ and terminates at
$s_{H+1}$. At step $h\in[H]$, each agent $i$ observes the state $s_{h}$ and
takes action $a_{h,i}$ simultaneously. After that, agent $i$ receives its own
reward $r_{h,i}(s_{h},\bm{a}_{h})$ where
$\bm{a}_{h}:=(a_{h,1},\cdots,a_{h,n})$ is the joint action and the environment
transits to a new state $s_{h+1}\sim P_{h}(\cdot|s_{h},\bm{a}_{h})$.

#### Policy.

A policy of the $i$-th agent
$\mu_{i}=\\{\mu_{h,i}:\mathcal{S}\to\Delta_{\mathcal{A}_{i}}\\}_{h\in[H]}$
specifies the action selection probability of agent $i$ in each state at each
step. In the following discussion we will drop the $h$ in $\mu_{h,i}$ when it
is clear from the context. We use $\pi$ to represent the joint policy of all
agents and $\mu_{-i}$ to denote the joint policy of all agents other than $i$.
Further, we assume each agent $i$ chooses its policy from a policy class
$\Pi_{i}$. Similarly, let $\Pi_{-i}:=\prod_{j\neq i}\Pi_{j}$ denote the
product of all agents’ policy classes other than the $i$-th agent.

#### Value functions and Bellman operators.

Given any joint policy $\pi$, the $i$-th agent’s value function
$V^{\pi}_{h,i}:\mathcal{S}\to\mathbb{R}$ and action-value (or Q) function
$Q^{\pi}_{h,i}:\mathcal{S}\times\prod_{i=1}^{n}\mathcal{A}_{i}\to\mathbb{R}$
characterize its expected cumulative rewards given a state or a state-action
pair, as defined below:

$\displaystyle
V^{\pi}_{h,i}(s):=\mathbb{E}_{\pi}\bigg{[}\sum_{t=h}^{H}r_{t,i}(s_{t},\bm{a}_{t})\bigg{|}s_{h}=s\bigg{]},Q^{\pi}_{h,i}(s,\bm{a}):=\mathbb{E}_{\pi}\bigg{[}\sum_{t=h}^{H}r_{t,i}(s_{t},\bm{a}_{t})\bigg{|}s_{h}=s,\bm{a}_{h}=\bm{a}\bigg{]},$

where the expectation is w.r.t. to the distribution of the trajectory induced
by executing the joint policy $\pi$ in $\mathcal{M}_{\text{MG}}$. Here we
suppose the action-value function is bounded:

$\displaystyle Q^{\pi}_{h,i}(s,\bm{a})\leq V_{\max},\forall s,\bm{a},h,i,\pi.$

Notice that when the reward function is bounded in $[0,1]$, $V_{\max}=H$
naturally.

###  2.2 Decentralized Policy Learning

In this paper we consider the decentralized learning setting (Jin et al.,
2021c, ; Huang et al.,, 2021; Liu et al.,, 2022) where only one agent is under
our control, which we call player, and the other agents can be adversarial.
Without loss of generality, assume that we can only control agent 1 and view
the other agents as a meta opponent. To simplify writing, we use
$a_{h},\mathcal{A},r_{h},\mu,\Pi,V^{\pi}_{h},Q^{\pi}_{h}$ to denote
$a_{h,1},\mathcal{A}_{1},r_{h,1},\mu_{1},\Pi_{1},V^{\pi}_{h,1},Q^{\pi}_{h,1}$
respectively. We also use $b_{h},\mathcal{B},\nu,\Pi^{\prime}$ to represent
the joint action, the joint action space, the joint policy and the joint
policy class of all the agents other than agent 1.

By decentralized learning we mean that during the episode, the player can only
observe its own rewards, actions and some information of the opponent
specified by the protocol, i.e.,
$\\{s_{h}^{t},a_{h}^{t},\mathcal{J}_{h}^{t},r_{h}^{t}\\}_{h=1}^{H}$ where
$\\{\mathcal{J}_{h}\\}_{h=1}^{H}$ is the information revealed by the opponent
in each episode, which we will specify later. Then at the beginning of $t$-th
episode, the player chooses a policy $\mu^{t}$ from its policy class $\Pi$
based only on its local information collected from previous episodes, without
any coordination from a centralized controller. Meanwhile, the opponent
selects $\nu^{t}$ from $\Pi^{\prime}$ secretly and probably adversely.

The learning objective is to minimize the regret of the player by comparing
its performance against the best fixed policy in hindsight as standard in
online learning literature (Anderson,, 2008; Hazan et al.,, 2016):

######  Definition 1 (Regret).

Suppose $(\mu^{t},\nu^{t})$ are the policies played by the player and the
opponent in $t$-th episode. Then the regret for $K$ episodes is defined as

$\displaystyle\text{Regret}(K)=\max_{\mu\in\Pi}\sum_{t=1}^{K}V^{\mu\times\nu^{t}}_{1}(s_{1})-\sum_{t=1}^{K}V^{\mu^{t}\times\nu^{t}}_{1}(s_{1}),$
(1)

where $\mu\times\nu$ denotes the joint policy where the player and the
opponent play $\mu$ and $\nu$ independently.

Achieving low regrets defined in (1) indicates that, in the presence of an
opponent playing adaptive $\\{\nu^{t}\\}_{t=1}^{T}$, the algorithm
approximately is as good as the best fixed policy in $\Pi$ in the hindsight.

#### Relation between Definition 1 and equilibria.

An inspiration for our definition of regrets comes from the tight connection
between low regrets and equilibria in the matrix game (Fudenberg and Tirole,,
1991; Blum and Monsour,, 2007; Daskalakis et al.,, 2011). By viewing each
policy in the policy class as a pure strategy in the matrix game, we can
generalize the notion of equilibria in matrix games to Markov games naturally.
In particular, a correlated mixed strategy profile $\overline{\pi}$ can be
defined as a mixture of the joint policy of all agents, i.e.,
$\overline{\pi}\in\Delta(\prod_{i\in[n]}\Pi_{i})$. Suppose the marginal
distribution of $\overline{\pi}$ over the policy of agent $i$ is
$\overline{\mu}_{i}$, then we can see that $\overline{\mu}_{i}$ is a mixture
of the policies in $\Pi_{i}$. For a correlated profile, the agents might not
play their mixed policies $\overline{\mu}_{i}$ independently, which means that
$\overline{\pi}$ might not be the product of $\overline{\mu}_{i}$. A coarse
correlated equilibrium (CCE) is simply a correlated profile that all the
agents have no incentive to deviate from by playing a different independent
policy:

######  Definition 2 (Coarse correlated equilibrium (CCE) for $n$-player MG).

A correlated strategy profile $\overline{\pi}$ is an $\epsilon$-approximate
coarse correlated equilibrium if we have for all $i\in[n]$

$\displaystyle
V_{1,i}^{\overline{\pi}}(s_{1})\geq\max_{\mu^{\prime}\in\Pi_{i}}V_{1,i}^{\mu^{\prime}\times\overline{\mu}_{-i}}(s_{1})-\epsilon,$
(2)

where $\overline{\mu}_{-i}$ is the marginal distribution of $\overline{\pi}$
over the joint policy of all agents other than $i$.

######  Remark 1.

Our definition of correlated strategy profile and CCEs is slightly different
from Mao et al., (2021). This is because we are considering with policy
classes while Mao et al., (2021) does not. In fact, our definition is more
strict in the sense that a correlated profile satisfying our definition must
also satisfy theirs.

Specially, if a CCE $\overline{\pi}$ satisfies
$\overline{\pi}=\prod_{i\in[n]}\overline{\mu}_{i}$, then we call
$\overline{\pi}$ a Nash Equilibrium (NE). We will show in Section 4.3 that if
a decentralized algorithm can achieve low regrets under Definition 1, we will
be able to find an approximate CCE by running the algorithm independently for
each agent and return the resulting mixture policy.

###  2.3 Function Approximation

To deal with the potentially large or even infinite state and action space, we
consider learning with general value function approximation in this paper
(Jiang et al.,, 2017; Jin et al., 2021a, ). We assume the player is given a
function class $\mathcal{F}=\mathcal{F}_{1}\times\cdots\times\mathcal{F}_{H}$
($\mathcal{F}_{h}\subseteq(\mathcal{S}\times\mathcal{A}\times\mathcal{B}\to[0,V_{\max}])$)
to approximate the action-value functions. Since there is no reward in state
$s_{H+1}$, we let $f_{H+1}(s,a,b)=0$ for all
$s\in\mathcal{S},a\in\mathcal{A},b\in\mathcal{B},f\in\mathcal{F}$.

To measure the size of $\mathcal{F}$, we use $|\mathcal{F}|$ to denote its
cardinality when $\mathcal{F}$ is finite. For infinite function classes, we
use $\epsilon$-covering number to measure its size, which is defined as
follows.

######  Definition 3 ($\epsilon$-covering number).

The $\epsilon$-covering number of $\mathcal{F}$, denoted by
$\mathcal{N}_{\mathcal{F}}(\epsilon)$, is the minimum integer $n$ such that
there exists a subset $\mathcal{F}^{\prime}\subset\mathcal{F}$ with
$|\mathcal{F}^{\prime}|=n$ and for any $f\in\mathcal{F}$ there exists
$f^{\prime}\in\mathcal{F}^{\prime}$ such that
$\max_{h\in[H]}\|f_{h}-f^{\prime}_{h}\|_{\infty}\leq\epsilon$.

In addition to the size, we also need to impose some complexity assumption on
the structure of the function class to achieve small generalization error.
Here we introduce one of such structure complexity measures called
Distributional Eluder (DE) dimension (Jin et al., 2021a, ), which we will
utilize in our subsequent analysis. First let us define independence between
distributions as follows.

######  Definition 4 ($\epsilon$-independence between distributions).

Let $\mathcal{W}$ be a function class defined on $\mathcal{X}$, and
$\rho,\rho_{1},\cdots,\rho_{n}$ be probability measure over $\mathcal{X}$. We
say $\rho$ is $\epsilon$-independent of $\\{\rho_{1},\cdots,\rho_{n}\\}$ with
respect to $\mathcal{W}$ if there exists $w\in\mathcal{W}$ such that
$\sqrt{\sum_{i=1}^{n}(\mathbb{E}_{\rho_{i}}[w])^{2}}\leq\epsilon$ but
$|\mathbb{E}_{\rho}[w]|>\epsilon$.

From the definition we can see that a probability distribution $\rho$ is
independent from $\\{\rho_{1},\cdots,\rho_{n}\\}$ if there exists a
discriminator function in $\mathcal{W}$ such that the function values are
small at $\\{\rho_{1},\cdots,\rho_{n}\\}$ while large at $\rho$. Then DE
dimension is simply the length of the longest sequence of independent
probability distributions that the function class can discriminate. We lay out
the definition of the DE dimension as follows.

######  Definition 5 (Distributional Eluder (DE) dimension).

Let $\mathcal{W}$ be a function class defined on $\mathcal{X}$, and
$\mathcal{Q}$ be a family of probability measures over $\mathcal{X}$. The
distributional Eluder dimension
$\mathrm{dim}_{\mathrm{DE}}(\mathcal{W},\mathcal{Q},\epsilon)$ is the length
of the longest sequence $\\{\rho_{1},\cdots,\rho_{n}\\}\subset\mathcal{Q}$
such that there exists $\epsilon^{\prime}\geq\epsilon$ where $\rho_{i}$ is
$\epsilon^{\prime}$-independent of $\\{\rho_{1},\cdots,\rho_{i-1}\\}$ for all
$i\in[n]$.

Eluder dimension, another commonly-used complexity measure proposed by Russo
and Van Roy, (2013), is a special case of DE dimension when the distributions
concentrate on a single point. That is, if we choose
$\mathcal{Q}=\\{\delta_{x}(\cdot)|x\in\mathcal{X}\\}$ where
$\delta_{x}(\cdot)$ is the dirac measure centered at $x$, then the Eluder
dimension can be formulated as

$\displaystyle\mathrm{dim}_{\mathrm{E}}(\mathcal{W},\epsilon)=\mathrm{dim}_{\mathrm{DE}}(\mathcal{W}-\mathcal{W},\mathcal{Q},\epsilon),$

where $\mathcal{W}-\mathcal{W}=\\{w_{1}-w_{2}:w_{1},w_{2}\in\mathcal{W}\\}$.
Many function classes in MDPs are known to have low Eluder dimension,
including linear MDPs (Jin et al.,, 2020), generalized linear complete models
(Wang et al.,, 2019) and kernel MDPs (Jin et al., 2021a, ).

We also assume the existence of an auxiliary function class
$\mathcal{G}=\mathcal{G}_{1}\times\cdots\times\mathcal{G}_{H}$
($\mathcal{G}_{h}\subseteq(\mathcal{S}\times\mathcal{A}\times\mathcal{B}\to[0,V_{\max}])$)
to capture the results of applying Bellman operators on $\mathcal{F}$ as in
Jin et al., 2021a ; Jin et al., 2021c . When $\mathcal{F}$ satisfies
completeness (Assumption 3), we can simply choose $\mathcal{G}=\mathcal{F}$.

##  3 Algorithm: DORIS

#### Policy revealing setting.

Recall that in decentralized policy learning setting, the player is also able
to observe some information of the opponent, denoted by $\mathcal{J}_{h}$,
aside from its own actions and rewards. There have been works studying the
case where $\mathcal{J}_{h}=\emptyset$ (Tian et al.,, 2021) and
$\mathcal{J}_{h}=b_{h}$ (Jin et al., 2021c, ; Huang et al.,, 2021) in two-
player zero-sum games. However, their benchmark is the Nash value of the
Markov game, i.e., $V^{\mu^{*}\times\nu^{*}}_{1}(s_{1})$ where
$\mu^{*}\times\nu^{*}$ is an NE, which is strictly weaker than our benchmark
$\max_{\mu\in\Pi}\sum_{t=1}^{K}V^{\mu\times\nu^{t}}_{1}(s_{1})$ in two-player
zero-sum games. In fact, Liu et al., (2022) have showed achieving a low regret
under Definition 1 is exponentially hard in tabular cases when the opponent’s
policy is not revealed. Therefore in this paper we let
$\mathcal{J}_{h}=\\{b_{h},\nu_{h}\\}$ just like Liu et al., (2022) and call
this information structure policy revealing setting.

That said, even in policy revealing setting, the challenge of nonstationarity
still exists because the opponent’s policy can be adversarial and only gets
revealed after the player plays a policy. Thus from the perspective of the
player, the transition kernel
$P^{\nu}_{h}(\cdot|s,a):=\mathbb{E}_{b\sim\nu_{h}(s)}P_{h}(\cdot|s,a,b)$ still
changes in an unpredictable way across episodes. In addition, the problem of
how to balance exploration and exploitation with general function
approximation also remains due to the unknown transition probability. In this
section we propose DORIS, an algorithm that is capable of handling all these
challenges and achieving a $\sqrt{K}$ regret upper bound in the policy
revealing setting.

####  DORIS.

Intuitively, our algorithm is an actor-critic / mirror descent (Hedge)
algorithm where each policy $\mu$ in $\Pi$ is regarded as an expert and the
performance of each expert at episode $t$ is given by the value function of
$V^{\nu\times\nu^{t}}_{1}(s_{1})$. We call it Decentralized Optimistic
hypeRpolicy mIrror deScent (DORIS). DORIS possesses three important features,
whose details are shown in Algorithm 1:

  * •

Hyperpolicy and Hedge: Motivated from the adversarial bandit literature
(Anderson,, 2008; Hazan et al.,, 2016; Lattimore and Szepesvári,, 2020), DORIS
maintains a distribution $p$ over the policies in $\Pi$, which we call
hyperpolicy, to combat the nonstaionarity. The hyperpolicy is updated using
Hedge, with the reward of each policy $\mu$ being an estimation of the value
function $V^{\mu\times\nu^{t}}_{1}(s_{1})$. This is equivalent to running
mirror ascent algorithm over the policy space $\Pi$ with the gradient being
$V^{\mu\times\nu^{t}}_{1}(s_{1})$.

  * •

Optimism: However, we do not have access to the exact value function since the
transition probability is unknown, which forces us to deal with the
exploration-exploitation tradeoff. Here we utilize the Optimism in the Face of
Uncertainty principle (Azar et al.,, 2017; Jin et al.,, 2020; Jin et al.,
2021a, ; Jin et al., 2021c, ; Huang et al.,, 2021) and choose our estimation
$\overline{V}^{t}(\mu)$ to be optimistic with respect to the true value
$V^{\mu\times\nu^{t}}_{1}(s_{1})$. In this way DORIS will prefer policies with
more uncertainty and thus encourage exploration in the Markov game.

  * •

Optimistic policy evaluation with general function approximation: Finally we
need to design an efficient method to obtain such optimistic estimation
$\overline{V}^{t}(\mu)$ with general function approximation. Here we propose
OptLSPE to accomplish this task. In short, OptLSPE constructs a confidence set
for the target action-value function $Q^{\mu\times\nu}$ based on the player’s
local information and chooses an optimistic estimation from the confidence
set, as shown in Algorithm 2. The construction of the confidence set utilizes
the fact that $Q^{\mu\times\nu}_{h}$ satisfies the Bellman equation
(Puterman,, 1994):

$\displaystyle
Q^{\mu\times\nu}_{h}(s,a,b)=(\mathcal{T}^{\mu,\nu}_{h}Q^{\mu\times\nu}_{h+1})(s,a,b):=r_{h}(s,a,b)+\mathbb{E}_{s^{\prime}\sim
P_{h}(\cdot|s,a,b)}[Q^{\mu\times\nu}_{h+1}(s^{\prime},\mu,\nu)],$

where
$Q^{\mu\times\nu}_{h+1}(s^{\prime},\mu,\nu)=\mathbb{E}_{a^{\prime}\sim\mu(\cdot|s^{\prime}),b^{\prime}\sim\nu(\cdot|s^{\prime})}[Q^{\mu\times\nu}_{h+1}(s^{\prime},a^{\prime},b^{\prime})]$.
We call $\mathcal{T}^{\mu,\nu}_{h}$ the Bellman operator induced by
$\mu\times\nu$ at $h$-th step. Then the construction rule of
$\mathcal{B}_{\mathcal{D}}(\mu,\nu)$ is based on least-squared policy
evaluation with slackness $\beta$ as below:

$\displaystyle\mathcal{B}_{\mathcal{D}}(\mu,\nu)\leftarrow\Big{\\{}f\in\mathcal{F}:\mathcal{L}_{\mathcal{D}}(f_{h},f_{h+1},\mu,\nu)\leq\inf_{g\in\mathcal{G}}\mathcal{L}_{\mathcal{D}}(g_{h},f_{h+1},\mu,\nu)+\beta,\forall
h\in[H]\Big{\\}},$ (3)

where $\mathcal{L}_{\mathcal{D}}$ is the empirical Bellman residuals on
$\mathcal{D}$:

$\displaystyle\mathcal{L}_{\mathcal{D}}(\xi_{h},\zeta_{h+1},\mu,\nu)=\sum_{(s_{h},a_{h},b_{h},r_{h},s_{h+1})\in\mathcal{D}}[\xi_{h}(s_{h},a_{h},b_{h})-r_{h}-\zeta_{h+1}(s_{h+1},\mu,\nu)]^{2}.$

Algorithm 1 DORIS

Input: learning rate $\eta$, confidence parameter $\beta$.

Initialize $p^{1}\in\Delta_{\Pi}$ to be uniform over $\Pi$.

for $t=1,\cdots,K$ do

Collect samples:

The player samples $\mu^{t}$ from $p^{t}$.

Run $\pi^{t}=\mu^{t}\times\nu^{t}$ and collect
$\mathcal{D}_{t}=\\{s^{t}_{1},a^{t}_{1},b^{t}_{1},r^{t}_{1},\cdots,s^{t}_{H+1}\\}$.

Update policy distribution:

The opponent reveals its policy $\nu^{t}$ to the player.

$\overline{V}^{t}(\mu)\leftarrow\textbf{{OptLSPE}}(\mu,\nu^{t},\mathcal{D}_{1:t-1},\mathcal{F},\mathcal{G},\beta),\quad\forall\mu\in\Pi$.

$p^{t+1}(\mu)\propto
p^{t}(\mu)\cdot\exp(\eta\cdot\overline{V}^{t}(\mu)),\quad\forall\mu\in\Pi$.

end for

Algorithm 2
$\textbf{{OptLSPE}}(\mu,\nu,\mathcal{D},\mathcal{F},\mathcal{G},\beta)$

Construct $\mathcal{B}_{\mathcal{D}}(\mu,\nu)$ based on $\mathcal{D}$ via (3).

Select
$\bar{V}\leftarrow\max_{f\in\mathcal{B}_{\mathcal{D}}(\mu,\nu)}f(s_{1},\mu,\nu)$.

return $\bar{V}$.

#### Decentralized Algorithm.

Here we want to highlight that DORIS is a decentralized algorithm because the
player can run DORIS based only on its local information, i.e.,
$\\{s_{h},a_{h},\mathcal{J}_{h},r_{h}\\}$, and we do not make any assumptions
on the behavior of the opponent.

###  3.1 DORIS in Self-Play Setting

Apart from decentralized learning setting with a possibly adversarial
opponent, we are also interested in the self-play setting where we can control
all the agents and need to find an equilibrium for the $n$-agent general-sum
Markov game. Inspired by the existing relationships between no-regret learning
and CCE in matrix games (Fudenberg and Tirole,, 1991; Blum and Monsour,, 2007;
Daskalakis et al.,, 2011), a natural idea is to simply let all agents run
DORIS independently. To achieve this, we assume each agent $i$ is given a
value function class
$\mathcal{F}_{i}=\mathcal{F}_{1,i}\times\cdots\times\mathcal{F}_{H,i}$ and an
auxiliary function class
$\mathcal{G}_{i}=\mathcal{G}_{1,i}\times\cdots\times\mathcal{G}_{H,i}$ as in
DORIS, and run DORIS by viewing the other agents as its opponent. Suppose the
policies played by agent $i$ during $K$ episodes are
$\\{\mu^{t}_{i}\\}_{t=1}^{K}$, then we output the final joint policy as a
uniform mixture of them:

$\displaystyle\widehat{\pi}\sim\mathrm{Unif}\Big{(}\Big{\\{}{\textstyle\prod_{i\in[n]}}\leavevmode\nobreak\
\mu^{1}_{i},\cdots,{\textstyle\prod_{i\in[n]}}\leavevmode\nobreak\
\mu^{K}_{i}\Big{\\}}\Big{)}.$

See Algorithm 3 for more details.

Algorithm 3 DORIS in self-play setting

Input: learning rate $\\{\eta_{i}\\}_{i=1}^{n}$, confidence parameter
$\\{\beta_{i}\\}_{i=1}^{n}$.

Initialize $p^{1}_{i}\in\Delta_{|\Pi_{i}|}$ to be uniform over $\Pi_{i}$ for
all $i\in[n]$.

for $t=1,\cdots,K$ do

Collect samples:

Agent $i$ samples $\mu^{t}_{i}$ from $p^{t}_{i}$.

Run $\mu^{t}=\prod_{i=1}^{n}\mu^{t}_{i}$ and collect
$\mathcal{D}_{t,i}=\\{s^{t}_{1},\bm{a}^{t}_{1},r^{t}_{1,i},\cdots,s^{t}_{H+1}\\}$
for each agent $i$.

Update policy distribution:

All agents reveal their policies $\mu^{t}_{i}$.

$\overline{V}^{t}_{i}(\mu_{i})\leftarrow\textbf{{OptLSPE}}(\mu_{i},\mu^{t}_{-i},\mathcal{D}_{1:t-1,i},\mathcal{F}_{i},\mathcal{G}_{i},\beta_{i}),\quad\forall\mu_{i}\in\Pi_{i},i\in[n]$.

$p^{t+1}_{i}(\mu_{i})\propto
p^{t}_{i}(\mu_{i})\cdot\exp(\eta_{i}\cdot\overline{V}^{t}_{i}(\mu_{i})),\quad\forall\mu_{i}\in\Pi_{i},i\in[n]$.

end for

Output:
$\widehat{\pi}\sim\text{Unif}(\\{\prod_{i\in[n]}\mu^{1}_{i},\cdots,\prod_{i\in[n]}\mu^{K}_{i}\\})$.

######  Remark 2.

Algorithm 3 is also a decentralized algorithm since every agent runs their
local algorithm independently without coordination. The only step that
requires centralized control is the output process where all the agents need
to share the same iteration index, which is also required in the existing
decentralized algorithms (Mao et al.,, 2021; Jin et al., 2021b, ).

##  4 Theoretical Guarantees

In this section we analyze the theoretical performance of DORIS in
decentralized policy learning and self-play setting. We first introduce a new
complexity measure for function classes and policy classes, called Bellman
Evaluation Eluder (BEE) dimension, and then illustrate the regret and sample
complexity bounds based on this new measure.

###  4.1 Bellman Evaluation Eluder Dimension

Motivated from Bellman Eluder (BE) dimension in classic MDPs and its variants
in MGs (Jin et al., 2021a, ; Jin et al., 2021c, ; Huang et al.,, 2021), we
propose a new measure specifically tailored to the decentralized policy
learning setting, called Bellman Evaluation Eluder (BEE) dimension. First, for
any function class $\mathcal{F}$, we define
$(\mathcal{I}-\mathcal{T}^{\Pi,\Pi^{\prime}}_{h})\mathcal{F}$ to be the
Bellman residuals induced by the policies in $\Pi$ and $\Pi^{\prime}$:

$\displaystyle(\mathcal{I}-\mathcal{T}^{\Pi,\Pi^{\prime}}_{h})\mathcal{F}:=\\{f_{h}-\mathcal{T}^{\mu,\nu}_{h}f_{h+1}:f\in\mathcal{F},\mu\in\Pi,\nu\in\Pi^{\prime}\\}.$

Then Bellman Evaluation Eluder (BEE) dimension is the DE dimension of the
Bellman residuals induced by the policy class $\Pi$ and $\Pi^{\prime}$ on
function class $\mathcal{F}$:

######  Definition 6.

The $\epsilon$-Bellman Evaluation Eluder dimension of function class
$\mathcal{F}$ on distribution family $\mathcal{Q}$ with respect to the policy
class $\Pi\times\Pi^{\prime}$ is defined as follows:

$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime},\mathcal{Q}):=\max_{h\in[H]}\mathrm{dim}_{\mathrm{DE}}((\mathcal{I}-\mathcal{T}^{\Pi,\Pi^{\prime}}_{h})\mathcal{F},\mathcal{Q}_{h},\epsilon).$

BEE dimension is able to capture the generalization error of evaluating value
function $V^{\mu\times\nu}$ where $\mu\in\Pi,\nu\in\Pi^{\prime}$, which is one
of the most essential tasks in decentralized policy space optimization as
shown in DORIS. Similar to Jin et al., 2021a ; Jin et al., 2021c , we mainly
consider two distribution families for $\mathcal{Q}$:

  * •

$\mathcal{Q}^{1}=\\{\mathcal{Q}^{1}_{h}\\}_{h\in[H]}$: the collection of all
probability measures over $\mathcal{S}\times\mathcal{A}\times\mathcal{B}$ at
each step when executing $(\mu,\nu)\in\Pi\times\Pi^{\prime}$.

  * •

$\mathcal{Q}^{2}=\\{\mathcal{Q}^{2}_{h}\\}_{h\in[H]}$: the collection of all
probability measures that put measure 1 on a single state-action pair
$(s,a,b)$ at each step.

We also use
$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})$ to denote
$\min\\{\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime},\mathcal{Q}^{1}),\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\break\Pi,\Pi^{\prime},\mathcal{Q}^{2})\\}$
for simplicity in the following discussion.

#### Relation with Eluder dimension.

To illustrate the generality of BEE dimension, we show that all function
classes with low Eluder dimension also have low BEE dimension, as long as
completeness (Assumption 3) is satisfied. More specifically, we have the
following proposition and its proof is deferred to Appendix A:

######  Proposition 1.

Assume $\mathcal{F}$ satisfies completeness, i.e.,
$\mathcal{T}^{\mu,\nu}_{h}f_{h+1}\in\mathcal{F}_{h},\forall
f\in\mathcal{F},\mu\in\Pi,\nu\in\Pi^{\prime},h\in[H]$. Then for all
$\epsilon>0$, we have

$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})\leq\max_{h\in[H]}\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon).$
(4)

Inequality (4) shows that BEE dimension is always upper bounded by Eluder
dimension when completeness is satisfied. With Proposition 1, Appendix C
validates that kernel Markov games (including tabular Markov games and linear
Markov games) and generalized linear complete models all have small Bellman
Evaluation Eluder Dimension. Furthermore, in this case the upper bound of BEE
dimension does not depend on $\Pi$ and $\Pi^{\prime}$, which is a desirable
property when $\Pi$ and $\Pi^{\prime}$ is large.

###  4.2 Decentralized Policy Learning Regret

Next we present the regret analysis for DORIS in decentralized policy learning
setting. Notice that when $\Pi$ is infinite, the lower bound in Liu et al.,
(2022) indicates that the regret will scale with $|\Pi^{\prime}|$ in tabular
cases, suggesting the hardness of efficient learning for infinite policy class
$\Pi$. Therefore we focus on finite $\Pi$ here:

######  Assumption 1 (Finite player’s policy class).

We assume $\Pi$ is finite.

We consider two cases, the oblivious opponent (i.e., the opponent determines
$\\{\nu^{t}\\}_{t=1}^{K}$ secretly before the game starts) and the adaptive
opponent (i.e., the opponent determines its policy adaptively as the game goes
on) separately. The difference between these two cases lies in the policy
evaluation step of DORIS. The policy $\nu^{t}$ of an oblivious opponent does
not depend on the collected dataset $\mathcal{D}_{1:t-1}$ and thus
$V^{\mu,\nu^{t}}$ is easier to evaluate. However, for an adaptive opponent,
$\nu^{t}$ will be chosen adaptively based on $\mathcal{D}_{1:t-1}$ and we need
to introduce an additional union bound over $\Pi^{\prime}$ when analyzing the
evaluation error of $V^{\mu,\nu^{t}}$.

#### Oblivious opponent.

To attain accurate value function estimation and thus low regrets, we first
need to introduce two standard assumptions, realizability and generalized
completeness, on $\mathcal{F}$ and $\mathcal{G}$ (Jin et al., 2021a, ; Jin et
al., 2021c, ). Here realizability refers to that all the ground-truth action
value functions belong to $\mathcal{F}$ and generalized completeness means
that $\mathcal{G}$ contains all the results of applying Bellman operator to
the functions in $\mathcal{F}$.

######  Assumption 2 (Realizability and generalized completeness).

Assume that for any
$h\in[H],\mu\in\Pi,\nu\in\\{\nu^{1},\cdots,\nu^{K}\\},f_{h+1}\in\mathcal{F}_{h+1}$,
we have
$Q^{\mu\times\nu}_{h}\in\mathcal{F}_{h},\mathcal{T}_{h}^{\mu,\nu}f_{h+1}\in\mathcal{G}_{h}$.

######  Remark 3.

Some existing works (Xie et al.,, 2021; Huang et al.,, 2021) assume the
completeness assumption, which can also be generalized to our setting:

######  Assumption 3.

Assume that for any
$h\in[H],\mu\in\Pi,\nu\in\Pi^{\prime},f_{h+1}\in\mathcal{F}_{h+1}$, we have
$\mathcal{T}_{h}^{\mu,\nu}f_{h+1}\in\mathcal{F}_{h}$.

We want to clarify that Assumption 3 is stronger than generalized completeness
in Assumption 2 since if Assumption 3 holds, we can simply let
$\mathcal{G}=\mathcal{F}$ to satisfy generalized completeness.

Appendix B shows that realizability and generalized completeness are satisfied
in many examples including tabular MGs, linear MGs and kernel MGs with proper
function classes. With the above assumptions, we have Theorem 1 to
characterize the regret of DORIS when the opponent is oblivious, whose proof
sketch is deferred to Section 7. To simplify writing, we use the following
notations in Theorem 1:

$\displaystyle
d_{\mathrm{BEE}}:=\mathrm{dim}_{\mathrm{BEE}}\big{(}\mathcal{F},\sqrt{1/K},\Pi,\Pi^{\prime}\big{)},\quad\mathcal{N}_{\mathrm{cov}}:=\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(V_{\max}/K)KH.$

######  Theorem 1 (Regret of Oblivious Adversary).

Under Assumption 1,2, there exists an absolute constant $c$ such that for any
$\delta\in(0,1]$, $K\in\mathbb{N}$, if we choose
$\beta=cV_{\max}^{2}\log(\mathcal{N}_{\mathrm{cov}}|\Pi|/\delta)$ and
$\eta=\sqrt{\log|\Pi|/(KV_{\max}^{2})}$ in DORIS, then with probability at
least $1-\delta$, we have:

$\displaystyle\text{Regret}(K)\leq\mathcal{O}\big{(}HV_{\max}\sqrt{Kd_{\mathrm{BEE}}\log\left(\mathcal{N}_{\mathrm{cov}}|\Pi|/\delta\right)}\big{)}.$
(5)

The $\sqrt{K}$ bound on the regret in Theorem 1 is consistent with the rate in
tabular case (Liu et al.,, 2022) and suggests that the uniform mixture of the
output policies $\\{\mu^{t}\\}_{t=1}^{K}$ is an $\epsilon$-approximate best
policy in hindsight when $K=\widetilde{\mathcal{O}}(1/\epsilon^{2})$. The
complexity of the problem affects the regret bound through the covering number
and the BEE dimension, implying that BEE dimension indeed captures the essence
of this problem. Further, in oblivious setting, the regret bound in (5) does
not depend on $\Pi^{\prime}$ directly (the upper bound of the BEE dimension is
also independent of $\Pi^{\prime}$ in some special cases as shown in
Proposition 1) and thus Theorem 1 can still hold when $\Pi^{\prime}$ is
infinite, as long as Assumptions 2 is satisfied.

#### Adaptive Opponent.

In the adaptive setting, the analysis in the oblivious setting can still work
but requires slight modifications. We first need to modify Assumption 2 to
hold for all $\nu\in\Pi^{\prime}$ since $\nu^{t}$ is no longer predetermined:

######  Assumption 4 (Uniform realizability and generalized completeness).

Assume that for any
$h\in[H],\mu\in\Pi,\nu\in\Pi^{\prime},f_{h+1}\in\mathcal{F}_{h+1}$, we have
$Q^{\mu\times\nu}_{h}\in\mathcal{F}_{h},\mathcal{T}_{h}^{\mu,\nu}f_{h+1}\in\mathcal{G}_{h}$.

Further, as we have mentioned before, we need to introduce a union bound over
the policies in $\Pi^{\prime}$ in our analysis and thus we also assume
$\Pi^{\prime}$ to be finite for simplicity.

######  Assumption 5 (Finite opponent’s policy class).

We assume $\Pi^{\prime}$ is finite.

######  Remark 4.

When $\Pi^{\prime}$ is infinite, it is straightforward to generalize our
analysis by replacing $|\Pi^{\prime}|$ with the covering number of
$\Pi^{\prime}$. However, the regret will still depend on the size of
$\Pi^{\prime}$, which is not the case in tabular setting Liu et al., (2022).
This dependency originates from our model-free type of policy evaluation
algorithm (Algorithm 2) and thus is inevitable for DORIS in general. That
said, when the Markov game has special structures (e.g., see the Markov game
in Section 5 and Section 6), we can avoid this dependency.

With the above assumptions, we have Theorem 2 to show that DORIS can still
achieve sublinear regret in adaptive setting, whose proof is deferred to
Section 7:

######  Theorem 2 (Regret of Adaptive Adversary).

Under Assumption 1,4,5, there exists an absolute constant $c$ such that for
any $\delta\in(0,1]$, $K\in\mathbb{N}$, choosing
$\beta=cV_{\max}^{2}\log(\mathcal{N}_{\mathrm{cov}}|\Pi||\Pi^{\prime}|/\delta)$
and $\eta=\sqrt{\log|\Pi|/(KV_{\max}^{2})}$ in DORIS, then with probability at
least $1-\delta$ we have:

$\displaystyle\text{Regret}(K)\leq\mathcal{O}\big{(}HV_{\max}\sqrt{Kd_{\mathrm{BEE}}\log\left(\mathcal{N}_{\mathrm{cov}}|\Pi||\Pi^{\prime}|/\delta\right)}\big{)}.$
(6)

We can see that in adaptive setting the regret also scales with $\sqrt{K}$,
implying that DORIS can still find an $\epsilon$-approximate best policy in
hindsight with $\widetilde{\mathcal{O}}(1/\epsilon^{2})$ episodes even when
the opponent is adaptive. Compared to Theorem 1, Theorem 2 has an additional
$\log|\Pi^{\prime}|$ in the upper bound (6), which comes from the union bound
over $\Pi^{\prime}$ in the analysis.

#### Intuitions on the regret bounds.

The regrets in Theorem 1 and Theorem 2 can be decomposed to two parts, the
online learning error incurred by Hedge and the cumulative value function
estimation error incurred by OptLSPE. From the online learning literature
(Hazan et al.,, 2016), the online learning error is
$\mathcal{O}(V_{\max}\sqrt{K\log|\Pi|})$ by viewing the policies in $\Pi$ as
experts and $\overline{V}^{t}(\mu)$ as the reward function of expert $\mu$.
For the estimation error, we utilize BEE dimensions to bridge
$\overline{V}^{t}(\mu^{t})-V_{1}^{\pi^{t}}(s_{1})$ with the function’s
empirical Bellman residuals on $\mathcal{D}_{1:t-1}$. This further incurs
$\widetilde{\mathcal{O}}(V_{\max}\sqrt{Kd_{\mathrm{BEE}}})$ in the results.
Our technical contribution mainly lies in bounding the cumulative value
function estimation error with the newly proposed BEE dimensions, which is
different from Jin et al., 2021a  where they focus on bounding the cumulative
distance from the optimal value function.

#### Comparison with existing works.

There have been works studying decentralized policy learning. However, most of
them (e.g., Tian et al., (2021); Jin et al., 2021c ; Huang et al., (2021))
only compete against the Nash value in a two-player zero-sum games, which is a
much weaker baseline than ours. Liu et al., (2022) can achieve a $\sqrt{K}$
regret upper bound under Definition 1, but their theory is restricted to the
tabular case and seems unable to deal with more complicated cases. For
example, when applying the algorithm in (Liu et al.,, 2022) to a linear MG,
the regret scales with $|\mathcal{S}|$ and $|\mathcal{A}|$, which becomes
vacuous in the face of large state and action space. However, for the case of
a linear MG, DORIS can achieve a regret bound that depends on the size of the
state-action space through the dimension $d$, rather than $|\mathcal{S}|$ and
$|\mathcal{A}|$. Thus DORIS is able to handle large or even infinite state and
action space. In summary, DORIS can achieve a $\sqrt{K}$ regret under
Definition 1 with general function approximation, capable of tackling all
models with low BEE dimension, including linear MGs, kernel MGs and
generalized linear complete models (Appendix C).

###  4.3 Self-Play Sample Complexity

Our previous discussion assumes the opponent is arbitrary or even adversary. A
natural question is to ask whether there are any additional guarantees if the
player and opponent run DORIS simultaneously, which is exactly Algorithm 3 in
the self-play setting. The following corollary answers this question
affirmatively and shows that Algorithm 3 can find an approximate CCE
$\widehat{\pi}$ efficiently:

######  Corollary 1.

Suppose Assumption 1,4 hold for all the agents $i$ and its corresponding
$\mathcal{F}_{i},\mathcal{G}_{i},\Pi_{i},\Pi_{-i}$. Then for any
$\delta\in(0,1],\epsilon>0$, if we choose

$\displaystyle
K\geq\mathcal{O}\bigg{(}H^{2}V_{\max}^{2}\cdot\max_{i\in[n]}\biggl{\\{}d_{\mathrm{BEE},i}\cdot\biggl{(}\log\mathcal{N}_{\mathrm{cov},i}+\sum_{j=1}^{n}\log|\Pi_{j}|+\log(n/\delta)\biggr{)}\biggr{\\}}\bigg{/}\epsilon^{2}\bigg{)},$
(7)

where $d_{\mathrm{BEE},i}$ and $\mathcal{N}_{\mathrm{cov},i}$ are defined
respectively as

$\displaystyle
d_{\mathrm{BEE},i}:=\mathrm{dim}_{\mathrm{BEE}}\big{(}\mathcal{F}_{i},\sqrt{1/K},\Pi_{i},\Pi_{-i}\big{)},\quad\mathcal{N}_{\mathrm{cov},i}:=\mathcal{N}_{\mathcal{F}_{i}\cup\mathcal{G}_{i}}(V_{\max}/K)KH,$

and set
$\beta_{i}=cV_{\max}^{2}\log(\mathcal{N}_{\mathrm{cov},i}|\Pi_{i}||\Pi_{-i}|n/\delta),\eta_{i}=\sqrt{\log|\Pi_{i}|/(KV_{\max}^{2})}$,
then with probability at least $1-\delta$, $\widehat{\pi}$ is
$\epsilon$-approximate CCE.

The proof is deferred to Appendix E. Corollary 1 shows that if we run DORIS
independently for each agent, we are able to find an $\epsilon$-approximate
CCE with $\widetilde{\mathcal{O}}(1/\epsilon^{2})$ samples. This can be
regarded as a counterpart in Markov games to the classic connection between
no-regret learning algorithms and equilibria in matrix games. This guarantee
does not hold if an algorithm can only achieve low regrets with respect to the
Nash values, which further validates the significance of DORIS to achieve low
regrets under Definition 1.

#### Avoiding curse of multiagents.

The sample complexity in (7) avoids exponential scaling with the number of
agents $n$ and only scales with $\max_{i\in[n]}d_{\mathrm{BEE},i}$,
$\max_{i\in[n]}\mathcal{N}_{\mathrm{cov},i}$ and
$\sum_{j=1}^{n}\log|\Pi_{j}|$, suggesting that statistically Algorithm 3 is
able to escape the curse-of-multiagents problem in the literature (Jin et al.,
2021b, ). Nevertheless, the input dimension of functions in $\mathcal{F}_{i}$
and $\mathcal{G}_{i}$ may scale with the number of the agents linearly,
leading to the computational inefficiency of OptLSPE. We comment that finding
computational efficient algorithms is beyond the scope of this paper and we
leave it to future works.

#### Comparison with existing algorithms.

There have been many works studying how to find equilibria in Markov games.
However, most of them are focused on centralized two-player zero-sum games
(Bai and Jin,, 2020; Xie et al.,, 2020; Jin et al., 2021c, ; Huang et al.,,
2021) rather than decentralized algorithms. For decentralized algorithms,
existing literature mainly handle with potential Markov games (Zhang et al.,
2021b, ; Leonardos et al.,, 2021; Ding et al.,, 2022) and two-player zero-sum
games (Daskalakis et al.,, 2020; Sayin et al.,, 2021; Wei et al., 2021a, ).
Mao et al., (2021); Jin et al., 2021b  are able to tackle decentralized multi-
agent general-sum Markov games while their algorithms are restricted to
tabular cases. Algorithm 3, on the other hand, can deal with more general
cases with function approximation and policy classes in multi-agent general-
sum games. Furthermore, compared to the above works, DORIS has an additional
advantage of robustness to adversaries since all the benign agents can exploit
the opponents and achieve no-regret learning.

#### Extensions.

Although Theorem 1, Theorem 2 and Corollary 1 are aimed at Markov games, DORIS
can be applied to a much larger scope of problems. Two such problems are
finding the optimal policy in constrained MDP (CMDP, Section 5) and vector-
valued MDP (VMDP, Section 6). We will investigate these two special yet
important problems later and demonstrate how to convert such problems into
Markov games with a fictitious opponent by duality, where DORIS is ready to
use.

##  5 Extension: Constrained Markov Decision Process

Although DORIS is designed to solve Markov games, there are quite a lot of
other problems where DORIS can tackle with small adaptation. In this section
we investigate an important scenario in practice called constrained Markov
decision process (CMDP). By converting CMDP into a maximin problem via
Lagrangian multiplier, we will be able to view it as a zero-sum Markov game
and apply DORIS readily.

#### Constrained Markov decision process.

Consider the Constrained Markov Decision Process (CMDP) (Ding et al.,, 2021)
$\mathcal{M}_{\text{CMDP}}=(\mathcal{S},\mathcal{A},\\{P_{h}\\}_{h=1}^{H},\\{r_{h}\\}_{h=1}^{H},\\{g_{h}\\}_{h=1}^{H},H)$
where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $H$
is the length of each episode,
$P_{h}:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is the transition
function at $h$-th step, $r_{h}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}_{+}$
is the reward function and $g_{h}:\mathcal{S}\times\mathcal{A}\to[0,1]$ is the
utility function at $h$-th step. We assume the reward $r_{h}$ is also bounded
in $[0,1]$ for simplicity and thus $V_{\max}=H$. Then given a policy
$\mu=\\{\mu_{h}:\mathcal{S}\to\Delta_{\mathcal{A}}\\}_{h\in[H]}$, we can
define the value function $V_{r,h}^{\mu}$ and action-value function
$Q_{r,h}^{\mu}$ with respect to the reward function $r$ as follows:

$\displaystyle
V_{r,h}^{\mu}(s)=\mathbb{E}_{\mu}\bigg{[}\sum_{t=h}^{H}r_{t}(s_{t},a_{t})\bigg{|}s_{h}=s\bigg{]},Q_{r,h}^{\mu}(s,a)=\mathbb{E}_{\mu}\bigg{[}\sum_{t=h}^{H}r_{t}(s_{t},a_{t})\bigg{|}s_{h}=s,a_{h}=a\bigg{]}.$

The value function $V_{g,h}^{\mu}$ and action-value function $Q_{g,h}^{\mu}$
with respect to the utility function $g$ can be defined similarly. Another
related concept is the state-action visitation distribution, which can be
defined as

$\displaystyle d^{\mu}_{h}(s,a)=\text{Pr}_{\mu}[(s_{h},a_{h})=(s,a)],$

where $\text{Pr}_{\mu}$ denotes the distribution of the trajectory induced by
executing policy $\mu$ in the $\mathcal{M}_{\text{CMDP}}$.

#### Learning objective.

In CMDP, the player aims to solve a constrained problem where the objective
function is the expected total rewards and the constraint is on the expected
total utilities: [Optimization problem of CMDP]

$\displaystyle\max_{\mu\in\Pi}V^{\mu}_{r,1}(s_{1})\quad\text{subject to}\quad
V^{\mu}_{g,1}(s_{1})\geq b,$ (8)

where $b\in(0,H]$ to avoid triviality.

Denote the optimal policy for (8) by $\mu^{*}_{\text{CMDP}}$, then the regret
can be defined as the performance gap with respect to $\mu^{*}_{\text{CMDP}}$:

$\displaystyle\text{Regret}(K)=\sum_{t=1}^{K}\Big{(}V_{r,1}^{\mu^{*}_{\text{CMDP}}}(s_{1})-V_{r,1}^{\mu^{t}}(s_{1})\Big{)}.$
(9)

However, since utility information is only revealed after a policy is decided,
it is impossible for each policy to satisfy the constraints. Therefore, like
Ding et al., (2021), we allow each policy to violate the constraint in each
episode and focus on minimizing total constraint violations over $K$ episodes:

$\displaystyle\text{Violation}(K)=\bigg{[}\sum_{t=1}^{K}\Big{(}b-V_{g,1}^{\mu^{t}}(s_{1})\Big{)}\bigg{]}_{+}.$
(10)

Achieving sublinear violations in (10) implies that if we sample a policy
uniformly from $\\{\mu^{t}\\}_{t=1}^{K}$, its constraint violation can be
arbitrarily small given large enough $K$. Therefore, if an algorithm can
achieve sublinear regret in (9) and sublinear violations in (10) at the same
time, this algorithm will be able to find a good approximate policy to
$\mu^{*}_{\text{CMDP}}$.

###  5.1 Algorithm: DORIS-C

To solve Problem 5 with DORIS, we first need to convert it into a Markov game.
A natural idea is to apply the Lagrangian multiplier $Y\in\mathbb{R}_{+}$ to
Problem 5, which brings about the equivalent maximin problem below:

$\displaystyle\max_{\mu\in\Pi}\min_{Y\geq
0}\mathcal{L}_{\mathrm{CMDP}}(\mu,Y):=V^{\mu}_{r,1}(s_{1})+Y(V_{g,1}^{\mu}(s_{1})-b).$
(11)

Although Problem 5 is non-concave in $\mu$, there have been works indicating
that strong duality still holds for Problem 5 when the policy class is
described by a good parametrization (Paternain et al.,, 2019). Therefore, here
we assume strong duality holds and it is straightforward to generalize our
analysis to the case where there exists a duality gap:

######  Assumption 6 (Strong duality).

Assume strong duality holds for Problem 5, i.e.,

$\displaystyle\max_{\mu\in\Pi}\min_{Y\geq
0}\mathcal{L}_{\mathrm{CMDP}}(\mu,Y)=\min_{Y\geq
0}\max_{\mu\in\Pi}\mathcal{L}_{\mathrm{CMDP}}(\mu,Y).$ (12)

######  Remark 5.

One example case where strong duality (12) holds is when policy class $\Pi$
satisfies global realizability. Let $\mu^{*}_{\text{glo}}$ denote the solution
to $\max_{\mu_{h}(\cdot|s)\in\Delta_{\mathcal{A}}}\min_{Y\geq
0}\mathcal{L}_{\mathrm{CMDP}}(\mu,Y)$. Ding et al., (2021) showed that
$\max_{\mu\in(\Delta_{\mathcal{A}})^{|\mathcal{S}|H}}\min_{Y\geq
0}\mathcal{L}_{\mathrm{CMDP}}(\mu,Y)$ satisfies strong duality, and thus as
long as $\mu^{*}_{\text{glo}}\in\Pi$, Problem 5 also has strong duality.

Further, let $D(Y):=\max_{\mu\in\Pi}\mathcal{L}_{\mathrm{CMDP}}(\mu,Y)$ denote
the dual function and suppose the optimal dual variable is
$Y^{*}=\arg\min_{Y\geq 0}D(Y)$. To ensure $Y^{*}$ is bounded, we need to
assume that the standard Slater’s Condition holds:

######  Assumption 7.

There exists $\lambda_{\mathrm{sla}}>0$ and $\widetilde{\mu}\in\Pi$ such that
$V_{g,1}^{\widetilde{\mu}}(s_{1})\geq b+\lambda_{\mathrm{sla}}$.

Then the following lemma shows that Assumption 7 implies bounded optimal dual
variable, whose proof is deferred to Appendix F.1:

######  Lemma 1.

Suppose Assumption 6,7 hold, then we have $0\leq
Y^{*}\leq{H}/{\lambda_{\mathrm{sla}}}$.

Now we are ready to adapt DORIS into a primal-dual algorithm to solve Problem
5. Notice that the maximin problem (11) can be viewed as a zero-sum Markov
game where the player’s policy is $\mu$ and the reward function for the player
is $r_{h}(s,a)+Yg_{h}(s,a)$. The opponent’s action is $Y\in\mathbb{R}_{+}$
which remains the same throughout a single episode. With this formulation, we
can simply run DORIS on the player, assuming the player is given function
classes $\\{\mathcal{F}^{r},\mathcal{G}^{r}\\}$ and
$\\{\mathcal{F}^{g},\mathcal{G}^{g}\\}$ to approximate $Q_{r,h}^{\mu}$ and
$Q_{g,h}^{\mu}$ respectively. In the meanwhile, we run online projected
gradient descent on the opponent so that its action $Y$ can capture the total
violation so far.

This new algorithm is called DORIS-C and shown in Algorithm 4. It consists of
the following three steps in each iteration. For the policy evaluation task in
the second step, DORIS-C runs a single-agent version of OptLSPE to estimate
$V^{\mu}_{r,1}(s_{1})$ and $V^{\mu}_{g,1}(s_{1})$ separately, which is
essential for DORIS-C to deal with the infinity of the opponent’s policy
class, i.e., $\mathbb{R}_{+}$.

  * •

The player plays a policy $\mu^{t}$ sampled from its hyperpolicy $p^{t}$ and
collects a trajectory.

  * •

The player runs OptLSPE-C to obtain optimistic value function estimations
$\overline{V}^{t}_{r}(\mu),\break\overline{V}^{t}_{g}(\mu)$ for all
$\mu\in\Pi$ and updates the hyperpolicy using Hedge with the loss function
being $\overline{V}^{t}_{r}(\mu)+Y_{t}\overline{V}^{t}_{g}(\mu)$. The
construction rule for $\mathcal{B}_{\mathcal{D}}(\mu)$ is still based on
relaxed least-squared policy evaluation:

$\displaystyle\mathcal{B}_{\mathcal{D}}(\mu)\leftarrow\\{f\in\mathcal{F}:\mathcal{L}_{\mathcal{D}}(f_{h},f_{h+1},\mu)\leq\inf_{g\in\mathcal{G}}\mathcal{L}_{\mathcal{D}}(g_{h},f_{h+1},\mu)+\beta,\forall
h\in[H]\\},$ (13)

where $\mathcal{L}_{\mathcal{D}}$ is the empirical Bellman residuals on
$\mathcal{D}$:

$\displaystyle\mathcal{L}_{\mathcal{D}}(\xi_{h},\zeta_{h+1},\mu)=\sum_{(s_{h},a_{h},x_{h},s_{h+1})\in\mathcal{D}}[\xi_{h}(s_{h},a_{h})-x_{h}-\zeta_{h+1}(s_{h+1},\mu)]^{2}.$

  * •

The dual variable is updated using online projected gradient descent.

Algorithm 4 DORIS-C

Input: learning rate $\eta,\alpha$, confidence parameter
$\beta_{r},\beta_{g}$, projection length $\textstyle\chi$.

Initialize $p^{1}\in\mathbb{R}^{|\Pi|}$ to be uniform over $\Pi$,
$Y_{1}\leftarrow 0$.

for $t=1,\cdots,K$ do

Collect samples:

The player samples $\mu^{t}$ from $p^{t}$.

Run $\mu^{t}$ and collect
$\mathcal{D}^{r}_{t}=\\{s^{t}_{1},a^{t}_{1},r^{t}_{1},\cdots,s^{t}_{H+1}\\}$,$\mathcal{D}^{g}_{t}=\\{s^{t}_{1},a^{t}_{1},g^{t}_{1},\cdots,s^{t}_{H+1}\\}$.

Update policy distribution:

$\overline{V}^{t}_{r}(\mu)\leftarrow\textbf{{OptLSPE-C}}(\mu,\mathcal{D}^{r}_{1:t-1},\mathcal{F}^{r},\mathcal{G}^{r},\beta_{r}),\quad\forall\mu\in\Pi$.

$\overline{V}^{t}_{g}(\mu)\leftarrow\textbf{{OptLSPE-C}}(\mu,\mathcal{D}^{g}_{1:t-1},\mathcal{F}^{g},\mathcal{G}^{g},\beta_{g}),\quad\forall\mu\in\Pi$.

$p^{t+1}(\mu)\propto
p^{t}(\mu)\cdot\exp(\eta\cdot(\overline{V}^{t}_{r}(\mu)+Y_{t}\overline{V}^{t}_{g}(\mu))),\quad\forall\mu\in\Pi$.

Update dual variable:

$Y_{t+1}\leftarrow\text{Proj}_{[0,{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}]}(Y_{t}+\alpha(b-\overline{V}^{t}_{g}(\mu^{t})))$.

end for

Algorithm 5
$\textbf{{OptLSPE-C}}(\mu,\mathcal{D},\mathcal{F},\mathcal{G},\beta)$

Construct $\mathcal{B}_{\mathcal{D}}(\mu)$ based on $\mathcal{D}$ via (13).

Select
$\bar{V}\leftarrow\max_{f\in\mathcal{B}_{\mathcal{D}}(\mu)}f(s_{1},\mu)$.

return $\bar{V}$.

###  5.2 Theoretical Guarantees

Next we provide the regret and constraint violation bounds for DORIS-C. Here
we also consider the case where $\Pi$ is finite, i.e., Assumption 1 is true.
However, we can see that here the opponent is adaptive and its policy class is
infinite, suggesting that Assumption 5 is violated. Fortunately, since the
opponent only affects the reward function, the player can simply first
estimate $V^{\mu}_{r,1}(s_{1})$ and $V^{\mu}_{g,1}(s_{1})$ respectively and
then use their weighted sum to approximate the target value function
$V^{\mu}_{r,1}(s_{1})+Y\cdot V^{\mu}_{g,1}(s_{1})$. In this way, DORIS-C
circumvents introducing a union bound on $Y$ and thus can work even when the
number of possible values for $Y$ is infinite.

We also need to introduce the realizability and general completeness
assumptions on the function classes as before:

######  Assumption 8 (Realizability and generalized completeness in CMDP).

Assume that for any
$h\in[H],\mu\in\Pi,f^{r}_{h+1}\in\mathcal{F}^{r}_{h+1},f^{g}_{h+1}\in\mathcal{F}^{g}$,
we have

$\displaystyle
Q_{r,h}^{\mu}\in\mathcal{F}^{r}_{h},Q_{g,h}^{\mu}\in\mathcal{F}^{g}_{h},\mathcal{T}_{h}^{\mu,r}f^{r}_{h+1}\in\mathcal{G}^{r}_{h},\mathcal{T}_{h}^{\mu,g}f^{g}_{h+1}\in\mathcal{G}^{g}_{h}.$
(14)

Here $\mathcal{T}_{h}^{\mu,r}$ is the Bellman operator at step $h$ with
respect to $r$:

$\displaystyle(\mathcal{T}_{h}^{\mu,r}f_{h+1})(s,a)=r_{h}(s,a)+\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}f_{h+1}(s^{\prime},\mu),$

where
$f_{h+1}(s^{\prime},\mu)=\mathbb{E}_{a^{\prime}\sim\mu(\cdot|s)}[f_{h+1}(s^{\prime},a^{\prime})]$.
$\mathcal{T}_{h}^{\mu,g}$ is defined similarly. We can see that (14) simply
says that all the action value functions with respect to $r$ ($g$) belong to
$\mathcal{F}^{r}$ ($\mathcal{F}^{g}$) and $\mathcal{G}^{r}$
($\mathcal{G}^{g}$) contains all the results of applying Bellman operator with
respect to $r$ ($g$) to the functions in $\mathcal{F}^{r}$
($\mathcal{F}^{g}$).

In addition, as a simplified case of Definition 6, BEE dimension for single-
agent setting can be defined as follows:

######  Definition 7.

The single-agent $\epsilon$-Bellman Evaluation Eluder dimension of function
class $\mathcal{F}$ on distribution family $\mathcal{Q}$ with respect to the
policy class $\Pi$ and the reward function $r$ is defined as follows:

$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,r,\mathcal{Q}):=\max_{h\in[H]}\mathrm{dim}_{\mathrm{DE}}((\mathcal{I}-\mathcal{T}^{\Pi,r}_{h})\mathcal{F},\mathcal{Q}_{h},\epsilon),$

where
$(\mathcal{I}-\mathcal{T}^{\Pi,r}_{h})\mathcal{F}:=\\{f_{h}-\mathcal{T}^{\mu,r}_{h}f_{h+1}:f\in\mathcal{F},\mu\in\Pi\\}$.

We also let $\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,r)$ denote
$\min\\{\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,r,\mathcal{Q}^{1}),\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\break\Pi,r,\mathcal{Q}^{2})\\}$
as before.
$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,g,\mathcal{Q})$ and
$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,g)$ are defined
similarly but with respect to the utility function $g$.

Now we can present the following theorem which shows that DORIS-C is capable
of achieving sublinear regret and constraint violation for Problem 5. We also
use the following notations to simplify writing:

$\displaystyle
d_{\mathrm{BEE},r}:=\mathrm{dim}_{\mathrm{BEE}}\big{(}\mathcal{F}^{r},\sqrt{{1}/{K}},\Pi,r\big{)},\quad\mathcal{N}_{\mathrm{cov},r}:=\mathcal{N}_{\mathcal{F}^{r}\cup\mathcal{G}^{r}}(H/K)KH,$
$\displaystyle
d_{\mathrm{BEE},g}:=\mathrm{dim}_{\mathrm{BEE}}\big{(}\mathcal{F}^{g},\sqrt{{1}/{K}},\Pi,g\big{)},\quad\mathcal{N}_{\mathrm{cov},r}:=\mathcal{N}_{\mathcal{F}^{g}\cup\mathcal{G}^{g}}(H/K)KH.$

######  Theorem 3.

Under Assumption 6,7,1,8, there exists an absolute constant $c$ such that for
any $\delta\in(0,1]$, $K\in\mathbb{N}$, if we choose
$\beta_{r}=cH^{2}\log(\mathcal{N}_{\mathrm{cov},r}|\Pi|/\delta)$,
$\beta_{g}=cH^{2}\log(\mathcal{N}_{\mathrm{cov},g}|\Pi|/\delta)$,
$\alpha=1/{\sqrt{K}}$,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}={2H}/{\lambda_{\mathrm{sla}}}$
and
$\eta=\sqrt{{\log|\Pi|}/({K({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}+1)^{2}H^{2}})}$
in DORIS-C, then with probability at least $1-\delta$, we have:

$\displaystyle\text{Regret}(K)\leq\mathcal{O}\bigg{(}\bigg{(}H^{2}+\frac{H^{2}}{\lambda_{\mathrm{sla}}}\bigg{)}\sqrt{Kd_{\mathrm{BEE},r}\log\left(\mathcal{N}_{\mathrm{cov},r}|\Pi|/\delta\right)}\bigg{)},$
(15)
$\displaystyle\text{Violation}(K)\leq\mathcal{O}\bigg{(}\bigg{(}H^{2}+\frac{H}{\lambda_{\mathrm{sla}}}\bigg{)}\sqrt{K\epsilon_{\text{BEE}}}\bigg{)},$
(16)

where we define $\epsilon_{\text{BEE}}$ as

$\displaystyle\epsilon_{\text{BEE}}=\max\Big{\\{}d_{\mathrm{BEE},r}\log\left(\mathcal{N}_{\mathrm{cov},r}|\Pi|/\delta\right),d_{\mathrm{BEE},g}\log\left(\mathcal{N}_{\mathrm{cov},g}|\Pi|/\delta\right)\Big{\\}}.$

The bounds in (15) and (16) show that both the regret and constraint violation
of DORIS-C scale with $\sqrt{K}$. This implies that for any $\epsilon>0$, if
$\widehat{\mu}$ is sampled uniformly from $\\{\mu^{t}\\}_{t=1}^{K}$ and
$K\geq\widetilde{\mathcal{O}}(1/\epsilon^{2})$, $\widehat{\mu}$ will be an
$\epsilon$ near-optimal policy with high probability in the sense that

$\displaystyle V_{r,1}^{\widehat{\mu}}(s_{1})\geq
V_{r,1}^{\mu^{*}_{\text{CMDP}}}(s_{1})-\epsilon,\qquad
V_{g,1}^{\widehat{\mu}}(s_{1})\geq b-\epsilon.$

In addition, compared to the results in Theorem 1 and Theorem 2, (15) and (16)
have an extra term scaling with $1/\lambda_{\mathrm{sla}}$. This is because
DORIS-C is a primal-dual algorithm and $\lambda_{\mathrm{sla}}$ characterizes
the regularity of this constrained optimization problem.

The proof of the regret bound is similar to Theorem 1 and Theorem 2 by viewing
$V^{\mu}_{r,1}(s_{1})+YV^{\mu}_{g,1}(s_{1})$ as the target value function and
decomposing the regret into cumulative estimation error and online learning
error. To bound the constraint violation, we need to utilize the strong
duality and the property of online projected gradient descent. See Appendix F
for more details.

#### Comparison with existing algorithms.

There has been a line of works studying the exploration and exploitation in
CMDPs. Efroni et al., (2020); Ding et al., (2021) propose a series of
algorithms which can achieve $\sqrt{K}$ bound on regrets and constraint
violations. However, they focus on tabular cases or linear function
approximation and do not consider policy classes while DORIS-C can deal with
nonlinear function approximation and policy classes. As an interesting follow-
up, Liu et al., (2021) reduces the constraint violation to
$\widetilde{\mathcal{O}}(1)$ by adding slackness to the algorithm and achieves
zero violation when a strictly safe policy is known; Wei et al., 2021b
further avoids such requirement with the price of worsened regrets. However,
these improvements are all limited in tabular cases and we leave the
consideration of their general function approximation counterpart to future
works.

##  6 Extension: Vector-valued Markov Decision process

Another setting where DORIS can play a role is the approachability task for
vector-valued Markov decision process (VMDP) (Miryoosefi et al.,, 2019; Yu et
al.,, 2021; Miryoosefi and Jin,, 2021). Similar to CMDP, we convert it into a
zero-sum Markov game by Fenchel’s duality and then adapt DORIS properly to
solve it.

#### Vector-valued Markov decision process.

Consider the Vector-valued Markov decision process (VMDP) (Yu et al.,, 2021)
$\mathcal{M}_{\text{VMDP}}=(\mathcal{S},\mathcal{A},\\{P_{h}\\}_{h=1}^{H},\bm{r},H)$
where
$\bm{r}=\\{\bm{r}_{h}:\mathcal{S}\times\mathcal{A}\to[0,1]^{d}\\}_{h=1}^{H}$
is a collection of $d$-dimensional reward functions and the rest of the
components are defined the same as in Section 5. Then given a policy
$\mu\in\Pi$, we can define the corresponding $d$-dimensional value function
$\bm{V}^{\mu}_{h}:\mathcal{S}\to[0,H]^{d}$ and action-value function
$\bm{Q}^{\mu}_{h}:\mathcal{S}\times\mathcal{A}\to[0,H]^{d}$ as follows:

$\displaystyle\bm{V}_{h}^{\mu}(s)=\mathbb{E}_{\mu}\bigg{[}\sum_{t=h}^{H}\bm{r}_{t}(s_{t},a_{t})\bigg{|}s_{h}=s\bigg{]},\quad\bm{Q}_{h}^{\mu}(s,a)=\mathbb{E}_{\mu}\bigg{[}\sum_{t=h}^{H}\bm{r}_{t}(s_{t},a_{t})\bigg{|}s_{h}=s,a_{h}=a\bigg{]}.$

#### Learning objective.

In this paper we study the approachability task (Miryoosefi et al.,, 2019) in
VMDP where the player needs to learn a policy whose expected cumulative reward
vector lies in a convex target set $\mathcal{C}$. We consider a more general
agnostic version (Yu et al.,, 2021; Miryoosefi and Jin,, 2021) where we do not
assume the existence of such policies and the player learns to minimize the
Euclidean distance between expected reward and the target set $\mathcal{C}$:
[Approachability for VMDP]

$\displaystyle\min_{\mu\in\Pi}\mathrm{dist}(\bm{V}^{\mu}_{1}(s_{1}),\mathcal{C}),$

where $\mathrm{dist}(\bm{x},\mathcal{C})$ is the Euclidean distance between
point $\bm{x}$ and set $\mathcal{C}$.

The approachability for VMDP is a natural objective in multi-task
reinforcement learning where each dimension of the reward can be regarded as a
task. It is important in many practical domains such as robotics, autonomous
vehicles and recommendation systems (Yu et al.,, 2021). Therefore, finding the
optimal policy for Problem 6 efficiently is of great significance in modern
reinforcement learning.

###  6.1 Algorithm: DORIS-V

To deal with Probelm 6, we first convert Problem 6 into a Markov game as we
have done in Section 5. By Fenchel’s duality of the distance function, we know
Problem 6 is equivalent to the following minimax problem:

$\displaystyle\min_{\mu\in\Pi}\max_{\bm{\theta}\in\mathbb{B}(1)}\mathcal{L}_{\mathrm{VMDP}}(\mu,\bm{\theta}):=\langle\bm{\theta},\bm{V}^{\mu}_{1}(s_{1})\rangle-\max_{\bm{x}\in\mathcal{C}}\langle\bm{\theta},\bm{x}\rangle,$

where $\mathbb{B}(r)$ is the $d$-dimensional Euclidean ball of radius $r$
centered at the origin. Regarding $\mu$ as the player’s policy and
$\bm{\theta}$ as the opponent, we can again view this minimax problem as a
Markov game where the reward function for the player is
$\langle\bm{\theta},\bm{r}_{h}(s,a)\rangle$. Consider the general function
approximation case that the player is given function classes
$\mathcal{F}:=\\{\mathcal{F}^{j}_{h}\\}_{h,j=1}^{H,d},\mathcal{G}:=\\{\mathcal{G}^{j}_{h}\\}_{h,j=1}^{H,d}$
to approximate $\bm{Q}_{h}^{\mu}$ where $\mathcal{F}^{j}_{h}$ and
$\mathcal{G}^{j}_{h}$ are the $j$-th dimension of $\mathcal{F}_{h}$ and
$\mathcal{G}_{h}$, then we can run DORIS for the player while the opponent
will update $\bm{\theta}$ with online projected gradient ascent just like
DORIS-C.

We call this new algorithm DORIS-V, which is shown in Algorithm 6 and also
consists of three steps in each iteration. For the policy evaluation task
here, we apply OptLSPE-V and construct a confidence set for each dimension of
the function class separately, and let the final confidence set be their
intersection. Therefore the construction rule for
$\mathcal{B}_{\mathcal{D}}(\mu)$ is given as:

$\displaystyle\mathcal{B}_{\mathcal{D}}(\mu)\leftarrow\\{f\in\mathcal{F}:\mathcal{L}_{\mathcal{D}^{j}}(f^{j}_{h},f^{j}_{h+1},\mu)\leq\inf_{g\in\mathcal{G}}\mathcal{L}_{\mathcal{D}^{j}}(g^{j}_{h},f^{j}_{h+1},\mu)+\beta,\forall
h\in[H],j\in[d]\\},$ (17)

where for any $j\in[d]$ and $h\in[H]$,

$\displaystyle\mathcal{L}_{\mathcal{D}^{j}}(\xi^{j}_{h},\zeta^{j}_{h+1},\mu)=\sum_{(s_{h},a_{h},r^{j}_{h},s_{h+1})\in\mathcal{D}}[\xi^{j}_{h}(s_{h},a_{h})-r^{j}_{h}-\zeta^{j}_{h+1}(s_{h+1},\mu)]^{2},$

and $r^{j}_{h}$ is the $j$-the dimension of $\bm{r}_{h}$. In addition, since
here we want to minimize the distance, OptLSPE-V will output a pessimistic
estimate of the target value function instead of an optimistic one.

  * •

The player plays a policy $\mu^{t}$ sampled from its hyperpolicy $p^{t}$ and
collects a trajectory.

  * •

The player runs OptLSPE-V to obtain pessimistic value function estimations
$\langle\bm{\theta}^{t},\underline{\bm{V}}^{t}(\mu)\rangle$ for all
$\mu\in\Pi$ and updates the hyperpolicy using Hedge.

  * •

The dual variable is updated using online projected gradient ascent.

Algorithm 6 DORIS-V

Input: learning rate $\eta,\alpha_{t}$, confidence parameter $\beta$.

Initialize $p^{1}\in\mathbb{R}^{|\Pi|}$ to be uniform over $\Pi$,
$\bm{\theta}_{1}\leftarrow 0$.

for $t=1,\cdots,K$ do

Collect samples:

The learner samples $\mu^{t}$ from $p^{t}$.

Run $\mu^{t}$ and collect
$\mathcal{D}_{t}=\\{s^{t}_{1},a^{t}_{1},\bm{r}^{t}_{1},\cdots,s^{t}_{H+1}\\}$.

Update policy distribution:

$\underline{\bm{V}}^{t}(\mu)\leftarrow\textbf{{OptLSPE-V}}(\mu,\mathcal{D}_{1:t-1},\mathcal{F},\mathcal{G},\beta,\bm{\theta}^{t}),\quad\forall\mu\in\Pi$.

$p^{t+1}(\mu)\propto
p^{t}(\mu)\cdot\exp(-\eta\langle\underline{\bm{V}}^{t}(\mu),\bm{\theta}^{t}\rangle),\quad\forall\mu\in\Pi$.

Update dual variable:

$\bm{\theta}_{t+1}\leftarrow\text{Proj}_{\mathbb{B}(1)}(\bm{\theta}_{t}+\alpha_{t}(\underline{\bm{V}}^{t}(\mu_{t})-\arg\max_{\bm{x}\in\mathcal{C}}\langle\bm{\theta}_{t},\bm{x}\rangle))$.

end for

Output: $\widehat{\mu}$ uniformly sampled from $\mu^{1},\cdots,\mu^{K}$.

Algorithm 7
$\textbf{{OptLSPE-V}}(\mu,\mathcal{D},\mathcal{F},\mathcal{G},\beta,\bm{\theta})$

Construct $\mathcal{B}_{\mathcal{D}}(\mu)$ based on $\mathcal{D}$ via (17).

Select $\underline{\bm{V}}\leftarrow f_{1}(s_{1},\mu)$, where
$f=\arg\min_{f^{\prime}\in\mathcal{B}_{\mathcal{D}}(\mu)}\langle
f^{\prime}_{1}(s_{1},\mu),\bm{\theta}\rangle$.

return $\underline{\bm{V}}$.

###  6.2 Theoretical Guarantees

In this subsection, we still consider finite policy class $\Pi$. Notice that
in the fictitious MG of VMDP, the policy class of the opponent is also
infinite, i.e., $\mathbb{B}(1)$. However, since the player only needs to
estimate $\bm{V}^{\mu}_{1}(s_{1})$, which is independent of $\bm{\theta}$,
DORIS-V can also circumvent the union bound on $\bm{\theta}$ just like
DORIS-C.

In addition, we need to introduce the realizability and generalized
completeness assumptions in this specific setting, which is simply a
vectorized version as before:

######  Assumption 9 (Realizability and generalized completeness in VMDP).

Assume that for any $h\in[H],j\in[d],\mu\in\Pi,f_{h+1}\in\mathcal{F}_{h+1}$,
we have
$Q^{\mu,j}_{h}\in\mathcal{F}_{h,j},\mathcal{T}_{h}^{\mu,j}f^{j}_{h+1}\in\mathcal{G}^{j}_{h}$,
where $Q_{h}^{\mu,j}$ is the $j$-the dimension of $\bm{Q}_{h}^{\mu}$ and
$\mathcal{T}_{h}^{\mu,j}$ is the $j$-th dimensional Bellman operator at step
$h$ defined in (18).

Here $\mathcal{T}_{h}^{\mu,j}$ is defined as:

$\displaystyle(\mathcal{T}_{h}^{\mu,j}f^{j}_{h+1})(s,a):=r^{j}_{h}(s,a)+\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}f^{j}_{h+1}(s^{\prime},\mu).$ (18)

In addition, the BEE dimension for VMDP can be defined as the maximum BEE
dimension among all $d$ dimensions:

######  Definition 8.

The $d$-dimensional $\epsilon$-Bellman Evaluation Eluder dimension of function
class $\mathcal{F}$ on distribution family $\mathcal{Q}$ with respect to the
policy class $\Pi$ is defined as follows:

$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\mathcal{Q}):=\max_{j\in[d],h\in[H]}\mathrm{dim}_{\mathrm{DE}}((\mathcal{I}-\mathcal{T}^{\Pi,j}_{h})\mathcal{F}^{j},\mathcal{Q}_{h},\epsilon),$

where
$(\mathcal{I}-\mathcal{T}^{\Pi,j}_{h})\mathcal{F}^{j}:=\\{f^{j}_{h}-\mathcal{T}^{\mu,j}_{h}f^{j}_{h+1}:f\in\mathcal{F},\mu\in\Pi\\}$.

We also use $\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi)$ to denote
$\min\\{\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\mathcal{Q}^{1}),\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\mathcal{Q}^{2})\\}$
as before.

The next theorem shows that DORIS-V is able to find a near optimal policy for
Problem 6 with polynomial samples, where we use the following notations to
simplify writing:

$\displaystyle
d_{\mathrm{BEE,V}}:=\mathrm{dim}_{\mathrm{BEE}}\big{(}\mathcal{F},\sqrt{{1}/{K}},\Pi\big{)},\quad\mathcal{N}_{\mathrm{cov,V}}:=\max_{j\in[d]}\mathcal{N}_{\mathcal{F}^{j}\cup\mathcal{G}^{j}}(H/K)KH.$

######  Theorem 4.

Under Assumption 1,9, there exists an absolute constant $c$ such that for any
$\delta\in(0,1]$, $K\in\mathbb{N}$, if we choose
$\beta=cH^{2}\log(\mathcal{N}_{\mathrm{cov,V}}|\Pi|d/\delta)$,
$\alpha_{t}={2}/({H\sqrt{dt}})$, and $\eta=\sqrt{{\log|\Pi|}/({KH^{2}d})}$ in
DORIS-V, then with probability at least $1-\delta$, we have:

$\displaystyle\mathrm{dist}(\bm{V}^{\widehat{\mu}}_{1}(s_{1}),\mathcal{C})\leq\min_{\mu\in\Pi}\mathrm{dist}(\bm{V}^{\mu}_{1}(s_{1}),\mathcal{C})+\mathcal{O}\Big{(}H^{2}\sqrt{d}\cdot\sqrt{{d_{\mathrm{BEE,V}}\log\left(\mathcal{N}_{\mathrm{cov,V}}|\Pi|d/\delta\right)}/{K}}\Big{)}.$
(19)

The bound in (19) shows that for any $\epsilon>0$, if
$K\geq\widetilde{\mathcal{O}}(d/\epsilon^{2})$, $\widehat{\mu}$ will be an
$\epsilon$ near-optimal policy with high probability. Compared to the results
in Theorem 1 and Theorem 2, there is an additional term $d$. This is because
the reward is $d$-dimensional and we are indeed evaluating $d$ scalar value
functions in OptLSPE-V.

The proof is similar to that of Theorem 3 and utilizes the fact that both
$\mu$ and $\bm{\theta}$ are updated via no-regret online learning algorithms
(Hedge for $\mu$ and online projected gradient ascent for $\bm{\theta}$). See
Appendix G for more details.

#### Comparison with existing algorithms.

Yu et al., (2021) has also proposed algorithms for approachability tasks in
tabular cases and achieve the same sub-optimality gap with respect to $d$ and
$K$ as Theorem 4. Miryoosefi and Jin, (2021) studies the tabular and linear
approximation cases, achieving $\sqrt{K}$ regret as well. Their sample
complexity does not scale with $d$ because they have normalized the reward
vector to lie in $\mathbb{B}(1)$ in tabular cases and
$\mathbb{B}(\sqrt{d_{\mathrm{lin}}})$ in $d_{\mathrm{lin}}$-dimensional linear
VMDPs. Compared to the above works, DORIS-V is able to tackle the more general
cases with nonlinear function approximation and policy classes while retaining
the sample efficiency.

##  7 Proof Sketch of Theorem 1 and Theorem 2

In this section we present a proof sketch for Theorem 1 and Theorem 2. We
first consider the oblivious setting. Let
$\mu^{*}=\arg\max_{\mu\in\Pi}\sum_{t=1}^{K}V_{1}^{\mu\times\nu^{t}}(s_{1})$
and we can decompose the regret into the following terms:

$\displaystyle\max_{\mu\in\Pi}\sum_{t=1}^{K}V_{1}^{\mu\times\nu^{t}}(s_{1})-\sum_{t=1}^{K}V_{1}^{\pi^{t}}(s_{1})$
$\displaystyle\qquad=\bigg{(}\underbrace{\sum_{t=1}^{K}V_{1}^{\mu^{*}\times\nu^{t}}(s_{1})-\sum_{t=1}^{K}\overline{V}^{t}(\mu^{*})}_{\displaystyle(1)}\bigg{)}+\bigg{(}\underbrace{\sum_{t=1}^{K}\overline{V}^{t}(\mu^{*})-\sum_{t=1}^{K}\langle\overline{V}^{t},p^{t}\rangle}_{\displaystyle(2)}\bigg{)}$
$\displaystyle\qquad\qquad+\bigg{(}\underbrace{\sum_{t=1}^{K}\langle\overline{V}^{t},p^{t}\rangle-\sum_{t=1}^{K}\overline{V}^{t}(\mu^{t})}_{\displaystyle(3)}\bigg{)}+\bigg{(}\underbrace{\sum_{t=1}^{K}\overline{V}^{t}(\mu^{t})-\sum_{t=1}^{K}V^{\pi^{t}}_{1}(s_{1})}_{\displaystyle(4)}\bigg{)}.$
(20)

Our proof bounds these terms separately and mainly consists of three steps:

  * •

Prove $\overline{V}^{t}(\mu)$ is an optimistic estimation of
$V_{1}^{\mu\times\nu^{t}}(s_{1})$ for all $t\in[K]$ and $\mu\in\Pi$, which
implies that term $(1)\leq 0$.

  * •

Bound term (4), the cumulative estimation error
$\sum_{t=1}^{K}\overline{V}^{t}(\mu^{t})-V_{1}^{\pi^{t}}(s_{1})$. In this step
we utilize the newly proposed complexity measure BEE dimension to bridge the
cumulative estimation error and the empirical Bellman residuals occurred in
OptLSPE.

  * •

Bound term (2) using the existing results of online learning error induced by
Hedge and bound (3) by noticing that it is a martingale difference sequence.

###  7.1 Step 1: Prove Optimism

First we can show that the constructed set
$\mathcal{B}_{\mathcal{D}_{1:t-1}}(\mu,\nu^{t})$ is not vacuous in the sense
that the true action-value function $Q^{\mu,\nu^{t}}$ belongs to it with high
probability

######  Lemma 2.

With probability at least $1-{\delta}/{4}$, we have for all $t\in[K]$ and
$\mu\in\Pi$,
$Q^{\mu,\nu^{t}}\in\mathcal{B}_{\mathcal{D}_{1:t-1}}(\mu,\nu^{t})$.

###### Proof.

See Appendix D.1. ∎

Then since
$\overline{V}^{t}(\mu)=\max_{f\in\mathcal{B}_{\mathcal{D}_{1:t-1}}(\mu,\nu^{t})}f(s_{1},\mu,\nu^{t})$,
we know for all $t\in[K]$ and $\mu\in\Pi$,

$\displaystyle\overline{V}^{t}(\mu)\geq
Q^{\mu,\nu^{t}}(s_{1},\mu,\nu^{t})=V_{1}^{\mu\times\nu^{t}}(s_{1}).$

In particular, we have for all $t\in[K]$,

$\displaystyle\overline{V}^{t}(\mu^{*})\geq
V_{1}^{\mu^{*}\times\nu^{t}}(s_{1}).$ (21)

Thus, (21) implies that $\overline{V}^{t}(\mu^{*})$ is an optimistic estimate
of $V_{1}^{\mu^{*}\times\nu^{t}}(s_{1})$ for all $t$, and therefore term (1)
in (20) is non-positive.

###  7.2 Step 2: Bound Estimation Error

Next we aim to handle term (4) in (20) and show the estimation error
$\sum_{t=1}^{K}\overline{V}^{t}(\mu^{t})-V_{1}^{\pi^{t}}(s_{1})$ is small. Let
$f^{t,\mu}=\arg\max_{f\in\mathcal{B}_{\mathcal{D}_{1:t-1}}(\mu,\nu^{t})}f(s_{1},\mu,\nu^{t})$.
Then using standard concentration inequalities, we can have the following
lemma which says that empirical Bellman residuals are indeed close to true
residuals with high probability. Recall that here
$\pi^{k}=\mu^{k}\times\nu^{k}$.

######  Lemma 3.

With probability at least $1-{\delta}/{4}$, we have for all $t\in[K]$,
$h\in[H]$ and $\mu\in\Pi$,

$\displaystyle(a)\quad\sum_{k=1}^{t-1}\mathbb{E}_{\pi^{k}}\bigg{[}\Big{(}f^{t,\mu}_{h}(s_{h},a_{h},b_{h})-(\mathcal{T}^{\mu,\nu^{t}}_{h}f^{t,\mu}_{h+1})(s_{h},a_{h},b_{h})\Big{)}^{2}\bigg{]}\leq\mathcal{O}(\beta),$
(22)
$\displaystyle(b)\quad\sum_{k=1}^{t-1}\Big{(}f^{t,\mu}_{h}(s_{h}^{k},a_{h}^{k},b_{h}^{k})-(\mathcal{T}^{\mu,\nu^{t}}_{h}f^{t,\mu}_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})\Big{)}^{2}\leq\mathcal{O}(\beta).$
(23)

###### Proof.

See Appendix D.2. ∎

Besides, using performance difference lemma we can easily bridge
$\overline{V}^{t}(\mu^{t})-V_{1}^{\pi^{t}}(s_{1})$ with Bellman residuals,
whose proof is deferred to Appendix D.3:

######  Lemma 4.

For any $t\in[K]$, we have

$\displaystyle\overline{V}^{t}(\mu^{t})-V_{1}^{\pi^{t}}(s_{1})=\sum_{h=1}^{H}\mathbb{E}_{\pi^{t}}\big{[}(f^{t,\mu^{t}}_{h}-\mathcal{T}^{\mu^{t},\nu^{t}}_{h}f^{t,\mu^{t}}_{h+1})(s_{h},a_{h}.b_{h})\big{]}.$

Therefore, from Lemma 4 we can obtain

$\displaystyle\sum_{t=1}^{K}\overline{V}^{t}(\mu^{t})-V_{1}^{\pi^{t}}(s_{1})=\sum_{h=1}^{H}\sum_{t=1}^{K}\mathbb{E}_{\pi^{t}}\big{[}(f^{t,\mu^{t}}_{h}-\mathcal{T}^{\mu^{t},\nu^{t}}_{h}f^{t,\mu^{t}}_{h+1})(s_{h},a_{h},b_{h})\big{]}.$
(24)

Notice that in (24) we need to bound the Bellman residuals of
$f^{t,\mu^{t}}_{h}$ weighted by policy $\pi^{t}$. However, in Lemma 3, we can
only bound the Bellman residuals weighted by $\pi^{1:t-1}$. Fortunately, we
can utilize the inherent low BEE dimension to bridge these two values with the
help of the following technical lemma:

######  Lemma 5 ((Jin et al., 2021a, )).

Given a function class $\Phi$ defined on $\mathcal{X}$ with $\phi(x)\leq C$
for all $(\phi,x)\in\Phi\times\mathcal{X}$, and a family of probability
measures $\mathcal{Q}$ over $X$. Suppose sequence
$\\{\phi_{t}\\}_{t=1}^{K}\subset\Phi$ and
$\\{\rho_{t}\\}_{t=1}^{K}\subset\mathcal{Q}$ satisfy that for all $t\in[K]$,
$\sum_{k=1}^{t-1}(\mathbb{E}_{\rho_{k}}[\phi_{t}])^{2}\leq\beta$. Then for all
$t\in[K]$ and $w>0$,

$\displaystyle\sum_{k=1}^{t}|\mathbb{E}_{\rho_{k}}[\phi_{k}]|\leq\mathcal{O}\Big{(}\sqrt{\mathrm{dim}_{\mathrm{DE}}(\Phi,\mathcal{Q},w)\beta
t}+\min\\{t,\mathrm{dim}_{\mathrm{DE}}(\Phi,\mathcal{Q},w)\\}C+tw\Big{)}.$

Invoking Lemma 5 with $\mathcal{Q}=\mathcal{Q}^{1}_{h}$,
$\Phi=(I-\mathcal{T}^{\Pi,\Pi^{\prime}}_{h})\mathcal{F}$ and
$w=\sqrt{{1}/{K}}$, conditioning on the event (22) in Lemma 3 holds true, we
have

$\displaystyle\sum_{t=1}^{K}\mathbb{E}_{\pi^{t}}\big{[}(f^{t,\mu^{t}}_{h}-\mathcal{T}^{\mu^{t},\nu^{t}}_{h}f^{t,\mu^{t}}_{h+1})(s_{h},a_{h}.b_{h})\big{]}$
(25)
$\displaystyle\qquad\leq\mathcal{O}\bigg{(}\sqrt{V_{\max}^{2}K\mathrm{dim}_{\mathrm{BEE}}\Big{(}\mathcal{F},\sqrt{{1}/{K}},\Pi,\Pi^{\prime},\mathcal{Q}^{1}\Big{)}\log\left(\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(V_{\max}/K)KH|\Pi|/\delta\right)}\bigg{)}.$

Similarly, invoking Lemma 5 with $\mathcal{Q}=\mathcal{Q}^{2}_{h}$,
$\Phi=(I-\mathcal{T}^{\Pi,\Pi^{\prime}}_{h})\mathcal{F}$ and
$w=\sqrt{{1}/{K}}$, conditioning on the event (23) in Lemma 3 holds true, we
have with probability at least $1-\delta/4$,

$\displaystyle\sum_{t=1}^{K}\mathbb{E}_{\pi^{t}}\big{[}(f^{t,\mu^{t}}_{h}-\mathcal{T}^{\mu^{t},\nu^{t}}_{h}f^{t,\mu^{t}}_{h+1})(s_{h},a_{h}.b_{h})\big{]}$
$\displaystyle\qquad\leq\sum_{t=1}^{K}\Big{(}f^{t,\mu^{t}}_{h}(s_{h},a_{h},b_{h})-(\mathcal{T}^{\mu,\nu^{t}}_{h}f^{t,\mu^{t}}_{h+1})(s^{t}_{h},a^{t}_{h},b^{t}_{h})\Big{)}+\mathcal{O}(\sqrt{K\log(K/\delta)})$
$\displaystyle\qquad\leq\mathcal{O}\bigg{(}\sqrt{V_{\max}^{2}K\mathrm{dim}_{\mathrm{BEE}}\Big{(}\mathcal{F},\sqrt{{1}/{K}},\Pi,\Pi^{\prime},\mathcal{Q}^{2}\Big{)}\log(\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(V_{\max}/K)KH|\Pi|/\delta)}\bigg{)},$
(26)

where the first inequality comes from standard martingale difference
concentration. Therefore, combining (25) and (26),we have:

$\displaystyle\sum_{t=1}^{K}\mathbb{E}_{\pi^{t}}\big{[}(f^{t,\mu^{t}}_{h}-\mathcal{T}^{\mu^{t},\nu^{t}}_{h}f^{t,\mu^{t}}_{h+1})(s_{h},a_{h}.b_{h})\big{]}$
$\displaystyle\qquad\leq\mathcal{O}\bigg{(}\sqrt{V_{\max}^{2}K\mathrm{dim}_{\mathrm{BEE}}\Big{(}\mathcal{F},\sqrt{{1}/{K}},\Pi,\Pi^{\prime}\Big{)}\log(\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(V_{\max}/K)KH|\Pi|/\delta)}\bigg{)}.$

Substitute the above bounds into (24) and we have:

$\displaystyle\sum_{t=1}^{K}\overline{V}^{t}(\mu^{t})-V_{1}^{\pi^{t}}(s_{1})$
(27)
$\displaystyle\qquad\leq\mathcal{O}\bigg{(}HV_{\max}\sqrt{K\mathrm{dim}_{\mathrm{BEE}}\Big{(}\mathcal{F},\sqrt{{1}/{K}},\Pi,\Pi^{\prime}\Big{)}\log(\mathcal{N}_{\mathcal{F}\cup\mathcal{G}}(V_{\max}/K)KH|\Pi|/\delta)}\bigg{)}.$

Thus, in Step 2, we establish an upper bound on term (4) in (20). It remains
to bound term (2) and term (3), which is completed in the final step of the
proof.

###  7.3 Step 3: Bound the regret

Now we only need to bound the online learning error. Notice that $p^{t}$ is
updated using Hedge with reward $\overline{V}^{t}$. Since
$0\leq\overline{V}^{t}\leq V_{\max}$ and there are $|\Pi|$ policies, we have
from the online learning literature (Hazan et al.,, 2016) that

$\displaystyle\sum_{t=1}^{K}\overline{V}^{t}(\mu^{*})-\sum_{t=1}^{K}\langle\overline{V}^{t},p^{t}\rangle\leq
V_{\max}\sqrt{K\log|\Pi|}.$ (28)

In addition, suppose $\mathfrak{F}_{k}$ denotes the filtration induced by
$\\{\nu^{1}\\}\cup(\cup_{i=1}^{k}\\{\mu^{i},\mathcal{D}_{i},\nu^{i+1}\\})$.
Then we can observe that
$\langle\overline{V}^{t},p^{t}\rangle-\overline{V}^{t}(\mu^{t})\in\mathfrak{F}_{t}$.
In addition, we have $\overline{V}^{t}\in\mathfrak{F}_{t-1}$ since the
estimation of $\overline{V}^{t}$ only utilizes $\mathcal{D}_{1:t-1}$, which
implies

$\displaystyle\mathbb{E}[\langle\overline{V}^{t},p^{t}\rangle-\overline{V}^{t}(\mu^{t})|\mathfrak{F}_{t-1}]=0.$

Therefore $(3)$ is a martingale difference sequence and by Azuma-Hoeffding’s
inequality we have with probability at least $1-\delta/4$,

$\displaystyle\sum_{t=1}^{K}\langle\overline{V}^{t},p^{t}\rangle-\sum_{t=1}^{K}\overline{V}^{t}(\mu^{t})\leq\mathcal{O}(V_{\max}\sqrt{K\log(1/\delta)})$
(29)

Substituting (21), (27), (28), and (29) into (20) concludes our proof for
Theorem 1 in the oblivious setting.

Meanwhile, for the adaptive setting, we can simply repeat the above arguments.
The only difference is that now $\nu^{t}$ can depend on $\mathcal{D}_{1:t-1}$
and thus we need to introduce a union bound over $\Pi^{\prime}$ when proving
Lemma 2 and Lemma 3. This will incur an additional $\log|\Pi^{\prime}|$ in
$\beta$ and thus also in the regret bound. This concludes our proof.

##  8 Conclusion

We study decentralized policy learning in general-sum Markov games.
Specifically, we aim to establish a no-regret online learning algorithm for a
single agent based on its local information, in the presence of nonstationary
and possibly adversarial opponents. Focusing on the policy revealing setting
where the opponent’s previous policies are revealed to the agent, we propose a
novel algorithm that achieves sublinear regret in the context of general
function approximation. Moreover, when all the agents adopt this algorithm, we
prove that their mixture policy constitutes an approximate CCE of the Markov
game. We further demonstrate the efficacy of the proposed algorithm by
applying it to constrained and vector-valued MDPs, which can be formulated as
zero-sum Markov games with a fictitious opponent. Finally, while we consider
the policy revealing setting, establishing decentralized RL algorithm for
Markov games under weaker information structures seems an important future
direction.

## References

  * Anderson, (2008) Anderson, T. (2008).  The theory and practice of online learning.  Athabasca University Press.
  * Azar et al., (2017) Azar, M. G., Osband, I., and Munos, R. (2017).  Minimax regret bounds for reinforcement learning.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 263–272. JMLR. org.
  * Bai and Jin, (2020) Bai, Y. and Jin, C. (2020).  Provable self-play algorithms for competitive reinforcement learning.  In International conference on machine learning, pages 551–560. PMLR.
  * Bai et al., (2020) Bai, Y., Jin, C., and Yu, T. (2020).  Near-optimal reinforcement learning with self-play.  Advances in neural information processing systems, 33:2159–2170.
  * Berner et al., (2019) Berner, C., Brockman, G., Chan, B., Cheung, V., Dębiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., et al. (2019).  Dota 2 with large scale deep reinforcement learning.  arXiv preprint arXiv:1912.06680.
  * Blum and Monsour, (2007) Blum, A. and Monsour, Y. (2007).  Learning, regret minimization, and equilibria.
  * Brafman and Tennenholtz, (2002) Brafman, R. I. and Tennenholtz, M. (2002).  R-max-a general polynomial time algorithm for near-optimal reinforcement learning.  Journal of Machine Learning Research, 3(Oct):213–231.
  * Brambilla et al., (2013) Brambilla, M., Ferrante, E., Birattari, M., and Dorigo, M. (2013).  Swarm robotics: a review from the swarm engineering perspective.  Swarm Intelligence, 7(1):1–41.
  * Canese et al., (2021) Canese, L., Cardarilli, G. C., Di Nunzio, L., Fazzolari, R., Giardino, D., Re, M., and Spanò, S. (2021).  Multi-agent reinforcement learning: A review of challenges and applications.  Applied Sciences, 11(11):4948.
  * Daskalakis et al., (2011) Daskalakis, C., Deckelbaum, A., and Kim, A. (2011).  Near-optimal no-regret algorithms for zero-sum games.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235–254. SIAM.
  * Daskalakis et al., (2020) Daskalakis, C., Foster, D. J., and Golowich, N. (2020).  Independent policy gradient methods for competitive reinforcement learning.  Advances in neural information processing systems, 33:5527–5540.
  * Ding et al., (2022) Ding, D., Wei, C.-Y., Zhang, K., and Jovanović, M. R. (2022).  Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence.  arXiv preprint arXiv:2202.04129.
  * Ding et al., (2021) Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M. (2021).  Provably efficient safe exploration via primal-dual policy optimization.  In International Conference on Artificial Intelligence and Statistics, pages 3304–3312. PMLR.
  * Du et al., (2021) Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021).  Bilinear classes: A structural framework for provable generalization in rl.
  * Efroni et al., (2020) Efroni, Y., Mannor, S., and Pirotta, M. (2020).  Exploration-exploitation in constrained MDPs.  arXiv preprint arXiv:2003.02189.
  * Freund and Schapire, (1997) Freund, Y. and Schapire, R. E. (1997).  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139.
  * Fudenberg and Tirole, (1991) Fudenberg, D. and Tirole, J. (1991).  Game theory.  MIT press.
  * Gronauer and Diepold, (2022) Gronauer, S. and Diepold, K. (2022).  Multi-agent deep reinforcement learning: a survey.  Artificial Intelligence Review, 55(2):895–943.
  * Gupta et al., (2017) Gupta, J. K., Egorov, M., and Kochenderfer, M. (2017).  Cooperative multi-agent control using deep reinforcement learning.  In International conference on autonomous agents and multiagent systems, pages 66–83. Springer.
  * Hazan et al., (2016) Hazan, E. et al. (2016).  Introduction to online convex optimization.  Foundations and Trends® in Optimization, 2(3-4):157–325.
  * Hernandez-Leal et al., (2018) Hernandez-Leal, P., Kartal, B., and Taylor, M. E. (2018).  Is multiagent deep reinforcement learning the answer or the question? a brief survey.  learning, 21:22.
  * Hernandez-Leal et al., (2019) Hernandez-Leal, P., Kartal, B., and Taylor, M. E. (2019).  A survey and critique of multiagent deep reinforcement learning.  Autonomous Agents and Multi-Agent Systems, 33(6):750–797.
  * Huang et al., (2021) Huang, B., Lee, J. D., Wang, Z., and Yang, Z. (2021).  Towards general function approximation in zero-sum markov games.  arXiv preprint arXiv:2107.14702.
  * Jiang et al., (2017) Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017).  Contextual decision processes with low bellman rank are pac-learnable.  In International Conference on Machine Learning, volume 70, pages 1704–1713. PMLR.
  * (25) Jin, C., Liu, Q., and Miryoosefi, S. (2021a).  Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.  Advances in Neural Information Processing Systems, 34.
  * (26) Jin, C., Liu, Q., Wang, Y., and Yu, T. (2021b).  V-learning–a simple, efficient, decentralized algorithm for multiagent rl.  arXiv preprint arXiv:2110.14555.
  * (27) Jin, C., Liu, Q., and Yu, T. (2021c).  The power of exploiter: Provable multi-agent rl in large state spaces.  arXiv preprint arXiv:2106.03352.
  * Jin et al., (2020) Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020).  Provably efficient reinforcement learning with linear function approximation.  In Conference on Learning Theory, pages 2137–2143. PMLR.
  * Konda and Tsitsiklis, (1999) Konda, V. and Tsitsiklis, J. (1999).  Actor-critic algorithms.  Advances in neural information processing systems, 12.
  * Lattimore and Szepesvári, (2020) Lattimore, T. and Szepesvári, C. (2020).  Bandit algorithms.  Cambridge University Press.
  * LeCun et al., (2015) LeCun, Y., Bengio, Y., and Hinton, G. (2015).  Deep learning.  Nature, 521(7553):436–444.
  * Leonardos et al., (2021) Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. (2021).  Global convergence of multi-agent policy gradient in markov potential games.  arXiv preprint arXiv:2106.01969.
  * Liu et al., (2022) Liu, Q., Wang, Y., and Jin, C. (2022).  Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits.  arXiv preprint arXiv:2203.06803.
  * Liu et al., (2021) Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. (2021).  Learning policies with zero or bounded constraint violation for constrained mdps.  Advances in Neural Information Processing Systems, 34.
  * Mao et al., (2021) Mao, W., Yang, L. F., Zhang, K., and Başar, T. (2021).  On improving model-free algorithms for decentralized multi-agent reinforcement learning.
  * Miryoosefi et al., (2019) Miryoosefi, S., Brantley, K., Daume III, H., Dudik, M., and Schapire, R. E. (2019).  Reinforcement learning with convex constraints.  Advances in Neural Information Processing Systems, 32.
  * Miryoosefi and Jin, (2021) Miryoosefi, S. and Jin, C. (2021).  A simple reward-free approach to constrained reinforcement learning.  arXiv preprint arXiv:2107.05216.
  * Mnih et al., (2013) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. (2013).  Playing atari with deep reinforcement learning.  arXiv preprint arXiv:1312.5602.
  * Paternain et al., (2019) Paternain, S., Chamon, L., Calvo-Fullana, M., and Ribeiro, A. (2019).  Constrained reinforcement learning has zero duality gap.  Advances in Neural Information Processing Systems, 32.
  * Puterman, (1994) Puterman, M. L. (1994).  Markov decision processes: Discrete stochastic dynamic programming.
  * Rashid et al., (2018) Rashid, T., Samvelyan, M., Schroeder, C., Farquhar, G., Foerster, J., and Whiteson, S. (2018).  Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning.  In International Conference on Machine Learning, pages 4295–4304. PMLR.
  * Russo and Van Roy, (2013) Russo, D. and Van Roy, B. (2013).  Eluder dimension and the sample complexity of optimistic exploration.  Advances in Neural Information Processing Systems, 26.
  * Sayin et al., (2021) Sayin, M., Zhang, K., Leslie, D., Basar, T., and Ozdaglar, A. (2021).  Decentralized q-learning in zero-sum markov games.  Advances in Neural Information Processing Systems, 34.
  * Shalev-Shwartz et al., (2016) Shalev-Shwartz, S., Shammah, S., and Shashua, A. (2016).  Safe, multi-agent, reinforcement learning for autonomous driving.  arXiv preprint arXiv:1610.03295.
  * Silver et al., (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016).  Mastering the game of Go with deep neural networks and tree search.  nature, 529(7587):484–489.
  * Srinivas et al., (2009) Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. (2009).  Gaussian process optimization in the bandit setting: No regret and experimental design.  arXiv preprint arXiv:0912.3995.
  * Tian et al., (2021) Tian, Y., Wang, Y., Yu, T., and Sra, S. (2021).  Online learning in unknown markov games.  In International conference on machine learning, pages 10279–10288. PMLR.
  * Vinyals et al., (2019) Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. (2019).  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  Nature, 575(7782):350–354.
  * Wainwright, (2019) Wainwright, M. (2019).  High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press.
  * Wang et al., (2019) Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. (2019).  Optimism in reinforcement learning with generalized linear function approximation.  arXiv preprint arXiv:1912.04136.
  * Wei et al., (2017) Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. (2017).  Online reinforcement learning in stochastic games.  Advances in Neural Information Processing Systems, 30.
  * (52) Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. (2021a).  Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games.  In Conference on Learning Theory, pages 4259–4299. PMLR.
  * (53) Wei, H., Liu, X., and Ying, L. (2021b).  A provably-efficient model-free algorithm for constrained markov decision processes.  arXiv preprint arXiv:2106.01577.
  * Xie et al., (2020) Xie, Q., Chen, Y., Wang, Z., and Yang, Z. (2020).  Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium.  In Conference on learning theory, pages 3674–3682. PMLR.
  * Xie et al., (2021) Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021).  Bellman-consistent pessimism for offline reinforcement learning.  arXiv preprint arXiv:2106.06926.
  * Yu et al., (2021) Yu, T., Tian, Y., Zhang, J., and Sra, S. (2021).  Provably efficient algorithms for multi-objective competitive rl.  In International Conference on Machine Learning, pages 12167–12176. PMLR.
  * (57) Zhang, K., Yang, Z., and Başar, T. (2021a).  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  Handbook of Reinforcement Learning and Control, pages 321–384.
  * (58) Zhang, R., Ren, Z., and Li, N. (2021b).  Gradient play in multi-agent markov stochastic games: Stationary points and convergence.  arXiv e-prints, pages arXiv–2106.

##  Appendix A Proofs of Proposition 1

From the completeness assumption, we know that there exists
$g_{h}\in\mathcal{F}_{h}$ such that $g_{h}=\mathcal{T}^{\mu,\nu}_{h}f_{h+1}$,
which implies that

$\displaystyle
f_{h}-\mathcal{T}^{\mu,\nu}_{h}f_{h+1}\in\mathcal{F}_{h}-\mathcal{F}_{h},\forall
f\in\mathcal{F},\mu\in\Pi,\nu\in\Pi^{\prime}.$

In other words,
$(I-\mathcal{T}^{\Pi,\Pi^{\prime}}_{h})\mathcal{F}\subseteq\mathcal{F}_{h}-\mathcal{F}_{h}$.
Therefore, from the definition of
$\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\break\Pi,\Pi^{\prime})$ we
have

$\displaystyle\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})$
$\displaystyle\leq\mathrm{dim}_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime},\mathcal{Q}^{2})=\max_{h\in[H]}\mathrm{dim}_{\mathrm{DE}}((I-\mathcal{T}^{\Pi,\Pi^{\prime}}_{h})\mathcal{F},\mathcal{Q}^{2}_{h},\epsilon)$
$\displaystyle\leq\max_{h\in[H]}\mathrm{dim}_{\mathrm{DE}}((\mathcal{F}_{h}-\mathcal{F}_{h}),\mathcal{Q}^{2}_{h},\epsilon)=\max_{h\in[H]}\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon),$

where the last step comes from the definition of $\mathrm{dim}_{\mathrm{E}}$
and $\mathcal{Q}^{2}_{h}$ is the dirac distribution family. This concludes our
proof.

##  Appendix B Examples for Realizability, Generalized Completeness and
Covering Number

In this section we illustrate practical examples where realizability and
generalized completeness hold while the covering number is upper bounded at
the same time. More specifically, we will consider tabular MGs, linear MGs and
kernel MGs.

###  B.1 Tabular MGs

For tabular MGs, we let
$\mathcal{F}_{h}=\\{f|f:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\mapsto[0,V_{\max}]\\}$
and $\mathcal{G}_{h}=\mathcal{F}_{h}$ for all $h\in[H]$. Then it is obvious
that $Q^{\mu\times\nu}_{h}\in\mathcal{F}_{h}$ and
$\mathcal{T}^{\mu,\nu}f_{h+1}\in\mathcal{G}_{h}$ for any
$f\in\mathcal{F},h\in[H],\mu,\nu$, which implies that realizability and
generalized completeness are satisfied. In addition, notice that in this case
we have

$\displaystyle\log\mathcal{N}_{\mathcal{F}_{h}}(\epsilon)=\log\mathcal{N}_{\mathcal{G}_{h}}(\epsilon)\leq|\mathcal{S}||\mathcal{A}||\mathcal{B}|\log({V_{\max}}/{\epsilon}).$

This suggests that the size of $\mathcal{F}$ and $\mathcal{G}$ is also not too
large.

###  B.2 Linear MGs

In this subsection we consider linear MGs. Here we generalize the definition
of linear MDPs in classic MDPs (Jin et al.,, 2020) to Markov games:

######  Definition 9 (Linear MGs).

We say an MG is linear of dimension $d$ if for each $h\in[H]$, there exists a
feature mapping
$\phi_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\mapsto\mathbb{R}^{d}$
and $d$ unknown signed measures
$\psi_{h}=(\psi_{h}^{(1)},\cdots,\psi_{h}^{(d)})$ over $\mathcal{S}$ and an
unknown vector $\theta_{h}\in\mathbb{R}^{d}$ such that
$P_{h}(\cdot|s,a,b)=\phi_{h}(s,a,b)^{\top}\psi_{h}(\cdot)$ and
$r_{h}(s,a,b)=\phi_{h}(s,a,b)^{\top}\theta_{h}$ for all
$(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$.

Without loss of generality, we assume $\|\phi_{h}(s,a,b)\|\leq 1$ for all
$s\in\mathcal{S},a\in\mathcal{A},b\in\mathcal{B}$ and
$\|\psi_{h}(\mathcal{S})\|\leq\sqrt{d},\theta_{h}\leq\sqrt{d}$ for all $h$.
Let
$\mathcal{F}_{h}=\mathcal{G}_{h}=\\{\phi_{h}(\cdot)^{\top}w|w\in\mathbb{R}^{d},\|w\|\leq(H-h+1)\sqrt{d},0\leq\phi_{h}(\cdot)^{\top}w\leq
H-h+1\\}$.

#### Realizability.

We have for any $\mu,\nu$,

$\displaystyle Q^{\mu\times\nu}_{h}(s,a,b)$
$\displaystyle=r_{h}(s,a,b)+\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a,b)}[V^{\mu\times\nu}_{h+1}(s^{\prime})]$
$\displaystyle=\langle\phi_{h}(s,a,b),\theta_{h}\rangle+\bigg{\langle}\phi_{h}(s,a,b),\int_{\mathcal{S}}V^{\mu\times\nu}_{h+1}(s^{\prime})d\psi_{h}(s^{\prime})\bigg{\rangle}$
$\displaystyle=\bigg{\langle}\phi_{h}(s,a,b),\theta_{h}+\int_{\mathcal{S}}V^{\mu\times\nu}_{h+1}(s^{\prime})d\psi_{h}(s^{\prime})\bigg{\rangle}$
$\displaystyle=\langle\phi_{h}(s,a,b),w^{\mu\times\nu}_{h}\rangle,$

where
$w^{\mu\times\nu}_{h}=\theta_{h}+\int_{\mathcal{S}}V^{\mu\times\nu}_{h+1}(s^{\prime})d\psi_{h}(s^{\prime})$
and thus $\|w^{\mu\times\nu}_{h}\|\leq(H-h+1)\sqrt{d}$. Therefore,
$Q^{\mu\times\nu}_{h}\in\mathcal{F}_{h}$, which means that realizability
holds.

#### Generalized completeness.

For any $f_{h+1}\in\mathcal{F}_{h+1}$, we have

$\displaystyle\mathcal{T}^{\mu,\nu}f_{h+1}(s,a,b)$
$\displaystyle=r_{h}(s,a,b)+\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a,b)}[f_{h+1}(s^{\prime},\mu,\nu)]$
$\displaystyle=\bigg{\langle}\phi_{h}(s,a,b),\theta_{h}+\int_{\mathcal{S}}f_{h+1}(s^{\prime},\mu,\nu)d\psi_{h}(s^{\prime})\bigg{\rangle}.$

Since $\|f_{h+1}\|_{\infty}\leq H-h$, we have
$\|\theta_{h}+\int_{\mathcal{S}}f_{h+1}(s^{\prime},\mu,\nu)d\psi_{h}(s^{\prime})\|\leq(H-h+1)\sqrt{d}$,
which indicates $\mathcal{T}^{\mu,\nu}f_{h+1}\in\mathcal{G}_{h}$ and thus
generalized completeness is satisfied.

#### Covering number.

First notice that from the literature (Wainwright,, 2019), the covering number
of a $l_{2}$-norm ball can be bounded as
$\log\mathcal{N}_{\mathbb{B}((H-h+1)\sqrt{d})}(\epsilon)\leq
d\log({3H\sqrt{d}}/{\epsilon})$. Therefore, there exists
$\mathcal{W}\subset\mathbb{B}((H-h+1)\sqrt{d})$ where $\log|\mathcal{W}|\leq
d\log({3H\sqrt{d}}/{\epsilon})$ such that for any
$w\in\mathbb{B}((H-h+1)\sqrt{d})$, there exists $w^{\prime}\in\mathcal{W}$
satisfying $\|w^{\prime}-w\|\leq\epsilon$. Now let
$\mathcal{F}^{\prime}_{h}=\\{\phi_{h}(\cdot)^{\top}w|w\in\mathcal{W}\\}$. For
any $f_{h}\in\mathcal{F}_{h}$, suppose
$f_{h}(\cdot)=\phi_{h}(\cdot)^{\top}w_{f_{h}}$. Then we know there exists
$f^{\prime}_{h}(\cdot)=\phi_{h}(\cdot)^{\top}w^{\prime}_{f_{h}}\in\mathcal{F}^{\prime}_{h}$
where $\|w^{\prime}_{f_{h}}-w_{f_{h}}\|\leq\epsilon$, which implies

$\displaystyle|f_{h}(s,a,b)-f^{\prime}_{h}(s,a,b)|\leq\|\phi_{h}(s,a,b)\|\|w^{\prime}_{f_{h}}-w_{f_{h}}\|\leq\epsilon.$

Therefore
$\log\mathcal{N}_{\mathcal{F}_{h}}(\epsilon)\leq\log|\mathcal{F}^{\prime}_{h}|=\log|\mathcal{W}|\leq
d\log({3H\sqrt{d}}/{\epsilon})$.

###  B.3 Kernel MGs

In this subsection we show that kernel MGs also satisfy realizability and
generalized completeness naturally. In addition, when a kernel MG has a
bounded effective dimension, its covering number will also be bounded. First
we generalize the definition of kernel MDPs Jin et al., 2021a  to MGs as
follows.

######  Definition 10 (Kernel MGs).

In a kernel MDP, for each step $h\in[H]$, there exist feature mapping
$\phi_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\mapsto\mathcal{H}$ and
$\psi_{h}:\mathcal{S}\mapsto\mathcal{H}$ where $\mathcal{H}$ is a separable
Hilbert space such that
$P_{h}(s^{\prime}|s,a,b)=\langle\phi_{h}(s,a,b),\psi_{h}(s^{\prime})\rangle_{\mathcal{H}}$
for all
$s\in\mathcal{S},a\in\mathcal{A},b\in\mathcal{B},s^{\prime}\in\mathcal{S}$.
Besides, the reward function os linear in $\phi$, i.e.,
$r_{h}(s,a,b)=\langle\phi_{h}(s,a,b),\theta_{h}\rangle_{\mathcal{H}}$ for some
$\theta_{h}\in\mathcal{H}$. Moreover, a kernel MG satisfies the following
regularization conditions:

  * •

$\|\theta_{h}\|_{\mathcal{H}}\leq 1,\|\phi_{h}(s,a,b)\|_{\mathcal{H}}\leq 1$,
for all $s\in\mathcal{S},a\in\mathcal{A},b\in\mathcal{B},h\in[H]$.

  * •

$\|\sum_{s\in\mathcal{S}}V(s)\psi_{h}(s)\|_{\mathcal{H}}\leq 1$, for all
function $V:\mathcal{S}\mapsto[0,1],h\in[H]$.

######  Remark 6.

It can be observed that tabular and linear MGs are special cases of kernel
MGs. Therefore, the following discussion applies to tabular and linear MGs as
well.

Then we let
$\mathcal{F}_{h}=\mathcal{G}_{h}=\\{\phi_{h}(\cdot)^{\top}w|w\in\mathcal{B}_{\mathcal{H}}(H-h+1)\\}$
where $\mathcal{B}_{\mathcal{H}}(r)$ is a ball with radius $r$ in
$\mathcal{H}$. Following the same arguments in linear MGs, we can validate
that realizability and generalized completeness are satisfied in kernel MGs.

#### Covering number.

Before bounding the covering number of $\mathcal{F}_{h}$, we need introduce a
new measure to evaluate the complexity of a Hilbert space since $\mathcal{H}$
might be infinite dimensional. Here we use the effective dimension (Du et
al.,, 2021; Jin et al., 2021a, ), which is defined as follows:

######  Definition 11 ($\epsilon$-effective dimension of a set).

The $\epsilon$-effective dimension of a set $\mathcal{X}$ is the minimum
integer $d_{\mathrm{eff}}(\mathcal{X},\epsilon)=n$ such that

$\displaystyle\sup_{x_{1},\cdots,x_{n}\in\mathcal{X}}\frac{1}{n}\log\det\bigg{(}I+\frac{1}{\epsilon^{2}}\sum_{i=1}^{n}x_{i}x_{i}^{\top}\bigg{)}\leq
e^{-1}.$

######  Remark 7.

When $\mathcal{X}$ is finite dimensional, suppose its dimension is $d$. Then
its effective dimension can be upper bounded by
$\mathcal{O}\big{(}d\log\big{(}1+{R^{2}}/{\epsilon}\big{)}\big{)}$ where $R$
is the norm bound of $\mathcal{X}$ (Du et al.,, 2021). In addition, even when
$\mathcal{X}$ is infinite dimensional, if the eigenspectrum of the covariance
matrices concentrates in a low-dimension subspace, the effective dimension of
$\mathcal{X}$ can still be small (Srinivas et al.,, 2009).

We call a kernel MG is of effective dimension $d(\epsilon)$ if
$d_{\mathrm{eff}}(\mathcal{X}_{h},\epsilon)\leq d(\epsilon)$ for all $h$ and
$\epsilon$ where
$\mathcal{X}_{h}=\\{\phi_{h}(s,a,b):(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\\}$.
Then the following proposition shows that the covering number of
$\mathcal{F}_{h}$ is upper bounded by the effective dimension of the kernel
MG:

######  Proposition 2.

If the kernel MG has effective dimension $d(\epsilon)$, then

$\displaystyle\log\mathcal{N}_{\mathcal{F}_{h}}(\epsilon)\leq\mathcal{O}\big{(}d({\epsilon}/{2H})\log(1+{Hd({\epsilon}/{2H})}/{\epsilon})\big{)}.$

###### Proof.

Suppose $\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon)=n$. Then by the
definition of Eluder dimension, there exists a sequence
$\\{\phi_{i}\\}_{i=1}^{n}$ such that for any
$w_{1},w_{2}\in\mathbb{B}_{\mathcal{H}}(H-h+1),\phi\in\mathcal{X}_{h}$, if
$\sum_{i=1}^{n}(\langle\phi_{i},w_{1}-w_{2}\rangle)^{2}\leq\epsilon^{2}$, then
$|\langle\phi,w_{1}-w_{2}\rangle|\leq\epsilon$. Therefore, the covering number
of kernel MGs can be reduced to covering the projection of
$\mathbb{B}_{\mathcal{H}}(H-h+1)$ onto the space spanned by
$\\{\phi_{i}\\}_{i=1}^{n}$, whose dimension is at most $n$. From the
literature (Wainwright,, 2019), the covering number of such space is
$\mathcal{O}\left(n\log\left(1+{nH}/{\epsilon}\right)\right)$, which implies

$\displaystyle\log\mathcal{N}_{\mathcal{F}_{h}}(\epsilon)\leq\mathcal{O}\big{(}n\log(1+{nH}/{\epsilon})\big{)}.$

Finally, by the proof of Proposition 3, we know $n\leq d({\epsilon}/{2H})$,
which concludes the proof.

∎

##  Appendix C Examples for BEE Dimension

In this section we will show that kernel MGs (including tabular MGs and linear
MGs) and generalized linear complete models have low BEE dimensions.

###  C.1 Kernel MGs

Consider the kernel MG defined in Definition 10 and
$\mathcal{F}_{h}=\\{\phi_{h}(\cdot)^{\top}w|w\in\mathcal{B}_{\mathcal{H}}(H-h+1)\\}$,
then we have the following proposition showing that the BEE dimension of a
kernel MG is upper bounded by its effective dimension (Definition 11):

######  Proposition 3.

If the kernel MG has effective dimension $d(\epsilon)$, then for any policy
classes $\Pi$ and $\Pi^{\prime}$, we have
$d_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})\leq
d({\epsilon}/{2H})$.

###### Proof.

First in Appendix B we have showed that $\mathcal{F}$ satisfies completeness.
By Proposition 1, we have
$d_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})\leq\max_{h\in[H]}\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon)$.
Therefore we only need to bound
$\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon)$ for each $h\in[H]$.
Suppose
$\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon)=k>d({\epsilon}/{2H})$.
Then by the definition of Eluder dimension, there exists a sequence
$\phi_{1},\cdots,\phi_{k}$ and
$\\{w_{1,i}\\}_{i=1}^{k},\\{w_{2,i}\\}_{i=1}^{k}$ where
$\phi_{i}\in\mathcal{X}_{h}=\\{\phi_{h}(s,a,b):(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\\},w_{1,i},w_{2,i}\in\mathcal{B}_{\mathcal{H}}(H-h+1)$
for all $i$ such that for any $t\in[k]$:

$\displaystyle\sum_{i=1}^{t-1}(\langle\phi_{i},w_{1,t}-w_{2,t}\rangle)^{2}\leq(\epsilon^{\prime})^{2},$
(30)
$\displaystyle|\langle\phi_{t},w_{1,t}-w_{2,t}\rangle|\geq\epsilon^{\prime},$
(31)

where $\epsilon^{\prime}\geq\epsilon$. Let $\Sigma_{t}$ denote
$\sum_{i=1}^{t-1}\phi_{i}\phi_{i}^{\top}+\frac{\epsilon^{2}}{4H^{2}}\cdot I$.
Then we have for any $t\in[k]$

$\displaystyle\|w_{1,t}-w_{2,t}\|_{\Sigma_{t}}^{2}\leq(\epsilon^{\prime})^{2}+\epsilon^{2}.$

On the other hand, by Cauchy-Schwartz inequality we know

$\displaystyle\|\phi_{t}\|_{\Sigma_{t}^{-1}}\|w_{1,t}-w_{2,t}\|_{\Sigma_{t}}\geq|\langle\phi_{t},w_{1,t}-w_{2,t}\rangle|\geq\epsilon^{\prime}.$

This implies for all $t\in[k]$

$\displaystyle\|\phi_{t}\|_{\Sigma_{t}^{-1}}\geq\frac{\epsilon^{\prime}}{\sqrt{\epsilon^{2}+(\epsilon^{\prime})^{2}}}\geq\frac{1}{\sqrt{2}}.$

Therefore, applying elliptical potential lemma (e.g., Lemma 5.6 and Lemma F.3
in Du et al., (2021)), we have for any $t\in[k]$

$\displaystyle\log\det\bigg{(}I+\frac{4H^{2}}{\epsilon^{2}}\sum_{i=1}^{t}\phi_{i}\phi_{i}^{\top}\bigg{)}=\sum_{i=1}^{t}\log(1+\|\phi_{i}\|_{\Sigma_{i}^{-1}}^{2})\geq
t\cdot\log\frac{3}{2}.$

However, by the definition of effective dimension, we know when
$n=d_{\mathrm{eff}}(\mathcal{X}_{h},\frac{\epsilon}{2H})$,

$\displaystyle\sup_{\phi_{1},\cdots,\phi_{n}}\log\det\bigg{(}I+\frac{4H^{2}}{\epsilon^{2}}\sum_{i=1}^{n}\phi_{i}\phi_{i}^{\top}\bigg{)}\leq
ne^{-1}.$

This is a contradiction since $n\leq d({\epsilon}/{2H})<k$ and
$\log\frac{3}{2}>e^{-1}$. Therefore we have
$\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon)\leq d({\epsilon}/{2H})$
for all $h\in[H]$, which implies

$\displaystyle d_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})\leq
d({\epsilon}/{2H}).$

This concludes our proof. ∎

#### Tabular MGs.

Tabular MGs are a special case of kernel MGs where the feature vectors are
$|\mathcal{S}||\mathcal{A}||\mathcal{B}|$-dimensional one-hot vectors. From
the standard elliptical potential lemma, we know
$d(\epsilon)=\widetilde{\mathcal{O}}(|\mathcal{S}||\mathcal{A}||\mathcal{B}|)$
for tabular MDPs, suggesting their BEE dimension is also upper bounded
$\widetilde{\mathcal{O}}(|\mathcal{S}||\mathcal{A}||\mathcal{B}|)$.

#### Linear MGs.

When the feature vectors are $d$-dimensional, we can recover linear MGs.
Similarly, by the standard elliptical potential lemma, we have the BEE
dimension of linear MGs is upper bounded $\widetilde{\mathcal{O}}(d)$.

###  C.2 Generalized Linear Complete Models

An important variant of linear MDPs is the generalized linear complete models
proposed by Wang et al., (2019). Here we also generalize it into Markov games:

######  Definition 12 (Generalized linear complete models).

In $d$-dimensional generalized linear complete models, for each step
$h\in[H]$, there exists a feature mapping
$\phi_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\mapsto\mathbb{R}^{d}$
and a link function $\sigma$ such that:

  * •

for the generalized linear function class
$\mathcal{F}_{h}=\\{\sigma(\phi_{h}(\cdot)^{\top}w)|w\in\mathcal{W}\\}$ where
$\mathcal{W}\subset\mathbb{R}^{d}$, realizability and completeness are both
satisfied;

  * •

the link function is strictly monotone, i.e., there exist
$0<c_{1}<c_{2}<\infty$ such that $\sigma^{\prime}\in[c_{1},c_{2}]$.

  * •

$\phi_{h},w$ satisfy the regularization conditions: $\|\phi_{h}(s,a,b)\|\leq
R,\|w\|\leq R$ for all $s,a,b,h$ where $R>0$ is a constant.

When the link function is $\sigma(x)=x$, the generalized linear complete
models reduce to the linear complete models, which contain instances such as
linear MGs and LQRs. The following proposition shows that generalized linear
complete models also have low BEE dimensions:

######  Proposition 4.

If a generalized linear complete model has dimension $d$, then for any policy
classes $\Pi$ and $\Pi^{\prime}$, its BEE dimension can be bounded as follows:

$\displaystyle
d_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})\leq\widetilde{\mathcal{O}}(d{c_{2}^{2}}/{c_{1}^{2}}).$

###### Proof.

The proof is similar to Proposition 3, except (30) and (31) become

$\displaystyle\sum_{i=1}^{t-1}c_{1}^{2}(\langle\phi_{i},w_{1,t}-w_{2,t}\rangle)^{2}\leq\sum_{i=1}^{t-1}(\sigma(\phi_{i}^{\top}w_{1,t})-\sigma(\phi_{i}^{\top}w_{2,t}))^{2}\leq(\epsilon^{\prime})^{2},$
$\displaystyle
c_{2}|\langle\phi_{t},w_{1,t}-w_{2,t}\rangle|\geq|\sigma(\phi_{t}^{\top}w_{1,t})-\sigma(\phi_{t}^{\top}w_{2,t})|\geq\epsilon^{\prime}.$

Then repeat the arguments in the proof of Proposition 3, we have
$\mathrm{dim}_{\mathrm{E}}(\mathcal{F}_{h},\epsilon)\leq\widetilde{\mathcal{O}}(d{c_{2}^{2}}/{c_{1}^{2}})$
for all $h\in[H]$. Since $\mathcal{F}$ satisfies completeness, we can use
Proposition 1 and obtain

$\displaystyle
d_{\mathrm{BEE}}(\mathcal{F},\epsilon,\Pi,\Pi^{\prime})\leq\widetilde{\mathcal{O}}(d{c_{2}^{2}}/{c_{1}^{2}}).$

∎

##  Appendix D Proofs of Lemmas in Section 7

###  D.1 Proof of Lemma 2

Let $\mathcal{V}_{\rho}$ be a $\rho$-cover of $\mathcal{G}$ with respect to
$\|\cdot\|_{\infty}$. Consider an arbitrary fixed tuple
$(\mu,t,h,g)\in\Pi\times[K]\times[H]\times\mathcal{G}$. Define
$W_{t,k}(h,g,\mu)$ as follows:

$\displaystyle W_{t,k}(h,g,\mu):=$
$\displaystyle(g_{h}(s^{k}_{h},a^{k}_{h},b_{h}^{k})-r_{h}^{k}-Q^{\mu,\nu^{t}}_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}$
$\displaystyle-(Q^{\mu,\nu^{t}}_{h}(s_{h}^{k},a_{h}^{k},b_{h}^{k})-r_{h}^{k}-Q^{\mu,\nu^{t}}_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2},$

and $\mathfrak{F}_{k,h}$ be the filtration induced by
$\\{\nu^{1},\cdots,\nu^{K}\\}\cup\\{s^{i}_{1},a^{i}_{1},b^{i}_{1},r^{i}_{1},\cdots,s^{i}_{H+1}\\}_{i=1}^{k-1}\cup\break\\{s^{k}_{1},a^{k}_{1},b^{k}_{1},r^{k}_{1},\cdots,s^{k}_{h},a^{k}_{h},b^{k}_{h}\\}$.
Then we have for all $k\leq t-1$,

$\displaystyle\mathbb{E}[W_{t,k}(h,g,\mu)|\mathfrak{F}_{k,h}]=[(g_{h}-Q^{\mu,\nu^{t}}_{h})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2},$

and

$\displaystyle\text{Var}[W_{t,k}(h,g,\mu)|\mathfrak{F}_{k,h}]\leq
4V_{\max}^{2}\mathbb{E}[W_{t,k}(h,g,\mu)|\mathfrak{F}_{k,h}].$

By Freedman’s inequality, with probability at least $1-\delta/4$, we have

$\displaystyle\bigg{|}\sum_{k=1}^{t-1}W_{t,k}(h,g,\mu)-\sum_{k=1}^{t-1}[(g_{h}-Q^{\mu,\nu^{t}}_{h})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}\bigg{|}$
$\displaystyle\leq\
\mathcal{O}\Bigg{(}V_{\max}\sqrt{\log\frac{1}{\delta}\cdot\sum_{k=1}^{t-1}[(g_{h}-Q^{\mu,\nu^{t}}_{h})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}}+V_{\max}^{2}\log\frac{1}{\delta}\Bigg{)}.$

By taking union bound over $\Pi\times[K]\times[H]\times\mathcal{V}_{\rho}$ and
the non-negativity of
$\sum_{k=1}^{t-1}[(g_{h}-Q^{\mu,\nu^{t}}_{h})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}$,
we have with probability at least $1-\delta/4$, for all
$(\mu,k,h,g)\in\Pi\times[K]\times[H]\times\mathcal{V}_{\rho}$,

$-\sum_{k=1}^{t-1}W_{t,k}(h,g,\mu)\leq\mathcal{O}(V_{\max}^{2}\iota),$

where $\iota=\log({HK|\mathcal{V}_{\rho}||\Pi|}/{\delta})$. This implies for
all $(\mu,t,h,g)\in\Pi\times[K]\times[H]\times\mathcal{G}$,

$\displaystyle\sum_{k=1}^{t-1}(Q^{\mu,\nu^{t}}_{h}(s_{h}^{k},a_{h}^{k},b_{h}^{k})-r_{h}^{k}-Q^{\mu,\nu^{t}}_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}$
$\displaystyle\qquad\leq\sum_{k=1}^{t-1}(g_{h}(s^{k}_{h},a^{k}_{h},b_{h}^{k})-r_{h}^{k}-Q^{\mu,\nu^{t}}_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}+\mathcal{O}(V_{\max}^{2}\iota+V_{\max}t\rho).$

Choose $\rho=V_{\max}/K$ and we know that with probability at least $1-\delta$
for all $\mu\in\Pi$ and $t\in[K]$,
$Q^{\mu,\nu^{t}}\in\mathcal{B}_{\mathcal{D}_{1:t-1}}(\mu,\nu^{t})$. This
concludes our proof.

###  D.2 Proof of Lemma 3

Let $\mathcal{Z}_{\rho}$ be a $\rho$-cover of $\mathcal{F}$ with respect to
$\|\cdot\|_{\infty}$. Consider an arbitrary fixed tuple
$(\mu,t,h,f)\in\Pi\times[K]\times[H]\times\mathcal{F}$. Let

$\displaystyle X_{t,k}(h,f,\mu):=$
$\displaystyle(f_{h}(s^{k}_{h},a^{k}_{h},b_{h}^{k})-r_{h}^{k}-f_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}$
$\displaystyle-((\mathcal{T}^{\mu,\nu^{t}}_{h}f_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})-r_{h}^{k}-f_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2},$

and $\mathfrak{F}_{k,h}$ be the filtration induced by
$\\{\nu^{1},\cdots,\nu^{K}\\}\cup\\{s^{i}_{1},a^{i}_{1},b^{i}_{1},r^{i}_{1},\cdots,s^{i}_{H+1}\\}_{i=1}^{k-1}\cup\break\\{s^{k}_{1},a^{k}_{1},b^{k}_{1},r^{k}_{1},\cdots,s^{k}_{h},a^{k}_{h},b^{k}_{h}\\}$.
Then we have for all $k\leq t-1$,

$\displaystyle\mathbb{E}[X_{t,k}(h,f,\mu)|\mathfrak{F}_{k,h}]=[(f_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}f_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2},$

and

$\displaystyle\text{Var}[X_{t,k}(h,f,\mu)|\mathfrak{F}_{k,h}]\leq
4V_{\max}^{2}\mathbb{E}[X_{t,k}(h,f,\mu)|\mathfrak{F}_{k,h}].$

By Freedman’s inequality, with probability at least $1-\delta$,

$\displaystyle\bigg{|}\sum_{k=1}^{t-1}X_{t,k}(h,f,\mu)-\sum_{k=1}^{t-1}[(f_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}f_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}\bigg{|}$
$\displaystyle\qquad\leq\
\mathcal{O}\Bigg{(}V_{\max}\sqrt{\log\frac{1}{\delta}\cdot\sum_{k=1}^{t-1}[(f_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}f_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}}+V_{\max}^{2}\log\frac{1}{\delta}\Bigg{)}.$

By taking union bound over $\Pi\times[K]\times[H]\times\mathcal{Z}_{\rho}$, we
have with probability at least $1-\delta$, for all
$(\mu,t,h,f)\in\Pi\times[K]\times[H]\times\mathcal{Z}_{\rho}$,

$\displaystyle\bigg{|}\sum_{k=1}^{t-1}X_{t,k}(h,f,\mu)-\sum_{k=1}^{t-1}[(f_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}f_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}\bigg{|}$
$\displaystyle\qquad\leq\
\mathcal{O}\Bigg{(}V_{\max}\sqrt{\iota\cdot\sum_{k=1}^{t-1}[(f_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}f_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}}+V_{\max}^{2}\iota\Bigg{)}.$
(32)

where $\iota=\log({HK|\mathcal{Z}_{\rho}||\Pi|}/{\delta})$.

Conditioned on the above event being true, we consider an arbitrary pair
$(h,t,\mu)\in[H]\times[K]\times\Pi$. By the definition of
$\mathcal{B}_{\mathcal{D}_{1:t-1}}(\mu,\nu^{t})$ and Assumption 2, we have:

$\displaystyle\sum_{k=1}^{t-1}X_{t,k}(h,f^{t,\mu},\mu)=$
$\displaystyle\sum_{k=1}^{t-1}(f_{h}(s^{k}_{h},a^{k}_{h},b_{h}^{k})-r_{h}^{k}-f_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}$
$\displaystyle-((\mathcal{T}^{\mu,\nu^{t}}_{h}f_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})-r_{h}^{k}-f_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{t-1}(f_{h}(s^{k}_{h},a^{k}_{h},b_{h}^{k})-r_{h}^{k}-f_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}$
$\displaystyle-\inf_{g\in\mathcal{G}}(g_{h}(s_{h}^{k},a_{h}^{k},b_{h}^{k})-r_{h}^{k}-f_{h+1}(s^{k}_{h+1},\mu,\nu^{t}))^{2}$
$\displaystyle\leq$ $\displaystyle\beta.$

Let
$l^{t,\mu}=\arg\min_{l\in\mathcal{Z}_{\rho}}\max_{h\in[H]}\|f^{t,\mu}_{h}-l^{t,\mu}_{h}\|_{\infty}$.
By the definition of $\mathcal{Z}_{\rho}$, we have

$\displaystyle\sum_{k=1}^{t-1}X_{t,k}(h,l^{t,\mu},\mu)\leq\mathcal{O}(V_{\max}t\rho+\beta).$
(33)

By (32), we know:

$\displaystyle\bigg{|}\sum_{k=1}^{t-1}X_{t,k}(h,l^{t,\mu},\mu)-\sum_{k=1}^{t-1}[(l^{t,\mu}_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}l^{t,\mu}_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}\bigg{|}$
$\displaystyle\qquad\leq\
\mathcal{O}\Bigg{(}V_{\max}\sqrt{\iota\cdot\sum_{k=1}^{t-1}[(l^{t,\mu}_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}l^{t,\mu}_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}}+V_{\max}^{2}\iota\Bigg{)}.$
(34)

Combining (33) and (34), we obtain

$\displaystyle\sum_{k=1}^{t-1}[(l^{t,\mu}_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}l^{t,\mu}_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}\leq\mathcal{O}(V_{\max}^{2}\iota+V_{\max}t\rho+\beta).$

This implies that

$\displaystyle\sum_{k=1}^{t-1}[(f^{t,\mu}_{h}-\mathcal{T}^{\mu,\nu^{t}}_{h}f^{t,\mu}_{h+1})(s_{h}^{k},a_{h}^{k},b_{h}^{k})]^{2}\leq\mathcal{O}(V_{\max}^{2}\iota+V_{\max}t\rho+\beta).$

Choose $\rho=V_{\max}/K$ and we can obtain (b). For (a), simply let
$\mathfrak{F}_{k,h}$ be the filtration induced by
$\\{\nu^{1},\cdots,\nu^{K}\\}\cup\\{\mu^{i},s^{i}_{1},a^{i}_{1},b^{i}_{1},r^{i}_{1},\cdots,s^{i}_{H+1}\\}_{i=1}^{k-1}\cup\mu^{k}$
and repeat the above arguments, which concludes our proof.

###  D.3 Proof of Lemma 4

First notice that
$\overline{V}^{t}(\mu^{t})=f^{t,\mu^{t}}_{1}(s_{1},\mu^{t},\nu^{t})$.
Therefore, we have

$\displaystyle\overline{V}^{t}(\mu^{t})-V^{\pi^{t}}_{1}(s_{1})=\mathbb{E}_{a_{1}\sim\mu^{t}(\cdot|s_{1}),b_{1}\sim\nu^{t}(\cdot|s_{1})}[f^{t,\mu^{t}}_{1}(s_{1},a_{1},b_{1})-Q^{\pi^{t}}_{1}(s_{1},a_{1},b_{1})]$
$\displaystyle\qquad=\mathbb{E}_{a_{1}\sim\mu^{t}(\cdot|s_{1}),b_{1}\sim\nu^{t}(\cdot|s_{1})}\big{[}\mathbb{E}_{s_{2}\sim
P_{1}(\cdot|s_{1},a_{1},b_{1})}[f^{t,\mu^{t}}_{2}(s_{2},\mu^{t},\nu^{t})]-\mathbb{E}_{s_{2}\sim
P_{1}(\cdot|s_{1},a_{1},b_{1})}[V^{\pi^{t}}_{2}(s_{2})]\big{]}$
$\displaystyle\qquad\quad+\mathbb{E}_{a_{1}\sim\mu^{t}(\cdot|s_{1}),b_{1}\sim\nu^{t}(\cdot|s_{1})}[(f^{t,\mu^{t}}_{1}-\mathcal{T}^{\mu^{t},\nu^{t}}_{1}f_{2}^{t,\mu^{t}})(s_{1},a_{1},b_{1})]$
$\displaystyle\qquad=\mathbb{E}_{s_{2}\sim\pi^{t}}[f^{t,\mu^{t}}_{2}(s_{2},\mu^{t},\nu^{t})-V^{\pi^{t}}_{2}(s_{2})]+\mathbb{E}_{\pi^{t}}[(f^{t,\mu^{t}}_{1}-\mathcal{T}^{\mu^{t},\nu^{t}}_{1}f_{2}^{t,\mu^{t}})(s_{1},a_{1},b_{1})].$

Repeat the above procedures and we can obtain Lemma 4. This concludes our
proof.

##  Appendix E Proof of Corollary 1

From Theorem 2, we have with probability at least $1-{\delta}$, for all
$i\in[n]$

$\displaystyle\max_{\mu_{i}\in\Pi_{i}}\frac{1}{K}\sum_{t=1}^{K}V_{1,i}^{\mu_{i}\times\mu_{-i}^{t}}(s_{1})\leq\frac{1}{K}\sum_{t=1}^{K}V_{1,i}^{\mu_{i}^{t}\times\mu_{-i}^{t}}(s_{1})+{\epsilon}.$

By the definition of $\widehat{\pi}$, this is equivalent to

$\displaystyle\max_{\mu_{i}\in\Pi_{i}}V_{1,i}^{\mu_{i}\times\widehat{\mu}_{-i}}(s_{1})\leq
V_{1,i}^{\widehat{\pi}}(s_{1})+{\epsilon},$

where $\widehat{\mu}_{-i}$ is uniformly sampled from
$\\{\mu^{t}_{-i}\\}_{t=1}^{K}$ and thus is the marginal distribution of
$\widehat{\pi}$ over the agents other than $i$. Therefore, by the definition
of CCE in (2), $\widehat{\pi}$ is $\epsilon$-approximate CCE with probability
at least $1-\delta$, which concludes our proof.

##  Appendix F Proof of Theorem 3

In this section we present the proof for Theorem 3. Our proof mainly consists
of four steps:

  * •

Prove $\overline{V}^{t}_{r}(\mu)$ and $\overline{V}^{t}_{g}(\mu)$ are
optimistic estimations of $V_{r,1}^{\mu}(s_{1})$ and $V_{g,1}^{\mu}(s_{1})$
for all $t\in[K]$ and $\mu\in\Pi$.

  * •

Bound the total estimation error
$\sum_{t=1}^{K}\overline{V}^{t}_{r}(\mu^{t})-V_{r,1}^{\mu^{t}}(s_{1})$ and
$\sum_{t=1}^{K}\overline{V}^{t}_{g}(\mu^{t})-V_{g,1}^{\mu^{t}}(s_{1})$.

  * •

Bound the regret by decomposing it into estimation error and online learning
error induced by Hedge.

  * •

Bound the constraint violation by strong duality.

#### Step 1: Prove optimism.

First we can show that the constructed set
$\mathcal{B}_{\mathcal{D}^{r}_{1:t-1}}(\mu)$
($\mathcal{B}_{\mathcal{D}^{g}_{1:t-1}}(\mu)$) is not vacuous in the sense
that the true action-value function $Q_{r}^{\mu}$ ($Q_{g}^{\mu}$) belongs to
it with high probability:

######  Lemma 6.

With probability at least $1-{\delta}/{4}$, we have for all $t\in[K]$ and
$\mu\in\Pi$,

$\displaystyle
Q_{r}^{\mu}\in\mathcal{B}_{\mathcal{D}^{r}_{1:t-1}}(\mu),Q_{g}^{\mu}\in\mathcal{B}_{\mathcal{D}^{g}_{1:t-1}}(\mu).$

###### Proof.

The proof is almost the same as Lemma 2 and thus is omitted here. ∎

Then since