BFTS: Thompson Sampling with Bayesian Additive Regression Trees

Ruizhe Deng, Bibhas Chakraborty, Ran Chen, Yan Shuo Tan
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:23780-23829, 2026.

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\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-deng26b, title = {{BFTS}: Thompson Sampling with {B}ayesian Additive Regression Trees}, author = {Deng, Ruizhe and Chakraborty, Bibhas and Chen, Ran and Tan, Yan Shuo}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {23780--23829}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/deng26b/deng26b.pdf}, url = {https://proceedings.mlr.press/v306/deng26b.html}, 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\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.} }
Endnote
%0 Conference Paper %T BFTS: Thompson Sampling with Bayesian Additive Regression Trees %A Ruizhe Deng %A Bibhas Chakraborty %A Ran Chen %A Yan Shuo Tan %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-deng26b %I PMLR %P 23780--23829 %U https://proceedings.mlr.press/v306/deng26b.html %V 306 %X 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\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.
APA
Deng, R., Chakraborty, B., Chen, R. & Tan, Y.S.. (2026). BFTS: Thompson Sampling with Bayesian Additive Regression Trees. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:23780-23829 Available from https://proceedings.mlr.press/v306/deng26b.html.

Related Material