贝尔曼方程【Bellman Equation】

强化学习笔记

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

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


文章目录

  • 强化学习笔记
  • 一、状态值函数贝尔曼方程
  • 二、贝尔曼方程的向量形式
  • 三、动作值函数
  • 参考资料


第一章我们介绍了强化学习的基本概念,本章介绍强化学习中一个重要的概念——贝尔曼方程.

一、状态值函数贝尔曼方程

贝尔曼方程(Bellman Equation),也称为贝尔曼期望方程,用于计算给定策略 π \pi π时价值函数在策略指引下所采轨迹上的期望。考虑如下一个随机轨迹:

S t → A t R t + 1 , S t + 1 → A t + 1 R t + 2 , S t + 2 → A t + 2 R t + 3 , … \begin{aligned} &&&&S_t\xrightarrow{A_t}R_{t+1},S_{t+1}\xrightarrow{A_{t+1}}R_{t+2},S_{t+2}\xrightarrow{A_{t+2}}R_{t+3},\ldots \\ \end{aligned} StAt Rt+1,St+1At+1 Rt+2,St+2At+2 Rt+3,
那么累积回报 G t G_t Gt可以写成如下形式:
G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + … , = R t + 1 + γ ( R t + 2 + γ R t + 3 + … ) , = R t + 1 + γ G t + 1 . \begin{aligned} G_t &=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\ldots, \\ &=R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\ldots), \\ &=R_{t+1}+\gamma G_{t+1}. \end{aligned} Gt=Rt+1+γRt+2+γ2Rt+3+,=Rt+1+γ(Rt+2+γRt+3+),=Rt+1+γGt+1.
状态值函数的贝尔曼方程为:

v π ( s ) ≐ E π [ G t ∣ S t = s ] = E π [ R t + 1 + γ G t + 1 ∣ S t = s ] = ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] , ∀ s ∈ S . \begin{aligned} v_{\pi}(s)& \doteq\mathbb{E}_{\pi}[G_{t}\mid S_{t}=s] \\ &=\mathbb{E}_{\pi}[R_{t+1}+\gamma G_{t+1}\mid S_{t}=s] \\ &=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\Big[r+\gamma v_\pi(s')\Big],\quad\forall s\in\mathcal{S}. \end{aligned} vπ(s)Eπ[GtSt=s]=Eπ[Rt+1+γGt+1St=s]=aπ(as)s,rp(s,rs,a)[r+γvπ(s)],sS.

  • 由值函数的定义出发,得到了一个关于 v v v的递推关系

下面再来详细的推导一下贝尔曼方程,由回报的定义,可以将 G t G_t Gt拆成两部分:
v π ( s ) = E [ G t ∣ S t = s ] = E [ R t + 1 + γ G t + 1 ∣ S t = s ] = E [ R t + 1 ∣ S t = s ] + γ E [ G t + 1 ∣ S t = s ] . \begin{aligned} v_{\pi}\left(s\right)& =\mathbb{E}[G_{t}|S_{t}=s] \\ &=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_{t}=s] \\ &=\mathbb{E}[R_{t+1}|S_{t}=s]+\gamma\mathbb{E}[G_{t+1}|S_{t}=s]. \end{aligned} vπ(s)=E[GtSt=s]=E[Rt+1+γGt+1St=s]=E[Rt+1St=s]+γE[Gt+1St=s].
首先考虑第一部分 E [ R t + 1 ∣ S t = s ] \mathbb{E}[R_{t+1}|S_t=s] E[Rt+1St=s],全概率公式的应用:

E [ R t + 1 ∣ S t = s ] = ∑ a π ( a ∣ s ) E [ R t + 1 ∣ S t = s , A t = a ] = ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r . \begin{aligned}\mathbb{E}[R_{t+1}|S_t=s]&=\sum_a\pi(a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\&=\sum_a\pi(a|s)\sum_rp(r|s,a)r. \end{aligned} E[Rt+1St=s]=aπ(as)E[Rt+1St=s,At=a]=aπ(as)rp(rs,a)r.
再来考虑第二部分 E [ G t + 1 ∣ S t = s ] \mathbb{E}[G_{t+1}|S_t=s] E[Gt+1St=s],第二个等式用到马尔可夫性质和全概率公式:

E [ G t + 1 ∣ S t = s ] = ∑ s ′ E [ G t + 1 ∣ S t = s , S t + 1 = s ′ ] p ( s ′ ∣ s ) = ∑ s ′ E [ G t + 1 ∣ S t + 1 = s ′ ] p ( s ′ ∣ s ) = ∑ s ′ v π ( s ′ ) p ( s ′ ∣ s ) = ∑ v π ( s ′ ) ∑ p ( s ′ ∣ s , a ) π ( a ∣ s ) . \begin{aligned} \mathbb{E}\left[G_{t+1}|S_{t}=s\right]& =\sum_{s^{\prime}}\mathbb{E}[G_{t+1}|S_{t}=s,S_{t+1}=s^{\prime}]p(s^{\prime}|s) \\ &=\sum_{s'}\mathbb{E}[G_{t+1}|S_{t+1}=s']p(s'|s) \\ &=\sum_{s^{\prime}}v_{\pi}(s^{\prime})p(s^{\prime}|s) \\ &=\sum v_{\pi}(s^{\prime})\sum p(s^{\prime}|s,a)\pi(a|s). \end{aligned} E[Gt+1St=s]=sE[Gt+1St=s,St+1=s]p(ss)=sE[Gt+1St+1=s]p(ss)=svπ(s)p(ss)=vπ(s)p(ss,a)π(as).
以上两部分合起来:
v π ( s ) = E [ R t + 1 ∣ S t = s ] + γ E [ G t + 1 ∣ S t = s ] , = ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r ⏟ mean of immediate rewards + γ ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) , ⏟ mean of future rewards = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] , ∀ s ∈ S = ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] , ∀ s ∈ S . \begin{aligned} v_{\pi}\left(s\right)& =\mathbb{E}[R_{t+1}|S_{t}=s]+\gamma\mathbb{E}[G_{t+1}|S_{t}=s], \\ &\begin{aligned}=\underbrace{\sum_a\pi(a|s)\sum_rp(r|s,a)r}_{\text{mean of immediate rewards}}+\underbrace{\gamma\sum_a\pi(a|s)\sum_{s'}p(s'|s,a)v_\pi(s'),}_{\text{mean of future rewards}}\end{aligned} \\ &=\sum_a\pi(a|s)\left[\sum_rp(r|s,a)r+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v_\pi(s^{\prime})\right],\forall s\in\mathcal{S}\\ &=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\Big[r+\gamma v_\pi(s')\Big],\quad \forall s\in\mathcal{S}. \end{aligned} vπ(s)=E[Rt+1St=s]+γE[Gt+1St=s],=mean of immediate rewards aπ(as)rp(rs,a)r+mean of future rewards γaπ(as)sp(ss,a)vπ(s),=aπ(as)[rp(rs,a)r+γsp(ss,a)vπ(s)],sS=aπ(as)s,rp(s,rs,a)[r+γvπ(s)],sS.

Note:

  • 贝尔曼公式给出了值函数的一个递推关系式
  • 当前状态的值函数,可以由下一状态的值函数完全确定

下面的树状图形象的刻画了贝尔曼方程中几个求和符合,各变量之间的关系:

截屏2024-03-17 12.29.55

实例:
仍然是agent-网格问题,绿色箭头表示当前策略:
截屏2024-03-19 14.56.47

截屏2024-03-19 14.57.14

二、贝尔曼方程的向量形式

我们将贝尔曼公式拆成两项之和的形式:
v π ( s ) = r π ( s ) + γ ∑ s ′ p π ( s ′ ∣ s ) v π ( s ′ ) , v_\pi(s)=r_\pi(s)+\gamma\sum_{s^{\prime}}p_\pi(s^{\prime}|s)v_\pi(s^{\prime}), vπ(s)=rπ(s)+γspπ(ss)vπ(s),其中:
r π ( s ) ≜ ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r , p π ( s ′ ∣ s ) ≜ ∑ a π ( a ∣ s ) p ( s ′ ∣ s , a ) . \begin{aligned}r_\pi(s)\triangleq\sum_a\pi(a|s)\sum_rp(r|s,a)r,\quad p_\pi(s'|s)\triangleq\sum_a\pi(a|s)p(s'|s,a)\end{aligned}. rπ(s)aπ(as)rp(rs,a)r,pπ(ss)aπ(as)p(ss,a).

假设状态为 s i ( i = 1 , … , n ) s_i(i=1, \ldots, n) si(i=1,,n),对于状态 s i s_i si, Bellman方程为:
v π ( s i ) = r π ( s i ) + γ ∑ s j p π ( s j ∣ s i ) v π ( s j ) ∀ i = 1 , … , n v_\pi\left(s_i\right)=r_\pi\left(s_i\right)+\gamma \sum_{s_j} p_\pi\left(s_j \mid s_i\right) v_\pi\left(s_j\right) \quad\forall i=1,\ldots ,n vπ(si)=rπ(si)+γsjpπ(sjsi)vπ(sj)i=1,,n

把所有状态的方程放在一起重写成矩阵-向量的形式
v π = r π + γ P π v π v_\pi=r_\pi+\gamma P_\pi v_\pi vπ=rπ+γPπvπ
其中

  • v π = [ v π ( s 1 ) , … , v π ( s n ) ] T ∈ R n v_\pi=\left[v_\pi\left(s_1\right), \ldots, v_\pi\left(s_n\right)\right]^T \in \mathbb{R}^n vπ=[vπ(s1),,vπ(sn)]TRn
  • r π = [ r π ( s 1 ) , … , r π ( s n ) ] T ∈ R n r_\pi=\left[r_\pi\left(s_1\right), \ldots, r_\pi\left(s_n\right)\right]^T \in \mathbb{R}^n rπ=[rπ(s1),,rπ(sn)]TRn
  • P π ∈ R n × n P_\pi \in \mathbb{R}^{n \times n} PπRn×n,其中 [ P π ] i j = p π ( s j ∣ s i ) \left[P_\pi\right]_{i j}=p_\pi\left(s_j \mid s_i\right) [Pπ]ij=pπ(sjsi)为状态转移矩阵

实例:

截屏2024-03-19 15.15.54

给定一个策略,算出出相应的状态值被称为策略评估,这是强化学习的一个基本问题。而通过上面的介绍我们知道要得到state value,可以求解贝尔曼方程。由刚刚介绍的贝尔曼方程矩阵形式:
v π = r π + γ P π v π v_\pi=r_\pi+\gamma P_\pi v_\pi vπ=rπ+γPπvπ易得:
v π = ( I − γ P π ) − 1 r π v_\pi=(I-\gamma P_\pi)^{-1}r_\pi vπ=(IγPπ)1rπ
但矩阵的求逆是 O ( n 3 ) O(n^3) O(n3)的复杂度,当矩阵很大时,求解效率很低。所以我们通常不用这个方法来解贝尔曼方程,而是采用迭代法(下一章详细介绍).迭代法格式如下:
v k + 1 = r π + γ P π v k \begin{aligned}v_{k+1}=r_\pi+\gamma P_\pi v_k\end{aligned} vk+1=rπ+γPπvk给定一个初始值 v 0 v_0 v0,可以得到迭代序列 { v 0 , v 1 , v 2 , … } . \{v_0,v_1,v_2,\ldots\}. {v0,v1,v2,}. 并且可以证明

v k → v π = ( I − γ P π ) − 1 r π , k → ∞ v_k\to v_\pi=(I-\gamma P_\pi)^{-1}r_\pi,\quad k\to\infty vkvπ=(IγPπ)1rπ,k
也就是可以用迭代法,通过有限次迭代得到一个近似值.

三、动作值函数

由状态值函数与动作值函数的关系,我们有:
v π ( s ) = ∑ a π ( a ∣ s ) q π ( s , a ) . v_\pi(s)=\sum_a\pi(a|s)q_\pi(s,a). vπ(s)=aπ(as)qπ(s,a).
上小节关于状态值函数的贝尔曼方程为:
v π ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] v_{\pi}(s)=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\Big[r+\gamma v_\pi(s')\Big] vπ(s)=aπ(as)s,rp(s,rs,a)[r+γvπ(s)]
两式对比我们可以得到动作值函数的贝尔曼方程
q π ( s , a ) = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] q_\pi(s,a)=\sum_{s',r}p(s',r|s,a)\Big[r+\gamma v_\pi(s')\Big] qπ(s,a)=s,rp(s,rs,a)[r+γvπ(s)]
总结一下:

截屏2024-03-17 13.15.54

参考资料

  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/475030.html

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

相关文章

鸿蒙开发之导航栏tabs(类似Android tablayout)

当页面信息较多时,为了让用户能够聚焦于当前显示的内容,需要对页面内容进行分类,提高页面空间利用率。Tabs组件可以在一个页面内快速实现视图内容的切换,一方面提升查找信息的效率,另一方面精简用户单次获取到的信息量…

IDEA中使用git

从远程仓库拉取代码 更新代码 提交代码 推送代码到远程仓库 如果代码只是进行了commit,即只提交到了本地仓库而并未推送要进行推送点击push按钮即可: 分支操作 新建分支 切换分支、删除分支、其余分支操作 git面板介绍 reset操作、rebase操作、rev…

【LeetCode: 224. 基本计算器 + 模拟 + 栈】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,…

matlab 条件数的倒数

目录 一、概述1、算法概述2、主要函数3、参考文献二、条件设置错误的矩阵的敏感度三、求解单位矩阵的条件四、参考链接本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、概述 1、算法概述

正则表达式具体用法大全

# 正则表达式: ## 单字符匹配: python # 匹配某个字符串: # text "abc" # ret re.match(b,text) # print(ret.group()) # 点(.):匹配任意的字符(除了\n): # text "\nabc&quo…

前言:为什么C语言最适合编程入门?

前言:为什么C语言最适合编程入门? C语言被认为最适合编程入门的原因主要有以下几点: 基础且强大:C语言是一种基础且强大的编程语言。它提供了对底层硬件的直接访问,让初学者能够更好地理解计算机的工作原理&#xff0…

Unity 学习笔记 5.控制飞机飞行

目录 1.摄像机跟随的方法 2.鼠标按键响应 3.键盘按键响应 4.导入素材 5.让飞机向前飞 6.摄像机跟随飞机移动 7.鼠标控制飞机倾斜 8.键盘控制飞机飞行 下载源码 UnityPackage 1.摄像机跟随的方法 2.鼠标按键响应 3.键盘按键响应 4.导入素材 下载素材 步骤: 将…

python的幼儿园管理系统flask-django-php-nodejs

随着信息时代的来临,过去的传统管理方式缺点逐渐暴露,对过去的传统管理方式的缺点进行分析,采取计算机方式构建幼儿园管理系统。本文通过课题背景、课题目的及意义相关技术,提出了一种活动信息、课程信息、菜谱信息、通知公告、家…

监听键盘按下和弹起事件

<div class"center-container" id"ed-editor-container" tabindex"0"></div> tabindex"0" 让div可获得聚焦 // 编辑器区域键盘事件监听 this.edEditorContainer document.getElementById(ed-editor-container) this.edEd…

【100%成功】从0到1教你开通GPT4.0会员,一年立省1800,拒绝高价代开,免排队无需等待。

我们看下这个网址代开差不多要300&#xff0c;而我用Fomepay每个月才150左右&#xff0c;不需要年费月费&#xff0c;虽然有开卡费用10刀&#xff0c;但是也很划算&#xff0c;你自己算一下&#xff0c;一个月300一年就1千多 点击获取卡&#xff0c;0年费0月费 开卡步骤很简…

卫生间尺寸大揭秘,让你装修不再迷茫。福州中宅装饰,福州装修

卫生间的布局和尺寸因卫生间的大小和设计风格而异。以下是一些常见的布局和尺寸&#xff1a; 1. 洗漱区&#xff1a; 洗手台的宽度一般为600mm&#xff0c;高度为850~900mm。洗手台外边距离障碍物应预留600mm&#xff0c;可容纳人员站立或弯腰时的纵向尺寸。弯腰洗脸横向活动…

Linux/Perfection

Enumeration nmap 用 nmap 扫描了常见的端口&#xff0c;发现对外开放了 22,80&#xff0c;扫描一下详细信息&#xff0c;如下所示 ┌──(kali㉿kali)-[~/vegetable/HTB/Perfection] └─$ nmap -sC -sV -p 22,80 10.10.11.253 -oA nmap Starting Nmap 7.93 ( https://nmap…

Mysql总结(附思维导图)

Mysql Mysql索引 使用 创建主键索引 在对应字段后指定primary_key&#xff1a;id int primary key 创建唯一索引 在对应字段后指定unique_key&#xff1a;name varchar(20) unique 创建普通索引 在创建表的最后&#xff0c;指定某列或某几列&#xff1a;index(name) 创建全…

【JAVA笔记】IDEA配置本地Maven

文章目录 1 配置本地Maven1.1 Maven下载1.2 Maven安装与配置1.2.1 安装1.2.2 配置1.2.2.1 环境配置1.2.2.2 本地仓库配置 2 IDEA设置本地Maven 1 配置本地Maven 1.1 Maven下载 官网&#xff1a;http://maven.apache.org/下载地址&#xff1a;http://maven.apache.org/downloa…

腾讯云优惠券、代金券、折扣券领取方法及使用教程

腾讯云作为国内领先的云计算服务提供商&#xff0c;一直致力于为广大用户提供高效、稳定、安全的云服务。为了吸引用户上云&#xff0c;腾讯云经常推出各种优惠活动&#xff0c;其中就包括腾讯云优惠券。下面小编将详细介绍腾讯云优惠券的相关信息&#xff0c;包括种类、领取入…

Coze知识库新上线!是否真的好用?

近期&#xff0c;Coze知识库工具新上线并迅速引起了行业内的关注。作为一款公认的知识管理和团队协作工具&#xff0c;Coze被赞誉为"团队协作的游戏规则修改者"。那么&#xff0c;Coze是否真的如传闻中那么好用呢&#xff1f; 首先&#xff0c;从优势来看&#xff0c…

考研数学|《660》题这样刷,效率最高!

首先要了解一下660的难度&#xff0c;我认为660的难度是在基础和强化之间的一本习题册。具有一些比较好的选填题目&#xff0c;有些题目可能对初学者来说较为困难&#xff0c;尤其是一些包含二级结论的一些题目。但是对于强化阶段来说&#xff0c;这本题目可能难度较低了一些。…

【鸿蒙HarmonyOS开发笔记】应用数据持久化之通过用户首选项实现数据持久化

概述 应用数据持久化&#xff0c;是指应用将内存中的数据通过文件或数据库的形式保存到设备上。内存中的数据形态通常是任意的数据结构或数据对象&#xff0c;存储介质上的数据形态可能是文本、数据库、二进制文件等。 HarmonyOS标准系统支持典型的存储数据形态&#xff0c;包…

mybatis-plus和mybatis同时引入时,出现的问题

这里同时引入了一个mybatis-plus和mybatis&#xff0c;导致了配置文件里面配置的映射文件一直没生效&#xff0c;一直报错找不到隐私文件 mapper-locations 同时引入是这个是不会生效的 只有用mybatis.mapper-locations配置时才会生效

鸿蒙Harmony应用开发—ArkTS-粒子动画

粒子动画是在一定范围内随机生成的大量粒子产生运动而组成的动画。动画元素是一个个粒子&#xff0c;这些粒子可以是圆点、图片。通过对粒子在颜色、透明度、大小、速度、加速度、自旋角度等维度变化做动画&#xff0c;来营造一种氛围感&#xff0c;比如下雪的动效&#xff0c;…