Reproduce “A Practical Method for Solving Contextual Bandit Problems Using Decision Trees” on OpenResearch

About this paper

Adam N. Elmachtoub, Ryan McNellis, Sechan Oh, Marek Petrik

Researchers from Columbia University and Moloco developed TreeBootstrap, a practical, parameter-free method for contextual bandit problems that combines decision trees with bootstrapping, and its efficient heuristic TreeHeuristic. The approach achieved lower cumulative regret on a simulated dataset and competitive performance against established benchmarks on real-world datasets without requiring manual tuning or extensive feature engineering.

Key insights

• Decision trees serve as effective non-parametric base learners for contextual bandits, reducing the need for feature engineering and offering robustness to complex, non-linear reward structures.
• Bootstrapping provides a parameter-free method to simulate posterior sampling for non-parametric models, effectively managing the exploration-exploitation trade-off akin to Thompson sampling.
• Balancing computational efficiency with performance, the TreeHeuristic approach demonstrates that localized uncertainty estimation within decision tree leaf nodes can yield competitive results while significantly reducing computational overhead.

Summary by alphaXiv.