cs.LGJun 13, 2025

Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values

Authors: R. Teal Witter, Yurong Liu, Christopher Musco

Organizations: Claremont McKenna College · New York University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 exact computation can require exponential time, 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; with cross-fitting, the method also produces 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 can be 11×11\times lower than Permutation SHAP (the most popular Monte Carlo method), 6.5×6.5\times lower than Kernel SHAP (the most popular linear regression method), and 3.4×3.4\times lower than Leverage SHAP (the prior state-of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error 390×390\times lower than the best estimator from prior work.

Figures & tables

Figure 1: Predicted versus true (normalized) Shapley values for three unbiased estimators (our Regression MSR estimators use cross-fitting; see Section 2 ) given a fixed number of black-box evaluations of the value function, vv . Each point represents one feature’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., [v(S∪{i})−v(S)]2[v(S\cup\{i\})-v(S)]^{2} . The Maximum Sample Reuse (MSR) estimator reuses samples, but has larger variance that depends on the magnitude of the values, i.e., [v(S)]2[v(S)]^{2} . Our Regression MSR estimators reuse samples and have smaller variance that depends on how well a learned function ff fits the value function vv , i.e., [v(S)−f(S)]2[v(S)-f(S)]^{2} . Even taking ff to be linear gives excellent performance (we call this method Linear MSR). Taking ff to be a decision-tree model (Tree MSR) can produce even better estimates for large sample sizes, as shown in Figure 2 .
Figure 2: Average relative squared ℓ2\ell_{2} error between estimated and true Shapley values as a function of sample size mm (number of evaluations of vv ) for various datasets. The lines report the mean error over 10 runs, and m=10n,20n,40n,80n,160n,320n,640nm=10n,20n,40n,80n,160n,320n,640n . Linear MSR consistently performs comparably to the prior state-of-the-art Leverage SHAP. Meanwhile, the performance of 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.
 ∑S∈T(ℓ)[v(S)−f(S)]2.\displaystyle\sum_{S\in\mathcal{T}^{(\ell)}}[v(S)-f(S)]^{2}. 
Algorithm 1 Regression Maximum Sample Reuse
 AdultForest FiresReal EstateBike SharingBreast CancerIndependentNHANESCommunitiesMean
LinearMSR         
Mean8.29\times10−048.29\text{\times}{10}^{-04}5.54\times10−055.54\text{\times}{10}^{-05}1.99\times10−081.99\text{\times}{10}^{-08}2.20\times10−032.20\text{\times}{10}^{-03}1.03\times10−031.03\text{\times}{10}^{-03}9.54\times10−059.54\text{\times}{10}^{-05}8.37\times10−068.37\text{\times}{10}^{-06}5.92\times10−055.92\text{\times}{10}^{-05}5.35\times10−045.35\text{\times}{10}^{-04}
1st Quartile2.50\times10−052.50\text{\times}{10}^{-05}2.06\times10−052.06\text{\times}{10}^{-05}6.66\times10−116.66\text{\times}{10}^{-11}4.56\times10−044.56\text{\times}{10}^{-04}8.84\times10−058.84\text{\times}{10}^{-05}3.96\times10−053.96\text{\times}{10}^{-05}9.54\times10−089.54\text{\times}{10}^{-08}4.45\times10−064.45\text{\times}{10}^{-06}7.93\times10−057.93\text{\times}{10}^{-05}
2nd Quartile5.17\times10−045.17\text{\times}{10}^{-04}3.15\times10−053.15\text{\times}{10}^{-05}1.27\times10−091.27\text{\times}{10}^{-09}1.35\times10−031.35\text{\times}{10}^{-03}1.13\times10−031.13\text{\times}{10}^{-03}7.24\times10−057.24\text{\times}{10}^{-05}3.51\times10−063.51\text{\times}{10}^{-06}5.43\times10−055.43\text{\times}{10}^{-05}3.95\times10−043.95\text{\times}{10}^{-04}
3rd Quartile1.47\times10−031.47\text{\times}{10}^{-03}8.15\times10−058.15\text{\times}{10}^{-05}2.83\times10−092.83\text{\times}{10}^{-09}4.23\times10−034.23\text{\times}{10}^{-03}1.76\times10−031.76\text{\times}{10}^{-03}9.74\times10−059.74\text{\times}{10}^{-05}1.50\times10−051.50\text{\times}{10}^{-05}8.36\times10−058.36\text{\times}{10}^{-05}9.67\times10−049.67\text{\times}{10}^{-04}
TreeMSR         
Table 1: Summary statistics of the average relative squared ℓ2\ell_{2} error between estimated and true Shapley values for all datasets listed in Appendix H . All estimators are run with m=40nm=40n samples. Tree MSR achieves average error that is 11×11\times lower than Permutation SHAP, 6.5×6.5\times lower than Kernel SHAP, and 3.4×3.4\times 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 in Figure 2 . We follow Olympic medal convention: gold , silver and bronze signify first, second and third best performance, respectively.
Figure 3: Average error between the estimated and true probabilistic values as a function of sample size. Each subplot shows results for a different probabilistic value with the error averaged over all large datasets ( n≥30n\geq 30 ), for which we used the tree-based method described in Appendix D . The lines report the mean error over 10 runs. Tree MSR gives the best performance, often by several orders of magnitude when mm is large.
 B(1,1)B(2,2)B(4,4)B(8,8)B(1,2)B(1,4)B(1,8)WB(0.5)WB(0.6)WB(0.7)WB(0.8)WB(0.9)Mean
LinearMSR             
Mean3.23\times10−043.23\text{\times}{10}^{-04}2.44\times10−042.44\text{\times}{10}^{-04}1.56\times10−041.56\text{\times}{10}^{-04}1.48\times10−041.48\text{\times}{10}^{-04}2.07\times10−032.07\text{\times}{10}^{-03}1.71\times10−031.71\text{\times}{10}^{-03}9.66\times10−049.66\text{\times}{10}^{-04}1.46\times10−041.46\text{\times}{10}^{-04}1.12\times10−031.12\text{\times}{10}^{-03}1.30\times10−031.30\text{\times}{10}^{-03}1.10\times10−031.10\text{\times}{10}^{-03}8.96\times10−048.96\text{\times}{10}^{-04}8.48\times10−048.48\text{\times}{10}^{-04}
1st Quartile7.29\times10−067.29\text{\times}{10}^{-06}6.07\times10−066.07\text{\times}{10}^{-06}7.85\times10−067.85\text{\times}{10}^{-06}7.01\times10−067.01\text{\times}{10}^{-06}4.33\times10−044.33\text{\times}{10}^{-04}2.84\times10−042.84\text{\times}{10}^{-04}1.74\times10−041.74\text{\times}{10}^{-04}5.52\times10−065.52\text{\times}{10}^{-06}2.33\times10−042.33\text{\times}{10}^{-04}1.92\times10−041.92\text{\times}{10}^{-04}1.60\times10−041.60\text{\times}{10}^{-04}8.69\times10−058.69\text{\times}{10}^{-05}1.33\times10−041.33\text{\times}{10}^{-04}
2nd Quartile4.24\times10−054.24\text{\times}{10}^{-05}4.80\times10−054.80\text{\times}{10}^{-05}4.25\times10−054.25\text{\times}{10}^{-05}3.45\times10−053.45\text{\times}{10}^{-05}7.63\times10−047.63\text{\times}{10}^{-04}5.94\times10−045.94\text{\times}{10}^{-04}3.33\times10−043.33\text{\times}{10}^{-04}3.79\times10−053.79\text{\times}{10}^{-05}6.75\times10−046.75\text{\times}{10}^{-04}5.81\times10−045.81\text{\times}{10}^{-04}4.30\times10−044.30\text{\times}{10}^{-04}2.52\times10−042.52\text{\times}{10}^{-04}3.19\times10−043.19\text{\times}{10}^{-04}
3rd Quartile1.35\times10−041.35\text{\times}{10}^{-04}1.27\times10−041.27\text{\times}{10}^{-04}1.13\times10−041.13\text{\times}{10}^{-04}8.53\times10−058.53\text{\times}{10}^{-05}1.82\times10−031.82\text{\times}{10}^{-03}1.32\times10−031.32\text{\times}{10}^{-03}7.11\times10−047.11\text{\times}{10}^{-04}8.46\times10−058.46\text{\times}{10}^{-05}1.34\times10−031.34\text{\times}{10}^{-03}1.30\times10−031.30\text{\times}{10}^{-03}1.17\times10−031.17\text{\times}{10}^{-03}4.88\times10−044.88\text{\times}{10}^{-04}7.23\times10−047.23\text{\times}{10}^{-04}
TreeMSR             
Table 2: Summary statistics of the relative squared ℓ2\ell_{2} error between estimated and true probabilistic values when m=40nm=40n . We summarize the error over large datasets (n≥30)(n\geq 30) , for which we use the tree-based method described in Appendix D to compute the true probabilistic values. On average over all probabilistic values, Tree MSR produces estimates with mean error that is 390×390\times lower than the best estimator from prior work.
Figure 4: Generalization error between value function vv and learned model ff 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 is a random forest or a neural network, the error of the linear model plateaus while the random forest and XGBoost learned models continue to improve. This phenomenon is reflected in Figures 3 and 7 ; the performance of Tree MSR continues to improve with the number of samples while Linear MSR plateaus.
Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

  Mean Relative Error ( m=40nm=40n , no noise)Runtime Ratio (Cross-fit / All-samples)
Weighting FamilyDatasetsLinear MSRLinear MSR AllTree MSRTree MSR AllLinearTree
Symmetric BetaSmall ( n<30n<30 )8.43\times10−048.43\text{\times}{10}^{-04}7.96\times10−047.96\text{\times}{10}^{-04}2.08\times10−042.08\text{\times}{10}^{-04}3.08\times10−043.08\text{\times}{10}^{-04}2.1×2.1\times8.5×8.5\times
Symmetric BetaBig ( n≥30n\geq 30 )2.18\times10−042.18\text{\times}{10}^{-04}2.23\times10−042.23\text{\times}{10}^{-04}7.55\times10−057.55\text{\times}{10}^{-05}1.90\times10−041.90\text{\times}{10}^{-04}2.3×2.3\times7.6×7.6\times
Asymmetric BetaSmall ( n<30n<30 )9.45\times10−049.45\text{\times}{10}^{-04}8.61\times10−048.61\text{\times}{10}^{-04}1.26\times10−041.26\text{\times}{10}^{-04}1.88\times10−041.88\text{\times}{10}^{-04}2.6×2.6\times8.7×8.7\times
Asymmetric BetaBig ( n≥30n\geq 30 )1.27\times10−031.27\text{\times}{10}^{-03}1.43\times10−031.43\text{\times}{10}^{-03}1.92\times10−041.92\text{\times}{10}^{-04}3.25\times10−043.25\text{\times}{10}^{-04}2.5×2.5\times7.7×7.7\times
Weighted BanzhafSmall ( n<30n<30 )1.51\times10−031.51\text{\times}{10}^{-03}1.31\times10−031.31\text{\times}{10}^{-03}1.55\times10−041.55\text{\times}{10}^{-04}2.34\times10−042.34\text{\times}{10}^{-04}2.5×2.5\times8.2×8.2\times
Appendix
Table 3: Mean relative error at m=40nm=40n without noise, and the ratio of the cross-fit estimator’s ( k=10k=10 ) runtime to the all-samples version’s ( k=1k=1 ), pooled over the datasets in each size group and the weightings in each family (10 runs per dataset and weighting). The lower error of each pair is in bold. Symmetric Beta pools B(1,1), B(2,2), B(4,4), B(8,8); Asymmetric Beta pools B(1,1), B(1,2), B(1,4), B(1,8); Weighted Banzhaf pools WB(0.5) through WB(0.9).
Figure 5: Error of the cross-fit estimators ( k=10k=10 , solid) and the all-samples version ( k=1k=1 , dashed) as a function of sample size on the large datasets ( n≥30n\geq 30 ) without noise; each line is the mean over 10 runs, averaged over datasets. Linear MSR and its all-samples version coincide in every panel; Tree MSR lies below its all-samples version for most weightings and sample sizes.
Figure 6: Probabilistic values by subset size for n=10n=10 . Beta Shapley values B (α,β)(\alpha,\beta) generalize Shapley values for α,β∈[1,∞)\alpha,\beta\in[1,\infty) ; increasing both α\alpha and β\beta flattens beta Shapley values while increasing just α\alpha (or just β\beta ) tilts beta Shapley values. Weighted Banzhaf values WB( pp ) generalize Banzhaf values for p∈(0,1)p\in(0,1) ; increasing (or decreasing) pp tilts weighted Banzhaf values.
 B(1,1)B(2,2)B(4,4)B(8,8)B(1,2)B(1,4)B(1,8)WB(0.5)WB(0.6)WB(0.7)WB(0.8)WB(0.9)Mean
LinearMSR             
Mean7.34\times10−047.34\text{\times}{10}^{-04}8.17\times10−048.17\text{\times}{10}^{-04}8.53\times10−048.53\text{\times}{10}^{-04}9.66\times10−049.66\text{\times}{10}^{-04}1.87\times10−031.87\text{\times}{10}^{-03}9.30\times10−049.30\text{\times}{10}^{-04}2.46\times10−042.46\text{\times}{10}^{-04}7.04\times10−047.04\text{\times}{10}^{-04}2.69\times10−032.69\text{\times}{10}^{-03}2.81\times10−032.81\text{\times}{10}^{-03}1.20\times10−031.20\text{\times}{10}^{-03}1.37\times10−041.37\text{\times}{10}^{-04}1.16\times10−031.16\text{\times}{10}^{-03}
1st Quartile1.55\times10−061.55\text{\times}{10}^{-06}1.30\times10−061.30\text{\times}{10}^{-06}1.23\times10−061.23\text{\times}{10}^{-06}6.17\times10−076.17\text{\times}{10}^{-07}4.21\times10−054.21\text{\times}{10}^{-05}2.66\times10−052.66\text{\times}{10}^{-05}4.04\times10−064.04\text{\times}{10}^{-06}2.09\times10−062.09\text{\times}{10}^{-06}4.71\times10−054.71\text{\times}{10}^{-05}2.34\times10−052.34\text{\times}{10}^{-05}2.14\times10−052.14\text{\times}{10}^{-05}1.96\times10−061.96\text{\times}{10}^{-06}1.45\times10−051.45\text{\times}{10}^{-05}
2nd Quartile6.80\times10−056.80\text{\times}{10}^{-05}7.52\times10−057.52\text{\times}{10}^{-05}1.01\times10−041.01\text{\times}{10}^{-04}6.54\times10−056.54\text{\times}{10}^{-05}1.01\times10−031.01\text{\times}{10}^{-03}5.08\times10−045.08\text{\times}{10}^{-04}1.31\times10−041.31\text{\times}{10}^{-04}1.08\times10−041.08\text{\times}{10}^{-04}1.70\times10−031.70\text{\times}{10}^{-03}1.16\times10−031.16\text{\times}{10}^{-03}5.98\times10−045.98\text{\times}{10}^{-04}4.75\times10−054.75\text{\times}{10}^{-05}4.64\times10−044.64\text{\times}{10}^{-04}
3rd Quartile8.96\times10−048.96\text{\times}{10}^{-04}9.48\times10−049.48\text{\times}{10}^{-04}9.54\times10−049.54\text{\times}{10}^{-04}1.12\times10−031.12\text{\times}{10}^{-03}3.14\times10−033.14\text{\times}{10}^{-03}1.32\times10−031.32\text{\times}{10}^{-03}3.55\times10−043.55\text{\times}{10}^{-04}6.18\times10−046.18\text{\times}{10}^{-04}5.23\times10−035.23\text{\times}{10}^{-03}4.46\times10−034.46\text{\times}{10}^{-03}1.74\times10−031.74\text{\times}{10}^{-03}1.39\times10−041.39\text{\times}{10}^{-04}1.74\times10−031.74\text{\times}{10}^{-03}
TreeMSR             
Appendix
Table 4: Summary statistics of the relative squared ℓ2\ell_{2} error between estimated and true probabilistic values when m=40nm=40n . We summarize the error over small datasets (n<30)(n<30) , for which the probabilistic values of a neural network model can be feasibly computed. On average over all probabilistic values, Tree MSR produces estimates with mean error that is 243×243\times lower than the best estimator from prior work.
Figure 7: 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 small datasets ( n<30n<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 is large.
Figure 8: Error between the estimated and true probabilistic values as a function of noise magnitude. Each subplot shows results for a different probabilistic value with the error averaged over all small datasets ( n<30n<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.
Figure 9: Error between the estimated and true probabilistic values as a function of noise magnitude. Each subplot shows results for a different probabilistic value with the error averaged over all large datasets ( n≥30n\geq 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.
DatasetnnSource / CitationAccess MethodLicense
Adult12[ 17 ]shap.datasetsCC-BY 4.0
Forest Fires13[ 7 ]UCI ML Repo 6 6 6 https://archive.ics.uci.edu/ml/datasets/forest+firesCC-BY 4.0
Real Estate15[ 41 ]UCI ML Repo 7 7 7 https://archive.ics.uci.edu/ml/datasets/Real+estate+valuation+data+setCC-BY 4.0
Bike Sharing16[ 10 ]OpenML 8 8 8 https://www.openml.org/d/42712Public Domain
Breast Cancer30[ 37 ]sklearn.datasetsCC-BY 4.0
Independent60[ 22 ]shap.datasetsMIT
Appendix
Table 5: A summary of the datasets used in our experiments, including source, access method, license, and number of features nn .
More in this topic

Shapley Value Attribution

Shapley value attribution fairly assigns a prediction or outcome among contributing features, data points, agents, or modalities.

See all 102 papers

Explore similar work

CardsList
May 4, 2026

First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint

Probabilistic values, including Shapley values and semivalues, provide a model-agnostic framework to attribute the behavior of a black-box model to data points or features, with a wide range of applications including explainable artificial intelligence and data valuation. However, their exact computation requires utility evaluations over exponentially many coalitions, making Monte Carlo approximation essential in modern machine learning applications. Existing estimators are often developed through different representation strategies, including weighted averages, self-normalized weighting, regression adjustment, and weighted least squares. Our key observation is that these seemingly distinct constructions share a common first-order expansion, in which the leading term is determined by the sampling law and a working surrogate function. This first-order representation yields an explicit expression for the leading mean squared error (MSE), which characterizes how the sampling law and the surrogate jointly determine statistical efficiency. Guided by this criterion, we propose an Efficiency-Aware Surrogate-adjusted Estimator (EASE) that directly chooses the sampling law and surrogate to minimize the first-order MSE. We demonstrate that EASE consistently outperforms existing estimators for various probabilistic values.

Ziqi Liu, Kiljae Lee, Yuan Zhang +1

Department of Statistics & Data Science, Carnegie Mellon University. · Department of Statistics, The Ohio State University.

Value Function EstimationShapley Value AttributionData Valuation
AskPDF
Oct 2, 2024

Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a general model with nn features, O(2n)O(2^n) model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. At the time of our original submission, no strong non-asymptotic complexity guarantees were known for Kernel SHAP. We address this issue by introducing Leverage SHAP, a lightweight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just O(nlog⁡n)O(n\log n) model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we find that Leverage SHAP achieves an approximately 50%50\% reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].

Christopher Musco, R. Teal Witter

New York University

SHAP Feature AttributionShapley Value Attribution
AskPDF
Jun 23, 2026

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

We address the problem of explainability in machine learning models through feature attribution methods. In particular, we consider a variant of Shapley values known as Asymmetric Shapley Values (ASV), which enables the incorporation of causal knowledge into model-agnostic explanations through the use of a causal graph. We show that in certain contexts in which the computation of SHAP is #P\#P-hard, the exact computation of ASV can be done in polynomial time. To extend this algorithmic result, we introduce a notion of equivalence classes over the topological orderings of the underlying causal graph, which is useful to reduce the time to compute ASV. In particular, we present a polynomial-time algorithm (in the number of equivalence classes) to compute it whenever the causal graph is a rooted directed tree. Finally, we develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random. To implement this sampling mechanism we leverage known algorithms as well as simpler alternatives. Our experimental results demonstrate the practical viability of the proposed approach in realistic causal structures.

Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Departamento de Computación, Facultad de Ciencias Exactas y Naturales, UBA · Instituto de Ciencias de la Computación (ICC), CONICET

Cooperative Game TheoryFeature AttributionCausal AttributionShapley Value AttributionCausal Interpretability
AskPDF