【强化学习】第二讲——探索与利用exploration vs. exploitation

发布于:2025-03-17 ⋅ 阅读:(13) ⋅ 点赞:(0)

强化学习的核心在于智能体通过与环境的交互进行学习,这种学习方式被称为 试错学习(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根拉杆,那动作空间就是集合\{a_1,a_2,...,a_k\},我们用a_t \in A表示任意一个动作;
  •  R为奖励概率分布,拉动每一根拉杆的动作都对应一个奖励概率分布R(r|a),不同拉杆的奖励分布通常是不同的。

假设每个时间步只能拉动一个拉杆,多臂老虎机的目标为最大化一段时间步T内累积的奖励: max\sum^T_{t=1}r_t,r_t\sim R(\cdot |a_t)。其中a_t表示在第时间步拉动某一拉杆的动作,表示动作获得的奖励。

累积懊悔

对于每一个动作,我们定义其期望奖励为:

E_{a\sim R(\cdot |a)}[r]

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

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

为了更加直观、方便地观察拉动一根拉杆的期望奖励离最优拉杆期望奖励的差距,我们引入懊悔(regret)概念。懊悔定义为拉动当前拉杆的动作a与最优拉杆的期望奖励差,即:

R(a)=Q^*-Q(a) 

累积懊悔(cumulative regret)即操作 T 次拉杆后累积的懊悔总量,对于一次完整的 T 步决策\{a_1,a_2,...,a_T\},累积懊悔为:

 \sigma_R=\sum ^{T}_{t=1}R(a_t)

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

如果一直保持探索性的策略,一定会有一个regret成线性增长。如果一直探索新策略,\sigma_R \propto T \cdot R,total regret将线性递增,无法收敛;如果一直不探索新策略,\sigma_R \propto T \cdot R,total regret仍将线性递增。那么是否存在一个方法具有次线性收敛保证的regret呢?

估计期望奖励

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

  • 对于\forall a\in A,初始化计数器 N(a)=0 和期望奖励估值\hat{Q}(a)=c^i
  • for  t=1\rightarrow T​​​​​​​do
    •  选取某根拉杆,该动作记为 a_t
    •  得到奖励 r_t=Bandint(a)
    •  更新计数器: N(a)=N(a)+1
    •  更新期望奖励估值:\hat{Q}(a)=\hat{Q}(a)+\frac{1}{N(a)}(r-\hat{Q}(a))
  • 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)