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

老虎机是赌场里最常见的一个设备，一家赌场里有那么多机器，每次摇动都可能后悔或者获得一定额度的奖励，你通过选择不同的老虎机臂最大化自己的利益。这个问题看似非常简单，让很多人都忘了他其实是一个reinforcement learning的问题。

问题描述

(Bernoulli Bandit)假设我们有一个K臂老虎机，每一个臂(action)的回报率(reward_i)都是固定的，但是agent并不知道这个回报率是多少，agent如何在T回合内最大化自己的回报(注意，这里的T通常是远远大于K的)。

在互联网行业，多臂老虎机问题之所以非常流行，是因为这些action可以被看做不同的广告投放，当用户来到网站上看到广告，对每一个广告有固定的点击率，那么平台就需要寻找一种最优策略来显示广告，最大化自己的利益。

最简单的做法就是贪心，模型想办法计算每一个action的回报，然后选择回报最大的action进行操作。这种贪心的做法问题就是没有完全探索其它奖励概率的可能性，很容易丢掉最优解。

有一种高级贪心的策略就是按照概率epsilon进行探索，按照uniform distribution选择一个臂进行尝试，按照1-epsilon的概率选择当前情况下回报率最大的action。尽管这种做法比纯贪心的情况好，但是对于下面这种情况，我们通过探索知道action 2的概率远远小于action 1，但还是会以一定的概率反复测试action 2，加大了损失。

A Tutorial on Thompson Sampling

根据对每一个action的回报概率计算置信度，我们可以有效地减少无用的探索，这就引出了今天要讲主题一，Thompson Sampling。

Thompson Sampling

Thompson Sampling将多臂赌博机每一个action的回报概率看做一个Beta分布，我们给分布先验概率参数alpha和beta，那么action的回报分布可以被描述成以下函数：

wikipedia - Beta distribution

这里我们利用gamma函数对分布就行归一化处理，当我们收集到越来越多的实验结果后，我们可以对分布的参数alpha和beta进行更新：

A Tutorial on Thompson Sampling

Beta分布有很多与生俱来的性质，随着我们观测到的结果越多，分布的置信区间就越窄，比方说最开始alpha=1, beta=1，当我们观测到3次正回报，5次负回报后，(alpha, beta)=(4, 6)，就产生了上图中action 3的概率分布。当我们观测到599次回报和399次零回报的动作后，(alpha, beta)=(600, 400)，就产生了上图中action 1的概率分布。

我们可以在K=10的多臂赌博机上对比一下Epsilon-Greedy和Thompson Sampling的实验效果，当轮数较少时，Thompson Sampling可能会以比较大的概率进行探索，较少的情况使用最佳动作，产生比较高的regret，但是轮数上升后，Thompson Sampling的尝试收敛了，总regret数也随着收敛。

The Multi-Armed Bandit Problem and Its Solutions

实战调整

上面描述的Thompson Sampling主要针对比较理想的情况，忽略了很多现实中可能遇到的问题，在这里我就针对三个小问题讨论一下Thompson Sampling可以做的变形。

先验估计:多臂赌博机最常见的一个问题就是广告投放，对于一个新的广告，我们既可以假设之前不知道这个广告的任何信息，先验概率为Beta(1,1)，然后运用Thompson Sampling进行测试，也可以试图通过广告主历史信息，文字历史信息对先验概率进行一定的估计，再利用Thompson Sampling进行测试，后者会用更少的时间得到一个相对准确的估计。

比方说下面这个例子，我们有10个广告，他们的点击率都不高。方法1采用Beta(1,1)的先验知识，方法2采用Beta(1,100)的先验知识，广告点击率在0.005左右，由于方法2更贴近真实情况，经过有限的尝试对广告的点击率估计要比方法1有效很多。

非平稳过程:考虑到电商这个场景，冬天展示冬季衣服，用户购买率高，夏天展示夏季衣服，购买率高，每一个展示产品的购买率是随着时间推移，变化的。抽象一下，我们的action回报率并不是一个定的参数a，而是随着时间变化的一系列参数a1,a2,...，这样来看，我们需要一直进行探索，才能够得到最优的回报。

这一类非平稳过程并不总适合Thompson Sampling，但如果参数在每一个时间段的改变很少，我们能进行比较多的测试，仍然可以有效解决该问题。最简单的方法就是只采取最近的一些数据进行建模，比方说我们可以对每一个产品计算过去一周的表现情况，来适应时间的改变。

另一种常见的做法则是进行Time Decay，方法如下图所示：

A Tutorial on Thompson Sampling

下图是多臂赌博机有两个臂的情况下，一个臂逐渐由0.1上升到0.6，另一个臂逐渐由0.9下降到0.4时候，不同的Thompson Sampling方法得到的不同结果。前期变化慢时，Time Decay的版本并没有差太多，一旦发生剧烈变化，没有适应的版本就会后悔。

上下文特征:最后想讲的一类是利用上下文特征对Thompson Sampling进行优化，这个和我们日常使用的推荐系统就非常的像了。上下文特征就是我们拥有的用户信息，环境信息以及产品信息，基于这些特征我们可以对先验进行估计，然后结合Thompson Sampling进行实验。鉴于这一部分非常重要，我们下一篇文章单独写。

增强学习版老虎机

回到一个更大的主题，我们可以用另一种增强学习的算法来解决多臂赌博机问题，那就是把每一个臂看做一个二分类问题。我们设计一个非常简单的神经网络，有K个输出节点，每一个节点的权重是选择该臂的的回报，初始时每一个臂的回报都是0。

每当我们对一个臂实施动作后，根据反馈对该臂的权重进行更新，可以应用最经典的分类loss:

我们还要引入概率epislon，进行探索，才能保证不会错过最优值:

兜兜转转，我们从Epsilon-Greedy算法深入到了最优的Thompson Sampling算法，最后又通过Policy Gradient回到了Epsilon-Greedy，对于背后概率固定的老虎机，又输给了传统做法。

这次的主题就写到这里，下次我会讲Contextual Bandits，这一与推荐系统最相关的主题。

推荐:

The Multi-Armed Bandit Problem and Its Solutions

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

一个朋友的博客，里面比较了多臂赌博机Epsilon Greedy，UCB，Bayesian UCB和Thompson Sampling算法，是我见过写的最好的博客，本文许多图片都由该文章提供的开源代码生成。

A Tutorial on Thompson Sampling

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

这篇文章从Thompson Sampling讲到实战问题，最后讲到局限性，非常推荐。

Simple Reinforcement Learning in Tensorflow: Part 1 - Two-armed Bandit

https://medium.com/@awjuliani/super-simple-reinforcement-learning-tutorial-part-1-fd544fab149

用Tensorflow解决两臂赌博机问题，其中Tensorflow的部分用到了policy gradient算法。

欢迎关注硅谷程序汪

原创文章，版权所有。