Actionable Recourse Summaries via Optimal Decision Trees

Abstract

Actionable Recourse aims to return feasible, low-cost edits on input features that flip black-box predictive models' decisions to a desired outcome. While most counterfactual explanation methods optimize actions per instance, many applications require transparent, consistent prescriptions to populations of affected individuals. Other group-level recourse methods already handle the setting by assigning actions to interpretable regions, but their optimization is not inherently aligned with modern dynamic programming tree learners, which are proven to guarantee global optimum. Here, we adapt optimal decision trees to examine this case under a separable, globally optimal formulation.

We introduce SOGAR (Summaries of Optimal and Global Actionable Recourse), a bi-objective optimization task built on STreeD (separable trees with dynamic programming). Under standard binarization and separability assumptions, SOGAR constructs a Pareto front of globally optimal trees that jointly minimize cost and maximize the effectiveness of edits. Each leaf is assigned an optimal action, and the objectives are element-wise additive, enabling dynamic programming recurrences. The outcome is a set of non-dominated, interpretable policies which are represented by different trees with near-tied scores, so users can select by domain preference rather than retrain models.

Across four tabular datasets, SOGAR demonstrates a competitive performance relative to related work, and stable generalization for compact trees. Overall, SOGAR shows that globally optimal tree structures can deliver group-level recourse summaries that are both interpretable and quantitatively strong. At the same time, it delivers a formulation that is reproducible and extendable to future tasks.