📊 statistics

BFTS: Thompson Sampling with Bayesian Additive Regression Trees

The paper introduces Bayesian Forest Thompson Sampling (BFTS), a novel contextual bandit algorithm that integrates Bayesian Additive Regression Trees (BART) to provide a principled, non-linear probabilistic framework that achieves theoretical regret bounds and superior empirical performance in personalized behavioral interventions.

Original authors: Ruizhe Deng, Bibhas Chakraborty, Ran Chen, Yan Shuo Tan

Published 2026-02-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ruizhe Deng, Bibhas Chakraborty, Ran Chen, Yan Shuo Tan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a personal health coach for thousands of people via a smartphone app. Every day, you have to decide which "nudge" to send to each person to help them stay healthy (e.g., "Time for a walk!" or "Drink some water!").

The problem is, you don't know exactly what works for whom. Some people respond to morning alerts; others only respond to evening ones. Some people are motivated by competition; others by gentle encouragement. If you send the wrong message, they ignore you. If you send the wrong message too often, they get "notification fatigue" and delete the app.

This paper introduces a new "brain" for this coach, called BFTS. Here is how it works, explained through a few simple analogies.

1. The Problem: The "Linear" vs. "Neural" Dilemma

To make decisions, the coach needs a model of how humans behave.

The "Straight Line" Model (Linear): Imagine trying to predict how much a plant grows using only a straight ruler. It’s simple and fast, but life isn't a straight line. If you give a plant too much water, it doesn't just grow "more"—it dies. A straight-line model can't understand that "tipping point."
The "Brain" Model (Neural Networks): This is like a super-complex, massive computer brain. It can understand almost anything, but it’s a "black box." It’s incredibly hard to tune, it requires massive amounts of electricity (computing power), and if you change one tiny setting, the whole thing might crash.

2. The Solution: BFTS (The "Wisdom of the Forest")

The researchers proposed BFTS, which uses something called BART (Bayesian Additive Regression Trees).

The Analogy: The Council of Experts
Instead of one giant, confusing brain (Neural Network) or one simple ruler (Linear Model), imagine BFTS is a Council of 100 Experts.

Each expert is a "Decision Tree." One expert might look only at your age. Another looks only at how much you slept. A third looks at the combination of your age and your sleep.
Each expert is a bit "weak" on their own, but when they all vote together, they create a incredibly nuanced, wavy, complex map of human behavior.
The "Bayesian" Magic: Unlike a standard council where everyone just shouts their opinion, these experts are honest about their uncertainty. If an expert hasn't seen many people like you before, they don't just say, "I think you'll like this message." They say, "I'm 50% sure you'll like this, but I'm actually quite confused."

3. The Strategy: Thompson Sampling (The "Smart Gambler")

How does the coach use this Council of Experts to actually pick a message? They use a strategy called Thompson Sampling.

The Analogy: The Weighted Dice
Imagine the coach has a set of dice for every possible message.

If the Council of Experts is very confident that "Message A" works, the die for Message A is weighted heavily to land on "Success."
If the Council is totally unsure about "Message B," the die for Message B is fair and unpredictable.

When it's time to send a nudge, the coach rolls the dice. Most of the time, the weighted dice will lead them to pick the best message (Exploitation). But occasionally, the "uncertain" dice will roll a high number, forcing the coach to try something new just to see what happens (Exploration). This prevents the coach from getting stuck in a rut.

4. Does it actually work? (The "Drink Less" Test)

The researchers didn't just test this on math problems; they tested it on real human data from a health trial called "Drink Less," which helped people reduce hazardous drinking.

They found that the BFTS "Council of Experts" was much better at predicting what would keep people engaged with the app than the old methods. In fact, it improved engagement rates by over 30%. It was smart enough to realize that a person's "days since downloading the app" and their "baseline risk score" were the most important things to watch, and it adjusted its "dice" accordingly.

Summary: Why is this a big deal?

In short, BFTS gives a digital health coach:

The Nuance of a Human: It understands complex, non-linear behaviors (thanks to the Forest of Experts).
The Honesty of a Scientist: It knows when it is guessing (thanks to the Bayesian math).
The Bravery of a Gambler: It knows when to try something new to learn more (thanks to Thompson Sampling).

Technical Summary: Bayesian Forest Thompson Sampling (BFTS)

Title: BFTS: Thompson Sampling with Bayesian Additive Regression Trees
Authors: Ruizhe Deng, Bibhas Chakraborty, Ran Chen, and Yan Shuo Tan (NUS, Duke-NUS, Duke University, Washington University in St. Louis)
Date: February 10, 2026

1. Problem Statement

The paper addresses the challenge of contextual bandits in personalized mobile health (mHealth) interventions. In these settings, an agent must select treatments (actions) based on complex, non-linear user behaviors (contexts) to maximize health outcomes.

The authors identify a "modeling gap" in current approaches:

Linear Models: Common in mHealth due to simplicity, but suffer from high bias because human behavior is rarely linear.
Neural Networks: Highly expressive but computationally expensive, difficult to tune in online settings, and often "brittle" when hyperparameters cannot be cross-validated in real-time.
Standard Tree Ensembles (e.g., XGBoost, Random Forest): Excellent at predicting tabular data but lack a principled probabilistic framework (Bayesian posterior) required for Thompson Sampling (TS), often relying on heuristic uncertainty quantification that breaks theoretical regret guarantees.

2. Methodology: Bayesian Forest Thompson Sampling (BFTS)

The authors propose BFTS, the first contextual bandit algorithm to integrate Bayesian Additive Regression Trees (BART) directly into the Thompson Sampling exploration loop.

Key Components:

Model Specification: BFTS uses an arm-wise BART prior. Instead of one joint model, it fits $K$ independent BART ensembles (one for each action $a \in A$ ). This preserves the arm-wise posterior factorization necessary for rigorous theoretical analysis.
BART Architecture: It employs a sum-of-trees model where each tree is a weak learner. The authors use a depth-exponential splitting prior to ensure the ensemble adapts to the underlying smoothness of the reward function.
Inference (Practical BFTS): Since exact sampling from the BART posterior is intractable, the algorithm uses Markov Chain Monte Carlo (MCMC) via a Metropolis-within-Gibbs sampler. To manage computational costs, they implement a batched update schedule (refreshing the posterior only at specific intervals $r(t)$ ).
Action Selection: In each round, the algorithm draws a sample from the current BART posterior and selects the action that maximizes the sampled reward function (greedy action).

3. Key Contributions

Algorithm: Introduction of BFTS, combining the predictive power of tree ensembles with the principled uncertainty of Bayesian non-parametrics.
Theoretical Guarantees:
- Bayesian Regret: They derive an information-theoretic Bayesian regret bound of $\tilde{O}(\sqrt{T})$ , proving the algorithm is efficient under a Bayesian design.
- Frequentist Optimality: They analyze a "feel-good" variant (an optimistic modification of TS) and prove it achieves minimax optimality for non-parametric bandits under sparsity assumptions.
Empirical Validation: Extensive testing on synthetic benchmarks, OpenML tabular datasets, and a real-world mHealth trial.

4. Results

Synthetic Benchmarks: BFTS achieved the best average rank (1.63) across eight scenarios, significantly outperforming NeuralTS and linear baselines, especially in non-linear and sparse environments (e.g., Friedman-type rewards).
Uncertainty Calibration: Unlike heuristic tree methods, BFTS demonstrated near-nominal uncertainty calibration (e.g., 95% credible intervals actually covered the true reward ~94% of the time).
OpenML (Tabular Data): BFTS achieved the lowest mean final regret across four representative datasets (Adult, MagicTelescope, Mushroom, Shuttle), outperforming XGBoostTS and RFTS.
Real-World Application (Drink Less mHealth Trial): In an offline policy evaluation of a micro-randomized trial for alcohol reduction, BFTS improved user engagement rates by over 30% compared to the originally deployed policy.
Interpretability: The model provides intrinsic feature importance (e.g., identifying days_since_download and AUDIT_score as key drivers), which is critical for clinical safety.

5. Significance

The significance of this work lies in its ability to bridge the gap between high-performance machine learning (tree ensembles) and rigorous decision theory (Bayesian Thompson Sampling). By providing a method that is both theoretically sound and practically effective for tabular data, BFTS offers a robust framework for deploying personalized, adaptive interventions in sensitive domains like digital health, where understanding uncertainty and feature importance is as vital as maximizing rewards.