马尔可夫决策过程

智能体得到环境的状态后，它会采取动作，并把这个采取的动作返还给环境。环境得到智能体的动作后，它会进入下一个状态，把下一个状态传给智能体。

在强化学习中，智能体与环境就是这样进行交互的，这个交互过程可以通过马尔可夫决策过程来表示，所以马尔可夫决策过程是强化学习的基本框架。

• 马尔可夫过程（Markov process，MP）
• 马尔可夫奖励过程（Markov reward process，MRP）
• 马尔可夫决策过程中的策略评估（policy evaluation） ，就是当给定决策后，我们怎么去计算它的价值函数。
• 最后，我们会介绍马尔可夫决策过程的控制，具体有策略迭代（policy iteration） 和 价值迭代（value iteration） 两种算法。
• 在马尔可夫决策过程中，它的环境是全部可观测的。
• 但是很多时候环境里面有些量是不可观测的，但是这个部分观测的问题也可以转换成马尔可夫决策过程的问题。

1.马尔科夫过程

• 马尔可夫性质（Markov property） 是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。
• 以离散随机过程为例，假设随机变量 X0,X1,⋯ ,XTX_0,X_1,\cdots,X_TX0,X1,⋯,XT构成一个随机过程。这些随机变量的所有可能取值的集合被称为状态空间（state space）。如果 Xt+1X_{t+1}Xt+1 对于过去状态的条件概率分布仅是 XtX_tXt 的一个函数，则

p(Xt+1=xt+1∣X0:t=x0:t)=p(Xt+1=xt+1∣Xt=xt)p\left(X_{t+1}=x_{t+1} \mid X_{0:t}=x_{0: t}\right)=p\left(X_{t+1}=x_{t+1} \mid X_{t}=x_{t}\right)p(Xt+1=xt+1∣X0:t=x0:t)=p(Xt+1=xt+1∣Xt=xt)

• 其中，X∗0:tX *{0:t}X∗0:t 表示变量集合 X∗0,X∗1,⋯ ,X∗tX*{0}, X *{1}, \cdots, X*{t}X∗0,X∗1,⋯,X∗t，x∗0:tx *{0: t}x∗0:t 为在状态空间中的状态序列 x∗0,x∗1,⋯ ,x∗tx*{0}, x *{1}, \cdots, x*{t}x∗0,x∗1,⋯,x∗t。马尔可夫性质也可以描述为给定当前状态时，将来的状态与过去状态是条件独立的。
• 如果某一个过程满足马尔可夫性质，那么未来的转移与过去的是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

2.马尔科夫链

马尔可夫过程是一组具有马尔可夫性质的随机变量序列 s1,⋯ ,sts_1,\cdots,s_ts1,⋯,st，其中下一个时刻的状态s∗t+1s *{t+1}s∗t+1只取决于当前状态 sts_tst。我们设状态的历史为h*{t}=\left{s *{1}, s*{2}, s *{3}, \ldots, s*{t}\right}（hth_tht 包含了之前的所有状态），则马尔可夫过程满足条件：

p(st+1∣st)=p(st+1∣ht)(2.1)p\left(s_{t+1} \mid s_{t}\right) =p\left(s_{t+1} \mid h_{t}\right) \tag{2.1}p(st+1∣st)=p(st+1∣ht)(2.1)

从当前 sts_tst 转移到 s∗t+1s *{t+1}s∗t+1，它是直接就等于它之前所有的状态转移到 s∗t+1s*{t+1}s∗t+1。

离散时间的马尔可夫过程也称为马尔可夫链（Markov chain） 。马尔可夫链是最简单的马尔可夫过程，其状态是有限的。例如，图 2.2 里面有4个状态，这4个状态在 s1,s2,s3,s4s_1,s_2,s_3,s_4s1,s2,s3,s4 之间互相转移。比如从 s1s_1s1 开始，s1s_1s1 有 0.1 的概率继续存留在 s1s_1s1 状态，有 0.2 的概率转移到 s2s_2s2，有 0.7 的概率转移到 s4s_4s4 。如果 s4s_4s4 是我们的当前状态，它有 0.3 的概率转移到 s2s_2s2，有 0.2 的概率转移到 s3s_3s3，有 0.5 的概率留在当前状态。

3.马尔科夫奖励

马尔可夫奖励过程（Markov reward process, MRP） 是马尔可夫链加上奖励函数。在马尔可夫奖励过程中，状态转移矩阵和状态都与马尔可夫链一样，只是多了奖励函数（reward function） 。奖励函数 RRR 是一个期望，表示当我们到达某一个状态的时候，可以获得多大的奖励。这里另外定义了折扣因子 γ\gammaγ 。如果状态数是有限的，那么 RRR 可以是一个向量。

图 2.6 计算马尔可夫奖励过程价值的蒙特卡洛方法

图 2.7 计算马尔可夫奖励过程价值的动态规划算法

4.马尔科夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策（决策是指动作），其他的定义与马尔可夫奖励过程的是类似的。此外，状态转移也多了一个条件，变成了p(s∗t+1=s′∣s∗t=s,at=a)p\left(s *{t+1}=s^{\prime} \mid s*{t}=s,a_{t}=a\right)p(s∗t+1=s′∣s∗t=s,at=a)。未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作。马尔可夫决策过程满足条件：

对于奖励函数，它也多了一个当前的动作，变成了 R(s∗t=s,a∗t=a)=E[r∗t∣s∗t=s,at=a]R\left(s *{t}=s, a*{t}=a\right)=\mathbb{E}\left[r *{t} \mid s*{t}=s, a_{t}=a\right]R(s∗t=s,a∗t=a)=E[r∗t∣s∗t=s,at=a]。当前的状态以及采取的动作会决定智能体在当前可能得到的奖励多少。

2.3.1 马尔可夫决策过程中的策略