Thompson Sampling for the MNL-Bandit
Thompson Sampling for the MNL-Bandit
复制标题
MNL-Bandit 的 Thompson 采样
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Zeevi
中科院分区：
文献类型：
--
作者：
Shipra Agrawal;Vashist Avadhanula;Vineet Goyal;A. Zeevi
考虑参数不确定下的序贯子集选择问题，其中在每个时间步，决策者从$N$个可能的项目(ARM)中选择一个基数$K$的子集，并观察所述子集中的一个项目的索引形式的反馈，或者没有反馈。指标集合中的每一项都被赋予一定的值(奖励)，反馈由参数为先验未知的多项Logit(MNL)选择模型控制。决策者的目标是在有限的范围内最大化预期的累积回报$T$，或者，相对于知道MNL参数的先知，最小化遗憾。我们称之为MNL-Bandit问题。这个问题代表了一大类涉及组合目标的勘探-开采问题，并出现在几个重要的应用领域。我们提出了一种使Thompson抽样适用于这个问题的方法，并证明了它获得了接近最优的遗憾以及吸引人的数值性能。
We consider a sequential subset selection problem under parameter uncertainty, where at each time step, the decision maker selects a subset of cardinality $K$ from $N$ possible items (arms), and observes a (bandit) feedback in the form of the index of one of the items in said subset, or none. Each item in the index set is ascribed a certain value (reward), and the feedback is governed by a Multinomial Logit (MNL) choice model whose parameters are a priori unknown. The objective of the decision maker is to maximize the expected cumulative rewards over a finite horizon $T$, or alternatively, minimize the regret relative to an oracle that knows the MNL parameters. We refer to this as the MNL-Bandit problem. This problem is representative of a larger family of exploration-exploitation problems that involve a combinatorial objective, and arise in several important application domains. We present an approach to adapt Thompson Sampling to this problem and show that it achieves near-optimal regret as well as attractive numerical performance.