# Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 1 Nov 2021.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Algorithmic Recourse: from Counterfactual Explanations to Interventions](https://mlsanity.com/paper/2002.06278/) (2020)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Interpretable Counterfactual Explanations Guided by Prototypes](https://mlsanity.com/paper/1907.02584/) (2019)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [Algorithmic recourse under imperfect causal knowledge: a probabilistic approach](https://mlsanity.com/paper/2006.06831/) (2020)
- [Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems](https://mlsanity.com/paper/1907.09615/) (2019)
- [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms](https://mlsanity.com/paper/2108.00783/) (2021)
- [On the Fairness of Causal Algorithmic Recourse](https://mlsanity.com/paper/2010.06529/) (2020)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [DECE: Decision Explorer with Counterfactual Explanations for Machine Learning Models](https://mlsanity.com/paper/2008.08353/) (2020)
- [ViCE: Visual Counterfactual Explanations for Machine Learning Models](https://mlsanity.com/paper/2003.02428/) (2020)
- [PermuteAttack: Counterfactual Explanation of Machine Learning Credit Scorecards](https://mlsanity.com/paper/2008.10138/) (2020)
- [Evaluating Fairness Metrics in the Presence of Dataset Bias](https://mlsanity.com/paper/1809.09245/) (2018)

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

- [Achieving Diversity in Counterfactual Explanations: a Review and Discussion](https://mlsanity.com/paper/2305.05840/) (2023)
- [Personalized Algorithmic Recourse with Preference Elicitation](https://mlsanity.com/paper/2205.13743/) (2022)
- [Framing Algorithmic Recourse for Anomaly Detection](https://mlsanity.com/paper/2206.14384/) (2022)
- [Prediction without Preclusion: Recourse Verification with Reachable Sets](https://mlsanity.com/paper/2308.12820/) (2023)
- [Towards User Guided Actionable Recourse](https://mlsanity.com/paper/2309.02517/) (2023)
- [Understanding Endogenous Data Drift in Adaptive Models with Recourse-Seeking Users](https://mlsanity.com/paper/2503.09658/) (2025)
- [From Universal to Individualized Actionability: Revisiting Personalization in Algorithmic Recourse](https://mlsanity.com/paper/2604.08030/) (2026)
- [Cost-Adaptive Recourse Recommendation by Adaptive Preference Elicitation](https://mlsanity.com/paper/2402.15073/) (2024)
- [Am I Being Treated Fairly? A Conceptual Framework for Individuals to Ascertain Fairness](https://mlsanity.com/paper/2504.02461/) (2025)
- [RecourseBench: A Modular Framework for Reproducible Algorithmic Recourse Evaluation](https://mlsanity.com/paper/2606.16113/) (2026)

## Abstract (arXiv)

People affected by machine learning model decisions may benefit greatly from access to recourses, i.e. suggestions about what features they could change to receive a more favorable decision from the model. Current approaches try to optimize for the cost incurred by users when adopting a recourse, but they assume that all users share the same cost function. This is an unrealistic assumption because users might have diverse preferences about their willingness to change certain features. In this work, we introduce a new method for identifying recourse sets for users which does not assume that users' preferences are known in advance. We propose an objective function, Expected Minimum Cost (EMC), based on two key ideas: (1) when presenting a set of options to a user, there only needs to be one low-cost solution that the user could adopt; (2) when we do not know the user's true cost function, we can approximately optimize for user satisfaction by first sampling plausible cost functions from a distribution, then finding a recourse set that achieves a good cost for these samples. We optimize EMC with a novel discrete optimization algorithm, Cost Optimized Local Search (COLS), which is guaranteed to improve the recourse set quality over iterations. Experimental evaluation on popular real-world datasets with simulated users demonstrates that our method satisfies up to 25.89 percentage points more users compared to strong baseline methods, while, the human evaluation shows that our recourses are preferred more than twice as often as the strongest baseline recourses. Finally, using standard fairness metrics we show that our method can provide more fair solutions across demographic groups than baselines. We provide our source code at: https://github.com/prateeky2806/EMC-COLS-recourse