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

强化学习的核心在于智能体通过与环境的交互进行学习，这种学习方式被称为 试错学习（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)

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

探索与利用的定义

问题介绍

累积懊悔

估计期望奖励

网站公告

今日签到

热门文章

最新发布