1.2 经典示例

1.2 经典示例

在本节中，我们将描述文献中研究过的，针对环境和智能体的不同形式的模型。

1.2.1 部分可观测马尔可夫决策过程

图1.2所示的模型被称为部分可观测马尔可夫决策过程（partially observable Markov decision process，POMDP，发音为“pom-dee-pee”）[KLC98]。通常，环境的动态模型由一个随机转移函数表示，而不是一个将噪声作为输入的确定性函数。我们可以如下推导这个转移函数：

\[p(z_{t + 1}\vert z_t, a_t) = \mathbb{E}_{\epsilon_t^z} \left[\mathbb{I} (z_{t + 1} = W(z_t, a_t, \epsilon_t^z))\right] \tag{1.12}\]

类似地，随机观测函数由下式给出：

\[p(o_{t + 1}\vert z_{t + 1}) = \mathbb{E}_{\epsilon_{t + 1}^o} \left[\mathbb{I} (o_{t + 1} = O(z_{t + 1}, \epsilon_{t + 1}^o))\right] \tag{1.13}\]

请注意，我们可以将这两个分布结合起来，推导出联合世界模型\(p_{WO}(z_{t + 1}, o_{t + 1}\vert z_t, a_t)\)。此外，我们可以使用这些分布来推导环境的非马尔可夫观测分布\(p_{\text{env}}(o_{t + 1}\vert o_{1:t}, a_{1:t})\)，如公式(1.4)中所使用的，如下所示：

\[\begin{align} p_{\text{env}}(o_{t + 1}\vert o_{1:t}, a_{1:t}) &= \sum_{z_{t + 1}} p(o_{t + 1}\vert z_{t + 1})p(z_{t + 1}\vert a_{1:t}) \tag{1.14}\\ p(z_{t + 1}\vert a_{1:t}) &= \sum_{z_1} \cdots \sum_{z_t} p(z_1\vert a_1)p(z_2\vert z_1, a_1) \cdots p(z_{t + 1}\vert z_t, a_t) \tag{1.15} \end{align}\]

如果世界模型（\(p(o\vert z)\)和\(p(z'\vert z, a)\)两者）是已知的，那么原则上，我们可以求解最优策略。该方法要求智能体的内部状态对应于信念状态\(s_t = b_t = p(z_t\vert h_t)\)，其中\(h_t = (o_{1:t}, a_{1:t - 1})\)是观测历史。信念状态可以使用贝叶斯法则递归更新。详见1.2.5节中的详细信息。信念状态构成了最优策略的充分统计量。不幸的是，计算信念状态以及由此产生的最优策略是极其困难的[PT87; KLC98]。我们将在1.3.4节中讨论一些近似方法。

1.2.2 马尔可夫决策过程（MDPs）

马尔可夫决策过程[Put94]是部分可观测马尔可夫决策过程（POMDP）的一种特殊情况，在马尔可夫决策过程中环境状态是可观测的，所以\(z_t = o_t = s_t\)⁴。我们通常根据世界模型诱导的状态转移矩阵来定义一个马尔可夫决策过程：

\[p_S(s_{t + 1}\vert s_t, a_t) = \mathbb{E}_{\epsilon_t^s} \left[\mathbb{I} (s_{t + 1} = W(s_t, a_t, \epsilon_t^s))\right] \tag{1.16}\]

作为观测模型的替代，我们假设环境（与智能体不同）发出一个奖励信号，该信号从\(p_R(r_t\vert s_t, a_t, s_{t + 1})\)中采样得到。那么期望奖励由下式给出：

\[\begin{align} R(s_t, a_t, s_{t + 1}) &= \sum_{r} r \ p_R(r\vert s_t, a_t, s_{t + 1}) \tag{1.17}\\ R(s_t, a_t) &= \sum_{s_{t + 1}} p_S(s_{t + 1}\vert s_t, a_t)R(s_t, a_t, s_{t + 1}) \tag{1.18} \end{align}\]

给定一个随机策略\(\pi(a_t\vert s_t)\)，智能体可以与环境进行多步交互。每一步称为一次转移，由元组\((s_t, a_t, r_t, s_{t + 1})\)组成，其中\(a_t \sim \pi(\cdot\vert s_t)\)，\(s_{t + 1} \sim p_S(s_t, a_t)\)，且\(r_t \sim p_R(s_t, a_t, s_{t + 1})\)。因此，在策略\(\pi\)下，生成长度为\(T\)的轨迹\(\tau = (s_0, a_0, r_0, s_1, a_1, r_1, s_2, \ldots, s_T)\)的概率可以明确地写为：

\[p(\tau) = p_0(s_0) \prod_{t = 0}^{T - 1} \pi(a_t\vert s_t)p_S(s_{t + 1}\vert s_t, a_t)p_R(r_t\vert s_t, a_t, s_{t + 1}) \tag{1.19}\]

一般来说，马尔可夫决策过程的状态集和动作集可以是离散的或连续的。当这两个集合都是有限的时候，我们可以将这些函数表示为查找表，这被称为表格表示。在这种情况下，我们可以将马尔可夫决策过程表示为一个有限状态机，它是一个图，其中节点对应状态，边对应动作以及相应的奖励和下一个状态。图1.3给出了一个具有3个状态和2个动作的马尔可夫决策过程的简单示例。

图1.3：将马尔可夫决策过程（MDP）表示为有限状态机（FSM）的图示。该MDP有三个离散状态（绿色圆圈）、两个离散动作（橙色圆圈）和两个非零奖励（橙色箭头）。黑色边线上的数字表示状态转移概率，例如，\(p(s' = s_0\vert a = a_0,s' = s_0)=0.7\)；大多数状态转移是不可能的（概率为0），因此图是稀疏的。黄色波浪边线上的数字表示期望奖励，例如，\(R(s = s_1,a = a_0,s' = s_0)= + 5\)；零奖励的状态转移未标注。来源于https://en.wikipedia.org/wiki/Markov_decision_process 。经维基百科作者waldoalvarez许可使用。

如果我们知道世界模型\(p_S\)和\(p_R\)，并且状态和动作空间是表格形式的，那么我们可以使用动态规划技术来求解最优策略，正如我们将在2.2节中讨论的那样。然而，通常世界模型是未知的，并且状态和动作可能需要复杂的非线性模型来表示它们的转移。在这种情况下，我们将不得不使用强化学习方法来学习一个好的策略。

1.2.3 上下文马尔可夫决策过程

上下文马尔可夫决策过程[HDCＭ15]是一种马尔可夫决策过程，其环境的动态和奖励依赖于一个称为上下文的隐藏静态参数。（这与1.2.4节中讨论的上下文多臂老虎机不同，在上下文多臂老虎机中，每一步的上下文都是可观测的。）上下文马尔可夫决策过程的一个简单例子是视频游戏，游戏的每一关都是程序生成的，也就是说，每次智能体开始新的一局时都是随机生成的。因此，智能体必须解决一系列从共同分布中抽取的相关马尔可夫决策过程问题。这要求智能体能够在多个马尔可夫决策过程中进行泛化，而不是过度拟合特定的环境[Cob+19; Kir+21; Tom+22]。（这种泛化形式不同于马尔可夫决策过程内部的泛化，马尔可夫决策过程内部的泛化要求在状态间进行泛化，而不是在不同环境间；两者都很重要。）

上下文马尔可夫决策过程是一种特殊的部分可观测马尔可夫决策过程，其中隐藏变量对应于模型的未知参数。在[Gho+21]中，他们将其称为认知部分可观测马尔可夫决策过程（epistemic POMDP），这与我们将在1.2.5节中讨论的信念状态马尔可夫决策过程的概念密切相关。

1.2.4 上下文多臂老虎机

上下文多臂老虎机是部分可观测马尔可夫决策过程（POMDP）的一种特殊情况，在这种情况下，世界状态转移函数与智能体的动作以及前一状态无关，即\(p(z_t\vert z_{t - 1}, a_t) = p(z_t)\)。在这种情况下，我们将世界状态称为“上下文”，并且这些上下文对智能体是可观测的，即\(o_t = z_t\)。由于世界状态分布与智能体的动作无关，所以智能体的动作对外部环境没有影响。然而，其动作确实会影响它获得的奖励。因此，随着智能体学习世界模型（见1.2.5节），智能体关于潜在奖励函数\(R(o, a)\)的内部信念状态会随时间发生变化。

上下文多臂老虎机的一种特殊情况是常规多臂老虎机，在常规多臂老虎机中没有上下文，或者等价地说，\(s_t\)是某个固定不变的常量。当可能的动作数量有限，\(\mathcal{A} = \{a_1, \ldots, a_K\}\)时，这被称为多臂老虎机⁵。在这种情况下，奖励模型具有\(R(a) = f(\boldsymbol{w}_a)\)的形式，其中\(\boldsymbol{w}_a\)是动作\(a\)对应的参数。

上下文多臂老虎机有许多应用。例如，考虑一个在线广告系统。在这种情况下，状态\(s_t\)表示用户当前正在浏览的网页的特征，动作\(a_t\)表示系统选择展示的广告。由于广告的相关性取决于页面，所以奖励函数具有\(R(s_t, a_t)\)的形式，因此该问题是上下文相关的。目标是最大化期望奖励，这等同于人们点击广告的期望次数，这被称为点击率（CTR）。（例如，可参考[Gra+10; Li+10; McM+13; Aga+14; Du+21; YZ22]获取关于此应用的更多信息。）上下文多臂老虎机的另一个应用是在临床试验中[VBW15]。在这种情况下，状态\(s_t\)是我们正在治疗的当前患者的特征，动作\(a_t\)是医生选择给予患者的治疗方式（例如，一种新药或安慰剂）。

有关多臂老虎机的更多详细信息，例如可参考[LS19; Sli19]。

1.2.5 信念状态马尔可夫决策过程

在本节中，我们将描述一种马尔可夫决策过程，其中状态表示一种概率分布，称为信念状态或信息状态，当智能体从环境中获取信息时，它会（在其“脑海中”）更新该状态⁶。更准确地说，考虑一个上下文多臂老虎机问题，智能体通过函数\(R(o, a) = f(o, a; \boldsymbol{w})\)来近似未知的奖励。我们用\(\boldsymbol{b}_t = p(\boldsymbol{w}\vert \boldsymbol{h}_t)\)表示未知参数的后验概率，其中\(\boldsymbol{h}_t = \{o_{1:t}, a_{1:t}, r_{1:t}\}\)是过去的观测、动作和奖励的历史记录。这个信念状态可以使用贝叶斯法则进行确定性更新，我们将这个操作记为\(\boldsymbol{b}_{t + 1} = \text{BayesRule}(\boldsymbol{b}_t, o_{t + 1}, a_{t + 1}, r_{t + 1})\)。（这与前面定义的状态更新\(SU\)相对应。）利用这一点，我们可以定义如下的信念状态马尔可夫决策过程，其确定性动态由下式给出：

\[p(\boldsymbol{b}_{t + 1}\vert \boldsymbol{b}_t, o_{t + 1}, a_{t + 1}, r_{t + 1}) = \mathbb{I}(\boldsymbol{b}_{t + 1} = \text{BayesRule}(\boldsymbol{b}_t, o_{t + 1}, a_{t + 1}, r_{t + 1})) \tag{1.20}\]

奖励函数由下式给出：

\[p(r_t\vert o_t, a_t, \boldsymbol{b}_t) = \int p_R(r_t\vert o_t, a_t; \boldsymbol{w})p(\boldsymbol{w}\vert \boldsymbol{b}_t) d\boldsymbol{w} \tag{1.21}\]

如果我们能够求解这个（部分可观测）马尔可夫决策过程((P)OMDP)，我们就能得到探索 - 利用问题的最优解。

作为一个简单的例子，考虑一个无上下文的伯努利多臂老虎机问题，其中\(p_R(r\vert a) = \text{Ber}(r\vert \mu_a)\)，且\(\mu_a = p_R(r = 1\vert a) = R(a)\)是采取动作\(a\)的期望奖励。唯一未知的参数是\(\boldsymbol{w} = \mu_{1:A}\)。假设我们使用一个分解的贝塔先验：

\[p_0(\boldsymbol{w}) = \prod_{a} \text{Beta}(\mu_a\vert \alpha_0^a, \beta_0^a) \tag{1.22}\]

其中\(\boldsymbol{w} = (\mu_1, \ldots, \mu_K)\)。我们可以通过闭式计算后验概率，得到：

\[p(\boldsymbol{w}\vert \mathcal{D}_t) = \prod_{a} \text{Beta}(\mu_a\vert \underbrace{\alpha_0^a + N_t^0(a)}_{\alpha_t^a}, \underbrace{\beta_0^a + N_t^1(a)}_{\beta_t^a}) \tag{1.23}\]

其中

\[N_t^r(a) = \sum_{i = 1}^{t - 1} \mathbb{I}(a_i = a, r_i = r) \tag{1.24}\]

图1.4：双臂beta-伯努利老虎机的顺序信念更新图示。动作1的奖励先验是（蓝色）均匀分布\(Beta(1,1)\)；动作2的奖励先验是（橙色）单峰分布\(Beta(2,2)\)。我们根据选择的动作以及观察到的奖励是成功（1）还是失败（0）来更新信念状态的参数。

图1.4展示了双臂伯努利多臂老虎机的情况。对于高斯多臂老虎机，我们可以使用类似的方法，其中\(p_R(r\vert a) = \mathcal{N}(r\vert \mu_a, \sigma_a^2)\)。

在上下文多臂老虎机的情况下，问题在概念上是相同的，但在计算上变得更加复杂。如果我们假设是线性回归多臂老虎机，\(p_R(r\vert s, a; \boldsymbol{w}) = \mathcal{N}(r\vert \boldsymbol{\phi}(s, a)^{\top}\boldsymbol{w}, \sigma^2)\)，我们可以使用贝叶斯线性回归通过闭式精确计算\(p(\boldsymbol{w}\vert \mathcal{D}_t)\)。如果我们假设是逻辑回归多臂老虎机，\(p_R(r\vert s, a; \boldsymbol{w}) = \text{Ber}(r\vert \sigma(\boldsymbol{\phi}(s, a)^{\top}\boldsymbol{w}))\)，则必须使用近似贝叶斯逻辑回归方法来计算\(p(\boldsymbol{w}\vert \mathcal{D}_t)\)。如果我们有一个形式为\(p_R(r\vert s, a; \boldsymbol{w}) = \mathcal{N}(r\vert f(s, a; \boldsymbol{w}))\)的神经多臂老虎机，其中\(f\)是某个非线性函数，那么后验推断就更具挑战性（这等同于贝叶斯神经网络中的推断问题，例如可参考[Arb+23]的离线情况综述文章，以及[DMKM22; JCM24]的一些近期在线方法）。

我们可以将上述方法推广，以计算马尔可夫决策过程中奖励函数和状态转移函数参数的信念状态。

一旦我们计算出信念状态，就可以使用诸如上置信界算法（UCB，见1.4.3节）或汤普森采样（见1.4.4节）等方法推导出具有最优遗憾值的策略。

1.2.6 优化问题

多臂老虎机问题是这样一类问题的示例：智能体必须与环境交互以收集信息，但除此之外不会对环境产生影响。因此，智能体的内部信念状态会随时间变化，而环境状态却不会⁷。当我们试图优化一个固定但未知的函数\(R\)时，这类问题经常出现。我们可以通过在不同的点（参数值）上对函数进行评估来 “查询” 它，在某些情况下，得到的观测结果可能还包括梯度信息。智能体的目标是尽可能少的步骤内找到函数的最优解。下面我们给出这种问题设定的一些示例。

1.2.6.1 最优臂识别

在标准的多臂老虎机问题中，我们的目标是最大化期望奖励之和。然而，在某些情况下，目标是在给定\(T\)次试验的固定预算下确定最优的臂；这个变体被称为最优臂识别[ABM10]。形式上，这对应于优化最终奖励准则：

\[V_{\pi, \pi_T} = \mathbb{E}_{p(a_{1:T}, r_{1:T}\vert s_0, \pi)} [R(\hat{a})] \tag{1.25}\]

其中\(\hat{a} = \pi_T(a_{1:T}, r_{1:T})\)是由终端策略\(\pi_T\)应用于探索策略\(\pi\)获得的观测序列后计算出的估计最优臂。这可以通过对标准多臂老虎机问题所用方法进行简单调整来解决。

1.2.6.2 贝叶斯优化

贝叶斯优化是一种无梯度的方法，用于优化计算成本高昂的黑盒函数。也就是说，我们希望找到

\[\boldsymbol{w}^* = \underset{\boldsymbol{w}}{\arg\max} R(\boldsymbol{w}) \tag{1.26}\]

对于某个未知函数\(R\)，其中\(\boldsymbol{w} \in \mathbb{R}^N\)，并且尽可能少地进行操作（对\(R\)的函数评估）。这本质上是最优臂识别问题的 “无限臂” 版本[Tou14]，我们将离散的臂选择\(a \in \{1, \ldots, K\}\)替换为参数向量\(\boldsymbol{w} \in \mathbb{R}^N\)。在这种情况下，如果智能体的状态\(s_t\)是关于未知函数的信念状态，即\(s_t = p(R\vert \boldsymbol{h}_t)\)，就可以计算最优策略。表示这种分布的一种常见方法是使用高斯过程。然后我们可以使用诸如期望改进、知识梯度或汤普森采样等启发式方法来实现相应的策略，\(\boldsymbol{w}_t = \pi(s_t)\)。具体细节可参考[Gar23]等资料。

1.2.6.3 主动学习

主动学习与贝叶斯优化相似，但我们不是试图找到函数值最大的点（即\(\boldsymbol{w}^*\)），而是试图通过在不同的点\(\boldsymbol{w}_t\)查询函数来学习整个函数\(R\)。同样，最优策略需要维持关于未知函数的信念状态，但现在最优策略采用不同的形式，例如选择查询点以降低信念状态的熵。具体可参考[Smi+23]等资料。

1.2.6.4 随机梯度下降（SGD）

最后，我们按照[Pow22]的思路，讨论如何将随机梯度下降解释为一个序贯决策过程。动作空间包括在位置\(\boldsymbol{a}_t = \boldsymbol{w}_t\)查询未知函数\(R\)，并观测函数值\(r_t = R(\boldsymbol{w}_t)\)；然而，与贝叶斯优化不同的是，现在我们还观测相应的梯度\(\boldsymbol{g}_t = \left.\nabla_{\boldsymbol{w}}R(\boldsymbol{w})\right\vert _{\boldsymbol{w}_t}\)，它提供了关于函数的非局部信息。环境状态包含用于根据智能体的动作生成观测值的真实函数\(R\)。智能体状态包含当前的参数估计值\(\boldsymbol{w}_t\)，还可能包含其他信息，例如像Adam等方法所需的一阶矩\(\boldsymbol{m}_t\)和二阶矩\(\boldsymbol{v}_t\)。（标准随机梯度下降的）更新规则形式为\(\boldsymbol{w}_{t + 1} = \boldsymbol{w}_t + \alpha_t\boldsymbol{g}_t\)，其中步长\(\alpha_t\)由策略选择，\(\alpha_t = \pi(s_t)\)。终端策略形式为\(\pi(s_T) = \boldsymbol{w}_T\)。

尽管原则上可以使用强化学习来学习学习率（步长）策略（例如见[Xu+17]），但该策略通常是手动选择的，要么使用学习率调度，要么是某种手动设计的自适应学习率策略（例如，基于二阶曲率信息）。