# Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 18 Jan 2022.

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

- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [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)
- [Algorithmic Recourse: from Counterfactual Explanations to Interventions](https://mlsanity.com/paper/2002.06278/) (2020)
- [Visualizing the Effects of Predictor Variables in Black Box Supervised Learning Models](https://mlsanity.com/paper/1612.08468/) (2016)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Local Rule-Based Explanations of Black Box Decision Systems](https://mlsanity.com/paper/1805.10820/) (2018)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Algorithmic recourse under imperfect causal knowledge: a probabilistic approach](https://mlsanity.com/paper/2006.06831/) (2020)
- [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- [The Hidden Assumptions Behind Counterfactual Explanations and Principal Reasons](https://mlsanity.com/paper/1912.04930/) (2019)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [Causal Discovery from Changes](https://mlsanity.com/paper/1301.2312/) (2013)
- [A Simple and Effective Model-Based Variable Importance Measure](https://mlsanity.com/paper/1805.04755/) (2018)
- [Decisions, Counterfactual Explanations and Strategic Behavior](https://mlsanity.com/paper/2002.04333/) (2020)
- [Synthesizing Action Sequences for Modifying Model Decisions](https://mlsanity.com/paper/1910.00057/) (2019)
- [Learning Compositional Neural Programs with Recursive Tree Search and Planning](https://mlsanity.com/paper/1905.12941/) (2019)
- [Consequence-aware Sequential Counterfactual Generation](https://mlsanity.com/paper/2104.05592/) (2021)
- [Extracting Incentives from Black-Box Decisions](https://mlsanity.com/paper/1910.05664/) (2019)
- [Learning compositional programs with arguments and sampling](https://mlsanity.com/paper/2109.00619/) (2021)

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

- [Personalized Algorithmic Recourse with Preference Elicitation](https://mlsanity.com/paper/2205.13743/) (2022)
- [The Utility of "Even if..." Semifactual Explanation to Optimise Positive Outcomes](https://mlsanity.com/paper/2310.18937/) (2023)
- [Exploiting Preference Elicitation in Interactive and User-centered Algorithmic Recourse: An Initial Exploration](https://mlsanity.com/paper/2404.05270/) (2024)
- [Time Can Invalidate Algorithmic Recourse](https://mlsanity.com/paper/2410.08007/) (2024)
- [Collective Counterfactual Explanations: Balancing Individual Goals and Collective Dynamics](https://mlsanity.com/paper/2402.04579/) (2024)
- [Learning Actionable Counterfactual Explanations in Large State Spaces](https://mlsanity.com/paper/2404.17034/) (2024)
- [From Universal to Individualized Actionability: Revisiting Personalization in Algorithmic Recourse](https://mlsanity.com/paper/2604.08030/) (2026)
- [Personalized Path Recourse for Reinforcement Learning Agents](https://mlsanity.com/paper/2312.08724/) (2023)

## Abstract (arXiv)

Being able to provide counterfactual interventions - sequences of actions we would have had to take for a desirable outcome to happen - is essential to explain how to change an unfavourable decision by a black-box machine learning model (e.g., being denied a loan request). Existing solutions have mainly focused on generating feasible interventions without providing explanations on their rationale. Moreover, they need to solve a separate optimization problem for each user. In this paper, we take a different approach and learn a program that outputs a sequence of explainable counterfactual actions given a user description and a causal graph. We leverage program synthesis techniques, reinforcement learning coupled with Monte Carlo Tree Search for efficient exploration, and rule learning to extract explanations for each recommended action. An experimental evaluation on synthetic and real-world datasets shows how our approach generates effective interventions by making orders of magnitude fewer queries to the black-box classifier with respect to existing solutions, with the additional benefit of complementing them with interpretable explanations.