1.2.3　强化学习的数学模型——马尔可夫决策过程

强化学习的数学理论基础是具有马尔可夫性的马尔可夫决策过程，为建立强化学习的数学模型，先介绍马尔可夫性和马尔可夫决策过程。为了简单起见，假设所考虑的是离散型强化学习问题，即动作空间和状态空间均为离散的。

马尔可夫性，也称无后效性，是指在时间步t+1时，环境的反馈仅取决于上一时间步t的状态s_t和动作a_t，与时间步t-1及之前时间步的状态和动作没有关系。用条件概率表示马尔可夫性即为

马尔可夫性是一种理想化的假设，在实际中，环境在下一步的状态和反馈并不仅只和当前时间步的状态和动作相关，可能与之前的状态和动作也有一定的关系，但对于许多问题来讲，这种假设不会对强化学习结果造成大的影响，例如棋类游戏或电子对战游戏。倘若系统下一步的状态和反馈确实和当前步及更早的时间步的状态和动作都有强相关关系，则不能使用强化学习来学习最优策略。

依赖于时序的且具有马尔可夫性的决策过程称为马尔可夫决策过程（Markov Decision Process，MDP）。一般的马尔可夫决策过程由状态空间S、动作空间A、状态转移概率函数p和奖励函数R（或r）来描述，即四元组MDP=（S，A，p，R）。强化学习中的马尔可夫决策过程增加了一个折扣系数γ，用于计算累积折扣奖励，所以用于强化学习的马尔可夫决策过程由一个五元组构成，即MDP=（S，A，p，R，γ）。以下从数学上对五元组进行定义。

（1）S：状态空间，表示环境的所有可能状态组成的集合。设环境一共有n_s个可能的状态，s_i，i=1，2，…，n_s表示第i种状态，则S={s₁，s₂，…，s_ns}。

（2）A：动作空间，表示智能体能对环境施加的所有可能动作组成的集合。设智能体一共有n_a个可能动作，a_i，i=1，2，…，n_a表示第i个动作，则A={a₁，a₂，…，a_na}。智能体在状态s时可用的合法动作的集合记为A（s），显然A（s）⊆A。

（3）p：状态转移概率函数，表示环境在当前状态s下，被智能体施行动作a，状态转移到s′的概率。状态转移概率在数学上可以定义为一个条件概率函数，即

如果p（s′|s，a）只能等于0或1，称其为确定性状态转移概率；否则称其为随机状态转移概率。在确定性状态转移概率下，p（s′|s，a）=1也可以写作p（s，a）=s′。

（4）R：奖励函数，表示环境在当前状态s下，被智能体施行动作a后反馈给智能体的奖励值。奖励函数在数学上可以定义为一个二元函数，即

奖励函数有时也定义成一个三元函数，表示环境在当前状态s下，被智能体施行动作a，状态转移到s′后反馈给智能体的奖励值，即

二元奖励函数是三元奖励函数在分布p（s′|s，a）下的期望，它们的关系如下：

显然，当p（s′|s，a）=1时，R（s，a）=r（s，a，s′）。

需要强调的是，奖励函数和状态转移概率函数一样，都是环境本身的属性，在环境构建时被定义。拥有相同状态空间和动作空间的环境，如果被定义了不同的状态转移概率函数或奖励函数，则应该被视为不用的环境。

（5）γ：折扣系数，用于计算累积折扣奖励。

智能体的策略π也是强化学习的一个重要组成部分。智能体在状态s的决策可以表示成一个条件概率函数

表示智能体在状态s时，执行动作a的概率。和状态转移概率一样，若π（a|s）只能等于0或1，则策略π称为确定性策略，此时如果π（a|s）=1，则策略函数也可以写成a=π（s）。否则称策略π为随机性策略。

根据马尔可夫决策过程，智能体和环境进行一局交互后，可以得到一条由状态、动作、奖励组成的序列，称这个序列为马尔可夫序列（MDP Sequence）或马尔可夫链（MDP Chain），即

这里，一次交互的数据S_t，A_t，R_t+1，S_t+1，t=0，1，…，T-1称为一个马尔可夫片段（MDP Section），表示环境在状态S_t时智能体执行动作A_t，环境反馈即时奖励R_t+1，同时环境状态转移到S_t+1。T表示系统交互到时间步T时到达终止状态。注意，这里S_T表示终止状态，但T的具体值可能会随着交互局次的不同而变化。例如，在两个局次的交互中，第1局次可能在第100个时间步到达终止状态，此时T=100，而第2局次的交互可能在第200个时间步到达终止状态，此时T=200。另外，读者在此要注意区别用于表示时间步的下标和用于表示集合中某个元素的下标，例如S_t表示第t步的状态，但S_t的一个样本s_t肯定是状态空间S中的某个元素，例如第i个元素，所以此时有s_t=s_i。

有的环境可能没有终止状态，需要一直交互下去。此时将得到一条无穷马尔可夫链

本书主要讨论存在终止状态且一般在有限时间步的交互后能够达到终止状态的环境。