精华内容
下载资源
问答
  • 价值迭代
    2022-04-08 22:31:19

    强化学习面试经典问题: 策略迭代与价值迭代的关系

    在强化学习问题中, 如果知道环境的模型(动力学模型Model-based, 例如所有的状态转移概率矩阵 P ( s ′ ∣ s ) P(s'|s) P(ss)等), 则可利用这些信息构建一个 MDP 模型来对环境进行描述. 一旦有了环境的动力学模型, 就可以使用动态规划(DP)的方法来对最优价值函数和策略进行求解. 一旦获得了最优价值函数 V π ∗ ( s ) V_π^* (s) Vπ(s), 最优策略就是选择能够最大化下一状态价值的动作.

    总结:

    相同点: 都用于求解 Model-Based 的DP算法.
    异同点:

    1. 价值迭代不直接改进策略; 策略迭代直接改进策略: 值函数和策略同时达到最优; 策略迭代先是① 策略评估, 后是② 策略提升
    2. 价值迭代采用的是贝尔曼最优方程,策略迭代采用的是贝尔曼方程
    3. 在状态空间较小时, 策略迭代的收敛速度更快一些. 在状态空间较大时, 不适合用策略迭代.

    策略迭代:

    策略迭代(Policy Iteration)就是在策略 π ( a │ s ) π(a│s) π(as)未知的情况下,根据每次迭代的反馈reward来学到最优 π ( a │ s ) π(a│s) π(as).
    策略迭代的主要时间都花费在策略评估上,对一个简单的问题来说,在策略评估上花费的时间不算长;但对复杂的问题来说,这个步骤的时间比较长. 但是其优点也很明显,就是很容易证明其收敛性.

    其算法思想是:

    1. 首先随机初始化策略 π ( a │ s ) π(a│s) π(as), 将状态价值函数 V π ( s ) V_π (s) Vπ(s)置为 0
    2. 在①策略评估部分, 根据当前的策略 π ( a │ s ) π(a│s) π(as)来计算每一个状态的价值 V π ( s ) V_π (s) Vπ(s), 直到 V π ( s ) V_π (s) Vπ(s)收敛为止: V ( s ) ← ∑ ( r , s ′ ) ( r + γ V ( s ′ ) ) ⋅ P ( r , s ′ ∣ s , π ( s ) ) V(s)←∑_(r,s')(r+γV(s' ))⋅P(r,s' |s,π(s)) V(s)(r,s)(r+γV(s))P(r,ss,π(s))
    3. 在②策略改进部分, 根据上一步求得的状态价值 V π ( s ) V_π (s) Vπ(s)来得到新的策略 π ( a │ s ) π(a│s) π(as), 直到策略 π ( a │ s ) π(a│s) π(as)收敛为止, 否则重新回到策略估计: π ( s ) ← a r g ⁡ m a x a ⁡ ∑ r , s ′ ( r + γ V ( s ′ ) ) ⋅ P ( r , s ′ ∣ s , π ( s ) ) π(s)←arg⁡max_a⁡∑_{r,s'}(r+γV(s' ))⋅P(r,s' |s,π(s)) π(s)argmaxar,s(r+γV(s))P(r,ss,π(s))

    首先随机初始化随机策略 π π π, 将所有状态 s s s的价值函数置为 V π ( s ) = 0 V_π (s)=0 Vπ(s)=0

    一直进行迭代步骤①+②, 直到 π ( a │ s ) π(a│s) π(as)收敛(两次迭代之间变化不大):
    ①策略评估: 根据当前的策略π来计算所有状态 s s s的价值 V π ( s ) V_π (s) Vπ(s), 直到收敛为止. 执行 n n n轮迭代, 每轮迭代时计算出每个状态 s s s V π ( s ) V_π (s) Vπ(s), 直到 V π ( s ) V_π (s) Vπ(s)变化不大时停止:
    V π ( s ) ← ∑ r , s ′ P ( r , s ′ ∣ s , π ( s ) ) ⋅ [ r + γ v π ( s ′ ) ] V_π (s)←∑_{r,s'}P(r,s' |s,π(s))⋅[r+γv_π (s')] Vπ(s)r,sP(r,ss,π(s))[r+γvπ(s)]
    其中 P ( r , s ′ ∣ s , π ( s ) ) P(r,s' |s,π(s)) P(r,ss,π(s))表示在状态 s s s时执行了以概率 π ( s ) π(s) π(s)的可能性执行了某一动作 a a a, 产生了状态 s ′ s' s和奖励 r r r的概率.

    ②策略提升: 根据①策略评估:求得的上一轮策略 π k − 1 ( a │ s ) π_{k-1} (a│s) πk1(as)下的状态价值 V π ( s ) V_π (s) Vπ(s)表, 根据贪心策略更新此轮的策略 π ( a │ s ) π(a│s) π(as) (即在不同的状态s时, 采取最大化 V π ( s ) V_π (s) Vπ(s)的动作 a a a):
    π ( a │ s ) ← a r g m a x a [ V π ( s ′ ) ] π(a│s)←argmax_a [V_π (s')] π(as)argmaxa[Vπ(s)]
    直到该轮策略 π k ( a │ s ) π_k (a│s) πk(as)与上一轮的该策略 π k − 1 ( a │ s ) π_{k-1} (a│s) πk1(as)变化不大时退出全部训练, 否则就回到①继续进行策略评估:来估计当前策略下 π k ( a │ s ) π_k (a│s) πk(as)的全部状态 s s s V π ( s ) V_π (s) Vπ(s).

    当策略 π ( a │ s ) π(a│s) π(as)变化不大时, 就返回当前的 π ( a │ s ) π(a│s) π(as).


    在这里插入图片描述图1. 基于Grid World环境的策略迭代过程: 每次迭代右图为 V π ( s ) V_π (s) Vπ(s), 左图为本次迭代生成的策略 π ( a │ s ) π(a│s) π(as)

    举例: Grid World 是一个4x4的16宫格, 左上角和右下角的格子是终止格子. 该位置的价值固定为0, 智能体如果到达了终止格子则停止移动且此后每轮奖励都是0.
    环境定义: 智能体在16宫格其他格的每次移动, 得到的即时奖励 R R R都是-1. 智能体每次只能移动一个格子, 且只能(上/下/左/右)4种移动选择. 如果在边界格往外走, 则会直接移动回到之前的边界格. 设折扣因子为 γ = 1 γ=1 γ=1.
    由于每次移动(上/下/左/右)下一格都是固定的, 因此执行一个动作(上/下/左/右)后, 状态转化概率是确定的 P = 1 P=1 P=1(即执行了向下的动作, 则智能体到下一个格子的概率为P=1).因为设定 P ( r , s ′ │ s ) = 1 P(r,s'│s)=1 P(r,ss)=1, 则只有概率 π ( s ) π(s) π(s)起作用, 即 P ( r , s ′ │ s , π ( a ∣ s ) ) = π ( a ∣ s ) P(r,s'│s,π(a|s) )=π(a|s) P(r,ss,π(as))=π(as)

    设初始策略是随机策略, 即每个格子(状态 s s s)里有 π ( a │ s ) = 1 / 4 π(a│s)=1/4 π(as)=1/4的概率(上/下/左/右)向周围的4个格子移动. 并初始化所有状态 s s s的状态价值 V π ( s ) V_π (s) Vπ(s)为0. 由于终止格子的价值固定为0, 所以可以不将其加入迭代过程.

    ①策略评估: 在迭代次数k=1的时候, 利用贝尔曼方程 V π ( s ) ← ∑ r , s ′ P ( r , s ′ ∣ s , π ( s ) ) ⋅ [ r + γ V π ( s ′ ) ] V_π (s)←∑_{r,s'}P(r,s' |s,π(s))⋅[r+γV_π(s')] Vπ(s)r,sP(r,ss,π(s))[r+γVπ(s)]计算每一个状态 s s s(格子)对于的 V π ( s ) V_π (s) Vπ(s), 如 k = 1 k=1 k=1轮迭代时, 第二行第一个格子的 V π ( s ) V_π (s) Vπ(s):
    v k = 1 21 = 1 / 4 [ ( − 1 + 0 ) + ( − 1 + 0 ) + ( − 1 + 0 ) + ( − 1 + 0 ) ] = − 1 v_{k=1}^{21}=1/4[(-1+0)+(-1+0)+(-1+0)+(-1+0)]=-1 vk=121=1/4[(1+0)+(1+0)+(1+0)+(1+0)]=1
    第二行第二个格子的价值 V π ( s ) V_π (s) Vπ(s)是:
    v k = 1 22 = 1 / 4 [ ( − 1 + 0 ) + ( − 1 + 0 ) + ( − 1 + 0 ) + ( − 1 + 0 ) ] = − 1 v_{k=1}^{22}=1/4[(-1+0)+(-1+0)+(-1+0)+(-1+0)]=-1 vk=122=1/4[(1+0)+(1+0)+(1+0)+(1+0)]=1
    以此类推, 计算出 k = 1 k=1 k=1全部状态的 V π ( s ) V_π(s) Vπ(s), 结果如图中 k = 1 k=1 k=1右图所示.

    ②策略提升: 根据①策略评估中计算出来的全部 V π ( s ) V_π (s) Vπ(s), 改进策略 π ( a │ s ) π(a│s) π(as). 改进的方法就是让智能体在状态 s s s时(某处格子), 选取动作的方式 π ( a │ s ) π(a│s) π(as)是最大化 V π ( s ′ ) V_π (s') Vπ(s):
    π ( a │ s ) ← a r g m a x a [ V π ( s ′ ) ] π(a│s)←argmax_a [V_π (s')] π(as)argmaxa[Vπ(s)]
    本次策略提升完成后的最终结果策略 π ( a │ s ) π(a│s) π(as) k = 1 k=1 k=1时的左图所示.

    再次进行 k = 2 , 3 , … k=2,3,… k=2,3,的迭代①策略评估+②策略提升, 直到策略 π ( a │ s ) π(a│s) π(as)变化不大为止.

    价值迭代:

    价值迭代(Value Iteration)可以理解为是策略迭代的一个改进版本. 价值迭代算法是一种直接求解最优策略的方法.
    其算法思想是: 在每一个状态 s s s下, 依次执行每一个可能的动作 a a a, 算出执行每一个动作 a a a后的动作价值 Q π ( s , a ) Q_π (s,a) Qπ(s,a), 从中取出最大值作为当前状态 s s s的最优状态价值 V π ∗ ( s ) V_π^* (s) Vπ(s). 重复这个过程, 直到每个状态的最优价值 V π ∗ ( s ) V_π^* (s) Vπ(s)不再发生变化, 则迭代结束.


    使用贝尔曼最优方程, 将策略改进视为值函数的改进, 每一步都求取最大的动作价值函数 Q π ( s , a ) Q_π (s,a) Qπ(s,a). 具体的迭代公式为:
    对于每一个状态 s s s, 求出所有可能动作 a a a的动作价值函数 Q π ( s , a ) Q_π (s,a) Qπ(s,a), 将最大的Q作为该状态s的最优状态价值函数 V π ∗ ( s ) V_π^* (s) Vπ(s).
    Q π ( s , a ) ← r + γ ∑ s ′ → 终 点 ( ∞ ) P ( s ′ ∣ s , a ) V π ( s ′ ) Q_π (s,a)←r+γ∑_{s'→终点(∞)}P(s' |s,a)V_π (s') Qπ(s,a)r+γs()P(ss,a)Vπ(s)
    V π ∗ ( s ) ← m a x a ∈ A ⁡ Q π ( s , a ) V_π^* (s)←max_{a∈A}⁡Q_π (s,a) Vπ(s)maxaAQπ(s,a)
    与策略迭代相比, 价值迭代没有等到状态价值收敛才去调整策略, 而是随着状态价值的迭代及时调整策略, 这样就大大减少了迭代的次数. 最后只要值函数达到最优, 那么策略也达到最优. 也就是说策略和价值从初始状态值函数开始同步迭代计算, 最终 V π ∗ ( s ) V_π^* (s) Vπ(s)收敛, 整个过程中没有遵循任何显式策略.

    最终输出的策略 π ( a │ s ) π(a│s) π(as)就是走最大 V π ∗ ( s ) V_π^* (s) Vπ(s)的动作.


    参考文献: 强化学习(三)用动态规划(DP)求解.

    更多相关内容
  • 价值迭代网络” 。 神经信息处理系统(NIPS)2016 该存储库包含TensorFlow中的Value Iteration Networks的实现,该实现在NIPS 2016上获得了最佳论文奖。此代码基于作者最初的Theano实现。 训练 从下载16x16和28...
  • 策略迭代与价值迭代

    2021-08-18 20:40:53
    对于最优策略的获得我们一般的思路包括策略迭代和价值迭代两种,它们之间有着区别,也有着很多的共性。 策略迭代 ​ 策略评估和策略提升 ​ 策略评估是策略迭代的一个步骤。策略评估的本质通俗来说,就是计算在服从...

    简介

    这篇博客对应课程的Topic2
    在这里插入图片描述
    )

    前面我们讲到,强化学习的最终目的是为了得到一个最优的策略方案而不是监督学习这类问题的模型。而在一开始我们往往对于最优策略一无所知。我们需要做的是不断向我们的最优策略逼近。对于最优策略的获得我们一般的思路包括策略迭代和价值迭代两种,它们之间有着区别,也有着很多的共性。

    策略迭代

    策略评估和策略提升

    策略评估是策略迭代的一个步骤。策略评估的本质通俗来说,就是计算在服从当前策略时,各个状态的价值函数,原理仍然是基于贝尔曼方程。
    这个方法有很多,包括前文讲的DP动态规划,还有后续的蒙特卡洛随机抽样方法等。都可以计算出各个服从某个策略下的各个状态的价值函数,称为策略评估,由于老师课件里面的介绍都是数学公式,就不往上贴了。贴一张稍微清爽一些的算法伪码图。
    在这里插入图片描述

    策略评估之后可以获得最大的价值函数,我们需要进行策略提升,策略提升的具体方法是采用贪心算法的思想,倘若在该状态下由于选择了某个action而跳转到另一个状态过程中产生了最大价值,则将这个action作为需改进的部分写入原来的policy,从而完成了policy improvement
    在这里插入图片描述

    就这样,在遵循现有策略下对于每一个状态都计算出其最有价值的action,从而将策略提升,再采用更新后的策略继续循环重复前面的操作,最终,当新的策略不再发生变化则说明已经达到了收敛,该策略就是最优策略。

    价值迭代

    在这里插入图片描述

    先放一张清凉点的伪码图。
    价值迭代是另一种计算最佳策略的方法,下面从策略迭代的角度分析值迭代,上图中内层Loop循环的值函数更新可以拆分为两步:
    1,策略提升:根据更新前的值函数进行策略提升,得到贪婪策略
    2,策略评估:根据贪婪策略选择状态s下的贪婪动作(greedy action)a对应的值(value),更新s对应的值函数

    价值迭代将两个步骤合在一起了,最终只迭代了一次策略,因此价值迭代其实也可以看成是迭代一次的策略迭代。价值迭代的价值函数更新的次数一般会多于策略迭代的次数,在现代的强化学习中运用得更多的是策略迭代。

    参考链接

    Policy iteration 和 Value iteration

    展开全文
  • 作者列出来是为了发现这个方法存在的问题是策略很快就收敛了而不需要等到策略评估收敛,为价值迭代做一个铺垫。 接下来就是看圈起来的2部分怎么由最初的随机策略进行一次策略提升得到的。 下面的公式之前已经讲过。...

    参考书籍: Reinforcement Learning An introduction
    第二版 作者:Richard S. Sutton and Andrew G. Barto
    以及此书的中文版《强化学习》

    第4章 动态规划

    上一章:第3章:有限马尔可夫决策过程
    下一章:第5章: Monte Carlo蒙特卡洛方法

    1.介绍

    动态规划在强化学习中的使用受到限制。主要因为两个原因:
    1.动态规划要求一个正确的模型假设。
    2.动态规划计算开销大。
    但是,动态规划是理解其它强化学习方法的基础。其它不使用动态规划的强化学习方法所做的事情,仅仅是为了在不知道模型和减小计算开销的条件下,达到和动态规划一样的效果。
    虽然动态规划也可以应用到连续的动作和状态空间中,但是可以只在某些案例中能得到正确结果。动态规划在解决连续动作和状态空间问题时,一个通用的求近似解的方法是量化动作和状态空间,然后利用有限状态的动态规划方法。这个方法之后讨论。
    DP和增强学习思想的核心通常说来是用价值函数去组织构建一种搜索从而找到好的策略。 本章展示DP怎么被用来计算上一章(上一章链接)中定义的价值函数。 在上一章中讨论过的,一旦我们找到最优价值函数 v∗ 或者 q∗,我们就可以很容易的获得最优策略,这符合贝尔曼最优方程:
    在这里插入图片描述
    或者在这里插入图片描述

    2.策略评估(预测)

    上一章介绍了以下式子:
    记住下面这个式子是Vπ的等式。下一个公式会用到这个结论。
    在这里插入图片描述
    在这里 π(a|s) 是在状态 s 时使用策略 π 采取动作 a 的概率, 期望下标 π 用来表明是在策略 π 的条件下只要 γ<1 或者所有的状态在策略 π(a|s) 下都能达到最终状态, 就能保证 vπ 存在且唯一。解释一下上面这句话。因为Vπ表示的未来长期的收益,如果是上一章说的持续型任务,那么γ<1,可以保证最终回报G不会无限制的增加,而是会收敛到一个值,也就保证 vπ 存在且唯一。此外,如果对所有状态策略都能到达终止状态,即回合型任务,那么G肯定是一个定值,也就能保证 vπ 存在且唯一。

    为了求解最优解,可以考虑迭代。Vk+1可以看做下一次迭代的值,等式右边涉及到Vk即上一轮迭代的值。因此每一轮迭代的新的V值由上一轮决定,那么什么时候终止呢?显然但新的V值和上一轮的V值相等的时候,那么迭代就没有意义了。我们假设Vk等于Vπ(这一小节开头要求记住的Vπ式子),那么下面式子Vk+1的右边可以变成Vπ的,于是右边可以直接用Vπ替换掉。即Vk+1=Vπ。故Vk+1=Vk=Vπ,表示可以迭代停止了。Vπ到底是多少我们不需要知道。我们只需要知道存在这样的Vπ可以使得迭代到一定时刻,Vk+1会等于Vπ就行了。这就是我们需要求解的Vπ。
    在这里插入图片描述
    在迭代得时候,我们不可能把Vk+1=Vk来当作迭代停止的条件,因为对于持续性任务,V是收敛到某一个值,而不会等于某一个值,这意味着我们得迭代停止条件是Vk+1和Vk的差值小于一个非常小的数的时候就停止。
    在这里插入图片描述

    3.策略提升

    我们计算某个策略价值函数的目的是找到一个更好的策略。假设我们已经确定了一个任意确定性的策略 π 价值函数 vπ。 对于某些状态 s 我们想知道是否应该改变策略来明确的选择一个动作 a≠π(s)。 我们知道在当前状态 s 遵从当前的策略有多好——也就是 vπ(s)——但是改变为一个新的状态会更好还是坏呢? 一种解决这个问题的方法是考虑从状态 s 下选择动作 a,然后遵从现有的策略 π。
    上一节策略评估讲的是下图标号为1的红色圈起来的内容。使得V在当前策略下收敛。而这小节策略提升是指在策略评估完成一次后,如何提升该策略,即下图中的圈起来的标号2的部分。注意没圈起来的这些策略实际上是不会执行的。作者列出来是为了发现这个方法存在的问题是策略很快就收敛了而不需要等到策略评估收敛,为价值迭代做一个铺垫。
    在这里插入图片描述
    接下来就是看圈起来的2部分怎么由最初的随机策略进行一次策略提升得到的。
    下面的公式之前已经讲过。是在状态s下采取a动作的时候,带来的总收益的期望。
    在这里插入图片描述
    我们在策略π下评估了每一个状态的价值。那么 在状态 s 选择执行一次动作 a 然后遵从策略 π 是否会比一直遵从策略 π 好——然后我们当然愿意每次到达状态 s 选择动作 a 都会比较好。 那么新的策略事实上总体来说也会比较好。
    这种方法是正确的,只是 策略提升理论 的一种特殊情况。π 和 π′ 是任意一对确定性的策略, 这样一来,对于所有的 s∈S,
    在这里插入图片描述
    那么策略 π′ 必须与策略 π 同样好或者比策略 π 更好。 也就是说,必须从所有的状态 s∈S 取得更好或者相等的期望回报:
    在这里插入图片描述

    证明如下
    在这里插入图片描述
    目前为止我们看到当给定一个策略和它的价值函数后,我们可以很容易地对在某个状态的动作改变进行评估。 很自然就会扩展到考虑所有状态和所有可能的动作,根据 qπ(s,a) 选择在每个状态最好的动作。 换句话说,考虑新的 贪婪 策略 π′,如下
    在这里插入图片描述

    假定新的贪婪策略 π′,与旧的策略 π 一样好。那么 Vπ=Vπ′, 根据 (4.9) 对于所有的 s∈S:
    在这里插入图片描述
    但是这与贝尔曼最优方程 (4.1) 一致(这和“2.策略评估”黑体是一样的原理),所以,Vπ′ 必须是 V∗, π 和 π′ 必须都是最优策略。因此策略提升一定会得到一个更好的策略除非初始的策略就是最优的。
    目前为止在这一章节中我们我们考虑了确定策略的特殊情况。普遍情况下,一个随机策略 π 通过在每一个状态 s 采取每一个动作 a 来指定概率 π(a|s)。 我们不会讨论细节,但是实际上,这一章节的所有的方法都可以很容易的扩展到随机策略。 特别的,策略提升理论贯穿如前所述的随机策略例子。另外,如果策略提升步骤比如 (4.9) 之间 有联系——也就是说,如果有几个动作都能得到最大值——那么在随机策略的例子中我们不需要从中选择一个单独的动作。 取而代之的是,每一个取得最大值的动作在新的贪婪策略中有一定的概率被选择。只要非最大动作的概率为零,任何分摊的方案都可以。

    4.策略迭代

    上面已经介绍了策略评估和策略提升。策略迭代就是交替的进行策略评估和策略提升。原理是一旦策略 π,已经用 Vπ 提升为更好的策略 π′, 我们可以计算 Vπ′ 再次提升策略得到更好的策略 π′′。 我们可以得到一系列单调提升的策略和价值函数:
    在这里插入图片描述
    需要注意的是,“3.策略提升”的第一张图这个例子,恰好在执行了圈1的策略评估,然后进行圈2的策略提升后,策略直接从最开始的随即策略变成了最优策略。但是一般情况下,很难这样迭代一次就直接提升到最优策略。因此策略迭代通常需要迭代多次才能得到最优策略。
    在这里插入图片描述

    5.价值迭代

    回顾:策略迭代是在策略评估时,让V收敛后,再进行策略提升。再用提升的策略进行策略评估。。。一直训练到策略提升收敛位置。
    上述策略迭代是很难实现的,因为每一轮迭代都需要让V收敛才提升一次策略。V收敛实际上是需要大量计算开销的。价值迭代实际上是更新一次V就进行策略提升,而不等到V收敛才策略提升。由于策略提升就是去最大动作的q,因此只需要在V迭代的时候,取max就是策略提升后计算的V了,如下形式
    在这里插入图片描述
    对应代码如下
    在这里插入图片描述

    6.异步动态规划

    对于价值迭代而言,虽然不需要等待V收敛,而是每一次就更新V就更新策略。但是每一次更新V需要遍历所有的状态s,更新每个状态s的V(s)。异步动态规划是指,每一次V更新不需要遍历所有状态,而是只更新部分V(s)。
    即异步 DP算法是就地迭代DP算法,并没有按照规则的状态集更新步骤进行组织。 这些算法以任何顺序更新状态值,使用恰好可用的其他状态值。某些状态的值可能会在其他状态的值更新一次之前被更新多次。 为了收敛到准确值,异步算法需要持续的回溯所有的状态值:在一定量的计算之后不能忽视任何状态。 异步DP算法在选择回溯更新状态时有极大的灵活性。

    重点:事实上,在状态空间非常大的环境中,必须使用异步动态规划。例如,五子棋有多于 1020 个状态。 即使我们能够一秒钟执行一百万个状态的价值迭代更新,也会花费一千年才能完成一次更新。
    未来学习的DQN,DDPG,TD3等算法,一般通过经验池数据来保证一些状态的值被更新,同时也会和环境直接交互,交互得到一部分数据状态更新取状态的值。都是属于异步的形式。

    7.广义策略迭代

    策略迭代包含两个同时进行的交互过程,一个使得价值函数与当前策略一致(策略评估),另一个使得策略在当前价值函数下变得贪婪(策略提升)。 在策略迭代过程中,这两个过程相互交替,一个完成了另一个才开始,但是这并不是必须的。 在价值迭代过程中,例如,在每两次策略提升的过程中只进行一次策略评估的迭代。 异步DP方法中,评估和提升过程以一种更加精细的方式交替。在某些例子中一个状态在转移到其他状态之前就在一个过程中更新。 只要两个过程持续更新所有的状态,最终的结果就会一致,即收敛到最优价值函数和最优策略
    在这里插入图片描述

    我们用术语 广义策略迭代 (GPI)这个词来指代策略评估和策略提升相互交互的一般概念,而不依赖于两个过程的粒度和其他细节。 几乎所有的强化学习方法都可以被描述为GPI。也就是说,都有可识别的策略和价值函数, 策略总是被价值函数进行更新,价值函数用来计算出相应策略下的价值函数,如上图所示。 很容易看到,如果评估过程和提升过程都稳定了,也就是说,不会再有变化,那么价值函数和策略一定是最优的。 价值函数仅在与当前策略一致时才稳定,并且策略仅在相对于当前价值函数贪婪时才稳定。 因此,只有当一个策略在它自己的评估函数下保持贪婪时,两个过程才能都稳定下来。 这预示着贝尔曼最优方程(4.1)成立,因此这个策略和价值函数是最优的。
    在这里插入图片描述

    GPI中的评估和提升的过程可以认为是既存在竞争又存在合作。在竞争这个意义上他们走向相反的方向。 使价值函数的策略贪婪通常会使更改的策略的价值函数不正确,使价值函数与策略一致通常会导致该策略不再贪婪。 然而,从长远来看,这两个过程相互作用以找到单一的联合解:最优价值函数和最优策略。
    我们可能还会考虑GPI中评估和提升过程的约束和目标的交互,例如,如上图所示两维空间中的两条线。 虽然实际的几何比这更加复杂,这个图表明了实际情况中会发生的情况。 每一个过程驱使价值函数或者策略朝向一条代表这两个目标的一个解的线前进。 目标会交互是因为两条线并不互相垂直。直接驱使向一个目标发展会导致偏离另一个目标。 然而,不可避免地,联合的过程越来越趋近整体的最优目标。 图中的箭头对应于策略迭代的行为过程,每个箭头都使系统完全达到两个目标中的一个。 在GPI过程中可以采取更小不完全的步骤去达到每个目标。 任一种情况,这两个过程一起会达到整体的最优目标,即使每一个单独都不能达到最优。

    上一章:第3章:有限马尔可夫决策过程
    下一章:第5章: Monte Carlo蒙特卡洛方法

    展开全文
  • 基于模型的RL:使用动态编程的策略和价值迭代学习目标了解政策评估与政策改进之间的区别以及这些流程如何相互作用了解策略迭代算法了解值迭代算法了解动态编程方法的局限性概括动态编程(DP)方法假定我们具有环境的...
  • 上一篇博文介绍了MDP问题以及对应的价值迭代和策略迭代两种解法,本文我们将手把手使用python 实现在4*3格网对value iteration algorithm 进行实现。首先回顾value iteration算法,如下图所示: 其中输入中最重要...

            上一篇博文介绍了MDP问题以及对应的价值迭代和策略迭代两种解法,本文我们将手把手使用python 实现在4*3格网对value iteration algorithm 进行实现。首先回顾value iteration算法,如下图所示:

    其中输入中最重要的就是构造 p(s'|s, a),我们可以采用矩阵的方式,因为一共有12个格子和4种动作,所以p(s'|s,a)可以表示为一个4*12*12的矩阵。首先我们对12个格网进行编号以便方便描述,如下图所示:

            接下来我们就可以构造对应的概率转移矩阵了。这里提示一点,由于Agent到达终止点后游戏停止,所以对于上图中的第8和第12个格子,其对应转移概率全部为0(这里可能会踩的坑就是认为每个格子对应于一个动作的转移概率之和必须是1,不要问我为什么知道,因为我踩过 >.<...),代码如下: 

    import numpy as np
    #定义状态转移矩阵
    upprobolity= [[0.1,0.1,0,0,0.8,0,0,0,0,0,0,0],
    [0.1,0.8,0.1,0,0,0,0,0,0,0,0,0],
    [0,0.1,0,0.1,0,0,0.8,0,0,0,0,0],
    [0,0,0.1,0.1,0,0,0,0.8,0,0,0,0],
    [0,0,0,0,0.2,0,0,0,0.8,0,0,0],
    [0,0,0,0,0.1,0,0.1,0,0,0.8,0,0],
    [0,0,0,0,0,0,0.1,0.1,0,0,0.8,0],
    [0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0.9,0.1,0,0],
    [0,0,0,0,0,0,0,0,0.1,0.8,0.1,0],
    [0,0,0,0,0,0,0,0,0,0.1,0.8,0.1],
    [0,0,0,0,0,0,0,0,0,0,0,0]]
    
    downprobolity = [[0.9,0.1,0,0,0,0,0,0,0,0,0,0],
    [0.1,0.8,0.1,0,0,0,0,0,0,0,0,0],
    [0,0.1,0.8,0.1,0,0,0,0,0,0,0,0],
    [0,0,0.1,0.9,0,0,0,0,0,0,0,0],
    [0.8,0,0,0,0.2,0,0,0,0,0,0,0],
    [0,0.8,0,0,0.1,0,0.1,0,0,0,0,0],
    [0,0,0.8,0,0,0,0.1,0.1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0.8,0,0,0,0.1,0.1,0,0],
    [0,0,0,0,0,0,0,0.8,0.1,0.1,0,0],
    [0,0,0,0,0,0,0.8,0,0.1,0,0.1,0],
    [0,0,0,0,0,0,0,0,0,0,0,0]]
    
    
    leftprobolity = [[0.9,0,0,0,0.1,0,0,0,0,0,0,0],
    [0.8,0.2,0,0,0,0,0,0,0,0,0,0],
    [0,0.8,0.1,0,0,0,0.1,0,0,0,0,0],
    [0,0,0.8,0.1,0,0,0,0.1,0,0,0,0],
    [0.1,0,0,0,0.8,0,0,0,0.1,0,0,0],
    [0,0.1,0,0,0.8,0,0,0,0,0.1,0,0],
    [0,0,0.1,0,0,0,0.8,0,0,0,0.1,0],
    [0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0.1,0,0,0,0.9,0,0,0],
    [0,0,0,0,0,0,0,0,0.8,0.2,0,0],
    [0,0,0,0,0,0,0.1,0,0,0.8,0.1,0],
    [0,0,0,0,0,0,0,0,0,0,0,0]]
    
    rightprobolity = [[0.1,0.8,0,0,0.1,0,0,0,0,0,0,0],
    [0,0.2,0.8,0,0,0,0,0,0,0,0,0],
    [0,0,0.1,0.8,0,0,0.1,0,0,0,0,0],
    [0,0,0,0.9,0,0,0,0.1,0,0,0,0],
    [0.1,0,0,0,0.8,0,0,0,0.1,0,0,0],
    [0,0.1,0,0,0,0,0.8,0,0,0.1,0,0],
    [0,0,0.1,0,0,0,0,0.8,0,0,0.1,0],
    [0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0.1,0,0,0,0.1,0.8,0,0],
    [0,0,0,0,0,0,0,0,0,0.2,0.8,0],
    [0,0,0,0,0,0,0.1,0,0,0,0.1,0.8],
    [0,0,0,0,0,0,0,0,0,0,0,0]]
    
    probobility = [upprobolity, downprobolity, leftprobolity, rightprobolity]
    P = np.array(probobility)

     对输入进行初始化:

    States = [1,2,3,4,5,6, 7, 8, 9,10,11,12]
    Actions = ['up', 'down', 'left', 'right']
    Rewards = [-0.04,-0.04, -0.04, -0.04,
               -0.04,-10000,-0.04, -1,
               -0.04,-0.04, -0.04,  1]

    初始化效用值,delta 

    r = 0.9
    U = np.zeros(12)
    U_updated = np.zeros(12)
    
    # epsilon :程序停止的阈值,当两次迭代后utility 向量差值小于epsilon 后即停止更新
    epsilon = 0.01
    
    # delta:一次迭代后新的utility向量 和 原始的utility 向量之间的差值
    # state utility 向量差值的大小等于所有state中更新前后utility最大的变化量(一个标量)
    # 我们这里对delta 进行初始化时将其设置为0,后面在迭代中对其进行更新
    delta = 0 

     定义函数来更新效用值,以下代码是对单个效用值的更新

    # actionid 包括[0,1,2,3]
    # P[:, index, :] 为 4*12 矩阵,U为12 *1 矩阵
    def maxUtility(s):
    	index = s-1
    	action_rewards = ((P[:, index, :])* U).sum(axis = 1)
    	next_disReward = r*(max(action_rewards))
    	us_updated = Rewards[index]+ next_disReward
    	return us_updated

    根据对每个状态的最大化效用值函数,对效用值进行更新

    while True:
    	U = U_updated.copy()
    	delta = 0
    	print(U)
    	for s in States:
    		us_updated = maxUtility(s)
    		U_updated[s-1] = us_updated
    		s_dif = np.absolute(U_updated[s-1] - U[s-1])
    		delta = s_dif if s_dif > delta else delta
    	if (delta <epsilon*(1-r)/r):
    		break

     更新完之后,我们定义一个函数用于获取每一个state 对应的最优动作:

    # 根据最大效用规则,选择下一个动作
    def getNextSateAction(s):
    	index = s-1
    	action_rewards = ((P[:, index, :])* U).sum(axis = 1)
    	actionID = np.argmax(action_rewards)
    	print(Actions[actionID])

    调用上面的函数获取最优动作结果(即我们的policy):

    # 除障碍网格6和终止点网格(8和12)外对应的最有动作
    for s in [1,2,3,4,5, 7, 9,10,11]:
    	getNextSateAction(s)
    # output: [up,right,up,left,up,up,right,right,right]

    通过可视化,我们将更新完之后的utilities 和对应最优动作展示如下:

    后记:

            这里我们思考一个问题,我们上一篇博客说过不论是初始状态是哪一个,最后得到最优策略是一样的。这里其实可以通过程序来印证这个问题,如果我们将States =[1,2,3,4,5,6,7,8,9,10,11,12] 中格子顺序进行随机排序后,得到最终更新的utilities 仍然将会是一样的。不信?那你试试!!

    MDP 系列文章

    1,马尔科夫决策过程原理和求解(MDP之一)

    2,价值迭代算法求解MDP实现 value iteration algorithm(MDP之二)

    3,策略迭代算法求解MDP实现(之三)

    展开全文
  • 在强化学习中,当环境模型已知时(也即环境状态转移概率和奖励已知),可以采用动态规划的思想来解决强化学习问题,常用的有策略迭代算法和值迭代算法两种,以下展开具体介绍。 1.动态规划与强化学习的联系 动态...
  • matlab的egde源代码价值迭代网络 NIPS 2016论文代码: 价值迭代网络 Aviv Tamar,Yi Wu,Garrett Thomas,Sergey Levine和Pieter Abbeel 加州大学伯克利分校 要求: 巨蟒(2.7) 茶野(0.8) 为了生成gridworld数据...
  • 笔记:价值迭代和策略迭代的不同 1.策略迭代包括:策略评估+策略改进,并且反复迭代这两项直到策略收敛。 2.价值迭代包括:找到最优价值函数+一个策略提取。两者没有重复,因为一旦值函数最佳,则其中的策略也应最佳...
  • 动态规划就是基于模型的强化学习方法,可分为策略迭代(policy iteration)和价值迭代(value iteration)两种,下面详细介绍。 \\[30pt] 1. 策略迭代 策略迭代又分为两个部分,即策略评估和策略改进。
  • 1、最优化原理(Principle of optimality) 2、确定性价值迭代(Deterministic Value Iteration) 4、价值迭代
  • 异步价值迭代网络

    2021-04-30 19:30:50
    异步价值迭代网络
  • 刚刚的例子很简单,在状态转移图中没有“环”,因此我们可以从末状态开始,计算他的价值,然后回到开始状态。然而,如果环境中有“环”,会给我们带来麻烦: 求s1,s2s_1,s_2s1​,s2​的价值?每个episode的奖励顺序...
  • (2)异步价值迭代 异步价值迭代只存储一份价值函数 下面是一个价值迭代的一个例子:最短路径 这里即时奖励值R为-1。 2.7.2 策略迭代 适用情况:对于一个状态空间和动作空间有限的MDP。 策略迭代的过程: 1.随机...
  • 该问题基于《Reinforcement Learning: An Introduction》在第四章的例4.4 gamblers问题.1、 问题描述一个Gamb
  • 强化学习经典算法笔记——价值迭代算法   由于毕业设计做的是强化学习相关的内容,感觉有必要把强化学习经典算法实现一遍,加强对算法和编程的理解。所以从这一篇开始,每一篇实现一个算法,主要包括Value ...
  • 1. 价值迭代算法的伪代码 2.源代码 3.代码解析
  • 策略迭代和价值迭代

    2022-08-29 13:59:41
    一. 策略迭代 (1)为V(s),(s),设初值。 (2)策略评估,改变V(s)。 利用贝尔曼期望方程。... 价值迭代(极端情况下的策略迭代,即策略评估只进行一次) (1)给V(s),(s),设初值。 (2)利用 通过贝尔曼最优性方程
  • 1. 价值迭代算法 价值迭代方法在迭代过程直接更新行动的值函数。那么它和上一节限制最大迭代次数为一的策略迭代有什么不同呢? 策略迭代法的核心是策略,每一轮的价值计算出来是为了更新策略用的,直观来看代码上有...
  • PyTorch实现价值迭代网络(NIPS '16)论文
  • 强化学习之策略迭代和价值迭代(gym)

    千次阅读 2020-08-11 20:29:57
    一、策略迭代 1.1 伪代码 1.2 基于冰湖环境的代码 实验环境及介绍:FrozenLake8x8-v0 import gym import time import numpy as np def policy_evaluation(env, value_table, policy, gamma=0.9, threshold=1e-4):...
  • 包含用于规划的算法:策略迭代和价值迭代。 还包含强化学习算法:蒙特卡洛学习,Sarsa(lambda)和Q学习。 在GridWorld问题的上下文中使用这些方法,在该问题中,代理的目标是找到到达终端状态的最快路径。 game....
  • 4. 基于价值迭代(Value iteration)的求解方法 5. 基于策略迭代(Policy iteration)的求解方法 6. 比较Value iteration和Policy iteration 7. 小结 1. 强化学习(Reinforcement learning)概述 强化学习...
  • 强化学习值迭代和 Q 学习在 4x4 随机 GridWorld 上的实现和可视化。概述Grid 环境及其动态在environment.py中实现为GridWorld类,以及实用函数grid 、 print_grid和play_game 。 Value Iteration 算法和 Q-learning ...
  • 价值迭代网络

    千次阅读 2018-09-24 21:32:44
    价值迭代网络(Value Iteration Networks)》获得了第 30 届神经信息处理系统大会(Conference and Workshop on Neural Information Processing Systems) NIPS 2016唯一的最佳论文奖项(Best Paper Award) ...
  • 原文:Value Iteration Networks 作者:Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbee 出处:Neural Information Processing Systems 2016
  • 强化学习-价值迭代

    2019-02-16 09:12:00
    在策略迭代最后我们发现策略迭代的收敛过程比较慢,那我们就会想有没更好更快的迭代方法,今天我们介绍的价值迭代就是另一种寻找最优策略的解决方案。 2. 动态规划 价值迭代需要用到动态规划的思想,那我们简单的...
  • 上一篇博客我们介绍了价值迭代的原理。这一节我们实现强化学习里面的价值迭代的部分代码(完整代码GitHub)。 2. 价值迭代回顾 我们把注意点放在值函数上,等值函数收敛了,我们的策略也会收敛到最优值。 \[ v^{T+1}(s...
  • 【强化学习】价值迭代

    千次阅读 2019-04-02 00:08:10
    价值函数定义为 带入 R 的定义: 角标 π\piπ 说明,所有状态的价值依赖于 ...用迭代的方式求解出任意 策略π\piπ 对应的价值函数。 最优的策略,就是每一步都选择价值最大的下一个状态,所以对应的价值函数为...
  • 参考文章 强化学习之策略迭代和价值迭代(gym)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 141,654
精华内容 56,661
关键字:

价值迭代