We introduce the probably approximately correct (PAC) version of the problem of {Battling-bandits} with the Plackett-Luce (PL) model -- an online learning framework where in each trial, the learner chooses a subset of $k \le n$ arms from a pool of fixed set of $n$ arms, and subsequently observes a stochastic feedback indicating preference information over the items in the chosen subset; e.g., the most preferred item or ranking of the top $m$ most preferred items etc. The objective is to recover an `approximate-best' item of the underlying PL model with high probability. This framework is motivated by practical settings such as recommendation systems and information retrieval, where it is easier and more efficient to collect relative feedback for multiple arms at once. Our framework can be seen as a generalization of the well-studied PAC-{Dueling-Bandit} problem over set of $n$ arms. We propose two different feedback models: just the winner information (WI), and ranking of top-$m$ items (TR), for any $2\le m \le k$. We show that with just the winner information (WI), one cannot recover the `approximate-best' item with sample complexity lesser than $\Omega\bigg( \frac{n}{\epsilon^2} \ln \frac{1}{\delta}\bigg)$, which is independent of $k$, and same as the one required for standard dueling bandit setting ($k=2$). However with top-$m$ ranking (TR) feedback, our lower analysis proves an improved sample complexity guarantee of $\Omega\bigg( \frac{n}{m\epsilon^2} \ln \frac{1}{\delta}\bigg)$, which shows a relative improvement of $\frac{1}{m}$ factor compared to WI feedback, rightfully justifying the additional information gain due to the knowledge of ranking of topmost $m$ items. We also provide algorithms for each of the above feedback models, our theoretical analyses proves the {optimality} of their sample complexities which matches the derived lower bounds (upto logarithmic factors).
翻译:我们以 Plackett-Luce (PL) 模式引入了大约正确的 {Battling-bandits} 问题( PAC) 的 Rism (PAC) 版本 {Battling-bandits} 。 这个框架是一个在线学习框架, 每次测试中, 学习者从一组固定的美元武器中选择一个 $k\ le n$ 的子集, 然后我们看到一个随机的反馈, 显示比所选择的子集中的项目更优先的信息; 例如, 最喜欢的项目或最喜欢的项目的排名 $m$ more 。 目标是回收一个基础的 TR $m 的“ 最接近 ” 项目 。 这个框架的驱动力是像建议系统和信息检索那样的实际设置, 一次采集多个武器的相对反馈比较容易和有效。 我们的框架可以被看成是精细的 PAC- {Delge- bit} 问题, 比所选择的 $n 更低的 。 我们建议两个不同的反馈模式: 仅用于赢家信息, 和最高的 Rent $ tal rima rima rist rist rist dreal dre dism 。