马尔可夫模型（MC, HMM, POMDP, MOMDP）

大家应该还记得马尔科夫链(Markov Chain)，了解机器学习的也都知道隐马尔可夫模型(Hidden Markov Model，HMM)。它们具有的一个共同性质就是马尔可夫性(无后效性)，也就是指系统的下个状态只与当前状态信息有关，而与更早之前的状态无关。

马尔可夫决策过程(Markov Decision Process, MDP)也具有马尔可夫性，与上面不同的是MDP考虑了动作，即系统下个状态不仅和当前的状态有关，也和当前采取的动作有关。还是举下棋的例子，当我们在某个局面（状态s）走了一步(动作a)，这时对手的选择（导致下个状态s’）我们是不能确定的，但是他的选择只和s和a有关，而不用考虑更早之前的状态和动作，即s’是根据s和a随机生成的。

隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。 是在被建模的系统被认为是一个马尔可夫过程与未观测到的（隐藏的）的状态的统计马尔可夫模型。

下面用一个简单的例子来阐述： 假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（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）。在我们这个例子里，D6的下一个状态是D4，D6，D8的概率都是1/3。D4，D8的下一个状态是D4，D6，D8的转换概率也都一样是1/3。这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。这样就是一个新的HMM。

同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability）。就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。 图中两条链分别是隐含状态链和可见状态链 其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。这些算法我会在下面详细讲。

说两句废话，答主认为呢，要了解一个算法，要做到以下两点：会其意，知其形。答主回答的，其实主要是第一点。但是这一点呢，恰恰是最重要，而且很多书上不会讲的。正如你在追一个姑娘，姑娘对你说“你什么都没做错！”你要是只看姑娘的表达形式呢，认为自己什么都没做错，显然就理解错了。你要理会姑娘的意思，“你赶紧给我道歉！”这样当你看到对应的表达形式呢，赶紧认错，跪地求饶就对了。数学也是一样，你要是不理解意思，光看公式，往往一头雾水。不过呢，数学的表达顶多也就是晦涩了点，姑娘的表达呢，有的时候就完全和本意相反。所以答主一直认为理解姑娘比理解数学难多了。

Reference: https://www.cnblogs.com/skyme/p/4651331.html

POMDP是MDP的泛化。在POMDP模型中，系统的动力学仍然是由MDP描述的，但是系统并不能直接观测到当前的状态，就是系统不确定现在处于哪个状态。所以，系统需要通过a set of observations ,observation probilities and underlying MDP得到一个probability distribution over the set of possible states。

An exact solution to a POMDP yields the optimal action for each possible belief over the world states.

(这里有个疑问：既然在POMDP规划框架中已经没有state了，为什么在定义时还要有transition function?)

在每个时间周期，系统处于状态 s s s，执行动作 a a a，以 T ( s ′ ∣ s , a ) T(s' | s, a) T(s′∣s,a)的概率转换到状态 s ′ s' s′， 同时，以 O ( o ∣ s ′ , a ) O(o | s', a) O(o∣s′,a)的概率观测到一个observation o ∈ Ω o \in \Omega o∈Ω，最后，得到一个reward R ( s , a ) R(s, a) R(s,a)。重复这个过程。

规划的目的是得到最大化 E [ ∑ t = 0 ∞ γ t r ( t ) ] E[\sum_{t=0}^{\infty} \gamma^{t}r(t)] E[∑t=0∞​γtr(t)]

因为系统不能直接观测到state，the agent must make decisions under uncertainty of the true environment state。但是，通过和环境交互并且不断得到observations，the agent may update its belief in the true state by updating the probility distribution of the current state.

A consequence of this property is that the optimal behavior may often include (information gathering) actions that are taken purely because they improve the agent’s estimate of the current state, thereby allowing it to make better decisions in the future.

在执行完动作，得到观测之后，需要更新its belief in the state the environment may (or not) be in。由于马尔可夫性，maintaining a belief over the states solely requires knowledge of the previous belief state, the action taken, and the current observation，i.e. b ′ = τ ( b , a , o ) b' = \tau (b, a, o) b′=τ(b,a,o)。

下面就介绍一下belief space的更新过程。(belief space就是状态的后验分布空间，belief的更新就是贝叶斯滤波。)

在状态 s ′ s' s′时，系统以 O ( o ∣ s ′ , a ) O(o | s', a) O(o∣s′,a)的概率观测到 o ∈ Ω o \in \Omega o∈Ω, b b b为probability distribution over the state space. b ( s ) b(s) b(s)表示the probability that the environment is in state s s s. Given b ( s ) b(s) b(s), then after taking action a a a, and observing o o o, b ′ ( s ′ ) = b'(s') = b′(s′)=

Reference: wiki