# Random Forest for the Contextual Bandit Problem - extended version

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2015.

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

- [Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent](https://mlsanity.com/paper/2102.07567/) (2021)
- [Tsetlin Machine for Solving Contextual Bandit Problems](https://mlsanity.com/paper/2202.01914/) (2022)
- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [LLMs-augmented Contextual Bandit](https://mlsanity.com/paper/2311.02268/) (2023)
- [Tree Ensembles for Contextual Bandits](https://mlsanity.com/paper/2402.06963/) (2024)
- [Variance-Aware Linear UCB with Deep Representation for Neural Contextual Bandits](https://mlsanity.com/paper/2411.05979/) (2024)
- [Universality of parametric Coupling Flows over parametric diffeomorphisms](https://mlsanity.com/paper/2202.02906/) (2022)
- [Efficient Online Decision Tree Learning with Active Feature Acquisition](https://mlsanity.com/paper/2305.02093/) (2023)
- [Active and Passive Causal Inference Learning](https://mlsanity.com/paper/2308.09248/) (2023)
- [BFTS: Thompson Sampling with Bayesian Additive Regression Trees](https://mlsanity.com/paper/2602.07767/) (2026)
- [Efficient Learning for Selecting Top-m Context-Dependent Designs](https://mlsanity.com/paper/2305.04086/) (2023)

## Abstract (arXiv)

To address the contextual bandit problem, we propose an online random forest algorithm. The analysis of the proposed algorithm is based on the sample complexity needed to find the optimal decision stump. Then, the decision stumps are assembled in a random collection of decision trees, Bandit Forest. We show that the proposed algorithm is optimal up to logarithmic factors. The dependence of the sample complexity upon the number of contextual variables is logarithmic. The computational cost of the proposed algorithm with respect to the time horizon is linear. These analytical results allow the proposed algorithm to be efficient in real applications, where the number of events to process is huge, and where we expect that some contextual variables, chosen from a large set, have potentially non- linear dependencies with the rewards. In the experiments done to illustrate the theoretical analysis, Bandit Forest obtain promising results in comparison with state-of-the-art algorithms.