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

R. Teal Witter; Yurong Liu; Christopher Musco

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

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\times$ lower than Permutation SHAP (the most popular Monte Carlo method), $6.5\times$ lower than Kernel SHAP (the most popular linear regression method), and $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\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,

v

. 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\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}

. Our Regression MSR estimators reuse samples and have smaller variance that depends on how well a learned function

f

fits the value function

v

, i.e.,

[v(S)-f(S)]^{2}

. Even taking

f

to be linear gives excellent performance (we call this method Linear MSR). Taking

f

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

\ell_{2}

error between estimated and true Shapley values as a function of sample size

m

(number of evaluations of

v

) for various datasets. The lines report the mean error over 10 runs, and

m=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.

\displaystyle\sum_{S\in\mathcal{T}^{(\ell)}}[v(S)-f(S)]^{2}.

Algorithm 1 Regression Maximum Sample Reuse

	Adult	Forest Fires	Real Estate	Bike Sharing	Breast Cancer	Independent	NHANES	Communities	Mean
LinearMSR
Mean	$8.29\text{\times}{10}^{-04}$	$5.54\text{\times}{10}^{-05}$	$1.99\text{\times}{10}^{-08}$	$2.20\text{\times}{10}^{-03}$	$1.03\text{\times}{10}^{-03}$	$9.54\text{\times}{10}^{-05}$	$8.37\text{\times}{10}^{-06}$	$5.92\text{\times}{10}^{-05}$	$5.35\text{\times}{10}^{-04}$
1st Quartile	$2.50\text{\times}{10}^{-05}$	$2.06\text{\times}{10}^{-05}$	$6.66\text{\times}{10}^{-11}$	$4.56\text{\times}{10}^{-04}$	$8.84\text{\times}{10}^{-05}$	$3.96\text{\times}{10}^{-05}$	$9.54\text{\times}{10}^{-08}$	$4.45\text{\times}{10}^{-06}$	$7.93\text{\times}{10}^{-05}$
2nd Quartile	$5.17\text{\times}{10}^{-04}$	$3.15\text{\times}{10}^{-05}$	$1.27\text{\times}{10}^{-09}$	$1.35\text{\times}{10}^{-03}$	$1.13\text{\times}{10}^{-03}$	$7.24\text{\times}{10}^{-05}$	$3.51\text{\times}{10}^{-06}$	$5.43\text{\times}{10}^{-05}$	$3.95\text{\times}{10}^{-04}$
3rd Quartile	$1.47\text{\times}{10}^{-03}$	$8.15\text{\times}{10}^{-05}$	$2.83\text{\times}{10}^{-09}$	$4.23\text{\times}{10}^{-03}$	$1.76\text{\times}{10}^{-03}$	$9.74\text{\times}{10}^{-05}$	$1.50\text{\times}{10}^{-05}$	$8.36\text{\times}{10}^{-05}$	$9.67\text{\times}{10}^{-04}$
TreeMSR

Table 1: Summary statistics of the average relative squared

\ell_{2}

error between estimated and true Shapley values for all datasets listed in Appendix H . All estimators are run with

m=40n

samples. Tree MSR achieves average error that is

11\times

lower than Permutation SHAP,

6.5\times

lower than Kernel SHAP, and

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\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

m

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
Mean	$3.23\text{\times}{10}^{-04}$	$2.44\text{\times}{10}^{-04}$	$1.56\text{\times}{10}^{-04}$	$1.48\text{\times}{10}^{-04}$	$2.07\text{\times}{10}^{-03}$	$1.71\text{\times}{10}^{-03}$	$9.66\text{\times}{10}^{-04}$	$1.46\text{\times}{10}^{-04}$	$1.12\text{\times}{10}^{-03}$	$1.30\text{\times}{10}^{-03}$	$1.10\text{\times}{10}^{-03}$	$8.96\text{\times}{10}^{-04}$	$8.48\text{\times}{10}^{-04}$
1st Quartile	$7.29\text{\times}{10}^{-06}$	$6.07\text{\times}{10}^{-06}$	$7.85\text{\times}{10}^{-06}$	$7.01\text{\times}{10}^{-06}$	$4.33\text{\times}{10}^{-04}$	$2.84\text{\times}{10}^{-04}$	$1.74\text{\times}{10}^{-04}$	$5.52\text{\times}{10}^{-06}$	$2.33\text{\times}{10}^{-04}$	$1.92\text{\times}{10}^{-04}$	$1.60\text{\times}{10}^{-04}$	$8.69\text{\times}{10}^{-05}$	$1.33\text{\times}{10}^{-04}$
2nd Quartile	$4.24\text{\times}{10}^{-05}$	$4.80\text{\times}{10}^{-05}$	$4.25\text{\times}{10}^{-05}$	$3.45\text{\times}{10}^{-05}$	$7.63\text{\times}{10}^{-04}$	$5.94\text{\times}{10}^{-04}$	$3.33\text{\times}{10}^{-04}$	$3.79\text{\times}{10}^{-05}$	$6.75\text{\times}{10}^{-04}$	$5.81\text{\times}{10}^{-04}$	$4.30\text{\times}{10}^{-04}$	$2.52\text{\times}{10}^{-04}$	$3.19\text{\times}{10}^{-04}$
3rd Quartile	$1.35\text{\times}{10}^{-04}$	$1.27\text{\times}{10}^{-04}$	$1.13\text{\times}{10}^{-04}$	$8.53\text{\times}{10}^{-05}$	$1.82\text{\times}{10}^{-03}$	$1.32\text{\times}{10}^{-03}$	$7.11\text{\times}{10}^{-04}$	$8.46\text{\times}{10}^{-05}$	$1.34\text{\times}{10}^{-03}$	$1.30\text{\times}{10}^{-03}$	$1.17\text{\times}{10}^{-03}$	$4.88\text{\times}{10}^{-04}$	$7.23\text{\times}{10}^{-04}$
TreeMSR

Table 2: Summary statistics of the relative squared

\ell_{2}

error between estimated and true probabilistic values when

m=40n

. We summarize the error over large datasets

(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\times

lower than the best estimator from prior work.

Figure 4: Generalization error between value function

v

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 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=40n$ , no noise)				Runtime Ratio (Cross-fit / All-samples)
Weighting Family	Datasets	Linear MSR	Linear MSR All	Tree MSR	Tree MSR All	Linear	Tree
Symmetric Beta	Small ( $n<30$ )	$8.43\text{\times}{10}^{-04}$	$7.96\text{\times}{10}^{-04}$	$2.08\text{\times}{10}^{-04}$	$3.08\text{\times}{10}^{-04}$	$2.1\times$	$8.5\times$
Symmetric Beta	Big ( $n\geq 30$ )	$2.18\text{\times}{10}^{-04}$	$2.23\text{\times}{10}^{-04}$	$7.55\text{\times}{10}^{-05}$	$1.90\text{\times}{10}^{-04}$	$2.3\times$	$7.6\times$
Asymmetric Beta	Small ( $n<30$ )	$9.45\text{\times}{10}^{-04}$	$8.61\text{\times}{10}^{-04}$	$1.26\text{\times}{10}^{-04}$	$1.88\text{\times}{10}^{-04}$	$2.6\times$	$8.7\times$
Asymmetric Beta	Big ( $n\geq 30$ )	$1.27\text{\times}{10}^{-03}$	$1.43\text{\times}{10}^{-03}$	$1.92\text{\times}{10}^{-04}$	$3.25\text{\times}{10}^{-04}$	$2.5\times$	$7.7\times$
Weighted Banzhaf	Small ( $n<30$ )	$1.51\text{\times}{10}^{-03}$	$1.31\text{\times}{10}^{-03}$	$1.55\text{\times}{10}^{-04}$	$2.34\text{\times}{10}^{-04}$	$2.5\times$	$8.2\times$

Appendix

Table 3: Mean relative error at

m=40n

without noise, and the ratio of the cross-fit estimator’s (

k=10

) runtime to the all-samples version’s (

k=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=10

, solid) and the all-samples version (

k=1

, dashed) as a function of sample size on the large datasets (

n\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=10

. Beta Shapley values B

(\alpha,\beta)

generalize Shapley values for

\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(

p

) generalize Banzhaf values for

p\in(0,1)

; increasing (or decreasing)

p

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
Mean	$7.34\text{\times}{10}^{-04}$	$8.17\text{\times}{10}^{-04}$	$8.53\text{\times}{10}^{-04}$	$9.66\text{\times}{10}^{-04}$	$1.87\text{\times}{10}^{-03}$	$9.30\text{\times}{10}^{-04}$	$2.46\text{\times}{10}^{-04}$	$7.04\text{\times}{10}^{-04}$	$2.69\text{\times}{10}^{-03}$	$2.81\text{\times}{10}^{-03}$	$1.20\text{\times}{10}^{-03}$	$1.37\text{\times}{10}^{-04}$	$1.16\text{\times}{10}^{-03}$
1st Quartile	$1.55\text{\times}{10}^{-06}$	$1.30\text{\times}{10}^{-06}$	$1.23\text{\times}{10}^{-06}$	$6.17\text{\times}{10}^{-07}$	$4.21\text{\times}{10}^{-05}$	$2.66\text{\times}{10}^{-05}$	$4.04\text{\times}{10}^{-06}$	$2.09\text{\times}{10}^{-06}$	$4.71\text{\times}{10}^{-05}$	$2.34\text{\times}{10}^{-05}$	$2.14\text{\times}{10}^{-05}$	$1.96\text{\times}{10}^{-06}$	$1.45\text{\times}{10}^{-05}$
2nd Quartile	$6.80\text{\times}{10}^{-05}$	$7.52\text{\times}{10}^{-05}$	$1.01\text{\times}{10}^{-04}$	$6.54\text{\times}{10}^{-05}$	$1.01\text{\times}{10}^{-03}$	$5.08\text{\times}{10}^{-04}$	$1.31\text{\times}{10}^{-04}$	$1.08\text{\times}{10}^{-04}$	$1.70\text{\times}{10}^{-03}$	$1.16\text{\times}{10}^{-03}$	$5.98\text{\times}{10}^{-04}$	$4.75\text{\times}{10}^{-05}$	$4.64\text{\times}{10}^{-04}$
3rd Quartile	$8.96\text{\times}{10}^{-04}$	$9.48\text{\times}{10}^{-04}$	$9.54\text{\times}{10}^{-04}$	$1.12\text{\times}{10}^{-03}$	$3.14\text{\times}{10}^{-03}$	$1.32\text{\times}{10}^{-03}$	$3.55\text{\times}{10}^{-04}$	$6.18\text{\times}{10}^{-04}$	$5.23\text{\times}{10}^{-03}$	$4.46\text{\times}{10}^{-03}$	$1.74\text{\times}{10}^{-03}$	$1.39\text{\times}{10}^{-04}$	$1.74\text{\times}{10}^{-03}$
TreeMSR

Appendix

Table 4: Summary statistics of the relative squared

\ell_{2}

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 a neural network model can be feasibly computed. On average over all probabilistic values, Tree MSR produces estimates with mean error that is

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<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<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\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.

Dataset	$n$	Source / Citation	Access Method	License
Adult	12	[ 17 ]	shap.datasets	CC-BY 4.0
Forest Fires	13	[ 7 ]	UCI ML Repo 6 6 6 https://archive.ics.uci.edu/ml/datasets/forest+fires	CC-BY 4.0
Real Estate	15	[ 41 ]	UCI ML Repo 7 7 7 https://archive.ics.uci.edu/ml/datasets/Real+estate+valuation+data+set	CC-BY 4.0
Bike Sharing	16	[ 10 ]	OpenML 8 8 8 https://www.openml.org/d/42712	Public Domain
Breast Cancer	30	[ 37 ]	sklearn.datasets	CC-BY 4.0
Independent	60	[ 22 ]	shap.datasets	MIT

Appendix

Table 5: A summary of the datasets used in our experiments, including source, access method, license, and number of features

n

Shapley Value Attribution

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

See all 102 papers

First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint
May 4, 2026Ziqi Liu, Kiljae Lee, Yuan Zhang +1Value Function Estimation Shapley Value Attribution
Department of Statistics & Data Science, Carnegie Mellon University. · Department of Statistics, The Ohio State University.
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
Oct 2, 2024Christopher Musco, R. Teal WitterSHAP Feature Attribution Shapley Value Attribution
New York University
Beyond Shapley: Efficient Computation of Asymmetric Shapley Values
Jun 23, 2026Ezequiel Companeetz, Santiago Cifuentes, Sergio AbriolaCooperative Game Theory Feature Attribution
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, UBA · Instituto de Ciencias de la Computación (ICC), CONICET

May 4, 2026J/K move · Enter open · S save

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

Ziqi Liu, Kiljae Lee, Yuan Zhang, Weijing Tang

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

Value Function Estimation Shapley Value Attribution Data Valuation

Open paper AskPDF arXiv

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.

Abstract

Shapley Value Attribution

Explore similar work

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

Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values