多臂老虎机（Multi-armed Bandit）

增强学习(Reinforcement Learning)

· 算法,知识

问题描述与定义

一个赌徒，要去摇老虎机，走进赌场发现一台老虎机，老虎机拥有很多个摇臂而且各臂的外表一模一样。每次投一个币就能获得一次摇臂的机会，而且每个摇臂按下都有可能获得硬币----但是

每个臂吐出硬币的概率分布是未知的。赌徒自然想最大化收益（累积N次的收入和），应该采取怎样的行动？

这就是多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB)。

在有些情况也叫做充资源分配问题

（Sequential resource allocation problem)　　

MAB 问题简介

先来介绍下 MAB（Multi-armed bandit problem，多臂赌博机）问题，有一个赌博机，一共有 k 个摇臂，玩家每次投一个游戏币后可以按一个摇臂，每个摇臂按下后都有可能吐出硬币作为奖励，但是每个摇臂吐出硬币的概率分布是未知的，玩家的目标是获得最大化的累积奖赏。

有选择的去调整策略： MAB 中的每个摇臂都是一个选项，因此它是一个有条件的选择问题，目标是获得最大化的累积奖赏，限制是已有的选择分支。

结合阅读：推荐系统的EE问题

推荐系统中也存在很多类似于 MAB 的问题，它们叫做 EE（exploit－explore）问题：

* exploit 采矿挖掘的意思，利用已知的比较确定的用户的兴趣，然后推荐与之相关的内容；

* explore 则是探索，比如说当我表达了我喜欢历史的特征后，为了避免来回给我推荐历史话题，对于其他话题也进行了推荐，否则推荐出的结果来来回回都是中国历史...

问题边界--关于选择

1. 一个用户拥有各种各样的兴趣偏好──以我个人为例，喜欢军事、历史、文化、游戏...... 那么当我初次来到一个电商平台时，推荐系统怎么快速地知道我对每类内容的感兴趣的差异？这是一个cold start 问题。

2. 假设我们有若干种投放广告素材，怎么知道该给每个用户展示何种类型的广告从而得到最大的收益（点击率，转化率）？

3. 算法工程师提出了新的模型，除了A/B test有没有更快的方法知道它是有效的？

4. ...

全都是关于选择的问题。多臂赌博机恰恰是用来解决选择的模型。

Bandit算法

Bandit算法是指一类算法。要比较不同Bandit算法的优劣，可以用累积遗憾这个概念来衡量。

它顾名思义，是指T次选择，将每次选择的实际收益 WB_i与此次选择如果选择最好的策略带来的最大收益之差，将T次差的加总就得到了累积遗憾。

假设用最简单的伯努利实验来模拟这个过程：我们有K个选择，其中每次选择时最优收益是1，其余非优收益为0. 我们进行了T次选择，则最差的情况下我们的累积遗憾就是T，而最好情况是每次选择都是1，遗憾为0.

几种Bandit算法

Thompson sampling

原理：假设每个臂是否产生收益，服从概率分布，产生收益的概率为p。

不断试验，得到一个置信度较高的概率p的概率分布，就能近似解决这个问题了。

如何估计概率p的概率分布？

答案是假设概率p的分布符合 beta分布 ~~ beta(wins, loses) 参数wins, loses

每个臂都对应着一组beta分布的参数。每次试验后，选中一个摇臂，有收益则该臂的wins+1，否则 loses+1。

选择摇臂的方式是：用每个臂现有beta分布产生一个随机数b，选择所有臂产生的随机数中最大的摇臂去展开策略。

以上是Thompson采样，在Python环境中的实现如下：

import numpy as np

choice = np.argmax(pymc.rbeta(1+self.wins, 1+self.trals-self.wins))

UCB算法（Upper Confidence Bound)

译为置信区间上界。原理如下：

先对每个摇臂都试验一遍。之后每次选择以下值最大的那个。

其中， x_j(t) 表示这个臂到目前的收益均值（获益水平的期望），后面一项叫做 bonus，本质是均值的标准差， t 为目前的试验次数 - trials, T_j,t 是这个臂被试次数（备注，这里为了避免一次都没有试过，可以考虑进行Laplace平滑处理，即对 T_j,t +1处理。

Epsilon-Greedy算法

初始化选择一个（0， 1）之间较小的正数， epsilon。

每次以 (0, epsilon )均分分布产生一个比epsilon小的数，选择所有臂中随机选一个，否则选择截止当前平均收益最大的那个臂。

Epsilon-Greedy 是看上去非常简单直接的算法。通过控制epsilon的值控制对 Exploit和Explore的偏好程度。

越接近0，越保守，反之越激进。

朴素算法

比较简单，非常容易实现。每个臂有了均值后，一直选择均值最大的那个。

这个算法是在实际中最容易想到的。比随机乱猜要好。

以上几种算法思路的模拟表现（次数10000次）

Bandit算法的思路：

小心尝试，如果某次选择得到了比较好的结果，那么就多选择它，越确定某个选择会导致差的结果，就少选择它。如果某个选择实验次数少，导致不确定好坏，就多给它一些被选择的机会，直到确定它是金子还是石头，把每次选择的机会给“确定效果还不错”或者是“不知道好坏的”的臂。

Bandit算法的环境因素：

臂每次选择的项。

回报每个臂之后的奖励（收益函数）

外部条件决定每个臂有何差异的环境变量。

对于推荐系统，就是臂--具体物品或类别，也可以是某种推荐算法。

回报：用户对推荐的结果的满意程度（点击？跳转？ etc）

环境：给当前用户推荐时所有周边环境。

Bandit算法要注意的问题

优质的交互项（诱导用户的交互行为）
用户数量不能过小（用户间的影响，行为基数）

如果平台中交互物品的质量水平差异明显，而且物品数量还较多，在资源位有限的情况下，用户尽快看到优质物品的机会不高，因为这时的推荐系统对大多数物品还是持不确定的态度，需要更多的Explore。

用户数量如果过小，导致用户与物品的交互行为少，那么算法则不能快速收殓。

而且在很多场景下，新入平台的用户很大程度上看到内容是会是平台老用户的历史沉淀所看到的结果。

参考阅读

https://zhuanlan.zhihu.com/p/21388070
https://cloud.tencent.com/developer/article/1164110