当前位置:首页> AI教程> Model-Based方法:策略迭代与价值迭代

Model-Based方法:策略迭代与价值迭代

释放双眼,带上耳机,听听看~!
本文讨论了在给定环境情况下,求最大化期望累计收益的RL模型,以及如何评价一个策略的好坏和策略评估方法。

Model-Based方法:策略迭代与价值迭代

在前一章我们已经知道,RL就是在给定了环境p(s′,r∣s,a)p(s’,r|s,a)的情况下,求π(⋅∣s)pi(cdot|s)使得能够最大化期望累计收益E[∑tγtRt]mathbb{E}[sum_t gamma ^t R_t]

p(s′,r∣s,a)p(s’,r|s,a)被称之为模型,如果它是已知的(注意给定和已知不一样,给定只是有输入可以得到输出,但是分布规律并不知道,已知意味着整个分布信息都知道),基于model求解policy的方法被称为model-based方法。

1 如何评价一个策略的好坏?- 策略评估

如何找一个好的策略,这个并不容易,一个容易点的问题是,如何评价一个策略的好坏?很自然能想到用优化目标,即期望累计收益E[∑tγtRt]mathbb{E}[sum_t gamma ^t R_t]去评价。

对于一个确定的策略π(⋅∣s)pi(cdot|s)和modelp(s′,r∣s,a)p(s’,r|s,a),再加上初始状态S0S_0,整个期望可以完全确定,即期望累计收益为Eπ[∑tγtRt∣S0]mathbb{E}^{pi}[sum_t gamma^t R_t|S_0]。我们Vπ(S0)V^{pi}(S_0)来表示,即在策略πpi下,从S0S_0出发能够获得的期望累积收益。

直接用优化目标评价策略还是很难,困难主要来源于他一下把所有步骤全部表示了,为了降低这个难度,考虑只写出一步,其余的步骤利用上面VV的定义递归表示。会让分析变得简单。所以我们尝试变形

Vπ(S0)=E[R0+γR1+…+γnRn∣S0]=E[R0∣S0]+γE[R1+…+γn−1Rn∣S0]=∑rr∑a∑s′p(s′,r∣S0,a)π(a∣S0)+γ∑s′p(s′∣S0)E[R1+…+γn−1Rn∣s′]=∑rr∑a∑s′p(s′,r∣S0,a)π(a∣S0)+γ∑s′∑a′p(s′∣S0,a)π(a∣S0)E[R1+…+γn−1Rn∣s′]=∑rr∑a∑s′p(s′,r∣S0,a)π(a∣S0)+γ∑s′∑a′∑rp(s′,r∣S0,a)π(a∣S0)Vπ(s′)
begin{aligned}

V^pi (S_0) &= mathbb{E}[R_0 + gamma R_1 + … + gamma^n R_n|S_0]

&= mathbb{E}[R_0|S_0] + gamma mathbb{E}[R_1 + … + gamma^{n-1} R_n|S_0]

&= sum_r rsum_{a}sum_{s’}p(s’,r|S_0, a)pi(a|S_0) + gamma sum_{s’}p(s’|S_0)mathbb{E}[R_1 + … + gamma^{n – 1}R_n|s’]

&= sum_r rsum_{a}sum_{s’}p(s’,r|S_0, a)pi(a|S_0) + gamma sum_{s’}sum_{a’}p(s’|S_0, a)pi(a|S_0)mathbb{E}[R_1 + … + gamma^{n – 1} R_n|s’]

&= sum_r rsum_{a}sum_{s’}p(s’,r|S_0, a)pi(a|S_0) + gamma sum_{s’}sum_{a’}sum_{r}p(s’, r|S_0, a)pi(a|S_0)V^pi (s’)

end{aligned}

第一行是定义,第二行是期望的线性性,第三行是把期望的条件换成下一个状态,因为下一个状态不确定,所以需要乘新的概率系数并求和。第四、五行是把p(s′∣s)p(s’|s)利用policy和model表示出来。后面三行主要是条件概率公式的应用。

至此,我们找到了用递归方法表示累积期望收益的办法。

推广至对任何tt时刻的状态StS_t,我们有

Vπ(St)=∑rr∑a∑s′p(s′,r∣St,a)π(a∣St)+γ∑s′∑a∑rp(s′,r∣St,a)π(a∣St)Vπ(s′)V^pi(S_t)=sum_r rsum_{a}sum_{s’}p(s’,r|S_t, a)pi(a|S_t) + gamma sum_{s’}sum_{a}sum_{r}p(s’, r|S_t, a)pi(a|S_t)V^pi (s’)

上面为了严谨使用了最基本的p(s′,r∣s,a)p(s’,r|s,a)π(⋅∣s)pi(cdot|s)表示。如果把被求和的中间量都省略掉,则∑a∑rp(s′,r∣St,a)π(a∣St)≡pπ(s′∣St)sum_{a}sum_{r}p(s’, r|S_t, a)pi(a|S_t)equiv p^pi(s’|S_t),而∑a∑s′p(s′,r∣St,a)π(a∣St)≡pπ(r∣St)sum_{a}sum_{s’}p(s’,r|S_t, a)pi(a|S_t)equiv p^pi(r|S_t)。那方程就简化成了

Vπ(St)=∑rrpπ(r∣St)+γ∑s′pπ(s′∣St)Vπ(s′)V^pi(S_t)=sum_r r p^pi(r|S_t) + gamma sum_{s’} p^pi(s’|S_t) V^pi (s’)

上面这个方程是针对一个状态具体而言的,并不能刻画全貌,为了方便表示,假设状态离散且有限,为Sa,Sb,…S_a, S_b, …,那么V(⋅)V(cdot)其实就是一个向量,它的长度是状态的数量,第ii个位置的数字表示第ii个状态的VV。我们可以用一个向量和矩阵的等式来表示。即

[Vπ(Sa)Vπ(Sb)…Vπ(Sz)]=[∑rrpπ(r∣Sa)∑rrpπ(r∣Sb)…∑rrpπ(r∣Sz)]+γ[pπ(Sa∣Sa)pπ(Sb∣Sa)…pπ(Sz∣Sa)pπ(Sa∣Sb)pπ(Sb∣Sb)…pπ(Sz∣Sb)…………pπ(Sa∣Sz)pπ(Sb∣Sz)…pπ(Sz∣Sz)]⋅[Vπ(Sa)Vπ(Sb)…Vπ(Sz)]
left[

begin{matrix}

V^pi(S_a)

V^pi(S_b)

V^pi(S_z)

end{matrix}

right] =

left[

begin{matrix}

sum_r r p^pi(r|S_a)

sum_r r p^pi(r|S_b)

sum_r r p^pi(r|S_z)

end{matrix}

right] +

gamma left[

begin{matrix}

p^pi(S_a|S_a) & p^pi(S_b|S_a) & … & p^pi(S_z|S_a)

p^pi(S_a|S_b) & p^pi(S_b|S_b) & … & p^pi(S_z|S_b)

… & … & … & …

p^pi(S_a|S_z) & p^pi(S_b|S_z) & … & p^pi(S_z|S_z)

end{matrix}

right] cdot

left[

begin{matrix}

V^pi(S_a)

V^pi(S_b)

V^pi(S_z)

end{matrix}

right]

可以验算一下每一个S带进去都是成立的。

简记为V=R+γPVV = R + gamma P V

这是一个等式,并且含有未知数(未知函数)VV。包含未知数的等式就是方程,所以上面的等式实际上是关于VV的方程。既然是方程,能否把他解出来?只要解出来了,我们就得到了关于给定策略πpi在任何一个状态出发的期望累计收益。就能够评价策略的好坏了!

直接求解这个方程不太容易。但是可以迭代求解:假设我们有一个初始的VV,按照方程右侧的方式计算,就能得到一个新的VV,再次带入右侧,又能得到新的,如果不断迭代,直至有一次我们迭代出来的新VV刚好和迭代之前的VV相同,那就找到了这个方程的解了!

现在只剩最后一个问题:这样做能不能收敛?能的话,我们找到的是唯一解吗,还是有其他解?答案是能,并且是唯一解

注意上面的简记有一个好处,就是很多看上去是变量的StS_t都不存在了,他们实际不过是向量中某个位置上的元素而已。这为后面的证明提供方便。

迭代计算一定可以找到解并且是唯一解。
把函数VV按照方程右侧计算,得到还是一个函数,这种输入和输出都是函数的操作称为算子,所以我们把对方程右侧的计算看作一个算子(术语叫Bellman Policy Operator),用BB表示,那么: BπV=R+γPVB^pi V = R + gamma P V
迭代计算的过程就是对一个初始的V0V_0 不断使用BπB^pi的过程。
接下来我们证明Bellman算子在无穷范数度量空间是一个压缩映射。
Q:什么叫无穷范数?A:就是对一个向量取最大值。
Q: 什么叫度量空间?A: 就是对于所有的元素(我们这里是V向量)定义一种表示元素之间距离的方法,这个距离定义满足正定(元素间距离非负,等于0当且仅当两个元素相同)、对称(a到b的就和b到a的距离一样)、三角不等式(d(a,b) + d(b,c)≤le d(a,c))
Q: 什么叫无穷范数度量空间?A: 对任意两个V1,V2V_1, V_2,我们定义距离∣∣V1−V2∣∣∞=max⁡i(∣V1[i]−V2[i]∣)||V_1-V_2||_infty=max_i(|V_1[i] – V_2[i]|)。注意这里取绝对值后才取最大值,可以自行验证这个距离定义满足度量空间里距离定义的正定、对称和三角不等式
Q: 什么叫压缩映射?
A:对任意的V1,V2V_1, V_2,考察被贝尔曼算子作用后的距离:
∣∣BπV1−BπV2∣∣∞=∣∣R+γPV1−R+γPV2∣∣∞=γmax⁡i(P∣V1−V2∣[i])≤γmax⁡i∣V1−V2∣[i]=γ∣∣V1−V2∣∣∞begin{aligned} ||B^pi V_1 – B^pi V_2||_infty =& ||R+gamma P V_1 – R + gamma P V_2||_infty =& gamma max_i (P|V_1 – V_2|[i]) le& gamma max_i |V_1 – V_2|[i] =& gamma ||V_1 – V_2||_inftyend{aligned}
第一行是距离定义,第二行是抵消合并,第三行是利用了PP矩阵的每一行和等于1,加权平均之后的结果一定比直接取最大小。第四行是距离定义。
所以经过贝尔曼算子操作之后,所有的元素的距离都比之前更近了。那么经过足够多次操作之后,所有的元素都被压缩到一个点上,再运算结果也不会改变了。
这说明贝尔曼算子的操作会收敛,并且会收敛到一个不动点上,对应唯一的VV的解!

2 如何根据评价的VV改进策略?- 策略迭代

上一节说明,通过定义了一个VV算子,然后利用递归的方式简化累计期望收益的表示得到了一个关于VV的方程,然后把方程右侧的操作看作算子,竟然可以迭代收敛,从而找到了VV的解。我们成功实现了评价策略的目标。接下来思考如何根据这个评价改进策略?

在之前的思路里,我们定义了Vπ(s)V^pi(s),他表示在状态ss开始,按照策略πpi交互获得的期望累计收益。这次与之不同是,因为需要考虑动作,所以我们把第一次的动作也作为条件。即定义函数Qπ(s,a)Q^pi(s, a),表示状态ss下采取动作aa,之后按照πpi选取动作,能够获得的期望累积收益。 即:

Qπ(St,At)=E[∑t′=tnγt′−tRt′∣St,At]Q^pi(S_t,A_t) = mathbb{E}[sum_{t’=t}^n gamma^{t’-t} R_t’|S_t, A_t]
我们当然可以按照以前计算VV的思路,把他写成递归的形式表示。但我们已经好不容易求出VV了,所以现在更希望用VV来表示QQ,从而为策略提供指导。其实根据定义很容易看出来

Qπ(s,a)=∑rrp(r∣s,a)+γ∑s′p(s′∣s)Vπ(s′)Q^pi(s,a)= sum_r r p(r|s, a) + gamma sum_{s’} p(s’|s) V^pi(s’)

推导思路是,先计算这一步在状态是ss采取动作aa带来的期望收益,∑rrp(r∣s,a)sum_r r p(r|s, a),然后计算下一状态的期望收益,下一状态的期望收益可以用VV表示,具体转移到那个状态不确定,所以再求一次期望。这些p(r∣s,a)p(r|s, a)p(s′∣s)p(s’|s)可以利用上一节计算VV的方式用p(s′,r∣s,a)p(s’,r|s,a)π(⋅∣s)pi(cdot|s)表示出来,就不写了。

有了QQ,一个直观的策略改进方法是π′(s)=arg⁡max⁡aQπ(s,a)pi'(s)=argmax_a Q^pi(s, a)

为什么这样可以呢? 因为

Vπ′(s)=Qπ(s,π′(s))=max⁡aQπ(s,a)≥∑aπ(a∣s)Q(s,a)=Vπ(s)
begin{aligned}

V^{pi’}(s) =& Q^pi(s,pi'(s))

=& max_a Q^pi(s, a)

ge & sum_a pi(a|s)Q(s, a)

=& V^pi(s)

end{aligned}

第一行是因为策略是确定的,并且选取动作总是基于当前的QQ,不用求期望,第二行是因为新策略取argmax,所以得到的一定是QQ的最大值,第三行是因为最大值一定大于所有值的加权平均,第四行是定义。

也就是说,在有了目前策略的πpi之后,我们对每个状态取argmax的方法,一定可以得到一个能够使VV更大的πpi。而VV就是我们评价策略好坏的标准,越大越好,所以策略得到了改进!再按照前一节的方法计算新策略的VV,然后循环,就可以得到最优策略π∗pi^*了!

此外还发现这里有一个不那么平凡的结论,就是如果一个策略π1pi_1比另一个策略π2pi_2好,那么它的Vπ1V^{pi_1}中的每一个ss对应的数都比Vπ2V^{pi_2}大。这是因为前面的推导对任意ss都成立。直观上我们可能觉得他有可能是有些状态大了,有些状态小了,但事实并不是如此。这个结论很关键。

这里Sutton的书上还特别提到了一个潜在的bug:如果有两个一样好的策略,那如果在策略提升的时候不去和过去的最优策略比较,有可能出现两个策略交替的情况。

广义策略迭代则是指,策略评估和价值迭代的过程都不需要进行充分(这里进行充分对策略评估过程指收敛,对价值迭代过程指遍历更新完全部状态)就进行下一步,这样最终也是可以收敛的。

3 更简单的方法 – 价值迭代

前面的过程中我们先用策略评估,计算VV,然后用VV计算QQ,然后基于QQ改进πpi,然后再计算VV

问题在于,我们都有能力从VV计算出QQ了 (也就是Qπ(s,a)=∑rrp(r∣s,a)+γ∑s′p(s′∣s)Vπ(s′)Q^pi(s,a)= sum_r r p(r|s, a) + gamma sum_{s’} p(s’|s) V^pi(s’)),那能不能直接求出VV的最优取值Vπ∗V^{pi^*},然后直接计算出QQ

这样可以避免反复求VVQQ

此外,我们从QQ改进策略的方法是取argmax,那这种思想能不能直接用到VV上帮助我们找最优策略呢?答案是肯定的。

我们定义一个新的算子Bellman Optimal Operator

B∗V=arg⁡max⁡aR+γPVB^* V = argmax_a {R + gamma PV} 其实这个操作就是取arg⁡max⁡Q(s,a)argmax Q(s,a)的过程。因为Qπ(s,a)=∑rrp(r∣s,a)+γ∑s′p(s′∣s)Vπ(s′)Q^pi(s,a)= sum_r r p(r|s, a) + gamma sum_{s’} p(s’|s) V^pi(s’)。如果表示成矩阵那其实是一样的。

和公式(2)几乎一样可以证明这个最优算子也可以收敛到唯一解。

所以第2节讲的策略评估+策略改进的方法,本质上是先有了一个Vπ1V_{pi_1},然后根据Q改进了一个π2pi_2,然后在第二节最后我们指出Vπ2≥Vπ1V_{pi_2}ge V_{pi_1},所以不断循环我们找到一个一个πpi每一个都比前一个的V大,直至找到了最大的。

现在不再通过QQ去找下一个策略了,而是直接利用Bellman Optimal Operator,这个过程和之前用QQ找是一样的,所以一样能找到最优策略。这样就避免了通过QQ去导出πpi而是直接从VV导出πpi,提高了计算速度。

在实际操作中,价值迭代往往不会分别maintain新旧价值表,而是只维护一张表,需要更新特定状态时直接原地更新,这种异步迭代方法同样有效。

Notes

  • 1 Model-based方法之所以是model-base,就是因为计算VVQQ的过程利用了p(s′,r∣s,a)p(s’,r|s,a)。这带来的最大优势是完全不需要和环境交互就可以求出最优策略。但是多数情况下这个是不知道的。如果问题比较简单,也许可以通过蒙特卡洛估计出p(s′,r∣s,a)p(s’,r|s,a),然后利用价值迭代计算policy。但更多时候环境很复杂,这种方法不适用。

  • 2 当model-base不适用的时候,从历史数据估计累计期望收益计算VVQQ就变成了一个很关键的事情。主要有两种思路,蒙特卡洛采样和时序差分。蒙特卡洛采样是指直接从当前状态出发按照policy采样多个完整的episode然后求平均估计期望。时序差分则是利用推导中递归的思想,用一步或几步的真实reward + 目前的VVQQ的值,实现自举地估计。前者的特点估计是无偏的,但是方差很大(因为是很多步reward求和)。后者的特点是有偏,但方差小(因为只有1步求和,但剩余部分用自己之前的估计,本身不准确)。

  • 3 公式(3)很重要,它说明随便给一个策略,只要取argmax就能得到更好的策略,这个思想在Q-Learning中会再次体现,也是经验重放思想得以应用的关键。因为历史数据混合起来使用,可以看作诸多历史策略的叠加产生的结果,而argmax能够保证新得到的策略一定比之前好。经验重放让数据的利用率得到提高,缓解了RL样本利用低效、数据获取难的问题,非常伟大。

有趣问题:赌徒问题

问题描述:有一个赌局,你初始有一笔钱(整数,范围在1-99),每一轮你可以选择把你手上的钱部分或全部押注,然后抛硬币,硬币向上的概率为0.4,正面向上你可以赢得和你押注数量一样的钱,否则输掉你押注的钱。手上没有钱或大于等于100元结束。求出手上有不同数量钱时的最优策略。

技巧:

  • 如果1)交互过程是有限、2)只有终止状态有reward、3)无折扣,可以为v添加终止状态,并且把值定死成reward。

  • 根据value生成action,不要简单的argmax,这取决于你的精确度到多少,浮点数误差需要忽视。

​这个题目非常奇妙,值得分析。
图中横轴表示状态,纵轴表示策略,每个点是一个策略。
Model-Based方法:策略迭代与价值迭代

  • 首先,50这个状态好,因为这个coin正面朝上概率小,意味着对我不利,我希望尽可能快的结束游戏,所以50的时候all in有助于直接完成,同样道理,51的时候如果只输掉1有助于我回到50的状态。注意这个题是多轮有限的,那么reward会受到持续时间的影响,想最大reward使得我们希望尽可能快的结束游戏。他能保证这是一个好的策略体现了长远眼光,即,充分考虑当前状态输了,也要尽可能落到一个取胜概率大的地方去。
  • 在51这个地方不仅1是一个好的选择,49同样是好的选择,因为你有0.4的概率直接结束,虽然你可能输的很惨变成2,但是100的诱惑是很大的,毕竟他的value是1,0而50只有0.4左右,所以期望其实差不多。因此49和51都是有两个选择的,即要么扔的少一点可能输到50,要么赌个大的,没准一把就赢了。这种情况从50向两边扩展,直至37,68的位置。
  • 37/68两个位置开始出现3个选择。其中有两个action是相邻的,倾向于回到50;还有一个对于左侧37是全押,对右侧是押一个能到100的。总之还是因为50和100的吸引力相似造成的。这种继续向两边延展,直到25,75。
  • 25/75这两个点只有一个状态,对75而言就是押25,不论50和100都是好的,这两个点在此重合了,所以action也只有1个。对25这个点,全押是唯一最优选择,因为你最远只能到50,另一个跨越50的可能不再存在了。再向两边延展又是两个选择。这里的两个选择有分别以25和75作为参考界限了。一种是希望能够到达25/75的状态,另一种是全押(押100-s)希望能够跨越25(到达终点)。也就是说,1~50和50~100这两个分段呈现出和全局1~100相似的特点。
  • 再一直向两边延展到了12、13,右侧是87左右。对左侧而言倾向于激进,总是全押,因为他没有机会跨越25了只能尽可能靠近,而右侧倾向于保守,因为50不具有吸引力,距离100已经很近了。

如果正面朝上的概率从0.4变成0.25,policy没有变化,因为正面还是劣势。但如果变成0.55,就有着显著变化。此时在钱比较少的时候,policy变得保守,只押1,因为硬币向上概率大,长期看是赚的,那么尽可能延长自己的玩的时间有助于提高本金。所以一直到41之前,最优策略都是只押1,最优策略从只有1,逐渐增加为{1,2}, {1,2,3}…到80和81的时候,策略多达19个。再往后开始减少,是因为押多了没用,到100就行了。策略图如下

Model-Based方法:策略迭代与价值迭代

如果是0.5那么你对于输赢完全没于任何把握,随机策略就是最好策略,换句话说,有10钱,1~10随便押就行了。策略图如下

Model-Based方法:策略迭代与价值迭代
这道题给出了一种智慧,对于胜利把握大的游戏,不要着急,看长线你总能赚。对于胜利把握小的游戏,快赢了的时候就得保守,快输了的时候就赌一把,拖延无好处。

附代码:

import numpy as np
import matplotlib.pyplot as plt

p_h = 0.4

def value_iteration(n_iter=10000):
    v = np.zeros(101)
    v[100] = 1.
    for it in range(n_iter):
        delta = 0.
        for s in range(1, 100):
            v_old = v[s]
            v[s] = np.max([p_h * v[s + a] + (1 - p_h) * v[s - a] for a in range(1, min(s, 100 - s) + 1)])
            delta = max(delta, abs(v_old - v[s]))
        if delta < 1e-5:
            print("converge at %d rounds" % it)
            break
    # pick all optimal actions for each state
    p = dict()
    for s in range(1, 100):
        cands = [p_h * v[s + a] + (1 - p_h) * v[s - a] for a in range(1, min(s, 100 - s) + 1)]
        max_value = np.max(cands)
        p[s] = []
        for a, cand in enumerate(cands):
            if abs(max_value - cand) < 1e-5:
                p[s].append(a + 1)
    return v, p

if __name__ == "__main__":
    value, policy = value_iteration(10000)
    plt.plot(value)
    plt.show()
    for s in policy:
        plt.scatter([s] * len(policy[s]), policy[s], marker='.', color='blue')
    plt.show()
本网站的内容主要来自互联网上的各种资源,仅供参考和信息分享之用,不代表本网站拥有相关版权或知识产权。如您认为内容侵犯您的权益,请联系我们,我们将尽快采取行动,包括删除或更正。
AI教程

异构图上节点分类与DGL源码实战

2023-12-21 8:46:14

AI教程

深度学习中常用的池化函数及其原理

2023-12-21 8:57:14

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索