Open Problem: Regret Bounds for Thompson Sampling
Open Problem: Regret Bounds for Thompson Sampling
复制标题
开放问题：汤普森抽样的遗憾界限
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Olivier Chapelle
中科院分区：
文献类型：
--
作者：
Lihong Li;Olivier Chapelle
背景多武装土匪（Langford和Zhang，2008）近年来由于其在互联网上的广泛应用，如新的推荐和广告，受到了极大的关注。这里的基本挑战是平衡探索和利用，使算法收集的总收益接近最优策略。探索技术，如贪婪，UCB（置信上限），以及他们的许多变种已被广泛研究。有趣的是，最古老的探索方法之一，可以追溯到汤普森（1933年），直到最近研究人员开始意识到其在关键的现实世界应用中的有效性时，才在文献中流行起来（Scott，2010年; Graepel等人，2010; May和Leslie，2011; Chapelle和Li，2012）。这种启发式方法被称为汤普森抽样，它实现了“概率匹配”的原则，即选择一个手臂的概率是最优的。在算法1中给出了一般描述，其中该算法保持后验分布P（θ| D）在定义一组贪婪策略的参数空间Θ上。在每一步，从后验中得出一个随机模型θt，并根据θt的收益预测选择贪婪行动。
Contextual multi-armed bandits (Langford and Zhang, 2008) have received substantial interests in recent years due to their wide applications on the Internet, such as new recommendation and advertising. The fundamental challenge here is to balance exploration and exploitation so that the total payoff collected by an algorithm approaches that of an optimal strategy. Exploration techniques like -greedy, UCB (upper confidence bound), and their many variants have been extensively studied. Interestingly, one of the oldest exploration heuristics, dated back to Thompson (1933), has not been popular in the literature until recently when researchers started to realize its effectiveness in critical real-world applications (Scott, 2010; Graepel et al., 2010; May and Leslie, 2011; Chapelle and Li, 2012). This heuristic, known as Thompson sampling, fulfills the principle of “probability matching,” which states that an arm is chosen with the probability that it is the optimal one. A generic description is given in Algorithm 1, where the algorithm maintains a posterior distribution P (θ|D) over a parameter space Θ that defines a set of greedy policies. At every step, a random model θt is drawn from the posterior, and the greedy action according to the payoff predictions of θt is chosen.