该节内容摘自于《动手学强化学习》第3章 马尔可夫决策过程。
1.马尔可夫过程
当且仅当某时刻的状态只取决于上一时刻的状态时，一个随机过程被称为具有马尔可夫性质，用公式表示为$P(S_{t+1}\vert S_t)=P(S_{t+1}\vert S_1,\cdots,S_t)$。马尔可夫过程指具有马尔可夫性质的随机过程，也被称为马尔可夫链。我们通常用元组$<S, P>$描述一个马尔可夫过程，$S$是有限数量的状态集合，$P$是状态转移矩阵。假设一共有$n$个状态，此时$S={s_1,s_2,\cdots,s_n}$，此时$P$定义了所有状态对之间的转移概率。
给定一个马尔可夫过程，我们就可以从某个状态出发，根据它的状态转移矩阵生成一个状态序列（episode），这个步骤也被叫做采样（sampling）。
2.马尔可夫奖励过程
在马尔可夫过程的基础上加入奖励函数$r$和折扣因子$\gamma$，就可以得到马尔可夫奖励过程。一个马尔可夫奖励过程由$<S,P,r,\gamma>$构成，各个组成元素的含义如下所示：
- $S$是有限状态的集合
- $P$是状态转移的矩阵
- $r$是奖励函数，某个状态$s$的奖励$r(s)$指转移到该状态时可以获得奖励的期望
- $\gamma$是折扣因子
在一个马尔可夫奖励过程中，从第$t$时刻状态$S_t$开始，直到终止状态时，所有奖励的衰减之和称为回报$G_t$，公式如下：
\[G_t=R_t+\gamma R_{t+1}+\gamma^2R_{t+2} + \cdots = \sum_{k=0}^\infty \gamma^kR_{t+k}\]在马尔可夫奖励过程中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值（value），所有状态的价值就组成了价值函数（value function）。价值函数的输入是某个状态，输出是这个状态的价值，我们将其写成$V(s)=E[G_t\vert S_t=s]$，展开为：
\[\begin{align*} V(s)&=E[G_t\vert S_t=s] \\ &= E[R_t+\gamma R_{t+1} + \cdots \vert S_t=s] \\ &= E[R_t+\gamma(R_{t+1} + \cdots) \vert S_t=s] \\ &= E[R_t+\gamma G_{t+1}\vert S_t=s] \\ &= E[R_t+\gamma V(S_{t+1}) \vert S_t=s] \end{align*}\]在上式中，一方面即时奖励的期望正是奖励函数的输出，即$E[R_t\vert S_t=s]=r(s)$；另一方面，等式中剩余部分$E[\gamma V(S_{t+1}) \vert S_t=s]$可以根据转移概率得到，即
\[V(s)=r(s) + \gamma \sum_{s^{'}\in S}p(s^{'}\vert s) V(s^{'})\]这也就是贝尔曼方程。若一个马尔可夫奖励过程一共有$n$个状态，即$S={s_1,\cdots,s_n}$，所有状态的价值表示为一个列向量$V=[V(s_1),\cdots, V(s_n)]^T$，同理奖励函数写成一个列向量$R=[r(s_1), \dots, r(s_n)]^T$，因此有：
\[V=R+\gamma P V\]求解得到：
\[V=(I-\gamma P)^{-1}R\]以上解析解的计算复杂度是$O(n^3)$，其中$n$是状态个数，因此这种方法只适用于很小的马尔可夫奖励过程。
3.马尔可夫决策过程
前面讲到的马尔可夫过程和马尔可夫奖励过程都是自发改变的随机过程。在马尔可夫奖励过程的基础上加入动作，就得到了马尔可夫决策过程。马尔可夫决策过程由元组$<S, A, P, r, \gamma>$构成。
3.1 策略
智能体的策略（policy）通常由字母$\pi$表示。策略$\pi(a \vert s)=P(A_t=a\vert S_t=s)$是一个函数，表示在输入状态$s$情况下采取动作$a$的概率。当一个策略是确定性策略（deterministic policy）时，它在每个状态时只输出一个确定性的动作，即只有该动作的概率为 1，其他动作的概率为 0；当一个策略是随机性策略（stochastic policy）时，它在每个状态时输出的是关于动作的概率分布，然后根据该分布进行采样就可以得到一个动作。
3.2 状态价值函数
我们用$V^\pi(s)$表示在MDP中基于策略$\pi$的状态价值函数（state-value function），定义为从状态$s$出发遵循策略$\pi$能获得的期望回报，数学表达为：
\[V^\pi(s)=E_{\pi}[G_t \vert S_t=s]\]3.3 动作价值函数
用$Q^{\pi}(s, a)$表示在MDP遵循策略$\pi$时，对当前状态$s$执行动作$a$得到的期望回报：
\[Q^{\pi}(s, a)=E_{\pi}[G_t \vert S_t=s, A_t=a]\]状态价值函数和动作价值函数之间的关系：在使用策略$\pi$中，状态$s$的价值等于在该状态下基于策略$\pi$采取所有动作的概率与相应的价值相乘再求和的结果：
\[V^{\pi}(s)=\sum_{a\in A}\pi(a \vert s)Q^{\pi}(s, a)\]3.4 贝尔曼期望方程
\[\begin{align*} V^{\pi}(s)&=E_{\pi}[R_t+\gamma V^{\pi}(S_{t+1})\vert S_t=s] \\ &=\sum_{a\in A}\pi(a\vert s)\left(r(s, a)+\gamma\sum_{s^{'}\in S}p(s^{'}\vert s, a)V^{\pi}(s^{'})\right) \\ Q^{\pi}(s, a) &= E_{\pi}[R_t+\gamma Q^{\pi}(S_{t+1}, A_{t+1}) \vert S_t=s, A_t=a] \\ &= r(s, a) + \gamma \sum_{s^{'}\in S}p(s^{'} \vert s, a) \sum_{a^{'} \in A} \pi(a^{'}\vert s^{'}) Q^{\pi}(s^{'}, a^{'}) \end{align*}\]3.5 蒙特卡洛方法
我们现在介绍如何用蒙特卡洛方法来估计一个策略在一个马尔可夫决策过程中的状态价值函数。回忆一下，一个状态的价值是它的期望回报，那么一个很直观的想法就是用策略在 MDP 上采样很多条序列，计算从这个状态出发的回报再求其期望就可以了，公式如下：
\[V^{\pi}(s) = E_{\pi}[G_t \vert S_t=s] \approx \frac{1}{N}\sum_{i=1}^NG_t^{(i)}\]