0


强化学习入门笔记

强化学习

相关概念

我们先回忆一下童年,来看看超级玛丽这款游戏

在这里插入图片描述

在这款游戏里面的,我们需要控制超级玛丽进行左右行走、跳、攻击等动作,来躲避或攻击小动物、吃金币以及各种类型的增益道具。最终,获得的金币数量的多少以及通关代表我们玩游戏玩的好不好。

那么,如果我们希望让机器来玩这个游戏呢?怎么能让机器在合适的时候做出合适的动作?这就是强化学习要学的东西。

模型表示

在强化学习中,我们把超级玛丽称作智能体(Agent),而把游戏机制称作环境(Environment),把每一帧画面称作状态(State),把超级玛丽的行为称为动作(Action),把获得的金币数量或者通关称为奖励或回报(Reward)

我们玩一局超级玛丽开始的画面是固定的,这叫初始状态。我们根据状态选择执行合适的动作,这叫策略,通常表示为

    π
   
   
    (
   
   
    a
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   \pi(a|s)
  
 
π(a∣s)。通常策略分为随机性策略和确定性策略,随机性策略即

 
  
   
    a
   
   
    ∼
   
   
    π
   
   
    (
   
   
    a
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   a\sim \pi(a|s)
  
 
a∼π(a∣s),确定性策略即

 
  
   
    a
   
   
    =
   
   
    π
   
   
    (
   
   
    s
   
   
    )
   
  
  
   a = \pi(s)
  
 
a=π(s)。

执行动作之后,游戏画面更新,这个过程叫做状态转移。当游戏失败或通关时,到达终止状态

所以一局游戏就是给定初始状态下,不断地发生状态转移直到到达终止状态的过程。我们把这整个过程叫做马尔科夫决策过程,并且我们把从初态到终态的其中一种可能的序列称为一条轨迹。即

    τ
   
   
    =
   
   
    
     s
    
    
     0
    
   
   
    ,
   
   
    
     a
    
    
     0
    
   
   
    ,
   
   
    
     r
    
    
     1
    
   
   
    ,
   
   
    
     s
    
    
     1
    
   
   
    ,
   
   
    
     a
    
    
     1
    
   
   
    ,
   
   
    
     r
    
    
     2
    
   
   
    ,
   
   
    
     s
    
    
     2
    
   
   
    ,
   
   
    .
   
   
    .
   
   
    .
   
   
    ,
   
   
    
     s
    
    
     T
    
   
  
  
   \tau = s_0,a_0,r_1,s_1,a_1,r_2,s_2,...,s_T
  
 
τ=s0​,a0​,r1​,s1​,a1​,r2​,s2​,...,sT​

在这里插入图片描述

在这里插入图片描述

从图上我们可以看出所谓的马尔科夫决策过程就是一个有向图模型,回报是我们附加的用于训练的概念,它本质上与模型无关,通常是当前状态和动作的函数,因此不参与有向图的概率分解。

因此我们可以对马尔科夫决策过程的一条轨迹进行建模

     p
    
    
     (
    
    
     τ
    
    
     )
    
    
     =
    
    
     p
    
    
     (
    
    
     
      s
     
     
      0
     
    
    
     )
    
    
     
      ∏
     
     
      
       i
      
      
       =
      
      
       0
      
     
     
      
       T
      
      
       −
      
      
       1
      
     
    
    
     π
    
    
     (
    
    
     
      a
     
     
      i
     
    
    
     ∣
    
    
     
      s
     
     
      i
     
    
    
     )
    
    
     ∗
    
    
     p
    
    
     (
    
    
     
      s
     
     
      
       i
      
      
       +
      
      
       1
      
     
    
    
     ∣
    
    
     
      s
     
     
      i
     
    
    
     ,
    
    
     
      a
     
     
      i
     
    
    
     )
    
   
   
     p(\tau) = p(s_0)\prod_{i=0}^{T-1} \pi(a_i|s_i)*p(s_{i+1}|s_i,a_i) 
   
  
 p(τ)=p(s0​)i=0∏T−1​π(ai​∣si​)∗p(si+1​∣si​,ai​)

这就是强化学习的模型表示。

目标函数

从机器学习的三要素出发,在明确模型之后,我们应该考虑学习准则或者叫目标函数。

强化学习中,要评估策略的好坏,跟奖励有关。

当我们根据策略做出一个动作后,我们可以根据即时奖励来评估动作的好坏

       G
      
      
       t
      
     
     
      =
     
     
      
       r
      
      
       
        t
       
       
        +
       
       
        1
       
      
     
    
   
   
     {\large G_t = r_{t+1}} 
   
  
 Gt​=rt+1​

但这样我们或许就成了短视的人,只能看到当前的好处,看不到大局。因此,另一个方案是采用从该时刻开始到游戏结束时的累计奖励作为评估标准,这样我们就能纵观全局,考虑了当前动作对未来的深远影响。

       G
      
      
       t
      
     
     
      =
     
     
      
       r
      
      
       
        t
       
       
        +
       
       
        1
       
      
     
     
      +
     
     
      
       r
      
      
       
        t
       
       
        +
       
       
        2
       
      
     
     
      +
     
     
      .
     
     
      .
     
     
      .
     
     
      +
     
     
      
       r
      
      
       T
      
     
    
   
   
     {\large G_t = r_{t+1}+r_{t+2}+...+r_T} 
   
  
 Gt​=rt+1​+rt+2​+...+rT​

但是这样也有问题,有的时候后期的奖励跟我们当前的动作其实并没有太大联系,我们加上后期奖励之后反倒有可能产生错误的评估结果。因此出现了一种折中的办法,即增加折扣率

        G
       
       
        t
       
      
      
       =
      
      
       
        r
       
       
        
         t
        
        
         +
        
        
         1
        
       
      
      
       +
      
      
       γ
      
      
       
        r
       
       
        
         t
        
        
         +
        
        
         2
        
       
      
      
       +
      
      
       
        γ
       
       
        2
       
      
      
       
        r
       
       
        
         t
        
        
         +
        
        
         3
        
       
      
      
       +
      
      
       .
      
      
       .
      
      
       .
      
      
       
        γ
       
       
        
         T
        
        
         −
        
        
         1
        
       
      
      
       
        r
       
       
        T
       
      
     
    
   
   
     {\large {G_t = r_{t+1}+\gamma r_{t+2}+ \gamma^2 r_{t+3}+...\gamma^{T-1}r_T} } 
   
  
 Gt​=rt+1​+γrt+2​+γ2rt+3​+...γT−1rT​

我们可以看到,当

    γ
   
  
  
   \gamma
  
 
γ为0时,为第一种情况,

 
  
   
    γ
   
  
  
   \gamma
  
 
γ为1时,为第二种情况,

 
  
   
    0
   
   
    <
   
   
    γ
   
   
    <
   
   
    1
   
  
  
   0<\gamma<1
  
 
0<γ<1时,即为折中的办法,可根据现实情况自由调整。

因为策略和状态转移都有一定的随机性,所以每次试验得到的轨迹是一个随机序列,其收获的总回报也不一样。强化学习的目标是学习到一个策略

     π
    
    
     θ
    
   
   
    (
   
   
    a
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   \pi_\theta(a|s)
  
 
πθ​(a∣s)来最大化期望回报(Expected Return),即希望智能体执行一系列的动作来获得尽可能多的平均回报。

 
  
   
    
     
      
       J
      
      
       (
      
      
       θ
      
      
       )
      
      
       =
      
      
       
        E
       
       
        
         τ
        
        
         ∼
        
        
         
          p
         
         
          θ
         
        
        
         (
        
        
         τ
        
        
         )
        
       
      
      
       [
      
      
       G
      
      
       (
      
      
       τ
      
      
       )
      
      
       ]
      
      
       =
      
      
       
        E
       
       
        
         τ
        
        
         ∼
        
        
         
          p
         
         
          θ
         
        
        
         (
        
        
         τ
        
        
         )
        
       
      
      
       [
      
      
       
        G
       
       
        0
       
      
      
       ]
      
      
       =
      
      
       
        E
       
       
        
         τ
        
        
         ∼
        
        
         
          p
         
         
          θ
         
        
        
         (
        
        
         τ
        
        
         )
        
       
      
      
       [
      
      
       
        ∑
       
       
        
         t
        
        
         =
        
        
         0
        
       
       
        
         T
        
        
         −
        
        
         1
        
       
      
      
       
        γ
       
       
        t
       
      
      
       
        r
       
       
        
         t
        
        
         +
        
        
         1
        
       
      
      
       ]
      
     
    
   
   
     {\large {J(\theta) = \mathbb{E}_{\tau\sim p_\theta(\tau)}[G(\tau)] = \mathbb{E}_{\tau\sim p_\theta(\tau)}[G_0]= \mathbb{E}_{\tau\sim p_\theta(\tau)}[\sum_{t=0}^{T-1}\gamma^tr_{t+1}]} } 
   
  
 J(θ)=Eτ∼pθ​(τ)​[G(τ)]=Eτ∼pθ​(τ)​[G0​]=Eτ∼pθ​(τ)​[t=0∑T−1​γtrt+1​]

为什么最大化期望回报就能作为强化学习的目标?

显然不同的轨迹导致不同的结果,我们希望回报越大的轨迹对应的概率越大,反过来,如果回报大的轨迹对应的概率小,那么得到的期望回报就越小。因此,最大化期望回报就会使得学习出来的模型会尽可能让大回报的轨迹更可能发生。

值函数

对我来说,值函数并不是先验的概念。我的意思是,前面所介绍的概念都是在定义强化学习时所必须的概念,不可或缺。但值函数确实在强化学习定义下,为了解决问题而导出的数学概念。

我们重新考虑期望回报的问题,虽然我们明确了强化学习的目标函数是期望回报,但并没有说如何计算它。显然如果直接按照期望的定义计算那是非常复杂的,因为我们根本不可能列出所有可能的轨迹。

于是贝尔曼通过动态规划的思想简化了它的计算问题

首先,

            E
           
           
            
             τ
            
            
             ∼
            
            
             p
            
            
             (
            
            
             τ
            
            
             )
            
           
          
          
           [
          
          
           G
          
          
           (
          
          
           τ
          
          
           )
          
          
           ]
          
         
        
       
       
        
         
          
          
           =
          
          
           
            E
           
           
            
             s
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               0
              
             
             
              )
             
            
           
          
          
           
            [
           
           
            
             E
            
            
             
              τ
             
             
              ∼
             
             
              p
             
             
              (
             
             
              τ
             
             
              )
             
            
           
           
            
             [
            
            
             
              ∑
             
             
              
               t
              
              
               =
              
              
               0
              
             
             
              
               T
              
              
               −
              
              
               1
              
             
            
            
             
              γ
             
             
              t
             
            
            
             
              r
             
             
              
               t
              
              
               +
              
              
               1
              
             
            
            
             ∣
            
            
             
              τ
             
             
              
               s
              
              
               0
              
             
            
            
             =
            
            
             s
            
            
             ]
            
           
           
            ]
           
          
         
        
       
      
      
       
        
         
        
       
       
        
         
          
          
           =
          
          
           
            E
           
           
            
             s
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               0
              
             
             
              )
             
            
           
          
          
           
            [
           
           
            
             V
            
            
             π
            
           
           
            (
           
           
            s
           
           
            )
           
           
            ]
           
          
         
        
       
      
     
    
   
   
     {\large \mathbf{\begin{aligned} \mathbb{E}_{\tau \sim p(\tau)}[G(\tau)] &=\mathbb{E}_{s \sim p\left(s_{0}\right)}\left[\mathbb{E}_{\tau \sim p(\tau)}\left[\sum_{t=0}^{T-1} \gamma^{t} r_{t+1} \mid \tau_{s_{0}}=s\right]\right] \\ &=\mathbb{E}_{s \sim p\left(s_{0}\right)}\left[V^{\pi}(s)\right] \end{aligned}} } 
   
  
 Eτ∼p(τ)​[G(τ)]​=Es∼p(s0​)​⎣⎡​Eτ∼p(τ)​⎣⎡​t=0∑T−1​γtrt+1​∣τs0​​=s⎦⎤​⎦⎤​=Es∼p(s0​)​[Vπ(s)]​

我们把

     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V^\pi(s)
  
 
Vπ(s)称为状态价值函数,即在给定初始状态为s的情况的期望回报

 
  
   
    
     
      
       
        V
       
       
        π
       
      
      
       (
      
      
       s
      
      
       )
      
      
       =
      
      
       
        E
       
       
        
         τ
        
        
         ∼
        
        
         p
        
        
         (
        
        
         τ
        
        
         )
        
       
      
      
       
        [
       
       
        
         ∑
        
        
         
          t
         
         
          =
         
         
          0
         
        
        
         
          T
         
         
          −
         
         
          1
         
        
       
       
        
         γ
        
        
         t
        
       
       
        
         r
        
        
         
          t
         
         
          +
         
         
          1
         
        
       
       
        ∣
       
       
        
         τ
        
        
         
          s
         
         
          0
         
        
       
       
        =
       
       
        s
       
       
        ]
       
      
     
    
   
   
     {\large {V^\pi(s) = \mathbb{E}_{\tau \sim p(\tau)}\left[\sum_{t=0}^{T-1} \gamma^{t} r_{t+1} \mid \tau_{s_{0}}=s\right]}} 
   
  
 Vπ(s)=Eτ∼p(τ)​⎣⎡​t=0∑T−1​γtrt+1​∣τs0​​=s⎦⎤​

经过一系列的数学手段

            V
           
           
            π
           
          
          
           (
          
          
           s
          
          
           )
          
          
           =
          
          
           
            E
           
           
            
             τ
            
            
             
              0
             
             
              :
             
             
              T
             
             
              ∼
             
             
              p
             
            
           
          
          
           
            [
           
           
            
             r
            
            
             1
            
           
           
            +
           
           
            γ
           
           
            
             ∑
            
            
             
              t
             
             
              =
             
             
              1
             
            
            
             
              T
             
             
              −
             
             
              1
             
            
           
           
            
             γ
            
            
             
              t
             
             
              −
             
             
              1
             
            
           
           
            
             r
            
            
             
              t
             
             
              +
             
             
              1
             
            
           
           
            ∣
           
           
            
             τ
            
            
             
              s
             
             
              0
             
            
           
           
            =
           
           
            s
           
           
            ]
           
          
         
        
       
      
      
       
        
         
          
           =
          
          
           
            E
           
           
            
             a
            
            
             ∼
            
            
             π
            
            
             (
            
            
             a
            
            
             ∣
            
            
             s
            
            
             )
            
           
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            E
           
           
            
             
              τ
             
             
              
               1
              
              
               :
              
              
               T
              
             
            
            
             ∼
            
            
             p
            
            
             (
            
            
             τ
            
            
             )
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             ∑
            
            
             
              t
             
             
              =
             
             
              1
             
            
            
             
              T
             
             
              −
             
             
              1
             
            
           
           
            
             γ
            
            
             
              t
             
             
              −
             
             
              1
             
            
           
           
            
             r
            
            
             
              t
             
             
              +
             
             
              1
             
            
           
           
            ∣
           
           
            
             τ
            
            
             
              s
             
             
              1
             
            
           
           
            =
           
           
            
             s
            
            
             ′
            
           
           
            ]
           
          
         
        
       
      
      
       
        
         
          
           =
          
          
           
            E
           
           
            
             a
            
            
             ∼
            
            
             π
            
            
             (
            
            
             a
            
            
             ∣
            
            
             s
            
            
             )
            
           
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             E
            
            
             
              
               τ
              
              
               
                1
               
               
                :
               
               
                T
               
              
             
             
              ∼
             
             
              p
             
             
              (
             
             
              τ
             
             
              )
             
            
           
           
            
             [
            
            
             
              ∑
             
             
              
               t
              
              
               =
              
              
               1
              
             
             
              
               T
              
              
               −
              
              
               1
              
             
            
            
             
              γ
             
             
              
               t
              
              
               −
              
              
               1
              
             
            
            
             
              r
             
             
              
               t
              
              
               +
              
              
               1
              
             
            
            
             ∣
            
            
             
              τ
             
             
              
               s
              
              
               1
              
             
            
            
             =
            
            
             
              s
             
             
              ′
             
            
            
             ]
            
           
           
            ]
           
          
         
        
       
      
      
       
        
         
          
           =
          
          
           
            E
           
           
            
             a
            
            
             ∼
            
            
             π
            
            
             (
            
            
             a
            
            
             ∣
            
            
             s
            
            
             )
            
           
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             V
            
            
             π
            
           
           
            
             (
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            ]
           
          
          
           .
          
         
        
       
      
     
    
   
   
     {\large \mathbf{\begin{array}{l} V^{\pi}(s)=\mathbb{E}_{\tau_{0: T \sim p}}\left[r_{1}+\gamma \sum_{t=1}^{T-1} \gamma^{t-1} r_{t+1} \mid \tau_{s_{0}}=s\right] \\ =\mathbb{E}_{a \sim \pi(a \mid s)} \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)} \mathbb{E}_{\tau_{1: T} \sim p(\tau)}\left[r\left(s, a, s^{\prime}\right)+\gamma \sum_{t=1}^{T-1} \gamma^{t-1} r_{t+1} \mid \tau_{s_{1}}=s^{\prime}\right] \\ =\mathbb{E}_{a \sim \pi(a \mid s)} \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma \mathbb{E}_{\tau_{1: T} \sim p(\tau)}\left[\sum_{t=1}^{T-1} \gamma^{t-1} r_{t+1} \mid \tau_{s_{1}}=s^{\prime}\right]\right] \\ =\mathbb{E}_{a \sim \pi(a \mid s)} \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right] . \end{array}} } 
   
  
 Vπ(s)=Eτ0:T∼p​​[r1​+γ∑t=1T−1​γt−1rt+1​∣τs0​​=s]=Ea∼π(a∣s)​Es′∼p(s′∣s,a)​Eτ1:T​∼p(τ)​[r(s,a,s′)+γ∑t=1T−1​γt−1rt+1​∣τs1​​=s′]=Ea∼π(a∣s)​Es′∼p(s′∣s,a)​[r(s,a,s′)+γEτ1:T​∼p(τ)​[∑t=1T−1​γt−1rt+1​∣τs1​​=s′]]=Ea∼π(a∣s)​Es′∼p(s′∣s,a)​[r(s,a,s′)+γVπ(s′)].​

我们最终得到了

     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V_\pi(s)
  
 
Vπ​(s)的迭代关系,这个关系叫做**贝尔曼方程**。

可以证明,只要给定策略和状态转移概率,那么我们可以随机初始化

     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V_\pi(s)
  
 
Vπ​(s)的值,通过反复迭代,最终会收敛到一个正确的状态价值函数。至于证明方法我们暂且不管。

仅有一个状态值函数还不够,毕竟在计算

     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V^\pi(s)
  
 
Vπ(s)之前,我们需要先知道策略

 
  
   
    π
   
   
    (
   
   
    a
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   \pi(a|s)
  
 
π(a∣s),但是好巧不巧的是强化学习学的就是

 
  
   
    π
   
   
    (
   
   
    a
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   \pi(a|s)
  
 
π(a∣s)…

那就这样吧,我们也不用最大化期望回报了,我们直接通过最大化状态价值函数来求

    π
   
  
  
   \pi
  
 
π

 
  
   
    
     π
    
    
     =
    
    
     a
    
    
     r
    
    
     g
    
    
     m
    
    
     a
    
    
     
      x
     
     
      π
     
    
    
     
      V
     
     
      π
     
    
    
     (
    
    
     s
    
    
     )
    
   
   
     \pi = argmax_\pi V^\pi(s) 
   
  
 π=argmaxπ​Vπ(s)

其实我们很容易想到,这东西肯定没有闭式解。所以只能通过迭代的方式更新

    π
   
  
  
   \pi
  
 
π,但是要怎么更新呢?

其实有两种方法,我们后面会讲到,现在先简单提一下。一个是将

    π
   
  
  
   \pi
  
 
π参数化成

 
  
   
    
     π
    
    
     θ
    
   
   
    (
   
   
    a
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   \pi_\theta(a|s)
  
 
πθ​(a∣s),我们通过计算期望回报对

 
  
   
    θ
   
  
  
   \theta
  
 
θ的梯度从而使用梯度下降的算法优化

 
  
   
    θ
   
  
  
   \theta
  
 
θ。另一个就是我们下面要讲的东西。

我们需要引入一个新的概念叫做状态-动作价值函数

        Q
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
      
       =
      
      
       
        E
       
       
        
         
          s
         
         
          ′
         
        
        
         ∼
        
        
         p
        
        
         
          (
         
         
          
           s
          
          
           ′
          
         
         
          ∣
         
         
          s
         
         
          ,
         
         
          a
         
         
          )
         
        
       
      
      
       
        [
       
       
        r
       
       
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         ,
        
        
         
          s
         
         
          ′
         
        
        
         )
        
       
       
        +
       
       
        γ
       
       
        
         V
        
        
         π
        
       
       
        
         (
        
        
         
          s
         
         
          ′
         
        
        
         )
        
       
       
        ]
       
      
     
    
   
   
     {\large \mathbf{Q^\pi(s,a) = \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right]}} 
   
  
 Qπ(s,a)=Es′∼p(s′∣s,a)​[r(s,a,s′)+γVπ(s′)]


 
  
   
    
     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
  
  
   Q^\pi(s,a)
  
 
Qπ(s,a)表示给定初始状态和初始动作后的期望回报,通过

 
  
   
    
     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
  
  
   Q^\pi(s,a)
  
 
Qπ(s,a)的定义,我们可以将

 
  
   
    
     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V^\pi(s)
  
 
Vπ(s)的自迭代转变为

 
  
   
    
     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V^\pi(s)
  
 
Vπ(s)与

 
  
   
    
     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   Q^\pi(s)
  
 
Qπ(s)的相互迭代。因为

 
  
   
    
     
      
       
        V
       
       
        π
       
      
      
       (
      
      
       s
      
      
       )
      
      
       =
      
      
       
        E
       
       
        
         a
        
        
         ∼
        
        
         π
        
        
         (
        
        
         a
        
        
         ∣
        
        
         s
        
        
         )
        
       
      
      
       
        Q
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
     
    
   
   
     {\large \mathbf{V^\pi(s) = \mathbb{E}_{a \sim \pi(a \mid s)} Q^\pi(s,a)}} 
   
  
 Vπ(s)=Ea∼π(a∣s)​Qπ(s,a)

那么为什么非要引入它呢?

假设在状态s,有一个动作

     a
    
    
     ∗
    
   
  
  
   a^*
  
 
a∗,如果

 
  
   
    
     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    
     a
    
    
     ∗
    
   
   
    )
   
   
    =
   
   
    
     
      max
     
     
      ⁡
     
    
    
     a
    
   
   
    
     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
  
  
   Q^\pi(s,a^*) = \max_a Q^\pi(s,a)
  
 
Qπ(s,a∗)=maxa​Qπ(s,a),这样一来就是说在状态

 
  
   
    s
   
  
  
   s
  
 
s下执行动作

 
  
   
    
     a
    
    
     ∗
    
   
  
  
   a^*
  
 
a∗是回报最高的。所以我们自然可以调高

 
  
   
    π
   
   
    (
   
   
    
     a
    
    
     ∗
    
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   \pi(a^*|s)
  
 
π(a∗∣s)的值从而达到优化策略的目的

优化算法

在介绍完强化学习的模型表示和目标函数后,自然而然来到第三个要素,即优化算法。强化学习的算法主要分为两大类。一类是基于值函数的优化算法,另一类是基于策略优化的算法。强化学习算法分类如图

#mermaid-svg-BRagHRkUyzx8xNME {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-BRagHRkUyzx8xNME .error-icon{fill:#552222;}#mermaid-svg-BRagHRkUyzx8xNME .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-BRagHRkUyzx8xNME .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-BRagHRkUyzx8xNME .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-BRagHRkUyzx8xNME .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-BRagHRkUyzx8xNME .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-BRagHRkUyzx8xNME .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-BRagHRkUyzx8xNME .marker{fill:#333333;stroke:#333333;}#mermaid-svg-BRagHRkUyzx8xNME .marker.cross{stroke:#333333;}#mermaid-svg-BRagHRkUyzx8xNME svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-BRagHRkUyzx8xNME .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-BRagHRkUyzx8xNME .cluster-label text{fill:#333;}#mermaid-svg-BRagHRkUyzx8xNME .cluster-label span{color:#333;}#mermaid-svg-BRagHRkUyzx8xNME .label text,#mermaid-svg-BRagHRkUyzx8xNME span{fill:#333;color:#333;}#mermaid-svg-BRagHRkUyzx8xNME .node rect,#mermaid-svg-BRagHRkUyzx8xNME .node circle,#mermaid-svg-BRagHRkUyzx8xNME .node ellipse,#mermaid-svg-BRagHRkUyzx8xNME .node polygon,#mermaid-svg-BRagHRkUyzx8xNME .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-BRagHRkUyzx8xNME .node .label{text-align:center;}#mermaid-svg-BRagHRkUyzx8xNME .node.clickable{cursor:pointer;}#mermaid-svg-BRagHRkUyzx8xNME .arrowheadPath{fill:#333333;}#mermaid-svg-BRagHRkUyzx8xNME .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-BRagHRkUyzx8xNME .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-BRagHRkUyzx8xNME .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-BRagHRkUyzx8xNME .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-BRagHRkUyzx8xNME .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-BRagHRkUyzx8xNME .cluster text{fill:#333;}#mermaid-svg-BRagHRkUyzx8xNME .cluster span{color:#333;}#mermaid-svg-BRagHRkUyzx8xNME div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-BRagHRkUyzx8xNME :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}

      强化学习
     

      策略优化
     

      值函数优化
     

      策略梯度
     

      Reinforce算法
     

      Reinforce-With-Baseline
     

      模型已知
     

      模型未知
     

      动态规划
     

      蒙特卡罗
     

      时序差分
     

      策略迭代
     

      值迭代
     

      Sarsa
     

      Q-Learning
     

基于值函数的优化算法一般采用确定性策略,基于策略优化的算法则一般采用随机性策略,当然也适用于确定性策略。

动态规划

之所以叫动态规划算法,是因为这一类的算法都是基于贝尔曼方程的价值迭代。让我们回顾一下贝尔曼方程

        Q
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
      
       =
      
      
       
        E
       
       
        
         
          s
         
         
          ′
         
        
        
         ∼
        
        
         p
        
        
         
          (
         
         
          
           s
          
          
           ′
          
         
         
          ∣
         
         
          s
         
         
          ,
         
         
          a
         
         
          )
         
        
       
      
      
       
        [
       
       
        r
       
       
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         ,
        
        
         
          s
         
         
          ′
         
        
        
         )
        
       
       
        +
       
       
        γ
       
       
        
         V
        
        
         π
        
       
       
        
         (
        
        
         
          s
         
         
          ′
         
        
        
         )
        
       
       
        ]
       
      
     
    
    
    
     
      
       
        V
       
       
        π
       
      
      
       (
      
      
       s
      
      
       )
      
      
       =
      
      
       
        E
       
       
        
         a
        
        
         ∼
        
        
         π
        
        
         (
        
        
         a
        
        
         ∣
        
        
         s
        
        
         )
        
       
      
      
       
        Q
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
     
    
   
   
     {\large \mathbf{Q^\pi(s,a) = \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right]}} \\ {\large \mathbf{V^\pi(s) = \mathbb{E}_{a \sim \pi(a \mid s)} Q^\pi(s,a)}} 
   
  
 Qπ(s,a)=Es′∼p(s′∣s,a)​[r(s,a,s′)+γVπ(s′)]Vπ(s)=Ea∼π(a∣s)​Qπ(s,a)

我们之前介绍过,

    π
   
  
  
   \pi
  
 
π只能通过反复迭代获得,但在介绍了状态价值函数之后,我们可以对迭代对象有更多的考虑,因为对于确定性策略,有

 
  
   
    
     π
    
    
     (
    
    
     s
    
    
     )
    
    
     =
    
    
     a
    
    
     r
    
    
     g
    
    
     m
    
    
     a
    
    
     
      x
     
     
      a
     
    
    
     Q
    
    
     (
    
    
     s
    
    
     ,
    
    
     a
    
    
     )
    
   
   
     \pi(s) = argmax_aQ(s,a) 
   
  
 π(s)=argmaxa​Q(s,a)

也就是说,如果我们能得到最优的状态动作价值函数,我们就能直接导出最优策略。所以现在有两个路子,一个是我们随机初始化策略和状态动作价值函数,然后在当前策略下通过贝尔曼方程求得最优的价值函数,最后根据价值函数更新策略这就叫策略迭代。另一个是我们随机初始化价值函数,然后通过价值函数导出当前最优策略,并根据最优策略更新价值函数,最终得到最优价值函数。这叫值迭代

策略迭代

通常我们把策略迭代分为两个阶段,即策略评估策略改进,策略评估顾名思义就是评估当前策略好不好,评估的标准就是价值函数,所以策略评估就是求价值函数。策略改进我们前面讲过,就是利用价值函数改进策略。之所以叫策略迭代就是因为我们主要的迭代对象就是策略,而价值函数只有一个中间过程。

值迭代

值迭代的对象是价值函数,策略更新反而变成了中间过程。可能从下面的算法过程第三行大家没有看到策略的出现,但其实里面已经包含了求根据价值函数导出最优策略的过程。

在这里插入图片描述

虽然从思想上策略迭代和值迭代刚好相反,但是在实际算法过程上,值迭代就相当于在使用贝尔曼方程计算价值函数时只迭代一次的策略迭代。

值得注意的是,上面介绍的是基于状态价值函数V的值迭代,但我们也可以使用状态动作价值函数Q

            Q
           
           
            π
           
          
          
           (
          
          
           s
          
          
           ,
          
          
           a
          
          
           )
          
         
        
       
       
        
         
          
          
           =
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             V
            
            
             π
            
           
           
            (
           
           
            
             s
            
            
             ′
            
           
           
            )
           
           
            ]
           
          
         
        
       
      
      
       
        
         
        
       
       
        
         
          
          
           =
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             
              max
             
             
              ⁡
             
            
            
             
              a
             
             
              ′
             
            
           
           
            
             Q
            
            
             π
            
           
           
            (
           
           
            
             s
            
            
             ′
            
           
           
            ,
           
           
            
             a
            
            
             ′
            
           
           
            )
           
           
            ]
           
          
         
        
       
      
     
    
   
   
     {\large \begin{aligned} Q^\pi(s,a) &= \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma V^\pi(s^\prime)\right] \\ &=\mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma \max_{a^\prime} Q^\pi(s^\prime,a^\prime)\right] \end{aligned}} 
   
  
 Qπ(s,a)​=Es′∼p(s′∣s,a)​[r(s,a,s′)+γVπ(s′)]=Es′∼p(s′∣s,a)​[r(s,a,s′)+γa′max​Qπ(s′,a′)]​

代码介绍

光贴个简单的算法截图大家可能还不能很好的理解这个过程,那么我们来看看实际的代码吧。

在介绍具体的算法代码之前,我们先来介绍一下整体框架。

首先是gym这个库,gym提供了强化学习需要的环境, 可以创造一些数据集, 用来测试和学习强化学习。

假如我们要产生一条完整的轨迹并计算回报

import gym
# 创建游戏环境
env = gym.make('CartPole-v0')# policy是一维的tensor,可以存放每个状态对应的动作defrun_episode(env, policy, gamma=1.0, render=False):
    obs = env.reset()
    total_reward =0
    step_idx =0whileTrue:# 显示游戏画面if render:
            env.render()
        obs, reward, done, _ = env.step(int(policy[obs]))# 计算折扣累积回报
        total_reward +=(gamma ** step_idx * reward)
        step_idx +=1if done:breakreturn total_reward

依照策略迭代的算法,我们的算法框架如下

# 总的策略迭代算法框架defpolicy_iteration(env, gamma=1.0):# 初始化一个随机策略# 即对每个状态赋予一个动作(确定性策略、状态离散)
    policy = np.random.choice(env.action_space.n, size=env.observation_space.n)
    max_iterations =20000
    gamma =1.0for i inrange(max_iterations):# 策略评估
        old_policy_v = compute_policy_v(env, policy, gamma)# 策略改进
        new_policy = extract_policy(env, old_policy_v, gamma)if(np.all(policy == new_policy)):# 判断策略是否收敛print('Policy-Iteration converged at iteration %d.'%(i +1))break
        policy = new_policy  # 如果没收敛,则以当前你策略为起点,继续循环策略评估和策略提升两个过程return policy

具体如何用贝尔曼方程计算价值函数,即如何进行策略评估

# 计算当前策略下的价值函数defcompute_policy_v(env, policy, gamma=1.0):# 初始化值函数为0
    v = np.zeros(env.observation_space.n)
    eps =1e-10whileTrue:
        prev_v = np.copy(v)# 遍历前一时刻的每一个状态for s inrange(env.observation_space.n -1):
            a = policy[s]
            v[s]=sum([p *(r + gamma * prev_v[s_])for p, s_, r, _ in env.env.P[s][a]])# 如果更新前后的值函数V小于给定阈值,说明收敛了,返回v_\piif np.sum((np.fabs(prev_v - v)))<= eps:print("Value function converged.")breakreturn v

策略改进,即根据公式

     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
   
    =
   
   
    
     E
    
    
     
      
       s
      
      
       ′
      
     
     
      ∼
     
     
      p
     
     
      
       (
      
      
       
        s
       
       
        ′
       
      
      
       ∣
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
     
    
   
   
    
     [
    
    
     r
    
    
     
      (
     
     
      s
     
     
      ,
     
     
      a
     
     
      ,
     
     
      
       s
      
      
       ′
      
     
     
      )
     
    
    
     +
    
    
     γ
    
    
     
      V
     
     
      π
     
    
    
     
      (
     
     
      
       s
      
      
       ′
      
     
     
      )
     
    
    
     ]
    
   
  
  
   \mathbf{Q^\pi(s,a) = \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right]}
  
 
Qπ(s,a)=Es′∼p(s′∣s,a)​[r(s,a,s′)+γVπ(s′)] 利用

 
  
   
    
     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V^\pi(s)
  
 
Vπ(s)求出

 
  
   
    
     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
  
  
   Q^\pi(s,a)
  
 
Qπ(s,a),然后根据

 
  
   
    
     Q
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
  
  
   Q^\pi(s,a)
  
 
Qπ(s,a)导出最优策略
# 主要步骤2:策略提升defextract_policy(env, v, gamma=1.0):# 初始化策略
    policy = np.zeros(env.observation_space.n -1)for s inrange(env.observation_space.n -1):
        q_sa = np.zeros(env.action_space.n)# 评估当前状态下,每个动作的收益for a inrange(env.action_space.n):# 计算动作值函数q
            q_sa[a]=sum([p *(r + gamma * v[s_])for p, s_, r, _ in env.env.P[s][a]])# 更新后的策略是相对于q的贪婪策略,所以使用max操作# 这里由于可能有多个最大值,我们等概率随机选择分配
        policy[s]= np.random.choice(np.argwhere(q_sa == np.max(q_sa)).flatten())# 返回提升的策略,根据策略提升理论,这个策略肯定比上一次迭代的策略要好return policy

完整代码见github(还没传,待续)

蒙特卡罗

在模型已知的情况下,也就是我们知道马尔科夫决策过程的状态转移概率时,我们可以才可以通过策略迭代或者值迭代的方法去求解最优策略。但是模型未知的情况下,我们没有办法直接精确计算贝尔曼方程中的期望了。于是蒙特卡罗算法提出,我们可以通过采样来近似Q函数。也就是经验分布近似期望(大数定律)的思想

     Q
    
    
     (
    
    
     s
    
    
     ,
    
    
     a
    
    
     )
    
    
     =
    
    
     
      Q
     
     
      ^
     
    
    
     (
    
    
     s
    
    
     ,
    
    
     a
    
    
     )
    
    
     =
    
    
     
      1
     
     
      N
     
    
    
     
      ∑
     
     
      
       i
      
      
       =
      
      
       1
      
     
     
      N
     
    
    
     G
    
    
     (
    
    
     
      τ
     
     
      i
     
    
    
     ∣
    
    
     
      s
     
     
      0
     
    
    
     =
    
    
     s
    
    
     ,
    
    
     
      a
     
     
      0
     
    
    
     =
    
    
     a
    
    
     )
    
   
   
     Q(s,a) = \hat Q(s,a) = \frac{1}{N}\sum_{i=1}^{N}G(\tau_i|s_0=s,a_0=a) 
   
  
 Q(s,a)=Q^​(s,a)=N1​i=1∑N​G(τi​∣s0​=s,a0​=a)

蒙特卡罗的增量形式

上面的基于蒙特卡罗的策略迭代虽然确实是一种方法,但它并不好。因为一次迭代需要进行SxAxN次采样。所以我们也想考虑一下蒙特卡罗算法与值迭代的结合。但是值迭代是利用贝尔曼方程更新价值函数,显然贝尔曼方程是用不了了,那么有什么新的迭代形式呢?

           Q
          
          
           ^
          
         
         
          N
         
         
          π
         
        
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         )
        
       
      
     
     
      
       
        
        
         =
        
        
         
          1
         
         
          N
         
        
        
         
          ∑
         
         
          
           n
          
          
           =
          
          
           1
          
         
         
          N
         
        
        
         G
        
        
         
          (
         
         
          
           τ
          
          
           
            
             s
            
            
             0
            
           
           
            =
           
           
            s
           
           
            ,
           
           
            
             a
            
            
             0
            
           
           
            =
           
           
            a
           
          
          
           
            (
           
           
            n
           
           
            )
           
          
         
         
          )
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          1
         
         
          N
         
        
        
         
          (
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             
              s
             
             
              0
             
            
            
             =
            
            
             s
            
            
             ,
            
            
             
              a
             
             
              0
             
            
            
             =
            
            
             a
            
           
           
            
             (
            
            
             N
            
            
             )
            
           
          
          
           )
          
         
         
          +
         
         
          
           ∑
          
          
           
            n
           
           
            =
           
           
            1
           
          
          
           
            N
           
           
            −
           
           
            1
           
          
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             
              s
             
             
              0
             
            
            
             =
            
            
             s
            
            
             ,
            
            
             
              a
             
             
              0
             
            
            
             =
            
            
             a
            
           
           
            
             (
            
            
             n
            
            
             )
            
           
          
          
           )
          
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          1
         
         
          N
         
        
        
         
          (
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             
              s
             
             
              0
             
            
            
             =
            
            
             s
            
            
             ,
            
            
             
              a
             
             
              0
             
            
            
             =
            
            
             a
            
           
           
            
             (
            
            
             N
            
            
             )
            
           
          
          
           )
          
         
         
          +
         
         
          (
         
         
          N
         
         
          −
         
         
          1
         
         
          )
         
         
          
           
            Q
           
           
            ^
           
          
          
           
            N
           
           
            −
           
           
            1
           
          
          
           π
          
         
         
          (
         
         
          s
         
         
          ,
         
         
          a
         
         
          )
         
         
          )
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          
           Q
          
          
           ^
          
         
         
          
           N
          
          
           −
          
          
           1
          
         
         
          π
         
        
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         )
        
        
         +
        
        
         
          1
         
         
          N
         
        
        
         
          (
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             
              s
             
             
              0
             
            
            
             =
            
            
             s
            
            
             ,
            
            
             
              a
             
             
              0
             
            
            
             =
            
            
             a
            
           
           
            
             (
            
            
             N
            
            
             )
            
           
          
          
           )
          
         
         
          −
         
         
          
           
            Q
           
           
            ^
           
          
          
           
            N
           
           
            −
           
           
            1
           
          
          
           π
          
         
         
          (
         
         
          s
         
         
          ,
         
         
          a
         
         
          )
         
         
          )
         
        
        
         .
        
       
      
     
    
   
   
     \begin{aligned} \hat{Q}_{N}^{\pi}(s, a) &=\frac{1}{N} \sum_{n=1}^{N} G\left(\tau_{s_{0}=s, a_{0}=a}^{(n)}\right) \\ &=\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)}\right)+\sum_{n=1}^{N-1} G\left(\tau_{s_{0}=s, a_{0}=a}^{(n)}\right)\right.\\ &=\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)}\right)+(N-1) \hat{Q}_{N-1}^{\pi}(s, a)\right) \\ &=\hat{Q}_{N-1}^{\pi}(s, a)+\frac{1}{N}\left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)} \right)-\hat{Q}_{N-1}^{\pi}(s, a)\right). \end{aligned} 
   
  
 Q^​Nπ​(s,a)​=N1​n=1∑N​G(τs0​=s,a0​=a(n)​)=N1​(G(τs0​=s,a0​=a(N)​)+n=1∑N−1​G(τs0​=s,a0​=a(n)​)=N1​(G(τs0​=s,a0​=a(N)​)+(N−1)Q^​N−1π​(s,a))=Q^​N−1π​(s,a)+N1​(G(τs0​=s,a0​=a(N)​)−Q^​N−1π​(s,a)).​

从结果来看,我们可以每增加一个样本,Q迭代一次,因为N是超参数,我们可以直接将1/N整体替换为

    α
   
  
  
   \alpha
  
 
α为作为新的超参数

 
  
   
    
     
      Q
     
     
      
       t
      
      
       +
      
      
       1
      
     
    
    
     (
    
    
     s
    
    
     ,
    
    
     a
    
    
     )
    
    
     =
    
    
     
      Q
     
     
      t
     
    
    
     (
    
    
     s
    
    
     ,
    
    
     a
    
    
     )
    
    
     +
    
    
     α
    
    
     
      (
     
     
      G
     
     
      
       (
      
      
       
        τ
       
       
        
         
          s
         
         
          0
         
        
        
         =
        
        
         s
        
        
         ,
        
        
         
          a
         
         
          0
         
        
        
         =
        
        
         a
        
       
       
        
         (
        
        
         N
        
        
         )
        
       
      
      
       )
      
     
     
      −
     
     
      
       
        Q
       
       
        ^
       
      
      
       
        N
       
       
        −
       
       
        1
       
      
      
       π
      
     
     
      (
     
     
      s
     
     
      ,
     
     
      a
     
     
      )
     
     
      )
     
    
   
   
     Q_{t+1}(s,a) = Q_t(s,a) + \alpha \left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)} \right)-\hat{Q}_{N-1}^{\pi}(s, a)\right) 
   
  
 Qt+1​(s,a)=Qt​(s,a)+α(G(τs0​=s,a0​=a(N)​)−Q^​N−1π​(s,a))

蒙特卡罗+策略迭代

假如我们把蒙特卡罗方法与策略迭代相结合,即将价值函数的计算部分用蒙特卡罗方法代替。另外我们这里用的价值函数是Q(s,a)不是V(s),因为其实我们更新策略需要的是Q,V的作用不大。

  • 随机初始化策略
  • 循环- 策略评估 - 遍历每一个 s s s,遍历每一个 a a a- 非增量形式:以 s , a s,a s,a作为初始状态和动作,然后根据策略采样N条轨迹,计算平均回报作为 Q ( s , a ) Q(s,a) Q(s,a)- 增量形式: - 随机初始化Q价值- 循环直到收敛- 以 s , a s,a s,a作为初始状态和动作,然后根据策略采样1条轨迹- Q t + 1 ( s , a ) = Q t ( s , a ) + α ( G ( τ s 0 = s , a 0 = a ( N ) ) − Q ^ N − 1 π ( s , a ) ) Q_{t+1}(s,a) = Q_t(s,a) + \alpha \left(G\left(\tau_{s_{0}=s, a_{0}=a}^{(N)} \right)-\hat{Q}_{N-1}^{\pi}(s, a)\right) Qt+1​(s,a)=Qt​(s,a)+α(G(τs0​=s,a0​=a(N)​)−Q^​N−1π​(s,a))- 策略改进 - 根据 π = a r g m a x a Q ( s , a ) \pi = argmax_aQ(s,a) π=argmaxa​Q(s,a)更新 π \pi π
  • 直到收敛

蒙特卡罗+值迭代

之所以迭代式中没有max,是因为max体现在直接使用Q函数进行采样的过程中,其实跟蒙特卡罗+策略迭代的方式是等价的,除了采样次数或增量迭代的次数之外。

  • 随机初始化Q价值函数
  • 循环 - 遍历每一个s,遍历每一个a- 以 s , a s,a s,a作为初始状态和动作,根据价值函数采样1条轨迹 ( a = a r g m a x a Q ( s , a ) ) \left( a=argmax_aQ(s,a)\right) (a=argmaxa​Q(s,a))- 只有增量形式: Q t + 1 ( s , a ) = Q t ( s , a ) + α ( G ( τ s 0 = s , a 0 = a ) − Q ^ t π ( s , a ) ) Q_{t+1}(s,a) = Q_t(s,a) + \alpha \left(G\left(\tau_{s_{0}=s, a_{0}=a}^{} \right)-\hat{Q}_{t}^{\pi}(s, a)\right) Qt+1​(s,a)=Qt​(s,a)+α(G(τs0​=s,a0​=a​)−Q^​tπ​(s,a))
  • 直到Q收敛

时序差分方法

前面我们用蒙特卡罗对策略迭代和值迭代做了初步的结合或改进以应对模型未知的情况,但是我们发现即便是采用值迭代的算法,每次迭代都至少需要SxA次采样,并且每次采样都是一条完整的轨迹。事实上我们会发现,策略迭代和值迭代都是利用一次状态转移进行训练的。所以说,蒙特卡罗与动态规划的结合的潜力还没有被挖掘完全。

根据增量迭代公式

          Q
         
         
          
           t
          
          
           +
          
          
           1
          
         
         
          π
         
        
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         )
        
       
      
     
     
      
       
        
        
         =
        
        
         
          Q
         
         
          t
         
         
          π
         
        
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         )
        
        
         +
        
        
         α
        
        
         
          (
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             
              s
             
             
              0
             
            
            
             =
            
            
             s
            
            
             ,
            
            
             
              a
             
             
              0
             
            
            
             =
            
            
             a
            
           
           
          
          
           )
          
         
         
          −
         
         
          
           Q
          
          
           t
          
          
           π
          
         
         
          (
         
         
          s
         
         
          ,
         
         
          a
         
         
          )
         
         
          )
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          Q
         
         
          t
         
         
          π
         
        
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         )
        
        
         +
        
        
         α
        
        
         
          (
         
         
          r
         
         
          +
         
         
          γ
         
         
          ∗
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             
              s
             
             
              0
             
            
            
             =
            
            
             s
            
            
             ,
            
            
             
              a
             
             
              0
             
            
            
             =
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              1
             
            
            
             =
            
            
             
              s
             
             
              ′
             
            
            
             ,
            
            
             
              a
             
             
              1
             
            
            
             =
            
            
             
              a
             
             
              ′
             
            
           
           
          
          
           )
          
         
         
          −
         
         
          
           Q
          
          
           t
          
          
           π
          
         
         
          (
         
         
          s
         
         
          ,
         
         
          a
         
         
          )
         
         
          )
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          Q
         
         
          t
         
         
          π
         
        
        
         (
        
        
         s
        
        
         ,
        
        
         a
        
        
         )
        
        
         +
        
        
         α
        
        
         
          (
         
         
          r
         
         
          +
         
         
          γ
         
         
          ∗
         
         
          
           Q
          
          
           t
          
          
           π
          
         
         
          (
         
         
          
           s
          
          
           ′
          
         
         
          ,
         
         
          
           a
          
          
           ′
          
         
         
          )
         
         
          −
         
         
          
           Q
          
          
           t
          
          
           π
          
         
         
          (
         
         
          s
         
         
          ,
         
         
          a
         
         
          )
         
         
          )
         
        
       
      
     
    
   
   
     \begin{aligned} Q_{t+1}^\pi(s,a) &= Q_t^\pi(s,a) + \alpha \left(G\left(\tau_{s_{0}=s, a_{0}=a}^{} \right)-{Q}_{t}^{\pi}(s, a)\right)\\ &=Q_t^\pi(s,a) + \alpha \left(r+\gamma*G\left(\tau_{s_{0}=s, a_{0}=a,s_1=s^\prime,a_1=a^\prime}^{} \right)-{Q}_{t}^{\pi}(s, a)\right) \\ &= Q_t^\pi(s,a)+\alpha \left(r+\gamma*Q_t^\pi(s^\prime,a^\prime)-{Q}_{t}^{\pi}(s, a)\right) \end{aligned} 
   
  
 Qt+1π​(s,a)​=Qtπ​(s,a)+α(G(τs0​=s,a0​=a​)−Qtπ​(s,a))=Qtπ​(s,a)+α(r+γ∗G(τs0​=s,a0​=a,s1​=s′,a1​=a′​)−Qtπ​(s,a))=Qtπ​(s,a)+α(r+γ∗Qtπ​(s′,a′)−Qtπ​(s,a))​

于是我们最终得到下面的迭代式

      Q
     
     
      
       t
      
      
       +
      
      
       1
      
     
     
      π
     
    
    
     (
    
    
     s
    
    
     ,
    
    
     a
    
    
     )
    
    
     =
    
    
     
      Q
     
     
      t
     
     
      π
     
    
    
     (
    
    
     s
    
    
     ,
    
    
     a
    
    
     )
    
    
     +
    
    
     α
    
    
     
      (
     
     
      r
     
     
      +
     
     
      γ
     
     
      ∗
     
     
      
       Q
      
      
       t
      
      
       π
      
     
     
      (
     
     
      
       s
      
      
       ′
      
     
     
      ,
     
     
      
       a
      
      
       ′
      
     
     
      )
     
     
      −
     
     
      
       Q
      
      
       t
      
      
       π
      
     
     
      (
     
     
      s
     
     
      ,
     
     
      a
     
     
      )
     
     
      )
     
    
   
   
     Q_{t+1}^\pi(s,a) = Q_t^\pi(s,a)+\alpha \left(r+\gamma*Q_t^\pi(s^\prime,a^\prime)-{Q}_{t}^{\pi}(s, a)\right) 
   
  
 Qt+1π​(s,a)=Qtπ​(s,a)+α(r+γ∗Qtπ​(s′,a′)−Qtπ​(s,a))

这个迭代式中

     Q
    
    
     
      t
     
     
      +
     
     
      1
     
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
  
  
   Q_{t+1}^\pi(s,a)
  
 
Qt+1π​(s,a)和

 
  
   
    
     Q
    
    
     t
    
    
     π
    
   
   
    (
   
   
    s
   
   
    ,
   
   
    a
   
   
    )
   
  
  
   Q_t^\pi(s,a)
  
 
Qtπ​(s,a)是迭代前后的价值函数的值,涉及的数据也是只包括一次状态转移的

 
  
   
    s
   
   
    ,
   
   
    a
   
   
    ,
   
   
    r
   
   
    ,
   
   
    
     s
    
    
     ′
    
   
   
    ,
   
   
    
     a
    
    
     ′
    
   
  
  
   s,a,r,s^\prime,a^\prime
  
 
s,a,r,s′,a′。然而,我们同时也能注意到,迭代式的右边的更新的部分除了Q(s,a)本身,还包括了

 
  
   
    Q
   
   
    (
   
   
    
     s
    
    
     ′
    
   
   
    ,
   
   
    
     a
    
    
     ′
    
   
   
    )
   
  
  
   Q(s^\prime,a^\prime)
  
 
Q(s′,a′),我们可以想到它的迭代是不稳定的,后面会有针对这部分的改进,这是后话了

这个式子也可以换个思路得到,根据Q函数的贝尔曼方程

            Q
           
           
            π
           
          
          
           (
          
          
           s
          
          
           ,
          
          
           a
          
          
           )
          
         
        
       
       
        
         
          
          
           =
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             Q
            
            
             π
            
           
           
            (
           
           
            
             s
            
            
             ′
            
           
           
            ,
           
           
            
             a
            
            
             ′
            
           
           
            )
           
           
            ]
           
          
          
           ,
          
          
           
            a
           
           
            ′
           
          
          
           =
          
          
           π
          
          
           (
          
          
           
            s
           
           
            ′
           
          
          
           )
          
         
        
       
      
     
    
   
   
     {\large \begin{aligned} Q^\pi(s,a) &= \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma Q^\pi(s^\prime,a^\prime)\right],a^\prime = \pi(s^\prime) \end{aligned}} 
   
  
 Qπ(s,a)​=Es′∼p(s′∣s,a)​[r(s,a,s′)+γQπ(s′,a′)],a′=π(s′)​

蒙特卡罗的方法本质上是经验分布近似期望,而跟具体的应用无关。我们完全可以用采样的方式近似在转移分布上的期望。

显然,我们需要采样的数据包括

    s
   
   
    ,
   
   
    a
   
   
    ,
   
   
    r
   
   
    ,
   
   
    
     s
    
    
     ′
    
   
  
  
   s,a,r,s^\prime
  
 
s,a,r,s′,我们把这样一组数据叫做一个Transition。于是

 
  
   
    
     
      
       
        
         
          
           
            Q
           
           
            π
           
          
          
           (
          
          
           s
          
          
           ,
          
          
           a
          
          
           )
          
         
        
       
       
        
         
          
          
           =
          
          
           
            1
           
           
            N
           
          
          
           
            ∑
           
           
            
             n
            
            
             =
            
            
             1
            
           
           
            N
           
          
          
           r
          
          
           
            (
           
           
            s
           
           
            ,
           
           
            a
           
           
            ,
           
           
            
             s
            
            
             ′
            
           
           
            )
           
          
          
           +
          
          
           γ
          
          
           
            Q
           
           
            π
           
          
          
           (
          
          
           
            s
           
           
            ′
           
          
          
           ,
          
          
           
            a
           
           
            ′
           
          
          
           )
          
         
        
       
      
      
       
        
         
        
       
       
        
         
          
          
           =
          
          
           
            Q
           
           
            π
           
          
          
           (
          
          
           s
          
          
           ,
          
          
           a
          
          
           )
          
          
           +
          
          
           
            1
           
           
            N
           
          
          
           (
          
          
           r
          
          
           
            (
           
           
            s
           
           
            ,
           
           
            a
           
           
            ,
           
           
            
             s
            
            
             ′
            
           
           
            )
           
          
          
           +
          
          
           γ
          
          
           
            Q
           
           
            π
           
          
          
           (
          
          
           
            s
           
           
            ′
           
          
          
           ,
          
          
           
            a
           
           
            ′
           
          
          
           )
          
          
           −
          
          
           
            Q
           
           
            π
           
          
          
           (
          
          
           s
          
          
           ,
          
          
           a
          
          
           )
          
          
           )
          
         
        
       
      
     
    
   
   
     {\large \begin{aligned} Q^\pi(s,a) &= \frac{1}{N}\sum_{n=1}^{N}r\left(s, a, s^{\prime}\right)+\gamma Q^\pi(s^\prime,a^\prime) \\ &= Q^\pi(s,a)+\frac{1}{N}(r\left(s, a, s^{\prime}\right)+\gamma Q^\pi(s^\prime,a^\prime)-Q^\pi(s,a)) \end{aligned}} 
   
  
 Qπ(s,a)​=N1​n=1∑N​r(s,a,s′)+γQπ(s′,a′)=Qπ(s,a)+N1​(r(s,a,s′)+γQπ(s′,a′)−Qπ(s,a))​

同样,将1/N用

    α
   
  
  
   \alpha
  
 
α替代后,

 
  
   
    
     
      
       
        Q
       
       
        
         t
        
        
         +
        
        
         1
        
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
      
       =
      
      
       
        Q
       
       
        t
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
      
       +
      
      
       α
      
      
       
        (
       
       
        r
       
       
        +
       
       
        γ
       
       
        ∗
       
       
        
         Q
        
        
         t
        
        
         π
        
       
       
        (
       
       
        
         s
        
        
         ′
        
       
       
        ,
       
       
        
         a
        
        
         ′
        
       
       
        )
       
       
        −
       
       
        
         Q
        
        
         t
        
        
         π
        
       
       
        (
       
       
        s
       
       
        ,
       
       
        a
       
       
        )
       
       
        )
       
      
     
    
   
   
     \large{Q_{t+1}^\pi(s,a) = Q_t^\pi(s,a)+\alpha \left(r+\gamma*Q_t^\pi(s^\prime,a^\prime)-{Q}_{t}^{\pi}(s, a)\right)} 
   
  
 Qt+1π​(s,a)=Qtπ​(s,a)+α(r+γ∗Qtπ​(s′,a′)−Qtπ​(s,a))

在得到上述迭代式后,我们可以重新考虑蒙特卡罗与策略迭代和值迭代结合的方式,从而衍生出两个新的算法:Sarsa和Q Learning

Sarsa

总体上,Sarsa = 蒙特卡罗+策略迭代+时序差分

细节上稍微有些区别

在这里插入图片描述

     (
    
    
     请
    
    
     暂
    
    
     时
    
    
     忽
    
    
     略
    
    
     掉
    
    
     算
    
    
     法
    
    
     中
    
    
     出
    
    
     现
    
    
     的
    
    
     ϵ
    
    
     )
    
   
   
     (请暂时忽略掉算法中出现的\epsilon) 
   
  
 (请暂时忽略掉算法中出现的ϵ)

第七行对应的就是策略评估的过程,但是只迭代了一次,这样一来,似乎如果值迭代也是正常改进的话,二者可能就完全相同了。

Q Learning

Q Learning = 蒙特卡罗+值迭代+时序差分

在应用了值迭代(最优策略)的思想后,迭代式修改如下

        Q
       
       
        
         t
        
        
         +
        
        
         1
        
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
      
       =
      
      
       
        Q
       
       
        t
       
       
        π
       
      
      
       (
      
      
       s
      
      
       ,
      
      
       a
      
      
       )
      
      
       +
      
      
       α
      
      
       
        (
       
       
        r
       
       
        +
       
       
        γ
       
       
        
         
          max
         
         
          ⁡
         
        
        
         
          a
         
         
          ′
         
        
       
       
        
         Q
        
        
         t
        
        
         π
        
       
       
        (
       
       
        
         s
        
        
         ′
        
       
       
        ,
       
       
        
         a
        
        
         ′
        
       
       
        )
       
       
        −
       
       
        
         Q
        
        
         t
        
        
         π
        
       
       
        (
       
       
        s
       
       
        ,
       
       
        a
       
       
        )
       
       
        )
       
      
     
    
   
   
     \large{Q_{t+1}^\pi(s,a) = Q_t^\pi(s,a)+\alpha \left(r+\gamma \max_{a^\prime}Q_t^\pi(s^\prime,a^\prime)-{Q}_{t}^{\pi}(s, a)\right)} 
   
  
 Qt+1π​(s,a)=Qtπ​(s,a)+α(r+γa′max​Qtπ​(s′,a′)−Qtπ​(s,a))

我简单解释一下为什么这么加一个max

值迭代中

            Q
           
           
            π
           
          
          
           (
          
          
           s
          
          
           ,
          
          
           a
          
          
           )
          
         
        
       
       
        
         
          
          
           =
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             V
            
            
             π
            
           
           
            (
           
           
            
             s
            
            
             ′
            
           
           
            )
           
           
            ]
           
          
         
        
       
      
      
       
        
         
        
       
       
        
         
          
          
           =
          
          
           
            E
           
           
            
             
              s
             
             
              ′
             
            
            
             ∼
            
            
             p
            
            
             
              (
             
             
              
               s
              
              
               ′
              
             
             
              ∣
             
             
              s
             
             
              ,
             
             
              a
             
             
              )
             
            
           
          
          
           
            [
           
           
            r
           
           
            
             (
            
            
             s
            
            
             ,
            
            
             a
            
            
             ,
            
            
             
              s
             
             
              ′
             
            
            
             )
            
           
           
            +
           
           
            γ
           
           
            
             
              max
             
             
              ⁡
             
            
            
             
              a
             
             
              ′
             
            
           
           
            
             Q
            
            
             π
            
           
           
            (
           
           
            
             s
            
            
             ′
            
           
           
            ,
           
           
            
             a
            
            
             ′
            
           
           
            )
           
           
            ]
           
          
         
        
       
      
     
    
   
   
     {\large \begin{aligned} Q^\pi(s,a) &= \mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma V^\pi(s^\prime)\right] \\ &=\mathbb{E}_{s^{\prime} \sim p\left(s^{\prime} \mid s, a\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma \max_{a^\prime} Q^\pi(s^\prime,a^\prime)\right] \end{aligned}} 
   
  
 Qπ(s,a)​=Es′∼p(s′∣s,a)​[r(s,a,s′)+γVπ(s′)]=Es′∼p(s′∣s,a)​[r(s,a,s′)+γa′max​Qπ(s′,a′)]​

这个式子应用蒙特卡罗方法推倒下去就会出现带max的结果

在这里插入图片描述

补充

    ϵ
   
  
  
   \epsilon
  
 
ϵ贪心法

我们现在来把之前留的

    ϵ
   
  
  
   \epsilon
  
 
ϵ的坑填一下。

我们前面介绍的算法通常是基于确定性策略的,如此,我们使用该策略进行采样时,可能没办法采样到更多可能的轨迹。对于策略迭代都还好,毕竟策略每一轮都在迭代,每次采样的轨迹很可能不同,但是对于值迭代来说,这就是致命的问题,因为值迭代的行为策略没有更新过,所以每次采样出来的轨迹有可能完全相同。

所以,为了增强对环境的探索能力,

    ϵ
   
  
  
   \epsilon
  
 
ϵ贪心法如下

在这里插入图片描述

这样一来,将行为策略转化为随机性策略,同时又不影响目标策略

同策略与异策略

我们前面介绍了SARSA算法和Q学习算法,有提到说SARSA是一种同策略的算法,而Q Learning是异策略的算法。那么同策略和异策略呢?

在强化学习的算法中,我们通常会涉及到两种策略,一种是行为策略,一种是目标策略。行为策略就是我们通过采样获得训练数据时使用的采样策略。而目标策略则是在用采样的数据进行训练的过程中所使用的策略。

所谓的同策略(On-Policy)即行为策略与目标策略一致,反之即为异策略(Off-Policy)

SARSA算法采样的时候是使用

     π
    
    
     ϵ
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   \pi^\epsilon(s)
  
 
πϵ(s)策略,而在训练过程中更新的也是该策略,所以SARSA是一个同策略算法。

Q Learning采样的时候使用

     π
    
    
     ϵ
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   \pi^\epsilon(s)
  
 
πϵ(s),而训练过程中从来没有更新过

 
  
   
    
     π
    
    
     ϵ
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   \pi^\epsilon(s)
  
 
πϵ(s),而是生成了临时的最优策略用于计算Q函数,所以Q Learning是异策略的算法

策略梯度

前面介绍的SARSA和Q Learning都是基于值函数的优化算法,我之前提到过,要求得策略,除了前面介绍的算法外,另一个是将

    π
   
  
  
   \pi
  
 
π参数化成

 
  
   
    
     π
    
    
     θ
    
   
   
    (
   
   
    a
   
   
    ∣
   
   
    s
   
   
    )
   
  
  
   \pi_\theta(a|s)
  
 
πθ​(a∣s),我们通过计算期望回报对

 
  
   
    θ
   
  
  
   \theta
  
 
θ的梯度从而使用梯度下降的算法优化

 
  
   
    θ
   
  
  
   \theta
  
 
θ,这种方法叫做策略梯度。

我们的目标函数是期望回报,那么

          ∂
         
         
          J
         
         
          (
         
         
          θ
         
         
          )
         
        
        
         
          ∂
         
         
          θ
         
        
       
      
     
     
      
       
        
        
         =
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         ∫
        
        
         
          p
         
         
          θ
         
        
        
         (
        
        
         τ
        
        
         )
        
        
         G
        
        
         (
        
        
         τ
        
        
         )
        
        
         d
        
        
         τ
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         ∫
        
        
         
          (
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          
           p
          
          
           θ
          
         
         
          (
         
         
          τ
         
         
          )
         
         
          )
         
        
        
         G
        
        
         (
        
        
         τ
        
        
         )
        
        
         d
        
        
         τ
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         ∫
        
        
         
          p
         
         
          θ
         
        
        
         (
        
        
         τ
        
        
         )
        
        
         
          (
         
         
          
           1
          
          
           
            
             p
            
            
             θ
            
           
           
            (
           
           
            τ
           
           
            )
           
          
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          
           p
          
          
           θ
          
         
         
          (
         
         
          τ
         
         
          )
         
         
          )
         
        
        
         G
        
        
         (
        
        
         τ
        
        
         )
        
        
         d
        
        
         τ
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         ∫
        
        
         
          p
         
         
          θ
         
        
        
         (
        
        
         τ
        
        
         )
        
        
         
          (
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           p
          
          
           θ
          
         
         
          (
         
         
          τ
         
         
          )
         
         
          )
         
        
        
         G
        
        
         (
        
        
         τ
        
        
         )
        
        
         d
        
        
         τ
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           τ
          
          
           ∼
          
          
           
            p
           
           
            θ
           
          
          
           (
          
          
           τ
          
          
           )
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           p
          
          
           θ
          
         
         
          (
         
         
          τ
         
         
          )
         
         
          G
         
         
          (
         
         
          τ
         
         
          )
         
         
          ]
         
        
        
         ,
        
       
      
     
    
   
   
     \begin{aligned} \frac{\partial \mathcal{J}(\theta)}{\partial \theta} &=\frac{\partial}{\partial \theta} \int p_{\theta}(\tau) G(\tau) \mathrm{d} \tau \\ &=\int\left(\frac{\partial}{\partial \theta} p_{\theta}(\tau)\right) G(\tau) \mathrm{d} \tau \\ &=\int p_{\theta}(\tau)\left(\frac{1}{p_{\theta}(\tau)} \frac{\partial}{\partial \theta} p_{\theta}(\tau)\right) G(\tau) \mathrm{d} \tau \\ &=\int p_{\theta}(\tau)\left(\frac{\partial}{\partial \theta} \log p_{\theta}(\tau)\right) G(\tau) \mathrm{d} \tau \\ &=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[\frac{\partial}{\partial \theta} \log p_{\theta}(\tau) G(\tau)\right], \end{aligned} 
   
  
 ∂θ∂J(θ)​​=∂θ∂​∫pθ​(τ)G(τ)dτ=∫(∂θ∂​pθ​(τ))G(τ)dτ=∫pθ​(τ)(pθ​(τ)1​∂θ∂​pθ​(τ))G(τ)dτ=∫pθ​(τ)(∂θ∂​logpθ​(τ))G(τ)dτ=Eτ∼pθ​(τ)​[∂θ∂​logpθ​(τ)G(τ)],​

 
  
   
    
     
      
       
        
         ∂
        
        
         
          ∂
         
         
          θ
         
        
       
      
     
     
      
       
        
        
         log
        
        
         ⁡
        
        
         
          p
         
         
          θ
         
        
        
         (
        
        
         τ
        
        
         )
        
        
         =
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         log
        
        
         ⁡
        
        
         
          (
         
         
          p
         
         
          
           (
          
          
           
            s
           
           
            0
           
          
          
           )
          
         
         
          
           ∏
          
          
           
            t
           
           
            =
           
           
            0
           
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          p
         
         
          
           (
          
          
           
            s
           
           
            
             t
            
            
             +
            
            
             1
            
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           ,
          
          
           
            a
           
           
            t
           
          
          
           )
          
         
         
          )
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         
          (
         
         
          log
         
         
          ⁡
         
         
          p
         
         
          
           (
          
          
           
            s
           
           
            0
           
          
          
           )
          
         
         
          +
         
         
          
           ∑
          
          
           
            t
           
           
            =
           
           
            0
           
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          +
         
         
          
           ∑
          
          
           
            t
           
           
            =
           
           
            0
           
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          log
         
         
          ⁡
         
         
          p
         
         
          
           (
          
          
           
            s
           
           
            
             t
            
            
             +
            
            
             1
            
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           ,
          
          
           
            a
           
           
            t
           
          
          
           )
          
         
         
          )
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          ∑
         
         
          
           t
          
          
           =
          
          
           0
          
         
         
          
           T
          
          
           −
          
          
           1
          
         
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         log
        
        
         ⁡
        
        
         
          π
         
         
          θ
         
        
        
         
          (
         
         
          
           a
          
          
           t
          
         
         
          ∣
         
         
          
           s
          
          
           t
          
         
         
          )
         
        
       
      
     
    
   
   
     \begin{aligned} \frac{\partial}{\partial \theta} & \log p_{\theta}(\tau)=\frac{\partial}{\partial \theta} \log \left(p\left(s_{0}\right) \prod_{t=0}^{T-1} \pi_{\theta}\left(a_{t} \mid s_{t}\right) p\left(s_{t+1} \mid s_{t}, a_{t}\right)\right) \\ &=\frac{\partial}{\partial \theta}\left(\log p\left(s_{0}\right)+\sum_{t=0}^{T-1} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right)+\sum_{t=0}^{T-1} \log p\left(s_{t+1} \mid s_{t}, a_{t}\right)\right) \\ &=\sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \end{aligned} 
   
  
 ∂θ∂​​logpθ​(τ)=∂θ∂​log(p(s0​)t=0∏T−1​πθ​(at​∣st​)p(st+1​∣st​,at​))=∂θ∂​(logp(s0​)+t=0∑T−1​logπθ​(at​∣st​)+t=0∑T−1​logp(st+1​∣st​,at​))=t=0∑T−1​∂θ∂​logπθ​(at​∣st​)​

 
  
   
    
     
      
       
        
         
          ∂
         
         
          J
         
         
          (
         
         
          θ
         
         
          )
         
        
        
         
          ∂
         
         
          θ
         
        
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           τ
          
          
           ∼
          
          
           
            p
           
           
            θ
           
          
          
           (
          
          
           τ
          
          
           )
          
         
        
        
         
          [
         
         
          
           (
          
          
           
            ∑
           
           
            
             t
            
            
             =
            
            
             0
            
           
           
            
             T
            
            
             −
            
            
             1
            
           
          
          
           
            ∂
           
           
            
             ∂
            
            
             θ
            
           
          
          
           log
          
          
           ⁡
          
          
           
            π
           
           
            θ
           
          
          
           
            (
           
           
            
             a
            
            
             t
            
           
           
            ∣
           
           
            
             s
            
            
             t
            
           
           
            )
           
          
          
           )
          
         
         
          G
         
         
          (
         
         
          τ
         
         
          )
         
         
          ]
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           τ
          
          
           ∼
          
          
           
            p
           
           
            θ
           
          
          
           (
          
          
           τ
          
          
           )
          
         
        
        
         
          [
         
         
          
           (
          
          
           
            ∑
           
           
            
             t
            
            
             =
            
            
             0
            
           
           
            
             T
            
            
             −
            
            
             1
            
           
          
          
           
            ∂
           
           
            
             ∂
            
            
             θ
            
           
          
          
           log
          
          
           ⁡
          
          
           
            π
           
           
            θ
           
          
          
           
            (
           
           
            
             a
            
            
             t
            
           
           
            ∣
           
           
            
             s
            
            
             t
            
           
           
            )
           
          
          
           )
          
         
         
          
           (
          
          
           G
          
          
           
            (
           
           
            
             τ
            
            
             
              0
             
             
              :
             
             
              t
             
            
           
           
            )
           
          
          
           +
          
          
           
            γ
           
           
            t
           
          
          
           G
          
          
           
            (
           
           
            
             τ
            
            
             
              t
             
             
              :
             
             
              T
             
            
           
           
            )
           
          
          
           )
          
         
         
          ]
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           τ
          
          
           ∼
          
          
           
            p
           
           
            θ
           
          
          
           (
          
          
           τ
          
          
           )
          
         
        
        
         
          [
         
         
          
           ∑
          
          
           
            t
           
           
            =
           
           
            0
           
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          
           (
          
          
           
            ∂
           
           
            
             ∂
            
            
             θ
            
           
          
          
           log
          
          
           ⁡
          
          
           
            π
           
           
            θ
           
          
          
           
            (
           
           
            
             a
            
            
             t
            
           
           
            ∣
           
           
            
             s
            
            
             t
            
           
           
            )
           
          
          
           
            γ
           
           
            t
           
          
          
           G
          
          
           
            (
           
           
            
             τ
            
            
             
              t
             
             
              :
             
             
              T
             
            
           
           
            )
           
          
          
           )
          
         
         
          ]
         
        
       
      
     
    
   
   
     \begin{aligned} \frac{\partial \mathcal{J}(\theta)}{\partial \theta} &=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[\left(\sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right)\right) G(\tau)\right] \\ &=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[\left(\sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right)\right)\left(G\left(\tau_{0: t}\right)+\gamma^{t} G\left(\tau_{t: T}\right)\right)\right] \\ &=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t=0}^{T-1}\left(\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} G\left(\tau_{t: T}\right)\right)\right] \end{aligned} 
   
  
 ∂θ∂J(θ)​​=Eτ∼pθ​(τ)​[(t=0∑T−1​∂θ∂​logπθ​(at​∣st​))G(τ)]=Eτ∼pθ​(τ)​[(t=0∑T−1​∂θ∂​logπθ​(at​∣st​))(G(τ0:t​)+γtG(τt:T​))]=Eτ∼pθ​(τ)​[t=0∑T−1​(∂θ∂​logπθ​(at​∣st​)γtG(τt:T​))]​

公式(28)中从第二步到第三步省略了一个极其复杂的过程

证明过程参考链接(待添加)

最后,我们显然也是无法直接计算期望的,所以也可以采用蒙特卡罗法进行近似。

       ∂
      
      
       J
      
      
       (
      
      
       θ
      
      
       )
      
     
     
      
       ∂
      
      
       θ
      
     
    
    
     ≈
    
    
     
      1
     
     
      N
     
    
    
     
      ∑
     
     
      
       n
      
      
       =
      
      
       1
      
     
     
      N
     
    
    
     
      (
     
     
      
       ∑
      
      
       
        t
       
       
        =
       
       
        0
       
      
      
       
        T
       
       
        −
       
       
        1
       
      
     
     
      
       ∂
      
      
       
        ∂
       
       
        θ
       
      
     
     
      log
     
     
      ⁡
     
     
      
       π
      
      
       θ
      
     
     
      
       (
      
      
       
        a
       
       
        t
       
       
        
         (
        
        
         n
        
        
         )
        
       
      
      
       ∣
      
      
       
        s
       
       
        t
       
       
        
         (
        
        
         n
        
        
         )
        
       
      
      
       )
      
     
     
      
       γ
      
      
       t
      
     
     
      
       G
      
      
       
        τ
       
       
        
         t
        
        
         :
        
        
         T
        
       
       
        
         (
        
        
         n
        
        
         )
        
       
      
     
     
      )
     
    
   
   
     \frac{\partial \mathcal{J}(\theta)}{\partial \theta} \approx \frac{1}{N} \sum_{n=1}^{N}\left(\sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t}^{(n)} \mid s_{t}^{(n)}\right) \gamma^{t} G_{\tau_{t: T}^{(n)}}\right) 
   
  
 ∂θ∂J(θ)​≈N1​n=1∑N​(t=0∑T−1​∂θ∂​logπθ​(at(n)​∣st(n)​)γtGτt:T(n)​​)

Reinforce

结合随机梯度算法,将上式转化为增量形式即为Reinforce算法

在这里插入图片描述

Reinforce With Baseline

Reinforce有一个缺点是不同路径之间的方差很大,导致训练不稳定,这是在高维空间使用蒙特卡罗方法的通病。注意,这里明确了是高维空间,之前介绍的Sarsa和Q Learning也用了蒙特卡罗算法,但是他们只是对一个transition采样,所以问题不大,但是Reinforce是对整个轨迹采样,那么采样空间的维度就变得太高了,所以才会出现稳定性差的问题。

那么如何解决呢?

其实很简单,如下

     Δ
    
    
     
      
       ∂
      
      
       J
      
      
       (
      
      
       θ
      
      
       )
      
     
     
      
       ∂
      
      
       θ
      
     
    
    
     ≈
    
    
     
      ∑
     
     
      
       t
      
      
       =
      
      
       0
      
     
     
      
       T
      
      
       −
      
      
       1
      
     
    
    
     
      ∂
     
     
      
       ∂
      
      
       θ
      
     
    
    
     log
    
    
     ⁡
    
    
     
      π
     
     
      θ
     
    
    
     
      (
     
     
      
       a
      
      
       t
      
      
       
        (
       
       
        n
       
       
        )
       
      
     
     
      ∣
     
     
      
       s
      
      
       t
      
      
       
        (
       
       
        n
       
       
        )
       
      
     
     
      )
     
    
    
     
      γ
     
     
      t
     
    
    
     
      (
     
     
      
       G
      
      
       
        τ
       
       
        
         t
        
        
         :
        
        
         T
        
       
       
        
         (
        
        
         n
        
        
         )
        
       
      
     
     
      −
     
     
      
       V
      
      
       ϕ
      
     
     
      (
     
     
      
       s
      
      
       t
      
     
     
      )
     
     
      )
     
    
   
   
     \Delta\frac{\partial \mathcal{J}(\theta)}{\partial \theta} \approx \sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t}^{(n)} \mid s_{t}^{(n)}\right) \gamma^{t} \left(G_{\tau_{t: T}^{(n)}}-V_\phi(s_t)\right) 
   
  
 Δ∂θ∂J(θ)​≈t=0∑T−1​∂θ∂​logπθ​(at(n)​∣st(n)​)γt(Gτt:T(n)​​−Vϕ​(st​))

我们注意到,上式与Reinforce的差别仅仅是对G减去了一个V(st),但是它的可行性和有效性的数学证明却不是一目了然的。

我们可以证明,任意引入一个与at无关的b(st),不改变期望形式的策略梯度。

首先,

          ∂
         
         
          J
         
         
          (
         
         
          θ
         
         
          )
         
        
        
         
          ∂
         
         
          θ
         
        
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           τ
          
          
           ∼
          
          
           
            p
           
           
            θ
           
          
          
           (
          
          
           τ
          
          
           )
          
         
        
        
         
          [
         
         
          
           ∑
          
          
           
            t
           
           
            =
           
           
            0
           
          
          
           
            T
           
           
            −
           
           
            1
           
          
         
         
          
           (
          
          
           
            ∂
           
           
            
             ∂
            
            
             θ
            
           
          
          
           log
          
          
           ⁡
          
          
           
            π
           
           
            θ
           
          
          
           
            (
           
           
            
             a
            
            
             t
            
           
           
            ∣
           
           
            
             s
            
            
             t
            
           
           
            )
           
          
          
           
            γ
           
           
            t
           
          
          
           G
          
          
           
            (
           
           
            
             τ
            
            
             
              t
             
             
              :
             
             
              T
             
            
           
           
            )
           
          
          
           )
          
         
         
          ]
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          ∑
         
         
          
           t
          
          
           =
          
          
           0
          
         
         
          
           T
          
          
           −
          
          
           1
          
         
        
        
         
          E
         
         
          
           τ
          
          
           ∼
          
          
           
            p
           
           
            θ
           
          
          
           (
          
          
           τ
          
          
           )
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             t
            
            
             :
            
            
             T
            
           
          
          
           )
          
         
         
          ]
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          ∑
         
         
          
           t
          
          
           =
          
          
           0
          
         
         
          
           T
          
          
           −
          
          
           1
          
         
        
        
         
          E
         
         
          
           s
          
          
           t
          
         
        
        
         
          E
         
         
          
           a
          
          
           t
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             t
            
            
             :
            
            
             T
            
           
          
          
           )
          
         
         
          ]
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          ∑
         
         
          
           t
          
          
           =
          
          
           0
          
         
         
          
           T
          
          
           −
          
          
           1
          
         
        
        
         
          
           ∂
          
          
           
            J
           
           
            t
           
          
          
           (
          
          
           θ
          
          
           )
          
         
         
          
           ∂
          
          
           θ
          
         
        
       
      
     
    
   
   
     \begin{aligned} \frac{\partial \mathcal{J}(\theta)}{\partial \theta} &=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t=0}^{T-1}\left(\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} G\left(\tau_{t: T}\right)\right)\right] \\ &=\sum_{t=0}^{T-1}\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} G\left(\tau_{t: T}\right)\right] \\ &=\sum_{t=0}^{T-1}\mathbb{E}_{s_t}\mathbb{E}_{a_t}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} G\left(\tau_{t: T}\right)\right] \\ &=\sum_{t=0}^{T-1}\frac{\partial \mathcal{J}_{t}(\theta)}{\partial \theta} \end{aligned} 
   
  
 ∂θ∂J(θ)​​=Eτ∼pθ​(τ)​[t=0∑T−1​(∂θ∂​logπθ​(at​∣st​)γtG(τt:T​))]=t=0∑T−1​Eτ∼pθ​(τ)​[∂θ∂​logπθ​(at​∣st​)γtG(τt:T​)]=t=0∑T−1​Est​​Eat​​[∂θ∂​logπθ​(at​∣st​)γtG(τt:T​)]=t=0∑T−1​∂θ∂Jt​(θ)​​

其次,引入b(st)后,

          ∂
         
         
          
           J
          
          
           t
          
         
         
          (
         
         
          θ
         
         
          )
         
        
        
         
          ∂
         
         
          θ
         
        
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           s
          
          
           t
          
         
        
        
         
          E
         
         
          
           a
          
          
           t
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          
           (
          
          
           G
          
          
           
            (
           
           
            
             τ
            
            
             
              t
             
             
              :
             
             
              T
             
            
           
           
            )
           
          
          
           −
          
          
           b
          
          
           (
          
          
           
            s
           
           
            t
           
          
          
           )
          
          
           )
          
         
         
          ]
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           s
          
          
           t
          
         
        
        
         
          E
         
         
          
           a
          
          
           t
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             t
            
            
             :
            
            
             T
            
           
          
          
           )
          
         
         
          ]
         
        
        
         +
        
        
         
          E
         
         
          
           s
          
          
           t
          
         
        
        
         
          E
         
         
          
           a
          
          
           t
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          b
         
         
          (
         
         
          
           s
          
          
           t
          
         
         
          )
         
         
          ]
         
        
       
      
     
    
   
   
     \begin{aligned} \frac{\partial \mathcal{J}_{t}(\theta)}{\partial \theta} &=\mathbb{E}_{s_t}\mathbb{E}_{a_t}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} \left(G\left(\tau_{t: T}\right)-b(s_t)\right)\right] \\ &=\mathbb{E}_{s_t}\mathbb{E}_{a_t}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} G\left(\tau_{t: T}\right)\right]+\mathbb{E}_{s_t}\mathbb{E}_{a_t}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} b(s_t)\right] \end{aligned} 
   
  
 ∂θ∂Jt​(θ)​​=Est​​Eat​​[∂θ∂​logπθ​(at​∣st​)γt(G(τt:T​)−b(st​))]=Est​​Eat​​[∂θ∂​logπθ​(at​∣st​)γtG(τt:T​)]+Est​​Eat​​[∂θ∂​logπθ​(at​∣st​)γtb(st​)]​

其中,

          E
         
         
          
           a
          
          
           t
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          b
         
         
          (
         
         
          
           s
          
          
           t
          
         
         
          )
         
         
          ]
         
        
       
      
     
     
      
       
        
        
         =
        
        
         b
        
        
         (
        
        
         
          s
         
         
          t
         
        
        
         )
        
        
         ∫
        
        
         
          π
         
         
          θ
         
        
        
         (
        
        
         
          a
         
         
          t
         
        
        
         ∣
        
        
         
          s
         
         
          t
         
        
        
         )
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         log
        
        
         ⁡
        
        
         
          π
         
         
          θ
         
        
        
         
          (
         
         
          
           a
          
          
           t
          
         
         
          ∣
         
         
          
           s
          
          
           t
          
         
         
          )
         
        
        
         d
        
        
         
          a
         
         
          t
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         b
        
        
         (
        
        
         
          s
         
         
          t
         
        
        
         )
        
        
         ∫
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         
          π
         
         
          θ
         
        
        
         
          (
         
         
          
           a
          
          
           t
          
         
         
          ∣
         
         
          
           s
          
          
           t
          
         
         
          )
         
        
        
         d
        
        
         
          a
         
         
          t
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         b
        
        
         (
        
        
         
          s
         
         
          t
         
        
        
         )
        
        
         ∫
        
        
         
          π
         
         
          θ
         
        
        
         
          (
         
         
          
           a
          
          
           t
          
         
         
          ∣
         
         
          
           s
          
          
           t
          
         
         
          )
         
        
        
         d
        
        
         
          a
         
         
          t
         
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          ∂
         
         
          
           ∂
          
          
           θ
          
         
        
        
         
          (
         
         
          b
         
         
          (
         
         
          
           s
          
          
           t
          
         
         
          )
         
         
          ∗
         
         
          1
         
         
          )
         
        
        
         =
        
        
         0
        
       
      
     
    
   
   
     \begin{aligned} \mathbb{E}_{a_t}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} b(s_t)\right] &= b(s_t)\int\pi_\theta(a_t \mid s_t)\frac{\partial}{\partial \theta}\log \pi_{\theta}\left(a_{t} \mid s_{t}\right)da_t \\ &=b(s_t)\int\frac{\partial}{\partial \theta}\pi_{\theta}\left(a_{t} \mid s_{t}\right)da_t \\ &=\frac{\partial}{\partial \theta}b(s_t)\int\pi_{\theta}\left(a_{t} \mid s_{t}\right)da_t \\ &= \frac{\partial}{\partial \theta}\left(b(s_t)* 1\right) =0 \end{aligned} 
   
  
 Eat​​[∂θ∂​logπθ​(at​∣st​)γtb(st​)]​=b(st​)∫πθ​(at​∣st​)∂θ∂​logπθ​(at​∣st​)dat​=b(st​)∫∂θ∂​πθ​(at​∣st​)dat​=∂θ∂​b(st​)∫πθ​(at​∣st​)dat​=∂θ∂​(b(st​)∗1)=0​

因此

          ∂
         
         
          
           J
          
          
           t
          
         
         
          (
         
         
          θ
         
         
          )
         
        
        
         
          ∂
         
         
          θ
         
        
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           s
          
          
           t
          
         
        
        
         
          E
         
         
          
           a
          
          
           t
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             t
            
            
             :
            
            
             T
            
           
          
          
           )
          
         
         
          ]
         
        
        
         +
        
        
         0
        
       
      
     
    
    
     
      
       
      
     
     
      
       
        
        
         =
        
        
         
          E
         
         
          
           s
          
          
           t
          
         
        
        
         
          E
         
         
          
           a
          
          
           t
          
         
        
        
         
          [
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          G
         
         
          
           (
          
          
           
            τ
           
           
            
             t
            
            
             :
            
            
             T
            
           
          
          
           )
          
         
         
          ]
         
        
       
      
     
    
   
   
     \begin{aligned} \frac{\partial \mathcal{J}_{t}(\theta)}{\partial \theta} &=\mathbb{E}_{s_t}\mathbb{E}_{a_t}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} G\left(\tau_{t: T}\right)\right]+0 \\ &=\mathbb{E}_{s_t}\mathbb{E}_{a_t}\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} G\left(\tau_{t: T}\right)\right] \end{aligned} 
   
  
 ∂θ∂Jt​(θ)​​=Est​​Eat​​[∂θ∂​logπθ​(at​∣st​)γtG(τt:T​)]+0=Est​​Eat​​[∂θ∂​logπθ​(at​∣st​)γtG(τt:T​)]​

证到这里答案已经呼之欲出了,在此省略之后的内容。

另外,我们虽然确实保证了期望形式的策略梯度保持不变,但我们实际训练时用的是蒙特卡罗方法近似的,所以增加baseline前后的策略梯度肯定还是会有一点差别的。

另外,关于减小方差的证明

         V
        
        
         a
        
        
         r
        
        
         
          (
         
         
          
           ∂
          
          
           
            ∂
           
           
            θ
           
          
         
         
          log
         
         
          ⁡
         
         
          
           π
          
          
           θ
          
         
         
          
           (
          
          
           
            a
           
           
            t
           
          
          
           ∣
          
          
           
            s
           
           
            t
           
          
          
           )
          
         
         
          
           γ
          
          
           t
          
         
         
          
           (
          
          
           G
          
          
           
            (
           
           
            
             τ
            
            
             
              t
             
             
              :
             
             
              T
             
            
           
           
            )
           
          
          
           −
          
          
           b
          
          
           (
          
          
           
            s
           
           
            t
           
          
          
           )
          
          
           )
          
         
         
          )
         
        
        
         =
        
        
         E
        
        
         
          
           [
          
          
           
            ∂
           
           
            
             ∂
            
            
             θ
            
           
          
          
           log
          
          
           ⁡
          
          
           
            π
           
           
            θ
           
          
          
           
            (
           
           
            
             a
            
            
             t
            
           
           
            ∣
           
           
            
             s
            
            
             t
            
           
           
            )
           
          
          
           
            γ
           
           
            t
           
          
          
           
            (
           
           
            G
           
           
            
             (
            
            
             
              τ
             
             
              
               t
              
              
               :
              
              
               T
              
             
            
            
             )
            
           
           
            −
           
           
            b
           
           
            (
           
           
            
             s
            
            
             t
            
           
           
            )
           
           
            )
           
          
          
           ]
          
         
         
          2
         
        
        
         −
        
       
      
     
    
    
     
      
       
        
         
          (
         
         
          E
         
         
          
           [
          
          
           
            ∂
           
           
            
             ∂
            
            
             θ
            
           
          
          
           log
          
          
           ⁡
          
          
           
            π
           
           
            θ
           
          
          
           
            (
           
           
            
             a
            
            
             t
            
           
           
            ∣
           
           
            
             s
            
            
             t
            
           
           
            )
           
          
          
           
            γ
           
           
            t
           
          
          
           
            (
           
           
            G
           
           
            
             (
            
            
             
              τ
             
             
              
               t
              
              
               :
              
              
               T
              
             
            
            
             )
            
           
           
            −
           
           
            b
           
           
            (
           
           
            
             s
            
            
             t
            
           
           
            )
           
           
            )
           
          
          
           ]
          
         
         
          )
         
        
        
         2
        
       
      
     
    
   
   
     \begin{aligned} Var\left(\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} \left(G\left(\tau_{t: T}\right)-b(s_t)\right)\right) = E\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} \left(G\left(\tau_{t: T}\right)-b(s_t)\right)\right]^2 -\\ \left(E\left[\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t} \left(G\left(\tau_{t: T}\right)-b(s_t)\right)\right]\right)^2 \\ \end{aligned} 
   
  
 Var(∂θ∂​logπθ​(at​∣st​)γt(G(τt:T​)−b(st​)))=E[∂θ∂​logπθ​(at​∣st​)γt(G(τt:T​)−b(st​))]2−(E[∂θ∂​logπθ​(at​∣st​)γt(G(τt:T​)−b(st​))])2​

后一部分前面已经证明过与b(st)无关,所以我们只考虑前半部分

         E
        
        
         
          [
         
         
          
           
            (
           
           
            
             ∂
            
            
             
              ∂
             
             
              θ
             
            
           
           
            log
           
           
            ⁡
           
           
            
             π
            
            
             θ
            
           
           
            
             (
            
            
             
              a
             
             
              t
             
            
            
             ∣
            
            
             
              s
             
             
              t
             
            
            
             )
            
           
           
            
             γ
            
            
             t
            
           
           
            )
           
          
          
           2
          
         
         
          
           
            (
           
           
            G
           
           
            
             (
            
            
             
              τ
             
             
              
               t
              
              
               :
              
              
               T
              
             
            
            
             )
            
           
           
            −
           
           
            b
           
           
            (
           
           
            
             s
            
            
             t
            
           
           
            )
           
           
            )
           
          
          
           2
          
         
         
          ]
         
        
        
         
          <
         
         
          ?
         
        
        
         E
        
        
         
          [
         
         
          
           
            (
           
           
            
             ∂
            
            
             
              ∂
             
             
              θ
             
            
           
           
            log
           
           
            ⁡
           
           
            
             π
            
            
             θ
            
           
           
            
             (
            
            
             
              a
             
             
              t
             
            
            
             ∣
            
            
             
              s
             
             
              t
             
            
            
             )
            
           
           
            
             γ
            
            
             t
            
           
           
            )
           
          
          
           2
          
         
         
          G
         
         
          
           
            (
           
           
            
             τ
            
            
             
              t
             
             
              :
             
             
              T
             
            
           
           
            )
           
          
          
           2
          
         
         
          ]
         
        
       
      
     
    
   
   
     \begin{aligned} E\left[\left(\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t}\right)^2 \left(G\left(\tau_{t: T}\right)-b(s_t)\right)^2\right] <_? E\left[\left(\frac{\partial}{\partial \theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \gamma^{t}\right)^2 G\left(\tau_{t: T}\right)^2\right] \end{aligned} 
   
  
 E[(∂θ∂​logπθ​(at​∣st​)γt)2(G(τt:T​)−b(st​))2]<?​E[(∂θ∂​logπθ​(at​∣st​)γt)2G(τt:T​)2]​

显然,只有当

      (
     
     
      G
     
     
      
       (
      
      
       
        τ
       
       
        
         t
        
        
         :
        
        
         T
        
       
      
      
       )
      
     
     
      −
     
     
      b
     
     
      (
     
     
      
       s
      
      
       t
      
     
     
      )
     
     
      )
     
    
    
     2
    
   
   
    <
   
   
    G
   
   
    
     
      (
     
     
      
       τ
      
      
       
        t
       
       
        :
       
       
        T
       
      
     
     
      )
     
    
    
     2
    
   
  
  
   \left(G\left(\tau_{t: T}\right)-b(s_t)\right)^2<G\left(\tau_{t: T}\right)^2
  
 
(G(τt:T​)−b(st​))2<G(τt:T​)2时才能减小方差,所以b(st)并不是随便去的,我们需要让b(st)尽可能地与G接近。因此实际中采用的就是

 
  
   
    
     V
    
    
     π
    
   
   
    (
   
   
    
     s
    
    
     t
    
   
   
    )
   
  
  
   V^\pi(s_t)
  
 
Vπ(st​),即相当于Gt的期望,所以自然会比较接近Gt。

但是现在又有一个问题,未来我们的期望回报就是用蒙特卡罗近似的,显然又引入一个期望,我们又怎么办呢?再用一次蒙特卡罗吗?显然不可能,因为这样就无限套娃了

事实上我们是用一组新的参数

    ϕ
   
  
  
   \phi
  
 
ϕ估计

 
  
   
    
     V
    
    
     π
    
   
   
    (
   
   
    s
   
   
    )
   
  
  
   V^\pi(s)
  
 
Vπ(s),在训练过程中除了优化策略函数的参数

 
  
   
    θ
   
  
  
   \theta
  
 
θ,也同时优化

 
  
   
    ϕ
   
  
  
   \phi
  
 
ϕ。

于是,最终的Reinforce With Baseline如下

在这里插入图片描述

大家看到对

    θ
   
  
  
   \theta
  
 
θ和

 
  
   
    ϕ
   
  
  
   \phi
  
 
ϕ不同的梯度更新千万不要怵,其实目标函数是一样的,只不过对不同参数求导得到不同结果而已。

本文转载自: https://blog.csdn.net/qq_41335232/article/details/125682485
版权归原作者 孤独腹地 所有, 如有侵权,请联系我们删除。

“强化学习入门笔记”的评论:

还没有评论