Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates multi-objective best-arm identification (BAI) in Gaussian bandits, demonstrating that contrary to intuition, additional objectives can simplify identification by providing richer feedback. Through explicit comparisons under Pareto, linear, and lexicographic preferences, it's shown that larger optimal sets can be identified with fewer samples than unique optima, and multi-objective identification can outperform even the easiest single-objective counterparts. An algorithm, Order-Aware Track-and-Stop (OATS), is proposed that achieves asymptotic optimality against a derived characteristic-time lower bound.
Multi-objective bandits can make finding the best arm *easier* than single-objective settings, even identifying larger optimal sets with fewer samples.
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.