# BFTS: Thompson Sampling with Bayesian Additive Regression Trees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 57 references that are in the map.
- First posted on arXiv 8 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [Approximate Thompson Sampling via Epistemic Neural Networks](https://mlsanity.com/paper/2302.09205/) (2023)
- [PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits](https://mlsanity.com/paper/1805.07458/) (2018)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [An Actor-Critic Contextual Bandit Algorithm for Personalized Mobile Health Interventions](https://mlsanity.com/paper/1706.09090/) (2017)
- [On Theory for BART](https://mlsanity.com/paper/1810.00787/) (2018)
- [Stochastic tree ensembles for regularized nonlinear regression](https://mlsanity.com/paper/2002.03375/) (2020)
- [Random Forest for the Contextual Bandit Problem - extended version](https://mlsanity.com/paper/1504.06952/) (2015)
- [A sequential Monte Carlo approach to Thompson sampling for Bayesian optimization](https://mlsanity.com/paper/1604.00169/) (2016)
- [A Mixing Time Lower Bound for a Simplified Version of BART](https://mlsanity.com/paper/2210.09352/) (2022)
- [Reinforcement Learning in Modern Biostatistics: Constructing Optimal Adaptive Interventions](https://mlsanity.com/paper/2203.02605/) (2022)
- [Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards](https://mlsanity.com/paper/2304.13593/) (2023)
- [Particle Gibbs for Bayesian Additive Regression Trees](https://mlsanity.com/paper/1502.04622/) (2015)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Thompson sampling for zero-inflated count outcomes with an application to the Drink Less mobile health study](https://mlsanity.com/paper/2311.14359/) (2023)
- [Very fast Bayesian Additive Regression Trees on GPU](https://mlsanity.com/paper/2410.23244/) (2024)
- [Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2511.02123/) (2025)

## Built on by (most cited first, 1 of 1)

- [PFN-TS: Thompson Sampling for Contextual Bandits via Prior-Data Fitted Networks](https://mlsanity.com/paper/2605.10137/) (2026)

## Abstract (arXiv)

Contextual bandits are a core technology for personalized mobile health interventions, where decision-making requires adapting to complex, non-linear user behaviors. While Thompson Sampling (TS) is a preferred strategy for these problems, its performance hinges on the quality of the underlying reward model. Standard linear models suffer from high bias, while neural network approaches are often brittle and difficult to tune in online settings. Conversely, tree ensembles dominate tabular data prediction but typically rely on heuristic uncertainty quantification, lacking a principled probabilistic basis for TS. We propose Bayesian Forest Thompson Sampling (BFTS), the first contextual bandit algorithm to integrate Bayesian Additive Regression Trees (BART), a fully probabilistic sum-of-trees model, directly into the exploration loop. We prove that BFTS is theoretically sound, deriving an information-theoretic Bayesian regret bound of tildeO(√T). As a complementary result, we establish frequentist minimax optimality for a "feel-good" variant, confirming the structural suitability of BART priors for non-parametric bandits. Empirically, BFTS achieves state-of-the-art regret on tabular benchmarks with near-nominal uncertainty calibration. Furthermore, in an offline policy evaluation on the Drink Less micro-randomized trial, BFTS improves engagement rates by over 30% compared to the deployed policy, demonstrating its practical effectiveness for behavioral interventions.