延续式决策问题中的最优化

17.1.2 延续式决策问题中的最优化

在图17.1的MDP例子中，智能体的性能是通过对访问过的状态的回报求和来度量的。这种性能度量的选择不是随意的，不过并不是唯一的可能性。这一节我们将研究性能度量的可能选择——也就是，对于环境历史上的效用函数的选择，我们记作Uh([s0, s1, …, sn] )。本节采用了第十六章中的一些思想，多少更技术化一些；要点在本节末尾进行总结。

第一个要回答的问题是制定决策是有限期的还是无限期的。有限期意味着在一个固定的时间N后任何事情都无所谓了——也就是说，游戏结束了。因此，对于任何k＞0，Uh([s0, s1, …, sN+k]) =Uh( [s0, s1,…,sN])。例如，假设一个智能体从图17.1中4×3世界的（3，1）开始，并且假设N=3。那么如果要有到达+1状态的机会，智能体就必须直奔目标，最优行动是Up。另一方面，如果N=100，那么智能体就有足够的时间选择比较安全的路径，采取行动 Left。所以在有限期条件下，给定状态的最优行动会随时间变化。我们称有限期的最优策略为非稳态的。相反，如果没有固定的时间期限，对于同一个状态就没有必要在不同时候采用不同的行为了。因此，最优行动仅仅由当前状态决定，其最优策略是稳态的。所以无限期的策略要比有限期的情况简单，在这一章我们主要处理无限期的情况[35]。注意“无限期”这里并不一定意味着所有的状态序列都是无限长的；它只是意味着没有固定的最后期限。实际上，在包含终止状态的无限期MDP中可以存在有限状态序列。

我们必须决定的下一个问题是如何计算状态序列的效用值。我们可以把这个问题当作多属性效用理论（参见第16.4节）中的问题来看待，其中每个状态si被视为状态序列[s0, s1, s2…]的一个属性。为了得到一个简单的属性表达式，我们需要做出某种偏好独立性假设。一种最自然的假设是智能体在状态序列之间的偏好是稳态的。偏好的稳态性含义如下：如果两个状态序列[s0, s1, s2…]与[s'0, s'1, s'2…]以同样的状态起始（即s'0=s0），那么两个序列的偏好次序就和状态序列[s1, s2…]与[s'1, s'2…]的偏好次序是一致的。也就说，这意味着如果未来从明天开始，你偏好某个未来甚于另一个，那么当未来从今天开始时，你仍然应该偏好那个未来。稳态性是个看来无害的假设而且有一些很强的逻辑推论：在稳态性假设下有两种给序列赋效用值的途径：

（1）累加回报（addictive reward）：状态序列的效用值是

Uh([s0, s1, s2, …])=R(s0)+R(s1)+R(s2)+…

图17.1中的4×3世界使用的就是累加回报。注意在我们用于启发式搜索算法（第四章）的路径耗散函数中，隐含地使用了累加性。

（2）折扣回报（discounted reward）：状态序列的效用值是

Uh([s0, s1, s2…])=R(s0)+γ R(s1)+γ2R(s2)+…

其中折扣因子γ是一个介于0和1之间的数。折扣因子描述了智能体对于当前回报与未来回报相比的偏好。当γ接近于0时，遥远未来的回报被认为无关紧要。而当γ是1时，折扣回报就和累加回报完全等价，所以累加回报是折扣回报的一种特例。对于动物和人随时间变化的偏好而言，折扣看来是个好的模型。折扣因子γ和利率(1/γ)–1是等价的。

在本章的其余部分里我们假设使用折扣回报，虽然有时我们将允许γ=1。至于这样假设的原因很快就会清楚。

潜藏在我们无限期的选择后面的是这样一个问题：如果环境不包含一个终止状态，或者智能体永远走不到终止状态，那么所有的环境历史就是无限长的，累加回报的效用值通常是无穷大。现在，我们可以同意+∞ 比–∞ 好，不过要比较出两个效用值都是+∞ 的序列的好坏就很难了。有 3 种解决办法，我们已经知道了其中的两个：

（1）使用折扣回报，无限序列的效用值仍然是有限的。事实上，如果回报不超过Rmax，并且γ＜1，那么通过无限等比级数的标准求和公式，我们得到

（2）如果环境包含有终止状态，而且智能体保证最终会到达其中之一的话，那么我们就不用比较无限序列了。一个确保能够到达终止状态的策略叫做适当策略。对于适当策略我们可以让γ=1（即累加回报）。图17.2（b）中的前3个策略是适当策略，而第4个不是。因为当非终止状态的回报是正的时候，智能体可以通过远离终止状态来获得无限的回报。这种不适当策略的存在，会导致求解MDP的标准算法在使用累加回报时失败，所以为使用折扣回报提供了一个好的理由。

（3）另一种可能性是根据每个时间步获得的平均回报对无限序列进行比较。假设4×3世界中的（1, 1）方格有0.1的回报，而其他非终止状态有0.01的回报。那么一个停留在（1, 1）的策略就比停留在其他状态的策略有更高的平均回报。在某些问题中，平均回报是一个有用的标准，不过对于平均回报算法的分析超出了本书的范围。

总之，使用折扣回报在评价状态序列时难度最低。最后一步是如何挑选策略，注意给定的策略π 不仅仅产生一个状态序列，而是整个可能的状态序列的范围，其中每一个状态序列有特定的由环境转移模型确定的概率。因此，策略的值是所得到的折扣回报的期望和，其中期望针对的是所有在执行该策略时可能发生的状态序列。最优策略π*是

下两节将描述寻找最优策略的算法。