RL-Note(2)-马尔可夫决策过程
Published:
马尔可夫过程
马尔可夫性质
在随机过程中，马尔可夫性质（Markov property）是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。以离散随机过程为例，假设随机变量 $X_0,X_1,\cdots,X_T$构成一个随机过程。这些随机变量的所有可能取值的集合被称为状态空间（state space）。如果 $X_{t+1}$ 对于过去状态的条件概率分布仅是 $X_t$ 的一个函数，则 \(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)\) 其中，$X_{0:t}$ 表示变量集合 $X_{0}, X_{1}, \cdots, X_{t}$，$x_{0: t}$ 为在状态空间中的状态序列 $x_{0}, x_{1}, \cdots, x_{t}$。马尔可夫性质也可以描述为给定当前状态时，将来的状态与过去状态是条件独立的。如果某一个过程满足马尔可夫性质，那么未来的转移与过去的是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。
马尔可夫链
马尔可夫过程是一组具有马尔可夫性质的随机变量序列 $s_1,\cdots,s_t$，其中下一个时刻的状态$s_{t+1}$只取决于当前状态 $s_t$。我们设状态的历史为 $h_{t} = \left[s_{1}, s_{2}, s_{3}, \dots, s_{t} \right]$（$h_t$ 包含了之前的所有状态），则马尔可夫过程满足条件：
\[p\left(s_{t+1} \mid s_{t}\right) =p\left(s_{t+1} \mid h_{t}\right)\]从当前 $s_t$ 转移到 $s_{t+1}$，它是直接就等于它之前所有的状态转移到 $s_{t+1}$。 离散时间的马尔可夫过程也称为马尔可夫链（Markov chain）。马尔可夫链是最简单的马尔可夫过程，其状态是有限的。
马尔可夫奖励过程（Markov reward process, MRP）
马尔可夫奖励过程实际上是马尔可夫链加上奖励函数 在[[RL-Note(1)- RL基础]]我们定义回报return为从当前状态到终止状态的累计奖励，加入折扣因子，衡量随着时间步的奖励折损。 \(G_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k} = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots\) 有了return，就可以定义状态的价值了，就是状态价值函数（state-value function）。对于马尔可夫奖励过程，状态价值函数被定义成回报的期望，即
\[\begin{aligned} V^{t}(s) &=\mathbb{E}\left[G_{t} \mid s_{t}=s\right] \\ &=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\ldots+\gamma^{T-t-1} r_{T} \mid s_{t}=s\right] \end{aligned}\]其中，$G_t$ 是之前定义的折扣回报（discounted return）。我们对$G_t$取了一个期望，期望就是从这个状态开始，我们可能获得多大的价值。所以期望也可以看成未来可能获得奖励的当前价值的表现，就是当我们进入某一个状态后，我们现在有多大的价值。
马尔可夫决策过程（Markov decision process，MDP）
马尔可夫决策过程是描述随机动态系统的一般框架，其并不仅仅局限于强化学习。马尔可夫决策过程的涉及以下关键要素：
- 集合:
- 状态空间:状态的结合，记为$\mathcal{S}$。
- 行动空间:行动的集合，记为$\mathcal{A}(s)$，其中$s \in \mathcal{S}$。
- 奖励集合:与每个状态-行动对$(s,a)$相关联的奖励集合，用$\mathcal{R}(s，a)$表示。
- 模型:
- 状态转移概率: 在状态$s$采取行动$a$时，智能体转变为状态$s’$的概率为$p(s’ \mid s,a)$。对于任意$(s,a)$有$\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}\mid s,a)=1$。
- 奖励概率: 在状态$s$下，当采取行动$a$时，智能体获得奖励$r$的概率为$p(r \mid s,a)$。对于任意$(s,a)$有$\sum_{r\in\mathcal{R}(s,a)}p(r \mid s,a)=1$
策略: 在状态$s$，智能体采取行动$a$的概率为$\pi(a \mid s).$对于任意$s\in\mathcal{S}$有$\sum_{a\in\mathcal{A}(s)}p(a\mid s)=1$。
- 马尔可夫性质: 马尔可夫性质 (Markov property)是指随机过程的无记忆性质。在数学上表示为：
其中$t$代表当前时刻，$t+1$代表下一个时刻。式子(1.4)表明下一个状态和奖励仅依赖于当前时刻的状态和行动，而与之前的状态和行动无关。马尔可夫特性对于推导MDP的贝尔曼方程非常重要，在下章我们会详细讨论。
在马尔科夫决策过程中，$p(s’ \mid s,a)$和$p(r \mid s,a)$被称为模型 (model)或动态 (dynamics)。模型可以是平稳的 (stationary)，也可以是非平稳的 (nonstationary)：平稳模型不会随时间变化；而非平稳模型会随时间变化。例如，在网格世界的例子中，如果一个禁区时而出现时而消失，那么所对应的状态转移或者奖励就会随时间而变化，此时系统是非平稳的，本书只考虑平稳的情况。
“马尔可夫决策过程”和“马尔可夫过程”有什么区别呢？答案是：一旦在马尔可夫决策过程中的策略被确定下来了，马尔可夫决策过程就退化成了一个马尔可夫过程
强化学习涉及智能体与环境的交互。智能体之外的一切都被视为环境。第一，智能体可以理解并感知当前的状态。第二，智能体可以了解在什么状态应该采取什么行动。第三，智能体能够执行策略所指示的动作，从而改变状态获得奖励。