sampling 从Thompson Sampling到增强学习, 再谈多臂老虎机问题

老虎机是赌场最常见的设备。赌场里的机器太多了，你可能会后悔，或者每次摇一摇都会得到一定的奖励。选择不同的吃角子老虎机兵种可以最大化自己的兴趣。这个问题看似很简单，却让很多人忘记了这其实是一个强化学习的问题。

问题描述

(伯努利·班迪特)假设我们有一个K臂吃角子老虎机，每个臂的回报(悬赏_i)是固定的，但是代理人不知道回报是什么，代理人如何在T轮中实现回报最大化(注意这里的T通常远大于K)。

在互联网行业，多臂吃角子老虎机的问题非常普遍，因为这些动作可以被视为不同的广告。当用户来网站看广告，并且每个广告都有固定的点击率时，平台需要找到一个最优的策略来显示广告，最大化自己的兴趣。

最简单的方法就是贪心。该模型试图计算每个动作的回报，然后选择回报最大的动作进行操作。这种贪婪方法的问题是，如果不完全探索其他奖励概率的可能性，很容易失去最优解。

一种先进的贪婪策略是根据概率ε进行探索，根据均匀分布选择一个手臂进行尝试，根据1-ε的概率选择当前情况下收益率最高的动作。虽然这种做法比纯粹的贪婪要好，但是对于下面的情况，我们知道行动2的概率远远小于行动1，但是我们会以一定的概率反复测试行动2，增加损失。

汤普森抽样指南

根据每个动作的返回概率，可以有效减少无用的探索，由此引出话题一，汤普森采样。

汤普森采样

汤普森抽样把多臂博彩机每个动作的返回概率看作一个beta分布，我们给出了分布先验概率参数α和Beta，那么动作的返回分布可以描述为如下函数:

维基百科-测试版发布

这里，我们使用伽马函数来归一化分布。当我们收集越来越多的实验结果时，我们可以更新分布参数α和β:

汤普森抽样指南

贝塔分布有很多固有的性质。我们观察到的结果越多，分布的置信区间越窄。比如一开始alpha=1，beta=1。当我们观察到三个正回报和五个负回报时，(α，β)=(4，6)，就产生了上图中动作3的概率分布。当我们观察到599个有回报的动作和399个零回报的动作时，(α，β)=(600，400)，生成上图中动作1的概率分布。

我们可以在K=10的多臂赌博机上比较Epsilon-Greedy和Thompson采样的实验结果。在回合数较少的情况下，Thompson Sampling可能以相对较高的概率进行探索，在较少的情况下使用最佳动作，从而产生相对较高的RERERET。但在回合数上升后，汤普森采样的尝试收敛，总RERET数也收敛。

多兵种土匪问题及其解决方法

实战调整

上述汤普森抽样主要是针对理想情况，忽略了现实中可能遇到的许多问题。在这里，我将讨论汤普森采样对三个小问题的变形。

先验估计:多臂赌博机最常见的问题之一是广告。对于一个新的广告，我们可以假设之前不知道这个广告的任何信息，然后用Thompson Sampling进行测试。我们也可以尝试通过广告商历史信息和文本历史信息来估计先验概率，然后用汤普森抽样(Thompson Sampling)来检验，这样会在更少的时间内得到相对准确的估计。

比如下面这个例子，我们有10个广告，他们的点击率不高。方法1使用Beta(1，1)的先验知识，方法2使用Beta(1，100)的先验知识。广告点击率0.005左右。因为方法2更接近真实情况，所以在有限的尝试后估计广告的点击率比方法1有效得多。

非平稳过程:考虑到电商的场景，冬天展示冬装，用户购买率高，夏天展示夏装。每个展示产品的购买率随时间而变化。抽象地说，我们的动作收益率不是一个固定的参数A，而是一系列参数a1，a2，...，随时间而变化。这样，我们需要一直探索，才能得到最好的回报。

这种非平稳过程并不总是适合汤普森采样，但如果每个时间段参数变化很小，我们可以做更多的测试，仍然可以有效地解决这个问题。最简单的方法是只使用一些最近的数据进行建模。例如，我们可以计算每个产品在过去一周的性能，以适应时间的变化。

另一种常见的方法是使用timedeck，如下图所示:

汤普森抽样指南

下图是多臂赌博机有两臂，一臂从0.1逐渐上升到0.6，另一臂从0.9逐渐下降到0.4时，不同的汤普森抽样方法得到的不同结果。之前的改动比较慢的时候，时间衰减的版本也不算太差。一旦发生剧变，不合适的版本会后悔。

上下文特征:我想说的最后一点是利用上下文特征优化汤普森采样，这和我们日常使用的推荐系统非常相似。上下文特征是我们拥有的用户信息、环境信息和产品信息。基于这些特征，我们可以估计先验，然后用汤普森抽样进行实验。既然这部分很重要，那我们就分开写下一篇。

增强型学习老虎机

回到一个更大的话题，我们可以用另一种学习增强算法来解决多臂赌博机问题，即把每一只手臂都当作一个二元分类问题来处理。我们设计了一个非常简单的有k个输出节点的神经网络，每个节点的权重就是选择arm的回报。最初，每个手臂的回位是0。

每次我们在手臂上执行一个动作，手臂的重量都会根据反馈进行更新，可以应用最经典的分类损失:

我们还需要引入概率epislon来探索，以确保我们不会错过最佳值:

转来转去，从ε-贪婪算法到最好的汤普森抽样算法，最后通过策略梯度回到ε-贪婪，输给了后面有固定概率的老虎机的传统做法。

这个话题到此结束。下一次我讲上下文类，这是和推荐系统最相关的话题。

推荐:

多兵种土匪问题及其解决方法

https://lilian Weng . github . io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions . html

一个朋友的博客，比较了Epsilon Greedy，UCB，Bayesian UCB，Thompson Sampling的算法，是我看过写的最好的博客。本文中的很多图片都是由本文提供的开源代码生成的。

汤普森抽样指南

https://arxiv.org/pdf/1707.02038.pdf

本文从汤普森采样谈起实际问题，最后谈到局限性，强烈推荐。

张量流中的简单强化学习:第一部分——双臂强盗

https://medium . com/@ awjuliani/super-simple-reduction-learning-tutorial-part-1-FD 544 fab 149

张量流用于解决双臂赌博机的问题，策略梯度算法用于张量流。

原创文章，保留所有权利。

请勿擅自转载。

图片来源于网络，版权归原作者所有。