Random Forest for the Contextual Bandit Problem

By Raphaël Féraud, Robin Allesiardo, Tanguy Urvoy, Fabrice Clérot. 2015

50 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Estimation Considerations in Contextual Bandits (2017, background): “Related approaches based on random forests or decision trees have been proposed in [30, 29].”
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, methodology): “We evaluated the algorithms (see Appendix A) on several bandit problems constructed from real-world datasets ([26, 27, 28] and Appendix B for details).”
The Impact of Machine Learning on Economics (2018, background): “Glaeser et al. (2018) provides a nice overview of how big data and ML will affect urban economics as a field as well as the operational efficiency of cities.”
Neural Contextual Bandits with UCB-based Exploration (2019, background): “, 2008), random forests (Féraud et al., 2016), Gaussian processes and kernels (Kleinberg et al.”
Decentralized Exploration in Multi-Armed Bandits (2018, background): “r et al (2006), the dueling bandit problem in Urvoy et al (2013), the batched bandit problem in Perchet et al (2015), the linear bandit problem in Soare et al (2014), the contextual bandit problem in Féraud et al (2016), and the non-stationary bandit problem in Allesiardo et al (2017). The decentral”