---

一、多臂老虎机

假设现在有如下的老虎机，每个老虎机都是单臂的，组合在一次就称为多臂老虎机。拉下老虎机的臂，就会按照概率得到一定的奖励，且每个老虎机的概率分布都是不同的。


因此，我们需要制定一定的策略，来最大化得到的奖励。

考虑一个arm数量为K的多臂老虎机问题，重复在K个arm内进行选择，每次选择一个arm就会得到对应的reward。目标是在一段时间内最大化总收益的期望。

二、探索Exploration与利用Exploitation

以上面的概率分布为例，当我们知道老虎机的概率分布时，肯定是选择D5老虎机（因为其均值最大，且大部分数据集中在右侧），从而使收益最大。但是，我们并不能事先知道老虎机的概率分布。 因此，我们需要通过不断的尝试，才能逐渐加深对老虎机的概率分布的认识。
这里引入一个遗憾regret的概念：

遗憾regret：选择了非最佳奖励的arm导致了与最佳奖励之间的差值

我们的一次次尝试，将导致遗憾的增大，我们应该尽可能快速的找到老虎机的概率分布，来找到最佳分布的最大化收益。
这就是探索Exploration与利用Exploitation的矛盾问题。

利用是贪心的思想，在本轮老虎机挑选中，导致的遗憾虽然小，但在全局可能并不是最优的动作；
探索是在本轮选择当前并不是最优的arm，来探索可能是更优的动作。
我们可以不断的玩老虎机，从而对每个老虎机的概率分布有更好的认识，但同时也会带来很大的遗憾；但如果玩老虎机的次数不是很多，目前得到的分布与实际老虎机的分布有偏差，通过此时的概率分布的信息来进行决策，得到的策略可能不是最优的。

三、置信区间上界算法（the-upper-confidence-bound-algorithm）

置信区间:置信区间是指由样本统计量所构造的总体参数的估计区间，即每个老虎机都有一个取值区间

UCB算法是通过用每个老虎机的取值区间的上界，来代替老虎机的奖励期望进行选择，是一种乐观的算法。

这种基于置信度上界的动作选择的思想是:平方根项是对第 $j$个动作的价值估计的不确定性的度量。因此，最大值的大小是动作 $j$的可能真实值的上限。每次选 $j$ 时，不确定性可能会减小，由于 $n_j$出现在不确定项的分母上，因此随着$n_j$的增加，这一项就减小了。另一方面，每次选择 $j$之外的动作时，在分子上的$n$增大，而 $n_j$却没有变化，所以不确定性增加了，自然对数的使用意味着随着时间的推移，增加会变得越来越小，但它是无限的。所有动作最终都将被选中，但是随着时间的流逝，具有较低价值估计的动作或者已经被选择了更多次的动作被选择的频率较低。

具体的算法流程示意图如下：本部分转载自
第一步，在我们开始之前，假设每个老虎机的概率分布是相同的，即平均值或期望是相同的。如图红色虚线表示平均值或期望，纵轴表示老虎机可能带来的收益。这些彩色的横线代表每个老虎机实际的平均或期望，这些期望我们是不知道的，这个问题的核心就是我们要进行不断的尝试去估算出每个老虎机的平均期望。

对于每个老虎机，我们讲置信区间，用灰色的方框表示。对于每个老虎机，我们按下老虎机得到的奖励有很大的概率是在这个区间当中的。我们每一轮将要选择的就是拥有最大的区间上界的老虎机，也就是顶上的这条线最大的老虎机，我们要在每一轮中选择它并按下它。在第一轮中，他们的区间上界是一样的。


比如选择3号老虎机，按下去，首先会发现区间所代表的方框下降了。因为按下去后我们会发现其给予的奖励，3号老虎机的实际期望比较低，那么观察得到的奖励也是比较低，那么重新计算观察到的所有平均值时，那么这个平均值就降低了。第二点，我们会发现这个置信区间变得更小了，因为比起上一轮的游戏，我们总共的观察次数变多了，也就是信心升高了，那么这个置信区间的长度就会变小。

那么此时第三个机器的置信区间上界比其他的要低，所以下一轮要选择其他四个机器，比如选择第四个，那么它的置信区间上界会变高，区间大小会变小。

在下一步，125三个机器的上界时一样的，因此可以在他们三个中间选一个，比如第一个，它的实际平均值比较低，但当我们按下老虎机的时候，它实际是个随机事件，因此可能高也可能低。虽然它的平均值，但假设此时运气比较好，投下去的钱翻倍了，那么他的区间上限变高，长度变小。

再然后在25中间选择一个，比如第二个，此时他的置信区间上界变低，宽度变小。

那么最后按下第五个机器，这时得到一个非常高的观察值，那么上限变高，宽度变小。但由于D5实际上是最佳的机器，那么就算置信区间变小了，但它的上界依然比其他的都要高。

那么我接下来选择的老虎机依然是它，当我们选择了一个最佳的解时，我们可能在这个选择上停留很多轮，但由于对他的信心会越来越高，因此这个区间会越来越小，此时的区间上界可能就会变成不是最高。

UCB算法有一个特点，当我们选择了一个机器很多次后，他的置信区间会变得很小，要给其他的机器一些机会，看看其他机器显示的观察结果所对应的新的置信区间上界是否会更高。这样经过很多轮后，最终D5的选择次数依然会很多很多，他的置信区间会越来越扁，一直到最终轮。

四、UCB(α)的bound证明

UCB(α)算法
1.在最开始的K round内，以随机的顺序选择每个arm一次，(K是arm的数量)
2.在之后的每一轮 t 结束后，均计算每个arm的UCB(α)值，该值的公式如下：
$${\hat{\mu }}_{i,N_i(t)}+\sqrt{\frac{\alpha \log t}{2N_i(t)}}$$
在第t+1轮，即下一轮，选择对应值最大的arm，即：
$$I(t+1)\in \underset{i=1,\dots ,K}{\mathrm{argmax}}\left\{{\hat{\mu }}_{i,N_i(t)}+\sqrt{\frac{\alpha \log T}{2N_i(t)}}\right\}$$

（跟之前的形式不同只有常数因子）

定理：考虑一个多臂老虎机问题，手臂数量为K，每个老虎机的奖励服从独立同分布的伯努利 Bernoulli(${\mu }_i$) 随机变量,不同老虎机之间的奖励也是相互独立的。不是一般性，假设${\mu }_1>{\mu }_2\ge \dots \ge {\mu }_K$，对$i\ge 2$，并且令${\Delta }_i={\mu }_1-{\mu }_i$。记$R(T)$为UCB(α)算法在前T轮的遗憾，则对于$\alpha >1$，有：
$$\mathcal{R}(T)\le \sum _{i=2}^K\left(\frac{\alpha +1}{\alpha -1}{\Delta }_i+\frac{2\alpha \log T}{{\Delta }_i}\right)$$

证明：如果观察到第$s+1$轮选择的手臂为$i$，即$I_{s+1}=i$，则以下事件至少有一项为真：
$$\begin{array}{rl}{\hat{\mu }}_{1,N_1(s)}& \le {\mu }_1-\sqrt{\frac{\alpha \log s}{2N_1(s)}}（2）\\ {\hat{\mu }}_{i,N_i(s)}& >{\mu }_i+\sqrt{\frac{\alpha \log s}{2N_i(s)}}（3）\\ N_i(s)& <\frac{2\alpha \log s}{{\Delta }_i^2}（4）\end{array}$$
其中第一项表示，$arm1$的置信区间上界小于其均值；第二项表示，$armi$的置信区间下界大于其均值；第三项表示，$armi$的探索项$\sqrt{\frac{\alpha \log t}{2N_i(t)}}$大于${\Delta }_i={\mu }_1-{\mu }_i$。
反之，如果三个不等式都为假，则第$I_{s+1}$轮仍选择第1个手臂，有以下成立：
$$\begin{array}{rl}{\hat{\mu }}_{1,N_1(s)}+\sqrt{\frac{\alpha \log s}{2N_1(s)}}& >{\mu }_1\\ & ={\mu }_i+{\Delta }_i\\ & \ge {\mu }_i+\sqrt{\frac{2\alpha \log s}{N_i(s)}}\\ & \ge {\hat{\mu }}_i+\sqrt{\frac{\alpha \log s}{2N_1(s)}}\end{array}$$
现在我们用这个式子来求次优手臂选择次数$t$的上界，令：
$$u=\lceil \frac{2\alpha \log t}{{\Delta }_i^2}\rceil$$
从上面三个式子的第三个式子${\mathbb{N}}_i(s)<\frac{2\alpha \log s}{{\Delta }_i^2}$得到，因此，$armi$选择次数为：
$$N_i(t)=\sum _{s=1}^{t}1(I(s)=i)\le u+\sum _{s=1}^{t}1\left(N_i(s-1)\ge u\text{ and }I(s)=i\right)$$
（即包括满足第三个式子的情况，对应次数为u；以及不满足第三个式子的情况）


对于$s<u$的情况下，$N_i(s-1)\ge u$不可能成立，因此：
$$N_i(t)\le u+\sum _{s=u+1}^{t}1\left(N_i(s-1)\ge u\text{ and }I(s)=i\right)$$
由上面三个式子与$I_{s+1}=i$，可将上式的替换一下，其期望为：
（即原本式子第二项为事件$I_{s+1}=i$和式子（4）为假同时发生，则可认为式子（2）和式子（3）为真至少有一个发生）
$$\begin{array}{rl}\mathbb{E}\left[N_i(t)\right]& \le u+\mathbb{E}\left[\sum _{s=u+1}^{t}1(I(s)=i\text{ and ineq. (4) is false })\right]\\ & \le u+\sum _{s=u+1}^t\mathbb{E}[1(\text{ ineq. }(2)\text{ or ineq. (3) is true) }]\\ & \le u+\sum _{s=u+1}^t(\mathbb{P}(\text{ ineq. }2\text{ is true })+\mathbb{P}(\text{ ineq. }(3)\text{ is true }))\end{array}$$
接下来为该概率定界，根据霍夫丁不等式，有：
$$\mathbb{P}\left({\hat{\mu }}_{i,N_i(s)}-{\mu }_i>\sqrt{\frac{\alpha \log s}{2N_i(s)}}\right)\le e^{-\alpha \log s}=s^{-\alpha }$$
且两个事件（2）和（3）发生的概率一致，因此有:
$$\begin{array}{rl}\mathbb{E}\left[N_i(t)\right]& \le u+\sum _{s=u+1}^{t}2s^{-\alpha }\\ & \le u+{\int }_u^{\infty }2s^{-\alpha }ds\\ & \le u+\frac{2}{\alpha -1}{u}^{-\alpha +1}\\ & \le u+\frac{2}{\alpha -1}\end{array}$$
将$u$代进去，有：
$$\mathbb{E}\left[N_i(t)\right]\le \lceil \frac{2\alpha \log t}{{\Delta }_i^2}]+\frac{2}{\alpha -1}\le \frac{2\alpha \log t}{{\Delta }_i^2}+1+\frac{2}{\alpha -1}$$
最后，将每个次优手臂选择次数的期望乘上遗憾regret，并求个累和，即可得到：
$$\sum _{i=2}^K\mathbb{E}\left[N_i(t)\right]\cdot {\Delta }_i=\sum _{i=2}^K\left(\frac{\alpha +1}{\alpha -1}{\Delta }_i+\frac{2\alpha \log T}{{\Delta }_i}\right)$$

---

Lai and Robbins引理：考虑一下K arms的多臂老虎机问题，arm的reward服从伯努利分布，不同arm的reward是相互独立的。对于任何强一致的策略，一个次最优的arm在时间T被选择的次数$N_i(t)$满足：
$$\underset{T\to \infty }{\mathrm{liminf}}\frac{\mathbb{E}\left[N_i(T)\right]}{\log T}\ge \frac{1}{K\left({\mu }_i;{\mu }^{\ast }\right)}$$

因此，任意策略的下界为：
$$\underset{T\to \infty }{\mathrm{liminf}}\frac{\mathcal{R}(T)}{\log T}=\underset{T\to \infty }{\mathrm{liminf}}\frac{{\sum }_{i:{\mu }_i<{\mu }_{\ast }}\left({\mu }^{\ast }-{\mu }_i\right)\mathbb{E}\left[N_i(T)\right]}{\log T}\ge \sum _{i:{\mu }_i<{\mu }^{\ast }}\frac{{\mu }^{\ast }-{\mu }_i}{K\left({\mu }_i;{\mu }^{\ast }\right)}$$
而我们求出来的UCB算法的下界为：
$$\underset{T\to \infty }{\mathrm{limsup}}\frac{\mathcal{R}(T)}{\log T}\le \sum _{i:{\mu }_i<{\mu }^{\ast }}\frac{2}{{\mu }^{\ast }-{\mu }_i}$$
引入Pinsker’s 不等式：$$K(q;p)\ge 2(q-p{)}^2$$
可求得UCB的算法是最优下界的四倍左右，即UCB算法基本接近最优。

五、UCB仿真 代码非原创，仅供参考学习

假设有一个汽车公司为了一个车做了十个广告ad1-ad10，这个公司需要知道哪个广告投放后，点击率最高。这组数据集是在模拟环境得到的，若值为1则指的是这个用户点击了这个广告，总共10000条数据。总结一下问题就是，我们有十个广告，要决定哪个广告有最高的点击率，并对逐步得到的信息来决定，第n个用户投放哪个广告得到最高的点击数。我们先看看如果对于每一个用户，我们随机抽选广告，会得到怎样的点击数。

---

使用random选择广告

可看到随机选择，每个广告选择的量大致为1000左右，最终得到的点击率为1199。


参考代码如下：

# Importing the libraries
import matplotlib.pyplot as plt
import pandas as pd

# Importing the dataset
dataset = pd.read_csv('Ads_CTR_Optimisation.csv')

# Implementing Random Selection
import random
N = 10000
d = 10
ads_selected = []
total_reward = 0
for n in range(0, N):
    ad = random.randrange(d)
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    total_reward = total_reward + reward

# Visualising the results
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()
print("total_reward:",total_reward)

---

使用UCB算法进行挑选
UCB算法中需要计算样本均值，即每个广告的平均奖励。因此计算过程中需要统计目前为止的广告被选次数$N_i$和累计奖励$R_i$。

可看到，使用UCB选择时，广告ad5被选择的次数更多，最后得到的点击率为2178。


参考代码如下：

import matplotlib.pyplot as plt
import pandas as pd
import math

# import the dataset
dataset = pd.read_csv('Ads_CTR_Optimisation.csv')

# Implementing UCB
N = 10000
d = 10
ads_selected = []
numbers_of_selections = [0] * d
sums_of_rewards = [0] * d
total_reward = 0
for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    for i in range(0, d):
        if numbers_of_selections[i] > 0:
            average_reward = sums_of_rewards[i] / numbers_of_selections[i]
            delta_i = math.sqrt(3/2 * math.log(n + 1) / numbers_of_selections[i])
            upper_bound = average_reward + delta_i
        else:
            upper_bound = 1e400     #inf
        if upper_bound > max_upper_bound:
            max_upper_bound = upper_bound
            ad = i
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    numbers_of_selections[ad] = numbers_of_selections[ad] + 1
    sums_of_rewards[ad] = sums_of_rewards[ad] + reward
    total_reward = total_reward + reward

# Visualising the results
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()
print("total_reward:",total_reward)

总结