【强化学习】DQN及其延伸算法

目录


强化学习笔记,内容来自 刘建平老师的博客

DQN算法

价值函数的近似表示

提出背景:

​ 动态规划DP、蒙特卡罗MC、时序差分TD这些求解MDP问题的算法,使用的状态都是有限个离散状态,问题规模小时易求解。而 当问题规模庞大,或者状态是连续的且离散化后依然规模庞大时,无法将Q表存在有限的内存中。因此用价值函数的近似表示来修改模 型。

近似表示:
状态价值函数

【强化学习】DQN及其延伸算法,其中w是参数

动作价值函数

【强化学习】DQN及其延伸算法,其中w是参数

​ 具体的近似有很多,比如:线性表示法、决策树、最近邻、傅里叶变换等,但是最常用的是神经网络(DNN、CNN、RNN)。

​ 对于状态价值函数,神经网络的输入是状态s的特征向量,输出是状态价值v(s,w)。

​ 对于动作价值函数,有两种方法,一种是输入状态s的特征向量和动作a,输出对应的动作价值q(s,a,w),另一种是只输入状态s的特征 向量,动作集合有多少个动作就有多少个输出q(s,ai,w)。这里隐示了动作是有限个的离散动作。

 

概述

​ 基本思路来源于Q-Learning,但是和Q-Learning不同的地方在于,它的Q值的计算不是直接通过状态值S 和动作A 来计算,而是通过上面讲到的Q网络来计算的,这个Q网络是一个神经网络。

经验回放(experience replay)

​ 将每次和环境交互得到的奖励与状态更新情况都保存起来,用于后面目标Q值的更新。Q-Learning是有一张Q表来保存所有的Q 值的当前结果的,而DQN在做动作价值函数更新时靠的就是经验回放。从经验池查询得到的S、A用神经网络结合公式计算得到的目 标Q值和直接通过Q网络直接计算得到的Q估计值肯定是不等的(经验池里的是之前神经网络算出来的,其网络参数与当前网络的不 同,这个差值作为神经网络的损失函数Loss Function,那么可以通过梯度的反向传播来更新神经网络的参数w,当w收敛后就得到的 近似的Q值计算方法,进而贪婪策略也就求出来了。

 

算法流程

输入:迭代轮数T、状态特征维度n、动作集A、步长α、衰减因子γ、探索率ϵ、Q网络结构、批量梯度下降的样本数m

输出:Q网络参数w

​ 1. 随机初始化Q网络的所有参数w,基于w初始化所有的状态和动作对应的价值Q,清空经验池D

​ 2. for i in [ 1, T ]:

​ a)初始化S为当前状态序列的第一个状态,拿到其特征向量ϕ(S)

​ b)把ϕ(S)输入Q网络,得到所有动作对应的Q值输出,用ε-greedy策略从中选择出动作A

​ c)执行动作A,由环境得到新状态S‘ 对应的特征向量ϕ(S‘)、奖励R’、终止标志is_end

​ d)将 { ϕ(S),A,R,ϕ(S‘),is_end } 这个五元组存入经验池D

​ e)前进一步:S = S’

​ f)从经验池中采集m个样本 { ϕ(Sj),Aj,Rj,ϕ(Sj‘),is_endj },j = 1,2,3…,把S‘ 和A’ 输入神经网络结合贪婪策略计算当前目标Q 值 yj:

【强化学习】DQN及其延伸算法

​ g)把S‘ 和A’ 输入Q网络直接求Q估计值,由目标Q值和Q估计值求损失函数Loss Function,然后梯度反向传播更新Q网络参数w

​ h)if S’是终止状态,break;else 跳回步骤b

​ (注意,f步和g步的Q值计算都需要用到Q网络。另外,实际应用中为了算法较好的收敛,探索率ϵ需要随着迭代的进行而变小 )

 

小结

​ DQN由于对价值函数做了近似表示,因此有了解决大规模强化学习问题的能力。但是DQN有个问题,就是它并不一定能保证Q网络的收敛,也就是说不一定可以得到收敛后的Q网络参数。这会导致训练出的模型效果很差。针对这个问题衍生出了DQN的很多变种,比如Nature DQN(NIPS 2015)、Double DQN、Dueling DQN等。

 
 
 
 

Nature DQN算法

概述

Nature DQN的优化点:

​ 目标Q值的计算用到了当前要训练的网络参数w:

【强化学习】DQN及其延伸算法

​ 用来计算损失函数的目标Q值和Q估计值,二者相关性太强,不利于算法收敛。因此提出Nature DQN使用两个Q网络来分别计 算目标Q值和Q估计值,从而减少二者间的依赖关系。

Nature DQN 建模——双网络结构:

​ 相较于普通DQN,Nature DQN使用了两个Q网络,当前Q网络用来选择动作,更新模型参数,目标Q网络用于计算目标Q值。 目标Q网络的网络参数不需要迭代更新,而是每隔一段时间从当前Q网络复制过来,即延时更新,这样可以减少目标Q值和当前 Q值的相关性。二者其余部分基本是完全相同的。(要注意的是,两个Q网络的结构是一模一样的。这样才可以复制网络参数 )

 

算法流程

输入:迭代轮数T、状态特征维度n、动作集A、步长α、衰减因子γ、探索率ϵ、当前Q网络Q、目标Q网络Q′、批量梯度下降的样本数m、 目标Q网络参数更新频率C

输出:当前Q网络参数(目标Q网络只是辅助工具)

​ 1. 随机初始化所有状态和动作对应的价值Q,随机初始化当前Q网络的所有参数w,初始化目标Q网络Q′的参数w′=w,清空经验池D

​ 2. for i in [ 1, T ]:

​ a)初始化S为当前序列的第一个状态,求其特征向量 ϕ(S)

​ b)把 ϕ(S) 输入当前Q网络,得到所有动作对应的Q值输出,用 ε-greedy 策略从中选择出动作 A

​ c)执行动作 A,由环境得到新状态 S‘ 对应的特征向量 ϕ(S’)、奖励 R、终止标志 is_end

​ d)将 { ϕ(S),A,R,ϕ(S‘),is_end } 这个五元组存入经验池 D

​ e)前进一步:S = S’

​ f)从经验池中采集m个样本 { ϕ(Sj),Aj,Rj,ϕ(Sj‘),is_endj },j = 1,2,3…,把S‘ 和A’ 输入目标Q网络结合贪婪策略计算当前目 标Q值 yj:

【强化学习】DQN及其延伸算法(注意:公式里的是Q’ 不是Q )

​ g)把S‘ 和A’ 输入当前Q网络求Q估计值,由目标Q值和Q估计值求损失函数Loss Function,然后梯度反向传播更新当前Q 网络参数w

​ h)if i%C == 0:更新目标Q网络参数w’ = w

​ i)if S’是终止状态,break;else 跳回步骤b

​ (注意,f步用的是目标Q网络、g步用的是当前Q网络。另外,实际应用中为了算法较好的收敛,探索率ϵ需要随着迭代变小 )
 

小结

​ Nature DQN 对 普通DQN 做了相关性方面的改进,这个改进虽然不错,但是仍然没有解决DQN的 很多问题,比如:

1) 目标Q值的计算是否准确?全部通过max Q来计算有没有问题?

2) 从经验池随机采样的方法好吗?按道理不同样本的重要性是不一样的。

3) Q值代表状态动作的价值,那么单独动作价值的评估会不会更准确?

第一个问题对应的改进是Double DQN, 第二个问题的改进是Prioritised Replay DQN,第三个问题的改进是Dueling DQN。

 
 
 
 

Double DQN算法

概述

DDQN的优化点:

​ 在DDQN之前,基本上所有的目标Q值都是通过贪婪法直接得到的,无论是Q-Learning、普通DQN 还是 Nature DQN。比如对 于Nature DQN,虽然用了两个Q网络并使用目标Q网络计算目标Q值,其第 j 个样本的目标Q值的计算还是贪婪法得到的:

【强化学习】DQN及其延伸算法

​ 使用max虽然可以快速让Q值向可能的优化目标靠拢,但是很容易过犹不及,导致过度估计(Over Estimation)。所谓过度估计就 是最终得到的算法模型有很大的偏差(bias)。而DDQN通过解耦目标Q值动作的选择和目标Q值的计算这两步,来达到消除过度估计的 问题。

DDQN建模——Q值与动作解耦:

​ DDQN 和 Nature DQN一样,也有一样的两个Q网络结构。在 Nature DQN 的基础上,通过解耦目标Q值动作的选择和目标Q值的计算这两步,来消除过度估计的问题。

​ Nature DQN对于非终止状态,其目标Q值的计算式子是:

【强化学习】DQN及其延伸算法

​ 在DDQN这里,不再是直接在目标Q网络里面找各个动作中最大Q值,而是先把S‘ 输入当前Q网络中找出最大Q值对应的动作amax(S′j,w),即:

【强化学习】DQN及其延伸算法

​ 然后利用这个选择出来的动作amax(S′j,w)在目标网络里面去计算目标Q值。即:

【强化学习】DQN及其延伸算法

​ 综合起来写就是:

【强化学习】DQN及其延伸算法

​ 动作A’ 是在当前Q网络对经验池样本S‘ 的输出中选择,然后用目标Q网络对A‘ 和S’ 算目标Q值。

 

算法流程

输入:迭代轮数T、状态特征维度n、动作集A、步长α、衰减因子γ、探索率ϵ、当前Q网络、目标Q网络、批量梯度下降的样本数m、目标Q网络参数更新频率C

输出:当前Q网络参数

​ 1. 随机初始化所有状态和动作对应的价值Q,随机初始化当前Q网络的所有参数w,初始化目标Q网络Q′的参数w′=w,清空经验池D

​ 2. for i in [ 1, T ]:

​ a)初始化S为当前状态序列的第一个状态, 拿到其特征向量 ϕ(S)

​ b)把ϕ(S)输入当前Q网络,得到所有动作对应的Q值输出,用ε-greedy策略从中选择出动作 A

​ c)执行动作 A,由环境得到新状态 S‘ 对应的特征向量 ϕ(S’)、奖励 R、终止标志 is_end

​ d)将 { ϕ(S),A,R,ϕ(S‘),is_end } 这个五元组存入经验池 D

​ e)前进一步:S = S’

​ f)从经验池中采集m个样本 { ϕ(Sj),Aj,Rj,ϕ(Sj‘),is_endj },j = 1,2,3…,用Q值与动作解耦的思想计算目标Q值:

【强化学习】DQN及其延伸算法

​ g)用当前Q网络求Q估计值,由目标Q值和Q估计值求损失函数 Loss Function,然后梯度反向传播更新当前Q网络参数 w

​ h)if i%C == 0:更新目标Q网络参数w’ = w

​ i)if S’是终止状态,break;else 跳回步骤b

​ (注意,f步两个网络都用了、g步只用到了当前Q网络。另外,实际应用中为了算法较好的收敛,探索率ϵ需要随着迭代变小 )

 
 
 
 

Prioritized Replay DQN算法

概述

Prioritized Replay DQN的优化点:

​ 普通DQN、Nature DQN、DDQN等都是通过经验回放来采样,进而做目标Q值的计算的。在采样时经验池里的所有样本都有相 同的被采样概率。但是注意到在经验池里面的不同的样本由于TD误差的不同,对反向传播的作用是不一样的。TD误差越大,对反向 传播的作用越大。而TD误差小的样本对反向梯度的计算影响不大。在Q网络中,TD误差就是目标Q网络计算的目标Q值和当前Q网络 计算的Q值之间的差距。这样如果TD误差的绝对值|δ(t)|较大的样本更容易被采样,则算法会比较容易收敛。

Prioritized Replay DQN建模:

​ 1. 经验池优化:

​ Prioritized Replay DQN的经验池中每个样本的优先级正比于TD误差绝对值|δ(t)|。由于引入了经验回放的优先级,Prioritized Replay DQN的经验池和之前的其他DQN算法的经验池不一样,因为这个优先级大小会影响它被采样的概率。在实际使用中,通常使 用SumTree这样的二叉树结构来做带优先级的经验回放池样本的存储:

【强化学习】DQN及其延伸算法

​ 所有的经验回放样本只保存在最下面的叶子节点上面,一个节点一个样本,内部节点不保存样本数据。叶子节点除了保存数据 以外,还要保存该样本的优先级数值(TD误差)。对于内部节点每个节点只保存自己的儿子节点的优先级值之和。以上面的树结构 为例,根节点是42,如果要采样一个样本,可以在[0,42]之间做均匀采样,采样到哪个区间,就是哪个样本。

​ (注意:当Q网络参数进行了梯度更新后,需要重新计算TD误差,并将TD误差更新到SunTree上面 )

​ 2. Loss Function优化:

​ 通常使用的损失函数:

【强化学习】DQN及其延伸算法

​ 考虑了样本优先级的损失函数要加上优先权重因子:

【强化学习】DQN及其延伸算法

​ 其中wj是第j个样本的优先级权重,由TD误差|δ(t)|归一化得到
 

算法流程(集成了DDQN)

输入:迭代轮数T、状态特征维度n、动作集A、步长α、采样权重系数β、衰减因子γ、探索率ϵ、当前Q网络、目标Q网络、批量梯度下降的样本数m、目标Q网络参数更新频率C、SumTree的叶子节点数S

输出:当前Q网络参数

​ 1. 随机初始化所有状态和动作对应的价值Q,随机初始化当前Q网络的所有参数w,初始化目标Q网络Q′的参数w′=w

​ 2. 初始化经验池SumTree的默认数据结构,SumTree的S个叶子节点的优先级pj都初始化为1

​ 3. for i in [ 1, T ]:

​ a)初始化S为当前状态序列的第一个状态, 拿到其特征向量 ϕ(S)

​ b)把ϕ(S)输入当前Q网络,得到所有动作对应的Q值输出,用ε-greedy策略从中选择出动作 A

​ c)执行动作 A,由环境得到新状态 S‘ 对应的特征向量 ϕ(S’)、奖励 R、终止标志 is_end

​ d)将 { ϕ(S),A,R,ϕ(S‘),is_end } 这个五元组存入SumTree

​ e)前进一步:S = S’

​ f)从SumTree中依概率 P(j) = pj / ∑(pi) 采集m个样本 { ϕ(Sj),Aj,Rj,ϕ(Sj‘),is_endj },j = 1,2,3…,用Q值与动作解耦的 思想计算目标Q值:

【强化学习】DQN及其延伸算法

​ g)用当前Q网络求Q估计值,由目标Q值和Q估计值求带优先权重因子wj的损失函数 Loss Function,然后梯度反向传播更新当 前Q网络参数 w,其中优先权重因子的公式为:

【强化学习】DQN及其延伸算法

​ h)用更新参数后的当前Q网络重新计算经验池中每个样本的Q估计值,然后用目标Q值和新的Q估计值算出新的TD误差作为优先 级更新SumTree

​ i)if i%C == 0:更新目标Q网络参数w’ = w

​ j)if S’是终止状态,break;else 跳回步骤b

​ (注意,f步两个网络都用了、g步只用到了当前Q网络。另外,实际应用中为了算法较好的收敛,探索率ϵ需要随着迭代变小 )

 
 
 
 

Dueling DQN算法

概述

Dueling DQN的优化点:

​ DDQN中通过优化目标Q值的计算来优化算法,Prioritized Replay DQN中通过优化经验回放池按权重采样来优化算法,而在 Dueling DQN中通过优化神经网络的结构来优化算法。

Dueling DQN网络结构:

​ Dueling DQN将Q网络分成两部分。第一部分仅与状态S有关,与具体要采用的动作A无关,叫做价值函数部分,记做V(S,w,α)。 第二部分同时与状态状态S和动作A有关,这部分叫做**优势函数(Advantage Function)**部分,记为A(S,A,w,β)。

【强化学习】DQN及其延伸算法

​ 最终价值函数可以重新 表示为:

【强化学习】DQN及其延伸算法

​ (其中,w是公共部分的网络参数,而α是价值函数部分独有的网络参数,β是优势函数部分独有的网络参数 )

​ 考虑到这个式子无法辨识最终输出里面V(S,w,α)和A(S,A,w,β)各自的作用,为了可以体现这种可辨识性(identifiability),实际使用的 组合公式如下:

【强化学习】DQN及其延伸算法

​ (其实就是对优势函数部分做了中心化的处理 )

 
 
 
 

总结

​ 这里一共总结了5种DQN算法:普通DQn、Nature DQN、DDQN、Prioritized Replay DQN、Dueling DQN,目前使用的比较主流的是后面三种算法思路,这三种算法思路也是可以混着一起使用的,相互并不排斥。

​ 当然DQN家族的算法远远不止这些,还有一些其他的DQN算法没有总结,比如使用一些较复杂的CNN和RNN网络来提高DQN的表达能力,又比如改进探索状态空间的方法等,主要是在DQN的基础上持续优化。

​ DQN算是深度强化学习的中的主流流派,代表了Value-Based这一大类深度强化学习算法。但是它也有自己的一些问题,就是绝大多数DQN只能处理离散的动作集合,不能处理连续的动作集合。虽然NAF DQN可以解决这个问题,但是方法过于复杂了。而深度强化学习的另一个主流流派Policy-Based而可以较好的解决这个问题。

上一篇:SpringBoot集成MyCat


下一篇:51_串口