🤖 machine learning

Optimal Recourse Summaries via Bi-Objective Decision Tree Learning

The paper introduces SOGAR, a novel framework that formulates recourse summary learning as a bi-objective decision tree problem to generate a complete Pareto front of stable, low-cost, and effective global recourse summaries, thereby enabling flexible trade-off selection between effectiveness and cost without retraining.

Original authors: Ioannis Chatzis, Jason Liartis, Athanasios Voulodimos, Giorgos Stamou

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ioannis Chatzis, Jason Liartis, Athanasios Voulodimos, Giorgos Stamou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are applying for a loan, and a computer algorithm says "No." You ask, "What do I need to change to get a 'Yes'?"

In the world of AI, this is called Actionable Recourse. It's like asking the computer for a recipe to fix your situation.

The Problem: One Size Doesn't Fit All

Most current methods try to give a single piece of advice to everyone who got rejected.

The Flaw: Imagine a group of people rejected for a loan. Some are young with low income; others are older with high debt. If the computer tells everyone to "Increase your income by $5,000," it might be easy for the older person but impossible for the younger one.
The Audit Problem: If you want to check if the system is fair (e.g., does it treat men and women differently?), looking at thousands of individual, unique recipes is a nightmare. It's like trying to find a pattern in a pile of 10,000 different handwritten notes.

The Solution: SOGAR (The "Group Recipe" Chef)

The authors introduce a new method called SOGAR (Summaries of Optimal and Global Actionable Recourse).

Think of SOGAR as a smart chef who doesn't just give one recipe to everyone. Instead, the chef looks at the whole crowd of rejected applicants and says:

"Okay, let's split this group into a few smaller, simpler teams. Team A needs to do this specific thing. Team B needs to do that specific thing."

This creates a Recourse Summary: a small set of clear groups, each with one shared action plan.

The Big Trade-Off: Cost vs. Success

When giving advice, there is always a tug-of-war between two goals:

Effectiveness: How likely is the advice to actually get the loan approved? (High success = Low "Loss").
Cost: How hard is it for the person to actually do the advice? (e.g., "Increase income" is hard; "Change your job title" might be easier).

Usually, to make advice more effective, you have to make it more expensive (harder) for the user. If you make it too easy, it might not work.

How SOGAR Works: The Pareto Map

Most other methods try to find one "perfect" balance between cost and success. They pick a single point on the map and say, "Here is the best answer."

SOGAR is different. It doesn't pick just one point. Instead, it draws the entire map of possible solutions, known as the Pareto Front.

The Analogy: Imagine you are packing a backpack for a hike. You want it to be light (low cost) but also have everything you need (high effectiveness).
- Other methods give you one specific backpack configuration.
- SOGAR gives you a menu of options: "Here is a very light bag with just water (easy but risky). Here is a heavy bag with a tent and food (hard but safe). Here is a medium bag with a sandwich and a map."
Why this matters: The user (or an auditor) can look at the whole menu and decide, "I want the medium bag," without having to re-run the computer to find it.

The Secret Sauce: Decision Trees

To organize these groups, SOGAR uses a Decision Tree.

Think of this tree as a simple flowchart.
Question 1: Is your income under $30k? (Yes/No)
Question 2: Do you have a credit card? (Yes/No)
Result: Depending on your answers, you land in a specific "leaf" (a group), and that leaf has one specific action assigned to it.

The paper claims SOGAR finds the globally optimal tree. This means it doesn't just guess; it mathematically proves it found the best possible way to split the groups to minimize cost and maximize success, all while keeping the tree simple enough for humans to understand.

Real-World Proof: Catching Bias

The authors tested SOGAR on real data (like the "Adult Income" dataset). They found something important:

When they looked at the entire "menu" of solutions (the Pareto Front), they could see that women consistently had to pay a higher "cost" or accept a higher "failure rate" than men to get the same result.
Other methods, which only gave one single solution, missed this pattern because they were looking at just one point on the map. SOGAR's full map revealed the unfairness clearly.

Summary

Old Way: Give everyone one generic, often unfair or confusing piece of advice.
SOGAR: Groups people logically, gives each group a simple, shared action, and shows you the entire range of possible trade-offs between "how hard it is" and "how well it works."
The Benefit: It helps people get better advice and helps auditors spot unfairness in AI systems that other methods miss.

The paper concludes that SOGAR is faster and more accurate than previous methods at finding these optimal groupings, even though it requires more computer power to calculate the full "menu" of options.

Technical Summary: Optimal Recourse Summaries via Bi-Objective Decision Tree Learning

Problem Statement

Automated decision-making systems in critical domains (e.g., credit, hiring, healthcare) often rely on opaque models. While Actionable Recourse provides individuals with specific actions to alter unfavorable outcomes, aggregating these local actions for global auditing and bias detection is costly and often inconsistent. Existing methods for Recourse Summaries—which partition a population into subgroups and assign a shared action to each—struggle to balance multiple objectives:

Recourse Effectiveness (Loss): The portion of the population for whom the assigned action fails to flip the classifier's output.
Recourse Cost: The estimated effort required to enact the action.
Interpretability Constraints: Subgroup count, subgroup description length, and action sparsity.

Current approaches typically scalarize these objectives using arbitrary coefficients or enforce thresholds, failing to provide global optimality guarantees. They often produce a single solution, preventing stakeholders from exploring the fundamental trade-off between cost and effectiveness. Furthermore, many existing methods (e.g., CET, AReS) suffer from high computational runtimes and do not guarantee finding the global optimum.

Methodology: SOGAR

The authors introduce Summaries of Optimal and Global Actionable Recourse (SOGAR), a framework that formulates recourse summary learning as a bi-objective optimal decision tree learning problem.

Core Formulation

Objective: Simultaneously minimize Recourse Cost ( $C$ ) and Recourse Loss ( $L$ ).
Structure: A recourse summary is represented as a shallow, axis-parallel decision tree. Internal nodes perform tests on features to partition the affected population into disjoint subgroups (leaves). Each leaf is assigned a single, sparse action.
Optimality: Instead of scalarizing objectives, SOGAR computes the complete Pareto front of non-dominated solutions. A solution $\tau$ dominates $\tau'$ if it is better in at least one objective and no worse in the other. This allows users to select the ideal trade-off post-hoc without retraining.

Technical Implementation

The method leverages the STreeD dynamic programming framework, which guarantees global optimality for separable optimization tasks.

Separability: The authors prove that finding optimal recourse summary trees satisfies the necessary and sufficient conditions for separability (Markovian cost/transition functions and order-preserving combining operators), enabling exact dynamic programming.
Action Set & Cost: Actions are defined as single or multi-edit operations (e.g., flipping binary values, changing categories, shifting numerical bins). The cost function uses Maximum Percentile Shift (MPS) to ensure scale invariance and realistic effort estimation.
Efficiency Enhancements:
- Caching: Pre-computation of cost and loss for every action-instance pair to enable $O(1)$ lookups during tree search.
- Parallelization: Implementation of multi-threaded CPU and GPU acceleration for aggregating costs and losses at leaf nodes, significantly reducing runtime.
- Constraints: The framework enforces maximum tree depth, maximum leaf count, and action sparsity to ensure interpretability.

Key Contributions

Bi-Objective Formulation: SOGAR is the first method to define recourse summary learning as a bi-objective optimal decision tree problem, jointly optimizing effectiveness and cost under structural constraints.
Global Optimality & Pareto Front: By casting the problem within the STreeD framework, SOGAR computes the exact, complete Pareto front of non-dominated solutions, avoiding arbitrary scalarization and providing global optimality guarantees.
Scalability: The introduction of CPU/GPU parallelization and efficient caching allows the method to solve NP-hard tree learning problems to global optimality within reasonable time budgets, even for large datasets.
Bias Auditing Capability: The diversity of the Pareto front enables the detection of bias across different operating points, revealing disparities that single-solution methods might miss.

Experimental Results

The authors evaluated SOGAR on four tabular datasets (Employee Attrition, German Credit, Bank Marketing, Adult Income) using three classifiers (LightGBM, XGBoost, DNN) against five baselines (CET, AReS, GLOBE-CE, GLANCE, T-CREx).

Performance: SOGAR consistently outperformed all baselines on the invalidity metric (sum of cost and loss) across all datasets and classifiers. It achieved the lowest cost in most datasets and competitive loss values.
Efficiency: While SOGAR has higher computational costs than heuristic methods like GLOBE-CE, it produces the entire Pareto front in a single run. In contrast, baselines like CET and AReS often exceeded the 1-hour timeout limit or failed to find solutions on larger datasets.
Generalization: Experiments showed minimal overfitting, with test metrics closely matching the training Pareto front.
Ablation Studies:
- Depth: Depth 3 offered the best balance between quality and runtime; Depth 4 yielded marginal gains at a prohibitive computational cost.
- Sparsity: Reducing action sparsity ( $k=2$ ) significantly lowered runtime but increased loss, particularly on complex datasets.
- Timeouts: Even with strict time limits (e.g., 10–60 seconds), SOGAR recovered solutions that outperformed baselines, demonstrating its "anytime" capability.

Bias Auditing Case Study

On the Adult Income dataset, SOGAR was used to audit a LightGBM classifier for gender bias. The analysis of the Pareto front revealed that females consistently faced higher invalidity than males across 96.4% of solutions. The disparity was driven primarily by higher recourse loss for females in low-cost regions and higher cost in high-cost regions. This finding highlights that single-solution methods (which often select low-loss, high-cost points) might underestimate the true extent of bias present across the full trade-off spectrum.

Significance and Claims

The paper claims that SOGAR represents a significant advancement in the field of algorithmic recourse and interpretability by:

Providing the first method to guarantee global optimality for recourse summaries.
Eliminating the need for arbitrary hyperparameter tuning (scalarization coefficients) by exposing the full trade-off curve.
Enabling robust global auditing of classifiers, allowing stakeholders to identify and quantify biases that persist across different cost-effectiveness trade-offs.
Demonstrating that exact optimization, when combined with modern hardware acceleration and caching, is a viable alternative to greedy or stochastic approaches for generating interpretable, actionable recourse summaries.

The authors acknowledge limitations, noting that SOGAR incurs higher computational costs than heuristic methods and may struggle with extremely high-dimensional datasets without additional feature selection. They emphasize that while SOGAR aids in auditing, it should be part of a broader fairness toolkit rather than a standalone criterion.