Achieving Fairness in Multi-Agent MDP Using Reinforcement Learning

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, provably efficient 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 multiagent 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. Published as a conference paper at ICLR 2024 central controller that focuses solely on maximizing the aggregate reward may allocate the machine exclusively to the job with the higher reward, causing the job with the lower reward to remain in a waiting state indefinitely. In this paper, our objective is to identify fair decision-making strategies for multi-agent MDP problems, ensuring that all agents are treated equitably. Drawing inspiration from well-known fairness principles (Arrow, 1965; Pratt, 1978; Atkinson et al., 1970) , we establish a formalization of fairness as a function of the individual value function of agents. Specifically, we concentrate on α-fairness, which encompasses both egalitarian or max-min fairness (when α → ∞) and proportional fairness (when α = 1). The parameter α allows us to adjust the level of fairness desired. To illustrate this concept, let's consider our example of two jobs with different rewards competing for the same machine. Proportional fairness dictates that the machine should be accessed with equal probability by both the low-reward and high-reward jobs. Conversely, max-min fairness suggests that the job with the higher reward should access the machine with a probability that is inversely proportional to its reward. In this work, we seek to determine the policy that maximizes the α-fairness value of the individual value functions of an MDP. Considering that the knowledge of the environment is usually unknown beforehand in real-world applications, we consider a Reinforcement Learning (RL)-based approach. However, a significant challenge of non-linearity arises since the central controller is not optimizing the sum of the individual value functions, rendering the classical Bellman equation inapplicable. Consequently, conventional techniques such as value-iteration-based or policy-gradient-based approaches cannot be directly employed. To evaluate an online algorithm, regret is a widely used metric that measures the cumulative performance gap between the online solution in each episode and the optimal solution. While there are algorithms that provide good empirical performance, they do not provide any regret guarantee. Therefore, we aim to develop an algorithm that exhibits sub-linear regret with respect to the α-fair solution. Further, since generating new data is costly or impossible for some applications, we also seek to develop a provably-efficient offline fair RL algorithm, i.e., an algorithm that requires no real-time new data. In short, we seek to answer-