# Socially Fair Reinforcement Learning

Debmalya Mandal
Max Planck Institute for Software Systems
<EMAIL_ADDRESS>
Jiarui Gan
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of episodic reinforcement learning where there are
multiple stakeholders with different reward functions. Our goal is to output a
policy that is socially fair with respect to different reward functions. Prior
works have proposed different objectives that a fair policy must optimize
including minimum welfare, and generalized Gini welfare. We first take an
axiomatic view of the problem, and propose four axioms that any such fair
objective must satisfy. We show that the Nash social welfare is the unique
objective that uniquely satisfies all four objectives, whereas prior
objectives fail to satisfy all four axioms. We then consider the learning
version of the problem where the underlying model i.e. Markov decision process
is unknown. We consider the problem of minimizing regret with respect to the
fair policies maximizing three different fair objectives – minimum welfare,
generalized Gini welfare, and Nash social welfare. Based on optimistic
planning, we propose a generic learning algorithm and derive its regret bound
with respect to the three different policies. For the objective of Nash social
welfare, we also derive a lower bound in regret that grows exponentially with
$n$, the number of agents. Finally, we show that for the objective of minimum
welfare, one can improve regret by a factor of $O(H)$ for a weaker notion of
regret.

##  1 Introduction

In recent years, reinforcement learning has been immensely successful in
various domains including game playing [Sil+17], and robotics [And+20]. These
breakthroughs have opened up new avenues for applying reinforcement learning
in real-world decision making systems like healthcare [Got+19], and finance
[Li+21]. However, such human-facing systems often include multiple
stakeholders with different preferences, and the classical goal of
maximization of rewards is no longer sufficient. A major design challenge is
the selection of right objective that provides certain fairness guarantees
across different agents.

Our first example comes from the use of reinforcement learning for vaccine
distribution [Mei+21]. In this context, the vulnerable population is in
immediate need, and their utilities should be prioritized. Similarly, multi-
armed bandit algorithms have been deployed for improving access to maternal
and child healthcare [Mat+22]. In this domain, researchers have found that
maximizing the minimum reward provides better fairness guarantees.

These examples suggest that in the context of multi-agent sequential decision
making, we should be careful about selecting the right measure. But what
should be the right measure? Besides maximizing minimum welfare discussed
above, researchers have proposed selecting a policy at the pareto frontier
[DCR18], or a policy maximizing generalized Gini social welfare [SWZ20]. In
this paper, we focus on the problem of selecting a measure that ensures
fairness in multi-agent sequential decision making. For the static setting,
this is a well-studied problem in economics [Mou04], and also in computational
social choice [Bra+16]. Motivated by the success of axiomatic framework in
these fields, we aim to layout a reasonable set of axioms for selecting a
fairness measure in dynamic multi-agent sequential decision making systems.

Even though a set of axioms might uniquely characterize a fairness measure,
the optimal policy according to this fairness measure is unknown. This is
because the underlying MDP is unknown, and we must interact with the
environment to learn such an optimal policy. Moreover, given the use of
different fairness measures in different contexts, can we come up with a
generic reinforcement learning algorithm that learns different fair optimal
policies? This is the second question we study in this paper, and in
particular, we consider the problem of minimizing regret with respect to
different fair optimal policies. Note that, this question is challenging since
most fairness measures are non-linear in value functions and dynamic
programming [Ber12] based learning algorithms cannot be applied.

###  1.1 Contributions

At a high level, we propose a set of axioms for selecting fairness measure in
multi-agent sequential decision making systems. Three natural fairness
measures are then analyzed against the proposed axioms. When the underlying
MDP is unknown, we propose a generic learning algorithm for minimizing regret
with respect to different fairness measures. In more detail, we make the
following contributions.

  * •

We consider the episodic reinforcement learning with multiple agents, and
propose a set of four axioms that any fairness measure should satisfy. We show
that these axioms uniquely characterize Nash social welfare ($\mathrm{NW}$),
whereas prior measures like minimum welfare ($\mathrm{MW}$) or generalized
Gini welfare ($\mathrm{GGW}$) violates some of them.

  * •

When the underlying model is unknown, we propose a generic learning algorithm
for minimizing regret with respect to the optimal fair according to a fairness
measure. For a setting with $n$ agents, $S$ states, $A$ actions, and horizon
length $H$, we instantiate this algorithm for different measures, and obtain
regret upper bounds of $\widetilde{O}(nH^{n+1}S\sqrt{AT})$ for the objective
of Nash social welfare, and $\widetilde{O}(H^{2}S\sqrt{AT})$ for both the
minimum welfare, and generalized Gini welfare.

  * •

For the objective of Nash social welfare, we derive a lower bound in regret
that scales exponentially with $n$, whereas for the other two measures lower
bound immediately follows from lower bound in regret for single-agent setting.
Finally, for the objective of minimum welfare, we show that one can improve
regret by a factor of $O(H)$ for a weaker notion of regret.

###  1.2 Related Work

Our work is related to several lines of research.

Fairness in Multi-Agent Systems. Our work falls under the framework of
fairness in multi-agent sequential decision-making [ZS14, JL19]. In a multi-
agent MDP model, [ZS14] propose to solve for a regularized maximin policy,
where the regularizer offers a trade-off between utilitarian and max-min fair
solution. [JL19], on the other hand, selects a policy in the pareto frontier.
Recently, several papers have proposed to use generalized Gini welfare
($\mathrm{GGW}$) [SWZ20, Zim+21] as a metric for selecting policies in multi-
agent MDP.

Nash Welfare in Bandits. Beyond learning in Markov decision processes, our
paper is closely related to [HMS21] who consider the objective of Nash social
welfare in multi-armed bandit and achieve $\widetilde{O}(\sqrt{T})$ regret.
Note that, our regret upper bound also becomes $\widetilde{O}(\sqrt{T})$ if
horizon length $H=1$, and number of states $S=1$. Additionally, there is no
need to generalize the classical axioms of [KN79] in a setting with a single
state. [Bar+22] also consider regret with respect to the Nash social welfare
objective. However, they consider a setting where an agent arrives each round,
and the goal is to maximize the Nash welfare (i.e. geometric mean of the
rewards) over the $T$ rounds. Beyond Nash welfare, several papers [Bis+20,
Pat+21] have also studied other notions of fairness in multi-armed bandits.

Fairness in Reinforcement Learning. Our work is related to fairness in online
learning [Jos+16, Jos+16a, Liu+17] and reinforcement learning [Jab+17]. In
contrast to our setting, these papers mainly define fairness with respect to
the arms and stipulates that arms of lower quality should not be selected over
arms of higher quality. Subsequent papers have considered group fairness in
online learning [Hua+20, Sch+19, WBT21]. with metrics like demographic parity.
These notions of fairness are different than ours and we refer the reader to
the recent survey [Gaj+22] for more details.

Episodic Reinforcement Learning. The classic paper of [AJO08] introduced the
UCRL algorithm and studied regret minimization in average reward MDP setting.
Our main learning algorithm is based on the optimistic planning approach of
UCRL algorithm. In the context of episodic reinforcement learning [AOM17]
obtained the minimax optimal regret bound. Subsequent papers have considered
other versions of episodic RL including changing reward function [Jin+20,
RM19], and changing transition function [Jin+18, JL20].

| Axioms | Regret
---|---|---
| PO | ANON | IIAN | CON | Upper Bound | Lower Bound
Nash Social Welfare | Y | Y | Y | Y | $\widetilde{O}\left(nH^{n+1}S\sqrt{AT}\right)$ | $\Omega\left(n\left(\frac{H}{2}\right)^{n}\sqrt{SAT}\right)$
Minimum Welfare | N | Y | N | Y | $\widetilde{O}\left(H^{2}S\sqrt{AT}\right)$ | $\Omega\left(\sqrt{HSAT}\right)$
Generalized Gini Welfare | Y | Y | N | Y | $\widetilde{O}\left(H^{2}S\sqrt{AT}\right)$ | $\Omega\left(\sqrt{HSAT}\right)$
Figure 1: Comparison between different fairness measures for reinforcement
learning. Measure $\mathrm{NW}$ is the unique fairness measure (up to a
monotone transformation) satisfying all four axioms. The regret for
$\mathrm{NW}$ scales exponentially with $n$, whereas for the other measure it
is independent of $n$.

##  2 Preliminaries

We consider the episodic reinforcement learning problem with multiple reward
functions. Before describing the general setting, we begin with the single-
agent episodie reinforcement learning. We are given an MDP
$\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\rho)$ with $S$ states and $A$
actions i.e. $\left|\mathcal{S}\right|=S$ and $\left|\mathcal{A}\right|=A$.
The initial state $s_{1}$ is drawn from a distribution $\rho$. We will write
$s_{h}$ (resp. $a_{h}$) to denote the state visited (resp. action taken) at
time-step $h$. For $h=1,\ldots,H-1$ the next state $s_{h+1}\sim
P(\cdot|s_{h},a_{h})$. The goal is to maximize the expected sum of rewards
over the $H$ steps i.e. $\mathbb{E}\left[\sum_{h=1}^{H}r(s_{h},a_{h})\mid
s_{1}\sim\rho\right]$.

In this paper, we consider a setting with $n$ different reward functions
$\mathbf{r}=\\{r_{i}\\}_{i\in[n]}$ corresponding to $n$ different agents. We
will assume $r_{i}(s,a)\in[0,1]$ for all $i$ and state,action pair $s,a$.
Given a policy $\pi$, we can define the value function corresponding to the
$i$-th reward function as follows.

$V^{\pi}(\rho;r_{i})=\mathbb{E}_{\pi}\left[\sum_{h=1}^{H}r_{i}(s_{h},a_{h})\mid
s_{1}\sim\rho\right]$ (1)

Often the starting state distribution $\rho$ will be clear from the context
and we will simply write $V^{\pi}(r_{i})$ instead of $V^{\pi}(\rho;r_{i})$.
Note that we are considering an episodic reinforcement learning setup, so the
policy $\pi$ need not be a stationary policy. We will write
$\pi=(\pi_{1},\ldots,\pi_{H})$ where $\pi_{h}$ is the (non-stationary) policy
used at time-step $h$. We will write $\Pi$ to denote the set of such non-
stationary policies.

Any policy $\pi$ affects different reward functions differently (e.g. through
value functions), and we want to build a measure to evaluate how fair the
policy $\pi$ is with respect to $n$ different reward functions. In particular,
a fairness measure $W$ maps a policy $\pi$ and a set of $n$ reward functions
to a real number i.e. $W:\Pi\times\mathbb{R}^{S\times A\times
n}\rightarrow\mathbb{R}$. Therefore, $W\left(\pi;\\{r_{i}\\}_{i\in[n]}\right)$
provides a way to evaluate the fairness of a policy $\pi$ and we want to
maximize the measure to find the optimal fair policy. The most basic measure
is the utilitarian measure which is the sum of values across the $n$ agents.
However, this measure violates basic axioms and we will consider the following
three measures of fairness.

#### Minimum Welfare.

We maximize the minimum value function across the $n$ agents.

$\textstyle\pi^{\star}_{\mathrm{MW}}\in\mathrm{argmax}_{\pi}\min_{i\in[n]}V^{\pi}\left(r_{i}\right).$

#### Generalized Gini Social Welfare (GGW).

This notion of fairness generalizes max-min fairness and has been considered
previously in the literature on multi-objective Markov decision processes
[SWZ20, Zim+21]. We are given a vector of weights $w\in\mathbb{R}^{n}$ so that
$w_{i}\geq 0$ for each $i$, $\sum_{i}w_{i}=1$, and $w_{1}\geq
w_{2}\geq\ldots\geq w_{n}$. Given a policy $\pi$, let $i_{1},\ldots,i_{n}$ be
an ordering of the agents so that $V^{\pi}(r_{i_{1}})\leq
V^{\pi}(r_{i_{2}})\leq\ldots\leq V^{\pi}(r_{i_{n}})$. We then maximize the
following objective:

$\textstyle\pi^{\star}_{\mathrm{GGW}}\in\mathrm{argmax}_{\pi}\sum_{j=1}^{n}w_{i}V^{\pi}(r_{i_{j}}).$

When $w_{1}=1$, the above objective coincides with minimum welfare.

#### Nash Social Welfare.

We maximize the product of the value functions of the $n$ agents, which is
known as the Nash social welfare.

$\textstyle\pi^{\star}_{\mathrm{NW}}\in\mathrm{argmax}_{\pi}\prod_{i=1}^{n}V^{\pi}(r_{i}).$

When the full MDP is known, a policy that maximizes each of the measures can
be computed by linear programming. The details can be found in the appendix.

Prior work on (multi-objective) fair reinforcement learning has mostly focused
on measures minimum welfare and generalized Gini welfare. In this work, we
want to emphasize the Nash social welfare as an alternative measure of
fairness because of its attractive axiomatic properties.

###  2.1 Axioms

We view the problem of solving a fair reinforcement learning problem as
maximization of a fairness measure $W$. Therefore, we propose four axioms that
any such fairness measure $W$ should satisfy. These axioms are inspired by
classical axioms in economics, particularly social choice theory [Sen18]. For
our setting, we build on the axiomatic framework developed by [KN79]. To
define the axioms we will need some additional notations.

  * •

Given a policy $\pi$ we will write $q^{\pi}$ to denote its state-action
occupancy measure, i.e.,

$q^{\pi}_{h}(s,a)=\operatorname{Pr}_{\pi}\left(s_{h}=s,a_{h}=a\right).$ (2)

  * •

Given an occupancy measure $q$ we will write $\pi^{q}$ to denote the
corresponding policy, i.e.,

$\pi^{q}_{h}(s,a)=\begin{cases}\frac{q_{h}(s,a)}{\sum_{b}q_{h}(s,b)}&\text{if
}\sum_{b}q_{h}(s,b)>0\\\ \frac{1}{A}&\text{otherwise}\end{cases}$

It is known that the occupancy measure of the policy $\pi^{q}$ is $q$.

  * •

Given two occupancy measures $q_{1}$ and $q_{2}$, we will write $\pi^{\alpha
q_{1}+(1-\alpha)q_{2}}$ to denote the policy corresponding to the convex
combination of the occupancy measures $q_{1}$ and $q_{2}$. In particular,
first we define the occupancy measure $q=\alpha q_{1}+(1-\alpha)q_{2}$ and
then take the policy $\pi^{q}$.

######  Axiom 1 (Pareto Optimality).

If $V^{\pi}(r_{i})\geq V^{\widetilde{\pi}}(r_{i})$ for all $i\in[n]$ and
$V^{\pi}(r_{j})>V^{\widetilde{\pi}}(r_{j})$ for some $j$, then it must be that

$W\left(\pi;\mathbf{r}\right)>W\left(\widetilde{\pi};\mathbf{r}\right).$

Namely, if policy $\pi$ pareto-improves policy $\widetilde{\pi}$, then $W$
must assign higher value to a policy $\pi$.

######  Axiom 2 (Independence of Irrelevant Alternatives with Neutrality).

Suppose that for all $i\in[n]$,

$\frac{V^{\pi_{1}}(r_{i})}{V^{\pi_{2}}(r_{i})}=\frac{V^{\widetilde{\pi}_{1}}(\widetilde{r}_{i})}{V^{\widetilde{\pi}_{2}}(\widetilde{r}_{i})}.$

Then $W\left(\pi_{1};\mathbf{r}\right)\geq W\left(\pi_{2};\mathbf{r}\right)$
if and only if $W\left(\widetilde{\pi}_{1};\widetilde{\mathbf{r}}\right)\geq
W\left(\widetilde{\pi}_{2};\widetilde{\mathbf{r}}\right)$.

Namely, if $\pi_{1}$ to $\pi_{2}$ is the same as $\widetilde{\pi}_{1}$ to
$\widetilde{\pi}_{2}$ to each agent in terms of value function, then
$W(\pi_{1})$ to $W(\pi_{2})$ is the same as $W(\widetilde{\pi}_{1})$ to
$W(\widetilde{\pi}_{2})$.

######  Axiom 3 (Anonymity).

For any permutation $\sigma:[n]\rightarrow[n]$ of the agents and policy $\pi$,
it must be that

$W\left(\pi;\mathbf{r}\right)=W\left(\pi;\\{r_{\sigma(i)}\\}_{i\in[n]}\right).$

Namely, $W$ is independent of the indices of the agents.

######  Axiom 4 (Continuity).

Suppose $W(\pi_{1};\mathbf{r})\geq W(\pi_{2};\mathbf{r})\geq
W(\pi_{3};\mathbf{r})$ and let $q_{j}=q^{\pi_{j}}$ for
$j\in\left\\{1,2,3\right\\}$. Then there exists $\alpha\in[0,1]$ such that

$W(\pi_{2};\mathbf{r})=W\left(\pi^{\alpha
q_{1}+(1-\alpha)q_{3}};\mathbf{r}\right).$

Namely, there is an intermediate policy between $\pi_{1}$ and $\pi_{3}$ that
attains the same value as $\pi_{2}$ under $W$. Note that, we don’t take direct
convex combination of policies, rather we take convex combination in the
occupancy measure. This is because the value function in an MDP is a non-
linear function of policy, and there might not exist a policy of the form
$\alpha\pi_{1}+(1-\alpha)\pi_{3}$ that achieves the same value as $\pi_{2}$.

##  3 Axiomatic Analysis

We investigate which of the above axioms are satisfied by different fairness
measures. First, we show that even though the axioms appear basic, not all of
them are satisfied by the fairness measures considered previously in the
literature. In fact, we can show that minimum welfare violates PO and IIAN,
whereas the measure generalized Gini welfare ($\mathrm{GGW}$) violates IIAN
under any choice of weight vector $w$.

#### Minimum Welfare Violates 1 (PO).

Consider a MDP with a single state and two actions $a$ and $b$. Agent $1$ has
the same reward for both the actions, say $1$. On the other hand, agent $2$
has reward $1$ for action $a$ and reward $2$ for action $b$. Consider a policy
$\pi_{a}$ that always pulls action $a$ in state $s$. Then
$V^{\pi_{a}}(r_{1})=V^{\pi_{a}}(r_{2})=H$. Now consider another policy
$\pi_{b}$ that always pulls action $b$ in state $s$. Then
$V^{\pi_{b}}(r_{1})=H$ and $V^{\pi_{b}}(r_{2})=2H$. Since the minimum value
function does not change we have
$\mathrm{MW}(\pi_{a})=\mathrm{MW}(\pi_{b})=H$.

#### Minimum Welare Violates 2 (IIAN).

We again consider a MDP with a single state and two actions $a$ and $b$. We
consider two reward functions $\mathbf{r}$ and $\widetilde{\mathbf{r}}$
defined as follows. For the first agent

$r_{1}(s,a)=\widetilde{r}_{1}(s,a)=1,\text{ and
}r_{1}(s,b)=\widetilde{r}_{1}(s,b)=0.$ (3)

On the other hand, for the second agent, we have

$r_{2}(s,a)=\frac{1}{4},r_{2}(s,b)=\frac{3}{4},\widetilde{r}_{2}(s,a)=1,\text{
and }\widetilde{r}_{2}(s,b)=3.$ (4)

Consider two policies: $\pi_{1}$ pulls $a$ or $b$ with equal probability,
whereas $\pi_{2}$ pulls $a$ with probability $3/4$ and $b$ with probability
$1/4$. For the first agent we then have,

$\textstyle
V^{\pi_{1}}(r_{1})=V^{{\pi_{1}}}(\widetilde{r}_{1})=\frac{H}{2},\text{ and
}V^{\pi_{2}}(r_{1})=V^{\pi_{2}}(\widetilde{r}_{1})=\frac{3H}{4}.$

For the second agent we have,

$\textstyle
V^{\pi_{1}}(r_{2})=\frac{H}{2},V^{\pi_{2}}(r_{2})=\frac{3H}{8},V^{{\pi_{1}}}(\widetilde{r}_{2})=2H,V^{\pi_{2}}(\widetilde{r}_{2})=\frac{3H}{2}.$

Therefore, we observe that the rewards and the policy satisfy the following
condition.

$\frac{V^{\pi_{1}}(r_{1})}{V^{\pi_{2}}(r_{1})}=\frac{V^{\pi_{1}}(\widetilde{r}_{1})}{V^{\pi_{2}}(\widetilde{r}_{1})}=\frac{2}{3}\
\textrm{ and
}\frac{V^{\pi_{1}}(r_{2})}{V^{\pi_{2}}(r_{2})}=\frac{V^{\pi_{1}}(\widetilde{r}_{2})}{V^{\pi_{2}}(\widetilde{r}_{2})}=\frac{4}{3}$

For the reward vector $\mathbf{r}$ we have
$\mathrm{MW}(\pi_{1};\mathbf{r})=\frac{H}{2}$ and
$\mathrm{MW}(\pi_{2};\mathbf{r})=\frac{3H}{8}$. On the other hand, for the
reward vector $\widetilde{\mathbf{r}}$ we have
$\mathrm{MW}(\pi_{1};\widetilde{\mathbf{r}})=\frac{H}{2}$ and
$\mathrm{MW}(\pi_{2};\widetilde{\mathbf{r}})=\frac{3H}{4}$. Therefore,
$\mathrm{MW}(\pi_{1};\mathbf{r})>\mathrm{MW}(\pi_{2};\mathbf{r})$ but
$\mathrm{MW}(\pi_{1};\widetilde{\mathbf{r}})<\mathrm{MW}(\pi_{2};\widetilde{\mathbf{r}})$.
This implies that the objective $\mathrm{MW}$ does not satisfy the
independence of irrelevant alternatives.

#### GGW Violates 2 (IIA).

We consider the same example as discussed for the setting of max-min fairness.
Consider a weight vector $\mathbf{w}=(w_{1},w_{2})$ where $w_{1}>w_{2}>0$ and
$w_{1}+w_{2}=1$. For the reward vector $\mathbf{r}$, we have

$\displaystyle\textstyle\mathrm{GGW}(\pi_{1},\mathbf{r})$
$\displaystyle=\frac{H}{2},$
$\displaystyle\textrm{and}\quad\mathrm{GGW}(\pi_{2},\mathbf{r})$
$\displaystyle=\frac{3H}{8}w_{1}+\frac{3H}{4}w_{2}=\frac{3H}{8}(1+w_{2}).$

For the reward vector $\widetilde{\mathbf{r}}$, we have

$\displaystyle\textstyle\mathrm{GGW}(\pi_{1};\widetilde{\mathbf{r}})$
$\displaystyle=\frac{H}{2}w_{1}+2Hw_{2},$
$\displaystyle\textrm{and}\quad\mathrm{GGW}(\pi_{2};\widetilde{\mathbf{r}})$
$\displaystyle=\frac{3H}{4}w_{1}+\frac{3H}{2}w_{2}.$

We now consider two cases. First, if $w_{2}<\frac{1}{3}$ we have
$\mathrm{GGW}(\pi_{1};\mathbf{r})>\mathrm{GGW}(\pi_{2};\mathbf{r})$ but
$\mathrm{GGW}(\pi_{1};\widetilde{\mathbf{r}})<\mathrm{GGW}(\pi_{2};\widetilde{\mathbf{r}})$.
On the other hand, if $w_{2}>\frac{1}{3}$ we have
$\mathrm{GGW}(\pi_{1};\mathbf{r})<\mathrm{GGW}(\pi_{2};\mathbf{r})$ but
$\mathrm{GGW}(\pi_{1};\widetilde{\mathbf{r}})>\mathrm{GGW}(\pi_{2};\widetilde{\mathbf{r}})$.

Now we consider the remaining case of $w_{2}=\frac{1}{3}$. We now consider a
different choice of reward functions than defined in equations (3) and (4).
Reward functions $r_{1}$ and $\widetilde{r}_{1}$ remain as they are, but we
change the definition of reward functions $r_{2}$ and $\widetilde{r_{2}}$ as
follows.

$r_{2}(s,a)=\frac{1}{2},r_{2}(s,b)=\frac{2}{3},\ \textrm{and}\
\widetilde{r}_{2}(s,a)=1,\widetilde{r}_{2}(s,b)=\frac{4}{3}$

Now it can be again checked that the required assumptions for axiom 2 is
satisfied. However, for the weight vector $(2/3,1/3)$ we have
$\mathrm{GGW}(\pi_{1};\mathbf{r})>\mathrm{GGW}(\pi_{2};\mathbf{r})$ but
$\mathrm{GGW}(\pi_{1};\widetilde{\mathbf{r}})<\mathrm{GGW}(\pi_{2};\widetilde{\mathbf{r}})$.
Therefore, we have shown that for any weight vector with $w_{1}>w_{2}>0$, one
can construct an instance where the fairness measure $\mathrm{GGW}$ violates
axiom IIA. Note that, the case of $w_{1}=1,w_{2}=0$ corresponds to minimum
welfare, and the construction can be generalized to more than two agents by
just duplicating the reward functions.

Apart from the above violations, the remaining axioms are satisfied by the
fairness measures minimum welfare, and the generalized Gini welfare. The
proofs are straightforward and are provided in the appendix.

###  3.1 Nash Social Welfare

We now turn to the fairness measure Nash social welfare. In the appendix, we
show that $\mathrm{NW}$ satisfies all four axioms. The main difference with
$\mathrm{GGW}$, and $\mathrm{MW}$ is the satisfaction of axiom IIA. Next we
state our first main result and show that up to a transformation by a
monotonically increasing function, $\mathrm{NW}$ is the unique fairness
measure that satisfies all four axioms.

######  Theorem 5.

Suppose there are at least four actions available at each state, and $W$ is a
fairness measure satisfying Axioms 1, 2, 3, and 4. Then it holds that
$W(\pi;\mathbf{r})=\phi\left(\mathrm{NW}(\pi;\mathbf{r})\right)$ for any
policy $\pi$, and reward function $\mathbf{r}$, where
$\phi:\mathbb{R}\rightarrow\mathbb{R}$ is some monotonically increasing
function.

The proof of Theorem 5 is provided in the appendix, and adapts main ideas from
[KN79] to the setting of episodic reinforcement learning.

  1. 1.

We first define an order $\succcurlyeq$ on $\mathbb{R}^{n}_{+}$ as
$x\succcurlyeq y$ if and only if $W(\pi^{a};\mathbf{r})\geq
W(\pi^{b};\mathbf{r})$. Here $\pi^{a}$ (resp. $\pi^{b}$) always plays action
$a$ (resp. $b$) and $\mathbf{r}$ is a reward function constructed using $x$
and $y$.

  2. 2.

Based on the function $W$, we then define a function
$F:\mathbb{R}^{n}_{+}\rightarrow\mathbb{R}$ that respects the order
$\succcurlyeq$. The construction of this function crucially depends on axiom
4.

  3. 3.

We then show the function $F$ satisfy some requirements so that we can invoke
a result due to [Osb76] and obtain that there exists a monotone increasing
function $G$ such that $F(x)=G\left(\prod_{i=1}^{n}x_{i}\right)$. This enables
us to show that $W$ is a monotone increasing transformation of $\mathrm{NW}$.

In addition to the above properties, the Nash social welfare also provides a
utility guarantee in comparison to the optimal max-min fair policy:
$\pi^{\star}_{\mathrm{NW}}$ provides any agent at least $1/n$ fraction of her
value under $\pi^{\star}_{\mathrm{MW}}$.

######  Theorem 6.

Suppose that the maximum $\mathrm{MW}$ social welfare is not zero.111When the
maximum $\mathrm{MW}$ social welfare is zero, for each policy $\pi$ there
exists an agent $i$ such that $V^{\pi}(r_{i})=0$, i.e., $\mathrm{NW}(\pi)=0$.
This implies that $\pi^{\star}_{\mathrm{NW}}$ is also a max-min fair
policy.Then for any agent $i\in[n]$, it holds that

$V^{\pi^{\star}_{\mathrm{NW}}}(r_{i})\geq\frac{1}{n}V^{\pi^{\star}_{\mathrm{MW}}}(r_{i}).$

Moreover, this bound is tight, i.e., for any $\delta>0$ there exists an
instance s.t.
$V^{\pi^{\star}_{\mathrm{NW}}}(r_{i})\leq\frac{1}{n}V^{\pi^{\star}_{\mathrm{MW}}}(r_{i})+\delta$
for some $i$.

The main idea to prove Theorem 6 is to show that the optimal policy
$\pi^{\star}_{\mathrm{NW}}$ can be computed by optimizing a log-concave
function over a convex set, and then use first order optimality conditions at
the optimal solution.222A similar relationship is known in the fair division
literature [Car+19], who showed a tight bound of $1/\sqrt{n}$, but their
setting and proof techniques are very different than ours. The details can be
found in the appendix.

##  4 Learning

We now consider the setting where the probability transition function $P$ is
unknown and the learner needs to learn $P$ in order to compute a fair policy.
The learner interacts with the environment over $T$ episodes. We will write
$\pi_{t}$ to denote the policy (possibly non-stationary) adopted by the
learner during episode $t$. We will also use $s_{t,h}$ to denote the state
visited at time-step $h$ of episode $t$, and $a_{t,h}$ to denote the action
taken at time-step $h$ of episode $t$. As is standard in the literature on
online reinforcement learning, we will assume that the reward functions are
known, but we show in the appendix how our algorithm and analysis can be
easily generalized to handle unknown reward functions. We next define the
regret of a learner that interacts with the world over $T$ episodes.

for  _$t=1,2,\ldots$_ do

/* Compute optimistic MDP $\widetilde{P}_{t}$ and the corresponding policy
$\widetilde{\pi}_{t}$ */

$\displaystyle\begin{array}[]{l}\widetilde{P}_{t}\leftarrow\mathrm{argmax}_{P\in
C_{t}(\widehat{P})}\max_{\pi}\mathbb{F}(\pi;P)\\\\[5.69054pt]
\widetilde{\pi}_{t}\in\mathrm{argmax}_{\pi}\mathbb{F}(\pi;\widetilde{P}_{t})\end{array}$
(7) for  _$h=1,\ldots,H$_ do

Observer state $s_{t,h}$.

Play $a_{t,h}\sim\widetilde{\pi}_{t,h}(\cdot|s_{t,h})$.

/* Update estimates of $P$ */

$N_{t}(s,a)=\sum_{t^{\prime}\leq
t}\sum_{h=1}^{H}\mathbbm{1}\left\\{s_{t,h}=s,a_{t,h}=a\right\\}$

$N_{t}(s,a,s^{\prime})=\sum_{t^{\prime}\leq
t}\sum_{h=1}^{H-1}\mathbbm{1}\left\\{s_{t,h}=s,a_{t,h}=a,s_{t,h+1}=s^{\prime}\right\\}$

for  _$s,a,s^{\prime}$_ do

$\widehat{P}(s,a,s^{\prime})=\frac{N_{t}(s,a,s^{\prime})}{N_{t}(s,a)}$.

Set $C_{t}(\widehat{P})=\left\\{P:\forall s\ \left\lVert
P(s,a,\cdot)-\widehat{P}(s,a,\cdot)\right\rVert_{1}\leq\sqrt{\frac{4S\log(SAt/\delta)}{\max\left\\{1,N_{t}(s,a)\right\\}}}\right\\}$

ALGORITHM 1 Upper Confidence Reinforcement Learning for Fair Objective
$\mathbb{F}$ (UCRL-$\mathbb{F}$)

#### Regret.

We define regret with respect to a generic fair objective
$\mathbb{F}\in\left\\{\mathrm{NW},\mathrm{GGW},\mathrm{MW}\right\\}$. For a
policy $\pi$ we will write $\mathbb{F}(\pi)$ to denote its value according to
the objective $\mathbb{F}$ e.g.
$\mathrm{NW}(\pi)=\prod_{i=1}^{n}V^{\pi}(\rho;r_{i})$. Let
$\pi^{\star}_{\mathbb{F}}$ be the policy that maximizes the objective
$\mathbb{F}$ i.e.
$\pi^{\star}_{\mathbb{F}}\in\mathrm{argmax}_{\pi}\mathbb{F}(\pi).$ Then we
measure regret of a learning algorithm $(\pi_{1},\ldots,\pi_{T})$ with respect
to this optimal fair policy.

$\textrm{Reg}_{\mathbb{F}}(T)=\sum_{t=1}^{T}\left(\mathbb{F}(\pi^{\star}_{\mathbb{F}})-\mathbb{F}(\pi_{t})\right)$
(8)

#### Algorithm.

Algorithm 1 presents our learning algorithm for a generic objective
$\mathbb{F}$. The algorithm is based on the principle of optimistic planning,
introduced by [AJO08]. The learner interacts with the environment over $T$
episodes each of length $H$. At the start of episode $t$, the learner first
computes the the optimistic model $\widetilde{P}_{t}$ and the optimistic
policy $\widetilde{\pi}_{t}$ (eq. 7). Then the learner plays policy
$\widetilde{\pi}_{t}$ for $H$ steps, and at the end of the episode, updates
the empirical probability transition function $\widehat{P}$.

#### Optimistic Planning.

The most important step of algorithm 1 is the computation of an optimistic
model and a policy (eq. 7). Here $\widetilde{P}_{t}$ is the probability
transition function that is plausible at time $t$ (i.e., lies within the
confidence ellipsoid $C_{t}(\widehat{P})$ centered around $\widehat{P}_{t}$)
and has the highest possible objective value according to the function
$\mathbb{F}$. For an arbitrary objective $\mathbb{F}$, it is not even clear
that this step can be performed efficiently. However, we show that for
objectives $\left\\{\mathrm{NW},\mathrm{GGW},\mathrm{MW}\right\\}$, one can
use the ellipsoid method to efficiently compute $\widetilde{P}_{t}$ and
$\widetilde{\pi}_{t}$. The details for the three objectives are provided in
the appendix. The next theorem bounds the regret of algorithm for the
objective of Nash social welfare ($\mathrm{NW}$).

######  Theorem 7.

For the objective of Nash social welfare, Algorithm 1 has regret

$\textrm{Reg}_{\mathrm{NW}}(T)=\widetilde{O}\left(nH^{n+1}S\sqrt{AT}\right).$

###### Proof sketch.

The proof of this theorem is provided in the appendix. Here we discuss the
main ideas behind the proof.

  1. 1.

We can apply Chernoff-Hoeffding inequality and the union bound to show that,
with high probability, the true probability transition function $P^{\star}$ is
contained within the confidence ellipsoid $C_{t}(\widehat{P})$ for all time
steps $t\in\left\\{1,2,\ldots,T\right\\}$ i.e. $P\left(\exists t\
P^{\star}\notin C_{t}(\widehat{P})\right)\leq\delta.$

  2. 2.

Conditioned on the event above, we show that the regret can be upper bounded
as
$\textrm{Reg}_{\mathrm{NW}}(T)\leq\sum_{t=1}^{T}\mathrm{NW}(\widetilde{\pi}_{t};\widetilde{P}_{t})-\mathrm{NW}(\widetilde{\pi}_{t};P^{\star})$.
This step uses the fact that $\widetilde{P}_{t}$ is the optimistic model and
$\widetilde{\pi}_{t}$ is the optimistic policy at time $t$.

  3. 3.

We can then bound the difference
$\mathrm{NW}(\widetilde{\pi}_{t};\widetilde{P}_{t})-\mathrm{NW}(\widetilde{\pi}_{t};P^{\star})$
in Nash welfare in terms of sum of difference in value functions. This gives
us the following upper bound on regret (see lemma 4 in the appendix).

$H^{n-1}\sum_{i=1}^{n}\underbrace{\sum_{t=1}^{T}\left|V^{\widetilde{\pi}_{t}}\left(r_{i};\widetilde{P}_{t}\right)-V^{\widetilde{\pi}_{t}}\left(r_{i};P^{\star}\right)\right|}_{:=\textrm{Reg}_{i}}$

This result can be thought of as a linearization lemma, and it generalizes
Lemma 2 by [HMS21] to the general setting of finite-horizon reinforcement
learning.

  4. 4.

Finally, we prove a bound of $\widetilde{O}\left(H^{2}S\sqrt{AT}\right)$ on
the term $\textrm{Reg}_{i}$ to complete the proof. ∎

We now consider the regret in learning the max-min fair policy. We instantiate
algorithm 1 with objective $\mathbb{F}=\mathrm{MW}$ and obtain a regret bound
of $\widetilde{O}(H^{2}S\sqrt{AT})$. Note that, unlike the objective of Nash
social welfare, the regret in this case doesn’t grow with the number of agents
$n$.

######  Theorem 8.

For the objective of minimum welfare, Algorithm 1 has regret

$\textrm{Reg}_{\mathrm{MW}}(T)=\widetilde{O}(H^{2}S\sqrt{AT}).$

###### Proof.

Proceeding similarly as the proof of Theorem 7 we can show that the regret can
be upper bounded by the regret with respect to the optimistic policies.

$\displaystyle\textrm{Reg}_{\mathrm{MW}}(T)$
$\displaystyle\leq\sum_{t=1}^{T}\min_{i}V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})-\min_{i}V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})$

We can bound the term $\min_{i}V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})$ as
follows.

$\displaystyle\min_{i}V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})$
$\displaystyle=\min_{i}\left\\{\left(V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})-V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})\right)+V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})\right\\}$
$\displaystyle\geq-\max_{i}\left|V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})-V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})\right|+\min_{i}V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})$

Substituting this bound gives us the following upper bound on
$\textrm{Reg}_{\mathrm{MW}}(T)$.

$\displaystyle\textrm{Reg}_{\mathrm{MW}}(T)\leq\sum_{t=1}^{T}\max_{i}\left|V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})-V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})\right|\leq\underbrace{\sum_{t=1}^{T}H^{2}\sqrt{\sum_{s^{\prime},b}\left\lVert\epsilon_{t}(s^{\prime},b,\cdot)\right\rVert_{1}^{2}}}_{:=\widetilde{\textrm{Reg}}}\quad\textrm{[By
Lemma~{}\ref{lem:diff-in-value}]}$

where
$\epsilon_{t}(s^{\prime},a,s)=\left|\widetilde{P}_{t}(s^{\prime},a,s)-P^{\star}(s^{\prime},a,s)\right|$.
The proof of Theorem 7 first upper bounds $\textrm{Reg}_{i}$ by
$\widetilde{\textrm{Reg}}$ for any $i$ and then bounds
$\widetilde{\textrm{Reg}}$ by $\widetilde{O}(H^{2}S\sqrt{AT})$. ∎

The next theorem upper bounds the regret for the objective of Generalized Gini
Social welfare.

######  Theorem 9.

For the objective of generalized Gini social welfare, Algorithm 1 has regret

$\textrm{Reg}_{\mathrm{GGW}}(T)=\widetilde{O}\left(H^{2}S\sqrt{AT}\right).$

###### Proof.

We proceed very similarly to the proof of Theorem 7. Since the true
probability transition function $P^{\star}$ is contained within
$C_{t}(\widehat{P})$ with high probability and algorithm 1 uses optimistic
planning, we can bound the regret as follows.

$\displaystyle\textrm{Reg}_{\mathrm{GGW}}(T)\leq\sum_{t=1}^{T}\mathrm{GGW}(\widetilde{\pi}_{t};\widetilde{P}_{t})-\mathrm{GGW}(\widetilde{\pi}_{t};P^{\star})$

We now consider two ordering of the agents. Let $i_{1},i_{2},\ldots,i_{n}$ be
an ordering of the agents so that

$V^{\widetilde{\pi}_{t}}(r_{i_{1}};\widetilde{P}_{t})\geq
V^{\widetilde{\pi}_{t}}(r_{i_{2}};\widetilde{P}_{t})\geq\ldots\geq
V^{\widetilde{\pi}_{t}}(r_{i_{n}};\widetilde{P}_{t}).$

Let $\ell_{1},\ell_{2},\ldots,\ell_{n}$ be an ordering of the agents so that

$V^{\widetilde{\pi}_{t}}(r_{\ell_{1}};P^{\star})\geq
V^{\widetilde{\pi}_{t}}(r_{\ell_{2}};P^{\star})\geq\ldots\geq
V^{\widetilde{\pi}_{t}}(r_{\ell_{n}};P^{\star}).$

Without loss of generality, we can assume that $i_{k}=k$ for all $k\in[n]$.
Then we can rewrite the upper bound on regret as follows:

$\displaystyle\textrm{Reg}_{\mathrm{GGW}}(T)\leq\sum_{t=1}^{T}\sum_{k=1}^{n}w_{k}\left(V^{\widetilde{\pi}_{t}}(r_{k};\widetilde{P}_{t})-V^{\widetilde{\pi}_{t}}(r_{\ell_{k}};P^{\star})\right).$

We can show that for all $k\in[n]$ it holds that

$V^{\widetilde{\pi}_{t}}(r_{k};\widetilde{P}_{t})-V^{\widetilde{\pi}_{t}}(r_{\ell_{k}};P^{\star})\leq\max_{i\in[n]}|V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})-V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})|.$
(9)

Indeed, if $V^{\widetilde{\pi}_{t}}(r_{k};\widetilde{P}_{t})\leq
V^{\widetilde{\pi}_{t}}(r_{\ell_{k}};P^{\star})$, then we are done, so we
assume that
$V^{\widetilde{\pi}_{t}}(r_{k};\widetilde{P}_{t})>V^{\widetilde{\pi}_{t}}(r_{\ell_{k}};P^{\star})$.

Note that there must be $j\geq k$ such that $\ell_{j}\leq k$. This is because
the converse, i.e., $\ell_{j}>k$ for all $j\geq k$, would imply that
$\ell_{j}=\ell_{j^{\prime}}$ for some $j\neq j^{\prime}$, which is a
contradiction. It then follows that

$\displaystyle
V^{\widetilde{\pi}_{t}}(r_{k};\widetilde{P}_{t})-V^{\widetilde{\pi}_{t}}(r_{\ell_{k}};P^{\star})\leq
V^{\widetilde{\pi}_{t}}(r_{\ell_{j}};\widetilde{P}_{t})-V^{\widetilde{\pi}_{t}}(r_{\ell_{j}};P^{\star})=|V^{\widetilde{\pi}_{t}}(r_{\ell_{j}};\widetilde{P}_{t})-V^{\widetilde{\pi}_{t}}(r_{\ell_{j}};P^{\star})|,$

so (9) follows.

Hence, we have

$\displaystyle\textrm{Reg}_{\mathrm{GGW}}(T)\leq\sum_{t=1}^{T}\max_{i}\left|V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})-V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})\right|$

and the remainder of the proof is the same as that of Theorem 8. ∎

###  4.1 Lower Bound on Regret

If all the $n$ agents have identical reward functions then regret in learning
minimum welfare ($\textrm{Reg}_{\mathrm{MW}}(T)$) just corresponds to regret
in learning a single reward function. Therefore,
$\textrm{Reg}_{\mathrm{MW}}(T)$ must be at least the regret in learning for
the single-agent setting which is $\Omega(\sqrt{HSAT})$ [AOM17]. Now, for the
generalized Gini welfare recall that the weights are normalized i.e.
$\sum_{k}w_{k}=1$. So, the regret in learning
($\textrm{Reg}_{\mathrm{GGW}}(T)$) again coincides with the regret in learning
for the single-agent setting and we have
$\textrm{Reg}_{\mathrm{GGW}}(T)\geq\Omega(\sqrt{HSAT})$.

We now consider the regret in learning for the Nash welfare objective. Note
that the upper bound in regret scales exponentially with $n$, the number of
agents. Intuitively this is expected as in an episodic reinforcement learning
setting, the Nash social welfare of $n$ agents scales as $H^{n}$. We now
provide a lower bound in regret $\textrm{Reg}_{\mathrm{NW}}(T)$ that also
scales exponentially with $n$.

######  Theorem 10.

Suppose $T\geq\Omega(\log H)$ and $H\geq\Omega(\log S)$. Then for any policy
$\pi$, there exists a MDP with $S$ states, and $A$ actions so that
$\mathbb{E}[\textrm{Reg}_{\mathrm{NW}}(\pi;T)]\geq
Cn\left(\frac{H}{2}\right)^{n}\sqrt{SAT}$ for some universal constant $C>0$.

Here we briefly highlight the main ideas of the proof. We use the same
instance used in the lower bound construction of average reward MDP [LS20,
AJO08], where there is a collection of $O(SA)$ MDPs. Each MDP has $S-2$ states
arranged in the form of an $A$-ary tree, and two other states – good state
$s_{g}$ (reward $1$) and bad state $s_{b}$ (reward $0$). Any action from the
leaves of this tree transition uniformly at random to the remaining two states
are good ($s_{g}$) and bad ($s_{b}$). However, on model $M_{\ell,a}$ we define

$\displaystyle\textstyle P(s_{g}|\ell,a)={1}/{2}+\Delta,\
P(s_{b}|\ell,a)={1}/{2}-\Delta.$

Now observe that on Model $M_{\ell,a}$ the optimal policy can navigate to leaf
$\ell$ and take action $a$. Moreover, the transition probabilities are
designed in such a way that once either the good or the bad state is reached,
it takes at least $\Theta(H)$ steps to leave that state. This means the
optimal policy achieves Nash welfare of at least $(1/2+\Delta)^{n}H^{n}$ per
episode. On the other hand, if the learning policy does not take action $a$ at
leaf node $\ell$, it achieves a Nash welfare of at most $(1/2)^{n}H^{n}$ that
episode. Therefore, the regret in these episodes is at least
$\left((1/2+\Delta)^{n}-(1/2)^{n}\right)H^{n}\geq n(H/2)^{n}$. Then the rest
of the proof shows that one can choose $\Delta$ small enough so that there
exists a model under which the number of such misses by the learning algorithm
is at least $O(T)$.

###  4.2 Improved Bound for Minimum Welfare

We now consider a weaker notion of regret for the fairness measure
$\mathrm{MW}$, minimum social welfare.

$\textrm{Reg}_{\mathrm{MW}}^{W}(T)=\sum_{t=1}^{T}\mathrm{MW}(\pi^{\star}_{\mathrm{MW}};\mathbf{r})-\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})$
(10)

The difference with the regret definition (8) is that for the second quantity
the order of minimum and summation is interchanged. Since value functions are
non-negative, sum of minimum welfare across $T$ episodes is upper bounded by
the minimum of the total welfare across $T$ episodes. This implies that
$\textrm{Reg}^{W}_{\mathrm{MW}}(T)\leq\textrm{Reg}_{\mathrm{MW}}(T)$, and we
show that it is possible to improve the bound for
$\textrm{Reg}^{W}_{\mathrm{MW}}(T)$.

Before deriving a regret bound with respect to the new definition, we first
argue that the new regret eq. 10 is perhaps more appropriate for our setting.
Since each of the $n$ agents interact with the learner for $T$ episodes, the
total utility received by agent $i$ is $\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})$.
Therefore, the minimum total welfare is
$\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})$. On the other hand, the optimal
minimum welfare achievable over $T$ episodes is

$\textstyle\max_{\pi\in\Pi}\min_{i}\sum_{t=1}^{T}V^{\pi}(r_{i})=T\max_{\pi\in\Pi}\min_{i}V^{\pi}(r_{i}).$

The difference between these two quantities is precisely the regret in eq. 10.

Algorithm 2 describes our new learning algorithm and is inspired by the dual
formulation of the problem of solving max-min fair policy.

$\displaystyle\begin{split}&\max_{v\in\mathbb{R},\ q\in\mathcal{Q}(\rho,P)}\
v\\\ \textrm{s.t.}&\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)\geq v\ \forall
i\in[n]\\\ \end{split}$ (11)

Here $q$ is the state-action occupancy measure (as defined in eq. 2) and the
constraint $q\in\mathcal{Q}(\rho,P)$ ensures that $q$ is valid with respect to
$P$. The Lagrangian of the optimization problem (11) is given as

$\displaystyle\mathcal{L}(q,v;\lambda)$
$\displaystyle=v+\sum_{i=1}^{n}\lambda_{i}\left(\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)-v\right)$

Suppose we know $v^{\star}$, the optimal solution to (11), i.e., the maxmin
value. Then substituting $v=v^{\star}$ we get the following expression for the
Lagrangian.

$\displaystyle\mathcal{L}(q;\lambda)$
$\displaystyle=v^{\star}+\sum_{i=1}^{n}\lambda_{i}\left(\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)-v^{\star}\right)$

Here we assume that $v^{\star}$ is known and it is an input to Algorithm 2. In
our full proof we show that it suffices to set $v^{\star}$ to an upper bound
of the maxmin value in Algorithm 2 (e.g., we can use an upper bound of the
rewards).

The Lagrangian can be interpreted as a two-player zero-sum game where the
learner (max-player) plays $q$ and the adversary (min-player) plays $\lambda$.
Algorithm 2 tries to find an equilibrium of this game by using a reinforcement
learning algorithm for the $q$-player and a bandit algorithm for the
$\lambda$-player. In order to see which RL algorithm is suitable let us first
rewrite the term $\mathcal{L}(q,\lambda)$ as

$\displaystyle\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)\left(\sum_{i}\lambda_{i}r_{i}(s,a)+\frac{v^{\star}}{H}(1-\sum_{i}\lambda_{i})\right)$

Therefore, we can define a new environment with rewards
$\widetilde{r}(s,a)=\sum_{i}\lambda_{i}r_{i}(s,a)+\frac{v^{\star}}{H}\left(1-\sum_{i}\lambda_{i}\right)$
and in the new environment the RL agent receives the expected reward
$\mathcal{L}(q,\lambda)$. We will fix the choice of $\lambda$ at the start of
an episode (say $\lambda^{t}$ at the start of episode $t$), and we also need
to fix the policy at the start of the episode. For this reason, we will be
using the UOB-REPS algorithm [Jin+20] which works with unknown transition, and
adversarial rewards, and has regret $O(HS\sqrt{AT})$.

The $\lambda$-player, on the other hand, chooses a point in the convex set
$\mathcal{C}=\left\\{\lambda\in\mathbb{R}^{n}_{+}:\sum_{i}\lambda_{i}\leq
B\right\\}$ at the start of each episode and receives an expected cost of
$\mathcal{L}(q,\lambda)$. As the cost function is linear in $\lambda$ we can
use any algorithm for linear bandit with adversarial reward. We will use the
OSMD algorithm proposed by [BCK12] which has regret ${O}(\sqrt{nT\log A})$.

Input: Maxmin value $v^{\star}$, number of episodes $T$, length of each
episode $H$.

Instantiate UOB-REPS with action set $\mathcal{A}$ and state space
$\mathcal{S}$.

Instantiate OSMD with action set
$\mathcal{C}=\left\\{\lambda\in\mathbb{R}^{n}_{+}:\sum_{i}\lambda_{i}\leq
B\right\\}$.

for  _$t=1,\ldots,T$_ do

$\pi^{t}\leftarrow$ policy chosen according to UOB-REPS.

$\lambda^{t}\leftarrow$ action chosen according to OSMD.

for  _$h=1,\ldots,H$_ do

Observe $x_{t,h}$.

Action $a_{t,h}=\pi^{t}(x_{t,h})$.

Reward feedback
$\widetilde{r}_{t,h}=\sum_{i}\lambda^{t}_{i}r_{i}(x_{t,h},a_{t,h})+\frac{v^{\star}}{H}\left(1-\sum_{i}\lambda^{t}_{i}\right)$.

Loss feedback to OSMD:
$v^{\star}+\sum_{i=1}^{n}\lambda^{t}_{i}\left(\sum_{h=1}^{H}r_{i}(x_{t,h},a_{t,h})-v^{\star}\right)$.

ALGORITHM 2 Lagrange-Maximin

######  Theorem 11.

For $n\leq\frac{S^{2}A}{\log A}$, algorithm 2 has regret

$\textrm{Reg}_{\mathrm{MW}}^{W}(T)=\widetilde{O}\left(HS\sqrt{AT}\right)$

The main idea is to show that the average occupancy measure
$\overline{q}=\frac{1}{T}\sum_{t}q^{t}$ and
$\overline{\lambda}=\frac{1}{T}\sum_{t}\lambda^{t}$ is an
$\epsilon$-approximate fixed point of the game $\mathcal{L}(h,q)$ for
$\epsilon=\widetilde{O}\left(B(HS\sqrt{A}+\sqrt{n\log A})/\sqrt{T}\right)$.
This lets us bound the constraint violation of $\overline{q}$ with respect to
the LP (11) and also bound regret $\textrm{Reg}^{W}_{\mathrm{MW}}(T)$. The
proof also shows that any choice of $v^{\star}$ larger than
$v^{\star}_{\mathrm{MW}}=\max_{\pi}\min_{i}V^{\pi}(r_{i})$ works, so one can
call algorithm 2 with $v^{\star}=H$. Additionally, the parameter $B$ needs to
be at least the maximum possible value of any reward function.

##  5 Conclusion

In this paper, we proposed a set of axioms for selecting fairness measure in
multi-agent sequential decision making systems. We analyzed three different
fairness measures ($\mathrm{NW},\mathrm{MW}$, and $\mathrm{GGW}$) against the
axioms. When the underlying MDP is unknown, we proposed a generic learning
algorithm for minimizing regret with respect to different fair optimal
policies. There are many interesting directions for future work. First, it
would be interesting to extend our framework to consider RL with general
function approximation. Our axioms should generalize easily, but the
computation of fair optimal policies might be challenging. Second, it would be
great to bridge the gap between the lower and upper bounds in regret (table
1). For single-agent RL, value iteration based methods achieve minimax regret
bounds. However, fairness measures are non-linear, and we might need to devise
different learning algorithms. Finally, it would also be interesting to
consider a setting where agents have partial information about the underlying
MDP [DCR18].

## References

  * [AJO08] Peter Auer, Thomas Jaksch and Ronald Ortner  “Near-optimal regret bounds for reinforcement learning”  In _Advances in neural information processing systems_ 21, 2008
  * [And+20] OpenAI: Marcin Andrychowicz et al.  “Learning dexterous in-hand manipulation”  In _The International Journal of Robotics Research_ 39.1 SAGE Publications Sage UK: London, England, 2020, pp. 3–20
  * [AOM17] Mohammad Gheshlaghi Azar, Ian Osband and Rémi Munos  “Minimax regret bounds for reinforcement learning”  In _International Conference on Machine Learning_ , 2017, pp. 263–272  PMLR
  * [Bar+22] Siddharth Barman, Arindam Khan, Arnab Maiti and Ayush Sawarni  “Fairness and Welfare Quantification for Regret in Multi-Armed Bandits”  In _arXiv preprint arXiv:2205.13930_ , 2022
  * [BCK12] Sébastien Bubeck, Nicolo Cesa-Bianchi and Sham M Kakade  “Towards minimax policies for online linear optimization with bandit feedback”  In _Conference on Learning Theory_ , 2012, pp. 41–1  JMLR WorkshopConference Proceedings
  * [Ber12] Dimitri Bertsekas  “Dynamic programming and optimal control: Volume I”  Athena scientific, 2012
  * [Bis+20] Ilai Bistritz, Tavor Baharav, Amir Leshem and Nicholas Bambos  “My fair bandit: Distributed learning of max-min fairness with multi-player bandits”  In _International Conference on Machine Learning_ , 2020, pp. 930–940  PMLR
  * [Bra+16] Felix Brandt et al.  “Handbook of computational social choice”  Cambridge University Press, 2016
  * [Bro11] Daniel G Brown  “How I wasted too long finding a concentration inequality for sums of geometric variables”, 2011
  * [Car+19] Ioannis Caragiannis et al.  “The unreasonable fairness of maximum Nash welfare”  In _ACM Transactions on Economics and Computation (TEAC)_ 7.3 ACM New York, NY, USA, 2019, pp. 1–32
  * [DCR18] Nishant Desai, Andrew Critch and Stuart J Russell  “Negotiable reinforcement learning for pareto optimal sequential decision-making”  In _Advances in Neural Information Processing Systems_ 31, 2018
  * [DP09] Devdatt P Dubhashi and Alessandro Panconesi  “Concentration of measure for the analysis of randomized algorithms”  Cambridge University Press, 2009
  * [Gaj+22] Pratik Gajane et al.  “Survey on Fair Reinforcement Learning: Theory and Practice”  In _arXiv preprint arXiv:2205.10032_ , 2022
  * [Got+19] Omer Gottesman et al.  “Guidelines for reinforcement learning in healthcare”  In _Nature medicine_ 25.1 Nature Publishing Group, 2019, pp. 16–18
  * [HMS21] Safwan Hossain, Evi Micha and Nisarg Shah  “Fair algorithms for multi-agent multi-armed bandits”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 24005–24017
  * [Hua+20] Wen Huang et al.  “Achieving user-side fairness in contextual bandits”  In _arXiv preprint arXiv:2010.12102_ , 2020
  * [Jab+17] Shahin Jabbari et al.  “Fairness in reinforcement learning”  In _International conference on machine learning_ , 2017, pp. 1617–1626  PMLR
  * [Jin+18] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck and Michael I Jordan  “Is Q-learning provably efficient?”  In _Advances in neural information processing systems_ 31, 2018
  * [Jin+20] Chi Jin et al.  “Learning adversarial Markov decision processes with bandit feedback and unknown transition”  In _International Conference on Machine Learning_ , 2020, pp. 4860–4869  PMLR
  * [JL19] Jiechuan Jiang and Zongqing Lu  “Learning fairness in multi-agent systems”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [JL20] Tiancheng Jin and Haipeng Luo  “Simultaneously learning stochastic and adversarial episodic mdps with known transition”  In _Advances in neural information processing systems_ 33, 2020, pp. 16557–16566
  * [Jos+16] Matthew Joseph, Michael Kearns, Jamie H Morgenstern and Aaron Roth  “Fairness in learning: Classic and contextual bandits”  In _Advances in neural information processing systems_ 29, 2016
  * [Jos+16a] Matthew Joseph et al.  “Fair algorithms for infinite and contextual bandits”  In _arXiv preprint arXiv:1610.09559_ , 2016
  * [KN79] Mamoru Kaneko and Kenjiro Nakamura  “The Nash social welfare function”  In _Econometrica: Journal of the Econometric Society_ JSTOR, 1979, pp. 423–435
  * [Li+21] Zechu Li et al.  “FinRL-Podracer: High performance and scalable deep reinforcement learning for quantitative finance”  In _Proceedings of the Second ACM International Conference on AI in Finance_ , 2021, pp. 1–9
  * [Liu+17] Yang Liu et al.  “Calibrated fairness in bandits”  In _arXiv preprint arXiv:1707.01875_ , 2017
  * [LS20] Tor Lattimore and Csaba Szepesvári  “Bandit algorithms”  Cambridge University Press, 2020
  * [Mat+22] Aditya Mate et al.  “Field study in deploying restless multi-armed bandits: Assisting non-profits in improving maternal and child health”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 36.11, 2022, pp. 12017–12025
  * [Mei+21] Eli Meirom, Haggai Maron, Shie Mannor and Gal Chechik  “Controlling graph dynamics with reinforcement learning and graph neural networks”  In _International Conference on Machine Learning_ , 2021, pp. 7565–7577  PMLR
  * [Mou04] Hervé Moulin  “Fair division and collective welfare”  MIT press, 2004
  * [Osb76] Dale K Osborne  “Irrelevant alternatives and social welfare”  In _Econometrica: Journal of the Econometric Society_ JSTOR, 1976, pp. 1001–1015
  * [Pat+21] Vishakha Patil, Ganesh Ghalme, Vineet Nair and Y Narahari  “Achieving Fairness in the Stochastic Multi-Armed Bandit Problem.”  In _J. Mach. Learn. Res._ 22, 2021, pp. 174–1
  * [RM19] Aviv Rosenberg and Yishay Mansour  “Online convex optimization in adversarial markov decision processes”  In _International Conference on Machine Learning_ , 2019, pp. 5478–5486  PMLR
  * [Sch+19] Candice Schumann, Zhi Lang, Nicholas Mattei and John P Dickerson  “Group fairness in bandit arm selection”  In _arXiv preprint arXiv:1912.03802_ , 2019
  * [Sen18] Amartya Sen  “Collective choice and social welfare”  Harvard University Press, 2018
  * [Sil+17] David Silver et al.  “Mastering the game of go without human knowledge”  In _nature_ 550.7676 Nature Publishing Group, 2017, pp. 354–359
  * [SWZ20] Umer Siddique, Paul Weng and Matthieu Zimmer  “Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards”  In _International Conference on Machine Learning_ , 2020, pp. 8905–8915  PMLR
  * [WBT21] Min Wen, Osbert Bastani and Ufuk Topcu  “Algorithms for fairness in sequential decision making”  In _International Conference on Artificial Intelligence and Statistics_ , 2021, pp. 1144–1152  PMLR
  * [Zim+21] Matthieu Zimmer, Claire Glanois, Umer Siddique and Paul Weng  “Learning fair policies in decentralized cooperative multi-agent reinforcement learning”  In _International Conference on Machine Learning_ , 2021, pp. 12967–12978  PMLR
  * [ZS14] Chongjie Zhang and Julie A Shah  “Fairness in multi-agent sequential decision-making”  In _Advances in Neural Information Processing Systems_ 27, 2014

##  Appendix A Computing Optimal Policies

We first recall the linear programming formulation of reinforcement learning.
Consider an MDP $\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\rho)$ and our goal
is to maximize value function with respect to the reward function $r$.

$\max_{\pi}V^{\pi}(\rho;r_{i})$

The primal linear program for this problem is the following.

$\displaystyle\min_{\\{V_{h}\\}_{h\in[H]}}$
$\displaystyle\sum_{s}\rho(s)V_{1}(s)$ s.t. $\displaystyle V_{h}(s)\geq
r(s,a)+\sum_{s^{\prime}}P(s,a,s^{\prime})V_{h+1}(s^{\prime})\ \forall
h\in[H-1]$

We will use the dual formulation of the above linear program.

$\displaystyle\begin{split}\max_{q}&\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r(s,a)\\\
\textrm{s.t.}&\sum_{a}q_{1}(s,a)=\rho(s)\ \forall s\\\
&\sum_{a}q_{h+1}(s,a)=\sum_{s^{\prime},a}q_{h}(s^{\prime},a)P(s^{\prime},a,s)\\\
&\qquad\qquad\ \forall s,\ \forall h\in[H-1]\\\ &q\geq 0\end{split}$ (12)

Here the variable $q_{h}(s,a)$ should be interpreted as the probability that
the policy visits state $s$ at time-step $h$ and takes action $a$. We will
refer to the variables
$\\{q_{h}(s,a)\\}_{a\in\mathcal{A},s\in\mathcal{S},h\in[H]}$ as a state-action
occupancy measure. Once we solve the LP 16, we can obtain the optimal policy
as

$\displaystyle\pi_{h}(a|s)=\left\\{\begin{array}[]{cc}\frac{q_{h}(s,a)}{\sum_{b}q_{h}(s,b)}&\textrm{
if }\sum_{b}q_{h}(s,b)>0\\\ \frac{1}{A}&\textrm{o.w.}\end{array}\right.$ (15)

Occupancy Measure Polytope: Given an initial state distribution $\rho$ and a
probability transition function $P$ we will write $\mathcal{Q}(\rho,P)$ to
denote the set of state-action occupancy measures satisfying the Bellman flow
conditions with respect to $\rho$ and $P$, i.e.

$\displaystyle\mathcal{Q}(\rho,P)=\left\\{q\geq 0:\sum_{a}q_{1}(s,a)=\rho(s)\
\forall s\
\textrm{and}\sum_{a}q_{h+1}(s,a)=\sum_{s^{\prime},a}q_{h}(s^{\prime},a)P(s^{\prime},a,s)\forall
s,\ \forall h\in[H-1]\right\\}$

#### Utilitarian.

We maximize the sum of value functions across the $n$ agents.

$\pi^{\star}_{\mathrm{UL}}\in\mathrm{argmax}_{\pi}\sum_{i}V^{\pi}(\rho;r_{i})$

We can solve optimization problem (12) with reward function $r=\sum_{i}r_{i}$
and obtain $q^{\star}_{\mathrm{UL}}$.

$\displaystyle\begin{split}q^{\star}_{\mathrm{UL}}\in&\mathrm{argmax}_{q}\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)\sum_{i}r_{i}(s,a)\\\
\textrm{s.t.}&\ q\in\mathcal{Q}(\rho,P)\end{split}$ (16)

Once we obtain $q^{\star}_{\mathrm{UL}}$ we can obtain the optimal utilitarian
policy $\pi^{\star}_{\mathrm{UL}}$ through eq. 15.

#### Max-Min Fair.

We maximize the worst value function across the $n$ agents.

$\pi^{\star}_{\mathrm{MW}}\in\mathrm{argmax}_{\pi}\min_{i\in[n]}V^{\pi}\left(\rho;r_{i}\right)$

The above optimization problem can also be solved through a linear program.

$\displaystyle\begin{split}\max_{q,t}\ &t\\\
\textrm{s.t.}&\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)\geq t\ \forall
i\in[n]\\\ &q\in\mathcal{Q}(\rho,P)\end{split}$ (17)

#### Nash Social Welfare.

We maximize the product of the value functions of the $n$ agents.

$\pi^{\star}_{\mathrm{NW}}\in\mathrm{argmax}_{\pi}\prod_{i=1}^{n}V^{\pi}(\rho;r_{i})$

The above optimization problem can be solved through a concave optimization
problem.

$\displaystyle\begin{split}\max_{q}&\sum_{i=1}^{n}\log\left(\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)\right)\\\
\textrm{s.t.}&\ q\in\mathcal{Q}(\rho,P)\end{split}$ (18)

#### Generalized Gini Social Welfare

(GGW): This notion of fairness generalizes max-min fairness and has been
considered previously in the literature on multi-objective Markov decision
processes [SWZ20, Zim+21]. We are given a vector of weights
$w\in\mathbb{R}^{n}$ so that $w_{i}\geq 0$ for each $i$, $\sum_{i}w_{i}=1$,
and $w_{1}\geq w_{2}\geq\ldots\geq w_{n}$. Given a policy $\pi$, let
$i_{1},\ldots,i_{n}$ be an ordering of the $n$ agents so that
$V^{\pi}(r_{i_{1}})\leq V^{\pi}(r_{i_{2}})\leq\ldots\leq V^{\pi}(r_{i_{n}})$.
Then we maximize the following objective

$\pi^{\star}_{\mathrm{GGW}}\in\mathrm{argmax}_{\pi}\sum_{j=1}^{n}w_{i}V^{\pi}(r_{i_{j}})$

The optimal GGW policy can also be computed through a linear program.

$\displaystyle\begin{split}\max_{q,t}\ &t\\\
\textrm{s.t.}&\sum_{i}w_{i}\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{\sigma(i)}(s,a)\geq
t\ \forall\sigma\in\mathcal{S}_{n}\\\ &q\in\mathcal{Q}(\rho,P)\end{split}$
(19)

Even though the linear program above has exponentially many constraints, one
can easily solve the LP using ellipsoid method. In order to apply the
ellipsoid method we just need to show that there exists an efficient
separation oracle. Given a candidate solution $q,t$ the bellman flow
constraints i.e. the last three constraints can be checked efficiently. Then
for each agent $i$ we compute
$V_{i}(q)=\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)$. Let
$i_{1},i_{2},\ldots,i_{n}$ be an ordering of the agents so that
$V_{i_{1}}(q)\geq V_{i_{2}}(q)\geq\ldots\geq V_{i_{n}}(q)$. Then we check if
$\sum_{j}w_{j}V_{i_{j}}(q)\geq t$ or not. If this constraint is violated then
we have a violating permutation $\sigma$ where $\sigma(j)=i_{j}$. On the other
hand, if this constraint is satisfied then all the other constraints are
satisfied since for any other permutation $\sigma$ we have
$\sum_{j}w_{j}V_{\sigma(j)}(q)\geq\sum_{j}w_{j}V_{i_{j}}(q)$. This is because
the weights are arranged in a non-increasing order.

##  Appendix B Proof of Theorem 6

The optimal policy according to Nash social welfare can be computed through
the following optimization problem.

$\displaystyle\max_{q}$
$\displaystyle\quad\prod_{i=1}^{n}\left(\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)\right)$
s.t. $\displaystyle\quad q\in\mathcal{Q}(\rho,P)$

Let $q^{\star}$ be the optimal solution of the above optimization problem. We
now consider two cases.

Case 1. $\mathrm{NW}(q^{\star})>0$: Since $q^{\star}$ is a stationary point
and the set $\mathcal{Q}(\rho,P)$ is convex, the first order stationarity
conditions gives us

$\nabla\mathrm{NW}(q^{\star})^{\top}(q-q^{\star})\leq 0\quad\forall
q\in\mathcal{Q}(\rho,P)$ (20)

The derivative of the Nash welfare objective with respect to $q_{h}(s,a)$ is
the following.

$\displaystyle\frac{\partial\mathrm{NW}(q)}{\partial q_{h}(s,a)}$
$\displaystyle=\sum_{i}\prod_{j\neq
i}\left(\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r_{i}(s,a)\right)r_{i}(s,a)=\mathrm{NW}(q)\sum_{i}\frac{r_{i}(s,a)}{V_{i}(q)}$

Then equation (20) gives us the following result.

$\displaystyle\mathrm{NW}(q^{\star})\sum_{i}\sum_{h,s,a}\frac{r_{i}(s,a)}{V_{i}(q^{\star})}\left(q_{h}(s,a)-q_{h}^{\star}(s,a)\right)\leq
0$ $\displaystyle\Rightarrow$
$\displaystyle\mathrm{NW}(q^{\star})\sum_{i}\frac{V_{i}(q)-V_{i}(q^{\star})}{V_{i}(q^{\star})}\leq
0$ $\displaystyle\Rightarrow$
$\displaystyle\sum_{i}\frac{V_{i}(q)}{V_{i}(q^{\star})}\leq n$

This immediately implies that $\max_{i}\frac{V_{i}(q)}{V_{i}(q^{\star})}\leq
n$.

Case 2. $\mathrm{NW}(q^{\star})=0$: This implies that for every policy $\pi$,
$V^{\pi}(r_{i})=0$ for some $i$. Hence, the minimum value of every policy
$\pi$ is zero and the MM social welfare is zero, contradicting the assumption
of the theorem.

#### Upper Bound

We now construct an instance for the upper bound on the value functions under
$\pi^{\star}_{\mathrm{NW}}$. Given any $\delta>0$ we construct the following
instance. Consider the following example with a single-state MDP and two
actions $a$ and $b$ available. The rewards are

$\displaystyle r_{1}(s,a)$ $\displaystyle=\delta^{n},\quad r_{i}(s,a)=1\text{
for all }i\neq 1,$ $\displaystyle\text{and}\quad r_{i}(s,b)$
$\displaystyle=\delta\text{ for all }i.$

Clearly, $\pi^{b}$, which selects action $b$ with probability $1$ maximizes
the minimum value, whereby $V^{\pi^{b}}(r_{i})=\delta$ for all $i\in[n]$. To
find out $\pi_{\mathrm{NW}}^{\star}$, consider an arbitrary policy which plays
action $a$ with probability $x$, and we optimize $x$ with respect to the Nash
welfare. Consider $\mathrm{NW}$ as a function of $x$, we have

$\frac{\partial\log\mathrm{NW}(x)}{\partial
x}=(n-1)\log(x+(1-x)\delta)+\log\left(x\delta^{n}+(1-x)\delta\right),$

of which the zero is given by

$\frac{(1-\delta)(n-1)}{x+(1-x)\delta}=\frac{1-\delta^{n-1}}{x\delta^{n-1}+(1-x)}.$

Rearranging the terms we get $x=(n-1)/n+o(1)$, where $o(1)$ is with respect to
$\delta$. Hence,

$\frac{V^{\pi_{\mathrm{NW}}^{\star}}(r_{1})}{V^{\pi_{\mathrm{MW}}^{\star}}(r_{1})}=\frac{\frac{n-1}{n}\delta^{n}+\frac{1}{n}\delta+o(1)}{\delta}=\frac{1}{n}+o(1).$

##  Appendix C Properties of Fairness Measures

######  Proposition 12.

$\mathrm{MW}$ satisfies axioms 3 and 4.

###### Proof.

Since minimum is an anonymous function, the objective $\mathrm{MW}$ satisfies
axiom 3. We now check axiom 4. Given a policy $\pi$, let $q^{\pi}$ be the
occupancy measure of policy $\pi$. Then we can express minimum value function
as
$\mathrm{MW}(\pi;{\mathbf{r}})=\min_{i}V^{\pi}(\rho;r_{i})=\min_{i}\sum_{h,s,a}q_{h}^{\pi}(s,a)r_{i}(s,a)$.
We can write down $\mathrm{MW}$ as a function of the occupancy measure of a
policy i.e.

$\mathrm{MW}_{o}(q;{\mathbf{r}})=\min_{i}\sum_{h,s,a}q_{h}(s,a)r_{i}(s,a)$

Since $\mathrm{MW}_{o}(\cdot;{\mathbf{r}})$ is a minimum of linear functions
$\mathrm{MW}_{o}$ is continuous. Therefore, there exists a point on the line
segment joining $q_{1}$ and $q_{3}$ that achieves the value
$\mathrm{MW}_{o}(q_{2};{\mathbf{r}})$. In particular, there exists
$\alpha\in[0,1]$ so that

$\mathrm{MW}_{o}(\alpha
q_{1}+(1-\alpha)q_{3};{\mathbf{r}})=\mathrm{MW}_{o}(q_{2};{\mathbf{r}})=\mathrm{MW}(\pi_{2};{\mathbf{r}})\qed$

######  Proposition 13.

There exists a weight vector $w\in\mathbb{R}^{n}_{+}$ so that $\mathrm{GGW}$
satisfies axioms 1, 3 and 4.

###### Proof.

Consider any weight vector $w$ so that $w_{1}>w_{2}>\ldots>w_{n}>0$ and
$\sum_{j}w_{j}=1$. Given a policy $\pi$, the ordering of the agents in terms
of their value functions remains unchanged even if we permute the agents. This
implies hat the objective $\mathrm{GGW}$ is anonymous for any weight vector
and it satisfies axiom 3. We now check axiom 4. Given a policy $\pi$, let
$q^{\pi}$ be the occupancy measure of policy $\pi$. Then we can express
generalized Gini welfare as a function of the occupancy measure of a policy
i.e.

$\mathrm{GGW}_{o}(q;\\{r_{i}\\}_{i\in[n]})=\sum_{j}w_{j}\sum_{h,s,a}q_{h}(s,a)r_{i_{j}}(s,a)$

Note that $\mathrm{GGW}_{o}(\cdot;\\{r_{i}\\}_{i\in[n]})$ is a weighted sum of
order statistics. Since each order statistic is a continuous function of the
occupancy measure $q$, $\mathrm{GGW}_{o}$ is a continuous function. Therefore,
there exists a point on the line segment joining $q_{1}$ and $q_{3}$ that
achieves the value $\mathrm{GGW}_{o}(q_{2};\\{r_{i}\\}_{i\in[n]})$. In
particular, there exists $\alpha\in[0,1]$ so that

$\mathrm{GGW}_{o}(\alpha
q_{1}+(1-\alpha)q_{3};\\{r_{i}\\}_{i\in[n]})=\mathrm{GGW}_{o}(q_{2};\\{r_{i}\\}_{i\in[n]})$

Now any policy $\pi^{q_{2}}$ achieves the generalized Gini welfare under the
occupancy measure $q_{2}$.

In order to check axiom 1 we assume $V^{\pi}(r_{i})\geq
V^{\widetilde{\pi}}(r_{i})$ for all $i$ and there exists $j$ such that
$V^{\pi}(r_{j})>V^{\widetilde{\pi}}(r_{j})$. Without loss of generality we can
also assume that the agents are ordered so that
$V^{\widetilde{\pi}}(r_{1})\geq V^{\widetilde{\pi}}(r_{2})\geq\ldots\geq
V^{\widetilde{\pi}}(r_{n})$. Then we have $V^{\pi}(r_{i_{k}})\geq
V^{\pi}(r_{k})\geq V^{\widetilde{\pi}}(r_{k})$ and $V^{\pi}(r_{i_{j}})\geq
V^{\pi}(r_{j})>V^{\widetilde{\pi}}(r_{j})$. Since $w_{k}>0$ we have
$\mathrm{GGW}(\pi;\\{r_{i}\\}_{i\in[n]})>\mathrm{GGW}(\pi;\\{r_{i}\\}_{i\in[n]})$.
∎

######  Proposition 14.

$\mathrm{NW}$ satisfies Axioms 1, 2, 3, and 4.

###### Proof.

Since $\mathrm{NW}$ is a monotonically increasing function of
$V^{\pi}(r_{i})$, axiom 1 is immediately satisfied. Moreover, the function
$\mathrm{NW}$ is a product of the values across the agents and hence
anonymous. In order to check axiom 2 suppose there exist policies
$\pi_{1},\pi_{2},\widetilde{\pi}_{1},\widetilde{\pi}_{2}$ and reward vectors
$r,\widetilde{r}$ so that for all $i$ we have

$\frac{V^{\pi_{1}}(\rho;r_{i})}{V^{\pi_{2}}(\rho;r_{i})}=\frac{V^{\widetilde{\pi}_{1}}(\rho;\widetilde{r}_{i})}{V^{\widetilde{\pi}_{2}}(\rho;\widetilde{r}_{i})}$

Now suppose
$\mathrm{NW}(\pi_{1};{\mathbf{r}})\geq\mathrm{NW}(\pi_{2};{\mathbf{r}})$. This
implies
$\prod_{i}V^{\pi_{1}}(\rho;r_{i})\geq\prod_{i}V^{\pi_{2}}(\rho;r_{i})$. This
gives us the following inequality.

$\frac{\prod_{i}V^{\widetilde{\pi}_{1}}(\rho;\widetilde{r}_{i})}{\prod_{i}V^{\widetilde{\pi}_{2}}(\rho;\widetilde{r}_{i})}=\frac{\prod_{i}V^{{\pi}_{1}}(\rho;{r}_{i})}{\prod_{i}V^{{\pi}_{2}}(\rho;{r}_{i})}\geq
1$

Therefore, we have
$\mathrm{NW}(\widetilde{\pi}_{1};\\{\widetilde{r}_{i}\\}_{i\in[n]})\geq\mathrm{NW}(\widetilde{\pi}_{2};\\{\widetilde{r}_{i}\\}_{i\in[n]})$.
The other direction of the implication can be proved analogously.

Now we check the final axiom 4. Given a policy $\pi$, let $q^{\pi}$ be the
occupancy measure of policy $\pi$. Then we can express the Nash social welfare
functional as
$\mathrm{NW}(\pi;\\{r_{i}\\}_{i\in[n]})=\prod_{i}V^{\pi}(\rho;r_{i})=\prod_{i}\left(\sum_{h,s,a}q^{\pi}_{h}(s,a)r_{i}(s,a)\right)$.
Therefore, we can write down log-Nash social welfare as a function of the
occupancy measure of a policy i.e.

$\mathrm{NW}_{o}(q;\mathbf{r})=\prod_{i}\left(\sum_{h,s,a}q_{h}(s,a)r_{i}(s,a)\right)$

$\mathrm{NW}_{o}$ is a continuous function of the occupancy measure. We are
also given that
$NW_{o}(q_{1};\mathbf{r})\geq\mathrm{NW}_{o}(q_{2};\mathbf{r})\geq\mathrm{NW}_{o}(q_{3};\mathbf{r})$.
Therefore, there exists a point on the line segment joining $q_{1}$ and
$q_{3}$ that achieves the value $\mathrm{NW}_{o}(q_{2};\mathbf{r})$. In
particular, there exists $\alpha\in[0,1]$ so that

$\displaystyle\mathrm{NW}_{o}(\alpha q_{1}+(1-\alpha)q_{3};\mathbf{r})$
$\displaystyle=\mathrm{NW}_{o}(q_{2};\mathbf{r})=\mathrm{NW}(\pi_{2};\mathbf{r})$

Now any policy with state-action occupancy measure $\alpha
q_{1}+(1-\alpha)q_{3}$ achieves the intermediate value
$\mathrm{NW}(\pi_{2};\mathbf{r})$. ∎

##  Appendix D Proof of Theorem 5

We prove that Axioms 1, 2, 3, and 4 uniquely characterize the Nash Social
Welfare function. Throughout we will fix the transition probability function
of the MDP and let different agents pick different reward functions. We assume
that there are at least four actions available at each state.

Defining Partial Order $\succcurlyeq$: We first define a partial order
$\succcurlyeq$ over the elements in
$\mathbb{R}^{n}_{+}=\left\\{x\in\mathbb{R}^{n}:x_{i}>0\ \forall i\right\\}$.

$x\succcurlyeq y\iff W\left(\pi^{a};{\mathbf{r}}\right)\geq
W\left(\pi^{b};{\mathbf{r}}\right)$ (21)

for arbitrary $a,b\in A$, where $\pi^{a}$ (resp. $\pi^{b}$) denotes a policy
such that $\pi^{a}(s)=a$ (resp. $\pi^{b}(s)=b$), and $\mathbf{r}$ is such that

$r_{i}(s,a)=x_{i}\ \text{ and }\ r_{i}(s,b)=y_{i}$ (22)

for all $i\in[n]$, and all the other entries of $\mathbf{r}$ are arbitrary.
Note that because of Axiom 2 this order $\succcurlyeq$ is well-defined despite
the arbitrary choice of $a$ and $b$ and reward vector $\mathbf{r}$ as we have
$V^{\pi^{a}}(r_{i})=x_{i}\cdot H$ and $V^{\pi^{b}}(r_{i})=y_{i}\cdot H$.

We now verify that the relation $\succcurlyeq$ satisfies reflexivity,
symmetry, and transitivity. Reflexivity and symmetry immediately follows from
the definition of the reward function in (22). For transitivity, suppose we
are given $x\succcurlyeq y$ and $y\succcurlyeq z$. We construct a reward
function $\mathbf{r}$ so that

$r_{i}(s,a)=x_{i},r_{i}(s,b)=y_{i},\textrm{ and }r_{i}(s,c)=z_{i}$

Then we have $W\left(\pi^{a};{\mathbf{r}}\right)\geq
W\left(\pi^{b};{\mathbf{r}}\right)$ and
$W\left(\pi^{b};{\mathbf{r}}\right)\geq W\left(\pi^{c};{\mathbf{r}}\right)$.
This implies $W\left(\pi^{a};{\mathbf{r}}\right)\geq
W\left(\pi^{c};{\mathbf{r}}\right)$ and $x\succcurlyeq z$. Therefore, any two
elements of $\mathbb{R}^{n}_{+}$ are comparable under the relation
$\succcurlyeq$.

######  Lemma 1.

Suppose $x,y\in\mathbb{R}^{n}_{+}$ with $x_{i}\geq y_{i}$ for all $i$ and
$x_{i}>y_{i}$ for some $i$. Then $x\succ y$.

###### Proof.

Let $\mathbf{r}$ be such that $r_{i}(s,a)=x_{i}$ and $r_{i}(s,b)=y_{i}$ for
all $i\in[n]$. Note that we have $V^{\pi^{a}}(r_{i})\geq V^{\pi^{b}}(r_{i})$
for all $i\in[n]$ and $V^{\pi^{a}}(r_{i})>V^{\pi^{b}}(r_{i})$ for some
individual $i$. Therefore, by Axiom 1 we must have
$W\left(\pi^{a};{\mathbf{r}}\right)>W\left(\pi^{b};{\mathbf{r}}\right)$. By
definition (21), this implies that $x\succ y$. ∎

#### Defining Function $F$.

Let $e\in\mathbb{R}^{n}_{+}$ be a vector with all component being $1$. For any
$x\in\mathbb{R}^{n}_{+}$, there exists $\lambda_{1}>\lambda_{0}>0$ such that
$\lambda_{0}\mathbf{e}<x<\lambda_{1}\mathbf{e}$ (where the comparison is
component-wise). We choose a reward function $\mathbf{r}$ such that

$r_{i}(s,a)=\lambda_{1},\ r_{i}(s,b)=\lambda_{0},\ r_{i}(s,c)=x_{i},$

and $r_{i}(s,d)$ is arbitrary. Then we have
$W\left(\pi^{a};{\mathbf{r}}\right)>W\left(\pi^{c};{\mathbf{r}}\right)>W\left(\pi^{b};{\mathbf{r}}\right)$.
By Axiom 4 there exists $\alpha\in[0,1]$ such that

$W\left(\pi^{c};{\mathbf{r}}\right)=W\left(\pi^{\alpha
q_{a}+(1-\alpha)q_{b}};\mathbf{r}\right)$ (23)

where $q_{a}=q^{\pi^{a}}$ and $q_{b}=q^{\pi^{b}}$. Under policy $\pi^{c}$ the
value function of agent $i$ is $V^{\pi^{c}}(r_{i})=x_{i}\cdot H$. And the
value function under the policy $\pi_{\alpha}=\pi^{\alpha
q_{a}+(1-\alpha)q_{b}}$ is

$\displaystyle V^{\pi_{\alpha}}(r_{i})$ $\displaystyle=\left\langle\alpha
q_{a}+(1-\alpha)q_{b},r_{i}\right\rangle$ $\displaystyle=\alpha\left\langle
q_{a},r_{i}\right\rangle+(1-\alpha)\left\langle q_{b},r_{i}\right\rangle$
$\displaystyle=\alpha\lambda_{1}\cdot H+(1-\alpha)\lambda_{0}\cdot H.$

Therefore, according to the definition of the order $\succcurlyeq$ we have
$x\sim[\alpha\lambda_{1}+(1-\alpha)\lambda_{0}]\mathbf{e}$ and we define

$F(x)=\alpha\lambda_{1}+(1-\alpha)\lambda_{0}.$

We first verify that $F$ is a well-defined function despite the arbitrary
choice of $\lambda_{0},\lambda_{1}$, and $\alpha$. Indeed, suppose that there
exists $\widetilde{\lambda}_{1}>\widetilde{\lambda}_{0}>0$ and
$\widetilde{\alpha}$ such that
$\widetilde{\lambda}_{0}\mathbf{e}<x<\widetilde{\lambda}_{1}\mathbf{e}$ and
$\widetilde{\alpha}$ satisfies (23) with respect to $\lambda_{0}$ and
$\lambda_{1}$. We have
$[\alpha\lambda_{1}+(1-\alpha)\lambda_{0}]\mathbf{e}\sim[\widetilde{\alpha}\widetilde{\lambda_{1}}+(1-\widetilde{\alpha})\widetilde{\lambda_{0}}]\mathbf{e}$.
Then by Lemma 1 it must be that
$\alpha\lambda_{1}+(1-\alpha)\lambda_{0}=\widetilde{\alpha}\widetilde{\lambda_{1}}+(1-\widetilde{\alpha})\widetilde{\lambda_{0}}$.
Hence, the value of $F(x)$ is independent of the choice of
$\lambda_{0},\lambda_{1}$, and $\alpha$.

We now establish an important property of the function $F$. The proof of this
claim is similar to the proof in [KN79] and uses the following lemma by
[Osb76] (also see Lemma 3.5 stated by [KN79]). We present our version of the
proof for completeness.

######  Lemma 2 ([Osb76]).

Suppose $\succcurlyeq$ is reflexive, symmetric, and transitive, and
$F:\mathbb{R}_{+}^{n}\to\mathbb{R}$ satisfies the following properties for any
$x,y\in\mathbb{R}_{+}^{n}$:

  * (i)

if $x\succcurlyeq y$, then $F(x)\geq F(y)$; and

  * (ii)

$F(x)\geq F(y)$ if and only if $F(\delta_{1}x_{1},\dots,\delta_{n}x_{n})\geq
F(\delta_{1}y_{1},\dots,\delta_{n}y_{n})$ for all
$\delta\in\mathbb{R}_{+}^{n}$.

Then there exist non-negative real constants $c_{1},\dots,c_{n}$ and a
monotone increasing function $g:\mathbb{R}\to\mathbb{R}$, such that
$F(x)\equiv g\left(\prod_{i=1}^{n}x_{i}^{c_{i}}\right)$.

######  Lemma 3.

There exists a monotone increasing function $g$ such that
$F(x)=g\left(\prod_{i=1}^{n}x_{i}\right)$.

###### Proof.

We show that the function $F$ satisfies two requirements of Lemma 2. This will
imply that there exist non-negative real constants $c_{1},\dots,c_{n}$ and a
monotone increasing function $g:\mathbb{R}\to\mathbb{R}$, such that
$F(x)\equiv g\left(\prod_{i=1}^{n}x_{i}^{c_{i}}\right)$. By Axiom 3, the
constants $c_{1},\dots,c_{n}$ must be identical, so the statement of the lemma
follows.

#### Requirement (i).

First, given $x\succcurlyeq y$, we need to show that $F(x)\geq F(y)$. Since
$x,y\in\mathbb{R}^{n}_{+}$ there exists $\lambda_{0},\lambda_{1}>0$ so that
$\lambda_{0}\mathbf{e}<x<\lambda_{1}\mathbf{e}$ and
$\lambda_{0}\mathbf{e}<y<\lambda_{1}\mathbf{e}$. We choose a reward function
$\mathbf{r}$ such that

$r_{i}(s,a)=\lambda_{1},r_{i}(s,b)=\lambda_{0},r_{i}(s,c)=x_{i},r_{i}(s,d)=y_{i}$

and $r_{i}=0$ otherwise. There exists $\alpha$ such that

$F(x)=\alpha\lambda_{1}+(1-\alpha)\lambda_{0}\ \textrm{and}\
W(\pi^{c};\mathbf{r})=W\left(\pi^{\alpha
q_{a}+(1-\alpha)q_{b}};\mathbf{r}\right).$

There also exists $\beta$ such that

$F(y)=\beta\lambda_{1}+(1-\beta)\lambda_{0}\ \textrm{and}\
W(\pi^{c};\mathbf{r}^{\prime})=W\left(\pi^{\beta
q_{a}+(1-\beta)q_{b}};\mathbf{r}^{\prime}\right),$

where
$r^{\prime}_{i}(s,a)=\lambda_{1},r^{\prime}_{i}(s,b)=\lambda_{0},r^{\prime}_{i}(s,c)=y_{i}$
and other entries of $\mathbf{r}^{\prime}$ are arbitrary. We have

$V^{\pi^{d}}(\mathbf{r})/V^{\pi^{\beta
q_{a}+(1-\beta)q_{b}}}(\mathbf{r})=V^{\pi^{c}}(\mathbf{r}^{\prime})/V^{\pi^{\beta
q_{a}+(1-\beta)q_{b}}}(\mathbf{r}^{\prime}).$

By Axiom 2, this means that $W(\pi^{d};\mathbf{r})\geq W\left(\pi^{\beta
q_{a}+(1-\beta)q_{b}};\mathbf{r}\right)$ if and only if
$W(\pi^{c};\mathbf{r}^{\prime})\geq W\left(\pi^{\beta
q_{a}+(1-\beta)q_{b}};\mathbf{r}^{\prime}\right)$. Hence, we also get that

$W(\pi^{d};\mathbf{r})=W\left(\pi^{\beta
q_{a}+(1-\beta)q_{b}};\mathbf{r}\right).$ (24)

Since $x\succcurlyeq y$ from definition (21) we have
$W(\pi^{c};\mathbf{r})\geq W(\pi^{d};\mathbf{r})$. This implies that

$W\left(\pi^{\alpha q_{a}+(1-\alpha)q_{b}};\mathbf{r}\right)\geq
W\left(\pi^{\beta q_{a}+(1-\beta)q_{b}};\mathbf{r}\right).$ (25)

But the vector of value functions under policy $\pi^{\alpha
q_{a}+(1-\alpha)q_{b}}$ is $(\alpha\lambda_{1}+(1-\alpha)\lambda_{0})\cdot
H\mathbf{e}$ and similarly the vector of value functions under policy
$\pi^{\beta q_{a}+(1-\beta)q_{b}}$ is
$(\beta\lambda_{1}+(1-\beta)\lambda_{0})\cdot H\mathbf{e}$. Therefore, it must
be that

$(\alpha\lambda_{1}+(1-\alpha)\lambda_{0})\cdot
H\mathbf{e}\geq(\beta\lambda_{1}+(1-\beta)\lambda_{0})\cdot H\mathbf{e}$

as otherwise we would have $(\alpha\lambda_{1}+(1-\alpha)\lambda_{0})\cdot
H\mathbf{e}<(\beta\lambda_{1}+(1-\beta)\lambda_{0})\cdot H\mathbf{e}$, which
contradicts (25) given Axiom 1. It follows that
$F(x)=\alpha\lambda_{1}+(1-\alpha)\lambda_{0}\geq\beta\lambda_{1}+(1-\beta)\lambda_{0}=F(y)$.

#### Requirement (ii).

Next, we show that $F(x)\geq F(y)$ if and only if
$F(\delta_{1}x_{1},\ldots,\delta_{n}x_{n})\geq
F(\delta_{1}y_{1},\ldots,\delta_{n}y_{n})$ for all $x,y$ and positive real
numbers $\delta_{i}$ for $i=1,\ldots,n$. First, suppose $F(x)\geq F(y)$.
Define $F(x),F(y)$ and the parameters $\alpha,\beta$ as we defined above.
Since $F(x)\geq F(y)$, we have

$\left(\alpha\lambda_{1}+(1-\alpha)\lambda_{0}\right)\mathbf{e}\geq\left(\beta\lambda_{1}+(1-\beta)\lambda_{1}\right)\mathbf{e}.$

Hence, $W(\pi^{c};\mathbf{r})\geq W(\pi^{d};\mathbf{r})$ by Axiom 1.

We now construct a new reward vector $\widetilde{\mathbf{r}}$. Let
$\underline{\delta}=\min\left\\{\delta_{1},\ldots,\delta_{n}\right\\}$ and
$\overline{\delta}=\max\left\\{\delta_{1},\ldots,\delta_{n}\right\\}$. Then we
define the following reward vector $\widetilde{\mathbf{r}}$

$\displaystyle\widetilde{r}_{i}(s,a)=\overline{\delta}\lambda_{1},$
$\displaystyle\widetilde{r}_{i}(s,b)=\underline{\delta}\lambda_{0},$
$\displaystyle\widetilde{r}_{i}(s,c)=\delta_{i}x_{i},$
$\displaystyle\widetilde{r}_{i}(s,d)=\delta_{i}y_{i}.$

We now apply axiom 2 with respect to policy $\pi^{c},\pi^{d}$ and reward
vectors $\mathbf{r}$ and $\widetilde{\mathbf{r}}$. Note that

$\frac{V^{\pi^{c}}(r_{i})}{V^{\pi^{d}}(r_{i})}=\frac{V^{\pi^{c}}(\widetilde{r}_{i})}{V^{\pi^{d}}(\widetilde{r}_{i})}.$

Since the function satisfies Axiom 2, we have
$W(\pi^{c};\widetilde{\mathbf{r}})\geq W(\pi^{d};\widetilde{\mathbf{r}})$.
From Definition (23) we know that there exists
$\widetilde{\alpha},\widetilde{\beta}$ such that

$W(\pi^{c};\widetilde{\mathbf{r}})=W\left(\pi^{\widetilde{\alpha}q_{a}+(1-\widetilde{\alpha})q_{b}};\widetilde{\mathbf{r}}\right)$

and, similarly to (24),

$W(\pi^{d};\widetilde{\mathbf{r}})=W\left(\pi^{\widetilde{\beta}q_{a}+(1-\widetilde{\beta})q_{b}};\widetilde{\mathbf{r}}\right).$

By Axiom 1, this implies that

$\left({\widetilde{\alpha}\overline{\delta}\lambda_{1}+(1-\widetilde{\alpha})\underline{\delta}\lambda_{0}}\right)\mathbf{e}\geq\left({\widetilde{\beta}\overline{\delta}\lambda_{1}+(1-\widetilde{\beta})\underline{\delta}\lambda_{0}}\right)\mathbf{e}$

as the two sides are the value vectors of
$\pi^{\widetilde{\alpha}q_{a}+(1-\widetilde{\alpha})q_{b}}$ and
$\pi^{\widetilde{\beta}q_{a}+(1-\widetilde{\beta})q_{b}}$. It follows that

$\displaystyle
F(\delta_{1}x_{1},\ldots,\delta_{n}x_{n})=\widetilde{\alpha}\overline{\delta}\lambda_{1}+(1-\widetilde{\alpha})\underline{\delta}\lambda_{0}\geq{\widetilde{\beta}\overline{\delta}\lambda_{1}+(1-\widetilde{\beta})\underline{\delta}\lambda_{0}}=F(\delta_{1}y_{1},\ldots,\delta_{n}y_{n}).$

This completes the proof. ∎

#### From Function $F$ to $\mathrm{NW}$.

Suppose there are two policies $\pi_{1}$ and $\pi_{2}$ such that
$W\left(\pi_{1};{\mathbf{r}}\right)\geq W\left(\pi_{2};{\mathbf{r}}\right)$.
Let us denote $q_{1}=q^{\pi_{1}}$ and $q_{2}=q^{\pi_{2}}$. Consider two
vectors $u,v\in\mathbb{R}^{n}_{+}$ such that

$u_{i}={\left\langle r_{i},q_{1}\right\rangle}\ \text{ and }\
v_{i}={\left\langle r_{i},q_{2}\right\rangle}.$

In order to determine whether $u\succcurlyeq v$ or $v\succcurlyeq u$ we define
the following reward functions following (22):

$\widetilde{r}_{i}(s,a)=\frac{\left\langle r_{i},q_{1}\right\rangle}{H}\
\textrm{and}\ \widetilde{r}_{i}(s,b)=\frac{\left\langle
r_{i},q_{2}\right\rangle}{H}.$

Then we have $V^{\pi^{a}}(\widetilde{r}_{i})=\left\langle
r_{i},q_{1}\right\rangle=V^{\pi_{1}}(r_{i})$ and
$V^{\pi^{b}}(\widetilde{r}_{i})=\left\langle
r_{i},q_{2}\right\rangle=V^{\pi_{2}}(r_{i})$. By Axiom 2 it must be that
$W\left(\pi_{a};{\mathbf{r}}\right)\geq W\left(\pi_{b};{\mathbf{r}}\right)$;
hence, we have $u\succcurlyeq v$ by definition. This implies that $F(u)\geq
F(v)$ as $F$ satisfies the first requirement of Lemma 2. By Lemma 3 this is
equivalent to:

$\displaystyle\prod_{i\in[n]}u_{i}\geq\prod_{i\in[n]}v_{i}$
$\displaystyle\iff$ $\displaystyle\sum_{i\in[n]}\log(\left\langle
r_{i},q_{1}\right\rangle)\geq\sum_{i\in[n]}\log(\left\langle
r_{i},q_{2}\right\rangle)$ $\displaystyle\iff$
$\displaystyle\sum_{i\in[n]}\log\left(V^{\pi_{1}}(r_{i})\right)\geq\sum_{i\in[n]}\log\left(V^{\pi_{2}}(r_{i})\right)$
$\displaystyle\iff$
$\displaystyle\mathrm{NW}(\pi_{1};\mathbf{r})\geq\mathrm{NW}(\pi_{2};\mathbf{r}).$

It can be also shown that $F(u)\geq F(v)\implies u\succcurlyeq v\implies
W\left(\pi_{1};{\mathbf{r}}\right)\geq W\left(\pi_{2};{\mathbf{r}}\right)$.
Hence, we get that $W\left(\pi_{1};{\mathbf{r}}\right)\geq
W\left(\pi_{2};{\mathbf{r}}\right)\iff\mathrm{NW}(\pi_{1};\mathbf{r})\geq\mathrm{NW}(\pi_{2};\mathbf{r})$.

##  Appendix E Optimistic Planning

We aim to solve the following optimization problem.

$\displaystyle\widetilde{P}_{t}\in\mathrm{argmax}_{P\in
C_{t}(\widehat{P})}\max_{\pi}\mathbb{F}(\pi;P)$ (26)

where $C_{t}(\widehat{P})$ is the set of plausible transition functions at
time $t$ i.e.

$C_{t}(\widehat{P})=\left\\{P:\forall s\left\lVert
P(s,a,\cdot)-\widehat{P}(s,a,\cdot)\right\rVert_{1}\leq\varepsilon_{t}(s,a)\right\\}$

for
$\varepsilon_{t}(s,a)=\sqrt{\frac{4S\log(SAt/\delta)}{\max\left\\{1,N_{t}(s,a)\right\\}}}$.
We will show that the objective
$\widetilde{\mathbb{F}}(P)=\max_{\pi}\mathbb{F}(\pi;P)$ is concave in $P$ for
various choices of $\mathbb{F}$, so the problem is a convex optimization.
Since the feasibility over $C_{t}(\widehat{P})$ can be determined efficiently,
one can use any standard optimization method (e.g. the ellipsoid method) to
solve the optimistic planning problem.

In order to show concavity of $\widetilde{\mathbb{F}}$, let us consider two
probability transition functions $P_{1}$ and $P_{2}$. For the probability
transition function $P_{i}$, let $\pi_{i}^{\star}$ be the policy maximizing
the objective $\widetilde{\mathbb{F}}(P_{i})$ and let $q_{i}^{\star}$ be the
corresponding state-action occupancy measure. Now consider the probability
transition function $\lambda P_{1}+(1-\lambda)P_{2}$. Note that, $\lambda
q_{1}^{\star}+(1-\lambda)q_{2}^{\star}$ satisfies the Bellman-flow constraints
with respect to the probability transition function $\lambda
P_{1}+(1-\lambda)P_{2}$ i.e. $\lambda
q_{1}^{\star}+(1-\lambda)q_{2}^{\star}\in\mathcal{Q}(\rho,\lambda
P_{1}+(1-\lambda)P_{2})$. With these definitions we are now ready to show that
$\widetilde{\mathbb{F}}(\lambda
P_{1}+(1-\lambda)P_{2})\geq\lambda\widetilde{\mathbb{F}}(P_{1})+(1-\lambda)\widetilde{\mathbb{F}}(P_{2})$.

Nash Social Welfare: In this case, the optimization problem eq. 26 is
equivalent to the following optimization problem.

$\displaystyle\widetilde{P}_{t}\in\mathrm{argmax}_{P\in
C_{t}(\widehat{P})}\max_{\pi}\sum_{i=1}^{n}\log V^{\pi}(r_{i})$

We now show that the objective
$\widetilde{\mathrm{NW}}(P)=\max_{\pi}\sum_{i}\log V^{\pi}(r_{i};P)$ is
concave in $P$. Suppose, policy $\widetilde{\pi}$ is the policy with state-
action occupancy measure $\lambda q_{1}^{\star}+(1-\lambda)q_{2}^{\star}$ we
have

$\displaystyle\widetilde{\mathrm{NW}}(P)\geq\sum_{i=1}^{n}\log
V^{\widetilde{\pi}}(r_{i})$
$\displaystyle=\sum_{i=1}^{n}\log\left(\sum_{h}\sum_{s,a}\left(\lambda
q_{1,h}^{\star}(s,a)+(1-\lambda)q_{2,h}^{\star}(s,a)\right)r_{i}(s,a)\right)$
$\displaystyle\geq\lambda\sum_{i=1}^{n}\log\left(\sum_{h}\sum_{s,a}q_{1,h}^{\star}(s,a)r_{i}(s,a)\right)+(1-\lambda)\sum_{i=1}^{n}\log\left(\sum_{h}\sum_{s,a}q_{2,h}^{\star}(s,a)r_{i}(s,a)\right)$
$\displaystyle=\lambda\sum_{i=1}^{n}\log
V^{\pi^{\star}_{1}}(r_{i};P_{1})+(1-\lambda)\sum_{i=1}^{n}\log
V^{\pi^{\star}_{2}}(r_{i};P_{2})$
$\displaystyle=\lambda\widetilde{\mathrm{NW}}(P_{1})+(1-\lambda)\widetilde{\mathrm{NW}}(P_{2})$

Therefore, $\widetilde{\mathrm{NW}}(P)$ is a concave function of the
probability transition function $P$.

Minimum Welfare: In this case, optimization problem eq. 26 is equivalent to
the following optimization problem.

$\widetilde{P}_{t}\in\mathrm{argmax}_{P\in
C_{t}(\widehat{P})}\max_{\pi}\min_{i}V^{\pi}(r_{i})$

We again show that the objective
$\widetilde{\mathrm{MW}}(P)=\max_{\pi}\min_{i}V^{\pi}(r_{i})$ is concave in
$P$.

$\displaystyle\widetilde{\mathrm{MW}}(P)\geq\min_{i}V^{\widetilde{\pi}}(r_{i})$
$\displaystyle=\min_{i}\sum_{h}\sum_{s,a}\left(\lambda
q_{1,h}^{\star}(s,a)+(1-\lambda)q_{2,h}^{\star}(s,a)\right)r_{i}(s,a)$
$\displaystyle=\min_{i}\lambda
V^{\pi^{\star}_{1}}(r_{i})+(1-\lambda)V^{\pi^{\star}_{2}}(r_{i})$
$\displaystyle\geq\lambda\min_{i}V^{\pi^{\star}_{1}}(r_{i})+(1-\lambda)\min_{i}V^{\pi^{\star}_{2}}(r_{i})$
$\displaystyle=\lambda\widetilde{\mathrm{MW}}(P_{1})+(1-\lambda)\widetilde{\mathrm{MW}}(P_{2})$

Generalized Gini Welfare: In this case, we are given a weight vector
$w\in\mathbb{R}^{n}$ so that $w_{i}\geq 0$ for each $i$, $\sum_{i}w_{i}=1$ and
$w_{1}\geq w_{2}\geq\ldots\geq w_{n}$. Let $i_{1},i_{2},\ldots,i_{n}$ be an
ordering of the $n$ agents so that

$V^{\widetilde{\pi}}(r_{i_{1}})\leq
V^{\widetilde{\pi}}(r_{i_{2}})\leq\ldots\leq V^{\widetilde{\pi}}(r_{i_{n}}).$

Here $\widetilde{\pi}$ is the policy with state-action occupancy measure
$\lambda q_{1}^{\star}+(1-\lambda)q_{2}^{\star}$. Our objective is

$\widetilde{\mathrm{GGW}}(P)=\max_{\pi}\mathrm{GGW}(\pi;P)$

We now show that the objective $\widetilde{\mathrm{GGW}}(P)$ is concave in
$P$.

$\displaystyle\widetilde{\mathrm{GGW}}(P)\geq\sum_{j}w_{j}V^{\widetilde{\pi}}(r_{i_{j}})$
$\displaystyle=\sum_{j}w_{j}\sum_{h}\sum_{s,a}\left(\lambda
q_{1,h}^{\star}(s,a)+(1-\lambda)q_{2,h}^{\star}(s,a)\right)r_{i_{j}}(s,a)$
$\displaystyle=\sum_{j}w_{j}\left(\lambda
V^{\pi^{\star}_{1}}(r_{i_{j}})+(1-\lambda)V^{\pi^{\star}_{2}}(r_{i_{j}})\right)$
$\displaystyle=\lambda\sum_{j}w_{j}V^{\pi^{\star}_{1}}(r_{i_{j}})+(1-\lambda)\sum_{j}w_{j}V^{\pi^{\star}_{2}}(r_{i_{j}})$
$\displaystyle\geq\lambda\mathrm{GGW}(\pi^{\star}_{1};P_{1})+(1-\lambda)\mathrm{GGW}(\pi^{\star}_{2};P_{2})$

The last line follows from the following observation. Suppose
$\ell_{1},\ell_{2},\ell_{n}$ be an ordering of the agents so that

$V^{\pi^{\star}_{1}}(r_{i_{1}})\leq
V^{\pi^{\star}_{1}}(r_{i_{2}})\leq\ldots\leq V^{\pi^{\star}_{1}}(r_{i_{n}}).$

Since the weight vector $w$ is non-increasing in $i$, the ordering
$\ell_{1},\ell_{2},\ldots,\ell_{n}$ achieves the smallest possible value of
the weighted sum of the value functions i.e.

$\sum_{j}w_{j}V^{\pi^{\star}_{1}}(r_{i_{j}})\geq\sum_{j}w_{j}V^{\pi^{\star}_{1}}(r_{\ell_{j}})=\mathrm{GGW}(\pi^{\star}_{1};P_{1})$

The same argument holds for policy $\pi^{\star}_{2}$. Since policy
$\pi^{\star}_{1}$ (resp. $\pi^{\star}_{2}$) maximizes generalized Gini welfare
with respect to the probability transition function $P_{1}$ (resp. $P_{2}$) we
have the following inequality.

$\widetilde{\mathrm{GGW}}(P)\geq\lambda\widetilde{\mathrm{GGW}}(P_{1})+(1-\lambda)\widetilde{\mathrm{GGW}}(P_{2}).$

##  Appendix F Proof of Theorem 7

###### Proof.

Let $P^{\star}$ be the true probability transition function. Let us define
$\varepsilon_{t}(s,a)=\sqrt{\frac{4S\log(SAt/\delta)}{N_{t}(s,a)}}$. By the
Chernoff-Hoeffding type concentration inequality for categorical random
variables, the following bound holds for any state $s$, action $a$, and
episode $t$.

$\operatorname{Pr}\left(\left\lVert\hat{P}(s,a,\cdot)-P^{\star}(s,a,\cdot)\right\rVert_{1}\geq\varepsilon_{t}(s,a)\right)\leq\frac{\delta}{2t^{2}SA}$

Therefore, by a union bound over the $T$ episodes and all state-action pairs
we see that with high probability the true probability transition function
$P^{\star}$ is contained in the set $C_{t}(\hat{P})$ for all $t$ i.e.

$\operatorname{Pr}\left(\exists t\ P^{\star}\notin
C_{t}(\hat{P})\right)\leq\delta\sum_{t}\frac{1}{2t^{2}}\leq\delta$

So we assume that this event holds. At the start of episode $t$, we compute
the best policy $\widetilde{\pi}_{t}$ for the optimistic model
$\widetilde{P}_{t}$. This implies the following bound on the Nash welfare with
respect to the true model $P^{\star}$.

$\displaystyle\mathrm{NW}(\widetilde{\pi}_{t};\widetilde{P}_{t})$
$\displaystyle=\max_{\pi}\mathrm{NW}(\pi;\widetilde{P}_{t})$
$\displaystyle\geq\max_{P\in
C_{t}(\widehat{P})}\max_{\pi}\mathrm{NW}(\pi;P)\geq\max_{\pi}\mathrm{NW}(\pi;P^{\star})$

This allows us to upper bound the regret through the optimistic policy.

$\displaystyle\textrm{Reg}_{\mathrm{NW}}(T)$
$\displaystyle=\sum_{t=1}^{T}\mathrm{NW}(\pi^{\star}_{\mathrm{NW}})-\mathrm{NW}(\pi_{t})$
$\displaystyle\leq\sum_{t=1}^{T}\mathrm{NW}(\widetilde{\pi}_{t};\widetilde{P}_{t})-\mathrm{NW}(\widetilde{\pi}_{t};P^{\star})$
$\displaystyle\leq
H^{n-1}\sum_{t=1}^{T}\sum_{i\in[n]}\left|V^{\widetilde{\pi}_{t}}\left(r_{i};\widetilde{P}_{t}\right)-V^{\widetilde{\pi}_{t}}\left(r_{i};P^{\star}\right)\right|$
$\displaystyle\leq
H^{n-1}\sum_{i=1}^{n}\underbrace{\sum_{t=1}^{T}\left|V^{\widetilde{\pi}_{t}}\left(r_{i};\widetilde{P}_{t}\right)-V^{\widetilde{\pi}_{t}}\left(r_{i};P^{\star}\right)\right|}_{:=\textrm{Reg}_{i}}$

The second inequality uses lemma 4. We now use lemma 5 to establish a bound of
$\widetilde{O}\left(H^{2}S\sqrt{AT}\right)$ on the term $\textrm{Reg}_{i}$ for
any $i$. This proves the desired upper bound on the regret.

Consider any agent $i$. We can apply lemma 5 with
$\epsilon_{t}(s^{\prime},a,s)=\left|\widetilde{P}_{t}(s^{\prime},a,s)-P^{\star}(s^{\prime},a,s)\right|$.
Notice that as $\widetilde{P}_{t},P^{\star}\in C_{t}(\hat{P})$ we have the
following inequality.

$\displaystyle\sum_{s}\epsilon_{t}(s^{\prime},a,s)$
$\displaystyle=\sum_{s}\left|\widetilde{P}_{t}(s^{\prime},a,s)-P^{\star}(s^{\prime},a,s)\right|$
$\displaystyle\leq\sum_{s}\left|\hat{P}_{t}(s^{\prime},a,s)-P^{\star}(s^{\prime},a,s)\right|+\sum_{s}\left|\widetilde{P}_{t}(s^{\prime},a,s)-P^{\star}(s^{\prime},a,s)\right|$
$\displaystyle\leq 2\sqrt{\frac{4S\log(SAt/\delta)}{N_{t}(s^{\prime},a)}}$
$\displaystyle\textrm{Reg}_{i}$
$\displaystyle=\sum_{t=1}^{T}\left|V^{\widetilde{\pi}_{t}}\left(r_{i};\widetilde{P}_{t}\right)-V^{\widetilde{\pi}_{t}}\left(r_{i};P^{\star}\right)\right|\leq\sum_{t}H^{2}\sqrt{\sum_{s^{\prime},b}\left\lVert\epsilon_{t}(s^{\prime},b,\cdot)\right\rVert_{1}^{2}}$
$\displaystyle\leq
2H^{2}\sum_{t}\sqrt{\sum_{s^{\prime},b}\frac{4S\log(SAt/\delta)}{N_{t}(s^{\prime},b)}}$
$\displaystyle=4H^{2}\sqrt{S\log(SAT/\delta)}\sum_{t}\sqrt{\sum_{s^{\prime},b}\frac{1}{N_{t}(s^{\prime},b)}}$
$\displaystyle\leq
4H^{2}\sqrt{S\log(SAT/\delta)}\sqrt{T}\sqrt{\sum_{t}\sum_{s^{\prime},b}\frac{1}{N_{t}(s^{\prime},b)}}$
$\displaystyle=4H^{2}\sqrt{ST\log(SAT/\delta)}\sqrt{\sum_{s^{\prime},b}\sum_{t=1}^{N_{T}(s^{\prime},b)}\frac{1}{t}}$
$\displaystyle\leq 4H^{2}\sqrt{S\log(SAT/\delta)}\sqrt{SA\log T}$

######  Lemma 4.

For any policy $\pi$, and probability transition functions $P_{1}$ and $P_{2}$
we have

$\displaystyle\mathrm{NW}(\pi;P_{1})-\mathrm{NW}(\pi;P_{2})\leq
H^{n-1}\sum_{i=1}^{n}\left|V^{\pi}(r_{i};P_{1})-V^{\pi}(r_{i};P_{2})\right|$

###### Proof.

We use induction on the number of agents $n$. When $n=1$ this is trivially
true. So we assume the claim holds for $n=m$.

$\displaystyle\mathrm{NW}(\pi;P_{1})-\mathrm{NW}(\pi;P_{2})$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{m+1}V^{\pi}(r_{i};P_{1})-\prod_{i=1}^{m+1}V^{\pi}(r_{i};P_{2})$
$\displaystyle=\prod_{i=1}^{m}V^{\pi}(r_{i};P_{1})\cdot
V^{\pi}(r_{m+1};P_{1})-\prod_{i=1}^{m}V^{\pi}(r_{i};P_{1})\cdot
V^{\pi}(r_{m+1};P_{2})$
$\displaystyle+\prod_{i=1}^{m}V^{\pi}(r_{i};P_{1})\cdot
V^{\pi}(r_{m+1};P_{2})-\prod_{i=1}^{m}V^{\pi}(r_{i};P_{2})\cdot
V^{\pi}(r_{m+1};P_{2})$
$\displaystyle\leq\prod_{i=1}^{m}V^{\pi}(r_{i};P_{1})\left|V^{\pi}(r_{m+1};P_{1})-V^{\pi}(r_{m+1};P_{2})\right|+V^{\pi}(r_{m+1};P_{2})\left(\prod_{i=1}^{m}V^{\pi}(r_{i};P_{1})-\prod_{i=1}^{m}V^{\pi}(r_{i};P_{2})\right)$
$\displaystyle\leq
H^{m}\left|V^{\pi}(r_{m+1};P_{1})-V^{\pi}(r_{m+1};P_{2})\right|+H\cdot
H^{m-1}\sum_{i=1}^{m}\left|V^{\pi}(r_{i};P_{1})-V^{\pi}(r_{i};P_{2})\right|$
[By the induction hypothesis and the fact that $V^{\pi}(r_{i};P)\leq H$ for
any $i$ and $P$] $\displaystyle\leq
H^{m}\sum_{i=1}^{m+1}\left|V^{\pi}(r_{i};P_{1})-V^{\pi}(r_{i};P_{2})\right|$

######  Lemma 5.

Let
$\epsilon(s^{\prime},a,s)=\left|P(s^{\prime},a,s)-\widetilde{P}(s^{\prime},a,s)\right|$
for all tuples $(s^{\prime},a,s)$. Then for any policy $\widetilde{\pi}$ we
have

$\left|V^{\widetilde{\pi}}(r;\widetilde{P})-V^{\widetilde{\pi}}(r;P)\right|\leq
H^{2}\sqrt{\sum_{s^{\prime},b}\left\lVert\epsilon(s^{\prime},b,\cdot)\right\rVert_{1}^{2}}$

###### Proof.

We will use $\widetilde{q}$ to write the state-action occupancy measure under
policy $\widetilde{\pi}$ and probability transition function $\widetilde{P}$
i.e.
$\widetilde{q}_{h}(s,a)=\operatorname{Pr}_{\widetilde{\pi},\widetilde{P}}(s_{h}=s,a_{h}=a)$.
Similarly, we will use $q$ to denote the state-action occupancy measure under
policy $\widetilde{\pi}$ and probability transition function $P$. We will also
write
$\epsilon(s^{\prime},b,s)=\widetilde{P}(s^{\prime},b,s)-P(s^{\prime},b,s)$.

Since rewards are bounded between $0$ and $1$ we have the following
inequality.

$\displaystyle\left|V^{\widetilde{\pi}}(r;\widetilde{P})-V^{\widetilde{\pi}}(r;P)\right|$
(27) $\displaystyle=$
$\displaystyle\left|\sum_{h=1}^{H}\sum_{s,a}\widetilde{q}_{h}(s,a)r(s,a)-\sum_{h=1}^{H}\sum_{s,a}q_{h}(s,a)r(s,a)\right|$
$\displaystyle\leq\sum_{h=1}^{H}\underbrace{\sum_{s,a}\left|\widetilde{q}_{h}(s,a)-q_{h}(s,a)\right|}_{:=\Delta_{h}}$
(28)

We now establish a recurrence relation for the term
$\Delta_{h}=\sum_{s,a}\left|\widetilde{q}_{h}(s,a)-q_{h}(s,a)\right|$. First
note that, $\Delta_{1}=0$ since

$\displaystyle\Delta_{1}$
$\displaystyle=\sum_{s,a}\left|\widetilde{q}_{1}(s,a)-q_{1}(s,a)\right|=\sum_{s,a}\left|\rho(s)\widetilde{\pi}(s,a)-\rho(s)\widetilde{\pi}(s,a)\right|=0$

Here we use the equality constraint
$\sum_{a}q_{1}(s,a)=\rho(s)=\sum_{a}\widetilde{q}_{1}(s,a)$.

$\displaystyle\Delta_{h}=\sum_{s,a}\left|\widetilde{q}_{h}(s,a)-q_{h}(s,a)\right|$
$\displaystyle=\sum_{s,a}\left|\sum_{b}\widetilde{q}_{h}(s,b)\widetilde{\pi}(a|s)-\sum_{b}q_{h}(s,b)\widetilde{\pi}(a|s)\right|$
$\displaystyle\leq\sum_{s,a}\widetilde{\pi}(a|s)\left|\sum_{b}\widetilde{q}_{h}(s,b)-\sum_{b}q_{h}(s,b)\right|$
$\displaystyle\leq\sum_{s}\left|\sum_{s^{\prime},b}\widetilde{q}_{h-1}(s^{\prime},b)P(s^{\prime},b,s)-\sum_{s^{\prime},b}q_{h-1}(s^{\prime},b)\widetilde{P}(s^{\prime},b,s)\right|$
$\displaystyle\leq\sum_{s}\left|\sum_{s^{\prime},b}\left(\widetilde{q}_{h-1}(s^{\prime},b)-q_{h-1}(s^{\prime},b)\right)P(s^{\prime},b,s)\right|+\sum_{s}\left|\sum_{s^{\prime},b}q_{h-1}(s^{\prime},b)\left(P(s^{\prime},b,s)-\widetilde{P}(s^{\prime},b,s)\right)\right|$
$\displaystyle\leq\sum_{s}\sum_{s^{\prime},b}\left|\widetilde{q}_{h-1}(s^{\prime},b)-q_{h-1}(s^{\prime},b)\right|P(s^{\prime},b,s)+\sum_{s}\sum_{s^{\prime},b}q_{h-1}(s^{\prime},b)\epsilon(s^{\prime},b,s)$
$\displaystyle\leq\sum_{s^{\prime},b}\left|\widetilde{q}_{h-1}(s^{\prime},b)-q_{h-1}(s^{\prime},b)\right|+\sum_{s^{\prime},b}q_{h-1}(s^{\prime},b)\sum_{s}\epsilon(s^{\prime},b,s)$
$\displaystyle\leq\Delta_{h-1}+\sqrt{\sum_{s^{\prime},b}q_{h-1}(s^{\prime},b)^{2}}\sqrt{\sum_{s^{\prime},b}\left(\sum_{s}\epsilon(s^{\prime},b,s)\right)^{2}}$
$\displaystyle\leq\Delta_{h-1}+\sum_{s^{\prime},b}q_{h-1}(s^{\prime},b)\sqrt{\sum_{s^{\prime},b}\left\lVert\epsilon(s^{\prime},b,\cdot)\right\rVert_{1}^{2}}$
$\displaystyle\leq\Delta_{h-1}+\underbrace{\sqrt{\sum_{s^{\prime},b}\left\lVert\epsilon(s^{\prime},b,\cdot)\right\rVert_{1}^{2}}}_{:=\varepsilon}$

The above recurrence relation and $\Delta_{1}=0$ gives us
$\Delta_{h}=(h-1)\varepsilon$. Substituting this result in equation 28 we get
the following bound.

$\left|V^{\widetilde{\pi}}(r;\widetilde{P})-V^{\widetilde{\pi}}(r;P)\right|\leq\sum_{h=1}^{H}(h-1)\varepsilon\leq
H^{2}\varepsilon\qed$

##  Appendix G Unknown Reward Functions

When the reward function is unknown we update the optimistic planning step as
follows

$\displaystyle(\widetilde{P}_{t},\widetilde{r}_{t})\leftarrow\mathrm{argmax}_{P\in
C_{t}(\widehat{P}),r\in D_{t}(\hat{r})}\max_{\pi}\mathbb{F}(\pi;P,r)$
$\displaystyle\widetilde{\pi}_{t}\leftarrow\mathrm{argmax}_{\pi}\mathbb{F}(\pi;\widetilde{P}_{t},\widetilde{r}_{t})$

Here $D_{t}(\hat{r})$ is a confidence set around the empirical reward function
$\hat{r}$ and it can be constructed by using Chernoff-Hoeffding inequality and
the union bound. Here we consider the case $\mathbb{F}=\mathrm{NW}$. The proof
for $\mathrm{MW}$, and $\mathrm{GGW}$ are similar. As in the proof of theorem
7 we can upper bound regret as

$\displaystyle\textrm{Reg}_{\mathrm{NW}}(T)\leq
H^{n-1}\sum_{t=1}^{T}\sum_{i\in[n]}\left|V^{\widetilde{\pi}_{t}}\left(\widetilde{r}_{t,i};\widetilde{P}_{t}\right)-V^{\widetilde{\pi}_{t}}\left(r_{i};P^{\star}\right)\right|$
$\displaystyle\leq
H^{n-1}\sum_{i\in[n]}\underbrace{\sum_{t=1}^{T}\left|V^{\widetilde{\pi}_{t}}\left(\widetilde{r}_{t,i};\widetilde{P}_{t}\right)-V^{\widetilde{\pi}_{t}}(r_{i};\widetilde{P}_{t})\right|}_{:=\textrm{Reg}_{i}^{r}}+H^{n-1}\sum_{i\in[n]}\underbrace{\sum_{t=1}^{T}\left|V^{\widetilde{\pi}_{t}}\left(r_{i};\widetilde{P}_{t}\right)-V^{\widetilde{\pi}_{t}}(r_{i};P^{\star})\right|}_{:=\textrm{Reg}^{P}_{i}}$

The second term $\textrm{Reg}^{P}_{i}$ exactly equals the term
$\textrm{Reg}_{i}$ introduced in theorem 7 and is bounded by
$O(H^{2}S\sqrt{AT})$. The first term $\textrm{Reg}^{r}_{i}$ equals the
difference in value functions between optimistic reward function
$\widetilde{r}_{t,i}$ and true reward function $r_{i}$ but with respect to the
fixed probability transition function $\widetilde{P}_{t}$. Let
$\varepsilon_{r}(s,a)=\left|\widetilde{r}_{t,i}(s,a)-r_{i}(s,a)\right|$ and
$\widetilde{q}_{t}$ be the state-action occupancy measure under policy
$\widetilde{\pi}_{t}$ and probability transition function $\widetilde{P}_{t}$.
Then we have,

$\displaystyle\textrm{Reg}^{r}_{i}$
$\displaystyle=\left|\left\langle\widetilde{q}_{t},\widetilde{r}_{t,i}\right\rangle-\left\langle\widetilde{q}_{t},{r}_{i}\right\rangle\right|=\left\langle\widetilde{q}_{t},\widetilde{r}_{t,i}-r_{i}\right\rangle\leq\sum_{h}\sum_{s,a}\varepsilon_{r}(s,a)\widetilde{q}_{t,h}(s,a)\leq
H\left\lVert\varepsilon_{r}\right\rVert_{1}$

Now, by an analysis very similar to bounding the error term
$\varepsilon=\sqrt{\sum_{s^{\prime},b}\left\lVert\epsilon(s^{\prime},b,\cdot)\right\rVert_{1}^{2}}$,
one can show that the term $\left\lVert\varepsilon_{r}\right\rVert_{1}$ is
bounded by $O(S\sqrt{AT})$. This implies that the term $\textrm{Reg}^{P}_{i}$
dominates the term $\textrm{Reg}^{r}_{i}$ and the regret is still bounded by
$O(nH^{n+1}S\sqrt{AT})$.

##  Appendix H Lower Bound on $\textrm{Reg}_{\mathrm{NW}}(T)$

$s_{0}$$s_{g}$$s_{b}$$\delta,\ 1$$\delta,\ 0$$1-\delta,\ 1$$1-\delta,\ 0$
Figure 2: Lower Bound Instance (following [LS20])

We consider a collection of MDPs, where the state-space of each of the MDPs
consists of a good state ($s_{g}$) and a bad state ($s_{b}$). The remaining
$S-2$ states are arranged in a $A$-ary tree. The transitions within the
$S$-ary tree is deterministic. Let $\mathcal{L}$ be the set of leaves in the
$A$-ary tree. Then for the $\ell$-th leaf node, and $a$-th action we consider
the following transition probabilities.

$P(s_{g}|\ell,a)=\frac{1}{2}+\Delta,\quad P(s_{b}|\ell,a)=\frac{1}{2}-\Delta$

In the $(\ell,a)$-th MDP, all the other actions from the leaf nodes have
uniform probability of transitioning to either the good or the bad state. From
the good or the bad state, taking any action maintains the current state with
probability $1-\delta$, and transitions to $s_{0}$ with probability $\delta$.
The rewards are $1$ for all the $n$ agents at state $s_{g}$. All the other
rewards are zero. We choose $\delta=\frac{1}{2H}$

###  H.1 Proof of theorem 10

###### Proof.

We will write $M_{0}$ to denote the MDP where
$P(s_{g}|\ell,a)=P(s_{b}|\ell,a)=\frac{1}{2}$ for all $\ell$ and $a$. Let us
define the following stopping time $\tau$.

$\tau=T\wedge\min\left\\{t:\sum_{u=1}^{t}\sum_{h=1}^{H}\mathbbm{1}\left\\{s_{u,h}=s_{g}\right\\}\geq
T-1\right\\}$ (29)

i.e. $\tau$ is the minimum episode number when the number of visits to state
$s_{g}$ is at least $T-1$. If this episode number is larger than $T$ then we
just set $\tau$ as $T$.

Let $T_{\ell,a}$ be the total number of times the policy visits state $\ell$
and takes action $a$ until the stopping time $\tau$. We first show that
$\mathbb{E}_{0}\left[\sum_{\ell,a}T_{\ell,a}\right]=\Theta(T)$ where
$\mathbb{E}_{0}[\cdot]$ denotes expectation with respect to the MDP $M_{0}$.
Note that a visit to one of the leaf nodes is followed by either a visit to
the good node $s_{g}$ or a visit to the bad node $s_{b}$. Since the number of
visits to $s_{g}$ is $T-1$ we just need to bound the number of visits to the
state $s_{b}$.

Let $T_{b}$ the total number of visits to the bad state starting from the node
$s_{0}$. We write $T_{b}=T_{b}^{1}+T_{b}^{2}$ where $T_{b}^{1}$ is the number
of visits to state $s_{b}$ which were followed by episode reset before
visiting the starting state $s_{0}$. On the other hand, $T_{b}^{2}$ is the
number of visits to state $s_{b}$ that were not stopped by episode reset
before visiting state $s_{0}$. Since there are $T$ episodes, we have
$T_{b}^{1}\leq T$.

In order to bound $T^{2}_{b}$ we consider the total amount of time the policy
stays at state $s_{b}$ before visiting $s_{0}$. This is a geometric random
variable with parameter $1/2H$. Therefore, if we write $Y_{b}$ to denote the
total amount of time the policy stays at $s_{b}$ because of visitations in the
set $T^{2}_{b}$, $Y_{b}$ is a sum of i.i.d. geometric random variables, and by
standard concentration inequality [DP09, Bro11] we get

$\operatorname{Pr}\left(Y_{b}<\frac{1}{2}\cdot
T^{2}_{b}\cdot\frac{H}{2}\right)\leq e^{-T^{2}_{b}/6}$

Therefore, as long as $T^{2}_{b}\geq 6\log(1/\delta)$ the total time spent at
state $s_{b}$ is at least $T^{2}_{b}H/4$ with probability at least $1-\delta$.
Since the total number of time steps is exactly $TH$, it must be that
$T^{2}_{b}\leq 4T$ in this case. Therefore, either $T_{b}^{2}$ is less than
$6\log(1/\delta)$ or it is less than $4T$ with probability at least
$1-\delta$. Combining these two cases we get the following upper bound on
expected value of $T_{b}^{2}$

$\mathbb{E}\left[T_{b}^{2}\right]\leq 6\log(1/\delta)+(1-\delta)4T+\delta TH$

This bound holds for any choice of $\delta$. In particular, for $\delta=1/4H$
and $T\geq\Omega(\log H)$ we get that $\mathbb{E}\left[T_{b}^{2}\right]\leq
5T$.

Therefore, we have
$\mathbb{E}[T_{b}]=\mathbb{E}[T^{1}_{b}]+\mathbb{E}[T^{2}_{b}]\leq 6T$. As
$\mathbb{E}_{0}\left[\sum_{\ell,a}T_{\ell,a}\right]$ is bounded by the total
number of visits to node $s_{g}$ and node $s_{b}$ we have the following bound.

$T-1\leq\mathbb{E}_{0}\left[\sum_{\ell,a}T_{\ell,a}\right]\leq 7T-1$

By a very similar argument we can also establish a similar bound for MDP
$(\ell,a)$.

Lower Bound on Regret for Model $P_{\ell,a}$: In this model the optimal policy
is to navigate to the $\ell$-th leaf node and then take action $a$. Let $W$ be
a geometric random variable with parameter $p=\frac{1}{2H}$. Then the value
function of an agent $i$ is at least

$\displaystyle\left(\frac{1}{2}+\Delta\right)\mathbb{E}\left[\min\left\\{W,H-\log
S\right\\}\right]$

We now lower bound the term $\mathbb{E}\left[\min\left\\{W,H-\log
S\right\\}\right]$.

$\displaystyle\mathbb{E}\left[\min\left\\{W,H-\log S\right\\}\right]$
$\displaystyle=\sum_{x=1}^{H-\log S}x(1-p)^{x-1}\cdot p+\sum_{x\geq H-\log
S}(H-\log S)(1-p)^{x-1}\cdot p$ $\displaystyle=\frac{1}{p}-2(1-p)^{H-\log S}$
$\displaystyle=2H-2\left(1-\frac{1}{2H}\right)^{H-\log S}$ $\displaystyle\geq
2H-2\cdot e^{-\frac{1}{2}-\frac{\log S}{2H}}=\Theta(H)$

as long as $H=\Omega(\log S)$. Therefore, the total expected Nash welfare over
the $T$ episodes is at least

$\displaystyle\Theta\left(T\left(\frac{1}{2}+\Delta\right)^{n}H^{n}\right)=\Theta\left(\left(\frac{1}{2}+\Delta\right)^{n}H^{n}\mathbb{E}_{\ell,a}\left[\sum_{\ell^{\prime},a^{\prime}}T_{\ell^{\prime},a^{\prime}}\right]\right)$

Let $X^{t}_{\ell^{\prime},a^{\prime}}$ be the indicator variable that denotes
whether the policy visits leaf node $\ell^{\prime}$, and takes action
$a^{\prime}$ at episode $t$. If $X^{t}_{\ell,a}=1$ then by a very similar
argument as above, we can show that expected Nash welfare at episode $t$ is at
most $O((1/2+\Delta)^{n}H^{n})$. On the other hand, if $X^{t}_{\ell,a}=0$ then
expected Nash welfare at episode $t$ is $O((1/2)^{n}H^{n})$. Therefore, the
sum of expected Nash welfare over the $T$ episodes is

$\displaystyle\sum_{t}\sum_{(\ell^{\prime},a^{\prime})\neq(\ell,a)}\mathbb{E}_{\ell,a}\left[X^{t}_{\ell^{\prime},a^{\prime}}\right]\left(\frac{H}{2}\right)^{n}+\sum_{t}\mathbb{E}_{\ell,a}\left[X^{t}_{\ell,a}\right]\left(\frac{1}{2}+\Delta\right)^{n}H^{n}$
$\displaystyle=\left(\frac{H}{2}\right)^{n}\sum_{\ell^{\prime},a^{\prime}}\mathbb{E}_{\ell,a}\left[T_{\ell^{\prime},a^{\prime}}\right]+\mathbb{E}_{\ell,a}\left[T_{\ell,a}\right]\left(\left(\frac{1}{2}+\Delta\right)^{n}-\left(\frac{1}{2}\right)^{n}\right)H^{n}$

Let $T_{\sigma}=\sum_{\ell^{\prime},a^{\prime}}T_{\ell^{\prime},a^{\prime}}$.
Then regret on model $P_{\ell,a}$ is at least

$\displaystyle R_{\ell,a}$
$\displaystyle\geq\left(\left(\frac{1}{2}+\Delta\right)^{n}-\left(\frac{1}{2}\right)^{n}\right)H^{n}\mathbb{E}_{\ell,a}\left[T_{\sigma}-T_{\ell,a}\right]\geq
n\Delta\left(\frac{H}{2}\right)^{n}\mathbb{E}_{\ell,a}\left[T_{\sigma}-T_{\ell,a}\right]$

Now we can proceed very similarly to the proof of theorem 38.7 from [LS20] and
establish that there exists some $\ell^{\prime},a^{\prime}$ so that
$\mathbb{E}_{\ell^{\prime},a^{\prime}}[T_{\sigma}-T_{\ell^{\prime},a^{\prime}}]\geq
O(T)$ for $\Delta=\Omega(\sqrt{SA/T})$. This choice of $\Delta$ implies the
following lower bound.

$R_{\ell^{\prime},a^{\prime}}\geq\Omega\left(n\left(\frac{H}{2}\right)^{n}\sqrt{SAT}\right)\qed$

##  Appendix I Proof of Theorem 11

###### Proof.

We first assume that $v^{\star}$ equals the maximin value
$v^{\star}_{\mathrm{MW}}=\max_{\pi}\min_{i}V^{\pi}(r_{i})$. We will assume
$B\geq 1$. Notice that UOB-REPS is run with reward function

$\widetilde{r}_{t}(s,a)=\sum_{i}\lambda_{i}^{t}r_{i}(s,a)+\frac{v^{\star}}{H}\left(1-\sum_{i}\lambda_{i}^{t}\right)$

at time $t$. Since each entry of the reward function $r_{i}$ is bounded by $1$
we have $\left|\widetilde{r}_{i}(s,a)\right|=O(B)$. Therefore, from the regret
guarantee of UOB-REPS we have

$\displaystyle\max_{q}\sum_{t=1}^{T}\mathcal{L}(q,\lambda^{t})-\sum_{t=1}^{T}\mathcal{L}(q^{t},\lambda^{t})\leq\widetilde{O}\left(BHS\sqrt{AT}\right)$
$\displaystyle\Rightarrow$
$\displaystyle\max_{q}T\cdot\mathcal{L}(q,\overline{\lambda})-\sum_{t=1}^{T}\mathcal{L}(q^{t},\lambda^{t})\leq\widetilde{O}\left(BHS\sqrt{AT}\right)$
(30)

where $\overline{\lambda}=\frac{1}{T}\sum_{t=1}^{T}\lambda_{t}$. On the other
hand, from the regret guarantee of OSMD we have,

$\displaystyle\sum_{t=1}^{T}\mathcal{L}(q^{t},\lambda^{t})-\min_{\lambda\in\mathcal{C}}\sum_{t=1}^{T}\mathcal{L}(q^{t},\lambda)\leq{O}\left(BH\sqrt{nT\log
A}\right)$ $\displaystyle\Rightarrow$
$\displaystyle\sum_{t=1}^{T}\mathcal{L}(q^{t},\lambda^{t})-\min_{\lambda\in\mathcal{C}}T\cdot\mathcal{L}(\overline{q},\lambda)\leq
O\left(BH\sqrt{nT\log A}\right)$ (31)

where $\overline{q}$ is defined as
$\overline{q}_{h}(s,a)=\frac{1}{T}\sum_{t=1}^{T}q^{t}_{h}(s,a)$. Let
$i^{\star}\in\mathrm{argmin}_{i\in[n]}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})$. Since
$\mathbb{E}[V^{\pi_{t}}(r_{i})]=\sum_{h}\sum_{s,a}q_{h}^{t}(s,a)r_{i}(s,a)$,
an application of Chernoff’s implies the following inequality holds with
probability at least $1-\delta$.

$\displaystyle\left|\sum_{t=1}^{T}\sum_{h}\sum_{s,a}q^{t}_{h}(s,a)r_{i^{\star}}(s,a)-\sum_{t=1}^{T}V^{\pi^{t}}(r_{i^{\star}})\right|\leq
O\left(H\sqrt{T\log(n/\delta)}\right)$

Let $e_{i^{\star}}$ be the unit vector with exactly $1$ at index $i^{\star}$,
and $0$ otherwise. Then from eq. 31 we get the following bound.

$\displaystyle
T\cdot\mathcal{L}(\overline{q},Be_{i^{*}})\geq\min_{\lambda\in\mathcal{C}}T\cdot\mathcal{L}(\overline{q},\lambda)$
$\displaystyle\geq\sum_{t=1}^{T}\mathcal{L}(q^{t},\lambda^{t})-O\left(BH\sqrt{nT\log
A}\right)$
$\displaystyle\geq\max_{q}T\cdot\mathcal{L}(q,\overline{\lambda})-\widetilde{O}\left(BHS\sqrt{AT}\right)-O\left(BH\sqrt{nT\log
A}\right)\ \textrm{[By~{}\eqref{eq:temp-regret-1}]}$ $\displaystyle=T\cdot
v^{\star}\left(1-\sum_{i}\overline{\lambda}_{i}\right)+T\cdot\max_{q}\sum_{i}\overline{\lambda}_{i}\sum_{h}\sum_{s,a}q_{h}(s,a)-\widetilde{O}\left(BHS\sqrt{AT}\right)-O\left(BH\sqrt{nT\log
A}\right)$ $\displaystyle\geq T\cdot
v^{\star}\left(1-\sum_{i}\overline{\lambda}_{i}\right)+T\cdot
v^{\star}\sum_{i}\overline{\lambda}_{i}-\widetilde{O}\left(BHS\sqrt{AT}\right)-O\left(BH\sqrt{nT\log
A}\right)$ $\displaystyle=T\cdot
v^{\star}-\widetilde{O}\left(BHS\sqrt{AT}\right)-O\left(BH\sqrt{nT\log
A}\right)$

We can upper bound $T\cdot\mathcal{L}(\overline{q},Be_{i^{\star}})$ as

$\displaystyle
T\cdot\left(v^{\star}+B\left(\sum_{h=1}^{H}\sum_{s,a}\overline{q}_{h}(s,a)r_{i^{\star}}(s,a)-v^{\star}\right)\right)$
$\displaystyle=Tv^{\star}(1-B)+B\sum_{t=1}^{T}\sum_{h=1}^{H}\sum_{s,a}q_{h}^{t}(s,a)r_{i^{\star}}(s,a)$
(32)

This equality gives us the following bound.

$\displaystyle-
Tv^{\star}B+B\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})\geq-\widetilde{O}\left(BHS\sqrt{AT}\right)-O\left(BH\sqrt{nT\log
A}\right)$

After rearranging, and dividing throughout by $B$ we get the following bound
on regret.

$Tv^{\star}-\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})\leq\widetilde{O}\left(HS\sqrt{AT}\right)+O\left(H\sqrt{nT\log
A}\right)$

Now consider the case when $v^{\star}\neq v^{\star}_{\mathrm{MW}}$. Pick any
$v^{\star}\geq v^{\star}_{\mathrm{MW}}$ and run algorithm 2. By a similar
argument as above, we can establish the following bound.

$\displaystyle T\cdot\mathcal{L}(\overline{q},Be_{i^{\star}})\geq T\cdot
v^{\star}\left(1-\sum_{i}\overline{\lambda}_{i}\right)+T\cdot
v^{\star}_{\mathrm{MW}}\sum_{i}\overline{\lambda}_{i}-\widetilde{O}\left(BHS\sqrt{AT}\right)-O\left(BH\sqrt{nT\log
A}\right)$

Using the upper bound established in (32) we get the following bound.

$\displaystyle Tv^{\star}(1-B)+B\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})\geq
T\cdot v^{\star}\left(1-\sum_{i}\overline{\lambda}_{i}\right)$
$\displaystyle+T\cdot
v^{\star}_{\mathrm{MW}}\sum_{i}\overline{\lambda}_{i}-\widetilde{O}\left(BHS\sqrt{AT}\right)-O\left(BH\sqrt{nT\log
A}\right)$

After rearranging and dividing throughout by $B$ we get the following
inequality.

$\displaystyle
Tv^{\star}-\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})\leq\frac{T}{B}\sum_{i}\overline{\lambda}_{i}\left(v^{\star}-v^{\star}_{\mathrm{MW}}\right)+\widetilde{O}\left(HS\sqrt{AT}\right)+{O}\left(H\sqrt{nT\log
A}\right)$

This gives us the following bound on regret.

$\displaystyle
Tv^{\star}_{\mathrm{MW}}-\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})$
$\displaystyle\leq
Tv^{\star}-\min_{i}\sum_{t=1}^{T}V^{\pi_{t}}(r_{i})+T(v^{\star}_{\mathrm{MW}}-v^{\star})$
$\displaystyle\leq
T(v^{\star}_{\mathrm{MW}}-v^{\star})\left(1-\frac{\sum_{i}\overline{\lambda}_{i}}{B}\right)+\widetilde{O}\left(HS\sqrt{AT}\right)+{O}\left(H\sqrt{nT\log
A}\right)$
$\displaystyle\leq\widetilde{O}\left(HS\sqrt{AT}\right)+{O}\left(H\sqrt{nT\log
A}\right)$

The last inequality follows because $v^{\star}_{\mathrm{MW}}\leq v^{\star}$
and $\sum_{i}\overline{\lambda}_{i}\leq B$. ∎