BFTS: Thompson Sampling with Bayesian Additive Regression Trees

Technische Samenvatting: BFTS

1. Probleemstelling (The Problem)

Het onderzoek richt zich op het contextual bandit-probleem, een kerntechnologie voor gepersonaliseerde interventies in de digitale gezondheidszorg (mobile health of mHealth). In dit scenario moet een algoritme (de 'agent') herhaaldelijk acties (behandelingen) selecteren op basis van de context van een gebruiker (bijv. leeftijd, gedragspatronen) om de beloning (bijv. gezondheidsuitkomsten of gebruikersbetrokkenheid) te maximaliseren.

De auteurs identificeren een fundamentele kloof in de huidige methoden:

• Lineaire modellen: Worden veel gebruikt vanwege eenvoud, maar schieten tekort omdat menselijk gedrag zelden lineair is (hoge bias).
• Neurale netwerken: Zijn expressief, maar vaak instabiel, moeilijk te tunen in online settings en rekentechnisch zwaar.
• Tree ensembles (zoals Random Forests): Presteren uitstekend op tabeldata, maar missen een principieel probabilistisch kader voor Thompson Sampling (TS), waardoor onzekerheid vaak via heuristieken wordt benaderd in plaats van via een exacte Bayesiaanse posterior.

2. Methodologie (Methodology)

De auteurs introduceren Bayesian Forest Thompson Sampling (BFTS). Het kernidee is om de voorspellende kracht van boom-ensembles te combineren met de theoretische strengheid van Bayesiaanse statistiek.

• Model: Bayesian Additive Regression Trees (BART): In plaats van heuristische bomen gebruikt BFTS BART, een volledig probabilistisch "sum-of-trees" model. Dit model levert een exacte Bayesiaanse posterior over de beloningsfuncties.
• Algoritme: BFTS voert Thompson Sampling uit door parameters te samplen uit de BART-posterior. Omdat exacte sampling onmogelijk is, gebruikt het algoritme Markov Chain Monte Carlo (MCMC) via een Metropolis-within-Gibbs sampler.
• Implementatie: Om de rekenlast te beheersen, wordt een batched update schema gebruikt (een refresh-functie $r(t)$), waarbij de posterior niet bij elke stap, maar periodiek wordt bijgewerkt.
• Arm-wise modeling: Elke actie (arm) krijgt een eigen onafhankelijk BART-model. Dit zorgt ervoor dat de posterior factoriseert, wat essentieel is voor de theoretische bewijsvoering.

3. Belangrijkste Bijdragen (Key Contributions)

Het paper levert drie cruciale bijdragen:

1. Algoritmisch: De introductie van BFTS, het eerste contextual bandit-algoritme dat BART direct integreert in de exploratie-loop voor een robuuste balans tussen exploratie en exploitatie.
2. Theoretisch:
   • Bayesiaanse Regret Bound: De auteurs bewijzen dat de verwachte Bayesiaanse regret van het ideale BFTS-algoritme voldoet aan $\tilde{O}(\sqrt{T})$.
   • Frequentistische Optimaliteit: Ze tonen aan dat een "feel-good" variant van het algoritme (die extra optimisme toevoegt) minimax-optimaal is voor niet-parametrische klassen onder aannames van schaarsheid (sparsity).
3. Empirisch: Validatie op zowel synthetische benchmarks als echte klinische data, waarbij BFTS superieur blijkt aan bestaande methoden zoals NeuralTS en XGBoostTS.

4. Resultaten (Results)

• Synthetische benchmarks: BFTS presteert consistent beter dan lineaire en neurale baselines, vooral in scenario's met niet-lineaire interacties en heteroscedastische ruis (variërende variantie). Het algoritme vertoont bovendien een uitstekende onzekerheidskalibratie (de voorspelde betrouwbaarheidsintervallen komen overeen met de werkelijke fouten).
• OpenML Benchmarks: Op diverse tabel-datasets behaalt BFTS de laagste gemiddelde regret, wat de superioriteit voor tabeldata bevestigt.
• Case Study (Drink Less mHealth trial): In een real-world test met een app voor alcoholreductie verbeterde BFTS de geschatte gebruikersbetrokkenheid met meer dan 30% ten opzichte van het bestaande beleid. Bovendien is het model interpreteerbaar: de boomstructuur laat zien welke variabelen (zoals leeftijd en tijd sinds download) de beslissingen het meest beïnvloeden.

5. Betekenis (Significance)

De publicatie van BFTS is significant omdat het een brug slaat tussen de praktische dominantie van tree-based machine learning en de theoretische strengheid van Bayesian reinforcement learning. Voor de medische sector (mHealth) betekent dit dat er een algoritme beschikbaar is dat niet alleen effectief is in het personaliseren van interventies, maar ook de nodige onzekerheid en interpreteerbaarheid biedt die cruciaal zijn voor klinische veiligheid en validatie.