强化学习——学习笔记2

news/2024/7/14 19:09:31/文章来源:https://blog.csdn.net/qq_52302919/article/details/139267028

在上一篇文章中对强化学习进行了基本的概述,在此篇文章中将继续深入强化学习的相关知识。

一、什么是DP、MC、TD?

动态规划法(DP):动态规划法离不开一个关键词,拆分 ,就是把求解的问题分解成若干个子阶段,前一问题的结果就是求解后一问题的子结构。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
举一个简单的例子:
有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第n个月的兔子总数为多少?

对于这个问题,我们可以根据月份把问题划分为n个阶段,每个月的兔子数,都会等于前一个月的兔子数加上这个月新出生的兔子数,
所以 第n个月的兔子数=第n-1个月的兔子数+新出生的兔子数,而 新出生的兔子数=有繁殖能力的兔子数=两个月前的兔子数,即:第n个月的兔子数=第n-1个月的兔子数+第n-2个月的兔子数。
看着有点混乱?
再举一个例子:
有一个背包,可以装载重量为5kg的物品。
​ 有4个物品,他们的重量和价值如下。
​ 背包:载重5kg
​ 物品1
​ 重量: 1kg
​ 价值:¥3
​ 物品2
​ 重量:2kg
​ 价值:¥4
​ 物品3:
​ 重量: 3kg
​ 价值:¥5
​ 物品4
​ 重量:4kg
​ 价值:¥6
​ 那么请问,在不得超过背包的承重的情况下,将哪些物品放入背包,可以使得总价值最大?

对于上题,总重量是5kg,从四个物品中选,我们要求的问题就是:F(5,4)。
对于第四个物品就只有两种情况,我们可以选择选,或者是不选,不选的话就还是5kg,只从前面三个物品去选,F(5,3)。选的话就是还剩下1kg,从前面三个去选,F(1,3)
则有如下状态转移计算:
F ( 5 , 4 ) = m a x { F ( 1 , 3 ) + 6 , F ( 5 , 3 ) } F(5,4) = max \{ F(1,3) + 6, F(5,3) \} F(5,4)=max{F(1,3)+6,F(5,3)}

F ( W , N ) = m a x { F ( W − W n , N − 1 ) + V n , F ( W , N − 1 ) } F(W,N) =max \{F(W-W_n, N-1)+V_n,F(W,N-1)\} F(W,N)=max{F(WWn,N1)+Vn,F(W,N1)}(w是重量,n是从前n个去选, W n W_n Wn是第n个的重量, V n V_n Vn是第n个的价值)
当重量只剩下0kg的时候,就没有能够选择的物品了,最大价值就是0,所以F(0,n)=0,
当只是剩下的重量大于0,但是已经遍历到从前1个物品中选择时,那么能选择的物品就只有第一个,最大价值就是3,即F(n,1)=3。

从上面两个问题可以看出,动态规划一般只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。

动态规划算法一般分为以下4个步骤:
1、描述最优解的结构
2、递归定义最优解的值
3、按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础。
4、由计算出的结果构造一个最优解 //此步如果只要求计算最优解的值时,可省略

换言之,动态规划方法的最优化问题的两个要素:最优子结构性质,和子问题重叠性质

最优子结构
如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。意思就是,总问题包含很多个子问题,而这些子问题的解也是最优的。
重叠子问题
子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

如果已经理解了上文中的动态规划算法基本知识,我们就可以蒋动态规划算法应用到强化学习中了。

求解最优策略 v ∗ ( s ) v_∗(s) v(s)
在这里插入图片描述

1、最优策略可以通过最大化 q π ( s , a ) q_π(s,a) qπ(s,a)找到。
在上一篇文章中提到如下公式:
在这里插入图片描述
在这里插入图片描述
2、从上面两个公式中可以看出,若想 q π ( s , a ) q_π(s,a) qπ(s,a)最大,则需要 π ∗ ( a ∣ s ) π_∗(a|s) π(as)最大,也就是 π ∗ ( a ∣ s ) = 1 π_∗(a|s)=1 π(as)=1

结合上面两个理论可以得出下式:
在这里插入图片描述
同时在上一篇文章中提出下式:
在这里插入图片描述
综合以上两个公式我们最终得出:
在这里插入图片描述
回归到DP问题,相当于当知道奖励函数和状态转换函数时,便可以根据下一个状态的价值来更新当前状态的价值,意味着可以把计算下一个可能状态的价值当成一个子问题,而把计算当前状态的价值看做当前问题。
下面展示DP求解最优策略的算法流程
在这里插入图片描述
蒙特卡洛法(MC):也称为统计模拟方法,就是通过大量的随机样本来估算或近似真实值,比如近似估算圆的面经、近似定积分、近似期望、近似随机梯度。
有如下例子:
可以通过这个式子来近似计算:圆的面积/ 正方形的面积 = 圆中点的个数/正方形中点的个数
在这里插入图片描述
类似的,也可以用蒙特卡洛法来估计一个策略在一个马尔可夫决策过程中的状态价值。考虑到 一个状态的价值是它的期望回报,那么如果我们用策略在马尔科夫决策过程上采样很多条序列,然后计算从这个状态出发的回报再求其期望。公式如下:
在这里插入图片描述
时序差分法(TD):
当面对状态价值函数的求解时
在这里插入图片描述
动态规划(DP)会把上述第三个等式的估计值作为目标,不是因为DP要求需要环境模型本身提供期望值,而是因为真实的 v π ( S t + 1 ) v_π(S_{t+1}) vπ(St+1)是未知的,所以只能使用当前的估计值 v π ( S t + 1 ) v_π(S_{t+1}) vπ(St+1)来替代:
在这里插入图片描述
且DP求解状态 S t S_t St的状态值函数时,需要利用所有后续状态 S t + 1 S_{t+1} St+1
在这里插入图片描述
蒙特卡洛方法(MC)会上述把第一个等式的估计值作为目标,毕竟第一个等式中的期望值是未知的,所以我们用样本回报来代替实际的期望回报。但MC求解状态 S t S_t St的状态值函数时,需要等一个完整序列结束,因为只有到此时, G t G_t Gt才是已知的:
在这里插入图片描述
而时序差分(TD)既要采样得到上述第一个等式的期望值,而且还要通过使用上述第三个等式中当前的估计值V来替代真实值 v π v_π vπ且TD每过一个time step就利用奖励 R t + 1 R_{t+1} Rt+1和值函数 V ( S t + 1 ) V(S_{t+1}) V(St+1)更新一次(当然,这里所说的one-step TD 方法,也可以两步一更新,三步一更新….)

考虑到 G t = R t + 1 + γ V ( S t + 1 ) G_t=R_t+1+γV(S_{t+1}) Gt=Rt+1+γV(St+1),可得:
在这里插入图片描述
TD与DP一致的是,时序差分方法也无需等待交互的最终结果,而可以基于下一个时刻的收益 R t + 1 R_{t+1} Rt+1和估计值 V ( S t + 1 ) V(S_{t+1}) V(St+1)就可以更新当前状态的价值函数,不需像MC等到N步以后即等一个完整序列结束后才能更新 V ( S t ) V(S_t) V(St)

总之,TD结合了DP和MC,与DP一致的点是与MC不一致,与DP不一致的点恰又与MC一致,某种意义上来说,结合了前两大方法各自的优点,从而使得在实际使用中更灵活,具体而言如下图所示:
在这里插入图片描述
顺带再举一个例子,好比行军打仗时,为了得到更好的行军路线,将军派一人前去探路
MC的做法相当于一条道走到黑 没走个10公里不回头;
DP相当于所有道比如10条道 每条道都走个1公里 不错过任何一条可能成为最好道的可能,最后10条道都走完1公里后才返回汇报;
TD则相当于先选一条道走个1公里即返回汇报,之后再走下一条道的1公里;

参考自:https://blog.csdn.net/v_JULY_v/article/details/128965854

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

AcWing 2568:树链剖分 ← 线段树+DFS

【题目来源】https://www.acwing.com/problem/content/2570/【题目描述】 给定一棵树,树中包含 n 个节点(编号 1∼n),其中第 i 个节点的权值为 ai。 初始时,1 号节点为树的根节点。 现在要对该树进行 m 次操作&#xf…

为表格添加背景色:\rowcolor, \columncolor,\cellcolor

设置行的背景 \rowcolor 是 LaTeX 中用于设置表格行的背景色的命令。它可以使表格更加美观和易于阅读。rowcolor 命令通常与 colortbl 宏包一起使用。 语法如下&#xff1a; \rowcolor{<color>}其中 表示要设置的背景色&#xff0c;可以是预定义的颜色名称&#xff08…

【已解决】C#设置Halcon显示区域Region的颜色

前言 在开发过程中&#xff0c;突然发现我需要显示的筛选区域的颜色是白色的&#xff0c;如下图示&#xff0c;这对我们来说不明显会导致我的二值化筛选的时候存在误差&#xff0c;因此我们需要更换成红色显示这样的话就可以更加的明显&#xff0c;二值化筛选更加的准确。 解…

JMH304-剑侠情缘2网络版+2017纹饰端+翅膀+单机+外网整理+各种副本

资源介绍&#xff1a; 藏剑-太虚-梁山-杀手堂种树地宫师门纹饰装备长流云阳套等等———– 做登录器联系站长 资源截图&#xff1a; 下载地址

揭秘OS模块:文件与文件夹的遍历艺术

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、引言 二、os.listdir()&#xff1a;当前目录的扫描者 三、os.walk()&#xff1a;文件系…

鹏哥C语言复习——调试

目录 什么是调试&#xff1f; Debug和Release&#xff1a; 调试方法&#xff1a; 环境准备&#xff1a; 调试快捷键介绍&#xff1a; 调试快捷键注意事项&#xff1a; 监视与内存查看&#xff1a; 数组元素的监视&#xff1a; 编译常见错误归类&#xff1a; 编译型错…

windows中每日定时执行python脚本,解决问题

由于需要一个每天定时执行的任务&#xff0c;所以需要定时启动&#xff0c;网上看了很多方法&#xff0c;感觉不能在python脚本种写个while true 定时执行&#xff0c;占资源不说还不可靠。 最后考虑通过系统工具定时启动&#xff0c;发现linux中有crontab&#xff0c;windows…

Matlab-熵权法

文章目录 熵权法一、模型简介二、例题1. 数据标准化2.指标的熵值和变异程度3.权重与评分4.代码实现 熵权法 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 例如&#xff1a;随着人工智能的不断发展&#xff0c;机器学习这门技术也越来越重要&#xff0c;很多…

修改了vue3 <script setup>留言板

Лунная ночь <template><button class"edit_view_checkbox"><input type"checkbox" v-model"editshowInput" value"编辑" /></button><div class"editshowInput" v-if"editshowI…

线性回归计算举例

使用正规方程计算&#xff08;一元线性回归&#xff09; import numpy as np import matplotlib.pyplot as plt # 转化成矩阵 X np.linspace(0, 10, num 30).reshape(-1, 1) # 斜率和截距&#xff0c;随机生成 w np.random.randint(1, 5, size 1) b np.random.randint(1,…

骆驼大赛

目录 一&#xff0c;主版图 二&#xff0c;骰子 三&#xff0c;初始设置 四&#xff0c;核心规则 五&#xff0c;结算 这是适合5-8人玩的一个概率推理类的回合制桌游。 一&#xff0c;主版图 赛道由16个格子组成&#xff0c;编号为1-16。 一共7个骆驼&#xff0c;其中正…

基于 Java 的浏览器——JxBrowser使用分享

软件介绍 JxBrowser 是一个基于 Java 的浏览器&#xff0c;它使用 Chromium 引擎来提供高性能的网页渲染和丰富的功能。它支持多种 GUI 框架&#xff0c;如 Swing、JavaFX 和 SWT&#xff0c;使得在 Java 应用程序中嵌入浏览器组件变得简单。 JxBrowser 是一个适用于多种用途…

MySQL索引和视图

MySQL索引和视图是关系型数据库MySQL中的两个重要概念。索引用于优化数据库的查询性能&#xff0c;而视图用于提供一个逻辑上的表结构&#xff0c;方便用户查询和操作数据。 索引是一种数据结构&#xff0c;可以加速对数据库表中的数据进行查询的速度。通过创建索引&#xff0…

基于QEMU-aarch64学习UEFI(EDK2)-7Print打印函数

1 基于QEMU-aarch64学习UEFI(EDK2)-7Print打印函数 文章目录 1 基于QEMU-aarch64学习UEFI(EDK2)-7Print打印函数1.1 Print打印函数输出字符串1.2 Print打印函数其他用法程序开发我们以 edk2-stable202302版本为准。 1.1 Print打印函数输出字符串 我们把edk2/MdeModulePkg/App…

Py列表(list)

目录 正向索引&#xff1a; 反向索引&#xff1a; 嵌套列表&#xff1a; 修改列表中的值 列表常用的方法 实例 练习&#xff1a; 正向索引&#xff1a; 从0开始&#xff0c;依次递增。第一个元素的索引为0&#xff0c;第二个元素的索引为1&#xff0c;依此类推。 列表的下标…

Windows 使用技巧

Windows 使用技巧 ①局域网内共享文件 ②CTRL Y 和 CTRL Z ①局域网内共享文件 第一步&#xff1a; 选择要共享的文件&#xff08;分享方操作&#xff09; 第二步&#xff1a; 右键打开属性&#xff0c;选择共享&#xff08;分享方操作&#xff09; 第三步&#xff1a; …

redis数据类型set,zset

华子目录 Set结构图相关命令sdiff key1 [key2]sdiffstore destination key1 [key2...]sinter key1 [key2...]sinterstore destination key1 [key2...]sunion key1 [key2...]sunionstore destination key1 [key2...]smove source destination memberspop key [count]sscan key c…

使用Word表格数据快速创建图表

实例需求&#xff1a;Word的表格如下所示&#xff0c;标题行有合并单元格。 现在需要根据上述表格数据&#xff0c;在Word中创建如下柱图。如果数据在Excel之中&#xff0c;那么创建这个图并不复杂&#xff0c;但是Word中就没用那么简单了&#xff0c;虽然Word中可以插入图表&a…

[IMX6ULL驱动开发]-Linux对中断的处理(二)

上一篇文章中&#xff0c;引入了Linux对于中断的一些简略流程以及中断抽象为具体实际形象。此文章主要是继续加深对Linux对中断的处理流程以及一些相应的数据结构。 目录 Linux对中断的扩展&#xff1a;硬件中断、软件中断 多中断处理 中断上下部处理流程 发生中断A&#…

Golang | Leetcode Golang题解之第104题二叉树的最大深度

题目&#xff1a; 题解&#xff1a; func maxDepth(root *TreeNode) int {if root nil {return 0}queue : []*TreeNode{}queue append(queue, root)ans : 0for len(queue) > 0 {sz : len(queue)for sz > 0 {node : queue[0]queue queue[1:]if node.Left ! nil {queue…