马尔可夫决策过程

马尔可夫决策过程（Markov decision process，MDP）是强化学习中的基础，一般的，强化学习中所说的环境就是一个马尔可夫决策过程。不同于之前的MAB问题，马尔可夫决策过程包含状态信息以及状态的转移机制。
如果要用强化学习去解决一个实际问题，第一步要做的事情就是把这个实际问题抽象为一个马尔可夫决策过程，也即明确马尔可夫决策过程的各个组成要素。

马尔可夫过程

• 马尔可夫性质
  当且仅当某时刻的状态只取决于上一时刻的状态时，一个随机过程被称为具有马尔可夫性质（Markov property），也即：$$\mathbf{P}({\mathbf{S}}_{\mathbf{t}+1}|{\mathbf{S}}_{\mathbf{t}})=\mathbf{P}({\mathbf{S}}_{\mathbf{t}+1}|{\mathbf{S}}_1,\dots ,{\mathbf{S}}_{\mathbf{t}})$$

但需注意：马尔可夫性并不代表这个随机过程和历史完全无关。虽然 t + 1 时刻的状态只与 t 时刻的状态有关，但是 t 时刻的状态其实包含了 t - 1 时刻的状态的信息，通过这种链式的关系，历史的信息被传递到了现在。马尔可夫性可以大大简化运算，因为只要当前状态可知，所有的历史信息都不再需要了，利用当前状态信息就可以决定未来。

• 马尔可夫过程
  而具有马尔可夫性质的随机过程，称为马尔可夫过程（Markov process），或马尔科夫链（Markov chain）。通常，使用二元组$⟨\mathcal{S},\mathcal{P}⟩$来描述，

  • $\mathcal{S}$：有限数量的状态集合；
  • $\mathcal{P}$：状态转移矩阵，如：$$\mathcal{P}=\left[\begin{array}{ccc}\mathbf{P}({\mathbf{s}}_1|{\mathbf{s}}_1)& \cdots & \mathbf{P}({\mathbf{s}}_{\mathbf{n}}|{\mathbf{s}}_1)\\ ⋮& \ddots & ⋮\\ \mathbf{P}({\mathbf{s}}_1|{\mathbf{s}}_{\mathbf{n}})& \cdots & \mathbf{P}({\mathbf{s}}_{\mathbf{n}}|{\mathbf{s}}_{\mathbf{n}})\end{array}\right]$$

• 补充：序列 & 采样
  给定一个马尔可夫过程，我们就可以从某个状态出发，根据它的状态转移矩阵生成一个状态序列（episode），这个步骤也被叫做采样（sampling）。

马尔可夫奖励过程

通常，可以使用四元组$⟨\mathcal{S},\mathcal{P},\mathbf{r},\mathbf{\gamma }⟩$描述马尔可夫奖励过程（Markov reward process，MRP）：

• $\mathcal{S}$：有限状态的集合；
• $\mathcal{P}$：状态转移矩阵；
• $r$：奖励函数，$r\left(s\right)$表示转移到状态 s 时可获得奖励的期望；
• $\gamma$：折扣因子（discount factor），取值范围$\left[0,1\right)$。主要是标定远期效益的权重，因为远期利益具有一定不确定性，接近 1 表示更关注长期的累计奖励，接近 0 表示更考虑短期奖励。

回报 & 价值

• 回报（return）
  在 MRP 中，从第 $t$ 时刻状态 $S_t$ 开始，直到终止状态时，所有奖励的衰减之和称为回报 $G_t$ ：$${\mathbf{G}}_{\mathbf{t}}={\mathbf{R}}_{\mathbf{t}}+\mathbf{\gamma }{\mathbf{R}}_{\mathbf{t}+1}+{\mathbf{\gamma }}^2{\mathbf{R}}_{\mathbf{t}+2}+\cdots =\sum _{\mathbf{k}=0}^{\infty }{\mathbf{\gamma }}^{\mathbf{k}}{\mathbf{R}}_{\mathbf{t}+\mathbf{k}}$$
• 价值（value）
  在 MRP 中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值（value），所有状态的价值就组成了价值函数（value function），此时函数输入是某个状态，输出是该状态的价值，可表示为：$$\mathbf{V}(\mathbf{s})=\mathbb{E}[{\mathbf{G}}_{\mathbf{t}}|{\mathbf{S}}_{\mathbf{t}}=\mathbf{s}]$$

  价值函数有如下推导：
  $$\begin{array}{rl}V(\mathbf{s})& =\mathbb{E}[G_t|S_t=\mathbf{s}]\\ & =\mathbb{E}[R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\dots |S_t=\mathbf{s}]\\ & =\mathbb{E}[R_t+\gamma (R_{t+1}+\gamma R_{t+2}+\dots )|S_t=\mathbf{s}]\\ & =\mathbb{E}[R_t+\gamma G_{t+1}|S_t=\mathbf{s}]\\ & =\mathbb{E}[R_t+\gamma V(S_{t+1})|S_t=\mathbf{s}]\end{array}$$
  最后一行，一是$\mathbb{E}[{\mathbf{R}}_{\mathbf{t}}|{\mathbf{S}}_{\mathbf{t}}=\mathbf{s}]=\mathbf{r}(\mathbf{s})$，即时奖励的期望正是奖励函数的输出；二是$\mathbb{E}[\mathbf{\gamma V}({\mathbf{S}}_{\mathbf{t}+1})|S_t=\mathbf{s}]$，即剩余部分可根据状态转移概率得到，故有：$$V(\mathbf{s})=\mathbf{r}(\mathbf{s})+\gamma \sum _{{\mathbf{s}}^{\prime }\in S}\mathbf{p}({\mathbf{s}}^{\prime }|\mathbf{s})V({\mathbf{s}}^{\prime })$$
  上式即后面要说到的贝尔曼方程。

回报需要对应某一个具体的序列才能计算，价值则是对当前状态所有序列的回报求期望，平均化了，更具一般意义。

马尔可夫决策过程

马尔可夫过程、马尔可夫奖励过程都是是自发改变的随机过程，但绝大多数的强化学习是智能体（agent）和环境的交互，也即智能体会对环境施加影响（称为智能体的动作）来改变这个随机过程，就变成马尔可夫决策过程（Markov decision process，MDP）。通常，使用五元组$⟨\mathcal{S},\mathcal{A},\mathbf{P},\mathbf{r},\mathbf{\gamma }⟩$来描述，其中：

• $\mathcal{S}$：状态的集合；
• $\mathcal{A}$：动作的集合；
• $\gamma$：折扣因子；
• $r\left(s,a\right)$：奖励函数，此时奖励可以同时取决于状态s 和动作$a$ ，在奖励函数只取决于状态s 时，则退化为$r\left(s\right)$；
• $\mathbf{P}({\mathbf{s}}^{\prime }|\mathbf{s},\mathbf{a})$：状态转移函数，表示在状态s 执行动作$a$ 之后到达状态$s^{\prime }$ 的概率。

（1） MDP 中，状态转移使用函数表示，一是因为状态转移也与动作有关了，是一个三维数组，而非一个矩阵（二维数组）；二是因为状态转移函数更具有一般意义，例如，若状态集合不是有限的，就无法用数组表示，但可以用状态转移函数表示。
（2）MDP 引入了智能体的动作，智能体会做出某个动作选择和环境进行不断交互，此时就是真正的强化学习的基本框架，可以用下图表示，下图将MDP普化为一般环境，就可以表示大部分强化学习的过程了：

智能体当前处于状态$S_t$，选择做出动作$A_t$，作用于环境后，环境根据奖励函数和状态转移函数反馈回$S_{t+1}$、$R_t$给智能体。

智能体的目标是最大化得到的累计奖励reward，而且强化学习最重要的也就是计算累计的reward。

上图是MDP一个例子，如：在状态$S_4$下，如果采取动作“概率前往”，就能得到奖励 1，并且会分别以概率 0.2、0.4、0.4 转移到$S_2$、$S_3$或$S_4$。

策略

策略（Policy）：智能体根据当前状态从动作的集合中选择一个动作的函数，表示为：$\pi (\mathbf{a}|\mathbf{s})=\mathbf{P}({\mathbf{A}}_{\mathbf{t}}=\mathbf{a}|{\mathbf{S}}_{\mathbf{t}}=\mathbf{s})$

①确定性策略（deterministic policy）：
它在每个状态时只输出一个确定性的动作，即只有该动作的概率为 1，其他动作的概率为 0；
②随机性策略（stochastic policy）：
它在每个状态时输出的是关于动作的概率分布（然后根据该分布进行采样就可以得到一个动作）。

状态价值函数 & 动作价值函数

状态价值函数（state-value function）：在 MDP 中，基于策略 $\pi$ 的状态价值函数（state-value function），定义为从状态 $s$ 出发遵循策略 $\pi$ 能获得的期望回报：
$${\mathbf{V}}^{\pi }(\mathbf{s})={\mathbb{E}}_{\pi }[{\mathbf{G}}_{\mathbf{t}}|{\mathbf{S}}_{\mathbf{t}}=\mathbf{s}]$$

动作价值函数（action-value function）：在 MDP 中，遵循策略 $\pi$ 时，对当前状态 $s$ 执行动作 $a$ 得到的期望回报：
$$Q^{\pi }(\mathbf{s},\mathbf{a})={\mathbb{E}}_{\pi }[G_t|{\mathbf{S}}_t=\mathbf{s},{\mathbf{A}}_t=\mathbf{a}]$$

状态价值V和动作价值Q的关系：
当给定一个策略 $\pi$ 时，
①状态 $s$ 的价值 = 在该状态下基于策略 $\pi$ 采取所有动作的概率与相应的价值相乘再求和的结果：$$V^{\pi }(\mathbf{s})=\sum _{\mathbf{a}\in A}\pi (\mathbf{a}|\mathbf{s})Q^{\pi }(\mathbf{s},\mathbf{a})$$

②状态 $s$ 下选择动作 $a$ 的动作价值 = 即时奖励 + 经过衰减后的所有可能的下一个状态的状态转移概率与相应的价值的乘积：$$Q^{\pi }(\mathbf{s},\mathbf{a})=r(\mathbf{s},\mathbf{a})+\gamma \sum _{s^{\prime }\in S}P({\mathbf{s}}^{\prime }|\mathbf{s},\mathbf{a})V^{\pi }({\mathbf{s}}^{\prime })$$

可见，当前状态s可能存在多个可选动作(a、b、c…），选择具体某个动作，如动作a能获得的奖励期望就是多少，由动作价值函数描述，而将这多个动作的动作价值一起计算，如求加权平均，就得到该状态的状态价值，这个就由状态价值函数描述。

贝尔曼方程

贝尔曼期望方程

两个价值函数的贝尔曼期望方程（Bellman Expectation Equation）：
$$\begin{array}{rl}{V}^{\pi }(s)& ={\mathbb{E}}_{\pi }[R_t+\gamma V^{\pi }(S_{t+1})|S_t=s]\\ & =\sum _{a\in A}\pi (a|s)\left(r(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V^{\pi }(s^{\prime })\right)\\ Q^{\pi }(s,a)& ={\mathbb{E}}_{\pi }[R_t+\gamma Q^{\pi }(S_{t+1},A_{t+1})|S_t=s,A_t=a]\\ & =r(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\end{array}$$
贝尔曼方程有什么用？
价值函数和贝尔曼方程是强化学习非常重要的组成部分，之后的一些强化学习算法都是据此推导出来的。

贝尔曼最优方程

强化学习的目标通常是找到一个策略，使得智能体从初始状态出发能获得最多的期望回报。那么就可能存在一个策略获得的期望回报不差于其他策略，这个策略叫做最优策略（optimal policy），可能有多个，表示为 ${\mathbf{\pi }}^{\ast }(\mathbf{s})$。相应的，最优策略下可以定义最优状态价值函数和最优动作价值函数，分别如下：

• 最优状态价值函数：$V^{\ast }(\mathbf{s})={\max }_{\pi }{V}^{\pi }(\mathbf{s}),\forall \mathbf{s}\in \mathcal{S}$；
• 最优动作价值函数：$Q^{\ast }(\mathbf{s},\mathbf{a})={\max }_{\pi }{Q}^{\pi }(\mathbf{s},\mathbf{a}),\forall \mathbf{s}\in \mathcal{S},\mathbf{a}\in \mathcal{A}$

此时两者的关系：
$${\mathbf{Q}}^{\ast }(\mathbf{s},\mathbf{a})=\mathbf{r}(\mathbf{s},\mathbf{a})+\mathbf{\gamma }\sum _{{\mathbf{s}}^{\prime }\in S}\mathbf{P}({\mathbf{s}}^{\prime }|\mathbf{s},\mathbf{a}){\mathbf{V}}^{\ast }({\mathbf{s}}^{\prime })$$
即为了使 Q 最大，我们需要在当前的状态动作对$(s,a)$之后都执行最优策略;
$${\mathbf{V}}^{\ast }(\mathbf{s})=\underset{\mathbf{a}\in \mathcal{A}}{\max }{\mathbf{Q}}^{\ast }(\mathbf{s},\mathbf{a})$$
即最优状态价值是选择此时使最优动作价值最大的那一个动作时的状态价值。
根据最优价值函数，可以得到贝尔曼最优方程（Bellman optimality equation）：
V ∗ ( s ) = max ⁡ a ∈ A { r ( s , a ) + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) V ∗ ( s ′ ) } Q ∗ ( s , a ) = r ( s , a ) + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) max ⁡ a ′ ∈ A Q ∗ ( s ′ , a ′ ) V^{*}(\bm{s}) =\max_{a\in\mathcal{A}}\{r(\bm{s},a)+\gamma\sum_{s^{\prime}\in \mathcal{S}}p(\bm{s}^{\prime}|\bm{s},a)V^{*}(\bm{s}^{\prime})\}\newline Q^{*}(\bm{s},a) =r(\bm{s},a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}p(\bm{s}^{ \prime}|\bm{s},a)\max_{a^{\prime}\in\mathcal{A}}Q^{*}(\bm{s}^{\prime},a^{ \prime}) V∗(s)=a∈Amax​{r(s,a)+γs′∈S∑​p(s′∣s,a)V∗(s′)}Q∗(s,a)=r(s,a)+γs′∈S∑​p(s′∣s,a)a′∈Amax​Q∗(s′,a′)

求解价值函数

强化学习最重要的就是计算累计的reward，我们希望能够找到一个平均累计reward最优的policy，而Value Function正是一种用于计算期望累计reward的函数。而我们上面定义了相关的价值函数，那应该如何求解呢？常用的三种方法：

蒙特卡洛

蒙特卡洛方法（Monte-Carlo methods）也被称为统计模拟方法，是一种基于概率统计的数值计算方法。一言以蔽之，就是通过重复随机抽样，利用概率统计计算，随着重复越多，最终能很好的逼近真实概率分布或理论值。
具体怎么做呢？
如前文所讲，一个状态的期望回报就是这个状态的价值，那么就可以基于某个策略在 MDP 上采样很多条序列，计算从这个状态出发的回报再综合求其期望，即：$$V^{\pi }(\mathbf{s})={\mathbb{E}}_{\pi }[{\mathbf{G}}_t|{\mathbf{S}}_t=\mathbf{s}]\approx \frac{1}{N}\sum _{i=1}^N{\mathbf{G}}_t^{(i)}$$
计算回报的期望时，除了可以把所有的回报加起来除以次数，还有一种增量更新的方法：
$$\mathbf{V}(\mathbf{s})+\frac{1}{\mathbf{N}(\mathbf{s})}(\mathbf{G}-\mathbf{V}(\mathbf{S}))$$

值得一提的是，可见，蒙特卡洛方法是不需要事先知道环境模型的，也即无需知道奖励函数和转移概率函数，它是通过采用来拟合、估计价值函数。所以蒙特卡洛是一种无模型（Model-free）的强化学习方法，并且它是基于价值的方法，所以蒙特卡洛还是一种 value-based 的方法。

动态规划算法

强化学习——动态规划算法

时序差分算法

强化学习——时序差分算法

小结

• 蒙特卡洛和时序差分是无模型（Model-free）的算法，动态规划是基于模型（Model-based）的方法；
• 目前所说的算法，MC、DP以及TD都是 value-based 的方法，也即主要是在更新价值函数来推出最优策略；
• DP 算法里的策略迭代和价值迭代通常只适用于有限马尔可夫决策过程，即状态空间和动作空间是离散且有限的；TD 算法的 Sarsa 和 Q-learning 也更适合于当环境是有限状态集合和有限动作集合时。