Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values
Authors: R. Teal Witter
Yurong Liu
Christopher Musco
Venue: NeurIPS 2025 poster ()
Keywords: Shapley values
Regression-adjustment
Kernel SHAP
Maximum sample reuse
Permutation SHAP
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We combine Monte Carlo and regression-based methods to get a flexible estimator which achieves state-of-the-art performance.

Abstract: With origins in game-theory, probabilistic values like Shapley values, Banzhaf values, and semi-values have emerged as a central tool in explainable AI. They are used for feature attribution, data attribution, data valuation, and more. Since all of these values require exponential time to compute exactly, research has focused on efficient approximation methods using two techniques: Monte Carlo sampling and linear regression formulations. In this work, we present a new way of combining both of these techniques. Our approach is more flexible than prior algorithms, allowing for linear regression to be replaced with any function family whose probabilistic values can be computed efficiently. This allows us to harness the accuracy of tree-based models like XGBoost, while still producing unbiased estimates. From experiments across eight datasets, we find that our methods give state-of-the-art performance for estimating probabilistic values. For Shapley values, the error of our methods is up to $6\times$ lower than Permutation SHAP (the most popular Monte Carlo method), $2.75\times$ lower than Kernel SHAP (the most popular linear regression method), and $1.75\times$ lower than Leverage SHAP (the prior state-of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error up to $60\times$ lower than prior work.

Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values
R. Teal Witter Claremont McKenna College rtealvitter@cme edu
Yurong Liu New York University yurong 1 liu@nyu. edu
Christopher Musco New York University cmusco@nyu. edu
Abstract
With origins in game theory, probabilistic values like Shapley values. Banzhaf values, and semi-values have emerged as a central tool in explainable AL. They are used for feature attribution, data attribution, data valuation, and more. Since all of these values require exponential time to compute exactly, research has focused efficient approximation methods using two techniques: Monte Carlo sampling and linear regression formulations. this work, we present a new way of combining both of these techniques. Our approach is more flexible than prior algorithms, allowing for linear regression to be replaced with any function family whose probabilistic values can be computed efficiently. This allows to harness the accuracy of tree-based models like XGBoost, while still producing unbiased estimates. From experiments across eight datasets, find that methods give state-of-the-art performance for estimating probabilistic values. For Shapley values, the error of our methods can be 6.5x lower than Permutation SHAP (the most popular Monte Carlo method), 3.8 x lower than Kernel SHAP (the most popular linear regression method), and 2.6x lower than Leverage SHAP (the prior state- of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error 215x lower than the best estimator from prior work.
Introduction
As Al becomes more prevalent across health care, education, finance, and the legal system, underlying algorithmic mechanisms are growing increasingly complex. Sophisticated computational models frequently make decisions that are opaque and challenging to comprehend. This is unacceptable in contexts where decisions can have profound consequences for individuals: the ability clearly understand and explain how an algorithmic system reaches its conclusions is paramount.
One tool that has arisen to address the challenge of understanding model behavior probabilistic values, which include Shapley values, Banzhaf values, and semi-values as special cases SK
L1.17 LEC+ 20. WJ23). Originating from game theory [Sha5]], probabilistic values quantify the contribution of a player by measuring how its addition to a set of other players changes the value
of the game. Formally, consider a value function v 2 + IR defined on sets S C [n]. where [n]
denotes n1....,n]. The probabilistic value for player [n]] is
(s(v)
Σ P( (+) v(S)
(1)
SCIRMM
where p = - .......PP-- Pn_1] E [0, 1|"h is set of probabilistic weights that satisfy Σn (m=
))=pp==
We can interpret the ith probabilistic value as the averuge marginal contribution of player to random set S, where the distribution over set sizes specified by p. Different choices of p yield different variants of probabilistic values [KZ22a] KZ22b LY24c). For example, to obtain the ubiquitous
Shapley values, set p.- = 1²--))= and to obtain Banzhaf values, set Pe = 1/22-1 -1 for all &.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Our paper addresses the problem of computing $1....,, Un in full generality for any p. The topic of which weights are best for given application has received significant attention. Some prior work focuses on axiomatic approaches for choosing p. For example, all probabilistic values satisfy three desirable properties: null player, symmetry, and linearity (see (Web88) for detailed discussion). Shapley values satisfy an additional efficiency property [Sha51]] and Banzhaf values satisfy 2- efficiency property that might be desirable when there are non-linear interactions between players PPn44 BI64]. Generalizations of these values include Beta Shapley [KZ22al values and weighted Banzhaf values [LY24c]. See Appendix
B for more on these generalizations.
Regardless of how p is chosen, the meaning of the probabilistic values depends on how the value function, v, defined. For example, a common task in explainable Al is to attribute a model prediction (for given input) to features [LL[7]. Here, v(S). is the prediction made when using just the subset of features corresponding to s Probabilistic values are also used in data attribution tasks, where (S) corresponds to the model loss when training with given subset of data [GZ19, WMSJ255. In these applications and others, evaluating e is expensive, as it requires re-running or possibly even re-training a model. As in prior work on efficient probabilistic value estimation, we thus focus on algorithms that estimate $i...., Un using as few evaluations of as possible. We view these evaluations as black-box, designing algorithms that are agnostic to the particular value function and can thus be applied in a wide range of downstream applications.
1.1 Efficiently Computing Probabilistic Values
For general value functions, exactly computing probabilistic values requires exponential time, as the summation in Equation ① involves O(2") terms. When is a highly structured function, like a linear function or decision tree, more efficient algorithms exist [LL17 LELI 8 LEC 20 KMM+22] However, given the complexity of modern machine learning models, most prior work focuses on approximation algorithms.
The standard method is to approximate the summation in Equation [ via Monte Carlo estimate obtained from a weighted sample of sets that do not contain KKZ22 K2222 LY24b]. Concretely, assume for simplicity that we sample a collection of subsets, S, by drawing samples with replacement from a distribution with density D 2l + [0, 1 We then compute the unbiased estimate:
IMC- =
1
(e)Su v(5)] PIS D(S)
(2)
SES;
We have that [[(MMC D. as well as [v(S u {i}) - "(S)]² for all S C [n]. In addition to high-variance in practice downside of Monte Carlo estimators is that is difficult to "reuse" samples between indices 1, ..... n. as each term in Equation 2 requires evaluating both v(S U {i}) and v(S) for particular i. Several methods address this issue via "sample reuse" [CGTO9] One technique especially relevant to our work is the maximum sample reuse (MSR) method, which was originally applied to Banzhaf values [W]23], but generalizes naturally to all probabilistic values [KBMH24 LY24a LY24b]. The MSR method draws a single collection of subsets, S. according to D 2 + [0, 1]. and computes the estimate:
Φ;, and the estimator's 's variance depends on the choice of sampling distribution
1 Σ
(SS) PIS| 1 Aii E S] - - 1[i ( Li
TMSR
S
D(S)
SES
It can be checked that still have B[oMSR] o; for all i. Moreover, every evaluation of the value function, v(S), contributes to the estimate for all i E [n]. so we achieve maximum sample reuse. However, the variance of MSR methods scales as a weighted sum of [o(S)]?, which is generally much larger than the difference between nearby values [o(S U (i)) - =(S))
Beyond Monte Carlo. Given the high variance of Monte Carlo methods, an alternate approach based on regression has become popular for the special case of Shapley values. In particular, Shapley values
'Since most models in machine learning require a full set of input features, features not in S are replaced with either mean value or random value from the training dataset a baseline [MB20 LELIS).
In order to efficiently sample, D typically assigns the same density to subsets of the same size. In general, variance scales with 1/ V|S. ie., only the inverse root of the number of samples.

---

Monte Carlo (MC)
Maxinum Sample Reuse (MSR)
Linear MSR
Predicted Value (normallzzed) lted]
1.0
0.5
0.5
0.5
0.0
0.0
0.0
-0.5
0.5
-1.0
-0.5
-1.0
True Value (normalized)
True Value (normalized)
True Value (normalized)
Adult 12)
Real Estate (n 15)
Correluted (p
NIIANES (n- 79)
Quality (n 12)
Sharing 16)
Independent: (p 80)
Commmnitics 101)
Forest Fires (n- 13)
Breast Cancer (n 30)
Figure I: Predicted versus true (normalized) Shapley values for three unbiased estimators given fixed number of black-box evaluations of the value function, v. Each point represents one feature's s estimated vs true Shapley value on one dataset. The Monte Carlo estimator uses each sample to estimate only one Shapley value, but has variance that depends on the difference in values between neighboring sets, i.e., (u(S U (i)) - -ie)))=(S>> The Maximum Sample Reuse (MSR) estimator reuses samples, but has larger variance that depends Regression MSR estimators reuse samples and have smaller variance that depends on how well a learned function f fits the value function v, i..., [u(S) f(S)]² Even taking f to be linear gives excellent performance (we call this method Linear MSR). Taking f to be a decision-tred model (Tree MSR) can produce even better estimates for large sample sizes, as shown in Figure 2
the magnitude of the values, i.e., [o(S)]² Our
are the unique solution to a particular overdetermined linear regression problem [CGKR88
( ........ pn
arg min (xxx))=v(l)))-vr
||Ax bllw,
(4)
where A IR:2" a specific structured matrix whose rows correspond to sets S [n], b E R²" vector whose entries equal v(S) v0), and || ||w is weighted & norm.
The ubiquitous Kernel SHAP algorithm L CL21 takes advantage of the regression formulation by approximately solving Equation 4 using subsample of constraints (and corresponding entries in b), each of which requires evaluating v(S) for a single subset S. This approach was recently improved by incorporating leverage score sampling [SIII, resulting in the state-of tite--ofthe state-of-the-ate th-the-rrt art Leverage SHAP method [W25]]. In addition to inherent sample reuse, the empirical effectiveness of Kernel SHAP and Leverage SHAP seems related to the fact that the accuracy of both methods depends on how well is approximated by a linear function. Indeed, it can be shown that if exactly linear, both methods return exact Shapley values after just n function evaluations [MW25] However, even when is not linear, there are theoretical guarantees on the performance Kernel SHAP and Leverage SHAP MW25 CSV+25)
The Kernel SHAP approach has been extended Banzhaf values [LWK+25) thanks similarly elegant regression formulation [HH22] However, extensions to more general probabilistic values have been less effective, failing to outperform Monte Carlo methods [LZL 22 LY24a LY24b]. A key challenge is that, due to the lack of an efficiency property. generalized linear regression formulations for probabilistic values typically require estimating the sum of these values, which introduces another source of error [RVZ98]. Moreover, even for Shapley and Banzhaf values, drawback of regression- based methods is that they fail to provide an unbiased estimate for each Φ;-
Attempts to fix this issue have generally led to estimates with much higher variance [C.21].
1.2 Our Contributions
We introduce a method called Regression MSR for leveraging regression to approximate probabilistic values. In contrast to previous work regression methods, Regression MSR leads to estimates that
3

---

Shapley Values: Error vs Sample Complexity
Adult (x 12)
Forest Fires
13)
Real Estate (n 15)
Bike Sharing (n 16)
10"
10
10
fp-error
10
10"
10
10-2
10-3
10-3
10
10
10-6
10
10
10
10"
10
10"
Breast Cancer (n 30)
Independent (n
60)
NHAANES (0 79)
Commuunities (P 101)
10
10
10
10
10
10
10
10-5
10
10
10
10
Nomber of Samples (m)
Number Samples (m)
Number of Samples (m)
Number of Samples (m)
LinearMSIt
TrecMSH
KeruelSHAP
PermatationSSAP
LeverageSHHAP
Figure 2: Average ey-error between estimated and true Shapley values as function of sample size m (number of evaluations of v) for various datasets. The lines report the mean error over 100 runs, and m = 10n, 20n, 40n, 80n, 160n, 320n, 640n. Linear MSR consistently performs comparably to the prior state-of-the-ar Leverage SHAP. Meanwhile, the performance Tree MSR depends on how well the tree-based model approximates the value function; with more samples, it can even outperform Leverage SHAP by several orders of magnitude.
are unbiased and easily extend to all probabilistic values. Moreover, the method can take advantage of non-linear regression methods like XGBoost (CG16) and other decision-tree models.
Instead of starting with a custom linear regression formulation for given type of probabilistic value, Regression MSR uses regression as variance reduction method for Monte Carlo approximation, and specifically, for the Maximum Sample Reuse method introduced earlier. Concretely, learning from small number of random subsets, we start by approximating the value function using simpler function, f. Using the fact that probabilistic values are linear- - i.e. (;(v) Φi(s) + dilv - for any we propose to return the estimator:
1 S
[(e(s)- f(S) Pls 1/ 8) Pis 1 S] D(S)
= o +
(5)
SES
Since the MSR estimator (second term) is consistent - i.e., returns the true Shapley values when on all subsets the Regression MSR estimator is too. Further, it can be checked that E [ = Φ;
for any fixed f (e.g., one learned using samples not in S). That is, the method is unbiased. Moreover, like the biased Kernel and Leverage SHAP methods, the variance of &. depends on [w(()) [()]
(see Section 2 for details). So, our method is more accurate than the standard MSR method when can obtain a good approximation to v.
The benefit of our approach is clear in Figure I where we take f to be a linear approximation to e and use Equation (5) to estimate Shapley values. However, there is also the potential to go beyond linear approximations. Observe that, evaluate d, the function f does not need to be a linear. Indeed, we can use any approximation for which the (f) term in Equation (5) can be computed efficiently. That is, any function family that admits efficient probabilistic value computation. Importantly, this includes a wide variety of functions based on decision trees. Concretely, in Appendix C we show how to efficiently compute probabilistic values for any linear mixture of decision trees
*Efficient methods for computing Shapley and Banzhaf values for decision trees were previously known LELI8 LEC KMM 22). However, they were based on particular summation property that does not hold for general probabilistic values; if value function only has contributions from n' < players, the

---

We leverage this observation to learn tree-based approximations to using powerful models like XGBoost (for the purposes of our experiments, we call this variant of our algorithm Tree MSR). For the well-studied Shapley values, we find that Tree MSR achieves state-of-the-an performance, especially when there are enough samples for the tree-based model to learn an accurate fit, see e.g.. Figure 2 In particular, Tree MSR can yield estimates with average error that is 2.6 lower than the prior state-of-the-arr Leverage SHAP estimator (see Table DT. For general probabilistic values, Tree MSR gives up to 215x lower average error than the best estimator from prior work (see Figure and Table 3).
Concurrent to our work, [BAK 25 introduce Proxy SPEX for estimating probabilistic values. Like Tree MSR, they fit gradient boosted trees to the value function v. However, instead of computing the probabilistic values of the trees, they extract the most influential Fourier terms and compute the probabilistic values of the Fourier representation. In terms of performance, Proxy SPEX outperforms Kernel SHAP for the low sample regime with budget < 5n, but Kernel SHAP is more accurate for moderate and larger sample regimes [BAK 25). Tree MSR underperforms Kernel SHAP (and hence Proxy SPEX) in the low sample regime, but generally outperforms Leverage SHAP in larger sample regimes (see e.g., Figure 2). Proxy SPEX is neither consistent nor unbiased, unlike Regression MSR.
2 Regression MSR
In this section, we present our Regression MSR method, which combines the benefits of Monte Carlo and regression-basee estimators. In particular, Regression MSR produces estimates that are unbiased (like Monte Carlo methods), reuses every sample for each estimate (like Maximum Sample Reuse and regression- methods), and achieves lower variance when a learned approximation is accurate (like regression- based methods). Unlike prior linear regression- based methods, Regression MSR successfully extends to any probabilistic value, and can harness the accuracy of richer function classes like regression trees.
The pseudocode of Regression MSR appears in Algorithm I We separate the samples used to train from the samples in the final prediction; this both ensures the estimator is unbiased, and allows us to give strong theoretical guarantees in Theorem 2.1 First, the algorithm partitions m samples into i collections of samples 5(1), , S(k), The algorithm then proceeds in three phases, repeated for each S(e); During the first phase, Regression MSR learns an approximation r((e to the value function v, on all samples that are not in S(f) In the second phase, the probabilistic values db (f())) are computed for all i. (We run Regression MSR with linear or tree-based methods so that computing their probabilistic values efficient.) Finally, the algorithm uses the learned function to reduce the variance of the MSR estimates on the samples in S(C)
Theorem 2.1 gives theoretical guarantees on the performance of Regression MSR. For a constant error constraint and failure probability 5 > 0, Regression MSR uses linear number of samples to produce estimates with f2-norm error that depends on a natural weighted squared error between the value function and worst learned function. We present the guarantee for any sampling distribution 'D over subsets, and, helow, discuss our suggested choice of this distribution.
Theorem 2.1 (Regression-Addustmen Guarantee). The estimates produced by Algoritim D are
unbiased estimates of the probabilistic values. Further, let c, > O, and fmax be the learned functionn f(() with largest generalization error over E 1k]. When run with m O(n c8 samples, Algorithm 7 prrouuess estimates that satisfy, with probability 5,
1
- 211 S c Σ (u(S) fmax (S)) Pis) (1
+ PiS1-1 D(S)
(6)
SCIN]
Algorithm [ can be used to make the estimates of any regression-based estimator unbiased while preserving its variance. To this end, we purposefully do not specify the sampling distribution D or the function class f. We next discuss two choices for how to select the model, f. and collect samples.
Shapley/Banzhal value on the induced game of those n' players is the same as the Shapley/Banzhat value on the original value function with all n players. Our approach in Appendix Iip based on an alternative way of viewing based models that avoids the need for this property.
5

---

Algorithm 1 Regression Maximum Sample Reuse
1: Input: number of players n, number of samples m, value function v 2 IR, probabilistic
weights p [0, 1]", probability density function for sampling D 2 [0. 1]. number of splits
k
2: Output: Estimated probabilistic values ői...., on
3: Sample S, consisting of m subsets drawn with (or without) replacement from D.
4: Randomly partition S into S(2), st.,,...,,,,. S(K)
5: for & E {I,...,A) k) do
6: For i E [n), initialize (!!)) +- 0.
7: Learn f(() 2/m) + R to minimize loss
Σ
(u(S) - f(S))²
8: For all i [n]. compute probabilistic values (.((()). Efficient for linear/tree- based models.
9: For all i E [n).
compute
(u(S) - / (S)) PISI PIs|- 1/i S]
P(s) 1 $ S]
8 + )=((0)
|ste]
D(S)
SEs
10: end for
11: For all i [n). compute final estimate oy - 1/2 E. 300)
12: return Ōi.....d. on
Linear MSR The simplest choice for f is a linear model. As discussed in the introduction, there is extensive prior work on special linear regression formulations for Shapley values [CGKR88] LL17
CL21 MW25). Using linear function for variance reduction in MSR offers natural alternative to these methods, and adds negligible computational overhead, yet tends show superior performance on most datasets (see, e.g., TT. When applying the method to Shapley values specifically, we use the existing state-of-the art Leverage SHAP method (which samples via leverage scores) to the learned function. We similarly use the linear regression-bass bbseddddaabdde--- Kernel Banzhaf algorithm [LWK <WK+25 25 when estimating Banzhaf values. For general probabilistic values, Linear MSR fits a linear model with the sampling distribution described below, and uses its predictions to adjust the final estimates.
Tree MSR Beyond linear models, tree-based regression models like XGBoost can learn more accurate approximations. As discussed in the introduction, it is known how to efficiently compute the Shapley values (LEC-20) and Banzhaf values [KMM 22] of trees; however, it was previously unclear how to generalize these approaches to probabilistic values: the Shapley/Banzhatt methods use the property that the probabilistic value of value function on n players is the probabilistic value of the extended value function on n'' >> players, as long as the additional nı' players always contribute nothing. This property unfortunately does not hold for all probabilistic values; e.g., consider probabilistic weights that are independently sampled (and normalized) for each number of players and n'. Instead, efficiently computing the probabilistic values of trees requires a subtly different approach, which we describe in Appendix C like XGBoost and efficiently compute its probabilistic values for the final estimate.
With this approach in hand, we can fit e with a tree-based model
Sampling Distribution When Algorithm 1 is not run on top of another regression- based estimator, we choose the sampling distribution so that the function ʃ is directly trained to minimize the error bound in Theorem 2.1 That is, we sample each set with probability proportional to
S
S
V pis (1
+ pisl-1
Then the error bound in Theorem 2.1 is proportional to
(o(S) (0()) [(S)} /p8s
|S|
S
Σ scInl
p
pis
n

---

Table Summary statistics of the average E--norm error between estimated and true Shapley values for all datasets listed in Appendix G All estimators are run with m = 40n samples. Tree MSR achieves average error that 6.5x lower than Permutation SHAP, 3.8x x lower than Kernel SHAP, and 2.6x lower than the prior state-of-the-art Leverage SHAP. We emphasize that Tree MSR gives even better performance for larger sample sizes, as shown Figure 2
We follow Olympic medal
convention:
gold silver and bronze signify first, second and third best performance, respectively.
Adolt
Forss Fires
Real Kstale
Bike Sharing
Breast Cancer
Independent
NHANES
Communtics
Mean
LinrarMSR
Mean
1.18 1188220 10
337 x 19
200 x 19
5.07 x 10
109 20
9.49 10
2.73 X 10
1.17% x 10
9.51 10
1st Quatilee
2.99 10-1
4.72 x 10-1
2.46 x 10-1
9.72 10
2,14 10
5:58 10
2.18 x 10-10
4.76 x 10-5
1.98 10-4
2nd Quirilee
7.67 10
x 10
5.1 x 10
2.85
1,02
6.61
2,40
0.46 10
6,00
Quatile
1.2
10-6
6,7
10-1
10
TreeMMR
6.7
1:07 x
2.04
1.08
1:96
7:00
Quartile
1.29
1.52 x 10
0.50 x 10-3
6.25 10
2:37 10
2.40 10-3
2.00
1.78 x 10
1.15 10
2nd Quartile
4.12 10
8.56 x 10
1:97 x 10
1:28
5.01 30
8:21
8.89
8.58 x 10
2.50
Rel Quavtile
9.08
x 10
1:00 x 10
1.40 x 10
2.46 10-3
1,25 x 10
1.50 x 10
3.91 10
5.70 x 10
5.00
10
KewnelSHEAP
Mean
4.50 10-3
2.58 x 10-5
1.38 x 10-7
6:12 10
2.01 10-3
1.97 10-4
4.08 10-3
1.50 x 10m
1.64 10-3
Quattile
5.1. 10
3.08 10-1
x 10
1.40
6.87 10
1.00 10
1.00
7/00 10-1
3:47 10
Quarile
10
10-1
10-3
10
10
10-
10
Quattlee
2.84 10
10-6
10-
10
10-
PermstationSAA
Mian
4.80
1:25 x 10-4
5.58 x 10-7
1.51 10-2
1.23 10-3
1.90 10-1
3:43 10-3
2.14 x 10-4
2.78 10-3
1st Quaztile
1.05 10
9.54 x 10-1
3.54 x 10
3.13 10-3
2.97 10
8:96 10
1.00
5.87 x 10
6.00
10
2nd Quattile
3.84 10
4.83 x 10
4:00 x 10
6.97 10
1,05 10
1.70 x
2:30 10
1.61 x 10
1.40
3rd Quattile
7.68 10
1,52 x 10
2:60 x 10
1.02 10
1.01 10
2,77 x 10
2.00 x 10
2.78 x 10
3.68
x 100
HeerggeSHHF
Moan
1:38 10
3.71 x 10-5
1/41 10-3
6.32 10-3
1.08 10
9/52 10-1
2:53 10
1.15 x 10
1:13 10
Quatilee
3.07 10
7,88 10
1.05
2.7
10
2.20
Quatile
10-5
5:21 10-5
10-5
Quattile
1.02
7,03
1,46
2,02
which, by design, is the expected loss used train f.
Bias vs. Accuracy vs. Runtime Regression MSR produces unbiased estimates by training k functions, each on (k= - 1)/k fraction of the available samples and evaluating on the held-out I/k. This creates a trade-off: increasing & improves accuracy (each function has larger training set) but raises computational cost. In our experiments, we set k 10, meaning that each function trained on 90% of the data. Thanks to efficient solvers (e.g., least squares or XGBoost), this setup maintains fast runtimes while delivering high accuracy.
Practical Simplification Unless a small bias term (similar to that of Leverage SHAP or Kernel SHAP) is unacceptable, we recommend simplifying the Regression MSR algorithm: Train a single function- and build the final estimate with it on all samples. While this introduces a small bias (and breaks the theoretical guarantees), the resulting algorithm runs faster and is generally more accurate than the version described in this paper.
3 Experiments
In this section, we describe our experiments on eight datasets. Overall, we find that Linear MSR and Tree MSR give state-of- of-the-art performance for almost all datasets and sample budgets
Value Function For evaluation, we focus the explainable AI feature attribution task, but emphasize that our methods can be applied to any application involving probabilistic values, as we only require black-box access to the value function U. Concretely, train a model on dataset, and attribute the prediction the model makes on a given explicand point x E R to its input features. We consider the interventional definition of v, where the explanation is relative
a baseline point xb E IR: For a set S, let x be the point where the ith feature is x if i E S and x otherwise. Then, the value function v(S) is the model's prediction on x There is also a conditional version of feature attribution, where the features not in S are drawn from background dataset [LL.7 LEL18]. However, we choose to focus on the interventional version since it is more efficient to compute v(5), and the resulting probabilistic values more interpretable [JB20)]
Ground Truth Probabilistic Values For small datasets with n < 30, we use a neural network model and compute the true probabilistic values through enumeration. For larger datasets with 2 30 where
'The code is available at http:p///g..ttboooo/////aaa/ttte
7

---

Probsbilistic Values: Error vs Sample Complexity (Regression Forest Ground Truth)
Symmetric Beta
Shapley
B(2,2)
B(4
B(8,8)
10
10
100
10
10
10
10'
Asyimmetric Heta
Shapley
((1.2)
BB(14)
B((18)
10
10-1
10
10"
10
10-4
10
101
Weigitted Hanzhaf
Banshaf
WB 6)
WB(0.7)
WII(O.)
10-1
10a
10
10
10
10
10-4-
Sample Multipiier (mn/in)
Sumple Multiplier (m//n)
Sample Multiglier (m//a)
Sample Multiiilee (10//))
LinewrMSR TreMMR
OFA
GELS ARM
WSHP
KerneSHHA
AMB KeruelBenzuaal
WSL
SHAP
PermatationSHAP
Figure 3: Average error between the estimated and true probabilistic values as a function of sample size. Each subplot shows results for different probabilistic value with the error averaged over all large datasets (n 2 30), for which we used the tree-based method described in Appendix [ The lines report the mean error over 10 runs. Tree MSR gives the best performance, often by several orders of magnitude when m is large.
Table 2: Summary statistics of the fn-norm error between estimated and true probabilistic values
when m 40n. We summarize the error over large datasets (n > 30), for which we use the tree-based method described in Appendix Cto compute the true probabilistic values. On average over all probabilistic values, Tree MSR produces estimates with mean error that is 215x lower than the best estimator from prior work.
RICA
WIRESS
WHRTR
WIBEIT
WISTES
WIREES
TTsarttst
la Quanti
6:00 10-
6-70-3 30
5.8%
6.55
10-4
2013-
3 10-
5.91% Io
T 10-
1.20 x
353
1.5
In-
2.41 In
2nd
4.42
13
7.5
1
Quartla
3.11
Quantic
10
0.53 0177
1.25
1.7
4.00x 2214
L85
1.22 10-1
525 10
ur
Quart
3:03
0.1%
Max
3.57
>
3.11
13
1.24
Quanti
10-3
556
5-66-1 10-
6.37
10-2
Znd Quatiz
5.00 30
3.00 33
x 01-4
5 01
1 10
7.27 2-13
8 1311
4.50 11
5 10
0:21 8 30
4.50 50
0.94 ur
WSL
Moar
6-30 10
10.
333
6.40
6:30
9.33
1:30x
1.00
10-1
10-1
Tel Quatii
1 10
015. 30-1
0.07x 10-2
4.5 10
1.00
10-3
5:50 x 13-3
01 10-2
1.37 10-1
1.0% 10
1.00
10-1
0.00 10
0.69 (p-1
0.11 10
Quarta
K.5x
5.15
9.50
234
2:00
3.00
1.79
5,33
Muse
2 30
3.13 30
1 00
1,34 un
1 10
3 2333
1.37 10
1.30 1
1.30 2011
3.15 30
3.75 53
5.74 u0
1.75 mr
2nd Quartz
30
33
1.53 50
7.45 10
1
10
1.20 13
9.84
- L0
10
Cuerite
$15
10
3.5.
3874
1.55
2.41x
1.30
1.3
1991
316.
2.55 197
2.81
Mos
100 10
0.22 33
0..5 00
6.85x 10
1/00 10
8.4. 1.4
1.33 10.
8.8 10
110
Quanti
6.00
1.75
3.22
1:25
9:33 23
7.84-
3.8
3.12
9.50 53
4.13
3ed Duande
1.40 10
1.15 22
7.35% 00
8.55 x 10
1.70 10-1
4:45 1m
6.33 16
6:55 10
5.83 02
3.40 52
16355
0.75 10
Mase
314
8.23% 1012
1.66 30
1.00 53
2.35% 10
bet Quantie
3.14-
0.2
6.00
5:0
2.0
031 00
03.9
2.55
Iud Duante
2:00
055
1 01
1.2
1.00-00
1 10
110 10
1
2.5 10
exact enumeration infeasible, we use a random forest model and compute the true probabilistic values using the algorithm described in Appendix C (Please see Appendix G for summary of the datasets in our experiments.) We emphasize that our method for computing the probabilistic values of trees enables the first experiments medium to large datasets where we can compare the estimates
8

---

to the ground truth probabilistic values. Such experiments were previously done for Shapley and Banzhaf values [M255 LWK 25], but not for other probabilistic values.
Baselines We compare I Linear MSR and Tree MSR to a wide variety of probabilistic value estimators from prior work. For the popular task of estimating Shapley values, we focus on the most effective estimators for general value functions i... Permutation SHAP [CGT09], Kernel SHAP [LL17 CL21] and Leverage SHAP [MW25]. We use the optimized implementations of Permutation SHAP and Kernel SHAP in the ubiquitous SHAP library for parity (LLIZ] For estimating probabilistic values, there has been substantial recent interest in designing estimators [KZ22a KZ22b LZL WI23
KBMH24 LY24al LY24b). These estimators generally use the standard Monte Carlo approach, apply the Maximum Sample Reuse idea, or extend linear regression- based methods. We provide a
description of each in Appendix [
Error and Uncertainty We measure the error between the true probabilistic values & and the estimated probabilistic values & with the l-- f--norm error | / / - All of our tables and figures report summary statistics over at least 10 runs. In the tables, we report the mean, first quartile, median, and third quartiles of the error. (We do not report +/- standard deviation because these are often negative for the small errors in our experiments.) In the figures, we report the mean error.
Implementation Details We use scikit-learn [PVG+11] and XGBoost [CGI6] for training our models. For the implementations of Permutation SHAP and Kernel SHAP, we use the SHAP library [L.17] Please see Appendix G for details on how accessed each dataset. All of our experiments are run on a machine with an Apple M2 chip and 8GB RAM.
We first describe our experiments on the popular task of estimating Shapley values. 2 shows estimator performance by sample size, and Table hiihhlights the corresponding uncertainty statistics when each estimator is run with the prior state-of-the-an Leverage SHAP by making its estimates unbiased, but the gain is marginal. In contrast, the performance Tree MSR depends on how well the tree-based approximation fits the underlying value function v. When the number of samples is smaller, Tree MSR is comparable to prior Shapley value estimators; however, as the number of samples grows, the tree-based model becomes more accurate and Tree MSR often gives the best performance, sometimes by orders of magnitude. As be seen in Table [ Tree MSR can give average error that is 2.6 lower than the prior state-of-the-art Leverage SHAP, when m = 40n. For larger sample sizes, Tree MSR outperforms Leverage SHAP by an even wider margin, shown in Figure 2
40n samples. We find that Linear MSR generally improves
Beyond estimating Shapley values, we run experiments on estimating the more general beta Shapley values and weighted Banzhaf values (see Appendix B for definitions). Figure 6 shows estimator performance by sample size for small datasets (where we can feasibly compute the true probabilistic values of neural networks), and Table highlights the corresponding uncertainty statistics when each estimator is run with m = 40n samples. We present the analogous results for smaller datasets (where we can exactly compute the probabilistic values of neural networks) in Figure and Table 3 in Appendix E We find that Linear MSR generally plateaus as the number of samples increases. In contrast, Tree MSR gives the best performance across the board, with the gap the next best estimator widening with the number of samples. We confirm this finding in Figure 4 As can be seen in Table 3 Tree MSR can give average error that is 215x lower than the best probabilistic value estimator from prior work.
We provide additional experiments on the effect of noisy access to the value function in Appendix F Figures 7 and suggest that Tree MSR is particularly resilient to noise.
Limitations and Broader Impacts
The performance of our methods depends on the underlying fit of the learned model. When the dataset is structured the number of samples is large, the learned model is accurate and the estimators are, too. However, for datasets with less structure or in sample-constrainet settings, the performance of estimators can worsen.
The primary application of our work is in explainable AI, where we seek to understand how features and data points contribute to the performance of machine learning models. We expect the broader impact of our work to better model explanations, and we do not see substantial negative risks as result of our research.

---

Generalization Error (All Datasets)
Linear Value Function
Rondt Value Fuuction
Neural Network Value Function
10
10-
4p-rrtor
10-2
10
10-13
10
10-2
10
10
10
10F
10
10
Sample Multiplee (m/n)
Sample Multipāer (mn (n)
Sample Multiplier (yn (n)
Learned Linear Model f
Learned HandomEbees Model f
Learned XGHoost Model f
Figure Generalization error between value function and learned model f by sample size, averaged over all datasets. When the base model is linear, the learned linear model quickly fits it to machine precision. When the base model random forest or neural network. the error of the linear model plateaus while the random forest and XGBoost learned models continue to improve. This phenomenon reflected Figures and O the performance of Tree MSR continues improve with the number of samples while Linear MSR plateaus.
Acknowledgments and Disclosure of Funding
Witter was supported by NSF Graduate Research Fellowship Grant No. DGE-2234660. Liu was partially supported by NSF Awards IIS-2106885 and the DARPA ASKEM and ARPA-H BDF programs. Musco partially supported by NSF Award CCF-2045590.
References
[BAK+25] Landon Butler, Abhineet Agarwal, Justin Singh Kang, Yigit Efe Erginbas, Bin Yu, and Kannan Ramchandran. Proxyspex: Inference-efffcient interpretability via sparse feature interactions in llms. arXiv preprint 2.Xiv:2505.17495. 2025.
[BI64] John F Banzhaf III. Weighted voting doesn't work: A mathematical analysis. Rutgers L. Rev, 19:317, 1964.
[Cen23] Centers for Disease Control and Prevention. National health and nutrition examination survey (nhanes). https:///wwn. cdc. www.g//wc///hnaness/./ 2023. https://wwww
[CG16] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd aem sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
[CGKR88] A Charnes, B Golany, M Keane, and J Rousseau. Extremal principle solutions of games in characteristic function form: core, chebychev and shapley value generalizations. Econometrics of planning and efficiency, pages 123-133, 1988.
[CGT09] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the shapley value based on sampling. Computers & Operations Research, 36(5):1726-1733 1730, 2009.
[CL21] Ian Covert and Su-In Lee. Improving KernelSHAP: Practical Shapley value estimation using linear regression. In Proceedings of The 24th International Conference Artificial Intelligence and Statistics, pages 3457-3465, 2021.
[CM07] Paulo Cortez and Anibal Morais. A data mining approach to predict forest fires using metcorological data. Proceedings of the 13th EPIA, 7:512-523, 2007.
[CSV+25] Tyler Chen, Akshay Seshadri, Mattia Villani, Pradeep Niroula, Shouvanik Chakrabarti, Archan Ray, Pranav Deshpande, Romina Yalovetzky, Marco Pistoia, and Niraj Kumar. unified framework for provably efficient algorithms to estimate shapley values. arXiv preprint arXiv:2506.052 05216, 2025.
10

---

[FTG14] Hadi Tanaee-T and João Gama. Event labeling combining ensemble detectors and background knowledge. In Progress in Artificial Intelligence (EPIA). pages 1-15. Springer, 2014.
[GZ19] Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning, pages 2242-2251. PMLR, 2019.
[HH92] Peter L Hammer and Ron Holzman. Approximations of pseudo-boolcan functions; applications to game theory. Zeitschrift für Operations Research, 36(1):3-21, 1992.
[Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, (3(301):13-333) 1963.
[JMB20] Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature relevance quantifi- cation in explainable ai: causal problem. In International Conference on artificial intelligence and statistics, pages 2907-2916. PMLR, 2020.
[KMM224] Patrick Kolpaczki. Viktor Bengs. Maximilian Muschalik, and Eyke Hüllermeier. Ap- proximating the shapley value without marginal contributions. In Proceedings of the AAAI conference on Artificial Intelligence, volume 38, pages 13246-13255, 2024.
[KMM 22] Adam Karezmarz, Tomasz Michalak, Anish Mukherjee, Piotr Sankowski, and Piotr Wygocki. Improved feature importance computation for tree models based on the banzhaf value. In Uncertainty in Artificial Intelligence, pages 969-9799 PMLR, 2022.
[Koh96] Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: a decision-tree hybrid. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD), pages 202-207, 1996.
[KZ22a] Yongchan Kwon and James Zou. Beta shapley: unified and noise-reduced data valuation framework for machine learning. In Gustau Camps-Valee Francisco R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 8780-8802. PMLR, 28-30 Mar 2022.
[KZ22b] Yongchan Kwon and James Y Zou. Weightedshap: analyzing and improving shap- ley based feature attributions. Advances in Neural Information Processing Systems, 35:34363-34376, 2022.
[LEC*20] Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, 2(1):56-67, 2020.
[LEL18] Scott M Lundberg, Gabriel G Erion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv: 1802.00888. 2018
[LL17] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
[LWK+25] Yurong Liu, R. Teal Witter, Flip Korn, Tarfah Alrashed, Dimitris Paparas, Christopher Musco, and Juliana Freire. Kernel banzhaf: fast and robust estimator for banzhaf values, 2025.
[LY24a] Weida Li and Yaoliang Yu. Faster approximation of probabilistic and distributional values via least squares. In The Twelfth International Conference on Learning Repre- sentations, 2024.
[LY24b] Weida Li and Yaoliang Yu. One sample fits all: Approximating all probabilistic values simultaneously and efficiently. Advances in Neural Information Processing Systems, 2024.
11

---

[LY24c] Weida Li and Yaoliang Yu. Robust data valuation with weighted banzhaf values. Advances in Neural Information Processing Systems, 36, 2024.
[2] Jinkun Lin, Anqi Zhang, Mathias Lécuyer, Jinyang Li, Aurojit Panda, and Siddhartha Sen. Measuring the effect of training data on deep learning predictions via randomized experiments. In International Conference on Machine Learning, pages 13468 13468-13504 13504. PMLR, 2022.
[MW25] Christopher Musco and R Teal Witter. Provably accurate shapley value estimation via leverage score sampling. In International conference on learning representations, 2025,
[Pen46] Lionel S Penrose. The elementary statistics of majority voting. Journal of the Royal Statistical Society, 109(1):33-57, 1946.
[1V Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Thirion, O. Grisel, M. Blon- del, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28835 2011.
[RC02] Michael Redmond and Corinna Cortes. Communities and crime data set. Technical report, UCI Machine Learning Repository, 2002. m1 ml/dad //ddaaates//eee cowaasuett/oomuiiieeeeee taeruuuniiiiiesaanrrririii
ics. uci edu/
[RV798] Luis M Ruiz, Federico Valenciano, and Jose M Zarzuelo. The family of least square values for transferable utility games. Games and Economic Behavior, 24(1-2):109-130, 1998.
[Sar06] Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006.
[Sha51] Lloyd Shapley. Notes on the n-person game-ii: The value of an n-person game. Research Memorandum RM-670, RAND Corporation, 1951.
[SK10] Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classi- fications using game theory. The Journal of Machine Learning Research, 11:1-18, 2010.
[SSI1] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913-1922 2011.
[SWM93] WN Street, WH Wolberg, and OL Mangasarian. Nuclear feature extraction for breast tumor diagnosis. IS&TSPIE 1993 International Symposium on Electronic Imaging: Science and Technology, 1905:861-870, 1993.
[Web88] Robert James Weber. Probabilistic values for games, page 101-120. Cambridge University Press, 1988.
[WJ23] Jiachen T. Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 0188-6421. PMLR, 25-27 Apr 2023.
[WMS125] Jiachen Wang, Prateek Mittal, Dawn Song, and Ruoxi Jia. Data shapley in one training run. In International conference on learning representations, 2025.
[YH09] I-Cheng Yeh and Tung Hsu. Comparisons of data mining techniques for predicting real-estate prices. The International Journal of Artificial Intelligence Tools, 18(03):435- 446, 2009.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please Sections
2 and well Appendix A
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 can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation 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: Please see the Limitations and Broader Impacts section immediately before the references.
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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 well-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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 to 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Please see 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 referenced in 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 to provide short proof sketch 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please Section
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 a 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 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.
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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture 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 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 reprodueibility. 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 to 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?
14

---

Answer: [Yes]
Justification:
The
code is available at
regressionMSR
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
wttggg/dddde/euubmi..... (osiinicyyy)) for more details.
While encourage the release of code and data, 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 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
//nips. //nips.cc/ppl cc/public/guu tetggiddddeeeoeebbbiiinnnn
ssiiisoliccyyyyyy for more details.
The authors should provide instructions 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, 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 permitted.
6. Experimental setting/details
Question: 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?
Answer: [Yes]
Justification: Please Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please see Section
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror 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).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error 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 (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures 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: Please see Section
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 or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in 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: Please the Limitations and Broader Impacts section before the references.
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 socictal 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., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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:
We do not have datasets models that have a high risk of misuse.
Guidelines:
The answer NA means that the paper poses 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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: Please Appendix
G
Guidelines:
The answer NA means that the paper does 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 (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: Please the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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:
We did not conduct research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We did not conduct research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

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 if 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 development in this work does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neur// /20p://///////ooeeeeeee///////// for what should or should not be described.
19

---

A Proof of Error Bound
Theorem 2.1 (RegressionAAdiustmenn Guarantee). The estimates produced by Algorithm D are
unbiased estimates of the probabilistic values. Further, let c,6 > O, and faa be the learned functinonnctin f(0) with largest generalization ervor over E lk.. When run with m O(n 2s samples, Algorithm
7 prrduucss estimates that satisfy, with probability 1-
[5| + P 11111
SI
Σ (w()) - f (5)) Pist SC(m)
1 1-11
SE
(6)
D(5)
Proof of Theorem 2.7 We will analyze the variance when the samples are drawn with replacement.
By Theorem 4 in Hoe63]. the variance can only decrease when samples are drawn without replace- ment.
Consider e E [k]. For simplicity, suppose that |S(0] = m/k. We will first show that each estimated probabilistic value ((0) is unbiased:
B[Ø = ()) + h
Σ
1 = 8") [u(S) (S)) - s] - 1i 1i $ $1)
E
D(S)
S'ESO Sgin
= )))(((0)+ +
Σ
(e(S) (S) 51 Pls $ S))
scmm
= =
Σ (e (SS)pp|s
Σ ((
SCM|M0
Σ
(c - u(S)pps = Φi.
SCMIMM
Since 700) is unbiased, the final estimate E 2i=1 J is also unbiased by the linearity of expecta- Next, we will analyze the variance of each estimate:
tion.
Var (
22 m
Var
Σ Σ
1 ST[((S)) (()
PIs| 1i: E S
Pis 1 $ S]
D(S)
S'ESt Sc(m)
D(S)[U(S) - (S))& ( 1/i E S] P
Pist 1/; $ S) 2
m
D(S)
SC(R)
Σ (u(S) (S)) 1 E S] + ris [ S
k
m
D(S)
SCIN
Let Φ E R" and Z(t)
E RT be vectors containing the true and estimated probabilistic values,
respectively. We will analyze the random variable | ((p) By linearity of expectation, we have
Eill 1- = E Σ (b. (o--5:93
/ - -E (Ø: 3 )(0)]] Σ Varlø: ((0) Σ Varlø
where the penultimate equality follows because EI [00] oi and the final equality follows because 6, is a constant with respect to the randomness of the estimator. Plugging in Equation (7), we get
k [u(S) ((0 pis
li E S] + ris L $ S]
B|| - 19
<
D(S)
==1
SCin)
k
(o(S) ((() (5))2 Pist
P(s) Pisi-111 |S| + pss) (n- - |S|)
m
D(S)
SC mn)
k
(o(S) f Smax f (5))
pis 1181 + piss (n 1S|)
(8)
m
D(S)
SC
20

---

where
lu(S) ,lر (19) -is
Pis (n |s|)
Smax == f((),
where e" = arg
D(S)
8E(R]
(C(m)
We now apply Markov's inequality ||
13 for each &
Pr
110 - 122 Ell x 88'
We are interested in the final estimate o- probability most k8'
1 Ei= お(0) By the Union Bound, have, with
1 3
Bll 11.
By the triangle inequality, setting 8' ö/k, and taking the complement, we have, with probability
1 1-d 6,
k|l - क|| S
| x
(by triangle inequality)
8=1
h Bllld 1
(by setting 8 = 8/kc)
8
(ss + ss -S1)
h h
(u(S) fmar (f))2 fmax
$ k
(by Equation
8
D(S)
Sg(M)
Then, with probability 1- 8,
h: k
(o(S) fmax (S) Pis |S| + pis] (n |S|)
| - --1122-
Ō SCin]
D(S)
The theorem statement follows by setting k2 c6 0
21

---

B Beta Shapley and Weighted Banzhaf Values
Probabilistic values satisfy three intuitive properties:
Linearity:
The probabilistic value of linear combination of value functions is the linear combination of the probabilistic values for each value function i.c., di(av + bw) = av:(v)
by: (w) for real values a, b E R and games v, w : 2 + IR.
Null Player: The probabilistic value for a player that has no effect on any coalition is i.e. if u(S U (x}) = u(S) for all S then Φ; 0.
Symmetry: If two players contribute equally to all coalitions then they have the same probabilistic value i.e., if vSS u {i}) v(S U (i)) for all S then di = Øz.
In addition to these three properties, Shapley and Banzhaf values satisfy the efficiency and 2-efficiency properties, respectively:
The sum of probabilistic values is the difference between the whole coalition and the empty set i... Σi=1 Ø; = v([z)) - ((). Efficiency is desirable in settings where we want to attribute the value v((n)) v0) to each player e.g., model prediction explanation cost-sharing.
Efficiency:
2-Efficiency: Let be a game where i and j are combined into a single player (i. That is, v' is defined on 1 players where the and players in are always considered together; effectively, o' is only defined on subsets that contain both i and j or contain neither nor j. The 2-efficiency property requires that (v(v) + (v) = (ن,,)) (v") for all i, 2- Efficiency is desirable in settings where players can be combined into subgroups e.g., federated learning with client aggregation games with alliances between players.
Shapley values are the most popular probabilistic value, in part because they are the only probabilistic value satisfy the efficiency property [Sha5]]. The probabilistic weights for Shapley values are P|s| = ( (
which weights all set sizes equally.
The efficiency property is useful in settings where we want to allocate the total value of the game to the players. However, efficiency is not always appropriate especially when there are non-linear interactions between players that cannot be attributed to individuals. For these cases, more appropriate property may be 2-efficiency which requires that probabilistic values add players are merged. The only probabilistic value that satisfies 2-efficiency is the Banzhaf value [Pen46 B164] The probabilistic weight for Banzhaf values is P|s 1/2"-1, which weights all sets equally.
Symmetric Beta Shapley 10)
Asymmetric Beta Shapley m==00 10)
Weighted Banchaf (n
10-1
Shapley
102
10a
B(2,2)
B64,4)
10-7
B(16.6)
10-1
Banchw!
10
B(1.2)
10-4
WB10
B(3.4)
10a0
8(1.8)
WBrO.8)
10
10
83116K
Wi:0.4)
Figure 5: Probabilistic values by subset size for 10. Beta Shapley values B(a, ()) generalize Shapley values for a, 3 E [1, oo); increasing both a and / flattens beta Shapley values while increasing just (or just 3) tilts beta Shapley values. Weighted Banzhaf values WB(p) generalize Banzhaf values for E (0, 1); increasing (or decreasing) p tilts weighted Banzhaf values.
Both Shapley and Banzhaf values have been generalized to beta Shapley values KZ22al and weighted Banzhaf values LY24c). respectively. Figure 5 plots Pis| for various beta Shapley and weighted Banzhaf values when n = 10. Beta Shapley values are defined by two parameters a, B [1, oo). In particular, the probabilistic weight is
Beta([S) + 8,n - |S] - 11111+0 1+
Beta(a, B)
22

---

Setting 3 = recovers Shapley values. Weighted Banzhaf values are defined by one parameter p E (0, 1). In particular, the probabilistic weight
p (1 151-1
Setting p recovers Banzhaf values.
23

---

C Computing Probabilistic Values of Tree-based Models
In this section, we show how efficiently compute the probabilistic values of tree when the value function is interventional feature attribution. Unfortunately, we cannot directly generalize analogous algorithms for Shapley and Banzhaf values [LL17 LEC+ 20, KMM+22 22], since they uses a property which does not hold for all probabilistic values. In particular, prior approaches assume that if a value function only has contributions from n' n players, the Shapley/Banzhat value on the induced game of those n' players is the same as the Shapley/Banzhaf value on the original value function with all players. Our approach based on an alternative way of viewing tree-based models that avoids the need for this property.
Consider the value function v : 2 + IR induced by a tree with explicand x" and baseline x². We decompose into sum of path value functions {uP) p where each vP 2/ + S corresponds to distinct root-to-leaf path P. In particular,
f leaf value of P if S follows path P on x x²,
vSS) = Σ 1 (S),
where (S( =
o
otherwise.
By the linearity property of probabilistic values, the contribution of feature to the full tree model e can be expressed as the sum of its contributions to each path model v.. Specifically,
Φ (v) = di Σ "
Therefore, it suffices compute o. ( for each path model vP and aggregate their contributions over all paths. To this end, we will introduce the following notation. Given probabilistic weights
p p Po, ... Pn- [0, 1)". for each path P. define
Sp as the set of features in P whose conditions are satisfied by x" but not by x",
Np p as the set features in whose conditions are satisfied by x² but not by x
Ep the final leaf value on path P.
Recall we can write the ith probabilistic value as
Φ:(0)
Σ P(s)-
Σ Pis(o(S).
Sc(n)iEs
scinlies
Using the definition of u., Sr, and Nr, we can consider di(uP) in three cases:
Case 1: i iE Sp: We need i E S in order to reach the leaf i.c., v 0 unless
Sp C S [n] \N and i E S. Then,
0e(vP)
Σ
P|S|-1 Ep
[Npl
P1-1
11
1 SSp
|Nrl /Nrl-10 (1r1-11p]] |Spl) -PP
1=1Spl
Case 2: i Np: We need i S in order to reach the leaf i.e., v P((S) 0 unless
Sp C S C [n] \ Np and i & S. Then,
n P-
NN - 1SP1) Ep
(1(1P)= = --
1 - Spl {
Σ Pi
1=|Sp
Case 3: E Np and i & Spt We reach the leaf whether E 5 or not i.e, (P(S) = -0 unless
Sp C S C [n] Np. Then,
Nrl
[p |Spl - 1) Cx
(1((P)
P1-1
- |5
sp
x
pPpl-1
n
NNl
11pp - 1
Pt
Ep
1 |Spl
1=1
24

---

C.1 TreeProb Pseudocode
Algorithm _ efficiently explores root-to-leaf paths, maintaining counters for how many times each feature has been "seen" under the explicand (ef seen) or the baseline (bf seen). When branching feature is encountered for the first time on a path, the algorithm branches into two recursive calls-one following x the other xndand updates the cardinalities 8p == |Spl or np = |Npl accordingly, depending on which feature value is consistent with the split. At each leaf node, the algorithm computes the contribution based on the current (sr,Np) and aggregates these into the overall attribution vector Φ. Algorithm
2 preserves the original complexity and traversal logic of Tree SHAP, while generalizing the reature-contribution calculation to the probabilistic formulation described above, making it applicable to any probabilistic value.
25

---

Algorithm 2 TreeProb with Interventional Feature Perturbation
1: Input: n: number players; p E [0, _]": probabilistic weights
2: Output: Exact probabilistic values @1.-...: 9n
3: function RECURSE (node, sp, np, ef seen, bf_ bf_seen)
4: if node is leaf then
R-p
5: pos_term term node.value
Σ Pi-1
Rp 8P
8p
n 11p 8p
6: term <- nole.value
3p
lmap
7: return (pos_term, term, (erg)
8: end if
node.leftchild node.rightchild
if Tee [node.feat] < node.t
9: child
otherwise
node.leftchild node.rightchild 0 then 12: return RECURSE((x__cill 8p, np, seen, be_seen)
if as [node.feat] < node.t otherwise
10: zo_child
11: lef_sseennoodee...eeeeeeeeeeeeee
13: end if
14: if bfbf_se b[_ssen[node.feat
then
15: return RECURSE(2s_chi) child, sp, np, ef seen, bf seen)
16: end if
17: af child Ts child then
18: return RECURsF(2,__hill, 8p, up, seen, be_seen)
19: else
20: ef_ssen[node..eat] + ef fe_seenfnode.feall +
(pos,. neg,) t RECURSE(z___hild sp 1, p,, seen, been) 22: ef_scen[node.feat + ef ef__seeeenodeefeeeeeee
bf 23: of b[_seen]node.feai br_eerennsoeeeeeeeeeeeee -
+1
24: (pos,, neg,) <- RECURSE(z)_child, 8p, np + 1, ef_seen, be_seen)
of seen[node..fatt
bf seen (node..e..faat -
26: Premp [node.feat] + 0remp [node.feat] + (pos, + neg,)
return (pos, + p neg, + neg,)
28: end if
end function
30: Initialize Φ +- 0
for each tree in the ensemble do
32: for each baseline x" in baselines do
33: Φremp +-
34:
RECo,, 0, 0, 0", 0")
35: + Φ + Oremp
36: end for
37: end for
38: return </(nmbeer of trees x number of baselines)
26

---

D Baselines
In this section, we describe the baselines compare against for estimating probabilistic values. These baselines broadly fall into three categories: standard Monte Carlo methods, maximum sample reuse methods, and regression methods.
For more technical description of many of these baselines, please refer to Appendix D of LY24b]
Monte Carlo Methods The standard Monte Carlo estimator estimates each probabilistic value individually by sampling each term in the summation with probability proportional its weight.
Weighted Sampling Lift (WSL) [K722a is the standard Monte Carlo, but where subsets are sampled according to the Shapley weights and reweighted to produce unbiased estimates of the probabilistic
values.
Permutation SHAP (CGT09 is similar to Monte Carlo estimates except that subsets are sampled in permutations; that is, the first element in the sampled permutation is one sampled subset, the first two elements are another sampled subset, and so on. Because each set size is weighted equally by Shapley values, sampling permutations without any reweighting gives estimates that are the Shapley values in expectation. Permutation SHAP gives close to state-of-the-arr performance.
Weighted SHAP estimator
[7222b generalizes permutation sampling approach to probabilistic value. Random permutations are drawn as before but now reweighted by the probabilistic value weights so that the final estimates are unbiased.
Maximum Sample Reuse Methods Monte Carlo methods are unbiased but inefficient the sense that they only use each sample to compute the estimates of one two probabilistic values. The key observation Maximum Sample Reuse (MSR) estimators that each probabilistic value Φ can be written two summations, methods use each sample to update every summation. First used for Banzhaf values [WJ23], MSR has since been generalized to other probabilistic values with different sampling distributions.
sets that include i and one over sets that do not. Then the MSR
Approximation without Requesting Marginals (ARM) [BMH244 is kind of MSR estimator. Half the samples are drawn with probability P while the other half are drawn with probability P)s| In order to avoid the numerical instability of reweighting, the final estimate only includes the first half' of samples if i E S and the second if i S.
One sample Fits All (OFA) [Y24b] similarly uses maximum sample reuse but samples according to a more complicated distribution.
Regression Methods A parallel line of work fits linear models / then returns the probabilistic values of f. These approaches originate for estimating Shapley values, and are based on a linear regression problem that exactly recovers the Shapley values when solved exactly (CGKR88)
Kernel SHAP [L17
samples subsets from this regression problem with probability proportional to their weighting in the regression problem.
Leverage SHAP MW25 similarly samples subsets but with probability proportional to their statistical leverage in the regression problem, resulting in state-of-the-ar Shapley value estimates and error bounds that depend on the of f to v.
Kernel Banzhaf [LWK 25 is similar to Kernel SHAP and Leverage SHAP but estimates Banzhaf values, and is based regression formulation specific to Banzhaf values (HH92)..
There is a known generalization of the Shapley value regression problem RVZ98), which, when solved exactly, recovers probabilistic values up to additive constant. Since Shapley values satisfy efficiency, this constant efficient to exactly compute for Shapley values. However, for general probabilistic values, the constant depends on the entire value function v and must be estimated, introducing another source of error.
The Generic Estimator based on Least Squares (GELS) LY24a estimates the constant by adding a dummy variable with probabilistic value 0. Instead of fitting linear function f. GELS considers the closed-form solution to the regression problem and effectively applies maximum sample reuse estimator to the underlying matrix-vector multiplication. The final estimates are adjusted by subtracting the value of the dummy variable.
27

---

The Average Marginal Effect (AME) IZL is another regression estimator that uses a different regression formulation. For probabilistic values that satisfy specific condition, the probabilistic values can be written as an infinitely tall regression problem. The estimator samples this regression problem and solves the approximate version.
28

---

E Experiments on Small Datasets with Neural Network Models
Table 3: Summary statistics of the f--norm error between estimated and true probabilistic values when m 40n. We summarize the error over small datasets (n < 30), for which the probabilistic values of neural network model can be feasibly computed. On average over all probabilistic values, Tree MSR produces estimates with mean error that is x50x lower than the best estimator from prior work.
RIZZI
BICA
B:141
WIRESS
VIBEER
Mox
1.20
8000 1072
4
144 umr
X33 up
Ouanti
1.51%
x
1-5.x
6.36%
3el Quattle
200 10
3.4 33-4
1.57% 00-9
1.1 10
150 10-1
1900
1.7%% 16
5.11 1 16
1.50 1
5.0% 05
0.13% 10
1.30% In
Maor
6:5
3.00
1:96
Quanti
7226-
1077
2314
1 D173
1
5.00
240
1.31 0877
1 187
7:2 1077
0.00
4.38 1
7:39 UPT7
Quartic
10
2.40
2.45
1,59
1.51
1.54
1.75 10
1
10
30
03
1.75 11
TOE
Quanttv
2:00 10-1
3.60
3.57% 0 1011
5:55
00
13 101
0.07 5 10
0.00 10-0
1.50 10-1
0.65 10
2nd Quatta
1.0
4.55
230
2.20
6.50
4.00
1.10
18:
WSL
Quantic
6.01 10
277
0.55
1.20
2.00 10
7ad Quati
6 10
15.
0.30x
6.77
Mus
1
1
1.55
S1C
6.83
1,30
T:4
0.29
0.33
Znd Quattz
1-42 10
1:13 30
- 00
5.0 2-23-
3.33- 10
EJIT 1
4.30 x
1.55 53
4.57 10
7:33
9.30
ABM
Mou
1/0
1 001
1.21
1/41
6.13
4.0 19
0.35 10
6.13%
4.20
5.15
11
5.50
Inl Quatic
6:20 10
4.18 00
4.97 10
4.80
3.2
4.52
4.01
4.64
3,12
5:33
Quanta
0.58
5:0
5.86
6.6
5.5
T:06
Musr
1.00 300
00 9310
3.56% 20
1.33 x 1001
3:66 333
752 10
1.51 16
500 1075
0.43 53
0.84% 1
06 10
5:37
1.22
Quarta
1.56 1074
1074
1.00
3.60 3330
100
0.86 1072
10
2.5%
2.65
hul Cuartie
82
4.2 00
3.95 10
195
6.2.
0.55
1/01 -
6:21 -
6.14 01
0.33
0.35 10
Probabilistic Values: Error vs Sample Complexity (Neural Net Ground Truth)
Symmetric Heta
Shapley
B(2,2)
B(4.4)
B(8.8)
10-1
10
10-3
10
10P
10
10
16P
Agymmettic Beta
Shapley
B(1
B(144
B(L.
Eyerror
10
10-1
10
10
10
10-2
10-2
10
10
101
10
10
Wrighted Hanzhaf
Banshaf
WBB0
WB(0.7)
WB(0.8)
10a
1
10
10-3
10
10
10'
10
10
102
10
10a
10
10a
Sample Multipher (18/1a
Sample Multiplicr (m/i))
Sumple Multiphier (m//a)
Sample Multiphie (m8/a)
LineurMRR MSR
OFA
CELS
WeighoodSHIAP
KernelSTAA
AME
ARM
SHAP
PermatationSTAA
KerneBanhhaf
Figure 6: Error between the estimated and true probabilistic values by complexity. Each subplot shows results for a different probabilistic value with the error averaged over all large datasets (n 2 30). The lines report the mean error over 10 runs. Tree and Linear MSR give the best performance, often by several orders of magnitude especially when the number of samples large.
29

---

Experiments by Noise
In many settings, access the value function is noisy. For example, may be the expectation over distribution that is expensive to exactly compute. Instead, we may estimate the expectation, and hence the values we observe are noisy. In this experiment, we add normally distributed noise the values passed into each estimator. The plots show the performance of each estimator by the magnitude of this noise.
Probabilistic Values: Error vs Noise Magnitude (Neural Net Ground Truth)
Shapley
((2,2)
B(4,4)
B(8.8)
10
10
Weighted Bonzhed Asymuetric Symmnetzic
100
10-
10
10-2
10
10P
10
10
10
10
10
Shapley
B(1.2)
B(1,4)
BCL.8)
100
10
100
10-3
10
10
10-2
10
10
20
162
10
Banzbaf
WB(0.6)
WB(0.7)
WB(0.8)
Ey-onoc
10a
10-2
10--
10-2
10
10
Noise Magnitude
Noise Magnicade
Noise Magaitude
Noise Magnitude
LinearMR TreMSR
OFA
GELS
WSig
Kern PermatationSHAP
AME
WSL
ARM
SHAP
Banzhaaa
Figure 7: Error between the estimated and true probabilistic values function of noise magnitude. Each subplot shows results for different probabilistic value with the error averaged over all small datasets 30). The lines report the mean error over 10 runs. Tree MSR gives the best performance, often by several orders of magnitude especially when the magnitude of the noise is small.
30

---

Probabilistic Values: Error Noise Magnitude (Regression Forest Ground Truth)
Shapley
B(2.2)
B(A
B(8.8)
Weighted Bonshaf Agymmeetiic Symmetric
10-2
10-22
10-2
10"
10
10
10
Shapley
B(1,2
B(1,4
BCL8
107-
10
100
10-2
10-2
10-22
10-2
100
1IP
10
10"
20
16
10
10
Bandbal
WB(0.6)
WB(0.7)
WB(O.))
10
10a
10-2
10--2
10-2
10
11f
10
10"
20
10P
10
10
Nuise Magnitude
Noise Maguitade
Noise Magaitude
Noiee Magnitule
LIneurMR Tre
WHAP
KemneSHHAP
ARM
SHAI
PermatationSAA
KerneBBanbal
Figure 8: Error between the estimated and true probabilistic values as function of noise magnitude. Each subplot shows results for a different probabilistic value with the error averaged over all large datasets (n 2 30). The lines report the mean error over 10 runs. Tree MSR gives the best performance, often by several orders of magnitude especially when the magnitude the noise is small.
31

---

G Dataset Descriptions
Table 4: summary of the datasets used in our experiments, including source, access method, license,
and number of features
Dataset
Source
Citation
Access Method
License
Adult
Koh96
shap. dataseta
CC-BY
Forest Fires
13
[CM07
UCI ML Repd
CC-BY 4.0
Real Estate
YH09
UCI ML Repd OpenMI
CC-BY 4.0
Bike Sharing
16
[TG14
Public Domain
Breast Cancer
30
SWM93
sklearn. datasets
CC-BY 4.0
Independent
60
LL17
datp.datssets
MIT
NHANES
79
Cen23
shap. datasess
Public Domain
Communities
101
RC02
dataseta
CC-BY 4.0
32


Reviews:
[{"review_id": "E53cNIitLw", "reviewer": "Reviewer_z7xn", "summary": "The article addresses the estimation of probabilistic values such as Shapley values and Banzhaf values without the need to perform $2^{n}$ computations and accesses to the payoff function.\nThey propose using a simpler function, $f(S): 2^{[n]} \\to \\mathcal{R}$, to approximate $v(S)$. This function is then used to exploit the linearity property of probabilistic values to find a formulation that can estimate the contributions consistently, which is proven theoretically.\nThe proposed algorithm assumes that $\\phi(f)$ can be computed fast, i.e. $f$ is either linear or tree-based.\nThe article also provides intensive numerical experiments analyzing the sample complexity of the proposed algorithm and comparing it to the many published methods.", "questions": "1) Equation (3) seems central to the proposed algorithm, but no intuition is provided. It’s also unclear which cited work this equation comes from. Can you clarify clarify its origin and provide some explanation?\n\n2) Theorem 2.1 is the main contribution of the article, I think it can be stated better, although equation (6) does entail consistency results, I believe the main contribution of the article can be more readily accessible if consistency ($E[\\hat{\\phi}_{i}] = \\phi_{i}$) and variance results are mentioned explicitly in the main body of the article.\n\n3) is the division between Monte Carlo and regression-based methods strictly correct? For instance, doesn’t KernelSHAP also involve Monte Carlo sampling, not just regression?\n\n4) Some explanations are hard to follow. For example, in line 35, the first sentence appears without context, and the topic shifts abruptly right after. This is also seen in sections 1.1\n\n5) Key related works like Mitchell et al., 2022 (\"Sampling Permutations for Shapley Value Estimation\") and Jethani et al., 2022 (\"FastSHAP\") are not mentioned. Even though FastSHAP is not based on Monte Carlo, it is relevant. Also, Mitchell et al. show that Owen's halves can be effective, yet this article only discusses Owen’s method in the context of KernelSHAP. I understand that the relevant literature is vast but it does draw attention that the method is not compared to such prevalent works", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) The article addresses an important problem in XAI which is the efficient computation of Shapley values\n2) It provides sound theoretical guarantees.\n3) The experimental results are thorough and convincingly demonstrate the method’s effectiveness. \n\nWeaknesses:\n1) The presentation lacks clarity in key areas, including both the preliminary literature overview, the discussion of closely related methods, and even the theoretical contribution\n2) The manuscript omits discussion of several relevant works in the literature on fast Shapley value estimation. While the literature is admittedly large, a more comprehensive review would strengthen the article.", "was_revised": true, "final_justification": "I believe the results of the article are significant. I had concerns about the comparisons and some points in the articles. The authors have convinced me on all points. I believe the article is interesting to people working in the area of XAI and is technically solid with impact on the area.", "rebuttal": "Thank you for your careful reading! We appreciate your clarifying questions, and pointers to specific related works. We respond in detail below:\n\n> Equation (3) seems central to the proposed algorithm [...] Can you clarify its origin and provide some explanation?\n\nThe Maximum Sample Reuse (MSR) estimator described in Equation (3) was originally proposed to estimate Banzhaf values [WJ23]. Since then, it has been generalized to other probabilistic values, albeit with differing notations [KBMH24, LY24a, LY24b]. The key insight is that we can write the probabilistic values as\n\n$$\n\\phi_i (v) = \\sum_{S \\subseteq [n] \\setminus \\{ i \\}} p_{|S|} [ v(S \\cup \\{i \\}) - v(S) ]\n$$\n$$\n= \\sum_{S  \\subseteq [n] : i \\in S} p_{|S| -1} v(S) - \\sum_{S \\subseteq [n]: i \\notin S} p_{|S|} v(S)\n$$\n$$\n= \\sum_{S \\subseteq [n]} v(S) [p_{|S|-1} {1}[i \\in S] - p_{|S|} {1}[i \\notin S] ]\n$$\n\nCompared to the first equation, the final equation makes it clear how $v(S)$ appears (albeit with a potentially different sign and weighting) in every probabilistic value. This observation naturally suggests the MSR estimator in Equation (3), where each $S$ is sampled, and reweighted, so that the estimator is right in expectation. We will update the paper to make this motivation clear.\n\n> I believe the main contribution of the article can be more readily accessible if consistency ($E[\\hat{\\phi}{i}] = \\phi{i}$) and variance results are mentioned explicitly in the main body of the article.\n\nWe think this is a good suggestion, and will plan on including the consistency and variance directly in Theorem 2.1.\n\n> is the division between Monte Carlo and regression-based methods strictly correct? For instance, doesn’t KernelSHAP also involve Monte Carlo sampling, not just regression?\n\nGood question! In our work, we distinguish between“Monte Carlo” methods that *directly* estimate the linear sum of probabilistic values, and “regression-based” methods that fit an approximation $f$ to the underlying game $v$, then compute the probabilistic values of $f$. While methods like KernelSHAP use *random sampling* to fit a linear function $f$ to $v$, the method ultimately computes $f$ via least squares regression and returns the Shapley values of $f$. (Since $f$ is a linear function, its Shapley values are simply the coefficients for each feature.) We will clarify this distinction in the updated paper..\n\n> in line 35, the first sentence appears without context, and the topic shifts abruptly right after. This is also seen in sections 1.1\n\nThank you for pointing out these writing discontinuities. We have smoothed out the transitions (Line 35 and Section 1.1 more broadly) in the new version.\n\n> Even though FastSHAP is not based on Monte Carlo, it is relevant. Also, Mitchell et al. show that Owen's halves can be effective, yet this article only discusses Owen’s method in the context of KernelSHAP. I understand that the relevant literature is vast but it does draw attention that the method is not compared to such prevalent works\n\nDue to their widespread applications in interpretability, there is certainly a vast literature on estimating Shapley values, and probabilistic values more broadly. We will plan on expanding our discussion of prior work in the updated paper. We briefly discuss two methods mentioned by the reviewer here: \n\nFast SHAP is a method for learning a function $f$ that simultaneously fits *multiple* related games $v$. While it has a high overhead in sample complexity to learn $f$, Fast SHAP can give improved results when we want to estimate Shapley values for multiple, similar games simultaneously. In our setting, we are interested in estimating the Shapley values of a *single* game $v$. Due to these incomparable settings, we do not compare to Fast SHAP in our work, but have now highlighted the estimator in the updated related work section in response to your comment.\n\nOwen’s and Owen’s halves are two Shapley value estimators. They both exploit a connection between Shapley values and the expectation of a continuous process. The “halves” augmentation is a kind of paired sampling (sometimes called “antithetical” sampling) that boosts performance. We chose not to compare to Owen’s or Owen’s halves estimators because they were shown in “Sampling Permutations for Shapley Value Estimation” to consistently perform worse than Permutation SHAP (what they call “MC-antithetic”) see e.g., their Figure 9. In our work, we find that Tree MSR already achieves an average $6\\times$ improvement over Permutation SHAP. Nevertheless, we will plan on adding discussion of this prior work."}, {"review_id": "ADP1ZspdpK", "reviewer": "Reviewer_Q2YG", "summary": "This paper proposed a novel estimator for general probabilistic values such as Shapley values and Banzhaf values. The authors combined Monte Carlo sampling with regression-based methods to construct an unbiased estimator. Specifically, the proposed method used regression as a variance reduction technique for the Maximum Sample Reuse method, thereby integrating the strengths of both approaches.", "questions": "See weaknesses", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThe proposed estimator has several desirable properties: (1) it is unbiased, (2) it is applicable to any probabilistic value (e.g., Shapley value and Banzhaf value), (3) it allows the use of any learned function $f$  to approximate the value function $v$, and (4) the variance of the estimator depends on the quality of the surrogate function $f$. As such, when $f$ is accurate, the variance can be significantly reduced.\n\n2.\tThe authors analyze the error bound of the estimator under an arbitrary sampling distribution $D$ , which improves the theoretical soundness and generality of the method.\n\n3.\tThe authors implement the estimator using both linear and tree-based models for the surrogate function $f$, with the tree-based models exhibiting lower approximation error in practice.\n\n**Weaknesses:**\n\n1.\tIt would be helpful if the authors could provide a more detailed derivation of Equation (5) in the appendix, including a formal proof of its unbiasedness and an analysis of its variance.\n\n\n\n2.\tSince the variance of the proposed estimator depends on the surrogate function $f$, it would be beneficial to provide a more detailed discussion of how different choices of $𝑓$ affect the variance and estimation accuracy. For example, to what extent does the use of linear versus non-linear models influence the quality of the estimated probabilistic values? Could shallow neural networks serve as effective approximators in this context? A more detailed analysis of how the choice of $f$ impacts estimation error would strengthen the paper.\n\n\n \n3.\tIt is unclear how the computational complexity of the proposed method compares to existing approaches. In particular, it would be helpful to clarify whether the estimator has similar time complexity to the Maximum Sample Reuse method. A discussion or empirical comparison of the time complexity (or runtime) would improve the clarity of the contribution.\n\n4.  The authors could add a summary table in the appendix comparing the proposed method with existing baselines (e.g., in terms of unbiasedness, variance, computational cost, use of surrogate models, and other relevant properties), which would help readers better understand the advantages and limitations of each method.", "was_revised": true, "final_justification": "I appreciate the strengths of this manuscript and the authors’ detailed responses. I am inclined to support its acceptance.", "rebuttal": "Thank you for your detailed comments! We respond below:\n\n> It would be helpful if the authors could provide a more detailed derivation of Equation (5) in the appendix, including a formal proof of its unbiasedness and an analysis of its variance.\n\nThese derivations are provided in proof of Theorem 2.1 (Appendix A). We show that $\\tilde{\\phi}_i$ is unbiased in the equation under Line 370, and analyze its variance in Equation (7). In response to your comment, and that of Reviewer z7xn, we will make this analysis clear in the *main body* of the updated paper.\n\n> to what extent does the use of linear versus non-linear models influence the quality of the estimated probabilistic values? Could shallow neural networks serve as effective approximators in this context? A more detailed analysis of how the choice of impacts estimation error would strengthen the paper.\n\nA crucial component of our proposed Regression MSR estimator is that the probabilistic values of the approximation $f$ need to be efficiently computable. (Otherwise, we would be stuck with the initial problem of estimating the probabilistic values of $f$.)\n\nWe are aware of two primary function classes with this property:\n\n* The coefficients of **linear functions** are always their probabilistic values. (This can directly be seen directly in Equation (1) with the *probabilistic* constraint that $\\sum_{\\ell=0}^{n-1} {n-1 \\choose ell} p_\\ell = 1$.)\n\n* We show in Appendix C how the probabilistic values of (multiple) **decision trees** can be computed efficiently. A special case of this was known for Shapley values, and basically follows from the “case”-like structure of trees.\n\nThe issue with neural networks is that computing their Shapley values is generally slow, requiring O(2^n) time even when the network is shallow or has few parameters.\n\n> it would be helpful to clarify whether the estimator has similar time complexity to the Maximum Sample Reuse method. A discussion or empirical comparison of the time complexity (or runtime) would improve the clarity of the contribution.\n\nGreat question! In our experience, the dominating cost is computing $m$ function evaluations of $v$. Here’s one way to see why: If $v$ is as expressive as a shallow neural network, this time complexity is already $O(m n^2)$ and likely much higher. (A single fully connected layer between $n$ nodes requires $O(n^2)$ operations, repeated for each of the $m$ different $n$-dimensional inputs.)\n\nBeyond the time to get evaluations of $v$, the additional computational step of Regression MSR is fitting the function $f$:\n\n* When $f$ is linear, solving a linear system with $m$ equations and $n$ rows takes $O(mn^2)$ time. In practice, this is very fast due to excellent linear algebra libraries. Note: Kernel SHAP and Leverage SHAP have this same time complexity because they are also solving a linear system of the same size.\n\n* When $f$ is tree-based model, fitting the function requires roughly $O(T * m * n)$ time where $T$ is the number of trees. In practice, we use the default $T=100$ for XGBoost. Due to its extensive optimizations, fitting XGboost is remarkably fast in practice.\n\n> The authors could add a summary table in the appendix comparing the proposed method with existing baselines (e.g., in terms of unbiasedness, variance, computational cost, use of surrogate models, and other relevant properties), which would help readers better understand the advantages and limitations of each method.\n\nGreat idea! We agree a summary table would be useful for the community. Please see below for an initial Shapley value estimator summary. We will continue to update, adding more estimators and properties, for the final version of the paper. Let $T_m$ be the time to evaluate the value function $v$ on $m$ different subsets.\n\n| Method             | Bias     | Time Complexity       | Regression-based       |\n|--------------------|----------|------------------------|-------------------------|\n| Kernel SHAP        | Biased   | $T_m + O(mn^2)$        | Linear Model            |\n| Leverage SHAP      | Biased   | $T_m + O(mn^2)$        | Linear Model            |\n| Permutation SHAP   | Unbiased | $T_m + O(m + n)$       | No                      |\n| MC                 | Unbiased | $T_m + O(m + n)$       | No                      |\n| MSR                | Unbiased | $T_m + O(m + n)$       | No                      |\n| Regression MSR     | Unbiased | $T_m + O(mn^2)$        | Linear or Tree Model    |"}, {"review_id": "mXxIv6Egdx", "reviewer": "Reviewer_BiBE", "summary": "This paper proposes using the control variates (CV) method or regression sampling (RS) method for computing the Shapley value and its variants to address the well-known computational challenges. While CV and RS are well-established techniques in Monte Carlo estimation, to the best of my knowledge, this is the first proposal to apply these methods to Shapley value calculation, which is a noteworthy contribution.\n\nAs demonstrated in general Monte Carlo contexts, both CV and RS are undoubtedly effective. For Shapley value computation, the baseline function can be chosen as a linear function, since in that case the exponential sum required for the Shapley value can be computed exactly.\n\nThe idea is straightforward. Since existing sampling approaches such as LeverageSHAP are already highly optimized, direct performance comparison may be challenging. Nevertheless, the authors’ proposal is meaningful as an additional acceleration method for SHAP, complementing LeverageSHAP. I support acceptance of this paper.", "questions": "I found Fig. 1(b) confusing. The Correlated and Community data points do not appear to satisfy the unbiasedness property. Why do they seem so biased? In theory, the estimated values should be distributed both above and below the true value, so that the deviations cancel out on average. Why is this not observed in the figure?", "limitations": "CV and RS is well-known. Contribution can be seen incremental from a general Monte Carlo study perspective. However, application to Shapley value computation is novel enough. This would should be accepted.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength:\n- The first introduction of the CV or RS method to Shapley values. \n- Demonstrated variance reduction.\n\nWeakness:\n- Depending on how the performance is measured, improvement may not be drastic as compared to highly optimized alternatives.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review!\n\n> Depending on how the performance is measured, improvement may not be drastic as compared to highly optimized alternatives.\n\nWhile it doesn’t give SOTA in every setting, our Tree MSR achieves an average error $1.75 \\times$ lower than the prior best Shapley value estimator, Leverage SHAP, on eight common datasets.\n\n> I found Fig. 1(b) confusing. The Correlated and Community data points do not appear to satisfy the unbiasedness property. Why do they seem so biased? In theory, the estimated values should be distributed both above and below the true value, so that the deviations cancel out on average. Why is this not observed in the figure?\n\nFigure 1(b) shows the true Shapley values vs. estimates produced by the **standard MSR estimator on one random run**. The multiple points for each dataset (e.g. for Correlated and Community) correspond to different features in the dataset. While the estimated Shapley value for each individual feature is unbiased, there is substantial correlation between the estimates for different features, leading to this clustering. The correlation is due to the fact that every function evaluation $v(S)$ is used to estimate the Shapley value for *every* feature. Large values of $v(S)$ in particular can have substantial impact. To observe unbiasedness, we would need to re-run the same experiment with different random seeds. If we do so, we see that the estimates for Correlated and Communities do not consistently appear on one side of the diagonal line. \n\nWhile the computational advantage of MSR is its “maximum reuse”, this property comes with a cost in variance and correlation. We view Regression MSR as a fix: The variance of Regression MSR depends on $[ f(S) \\approx v(S) ]^2$ rather than $[v(S)]^2$ like standard MSR. So, even if some $v(S)$ is large, we can still get remarkably accurate estimators provided $f(S) \\approx v(S)$."}, {"review_id": "9fM9plFWOn", "reviewer": "Reviewer_38gP", "summary": "The paper proposes a technique that combines Monte Carlo sampling with a regression-based formulation. This approach is claimed to reduce the variance of approximation, thereby improving the estimation of probabilistic values. The authors also introduce treeprob, a method for exactly computing all probabilistic values when interventional utility is used. Experimental results support the potential effectiveness of the proposed technique.", "questions": "- Why not combine $\\mathcal{S}\\^{\\mathrm{train}}$ and $\\mathcal{S}\\^{\\mathrm{test}}$ for both learning and approximating, given that they are drawn from the same distribution?\n- Could the authors provide results of substituting other Monte Carlo baselines in both linearMSR and treeMSR?", "limitations": "yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The proposed approach appears promising for developing variance-reduced Monte Carlo methods for approximating probabilistic values.\n\n**Weaknesses**\n#### Major\n- Basically, the proposed procedure can be summarized as follows: (1) learning a function $f$ to approximate the given utility function $v$, where $\\phi(f)$ is cheap to compute exactly; and then (2) approximate $\\phi(v)$ as $\\phi(f) + \\hat{\\phi}(v-f)$. In particular, $\\hat{\\phi}(v-f)$ is an approximation of $\\phi(v-f)$ computed using th Monte Carlo method introduced in Eq. (2). That being said,  $\\hat{\\phi}(v-f)$ could also be computed using any existing Monte Carlo methods. This suggests that all the considered Monte Carlo baselines could potentially benefit from the same learned function $f$. \n\n\n- On the other hand, while the proposed Monte Carlo method appears novel, it is unclear whether it achieves faster convergence rate either empirically or theoretically compared to the existing baselines.  \n\nAll in all, the paper lacks experiments demonstrating that the proposed Monte Carlo method is the most effective when paired with the learned $f$. \n\n\n#### Minor\n- I suggest that the authors include more details on the implementation of treeMSR. After examining the provided code, I found that the features used are binary; the baseline is the zero vector, and the explicand is the one vector. This important information is missing in the paper.\n\n- In the proof of theorem 2.1, the randomness involved in learning $f$ is not accounted. As a result, the stated result applies only to the specific Monte Carlo method defined in Eq. (3). The current statement of theorem 2.1 may therefore be misleading.\n\n\n**Typos**\n- According to Eq. (7), the first equality in Eq. (8) should be changed to $\\leq$. \n- In line 26 of Algorithm 2, it should be $\\phi[\\mathrm{node.feat}] \\gets \\phi[\\mathrm{node.feat}] + (\\mathrm{pos}\\_{e} + \\mathrm{neg}\\_{b})$.", "was_revised": true, "final_justification": "Although the presented theory has certain flaws, such as not positioning the proposed MSR estimator relative to existing ones in terms of theoretical convergence rate, and Theorem 2.1 for employing the proposed regression-adjusted trick being clearly naive, I believe the trick itself is promising, and future work may yield improved results both theoretically and empirically. In my view, a better theorectical framework is far beyond what is presented in this work.", "rebuttal": "> all the considered Monte Carlo baselines could potentially benefit from the same learned function $f$.\n\nWe agree with this point, and actually view it as a *strength* rather than a *weakness* of our approach. We selected MSR as our “baseline” estimator because, in addition to being simple to implement, it is\n\n1) unbiased (contrasting with Kernel SHAP and Leverage SHAP), and\n\n2) computationally efficient in the sense that every function evaluation $v(S)$ is used to update every estimate (contrasting with Permutation SHAP and MC).\n\nAs far as we know, MSR uniquely satisfies these two properties among probabilistic value estimators.\n\n> the paper lacks experiments demonstrating that the proposed Monte Carlo method is the most effective when paired with the learned $f$.\n\nSince the main contribution of our work is the regression adjustment technique (learning an $f$ for which we can compute probabilistic values exactly), considering a wide variety of alternative baseline estimators is outside the scope of the paper. That being said, we just ran some experiments with MC as the baseline; please see below.\n\n> On the other hand, while the proposed Monte Carlo method appears novel, it is unclear whether it achieves faster convergence rate either empirically or theoretically compared to the existing baselines.\n\nFor fixed sample budgets, Tree MSR achieves an average error that is $1.75\\times$ lower than the prior best estimator, Leverage SHAP, across eight popular datasets (Table 1). As for convergence rate, we explore how accurately the estimators recover the true Shapley values (Figure 2) and probabilistic values (Figure 3) as a function of sample size. From these figures, we conclude that, for most datasets, *Tree MSR does gives faster convergence empirically*. We justify this finding theoretically in Theorem 2.1, where we show the performance of our estimator depends on how well the (randomly) learned $f$ fits $v$.\n\n> I suggest that the authors include more details on the implementation of treeMSR. After examining the provided code, I found that the features used are binary; the baseline is the zero vector, and the explicand is the one vector. This important information is missing in the paper.\n\nWe will add more details! One note: In the interventional setting where we apply Tree Prob, a point is fully specified by the binary indicator of which features come from the “explicand” and which come from the “baseline”. Since the tree-based model can learn in a scale-invariant and shift-invariant way with respect to these features, it actually suffices to only consider binary inputs. We make this clear in the updated version of the paper.\n\n> In the proof of theorem 2.1, the randomness involved in learning $f$ is not accounted. As a result, the stated result applies only to the specific Monte Carlo method defined in Eq. (3). The current statement of theorem 2.1 may therefore be misleading.\n\nWe can add a comment reminding the reader that f itself is a random function. Since independent samples are used to fit $f$ (line 3-4 in Algorithm 1) and to approximate Shapley values (line 6-7) the statement of Theorem 2.1 is true regardless of the outcome of f. \n\n> Typos\n\nThank you!\n\n> Why not combine $\\mathcal{S}^\\text{train}$ and $\\mathcal{S}^\\text{test}$ for both learning and approximating, given that they are drawn from the same distribution?\n\nGood question! Our variance analysis in the proof of Theorem 2.1 relies on independence between the final estimate and the learned function $f$. We use $\\mathcal{S}^\\text{train}$ to learn the function $f$, and then $\\mathcal{S}^\\text{test}$ for the samples used to build the final estimate.\n\n> Could the authors provide results of substituting other Monte Carlo baselines in both linearMSR and treeMSR?\n\nYes! We compare several Shapley value estimators in the small sample regime $m=10n$ on the four small datasets below.\n\n### Dataset: Adult (n=12)\n\n| Estimator | Mean | 1st | 2nd | 3rd | Max |\n|--------------------|-----------|-----------|-----------|-----------|-----------|\n| LinearMC | 6.80e-01 | 2.70e-02 | 1.04e-01 | 1.31e-01 | 2.53e+00 |\n| TreeMC | 1.30e-05 | 2.92e-08 | 5.40e-08 | 1.34e-07 | 1.22e-04 |\n| LinearMSR | 1.59e-04 | 1.77e-05 | 4.43e-05 | 5.07e-05 | 4.89e-04 |\n| TreeMSR | 1.09e-06 | 3.61e-08 | 4.19e-08 | 1.68e-07 | 3.12e-06 |\n| KernelSHAP | 5.19e-04 | 1.01e-04 | 1.18e-04 | 1.90e-04 | 1.15e-03 |\n| LeverageSHAP | 1.87e-04 | 1.13e-05 | 3.06e-05 | 4.64e-05 | 5.34e-04 |\n| PermutationSHAP | 4.83e-03 | 2.65e-04 | 4.14e-04 | 5.85e-04 | 2.04e-02 |\n\n### Dataset: Forest Fires (n=13)\n\n| Estimator | Mean | 1st | 2nd | 3rd | Max |\n|--------------------|-----------|-----------|-----------|-----------|-----------|\n| LinearMC | 4.64e-01 | 3.47e-02 | 1.03e-01 | 1.09e-01 | 1.99e+00 |\n| TreeMC | 1.29e-05 | 2.54e-07 | 1.18e-06 | 2.09e-06 | 4.15e-05 |\n| LinearMSR | 6.41e-05 | 1.27e-05 | 1.50e-05 | 1.54e-05 | 2.93e-04 |\n| TreeMSR | 1.21e-06 | 6.79e-08 | 1.00e-07 | 1.05e-07 | 8.51e-06 |\n| KernelSHAP | 6.72e-05 | 7.45e-06 | 1.51e-05 | 1.89e-05 | 1.86e-04 |\n| LeverageSHAP | 5.78e-05 | 6.83e-06 | 8.97e-06 | 1.86e-05 | 1.64e-04 |\n| PermutationSHAP | 7.63e-04 | 1.40e-04 | 1.42e-04 | 1.70e-04 | 2.53e-03 |\n\n### Dataset: Real Estate (n=15)\n\n| Estimator | Mean | 1st | 2nd | 3rd | Max |\n|--------------------|-----------|-----------|-----------|-----------|-----------|\n| LinearMC | 7.30e+00 | 2.27e-01 | 4.37e-01 | 6.58e-01 | 6.20e+01 |\n| TreeMC | 1.21e-10 | 4.54e-12 | 4.83e-12 | 1.05e-11 | 8.63e-10 |\n| LinearMSR | 5.94e-06 | 3.21e-07 | 5.74e-07 | 7.47e-07 | 2.44e-05 |\n| TreeMSR | 1.95e-10 | 4.19e-12 | 4.63e-12 | 7.32e-12 | 1.60e-09 |\n| KernelSHAP | 8.02e-06 | 3.00e-07 | 4.86e-07 | 5.28e-07 | 4.87e-05 |\n| LeverageSHAP | 8.77e-06 | 2.38e-07 | 4.20e-07 | 1.18e-06 | 3.79e-05 |\n| PermutationSHAP | 3.66e-05 | 4.53e-08 | 4.29e-07 | 1.22e-06 | 2.03e-04 |\n\n### Dataset: Bike Sharing (n=16)\n\n| Estimator | Mean | 1st | 2nd | 3rd | Max |\n|--------------------|-----------|-----------|-----------|-----------|-----------|\n| LinearMC | 2.18e+00 | 4.83e-02 | 1.08e-01 | 2.63e-01 | 1.74e+01 |\n| TreeMC | 2.05e-06 | 1.31e-08 | 1.52e-08 | 1.99e-07 | 8.10e-06 |\n| LinearMSR | 5.82e-05 | 1.13e-06 | 5.11e-06 | 9.26e-06 | 1.89e-04 |\n| TreeMSR | 2.96e-07 | 4.78e-10 | 5.78e-10 | 1.60e-08 | 1.96e-06 |\n| KernelSHAP | 7.10e-05 | 1.18e-06 | 1.73e-05 | 2.01e-05 | 1.61e-04 |\n| LeverageSHAP | 5.19e-05 | 3.73e-06 | 5.26e-06 | 9.99e-06 | 1.28e-04 |\n| PermutationSHAP | 2.16e-04 | 1.47e-05 | 2.94e-05 | 4.82e-05 | 3.82e-04 |\n\nWhile Tree MC is quite good, we generally find that Tree MSR gives error about an order of magnitude smaller. We believe this is due to the differences in the final regression-adjusted estimate: each sample is used for every estimate in MSR, whereas each sample is only used for one estimate in MC."}]

Author rebuttal:

Meta-review: The paper presents a novel method for efficiently estimating probabilistic values, such as Shapley and Banzhaf values, by combining Monte Carlo sampling with flexible function-based regression. This approach achieves state-of-the-art accuracy across multiple datasets, significantly reducing estimation error compared to existing methods while maintaining unbiased probabilistic value computations.

Strengths of the paper include addressing efficient and accurate computation of Shapley and other probabilistic values with strong theoretical guarantees. The estimator is unbiased, flexible, applicable to any probabilistic value, and achieves variance reduction with accurate surrogates. Experiments are thorough and demonstrate state-of-the-art performance, particularly using tree-based models, and the method introduces novel variance-reduction techniques.

Reviewers raised several concerns, many of which were addressed during the rebuttal and discussion period, including unclear presentation of the literature review, related methods, and theoretical contributions, missing discussion of relevant prior work, and insufficient derivations or proofs. The impact of different surrogate functions on variance and accuracy is underexplored, computational complexity and runtime comparisons are lacking, and it is unclear if the method converges faster than existing Monte Carlo baselines.

The reviewers agree that the paper is technically solid, addresses an important problem in XAI, and is of interest to the community. While some theoretical aspects, such as the convergence analysis and Theorem 2.1, are limited or simplistic, the proposed regression-adjusted approach is promising and may inspire future theoretical and empirical improvements. Overall, the reviewers support acceptance.
Decision: Accept (poster)