Pure Exploration with Structured Preference Feedback

2021/04/12 by Gupta, Shubham, Saha, Aadirupa, Katariya, Sumeet
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2104.05294

Abstract

We consider the problem of pure exploration with subset-wise preference feedback, which contains N arms with features. The learner is allowed to query subsets of size K and receives feedback in the form of a noisy winner. The goal of the learner is to identify the best arm efficiently using as few queries as possible. This setting is relevant in various online decision-making scenarios involving human feedback such as online retailing, streaming services, news feed, and online advertising; since it is easier and more reliable for people to choose a preferred item from a subset than to assign a likability score to an item in isolation. To the best of our knowledge, this is the first work that considers the subset-wise preference feedback model in a structured setting, which allows for potentially infinite set of arms. We present two algorithms that guarantee the detection of the best-arm in O ((d²)/(K Δ²)) samples with probability at least 1 - δ, where d is the dimension of the arm-features and Δ is the appropriate notion of utility gap among the arms. We also derive an instance-dependent lower bound of Ω((d)/(Δ²) log \frac1δ) which matches our upper bound on a worst-case instance. Finally, we run extensive experiments to corroborate our theoretical findings, and observe that our adaptive algorithm stops and requires up to 12x fewer samples than a non-adaptive algorithm.

Related

• Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options
• PAC Battling Bandits in the Plackett-Luce Model
• Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design
• Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits
• Active Ranking with Subset-wise Preferences