A Practical Method for Solving Contextual Bandit Problems Using Decision Trees

Adam N. Elmachtoub, Ryan McNellis, Sechan Oh, Marek Petrik
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:21-30, 2017.

Abstract

Many efficient algorithms with strong theoreti- cal guarantees have been proposed for the con- textual multi-armed bandit problem. However, applying these algorithms in practice can be difficult because they require domain exper- tise to build appropriate features and to tune their parameters. We propose a new method for the contextual bandit problem that is sim- ple, practical, and can be applied with little or no domain expertise. Our algorithm relies on decision trees to model the context-reward re- lationship. Decision trees are non-parametric, interpretable, and work well without hand- crafted features. To guide the exploration- exploitation trade-off, we use a bootstrapping approach which abstracts Thompson sampling to non-Bayesian settings. We also discuss several computational heuristics and demon- strate the performance of our method on sev- eral datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-elmachtoub17a, title = {A Practical Method for Solving Contextual Bandit Problems Using Decision Trees}, author = {Elmachtoub, Adam N. and McNellis, Ryan and Oh, Sechan and Petrik, Marek}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {21--30}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/elmachtoub17a/elmachtoub17a.pdf}, url = {https://proceedings.mlr.press/r15/elmachtoub17a.html}, abstract = {Many efficient algorithms with strong theoreti- cal guarantees have been proposed for the con- textual multi-armed bandit problem. However, applying these algorithms in practice can be difficult because they require domain exper- tise to build appropriate features and to tune their parameters. We propose a new method for the contextual bandit problem that is sim- ple, practical, and can be applied with little or no domain expertise. Our algorithm relies on decision trees to model the context-reward re- lationship. Decision trees are non-parametric, interpretable, and work well without hand- crafted features. To guide the exploration- exploitation trade-off, we use a bootstrapping approach which abstracts Thompson sampling to non-Bayesian settings. We also discuss several computational heuristics and demon- strate the performance of our method on sev- eral datasets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Practical Method for Solving Contextual Bandit Problems Using Decision Trees %A Adam N. Elmachtoub %A Ryan McNellis %A Sechan Oh %A Marek Petrik %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-elmachtoub17a %I PMLR %P 21--30 %U https://proceedings.mlr.press/r15/elmachtoub17a.html %V R15 %X Many efficient algorithms with strong theoreti- cal guarantees have been proposed for the con- textual multi-armed bandit problem. However, applying these algorithms in practice can be difficult because they require domain exper- tise to build appropriate features and to tune their parameters. We propose a new method for the contextual bandit problem that is sim- ple, practical, and can be applied with little or no domain expertise. Our algorithm relies on decision trees to model the context-reward re- lationship. Decision trees are non-parametric, interpretable, and work well without hand- crafted features. To guide the exploration- exploitation trade-off, we use a bootstrapping approach which abstracts Thompson sampling to non-Bayesian settings. We also discuss several computational heuristics and demon- strate the performance of our method on sev- eral datasets. %Z Reissued by PMLR on 04 October 2026.
APA
Elmachtoub, A.N., McNellis, R., Oh, S. & Petrik, M.. (2017). A Practical Method for Solving Contextual Bandit Problems Using Decision Trees. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:21-30 Available from https://proceedings.mlr.press/r15/elmachtoub17a.html. Reissued by PMLR on 04 October 2026.

Related Material