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

Bo Xue; Ji Cheng; Yuanyu Wan; Shuang Qiu

cs.LGOct 13, 2026

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

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

Organizations: City University of Hong Kong · Zhejiang University

Abstract

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

Explore similar work

Oct 12, 2026

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

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.

Bo Xue, Yilu Liu, Haodong Jing +3

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

Multi-Armed Bandits Best-Arm Identification

Ask PDF

Mar 11, 2026

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

We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget

T\in \mathbb{N}

, finite arm set

\mathcal{X} \subset \mathbb{R}^d

, and a potentially adversarial sequence of unknown parameters

\lbrace θ_t\rbrace_{t=1}^{T}

(hence non-stationary), a learner aims to identify the arm with the largest cumulative reward

x_* = \arg\max_{x \in \mathcal{X}} x^\top\sum_{t=1}^T θ_t

with high probability. In this setting, it is well-known that uniformly sampling arms from the G-optimal design yields a minimax-optimal error probability of

\exp\left(-Θ\left(T / H_{G}\right)\right)

, where

H_{G}

scales proportionally with the dimension

d

. However, this notion of complexity is overly pessimistic, as it is derived from a lower bound in which the arm set consists only of the standard basis vectors, thus masking any potential advantages arising from arm sets with richer geometric structure. To address this, we establish an arm-set-dependent lower bound that, in contrast, holds for any arm set. Motivated by the ideas underlying our lower bound, we propose the Adjacent-optimal design, a specialization of the well-known

\mathcal{X}\mathcal{Y}

-optimal design, and develop the

\textsf{Adjacent-BAI}

algorithm. We prove that the error probability of

\textsf{Adjacent-BAI}

matches our lower bound up to constants, verifying the tightness of our lower bound, and establishing the arm-set-dependent complexity of this setting.

Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1

University of Washington

Multi-Armed Bandits Best-Arm Identification Non-Stationary Bandits

Ask PDF

Apr 5, 2026

Nearly Optimal Best Arm Identification for Semiparametric Bandits

We study fixed-confidence Best Arm Identification (BAI) in semiparametric bandits, where rewards are linear in arm features plus an unknown additive baseline shift. Unlike linear-bandit BAI, this setting requires orthogonalized regression, and its instance-optimal sample complexity has remained open. For the transductive setting, we establish an attainable instance-dependent lower bound characterized by the corresponding linear-bandit complexity on shifted features. We then propose a computationally efficient phase-elimination algorithm based on a new

XY

-design for orthogonalized regression. Our analysis yields a nearly optimal high-probability sample-complexity upper bound, up to log factors and an additive

d^2

term, and experiments on synthetic instances and the Jester dataset show clear gains over prior baselines.

Seok-Jin Kim

Columbia University

Best-Arm Identification Multi-Armed Bandits Semiparametric Inference

Ask PDF