在介绍马尔可夫决策过程之前，我们先介绍下情节性任务和连续性任务以及马尔可夫性。
情节性任务 vs. 连续任务情节性任务（Episodic Tasks），所有的任务可以被可以分解成一系列情节，可以看作为有限步骤的任务。
连续任务（Continuing Tasks），所有的任务不能分解，可以看作为无限步骤任务。
马尔可夫性引用维基百科对马尔可夫性的定义：
马尔可夫性：当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。
用数学形式表示如下：
A state \(S_t\) is Markov if and only if
\[P[S_{t+1}|S_t] = P[S_{t+1}|S_1, ..., S_t]\]
马尔可夫过程即为具有马尔可夫性的过程，即过程的条件概率仅仅与系统的当前状态相关，而与它的过去历史或未来状态都是独立、不相关的。
马尔可夫奖赏过程马尔可夫奖赏过程（Markov Reward Process，MRP）是带有奖赏值的马尔可夫过程，其可以用一个四元组表示 \(<S, P, R, \gamma>\)。
\(S\) 为有限的状态集合；
\(P\) 为状态转移矩阵，\(P_{ss^{'}} = P[S_{t+1} = s^{'}|S_t = s]\)；
\(R\) 是奖赏函数；
\(\gamma\) 为折扣因子（discount factor），其中 \(\gamma \in [0, 1]\)
奖赏函数在 \(t\) 时刻的奖赏值 \(G_t\)：
\[G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1}\]
关于Return的计算为什么需要 \(\gamma\) 折扣系数。David Silver 给出了下面几条的解释：
数学表达的方便
避免陷入无限循环
远期利益具有一定的不确定性
在金融学上，立即的回报相对于延迟的汇报能够获得更多的利益
符合人类更看重眼前利益的特点
价值函数状态 \(s\) 的长期价值函数表示为：
\[v(s) = E[G_t | S_t = s] \]
\[ \begin{align} v(s) &= E[G_t|S_t=s]\\ &= E[R_{t+1} + \gamma R_{t+2} + ... | S_t = s]\\ &= E[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} ... ) | S_t = s]\\ &= E[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= E[R_{t+1} + \gamma v(s_{t+1}) | S_t = s] \end{align} \]
下图为MRP的 backup tree 示意图：