# ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation

arXiv: https://arxiv.org/abs/2606.02247 · HTML: https://mlsanity.com/paper/2606.02247/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 47 of its 112 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Builds on (most cited first, 30 of 47)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [TabPFN-2.5: Advancing the State of the Art in Tabular Foundation Models](https://mlsanity.com/paper/2511.08667/) (2025)
- [Reliable Post hoc Explanations: Modeling Uncertainty in Explainability](https://mlsanity.com/paper/2008.05030/) (2020)
- [Modern Bayesian Experimental Design](https://mlsanity.com/paper/2302.14545/) (2023)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [Shapley explainability on the data manifold](https://mlsanity.com/paper/2006.01272/) (2020)
- [Active Testing: Sample-Efficient Model Evaluation](https://mlsanity.com/paper/2103.05331/) (2021)
- [On Statistical Bias In Active Learning: How and When To Fix It](https://mlsanity.com/paper/2101.11665/) (2021)
- [YAHPO Gym -- An Efficient Multi-Objective Multi-Fidelity Benchmark for Hyperparameter Optimization](https://mlsanity.com/paper/2109.03670/) (2021)
- [Prediction-Oriented Bayesian Active Learning](https://mlsanity.com/paper/2304.08151/) (2023)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Optimal experimental design: Formulations and computations](https://mlsanity.com/paper/2407.16212/) (2024)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information](https://mlsanity.com/paper/2104.09460/) (2021)
- [A computational framework for infinite-dimensional Bayesian inverse problems. Part I: The linearized case, with application to global seismic inversion](https://mlsanity.com/paper/1308.1313/) (2013)
- [Sampling for Inference in Probabilistic Models with Fast Bayesian Quadrature](https://mlsanity.com/paper/1411.0439/) (2014)
- [RKHS-SHAP: Shapley Values for Kernel Methods](https://mlsanity.com/paper/2110.09167/) (2021)

## Abstract (arXiv)

Shapley values are a principled attribution measure widely used in interpretable machine learning, but their exact computation scales exponentially with the number of players, motivating a wide range of approximation methods based on value function evaluations of sampled coalitions. This raises the question of whether approximation accuracy can be improved by adaptively selecting coalitions for evaluation based on previous evaluations. This is particularly relevant in settings where the value function is costly and the number of evaluations is severely limited, such as retraining-based feature importance, data valuation, and hyperparameter importance. For this purpose, we propose ShaplEIG, a Bayesian experimental design approach that approximates the expensive value function using a Gaussian process surrogate and adaptively selects coalitions based on their expected information gain about the Shapley values. By the linearity of the Shapley values in the value function, we show that the expected information gain is available in closed form. Furthermore, we propose an efficient computation scheme that reduces the complexity from exponential to polynomial in the number of players via elementary symmetric polynomials. In extensive experiments across diverse costly applications, our method consistently improves sample efficiency in the low-budget regime over state-of-the-art baselines.