论文标题
带有子集选择的随机实用程序模型中的最佳项目学习
Best-item Learning in Random Utility Models with Subset Choices
论文作者
论文摘要
我们考虑PAC从$ n $项目中学习最有价值的物品的问题，使用$ k $项目的子宫子的序列播放，当在扮演子集后，学习者会根据一般的随机效用模型（朗姆酒）采样，并根据对潜在项目的独立噪声扰动进行相对的反馈。我们确定了这种朗姆酒的新属性，称为最低优势，有助于表征基于其相对的赢/损失经验计数分离项目对的复杂性，并且可以单独根据噪声分布来界定。我们为一般朗姆酒提供了学习算法，基于项目的成对相对计数和分层消除，以及新的PAC样品复杂性保证$ O（\ frac {n} {c^2ε^2} \ log \ log \ frac {k}δ）$ ndive $ poptim $ $ε$ 1-Δ至少$ c $到项目的参数差距。 PAC样品复杂性的基本下限表明，就其依赖$ N，K $和$ C $而言，这几乎是最理想的。
We consider the problem of PAC learning the most valuable item from a pool of $n$ items using sequential, adaptively chosen plays of subsets of $k$ items, when, upon playing a subset, the learner receives relative feedback sampled according to a general Random Utility Model (RUM) with independent noise perturbations to the latent item utilities. We identify a new property of such a RUM, termed the minimum advantage, that helps in characterizing the complexity of separating pairs of items based on their relative win/loss empirical counts, and can be bounded as a function of the noise distribution alone. We give a learning algorithm for general RUMs, based on pairwise relative counts of items and hierarchical elimination, along with a new PAC sample complexity guarantee of $O(\frac{n}{c^2ε^2} \log \frac{k}δ)$ rounds to identify an $ε$-optimal item with confidence $1-δ$, when the worst case pairwise advantage in the RUM has sensitivity at least $c$ to the parameter gaps of items. Fundamental lower bounds on PAC sample complexity show that this is near-optimal in terms of its dependence on $n,k$ and $c$.
