马尔可夫决策过程(零)--问题介绍

马尔可夫决策被经常用在序列决策的场景中，例如强化学习中说到的迷宫问题，以及翻阅本站点曾经讲到的MM（map match）路网匹配问题等等，都是这类理论一个比较好的应用，目的是在一个决策空间内，做一系列的决策从而保证最后的结果是最优的。

现在我们要开始学习马尔可夫决策过程的相关理论和知识啦，这部分知识其实是十分复杂、枯燥、无味的，但是作为强化学习的最基础的理论，又是逃不掉的一部分，所以要尝试硬着头皮看看这一部分的学习。注定这将是一个系列的学习，所以本篇博客就介绍一个背景已经常用的表示方式就好啦。

决策时刻周期

首先要解决的一个问题就是决策周期，所谓决策周期就是，我们在什么时间点做决策，或者隔多长时间做决策。从这个角度我们可以首先拆分两种决策时刻，一种是有限阶段决策时刻 $T={0,1,2,..,N}$ , 另一类是无限阶段决策 $T={0,1,2,..}$ 。

状态集合和行动集合

在马尔可夫决策中经常提到的就是这两个集合，状态集合是用来描述智能体所处的上下文，动作集合简单说就是面对当前状态能够使用的动作类别，这里包括咱们提到迷宫问题中上\下\左\右就是一个动作集合，我们一般用符号 $A(i)$ 表示状态i的可用动作集合，这里的状态是 $i \in S$ ,i表示单个状态，而S表示的状态集合。

转移概率和报酬

对于任意一个决策时刻，在状态i采取的行动a后会产生两个结果

决策体获得的报酬r(i,a)
下个决策时刻系统所处的状态由概率分布p(*|i,a)决定

$r(i,a)$ 表示当状态i采用动作a后获得的报酬，当这个报酬为正时表示收入，当这个报酬为负的时候表示费用，这个值在强化学习中一般是一个期望值。实际上这个报酬可以包括，到下一个时刻的一次性收入以及到下一个阶段的累积收入还有转移到下个状态的随机收入等等，是不是比较复杂。那我们来量化一下。

r(i,a)=\sum_{j \in S} r(i,a,j) p(j|i,a)

$p(j|i,a)$ 表示当处于状态i的状态下，采用动作a的时候，转移到状态j的概率，称为转移概率函数,既然是概率吗，当然是满足 $\sum_{j \in S}p(j|i,a)=1$ . 讲到这里我们要把马尔可夫决策的五元组郑重的给出来啦。

(T, S, A(i), p(*|i, a), r(i,a))

上面这个五元组就是出名的马氏决策过程，这里隐身的条件就是转移概率和报酬仅仅依赖当前状态和选取的行动，而不依赖历史数据。

对于马氏常用的数据就是一条过程轨迹。

h_{t}={i_{0}, a_{0},i_{1}, a_{1}, ..., i_{t}}

策略类

所谓策略是描述一个决策时刻系统在各个不同的状态上选择动作的规则，马尔可夫决策的体系下有很多种决策策略，下面我们就一一讲解一下。

马氏策略类

一个决策函数序列 $\pi=(f_{0},f_{1},..)$ , $f \in F$ ,就称为马氏策略，其中 $f_{t}$ 是决策时刻t的决策函数，不依赖于以前的系统历史，全体马氏策略所成的集合$ \Pi_{m}^{d}$称为马氏策略类。

随机马氏策略类

一个马氏决策规则序列 $\pi=(\pi_{0},\pi_{1},\pi_{2}...)$ 称为随机马氏策略，其中 $\pi_{t}$ 是决策时刻t的决策规则且不依赖时刻t以前的系统，全体随机马氏策略所成的集合称为随机马氏策略类，用$ \Pi_{m}$表示。

决定性策略类

一个决策规则序列 $\pi=(\pi_{0},\pi_{1},\pi_{2}...)$ ，如果t时刻的决策规则 $\pi_{t}$ 不仅是随机的，而且依赖于系统的历史 $h_{t}$ ,这是最一般的策略，全体一般策略所成的集合称为策略空间，用 $\Pi$ 表示，如果对一切t， $\pi_{t}$ 是依赖系统历史 $h_{t}$ 的退化分布，那么 $\pi$ 称为决定性策略，全体决定性策略称为决定性策略类。 $\Pi^{d}$ 。