Abstract

Cooperation in multi-agent systems is typically optimized through utilitarian objectives that maximize overall efficiency but fail to account for reward distribution, often resulting in inequitable "leader-follower" dynamics. While fairness-based approaches encourage pro-social behaviors where every agent benefits from cooperation, many current algorithms—including those utilizing reward shaping—break the stationarity of Markov Games or lack rigorous theoretical guarantees. This creates a critical gap between fair objective methods and theoretically safe learning frameworks. We propose a novel framework that bridges \(\alpha\)-fairness with Heterogeneous-Agent Trust Region Learning (HATRL), ensuring monotonic improvement and convergence toward Nash Equilibria. Our approach leverages a fair advantage function that dynamically weights agent utilities based on their expected returns, allowing the global objective to transition from purely utilitarian efficiency to \(\alpha\)-fairness welfare based on the parameter \(\alpha\). We introduce two practical algorithms, \(\alpha\)-fair HATRPO and \(\alpha\)-fair HAPPO, and demonstrate through experiments in sequential social dilemmas like CleanUp and CommonHarvest that they perform better than HATRL’s algorithms from a utilitarian point of view while achieving socially higher outcomes.

1 Introduction↩︎

Cooperation is a fundamental pillar of multi-agent systems (MAS), ranging from biological systems ([1]) to complex human societies([2]). Within Multi-Agent Reinforcement Learning (MARL), cooperation has traditionally been viewed through a utilitarian lens ([3], [4]), where the primary goal is to maximize the sum of all agents’ utilities. However, this focus on raw efficiency often ignores how rewards are distributed, potentially creating "leader-follower" dynamics ([5]) where a subset of agents is marginalized to optimize the collective total. For cooperation to be sustainable, fairness is not just a moral preference but a functional necessity, ensuring that every participant gains from the interaction. This need is further amplified by the recent rise of collective decision-making driven by Large Language Models (LLMs, [6]).

Recent efforts to integrate fairness into MARL have followed three primary paths: reward shaping, fairness constraints and social welfare objectives. Reward shaping methods, such as inequity aversion (IA, [7]), penalize differences in temporal rewards to solve social dilemmas. However, these approaches often rely on history-dependent rewards (FEN FEN?, Fair&LocalIA[8], IA[7]), which break the stationary property of Markov Games. Furthermore, they frequently utilize Proximal Policy Optimization (PPO–[9]) based algorithms like Independent PPO (IPPO–[10]) or Multi-Agent PPO (MAPPO–[11]), which, while popular, lack the rigorous theoretical convergence guarantees found in single-agent Trust Region Learning (TRL – [9]) methods. FCGrad ([12]) adopts an interesting approach by resolving gradient conflicts of individual objective and fair objective but it lacks equilibrium analysis and interpretability. Alternatively, fairness can be formulated as a formal constraint within the optimization problem (AdaFair-MARL[13], DeCOM[14], EcoFair-CH-MARL[15]), often by bounding specific indices like the Gini coefficient. While these constraint-based methods offer high interpretability, they are frequently domain-specific and struggle to generalize across a diverse range of multi-agent environments. Last but not least, social welfare objectives like the Generalized Gini function ([16]), Proportional Fairness ([17]) or \(\alpha\)-fairness ([18], [19]) offer a more unified goal (Fair MARL[5], SOTO[20], AT-FAPPO [21], or [22]), yet their practical implementations still largely rely on extrapolated PPO objectives that lack theoretical safeguards, and existing theoretical guarantees (e.g., in SOTO [20]) often rely on idealized assumptions (e.g., concavity of the objective function).

In this work, we bridge this gap by introducing a theoretically grounded framework for fair multi-agent learning built upon Heterogeneous-Agent Trust Region Learning (HATRL–[23], [24]). By combining the \(\alpha\)-fair objective with the monotonic improvement guarantees of HATRL, we provide a mathematically safe path for agents to learn pro-social behaviors. Our contributions are three-fold. We first introduce the Markov Game (MG) framework, then the fair objective used through this work. We also introduce the HATRL framework in the fully-cooperative setting. Secondly, we build a HATRL framework for our fair objective called \(\alpha\)-fair HATRL and study the theoretical properties of the learning framework. Thirdly, we develop two algorithms called \(\alpha\)-fair HATRPO and \(\alpha\)-fair HAPPO that extend \(\alpha\)-fair HATRL to practical settings. Finally, we test our algorithms on two sequential social dilemmas (SSD–[7]) environments called CleanUp and CommonHarvest and compare them to other methods relying on the same fair objective function. We demonstrate that \(\alpha\)-fair HATRPO and \(\alpha\)-fair HAPPO both reach higher level of performance compared to HATRL’s algorithm while reaching fairer outcomes.

2 Preliminaries↩︎

In this section, we first introduce the problem formulation and notations for MARL in the Markov Game settings, and then the core ideas of Heterogeneous-Agent Trust Region Learning (HATRL).

2.1 Notations↩︎

We denote the set of real numbers by \(\mathbb{R}\) and positive real numbers by \(\mathbb{R}^+\) and \(d\)-dimensional real-numbered vector spaces as \(\mathbb{R}^d\). Interval of integers between \(a\) and \(b\) are denoted by \(\llbracket a~;~ b \rrbracket\). By \(\mathcal{P}(A)\), we denote the power set of a set \(A\). We write \(|A|\) for the cardinality of a finite set \(A\). We use the vector notation \(\vec{.}\) to refer to any element in a cartesian product, i.e for any sets \(A_1,\,\dots,\,A_n\), \(\vec{a}=(a_1,\,\dots,\, a_n)\in\bigtimes_{i=1}^n A_i\).

2.2 General-Sum Markov Games and Fair Objective↩︎

For modeling sequential decision-making in multi-agent settings, we use the standard Markov Game framework (also known as a Stochastic Game–[25]). In this work, we consider a general-sum Markov game, meaning there is no condition on the reward functions.

A Markov game \(\mathcal{M}\) is defined by the following tuple: \((N, \tilde{\mathcal{S}}, \{\mathcal{A}_i\}_{i \in N}, P, \rho_0, \{r_i\}_{i \in N}, \gamma)\), with \(N\) the finite set of \(n\) players, \(\tilde{\mathcal{S}}\) the space of all possible states of the environment, \(\{\mathcal{A}_i\}_{i\in N}\) the individual action set for each player, \(P(\tilde{s}',\vec{a}, \tilde{s}) = \mathbb{P}(s'\,|\, s, \vec{a})\) the transition probability kernel, \(\rho_0\in\Delta(\tilde{\mathcal{S}})\) the initial state distribution, \(\{r_i\}_{i\in N}\) the individual reward for each player and \(\gamma \in [0, 1)\) the discount factor. At time step \(t\in\mathbb{N}\), the environment is at state \(s_t\in\mathcal{S}\) and each agent has to take an action \(a_i\in\mathcal{A}_i\) according to their policy \(\pi^i(\cdot|s_t)\). Given the environment state \(s_t\) and the joint action \(\vec{a}\in\mathcal{A}\) drawn by their joint policy \(\vec{\pi}(\cdot|s_t)=\prod_{i=1}^n\pi^i(\cdot|s_t)\), the environment moves to the next state \(s_{t+1}\in\mathcal{S}\) sampled by the transition probability kernel \(P(\tilde{s}',\vec{a}, \tilde{s}) = \mathbb{P}(\tilde{s}'\,|\, \tilde{s}, \vec{a})\) and each agent receive its reward \(r_i(s_t,\vec{a} _t)\in\mathbb{R}^+\). The sequence \(\tau=(s_0,\vec{a}_0, \vec{r}_0, s_1, \vec{a}_1, \vec{r} _1, \dots)\) is called a trajectory. All together, the discount factor, the joint policy and the transition kernel induce an improper state visitation distribution \(d_{\vec{\pi}}\).

Let us define the contextualized state \(s=(\tilde{s}, \tilde{c})\in \tilde{\mathcal{S}}\times\tilde{\mathcal{S}}\), where \(\tilde{c}\) is the context and stored the initial state through trajectories. The latter will be useful to get rid of the initial-state dependency in the next equations. For any state space, we define the state value function and the state-action value function linked to agent \(i\) respectively: \(V_i^{\vec{\pi}}(s)=\mathbb{E}_{\tau}\left[\sum_{t=0}^\infty\gamma^t r_t^i(s_t, \vec{a}_t)~|~s_0=s\right]\) and \(Q_i^{\vec{\pi}}(s, \vec{a})=\mathbb{E}_{\tau}\left[\sum_{t=0}^\infty\gamma^t r_t^i(s_t, \vec{a}_t)~|~s_0=s, \, \vec{a}_0=\vec{a}\right]\). The advantage function associated to agent \(i\) is \(A_i^{\vec{\pi}}(s, \vec{a})=Q_i^{\vec{\pi}}(s, \vec{a}) -V_i^{\vec{\pi}}(s)\).

In this work, we assume the state and action spaces to be finite and the reward functions to be positive and bounded by \(R_{\max}\).

2.3 Heterogeneous Agent Trust Region Learning↩︎

HATRL [23] was built on top of the single-agent Trust Region Learning (TRL) framework, where one agent tries to maximize a single reward signal \(r\). TRL relies on a first-order approximation of the expected return \(J_{\text{coop}}(\pi)=\mathbb{E}_{\tau\sim\pi}\left[\sum_{t=0}^\infty\gamma ^t r_t\right]\). Formally, for any policies \(\pi\) and \(\pi'\), TRL gives a lower bound of \(J_{\text{coop}}(\pi')-J_{\text{coop}}(\pi)\) using the surrogate function \(L_\pi(\tilde{\pi})=J_{\text{coop}}(\pi)+\mathbb{E}_{s\sim d_\pi, a\sim\tilde{\pi}}[A^\pi(s, a)]\) and \(D_{\text{KL}}^{\max}\left(\pi\,,\,\pi'\right)=\max_sD_{\text{KL}}(\pi(\cdot|s) \parallel \tilde{\pi}(\cdot|s))\): \[J_{\text{coop}}(\pi')\geq L_\pi(\tilde{\pi})-CD_{\text{KL}}^{\max}\left(\pi\,,\,\pi'\right),\] where \(C=\frac{4\gamma\max_{s,a}|A^\pi(s,a)|}{(1-\gamma)^2}\).

HATRL extends the TRL framework by considering multiple heterogeneous agents trying to maximize a single reward function. HATRL adapts TRL by considering joint policies instead of single policy and leveraging sequential update to coordinate agent’s learning.

Let \(\sigma\) be a permutation of \(\llbracket 1~;~n\rrbracket\). Let \(I_m=\{i_1, \dots,i_m\}\) denote an ordered subset of the shuffled interval, where \(i_k=\sigma(k)\). Let \(-I_m\) refer to its complement. HATRL defines the multi-agent state-action value function as \[Q^{\vec{\pi},\, I_m}(s, \, \vec{a}^{I_m})=\mathbb{E}_{\vec{a}^{-I_m}\sim \vec{\pi}_{-I_m}}\left[Q^{\vec{\pi}}(s,\, \vec{a}^{I_m}, \vec{a}^{-I_m})\right],\] and for disjoint sets \(J_k\) and \(I_m\), the multi-agent advantage function is defined as \[A^{\vec{\pi},\, I_m}(s, \vec{a}^{J_k}, \vec{a}^{I_m}) = Q^{\vec{\pi},\, J_k+ I_m}(s, \, \vec{a}^{J_k+ I_m}) - Q^{\vec{\pi},\, J_k}(s, \, \vec{a}^{J_k}).\]

Formally, HATRL can be described as followed. Let \(\vec{\pi}\) be the current joint policy, \(\vec{\pi} '\) be any other policy and \(I_n\) a shuffled order. Let us define \(L_{\vec{\pi}}^{I_m}(\vec{\pi}'^{I_{m-1}}, \pi'^{i_m})= \mathbb{E}_{s\sim d_{\vec{\pi}}, \vec{a} ^{I_{m-1}}, a^{i_m}\sim\pi'^{i_m}}[A^{\vec{\pi}, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m})]\). HATRL states that TRL’s surrogate function applied on joint policy can be decomposed into \(n\) ordered summands, the \(m\)-th summand depending only on the \(m\) first policies: \[J_{\text{coop}}(\vec{\pi}') \geq J_{\text{coop}}(\vec{\pi}) +\sumi[m]L_{\vec{\pi}}^{I_m}(\vec{\pi}'^{I_{m-1}}, \pi'^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi^{i_m}\,,\,\pi'^{i_m}\right).\] The \(m\)-th summand can be interpreted as a first order approximation of \(J(\vec{\pi}')-J(\vec{\pi})\) with respect to the \(m\)-th policy for the given order \(I_n\). Hence, instead of maximizing directly \(J(\vec{\pi})\), HATRL tries to maximize each summand of the surrogate function sequentially: \[\pi_{k+1}^{i_m}=\underset{\pi^{i_m}}{\arg\max} \;L_{\vec{\pi}_k}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi_k^{i_m}\,,\,\pi^{i_m}\right).\] To apply this procedure in practical settings with parametrised policies \(\pi_{\theta}^i\) (we usually confound \(\pi_\theta^i\) with its parameters \(\theta^i\) for simplicity), [23] developed Heterogeneous-Agent TRPO (HATRPO) by approximating the KL-penalty with a KL-constraint. The authors also proposed Heterogeneous-Agent PPO (HAPPO), a first order approximation of HATRPO’s objective (see [23] Section 4 for more details, or [24] for broader understanding).

Notice that HATRL can be easily adapted to GSMG by considering the sum of all the reward. Because the expectation is linear, we can define the global value function by summing agent’s value functions (e.g. \(A^{\vec{\pi}}(s,\vec{a})=\sumi A_i^{\vec{\pi}}(s, \vec{a})\)). In that case, the global objective is exactly the utilitarian objective.

2.4 \(\alpha\)-fairness function↩︎

In networking, \(\alpha\)-fairness (alpha-fairness) is an utility function used to determine how resources—typically bandwidth—should be distributed among users. Formally, it is expressed as: \[U_\alpha(x)= \begin{cases} \frac{x^{1-\alpha}}{1-\alpha} & \text{for } \alpha \neq 1, \\ \ln(x) & \text{for } \alpha = 1. \end{cases}\]

The parameter \(\alpha\) controls the level of fairness. When \(\alpha\rightarrow 0\), the efficiency is preferred over how resources are distributed among users. On the other hand, when \(\alpha\) tends to \(+\infty\), the network just cares about the user with the lower resources. For \(\alpha=1\), we obtain the proportional fairness objective ([17]), known to well-balance overall performance and fairness.

3 Heterogeneous Trust Region Learning with Fair Objective↩︎

In this section, the goal is to adapt HATRL for our global fair objective and build the theoretical foundation to learn fair policies. We first introduce a surrogate function for our fair global objective, then we will adapt the sequential update scheme to our new surrogate function and propose a new procedure. Finally, we will study the convergence of our method.

3.1 Fair HATRL↩︎

In this work, we consider a fully-cooperative setting where all the agents aim to maximize the same fair global objective: \[J(\vec{\pi})=\mathbb{E}_{s_0\sim\rho_0}\left[\sum_{i=1}^n U_\alpha \left(\nu+V_i^{\vec{\pi}}(s_0)\right)\right],\] where \(\nu>0\) is a constant to ensure positiveness of the inner expression and \(U_\alpha\) is the \(\alpha\)-fair function.

This objective can model different type of objective functions. When \(\alpha\rightarrow 0\), the global objective tends to the utilitarian objective \(J_{\text{util}}(\vec{\pi})=\mathbb{E}_{s_0\sim\rho_0}\left[\sum_{i=1}^n V_i^{\vec{\pi}}(s_0)\right]\). On the other hand, when \(\alpha\) tends to \(+\infty\), the global objective is equivalent to the Rawlsian welfare function \(J_{\text{Rawls}}(\vec{\pi})=\mathbb{E}_{s_0\sim\rho_0}\left[\min_{i}V_i^{\vec{\pi}}(s_0)\right]\). For \(\alpha=1\), the global objective becomes the proportional fairness objective \(J_{\text{Prop}}(\vec{\pi})=\mathbb{E}_{s_0\sim\rho_0}\left[\sumi[i] \log V_i^{\vec{\pi}}(s_0)\right]\).

To adapt HATRL to our global fair objective, we first introduce some notations.

Definition 1. Let \(\vec{\pi}\) be the joint policies. For any contextualized state \(s=(\tilde{s}, \tilde{c})\) and joint actions \(\vec{a}\in\mathcal{A}\), let us define \(\mathcal{V}_j^{\vec{\pi}}(\tilde{s}, \tilde{c})=\left(\nu+V_j^{\vec{\pi}}(\tilde{c}, \tilde{c})\right)^\alpha\) and the fair advantage function \[\label{equ:fair95advantage95function} A_{F}^{\vec{\pi}}(s,\vec{a})=\sumi[j]\frac{A_j^{\vec{\pi}}(s,\vec{a})}{\mathcal{V}_j^{\vec{\pi}}(s)}.\tag{1}\]

We start by introducing a fundamental lemma which presents a bound for the difference \(J(\vec{\pi}')-J(\vec{\pi})\) with a surrogate function that is similar the one introduced in TRL.

lemmafairsurrogate Let \(\vec{\pi}\) be a policy and \(\vec{\pi}'\) be an other policy. Let us define the surrogate function \(\mathcal{L}_{\vec{\pi}}(\vec{\pi}')=\mathbb{E}_{s\sim d_{\vec{\pi}}, \; \vec{a}\sim\vec{\pi}'(\cdot|s)}\left[A_{F}^{\vec{\pi}}(s,\vec{a}) \right].\)

For the global objective defined previously, the difference \(J(\vec{\pi}')-J(\vec{\pi})\) is bounded and the following inequality \[\mathcal{L}_{\vec{\pi}}(\vec{\pi}') \geq J(\vec{\pi}')-J(\vec{\pi}) \geq \mathcal{L}_{\vec{\pi}}(\vec{\pi}')-C\cdot D_{\text{KL}}^{\max}(\vec{\pi}\;||\; \vec{\pi}')\] holds, where \(C=\frac{4n\alpha \nu^{-1-\alpha}}{(1-\gamma)^2}A_{\max}^2 + \frac{4nA_{\max}\gamma}{\nu^\alpha(1-\gamma)^2 }\) and \(A_{\max}=\max_{j,s,\vec{a}}|A_j^{\vec{\pi}}(s,\vec{a})|\)

See Appendix 9.2 for the proof. The surrogate function is a weighted sum of agent’s advantage function whose weights are dynamically changing and depends on the expected return of each agent for a given initial state. The more an agent is efficient, the greater is its expected return and the less important is its advantage function in the sum – consequently giving more space for other to thrive. Notice that the upper bound is unnecessary for building Fair HATRL but it will be very helpful in the theoretical analysis of HATRL. Now, the lower bound settled, we can introduce the value functions in the HATRL’s style.

Definition 2. Let \(\sigma\) be a permutation of \(\llbracket 1~;~n\rrbracket\). Let \(I_m=\{i_1, \dots,i_m\}\) denote an ordered subset of the shuffled interval, where \(i_k=\sigma(k)\). Let \(-I_m\) refer to its complement. We define the agent \(j\)’s state-action value function as \[Q_j^{\vec{\pi},\, I_m}(s, \, \vec{a}^{I_m})=\mathbb{E}_{\vec{a}^{-I_m}\sim \vec{\pi}^{-I_m}}\left[Q_j^{\vec{\pi}}(s,\, \vec{a}^{I_m}, \vec{a}^{-I_m})\right],\] and for disjoint sets \(J_k\) and \(I_m\), the agent \(j\)’s advantage function is defined as \[A_j^{\vec{\pi},\, I_m}(s, \vec{a}^{J_k}, \vec{a}^{I_m}) = Q_j^{\vec{\pi},\, J_k\sqcup I_m}(s, \, \vec{a}^{J_k\sqcup I_m}) - Q_j^{\vec{\pi},\, J_k}(s, \, \vec{a}^{J_k}).\] Finally, we define the multi-agent fair advantage function as: \[A_F^{\vec{\pi},\, I_m}(s,\vec{a}^{J_k}, \vec{a}^{I_m}) = \sumi[j]\frac{1}{\mathcal{V}_j^{\vec{\pi}}(s)}A_j^{\vec{\pi},\, I_m}(s, \vec{a}^{J_k}, \vec{a}^{I_m})\]

We now introduce a pivotal lemma which states that the fair advantage function can be split into a summation of each agent’s local advantages.

lemmaadvantagedecomp For any agent j and subset \(I_m\subseteq I_n\), we have \[A_F^{\vec{\pi},\, I_m}(s, \vec{a}^{I_m}) = A_F^{\vec{\pi},\, I_m}(s, a^{\varnothing}, \vec{a}^{I_m})=\sum_{l=1}^m A_F^{\vec{\pi},\, i_l}(s, \vec{a}^{I_{l-1}}, a^{i_l})\]

See Appendix [sec:proof95lemma953462] for the proof. This lemma is the foundation for sequential update. Let \(I_n\) be an arbitrary order. Suppose agent \(i_1\) takes the first action \(a^{i_1}\)such that it improves its local fair advantage function, the subsequent agent \(i_m\) can then sample its own action \(a^{i_m}\) by taking into account the actions drawn by the preceding agents such that its action also improves its local fair advantage function – then resulting into monotonic improvement. To formalize this intuition, we need the following definitions.

Definition 3. Let \(\vec{\pi}\) be a joint policy, \(\vec{\pi}'^{I_{m-1}}\) be some other joint policy of agents \(I_{m-1}\), and \(\pi'^{i_m}\) be some other policy of agent \(i_m\). Then \[\mathcal{L}_{\vec{\pi}}^{I_m}(\vec{\pi}'^{I_{m-1}}, \pi'^{i_m})=\mathbb{E}_{s_\sim d_{\vec{\pi}}, \;\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}}(.|s), \, a^{i_m}\sim\pi'^{i_m}(.|s)}\left[A_F^{\vec{\pi},\,i_m}\left(s, \vec{a} ^{I_{m-1}}, a^{i_m}\right)\right]\] Note that, for any \(\vec{\pi}'^{I_{m-1}}\) and \(\pi'^{i_m}=\pi^{i_m}\) \[\mathcal{L}_{\vec{\pi}}^{I_m}(\vec{\pi}'^{I_{m-1}}, \pi^{i_m})=0\]

Thanks to lemma and theorem, we can generalize HATRL to our global fair objective.

lemmasurrogatedecomp Let \(\vec{\pi}\) and \(\vec{\pi}'\) be two joint policies, and \(I_n\) an order, the surrogate function can be decomposed into \(n\) summands: \[J(\vec{\pi}')-J(\vec{\pi})\geq \sumi[m]\mathcal{L}_{\vec{\pi}}^{I_m}(\vec{\pi}'^{I_{m-1}}, \pi'^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi^{i_m}\,,\,\pi'^ {i_m}\right).\]

See Appendix 9.4 for the proof. This remarkable statement gives an idea about how a joint policy can be improved to maximize our global fair objective. Specifically, we can sequentially update agents policy by maximizing its corresponding summand \(\mathcal{L}_{\vec{\pi}}^{I_m}(\vec{\pi}'^{I_{m-1}}, \pi'^{i_m}) - CD_{\text{KL}}^{\max}\left(\pi^{i_m}\,,\,\pi'^ {i_m}\right)\) which can always be positive as we can nullify the latter by making no policy update. Therefore, any policy updates that lead to a positive summand improves the overall summation. Hence, we propose the following algorithm.

Figure 1: Multi-Agent Policy Iteration with Monotonic Improvement Guarantee

3.2 Theoretical analysis↩︎

In this section, we highlight the link between the surrogate function and the global fair objective. We first introduce a directional derivative definition.

definitiongateaux(Gâteaux Derivative) Let \(\vec{\pi},\vec{\pi}'\) be two joint policies and \(\eta>0\) a positive number. Let us define the perturbed policies \(\pi_\eta^i=\pi^i+\eta(\pi'^i-\pi^i)\), all together define the joint perturbed policy \(\vec{\pi}_\eta\). If the limit exists, we define the Gateaux derivative of a function \(f(\vec{\pi})\) as \(\mathfrak D_{\vec{\pi}'}f(\vec{\pi})=\lim_{\eta\rightarrow 0}\frac{f(\vec{\pi}_\eta)-f(\vec{\pi})}{\eta}\).

The surrogate function is actually the Gateaux derivative of \(J(\vec{\pi})\) in the \(\vec{\pi}'\) direction.

lemmasurrogategateaux Let \(\vec{\pi}\) be a policy and \(\vec{\pi}'\) be another policy. The following statement holds: \(\mathfrak D_{\vec{\pi}'}J(\vec{\pi})=\mathcal{L}_{\vec{\pi}}(\vec{\pi}')\).

See Appendix 9.5 for the proof. The lemma provides a deeper understanding of Fair HATRL. Indeed, at each iteration \(k+1\), the current joint policy \(\vec{\pi}_k\) is moving toward the joint policy \(\vec{\pi}'\) with the steepest slope to climb that remains in the trust region. Notice that similar result has be been shown for TRL.

Now we state the main properties enjoyed by Algorithm 1. We first need to introduce the following solution concept.

Definition 4 (Nash equilibrium). In a fully-cooperative game, a joint policy \(\vec{\pi}_*=(\pi_*^1,\dots,\pi_*^n)\) is a Nash equilibrium (NE) if for every \(i\in N\), \(\piî\in\Pi^i\) implies \(J(\vec{\pi}_*)\geq J(\pi^i, \vec{\pi}_*^{-i})\).

NE ([26]) is common game-theory solution concept introduced by Nash. It describes an equilibrium where no agent can improve the global objective by deviating alone from its NE policy.

theoremconvergence Supposing in Algorithm 1 any permutation of agents has a fixed non-zero probability to begin the update, the joint policies induced by the learning algorithm enjoy the following properties:

Monotonic Improvement property: \(J(\vec{\pi}_{k+1})\geq J(\vec{\pi}_k)\),
The fair global objective converges: \(\lim_{k\rightarrow\infty}J(\vec{\pi}_k)=J_\infty\),
The set of joint policies’ limit points is non empty, each of which is a Nash equilibrium.

See Appendix 9.6 for the proof. The monotonic improvement and the convergence of the global fair objective is pretty straightforward. The characterization of the limit points provides some guarantee about the convergence of Fair-HATRL.

4 Practical algorithms↩︎

In practical settings, we employ Deep Reinforcement Learning (DRL) by parameterizing each agent’s policy \(\pi^i\) with \(\theta^i\) to accommodate high-dimensional state and action spaces. For brevity, we denote the policy \(\pi^i_{\theta^i}\) simply as \(\theta^i\) where the context is clear. Fair-HATRL and HATRL share a core architectural framework; specifically, Fair-HATRL can be obtained from HATRL by substituting the standard multi-agent advantage function with our proposed global fair advantage function. Since both functions share the same analytical properties, we provide a high-level overview of the practical implementation below and refer the reader to [23] for further details.

4.1 \(\alpha\)-fair HATRPO↩︎

Similarly to HATRPO ([23]) and TRPO ([9]), we replace the KL-penalty by a KL-constraint to avoid computing \(C\) and \(D_{\text{KL}}^{\max}\left(\theta^{i_m}_k\,,\,\theta^{i_m}\right)\) in Algorithm 1. Formally, at every iteration \(k+1\), given a permutation \(I_n\), Fair-HATRPO sequentially optimises agent \(i_m\) policy parameters \(\theta^{i_m}_{k+1}\) by solving the following optimization problem for a given a KL-radius \(\delta>0\): \[\begin{align} \theta^{i_m}_{k+1}=\underset{\theta^{i_m}}{\arg\max}\;\;\mathbb{E}_{s_\sim d_{\vec{\theta}_k}, \;\vec{a}^{I_{m-1}}\sim\vec{\theta}_{k+1}^{I_{m-1}}(.|s), \, a^{i_m}\sim\theta^{i_m}(.|s)}\left[A_F^{\vec{\theta}_k,\,i_m}\left(s, \vec{a} ^{I_{m-1}}, a^{i_m}\right)\right] \\ \text{subject to } \underset{s\sim d_{\vec{\theta}_k}}{\mathbb{E}}\left[D_{\text{KL}}\left(\theta^{i_m}_k(\cdot|s),\theta^{i_m}(\cdot|s)\right)\right] \leq \delta. \qquad\qquad\quad \end{align}\]

One can solve this constrained optimization problem by using a linear approximation to the objective function and a quadratic approximation of the KL-constraint leading to the following update rule: \[\theta_{k+1}^{i_m} = \theta_k^{i_m} + \beta^j \sqrt{\frac{2\delta}{g_k^{i_m} (H_k^{i_m})^{-1} g_k^{i_m}}} (H_k^{i_m})^{-1} g_k^{i_m} ,\] where \(H_k^{i_m} = \nabla_{\theta^{i_m}}^2 \mathbb{E}_{s \sim d_{\vec{\theta}_k}} \left[ \text{D}_{\text{KL}} \left( \theta_k^{i_m} (\cdot | s), \theta^{i_m} (\cdot | s) \right) \right] \Big|_{\theta^{i_m} = \theta_k^{i_m}}\) is the Hessian of the expected KL-divergence, \(g_k^{i_m}\) is the gradient of the objective function, \(\beta^j\) is computed via backtracking line search, and the product \((H_k^{i_m})^{-1}g_k^{i_m}\) can be efficiently computed using the conjugate gradient algorithm.

For a given batch \(\mathcal{B}\) of trajectories with length \(T\), let \(\hat{A}^{\vec{\theta}_k}_F(s,\vec{a})\) be the estimator of the fair advantage function \(A^{\vec{\theta}_k}_F(s,\vec{a})\). Then, the gradient of the objective function can be estimated using the following formula: \[\hat{g}_{k}^{i_{m}}=\frac{1}{|\mathcal{B}|} \sum_{\tau \in \mathcal{B}} \sum_{t=0}^{T} M_F^{I_m}\left(s_{t}, \vec{a}_{t}\right) \nabla_{\theta^{i_{m}}} \log \pi_{\theta^{i_{m}}}^{i_{m}}\left(a_{t}^{i_m} | s_{t}\right)|_{\theta^{i_{m}}=\theta_{k}^{i_{m}}} .\] where \(M^{I_m}_F = \frac{\vec{\pi}'^{I_{m-1}}(\vec{a}^{I_{m-1}} | s)}{\vec{\pi}^{I_{m-1}}(\mathbf{a}^{I_{m-1}} | s)} \hat{A}_F^{\vec{\theta}_k}(s, \vec{a})\). The estimator of the fair advantage function is estimated from individual state-value functions’ estimates (by the individual critic) and individual advantage functions’ estimates (like GAE–[27]).

4.2 \(\alpha\)-fair HAPPO↩︎

Similarly to HAPPO and PPO, we propose a first order approximation and avoid the computation of the hessian \(H_k^{i_m}\). Thus, agent \(i_m\) updates its parameter \(\theta^{i_m}\) by maximizing the following clipping objective \[\mathbb{E}_{s \sim d_{\vec{\theta}_k}, \vec{a} \sim \vec{\theta}_{k}}\left[\min \left(\frac{\pi_{\theta^{i m}}^{i_{m}}\left(a^{i_m} | s\right)}{\pi_{\theta_{k}^{i m}}^{i_{m}}\left(a^{i_m} | \mathrm{s}\right)} M^{I_m}(s, \vec{a}), \operatorname{clip}\left(\frac{\pi_{\theta^{i m}}^{i_{m}}\left(a^{i_m} | s\right)}{\pi_{\theta_{k}^{i_m}}^{i_{m}}\left(a^{i_m} | s\right)}, 1 \pm \epsilon\right) M^{I_m}(s, \vec{a})\right)\right] .\]

5 Experiments and Results↩︎

Finally, we test both our algorithms on two SSD – CleanUp and Harvest ([7]) – against state-of-the-art algorithms. We built our experiments upon the environments provided by SocialJax ([28]). All hyperparameter settings and implementations details can be found in Appendix 11.3. Simulations were done on two RTX 4090 (24GB VRAM).

5.1 Environments and Baselines↩︎

Harvest presents a "tragedy of the commons" scenario where agents must balance their individual desire to collect apples with the need for collective restraint, as the resource only regenerates if a sufficient population of apples is maintained. In contrast, CleanUp models a public goods dilemma where agents face a conflict between harvesting apples and performing the labor-intensive task of cleaning a river; because apples only grow when the river is under a certain level of pollutants, agents must navigate the tension between contributing to the environment and free-riding on the efforts of others.

We compare both FHATRPO and FHAPPO for different values of \(\alpha\in\{0.5, 1,1.5\}\) and study the influence of that parameter on the efficiency and the fairness. We also test our algorithms against SOTA algorithms : HATRPO/HAPPO with global reward and FMAPPO with altruism level of 1 [5]. FMAPPO is based on the Proportional fairness objective and uses an PPO objective extrapolated from the gradient derivation with no theoretical guarantees.

5.2 Results↩︎

We decide to do the comparison on two metrics : the total apples consumed (TAC) which measure the overall efficiency of the agents and the Gini index which measure how equal the utility distribution is. Other metrics can be found in Appendix 11.3.

Common Harvest. The Figure 2 presents the results obtained on Common Harvest. All the algorithms successfully learn the complexity of the environment. Interestingly, our FHATRPO and FHAPPO seem to perform slightly better than their baselines while reaching lower level of Gini index. Moreover, it seems that the higher \(\alpha\) is, the fairer the outcome is except for \(1.5\)-FHAPPO which is probably due to the hard hyperparameter tuning. On the other hand, FMAPPO seems to perform pretty well. It levels FHATRPO on both TAC and Gini index and outperformed FHAPPO on pure efficiency. Nonetheless, FHAPPO reaches socially better result with a lower Gini index.

Figure 2: Results on Common Harvest. Each line is obtained by averaging its actual value on a rolling window of size 100 and its shaded area corresponds to its minimum and maximum on the same rolling window.

CleanUp Results are presented in Figure 3. We can draw similar conclusion compared to Harvest ; especially that higher value of \(\alpha\) leads to fairer outcomes. Nonetheless, the efficiency advantage of our fair algorithm is minimal and FMAPPO seems to be better than our fair algorithms. We also notice that FHAPPO struggles for \(\alpha=1.5\) as the learning curve suffered from high drop of TAC.

Figure 3: Results on CleanUp. Each line is obtained by averaging its actual value on a rolling window of size 100 and its shaded area corresponds to its minimum and maximum on the same rolling window.

6 Discussions and limitations↩︎

During hyperparameter optimization, we observed significant performance degradation for high values of \(\alpha\) (specifically, \(\alpha > 1\)). As \(\alpha\) increases, the fair advantage function (Equation 1 ) effectively diminishes the weights of agents performing above the collective average, causing their corresponding terms in the summation to vanish. Consequently, the global objective becomes heavily biased toward the lowest-performing agents. This creates a high sensitivity to the "worst learners"; if these agents fail to explore effectively or hit a local optimum, the resulting gradients in the fair advantage function become volatile, leading to training instability. Using smaller KL-constraint/PPO-clipping can partially solve this issue.

On the other hand, the \(\alpha\)-fair HATRL framework suffers from several limitations. Namely, it relies on a strong theoretical constraint : positive bounded reward which narrows down the usable environments. Moreover, \(\alpha\)-fair HATRPO and \(\alpha\)-fair HAPPO require fully-observable state which is rarely the case in real world situation. Approximation using observation-based estimator with Recurent Neural Network can mitigate this but lack the theoretical properties.

7 Conclusion↩︎

This work introduces a novel framework that bridges \(\alpha\)-fairness with Heterogeneous-Agent Trust Region Learning (HATRL), successfully filling the gap between equitable objective functions and theoretically grounded learning. We proved that our approach provides monotonic improvement and convergence toward Nash Equilibria in Positive Markov games. Practically, our developed algorithms—\(\alpha\)-fair HATRPO and \(\alpha\)-fair HAPPO—demonstrated in sequential social dilemmas like CleanUp and CommonHarvest that they can achieve significantly better fairness (lower Gini indices) while maintaining high utilitarian efficiency. This framework establishes a mathematically safe foundation for training agents to adopt sustainable, pro-social behaviors in complex multi-agent systems. For future work, we suggest to investigate mechanism to enhance exploration like entropy normalization or adaptive KL-constraint/PPO-clipping that freezes the best learners and improves the worst.

Use unnumbered first level headings for the acknowledgments. All acknowledgments go at the end of the paper before the list of references. Moreover, you are required to declare funding (financial activities supporting the submitted work) and competing interests (related financial activities outside the submitted work). More information about this disclosure can be found at: https://neurips.cc/Conferences/2026/PaperInformation/FundingDisclosure.

Do not include this section in the anonymized submission, only in the final paper. You can use the ack environment provided in the style file to automatically hide this section in the anonymized submission.

8 Preliminaries↩︎

8.1 Assumptions and Definitions↩︎

We use the same assumption as in HATRL [23]:

Assumption 1. There exists \(\eta \in \mathbb{R}\), such that \(0 < \eta \ll 1\), and for every agent \(i \in \mathcal{N}\), the policy space \(\Pi^i\) is \(\eta\)-soft; that means that for every \(\pi^i \in \Pi^i\), \(s \in \mathcal{S}\), and \(a^i \in \mathcal{A}^i\), we have \(\pi^i(a^i|s) \geq \eta\).

Definition 5. Let \(X\) be a finite set and \(p: X \rightarrow \mathbb{R}\), \(q: X \rightarrow \mathbb{R}\) be two maps. Then, the notion of distance between \(p\) and \(q\) that we adopt is given by \(\|p - q\| \triangleq \max_{x \in X} |p(x) - q(x)|\).

We also introduce the new probability distribution for the contextualized state:

Definition 6. Let \(\tilde{\mathcal{M}}=(N, \tilde{\mathcal{S}}, \{\mathcal{A}_i\}_{i \in N}, \tilde{P}, \tilde{\rho}_0, \{\tilde{r}_i\}_{i \in N}, \gamma)\) be a Markov game. We define the Markov game \(\mathcal{M}=(N, \mathcal{S}, \{\mathcal{A}_i\}_{i \in N}, P, \rho_0, \{r_i\}_{i \in N}, \gamma)\) for the contextualized state \(\mathcal{S}=\tilde{\mathcal{S}}\times\tilde{\mathcal{S}}\) where for any contextualized state \(s=(\tilde{s}, \tilde{c})\):

\(\rho_0(s)=\rho_0(\tilde{s}, \tilde{c})=\tilde{\rho}_0(\tilde{s})\mathbb{1}_{\{\tilde{s}=\tilde{c}\}}\) is the initial state distribution,
for any joint action \(\vec{a}\in \mathcal{A}\) and other state \(s'\), \(P(s,\vec{a}, s')=\tilde{P}(\tilde{s}, \vec{a}, \tilde{s}')\mathbb{1}_{\{\tilde{c}'=\tilde{c}\}}\) is the transition kernel,
for any agent \(i\) and joint action \(\vec{a}\), \(r_i(s, \vec{a})=\tilde{r}_i(\tilde{s},\vec{a})\) is the reward function.

8.2 Preliminary results↩︎

Lemma 1. Every agent \(i\)’s policy space \(\Pi_i\) is convex and compact under the maximum norm.

Lemma 2. The improper state distribution \(d_{\vec{\pi}}\) is continuous in \(\vec{\pi}\).

Lemma 3. Let \(\vec{\pi}\) be a policy. Then, for any agent \(i\), \(Q_i^{\vec{\pi}}(s,\vec{a})\) is Lipsichtz-continuous in \(\vec{\pi}\).

Proof. For proof of the lemmas 1, 2, 3, see [23] (Appendix A.2 Lemma 3, 4, 5). Notice that in [23], the authors prove the lemmas for a global reward function but the proof holds for any reward functions. The proof relies on the Bellman Equations for \(Q_\pi\) (see [29], Chapter 3.5) which also hold in our Multi-agent settings. ◻

Lemma 4. The function \(U_\alpha\) is Lipschitz-continuous on \(\mathbb{R}^+\).

Proof. Let us recall \(U_\alpha(x)=\frac{x^{1-\alpha}}{1-\alpha}\) for \(\alpha\neq 1\) and \(U_\alpha(x)=\ln(x)\) for \(\alpha=1\).

The \(\alpha\)-fairness function is differentiable on \([\nu;+\infty[\) and for any \(\alpha\geq 0\), \[U_\alpha'(x)=x^{-\alpha}\]

On \([\nu;+\infty[\), \(\left|U_\alpha'(x)\right|\) is bounded by \(\epsilon^{-\alpha}\). Thus, \(U_\alpha\) is Lipschitz-continuous with constant \(\nu^{-\alpha}\). ◻

Corollary 1. From Lemma 3 and Lemma 4, for any agent \(i\), we obtain that the following functions are Lipschitz-continuous in \(\pi\):

the state value function \(V_i^{\vec{\pi}}(s) = \sum_{\vec{a}} \vec{\pi}(\vec{a}|s)Q_i^{\vec{\pi}}(s, \vec{a})\),
the advantage function \(A_i^{\vec{\pi}}(s, \vec{a}) = Q_i^{\vec{\pi}}(s, \vec{a}) - V_i ^{\vec{\pi}}(s)\),
the fair global objective \(J(\vec{\pi}) = \mathbb{E}_{s \sim \rho_0} [\sumi[i] U_\alpha\left(\nu + V_i^{\vec{\pi}}(s)\right)]\),
and the fair advantage function \(A_F^{\vec{\pi}}(s,\vec{a})=\sumi[j]\frac{A_j^{\vec{\pi}}(s,\vec{a})}{\mathcal{V}_j^{\vec{\pi}}(s)}\)

Lemma 5. Let \(\vec{\pi}\) and \(\vec{\pi}'\) be some policies. The quantity \(\mathbb{E}_{s\sim d_{\vec{\pi}}, \vec{a}\sim \vec{\pi}'(\cdot|s)}\left[A_F^{\vec{\pi}}(s,\vec{a})\right]\) is continuous with \(\vec{\pi}\).

Proof. We have \[\mathbb{E}_{s\sim d_{\vec{\pi}}, \vec{a}\sim \vec{\pi}'(\cdot|s)}\left[A_F^{\vec{\pi}}(s,\vec{a})\right]=\sum_s\sum_{\vec{a}}d_{\vec{\pi}}(s)\vec{\pi}(\vec{a}|s) A_F^{\vec{\pi}}(s,\vec{a}),\] the continuity is induced by continuity of \(d_{\vec{\pi}}\) (Lemma 2) and \(A_F^{\vec{\pi}}\) (Corollary 1). ◻

9 Heterogeneous Agent Trust Region Learning with fair objective↩︎

In this section, the goal is to build a Trust Region Learning framework for the global objective we defined previously.

9.1 Previous results↩︎

In this section, we list the useful lemma proved in TRL [9] that holds in our multi-agent settings.

Lemma 6. Let \(\vec{\pi}\) and \(\vec{\pi}'\) be two stochastic policies’ profiles. For any agent \(i\), the difference in their expected returns for a given initial state \(s_0\in \mathcal{S}\) is given by:

\[V_i^{\vec{\pi}'}(s_0) - V_i^{\vec{\pi}}(s_0) = \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t A_i^{\vec{\pi}}(s_t, \vec{a}_t) \mid s_0 \right]\]

Proof. The proof is similar to the performance difference lemma demonstrated in [9] (Lemma 1) or in [30] (Lemma 6.1): \[\begin{align} \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t A_i^{\vec{\pi}}(s_t, \vec{a}_t) \mid s_0 \right] &= \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t \left( r_i(s_t, \vec{a}_t) + \gamma V_i^{\vec{\pi}}(s_{t+1}) - V_i^{\vec{\pi}}(s_t) \right) \mid s_0 \right] \\ &= \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t r_i(s_t, \vec{a}_t) \mid s_0 \right] \\ &\qquad\qquad\qquad+ \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t \left( \gamma V_i^{\vec{\pi}}(s_{t+1}) - V^{\vec{\pi}}(s_t) \right) \mid s_0 \right] \\ &= V_i^{\vec{\pi}'}(s_0) + \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \left( \gamma^{t+1} V_i^{\vec{\pi}}(s_{t+1}) - \gamma^t V_i^{\vec{\pi}}(s_t) \right) \mid s_0 \right] \\ &= V_i^{\vec{\pi}'}(s_0) + \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ -V_i^{\vec{\pi}}(s_0) + \lim_{T \to \infty} \gamma^T V_i^{\vec{\pi}}(s_T) \mid s_0 \right]\\ &= V_i^{\vec{\pi}'}(s_0) - V_i^{\vec{\pi}}(s_0) \end{align}\] ◻

Lemma 7. For any agent \(i\), any state \(s \in \mathcal{S}\) and a joint strategy profile \(\vec{\pi}\), the following result holds: \[\mathbb{E}_{\vec{a} \sim \vec{\pi}(\cdot|s)} [A_i^{\vec{\pi}}(s, \vec{a})] = 0\]

Proof. For any state \(s\), we have \[\begin{align} \mathbb{E}_{\vec{a} \sim \vec{\pi}(\cdot|s)} [A_i^{\vec{\pi}}(s, \vec{a})] &=\mathbb{E}_{\vec{a} \sim \vec{\pi}(\cdot|s)} [Q_i^{\vec{\pi}}(s, \vec{a}) - V_i^{\vec{\pi}}(s)] \\ &= \mathbb{E}_{\vec{a} \sim \vec{\pi}(\cdot|s)} [Q_i^{\vec{\pi}}(s, \vec{a})] - \mathbb{E}_{\vec{a} \sim \vec{\pi}(\cdot|s)} [V_i^{\vec{\pi}}(s)]\\ &=V_i^{\vec{\pi}}(s) - V_i^{\vec{\pi}}(s) \\ &= 0 \end{align}\] ◻

Lemma 8. Let us define \(\bar{A}_i^{\vec{\pi}',\, \vec{\pi}}(s)=\mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)} \left[A_i^{\vec{\pi}}(s, \vec{a})\right]\). For any state \(s \in \mathcal{S}\) and any \(\kappa\)-coupled policy pair \((\vec{\pi},\vec{\pi}')\), the magnitude of the expected joint advantage function \(A^{\vec{\pi}}(s, \vec{a})\) evaluated under the policy \(\vec{\pi}'\) is upper-bounded by the Total Variation (TV) distance between the two profiles: \[\left| \mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)} [A_i^{\vec{\pi}}(s, \vec{a})] \right| \leq 2 D_{\text{TV}}\left(\vec{\pi}'(\cdot|s) \parallel \vec{\pi}(\cdot|s)\right) \max_{\vec{a}} |A_i^{\vec{\pi}}(s, \vec{a})|\]

Proof. We use the previous Lemma 7 to write \(0\) differently: \[\begin{align} \left|\bar{A}_i^{\vec{\pi}',\, \vec{\pi}}(s)\right| &=\left| \mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)} \left[A_i^{\vec{\pi}}(s, \vec{a})\right] \right| \\ &= \left| \mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)} [A_i^{\vec{\pi}}(s, \vec{a})] - \mathbb{E}_{\vec{a} \sim \vec{\pi}(\cdot|s)} [A_i^{\vec{\pi}}(s, \vec{a})] \right| \\ &= \left| \sum_{\vec{a}} \left( \vec{\pi}'(\vec{a}|s) - \vec{\pi}(\vec{a}|s) \right) A_i^{\vec{\pi}}(s, \vec{a}) \right| \\ &\leq \sum_{\vec{a}} \left| \vec{\pi}'(\vec{a}|s) - \vec{\pi}(\vec{a}|s) \right| \cdot \max_{\vec{a}} |A_i^{\vec{\pi}}(s, \vec{a})| \\ &\leq 2 \epsilon_i(s) D_{\text{TV}}(\vec{\pi}'(\cdot|s) \parallel \vec{\pi}(\cdot|s)), \end{align}\] where \(\epsilon_i(s)=\max_{\vec{a}}|A_i^{\vec{\pi}}(s, \vec{a})|\). ◻

Lemma 9. Let \(\kappa=D_{\text{KL}}^{\max}\left(\vec{\pi}\,,\,\vec{\pi}'\right)=\max_sD_{\text{KL}}\left(\vec{\pi}(\cdot|s), \vec{\pi}'(\cdot|s)\right)\) Let \((\vec{\pi}, \vec{\pi}')\) be an \(\kappa\)-coupled policy pair. Then, the following statement holds: \[\begin{align} \left| \mathbb{E}_{s_t \sim \vec{\pi}'} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] - \mathbb{E}_{s_t \sim\vec{\pi}} [A_i^{\vec{\pi}',\, \vec{\pi}} (s_t)] \right| &\leq 4\kappa \max_{s,a} |A_i^{\vec{\pi}}(s, a)| \\ &\le 4\kappa(1 - (1 - \kappa)^t) \max_{s,a} |A_i^{\vec{\pi}}(s, a)| \end{align}\]

Proof. Let \(\kappa=D_{\text{KL}}^{\max}\left(\vec{\pi}\,,\,\vec{\pi}'\right)\), then we can define an \(\kappa\)-coupled policy pair \((\vec{\pi},\vec{\pi}')\) such that \[\mathbb{P}(\vec{a}_k \neq \vec{a}'_k | s_k) \le \kappa.\] See [31] (proposition 4.7). Hence, the probability that the two policies disagree on an action at any given time step is bounded by \(\kappa\).

Let \(n_t\) be the number of times the policies diverge before time step \(t\). The probability that they agree on all steps up to \(t-1\) is at least \((1 - \kappa)^t\). \[\mathbb{E}_{s_t \sim \vec{\pi}'} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] = \mathbb{P}(n_t = 0) \mathbb{E}_{s_t \sim \vec{\pi}' | n_t = 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] + \mathbb{P}(n_t > 0) \mathbb{E}_{s_t \sim \vec{\pi}' | n_t > 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)]\]

Similarly for the policy \(\vec{\pi}\):

\[\mathbb{E}_{s_t \sim \vec{\pi}} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] = \mathbb{P}(n_t = 0) \mathbb{E}_{s_t \sim \vec{\pi} | n_t = 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] + \mathbb{P}(n_t > 0) \mathbb{E}_{s_t \sim \vec{\pi} | n_t > 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)]\]

Note that \(n_t=0\) terms are equal as it means that \(\vec{\pi}\) and \(\vec{\pi}'\) agreed on all the timesteps less than \(t\): \[\mathbb{E}_{s_t \sim \vec{\pi} | n_t = 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)]= \mathbb{E}_{s_t \sim \vec{\pi}' | n_t = 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)]\]

By definition, the probability that they disagree at least once before time \(t\) is bounded by: \[\mathbb{P}(n_t > 0) \le 1 - (1 - \kappa)^t\]

Then, we have

\[\begin{align} |\mathbb{E}_{s_t \sim \vec{\pi}' | n_t > 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] - \mathbb{E}_{s_t \sim \pi | n_t > 0}& [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)]| \\ &\leq |\mathbb{E}_{s_t \sim \tilde{\pi} | n_t > 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)]| + |\mathbb{E}_{s_t \sim \pi | n_t > 0} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)]| \\ &\leq 4\kappa \max_{s,a} |A_i^{\vec{\pi}}(s, a)| \end{align}\]

Therefore, using Lemma 8, we have \[\begin{align} \left| \mathbb{E}_{s_t \sim \vec{\pi}'} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] - \mathbb{E}_{s_t \sim\vec{\pi}} [A_i^{\vec{\pi}',\, \vec{\pi}}(s_t)] \right| &\le 2(1 - (1 - \kappa)^t) \max_s |\bar{A}_i^{\vec{\pi}',\, \vec{\pi}}(s)| \\ &\le 4\kappa(1 - (1 - \kappa)^t) \max_{s,a} |A_i^{\vec{\pi}}(s, a)| \end{align}\] ◻

9.2 Proof of Lemma [lem:fair95surrogate]↩︎

Proof. We are looking for a lower bound of \(J(\vec{\pi}')-J(\vec{\pi})\). \[J(\vec{\pi}')-J(\vec{\pi})= \mathbb{E}_{s_0\sim\rho_0}\left[\sumi U_{\alpha}\left(\epsilon+\vf{'}(s_0)\right) - U_{\alpha}\left(\epsilon+\vf{}(s_0)\right)\right]\]

As \(U_{\alpha}\) is concave, one interesting property is by \[\frac{y-x}{x^\alpha}\geq U_{\alpha}(y)-U_{\alpha}(x)\geq \frac{y-x}{y^\alpha}.\]

Applying this property to the previous difference and using Lemma 6 gives the lower bound \[\begin{align} J(\vec{\pi}')-J(\vec{\pi}) &\geq \mathbb{E}_{s_0\sim\rho_0}\left[\frac{\vf{'}(s_0)-\vf{}(s_0)}{\calvf{'}(s_0)}\right] \\ &= \mathbb{E}_{s_0\sim\rho_0}\left[\sumi \frac{1}{\calvf{'}(s_0)}\mathbb{E}_{\tau \sim \vec{\pi}'|s_0} \left[ \sum_{t=0}^{\infty} \gamma^t A_j^{\vec{\pi}}(s_t, \vec{a}_t) \right]\right]\\ &= \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t \left(\sumi \frac{A_j^{\vec{\pi}}(s_t, \vec{a}_t)}{\calvf['](s_0)}\right) \right] \\ &= \mathcal{F}_{\vec{\pi}}(\vec{\pi}'), \end{align}\] and the upper bound \[\begin{align} J(\vec{\pi}')-J(\vec{\pi}) &\leq \mathbb{E}_{s_0\sim\rho_0}\left[\frac{\vf{'}(s_0)-\vf{}(s_0)}{\calvf(s_0)}\right] \\ &= \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t \left(\sumi \frac{A_j^{\vec{\pi}}(s_t, \vec{a}_t)}{\calvf['](s_0)}\right) \right] \\ &= \mathcal{L}_{\vec{\pi}}(\vec{\pi}'). \end{align}\]

Let us define \(A_j^{\vec{\pi}', \vec{\pi}}(s)=\mathbb{E}_{\vec{a}\sim \vec{\pi}'(\cdot|s)}\left[A_j^{\vec{\pi}}(s, \vec{a})\right]\). Using that notation and conditional expectation, we have \[\begin{align} \mathcal{F}_{\vec{\pi}}(\vec{\pi}')= \mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t \left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s_t)}{\calvf['](s_0)}\right) \right] \end{align}\]

As \(s_t=(\tilde{s}_t, \tilde{s}_0)\) carries the initial state, we can drop the initial state dependency in the denominator:

\[\begin{align} \mathcal{F}_{\vec{\pi}}(\vec{\pi}') &=\mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t \left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s_t)}{\calvf['](s_0)}\right) \right]\notag\\ &= \sum_s\rho_0(s)\sum_{t=0}^\infty\gamma^t \sum_{s'}\mathbb{P}_{\vec{\pi}'}(s_t=s'\,|\, s_0=s) \left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s')}{\calvf['](s_0)}\right) \notag\\ &=\sum_{\tilde{s},\,\tilde{c}}\rho_0(\tilde{s})\mathbb{1}_{\{\tilde{s} = \tilde{c}\}}\sum_{t=0}^\infty\gamma^t \sum_{\tilde{s}', \tilde{c}'}\mathbb{P}_{\vec{\pi}'}(\tilde{s}_t=\tilde{s}'\,|\, \tilde{s}_0=\tilde{s})\mathbb{1}_{\{\tilde{c}' = \tilde{c}\}} \left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(\tilde{s}', \tilde{c}')}{\calvf['](\tilde{s}, \tilde{c})}\right) \notag\\ &=\sum_{\tilde{s},\,\tilde{c}}\rho_0(\tilde{s})\mathbb{1}_{\{\tilde{s} = \tilde{c}\}}\sum_{t=0}^\infty\gamma^t \sum_{\tilde{s}', \tilde{c}'}\mathbb{P}_{\vec{\pi}'}(\tilde{s}_t=\tilde{s}'\,|\, \tilde{s}_0=\tilde{s})\mathbb{1}_{\{\tilde{c}' = \tilde{c}\}} \left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(\tilde{s}', \tilde{c}')}{\calvf['](\tilde{c}', \tilde{c}')}\right) \notag\\ &=\sum_{\tilde{s},\,\tilde{c}}\rho_0(\tilde{s})\mathbb{1}_{\{\tilde{s} = \tilde{c}\}} \sum_{\tilde{s}', \tilde{c}'}\sum_{t=0}^\infty\gamma^t\mathbb{P}_{\vec{\pi}'}(\tilde{s}_t=\tilde{s}'\,|\, \tilde{s}_0=\tilde{s})\mathbb{1}_{\{\tilde{c}' = \tilde{c}\}} \left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(\tilde{s}', \tilde{c}')}{\calvf['](\tilde{c}', \tilde{c}')}\right) \notag\\ &=\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf['](s)} \right] \end{align}\]

Because the value function and the state distribution of the other policy \(\vec{\pi} '\) are unknown, we want to bound \(\mathcal{F}_{\vec{\pi}}(\vec{\pi}')\) by \(\vec{\pi}\)-depended functions. Therefore, let us consider the following function: \[\mathcal{L}_{\vec{\pi}}(\vec{\pi}')=\mathbb{E}_{s \sim d_{\vec{\pi}}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]\]

We now want to bound the absolute difference of \(|\mathcal{F}_{\vec{\pi}}(\vec{\pi}') - \mathcal{L}_{\vec{\pi}}(\vec{\pi}')|\): \[\begin{align} |\mathcal{F}_{\vec{\pi}}(\vec{\pi}') - \mathcal{L}_{\vec{\pi}}(\vec{\pi}')| &=\left|\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf['](s)} \right]-\mathbb{E}_{s \sim d_{\vec{\pi}}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]\right| \\[2ex] &\leq \underbrace{\left|\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf['](s)} \right] -\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]\right|}_{=\Delta_1}\nonumber\\[2ex] &\qquad + \underbrace{\left|\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]-\mathbb{E}_{s \sim d_{\vec{\pi}}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]\right|}_{=\Delta_2} \end{align}\]

The first error \(\Delta_1\) is due to a shift of state value functions between the two policies \(\vec{\pi}\) and \(\vec{\pi} '\):

\[\begin{align} \Delta_1 &=\left|\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf['](s)} \right] -\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]\right| \\ &=\left|\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \left(\frac{1}{\calvf['](s)} -\frac{1}{\calvf(s)}\right) A_j^{\vec{\pi}', \vec{\pi}}(s) \right]\right| \end{align}\]

The function \(f(v)=(\epsilon +v) ^{-\alpha}\) is Lipschitz continuous on \(\mathbb{R} ^+\). Thus, the following statement holds for any \(v,\, w\in \mathbb{R}^+\): \[|f(v)-f(w)|\leq L_\alpha|v-w|,\] where \(L_\alpha=\max_{v\in\mathbb{R}^+}\;|f'(v)| = \alpha \nu^{-1-\alpha}\) is a Lipschitz constant.

Therefore, we have \[\begin{align} \left|\frac{1}{\calvf['](s)} -\frac{1}{\calvf(s)}\right| &= \left|\frac{1}{f(\vf['](s))} -\frac{1}{f(\vf(s))}\right| \\ &\leq L_\alpha\cdot |\vf['](s)-\vf(s)| \\ &= L_\alpha\cdot\left|\mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t A_j^{\vec{\pi}}(s_t, \vec{a}_t) | s_0=s \right]\right| \\ &= L_\alpha\cdot\left|\mathbb{E}_{\tau \sim \vec{\pi}'} \left[ \sum_{t=0}^{\infty} \gamma^t A_j^{\vec{\pi}', \vec{\pi}}(s_t) | s_0=s \right]\right| \\ &\leq L_\alpha\cdot\mathbb{E}_{\tau \sim \vec{\pi}'} \left[\sum_{t=0}^{\infty} \gamma^t \left|A_j^{\vec{\pi}', \vec{\pi}}(s_t)\right| \;|\; s_0=s \right] \\ &\leq \frac{2L_\alpha}{1-\gamma}A_{\max} D_{\text{TV}}^{\max}(\vec{\pi},\,\vec{\pi} ') \end{align}\]

Plugging back the previous result into the first difference leads to: \[\begin{align} \Delta_1 &=\left|\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \left(\frac{1}{\calvf['](s)} -\frac{1}{\calvf(s)}\right) A_j^{\vec{\pi}', \vec{\pi}}(s) \right]\right|\notag\\ &\leq \mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \left|\frac{1}{\calvf['](s)} -\frac{1}{\calvf(s)}\right| \left|A_j^{\vec{\pi}', \vec{\pi}}(s)\right| \right]\notag\\ \text{using Lemma \ref{lem:borne95sup95advantage}, }&\\ &\leq \mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{4L_\alpha}{1-\gamma}A_{\max}^2 \kappa^2 \right]\notag\\ &= \frac{4nL_\alpha}{(1-\gamma)^2}A_{\max}^2 \kappa^2, \end{align}\]

where \(\kappa=D_{\text{TV}}^{\max}(\vec{\pi},\,\vec{\pi} ')\).

Next, we have to find an upper bound of the second difference \(\Delta_2\) which is due to the shift of state visitation distribution: \[\begin{align} \Delta_2 &=\left|\mathbb{E}_{s \sim d_{\vec{\pi}'}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]-\mathbb{E}_{s \sim d_{\vec{\pi}}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right]\right| \notag\\ &=\left|\mathbb{E}_{\tau \sim \vec{\pi}'} \left[\sum_{t=0}^\infty\gamma^t \left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s_t)}{\calvf(s_0)} \right)\right]-\mathbb{E}_{\tau \sim \vec{\pi}} \left[\sum_{t=0}^\infty\left(\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s)}{\calvf(s)} \right)\right]\right|\notag\\ &=\sum_{t=0}^\infty\gamma^t\left|\mathbb{E}_{\tau \sim \vec{\pi}'} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s_t)}{\calvf(s_0)}\right]- \mathbb{E}_{\tau \sim \vec{\pi}} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s_t)}{\calvf(s_0)}\right]\right|\notag\\ &=\sum_{t=0}^\infty\gamma^t\left|\mathbb{E}_{s_0\sim\rho_0}\left[\mathbb{E}_{\tau \sim \vec{\pi}'|s_0} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s_t)}{\calvf(s_0)}\right]- \mathbb{E}_{\tau \sim \vec{\pi}|s_0} \left[\sumi \frac{A_j^{\vec{\pi}', \vec{\pi}}(s_t)}{\calvf(s_0)}\right]\right]\right|\notag\\ &\leq\sum_{t=0}^\infty\gamma^t\mathbb{E}_{s_0\sim\rho_0}\left[\sumi\frac{1}{\calvf(s_0)}\left|\mathbb{E}_{\tau \sim \vec{\pi}'|s_0} \left[ A_j^{\vec{\pi}', \vec{\pi}}(s_t)\right]- \mathbb{E}_{\tau \sim \vec{\pi}|s_0} \left[ A_j^{\vec{\pi}', \vec{\pi}}(s_t)\right]\right|\right]\\ \end{align}\]

Let us recall Lemma 9: \[\left|\mathbb{E}_{\tau \sim \vec{\pi}'|s_0} \left[ A_j^{\vec{\pi}', \vec{\pi}}(s_t)\right]- \mathbb{E}_{\tau \sim \vec{\pi}|s_0} \left[ A_j^{\vec{\pi}', \vec{\pi}}(s_t)\right]\right| \leq 4\kappa(1-(1-\kappa)^t)A_{\max}.\]

Moreover, \(\frac{1}{\calvf(s_0)}\) is upper bounded by \(\nu^{-\alpha}\). Thus, we have \[\begin{align} \Delta_2 &\leq\sum_{t=0}^\infty\gamma^t\mathbb{E}_{s_0\sim\rho_0}\left[\sumi\frac{1}{\calvf(s_0)}\left|\mathbb{E}_{\tau \sim \vec{\pi}'|s_0} \left[ A_j^{\vec{\pi}', \vec{\pi}}(s_t)\right]- \mathbb{E}_{\tau \sim \vec{\pi}|s_0} \left[ A_j^{\vec{\pi}', \vec{\pi}}(s_t)\right]\right|\right]\\ &\leq \sum_{t=0}^\infty\gamma^t \mathbb{E}_{s_0\sim\rho_0}\left[4nA_{\max}\nu^{-\alpha}(1-(1-\kappa)^t)\kappa\right]\\ &\leq \sum_{t=0}^\infty\gamma^t 4nA_{\max}\nu^{-\alpha}(1-(1-\kappa)^t)\kappa\\ &\leq \frac{4nA_{\max}\kappa}{\nu^\alpha}\left(\frac{1}{1-\gamma}-\frac{1}{1-\gamma(1-\kappa)}\right)\\ &\leq \frac{4nA_{\max}\gamma\kappa^2}{\nu^\alpha(1-\gamma)^2 } \end{align}\]

Therefore, by combining both inequalities, we have : \[\begin{align} \left|\mathcal{F}_{\vec{\pi}}(\vec{\pi}')-\mathcal{L}_{\vec{\pi}}(\vec{\pi}')\right| &\leq \Delta_1+\Delta_2\notag\\ &\leq \frac{4nL_\alpha}{(1-\gamma)^2}A_{\max}^2 \kappa^2 + \frac{4nA_{\max}\gamma}{\nu^\alpha(1-\gamma)^2 }\kappa^2 \end{align}\]

This concludes the proof. ◻

9.3 Proof of Lemma [lem:advantage95decomp]↩︎

The Lemma [lem:advantage95decomp] is induced by individual advantage functions decomposition:

Lemma 10. For any agent j and subset \(I_m\subseteq I_n\), we have \[A_j^{\vec{\pi},\, I_m}(s, \vec{a}^{I_m}) = A^{\vec{\pi},\, I_m}(s, a^{\varnothing}, \vec{a}^{I_m})=\sum_{l=1}^m A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, \vec{a}^{i_m})\]

Proof. For any state \(s\) and joint action \(\vec{a}^{I_m}\), we have \[\begin{align} A_j^{\vec{\pi},\, I_m}(s, \vec{a}^{I_m}) &= A^{\vec{\pi},\, I_m}(s, a^{\varnothing}, \vec{a}^{I_m})\\ &=Q_j^{\vec{\pi},\, \varnothing\sqcup I_m}(s, \, \vec{a}^{\varnothing\sqcup I_m}) - Q_j^{\vec{\pi},\, \varnothing}(s, \, a^{\varnothing})\\ &=Q_j^{\vec{\pi},\, I_l}(s, \, \vec{a}^{I_l}) - V_j^{\vec{\pi}}(s)\\ &=\sum_{l=1}^m Q_j^{\vec{\pi},\, I_l}(s, \, \vec{a}^{I_l})-Q_j^{\vec{\pi},\, I_{l-1}}(s, \, \vec{a}^{I_{l-1}})\\ &=\sum_{l=1}^m A_j^{\vec{\pi},\, i_l}(s, \vec{a}^{I_{l-1}}, a^{i_l}) \end{align}\] ◻

Proof. The proof is pretty straightforward by considering the Lemma 10. For any set \(I_m\), state \(s\) and joint action \(\vec{a}^{I_m}\), we have by definition \[\begin{align} A_F^{\vec{\pi},\, I_m}(s, \vec{a}^{I_m}) &= \sumi[j]\frac{1}{\mathcal{V}_j^{\vec{\pi}}(s)}A_j^{\vec{\pi},\, I_m}(s, \vec{a}^{I_m}) \\ &= \sumi[j]\frac{1}{\mathcal{V}_j^{\vec{\pi}}(s)}\sum_{l=1}^m A_j^{\vec{\pi},\, i_l}(s, \vec{a}^{I_{l-1}}, \vec{a}^{i_l})\\ &= \sum_{l=1}^m \left(\sumi[j]\frac{1}{\mathcal{V}_j^{\vec{\pi}}(s)} A_j^{\vec{\pi},\, i_l}(s, \vec{a}^{I_{l-1}}, a^{i_l})\right)\\ &=\sum_{l=1}^m A_F^{\vec{\pi},\, i_l}(s, \vec{a}^{I_{l-1}}, a^{i_l}) \end{align}\] ◻

9.4 Proof of Lemma [lem:surrogate95decomp]↩︎

To prove Lemma [lem:surrogate95decomp], we first need to decompose the KL-penalty term:

Lemma 11. For any joint policies \(\vec{\pi}\) and \(\vec{\pi}'\) and state \(s\), the following statement holds \[D_{\text{KL}}\left(\vec{\pi}(.|s) \; ||\; \vec{\pi} ' (.|s)\right)= \sumi D_{\text{KL}}\left(\pi_j(.|s) \; ||\; \pi_j (.|s)\right).\]

Proof. For any state \(s\), we have \[\begin{align} D_{\text{KL}}\left(\vec{\pi}(\cdot|s) \parallel \vec{\pi}'(\cdot|s)\right) &= \mathbb{E}_{\vec{a}\sim\vec{\pi}(.|s)} \left[\log \vec{\pi}(\vec{a}|s) - \log\vec{\pi}'(\vec{a}|s)\right] \\ &= \mathbb{E}_{\vec{a}\sim\vec{\pi}(.|s)} \left[\log \prod_{j=1}^n \pi_j(a_j|s) - \log\prod_{j=1}^N \pi_j'(a_j|s)\right] \\ &= \mathbb{E}_{\vec{a}\sim\vec{\pi}(.|s)} \left[\sumi\log \pi_j(a_j|s) - \log \pi_j'(a_j|s)\right] \\ &= \sumi\mathbb{E}_{a_j\sim\pi_j(.|s)} \left[\log \pi_j(a_j|s) - \log \pi_j'(a_j|s)\right] \\ &= \sum_{j=1}^n D_{\text{KL}}\left(\pi_j(\cdot|s) \parallel \pi'_j(\cdot|s)\right) \end{align}\] ◻

Proof. The proof relies on Lemma [lem:advantage95decomp] and Lemma 11: \[\begin{align} J(\vec{\pi}')-J(\vec{\pi}) &\geq \mathcal{L}_{\vec{\pi}}(\vec{\pi}')-C\cdot D_{\text{KL}}^{\max}(\vec{\pi}\;||\; \vec{\pi}') \\ &\geq \mathbb{E}_{s \sim d_{\vec{\pi}}, \,\vec{a} \sim \vec{\pi}'(.|s)} \left[\sumi \frac{A_j^{\vec{\pi}}(s, \vec{a})}{\calvf(s)} \right] -C\cdot D_{\text{KL}}^{\max}(\vec{\pi}\;||\; \vec{\pi}') \\ &\geq \mathbb{E}_{s \sim d_{\vec{\pi}}, \,\vec{a} \sim \vec{\pi}'(.|s)} \left[\sumi \frac{1}{\calvf(s)}\sumi[m] A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] \\ &\qquad\qquad\qquad\qquad\qquad-\sumi[m]C\cdot D_{\text{KL}}^{\max}(\pi_{i_m}\;||\; \pi'_{i_m}) \\ &\geq \sumi[m] \mathbb{E}_{s_\sim d_{\vec{\pi}}, \;\vec{a}^{I_{m-1}}\sim\vec{\pi}^{I_{m-1}}(.|s), \, a^{i_m}\sim\pi'^{i_m}(.|s)} \left[\sumi \frac{1}{\calvf(s)} A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] \nonumber\\ &\qquad\qquad\qquad\qquad\qquad -C\cdot D_{\text{KL}}^{\max}(\pi_{i_m}\;||\; \pi'_{i_m}) \\ &= \sumi[m]\mathcal{L}_{\vec{\pi}}^{I_m}(\vec{\pi}'^{I_{m-1}}, \pi'^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi_{i_m}\,,\,\pi'_ {i_m}\right) \end{align}\] ◻

9.5 Proof of Lemma [lem:surrogate95gateaux]↩︎

Let us recall the definition of Gâteaux derivative.

Lemma 12. Let \(\vec{\pi}\) and \(\vec{\pi}'\) be two joint policies, then for any agent \(i\) and state \(s\), \(V_i^{\vec{\pi}}(s)\) is Gâteaux differentiable and \[\mathfrak D_{\vec{\pi}'}V_i^{\vec{\pi}}(s_0) = \mathbb{E}_{s\sim d_{\vec{\pi}|s_0},\,\vec{a} \sim \vec{\pi}'(\cdot|s)}\left[ A_i^{\vec{\pi}}(s, \vec{a}) \right]\]

Proof. Let \(\vec{\pi}, \vec{\pi}'\) be two joint policies and \(\eta>0\). For any agent \(i\), we defined the perturbed policy \(\pi^i_\eta=\pi^i+\eta(\pi'^i-\pi^i)\), which together define the perturbed joint policy \(\vec{\pi}_\eta\).

Let us consider the following quantity for a given state \(s_0\) \[f(\eta)=\frac{V_i^{\vec{\pi}_\eta}(s_0)-V_i^{\vec{\pi}}(s_0)}{\eta}.\]

Using Lemma 6, we have \[\begin{align} f(\eta) &=\frac{1}{\eta}\mathbb{E}_{\tau \sim \vec{\pi}_\eta} \left[ \sum_{t=0}^{\infty} \gamma^t A_i^{\vec{\pi}}(s_t, \vec{a}_t) \mid s_0 \right] \\ &=\frac{1}{\eta}\sum_{t=0}^{\infty} \gamma^t \mathbb{E}_{\tau \sim \vec{\pi}_\eta} \left[ A_i^{\vec{\pi}}(s_t, \vec{a}_t) \mid s_0 \right] \\ &=\frac{1}{\eta}\sum_{t=0}^{\infty} \gamma^t \sum_s\mathbb{P}(s_t=s|s_0,\vec{\pi}_\eta)\mathbb{E}_{\vec{a} \sim \vec{\pi}_\eta(\cdot|s)} \left[ A_i^{\vec{\pi}}(s, \vec{a}) \right] \end{align}\] Note that we can swap the expectation with the sum using Fubini’s Theorem as the expected sum of the discounted advantage function is converging uniformly.

By definition of \(\vec{\pi}_\eta\), we have \[\mathbb{E}_{\vec{a} \sim \vec{\pi}_\eta(\cdot|s)} \left[ A_i^{\vec{\pi}}(s, \vec{a}) \right]=(1-\eta)\mathbb{E}_{\vec{a} \sim \vec{\pi}(\cdot|s)} \left[ A_i^{\vec{\pi}}(s, \vec{a}) \right]+\eta\mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)} \left[ A_i^{\vec{\pi}}(s, \vec{a}) \right]\] Lemma 7 states that the first term is null. Therefore, we have \[\mathbb{E}_{\vec{a} \sim \vec{\pi}_\eta(\cdot|s)} \left[ A_i^{\vec{\pi}}(s, \vec{a}) \right]=\eta\mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)} \left[ A_i^{\vec{\pi}}(s, \vec{a}) \right].\]

Putting back into \(f(\eta)\) gives: \[\begin{align} f(\eta) &=\sum_{t=0}^{\infty} \gamma^t \sum_s\mathbb{P}(s_t=s|s_0)\mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)} \left[ A_i^{\vec{\pi}}(s, \vec{a}) \right] \\ &= \sum_sd_{\vec{\pi}_\eta}(s|s_0)\mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)}\left[ A_i^{\vec{\pi}}(s, \vec{a}) \right] \end{align}\]

When \(\eta\rightarrow0\), Lemma 2 states that \(d_{\vec{\pi}_\eta}\) converges to \(d_{\vec{\pi}}\) by continuity. Hence, we have \[\begin{align} \mathfrak D_{\vec{\pi}'} V^{\vec{\pi}}_i(s_0) &=\lim_{\eta\rightarrow 0}f(\eta) \\ &=\sum_sd_{\vec{\pi}}(s|s_0)\mathbb{E}_{\vec{a} \sim \vec{\pi}'(\cdot|s)}\left[ A_i^{\vec{\pi}}(s, \vec{a}) \right]\\ &=\mathbb{E}_{s\sim d_{\vec{\pi}|s_0},\,\vec{a} \sim \vec{\pi}'(\cdot|s)}\left[ A_i^{\vec{\pi}}(s, \vec{a}) \right] \end{align}\] ◻

Proof. Let \(\vec{\pi}, \vec{\pi}'\) be two joint policies and \(\eta>0\). We defined the perturbed policy \(\vec{\pi}_\eta=\vec{\pi}+\eta(\vec{\pi}'-\vec{\pi})\).

Let us consider the following quantity \[f(\eta)=\frac{J(\vec{\pi}_\eta)-J(\vec{\pi})}{\eta}.\]

Then, we have \[\begin{align} f(\eta) &=\frac{J(\vec{\pi}_\eta)-J(\vec{\pi})}{\eta} \\ &=\frac{1}{\eta}\mathbb{E}_{s_0\sim\rho_0}\left[\sumi U_\alpha(\nu+V_j^{\vec{\pi}_\eta}(s_0))- U_\alpha(\nu+V_j^{\vec{\pi}}(s_0))\right] \\ &=\sum_{s_0}\rho_0(s_0)\sumi\frac{U_\alpha(\nu+V_j^{\vec{\pi}_\eta}(s_0))- U_\alpha(\nu+V_j^{\vec{\pi}}(s_0))}{\eta} \end{align}\]

As the state space is finite, we can pass to the limit in the sum. \[\begin{align} \lim_{\eta\rightarrow0}f(\eta) &=\sum_{s_0}\rho_0(s_0)\sumi\lim_{\eta\rightarrow0}\frac{U_\alpha(\nu+V_j^{\vec{\pi}_\eta}(s_0))- U_\alpha(\nu+V_j^{\vec{\pi}}(s_0))}{\eta} \end{align}\]

We recognize the derivative of a composite function. As \(U_\alpha\) is differentiable on \(\mathbb{R}^+\) and \(V_j^{\vec{\pi}}(s_0)\) is Gateaux derivative, the composite \(U_\alpha(\nu+V_j^{\vec{\pi}}(s_0))\) is also Gateaux differentiable and the following statement holds: \[\mathfrak D_{\vec{\pi}'}J(\vec{\pi})=\lim_{\eta\rightarrow0}f(\eta)=\sum_{s_0}\rho_0(s_0)\sumi U_\alpha'(\nu+V_j^{\vec{\pi}}(s_0)) \mathfrak D_{\vec{\pi}'}V_j^{\vec{\pi}}(s_0)\]

Using Lemma 12, we have \[\begin{align} \mathfrak D_{\vec{\pi}'}J(\vec{\pi}) &=\sum_{s_0}\rho_0(s_0) \sumi U_\alpha'(\nu+V_j^{\vec{\pi}}(s_0)) \mathfrak D_{\vec{\pi}'}V_j^{\vec{\pi}}(s_0)\\ &=\mathbb{E}_{s_0\sim\rho_0}\left[\sumi \frac{1}{\mathcal{V}_j^{\vec{\pi}}(s_0)}\mathbb{E}_{s\sim d_{\vec{\pi}|s_0},\,\vec{a} \sim \vec{\pi}'(\cdot|s)}\left[ A_i^{\vec{\pi}}(s, \vec{a}) \right]\right]. \end{align}\]

Recall we are using contextualized states, thus the initial state \(s_0\) is passed to any other state in a trajectory. Then, using the total expectation theorem, we have \[\mathfrak D_{\vec{\pi}'}J(\vec{\pi}) = \mathbb{E}_{s\sim d_{\vec{\pi}},\,\vec{a} \sim \vec{\pi}'(\cdot|s)}\left[ \sumi \frac{1}{\mathcal{V}_j^{\vec{\pi}}(s_0)} A_i^{\vec{\pi}}(s, \vec{a}) \right]=\mathcal{L}_{\vec{\pi}}(\vec{\pi}').\] ◻

9.6 Proof of Theorem [thm:convergence]↩︎

To prove Theorem [thm:convergence], we need the following lemmas.

Lemma 13. For any subset \(I_m\), any joint policies \(\vec{\pi}\) and \(\vec{\pi}'\) \[\mathbb{E}_{s\sim d_{\vec{\pi}},\, \vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m}}\left[A_F^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] = 0\]

Proof. By definition, we have \[\begin{align} &\mathbb{E}_{s\sim d_{\vec{\pi}},\, \vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m}}\left[A_F^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] \\ &\qquad= \mathbb{E}_{s\sim d_{\vec{\pi}},\, \vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m}}\left[\sumi\frac{1}{\calvf(s)} A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] \\ &\qquad= \sumi\mathbb{E}_{s\sim d_{\vec{\pi}},\, \vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m}}\left[\frac{1}{\calvf(s)} A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] \\ &\qquad= \sumi\mathbb{E}_{s\sim d_{\vec{\pi}}}\left[\frac{1}{\calvf(s)}\mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[ A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right]\right]. \end{align}\]

For any agent \(j\), we have \[\begin{align} &\mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[ A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] \\ &\qquad= \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[ Q_j^{\vec{\pi},\, I_m}(s, \, \vec{a}^{I_{m-1}}, \, a^{i_m}) - Q_j^{\vec{\pi},\, I_{m-1}}(s, \, \vec{a}^{I_{m-1}}) \right] \\ &\qquad= \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[ Q_j^{\vec{\pi},\, I_m}(s, \, \vec{a}^{I_{m-1}}, \, a^{i_m})\right]\notag\\ &\qquad\qquad\qquad\qquad\qquad- \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}}|s}\left[Q_j^{\vec{\pi},\, I_{m-1}}(s, \, \vec{a}^{I_{m-1}}) \right] \end{align}\]

The first term can be re-written as \[\begin{align} &\mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[ Q_j^{\vec{\pi},\, I_m}(s, \, \vec{a}^{I_{m-1}}, \, a^{i_m})\right]\\ &\quad= \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[\mathbb{E}_{\vec{a}^{-I_m}\sim \vec{\pi}_{-I_m}}\left[Q_j^{\vec{\pi}}(s,\, \vec{a}^{I_{m-1}}, a^{i_m},\, \vec{a}^{-I_m})\right]\right] \\ &\quad= \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}}|s}\left[\mathbb{E}_{\vec{a}^{-I_{m-1}}\sim \vec{\pi}^{-I_{m-1}}}\left[Q_j^{\vec{\pi}}(s,\, \vec{a}^{I_{m-1}},\, \vec{a}^{-I_{m-1}})\right]\right] \\ &\quad= \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}}|s}\left[Q_j^{\vec{\pi},\, I_{m-1}}(s, \vec{a}^{I_{m-1}})\right] \end{align}\]

Putting back into the former equation ends the demonstration: \[\begin{align} &\mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[ A_j^{\vec{\pi},\, i_m}(s, \vec{a}^{I_{m-1}}, a^{i_m}) \right] \\ &\quad= \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}},\, a^{i_m}\sim\pi^{i_m} |s}\left[ Q_j^{\vec{\pi},\, I_m}(s, \, \vec{a}^{I_{m-1}}, \, a^{i_m})\right]\notag\\ &\qquad\qquad\qquad\qquad- \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}}|s}\left[Q_j^{\vec{\pi},\, I_{m-1}}(s, \, \vec{a}^{I_{m-1}}) \right] \\ &\quad= \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}}|s}\left[Q_j^{\vec{\pi},\, I_{m-1}}(s, \, \vec{a}^{I_{m-1}}) \right] - \mathbb{E}_{\vec{a}^{I_{m-1}}\sim\vec{\pi}'^{I_{m-1}}|s}\left[Q_j^{\vec{\pi},\, I_{m-1}}(s, \, \vec{a}^{I_{m-1}}) \right] \\ &\quad =0 \end{align}\] ◻

Proof. We will prove the theorem in three folds.

I. Monotonic Improvement Property

For any \(k\in \mathbb{N}\) and any permutation \(I_n\), suppose \(\vec{\pi}_{k+1}\) is updated by Algorithm 1, i.e. \[\pi_{k+1}^{i_m}=\underset{\pi^{i_m}}{\arg \max}\;\mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi_k^{i_m}\,,\,\pi^ {i_m}\right)\]

We want to bound the difference \(J(\vec{\pi}_{k+1}) - J(\vec{\pi}^i)\): \[\begin{align} J(\vec{\pi}_{k+1}) - J(\vec{\pi}^i) &\geq \sumi[l]\mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi_{k+1}^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi_{k}^{i_m}\,,\,\pi_{k+1}^{i_m}\right) \\ \end{align}\]

As \(\pi_{k+1}^{i_m}\) maximizes the surrogate function, the latter function gets lower evaluation for any other policy \(\pi'^{i_m}\). In particular, for \(\pi'^{i_m}=\pi_{k}^{i_m}\), we have : \[\begin{align} \mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi_{k+1}^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi_k^{i_m}\,,\,\pi_{k+1}^{i_m}\right) &\geq \mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi_{k}^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi_k^{i_m}\,,\,\pi_{k}^{i_m}\right) \\ &\geq \mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi_{k}^{i_m}) \end{align}\]

We then use the Lemma 13: \[\begin{align} \mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi_{k}^{i_m}) &=\mathbb{E}_{s_\sim d_{\vec{\pi}^i}, \;\vec{a}^{I_{m-1}}\sim\vec{\pi}_{k+1}^{I_{m-1}}(.|s), \, a^{i_m}\sim\pi_k^{i_m}(.|s)}\left[A^{\vec{\pi},\,i_m}\left(s, \vec{a} ^{I_{m-1}}, a^{i_m}\right)\right] \\ &=0. \end{align}\]

Hence, it follows that \[\begin{align} J(\vec{\pi}_{k+1}) - J(\vec{\pi}^i) &\geq \sumi[l]\mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi_{k+1}^{i_m}) - C\cdot D_{\text{KL}}^{\max}\left(\pi_{k}^{i_m}\,,\,\pi_{k+1}^{i_m}\right) \\ &\geq \sumi[l]\mathcal{L}_{\vec{\pi}^i}^{I_m}(\vec{\pi}_{k+1}^{I_{m-1}}, \pi_{k}^{i_m})\\ &\geq 0. \end{align}\]

II. Convergence of the fair global objective

First of all, the sequence \((J(\vec{\pi}_k))_{k\in\mathbb{N}}\) converges as, by the Monotonic Improvement property, it is monotonically increasing and upper bounded by \(n\cdot U_\alpha\left(\nu+\frac{r_{\max}}{1-\gamma}\right)\). Let us denote the limit by \(J_\infty\).

III. Nash Equilibrium of the limit points

The following proof is adapted from Appendix C.3 of [23]. We update the original notation and substitute their multi-agent advantage function with our fair advantage function. While Steps 1 and 2 follow directly from this substitution, we include the fully adapted steps here for completeness.

Step 1 (Stationarity of any limit point). The policy state \(\Pi^i\) is bounded. Therefore, for any sequence of policies \((\vec{\pi}^i)\), Bolzano-Weierstrass Theeorem states that we can extract a subsequence \((\vec{\pi}_{k_j})_{j\in\mathbb{N}}\) that converges to an adherent point \(\vec{\pi}_\infty\). By continuity of \(J\) in \(\vec{\pi}\) (1), we have \[J(\vec{\pi}_\infty) = J\left( \lim_{j \to \infty} \vec{\pi}_{k_j} \right)= \lim_{j \to \infty} J(\vec{\pi}_{k_j}) = J_\infty.\]

Definition 7 (TR-Stationarity, [23]). A joint policy \(\vec{\pi}_\circ\) is a trust-region-stationary (TR-stationary) if, for every agent \(i\), \[\pi^i_\circ = \arg \max_{\pi^i} \left[ \mathbb{E}_{s \sim d_{\vec{\pi}_\circ},\, a^i \sim \pi^i} \left[ A_F^{\vec{\pi}_\circ,\, i}(s, a^i) \right] - C_{\vec{\pi}_\circ} \mathrm{D}_{KL}^{\max} \left( \pi^i_\circ, \pi^i \right) \right],\] where \(C_{\vec{\pi}_\circ} = \frac{4nL_\alpha}{(1-\gamma)^2}A_{\max}^2 + \frac{4nA_{\max}\gamma}{\nu^\alpha(1-\gamma)^2 }\), and \(A_{\max} = \max_{j, s, \vec{a}} |A_j^{\vec{\pi}_\circ}(s, \vec{a})|\).

The goal now is to establish the TR-stationarity of any limit point joint policy \(\vec{\pi}_\infty\). Let \(\mathbb{E}_{I_{n}^{0:\infty}} [\cdot]\) denote the expected value operator under the random process \((I_{n}^{0:\infty})\). Let also \(A_k = \max_{j, \,s, \,\vec{a}} |A_j^{\vec{\pi}_k}(s, \vec{a})|\), and \(C_{\vec{\pi}_k} = \frac{4nL_\alpha}{(1-\gamma)^2}A_{k}^2 + \frac{4nA_{k}\gamma}{\nu^\alpha(1-\gamma)^2 }\). We have \[\begin{align} 0 &= \lim_{k \to \infty} \mathbb{E}_{I_{n}^{0:\infty}} [J(\vec{\pi}_{k+1}) - J(\vec{\pi}_k)] \\ &\ge \lim_{k \to \infty} \mathbb{E}_{I_{n}^{0:\infty}} [\mathcal{L}_{\vec{\pi}_k}(\vec{\pi}_{k+1}) - C_k \mathrm{D}_{KL}^{\max}(\vec{\pi}_k, \vec{\pi}_{k+1})] \text{ by Lemma \textcolor{red}{\ref{lem:fair95surrogate}}} \\ &\ge \lim_{k \to \infty} \mathbb{E}_{I_{n}^{0:\infty}} \left[ \mathcal{L}_{\vec{\pi}_k}^{i^k_1} \left( \pi_{k+1}^{i^k_1} \right) - C_k \mathrm{D}_{KL}^{\max} \left( \pi_k^{i^k_1}, \pi_{k+1}^{i^k_1} \right) \right], \end{align}\] by Lemma [lem:surrogate95decomp] and removing the all the summands except \(i_1^k\) (because the summands are all positive).

Now, we consider an arbitrary limit point \(\vec{\pi}_\infty\) from the adherent set, and a subsequence \((\vec{\pi}_{k_j})_{j=0}^{\infty}\) that converges to \(\vec{\pi}_\infty\).

On one hand, we have from above

\[0 \ge \lim_{j \to \infty} \mathbb{E}_{I_{n}^{0:\infty}} \left[ \mathcal{L}^{i^{k_j}_1}_{\vec{\pi}_{k_j}} \left( \pi^{i^{k_j}_1}_{k_j+1} \right) - C_{k_j} D_{\mathrm{KL}}^{\max} \left( \pi^{i^{k_j}_1}_{k_j}, \pi^{i^{k_j}_1}_{k_j+1} \right) \right].\]

On the other hand, let denote by \(p_i\) the probability to have \(i_{k_j} = i\) under the assumption that every permutation has strictly positive probability to happen. As the expectation is taken of positive random variables, we also have

\[\begin{align} &\lim_{j \to \infty} \mathbb{E}_{I_{n}^{0:\infty}} \left[\mathcal{L}^{i^{k_j}_1}_{\vec{\pi}_{k_j}} \left( \pi^{i^{k_j}_1}_{k_j+1} \right)- C_{k_j} D_{\mathrm{KL}}^{\max} \left( \pi^{i^{k_j}_1}_{k_j}, \pi^{i^{k_j}_1}_{k_j+1} \right)\right]\\ & \qquad\qquad\qquad\qquad\qquad\qquad\qquad\geq p_i \lim_{j \to \infty} \max_{\pi^i} \left[\mathcal{L}^{i}_{\vec{\pi}_{k_j}} \left( \pi^i \right) - C_{k_j} D_{\mathrm{KL}}^{\max} \left( \pi^i_{k_j}, \pi^i \right)\right] \\ & \qquad\qquad\qquad\qquad\qquad\qquad\qquad\geq p_i \max_{\pi^i} \left[\mathcal{L}^{i}_{\vec{\pi}_\infty} \left( \pi^i \right) - C_{\vec{\pi}_\infty} D_{\mathrm{KL}}^{\max} \left( \vec{\pi}^i_\infty, \pi^i \right)\right] \\ & \qquad\qquad\qquad\qquad\qquad\qquad\qquad\geq 0 \text{ by Lemma \ref{lem:expected95local95advantage95null}.} \end{align}\]

\(\mathcal{L}^{i}_{\vec{\pi}_{k_j}}(\pi^i)\) converges as \(\mathcal{L}^{i}_{\vec{\pi}}(\pi^i)\) is continuous with respect to \(\vec{\pi}\) (by Definition 3 and Lemma 5). \(C_{k_j}\) converges as it is continuous with respect to \(\vec{\pi}\) (Corollary 1). \(D_{\mathrm{KL}}^{\max}\) convergence follows from from continuity of \(D_{\mathrm{KL}}\) with Assumption 1 and continuity of \(\max\) over finite state space.

Therefore, we have \[\max_{\pi^i} \left[\mathcal{L}^{i}_{\vec{\pi}_\infty}(\pi^i)- C_{\vec{\pi}_\infty} D_{\mathrm{KL}}^{\max} \left( \pi^i_\infty, \pi^i \right)\right] = 0,\] which proves \(\vec{\pi}_\infty\) is TR-stationary.

Step 2 (dropping the penalty term). In this second step, the goal is to prove that a TR-stationary joint policy \(\bar{\pi}\) satisfies \[\label{eq:arg95max} \pi_\infty^i = \arg\max_{\pi^i} \mathbb{E}_{a^i \sim \pi^i} \left[ A_F^{\vec{\pi}_\infty, \, i} (s, a^i) \right],\tag{2}\] for every state \(s \in \mathcal{S}\).

We will prove the statement by contradiction. Hence, suppose that there exists a state \(s_0\) and a policy \(\hat{\pi}^i\) such that \[\label{eq:contradiction95hypothesis} \mathbb{E}_{a^i \sim \hat{\pi}^i} \left[ A_F^{\vec{\pi}_\infty,\, i} (s_0, a^i) \right] > \mathbb{E}_{a^i \sim \pi^i_\infty} \left[ A_F^{\vec{\pi}_\infty,\, i} (s_0, a^i) \right].\tag{3}\]

Parameterize the policy \(\pi^i(\cdot \mid s_0)\) as a probability vector: \[\pi^i(\cdot \mid s_0) = \left( x_1^i, \ldots, x_{d^i-1}^i, 1 - \sum_{j=1}^{d^i-1} x_j^i \right),\] where \(x_j^i\) ensures a valid distribution and \(d^i=|\mathcal{A}_i|\). The expected fair advantage in Equation 2 can be rewritten as: \[\begin{align} \mathbb{E}_{a^i \sim \pi^i} \left[A_F^{\vec{\pi}_\infty,\, i}(s_0, a^i) \right] &= \sum_{j=1}^{d^i-1} x_j^i \cdot A_F^{\vec{\pi}_\infty,\, i} (s_0, a_j^i) + \left( 1 - \sum_{h=1}^{d^i-1} x_h^i \right) A_F^{\vec{\pi}_\infty,\, i} (s_0, a_{d^i}^i) \\ &= \sum_{j=1}^{d^i-1} x_j^i \left[ A_F^{\vec{\pi}_\infty,\, i}(s_0, a_j^i) - A_F^{\vec{\pi}_\infty,\, i} (s_0, a_{d^i}^i) \right] + A_F^{\vec{\pi}_\infty,\, i}(s_0, a_{d^i}^i). \end{align}\]

Because this expectation is an affine function of \(x^i\), its gradients and directional derivatives are constant. The existence of \(\hat{\pi}^i(\cdot \mid s_0)\) satisfying Inequality 3 guarantees a strictly positive directional derivative from \(\bar{\pi}^i(\cdot \mid s_0)\) toward \(\hat{\pi}^i(\cdot \mid s_0)\).

Additionally, the KL divergence gradient vanishes at the reference policy \(\pi_\infty^i\): \[\begin{align} \frac{\partial D_{\mathrm{KL}}(\pi_\infty^i(\cdot \mid s_0), \pi^i(\cdot \mid s_0))}{\partial x_j^i} &= \frac{\partial}{\partial x_j^i} \left[ (\pi_\infty^i(\cdot \mid s_0))^T \big( \log \pi_\infty^i(\cdot \mid s_0) - \log \pi^i(\cdot \mid s_0) \big) \right] \\ &= - \frac{\partial}{\partial x_j^i} \left[ (\pi_\infty^i)^T \log \pi^i \right] \quad \text{(omitting state s_0 for brevity)} \\ &= - \frac{\partial}{\partial x_j^i} \sum_{k=1}^{d^i-1} \pi_{\infty, k}^i \log x_k^i \;-\; \frac{\partial}{\partial x_j^i} \pi_{\infty,\,d^i}^i \log \left( 1 - \sum_{k=1}^{d^i-1} x_k^i \right) \\ &= - \frac{\pi_{\infty,\,j}^i}{x_j^i} + \frac{\pi_{\infty,\,d^i}^i}{1 - \sum_{k=1}^{d^i-1} x_k^i} \\ &= - \frac{\pi_{\infty,\,j}^i}{\pi_j^i} + \frac{\pi_{\infty,\,d^i}^i}{\pi_{d^i}^i} = 0, \quad \text{when } \pi^i = \pi_\infty^i. \end{align}\]

Consequently, when evaluated at \(\pi^i(\cdot \mid s_0) = \pi_\infty^i(\cdot \mid s_0)\), the full penalized objective: \[d_{\vec{\pi}_\infty}(s_0)\,\mathbb{E}_{a^i \sim \pi^i} \left[ A_F^{\vec{\pi}_\infty,\, i} (s_0, a^i) \right] - C_{\vec{\pi}_\infty} D_{\mathrm{KL}} \big( \pi_\infty^i(\cdot \mid s_0), \pi^i(\cdot \mid s_0) \big)\] has a strictly positive directional derivative toward \(\hat{\pi}^i(\cdot \mid s_0)\). This implies we can find a local policy \(\tilde{\pi}^i(\cdot \mid s_0)\) on the path toward \(\hat{\pi}^i(\cdot \mid s_0)\) that strictly improves the objective: \[d_{\vec{\pi}_\infty}(s_0)\,\mathbb{E}_{a^i \sim \tilde{\pi}^i} \left[ A_F^{\vec{\pi}_\infty,\, i} (s_0, a^i) \right] - C_{\vec{\pi}_\infty} D_{\mathrm{KL}} \big( \pi_\infty^i(\cdot \mid s_0), \tilde{\pi}^i(\cdot \mid s_0) \big) > 0.\]

Now, construct a global policy \(\pi_*^i\) such that \(\pi_*^i(\cdot \mid s_0) = \tilde{\pi}^i(\cdot \mid s_0)\) and \(\pi_*^i(\cdot \mid s) = \pi_\infty^i(\cdot \mid s)\) for all \(s \neq s_0\). For unperturbed states (\(s \neq s_0\)), both the advantage and KL divergence evaluate to zero: \[\begin{align} d_{\vec{\pi}_\infty}(s)\,\mathbb{E}_{a^i \sim \pi_*^i} \left[ A_F^{\vec{\pi}_\infty,\, i} (s, a^i) \right] &= d_{\vec{\pi}_\infty}(s)\,\mathbb{E}_{a^i \sim \pi_\infty^i} \left[ A_F^{\vec{\pi}_\infty,\, i}(s, a^i) \right] = 0, \notag\\ D_{\mathrm{KL}} \big( \pi_\infty^i(\cdot \mid s), \pi_*^i(\cdot \mid s) \big) &= 0. \end{align}\]

Applying this to the full objective yields: \[\begin{align} \mathcal{L}^i_{\vec{\pi}_\infty}(\pi_*^i) - C_{\vec{\pi}_\infty} D_{\mathrm{KL}}^{\max}(\pi_\infty^{i}, \pi_*^i) &= d_{\vec{\pi}_\infty}(s_0)\,\mathbb{E}_{a^i \sim \tilde{\pi}^i} \left[ A_F^{\vec{\pi}_\infty,\, i} (s_0, a^i) \right] \notag\\ &\qquad - C_{\vec{\pi}_\infty} D_{\mathrm{KL}} \big( \pi_\infty^i(\cdot \mid s_0), \tilde{\pi}^i(\cdot \mid s_0) \big) \\ &> 0 \\ &= \mathcal{L}^i_{\vec{\pi}_\infty}(\pi_\infty^i) - C_{\vec{\pi}_\infty} D_{\mathrm{KL}}^{\max}(\pi_\infty^{i}, \pi_\infty^i). \end{align}\]

This strict improvement directly contradicts the assumption of TR-stationarity for \(\bar{\pi}\), thereby proving the claim.

Step 3 (optimality). Now, for a fixed joint policy \(\vec{\pi}_\infty^{-i}\) of other agents, \(\pi_\infty^i\) satisfies \[\pi_\infty^i = \arg\max_{\pi^i} \mathbb{E}_{a^i \sim \pi^i} \left[ A^{\vec{\pi}_\infty, \, i} (s, a^i) \right].\]

Lemma [lem:fair95surrogate] gives an upper bound of the performance difference. Then, for a given TR-stationary point \(\vec{\pi}_\infty\) and any other policy \(\pi^i\) for agent \(i\), we have \[J(\pi^i,\vec{\pi}_\infty^{-i})-J(\vec{\pi}_\infty) \leq \mathcal{L} _{\vec{\pi}_\infty}(\pi^i,\vec{\pi}_\infty^{-i}),\] which by definition of \(\mathcal{L}_{\vec{\pi}_\infty}\) is equivalent to \[\begin{align} J(\pi^i,\vec{\pi}_\infty^{-i})-J(\vec{\pi}_\infty) &\leq \mathbb{E}_{s\sim d_{\vec{\pi}_\infty}, \; a^i\sim\pi^i(\cdot|s),\, \vec{a}^{-i}\sim\vec{\pi}^{-i}_\infty(\cdot|s)}\left[A_{F}^{\vec{\pi}_\infty}(s,a^i,\vec{a}^{-i}) \right] \\ &=\mathbb{E}_{s\sim d_{\vec{\pi}_\infty}}\left[\mathbb{E}_{a^i\sim\pi^i(\cdot|s)}\left[A_{F}^{\vec{\pi}_\infty, \,i}(s,a^i) \right] \right]\\ &\leq \mathbb{E}_{s\sim d_{\vec{\pi}_\infty}}\left[\mathbb{E}_{a^i\sim\pi^i_\infty(\cdot|s)}\left[A_{F}^{\vec{\pi}_\infty, \,i}(s,a^i) \right] \right] \text{ (by definition of \pi_\infty^i)} \\ &=0\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\; \text{ (by Lemma \ref{lem:expected95local95advantage95null})} \end{align}\]

Thus, we have \[J(\pi^i,\vec{\pi}_\infty^{-i})\leq J(\vec{\pi}_\infty).\]

As this statement holds for any arbitrary agent \(i\), this proves \(\vec{\pi}_\infty\) is a Nash equilibrium. ◻

10 Pratical Algorithms↩︎

10.1 \(\alpha\)-fair HATRPO↩︎

The derivation of \(\alpha\)-fair HATRPO relies on an estimator \(\hat{g}_{k}^{i_{m}}\) of the gradient of the local objective \(\mathbb{E}_{s_\sim d_{\vec{\theta}_k}, \;\vec{a}^{I_{m-1}}\sim\vec{\theta}_{k+1}^{I_{m-1}}(.|s), \, a^{i_m}\sim\theta^{i_m}(.|s)}\left[A_F^{\vec{\theta}_k,\,i_m}\left(s, \vec{a} ^{I_{m-1}}, a^{i_m}\right)\right]\).

In this form, the local objective is hard to differentiate. Thankfully, we can re-write this in a more tractable expression.

Lemma 14. Let \(\vec{\pi}\) be a joint policy, \(\vec{\pi}'^{I_{m-1}}\) be some other joint policy of agents \(I_{m-1}\) and \(\pi'^{i_m}\) be some other policy of agent \(i_m\). Then, the local objective can be rewritten as \[\begin{align} \mathbb{E}_{\vec{a}^{I_{m-1}} \sim \vec{\pi}'^{I_{m-1}}, a^{i_m} \sim \pi'^{i_m}} [A_F^{\vec{\pi},\,i_m}(s,& \vec{a}^{I_{m-1}}, a^{i_m})] = \notag \\ &\mathbb{E}_{\vec{a} \sim \vec{\pi}} \left[\left(\frac{\pi'^{i_m}({a}^{i_m}|s)}{\pi^{i_m}({a}^{i_m}|s)} - 1\right)\frac{\vec{\pi}'^{I_{m-1}}(\vec{a}^{I_{m-1}}|s)}{\vec{\pi}^{I_{m-1}}(\vec{a}^{I_{m-1}}|s)}A_F^{\vec{\pi}}(s, \vec{a})\right]. \end{align}\]

Proof. See [23], Appendix D.1 (Proposition 2). The proof is similar by replacing the multi-agent advantage function with our fair advantage function. Because both advantage functions enjoy the same decomposition property (Lemma [lem:advantage95decomp]), the proof holds for our fair advantage function. ◻

Let us introduce \(M_F^{I_m} = \frac{\vec{\pi}'^{I_{m-1}}(\vec{a}^{I_{m-1}} | s)}{\vec{\pi}^{I_{m-1}}(\vec{a}^{I_{m-1}} | s)} A_F^{\vec{\theta}_k}(s, \vec{a})\). It follows that the derivation of the gradient estimator for HATRPO holds for \(\alpha\)-fair HATRPO by replacing the multi-agent advantage function with our fair advantage function:

\[\begin{align} &\nabla_{\theta^{i_m}} \mathbb{E}_{s \sim d_{\vec{\theta}_k}, \vec{a} \sim \vec{\theta}_k} \left[ \left( \frac{\pi_{\theta^{i_m}}^{i_m}(a^{i_m}|s)}{\pi_{\theta_k^{i_m}}^{i_m}(a^{i_m}|s)} - 1 \right) M_F^{I_{m}}(s, \vec{a}) \right] \\ &\qquad\qquad= \mathbb{E}_{s \sim d_{\vec{\theta}_k}, a \sim \vec{\theta}_k} \left[ \frac{\pi_{\theta^{i_m}}^{i_m}(a^{i_m}|s)}{\pi_{\theta_k^{i_m}}^{i_m}(a^{i_m}|s)} \nabla_{\theta^{i_m}} \log \pi_{\theta^{i_m}}^{i_m}(a^{i_m}|s) M_F^{i_{1:m}}(s, \vec{a}) \right]. \end{align}\] See Appendix D.2 of [23] for more details.

Figure 4: \alpha-FHATRPO — Figure 4: \(\alpha\)-FHATRPO

10.2 \(\alpha\)-fair HAPPO↩︎

Figure 5: \alpha-FHAPPO — Figure 5: \(\alpha\)-FHAPPO

11 Experiments↩︎

11.1 Environments’ parameters↩︎

In this work, we based our implementation on the environment provided by SocialJax.

Table 1: CleanUp Environment Parameters
Parameter	Value / Description
Grid Size	\(28 \times 19\)
Trajectory Length	\(500\) steps
Max Regrowth Apple Rate	0.05
Maximum Level of Pollution	\(40\%\)
Delay Start of Dirt Spawning	50
Dirt Spawn Probability	0.5

Table 2: Harvest Environment Parameters
Parameter	Value
Grid Size	\(22 \times 16\)
Trajectory Length	\(500\)
Regrowth Apple Rate	Proportional to density

11.2 Hyper-parameters of the different algorithms↩︎

We implement HATRPO and HAPPO from scratch using the pseudo code provided by HATRL [23]. We recover the code of Fair MAPPO from FairMARL[5] (https://github.com/AkuBrains/altruistic-fair-MARL/). In this work, actor and critic networks use similar architecture : CNN followed by MLP. We use the tanh activation layer for hidden layers and the softplus activation function for the final layer of critics to ensure positiveness of the state value estimation.

Table 3: Hyperparameters for the Adam Optimizer.
Parameter	Default Value
Exponential Decay (\(\beta_1\))	\(0.9\)
Exponential Decay (\(\beta_2\))	\(0.999\)
Epsilon (\(\epsilon\))	\(10^{-8}\)
Weight Decay (\(\lambda\))	\(0\)

Table 4: Hyperparameters HATRPO’s algorithms (**Harvest**).
Parameter	HATRPO	0.5-FHATRPO	1-FHATRPO	1.5-FHATRPO
\(\nu\)	/	\(0.1\)	\(0.1\)	\(0.1\)
KL (\(\delta\))	\(0.01\)	\(0.01\)	\(0.01\)	\(0.01\)
critic learning rate	\(0.0001\)	\(0.0001\)	\(0.0001\)	\(0.0001\)
accept ratio	\(0.1\)	\(0.1\)	\(0.1\)	\(0.1\)
CG iteration	\(15\)	\(15\)	\(15\)	\(15\)

Table 5: Hyperparameters HAPPO’s algorithms (**Harvest**).
Parameter	HAPPO	0.5-FHAPPO	1-FHAPPO	1.5-FHAPPO
\(\nu\)	/	\(0.1\)	\(0.1\)	\(0.1\)
Clipping \(\epsilon\)	\(0.05\)	\(0.05\)	\(0.05\)	\(0.05\)
actor learning rate	\(0.0003\)	\(0.0003\)	\(0.0005\)	\(0.0005\)
critic learning rate	\(0.0001\)	\(0.0001\)	\(0.0001\)	\(0.0001\)
Minibatch size	\(1000\)	\(1000\)	\(1000\)	\(1000\)

Table 6: Hyperparameters HATRPO’s algorithms (**CleanUp**).
Parameter	HATRPO	0.5-FHATRPO	1-FHATRPO	1.5-FHATRPO
\(\nu\)	/	\(0.1\)	\(0.1\)	\(0.1\)
KL (\(\delta\))	\(0.005\)	\(0.005\)	\(0.005\)	\(0.0005\)
critic learning rate	\(0.0001\)	\(0.0001\)	\(0.0001\)	\(0.0001\)
accept ratio	\(0.1\)	\(0.1\)	\(0.1\)	\(0.1\)
CG iteration	\(10\)	\(10\)	\(10\)	\(15\)

Table 7: Hyperparameters HAPPO’s algorithms (**CleanUp**).
Parameter	HAPPO	0.5-FHAPPO	1-FHAPPO	1.5-FHAPPO
\(\nu\)	/	\(0.1\)	\(0.1\)	\(0.1\)
Clipping \(\epsilon\)	\(0.1\)	\(0.2\)	\(0.1\)	\(0.1\)
actor learning rate	\(0.0005\)	\(0.0005\)	\(0.0005\)	\(0.0005\)
critic learning rate	\(0.0001\)	\(0.0001\)	\(0.0001\)	\(0.0001\)
Minibatch size	\(1000\)	\(1000\)	\(1000\)	\(1000\)

Table 8: Hyperparameters for FMAPPO algorithm.
Parameter	CleanUp	Harvest
altruism level (\(\alpha\))	\(1\)	\(1\)
Clipping \(\epsilon\)	\(0.1\)	\(0.1\)
actor learning rate	\(0.0005\)	\(0.0005\)
critic learning rate	\(0.0005\)	\(0.0005\)
Minibatch size	\(1250\)	\(1000\)

11.3 Additional metrics↩︎

CleanUp

In the CleanUp environment, agents must clean the river and maintain pollution levels below a certain threshold to allow apples to spawn. Consequently, agents must sacrifice short-term rewards for the long-term benefit of cleaning the river. Furthermore, agents can utilize the zap action to teleport zapped agents to a random spawning location. We study this cooperation using two additional metrics: the Total Zap Action (TZA) and the Total Clean Action (TCA). Figure 6 presents these additional results. The TZA tends to decrease throughout the training process across all algorithms, stabilizing between \(50\) and \(100\) actions per trajectory, while the TCA also decreases and stabilizes at approximately \(200\) actions per trajectory.

Harvest

In the Harvest environment, agents must harvest as many apples as possible while maintaining a sufficient apple population, as apples can only regenerate near existing ones. Similar to the CleanUp environment, agents can utilize the zap action to teleport zapped agents to a random spawning location. We can analyze this cooperation using two additional metrics: the Total Zap Action (TZA) and the Time to Depletion (TD). Figure 7 summarizes these additional results. The TZA values appear to decrease and approach zero for all algorithms except HAPPO and \(0.5\text{-FHAPPO}\). Meanwhile, the TD exhibits an initial drop at the beginning of training—as agents learn to harvest apples efficiently—before increasing and plateauing at \(500\), indicating that agents successfully maintain a stable level of apples on the board until the end of each trajectory.

References↩︎

[1]

S. A. West, A. S. Griffin, and A. Gardner, “Evolutionary Explanations for Cooperation,” Current Biology, vol. 17, no. 16, pp. R661–R672, Aug. 2007, doi: 10.1016/j.cub.2007.06.004.

[2]

P. A. M. V. Lange, Google-Books-ID: KfhMAgAAQBAJSocial Dilemmas: Understanding Human Cooperation. OUP USA, 2014.

[3]

S. Roesch, S. Leonardos, and Y. Du, “Selfishness Level Induces Cooperation in Sequential Social Dilemmas.”

[4]

J. Pérolat, J. Z. Leibo, V. Zambaldi, C. Beattie, K. Tuyls, and T. Graepel, “A multi-agent reinforcement learning model of common-pool resource appropriation,” in Advances in Neural Information Processing Systems, 2017, vol. 30, Accessed: Apr. 27, 2026. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2017/hash/2b0f658cbffd284984fb11d90254081f-Abstract.html.

[5]

Y. F. Xu, T. Lemlouma, A. Braud, and J.-M. Bonnin, arXiv:2602.08389 [cs]“Altruism and Fair Objective in Mixed-Motive Markov games.” Feb. 2026, doi: 10.65109/MPMP3285.

[6]

K.-T. Tran, D. Dao, M.-D. Nguyen, Q.-V. Pham, B. O’Sullivan, and H. D. Nguyen, arXiv:2501.06322 [cs]“Multi-Agent Collaboration Mechanisms: A Survey of LLMs.” arXiv, Jan. 2025, doi: 10.48550/arXiv.2501.06322.

[7]

E. Hughes et al., arXiv:1803.08884 [cs]“Inequity aversion improves cooperation in intertemporal social dilemmas.” arXiv, Sep. 2018, doi: 10.48550/arXiv.1803.08884.

[8]

A. Demir, H. Aydın, K. A. Tessera, D. Abel, and S. V. Albrecht, arXiv:2602.15407 [cs]“Fairness over Equality: Correcting Social Incentives in Asymmetric Sequential Social Dilemmas.” Feb. 2026, doi: 10.65109/CZPZ7833.

[9]

J. Schulman, S. Levine, P. Moritz, M. I. Jordan, and P. Abbeel, arXiv:1502.05477 [cs]“Trust Region Policy Optimization.” arXiv, Apr. 2017, doi: 10.48550/arXiv.1502.05477.

[10]

C. S. de Witt et al., arXiv:2011.09533 [cs]“Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?” arXiv, Nov. 2020, doi: 10.48550/arXiv.2011.09533.

[11]

C. Yu et al., arXiv:2103.01955 [cs]“The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games.” arXiv, Nov. 2022, doi: 10.48550/arXiv.2103.01955.

[12]

W. Kim and K. Sycara, “Fair cooperation in mixed-motive games via conflict-aware gradient adjustment.” 2025, [Online]. Available: https://arxiv.org/abs/2508.17696.

[13]

P. Ekpo, S. Agarwal, F. Grimm, L. Molu, and A. Taylor, arXiv:2511.14135 [cs] version: 1“Fair-GNE : Generalized Nash Equilibrium-Seeking Fairness in Multiagent Healthcare Automation.” arXiv, Nov. 2025, doi: 10.48550/arXiv.2511.14135.

[14]

Z. Yang et al., “DeCOM: Decomposed Policy for Constrained Cooperative Multi-Agent Reinforcement Learning,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 9, pp. 10861–10870, Jun. 2023, doi: 10.1609/aaai.v37i9.26288.

[15]

S. Alqithami, arXiv:2603.14625 [cs]“EcoFair-CH-MARL: Scalable Constrained Hierarchical Multi-Agent RL with Real-Time Emission Budgets and Fairness Guarantees,” 2025.

[16]

J. A. Weymark, “Generalized gini inequality indices,” Mathematical Social Sciences, vol. 1, no. 4, pp. 409–430, 1981, doi: https://doi.org/10.1016/0165-4896(81)90018-4.

[17]

F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: Shadow prices, proportional fairness and stability,” Journal of the Operational Research Society, vol. 49, no. 3, pp. 237–252, 1998, doi: 10.1057/palgrave.jors.2600523.

[18]

J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–567, 2000, doi: 10.1109/90.879343.

[19]

T. Lan, D. Kao, M. Chiang, and A. Sabharwal, “An axiomatic theory of fairness in network resource allocation,” in 2010 proceedings IEEE INFOCOM, 2010, pp. 1–9, doi: 10.1109/INFCOM.2010.5461911.

[20]

M. Zimmer, C. Glanois, U. Siddique, and P. Weng, “Learning Fair Policies in Decentralized Cooperative Multi-Agent Reinforcement Learning,” in Proceedings of the 38th International Conference on Machine Learning, Jul. 2021, pp. 12967–12978, Accessed: Apr. 26, 2026. [Online]. Available: https://proceedings.mlr.press/v139/zimmer21a.html.

[21]

U. Siddique, P. Li, and Y. Cao, “Towards Fair and Equitable Policy Learning in Cooperative Multi-Agent Reinforcement Learning,” 2024.

[22]

P. Ju, A. Ghosh, and N. B. Shroff, arXiv:2306.00324 [cs]“Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning.” arXiv, Jun. 2023, doi: 10.48550/arXiv.2306.00324.

[23]

Y. Zhong, J. G. Kuba, X. Feng, S. Hu, J. Ji, and Y. Yang, “Heterogeneous-Agent Reinforcement Learning.”

[24]

J. G. Kuba, X. Feng, S. Ding, H. Dong, J. Wang, and Y. Yang, arXiv:2208.01682 [cs]“Heterogeneous-Agent Mirror Learning: A Continuum of Solutions to Cooperative MARL.” arXiv, Aug. 2022, doi: 10.48550/arXiv.2208.01682.

[25]

S. V. Albrecht, F. Christianos, and L. Schäfer, Multi-agent reinforcement learning: Foundations and modern approaches. MIT Press, 2024.

[26]

J. Nash, “Non-cooperative games,” Annals of Mathematics, vol. 54, no. 2, pp. 286–295, 1951, Accessed: Apr. 29, 2026. [Online]. Available: http://www.jstor.org/stable/1969529.

[27]

J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, arXiv:1506.02438 [cs]“High-Dimensional Continuous Control Using Generalized Advantage Estimation.” arXiv, Oct. 2018, doi: 10.48550/arXiv.1506.02438.

[28]

Z. Guo, S. Shi, R. Willis, T. Tomilin, J. Z. Leibo, and Y. Du, arXiv:2503.14576 [cs]“SocialJax: An Evaluation Suite for Multi-agent Reinforcement Learning in Sequential Social Dilemmas.” arXiv, May 2025, doi: 10.48550/arXiv.2503.14576.

[29]

R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction, Second. The MIT Press, 2018.

[30]

S. Kakade and J. Langford, “Approximately optimal approximate reinforcement learning,” in Proceedings of the nineteenth international conference on machine learning, 2002, pp. 267–274.

[31]

D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times. American Mathematical Society, 2006.

\(\alpha\)-fair Heterogeneous Agent Reinforcement Learning