思维之海

——在云端,寻找我的星匙。

多臂老虎机

References

《强化学习》,第2章

多臂赌博机 (Multi-armed Bandit)

The Multi-Armed Bandit Problem and Its Solutions

什么是老虎机

老虎机 -维基百科

Slot machine / One-armed bandit

13 Solutions to Multi-Arm Bandit Problem for Non-Mathematicians | by Jae  Duk Seo | Towards Data Science

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

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

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

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

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

Multi-Armed Bandit — AB Experimentation 2.0 | by Rajat Jain | 1mg  Technology | Feb, 2021 | Medium

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

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

由此引出了两个naive的策略……Explore-onlyExploit-only

Explore-only

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

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

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

我们的目标是:maxmize Reward,或等价地,minimize Regret

Exploit-only

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 均值和方差
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不符)

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

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

Greedy Method

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

计算历史测量均值:

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

就地算法:(增量)

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

Nonstationary Problem

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

若展开,可得

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

另外,$Q_n$的收敛性有两个条件:

当 $\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}$ 反应了时间上的平均遗憾。初期,因为缺少信息,与最佳收益相差大,所以遗憾较大;随着不断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)策略选取老虎机的方式根据:

左边的${\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$的情形)

梯度老虎机 Gradient Bandit

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

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

$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。