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.
Figures & tables
Figure 1: Sample cost on synthetic instances with irrelevant objective-wise near-ties and dominated arms. Points show means over 100 trials and error bars indicate 95% CIs; the horizontal axis is 1/ξ2 .
Figure 2: (a)–(b) Sample cost and sharing gain on the shared-feedback synthetic instance; the dashed line in (b) marks the linear reference y=Q . (c) Sample cost on the Adult model-portfolio task; all methods identify the same optimal pair in every trial.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Confidence calibration. The left panel compares the empirical error rate with the target confidence level, and the right panel reports the corresponding sample complexity.
Figure 4: Scaling with the number of objectives in the known-group setting.
Figure 5: Sensitivity to the representative gap. Both known-group and latent-group identification become harder as the representative gap shrinks.
K
Method
∣SL∣
Pulls
Time (ms)
∣S∣
Φ(S)
32
AFM-Elim
35,960
2,144
42.9
4
0.20
32
BiAFM-Greedy
35,960
9,888
0.35
12
0.00
48
AFM-Elim
194,580
2,480
238.5
4
0.20
48
BiAFM-Greedy
194,580
15,456
0.43
12
0.00
64
AFM-Elim
635,376
2,784
782.8
4
0.20
64
BiAFM-Greedy
635,376
21,184
0.51
12
0.00
Appendix
Table 1: Supplementary latent-group experiment for the polynomial-time bicriteria procedure. AFM-Elim returns the exact size- L optimum, whereas BiAFM-Greedy avoids enumerating SL and returns a bicriteria set within the relaxed budget.
Figure 6: BiAFM-Greedy versus AFM-Elim . The four panels show arm pulls, runtime, returned set size, and true coverage loss as the exact candidate family grows.
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.
Bo Xue, Ji Cheng, Yuanyu Wan +1
City University of Hong Kong · Zhejiang University
We study fixed budget constrained best-arm identification in grouped bandits, where each arm consists of multiple independent attributes with stochastic rewards. An arm is considered feasible only if all its attributes' means are above a given threshold. The aim is to find the feasible arm with the largest overall mean. We first derive a lower bound on the error probability for any algorithm on this setting. We then propose Feasibility Constrained Successive Rejects (FCSR), a novel algorithm that identifies the best arm while ensuring feasibility. We show it attains optimal dependence on problem parameters up to constant factors in the exponent. Empirically, FCSR outperforms natural baselines while preserving feasibility guarantees.
Raunak Mukherjee, Sharayu Moharir
Indian Institute of Technology, Bombay · Dept. of Electrical Engineering, IIT Bombay
In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across K arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any K≥3 and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most (1+8log(K))−1 times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.