【强化学习-读书笔记】表格型问题的 Model-Free 方法
参考
Reinforcement Learning, Second Edition
An Introduction
By Richard S. Sutton and Andrew G. Barto
无模型方法
在前面的文章中,我们介绍的是有模型方法(Model-Based)。在强化学习中,"Model"可以理解为算法对环境的一种建模与抽象。这个模型用于捕捉智能体与环境之间的交互关系。建模的目的是为了帮助智能体更好地理解环境的动态特性,从而能够更有效地制定策略。在 Model-Based 方法中,智能体使用这个模型来规划未来的行动,而在 无模型方法(Model-Free) 方法中,智能体直接通过与环境的交互来学习策略,而不依赖于显式的环境模型。
无模型方法仅仅需要从环境中收集到 S , A , R , . . . S,A,R,... S,A,R,... 序列,作为算法的经验,持续更新。
根据每一次采样序列的长短,无模型方法分为 MC 和 TD 两大类。
MC 蒙特卡洛方法
从一个状态 s s s出发,重复采样多条轨迹,每一条状态都采样直到终止状态,把轨迹的平均折扣回报作为状态价值的估计
V π ( s ) = E [ G t ∣ s ] ≈ 1 N ∑ i = 1 N G t i V_\pi (s)=\mathbb{E}[G_t|s]\approx \frac{1}{N}\sum_{i=1}^N G_{t}^i Vπ(s)=E[Gt∣s]≈N1i=1∑NGti
MC 的增量更新
V π ( s ) ← V π ( s ) + 1 N ( G t − V π ( s ) ) V_\pi(s) \leftarrow V_\pi(s)+\frac{1}{N}(G_t-V_\pi(s)) Vπ(s)←Vπ(s)+N1(Gt−Vπ(s))
对于非平稳问题,增量更新为(红色:TD target):
V π ( s ) ← V π ( s ) + α ( G t − V π ( s ) ) V_\pi(s) \leftarrow V_\pi(s)+\alpha(\red{G_t}-V_\pi(s)) Vπ(s)←Vπ(s)+α(Gt−Vπ(s))
缺点:
- 只适用于有限幕问题
- 更新慢,需要采样整条序列,然后才进行更新。
TD 时序差分方法
TD 在 MC 上做了修改,不需要采样整条序列,而是只采样一步(贝尔曼方程),用 V V V 对后面所有的奖励进行估计(自举法) ,然后立刻进行更新(红色:TD target):
V π ( s ) ← V π ( s ) + α ( R t + 1 + γ V π ( S t + 1 ) − V π ( s ) ) V_\pi(s) \leftarrow V_\pi(s)+\alpha(\red{R_{t+1}+\gamma V_\pi(S_{t+1})} -V_\pi(s)) Vπ(s)←Vπ(s)+α(Rt+1+γVπ(St+1)−Vπ(s))
一般来说,TD方法比MC方法收敛更快。
MC vs TD
- TD 可以在线学习,效率高一些,采样和学习可以同时进行,而MC不行,要一直模拟到游戏结束
- TD 方差大,因为没训练好的时候 V V V本身就估计不准,所以 V t + 1 V_{t+1} Vt+1引入了额外的误差
强化学习中的重要性加权
例子引入:现在给定的轨迹是另一个策略 μ \mu μ (顶级选手的下法 μ ( a ∣ s ) \mu(a|s) μ(a∣s))采样出来的,如果用 μ \mu μ 的轨迹计算得到的 G t G_t Gt (经验)直接用来进行另一个策略 π \pi π (入门选手 π ( a ∣ s ) \pi(a|s) π(a∣s))的学习,那么就可能不合适。
从算法的角度说,在于 TD target G t G_{t} Gt 对于 μ \mu μ 的评价是不准确的,我们需要对 G t G_t Gt进行修正。
改进的方法是使用重要性加权。
- MC 的重要性加权
朴素的想法:对于那些 π \pi π 也能做出类似的 ( a ∣ s ) (a|s) (a∣s) 动作,给予这些动作对应的轨迹的回报 G t G_t Gt 更大的权重,反之给予小的权重。
于是 MC 的重要性加权如下:
G t π / μ = π ( a t ∣ s t ) μ ( a t ∣ s t ) π ( a t + 1 ∣ s t + 1 ) μ ( a t + 1 ∣ s t + 1 ) . . . π ( a T ∣ s T ) μ ( a T ∣ s T ) G t G_{t}^{\pi/\mu}=\frac{\pi(a_t|s_t)}{\mu(a_t|s_t)}\frac{\pi(a_{t+1}|s_{t+1})}{\mu(a_{t+1}|s_{t+1})}...\frac{\pi(a_{T}|s_{T})}{\mu(a_{T}|s_{T})}G_t Gtπ/μ=μ(at∣st)π(at∣st)μ(at+1∣st+1)π(at+1∣st+1)...μ(aT∣sT)π(aT∣sT)Gt
用加权之后的总折扣 G t π / μ G_{t}^{\pi/\mu} Gtπ/μ更新值函数
V π ( s ) ← V π ( s ) + α ( G t π / μ − V π ( s ) ) V_\pi(s) \leftarrow V_\pi(s)+\alpha(G_{t}^{\pi/\mu}-V_\pi(s)) Vπ(s)←Vπ(s)+α(Gtπ/μ−Vπ(s))
问题在于:
- 无法在 μ \mu μ 为0时使用
- 由于连续多个商相乘,显著增大方差。
改进:- TD 的重要性加权
TD 由于只用一步进行更新,所以相应的重要性采样只有一个商,可以降低方差。
V π ( s ) ← V π ( s ) + α ( π ( a t ∣ s t ) μ ( a t ∣ s t ) ( r t + 1 + γ V ( S t + 1 ) ) − V π ( s ) ) V_\pi(s) \leftarrow V_\pi(s)+\alpha \left(\blue{\frac{\pi(a_t|s_t)}{\mu(a_t|s_t)}}\red{(r_{t+1}+\gamma V(S_{t+1}))}-V_\pi(s) \right) Vπ(s)←Vπ(s)+α(μ(at∣st)π(at∣st)(rt+1+γV(St+1))−Vπ(s))
TD 方法: SARSA
两个步骤:
- ϵ \epsilon ϵ-贪心(或者 Decaying ϵ − \epsilon- ϵ−贪心,更加有效)地选择 A A A,从而得到 S , A , R ′ , S ′ , A ′ S ,A ,R' ,S', A' S,A,R′,S′,A′五元组,
- 利用五元组更新价值函数,TD target = R + γ Q ( S ′ , A ′ ) =R+\gamma Q(S',A') =R+γQ(S′,A′)
Q ( S , A ) ← Q ( S , A ) + α [ R + γ Q ( S ′ , A ′ ) − Q ( S , A ) ] Q(S,A)\leftarrow Q(S,A) + \alpha [\red{R+ \gamma Q(S',A')} - Q(S,A)] Q(S,A)←Q(S,A)+α[R+γQ(S′,A′)−Q(S,A)]
SARSA 是一种 On-policy (同轨策略)方法,因为用于计算 TD target 的值函数和用于动作选择的值函数是同一个。
特点:
- 同轨策略
- 运算量小,轻量化,在线
- 偏保守,考虑了 ϵ \epsilon ϵ 的影响(悬崖例子)
TD 方法:Q-learning
和 SARSA 的唯一区别:
将给 TD target 加了一个 max,是用最大估计价值来更新值函数。
Q ( S , A ) ← Q ( S , A ) + α [ R + γ max a Q ( S ′ , a ) − Q ( S , A ) ] Q(S,A)\leftarrow Q(S,A) + \alpha [\red{R+ \gamma \max_a Q(S',a)} - Q(S,A)] Q(S,A)←Q(S,A)+α[R+γamaxQ(S′,a)−Q(S,A)]
- 异轨策略(Off-policy)
- 运算量大,因为要比较每一个 a a a 的价值
- 偏激进,没有考虑 ϵ \epsilon ϵ 的影响(悬崖例子)
- 有过估计的问题,由于 max \max max 操作,会让估计值偏大,导致算法过于自信。
SARSA 改进: 期望 SARSA
由于 SARSA 每一次只用 S ′ , A ′ S',A' S′,A′作为下一个状态的估计,会导致方差较大, 期望 SARSA 引入后继所有状态价值的期望,降低了方差。
Q ( S , A ) ← Q ( S , A ) + α [ R + γ ∑ a π ( a ∣ S ′ ) Q ( S ′ , a ) − Q ( S , A ) ] Q(S,A)\leftarrow Q(S,A) + \alpha [\red{R+ \gamma \sum_{a} \pi(a|S')Q(S',a)} - Q(S,A)] Q(S,A)←Q(S,A)+α[R+γa∑π(a∣S′)Q(S′,a)−Q(S,A)]
期望 SARSA 既可以看作 SARSA 的期望版本,也可以看作将 Q-learning 的 max 改为 mean 的版本。
期望 Sarsa 在计算上比 Sarsa 更加复杂。但作为回报,它消除了因为随机选择产生的方差。 在相同数量的经验下,我们可能会预想它的表现能略好于 Sarsa, 期望 Sarsa也确实表现更好。
除了增加少许的计算量之。期望 Sarsa 应该完全优于这两种更知名的时序差分控制算法
最大化偏差与双学习
Q-learning 存在最大化偏差的问题,max 的操作会让算法过高估计值函数。
书中的例子:
走左边在期望意义上是更差的,但是由于左边的奖励是由 N ( − 0.1 , 1 ) \mathcal{N}(-0.1,1) N(−0.1,1) 产生的,在刚开始的时候算法的 Q ( s , a ) Q(s,a) Q(s,a) 大概率有正数,因此 max 之后会得到一个正数,这会驱使算法在刚开始的时候往左边走。当估计次数增多之后,左边各个状态都收敛到 -0.1 的均值奖励,从而 max Q 必然小于0,算法开始回头,往期望恒为 0 的右边走。
双 Q 学习
这里实际上是非深度版本的Double Q-learning,因为没有buffer,所以是 Q 1 , Q 2 Q_1,Q_2 Q1,Q2完全对等的地位,用交替更新的方法打破对称性。在实际选择动作的时候用 Q 1 + Q 2 Q_1+Q_2 Q1+Q2
在交替更新的时候,都用需要更新的那个 Q Q Q 进行动作选择,然后另一个 Q ′ Q' Q′ 进行动作估计
(类似于 Deep Double Q-learning ,快 Q θ Q_{\theta} Qθ 用来选动作,慢 Q θ − Q_{\theta -} Qθ− 用来进行价值估计)
相关文章:

【强化学习-读书笔记】表格型问题的 Model-Free 方法
参考 Reinforcement Learning, Second Edition An Introduction By Richard S. Sutton and Andrew G. Barto无模型方法 在前面的文章中,我们介绍的是有模型方法(Model-Based)。在强化学习中,"Model"可以理解为算法…...
【手撕算法系列】k-means
k-means k-means算法介绍 k-means算法介绍 K-means算法是一种用于聚类的迭代算法,它将数据集划分为K个簇,其中每个数据点属于与其最近的簇的中心。这个算法的目标是最小化簇内的平方和误差(簇内数据点与簇中心的距离的平方和)。 …...

D33|动态规划!启程!
1.动态规划五部曲: 1)确定dp数组(dp table)以及下标的含义 2)确定递推公式 3)dp数组如何初始化 4)确定遍历顺序 5)举例推导dp数组 2.动态规划应该如何debug 找问题的最好方式就是把…...

C语言----文件操作(二)
在上一篇文章中我们简单介绍了在C语言中文件是什么以及文件的打开和关闭操作,在实际工作中,我们不仅仅是要打开和关闭文件,二是需要对文件进行增删改写。本文将详细介绍如果对文件进行安全读写。 一,以字符形式读写文件ÿ…...
oracle 10046事件跟踪
10046事件是一个很好的排查sql语句执行缓慢的内部事件,具体设置方式如下: 根据10046事件跟踪SQL语句 1、 alter session set events 10046 trace name context forever,level 12; 2、执行SQL语句 3、关闭10046事件 alter session set events 10046 trace…...

微软自带浏览器Edge,无法关闭“保存历史记录网站的屏幕截图”解决方案
微软自带浏览器Edge,无法关闭“保存历史记录网站的屏幕截图”解决方案 吐槽1:Windows自带的Chrome内核版本的浏览器Microsofg Edge刚发布时可谓一股清流,启动速度快,占用内存较小,相信很多人也开始抛弃正代Chrome&…...

讲座 | 颠覆传统摄像方式乃至计算机视觉的“脉冲视觉”
传统相机拍摄视频时其实是以一定帧率进行采样,视频其实还是一串图片的集合,因此低帧率时会觉得视频卡,拍摄高速运动物体时会有运动模糊等等问题。然而你能想象这一切都可以被“脉冲视觉”这一前沿技术改变吗? 今天下午听了北京大学…...

uniGUI学习之UniHTMLMemo1富文本编辑器
1]系统自带的富文本编辑器 2]jQueryBootstarp富文本编辑器插件summernote.js 1]系统自带的富文本编辑器 1、末尾增加<p> 2、增加字体 3、解决滚屏问题 4、输入长度限制问题 5、显示 并 编辑 HTML源代码(主要是图片处理) 1、末尾增加<p> UniHTMLMemo1.Lines…...

详细教程 - 从零开发 鸿蒙harmonyOS应用 第四节 (鸿蒙Stage模型 登录页面 ArkTS版 推荐使用)
在鸿蒙OS中,Ability是应用程序提供的抽象功能,可以理解为一种功能。在应用程序中,一个页面即一种能力,如登录页面,即具有登录功能的能力。以下是对鸿蒙新建项目的登录代码功能的详细解读和工作流程的描述: …...
uniapp怎么实现授权登录
在Uniapp中实现授权登录通常涉及以下几个步骤: 创建登录按钮:在页面中创建一个按钮,用于触发登录操作。 获取用户授权:当用户点击登录按钮时,调用uni.login或uni.getUserInfo等API获取用户授权。 处理授权回调&#…...

从零开始:前端架构师的基础建设和架构设计之路
文章目录 一、引言二、前端架构师的职责三、基础建设四、架构设计思想五、总结《前端架构师:基础建设与架构设计思想》编辑推荐内容简介作者简介目录获取方式 一、引言 在现代软件开发中,前端开发已经成为了一个不可或缺的部分。随着互联网的普及和移动…...

椋鸟C语言笔记#26:数据在内存中的存储(大小端字节序)、浮点数的存储(IEEE754)
萌新的学习笔记,写错了恳请斧正。 目录 大小端字节序 什么是大小端 写一个判断大小端的程序 浮点数在内存中的存储(IEEE 754规则) 引入 存储规则解释 读取规则解释 1.阶码不全为0或全为1(规格化数) 2.阶码全为…...

设计模式——组合模式(结构型)
引言 组合模式是一种结构型设计模式, 你可以使用它将对象组合成树状结构, 并且能像使用独立对象一样使用它们。 问题 如果应用的核心模型能用树状结构表示, 在应用中使用组合模式才有价值。 例如, 你有两类对象: …...

鸿蒙小车之多任务调度实验
说到鸿蒙我们都会想到华为mate60:遥遥领先!我们一直领先! 我们这个小车也是采用的是鸿蒙操作系统,学习鸿蒙小车,让你遥遥领先于你的同学。 文章目录 前言一、什么是任务?为什么要有任务二、任务的状态三、任…...

【报错栏】(vue)Module not found: Error: Can‘t resolve ‘element-ui‘ in xxx
Module not found: Error: Cant resolve element-ui in xxx 报错原因是: 未安装 element-ui 依赖 解决: npm install element-ui 运行...

seaborn库图形进行数据分析(基于tips数据集)
Seaborn 是一个基于 matplotlib 的数据可视化库,可以用来绘制各种统计图表,包括散点图、条形图、折线图、箱线图等。Seaborn 提供了一些用于美化图表的默认样式和颜色主题,使得生成的图表更具有吸引力。下面是一些 Seaborn 库的常用功能和用法…...

AC843. n皇后问题--60
我们只需要把蓝色的往上移动就行了 if(!col[i][j]&&!dg[ui]&&!udg[])//1y(i)向下,x(u)向右为正。yxb的by-x一定>0,y-xb的bxy可能>0,这个不考虑,只看-bxy....
Js WebSocket类,收发Json,带心跳,断线重连
如题 心跳:4秒发一次 断线:2秒后自动重连 收发:发送和返回json,处理粘包断包等情况,json字符串最大长度9999 缓存:未连接时,自动缓存100个包,当连接时会自动发出 JS代码 var MyWeb…...

VBA技术资料MF96:单字段多条件高级筛选
我给VBA的定义:VBA是个人小型自动化处理的有效工具。利用好了,可以大大提高自己的工作效率,而且可以提高数据的准确度。我的教程一共九套,分为初级、中级、高级三大部分。是对VBA的系统讲解,从简单的入门,到…...

电子取证中Chrome各版本解密Cookies、LoginData账号密码、历史记录
文章目录 1.前置知识点2.对于80.X以前版本的解密拿masterkey的几种方法方法一 直接在目标机器运行Mimikatz提取方法二 转储lsass.exe 进程从内存提取masterkey方法三 导出SAM注册表 提取user hash 解密masterkey文件(有点麻烦不太推荐)方法四 已知用户密…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...