马尔科夫奖励过程（Markov Reword Process，MRP）

我更愿意叫它马尔科夫回馈过程。这里，马尔科夫回馈过程通过一个四元组 < S , P , R , γ > <S,P,R,\gamma> <S,P,R,γ>来表示。

定义：
\quad 马尔科夫回馈过程为 < S , P , R , γ > <S,P,R,\gamma> <S,P,R,γ>
\quad 其中：
\quad\quad\quad S S S为有限状态集， S = { s 1 , s 2 , ⋯   , s n } S=\{s_1,s_2,\cdots,s_n\} S={s1​,s2​,⋯,sn​}
\quad\quad\quad P P P为状态转移概率矩阵， p s s ′ = P [ S t + 1 = s ′ ∣ S t = s ] p_{ss'}=P[S_{t+1}=s'|S_{t}=s] pss′​=P[St+1​=s′∣St​=s]
\quad\quad\quad R R R为回馈方程， R s = E [ R t + 1 ∣ S t = s ] R_s=E[R_{t+1}|S_t=s] Rs​=E[Rt+1​∣St​=s]
\quad\quad\quad γ \gamma γ为折扣因子， γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ∈[0,1]

这里新增了几个概念/字母表示，需要解释清楚。

• 为什么多了 t t t和 t + 1 t+1 t+1？这里用 t t t表示当前时刻，用 t + 1 t+1 t+1表示下一时刻，比如 S t S_t St​表示当前时刻的状态， S t + 1 = s ′ S_{t+1}=s' St+1​=s′表示下一时刻的状态为 s ′ s' s′
• 回馈方程是什么？用文字翻译翻译回馈方程的定义为，在当前状态为s的条件下，跳出当前状态的期望回馈（或者奖励）是多少。所以，这里面 R t + 1 R_{t+1} Rt+1​的下标为 t + 1 t+1 t+1，表示跳出当前状态（即将进入下一时刻）
• 折扣因子表示什么？这里表示回馈的“时效”性，或者说影响能力。当折扣因子为1时，表示当前 t t t时刻的回馈值会永久地、不打折扣地影响到之前的所有时刻。而当折扣因子 0 < γ < 1 0<\gamma<1 0<γ<1时， t + k t+k t+k时刻的回馈对 t t t时刻的影响就只剩 γ k R t \gamma^kR_t γkRt​了

回馈函数和折扣因子的引入使得马尔科夫回馈过程更符合我们人类的行为模式。当我们从一种状态（兴奋、或者抑郁）跳出来时，或多或少地会获得一些奖励（比如失落感或满足感)。并且，我们往往更注重“眼前”的奖励，而对那些遥遥无期、画大饼式的奖励不感兴趣，这就是折扣因子存在的原因。此外，引入折扣因子的其他原因如下（引用自David Silver强化学习课程Lecture2）

• 数学上对奖励的打折处理很方便
• 避免在循环马尔科夫过程中的无限回馈（注： γ ∞ = 0 \gamma^\infin=0 γ∞=0，当 0 < γ < 1 0<\gamma<1 0<γ<1时)
• 遥远未来的不确定性不需要作为当前的考虑因素
• 如果回馈/奖励是经济性的（比如直接撒钱），那么即时回馈比远期回馈要更有吸引力（注：就是说画大饼对我没用）
• 人/动物的行为更偏向于获得较高的即时回馈
• 有些情况下也是会用到无折扣（ γ = 1 \gamma=1 γ=1）的

爱学习的马尔科夫蛙

举个栗子。我们上一讲的马尔科夫蛙它换了个马甲，不跳荷叶改看《兵法》了。

故事是这样的：最近它报了一门课，叫《如何不被本山忽悠》，这门课分三课，第一课叫《卖拐》，第二课叫《卖车》，第三课叫《功夫》。课上的好呢，可以直接通过，不用去考试；课上不好呢，得跟本山老师对戏，哪儿没演好就从哪儿开始重新上课。大致情况可以用下图表示：

马尔科夫蛙呢，可能在刚开始上《卖拐》的时候觉得没意思，就刷刷微博啥的；也可能觉得还挺不错，直接学《卖车》，而且资质过人直接领悟范伟境界，拿到终极成就“自学成才”；最有可能的是它上满三节课，然后跟本山对戏或者直接通过获取成就。

在上述过程中，马尔科夫蛙的状态转移概率 p p p以及跳出当前状态的即时回馈 r r r被标注在图上。我们不需要关心这些概率和回馈值怎么来的、为什么是那样一个数，因为在模型已知的马尔科夫过程中， S , P , R , γ S,P,R,\gamma S,P,R,γ就是给定的！（至于模型未知的情况，以后再做讨论，但至少你得先学会模型已知的情况不是？）

至此，马尔科夫回馈过程的概念就讲差不多了。但还有一个事儿没讲明白，为啥要引入马尔科夫回馈过程？没有回馈过程它不香么？
答案是：是的，它不香。因为有了回馈，我们才能衡量（或者说 评价）处于某一状态是好是坏，以便做出决策！

那么，如何衡量呢？

状态值函数（State-Value Function）

某一状态好坏，可以从跳出该状态后可能获得的所有回馈值之和来衡量。

定义： G t G_t Gt​是 t t t时刻起的总折扣奖励（total discounted reward），可表示为如下所示
G t = R t + 1 + R t + 2 + R t + 3 + ⋯ = ∑ k = 0 ∞ γ k R t + k + 1 G_t=R_{t+1}+R_{t+2}+R_{t+3}+\cdots=\sum_{k=0}^\infin\gamma^kR_{t+k+1} Gt​=Rt+1​+Rt+2​+Rt+3​+⋯=k=0∑∞​γkRt+k+1​

还是以马尔科夫蛙上课为例，假设它当前在上《卖拐》这堂课，那么它之后可能的马尔科夫序列为：

• 卖拐1：卖拐 ⇒ \Rarr ⇒卖车 ⇒ \Rarr ⇒功夫 ⇒ \Rarr ⇒通过 ⇒ \Rarr ⇒“自学成才”
• 卖拐2：卖拐 ⇒ \Rarr ⇒微博 ⇒ \Rarr ⇒微博 ⇒ \Rarr ⇒卖拐 ⇒ \Rarr ⇒卖车 ⇒ \Rarr ⇒“自学成才”
• 卖拐3：卖拐 ⇒ \Rarr ⇒卖车 ⇒ \Rarr ⇒功夫 ⇒ \Rarr ⇒和本山对戏 ⇒ \Rarr ⇒卖车 ⇒ \Rarr ⇒功夫 ⇒ \Rarr ⇒通过 ⇒ \Rarr ⇒“自学成才”

设折扣因子为0.5，那么对应的总折扣奖励为：
G 卖 拐 1 = − 2 − 2 ∗ 1 2 − 2 ∗ 1 4 + 10 ∗ 1 8 = − 2.25 G 卖 拐 2 = − 2 − 1 ∗ 1 2 − 1 ∗ 1 4 − 2 ∗ 1 8 − 2 ∗ 1 16 = − 3.125 G 卖 拐 3 = − 2 − 2 ∗ 1 2 − 2 ∗ 1 4 + 1 ∗ 1 8 − 2 ∗ 1 16 − 2 ∗ ∗ 1 32 + 10 ∗ ∗ 1 64 = − 3.41 G_{卖拐1}=-2-2*\frac{1}{2}-2*\frac{1}{4}+10*\frac{1}{8}=-2.25 \\ G_{卖拐2}=-2-1*\frac{1}{2}-1*\frac{1}{4}-2*\frac{1}{8}-2*\frac{1}{16}=-3.125 \\ G_{卖拐3}=-2-2*\frac{1}{2}-2*\frac{1}{4}+1*\frac{1}{8}-2*\frac{1}{16}-2**\frac{1}{32}+10**\frac{1}{64}=-3.41 G卖拐1​=−2−2∗21​−2∗41​+10∗81​=−2.25G卖拐2​=−2−1∗21​−1∗41​−2∗81​−2∗161​=−3.125G卖拐3​=−2−2∗21​−2∗41​+1∗81​−2∗161​−2∗∗321​+10∗∗641​=−3.41

可见，从同一起点开始，可以有不同的马尔科夫序列（上一节已经讲过），并且他们的 G G G值也可能不同，那这怎么衡量？

同一起点开始，形成的马尔科夫序列是随机的，其 G G G值也是随机的，但期望（所有可能 G G G值的平均值）是个定值！ 因此我们可以用 G G G值的期望来衡量处于某一状态 s s s下的好坏程度。

定义：MRP的状态值函数 v ( s ) v(s) v(s)为自 s s s状态开始的 期望 总折扣奖励，可用下式表示
v ( s ) = E [ G t ∣ S t = s ] v(s)=E[G_t|S_t=s] v(s)=E[Gt​∣St​=s]

至此，我们终于可以衡量（或者说评价）处于某一状态的好坏了。当然，好坏的衡量也是与 γ \gamma γ有关的。

仍以马尔科夫蛙为例， γ = 0 ， 0.9 ， 1 \gamma=0，0.9，1 γ=0，0.9，1的各状态值函数如下三图所示。



最后一个问题！
从s状态开始到结束为止，有无穷多种可能，那这期望怎么求？

这就需要大神登场——贝尔曼方程。

未完待续…