多臂老虎机

References

《强化学习》，第2章

多臂赌博机 (Multi-armed Bandit)

The Multi-Armed Bandit Problem and Its Solutions

什么是老虎机

老虎机 -维基百科

Slot machine / One-armed bandit

老虎机是一个概率赌博机器。每次试验按照某种概率分布随机产生一个图案组合，若符合特定组合则中奖。早期老虎机采用铁铸机身、机械转轴和摇杆等原始设计，现代老虎机则利用伪随机数据产生器来运行，逐渐演化为一种电子游戏。

多臂老虎机 Multi-Armed Bandit(MAP)

Multi-Armed Bandit : Data Science Concepts (ritvikmath’s video is awesome

多臂老虎机可以简单地理解为“多个老虎机”，多个未知分布的老虎机，参与者在不断试验的过程中，逐渐探索到各个老虎机的概率分布，并要尽可能使得总的期望收益最大。

从更广义的意义上来看，多臂老虎机实际反映了一种决策模型：当一个人面临诸多选择时，如何最快地得到最优策略。比如，医疗上药物试验要选取效果最好的试验药，网络路由要选取最好的路径，在线广告投放要选取价值最匹配的广告，各种游戏中也涉及到策略的选择……

多臂老虎机的两个核心策略：

• Exploration
  • 不断在所有老虎机上试验，确定它们的分布规律
• Exploitation
  • 找到感觉收益大的某个老虎机，专注于获取收益

由此引出了两个naive的策略……Explore-only 和 Exploit-only。

Explore-only

Explore-only就是纯粹的随机选择，对各个老虎机没有任何偏好。所以Explore-only策略的收益将会是所有老虎机的期望的平均值。一般将Explore-only策略视作Baseline。

Regret ($\rho$)：Regret 遗憾用于衡量一个策略的总收益与最佳收益之间的差距。

$$\text{Regret} = \text{Best Reward} - \text{Current Reward}$$

MAP的收益是有上界的，上界所代表的就是最佳收益。

我们的目标是：maxmize Reward，或等价地，minimize Regret。

Exploit-only

Exploit-only策略是先Explore采样每个老虎机1次，然后选定表现最好的老虎机，将接下来所有的试验都放到该老虎机上。

从概率意义上而言，Exploit-only加入了人为的优选环节，因次期望得到的策略比完全随机要好，其表现将比Explore-only要好一些。下面是一个简单的测试程序来验证上述推断的合理性：

# 均值和方差
a1, a2 = 10, 2.5
b1, b2 = 8, 2
c1, c2 = 5, 12.5

# Explore-only
import random
ans, times = 0, 1000
for j in range(times):
    ret = 0
    for i in range(300):
        t = random.randint(0, 2)
        if t == 0:
            a = a1 + random.uniform(-a2, a2)
            ret += a
        if t == 1:
            b = b1 + random.uniform(-b2, b2)
            ret += b
        if t == 2:
            c = c1 + random.uniform(-c2, c2)
            ret += c
    ans += ret
print("Explore-only Regret:", 3000 - ans/times)

# Exploit-only
ans, times = 0, 1000
for j in range(times):
    ret = 0
    a = a1 + random.uniform(-a2, a2)
    b = b1 + random.uniform(-b2, b2)
    c = c1 + random.uniform(-c2, c2)
    maxi = max(a, b, c)
    if maxi == a:
        for i in range(297):
            ret += a1 + random.uniform(-a2, a2)
    if maxi == b:
        for i in range(297):
            ret += b1 + random.uniform(-b2, b2)
    if maxi == c:
        for i in range(297):
            ret += c1 + random.uniform(-c2, c2)
    ans += ret + a + b + c
print("Exploit-only Regret:", 3000 - ans/times)

输出结果：（上述数据来源于视频中，但Exploit-only Regret部分计算得到的结果与视频中的≈300不符）

Explore-only Regret: 699.736049747195
Exploit-only Regret: 507.8104310726417

可以看到Exploit-only策略的Regret确实要更小一些。若老虎机的方差越小，则Exploit-only策略的优势越明显。

Greedy Method

$$\begin{equation} Q_{t}(a) \doteq \frac{\text { sum of rewards when } a \text { taken prior to } t}{\text { number of times } a \text { taken prior to } t}=\frac{\sum_{i=1}^{t-1} R_{i} \cdot \mathbb{1}_{A_{i}=a}}{\sum_{i=1}^{t-1} \mathbb{1}_{A_{i}=a}} \end{equation}$$

Greedy Method即贪心策略，每次选取当前历史测量均值最高的老虎机$r’$，作为Exploit的对象。与Exploit-only策略的区别在于，在不断试验的过程中，不同老虎机的优先级可能会发生变化。一些实际均值较低但初始测量值较高的老虎机，其历史测量均值会逐渐变小。

但是Greedy Method容易收敛到suboptimal actions（次优解）。这是因为，一旦最优策略的首次测量偏低，那么之后便有极大概率不会再被采样。

$\epsilon$-greedy 策略

实际中常常需要权衡Exploration和Exploitation的占比（$\epsilon$），这样的混合策略被称为 $\epsilon$-greedy 策略。即，每轮都有 $\epsilon$ 的概率从Exploration或Exploitation中挑选一种策略。

$\epsilon$-greedy 策略的表现比Explore-only或Exploit-only更好。

下图是《强化学习》书中的一个试验，对10-arm老虎机进行大量统计实验后等到的结果：

值得注意的是，上图中没有反应的是$\epsilon=0.01$策略虽然增长缓慢，但是时间步数足够大之后获得的收益却会优于$\epsilon=0.1$的策略。这是因为$\epsilon=0.1$作为固定值，在大后期算法找到了最优老虎机后，反而变成了累赘。一个解决办法是，让 $\epsilon$ 的值随时间不断减少。

Incremental Implementation

计算历史测量均值：

$$\begin{equation} Q_{n} \doteq \frac{R_{1}+R_{2}+\cdots+R_{n-1}}{n-1} \end{equation}$$

这种方法需要记录历史测量值。有额外时空复杂度。

就地算法：（增量）

$$\begin{equation} \begin{aligned} Q_{n+1} &=\frac{1}{n} \sum_{i=1}^{n} R_{i} \\ &=\frac{1}{n}\left(R_{n}+\sum_{i=1}^{n-1} R_{i}\right) \\ &=\frac{1}{n}\left(R_{n}+(n-1) \frac{1}{n-1} \sum_{i=1}^{n-1} R_{i}\right) \\ &=\frac{1}{n}\left(R_{n}+(n-1) Q_{n}\right) \\ &=\frac{1}{n}\left(R_{n}+n Q_{n}-Q_{n}\right) \\ &=Q_{n}+\frac{1}{n}\left[R_{n}-Q_{n}\right] \end{aligned} \end{equation}$$

这样，算法不需要任何额外空间。

Nonstationary Problem

如果问题本身是非稳态的，比如，老虎机可能发生折旧从而其概率分布发生变化，那么新的试验结果应该占得更大比重。我们引入常量 $\alpha$ 代替原有的 $\cfrac{1}{n}$。

$$\begin{equation} Q_{n+1} \doteq Q_{n}+{\color{red}{\alpha} }\left[R_{n}-Q_{n}\right]\;\;,\;\;\alpha \in(0,1] \end{equation}$$

若展开，可得

$$\begin{equation} \begin{aligned} Q_{n+1} &=Q_{n}+\alpha\left[R_{n}-Q_{n}\right] \\ &=\alpha R_{n}+(1-\alpha) Q_{n} \\ &=\alpha R_{n}+(1-\alpha)\left[\alpha R_{n-1}+(1-\alpha) Q_{n-1}\right] \\ &=\alpha R_{n}+(1-\alpha) \alpha R_{n-1}+(1-\alpha)^{2} Q_{n-1} \\ &=\alpha R_{n}+(1-\alpha) \alpha R_{n-1}+(1-\alpha)^{2} \alpha R_{n-2}+\\ & \cdots+(1-\alpha)^{n-1} \alpha R_{1}+(1-\alpha)^{n} Q_{1} \\ &={\color{red}{(1-\alpha)^{n} } } Q_{1}+\sum_{i=1}^{n} \alpha{\color{red}{(1-\alpha)^{n-i} } }R_{i} \end{aligned} \end{equation}$$

可以看到，这样的处理实现了指数级的权重衰减。

另外，$Q_n$的收敛性有两个条件：

$$\begin{equation} \sum_{n=1}^{\infty} \alpha_{n}(a)=\infty \quad \text { and } \quad \sum_{n=1}^{\infty} \alpha_{n}^{2}(a)<\infty \end{equation}$$

当 $\alpha_{n}=\cfrac{1}{n}$ 时，$Q_n$ 收敛；当 $\alpha_{n}= \text{const.}$ 时，$Q_n$ 并不收敛，它反映了最近的Reward情况。

Optimistic Initial Values

之前我们对于每个老虎机的初始期望值 $Q_1$ 都简单地设置为0。一个较高的初始值能够增进Exploration，从而使得对所有老虎机的测试在前期就比较充分，因而可以更快找到最优策略。

因此，一定的乐观估计对于整个问题的收敛是有帮助的。

Zero Regret 平均遗憾*

$$\cfrac{\rho}{T}\longrightarrow 0 \;\;\;(\text{as}\;\;\;T\longrightarrow\infty)$$

$\cfrac{\rho}{T}$ 反应了时间上的平均遗憾。初期，因为缺少信息，与最佳收益相差大，所以遗憾较大；随着不断Exploration，多臂老虎机的分布被逐渐了解，所以策略选择上产生的遗憾变小，越来越接近最优策略。$\cfrac{\rho}{T}$ 平均遗憾也逐渐趋于0。

UCB策略

Best Multi-Armed Bandit Strategy? (feat: UCB Method)

Link to Hoffding’s Inequality: https://lilianweng.github.io/lil-log/…

UCB1（Upper Confidence Bound）策略选取老虎机的方式根据：

$$\begin{equation} {\color{blue}{\hat{\mu}_{r} } }+{\color{red}{\sqrt{\frac{2 l_{n}(t)}{ {\color{green} { {N_{t}(r)} } } } } } } \end{equation}$$

左边的${\color{blue}{\hat{\mu}_{r} } }$代表着老虎机$r$的历史测量均值，${\color{red}{\sqrt{\cfrac{2 l_{n}(t)}{ {\color{green} {…} } } } } }$代表当前时间步数的自然对数，${\color{green} { {N_{t}(r)} } }$代表老虎机$r$的已测量次数。该方式可以动态权衡Exploration和Exploitation。

${\color{red}{\sqrt{\frac{2 l_{n}(t)}{ {\color{green} { {N_{t}(r)} } } } } } }$可由Hoeffding’s Inequality推导得到。

https://wp.nyu.edu/kexinhuang/2018/08/20/hoeffdings/

https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html

从式中可以看出，测量次数越少的老虎机，其优先级相对更高。

---

UCB的通用形式：（UCB1就是$c=1$的情形）

$$\begin{equation} A_{t} \doteq \underset{a}{\arg \max }\left[Q_{t}(a)+c \sqrt{\frac{\ln t}{N_{t}(a)}}\right] \end{equation}$$

梯度老虎机 Gradient Bandit

和之前的方法不同，Gradient Bandit根据 preference 来选择老虎机，记为 $H_t(a)$。

$$\begin{equation} \operatorname{Pr}\left\{A_{t}=a\right\} \doteq \frac{e^{H_{t}(a)}}{\sum_{b=1}^{k} e^{H_{t}(b)}} \doteq \pi_{t}(a) \end{equation}$$

根据 $H_t(a)$ 做一个 softmax 以后，就得到了 $\pi_{t}(a)$，也就是每个老虎机的选取概率。我们每次试验就根据 $\pi_{t}(a)$ 来随机抽样，试验完成以后根据结果更新相应的 $H_t(a)$（这里采用了类似SGD的更新思想，因此叫做梯度老虎机，具体的梯度推导证明参考《强化学习》相关章节）。

$$\begin{equation} \begin{aligned} H_{t+1}\left(A_{t}\right) & \doteq H_{t}\left(A_{t}\right)+\alpha{\color{red}{\left(R_{t}-\bar{R}_{t}\right)} }\left(1-\pi_{t}\left(A_{t}\right)\right), & & \text { and } \\ H_{t+1}(a) & \doteq H_{t}(a)-\alpha\left(R_{t}-\bar{R}_{t}\right) \pi_{t}(a), & & \text { for all } a \neq A_{t} \end{aligned} \end{equation}$$

$R_{t}$ 代表当前步的 Reward，$\bar{R}_{t}$ 代表之前所有步的平均 Reward。$\left(R_{t}-\bar{R}_{t}\right)$ 项的正负号比较关键。

上下文老虎机 Contextual Bandits / Associative Search

强化学习中常常面临的是多环境、多策略。想象你面临着多个MAB模型，每次你将面对一个随机的MAB模型（从所有模型中抽取）。你既需要识别是哪个MAB模型，也需要在对应的MAB模型下选择最优的策略。

这就是Associative Search，即Contextual Bandits。

---

相关文章

• 人工智能的数学
• 机器学习理论
• 阅《Dark, Beyond Deep: A Paradigm Shift to Cognitive AI with Humanlike Common Sense》
• 认知图谱探知
• 阅《Bandit Learning with Implicit Feedback》