Policy Optimization with Advantage Regularization for Long-Term Fairness in Decision Systems
Authors: Eric Yang Yu
Zhizhen Qin
Min Kyung Lee
Sicun Gao
Venue: NeurIPS 2022 Accept (2022)
Keywords: fairness
reinforcement learning
policy optimization
algorithmic decision making

Abstract: Long-term fairness is an important factor of consideration in designing and deploying learning-based decision systems in high-stake decision-making contexts. Recent work has proposed the use of Markov Decision Processes (MDPs) to formulate decision-making with long-term fairness requirements in dynamically changing environments, and demonstrated major challenges in directly deploying heuristic and rule-based policies that worked well in static environments. We show that policy optimization methods from deep reinforcement learning can be used to find strictly better decision policies that can often achieve both higher overall utility and less violation of the fairness requirements, compared to previously-known strategies. In particular, we propose new methods for imposing fairness requirements in policy optimization by regularizing the advantage evaluation of different actions. Our proposed methods make it easy to impose fairness constraints without reward engineering or sacrificing training efficiency. We perform detailed analyses in three established case studies, including attention allocation in incident monitoring, bank loan approval, and vaccine distribution in population networks. 

Appendix: Policy Optimization with Advantage Regularization for Long-Term Fairness in Decision Systems
Eric Yang Yu UC San Diego
Zhizhen Qin UC San Diego
Min Kyung Lee UT Austin
Sicun Gao UC San Diego
A An Introduction to Lyapunov Stability
We first define n-dimensional dynamical system + by:
(tt) f(x(t), u(t),, utt) g(x(t))
where x1)) D is state vector at time E R in the state space D) R.. : D -> R is control function, and f D + Rº is Lipschitz-continnous vector field.
Suppose system & has an equilibrium point at x The system stable x if for all e E R+ there exists some ô(e) E IR+ such that [xx(t) xell < for all 2 0 if ||x(0) xell < 6. In other words, if an initial point z00) starts at some distance from equilibrium point z5. any point along all possible solution trajectories from z00) to z should be smaller than some distance from Ke. To take this stability notion one step further, we say system locally asymptotically stable around xe if lim xt) = 0 for all (cx(0) - xell < 5.
Next, explore the definition of the Lyapunov function and Lie derivative. Using the existing system setup, let V D + R be a continuously differentiable function. V is a Lyapunov function (0) and Ly V (zx))) and Yz D (0), ((x(t) The Lie derivative of V over is
defined:
OV Ōt dx, dt
OV da.
OV Ox: i(t)
L,V(((t)= = Σ
Σ
At a high level, the Lyapunov function defines field of attraction around some equilibrium point, and the Lie derivative V (2(()) measures the rate of convergence of V over time along the system dynamics of zt) its equilibrium point Te. this Lyapunov function be defined, system is asymptotically stable at Z-.
One issue with formulating the Lie derivative in the context of Reinforcement Learning (RL) training that computing requires full access to system dynamics f. which the RL policy training does have access to. Thus, must approximate the Lie derivative along sampled trajectories of the dynamical system during training:
(x(()( 1 1V)
1 Al
where
lim At-o0 (=)) -Lv
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

B Hyperparameters for Case Studies
We used the following hyperparameters in the training procedures. Table Table 2 and Table show the hyperparameters used for PPO variations on attention allocation, lending, and infectious disease control environments, respectively. Note that for the lending and precision disease control environments, our hyperparameters are chosen with respect to min-max normalization applied to each advantage term.
PPO Agent
Co
{1
C2
50
B1
B2
Greedy (G-PPO)
I
0.25
0
0
0
Reward-Only Fairness Constrained (R-PPO)
0.25
10
Advantage Regularized (A-PPO)
1
0.25
0
0.05
0.32
0.63
Table I: The hyperparameters used for each PPO variation during training on the base and harder attention allocation environments.
PPO Agent
So
C1
B1
32
Greedy (G-PPO)
1
0
0
0
Reward-Only Fairness Constrained (R-PPO)
0
0
Advantage Regularized (A-PPO)
0
0.5
0.5
Table 2: The hyperparameters used for each PPO variation during training on the lending environment.
PPO Agent
So
C1
50
31
B2
No Fairness Constraints (N PPO)
1
0
0
Only Reward Fairness Constraint (R PPO)
1
0.1
0
0
0
Only Advantage Fairness Constraint (A PPO)
1
0.6
0.15
0.25
Table 3: hyperparameters used PPO variation during training on the precision disease control environment.
C Social network for Infectious Disease Case Study
Betweenness Centrality
Communties
Figure 1: [Left] Node betweenness centrality visualized for the Karate Club graph the precision disease control environment, where the intensity of the node positively correlates its hetweenness centrality value. [Right] Communities for the Karate Club graph in the precision discase control environment. These communities are obtained by applying the Girvan-Newmin Newman community detection algorithm once on the graph.
We obtain our notion of community the Karate Club graph using the Girvan-Newman community detection algorithm. We define edge betweenness as the number of shortest paths between two nodes that travel through an edge. In this algorithm, each edge is computed for its edge betweenness. Then, the edge with the highest betweenness is removed to reveal two communities seen on the right in Figure [ Node betweenness centrality is defined as the combined fraction of all shortest paths between pairs that pass through node, and can be visualized the left in Figure Although

---

betweenness centrality is distinct from edge betweenness and is not part of the Girvan-Newman algorithm, we include it provide more insight into the underlying structure of the Karate Club Graph.
3


Reviews:
[{"review_id": "vaDPMA-yp1U", "reviewer": "Reviewer_sDf6", "summary": "The authors propose an approach to extend policy optimization algorithms to consider fairness requirement. To achieve this, they extend the MDPs to include two fairness related terms: (i) fairness metric regularization which penalizes when the fairness metric is above a threshold, and (ii) improvement over time term, which penalizes if the fairness metric increases in the next time step. This makes the model fairness aware.", "questions": "* Did you try other regularization terms or variations of the value-thresholding term and decrease-in-violation term in Eq. 3? Can you justify mathematically why the terms used would be optimal?", "limitations": "Yes, authors have adequately addressed the limitations and potential negative impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The extension proposed is simple, intuitive and easy-to-implement. Further, the experiments and results are neatly presented with several case studies. \n\nThe primary weakness is the magnitude of novelty. The authors propose two simple regularization terms without any mathematical analysis. They have also not presented other possible alternatives they considered or any detailed justification about their final choice.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "qzpbiFrEgAq", "reviewer": "Reviewer_pkLZ", "summary": "This paper suggests a method for optimizing a reinforcement learning model which has some auxiliary objective beyond reward (e.g. a fairness objective). They run some experiments and analyze the difference in performance between their method and several others, focusing on application to fairness-type questions, showing the advantages of their method.", "questions": "- Would be useful to clarify (to me) what the novelty is in this paper: is it the method for optimizing and auxiliary objective in the RL setting, the exploration of fairness, or something else?\n- How general is the proposed method? If can be used beyond fairness but you're just choosing to explore fairness here for some reasons, would be nice to walk through that\n- some clarifications on how to interpret the difference between A and R-PPO", "limitations": "none", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- this method seems very general and useful\n- exposition of the method and motivation is very clear\n- experiments support the claims of the method on a variety of simple RL problems\n\nWeaknesses:\n- the novelty of the work is not clear to me as I think I am not quite familiar enough with the relevant RL literature. I'm not sure how many similar methods exist for optimizing auxiliary objective functions like this\n- I'm not quite sure how specific the proposed method is to fairness - if very specific, it should be explained why. If very general, I think the exposition of the paper should be a little bit different to communicate that it's a general method they are specifically exploring with respect to fairness\n\nMinor points:\nline 142: Q value is never defined\nline 168: there are a few hyperparameters to balance this function (the \\beta's). I'm not sure how this relates to the critique of existing methods on line 45, where the authors say that the hyperparameters weighting fairness and accuracy constraints may result in reward hacking.\nline 168: I may just not be familiar enough to the relevant literature but I don't understand why the reference to Lyapunov stability is helpful here\nExperiments: can you clarify more how to interpret the difference between A-PPO and R-PPO?\nLine 303: what is the \"min-max normalization\" and what is it for?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YMKfO9KVDpf", "reviewer": "Reviewer_MEKu", "summary": "The paper proposes a modification to PPO algorithm and presents an algorithm to constrain advantage disparity in the dynamic setup. The empirical results on multiple practical scenarios are also provided.", "questions": "### Q1: what does the term \"human-designed policies\" mean in the summary of experimental results?\n\nIn presented experimental results, it is mentioned several times that the proposed A-PPO outperforms human-designed policies. I am a little bit confused of the used term here. Is the term \"human-designed\" referring to reward engineering (line 46)? If so, it seems that the proposed algorithm also involves an explicitly defined trade-off between utility and fairness violation, e.g., Equation 3. A further clarification would be very helpful.\n\n### Q2: what is the contribution of the paper, is it in terms of technical modification of the PPO algorithm, or there are additional takeaway messages?\n\nI think readers can benefit more from a clearer presentation of the contribution of the paper.\n\n### Q3: how does the proposed modification of PPO algorithm overcome the drawbacks/difficulties of current RL approaches (to algorithmic fairness) outlined in the introduction?\n\nIn introduction (e.g., paragraph 2 of Section 1), the paper listed several drawbacks/difficulties of current RL approaches towards fairness in dynamic settings. I am wondering how the proposed technical modification of the PPO algorithm overcomes some or all of the listed drawbacks.", "limitations": "In light of the questions detailed in Section `Questions`, while the experimental results are relatively well documented, readers can benefit more from clearer presentations of the takeaway messages of the paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper comes from a detailed presentation of the conducted experiments. The results are reported in three case studies (following D'Armor et al., 2020) and the comparisons involve various algorithms and fairness criteria.\n\nWeakness of the paper comes from the way materials are presented. In particular, it would be very helpful if authors can clarify several questions (detailed in Section `Questions`):\n\nQ1: what does the term \"human-designed policies\" mean in the summary of experimental results?\n\nQ2: what is the contribution of the paper, is it in terms of technical modification of the PPO algorithm, or there are additional takeaway messages?\n\nQ3: how does the proposed modification of PPO algorithm overcome the drawbacks/difficulties of current RL approaches (to algorithmic fairness) outlined in the introduction?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BTH3L4QgcKd", "reviewer": "Reviewer_oAdk", "summary": "The paper studies the long-term fairness problem in MDPs by proposing advantage regularization policy optimization methods to achieve high overall utility and mitigate violation of the fairness requirements. ", "questions": "I suggest the authors discuss the fairness notion in the problem setup. The fairness requirement is a function of the state, and depending on the context, it has different implications. I did not know the fairness notion until I read the experiment.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Novelty* The paper studies the long-term fairness problem in MDPs. The problem is well-motivated, and this work is a novel combination of PPO and Lyapunov stability. Overall, the problem setting and methods are novel, but the authors fail to cite some recent works of fairness in MDPs [1-2].\n\n*Quality*: The paper is technically sound. In particular, I find the authors have a reasonable and interesting RL environment setup. \n\n*Clarity*: The paper is well written, but the fairness definition is unclear at the beginning before the case study. \n\n*Significance*:  The long-term fairness problem is important. The paper seems to be a useful contribution to the literature in this area by proposing practical algorithms to achieve long-term fairness.   \n\n[1] Towards Long-term Fairness in Recommendation, in WSDM 2021\n\n[2] Towards Return Parity in Markov Decision Processes, in AISTATS 2022", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept