在本文中，我将讨论如何计算最佳操作集，以在已知环境（也称为规划）中操作时完成任务。对于这种情况，我们对系统的动力学有完整的了解，包括每个状态的奖励以及代理如何更改其状态的概率模型。这篇文章将为最终讨论强化学习奠定基础，因为我们的代理无法访问底层的系统动态。

马尔可夫决策过程
马尔可夫决策过程是一种用于在随机环境中进行规划的方法。尽管我们无法控制或优化发生的随机性，但是我们可以在随机环境中优化我们的动作。规划随机环境比规划确定性环境困难得多。考虑到当前的随机性，我们的行动结果存在一定程度的不确定性。

具体地说，计划是指弄清楚一组动作来完成给定的任务。马尔可夫决策过程是一个有用的框架，用于直接解决随机环境中要采取的最佳行动。

马尔可夫决策过程所使用的环境由以下组件定义：

一个代理是谁被鼓励完成既定任务环境中的对象。
代理在环境中采取一种状态，并且可以通过更改其状态来遍历环境。
代理可以通过从一组可能的动作中执行一个动作来更改其状态。
甲传递函数定义所述试剂完成一个动作之后如何进入其新状态。该传递函数是潜在状态的概率分布，将随机行为引入环境。此外，此传递函数仅取决于当前状态-它不需要以前动作的全部历史记录。这支持了所谓的Markov属性。
一个奖励函数用来鼓励代理人来完成既定任务。
在这种环境下，我们可以制定一个策略，描述对环境中任何给定状态应采取的最佳措施。当代理遍历其环境时，它将引用该策略以执行下一个操作。

一个简单的例子
要提供上面定义的环境的具体示例，请看以下图像。

该图中的每个正方形代表一个可能的状态（黑色正方形除外，假设这是一个无限高的势垒）。代理从左下角开始，可以通过以下一组操作从一个状态移动到另一个状态：上，下，左，右。如果该代理位于环境外围的正方形之一上，并试图在环境之外迈出一步，则它只会撞到墙壁上并停留在当前状态。右上角的方块是所需的最终状态，奖励特工+1分并结束“游戏”。右下方的方块也结束了“游戏”，但奖励代理人-1的罚款。

向环境引入随机行为
现在让我们定义传递函数。在确定性世界中，如果（通过策略）指示代理“上移”，则代理将这样做。但是，假设您的经纪人是一个生气的少年，并且仅80％的时间听指令。10％的时间，座席向指示的动作向左移动90度，并且10％的时间，座席向指示的动作向右移动90度。


在此，蓝色箭头表示所指示的操作，而所有箭头均表示可能的结果。这引入了一定程度的不确定性，这不仅对建模愤怒的青少年有用。例如，如果您依靠传感器数据来为自主机器人提供信息，则在使用该信息时，需要考虑传感器的噪声。对随机行为进行建模可以使我们通过了解信息的非依赖性本质来构建更可靠（健壮）的系统。

现在，我们介​​绍了随机行为，请注意最佳操作集将如何变化。最初，此环境中从头到尾的最短序列是{上，上，右，右，右}或{上，右，上，右，右}。但是，既然我们引入了传递函数，其中代理仅在80％的时间执行预期的操作，那么前一种路由似乎比后者更“安全”，因为我们不太可能最终无意中终止进入红色状态。

定义奖励
奖励功能在很大程度上控制了我们代理商的行为。此功能将奖励映射到环境中的每个状态。因此，对于上面的示例，除了对绿色和红色状态的预定义奖励之外，我们还将对白色状态进行奖励。

如果我们想鼓励代理商在尽可能短的时间内达到绿色状态，我们可以为其余状态分配少量罚款（负奖励）。下图显示了每个白色状态的奖励为-0.04的环境的最佳策略（用蓝色箭头表示）。



冒着在本领域引入冗余术语的风险，我将区分到目前为止我们看到的两种奖励类型。

客观的状态奖励驱动我们的代理商完成给定任务的最终行为。在我们的示例中，这是1）转到绿色方块，而2）避开红色方块。
潜在状态奖励定义了代理在环境中如何实现目标奖励的过程。在我们的示例中，这是对每个白人州给予的奖励，以鼓励我们的特工迅速到达终点州。
我们可以通过更改潜在状态奖励值来观察奖励函数对最优策略的影响。

如果我们让每个州都获得了潜在的惩罚性奖励（以鼓励特工结束游戏），那么我们的特工就不会那么小心地避免出现红色状态。存在的惩罚比进入红色状态要严厉，因此我们的特工自杀。


如果我们使每个州都获得积极的潜在奖励，那么代理商就没有动力结束游戏，并且漫无目的地徘徊在收集每个白人州的潜在奖励的环境中。在这种情况下，我们的经纪人会成为享乐主义者，并不关心达成目标。

因此，找到合适的奖励功能对于正确鼓励您的经纪人完成任务至关重要。

国家的效用
人们可能会认为，能够计算一系列状态的有用性可能会有所帮助，这样我们的“未来展望”不仅限于我们的直接下一步行动。例如，与其希望在相邻州的下一个立即奖励指导下的环境中盲目走动，您希望它看到前进的方向，并朝着积极奖励的方向走，而远离消极奖励，即使那些州不是您当前状态的直接邻居。

假设您的经纪人处于以下环境中，其中金星代表一些丰厚的回报。


显然，您希望您的代理采取行动，以接近丰厚的回报。但是，如果我们仅根据下一个可能状态的奖励来选择我们的行动，那么代理商就无路可走。

我们可以将状态序列的有用性（或效用）计算为在每个状态下累积的奖励之和。通过在决定采取下一步行动时考虑一系列状态的效用，我们可以对我们立即采取行动的结果进行长期观察。

我们还希望我们的模型在这种随机环境中支持更直接的奖励，因为不能保证以后的奖励（由于传递函数的随机性，我们可能不会最终达到预期的状态）。因此，我们针对一系列国家效用的模型将折现未来的奖励。更正式地说，我们可以将给定状态序列的效用定义为


哪里 γ是介于0和1之间的数字，用作折扣因子。对于未来的州，奖励将在更大程度上打折。

现在，我们已经确定了给定状态序列的值度量，让我们考虑如何使用它来定义特定状态的值。记住，我们希望国家的价值既代表立即的回报，又代表“朝正确的方向前进”的度量（请参考上图）以积累未来的回报；我们对未来状态的顺序很感兴趣，因此我们可以确定“朝正确方向前进”的度量。

重要的是要区别对待，朝正确的方向前进只有在您继续朝正确的方向前进时才重要。如果您朝着正确的方向迈出了一步，然后完全陷入歧途，那么在随后的状态序列中所积累的价值（即奖励）将很少。因此，当考虑给定状态是否是朝正确方向迈出的一步时（通过从随后的状态序列中计算累积的未来奖励），我们假设我们的代理将按照从新状态向前一致的方式前进一些特定的政策。

总结到目前为止我们建立的内容，一个州的效用是我们希望在当前状态下获得的奖励，再加上我们希望遵循给定政策在此之后积累的奖励。我们将此定义定义为一种期望，因为环境是随机的，我们无法确切地说出我们的代理商将来会访问什么状态。


此外，下一状态的值包含随后的无限状态序列的值。因此，我们可以仅根据状态的当前报酬和对以下状态的效用的期望来定义状态的效用。让我们看看它是如何工作的。

首先，让我们在前面的定义中扩展总和。请记住，我们的政策决定了代理商如何改变状态；如果未指定任何策略，我们将假定代理遵循最佳策略。



接下来，我们将所有折价的未来奖励条款归为一类， γ。



现在，很明显，我们可以将括号内的表达式重写为下一个状态的实用程序。




稍作重新安排，我们现在可以清楚地观察到前面提到的组成状态效用的两个组件。



总而言之，我们定义了一个计算效用的函数，该函数以状态作为输入，效用函数返回进入给定状态的值。
定义最佳政策
该策略表示基于在代理当前状态下可用的信息，提供给代理的指令。我们可以将最优策略定义为策略π这将最大限度地提高遵循该策略所产生的状态序列的预期效用。请注意，这是预期的实用程序，因为不能保证我们的代理程序的操作会将其带入预期状态。

正如我们在上一节中讨论的那样，状态的效用表示当前状态的奖励的期望值加上通过遵循给定策略积累的折现未来奖励的无穷总和。在这里，我们声称我们的代理商将遵循最佳政策。



可以将这种实用程序视为遵循一系列操作的长期利益，而奖励功能定义了给定状态下存在的直接利益。通过专注于效用，我们可以遵循一项政策，该政策可能会导致短期负面结果，但长期来看会带来更多价值。

我们可以将给定状态的最优策略视为对所有可能结果产生最大加权效用的总和的动作（其中加权项是进入状态的可能性） s′ 来自国家 s，由传递函数定义）。



贝尔曼方程
让我们重新来看一下定义效用函数的最终表达式。

首先，由于当前状态的奖励是确定性的，因此我们可以简化第一项。


接下来，让我们考虑下一个状态的效用的期望。回想一下，我们将根据最佳政策选择要采取的行动。

从我们的当前状态开始，存在由传递函数定义的一系列可能的下一状态。在所有可能的下一状态中，来自该可能性范围的期望值可以写为给定下一状态效用的总和，该总和由传递函数将代理置于该状态的概率加权。

为了遵循最佳策略，我们将采取使下一个状态的预期效用最大化的操作。

（我会经常使用 s 表示当前状态和 s′表示下一个状态。请记住s 相当于 小号Ť 和 s′ 相当于 小号t + 1）

将这个新表达式替换为我们先前对效用函数的定义，即可得到Bellman方程。

动态编程以找到最佳策略
我们有一个 ñ 代表效用的方程 ñ 状态，我们有 ñ未知数-每个状态的效用。对于一组线性方程，求解起来很简单。不幸的是，max运算符引入了非线性，阻止了我们直接求解线性方程组。

但是，我们可以通过以下过程来近似真实的实用程序：

首先对所有实用程序进行初步猜测。
通过查看当前状态的奖励值并使用先前估计的所有其他状态的效用来更新每个状态的效用。
重复直到收敛。
本质上，我们递归地解决以下表达式。


这个迭代过程具有传播每个州的真实回报的效果。因为我们在每次迭代期间都添加了真实的奖励，所以在每次下一次迭代时，实用程序的表达越来越“更加真实”。此过程称为值迭代。您可以在此处的交互式演示中看到该过程的可视化效果（单击“切换值迭代”）。

为了找到最佳策略，我们需要找到任何给定状态的动作，这将导致转换为效用最高的状态。因此，为了找到最佳策略，我们只需要具有公用事业的相对价值，这样我们的策略就可以找到将我们带到最佳状态的行动。

考虑到这一点，我们可以专注于直接搜索最佳策略，而不是执行价值迭代，然后推断最佳策略。这称为策略迭代。

从对策略的初步猜测开始。

根据政策 π，计算状态的相应效用。


给定上一步中更新的实用程序，重新计算策略。