analiza aiqbench
This research demonstrates a counterintuitive finding in multi-objective bandits where richer feedback from multiple criteria can reduce the sample complexity required for best-arm identification compared to single-objective settings. The authors establish theoretical lower bounds and introduce the Order-Aware Track-and-Stop (OATS) algorithm, which asymptotically matches these bounds while accommodating various preference structures like Pareto and lexicographic orders. These results advance the theoretical understanding of exploration-exploitation trade-offs in complex decision-making frameworks relevant to advanced reinforcement learning systems.
When More Objectives Make Identification Easier: The Role of Preferences and Feedback
arXiv:2610.18577v1 Announce Type: cross 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.
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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2610.18577 [cs.LG]
(or arXiv:2610.18577v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.18577 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 279 cuvinte
Subiecte conexe
Do AI models assist with human rights violations?
LessWrong · 29 sept. 2026
Presentation: Engineering AI for Creativity and Curiosity on Mobile
InfoQ · 21 iul. 2026
Salesforce after Dreamforce: How the CRM giant can grow beyond its own interface
SiliconANGLE · 19 sept. 2026
[AINews] Reality Checks on AI News (Yegge shuts down Gas Town, Databricks’ +60% Astra cost)
Latent Space · 17 sept. 2026