深度强化学习：章节5—Q-learning & DQN & DDPG

NoiseFloor

1. Q-learning

Q-learning 是一个基于值的强化学习算法，利用 Q 函数寻找最优的「动作—选择」策略；它根据动作值函数评估应该选择哪个动作，这个函数决定了处于某一个特定状态以及在该状态下采取特定动作的奖励期望值[1]。

核心的目的是什么？
最大化 Q 函数的值（给定一个状态和动作时的未来奖励期望）。

对于q值的理解，Q-learning中q值是存储在q-table中的，q值表示的是（状态，动作）对的值，通俗说就是在当前状态下采取动作能带来的价值，而Q-learning的目的就是不断去更新q表，之前看到一句话说的很好，Q值是可以“一眼看穿未来”。
q-learning训练步骤：

• 初始化Q-table
  
• 按照指定策略选择action a, 并执行
  
• 计算reward收益
  
• 更新Q-table
  

Q-table的训练最后，能够获得最优Q-table



newQ值更新

即下列式子：
newQ_{S,A}=(1-\alpha) Q_{S,A} + \alpha (R_{S,A} + \gamma \ast maxQ^{'}(s^{'}, a^{'}))  \\ ；
其中 (1-\alpha) Q_{S,A} 是旧Q值在 newQ_{S,A} 之中所占的比重； \alpha (R_{S,A} + \gamma \ast maxQ^{'}(s^{'}, a^{'}))  为本次行动学习到的奖励（行动本身带来的奖励和未来潜在的奖励）
2. DQN (Deep Q Network)

使用Q-table来存储每一个状态 state, 和在这个 state 每个行为 action 所拥有的 Q 值. 而当今问题过于太复杂时, 状态可以多到比天上的星星还多(比如下围棋). 如果全用表格来存储它们, 恐怕我们的计算机有再大的内存都不够, 而且每次在这么大的表格中搜索对应的状态也是一件很耗时的事。这些是Q-learning 所面对的问题难点。

DQN能解决这一难题吗？

DQN将状态和动作当成神经网络的输入, 然后经过神经网络分析后得到动作的 Q 值, 这样我们就没必要在表格中记录 Q 值, 而是直接使用神经网络生成 Q 值；还有一种形式，只输入状态值, 输出所有的动作值, 然后按照 Q learning 的原则, 直接选择拥有最大值的动作当做下一步要做的动作。



DQN模型

左边的模型[2]把一个状态和一个可能的动作作为输入，得到相应的Q值。这个模型的问题是，如果我们现在想要使用我们的策略，为了得到最优的Q值，我们必须循环的输入对应的状态和所有可能的行动，然后找到最大的Q值。这显然是不合理且费时的。
为了解决该问题，我们介绍右边的模型，现在我们只输入状态，DQN将会计算所有可能行动的Q值，这意味着，如果我们想在给定状态下采取行动，我们只需将状态反馈给网络，它就会返回所有的Q值。
这两个情况都可以根据下方的Q-loss来更新网络的参数。
2.1 DQN2013版

DQN的算法步骤：参照2013DQN[3]

• 首先初始化Memory D，它的容量为N;
  
• 初始化Q网络，随机生成权重ω;
  
• 循环遍历episode =1, 2, …, M:
  
  
  
  • 初始化initial state S1;
    
  • 循环遍历step =1,2,…, T:
    
    
    
    • 1) 用 \epsilon - greedy 策略生成action a_t ；
      
    • 2) 执行action a_t ，接受reward r_t 及新的state S_{t+1} ；
      
    • 3) 将transition样本（ S_t, a_t, r_t, S_{t+1} ）存入D中；
      
    • 4) 令 y_j=r_j ，如果j+1步是terminal的话，否则，令 y_j = r_j + \gamma * max Q(S_{t+1}, a)
      
    • 5) 对 (y_j- Q(S_t, a_j, w)) ^ 2 关于 w 使用梯度下降法进行更新，根据方程式3
      
    
    
  • end for
    
  
  
• end for
  

原论文中方程式3

与Q-learning 对比，关键点在于创建了记忆库Memory D。实际项目中，我们会先让记忆库积累到一定的数量，才会开始抽取样本，训练神经网络，梯度下降去优化。

代码中 Replay Buffer使用过程：

• 收集样本：按照时间先后顺序存入结构中，如果Replay Buffer已经存满样本，那么新的样本会将时间上最久远的样本覆盖；
  
• 采样样本：一般来说，Replay Buffer会从缓存中均匀地随机采样一批样本进行学习。
  

DQN2013版流程图表示如下：



2013版DQN流程图

样本中只有 (S_i, a, r, S_{I+1}) ,时序差分公式必要的 maxQ(s^{'}, a^{'}) 怎么得来？抽取训练样本后，用神经网络处理样本，得到 maxQ(s^{'}, a^{'})
2.2 DQN2015版

对比一下2015年DQN作了哪些改进呢？

• 首先初始化Memory D, 它的容量为N；
  
• 初始化Q网络，随机生成权重 w ;
  
• 初始化target Q网络，权重为 w^{-}=w ;
  
• 循环便利 episode=1,2,...,M:
  
  
  
  • 初始化initial state S1；
    
  • 循环遍历step=1,2,..., T:
    
    
    
    • 1）用 \epsilon - greedy 策略生成action  a_t
      
    • 2）执行action a_t, 接受reward r_t 及新的state  S_{t+1}
      
    • 3）将transition样本 (S_t, a_t, r_t, S_{t+1}) 存入D中；
      
    • 4）从D中随机抽取一个minibatch的transitions (S_j, a_j, r_j, S_{j+1}) ;
      
    • 5）令 y_j=r_j ,如果j+1步是terminal的话，否则，令 y_j = r_j + \gamma * maxQ(S_{t+1}, a)
      
    • 6）对 (y_j- Q(S_t, a_j, w)) ^ 2 关于 w 使用梯度下降法进行更新；
      
    • 7）每隔C steps更新target Q网络， w^{-}=w 。
      
    
    
  
  

2015版DQN流程图

它通过使用两个相同的神经网络，以解决数据样本和网络训练之间的相关性；与DQN2013版对比，关键点在于使用两个相同结构的神经网络。其中网络A作为实际Q的计算网络，输出预估的Q值，此为Q估计；
使用B网络输出的Q值，以时序差分方程计算Q现实，最后计算loss，然后每一步都对A进行梯度下降更新，每隔C步（一般是几百步），同步A，B网络权重参数。这就是fix  q-target原理。

以下所说的普通DQN都是2015版；
可以参看一下这个博主的DQN的原理解析，比较详细：
2.3 DQN改进算法Deep Q Network(DQN)原理解析2.3 DQN改进算法

1）Double DQN
传统DQN使用target-Q network得到target-Q值 (现实值)，如下，由于预测具有误差，而且取Qmax值计算，可能导致误差更大：
{\,}{\,}{\,}{\,}{\,} Y_t^{DQN} = R_{t+1} + \gamma  \cdot max_aQ(S_{t+1}, a; \theta ^{-})  \\
于是，Double DQN方法将这个公式优化了一下，不再是取target-Q network 中 S_{t+1} 的Qmax而是取eval-Q network(Q估计)中 max(S_{t+1}, a) ，然后用这个动作a取Q现实中的Q值来替代。更新后的公式为：
{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}Y_t^{DoubleDQN}= R_{t+1} + \gamma \cdot Q(S_{t+1}, argmaxQ(S_{t+1}, a; \theta _t), \theta_t^{-})  \\
2)  DQN with Prioritized Replay
这套算法重点就在batch抽样时候并不是随机抽样，而是按照Memory中样本优先级来抽，所以这能更有效的找到我们需要的样本；



Double DQN. with Prioritized Replay

优先级定义方式：采用SumTree有效抽样，本质上是使误差更大的样本有更大的被选中的概率；
原理：

• 设定 TD_{error}=Q_{现实} - Q_{估计} 来规定优先学习的程度。如果 TD_{error} 越大，就代表我们的预测精度还有很多上升空间，那么这个样本就越需要被学习，也就是优先级p越高。
  
• SumTree是一个完全二叉树，每片树叶存储每个样本的优先级p,每个树节点只有两个分叉，节点值是两个分叉的合，所以SumTree的顶端就是所有p的合。
  

3. DDPG (Deep Deterministic Policy Gradient)

3.1 DDPG介绍

DDPG是google DeepMind团队提出的一种用于输出确定性动作的算法，它解决Actor-Critic神经网络每次参数更新前后都存在相关性，导致神经网络只能片面的看待问题这一缺点。同时也解决了DQN不能用于连续性动作的缺点。[4]

Deep Deterministic Policy Gradient(DDPG)即深度确定性策略梯度算法，是一种可以解决连续性控制问题的方法，属于model-free,off-policy,policy-based的方法。
DDPG可以拆开来看，Deep是说明需要神经网络；Deterministic的意思就是最终确定地只输出一个动作。Policy Gradient是策略梯度算法。DDPG可以看成是DQN的扩展版，不同的是，以往的DQN在最终输出的是一个动作向量，对于DDPG是最终确定地只输出一个动作。而且，DDPG让DQN可以扩展到连续的动作空间。

=================================
在DDPG算法之前如何求解连续动作空间问题？

主要有两种方式：一是对连续动作做离散化处理，然后再利用强化学习算法（例如DQN）进行求解。二是使用Policy Gradient (PG)算法 (例如Reinforce) 直接求解。但是对于方式一，离散化处理在一定程度上脱离了工程实际；对于方式二，PG算法在求解连续控制问题时效果往往不尽人意。
DDPG算法是Actor-Critic (AC)框架下的一种在线式深度强化学习算法，因此算法内部包括Actor网络和Critic网络，每个网络分别遵从各自的更新法则进行更新，从而使得累计期望回报最大化。
3.2 DDPG原理

DDPG算法将确定性策略梯度算法和DQN算法中的相关技术结合在一起[5]，具体而言，DDPG算法主要包括以下三个关键技术：

• 经验回放：智能体将得到的经验数据 (s,a,r,s^{'}, done) 放入Replay Buffer中，更新网络参数时按照批量采样。
  
• 目标网络：在Actor网络和Critic网络外再使用一套用于估计目标的Target Actor网络和Target Critic网络。在更新目标网络时，为了避免参数更新过快，采用软更新方式。
  
• 噪声探索：确定性策略输出的动作为确定性动作，缺乏对环境的探索。在训练阶段，给Actor网络输出的动作加入噪声，从而让智能体具备一定的探索能力。
  

DQN和DDPG直观上的区别

经验回收[6]是强化学习中绝大多数应用的训练数据处理方法，上文DQN中已经介绍了，下面介绍一下目标网络的更新话题。
3.2.1 目标网络：
由于DDPG算法是基于AC框架，因此算法中必然含有Actor和Critic网络。另外每个网络都有其对应的目标网络，所以DDPG算法包含四个网络：

• Actor网络 \mu (\cdot|\theta^\mu)
  
• Critic网络 Q (\cdot|\theta^Q)
  
• Target Actor网络 \mu ^{'} (\cdot | \theta ^{\mu^{'}})
  
• Target Critic网络 Q^{'}(\cdot| \theta ^{'})
  

3.2.2 算法更新过程：
算法更新主要是Actor和Critic网络的参数，其中Actor网络通过最大化累积期望回报来更新 \theta ^{\mu} , Critic网络通过最小化评估值与目标值之间的误差来更新 \theta ^Q 。在训练阶段，从Replay Buffer中采样一个批次的数据，假设采样到的一条数据为 (s, a, r, s^{'}, done)  , Actor 和 Critic网络更新过程如下：

Critic网络更新过程：

• 1) 利用Target Actor网络计算出状态 s^{'} 下的动作： a^{'} = \mu ^{'} (s^{'} | {\,} \theta ^{\mu ^{'}})
  
• 2) 这里需要注意：计算出动作不需要加入噪声。然后利用 Target Critic 网络计算出状态动作对 (s, a) 的目标值： y = r + \gamma (1-done)Q^{'}(s^{'}, a^{'} | {\,} \theta ^ {Q ^{'}})
  
• 3) 接着利用 Critic 网络计算出状态动作对 (s, a) 的评估值： q = Q(s, a | {\,} \theta ^ Q)
  
• 4) 最后利用梯度下降算法最小化评估值和期望值之间的差值 L_c , 从而对Critic网络中的参数进行更新： L_c=(y-q) ^ 2
  

上述过程其实和DQN算法非常类似。

Actor网络更新过程：

• 1) 利用Actor网络计算出状态 s 下的动作： a_{new} = \mu (s | {\,} \theta ^{\mu})
  
• 2) 这里需要注意：计算出动作后不需要加入噪声。然后利用Critic网络计算出状态动作对  (s, a_{new}) 的评估值 （即累计期望回报）： q_{new} = Q(s, a_{new} | {\,} \theta ^ Q)
  
• 3) 最后利用梯度上升算法最大化累积期望回报 q_{new} （代码实现是采用梯度下降算法优化 -q_{new} ,其实本质都是一样的），从而对Actor网络中的参数进行更新。
  

至此我们就完成了对Actor和Critic网络的更新。
3.2.3 目标网络更新：
对于目标网络的更新，DDPG算法中采用软更新方式，也可以称为指数平均移动 (Exponential Moving Average, EMA)。即引入一个学习率 \tau ，将旧的目标网络参数和新的对应网络参数做加权平均，然后赋值给目标网络：
Target Actor网络更新过程：
\theta ^{\mu ^{'}} = \tau \theta ^{\mu}  + (1-\tau) \theta ^ {\mu ^{'}}  \\
Target Critic网络更新过程：
\theta ^{Q ^{'}} = \tau \theta ^{Q}  + (1-\tau) \theta ^ {Q ^{'}}  \\
学习率（动量） \tau \in (0, 1) , 通常取值0.005。
3.2.4 引入目标网络的目的：
引入目标网络的目的其实和DQN算法的想法是一样的。由于目标网络中的参数是通过软更新的方式来缓慢更新的，因此它的输出会更加稳定，利用目标网络来计算目标值自然也会更加稳定，从而进一步保证Critic网络的学习过程更加平稳。
y=r + \gamma (1-done)Q(s^{'} , a^{'} | {\,} \theta ^{Q})  \\
那么由于Critic网络在不断更新，网络波动剧烈，自然目标值 y 的变化也很剧烈。在学习过程中，让Critic网络的评估值追逐一个变化剧烈的目标，很容易出现网络震荡，从而导致整个学习过程坍塌。
其实还有另外一个目的。当使用Critic网络来计算目标值时（如上式所示），它其实本质上是一种自举 (见附录二)(Bootstrapping) 的过程。然后让 Q(s, a | {\,}\theta ^{Q}) 不断逼近y，很容易导致网络过估计。因为当 Q (s^{'}, a^{'} | \theta ^ {Q}) 出现过估计时，会将其回传至 Q(s, a | {\,}\theta ^{Q}) ，导致该项也出现了过估计，从而形成了一种正反馈，最终导致整个网络出现过估计。
那么过估计会出现什么问题呢？如果过估计是均匀的，对于最终的决策不会造成影响；但是如果不均匀，对于最终的决策会产生很大影响。
后续章节会更新
& A3C & PPO & GAE
附录：

1. on-policy 与 off-policy有什么区别？

我们首先搞清楚一个问题：什么是行为策略（Behavior Policy）和目标策略（Target Policy）: 行为策略是用来与环境互动产生数据的策略，即在训练过程中作决策；而目标策略在行为策略产生的数据中不断学习、优化、即学习训练完毕后拿去应用的策略。
为什么会有两个策略？

• 是为了解决强化学习问题中的exploitation（利用）和exploration（探索），利用一个策略（行为策略）保持探索性，提供多样化数据，而不断优化另一个策略（目标策略）。
  
• On-policy的目标策略和行为策略是同一个策略，其好处是简单粗暴，直接利用数据就可以优化其策略，但这样的处理会导致其实是在学习一个局部最优，因为On-policy的策略没办法很好的同时保持即探索又利用；
  
• Off-policy将目标策略和行为策略分开，可以在保持探索的同时，更能求到全局最优值。其难点在于：如何在一个策略下产生的数据来优化另外一个策略？
  

更多的详细解释，可以参考这篇文章：
2. 自举 (Bootstrapping)

表示在当前值函数的计算过程中，会利用到后续的状态值函数或动作值函数，即利用到后续的状态或者状态动作对。
参考

• ^强化学习Q-learning简单理解https://blog.csdn.net/qq_44812718/article/details/124133311
  
• ^强化学习(Q-funcation,DQN)基本介绍https://www.jianshu.com/p/230bae5ca3d1
  
• ^强化学习-什么是DQNhttps://www.jianshu.com/p/865653001642
  
• ^从零开始强化学习（七）——DDPGhttps://www.jianshu.com/p/da663d2628ee
  
• ^深度强化学习-DDPG算法原理与代码https://blog.csdn.net/weixin_46133643/article/details/124356983
  
• ^从零开始强化学习（七）——DDPGhttps://www.jianshu.com/p/da663d2628ee