阐述、总结【动手学强化学习】章节内容的学习情况，复现并明白代码。
一、什么是动态规划？
1.1概念
**动态规划（dynamic programming）**是程序设计算法中非常重要的内容，能够高效解决一些经典标题，比方背包标题和最短路径规划。动态规划的基本思想是将待求解标题分解成多少个子标题，先求解子标题，然后从这些子标题的解得到目标标题的解。动态规划会保存已解决的子标题的答案，在求解目标标题的过程中，需要这些子标题答案时就可以直接利用，避免重复计算。
基于动态规划的强化学习算法主要有两种：一是策略迭代（policy iteration），二是代价迭代（value iteration）。
1.2实用条件
需要“白盒”情况（model-based）！！！基于动态规划的这两种强化学习算法要求事先知道情况的状态转移函数和奖励函数，也就是需要知道整个马尔可夫决议过程。策略迭代和代价迭代通常只实用于有限马尔可夫决议过程，即状态空间和动作空间是离散且有限的。
二、算法示例
2.1标题建模
CliffWalking悬崖漫步情况
- 目标：要求一个智能体从起点出发，避开悬崖行走，最终到达目标位置。
根据MDP过程举行建模：
- 状态空间：4×12 的网格世界，每一个网格表现一个状态。起点是左下角的状态，目标是右下角的状态。
- 动作空间：可以采取 4 种动作：上、下、左、右。
- 扣头因子：取0.9。
- 奖励函数：智能体采取动作后触碰到边界墙壁则状态不发生改变，否则就会相应到达下一个状态。情况中有一段悬崖，智能体掉入悬崖或
到达目标状态都会竣事动作并回到起点，也就是说掉入悬崖或者达到目标状态是停止状态。智能体每走一步的奖励是 −1，掉入悬崖的奖励是−100。
- 状态转移函数：
2.2策略迭代（policyiteration）算法
2.2.1伪代码
- 算法流程简述：
①初始化：根据情况，初始化各state的state value，一般设置为0；policy同时也初始化，一般设置为每个state选取各action的概率相等
②代价评估（policy evaluation，PE）：循环迭代计算，究竟当前policy下稳态state value
③策略提拔（policy improvement）：依据当前statevalue值，根据情况模型（ p ( r ∣ s , a ) p(r|s,a) p(r∣s,a)、 p ( s ′ ∣ s , a ) p(s'|s,a) p(s′∣s,a)）计算各(s,a)对action value，并以greedy policy策略将各state中action value最大的值举行policy优化
④停止判定：判定最近两次policy是否相等，若是则停止算法输出policy，若否则重复实行②③步。
2.2.2完整代码
[code]# =============================================================================
#
# 悬崖漫步是一个非常经典的强化学习环境，它要求一个智能体从起点出发，避开悬崖行走，最终到达目标位置。
# state:如图 4-1 所示，有一个 4×12 的网格世界，每一个网格表示一个状态,智能体的起点是左下角的状态，目标是右下角的状态.
# action:智能体在每一个状态都可以采取 4 种动作：上、下、左、右。
# goal:如果智能体采取动作后触碰到边界墙壁则状态不发生改变，否则就会相应到达下一个状态。环境中有一段悬崖，智能体掉入悬崖或
# 到达目标状态都会结束动作并回到起点，也就是说掉入悬崖或者达到目标状态是终止状态。
# reward:智能体每走一步的奖励是 −1，掉入悬崖的奖励是−100。
# =============================================================================
import copy
class CliffWalkingEnv:
""" 悬崖漫步环境"""
def __init__(self, ncol=12, nrow=4):
self.ncol = ncol # 定义网格世界的列
self.nrow = nrow # 定义网格世界的行
# 转移矩阵P[state][action] = [(p, next_state, reward, done)]包含下一个状态和奖励
self.P = self.createP()
def createP(self):
# =============================================================================
# 转移矩阵P[a] = [(p, next_state, reward, done)]包含下一个状态和奖励
# p:s到next_state的状态转移概率，在这里都取1
# reward:s到next_state的即时奖励
# done：是否到达终点或悬崖
# =============================================================================
# 初始化
P = [[[] for j in range(4)] for i in range(self.nrow * self.ncol)]
# 4种动作, change[0]:上,change[1]:下, change[2]:左, change[3]:右。坐标系原点(0,0)
# 定义在左上角
change = [[0, -1], [0, 1], [-1, 0], [1, 0]]
for i in range(self.nrow):
for j in range(self.ncol):
for a in range(4):
# 位置在悬崖或者目标状态,因为无法继续交互,任何动作奖励都为0
if i == self.nrow - 1 and j > 0:
# 除了4行1列的元素的done状态都设置为True，其都为悬崖，除4行12列为终点
P[i * self.ncol + j][a] = [(1, i * self.ncol + j, 0,
True)]
continue
# 其他位置
next_x = min(self.ncol - 1, max(0, j + change[a][0]))
next_y = min(self.nrow - 1, max(0, i + change[a][1]))
next_state = next_y * self.ncol + next_x
reward = -1
done = False
# 下一个位置在悬崖或者终点
if next_y == self.nrow - 1 and next_x > 0:
done = True
if next_x != self.ncol - 1: # 下一个位置在悬崖
reward = -100
P[i * self.ncol + j][a] = [(1, next_state, reward, done)]
return P
class PolicyIteration:
""" 策略迭代算法 """
def __init__(self, env, theta, gamma):
self.env = env
self.v = [0] * self.env.ncol * self.env.nrow # 初始化价值为0
# |
