强化学习------贝尔曼方程

目录

    • 前言
    • 基础知识
    • 马尔可夫决策过程 (Markov decision process, MDP)
        • 回报(Return)
        • 折扣回报(Discounted Return)
    • State Value(状态价值函数)
    • 贝尔曼方程的推导
    • 贝尔曼方程的矩阵形式
    • Action Value(动作价值函数)
    • 贝尔曼最优公式

前言

最近在学习强化学习的内容,为了更加方便理解强化学习中的各种算法与底层原理,学习了贝尔曼方程以及最优公式,特此记录
参考课程:强化学习的数学原理

什么是贝尔曼方程?

贝尔曼方程,又叫动态规划方程,是以Richard Bellman命名的,表示动态规划问题中相邻状态关系的方程。某些决策问题可以按照时间或空间分成多个阶段,每个阶段做出决策从而使整个过程取得效果最优的多阶段决策问题,可以用动态规划方法求解。某一阶段最优决策的问题,通过贝尔曼方程转化为下一阶段最优决策的子问题,从而初始状态的最优决策可以由终状态的最优决策(一般易解)问题逐步迭代求解。存在某种形式的贝尔曼方程,是动态规划方法能得到最优解的必要条件。绝大多数可以用最优控制理论解决的问题,都可以通过构造合适的贝尔曼方程来求解。

基础知识

名词解释
智能体学习器与决策者的角色
环境智能体之外一切组成的、与之交互的事物
动作智能体的行为表征
状态智能体从环境获取的信息
奖励环境对于动作的反馈
策略智能体根据状态进行下一步动作的函数
状态转移概率智能体做出动作后进入下一状态的概率

RL考虑的是智能体(Agent)与环境(Environment)的交互问题:
RL的目标是找到一个最优策略,使智能体获得尽可能多的来自环境的奖励。例如赛车游戏,游戏场景是环境,赛车是智能体,赛车的位置是状态,对赛车的操作是动作,怎样操作赛车是策略,比赛得分是奖励。在论文中中常用观察(Observation)而不是环境,因为智能体不一定能得到环境的全部信息,只能得到自身周围的信息。
在这里插入图片描述

学习开始时往往采用随机策略进行实验得到一系列的状态、动作和奖励样本,算法根据样本改进策略,最大化奖励。由于奖励越来越大的特性,这种算法被称作强化学习。

马尔可夫决策过程 (Markov decision process, MDP)

强化学习的数学基础和建模工具是马尔可夫决策过程 (Markov decision process,MDP)
一个 MDP 通常由状态空间、动作空间、状态转移函数、奖励函数、折扣因子等组成。

回报(Return)

回报 (return) 是从当前时刻开始到本回合结束的所有奖励的总和,所以回报也叫做累计奖励 (cumulative future reward)。
把t时刻的回报记作随机变量 U t U_t Ut,如果一回合游戏结束,已经观测到所有奖励,那么就把回报记作 u t u_t ut ,设本回合在时刻n nn结束。定义回报为:
U t = R t + R t + 1 + R t + 2 + R t + 3 + . . . + R n U_t =R _t +R _{t+1}+R _{t+2}+R_{t+3}+...+R _n Ut=Rt+Rt+1+Rt+2+Rt+3+...+Rn

回报是未来获得的奖励总和,所以智能体的目标就是让回报尽量大,越大越好。强化学习的目标就是寻找一个策略,使得回报的期望最大化。这个策略称为最优策略 (optimum policy)。

折扣回报(Discounted Return)

在 MDP 中,通常使用折扣回报 (discounted return),给未来的奖励做折扣。折扣回报的定义如下:
G t = R t + γ R t + 1 + γ 2 R t + 2 + γ 3 R t + 3 + . . . G_t =R _t +γR _{t+1}+γ^2R _{t+2}+γ^3R_{t+3}+... Gt=Rt+γRt+1+γ2Rt+2+γ3Rt+3+...
这里的 γ ∈ [ 0 , 1 ] \gamma \in [0,1] γ[0,1]叫折扣率。对待越久远的未来,给奖励打的折扣越大。
t t t时刻当前状态 s t s_t st 和策略函数 π ( a ∣ s ) \pi(a|s) π(as)选取动作 a t a_t at,然后状态转移 p t ( s ′ ∣ s , a ) = P ( S t + 1 ′ = s ′ ∣ S t = s , A t = a ) p_t(s'|s,a) = P(S'_{t+1}=s'|S_t=s,A_t=a) pt(ss,a)=P(St+1=sSt=s,At=a),选取新的状态 S t + 1 ′ = s ′ S'_{t+1}=s' St+1=s,奖励 R i R_i Ri只依赖于 S i S_i Si A i A_i Ai

State Value(状态价值函数)

首先我们采取一个以下的过程
在这里插入图片描述

  • t t t, t + 1 t+1 t+1:时间片段
  • S t S_t St:在时间 t t t下的状态
  • A t A_t At:在状态 S T S_T ST下采取的动作
  • R t + 1 R_{t+1} Rt+1:采取动作 A t A_t At后获取到的奖励值
  • S t + 1 S_{t+1} St+1:采取动作 A t A_t At后到达的状态

这样的一个动作持续下去:
在这里插入图片描述

我们通过马尔可夫过程,获得一个累计的折扣奖励:
G t = R t + γ R t + 1 + γ 2 R t + 2 + γ 3 R t + 3 + . . . G_t =R _t +γR _{t+1}+γ^2R _{t+2}+γ^3R_{t+3}+... Gt=Rt+γRt+1+γ2Rt+2+γ3Rt+3+...
γ ∈ [ 0 , 1 ] \gamma \in [0,1] γ[0,1]

State Value是什么呢?
本质上就是 G t G_t Gt的期望,即平均值,在状态 S t S_t St下可以执行多不同的行为,从而产生多个轨迹 G t G_t Gt,State Value就是这多个 G t G_t Gt的平均值。
我们用 v π v_{\pi} vπ代表State Value
在这里插入图片描述

以下是采取不同策略获得的State Value

在这里插入图片描述

贝尔曼方程的推导

我们将上方的 G t G_t Gt的做一下修改;

在这里插入图片描述
可以看到我们将 G t G_t Gt分为了两部分

然后我们将其带入到 v π ( s ) v_\pi(s) vπ(s)中,可以看到 v π ( s ) v_\pi(s) vπ(s)也被分为了两部分

在这里插入图片描述
下面我们做的就是分别来分析这两个公式,就可以得到贝尔曼方程

首先第一项 E [ R t + 1 ∣ S t = s ] E[R_{t+1} | S_t=s] E[Rt+1St=s]
可以得到
在这里插入图片描述
解释:在状态s可以有多个action去执行,执行a的概率为 π ( a ∣ s ) \pi(a|s) π(as),然后我们在状态s下执行a,获得奖励r,我们将这多个action执行后获得的奖励求平均即可

本质上就是我们在状态s下执行各种action获得奖励的平均值,为及时奖励

我们再来看第二项
在这里插入图片描述
解释:通过马尔可夫的性质:下个状态只与当前状态信息有关,与更早之前的状态无关,即“无记忆性”,我们可以省去 S t = s S_t=s St=s,因为 E [ G t + 1 ∣ S t + 1 = s ‘ ] E[G_{t+1} | S_{t+1}=s^‘] E[Gt+1St+1=s]就是下一个状态的 v π v_{\pi} vπ,所以可以推导出以上公式
本质上是未来奖励

推导完上面的两项公式,我们将推导的公式代入到 v π v_{\pi} vπ,就可以得出贝尔曼方程:
在这里插入图片描述
这个公式描述了不同状态之间的关系,因为左边是 v π ( s ) v_{\pi}(s) vπ(s),右边是 v π ( s ’ ) v_{\pi}(s^’) vπ(s)

例子
在这里插入图片描述
我们从 s 1 s_1 s1出发,根据贝尔曼方程,我们可以得到
v π ( s 1 ) v_{\pi}(s_1) vπ(s1) = 0.5[0+γ v π ( s 3 ) + 0.5 [ − 1 + γ v π ( s 2 ) ] v_{\pi}(s_3)+0.5[-1+γv_{\pi}(s_2)] vπ(s3)+0.5[1+γvπ(s2)]
s 2 s_2 s2 s 3 s_3 s3 s 4 s_4 s4,分别可以得到:

在这里插入图片描述

贝尔曼方程的矩阵形式

当我们有了一个贝尔曼方程,我们需要求解该贝尔曼方程

对于贝尔曼方程,所有的状态都是适用的,这样我们可以写成一个矩阵的形式,这样方便我们去求解该方程。

我们先令以下公式成立:
在这里插入图片描述
然后我们就可以将贝尔曼方程,化简为:
在这里插入图片描述
我们将其化为矩阵形式就需要多个状态,我们设有n个状态:
在这里插入图片描述
从刚才的公式我们可以得到:
在这里插入图片描述
然后我们令:
在这里插入图片描述
[ P π ] i j [P_\pi]_{ij} [Pπ]ij代表第i行第j列的元素是从 s i s_i si跳到 s j s_j sj的这样一个概率

之后我们就可以得到,贝尔曼方程的矩阵形式如下:
v π = r π + γ P π v_\pi = r_\pi + γP_\pi vπ=rπ+γPπ v π v_\pi vπ

具体例子如下:
例子1
在这里插入图片描述

例子2
在这里插入图片描述
我们如何求解这个矩阵形式的贝尔曼方程呢?

可以使用迭代的方式去求解
通过 v 0 v_0 v0求出 v 1 v_1 v1,通过 v 1 v_1 v1求出 v 2 v_2 v2,以此迭代下去。

Action Value(动作价值函数)

  • State value:从一个状态s出发得到的平均奖励(从状态s出发的多条轨迹的平均奖励)
  • Action vlaue:从一个状态出发并选择一个action得到的平均奖励

Action value的定义如下:
在这里插入图片描述
我们从数学上看一下 Action value与State value的关系:

在这里插入图片描述
因此

在这里插入图片描述
我们将上面这个公式与下面的公式做对比
在这里插入图片描述
我们可以得到画线的就是Action value在这里插入图片描述

在这里插入图片描述
所以我们可以得出结论:

  • 1、如果我们得到一个状态s下的所有Action value,求平均就可以得到State value
  • 2、如果我们得到所有状态的State value,就可以得到所有的Action value

具体例子如下
首先我们按照箭头的方向做出action,得到以下的Action value
q π ( s 1 , a 2 ) = − 1 + γ v π ( s 2 ) q_\pi(s_1,a_2) = -1 + γv_\pi(s_2) qπ(s1,a2)=1+γvπ(s2)

虽然箭头是指向s2的(忽略红色箭头),但是我们依旧可以算其它方向的Action value,例如我们可以计算红色箭头的Action value
q π ( s 1 , a 3 ) = 0 + γ v π ( s 3 ) q_\pi(s_1,a_3) = 0 + γv_\pi(s_3) qπ(s1,a3)=0+γvπ(s3)(因为 s 1 s_1 s1 s 3 s_3 s3都为空白格,所以奖励为0)

在这里插入图片描述

贝尔曼最优公式

在强化学习中,我们的目的就是找最优的策略,而贝尔曼方程的最优公式为我们提供了理论支撑

最优的定义:

我们有一个策略 π ∗ \pi^* π,在所有的状态s下以及所有其它策略 π \pi π下,存在 v π ∗ ( s ) v_{\pi^*}(s) vπ(s)大于所有的 v π ( s ) v_\pi(s) vπ(s)
我们称这个策略 π ∗ \pi^* π为最优策略

对于最优,我们有以下问题:

  • 1、该策略是否存在?
  • 2、该策略是否唯一?
  • 3、该策略是确定性的还是非确定性的?
  • 4、怎么去得到最优策略?

根据以上问题,我们需要研究贝尔曼最优公式,以下就是贝尔曼最优公式
在这里插入图片描述

以下是贝尔曼方程最优公式的矩阵形式:
在这里插入图片描述
因为对于求解贝尔曼方程最优公式的推导有些复杂,视频中介绍了contraction mapping theorem来求解贝尔曼最优公式,我这里不详细给出,有兴趣的可以观看视频

我们只要知道,该方程存在一个唯一的解 v ∗ v^* v,且唯一存在,同时也可以利用迭代的方法求解出来
在这里插入图片描述
求解步骤如下:
1、对于任何状态s,当前的策略为 v k ( s ) v_k(s) vk(s)(初始化得到的)
2、对于任何action,我们计算在这里插入图片描述

3、我们使用贪婪算法,选择最大的 q k ( s , a ) q_k(s,a) qk(s,a)
在这里插入图片描述
4、然后 v k + 1 ( s ) v_{k+1}(s) vk+1(s)就是最大的 q k ( s , a ) q_k(s,a) qk(s,a)
在这里插入图片描述
这个步骤迭代下去,就可以求出一个最优的策略 π \pi π

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

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

相关文章

基于 Modbus 的工业数据采集、控制(part 2)

基本处理流程 服务器 parse_and_process(char * input)//input :post请求发送的正文 {...// 请求 modbus 数据else if(strstr(input, "modbus_get")){return handle_get(sock, input);}// 控制 modbus 设备else if(strstr(input, "modbus_set")){return …

【OpenAI】经营权争夺战关系图

《OpenAI新模型曝重大飞跃:AGI雏形或威胁人类,也成Altman被解雇导火索!》摘要如下: [一句话总结] OpenAI的Q*项目取得突破,解决了以前未见过的数学问题,为AI发展带来重要的技术里程碑。 [文章概览要点] OpenAI内部研…

redis运维(十四) hash缓存案例

一 缓存案例 ① 需求 ② 个人理解 策略:不更新缓存,而是删除缓存大部分观点认为:1、做缓存不应该是去更新缓存,而是应该删除缓存2、然后由下个请求去缓存,发现不存在后再读取数据库,写入redis缓存 高并发场景下,到底先更新缓存还是先更…

完美解决RuntimeError: implement_array_function method already has a docstring

文章目录 一、报错原因--numpy版本太低二、更新numpy总结 一、报错原因–numpy版本太低 当收到 "RuntimeError: implement_array_function method already has a docstring" 错误时,这可能是由于在numpy的某个版本中,该方法的文档字符串&…

vue3-生命周期

​🌈个人主页:前端青山 🔥系列专栏:Vue篇 🔖人终将被年少不可得之物困其一生 依旧青山,本期给大家带来vue篇专栏内容:vue3-生命周期 目录 vue3生命周期 vue3生命周期钩子 1.1 onMounted() 1.2 onUpdated() 1.3 onU…

2024年天津专升本招生计划及其收费标准

2024年天津专升本招生计划及其收费标准 天津农学院 文史类 人力资源管理 20 4400 文史类 物流管理 20 4400 理工类 人力资源管理 10 4400 理工类 物流管理 10 4400 理工类 水文与水资源工程 30 5400 有专业限制 理工类 水产养殖学 20 4400 有专业限制 天津…

ui5使用echart

相关的代码已经发布到github上。 展示下相关的实现功能 1、柱状图-1 2、柱状图-2 3.折线图 4.饼状图 如何使用: 使用git clone项目到本地 git clone https://github.com/linhuang0405/com.joker.Zechart找到index.html。在vscode里右键选择Open with Live Serve…

我的创业之路:3个月的经历与回顾

从金山办公离职到现在已过去差不多3个月的时间,自己开发的产品也逐步稳定,是时候总结和回顾一下这三个月的心路历程了 起点 离职后,我思考过很多个创业项目,最后还是选择了做一款在线打字练习的网站。其主要原因如下&#xff1a…

杨传辉:从一体化架构,到一体化产品,为关键业务负载打造一体化数据库

在刚刚结束的年度发布会上,OceanBase正式推出一体化数据库的首个长期支持版本 4.2.1 LTS,这是面向 OLTP 核心场景的全功能里程碑版本,相比上一个 3.2.4 LTS 版本,新版本能力全面提升,适应场景更加丰富,有更…

关于APP备案的通知以及APP备案的常见问题

前言 众所周知今年8月份,工信部出台了《工业和信息化部关于开展移动互联网应用程序备案工作的通知》,APP开发者的影晌是显而易见的。开发者需要按照要求提交相关材料进行备案,这无疑增加了开发者的时间和精力成本。虽然备案制度会增加开发者…

探针台的应用领域

探针台(Probe Station)是一种用于对半导体器件进行电性能测试的重要设备。它通常由精密的机械结构、高性能的探针针头和电性能测试仪器组成。探针台可以对半导体芯片、集成电路和其他微电子器件进行直接的电性能测试,从而为研究和生产提供有价…

Docker部署Vue+Springboot项目

一、部署Springboot项目 1.1先将本地的java项目打成jar包。 再右上角进行maven操作。 1.2将jar包上传到服务器当中。 先再目录/home 下创建一个文件夹(classRoom)用于存放后端打镜像时需要的文件。 如果是服务器的话可以直接将文件拖拽到想要转移的地方…

python数据结构与算法-15_堆与堆排序

堆(heap) 前面我们讲了两种使用分治和递归解决排序问题的归并排序和快速排序,中间又穿插了一把树和二叉树, 本章我们开始介绍另一种有用的数据结构堆(heap), 以及借助堆来实现的堆排序,相比前两种排序算法要稍难实现一些。 最后我…

Unity UI设计 软件构造实验报告

实验1: 仿真系统的UI主界面设计 1.实验目的 (1)熟悉Unity中UI界面的设计与编写; (2)熟悉UI界面中场景转换,UI与场景内容相互关联的方式。 (3)熟悉Unity中MySQL数据库的操作 2.实验内容 新建…

分布式锁之基于redis实现分布式锁(二)

2. 基于redis实现分布式锁 2.1. 基本实现 借助于redis中的命令setnx(key, value),key不存在就新增,存在就什么都不做。同时有多个客户端发送setnx命令,只有一个客户端可以成功,返回1(true);其他…

在线视频课程教育系统源码/网课网校/知识付费/在线教育系统/在线课程培训系统源码

源码简介: 在线视频课程教育系统源码,作为网课/网校/知识付费/在线教育系统,它有文章付费阅读在线点播自动发货付费阅读VIP会员系统等功能。它是实用的在线课程培训系统源码。 发货100-在线视频课程教育系统,它是一款功能实用的…

PC8250(CC-CV控制)5V/8A同步降压恒流恒压软启动带EN功能只需极少外围元件

概述 PC8250是一个同步降压转换器输出电流至8A。它的设计允许操作电源电压范围从9V到42V。外部关闭功能可以通过逻辑电平来控制COMP/EN引脚下降,然后进入待机模式。外部补偿使反馈控制具有良好的线路和负载调节,外部设计灵活。PC8250在CC(恒定…

【C语言】深入解开指针(四)

🌈write in front :🔍个人主页 : 啊森要自信的主页 ✏️真正相信奇迹的家伙,本身和奇迹一样了不起啊! 欢迎大家关注🔍点赞👍收藏⭐️留言📝>希望看完我的文章对你有小小的帮助&am…

基于Pytorch框架多人多摄像头摔倒跌倒坠落检测系统

欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 深度学习在计算机视觉领域的应用已经取得了显著的进展,特别是在多人多摄像头场景下的摔倒跌倒检测。通过…

OpenSearch开发环境安装Docker和Docker-Compose两种方式

文章目录 简介常用请求创建映射写入数据查询数据其他 安装Docker方式安装OpenSearch安装OpenSearchDashboard Docker-Compose方式Docker-Compose安装1.设置主机环境2.下载docker-compose.yml文件3.启动docker-compose4.验证 问题问题1:IPv4 forwarding is disabled.…