What is the theoretical reason why Thompson Sampling needs to involve posterior distributions? Why can we not sample over predictive distributions? (or is the issue that predictive frequentist distributions are difficult to obtain?)
A "frequentist" alternative to Thompson Sampling is Bootstrap Thompson Sampling (BTS). The general idea is to approximate sampling from a posterior distribution by using a bootstrap distribution. In this paper by Eckles and Kaptein they use an online "double or nothing" bootstrap. You get the nice benefit of constant time updates regardless of if your posterior distribution is computable or not, so no MCMC necessary for distributions without a closed form.
You also may be interested in this paper by Lihong Li. He derives "generalized Thompson sampling" and makes the suggestion that the performance of Thompson sampling is not due to its Bayesian nature, but rather that the Bayesian perspective on Thompson sampling is just a special case of a more general exponential update algorithm.