Random Forest for the Contextual Bandit Problem

Raphaël Féraud, Robin Allesiardo, Tanguy Urvoy, Fabrice Clérot
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:93-101, 2016.

Abstract

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 recursively stacked 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-feraud16, title = {Random Forest for the Contextual Bandit Problem}, author = {Féraud, Raphaël and Allesiardo, Robin and Urvoy, Tanguy and Clérot, Fabrice}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {93--101}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/feraud16.pdf}, url = {https://proceedings.mlr.press/v51/feraud16.html}, abstract = {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 recursively stacked 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.} }
Endnote
%0 Conference Paper %T Random Forest for the Contextual Bandit Problem %A Raphaël Féraud %A Robin Allesiardo %A Tanguy Urvoy %A Fabrice Clérot %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-feraud16 %I PMLR %P 93--101 %U https://proceedings.mlr.press/v51/feraud16.html %V 51 %X 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 recursively stacked 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.
RIS
TY - CPAPER TI - Random Forest for the Contextual Bandit Problem AU - Raphaël Féraud AU - Robin Allesiardo AU - Tanguy Urvoy AU - Fabrice Clérot BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-feraud16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 93 EP - 101 L1 - http://proceedings.mlr.press/v51/feraud16.pdf UR - https://proceedings.mlr.press/v51/feraud16.html AB - 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 recursively stacked 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. ER -
APA
Féraud, R., Allesiardo, R., Urvoy, T. & Clérot, F.. (2016). Random Forest for the Contextual Bandit Problem. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:93-101 Available from https://proceedings.mlr.press/v51/feraud16.html.

Related Material