动态规划在强化学习中的应用

基于动态规划的算法优良 ：策略迭代和价值迭代。

策略迭代分为策略评估和策略提升，使用贝尔曼期望方程得到一个策略的状态价值函数；价值迭代直接使用贝尔曼最优方程进行动态规划，得到最终的最优状态价值。

基于动态规划的算法需要知道环境的状态转移函数和奖励函数，不需要通过智能体与环境的大量交互中学习，直接用动态规划求解状态价值函数，只适用于有限马尔可夫决策过程，即状态空间和动作空间是离散且有限的。

悬崖漫步环境

与上一节介绍的算法题类似，要求智能体从起点出发，避开悬崖，走到终点，且智能体无法越过边界。智能体走到悬崖，或者到达目标时，结束动作并回到起点。智能体每个状态可以采取四种动作：上下左右，智能体每走一步的奖励是 −1，掉入悬崖的奖励是 −100。

我们使用代码，定义一个4×12的环境

import copy
class CliffWalkingEnv:
    def __init__(self, ncol=12,nrow=3):
        self.ncol = ncol
        self.nrow = nrow
        # 转移矩阵P[state][action] = [(p, next_state, reward, done)]包含下一个状态和奖励
        self.P=self.createP()
        
    def createP(self):
        # 初始化，每一个动作对应四个值
        P=[[[] for j in range(4) ] for i in range(self.ncol*self.nrow)]
        # 定义四种动作，一次为上下左右，坐标系原点为(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:
                        # 如果为3行，那么i=2，i*self.ncol+j表示智能体所在的位置
                        # 相当于将棋盘格展开成一条线，下标为i*self.ncol+j
                        # 下一个状态还是本位置
                        P[i*self.ncol+j][a]=[(1,i*self.ncol+j,0,True)]
                        continue
                    # 其他位置
                    # max(0,j+change[a][0])是为了防止越界，防止下一个位置小于0
                    # 如果判断为越界，则取0
                    # min(self.ncol-1,max(0,j+change[a][0]))
                    # 防止数值大于self.ncol-1，如果大于self.ncol-1，则取self.ncol-1
                    nextX=min(self.ncol-1,max(0,j+change[a][0]))
                    nextY=min(self.nrow-1,max(0,i+change[a][1]))
                    nextState=nextY*self.ncol+nextX
                    reward=-1
                    done=False
                    # 下一个位置在悬崖或者终点
                    if nextY==self.nrow-1 and nextX>0:
                        done = True
                        #如果下一个位置不是终点（即是悬崖）
                        if nextX != self.ncol-1:
                            reward = -100
                    P[i*self.ncol+j][a]=[(1,nextState,reward,done)]
        return P