在多臂老虎机(multi-armed bandit,MAB)问题中,有一个拥有
K
K
K根拉杆的老虎机,拉动每一根拉杆都对应一个关于奖励的概率分布
R
R
R。我们每次拉动其中一根拉杆,就可以从该拉杆对应的奖励概率分布中获得一个奖励
r
r
r。我们在各根拉杆的奖励概率分布未知的情况下,从头开始尝试,目标是在操作
T
T
T次拉杆后获得尽可能高的累积奖励。由于奖励的概率分布是未知的,因此我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。“采用怎样的操作策略才能使获得的累积奖励最高”便是多臂老虎机问题。
在这个场景中,赌博机相当于环境,个体拉下某一单臂赌博机的拉杆表示执行了一个特定的行为,赌博机会给出一个即时奖励
R
R
R,随即该状态序结束。因此多臂赌博机中的一个完整状态序列就由一个行为和一个即时奖励构成,与状态无关。
形式化描述
多臂老虎机问题可以表示为一个元组
<
A
,
R
>
<\mathcal{A},\mathcal{R}>
<A,R>,其中:
A
\mathcal{A}
A为动作集合,其中一个动作表示拉动一个拉杆。若多臂老虎机一共有
K
K
K根拉杆,那动作空间就是集合
{
a
1
,
A
2
,
⋯
,
a
K
}
\{a_1,A_2,\cdots,a_K\}
{a1,A2,⋯,aK},我们用
a
t
∈
A
a_t\in\mathcal{A}
at∈A表示任意一个动作;
R
\mathcal{R}
R为奖励概率分布,拉动每一根拉杆的动作
a
a
a都对应一个奖励概率分布
R
(
r
∣
a
)
\mathcal{R}(r|a)
R(r∣a),不同拉杆的奖励分布通常是不同的。
假设每个时间步只能拉动一个拉杆,多臂老虎机的目标为最大化一段时间步内累积的奖励:
max
∑
t
=
1
T
r
t
,
r
t
∼
R
(
⋅
∣
a
t
)
\max \sum_{t=1}^{T} r_{t}, r_{t} \sim \mathcal{R}\left(\cdot \mid a_{t}\right)
max∑t=1Trt,rt∼R(⋅∣at) 。其中
a
t
a_t
at表示在第
t
t
t时间步拉动某一拉杆的动作,
r
t
r_t
rt表示动作
a
t
a_t
at获得的奖励。
估计期望奖励
为了方便描述问题,定义行为价值
Q
(
a
)
Q(a)
Q(a)为采取行为
a
a
a获得的奖励期望:
Q
(
a
)
=
E
[
r
∣
a
]
)
Q(a)=\mathbb{E}[r \mid a])
Q(a)=E[r∣a]) 假设能够事先知道哪一个拉杆能够给出最大即时奖励,那可以每次只选择对应的那个拉杆。如果用
V
∗
V^*
V∗表示这个最优价值,
a
∗
a^*
a∗表示能够带来最优价值的行为,那么:
V
∗
=
Q
(
a
∗
)
=
max
a
∈
A
Q
(
a
)
V^{*}=Q\left(a^{*}\right)=\max _{a \in A} Q(a)
V∗=Q(a∗)=a∈AmaxQ(a) 事实上不可能事先知道拉下哪个拉杆能带来最高奖励,因此每一次拉杆获得的即时奖励都与最优价值
V
∗
V^*
V∗存在一定的差距,定义这个差距为懊悔(regret)值:
l
t
=
E
[
V
∗
−
Q
(
a
t
)
]
l_{t}=\mathbb{E}\left[V^{*}-Q\left(a_{t}\right)\right]
lt=E[V∗−Q(at)] 每执行一次拉杆行为都会产生一个懊悔值
l
t
l_t
lt,随着拉杆行为的持续进行,将所有的懊悔值加起来,形成一个总的懊悔值:
L
t
=
E
[
∑
τ
=
1
t
(
V
∗
−
Q
(
a
τ
)
)
]
L_{t}=\mathbb{E}\left[\sum_{\tau=1}^{t}\left(V^{*}-Q\left(a_{\tau}\right)\right)\right]
Lt=E[τ=1∑t(V∗−Q(aτ))] 这样最大化累积奖励的问题就可以转化为最小化总懊悔值了。同时对分析问题较为简单、直观。上式也可用另一种方式重写。令
N
t
(
a
)
N_t(a)
Nt(a)为到
t
t
t时刻时已执行行为
a
a
a的次数,
Δ
a
\Delta_a
Δa为最优价值
V
∗
V^*
V∗与行为
a
a
a对应的价值之间的差,则总懊悔值可以表示为:
L
t
=
E
[
∑
τ
=
1
t
V
∗
−
Q
(
a
τ
)
]
=
∑
a
∈
A
E
[
N
t
(
a
)
]
(
V
∗
−
Q
(
a
)
)
=
∑
a
∈
A
E
[
N
t
(
a
)
]
Δ
a
\begin{aligned} L_{t} &=\mathbb{E}\left[\sum_{\tau=1}^{t} V^{*}-Q\left(a_{\tau}\right)\right] \\ &=\sum_{a \in A} \mathbb{E}\left[N_{t}(a)\right]\left(V^{*}-Q(a)\right) \\ &=\sum_{a \in A} \mathbb{E}\left[N_{t}(a)\right] \Delta_{a} \end{aligned}
Lt=E[τ=1∑tV∗−Q(aτ)]=a∈A∑E[Nt(a)](V∗−Q(a))=a∈A∑E[Nt(a)]Δa 把总懊悔值按行为分类统计可以看出,一个好的算法应该尽量减少执行那些价值差距较大的行为的次数。但个体无法知道这个差距具体有多少,可以使用蒙特卡罗评估来得到某行为的近似价值:
Q
^
t
(
a
)
=
1
N
t
(
a
)
∑
t
=
1
T
r
t
1
(
a
t
=
a
)
≈
Q
(
a
)
\hat{Q}_{t}(a)=\frac{1}{N_{t}(a)} \sum_{t=1}^{T} r_{t} \ 1\left(a_{t}=a\right) \approx Q(a)
Q^t(a)=Nt(a)1t=1∑Trt1(at=a)≈Q(a) 理论上
V
∗
V^*
V∗和
Q
(
a
)
Q(a)
Q(a)由环境动力学确定,因而都是静态的,随着交互次数
t
t
t的增多,可以认为蒙特卡罗评估得到的行为近似价值
Q
^
t
(
a
)
\hat Q_t(a)
Q^t(a)越来越接近真实的行为价值
Q
(
a
)
Q(a)
Q(a)。
对于
∀
a
∈
A
\forall a\in\mathcal{A}
∀a∈A,初始化计数器
N
(
a
)
=
0
N(a)=0
N(a)=0和期望奖励估值
Q
^
(
a
)
=
0
\hat Q(a)=0
Q^(a)=0
for
t
=
1
→
T
t=1\rightarrow T
t=1→Tdo
选取某根拉杆,该动作记为
a
t
a_t
at
得到奖励
r
t
r_t
rt
更新计数器:
N
(
a
t
)
=
N
(
a
t
)
+
1
N\left(a_{t}\right)=N\left(a_{t}\right)+1
N(at)=N(at)+1
更新期望奖励估值:
Q
^
(
a
t
)
=
Q
^
(
a
t
)
+
1
N
(
a
t
)
[
r
t
−
Q
^
(
a
t
)
]
\hat{Q}\left(a_{t}\right)=\hat{Q}\left(a_{t}\right)+\frac{1}{N\left(a_{t}\right)}\left[r_{t}-\hat{Q}\left(a_{t}\right)\right]
Q^(at)=Q^(at)+N(at)1[rt−Q^(at)]
end for
以上 for 循环中的第四步如此更新估值,是因为这样可以进行增量式的期望更新,公式如下。
Q
k
=
1
k
∑
i
=
1
k
r
i
=
1
k
(
r
k
+
∑
i
=
1
k
−
1
r
i
)
=
1
k
(
r
k
+
(
k
−
1
)
Q
k
−
1
)
=
1
k
(
r
k
+
k
Q
k
−
1
−
Q
k
−
1
)
=
Q
k
−
1
+
1
k
[
r
k
−
Q
k
−
1
]
\begin{aligned} Q_{k} &=\frac{1}{k} \sum_{i=1}^{k} r_{i} \\ &=\frac{1}{k}\left(r_{k}+\sum_{i=1}^{k-1} r_{i}\right) \\ &=\frac{1}{k}\left(r_{k}+(k-1) Q_{k-1}\right) \\ &=\frac{1}{k}\left(r_{k}+k Q_{k-1}-Q_{k-1}\right) \\ &=Q_{k-1}+\frac{1}{k}\left[r_{k}-Q_{k-1}\right] \end{aligned}
Qk=k1i=1∑kri=k1(rk+i=1∑k−1ri)=k1(rk+(k−1)Qk−1)=k1(rk+kQk−1−Qk−1)=Qk−1+k1[rk−Qk−1] 这样做是因为:如果将所有数求和再除以次数,其缺点是每次更新的时间复杂度和空间复杂度均为
O
(
n
)
O(n)
O(n)。而采用增量式更新,时间复杂度和空间复杂度均为
O
(
1
)
O(1)
O(1)。
设想这样一种情况:对于一台双臂老虎机,其中第一根拉杆只被拉动过一次,得到的奖励为0;第二根拉杆被拉动过很多次,我们对它的奖励分布已经有了大致的把握。这时你会怎么做?或许你会进一步尝试拉动第一根拉杆,从而更加确定其奖励分布。这种思路主要是基于不确定性,因为此时第一根拉杆只被拉动过一次,它的不确定性很高。一根拉杆的不确定性越大,它就越具有探索的价值,因为探索之后我们可能发现它的期望奖励很大。我们在此引入不确定性度量
U
(
a
)
U(a)
U(a),它会随着一个动作被尝试次数的增加而减小。我们可以使用一种基于不确定性的策略来综合考虑现有的期望奖励估值和不确定性,其核心问题是如何估计不确定性。
上置信界(upper confidence bound,UCB)算法是一种经典的基于不确定性的策略算法,它的思想用到了一个非常著名的数学原理:霍夫丁不等式(Hoeffding’s inequality)。在霍夫丁不等式中,令
X
1
,
⋯
,
X
n
X_1,\cdots,X_n
X1,⋯,Xn为
n
n
n个独立同分布的随机变量,取值范围为
[
0
,
1
]
[0,1]
[0,1],其经验期望为
x
ˉ
n
=
1
n
∑
j
=
1
n
X
j
\bar x_n=\frac{1}{n}\sum_{j=1}^{n}X_j
xˉn=n1∑j=1nXj,则有
P
{
E
[
X
]
≥
x
ˉ
t
+
u
}
≤
e
−
2
n
u
2
\mathbb{P}\left\{\mathbb{E}[X] \geq \bar{x}_{t}+u\right\} \leq e^{-2 n u^{2}}
P{E[X]≥xˉt+u}≤e−2nu2 现在我们将霍夫丁不等式运用于多臂老虎机问题中。将
Q
^
t
(
a
)
\hat Q_t(a)
Q^t(a)代入
x
ˉ
t
\bar x_t
xˉt,不等式中的参数
u
=
U
^
t
(
a
)
u=\hat U_t(a)
u=U^t(a)代表不确定性度量。给定一个概率
p
=
e
−
2
N
t
(
a
)
U
a
(
a
)
2
p=e^{-2N_t(a)U_a(a)^2}
p=e−2Nt(a)Ua(a)2 根据上述不等式,
Q
t
(
a
)
<
Q
^
t
(
a
)
+
U
^
t
(
a
)
Q_{t}(a)<\hat{Q}_{t}(a)+\hat{U}_{t}(a)
Qt(a)<Q^t(a)+U^t(a)至少以概率
1
−
p
1-p
1−p成立。当
p
p
p很小时,
Q
t
(
a
)
<
Q
^
t
(
a
)
+
U
^
t
(
a
)
Q_{t}(a)<\hat{Q}_{t}(a)+\hat{U}_{t}(a)
Qt(a)<Q^t(a)+U^t(a)就以很大概率成立,
Q
^
t
(
a
)
+
U
^
t
(
a
)
\hat{Q}_{t}(a)+\hat{U}_{t}(a)
Q^t(a)+U^t(a)便是期望奖励上界。此时,上置信界算法便选取期望奖励上界最大的动作,即
a
=
argmax
a
∈
A
[
Q
^
(
a
)
+
U
^
(
a
)
]
a=\underset{a \in \mathcal{A}}{\operatorname{argmax}}[\hat{Q}(a)+\hat{U}(a)]
a=a∈Aargmax[Q^(a)+U^(a)]
那其中
U
^
t
(
a
)
\hat U_t(a)
U^t(a)具体是什么呢?根据等式
e
−
2
N
t
(
a
)
U
a
(
a
)
2
e^{-2N_t(a)U_a(a)^2}
e−2Nt(a)Ua(a)2,解之即得
U
^
t
(
a
)
=
−
log
p
2
N
t
(
a
)
\hat{U}_{t}(a)=\sqrt{\frac{-\log p}{2 N_{t}(a)}}
U^t(a)=2Nt(a)−logp
因此,设定一个概率
p
p
p后,就可以计算相应的不确定性度量
U
^
t
(
a
)
\hat U_t(a)
U^t(a)了。更直观地说,UCB 算法在每次选择拉杆前,先估计每根拉杆的期望奖励的上界,使得拉动每根拉杆的期望奖励只有一个较小的概率
p
p
p超过这个上界,接着选出期望奖励上界最大的拉杆,从而选择最有可能获得最大期望奖励的拉杆。
不确定性度量
U
^
t
(
a
)
\hat U_t(a)
U^t(a)的理解:如果一个行动被选择次数越多意味着它的行动价值估计的确定性就越小,比如说,如果某个行动被选择次数还是0的话,那就意味着该行动在exploring中应该以最高优先度被选择。
代码实现:在具体的实现过程中,设置
p
=
1
t
p=\frac{1}{t}
p=t1,并且在分母中为拉动每根拉杆的次数加上常数 1,以免出现分母为 0 的情形,即此时
U
^
t
(
a
)
=
log
t
2
(
N
t
(
a
)
+
1
)
\hat{U}_{t}(a)=\sqrt{\frac{\log t}{2\left(N_{t}(a)+1\right)}}
U^t(a)=2(Nt(a)+1)logt
同时,我们设定一个系数
c
c
c来控制不确定性的比重,此时
a
=
arg
max
a
∈
A
Q
^
(
a
)
+
c
⋅
U
^
(
a
)
0
a=\arg \max _{a \in \mathcal{A}} \hat{Q}(a)+c \cdot \hat{U}(a)_{0}
a=arga∈AmaxQ^(a)+c⋅U^(a)0
MAB 中还有一种经典算法——汤普森采样(Thompson sampling),先假设拉动每根拉杆的奖励服从一个特定的概率分布,然后根据拉动每根拉杆的期望奖励来进行选择。但是由于计算所有拉杆的期望奖励的代价比较高,汤普森采样算法使用采样的方式,即根据当前每个动作
a
a
a的奖励概率分布进行一轮采样,得到一组各根拉杆的奖励样本,再选择样本中奖励最大的动作。可以看出,汤普森采样是一种计算所有拉杆的最高奖励概率的蒙特卡洛采样方法。
了解了汤普森采样算法的基本思路后,我们需要解决另一个问题:怎样得到当前每个动作
a
a
a的奖励概率分布并且在过程中进行更新?在实际情况中,我们通常用Beta分布对当前每个动作的奖励概率分布进行建模。具体来说,若某拉杆被选择了
k
k
k次,其中
m
1
m_1
m1次奖励为 1,
m
2
m_2
m2次奖励为 0,则该拉杆的奖励服从参数为
(
m
1
+
1
,
m
2
+
1
)
(m_1+1, m_2+1)
(m1+1,m2+1)的 Beta 分布。
Beta分布特点:
a+b的值越大,分布曲线越窄,分布越集中,产生的随机数越靠近中心位置。
a/(a+b)的值越大,分布的中心位置越靠近1,否则越靠近0。这样产生的随机数也更容易靠近1或0。
汤普森采样的背后原理就是Beta分布,你把贝塔分布的 a 参数看成是每根拉杆奖励为1的次数,把分布的 b 参数看成是每根拉杆奖励为0的次数,则汤普森采样过程如下: