When More Objectives Make Identification Easier: The Role of Preferences and Feedback

Bo Xue; Ji Cheng; Yuanyu Wan; Shuang Qiu

cs.LGOct 13, 2026

When More Objectives Make Identification Easier: The Role of Preferences and Feedback

Authors: Bo Xue, Ji Cheng, Yuanyu Wan, Shuang Qiu

Organizations: City University of Hong Kong · Zhejiang University

Abstract

Best-arm identification (BAI) aims to identify the optimal arm using as few samples as possible. While most existing work focuses on a single objective, many real-world applications involve multiple criteria, which motivates the study of BAI in multi-objective bandits. Intuitively, multi-objective identification seems harder, since the learner must identify optimal arms in a higher-dimensional reward space; however, the additional objectives also provide richer feedback that can reduce the required exploration. In this paper, we characterize when and why multiple objectives can make BAI easier. For Gaussian bandits, we establish a characteristic-time lower bound for fixed-confidence identification that holds uniformly across preference orders. Through explicit comparisons under Pareto, linear, and lexicographic preferences, we reveal three phenomena: (i) identifying a larger optimal set can require fewer samples than identifying a unique optimum; (ii) the advantage of vector feedback over coordinate feedback depends fundamentally on the preference order; and (iii) multi-objective identification can require fewer samples than even the easiest corresponding single-objective problem. Finally, we propose Order-Aware Track-and-Stop (OATS), an algorithm that is correct at any prescribed confidence level and asymptotically matches the lower bound.

Figures & tables

Figure 1: Synthetic results for Propositions 1 – 3 and Theorem 2 . (a) The ratio

\mathbb{E}[\tau_{\mathrm{lex}}]/\mathbb{E}[\tau_{\mathrm{P}}]

grows with

M

: Pareto-set identification becomes increasingly easier than lexicographic identification. (b) The feedback gain

\mathbb{E}[\tau_{\mathrm{coord}}]/\mathbb{E}[\tau_{\mathrm{vec}}]

grows with

M

under the Pareto order but remains near one under the lexicographic order. (c) The gain

\mathbb{E}[\tau_{\mathrm{best}}]/\mathbb{E}[\tau_{\mathrm{vec}}]

increases with

M

under all three orders and stays above one, confirming multi-objective acceleration. (d) The normalized stopping time

\mathbb{E}_{\bm{\mu}}[\tau_{\delta}]/\log(1/\delta)

decreases toward the corresponding characteristic time as

\delta

decreases. Markers show empirical means with 95% confidence intervals, and dashed lines show theoretical predictions.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: HELM-derived Gaussian instances. (a) Empirical CDF of the theoretical gain across within-scenario model pairs; a gain above

1

indicates a multi-objective speedup over the best scalar benchmark. (b) Observed stopping time versus

T_{\preceq}(\bm{\mu})\log(1/\delta)

for eligible Pareto and linear instances, showing that

T_{\preceq}(\bm{\mu})

captures instance difficulty on HELM-derived geometries.

Allocation	Mean $\tau$	95% CI	Errors
OATS	$\bm{61{,}797}$	$[61{,}119,62{,}474]$	$0/500$
Uniform	$87{,}600$	$[86{,}663,88{,}538]$	$0/500$
Oracle-Track	$61{,}938$	$[61{,}289,62{,}588]$	$0/500$

Appendix

Table 1: A four-arm HELM-derived linear instance (Best ChatGPT Prompts scenario,

\delta=0.05

). All methods share the same evidence statistic and stopping threshold. We report the mean stopping time, its 95% confidence interval, and the number of incorrect answers over 500 trials. Oracle-Track uses the true mean matrix and is not implementable.

Check	Setting	$T_{\preceq}(\bm{\mu})$	Mean $\tau$
Gap scaling	$\Delta=0.5$	$10.667$	$631.2$
Gap scaling	$\Delta=1$	$2.667$	$133.4$
Gap scaling	$\Delta=2$	$0.667$	$28.3$
Unequal linear weights	$M=4$	$2.400$	$94.5$
Unequal linear weights	$M=8$	$1.259$	$58.3$
Unequal linear weights	$M=12$	$0.855$	$45.3$

Appendix

Table 2: Additional two-arm synthetic checks (

\delta=0.05

, 500 repetitions).

$K$	$M$	$T_{\preceq}(\bm{\mu})$	OATS	Uniform	Oracle-Track
$5$	$3$	$3.568$	$302$	$397$	$312$
$5$	$5$	$3.568$	$354$	$470$	$367$
$5$	$8$	$3.568$	$420$	$561$	$438$
$10$	$3$	$4.765$	$792$	$1586$	$813$
$10$	$5$	$4.765$	$933$	$1876$	$958$
$10$	$8$	$4.765$	$1118$	$2250$	$1127$

Appendix

Table 3: Linear identification with larger

K

(

\delta=0.05

, 500 repetitions). The last three columns report empirical mean stopping times. Oracle-Track uses the true instance and is not implementable.

Explore similar work

Few-for-Many Best-Arm Identification in Multi-Objective Bandits
Oct 12, 2026Bo Xue, Yilu Liu, Haodong Jing +3Multi-Armed Bandits Best-Arm Identification
City University of Hong Kong. · Xi’an Jiaotong University. · Northwest Polytechnical University.
On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
Mar 11, 2026Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1Multi-Armed Bandits Best-Arm Identification
University of Washington
Nearly Optimal Best Arm Identification for Semiparametric Bandits
Apr 5, 2026Seok-Jin KimBest-Arm Identification Multi-Armed Bandits
Columbia University

Oct 12, 2026J/K move · Enter open · S save

Few-for-Many Best-Arm Identification in Multi-Objective Bandits

Bo Xue, Yilu Liu, Haodong Jing, Hongzong Li+2

City University of Hong Kong. · Xi’an Jiaotong University. · Northwest Polytechnical University.

Multi-Armed Bandits Best-Arm Identification

Open paper AskPDF arXiv

Real-world systems often serve many objectives but can deploy only a few options, whose performance must be learned from noisy feedback. Modeling each option as an arm in a multi-objective bandit, we introduce few-for-many best-arm identification, which seeks a small set of arms minimizing the worst weighted degradation from the objective-wise optima, rather than the best arm for every objective. We consider both known objective groups and latent groups specified only by a representative budget, and propose GFM-Elim and AFM-Elim with instance-dependent sample-complexity guarantees. For Gaussian rewards, we further derive a lower bound for the latent-group setting and show that it is asymptotically attainable with high probability by an oracle-based Track-and-Stop procedure. Our results show that sharing observations across objectives and ignoring irrelevant objective-wise distinctions can substantially reduce the sampling cost, as confirmed by experiments on synthetic and real-world tasks.

Abstract

Explore similar work

Few-for-Many Best-Arm Identification in Multi-Objective Bandits

On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

Nearly Optimal Best Arm Identification for Semiparametric Bandits