Learning Gradient Boosted Decision Trees with Algorithmic Recourse
Authors: Kentaro Kanamori
Ken Kobayashi
Takuya Takagi
Venue: NeurIPS 2025 poster ()
Keywords: algorithmic recourse
gradient boosted decision trees
counterfactual explanation
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: This paper proposes a new algorithm for learning gradient boosted decision trees while ensuring the existence of recourse actions. Algorithmic recourse aims to provide a recourse action for altering the undesired prediction result given by a model. While existing studies often focus on extracting valid and executable actions from a given learned model, such reasonable actions do not always exist for models optimized solely for predictive accuracy. To address this issue, recent studies proposed a framework for learning a model while guaranteeing the existence of reasonable actions with high probability. However, these methods can not be applied to gradient boosted decision trees, which are renowned as one of the most popular models for tabular datasets. We propose an efficient gradient boosting algorithm that takes recourse guarantee into account, while maintaining the same time complexity as the standard ones. We also propose a post-processing method for refining a learned model under the constraint of a recourse guarantee and provide a PAC-style analysis of the refined model. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency.

Learning Gradient Boosted Decision Trees with Algorithmic Recourse
Kentaro Kanamori
Ken Kobayashi
Artificial Intelligence Laboratory
School of Engineering Institute of Science Tokyo kobayashi kkiee..... eng isct..ttt.c jp.jp
Fujitsu Limited
k. kanamori wfw.iisuuuiiuuooooooooooiuuuueee
Takuya Takagi
Artificial Intelligence Laboratory
Fujitsu Limited
takagi. takuya@fujitstt com
Abstract
This paper proposes new algorithm for learning gradient boosted decision trees while ensuring the existence of recourse actions. Algorithmic recourse aims to provide a recourse action for altering the undesired prediction result given by model. While existing studies often focus on extracting valid and executable actions from a given learned model, such reasonable actions do not always exist for models optimized solely for predictive accuracy. To address this issue, recent studies proposed framework for learning a model while guaranteeing the existence of reasonable actions with high probability. However, these methods can not be applied to gradient boosted decision trees, which are renowned as one of the most popular models for tabular datasets. We propose efficient gradient boosting algorithm that takes recourse guarantee into account, while maintaining the same time complexity the standard ones. We also propose post-process processing method for refining learned model under the constraint of recourse guarantee and provide PAC-style analysis of the refined model. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency.
Introduction
Machine learning models are increasingly applied to critical decision-maiee making tasks, such loan approvals. such high-stakes applications where predictions can significantly impact individuals [52. decision-makers need to explain how users alter undesired predictions 42 62 Algorithmic Recourse (AR) aims to provide such information (58). For a predictive model f: X - v, desired class y² E V, and an instance E X' such that f(x) + y", AR provides perturbation that flips the prediction result into the desired class, i.e., f(x + a) = y² The user can regard the perturbation recourse action for obtaining the desired outcome y" (32). For example, let consider situation where bank deploys a model f for predicting whether a loan applicant will repay the loan or default, and a user gets the loan application rejected. To help the user æ get the loan approved, AR suggests an action a that changes the prediction result of from "default" to "repayment."
To provide actions that executable for users, most of the existing studies AR focus post-hoc methods for extracting feasible actions with low costs from a learned model f [5] [1 [3] [9 27
29 39 45
48
57, 64] In general, however, such executable actions do not always exist when For example, in the above loan approval
is trained solely for predictive performance 36 55
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

scenario, users can not change their demographic features (e.g,, age or race) or features relating to past records (e.g., past bankruptcy). While users can change their education level, increasing it may be practically difficult due to the associated costs. If a learned model f heavily relies on such features, there is no guarantee for the existence of executable actions, and thus, the existing post-hoc methods often fail to extract them from f. As a result, it may be impossible for many affected individuals to flip an undesired decision to their desired one as long as f is deployed [56] 60).
To address the above issue, recent studies introduced a framework for learning a model f that ensures the existence of executable actions a for input instances æ with high probability [00 5TI. Specifically, Ross et al. [51] proposed gradient descent algorithm for learning deep neural networks. Kanamori et al. [30] proposed a top-down greedy learning algorithm designed for classification trees. These studies demonstrate that we can learn model f that guarantees the existence of executable actions without significantly degrading predictive accuracy and computational efficiency (55)
In this paper, we focus on the gradient boosted decision trees (GBDTs) [6]. such as XGBoost LightGBM [33], and CatBoost [47]. Due to their performance and scalability, they are recognized as one of the state-of-the-art models for tabular datasets 188 21 41) which often appear in the areas where AR is required (e.g., finance and justice) [6.. Contrary their popularity and importance, however, existing methods for learning models with recourse guarantee cannot be applied to GBDTs. Ross et al. [5T] assume that the loss function is differentiable with respect to the model parameters, which does not hold for tree-based models. The algorithm proposed by Kanamori et al. [30 is specifically tailored for classification trees and can not learn regression trees, which are used as base learners for GBDTTs. In addition, although there exists gradient boosting algorithms considering some additional constraints [00 [2 26 46 54 59 [55] such as robustness [ 63), they do not aim to ensure the existence of recourse actions. Therefore, we need to design a new gradient boosting algorithm that takes the existence of recourse actions into account.
Our contributions In this paper, we propose Recourse-Aware gradient Boosted dectsion Trees (RA- BIT), a new framework for learning tree ensemble models that make accurate predictions and guarantee recourse actions. Our contributions are summarized as follows:
We propose an efficient algorithm for learning tree ensembles by gradient boosting with the recourse loss (30 [5T] that encourages the existence of recourse actions. To handle the recourse loss in the modern framework of gradient boosting, we derive its upper bound to which the Taylor expansion our algorithm is equivalent to that of the standard gradient boosting algorithm.
be applied. We show that the computational complexity of
We introduce a post-pro post-processing task of modifying a learned tree ensemble model so as to satisfy the constraint recourse guarantee. We formulate our task a problem of refining the leaf weights of the trees in the ensemble, where we minimize the empirical risk under the constraint the recourse loss. We show that this problem can be solved efficiently and provide a PAC-style guarantee for the models refined by our post- possceroc.ss.ng..
We conducted numerical experiments on real datasets and demonstrated that our RABIT successfully provided executable recourse actions to more individuals than the baselines while keeping comparable predictive accuracy and computational efficiency. We also con- firmed that RABIT could attain better trade-off's between predictive accuracy and recourse guarantee than the baselines by combining our learning algorithm and post-processing
2 Problem statement
For positive integer n e N. we write [n] == {l,... n). As with the previous studies 330 51] we consider a binary classification task between undesired and desired classes. Note that our framework can be applied to a multiclass classification task if we can reduce it to a binary classification task between undesired and desired classes. Let X' C IR. and y {+1} be input and output domains, respectively. We assume that y = +1 is desirable class (e.g.. loan repayment). We call a vector (#1...., 2DD) E X' an instance, and a function f: X + R a predictive model that maps æ to a prediction score. We assume that a predictive model ʃ makes prediction ý E y according to =ssgn[] sg)(( Let y x R + Re be differentiable convex loss function. We assume that loss function satisfies lo (y, 9) S Iyy 9) for the 0-1 loss function loi (y, ù) = [y " < 0), and is non-increasing with respect to the value of y ÿ. These assumptions are satisfied by many major
2

---

loss functions, such as the binary cross-entropy loss. While these assumptions are required for our theoretical analyses, in practice, our learning algorithm works without these assumptions.
2.1 Algorithmic recourse
For an instance x E X, we define an action as a perturbation vector a E RD such that a + a E X. Let A(x) be set of feasible actions for such that 0 A(x) and A(x) C fa R x + E X). For model S. an action a is valid for æ if a E A(xx) and (g + a)) = +1. For æ E X and A(ar), a cost function c: A(æ) + R20 measures the required effort of a with respect to æ.
The aim of Algorithmic Recourse (AR) [58] is to find an action a that valid for æ with respect to f and minimizes its cost c(a æ). This task can be formulated follows [32]:
A(a) c(a x)
subject to sgn(f( + a)) =+1.
(1)
As with the existing studies 30 we assume that the cost function e satisfies the following
properties: (i) c(O x) = O; (ii) c(a x) max ca(aa Id), where is the cost of the action Pd for a feature d; (iii) ca(as Id)= S ca(as (1 + E) | xa) holds for any ε 2 0. Note that several major cost functions, including the weighted e -nomm [5]] and max percentile shift (58). satisfy the above properties. We also assume that set of feasible actions can be expressed as A(x)= = [4, u1] x
L,D Up] with lower and upper bounds L1 Ua E E for d E [D]. For example, while there exist some immutable features that can not be changed, such as age, race, and past bankruptcy, we can express them by setting la = ud O. Similarly, we can express a feature that is allowed to be only increased (e.g., education level) by setting La = 0 and uh > 0.
2.2 Tree ensemble and gradient boosting
sum of T regression trees fi,..., Jr: X R: that is, f(x) = Ei fz)). Each tree ft is a regressor that consists of set of if-then-else rules expressed as binary tree structure B. For a given input E X, it makes a prediction according to the weight value w of the leaf that x reaches. The corresponding leaf is determined by traversing the tree from the root, depending on whether the split condition za S b is true or not, where (d, b) [D) x R is pair of feature and threshold of each internal node. Let I, be the total number of leaves in ft, and We, E IR. be the leaf weight of leaf i E [7t]. respectively. Then, we can express regression tree fo as fz( = Σ Wt. (x), where (x.( [ rt,,] is the leaf indicator of i and re.s S X is the input region corresponding to i. Note that each region Tt.i is an axis-aligned rectangle and
A free ensemble model is expressed
determined by the split conditions on the path from the root to the leaf [5 20
Gradient boosting is one of the most popular frameworks for learning tree ensemble models [16] 18 41) For each round t [T') it learns a new regression tree fr that fits the pseudo residual corresponding to the loss I(y, (x)) the model F-- (z) = Σ (x) trained before round
t 9 40 Given a sample = ((xn: yn)) ) we consider the following optimization problem:
ft E argmin Σm
n=1 N(m, (x,) + f<(,))))
N
where F is a set of regression trees. For simplicity, we omit some popular techniques, such as regularization and learning rate 16. Note that our framework, proposed later, can handle them.
Because exactly solving the problem 2 is computationally challenging due to the combinatorial
nature of decision trees (23 24), existing methods employ a top-down greedy algorithm as with the
standard decision tree learning 3. Let us consider growing a regression tree J. by adding a new split condition (d, b) to leaf E [4] of fe. We assume a finite set of candidate thresholds Ba C R for each d E [D] such that Bal = O(N). Let (rre.) = (n E [N] In E rt,s} be the set of instances that reach and WL, WR IR be the leaf weights of the left and right children of i, respectively. Then, we consider the task of finding best parameters (d, b, Wt, Wn), which can be formulated as
(D) minwy,..w.E EmENTr... 1(yn, (xx) + h(x, d, b, WL, wR)),
(3)
where h(x;;; d, b, wt., wn. == wr TI (Ira S bj + wR II [ara b) is a decision stump with a split condition (d, b) and leaf weights wi,, wn. While the candidate split conditions (d, b) are finite and can be easily enumerated, we need to numerically optimize the leaf weights WL, WR for each (d, b).
3

---

To efficiently solve the problem modern implementations of the gradient boosted decision trees (GBDTs), such as XGBoost employ the second-orde Taylor expansion of the loss function
1. Here, we fix the split condition (d. and denote rt. = {ar E ft.i Zd S b) and I' == Ft.i \ rL. Let
C..6 wn) = EneV(rr, .) [Yyn ( + h(m:: d, b, wt, wn)) be the objective function of (3) By ignoring the constant term independent of wL and wa, we can approximate Pa,b as follows 77:
1 -RR -
(.db(wr, WR) Gt. wL + Hr wf GR. WR 2
where Gr. == EnEN(ry) By
& (Mr. 1) (g=P-1((..) (20n 1) (( and Hr, == EngN(r)) By
We define GR and HR in a similar way. We can compute the optimal leaf weights "i and w that minimizes the above approximated objective function by "n Thus, we can analytically obtain an approximate solution to the inner problem of (3) for each split condition (d. b). While naive computation of w and " requires ((V) time, we can compute them in amortized constant time if the instances Ti are sorted by un.d in advance [ 50 Thus, we can obtain an approximate solution to the problem (3) in O(N D). We grow the I-th regression tree St by recursively repeating this procedure until some conditions are met (e.g., maximum depth).
Gt, and wi = Gr respectively.
Hy
Ha
2.3 Problem formulation
To formulate our learning task, we introduce the recourse loss 30 51 For cost budget parameter
3 2 0, let Ag (a:) := {a E A(x) c(a a) I 3} be the set of feasible actions whose costs are lower
than equal to B. We define the recourse loss (2( f) of a model for an instance æ as follows:
la(x f) = minac f(x a))
We can regard lg relaxation of the validity constraint with cost budget B. By definition, it takes a small value if there exists a feasible action a E AA(x) such that sgn(f(æ + a)) = +1 and
c(a x) S B. Thus, minimizing Io encourages f to ensure valid action a with low cost 30
The aim of this paper to propose gradient boosting algorithm for learning tree ensemble model I while ensuring the existence of valid and low-cost recourse actions a for as many instances æ as possible. More precisely, we learn a tree ensemble model f(x) Σt= fz( that minimizes the weighted sum of the standard loss I and recourse loss 1z. Given a sample S = { yn) b learning task of each round t E [T] can be formulated as follows:
Σ n=1 (1 F + f((x,)) + (z( Fi-1 + fi),
ft E arg min
(4)
where 7 0 hyperparameter that controls the trade-off between the predictive accuracy and recourse guarantee. We can recover the standard unconstrained gradient boosting by setting 7 = O.
Recourse-aware gradient boosting
In this section, we propose an efficient algorithm for learning tree ensemble model while ensuring the existence of recourse actions for as many instances as possible. Following the modern frameworks of gradient boosting 7 33 47,, we learn each regression tree fe by recursively solving the problem (4) in a top-down greedy manner and leveraging the second-order Taylor expansion to obtain closed-form solution to the leaf weights wT,, WR. Let V. (z;; r) == II [a E As(æ))
E r] be the indicator whether æ can reach a region r by some action a E (z). Similar to the term La,b corresponding to the standard loss I, we define the term corresponding to the recourse loss Lg as follows:
(,L, WR) == -EnENs(r..) (0(
F + h(;; d, b, WL. wR)).
where Nr(rr.)) = (n E [N]
(ag(anire.)) 1) is the set of instances Dn that can reach the leaf i by some action a E (a Then, we consider the following optimization problem:
min.e(D))bbB. minwi,,nER (a,,ww,, wR) + V.,, (.,, wR).
(5)
main obstacle to solving the problem (5) is that we can not directly apply the second-order Taylor expansion to the term La,b due to the recourse loss lg. Hence, efficiently solving the inner problem of (5) not trivial in contrast to the standard case. To address this issue, we derive differentiable upper bound of Va.s. which enables us to use the second-order Taylor expansion when solving the problem (5). We also show that we can compute the approximate solution to the problem (5) in O(N- D) time, which is equivalent to the standard unconstrained gradient boosting algorithm.

---

3.1 Differentiable upper bound on recourse loss
First, we derive an upper bound on the term V d. that differentiable with respect the leaf weights wL and wR. In the following proposition, we show an upper bound on the recourse loss lg.
Proposition 1. For regression trees Ji.-.., E F, we define & (((r)) == Σt=l minaeAs(s) fa
a). Then, for any instance x E X and regression tree h E F, we have
L Fi-1 + minaeAp(=)) (r h(x ((x++a)) +a).
We give a proof of Proposition in Appendix A Note that (xx a lower bound on the prediction score of Fi-1 for x by some action (2(x), and we can compute each term of (x(x) in O M
Let (u(,,, WR; x) = A & + h( + a; d, b, WL, WR)) be the upper bound of Proposition for a decision stump (1; d, b, WT, WR). For any æ with up (2; T2,1) = 1, we have
[minwe (( (+11, (xr) + w) ((++1, wt. v7 + wn. un (ar) otherwise,
if (x)) = (2()) 1,
[o(WL, wRi
where uI (2)) == (g(); TL) and UR (x) = [g( By definition, (a( = 1 implies (x) + UR (x) 2 The case with (L)x) uR (2) = corresponds the situation where the instance x can reach both left and right children by some action a E A (z). and the other case corresponds to the situation where only one of them reachable. We can apply the Taylor expansion to the latter case, but not to the former, due to the minimum operator. To avoid this difficulty, we replace the minimum operator with the LogSumExp function follows:
2 1 In (e- (WL, wR; = [1++1, y
+ +-vv((++(GG(()tmm))) if un. (x:) vn (x:) = 1,
(x) + wi (L) + WR (x))
otherwise,
where v > 0 is some small constant that controls the approximation quality. By LogSumExp trick, we have (uT, wRa#) a) < [g (WT,, wR: æ)) Combining the above results, we define our surrogate function of the recourse loss by V (4,6(un (WL, WR) = (o a. Our surrogate function V..b satisfies (a,, wn) a,, wn) and is differentiable with respect wr. and wn by definition.
3.2 Analytical solution to leaf weights
Now, we consider the following problem where we replace the term aa of 5 with our surrogate v
min.e(D)).eBB, minwL..ReR (.,,(wr., wR) + + V..b (w., WR).
As with the modern gradient boosting algorithm 7 33 47), we obtain an approximate solution the inner problem of (6) by applying the second-order Taylor expansion to its objective function. For notational convenience, we divide the set of instances (r( into three disjoint subsets:
Nn (n Na(re,) (x.)))) 1, (x.,) 1}; (,())
Ni. = {n E Na(r,,) (x,(),) = 1, 1R (x,) = 0}.
NR. (n No(r,) (L(x.)) = 0, UR (x,,) 1}.
By ignoring constant terms, the second-order Taylor expansion of our surrogate term V.s is given by
a WL, wR) Gr wL + ! Hr wf + GR WR + 2 HR wît + HB wp wR. Here, each term is defined as follows:
1
GL Σ nEN, Ow
((+1,w) (n==g((m..) + + nENS Ow
isw (x( xn) I (m
02
Hr -E, E'EN,  1 ((ww) + + neAin dw is( (Ix.): xn) (nw))
82
An = EneN' Fwod
P Ja(w, (0)) ( ((o
5

---

We define GR and HR in similar way. By minimizing the second-order approximation of the objective function in the inner problem of ( we obtain an approximate solution as a closed-form:
" r. HH (GR + GR) - (HR + + HR) (G1. + .T.
(H1, v M1.) (HR + HR) - -2 Hf
wn- 7 AB. (G1. 7 G1.) (H1, 7 Hh.) (GR +y Gr)
(8)
(H1, +y H1.) (HR + HR) - 7² l1
As with the standard unconstrained case, naive computation of W and w requires (NV time due to each of the terms such as Gr. and Hr. However, we can compute them in amortized constant time by the same technique for classification trees proposed by Kanamori et al. 30). Proposition 2 shows that we can compute an approximate solution to the problem (5) in the same time complexity as the standard gradient boosting algorithm. We present our algorithm and proof in Appendix A
Proposition 2. There exists an algorithm that approximately solves the problem (5) in O(N D).
4 Recourse-aware leaf refinement
This section presents a post-processing approach for improving the recourse guarantee a learned tree ensemble model. While minimizing the recourse loss la encourages a model ensure the existence of recourse actions for instances in a training sample S, there is no guarantee that the model can ensure for unseen post-proot post-processing task, called leaf refinement [49] that modifies the leaf weights of a learned tree ensemble model f under the constraint on the recourse loss Ig. Then, we show that we can guarantee the existence of recourse actions for unseen test instances through PAC-style bound [4].. Note that our post procepsog method can be applied to any tree ensemble model, and does not require any assumptions on the cost function e and feasible action set A(x).
instances as well [5T]. To alleviate this issue, we introduce
4.1 Formulation and optimization
We introduce a post-processing task that refines the leaf weights of learned tree ensemble model under the constraint on the recourse loss (g. Let J = Σ Le be the total number of leaves in the ensemble. From the definition of tree ensemble models, can express given learned tree ensemble model f as a form of f()) Σ wy 6 49 Let a R. be vector of refined leaf weights, and we define a refined model by (x) = Σラ= aj (x)). Given sample S = {(x yn)) J formulate our task constrained empirical risk minimization problem [6] defined as follows:
min Σxe (y (xx,) subject to
Σ
La(#n fa) S S,
where 2 0 is a given parameter. Note that each leaf indicator Φ, is fixed here, and a model fa can be regarded linear model with respect to the binary representation vector (0) (x), (z()))
To make the constraint of the problem p tractable, we assume a deterministic oracle algorithm A that takes an instance æ and returns feasible action a E As((x) based on the learned model f. as with the previous study [5T]. Note that we can employ any existing algorithm for tree ensembles (e.g., 5 57)) and do not require the oracle to be optimal in the sense of the problem ① We also note that we can easily extend the setting where the oracle A returns multiple diverse actions 44]
Using the oracle algorithm Ağ, by definition, [s( fa) S [(+1,fa(x Az(x))) holds for any It implies that the recourse loss lg for is upper bounded by the standard loss for labeled instance (a + (z()), (), +1), which is tractable to be minimized. Based on this fact, we consider the following unconstrained problem instead of
min Σ
(ymn. fa (x.)) A >n fa + Az(#x))),
(10)
where À 2 0 is Lagrangian multiplier. There exists À such that the solution to the problem (10
satisfies N " [(+1, (x A)()x))) which implies that & -> fa) < holds

---

as well. Furthermore, the problem (T0) can be easily solved by any off- aff-the-shelf library since it can be regarded as a learning problem for linear model with the weighted empirical risk on the concatenated sample S S', where S' == {m + A (nn) +1)n),+)){a)
+ n=1- In nutshell, by iteratively solving the problem TTP and updating A, we can efficiently obtain a feasible solution to the problem (
4.2 PAC-style guarantee
Our leaf refinement approach enables to control the ratio that the refined model fa ensure actions for instances in S with a given parameter e. However, it is not guaranteed that the model Sa ensure actions for unseen test instances well. To analyze this risk, we show PAC-style bound on the estimation error of our surrogate risk R₂ (Ja ()
1(t,, (I, + Azxx))))
( + a)) & +1] be the expected recourse risk of f. Given a sample S = {(xn. yn)) refined tree ensemble model (a) - E}=1" 0g (x(x), and 5 > 0, the following inequality holds with probability at least 1 8:
Proposition 3. For model f: X + R, let R ) = Pz[va E Ag(x)) sf
8 In e N
Ro(fa) s Ro(fa SS)
N.N
We give our proof of Proposition 3 in Appendix From Proposition 3 we can probably obtain refined model fa that can guarantee the existence of actions for any instance with probability at least
1 e' by solving the problem (9), where g' = +
8 In
N +
In
2N
Experiments
To investigate the performance of our RABIT, conducted experiments on real datasets. All the code was implemented in Python 3.10 with Numba 0.61.0 and is available at huttps://githhe com/kel com/kelicht/rabit All the experiments
conducted macOS Sequoia with Apple M2 Ultra CPU and 128 GB memory. Our experimental evaluation aims to answer the following questions: (i) How are the predictive accuracy and recourse guarantee of tree ensembles learned by our RABIT compared to those by the baselines? (ii) Can our RABIT balance the trade-off between accuracy and recourse? (iii) Is our post-processing approach effective in improving the recourse guarantee of tree ensembles? Due to page limitations, the complete results are shown in Appendix C
Experimental settings We used four real benchmark datasets: FICO (N- 9871, D 23) [4] COMPAS (N = 6167, D = 14) [2]. Adult (N = 48842, D = 16) 34 and Bail (N 8923, D 16) [33 These datasets represent diverse real-world applications (finance, criminal justice, census, and bail prediction) that are widely used in the literature of algorithmic recourse (32) For each dataset, all the categorical features were one-hot encoded. To obtain an action a for each instance x by solving the problem (T). we employed the feature tweaking algorithm (57). which is a fast heuristic algorithm for tree ensemble models. Note that we also employed the exact method based on integer optimization [11 28), and its results are presented in Appendix
As cost function we used the max percentile shift (MPS) (88) defined as c(a x)) max D) Qa(aa + aa) Qa(aa)), where Qu is the cumulative distribution function of feature d. In addition, actionability constraints were imposed on certain features (e.g., gender), as shown Appendix C
To the best our knowledge, there is no existing method that can train GBDTs while guaranteeing the existence of actions. Following the previous studies 112 30), we compared our RABIT with two baselines: standard unconstrained learning (Vanilla) and learning with only actionable features (OAF).
5.1 Baseline comparison
First, we evaluate the performance of tree ensemble models learned by our RABIT in comparison with the baselines. We randomly split the dataset into the training and test sets with ratio of 75 25, and trained tree ensemble models by each method on the training set. For learned models, we measured (1) the accuracy on the test set, (2) the recourse ratio, which is defined as the ratio of the test instances that are guaranteed valid actions whose costs are less than 3 = 0.2, and (3) the running time for training. We repeated this procedure 10 times. For the baselines and our RABIT, we trained T 100
7

---

FICO Antunayy
COMPAS Ancurary
Adult Ammureyy
Bail Armuney
D.70
0.99
Accunsy
Accurccy
Accuracy
9.55
Aecuracy
0.7
0.84
0.88
9.83
0.70
BM9
0.86
Vanilio
OAP
RARET
Vanilla
OAF
RARET
Vanilla
OAF
RAIRF
Venills
QAP
RANIT
Acta's
0.8
Recomaee
Bocouuse
Decouree
9.3
0.90
Veniths
Figure 1: Experimental results baseline comparison with respect to the accuracy and the recourse ratio (higher is better). We observed that our RABIT attained higher recourse ratio than the baselines while keeping comparable accuracy on all the datasets.
Vanilla
OAF
RABIT
20
Time
10
FICO
COMPAS
Adult
Dail
Figure 2: Average running time [s] of each method (lower is better). There is no significant difference
between the baselines and our RABIT all the datasets.
regression trees with a maximum depth of 8 and learning rate 0.1. For RABIT, we set 0.002 and did not apply our leaf refinement post-processing.
Figure presents the results on the accuracy and recourse ratio. From Figure we observed that (i) RABIT attained comparable accuracy to the baselines, and (ii) RABIT achieved significantly higher recourse ratios than the baselines. Compared to Vanilla, while OAF attained slightly higher recourse ratio, it suffered from significant degradation in accuracy. One possible reason is that OAF restricted to using only actionable features, sacrificing predictive power by ignoring potentially highly predictive non-actionable features. On the other hand, our RABIT succeeded improving the recourse guarantee without significantly degrading the predictive performance. Figure shows shows the average running time for each dataset. We can see that there is no significant difference in the running time between the baselines and RABIT. These results indicate that our algorithm performed as fast as the standard learning algorithms, even though it additionally considers the recourse loss.
In summary, have confirmed that our RABIT succeeded in guaranteeing the existence of re- course actions for more instances than the baselines without compromising predictive accuracy and computational efficiency. Our findings show that RABIT improves the availability of executable recourse actions for individuals without sacrificing the predictive accuracy or computational efficiency of standard GBDTs. This makes RABIT a practical and reliable tool for decision- makiinn systems, enhancing transparency and user trust in weal-world applications.
automated
Recourse quality analyses To assess the quality of actions extracted from tree ensembles trained by our RABIT, we evaluate their cost, sparsity, and plausibility. To evaluate the plausibility, the previous studies often use the outlier score 9 of x + [19]. Following the previous study [45] we employed isolation forests (IF) [37] q. Table T shows the average cost c(a x), sparsity ||a||o and plausibility q( + a) of the obtained valid actions for test instances æ. We can see that RABIT
attained lower cost and sparsity than the baselines. We also observed that there is no remarkable difference plausibility between baselines and RABIT. From these results, we have confirmed that our method could provide executable recourse actions without harming their plausibility.

---

Table 1: Average cost, sparsity, and plausibility of extracted actions (lower is better). Our RABIT achieved lower costs and sparsity than the baselines while keeping comparable plausibility.
Cost (MPS)
Sparsity (fo-norm)
Plausibility (IF)
Dataset
Vanilla
OAF
RABIT
Vanilla
OAF
RABIT
Vanilla
OAF
RABIT
FICO
0.358
0.315
0.165
2.155
2.792
1.078
0.438
0.44
0.475
COMPAS
0.23
0.181
0.112
1.518
L.553
1.264
0.436
0.446
0.466
Adult
0.354
0.308
0.275
1.467
1.547
1.422
0.477
0.464
0.479
Bail
0.449
0.371
0.225
1.546
1.563
1.131
0.508
0.503
0.519
FIOG Aucunay
COMPAS- Arsuncy
Adull Ausunay
Accunayy
0.74
0.69
Accunary
0.73
Aucurnrry
0.54 Accuncy
0.70
0.72
0.65
0.68
0.7
0,002
0.004
0
1L004
TU022
0,004
0
0,004
Trade Pazumoter
Tode off Pummeeter
Tride off Forameter
Trade Paramitte
PICO Recourve
COMPAS Recousse
Adult Rocousse
Boil Recoumse
Recourse
0.5
0.95
Ricourse
0.50
0.4
0.6
0.85
0.3
0,001
0.04 Thadoooff Pimumeter
0.002
0.000
0,000
0,001
Trode Pizumoder
Tride-oft Parameter
Trado Parauuete
Vanilin
OAF
RADIT
Figure 3: Sensitivity analyses of the parameter y with respect to the accuracy and recourse ratio. We can see that the average recourse ratio (resp. accuracy) was improved 7 increased (resp. decreased).
5.2 Trade-off analysis
Next, we analyze the trade-off between the predictive accuracy and recourse guarantee of our RABIT by varying its trade-off parameter y. Under the same experimenta settings as in Section 5.1 we trained tree ensemble models by varying the trade-off parameter 7, and compared their average accuracy and recourse ratio to those of the baselines.
Figure 3 shows the average accuracy and recourse ratio for each y. We can see that the recourse ratio (resp. accuracy) was improved by increasing (resp. decreasing) 7 on almost all the datasets, which suggests that could balance their trade-off by tuning y. More precisely, began to outperform the baselines in terms of the recourse ratio without significantly degrading the accuracy around y 0.002 all the datasets. These results indicate that we have chance to attain a higher recourse ratio without compromising prediction performance if we can determine the appropriate value of 7. In summary, have confirmed that our method could obtain models that achieve a better recourse ratio than the baselines while keeping comparable accuracy by tuning ?/-
observed that RABIT
5.3 Efficacy of post-processing approach
Finally, we examine the efficacy of our leaf refinement approach for improving the recourse guarantee of tree ensemble models. We randomly split the dataset into the training, calibration, and test sets with a ratio of 50 25 : 25. After learning tree ensembles by each method on the training set, we applicd our leaf refinement approach to them with the calibration set. Instead of solving the problem (9) directly, we solved the problem (TO) for a fixed Lagrangian multiplier and repeated this procedure by varying X. We report the average accuracy and recourse ratio of the refined models over 10 trials. Note that the ablation study on our post- post-processiig approach is presented in Appendix C
Figure 4 presents the scatter plots of the average accuracy and recourse ratio for each A. We can see that, in the FICO and COMPAS datasets, RABIT dominated the baselines in terms of accuracy and recourse ratio. It indicates that the combination of our learning algorithm and post-processing approach performed the best on these datasets. On the other hand, in the Adult and Bail datasets, we observed that Vanilla and RABIT demonstrated comparable performance. For example, in the

---

FICO
COMPAS
Adult
Bail
1.0
1,000
1.0
0L073
0.9
Recnnne
0.9
0.000
Bemune
0.5
0.7
Vanilla
0.0
OAP
0.900
0.5
RABIT
0.875
0.5
01:03
0.70
0.63
0.46
0.07
6.75
0,50
0.55
0.55
0.00
0.85
0.70
Acturary
Ancumnyy
Accurary
Ancrney
Figure 4: Experimental results of the post-proesssing approach. In each figure, x-axis and y-axis stand for the average accuracy and the recourse ratio, respectively. Our RABIT attained better or comparable trade-offs between the accuracy and the recourse ratio than the baselines.
Adult dataset, they maintained the accuracy around 85% while improving the recourse ratio from roughly 40% to 80%, which are better results than those in Figure [ These results suggest that our post-processing approach was sometimes effective even for tree ensembles learned by existing standard algorithms. In summary, we have confirmed that our pest-processing approach succeeded in improving the recourse guarantee of free ensembles while maintaining their predictive accuracy.
6
Conclusion
This paper proposed a new framework of gradient boosted decision trees, named recourse-aware gradient boosted decision trees (RABIT), that can provide both accurate predictions and executable recourse actions. We proposed an efficient gradient boosting algorithm for learning tree ensemble models with the recourse loss that encourages the existence of recourse actions, and showed that its computational complexity is equivalent to that of the standard unconstrained algorithm. We also proposed post-processing approach that refines the leaf weights of learned tree ensemble model under the constraint on the recourse loss, and gave a PAC-style guarantee on the existence of recourse actions. Experimental results demonstrated that our RABIT succeeded in guaranteeing recourse actions for more individuals than the baselines while keeping comparable accuracy and efficiency.
Limitations and future work
There several directions to make our RABIT more practical. First, the computational efficiency of our algorithm relies on our assumption of the -type cost function c. For the tyye cost functions, we can easily decide whether the budget constraint violated or not by checking each feature independently. In general, such a property does not hold for other cost functions, including f or f2-type cost functions. However, we expect that algorithm can efficiently handle general cost functions by exploiting some heuristic strategies (c.g., changing 3 depending on the tree depth (63))
Second, deriving tight bound for recourse loss وا is important for future work. From Figure 3 we found that a slight emphasis on 1z. i.e., setting ? = 0.002, is sufficient to achieve substantial improvements in the recourse ratio without harming performance. It suggests that bound in Proposition [ is too conservative, and our method can be improved by developing a tighter bound.
Third, identifying when our post-processing method becomes effective is interesting for future work. In Figure and our ablation study in Appendix C we observed that the combination of our learning algorithm and post-processing method worked the best some datasets, while it was comparable to the combination of standard learning algorithms and our post-proccse post-processing method on other datasets. suggests that there exist situations where post-processing alone yields sufficient improvement in recourse guarantee. Such situations might be characterized by some specific properties datasets, such as the ratio of actionable features the percentage of categorical features. However, it is still challenging to identify a general cause of this phenomenon, and we leave as future work.
Finally, there is room for our implementation of RABIT to be more sophisticated. In particular, our RABIT has the potential to improve scalability, generalization performance, and stability by several techniques implemented in modern frameworks of gradient boosting, such as histogram- based learning 7 [3), stochastic sampling [17 25), and so on [35 38 Since these techniques are compatible with RABIT, it is worth investigating their efffcctiveness in our framework.
10

---

Acknowledgments
We wish to thank Yuichi Ike for making a number of valuable suggestions. We also thank the anonymous reviewers for their insightful comments. This work was supported in part by JST ACT-X JPMJAX23C6 and ISPS KAKENHI Grant-in-Aid for Early-Career Scientists 24K17465.
References
[1] M. Andriushchenko and M. Hein. Provably robust boosted decision stumps and trees against adversarial attacks. In Proceedings of the 33rd Anual Conference on Neural Information Processing Systems, pages 13017-13028, 2019.
[2] J. Angwin, J. Larson, S. Mattu, and L. Kirchner. Machine Bias. ProPublica, 2016.
[3] L. Breiman, J. H. Friedman, R. A. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, 1984.
[4] S. Calzavara, C. Lucchese, and G. Tolomei. Adversarial training of gradient-boosted decision trees. In Proceedings the 28th ACM International Conference Information and Knowledge Management, pages 2429 2432, 2019.
M. A. Cerreira-Perpiñaae and S. S. Hada. Very fast, approximate counterfactual explanations for decision forests. Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages 6935-6943, 2023.
[6] L. Chamon and A. Ribeiro. Probably approximately correct constrained learning. Proceedings of the 34th Anual Conference on Neural Information Processing Systems, pages 16722 16722, 2020.
[7] T. Chen and C. Guestrin. XGBoost: scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785-794, 2016.
[8] S. H. Cheon, A. Wernerfelt, S. Friedler, and B. Ustun. Feature responsiveness scores: Model-agnostic ex- planations for recourse. In Proceedings of the 13th International Conference on Learning Representations. 2025.
[9] C. Cortes, M. Mohri, and D. Storcheus. Regularized gradient boosting. In Proceedings of the 33rd Anual Conference Neural Information Processing Systems, pages 5449-5458, 2019.
[10] A. Cruz, C. G. Belém, J. Bravo, P. Saleiro, and P. Bizarro. FairGBM: Gradient boosting with fairness constraints. Proceedings of the 1t International Conference on Learning Representations, 2023.
[11] Z. Cui, W. Chen, Y. He, and Y. Chen. Optimal action extraction for random forests and boosted trees. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 179 188, 2015.
[12] R. Dominguez-Olmedo A. H. Karimi, and B. Schölkopf. On the adversarial robustness of causal al- gorithmic recourse. In Proceedings of the 39th International Conference on Machine Learning, pages 5324-5342, 2022.
[13] S. Dutta, J. Long. S. Mishra, C. Tilli, and D. Magazzeni, Robust counterfactual explanations for tree-based ensembles. In Proceedings of the 39th International Conference on Machine Learning, pages 5742-5756, 2022.
[14] FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berkeley. Explainable Machine Learning Challenge, 2018. Accessed: 2025-05-15. 15.
[15] A. A. Freitas. Comprehensible classification models: A position paper. ACM SIGKDD Explorations Newsletter, 15(1):1-10, 2014.
[16] H. Friedman. Greedy function approximation: gradient boosting machine. Annals of Statistics. 29:1189 1232, 2000.
[17] H. Fricdman. Stochastic gradient boosting. Computational Statistics & Data Analysis, 38(4):367-378, 2002.
[18] L. Grinsztajn, E. Oyallon, and G. Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? In Proceedings of the 36th Anual Conference on Neural Information Processing Systems, pages 520, 2022.

---

[19] R. Guidotti. Counterfactual explanations and how to find them: literature review and benchmarking. Data Mining and Knowledge Discovery, 38:2770-2824, 2022.
[20] R. Guidotti, A. Monreale. S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi. A survey of methods for explaining black box models. ACM Computing Surveys, 51(5):1-422 2018.
[21] D. Holzmüller, L. Grinsztajn, and I. Steinwart. Better by default: Strong pre-tuned MLPs and boosted trees tabular data. In Proceedings of the 37th Anual Conference on Neural Information Processing Systems, pages 26577-26658, 2024.
[22] H. Hsu, Brugere, S. Sharma, F. Lecue, and C.-F. Chen. Rashomongb: Analyzing the rashomon effect and mitigating predictive multiplicity in gradient boosting. In Proceedings of the 37th Anual Conference on Neural Information Processing Systems, pages
2024.
[23] X. Hu, Rudin, and M. Seltzer. Optimal sparse decision trees. Proceedings of the 32nd Anual Conference on Neural Information Processing Systems, pages 7265-7273, 2019.
[24] L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1):15-77, 1976.
[25] B. Ibragimov and G. Gusev. Minimal variance sampling in stochastic gradient boosting. In Proceedings of the 33rd Anual Conference on Neural Information Processing Systems, pages 15087-15097, 2019.
[26] L. Iosipoi and A. Vakhrushev. Sketchhoost: fast gradient hoosted decision tree for multioutput problems. In Proceedings of the 36th Anual Conference on Neural Information Processing Systems, pages 25422-25435, 2022.
[27] K. Kanamori, K. Kobayashi. Hara, and Takagi. Algorithmii recourse for long-term improvement. In Proceedings of the 42nd International Conference on Machine Learning, pages 28849-28877, 2025.
[28] K. Kanamori, T. Takagi, K. Kobayashi, and H. Arimura. DACE: Distrihution-awan counterfactual explanation by mixed-integer linear optimization. In Proceedings of the 29th Interaaiinna Joint Conference on Artificial Intelligence, pages 1855-28622 2020.
[29] K. Kanamori, T. Takagi, K. Kobayashi, and Y. lke. Counterfactual explanation trees: Transparent and consistent actionable recourse with decision trees. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pages 1846 1870, 2022.
[30] K. Kanamori, T. Takagi. K. Kobayashi, and Y. lke. Learning decision trees and forests with algorithmic recourse. In Proceedings of the 41st International Conference on Machine Learning, pages 2024.
[31] R. Kanoh and M. Sugiyama. Neural tangent kernels for axis-aligned tree ensembles. In Proceedings of the 4lst International Conference on Machine Learning, pages 23058-23088 2024.
[32] A.HH. Karimi, G. Barthe, B. Schölkopf, and Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. ACM Computing Surveys, 55(5):1-29, 2022.
[33] G. Ke, Q. Meng. T. Finlcy, T. Wang, W. Chen, W. Ma, Q Ye, and T.-Y. Liu. LightGBM: A highly efficient gradient boosting decision tree. Proceedings of the 31st Anual Conference on Neural Information Processing Systems, pages 3149-3157, 2017.
[34] M. Kelly, R. Longjohn, and K. Nottingham. The UCI machine learning repository. htttp:://archi ics. uci.edu Accessed: 2025-05-15.
[35] R. Korlakai Vinayak and Gilad-Bachrach. DART: Dropouts meet Multiple Additive Regression Trees. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, pages 489-497, 2015.
[36] A. Kothari, B. Kulynych, T.W.. Weng, and B. Ustun. Prediction without preclusion: Recourse verification with reachable sets. In Proceedings of the 12th International Conference on Learning Representations, 2024.
[37] F. T. Liu, K. M. Ting, and Z.-H. Zhou, Isolation forest. In Proceedings of the 2008 IEEE International Conference on Data Mining, pages 413-422, 2008
[38] H. Lu, S. P. Karimireddy, N. Ponomareva, and V. Mirrokni. Accelerating gradient boosting machines. In
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 516-526 2020.
12

---

[39] A. Lucic. H. Oosterhuis, H. Haned, and M. de Rijke. FOCUS: Flexible optimizable counterfactual explanations for tree ensembles. In Proceedings of the 36th AAAI Conference on Artificial Intelligence. pages 5313-5322, 2022.
[40] L. Mason, J. Baxter, P. Bardett, and M. Frean. Boosting algorithmms as gradient descent. In Proceedings of the 13th Anual Conference on Neural Information Processing Systems, pages 512-518. 1999.
[41] D. McElfresh, S. Khandagale, J. Valverde, V. C.,, G. Ramakrishnan, M. Goldblum, and C. White. When do neural nets outperform boosted trees on tabular data? In Proceedings of the 37th Anual Conference on Neural Information Processing Systems, pages 76336-76369 2023.
[42] T. Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence. 267:1-38, 2019.
[43] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
[44] R. K. Mothilal, A. Sharma, and C. Tan. Explaining machine learning classifiers through diverse counterfac- tual explanations. Proceedings of the 2020 Conference on Fairness, Accountability, and Transpurency, pages 607-617, 2020.
[45] A. Parmentier and Vidal. Optimal counterfactual explanations in tree ensembles. In Proceedings of the 38th International Conference on Machine Learning, pages 8422-8431, 2021.
[46] S. Peter, F. Diego, F. A. Hamprecht, and B. Nadler. Cost efficient gradient boosting. In Proceedings of the st Anual Conference on Neural Information Processing Systems, pages 1550-1560, 2017.
[47] L. Prokhorenkova, G. Gusev, A. Vorobev, A. V. Dorogush, and A. Gulin, CatBoost: unbiased boosting with categorical fcatures. In Proceedings of the 32nd Anual Conference on Neural Information Processing Systems, pages 6639-6649, 2018.
[48] K. Rawal and H. Lakkaraju. Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses. In Proceedings of the 34th Anual Conference on Neural Information Processing Systems, pages 12187-12198, 2020.
[49] S. Ren, X. Cao, Y. Wei, and J. Sun. Global refinement of random forest, In Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition, pages 723-730, 2015.
[50] L. Rokach and O. Maimon. Top-down induction of decision trees classifiers survey. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 35(4):476-487, 2005
[51] A. Ross, H. Lakkaraju, and O. Bastani. Learning models for actionable recourse. In Proceedings of the 35th Anual Conference on Neural Information Processing Systems, pages 18734-18746, 2021.
[52] C. Rudin. Stop explaining black box machine Icarning models for high stakes decisions and use interpretable models instcad. Nature Machine Intelligence, 1:206-211 2256 2019.
[53] P. Schmidd and A. D. Witte. Predicting recidivism in north carolina, 1978 and 1980. Inter-university Consortium for Political and Social Research,, 1988.
[54] Y. Shi, G. Ke, Z. Chen, S. Zheng, and T.-Y. Y. Liu. Quantized training of gradient boosting decision trees. In Proceedings of the 36th Anual Conference on Neural Information Processing Systems, pages 18822- -18333, 2022.
[55] K. Sokol and E. Hüllermeier. All you need for counterfactual explainability is principled and reliable estimate of aleatoric and epistemic uncertainty. arXiv, arXiv:2502. 17007, 2025.
[56] E. Sullivan and P. Verreault-Julic From explanation to recommendation: Ethical standards for algorithmic recourse. In Proceedings of the 2022 AAAI/ACM Conference on AI, Ethics, and Society, pages 712-722. 2022.
[57] G. Tolomei, F. Silvestri, A. Haines, and M. Lalmas. Interpretable predictions of based ensembles via actionable feature tweaking. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 465-474, 2017.
[58] B. Ustun, A. Spangher, and Y. Liu, Actionable recourse in linear classification. In Proceedings of the 2019 Conference on Fairness, Accountability, and Transparency, pages 10-19, 2019.
[59] A. Vargo, F. Zhang, M. Yurochkin, and Y. Sun. Individually fair gradient boosting. In Proceedings of the 9th International Conference Learning Representations, 2021.
13

---

[60] S. Venkatasubrammaiian and M. Alfano. The philosophical basis of algorithmic recourse. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 284-293, 2020.
[61] S. Verma, Boonsanong. Hoang, K. E. Hines, P. Dickerson, and C. Shah. Counterfactual explanations and algorithmic recourses for machine learning: A review. arXiv, (xii:20010,105990 2020.
[62] S. Wachter, B. Mittelstadt, and C. Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvord Journal of Law & Technology. 31:841-887, 2018.
[63] Y. Wang, H. Zhang, H. Chen, D. Boning, and C.-. Hsieh. On Ip-norm robustness of ensemble decision stumps and trees. In Proceedings of the 37th International Conference on Machine Learning, pages 10104-10114, 2020.
[64] S. Yamao, K. Kobayashi, K. Kanamori, Takagi, Y. lke, and Nakata. cerribution-alinndn sequential counterfactual explanation with local outlier factor. In Proceedings of the 21st Pacific Rim International Conference on Artificial Intelligence, pages 243-256, 2024.
[65] F. Yang. Le Bodic, M. Kamp, and M. Boley. Orthogonal gradient boosting for simpler additive rule ensembles. In Proceedings the 27th International Conference on Artificial Intelligence and Statistics. pages 1117-1125, 2024.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the abstract and Section 1
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the last paragraph of Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
14

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: See Sections to 4 and Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Section 5 and Appendices B to
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
15

---

reproducible, they While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
We provide our code and data in our GitHub repository at hthttps: /tap::///ithuut gight......... homm/elichh/rabii
Justification: See Section S and Appendix D
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
iiy))) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
/ //nips httpsecccpbbllccuuiccccocc htt/g/dddde/ooeSuummimmm www.sSuummsssooooooooooo
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: See Section 5 and Appendices and
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail
that is necessary to appreciate the results and make sense of them.
16

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: All averages in figures are reported with confidence intervals. The standard deviations of Tiile shown in Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section and Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics aattps://neuri: cttp:///bbce/eeicccc...eleelllll
Answer: [Yes]
Justification: We have read the ethics guidelines and surely confirmed that our paper accords with them.
Guidelines:
17

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., dep.oymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
18

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppppppashtaeea thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
See beclttp://ggttuubb.cc///llllll/s
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
19

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method of this paper does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy http:::/eearripsccc/ooofeeeeeeee for what should or should not be described.
20

---

A Omitted proofs
A.1 Proof of Proposition) 1
To prove Proposition] sum of two functions.
I
we first show a lemma that provides a lower bound on the maximum of the
Lemma 1. For any functions 91 and ga defined on a finite set X, the following inequality holds:
max (g)(x) =2(x)) 2 minzex 91 (x) maxxex 92(æ)).
Proof. Let x² = arg m (2(x). From the property of the maximum operator, we have
maxxex (91 (1:) + 92(x)) 2 91 (x) g2(x*). Since gn (xx) 2 x91 (x) and 92(x²) max (2 hold by definition, we have (1(x)) + 92(x") 2 mingex0: (x) max which concludes the proof.
Using Lemma we give proof of Proposition as follows.
Proof of Proposition Recall that the loss function I(y, () is non-increasing with respect to ý when y = +1. That is, 1(+1, () _ I(+1, 8') holds if ÿ 2 ÿ/. Combining Lemma with this fact, we have 1g(2 Fe-1 + h) mi 1(+1, Ft + a) + h(x + a))
((+1, max Ft-1 a) h(
+ a))
< ((+1, minae
Fi-1 a) + max h(x +
From the definition of F we have minneA.(m) F. a) > 2 Am (ax)). Thus, have
ls( Fi-1 + h) s 1(+11111100 Ap (x + a) + maxneAp(1) h(x +
$ [+++1 Σ ==1 m fa( + a) + max h(x + +a)
+ ((x h(x + +a))
4m(1 ((+1,E1(z) + h(x + a)),
which concludes the proof.
A.2 Proof of Proposition]
We present our algorithm for approximately solving the problem (5 in Algorithm In addition to the subset of sample A(rr..) and trade-off parameter 7, our algorithm takes the following inputs:
Algorithm
1. set of candidate thresholds Ba [bd,1, dd,M,) such that ba, S ba, and
Bal = -ON for each feature E [D];
2. permutation aa such that (1).
z (N) for each d [D]
3. gradient and hessian statistics for each n E (rr,)) defined follows:
θ (ynn ú) (Z=Fi-((a)) hn 0ÿ
0²
In 0y
(yon, (Z=f)-((a.))
0
8²
In.
1(+1, () (g-E)(m)))
h = Dzz
1(+ 1(+1, ()-S((m.))
og
(11)
0
0 Tolw, (i(x)) (mm))
In dw
l (w (xx wn (mm))(m))) hn ow
h fwdw (w, w/: x.) ( (w=
4. indicator values o (d, b) and on (d, b) for each N(rr,)) d [D], and b Ba, which are defined as follows:
on (d, b) = I imin (m.))) S - Ina], bd(d (a > x xn.d
(12)
21

---

Algorithm Algorithm for approximately solving the problem (
1: G ++ EneN(r On' H + EneN(r hai G t EnEN(TOw In: H t- EneN(rus) Mni
2: for d 1,2....... do
3:
A Initialize each term */
4:
Hr, GL, HI, HB < 0, 0,0,0,0,0; GR, HR. GR. HR m, m,, mR + 1; n,, Ri,, nR + oa(m), oall))))
G. G,H,G,H,
5:
6: for b E Bg do
7:
1 Update terms corresponding to the standard loss #/ while In.d and m S N do
8:
9:
GL. GR. HL, HR + GL + In. GR In: HL + has HR - hns m E + 1; am(m):
11:
end while
1" Update terms corresponding the recourse loss 18 while on, (d. and my S N do
13:
14:
GL,Hi t GL + Hmz Inz, Hy + hmn. hnz fB HB hngi
16:
m. m,,
ml, + 1; t oa(m)))
end while
18:
while Onn (d, = 0 and mR S N do
19:
Gr. HR GR- Inn InR. HR hina + hnai
20:
HB Hn hnni
21:
mR < mn. + 1; nn +- oa(ma):
22:
end while
23:
1* Compute leaf weights and approximate loss */
Compute leaf weights wr,dd
(d, b) and wR (d, b) by (7):
25:
Compute approximate objective value loss(d, b, wt (d, 6), wR (d) by (13
end for
27: end for
1* Find the best parameters */
29: d=, + arg (D).ee(D). loss(d, b, wi wi(d, b), wx(d,
30: "L, WR <- wL(d", (d", (R(d", b²);
return d", 6", w[, wii
Note that while we need to compute these inputs in advance, it roughly takes most O(D N2) and we only need to compute them once as pre-processing before growing trees [30]
In the following, give proof of Proposition
Proof of Proposition 2 To prove Proposition 2 we first prove that Algorithm computes an approx- imate solution to the problem ()) and then, we show that it runs in O(D N time.
Correctness We first show that Algorithm I returns split condition (d, b) and leaf weights wn. that minimize our approximate objective function of the problem (5) by the same technique proposed by [3). By applying the second-orde Taylor expansion to our surrogate objective function in (6). we obtain our approximate objective function as follows:
1
loss(d, b, Wr, wR) (G. + Gr.) Wt 2 (H₁, + + H1.) wf,
(13)
+ (Gn + GR) wn + 2 (HR + Hn) w + HB W1.
For fixed split condition (d, b), we can compute the optimal leaf weights that minimize 13 by taking the derivatives of (13) with respect to wi and and setting it to zero, which yields our closed-form solution shown in (7) of the main paper. Since candidate features E [D] and thresholds i E B2 are finite, we can obtain the optimal split condition (d, and leaf weights wt., wn that minimize (13) by enumerating all the possible split conditions, computing their optimal leaf weights, and comparing their objective values loss(d. (d, b, WL, WR). Thus, in the following, prove
22

---

that Algorithm ! exaccty computes each term in (3) for each split condition (d, b). For that purpose, we show that we can compute the terms GL, HI, HB for split condition (d, bm) using those for the previous split condition (d, bm-1), which we denote GR, Hi, HB- For notational simplicity, assume (rrr,)) = [N] and Ii,d < ... < INaa without loss of generality. Recall that (z Tt,a) = 1 have (I,)
(z rt.)) on,d, bm)) on (d, bm) and Un (T,,, = Fg ( r on (d(d, bm) = on bm) by definition. In addition, we can see the two monotonic properties
holds for any E [M] and thus,
n. [N] and m E [Ma]: on (n, bm) On' (m) for any n' > and (n.d. bm)) 2 on ) for any m' < m. While the former implies that On (d, dm) = -
(d, bm) 0 holds for any n' n, the latter implies that on (cl, d,n) 1 = On (d,bmr)
1 holds for any m' > m. Let k = mi (d.bbmd)))))))))mm 10-= and k' = (d..
Combining the above properties and the definitions of GL, HL, HB, have
G1. G _
n= In Σ In
GL = G Σ n=k (0n In);
m=k
HL HH, = nuhh hn Σ k''
hn
= Hr = Hi, + E m (hn hn),
n=k
MB ii
hm il-= il's E hn
Because the similar monotonic properties hold for on, we can compute On and HR. in the same way. Note that GL, Hr, GR, HR can also be computed in a similar manner, shown in (7]. Algorithm | updates each term of (13) in lines 22 using these facts. To conclude, we can see that Algorithm correctly computes the leaf weights for each split condition, and thus, it returns the optimal sphit condition (d, b) and leaf weights wt. WR that minimize our surrogate objective function.
Complexity
We now show that Algorithm runs in O(D .N) time. Our complexity analysis of Algorithm| can be divided into the following four parts:
In line I Algorithm I iniitializes the terms in ((N).
In the for-loop of lines 26 each while-loop runs at most N times through the for-loop of fixed Ba- In addition, can compute leaf weights ut., wn and their objective value in constant time. Since we assume |Bal = O(N), the overall complexity is O(N).
Since the inner for-loop of lines 6 26 takes O(N), the outer for-loop of lines O(D .).
27 takes
The optimization task in line 29 can be solved in O(D- .N) because the objective value of each (d. b) has been computed in lines 27
In summary, the overall complexity of Algorithm is O(D - N), which concludes the proof.
A.3 Proof of Proposition
To prove Proposition 3
we first show two lemmas. Our first lemma is a Rademacher complexity bound for the expected recourse risk Rf)
Lemma 2. For model class F, let ((F) be the Rademacher complexity of F. Then, any f E F and 6 > O, the following inequality holds with probability at least 1 8:
In
Ra(f) < R2 (1)))))++(()))))))))))))))))))))
2. N
where Ro(f(S) = + Az(x)))
Proof. Let D be a distribution over the input domain X'. By the definition of the expected recourse risk Rg we have
R₂( PALD Va As(æ) sgu(s(# + a)) + +1]
= EgED [ [Va E As(x) sgn(f(# + a)) + +1]]
EEND [minaeAA(a)) lo1 (+1, a))]
23

---

From our assumptions on the oracle A3. we have (a + a)) I (,,, Az(m))) for any X. Thus, we have (f( S (=1, + (3(x)))) By applying the Rademacher complexity bound 43 we have
Eg (loi (+1 A3(x)))] 1 E loi (+1, Ab(a:))) ((F) |
in 1
8
2
with probability at least 8. Combining these inequalities, the following inequality holds with probability least 1 6:
Rs(f) S Dlwwllor(+1,, f(x +
Σ n=1 (11, + A3(x))) + 2(F) +
In z 2. N (o(fl)+2000
In 3 2 N
which concludes the proof.
In our second lemma, we show that the Rademacher complexity of the refined model fa is equivalent that of the leaf indicator functions 6, we normalize the weight vector a.
Lemma 3.
Let { O53 and F = {fa ||al|1 S 1}, where fa(x) E3= oj (z)
Then, we have S(F) = (2(1)).
Proof. Recall that the Rademacher complexity (2FF) of a model class F is defined as (2FF) =
Es, (supfeF & En= on [(x))
43 Thus, we have
((F) = Es,a
1 L
On fa(an)
f
N
on E aj ()()))
Es.a
SUPaER<:lalliS1
N
n=1
Oj E Ene
Es.o
SUPaER/:JalisS]
on (0((n))
N j= j=1
n=1
N
Es.a
maxje(J]
n=1 kz(
N
Es.a
suP
Σ
On
((xn)
= -((()).
N n=1
where the fourth equality holds by the property of the dual norm 43
Using Lemmas and
we give proof of Proposition follows.
Proof of Proposition from Lemmas
For any E R. let ā [|a]]] a. Since ||ā|| 1, fa F holds. Thus,
2 and we have
In 1
Ro(fa) Ro(fa () + Q(H) +
2- N
with probability at least - 8. Recall that o, H is defined (x = [ ry] with axis- aligned rectangle C X. Hence, the VC dimension H. is and its Rademacher complexity
bounded by 2(H) S / /s-In aN
In addition, since fa(x) = ||l] fa (x) holds, we have sg)(fa(#)) = sgn(fa (x)), which implies loi (+1, fa + Ab(x))) = (1,, fa (x + A}(x))). Thus, Re(Sa) = RR(Sa) and Ro(Sa 5) = Ro(Sa 5) holds. Finally, recall that loı (+1, Az(x))) < 1(++1 + A}(x))) holds from assumption the loss function (. Therefore,
N

---

Algorithm 2 Actionable feature tweaking algorithm for approximately solving the problem T
1: a' t- 0: c² &- oo;
2: 1* Enumerate all leaves in ensemble "/
3: for t =
do
4: for = 1, 1.......,44 do
5:
/* Optimize action for leaf */
6:
à +- arg A(æ)) c(a at) s.t. a: + a E raji
7:
1* Check if the action is better */
8:
a)) = +1 and c(à æ)) < e² then if sgn(
9:
a' e* t c(à x);
10: end if
end for
12: end for
return a::
have R,3 |S] S Ra(Sa () by definition. To summarize, the following inequality holds with probability least 1 ò:
= = Rs(fa)
In h
S Ro |S) +))+((H))) +
2
8n eNN
In
s Rolfa 5
N
2 N
8 In EN
In
= Ralsa 15++1
+
N
2 N
8.
In 1
S Ro S)+
4
+
N
2. N
which concludes the proof.
B
Implementation Details
B.1 Baseline methods
Vanilla. To the best of our knowledge, there is no study learning tree ensemble models by gradient boosting while guaranteeing the existence of recourse actions. Thus, as baseline approaches, employed standard unconstrained gradient boosting methods, which we refer to as Vanilla. Note that it can implemented by simply setting 7 0.0 in our RABIT.
Only actionable features (OAF). As another baseline, employed modified version of Vanilla, named only actionable features (OAF), that uses only features that can be changed by actions. Note that such baseline employed by the previous studies well [12] 33]. Its idea is based the observation of the existing study that relying on actionable features facilitates the existence of
actions [12]. Our setting of actionability of the features each dataset is shown Tables to
B.2 Actionable feature tweaking algorithm
To extract actions from tree ensemble models f(x)= f(()) by solving the problem ① we
employed actionable feature tweaking algorithm [57] which is fast heuristic method. Algorithm presents a pseudo-code of the actionable feature tweaking algorithm. Algorithm consists of following three steps: (i) for each tree f. in the ensemble, enumerating all the leaves E [7.]: (ii) computing an optimal action to the region rt, corresponding to the leaf i; (iii) finding the minimum cost action a among ones altering the prediction results of f into the desired class (i.c.,
25

---

sgu(f(æ + a)) +1). Note that we can easily compute an optimal action à = (a1...., to
[ Up) as Od median(2 Las u.d) z for d E [D] 5 63 Our implementation is parallelized and runs faster than the existing public ones.
un) an instance and region [,,u,) x
C Complete experimental results
We present the complete results of our experiments. Tables 2 to present the details on the value type, minimum value, maximum value, immutability, and constraint of each feature of the datasets that we used our experiments.
C.1 Additional experimental results of baseline comparison
Figure presents the experimental results of our baseline comparison with respect to the area under the ROC curve (AUC) and FI score. As with the results with respect to the accuracy, we observed that RABIT achieved comparable AUC and Fl score to the baselines. Table/sshows the average cost, sparsity, and plausibility of extracted actions with their standard deviations.
C.2 Sensitivity analysis of hy hyperparameters
Number of trees T Figure 6 presents the experimental results of our baseline comparison with different numbers of trees T. We varied T from 50 to 250 with a step size of 50, and measured the average accuracy and recourse ratio for each T. We can see that RABIT attained higher recourse ratios than the baselines while keeping comparable accuracy regardless of the number of trees
presents the sensitivity analysis of the cost budget B. We varied 3 from 0.1 to 0.5 with a step size of 0.1, and measured the average accuracy and recourse ratio for each B. We can see that RABIT stably attained comparable accuracy to the baselines regardless of the cost budget B. We also observed that RABIT achieved higher recourse ratios than the baselines for almost all B.
Cost budget Figure 7
C.3 Efficacy of intercept adjustment
By transforming learned tree ensemble f into a probabilistic forecaster go(x)) I+e-Zonre with an intercept 0 E I. can directly apply the existing poot-procsssing method that adjusts the intercept 0 through a PAC-style guarantee [51]. J. To investigate the efficacy of the existing intercept adjustment, applied it the baselines and RABIT and measured the accuracy and recourse ratio of the adjusted models.
Figure 8 presents the results, where we fixed å = 0.05 and varying from 0.05 to 0.5 with step size of 0.05. We can see that while the recourse ratios of all the methods could be controlled by the parameter RABIT succeeded in maintaining the best accuracy for almost all the situations. However, compared to our leaf refinement approach, the intercept adjustment approach tended to drop the accuracy significantly when is small. For the example on the Adult dataset, the accuracies of the intercept adjustment approach were less than 50% when g < 0.1, while those of our leaf refinement approach were more than 80% as shown in Figure 4 These results suggest that the intercept adjustment approach effective in controlling the recourse ratio, but it is not as effective as leaf refinement approach in terms of accuracy.
C.4
Impact on model brittleness
We examine the impact of method the model brittleness, i.e., the sensitivity of the model to small perturbations of the input data. Following the previous work [51]. we add i.i.d. Gaussian noises test instances and measure the ratio of instances whose predictions change. For each instance, we generate 100 perturbed instances by adding da ~ (0, 03) for each actionable feature d, where of is the variance of d.
Table 7 presents the results of the average model brittleness of each method. We can see that there is no significant difference the model brittleness between RABIT and the baselines, which suggests that our method does not significantly affect the model brittleness.
26

---

C,5 Comparison using Exact AR Algorithm based on Integer Optimization
To investigate whether an action extraction algorithm affects the results, we also employed the exact AR method based on integer optimization [11
28 to extract actions from tree ensembles trained by
each method. As with our experiment of Section 5.1 we extracted actions for test instances predicted as the undesired class in each trial, and measured the average cost of the extracted actions. We used PYSCIPOpt 5.5.0, which is Python wrapper of SCIF one of the fastest open- open-source mathematical programming solvers. Due to computational cost, randomly picked 30 test instances in each fold, and a 60 second time limit was imposed on optimizing an action for each instance.
Table 8 presents the average cost of the extracted actions. As with our results using the heuristic algorithm shown in Section [.1] we can see that our RABIT achieved lower cost than the baselines regardless of the datasets.
C.6 Ablation Study on Leaf Refinement
To investigate the efficacy of our learning algorithm and leaf refinement approach, we conducted its ablation study that compares Vanilla and RABIT with Vanilla with leaf refinement (Vanilla w/ Refinement) and RABIT with leaf refinement (RABIT w/ Refinement). Note that there are two main evaluation metrics (i.e., accuracy and recourse ratio) and the parameter À of our post-hoe refinement affects these metrics. To make the comparison easier to understand, for each method and dataset, we selected the value of that attained the closest accuracy that of RABIT.
Table/9 the average accuracy and recourse ratio of each method. We can see that the accuracy gaps between methods were at most 2.7%, 0.6%. 0.3%, and 1.0% on FICO, COMPAS, Adult, and Bail datasets, respectively. It indicates that all the methods attained comparable accuracy in each dataset. In addition, observed that RABIT w/ Refinement performed the best, and that RABIT and Vanilla w/ Refinement performed better than Vanilla. Furthermore, we also observed that while RABIT outperformed Vanilla w/ Refinement in FICO and COMPAS datasets, Vanilla w/ Refinement outperformed RABIT in Adult and Bail datasets. These results indicate that our learning algorithm and post-hoc refinement effectice individually, and their combination can achieve better results.
D Additional Comments on Existing Assets
Numba 0.61. is publicly available under the BSD-2- license. PySCIPOpt 5.5.0 is publicly available under the MIT license. All the scripts and datasets used in our experiments are available in our GitHub repository at htttps://githhut com kon//keiicht/rabt]
All the datasets used in Section publicly available and do not contain any identifiable information or offensive content. As they are accompanied by appropriate citations in the main body, see the corresponding references for more details.
E Discussion on potential societal impacts
Our proposed method, named RABIT, a new framework that aims to learn accurate tree ensemble models while guaranteeing the existence of recourse actions. As demonstrated in our experiments, tree ensembles trained by our method can provide executable actions to more individuals than the existing baselines without degrading accuracy. Thus, our method enables to learn predictive models that make accurate predictions and guarantee recourse actions. improves the trustworthiness of algorithmic pocissoo-mmainn for critical tasks in the real world, such loan approvals and judicial decisions (3 58).
On the other hand, our framework also has potential societal impacts that need careful consideration. In practice, it may not always be necessary for decision-makers to guarantee the existence of executable actions for all individuals. For example, providing easy actions for granting loans to applicants who not have sufficient capacity repay might cause a serious financial crisis in the
https://www.ccippt org
org/
https://pyscipopt.rrr htw.::ccppppprrraatttoooooos.ooo
27

---

future. However, since our method can adjust the ratio of individuals who are guaranteed to have executable actions by tuning its hyperparameter y. helps decision-min makerrs provide recourse actions to appropriate individuals while keeping the quality of Decision-making
In addition, there is risk that method may be used maliciously to train model that provides specific actions for causing some undesired situations, such as discrimination. To avoid this risk, we may need check the actions provided to affected individuals before deploying the models (e.g.. using the existing techniques for globally summarizing recourse actions 29 48)
Overall, the proposed method has the potential to significantly improve the trustworthiness of the decision-making process, but we need careful consideration of its risks before incorporating into the actual decision-male process.
28

---

Table 2: Details of each feature of the FICO dataset 14
Feature
Type
Min
Max
Immutable
Constraint
ExternalRiskEstimatte
Integer 0.00
94.00
Yes
Fix
MSinneeOldesTTaaeeOpen
Integer
0.00
803.00
Yes
Fix
ASinceMossReceen//adopppp
Integer
0.00
383.00
Yes
Fix
Average.MInFile
Integer
4.00
383.00
Yes
Fix
NumSatisfactory Trades
Integer
0.00
79.00
No
Nothing
NunTrrddesOOEvee2DrropPPRBCB
Integer 0.00
19.00
Yes
Fix
Integer 0.00
19.00
Yes
Fix
Pereen/TradesNNevrrDDegg
Integer 0.00
100.00
No
Nothing
MSince-MostRecentDeel
Integer 0.00
83.00
No
Nothing
Max.eelg2PubicceeeLsst22222
Integer 0.00
9.00
No
Nothing
MaxDelqEver
Integer 2.00
8.00
No
Nothing
NumTotallTrades
Integer 0.00
104.00
Yes
Fix
NamTTradesSpeeninLsst1222
Integer 0.00
19.00
Yes
Fix
PerventInstallTradess
Integer 0.00
100.00
No
Nothing
MSinc<MossRccconnneexTTfeea
Integer 0.00
24.00
No
Nothing
NumlnglLast6M
Integer 0.00
66.00
No
Nothing
Numlngglast6Meex//7ays
Integer 0.00
66.00
No
Nothing
NelPraattonnkevoovingBBurr
Integer 0.00
232.00
No
Nothing
NetFPractioonnntallluurdre
Integer 0.00
471.00
No
Nothing
WonneevooiingTTdeeeWBBaaaaa
Integer 0.00
32.00
No
Nothing
NunlastallTradessBBBlaaam
Integer
0.00
23.00
No
Nothing
Integer
0.00
18.00
No
Nothing
Percent Waalance
Integer
0.00
100.00
No
Nothing
Table 3: Details of each feature of the COMPAS dataset 2
Feature
Type
Min
Max
Immutable
Constraint
age
Integer
18.00
96.00
No
Irreducible
juv_fel_com count
Integer
0.00
20.00
No
Nothing
juv_misd ccuntt
Integer
0.00
13.00
No
Nothing
juv_other_come count
Integer
0.00
17.00
No
Nothing
priors_cor _ount
Integer
0.00
38.00
No
Nothing
sex:Female
Binary
0.00
1.00
Yes
Fix
sex:Male
Binary
0.00
1.00
Yes
Fix
moe:African-America
Binary
0.00
1.00
Yes
Fix
race:Asian
Binary
0.00
1.00
Yes
Fix
race:Caucasian
Binary
0.00
1.00
Yes
Fix
race:Hispanic
Binary
0.00
1.00
Yes
Fix
race:Native-Americe
Binary
0.00
1.00
Yes
Fix
race:Other
Binary
0.00
1.00
Yes
Fix
e charge
F
Binary
0.00
1.00
No
Nothing
c_cargg__eegree:MM
charge
Binary
0.00
1.00
No
Nothing
29

---

Table 4:
Details of each feature of the Adult dataset 34
Feature
Type
Min
Max
Immutable
Constraint
age
Integer 17.00
90.00
No
Irreducible
educational num
Integer 1.00
16.00
No
Nothing
capital-gain
Integer
0.00
99999.00
No
Nothing
capital-loss
Integer
0.00
4356.00
No
Nothing
hours-per-week
Integer
1.00
99.00
No
Nothing
ciattallsstauus-Maride
Binary
0.00
1.00
Yes
Fix
marital-status:NoMMarii
Binary
0.00
1.00
Yes
Fix
race:Amer-Indiig -siii--
Binary
0.00
1.00
Yes
Fix
muc:Assia-Pac--slannde
Binary
0.00
1.00
Yes
Fix
race:Black
Binary
0.00
1.00
Yes
Fix
race:Other
Binary
0.00
1.00
Yes
Fix
race: White
Binary
0.00
1.00
Yes
Fix
gender:Female
Binary
0.00
1.00
Yes
Fix
gender:Male
Binary
0.00
1.00
Yes
Fix
native-country:Otherrs
Binary
0.00
1.00
Yes
Fix
native-country:US
Binary
0.00
1.00
Yes
Fix
Table 5: Details of each feature of the Bail dataset [53
Feature
Type
Min
Max
Immutable
Constraint
White
Binary
0.00
1.00
Yes
Fix
Alchy
Binary
0.00
1.00
No
Nothing
Junky
Binary
0.00
1.00
No
Nothing
Super
Binary
0.00
1.00
Yes
Fix
Married
Binary
0.00
1.00
Yes
Fix
Felon
Binary
0.00
1.00
Yes
Fix
Workrel
Binary
0.00
1.00
No
Nothing
Propty
Binary
0.00
1.00
Yes
Fix
Person
Binary
0.00
1.00
Yes
Fix
Male
Binary
0.00
1.00
Yes
Fix
Priors
Integer
0.00
40.00
No
Nothing
School
Integer
1.00
19.00
No
Nothing
Rule
Integer
0.00
39,00
No
Nothing
Age
Integer
15.00
72.00
No
Irreducible
Tservd
Integer
1.00
287.00
Yes
Fix
Follow
Integer
46.00
57.00
Yes
Fix
30

---

FICO ADC
COMPAS ADC
Adult - ADC
Bail ADC
0,88
6,50
0,80
ALC
0.72
Vanilla
Vanilla
RABBT
Vanilia
Vanila
RABIT
(a) AUC
0.66
0.30
0.45
8.675
0.70
0.40
Vaaillo
OAF
RABIT
Vaailaa
O.F.P
RABET
Viailo
OAF
RABET
Viaili
OAF
RABET
(b) F1
Figure 5: Experimental results of baseline comparison with respect to the area under the ROC curve (AUC) and Fl score the models trained by each method (higher better).
Table 6: Average cost, sparsity, and plausibility of extracted actions with their standard deviation (lower better).
(a) Cost
Dataset
Vanilla
OAF
RABIT
FICO
0.358 = 0.01
0.315 + 0.01
0.165 0.03
COMPAS
0
0.181 0.01
0.11
Adult Bail
0.354
0.308 + 0.01
0.0
0.449 = 0.02
0.371 + 0.01
0.225
(b) Sparsity
Dataset
Vanilla
OAF
RABIT
FICO
2.155 = 0.06
2.792 0.08
1.078 0.05
COMPAS
1.518 = 0.05
1.553 0.05
2.64
Adult
1.467 = 0.07
1.547 0.1
1.422 = 0.14
0.14
Bail
1.546 + 0.1
1.563 0.05
1.131 0.03
(c) Plausibility
Dataset
Vanilla
OAF
RABIT
FICO
0.438 + 0.0
0.44 0.0
0.475 + 0.0
COMPAS
0.436 + 0.01
0.446 0.01
0.466 1.61
Adult
0.477 0.01
0.464 0.01
0.479
Bail
0.508 0.0
0.503
0.0
31

---

F500 Acsannzy
COMPAS- Ansusey
Adal Auernyy
Bad Jucana
E.71
exs
Vaadla
OLD
RABTT
Veudia
ONE
RAGIE
OMP
RARIT
Vorkk
ONF
RASET
IRCD Ticoaro
Revoroo
Bacnne
0.2
Ca
KAST
T
CGMPAS
Ancenuy
Avenary
Bet
6-Ta
Acconaay
B1A
Vandil
Vaciil
Statis
XARLE
KART
IED
EOUPPAS
Beverro
Adit Bevorm
Dull Bacceme
24
RASET
(b)
100
0.65
FICO Rocaze:
COMPAS-
Racone
Ads - BrorD
Bell Recene
1.
BS
OXT
RARITT
DAP
RARET
OAP
BARIT
Vesta
OXF
RAIIT
(c) T 150
Acxanay
COMPAS- Aneunay
Juancy
CAR
8.73
cas
BLA
FICO-
COMPAS
859
Vandil
JASLE
Vonill
UNE
KAXUT
Statis
XARU
KAXT
(d) T 200
F1C0 ANAERRY
COUPASS ANeeaa
Bell AnszaaY
6/7
usi
0.88
OAF
BARIT
RABIT
Yaiia
65
67
Sc
E
(e) T = 250
Figure 6: Sensitivity analysis of the number of trees T.
32

---

FICO Aneuncyy
CUMPAS - Accuracy
Adull Anerancy
Ball Accunccy
1.74
Accuracy
0.07
0.70
0020
0.84
0.67
0.83
0.2
Cost Dodge
Cost Budgge 3
Cost Dodgee
Coss Dodige 3
FICO Recouree
COMPAS Recoume
Adul Recourse
Boil Recoums
Recoume
Rocouze
0.50
0.2
Clod. Bodge
Clal Eurigs J
Clod Budlge
Cbsi Budges /
Vazilla
Figure 7: Sensitivity analysis of the cost budget ,..
Areaney
Accurary
Adult Aneuneey
Accunacy
0,8
0.70
Arcusaee
Ateurary
0.0
0.5
0.4
0.2
0.
0.2
04
0.2
04
0.4 Confidence Lebel
0.2
Confidence Lebel
Confidence Lebel
Confidence Lobel
FI0O Recouree
COMPAS Recoume
Adolt Recourse
Recomme
0.95
Tecoue
0.
Reconse
1000
Rx
Recauran
0.
0.8
0.3 Coalidencs Lebai.
0.3
Caulisune Labad
Coulidhacs Labad
Coalidaars Labad
Vasilla
OAF
RAJIT
Figure 8: Experimental results of the intercept adjustment approach proposed by 51
Table 7: Average brittleness of the models trained by each method against input perturbations (lower is better).
Dataset FICO COMPAS
Vanilla
OAF
RABIT
0.064 + 0.0
0.098 + 0.01
0.063 0.0
0.107 0.0
0.114
0.113
Adult Bail
0.0
0.064
0.043 0.0
0.112
0.144 0.01
0.105 0.01
Table 8: Average cost of actions extracted by the exaxt AR method (lower is better).
Dataset
Vanilla
OAF
RABIT
FICO
0.354 0.05
0.293 = 0.07
0.11 0.01
COMPAS
0.188 + 0.04
0.158 + 0.03
1096+0000
Adult
0.34 + 0.02
0.297
0.257
Bail
0.42 + 0.05
0.32 + 0.04
0.213 0.02
33

---

Table 9: Average accuracy and recourse ratio of each method in the ablation study our learning algorithm and leaf refinement method (higher is better).
(a) Accuracy
Dataset
Vanilla
RABIT
Vanilla w/ Refinement
RABIT Refinement
FICO
0.735
0.01
0.732 + 0.01
0.708 + 0.01
0.716 + 0.01
COMPAS
0.682 + 0.01
0.677 0.01
0.676 + 0.01
0.677 + 0.01
Adult
0.852 + 0.0
0.851 + 0.0
0.853 0.0
0.85 + 0.0
Bail
0.711 = 0.01
0.701 0.0
0.702 + 0.01
0.706 + 0.01
(b) Recourse Ratio
Dataset
Vanilla
RABIT
Vanilla w/ Refinement
RABIT w/ Refinement
FICO
0.541 0.01
0.825 + 0.03
0.694 + 0.01
0.859 + 0.01 0.986 + 0.0
COMPAS
0.832 - 0.02
0.936 + 0.02
0,887 + 0.01
Adult
0.274 = 0.01
0.427 0.02
0.685 0.06
0.847 : 0.05
Bail
0.364 + 0.02
0.628 0.03
0.84 + 0.03
0.868 = 0.01
34


Reviews:
[{"review_id": "ix8wDJRV93", "reviewer": "Reviewer_FRpp", "summary": "The paper studies how to train boosted tree ensembles to maximize both the predictive accuracy and the likelihood of obtaining counterfactual explanations. It shows how to adapt the training procedure and provides theoretical results on guarantees of finding feasible recourse actions.", "questions": "- What part specifically in the approach of Kanamori et al. [ 28 ] makes it impossible to adapt the method to gradient-boosted trees?", "limitations": "See weaknesses.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is very well written. Its main argument is convincing and the methodology is well-supported.\n\nMy main concern is w.r.t the choice of Feature Tweaking as an oracle for finding an algorithmic recourse in the experiments. This algorithm is well-known to be outperformed by several more recent approaches, such as the work of Kanamori et al, Cui et al (cited in the paper) but also:\n- Parmentier, A., & Vidal, T. (2021, July). Optimal counterfactual explanations in tree ensembles. In International conference on machine learning (pp. 8422-8431). PMLR.\n- Lucic, A., Oosterhuis, H., Haned, H., & de Rijke, M. (2022, June). FOCUS: Flexible optimizable counterfactual explanations for tree ensembles. In Proceedings of the AAAI conference on artificial intelligence (Vol. 36, No. 5, pp. 5313-5322).\nIt is likely that the trend in results would maintain with alternative algorithms for algorithmic recourse, but it is a worthy experiment to show how large the gap in guaranteed recourse depends on the underlying algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comments and questions raised by the reviewer. \n\n---\n> My main concern is w.r.t the choice of Feature Tweaking as an oracle for finding an algorithmic recourse in the experiments. This algorithm is well-known to be outperformed by several more recent approaches, such as the work of Kanamori et al, Cui et al (cited in the paper) but also:\n>\n> - Parmentier, A., & Vidal, T. (2021, July). Optimal counterfactual explanations in tree ensembles. In International conference on machine learning (pp. 8422-8431). PMLR.\n> - Lucic, A., Oosterhuis, H., Haned, H., & de Rijke, M. (2022, June). FOCUS: Flexible optimizable counterfactual explanations for tree ensembles. In Proceedings of the AAAI conference on artificial intelligence (Vol. 36, No. 5, pp. 5313-5322). \n>\n> It is likely that the trend in results would maintain with alternative algorithms for algorithmic recourse, but it is a worthy experiment to show how large the gap in guaranteed recourse depends on the underlying algorithm.\n\nWe appreciate your important suggestion. While we employed the Feature Tweaking algorithm due to its efficiency in our experiments, we agree with the worthiness of the experiments that examine the dependence on the underlying algorithm for extracting recourse actions. \n\nWe conducted additional experiments where we employed the exact algorithm based on integer optimization proposed by (Cui et al. 2015), which is one of the alternative algorithms you raised. As with the experiments in Section 5.1, we split each dataset into the training and test sets with a ratio of 75:25, and trained a tree ensemble model by each method on the training set. Then, for test instances, we extracted actions from the model by (Cui et al. 2015), and measured the average cost of the extracted actions. Due to computational costs, we randomly sample 50 test instances for each trial. \n\nThe following Table 1 presents the average cost of actions over 10 trials (lower is better). We can see that our RABIT achieved lower costs than the baselines, regardless of the datasets, showing a similar tendency to the results with the Feature Tweaking algorithm. These results suggest that *the effectiveness of our method is maintained with an alternative recourse algorithm based on integer optimization*. \n\n**Table 1. Average Cost of Actions Extracted by (Cui et al. 2015) (lower is better)**\n|         |   FICO |   COMPAS |   Adult |   Bail |\n|:--------|-------:|---------:|--------:|-------:|\n| Vanilla |  0.354 |    0.188 |   0.340 |  0.420 |\n| OAF     |  0.293 |    0.158 |   0.297 |  0.320 |\n| RABIT   |  **0.110** |    **0.096** |   **0.257** |  **0.213** |\n\nWe will add these results to our final version. If possible, we will also conduct additional experiments with (Parmentier & Vidal 2021) or (Lucic et al. 2022). \n\n\n> What part specifically in the approach of Kanamori et al. [ 28 ] makes it impossible to adapt the method to gradient-boosted trees?\n\nThank you for your important question. The learning algorithm of Kanamori et al. is designed for classification trees and implicitly exploits the assumption that the output space is a finite set of labels, such as $\\{ -1, +1 \\}$. It enables us to efficiently determine the optimal leaf labels for a fixed branching rule by enumerating all the patterns of leaf labels and computing the objective value of each pattern. However, gradient boosting requires learning regression trees, where we need to handle the output space over $\\mathbb{R}$, rather than a finite set of labels. This prevents us from directly applying the existing algorithm of Kanamori et al. to our learning problem, and thus, we develop a new learning algorithm designed for gradient boosting. \n\n---\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback."}, {"review_id": "CspQfIoF9I", "reviewer": "Reviewer_H9PE", "summary": "The paper proposes a new framework, Recourse-Aware gradient Boosted decIsion Trees (RABIT) that learns tree ensemble models with recourse guarantees. The authors further proposes a post-processing procedure for modifying an existing tree ensemble model for better recourse outcomes on unseen data. They run a empirical experiments to verify that the resulting models have recourse and do not significantly sacrifice predictive accuracy.", "questions": "- Why do we assume that $l_{01} (y,\\hat{y}) \\leq l(y,\\hat{y})$? (Line 80)\n- Shouldn't the 0-1 loss be $l_{01}(y,\\hat{y} = \\mathbb{I}[y\\cdot\\hat{y} < 0])$?\n- Can the authors elaborate on how each term of $\\xi_{t}$ can be computed in $\\mathcal{O}(I_{s})$? Is this because $\\mathcal{A}$ is an $l_{\\infty}$ ball around $x$?\n- Is Proposition 5 really necessary?\n- The current framework aims to have one point with the desired prediction for each data point. Can we modify the framework to allow more recourse provision for each data point (i.e., rather than having just one with minimal cost)?\n- Any guesses on when post-processing is as effective as RABIT ensembles for standard tree ensembles?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\nThe authors have framed the problem very well. The problem they aim to address is significant and seems to be up to date with the literature. Experiments are well-designed.\n\n## Weaknesses\n**Significance of Experimental Results**\n\nThe paper can benefit from a more extensive discussion of the experimental results rather than just describing the outcome. The authors should take the extra step and answer: what significance do these results have? (i.e., real-life impact)\n\n**Set of Feasible Actions**\n\nStudies on algorithmic recourse heavily depend on how the set of feasible actions is defined. The set that the authors have presented in Section 2.1 (lines 94-95) is a convex relaxation of the true set of feasible actions. I have my reservations about this setup in effectively recovering recourse actions that are feasible in practice.", "was_revised": true, "final_justification": "The authors have adequately addressed most of my concerns.", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comments and questions raised by the reviewer. \n\n---\n> Significance of Experimental Results\n> The paper can benefit from a more extensive discussion of the experimental results rather than just describing the outcome. The authors should take the extra step and answer: what significance do these results have? (i.e., real-life impact)\n\nWe appreciate the reviewer's suggestion to elaborate on the real-life impact of our experimental results. We believe that the significance of our findings, particularly the improved recourse ratio without significant degradation in accuracy and computational efficiency, lies in their direct implications for reliability in high-stakes decision-making systems.\n\nIn real-world applications like loan approvals, our RABIT provides more individuals with feasible recourse actions, as shown in Figure 1. This means that users who receive an unfavorable decision are more likely to be given clear, low-cost steps they can take to change the outcome. This directly addresses the critical need for transparency in automated decision systems. Furthermore, as shown in Figures 1 and 2, RABIT maintains comparable accuracy and computational efficiency to standard gradient boosting. This fact makes our RABIT a highly practical tool for real-world deployment. Decision-makers can adopt our method without sacrificing predictive performance or incurring prohibitive computational costs.\n\nOur results also have another real-life impact in the sense that we focus on gradient boosted decision trees (GBDTs). GBDTs, such as XGBoost and LightGBM, are one of the most popular machine learning models and are widely used due to their excellent performance. Our results indicate the potential of our method that practitioners can replace the model in their system with our RABIT and improve their ability to provide recourses without degrading accuracy and efficiency.\n\nIn summary, our experimental results have significance in the sense that our RABIT is demonstrated to provide more individuals with feasible recourse actions without sacrificing predictive performance and computational efficiency of GBDTs. We believe it has a real-life impact as a first step to improve the reliability in high-stakes automated decision-making systems from the perspective of algorithmic recourse. \n\n\n> Set of Feasible Actions\n> Studies on algorithmic recourse heavily depend on how the set of feasible actions is defined. The set that the authors have presented in Section 2.1 (lines 94-95) is a convex relaxation of the true set of feasible actions. I have my reservations about this setup in effectively recovering recourse actions that are feasible in practice.\n\nThank you for your important comment. As you pointed out, we consider a convex set defined by $\\mathcal{A}(x) = [l_1, u_1] \\times \\dots \\times [l_D, u_D]$ as a set of feasible actions, and this setup reflects the practical feasibility of actions to some extent. As mentioned in lines 95-97, this setup can express some basic constraints on actionability, such as immutable features (e.g., race) and partially actionable features (e.g., education level), by adequately setting the bounds $l_d$ and $u_d$. Thus, we believe that our method is valuable as a foundational step for further extension.\n\nOf course, we acknowledge that a more complex, non-convex set of feasible actions might better capture certain real-world nuances (e.g., dependencies between features). Unfortunately, it is not trivial to incorporate such a non-convex action set into our learning algorithm while maintaining computational efficiency and theoretical guarantees. This is because our algorithm relies on the property that we can evaluate the feasibility of an action by checking each feature independently.\n\nAs a side note, we would like to note that while it is difficult for our learning algorithm to directly handle a non-convex feasible action set, our post-processing method can deal with such a complex constraint. Our post-processing method assumes only that we have an oracle algorithm $A_\\beta^\\ast$ for generating recourse actions, and does not require its feasible action set to be convex. Thus, if we can employ an oracle algorithm $A_\\beta^\\ast$ that can handle non-convex constraints (e.g., integer optimization-based algorithms), we can take into account a non-convex set of feasible actions by combining such an oracle $A_\\beta^\\ast$ and our post-processing method. In the final version, we will clarify this point.\n\n\n> Why do we assume that $l_{01}(y, \\hat{y}) \\leq l(y, \\hat{y})$? (Line 80)\n> Shouldn't the 0-1 loss be $l_{01}(y, \\hat{y}) = \\mathbb{I}[y \\cdot \\hat{y} < 0]$?\n\nWe appreciate your careful reading. As you pointed out, $l_{01}(y, \\hat{y}) = \\mathbb{I}[y \\cdot \\hat{y} < 0]$ is correct. We need the assumption $l_{01}(y, \\hat{y}) \\leq l(y, \\hat{y})$ only for proving our PAC-style bound in Proposition 3. In practice, however, this assumption does not affect our learning algorithm itself, and thus our method works without it. We will clarify this point in our final version. \n\n\n> Can the authors elaborate on how each term of $\\xi_t$ can be computed in $\\mathcal{O}(I_s)$? Is this because $\\mathcal{A}$ is an $l_\\infty$ ball around $x$?\n\nYes, we can compute each term of $\\xi_t$ in $\\mathcal{O}(I_s)$ by using our assumption on the $\\ell_\\infty$-type cost function. To compute each term of $\\xi_t$, we need to enumerate the leaves of a tree $f_s$ that an instance $x$ can reach within the given cost budget $\\beta$. We can identify such leaves by traversing the tree $f_s$ from its root and evaluating whether $x$ can reach the region corresponding to each node by some action whose cost is less than $\\beta$. This evaluation can be done in a constant time because we need to check only the feature corresponding to the branching rule of each node, thanks to our assumption on the cost function. The entire procedure can be done by simple DFS or BFS over the tree, and takes at most the total number of nodes of $f_s$, i.e., $\\mathcal{O}(I_s)$. \n\n\n> Is Proposition 5 really necessary?\n\nWe would like to note that our paper does not include Proposition 5. Thus, we reply to this comment by assuming that it refers to any one of Propositions 1-3 in our paper. First, Proposition 1 gives a theoretical foundation for deriving a differentiable upper bound on recourse loss. Proposition 2 proves that taking into account the recourse loss does not sacrifice the computational efficiency of the standard gradient boosting algorithm. Finally, Proposition 3 provides a probabilistic guarantee for the existence of actions for unseen test instances. Since these implications are strongly connected to our contributions, we believe that Propositions 1-3 are necessary for guaranteeing and demonstrating the efficacy of our framework.\n\n\n> The current framework aims to have one point with the desired prediction for each data point. Can we modify the framework to allow more recourse provision for each data point (i.e., rather than having just one with minimal cost)?\n\nThank you for your interesting suggestion. As you mentioned, our recourse loss encourages the model to guarantee the existence of at least one valid action whose cost is less than a given budget. It is not trivial to extend our recourse loss to take multiple actions into account without harming its tractability. However, we believe that our post-processing approach can be extended to allow multiple actions. If we assume that the oracle algorithm $A^\\ast_\\beta(x)$ generates multiple actions for $x$, we can easily extend our leaf refinement problem in (9) to the case where each instance $x_n$ has multiple actions, which can be solved by the same algorithm as our current approach. By solving this extended task, a refined model is expected to probably ensure that multiple generated actions are valid for each $x$. That is, the refined model probably guarantees the existence of multiple valid recourse actions for each instance.\n\n\n> Any guesses on when post-processing is as effective as RABIT ensembles for standard tree ensembles?\n\nThank you for your important question. Recall our post-processing method refines the leaf weights of a trained ensemble, while fixing the tree structures in the ensemble. Thus, if an ensemble trained by the standard algorithm (Vanilla) has similar tree structures to those of an ensemble that attains a high recourse ratio, we can achieve a comparable recourse ratio to RABIT by our post-processing method alone.\n\nIn our reply to Reviewer bYie, we show our ablation results where we compared the performance of Vanilla, RABIT, Vanilla w/ Refinement, and RABIT w/ Refinement. We observed that while RABIT outperformed Vanilla w/ Refinement in FICO and COMPAS datasets, Vanilla w/ Refinement outperformed RABIT in Adult and Bail datasets. This suggests that, among these four datasets, Adult and Bail are expected to be the cases where our post-processing is more effective than RABIT. While such a gap might be caused by some specific properties of datasets, such as the ratio of actionable features or the percentage of categorical features, it is challenging to characterize a general cause. It is important for future work, and we will add a discussion on this point to our final version.\n\n\n---\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback."}, {"review_id": "pIjG0OKTlO", "reviewer": "Reviewer_bYie", "summary": "This paper proposes *recourse loss* which measures how easily a prediction can be flipped with a low-cost, feasible action. This paper is the first to extend recourse guarantees to GBDTs: the training objective combines standard predictive loss and recourse loss via a trade-off parameter. The recourse loss is non-differentiable, so the authors derive a smooth upper bound using techniques like log-sum-exp, enabling gradient boosting.\n\nPost-hoc refinement treats the tree ensemble as a linear model in its leaves and solves a constrained optimization to reduce recourse loss on unseen data. The optimization is made feasible by being reformulated into a tractable unconstrained problem using a Lagrangian multiplier tuned on a calibration set.", "questions": "See Weaknesses", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Pros:\n\nThe paper is generally well-written and the empirical result is strong. The contribution appear to be significant within a community: previous recourse-aware learning methods targeted NN which rely on differentiability, or classification trees. This paper is the first to extend recourse guarantees to GBDTs. \n\nCons:\n\nThere isn't an ablation study on the post-hoc refinement. Does the proposed method not make sense at all without the refinement?", "was_revised": true, "final_justification": "The author have adequately addressed my concern. I believe this is a quality paper to a somewhat limited audience.", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comment raised by the reviewer. \n\n---\n> Cons:\n> There isn't an ablation study on the post-hoc refinement. Does the proposed method not make sense at all without the refinement?\n\nThank you for your important comment. As you mentioned, our current manuscript does not explicitly show ablation studies on our post-hoc refinement. However, we can discuss its effect in an ablation study manner by reorganizing the results in Figures 1 and 4. In what follows, we show the reorganized results from Figure 1 and Figure 4 to compare the performances of *Vanilla*, *RABIT*, *Vanilla w/ Refinement*, and *RABIT w/ Refinement*. \n\nNote that there are two main evaluation metrics (i.e., accuracy and recourse ratio) and the parameter $\\lambda$ of our post-hoc refinement affects these metrics. To make the comparison easier to understand, for each method and dataset, we selected the value of $\\lambda$ that attained the closest accuracy to that of RABIT. The following Table 1 shows the average accuracy of each method (higher is better). We can see that the accuracy gaps between methods were at most 2.7%, 0.6%, 0.3%, and 1.0% on FICO, COMPAS, Adult, and Bail datasets, respectively. It indicates that *all the methods attained comparable accuracy in each dataset*. \n\n**Table 1. Average Accuracy (higher is better)**\n|                       |   FICO |   COMPAS |   Adult |   Bail |\n|:----------------------|-------:|---------:|--------:|-------:|\n| Vanilla               |  0.735 |    0.682 |   0.852 |  0.711 |\n| RABIT                 |  0.732 |    0.677 |   0.851 |  0.701 |\n| Vanilla w/ Refinement |  0.708 |    0.676 |   0.853 |  0.702 |\n| RABIT w/ Refinement   |  0.716 |    0.677 |   0.850 |  0.706 |\n\nThe following Table 2 shows the average recourse ratios of each method (higher is better). We observed that RABIT w/ Refinement performed the best, and that RABIT and Vanilla w/ Refinement performed better than Vanilla. In addition, we also observed that while RABIT outperformed Vanilla w/ Refinement in FICO and COMPAS datasets, Vanilla w/ Refinement outperformed RABIT in Adult and Bail datasets. These results indicate that *our learning algorithm and post-hoc refinement are effective individually*, and *their combination can achieve better results*. \n\n**Table 2. Average Recourse Ratio (higher is better)**\n|                       |   FICO |   COMPAS |   Adult |   Bail |\n|:----------------------|-------:|---------:|--------:|-------:|\n| Vanilla               |  0.541 |    0.832 |   0.274 |  0.364 |\n| RABIT                 |  *0.825* |    *0.936* |   0.427 |  0.628 |\n| Vanilla w/ Refinement |  0.694 |    0.887 |   *0.685* |  *0.840* |\n| RABIT w/ Refinement   |  **0.859** |    **0.986** |   **0.847** |  **0.868** |\n\n\nIn summary, we confirmed that our proposed learning method can make sense on its own, even without our refinement method. In our final version, we will add the above ablation study and discuss its results.\n\n\n---\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback."}, {"review_id": "gMLWGY3s93", "reviewer": "Reviewer_JBHL", "summary": "The authors propose a recourse-aware gradient-boosting algorithm (RABIT) that considers recourse actions. They also propose a post-processing task of modifying a learned tree ensemble model to satisfy the constraint on recourse guarantee and theoretically and empirically demonstrate the efficacy of RABIT in comparison to vanilla gradient boosting algorithms.", "questions": "- Actionability and mutability of features. \nThe authors consider two cases: RABIT, which places less emphasis on actionability, and OAF, which restricts itself to actionable features. \nWhile I understand the premise of the author's argument and appreciate the two versions, it is unclear to me whether the recourse generated based on the RABIT-trained trees respects actionability constraints.\nFor example, even if RABIT does not explicitly incorporate actionability, do the generated recourses avoid suggesting unrealistic or non-actionable changes, such as increasing age by 10 years? While technically viable, the recommendation is not actionable and could encourage gaming behavior rather than genuine improvement.\nAdditionally, regarding the example on lines 31–36, would it be possible for the authors to use another example?\n\n- Price of recourse.\nThe authors use the maximum percentile shift costs function. However, Ustun et al. mention that this might not correctly reflect the difficulty\nof recourse. How easy(hard) would it be to equation 5 to other forms of the price of recourse?\n\n- Experiments.\nWhile the authors do a great job of illustrating the experimental results, the explanations of the observations are sparse. \nFor example, can the authors provide explanations for why OAF (Figure) consistently has the lowest accuracy and why the recourse ratio is close to 1 and 0.5 in other datasets, or why RABIT consistently has the highest ratio? Why is the gamma parameter better at 0.002 to 0.004?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The authors clearly state the problem and present theoretically and empirically sound results. \n- They theoretically prove that with and without recourse guarantees, they can get an approximate solution in O(ND) time. \n- To ensure recourse guarantees for unseen test instances, authors also propose a leaf refinement approach and show a PAC-style bound on the estimation error of the surrogate risk.\n- Authors empirically test RABIT on four commonly used real-world datasets, provide key details about the experimentation process in the main paper and appendix, and avail their code. \n\n**Weaknesses**\n- Actionability and mutability of features. \nThe authors consider two cases: RABIT, which places less emphasis on actionability, and OAF, which restricts itself to actionable features. \nWhile I understand the premise of the author's argument and appreciate the two versions, it is unclear to me whether the recourse generated based on the RABIT-trained trees respects actionability constraints.\nFor example, even if RABIT does not explicitly incorporate actionability, do the generated recourses avoid suggesting unrealistic or non-actionable changes, such as increasing age by 10 years? While technically viable, the recommendation is not actionable and could encourage gaming behavior rather than genuine improvement.\nAdditionally, regarding the example on lines 31–36, would it be possible for the authors to use another example?\n\n- Price of recourse.\nThe authors use the maximum percentile shift costs function. However, Ustun et al. mention that this might not correctly reflect the difficulty\nof recourse. How easy(hard) would it be to equation 5 to other forms of the price of recourse?\n\n- Experiments.\nWhile the authors do a great job of illustrating the experimental results, the explanations of the observations are sparse. \nFor example, can the authors provide explanations for why OAF (Figure) consistently has the lowest accuracy and why the recourse ratio is close to 1 and 0.5 in other datasets, or why RABIT consistently has the highest ratio? Why is the gamma parameter better at 0.002 to 0.004?", "was_revised": true, "final_justification": "I will retain the positive score with the hope that authors incorporate the promised changes such as a comprehensive limitations and  and future works sections, and the new observations e.g., extension of leaf refinement problem to the case where instance has multiple actions, among others.", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key comments and questions raised by the reviewer. \n\n---\n> Actionability and mutability of features. The authors consider two cases: RABIT, which places less emphasis on actionability, and OAF, which restricts itself to actionable features. While I understand the premise of the author's argument and appreciate the two versions, it is unclear to me whether the recourse generated based on the RABIT-trained trees respects actionability constraints. For example, even if RABIT does not explicitly incorporate actionability, do the generated recourses avoid suggesting unrealistic or non-actionable changes, such as increasing age by 10 years? While technically viable, the recommendation is not actionable and could encourage gaming behavior rather than genuine improvement. \n\nOur method is designed to avoid suggesting unrealistic or non-actionable changes. This is because we explicitly incorporate actionability during the model training phase, as well as the recourse generating phase.\n\nAt the training phase, we consider the learning objective function that consists of the standard loss and our recourse loss. Our recourse loss is defined as $l_\\beta(x \\mid f) = \\min_{a \\in \\mathcal{A}_\\beta(x)} l(+1, f(x+a))$, where the set of feasible actions $\\mathcal{A}_\\beta(x)$ is constructed under given actionability constraints. For example, we can enforce $\\mathcal{A}_\\beta(x)$ to not include actions that change age or gender. Our recourse loss encourages learning a model whose decision boundary is \"recourse-friendly\" within the predefined actionability constraints, rather than simply ignoring immutable features like OAF. By minimizing our learning objective function, we can guarantee the existence of realistic and actionable recourse actions while maintaining sufficient accuracy by exploiting both actionable and immutable features.\n\nIn addition, at the generating phase, we extract actions from the trained models under the actionability constraints so that the generated actions do not change immutable features. Note that this can be done by existing algorithms for generating recourse actions. Our main contribution is to incorporate actionability in the training phase of gradient boosted decision trees and demonstrate that we can ensure the existence of realistic actions for many instances without degrading predictive accuracy and computational efficiency.\n\n\n> Additionally, regarding the example on lines 31–36, would it be possible for the authors to use another example?\n\nWe can provide other examples with respect to lines 31-36. For example, \"past bankruptcy\" is an important feature for estimating the risk of default, but it might be immutable for a certain period. Another example is \"number of dependents,\" which might be practically difficult to change solely for the purpose of a loan. In our final version, we will revise our example scenario.\n\n\n> Price of recourse. The authors use the maximum percentile shift costs function. However, Ustun et al. mention that this might not correctly reflect the difficulty of recourse. How easy(hard) would it be to equation 5 to other forms of the price of recourse?\n\nThank you for your important comment. The computational efficiency of our algorithm relies on a property of $\\ell_\\infty$-type cost functions, including the maximum percentile shift. Thus, it would be challenging to maintain its efficiency by simply extending our method to other cost functions.\n\nSpecifically, for $\\ell_\\infty$-type cost functions, we can easily decide whether the budget constraint is violated or not by checking each feature independently. In general, this property does not hold for other cost functions such as $\\ell_1$-norm. Thus, it is not trivial to deal with these cost functions in our current approach while maintaining its computational efficiency.\n\nIn practice, however, we expect that if we introduce some heuristic strategies such as changing the budget parameter $\\beta$ for each depth of tree (Wang et al. 2020), our approach can be extended to deal with other cost functions without harming efficiency. In our final version, we will clarify this limitation of our current algorithm and mention it as future work.\n\n\n> Experiments. While the authors do a great job of illustrating the experimental results, the explanations of the observations are sparse. For example, can the authors provide explanations for why OAF (Figure) consistently has the lowest accuracy and why the recourse ratio is close to 1 and 0.5 in other datasets, or why RABIT consistently has the highest ratio? Why is the gamma parameter better at 0.002 to 0.004?\n\nWe appreciate your important comment on our explanations of the observations. In our final version, we will add more detailed discussions on our experimental results.\n\n**On the lowest accuracy of OAF**:\nOne possible reason why OAF consistently had the lowest accuracy is that OAF restricts models to only actionable features during training, sacrificing predictive power by ignoring potentially highly predictive non-actionable features. For example, in the Adult dataset, OAF could use only 5 of the 16 features and could not use immutable features such as gender, race, and age, which might degrade the accuracy of OAF compared to other methods. We think this inherent limitation might lead to lower accuracy compared to models using all features.\n\n**On the Variance of Recourse Ratio and Highest Ratio of RABIT**:\nThe recourse ratio depends heavily on the inherent properties of the datasets. In particular, we guess that it might depend on the specific actionability constraints defined for each feature (as shown in Tables 2-5 in Appendix C). For instance, in FICO, many financial features (e.g., NumSatisfactoryTrades, NetFractionRevolvingBurden) are actionable, making it easier to find low-cost recourses for almost all instances. In contrast, since Adult includes many demographic features that are not actionable, there might be no actionable change if the trained model heavily relies on these immutable features for its predictions. It suggests that it is challenging to provide actionable and low-cost actions even for half of the instances in such a dataset. As mentioned above, the objective function of our RABIT directly optimizes for recourse existence via the recourse loss term that explicitly guides the model to find recourse-friendly decision boundaries. We believe it is a main reason why our RABIT consistently had the highest recourse ratio. \n\n**On the Gamma Parameter**:\nBy our definition, $\\gamma$ balances predictive accuracy and recourse guarantee in our learning objective function. We observed that $\\gamma = 0.002$ is a sweet spot where RABIT achieves significant improvements in recourse ratio without significantly degrading accuracy, regardless of the datasets in our experiments. It suggests that such a slight emphasis on our recourse loss is sufficient to achieve substantial improvements without harming predictive performance. One possible reason is that our bound for the recourse loss shown in Proposition 1 is too conservative. It suggests that our method can be improved by developing a tighter bound, which is interesting for future work. \n\n\n---\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback."}, {"review_id": "DeX0zJwaTz", "reviewer": "Reviewer_nKF5", "summary": "This paper focuses on Algorithmic Recourse. The paper proposes a new gradient boosted decision tree framework, called Resource-Aware Gradient Boosted Decision Tree (RABIT), which can provide both accurate predictions and executable resource actions. A post-processing method is also proposed to refine the leaf weights, and a PAC-style guarantee is provided. Experimental results on four datasets show that RABIT outperforms the baseline while maintaining comparable accuracy and efficiency.", "questions": "1. There are few data sets used in the experiment. Why did you choose these four data sets?\n\n2. Is it only binary classification? How about multiple classifications?\n\n3. In the introduction section, it was mentioned that some features, such as age and race, cannot be modified. How did you reflect this in your experiment?\n\n4. “Figure 3 shows the average accuracy and recourse ratio for each γ. We can see that the recourse ratio 294 (resp. accuracy) was improved by increasing (resp. decreasing) γ on almost all the datasets, which 295 suggests that we could balance their trade-off by tuning “ I disagree with this statement. Figure 3 can only show that there is a trade-off, but it cannot show that RABIT can balance this trade-off.\n\n5. Are the experimental results in Sections 5.1 and 5.2 using post-processing or not? What are the ablation experiments with and without post-processing?\n\n6. Why is the accuracy lower and the variance larger on adult and bail from t=100 to t=150? The same thing happens on FICO and COMPAS from t=150 to t=200.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths \n\nThe issues this paper focuses on are important, especially since some of the features cannot be modified as mentioned in the introduction.\n\nThe paper gives a PAC-style guarantee.\n\n## Weaknesses\n\nThe experiments are not sufficient, for example, only four datasets are used, and the analysis of some experimental results is not very clear.", "was_revised": true, "final_justification": "My concerns are addressed, so I keep my positive score.", "rebuttal": "We would like to thank the reviewer for valuable and thoughtful feedback. We will reflect all of them in our final version. In the following, we will respond to the key questions raised by the reviewer. \n\n---\n> 1. There are few data sets used in the experiment. Why did you choose these four data sets?\n\nWe chose the four datasets (FICO, COMPAS, Adult, and Bail) because they are widely used and well-established benchmarks in the literature on algorithmic recourse (e.g., Ross et al. 2021, Kanamori et al. 2024). These datasets represent diverse real-world applications (finance, criminal justice, census, and bail prediction), allowing us to demonstrate the generalizability and effectiveness of RABIT across different domains. While we acknowledge that more datasets could further strengthen our experiments, we believe these four datasets are sufficient to validate our claims and compare our method with existing baselines, as evidenced by prior studies in this field that also use these datasets.\n\n\n> 2. Is it only binary classification? How about multiple classifications?\n\nThank you for your important question. While the current manuscript focuses on binary classification, our method can be applied to multiclass classification settings if we can reduce the multiclass problem to a binary one. For example, if we can divide the classes into desirable and undesirable ones, then the multiclass problem is reduced to a binary classification problem between these two classes.\n\n\n> 3. In the introduction section, it was mentioned that some features, such as age and race, cannot be modified. How did you reflect this in your experiment?\n\nIn our experiments, we defined immutable features for each dataset, which are shown in Tables 2-5 in Appendix C. When we extracted recourse actions from the models trained by each method, we imposed the actionability constraints so that the generated actions do not change immutable features, such as age and race. In addition, our RABIT incorporates such actionability constraints in our recourse loss, which encourages the model to guarantee the existence of recourse actions that do not change immutable features. In summary, we take into account the actionability constraints during both the recourse extraction and model training phases.\n\n\n> 4. “Figure 3 shows the average accuracy and recourse ratio for each γ. We can see that the recourse ratio 294 (resp. accuracy) was improved by increasing (resp. decreasing) γ on almost all the datasets, which 295 suggests that we could balance their trade-off by tuning “ I disagree with this statement. Figure 3 can only show that there is a trade-off, but it cannot show that RABIT can balance this trade-off.\n\nWe appreciate your careful reading and acknowledge the nuance in the statement. Let us clarify our claim \"we could balance their trade-off\" in line 295. \n\nAs you pointed out, it is true that Figure 3 shows a trade-off between the recourse ratio and accuracy. However, Figure 3 also indicates the potential that we can attain a higher recourse ratio without compromising prediction performance if we can determine the appropriate value of $\\gamma$. From this observation, we claim that if we execute RABIT with multiple $\\gamma$, we have a chance to achieve a high recourse ratio with comparable accuracy to baselines, which is mentioned in lines 295-299. In our final version, we will rephrase these statements to be more precise and avoid any ambiguity.\n\n\n> 5. Are the experimental results in Sections 5.1 and 5.2 using post-processing or not? What are the ablation experiments with and without post-processing?\n\nThank you for your important question. In our experiments in Sections 5.1 and 5.2, we did not use our post-processing method.\n\nWhile our paper does not explicitly include the ablation experiments on our post-hoc refinement, we can discuss its effect in an ablation study manner by reorganizing the results in Figures 1 and 4, where we compare the performances of Vanilla, RABIT, Vanilla w/ Refinement, and RABIT w/ Refinement.\n\nThe reorganized results are shown as our reply to Reviewer bYie. As we replied to Reviewer bYie, these results indicate that our learning algorithm and post-hoc refinement are effective individually, and their combination can achieve significantly better results than the baseline. In our final version, we will add this ablation result and discuss it.\n\n\n> 6. Why is the accuracy lower and the variance larger on adult and bail from t=100 to t=150? The same thing happens on FICO and COMPAS from t=150 to t=200.\n\nThank you for your careful reading. We think that there are some reasons for such results.\n\nOne possible reason is that the trained models might have overfitted the training datasets in some cases as the total number of $T$, i.e., model complexity, increased. In our experiments, we fixed the learning rate to $0.1$ and maximum depth of trees to $8$ regardless of $T$. If we carefully tune these parameters, we may obtain more stable results.\n\nAnother reason is the heuristic nature of gradient boosting algorithms. While our method provides theoretical guarantees, the practical implementation of gradient boosting involves some heuristic techniques, such as greedy splitting, approximation based on Taylor expansion, and bootstrap sampling for training each tree. These heuristics might lead to less stable solutions and increase variance. \n\nIn practical situations, we acknowledge that it is valuable to stabilize our algorithm without harming its performance. In our final version, we will mention this point as future work. \n\n\n---\nWe hope that we have adequately addressed all your questions and concerns. Please let us know if we can provide any further details and/or clarifications. Thank you again for your valuable feedback."}]

Author rebuttal:

Meta-review: This paper proposes a gradient boosting algorithm for the _algorithmic recourse_ framework, in which the predictor can provide a _recourse action_ that would have changed its prediction. For example, if the predictor outputs a credit score, it could suggest a change to the candidate's financial status that would have increased (or decreased) their score. This helps with explainability and could be used to improve outcomes (e.g., suggesting actions a candidate could take to improve their credit). According to the paper, guaranteeing the existence of a recourse action is nontrivial, and prior methods to guarantee recourse actions do not apply to the class of gradient boosting algorithms. Thus, the paper fills this gap, providing a gradient boosting algorithm with (high-probability) recourse guarantees. In addition, it provides a post-processing algorithm that, given a learn model, outputs a "refined" version thereof along with recourse guarantees.

The reviews all say that this paper is well written, well motivated, and technically sound. The authors' rebuttal seems to have addressed all of the reviewers' concerns, so I will not bother enumerating them here. The overall scores are all positive, so I recommend accepting this paper.
Decision: Accept (poster)