Paper deep dive
Few-for-Many Best-Arm Identification in Multi-Objective Bandits
Bo Xue, Yilu Liu, Haodong Jing, Hongzong Li, Xi Lin, Shuang Qiu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 \emph{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 \textsc{GFM-Elim} and \textsc{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.
Tags
Links
- Source: https://arxiv.org/abs/2610.16840v1
- Canonical: https://arxiv.org/abs/2610.16840v1
Trouble viewing inline? Open PDF directly →
Full Text
100,405 characters extracted from source content.
Expand or collapse full text
22footnotetext: Corresponding Author Few-for-Many Best-Arm Identification in Multi-Objective Bandits Bo XueYilu LiuHaodong JingHongzong LiXi Lin †thanks: City University of Hong Kong. Email: boxue4-c@my.cityu.edu.hk†thanks: City University of Hong Kong. Email: J.Cheng@my.cityu.edu.hk†thanks: Xi’an Jiaotong University. Email: jinghd@stu.xjtu.edu.cn†thanks: Northwest Polytechnical University. Email: lihongzong@nwpu.edu.cn†thanks: Xi’an Jiaotong University. Email: xi.lin@xjtu.edu.cn Shuang Qiu †thanks: City University of Hong Kong. Email: shuanqiu@cityu.edu.hk October 12, 2026 Abstract 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. 1 Introduction Modern decision systems frequently need to serve many evaluation criteria or user groups with only a handful of deployable choices. This motivates the few-for-many paradigm, which selects a small set of complementary solutions that jointly cover many objectives (Liu et al., 2024; Lin et al., 2025; Liu et al., 2025; Shang et al., 2026). For example, clinical trials may seek a few treatment options that collectively perform well across multiple efficacy and safety outcomes (Kavelaars et al., 2020; Villar et al., 2015); online advertising platforms may use a few campaigns to reach heterogeneous target audiences (Geng et al., 2020; Schwartz et al., 2017); and LLM services may route diverse queries among a limited pool of models with different capabilities and inference costs (Chen et al., 2024; Ong et al., 2025). A key challenge in these applications is that the multi-objective performance of each candidate is unknown and must be learned from noisy observations, such as patient outcomes, user responses to advertisements, or repeated model evaluations. Few-for-many selection thus becomes a statistical identification problem: the learner must find a small representative set whose members jointly serve many objectives, while simultaneously learning their unknown performance. Multi-objective multi-armed bandits offer a natural framework for this setting, associating each arm with an unknown vector-valued mean reward (Drugan and Nowe, 2013; Lattimore and Szepesvári, 2020). In the pure-exploration regime, the goal is to identify the desired representative set with probability at least 1−δ1-δ using as few arm pulls as possible (Audibert and Bubeck, 2010; Garivier and Kaufmann, 2016). Existing multi-objective formulations typically lie at one of two extremes. At one end, Pareto-front identification (Auer et al., 2016; Ararat and Tekin, 2023; Crepon et al., 2024) seeks all nondominated arms; as the number of objectives grows, however, the Pareto set can become large, increasing both the statistical cost of recovering it and the burden of choosing among its members. At the other end, scalarization-based methods (Paria et al., 2020; Lin et al., 2024) collapse multiple objectives into a scalar utility and return a single solution for a given preference, which can be overly restrictive when different objectives favor different arms. These limitations call for an intermediate goal: identifying a few complementary arms that jointly serve many objectives. The closest bandit formulation, multi-objective best-arm identification (MO-BAI), seeks the best arm for every objective (Chen et al., 2025). This target is appropriate when a separate decision can be deployed for each objective, but it can be unnecessarily costly when many objectives must be served under a limited deployment budget. The few-for-many principle instead selects a prescribed number of complementary solutions such that every objective is well served by at least one of them (Lin et al., 2025; Liu et al., 2025). However, existing studies apply this principle to deterministic many-objective optimization, whereas in the bandit setting both the objective-wise ideal values and the quality of any candidate representative set must be inferred from noisy observations. To bridge this gap, we formulate a stochastic counterpart of few-for-many optimization, which we call few-for-many best-arm identification. The quality of a representative set is measured by its worst weighted degradation from the objective-wise ideal values. We consider two forms of prior structure. In the known-group setting, the objectives are partitioned in advance and one arm is selected for each group. In the latent-group setting, only a representative budget L is specified, and the selected arms implicitly induce groups according to which representative best serves each objective. In the latter setting, L=1L=1 recovers a single robust representative, whereas a sufficiently large L recovers objective-wise identification; the intermediate regime 1<L≪M1<L M captures the practically relevant case in which a few deployable arms must jointly serve many objectives. Our main contributions are as follows: • We introduce a few-for-many bandit framework that covers both known and latent objective groups. It bridges MO-BAI (Chen et al., 2025) and few-for-many optimization (Lin et al., 2025), accommodating both noisy observations and a limited representative budget. • We develop two phase-based elimination algorithms, GFM-Elim for known objective groups and AFM-Elim for latent groups, and establish finite-time sample-complexity guarantees for both. Unlike MO-BAI (Chen et al., 2025), our algorithms need not resolve objective-wise distinctions that do not affect the optimal representatives, which can substantially reduce the sampling cost in many-objective settings. • For Gaussian rewards, we establish an information-theoretic lower bound for the latent-group setting that characterizes its fundamental instance-dependent sample complexity. We further show in Appendix C that this lower bound is asymptotically attainable with high probability by an oracle-based Track-and-Stop procedure. • We evaluate the proposed algorithms on synthetic and real-world tasks. The results show that GFM-Elim and AFM-Elim reliably identify compact representative sets while requiring fewer samples than existing multi-objective identification baselines. Related Work. Best-arm identification (BAI) aims to identify the optimal decision using as few samples as possible. Garivier and Kaufmann (2016) established the instance-dependent asymptotic lower bound for classical BAI and introduced Track-and-Stop, which has since been extended to structured pure-exploration problems, including combinatorial answer spaces and multiple correct answers (Chen et al., 2014; Degenne and Koolen, 2019; Jourdan et al., 2021). For vector-valued rewards, multi-objective bandits have been studied under Pareto-based and preference-based criteria (Drugan and Nowe, 2013; Auer et al., 2016; Shukla and Basu, 2024; Xue et al., 2026c; Xue et al., 2026a; Xue et al., 2026b). In particular, Chen et al. (2025) identify the best arm for every objective and develop asymptotically optimal sampling strategies. In parallel, few-for-many optimization seeks a small set of complementary solutions that jointly serve many objectives, as exemplified by the many-objective cover problem (Liu et al., 2024), Tchebycheff set scalarization (Lin et al., 2025), and the general F4M framework (Liu et al., 2025; Shang et al., 2026). These works mainly consider deterministic optimization, where objective evaluations or gradients are directly accessible. Our work connects these two lines of research by studying few-for-many identification with unknown vector-valued means, where only the distinctions that can affect the optimal representatives need to be resolved from noisy sequential observations. A more detailed discussion is provided in Appendix A. 2 Preliminaries For any positive integer n, let [n]=1,…,n[n]=\1,…,n\. For a finite set X, |||X| denotes its cardinality. For any x∈ℝx , let [x]+=maxx,0[x]_+= \x,0\. We use ΔK=w∈ℝ+K:∑a=1Kwa=1 _K=\w _+^K: _a=1^Kw_a=1\ to denote the probability simplex over K arms. We consider a stochastic multi-armed bandit problem with K arms and M objectives. At each time step t, the learner selects an arm at∈[K]a_t∈[K] and observes a vector-valued reward t=(rt,1,…,rt,M)⊤∈ℝM. r_t=(r_t,1,…,r_t,M) ^M. For each arm a∈[K]a∈[K], let a=(μa,1,…,μa,M)⊤ μ_a=( _a,1,…, _a,M) denote its unknown mean reward vector, where μa,m=[rt,m∣ℱt−1,at=a],∀m∈[M], _a,m=E[r_t,m _t-1,a_t=a], ∀ m∈[M], and ℱt−1F_t-1 denotes the history available before time step t. We assume that the reward noise is σ2σ^2-sub-Gaussian; that is, for any s∈ℝs , [exp(s(rt,m−μa,m))|ℱt−1,at=a]≤exp(σ2s22).E [ (s (r_t,m- _a,m ) ) |F_t-1,a_t=a ]≤ ( σ^2s^22 ). (1) The reward coordinates may be statistically dependent, since our finite-time analysis relies only on the marginal concentration property in Eq. (1). For ease of presentation, we assume μa,m∈[0,1] _a,m∈[0,1]. We further assume that each objective has a unique best arm. For every objective m∈[M]m∈[M], we define its ideal value and best arm as μm⋆=maxa∈[K]μa,m,bm⋆=argmaxa∈[K]μa,m. _m = _a∈[K] _a,m, b_m = _a∈[K] _a,m. Few-for-Many Identification. When the number of objectives is large, identifying a separate best arm for every objective may yield many arms, whereas requiring a single arm to perform well on all objectives can be overly restrictive. Motivated by the few-for-many paradigm (Lin et al., 2025), we seek a small number of representative arms that together perform well across many objectives, with each representative serving a group of objectives. We consider two complementary settings, depending on whether the objective groups are known in advance. Known Objective Groups. In the known-group setting, objectives are partitioned in advance, and all objectives in a group share one representative arm. Let 1≤Q≪M1≤ Q M and let =G1,…,GQG=\G_1,…,G_Q\ be a partition of [M][M], i.e., [M]=∪q=1QGq[M]= _q=1^QG_q, where GqG_q contains the objectives in the q-th group. Let λm>0 _m>0 be a known weight for objective m∈[M]m∈[M], which reflects its relative importance. For every group q∈[Q]q∈[Q] and arm a∈[K]a∈[K], we define the group coverage loss as Rq(a)=maxm∈Gqλm(μm⋆−μa,m).R_q(a)= _m∈ G_q _m ( _m - _a,m ). Thus, Rq(a)R_q(a) measures the largest weighted degradation incurred when arm a represents all objectives in GqG_q. Accordingly, the identification target is ⋆=(a1⋆,…,aQ⋆),aq⋆=argmina∈[K]Rq(a). a_G =(a_1 ,…,a_Q ), a_q = _a∈[K]R_q(a). When Q=1Q=1, the problem reduces to identifying a single robust representative for all objectives. When Q=MQ=M and Gq=qG_q=\q\, it reduces to identifying the best arm for every objective. Latent Objective Groups. In the latent-group setting, the objective partition is not known in advance. Instead, the learner is given a representative budget 1≤L≪M1≤ L M and seeks L arms that jointly provide good coverage of all objectives, with the objective groups implicitly induced by the selected representatives. For any nonempty arm set S⊆[K]S [K], we define its overall coverage loss as Φ(S)=maxm∈[M]λm(μm⋆−Vm(S)),Vm(S)=maxa∈Sμa,m. (S)= _m∈[M] _m ( _m -V_m(S) ), V_m(S)= _a∈ S _a,m. Hence, Φ(S) (S) measures the largest weighted degradation incurred when each objective is served by its best arm in S rather than by its best arm in [K][K]. Accordingly, the identification target is SL⋆=argminS∈LΦ(S),L=S⊆[K]:|S|=L.S_L = _S _L (S), _L= \S [K]:|S|=L \. The optimal set SL⋆S_L naturally induces an assignment of objectives to representatives. Specifically, let πL⋆(m)=argmaxa∈SL⋆μa,m _L (m)= _a∈ S_L _a,m. The objectives assigned to the same representative arm then form a latent group: Ga⋆=m∈[M]:πL⋆(m)=a,a∈SL⋆.G_a = \m∈[M]: _L (m)=a \, a∈ S_L . Thus, the objective partition is induced directly by SL⋆S_L rather than identified separately. When L=1L=1, the problem reduces to identifying a single robust representative for all objectives, which coincides with the known-group setting with Q=1Q=1. At the other extreme, once L≥|bm⋆:m∈[M]|L≥|\b_m :m∈[M]\| (in particular, whenever L≥ML≥ M), the representative set can contain all objective-wise best arms and attains zero coverage loss. 3 Finite-Time Elimination Algorithms This section presents finite-time elimination algorithms for the two few-for-many settings: known objective groups and latent objective groups. 3.1 Grouped Few-for-Many Elimination We begin with the known-group setting. Although the objective groups are given, the group coverage losses cannot be evaluated directly because the mean rewards are unknown. To address this, we propose GFM-Elim, a phase-based elimination algorithm that jointly learns the mean rewards and the representative of each group. The complete procedure is summarized in Algorithm 1. At phase r, GFM-Elim maintains benchmark candidate sets ℬm,rB_m,r for the objective-wise ideal values and representative candidate sets q,rC_q,r for the group representatives, all initialized to [K][K]. Let r=q:|q,r|>1Q_r=\q:|C_q,r|>1\ denote the set of unresolved groups and ℳr=∪q∈rGqM_r= _q _rG_q be the associated objectives. The algorithm samples only the arms in r=(∪q∈rq,r)∪(∪m∈ℳrℬm,r),U_r= ( _q _rC_q,r )∪ ( _m _rB_m,r ), so that each observation is shared across all unresolved groups for which the arm remains relevant. Each phase refines the candidates at a finer accuracy than the previous one. Specifically, let ϵr=2−r,δr=6δπ2r2,nr=⌈2σ2ϵr2log(2KMδr)⌉. _r=2^-r, _r= 6δπ^2r^2, n_r= 2σ^2 _r^2 ( 2KM _r ) . (2) This choice of nrn_r ensures that, with probability at least 1−δr1- _r, the empirical means of all arm–objective pairs are simultaneously accurate to within ϵr _r. Each active arm is therefore sampled until it has accumulated nrn_r observations, from which GFM-Elim computes the empirical means μ^a,m(r) μ_a,m^(r). Algorithm 1 GFM-Elim: Grouped Few-for-Many Elimination 1: Confidence level δ, groups =G1,…,GQG=\G_1,…,G_Q\, and weights λmm∈[M]\ _m\_m∈[M] 2: ℬm,1←[K]B_m,1←[K] for all m; q,1←[K]C_q,1←[K] for all q 3: for r=1,2,…r=1,2,… do 4: r←q:|q,r|>1Q_r←\q:|C_q,r|>1\ 5: if r=∅Q_r= then 6: return the unique arms in (q,r)q∈[Q](C_q,r)_q∈[Q] 7: end if 8: ℳr←⋃q∈rGqM_r← _q _rG_q; r←(⋃q∈rq,r)∪(⋃m∈ℳrℬm,r)U_r←( _q _rC_q,r)∪( _m _rB_m,r) 9: Sample every a∈ra _r until it has nrn_r observations and compute μ^a,m(r) μ_a,m^(r) 10: for m∈ℳrm _r do 11: μ^m,r⋆=maxb∈ℬm,rμ^b,m(r) μ_m,r = _b _m,r μ_b,m^(r) 12: ℬm,r+1←a∈ℬm,r:μ^a,m(r)≥μ^m,r⋆−2ϵrB_m,r+1←\a _m,r: μ_a,m^(r)≥ μ_m,r -2 _r\ 13: end for 14: for each q∈rq _r do 15: Compute R¯q,r(a) R_q,r(a) and R¯q,r(a) R_q,r(a) using Eq. (3) 16: q,r+1←a∈q,r:R¯q,r(a)≤minbR¯q,r(b)C_q,r+1←\a _q,r: R_q,r(a)≤ _b R_q,r(b)\ 17: end for 18: Keep all inactive sets unchanged 19: end for GFM-Elim first refines the benchmark candidates. For each active objective m∈ℳrm _r, the empirical benchmark is defined as μ^m,r⋆=maxb∈ℬm,rμ^b,m(r) μ_m,r = _b _m,r μ_b,m^(r). On the confidence event, an arm whose empirical mean falls more than 2ϵr2 _r below this benchmark cannot be the best arm for objective m, and is therefore eliminated, i.e., ℬm,r+1=a∈ℬm,r:μ^a,m(r)≥μ^m,r⋆−2ϵrB_m,r+1=\a _m,r: μ_a,m^(r)≥ μ_m,r -2 _r\. The representative candidates are then updated according to their group coverage losses. Since both the empirical benchmark and the empirical mean of arm a are accurate to within ϵr _r, the coverage loss Rq(a)R_q(a) is bracketed by R¯q,r(a)=maxm∈Gqλm[μ^m,r⋆−μ^a,m(r)−2ϵr]+,R¯q,r(a)=maxm∈Gqλm[μ^m,r⋆−μ^a,m(r)+2ϵr]+. R_q,r(a)= _m∈ G_q _m [ μ_m,r - μ_a,m^(r)-2 _r ]_+,\, R_q,r(a)= _m∈ G_q _m [ μ_m,r - μ_a,m^(r)+2 _r ]_+. (3) An arm is eliminated as a representative candidate once its optimistic loss exceeds the smallest pessimistic loss in its group, i.e., q,r+1=a∈q,r:R¯q,r(a)≤minbR¯q,r(b)C_q,r+1=\a _q,r: R_q,r(a)≤ _b R_q,r(b)\. This procedure continues until every group has a unique representative candidate. We next state its finite-time guarantee, which reflects the arm-dependent stopping behavior described above. To characterize the complexity, we define the group-representative gap and the objective-wise gap as Δq,a=Rq(a)−Rq(aq⋆),gm,a=μm⋆−μa,m. _q,a=R_q(a)-R_q(a_q ), g_m,a= _m - _a,m. For each q∈[Q]q∈[Q], let λ¯q=maxm∈Gqλm λ_q= _m∈ G_q _m and define its identification radius as ρq=mina≠aq⋆Δq,a8λ¯q _q= _a≠ a_q _q,a8 λ_q. The effective gap of arm a is then defined as Γa=minq∈[Q]maxρq,Δq,a8λ¯q,minm∈Gqmaxρq,gm,a4. _a= _q∈[Q] \ \ _q, _q,a8 λ_q \, _m∈ G_q \ _q, g_m,a4 \ \. (4) The two terms in Eq. (4) correspond to the two roles of arm a: the first determines when it can be eliminated as a representative candidate for group q, while the second determines when it is no longer needed to estimate the objective-wise benchmarks within that group. The radius ρq _q reflects the fact that both roles terminate once group q is resolved. Hence, Γa _a captures the hardest role of arm a across all groups and determines the last phase in which it is sampled. Theorem 1 (Instance-dependent sample complexity). With probability at least 1−δ1-δ, Algorithm 1 returns the optimal representative tuple ⋆ a_G using at most TGFM(,δ)T_ GFM( μ,δ) arm pulls, where TGFM(,δ) T_ GFM( μ,δ) =O~(σ2∑a=1K1Γa2logKMδ). = O (σ^2 _a=1^K 1 _a^2 KMδ ). (5) Theorem 1 shows that GFM-Elim is instance-adaptive at the arm level: each arm is sampled only until all of its benchmark and representative roles have been resolved. Consequently, the complexity depends on the hardest remaining role of each arm through Γa _a, rather than accumulating a separate sampling cost for every group. This shared-feedback effect can improve the leading complexity term by a factor of up to Q relative to running an independent elimination procedure for each group. 3.2 Adaptive Few-for-Many Elimination We next turn to the latent-group setting, where no objective partition is available and the learner must identify the optimal representative set directly. We propose AFM-Elim, which lifts the elimination principle of GFM-Elim from individual arms to candidate sets. Importantly, although elimination is performed at the set level, sampling remains at the base-arm level, so that observations are shared across candidate sets. The complete procedure is summarized in Algorithm 2. At phase r, AFM-Elim maintains a benchmark candidate set ℬm,rB_m,r for each objective m∈[M]m∈[M] and a family rC_r of candidate representative sets, initialized as ℬm,1=[K]B_m,1=[K] and 1=LC_1=S_L, respectively. The algorithm samples only the base arms that either belong to an active candidate set or remain relevant for estimating an objective-wise benchmark, i.e., r=(∪S∈rS)∪(∪m=1Mℬm,r).U_r= ( _S _rS )∪ ( _m=1^MB_m,r ). Thus, a single pull of an arm simultaneously refines the estimates of all active candidate sets containing that arm, as well as all objectives for which it remains a benchmark candidate. AFM-Elim uses the same phase schedule in Eq. (2) and the same benchmark-refinement rule as GFM-Elim. The remaining candidate sets are then compared through their empirical coverage losses. For each S∈rS _r, its empirical value on objective m is V^m,r(S)=maxa∈Sμ^a,m(r) V_m,r(S)= _a∈ S μ_a,m^(r). Since both the empirical benchmark μ^m,r⋆ μ_m,r and the empirical set value V^m,r(S) V_m,r(S) are accurate to within ϵr _r on the confidence event, the coverage loss Φ(S) (S) is bracketed by Φ¯r(S)=maxm∈[M]λm[μ^m,r⋆−V^m,r(S)−2ϵr]+,Φ¯r(S)=maxm∈[M]λm[μ^m,r⋆−V^m,r(S)+2ϵr]+. _r(S)= _m∈[M] _m [ μ_m,r - V_m,r(S)-2 _r ]_+, _r(S)= _m∈[M] _m [ μ_m,r - V_m,r(S)+2 _r ]_+. (6) A candidate set is eliminated once its optimistic loss exceeds the pessimistic loss of some other active set, i.e., r+1=S∈r:Φ¯r(S)≤minS′∈rΦ¯r(S′)C_r+1=\S _r: _r(S)≤ _S _r _r(S )\. Algorithm 2 AFM-Elim: Adaptive Few-for-Many Elimination 1: Confidence level δ, representative budget L, and weights λmm∈[M]\ _m\_m∈[M] 2: ℬm,1←[K]B_m,1←[K] for all m; 1←LC_1 _L 3: for r=1,2,…r=1,2,… do 4: if |r|=1|C_r|=1 then 5: return the unique set in rC_r 6: end if 7: r←(⋃S∈rS)∪(⋃m=1Mℬm,r)U_r←( _S _rS)∪( _m=1^MB_m,r) 8: Sample every a∈ra _r until it has nrn_r observations and compute μ^a,m(r) μ_a,m^(r) 9: for m∈[M]m∈[M] do 10: μ^m,r⋆=maxb∈ℬm,rμ^b,m(r) μ_m,r = _b _m,r μ_b,m^(r) 11: ℬm,r+1←a∈ℬm,r:μ^a,m(r)≥μ^m,r⋆−2ϵrB_m,r+1←\a _m,r: μ_a,m^(r)≥ μ_m,r -2 _r\ 12: end for 13: for S∈rS _r do 14: Compute Φ¯r(S) _r(S) and Φ¯r(S) _r(S) using Eq. (6) 15: end for 16: r+1←S∈r:Φ¯r(S)≤minS′∈rΦ¯r(S′)C_r+1←\S _r: _r(S)≤ _S _r _r(S )\ 17: end for This procedure continues until a unique candidate set remains. We next characterize its arm-dependent stopping behavior. For every candidate set S∈LS _L, we define its identification gap and the minimum set-level gap as ΔL(S)=Φ(S)−Φ(SL⋆),ΔL,min=minS∈L∖SL⋆ΔL(S)>0. _L(S)= (S)- (S_L ), _L, = _S _L \S_L \ _L(S)>0. Let λ¯=maxm∈[M]λm λ= _m∈[M] _m and define the set-identification radius as ρL=ΔL,min/(8λ¯) _L= _L, /(8 λ). The effective gap of each base arm a∈[K]a∈[K] is defined as ΓL,a=minmaxρL,minS∈La∈SΔL(S)8λ¯,minm∈[M]maxρL,gm,a4. _L,a= \ \ _L, _ subarraycS _L\\ a∈ S subarray _L(S)8 λ \,\; _m∈[M] \ _L, g_m,a4 \ \. (7) The first term in Eq. (7) determines when all candidate sets containing arm a can be eliminated, whereas the second determines when arm a is no longer needed for benchmark estimation. The truncation at ρL _L reflects the fact that both roles become irrelevant once the optimal representative set has been identified. Hence, ΓL,a _L,a determines the last phase in which arm a is sampled. Theorem 2 (Instance-dependent sample complexity). With probability at least 1−δ1-δ, Algorithm 2 returns the optimal representative set SL⋆S_L using at most TAFM(,δ)T_ AFM( μ,δ) arm pulls, where TAFM(,δ)=O~(σ2∑a=1K1ΓL,a2logKMδ).T_ AFM( μ,δ)= O (σ^2 _a=1^K 1 _L,a^2 KMδ ). (8) Theorem 2 shows that AFM-Elim remains adaptive at the base-arm level even though it operates over a combinatorial family of candidate sets. An arm that appears only in clearly suboptimal candidate sets is discarded early, whereas an arm involved in difficult set comparisons or in benchmark estimation is sampled for longer. Moreover, each base-arm observation is shared across all active candidate sets containing that arm, so no separate sampling cost is incurred for individual sets. The identified representative set can further be used to recover the latent objective groups; a confidence-based assignment procedure and its sample complexity are given in Appendix F.3. Computationally Efficient Relaxation. Exact latent-set identification in AFM-Elim requires optimizing over the combinatorial family L=S⊆[K]:|S|=LS_L=\S [K]:|S|=L\, which is computationally intractable in general. To obtain a polynomial-time alternative that preserves the worst-objective coverage criterion, we consider a bicriteria relaxation that allows O(LlogM)O(L M) representative arms. Specifically, with probability at least 1−δ1-δ, the relaxed procedure returns a set S S satisfying Φ(S^)≤Φ(SL⋆)+ϵ,|S^|≤⌈HML⌉,HM=∑j=1M1j≤1+logM. ( S)≤ (S_L )+ε, | S|≤ H_ML , H_M= _j=1^M 1j≤ 1+ M. The key to computational efficiency is that, at any fixed loss threshold, feasibility reduces to a set-cover problem over the objectives. Here, a loss threshold specifies the largest weighted degradation from the objective-wise ideal value that we are willing to tolerate on each objective, and an arm covers exactly those objectives whose weighted degradation does not exceed the threshold. Building on this observation, we propose BiAFM-Greedy, which first estimates the reward matrix by uniform sampling, then scans candidate thresholds in increasing order and applies the greedy set-cover rule at each one. It returns the first cover that satisfies the relaxed budget, thereby avoiding enumeration of all size-L candidate sets. Compared with AFM-Elim, this procedure forgoes exact size-L identification and instance-adaptive sampling, but in return offers a polynomial-time bicriteria guarantee: with high probability, its coverage loss is within ϵε of the optimal size-L loss while using at most O(LlogM)O(L M) arms. The formal procedure and its theoretical guarantee are given in Appendix B. 4 Information-Theoretic Lower Bound The preceding algorithms come with explicit finite-time guarantees, but these guarantees do not characterize the fundamental difficulty. In this section, we establish an information-theoretic lower bound on the sample complexity of identifying the optimal representative set SL⋆S_L . We consider Gaussian rewards, where each pull of arm a∈[K]a∈[K] yields an independent observation t∼(a,σ2M) r_t ( μ_a,σ^2I_M). The Kullback–Leibler (KL) divergence between the reward distributions with mean vectors a μ_a and a ν_a is d(a,a)=‖a−a‖222σ2.d( μ_a, ν_a)= \| μ_a- ν_a\|_2^22σ^2. Let =(1,…,K) μ=( μ_1,…, μ_K) denote a bandit instance, and let SL⋆()S_L ( μ) denote its optimal representative set, which we assume to be unique. For a fixed instance μ, the set of alternative instances is AltL()=:SL⋆()≠SL⋆().Alt_L( μ)= \ ν:S_L ( ν)≠ S_L ( μ) \. (9) Each ∈AltL() ν _L( μ) induces a different optimal representative set and must therefore be distinguished from μ by any correct identification algorithm. The corresponding characteristic time is defined by (TL⋆())−1=sup∈ΔKinf∈AltL()∑a=1Kwad(a,a). (T_L ( μ) )^-1= _ w∈ _K _ ν _L( μ) _a=1^Kw_ad( μ_a, ν_a). (10) Here, the outer optimization determines the asymptotic sampling proportions, while the inner optimization selects the hardest alternative under the chosen allocation. Theorem 3 (Information-theoretic lower bound). Let δ∈(0,1/2)δ∈(0,1/2). Any fixed-confidence algorithm that identifies the optimal representative set with probability at least 1−δ1-δ on every Gaussian instance with a unique optimal representative set satisfies [τ]≥TL⋆()KL(1−δ,δ),E_ μ[τ]≥ T_L ( μ)KL(1-δ,δ), (11) where KL(⋅,⋅)KL(·,·) denotes the binary relative entropy. Consequently, lim infδ↓0[τ]log(1/δ)≥TL⋆(). _δ 0 E_ μ[τ] (1/δ)≥ T_L ( μ). (12) Theorem 3 shows that any δ-PAC algorithm requires, in expectation, at least order log(1/δ) (1/δ) samples, with TL⋆()T_L ( μ) quantifying the intrinsic difficulty of the instance. The max–min form in Eq. (10) admits the standard fixed-confidence interpretation: the learner chooses asymptotic sampling proportions w, and the inner optimization selects the hardest alternative instance that changes the optimal representative set. The resulting weighted KL divergence gives the maximal information rate, whose inverse is the leading constant of the asymptotic sample complexity. Unlike in objective-wise MO-BAI (Chen et al., 2025), the lower bound only requires distinguishing alternatives that change SL⋆S_L ; objective-wise near-ties are therefore irrelevant unless they alter the optimal representative set. An oracle-based Track-and-Stop algorithm that asymptotically attains this bound with high probability is presented in Appendix C. 5 Experiments In this section, we evaluate the proposed few-for-many identification framework from both statistical and practical perspectives. We first examine whether it improves sample efficiency by avoiding unnecessary objective-wise distinctions and by sharing vector-valued observations across objectives. We then assess its practical effectiveness on a real-world task. Synthetic setup. All synthetic experiments use Gaussian rewards with σ=1σ=1 and 100 independent trials, with random seeds shared across methods. We report the mean number of arm pulls with 95%95\% confidence intervals, and set δ=0.05δ=0.05 unless otherwise specified. We compare against three types of baselines: uniform-sampling variants of our algorithms; Independent-GFM, which solves each group separately with confidence level δ/Qδ/Q; and the two-stage MOBAI+GFM/AFM, which first identifies the objective-wise best arms using the method of Chen et al. (2025) and then performs few-for-many identification. The two stages split the confidence budget equally, and the second stage reuses the first-stage samples. For Figure 1, the known-group instance has Q=4Q=4 groups with four objectives each, so M=16M=16; the latent-group instance has M=9M=9 objectives generated from three planted blocks of size three and uses the representative budget L=3L=3, but the partition is not revealed to the algorithm. These instances are constructed so that objective-wise identification becomes harder as ξ decreases, while the optimal representatives remain unchanged. Each group or planted block has a common representative with mean 0.80.8, each objective has a specialist with mean 11 and a near-specialist with mean 1−ξ1-ξ, and the remaining arms are dominated with mean 0.050.05. Decreasing ξ therefore isolates distinctions that are difficult for MO-BAI but irrelevant to few-for-many identification. To evaluate the benefit of sharing vector observations across groups, we further use a two-arm construction with M=QM=Q singleton groups and vary Q∈1,2,4,8,16,32Q∈\1,2,4,8,16,32\. (a) Known groups (b) Latent groups 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/ξ21/ξ^2. Synthetic results. All methods identify the correct representatives in every run. In Figure 1, the two-stage MO-BAI baselines require substantially more samples as ξ decreases, because distinguishing each specialist from its near-specialist becomes increasingly difficult. In contrast, GFM-Elim and AFM-Elim are nearly insensitive to ξ, since these near-ties do not affect the optimal representatives. This illustrates the advantage of targeting the few-for-many solution directly and avoiding unnecessary objective-wise distinctions. Figure 1 also highlights the benefit of adaptive elimination: unlike the uniform variants, which keep sampling all arms, the proposed methods discard arms once they become irrelevant to benchmark or representative identification, and consistently require fewer samples. Figures 2(a)–(b) further demonstrate the benefit of shared vector feedback. Because a single pull reveals all objective coordinates, GFM-Elim reuses the same observations across groups, whereas Independent-GFM solves each group separately. As a result, the relative gain grows approximately linearly in Q and reaches about 32×32× at Q=32Q=32, consistent with our analysis. (a) Sample cost (b) Sharing gain (c) Adult, L=2L=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=Qy=Q. (c) Sample cost on the Adult model-portfolio task; all methods identify the same optimal pair in every trial. Real-world setup. We evaluate the proposed methods on the Adult dataset (Kohavi, 1996). We construct 12 arms by combining three classifiers (logistic regression, random forest, and histogram gradient boosting) and four decision thresholds in 0.35,0.45,0.55,0.65\0.35,0.45,0.55,0.65\. The 15 objectives are test accuracies on demographic subgroups defined by sex, age, race, and sex–age combinations, after excluding two subgroups whose best arms are tied. Each pull returns subgroup-level correctness indicators, which are sub-Gaussian with σ=1/2σ=1/2. We set L=2L=2, for which the optimal representative set consists of the two histogram-gradient-boosting models with thresholds 0.450.45 and 0.550.55. We run 100 independent trials and compare AFM-Elim with Uniform-AFM and MOBAI+AFM, using the same MO-BAI implementation as in the synthetic experiments. Real-world results. As shown in Figure 2(c), all methods identify the optimal two-model portfolio in every trial, but their sampling costs differ substantially. Uniform-AFM samples every model throughout the elimination process and thus cannot exploit the fact that several classifiers are quickly revealed to be irrelevant to the best size-two portfolio. AFM-Elim eliminates such arms and candidate sets earlier, reducing the cost by roughly a factor of two. The MO-BAI-based baseline is even more expensive, because its first stage attempts to identify the best model for every subgroup before solving the portfolio problem. On Adult, several subgroup accuracies are close across neighboring thresholds, so resolving every subgroup-wise winner requires many additional samples. The few-for-many objective, in contrast, only needs to determine which pair jointly covers the subgroups well, and can therefore stop without resolving all objective-wise winners. Consequently, AFM-Elim uses only about one third of the pulls of MOBAI+AFM. Overall, the real-world experiment supports the same conclusion as the synthetic study: directly targeting the deployable representative set can be much cheaper than solving the stronger objective-wise identification problem. Appendix D provides further empirical results, including confidence calibration, objective scaling, representative-gap sensitivity, and a computational study of the bicriteria approximation algorithm. 6 Conclusion and Future Work We formulated few-for-many best-arm identification as a fixed-confidence problem whose goal is to find a small set of arms such that every objective is well served by at least one selected arm. We considered two settings: known objective groups, where one representative is identified for each group, and latent objective groups, where a budgeted representative set is selected without a predefined partition. For these settings, we developed GFM-Elim and AFM-Elim, which exploit vector-valued feedback and eliminate arms as soon as they become irrelevant to the final decision. We established instance-dependent sample-complexity guarantees for both algorithms and an information-theoretic lower bound for the latent-group setting, and further showed that this lower bound is asymptotically attainable with high probability by an oracle-based Track-and-Stop procedure. Our experiments demonstrate that directly targeting the few-for-many solution can substantially reduce the sample complexity by sharing observations and avoiding unnecessary objective-wise distinctions. An important direction for future work is to better reconcile statistical efficiency with computational scalability in the latent-group setting, where exact identification involves combinatorial optimization. It would also be of interest to extend the framework beyond the current setting, for example, to adaptive selection of the representative budget and to partial feedback. Appendix Appendix A Extended Related Work In this section, we review three lines of research most relevant to our work: fixed-confidence best-arm identification, multi-objective bandits, and few-for-many optimization. Fixed-confidence best-arm identification. Fixed-confidence best-arm identification (BAI) seeks to identify the optimal arm with a prescribed confidence level while minimizing the number of samples (Audibert and Bubeck, 2010; Gabillon et al., 2012). A major line of work studies its instance-dependent sample complexity and develops sampling strategies that attain the corresponding information-theoretic limits. In the classical setting, Garivier and Kaufmann (2016) established an asymptotically tight lower bound and proposed Track-and-Stop, which adaptively tracks the optimal sampling proportions. This framework has since been extended to more structured pure-exploration problems, including combinatorial identification (Chen et al., 2014; Chen et al., 2016; Jourdan et al., 2021), identification with multiple correct answers (Degenne and Koolen, 2019), and linear and transductive bandits (Fiez et al., 2019; Degenne et al., 2020; Jedra and Proutiere, 2020). These studies show that the structure of the answer space and of the feedback model plays a central role in determining both the optimal sampling allocation and the resulting sample complexity. Multi-objective bandits. Multi-objective bandits extend classical bandit models to vector-valued rewards and have been studied extensively in both online decision making and pure exploration (Drugan and Nowe, 2013). In the online setting, one line of work targets Pareto-efficient decisions without imposing an explicit scalar preference, including contextual Pareto regret (Turgay et al., 2018), Pareto regret under stochastic and adversarial feedback (Xu and Klabjan, 2023), and Pareto-regret minimization in linear contextual bandits (Park et al., 2025). Another line incorporates user preferences through scalarizations or structured orderings. Representative examples include nonlinear scalarizations for exploring the Pareto front with hypervolume guarantees (Zhang, 2024), as well as lexicographic and Pareto–lexicographic bandits that optimize objectives according to prescribed priority structures (Xue et al., 2024; Cheng et al., 2024). Recent extensions study cost-aware multi-objective evaluation (Xue et al., 2026c), lexicographic generalized low-rank matrix bandits (Xue et al., 2026a), safe multi-objective linear bandits under hierarchical preferences (Xue et al., 2026b), and multi-objective reinforcement learning with bandit feedback (Qiu et al., 2024). In pure exploration, most existing work focuses on identifying the Pareto-optimal set under fixed-budget or fixed-confidence criteria (Auer et al., 2016; Ararat and Tekin, 2023; Kone et al., 2023; Crepon et al., 2024). More recent studies incorporate preference information through ordering cones, which induce partial orders over vector-valued rewards and encode structured trade-offs among objectives (Shukla and Basu, 2024; Das et al., 2025). Most closely related to our work, Chen et al. (2025) study fixed-confidence multi-objective best-arm identification, in which the learner identifies the best arm for each objective, and characterize asymptotically optimal sampling. In contrast, few-for-many identification seeks only a small set of representative arms that collectively serve all objectives. Consequently, it need not recover the entire Pareto set or resolve every objective-wise best arm, but only those distinctions that can affect the optimal representatives. Few-for-many optimization. The few-for-many paradigm has emerged as an alternative to approximating a large Pareto set when only a small number of solutions can ultimately be deployed. Liu et al. (2024) formulate the many-objective cover problem (MaCP), which selects k≪Mk M solutions such that each objective is well served by at least one of them, and propose a clustering-based method for the resulting NP-hard problem. Building on this idea, Lin et al. (2025) introduce Tchebycheff set scalarization, which evaluates a set through its worst objective-wise performance, together with a smooth variant amenable to gradient-based optimization. Liu et al. (2025) further develop a conditional set-optimization framework that supports different scalarizations and both continuous and discrete many-objective problems. Subsequent studies improve the computational efficiency of few-for-many optimization (Shang et al., 2026) and extend the paradigm to personalized federated learning, where a small collection of shared models is optimized to serve heterogeneous clients (Guo et al., 2026). These works primarily address deterministic optimization, where objective evaluations or optimization feedback are directly available. In contrast, we study few-for-many identification under statistical uncertainty, where the vector-valued means of the candidate arms are unknown and must be inferred from noisy sequential observations. Appendix B Polynomial-Time Bicriteria Approximate Identification Algorithm 3 GreedyCover 1: Coverage sets Caa∈[K]\C_a\_a∈[K] and universe [M][M] 2: S←∅S← , ←[M]U←[M], and ←[K]A←[K] 3: while ≠∅U≠ do 4: Choose a′∈argmaxa∈|Ca∩|a ∈ _a |C_a | 5: if |Ca′∩|=0|C_a |=0 then 6: return Fail 7: end if 8: S←S∪a′S← S∪\a \, ←∖Ca′U C_a , and ←∖a′A \a \ 9: end while 10: return S Algorithm 4 BiAFM-Greedy: Bicriteria Approximate Few-for-Many Identification 1: Accuracy ϵ>0ε>0, confidence δ∈(0,1)δ∈(0,1), budget L, and weights λmm∈[M]\ _m\_m∈[M] 2: λ¯←maxm∈[M]λm λ← _m∈[M] _m and n←⌈32σ2λ¯2ϵ2log(2KMδ)⌉n← 32σ^2 λ^2ε^2 ( 2KMδ ) 3: Pull every arm n times and compute μ^a,m μ_a,m for all a,ma,m 4: μ^m⋆←maxa∈[K]μ^a,m μ_m ← _a∈[K] μ_a,m for every m∈[M]m∈[M] 5: d^a,m←λm(μ^m⋆−μ^a,m) d_a,m← _m( μ_m - μ_a,m) for all a,ma,m 6: ^←d^a,m:a∈[K],m∈[M] T←\ d_a,m:a∈[K],m∈[M]\, sorted increasingly after removing duplicates 7: BL←minK,⌈HML⌉B_L← \K, H_ML \ 8: for each γ∈^γ∈ T in increasing order do 9: C^a(γ)←m∈[M]:d^a,m≤γ C_a(γ)←\m∈[M]: d_a,m≤γ\ for every a∈[K]a∈[K] 10: Sγ←GreedyCover(C^a(γ)a∈[K],[M])S_γ← GreedyCover(\ C_a(γ)\_a∈[K],[M]) 11: if Sγ≠FailS_γ≠ Fail and |Sγ|≤BL|S_γ|≤ B_L then 12: return S^←Sγ S← S_γ 13: end if 14: end for The exact AFM-Elim algorithm identifies SL⋆S_L with an instance-dependent sample complexity, but it maintains a combinatorial family of candidate sets. This section presents BiAFM-Greedy, a complementary polynomial-time procedure. The price of computational tractability is a bicriteria relaxation: the returned set may contain O(LlogM)O(L M) arms, while its coverage loss remains within ϵε of the optimal size-L loss. The key observation is that, for a fixed target loss, the latent few-for-many problem reduces to a set-cover problem over the objectives. For each arm a∈[K]a∈[K] and objective m∈[M]m∈[M], define the weighted deficit da,m=λm(μm⋆−μa,m)d_a,m= _m( _m - _a,m). The latent-set loss can then be written as Φ(S)=maxm∈[M]mina∈Sda,m. (S)= _m∈[M] _a∈ Sd_a,m. For any threshold γ≥0γ≥ 0, define the set of objectives covered by arm a as Ca(γ)=m∈[M]:da,m≤γ.C_a(γ)=\m∈[M]:d_a,m≤γ\. It follows that Φ(S)≤γ⟺⋃a∈SCa(γ)=[M]. (S)≤γ _a∈ SC_a(γ)=[M]. Hence, for a fixed threshold γ, finding a minimum-cardinality representative set with loss at most γ is equivalent to finding a minimum set cover of the objectives. We therefore use the standard greedy set-cover procedure in Algorithm 3. Starting with all objectives uncovered, it repeatedly selects the arm that covers the largest number of currently uncovered objectives. Whenever a feasible cover exists, the classical greedy guarantee gives |Sgreedy|≤HMOPTSC,HM=∑j=1M1j≤1+logM,|S_ greedy|≤ H_M\,OPT_ SC, H_M= _j=1^M 1j≤ 1+ M, where OPTSCOPT_ SC denotes the minimum cover size. The complete BiAFM-Greedy procedure is summarized in Algorithm 4. It first samples all arms uniformly to estimate the unknown means, and then computes the corresponding empirical ideal values and weighted deficits. Instead of enumerating the candidate family LS_L, the algorithm uses the distinct empirical deficits as candidate thresholds. For each threshold, it constructs the induced empirical coverage sets and applies GreedyCover; the first threshold whose greedy cover satisfies the relaxed budget BL=minK,⌈HML⌉B_L= \K, H_ML \ determines the returned set. Algorithm 4 thus examines at most KMKM thresholds and never enumerates the (KL) KL candidate sets. Theorem 4 (Polynomial-time bicriteria identification). Suppose that the reward noise is σ2σ^2-sub-Gaussian, and let λ¯=maxm∈[M]λm λ= _m∈[M] _m. For any ϵ>0ε>0 and δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, Algorithm 4 returns a set S S such that |S^|≤minK,⌈HML⌉,Φ(S^)≤Φ(SL⋆)+ϵ,| S|≤ \K, H_ML \, ( S)≤ (S_L )+ε, where HM=∑j=1M1/j≤1+logMH_M= _j=1^M1/j≤ 1+ M. The total number of arm pulls satisfies TBiAFM≤K⌈32σ2λ¯2ϵ2log(2KMδ)⌉.T_ BiAFM≤ K 32σ^2 λ^2ε^2 ( 2KMδ ) . (13) Moreover, the computational complexity of the algorithm is polynomial in K, M, L, 1/ϵ1/ε, and log(1/δ) (1/δ). Theorem 4 provides a finite-time bicriteria guarantee for the polynomial-time relaxation. Ignoring integer rounding, it is an (HM,ϵ,δ)(H_M,ε,δ)-PAC result: with probability at least 1−δ1-δ, the algorithm returns a set whose loss is within ϵε of that of the best size-L representative set, at the cost of a multiplicative relaxation of at most HM≤1+logMH_M≤ 1+ M in set size. Thus, BiAFM-Greedy complements AFM-Elim by trading exact cardinality for polynomial-time computation. Appendix C Oracle-Based Track-and-Stop This section presents AFM-TaS, an oracle-based, asymptotically optimal counterpart of AFM-Elim. Rather than providing a practical finite-time procedure, its purpose is to show that, under Gaussian rewards and given the required optimization oracles, the information-theoretic lower bound in Theorem 3 is asymptotically attainable with high probability. Following the Track-and-Stop framework (Garivier and Kaufmann, 2016; Chen et al., 2025), AFM-TaS repeatedly estimates the optimal representative set, tracks the corresponding optimal sampling allocation, and stops once sufficient evidence separates the current answer from all alternatives. The optimal sampling proportions are characterized by the max–min problem in Eq. (10). For an instance μ, define L⋆()=argmax∈ΔKinf∈AltL()∑a=1Kwad(a,a).W_L ( μ)= _ w∈ _K _ ν _L( μ) _a=1^Kw_ad( μ_a, ν_a). At round t, let ^(t) μ(t) denote the empirical mean instance. The current empirical answer is S^t∈argminS∈LΦ^(t)(S), S_t∈ _S _L _ μ(t)(S), (14) and the statistical evidence in its favor is quantified by the generalized likelihood-ratio (GLR) statistic ZL(t)=inf:SL⋆()≠S^t∑a=1KNa(t)d(^a(t),a).Z_L(t)= _ ν:\,S_L ( ν)≠ S_t _a=1^KN_a(t)d ( μ_a(t), ν_a ). (15) Thus, ZL(t)Z_L(t) measures the minimum accumulated evidence needed to move from the empirical instance to an alternative under which S^t S_t is no longer optimal. We instantiate the stopping threshold as β(t,δ)=log(π2t2|L|6δ),β(t,δ)= ( π^2t^2|S_L|6δ ), where the factor |L||S_L| accounts for the finite answer space. By the standard GLR maximal inequality and a union bound over the candidate answers and over time (using ∑t≥16/(π2t2)=1 _t≥ 16/(π^2t^2)=1), this threshold satisfies ℙ(∃t≥1:S^t≠SL⋆(),ZL(t)≥β(t,δ))≤δ,P_ μ (∃ t≥ 1: S_t≠ S_L ( μ),\;Z_L(t)≥β(t,δ) )≤δ, (16) and, for fixed problem dimensions, β(t,δ)=log1δ+o(log1δ)β(t,δ)= 1δ+o ( 1δ ) (17) uniformly over t=O(log(1/δ))t=O( (1/δ)). AFM-TaS first samples every arm once. At each subsequent round, it stops and returns S^t S_t if ZL(t)≥β(t,δ)Z_L(t)≥β(t,δ). Otherwise, it computes an allocation in L⋆(^(t))W_L ( μ(t)) and tracks it while enforcing sufficient exploration of every arm. This tracking rule drives the empirical sampling proportions toward the information-theoretically optimal allocation while ensuring consistent estimation of the underlying instance. Algorithm 5 AFM-TaS: Oracle-Based Adaptive Few-for-Many Track-and-Stop 1: Confidence level δ and representative budget L 2: Pull every arm once 3: for t=K,K+1,…t=K,K+1,… do 4: Compute S^t S_t and ZL(t)Z_L(t) using Eqs. (14)–(15) 5: if ZL(t)≥β(t,δ)Z_L(t)≥β(t,δ) then 6: return S^t S_t 7: end if 8: Compute t∈L⋆(^(t)) w_t _L ( μ(t) ) 9: if mina∈[K]Na(t)<t−K/2 _a∈[K]N_a(t)< t-K/2 then 10: Pull an arm with the smallest number of observations 11: else 12: Pull At+1∈argmina∈[K][Na(t)−∑s=Ktws,a]A_t+1∈ _a∈[K] [N_a(t)- _s=K^tw_s,a ] 13: end if 14: end for Theorem 5 (Oracle-based asymptotic upper bound). Suppose that the rewards are Gaussian and TL⋆()<∞T_L ( μ)<∞, and that the allocation oracle in Step 7 is exact. Then Algorithm 5 is δ-PAC and, for every η>0η>0, satisfies limδ↓0ℙ(τδ≤(1+η)TL⋆()log1δ)=1. _δ 0P_ μ ( _δ≤(1+η)T_L ( μ) 1δ )=1. (18) Thus, Algorithm 5 attains the characteristic time TL⋆()T_L ( μ) with asymptotically high probability. Theorem 5 shows that the oracle allocation is not merely a heuristic for focusing samples: with asymptotically high probability, the stopping time of AFM-TaS matches the characteristic time TL⋆()T_L ( μ) appearing in the lower bound of Theorem 3. By contrast, AFM-Elim trades this asymptotic optimality for a simpler elimination rule and an explicit non-asymptotic guarantee. The two algorithms therefore play different roles: AFM-Elim is the implementable finite-time procedure, whereas AFM-TaS certifies the information-theoretic benchmark. Appendix D Additional Experiments This appendix provides additional experiments that complement the main results in Section 5. We first examine confidence calibration, scaling with the number of objectives, and sensitivity to the gaps that directly determine the few-for-many answer. We then study the computational behavior of the polynomial-time bicriteria algorithm in Appendix B. We do not include AFM-TaS, since it is an oracle-based construction that requires solving the characteristic-time allocation problem exactly and repeatedly computing GLR stopping statistics against all alternative representative sets. D.1 Confidence Calibration We first examine whether the empirical error rate is consistent with the prescribed confidence level. We consider one known-group instance and one latent-group instance from the synthetic setting in Section 5, fix ξ=0.1ξ=0.1, and vary δ∈0.2,0.1,0.05,0.02δ∈\0.2,0.1,0.05,0.02\. For each δ, we run 200 independent trials, using GFM-Elim on the known-group instance and AFM-Elim on the latent-group instance. 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. As shown in Figure 3, both algorithms return the correct answer in all trials at every tested confidence level, which is consistent with the conservative finite-time confidence allocation used by the elimination procedures. The sample complexity increases only mildly as δ decreases, in line with the logarithmic dependence on 1/δ1/δ in the theoretical bounds. Hence, the algorithms remain reliable across confidence levels, and the sample budget grows gradually as the confidence requirement becomes stricter. D.2 Scaling with the Number of Objectives We next isolate the many-objective effect in the known-group setting. We fix Q=4Q=4 groups and increase the number of objectives per group from 22 to 1616, so that M ranges from 88 to 6464. The optimal representative of each group remains unchanged, while every objective has its own specialist and near-specialist. Consequently, methods that first identify all objective-wise best arms must resolve a growing number of distinctions that are unnecessary for the few-for-many answer. Figure 4: Scaling with the number of objectives in the known-group setting. As shown in Figure 4, GFM-Elim consistently identifies the group representatives using substantially fewer pulls than the two-stage MOBAI+GFM baseline. The gap widens as M grows, because MOBAI+GFM spends many samples resolving objective-wise specialists before solving the grouped problem. GFM-Elim also improves over Independent-GFM by sharing each vector observation across group decisions. Its curve approaches that of Uniform-GFM for larger M, because this experiment adds a specialist and a near-specialist arm for each new objective while keeping the number of easily discarded dominated arms fixed; hence, a growing fraction of arms remains relevant to benchmark estimation. These results confirm the main message of the synthetic study: as the number of objectives grows, directly identifying representatives is more sample-efficient than recovering every objective-wise winner. D.3 Sensitivity to Representative Gaps The main experiment in Figure 1 varies an objective-wise gap that is irrelevant to the answer. Here, we instead vary the gap between the optimal representative and its closest competitor, while keeping the near-specialist gap fixed at ξ=0.1ξ=0.1. This directly changes the difficulty of the few-for-many decision. Figure 5: Sensitivity to the representative gap. Both known-group and latent-group identification become harder as the representative gap shrinks. Figure 5 exhibits the expected quadratic growth in sample complexity as the representative gap decreases. In the known-group case, the average sample complexity of GFM-Elim increases from the order of thousands to the order of hundreds of thousands as the representative gap shrinks from 0.20.2 to 0.0250.025; the latent-group results for AFM-Elim follow the same pattern. This contrasts with Figure 1: the proposed methods are insensitive to gaps that do not change the few-for-many answer, yet correctly spend more samples on gaps that determine the representative decision. Together, the two experiments indicate that the algorithms adapt to the right notion of difficulty. D.4 Computational Scalability of the Bicriteria Algorithm We further evaluate the polynomial-time BiAFM-Greedy algorithm. This experiment focuses on computational efficiency and complements, rather than replaces, the sample-complexity comparisons in Section 5. Unlike AFM-Elim, which maintains the combinatorial candidate family to identify the exact size-L representative set, BiAFM-Greedy uses uniform sampling and returns a representative set under the relaxed budget. We use the latent version of the synthetic family from Section 5, with Q=4Q=4 planted blocks of three objectives each (M=12M=12), L=4L=4, ξ=0.05ξ=0.05, σ=0.1σ=0.1, and δ=0.05δ=0.05. We vary the number of dominated arms, which increases K and hence the number of exact candidate sets |L|=(KL)|S_L|= KL. For BiAFM-Greedy, we use ϵ=0.1ε=0.1, which gives the relaxed budget ⌈H12L⌉=13 H_12L =13. Each configuration is averaged over 30 independent trials with common random seeds. Reported runtimes exclude the post-hoc computation of the true optimum, which is used only for evaluation. 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 LS_L and returns a bicriteria set within the relaxed budget. K Method |L||S_L| Pulls Time (ms) |S^|| S| Φ(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 Table 1 summarizes the statistical–computational trade-off. On this instance, exact AFM-Elim is more sample-efficient: it respects the strict budget L=4L=4 and uses only the samples needed to certify the exact optimal representative set. However, its runtime grows quickly with K, because the candidate family expands from tens of thousands to hundreds of thousands of sets. In contrast, BiAFM-Greedy samples all arms uniformly and therefore uses more pulls, but it never enumerates LS_L, and its runtime stays below one millisecond in all tested configurations. The returned set sizes and coverage losses reflect the bicriteria nature of the guarantee: BiAFM-Greedy returns a larger set, still within the relaxed logarithmic budget, which attains zero true coverage loss in this construction, whereas AFM-Elim returns the best strict size-L set, whose coverage loss is nonzero. 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. Figure 6 visualizes these trends across the four measured quantities. The sample panel shows the price of the uniform exploration in BiAFM-Greedy, while the runtime panel shows the benefit of replacing exact enumeration of candidate sets with a greedy cover computation. The set-size and coverage-loss panels make the approximation trade-off explicit: the bicriteria method returns more arms, and this enlarged set covers all objectives better than the strict size-L optimum on this instance. Hence, BiAFM-Greedy is useful when exact enumeration of candidate sets is the computational bottleneck and a modest relaxation of the budget is acceptable. Appendix E Analysis of the Grouped Method: GFM-Elim E.1 Confidence bounds and correctness For every arm a, objective m, and phase r, let μ^a,m(nr) μ_a,m(n_r) denote the empirical mean of the first nrn_r samples of arm a on objective m. Consider the event ℰ=⋂r=1∞⋂a∈[K]⋂m∈[M]|μ^a,m(nr)−μa,m|≤ϵr.E= _r=1^∞ _a∈[K] _m∈[M] \ | μ_a,m(n_r)- _a,m |≤ _r \. (19) Lemma 1. Under Eq. (1), ℙ(ℰ)≥1−δ.P_ μ(E)≥ 1-δ. Proof. For every fixed r, a, and m, the sub-Gaussian concentration inequality gives ℙ(|μ^a,m(nr)−μa,m|>ϵr)≤2exp(−nrϵr22σ2)≤δrKM.P_ μ ( | μ_a,m(n_r)- _a,m |> _r )≤ 2 (- n_r _r^22σ^2 )≤ _rKM. A union bound over all arms and objectives yields ℙ(∃a∈[K],m∈[M]:|μ^a,m(nr)−μa,m|>ϵr)≤δr.P_ μ (∃ a∈[K],m∈[M]: | μ_a,m(n_r)- _a,m |> _r )≤ _r. Finally, ∑r=1∞δr=6δπ2∑r=1∞1r2=δ, _r=1^∞ _r= 6δπ^2 _r=1^∞ 1r^2=δ, and a union bound over phases completes the proof. ∎ Lemma 2. On the event ℰE, the following statements hold at every phase r. 1. The best arm of every objective remains in the corresponding benchmark set: bm⋆∈ℬm,r,∀m∈[M].b_m _m,r, ∀ m∈[M]. 2. For every unresolved group q and every a∈q,ra _q,r, R¯q,r(a)≤Rq(a)≤R¯q,r(a). R_q,r(a)≤ R_q(a)≤ R_q,r(a). (20) 3. The loss bounds satisfy Rq(a)−4λ¯qϵr≤R¯q,r(a)≤R¯q,r(a)≤Rq(a)+4λ¯qϵr.R_q(a)-4 λ_q _r≤ R_q,r(a)≤ R_q,r(a)≤ R_q(a)+4 λ_q _r. (21) Proof. We first prove the benchmark-set property by induction. Initially, ℬm,1=[K]B_m,1=[K], so the claim holds. Suppose that bm⋆∈ℬm,rb_m _m,r. On ℰE, μ^bm⋆,m(r)≥μm⋆−ϵr,μ^m,r⋆≤μm⋆+ϵr. μ_b_m ,m^(r)≥ _m - _r, μ_m,r ≤ _m + _r. Hence, μ^bm⋆,m(r)≥μ^m,r⋆−2ϵr μ_b_m ,m^(r)≥ μ_m,r -2 _r, and thus bm⋆∈ℬm,r+1b_m _m,r+1. Since bm⋆∈ℬm,rb_m _m,r, the definition of the maximum and the event ℰE imply |μ^m,r⋆−μm⋆|≤ϵr. | μ_m,r - _m |≤ _r. (22) Consequently, for every arm a, |(μ^m,r⋆−μ^a,m(r))−(μm⋆−μa,m)|≤2ϵr. | ( μ_m,r - μ_a,m^(r) )- ( _m - _a,m ) |≤ 2 _r. Since the positive-part operator is nondecreasing and 11-Lipschitz, and μm⋆−μa,m≥0 _m - _a,m≥ 0, subtracting and adding 2ϵr2 _r as in Eq. (3) and taking the weighted maximum over m∈Gqm∈ G_q proves Eq. (20). The same display also yields R¯q,r(a)≥Rq(a)−4λ¯qϵr,R¯q,r(a)≤Rq(a)+4λ¯qϵr, R_q,r(a)≥ R_q(a)-4 λ_q _r, R_q,r(a)≤ R_q(a)+4 λ_q _r, which proves Eq. (21). ∎ Lemma 3 (Elimination correctness). Algorithm 1 satisfies ℙ(τ<∞,^=⋆)≥1−δ.P_ μ (τ<∞, a_G= a_G )≥ 1-δ. More precisely, on the event ℰE: 1. aq⋆a_q is never eliminated from q,rC_q,r; 2. every a≠aq⋆a≠ a_q is eliminated from q,rC_q,r at the first phase r at which ϵr<Δq,a8λ¯q _r< _q,a8 λ_q and a is still active in group q. Proof. Fix a group q. By Lemma 2, R¯q,r(aq⋆)≤Rq(aq⋆). R_q,r(a_q )≤ R_q(a_q ). Moreover, for every b∈q,rb _q,r, R¯q,r(b)≥Rq(b)≥Rq(aq⋆). R_q,r(b)≥ R_q(b)≥ R_q(a_q ). Therefore, R¯q,r(aq⋆)≤minb∈q,rR¯q,r(b), R_q,r(a_q )≤ _b _q,r R_q,r(b), so aq⋆a_q is never eliminated. Now consider an arm a≠aq⋆a≠ a_q . By Eq. (21), R¯q,r(a)≥Rq(a)−4λ¯qϵr R_q,r(a)≥ R_q(a)-4 λ_q _r and, since aq⋆∈q,ra_q _q,r, minb∈q,rR¯q,r(b)≤R¯q,r(aq⋆)≤Rq(aq⋆)+4λ¯qϵr. _b _q,r R_q,r(b)≤ R_q,r(a_q )≤ R_q(a_q )+4 λ_q _r. Hence, R¯q,r(a)−minb∈q,rR¯q,r(b)≥Δq,a−8λ¯qϵr. R_q,r(a)- _b _q,r R_q,r(b)≥ _q,a-8 λ_q _r. If ϵr<Δq,a8λ¯q, _r< _q,a8 λ_q, the right-hand side is strictly positive, and arm a is eliminated. Since all suboptimal group gaps are positive and ϵr→0 _r→ 0, every group eventually contains only aq⋆a_q on ℰE. Combined with ℙ(ℰ)≥1−δP_ μ(E)≥ 1-δ from Lemma 1, this proves the lemma. ∎ E.2 Proof of Theorem 1 Proof. We work on the event ℰE throughout. Fix a group q. By Lemma 3, every suboptimal representative candidate is eliminated once ϵr<Δq,a8λ¯q. _r< _q,a8 λ_q. In particular, all suboptimal candidates are eliminated once ϵr<ρq _r< _q, so group q is resolved no later than the first phase satisfying ϵr<ρq _r< _q. Consider first the representative role of arm a in group q. If a≠aq⋆a≠ a_q , it is eliminated once ϵr<Δq,a8λ¯q. _r< _q,a8 λ_q. If a=aq⋆a=a_q , it remains active until group q is resolved. In both cases, this role has ended by the first phase satisfying ϵr<maxρq,Δq,a8λ¯q. _r< \ _q, _q,a8 λ_q \. Next, consider the benchmark role of arm a for an objective m∈Gqm∈ G_q. If gm,a>4ϵrg_m,a>4 _r, then on ℰE, μ^a,m(r)≤μa,m+ϵr<μm⋆−3ϵr≤μ^m,r⋆−2ϵr, μ_a,m^(r)≤ _a,m+ _r< _m -3 _r≤ μ_m,r -2 _r, so a is eliminated from ℬm,r+1B_m,r+1. Otherwise, the benchmark role still ends once group q is resolved, since m then leaves ℳrM_r. Therefore, this role has ended by the first phase satisfying ϵr<maxρq,gm,a4. _r< \ _q, g_m,a4 \. By Eq. (4), all roles of arm a have ended by the phase ra=minr≥1:ϵr<Γa,r_a= \r≥ 1: _r< _a \, so arm a is pulled at most nran_r_a times. By the minimality of rar_a, ϵra≥Γa2 _r_a≥ _a2 and ra≤1+⌈log21Γa⌉.r_a≤ 1+ _2 1 _a . Using Eq. (2), nra n_r_a ≤1+2σ2ϵra2log(π2KMra23δ) ≤ 1+ 2σ^2 _r_a^2 ( π^2KMr_a^23δ ) ≤1+8σ2Γa2log(π2KM3δ(1+⌈log21Γa⌉)2). ≤ 1+ 8σ^2 _a^2 ( π^2KM3δ (1+ _2 1 _a )^2 ). Consequently, on ℰE, the total number of pulls is at most ∑a=1K[1+8σ2Γa2log(π2KM3δ(1+⌈log21Γa⌉)2)], _a=1^K [1+ 8σ^2 _a^2 ( π^2KM3δ (1+ _2 1 _a )^2 ) ], which is of the order stated in Eq. (5). Since ℙ(ℰ)≥1−δP_ μ(E)≥ 1-δ by Lemma 1, the high-probability guarantee follows. ∎ Appendix F Analysis of the Adaptive Method: AFM-Elim F.1 Set-level confidence bounds and correctness Let ℰE be the simultaneous confidence event defined in Eq. (19). We first show that the loss bounds in Eq. (6) are valid uniformly over all candidate sets. Importantly, this result does not require a union bound over the (KL) KL candidate sets. Lemma 4 (Set-level confidence bounds). On the event ℰE, the following statements hold at every phase r. 1. The best arm of every objective remains in its benchmark set: bm⋆∈ℬm,r,∀m∈[M].b_m _m,r, ∀ m∈[M]. 2. For every S∈rS _r and m∈[M]m∈[M], the empirical objective-wise value satisfies |V^m,r(S)−Vm(S)|≤ϵr. | V_m,r(S)-V_m(S) |≤ _r. (23) 3. For every S∈rS _r, Φ¯r(S)≤Φ(S)≤Φ¯r(S). _r(S)≤ (S)≤ _r(S). (24) 4. The set-level loss bounds satisfy Φ(S)−4λ¯ϵr≤Φ¯r(S)≤Φ¯r(S)≤Φ(S)+4λ¯ϵr. (S)-4 λ _r≤ _r(S)≤ _r(S)≤ (S)+4 λ _r. (25) Proof. The benchmark-set statement follows from the same induction argument as in Lemma 2, so bm⋆b_m is never removed from ℬm,rB_m,r. On ℰE, the nonexpansiveness of the maximum operator gives |V^m,r(S)−Vm(S)|≤maxa∈S|μ^a,m(r)−μa,m|≤ϵr, | V_m,r(S)-V_m(S) |≤ _a∈ S | μ_a,m^(r)- _a,m |≤ _r, which proves Eq. (23). Because the best arm remains in ℬm,rB_m,r, Eq. (22) also holds. Therefore, |(μ^m,r⋆−V^m,r(S))−(μm⋆−Vm(S))|≤2ϵr. | ( μ_m,r - V_m,r(S) )- ( _m -V_m(S) ) |≤ 2 _r. The monotonicity and 11-Lipschitz continuity of the positive-part operator in Eq. (6) then yield Eq. (24), as well as Φ¯r(S)≥Φ(S)−4λ¯ϵr,Φ¯r(S)≤Φ(S)+4λ¯ϵr, _r(S)≥ (S)-4 λ _r, _r(S)≤ (S)+4 λ _r, which proves Eq. (25). ∎ The set-level confidence event depends only on the KMKM base-arm means. Consequently, the confidence radius scales logarithmically in KMKM rather than in the exponentially large number of candidate sets. Lemma 5 (Set-elimination correctness). Algorithm 2 is δ-PAC. More precisely, on the event ℰE: 1. the optimal representative set SL⋆S_L is never eliminated; 2. every S≠SL⋆S≠ S_L that is still active is eliminated at the first phase satisfying ϵr<ΔL(S)8λ¯. _r< _L(S)8 λ. (26) Therefore, ℙ(τ<∞,S^L=SL⋆)≥1−δ.P_ μ (τ<∞, S_L=S_L )≥ 1-δ. Proof. Let Br=minS′∈rΦ¯r(S′)B_r= _S _r _r(S ) denote the elimination threshold at phase r. By Lemma 4, Φ¯r(SL⋆)≤Φ(SL⋆), _r(S_L )≤ (S_L ), and, for every S∈rS _r, Φ¯r(S)≥Φ(S)≥Φ(SL⋆). _r(S)≥ (S)≥ (S_L ). It follows that Φ¯r(SL⋆)≤Br, _r(S_L )≤ B_r, so SL⋆S_L is never eliminated. Now fix a suboptimal set S≠SL⋆S≠ S_L . By Eq. (25), Φ¯r(S)≥Φ(S)−4λ¯ϵr, _r(S)≥ (S)-4 λ _r, and, since SL⋆∈rS_L _r, Br≤Φ¯r(SL⋆)≤Φ(SL⋆)+4λ¯ϵr.B_r≤ _r(S_L )≤ (S_L )+4 λ _r. Therefore, Φ¯r(S)−Br≥ΔL(S)−8λ¯ϵr. _r(S)-B_r≥ _L(S)-8 λ _r. Whenever Eq. (26) holds, the right-hand side is strictly positive, and hence S is removed from r+1C_r+1. Since ΔL,min>0 _L, >0 and ϵr→0 _r→ 0, every suboptimal candidate set is eventually eliminated on ℰE. Combined with ℙ(ℰ)≥1−δP_ μ(E)≥ 1-δ from Lemma 1, this proves the result. ∎ F.2 Proof of Theorem 2 Proof. We work on the event ℰE throughout. Fix a base arm a, and consider first its role in the active candidate family. If a∉SL⋆a∉ S_L , every candidate set containing a is suboptimal. By Lemma 5, each such set S is eliminated once ϵr<ΔL(S)8λ¯. _r< _L(S)8 λ. Therefore, all candidate sets containing a have been eliminated once ϵr<minS∈La∈SΔL(S)8λ¯. _r< _ subarraycS _L\\ a∈ S subarray _L(S)8 λ. If a∈SL⋆a∈ S_L , then a remains in the union of active candidate sets until the algorithm terminates. Since every suboptimal set is eliminated once ϵr<ρL _r< _L, this role ends once ϵr<ρL. _r< _L. Next, consider the benchmark role of arm a for objective m. If gm,a>4ϵr,g_m,a>4 _r, then, on ℰE, μ^a,m(r)≤μa,m+ϵr<μm⋆−3ϵr≤μ^m,r⋆−2ϵr, μ_a,m^(r)≤ _a,m+ _r< _m -3 _r≤ μ_m,r -2 _r, so a is removed from ℬm,r+1B_m,r+1. Otherwise, this role ends when the algorithm terminates. Hence, the benchmark role has ended by the first phase satisfying ϵr<maxρL,gm,a4. _r< \ _L, g_m,a4 \. By Eq. (7), all roles of arm a have ended by the phase ra=minr≥1:ϵr<ΓL,a,r_a= \r≥ 1: _r< _L,a \, so the arm is pulled at most nran_r_a times. By the minimality of rar_a, ϵra≥ΓL,a2,ra≤1+⌈log21ΓL,a⌉. _r_a≥ _L,a2, r_a≤ 1+ _2 1 _L,a . Substituting these inequalities into the definition of nrn_r gives nra≤1+8σ2ΓL,a2log(π2KM3δ(1+⌈log21ΓL,a⌉)2).n_r_a≤ 1+ 8σ^2 _L,a^2 ( π^2KM3δ (1+ _2 1 _L,a )^2 ). Consequently, on ℰE, the total number of pulls is at most ∑a=1K[1+8σ2ΓL,a2log(π2KM3δ(1+⌈log21ΓL,a⌉)2)], _a=1^K [1+ 8σ^2 _L,a^2 ( π^2KM3δ (1+ _2 1 _L,a )^2 ) ], which is of the order stated in Eq. (8). Since ℙ(ℰ)≥1−δP_ μ(E)≥ 1-δ by Lemma 1, the high-probability guarantee follows. ∎ F.3 Recovery of the latent objective groups Identifying SL⋆S_L does not by itself determine a unique objective partition. To recover a unique assignment, we impose the following condition. Assumption 1. For every objective m∈[M]m∈[M], there exists a unique arm πL⋆(m)∈SL⋆ _L (m)∈ S_L satisfying πL⋆(m)=argmaxa∈SL⋆μa,m. _L (m)= _a∈ S_L _a,m. The latent group represented by a∈SL⋆a∈ S_L is then Ga⋆=m∈[M]:πL⋆(m)=a.G_a = \m∈[M]: _L (m)=a \. (27) When L=1L=1, the assignment is trivial and requires no additional samples. We therefore assume L≥2L≥ 2 below and define the assignment gap ζm=μπL⋆(m),m−maxa∈SL⋆∖πL⋆(m)μa,m, _m= _ _L (m),m- _a∈ S_L \ _L (m)\ _a,m, (28) together with ζmin=minm∈[M]ζm. _ = _m∈[M] _m. After SL⋆S_L has been identified, the learner can continue sampling its L arms until, for every objective m, there exists an arm π^(m)∈SL⋆ π(m)∈ S_L such that μ^π^(m),m(r)−maxa∈SL⋆∖π^(m)μ^a,m(r)>2ϵr. μ_ π(m),m^(r)- _a∈ S_L \ π(m)\ μ_a,m^(r)>2 _r. (29) The output groups are G^a=m∈[M]:π^(m)=a,a∈SL⋆. G_a= \m∈[M]: π(m)=a \, a∈ S_L . Corollary 1 (Latent-group recovery). Suppose that L≥2L≥ 2 and that Assumption 1 holds. On the event ℰE, condition Eq. (29) is satisfied for all objectives once ϵr<ζmin4, _r< _ 4, and the resulting assignments and groups satisfy π^(m)=πL⋆(m),G^a=Ga⋆. π(m)= _L (m), G_a=G_a . The additional sample complexity is at most O~(σ2Lζmin2logKMδ). O ( σ^2L _ ^2 KMδ ). (30) Proof. For every objective m, on ℰE, μ^πL⋆(m),m(r)−maxa∈SL⋆∖πL⋆(m)μ^a,m(r)≥ζm−2ϵr. μ_ _L (m),m^(r)- _a∈ S_L \ _L (m)\ μ_a,m^(r)≥ _m-2 _r. When ϵr<ζmin/4 _r< _ /4, the right-hand side exceeds 2ϵr2 _r, so Eq. (29) holds with π^(m)=πL⋆(m) π(m)= _L (m). Conversely, on ℰE, any arm π^(m) π(m) satisfying Eq. (29) has a true mean strictly larger than those of all other arms in SL⋆S_L , so the certified assignment is correct. At the first phase with ϵr<ζmin/4 _r< _ /4, the same calculation as in the proof of Theorem 1 gives nr=O~(σ2ζmin−2log(KM/δ))n_r= O(σ^2 _ ^-2 (KM/δ)). Sampling the L selected arms to this precision proves Eq. (30). ∎ Appendix G Proof of Theorem 3 Proof. If [τ]=+∞E_ μ[τ]=+∞, the lower bound holds trivially. We therefore assume [τ]<+∞E_ μ[τ]<+∞. Let E=S^L=SL⋆().E= \ S_L=S_L ( μ) \. Since the algorithm is δ-PAC, ℙ(E)≥1−δ.P_ μ(E)≥ 1-δ. For every ∈AltL() ν _L( μ), the set SL⋆()S_L ( μ) is not optimal under ν, and hence ℙ(E)≤δ.P_ ν(E)≤δ. The change-of-measure inequality for adaptive sampling gives ∑a=1K[Na(τ)]d(a,a)≥KL(ℙ(E),ℙ(E))≥KL(1−δ,δ), _a=1^KE_ μ[N_a(τ)]d( μ_a, ν_a) (P_ μ(E),P_ ν(E) ) (1-δ,δ), where the last step uses the monotonicity of KLKL and δ<1/2δ<1/2. Let wa=[Na(τ)][τ].w_a= E_ μ[N_a(τ)]E_ μ[τ]. Then ∈ΔK w∈ _K, and since the previous inequality holds for every alternative, [τ]inf∈AltL()∑a=1Kwad(a,a)≥KL(1−δ,δ).E_ μ[τ] _ ν _L( μ) _a=1^Kw_ad( μ_a, ν_a) (1-δ,δ). By the definition of TL⋆()T_L ( μ), inf∈AltL()∑a=1Kwad(a,a)≤(TL⋆())−1. _ ν _L( μ) _a=1^Kw_ad( μ_a, ν_a)≤ (T_L ( μ) )^-1. Combining the last two inequalities proves Eq. (11). Finally, since KL(1−δ,δ)∼log1δKL(1-δ,δ) 1δ as δ↓0δ 0, Eq. (12) follows. ∎ Appendix H Proof of Theorem 4 Proof. Set η=ϵ/(4λ¯)η=ε/(4 λ) and define ℰBi=|μ^a,m−μa,m|≤η,∀a∈[K],m∈[M].E_ Bi= \| μ_a,m- _a,m|≤η,\ ∀ a∈[K],m∈[M] \. For each arm–objective pair, the sub-Gaussian concentration inequality gives ℙ(|μ^a,m−μa,m|>η)≤2exp(−nη22σ2).P_ μ (| μ_a,m- _a,m|>η )≤ 2 (- nη^22σ^2 ). The prescribed value of n and η2=ϵ2/(16λ¯2)η^2=ε^2/(16 λ^2) imply nη22σ2≥log(2KMδ). nη^22σ^2≥ ( 2KMδ ). Hence, each failure probability is at most δ/(KM)δ/(KM), and a union bound yields ℙ(ℰBi)≥1−δP_ μ(E_ Bi)≥ 1-δ. On ℰBiE_ Bi, the nonexpansiveness of the maximum operator gives, for every m, |μ^m⋆−μm⋆|=|maxaμ^a,m−maxaμa,m|≤maxa|μ^a,m−μa,m|≤η.| μ_m - _m |= | _a μ_a,m- _a _a,m |≤ _a| μ_a,m- _a,m|≤η. Consequently, for every a and m, |d^a,m−da,m|≤λm(|μ^m⋆−μm⋆|+|μ^a,m−μa,m|)≤2λ¯η=ϵ2.| d_a,m-d_a,m|≤ _m (| μ_m - _m |+| μ_a,m- _a,m| )≤ 2 λη= ε2. (31) Define the empirical loss Φ^(S)=maxm∈[M]mina∈Sd^a,m. (S)= _m∈[M] _a∈ S d_a,m. (32) Since both the minimum and the maximum operators are nonexpansive in the sup norm, Eq. (31) implies, simultaneously for every nonempty S⊆[K]S [K], |Φ^(S)−Φ(S)|≤ϵ2.| (S)- (S)|≤ ε2. (33) Let γemp⋆=Φ^(SL⋆) _ emp = (S_L ). For each objective m, some arm in SL⋆S_L has an empirical deficit of at most γemp⋆ _ emp , so the L arms in SL⋆S_L cover [M][M] at this threshold. Thus, OPTSC(γemp⋆)≤L,|Sγemp⋆|≤HML.OPT_ SC( _ emp )≤ L, |S_ _ emp |≤ H_ML. (34) Moreover, because both extrema in Eq. (32) are taken over finite sets, there exist m′∈[M]m ∈[M] and a′∈SL⋆a ∈ S_L such that γemp⋆=d^a′,m′ _ emp = d_a ,m ; hence γemp⋆∈ _ emp ∈ T. Algorithm 4 scans the thresholds in increasing order, and Eq. (34), together with the fact that a greedy cover uses at most K distinct arms, shows that the acceptance test is passed no later than at γemp⋆ _ emp . The returned threshold γ γ therefore satisfies γ^≤γemp⋆ γ≤ _ emp . Because S S covers every objective at threshold γ γ, we have Φ^(S^)≤γ ( S)≤ γ. Combining this with Eq. (33) gives Φ(S^) ( S) ≤Φ^(S^)+ϵ2≤γ^+ϵ2≤Φ^(SL⋆)+ϵ2≤Φ(SL⋆)+ϵ. ≤ ( S)+ ε2≤ γ+ ε2≤ (S_L )+ ε2≤ (S_L )+ε. The budget bound follows directly from the acceptance test, and the preceding argument holds on an event of probability at least 1−δ1-δ. The algorithm uses exactly KnKn arm pulls, which gives Eq. (13). There are at most KMKM distinct thresholds. Under a direct implementation, computing the empirical means costs O(KMn)O(KMn) scalar operations, sorting the thresholds costs O(KMlog(KM))O(KM (KM)), and constructing all coverage sets and running the greedy cover at every threshold costs at most O(K3M2)O(K^3M^2). Hence, the overall computation is polynomial in the stated parameters. ∎ Appendix I Proof of Theorem 5 Proof. The δ-PAC property follows directly from Eq. (16): an incorrect recommendation can occur only if, for some t, S^t≠SL⋆()andZL(t)≥β(t,δ), S_t≠ S_L ( μ) Z_L(t)≥β(t,δ), and this event has probability at most δ. Forced exploration guarantees that Na(t)⟶∞,∀a∈[K].N_a(t) ∞, ∀ a∈[K]. Therefore, by the strong law of large numbers, ^a(t)⟶aalmost surely. μ_a(t) μ_a surely. Since ΔL,min>0 _L, >0, the empirical optimal set eventually coincides with the true optimal set, i.e., S^t=SL⋆ S_t=S_L for all sufficiently large t, almost surely. For ∈ΔK w∈ _K and an instance θ, define the information rate IL(,)=inf∈AltL()∑a=1Kwad(a,a).I_L( w, θ)= _ ν _L( θ) _a=1^Kw_ad( θ_a, ν_a). Let (t)=(t)/t w(t)=N(t)/t. Once the empirical answer has stabilized, Eq. (15) gives ZL(t)t=IL((t),^(t)). Z_L(t)t=I_L ( w(t), μ(t) ). The exact allocation oracle and the tracking step of Algorithm 5 constitute precisely the Track-and-Stop tracking rule applied to the latent answer space. The standard tracking argument therefore implies that, along the realized trajectory, the empirical sampling proportions approach the optimal allocation set of the true instance. Consequently, we may choose t⋆∈L⋆() w_t _L ( μ) such that ‖(t)−t⋆‖→0\| w(t)- w_t \|→ 0. Together with the strong law and the standard continuity argument for Track-and-Stop statistics, this yields |IL((t),^(t))−IL(t⋆,)|⟶0almost surely. |I_L ( w(t), μ(t) )-I_L( w_t , μ) | 0 surely. Since every t⋆ w_t maximizes the information rate, IL(t⋆,)=1/TL⋆()I_L( w_t , μ)=1/T_L ( μ). Therefore, ZL(t)t⟶1TL⋆()almost surely. Z_L(t)t 1T_L ( μ) surely. Hence, for every η∈(0,1)η∈(0,1), there exists an almost surely finite random time tηt_η such that ZL(t)≥(1−η)tTL⋆()Z_L(t)≥ (1-η)tT_L ( μ) for all t≥tηt≥ t_η. Let tδ=⌈1+2η1−ηTL⋆()log1δ⌉.t_δ= 1+2η1-ηT_L ( μ) 1δ . By Eq. (17), β(tδ,δ)≤(1+η)log1δβ(t_δ,δ)≤(1+η) 1δ for all sufficiently small δ. Therefore, on the event tη≤tδ\t_η≤ t_δ\, ZL(tδ)≥(1+2η)log1δ>β(tδ,δ)Z_L(t_δ)≥(1+2η) 1δ>β(t_δ,δ) for all sufficiently small δ. Since tδ→∞t_δ→∞ and tη<∞t_η<∞ almost surely, ℙ(tη≤tδ)→1P_ μ(t_η≤ t_δ)→ 1. It follows that ℙ(τδ≤tδ)⟶1.P_ μ( _δ≤ t_δ) 1. Since (1+2η)/(1−η)(1+2η)/(1-η) can be made arbitrarily close to one by choosing η sufficiently small, relabeling the constant proves Eq. (18). ∎ References Ararat and Tekin (2023) C. Ararat and C. Tekin Vector optimization with stochastic bandit feedback. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, p. 2165–2190. Cited by: Appendix A, §1. Audibert and Bubeck (2010) J. Audibert and S. Bubeck Best arm identification in multi-armed bandits. In Proceedings of the 23rd Annual Conference on Learning Theory, p. 41–53. Cited by: Appendix A, §1. Auer et al. (2016) P. Auer, C. Chiang, R. Ortner, and M. Drugan Pareto front identification from stochastic bandit feedback. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, p. 939–947. Cited by: Appendix A, §1, §1. Chen et al. (2016) L. Chen, A. Gupta, and J. Li Pure exploration of multi-armed bandit under matroid constraints. In Proceedings of the 29th Annual Conference on Learning Theory, p. 647–669. Cited by: Appendix A. Chen et al. (2024) L. Chen, M. Zaharia, and J. Zou FrugalGPT: how to use large language models while reducing cost and improving performance. Transactions on Machine Learning Research. Cited by: §1. Chen et al. (2014) S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen Combinatorial pure exploration of multi-armed bandits. In Advances in Neural Information Processing Systems 27, p. 379–387. Cited by: Appendix A, §1. Chen et al. (2025) Z. Chen, P. N. Karthik, Y. M. Chee, and V. Y. F. Tan Optimal multi-objective best arm identification with fixed confidence. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, p. 1162–1170. Cited by: Appendix A, Appendix C, 1st item, 2nd item, §1, §1, §4, §5. Cheng et al. (2024) J. Cheng, B. Xue, J. Yi, and Q. Zhang Hierarchize pareto dominance in multi-objective stochastic linear bandits. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, p. 11489–11497. Cited by: Appendix A. Crepon et al. (2024) É. Crepon, A. Garivier, and W. M Koolen Sequential learning of the Pareto front for multi-objective bandits. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, p. 3583–3591. Cited by: Appendix A, §1. Das et al. (2025) U. Das, A. Shukla, and D. Basu FraPPE: fast and efficient preference-based pure exploration. In Advances in Neural Information Processing Systems 38, p. 10190–10236. Cited by: Appendix A. Degenne and Koolen (2019) R. Degenne and W. M. Koolen Pure exploration with multiple correct answers. In Advances in Neural Information Processing Systems 32, p. 14564–14573. Cited by: Appendix A, §1. Degenne et al. (2020) R. Degenne, P. Ménard, X. Shang, and M. Valko Gamification of pure exploration for linear bandits. In Proceedings of the 37th International Conference on Machine Learning, p. 2432–2442. Cited by: Appendix A. Drugan and Nowe (2013) M. M. Drugan and A. Nowe Designing multi-objective multi-armed bandits algorithms: a study. In The 2013 International Joint Conference on Neural Networks, p. 1–8. Cited by: Appendix A, §1, §1. Fiez et al. (2019) T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff Sequential experimental design for transductive linear bandits. In Advances in Neural Information Processing Systems 32, p. 10667–10677. Cited by: Appendix A. Gabillon et al. (2012) V. Gabillon, M. Ghavamzadeh, and A. Lazaric Best arm identification: a unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems 25, p. 3212–3220. Cited by: Appendix A. Garivier and Kaufmann (2016) A. Garivier and E. Kaufmann Optimal best arm identification with fixed confidence. In Proceedings of the 29th Annual Conference on Learning Theory, p. 998–1027. Cited by: Appendix A, Appendix C, §1, §1. Geng et al. (2020) T. Geng, X. Lin, and H. S. Nair Online evaluation of audiences for targeted advertising via bandit experiments. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, p. 13273–13279. Cited by: §1. Guo et al. (2026) P. Guo, T. Zhang, X. Lin, X. Li, Z. Tang, and Q. Zhang Few-for-many personalized federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 17515–17524. Cited by: Appendix A. Jedra and Proutiere (2020) Y. Jedra and A. Proutiere Optimal best-arm identification in linear bandits. In Advances in Neural Information Processing Systems 33, p. 10007–10017. Cited by: Appendix A. Jourdan et al. (2021) M. Jourdan, M. Mutný, J. Kirschner, and A. Krause Efficient pure exploration for combinatorial bandits with semi-bandit feedback. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, p. 805–849. Cited by: Appendix A, §1. Kavelaars et al. (2020) X. Kavelaars, J. Mulder, and M. Kaptein Decision-making with multiple correlated binary outcomes in clinical trials. Statistical Methods in Medical Research 29 (11), p. 3265–3277. Cited by: §1. Kohavi (1996) R. Kohavi Scaling up the accuracy of naive-bayes classifiers: a decision-tree hybrid. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, p. 202–207. Cited by: §5. Kone et al. (2023) C. Kone, E. Kaufmann, and L. Richert Adaptive algorithms for relaxed pareto set identification. In Advances in Neural Information Processing Systems 36, Cited by: Appendix A. Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári Bandit algorithms. Cambridge University Press. Cited by: §1. Lin et al. (2025) X. Lin, Y. Liu, X. Zhang, F. Liu, Z. Wang, and Q. Zhang Few for many: tchebycheff set scalarization for many-objective optimization. In The Thirteenth International Conference on Learning Representations, Cited by: Appendix A, 1st item, §1, §1, §1, §2. Lin et al. (2024) X. Lin, X. Zhang, Z. Yang, F. Liu, Z. Wang, and Q. Zhang Smooth tchebycheff scalarization for multi-objective optimization. In Proceedings of the 41st International Conference on Machine Learning, p. 30479–30509. Cited by: §1. Liu et al. (2025) Y. Liu, X. Lin, L. Zhao, and Q. Zhang Few for many: towards efficient and flexible many-objective optimization. IEEE Transactions on Evolutionary Computation. Cited by: Appendix A, §1, §1, §1. Liu et al. (2024) Y. Liu, C. Lu, X. Lin, and Q. Zhang Many-objective cover problem: discovering few solutions to cover many objectives. In Parallel Problem Solving from Nature, p. 68–82. Cited by: Appendix A, §1, §1. Ong et al. (2025) I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. Kadous, and I. Stoica Routellm: learning to route llms from preference data. In International Conference on Learning Representations, Vol. 2025, p. 34433–34448. Cited by: §1. Paria et al. (2020) B. Paria, K. Kandasamy, and B. Póczos A flexible framework for multi-objective bayesian optimization using random scalarizations. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence, p. 766–776. Cited by: §1. Park et al. (2025) S. Park, H. Ann, and M. Oh Thompson sampling for multi-objective linear contextual bandit. In Advances in Neural Information Processing Systems 38, p. 84523–84555. Cited by: Appendix A. Qiu et al. (2024) S. Qiu, D. Zhang, R. Yang, B. Lyu, and T. Zhang Traversing pareto optimal policies: provably efficient multi-objective reinforcement learning. arXiv preprint arXiv:2407.17466. Cited by: Appendix A. Schwartz et al. (2017) E. M. Schwartz, E. T. Bradlow, and P. S. Fader Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science 36 (4), p. 500–522. External Links: Document Cited by: §1. Shang et al. (2026) K. Shang, H. Ishibuchi, Z. Zhu, and Q. Zhang An efficient evolutionary algorithm for few-for-many optimization. IEEE/CAA Journal of Automatica Sinica 13 (6), p. 1362–1377. Cited by: Appendix A, §1, §1. Shukla and Basu (2024) A. Shukla and D. Basu Preference-based pure exploration. In Advances in Neural Information Processing Systems 37, p. 17313–17347. Cited by: Appendix A, §1. Turgay et al. (2018) E. Turgay, D. Oner, and C. Tekin Multi-objective contextual bandit problem with similarity information. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, p. 1673–1681. Cited by: Appendix A. Villar et al. (2015) S. S. Villar, J. Bowden, and J. Wason Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical Science 30 (2), p. 199 – 215. Cited by: §1. Xu and Klabjan (2023) M. Xu and D. Klabjan Pareto regret analyses in multi-objective multi-armed bandit. In Proceedings of the 40th International Conference on International Conference on Machine Learning, p. 38499–38517. Cited by: Appendix A. Xue et al. (2026a) B. Xue, J. Cheng, H. Jing, H. Li, and S. Qiu Efficient online lexicographic generalized low-rank matrix bandits. arXiv preprint arXiv:2608.04324. Cited by: Appendix A, §1. Xue et al. (2024) B. Xue, J. Cheng, F. Liu, Y. Wang, and Q. Zhang Multiobjective lipschitz bandits under lexicographic ordering. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 16238–16246. Cited by: Appendix A. Xue et al. (2026b) B. Xue, M. He, Y. Liu, J. Cheng, Z. Zhao, and Q. Zhang Safe multi-objective linear bandits with hierarchical preferences. In Proceedings of the 35th International Joint Conference on Artificial Intelligence, p. 2418–2426. Cited by: Appendix A, §1. Xue et al. (2026c) B. Xue, Z. Hong, J. Li, Y. Wan, J. Cheng, and S. Qiu Cost-aware multi-objective bandits: theory and application to budgeted llm configuration evaluation. arXiv preprint arXiv:2608.04333. Cited by: Appendix A, §1. Zhang (2024) Q. R. Zhang Optimal scalarizations for sublinear hypervolume regret. Advances in Neural Information Processing Systems 37, p. 39963–39999. Cited by: Appendix A.