Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments
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.
Related
- On the efficiency of highly stratified experiments
- Post-stratified importance sampling
- Towards stratified sampling for redistricting plans
- A Tutorial on Safe Anytime-Valid Inference: Practical Maximally Flexible Sampling Designs for Experiments Based on e-Values
- Auxiliary-Driven Transformations for Efficient Mean Estimation Under Stratified Systematic Sampling
BibTeX
@misc{takei2026optimal,
title = {{Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments}},
author = {Tomoka Takei and Shunnosuke Ikeda and Yuichi Takano},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23308},
eprint = {2609.23308},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23308},
}
RIS
TY - UNPB
TI - Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments
AU - Tomoka Takei
AU - Shunnosuke Ikeda
AU - Yuichi Takano
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23308
UR - https://arxiv.org/abs/2609.23308
AB - 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.
ER -