强化学习的核心在于智能体通过与环境的交互进行学习,这种学习方式被称为 试错学习(trial-and-error learning) 。在学习强化学习之前,理解多臂老虎机问题(Multi-Armed Bandit Problem) 是一个很好的起点,因为它可以被视为强化学习的一个简化版本。
与强化学习不同,多臂老虎机问题中不存在状态信息,只有动作和奖励,因此它是“智能体与环境交互学习”的最简单形式。多臂老虎机问题中的 探索与利用(exploration vs. exploitation)是一个经典问题。
探索与利用的定义
利用(Exploitation) : 基于当前已知的信息,选择能够带来最大收益的决策。
- 优势:最大化当前收益。
- 风险:可能错过更优的决策,陷入局部最优。
探索(Exploration) : 尝试新的或不确定的决策,以获取更多信息。
- 优势:可能发现更优的决策,提升长期收益。
- 风险:短期内可能无法获得最大收益。
问题介绍
在多臂老虎机(Multi-Armed Bandit, MAB)问题中,我们面对一台拥有 K 根拉杆的老虎机,每根拉杆都对应一个独立的奖励概率分布 R 。每次拉动一根拉杆,我们都会从该拉杆对应的奖励分布中获得一个奖励。问题的关键在于,这些奖励分布是未知的,而我们的目标是在 T 次操作后,尽可能获得最高的累积奖励。 由于我们不知道每根拉杆的奖励分布,因此需要在探索(exploration) 和利用(exploitation)之间进行权衡:
- 探索 :尝试拉动不同的拉杆,以了解每根拉杆的奖励分布。
- 利用 :根据当前的经验,选择已知奖励最高的拉杆,以最大化当前收益。
多臂老虎机问题的核心在于如何设计一种操作策略,在探索和利用之间找到最佳平衡,从而在 T 次操作后获得最高的累积奖励。
多臂老虎机问题可以表示为一个元组 <A, R>,其中:
- A为动作集合,其中一个动作表示拉动一个拉杆。若多臂老虎机一共有K根拉杆,那动作空间就是集合
,我们用
表示任意一个动作;
- R为奖励概率分布,拉动每一根拉杆的动作都对应一个奖励概率分布
,不同拉杆的奖励分布通常是不同的。
假设每个时间步只能拉动一个拉杆,多臂老虎机的目标为最大化一段时间步T内累积的奖励: 。其中
表示在第时间步拉动某一拉杆的动作,表示动作获得的奖励。
累积懊悔
对于每一个动作,我们定义其期望奖励为:
于是,至少存在一根拉杆,它的期望奖励不小于拉动其他任意一根拉杆,我们将该最优期望奖励表示为:
为了更加直观、方便地观察拉动一根拉杆的期望奖励离最优拉杆期望奖励的差距,我们引入懊悔(regret)概念。懊悔定义为拉动当前拉杆的动作a与最优拉杆的期望奖励差,即:
累积懊悔(cumulative regret)即操作 T 次拉杆后累积的懊悔总量,对于一次完整的 T 步决策,累积懊悔为:
MAB 问题的目标为最大化累积奖励,等价于最小化累积懊悔。
如果一直保持探索性的策略,一定会有一个regret成线性增长。如果一直探索新策略,,total regret将线性递增,无法收敛;如果一直不探索新策略,
,total regret仍将线性递增。那么是否存在一个方法具有次线性收敛保证的regret呢?
估计期望奖励
为了知道拉动哪一根拉杆能获得更高的奖励,我们需要估计拉动这根拉杆的期望奖励。由于只拉动一次拉杆获得的奖励存在随机性,所以需要多次拉动一根拉杆,然后计算得到的多次奖励的期望,其算法流程如下所示。
- 对于
,初始化计数器
和期望奖励估值
- for
do
- 选取某根拉杆,该动作记为
- 得到奖励
- 更新计数器:
- 更新期望奖励估值:
- end for
以上 for 循环中的第四步如此更新估值,是因为这样可以进行增量式的期望更新,公式如下。
在多臂老虎机问题中,我们需要估计每根拉杆的奖励概率分布。如果采用 直接求和再除以次数 的方法,每次更新奖励均值的 时间复杂度 和 空间复杂度 均为 O ( n ),其中 n 是拉杆被拉动的次数。这种方法的缺点是效率较低,尤其是在 n 很大时,计算和存储成本会显著增加。 相比之下,采用 增量式更新 的方法,可以显著提高效率。增量式更新的 时间复杂度 和 空间复杂度 均为 O(1) ,因为每次更新只需要记录当前均值和拉杆被拉动的次数,而不需要存储所有历史数据。下面我们编写代码来实现一个拉杆数为 10 的多臂老虎机。其中拉动每根拉杆的奖励服从伯努利分布(Bernoulli distribution),即每次拉下拉杆有p的概率获得的奖励为 1,有(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)