Achieving Fairness in Multi-Agent MDP Using Reinforcement Learning

The experimental results are very limited and cast doubts on the applicability of the proposed algorithms: The toy MDPs are very small and have a short horizon.

Response: We added a new simulation figure with a longer horizon (H=10) in the new Figure 4 of the current revision, and we will add more simulations for the final version of this paper.

---

The method is not compared with any other approach from the literature on fair MARL. There is basically no baseline in the experimental results.

Response: Fair MARL is a relatively new topic and that is why when we write the paper, there are almost no popular existing algorithms with regret guarantees that are suitable for a baseline in our setup (e.g., some algorithms have much higher computation complexity than ours).

---

Since the authors are talking about resource allocation throughout the paper and that problem setting seems to be the main goal. I was surprised to see the experiments are on some randomly generated toy MDPs.

Response: Thanks for your suggestions. Our current simulation is on randomly generated toy MDPs because we want to speed up the simulation. Nonetheless, we agree with the reviewer that showing experiments on real resource allocation is more helpful. Although the rebuttal time period is too short to run simulations in this new setup, we will add these simulations on resource allocation in the final version.

---

I would have preferred to see the experimental results in the main body of the paper, perhaps instead of the proof outlines.

Response: Thanks for your suggestion. In the final version, we plan to allocate some space (by shrinking the length of some other parts) in the main body to include experimental results.

---

I find the paper hard to follow, and I think both the writing and the outline of the paper needs some improvements for more clarity and coherence. Some examples are: Some of the notation is cluttered and overloaded (e.g., equations 10-13) which makes the math hard to understand.

Response: Thank you for your comment. Due to space limitations, we had to put some less important math details in Appendix C. We will revise the paper further to ensure that the main body is self-contained.

---

While I appreciate the existence of proof outlines, in their current form they are vague (at least to me).

Response: Due to the limit of the paper length, we use the proof outline only to show readers a rough idea of our proving methods. If the reviewer wants to know some specific parts of the proof outline, we are happy to provide more details. The full rigorous proof is in the appendix.

---

Also, I am confused by their positioning in the text; for example, proof outline of Theorem 1 is not immediately after the Theorem. Some section titles are too generic without any useful information. For example Section 5 is titled “Algorithm” whereas Section 6 is titled “Offline Fair MARL”. It makes sense to rename Section 5 to something more informative (e.g., Online Fair MARL).

Response: Thanks for your suggestions. In the revision, we have changed the location of the proof outline and the section title as you suggested.

---

Why is the horizon extremely short (H=3) in the experiments in Appendix G?

Response: We use a short horizon to speed up the simulation. To address the concern of the horizon length, in the revision, we have added experiments of a slightly longer horizon (H=10) in the new Fig. 4.

---

In Figure 3, why is the offline RL algorithm significantly outperforming the online RL algorithm? I find this a bit surprising because usually online only performs better and more importantly, your proposed online RL algorithm is optimistic whereas your offline RL algorithm is pessimistic.

Response: The reason is that in Fig 3, for each $K$, the offline RL algorithm uses the same data collected by the online algorithm. In other words, the high-quality data explored by the online algorithm is also used as the input of the offline RL algorithm. Thus, the offline algorithm gets the full benefits of the high-quality data collected by the online algorithm. Meanwhile, the online algorithm needs to balance between the exploitation of the collected data and future exploration, while the offline algorithm totally works on exploitation. This is why the offline RL algorithm works better than the online algorithm in Fig. 3. We also agree that if the offline algorithm uses different data (e.g., randomly generated data), then the online algorithm may perform better than the offline one when the offline RL algorithm does not get access to the high-quality data collected by online RL.

---

Despite the vast contributions, I think the paper somewhat overclaims. I suggest to rewrite some parts of the Abstract, Introduction, and Related work. I elaborate below: Fairness in (deep) RL, and in particular alpha-fairness, has been studied in multiple prior works. The Related Work section is too concise and does not give the existing literature enough merit. Example: Zimmer et al. 2021 is cited, but is claimed to focus on gini fairness. This is not true: they focus on a general class of fair SW functions, including alpha-fairness, and they have long-term fairness, and they propose a policy gradient algorithm. Another example: Ivanov et al. 2021 is missing, and they have long-term max-min fairness.

Response: Thank you for your suggestion. We have now modified our claim. We agree that Zimmer et al. 2021 indeed considered alpha-fairness. However, unlike those previous works, we provide regret bounds. Further, unlike all the other papers, we also consider an offline RL setup. We have now added the above in the paper. We did not find Ivanov et al. 2021. If the reviewer can provide the title or the link of the paper, we are happy to cite and compare with it in the final version.

---

In abstract, “the exploration of fairness in such systems for unknown environments remains open”. Yet many papers from section 2 are in model-free setting.

Response: While we agree that there are model-free algorithms with good empirical performance, these algorithms do not provide theoretical guarantees, e.g., none of the algorithms provide a regret bound. This is what we meant in the above sentence. In the revision, we modified the sentence as the following: “...provably efficient exploration of fairness in such systems for unknown environments remains open”.

---

The experiments are simple. I am not sure how to express it: they are as simple as they could be. One would actually have trouble to come up with simpler experiments. Two to four states, actions, agents, and transitions in an episode, all uniformly generated. This is ok by itself for a theoretical paper: after all, simple experiments are better than no experiments. But the authors claim that “... we also developed a policy-gradient-based algorithm that is applicable to large state space as well.” I would not call four a large number, so there is no evidence for this claim. Other than these problems, the contribution is primarily theoretical and I only skimmed the theory.

Response: Thanks for your understanding. In the current revision, we added a new simulation figure with a longer horizon (H=10) in the new Figure 4. In the final version, we will add more simulations.

---

Given my comment about the relation to literature, would it perhaps be more fair (pun not intended) to frame the paper as theoretically justifying existing approaches and proposing their new implementations rather than proposing new approaches?

Response: Thank you for the interesting question. Note that our proposed algorithm is indeed a new algorithm that can achieve regret bound on fairness. Further, to the best of our knowledge, we propose the first offline RL algorithm with provable sub-optimal guarantee. As the reviewer pointed out there are algorithms that have attained good empirical performance, however, they do not provide any theoretical guarantees. We hope that our work can influence others to provide theoretical performance bounds for those approaches as well.

---

End of 5.1: why is the policy defined stochastically instead of deterministic argmax_a q? Wouldn’t the deterministic policy maximize social welfare?

Response: The last equation of Section 5.1 is due to the definition of occupancy measure $q$ in Eq. (8). The value of $q$ in the last equation of Section 5 is from the optimization result of Eq. (10). Then we just use Eq. (8) to find a policy that will lead to this occupancy measure, i.e., the last equation of Sec 5.1. Notice that after we get $q$, the optimization process is finished. Finding the policy that leads to this $q$ based on Eq. (8) does not involve any optimization.

A deterministic policy is a special case of our solution. If the optimal policy is a deterministic policy, then for a given $s$, $q_h(s, a)$ will only have one non-zero (equal to 1) term among all $a$. However, since the Bellman equation does not apply in our fairness setup, the optimal fair policy may not necessarily be a deterministic policy.

---

Followed by "Response to Reviewer KfsC (part 2)"

All concerns relate to the practicality of the method: While the regret bounds are proven with a PAC guarantee, the cardinality of S is often huge in real-world settings, making it difficult to use. The occupancy measure is based on the frequency of appearance for each state-action pair, which may be biased and difficult to count since we cannot always experience the entire environment.

Response: We agree that the cardinality of S can be large in a multi-agent system and counting the state-action pair may be difficult in this case. However, in this paper, our focus is on dealing with fairness. We leave the possible state dimension reduction methods to future work. For example, one possible extension might be to consider linear MDP structure in [1-3]. For the concern that we cannot always experience the entire environment, our online algorithm indeed has an exploration term in the range of confidence intervals that puts priority on those unvisited state-action pairs.

Also note that we use a policy-gradient approach which might be more suitable for large state-space as they can leverage on function approximation using neural networks. However, the sample complexity bound characterization of such approaches has been left for future investigations.

[1]. Neu, Gergely, and Nneka Okolo. "Efficient global planning in large mdps via stochastic primal-dual optimization." In International Conference on Algorithmic Learning Theory, pp. 1101-1123. PMLR, 2023.

[2]. Neu, Gergely, and Julia Olkhovskaya. "Online learning in MDPs with linear function approximation and bandit feedback." Advances in Neural Information Processing Systems 34 (2021): 10407-10417.

[3]. Nachum, Ofir, and Bo Dai. "Reinforcement learning via fenchel-rockafellar duality." arXiv preprint arXiv:2001.01866 (2020).

---

Estimating the empirical average of p and r is often challenging in multi-agent settings, and the confidence interval may be unreliable.

Response: We agree that in multi-agent settings, the empirical average of $p$ and $r$ needs a lot of samples. However, the definition of the confidence interval implies that it is an interval with high probability within which the true value lies. In our work, when there are few samples, the confidence interval will be large. When there are many samples, the confidence interval will be small. It is certainly true that such a confidence interval scales with the cardinality of the state-space. One possible solution might be to use a linear MDP structure where transition probability and the reward are linear in the known feature space in order to efficiently compute the confidence interval. The characterization of our policy for such a linear MDP constitutes an interesting future research direction.

---

Could you please provide some examples to demonstrate the effectiveness of fairness in a multi-agent system?

Response: Certainly. The effectiveness of fairness is motivated by the literature on resource allocation in communication networking systems. For example, the max-min fairness is particularly effective when the overall system is limited by the agent/device that has the smallest utility. For example, the throughput over a route in a network (a set of links) is limited by the link with the smallest capacity. Thus, by maximizing the minimal agent’s (link’s) capacity, we effectively maximize the throughput of the network.

---

I cannot understand what the experiment in the appendix demonstrates. Could you please provide a detailed description? (or how each agent can benefit from the fairness algorithm?)

Response: Thank you for this question. The fairness algorithm’s goal is to not necessarily benefit all agents, but to ensure that the disparity among agents is not very large. Usually, to achieve the fairness objective, some agents will need to sacrifice their rewards while some other agents will get more rewards (thus the result becomes “fair”). How the disparities are mitigated depends on the fairness objective. For example, in the max-min fairness, we tend to equalize the cumulative rewards achieved by each agent. In our simulations in the appendix, we consider all three types of fairness introduced in Section 3. For example, in Fig. 1(a), the blue curve approaches the red dashed line, which means that our Algorithm 1 eventually achieves the max-min fairness. In other words, the algorithm learned an optimal policy that can maximize the long-term return of the agent who has the smallest long-term return among all agents.

---

It seems that the main novelty of this paper is showing that the optimal fairness-aware policy can be solved by convex optimization in the space of visitation measure. The function F is Lipschitz and monotone in each coordinate. One can easily extend the performance-difference lemma for standard MDP to this new problem.

Given existing works on UCB-based and pessimism-based RL, what are the technical novelties?

Response: For the novelty of the results, to the best of our knowledge, our work is the first to give the regret/suboptimality bound for both online and offline fair RL algorithms. We achieve sub-linear regret bound and order (nearly) optimal in $K$.

Regarding the technical novelty, although we acknowledge that certain components/steps of our methods (e.g., using confidence bound to quantify the uncertainty) may seem similar to some online convex work, our work, in general, is different. This is because the max-min, proportional, and alpha fairness objectives have not been studied in the RL literature, and the methods for a general concave objective do not fit here because the fairness objective (proportional and alpha fairness) is not always L-Lipchitz. This critical difference between the fairness objective and the general Lipschitiz continuous concave objective is also one of our motivations. Specifically, since the proportional and alpha fairness objective function can go to infinity and the regret can be unbounded, we have to make an additional requirement in Assumption 1 that the instant reward should not be too small. Related to this point, the technical challenge/novelty is how to connect this additional requirement to the performance of our algorithm. Indeed, as we show in the main results, this effect depends on the specific type of fairness, which is characterized by the coefficient $C_F$. In this regard, we state and prove Lemma 5 to show the dependency over different fairness functions, which we use to bound the regret.

Furthermore, there are subtle differences in the algorithmic front as well. For example, we find that instead of a state-action occupancy measure, we need to consider a state-action-next state occupancy measure for efficient computation for an online approach. On the other hand, we have to modify the reward function in order to find the policy in the offline setup.

---

The setting seems a bit restrictive. This paper considers the centralized setting and assumes all the $N$ agents have the same action $a$. This makes the problem no different from a single-agent MDP with different reward functions. The assumption that the reward function is bounded from below by $\epsilon/H$ seems an unnatural assumption.

Response: In our setting, we consider a centralized decision maker that learns the fair policy for all agents. Different agents can have different actions and different rewards, while the centralized decision-maker can view the actions of all agents as an aggregated action. However, the reward cannot be aggregated because of the fairness requirement. Therefore, the MDP is not equivalent to a single-agent MDP. While we consider that a central agent is taking decisions, our focus is on how those decisions can be fair to the agents.

Further note that we can consider the setup where each individual agent is making a decision (here, the action-space can be different for different agents). Our algorithm is still applicable and it is equivalent to a centralized-training-and-decentralized-execution framework [1-2]. In particular, the optimal joint action can be learned by a centralized agent, then each agent can execute its own action based on the global state. The consideration of a decentralized training framework where each agent can learn only from its local information has been left for future investigations.

[1]. Chen, Gang. "A New Framework for Multi-Agent Reinforcement Learning--Centralized Training and Exploration with Decentralized Execution via Policy Distillation." arXiv:1910.09152 (2019).

[2]. Zimmer, Matthieu, Claire Glanois, Umer Siddique, and Paul Weng. "Learning fair policies in decentralized cooperative multi-agent reinforcement learning." ICML 2021.

---

It seems unclear whether the fairness notions studied in this work include most of the common fairness metrics. For example, existing works also study Generalized Gini Social Welfare Function in the context of MARL.

Response: We agree that there are some other fairness types in the literature. However, in our paper, we have considered max-min, proportional, and alpha fairness, which are the most common/standard types in the literature of resource allocation (e.g., see Mo & Walrand (2000)).

Jeonghoon Mo and Jean Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on networking, 8(5):556–567, 2000.

---

Followed by "Response to Reviewer uKyX (Part 2)"