强化学习系列案例 | 利用策略迭代和值迭代求解迷宫寻宝问题
原创
查看本案例完整的数据、代码和报告请登录数据酷客（cookdata.cn）案例板块。
迷宫寻宝问题是指玩家和宝藏在同一个有限空间中，但宝藏和玩家并不在同一个位置，玩家可以上下左右移动，找到宝藏即游戏结束，在迷宫寻宝中要解决的问题是玩家如何以最小的步数找到宝藏。本案例中我们将使用强化学习方法解决迷宫寻宝问题，将其形式化为一个MDP问题，然后分别使用策略迭代和值迭代两种动态规划方法进行求解，得到问题的最佳策略。
1.价值的概念
在寻找最佳策略时，每一步都十分重要，对于某些状态，虽然这个状态本身并没有直接得到最优结果，但是只要进入这个状态就可以通过合理的动作出现最好的局面，因此认为这些状态本身是有“价值”的，“价值”是指在“正确的动作”前提下能获得的最大奖励，下面给出两个状态价值的定义。
- 策略下状态的价值：即当前处于状态𝑠，按照策略𝜋执行后可以获得的累积期望奖励，记为
- 状态的价值：即当前处于状态𝑠，且之后按照“最佳策略”执行，能够获得的累积期望奖励，记为
2.Bellman方程
可以利用动态规划的方法求解策略下状态价值，动态规划的思想是将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。Bellman方程，又叫动态规划方程，表示动态规划问题中相邻状态关系的方程，某些决策问题可以按照时间或空间分成多个阶段，每个阶段做出决策从而使整个过程取得效果最优的多阶段决策问题，可以用动态规划方法求解。某一阶段最优决策的问题，通过Bellman方程转化为下一阶段最优决策的子问题，从而初始状态的最优决策可以由终状态的最优决策(一般易解)问题逐步迭代求解。
状态的价值函数可以用递归的形式表示，任一状态的价值可由其它状态价值得到，因此求解价值可以使用如下的Bellman方程，该方程记录了价值函数的内在关系：
可以通过雅克比迭代法求解Bellman方程。
3.迷宫寻宝问题介绍
在迷宫寻宝问题中有一个5×5的棋盘，超级玛丽位于棋盘左上角的方格内，并且可以朝上、下、左、右四个方向移动，每回合移动一次记为1步；宝藏位于棋盘最下层的中间方格内，在游戏中玩家控制超级玛丽进行移动，超级玛丽找到宝藏则游戏结束(即超级玛丽和宝藏位于同一个方格)，游戏的目标就是让超级玛丽以最少的步数找到宝藏。
超级玛丽到达宝藏的位置可以有很多种走法，但哪一种方法最省力呢？当然我们用肉眼很快便能找出最佳的走法，但计算机是怎样实现的呢？接下来我们尝试使用强化学习的方法使超级玛丽找到最佳的行走策略。
4.形式化为MDP问题
使用强化学习解决上述问题，需要先将问题转化为MDP的形式，对于上述的迷宫寻宝问题我们分别定义它的状态空间S，动作空间A，奖励集合R，转移关系P以及折扣因子γ如下：
状态空间S：
宝藏的位置是不变的，因此在游戏过程中只有超级玛丽的位置在变化，将其位置编码为0～24。
# 状态0~24
import numpy as np
states = np.arange(25)
states
动作空间：
超级玛丽的四种动作，向上、向右、向下、向左分别用0、1、2、3表示。
# 动作0、1、2、3,分别表示向上、向右、向下、向左
actions = np.arange(4)
actions
奖励R：
本问题中，转移到终止状态22（宝藏位置）获得的奖励记为0，转移到其余状态获得的奖励均记为-1。
# 奖励
rewards = -1 * np.ones(25)
rewards[22] = 0
rewards
折扣因子γ ：设为0.9
# 奖励折扣因子
gamma = 0.9状态动作转移关系：
- 在游戏中给定动作，当前状态以概率1转移到下一状态，例如状态12，选择向上动作，只能转移到状态7，选择向下动作，只能转移到状态17。
- 若执行某一动作会使超级玛丽碰撞棋盘边缘，则保持当前状态不变，并获得-1单位的奖励，例如状态20，选择向左动作，将继续停留在状态20，并获得-1单位的奖励。
# 定义状态动作转移，传入当前状态和执行的动作，返回当前状态下执行动作得到的转移概率、下一状态和奖励
def p_state_reward(state, action):
# 向上移动
if action == 0:
# 状态0,1,2,3,4选择向上移动会保持当前状态不变
if state in range(5):
return ((1, state, -1))
# 其它状态选择向上动作以概率1转移到下一状态
else:
return ((1, state-5, -1))
# 向下移动
if action == 2:
# 状态20,21,22,23,24,25选择向下移动会保持当前状态不变
if state in range(20, 25):
return ((1, state, -1))
# 状态17选择向下动作会转移到终止状态22
if state == 17:
return ((1, 22, 0))
# 其它状态选择向下动作以概率1转移到下一状态
else:
return ((1, state+5, -1))
# 向左移动
if action == 3:
# 状态0,5,10,15,20选择向左移动会保持当前状态不变
if state in np.arange(0,25,5):
return ((1, state, -1))
# 状态23选择向左动作会转移到终止状态22
if state == 23:
return ((1, 22, 0))
# 其它状态选择向下动作以概率1转移到下一状态
else:
return ((1, state-1, -1))
# 向右移动
if action == 1:
# 状态4,9,14,19,24选择向右动作会离开棋盘
if state in np.arange(4,29,5):
return ((1, state, -1))
# 状态21选择向右动作会转移到终止状态22
if state == 21:
return ((1, 22, 0))
# 其它状态选择向右动作以概率1转移到下一状态
else:
return ((1, state+1, -1))5.使用策略迭代进行求解
策略迭代是一种动态规划算法，包含策略评估（policy evaluation）和策略提升（policy improvement）两部分，其基本思想是初始化一个策略𝜋，通过不断重复策略评估和策略提升的过程，得到最佳策略𝜋*。
策略评估是指求解给定策略𝜋对应的价值函数V𝜋(𝑠)，由于已知Pa(𝑠,𝑠')与Ras，所以可以由
列出所有V𝜋(𝑠)对应的方程，它是个系数完全已知的线性方程组，使用雅克比迭代法求解方程组即可得到V𝜋(s)。
策略提升是指可以通过计算出的V𝜋(𝑠)进一步得到更好的策略， 对于每一个状态𝑠，分别计算其所有可能动作带来的累积期望奖励，选择最大累积期望奖励对应的动作更新策略：
重复策略评估（计算出𝜋对应V的）和策略提升（用V𝜋(𝑠)更新𝜋），直到算法收敛，其流程如下：
我们根据上述方法实现策略迭代，首先初始化一个策略，所有状态都选择向下动作。
# 随机初始化一个策略，全部向下
random_policy = 2 *np.ones(len(states))
random_policy
# 设置迭代次数
n = 1000定义一个函数计算策略下的状态价值，目的是为了进行策略评估。首先初始化每个状态的策略下价值为0，并设定一个阈值，用于判断策略下价值的更新程度，以便在收敛时及时停止循环，然后建立一个列表保存每次迭代中更新的策略下价值，最后遍历所有状态，根据策略下价值的计算公式迭代求解。
# 策略评估：计算策略下状态的价值
def compute_value_function(policy, gamma):
## 设置阈值
threshold = 1e-10
# 初始化每个状态的价值
value_table = np.zeros(len(states))
while True:
# 创建每次迭代更新的状态价值表
update_value_table = np.copy(value_table)
## 遍历所有状态
for state in states:
## 选择当前策略下当前状态所对应的动作
action = policy[state]
## 返回当前状态下执行动作得到的转移概率、下一状态和奖励
trans_prob, next_state, reward = p_state_reward(state, action)
## 计算策略下状态价值
value_table[state] = reward + gamma * trans_prob * update_value_table[next_state]
## 价值表前后两次更新之差小于阈值时停止循环
if np.sum((np.fabs(update_value_table - value_table))) <= threshold:
break
return value_table定义策略提升函数，目的是为了更新策略。先创建空数组保存改进的策略，接着遍历所有状态，计算每个状态下执行不同动作的价值，最后选取价值最大的动作更新策略。
# 策略提升：更新策略
def next_best_policy(value_table, gamma):
## 创建空数组保存改进的策略
policy = np.zeros(len(states))
for state in states:
## 创建列表存储当前状态下执行不同动作的价值
action_table = np.zeros(len(actions))
## 遍历所有动作
for action in actions:
## 返回当前状态-动作下一步的状态、转移概率和奖励
trans_prob, next_state, reward = p_state_reward(state, action)
## 计算当前状态下执行当前动作的价值
action_table[action] = reward + gamma * trans_prob * value_table[next_state]
## 策略提升：选取动作值最大的动作更新策略
policy[state] = np.argmax(action_table)
return policy 最后定义策略迭代函数，进行1000次迭代，每次迭代中，首先进行策略评估，然后进行策略提升，最后判断更新的策略与之前是否有变化，若没有变化，则迭代结束。
# 建立策略迭代函数
def policy_iteration(random_policy, gamma, n):
## 进行迭代
for i in range(n):
## 策略评估：得到各状态的价值
new_value_function = compute_value_function(random_policy, gamma)
## 策略提升：选取动作值最大的动作更新策略
new_policy = next_best_policy(new_value_function, gamma)
## 对当前策略进行判断
if np.all(random_policy == new_policy):
print('策略迭代结束，迭代次数为%d'%(i+1))
break
## 替换为当前最佳策略
random_policy = new_policy
return new_policy 开始迭代，完成后输出最佳策略。
best_policy = policy_iteration(random_policy, gamma, n)
print(best_policy)
通过最佳策略，我们可以得到最佳行动路线。
# 创建最佳路线列表，起始位置一定在状态0
best_route = [0]
next_state = 0
while True:
# 通过最佳策略求解当前状态下执行最优动作所转移到的下一个状态
_, next_state, _ = p_state_reward(next_state, best_policy[next_state])
# 将下个状态加入最佳路线列表
best_route.append(next_state)
# 转移到终止状态，停止循环
if next_state == 22:
break
print('最佳路线：',best_route)
由上图可以看到最佳行动路线为(0→1→2→7→12→17→22)，并且步数为6。
6.使用值迭代进行求解
在上述的策略迭代中需要维护策略的更新，并且需要一个单独的循环迭代处理策略评估，这会产生很大的计算量，下边我们尝试另一种求解方法那就是值迭代方法，它同样是一种动态规划算法，核心思想是迭代过程中只更新值函数，迭代完成后通过构造最佳策略，其算法流程如下：
首先初始化状态价值表，设每个状态的价值为0，之后创建空数组保存最佳策略，接着利用雅克比迭代法进行1000次值迭代，每次迭代中判断价值表前后两次更新之差是否小于阈值，若小于则认为迭代收敛，停止迭代，最后利用求出的每个状态的价值得到最佳策略。
# 初始化状态价值表
value_table = np.zeros(len(states))
# 定义值迭代函数
def value_iteration(value_table, gamma, n):
## 设置阈值
threshold = 1e-20
# 创建数组保存策略
policy = np.zeros(len(states))
# 进行迭代
for i in range(n):
# 创建每次迭代更新的状态价值表
update_value_table = np.copy(value_table)
# 遍历所有状态
for state in states:
# 创建空的动作价值列表
action_value = np.zeros(len(actions))
# 遍历所有动作
for action in actions:
## 返回当前状态-动作下一步的状态、转移概率和奖励
trans_prob, next_state, reward = p_state_reward(state, action)
## 计算动作的累积期望奖励
action_value[action] = reward + gamma * trans_prob * update_value_table[next_state]
# 更新状态值表
value_table[state] = max(action_value)
# 记录当前最佳策略
policy[state] = np.argmax(action_value)
## 价值表前后两次更新之差小于阈值时停止循环
if np.sum((np.fabs(update_value_table - value_table))) <= threshold:
print('值迭代结束，迭代次数为%d'%(i+1))
break
return policy进行值迭代并输出最佳策略。
best_policy_value = value_iteration(value_table, gamma, n)
print(best_policy_value)
由最佳策略得到最佳路线。
best_route_value = [0]
next_state = 0
while True:
_, next_state, _ = p_state_reward(next_state, best_policy_value[next_state])
best_route_value.append(next_state)
if next_state == 22:
break
print('最佳路线：',best_route_value)
由上图可以看出最佳行动路线为(0→1→2→7→12→17→22)，且步数为6，通过值迭代我们也得到了最佳策略。
6.总结
在本案例中，我们将迷宫寻宝问题形式化为一个MDP问题，并使用策略迭代和值迭代两种方法得到问题的最佳策略。从结果可以看到，策略迭代和值迭代得到的最佳策略是一致的。由最佳策略得到的行动路线不仅移动步数最少，而且执行动作的个数也是最少的，可以说是一个最佳的选择。策略迭代比值迭代用了更少的迭代次数。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
