第7章：应用，再探讨

现在我们已经回顾了一系列问题背景，接下来我们将暂停一下，利用这些应用来更深入地阐述我们在第 1 章中提到的一些建模问题。

从第 1 章的库存问题开始，我们现在已经涵盖了六类序贯决策问题。对于每个问题，我们都展示了一到两种决策策略：

• 第 1 章） 库存问题——我们通过一个简单库存问题的多种变体，介绍了序贯决策问题。策略包括补货至目标水平策略，以及一种基于调整后预测的策略。
• 第 2 章） 出售资产——我们必须决定何时出售一项金融资产。策略包括低买高卖策略的多种变体。
• 第 3 章） 自适应市场规划——该问题使用了基于导数的随机搜索，其中序贯决策问题是选择步长，我们用简单的参数化函数进行了说明。
• 第 4 章） 学习最佳糖尿病治疗方案——这是一个经典的主动学习问题，被称为多臂赌博机问题。我们设计了基于参数化优化问题的策略。
• 第 5 章） 静态随机最短路径——我们使用经典的动态规划递归精确求解了某一特定版本的随机最短路径问题的最优解，然后引入了一个更复杂的随机版本，我们利用决策后状态变量，通过近似动态规划求解了该问题。
• 第 6 章） 动态随机最短路径——这里我们转向了一个动态最短路径问题，其中路径预期成本的估计值会随时间演变（在第 5 章的静态情形中，我们对预期成本的估计并不发生变化）。我们用这个问题来说明基本的确定性前瞻策略，以及一种参数化前瞻策略。

在前面，我们介绍了四类策略。在迄今为止我们回顾的这些应用中，我们已经看到了这四类策略中每一类的示例。在本章中，我们将更深入地回顾这四类策略，然后再回到我们的一系列应用，为每个建议的策略确定其所属的类别。

四类策略

我们首先注意到，这四类策略可以分为两大类：策略搜索类和前瞻类。这两大类又可以各自进一步细分为两类，从而形成了这四类策略。下面对它们做更详细的说明。

策略搜索

“策略搜索”类策略包括在一组用于做决策的函数中进行搜索，以找到平均表现最好的函数，所使用的目标取决于具体问题的适用性。多数情况下，这意味着要在一组表征参数化策略的参数中搜索最佳取值，但这也意味着我们可能需要评估不同的参数化形式。

策略搜索类策略可以分为两类：

• 策略函数近似（PFAs）——这些是将状态直接映射为行动的解析函数。一些例子包括：
  • 一个参数化函数，例如第 2 章中给出的“高—低”策略，我们在此重复列出
  \[X^{high-low}(S_t\vert \theta^{high-low}) = \begin{cases} 1 & \text{if } p_t < \theta^{low} \text{ or } p_t > \theta^{high}, \\ 1 & \text{if } t=T, \\ 0 & \text{otherwise.}\end{cases}\]

  其中 $\theta^{sell-low} = (\theta^{low},\theta^{high})$。其他例子包括我们在第 1 章中看到的补货至目标水平策略，以及调整后预测策略。

  • 一个线性函数，例如
  \[X^\pi(S_t\vert \theta) = \theta_0 + \theta_1 \phi_1(S_t) + \theta_1 \phi_1(S_t) + \ldots + \theta_F \phi_F(S_t)\]

  其中 $(\phi_f(S_t)),~f=1, \ldots, F$ 是一组特征（“线性”是指关于参数向量 $\theta$ 是线性的——特征 $\phi_f(S_t)$ 本身在 $S_t$ 中可以是高度非线性的）。例如，我们可能要决定为在网站上投放一部电影广告出价多少，而某个特征可能是这部电影的类型或主演演员的姓名。

  线性函数（也称为“仿射策略”）很受欢迎，但请注意，你不能用线性函数来近似上面所示的低买高卖策略或补货至目标水平策略这类阶跃函数。

  • 高级函数，例如局部线性函数或神经网络，尽管这些函数通常拥有大量需要调节的参数（例如神经网络中的权重）。
• 成本函数近似（CFAs）——这些策略需要求解一个参数化的优化问题，我们可能对目标函数或约束条件进行参数化。CFAs 为求解高维决策问题打开了大门。一些例子包括：
  • 一个参数化成本函数近似的简单例子，是我们在第 4 章中介绍的区间估计策略，在此重复列出
  \[X^{IE}(S^n\vert \theta^{IE}) = \argmax_{x\in\Xcal} \left(\mubar^n_x + \theta^{IE} \sigmabar^n_x \right).\]
  • 参数化优化模型——我们在第 6 章中选择链路成本的第 $\theta$ 百分位数时见过这种做法。这是业界广泛使用的一种启发式方法，但一直被研究文献所忽视。航空公司利用这一思路，在遇到重大天气延误时优化其飞机和机组人员的调度。规划发电机组调度的电网运营商会加入备用容量，以确保在某台发电机组发生故障时仍能满足需求。

PFAs 和 CFAs 都有需要调节的参数。二者唯一的区别在于策略是否包含一个内嵌的优化问题。二者都极为强大，并在不同场景中被广泛使用。

前瞻近似

基于前瞻近似的策略，是通过近似当前所做决策的下游成本（或奖励）来构建的，随后将其与初始决策的初始成本（或奖励）一并加以考虑。

• 基于值函数近似（VFAs）的策略——这些是基于贝尔曼方程的策略。针对确定性问题，贝尔曼方程最基本的形式最早在第 5 章中给出，如下：

在许多问题中，向 $S_{t+1}$ 的转移涉及在时刻 $t$ 尚不为人所知的信息（包含在 $W_{t+1}$ 中），这意味着 $S_{t+1}$ 在时刻 $t$ 是一个随机变量。在这种情况下，我们必须像之前那样插入一个期望，从而得到

在实践中，我们通常必须用一个近似值 $\Vbar_{t+1}(S_{t+1})$ 来替代值函数 $V_{t+1}(S_{t+1})$，正如我们在第 5 章近似动态规划一节中所做的那样。研究这些近似方法的领域有多种称呼，例如近似动态规划、强化学习（起源于计算机科学）以及自适应动态规划（工程控制领域所使用的术语）。在这种情况下，策略可写为

如果我们使用决策后状态 $S^x_t$，就可以将我们的策略写为

这正是我们在第 5 章中所展示的内容。

我们用确定性最短路径问题来展示了一个值函数可以被精确计算的应用示例。在随机性问题中，有时也可以做到这一点，但在大多数应用中，只能近似地进行计算。挑战在于要进行足够高质量的计算，从而产生有效的策略。

一种流行的值函数近似策略是使用如下线性模型

其中 $(\phi_f(S^x_t))_{f\in\Fcal}$ 是一组用户自定义的特征，$\theta^{VFA}$ 是使用近似动态规划算法选定的一组参数。

我们通过收集处于状态 $S^n_t$ 时的值 $\vhat^n_t$ 的“观测值”来拟合该线性模型，这些观测值来自第 $n$ 次迭代。设 $\thetabar^{VFA,n-1}$ 为经过 $n-1$ 次更新后对 $\theta^{VFA}$ 的估计值。存在一些方法，可以利用 $\vhat^n_t$ 轻松更新 $\thetabar^{VFA,n-1}$ 并得到 $\thetabar^{VFA,n}$。这样我们就得到了一个可以写成如下形式的 VFA 策略

使用线性模型近似值函数一直非常流行，但对于所得解的质量，几乎没有任何理论保证。更糟糕的是，有经验证据表明这种方法得到的结果可能相当差。然而，由于它是一种能够轻松“得出一个数值”的方法，因此仍然十分流行。

如今同样流行的做法是使用神经网络（尤其是深度神经网络）来近似值函数。神经网络之所以具有吸引力，是因为它们无需为 $f\in\Fcal$ 设计特征集 $(\phi_f(S_t))$。但必须谨慎行事，尤其是当我们必须处理带噪声的值函数观测值时，因为神经网络极大的灵活性可能导致过拟合。

• 直接前瞻近似（DLAs）——前三类策略都需要找到某种形式的函数近似：策略本身（对于 PFAs）、被优化的函数（对于 CFAs），或处于下游状态的价值（对于 VFAs）。然而，有许多问题是无法找到这类函数近似的。

  求解 DLA 的“正确”方式，是从状态 $S_t$ 出发、采取行动 $x_t$、然后观测随机信息 $W_{t+1}$ 之后所产生的状态 $S_{t+1}$ 开始，去求解未来的真实问题。困难之处在于，除了要对未来的不确定性 $W_{t+1}, W_{t+2}, \ldots$ 建模之外，我们还必须做出最优决策 $x_{t+1}, x_{t+2}, \ldots$，而每一个决策都依赖于未来的状态 $S_{t+1}, S_{t+2}, \ldots$，而这些状态都是随机的。

  尽管这看起来相当繁琐（甚至令人望而生畏），该策略意味着要求解

如果我们能够计算方程 $\eqref{eq:policiesDLA}$，我们就得到了一个最优策略。然而方程 $\eqref{eq:policiesDLA}$ 能被精确求解的情形十分罕见。第 5 章中的基本随机最短路径问题就是一个例子，但这是因为其中的不确定性以一种特别简单的方式出现。

在大多数应用中，我们是通过求解一个近似的前瞻模型来求解 $\eqref{eq:policiesDLA}$。我们不再采用如下的状态、决策与信息序列

而是为在时刻 $t$ 求解的模型创建一组简化的状态、决策与信息，用如下形式表示

其中 $\Stilde_{tt’}$ 通常是我们在时刻 $t$ 做出决策时、为前瞻模型中时刻 $t’$ 所创建的简化状态变量。$\xtilde_{tt’}$ 是我们为前瞻模型中时刻 $t’$ 所创建的（可能经过简化的）决策，$\Wtilde_{tt’}$ 是前瞻模型中时刻 $t’$ 的简化信息过程。决策 $\xtilde_{tt’}$ 是使用一个前瞻策略 $\Xtilde^{\tilde \pi}_t(\Stilde_{tt’})$ 做出的，该策略通常是一个因易于计算而被选定的简化策略。

基于我们的近似前瞻模型所得到的策略可写作

方程 $\eqref{eq:policiesapproximateDLA}$ 通过图 7.1 中的决策树加以说明，展示了在展望未来时对状态、决策与不确定性使用近似的方式。构建这些近似需要艺术与科学的结合。我们希望在准确建模未来与兼顾计算需求之间取得平衡。

前瞻策略 $\tilde \pi$（有时称为“策略中的策略”）的设计高度依赖于具体问题。事实上，我们可以使用我们四类策略中的任意一类。关键在于它必须在计算上简单易行，因为我们将需要多次对其进行计算。请记住，前瞻模型不必是精确的（在大多数情况下，如果我们试图使用一个精确的前瞻模型，我们根本无法求解它）。相反，我们所选择的是我们认为能够为当前产生良好决策的近似方法，其手段是对我们可能在未来做出的决策进行近似。

我们已经见识过这种方法的应用。对于第 6 章中的动态最短路径问题,我们采用了一种广泛使用的方法,即求解一个确定性前瞻模型,其中我们取未来可能发生情况的最佳估计,并求解一个确定性优化问题。这种方法忽略了未来不确定性的影响,但我们引入了使用参数化确定性优化问题的思想。然而,我们必须调整这个参数。

这四类策略(PFA、CFA、VFA 和 DLA)是普适的,也就是说,为某个序贯决策问题(任何序贯决策问题)所选择的策略都将属于这四类之一。然而,这些策略类别也可以作为混合策略的构建模块。

我们已经展示了所有四类策略,这就引出了一个问题:你怎么知道该使用哪一类?有时这看起来很明显,例如寻找到目的地的最佳路径。对于这类问题,直接前瞻是一个自然的选择。但也存在这样的问题,即四类策略中的任何一类都是可行的候选方案。

我们成功展示了全部四类策略的两个问题是第 1 章中的库存问题,以及第 4 章中的糖尿病学习问题。关键在于要认真思考全部四类策略,而不是只关注其中一类,而这恰恰是当今经常发生的情况。

模型再探

在本节中,我们将对不同的应用进行一次巡礼,首先从状态变量的回顾开始。然后我们将回顾不同的策略,并将我们所见过的策略归入这四个类别。

状态变量再探

学术文献中关于状态变量含义的说法相当混乱,这一点从动态规划、随机规划和强化学习相关书籍中普遍缺乏对状态变量的定义就可以看出。

对这种模式唯一的例外——也确实非常突出——是最优控制文献,其中状态变量的定义相当常见。在控制学界,状态变量通常被定义为”在时间 $t$ 我们需要知道的、用以对系统从时间 $t$ 起向前建模的全部信息”。然而,其中缺失的是对究竟需要哪些信息才能对系统从时间 $t$ 起向前建模的确切描述。

我们定义了两个版本的状态变量(取自《Reinforcement Learning and Stochastic Optimization》第 9.4 节):

状态变量是:

a) 依赖于策略的版本 —— 历史的一个函数,它与外源信息(以及某个策略)相结合后,足以且必要地用来计算成本/贡献函数、决策函数(即策略),以及转移函数为对成本/贡献函数和决策函数所需信息进行建模而需要的任何信息。

b) 优化版本 —— 历史的一个函数,它足以且必要地用来计算成本/贡献函数、约束条件,以及转移函数为对成本/贡献函数和约束条件所需信息进行建模而需要的任何信息。

我们之所以需要这两个版本,是因为如果我们所研究的系统已经指定了某种策略的结构,我们就需要确保纳入该策略所需的任何信息。例如,我们可能有一个库存问题,考虑两种策略:一种使用未来需求的预测,另一种只使用一种补货至某水平的策略。虽然预测看起来当然是相关的,但如果我们使用的是补货至某水平的策略,我们就并未使用该预测,因此它就不会出现在状态变量中。

不妨对我们迄今为止的各个应用做一次巡礼,回顾一下每个应用的状态变量。对于每个应用,我们将总结其状态变量,视具体情形我们可能将其写为 $S_t$ 或 $S^n$,并将其中的元素分类为物理状态变量 $R_t$、信息类变量 $I_t$,以及信念状态变量 $B_t$。

第 1 章 —— 本章介绍了两个库存问题,它们的设计目的也在于呈现状态变量的不同风格。简单库存问题的特征是一个状态变量 $S_t$,它仅由时间 $t$ 的库存 $R^{inv}_t$ 构成。这个问题是用于阐释动态规划最常用的应用之一。

更复杂的库存问题需要如下状态变量

这个状态变量展示了状态变量中全部三类信息:物理状态变量 $R_t = R^{inv}_t$、其他信息 $I_t = c_t$,以及信念状态变量 $B_t = (f^D_{t,t+1}, \sigmabar^D_t, \sigmabar^f_t)$,其中 $(f^D_{t,t+1},\sigmabar^D_t,\sigmabar^f_t)$ 捕捉了对未来需求 $\Dhat_{t+1}$ 误差的预测均值和标准差,以及从时间 $t$ 到 $t+1$ 预测变化的标准差(我们假设预测的变化均值为零)。

第 2 章 —— 本章介绍了一个简单的资产出售问题,其状态变量为

其中物理状态变量 $R_t$ 捕捉了我们是否仍持有该资产(它也可以用来记录我们持有的股票数量),而信息状态 $I_t = p_t$ 是我们出售股票的价格。

我们还引入了使用以下方式计算资产价格平滑估计值的思想

随后我们设计了一种基于价格 $p_t$ 偏离该平滑估计值的程度来做决策的策略。此时我们的状态变量变为

现在想象一下,当我们决定在时间 $t$ 出售股票时,我们是以一个未知价格 $p_{t+1}$ 出售的,该价格按以下方式演化

其中 $\varepsilon_{t+1}$ 是均值为 0 的噪声项。此时我们的状态变量将变为

第 3 章 —— 在这里我们描述了一种基于梯度的搜索算法,它按照如下经典随机搜索迭代式演化

这个过程是一种搜索 $x$ 最佳值的方法,但这是一个序贯决策问题,其中步长 $\alpha_n$ 就是决策。如果我们用一个确定性公式(例如 $\alpha_n =1/n$)来选择步长,那么我们搜索过程的”状态”就是

然而,我们也可能使用一种自适应的(随机的)步长公式,例如

其中 $N^n$ 是梯度 $\nabla_x F(x^n,W^{n+1})$ 改变方向的次数,那么我们就需要知道 $N^n$,此时我们的状态变量变为

第 4 章 —— 我们的糖尿病问题是一个纯学习问题的实例,在其中我们试图学习某患者对某药物的真实反应 $\mu_x$。在尝试了几种药物后,我们可以用以下状态来刻画我们的信念

其中我们假设真实反应 $\mu_x \sim N(\mubar^n_x, (\sigmabar^n_x)^2)$。

如果我们为每位患者都建立不同的信念,这种信念模型可能是可行的,但可以设想我们一开始就掌握了该药物在所有患者身上作用方式的一整套知识体系。我们可以将其纳入一个初始状态

现在想象第 $n$ 位患者以属性 $a^n$(性别、体重、吸烟史……)到来。该患者对药物 $x$ 的反应将同时取决于药物本身以及该患者的属性。这意味着我们的状态变量(即我们可用来做决策的信息)由我们无法控制的信息(患者属性 $a^n$)和我们可以控制的信息(药物选择 $x^n$)构成。因此我们将状态变量(即我们用来做决策的信息)写作

其中我们决定将 $a^n$ 放入信息状态变量 $I^n$,而将变量 $(\mubar^n_x, \sigmabar^n_x)$ 放入信念状态变量 $B^n$。

第 5 章 —— 对于我们的随机最短路径问题,我们从一个基本问题出发,即旅行者在穿越某条链路时会产生一个随机成本,但在节点 $i$ 做出穿越哪条链路 $(i,j)$ 的决策之前,他只知道成本的均值和方差。对于这个问题,我们旅行者的状态就是他在穿越了 $t$ 条链路之后所处的节点 $N_t$,这就给出了

随后我们转向了这样一个问题:处于节点 $i$ 的旅行者能够看到,如果他要穿越链路 $(i,j)$ 将会产生的实际成本 $\chat_{tij}$。有了这一额外信息,状态变量就变成了

第 6 章 —— 我们考虑了一个动态最短路径问题,其中链路 $(i,j)$ 的估计成本 $\cbar_{tij}$ 会随时间演化。也就是说,在时间 $t+1$,我们假设得到了一组更新后的估计值,记为 $\cbar_{t+1}$。设想我们的旅行者处于节点 $N_t= i$。此时(对于我们的旅行者而言)系统的状态将由下式给出

现在想象我们向旅行者展示了一条我们指定为 $p_t$ 的路径,它是我们计划用来从他当前所在节点 $N_t$ 到达目的地所使用的一组链路。假设我们刚刚更新了这条路径,并询问旅行者是否接受这条新路径。如果他表示接受,导航系统将继续重新优化,但会为坚持使用旅行者刚接受的最新路径 $p_t$ 引入一个小额奖励(这样做是为了防止系统在两条几乎等价的路径之间来回摆动)。

如果 $p_t$ 是最近被接受的路径,那么这就是我们在未来做决策时所需要的信息。在这种情况下,我们的状态变量就变成了

这些决策问题展示了全部三种类型的状态变量:物理状态变量 $R_t$、信息状态变量 $I_t$,以及信念状态变量 $B_t$。我们已经见过只有 $R_t$,或只有 $B_t$ 的问题,也见过与 $I_t$ 的组合,例如 $(R_t, I_t)$ 和 $(I_t, B_t)$,以及三者兼具的 $(R_t, I_t, B_t)$。我们要强调的是,$R_t$ 与 $I_t$ 之间的区分有时可能是任意的,但由于存在大量涉及管理物理或金融资源(购买、出售、移动、修改)的问题,其决策会影响(或受限于)物理或金融资源,我们认为有必要专门为资源创建一个特殊类别。

我们认为,有许多涉及不确定性的问题同时也涉及学习,而且由于决策可能影响我们所观察到的内容(如糖尿病例子中那样),这些问题可能涉及主动学习。我们推测,随着建模者越来越习惯于在序贯决策问题中纳入信念状态变量,我们将看到它们被更频繁地使用。

策略再探

我们的六个应用场景(在某些情况下还有其扩展)都是精心挑选出来,以展现这四类策略中的每一类。下面我们将回顾不同的策略,并指出它们各自所属的类别。

第 1 章 —— 我们介绍了两个库存问题。一个使用了如下形式的补货至某水平的策略

而第二个则使用了将库存补至预测需求加上一个缓冲量的策略

这两种策略都涉及一到两个可调参数。二者都是不含内嵌优化算子($\min$ 或 $\max$)的解析函数。这些正是策略函数近似(PFA)的显著特征。

第 2 章 —— 本章探讨了何时出售一项资产的问题。文中提出了若干策略,其代表性例子有”逢低卖出”策略,由下式给出

以及”跟踪策略”

这两种策略都与我们的”补货至某水平”库存订购策略相似,都是带有可调参数的参数化函数,这意味着它们是策略函数近似(PFA)的又一实例。虽然这绝非解决资产出售问题的唯一方式,但这类策略在华尔街相当受欢迎。

PFA 在实践中很受欢迎,原因在于其简单性和透明性,但需要牢记:简单性是有代价的……那就是可调参数……而调参很难!

第 3 章 – 自适应市场规划 – 该问题涉及使用一种流行的基于梯度的搜索方法（见方程$\eqref{eq:stochasticgradientaltransitionrevisited}$），其中步长$\alpha_n$是决策。如果我们面对的是一个确定性问题，我们会通过求解如下的一维优化问题来计算$\alpha_n$

这是直接前瞻近似（DLA）的一种形式。然而，当我们必须处理不确定性时，一维搜索意味着我们必须能够计算期望$F(x) = \E F(x,W)$，而这在实践中通常是不可能的。取而代之，我们可能会使用如下的确定性策略

我们将其写成一个参数化函数（也就是一种PFA的形式）。我们还展示了由方程$\eqref{eq:adaptivealpharevisited}$给出的一种自适应（依赖于状态的）策略，其中我们用一个计数器$N^n$替代了$n$，该计数器统计梯度改变方向的次数（或者我们也可以统计目标函数没有改善的次数）。我们可以将这一策略写为

其中我们的状态$S^n$携带信息$N^n$。

补充说明：PFA类型的策略在随机梯度算法中被广泛使用。虽然这些策略实际上可能是最优的，但现实是没有人尝试过使用其他三类策略。这或许值得研究一下。

第 4 章 – 学习最佳糖尿病治疗方案 – 这是一个纯粹的学习问题，我们采用了一类非常流行的策略——置信上界法（upper confidence bounding）来处理。也许最著名的UCB策略由下式给出

另一个效果很好的变体最初被称为区间估计（interval estimation），由下式给出

最后，一个最初在1933年被发现、几年前又被重新发现的变体是汤普森抽样（Thompson sampling），由下式给出

其中$\muhat^n_x$是从均值为$\mubar^n_x$、方差为$\theta^{TS} \sigmabar^n_x$的正态分布中随机抽取的。

请注意，这三种策略都具有两个共同特征：一个优化算子（对这些策略而言是$\argmax_x$）和一个可调参数。这些可以被视为参数化的优化问题，属于参数化成本函数近似（parametric cost function approximation，或称CFA）这一类。

CFA策略在实践中被广泛使用，但除了在学习策略这一特定应用（如我们的糖尿病应用）之外，在学术文献中受到的关注非常少。我们将在后面的章节中看到这一思想在一个截然不同的场景中的应用。

第 5 章 – 静态随机最短路径 – 我们的第一个随机最短路径问题假设旅行者会产生随机成本，但这些成本只有在经过某条链路之后才能得知。这一假设使我们能够将该问题作为确定性最短路径问题来求解，而这可以很容易地用贝尔曼方程求解，从而得到如下形式的策略

其中$S_t = N_t = i$是旅行者所在的节点。值函数$V_t(S_t)$是通过时间反向递推计算的，从$t=T$开始，此时我们对所有节点$S_T$设置$V_T(S_T) = 0$。这是一种基于值函数近似的策略，而这是VFA策略实际上是最优的少数情形之一。

随后我们转向一个更困难的问题，其中允许旅行者在离开节点$i = N_t$之前看到成本$\chat_{tij}$。对于这个问题，状态变量变为$S_t = (N_t, (\chat_{t,N_t,j},~j\in\Ncal^+_i))$。对于这个问题，我们必须使用后决策状态$S^x_t = N^x_t$来近似值函数，其中$N^x_t$是我们在节点$N_t$做出决策$x_t$之后选择前往的节点。在这种情况下，我们的策略形式如下

这同样是一种基于VFA的策略，但这一次它不再是最优的，因为$\Vbar^x_t(S^x_t)$是我们必须从数据中估计出的近似值。不过，只要处理得当，我们仍可以设计出一个渐近最优的策略。

第 6 章 – 动态随机最短路径 – 在这里我们遇到一个问题：每条链路上的估计成本$\cbar_{tij}$会随时间演变。因此，在时间$t$时，$\cbar_t$是估计链路成本的向量，到下一个时间段会变为$\cbar_{t+1}$。这意味着我们的状态变量从仅仅是旅行者所在节点的$S_t = N_t$，转变为一个维度极高的状态变量$S_t = (N_t, \cbar_t)$。即使采用近似动态规划，这也不是一个我们能够处理的问题（很难想象能围绕这个状态变量构建出VFA）。

取而代之，我们提出使用前瞻模型（lookahead model）的思路，即忽略这样一个事实：随着旅行者在网络中前进，估计链路成本向量$\cbar_t$会随时间演变。相反，我们可以假设它是固定的（并且不妨假设是确定性的）。这意味着我们现在有了一个前瞻模型，它实际上是一个确定性最短路径问题，但我们必须记住，我们优化的是一个近似的前瞻模型，这是一种DLA策略。当然，我们知道如何最优地求解这个问题，但对一个近似前瞻模型的最优解并不是一个最优策略！

确定性前瞻策略很流行，但有一种方法可以在不使其更复杂的情况下使其变得更好。我们在建议使用成本的$\theta$分位数而不是均值$\cbar_t$时提出了这一思想。设$\ctilde_{tij}(\theta)$为在时间$t$已知信息条件下，链路$(i,j)$上成本的$\theta$分位数。现在，使用成本$\ctilde_{tij}(\theta)$求解一个确定性前瞻模型。这样我们就得到了一个参数化的确定性前瞻模型，它是参数化CFA与DLA的一种混合形式。

在线与离线目标

评估策略性能有两种视角：

• 在线学习 – 在许多场景下，我们必须在实际操作中边做边学。例如，我们可能试图学习一种产品的最优定价、在拥堵城市中的最佳路径，或者用于降低患者血压的最佳药物。在所有这些情况下，我们都希望在现有认知的基础上尽可能做好，但由于我们仍在学习，因此可以在未来做出更好的决策。这意味着我们需要最大化一段时间（或若干次迭代）内的累积回报，从而衡量我们在学习过程中的表现有多好。
• 离线学习 – 在其他情况下，我们可以在实验室环境中进行学习，这可能是一个实体实验室（用于测试不同材料或观察药物对小鼠的效果）、一个计算机仿真环境，甚至是一个作为测试市场运行的现场环境（用于评估产品）或临床试验（用于测试药物）。如果我们是在实验室环境（”离线”）中进行学习，那么我们愿意进行试错而不必担心当下的表现如何。相反，我们唯一关心的是最终解的质量，这意味着我们希望优化最终回报。

关于在线和离线这两个术语，需要提醒大家注意。在机器学习界，”离线”指的是使用单一、批量数据集进行模型估计。相比之下，”在线学习”指的是数据随时间到来的完全序贯的场景。这通常出现在数据由某个外源过程产生的现场情境中（例如观察患者陆续到诊所就诊），这与我们使用”在线”一词时所假设的场景相同。然而，在机器学习中，”在线”仍然会被用来指代在仿真中使用的迭代算法。

有整个研究领域是根据其关注的是最终回报还是累积回报来划分序贯决策问题的。例如，从事”随机搜索”研究的社区往往关注最终回报，而从事”多臂老虎机问题”（一种随机搜索问题的形式）研究的社区通常优化累积回报。现实情况是，你可以将同一个策略用于任一目标，但必须根据所选定的目标对其进行调优。

在线（累积回报）优化

在进行策略搜索时，通常情况是我们有一个可以写成$X^\pi(S_t\vert \theta)$的参数化策略。决策$x_t = X^\pi(S_t\vert \theta)$可能是产品的价格、降压药物的选择，或者是为最大化广告点击量而设定的出价。在所有这些情况下，我们都必须边做边学，这意味着我们需要在学习过程中最大化表现。

设$C(S_t,x_t)$为我们的绩效度量（收入、血压降低幅度，或广告点击带来的净收入）。我们希望找到能产生策略$X^\pi(S_t\vert \theta)$的$\theta$，以求解如下优化问题

其中$S_{t+1} = S^M(S_t, X^\pi(S_t\vert \theta),W_{t+1})$。$\eqref{eq:derivativebasedonline}$中的期望是对$W_1, \ldots, W_T$所有可能的实现，以及初始状态$S_0$中所包含的不确定参数（例如关于市场反应的不确定初始信念，或某人对药物的反应）的可能取值求取的。

方程$\eqref{eq:derivativebasedonline}$是”在线”或”累积回报”目标函数的一个例子，因为我们希望在某个时域内最大化所有回报的总和。这在在线学习问题中尤为重要，在这类问题中我们必须边学习表现（例如某个价格带来的收入，或某种药物对特定患者的疗效），这意味着需要在学习过程与尽力争取良好表现之间取得平衡。

离线（最终回报）优化

在离线场景中，我们通常拥有$N$次实验的预算。一个常用于说明离线、无导数学习的经典（尽管并不恰当）问题是报童问题，我们在第 3 章中已经探讨过。作为提醒，报童问题写作

其中$x$是我们以单位成本$c$订购的资源数量，用来满足需求$W$（在我们选择$x$时该需求是未知的）。我们假设$W$的分布是未知的。

设$x^n = X^\pi(S^n\vert \theta)$为我们在已知信息（由$S^n$所体现）条件下对$x$的选择，其中我们的策略$X^\pi(S^n\vert \theta)$依赖于$\theta$中的一个或多个参数。在实施$x^n$之后，我们观察到$W^{n+1}$，更新$S^{n+1}$，然后重复这一过程。经过$N$次迭代后，我们得到一个最终设计，记为$x^{\pi,N}(\theta)$。

现在我们必须评估我们的最终设计$x^{\pi,N}(\theta)$。为了进行这一评估，我们必须考虑两种、甚至可能三种不确定性来源。第一种是我们可能对未知参数（如$W$的均值）存在不确定性。例如，$W$可能来自均值为$\mu$的泊松分布，我们可以假设$\mu \in \lbrace \mu_1, \ldots, \mu_K\rbrace $，其中$p_k = Prob[\mu = \mu_k]$。分布$(p_k)_{k=1}^K$包含在初始状态$S_0$中。

接下来是需求$W^1, \ldots, W^N$的随机到达，这些需求会从均值为$\mu$的分布中抽样得出。我们利用这些观测值以及策略$X^\pi(S^n\vert \theta)$来计算$x^{\pi,N}(\theta)$。需要重要指出的是，$x^{\pi,N}(\theta)$是一个随机变量，它依赖于$S^0$中包含的任何信息（无论该信息是确定性的还是随机的）。

一旦我们计算出$x^{\pi,N}(\theta)$，我们就必须运行最后一组仿真来评估它的效果如何。我们引入一个新的随机变量$\What$，用来表示用于评估我们最终设计的$W$的样本。

有了这样的记号，我们就可以将离线学习的目标函数写成

我们要强调的是，我们之所以用期望的形式来书写，只是为了表明我们必须对随机信息进行平均。我们将在接下来讨论如何计算这些期望的问题。

策略评估

累积回报（见$\eqref{eq:derivativebasedonline}$）和最终回报（见$\eqref{eq:derivativebasedoffline}$）的目标函数都是用期望的形式写出的，这是我们用来表示”我们要对一切随机因素进行平均”的一种方式。这在数学书写上很方便，但这些期望几乎从来都无法真正计算出来。

每当我们需要计算期望值时，假设我们将通过抽样来估计该期望值会有所帮助。我们首先说明如何针对$\eqref{eq:derivativebasedonline}$中给出的累积奖励目标函数进行这一操作。这里，我们可能在初始状态$S_0$中存在不确定量，例如市场对价格反应的不确定性、油井甲烷产量的不确定性，或患者对药物反应的不确定性。然后，我们有外源信息$W_1, \ldots, W_T$，它可能是销售观测值、大气温度的变化，或患者对药物治疗的反应。

设$\omega$为所有这些不确定量的一个样本实现。假设我们生成了一组这些不确定量的样本，并将它们存储在集合$\Omega = \lbrace \omega^1, \ldots, \omega^K\rbrace $中。那么，每当我们写出$W_t(\omega)$时，这就是我们在时间$t$观测到的量的一个样本实现。如果我们使用策略$X^\pi(S_t\vert \theta)$，那么我们将沿着由我们的转移函数所支配的状态$S_t(\omega)$、决策$x_t(\omega) = X^\pi(S_t(\omega)\vert \theta)$和外源信息$W_{t+1}(\omega)$的样本路径进行

利用我们的样本观测集$\Omega$，我们可以用下式来近似我们的期望$F^\pi(\theta)$

如果我们使用的是最终奖励目标函数，我们需要先估计$x^{\pi,N}(\theta)$。如果我们沿着样本路径$\omega$，那么我们会将最终设计写为$x^{\pi,N}(\omega\vert \theta)$，其中$\omega$捕获了我们在由$(S_0(\omega), W_1(\omega), \ldots, W_T(\omega))$给出的训练过程中所用到的一切信息。

然后我们需要使用$\What$中捕获的测试数据来评估我们的设计$x^{\pi,N}(\omega\vert \theta)$。设$\psi$为$\What$的一个样本实现，正如我们假设对$\omega$有一个样本集$\Omega$一样，我们假设也创建了一组由$\Psi = \lbrace \psi^1, \ldots, \psi^L\rbrace $给出的$\What$的样本结果。请记住，$\What$代表了我们评估设计$x^{\pi,N}$所需的任何模拟信息。它可能是一组随机变量（患者属性、天气、市场状况），甚至可能代表随时间演化的信息。换句话说……任何东西都有可能。

现在我们可以将最终奖励设定下策略性能的估计写为

将两者结合起来

方程$\eqref{eq:derivativebasedonline}$展示了一个在线目标函数，即累积奖励目标函数，我们需要在学习过程中最大化总体表现。方程$\eqref{eq:derivativebasedoffline}$展示了一个离线目标函数，即最终奖励目标函数，我们需要搜索一旦固定设计之后平均表现最佳的设计。目前重要的是，这两个问题都涉及求解

其中$F(\theta)$是一个未知函数，我们只能以带噪声的方式对其进行抽样。

我们可以将$\eqref{eq:searchovertheta}$中的目标函数扩展为对不同策略类别进行搜索。设$\Fcal$表示所有可能类型的策略集合，包括主要类别（PFA、CFA、VFA和DLA），以及每一类别中的不同函数。然后设$\Theta^f$为对应于我们所选定的任何策略类别$f\in\Fcal$的所有可能参数向量$\theta$的集合。在这种情况下，我们可以将我们的优化问题写为

在实践中，我们往往凭借直觉和对问题结构的理解来选择策略类别$f\in\Fcal$，但这并非总是显而易见的。我们敦促读者随时准备运用直觉和常识，但要意识到所有四个类别的存在。这并不意味着你必须测试所有四个类别，但你应该准备好为自己所做的选择进行辩护。

接下来我们转向对$\theta$进行优化的问题，我们假设它是连续的，并且在大多数情况下是向量值的。我们可以应用两大类搜索方法来寻找$\theta$：基于导数的方法和无导数的方法。

对初始状态的依赖性

无论我们使用的是累积奖励目标函数（如方程$\eqref{eq:derivativebasedonline}$）还是最终奖励目标函数（如方程$\eqref{eq:derivativebasedoffline}$），我们对$\theta$的优化都将依赖于初始状态$S_0$。这意味着$S_0$中信息的变化有可能改变我们的结果，包括策略的选择。

初始状态$S_0$包含了以任何方式影响系统行为的所有信息。它可能包括确定性参数、关于不确定参数的分布，甚至搜索算法的起始位置。

最优解对$S_0$中信息的依赖性在算法文献中被广泛忽视。如果我们能够计算函数$\theta(S_0)$来捕捉这种依赖性会很好，但估计这个函数是难以处理的。这意味着如果$S_0$发生变化，我们可能不得不重新优化$\theta$。这本来没有问题，除非存在许多情况，其中$S_0$发生了变化，而我们并没有重新优化$\theta$，仅仅是因为这样做可能相当困难。

这是读者应当意识到的一点。

基于导数的策略搜索

假设我们正试图求解问题

其中$F(\theta)$是关于$\theta$的某个参数化函数。进一步假设$\theta$是一个向量，并且我们可以计算梯度

在实践中，精确计算导数通常是不可能的。

一种处理高维参数向量的实用方法是Spall（2003）提出的同时扰动随机逼近（simultaneous perturbation stochastic approximation，简称SPSA），它以如下方式近似梯度。设$Z_p, p=1, \ldots, P$为均值为0的随机变量（它们可能服从正态分布）的一个实现样本。设$Z^n$为第$n$次迭代中具有这些实现值的$p$维向量。我们通过用$x^n+\eta^nZ^n$和$x^n-\eta^nZ^n$对$x^n$进行向量$Z$的扰动来近似梯度，其中$\eta^n$是一个缩放参数，它可以在各次迭代中保持恒定，也可以变化（通常会递减）。

现在设$W^{n+1,+}$和$W^{n+1,-}$代表驱动仿真的随机变量的两个不同样本（这些可以事先生成，也可以即时生成）。然后我们运行两次仿真：一次求得$F(x^n + \eta^nZ^n,W^{n+1,+})$，一次求得$F(x^n - \eta^nZ^n,W^{n+1,-})$。梯度的估计值则由下式给出

请注意，方程$\eqref{eq:SPSAgradient}$中梯度每个元素的分子都是相同的，这意味着我们只需要两次函数求值：$F(x^n + \eta^nZ^n,W^{n+1,+})$和$F(x^n - \eta^nZ^n,W^{n+1,-})$。唯一的区别在于每个维度$p$的分母中的$Z^n_p$（这正是SPSA的巧妙之处）。（关于SPSA的介绍，参见《Reinforcement Learning and Stochastic Optimization》第5章第5.4.4节。）

关于SPSA“巧妙之处”的一点提醒是：梯度可能相当嘈杂。因此，一种常见的策略是对每个扰动后的仿真运行多次仿真（文献中称为小批量，mini-batches）并取平均值。小批量的适当规模取决于问题的特性，因此请预留一些时间来调整这个参数。

无论我们如何计算梯度，我们的搜索算法（我们在第3章中见过）都由下式给出

现在我们必须为步长$\alpha_n$选择一个策略，我们在第3章中讨论过这个问题，但关于步长策略的详尽讨论，请参见《Reinforcement Learning and Stochastic Optimization》第6章。我们提醒读者，随机梯度算法本身就是一个序贯决策问题（正如我们在第3章中所看到的那样）。

无导数策略搜索

无导数策略搜索只是本书通篇关注的序贯决策问题的另一个例子，主要区别在于唯一的状态变量将是关于我们正在最大化的函数的信念（这与我们在第4章中的糖尿病应用相同）。

我们可以使用以下任何一种方法来形成信念：

• 查找表 —— 假设我们可以将$\theta$的可能取值集合离散化为一个集合$\Theta = \lbrace \theta_1, \ldots, \theta_K\rbrace $。定义一个随机变量$\mu_\theta = F(\theta) = \E F(\theta,W)$，之所以是随机变量，是因为我们不知道$F(\theta)$（或$\mu_\theta$）。假设我们可以运行实验来对$\Fhat^{n+1} = F(\theta^n, W^{n+1})$进行抽样。我们可以利用这些样本，为$\theta \in \Theta$的每个离散取值创建估计值$\mubar^n_\theta$。这将是一个查找表信念模型。

  最简单的信念模型是具有独立信念的查找表，我们在第4章的糖尿病应用中首次见到过它。设$\mubar^n_\theta$为在（跨所有实验）共$n$次抽样后，对某个$\theta \in \lbrace \theta_1, \ldots, \theta_K\rbrace $处$\E F(\theta)$的估计值。设$\sigmabar^n_{\theta_k}$为估计值$\mubar^n_{\theta_k}$的标准差，并设$\beta^n_{\theta_k}$为由下式给出的精度

  \[\beta^n_{\theta_k} = \frac{1}{(\sigmabar^n_{\theta_k})^2}.\]

• 参数化模型 —— 我们可能会估计一个如下形式的线性模型

  \[F(\theta\vert \eta) \approx \eta_0 + \eta_1 \phi_1(\theta) + \eta_2 \phi_2(\theta) + \ldots\]

  其中$\phi_f(\theta)$是根据向量$\theta$计算出的特征，该向量可能由诸如$\theta,$$\theta^2$或$\ln \theta$之类的项组成。请注意，“线性模型”是指该模型在系数$\eta$中是线性的；特征$\phi_f(\theta)$可能是$\theta$的非线性函数。

  尽管线性模型很受欢迎，但它们很可能只是一种局部近似。如果我们围绕正确的点来拟合线性模型，这就不是问题。问题在于如何找到正确的点！

• 非参数模型 —— 非参数模型最好被理解为函数在（也许随机选取的）某组点周围的局部近似。估计值可能是一个常数（这是最典型的情况），也可能是一个局部线性近似。

  创建非参数模型的方法有很多。也许最常见的方法是通过对接近$\theta$的取值$\theta_k$上的$\mubar_{\theta_1}, \ldots, \mubar_{\theta_K}$进行平均，来创建估计值$\mubar_\theta$。本书不打算采用非参数方法，主要是因为它们对数据的需求量大，使用起来也有些笨拙。

《Reinforcement Learning and Stochastic Optimization》第3章描述了若干递归估计函数的方法，涵盖了查找表、线性模型和非线性模型的若干信念模型。该章还涵盖了贝叶斯模型和频率派模型两者。我们在糖尿病例子中已经见过查找表的递归方程，其中的更新由第4章中的转移方程给出（这些方程假设了一个贝叶斯信念模型）。稍后我们将说明线性和非线性模型的递归更新。

我们可以使用通用建模框架的五个要素来对执行无导数搜索的过程进行建模：

• 状态变量 —— 这将是关于$\E F(x,W)$的信念，我们可以将其写为$S^n = B^n$。我们如何存储信念状态取决于我们使用的是查找表（以及哪种类型的查找表）、线性模型还是非线性模型。如果我们使用的是查找表信念模型，我们将使用

  \[B^n = (\mubar^n_\theta,\beta^n_\theta),~\theta \in \{\theta_1, \ldots, \theta_K\}.\]
• 决策变量 —— 决策是选择$\theta^n$要评估函数以获得$\Fhat^{n+1} = F(x^n,W^{n+1})$的$\theta$值。我们使用一个需要设计的策略$\Theta^\pi(S^n)$来做出选择$\theta^n = \Theta^\pi(S^n)$。
• 外源信息 —— 我们通常将外源信息视为抽样观测值$\Fhat^{n+1} = F(\theta^n,W^{n+1})$。设$\beta^W_\theta$为在点$\theta$处观测函数$F(\theta^n,W^{n+1})$所产生噪声的精度（方差的倒数）。

• 转移函数 —— 转移函数以更新我们信念的递归方程的形式出现。例如，第4章中我们在寻找最佳糖尿病药物时使用的查找表信念的更新方程。同样使用我们的查找表信念模型，转移函数将是

  \[\begin{align} \mubar^{n+1}_\theta &= \frac{\beta^n_\theta \mubar^n_\theta + \beta^W_\theta W^{n+1}_\theta}{\beta^n_\theta + \beta^W_\theta},\label{eq:thetatransition1}\\ \beta^{n+1}_\theta &= \beta^n_\theta + \beta^W.\label{eq:thetatransition2} \end{align}\]

• 目标函数 —— 最常见的情况是，我们会离线使用仿真器来搜索$\theta$的最佳值，这意味着采用最终奖励目标函数。设$\theta^{\pi,N}$为在$N$次抽样后，根据我们的信念模型得出的参数向量$\theta$的最佳值。例如，如果我们使用的是查找表信念模型，并且在$N$次实验后为每个选择$\theta$获得了估计值$\mubar^N_\theta$，我们将选择

  \[\theta^{\pi,N} = \argmax_{\theta\in\Theta} \mubar^N_\theta,\]

  其中$\theta^{\pi,N}$中的上标“$\pi$”反映了在估计$\mubar^N_x$时所使用的搜索策略$\pi$的类型。搜索最佳策略$\pi$的优化问题将写为

  \[\max_{\pi} \E_{S^0}\E_{W^1, \ldots, W^N\vert S^0} \E_{\What\vert S^0} F(\theta^{\pi,N},\What).\]

请记住,我们如上文所示,使用模拟来计算期望值,对于累积奖励见方程$\eqref{eq:simulatedcumulativereward}$,对于最终奖励见方程$\eqref{eq:simulatedfinalreward}$。

这就给我们留下了一个问题:我们该如何设计搜索策略$\Theta^\pi(S^n)$?我们希望这不会让人感到意外——我们可以从四类策略中的任意一类进行选择。这四类策略都在《Reinforcement Learning and Stochastic Optimization》第7章中有深入讨论,但我们也建议参考该书第12章中关于策略搜索的讨论。

出于我们的目的,我们将展示两种相对简单而自然的策略。

• 查找表信念模型的区间估计策略 —— 我们回顾了糖尿病问题中的若干策略,其中特别有效的一种是区间估计策略,由下式给出

  \[\begin{align} \Theta^{IE}(S^n\vert \theta^{IE}) = \argmax_{\theta\in\Theta} \left(\mubar^n_\theta + \theta^{IE} \sigmabar^n_\theta \right). \label{eq:thetaIE} \end{align}\]

  现在我们必须搜索$\theta^{IE}$的最佳值。可以把这看作是一个序贯决策问题(寻找最佳$\theta^{IE}$),用以解决另一个序贯决策问题(为我们的策略$X^\pi(S_t\vert \theta)$寻找最佳$\theta$)。我们注意到,在搜索领域,参数$\theta^{IE}$的调优在研究文献中通常被忽视,但实践者深知这一步是必须要做的。

• 经典响应曲面方法 —— 对于$x$是连续的问题,给函数$\E F(x,W)$拟合一个参数化模型是有意义的做法。虽然如今很容易想到使用神经网络,但请记住,这些是高维模型,往往会对任何噪声产生过拟合。有许多问题中$F(x,W)$的评估代价很高;例如,它可能是一个需要一小时甚至更长时间的计算机模拟,也可能需要进行现场实验。

  基于这些原因,一种流行的策略是使用如下形式的线性模型

  \[\Fbar(x) = \sum_f \theta_f \phi_f(x),\]

  其中$\phi_f(x)$是从输入向量$x$中提取的特征。假设我们已使用输入$x^0, \ldots, x^{n-1}$运行了$n$次实验,从中观测到了响应$\Fhat^1, \ldots, \Fhat^n$。基于这些数据,我们可以使用线性回归技术来拟合我们的线性模型,得到估计值$\theta \approx \thetabar^n$,从而得到近似式

  \[\Fbar^n(x) = \sum_f \thetabar^n_f \phi_f(x).\]

  响应曲面文献长期以来使用的是一种贪婪策略,即优化$\Fbar^n(x)$以找到下一个要观测的点,这意味着我们会写出

  \[\begin{align} x^n = \argmax_x \Fbar^n(x). \label{eq:responsesurfacegreedy} \end{align}\]

  虽然这个想法在直觉上很有吸引力,但事实证明,基于我们的近似式$\Fbar^n(x)$所得出的看似最优的点,来进行采样其实是学习$\E F(x)$最佳近似的一种糟糕方式。

  图7.2展示了学习参数化函数所面临的挑战。这里我们展示了三条形如$D(p) = \theta_0 - \theta_1 p$的线性需求响应曲线,表示需求作为价格的函数。我们的目标是最大化收入$R(p) = pD(p)$。图7.2(a)展示了三条可能的需求曲线及其对应的收入曲线。

(a)

(b)

(c)

(d)

我们很容易想要像图7.2(b)那样报出能优化收入的价格,但这会产生一组聚集在一个球内的点,使得估计需求曲线变得困难。估计需求曲线的最佳方法是像图7.2(c)那样报出接近极端的价格,但在这些点上收入非常低,因此我们在学习的同时无法赚钱。

一个好的方法是在“肩部”点上进行测试,也就是说不在最优点上,但也不要离得太远,就像我们在图7.2(d)中所做的那样,这是一种我们通过下文描述的策略来实现的行为。

• 带扰动的响应曲面方法 —— 一种克服图7.2所示探索与利用权衡的策略,使用了一种称为知识梯度的单步前瞻策略,该策略选择$x^n$作为能产生最大信息价值的值。事实证明,能使信息价值最大化的点会给我们带来图7.2(d)所示的采样模式。

  知识梯度对于我们此处的讲解来说过于复杂,但有一种非常简单的方法可以获得同样的行为。我们不采用$\eqref{eq:responsesurfacegreedy}$那样直接取当前看似最优的估计点$x^n$,而是对其施加一个幅度为$\rho$的扰动,但这里有两种做法:

  • 最优偏离策略 —— 这里的思路是选取一个与最优点$\xbar^n = \argmax_x \Fbar^n(x\vert \thetabar^n)$相距$\rho$的点$x^n$。如果$x$是一个$k$维向量,这种偏离可以通过采样$k$个服从正态分布的随机变量$Z_1, \ldots, Z_K$(每个均值为0、方差为1)来生成,然后将它们归一化,使得

    \[\sqrt{\sum_{k=1}^K Z^2_k} = \rho.\]

    令$\Zbar^n$为所得到的$k$维向量。现在使用下式计算采样点

    \[x^n_k = \xbar^n_k + \Zbar^n_k.\]

    注意在一维情形下,我们会有$\Zbar^n = \pm \rho$。

  • 激励策略 —— 这里我们同样生成一个$k$维的扰动向量$Z^n$,其每个元素均值为0、方差为1,然后设

    \[x^n_k = \Xbar^n_k + \rho Z^n_k.\]

    最优偏离策略强制$x^n$与最优点$\xbar^n$相距$\rho$,而激励策略只是引入一个均值为0的随机扰动,这意味着最有可能被采样到的点就是$\fbar^n(x\vert \thetabar^n)$的最优点。

  我们建议,最优偏离策略更适合于离线的最终奖励目标,而激励策略在优化累积奖励的在线场景中效果更佳。

我们学到了什么?

• 我们回顾了四类策略。
• 我们利用前六章中介绍的所有应用,来对比不同风格的状态变量,并说明四类策略中的每一类。
• 我们还描述了最终奖励与累积奖励两种目标。当我们在实验环境(实验室或现场)中进行观测,只关心最终设计的表现时,就会出现最终奖励目标。而当我们边做边学时,则使用累积奖励目标。
• 我们描述了用于参数搜索的基于导数和无导数两类搜索方法。
• 我们指出,基于导数的和无导数的随机搜索都是序贯决策问题。

习题

复习题

1. PFA与其他三类策略的区别是什么?
2. VFA和DLA与PFA和CFA的区别是什么?
3. 在第1章中,针对更复杂的库存问题,状态变量由物理状态变量$R_t$、信息状态变量$I_t$以及信念状态变量$B_t$组成。信念状态变量与信息状态变量有何区别?
4. 在线学习与离线学习在目标函数上有何不同?
5. 我们将基于导数和无导数的随机搜索都描述为序贯决策问题。这两种策略中哪一种使用了信念状态,为什么这是必要的?

问题求解题

1. 图7.3展示了一个确定性图,我们试图使用不同的目标函数寻找一条从节点1到节点11的路径。
   1. 如果我们的旅行者只是想要最小化从节点1到节点11的总旅行时间,并且她目前已经走过了路径1-2-6-9,那么她的状态是什么?
   2. 现在假设我们的旅行者必须在时间45之前到达节点11。如果她在时间45之后到达,将被处以等于延误时间平方的惩罚。目前已经走过路径1-2-6-9的旅行者的状态是什么?
   3. 如果已经走过路径1-2-6-9的旅行者想要最小化她路径上各条边中第二高的成本,那么此时的状态是什么?

   

2. 真实故事:一家金融科技公司("fintech")拥有一套用于高频交易的算法交易系统。在时间$t$,当某资产以价格$p_t$交易时,该公司通过对日内滚动时域内价格可能如何变化的一系列预测,来估计价格是上涨还是下跌。此处,时间以15分钟为增量计量。设$f_{tt'}$为在时间$t$掌握的信息下,对时间$t'$的资产价格所做的估计。现在使用下式构造一个估计价格 $$ \fbar_t(\theta) = \sum_{t'=t+1}^{t+H} \theta_{t'-t} f_{tt'}, $$ 其中$\theta = (\theta_1, \theta_2, \ldots, \theta_H)$是未来六小时内(24个增量)每个15分钟增量对应的权重向量。设$x_t = 1$表示在时间$t$做出卖出决策,$x_t = -1$表示买入决策,$x_t = 0$表示持有,策略为 $$ X^\pi(S_t\vert \theta) = \begin{cases} +1 & \text{if } \fbar_t(\theta) \geq p_t + 1.0, \\ 0 & \text{if } p_t - 1.0 < \fbar_t(\theta) < p_t + 1.0, \\ -1 & \text{if } \fbar_t(\theta) \leq p_t - 1.0. \end{cases} $$ 面临的挑战是优化权重向量$\theta$。
   1. 在时间$t$,该系统的状态是什么?
   2. $X^\pi(S_t\vert \theta)$属于哪一类策略?请解释。
   3. 假设你可以在模拟器中使用历史数据来模拟该策略。设$F(\theta)$为给定参数向量$\theta$时策略的期望表现。请写出该目标函数,假设你将使用单一的历史样本来模拟该策略。
   4. 描述如何使用你的模拟器计算数值导数。请仅针对单个元素$\theta_\tau$写出该数值导数。