多臂老虎机

多臂老虎机： Multi-Armed Bandit： MAB

该项目完整代码可见：【强化学习】多臂老虎机，喜欢就来Fork一下，然后运行体验吧。

1.前言

之前在与学长的课题讨论中，学长用到了多臂老虎机，尽管学长给我讲了一通，但其实我没听懂，哈哈哈。今天来细致学一哈什么是多臂老虎机以及如何实现多臂老虎机。

2.问题介绍

2.1 简介

• 与强化学习不同，多臂老虎机不存在状态信息，只有动作和奖励，算是最简单的和环境交互中的学习的一种形式。
• 多臂老虎机中的探索与利用（exploration vs. exploitation）问题一直以来都是一个特别经典的问题。

2.2 问题定义

• 背景：在一个拥有k根拉杆的老虎机中，每根拉杆都对应一个关于奖励的概率分布R.我们每拉动一根拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励r。
• 目标：我们在各根拉杆的奖励概率分布未知的情况下，从0开始尝试，目标是在T次拉杆后获得尽可能高的累计奖。
• 难点：在“探索拉杆的获奖概率”和“根据经验选择目前获得奖最多的拉杆”中平衡，因此，多臂老虎机问题就是研究“采用怎么样的操作策略才能获得最大的累计奖励”。

2.3 形式化描述

多臂老虎机问题可以表示为一个元组,其中：

• A为动作集合，其中一个动作表示拉动一个拉杆。若多臂老虎机一共有K根拉杆，那动作空间就是集合{a₁ ,a₂ ,……,a_k},用a_t $\in$ A表示任意一个动作。
• R为奖励概率分布，拉动每一根拉杆的动作a都对应一个奖励概率分布R(r|a),不同拉杆的奖励分布通常是不用的。

2.4 累计懊悔

对于每一个动作a,定义其期望奖励为：
$$Q\left(a\right)=E_{r\sim R\left(\cdot |a\right)}\left[r\right]$$
于是，至少存在一根拉杆，它的期望奖励不小于其他任意一根拉杆，可以将该最优期望奖励表示为:
$$Q^{\ast }=\underset{a\in A}{\max }Q\left(a\right)$$

为了更加直观、方便地观察拉动一根拉杆的期望奖励与最优拉杆期望奖励的差距，引入 懊悔 概念。

• 懊悔(regret)：拉动当前拉杆的动作a与最优拉杆的期望奖励差，即
  $$R\left(a\right)=Q^{\ast }-Q\left(a\right)$$
• 累计懊悔(cumulative regret)：即操作T次拉杆后累计的懊悔总量，对于一次完整的T步决策{a₁ ,a₂ ,……,a_T},累计懊悔为：
  $${\sigma }_R=\sum _{t=1}^{T}R\left(a_t\right)$$
  MBA问题的目标为最大化累积奖励，等价于最小化累积懊悔

2.5 估计期望奖励

为了知道拉动拿一根拉杆能获得更高的奖励，我们需要估计拉动拉杆的期望奖励。由于只拉动一次拉杆获得的奖励存在随机性，所以需要多次拉动一根拉杆，然后计算得到的多次奖励的期望，算法流程如下：

• 对于$\forall a\in A$，初始化计数器N(a)=0和期望奖励估值$\stackrel{\wedge }{Q}\left(a\right)=0$
• for $t=1\to T$do
  • 选取某根拉杆，记录动作为a_t
  • 得到奖励r_t
  • 更新计数器：N(a_t)=N(a_t)+1
  • 更新期望奖励估值：$\overset{\land}{Q}\left( a_t \right) =\overset{\land}{Q}\left( a_t\right) +\frac{1}{N\left( a_t \right)}\left[ r_t-\overset{\land}{Q}\left( a_t \right) \right] $
• end for

注意：for循环的第四步计算期望采用了增量式计算方法，并没有使用求和再除以次数的方法。

下面编码实现一个10拉杆的多臂老虎机。每根拉杆的奖励服从伯努利分布。

• 一个简单的多臂老虎机中的伯努利分布：每次拉下拉杆有p的概率获得奖励为1，有(1-p)的概率获得的奖励为0。

注意：这里对老虎机做了很多简化，比如所有拉杆的获得奖励的概率服从同一个分布，奖励值都为1。在一些复杂的问题中，不同拉杆的奖励获得概率分布可能不同，奖励值可能也不同。

import numpy as np
import matplotlib.pyplot as plt
1
2

class BernoulliBandit:
    """伯努利老虎机，k表示拉杆的数量"""
    def __init__(self,k):
        self.probs=np.random.uniform(size=k) # 随机生成k个0~1的数，作为拉动每根拉杆的获得奖励的概率
        self.best_idx=np.argmax(self.probs) # 获得奖励概率最大的拉杆
        self.best_prob=self.probs[self.best_idx] # 获奖的最大概率
        self.k=k
    
    def step(self,k):
        # 当玩家选择了k好拉杆后，根据拉动该老虎机的K号拉杆获得奖励的概率返回1
        if np.random.rand()<self.probs[k]:
            return 1
        else:
            return 0
    def print_prob(self):
        for i in range(self.k):
            print("%d号拉杆的获奖概率为:%.4f"%(i,self.probs[i]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

np.random.seed(1) # 设定随机种子，使实验具有可重复性
k=10
bandit_10_arm=BernoulliBandit(k)

print("随机生成了一个%d臂伯努利老虎机"%k)
print("获奖概率最大的拉杆为%d号，其获奖概率为%.4f"%(bandit_10_arm.best_idx,bandit_10_arm.best_prob))

print("************")
bandit_10_arm.print_prob()
1
2
3
4
5
6
7
8
9

随机生成了一个10臂伯努利老虎机
获奖概率最大的拉杆为1号，其获奖概率为0.7203
************
0号拉杆的获奖概率为:0.4170
1号拉杆的获奖概率为:0.7203
2号拉杆的获奖概率为:0.0001
3号拉杆的获奖概率为:0.3023
4号拉杆的获奖概率为:0.1468
5号拉杆的获奖概率为:0.0923
6号拉杆的获奖概率为:0.1863
7号拉杆的获奖概率为:0.3456
8号拉杆的获奖概率为:0.3968
9号拉杆的获奖概率为:0.5388
1
2
3
4
5
6
7
8
9
10
11
12
13

• 思考： 根据上述例子，我们假设一共进行两步拉杆操作，假设第一步选了0号拉杆并且获得了奖励，那么我们第二步是继续选择0号拉杆还是去探索呢？在已知概率分布的情况下，这是一个复杂的概率计算问题；那么当我们不知道概率分布时怎么办呢？【仅做思考】

接下来定义一个Solver基础类实现上述的伯努利老虎机的求解方案,该类只定义了一些基本的功能函数，具体的决策、奖励、更新在该类的继承（子类）中具体实现。

class Solver:
    """多臂老虎机算法基础框架"""
    def __init__(self,bandit):
        self.bandit=bandit # 多臂老虎机
        self.counts=np.zeros(self.bandit.k) # 计数器
        self.regret=0 # 当前的累计懊悔
        self.actions=[] # 记录每一步的动作
        self.regrets=[] # 记录每一步的累积懊悔
    
    def updata_regret(self,k):
        # 计算累积懊悔并保存，k为本次选择的拉杆的编号
        self.regret+=self.bandit.best_prob-self.bandit.probs[k] # 选择的拉杆的概率与最大获得奖励的概率之差，懊悔
        self.regrets.append(self.regret)
    
    def run_one_step(self):
        # 返回当前动作选择哪一根拉杆，由每个具体的策略实现
        raise NotImplementedError
    
    def run(self,num_steps):
        # 运行一定次数，num_steps为总运行次数
        for _ in range(num_steps):
            k=self.run_one_step() # 决策结果
            self.counts[k]+=1
            self.actions.append(k)
            self.updata_regret(k)
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

3.探索与利用的平衡

在多臂老虎机中，一个经典的问题就是探索与利用的平衡问题。

• 探索exploration: 指尝试拉动更多可能的拉杆，虽然这种方式不一定会获得最大的奖励，但是能探索到所有拉杆的获奖情况。
• 利用exploitation: 指拉动已知期望奖励最大的那根拉杆，由于已知的信息仅仅来自有限的交互观测，所以当前的最优拉杆不一定是全局最优的。

在多臂老虎机中，设计策略时就需要平衡探索和利用的次数，使得累计奖励最大化。一个常用的思路是在开始时做较多的探索，在对每根拉杆都有比较准确的估计后，在进行利用。

目前有一些经典的算法来平衡探索和利用，如

• $ϵ-$贪婪算法
• 上置信界算法
• 汤普森采样算法

4. 𝜖-贪婪算法

• 完全贪婪算法： 即在每一时刻采取期望奖励估值最大的动作，也就是纯粹的利用，并没有探索。
  $ϵ-$贪婪算法是完全贪婪策略的修改版本，在其基础上添加了噪声，每次以$1-ϵ$的概率选择以往经验中期望奖励估值最大的那根拉杆（利用），以$ϵ$的概率随机选择一根拉杆（探索）。$ϵ-$贪婪算法算法公式如下：
  KaTeX parse error: \cr valid only within a tabular/array environment
  随着探索次数的不断增加，我们对各个动作的奖励估计得越来越准，此时我们就没有要继续花大力气进行探索。因此可以使$ϵ$随时间进行衰减。

# 𝜖 =0.01,T=5000
class EpsionGreedy(Solver):
    """epsilon贪婪算法，继承自Solver类"""
    def __init__(self,bandit,epsilon=0.01,init_prob=1.0):
        super(EpsionGreedy,self).__init__(bandit)
        self.epsilon=epsilon
        self.estimates=np.array([init_prob]*self.bandit.k) # 初始化拉动所有拉杆的期望奖励估值
    
    def run_one_step(self): #父类Solver的方法重写
        if np.random.random()<self.epsilon:
            k=np.random.randint(0,self.bandit.k) # 随机选择一根拉杆
        else:
            k=np.argmax(self.estimates) # 选择期望奖励估值最大的拉杆
        
        r=self.bandit.step(k) # 获得本次动作的奖励
        
        self.estimates[k]+=1./(self.counts[k]+1)*(r-self.estimates[k]) #增量式更新期望
        
        return k
    
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 可视化
def plot_results(solvers,solver_names):
    """生成累计懊悔随时间变化的图像。输入solvers是一个列表，列表中的每个元素是一种特定的策略
       而solver_names也是一个列表，存储每个策略的名称   
    """
    for idx,solver in enumerate(solvers):
        time_list=range(len(solver.regrets))
        plt.plot(time_list,solver.regrets,label=solver_names[idx])
    
    plt.xlabel("Time steps")
    plt.ylabel("Cumulative regrets")
    plt.title("%d-armed bandit"%solvers[0].bandit.k)
    plt.legend()
    plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

np.random.seed(1)
epg_solver=EpsionGreedy(bandit=bandit_10_arm,epsilon=0.01)
epg_solver.run(5000)
print("5000步下𝜖 -贪婪算法的累计懊悔为：",epg_solver.regret)
plot_results([epg_solver],['EpsilonGreedy'])
1
2
3
4
5

5000步下𝜖 -贪婪算法的累计懊悔为： 25.526630933945313
1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3NFo8fzQ-1668394929265)(%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_files/%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_15_1.png)]

通过上述代码，可以看出，在经历了开始的一小段时间后，𝜖-贪婪算法的累积懊悔几乎是线性增长的。下面探究不同的𝜖取值结果。

np.random.seed(0)
epsilons=[1e-4,0.01,0.1,0.25,0.5]
epsilon_greedy_solver_list=[EpsionGreedy(bandit_10_arm,epsilon=e) for e in epsilons]

epsilon_greedy_solver_names=["epsilon={}".format(e) for e in epsilons]

for solver in epsilon_greedy_solver_list:
    solver.run(5000)

plot_results(epsilon_greedy_solver_list,epsilon_greedy_solver_names)
1
2
3
4
5
6
7
8
9
10

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C059embE-1668394929266)(%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_files/%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_17_0.png)]

从上述代码可以看出，基本上无论𝜖取值是什么，累积懊悔大致都是线性增长的。但是𝜖越大，表示探索的概率越大，累积懊悔增长的速度也会越大。(基本上，因为我们的拉杆数目有限，当我们大体上摸清每个拉杆的获奖概率后，再进行相对大概率的探索就会使得累积懊悔增大)

下面探究随时间衰减的𝜖-贪婪算法，具体的衰减形式为：
$$ϵ=\frac{1}{t}$$

class DecayingEpsilonGreedy(Solver):
    """epsilon值随时间衰减的𝜖-贪婪算法，继承Solver类"""
    def __init__(self,bandit,init_prob=1.0):
        super(DecayingEpsilonGreedy,self).__init__(bandit)
        self.estimates=np.array([init_prob]*self.bandit.k)
        self.total_count=0 # 执行次数，作为衰减因子

    def run_one_step(self):
        self.total_count+=1
        if np.random.random()<1/self.total_count:
            k=np.random.randint(self.bandit.k)
        else:
            k=np.argmax(self.estimates)
        
        r=self.bandit.step(k)
        
        self.estimates[k]+=1/(self.counts[k]+1)*(r-self.estimates[k])
        
        return k
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

np.random.seed(1)
decaying_epsilon_greedy_solver=DecayingEpsilonGreedy(bandit_10_arm)
decaying_epsilon_greedy_solver.run(5000)
print("𝜖衰减的贪婪算法的累计懊悔为：",decaying_epsilon_greedy_solver.regret)
plot_results([decaying_epsilon_greedy_solver],['DecayingEpsilonGreedy'])
1
2
3
4
5

𝜖衰减的贪婪算法的累计懊悔为： 10.114334931260183
1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wuu6Hjcf-1668394929267)(%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_files/%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_20_1.png)]

5.上置信界算法

一根拉杆只被拉动过一次，那么它的不确定性很高，进而其探索的价值高。为此，引入不确定性度量U(a),它会随着一个动作被尝试的次数的增加而减小。进而，我们可以使用一种基于不确定性的策略来综合考虑现有的期望奖励估值和不确定性，核心问题是如何估计不确定性。

上置信界(upper confidence bound, UCB)算法是一种经典的基于不确定性的策略方法，它的思想用到来了著名的数学原理：霍夫丁不等式。

霍夫丁不等式：令$
X_1,\cdots ,X_n$为n个独立同分布的随机变量，取值范围为[0,1],其经验期望为：$\overset{-}{x_n}=\frac{1}{n}\sum_{j=1}^n{X_j}$，则有
$$P\left\{E\left[X\right]\ge \stackrel{-}{x_n}+u\right\}\le e^{-2n{u}^2}$$

将霍夫丁不等式应用到多臂老虎机问题中：将$\stackrel{\wedge }{Q}(a_t)$ 带入$
\overset{-}{x_t}
$，不等式中的参数$
u=\overset{\land}{U}\left( a_t \right)
$代表不确定性度量。那么：
$$P\left\{E\left[X\right]\ge \stackrel{\wedge }{Q}\left(a_t\right)+\stackrel{\wedge }{U}\left(a_t\right)\right\}\le e^{-2n{u}^2}$$

给定一个概率$
p=e^{-2N\left( a_t \right) U\left( a_t \right) ^2}
$，则不等式$Q\left( a_t \right) <\overset{\land}{Q}\left( a_t \right) +\overset{\land}{U}\left( a_t \right)$至少以概率1-p成立。当p很小时，$Q\left( a_t \right) <\overset{\land}{Q}\left( a_t \right) +\overset{\land}{U}\left( a_t \right)$成立的概率就很大，$\overset{\land}{Q}\left( a_t \right) +\overset{\land}{U}\left( a_t \right)$便是期望奖励上界。此时置信上界算法便选取期望奖励上界最大的动作，即$a=\underset{a\in A}{arg\max}\left[ \overset{\land}{Q}\left( a \right) +\overset{\land}{U}\left( a \right) \right] $。其中$\overset{\land}{U}\left( a_t \right)$由等式$p=e^{-2N\left( a_t \right) U\left( a_t \right) ^2}$解得$
\overset{\land}{U}\left( a_t=\sqrt{\frac{-\log p}{2N\left( a_t \right)}} \right)
$。

直观地说，UCB算法在每次选择拉杆前，先估计每根拉杆的期望奖励的上界，使得每根拉杆的期望奖励只有一个较小的概率p超过这个上界，接着选取期望上界最大的拉杆，从而选择最有可能获得最大期望奖励的拉杆。

下面使用前面定义的10臂老虎机模拟UCB算法。设置概率为$p=\frac{1}{t}$；不确定性度量为$
\overset{\land}{U}\left( a_t=\sqrt{\frac{-\log p}{2N\left( a_t \right)+1}} \right)
$，分母加上常数1是为了防止分母为0；同时设定一个系数c控制不确定性的比重，此时$a=\underset{a\in A}{arg\max}\left[ \overset{\land}{Q}\left( a \right) +c \cdot \overset{\land}{U}\left( a \right) \right] $。

class UCB(Solver):
    """UCB算法，继承自Solver类"""
    def __init__(self,bandit,coef,init_prob=1.0):
        super(UCB,self).__init__(bandit)
        self.total_count=0
        self.estimates=np.array([init_prob]*self.bandit.k)
        self.coef=coef
        
    def run_one_step(self):
        self.total_count+=1
        ucb=self.estimates+self.coef*np.sqrt(np.log(self.total_count)/(2*(self.counts+1)))#计算置信上界
        
        k=np.argmax(ucb)
        r=self.bandit.step(k)
        
        self.estimates[k]+=1./(self.counts[k]+1)*(r-self.estimates[k])
        return k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

np.random.seed(1)
coef=1 # 不确定性系数
UCB_solver=UCB(bandit_10_arm,coef)
UCB_solver.run(5000)

print("上置信界算法的累计懊悔为：",UCB_solver.regret)
plot_results([UCB_solver],["UCB"])
1
2
3
4
5
6
7

上置信界算法的累计懊悔为： 70.45281214197854
1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jfdimUhY-1668394929268)(%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_files/%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_24_1.png)]

6.汤普森采样算法

汤普森采样(Thompson sampling)的基本思路：根据当前每个动作a的奖励概率进行一轮采样，得到一组各根拉杆的奖励样本，再选择样本中奖励最大的动作。

如何得到当前每个动作a的奖励概率分布并在过程中进行更新？：通常使用Beta分布对当前每个动作的奖励概率分布进行建模。具体来说，模某根拉杆被选择了k此，其中$m_1$次奖励为1，$m_2$次奖励为0，则该拉杆的奖励服从参数为($m_1$+1,$m_2$+1)的Beta分布。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kXdImDat-1668394929270)(https://ai-studio-static-online.cdn.bcebos.com/9071f5e5d37a49b59e4f36827ce17712119fbfd92aa04c5bbc172fe63a9a0838)]

class ThompsonSampling(Solver):
    """汤姆森采样算法，继承Solver类"""
    def __init__(self,bandit):
        super(ThompsonSampling,self).__init__(bandit)
        self.a=np.ones(self.bandit.k) # 每根拉杆奖励为1的次数
        self.b=np.ones(self.bandit.k) # 每根拉杆奖励为0的次数
    def run_one_step(self):
        samples=np.random.beta(self.a,self.b)
        k=np.argmax(samples)
        r=self.bandit.step(k)
        
        self.a[k]+=r
        self.b[k]+=(1-r)
        
        return k
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

np.random.seed(1)
thompson_sampling_solver=ThompsonSampling(bandit_10_arm)
thompson_sampling_solver.run(5000)
print("汤普森采样的累计懊悔为：",thompson_sampling_solver.regret)

plot_results([thompson_sampling_solver],["ThompsonSampling"])

1
2
3
4
5
6
7

汤普森采样的累计懊悔为： 57.19161964443925
1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pCKhQ6DS-1668394929271)(%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_files/%E5%A4%9A%E8%87%82%E8%80%81%E8%99%8E%E6%9C%BA_27_1.png)]

总结

本项目仅是对一些概念和方法做简单的描述，没有涉及优化问题。通过本项目，我们的目标是：

• 了解多臂老虎机问题
• 了解𝜖-贪婪算法及其变体
• 了解上置信界算法
• 了解汤普森算法
• 体会到探索和利用是多臂老虎机问题的重要研究方向之一，二者的平衡至关重要

友情链接：
多臂老虎机