第3章动态规划
3.1动态规划简介

动态规划(Dynamic Programming)是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初，美国数学家R.E.Bellman(贝尔曼)等在研究多阶段决策过程的优化问题时提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的，因此在解决子问题的时候，其结果通常需要存储起来用以解决后续复杂问题。这样就可以避免大量的重复计算，节省时间。
当问题具有下列特性时，通常可以考虑使用动态规划来求解： 第一个特性是一个复杂问题的最优解由数个小问题的最优解构成，可以通过寻找子问题的最优解来得到复杂问题的最优解； 第二个特性是子问题在复杂问题内重复出现，使得子问题的解可以被存储起来重复利用。
马尔可夫决策过程(MDP)具有上述两个特性。贝尔曼方程把问题递归为求解子问题，价值函数相当于存储了一些子问题的解，可以复用。因此可以使用动态规划来求解马尔可夫决策过程(MDP)。
使用动态规划算法求解马尔可夫决策过程(MDP)模型，也就是在清楚模型结构(包括状态转移概率、回报等)的基础上，用规划方法来进行策略评估和策略改进，最终获得最优策略。

策略评估(预测)： 给定一个马尔可夫决策过程模型MDP： <S,A,P,R,γ>和一个策略π，要求输出基于当前策略π的所有状态的值函数Vπ。
策略改进(控制)： 给定一个马尔可夫决策过程模型MDP： <S,A,P,R,γ>和一个策略π，要求确定最优值函数V*和最优策略π*。


3.2策略评估

策略评估要解决问题是，给定一个策略π，如何计算在该策略下的值函数Vπ。
因为实际中涉及的马尔可夫模型规模一般比较大，直接求解效率低，因此可使用迭代法进行求解。考虑应用贝尔曼(Bellman)期望方程进行迭代，公式如下： 
Vπ(s)=∑a∈Aπ(a|s)Ras+γ∑s′∈SPass′Vπ(s′)


可见，状态s处的值函数Vπ(s)，可以利用后继状态s′的值函数Vπ(s′)来表示，依此类推，这种求取值函数的方法称为自举法(Bootstrapping)。


图31迭代法

如图31所示，初始所有状态值函数全部为0。第k+1次迭代求解Vπ(s)时，使用第k次计算出来的值函数Vk（s′）更新计算Vk+1(s)。迭代时使用的公式如下： 
Vk+1(s)=∑a∈Aπ(a|s)Ras+γ∑s′∈SPass′Vk(s′)

对于模型已知的强化学习算法，上式中，Pass′、π(a|s)、Ras都是已知数，唯一的未知数是值函数，因此该方法通过反复迭代最终将收敛。




3.3策略改进

计算值函数的目的是利用值函数找到最优策略。既然值函数已经获得，接下来要解决的问题是如何利用值函数进行策略改善，从而得到最优策略。
一个很自然的方法是针对每个状态采用贪心策略对当前策略进行改进，即
πl+1(s)∈argmaxaQπl(s,a)

其中，Qπ(s,a)可由下式获得： 
Qπ(s,a)=Ras+γ∑s′∈SPass′Vπ(s′)

在当前策略π的基础上，利用贪心算法选取行为，直接将所选择的动作改变为当前最优的动作。
改变之后，策略是不是变得更好了呢？
令动作改变后对应的策略为π′，a′为在状态s下遵循策略π′选取的动作，同理a″为在状态s′下遵循策略π′选取的动作。改变动作的条件是Qπ(s,a′)≥Vπ(s)，则可得
Vπ(s)≤Qπ(s,a′)=∑s′∈SRa′s+γPa′ss′Vπ(s′)≤∑s′∈SRa′s+γPa′ss′Qπ(s′,a″)=…=Vπ′(s)


可见，值函数对于策略的每一点改进都是单调递增的，因此对于当前策略π，可以放心地将其改进为
π′= maxa∈AQπ(s,a)

直到π′与π一致，不再变化，收敛至最优策略。
贪心这个词在计算机领域是指在对问题求解时，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，仅针对短期行为(即一步搜索)求得局部最优解。将贪心算法应用在强化学习中求解最优策略实际上可以获得全局最优解，因为贪心策略公式中的值函数Vπ(s)、Qπ(s,a)已经考虑了未来的回报。因此在策略改进时，可以放心使用贪心算法求得全局最优解。


3.4策略迭代



图32策略迭代


将策略评估算法和策略改进算法合起来便有了策略迭代算法。策略迭代算法通常由策略评估和策略改进两部分构成。在策略评估中，根据当前策略计算值函数。在策略改进中，通过贪心算法选择最大值函数对应的行为。策略评估和策略改进两部分交替进行不断迭代。算法整体流程如图32所示。

假设我们有一个初始策略π1，策略迭代算法首先评估该策略的价值(用E表示)，得到该策略的值函数Vπ1或Qπ1。下一步，策略迭代算法会借助贪心算法对初始策略π1进行改进(用I表示)，得到π2。接着，对改进后的策略π2进行评估，再进一步改进当前策略，如此循环迭代，直到策略收敛至最优。
π1EVπ1,Qπ1Iπ2EVπ2,Qπ2I…π*EV*,Q*Iπ*

其中，π1为初始策略，E表示策略评估，I表示策略改进。策略评估过程中，对于任意的策略πk，通过贝尔曼期望方程进行迭代计算得到Vπk和Qπk。例如： 
Vπk(s)=Vπkk(s)=∑a∈Aπk(a|s)Ras+γ∑s′∈SPass′Vπkk-1(s′)


策略改进部分，用贪心算法得到更新的策略： 
π′(s)=argmaxa∈AQπk(s,a)

或者
π′(s)= argmaxa∈ARas+γ∑s′∈SPass′Vπk(s′)

算法流程如下。



算法： 策略迭代算法

输入： MDP五元组M=<S,A,P,R,γ>

初始化值函数V(s)=0，初始化策略π1为随机策略



Loop

Fork=0，1，2，3…do

s∈S′： V′(s)=∑a∈Aπ(a|s)Ras+γ∑s′∈SPass′V(s′)

ifV′=V

end if

end for

s∈S′： π′(s)=argmaxa∈AQ(s,a)

or π′(s)= argmaxa∈ARas+γ∑s′∈SPass′V(s′)

ifs：  π′(s)=π(s) then

break

elseπ=π′

end if

end loop
输出： 最优策略π

在策略评估过程中，往往需要等到值函数收敛之后才能进行策略改进，这其实是没有必要的。可以在进行一次策略评估之后就开始策略改进，如此循环往复执行这两个过程，最终会收敛到最优值函数和最优策略，如图33所示，这便是广义策略迭代的思想，很多强化学习方法都用到了这种思想。


图33广义策略迭代




3.5值迭代

策略迭代算法在每次进行策略评估时，采用贝尔曼期望方程更新值函数。而值迭代算法借助的是贝尔曼最优方程，直接使用行为回报的最大值更新原来的值，如图34所示。

Vk+1(s)= maxa∈ARas+γ∑s′∈SPass′Vk(s′)



图34求取Vk+1(s)



值迭代算法将策略改进视为值函数的改善，每一步都求取最大的值函数，即
V1→V2→V3→…→V*

假设在状态s下，我们有一个初始值函数V1(s)，基于当前状态，我们有多个可选行为a。每个行为a会引发一个立即回报Ras，一个或多个状态转移，如从状态s转换至状态s′。不同状态s′对应有不同的值函数V1(s′)整个的Ras+γ∑s′∈SPass′V1(s)称为a的行为回报。值迭代算法直接使用所有行为引发的行为回报中取值最大的那个值来更新原来的值，得到V2（s）。如此迭代计算，直至值函数收敛，整个过程没有遵循任何策略。
虽然算法中没有给出明确的策略，但是根据公式
Vt+1(s)←maxa∈AQt+1(s,a)

可以看出策略改进是隐含在值迭代过程中执行的。
算法流程如下。



算法： 值迭代算法

输入： MDP五元组M=<S,A,P,R,γ>

初始化值函数V(s)=0，收敛阈值θ

For k=0，1，2，3…do

s∈S′： V′(s)=maxa∈ARas+γ∑s′∈SPass′V(s′)

ifmaxs∈S|V′(s)-V(s′)|<θthen

break

else V=V′

end if

end for

s∈S′： π′(s)=argmaxa∈AQ(s,a)

or π′(s)=argmaxa∈ARas+γ∑s′∈SPass′V(s′)

输出： 最优策略π′



3.6实例讲解

本节以在5×5的网格世界中寻找宝藏为例，分别使用策略迭代和值迭代算法寻找最优策略，并比较两种算法在处理上的异同，以及两者的运行效率。
3.6.1“找宝藏”环境描述
1. 环境描述

首先构建寻宝环境的马尔可夫决策模型M=<S,A,P,R,γ>。


图355×5网格世界


如图35所示为5×5的网格世界，其状态空间为S={0,1,…,24}，其中状态8为宝藏区。动作空间A={UP,RIGHT,DOWN,LEFT}，宝藏区回报为r=0，其他位置回报为r=-1。
当智能体位于网格世界边缘位置时，任何使其离开网格世界的行为都会使其停留在当前位置。例如，当位于0位置时，采取向上的行为，a=UP，智能体获取-1的回报后，重新回到位置0。当智能体位于宝藏区时，则无论采取何种行为，均会产生0回报，且位置不变。当智能体位于其他位置时，采取任何一个行为，则会向相应的方向移动一格。状态转移概率pass′=1。折扣因子γ=1。
求解此网格世界寻找宝藏的最优策略。

2. 环境代码
接下来基于gym构建寻找宝藏的环境，以下代码主要定义了寻宝藏MDP模型的状态空间、行为空间、状态转移概率和回报等信息。此环境代码较为简单，读者可结合注释，加深对此代码的理解。




import numpy as np

import sys

from gym.envs.toy_text import discrete

#定义动作空间

UP = 0

RIGHT = 1

DOWN = 2

LEFT = 3

#定义宝藏区(宝藏所在的状态)

DONE_LOCATION = 8

#定义网格世界环境模型

class GridworldEnv(discrete.DiscreteEnv)： 







"""定义了一个5×5网格，如下所示： 

o o o o o

o o o T o

o o o o o

o x o o o

o o o o o

x是智能体的位置，T是宝藏位置，智能体的目标是到达宝藏位置。在每个状态都可以采取4种行为(UP = 0，RIGHT = 1，DOWN = 2，LEFT = 3)。每一步移动都会收到-1回报，直到达到宝藏状态"""

def init(self, shape=［5,5］):

if not isinstance(shape, (list, tuple)) or not len(shape) == 2:

raise ValueError('shape argument must be a list/tuple of length 2')

self.shape = shape

#np.prod函数是乘法，如传进去［4,5,6］，那么就是120。而这里传进去的就是5,5，

#得到25就代表元素的个数。Max_y和Max_x得到横排和竖排的个数

nS = np.prod(shape)#状态个数

nA = 4#动作个数

MAX_Y = shape［0］ #5

MAX_X = shape［1］#5

#grid是创建一个5x5的表格，而np.nditer是为这个表格索引排序

#flags=［'multi_index'］表示对grid进行多重索引，如(1,3)

P = {}

grid = np.arange(nS).reshape(shape)

it = np.nditer(grid, flags=［'multi_index'］)

#s得到的是一个索引值。p［s］［a］记录的是对于每一个格子采用四种走法，即上右下左之后产

#生的回报、下一个状态、是否达到宝藏区等信息。

#is_done记录是否到达宝藏区，如果到达则返回true，否则返回false

#Reward为回报，除了宝藏区，其他状态都是-1回报

while not it.finished:

s = it.iterindex

y, x = it.multi_index

P［s］ = {a: ［］ for a in range(nA)}

is_done = lambda s: s == DONE_LOCATION

reward = 0.0 if is_done(s) else -1.0

#p［s］［a］中第一个参数是状态转移概率，为1。第二个参数代表到达下一个的位置。

#第三个参数reward表示回报。最后一个参数为True表示达到宝藏区，为false表示未到达宝

#藏区

if is_done(s):

#如果位于宝藏区，则采取上下左右之后，依然会转换到宝藏区

P［s］［UP］ = ［(1, s, reward, True)］

P［s］［RIGHT］ = ［(1, s, reward, True)］

P［s］［DOWN］ = ［(1, s, reward, True)］

P［s］［LEFT］ = ［(1, s, reward, True)］

else:

#宝藏区之外的状态，采取上下左右之后，所进行的状态转换







ns_up = s if y == 0 else s - MAX_X

ns_right = s if x == (MAX_X - 1) else s + 1

ns_down = s if y == (MAX_Y - 1) else s + MAX_X

ns_left = s if x == 0 else s - 1

P［s］［UP］ = ［(1, ns_up, reward, is_done(ns_up))］

P［s］［RIGHT］ = ［(1, ns_right, reward, is_done(ns_right))］

P［s］［DOWN］ = ［(1, ns_down, reward, is_done(ns_down))］

P［s］［LEFT］ = ［(1, ns_left, reward, is_done(ns_left))］

it.iternext()

isd = np.ones(nS) / nS

self.P = P

super(GridworldEnv, self).init(nS, nA, P, isd)





3.6.2策略迭代
1. 算法详情

使用策略迭代法对此问题进行求解。假设初始策略为均匀随机策略： 
π(UP|·)=0.25，π(RIGHT|·)=0.25，π(DOWN|·)=0.25，π(LEFT|·)=0.25

(1) 首先评估给定随机策略下的值函数，使用贝尔曼期望方程迭代计算直至值函数收敛。
初始所有状态值函数全部为0。在对值函数进行迭代计算时，使用如下公式： 
Vk+1(s)=∑a∈Aπ(a|s)Ras+γ∑s′∈SPass′Vk(s′)

k=0时，随机策略下的值函数Vπ0(s)为： 





0.00.00.00.00.0
0.00.00.00.00.0

0.00.00.00.00.0
0.00.00.00.00.0
0.00.00.00.00.0

k=1时，随机策略下的值函数Vπ1(s)为： 





-1.-1.25-1.3125-1.328125-1.33203125

-1.25-1.625-1.7343750-1.33300781

-1.3125-1.734375-1.8671875-1.46679688-1.69995117
-1.328125-1.765625-1.90820312-1.84375-1.88592529
-1.33203125-1.77441406-1.9206543-1.94110107-1.95675659

k=2时，随机策略下的值函数Vπ2(s)为： 





-2.125-2.578125-2.73828125-2.34960938-2.58666992
-2.578125-3.15625-2.940429690-2.40490723
-2.73828125-3.38183594-3.42431641-2.74200439-3.18319702
-2.79101562-3.46386719-3.66314697-3.55804443-3.64598083
-2.80737305-3.49157715-3.75411987-3.80250549-3.84049988

k=3时，随机策略下的值函数Vπ3(s)为： 





-3.3515625-3.95605469-3.99609375-3.23309326-3.70283508
-3.95605469-4.55859375-3.994750980-3.32273483
-4.21679688-4.91589355-4.82894897-3.89254761-4.51111507
-4.31976318-5.09759521-5.30967712-5.16267776-5.29006839
-4.35652161-5.17495346-5.51031399-5.57899928-5.63751686

k=4时，随机策略下的值函数Vπ4(s)为： 





-4.65380859-5.2911377-5.12876892-4.01617432-4.68614483
-5.34631348-5.88702393-4.961185460-4.12999868
-5.69969177-6.37831497-6.13543129-4.95230603-5.72087204
-5.86839294-6.68283463-6.87281442-6.67354703-6.83050108
-5.9390974-6.82679987-7.19723189-7.27182376-7.34433964

k=41时，随机策略下的值函数Vπ41(s)为： 





-35.74494727-32.12641885-24.538604-15.06495731-16.92612327
-36.99508377-33.06340423-23.041452410-15.19035534
-39.42427668-36.72916281-30.88336916-23.26533384-25.00530954
-41.89467692-40.31033299-37.11427253-33.74277078-33.11384648
-43.38748716-42.36206491-40.28332744-38.18485134-37.28195844

k=338时，随机策略下的值函数Vπ338(s)收敛，收敛结果为： 





-47.13614306-41.72708685-31.24229447-18.62114329-20.62114063
-48.54523094-42.80284177-29.378665220-18.62114576
-51.69673216-47.56039644-39.46953083-29.37866962-31.24230361
-54.98459517-52.27249581-47.56040397-42.80285506-41.72710615
-56.98458538-54.98460426-51.6967489-48.54525416-47.13617306
对应代码如下。




V = np.zeros(env.nS)

i = 0



while True:

value_delta = 0

# 遍历各状态

for s in range(env.nS):

v = 0

# 遍历各行为的概率(上,右,下,左)

for a, action_prob in enumerate(policy［s］):

# 对于每个行为确认下个状态

# 四个参数: prob:概率, next_state: 下一个状态的索引, reward: 回报, 

#done: 是否是终止状态

for prob, next_state, reward, done in env.P［s］［a］:

# 使用贝尔曼期望方程进行状态值函数的求解

v += action_prob * prob * (reward + discount_factor * V［next_state］)

# 求出各状态和上一次求得状态的最大差值

value_delta = max(value_delta, np.abs(v - V［s］))

V［s］ = v





(2) 使用如下公式： 
π*(a|s)= argmaxa∈ARas+γ∑s′∈SPass′V*(s′)


对收敛的值函数Vπ338(s)，使用贪心算法进行策略改进，求取Vπ338(s)对应的改进后的策略π1，则有π1： 





→→→↓←
→→→宝藏←
→→↑↑↑
↑↑↑↑↑
↑→↑↑↑

对应代码如下： 




# 评估当前的策略,输出为各状态的当前的状态值函数

V = policy_eval_fn(policy, env, discount_factor)

# 定义一个当前策略是否改变的标识

policy_stable = True



# 遍历各状态

for s in range(env.nS):

# 取出当前状态下最优行为的索引值

chosen_a = np.argmax(policy［s］)



# 初始化行为数组［0,0,0,0］

action_values = np.zeros(env.nA)

for a in range(env.nA):

# 遍历各行为

for prob, next_state, reward, done in env.P［s］［a］:

# 根据各状态值函数求出行为值函数

action_values［a］ += prob * (reward + discount_factor * V［next_state］)



# 输出一个状态下所有的可能性

best_a_arr, policy_arr = get_max_index(action_values)

if chosen_a not in best_a_arr:

policy_stable = False

policy［s］ = policy_arr





(3) 继续使用贝尔曼期望方程求取当前策略π1下的值函数，直至值函数收敛。计算过程与(1)相同。
经过5轮迭代，值函数收敛，得到Vπ15(s)为： 





-4-3-2-1-2
-3-2-10-1
-4-3-2-1-2
-5-4-3-2-3
-6-5-4-3-4

(4) 针对值函数Vπ15(s)，进行第二次策略改善，得到π2。
(5) 继续求取π2对应的值函数(策略评估)，针对收敛的值函数Vπ25(s)进行第三次策略改进，得到π3。经过三次策略改进，策略收敛。
对应最优值函数V*(Vπ25(s))为： 





-4-3-2-1-2
-3-2-10-1
-4-3-2-1-2
-5-4-3-2-3
-6-5-4-3-4

最优策略π*(π3)为： 





↓→↓→↓→↓←↓
→→→宝藏←
↑→↑→↑→↑←↑
↑→↑→↑→↑←↑
↑→↑→↑→↑←↑

代码如下。




if policy_stable:

return policy, V




policy_stable初始为True，策略未达到收敛时不会输出策略和值函数，只有达到最优收敛之后结束迭代时，才会输出最优策略和值函数。

2. 核心代码
策略迭代算法主要包含两步，即策略评估和策略改进，重点包含了两个函数policy_eval方法和policy_improvement方法。
policy_eval方法是策略评估方法，输入要评估的策略policy，环境env，折扣因子discount_factor，阈值threshold。输出当前策略下收敛的值函数V。
policy_improvement是策略改进方法，输入为环境env，策略评估函数policy_eval，折扣因子discount_factor。输出为最优值函数和最优策略。
(1) 首先展示策略评估方法： 




def policy_eval(policy, env, discount_factor=1, threshold=0.00001):  #

# 初始化各状态的状态值函数

V = np.zeros(env.nS)

i = 0







while True:

value_delta = 0

# 遍历各状态

for s in range(env.nS):

v = 0

# 遍历各行为的概率(上,右,下,左)

for a, action_prob in enumerate(policy［s］):

# 对于每个行为确认下个状态

# P［s］［a］含四个参数。 prob:状态转换概率， next_state: 下一个状态， reward: #回报， done: 是否是终止状态(宝藏区)

for prob, next_state, reward, done in env.P［s］［a］:

# 使用贝尔曼期望方程进行状态值函数的求解

v += action_prob * prob * (reward + discount_factor * V［next_state］)

# 求出各状态和上一次求得状态的最大差值

value_delta = max(value_delta, np.abs(v - V［s］))

V［s］ = v

i += 1

# 当前循环得出的各状态和上一次状态的最大差值小于阈值，则收敛，停止运算

if value_delta < threshold:

break

return np.array(V)




(2) 策略改进方法通过调用策略评估方法实现。




# 定义两个全局变量用来记录运算的次数

v_num = 1

i_num = 1

# 根据传入的四个行为选择值函数最大的索引，返回的是一个索引数组和一个行为策略

def get_max_index(action_values):

indexs = ［］

policy_arr = np.zeros(len(action_values))

action_max_value = np.max(action_values)



for i in range(len(action_values)):

action_value = action_values［i］



if action_value == action_max_value:

indexs.append(i)

policy_arr［i］ = 1

return indexs,policy_arr



# 将策略中的每行可能行为改成元组形式，方便对多个方向的表示

def change_policy(policys):

action_tuple = ［］








for policy in policys:

indexs, policy_arr = get_max_index(policy)

action_tuple.append(tuple(indexs))



return action_tuple

#policy_improvement是策略改进方法，输入为环境env，策略评估函数policy_eval，折扣因子

#输出为最优值函数和最优策略

def	 policy_improvement(env, policy_eval_fn=PolicyEvaluationSolution.policy_eval, discount_factor=1.0)

# 初始化一个随机策略

policy = np.ones(［env.nS, env.nA］) / env.nA



while True:

global i_num

global v_num



v_num = 1

# 评估当前的策略，输出为各状态的当前的状态值函数

V = policy_eval_fn(policy, env, discount_factor)

# 定义一个当前策略是否改变的标识

policy_stable = True



# 遍历各状态

for s in range(env.nS):

# 取出当前状态下最优行为的索引值

chosen_a = np.argmax(policy［s］)




# 初始化行为数组［0,0,0,0］

action_values = np.zeros(env.nA)

for a in range(env.nA):

# 遍历各行为

for prob, next_state, reward, done in env.P［s］［a］:

# 根据各状态值函数求出行为值函数

action_values［a］ += prob * (reward + discount_factor * V［next_state］)



#因为np.argmax(action_values)只会选取第一个最大值出现的索引，会丢掉其他方

#向的可能性，所以这个方法会输出一个状态下所有的可能性

best_a_arr, policy_arr = get_max_index(action_values)



# 如果求出的最大行为值函数的索引(方向)没有改变，则定义当前策略未改变，收敛输出，

# 否则将当前状态中将有最大行为值函数的方向置1，其余方向置0

if chosen_a not in best_a_arr:

policy_stable = False

policy［s］ = policy_arr

i_num = i_num + 1









# 如果当前策略没有发生改变，即已经到了最优策略，返回

if policy_stable:

return policy, V

env = GridworldEnv()

policy, v = policy_improvement(env)

update_policy_type = change_policy(policy)





3.6.3值迭代
1. 算法详情

在进行一次策略评估(即求取当前策略下的值函数)之后就进行策略改进，这种方法称为值函数迭代算法。即，在每次进行值函数计算时，直接选择那个使得值函数最大的行为。
(1) 初始值函数Vπ0(s)为(k=0)： 





0.00.00.00.00.0

0.00.00.00.00.0

0.00.00.00.00.0

0.00.00.00.00.0

0.00.00.00.00.0

代码如下。




V=np.zeros(env.nS)




(2) 使用贝尔曼最优方程，直接使用当前状态的最大行为值函数更新当前状态值函数。
Vk+1(s)= maxa∈ARas+γ∑s′∈SPass′Vk(s′)

第一次迭代(k=1)，得Vπ1(s)为： 





-1-1-1-1-1
-1-1-10-1
-1-1-1-1-1
-1-1-1-1-1
-1-1-1-1-1

第二次迭代(k=2)，得Vπ2(s)为： 





-2-2-2-1-2
-2-2-10-1
-2-2-2-1-2
-2-2-2-2-2
-2-2-2-2-2

第三次迭代(k=3)，得Vπ3(s)为： 





-3-3-2-1-2
-3-2-10-1
-3-3-2-1-2
-3-3-3-2-3
-3-3-3-3-3

第七次之后各状态的最优行为值函数已经收敛，Vπ7(s)为： 





-4-3-2-1-2
-3-2-10-1
-4-3-2-1-2
-5-4-3-2-3
-6-5-4-3-4
对应的最优策略为： 





↓→↓→↓→↓←↓
→→→宝藏←
↑→↑→↑→↑←↑
↑→↑→↑→↑←↑
↑→↑→↑→↑←↑

求取各状态下最大行为值函数代码如下： 




V = np.zeros(env.nS)



while True:

# 停止条件

delta = 0

# 遍历每个状态

for s in range(env.nS):

# 计算当前状态的各行为值函数

q = one_step_lookahead(s, V)

# 找到最大行为值函数

best_action_value = np.max(q)

# 值函数更新前后求差

delta = max(delta, np.abs(best_action_value - V［s］))

# 更新当前状态的值函数，即将最大的行为值函数赋值给当前状态，用以更新当前状态的

# 值函数

V［s］ = best_action_value



i_num += 1

# 如果当前状态值函数更新前后相差小于阈值,则说明已经收敛,结束循环

if delta < threshold:

break




求取最优策略的代码如下。




# 初始化策略

policy = np.zeros(［env.nS, env.nA］)

# 遍历各状态

for s in range(env.nS):

# 根据已经计算出的V,计算当前状态的各行为值函数

q = one_step_lookahead(s, V)

# 求出当前最大行为值函数对应的动作索引

# 输出一个状态下所有的可能性

best_a_arr, policy_arr = get_max_index(q)

# 将当前所有最优行为赋值给当前状态

policy［s］ = policy_arr





2. 核心代码
值迭代方法将策略改进视为值函数的改进，每一步都求取最大行为值函数，用最大行为值函数更新当前状态值函数。值迭代方法为value_iteration，输入为环境env，阈值threshold，折扣因子discount_factor。输出为最优值函数和最优策略。在进行值函数更新时，使用了最优贝尔曼方程。其中方法one_step_lookahead用以求取当前状态的所有行为值函数。
代码如下。




from lib.envs.gridworld import GridworldEnv

# 定义1个全局变量用来记录运算的次数

i_num = 1

# 根据传入的四个行为选择值函数最大的索引，返回的是一个索引数组和一个行为策略

def get_max_index(action_values):

indexs = ［］

policy_arr = np.zeros(len(action_values))

action_max_value = np.max(action_values)

for i in range(len(action_values)):

action_value = action_values［i］

if action_value == action_max_value:

indexs.append(i)

policy_arr［i］ = 1

return indexs,policy_arr

# 将策略中的每行可能行为改成元组形式，方便对多个方向的表示

def change_policy(policys):

action_tuple = ［］

for policy in policys:

indexs, policy_arr = get_max_index(policy)

action_tuple.append(tuple(indexs))

return action_tuple



def value_iteration(env, threshold=0.0001, discount_factor=1.0):

"""

值迭代算法

env表示环境

env.P ［s］ ［a］(prob，next_state，reward，done)记录状态转移概率、下一个状态、回报、是否结束

env.nS是环境状态空间

env.nA是环境动作空间

discount_factor:折扣因子

返回:最优策略和最优值函数

"""

global i_num



def one_step_lookahead(state, V)

#求取当前状态的所有行为值函数

q = np.zeros(env.nA)

for a in range(env.nA):

for prob, next_state, reward, done in env.P［state］［a］:

q［a］ += prob * (reward + discount_factor * V［next_state］)

return q










V = np.zeros(env.nS)



while True:

# 停止条件

delta = 0

# 遍历每个状态

for s in range(env.nS):

# 计算当前状态的各行为值函数

q = one_step_lookahead(s, V)

# 找到最大行为值函数

best_action_value = np.max(q)

#  值函数更新前后求差

delta = max(delta, np.abs(best_action_value - V［s］))

# 更新当前状态的值函数，即将最大的行为值函数赋值给当前状态，用以更新当前

# 状态的值函数

V［s］ = best_action_value

i_num += 1

# 如果当前状态值函数更新前后相差小于阈值，则说明已经收敛，结束循环

if delta < threshold:

break



# 初始化策略

policy = np.zeros(［env.nS, env.nA］)

# 遍历各状态

for s in range(env.nS):

# 根据已经计算出的V，计算当前状态的各行为值函数

q = one_step_lookahead(s, V)

# 求出当前最大行为值函数对应的动作索引

# 在初始策略中对应的状态上将最大行为值函数方向置1，其余方向保持不变，仍为0

# 因为np.argmax(action_values)只会选取第一个最大值出现的索引，

# 会丢掉其他方向的可能性，所以以下方法会输出一个状态下所有的可能性

best_a_arr, policy_arr = get_max_index(q)

# 将当前所有最优行为赋值给当前状态

policy［s］ = policy_arr

return policy, V

env = GridworldEnv()

policy, v = value_iteration(env)

update_policy_type = change_policy(policy)





3.6.4实例小结
本节分别使用策略迭代和值迭代解决同一个网格世界寻找宝藏的问题，均给出了最优策略。
从策略迭代的代码可以看到，进行策略改进之前需要得到收敛的值函数。值函数的收敛往往需要很多次迭代。例如，在第一次策略改进之前，进行了338次迭代。进行策略改进之前一定要等到策略值函数收敛吗？答案是不需要。依然以第一次策略改进之前策略评估为例，策略评估迭代41次和迭代338次所得到的贪心策略是一样的，可见策略迭代方法在效率方面存在问题。
相比而言，值迭代方法就高效得多，每一次都直接用最大的行为值函数更新当前状态的值函数，直至值函数收敛，输出最优策略，其解决同样的问题仅仅需要7次迭代。


3.7小结

动态规划是用来解决已知模型强化学习问题的基础方法。具体来说，它包括策略迭代和值迭代两类算法。策略迭代通过策略评估和策略改进交替进行求取最优策略。值迭代在进行每一步的策略评估时，直接求取最优值函数，值函数收敛后求取最优策略。本章通过网格世界寻找宝藏的实例，详细介绍了两种算法的求解过程和代码，并对两者的效率进行了比较，相比而言，值迭代算法具有更高的效率。

3.8习题

1. 动态规划是什么？它适合解决什么类型的问题?
2. 什么是策略评估和策略改进？
3. 简述策略迭代算法和值迭代算法。
4. 策略迭代和值迭代这两个算法的区别和联系是什么？
5. 假设在本章案例的迷宫问题中，对每个状态的立即奖赏加上一个常量C，这样对最终结果是否有影响？请给出解释。