Optimal decision trees improve A B test accuracy with smaller samples
Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments
Machine Learning
Summary
Online A/B tests help websites and apps understand what changes work better by comparing different versions. The authors focus on making these tests more accurate without needing more people to participate. They created a method using special decision trees that split users into groups based on features to reduce variance in results. Their approach finds the best way to create these groups to make the test results clearer and easier to understand.
What this means in practice
- •For data scientists: Design A/B tests with more precise statistical estimates without increasing sample sizes using optimized stratification.
- •For marketing analysts: Improve measurement of campaign effects by grouping customers into interpretable segments that minimize result variance.
Authors
Tomoka Takei, Shunnosuke Ikeda, Yuichi Takano
Abstract
Online controlled experiments, or A/B tests, are widely used to estimate causal effects on digital platforms. A central challenge is to improve experimental sensitivity, or statistical power, without increasing the experimental sample size. Stratified sampling is a classical variance reduction technique; however, its effectiveness depends critically on how the strata are constructed. We thus propose an optimization-based stratification framework for stratified sampling using optimal multi-way decision trees. Our method, called Optimal Multi-way Stratification Trees (OMST), formulates stratification as a path-selection problem over a feature graph. The selected paths define interpretable stratification rules and are optimized using an exact variance-minimizing binary optimization formulation under continuous proportional allocation and a Neyman-type optimal allocation. We incorporate supervised optimal binning to generate outcome-relevant candidate splits for numerical features. Furthermore, we introduce reduction procedures for redundant candidate paths and assignment constraints, substantially reducing the optimization problem size. Experiments on both a real-world and a simulated dataset demonstrate that OMST achieves comparable or superior variance reduction to existing methods while maintaining shallow and interpretable stratification trees.