2.1.1 马尔可夫决策过程和回溯图

在第1章中，已经简单介绍了强化学习的基本原理，这里简单回顾一下这些概念，并且进行深入阐述。首先是马尔可夫决策过程（Markov Decision Process, MDP）。这个决策过程基于以下原理：智能体的决策过程仅和其当前所处的状态有关，与智能体所经历的历史无关。在这种理想的状态下，智能体所处的每个状态都是有其价值的，可以定义对应的状态价值函数V_π（s_t），注意到这个状态价值函数除了和当前时刻的状态s_t有关，还和我们采取的策略π有关。当然，这个状态函数是智能体在策略π的条件下，每个状态按照一定的概率采取不同的动作a_t得到的最终价值的期望，我们可以把状态价值函数进一步细化，得到对应的状态-动作价值函数Q_π（s_t，a_t）。于是在这个条件下，给每个对应的状态动作的组合对（s_t，a_t）计算对应的价值，整个强化学习模型的决策可以根据对应的组合对的值得到。由于马尔可夫的决策过程之间的状态具有固定的依赖关系，即当前的状态仅依赖于上一步的状态，这里可以使用回溯图（Backup Diagram）的数据结构来对决策过程进行描述。一个简单的回溯图如图2.1所示。

在图2.1中，使用空心的圆形来代表某个状态s，用实心的圆形来代表智能体采取的某个动作a，箭头的链接代表状态和动作之间的因果关系。在这个图中可以看到，如果从初始状态s出发，根据策略π采取一个动作a，有一定的概率p，可以到达一个新的状态s′，同时获取奖励r。反之，根据这个回溯图可以找到状态s′是由状态s通过动作a得来的，这就是这个图被称为回溯图的原因。这样，从图2.1的回溯图可以直接看出，从初始状态出发，根据策略有三种可能的动作，同时每个动作有一定的概率能够各自到达两个新的状态。另外需要注意的是，回溯图不保证状态s和状态s′不同，有可能经过一次决策之后状态s回到自身。

在回溯图所描述的决策过程中，假如已知状态价值函数V_π（s_t）或者状态-动作价值函数Q_π（s_t，a_t），可以很容易地根据这两个函数的定义，得到相应的递归关系，如式（2.1）和式（2.2）所示。

其中，s_t+1∈S代表s_t+1在所有s_t可能转移到的状态空间S中的取值；同样，a_t+1∈A代表a_t+1在所有的a_t可能转移到的状态空间A中的取值，E_π的具体含义是在策略π下面的期望，具体的形式如式（2.3）所示。

其中，p（r_t，s_t+1|a_t，s_t）为在状态s_t下，智能体采取动作a_t，转移到状态s_t+1，并且获取r_t的奖励的概率。

在图2.1中，对应的是从某一个状态s_t出发，到达所有可能的其他状态的相关联的函数f（r_t，s_t+1）按照概率的求和（这里使用的是任意函数，读者不难把式（2.3）应用于式（2.1）中的状态价值函数和式（2.2）中的状态-动作价值函数。注意，如果是状态-动作价值函数，则不需要考虑式（2.3）中第一个关于策略概率的求和，因为在状态-动作价值函数中动作是一个变量）。式（2.1）和式（2.2）成立的原因在于，在马尔可夫决策过程中，相应的策略π，状态价值函数V_π（s_t）和状态-动作价值函数Q_π（s_t，a_t）与决策的历史无关（参见1.2.2节的内容），也即是仅和当前所处的状态s_t有关。这就给我们的递归计算过程提供了理论基础。接下来看一下基于式（2.1）和式（2.2）最简单的情况，即所谓最优策略下的情形。