多臂老虎机（强化学习中的探索与利用）

标签：探索 epsilon self 多臂 bandit 奖励算法老虎机拉杆

文章目录

一、多臂老虎机问题介绍
二、探索与利用的平衡
三、ϵ-贪心算法
四、上置信界算法
五、汤普森采样算法

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

一、多臂老虎机问题介绍

1.1 问题定义

在多臂老虎机（multi-armed bandit，MAB）问题中，有一个拥有 K \mathcal{K} K根拉杆的老虎机，拉动每一根拉杆都对应一个关于奖励的概率分布 R \mathcal{R} R。
我们每次拉动其中一根拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励 r r r。我们在各根拉杆的奖励概率分布未知的情况下，从头开始尝试，目标是在操作 T T T次拉杆后获得尽可能高的累积奖励。
由于奖励的概率分布是未知的，因此我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。“
在这里插入图片描述

1.2 形式化表述

多臂老虎机问题可以表示为一个元组 < A , R > \mathcal{<A,R>} <A,R> ，其中：

A \mathcal{A} A为动作集合，其中一个动作表示拉动一个拉杆。若多臂老虎机一共有 K \mathcal{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\vert a) R(r∣a)，不同拉杆的奖励分布通常是不同的。
假设每个时间步只能拉动一个拉杆，多臂老虎机的目标为最大化一段时间步 T T T内累积的奖励:
max ⁡ ∑ t = 1 T r t , r t ∼ R ( ⋅ ∣ a t ) \max \sum_{t=1}^T r_t, r_t \sim \mathcal{R}(\cdot \vert a_t) maxt=1∑Trt,rt∼R(⋅∣at)
其中 a t a_t at表示在第 t t t时间步拉动某一拉杆的动作， r t r_t rt表示动作 a t a_t at获得的奖励。

1.3 累积懊悔

对于每一个动作 a a a，我们定义其期望奖励为 Q ( a ) = E r ∼ R ( ⋅ ∣ a ) [ r ] Q(a)=\mathbb{E}_{r \sim \mathcal {R}(\cdot \vert a)}[r] Q(a)=Er∼R(⋅∣a)[r]。于是，至少存在一根拉杆，它的期望奖励不小于拉动其他任意一根拉杆，我们将该最优期望奖励表示为 Q ∗ = max ⁡ a ∈ A Q ( a ) Q^*=\max_{a \in \mathcal{A}} Q(a) Q∗=maxa∈AQ(a)。为了更加直观、方便地观察拉动一根拉杆的期望奖励离最优拉杆期望奖励的差距，引入懊悔（regret）概念。懊悔定义为拉动当前拉杆的动作 a a a与最优拉杆的期望奖励差，即 R ( a ) = Q ∗ − Q ( a ) R(a)=Q^*-Q(a) R(a)=Q∗−Q(a)。累积懊悔（cumulative regret）即操作 T T T次拉杆后累积的懊悔总量，对于一次完整的 T T T步决策 { a 1 , a 2 , ⋯ , a T } \{a_1,a_2, \cdots,a_T \} {a1,a2,⋯,aT}，累积懊悔为 σ R = ∑ t = 1 T R ( a t ) \sigma_R=\sum_{t=1}^T R(a_t) σR=∑t=1TR(at)。
MAB 问题的目标为最大化累积奖励，等价于最小化累积懊悔。

1.4 估计期望奖励

为了知道拉动哪一根拉杆能获得更高的奖励，我们需要估计拉动这根拉杆的期望奖励。由于只拉动一次拉杆获得的奖励存在随机性，所以需要多次拉动一根拉杆，然后计算得到的多次奖励的期望，其算法流程如下所示。
在这里插入图片描述

采用增量式更新，时间复杂度和空间复杂度均为 O ( 1 ) O(1) O(1) 。

编写代码来实现一个拉杆数为 10 的多臂老虎机。其中拉动每根拉杆的奖励服从伯努利分布（Bernoulli distribution），即每次拉下拉杆有 p p p的概率获得的奖励为 1，有 1 − p 1-p 1−p的概率获得的奖励为 0。奖励为 1 代表获奖，奖励为 0 代表没有获奖。

# 导入需要使用的库,其中numpy是支持数组和矩阵运算的科学计算库,而matplotlib是绘图库
import numpy as np
import matplotlib.pyplot as plt


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（获奖）或0（未
        # 获奖）
        if np.random.rand() < self.probs[k]:
            return 1
        else:
            return 0


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))

用一个 Solver 基础类来实现上述的多臂老虎机的求解方案。根据前文的算法流程，需要实现下列函数功能：根据策略选择动作、根据动作获取奖励、更新期望奖励估值、更新累积懊悔和计数。在下面的 MAB 算法基本框架中，我们将根据策略选择动作、根据动作获取奖励和更新期望奖励估值放在 run_one_step() 函数中，由每个继承 Solver 类的策略具体实现。而更新累积懊悔和计数则直接放在主循环 run() 中。

class Solver:
    """ 多臂老虎机算法基本框架 """
    def __init__(self, bandit):
        self.bandit = bandit
        self.counts = np.zeros(self.bandit.K)  # 每根拉杆的尝试次数
        self.regret = 0.  # 当前步的累积懊悔
        self.actions = []  # 维护一个列表,记录每一步的动作
        self.regrets = []  # 维护一个列表,记录每一步的累积懊悔

    def update_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.update_regret(k)

二、探索与利用的平衡

探索（exploration）是指尝试拉动更多可能的拉杆，这根拉杆不一定会获得最大的奖励，但这种方案能够摸清楚所有拉杆的获奖情况。例如，对于一个 10 臂老虎机，我们要把所有的拉杆都拉动一下才知道哪根拉杆可能获得最大的奖励。利用（exploitation）是指拉动已知期望奖励最大的那根拉杆，由于已知的信息仅仅来自有限次的交互观测，所以当前的最优拉杆不一定是全局最优的。例如，对于一个 10 臂老虎机，我们只拉动过其中 3 根拉杆，接下来就一直拉动这 3 根拉杆中期望奖励最大的那根拉杆，但很有可能期望奖励最大的拉杆在剩下的 7 根当中，即使我们对 10 根拉杆各自都尝试了 20 次，发现 5 号拉杆的经验期望奖励是最高的，但仍然存在着微小的概率—另一根 6 号拉杆的真实期望奖励是比 5 号拉杆更高的。
于是在多臂老虎机问题中，设计策略时就需要平衡探索和利用的次数，使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的探索，在对每根拉杆都有比较准确的估计后，再进行利用。目前已有一些比较经典的算法来解决这个问题，例如 ϵ \epsilon ϵ-贪婪算法、上置信界算法和汤普森采样算法等。

三、ϵ-贪心算法

完全贪婪算法即在每一时刻采取期望奖励估值最大的动作（拉动拉杆），这就是纯粹的利用，而没有探索，所以我们通常需要对完全贪婪算法进行一些修改，其中比较经典的一种方法为 ϵ \epsilon ϵ-贪婪算法。 ϵ \epsilon ϵ-贪婪算法在完全贪婪算法的基础上添加了噪声，每次以概率 1 − ϵ 1-\epsilon 1−ϵ择以往经验中期望奖励估值最大的那根拉杆（利用），以概率 ϵ \epsilon ϵ随机选择一根拉杆（探索），公式如下：
a t = { arg max ⁡ a ∈ A Q ^ ( a ) ，采样概率； 1 − ϵ 从 A 中随机选择，采样概率； ϵ a_t=\begin{cases} \argmax_{a \in \mathcal{A}} \hat{Q}(a)，采样概率；1-\epsilon \\ 从\mathcal{A}中随机选择，采样概率；\epsilon \end{cases} at={argmaxa∈AQ^(a)，采样概率；1−ϵ从A中随机选择，采样概率；ϵ
随着探索次数的不断增加，我们对各个动作的奖励估计得越来越准，此时我们就没必要继续花大力气进行探索。所以在 ϵ \epsilon ϵ-贪婪算法的具体实现中，我们可以令 ϵ \epsilon ϵ随时间衰减，即探索的概率将会不断降低。但是 ϵ \epsilon ϵ不会在有限的步数内衰减至 0，因为基于有限步数观测的完全贪婪算法仍然是一个局部信息的贪婪算法，永远距离最优解有一个固定的差距。

class EpsilonGreedy(Solver):
    """ epsilon贪婪算法,继承Solver类 """
    def __init__(self, bandit, epsilon=0.01, init_prob=1.0):
        super(EpsilonGreedy, self).__init__(bandit)
        self.epsilon = epsilon
        #初始化拉动所有拉杆的期望奖励估值
        self.estimates = np.array([init_prob] * self.bandit.K)

    def run_one_step(self):
        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

为了更加直观地展示，可以把每一时间步的累积函数绘制出来。于是定义了以下绘图函数，方便之后调用。

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()


np.random.seed(1)
epsilon_greedy_solver = EpsilonGreedy(bandit_10_arm, epsilon=0.01)
epsilon_greedy_solver.run(5000)
print('epsilon-贪婪算法的累积懊悔为：', epsilon_greedy_solver.regret)
plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])

在这里插入图片描述
通过上面的实验可以发现，在经历了开始的一小段时间后， ϵ \epsilon ϵ-贪婪算法的累积懊悔几乎是线性增长的。这是 ϵ \epsilon ϵ=0.01时的结果，因为一旦做出了随机拉杆的探索，那么产生的懊悔值是固定的。不同的 ϵ \epsilon ϵ会有不同的结果。

np.random.seed(0)
epsilons = [1e-4, 0.01, 0.1, 0.25, 0.5]
epsilon_greedy_solver_list = [
    EpsilonGreedy(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)

在这里插入图片描述
通过实验结果可以发现，基本上无论 ϵ \epsilon ϵ取值多少，累积懊悔都是线性增长的。在这个例子中，随着 ϵ \epsilon ϵ增大，累积懊悔增长的速率也会增大。接下来我们尝试 ϵ \epsilon ϵ值随时间衰减的 ϵ \epsilon ϵ-贪婪算法，采取的具体衰减形式为反比例衰减，公式为 ϵ t = 1 t \epsilon_t=\frac 1 t ϵt=t1。

class DecayingEpsilonGreedy(Solver):
    """ epsilon值随时间衰减的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:  # 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


np.random.seed(1)
decaying_epsilon_greedy_solver = DecayingEpsilonGreedy(bandit_10_arm)
decaying_epsilon_greedy_solver.run(5000)
print('epsilon值衰减的贪婪算法的累积懊悔为：', decaying_epsilon_greedy_solver.regret)
plot_results([decaying_epsilon_greedy_solver], ["DecayingEpsilonGreedy"])

在这里插入图片描述
从实验结果图中可以发现，随时间做反比例衰减的 ϵ \epsilon ϵ-贪婪算法能够使累积懊悔与时间步的关系变成次线性（sublinear）的，这明显优于固定 ϵ \epsilon ϵ值的 ϵ \epsilon ϵ-贪婪算法。

四、上置信界算法

一根拉杆的不确定性越大，它就越具有探索的价值，因为探索之后我们可能发现它的期望奖励很大。我们在此引入不确定性度量 U ( a ) U(a) U(a)，它会随着一个动作被尝试次数的增加而减小。我们可以使用一种基于不确定性的策略来综合考虑现有的期望奖励估值和不确定性，其核心问题是如何估计不确定性。
上置信界（upper confidence bound，UCB）算法是一种经典的基于不确定性的策略算法，它的思想用到了一个非常著名的数学原理：霍夫丁不等式（Hoeffding’s inequality）。更直观地说，UCB 算法在每次选择拉杆前，先估计每根拉杆的期望奖励的上界，使得拉动每根拉杆的期望奖励只有一个较小的概率 p p p超过这个上界，接着选出期望奖励上界最大的拉杆，从而选择最有可能获得最大期望奖励的拉杆。

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


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"])

在这里插入图片描述

五、汤普森采样算法

MAB 中还有一种经典算法——汤普森采样（Thompson sampling），先假设拉动每根拉杆的奖励服从一个特定的概率分布，然后根据拉动每根拉杆的期望奖励来进行选择。但是由于计算所有拉杆的期望奖励的代价比较高，汤普森采样算法使用采样的方式，即根据当前每个动作 a a a的奖励概率分布进行一轮采样，得到一组各根拉杆的奖励样本，再选择样本中奖励最大的动作。可以看出，汤普森采样是一种计算所有拉杆的最高奖励概率的蒙特卡洛采样方法。

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)  # 按照Beta分布采样一组奖励样本
        k = np.argmax(samples)  # 选出采样奖励最大的拉杆
        r = self.bandit.step(k)

        self._a[k] += r  # 更新Beta分布的第一个参数
        self._b[k] += (1 - r)  # 更新Beta分布的第二个参数
        return k


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"])