# Towards Return Parity in Markov Decision Processes

arXiv: https://arxiv.org/abs/2111.10476 · HTML: https://mlsanity.com/paper/2111.10476/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 54 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 30 of 34)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Delayed Impact of Fair Machine Learning](https://mlsanity.com/paper/1803.04383/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [Inherent Tradeoffs in Learning Fair Representations](https://mlsanity.com/paper/1906.08386/) (2019)
- [Wasserstein Fair Classification](https://mlsanity.com/paper/1907.12059/) (2019)
- [Fair Regression with Wasserstein Barycenters](https://mlsanity.com/paper/2006.07286/) (2020)
- [Runaway Feedback Loops in Predictive Policing](https://mlsanity.com/paper/1706.09847/) (2017)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Towards Long-term Fairness in Recommendation](https://mlsanity.com/paper/2101.03584/) (2021)
- [Learning Fair Policies in Multiobjective (Deep) Reinforcement Learning with Average and Discounted Rewards](https://mlsanity.com/paper/2008.07773/) (2020)
- [How Do Fair Decisions Fare in Long-term Qualification?](https://mlsanity.com/paper/2010.11300/) (2020)
- [On the Long-term Impact of Algorithmic Decision Policies: Effort Unfairness and Feature Segregation through Social Learning](https://mlsanity.com/paper/1903.01209/) (2019)
- [A Short-term Intervention for Long-term Fairness in the Labor Market](https://mlsanity.com/paper/1712.00064/) (2017)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [The Disparate Equilibria of Algorithmic Decision Making when Individuals Invest Rationally](https://mlsanity.com/paper/1910.04123/) (2019)
- [Interactive Recommender System via Knowledge Graph-enhanced Reinforcement Learning](https://mlsanity.com/paper/2006.10389/) (2020)
- [Group Retention when Using Machine Learning in Sequential Decision Making: the Interplay between User Dynamics and Fairness](https://mlsanity.com/paper/1905.00569/) (2019)
- [From Fair Decision Making to Social Equality](https://mlsanity.com/paper/1812.02952/) (2018)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [Downstream Effects of Affirmative Action](https://mlsanity.com/paper/1808.09004/) (2018)
- [Individual Fairness in Hindsight](https://mlsanity.com/paper/1812.04069/) (2018)

## Built on by (most cited first, 13 of 13)

- [Fair and Optimal Classification via Post-Processing](https://mlsanity.com/paper/2211.01528/) (2022)
- [Policy Optimization with Advantage Regularization for Long-Term Fairness in Decision Systems](https://mlsanity.com/paper/2210.12546/) (2022)
- [Addressing Polarization and Unfairness in Performative Prediction](https://mlsanity.com/paper/2406.16756/) (2024)
- [Designing Long-term Group Fair Policies in Dynamical Systems](https://mlsanity.com/paper/2311.12447/) (2023)
- [Adapting Static Fairness to Sequential Decision-Making: Bias Mitigation Strategies towards Equal Long-term Benefit Rate](https://mlsanity.com/paper/2309.03426/) (2023)
- [Long-Term Fairness Inquiries and Pursuits in Machine Learning: A Survey of Notions, Methods, and Challenges](https://mlsanity.com/paper/2406.06736/) (2024)
- [Fairness Aware Reinforcement Learning via Proximal Policy Optimization](https://mlsanity.com/paper/2502.03953/) (2025)
- [SPRINT: Stochastic Performative Prediction With Variance Reduction](https://mlsanity.com/paper/2509.17304/) (2025)
- [Achievement and Fragility of Long-term Equitability](https://mlsanity.com/paper/2206.12333/) (2022)
- [Group Fairness in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2503.07817/) (2025)
- [Price of Fairness in Short-Term and Long-Term Algorithmic Selections](https://mlsanity.com/paper/2605.06227/) (2026)
- [Long-term Fairness with Selective Labels](https://mlsanity.com/paper/2605.22291/) (2026)
- [Algorithmic Fairness Over Time: Advances & Prospects](https://mlsanity.com/paper/2610.15015/) (2026)

## Abstract (arXiv)

Algorithmic decisions made by machine learning models in high-stakes domains may have lasting impacts over time. However, naive applications of standard fairness criterion in static settings over temporal domains may lead to delayed and adverse effects. To understand the dynamics of performance disparity, we study a fairness problem in Markov decision processes (MDPs). Specifically, we propose return parity, a fairness notion that requires MDPs from different demographic groups that share the same state and action spaces to achieve approximately the same expected time-discounted rewards. We first provide a decomposition theorem for return disparity, which decomposes the return disparity of any two MDPs sharing the same state and action spaces into the distance between group-wise reward functions, the discrepancy of group policies, and the discrepancy between state visitation distributions induced by the group policies. Motivated by our decomposition theorem, we propose algorithms to mitigate return disparity via learning a shared group policy with state visitation distributional alignment using integral probability metrics. We conduct experiments to corroborate our results, showing that the proposed algorithm can successfully close the disparity gap while maintaining the performance of policies on two real-world recommender system benchmark datasets.