我们在第 1 章中了解到,强化学习关注智能体和环境交互过程中的学习,这是一种试错型学习(trial-and-error learning)范式。在正式学习强化学习之前,我们需要先了解多臂老虎机问题,它可以被看作简化版的强化学习问题。与强化学习不同,多臂老虎机不存在状态信息,只有动作和奖励,算是最简单的“和环境交互中的学习”的一种形式。多臂老虎机中的探索与利用(exploration vs. exploitation)问题一直以来都是一个特别经典的问题,理解它能够帮助我们学习强化学习。
在多臂老虎机(multi-armed bandit,MAB)问题(见图 2-1)中,有一个拥有
多臂老虎机问题可以表示为一个元组
假设每个时间步只能拉动一个拉杆,多臂老虎机的目标为最大化一段时间步
对于每一个动作
为了知道拉动哪一根拉杆能获得更高的奖励,我们需要估计拉动这根拉杆的期望奖励。由于只拉动一次拉杆获得的奖励存在随机性,所以需要多次拉动一根拉杆,然后计算得到的多次奖励的期望,其算法流程如下所示。
以上 for 循环中的第四步如此更新估值,是因为这样可以进行增量式的期望更新,公式如下。
如果将所有数求和再除以次数,其缺点是每次更新的时间复杂度和空间复杂度均为
下面我们编写代码来实现一个拉杆数为 10 的多臂老虎机。其中拉动每根拉杆的奖励服从伯努利分布(Bernoulli distribution),即每次拉下拉杆有
# 导入需要使用的库,其中numpy是支持数组和矩阵运算的科学计算库,而matplotlib是绘图库import numpy as npimport matplotlib.pyplot as pltclass 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 = Kdef step(self, k):# 当玩家选择了k号拉杆后,根据拉动该老虎机的k号拉杆获得奖励的概率返回1(获奖)或0(未# 获奖)if np.random.rand() < self.probs[k]:return 1else:return 0np.random.seed(1) # 设定随机种子,使实验具有可重复性K = 10bandit_10_arm = BernoulliBandit(K)print("随机生成了一个%d臂伯努利老虎机" % K)print("获奖概率最大的拉杆为%d号,其获奖概率为%.4f" %(bandit_10_arm.best_idx, bandit_10_arm.best_prob))
随机生成了一个10臂伯努利老虎机获奖概率最大的拉杆为1号,其获奖概率为0.7203
接下来我们用一个 Solver 基础类来实现上述的多臂老虎机的求解方案。根据前文的算法流程,我们需要实现下列函数功能:根据策略选择动作、根据动作获取奖励、更新期望奖励估值、更新累积懊悔和计数。在下面的 MAB 算法基本框架中,我们将根据策略选择动作、根据动作获取奖励和更新期望奖励估值放在 run_one_step()
函数中,由每个继承 Solver 类的策略具体实现。而更新累积懊悔和计数则直接放在主循环 run()
中。
class Solver:""" 多臂老虎机算法基本框架 """def __init__(self, bandit):self.bandit = banditself.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 NotImplementedErrordef run(self, num_steps):# 运行一定次数,num_steps为总运行次数for _ in range(num_steps):k = self.run_one_step()self.counts[k] += 1self.actions.append(k)self.update_regret(k)
在 2.2 节的算法框架中,还没有一个策略告诉我们应该采取哪个动作,即拉动哪根拉杆,所以接下来我们将学习如何设计一个策略。例如,一个最简单的策略就是一直采取第一个动作,但这就非常依赖运气的好坏。如果运气绝佳,可能拉动的刚好是能获得最大期望奖励的拉杆,即最优拉杆;但如果运气很糟糕,获得的就有可能是最小的期望奖励。在多臂老虎机问题中,一个经典的问题就是探索与利用的平衡问题。探索(exploration)是指尝试拉动更多可能的拉杆,这根拉杆不一定会获得最大的奖励,但这种方案能够摸清楚所有拉杆的获奖情况。例如,对于一个 10 臂老虎机,我们要把所有的拉杆都拉动一下才知道哪根拉杆可能获得最大的奖励。利用(exploitation)是指拉动已知期望奖励最大的那根拉杆,由于已知的信息仅仅来自有限次的交互观测,所以当前的最优拉杆不一定是全局最优的。例如,对于一个 10 臂老虎机,我们只拉动过其中 3 根拉杆,接下来就一直拉动这 3 根拉杆中期望奖励最大的那根拉杆,但很有可能期望奖励最大的拉杆在剩下的 7 根当中,即使我们对 10 根拉杆各自都尝试了 20 次,发现 5 号拉杆的经验期望奖励是最高的,但仍然存在着微小的概率—另一根 6 号拉杆的真实期望奖励是比 5 号拉杆更高的。
于是在多臂老虎机问题中,设计策略时就需要平衡探索和利用的次数,使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的探索,在对每根拉杆都有比较准确的估计后,再进行利用。目前已有一些比较经典的算法来解决这个问题,例如
完全贪婪算法即在每一时刻采取期望奖励估值最大的动作(拉动拉杆),这就是纯粹的利用,而没有探索,所以我们通常需要对完全贪婪算法进行一些修改,其中比较经典的一种方法为
随着探索次数的不断增加,我们对各个动作的奖励估计得越来越准,此时我们就没必要继续花大力气进行探索。所以在
我们接下来编写代码来实现一个
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"])
psilon-贪婪算法的累积懊悔为:25.526630933945313
通过上面的实验可以发现,在经历了开始的一小段时间后,
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)
通过实验结果可以发现,基本上无论
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 = 0def run_one_step(self):self.total_count += 1if 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 knp.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值衰减的贪婪算法的累积懊悔为:10.114334931260183
从实验结果图中可以发现,随时间做反比例衰减的
设想这样一种情况:对于一台双臂老虎机,其中第一根拉杆只被拉动过一次,得到的奖励为
上置信界(upper confidence bound,UCB)算法是一种经典的基于不确定性的策略算法,它的思想用到了一个非常著名的数学原理:霍夫丁不等式(Hoeffding's inequality)。在霍夫丁不等式中,令
现在我们将霍夫丁不等式运用于多臂老虎机问题中。将
我们编写代码来实现 UCB 算法,并且仍然使用 2.2.4 节定义的 10 臂老虎机来观察实验结果。在具体的实现过程中,设置
class UCB(Solver):""" UCB算法,继承Solver类 """def __init__(self, bandit, coef, init_prob=1.0):super(UCB, self).__init__(bandit)self.total_count = 0self.estimates = np.array([init_prob] * self.bandit.K)self.coef = coefdef run_one_step(self):self.total_count += 1ucb = 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 knp.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"])
上置信界算法的累积懊悔为: 70.45281214197854
MAB 中还有一种经典算法——汤普森采样(Thompson sampling),先假设拉动每根拉杆的奖励服从一个特定的概率分布,然后根据拉动每根拉杆的期望奖励来进行选择。但是由于计算所有拉杆的期望奖励的代价比较高,汤普森采样算法使用采样的方式,即根据当前每个动作
了解了汤普森采样算法的基本思路后,我们需要解决另一个问题:怎样得到当前每个动作
我们编写代码来实现汤普森采样算法,并且仍然使用 2.2.4 节定义的 10 臂老虎机来观察实验结果。
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 knp.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"])
汤普森采样算法的累积懊悔为:57.19161964443925
通过实验我们可以得到以下结论:
探索与利用是与环境做交互学习的重要问题,是强化学习试错法中的必备技术,而多臂老虎机问题是研究探索与利用技术理论的最佳环境。了解多臂老虎机的探索与利用问题,对接下来我们学习强化学习环境探索有很重要的帮助。对于多臂老虎机各种算法的累积懊悔理论分析,有兴趣的同学可以自行查阅相关资料。
多臂老虎机问题与强化学习的一大区别在于其与环境的交互并不会改变环境,即多臂老虎机的每次交互的结果和以往的动作无关,所以可看作无状态的强化学习(stateless reinforcement learning)。第 3 章将开始在有状态的环境下讨论强化学习,即马尔可夫决策过程。
[1] AUER P, CESA-BIANCHI N,FISCHER P. Finite-time analysis of the multiarmed bandit problem[J]. Machine learning,2002, 47 (2) : 235-256.
[2] AUER P. Using confidence bounds for exploitation-exploration trade-offs[J]. Journal of Machine Learning Research,2002, 3(3): 397-422.
[3] GITTINS J, GLAZEBROOK K,WEBER R. Multi-armed bandit allocation indices[M]. 2nd ed. America: John Wiley & Sons, 2011.
[4] CHAPELLE O, LI L. An empirical evaluation of thompson sampling [J]. Advances in neural information processing systems, 2011, 24: 2249-2257.