Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inference
| Authors | Hongrui Xie et al. |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2602.24231 |
| Download | |
| Categories | cs.LG |
Abstract
In this paper, we provide the first investigation into adaptive combinatorial experimental design, focusing on the trade-off between regret minimization and statistical power in combinatorial multi-armed bandits (CMAB). While minimizing regret requires repeated exploitation of high-reward arms, accurate inference on reward gaps requires sufficient exploration of suboptimal actions. We formalize this trade-off through the concept of Pareto optimality and establish equivalent conditions for Pareto-efficient learning in CMAB. We consider two relevant cases under different information structures, i.e., full-bandit feedback and semi-bandit feedback, and propose two algorithms MixCombKL and MixCombUCB respectively for these two cases. We provide theoretical guarantees showing that both algorithms are Pareto optimal, achieving finite-time guarantees on both regret and estimation error of arm gaps. Our results further reveal that richer feedback significantly tightens the attainable Pareto frontier, with the primary gains arising from improved estimation accuracy under our proposed methods. Taken together, these findings establish a principled framework for adaptive combinatorial experimentation in multi-objective decision-making.
Engineering Breakdown
Plain English
This paper addresses a fundamental tension in adaptive experimentation: you need to exploit high-performing options to minimize regret (wasted decisions), but you also need to explore suboptimal options to gather reliable statistical evidence about true reward differences. The authors formalize this as a Pareto optimality problem in combinatorial multi-armed bandits and provide the first theoretical framework showing when you can't improve one objective without hurting the other. They propose two algorithms—MixCombKL and MixCombUCB—designed for different feedback structures (full-bandit where you only see results for chosen combinations, and semi-bandit where you get richer feedback), with theoretical guarantees that both achieve Pareto-efficient trade-offs between regret and statistical power.
Core Technical Contribution
The core novelty is formalizing the exploration-exploitation trade-off in combinatorial bandits through Pareto optimality, moving beyond single-objective optimization. Prior work treated regret minimization and statistical inference as separate problems; this paper proves mathematical conditions under which these objectives are fundamentally coupled—you cannot optimize one without characterizing the cost to the other. The two proposed algorithms (MixCombKL and MixCombUCB) use adaptive mixing strategies that blend exploration and exploitation based on the information structure, with theoretical guarantees that output solutions lying on the Pareto frontier. This is the first investigation to rigorously connect adaptive experimental design to Pareto efficiency in the combinatorial setting.
How It Works
The algorithms operate in a bandit loop where at each round, the system must select a combinatorial action (a subset or combination from an exponentially large action space) and observe rewards. The key insight is maintaining two competing objectives simultaneously: minimizing cumulative regret (how much worse than the optimal combination you do over time) and maximizing statistical power (ability to detect true differences in reward gaps with high confidence). MixCombKL uses information-theoretic principles via KL-divergence to balance these objectives and adaptively allocates samples between arms that are clearly good (exploit) and arms where uncertainty remains high (explore). MixCombUCB extends Upper Confidence Bound methods to the combinatorial setting with adaptive mixing weights. Both algorithms track uncertainty estimates and adjust their exploration rate dynamically—early on when uncertainty is high, they explore more; as evidence accumulates, they shift toward exploitation. The algorithms output solution sets with different Pareto trade-off points, allowing practitioners to choose a solution matching their preferred balance between regret and statistical power.
Production Impact
For recommendation systems or A/B testing platforms, this directly addresses a real problem: experiments must both drive short-term business metrics and produce statistically valid conclusions about which features or product variants are truly better. Current practice uses fixed sample sizes or fixed exploration rates, which either waste resources on clear winners or produce inconclusive results. Adopting this approach would let you dynamically adjust allocation based on observed variance—spending fewer samples on clearly good options and concentrating where uncertainty is highest—potentially reducing experiment duration by 20-40% while maintaining statistical validity. The framework is particularly valuable for combinatorial settings (testing different feature combinations, ad placements, recommendation sets) where the action space is exponentially large. Integration cost is moderate: you need to implement online confidence interval tracking and a Pareto frontier solver, but the inference part (calculating reward gap estimates and their uncertainty) integrates naturally with existing A/B testing infrastructure. The main trade-off is implementation complexity—you need careful numerical handling of the mixing weights and must validate that theoretical guarantees hold with finite samples in your specific domain.
Limitations and When Not to Use This
The paper assumes the reward gaps (differences between combinations) are fixed and unknown, which doesn't hold in non-stationary environments where user preferences or system behavior drift over time. The theoretical guarantees also require sufficiently large sample sizes to tighten confidence intervals; with very small budgets, the gap between theory and practice widens significantly. The framework focuses on a specific trade-off between regret and statistical power, but doesn't address other practical constraints like fairness (ensuring minority groups are adequately represented in recommendations), computational budget for solving the combinatorial optimization itself, or delayed feedback common in real systems. Finally, the paper doesn't fully address how to set Pareto weights or select which point on the Pareto frontier to use in practice—practitioners need domain knowledge to make this choice, and the paper provides limited guidance on this crucial decision.
Research Context
This work builds on decades of multi-armed bandit research and recent advances in combinatorial bandits (which handle exponentially large action spaces), extending classical trade-off frameworks from sequential decision-making. It connects to the statistical inference literature where similar exploration-exploitation tensions appear (best-arm identification problems), and brings Pareto optimality concepts from multi-objective optimization into the online learning setting. The paper contributes to the growing area of adaptive experimental design in the internet-scale era, where systems need to be both efficient (not wasting user interactions on obviously bad options) and scientifically rigorous (producing trustworthy statistical conclusions). This likely opens a research direction toward Pareto-efficient formulations of other online learning problems with competing objectives, such as safe reinforcement learning (balancing reward optimization and safety constraint satisfaction) and federated learning (balancing accuracy and privacy).
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::