# Online Learning of Decision Trees with Thompson Sampling

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 42 references that are in the map.
- First posted on arXiv 9 Apr 2024.

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

- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [Efficient non-greedy optimization of decision trees](https://mlsanity.com/paper/1511.04056/) (2015)
- [On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2002.03585/) (2020)
- [On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs](https://mlsanity.com/paper/2209.02864/) (2022)

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

- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)
- [Learning Decision Trees as Amortized Structure Inference](https://mlsanity.com/paper/2503.06985/) (2025)
- [MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound](https://mlsanity.com/paper/2605.11617/) (2026)

## Abstract (arXiv)

Decision Trees are prominent prediction models for interpretable Machine Learning. They have been thoroughly researched, mostly in the batch setting with a fixed labelled dataset, leading to popular algorithms such as C4.5, ID3 and CART. Unfortunately, these methods are of heuristic nature, they rely on greedy splits offering no guarantees of global optimality and often leading to unnecessarily complex and hard-to-interpret Decision Trees. Recent breakthroughs addressed this suboptimality issue in the batch setting, but no such work has considered the online setting with data arriving in a stream. To this end, we devise a new Monte Carlo Tree Search algorithm, Thompson Sampling Decision Trees (TSDT), able to produce optimal Decision Trees in an online setting. We analyse our algorithm and prove its almost sure convergence to the optimal tree. Furthermore, we conduct extensive experiments to validate our findings empirically. The proposed TSDT outperforms existing algorithms on several benchmarks, all while presenting the practical advantage of being tailored to the online setting.