欢迎转载，作者：Ling，注明出处：强化学习教程: 02-MDP

 

几乎所有的强化学习问题都可以转化为马尔科夫决策过程，所以我们文主要介绍以下内容：

• 马尔科夫过程：Markov Processes
• 马尔科夫奖励过程：Markov Reward Processes
• 马尔科夫决策过程：Markov Decision Processes
• 马尔科夫的扩展问题

马尔科夫过程：Markov Processes

马尔科夫性质：

如果值考虑前一个状态，一般称为一阶马尔科夫过程，我们主要考虑的也是后一个状态仅由前一个状态决定

状态转移矩阵：

从s到s'的概率

所有状态构成矩阵：

每行和为1

马尔科夫过程：

定义：状态加状态矩阵

举例：

学生马尔科夫过程：

其中

S=(C1, C2, C3, Pub, Pass, Sleep, Facebook)

马尔科夫奖励过程：Markov Reward Processes

定义：

多了个奖励值R：每个状态都有个奖励值, 注意，根据上章我们的约定，在t时间步，环境给出的奖励值是 ， 表示在t时刻，状态为S，环境给出的奖励值，该奖励值一般不变。很多人会疑问，为啥t时候给出的不是 ,你可以这么想，环境给出的是下一个时间步的奖励，参考前章内容。

多了个折扣/衰减值γ：计算回报时会用到

举例：

就是每个状态加了个奖励值而已，该值由环境直接给出

回报：回报是用于计算Value的

回报是折扣奖励之和。

举例说明其具体含义：

假设t时间步在C2，给出的奖励是R_t+1，t+1时间步在C3，给出的奖励是R_t+2，t+2时间步在Pass，给出的奖励是R_t+3

Gt = C2的R (-2)  + γC3的R(-2) + γ2Pass的R(+10)，走多少步，由选择的样本而定

Value Function：

v(s)表示在s状态的价值。有样本的Gt期望决定。

举例

如果S1 = C1且γ=1/2

我们有四个样本：

对于C1 C2 C3 Pass Sleep这个序列样本的回报

G1=-2 + 1/2 * (-2) + 1/4*(-2) + 1/8*(+10) + 1/16*(0)

将四个样本G1求期望，比如求个平均值，就是v(c1)的值

这样的做法是根据样本+公式求V值

如果S1=C3且γ=0的情况：​

s1 = c3

G1 = -2 + 0*xxx… = -2

所有G1求均值就是v(c3) ，其他同理

如果S=C2且γ=0.9：

s1 = c2

对于样本 C2 C3 Pass

G1 = -2+ 0.9* 0.8 * -2 + 0.9*0.9 *0.6*10 = 1.42

然后将所有样本取平均得到0.9

这就是v(c3)的值

关于γ：

• 属于0-1，如果接近0，表示只看眼前，如果接近1，表示更有远见
• 用于衰减远处的值

为什么需要γ：

• 数学角度需要递减
• 避免马尔科夫中存在环，不递减，会一直围绕大值走
• 从金融角度看，近期回报也要大于远期

马尔科夫奖励过程的贝尔曼方程

推导：

分解：

v(s) = E[Rt+1 + γ*v(St+1)| St = s]

含义：

v(s)表示在s状态的价值，等于s状态的Reward Rs+1  加上 从s变成s'的转移概率乘以v(s'),在求所有可能情况的和，再乘上衰变值γ

举例：

假设γ是1：

其中v(c3) 计算公式为红色

v(c2) = -2 + 0.8*4.3+0.2*0=1.44

这种做法是根据下一步的V值求本步的V值

贝尔曼方程矩阵形式：

求逆计算：

这种做法也是通过公式直接求V值

但是，该公式只能用于很小的MRP求值，对于比较大的MRP需要通过：

• 动态规划(Dynamic programming)
• 蒙特卡洛方法(Monte-Carlo evaluation)
• 差分学习法(Temporal-Difference learning)

马尔科夫决策过程: Markov Decision Processes (MDP):

MDP与MRP不同点：

• 加入Action
• 加入Reward函数：它表示的不是一个状态的Reward，而是在一个状态，take了某个action的Reward

马尔科夫决策过程的Reward和马尔科夫奖励过程的Reward区别：

• 表示s状态的Reward，画在状态上
• 表示s状态，且之后agent会采取a动作的Reward，画在边上

举例：红色部分就是Action，并且R在边上

对比：

策略：Policy，

• 策略决定了Agent行为
• 是状态到action的映射或者说概率
• MDP仅考虑当前状态，不考虑历史状态
• 策略实际上是时间独立的，任何时间策略都是固定的

定义：

给定 MDP=<S, A, P,R, γ>和π

• 得到的状态序列s1,s2…是马尔科夫过程 <S, Pπ>
• 得到的状态和Reward序列S1,R1,S2,R2…是马尔科夫奖励过程<S, Pπ,Rπ,γ>
• 得到的状态，reward，action序列S1,R1,A1,S2,R2,A2…则是马尔科夫决策过程：

其中：

Value Function：有两种，一种是V值函数，一种是Q值函数

举例：

S1 = C1, A = Study

也就是说从C1走，第一个action选Study， 则第一个action不会是Facebook

C1 Study C2 Study C3 Study

G1 = -2 + 1*-2+1*1*(+10)=6

C1 Study C2 Sleep

G1 = -2 +1*(0)=-2

C1 Study C2 Study C3 pub

G1 = -2 + 1*(-2)+1*1*(+1)=-3

qΠ(c1,study) = 所有G1取均值

根据样本+G公式求得

 

S1 = C1, A = Facebook

也就是说从C1走，第一个action选Facebook， 则第一个action不会是Study

C1 Facebook F Facebook

G1 = -1 + 1*-1=-2

G1 = -1 + 1 * 0=-1

qΠ(c1, facebook) = 所有G1取均值

q值是边上的值

根据样本+G公式求得

 

在决策概率确定情况下的V值：

vΠ(c1)= 0.5*qπ(c1, study) + 0.5*qπ(c1, facebook)=-1.3

v值是点上的值

通过求q进而求v

 

贝尔曼期望方程：

只是加入了action

分解：黑色的点是Q，白圈就是V：

通过q求v

通过v求q

通过采样和公式求值

多看两步：

后面状态的v，求当前状态的v

后面状态和action的q，求当前状态和action的q

通过后求前

举例：通过后面值，求当前值

由：

假设从pub出去每个action的reward都是0

vπ(Pub) = 0.2*(0+1*-1.3) + 0.4*(0+1*2.7)+0.4*(0+1*7.4)=3.78

vπ(c3)= 0.5*(+1+1*vπ(Pub)) + 0.5*(+10+1*0)=(0.5*(+1+1*3.78) + 0.5*(+10+1*0))=7.39

贝尔曼方程矩阵直接求解：

然后直接得到vπ，同样这种情况也只适合较小的MDP

我们已经知道在策略确定时，v和q的计算方法了，现在问题来了，如果策略不确定，如何寻找最优策略？

也就是上面是Prediction，下面我们看如何control

策略最优问题：

即求使得v或者q最大的策略

最优策略定理：

就是要让每个状态的q或者v值最大，得到的策略就是最优的

例如：

让每个状态的value都最大：

让每个边的q都最大：

如果我们已经求得所有状态最优的q，我们就可以得到最优策略：

一个状态可以有多个action，选择q更大的那个action就是最优策略

举例：在每个q都已经求得最大值后，如何选择策略？

从最左上角出发，最优的策略为红线所示。

所以最终问题是，如何求所有最优的V或者Q

贝尔曼最优方程分解：

对比：

q得到v

之前

现在

不需要把所有加起来，直接选最大q

 

v得到q

之前：

现在：

没有任何变化

 

多看两步：

v得到v：

q得到q

举例：v得到v

 

求解贝尔曼最优方程：

没有直接的解法

迭代的解决办法   

• 价值迭代   
• 策略迭代   
• Q-learning   
• Sarsa

MDP扩展：

• Infinite and continuous MDPs
• Partially observable MDPs
• Undiscounted, average reward MDPs

总结：

• V和Q方程可以互相转换，后面你会发现，Q Policy Iteration 和 V Policy Iteration, Q Value iteration 和 V value iteration都可以求得最优解
• 我们一般做法是在某个随机策略下，更新各个状态的v或者q，然后求各个状态的最大q对应的action，以此更新策略，有了新策略然后继续更新v或者q，然后求最大q对应的action，再更新策略，直到收敛，而且利用的公司就是贝尔曼最优方程