Long-Term Fairness with Unknown Dynamics

Summary

This paper examines the issue of enduring fairness within a dynamically responsive population, framing it as a reinforcement learning (RL) problem with certain constraints. In this scenario, the state distribution is subject to change dynamically based on the actions of the deployed agent. To address this problem, the authors introduce L-UCBFair and R-TD3. L-UCBFair assumes a simplified linear Markov Decision Process, while R-TD3 incorporates existing deep reinforcement learning methods for a more general setting. According to the numerical experiments conducted, the proposed method consistently surpasses the performance of baseline methods. The RL approach enables an agent to learn how to forego short-term utility to steer the system towards more desirable equilibrium states.

Strengths

**Originality**: The authors uniquely approach the fairness problem in machine learning within a context where the underlying state distribution dynamically evolves based on the agent's decision. This novel setup extends the static fairness issue found in the existing literature. The dynamic viewpoint introduces the concept of cumulative reward and distortion (cumulative fairness disparity), aptly fitting the method of reinforcement learning. The experiments carried out distinctly highlight the benefits of incorporating a reinforcement learning method, particularly in cases of changing underlying environments. **Quality and Clarity**: The motivation behind this work is cogently presented in the introduction, while the related works section explores a wide range of existing literature, discussing both fairness issues in non-stationary settings and safe reinforcement learning. The demonstration of numerical experiments is lucidly laid out. **Significance**: The suggested L-UCBFair and R-TD3 methods surpass the performance of baseline methods. The concept of foregoing short-term utility to guide the system towards more optimal equilibrium states is effectively demonstrated. Furthermore, the author presents a thorough theoretical analysis for the proposed L-UCBFair under the linear Markov Decision Process assumption.

Weaknesses

**Weakness 1**: The depiction of Algorithm 1 could be clearer. There are several terms defined in the paper that aren't elaborated upon, making comprehension more challenging. Enhancing the clarity in Section 3.1.1 could greatly improve overall readability. **Weakness 2**: The authors introduce R-TD3 as a broader reinforcement learning method, not reliant on the linear MDP assumption. Could the authors shed more light on the advantages or enhancements that R-TD3 offers in comparison to the foundational method, L-UCBFair? **Weakness 3**: In the numerical experiments, the authors have designed synthetic simulation environments based on straightforward datasets. However, in the existing literature, public simulators dedicated to long-term simulation, such as "Fairness is not static: Deeper understanding of long term fairness via simulation studies", are readily available. Given that this has been mentioned in the related works, could the authors assess their proposed L-UCBFair and R-TD3 in these more complex simulation environments? For instance, situations involving lending, attention allocation, or college admissions could provide further insights. **Weakness 4**: Reinforcement learning utilizes long-term planning to maximize rewards and diminish distortion, whereas myopic-fair methods – the basis of all baseline methods used in the paper – only address a one-step optimization issue. Given this, the result presented in Figure 1 seems rather self-evident as one would expect a long-term planning-based RL method to surpass more short-sighted methods. Could the authors compare their proposed method with more robust baseline methods that also consider underlying dynamics?

Questions

The issue of long-term fairness can become quite resource-intensive when the agent interacts with the real-world scenarios. Within the existing body of reinforcement learning literature, model-based reinforcement learning methods have been devised to enhance sample efficiency. Could the authors discuss the potential of developing a model-based reinforcement learning approach to tackle the long-term fairness problem addressed in this paper? Moreover, several queries were raised in the previously mentioned weaknesses section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors followed the PaperChecklist by providing a discussion on the current limitations.

Summary

This paper considers a binary classification task with long-term fairness. The authors formulate the problem as a constrained MDP where the classifier is an action, the distribution is the state, the distribution will shift reacting to an action. The problem aims to optimize the expected long-term reward under the constraints for long-term fairness in expectation. They develop L-UCBFair which is a model-free algorithm to guarantee long-term fairness with continuous state and action spaces. Under the linear MDP assumption, they prove sublunar regret and disparity with high probability. Finally, experiment results are given to demonstrate the performance of the proposed algorithm.

Strengths

I believe the paper has the following strong points. + The paper formulates fairness constrained classification problem as a constrained MDP, which is new to me. + The paper applies linear MDP algorithms and TD3 to the considered problem and prove the regret bound with linear MDP assumption.

Weaknesses

The paper can still be improved in the following aspects. - The paper seems to directly apply LSVI-UCB and TD3 algorithms to solve the considered constrained MDP problem. It would be much better if the authors can discuss how the algorithm design and proof techniques are different from original works in (Jin et al. (2020)) and Fujimoto et al. (2018). - The paper formulates the fairness-constrained classification problem as a MDP problem, but does not give enough motivation. - It usually requires a lot of exploration for the constrained RL to achieve low disparity, so I am afraid that the fairness violation can be very high at early stages. - The paper is limit in addressing the complexity problem by using constrained RL for this problem. The action space (classifier) can be very large, which can cause a very large complexity.

Questions

1. The paper considers a dynamic where the new distribution is affected by the previous distribution and classifier. Can the authors give some concrete motivation examples for such distribution shift? 2. Can the authors discuss the challenges of solving the MDP with fairness constraints? What are the differences comparing with standard constrained MDP problems? 3. How does the complexity of proposed algorithm rely on the space of state and action?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The limitations are listed by the authors.

Summary

This paper introduces a new method to ensure long-term fairness in reinforcement learning. The method is compatible with different utility measures (e.g., the accuracy of the classifier when the goal is to predict a label) and different fairness constraints (e.g., demographic parity or equal opportunity). The method is an online reinforcement learning method, so the agent has to interact with its environment in order to improve the quality of the policy, either in the real world or in simulation. The authors introduce two measures of regret, one related to the primary utility goal and one related to the fairness measure, and present an upper bound for both regrets achieved by the proposed algorithm. The paper presents empirical results using a mixture of synthetic and real data.

Strengths

- This paper tackles the very important problem of ensuring fairness in a sequential decision-making setting. It uses insights from the - reinforcement learning literature to solve a supervised learning fairness problem. - The proposed method extends existing ones to the continuous setting (i.e., continuous states—e.g., attributes—and continuous actions). - The paper is very thorough with the mathematical formulation, assumptions, and definitions necessary to fully describe the method.

Weaknesses

- The proposed method is an online RL method, where the learning process occurs while the policy is applied. This is often not realistic in scenarios where we would like to ensure fairness, as intermediate policies could lead to unfair behavior. - My understanding is that the proposed method is an extension of the method presented by Ghosh et al. (2022) for the continuous setting, where the method itself is fairly similar, and the main new contribution is showing that it is possible to achieve the same bound in this new setting. I believe that this could be better clarified in the paper to highlight the novelty of this work more clearly. - In the introduction, the authors state that the primary contribution of this work is to consider the problem of long-term fairness as a reinforcement learning problem subject to a constraint. However, previous works have already considered this setting (e.g., the method on which the present work is based). - I believe the experiments with R-TD3 are not strongly supporting the argument that an algorithm without theoretical guarantees can still be used for long-term fairness. Applying the method in just two scenarios does not present enough empirical evidence to support the claim that the final policy is still fair, and without any theoretical guarantees, this is essential.

Questions

- Could the authors please provide some motivating examples for when an online RL method would be useful/applicable, considering the fact that the policy is updated while being deployed and the regret bounds are only for the final distortion and not the disparity at each timestep (possibly causing intermediate policies to be unfair)? - The color scheme in Figure 1 is slightly unclear. The range for the demographic disparity in the first two plots is between zero and 0.005 or zero and 0.07 (a very small interval), but for the proposed method results it is between zero and 1. This makes it harder to compare the fairness measures. Could the authors please clarify this? - Why did the authors select only the Myopic-fair baseline for the second experiment? From the first experiment, it seemed like this wasn’t one of the most competitive baselines, so it would be interesting to see how the other baselines perform in this second scenario as well.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors discuss the limitations of the work. No major concerns.

Summary

The paper demonstrates that reinforcement learning algorithms can be used to satisfy long term fairness constraints in dynamic environments in which a classifier and population interact while finding high-value equilibria. The main approach is to treat the problem as a constrained optimization and optimize the Lagrangian function. The authors use a linear UCB-style algorithm to obtain provable regret bounds on both the cumulative value and constraint violations and demonstrate effectiveness of that algorithm and a less-principled-but-still-practical RL alternative using small simulation studies. Adapting previous work to the interacting classifier population setting requires handling a continuous action space (setting per-group classifier thresholds) - which the authors handle by showing the continuous action space in this setting can be searched in a discretized manner without losing guarantees. The simulation experiments demonstrate that the RL approaches can find good operating points where more myopic policies can end up exacerbating qualification rate disparities.

Strengths

Significance & Originality: The authors address an important question: How to design decision-making algorithms for dynamic settings where the underlying dynamics are not well known and the designers want to be both fair and encourage positive societal outcomes overall. Adding fairness considerations to an RL algorithm with a suitably specified reward function is not a groundbreaking idea, but this work offers a concrete algorithm and practical model-free approach for this question that (as far as I can tell) thus far have not been proposed. Clarity: Paper is very clear and easy to read up to the experiments, setting and notation are clear, as well as the paper’s goals and contributions.

Weaknesses

I found the experiments to be a little bit unclear in terms of what was being demonstrated with each figure / experiment. What is the role of the fully synthetic vs semi-synthetic experiments? I think the paper could be improved with a clearer exposition of the takeaways from each experiment. The authors note that real-world experiments would be necessary to really assess impact of this algorithm. I strongly agree with this sentiment and while I understand that truly real-world experiments can be hard to find, the authors could potentially test across a range of dynamic synthetic environments to give a better sense of the generalizability of the proposed approach.

Questions

1. The shading in figures 1a-d suggests that the demographic parity violation can be mapped to the same state space as qualification parity? Is that really true? For any pair x,y on those plots is there a unique value for the demographic parity violation? 2. How would a purely RL-based long-term reward maximizing agent perform as a baseline (with no fairness constraints)? I would think it might also drive the qualification rates up to the top-right of figures 1a-d, in which case can we be sure it’s the fairness constraints that are actually doing the work here and not just the long-term reward optimization in general?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Authors addressed the limitations of their experimental setup with synthetic environments. They might also consider discussing what types of societal inequalities can and cannot be addressed by fairness-in-decision-making style constraints.

Thank you for rebuttals

I thank the authors for answering my questions. I acknowledge reading the rebuttal and have further questions. **Difference from LSVI_UCB and TD3.** I am convinced that this work is different from LSVI_UCB and TD3 since they do not consider constraints. **Motivation of RL formulation.** The example of loan approval is a good motivation for this problem, but the limitations about the observability should be discussed in the paper. **Fairness violation.** I understand that the constant violation is not avoidable for the online setting. **Difference from constrained MDP.** I understand that the analysis generalizes the constrained MDP with finite action space (Ghosh et al. (2022)) to continuous action space. The issue introduced by continuous action is solved by discretizing the action space which is shown in the proofs of Lemma B.10, B.11, B.12. Please response to me if I miss other technical challenges. **Complexity** I understand that the regret bound depends on the dimensionality of the embedding instead of directly on the size of the action-state space. However, dimensionality of the embedding may also implicitly increases with the size of the action-state space. The authors may need to discuss this scalability issue, especially for this setting where the state includes the full distribution information.