We present a unified framework of provably efficient randomized estimators for Shapley values. We also provide, for the first time to our knowledge, provable guarantees for KernelSHAP, the most popular Shapley value method.