问题描述与定义
一个赌徒,要去摇老虎机,走进赌场发现一台老虎机,老虎机拥有很多个摇臂而且各臂的外表一模一样。每次投一个币就能获得一次摇臂的机会,而且每个摇臂按下都有可能获得硬币----但是
每个臂吐出硬币的概率分布是未知的。赌徒自然想最大化收益(累积N次的收入和),应该采取怎样的行动?
这就是多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB)。
在有些情况也叫做充资源分配问题
(Sequential resource allocation problem)
先来介绍下 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算法要注意的问题
参考阅读
Almost done…
We just sent you an email. Please click the link in the email to confirm your subscription!