Model Derivation We write the joint posterior as, 2|Y,Z/ (Y|X,, 2) (| 2) (2) (13) / (2) N/2exp(1 2 2 (Y Z)Tdiag(x(Z)) (Y Z)) (2) 1exp(1 2 2 T) (2) (1+

The intermediate steps can be found in [67]. Derivation of Posterior Predictive Note, this derivation takes the priors to be set as in BayesLIME or BayesSHAP, namely, with values close to zero. We apply the identity from equation 17 to derive this posterior. In these derivations, the perturbation matrices Z have elements Zij 2{ 0,1} where each Zij Bernoulli(0.5). Note, in these proofs, we take take the priors to be set as in BayesLIME and BayesSHAP, i.e., they have hyperparameter values close to 0. B.1 Proof of Theorem 3.3 Note that we use N to denote the total perturbations while S denotes the perturabtions collected so far.