# Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 43 references that are in the map.
- First posted on arXiv 13 Mar 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Deep Neural Networks and Tabular Data: A Survey](https://mlsanity.com/paper/2110.01889/) (2021)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [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)
- [Towards Understanding Knowledge Distillation](https://mlsanity.com/paper/2105.13093/) (2021)
- [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)
- [Preserving Causal Constraints in Counterfactual Explanations for Machine Learning Classifiers](https://mlsanity.com/paper/1912.03277/) (2019)
- [Algorithmic recourse under imperfect causal knowledge: a probabilistic approach](https://mlsanity.com/paper/2006.06831/) (2020)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [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)
- [Getting a CLUE: A Method for Explaining Uncertainty Estimates](https://mlsanity.com/paper/2006.06848/) (2020)
- [CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms](https://mlsanity.com/paper/2108.00783/) (2021)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [On Counterfactual Explanations under Predictive Multiplicity](https://mlsanity.com/paper/2006.13132/) (2020)
- [On the Adversarial Robustness of Causal Algorithmic Recourse](https://mlsanity.com/paper/2112.11313/) (2021)
- [Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis](https://mlsanity.com/paper/2106.09992/) (2021)
- [Inverse Classification for Comparison-based Interpretability in Machine Learning](https://mlsanity.com/paper/1712.08443/) (2017)
- [FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles](https://mlsanity.com/paper/1911.12199/) (2019)
- [Evaluating Robustness of Counterfactual Explanations](https://mlsanity.com/paper/2103.02354/) (2021)
- [Consistent Counterfactuals for Deep Models](https://mlsanity.com/paper/2110.03109/) (2021)
- [Algorithmic Recourse in the Wild: Understanding the Impact of Data and Model Shifts](https://mlsanity.com/paper/2012.11788/) (2020)
- [Counterfactual Explanations for Arbitrary Regression Models](https://mlsanity.com/paper/2106.15212/) (2021)

## Built on by (most cited first, 30 of 40)

- [Adversarial attacks and defenses in explainable artificial intelligence: A survey](https://mlsanity.com/paper/2306.06123/) (2023)
- [Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees](https://mlsanity.com/paper/2305.11997/) (2023)
- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation](https://mlsanity.com/paper/2309.12545/) (2023)
- [Finding Regions of Counterfactual Explanations via Robust Optimization](https://mlsanity.com/paper/2301.11113/) (2023)
- [Promoting Counterfactual Robustness through Diversity](https://mlsanity.com/paper/2312.06564/) (2023)
- [Generating robust counterfactual explanations](https://mlsanity.com/paper/2304.12943/) (2023)
- [Setting the Right Expectations: Algorithmic Recourse Over Time](https://mlsanity.com/paper/2309.06969/) (2023)
- [Counterfactual Explanations with Probabilistic Guarantees on their Robustness to Model Change](https://mlsanity.com/paper/2408.04842/) (2024)
- [Fairness in Algorithmic Recourse Through the Lens of Substantive Equality of Opportunity](https://mlsanity.com/paper/2401.16088/) (2024)
- [The Risks of Recourse in Binary Classification](https://mlsanity.com/paper/2306.00497/) (2023)
- [Time Can Invalidate Algorithmic Recourse](https://mlsanity.com/paper/2410.08007/) (2024)
- [Feature Responsiveness Scores: Model-Agnostic Explanations for Recourse](https://mlsanity.com/paper/2410.22598/) (2024)
- [Interval Abstractions for Robust Counterfactual Explanations](https://mlsanity.com/paper/2404.13736/) (2024)
- [Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations](https://mlsanity.com/paper/2407.07482/) (2024)
- [Navigating Explanatory Multiverse Through Counterfactual Path Geometry](https://mlsanity.com/paper/2306.02786/) (2023)
- [Faithful Model Explanations through Energy-Constrained Conformal Counterfactuals](https://mlsanity.com/paper/2312.10648/) (2023)
- [Counterfactual Explanations for Model Ensembles Using Entropic Risk Measures](https://mlsanity.com/paper/2503.07934/) (2025)
- [From Search To Sampling: Generative Models For Robust Algorithmic Recourse](https://mlsanity.com/paper/2505.07351/) (2025)
- [Explaining Black-Box Models through Counterfactuals](https://mlsanity.com/paper/2308.07198/) (2023)
- [Trust Regions for Explanations via Black-Box Probabilistic Certification](https://mlsanity.com/paper/2402.11168/) (2024)
- [Learning-Augmented Robust Algorithmic Recourse](https://mlsanity.com/paper/2410.01580/) (2024)
- [Characterizing Data Point Vulnerability via Average-Case Robustness](https://mlsanity.com/paper/2307.13885/) (2023)
- [CE-QArg: Counterfactual Explanations for Quantitative Bipolar Argumentation Frameworks (Technical Report)](https://mlsanity.com/paper/2407.08497/) (2024)
- [Robust Counterfactual Explanations under Model Multiplicity Using Multi-Objective Optimization](https://mlsanity.com/paper/2501.05795/) (2025)
- [Optimal Robust Recourse with Lp-Bounded Model Change](https://mlsanity.com/paper/2509.21293/) (2025)
- [Reinforcement Learning for Durable Algorithmic Recourse](https://mlsanity.com/paper/2509.22102/) (2025)
- [Algorithmic Recourse with Missing Values](https://mlsanity.com/paper/2304.14606/) (2023)
- [Explaining and visualizing black-box models through counterfactual paths](https://mlsanity.com/paper/2307.07764/) (2023)
- [Perfect Counterfactuals in Imperfect Worlds: Modelling Noisy Implementation of Actions in Sequential Algorithmic Recourse](https://mlsanity.com/paper/2410.02273/) (2024)

## Abstract (arXiv)

As machine learning models are increasingly being employed to make consequential decisions in real-world settings, it becomes critical to ensure that individuals who are adversely impacted (e.g., loan denied) by the predictions of these models are provided with a means for recourse. While several approaches have been proposed to construct recourses for affected individuals, the recourses output by these methods either achieve low costs (i.e., ease-of-implementation) or robustness to small perturbations (i.e., noisy implementations of recourses), but not both due to the inherent trade-offs between the recourse costs and robustness. Furthermore, prior approaches do not provide end users with any agency over navigating the aforementioned trade-offs. In this work, we address the above challenges by proposing the first algorithmic framework which enables users to effectively manage the recourse cost vs. robustness trade-offs. More specifically, our framework Probabilistically ROBust rEcourse (textttPROBE) lets users choose the probability with which a recourse could get invalidated (recourse invalidation rate) if small changes are made to the recourse i.e., the recourse is implemented somewhat noisily. To this end, we propose a novel objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates, minimizes recourse costs, and also ensures that the resulting recourse achieves a positive model prediction. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance w.r.t. different classes of underlying models (e.g., linear models, tree based models etc.), and leverage these results to efficiently optimize the proposed objective. Experimental evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.