Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inference

• URL: http://arxiv.org/abs/2602.24231v1
• Date: Fri, 27 Feb 2026 17:58:37 GMT
• Title: Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inference
• Authors: Hongrui Xie, Junyu Cao, Kan Xu,
• Abstract summary: We provide the first investigation into adaptive experimental design, focusing on the trade-off between regret and statistical power in multi-armed bandits (CMAB)<n>We propose two algorithms MixCombKL and MixCombUCB respectively for two relevant cases under different information structures.
• Score: 2.9618272039677667
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Exploration-free Algorithms for Multi-group Mean Estimation [7.480522058240762]
  We address the problem of multi-group mean estimation, which seeks to allocate a finite sampling budget across multiple groups to obtain uniformly accurate estimates of their means.<n>Unlike classical multi-armed bandits, whose objective is to minimize regret by identifying and exploiting the best arm, the optimal allocation in this setting requires sampling every group on the order of $Theta(T)$ times.
  arXiv  Detail & Related papers  (2025-10-12T00:20:30Z)
• COM-BOM: Bayesian Exemplar Search for Efficiently Exploring the Accuracy-Calibration Pareto Frontier [12.261526989434282]
  Prior search methods narrowly optimize for predictive accuracy and model calibration.<n>In this paper, we formulate a multi-objective optimization problem targeting both the determinant of predictive accuracy and the minimization of expected calibration error.<n>We find that COM-BOM beats or matches the baselines at jointly optimizing the two objectives.
  arXiv  Detail & Related papers  (2025-10-01T17:57:49Z)
• FACTORS: Factorial Approximation for Complementary Two-factor Optimization with Risk-aware Scoring [0.0]
  FACTORS is a framework that combines design of experiments with Shapley decomposition to address performance and stability issues.<n>Our approach consistently estimates main effects and two-factor interactions, then integrates them into a risk-adjusted objective function.
  arXiv  Detail & Related papers  (2025-09-13T14:44:45Z)
• Risk-Averse Best Arm Set Identification with Fixed Budget and Fixed Confidence [0.4199844472131922]
  We introduce a novel problem setting in bandit optimization that addresses maximizing expected reward and minimizing associated uncertainty.<n>We propose a unified meta-budgetalgorithmic framework capable of operating under both fixed-confidence and fixed-optimal regimes.<n>Our approach outperforms existing methods in terms of both accuracy and sample efficiency.
  arXiv  Detail & Related papers  (2025-06-27T14:21:03Z)
• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization [45.99743804547533]
  Two-way partial AUCAUC is a critical performance metric for binary classification with imbalanced data.<n>Existing algorithms for TPAUC optimization remain under-explored.<n>We introduce two innovative double-coordinate block-coordinate algorithms for TPAUC optimization.
  arXiv  Detail & Related papers  (2025-05-28T03:55:05Z)
• Towards Optimal Multi-draft Speculative Decoding [102.67837141152232]
  Multi-Draft Speculative Decoding (MDSD) is a recent approach where, when generating each token, a small draft model generates multiple drafts.<n>This paper discusses the dual of the optimal transport problem, providing a way to efficiently compute the optimal acceptance rate.
  arXiv  Detail & Related papers  (2025-02-26T03:22:44Z)
• Optimal Adaptive Experimental Design for Estimating Treatment Effect [14.088972921434761]
  This paper addresses the fundamental question of determining the optimal accuracy in estimating the treatment effect. By incorporating the concept of doubly robust method into sequential experimental design, we frame the optimal estimation problem as an online bandit learning problem. Using tools and ideas from both bandit algorithm design and adaptive statistical estimation, we propose a general low switching adaptive experiment framework.
  arXiv  Detail & Related papers  (2024-10-07T23:22:51Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  Best arm identification problem elegantly amalgamates regret minimization and BAI. Agent's goal is to identify the best arm with a prescribed confidence level. Double KL-UCB algorithm achieves optimality as the confidence level tends to zero.
  arXiv  Detail & Related papers  (2024-09-27T16:46:02Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  We introduce a new variant of the Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts. We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.
  arXiv  Detail & Related papers  (2023-01-19T18:24:08Z)
• When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee [51.527543027813344]
  We propose systematic and efficient gradient-based methods for both one-way and two-way partial AUC (pAUC) For both one-way and two-way pAUC, we propose two algorithms and prove their convergence for optimizing their two formulations, respectively.
  arXiv  Detail & Related papers  (2022-03-01T01:59:53Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms. We develop a general framework from the perspective of Bregman minimization divergence. We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
  arXiv  Detail & Related papers  (2021-12-07T01:23:20Z)
• An Empirical Study of Assumptions in Bayesian Optimisation [61.19427472792523]
  In this work we rigorously analyse conventional and non-conventional assumptions inherent to Bayesian optimisation. We conclude that the majority of hyper- parameter tuning tasks exhibit heteroscedasticity and non-stationarity. We hope these findings may serve as guiding principles, both for practitioners and for further research in the field.
  arXiv  Detail & Related papers  (2020-12-07T16:21:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.