小秃科普："买定离手"，多臂老虎机问题是什么？

UgoHix

提到老虎机，你会想到什么呢？暴富？运气？失落？



今天小秃给大家介绍的是《多臂老虎机问题( multi-armed bandit)》——人工智能中强化学习算法的基础部分。

多臂老虎机是什么？

为了防止一些涉世未深的小朋友不明白什么是老虎机，也为了一些真正的老虎机玩家”误解“了我这里提到的老虎机（这里的老虎机机制比较简单，不要想太复杂），这里对多臂老虎机做一个解释。

远在澳门的小豪家里有一台多臂老虎机，这个老虎机有10个拉杆，拉下每一个拉杆，老虎机会吐出金额不定的钱。但经过小豪的精心调试，这10个拉杆中，每个拉杆吐出钱的金额是不同的，有的拉杆对应的金额大，有的拉杆吐出的金额少（例如拉杆1只能吐一元钱，拉杆2能吐10元钱）。同时，小豪为了防止玩家每个拉杆都拉一遍就知道每个拉杆能吐出多少钱，他还对机器做了一些手脚，他对机器加入了一定的随机性。这样，每个拉杆都有一个倾向，有的拉杆倾向于吐出较多的钱，有的拉杆向于吐出较少的钱，但由于随机性的存在，这种倾向需要大量的尝试才能发现。

多臂老虎机问题的相关算法能做什么？

简单说来，该算法能让我们合理地进行尝试以获得最大的收益。具体可以用在以下场景下：

1） 可应用在本文中描述的多臂老虎机问题中；

2） 可应用在推荐系统中的冷启动相关问题中；

3） 可应用在计算广告中的新广告的选取中；

都有哪些方法可以解决多臂老虎机问题？

1） ϵ−greedy

2） Thompson Sampling

2） Upper Confidence Bounds(UCB)

3） LinUCB (Linear UCB)

由于本文只是简单介绍，所以这里选取最简单的一个算法（ϵ−greedy）进行介绍：

ϵ−greedy算法介绍：

一、 两个步骤：

该算法分成探索和利用两个步骤，探索和利用步骤不断交替进行，如下：

探索->利用->探索->利用->探索->利用->.....

二、 探索和利用分别在做什么？

探索：随机地尝试多个臂，然后重新估计每个臂对应的收益的期望。具体的，可以在每次随机选择后，看看该臂有多少收益，计算这个臂的收益的平均值为多少，将这个值当做该臂的收益期望；

利用：看目前哪个臂能获取最大的期望收益，就选择该臂。具体的，看看哪个臂的平均收益最大，本次选择就选这个臂；

三、 探索和利用比例：

设置一个很小的参数ε（例如可以是0.1），该参数代表的10%的概率进行探索，90%的概率进行利用。设置成0.1意味着我能充分利用当前已有的信息，去获取当前我认为的最大收益。同时，保留一些希望，有10%的概率去探索，万一别的臂的收益更高呢，避免过于相信少部分经验，从而失去更大的可能。

注：

推荐系统：新闻推荐、商品推荐、影视剧推荐等等的推荐都属于推荐系统的一种；

冷启动：在推荐系统中，针对新用户的推荐策略，我们一般叫做冷启动。对于新用户，我们没有他们的行为以及标签数据，所以，相比老用户的推荐，冷启动是一个较难解决的问题；

计算广告：可以粗略地认为是现在互联网利用技术投放广告的方法；