Choice Bandits
Choice Bandits
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Arpit Agarwal;Nicholas Johnson;S. Agarwal
中科院分区：
文献类型：
--
作者：
Arpit Agarwal;Nicholas Johnson;S. Agarwal
近年来，人们对决斗强盗问题产生了很大的兴趣，在每一轮中，学习者都会扮演一对手臂，并接收它们之间相对成对比较的结果作为反馈。在这里，我们研究一种自然概括，我们称之为选择老虎机，其中学习者扮演一组最多 k ≥ 2 个手臂，并以从底层多路选择模型中提取的拉动手臂中的单个多路选择的形式接收有限的相对反馈。我们在非常一般的选择模型类别下研究选择强盗，该模型的特征是存在唯一的“最佳”臂（我们称之为广义孔多塞赢家），并且包括作为特殊情况的经过充分研究的多项式 Logit (MNL) 和多项式概率 (MNP) 选择模型，以及更一般地，具有 i.i.d. 的随机效用模型类别。噪声（IID-RUM）。我们提出了一种选择老虎机的算法，称为 Winner Beats All (WBA)，在所有这些选择模型下具有与分布相关的 O(log T ) 后悔界限。我们设置中的挑战是决策空间是 θ(n)，即使对于中等 k 来说，该空间也很大。我们的算法通过从多路选择中提取 O(n) 统计数据并利用唯一的“最佳”臂的存在来找到与该臂竞争的臂，从而构建具有低遗憾的集合，从而解决了这一挑战。由于这些统计数据是从相同的选择观察中提取的，因此需要进行仔细的鞅分析，以表明这些统计数据是集中的。我们用下界结果补充我们的上限结果，这表明我们的上限是按顺序最优的。我们的实验表明，对于 k = 2 的特殊情况，我们的算法与之前的决斗老虎机算法具有竞争力，并且对于更一般的情况 k > 2，优于最近提出的为 MNL 模型设计的 MaxMinUCB 算法。
There has been much interest in recent years in the problem of dueling bandits, where on each round the learner plays a pair of arms and receives as feedback the outcome of a relative pairwise comparison between them. Here we study a natural generalization, that we term choice bandits, where the learner plays a set of up to k ≥ 2 arms, and receives limited relative feedback in the form of a single multiway choice among the pulled arms, drawn from an underlying multiway choice model. We study choice bandits under a very general class of choice models that is characterized by the existence of a unique ‘best’ arm (which we term generalized Condorcet winner), and includes as special cases the well-studied multinomial logit (MNL) and multinomial probit (MNP) choice models, and more generally, the class of random utility models with i.i.d. noise (IID-RUMs). We propose an algorithm for choice bandits, termed Winner Beats All (WBA), with a distribution dependent O(log T ) regret bound under all these choice models. The challenge in our setting is that the decision space is Θ(n), which is large for even moderate k. Our algorithm addresses this challenge by extracting just O(n) statistics from multiway choices and exploiting the existence of a unique ‘best’ arm to find arms that are competitive to this arm in order to construct sets with low regret. Since these statistics are extracted from the same choice observations, one needs a careful martingale analysis in order to show that these statistics are concentrated. We complement our upper bound result with a lower bound result, which shows that our upper bound is order-wise optimal. Our experiments demonstrate that for the special case of k = 2, our algorithm is competitive with previous dueling bandit algorithms, and for the more general case k > 2, outperforms the recently proposed MaxMinUCB algorithm designed for the MNL model.