强化学习三、策略迭代与值迭代

青旅半醒 2021-09-23 12:16 970阅读 0赞

本文参考[http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Teaching.html][http_www0.cs.ucl.ac.uk_staff_D.Silver_web_Teaching.html]

上一次已经分享了强化学习的概念以及基本的MDP，本节将分享基于Bellman方程和动态规划的策略迭代和值迭代，对于Bellman方程，大家都比较清楚了，那么我们先介绍一下动态规划算法的基本原理

**一、动态规划**

这里面我要简单介绍一下动态规划，因为严格来说，值迭代与策略迭代是用来解决动态规划问题的两种规划方法。而强化学习又有另外一个昵称——就是拟动态规划。说白了强化学习就是模拟动态规划算法。

用一句话来总结动态规划就是，对一个复杂问题给出一个一般性的解决办法。它主要由两个性质:

1、最优子结构：最优解法能被分解到多个子问题中

2、重叠子问题：子问题能重复多次且解法能被重复利用

马尔科夫决策过程（MDP）满足以上两个性质，所以任何MDP都可以用动态规划来解。动态规划与强化学习的区别就是动态规划假设MDP模型是全知的（即参数可知） 而强化学习可以使MDP未知。

MDP需要解决的问题有两种，第一种是prediction，它已知MDP的S,A,P,R,γ以及policy，目标是算出在每个状态下的value function(值函数其实就是问题的目标，一般都是跟reward有关的函数，例如Atari小游戏，一般值函数就是累计的得分的期望。目标一般就是最大化这个值函数。而第二种是control，它已知MDP的S,A,P,R,γ但是policy未知（即动作action未知），因此它的目标不仅是计算出最优的value function而且要给出最优的Policy。

**二、策略迭代POLICY ITERATION**

策略迭代就是在policy未知的情况下，根据每次的reward学到最优policy。策略迭代每次先初始化每个状态的值函数v(s)和一个策略，然后根据这个策略计算值函数v(s), 通过这个值函数来根据贪心策略更新策略，不断迭代直到策略收敛，下面是算法的流程：

1、initialization

初始化所有状态的v(s)以及π(s)（初始化为随机策略）

2、poicy evaluation

用当前的v(s)对当前策略进行评估，计算出每一个状态的v(s)，直到v(s)收敛，才算训练好了这个状态价值函数V(s)

3、policy improvement

既然上一步已经得到了当前策略的评估函数V(s),那么就可以利用这个评估函数进行策略改进啦。

在每个状态s时，对每个可能的动作a,都计算一下采取这个动作后到达的下一个状态的期望价值。看看哪个动作可以到达的状态的期望价值函数最大，就选取这个动作。以此更新了π(s)

然后再次循环上述２、３步骤，直到V(s)与π(s)都收敛。

下面总结一下Policy evaluation和Policy improvement这两个阶段：

**2.1****策略评估Policy evaluation**

策略评估就是在任意策略下，计算每个状态的值函数vπ，我们也把它称为预测问题。由值函数的定义*V**π*(*s*)=*E**π*\[*G**t*∣*S**t*=*s*\]展开为

*V**π*(*s*)=∑*a**π*(*a*∣*s*)∑*s*′*P*(*s*′∣*s*,*a*)(*R*(*s*,*a*,*s*′)\+*γV**π*(*s*′))

其中*π*(*a*∣*s*)为在s状态下执行动作a的概率，

下面是策略评估的python代码

def policy\_evaluation(self, agent, max\_iter=-1):

iteration = 0

\# iterative eval

while True:

\# one iteration

iteration += 1

new\_value\_pi = agent.value\_pi.copy()

for i in range(1, agent.s\_len):  \# for each state

value\_sas = \[\]

ac = agent.pi\[i\]

transition = agent.p\[ac, i, :\]

value\_sa = np.dot(transition, agent.r + agent.gamma \* agent.value\_pi)

new\_value\_pi\[i\] = value\_sa  \# value\_sas\[agent.policy\[i\]\]

diff = np.sqrt(np.sum(np.power(agent.value\_pi - new\_value\_pi, 2)))

\# print 'diff=\{\}'.format(diff)

if diff < 1e-6:

break

else:

agent.value\_pi = new\_value\_pi

if iteration == max\_iter:

break

**2.2****策略改进Policy improvement**

策略改进是Greedy policy，它寻找每个状态下得到最大值函数vπ的策略π，也就是说，采取哪个动作可以达到下一个状态的最大值，那么就选择这个动作为最优策略

计算期望值

*Q**π*(*s*,*a*)=∑*s*′,*r**P*(*s*′,*r*∣*s*,*a*)(*r*\+*γV**π*(*s*′))

改进策略

*π*′(*s*)=*argmax**a**Q**π*(*s*,*a*)

改进策略后更新状态值

*V**π*′(*s*)=*max**a*∑*s*′,*r**P*(*s*′,*r*∣*s*,*a*)(*r*\+*γV**π*′(*s*′))

策略改进的python代码如下：

def policy\_improvement(self, agent):

new\_policy = np.zeros\_like(agent.pi)

for i in range(1, agent.s\_len):

for j in range(0, agent.a\_len):

agent.value\_q\[i, j\] = np.dot(agent.p\[j, i, :\], agent.r + agent.gamma \* agent.value\_pi)

max\_act = np.argmax(agent.value\_q\[i, :\])

new\_policy\[i\] = max\_act

if np.all(np.equal(new\_policy, agent.pi)):

return False

else:

agent.pi = new\_policy

return True

策略迭代算法的伪代码如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70][]

**三、价值迭代VALUE ITERATION**

价值迭代算法主要流程如下。

1、初始化Value Function，即对每个状态的价值都赋一个初始值，一般是0

2、计算每一个状态-动作pair 的值，也就是Q(s,a)

3、 每一个状态st下都有一个动作空间at∈A，maxatQ(st,at)，即最大的Q值作为当前状态的价值，更新Value Function

4、返回第2步，直至Value Function收敛。

迭代公式如下：

*V**t*\+1(*s*)=*max*∑*s*′,*r**P*(*s*′,*r*∣*s*,*a*)(*r*\+*γV**t*(*s*′))

值迭代的伪代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70 1][]

值迭代的python代码如下：

def value\_iteration(self, agent, max\_iter=-1):

iteration = 0

while True:

iteration += 1

new\_value\_pi = np.zeros\_like(agent.value\_pi)

for i in range(1, agent.s\_len):  \# for each state

value\_sas = \[\]

for j in range(0, agent.a\_len):  \# for each act

value\_sa = np.dot(agent.p\[j, i, :\], agent.r + agent.gamma \* agent.value\_pi)

value\_sas.append(value\_sa)

new\_value\_pi\[i\] = max(value\_sas)

diff = np.sqrt(np.sum(np.power(agent.value\_pi - new\_value\_pi, 2)))

if diff < 1e-6:

break

else:

agent.value\_pi = new\_value\_pi

if iteration == max\_iter:

break

print('Iter \{\} rounds converge'.format(iteration))

for i in range(1, agent.s\_len):

for j in range(0, agent.a\_len):

agent.value\_q\[i, j\] = np.dot(agent.p\[j, i, :\], agent.r + agent.gamma \* agent.value\_pi)

max\_act = np.argmax(agent.value\_q\[i, :\])

agent.pi\[i\] = max\_act

那么策略迭代和值迭代有什么区别和联系呢？

共同点：

1.  他们都是基于模型的方法，也就是说都需要知道环境的状态转移概率P；
2.  都需要通过bellman方程来更新状态值函数

不同点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70 3][]

1、策略迭代在价值评估阶段，每迭代一次都需要保证每个状态的值函数收敛，这是非常耗时的；而值迭代是采用动态规划的思想来收敛每个状态的值函数的。

2、策略迭代的第二步policy evaluation与值迭代的第二步finding optimal value function十分相似，除了后者用了max操作，前者没有max.因此后者可以得出optimal value function, 而前者不能得到optimal function.

3、策略迭代的收敛速度更快一些，在状态空间较小时，最好选用策略迭代方法。当状态空间较大时，值迭代的计算量更小一些。

4\*\*\*\*\*、侧重点不同：策略迭代最后是策略收敛，而值迭代是值函数收敛；收敛的方式也不同，策略迭代是argmax，而值函数是max

[http_www0.cs.ucl.ac.uk_staff_D.Silver_web_Teaching.html]: http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Teaching.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70]: /images/20210923/4684dedea5b04603a677ef42bb8af600.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70 1]: /images/20210923/00f08a3ec46c444eac61ab809162ee4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70 2]: /images/20210923/10e99316ad5f4dc38107c85ca0593c3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzaHpk_size_16_color_FFFFFF_t_70 3]: /images/20210923/7fd16395439545cb8408c57da98741f4.png