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

AI summary

Overview

Research area: Machine learning theory — combinatorial multi-armed bandits (CMAB), adaptive experimental design, and multi-objective trade-offs between regret minimization and statistical inference.

Technical level: Advanced. The paper is theoretical: it formalizes a bi-objective optimality notion, proves finite-time minimax-style bounds, and analyzes two feedback regimes. Prior familiarity with bandit regret analysis (UCB, KL-divergence/Online Stochastic Mirror Descent, martingale concentration) is needed to follow the results.

Scope (one sentence): The paper formalizes the tension between minimizing cumulative regret and accurately estimating reward gaps in combinatorial bandits, and proposes two Pareto-optimal algorithms — MixCombKL for full-bandit feedback and MixCombUCB for semi-bandit feedback — each with finite-time guarantees on both regret and estimation error.

What This Paper Is About

In a combinatorial multi-armed bandit, a learner repeatedly selects a "super arm" — a structured combination of base arms, such as a set of interventions or content items — and observes a reward that depends on the combination. Many real applications need two things at once: low cumulative regret (good decisions during the experiment) and accurate estimates of the reward gaps between arms (reliable conclusions after the experiment). These goals pull in opposite directions, because minimizing regret requires repeatedly exploiting high-reward arms, while estimating gaps accurately requires sustained exploration of suboptimal actions.

The paper asks what trade-offs are actually achievable when the action space is combinatorial — potentially exponentially large — and designs algorithms whose regret and estimation error cannot be jointly improved upon by any other policy. It calls such policies Pareto optimal, and studies how the richness of feedback (only the total super-arm reward, versus per-base-arm rewards) changes the attainable frontier.

Key Contributions

1. Pareto-optimal algorithms for combinatorial bandits. The paper develops MixCombKL for full-bandit feedback and MixCombUCB for semi-bandit feedback. Both dynamically calibrate exploration to preserve estimation accuracy and regret performance, described as maintaining Pareto optimality regardless of the complexity of the combinatorial action space. This is stated to be the first systematic study of Pareto optimality in the context of combinatorial bandit feedback.

2. Theoretical guarantees under different bandit feedback models. The paper derives finite-sample regret bounds and estimation error guarantees for both settings and establishes their Pareto optimality, with the analysis handling concentration of information in the super-arm subspace.

3. A comparison of feedback regimes on the Pareto frontier. The analysis shows semi-bandit feedback yields a sharper Pareto frontier than full-bandit feedback, with the improvement arising from reduced estimation error, while regret under the two regimes remains of the same order when the proposed algorithms are used.

4. A formal framework for the regret–inference trade-off in CMAB. The paper defines Pareto optimality for combinatorial bandit policies and characterizes the Pareto frontier as the solution to a multi-objective problem that minimizes worst-case regret and worst-case maximum gap-estimation error simultaneously.

Main Findings

• The trade-off is formalized as Pareto optimality. A policy pair (π, Δ̂) — an algorithm plus a gap estimator — is Pareto optimal if no alternative admissible pair is at least as good on both cumulative regret and maximum estimation error while being strictly better in at least one of them (Definition 3.1). The Pareto frontier is the set of all such non-dominated policies (Definition 3.2). Comparisons are made up to constant (and logarithmic) factors, following the convention used by Simchi-Levi and Wang (2025).

• Two feedback models are distinguished. In full-bandit feedback only the aggregate reward f(M(t), w_t) is revealed; in semi-bandit feedback the individual component rewards w_t(e) for e in M are observed. The paper also restricts attention to estimable base actions — 𝒜_ad in general, ℳ_KL for full-bandit and ℳ_UCB for semi-bandit — because combinatorial feedback generally prevents estimation of all base actions in 𝒜.

• MixCombKL estimation guarantee (full-bandit). With probability at least 1 − δ, |Δ̂_{M,n}^{(i,j)} − Δ_M^{(i,j)}| ≤ (6/λ_min) · sqrt(m³d / n^{1−α}) · ln(2d/δ); and for base-arm gaps, |Δ̂_{μ,n}^{(i,j)} − Δ_μ^{(i,j)}| ≤ (6m/λ_min) · sqrt(d / n^{1−α}) · ln(2d/δ). Taking δ = 1/n², both maximum estimation errors are Õ(sqrt(n^{α−1})).

• MixCombKL regret guarantee (full-bandit). Regret satisfies R_ν(n, π) ≤ 2·sqrt(m³n(d + m^{1/2}/λ_min) log ρ_min^{-1}) + m n^{1−α}/(2(1−α)) + (m^{5/2}/λ_min) log ρ_min^{-1}. For most classes of ℳ, where ρ_min^{-1} = O(poly(d)) and m(d λ_min)^{-1} = O(1), this becomes O(sqrt(m³dn log(d/m)) + m n^{1−α}). The uniform-exploration step (when U_t = 1) adds an O(n^{1−α}) term on top of the bound of Combes et al. (2015).

• MixCombUCB estimation guarantee (semi-bandit). With probability at least 1 − δ, |Δ̂_{M,n}^{(i,j)} − Δ_M^{(i,j)}| ≤ 6md·sqrt(n^{α−1})·ln(2d/δ), and |Δ̂_{μ,n}^{(i,j)} − Δ_μ^{(i,j)}| ≤ 6d·sqrt(n^{α−1})·ln(2d/δ). With δ = 1/n², both maximum estimation errors are Õ(sqrt(n^{α−1})). Notably, the base-arm bound has no m factor and no 1/λ_min factor relative to the full-bandit case.

• Feedback richness tightens the frontier mainly through estimation. Both algorithms achieve maximum estimation error of order Õ(sqrt(n^{α−1})), but semi-bandit feedback yields a sharper frontier, with the improvement attributed to reduced estimation error rather than to regret.

• The parameter α is the explicit trade-off knob. For MixCombKL, α ∈ [0, 1/2]; α = 0 gives equal probability of uniform or KL-based sampling at each time, and larger α shifts the algorithm toward regret. For MixCombUCB, α_t = 1/(m_0 t^α), and the admissible range of α is [0, 1] when the large-gap property Δ_{e,min} = Θ(1) holds for all e ∈ 𝒜, and [0, 1/2] when it does not.

• Large-gap property yields sharper regret for the semi-bandit case. The paper defines the minimum gap Δ_{e,min} = f(M*, μ) − max_{M ∈ ℳ: e ∈ M, Δ_M > 0} f(M, μ) over suboptimal items, and states that a non-vanishing gap allows the algorithm to distinguish suboptimal actions more quickly. The provided content is truncated before the full statement of the semi-bandit regret theorem, so that bound is not reported here.

• No empirical results appear in the provided content. The paper's claims in the excerpt are theoretical; computational efficiency is stated to be analyzed in Appendix B, and an example of a restricted bandit structure is given in Appendix G.

Methodology in Plain English

The researchers start by writing down a standard stochastic CMAB model: a set of base arms 𝒜 = {1, ..., d}, a family of feasible super arms ℳ ⊆ 2^𝒜, and a reward distribution ν over [0,1]^d whose mean is μ. Rewards are additive over the selected super arm, f(M(t), w_t) = sum over e in M(t) of w_t(e), and every super arm is constrained to have exactly m base arms in the full-bandit analysis (relaxed to |M| ≤ m for semi-bandit). Performance is measured by cumulative regret against the best super arm M*, and inference quality is measured by the expected absolute error of an estimator Δ̂ of either base-arm gaps Δ_μ^{(i,j)} or super-arm gaps Δ_M^{(i,j)}.

They then cast the joint objective as a multi-objective minimization: minimize, over policies and estimators, the worst-case pair (regret, maximum estimation error). A policy is Pareto optimal when no other policy improves one coordinate without worsening the other.

Algorithm design follows the information structure:

• For full-bandit feedback, classical UCB is impractical because per-arm play counts do not exist — individual base-arm rewards are never observed, and the super-arm space can be exponentially large. The authors instead build on Online Stochastic Mirror Descent and use KL divergence as the Bregman divergence for projecting onto the scaled convex hull of the vectorized super arms. Each super arm M is vectorized as a binary indicator vector θ_M with L1 norm m. At each round the algorithm forms a mixture q'{t−1} = (1 − γ)q{t−1} + γρ⁰ of the current distribution and a fixed exploration distribution ρ⁰ induced by the uniform distribution over ℳ; a Bernoulli variable U_t with P(U_t = 1) = 1/(2t^α) occasionally forces a uniform super-arm sample; otherwise a KL-projection update is applied to inverse-propensity-weighted reward estimates w̃_t(e) = f(M(t), w_t) Σ_{t−1}^+ θ_M. Running reward accumulators R_t for super arms and for the estimable single-arm set ℳ_KL are output as gap estimates.

• For semi-bandit feedback, per-arm confidence intervals are easy to construct, so the authors use a UCB-style scheme. An initialization routine InitUCB probes the optimization oracle on an auxiliary binary weight vector until every base arm has been observed at least once, terminating in at most d steps and yielding m_0 initialization steps. During the main loop, each base arm gets a UCB index U_t(e) = ŵ(e) + sqrt(2 log t / s). The algorithm plays the UCB-optimal super arm M̃(t) with probability 1 − m_0 α_t, and each recorded initialization super arm M_e with probability α_t = 1/(m_0 t^α). Running estimates R_t(e) are updated with inverse-propensity weighting by the probability that e ∈ M(t).

The theoretical work uses martingale constructions to bound estimation error and a "triangle inequality" type lemma relating KL divergence to expected reward differences (analogous to Lemma 4 in Combes et al. (2015)) to bound regret. The design departs from Combes et al. (2015) by using a mixture of distributions as the super-arm sampling distribution to improve inference accuracy, and from Kveton et al. (2015) by randomizing the selection rather than always playing the UCB-optimal super arm.

Why This Matters

Impact on research. Pareto frontiers for bandits were first developed for classical multi-armed bandits by Zhong et al. (2023), and Simchi-Levi and Wang (2025) proved a sufficient and necessary condition for Pareto optimality with a corresponding algorithm; the framework was later extended to multinomial logistic bandits (Zuo and Qin, 2025) and network inference (Zhang and Wang, 2025). This paper extends the framework to CMAB, where the exponential super-arm space makes applying prior methods computationally infeasible, and shows how feedback richness governs where the frontier sits.

Real-world applications (all cited in the paper):

• Online advertising, where multiple ads or creatives are combined and the platform needs

Authors’ 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.