Paper deep dive
$α$-fair heterogeneous agent reinforcement learning
Yao-hua Franck Xu, Tayeb Lemlouma, Jean-Marie Bonnin, Arnaud Braud
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/9/2026, 5:04:22 AM
Summary
The paper addresses the lack of theoretical guarantees and stationarity in fairness-based multi-agent reinforcement learning (MARL) by introducing a novel framework that integrates α-fairness with Heterogeneous-Agent Trust Region Learning (HATRL). The proposed Fair HATRL framework employs a dynamically weighted fair advantage function to transition between utilitarian efficiency and α-fair welfare. It provides theoretical guarantees for monotonic improvement and convergence to Nash Equilibria. Two practical algorithms, α-fair HATRPO and α-fair HAPPO, are derived and evaluated on sequential social dilemmas (CleanUp and CommonHarvest), demonstrating superior utilitarian performance and socially fairer outcomes compared to existing baselines.
Entities (11)
Relation Signals (8)
Fair HATRL → bridges → Fairness
confidence 95% · We propose a novel framework that bridges α-fairness with Heterogeneous-Agent Trust Region Learning (HATRL)
Fair HATRL → convergesto → Nash Equilibria
confidence 95% · ensuring monotonic improvement and convergence toward Nash Equilibria
Fair HATRL → ensures → Monotonic Improvement
confidence 95% · ensuring monotonic improvement and convergence toward Nash Equilibria
α-fair HATRPO → extends → Fair HATRL
confidence 90% · We introduce two practical algorithms, α-fair HATRPO and α-fair HAPPO, and demonstrate through experiments
α-fair HAPPO → extends → Fair HATRL
confidence 90% · We introduce two practical algorithms, α-fair HATRPO and α-fair HAPPO
CommonHarvest → isa → Sequential Social Dilemmas
confidence 90% · test our algorithms on two sequential social dilemmas (SSD–[6]) environments called CleanUp and CommonHarvest
Cleanup → isa → Sequential Social Dilemmas
confidence 90% · test our algorithms on two sequential social dilemmas (SSD–[6]) environments called CleanUp and CommonHarvest
Fair HATRL → utilizes → Fair Advantage Function
confidence 90% · Our approach leverages a fair advantage function that dynamically weights agent utilities
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2606.13076v1
- Canonical: https://arxiv.org/abs/2606.13076v1
Trouble viewing inline? Open PDF directly →
Full Text
75,396 characters extracted from source content.
Expand or collapse full text
α-fair Heterogeneous Agent Reinforcement Learning Yao-hua Franck Xu Orange Innov Lannion, France franck.xu@orange.com Tayeb Lemlouma IRISA Université de Rennes Lannion, France tayeb.lemlouma@irisa.fr Jean-Marie Bonnin IRISA IMT Atlantique Rennes, France jean-marie.bonnin@irisa.fr Arnaud Braud Orange Innov Lannion, France arnaud.braud@orange.com Abstract Cooperation in multi-agent systems is typically optimized through utili- tarian 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α-fairness with Heterogeneous-Agent Trust Region Learning (HATRL), ensuring monotonic improvement and conver- gence 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α-fairness welfare based on the parameterα. We introduce two practical algorithms,α-fair HATRPO andα-fair HAPPO, and demon- strate 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 ([25]) to complex human societies([14]). Within Multi-Agent Reinforcement Learning (MARL), cooperation has traditionally been viewed through a utilitarian lens ([19,18]), 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 ([28]) 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, [24]). Preprint. arXiv:2606.13076v1 [cs.MA] 11 Jun 2026 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, [6]), penalize differences in temporal rewards to solve social dilemmas. However, these approaches often rely on history-dependent rewards (FEN [7], Fair&LocalIA[3], IA[6]), which break the stationary property of Markov Games. Furthermore, they frequently utilize Proximal Policy Optimization (PPO–[20]) based algorithms like Independent PPO (IPPO–[27]) or Multi-Agent PPO (MAPPO–[30]), which, while popular, lack the rigorous theoretical convergence guarantees found in single-agent Trust Region Learning (TRL – [20]) methods. FCGrad ([11]) 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[4], DeCOM[29], EcoFair-CH-MARL[2]), 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 ([26]), Proportional Fairness ([10]) orα-fairness ([16,13]) offer a more unified goal (Fair MARL[28], SOTO[32], AT-FAPPO [22], or [8]), yet their practical implementations still largely rely on extrapolated PPO objectives that lack theoretical safeguards, and existing theoretical guarantees (e.g., in SOTO [32]) 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– [31,12]). By combining theα-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 α-fair HATRL and study the theoretical properties of the learning framework. Thirdly, we develop two algorithms calledα-fair HATRPO andα-fair HAPPO that extendα-fair HATRL to practical settings. Finally, we test our algorithms on two sequential social dilemmas (SSD–[6]) environments called CleanUp and CommonHarvest and compare them to other methods relying on the same fair objective function. We demonstrate thatα-fair HATRPO andα-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 byRand positive real numbers byR + andd-dimensional real-numbered vector spaces asR d . Interval of integers betweenaandbare denoted by Ja;bK. ByP(A), we denote the power set of a setA. We write|A|for the cardinality of a finite setA. We use the vector notation⃗.to refer to any element in a cartesian product, i.e for any sets A 1 , ..., A n , ⃗a = (a 1 , ..., a n )∈ × n i=1 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–[1]). In this work, we consider a general-sum Markov game, meaning there is no condition on the reward functions. A Markov gameMis defined by the following tuple: (N, ̃ S,A i i∈N ,P,ρ 0 ,r i i∈N ,γ), with Nthe finite set ofnplayers, ̃ Sthe space of all possible states of the environment,A i i∈N the individual action set for each player,P( ̃s ′ ,⃗a, ̃s) =P(s ′ |s,⃗a) the transition probability kernel, 2 ρ 0 ∈∆( ̃ S) the initial state distribution,r i i∈N the individual reward for each player and γ ∈[0,1) the discount factor. At time stept∈ N, the environment is at states t ∈Sand each agent has to take an actiona i ∈A i according to their policyπ i (·|s t ). Given the environment states t and the joint action⃗a∈Adrawn by their joint policy⃗π(·|s t ) = Q n i=1 π i (·|s t ), the environment moves to the next state s t+1 ∈S sampled by the transition probability kernel P( ̃s ′ ,⃗a, ̃s) =P( ̃s ′ | ̃s,⃗a) and each agent receive its rewardr i (s t ,⃗a t )∈ R + . The sequence τ= (s 0 ,⃗a 0 ,⃗r 0 ,s 1 ,⃗a 1 ,⃗r 1 ,...) is called a trajectory. All together, the discount factor, the joint policy and the transition kernel induce an improper state visitation distribution d ⃗π . Let us define the contextualized states= ( ̃s, ̃c)∈ ̃ S × ̃ S, where ̃cis 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 agentirespectively:V ⃗π i (s) = E τ P ∞ t=0 γ t r i t (s t ,⃗a t ) | s 0 = s andQ ⃗π i (s,⃗a) =E τ P ∞ t=0 γ t r i t (s t ,⃗a t ) | s 0 = s, ⃗a 0 = ⃗a . The advantage function associated to agent i is A ⃗π i (s,⃗a) = Q ⃗π i (s,⃗a)− V ⃗π i (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 [31] was built on top of the single-agent Trust Region Learning (TRL) framework, where one agent tries to maximize a single reward signalr. TRL relies on a first-order approximation of the expected returnJ coop (π) =E τ∼π [ P ∞ t=0 γ t r t ] . Formally, for any policies πandπ ′ , TRL gives a lower bound ofJ coop (π ′ )− J coop (π) using the surrogate function L π ( ̃π) = J coop (π) + E s∼d π ,a∼ ̃π [A π (s,a)] and D max KL (π , π ′ ) = max s D KL (π(·|s)∥ ̃π(·|s)): J coop (π ′ )≥ L π ( ̃π)− CD max KL (π , π ′ ),(1) where C = 4γ max s,a |A π (s,a)| (1−γ) 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σbe a permutation ofJ1 ;nK. LetI m =i 1 ,...,i m denote an ordered subset of the shuffled interval, wherei k =σ(k). Let−I m refer to its complement. HATRL defines the multi-agent state-action value function as Q ⃗π,I m (s, ⃗a I m ) = E ⃗a −I m ∼⃗π −I m Q ⃗π (s, ⃗a I m ,⃗a −I m ) ,(2) and for disjoint sets J k and I m , the multi-agent advantage function is defined as A ⃗π,I m (s,⃗a J k ,⃗a I m ) = Q ⃗π,J k +I m (s, ⃗a J k +I m )− Q ⃗π,J k (s, ⃗a J k ).(3) Formally, HATRL can be described as followed. Let⃗πbe the current joint policy, ⃗π ′ be any other policy andI n a shuffled order. Let us defineL I m ⃗π (⃗π ′I m−1 ,π ′i m ) = E s∼d ⃗π ,⃗a I m−1 ,a i m ∼π ′i m [A ⃗π,i m (s,⃗a I m−1 ,a i m )]. HATRL states that TRL’s surrogate function applied on joint policy can be decomposed intonordered summands, them-th summand depending only on the m first policies: J coop (⃗π ′ )≥ J coop (⃗π) + n X m=1 L I m ⃗π (⃗π ′I m−1 ,π ′i m )− C· D max KL π i m , π ′i m .(4) Them-th summand can be interpreted as a first order approximation ofJ(⃗π ′ )− J(⃗π) with respect to them-th policy for the given orderI n . Hence, instead of maximizing directly J (⃗π), HATRL tries to maximize each summand of the surrogate function sequentially: π i m k+1 = arg max π i m L I m ⃗π k (⃗π I m−1 k+1 ,π i m )− C· D max KL π i m k , π i m . To apply this procedure in practical settings with parametrised policiesπ i θ (we usually confoundπ i θ with its parametersθ i for simplicity), [31] developed Heterogeneous-Agent 3 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 [31] Section 4 for more details, or [12] 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 ⃗π (s,⃗a) = P n j=1 A ⃗π i (s,⃗a)). In that case, the global objective is exactly the utilitarian objective. 2.4 α-fairness function In networking,α-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 α (x) = ( x 1−α 1−α for α̸= 1, ln(x) for α = 1. The parameterαcontrols the level of fairness. Whenα →0, the efficiency is preferred over how resources are distributed among users. On the other hand, whenαtends to +∞, the network just cares about the user with the lower resources. Forα= 1, we obtain the proportional fairness objective ([10]), 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 (⃗π) = E s 0 ∼ρ 0 " n X i=1 U α ν + V ⃗π i (s 0 ) # , whereν >0 is a constant to ensure positiveness of the inner expression andU α is theα-fair function. This objective can model different type of objective functions. Whenα →0, the global objective tends to the utilitarian objectiveJ util (⃗π) =E s 0 ∼ρ 0 P n i=1 V ⃗π i (s 0 ) . On the other hand, whenαtends to +∞, the global objective is equivalent to the Rawlsian welfare function J Rawls (⃗π) =E s 0 ∼ρ 0 min i V ⃗π i (s 0 ) . Forα= 1, the global objective becomes the proportional fairness objective J Prop (⃗π) = E s 0 ∼ρ 0 P n i=1 logV ⃗π i (s 0 ) . To adapt HATRL to our global fair objective, we first introduce some notations. Definition 3.1. Let⃗πbe the joint policies. For any contextualized states= ( ̃s, ̃c) and joint actions ⃗a∈A, let us define V ⃗π j ( ̃s, ̃c) = ν + V ⃗π j ( ̃c, ̃c) α and the fair advantage function A ⃗π F (s,⃗a) = n X j=1 A ⃗π j (s,⃗a) V ⃗π j (s) .(5) We start by introducing a fundamental lemma which presents a bound for the difference J (⃗π ′ )− J (⃗π) with a surrogate function that is similar the one introduced in TRL. Lemma 3.1. Let⃗πbe a policy and⃗π ′ be an other policy. Let us define the surrogate function L ⃗π (⃗π ′ ) = E s∼d ⃗π , ⃗a∼⃗π ′ (·|s) A ⃗π F (s,⃗a) . 4 For the global objective defined previously, the differenceJ(⃗π ′ )− J(⃗π) is bounded and the following inequality L ⃗π (⃗π ′ )≥ J (⃗π ′ )− J (⃗π)≥L ⃗π (⃗π ′ )− C· D max KL (⃗π || ⃗π ′ ) holds, where C = 4nαν −1−α (1−γ) 2 A 2 max + 4nA max γ ν α (1−γ) 2 and A max = max j,s,⃗a |A ⃗π j (s,⃗a)| See Appendix B.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 3.2. Letσbe a permutation ofJ1 ;nK. LetI m =i 1 ,...,i m denote an ordered subset of the shuffled interval, wherei k =σ(k). Let−I m refer to its complement. We define the agent j’s state-action value function as Q ⃗π,I m j (s, ⃗a I m ) = E ⃗a −I m ∼⃗π −I m Q ⃗π j (s, ⃗a I m ,⃗a −I m ) ,(6) and for disjoint sets J k and I m , the agent j’s advantage function is defined as A ⃗π,I m j (s,⃗a J k ,⃗a I m ) = Q ⃗π,J k ⊔I m j (s, ⃗a J k ⊔I m )− Q ⃗π,J k j (s, ⃗a J k ).(7) Finally, we define the multi-agent fair advantage function as: A ⃗π,I m F (s,⃗a J k ,⃗a I m ) = n X j=1 1 V ⃗π j (s) A ⃗π,I m j (s,⃗a J k ,⃗a I m )(8) 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. Lemma 3.2. For any agent j and subset I m ⊆ I n , we have A ⃗π,I m F (s,⃗a I m ) = A ⃗π,I m F (s,a ∅ ,⃗a I m ) = m X l=1 A ⃗π,i l F (s,⃗a I l−1 ,a i l )(9) See Appendix B.2 for the proof. This lemma is the foundation for sequential update. LetI n be an arbitrary order. Suppose agenti 1 takes the first actiona i 1 such that it improves its local fair advantage function, the subsequent agenti m can then sample its own actiona 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.3. Let⃗πbe a joint policy,⃗π ′I m−1 be some other joint policy of agentsI m−1 , and π ′i m be some other policy of agent i m . Then L I m ⃗π (⃗π ′I m−1 ,π ′i m ) = E s ∼ d ⃗π , ⃗a I m−1 ∼⃗π ′I m−1 (.|s),a i m ∼π ′i m (.|s) h A ⃗π,i m F s,⃗a I m−1 ,a i m i (10) Note that, for any ⃗π ′I m−1 and π ′i m = π i m L I m ⃗π (⃗π ′I m−1 ,π i m ) = 0(11) Thanks to lemma and theorem, we can generalize HATRL to our global fair objective. Lemma 3.3. Let⃗πand⃗π ′ be two joint policies, andI n an order, the surrogate function can be decomposed into n summands: J (⃗π ′ )− J (⃗π)≥ n X m=1 L I m ⃗π (⃗π ′I m−1 ,π ′i m )− C· D max KL π i m , π ′i m .(12) 5 See Appendix B.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 L I m ⃗π (⃗π ′I m−1 ,π ′i m )− CD max KL π i m , π ′i m 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. Algorithm 1 Multi-Agent Policy Iteration with Monotonic Improvement Guarantee 1: Initialize the joint policy ⃗π 0 = (π 1 0 ,...,π n 0 ). 2: for k = 0, 1,... do 3: Compute the fair advantage functionA ⃗π k F (s,⃗a) for all state-action pairs (s,a) and all agent j. 4: Compute ω = max j,s,⃗a |A ⃗π k j (s,⃗a)| and C = 4nαν −1−α (1−γ) 2 ω 2 + 4nωγ ε α (1−γ) 2 . 5: Draw a permutation I n of agents at random. 6: for m = 1,...,n do 7:Make an update π i m k+1 = arg max π i m h L I m ⃗π k (⃗π I m−1 k+1 ,π i m )− CD KL (π i m k ∥ π i m ) i . 8: end for 9: end for 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. Definition 3.4. (Gâteaux Derivative) Let⃗π,⃗π ′ be two joint policies andη >0 a positive number. Let us define the perturbed policiesπ i η =π i +η(π ′i − π i ), all together define the joint perturbed policy⃗π η . If the limit exists, we define the Gateaux derivative of a function f (⃗π) asD ⃗π ′ f (⃗π) = lim η→0 f (⃗π η )−f (⃗π) η . The surrogate function is actually the Gateaux derivative of J (⃗π) in the ⃗π ′ direction. Lemma 3.4. Let⃗πbe a policy and⃗π ′ be another policy. The following statement holds: D ⃗π ′ J (⃗π) =L ⃗π (⃗π ′ ). See Appendix B.5 for the proof. The lemma provides a deeper understanding of Fair HATRL. Indeed, at each iterationk+ 1, the current joint policy⃗π k is moving toward the joint policy ⃗π ′ 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 3.5 (Nash equilibrium). In a fully-cooperative game, a joint policy⃗π ∗ = (π 1 ∗ ,...,π n ∗ ) is a Nash equilibrium (NE) if for everyi∈ N,πî∈Π i impliesJ(⃗π ∗ )≥ J(π i ,⃗π −i ∗ ). NE ([17]) 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. Theorem 3.5. 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 (⃗π k+1 )≥ J (⃗π k ), • The fair global objective converges: lim k→∞ J (⃗π k ) = J ∞ , •The set of joint policies’ limit points is non empty, each of which is a Nash equilibrium. See Appendix B.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. 6 4 Practical algorithms In practical settings, we employ Deep Reinforcement Learning (DRL) by parameterizing each agent’s policyπ i withθ i to accommodate high-dimensional state and action spaces. For brevity, we denote the policyπ i θ i simply asθ 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 [31] for further details. 4.1 α-fair HATRPO Similarly to HATRPO ([31]) and TRPO ([20]), we replace the KL-penalty by a KL-constraint to avoid computingCandD max KL θ i m k , θ i m in Algorithm 1. Formally, at every iterationk+ 1, given a permutationI n , Fair-HATRPO sequentially optimises agenti m policy parameters θ i m k+1 by solving the following optimization problem for a given a KL-radius δ > 0: θ i m k+1 = arg max θ i m E s ∼ d ⃗ θ k , ⃗a I m−1 ∼ ⃗ θ I m−1 k+1 (.|s),a i m ∼θ i m (.|s) h A ⃗ θ k ,i m F s,⃗a I m−1 ,a i m i subject to E s∼d ⃗ θ k D KL θ i m k (·|s),θ i m (·|s) ≤ δ. (13) 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: θ i m k+1 = θ i m k + β j s 2δ g i m k (H i m k ) −1 g i m k (H i m k ) −1 g i m k ,(14) whereH i m k =∇ 2 θ i m E s∼d ⃗ θ k D KL θ i m k (·|s),θ i m (·|s) θ i m =θ i m k is the Hessian of the expected KL-divergence,g i m k is the gradient of the objective function,β j is computed via backtracking line search, and the product (H i m k ) −1 g i m k can be efficiently computed using the conjugate gradient algorithm. For a given batchBof trajectories with lengthT, let ˆ A ⃗ θ k F (s,⃗a) be the estimator of the fair advantage functionA ⃗ θ k F (s,⃗a). Then, the gradient of the objective function can be estimated using the following formula: ˆg i m k = 1 |B| X τ∈B T X t=0 M I m F (s t ,⃗a t )∇ θ i m logπ i m θ i m a i m t |s t | θ i m =θ i m k .(15) whereM I m F = ⃗π ′I m−1 (⃗a I m−1 |s) ⃗π I m−1 (a I m−1 |s) ˆ A ⃗ θ k F (s,⃗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–[21]). 4.2 α-fair HAPPO Similarly to HAPPO and PPO, we propose a first order approximation and avoid the computation of the hessianH i m k . Thus, agenti m updates its parameterθ i m by maximizing the following clipping objective E s∼d ⃗ θ k ,⃗a∼ ⃗ θ k min π i m θ im a i m |s π i m θ im k (a i m |s) M I m (s,⃗a), clip π i m θ im a i m |s π i m θ i m k (a i m |s) , 1± ε M I m (s,⃗a) . (16) 7 5 Experiments and Results Finally, we test both our algorithms on two SSD – CleanUp and Harvest ([6]) – against state-of-the-art algorithms. We built our experiments upon the environments provided by SocialJax ([5]). All hyperparameter settings and implementations details can be found in Appendix D.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α∈0.5,1,1.5and 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 [28]. 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 D.3. Common Harvest. The Figure 1 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α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. CleanUp Results are presented in Figure 2. We can draw similar conclusion compared to Harvest ; especially that higher value ofα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α= 1.5 as the learning curve suffered from high drop of TAC. 6 Discussions and limitations During hyperparameter optimization, we observed significant performance degradation for high values ofα(specifically,α >1). Asαincreases, the fair advantage function (Equation 5) 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α-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,α-fair HATRPO andα-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. 8 00.20.40.60.81 ·10 8 50 100 150 200 250 300 timestep Apples consumed Total apples consumed HATRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 50 100 150 200 250 300 timestep Apples consumed Total apples consumed HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 50 100 150 200 250 300 timestep Apples consumed Total apples con- sumed forα= 1 FMAPPO FHATRPO FHAPPO 00.20.40.60.81 ·10 8 0 0.2 0.4 0.6 timestep Gini Index Gini index HA- TRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 0.2 0.4 0.6 timestep Gini Index Gini Index HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 0.1 0.2 0.3 0.4 timestep Gini Index Gini Index forα= 1 FMAPPO FHATRPO FHAPPO Figure 1: 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. 00.20.40.60.81 ·10 8 0 200 400 600 800 1,000 1,200 timestep Apples consumed Total apples consumed HATRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 200 400 600 800 1,000 1,200 timestep Apples consumed Total apples consumed HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 500 1,000 timestep Apples consumed Total apples con- sumed forα= 1 FMAPPO FHATRPO FHAPPO 00.20.40.60.81 ·10 8 0 0.2 0.4 0.6 0.8 timestep Gini Index Gini index HA- TRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 0.2 0.4 0.6 0.8 timestep Gini Index Gini Index HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 0.2 0.4 0.6 0.8 timestep Gini Index Gini Index forα= 1 FMAPPO FHATRPO FHAPPO Figure 2: 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. 9 7 Conclusion This work introduces a novel framework that bridgesα-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—α-fair HATRPO andα-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. Acknowledgments and Disclosure of Funding 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.c/Conferences/2026/PaperInformation/FundingDisclosure. Do not include this section in the anonymized submission, only in the final paper. You can use theackenvironment provided in the style file to automatically hide this section in the anonymized submission. 10 References [1] Stefano V. Albrecht, Filippos Christianos, and Lukas Schäfer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2024. [2]Saad Alqithami. EcoFair-CH-MARL: Scalable Constrained Hierarchical Multi-Agent RL with Real-Time Emission Budgets and Fairness Guarantees. October 2025. arXiv:2603.14625 [cs]. [3]Alper Demir, Hüseyin Aydın, Kale-ab Abebe Tessera, David Abel, and Stefano V. Albrecht. Fairness over Equality: Correcting Social Incentives in Asymmetric Sequential Social Dilemmas, February 2026. arXiv:2602.15407 [cs]. [4] Promise Ekpo, Saesha Agarwal, Felix Grimm, Lekan Molu, and Angelique Taylor. Fair-GNE : Generalized Nash Equilibrium-Seeking Fairness in Multiagent Healthcare Automation, November 2025. arXiv:2511.14135 [cs] version: 1. [5] Zihao Guo, Shuqing Shi, Richard Willis, Tristan Tomilin, Joel Z. Leibo, and Yali Du. SocialJax: An Evaluation Suite for Multi-agent Reinforcement Learning in Sequential Social Dilemmas, May 2025. arXiv:2503.14576 [cs]. [6] Edward Hughes, Joel Z. Leibo, Matthew G. Phillips, Karl Tuyls, Edgar A. Duéñez- Guzmán, Antonio García Castañeda, Iain Dunning, Tina Zhu, Kevin R. McKee, Raphael Koster, Heather Roff, and Thore Graepel. Inequity aversion improves cooperation in intertemporal social dilemmas, September 2018. arXiv:1803.08884 [cs]. [7]Jiechuan Jiang and Zongqing Lu. Learning Fairness in Multi-Agent Systems. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. [8]Peizhong Ju, Arnob Ghosh, and Ness B. Shroff. Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning, June 2023. arXiv:2306.00324 [cs]. [9] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, ICML ’02, page 267–274, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. [10]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, 49(3):237–252, 1998. [11] Woojun Kim and Katia Sycara. Fair cooperation in mixed-motive games via conflict- aware gradient adjustment, 2025. [12]Jakub Grudzien Kuba, Xidong Feng, Shiyao Ding, Hao Dong, Jun Wang, and Yaodong Yang. Heterogeneous-Agent Mirror Learning: A Continuum of Solutions to Cooperative MARL, August 2022. arXiv:2208.01682 [cs]. [13]Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. In 2010 Proceedings IEEE INFOCOM, pages 1–9, 2010. [14]Paul A. M. Van Lange. Social Dilemmas: Understanding Human Cooperation. OUP USA, 2014. Google-Books-ID: KfhMAgAAQBAJ. [15]David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006. [16]J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking, 8(5):556–567, 2000. [17] John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286–295, 1951. 11 [18]Julien Pérolat, Joel Z Leibo, Vinicius Zambaldi, Charles Beattie, Karl Tuyls, and Thore Graepel. A multi-agent reinforcement learning model of common-pool resource appropriation. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. [19] Stefan Roesch, Stefanos Leonardos, and Yali Du. Selfishness Level Induces Cooperation in Sequential Social Dilemmas. [20]John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust Region Policy Optimization, April 2017. arXiv:1502.05477 [cs]. [21]John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- Dimensional Continuous Control Using Generalized Advantage Estimation, October 2018. arXiv:1506.02438 [cs]. [22] Umer Siddique, Peilang Li, and Yongcan Cao. Towards Fair and Equitable Policy Learning in Cooperative Multi-Agent Reinforcement Learning. 2024. [23]Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. [24] Khanh-Tung Tran, Dung Dao, Minh-Duong Nguyen, Quoc-Viet Pham, Barry O’Sullivan, and Hoang D. Nguyen. Multi-Agent Collaboration Mechanisms: A Survey of LLMs, January 2025. arXiv:2501.06322 [cs]. [25]Stuart A. West, Ashleigh S. Griffin, and Andy Gardner. Evolutionary Explanations for Cooperation. Current Biology, 17(16):R661–R672, August 2007. [26] John A. Weymark. Generalized gini inequality indices. Mathematical Social Sciences, 1(4):409–430, 1981. [27]Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip H. S. Torr, Mingfei Sun, and Shimon Whiteson. Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?, November 2020. arXiv:2011.09533 [cs]. [28]Yao-hua Franck Xu, Tayeb Lemlouma, Arnaud Braud, and Jean-Marie Bonnin. Altruism and Fair Objective in Mixed-Motive Markov games, February 2026. arXiv:2602.08389 [cs]. [29]Zhaoxing Yang, Haiming Jin, Rong Ding, Haoyi You, Guiyun Fan, Xinbing Wang, and Chenghu Zhou. DeCOM: Decomposed Policy for Constrained Cooperative Multi-Agent Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 37(9):10861–10870, June 2023. [30]Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games, November 2022. arXiv:2103.01955 [cs]. [31]Yifan Zhong, Jakub Grudzien Kuba, Xidong Feng, Siyi Hu, Jiaming Ji, and Yaodong Yang. Heterogeneous-Agent Reinforcement Learning. [32] Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. Learning Fair Policies in Decentralized Cooperative Multi-Agent Reinforcement Learning. In Proceedings of the 38th International Conference on Machine Learning, pages 12967–12978. PMLR, July 2021. 12 A Preliminaries A.1 Assumptions and Definitions We use the same assumption as in HATRL [31]: Assumption 1. There existsη ∈ R, such that 0< η ≪1, and for every agenti∈N, the policy space Π i isη-soft; that means that for everyπ i ∈Π i ,s ∈ S, anda i ∈ A i , we have π i (a i |s)≥ η. Definition A.1. Let X be a finite set and p : X → R, q : X → R be two maps. Then, the notion of distance betweenpandqthat we adopt is given by∥p−q∥≜ max x∈X |p(x)−q(x)|. We also introduce the new probability distribution for the contextualized state: Definition A.2. Let ̃ M= (N, ̃ S,A i i∈N , ̃ P, ̃ρ 0 , ̃r i i∈N ,γ) be a Markov game. We define the Markov gameM= (N,S,A i i∈N ,P,ρ 0 ,r i i∈N ,γ) for the contextualized state S = ̃ S× ̃ S where for any contextualized state s = ( ̃s, ̃c): • ρ 0 (s) = ρ 0 ( ̃s, ̃c) = ̃ρ 0 ( ̃s)1 ̃s= ̃c is the initial state distribution, • for any joint action⃗a ∈ Aand other states ′ ,P(s,⃗a,s ′ ) = ̃ P ( ̃s,⃗a, ̃s ′ )1 ̃c ′ = ̃c is the transition kernel, • for any agent i and joint action ⃗a, r i (s,⃗a) = ̃r i ( ̃s,⃗a) is the reward function. A.2 Preliminary results Lemma A.1. Every agenti’s policy space Π i is convex and compact under the maximum norm. Lemma A.2. The improper state distribution d ⃗π is continuous in ⃗π. Lemma A.3. Let⃗πbe a policy. Then, for any agenti,Q ⃗π i (s,⃗a) is Lipsichtz-continuous in ⃗π. Proof.For proof of the lemmas A.1, A.2, A.3, see [31] (Appendix A.2 Lemma 3, 4, 5). Notice that in [31], 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 forQ π (see [23], Chapter 3.5) which also hold in our Multi-agent settings. Lemma A.4. The function U α is Lipschitz-continuous on R + . Proof. Let us recall U α (x) = x 1−α 1−α for α̸= 1 and U α (x) = ln(x) for α = 1. The α-fairness function is differentiable on [ν; +∞[ and for any α≥ 0, U ′ α (x) = x −α On [ν; +∞[,|U ′ α (x)|is bounded byε −α . Thus,U α is Lipschitz-continuous with constant ν −α . Corollary A.4.1. From Lemma A.3 and Lemma A.4, for any agenti, we obtain that the following functions are Lipschitz-continuous in π: • the state value function V ⃗π i (s) = P ⃗a ⃗π(⃗a|s)Q ⃗π i (s,⃗a), • the advantage function A ⃗π i (s,⃗a) = Q ⃗π i (s,⃗a)− V ⃗π i (s), • the fair global objective J (⃗π) = E s∼ρ 0 [ P n i=1 U α ν + V ⃗π i (s) ], • and the fair advantage function A ⃗π F (s,⃗a) = P n j=1 A ⃗π j (s,⃗a) V ⃗π j (s) 13 Lemma A.5. Let⃗πand⃗π ′ be some policies. The quantityE s∼d ⃗π ,⃗a∼⃗π ′ (·|s) A ⃗π F (s,⃗a) is continuous with ⃗π. Proof. We have E s∼d ⃗π ,⃗a∼⃗π ′ (·|s) A ⃗π F (s,⃗a) = X s X ⃗a d ⃗π (s)⃗π(⃗a|s)A ⃗π F (s,⃗a),(17) the continuity is induced by continuity of d ⃗π (Lemma A.2) and A ⃗π F (Corollary A.4.1). BHeterogeneous 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. B.1 Previous results In this section, we list the useful lemma proved in TRL [20] that holds in our multi-agent settings. Lemma B.1. Let⃗πand⃗π ′ be two stochastic policies’ profiles. For any agenti, the difference in their expected returns for a given initial state s 0 ∈S is given by: V ⃗π ′ i (s 0 )− V ⃗π i (s 0 ) = E τ∼⃗π ′ " ∞ X t=0 γ t A ⃗π i (s t ,⃗a t )| s 0 # Proof. The proof is similar to the performance difference lemma demonstrated in [20] (Lemma 1) or in [9] (Lemma 6.1): E τ∼⃗π ′ " ∞ X t=0 γ t A ⃗π i (s t ,⃗a t )| s 0 # = E τ∼⃗π ′ " ∞ X t=0 γ t r i (s t ,⃗a t ) + γV ⃗π i (s t+1 )− V ⃗π i (s t ) | s 0 # = E τ∼⃗π ′ " ∞ X t=0 γ t r i (s t ,⃗a t )| s 0 # + E τ∼⃗π ′ " ∞ X t=0 γ t γV ⃗π i (s t+1 )− V ⃗π (s t ) | s 0 # = V ⃗π ′ i (s 0 ) + E τ∼⃗π ′ " ∞ X t=0 γ t+1 V ⃗π i (s t+1 )− γ t V ⃗π i (s t ) | s 0 # = V ⃗π ′ i (s 0 ) + E τ∼⃗π ′ h −V ⃗π i (s 0 ) + lim T→∞ γ T V ⃗π i (s T )| s 0 i = V ⃗π ′ i (s 0 )− V ⃗π i (s 0 ) Lemma B.2. For any agenti, any states∈Sand a joint strategy profile⃗π, the following result holds: E ⃗a∼⃗π(·|s) [A ⃗π i (s,⃗a)] = 0 Proof. For any state s, we have E ⃗a∼⃗π(·|s) [A ⃗π i (s,⃗a)] = E ⃗a∼⃗π(·|s) [Q ⃗π i (s,⃗a)− V ⃗π i (s)] = E ⃗a∼⃗π(·|s) [Q ⃗π i (s,⃗a)]− E ⃗a∼⃗π(·|s) [V ⃗π i (s)] = V ⃗π i (s)− V ⃗π i (s) = 0 14 Lemma B.3. Let us define ̄ A ⃗π ′ ,⃗π i (s) =E ⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) . For any states∈Sand any κ-coupled policy pair (⃗π,⃗π ′ ), the magnitude of the expected joint advantage functionA ⃗π (s,⃗a) evaluated under the policy⃗π ′ is upper-bounded by the Total Variation (TV) distance between the two profiles: E ⃗a∼⃗π ′ (·|s) [A ⃗π i (s,⃗a)] ≤ 2D TV (⃗π ′ (·|s)∥ ⃗π(·|s)) max ⃗a |A ⃗π i (s,⃗a)| Proof. We use the previous Lemma B.2 to write 0 differently: ̄ A ⃗π ′ ,⃗π i (s) = E ⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) = E ⃗a∼⃗π ′ (·|s) [A ⃗π i (s,⃗a)]− E ⃗a∼⃗π(·|s) [A ⃗π i (s,⃗a)] = X ⃗a (⃗π ′ (⃗a|s)− ⃗π(⃗a|s))A ⃗π i (s,⃗a) ≤ X ⃗a |⃗π ′ (⃗a|s)− ⃗π(⃗a|s)|· max ⃗a |A ⃗π i (s,⃗a)| ≤ 2ε i (s)D TV (⃗π ′ (·|s)∥ ⃗π(·|s)), where ε i (s) = max ⃗a |A ⃗π i (s,⃗a)|. Lemma B.4. Letκ=D max KL (⃗π , ⃗π ′ ) =max s D KL (⃗π(·|s),⃗π ′ (·|s))Let (⃗π,⃗π ′ ) be anκ-coupled policy pair. Then, the following statement holds: E s t ∼⃗π ′ [A ⃗π ′ ,⃗π i (s t )]− E s t ∼⃗π [A ⃗π ′ ,⃗π i (s t )] ≤ 4κ max s,a |A ⃗π i (s,a)| ≤ 4κ(1− (1− κ) t ) max s,a |A ⃗π i (s,a)| Proof. Let κ = D max KL (⃗π , ⃗π ′ ), then we can define an κ-coupled policy pair (⃗π,⃗π ′ ) such that P(⃗a k ̸= ⃗a ′ k |s k )≤ κ. See [15] (proposition 4.7). Hence, the probability that the two policies disagree on an action at any given time step is bounded by κ. Letn t be the number of times the policies diverge before time stept. The probability that they agree on all steps up to t− 1 is at least (1− κ) t . E s t ∼⃗π ′ [A ⃗π ′ ,⃗π i (s t )] = P(n t = 0)E s t ∼⃗π ′ |n t =0 [A ⃗π ′ ,⃗π i (s t )] + P(n t > 0)E s t ∼⃗π ′ |n t >0 [A ⃗π ′ ,⃗π i (s t )] Similarly for the policy ⃗π: E s t ∼⃗π [A ⃗π ′ ,⃗π i (s t )] = P(n t = 0)E s t ∼⃗π|n t =0 [A ⃗π ′ ,⃗π i (s t )] + P(n t > 0)E s t ∼⃗π|n t >0 [A ⃗π ′ ,⃗π i (s t )] Note thatn t = 0 terms are equal as it means that⃗πand⃗π ′ agreed on all the timesteps less than t: E s t ∼⃗π|n t =0 [A ⃗π ′ ,⃗π i (s t )] = E s t ∼⃗π ′ |n t =0 [A ⃗π ′ ,⃗π i (s t )] By definition, the probability that they disagree at least once before time t is bounded by: P(n t > 0)≤ 1− (1− κ) t Then, we have |E s t ∼⃗π ′ |n t >0 [A ⃗π ′ ,⃗π i (s t )]− E s t ∼π|n t >0 [A ⃗π ′ ,⃗π i (s t )]|(18) ≤|E s t ∼ ̃π|n t >0 [A ⃗π ′ ,⃗π i (s t )]| +|E s t ∼π|n t >0 [A ⃗π ′ ,⃗π i (s t )]| (19) ≤ 4κ max s,a |A ⃗π i (s,a)|(20) 15 Therefore, using Lemma B.3, we have E s t ∼⃗π ′ [A ⃗π ′ ,⃗π i (s t )]− E s t ∼⃗π [A ⃗π ′ ,⃗π i (s t )] ≤ 2(1− (1− κ) t ) max s | ̄ A ⃗π ′ ,⃗π i (s)| ≤ 4κ(1− (1− κ) t ) max s,a |A ⃗π i (s,a)| B.2 Proof of Lemma 3.1 Lemma 3.1. Let⃗πbe a policy and⃗π ′ be an other policy. Let us define the surrogate function L ⃗π (⃗π ′ ) = E s∼d ⃗π , ⃗a∼⃗π ′ (·|s) A ⃗π F (s,⃗a) . For the global objective defined previously, the differenceJ(⃗π ′ )− J(⃗π) is bounded and the following inequality L ⃗π (⃗π ′ )≥ J (⃗π ′ )− J (⃗π)≥L ⃗π (⃗π ′ )− C· D max KL (⃗π || ⃗π ′ ) holds, where C = 4nαν −1−α (1−γ) 2 A 2 max + 4nA max γ ν α (1−γ) 2 and A max = max j,s,⃗a |A ⃗π j (s,⃗a)| Proof. We are looking for a lower bound of J (⃗π ′ )− J (⃗π). J (⃗π ′ )− J (⃗π) = E s 0 ∼ρ 0 n X j=1 U α ε + V ⃗π j ′ (s 0 ) − U α ε + V ⃗π j (s 0 ) (21) As U α is concave, one interesting property is by y− x x α ≥ U α (y)− U α (x)≥ y− x y α .(22) Applying this property to the previous difference and using Lemma B.1 gives the lower bound J (⃗π ′ )− J (⃗π)≥ E s 0 ∼ρ 0 " V ⃗π j ′ (s 0 )− V ⃗π j (s 0 ) V ⃗π j ′ (s 0 ) # (23) = E s 0 ∼ρ 0 n X j=1 1 V ⃗π j ′ (s 0 ) E τ∼⃗π ′ |s 0 " ∞ X t=0 γ t A ⃗π j (s t ,⃗a t ) # (24) = E τ∼⃗π ′ ∞ X t=0 γ t n X j=1 A ⃗π j (s t ,⃗a t ) V ⃗π ′ j (s 0 ) (25) =F ⃗π (⃗π ′ ),(26) and the upper bound J (⃗π ′ )− J (⃗π)≤ E s 0 ∼ρ 0 " V ⃗π j ′ (s 0 )− V ⃗π j (s 0 ) V ⃗π j (s 0 ) # = E τ∼⃗π ′ ∞ X t=0 γ t n X j=1 A ⃗π j (s t ,⃗a t ) V ⃗π ′ j (s 0 ) =L ⃗π (⃗π ′ ). Let us defineA ⃗π ′ ,⃗π j (s) =E ⃗a∼⃗π ′ (·|s) A ⃗π j (s,⃗a) . Using that notation and conditional expecta- tion, we have F ⃗π (⃗π ′ ) = E τ∼⃗π ′ ∞ X t=0 γ t n X j=1 A ⃗π ′ ,⃗π j (s t ) V ⃗π ′ j (s 0 ) (27) 16 Ass t = ( ̃s t , ̃s 0 ) carries the initial state, we can drop the initial state dependency in the denominator: F ⃗π (⃗π ′ ) = E τ∼⃗π ′ ∞ X t=0 γ t n X j=1 A ⃗π ′ ,⃗π j (s t ) V ⃗π ′ j (s 0 ) = X s ρ 0 (s) ∞ X t=0 γ t X s ′ P ⃗π ′ (s t = s ′ |s 0 = s) n X j=1 A ⃗π ′ ,⃗π j (s ′ ) V ⃗π ′ j (s 0 ) = X ̃s, ̃c ρ 0 ( ̃s)1 ̃s= ̃c ∞ X t=0 γ t X ̃s ′ , ̃c ′ P ⃗π ′ ( ̃s t = ̃s ′ | ̃s 0 = ̃s)1 ̃c ′ = ̃c n X j=1 A ⃗π ′ ,⃗π j ( ̃s ′ , ̃c ′ ) V ⃗π ′ j ( ̃s, ̃c) = X ̃s, ̃c ρ 0 ( ̃s)1 ̃s= ̃c ∞ X t=0 γ t X ̃s ′ , ̃c ′ P ⃗π ′ ( ̃s t = ̃s ′ | ̃s 0 = ̃s)1 ̃c ′ = ̃c n X j=1 A ⃗π ′ ,⃗π j ( ̃s ′ , ̃c ′ ) V ⃗π ′ j ( ̃c ′ , ̃c ′ ) = X ̃s, ̃c ρ 0 ( ̃s)1 ̃s= ̃c X ̃s ′ , ̃c ′ ∞ X t=0 γ t P ⃗π ′ ( ̃s t = ̃s ′ | ̃s 0 = ̃s)1 ̃c ′ = ̃c n X j=1 A ⃗π ′ ,⃗π j ( ̃s ′ , ̃c ′ ) V ⃗π ′ j ( ̃c ′ , ̃c ′ ) = E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π ′ j (s) (28) Because the value function and the state distribution of the other policy⃗π ′ are unknown, we want to boundF ⃗π (⃗π ′ ) by⃗π-depended functions. Therefore, let us consider the following function: L ⃗π (⃗π ′ ) = E s∼d ⃗π n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) (29) We now want to bound the absolute difference of |F ⃗π (⃗π ′ )−L ⃗π (⃗π ′ )|: |F ⃗π (⃗π ′ )−L ⃗π (⃗π ′ )| = E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π ′ j (s) − E s∼d ⃗π n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) (30) ≤ E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π ′ j (s) − E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) |z =∆ 1 + E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) − E s∼d ⃗π n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) | z =∆ 2 (31) The first error ∆ 1 is due to a shift of state value functions between the two policies⃗πand⃗π ′ : ∆ 1 = E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π ′ j (s) − E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) = E s∼d ⃗π ′ n X j=1 1 V ⃗π ′ j (s) − 1 V ⃗π j (s) ! A ⃗π ′ ,⃗π j (s) 17 The functionf(v) = (ε+v) −α is Lipschitz continuous onR + . Thus, the following statement holds for any v, w ∈ R + : |f (v)− f (w)|≤ L α |v− w|,(32) where L α = max v∈R + |f ′ (v)| = αν −1−α is a Lipschitz constant. Therefore, we have 1 V ⃗π ′ j (s) − 1 V ⃗π j (s) = 1 f (V ⃗π ′ j (s)) − 1 f (V ⃗π j (s)) ≤ L α ·|V ⃗π ′ j (s)− V ⃗π j (s)| = L α · E τ∼⃗π ′ " ∞ X t=0 γ t A ⃗π j (s t ,⃗a t )|s 0 = s # = L α · E τ∼⃗π ′ " ∞ X t=0 γ t A ⃗π ′ ,⃗π j (s t )|s 0 = s # ≤ L α · E τ∼⃗π ′ " ∞ X t=0 γ t A ⃗π ′ ,⃗π j (s t ) | s 0 = s # ≤ 2L α 1− γ A max D max TV (⃗π, ⃗π ′ ) Plugging back the previous result into the first difference leads to: ∆ 1 = E s∼d ⃗π ′ n X j=1 1 V ⃗π ′ j (s) − 1 V ⃗π j (s) ! A ⃗π ′ ,⃗π j (s) ≤ E s∼d ⃗π ′ n X j=1 1 V ⃗π ′ j (s) − 1 V ⃗π j (s) A ⃗π ′ ,⃗π j (s) using Lemma B.3,(33) ≤ E s∼d ⃗π ′ n X j=1 4L α 1− γ A 2 max κ 2 = 4nL α (1− γ) 2 A 2 max κ 2 ,(34) where κ = D max TV (⃗π, ⃗π ′ ). 18 Next, we have to find an upper bound of the second difference ∆ 2 which is due to the shift of state visitation distribution: ∆ 2 = E s∼d ⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) − E s∼d ⃗π n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) = E τ∼⃗π ′ ∞ X t=0 γ t n X j=1 A ⃗π ′ ,⃗π j (s t ) V ⃗π j (s 0 ) − E τ∼⃗π ∞ X t=0 n X j=1 A ⃗π ′ ,⃗π j (s) V ⃗π j (s) = ∞ X t=0 γ t E τ∼⃗π ′ n X j=1 A ⃗π ′ ,⃗π j (s t ) V ⃗π j (s 0 ) − E τ∼⃗π n X j=1 A ⃗π ′ ,⃗π j (s t ) V ⃗π j (s 0 ) = ∞ X t=0 γ t E s 0 ∼ρ 0 E τ∼⃗π ′ |s 0 n X j=1 A ⃗π ′ ,⃗π j (s t ) V ⃗π j (s 0 ) − E τ∼⃗π|s 0 n X j=1 A ⃗π ′ ,⃗π j (s t ) V ⃗π j (s 0 ) ≤ ∞ X t=0 γ t E s 0 ∼ρ 0 n X j=1 1 V ⃗π j (s 0 ) E τ∼⃗π ′ |s 0 h A ⃗π ′ ,⃗π j (s t ) i − E τ∼⃗π|s 0 h A ⃗π ′ ,⃗π j (s t ) i Let us recall Lemma B.4: E τ∼⃗π ′ |s 0 h A ⃗π ′ ,⃗π j (s t ) i − E τ∼⃗π|s 0 h A ⃗π ′ ,⃗π j (s t ) i ≤ 4κ(1− (1− κ) t )A max . Moreover, 1 V ⃗π j (s 0 ) is upper bounded by ν −α . Thus, we have ∆ 2 ≤ ∞ X t=0 γ t E s 0 ∼ρ 0 n X j=1 1 V ⃗π j (s 0 ) E τ∼⃗π ′ |s 0 h A ⃗π ′ ,⃗π j (s t ) i − E τ∼⃗π|s 0 h A ⃗π ′ ,⃗π j (s t ) i (35) ≤ ∞ X t=0 γ t E s 0 ∼ρ 0 4nA max ν −α (1− (1− κ) t )κ (36) ≤ ∞ X t=0 γ t 4nA max ν −α (1− (1− κ) t )κ(37) ≤ 4nA max κ ν α 1 1− γ − 1 1− γ(1− κ) (38) ≤ 4nA max γκ 2 ν α (1− γ) 2 (39) Therefore, by combining both inequalities, we have : |F ⃗π (⃗π ′ )−L ⃗π (⃗π ′ )|≤ ∆ 1 + ∆ 2 ≤ 4nL α (1− γ) 2 A 2 max κ 2 + 4nA max γ ν α (1− γ) 2 κ 2 (40) This concludes the proof. B.3 Proof of Lemma 3.2 The Lemma 3.2 is induced by individual advantage functions decomposition: Lemma B.5. For any agent j and subset I m ⊆ I n , we have A ⃗π,I m j (s,⃗a I m ) = A ⃗π,I m (s,a ∅ ,⃗a I m ) = m X l=1 A ⃗π,i m j (s,⃗a I m−1 ,⃗a i m )(41) 19 Proof. For any state s and joint action ⃗a I m , we have A ⃗π,I m j (s,⃗a I m ) = A ⃗π,I m (s,a ∅ ,⃗a I m )(42) = Q ⃗π, ∅⊔I m j (s, ⃗a ∅⊔I m )− Q ⃗π, ∅ j (s, a ∅ )(43) = Q ⃗π,I l j (s, ⃗a I l )− V ⃗π j (s)(44) = m X l=1 Q ⃗π,I l j (s, ⃗a I l )− Q ⃗π,I l−1 j (s, ⃗a I l−1 )(45) = m X l=1 A ⃗π,i l j (s,⃗a I l−1 ,a i l )(46) Lemma 3.2. For any agent j and subset I m ⊆ I n , we have A ⃗π,I m F (s,⃗a I m ) = A ⃗π,I m F (s,a ∅ ,⃗a I m ) = m X l=1 A ⃗π,i l F (s,⃗a I l−1 ,a i l )(9) Proof.The proof is pretty straightforward by considering the Lemma B.5. For any setI m , state s and joint action ⃗a I m , we have by definition A ⃗π,I m F (s,⃗a I m ) = n X j=1 1 V ⃗π j (s) A ⃗π,I m j (s,⃗a I m ) = n X j=1 1 V ⃗π j (s) m X l=1 A ⃗π,i l j (s,⃗a I l−1 ,⃗a i l ) = m X l=1 n X j=1 1 V ⃗π j (s) A ⃗π,i l j (s,⃗a I l−1 ,a i l ) = m X l=1 A ⃗π,i l F (s,⃗a I l−1 ,a i l ) B.4 Proof of Lemma 3.3 To prove Lemma 3.3, we first need to decompose the KL-penalty term: Lemma B.6. For any joint policies ⃗π and ⃗π ′ and state s, the following statement holds D KL (⃗π(.|s)|| ⃗π ′ (.|s)) = n X j=1 D KL (π j (.|s)|| π j (.|s)). 20 Proof. For any state s, we have D KL (⃗π(·|s)∥ ⃗π ′ (·|s)) = E ⃗a∼⃗π(.|s) [log⃗π(⃗a|s)− log⃗π ′ (⃗a|s)] = E ⃗a∼⃗π(.|s) log n Y j=1 π j (a j |s)− log N Y j=1 π ′ j (a j |s) = E ⃗a∼⃗π(.|s) n X j=1 logπ j (a j |s)− logπ ′ j (a j |s) = n X j=1 E a j ∼π j (.|s) logπ j (a j |s)− logπ ′ j (a j |s) = n X j=1 D KL π j (·|s)∥ π ′ j (·|s) Lemma 3.3. Let⃗πand⃗π ′ be two joint policies, andI n an order, the surrogate function can be decomposed into n summands: J (⃗π ′ )− J (⃗π)≥ n X m=1 L I m ⃗π (⃗π ′I m−1 ,π ′i m )− C· D max KL π i m , π ′i m .(12) Proof. The proof relies on Lemma 3.2 and Lemma B.6: J (⃗π ′ )− J (⃗π)≥L ⃗π (⃗π ′ )− C· D max KL (⃗π || ⃗π ′ )(47) ≥ E s∼d ⃗π ,⃗a∼⃗π ′ (.|s) n X j=1 A ⃗π j (s,⃗a) V ⃗π j (s) − C· D max KL (⃗π || ⃗π ′ )(48) ≥ E s∼d ⃗π ,⃗a∼⃗π ′ (.|s) n X j=1 1 V ⃗π j (s) n X m=1 A ⃗π,i m j (s,⃗a I m−1 ,a i m ) (49) − n X m=1 C· D max KL (π i m || π ′ i m )(50) ≥ n X m=1 E s ∼ d ⃗π , ⃗a I m−1 ∼⃗π I m−1 (.|s),a i m ∼π ′i m (.|s) n X j=1 1 V ⃗π j (s) A ⃗π,i m j (s,⃗a I m−1 ,a i m ) − C· D max KL (π i m || π ′ i m )(51) = n X m=1 L I m ⃗π (⃗π ′I m−1 ,π ′i m )− C· D max KL π i m , π ′ i m (52) B.5 Proof of Lemma 3.4 Let us recall the definition of Gâteaux derivative. Definition 3.4. (Gâteaux Derivative) Let⃗π,⃗π ′ be two joint policies andη >0 a positive number. Let us define the perturbed policiesπ i η =π i +η(π ′i − π i ), all together define the joint perturbed policy⃗π η . If the limit exists, we define the Gateaux derivative of a function f (⃗π) asD ⃗π ′ f (⃗π) = lim η→0 f (⃗π η )−f (⃗π) η . Lemma B.7. Let⃗πand⃗π ′ be two joint policies, then for any agentiand states,V ⃗π i (s) is Gâteaux differentiable and D ⃗π ′ V ⃗π i (s 0 ) = E s∼d ⃗π|s 0 ,⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) (53) 21 Proof.Let⃗π,⃗π ′ be two joint policies andη >0. For any agenti, we defined the perturbed policy π i η = π i + η(π ′i − π i ), which together define the perturbed joint policy ⃗π η . Let us consider the following quantity for a given state s 0 f (η) = V ⃗π η i (s 0 )− V ⃗π i (s 0 ) η . Using Lemma B.1, we have f (η) = 1 η E τ∼⃗π η " ∞ X t=0 γ t A ⃗π i (s t ,⃗a t )| s 0 # = 1 η ∞ X t=0 γ t E τ∼⃗π η A ⃗π i (s t ,⃗a t )| s 0 = 1 η ∞ X t=0 γ t X s P(s t = s|s 0 ,⃗π η )E ⃗a∼⃗π η (·|s) A ⃗π i (s,⃗a) 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 ⃗π η , we have E ⃗a∼⃗π η (·|s) A ⃗π i (s,⃗a) = (1− η)E ⃗a∼⃗π(·|s) A ⃗π i (s,⃗a) + ηE ⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) Lemma B.2 states that the first term is null. Therefore, we have E ⃗a∼⃗π η (·|s) A ⃗π i (s,⃗a) = ηE ⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) . Putting back into f (η) gives: f (η) = ∞ X t=0 γ t X s P(s t = s|s 0 )E ⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) = X s d ⃗π η (s|s 0 )E ⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) When η → 0, Lemma A.2 states that d ⃗π η converges to d ⃗π by continuity. Hence, we have D ⃗π ′ V ⃗π i (s 0 ) = lim η→0 f (η) = X s d ⃗π (s|s 0 )E ⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) = E s∼d ⃗π|s 0 ,⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) Lemma 3.4. Let⃗πbe a policy and⃗π ′ be another policy. The following statement holds: D ⃗π ′ J (⃗π) =L ⃗π (⃗π ′ ). Proof.Let⃗π,⃗π ′ be two joint policies andη >0. We defined the perturbed policy⃗π η = ⃗π + η(⃗π ′ − ⃗π). Let us consider the following quantity f (η) = J (⃗π η )− J (⃗π) η . 22 Then, we have f (η) = J (⃗π η )− J (⃗π) η = 1 η E s 0 ∼ρ 0 n X j=1 U α (ν + V ⃗π η j (s 0 ))− U α (ν + V ⃗π j (s 0 )) = X s 0 ρ 0 (s 0 ) n X j=1 U α (ν + V ⃗π η j (s 0 ))− U α (ν + V ⃗π j (s 0 )) η As the state space is finite, we can pass to the limit in the sum. lim η→0 f (η) = X s 0 ρ 0 (s 0 ) n X j=1 lim η→0 U α (ν + V ⃗π η j (s 0 ))− U α (ν + V ⃗π j (s 0 )) η We recognize the derivative of a composite function. AsU α is differentiable onR + and V ⃗π j (s 0 ) is Gateaux derivative, the compositeU α (ν+V ⃗π j (s 0 )) is also Gateaux differentiable and the following statement holds: D ⃗π ′ J (⃗π) = lim η→0 f (η) = X s 0 ρ 0 (s 0 ) n X j=1 U ′ α (ν + V ⃗π j (s 0 ))D ⃗π ′ V ⃗π j (s 0 ) Using Lemma B.7, we have D ⃗π ′ J (⃗π) = X s 0 ρ 0 (s 0 ) n X j=1 U ′ α (ν + V ⃗π j (s 0 ))D ⃗π ′ V ⃗π j (s 0 ) = E s 0 ∼ρ 0 n X j=1 1 V ⃗π j (s 0 ) E s∼d ⃗π|s 0 ,⃗a∼⃗π ′ (·|s) A ⃗π i (s,⃗a) . Recall we are using contextualized states, thus the initial states 0 is passed to any other state in a trajectory. Then, using the total expectation theorem, we have D ⃗π ′ J (⃗π) = E s∼d ⃗π ,⃗a∼⃗π ′ (·|s) n X j=1 1 V ⃗π j (s 0 ) A ⃗π i (s,⃗a) =L ⃗π (⃗π ′ ). B.6 Proof of Theorem 3.5 To prove Theorem 3.5, we need the following lemmas. Lemma B.8. For any subset I m , any joint policies ⃗π and ⃗π ′ E s∼d ⃗π ,⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m h A ⃗π,i m F (s,⃗a I m−1 ,a i m ) i = 0(54) Proof. By definition, we have E s∼d ⃗π ,⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m h A ⃗π,i m F (s,⃗a I m−1 ,a i m ) i (55) = E s∼d ⃗π ,⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m n X j=1 1 V ⃗π j (s) A ⃗π,i m j (s,⃗a I m−1 ,a i m ) (56) = n X j=1 E s∼d ⃗π ,⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m " 1 V ⃗π j (s) A ⃗π,i m j (s,⃗a I m−1 ,a i m ) # (57) = n X j=1 E s∼d ⃗π " 1 V ⃗π j (s) E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s h A ⃗π,i m j (s,⃗a I m−1 ,a i m ) i # . (58) 23 For any agent j, we have E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s h A ⃗π,i m j (s,⃗a I m−1 ,a i m ) i (59) = E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s h Q ⃗π,I m j (s, ⃗a I m−1 , a i m )− Q ⃗π,I m−1 j (s, ⃗a I m−1 ) i (60) = E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s h Q ⃗π,I m j (s, ⃗a I m−1 , a i m ) i − E ⃗a I m−1 ∼⃗π ′I m−1 |s h Q ⃗π,I m−1 j (s, ⃗a I m−1 ) i (61) The first term can be re-written as E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s h Q ⃗π,I m j (s, ⃗a I m−1 , a i m ) i (62) = E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s E ⃗a −I m ∼⃗π −I m Q ⃗π j (s, ⃗a I m−1 ,a i m , ⃗a −I m ) (63) = E ⃗a I m−1 ∼⃗π ′I m−1 |s E ⃗a −I m−1 ∼⃗π −I m−1 Q ⃗π j (s, ⃗a I m−1 , ⃗a −I m−1 ) (64) = E ⃗a I m−1 ∼⃗π ′I m−1 |s h Q ⃗π,I m−1 j (s,⃗a I m−1 ) i (65) Putting back into the former equation ends the demonstration: E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s h A ⃗π,i m j (s,⃗a I m−1 ,a i m ) i (66) = E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π i m |s h Q ⃗π,I m j (s, ⃗a I m−1 , a i m ) i − E ⃗a I m−1 ∼⃗π ′I m−1 |s h Q ⃗π,I m−1 j (s, ⃗a I m−1 ) i (67) = E ⃗a I m−1 ∼⃗π ′I m−1 |s h Q ⃗π,I m−1 j (s, ⃗a I m−1 ) i − E ⃗a I m−1 ∼⃗π ′I m−1 |s h Q ⃗π,I m−1 j (s, ⃗a I m−1 ) i (68) = 0(69) Theorem 3.5. 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 (⃗π k+1 )≥ J (⃗π k ), • The fair global objective converges: lim k→∞ J (⃗π k ) = J ∞ , •The set of joint policies’ limit points is non empty, each of which is a Nash equilibrium. Proof. We will prove the theorem in three folds. I. Monotonic Improvement Property For any k ∈ N and any permutation I n , suppose ⃗π k+1 is updated by Algorithm 1, i.e. π i m k+1 = arg max π i m L I m ⃗π i (⃗π I m−1 k+1 ,π i m )− C· D max KL π i m k , π i m (70) We want to bound the difference J (⃗π k+1 )− J (⃗π i ): J (⃗π k+1 )− J (⃗π i )≥ n X l=1 L I m ⃗π i (⃗π I m−1 k+1 ,π i m k+1 )− C· D max KL π i m k , π i m k+1 Asπ i m k+1 maximizes the surrogate function, the latter function gets lower evaluation for any other policy π ′i m . In particular, for π ′i m = π i m k , we have : L I m ⃗π i (⃗π I m−1 k+1 ,π i m k+1 )− C· D max KL π i m k , π i m k+1 ≥L I m ⃗π i (⃗π I m−1 k+1 ,π i m k )− C· D max KL π i m k , π i m k (71) ≥L I m ⃗π i (⃗π I m−1 k+1 ,π i m k )(72) 24 We then use the Lemma B.8: L I m ⃗π i (⃗π I m−1 k+1 ,π i m k ) = E s ∼ d ⃗π i , ⃗a I m−1 ∼⃗π I m−1 k+1 (.|s),a i m ∼π i m k (.|s) A ⃗π,i m s,⃗a I m−1 ,a i m (73) = 0.(74) Hence, it follows that J (⃗π k+1 )− J (⃗π i )≥ n X l=1 L I m ⃗π i (⃗π I m−1 k+1 ,π i m k+1 )− C· D max KL π i m k , π i m k+1 ≥ n X l=1 L I m ⃗π i (⃗π I m−1 k+1 ,π i m k ) ≥ 0. I. Convergence of the fair global objective First of all, the sequence (J(⃗π k )) k∈N converges as, by the Monotonic Improvement property, it is monotonically increasing and upper bounded byn· U α ν + r max 1−γ . Let us denote the limit by J ∞ . I. Nash Equilibrium of the limit points The following proof is adapted from Appendix C.3 of [31]. 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 Π i is bounded. Therefore, for any sequence of policies (⃗π i ), Bolzano-Weierstrass Theeorem states that we can extract a subsequence (⃗π k j ) j∈N that converges to an adherent point⃗π ∞ . By continuity ofJin⃗π (A.4.1), we have J (⃗π ∞ ) = J lim j→∞ ⃗π k j = lim j→∞ J (⃗π k j ) = J ∞ .(75) Definition B.1 (TR-Stationarity, [31]). A joint policy⃗π ◦ is a trust-region-stationary (TR-stationary) if, for every agent i, π i ◦ = arg max π i h E s∼d ⃗π ◦ ,a i ∼π i h A ⃗π ◦ ,i F (s,a i ) i − C ⃗π ◦ D max KL π i ◦ ,π i i ,(76) where C ⃗π ◦ = 4nL α (1−γ) 2 A 2 max + 4nA max γ ν α (1−γ) 2 , and A max = max j,s,⃗a |A ⃗π ◦ j (s,⃗a)|. The goal now is to establish the TR-stationarity of any limit point joint policy⃗π ∞ . Let E I 0:∞ n [·] denote the expected value operator under the random process (I 0:∞ n ). Let also A k = max j,s,⃗a |A ⃗π k j (s,⃗a)|, and C ⃗π k = 4nL α (1−γ) 2 A 2 k + 4nA k γ ν α (1−γ) 2 . We have 0 = lim k→∞ E I 0:∞ n [J (⃗π k+1 )− J (⃗π k )] ≥ lim k→∞ E I 0:∞ n [L ⃗π k (⃗π k+1 )− C k D max KL (⃗π k ,⃗π k+1 )] by Lemma 3.1 ≥ lim k→∞ E I 0:∞ n h L i k 1 ⃗π k π i k 1 k+1 − C k D max KL π i k 1 k ,π i k 1 k+1 i , by Lemma 3.3 and removing the all the summands excepti k 1 (because the summands are all positive). Now, we consider an arbitrary limit point⃗π ∞ from the adherent set, and a subsequence (⃗π k j ) ∞ j=0 that converges to ⃗π ∞ . On one hand, we have from above 0≥ lim j→∞ E I 0:∞ n L i k j 1 ⃗π k j π i k j 1 k j +1 − C k j D max KL π i k j 1 k j ,π i k j 1 k j +1 .(77) 25 On the other hand, let denote byp i the probability to havei k j =iunder the assumption that every permutation has strictly positive probability to happen. As the expectation is taken of positive random variables, we also have lim j→∞ E I 0:∞ n L i k j 1 ⃗π k j π i k j 1 k j +1 − C k j D max KL π i k j 1 k j ,π i k j 1 k j +1 ≥ p i lim j→∞ max π i h L i ⃗π k j π i − C k j D max KL π i k j ,π i i ≥ p i max π i L i ⃗π ∞ π i − C ⃗π ∞ D max KL ⃗π i ∞ ,π i ≥ 0 by Lemma B.8. L i ⃗π k j (π i ) converges asL i ⃗π (π i ) is continuous with respect to⃗π(by Definition 3.3 and Lemma A.5).C k j converges as it is continuous with respect to⃗π(Corollary A.4.1).D max KL convergence follows from from continuity ofD KL with Assumption 1 and continuity ofmaxover finite state space. Therefore, we have max π i L i ⃗π ∞ (π i )− C ⃗π ∞ D max KL π i ∞ ,π i = 0,(78) which proves ⃗π ∞ is TR-stationary. Step 2 (dropping the penalty term). In this second step, the goal is to prove that a TR-stationary joint policy ̄π satisfies π i ∞ = arg max π i E a i ∼π i h A ⃗π ∞ ,i F (s,a i ) i ,(79) for every state s∈S. We will prove the statement by contradiction. Hence, suppose that there exists a states 0 and a policy ˆπ i such that E a i ∼ˆπ i h A ⃗π ∞ ,i F (s 0 ,a i ) i > E a i ∼π i ∞ h A ⃗π ∞ ,i F (s 0 ,a i ) i .(80) Parameterize the policy π i (·| s 0 ) as a probability vector: π i (·| s 0 ) = x i 1 ,...,x i d i −1 , 1− d i −1 X j=1 x i j ,(81) wherex i j ensures a valid distribution andd i =|A i |. The expected fair advantage in Equation 79 can be rewritten as: E a i ∼π i h A ⃗π ∞ ,i F (s 0 ,a i ) i = d i −1 X j=1 x i j · A ⃗π ∞ ,i F (s 0 ,a i j ) + 1− d i −1 X h=1 x i h A ⃗π ∞ ,i F (s 0 ,a i d i )(82) = d i −1 X j=1 x i j h A ⃗π ∞ ,i F (s 0 ,a i j )− A ⃗π ∞ ,i F (s 0 ,a i d i ) i + A ⃗π ∞ ,i F (s 0 ,a i d i ). (83) Because this expectation is an affine function ofx i , its gradients and directional derivatives are constant. The existence ofˆπ i (·| s 0 ) satisfying Inequality 80 guarantees a strictly positive directional derivative from ̄π i (·| s 0 ) toward ˆπ i (·| s 0 ). 26 Additionally, the KL divergence gradient vanishes at the reference policy π i ∞ : ∂D KL (π i ∞ (·| s 0 ),π i (·| s 0 )) ∂x i j = ∂ ∂x i j (π i ∞ (·| s 0 )) T logπ i ∞ (·| s 0 )− logπ i (·| s 0 ) (84) =− ∂ ∂x i j (π i ∞ ) T logπ i (omitting state s 0 for brevity) (85) =− ∂ ∂x i j d i −1 X k=1 π i ∞,k logx i k − ∂ ∂x i j π i ∞,d i log 1− d i −1 X k=1 x i k (86) =− π i ∞,j x i j + π i ∞,d i 1− P d i −1 k=1 x i k (87) =− π i ∞,j π i j + π i ∞,d i π i d i = 0, when π i = π i ∞ .(88) Consequently, when evaluated at π i (·| s 0 ) = π i ∞ (·| s 0 ), the full penalized objective: d ⃗π ∞ (s 0 ) E a i ∼π i h A ⃗π ∞ ,i F (s 0 ,a i ) i − C ⃗π ∞ D KL π i ∞ (·| s 0 ),π i (·| s 0 ) (89) has a strictly positive directional derivative towardˆπ i (· | s 0 ). This implies we can find a local policy ̃π i (·| s 0 ) on the path toward ˆπ i (·| s 0 ) that strictly improves the objective: d ⃗π ∞ (s 0 ) E a i ∼ ̃π i h A ⃗π ∞ ,i F (s 0 ,a i ) i − C ⃗π ∞ D KL π i ∞ (·| s 0 ), ̃π i (·| s 0 ) > 0.(90) Now, construct a global policyπ i ∗ such thatπ i ∗ (·| s 0 ) = ̃π i (·| s 0 ) andπ i ∗ (·| s) =π i ∞ (·| s) for alls ̸=s 0 . For unperturbed states (s ̸=s 0 ), both the advantage and KL divergence evaluate to zero: d ⃗π ∞ (s) E a i ∼π i ∗ h A ⃗π ∞ ,i F (s,a i ) i = d ⃗π ∞ (s) E a i ∼π i ∞ h A ⃗π ∞ ,i F (s,a i ) i = 0, D KL π i ∞ (·| s),π i ∗ (·| s) = 0.(91) Applying this to the full objective yields: L i ⃗π ∞ (π i ∗ )− C ⃗π ∞ D max KL (π i ∞ ,π i ∗ ) = d ⃗π ∞ (s 0 ) E a i ∼ ̃π i h A ⃗π ∞ ,i F (s 0 ,a i ) i − C ⃗π ∞ D KL π i ∞ (·| s 0 ), ̃π i (·| s 0 ) (92) > 0(93) =L i ⃗π ∞ (π i ∞ )− C ⃗π ∞ D max KL (π i ∞ ,π i ∞ ).(94) This strict improvement directly contradicts the assumption of TR-stationarity for ̄π, thereby proving the claim. Step 3 (optimality). Now, for a fixed joint policy ⃗π −i ∞ of other agents, π i ∞ satisfies π i ∞ = arg max π i E a i ∼π i A ⃗π ∞ ,i (s,a i ) .(95) Lemma 3.1 gives an upper bound of the performance difference. Then, for a given TR- stationary point ⃗π ∞ and any other policy π i for agent i, we have J (π i ,⃗π −i ∞ )− J (⃗π ∞ )≤L ⃗π ∞ (π i ,⃗π −i ∞ ), which by definition of L ⃗π ∞ is equivalent to J (π i ,⃗π −i ∞ )− J (⃗π ∞ )≤ E s∼d ⃗π ∞ , a i ∼π i (·|s),⃗a −i ∼⃗π −i ∞ (·|s) h A ⃗π ∞ F (s,a i ,⃗a −i ) i (96) = E s∼d ⃗π ∞ h E a i ∼π i (·|s) h A ⃗π ∞ ,i F (s,a i ) i (97) ≤ E s∼d ⃗π ∞ h E a i ∼π i ∞ (·|s) h A ⃗π ∞ ,i F (s,a i ) i (by definition of π i ∞ ) (98) = 0(by Lemma B.8)(99) 27 Thus, we have J (π i ,⃗π −i ∞ )≤ J (⃗π ∞ ).(100) As this statement holds for any arbitrary agenti, this proves⃗π ∞ is a Nash equilibrium. C Pratical Algorithms C.1 α-fair HATRPO The derivation ofα-fair HATRPO relies on an estimatorˆg i m k of the gradient of the local objective E s ∼ d ⃗ θ k , ⃗a I m−1 ∼ ⃗ θ I m−1 k+1 (.|s),a i m ∼θ i m (.|s) h A ⃗ θ k ,i m F s,⃗a I m−1 ,a i m i . In this form, the local objective is hard to differentiate. Thankfully, we can re-write this in a more tractable expression. Lemma C.1. Let⃗πbe a joint policy,⃗π ′I m−1 be some other joint policy of agentsI m−1 and π ′i m be some other policy of agent i m . Then, the local objective can be rewritten as E ⃗a I m−1 ∼⃗π ′I m−1 ,a i m ∼π ′i m [A ⃗π,i m F (s,⃗a I m−1 ,a i m )] = E ⃗a∼⃗π π ′i m (a i m |s) π i m (a i m |s) − 1 ⃗π ′I m−1 (⃗a I m−1 |s) ⃗π I m−1 (⃗a I m−1 |s) A ⃗π F (s,⃗a) . (101) Proof. See [31], 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 3.2), the proof holds for our fair advantage function. Let us introduceM I m F = ⃗π ′I m−1 (⃗a I m−1 |s) ⃗π I m−1 (⃗a I m−1 |s) A ⃗ θ k F (s,⃗a). It follows that the derivation of the gradient estimator for HATRPO holds forα-fair HATRPO by replacing the multi-agent advantage function with our fair advantage function: ∇ θ i m E s∼d ⃗ θ k ,⃗a∼ ⃗ θ k π i m θ i m (a i m |s) π i m θ i m k (a i m |s) − 1 M I m F (s,⃗a) (102) = E s∼d ⃗ θ k ,a∼ ⃗ θ k π i m θ i m (a i m |s) π i m θ i m k (a i m |s) ∇ θ i m logπ i m θ i m (a i m |s)M i 1:m F (s,⃗a) . (103) See Appendix D.2 of [31] for more details. 28 Algorithm 2 α-FHATRPO 1:Input: Stepsizeω, batch sizeB, number of: agentsn, episodesK, steps per episode T, constantν, fairness levelα, possible steps in line searchL, line search acceptance threshold ι. 2:Initialize: Actor networksθ i 0 , ∀i ∈ N , individual V-value networksφ i 0 , ∀i ∈ N , Replay buffer B 3: for k = 0, 1,...,K− 1 do 4: Collect a set of trajectories by running the joint policy π θ k = (π 1 θ 1 k ,...,π n θ n k ). 5: Sample a random minibatch of B transitions from B. 6: Compute individual state value function ˆ V j (s) based on individual critics network. 7: Compute individual advantage function ˆ A j (s,⃗a) with GAE. 8: Compute fair advantage function ˆ A F (s,⃗a) with α, ν, ˆ A j (s,⃗a) and ˆ V j (s). 9: Draw a random permutation of agents I n . 10: Set M i 1 F (s,⃗a) = ˆ A F (s,⃗a). 11: for agent i m = i 1 ,...,i n do 12:Estimate the gradient of the agent’s maximisation objective ˆ g i m k = 1 B B X b=1 T X t=1 ∇ θ i m k logπ i m θ i m k (a i m t | o i m t )M i 1:m F (s t ,a t ). Use the conjugate gradient algorithm to compute the update direction ˆ x i m k ≈ ( ˆ H i m k ) −1 ˆ g i m k , where ˆ H i m k is the Hessian of the average KL-divergence 1 BT B X b=1 T X t=1 D KL π i m θ i m k (·| o i m t ),π i m θ i m (·| o i m t ) . 13:Estimate the maximal step size allowing for meeting the KL-constraint ˆ β i m k ≈ s 2δ ( ˆ x i m k ) T ˆ H i m k ˆ x i m k . 14:Update agent i m ’s policy by θ i m k+1 = θ i m k + ω j ˆ β i m k ˆ x i m k , wherej ∈0,1,...,Lis the smallest suchjwhich improves the sample loss by at least ια j ˆ β i m k ˆ x i m k · ˆ g i m k , found by the backtracking line search. 15:Compute M i 1:m+1 F (s,⃗a) = π i m θ i m k+1 (a i m |o i m ) π i m θ i m k (a i m |o i m ) M i 1:m F (s t ,a t ). //Unless m = n. 16: end for 17: Update V-value networks by following formula: φ i k+1 = arg min φ i 1 BT B X b=1 T X t=0 V φ i (s t )− ˆ R i t 2 , ∀i∈N. 18: end for 29 C.2 α-fair HAPPO Algorithm 3 α-FHAPPO 1:Input: Clippingε, batch sizeB, number of: agentsn, episodesK, steps per episodeT. 2:Initialize: Actor networksθ i 0 , ∀i ∈ N, individual V-value networksφ i 0 , ∀i ∈ N, Replay buffer B 3: for k = 0, 1,...,K− 1 do 4: Collect a set of trajectories by running the joint policy π θ k = (π 1 θ 1 k ,...,π n θ n k ). 5: Push transitions (o i t ,a i t ,o i t+1 ,r t ),∀i∈N,t∈ T into B. 6: Sample a random minibatch of B transitions from B. 7: Compute individual state value function ˆ V j (s) based on individual critics network. 8: Compute individual advantage function ˆ A j (s,⃗a) with GAE. 9: Compute fair advantage function ˆ A F (s,⃗a) with α, ν, ˆ A j (s,⃗a) and ˆ V j (s). 10: Draw a random permutation of agents i 1:n . 11: Set M i 1 F (s,⃗a) = ˆ A F (s,⃗a). 12: for agent i m = i 1 ,...,i n do 13:Update actor i m with θ i m k+1 , the argmax of the PPO-Clip objective 1 BT B X b=1 T X t=0 min π i m θ i m (a i m t | o i m t ) π i m θ i m k (a i m t | o i m t ) M i 1:m F (s t ,a t ), clip π i m θ i m (a i m t | o i m t ) π i m θ i m k (a i m t | o i m t ) , 1± ε M i 1:m F (s t ,a t ) . 14:Compute M i 1:m+1 F (s,⃗a) = π i m θ i m k+1 (a i m |o i m ) π i m θ i m k (a i m |o i m ) M i 1:m F (s,⃗a). //Unless m = n. 15: end for 16: Update V-value networks by following formula: φ i k+1 = arg min φ i 1 BT B X b=1 T X t=0 V φ i (s t )− ˆ R i t 2 17: end for D Experiments D.1 Environments’ parameters In this work, we based our implementation on the environment provided by SocialJax. Table 1: CleanUp Environment Parameters ParameterValue / Description Grid Size28× 19 Trajectory Length500 steps Max Regrowth Apple Rate0.05 Maximum Level of Pollution40% Delay Start of Dirt Spawning 50 Dirt Spawn Probability0.5 30 Table 2: Harvest Environment Parameters ParameterValue Grid Size22× 16 Trajectory Length500 Regrowth Apple Rate Proportional to density D.2 Hyper-parameters of the different algorithms We implement HATRPO and HAPPO from scratch using the pseudo code pro- vided by HATRL [31]. We recover the code of Fair MAPPO from FairMARL[28] (https://github.com/AkuBrains/altruistic-fair-MARL/). In this work, actor and critic net- works 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. ParameterDefault Value Exponential Decay (β 1 )0.9 Exponential Decay (β 2 )0.999 Epsilon (ε)10 −8 Weight Decay (λ)0 Table 4: Hyperparameters HATRPO’s algorithms (Harvest). ParameterHATRPO 0.5-FHATRPO 1-FHATRPO 1.5-FHATRPO ν/0.10.10.1 KL (δ)0.010.010.010.01 critic learning rate0.00010.00010.00010.0001 accept ratio0.10.10.10.1 CG iteration15151515 Table 5: Hyperparameters HAPPO’s algorithms (Harvest). ParameterHAPPO 0.5-FHAPPO 1-FHAPPO 1.5-FHAPPO ν/0.10.10.1 Clipping ε0.050.050.050.05 actor learning rate0.00030.00030.00050.0005 critic learning rate0.00010.00010.00010.0001 Minibatch size1000100010001000 Table 6: Hyperparameters HATRPO’s algorithms (CleanUp). ParameterHATRPO 0.5-FHATRPO 1-FHATRPO 1.5-FHATRPO ν/0.10.10.1 KL (δ)0.0050.0050.0050.0005 critic learning rate0.00010.00010.00010.0001 accept ratio0.10.10.10.1 CG iteration10101015 31 Table 7: Hyperparameters HAPPO’s algorithms (CleanUp). ParameterHAPPO 0.5-FHAPPO 1-FHAPPO 1.5-FHAPPO ν/0.10.10.1 Clipping ε0.10.20.10.1 actor learning rate0.00050.00050.00050.0005 critic learning rate0.00010.00010.00010.0001 Minibatch size1000100010001000 Table 8: Hyperparameters for FMAPPO algorithm. ParameterCleanUp Harvest altruism level (α)11 Clipping ε0.10.1 actor learning rate0.00050.0005 critic learning rate0.00050.0005 Minibatch size12501000 D.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 3 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 4 summarizes these additional results. The TZA values appear to decrease and approach zero for all algorithms except HAPPO and 0.5-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. 32 00.20.40.60.81 ·10 8 0 200 400 timestep Zap Total zap HA- TRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 200 400 600 timestep Zap Total zap consumed HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 200 400 600 timestep Zap Total zap con- sumed forα= 1 FMAPPO FHATRPO FHAPPO 00.20.40.60.81 ·10 8 100 200 300 400 500 600 timestep Clean Total Clean actions HATRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 200 400 600 800 timestep Clean Total Clean actions HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 200 400 600 800 timestep Clean Total Clean ac- tions forα= 1 FMAPPO FHATRPO FHAPPO Figure 3: Additional 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. 00.20.40.60.81 ·10 8 0 100 200 300 400 timestep Zap Total zap actions HATRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 200 400 timestep Zap Total zap actions HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 0 100 200 300 400 500 timestep Zap Total zap ac- tions forα= 1 FMAPPO FHATRPO FHAPPO 00.20.40.60.81 ·10 8 350 400 450 500 timestep Time to Depletion Time to Depletion HATRPO/FHATRPO HATRPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 300 400 500 timestep Time to Depletion Time to Depletion HAPPO/FHAPPO HAPPO α=0.5 α=1 α=1.5 00.20.40.60.81 ·10 8 350 400 450 500 timestep Time to Depletion Time to Deple- tion forα= 1 FMAPPO FHATRPO FHAPPO Figure 4: Additional 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. 33