上一次已经分享了强化学习的概念以及基本的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)都收敛。
下面总结一下Policyevaluation和Policy improvement这两个阶段：
2.1 策略评估Policy evaluation
策略评估就是在任意策略下，计算每个状态的值函数vπ，我们也把它称为预测问题。由值函数的定义V**π(s)=E**π[G**t∣S**t=s]展开为
V π
∑ 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
策略改进是Greedypolicy，它寻找每个状态下得到最大值函数vπ的策略π，也就是说，采取哪个动作可以达到下一个状态的最大值，那么就选择这个动作为最优策略
计算期望值
Q π
∑ s ′ , r
P ( s ′ , r ∣ s , a ) ( r
γV π
( s ′ ))
改进策略
argmax a
Q π
( s , a )
改进策略后更新状态值
V π ′
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
策略迭代算法的伪代码如下所示：
三、价值迭代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
max
∑ s ′ , r
P ( s ′ , r ∣ s , a ) ( r
γV t
( s ′ ))
值迭代的伪代码如下：
值迭代的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 {} roundsconverge'.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方程来更新状态值函数
不同点：
1、策略迭代在价值评估阶段，每迭代一次都需要保证每个状态的值函数收敛，这是非常耗时的；而值迭代是采用动态规划的思想来收敛每个状态的值函数的。
2、策略迭代的第二步policy evaluation与值迭代的第二步findingoptimal value function十分相似，除了后者用了max操作，前者没有max.因此后者可以得出optimal value function, 而前者不能得到optimalfunction.
3、策略迭代的收敛速度更快一些，在状态空间较小时，最好选用策略迭代方法。当状态空间较大时，值迭代的计算量更小一些。
4*****、侧重点不同：策略迭代最后是策略收敛，而值迭代是值函数收敛；收敛的方式也不同，策略迭代是argmax，而值函数是max。