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

arXiv: https://arxiv.org/abs/2610.18577 · HTML: https://mlsanity.com/paper/2610.18577/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 44 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 25 of 25)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Multi-objective Contextual Bandit Problem with Similarity Information](https://mlsanity.com/paper/1803.04015/) (2018)
- [Multi-objective Contextual Multi-armed Bandit with a Dominant Objective](https://mlsanity.com/paper/1708.05655/) (2017)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [FraPPE: Fast and Efficient Preference-based Pure Exploration](https://mlsanity.com/paper/2508.16487/) (2025)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits](https://mlsanity.com/paper/2511.05802/) (2025)

## Abstract (arXiv)

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.