2.1.2 贪心策略和最优策略
根据回溯图可以看到，从一个初始状态s出发，采取一定的策略可以以一定的概率到达一个新的状态s′，并且获得对应的奖励r。在强化学习的问题中，初始状态和最终到达的状态都不是智能体所能控制的，智能体能够控制的只有这里的策略π。为了能够评估策略的好坏，可以按照策略获得奖励的期望对策略的效果进行评估，也就是定义一个策略的函数（或者准确一点，可以称为泛函，因为策略本身也是一个函数），这个函数通过给定一个策略和对应的决策环境，可以告诉我们这个策略能够获取多少预期的奖励。我们可以粗略地用式（2.4）来对这个函数进行描述，也就是求在策略π下的奖励r的期望。虽然这个公式看起来比较简单，但是这个公式蕴含的一个信息很重要：强化学习的最终的目的是为了找到一个策略，让这个策略对应奖励的期望最大，如式（2.5）所示，这里用π∗来表示找到的最优策略。
为了得到这个最优策略，需要根据一定的方法确定策略间的排序关系。因为状态价值函数反映了智能体在某一状态下未来可能获取的奖励的期望，所以假如有两个策略π1和π2，且π1≥π2，可以得到对于任意状态s，有
。有了这种策略排序关系，可以定义一个最优策略π∗，也就是对于任意其他的策略π，在任意状态s的情况下，均有
。在这种情况下，由于对应的价值函数永远是最大的，可以简单选择使价值函数
最大的状态s′，作为智能体决策的下一步，其对应的状态价值函数和状态-动作价值函数被分别称为最优状态价值函数和最优状态-动作价值函数。这种最简单的策略被称为贪心（Greedy）策略，在这种策略下，最优状态价值函数V∗和最优状态-动作价值函数Q∗如式（2.6）和式（2.7）所示（默认使用右上角的星号来代表对应函数使用了贪心策略）。
简单解释一下式（2.6）和式（2.7）。首先对于式（2.6）来说，为了能够得到最优的策略，需要找到一个最优的动作at，使得式（2.1）中的期望最大，也就是式（2.6）中第一个等号右边的内容，希望在最优策略下采取某个动作得到的回报最大。将这个公式对应的期望的内容展开，结合式（2.3）的定义（其中策略部分对所有可能的动作求和在当前的最优策略下变为只考虑最优的动作），就能得到式（2.6）中第二个等式的结果。对于式（2.7），第一个等号跟前面的叙述类似，这里不再赘述，而第二个等号之所以成立，是因为我们已经把所有的动作从最优状态价值函数V∗分离开来，形成了最优状态-动作价值函数Q∗，这个函数的变量是t时刻不同的状态st和动作at，因此函数在公式中只需要考虑下一步的动作at+1，并且取这个动作让状态-动作价值函数Q∗取得最大值。
由于式（2.6）的和式（2.7）的出发点不同，对应的回溯图的结构也不相同，图2.2对应地描述了这两种不同的回溯图。在式（2.6）的情况下，由于出发点是状态s，所以整体的图结构和图2.1类似，只不过对应的策略选择的原则是使后续的状态函数相关的期望取得最大。同样，在式（2.7）的状态下，由于最优状态-动作价值函数和当前状态下采取的动作相关，所以从当前的动作出发，可以看到需要选择下一步的动作，使当前的状态-动作价值函数的值最大。
图2.2 最优状态价值函数的回溯图（左）和最优状态-动作价值函数的回溯图（右）