当前位置: 首页 > news >正文

03 贝尔曼公式

贝尔曼公式

    • 前言
    • 1、Motivating examples
    • 2、state value
    • 3、Bellman equation:Derivation
    • 4、Bellman equation:Matrix-vector form
    • 4、Bellman equation:Solve the state value
    • 5、Action value

前言

本文来自西湖大学赵世钰老师的B站视频。本节课主要介绍贝尔曼公式。
本节课概要:本节课需要抓住两个内容,state value 和 the Bellman equation。本次大纲如下:

在这里插入图片描述

1、Motivating examples

在这里插入图片描述
return就是有多条轨迹,沿着这些轨迹可以得到很多的rewards,把这些rewards求和,就得到return。为什么return这么重要呢?通过上图三个例子来做介绍,上面三幅图的环境是一样的,s4是目标,s2是forbidden area,白色的是accessible area。这三幅图不同的是在状态s1上的策略是不同的,第一幅图在s1会往下走,第二幅图在s1会往右走,第三幅图在s1有50%的概率往下走,50%的概率往右走,在其他位置上,它们的策略是一样的。
因此,我们需要回答,从s1出发,哪一个策略是最好的,哪一个策略是最差的,从直观上来说,第一幅图的策略是最好的,第二幅图的策略是最差的,第三幅图的策略不好也不差。因为第一幅图从s1出发不会进入到forbidden area,第二幅图会直接进入forbidden area,第三幅图有50%的概率进入到forbidden area。那么我们可以用数学来描述这一种直观,数学工具就是这个return。return之所以重要,是因为它告诉我们哪个策略好,哪个策略坏,即它能够评估策略。
下面我们分别来计算这三个例子对应的return:
在这里插入图片描述
对于第一幅图,从s1到s3,得到的reward为0,从s3到s4得到的reward为γ乘以1,然后就会一直呆在s4,得到的结果如上图。同样的方法我们可以得到第二幅图和第三幅图对应的return。策略3对应的return实际上就是我们接下来要学的state value。
在这里插入图片描述
在这里插入图片描述
下面做个总结:
在这里插入图片描述
下面进一步来讲一下return如何计算。
考虑从不同状态出发,计算的return。用vi表示从状态si出发得到的return。有两种方法,第一种方法为:
在这里插入图片描述
第二种方法为:
在这里插入图片描述
v1就是从s1出发,到达s2之后,就相当于从s2出发了,从s2出发一定得到的是v2,因此v1可以写成上述形式,依次类推。
但同样也面临着一些问题,在计算时我们要求解v,但还得事先知道v,这个好像陷入了一个不可能解决的问题。看似好像无法解决,但如果我们用数学的话,就可以解决了,首先我们将上图中的式子写成矩阵和向量的形式:
在这里插入图片描述
在这里插入图片描述
这是一个比较简单的,特别是针对确定性问题的贝尔曼公式,后面会更加正式地介绍一般化地贝尔曼公式。但这个公式也告诉我们,一个状态地value实际上依赖于其他状态地value,这个就是bootstrapping想法;另外就是matrix-vector form也是非常重要地,就是我们只看一个公式是没办法解决的,但我们把所有的公式全都组合到一起,得到一个matrix-vector form就很容易求出来。
下面我们在做一个例子来加深理解:
在这里插入图片描述

2、state value

这一部分介绍state value概念。为了介绍state value,我们首先引入一些符号:
在这里插入图片描述
首先看单步的,St是当前状态,在当前状态下采取的动作是At,得到的下一个reward是Rt+1,跳到下一个状态是St+1。t指的是当前时刻,t+1指的是下一时刻。
在这里插入图片描述
St、At、Rt+1都是随机变量,这也就意味着我们可以求解它们的期望。这样单步的过程可以推广到多步的trajectory。下图中的Gt也是一个随机变量。
在这里插入图片描述
有了以上基础,我们可以来定义state value了:在这里插入图片描述

第一点:state value function 是关于状态s的函数,从不同的s出发,得到的轨迹不同,显然得到的discount return也不同,求平均也是不同的;第二点:state value function是一个策略的函数,显然不同的策略会得到不同的轨迹,不同的轨迹又会得到不同的return,进而会得到不同的state value。最后一点是,这个state value不仅仅是一个数值的value,它也代表一种价值,当一个state value比较大的时候,就代表这个状态是比较有价值的,因为从这个状态出发,我们会得到更多的return。
最后来回答这样一个问题:state value和return有什么区别?return是针对单个trajectory求的return,而state value是对多个trajectory得到的return再求平均值,如果我们从一个状态出发,有可能得到多个trajectory,此时return和state value是有区别的,但是如果我们从一个状态出发,一切都是确定性的,也就是说只能得到一条trajectory,此时从那个状态出发得到的return和state value是一样的
下面我们来看一个例子:
在这里插入图片描述
上述三幅图分别对应三个策略,假设从左到右分别是π1、π2、π3,接下来我们计算在这三个不同策略下,同一个状态s1的state value。计算vπ1(s1)、vπ2(s1)、vπ3(s1)可知,第一幅图对应的策略是最好的。(上图所举例子是求确定性的trajectory下的state value)

3、Bellman equation:Derivation

我们首先来学习的是如何来推到贝尔曼公式。本小节重点如下:
在这里插入图片描述
总结:我们要学会用贝尔曼公式计算上节中提到的state value,贝尔曼公式用一句话可以概况来说就是它描述了不同状态的state value之间的关系

在这里插入图片描述
首先考虑这样一个trajectory,从状态St出发,采取动作At,得到Rt+1和St+1,以此类推,得到了上图中的一个trajectory。这样的一个trajectory可以计算它的discounted return Gt,从上图推导后的公式来看,Gt就等于我立刻能得到的immediate reward Rt+1,再加上从下一时刻出发得到的Gt+1乘以discount rate γ。
在这里插入图片描述
从上图可以看出,state value可以用蓝色的两个期望来表示,分别计算这两个期望就能得到贝尔曼公式。下图就是第一个期望的计算方法:
在这里插入图片描述
第一项期望实际上就是immediate rewards的mean,第二项的期望公式见下图:
在这里插入图片描述
第二项是从当前状态s出发所得到的下一时刻的return的mean。从当前状态出发,可以有多个选择,可以跳到s撇,跳到不同s撇的概率是p(s撇|s),跳到s撇得到的期望值是E(Gt+1|St=s,St+1=s撇),E(Gt+1|St=s,St+1=s撇)指的是当前状态是s,下一时刻状态是s撇,计算从下一个状态出发,所得到的return的mean。E(Gt+1|St=s,St+1=s撇)中的St=s是可以去掉的,因为我已经知道了下一个状态是s撇,就不用关心之前是什么状态了。E(Gt+1|St+1=s撇)就是针对s撇的state value,用vπ(s撇)。从s到s撇的概率p(s撇|s)就是从状态s出发,选取不同的动作a的概率,乘以当前状态下采取动作a得到s撇的概率,不同动作a求和就是p(s撇|s)。
总之,第二个期望就是未来rewards的一个均值。
在这里插入图片描述
至此,我们就可以给出贝尔曼公式的表达式了:
在这里插入图片描述
上图中的公式就是贝尔曼公式,它实际上描述了不同状态的state value之间的关系。公式左边是s的state value,右边是s撇的state value。另外,这个式子包含两项,一项是immediate reward,另一项是future reward。上述式子应该是对状态空间中所有的状态都成立的,所以,如果我们有n个状态,我们就会有n个这样的式子,通过n个这样的式子,我们就可以把state value给求解出来,但我们通常就写上述一个式子,大家千万不要以为贝尔曼公式就只有这一个式子。

在这里插入图片描述
状态值如何计算呢?vπ(s)依赖于vπ(s撇),而vπ(s撇)又依赖于其它状态值,看起来似乎没办法计算,这其实就是bootstrapping,我们可以用矩阵来进行计算。另外,这个式子依赖于很多概率,π(a|s)是policy,贝尔曼公式是依赖于概率的,我们要把state value给计算出来,实际上我们现在正在做的事情就叫policy evaluation,就是去evaluation这个policy是好是坏。
在这里插入图片描述
上图中的绿色箭头就是策略π。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
如果假设γ=0.9,得到的结果见上图。state value实际上是代表了他的价值,如果一个状态价值高,说明了这个状态是值得我们往那个方向走的,在上图中,为什么s2,s3,s4的价值高呢,是因为他们离target area是比较近的,而s1离得较远。计算得到这个状态值之后,我们就可以去改进这个策略,慢慢的我们就可以得到最优的策略。
在这里插入图片描述
在这里插入图片描述

4、Bellman equation:Matrix-vector form

在上节中,我们介绍了贝尔曼公式的推导,这节来介绍贝尔曼公式的矩阵和向量形式。
在这里插入图片描述
在这里插入图片描述

rπ(s)是从当前状态出发,得到了所有immediate reward的平均值。上式红色画的意思是展开相乘。
在这里插入图片描述
上图中,[Pπ]ij代表第i行第j列的元素是从si跳到sj的概率,[Pπ]ij这个矩阵也被称为状态转移矩阵

在这里插入图片描述

上图是当n=4时,我所得到的matrix-vector 形式,上图中的Pπ就是状态转移矩阵。在举一个例子,见下图:
在这里插入图片描述

4、Bellman equation:Solve the state value

在这里插入图片描述
首先我们来回答一下为什么要求解state value,实际上给定一个policy,然后我会列出来它的一个贝尔曼公式,再进一步求解贝尔曼公式得到state value,这样的一个过程实际上叫做policy evaluation。policy evaluation是强化学习中非常关键的一个问题,因为我们只有去评价一个策略到底好还是不好,我们才能进一步的去改进它,最后在找到最优的策略,所以求解贝尔曼公式进而得到state value是非常重要的一个问题。
在这里插入图片描述
求state value我们给出两种解决方案,第一种就是用求逆矩阵的方法直接求解,但是这种方法通常不会使用,因为当状态空间特别大的时候,矩阵的维度也会特别大,求逆的计算量也会特别大,所以实际当中我们使用的是迭代的方法。iterative solution方法就是从一开始随机猜一个vπ,记为v0,把这个v0带入到上图红色箭头所指的式子中,因为rπ和Pπ都是可以事先知道的,所以可以计算得到v1,然后再把v1带到右边,就又可以得到v2,依次类推,就会得到序列{v0,v1,v2,…vk},实际上我们可以证明当k趋近于无穷的时候,vk就收敛到了vπ,这个vπ就是真实的state value。为什么vk会收敛到vπ呢?下面是证明。
在这里插入图片描述
证明的思路是定义vk与vπ之间的误差,证明这个误差趋近于0即可。下面我们通过例子来进一步说明。
在这里插入图片描述
上图是两个比较好的policy,可以看到得到的状态值均为正,并且我们还可以看出,不同的策略可以得到相同的value值。下面我们在看两个不好的policy。
在这里插入图片描述
通过以上例子可以得出,我们可以计算state value来评价一个策略究竟是好还是坏。

5、Action value

在前几节,我们介绍了state value,以及描述state value的贝尔曼公式,下面我们将从state value转向action value。
在这里插入图片描述
state value和action value有什么区别与联系呢?state value指的是agent从一个状态出发,所得到的average returnaction value指的是agent从一个状态出发并且选择一个action之后得到的average return
为什么要关注action value:实际上我们一直讨论的是强化学习中的策略,策略指的是在一个状态我要选择什么样的action,action有很多,具体选择哪一个action就是通过action value来判断,action value大的意味着采取该action能够得到更多的reward。
在这里插入图片描述
由上图可知,state value可以和action value建立联系。有很多个action,在当前状态下,采取其中一个action的概率为π(a|s),乘以采取该动作后得到的average return。与π(a|s)相乘的那一项就是action value。
在这里插入图片描述
在这里插入图片描述
下面通过一个例子来理解action value:
上图中策略已经通过绿色箭头画出来了。
在这里插入图片描述
下面做一个总结:

在这里插入图片描述
state value满足贝尔曼公式,贝尔曼公式刻画了state value之间的公式,是求解state value的一个工具,上图是它的elementwise form,就是对每一个状态都存在这样一个式子。

相关文章:

03 贝尔曼公式

贝尔曼公式 前言1、Motivating examples2、state value3、Bellman equation:Derivation4、Bellman equation:Matrix-vector form4、Bellman equation:Solve the state value5、Action value 前言 本文来自西湖大学赵世钰老师的B站视频。本节课主要介绍贝尔曼公式。 本节课概要…...

学习视频剪辑:批量添加srt字幕,让视频更生动

随着社交媒体的普及,视频制作变得越来越重要。无论是记录生活,还是分享知识,视频都是一个非常有力的工具。但是,如何让您的视频更生动、更吸引人呢?通过学习视频剪辑,您可以使您的视频更具有吸引力。而在这…...

Windows桌面便签工具推荐使用哪一款?

电脑桌面上张贴便利贴可以将近期需要完成的工作计划逐一添加到便利贴中,电脑桌面悬挂便利贴工具可以督促日常各项事务的完成。当前可悬挂在电脑桌面上的便利贴工具是比较多的,其中桌面小工具便签软件敬业签可满足各行业的办公需求。 建议大家在Windows桌…...

【微信小程序】自定义组件(二)

自定义组件 纯数据字段1、什么是纯数据字段2、使用规则 组件的生命周期1、组件全部的生命周期函数2、组件主要的生命周期函数3、lifetimes节点 组件所在页面的生命周期1、什么是组件所在页面的生命周期2、 pageLifetimes节点3、生成随机的颜色值 纯数据字段 1、什么是纯数据字…...

llinux的更目录下的文件作用和举例

Linux是一种开源的操作系统,其文件系统采用了一种层次化的结构。在Linux文件系统中,最顶层的目录被称为根目录,也就是“/”(斜杠)。在根目录下,有很多文件和目录,它们各自有着不同的作用。本文将…...

20231106_抽象类abstract

抽象类abstract 关键字 abstract运用抽象类抽象方法:修饰抽象类中的某个方法,强制子类重写该方法 归纳 关键字 abstract 对于子类必须要实现特定方法,当时父类无法明确时,可定义为抽象类及抽象方法 不合理: 动物吃东西是基础,在这里写吃的方法过于简单,信息没有实际意义; 怎…...

yolov5 obb旋转框 tensorrt部署

文章目录 1.生成engine文件2.检测图像3.代码yolov5-obb tensorRT部署代码结合王新宇和fish-kong两者的代码,可以多batch批量检测旋转框 yolov5旋转框检测: https://blog.csdn.net/qq_42754919/article/details/134145174 1.生成engine文件 首先需要将pt文件转换成wts文件,…...

http中的Content-Type类型

浏览器的Content-Type 最近在做web端下载的时候需要给前端返回一个二进制的流,需要在请求头中设置一个 writer.Header().Set("Content-Type", "application/octet-stream")那么http中的Content-Type有具体有哪些呢?他们具体的使用场…...

【C语法学习】17 - fwrite()函数

文章目录 1 函数原型2 参数3 返回值4 示例 1 函数原型 fwrite():将ptr指向的内存空间中储存的数据块写入与指定流stream相关联的二进制文件中,函数原型如下: size_t fwrite(const void *ptr, size_t size, size_t count, FILE *stream)2 参…...

CWE(Common Weakness Enumeration,通用缺陷枚举)

参考链接:https://cwe.mitre.org/ CWE(Common Weakness Enumeration,通用缺陷枚举)和CVE(Common Vulnerabilities & Exposures,通用漏洞和风险)都是在计算机软件安全领域中非常重要的公开数…...

华为政企视频会议产品集

产品类型产品型号产品说明 maintainProductCloudMCU基础版-ARM华为CloudMCU是为面向云化需求而推出的功能强大的企业云通信融合媒体平台。融合视频、音频和数据等多种媒体内容,接入从会议室到个人PC、手机等设备,实现统一无缝的沟通协作。maintainProduc…...

IntelliJ IDEA 2022创建Maven项目

IntelliJ IDEA 2022创建Maven项目 点击New Project 配置一下下 (1). 选择Maven Archetype (2). 输入Name就是你的项目名称 (3). 输入Location是你的项目保存目录 (4). 选择JDK (5). 选择Catalog一般默认选择Internal即可 在Archetype这里我们选择一个模板来创建Maven项目 …...

有限域的Fast Multiplication和Modular Reduction算法实现

1. 引言 关于有限域的基础知识,可参考: RISC Zero团队2022年11月视频 Intro to Finite Fields: RISC Zero Study Club 有限域几乎是密码学中所有数学的基础。 ZKP证明系统中的所有运算都是基于有限域的: 使用布尔运算的数字电路&#xf…...

第八章:security testing

文章目录 Security Testingbuffer overflow 的例子Fuzzing 测试Random Testing好处坏处Mutation-based Fuzzing好处坏处Generation-based Fuzzing好处坏处Memory DebuggerUndefined Behaviors (未定义行为)Security Testing 渗透测试(或称为pentesting)是指攻击软件以寻找安…...

Linux系统下一些配置建议整理

1. 【推荐】高并发服务器建议调小 TCP 协议的 time_wait 超时时间。 说明:操作系统默认 240 秒后,才会关闭处于 time_wait 状态的连接,在高并发访问下,服 务器端会因为处于 time_wait 的连接数太多,可能无法建立新的…...

【launch文件中如何启动gdb调试单个节点多个节点】

文章目录 调试多个节点在ROS中,如果需要用gdb调试节点,你可以在.launch文件中添加相关的参数。以下是一个例子,展示如何为一个节点启动gdb调试: <launch><node pkg="your_package" type="your_node...

Unity中Shader的GI的直接光实现

文章目录 前言一、在上一篇文章中&#xff0c;得到GI相关数据后&#xff0c;需要对其进行Lambert光照模型计算二、在准备好上面步骤后&#xff0c;我们需要准备缺少的数据1、准备上图中的 s.Normal2、准备上图中的 s.Albedo 前言 Unity中Shader的GI的直接光实现&#xff0c;基…...

JAVA进程和线程

哈喽~大家好呀&#xff0c;这篇来看看JAVA进程和线程。 &#x1f947;个人主页&#xff1a;个人主页​​​​​ &#x1f948; 系列专栏&#xff1a;【日常学习上的分享】 &#x1f949;与这篇相关的文章&#xff1a; Redis快速入…...

3.2-Docker Image概述

...

JS自定义深浅度克隆

function deepClone(obj, cache new WeakMap()) {if (typeof obj ! object) return obj //普通类型&#xff0c;直接返回if (obj null) return objif (cache.get(obj)) return cache.get(obj)//防止循环引用&#xff0c;程序进入死循环if (obj instanceof Date) return new D…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...