贝尔曼最优方程【BOE】

强化学习笔记

主要基于b站西湖大学赵世钰老师的【强化学习的数学原理】课程,个人觉得赵老师的课件深入浅出,很适合入门.

第一章 强化学习基本概念
第二章 贝尔曼方程
第三章 贝尔曼最优方程


文章目录

  • 强化学习笔记
  • 一、最优策略
  • 二、贝尔曼最优方程(BOE)
  • 三、BOE的求解
    • 1 求解方法
    • 2 实例
  • 四、BOE的最优性
  • 参考资料


上一节讲了贝尔曼方程,这一节继续在贝尔曼方程的基础上讲贝尔曼最优方程,后面的策略迭代和值迭代算法都是根据贝尔曼最优方程来的.

一、最优策略

强化学习的最终目标是获得最优策略,所以有必要首先定义什么是最优策略。该定义基于状态值,比如,我们考虑两个给定策略 π 1 \pi_1 π1 π 2 \pi_2 π2。若任一状态 π 1 \pi_1 π1的状态值大于等于 π 2 \pi_2 π2的状态值,即:
v π 1 ( s ) ≥ v π 2 ( s ) , ∀ s ∈ S , v_{\pi_1}(s)\geq v_{\pi_2}(s),\quad\forall s\in\mathcal{S}, vπ1(s)vπ2(s),sS,
那么我们称 π 1 \pi_1 π1是比 π 2 \pi_2 π2更好的策略.最优策略就是所有可能的策略中最好的,定义如下:

截屏2024-03-19 16.34.52

如何得到这个策略呢?需要求解贝尔曼最优方程.

二、贝尔曼最优方程(BOE)

贝尔曼最优方程(Bellman Optimal Equation,BOE),就是最优策略条件下的贝尔曼方程
v ( s ) = max ⁡ π ∑ a π ( a ∣ s ) ( ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v ( s ′ ) ) , ∀ s ∈ S = max ⁡ π ∑ a π ( a ∣ s ) q ( s , a ) s ∈ S \begin{aligned} v\left(s\right)& =\max_{\pi}\sum_{a}\pi(a|s)\left(\sum_{r}p(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v(s')\right),\quad\forall s\in\mathcal{S} \\ &=\max_{\pi}\sum_{a}\pi\left(a|s\right)q\left(s,a\right)\quad s\in{\mathcal S} \end{aligned} v(s)=πmaxaπ(as)(rp(rs,a)r+γsp(ss,a)v(s)),sS=πmaxaπ(as)q(s,a)sS
注意:

  1. p ( r ∣ s , a ) , p ( s ′ ∣ s , a ) p(r|s,a),p(s^{\prime}|s,a) p(rs,a),p(ss,a) 给定
  2. v ( s ) , v ( s ′ ) v(s),v(s^{\prime}) v(s),v(s) 是需要计算的变量
  3. π \pi π为优化变量

我们可以发现贝尔曼最优方程存在两个未知数 v v v π \pi π,一个方程怎么求解两个未知数呢?我们以下列式子说明,是可以求解的。
截屏2024-03-17 15.26.11

也就是说在求解时,可以固定一个变量,先求max的变量.

截屏2024-03-17 15.28.38

受上面例子的启发,考虑到 ∑ a π ( a ∣ s ) = 1 \sum_a\pi(a|s)=1 aπ(as)=1,我们有:

υ ( s ) = max ⁡ π ∑ a π ( a ∣ s ) ( ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v ( s ′ ) ) , = max ⁡ π ∑ a π ( a ∣ s ) q ( s , a ) = max ⁡ a ∈ A ( s ) q ( s , a ) \begin{aligned} \upsilon(s)& \begin{aligned}=\max_{\color{red}{\pi}}\sum_{a}\pi(a|s)\left(\sum_{r}p(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v(s')\right),\end{aligned} \\ &=\max_{\color{red}{\pi}}\sum_{a}\color{red}{\pi(a|s)}q(s,a) \\ &=\max_{\color{red}{a\in\mathcal{A}(s)}}q(s,a) \end{aligned} υ(s)=πmaxaπ(as)(rp(rs,a)r+γsp(ss,a)v(s)),=πmaxaπ(as)q(s,a)=aA(s)maxq(s,a)
我们通过先对 π \pi π变量求max,最后将问题转换为:
v ( s ) = max ⁡ a ∈ A ( s ) q ( s , a ) v(s)=\max_{\color{red}{a\in\mathcal{A}(s)}}q(s,a) v(s)=aA(s)maxq(s,a)而这个方程与 π \pi π无关了,只有一个变量,那就是 v ( s ) v(s) v(s)(向量形式),如何求解这个方程呢?下面介绍如何用迭代法进行求解.

三、BOE的求解

1 求解方法

我们考虑BOE的向量形式:
v = f ( v ) = max ⁡ π ( r π + γ P π v ) v=f(v)=\max_{\pi}(r_\pi+\gamma P_\pi v) v=f(v)=πmax(rπ+γPπv)而这个函数 f f f是一个压缩映射,压缩常数为 γ \gamma γ,证明见参考资料1的对应章节。什么是压缩映射?
定义(压缩映射)

如果存在 α ∈ ( 0 , 1 ) \alpha\in(0,1) α(0,1),使得函数 g g g ∀ x 1 , x 2 ∈ dom ⁡ g \forall x_1,x_2\in \operatorname{dom} g x1,x2domg满足
∥ g ( x 1 ) − g ( x 2 ) ∥ ≤ α ∥ x 1 − x 2 ∥ \|g(x_1)-g(x_2)\|\leq\alpha\|x_1-x_2\| g(x1)g(x2)αx1x2则我们称 g g g为一个压缩映射,称常数 α \alpha α为压缩常数.

f f f是压缩映射有什么用呢?这里需要先介绍一下压缩映射原理.

定理(压缩映射原理)

g g g [ a , b ] [a,b] [a,b] 上的一个压缩映射,则

  1. g g g [ a , b ] [ a, b] [a,b]存在唯一的不动点 ξ = g ( ξ ) \xi=g\left(\xi\right) ξ=g(ξ) ;
  2. 任何初始值 x 0 ∈ [ a , b ] x_0\in[a,b] x0[a,b] 和递推公式
    x n + 1 = g ( x n ) , n ∈ N ∗ x_{n+1}=g\left(x_n\right),n\in N^* xn+1=g(xn)nN 生成的数列 { x n } \{x_n\} {xn} 一定收敛于 ξ \xi ξ.

这也就是说,压缩映像原理给出了一个求不动点的方法,而BOE的 f f f是压缩映射,因此我们有

截屏2024-03-19 19.29.54

具体来看每一次迭代怎么算:

截屏2024-03-19 19.32.10

当我们计算每个状态 s s s时,我们由 v k ( s ′ ) v_k(s') vk(s)可以计算得到 q k ( s , a ) q_k(s,a) qk(s,a),然后再求最大就得到 v k + 1 ( s ) v_{k+1}(s) vk+1(s)了。值得注意的是上述方程右端取得最优值时,我们有:
π k + 1 ( a ∣ s ) = { 1 a = a ∗ , 0 a ≠ a ∗ . \pi_{k+1}(a|s)=\begin{cases} 1 & a=a^*,\\ 0 & a\neq a^*. \end{cases} πk+1(as)={10a=a,a=a.其中 a ∗ = arg ⁡ max ⁡ a q k ( s , a ) a^*=\arg\max\limits_a q_k(s,a) a=argamaxqk(s,a),这个策略被称为greedy policy,也就是每次都选择动作值(q值)最大的动作.

Note:

  • 值得注意的是,任意给 v 0 ∈ dom ⁡ f v_0\in\operatorname{dom} f v0domf,都能收敛到不动点.

2 实例

我们考虑如下这样一个问题,还是智能体走格子:

  • 状态集: s 1 , s 2 , s 3 s_1,s_2,s_3 s1,s2,s3其中 s 2 s_2 s2是目标状态.
  • 动作集: a l , a 0 , a r a_l,a_0,a_r al,a0,ar分别代表向左、原地不动、向右.
  • 奖励:进入 s 2 s_2 s2+1,走出格子-1。

截屏2024-03-19 19.45.20
回顾上一章讲动作值函数和状态值函数的关系,我们可以写出 q ( s , a ) q(s,a) q(s,a) v ( s ) v(s) v(s)的关系:
截屏2024-03-19 19.48.32
下面给定一个 v ( s ) v(s) v(s)的初始值,进行迭代:
截屏2024-03-19 19.53.21

显然,从直观上我们知道当前策略已经是最好的了。如果继续进行迭代,得到的策略不会再改变了,那么迭代算法怎么停止呢?停止准则可以通过如下公式进行判断:
∥ v k + 1 − v k ∥ ≤ ϵ \|v_{k+1}-v_k\|\leq\epsilon vk+1vkϵ其中 ϵ \epsilon ϵ是一个给定的很小的值,也就是相邻两次 v v v相差很小时,我们认为 v v v已经逼近精确值了.

四、BOE的最优性

上面介绍怎么求解BOE的过程中,我们同时通过greedy policy的方法得到了最优策略:
π ∗ = arg ⁡ max ⁡ π ( r π + γ P π v ∗ ) \pi^*= \arg\max\limits_\pi (r_\pi+\gamma P_\pi v^*) π=argπmax(rπ+γPπv)其中 v ∗ v^* v π ∗ \pi^* π对应的状态值,那么求解贝尔曼最优方程得到的这个 π ∗ \pi^* π是不是最优策略呢?有如下定理进行保证.

截屏2024-03-19 20.08.54

这个定理保证了,我们通过求解BOE得到的策略是最优策略,证明见参考资料1的对应章节.

截屏2024-03-19 20.10.41

参考资料

  1. Zhao, S. Mathematical Foundations of Reinforcement Learning. Springer Nature Press and Tsinghua University Press.
  2. Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.

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

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

相关文章

【C++ 函数参数】指针类型和指针引用类型的区别

目录 0 引言1 参数是指针类型2 参数是指针的引用3 总结 🙋‍♂️ 作者:海码007📜 专栏:C专栏💥 标题:【C 函数参数】指针类型和指针引用类型的区别❣️ 寄语:人生的意义或许可以发挥自己全部的潜…

对外开放接口的Appkey和Secret应该如何设置?

文章目录 appkey和Secret 分别是什么?App keyapp secret Appkey和Secret 因遵循什么原则?代码示例随机生成有效的appkey校验Appkey调用效果 小结 appkey和Secret 分别是什么? App key App key简称API接口验证序号,是用于验证API…

C++ - 类和对象(上)

目录 一、类的定义 二、访问限定符 public(公有) protected(保护) private(私有) 三、类声明和定义分离 四、外部变量和成员变量的区别与注意 五、类的实例化 六、类对象的模型 七、类的this指针…

linux系统编程 socket part2

报式套接字 1.动态报式套接字2.报式套接字的广播3.报式套接字的多播4.UDP协议分析4.1.丢包原因4.2.停等式流量控制 接linux系统编程 socket part1 1.动态报式套接字 在之前的例子上,发送的结构体中的名字由定长改变长。可以用变长结构体。 变长结构体是由gcc扩展的…

主流电商平台淘宝/1688/京东电商数据实时采集监测|电商API接口接入

电商大数据平台基于网络主流电商平台淘宝/1688/京东电商数据进行搭建,全面监测了包含淘宝、京东、苏宁、美团、大众点评等共计100余个主流电商交易平台,并凭借多年的电子商务数据分析挖掘经验积累形成的电商数据清洗体系和挖掘模型,能高效完成…

ARIMA

一.数据平稳性与差分法 1.平稳性: 2.差分法: 错开时间点,使得数据可以平稳 原数据➡️一阶差分➡️二阶差分: 二、arima 1.自回归模型 2.移动平均模型 关注的是误差项的累积 3.arma p d(几阶差分) q自己指定 4.总…

分手我见得多了,怎么软件也玩分手?

网管小贾 / sysadm.cc 今年年初,我们就注意到了一件忒奇怪的事儿。 我们公司的同事小孙,以前人长得高高瘦瘦,做人做事也是谨小慎微、内敛腼腆,怎么突然间变得容光焕发、大大咧咧,脸上肚子上也多了几斤肉,整…

基于ssm的酒店民宿管理系统的设计与实现

系统主要功能介绍: 1、登录:输入账号密码进行登录,登录后才能进行相应的操作 2、客房管理:客房管理主要是酒店预订,可以选择不同的房间,比如大床房,家庭房等,入住办理,…

【力扣刷题日记】1076.项目员工II

前言 练习sql语句,所有题目来自于力扣(https://leetcode.cn/problemset/database/)的免费数据库练习题。 今日题目: 1076.项目员工II 表:Project 列名类型project_idintemployee_idint (project_id, employee_id)…

AIGC实战——Transformer模型

AIGC实战——Transformer模型 0. 前言1. T52. GPT-3 和 GPT-43. ChatGPT小结系列链接 0. 前言 我们在 GPT (Generative Pre-trained Transformer) 一节所构建的 GPT 模型是一个解码器 Transformer,它逐字符地生成文本字符串,并使用因果掩码只关注输入字…

代码随想录算法训练营第五十天|123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV

123.买卖股票的最佳时机III 刷题https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/文章讲解https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html视频讲解https://www…

Arduino中的map函数

一、案例 val analogRead(dyPin); //读取模拟口的模拟量数值 dyValuemap(val,0,1023,0,500);//这个函数是将电位器调节的模拟量的值按比例转换成对应的电压量 问题,为什么不是0~499呢? 其实也行↓ 当map(val, 0, 1023, 0, 500)被调用时&#xff0…

YiYi-Web项目介绍

YiYi-Web项目介绍 1. 简介2. 使用2.1 后端开发环境2.2 前端开发环境 3. 测试环境:4. 更新日志5. 打包情况6.项目截图 本项目前端是html、css、js、jQuery基础技术。 后端都是最新的SpringBoot技术,不分离版本, 是最基础的项目开发教程&#x…

yolov5训练并生成rknn模型部署在RK3588开发板上,实现NPU加速推理

简介 RK3588是瑞芯微(Rockchip)公司推出的一款高性能、低功耗的集成电路芯片。它采用了先进的28纳米工艺技术,并配备了八核心的ARM Cortex-A76和Cortex-A55处理器,以及ARM Mali-G76 GPU。该芯片支持多种接口和功能,适…

atoi函数详解

atoi函数使用方法 在c官网中是这样介绍atoi函数的 通俗的讲就是把字符串中的字符数字转换为整形数字,遇到空格就跳过,如果在字符串开始遇到不是有效的整数比如说abc就直接返回0,如果遇到像这种情况123abc345这个就只返回123,这个…

申请Github Education获取免费Copilot权限(2024.3.18实测成功)

起因:旧帐户Copilot权限被封 我已经离开Github Copilot就无法独自耐着性子写代码了(懒惰AI成瘾性),这两天Github Copilot不知道为什么在大规模封号,我不幸也被封号了(禁用掉了Github Copilot权限&#xff…

大数据技术原理与应用 01.大数据概述

不可以垂头丧气,会显矮 —— 24.3.24 参考学习:厦门大学 林子雨老师 大数据技术原理与应用 一、大数据时代 大数据概念、影响、应用、关键技术 大数据与云计算、物联网的关系 ①三次信息化浪潮时代 ②第三次信息化浪潮的技术支撑 1>存储设备容量不断…

微服务(基础篇-003-Nacos)

目录 Nacos注册中心(1) 认识和安装Nacos(1.1) Nacos快速入门(1.2) 服务注册到Nacos(1.2.1) Nacos服务分级存储模型(1.3) 配置集群(1.3.1) 根据集群修改…

[ Linux ] git工具的基本使用(仓库的构建,提交)

1.安装git yum install -y git 2.打开Gitee,创建你的远程仓库,根据提示初始化本地仓库(这里以我的仓库为例) 新建好仓库之后跟着网页的提示初始化便可以了 3.add、commit、push三板斧 git add . //add仓库新增(变…

阿里云倚天云服务器怎么样?如何收费?

阿里云倚天云服务器CPU采用倚天710处理器,租用倚天服务器c8y、g8y和r8y可以享受优惠价格,阿里云服务器网aliyunfuwuqi.com整理倚天云服务器详细介绍、倚天710处理器性能测评、CIPU架构优势、倚天服务器使用场景及生态支持: 阿里云倚天云服务…