RL-Lec9 探索与利用

介绍

所谓利用（Exploitation）是指做出当前信息下的最佳决定，而探索（Exploration）是指尝试不同的行为继而收集更多的信息。一般来说，最好的长期战略通常包含一些牺牲短期利益举措，通过搜集更多的信息使得个体能够达到宏观上的最佳策略。总之，探索和利用是一对矛盾。

例子	利用	探索
饭店搜索	去最喜欢的饭店	尝试一个新饭店
广告投放	投放最成功的广告	尝试一个新的广告投放
钻井探油	在已知最好的位置钻探	在新的位置钻探
玩游戏	采取当前认为的最佳行动	尝试一个新行动

探索原则及其分类

在探索领域，有以下几种基本的探索方法：

朴素探索（Naive Exploration）：在贪婪搜索的基础上增加噪音以实现朴素探索（如 $\varepsilon$-贪婪搜索）
乐观初始估计（Optimistic Initialization）：优先选择当前被认为是最高价值的行为，除非新信息的获取推翻了该行为具有最高价值这一认知。
不确定优先（Optimism in the Face of Uncertainty）：优先尝试不确定价值的行为。
概率匹配（Probability Matching）：根据当前估计的概率分布采样行为。
信息状态搜索（Information State Search）：将已探索的信息作为状态的一部分联合个体的状态组成新的状态，以新状态为基础进行前向探索。

大致上，根据搜索过程中使用的数据结构，可以将搜索分为：

依据状态行为空间的探索（State-Action Exploration）：针对每一个当前的状态，以一定的算法尝试之前该状态下没有尝试过的行为。
参数化搜索（Parameter Exploration）：直接针对策略的函数近似，此时策略用各种形式的参数表达，探索即表现为尝试不同的参数设置。

参数化搜索的优点在于可以得到基于某一策略的一段持续性的行为，其缺点是对个体曾经到过的状态空间毫无记忆，不能利用已经到过的状态信息。

Multi-Armed Bandits

下面以多臂赌博机（Multi-Armed Bandits）为例对探索与利用作进一步分析。

多臂赌博机是由多个独立的单臂赌博机构成，赌博机相当于环境，个体拉下某一单臂赌博机的拉杆表示选择该赌博机，随后该赌博机会给出一个即时奖励 $R$。这里我们假设：

各个单臂赌博机之间是独立的；
同一时刻只能拉下其中一个赌博机的拉杆；
同一赌博机在不同次拉杆给出的即时奖励与先前给出的奖励无关。

注意到，多臂赌博机的回合是以行动和奖励构成的序列，与状态无关。我们的目标自然是使得累计奖励达到最大。

后悔（Regret）

定义仅针对某一行动的值函数 $q(a)$：

$q(a)=\mathbb E(R_t\mid A_t=a),$

即一个行动的价值等于该行动能得到的即时奖励期望。于是我们采取的行动自然是

$a^\star=\max\limits_{a\in\mathcal A}q(a).$

对应的最优价值 $q^\star=q(a^\star)$。但我们事先并不知道各个行动值函数，因此每次拉杆获得的即时奖励与这个最优价值存在差距，定义这个差距为后悔（regret）：

$I_t=\mathbb E[q^\star-q(a_t)].$

于是最大化累计奖励的问题等价于最小化总后悔

$\displaystyle L_t=\mathbb E\left[\sum_{\tau=1}^t(q^\star-q(a_\tau))\right].$

下面从另一个角度重写总后悔。定义：

计数（count）$N_t(a)$ 为到 $t$ 时刻时已执行行动 $a$ 的总次数；
差距（gap）$\Delta_a$ 为最优价值 $q^\star$ 与行动 $a$ 的价值之间的差 $\Delta_a=q^\star-q(a).$

那么总后悔就可以改写为

$\displaystyle L_t=\mathbb E\left[\sum_{\tau=1}^t(q^\star-q(a_\tau))\right]=\sum_{a\in\mathcal A}\mathbb E[N_t(a)]\Delta_a.$

因此，一个好的算法应该尽量减少那些差距较大的行动的次数，不过实际问题中这个差距并不是已知的。

朴素探索

在贪婪算法中，我们总是选择使得行动值函数达到最大的那个行动，即

$\displaystyle a_t^\star=\underset{a\in\mathcal A}{\arg\max}~\hat{q}_t(a)=\underset{a\in\mathcal A}{\arg\max}~\dfrac{1}{N_t(a)}\sum_{\tau=1}^tR_\tau\pmb 1(a_t=a).$

由于这种搜索方法可能永远卡在次优行动，因此总后悔随时间步线性增长。

在 $\varepsilon$-贪婪算法中，我们以 $1-\varepsilon$ 的概率选择使得行动值函数达到最大的那个行动，而以 $\varepsilon$ 的概率随机选择一个行动，此时

$\displaystyle I_t=\mathbb E[q^\star-q(a_t)]=(1-\varepsilon)(q^\star-\hat{q}_t(a))+\dfrac{\varepsilon}{\vert\mathcal A\vert}\sum_{a\in\mathcal A}\Delta_a\geq\dfrac{\varepsilon}{\vert\mathcal A\vert}\sum_{a\in\mathcal A}\Delta_a.$

因此，对于 $\varepsilon$-贪婪算法，总后悔也会呈线性增长。

乐观初始估计

乐观初始估计的主要思想是，在初始时给 $q(a)$ 一个较高的价值，随后使用增量MC评估来更新该行动的价值：

$\hat{q}_t(a_t)=\hat{q}_{t-1}+\dfrac{1}{N_t(a_t)}(R_t-\hat{q}_{t-1}).$

某行动的价值会随着实际获得的即时奖励在初始设置的较高价值基础上不断得到更新，这在一定程度上达到了尽可能尝试所有可能的行动的要求。理论上，这仍是总后悔线性增加的探索方法，但是实际应用效果却非常好，是贪婪算法的一种改进。

衰减 $\varepsilon$-贪婪

衰减 $\varepsilon$-贪婪是对 $\varepsilon$-贪婪的改进，它随着时间的延长逐渐衰减 $\varepsilon$ 的值。

假设事先知道所有行动的差距 $\Delta_a$，则自然想法是一个行动的差距越小，则尝试该行为的机会越多，即

$\varepsilon_t=\min\left\{1,\dfrac{c\vert\mathcal A\vert}{d^2t}\right\},\quad d=\min\limits_{a:\Delta_a>0}\Delta_a,~c>0.$

衰减 $\varepsilon$-贪婪能使得总后悔呈现与时间步的次线性（sublinear）关系，如下图所示。

但是，这种方法需要事先知道所有行动的差距 $\Delta_a$，在实际中不现实。因此，下面考虑在没有即时奖励 $R$ 的信息的情况下，来找到一种具有次线性总后悔的解决多臂赌博机的算法。

不确定优先探索

如果多臂赌博机中某个单臂一直给较高的奖励，而其它单臂则一直给相对较低的奖励，那么选择起来就容易得多了。而如果多个单臂给出的奖励变异程度较大，忽高忽低，而且多个单臂给出的奖励值有很多时候非常接近，那么选择一个价值高的行动可能就要花费很长时间了。

因此，可以通过比较两个单臂价值（均值）的差距 $\Delta_a$ 以及描述其奖励分布的相似程度的KL散度来判断总后悔的下限。

定理.(Lai & Robbins) 存在一个总后悔的下限，任何算法的性能都不能比下述步数对数下限更好，即

$\displaystyle\lim\limits_{t\rightarrow\infty}L_t\geq\log t\sum_{a:\Delta_a>0}\dfrac{\Delta_a}{KL(\mathcal R_a\|\mathcal R_{a^\star})}.$

不确定优先探索的思想是希望优先尝试不确定价值的行为。例如下图中，正确的行动是采取蓝色的单臂，而不是绿色的单臂。因为蓝色单臂的行动价值具有较高的不确定性，以更准确地估计其行动价值，从而尽可能缩小其奖励分布的方差。

注意，上图中的分布并不是奖励的真实分布，而是根据历史信息构建的一个经验分布。

基于这一想法，我们需要考虑估计行动价值在一定可信度上的价值上限，将其作为指导后续行动的参考。考虑对每个行动值估计一个置信上限 $\hat{U}_t(a)$，这个上限将以高的概率满足

$q(a)\leq\hat{q}_t(a)+\hat{U}_t(a).$

直观上可以理解，当某一行动的计数较少时，该行动价值某一可信度的价值上限将偏离均值较多，而随着计数的增多，这种价值上限将越来越接近于均值。因此，我们可以由此来指导行动的选择，即

$a_t=\underset{a\in\mathcal A}{\arg\max}\left(\hat{q}_t(a)+\hat{U}_t(a)\right).$

利用Hoeffding不等式可得

$\mathbb P\left[q(a)>\hat{q}_t(a)+U_t(a)\right]\leq\text{e}^{-2N_t(a)U_t(a)^2}.$

因此若假定行动价值有 $p$ 的概率超过可信区间上界，就可以得到

$U_t(a)=\sqrt{\dfrac{-\log p}{2N_t(a)}}.$

随着时间步的增加，我们逐渐减少 $p$ 值，从而得到最佳行动。在实际中，往往取 $p=t^{-4}$，从而得到UCB1算法：

$a_t=\underset{a\in\mathcal A}{\arg\max}\left(q(a)+\sqrt{\dfrac{2\log t}{N_t(a)}}\right).$

定理. 由UCB1算法设计的探索方法可以使总后悔满足对数渐近关系：

$\displaystyle\lim_{t\rightarrow\infty}L_t\leq 8\log t\sum_{a:\Delta_a>0}\Delta_a.$

Bayesian Bandits

在UCB1算法的基础上，如果我们有先验的奖励分布，则可以计算出更好的界的估计。我们希望在有了历史信息 $h_t={a_1,r_1,\dots,a_{t-1},r_{t-1}}$ 的基础上，对奖励分布 $p(\mathcal R)$ 作更新 $p(\mathcal R\mid h_t)$。

例如，假设其来自独立的正态分布 $q(a)=N(r;\mu_a,\sigma_a^2)$，则后验分布为

$\displaystyle p(\mu_a,\sigma_a^2\mid h_t)\propto p(\mu_a,\sigma_a^2)\prod_{t:a_t=a}N(r_t;\mu_a,\sigma_a^2).$

由此选择均值和一定比例的标准差之和作为UCB算法中的置信上限，即

$a_t=\underset{a\in\mathcal A}{\arg\max}\left(\mu_a+\dfrac{c\sigma_a}{\sqrt{N_t(a)}}\right).$

概率匹配

概率匹配的想法是先估计每一个行动可能是最佳行动的概率，然后依据这个概率来选择后续行动：

$\pi(a\mid h_t)=\mathbb P\left[q(a)>q(a'),\forall a'\neq a\mid h_t\right].$

这个算法意味着越不确定价值的行为有着越高的几率被选择，目的是通过采样减少其不确定性，进而调整后续策略，但是这种后验概率的计算成了一大问题。

汤普森采样（Thompson Sampling）是基于概率匹配的一种实际可行的算法，它考虑

$\pi(a\mid h_t)=\mathbb E_{\mathcal R\vert h_t}[\pmb 1(a=\underset{a\in\mathcal A}{\arg\max}~q(a))].$

其基本步骤如下：

基于历史信息构建各单臂的奖励分布估计，并计算后验概率 $p(\mathcal R\mid h_t)$；
依次从每一个分布中采样得到所有行动对应即时奖励的采样值；
计算行动值函数 $q(a)=\mathbb E[\mathcal R_a]$；
选择最佳行动 $a_t=\underset{a\in\mathcal A}{\arg\max}~q(a)$。

这一算法的采样过程中利用了历史信息得到的分布，同时行动得到的真实奖励值将更新该行动的分布估计。可以证明，汤普森采样可以达到Lai&Robbins的下界。

信息状态搜索

探索的过程之所以有价值是因为它会带来更多的信息。能否量化被探索信息的价值和探索本身的开销，以此来决定是否有探索该信息的必要？这就涉及到信息本身的价值。如果对此实现了量化，那么就可以很轻松地通过优化方式平衡探索与利用。

为了确定信息本身的价值，可以设计一个MDP，将信息作为MDP的状态构建对其价值的估计：

信息状态 $\tilde{s}$ 是关于历史信息的一个统计量，即 $\tilde{s}_t=f(h_t)$；
每个行动会导致信息状态的转移，其概率为 $\tilde{\mathcal P}_{s,s’}^a$，

于是MDP模型为 $\tilde{\mathcal M}=\langle\tilde{\mathcal S},\mathcal A,\tilde{\mathcal P},\mathcal R,\gamma\rangle$。利用状态值函数的近似方法可以实现信息价值的估计。

以Bernoulli Bandits为例，考虑一个即时奖励服从Bernoulli分布的赌博机 $\mathcal R_a=B(\mu_a)$，我们的目标是找到具有较高 $\mu_a$ 的赌博机，从而最小化总后悔。对于这样一个由2个行动组成的行动空间，可以将信息状态描述为 $\tilde{s}=\langle\alpha,\beta\rangle$，其中 $\alpha_a$ 为执行行为 $a$ 得到奖励为0的次数，$\beta_a$ 为执行行为 $a$ 得到奖励为1的次数。解决这一问题的Bayes-Adaptive Bernoulli Bandits算法如下：

Contextual Bandits

语境赌博机（Contextual Bandits）是一个三元组 $\langle\mathcal A,\mathcal S,\mathcal R\rangle$：

$\mathcal A$ 是已知的行动集合；
$\mathcal S=\mathbb P(s)$ 是未知的状态分布；
$\mathcal R_s^a(r)=\mathbb P(r\mid s,a)$ 是未知的奖励分布。

在每一个时间步，环境交互产生状态 $s_t\sim\mathcal S$，个体选择行动 $a_t\in\mathcal A$，进而环境产生奖励 $r_t\sim\mathcal R_{s_t}^{a_t}$，我们的目标是希望累积奖励达到最大。

线性回归与线性UCB

考虑状态行动值函数的参数化表示

$q_\theta(s,a)=\phi(s,a)^\textsf{T}\theta\approx q(s,a)=\mathbb E(r\mid s,a).$

从而根据最小二乘法的思想可以得到

$\displaystyle\theta_t=A_t^{-1}b_t,\quad A_t=\sum_{\tau=1}^t\phi(s_\tau,a_\tau)\phi(s_\tau,a_\tau)^\textsf{T},~b_t=\sum_{\tau=1}^t\phi(s_\tau,a_\tau)r_\tau.$

注意到最小二乘估计本身就是对 $\theta$ 的高斯估计，因此方差的估计即

$\sigma_\theta^2(s_t,a_t)=\phi(s_t,a_t)^\textsf{T}A_t^{-1}\phi(s_t,a_t).$

于是最佳行动的UCB选择是

$a_t=\underset{a\in\mathcal A}{\arg\max}\left(q_\theta(s_t,a)+c\sqrt{\phi(s_t,a)^\textsf{T}A_t^{-1}\phi(s_t,a)}\right).$

MDPs

类似的探索与利用的想法也可以用到马尔可夫决策过程之中：

朴素探索
乐观初始估计
- 无模型强化学习：初始化 $q(s,a)$ 为 $\dfrac{r_{\max}}{1-\gamma}$，然后再使用无模型强化学习算法。
- 基与模型的强化学习：构建最优MDP模型，以过渡到终止状态的奖励为后继状态转移，再利用规划算法求解最优模型。
- 鼓励系统地探索状态和动作空间。
不确定优先
- UCB方法无模型强化学习
- 贝叶斯基与模型的强化学习：获得MDP模型的后验估计，并估计转移和奖励的概率分布，用后验估计为指引探索。
概率匹配
- 汤普森采样：从后验估计中采样MDP，用规划方法求解最优价值函数，进而选择最优行动。
信息状态搜索
- 自适应贝叶斯MDPs：将原始MDPs增强为带有信息状态的MDPs，再对之进行求解（通常使用基于采样的方法来学习）。

后记

本文内容来自中国科学技术大学《强化学习》（2022Fall）课件。

如对本文内容有任何疑问，请联系 watthu@mail.ustc.edu.cn。

Exploration and Exploitation

介绍