  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.
