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.