强化学习---马尔可夫决策过程 MP MRP MDP

1.马尔可夫过程（MP）

1.1马尔可夫性质

马尔可夫性质（Markov property）是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。我们假设一个离散的随机过程：$X_0$,$X_1$, · · · ,$X_T$ ，这些随机变量的所有可能取值的集合被称为状态空间。如果$X_{t+1}$ 对于过去状态的条件概率分布仅是$X_t$ 的一个函数，则:
$$p(X_{t+1}=x_{t+1}|X_{0:t}=x_{0:t})=p(X_{t+1}=x_{t+1}|X_t=x_t)$$
从上述式子可以得到，未来仅有当前决定，与过去无关。马尔可夫性质是所有马尔可夫过程的基础。

1.2马尔可夫链

假设一组随机变量$s_1$, · · · ,$s_t$ 满足马尔可夫性质。我们定义状态的历史为$h_t=s_1,s_2,s_3,...,s_t$，则马克可夫过程可以概括为：
$$p(s_{t+1}|s_t)=p(s_{t+1}|h_t)$$
同时，我们将离散的马尔可夫过程成为马尔可夫链。

2.马尔可夫奖励过程（MRP）

马尔可夫奖励过程（Markov reward process, MRP）是马尔可夫链加上奖励函数。在马尔可夫奖励过程中，状态转移矩阵和状态都与马尔可夫链一样，只是多了奖励函数（reward function）,即MRP=MP+reward。

2.1回报与价值函数

回报是指把奖励进行折扣后所获得的奖励。回报可以定义为奖励的逐步叠加，即：
$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+{\gamma }^3{r}_{t+4}+...+{\gamma }^{T-t-1}{r}_T$$
其中引入了$\gamma$作为折扣因子，即越往后得到的奖励，折扣越多。当我们定义了回报奖励之后，就可以定义状态价值函数：
$$V^t(s)=E[G_t|s_t=s]$$
$$V^t(s)=E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...+{\gamma }^{T-t-1}{r}_T|s_t=s]$$

2.2折扣因子

引入折扣因子的原因有多个：
第一，马尔可夫过程有可能带环，如果不引入折扣，则可能形成无穷的奖励，导致整个迭代过程无法结束。
第二，对现实的建模有不准确性，也代表了未来评估的不准确性，因此对未来引入折扣以展示其不确定性，最终希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。
第三，折扣因子可以作为强化学习智能体的一个超参数（hyperparameter）来进行调整，通过调整折扣因子，我们可以得到不同动作的智能体。

2.3贝尔曼方程

我们可以从价值函数中推导出贝尔曼方程如下：
$$V(s)=R(s)+\gamma \sum _{s^{\prime }\in S}p(s\prime |s)V(s\prime )$$
其中，s′ 可以看成未来的所有状态，p(s′|s) 是指从当前状态转移到未来状态的概率。V (s′) 代表的是未来某一个状态的价值。从上述式子我们可以看出未来奖励的折扣总和加上即时奖励，就组成了贝尔曼方程。
贝尔曼方程的解析解的推导：
$$V=R+\gamma PV$$$$IV=R+\gamma PV$$$$(I-\gamma P)V=R$$$$V=(I-\gamma P{)}^{-1}R$$

则贝尔曼方程的解析解为：
$$V=(I-\gamma P{)}^{-1}R$$
我们可以通过矩阵求逆把V 的价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是$O(N^3)$。所以当状态非常多的时候，比如从10 个状态到1000 个状态，或者到100 万个状态，当我们有100 万个状态的时候，状态转移矩阵就会是一个100 乘100 的矩阵，对这样一个大矩阵求逆是非常困难的。所以这种通过解析解去求解的方法只适用于很小量的马尔可夫奖励过程。

3.马尔可夫决策过程（MDP）

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策（决策是指动作），即MDP=MRP+Action。此外，状态转移也多了一个条件，变成了$p(s_{t+1}=s\prime |s_t=s,a_t=a)$。未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作。马尔可夫决策过程满足条件：
$$p(s_{t+1}|s_t,a_t)=p(s_{t+1}|h_t,a_t)$$
此时奖励R因为引入了动作，而变为：
$$R(s_t=s,a_t=a)=E[r_t|s_t=s,a_t=a]$$

3.1策略

策略定义了在某一个状态应该采取什么样的动作。知道当前状态后，我们可以把当前状态代入策略函
数来得到一个概率，即：
$$\pi (a|s)=p(a_t=a|s_t=s)$$
当已知马尔可夫决策过程和策略π，我们可以把马尔可夫决策过程转换成马尔可夫奖励过程。从奖励函数的角度来看：
$$R_{\pi (s)}=\sum _{a\in A}\pi (a|s)R(s,a)$$
即此时因为所有的action已知，那么当前状态的奖励应该等于所有action所对应的奖励之和。

3.2MP，MRP与MDP的区别：

对于MP与MRP来说，比如当前状态是s，那么直接通过转移概率决定下一个状态是什么。

但对于马尔可夫决策过程，它的中间多了一层动作a ，即智能体在当前状态的时候，首先要决定采取某一种动作，这样会到达某一个黑色的节点。到达这个黑色的节点后，因为有一定的不确定性，所以当智能体当前状态以及智能体当前采取的动作决定过后，智能体进入未来的状态其实也是一个概率分布。

3.3MDP中的价值函数：

马尔可夫决策过程中的价值函数可定义为：
$$V_{\pi }(s)=E_{\pi }[G_t|s_t=s]$$
同时我们引入一个Q函数，Q函数也被成为动作价值函数，Q 函数定义的是在某一个状态采取某一个动作，它有可能得到的回报的一个期望，即：
$$Q_{\pi }(s,a)=E_{\pi }[G_t|s_t=s,a_t=a]$$
则MDP的价值函数通过Q函数的形式可以有如下表达：
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)Q_{\pi }(s,a)$$
此处Q函数可以推导出贝尔曼方程如下：
$$Q(s,a)=R(s,a)+\gamma \sum _{s\prime \in S}p(s\prime |s,a)V(s\prime )$$

3.4贝尔曼期望方程：

价值函数与Q函数都可以被拆分为：即时奖励和后续状态的折扣价值两部分。分解状态价值函数可以得到：
$$V_{\pi }(s)=E_{\pi }[r_{t+1}+\gamma V_{\pi }(s_{t+1})|s_t=s]$$$$Q_{\pi }(s,a)=E_{\pi }[r_{t+1}+\gamma Q_{\pi }(s_{t+1},a_{t+1})|s_t=s,a_t=a]$$
上面二者即为贝尔曼期望方程，它定义了当前状态与未来状态之间的关联。
假设引入价值函数与Q函数的关系式以及Q函数的贝尔曼方程：
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)Q\pi (s,a)$$$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s\prime \in S}p(s\prime |s,a)V_{\pi }(s\prime )$$
(1)式(2)式分别互相带入可以得到贝尔曼期望方程的另一种形式:
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)(R(s,a)+\gamma \sum _{s\prime \in S}p(s\prime |s,a)V_{\pi }(s\prime ))$$$$Q_{\pi }(s,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 )$$