A Practical Method for Solving Contextual Bandit Problems Using Decision Trees

Abstract

Many efficient algorithms with strong theoretical guarantees have been proposed for the contextual multi-armed bandit problem. However, applying these algorithms in practice can be difficult because they require domain expertise to build appropriate features and to tune their parameters. We propose a new method for the contextual bandit problem that is simple, practical, and can be applied with little or no domain expertise. Our algorithm relies on decision trees to model the context-reward relationship. 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 demonstrate the performance of our method on several datasets.

Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI 2017)

References in corpus (3)

• Efficient Optimal Learning for Contextual Bandits
• Bootstrapped Thompson Sampling and Deep Exploration
• A Neural Networks Committee for the Contextual Bandit Problem

Cited by in corpus (10)

• Decision Trees for Decision-Making under the Predict-then-Optimize Framework
• Nonparametric Pricing Analytics with Customer Covariates
• New Insights into Bootstrapping for Bandits
• Perturbed-History Exploration in Stochastic Linear Bandits
• Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
• Residual Bootstrap Exploration for Bandit Algorithms
• Differentiable Linear Bandit Algorithm
• Online Learning and Decision-Making under Generalized Linear Model with High-Dimensional Data
• Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
• Debiasing Samples from Online Learning Using Bootstrap