Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis
This addresses the need for interpretable recourse in algorithmic decision-making, offering a more efficient and explainable alternative to user-specific optimization approaches.
The paper tackles the problem of generating explainable counterfactual interventions for black-box machine learning decisions, such as loan denials, by learning a program that outputs sequences of actions with explanations, resulting in orders of magnitude fewer queries to the classifier compared to existing methods.
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.