Long-Term Fairness in Reinforcement Learning with Bisimulation Metrics

Thank you for your review.

Weaknesses

• [Extension to other problems] Since our method is based on demographic parity (Dwork et al., 2012), it is in fact applicable to a wide range of problems. We refer the reviewer to (Dwork et al., 2012; Barocas et al., 2023) for detailed discussions on the applicability of demographic parity.

• [Extension to other fairness notions] We agree that exploring adaptations to other fairness notions would be a promising direction for future work. However, as highlighted in the limitations section (Section 7), this paper focuses specifically on group fairness. We believe that establishing the link between bisimulation metrics and group fairness could serve as a foundation for future extensions. Moreover, a key novelty of our approach lies in its unconstrained optimization framework, which sets it apart from other methods that rely on constrained optimization.

• [Assumption of known MDP] It seems there may be some confusion here. To clarify, our method assumes the MDP is unknown—the algorithm does not have access to the explicit functional forms of the reward function or transition dynamics. While we do assume that the MDP is accessible for policy rollouts and sample collection, this is a standard assumption throughout the literature on online RL. Our approach uses only the samples provided by the environment, rather than the explicit forms of $R^{original}(s, a)$ or the transition dynamics. In fact, due to the MDP’s unknown structure, we train a dynamics model $\mathcal{T}_\psi$ on transition samples to evaluate the Wasserstein distance between transition probabilities.

• [Non-stationarity in training] In the off-policy deep RL setting, non-stationarity is unavoidable, which is why mechanisms like target networks are typically used to enhance stability. We recognize that our approach introduces additional non-stationarity due to changes in the reward function and observation dynamics. However, by conducting these optimizations outside of the policy optimization loop, we reduce the impact of non-stationarity, thereby increasing the stability of our method. We acknowledge that this point was not clearly communicated in the original text and have revised it for better clarity.

• [Clarifications on the implementation] Thank you for your suggestion, we have clarified these points in the revised version:

  • During each batch update, we divide states into four quartiles for each group. We then compare states from corresponding quartiles across groups as outlined in Equation (7). For example, in the lending scenario, this means matching the top 25% of individuals from group 1 (based on their credit) with the top 25% from group 2. This quantile matching is essential because, as shown in Figure 4, the initial credit distributions of the two groups (representing the states) have minimal overlap.
  • Detailed architecture and implementation specifics are provided in Appendix D. If there are any further questions, we are happy to address them.

• [Conceptual benefits of our approach] We propose an alternative to the widely used constrained optimization methods, offering a perspective that aligns more closely with real-world practices. For instance, our algorithm functions like a third-party regulator that sets rules for fair decision-making without directly engaging in policy optimization. An analogy would be governmental regulations on lending (learned via the bisimulator) and a bank's decision-making policies (learned using an unconstrained RL approach). We believe this regulatory perspective is largely unexplored in the literature, and we hope our work provides initial insights in this direction.

• [Metrics in supervised learning] We are not entirely sure we understood your question correctly. Could you please provide further clarification?

• [Minor comments] Thank you for highlighting the overuse of the term "co-optimization." We have revised it. Regarding Line 131, this is not a typo as we have used the subscript $a$ in the $tau_a(s’|s, g)$ to represent the action. Regarding Lines 281-282, our point was that the benchmark’s fairness metric does not affect our method's applicability, regardless of the fact that we use demographic parity. For example, in the lending environment, the metrics are recall, credit gap, and total loans. Unlike our method, some baselines (e.a., A-PPO and EO) explicitly constrain the optimization to achieve equalized recall values, which are directly measured by the benchmark.

Thank you for your review.

Weaknesses

• [Simple environments] As highlighted in the limitations section (Section 7), the benchmark we utilized in this paper (D'Amour et al., 2020) is currently the only established benchmark within the fair RL domain. Several recent works (Xu et al., 2024; Deng et al., 2024; Hu et al., 2023; Yu et al., 2022) have also relied on this same benchmark. While we acknowledge the need for more advanced benchmarks, developing such benchmarks falls outside the scope of our paper. If the reviewer is aware of a more complex benchmark that could enhance our evaluation, we would welcome the suggestion.

• [Theoretical analysis on the properties of the reward and observation dynamics] We agree that a theoretical analysis in this area would be valuable. However, we would like to remind the reviewer that our focus is within the deep RL setting. Although our method is solidly based on bisimulation metrics, conducting a theoretical analysis of the learned reward function or transition dynamics is typically only feasible in finite MDPs or bandit settings—problems that are not the focus of our study. Instead, our primary objective is to present a practical algorithm with some theoretical foundation. That said, we have conducted empirical evaluations of the transition dynamics in Section 5 (Lines 374 and 463 of the initial version).

• [Paper’s organization] We have revised the manuscript for improved clarity and have added the modified definition of long-term fairness in the introduction based on Yin et al. (2023). The reviewer mentioned a need for a clearer connection between bisimulation and fairness metrics, but it is unclear to us what specific aspect needs further clarification. We have explicitly established this connection through Theorems 1, 2, and 3 in Section 4, with detailed proofs provided in Appendix A. If there are specific questions or concerns regarding this connection, we would be happy to address them.

Thank you for your review.

Weaknesses

1. [Clarifications] Thank you for your suggestion, we have improved the clarity of the paper in the revised version. Please find the updated document attached, with the changes highlighted in purple text.

Questions

1. [Fixed state vs different state-group pairs] A bisimulation relation compares all state-group pairs (Castro, 2020), which will include the case where the state is the same, but the group is different. Although it makes sense to have a fixed state, it is highly unlikely to have exact equivalence in practice especially when the state space is large. For example, in the credit score scenario, we might have two individuals belonging to two different groups, but have their credit score differ by 1 point. Such a pair would not be considered for the policy update if we fix the state, but it will be accounted for in the group $\pi$-bisimulation update since they will be considered similar enough. Therefore, we choose to not constrain the bisimulation definition by fixing the state and instead use quantile matching to select the states for comparison. For example, in the lending scenario, this means matching the top 25% of individuals from group 1 (based on their credit) with the top 25% from group 2. This quantile matching is essential because, as shown in Figure 4, the initial credit distributions of the two groups (representing the states) have minimal overlap.

2. [Nature of algorithm (online/offline)] The proposed algorithm is currently tailored for online RL algorithms and the dataset $\mathcal{D}$ is collected through interaction with the environment. Exploring extensions to offline RL algorithms is a promising direction for future research.

3. [Role of $\omega$] $\omega$ represents the adjustable parameters of the modifiable MDP observation dynamics. Its role is discussed in Lines 249-254 in the initial submission, with additional clarifications provided in the revised version. The use of $\omega$ is context-specific and is explained individually for each environment in Sections 5.1 and 5.2.

   • In the lending environment, $\omega$ represents the credit changes that depend on the applicant’s group membership. For instance, applicants from the disadvantaged group may receive a higher credit increase upon loan repayment, compared to those who belong to the advantaged group. This is a realistic assumption since in practice, banks or other regulators are allowed to override credit scores during their decision making process (Lines 306-312 in the initial submission).

   • In the college admission environment, $\omega$ represents the group specific costs for score modification. These adjustments can be seen as subsidized education for disadvantaged groups, which is a common practice (Lines 418-420 in the initial submission).

4. [Limitations] Thank you for your suggestion. We have mentioned some of the limitations in Section 7, noting the constrained experimental setup due to the lack of a more complicated benchmark in the existing literature. Additionally, our current approach is based on demographic parity fairness. Extending the method to encompass other fairness criteria remains an intriguing avenue for future research.

We believe we have addressed all of your concerns. Since the only weakness you mentioned is on the clarity of the paper, could you please consider raising the score? If not, could you clarify what may still be missing?

We would like to inform you about additional experiments included in the revised PDF. We have conducted additional experiments with 10 groups (in contrast to the original experiments with 2 groups). These new results demonstrate the scalability of our method to handle a larger number of groups. Please refer to Figure 3 and Table 2 in the revised PDF for details. Due to the rebuttal time constraint, these experiments are run on 5 seeds and compare Bisimulator against ELBERT-PO (the SOTA baseline) and PPO. Full results will be added to the final version.

Additionally, we believe we have addressed all your previous concerns and have improved the clarity of the paper in multiple areas. If you find that all your concerns have been resolved, we kindly request that you consider revising your score. If there are any remaining issues, we would be happy to address them.

• [More complex benchmark] As highlighted in the limitations section (Section 7), the benchmark we utilized in this paper (D'Amour et al., 2020) is currently the only established benchmark within the fair RL domain. Several recent works (Xu et al., 2024; Deng et al., 2024; Hu et al., 2023; Yu et al., 2022) have also relied on this same benchmark. While we acknowledge the need for more advanced benchmarks, developing such benchmarks falls outside the scope of our paper. If the reviewer is aware of a more complex benchmark that could enhance our evaluation, we would welcome the suggestion.

• [Definition 5] This is not a typo as Definition 5 uses $J^\pi$. We refer the reviewer to Definition 2.2 of Satija et al. (2022).

Questions

1. [Definition of long-term fairness] We provided a brief definition of long-term fairness in Lines 30-31 of the original submission: "ensuring fairness over an extended period rather than at the level of individual decisions." A more formal definition has been added to the revised version, following Yin et al. (2023):

Yin et al. (2023) define long-term fairness in RL as the optimization of the cumulative reward subject to a constraint on the cumulative utility, reflecting fairness over a time horizon.

Note that since our fairness definition is based on Satija et al. (2022), we have not added the formal definition and terminology used in Yin et al. (2023) to avoid confusion.

2. [Optimizable parameters] The optimization procedure for Equation (7) is detailed in Sections 4.1 and 4.2. * In Section 4.1, we describe how we optimize the learnable reward function $R_\phi(s, a, g)$, which is parameterized by a neural network with parameters $\phi$ and optimized using a gradient-based optimizer. * In Section 4.2, we describe how we optimize the modifiable parameters $\omega$ of the observation dynamics. $\omega$ is optimized with a gradient-free optimization method (One-Plus-One). Please see our reply to Question 3 below for the role of $\omega$.

3. [Role of $\omega$] $\omega$ represents the adjustable parameters of the modifiable MDP observation dynamics. Its role is discussed in Lines 249-254 in the initial submission, with additional clarifications provided in the revised version. The use of $\omega$ is context-specific and is explained individually for each environment in Sections 5.1 and 5.2.

   • In the lending environment, $\omega$ represents the credit changes that depend on the applicant’s group membership. For instance, applicants from the disadvantaged group may receive a higher credit increase upon loan repayment, compared to those who belong to the advantaged group. This is a realistic assumption since in practice, banks or other regulators are allowed to override credit scores during their decision making process (Lines 306-312 in the initial submission).

   • In the college admission environment, $\omega$ represents the group specific costs for score modification. These adjustments can be seen as subsidized education for disadvantaged groups, which is a common practice (Lines 418-420 in the initial submission).

We believe we have addressed all your concerns. Could you consider revising your score? If there are any remaining issues or areas for improvement, we would appreciate it if you could clarify what still needs to be addressed.

Thank you for your review.

Weaknesses

• [The use of bisimulation metrics] The bisimulation relation was originally introduced for labeled transition systems, and its original use case was in fact for comparing two systems [Milner, 1989]. In RL, bisimulation metrics are psuedometrics that measure the behavioral similarity between states based on transition dynamics and rewards, without requiring the states to belong to the same MDP. While most work on bisimulation metrics in RL has focused on representation learning within a single MDP, these metrics have broader applications beyond representation learning. For instance, they have been used for transfer learning between multiple MDPs (Castro et al., 2010), identifying symmetries (Taylor et al., 2008), and mapping between two MDPs (Rezaei-Shoshtari et al., 2022).

  Our approach introduces a novel application of bisimulation metrics: optimizing specific aspects of an MDP (such as reward functions and observation dynamics) using guidance from these metrics. There are no conceptual or theoretical issues to applying bisimulation metrics in this manner.

• [Scenario illustrating the effect of modifying the reward] As an example, consider the lending environment where group 2 is disadvantaged. In this scenario, many individuals in group 2 have a low likelihood of repayment, although some are capable of repaying their loans. A greedy agent that solely maximizes the bank's profit learns that in order to maximize returns, it is optimal to disregard the small chance of repayment of those individuals and automatically reject all applicants from group 2. However, by optimizing the reward function guided by bisimulation, an additional reward term is introduced into the problem. This term, once learned by the Bisimulator, incentivizes providing loans to group 2, leading to higher acceptance rates and improved recall compared to the greedy agent. It is worth noting that fairness-aware algorithms often experience some performance trade-offs relative to purely greedy approaches, this is widely recognized in the literature (Barocas et al., 2023).

• [Fixed state vs different state-group pairs] A bisimulation relation compares all state-group pairs (Castro, 2020), which will include the case where the state is the same, but the group is different. Although it makes sense to have a fixed state, it is highly unlikely to have exact equivalence in practice especially when the state space is large. For example, in the credit score scenario, we might have two individuals belonging to two different groups, but have their credit score differ by 1 point. Such a pair would not be considered for the policy update if we fix the state, but it will be accounted for in the group $\pi$-bisimulation update since they will be considered similar enough. Therefore, we choose to not constrain the bisimulation definition by fixing the state and instead use quantile matching to select the states for comparison. For example, in the lending scenario, this means matching the top 25% of individuals from group 1 (based on their credit) with the top 25% from group 2. This quantile matching is essential because, as shown in Figure 4, the initial credit distributions of the two groups (representing the states) have minimal overlap.

• [Clarification for proof of Theorem 3] $\epsilon \in \mathbb{R}$ is a small positive threshold that defines how close the iteratively computed pi-bisimulation metric $d_{n}$ is to its fixed-point $d_\sim$. Specifically, we bound $||d_n - d_{\sim}|| \leq ϵ$ by utilizing an existing result stating that the sequence ${||d_n - d_{\sim}||}$ is a contraction that assumes a fixed point $d_{\sim}$ by Banach fixed-point theorem (Castro, 2020). Since we are minimizing Equation 7, updating $d_{n}$ will almost surely reduce to $d_{\sim}$ after $N \geq n$ iterations, which means we would obtain bisimilar state-group pairs where, as was pointed out, the rewards and the transition dynamics would be similar for each group. We combine this fact about bisimulation relations with demographic parity fairness notion such that $\epsilon$ also becomes an acceptable error of how unfairly different state-groups are treated in a sequential decision making process.

• [Implementation details] Please see our replies to Questions 2 and 3 below.

• [Convergence of the algorithm] We would like to remind the reviewer that our focus is within the deep RL setting, where convergence guarantees are nearly impossible to establish. Therefore, proving convergence for our iterative algorithm in this context is not feasible. Our primary goal is to present a practical algorithm with some theoretical foundations based on bisimulation metrics. The empirical results demonstrate the stability and effectiveness of our approach.

We thank the reviewer for their reply and for revising their score.

• Fixed versus different states: We acknowledge that, under function approximation, such pairs could eventually be updated, though this may not always occur. By employing quantile matching, we ensure that similar states are consistently updated. This approach provides a clearer learning signal for the bisimulator, improving its effectiveness in practice.

• Convergence: Due to the utilization of the $\pi$-bisimulation (on-policy bisimulation) metric, establishing such convergence, even in the tabular case, is challenging and is an open research question in the literature, to the best of our knowledge. This limitation is not due to the specifics of our method. As noted in Section 3.2.3 of Kemertas et al. (2021), the policy dependence of the $\pi$-bisimulation metric renders the assumptions required for proving policy improvement in DBC (Zhang et al., 2020), and hence convergence to the optimal policy, overly restrictive and seldom satisfied.

  Consequently, convergence proofs for RL methods based on $\pi$-bisimulation metrics are an open topic of research. It requires an intricate analysis on how the fixed-point properties of $\pi$-bisimulation interact with the convergence properties of a bisimulation-dependent policy, as they both rely on one another. This is an interesting research avenue on its own, beyond the primary focus of our paper, which is the application of bisimulation metrics for group fairness. Nonetheless, these methods, including DBC and our approach, have demonstrated strong and consistent empirical performance.

  We have added this theoretical limitation in the revised PDF in the limitations section (Section 7).

• Additional experiments with several groups: To address your earlier comment regarding the simplicity of the environments, we have conducted additional experiments with 10 groups (in contrast to the original experiments with 2 groups). These new results demonstrate the scalability of our method to handle a larger number of groups. Please refer to Figure 3 and Table 2 in the revised PDF for details. Due to the rebuttal time constraint, these experiments are run on 5 seeds and compare Bisimulator against ELBERT-PO (the SOTA baseline) and PPO. Full results will be added to the final version.

We hope that the new results and our explanation have further addressed your concerns. In that case, we kindly request that you consider revising your score. Otherwise, we would be happy to address them.

References

• Kemertas, M., & Aumentado-Armstrong, T. (2021). Towards robust bisimulation metric learning. Advances in Neural Information Processing Systems, 34, 4764-4777.
• Zhang, Amy, et al. (2020) "Learning Invariant Representations for Reinforcement Learning without Reconstruction." International Conference on Learning Representations.

I accidentally came across this review and discussion of your paper, and noticed the reference our 2021 work, where we pointed out the limitation of the Zhang et al. (2021) theoretical result. Regarding the convergence of policy improvement algorithms using bisimulation, I wanted to take a moment to encourage you to view a follow-up paper, Kemertas & Jepson (2022), linked below. This paper shows one way to obtain (arguably) a stronger convergence result by analyzing a certain approximate policy iteration algorithm. Perhaps the first of its kind, the paper shows convergence of alternating updates to the bisimulation metric (fixed-point iteration) and a policy (given value functions approximated over a bisimulation-aggregated state space).

Link: https://openreview.net/forum?id=Ii7UeHc0mO

We have further made the following changes to the revised PDF, currently available on openreview:

1. Additional experiments (Figure 3 and Table 2): New experimental results with 10 groups, to showcase the scalability of our method to more complex tasks in response to Yfvq and c9Ni. Please note that due to the time constraint of the rebuttal, these results are obtained on 5 seeds and compare Bisimulator against PPO and ELBERT-PO (the SOTA baseline). Full results will be added to the final version.
2. Convergence: Addressing the convergence properties of our method in the limitations section (Section 7) in response to Yfvq and BVZt.