【强化学习-读书笔记】动态规划（策略评估、价值迭代、策略迭代算法）

参考 
Reinforcement Learning, Second Edition  
An Introduction 
By Richard S. Sutton and Andrew G. Barto

动态规划 (Dynamic Programming, DP) 是一类优化方法，在给定一个用马尔可夫决策过程 (MDP) 描述的完备环境模型的情况下，其可以计算最优的策略。

Recall: Bellman Equation

我们知道 v π v_\pi vπ​的贝尔曼方程可以写作如下形式：
v π ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] v_\pi(s)=\sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r+\gamma v_{\pi}(s')] vπ​(s)=a∑​π(a∣s)s′,r∑​p(s′,r∣s,a)[r+γvπ​(s′)]
如何求解最优策略 v ∗ ( s ) v_*(s) v∗​(s)呢？
实际上对于每一个可能的状态 s ∈ S s\in \mathcal{S} s∈S，都有这样的一个方程，因此可以通过解这样一组贝尔曼方程组来直接求解出 v ∗ ( s ) v_*(s) v∗​(s)。但是问题在于许多场景的状态空间很大，因此难以直接利用解方程的方式来求。因此我们考虑迭代的方式。

Example Task —— 最短路径任务

在这里插入图片描述
为了说明以下三个不同的算法，我们引入一个 exmaple task。 智能体的目标是找到从任意一个点出发怎么走才能最快到达图上的两个终止状态。每走一步， r = − 1 r=-1 r=−1；如果出界，就保持原来的状态不动。
我们希望智能体能够找到最优价值函数 v ∗ ( s ) v_*(s) v∗​(s) 或者最优策略 π ∗ ( a ∣ s ) \pi_*(a|s) π∗​(a∣s)（以矩阵表示）
在这里插入图片描述

策略评估算法

策略评估（Policy Evaluation）算法的核心思想在于，如果存在最优价值函数 v ∗ ( s ) v_*(s) v∗​(s)，那么 v ∗ ( s ) v_*(s) v∗​(s)实际上就是贝尔曼方程的一个不动点，我们从任意一个 V 0 V_0 V0​出发，不断迭代贝尔曼方程，最终收敛到的价值函数就是最优价值函数。 Δ \Delta Δ记录前后两个价值函数矩阵的最大差值，当差值足够小，就认为找到了 v ∗ ( s ) v_*(s) v∗​(s)
在这里插入图片描述

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
plt.rcParams['font.sans-serif'] = ['Microsoft YaHei']
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号

STOP = np.array([
    [1,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,1]
])
V = np.array([
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0]
]).astype('float')
V_new = V.copy()
actions = [(0,1),(1,0),(0,-1),(-1,0)]
gamma = 1.0
states = [(i,j) for i in range(4) for j in range(4)]
print(states)

for step in range(100):                                        # 对应贝尔曼方程

    for state in states:                                       # for s \in S
        if STOP[state]:
            continue
        
        v = V[state]
        res = 0
        for action in actions:                                 # \sum a
            s_next = [action[0]+state[0], action[1]+state[1]]

            # 处理边界动作
            if s_next[0]<0:
                s_next[0]=0
            if s_next[0]>3:
                s_next[0]=3
            if s_next[1]<0:
                s_next[1]=0
            if s_next[1]>3:
                s_next[1]=3
            # print(state,'a:',action,'-> s',s_next)
            r = -1                                             # 每走一步奖励固定是 -1
            res += 1/4 * (r + gamma * V[tuple(s_next)])        # \pi(a|s) [r + \gamma V(s)]
        
        V_new[state] = res
    
    delta = (abs(V_new-V)).max()

    V = V_new.copy()

    if delta < 0.01:
        plt.figure(figsize=(3,2))
        sns.heatmap(V,annot=True,cmap='Blues_r')
        plt.title('$V_\pi(s)$ @ step={}  $\Delta$={:0.4f}'.format(step,delta),color='green')
        plt.xlabel('x66ccff')
        plt.ylabel('迭代策略评估')
        plt.show()
        print('break at delta={:.4f}, step={}'.format(delta, step))
        break

    elif step <= 3:
        plt.figure(figsize=(3,2))
        sns.heatmap(V,annot=True,cmap='Blues_r')
        plt.title('$V_\pi(s)$ @ step={}  $\Delta$={:0.4f}'.format(step,delta),color='black')
        plt.ylabel('迭代策略评估')
        plt.show()

请添加图片描述
请添加图片描述
请添加图片描述
请添加图片描述
请添加图片描述
策略评估使用了长达 88 步才达到收敛

价值迭代（Value Iteration）

价值迭代仅仅是将贝尔曼最优方程变为一条更新规则。另外，除了从达到最大值的状态更新以外，价值迭代与策略评估的更新公式几乎完全相同

价值迭代（v 更新取 max）和策略评估（不动点）的区别仅仅在于多了一个取所有后继状态的价值的 max ⁡ \max max ，而不是平均（期望）价值。
在这里插入图片描述

STOP = np.array([
    [1,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,1]
])
V = np.array([
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0]
]).astype('float')
V_new = V.copy()
actions = [(0,1),(1,0),(0,-1),(-1,0)]
gamma = 1.0
states = [(i,j) for i in range(4) for j in range(4)]
print(states)

for step in range(100):                                        # 对应贝尔曼方程

    for state in states:                                       # for s \in S
        if STOP[state]:
            continue
        
        v = V[state]
        # res = 0
        res_a_ls = []                                          # <------ 修改的地方
        for action in actions:                                 # \sum a
            s_next = [action[0]+state[0], action[1]+state[1]]

            # 处理边界动作
            if s_next[0]<0:
                s_next[0]=0
            if s_next[0]>3:
                s_next[0]=3
            if s_next[1]<0:
                s_next[1]=0
            if s_next[1]>3:
                s_next[1]=3
            # print(state,'a:',action,'-> s',s_next)
            r = -1                                             # 每走一步奖励固定是 -1
            # res += 1/4 * (r + gamma * V[tuple(s_next)])        # \pi(a|s) [r + \gamma V(s)]
            res_a = (r + gamma * V[tuple(s_next)])               # <------ 修改的地方
            res_a_ls.append(res_a)                               # <------ 修改的地方
        
        V_new[state] = max(res_a_ls)                             # <------ 修改的地方 
    
    delta = (abs(V_new-V)).max()

    V = V_new.copy()

    if delta < 0.01:
        plt.figure(figsize=(3,2))
        sns.heatmap(V,annot=True,cmap='Blues_r')
        plt.title('$V_\pi(s)$ @ step={}  $\Delta$={:0.4f}'.format(step,delta),color='green')
        plt.xlabel('x66ccff')
        plt.ylabel('价值迭代')
        plt.show()
        print('break at delta={:.4f}, step={}'.format(delta, step))
        break

    elif step <= 3:
        plt.figure(figsize=(3,2))
        sns.heatmap(V,annot=True,cmap='Blues_r')
        plt.title('$V_\pi(s)$ @ step={}  $\Delta$={:0.4f}'.format(step,delta),color='black')
        plt.ylabel('价值迭代')
        plt.show()

请添加图片描述
请添加图片描述
请添加图片描述
请添加图片描述
注意到，价值迭代只用了3步就达到了收敛，比策略评估算法快得多。

策略迭代（Policy Iteration）

策略迭代与前两者不同，不仅仅维护 V π ( s ) V_\pi(s) Vπ​(s)矩阵，还维护表示策略的 π ( a ∣ s ) \pi(a|s) π(a∣s)矩阵，两者交替进行更新。

其分为两个阶段：

  • 策略评估（根据最优动作 π ( a ∣ s ) \pi(a|s) π(a∣s) 更新 V π V_\pi Vπ​，而不是求平均）
  • 策略改进（根据 V π V_\pi Vπ​ 更新每一个状态 s s s 的最优动作 π ( a ∣ s ) \pi(a|s) π(a∣s)）

因此策略迭代相当于在策略评估算法（但没有求平均，而是 π \pi π直接给出 a a a）的基础上，加了一个策略改进的部分。
在这里插入图片描述
在这里插入图片描述

STOP = np.array([
    [1,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,1]
])
V = np.array([
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0]
]).astype('float')
V_new = V.copy()
actions = [(0,1),(1,0),(0,-1),(-1,0)]
gamma = 1.0
states = [(i,j) for i in range(4) for j in range(4)]
print(states)

# 策略迭代新增
np.random.seed(42)
Policy = np.random.randint(0,4,16).reshape(4,4) # 随机初始化策略
Policy

array([[2, 3, 0, 2],
[2, 3, 0, 0],
[2, 1, 2, 2],
[2, 2, 3, 0]])

for step in range(100):                                        # 对应贝尔曼方程

    ######################## a) 先根据策略Policy进行价值更新

    for state in states:                                       # for s \in S
        if STOP[state]:
            continue
        
        v = V[state]
        res = 0
        # res_a_ls = []                             # <------修改的地方
        # for action in actions:                    # <------修改的地方  # 不需要 for a
        action = actions[Policy[state]]             # <------修改的地方  # 根据 Policy 选择a
        s_next = [action[0]+state[0], action[1]+state[1]]

        # 处理边界动作
        if s_next[0]<0:
            s_next[0]=0
        if s_next[0]>3:
            s_next[0]=3
        if s_next[1]<0:
            s_next[1]=0
        if s_next[1]>3:
            s_next[1]=3
        r = -1                                             # 每走一步奖励固定是 -1
        res = (r + gamma * V[tuple(s_next)])        # \pi(a|s) [r + \gamma V(s)]
        # res_a = (r + gamma * V[tuple(s_next)])     # <------修改的地方
        # res_a_ls.append(res_a)                     # <------修改的地方
        # V_new[state] = max(res_a_ls)               # <-------修改的地方
        V_new[state] = res

    delta = (abs(V_new-V)).max()

    V = V_new.copy()


    ############################ b) 对每一个状态更新策略

    for state in states:
        res_ls = []
        for i in range(4):

            s_next = [actions[i][0] + state[0] , actions[i][1] + state[1]]
            # 处理边界动作
            if s_next[0]<0:
                s_next[0]=0
            if s_next[0]>3:
                s_next[0]=3
            if s_next[1]<0:
                s_next[1]=0
            if s_next[1]>3:
                s_next[1]=3
            res_a = (r + gamma * V[tuple(s_next)])
            res_ls.append(res_a)
        best_action_index = np.argmax(res_ls)
        Policy[state] = best_action_index


    if delta < 0.01:
        plt.figure(figsize=(3,2))
        sns.heatmap(V,annot=True,cmap='Blues_r')
        plt.title('$V_\pi(s)$ @ step={}  $\Delta$={:0.4f}'.format(step,delta),color='green')
        plt.xlabel('x66ccff')
        plt.ylabel('策略迭代')
        plt.show()
        print('break at delta={:.4f}, step={}'.format(delta, step))
        break

    elif step <= 3:
        plt.figure(figsize=(3,2))
        sns.heatmap(V,annot=True,cmap='Blues_r')
        plt.title('$V_\pi(s)$ @ step={}  $\Delta$={:0.4f}'.format(step,delta),color='black')
        plt.ylabel('策略迭代')
        plt.show()

请添加图片描述
请添加图片描述
请添加图片描述
请添加图片描述

策略迭代也用了3步达到最优。这三种方法最终得到的 V π V_\pi Vπ​都不同，但是都是最优策略（看图容易验证，只要往浅色区域走，总能最快到达终止位置）

异步动态规划

上面的三种算法都是完全遍历完所有状态 s s s，再进行策略/价值的更新的（实际上也就是存储了新旧两个矩阵）。关键问题在于，遍历所有状态很多情况下是不可能的，比如围棋的合法状态空间大概为 1 0 170 10^{170} 10170，这是没法遍历的。

异步 DP 就是选择性地更新某些状态，从而增加了算法的灵活性。可以选择任意的状态 s s s进行更新，有的状态可能已经更新了很多次，但是有的状态甚至可以没有更新。

异步 DP 的优势在于

  • 有可能减少计算量，并不需要完全遍历所有状态
  • 有可能多考虑一些关键状态，从而提高效率

广义策略迭代（GPI）

广义策略迭代 (GPI) 指让策略评估和策略改进相互作用的一般思路
策略迭代示意图

策略迭代包含两个过程：

  • 用 π \pi π 更新 V V V （ a = arg ⁡ max ⁡ a π ( a ∣ s ) , a → s ′ → V ( s ′ ) a=\arg \max_a \pi(a|s), a \to s' \to V(s') a=argmaxa​π(a∣s),a→s′→V(s′)）
  • 用 V V V 更新 π \pi π（选择 max r + γ V ( s ′ ) r+\gamma V(s') r+γV(s′) 的动作）

这两个过程交替进行。
广义策略迭代示意图

但是在广义策略迭代中，交替不是必须的，也不是必须要更新所有状态

GPI 允许在某些特殊情况下甚至有可能仅有一个状态在评估流程中得到更新（用 π \pi π 更新 V V V），然后马上就返回到改进流程（用 V V V 更新 π \pi π）。

几乎所有的强化学习方法都可以被描述为 GPI 。也就是说，几乎所有方法都包含明确定义的策略和价值函数，且如右图所示，策略总是基于特定的价值函数进行改进，价值函数也始终会向对应特定策略的真实价值函数收敛。GPI 中，我们也可以让每次走的步子小一点，部分地实现其中一个目标。无论是哪种情况，尽管没有直接优化总目标．但评估和改进这两个流程结合在一起，就可以最终达到最优的总目标

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/248200.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Jeecg Boot 3 - 保姆级】第1节 docker + redis + nginx + redis一键安装启动

【Jeecg Boot 3 - 保姆级】第1节 docker + redis + nginx + redis一键安装启动

一、前言 ▶ JEECG-BOOT 开源版难以吃透的原因 ▶ 为了针对上面痛点&#xff0c;笔者做了如下安排 ▶ 你能收获什么 二、效果(第一节效果) ▶ 启动后端 &#xff1e; 日志 &#xff1e; 接口文档 ▶ 启动前端 三、准备工作 四、实战 ▶ 1、服务器安装 Stag…
阅读更多...
RF模块是如何工作的？

RF模块是如何工作的？

射频&#xff08;RF&#xff09;模块使用无线电频率工作&#xff0c;这个频率范围在30kHz到300kHz之间变化。 在这个射频系统中&#xff0c;数字数据被表示为载波波幅度的变化。这种调制类型是振幅移位键。 这个射频模块是射频发射器和接收器的组合&#xff0c;发射器接收器对的…
阅读更多...
读书笔记-《数据结构与算法》-摘要6[快速排序]

读书笔记-《数据结构与算法》-摘要6[快速排序]

快速排序 核心&#xff1a;快排是一种采用分治思想的排序算法&#xff0c;大致分为三个步骤。 定基准——首先随机选择一个元素最为基准划分区——所有比基准小的元素置于基准左侧&#xff0c;比基准大的元素置于右侧递归调用——递归地调用此切分过程 快排的实现与『归并排…
阅读更多...
伪距单点定位概念与原理、算例分析

伪距单点定位概念与原理、算例分析

目录 一、概念与原理 1.伪距观测值 2.为何被称为"伪距" ? 3.单点定位的概念 4.伪距单点定位的原理 5.伪距单点定位的优缺点 二、伪距观测方程 三、伪距观测方程线性化 1.泰勒级数展开 2.得到线性化后的观测方程 3.在某历元接收机同时观测n颗卫星&#xf…
阅读更多...
视频号小店需要缴纳保证金吗？保证金缴纳标准，不懂的快来看！

视频号小店需要缴纳保证金吗？保证金缴纳标准，不懂的快来看！

我是电商珠珠 入驻视频号小店&#xff0c;需要缴纳保证金吗&#xff1f;具体缴纳多少&#xff1f;... 这是想要入驻视频号小店的热门话题&#xff0c;今天我就来给大家一一讲明白。 想要入驻视频号小店&#xff0c;就必须要缴纳保证金。保证金是平台为了约束商家的行为&…
阅读更多...
递推与递归练习题

递推与递归练习题

公众号&#xff1a;编程驿站 题目来源于洛谷&#xff01; 数楼梯 题目描述 楼梯有 N 阶&#xff0c;上楼可以一步上一阶&#xff0c;也可以一步上二阶。 编一个程序&#xff0c;计算共有多少种不同的走法。 输入格式 一个数字&#xff0c;楼梯数。 输出格式 输出走的方…
阅读更多...
智能优化算法应用：基于阴阳对算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于阴阳对算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于阴阳对算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于阴阳对算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.阴阳对算法4.实验参数设定5.算法结果6.参考文…
阅读更多...
PR模板,复古怀旧电影效果视频制作PR项目工程文件

PR模板,复古怀旧电影效果视频制作PR项目工程文件

Premiere复古怀旧电影效果视频制作pr模板项目工程文件下载 这个PR模板以复古城市印象电影质感为特色&#xff0c;结合了电影和数字故障效果。包含6个场景。可以编辑文本、添加媒体和自定义颜色。包含视频教程。4K版本。不需要任何插件。 软件支持&#xff1a;PR2022 | 分辨率&a…
阅读更多...
人类简史作者警告：人工智能或将夺取世界主宰 / 机器学习加速新药研发，AI的崭新角色｜魔法半周报

人类简史作者警告：人工智能或将夺取世界主宰 / 机器学习加速新药研发，AI的崭新角色｜魔法半周报

我有魔法✨为你劈开信息大海❗ 高效获取AIGC的热门事件&#x1f525;&#xff0c;更新AIGC的最新动态&#xff0c;生成相应的魔法简报&#xff0c;节省阅读时间&#x1f47b; &#x1f525;资讯预览 机器学习加速新药研发&#xff0c;AI的崭新角色 2022年中国研发经费总投入突…
阅读更多...
RocketMQ源码 Broker-SubscriptionGroupManager 订阅组管理组件源码分析

RocketMQ源码 Broker-SubscriptionGroupManager 订阅组管理组件源码分析

前言 SubscriptionGroupManager 继承了ConfigManager配置管理组件&#xff0c;拥有将内存数据持久化到磁盘文件subscriptionGroup.json的能力。它主要负责维护所有消费组在内存中的订阅数据。 源码版本&#xff1a;4.9.3 源码架构图 核心数据结构 主要的数据结构比较简单&am…
阅读更多...
CMS—评论功能设计

CMS—评论功能设计

一、需求分析 1.1、常见行为 1.敏感词过滤 2.新增评论&#xff08;作品下、评论下&#xff09; 3.删除评论&#xff08;作品作者、上级评论者、本级作者&#xff09; 4.上级评论删除关联下级评论 5.逻辑状态变更&#xff08;上线、下线、废弃...&#xff09; 6.上逻辑状态变更…
阅读更多...
Java报错-Non-terminating decimal expansion； no exact representable decimal result

Java报错-Non-terminating decimal expansion； no exact representable decimal result

1. 背景 在使用 BigDecimal 的 divide() 对两个数相除时&#xff0c;报了如题的错误。 public class Test {public static void main(String[] args) {BigDecimal b1 new BigDecimal(1);BigDecimal b2 new BigDecimal(3);System.out.println(b1.divide(b2)); // Sys…
阅读更多...
jupyter notebook介绍、安装和使用

jupyter notebook介绍、安装和使用

简介 Jupyter Notebook是基于网页的用于交互计算的应用程序。其可被应用于全过程计算&#xff1a;开发、文档编写、运行代码和展示结果。——Jupyter Notebook官方介绍 简而言之&#xff0c;Jupyter Notebook是以网页的形式打开&#xff0c;可以在网页页面中直接编写代码和运…
阅读更多...
Shell三剑客：文本过滤工具——grep

Shell三剑客：文本过滤工具——grep

一、简介&#xff1a;过滤&#xff0c;查找文档中的内容 二、分类 grepegrep——扩展支持正则\w所有字母与数字&#xff0c;称为字符[a-zA-Z0-9] l[a-zA-Z0-9]*ve l\w*ve\W所有字母与数字之外的字符&#xff0c;称为非字符 love[^a-zA-Z0-9] love\W\b词边界 \<love\>…
阅读更多...
力扣每日一题day32[104. 二叉树的最大深度]

力扣每日一题day32[104. 二叉树的最大深度]

给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 2&#xff1a; 输入&#xff1a;root [1,null,2] 输出…
阅读更多...
winform中也可以这样做数据展示✨

winform中也可以这样做数据展示✨

1、前言 在做winform开发的过程中&#xff0c;经常需要做数据展示的功能&#xff0c;之前一直使用的是gridcontrol控件&#xff0c;今天想通过一个示例&#xff0c;跟大家介绍一下如何在winform blazor hybrid中使用ant design blazor中的table组件做数据展示。 2、效果 先来…
阅读更多...
MYSQL练题笔记-子查询-换座位

MYSQL练题笔记-子查询-换座位

一、题目相关内容 1&#xff09;相关的表和题目 2&#xff09;帮助理解题目的示例&#xff0c;提供返回结果的格式 二、自己初步的理解 没啥思路&#xff0c;我还没做过交换的这种题&#xff0c;所以我觉得这类交换的题以后值得做一个合集&#xff0c;是有点灵活度在里面的&a…
阅读更多...
computed 和 watch 的奇妙世界：让数据驱动你的 Vue 应用(上)

computed 和 watch 的奇妙世界：让数据驱动你的 Vue 应用(上)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
海思平台isp之ccm标定

海思平台isp之ccm标定

文章目录 1、raw图采集2、ccm标定2.1、标定参数配置2.2、标定效果优化2.2.1、优化方式一2.2.2、优化方式二2.2.3、优化方式三1、raw图采集 raw图采集步骤及标准，请参考文章 《海思平台isp之ccm标定》。2、ccm标定 2.1、标定参数配置 （1）图像基本参数 （2）黑电平设置 (…
阅读更多...
VR播控系统深耕VR教学领域，助力开启未来新课堂

VR播控系统深耕VR教学领域，助力开启未来新课堂

作为提升教育质量的技术之一&#xff0c;VR技术已经逐渐成为培养新一代人才、提升教学质量的重要方式&#xff0c;相比于传统教育&#xff0c;VR技术在教学方面的应用&#xff0c;所带来的变化和效果提升都是非常明显的&#xff0c;尤其是VR播控系统的上线&#xff0c;作为VR教…
阅读更多...
最新文章

Copyright @ 2022~2023