# Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning

arXiv: https://arxiv.org/abs/2306.00324 · HTML: https://mlsanity.com/paper/2306.00324/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 55 references that are in the map.
- First posted on arXiv 1 Jun 2023.

## Builds on (most cited first, 29 of 29)

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation](https://mlsanity.com/paper/1908.08342/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Dynamic Weights in Multi-Objective Deep Reinforcement Learning](https://mlsanity.com/paper/1809.07803/) (2018)
- [Multi-Objective Deep Reinforcement Learning](https://mlsanity.com/paper/1610.02707/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Learning Fair Policies in Multiobjective (Deep) Reinforcement Learning with Average and Discounted Rewards](https://mlsanity.com/paper/2008.07773/) (2020)
- [Multi-Agent Reinforcement Learning Based Resource Allocation for UAV Networks](https://mlsanity.com/paper/1810.10408/) (2018)
- [Algorithms for Fairness in Sequential Decision Making](https://mlsanity.com/paper/1901.08568/) (2019)
- [Learning Fairness in Multi-Agent Systems](https://mlsanity.com/paper/1910.14472/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Learning Fair Policies in Decentralized Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2012.09421/) (2020)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [Proportional Fairness in Federated Learning](https://mlsanity.com/paper/2202.01666/) (2022)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits](https://mlsanity.com/paper/2002.09808/) (2020)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Group Fairness in Bandit Arm Selection](https://mlsanity.com/paper/1912.03802/) (2019)
- [Socially Fair Reinforcement Learning](https://mlsanity.com/paper/2208.12584/) (2022)
- [Achieving User-Side Fairness in Contextual Bandits](https://mlsanity.com/paper/2010.12102/) (2020)
- [Reinforcement Learning with Stepwise Fairness Constraints](https://mlsanity.com/paper/2211.03994/) (2022)

## Built on by (most cited first, 8 of 8)

- [Fairness in Preference-based Reinforcement Learning](https://mlsanity.com/paper/2306.09995/) (2023)
- [Scalable Multi-Objective Reinforcement Learning with Fairness Guarantees using Lorenz Dominance](https://mlsanity.com/paper/2411.18195/) (2024)
- [Fairness in Reinforcement Learning with Bisimulation Metrics](https://mlsanity.com/paper/2412.17123/) (2024)
- [Fair Contracts in Principal-Agent Games with Heterogeneous Types](https://mlsanity.com/paper/2506.15887/) (2025)
- [Fair Resource Allocation in Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2411.09804/) (2024)
- [MAFE: Enabling Equitable Algorithm Design in Multi-Agent Multi-Stage Decision-Making Systems](https://mlsanity.com/paper/2502.18534/) (2025)
- [α-fair heterogeneous agent reinforcement learning](https://mlsanity.com/paper/2606.13076/) (2026)
- [Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2609.36174/) (2026)

## Abstract (arXiv)

Fairness plays a crucial role in various multi-agent systems (e.g., communication networks, financial markets, etc.). Many multi-agent dynamical interactions can be cast as Markov Decision Processes (MDPs). While existing research has focused on studying fairness in known environments, the exploration of fairness in such systems for unknown environments remains open. In this paper, we propose a Reinforcement Learning (RL) approach to achieve fairness in multi-agent finite-horizon episodic MDPs. Instead of maximizing the sum of individual agents' value functions, we introduce a fairness function that ensures equitable rewards across agents. Since the classical Bellman's equation does not hold when the sum of individual value functions is not maximized, we cannot use traditional approaches. Instead, in order to explore, we maintain a confidence bound of the unknown environment and then propose an online convex optimization based approach to obtain a policy constrained to this confidence region. We show that such an approach achieves sub-linear regret in terms of the number of episodes. Additionally, we provide a probably approximately correct (PAC) guarantee based on the obtained regret bound. We also propose an offline RL algorithm and bound the optimality gap with respect to the optimal fair solution. To mitigate computational complexity, we introduce a policy-gradient type method for the fair objective. Simulation experiments also demonstrate the efficacy of our approach.