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

Hongrui Xie; Junyu Cao; Kan Xu

cs.LGFeb 27, 2026

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

Authors: Hongrui Xie, Junyu Cao, Kan Xu

Organizations: University of Science and Technology of China · The University of Texas at Austin · Arizona State University

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.

Figures & tables

Feedback model	Full-Bandit		Semi-Bandit
Admissible pair	$(\pi,\hat{\Delta}_{M,n})$	$(\pi,\hat{\Delta}_{\mu,n})$	$(\pi,\hat{\Delta}_{M,n})$	$(\pi,\hat{\Delta}_{\mu,n})$
Inference error $e(n,\hat{\Delta})$	$\tilde{\mathcal{O}}(\sqrt{md^{3}n^{\alpha-1}})$	$\tilde{\mathcal{O}}(\sqrt{d^{3}n^{\alpha-1}})$	$\tilde{\mathcal{O}}(md\sqrt{n^{\alpha-1}})$	$\tilde{\mathcal{O}}(d\sqrt{n^{\alpha-1}})$
Regret bound $\mathcal{R}_{\nu}(\pi,n)$	$\tilde{\mathcal{O}}(mn^{1-\alpha})$	$\tilde{\mathcal{O}}(mn^{1-\alpha})$	$\tilde{\mathcal{O}}(mn^{1-\alpha})$	$\tilde{\mathcal{O}}(mn^{1-\alpha})$
Pareto Frontier $S_{PF}$	$\tilde{\mathcal{O}}(m\sqrt{d^{3}})$	$\tilde{\mathcal{O}}(\sqrt{md^{3}})$	$\tilde{\mathcal{O}}(d\sqrt{m^{3}})$	$\tilde{\mathcal{O}}(d\sqrt{m})$

Table 1: Pareto Frontier restrictions for fully and semi-bandit feedback models. We consider the estimation for both super arms and basic actions and we set

\lambda_{\min}

for most instances of

\mathcal{M}

so that

\lambda_{\min}^{-1}=\mathcal{O}(dm^{-1})

( Cesa-Bianchi and Lugosi, 2012 ) . The parameter

\alpha

is chosen within the admissible range for each algorithm.

Figure 1: Summary of

\hat{\Delta}_{M,n}

Pareto Frontier Results with Feedback Difference.

Panel of Figure 2 — Figure 2: The regret and MSE plot of MixCombKL .

Panel of Figure 3 — Figure 3: The regret and MSE plot of MixCombUCB .

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Notation	Description
$[i]$	The set $\{1,...,i\}$ , given a positive integer $i$
$n$	Time horizon length
$\mathbb{E}[X]$	Expectation of random variable $X$
$d$	Total number of base arms
$e$	The base arms
$m$	Numbers of based arms in a super arm $M$

Appendix

Table 2: Summary of notations used in this paper.

Combinatorial Multi-Armed Bandits

Combinatorial multi-armed bandits study how to learn which subsets of actions to choose when rewards and feedback are limited.

See all 33 papers

The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits
Sep 19, 2026Changkun Guan, Mengfan XuMulti-Armed Bandits Adversarial Bandits
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology · Mechanical and Industrial Engineering University of Massachusetts Amherst
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
Sep 29, 2026Kaixuan Ji, Qiwei Di, Qingyue Zhao +2Multi-Armed Bandits Minimax Regret
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Selective Ensemble Based on Preference-Directed Multi-Objective Bandits
Jun 20, 2026Lanjihong Ma, Zhen-Yu Zhang, Masashi Sugiyama +1Multi-Armed Bandits Ensemble Learning
Department of Computer Science, Zhejiang Gongshang University, China · Center for Advanced Intelligence Project, RIKEN, Japan · Graduate School of Frontier Sciences, The University of Tokyo, Japan +1

Sep 19, 2026J/K move · Enter open · S save

The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

Changkun Guan, Mengfan Xu

H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology · Mechanical and Industrial Engineering University of Massachusetts Amherst

Multi-Armed Bandits Adversarial Bandits Minimax Regret

Open paper AskPDF arXiv

Adversarial multi-objective bandits hold the potential to help us optimize choices (arms) whose reward is a multidimensional vector chosen by an adversary and whose performance is measured by Pareto regret. We define loss as one minus reward and measure the easiness of a coordinate by the smallest cumulative loss of the arms on it, and call the coordinate easier when this quantity is smaller. Existing work suggests that in theory an easier coordinate may reduce Pareto regret. However, in practice, one may not know which coordinate is easier. On the negative side, we show that this lack of information eliminates the possibility: a smaller cumulative loss does not improve the worst-case order of Pareto regret. Precisely, let

L_d

be the smallest cumulative loss along coordinate

d

over

T

rounds. For

K\ge4

arms,

T\ge6

rounds, and at least 2 coordinates, we prove that the minimax expected Pareto regret is

Ω(\min\{T-L_0,\sqrt{K(T-L_0)}\})

. It is monotonically decreasing in

L_0

, even when

L_0=\min_d L_d

itself is known. On the positive side, this result motivates the possibility that other coordinates, not just the easy one, may suffice to attain the optimal rate of Pareto regret. When

L_0

is known, we apply Poly-INF to a fixed coordinate and obtain an upper bound on Pareto regret that exhibits the same order and thus matches the lower bound. Without such knowledge, we develop a reward-doubling version of Poly-INF that adapts to this unknown quantity while still attaining the matching minimax rate. Another implication is that it has no extra

\log T

factor and is independent of the number of coordinates.

Abstract

Combinatorial Multi-Armed Bandits

Explore similar work

The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

Selective Ensemble Based on Preference-Directed Multi-Objective Bandits