网站建设仟首先金手指12,麦德龙网上商城,福州公司建站模板,网站管理员怎么联系贝尔曼公式 前言1、Motivating examples2、state value3、Bellman equation:Derivation4、Bellman equation:Matrix-vector form4、Bellman equation:Solve the state value5、Action value 前言
本文来自西湖大学赵世钰老师的B站视频。本节课主要介绍贝尔曼公式。 本节课概要… 贝尔曼公式 前言1、Motivating examples2、state value3、Bellman equation:Derivation4、Bellman equation:Matrix-vector form4、Bellman equation:Solve the state value5、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是Rt1跳到下一个状态是St1。t指的是当前时刻t1指的是下一时刻。 St、At、Rt1都是随机变量这也就意味着我们可以求解它们的期望。这样单步的过程可以推广到多步的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得到Rt1和St1以此类推得到了上图中的一个trajectory。这样的一个trajectory可以计算它的discounted return Gt从上图推导后的公式来看Gt就等于我立刻能得到的immediate reward Rt1再加上从下一时刻出发得到的Gt1乘以discount rate γ。 从上图可以看出state value可以用蓝色的两个期望来表示分别计算这两个期望就能得到贝尔曼公式。下图就是第一个期望的计算方法 第一项期望实际上就是immediate rewards的mean第二项的期望公式见下图 第二项是从当前状态s出发所得到的下一时刻的return的mean。从当前状态出发可以有多个选择可以跳到s撇跳到不同s撇的概率是p(s撇|s)跳到s撇得到的期望值是E(Gt1|Sts,St1s撇)E(Gt1|Sts,St1s撇)指的是当前状态是s下一时刻状态是s撇计算从下一个状态出发所得到的return的mean。E(Gt1|Sts,St1s撇)中的Sts是可以去掉的因为我已经知道了下一个状态是s撇就不用关心之前是什么状态了。E(Gt1|St1s撇)就是针对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实际上是代表了他的价值如果一个状态价值高说明了这个状态是值得我们往那个方向走的在上图中为什么s2s3s4的价值高呢是因为他们离target area是比较近的而s1离得较远。计算得到这个状态值之后我们就可以去改进这个策略慢慢的我们就可以得到最优的策略。
4、Bellman equation:Matrix-vector form
在上节中我们介绍了贝尔曼公式的推导这节来介绍贝尔曼公式的矩阵和向量形式。
rπ(s)是从当前状态出发得到了所有immediate reward的平均值。上式红色画的意思是展开相乘。 上图中[Pπ]ij代表第i行第j列的元素是从si跳到sj的概率[Pπ]ij这个矩阵也被称为状态转移矩阵。 上图是当n4时我所得到的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依次类推就会得到序列{v0v1v2…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 return。action value指的是agent从一个状态出发并且选择一个action之后得到的average return。 为什么要关注action value实际上我们一直讨论的是强化学习中的策略策略指的是在一个状态我要选择什么样的actionaction有很多具体选择哪一个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就是对每一个状态都存在这样一个式子。
