多臂老虎机

\(\)

2.1 简介 #

我们在第 1 章中了解到，强化学习关注 agent 和 Env 交互过程中的学习，这是一种试错型学习 (trial-and-error learning) 范式。在正式学习强化学习之前，我们需要先了解多臂老虎机问题，它可以被看作简化版的强化学习问题。与强化学习不同，多臂老虎机不存在状态信息，只有动作和奖励，算是最简单的“和环境交互中的学习”的一种形式。多臂老虎机中的探索与利用 (exploration vs. exploitation) 问题一直以来都是一个特别经典的问题，理解它能够帮助我们学习强化学习。

2.2 问题介绍 #

2.2.1 问题定义 #

在多臂老虎机（multi-armed bandit，MAB）问题（见图 2-1）中，有一个拥有 $K$ 根拉杆的老虎机，拉动每一根拉杆都对应一个关于奖励的概率分布 $R$。我们每次拉动其中一根拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励 $r$。我们在各根拉杆的奖励概率分布未知的情况下，从头开始尝试，目标是在操作 $T$ 次拉杆后获得尽可能高的累积奖励。由于奖励的概率分布是未知的，因此我们需要在 “探索拉杆的获奖概率” 和 “根据经验选择获奖最多的拉杆” 中进行权衡。“采用怎样的操作策略才能使获得的累积奖励最高” 便是多臂老虎机问题。如果是你，会怎么做呢？

2-1

图2-1 多臂老虎机

2.2.2 形式化描述 #

多臂老虎机问题可以表示为一个元组 $\left \langle \mathcal{A}, \mathcal{R} \right \rangle$，其中：

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

假设每个时间步只能拉动一个拉杆，多臂老虎机的目标为最大化一段时间步 $T$ 内累积的奖励:

$$ \max\sum_{t=1}^T r_t,\ \ \ \ r_t\sim\mathcal{R}(\cdot|a_t) $$

其中 $a_t$ 表示在第 $t$ 时间步拉动某一拉杆的动作，$r_t$ 表示动作 $a_t$ 获得的奖励。

2.2.3 累积懊悔 #

对于每一个动作 $a$，我们定义其期望奖励为

$$ Q(a)=\mathbb{E}_{r\sim\mathcal{R}(\cdot|a)}[r] $$

于是，至少存在一根拉杆，它的期望奖励不小于拉动其他任意一根拉杆，我们将该最优期望奖励表示为

$$ Q^* = \max_{a\in\mathcal{A}}Q(a) $$

为了更加直观、方便地观察拉动一根拉杆的期望奖励离最优拉杆期望奖励的差距，我们引入 懊悔（regret）概念。懊悔定义为拉动当前拉杆的动作 $a$ 与最优拉杆的期望奖励差，即 $R(a)=Q^*-Q(a)$。累积懊悔（cumulative regret）即操作 $T$ 次拉杆后累积的懊悔总量，对于一次完整的 $T$ 步决策 $(a_1, \cdots, a_T)$，累积懊悔为

$$ \sigma_R = \sum_{t=1}^T R(a_t) $$

MAB 问题的目标为最大化累积奖励，等价于最小化累积懊悔。

2.2.4 估计期望奖励 #

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

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

以上 for 循环中的第四步如此更新估值，是因为这样可以进行增量式的期望更新，公式如下：

$$ \begin{align*} Q_k &= \cfrac{1}{k}\sum_{i=1}^k r_i \\ &= \cfrac{1}{k}\left(r_k + \sum_{i=1}^{k-1}r_i\right) \\ &= \cfrac{1}{k}\left(r_k + (k-1)Q_{k-1}\right) \\ &= \cfrac{1}{k}\left(r_k + kQ_{k-1} - Q_{k-1}\right) \\ &= Q_{k-1} + \cfrac{1}{k}(r_k - Q_{k-1}) \\ \end{align*} $$

如果是将所有数求和再除以次数，缺点是每次更新的时间复杂度和空间复杂度均为 $O(n)$。而采用增量式更新，时间复杂度和空间复杂度均为 $O(1)$。

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

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（未获奖）
        return int(np.random.rand() < self.probs[k])

np.random.seed(2048)
K = 10

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

随机生成了一个 10 臂伯努利老虎机
获奖概率最大的拉杆为 3 号, 其获奖概率为 0.9871

接下来我们用一个 Solver 基础类来实现上述的多臂老虎机的求解方案。根据前文的算法流程，我们需要实现下列函数功能：根据 policy 选择动作、根据动作获取奖励、更新期望奖励估值、更新累积懊悔和计数。

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)

2.3 探索与利用的平衡 #

在多臂老虎机问题中，一个经典的问题就是 探索与利用 的平衡问题。探索 (exploration) 是指尝试拉动更多可能的拉杆，这根拉杆不一定会获得最大的奖励，但这种方案能够摸清楚所有拉杆的获奖情况。利用 (exploitation) 是指拉动已知期望奖励最大的那根拉杆，由于已知的信息仅仅来自有限次的交互观测，所以当前的最优拉杆不一定是全局最优的。

于是在多臂老虎机问题中，设计策略时就需要平衡 exploration 和 exploitation 的次数，使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的 exploration，在对每根拉杆都有比较准确的估计后，再进行 exploitation。目前已有一些比较经典的算法来解决这个问题，例如 $\epsilon$-Greedy 算法、上置信界算法 和 汤普森采样算法 等。

2.4 $\epsilon$-贪心 算法 #

完全贪心算法 即在每一时刻采取期望奖励估值最大的动作 (拉动拉杆)，这就是纯粹的 exploitation，而没有 exploration，所以我们通常需要对 完全贪心算法 进行一些修改，其中比较经典的一种方法为 $\epsilon$-贪心 ($\epsilon$-Greedy) 算法。 $\epsilon$-Greedy 算法在 完全贪心算法 的基础上添加了噪声，每次以概率 $1-\epsilon$ 选择以往经验中期望奖励估值最大的那根拉杆 (exploitation)，以概率 $\epsilon$ 随机选择一根拉杆 (exploration)，公式如下：

$$ a_t=\begin{cases} \arg\max_{a\in\mathcal{A}}\hat{Q(a)},\ \ \ \ \text{采样概率 } 1-\epsilon \\ \text{从 } \mathcal{A} \text{ 中随机选择},\ \ \ \ \text{采样概率 } \epsilon \end{cases} $$

随着 exploration 次数的不断增加，我们对各个动作的奖励估计得越来越准，此时我们就没必要继续花大力气进行 exploration。所以在 $\epsilon$-Greedy 算法的具体实现中，我们可以令 $\epsilon$ 随时间衰减，即 exploration 的概率将会不断降低。但是请注意，$\epsilon$ 不会在有限的步数内衰减至 0，因为基于有限步数观测的 完全贪心算法 仍然是一个局部信息的贪心算法，永远距离最优解有一个固定的差距。

我们接下来编写代码来实现一个 $\epsilon$-Greedy 算法，并用它去解决 2.2.4 节生成的 10 臂老虎机的问题。设置 $\epsilon = 0.001$，以及 $T=5000$。

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-贪心算法的累积懊悔为： 36.257475887481995

2-code-1

通过上面的实验可以发现，在经历了开始的一小段时间后，$\epsilon$-Greedy 算法的累积懊悔几乎是线性增长的。这是 $\epsilon=0.01$ 时的结果，因为一旦做出了随机拉杆的 exploration，那么产生的懊悔值是固定的。其他不同的 $\epsilon$ 取值又会带来怎样的变化呢？我们继续使用该 10 臂老虎机，我们尝试不同的参数，查看相应的实验结果

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)

2-code-2

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

class DecayingEpsilonGreedy(Solver):
    """ epsilon 值随时间衰减的 epsilon-Greedy 算法,继承 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 值衰减的贪心算法的累积懊悔为： 13.765494435745682

2-code-3

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

2.5 上置信界算法 #

上置信界 (upper confidence bound，UCB) 算法，又称置信区间上界算法。他的思想是：显然，当前成功率高的按钮是有高利用价值的，不确定性高的按钮是有高探索价值的。我们能不能综合这两种价值，给每种按钮一个评分，从而选择评分最高的按钮呢？

用预估奖励概率 (得到奖励的次数 / 按下的次数) 来衡量某个按钮的 “利用价值” 就行了，“探索价值” 可以用这个按钮的某种 不确定性度量 来衡量。而按钮的评分，最简单的方法就是用两个价值的和来表示。也就是说：

评分 = 预估奖励概率 + 不确定性度量

到了这个阶段，找到一种能够衡量按钮的不确定性的方法就至关重要了。下面说一下 UCB 算法的思路：

假设当前某个按钮的真实奖励概率是 $p$，它被按下了 $n$ 次，其中有 $n_r$ 次获得了奖励，它的预估奖励概率是 $\tilde{p}=\cfrac{n_r}{n}$。如果能够根据我们按按钮的经验找到一个 $\delta$，使得 $p \le \tilde{p} + \delta$ 恒成立，那么 $\tilde{p} + \delta$ 就是真实概率 $p$ 的上界，或者说 $\tilde{p} + \delta$ 决定了 $p$ 的取值范围。因此在 $\tilde{p}$ 确定的情况下，$\delta$ 越大 $p$ 的取值范围也就越大。显然 $\delta$ 能够在一定程度上反映按钮的不确定性。

那怎么找到这个 $\delta$ 呢？我们需要引入一个著名的数学原理——霍夫丁不等式 (Hoeffding's inequality)。

【霍夫丁不等式】

设 $X_1, X_2, \cdots, X_n$ 是取值范围为 $[0, 1]$ 的 $n$ 个独立同分布随机变量，用

$$ \tilde{p} = \cfrac{1}{n}\sum_{i=1}^{n}X_i $$

表示它们的样本均值，用 $p$ 表示它们的分布的均值。那么有:

$$ P\{ p - \tilde{p} \le \delta \} \ge 1- e^{-2n\delta^2} $$

所以，霍夫丁不等式怎么帮助我们找到之前说的 $\delta$ 呢？

在多臂老虎机问题中，对于某个按钮而言，按一次的结果 (即得到的钱) 可以用服从伯努利分布的随机变量 $X$ 表示。其中有 $p$ 的概率能够得到奖励，此时 $X = 1$；又有 $1 - p$ 的概率得不到奖励，此时 $X = 0$。得到的钱的期望也正是 $p$。按 $n$ 次该按钮的结果分别是取值范围为 $[0, 1]$ 的独立同分布的随机变量 $X_1, X_2, \cdots, X_n$。它们的样本均值为 $\tilde{p} = \cfrac{1}{n}\sum_{i=1}^{n}X_i$。这其实就是霍夫丁不等式的条件的描述。

霍夫丁不等式本身又是什么意思呢？就是说 $p - \tilde{p} \le \delta$ 这件事发生的概率一定大于或等于 $1- e^{-2n\delta^2}$。我们对 $p - \tilde{p} \le \delta$ 做移项，可以得到 $p \le \tilde{p} + \delta$。可以发现，这正是我们定义不确定信度量 $\delta$ 时用的不等式吗。

前面说过，我们想要让 $p \le \tilde{p} + \delta$ 恒成立。可惜这是不现实的，但是好在根据霍夫丁不等式，我们可以想办法让 $p \le \tilde{p} + \delta$ 这件事发生的概率足够大，大到我们可以睁一只眼闭一只眼，近似地认为它一定会发生。也就是说我们要想办法让霍夫丁不等式右侧的 $1- e^{-2n\delta^2}$ 在小于 1 的限制下足够大。

那么问题来了，多大才算足够大？不妨用当前按下按钮的总次数 $N$ 来定义 “足够大”，看看会得到什么样的结论。$\cfrac{N-1}{N}$ 看上去就足够大了，而且也满足小于 1 的限制。我们令 $1- e^{-2n\delta^2} = \cfrac{N-1}{N}$ 解这个方程可以得到:

$$ \delta = \sqrt{\cfrac{\ln N}{2n}} $$

结论就是我们令 $\delta = \sqrt{\cfrac{\ln N}{2n}}$，可以几乎使得 $p \le \tilde{p} + \delta$ 恒成立，因此 $\delta$ 是一个不错的不确定性度量。

  • 当 $n$ 不变时，$\delta$ 随着 $N$ 的增大而增大。也就是说，当我们始终不按某个按钮，却多次按下其它按钮时，这个按钮的不确定性 (相对别的按钮而言) 就升高了
  • 当N不变时，$\delta$ 随着 $n$ 的增大而减小。也就是说，当我们按某个按钮的比例增大后，这个按钮的不确定性 (相对别的按钮而言) 就降低了

这两条分析都是合理的所以可以认为我们得到的不确定性表达式是合理的。

至此，我们得到了 UCB 算法选择按钮的策略：

每次选择评分 $\cfrac{n_r}{n+1} + \sqrt{\cfrac{\ln N}{2n}}$ 最高的按钮

为了防止分母爆零，我们可以将分母加上 1。另外，为了调节探索与利用的权重，我们可以在根号前乘上一个超参数 c，以便通过设置一个较大的 c 使策略更加注重探索。相当于

在工程上会使用这个评分表达式： $\cfrac{n_r}{n} + c\sqrt{\cfrac{\ln N}{2n+1}}$

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

上置信界算法的累积懊悔为： 82.6468452073969

2-code-4

2.6 汤普森采样算法 #