PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Bo Xue, Yilu Liu, Haodong Jing, Hongzong Li, Xi Lin, Shuang Qiu

arXiv:2610.16840v1cs.LGcs.AI

TL;DR

When many objectives must be served by only a few options, identifying a separate best arm for every objective may not fit a limited deployment budget. This paper formulates few-for-many best-arm identification for known and latent groups and develops elimination algorithms with instance-dependent guarantees. Its experiments report fewer samples than existing multi-objective identification baselines, while the conclusion highlights observation sharing and avoiding irrelevant objective-wise distinctions.

  • Problem

    When many objectives must be served under a limited deployment budget, identifying a best arm for every objective may be unnecessarily costly, while few-for-many bandit identification must infer performance from noisy observations.

    Source: §1 · pp. 1–2

  • Method

    The paper formulates few-for-many identification for known groups and latent groups specified by a representative budget, and proposes GFM-Elim and AFM-Elim with instance-dependent guarantees.

    Source: §1 · p. 2

  • Results

    Experiments on synthetic and real-world tasks show GFM-Elim and AFM-Elim reliably identify compact representative sets using fewer samples than existing multi-objective identification baselines.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The conclusion reports that targeting few-for-many solutions can substantially reduce sample complexity by sharing observations and avoiding unnecessary objective-wise distinctions.

    Source: §6 · p. 12

    In the latent-group setting, exact identification involves combinatorial optimization, motivating future work on statistical efficiency and computational scalability.

    Source: §6 · p. 12

Abstract

from arXiv · show

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.

1 Introduction

Few-for-many best-arm identification addresses settings where many objectives must be served by a limited number of choices learned from noisy feedback. The paper defines this stochastic identification problem for known and latent objective groups and introduces algorithms and guarantees for both.

1 Introduction

  • Pareto-front identification can return many arms as objectives grow, while scalarization returns one solution for a given preference, motivating an intermediate few-arm goal.Source: §1 · p. 2
  • Few-for-many best-arm identification selects complementary arms to minimize the worst weighted degradation from objective-wise ideal values, with groups either known or induced by a representative budget.Source: §1 · p. 2
  • GFM-Elim handles known groups and AFM-Elim handles latent groups; both have finite-time sample-complexity guarantees and need not resolve distinctions irrelevant to optimal representatives.For Gaussian rewards, the latent-group setting also has an information-theoretic lower bound that an oracle-based Track-and-Stop procedure asymptotically attains with high probability.Source: §1 · p. 2
  • Experiments on synthetic and real-world tasks show GFM-Elim and AFM-Elim reliably identify compact representative sets using fewer samples than existing multi-objective identification baselines.Source: §1 · p. 2
  • The framework connects few-for-many optimization with MO-BAI, extending few-for-many selection to unknown vector-valued means learned from noisy sequential observations.Source: §1 · pp. 2–3

2 Preliminaries

The preliminaries model arms as having unknown vector-valued rewards observed through a multi-armed bandit. They define the few-for-many target under known objective groups and under a latent representative budget.

2 Preliminaries

  • Each pull returns a vector of rewards across M objectives, and each of K arms has an unknown mean reward vector.Source: §2 · p. 3
  • The framework assumes σ²-sub-Gaussian reward noise and permits statistically dependent reward coordinates; mean rewards are assumed to lie in [0, 1].Source: §2 · p. 3
  • Few-for-many identification seeks a small set of representatives that jointly serves many objectives, avoiding both a separate best arm for every objective and a single arm for all objectives.Source: §2 · pp. 3–4
  • With known groups, objectives are partitioned in advance and one representative serves each group; objective weights reflect their relative importance.Source: §2 · p. 4
  • Coverage loss measures the largest weighted degradation from objective-wise ideal values, using a group's representative in the known-group setting or each objective's best arm in the selected set in the latent setting.Source: §2 · p. 4
  • With latent groups, a budget L determines the number of representatives, whose best-served objectives implicitly form groups; L = 1 is a robust representative, while enough representatives can include every objective-wise best arm.Source: §2 · p. 4

3 Finite-Time Elimination Algorithms

The section develops phase-based elimination for known and latent objective groups, with sampling shared across the unresolved decisions that use each arm. It also describes a polynomial-time relaxation for latent groups that trades exact cardinality and instance-adaptive sampling for a bicriteria guarantee.

3.1 Grouped Few-for-Many Elimination

  • GFM-Elim jointly learns objective-wise benchmarks and group representatives, sampling arms relevant to unresolved groups and refining candidates through empirical means and coverage losses.Source: §3.1 · pp. 5–6
  • In each group, GFM-Elim eliminates a representative candidate when its optimistic loss exceeds the smallest pessimistic loss among candidates.Source: §3.1 · p. 6
  • With probability at least 1 − δ, GFM-Elim returns the optimal representative tuple within its instance-dependent pull bound, and shared feedback can improve the leading complexity term by up to a factor Q.Each arm is sampled until its benchmark and representative roles have been resolved, rather than incurring a separate sampling cost for every group.Source: §3.1 · p. 6

3.2 Adaptive Few-for-Many Elimination

  • AFM-Elim lifts elimination to candidate sets but samples base arms, sharing each observation across active sets that contain the arm and relevant objective benchmarks.Source: §3.2 · pp. 6–7
  • AFM-Elim eliminates a candidate set when its optimistic coverage loss exceeds another active set's pessimistic loss, continuing until one set remains.Source: §3.2 · p. 7
  • With probability at least 1 − δ, AFM-Elim returns the optimal representative set within its instance-dependent pull bound, adapting sampling to difficult set comparisons and benchmark estimation.An arm's observations are shared across active candidate sets containing it, rather than sampled separately for each set.Source: §3.2 · p. 8
  • BiAFM-Greedy avoids enumerating size-L sets by reducing fixed-threshold feasibility to set cover and applying a greedy rule across increasing loss thresholds.It uses uniform sampling and returns the first cover satisfying the relaxed budget.Source: §3.2 · p. 8
  • The polynomial-time relaxation returns coverage loss within ϵ of the optimal size-L loss while using at most O(L log M) arms, sacrificing exact size-L identification and instance-adaptive sampling.Source: §3.2 · p. 8

4 Information-Theoretic Lower Bound

For Gaussian rewards, the section characterizes the latent-group identification difficulty through a max–min information rate and establishes a fixed-confidence lower bound. An oracle-based Track-and-Stop procedure asymptotically attains the bound with high probability.

4 Information-Theoretic Lower Bound

  • The lower bound assumes independent Gaussian vector rewards with covariance σ²I_M and a unique optimal representative set.The KL divergence between mean vectors is their squared Euclidean distance divided by 2σ².Source: §4 · p. 8
  • The characteristic time optimizes sampling proportions against the hardest alternative instance that changes the optimal representative set.Its inverse is the maximal information rate and the leading constant in asymptotic sample complexity.Source: §4 · p. 9
  • Theorem 3 gives a lower bound for any fixed-confidence algorithm identifying the unique optimal representative set on every Gaussian instance.The bound scales with log(1/δ) and the instance’s characteristic time T*_L(µ).Source: §4 · p. 9
  • An oracle-based Track-and-Stop procedure asymptotically attains the lower bound with high probability.Unlike objective-wise MO-BAI, the bound requires distinguishing only alternatives that change the optimal representative set.Source: §4 · p. 9

5 Experiments

Across synthetic and Adult experiments, the proposed methods identify the correct representative sets while using fewer samples than objective-wise or uniform-sampling baselines. Their savings reflect both eliminating irrelevant arms and sharing vector feedback across objectives.

Experimental setup

  • The synthetic study varies irrelevant objective-wise gaps and feedback-sharing scale; the Adult task uses 12 classifier-threshold arms, 15 subgroup objectives, and budget L = 2.The synthetic instances include known groups and latent planted blocks; the Adult optimal pair comprises histogram-gradient-boosting models at thresholds 0.45 and 0.55.Source: §5 · pp. 9–10

Synthetic results

  • As ξ decreases, MO-BAI-based methods require substantially more samples, while GFM-Elim and AFM-Elim remain nearly insensitive to the irrelevant near-ties.Both proposed methods identify the correct representatives in every synthetic run and consistently use fewer samples than uniform variants through adaptive elimination.Source: Figure 1 · p. 10, §5 · p. 10

Real-world results

  • AFM-Elim uses roughly half the pulls of Uniform-AFM and about one third of MOBAI+AFM’s pulls on Adult, with all methods identifying the same optimal pair.Figure 2(c) reports sample cost for the Adult model-portfolio task.Source: Figure 2 · p. 11, §5 · p. 11

Synthetic results

  • Sharing vector feedback yields a gain that grows approximately linearly in Q, reaching about 32× at Q = 32.GFM-Elim reuses each pull across groups, unlike Independent-GFM, which solves groups separately; Figure 2(a)–(b) shows sample cost and sharing gain.Source: §5 · p. 10, Figure 2 · p. 11

6 Conclusion and Future Work

The paper develops fixed-confidence few-for-many identification for known and latent objective groups, with elimination algorithms, sample-complexity guarantees, and a latent-group lower bound. It situates this stochastic setting between deterministic few-for-many optimization and objective-wise bandit identification.

6 Conclusion and Future Work

  • GFM-Elim and AFM-Elim exploit vector feedback and eliminate arms once irrelevant, with instance-dependent guarantees for known and latent groups.For latent groups, an oracle-based Track-and-Stop procedure asymptotically attains the information-theoretic lower bound with high probability.Source: §6 · p. 11
  • Experiments show that directly targeting representative sets can reduce sample complexity by sharing observations and avoiding unnecessary objective-wise distinctions.The conclusion identifies both mechanisms as contributing to the reported reductions.Source: §6 · p. 12
  • Exact latent-group identification involves combinatorial optimization, motivating future work on reconciling statistical efficiency with computational scalability.The authors also identify adaptive representative budgets and partial feedback as extensions of interest.Source: §6 · p. 12

A Extended Related Work

  • Few-for-many optimization selects a small set of solutions to serve many objectives, while prior bandit work includes Pareto identification and preference-based criteria.The paper’s stochastic formulation adds unknown vector-valued means that must be inferred from observations.Source: A Extended Related Work · pp. 13–14
  • Prior few-for-many work primarily addresses deterministic optimization, whereas this paper studies identification from noisy sequential observations.Unlike MO-BAI, which seeks each objective’s best arm, few-for-many identification need not recover every objective-wise winner or the entire Pareto set.Source: A Extended Related Work · pp. 13–14

B Polynomial-Time Bicriteria Approximate Identification

BiAFM-Greedy makes latent-group identification polynomial-time by relaxing the representative-set size while controlling coverage loss. It converts loss-threshold feasibility into set cover and searches empirical deficit thresholds rather than enumerating candidate sets.

B Polynomial-Time Bicriteria Approximate Identification

  • BiAFM-Greedy returns a set with loss within ε of the best size-L set while allowing up to O(L log M) arms.Theorem 4 gives an (HM, ε, δ)-PAC guarantee, with HM ≤ 1 + log M ignoring integer rounding.Source: B Polynomial-Time Bicriteria… · pp. 14–16
  • For a fixed loss threshold, finding a minimum-cardinality representative set is equivalent to covering the objectives with arms.The procedure applies greedy set cover to the induced coverage sets.Source: B Polynomial-Time Bicriteria… · pp. 14–15
  • The algorithm samples all arms, computes empirical deficits, and tests their distinct values as thresholds rather than enumerating candidate sets.It examines at most KM thresholds and returns the first greedy cover satisfying the relaxed budget.Source: B Polynomial-Time Bicriteria… · p. 15

C Oracle-Based Track-and-Stop

AFM-TaS is an oracle-based counterpart to AFM-Elim that, under Gaussian rewards and the required exact optimization oracles, attains the latent-group information-theoretic lower bound with asymptotically high probability. Supplementary experiments examine confidence calibration, scaling with the number of objectives, and sensitivity to representative gaps.

C Oracle-Based Track-and-Stop

  • AFM-TaS repeatedly estimates the representative set, tracks an optimal sampling allocation, and stops when the GLR evidence against alternatives reaches its confidence threshold.The statistic measures the minimum accumulated evidence needed to move to an alternative where the current answer is no longer optimal.Source: C Oracle-Based Track-and-Stop · p. 16
  • Under Gaussian rewards and an exact allocation oracle, AFM-TaS is δ-PAC and its stopping time asymptotically matches the characteristic time in the latent-group lower bound.AFM-Elim instead provides a simpler finite-time procedure with an explicit non-asymptotic guarantee.Source: C Oracle-Based Track-and-Stop · p. 17

D Additional Experiments

  • The supplementary experiments test calibration, objective-count scaling, representative-gap sensitivity, and the computational behavior of the bicriteria algorithm; they omit AFM-TaS because it requires exact oracles and repeated GLR computations..Source: D Additional Experiments · p. 17

D.1 Confidence Calibration

  • Both elimination algorithms returned the correct answer in all trials at every tested confidence level; sample complexity increased only mildly as δ decreased, consistent with logarithmic dependence on 1/δ.Source: §D.1 · p. 18

D.2 Scaling with the Number of Objectives

  • As objectives grow, GFM-Elim identifies group representatives with substantially fewer pulls than MOBAI+GFM, and the gap widens because the baseline resolves unnecessary objective-wise specialists.GFM-Elim also improves over Independent-GFM by sharing each vector observation across group decisions.Source: §D.2 · pp. 18–19, Figure 4 · p. 18

D.3 Sensitivity to Representative Gaps

  • Shrinking the representative gap produces expected quadratic sample-complexity growth for GFM-Elim, with AFM-Elim showing the same pattern.GFM-Elim’s average sample complexity rises from thousands to hundreds of thousands as the gap shrinks from 0.2 to 0.025.Source: §D.3 · p. 19, Figure 5 · p. 19

D.4 Computational Scalability of the Bicriteria Algorithm

The supplementary experiment contrasts exact AFM-Elim with polynomial-time BiAFM-Greedy as the exact candidate family grows. The accompanying correctness results state that the elimination procedure succeeds with probability at least 1−δ and eventually removes suboptimal representatives.

D.4 Computational Scalability of the Bicriteria Algorithm

  • BiAFM-Greedy uses uniform sampling and avoids enumerating the exact size-L candidate family, trading sample efficiency and a strict budget for computational efficiency and a relaxed budget.The experiment varies the number of dominated arms, increasing the number of exact candidate sets.Source: §D.4 · pp. 19–20

E.1 Confidence bounds and correctness

  • On event E, whose probability is at least 1−δ, the optimal representative remains while every suboptimal representative is eventually eliminated as ϵr approaches zero.The elimination rule removes a suboptimal candidate at the first phase when its stated condition holds.Source: §E.1 · pp. 20, 22, 23

D.4 Computational Scalability of the Bicriteria Algorithm

  • On tested configurations, BiAFM-Greedy uses more pulls but stays below one millisecond and attains zero true coverage loss, while exact AFM-Elim respects L = 4.BiAFM-Greedy returns a larger set within the relaxed budget; AFM-Elim returns the strict size-L set with nonzero coverage loss.Source: §D.4 · p. 20, Table 1 · p. 20, Figure 6 · p. 21

E.2 Proof of Theorem 1

The proof bounds GFM-Elim’s sampling by the phases needed to resolve candidate-arm roles, then establishes confidence and correctness for set-level elimination. The set-level confidence radius depends logarithmically on KM rather than on the exponentially large candidate-set family.

E.2 Proof of Theorem 1

  • All suboptimal candidates in a group are eliminated once ϵr < ρq, so the group is resolved by the first phase meeting that condition.The proof combines this phase bound with the confidence event to establish the guarantee.Source: §E.2 · pp. 23–24
  • On event E, each arm’s representative and benchmark roles end by a phase determined by their gaps, yielding the stated total-pull bound and a high-probability guarantee.The event has probability at least 1−δ.Source: §E.2 · pp. 23–24

F.1 Set-level confidence bounds and correctness

  • The set-level confidence event depends on KM base-arm means, so its confidence radius scales logarithmically in KM rather than in the exponentially large candidate-set count.On that event, every suboptimal candidate set is eventually eliminated, establishing δ-PAC correctness.Source: §F.1 · p. 25

F.2 Proof of Theorem 2

The proofs establish high-probability pull guarantees, recover latent objective assignments under a uniqueness assumption, derive a lower-bound relation, and validate threshold-based covering guarantees.

F.2 Proof of Theorem 2

  • On event E, the proof bounds total pulls by the order in Eq. (8), and Pµ(E)≥1−δ yields the high-probability guarantee.Source: §F.2 · p. 26

F.3 Recovery of the latent objective groups

  • Under Assumption 1, once ε_r<ζ_min/4, the selected-set arm with the largest true mean satisfies Eq. (29), making the certified objective assignment correct.Source: §F.3 · pp. 26–27

G Proof of Theorem 3

  • The adaptive-sampling change-of-measure argument combines a simplex sampling allocation and alternatives to prove Eq. (11), with Eq. (12) following as δ↓0.Source: G Proof of Theorem 3 · p. 28

H Proof of Theorem 4

  • Algorithm 4 scans thresholds, returns a cover with empirical loss bounded by its selected threshold, and selects a threshold no larger than γ⋆_emp.Source: H Proof of Theorem 4 · p. 29
  • Algorithm 4 uses exactly Kn arm pulls and polynomial computation; its budget guarantee holds with probability at least 1−δ.Source: H Proof of Theorem 4 · p. 29

I Proof of Theorem 5

The proof establishes the stated asymptotic guarantee by controlling the tracking procedure and showing that its relevant event occurs with probability tending to one. It also verifies the δ-PAC property.

I Proof of Theorem 5

  • The stopping rule is δ-PAC because an incorrect recommendation can occur only on an event whose probability is at most δ.Source: I Proof of Theorem 5 · pp. 29–30
  • The oracle allocation and tracking step apply the Track-and-Stop rule to the latent answer space, and the realized sampling proportions approach the true-instance optimal allocation set.Source: I Proof of Theorem 5 · p. 30
  • As η→0, the proof closes Eq. (18), with the relevant event probability tending to one as δ→0.Source: I Proof of Theorem 5 · p. 31
Loading 2610.16840v1…