2.1.1 马尔可夫决策过程和回溯图
在第1章中，已经简单介绍了强化学习的基本原理，这里简单回顾一下这些概念，并且进行深入阐述。首先是马尔可夫决策过程（Markov Decision Process, MDP）。这个决策过程基于以下原理：智能体的决策过程仅和其当前所处的状态有关，与智能体所经历的历史无关。在这种理想的状态下，智能体所处的每个状态都是有其价值的，可以定义对应的状态价值函数Vπ（st），注意到这个状态价值函数除了和当前时刻的状态st有关，还和我们采取的策略π有关。当然，这个状态函数是智能体在策略π的条件下，每个状态按照一定的概率采取不同的动作at得到的最终价值的期望，我们可以把状态价值函数进一步细化，得到对应的状态-动作价值函数Qπ（st，at）。于是在这个条件下，给每个对应的状态动作的组合对（st，at）计算对应的价值，整个强化学习模型的决策可以根据对应的组合对的值得到。由于马尔可夫的决策过程之间的状态具有固定的依赖关系，即当前的状态仅依赖于上一步的状态，这里可以使用回溯图（Backup Diagram）的数据结构来对决策过程进行描述。一个简单的回溯图如图2.1所示。
图2.1 简单的回溯图示例
在图2.1中，使用空心的圆形来代表某个状态s，用实心的圆形来代表智能体采取的某个动作a，箭头的链接代表状态和动作之间的因果关系。在这个图中可以看到，如果从初始状态s出发，根据策略π采取一个动作a，有一定的概率p，可以到达一个新的状态s′，同时获取奖励r。反之，根据这个回溯图可以找到状态s′是由状态s通过动作a得来的，这就是这个图被称为回溯图的原因。这样，从图2.1的回溯图可以直接看出，从初始状态出发，根据策略有三种可能的动作，同时每个动作有一定的概率能够各自到达两个新的状态。另外需要注意的是，回溯图不保证状态s和状态s′不同，有可能经过一次决策之后状态s回到自身。
在回溯图所描述的决策过程中，假如已知状态价值函数Vπ（st）或者状态-动作价值函数Qπ（st，at），可以很容易地根据这两个函数的定义，得到相应的递归关系，如式（2.1）和式（2.2）所示。
其中，st+1∈S代表st+1在所有st可能转移到的状态空间S中的取值；同样，at+1∈A代表at+1在所有的at可能转移到的状态空间A中的取值，Eπ的具体含义是在策略π下面的期望，具体的形式如式（2.3）所示。
其中，p（rt，st+1|at，st）为在状态st下，智能体采取动作at，转移到状态st+1，并且获取rt的奖励的概率。
在图2.1中，对应的是从某一个状态st出发，到达所有可能的其他状态的相关联的函数f（rt，st+1）按照概率的求和（这里使用的是任意函数，读者不难把式（2.3）应用于式（2.1）中的状态价值函数和式（2.2）中的状态-动作价值函数。注意，如果是状态-动作价值函数，则不需要考虑式（2.3）中第一个关于策略概率的求和，因为在状态-动作价值函数中动作是一个变量）。式（2.1）和式（2.2）成立的原因在于，在马尔可夫决策过程中，相应的策略π，状态价值函数Vπ（st）和状态-动作价值函数Qπ（st，at）与决策的历史无关（参见1.2.2节的内容），也即是仅和当前所处的状态st有关。这就给我们的递归计算过程提供了理论基础。接下来看一下基于式（2.1）和式（2.2）最简单的情况，即所谓最优策略下的情形。