一、相关概念

二、马尔科夫奖励过程

1.如何描述

用一个四元组来描述 <S,P,R,γ>

S
有限的状态集合
P
状态转移矩阵
R（Reward奖励）
离开状态 s 能够获得的立即奖励
γ
衰减因子：体现了未来的奖励在当前时刻的价值比例
γ接近 0 ：注重短期回报
γ接近 1 ：表明偏重考虑长远利益

2.举例说明

状态转移序列

立即奖励R（Reward）

当学生处于 Class1 状态时，若他选择参加 Class2 获得的 Reward 是 -2；若他选择去刷 Facebook 获得的 Reward 是 -2。即他从 Class1 状态离开就可获得立即奖励，这个立即奖励和他去哪没关系。

3.引入回报（Return）——针对一个片段 Episode

定义：收获 Gt 为在一个马尔科夫链上从 t 时刻开始往后所有的奖励的有衰减的收益总和。

回报、值函数的计算

从 Class1 状态到终止状态（Sleep），我们观测到了 4 条状态转移序列，还有很多其他的可能序列，但可能我们没有观测到。下面选取两条状态转移序列计算它们的回报值（从状态 Class1 开始，γ = 0.5）。

C1 C2 C3 Pass Sleep

G1 = 从 C1 离开的立即奖励 + γ × 从 C2 离开的立即奖励 + γ² × 从 C3 离开的立即奖励 + γ³ × 从 Pass 离开的立即奖励
= -2 + 1/2 × (-2) + 1/4 × (-2) + 1/8 × (+10) = -2.25

C1 FB FB C1 C2 Sleep

G1 = 从 C1 离开的立即奖励 + γ × 从 FB 离开的立即奖励 + γ² × 从 FB 离开的立即奖励 + γ³ × 从 C1 离开的立即奖励 + γ4 × 从 C2 离开的立即奖励 
= -2 + 1/2 × (-1) + 1/4 × (-1) + 1/8 × (-2) + 1/16 ×(-2) = -3.125

C1 C2 C3 Pub C2 C3 Pass Sleep

G1 = 从 C1 离开的立即奖励 + γ × 从 C2 离开的立即奖励 + γ² × 从 C3 离开的立即奖励 + γ³ × 从 Pub 离开的立即奖励 + γ4 × 从 C2 离开的立即奖励 + γ5 × 从 C3 离开的立即奖励 + γ6 × 从 Pass 离开的立即奖励 
= -2 + 1/2 × (-2) + 1/4 × (-2) + 1/8 × (1) + 1/16 ×(-2) + 1/32 ×(-2)+ 1/64 ×(10)= -3.41

C1 FB FB C1 C2 C3 Pub C1...

略

回报值是针对一次片段的结果，存在很大的样本偏差。Gt 是从 t 时刻的状态到终止状态的一条状态转移序列的回报值，但从 t 时刻的状态到终止状态可能有多条路径，就如上述状态转移图所示（而且可能还有很多序列没有观测到）。故要想精确的计算出 Gt 是不可能的，因为无法穷举所有序列。

4.引入值函数（Value function）——针对一个状态

1）目的

上面说 Gt 有多条路径，不好算，引入值函数就是为了解决这个问题。值函数是一个数值包含了多条路径。

假设你已经算出来上面的各个状态下的值函数，那么对于强化学习而言，假设是找到一条最优路径，起点状态是 Class1 ，那么很明显最优状态链是class1->class2->class3->pass->sleep，也就是说这条路径的累计回报最大，也就是说值函数求出来了，其实强化学习问题就解决了，对应的就是后续的值迭代法、Q-learning等思路了。

2）定义

马尔科夫奖励过程中某一状态的价值函数为从该状态开始的马尔科夫链回报的期望。

3）举例说明

对于上述状态转移图如果仅仅观测到以上 4 条序列，那么在状态 Class1 处的学生的值函数就是上述 4 个值除以 4 即可。

v(Class1) = ( (-2.25) + (-3.125) + (-3.41) + (-3.21) )  ÷ 4 =  2.996

5.引入贝尔曼方程（Bellman Equation）

1）作用

状态值函数的引入解决了 Return Gt 路径有很多条，不容易优化的问题，将其转化为期望编程固定标量了。但，状态值函数也不好算，因为在计算某个状态时候需要使用到将来所有状态的 Gt，这明显是不科学的。引入贝尔曼方程的目的是使状态值函数容易求解。

2）定义

贝尔曼方程的矩阵形式

3）举例说明

计算状态 s 的值函数方法 = 该状态的立即奖励 + 遍历该状态的各个后继状态，对于每一个后继状态： γ × 状态转移概率 × 后继状态的值函数求和。

此处取 γ=1

4.3= -2 + ( 1 × 0.6 × v(pass)  + 1 × 0.4 × v(pub) ) = -2 +( 1 × 0.6 × 10  + 1 × 0.4 × 0.8 )

Q：可能还有一些童鞋会问，算该状态的 value function 的时候，其它的状态的value function是怎么知道的呢？
A：比如算 4.3 的时候，我们如何知道它后继状态的value funciton为 0.8 ，10。其实这些值一开始可以任意初始化，后面可以学习更新，就类似于神经网络的权值参数，一开始任意初始化，后面通过loss反向更新一样。【？？还不太理解】