BFTS: Thompson Sampling with Bayesian Additive Regression Trees

Abstract

We propose Bayesian Forest Thompson Sampling (BFTS), which performs Thompson sampling using arm-wise Bayesian Additive Regression Trees (BART) to model each action's mean reward and generate MCMC-based posterior draws for decision-making. We derive an information-theoretic Bayesian regret bound of order $\widetilde{\mathcal O}(K\sigma\sqrt{T})$ for ideal posterior sampling under a correctly specified Bayesian design. Empirically, BFTS achieves competitive regret on nonlinear synthetic benchmarks with near-nominal uncertainty calibration, attains the best average rank across nine OpenML contextual bandit benchmarks, and yields higher estimated policy values than linear, neural, and tree-ensemble baselines in a Drink Less micro-randomized trial case study. Across OpenML benchmarks, BFTS is robust to hyperparameter choices.