一、马尔可夫过程
1、马尔可夫过程
一个马尔科夫过程就是指过程中的每个状态的转移只依赖于之前的n个状态，这个过程被称为1个n阶的模型，其中n是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程，每一个状态的转移只依赖于其之前的那一个状态。
2、马尔可夫链
马尔可夫链是随机变量X1,X2,X3…的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为状态空间。
设表示随机变量X在离散时间t时刻的取值。若该变量随时间变化的转移概率仅依赖于它的当前值，即：
也就是说，状态转移概率只依赖于前一个状态，则称这个变量为马尔可夫变量，其中为随机变量X可能的状态，P是状态转移概率矩阵，这个性质称为马尔可夫性质，马尔可夫链是满足马尔可夫性质的随机过程。
3、状态转移概率矩阵
马尔可夫链是通过转移概率定义的，转移概率指随机变量从一个时刻到下一个时刻，从状态转移到状态的概率：
记表示变量X在时刻t的取值为的概率，则随机变量X在时刻t+1的取值为的概率为：
假设状态的数目为n，则：
4、马尔科夫链实例
既然某一时刻状态转移的概率只依赖前一个状态，那么只要求出系统中任意两个状态之间的转移概率，马尔科夫链的模型就定了。
这个马尔科夫链是表示股市模型的，共有三种状态：牛市（Bull market）, 熊市（Bear market）和横盘（Stagnant market）。每一个状态都以一定的概率转化到下一个状态。比如，牛市以0.025的概率转化到横盘的状态。这个状态概率转化图可以以矩阵的形式表示。如果我们定义矩阵阵P某一位置P(i, j)的值为P(j|i)，即从状态i变为状态j的概率。另外定义牛市、熊市、横盘的状态分别为0、1、2，这样我们得到了马尔科夫链模型的状态转移矩阵为：
当这个状态转移矩阵P确定以后，整个股市模型就已经确定。
5、马尔可夫链收敛
以股市模型为例，假设初始状态为t0=[0.1,0.2,0.7]，然后算之后的状态。
从第18次开始，状态就开始收敛至[0.624,0.312,0.0625] 。
如果我们换一个初始状态t0，比如[0.2,0.3.0.5]，继续运行上面的代码，只是将init_array变一下，最后结果为：
到第18次的时候，又收敛到了[0.624,0.312,0.0625]。
不管我们的初始状态是什么样子的，只要状态转移矩阵不发生变化，当n→∞时，最终状态始终会收敛到一个固定值。
6、马尔可夫链细致平稳条件
马尔科夫链要能收敛，需要满足以下条件：
可能的状态数是有限的。状态间的转移概率需要固定不变。从任意状态能够转变到任意状态。不能是简单的循环，例如全是从x到y再从y到x。
细致平衡条件（Detailed Balance Condition）：给定一个马尔科夫链，分布π和概率转移矩阵P，如果等式成立：
则此马尔科夫链具有一个平稳分布（Stationary Distribution)。
证明过程：，取j→∞，就可以得到矩阵表达式：。
二、隐马尔可夫链
1、马尔科夫链的缺陷
很明显，前后关系的缺失，带来了信息的缺失，比如我们的股市，如果只是观测市场，我们只能知道当天的价格、成交量等信息，但是并不知道当前股市处于什么样的状态（牛市、熊市、震荡、反弹等），在这种情况下我们有两个状态集合，一个可以观察到的状态集合（股市价格成交量状态等）和一个隐藏的状态集合（股市状态）。我们可以将这种类型的过程建模为有一个隐藏的马尔科夫过程和一个与这个隐藏马尔科夫过程概率相关的并且可以观察到的状态集合，就是隐马尔科夫模型。
2、隐马尔可夫链
隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。
3、隐马尔可夫链例子
假设我手里有三个不同的骰子。
第一个骰子6个面（称这个骰子为D6），每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。第三个骰子有八个面（称这个骰子为D8），每个面（1，2，3，4，5，6，7，8）出现的概率是1/8。
假设我们开始掷骰子，我们先从三个骰子里挑一个，挑到每一个骰子的概率都是1/3。然后我们掷骰子，得到一个数字，1，2，3，4，5，6，7，8中的一个。不停的重复上述过程，我们会得到一串数字，每个数字都是1，2，3，4，5，6，7，8中的一个。例如我们可能得到这么一串数字（掷骰子10次）：1 6 3 5 2 7 3 5 2 4。这串数字叫做可见状态链。
但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是你用的骰子的序列。比如，隐含状态链有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8
一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（骰子）之间存在转换概率（transition probability）。
可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability）。就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。
4、隐马尔可夫链HMM模型的三类问题
（1）知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道每次掷出来的都是哪种骰子（隐含状态链）。 在语音识别领域，叫做解码问题。
（2）还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出这个结果的概率。 ——反欺诈。
（3）知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率），观测到很多次掷骰子的结果（可见状态链），我想反推出每种骰子是什么（转换概率）。
5、隐马尔科夫链的解法（*）
（1）问题1 的解法：维特比算法
（2）问题2 的解法1：遍历算法
（3）问题2 的解法2：向前算法
（4）问题2 的解法3：后向算法
（5）问题3 的解法：Baum-Welch 算法
三、马尔可夫决策过程
1、马尔可夫奖赏过程(MRP)
〈S,P,R,γ〉是马尔可夫奖赏过程是指S为有限状态集合，P为状态转移矩阵, R：S⟶ℝ为奖赏函数Rs=?[Rt+1|St=s]，γ是折扣率
（1）MRP的价值函数
Rt定义为从状态st−1到达状态stst所得到的奖励，那么时刻0所能得到的回报可以写为：
t时刻在某一状态下的回报可以如下式子表示：
从某一状态到达另一状态是根据一定的概率，真实的Gt的可能有很多种，定义在某一状态下的价值函数：，其中St表示在t时刻的状态。
（2）Bellman方程
这个公式就是Bellman方程的基本形态，得到线性方程组：，可以求得每个状态的价值。
2、马尔可夫决策过程（MDP）（*）
马尔可夫决策过程由五个关键元素{S,A,P,R,γ}组成，其中：
S代表状态集合，A代表动作集合，P是三维概率矩阵：，R是回报函数，R:S×A→ℝ，有时R与A无关，R:S→ℝ：γ表示学习随着时间推移的折扣率
这里有确定的概率矩阵，所以也就给出了状态转移的模型，所以这里的MDP是基于模型的（Model-based），很多时候概率是不确定的，这就是不基于模型的（Model-free）。
（1）马尔可夫决策过程
状态s0在动作a0作用下根据概率分布到s1，再执行动作a1⋯，得到的回报如下 ：为了方便解释，把rt定义为从状态st−1执行行为at−1根据一定概率到达状态st所得到的奖励：
（2）策略
策略是指在各个特定的状态下执行不同动作的概率分布，给定一个MDP：，一个策略：π，
那么是一个MP，是一个MRP，其中：
（3）MDP的价值函数
给定一个MDP和一个策略π，因为是一个MRP，所以可以求出这个MRP的价值函数：
（4）动作价值函数
考虑某个状态下不同动作的价值，得：
（5）价值函数和动作价值函数的关系
所以在给定的策略下可以求出价值函数和动作价值函数
（6）最优价值函数和最优动作价值函数
定义最优价值函数v∗:S⟶ℝ，
定义最优动作价值函数q∗:S⟶ℝ，
对于任意一个MDP：
存在一个最优策略π∗使得对于∀π，π∗≥π所有的最优策略对应的价值函数就是最优价值函数：所有的最优策略对应的动作价值函数就是最优动作价值函数：
根据这个定理，可以得到Bellman最优方程：
（7）策略迭代（Policy Iteration）
Policy Iteration的目的是通过迭代计算value function 价值函数的方式来使policy收敛到最优。
Policy Iteration本质上就是直接使用Bellman方程而得到的：
Policy Iteration一般分为两步:
策略评估 Policy Evaluation： 更新vπv策略改进 Policy Improvement： π′=greedy(vπ)
直至收敛到π∗
考虑一个决定性的策略，a=π(s)既π(a|s)=1可以通过贪婪的方法改进策略：
如果改进结束，那么，满足Bellman最优方程，因此得到了最优策略π∗
（8）值迭代(Value Iteration)
根据Bellman最优方程，得到，有以下迭代公式 ：
参考文章：
/bitcarmanlee/article/details/82819860
/zxm1306192988/article/details/78595933
/greent/article/details/53995974
