# Addressing the Long-term Impact of ML Decisions via Policy Regret

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 56 references that are in the map.
- First posted on arXiv 2 Jun 2021.

## Builds on (most cited first, 22 of 22)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [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)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [How Algorithmic Confounding in Recommendation Systems Increases Homogeneity and Decreases Utility](https://mlsanity.com/paper/1710.11214/) (2017)
- [The Social Cost of Strategic Classification](https://mlsanity.com/paper/1808.08460/) (2018)
- [Runaway Feedback Loops in Predictive Policing](https://mlsanity.com/paper/1706.09847/) (2017)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Discrimination in Online Ad Delivery](https://mlsanity.com/paper/1301.6822/) (2013)
- [The Disparate Effects of Strategic Manipulation](https://mlsanity.com/paper/1808.08646/) (2018)
- [Degenerate Feedback Loops in Recommender Systems](https://mlsanity.com/paper/1902.10730/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [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)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [What does it mean to solve the problem of discrimination in hiring? Social, technical and legal perspectives from the UK on automated hiring systems](https://mlsanity.com/paper/1910.06144/) (2019)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [From Fair Decision Making to Social Equality](https://mlsanity.com/paper/1812.02952/) (2018)
- [Downstream Effects of Affirmative Action](https://mlsanity.com/paper/1808.09004/) (2018)
- [Optimizing Long-term Social Welfare in Recommender Systems: A Constrained Matching Approach](https://mlsanity.com/paper/2008.00104/) (2020)

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

- [Preemptive Detection and Correction of Misaligned Actions in LLM Agents](https://mlsanity.com/paper/2407.11843/) (2024)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Complete Policy Regret Bounds for Tallying Bandits](https://mlsanity.com/paper/2204.11174/) (2022)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)

## Abstract (arXiv)

Machine Learning (ML) increasingly informs the allocation of opportunities to individuals and communities in areas such as lending, education, employment, and beyond. Such decisions often impact their subjects' future characteristics and capabilities in an a priori unknown fashion. The decision-maker, therefore, faces exploration-exploitation dilemmas akin to those in multi-armed bandits. Following prior work, we model communities as arms. To capture the long-term effects of ML-based allocation decisions, we study a setting in which the reward from each arm evolves every time the decision-maker pulls that arm. We focus on reward functions that are initially increasing in the number of pulls but may become (and remain) decreasing after a certain point. We argue that an acceptable sequential allocation of opportunities must take an arm's potential for growth into account. We capture these considerations through the notion of policy regret, a much stronger notion than the often-studied external regret, and present an algorithm with provably sub-linear policy regret for sufficiently long time horizons. We empirically compare our algorithm with several baselines and find that it consistently outperforms them, in particular for long time horizons.