强化学习(二）：马尔可夫决策过程MDP【上篇】

我们用状态 $S_{t}$ 来切分历史数据， $H_{1:t}\, \rightarrow \, S_{t}\, \rightarrow \, H_{t+1:\infty }$ 状态 $S_{t}$ 从history中捕获了所有县官的信息。若已知状态 $S_{t}$ ，则 $H_{1:t}\,$ 就可以被丢掉。状态 $S_{t}$ 是 $H_{t+1:\infty }$ 的充分统计量。

状态转移矩阵

一个马尔可夫状态从当前的s转到下一状态 $s^{{}'}$ 的概率定义为状态转移概率：

所有的当前状态s转移到所有后继状态的概率构成一个矩阵 ——状态转移矩阵P：

由于当前状态必然转移到下一个可选的状态中的某一个，所以P矩阵的每一行的和都为1.

马尔可夫过程

是一个无记忆性的随机过程，也就是随机状态序列 $S_{1}\, ,\, S_{2}\, ,...$ 具有马尔可夫性。

马氏链MDP：以学生上课的状态为例

学生们上课的状态，在上课堂【Class1】时，

有50%的人会选择继续听下一节课，另外50%的人（可能觉得课程无聊）选择去刷Facebook，
刷Facebook的人：有90%的继续刷Facebook，还有10%的人会回到课堂1，
在课堂2处，有20%的人选择睡觉，80%的人选择去听课堂3，
在课堂3处，有60%的人通过考试，有40%的人选择去酒吧喝两杯；
去到酒吧的人，有20%的人回到课堂1，40%的人回到课堂2，40%的人回到课堂3，
通过考试的人，全都去睡觉。

假设状态S1 = C1,用FB表示Facebook，那么我们从上述的马氏链中采样序列【episodes】，

，可以得到以下几种：【状态有C1、 C2、 C3、 Pass 、Pub 、FB 、Sleep】

C1 C2 C3 Pass Sleep
C1 FB FB C1 C2 Sleep
C1 C2 C3 Pub C2 C3 Pass Sleep
C1 FB FB C1 C2 C3 Pub C1 FB FB FB C1 C2 C3 Pub C2 Sleep

Markov Reward Process

马尔可夫奖励过程是具有values的马氏链，可以定义为一个四元组 $< \, S\, ,P,\, R, \,\gamma >$ ,其中R是奖励函数， $\gamma$ 是折扣因子。

与MDP的不同在于增加了从一个状态转到下一个状态的奖励的期望。

MRP：以学生上课的状态为例

回报Return

大多数马尔可夫reward and decision过程都要乘以折扣因子 $\gamma$ 。为什么？

数学上的计算简便
避免了周期性马氏过程的 inﬁnite returns 问题。
无法充分地表示未来的不确定性。
如果奖励是关于金融方面的，那么眼前的回报会比延迟得到的回报赚得更多的利息。
人类和动物的天性都是偏好眼前利益。
如果所有的序列是有限个时间步，有时候也使用不带折扣因子的MRP (i.e. $\gamma$ = 1),
每一个时间步都要乘以 $\gamma$ ，由此可知在隔k+1个时间步后，再接受到奖励的R值变为 $\gamma ^{k}R$ . ,说明了比起延迟得到的奖励，这个值更看重眼前的奖励。

因为未来的奖励要在未来才能兑现，在当前状态下就要打个折扣。比如最近的知乎话题（马云这类大佬的经验与知识和一千万你选哪个）的高赞回答（马云的经验知识，可能就是告诉你要选这一千万），为什么呀？因为未来具有很大的不确定性，就像鸡汤说的：明天和意外不知哪一个先来。所以要给当下的奖励以更高的权重，对于长远未来的奖励要打个折扣。

值函数 value function

值函数v(s) 给出了MRP中从状态s开始的 expected return【回报的期望】。

举例：学生上课的MRP Returns

从学生的MRP中，对 returns 采样。从S1 = C1开始， $\gamma =\frac{1}{2}$ 有

举例：学生上课的MRP的状态-值函数

MRP 的Bellman Equation【贝尔曼方程】

值函数可以分解为两个部分：immediate reward $R_{t+1}$ ；下一状态的值函数乘以 $\gamma$

贝尔曼方程的矩阵表示

是一个线性方程

其中v是一个列向量，它表示每一个状态的值函数

贝尔曼方程的求解

由于线性方程可直接求解：

对于求解有n个状态的贝尔曼方程，的计算复杂度为，因此只有n很小时才直接求解，当n很大时用迭代方法求解，比如：

动态规划、 Monte-Carlo估计、时序差分学习Temporal-Diﬀerence learning】