1.4 探索 - 利用权衡

1.4 探索 - 利用权衡

在转移模型和奖励模型未知的强化学习中，一个根本问题是在以下两种动作选择间做出决策：选择智能体已知会带来高奖励的动作，或者选择奖励未知，但可能会提供信息，帮助智能体进入能获得更高奖励的状态 - 动作空间的动作。这被称为探索 - 利用权衡。在本节中，我们将讨论各种解决方案。

1.4.1 简单启发式方法

我们从基于纯粹利用的策略开始。这就是所谓的贪婪策略，\(a_t = \underset{a}{\arg\max} Q(s, a)\)。我们可以通过偶尔选择其他非贪婪动作来为其添加探索机制。

一种方法是使用\(\epsilon\)-贪婪策略\(\pi_{\epsilon}\)，由\(\epsilon \in [0, 1]\)参数化。在这种情况下，我们以\(1 - \epsilon\)的概率选择关于当前模型的贪婪动作，\(a_t = \underset{a}{\arg\max} \hat{R}_t(s_t, a)\)，以\(\epsilon\)的概率选择随机动作。这个规则确保智能体持续探索所有的状态 - 动作组合。不幸的是，这种启发式方法并非最优，因为它至少以常数概率\(\epsilon/\vert \mathcal{A}\vert\)探索每个动作，不过这可以通过随时间将\(\epsilon\)退火至0来解决。

\(\epsilon\)-贪婪策略的另一个问题是它可能导致 “抖动”，即智能体不断改变其行动决策。在[DOB21]中，他们提出了一个针对此问题的简单解决方案，即\(\epsilon z\)-贪婪策略，它通常效果良好。其思路是，智能体以\(1 - \epsilon\)的概率进行利用，但以\(\epsilon\)的概率进行探索，探索方式是连续\(n \sim z()\)步重复采样到的动作，其中\(z(n)\)是关于重复次数的分布。这可以帮助智能体摆脱局部最小值。

另一种方法是使用玻尔兹曼探索（Boltzmann exploration），它会为更有潜力的动作分配更高的探索概率，同时考虑奖励函数。也就是说，我们使用如下形式的策略：

\[\pi_{\tau}(a\vert s) = \frac{\exp(\hat{R}_t(s_t, a)/\tau)}{\sum_{a'} \exp(\hat{R}_t(s_t, a')/\tau)} \tag{1.34}\]

其中\(\tau > 0\)是温度参数，用于控制分布的熵。当\(\tau\)趋近于0时，\(\pi_{\tau}\)趋近于贪婪策略。另一方面，\(\tau\)值越高，\(\pi(a\vert s)\)的分布就越均匀，从而鼓励更多的探索。如表1.3所示，相较于\(\epsilon\)-贪婪策略，其动作选择概率在奖励估计变化时更加 “平滑”。

玻尔兹曼策略在所有状态下的探索范围相同。另一种替代方法是尝试探索结果可能不确定的（状态，动作）组合。这可以通过使用探索奖励\(R_t^b(s, a)\)来实现，如果我们在状态\(s\)下尝试动作\(a\)的次数较少，这个奖励值就会很大。然后我们可以将\(R_t^b\)加到常规奖励中，以引导智能体的行为，使其有望学习到关于世界的有用信息。这被称为内在奖励函数（5.2.4节）。

1.4.2 基于信念状态马尔可夫决策过程的方法

我们可以通过采用贝叶斯方法来计算探索 - 利用权衡问题的最优解。首先，如1.2.5节所讨论的，计算信念状态马尔可夫决策过程。然后，我们按照下面的说明计算最优策略。

1.4.2.1 多臂老虎机情况（吉廷斯指数）

假设我们有一种方法可以递归地计算关于模型参数的信念状态\(p(\boldsymbol{\theta}_t\vert \mathcal{D}_{1:t})\)。那么，我们如何利用它来求解由此得到的信念状态马尔可夫决策过程中的策略呢？

在无上下文且臂数有限的多臂老虎机这种特殊情况下，可以使用动态规划来计算这个信念状态马尔可夫决策过程的最优策略。结果可以表示为一个每一步动作概率\(\pi_t(a_1, \ldots, a_K)\)的表格，这些概率被称为吉廷斯指数 [Git89]（详细解释见[PR12; Pow22]）。然而，对于一般的上下文多臂老虎机，计算最优策略是难以实现的[PT87]。

1.4.2.2 马尔可夫决策过程情况（贝叶斯自适应马尔可夫决策过程）

我们可以通过构建一个BAMDP（即 “贝叶斯自适应马尔可夫决策过程” [Duf02]）将上述技术扩展到马尔可夫决策过程的情况。然而，求解这个过程在计算上是难以实现的，因此人们提出了各种近似方法（例如见[Zin+21; AS22; Mik+20]）。

1.4.3 上置信界（UCB）

探索 - 利用问题的最优解很难计算。然而，一种直观合理的方法基于 “面对不确定性时持乐观态度”（OFU）的原则。该原则贪婪地选择动作，但基于对动作奖励的乐观估计。这种方法的最优性在[Ten02]的R - Max论文中得到了证明，该论文建立在早期[KS02]的E3论文基础之上。

这个原则最常见的实现基于上置信界（UCB）的概念。我们将首先针对多臂老虎机情况进行解释，然后扩展到马尔可夫决策过程的情况。

1.4.3.1 基本思想

为了使用上置信界（UCB）策略，智能体要维护一个乐观的奖励函数估计值\(\tilde{R}_t\)，使得对于所有的动作\(a\)，\(\tilde{R}_t(s_t, a) \geq R(s_t, a)\)以高概率成立，然后相应地选择贪婪动作：

\[a_t = \underset{a}{\arg\max} \tilde{R}_t(s_t, a) \tag{1.35}\]

UCB可以被看作是一种探索奖励，其中乐观的估计值鼓励智能体进行探索。通常，乐观程度\(\tilde{R}_t - R\)会随着时间降低，这样智能体就会逐渐减少探索。在构建合适的乐观奖励估计值的情况下，UCB策略已被证明在多臂老虎机的许多变体中能实现接近最优的遗憾值[LS19]。（我们在1.1.4节讨论了遗憾值。）

乐观函数\(\tilde{R}\)可以通过不同方式得到，有时能以闭式形式获得，下面我们将进行讨论。

1.4.3.2 多臂老虎机情况：频率学派方法

频率学派计算置信界的方法可以基于集中不等式[BLM16]，来推导估计误差的高概率上界：\(\vert \hat{R}_t(s, a) - R_t(s, a)\vert \leq \delta_t(s, a)\)，其中\(\hat{R}_t\)是\(R\)的常用估计值（通常是最大似然估计值），\(\delta_t\)是经过适当选择的函数。然后通过设置\(\tilde{R}_t(s, a) = \hat{R}_t(s, a) + \delta_t(s, a)\)得到乐观奖励值。

例如，再次考虑无上下文的伯努利多臂老虎机，\(R(a) \sim \text{Ber}(\mu(a))\)。最大似然估计值\(\hat{R}_t(a) = \hat{\mu}_t(a)\)由每次采取动作\(a\)时观测到的奖励的经验平均值给出：

\[\hat{\mu}_t(a) = \frac{N_t^1(a)}{N_t(a)} = \frac{N_t^1(a)}{N_t^0(a) + N_t^1(a)} \tag{1.36}\]

其中\(N_t^r(a)\)是（截至步骤\(t - 1\)）采取动作\(a\)且观测到奖励为\(r\)的次数，\(N_t(a)\)是采取动作\(a\)的总次数：

\[N_t(a) = \sum_{s = 1}^{t - 1} \mathbb{I}(a_s = a) \tag{1.37}\]

然后，切尔诺夫 - 霍夫丁不等式[BLM16]得出对于某个常数\(c\)，\(\delta_t(a) = c / \sqrt{N_t(a)}\)，所以

\[\tilde{R}_t(a) = \hat{\mu}_t(a) + \frac{c}{\sqrt{N_t(a)}} \tag{1.38}\]

1.4.3.3 多臂老虎机情况：贝叶斯方法

我们也可以通过贝叶斯推断来推导上置信界。如果使用贝塔先验，我们可以像公式(1.23)那样以闭式形式计算后验概率。后验均值是\(\hat{\mu}_t(a) = \mathbb{E}[\mu(a)\vert \boldsymbol{h}_t] = \frac{\alpha_t^a}{\alpha_t^a + \beta_t^a}\)，后验标准差近似为

\[\hat{\sigma}_t(a) = \sqrt{\mathbb{V}[\mu(a)\vert \boldsymbol{h}_t]} \approx \sqrt{\frac{\hat{\mu}_t(a)(1 - \hat{\mu}_t(a))}{N_t(a)}} \tag{1.39}\]

对于高斯多臂老虎机，我们可以使用类似的技术，其中\(p_R(R\vert a, \boldsymbol{\theta}) = \mathcal{N}(R\vert \mu_a, \sigma_a^2)\)，\(\mu_a\)是期望奖励，\(\sigma_a^2\)是方差。如果使用共轭先验，我们可以以闭式形式计算\(p(\mu_a, \sigma_a\vert \mathcal{D}_t)\)。使用共轭先验的无信息版本，我们得到\(\mathbb{E}[\mu_a\vert \boldsymbol{h}_t] = \hat{\mu}_t(a)\)，这就是动作\(a\)的奖励的经验均值。该估计的不确定性是均值的标准误差，即\(\sqrt{\mathbb{V}[\mu_a\vert \boldsymbol{h}_t]} = \hat{\sigma}_t(a)/\sqrt{N_t(a)}\)，其中\(\hat{\sigma}_t(a)\)是动作\(a\)的奖励的经验标准差。

一旦我们计算出均值和后验标准差，就将乐观奖励估计值定义为

\[\tilde{R}_t(a) = \hat{\mu}_t(a) + c\hat{\sigma}_t(a) \tag{1.40}\]

其中常数\(c\)控制策略的贪婪程度。相关示例见图1.5。可以看到，这与基于集中不等式的频率学派方法类似，但更具通用性。

图1.5：具有3种不同动作的高斯老虎机的奖励分布\(Q(a)\)，以及相应的置信下限和上限的图示。我们用垂直虚线表示后验均值\(Q(a)=\mu(a)\)，用水平实线表示缩放后的后验标准差\(c\sigma(a)\)。来源于[Sil18]。经David Silver许可使用。

1.4.3.4 马尔可夫决策过程情况

上置信界（UCB）的思想（尤其是频率学派形式）在一些研究中被扩展到了马尔可夫决策过程（MDP）的情况。（贝叶斯版本将在1.4.4节讨论。）例如，[ACBF02]建议将UCB与Q学习相结合，把策略定义为

\[\pi(a\vert s) = \mathbb{I} \left( a = \underset{a'}{\arg\max} Q(s, a') + c\sqrt{\log(t)/N_t(s, a')} \right) \tag{1.41}\]

[AJO08]提出了更复杂的UCRL2算法，该算法在每个回合开始时计算马尔可夫决策过程所有模型参数的置信区间；然后计算由此得到的乐观马尔可夫决策过程，并求解最优策略，用于收集更多数据。

1.4.4 汤普森采样

上置信界（UCB）的一种常见替代方法是使用汤普森采样[Tho33]，也称为概率匹配[Sco10]。我们先从多臂老虎机的情况进行介绍，然后扩展到马尔可夫决策过程（MDP）的情况。更多细节见[Rus+18]。（另见[Ger18]，其中有证据表明人类会使用类似汤普森采样的机制。）

1.4.4.1 多臂老虎机情况

在汤普森采样中，我们将步骤\(t\)的策略定义为\(\pi_t(a\vert s_t, \boldsymbol{h}_t) = p_a\)，其中\(p_a\)是动作\(a\)为最优动作的概率。这个概率可以通过以下公式计算：

\[p_a = \text{Pr}(a = a_*\vert s_t, \boldsymbol{h}_t) = \int \mathbb{I} \left( a = \underset{a'}{\arg\max} R(s_t, a'; \boldsymbol{\theta}) \right) p(\boldsymbol{\theta}\vert \boldsymbol{h}_t) d\boldsymbol{\theta} \tag{1.42}\]

如果后验概率存在不确定性，智能体就会尝试多种不同的动作，从而自动实现探索。随着不确定性降低，智能体将开始利用已有的知识。

为了了解如何实现这种方法，注意我们可以通过使用单个蒙特卡罗样本\(\tilde{\boldsymbol{\theta}}_t \sim p(\boldsymbol{\theta}\vert \boldsymbol{h}_t)\)来计算公式(1.42)中的表达式。然后将这个参数代入奖励模型中，并贪婪地选择最佳动作：

\[a_t = \underset{a'}{\arg\max} R(s_t, a'; \tilde{\boldsymbol{\theta}}_t) \tag{1.43}\]

这种先采样再利用的方法会以恰好符合预期的概率选择动作，因为

这是一个关于概率计算的数学公式，其Markdown格式如下：

\[\begin{align} p_a &= \int \mathbb{I} \left(a = \underset{a'}{\operatorname{argmax}} R(s_t, a'; \tilde{\boldsymbol{\theta}}_t) \right) p(\tilde{\boldsymbol{\theta}}_t\vert h_t) \\ &= \underset{\tilde{\boldsymbol{\theta}}_t \sim p(\boldsymbol{\theta}\vert h_t)}{\operatorname{Pr}} \underset{a'}{\left(a = \operatorname{argmax} R(s_t, a'; \tilde{\boldsymbol{\theta}}_t) \right)} \tag{1.44} \end{align}\]

尽管这种方法很简单，但已证明它能实现最优遗憾值（例如，相关综述见[Rus+18] ）。此外，它非常易于实现，因此在实际中得到广泛应用[Gra+10; Sco10; CL11]。

图1.6：应用于线性高斯上下文老虎机的汤普森采样图示。上下文的形式为\(s_t=(1,t,t^2)\)。(a) 每个摇臂的真实奖励随时间的变化。(b) 每个摇臂的累积奖励随时间的变化。(c) 累积遗憾随时间的变化。由thompson_sampling_linear_gaussian.ipynb生成。

在图1.6中，我们给出了汤普森采样应用于线性回归多臂老虎机的一个简单示例。上下文的形式为\(\boldsymbol{s}_t = (1, t, t^2)\)。真实的奖励函数形式为\(R(\boldsymbol{s}_t, a) = \boldsymbol{w}_a^{\top} \boldsymbol{s}_t\) 。每个臂的权重选择如下：\(\boldsymbol{w}_0 = (-5, 2, 0.5)\)，\(\boldsymbol{w}_1 = (0, 0, 0)\)，\(\boldsymbol{w}_2 = (5, -1.5, -1)\) 。因此我们可以看到，臂0最初表现较差（负偏差较大），但随着时间推移会变好（斜率为正）；臂1没有作用；臂2最初表现较好（正偏差较大），但随着时间推移会变差。所有臂的观测噪声相同，\(\sigma^2 = 1\) 。奖励函数的绘图见图1.6(a) 。我们使用共轭高斯 - 伽马先验并进行精确的贝叶斯更新。汤普森采样很快发现臂1没有作用。最初它更多地选择臂2，但随着问题的非平稳特性显现，它适应了这种特性并切换到臂0，如图1.6(b)所示。在图1.6(c)中，我们展示了蓝色的经验累积遗憾值接近红色的最优下界。

1.4.4.2 马尔可夫决策过程情况（后验采样强化学习）

我们可以将汤普森采样推广到（ episodic，即回合制）马尔可夫决策过程（MDP）的情况，方法是对所有模型参数（奖励函数和转移模型）维护一个后验分布，在每个回合开始时从这个信念状态中采样一个马尔可夫决策过程，求解与采样得到的马尔可夫决策过程相对应的最优策略，使用得到的策略收集新数据，然后在回合结束时更新信念状态。这被称为后验采样强化学习 [Str00; ORVR13; RR14; OVR17; WCM24]。

作为一种计算效率更高的替代方法，也可以对策略或Q函数而不是世界模型维护后验分布；例如，基于认知神经网络 [Osb+23b] 实现该想法的内容见 [Osb+23a]。另一种方法是使用后继特征（4.4.4节），其中假设Q函数具有\(Q^{\pi}(s, a) = \boldsymbol{\psi}^{\pi}(s, a)^{\top} \boldsymbol{w}\)的形式。具体来说，[Jan+19b] 提出了后继不确定性（Successor Uncertainties），他们将\(\boldsymbol{w}\)的不确定性建模为高斯分布，\(p(\boldsymbol{w}) = \mathcal{N}(\boldsymbol{\mu}_{\boldsymbol{w}}, \boldsymbol{\Sigma}_{\boldsymbol{w}})\)。由此，他们可以推导出Q值的后验分布为

\[p(Q(s, a)) = \mathcal{N}(\boldsymbol{\Psi}^{\pi} \boldsymbol{\mu}_{\boldsymbol{w}}, \boldsymbol{\Psi}^{\pi} \boldsymbol{\Sigma}_{\boldsymbol{w}} (\boldsymbol{\Psi}^{\pi})^{\top}) \tag{1.45}\]

其中\(\boldsymbol{\Psi}^{\pi} = [\boldsymbol{\psi}^{\pi}(s, a)]^{\top}\)是一个特征矩阵，每个状态 - 动作对对应一个特征。