Research map / Learning theory and algorithms / Prediction and decision losses
Learning Decision Trees and Forests with Algorithmic Recourse
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RACT, a top-down greedy learner for decision trees and random forests that penalizes leaves lacking recourse-reachable positive outcomes, plus set-cover relabeling to meet a recourse-ratio constraint.
Problem
Standard accurate tree-based classifiers often leave many instances without any low-cost executable recourse action; the goal is to learn accurate trees that guarantee valid actions for as many instances as possible.
Approach
Formulates learning a classification tree under an empirical recourse-risk constraint, solves the split search in O(D·N) by adapting adversarial-training-style robust splitting to recourse reachability, and post-processes leaf labels via a weighted partial set-cover greedy with approximation guarantee.
Key results
- On random forests, RACT reaches recourse ratios well above Vanilla and OAF on most datasets with accuracy comparable to baselines (10-fold CV).
- Average MPS action cost for RACT is lower than baselines on all four datasets, e.g., FICO 0.283 vs 0.407 (OAF) and 0.447 (Vanilla).
- Causal-recourse validity on Bail rises to 0.539 for RACT vs 0.201 for OAF and 0.174 for Vanilla; running time is comparable to Vanilla CART/RF.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train the random forest with RACT instead of Vanilla | Random forest · FICO, COMPAS, Credit, Bail | average action cost: FICO: 0.447 ± 0.05 -> 0.283 ± 0.01; COMPAS: 0.298 ± 0.02 -> 0.232 ± 0.02; Credit: 0.293 ± 0.02 -> 0.166 ± 0.04; Bail: 0. | Helped |
| Train the random forest with RACT instead of OAF | Random forest · FICO, COMPAS, Bail | average action cost: FICO: 0.407 ± 0.03 -> 0.283 ± 0.01; COMPAS: 0.28 ± 0.01 -> 0.232 ± 0.02; Bail: 0.525 ± 0.04 -> 0.419 ± 0.05 | Helped |
| Train the random forest with RACT instead of Vanilla | Random forest · FICO, COMPAS, Credit, Bail | causal action validity: FICO: 0.316 ± 0.04 -> 0.648 ± 0.03; COMPAS: 0.599 ± 0.02 -> 0.721 ± 0.02; Credit: 0.669 ± 0.05 -> 0.964 ± 0.03; Bail: 0. | Helped |
| Train the random forest with RACT instead of OAF | Random forest · FICO, COMPAS, Bail | causal action validity: FICO: 0.502 ± 0.03 -> 0.648 ± 0.03; COMPAS: 0.642 ± 0.04 -> 0.721 ± 0.02; Bail: 0.201 ± 0.04 -> 0.539 ± 0.03 | Helped |
| Train the random forest with RACT instead of Vanilla | Random forest · FICO, COMPAS, Credit, Bail | average running time [s]: FICO: 42.09 ± 1.8 -> 48.07 ± 2.33; COMPAS: 2.31 ± 0.32 -> 2.07 ± 0.13; Credit: 292.53 ± 21.6 -> 277.40 ± 25.8; Bail: 24. | No clear effect |
| Train the random forest with RACT instead of the baselines | Random forest · FICO, COMPAS, Credit, Bail | action plausibility: null | No clear effect |
| Increase the trade-off parameter λ | RACT random forest · FICO, COMPAS, Credit, Bail | recourse ratio: null | Helped |
| Increase the trade-off parameter λ | RACT random forest · FICO, COMPAS, Credit, Bail | AUC: null | Hurt |
| Increase δ | RACT classification tree · FICO, COMPAS, Credit, Bail | recourse ratio: null | Helped |
| Increase δ | RACT classification tree · FICO, COMPAS, Credit, Bail | accuracy: null | Hurt |
| Use λ = 0.0, omitting recourse-risk-aware greedy splitting before set-cover relabeling (ablation) | RACT classification tree · FICO, Bail | accuracy: null | Hurt |
Surprising findings
- OAF achieved a 100% recourse ratio on Credit only because it collapsed to a constant classifier predicting the desired class.
Limitations
- Efficiency relies on l_infinity-type (per-feature separable) cost functions; l1/l2 costs not handled efficiently.
- Requires per-dataset tuning of trade-off hyperparameters lambda and delta, which is costly.
- Currently limited to classification trees and random forests; gradient boosted trees and regression trees left as future work.
Experimental setup
Datasets: FICO COMPAS Credit Bail
Benchmarks: FICO COMPAS Credit Bail
Metrics: accuracy AUC recourse ratio running time average action cost (MPS) plausibility (isolation forest outlier score) causal validity
Baselines: Vanilla CART/random forest Only Actionable Features (OAF)
Builds on: CART robust decision trees feature tweaking algorithm maximum percentile shift
Closest papers by meaning
- Learning Gradient Boosted Decision Trees with Algorithmic Recourse (NeurIPS 2025 · similarity 0.91)
- Towards Better Decision Forests: Forest Alternating Optimization (CVPR 2023 · similarity 0.87)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.85)
- Generative Model for Decision Trees (AAAI 2024 · similarity 0.85)
- Generative Forests (NeurIPS 2024 · similarity 0.85)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.