Achieving Fairness in Multi-Agent Markov Decision Processes Using
  Reinforcement Learning
Peizhong Ju Arnob Ghosh Ness B. Shroff
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.