Technical Summary: $\alpha$-fair Heterogeneous Agent Reinforcement Learning

Problem Statement

In Multi-Agent Reinforcement Learning (MARL), cooperation is traditionally optimized through utilitarian objectives that maximize the sum of all agents' utilities. While efficient, this approach often neglects reward distribution, leading to inequitable "leader-follower" dynamics where a subset of agents is marginalized. Existing attempts to integrate fairness into MARL generally fall into three categories: reward shaping (e.g., inequity aversion), fairness constraints, and social welfare objectives. However, these methods suffer from critical limitations:

1. Stationarity Issues: Reward shaping methods often rely on history-dependent rewards, breaking the stationary property of Markov Games.
2. Lack of Theoretical Guarantees: Popular algorithms like Independent PPO (IPPO) or Multi-Agent PPO (MAPPO), even when adapted for fairness, lack the rigorous theoretical convergence guarantees found in single-agent Trust Region Learning (TRL).
3. Generalization and Interpretability: Constraint-based methods are often domain-specific, while social welfare objectives (like $\alpha$-fairness) often rely on extrapolated PPO objectives without theoretical safeguards or rely on idealized assumptions (e.g., concavity).

There exists a gap between equitable objective functions and theoretically safe learning frameworks. This paper aims to bridge this gap by introducing a framework that ensures monotonic improvement and convergence toward Nash Equilibria while optimizing for $\alpha$-fairness.

Methodology

Theoretical Framework: $\alpha$-fair HATRL

The authors propose a novel framework combining $\alpha$-fairness with Heterogeneous-Agent Trust Region Learning (HATRL).

1. Global Fair Objective:
   The framework defines a global objective function $J(\vec{\pi})$ for a fully-cooperative setting:
   $$J(\vec{\pi}) = \mathbb{E}_{s_0 \sim \rho_0} \left[ \sum_{i=1}^n U_\alpha(\nu + V_i^{\vec{\pi}}(s_0)) \right]$$
   where $U_\alpha$ is the $\alpha$-fair utility function, $\nu$ is a positive constant ensuring positivity, and $V_i^{\vec{\pi}}$ is the value function for agent $i$.

   • As $\alpha \to 0$, the objective approaches the utilitarian sum.
   • As $\alpha \to +\infty$, it approaches the Rawlsian welfare (max-min) function.
   • At $\alpha = 1$, it corresponds to proportional fairness.

2. Fair Advantage Function:
   To adapt HATRL, the authors introduce a fair advantage function $A_F^{\vec{\pi}}(s, \vec{a})$. Unlike standard multi-agent advantage functions, this is a weighted sum of individual agents' advantage functions, where weights are dynamically determined by the inverse of the agents' expected returns ($1/V_j^{\vec{\pi}}(s)$). This weighting ensures that agents with higher expected returns contribute less to the gradient update, allowing space for lower-performing agents to improve.

3. Sequential Update and Surrogate Function:
   Building on HATRL, the authors derive a surrogate function $L_{\vec{\pi}}(\vec{\pi}')$ that serves as a lower bound for the improvement in the global fair objective. They prove that the difference $J(\vec{\pi}') - J(\vec{\pi})$ is bounded by this surrogate function minus a KL-divergence penalty term.
   Crucially, they demonstrate that the surrogate function can be decomposed into $n$ ordered summands. This allows for a sequential update scheme where agents update their policies one by one (in a random permutation), maximizing their local contribution to the global fair objective while respecting a trust region constraint.

4. Theoretical Guarantees:
   The paper provides proofs for:

   • Monotonic Improvement: The global fair objective $J(\vec{\pi})$ is guaranteed to increase (or stay equal) at each iteration.
   • Convergence: The sequence of joint policies converges to a limit point.
   • Nash Equilibrium: The set of limit points is non-empty, and each limit point constitutes a Nash Equilibrium for the fully-cooperative game.

Practical Algorithms

To implement this framework in high-dimensional spaces, the authors develop two deep reinforcement learning algorithms:

1. $\alpha$-fair HATRPO: An extension of Heterogeneous-Agent Trust Region Policy Optimization. It replaces the standard multi-agent advantage with the fair advantage function and solves the constrained optimization problem using a KL-constraint and conjugate gradient updates.
2. $\alpha$-fair HAPPO: An extension of Heterogeneous-Agent PPO. It uses a first-order approximation with a clipping mechanism to avoid computing the Hessian, making it more computationally efficient while maintaining the sequential update structure.

Key Contributions

1. Theoretical Bridge: The paper introduces a theoretically grounded framework that integrates $\alpha$-fairness into Heterogeneous-Agent Trust Region Learning, providing mathematical safety (monotonic improvement and convergence guarantees) for learning pro-social behaviors.
2. Novel Surrogate Function: The definition of a fair advantage function that dynamically weights agent utilities based on expected returns, enabling the transition from utilitarian efficiency to $\alpha$-fairness welfare.
3. Algorithm Development: The proposal of two practical algorithms, $\alpha$-fair HATRPO and $\alpha$-fair HAPPO, which extend the theoretical framework to parametric policy settings.
4. Empirical Validation: Demonstration that these algorithms achieve higher social outcomes (lower Gini indices) while maintaining or exceeding utilitarian efficiency compared to baselines in sequential social dilemmas.

Experimental Results

The algorithms were evaluated on two Sequential Social Dilemma (SSD) environments from the SocialJax suite: CleanUp and CommonHarvest.

• Baselines: The proposed methods were compared against standard HATRPO/HAPPO (utilitarian) and FMAPPO (a PPO-based method using proportional fairness without theoretical guarantees).
• Metrics: Performance was measured by Total Apples Consumed (TAC) for efficiency and the Gini Index for fairness.
• Findings:
  • Fairness: Increasing the parameter $\alpha$ generally led to fairer outcomes (lower Gini indices). The proposed $\alpha$-fair algorithms achieved significantly lower Gini indices than the utilitarian baselines.
  • Efficiency: In the CommonHarvest environment, $\alpha$-fair HATRPO and HAPPO performed slightly better than utilitarian baselines in terms of TAC while achieving better fairness. In CleanUp, the efficiency advantage was minimal, and FMAPPO sometimes outperformed the proposed methods in pure efficiency, though the proposed methods still achieved socially superior results (lower Gini).
  • Comparison with FMAPPO: While FMAPPO performed well, the proposed methods offered a theoretically safe alternative with comparable or better fairness outcomes.

Significance and Limitations

Significance:
The paper claims to establish a "mathematically safe foundation" for training agents to adopt sustainable, pro-social behaviors. By ensuring monotonic improvement and convergence to Nash Equilibria, the framework addresses the lack of theoretical guarantees in existing fair MARL approaches. It successfully fills the gap between equitable objective functions and safe learning frameworks.

Limitations:
The authors acknowledge several constraints:

1. Hyperparameter Sensitivity: High values of $\alpha$ ($\alpha > 1$) can lead to performance degradation and training instability. This is attributed to the fair advantage function diminishing the weights of high-performing agents, making the global objective overly sensitive to "worst learners" who may get stuck in local optima.
2. Theoretical Constraints: The framework relies on the assumption of positive, bounded rewards, which limits its applicability to certain environments.
3. Observability: The algorithms require fully observable states. In real-world scenarios with partial observability, approximations (e.g., using RNNs) would be necessary, but these would lack the current theoretical guarantees.

The paper concludes by suggesting future work on mechanisms to enhance exploration (e.g., entropy normalization) or adaptive constraints to stabilize learning when $\alpha$ is high.