Source-linked AI summary
FairTest: Search-Based Fairness Testing for Multi-Agent Reinforcement Learning Systems
Xiaotong Wang, Xuan Xie
TL;DR
MARL training seeks high team return, but that does not ensure fair reward allocation, and fairness testing for MARL remains limited. FairTest searches policy executions using fairness and uncertainty signals to guide candidate selection and test prioritization. Across the evaluated environments and algorithms, it detects more fairness failures than every baseline with statistical significance.
Problem
MARL’s team-return objective does not ensure fair reward allocation, and few existing methods test MARL for fairness.
Source: §1 · pp. 1–2Method
FairTest uses genetic search to generate candidate joint episodes, scores them by measured and predicted fairness and policy uncertainty, and prioritizes candidates by predicted fairness and uncertainty.
Source: §1 · p. 2, §3 · p. 4, §3.1 · p. 5Results
Across all environment-algorithm configurations, FairTest detects more fairness failures than every baseline, with statistical significance.
Source: §1 · p. 2Takeaways & Limitations
The experiments demonstrate fairness testing of MARL policies across three environments and two algorithms under the evaluated settings.
Source: §1 · p. 2The evaluation covers only three environments and two value-based MARL algorithms, so findings may not transfer to other systems.
Source: §5 · p. 22
Abstract
from arXiv · showhide
Multi-agent Reinforcement Learning (MARL) trains a team of agents that share one environment and learn their policies together. Training maximizes the team return, and a high return does not imply that the rewards are shared fairly among the agents in every episode. Testing is an established way to discover the failures of deep reinforcement learning, yet few methods address the fairness of MARL. In this work, we propose FairTest, a search-based testing approach that seeks the unfair executions of a MARL policy. The design combines search guidance with test prioritization. The guidance scores each candidate with three fitness functions. One measures the fairness of the runs already performed, another predicts the fairness from abstract states and fairness features, and the third reads the decision uncertainty from the policy. Crossover and mutation derive further candidates from the observed executions. The prioritization ranks the candidates by the predicted fairness and the decision uncertainty, so that the runs reach the candidates where failures are expected. FairTest is evaluated on three environments and two MARL algorithms, and four baselines are given the same budget. It detects the most fairness failures compared to three baselines with statistical significance and large effect sizes. The failure count exceeds that of the strongest baseline by 221% on average and coverage improves by an average of 23%.
1 Introduction
MARL training maximizes team reward, but that objective does not ensure rewards are fairly distributed among agents. FairTest addresses the limited availability of fairness testing for MARL with search-guided candidate generation and prioritization, and detects more fairness failures than the evaluated baselines.
1 Introduction
- MARL’s team-return objective does not ensure an even reward distribution, and an idle service robot can waste capacity and lower service quality.Fairness is therefore presented as a practical requirement for MARL policies.Source: §1 · p. 1
- Existing fairness methods focus on training, while prior deep-RL testing targets single agents and MASTest targets team functionality rather than fairness.The paper identifies detecting unfair executions as a largely untouched problem.Source: §1 · pp. 1–2
- FairTest searches candidate executions using measured and predicted fairness plus policy decision uncertainty, then prioritizes candidates by predicted fairness and uncertainty.Crossover and mutation create variants of observed executions; a run is recorded as a failure when its observed fairness falls below a threshold.Source: §1 · p. 2
- Across all environment-algorithm configurations, FairTest detects more fairness failures than every baseline, with statistical significance.The comparison covers three environments and two MARL algorithms; improvement over the strongest baseline ranges from 43% to 412% across the reported settings.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish the single-agent and team decision settings, then define reward fairness and the threshold used to identify a fairness failure.
2 Preliminaries
- The preliminaries introduce the reinforcement-learning model, extend it to MARL, and define fairness, fairness failure, and the distinction between bias and unfairness.The fairness measure is Jain’s Fairness Index (JFI).Source: §2 · pp. 2–3
2.1 Reinforcement Learning
- An MDP models an agent’s states, actions, transitions, rewards, and policy; the policy selects an action at each state.An episode ends at a terminal state or when the time limit is reached.Source: §2.1 · p. 3
2.2 Multi-Agent Reinforcement Learning
- MARL extends the single-agent setting to agents sharing an environment, whose policies and outcomes remain coupled through team actions and individual rewards.Executing the joint policy from an initial joint state yields a joint episode, the object analyzed by the approach.Source: §2.2 · p. 3
2.3 Fairness in MARL
- JFI measures how evenly agents’ episode rewards are distributed, with 1 representing equal rewards and 1/N representing one agent receiving the whole reward.The paper adopts the outcome-based meaning of unfairness for unequal reward allocation among agents.Source: §2.3 · p. 4
- A fairness failure occurs when an episode’s JFI is at or below the threshold θ.Source: §2.3 · p. 4
3 Methodology
FairTest searches trained MARL policies for unfair executions by generating candidate episodes, scoring and prioritizing them against fairness objectives, and confirming failures with an oracle. Its methodology uses a learned fairness predictor, Pareto-based prioritization, crossover and mutation, and MOSA to select candidates that pursue uncovered fitness goals.
3.1 Reformulation as a Search Problem
- FairTest searches joint episodes to minimize the fairness index, predicted probability of fairness, and policy decision uncertainty, under a budget of 18,000 episodes per run.The setup uses random policy executions to form the initial population, then crossover and mutation to generate offspring; MOSA-based selection chooses survivors.Source: §3.1 · p. 5
3.2 Overview of the Approach
- Each search round builds candidates through random executions, evaluates and selects an initial population, evolves offspring, and collects oracle-confirmed failures until the testing budget is spent.The population and offspring are evaluated on the three fitness functions, and fairness failures are gathered in a failure pool throughout the search.Source: §3.2 · p. 5, §3.3 · p. 7
3.3 Fitness Functions
- The three fitness functions target reward inequality, predicted unfairness, and uncertain policy decisions that small perturbations may change.Jain’s Fairness Index [27] identifies failures below threshold θ; the predictor scores candidates before execution, while DeepGini uses recorded Q-values to measure decision uncertainty without additional execution.Source: §3.3 · pp. 7–8
3.4 Fairness Predictor
- A random forest fairness predictor combines Q-value-based abstract states with reward-derived features to estimate whether an episode is fair.Training episodes are labeled using the fairness threshold; the features include individual accumulated rewards and reward shares, alongside team-level statistics of reward distribution.Source: §3.4 · pp. 9–10
3.5 Pareto-based Test-Case Prioritization
- Prioritization filters for uncertain candidates, retains Pareto-optimal trade-offs between predicted unfairness and uncertainty, then uses crowding distance to reach the target size.Failures are determined independently of population selection: only executed episodes below the fairness threshold count, and they are recorded even if prioritization discards them.Source: §3.5 · p. 11
3.6 Search Operators
- Crossover joins two episodes at a step where their teams share the same joint abstract state, recombining their prefixes and suffixes into two offspring.The first parent is selected by tournament selection, preserving a chance for weaker episodes to contribute to the population.Source: §3.6 · p. 12
- Crossover offspring are truncated to the episode limit and scored using predicted fairness and decision uncertainty from their parents, but potentially invalid trajectories are not executed until search ends.Matching on abstract states increases offspring validity, while final validity is confirmed after search termination.Source: §3.6 · p. 12
- Mutation perturbs only the tested agents at a randomly chosen step, then re-executes the joint policy so the team can respond and produce a new reward allocation.The perturbation scales positions and velocities by independent uniform factors, clips them to environment bounds, and replaces the transitions after the mutation point.Source: §3.6 · pp. 12–13
- MOSA selects the next population by minimizing three fitness functions, prioritizing uncovered goals and ranking candidates by preference, non-dominated fronts, and crowding distance.Evaluated episodes with fairness index at or below threshold θ enter the failure pool.Source: §3.6 · p. 13
4 Experimental Evaluation
FairTest was evaluated against four baselines on three MARL environments and two algorithms under a shared testing budget. It found more fairness failures in all six configurations; further analyses show that performance depends on the retained-budget ratio and benefits from fairness-aware guidance and Pareto prioritization.
4.1 Experimental Setup
- The evaluation covered MPE, LBF, and Predator-Prey with IQL and QMIX, comparing FairTest with four baselines under 18,000 episodes per run.Each method was evaluated over 10 independent runs; the fairness-failure thresholds were 0.80 for MPE, 0.67 for LBF, and 0.80 for Predator-Prey.Source: §4.1 · pp. 13, 15
4.2.1 RQ1. How does our method perform compared to existing testing approaches?
- FairTest detected more fairness failures than every baseline in all six configurations, with every pairwise comparison highly significant (p<0.001, A12=1.000).The comparison used 10 runs; Table 1 reports mean failure counts and standard deviations.Source: §4.2.1 · p. 15, Table 1 · p. 16
- FairTest had higher failure coverage than Random, MASTest, and STARLA in every configuration, but GMT covered more cells in three configurations despite finding far fewer failures.On Predator-Prey, FairTest coverage was 0.889 for IQL and 0.821 for QMIX, versus 0.416 and 0.338 for GMT.Source: §4.2.1 · p. 16, Table 3 · p. 17
- The retained-budget ratio had environment-specific effects: fewer retained candidates found more failures on MPE, more did so on LBF, and Predator-Prey was nearly flat.The study recommends the default 20% setting.Source: Figure 4 · p. 18, §4.2.2 · p. 19
- Adding fairness features raised predictor AUC-ROC from 0.882 to 0.997 for IQL and from 0.852 to 0.955 for QMIX.The features summarize individual-agent rewards and reward-distribution statistics; the abstract states alone contain no reward information.Source: §4.2.3 · p. 19
- Every enabled fitness function found more failures than unguided search on both policies; the strongest single signal was predicted fairness for IQL and direct fairness for QMIX.Using all three functions yielded 1,046.1 failures on IQL and 469.1 on QMIX, slightly above each policy’s best single-function result.Source: §4.2.3 · pp. 20–21
- Pareto prioritization produced about four times as many failures and higher coverage than the unprioritized search at the same episode budget.On Predator-Prey, failure counts were 4,523.4 versus 1,046.1 for IQL and 1,930.5 versus 469.1 for QMIX; coverage rose from 0.495 to 0.889 and from 0.379 to 0.821, respectively.Source: §4.2.3 · p. 21, Figure 7 · p. 21, Table 5 · p. 22
5 Threats to Validity
The paper discusses internal, external, and construct threats to validity, including failure verification, limited experimental scope, and metric and predictor concerns.
5 Threats to Validity
- Failures are counted only after execution, using actual trajectory rewards to compute JFI; thresholds are calibrated from random executions of trained policies.Mutation episodes are rerun, and crossover offspring are executed after the search.Source: §5 · p. 22
- The evaluation covers three environments and two value-based MARL algorithm families, so findings may not transfer to other systems.Training policies and executing thousands of episodes constrain the experimental scope; the environments cover navigation, foraging, and pursuit.Source: §5 · p. 22
- JFI measures reward division, not reward size, while coverage complements failure counts by distinguishing how failures spread across the state space.Predictor errors can waste testing budget on fair episodes, but executed failures are judged using measured JFI, so prediction accuracy affects search efficiency rather than reported-failure validity.Source: §5 · p. 22
6 Related Work
Prior MARL fairness work centers on metrics and training objectives, while existing MARL testing targets functional failures rather than fairness. FairTest positions low-JFI episode testing against these gaps and the single-agent focus of much DRL testing.
6.1 Fairness in Multi-Agent Reinforcement Learning
- MARL fairness work uses JFI, Gini, and min-max ratio and optimizes fairness during training, while FairTest tests episodes for low JFI.The related work frames deployment-time validation of trained policies as distinct from training-time fairness optimization.Source: §6.1 · pp. 22–23
6.2 Testing Multi-Agent Reinforcement Learning
- Existing MAS testing targets functional failures or robustness degradation; FairTest instead uses fairness as its oracle and searches for low-JFI episodes.MASTest models team behavior with graphs and diversity-guided search, but does not target fairness.Source: §6.2 · p. 23
6.3 Testing of Single-Agent Deep Reinforcement Learning
- Single-agent DRL testing commonly targets reward crashes or safety violations, while FairTest combines search and machine-learning guidance to test MARL fairness.The cited review identifies specialized fairness testing as a key gap.Source: §6.3 · p. 24
7 Conclusion
FairTest searches and prioritizes candidate executions to verify MARL policy fairness before deployment. It finds more failures than every baseline across configurations, while root-cause analysis remains an open direction.
7 Conclusion
- FairTest finds more fairness failures than every baseline in all configurations, with statistically significant differences and large effect sizes.Ablations support the value of fairness features and each fitness function; Pareto-based prioritization delivers the largest part of the gain.Source: §7 · p. 24
- Guidance scores candidates using measured fairness, predicted fairness, and policy decision uncertainty; prioritization uses predicted fairness and uncertainty to direct runs.Crossover and mutation generate further candidates from executions already run, and a failure is reported when execution confirms fairness below the threshold.Source: §7 · p. 24
- Root-cause analysis remains open: localizing the sub-episodes behind a fairness failure could identify the responsible agent and action.The paper also identifies feeding detected failures back into retraining for fairness enhancement as a future direction.Source: §7 · pp. 24–25