基于动态规划的强化学习方法

这篇具有很好参考价值的文章主要介绍了基于动态规划的强化学习方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

\quad
\quad

基于动态规划的强化学习方法

\quad

动态规划(dynamic programming)是程序设计算法中非常重要的内容,能够高效解决一些经典问题,例如背包问题最短路径规划。动态规划的基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到目标问题的解。动态规划会保存已解决的子问题的答案,在求解目标问题的过程中,需要这些子问题答案时就可以直接利用,避免重复计算。本文介绍如何用动态规划的思想来求解在马尔可夫决策过程中的最优策略。

基于动态规划的强化学习算法主要有两种:一是策略迭代(policy iteration),二是价值迭代(value iteration)。其中,策略迭代由两部分组成:策略评估(policy evaluation)和策略提升(policy improvement)。

具体来说,策略迭代中的策略评估使用贝尔曼期望方程来得到一个策略的状态价值函数,这是一个动态规划的过程;而价值迭代直接使用贝尔曼最优方程来进行动态规划,得到最终的最优状态价值。

不同于蒙特卡洛方法和时序差分算法,基于动态规划的强化学习算法要求事先知道环境的状态转移函数和奖励函数,也就是需要知道整个马尔可夫决策过程。在这样一个白盒环境中,不需要通过智能体和环境的大量交互来学习,可以直接用动态规划求解状态价值函数。但是,现实中的白盒环境很少,这也是动态规划算法的局限之处,我们无法将其运用到很多实际场景中。另外,策略迭代和价值迭代通常只适用于有限马尔可夫决策过程,即状态空间和动作空间是离散且有限的
\quad

概述

首先,回顾一下马尔克夫决策过程。一个完整的已知模型的马尔可夫决策过程可以利用元组 ( S , A , P , r , γ ) (S,A,P,r,\gamma) (S,A,P,r,γ)来表示。其中:

  • S S S表示状态集
  • A A A表示动作集
  • P P P为转移概率,也就是对应着环境和智能体的模型
  • r r r为回报函数
  • γ \gamma γ为折扣因子,用来计算累计回报 R R R

累计回报公式为 R = ∑ t = 0 T γ t r t R=\sum\limits_{t=0}^{T}\gamma^tr_t R=t=0Tγtrt,其中 0 ≤ γ ≤ 1 0 \leq \gamma \leq 1 0γ1

  • T T T为有限值时,强化学习过程称为有限范围强化学习;
  • T = ∞ T=\infty T=时,强化学习过程称为无穷范围强化学习。

强化学习的目标是找到最优策略 π \pi π使得累计回报的期望最大。

所谓策略是指状态到动作的映射 π : s → a \pi:s \rightarrow a π:sa,用 τ \tau τ表示从状态 s s s到最终状态的一个序列 τ : s t , s t + 1 , ⋯   , s T \tau:s_t,s_{t+1},\cdots,s_T τ:st,st+1,,sT,则累计回报 R ( τ ) R(\tau) R(τ)是个随机变量,随机变量无法进行优化,无法作为目标函数,故而我们采用累计回报的期望作为目标函数,即 ∫ R ( τ ) p π ( τ ) d τ \int R(\tau)p_{\pi}(\tau)d\tau R(τ)pπ(τ)dτ作为目标函数。

强化学习的最终目标就是找到最优策略为 π ∗ : s → u ∗ \pi^*:s\rightarrow u^* π:su。从广义上来讲,强化学习可以归结为序贯决策问题,即找到一个决策序列,使得目标函数最优。累计回报的含义是评价策略完成任务的总回报,所以目标函数等价于任务。回报函数对应着具体的任务,所以强化学习所学到的最优策略是与具体的任务相对应的

从广义上讲,强化学习是序贯决策问题。但序贯决策问题包含的内容更丰富。它不仅包含马尔科夫过程的决策,而且包括非马尔科夫过程的决策。马尔科夫决策过程可以利用元组 ( S , A , P , r , γ ) \left( {S,A,P,r,\gamma } \right) (S,A,P,r,γ)来描述,根据转移概率 P P P是否已知,可以分为基于模型的强化学习方法和基于无模型的强化学习方法,两种类别都包括策略迭代算法,值迭代算法和策略搜索算法。不同的是无模型的强化学习方法又分为online和offline两种。

基于模型的强化学习可以利用动态规划的思想来解决。顾名思义,动态规划中的动态蕴含着序列和状态的变化;规划蕴含着优化,如线性优化,二次优化或者非线性优化。利用动态规划可以解决的问题需要满足两个条件:

  1. 整个优化问题可以分解为多个子优化问题
  2. 子优化问题的解可以被存储和重复利用。

\quad
\quad

策略迭代算法

\quad

策略评估算法

强化学习可以利用马尔科夫决策过程来描述,利用贝尔曼最优性原理得到贝尔曼最优化方程:
v ∗ ( s ) = max ⁡ a R s a + γ ∑ s ′ ∈ S P s s ′ a v ∗ ( s ′ ) q ∗ ( s , a ) = R s a + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) max ⁡ a ′ q ∗ ( s ′ , a ′ ) v^{*}(s)=\max _{a} R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v^{*}\left(s^{\prime}\right)\\ q^{*}(s, a)=R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} |s, a\right) \max _{a^{\prime}} q^{*}\left(s^{\prime}, a^{\prime}\right) v(s)=amaxRsa+γsSPssav(s)q(s,a)=Rsa+γsSP(ss,a)amaxq(s,a)
从这两个方程中,显然可以看到,马尔科夫决策问题符合使用动态规划的两个条件,因此可以利用动态规划解决马尔科夫决策过程的问题。贝尔曼方程指出,动态规划的核心是找到最优值函数,那么,给定一个策略 π \pi π,如何计算在策略 π \pi π下的值函数就成了一个问题。下面给出值函数的计算过程:
image.png

红色方框内的计算公式为:
v π ( s ) = ∑ a ∈ A π ( a ∣ s ) q π ( s , a ) (1) v_{\pi}(s)=\sum_{a \in A} \pi(a \mid s) q_{\pi}(s, a)\tag{1} vπ(s)=aAπ(as)qπ(s,a)(1)
该方程表示,在状态 s s s处的值函数等于采取策略 π \pi π时,所有状态-行为值函数的总和。

蓝色方框的计算公式为状态-行为值函数的计算:
q π ( s , a ) = R s a + γ ∑ s ′ P ( s ′ ∣ s , a ) v π ( s ′ ) (2) q_{\pi}(s, a)=R_{s}^{a}+\gamma \sum_{s^{\prime}} P\left(s^{\prime}|s, a\right) v_{\pi}\left(s^{\prime}\right)\tag{2} qπ(s,a)=Rsa+γsP(ss,a)vπ(s)(2)
该方程表示,在状态 s s s采用动作 a a a的状态值函数等于回报加上后续状态值函数。

将方程(2)代入方程(1)便得到状态值函数的计算公式:
v π ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) v π ( s ′ ) ) (3) v_{\pi}(s)=\sum_{a \in A} \pi(a \mid s)\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime}|s, a\right)v_{\pi}\left(s^{\prime}\right)\right)\tag{3} vπ(s)=aAπ(as)(Rsa+γsSP(ss,a)vπ(s))(3)

可以看到,当知道奖励函数和状态转移函数时,我们可以根据下一个状态的价值来计算当前状态的价值。
\quad
首先,可以从数学的角度出发去解释方程(3),对于模型已知的强化学习算法,方程中的 P ( s ′ ∣ s , a ) P\left(s^{\prime} \mid s, a\right) P(ss,a) γ \gamma γ R S a R_S^a RSa都是已知数, π ( a ∣ s ) \pi(a|s) π(as)为要评估的策略,也是已知值。方程中唯一的未知数是值函数,也就是说,方程(3)其实是关于值函数的线性方程组,其未知数的个数为状态的总数,用 ∣ S ∣ |S| S来表示。

因此,根据动态规划的思想,可以把计算下一个可能状态的价值当成一个子问题,把计算当前状态的价值看作当前问题。在得知子问题的解后,就可以求解当前问题。更一般的,考虑所有的状态,就变成了用上一轮的状态价值函数来计算当前这一轮的状态价值函数,即
V k + 1 ( s ) = ∑ a ∈ A π ( a ∣ s ) ( r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V k ( s ′ ) ) V^{k+1}(s)=\sum_{a \in A} \pi(a \mid s)\left(r(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime}|s, a\right) V^{k}\left(s^{\prime}\right)\right) Vk+1(s)=aAπ(as)(r(s,a)+γsSP(ss,a)Vk(s))

根据如上分析,可以给出策略评估算法的伪代码,需要注意的是,在每次迭代中都需要对状态集进行一次遍历(扫描)以便评估每个状态的值函数。


Input:策略 π \pi π,状态转移概率 P ( s ′ ∣ s , a ) P\left(s^{\prime}|s, a\right) P(ss,a),回报函数 R s a R_s^a Rsa,折扣因子 γ \gamma γ初始化值函数: V ( s ) = 0 V(s)=0 V(s)=0
Output v ( s ) v(s) v(s)

  • 初始化值函数: V ( s ) = 0 V(s)=0 V(s)=0
  • Repeat
    • For every s s sDo
      • v k + 1 ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) v k ( s ′ ) ) v_{k+1}(s) = \sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s'\in S}P\left(s^{\prime} \mid s, a\right)v_k(s')) vk+1(s)=aAπ(as)(Rsa+γsSP(ss,a)vk(s))
    • End For
  • Until v k + 1 = v k v_{k+1}=v_k vk+1=vk( k = 0 , 1 , ⋯ k=0,1,\cdots k=0,1,)

根据贝尔曼期望方程,可以得知 V k = V π V^k=V^{\pi} Vk=Vπ是以上更新公式的一个不动点(fixed point)。事实上,可以证明当 k → ∞ k\rightarrow \infty k时,序列 { V k } \{V^k\} {Vk}收敛 V π V^{\pi} Vπ,所以可以据此来计算得到一个策略的状态价值函数。

可以看到,由于需要不断做贝尔曼期望方程迭代,策略评估其实会耗费很大的计算代价。在实际的实现过程中,如果某一轮的值非常小,可以提前结束策略评估。这样做可以提升效率,并且得到的价值也非常接近真实的价值。

策略提升算法

使用策略评估计算得到当前策略的状态价值函数之后,我们可以据此来改进该策略。假设此时对于策略 π \pi π,我们已经知道其价值 V π V^{\pi} Vπ,也就是知道了在策略 π \pi π下从每一个状态出发最终得到的期望回报。我们要如何改变策略来获得在状态下更高的期望回报呢?

假设智能体在状态 s s s下采取动作 a a a,之后的动作依旧遵循策略 π \pi π,此时得到的期望回报其实就是动作价值 Q π ( s , a ) Q^{\pi}(s,a) Qπ(s,a)。如果我们有 Q π ( s , a ) > V π ( s ) Q^{\pi}(s,a)>V^{\pi}(s) Qπ(s,a)>Vπ(s),则说明在状态 s s s下采取动作 a a a会比原来的策略 π ( a ∣ s ) \pi(a|s) π(as)得到更高的期望回报。以上假设只是针对一个状态,现在假设存在一个确定性策略,在任意一个状态下,都满足
Q π ( s , π ′ ( s ) ) ≥ V π ( s ) Q^{\pi}\left(s, \pi^{\prime}(s)\right) \geq V^{\pi}(s) Qπ(s,π(s))Vπ(s)
于是在任意状态下,我们有
V π ′ ( s ) ≥ V π ( s ) V^{\pi^{\prime}}(s) \geq V^{\pi}(s) Vπ(s)Vπ(s)
这便是策略提升定理(policy improvement theorem)。

于是我们可以直接贪心地在每一个状态选择动作价值最大的动作,也就是
π ′ ( s ) = arg ⁡ max ⁡ a Q π ( s , a ) = arg ⁡ max ⁡ a { r ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V π ( s ′ ) } \pi^{\prime}(s)=\arg \max _{a} Q^{\pi}(s, a)=\arg \max _{a}\left\{r(s, a)+\gamma \sum_{s^{\prime}} P\left(s^{\prime}|s, a\right) V^{\pi}\left(s^{\prime}\right)\right\} π(s)=argamaxQπ(s,a)=argamax{r(s,a)+γsP(ss,a)Vπ(s)}
这其实是一个很自然的想法,当已知当前策略的值函数时,在每个状态采用贪婪策略对当前策略进行改进即可。

我们发现构造的贪心策略 π ′ \pi' π满足策略提升定理的条件,所以策略 π ′ \pi' π能够比策略 π \pi π更好或者至少与其一样好。这个根据贪心法选取动作从而得到新的策略的过程称为策略提升。当策略提升之后得到的策略 π ′ \pi' π和之前的策略 π \pi π一样时,说明策略迭代达到了收敛,此时 π ′ \pi' π π \pi π就是最优策略。

策略提升定理的证明:可以通过以下推导过程可以证明,使用上述提升公式得到的新策略在每个状态的价值不低于原策略在该状态的价值。
V π ( s ) ≤ Q π ( s , π ′ ( s ) ) = E π ′ [ R t + γ V π ( S t + 1 ) ∣ S t = s ] ≤ E π ′ [ R t + γ Q π ( S t + 1 , π ′ ( S t + 1 ) ) ∣ S t = s ] = E π ′ [ R t + γ R t + 1 + γ 2 V π ( S t + 2 ) ∣ S t = s ] ≤ E π ′ [ R t + γ R t + 1 + γ 2 R t + 2 + γ 3 V π ( S t + 3 ) ∣ S t = s ] ⋮ ≤ E π ′ [ R t + γ R t + 1 + γ 2 R t + 2 + γ 3 R t + 3 + ⋯ ∣ S t = s ] = V π ′ ( s ) \begin{aligned} V^{\pi}(s) & \leq Q^{\pi}\left(s, \pi^{\prime}(s)\right) \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t}+\gamma V^{\pi}\left(S_{t+1}\right) \mid S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t}+\gamma Q^{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) \mid S_{t}=s\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t}+\gamma R_{t+1}+\gamma^{2} V^{\pi}\left(S_{t+2}\right) \mid S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t}+\gamma R_{t+1}+\gamma^{2} R_{t+2}+\gamma^{3} V^{\pi}\left(S_{t+3}\right) \mid S_{t}=s\right] \\ & \vdots \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t}+\gamma R_{t+1}+\gamma^{2} R_{t+2}+\gamma^{3} R_{t+3}+\cdots \mid S_{t}=s\right] \\ &=V^{\pi^{\prime}}(s) \end{aligned} Vπ(s)Qπ(s,π(s))=Eπ[Rt+γVπ(St+1)St=s]Eπ[Rt+γQπ(St+1,π(St+1))St=s]=Eπ[Rt+γRt+1+γ2Vπ(St+2)St=s]Eπ[Rt+γRt+1+γ2Rt+2+γ3Vπ(St+3)St=s]Eπ[Rt+γRt+1+γ2Rt+2+γ3Rt+3+St=s]=Vπ(s)
可以看到,推导过程中的每一个时间步都用到局部动作价值优势 V π ( S t + 1 ) ≤ Q π ( S t + 1 , π ′ ( S t + 1 ) ) V^{\pi}\left(S_{t+1}\right) \leq Q^{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) Vπ(St+1)Qπ(St+1,π(St+1)),累积到无穷步或者终止状态时,我们就得到了整个策略价值提升的不等式。

下图给出了贪婪策略的示意图,图中红色部分为最优策略选择。
1.png

通过将公式(2)代入到公式(3)就可以得到状态-动作值函数的计算公式,即为:
q π ( s , a ) = R S a + γ ∑ s ′ ∈ S P s s ′ a ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) q π ( s ′ , a ′ ) q_{\pi}(s,a)=R_S^a + \gamma\sum_{s'\in S}P_{ss'}^a\sum_{a'\in A}\pi(a'|s')q_{\pi}(s',a') qπ(s,a)=RSa+γsSPssaaAπ(as)qπ(s,a)
在贪婪策略下,状态-动作值函数就可以变为
q π ( s , a ) = R s a + γ ∑ s ′ ∈ S P s s ′ a max ⁡ a ′ q π ( s ′ , a ′ ) q_{\pi}(s, a)=R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} \max _{a^{\prime}} q_{\pi}\left(s^{\prime}, a^{\prime}\right) qπ(s,a)=Rsa+γsSPssaamaxqπ(s,a)

策略迭代算法

总体来说,策略迭代算法的过程如下:对当前的策略进行策略评估,得到其状态价值函数,然后根据该状态价值函数进行策略提升以得到一个更好的新策略,接着继续评估新策略、提升策略……直至最后收敛到最优策略:
1.png
结合策略评估算法和策略提升算法,便得到了策略迭代算法:


随机初始化策略 π ( s ) \pi(s) π(s)和价值函数 V ( s ) V(s) V(s)

  • While Δ > θ \Delta > \theta Δ>θ do: (策略评估循环)
    • Δ ← 0 \Delta \leftarrow 0 Δ0
    • For s ∈ S s\in \mathcal{S} sS
      • v ← V ( S ) v \leftarrow V(\mathcal{S}) vV(S)
      • V ( s ) ← r ( s , π ( s ) ) + γ ∑ s ′ P ( s ′ ∣ s , π ( s ) ) − V ( s ′ ) V(s) \leftarrow r(s, \pi(s))+\gamma \sum_{s^{\prime}} P\left(s^{\prime} \mid s, \pi(s)\right) - V\left(s^{\prime}\right) V(s)r(s,π(s))+γsP(ss,π(s))V(s)
      • Δ ← max ⁡ ( Δ , ∣ v − V ( s ) ∣ ) \Delta \leftarrow \max (\Delta,|v-V(s)|) Δmax(Δ,vV(s))
    • End For
  • End While
  • π old  ← π \pi_{\text {old }} \leftarrow \pi πold π
  • For s ∈ S s\in \mathcal{S} sS
    • π ( s ) ← arg ⁡ max ⁡ a r ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V ( s ′ ) \pi(s) \leftarrow \arg \max _{a} r(s, a)+\gamma \sum_{s^{\prime}} P\left(s^{\prime} \mid s, a\right) V\left(s^{\prime}\right) π(s)argmaxar(s,a)+γsP(ss,a)V(s)
  • End For
  • π o l d = π \pi_{\mathrm{old}}=\pi πold=π, 则停止算法并返回 V V V π \pi π; 否则转到策略评估循环

价值迭代算法

策略迭代算法包括策略评估和策略改进两个步骤。在策略评估中,给定策略,通过数值迭代算法不断计算该策略下每个状态的值函数,利用该值函数和贪婪策略得到新的策略。如此循环下去,最终得到最优策略。这是一个策略收敛的过程。

值函数收敛过程如下图,从策略迭代的伪代码我们看到,进行策略改进之前需要得到收敛的值函数。值函数的收敛往往需要很多次迭代,这需要很大的计算量,尤其是在状态和动作空间比较大的情况下。但是进行策略改进之前一定要等到策略值函数收敛吗?
1.png

试想一下,可能出现这样的情况:虽然状态价值函数还没有收敛,但是不论接下来怎么更新状态价值,策略提升得到的都是同一个策略。如果只在策略评估中进行一轮价值更新,然后直接根据更新后的价值进行策略提升,这样是否可以呢?答案是肯定的,这其实就是价值迭代算法,它可以被认为是一种策略评估只进行了一轮更新的策略迭代算法。需要注意的是,价值迭代中不存在显式的策略,我们只维护一个状态价值函数。

确切来说,价值迭代可以看成一种动态规划过程,它利用的是贝尔曼最优方程:
V ∗ ( s ) = max ⁡ a ∈ A { r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V ∗ ( s ′ ) } V^{*}(s)=\max _{a \in \mathcal{A}}\left\{r(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right) V^{*}\left(s^{\prime}\right)\right\} V(s)=aAmax{r(s,a)+γsSP(ss,a)V(s)}
将其写成迭代更新的方式为
V k + 1 ( s ) = max ⁡ a ∈ A { r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V k ( s ′ ) } V^{k+1}(s)=\max _{a \in \mathcal{A}}\left\{r(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right) V^{k}\left(s^{\prime}\right)\right\} Vk+1(s)=aAmax{r(s,a)+γsSP(ss,a)Vk(s)}
价值迭代便是按照以上更新方式进行的。等到 V k + 1 V^{k+1} Vk+1 V k V^k Vk相同时,它就是贝尔曼最优方程的不动点,此时对应着最优状态价值函数 V ∗ V^* V。然后我们利用
π ( s ) = arg ⁡ max ⁡ a { r ( s , a ) + γ ∑ s ′ p ( s ′ ∣ s , a ) V k + 1 ( s ′ ) \pi(s)=\arg \max _{a}\left\{r(s, a)+\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) V^{k+1}\left(s^{\prime}\right)\right. π(s)=argamax{r(s,a)+γsp(ss,a)Vk+1(s)
从中恢复出最优策略即可。

值函数迭代算法的伪代码如下:


随机初始化策略价值函数 V ( s ) V(s) V(s)

  • While Δ > θ \Delta > \theta Δ>θ do: (策略评估循环)
    • Δ ← 0 \Delta \leftarrow 0 Δ0
    • For s ∈ S s\in \mathcal{S} sS
      • v ← V ( S ) v \leftarrow V(\mathcal{S}) vV(S)
      • V ( s ) ← max ⁡ a r ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V ( s ′ ) V(s) \leftarrow \max _{a} r(s, a)+\gamma \sum_{s^{\prime}} P\left(s^{\prime} \mid s, a\right) V\left(s^{\prime}\right) V(s)maxar(s,a)+γsP(ss,a)V(s)
      • Δ ← max ⁡ ( Δ , ∣ v − V ( s ) ∣ ) \Delta \leftarrow \max (\Delta,|v-V(s)|) Δmax(Δ,vV(s))
    • End For
  • End While
  • 返回一个确定性策略 π ( s ) = arg ⁡ max ⁡ a { r ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V ( s ′ ) } \pi(s)=\arg \max _{a}\left\{r(s, a)+\gamma \sum_{s^{\prime}} P\left(s^{\prime} \mid s, a\right) V\left(s^{\prime}\right)\right\} π(s)=argmaxa{r(s,a)+γsP(ss,a)V(s)}

从伪代码中,可以看到在每次迭代过程,需要对状态空间进行一次扫描,同时在每个状态对动作空间进行扫描以便得到贪婪的策略。文章来源地址https://www.toymoban.com/news/detail-403610.html

参考

  • 《深入浅出强化学习》
  • 《动手学强化学习》

到了这里,关于基于动态规划的强化学习方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 基于sumo实现交通的拥堵预测和路径动态规划 基于机器学习或者深度学习方法动态预测各路段的拥堵指数

    基于sumo实现交通的拥堵预测和路径动态规划 实现思路: 1、基于机器学习或者深度学习方法动态预测各路段的拥堵指数。 2、采用A* Dijkstra实现车辆的路径实时动态规划 基于sumo实现交通的拥堵预测和路径动态规划 随着城市化进程的加速以及交通运输工具的不断普及,城市交

    2024年04月17日
    浏览(42)
  • 基于动态规划的强化学习算法

    学习「强化学习」(基于这本教材,强烈推荐)时的一些总结,在此记录一下。 在马尔可夫决策过程 环境模型已知 (也就是状态转移函数P、奖励函数r已知)的情况下,我们可以通过 「动态规划」 求得马尔可夫决策过程的最优策略 (pi^*) 。 对于做过算法题目的同学而言,

    2024年03月09日
    浏览(42)
  • 【机器学习】强化学习(二)基于动态规划的算法

    值函数可以分为状态价值函数和动作价值函数,分别适用于哪些强化学习问题 二、基于动态规划的算法 2.1 策略迭代算法 示例: 代码 首先定义了一些参数,如奖励、折扣因子、最大误差等,然后初始化了一个网格世界的环境,包括状态、动作、价值函数和策略。接着,它定

    2024年01月21日
    浏览(46)
  • 基于注意力神经网络的深度强化学习探索方法:ARiADNE

    参考论文:Cao Y, Hou T, Wang Y, et al. Ariadne: A reinforcement learning approach using attention-based deep networks for exploration[J]. arXiv preprint arXiv:2301.11575, 2023. 2023 IEEE International Conference on Robotics and Automation (ICRA 2023) ARE的传统边界法 自主机器人探索(Autonomous robot exploration, ARE) 目标: ARE的目标是规

    2024年02月12日
    浏览(46)
  • 【论文笔记】IntelliLight智能交通灯:一种基于强化学习的智能交通信号灯控制方法

    博客声明:本文仅为个人论文阅读笔记,大部分原文对照的中文为翻译而来,只对其中错误明显的部分作了修改。其他一些个人理解不到位或有误的地方也尽请见谅。 标题原文: IntelliLight:A Reinforcement Learning Approach for Intelligent Traffic Light Control 论文来源: Proceedings of the 24

    2024年04月12日
    浏览(61)
  • 通识强化学习,初步了解强化学习的运行规则和估值方法

    目录 1.强化学习的发展及应用现状 1.1.强化学习的由来 1.2.强化学习的应用 2.强化学习的基本概念 2.1.概要介绍 2.2.强化学习的构成要素 2.3.工作过程 2.4.强化学习的主要特点 2.5.与其他机器学习方法的区别 3.估值方法 3.1.估值的方式 3.2.依据更新方式 目前,大家认为强化学习(

    2024年02月16日
    浏览(43)
  • 无模型的强化学习方法

    学习「强化学习」(基于这本教材,强烈推荐)时的一些总结,在此记录一下。 动态规划算法需要马尔可夫决策过程是已知的(状态转移函数、奖励函数已知),智能体不用真正地与环境互动也能在「理性」世界里求得最优策略。 现实通常并非如此,环境已知恰恰是很少见

    2024年03月09日
    浏览(48)
  • 强化学习系列--时序差分学习方法(SARSA算法)

    SARSA(State-Action-Reward-State-Action)是一种强化学习算法,用于解决马尔可夫决策过程(MDP)中的问题。 SARSA算法属于基于值的强化学习算法 ,用于学习最优策略。 在SARSA算法中,智能体通过与环境进行交互来学习。它基于 当前状态、选择的动作、获得的奖励、下一个状态和下

    2024年02月11日
    浏览(36)
  • 强化学习价值函数方法笔记

    在强化学习中,价值函数(Value Function)是一个核心概念,它用于衡量在不同状态或状态-动作对下,一个智能体(agent)可以获得的预期累积奖励。价值函数对于智能体做出决策和学习行为策略非常重要。 价值函数可以分为两种类型: 状态价值函数(State Value Function):记作

    2024年02月15日
    浏览(37)
  • 强化学习:蒙特卡洛方法(MC)

       以抛硬币为例,将结果(正面朝上或反面朝上)表示为作为随机变量 X X X ,如果正面朝上则 X = + 1 X=+1 X = + 1 ,如果反面朝上,则 X = − 1 X=-1 X = − 1 ,现在要计算 E [ X ] E[X] E [ X ] 。    我们通常很容易想到直接用定义来计算,因为我们知道正面朝上和反面朝上的概率都是

    2024年02月08日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包