Exploration and Exploitation(探索与开发)是计算广告和推荐系统里常见的一个问题，在数学领域也被称为多臂赌博机问题(multi-armed bandit problem), 最早是从赌场上演化而来。

1. 问题复现

有一个赌徒在一排老虎机面前决定拉动其中某一个老虎机的臂(arm)，用以期望获取的收益最高。当他在拉老虎机臂的时候，他并不知道哪一个老虎机赢钱的机率是最大的，以及他手头只有有限的money，

每玩一次都是有成本的，会损失一部分的本金。那么为了收益最高这个目标，该执行什么样的策略?

对应计算广告里的问题：假设资源池有若干广告（或若干类item），怎么知道该给每个用户展示哪个（类），从而获得最大的点击？是每次都挑效果最好那个么？那么新广告如何才有出头之日？

2. 名词解释

Exploitation: 开发利用, 选择执行目前已知最好的item，也就是回报概率最大的item

优点: 短期回报会比较高，充分利用已知回报率最高的item
缺点: 容易陷入局部最优，潜在可能存在回报率更高的item，只是不知道是哪个

Exploration: 探索，探索发现潜在可能回报率更高的item

优点: 能够发现回报率更高的item
缺点: 没有充分利用已知的信息，探索的过程会降低当前收益

3. 评估指标

多臂(arm)问题里有一个概念叫做累计遗憾(regret)，公式如下:

image.png

这里 t 表示轮数,at* 表示第t轮最优的那个arm, r表示回报

每次都会计算当前选择的arm获取的收益与最优arm期望最大收益之间的差距，把每次差距累加起来就是总的遗憾。

对应同样的问题，采用不同bandit算法来进行实验相同的次数，那么看哪个算法的总regret增长最慢，那么哪个算法的效果就是比较好的。

4. Bandit算法介绍

4.1 Epsilon-Greedy算法

4.1.1 算法过程描述

选一个(0,1)之间较小的数epsilon
每次以概率epsilon（产生一个[0,1]之间的随机数，比epsilon小）做一件事：所有臂中随机选一个。否则，选择截止当前，平均收益最大的那个臂。
根据选择臂的回报值来对回报期望进行更新

这里epsilon的值可以控制对exploit和explore的偏好程度，每次决策以概率ε去勘探Exploration，1-ε的概率来开发Exploitation，基于选择的item及回报，更新item的回报期望。

4.1.2 优点

能够应对变化：如果item的回报发生变化，能及时改变策略，避免卡在次优状态
可以控制对Exploration和Exploitation的偏好程度：ε大，模型具有更大的灵活性（能更快的探索潜在可能高回报item，适应变化，收敛速度更快），ε小，模型具有更好的稳定性（更多的机会用来开发利用当前最好回报的item），收敛速度变慢

4.1.3 缺点

设置最好的ε比较困难，大则适应变化较快，但长期累积回报低，小则适应变好的能力不够，但能获取更好的长期回报。
策略运行一段时间后，我们已经对各item有了一定程度了解，但没用利用这些信息，仍然不做任何区分地随机exploration

4.2 UCB算法(Upper Confidence Bound 置信区间上界)

4.2.1 算法过程描述

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

image.png

其中加号前面是这个臂到目前的收益均值，后面的叫做bonus，本质上是均值的标准差，t是目前的试验次数，Tjt是当前这个臂被试过的次数。
更新选择臂的收益均值

这个公式反映：均值越大，标准差越小，被选中的概率会越来越大，起到了exploit的作用；同时哪些被选次数较少的臂也会得到试验机会，起到了explore的作用。

4.2.2 优点

考虑了回报均值的不确定性，让新的item更快得到尝试机会，将探索+开发融为一体
基础的UCB算法不需要任何参数，因此不需要考虑如何验证参数（ε如何确定）的问题

4.2.3 缺点

UCB1算法需要首先尝试一遍所有item，因此当item数量很多时是一个问题
一开始各item选择次数都比较少，导致得到的回报波动较大（经常选中实际比较差的item）

4.3 Thompson sampling算法

4.3.1 算法过程描述

假设每个臂的背后都有一个概率分布来产生回报，我们要做的就是通过实验来估算出每个臂背后的概率分布p.
估算的方法为:假设概率分布服从Beta(win, lose)分布, 每个臂都有对应的这么一组参数，当实验过程中摇动臂的时候，有收益那么给win加1，如果没有收益那么给lose加1，从而估算出概率p的分布。
得到p的分布以后，通过这个概率分布p来选择臂，具体的方法如下: 用每个臂现有的beta分布产生一个随机数b，选择所有臂产生的随机数中最大的那个臂去摇。

4.3.2 优点

UCB采用确定的选择策略，可能导致每次返回结果相同（不是推荐想要的），Thompson Sampling则是随机化策略。
Thompson sampling实现相对更简单，UCB计算量更大（可能需要离线/异步计算）
在计算机广告、文章推荐领域，效果与UCB不相上下或更好competitive to or better
对于数据延迟反馈、批量数据反馈更加稳健robust

5. 效果比对