Summary of Preference-based Pure Exploration, by Apurv Shukla et al.
Preference-based Pure Exploration
by Apurv Shukla, Debabrota Basu
First submitted to arxiv on: 4 Dec 2024
Categories
- Main: Machine Learning (stat.ML)
- Secondary: Machine Learning (cs.LG)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper tackles the problem of preference-based pure exploration in bandits with vector-valued rewards. The researchers aim to identify the set of Pareto optimal arms, where the rewards are ordered using a given preference cone. To quantify the impact of preferences, they derive a novel lower bound on sample complexity for identifying the most preferred policy with a confidence level 1-δ. This lower bound highlights the role played by the geometry of the preference cone and demonstrates the difference in hardness compared to existing best-arm identification variants. The researchers also 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, they show that the sample complexity of PreTS is asymptotically tight by deriving a new concentration inequality for vector-valued rewards. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper explores how to find the best option in bandit problems when there are multiple good options and some of them are better than others. The researchers use something called a preference cone to understand what makes one option better than another, and they come up with a new way to figure out which option is the best. They also create an algorithm that can be used to find the best option and show that it works well. |
