Preference-based Pure Exploration
This work addresses a specific variant of bandit problems for decision-making under preferences, but it is incremental as it builds on existing best-arm identification methods.
The paper tackles the preference-based pure exploration problem for bandits with vector-valued rewards, aiming to identify Pareto optimal arms using a given preference cone, and shows that their PreTS algorithm achieves asymptotically tight sample complexity with a derived lower bound highlighting the role of preference cone geometry.
We study the preference-based pure exploration problem for bandits with vector-valued rewards. The rewards are ordered using a (given) preference cone $\mathcal{C}$ and our goal is to identify the set of Pareto optimal arms. First, to quantify the impact of preferences, we derive a novel lower bound on sample complexity for identifying the most preferred policy with a confidence level $1-δ$. Our lower bound elicits the role played by the geometry of the preference cone and punctuates the difference in hardness compared to existing best-arm identification variants of the problem. We further explicate this geometry when the rewards follow Gaussian distributions. We then provide a convex relaxation of the lower bound and leverage it to design the Preference-based Track and Stop (PreTS) algorithm that identifies the most preferred policy. Finally, we show that the sample complexity of PreTS is asymptotically tight by deriving a new concentration inequality for vector-valued rewards.