马尔科夫决策过程（MDP）五大元素
什么是马尔科夫决策过程（Markove Decision Progress, MDP）？
生活中无时无刻不在做决定。假如以“时间 t t t”为横坐标轴，每个离散时刻的状态为随机变量 X t X_t Xt（ X t X_t Xt服从某个分布，离散的或连续）,存在一个动作集合 Φ \Phi Φ，同时维持一个奖励或者损失函数 C C C，以及一个状态转移概率 P P P。 那么通俗一点，MDP过程就可以定义为，在时间序列上，以上述五元素为已知条件，根据某种策略 π ∈ Π \pi\in\Pi π∈Π，得到一条使得目标函数 F ( C ) F(C) F(C) 的决策序列。这个定义不是严谨的，但是容易理解。
举个例子：假如我们以我们一天的生活为时间轴，1个小时为一个坐标点，以饥饿程度为状态，状态空间为：(特别饿，比较饿，刚好，满足，撑了)，以“进食和“不进食”为动作集合，以”过一个钟头就饿一成“为损失函数，状态转移方程为：撑了还吃的概率为0（那么不吃的概率就为1），满足还吃的概率为0.1，刚好还吃的概率为0.3，比较饿才吃的概率为0.6，饿极了再吃的概率为0.9（假设那0.1是饭撒了或者没钱了-_-）。那么给定一个初始状态，比如说：刚好，饥饿程度随时间增加，那么一个小时做一次决策，决定进食还是不进食，这样一天下来，我们所经历的状态和所做的决定就构成了一条MDP采样。
MDP五大元素
上述的五元素就是MDP问题的五个元素：
- 决策周期 T T T.
- 系统状态 S S S.
- 动作集合 A A A.
- 转移概率 P P P.
- 奖惩函数 C C C.
其中，根据 T T T的长度有限(finite)和无限(infinite)可以分为，有限决策过程(finite horizon problem)和无限决策过程(infinite horizon problem)；根据 T T T的离散还是连续又分为，离散决策问题(discrete MDP problem)和连续决策问题(consecutive MDP problem)。
决策的发生点：
- 所有决策epoch（epoch是指决策周期中的一个完整的决策过程，比方说12个小时是一个决策周期，那么每个小时就是一个epoch，这样一条链中就有11个决策epoch，决策发生在epoch的开始）
- 队列系统中的随机事件的发生点，比方说只在事件到达时做决策
- 关键点决策，这个简单，比方说，指定在1,3,5等时间点做决策，其他时间点不决策
因此，提起MDP，不一定只是 每epochMDP。
系统状态 S S S和动作集合 A A A：
-
均可为任意有限集合
-
均可为任意可数无限集合
什么是可数无限集合呢？一般指这样的集合，集合中的元素能够与自然数产生一一映射，数量上无限，或者说该集合是全体自然数集合的一个子集映射。比方说， s e t = 2 , 4 , 6 , 8 , 10 , . . . ∞ set = {2,4,6,8,10,...\infty } set=2,4,6,8,10,...∞就是一个可数无限集合。
-
有限欧几里得空间的子集
这种一般是指状态空间为二维或者以上的情况
-
no-empty Borel subsets of complete ,separable metric spaces.
奖惩函数 C C C:
在当前状态
s
s
s下，动作
a
a
a带来的影响分为两部分，一部分是立马可以获得的，称为即时奖励(immediate reward)。另一部分随着时间的流逝，慢慢获得，称为长期奖励(long-term reward)。并且，该奖惩函数收到
(
S
,
A
)
(S,A)
(S,A)的影响，一般表示为:
r
t
(
s
,
a
)
r_{t}(s,a)
rt(s,a).奖惩一般可以是当前状态下作出该动作所消耗的能量、所花费的成本、所收获的赏金等等，需要映射到一个实际情景，没有同一的定义，随着问题的不同而不同。
E
[
r
t
(
s
,
a
)
]
=
∑
j
∈
S
r
t
(
j
∣
s
,
a
)
p
t
(
j
∣
s
,
a
)
E[r_t(s,a)] = \sum_{j \in S }r_t(j|s,a)p_t(j|s,a)
E[rt(s,a)]=j∈S∑rt(j∣s,a)pt(j∣s,a)
状态转移概率
P
P
P:
状态转移概率 P P P表示为系统在当前状态 s s s下，作出动作 a a a，进入下一状态的分布情况。表示为 p t ( ⋅ ∣ s , a ) p_t(·|s,a) pt(⋅∣s,a)，并且 ∑ j ∈ S p t ( j ∣ s , a ) = 1 \sum_{j \in S}p_t(j|s,a) = 1 ∑j∈Spt(j∣s,a)=1.
至此，收集五元素：
{
T
,
S
,
A
s
,
p
t
(
⋅
∣
s
,
a
)
,
r
t
(
s
,
a
)
}
\{T,S,A_s,p_t(·|s,a),r_t(s,a)\}
{T,S,As,pt(⋅∣s,a),rt(s,a)}
即可生成MDP所需的一切了。
什么是决策规则(Decision Rules,DR)
DR是指决策者自行定义的，针对相应的状态所对应的特殊动作，DR可以是确定的，也就是说给定一个特殊状态，有一个明确的对应动作；DR也可以是随机的，也就是说给定一个特殊状态，有一个动作分布。在MDP中，我们所关心的DR是无后效性的，也就是说DR(s)只与当前状态有关。数学表达为： d t : S − > A s d_t: S->A_s dt:S−>As.
根据对history的依赖程度，可以对DR进行分类，分别是
- history dependent and randomized(HR),
- history dependent and deterministrc(HD),
- Markovian and randomized(MR),
- Markovian and deterministic(MD).
期望及时奖赏
E
[
r
t
(
s
,
d
t
(
s
)
)
]
=
∑
a
∈
A
s
r
t
(
s
,
a
)
q
d
t
(
s
)
(
a
)
E[r_t(s,d_t(s))] = \sum_{a \in A_s}r_t(s,a)q_{d_{t(s)}}(a)
E[rt(s,dt(s))]=a∈As∑rt(s,a)qdt(s)(a)
期望转移概率
p
t
(
j
∣
s
,
d
t
(
s
)
)
=
∑
a
∈
A
s
p
t
(
j
∣
s
,
a
)
q
d
t
(
s
)
(
a
)
p_t(j|s,d_t(s)) = \sum_{a \in A_s}p_t(j|s,a)q_{d_t(s)}(a)
pt(j∣s,dt(s))=a∈As∑pt(j∣s,a)qdt(s)(a)
什么是策略
It provides the decision maker with a prescription for action selection under any possible
future system state or history.
如果我们说DR是针对某一个状态给定的特殊动作，那么策略就是针对任意状态，都可以给定相应的动作。策略作用于整条链，与DR的关系为 π = ( d 1 , d 2 , d 3 , . . . d N − 1 ) \pi = (d_1,d_2,d_3,...d_{N-1}) π=(d1,d2,d3,...dN−1). 当 d t = d d_t = d dt=d的时候，也就是说对于任意 t t t,DR是确定的，我们称这个策略是静态的。相反，对于任意 t t t, DR是不确定的，也就是说针对不同epoch t,对应了不同的DR， 此时，我们称为该策略是动态的。
大白话其实就是，策略是一系列状态到动作之间的概率映射，如果该映射针对所有的t有固定的映射关系，那么就是静态的（即与t无关，不受t影响）。如果针对所有的t没有固定的映射关系，而是针对不同的t有不同的映射关系，那么就是动态的（受t的影响）。
至此，MDP所需要的基本条件就介绍完了。