Deep Q learning: DQN及其改进

Deep Q Learning

Generalization

Deep Reinforcement Learning

• 使用深度神经网络来表示
  • 价值函数
  • 策略
  • 模型
• 使用随机梯度下降(SGD)优化loss函数

Deep Q-Networks(DQNs)

• 使用带权重集$\textbf{w}$w的Q-network来表示状态-动作价值函数
  $\hat{Q}(s,a;\textbf{w})\approx Q(s,a)$Q^​(s,a;w)≈Q(s,a)
  

Recall: Action-Value Function Approximation with an Oracle

这是在做control

• $\hat{Q}^\pi(s;a;\textbf{w}) \approx Q^\pi$Q^​π(s;a;w)≈Qπ
• 最小化真实动作-价值函数$Q^\pi$Qπ和近似动作-价值函数的均方误差：
  $J(\textbf{w})=\mathbb{E}_\pi[(Q^\pi(s,a)-\hat{Q}(s,a;\textbf{w}))^2]$J(w)=Eπ​[(Qπ(s,a)−Q^​(s,a;w))2]
• 使用随机梯度下降来寻找一个局部最小值
  $-\frac{1}{2}\nabla_{\textbf{w}}J(\textbf{w}) = \mathbb{E}_\pi[(Q^\pi(s,a)-\hat{Q}^\pi(s,a;\textbf{w}))\nabla_{\textbf{w}}\hat{Q}^\pi(s,a;\textbf{w})]$−21​∇w​J(w)=Eπ​[(Qπ(s,a)−Q^​π(s,a;w))∇w​Q^​π(s,a;w)]
  $\Delta(\textbf{w})=-\frac{1}{2}\alpha\nabla_{\textbf{w}}J(\textbf{w})$Δ(w)=−21​α∇w​J(w)
• 随机梯度下降(SGD)采样梯度

Recall: Incremental Model-Free Control Approaches

• 如同策略评估，一个状态的真实状态-动作价值函数是未知的所以使用一个目标值来替代
• 在蒙特·卡罗尔方法，使用一个回报$G_t$Gt​作为一个替代目标
  $\Delta_{\textbf{w}}=\alpha(G_t-\hat{Q}(s_t,a_t;\textbf{w}))\nabla_{\textbf{w}}\hat{Q}(s_t,a_t;\textbf{w})$Δw​=α(Gt​−Q^​(st​,at​;w))∇w​Q^​(st​,at​;w)
• 在SARSA，代替真实值的是TD目标$r+\gamma(s_{t+1},a_{t+1};\textbf{w})$r+γ(st+1​,at+1​;w)，它利用了当前的函数近似价值
  $\Delta_{\textbf{w}}=\alpha(r+\gamma\hat{Q}(s_{t+1},a_{t+1};\textbf{w})-\hat{Q}(s_t,a_t;\textbf{w}))\nabla_{\textbf{w}}(s_t,a_t;\textbf{w})$Δw​=α(r+γQ^​(st+1​,at+1​;w)−Q^​(st​,at​;w))∇w​(st​,at​;w)
• 在Q-learning，替代真实值的是TD目标$r+\gamma max_a\hat{Q}(s_{t+1},a;\textbf{w})$r+γmaxa​Q^​(st+1​,a;w)，它利用了当前函数近似价值的最大值
  $\Delta_{\textbf{w}}=\alpha(r+\gamma max_a\hat{Q}(s_{t+1},a;\textbf{w})-\hat{Q}(s_t,a_t;\textbf{w}))\nabla_{\textbf{w}}\hat{Q}(s_t,a_t;w)$Δw​=α(r+γmaxa​Q^​(st+1​,a;w)−Q^​(st​,at​;w))∇w​Q^​(st​,at​;w)
  

DQNs in Atari

DeepMind发表在nature上的文章，源代码可以在sites.google.com/a/deepmind.com/dqn找到

• 端到端从像素集s中学习$Q(s,a)$Q(s,a)价值
• 输入状态s是最后四帧的原始像素集的堆砌
• 输出是18个控制杆/按钮位置的$Q(s,a)$Q(s,a)值
• 回报是那一步的得分
• 网络结构和超参数在所有的游戏中都是固定的

他们的核心论点是不必在每一个游戏单独使用完全不同的网络架构来做完全不同的超参数调参来获得成功，这是一个通用的结构足够针对所有的游戏去学习好的决策。它的贡献在于我们尝试得到某种通用的算法和相关配置，能超越我们其他在强化学习论文上看到的只能在三个普通例子上运行。它在50中游戏上尝试做到很好。

Q-Learning with Value Function Approximation

• 使用随机梯度下降最小化MSE损失
• 使用表格查询表示收敛到最优$Q^{*}(s,a)$Q∗(s,a)
• 但是使用VFA的Q-learning会发散
• 两个担忧引发了这个问题
  • 采样之间的相关性
  • 非驻点的目标
• Deep Q-learning(DQN)同时通过下列方式解决这两项挑战
  • 经验重播(Experience replay)
  • 固定Q-targets

DQNs: 经验重播

• 为了有助于移除相关性，从先前的经验中存储数据集(称作重播缓存)$\mathcal{D}$D
  
• 为进行经验重播，循环以下步骤：
  • $(s,a,r,s')\sim\mathcal{D}$(s,a,r,s′)∼D：从数据集中采样一个tuple
  • 计算采样s的目标价值：$r+\gamma max_{a'}\hat{Q}(s',a';\textbf{w})$r+γmaxa′​Q^​(s′,a′;w)
  • 使用随机梯度下降来更新网络权重
    $\nabla_\textbf{w} = \alpha(r+\gamma max_a' \hat{Q}(s',a';\textbf{w})-\hat{Q}(s,a;\textbf{w}))\Delta_{\textbf{w}}\hat{Q}(s,a;\textbf{w})$∇w​=α(r+γmaxa′​Q^​(s′,a′;w)−Q^​(s,a;w))Δw​Q^​(s,a;w)

不重用数据能降低内存消耗，但对弱化模型表现。经验重播相当于重用数据，而这是有帮助的。

• 可以把目标视作一个标量，但是权重将会在下一次更新，这改变了目标价值。

DQNs: fixed Q-Targets

• 为了提升稳定性，使用在多次更新中的目标计算固定目标权重
• 使用一个不同的权重来计算目标更不是更新目标
• 记参数集$\text{w}^{-}$w−为在目标中使用的权重，$\textbf{w}$w是被更新的权重
• 计算目标值时有细微的改变：
  • $(s,a,r,s')\sim\mathcal{D}$(s,a,r,s′)∼D：从数据集中采样
  • 从采样s中计算目标值$r+\gamma max_{a'}\hat{Q}(s',a';\textbf{w}^-)$r+γmaxa′​Q^​(s′,a′;w−)
  • 使用随机梯度下降来更新网络权重
    $\Delta_{\textbf{w}} = \alpha(r+\gamma max_{a'}\hat{Q}(s',a';\textbf{w}^-)-\hat{Q}(s,a;\textbf{w}))\nabla_{\textbf{w}}\hat{Q}(s,a;\textbf{w})$Δw​=α(r+γmaxa′​Q^​(s′,a′;w−)−Q^​(s,a;w))∇w​Q^​(s,a;w)

这种Q-learing不是真正的梯度下降方法。GTD(gradient temporal difference) learning 是"更加"真实的梯度下降算法。这样做非常有帮助，但仍然不能保证收敛。

DQNs Summary

• DQN 使用经验重播或固定Q-targets
• 在重播缓存$\mathcal{D}$D中存储变迁$s_t,a_t,r_{t+1},s_{t+1}$st​,at​,rt+1​,st+1​
• 从$\mathcal{D}$D中采样随机的小批量变迁$(s,a,r,s')$(s,a,r,s′)
• 计算相对于旧的，固定的参数集$\textbf{w}^-$w−的Q-learnning目标
• 优化Q-network和Q-learning 目标之间的均方误差
• 使用随机梯度下降

基本上都是用$\epsilon$ϵ-greedy exploration

DQN Result in Atari

这张图来自Deep Mind团队2015年的一篇论文，他们在50中游戏上实验了DQN算法，使用了CNN处理每一帧游戏画面。在超过半数的游戏里，都能实现接近人类甚至大幅领先人类的水平，但是需要大量的数据和时间来训练。

Which Aspects of DQN were Import for Success?

哪一部分对成功贡献最大？

Deep RL

• 在Atari游戏上的成功引起了使用深度神经网络来做价值函数近似的浓厚兴趣
• 这里列举了一些在之后马上的改进(还有很多其他的)
  • Double DQN (Deep Reinforcement Learning with Double Q-Learning, Van Hasselt et al, AAAI 2016)
  • Prioritized Replay (Prioritized Experience Replay, Schaul et al, ICLR 2016)
  • Dueling DQN (best paper ICML 2016) (Dueling Network Architectures for Deep Reinforcement Learning, Wang et al, ICML 2016)
    人工智能的学术会议，大多可以免费下载论文(非IEEE)，不需要权限，所以上面的链接你可以直接点)

补充一点：
2018年Deep Mind在AAAI发表了组合6中DQN改进方法(包括上述)的Rainbow，Rainbow: Combining Improvements
in Deep Reinforcement Learning

Recall: Double Q-Learning

$1:\ Intialize \ Q_1(s,a)$1: Intialize Q1​(s,a) and $Q_2(s,a), \forall s \in S, a \in A \ t=0,$Q2​(s,a),∀s∈S,a∈A t=0, initial state $s_t=s_0$st​=s0​
$2:\ loop$2: loop
$3:\ \quad Select$3: Select $a_t$at​ using $\epsilon$ϵ-greedy $\pi(s)=argmax_a Q_1(s_t,a)+Q_2(s_t,a)$π(s)=argmaxa​Q1​(st​,a)+Q2​(st​,a)
$4:\ \quad Observe \ (r_t,s_{t+1})$4: Observe (rt​,st+1​)
$5:\ \quad if$5: if(with 0.5 probability) then
$6:\ \quad \quad Q_1(s_a,a_t) \leftarrow Q_1(s_t,a_t)+\alpha$6: Q1​(sa​,at​)←Q1​(st​,at​)+α
$7:\ \quad else$7: else
$8:\ \quad \quad Q_2(s_t,a_t) \leftarrow Q_2(s_t,a_t)+\alpha$8: Q2​(st​,at​)←Q2​(st​,at​)+α
$9:\ \quad end if$9: endif
$10:\ \quad t= t+1$10: t=t+1
$11: end \ loop$11:end loop

这是在将我们如何选择action与评估那个action的价值分离开，以解决过估计的问题。

Double DQN

• 扩展Double Q-Learning的思想到DQN
• 当前Q-network的$\textbf{w}$w用于选择动作
• 旧的Q-network的$\textbf{w}^-$w−用于评估动作
  $\Delta_\textbf{w}=\alpha(r+\gamma \hat{Q}(argmax_{a'}\hat{Q}(s',a';\textbf{w});\textbf{w}^-)-\hat{Q}(s,a;\textbf{w}))$Δw​=α(r+γQ^​(argmaxa′​Q^​(s′,a′;w);w−)−Q^​(s,a;w))
  

Double DQN

在Atari游戏中，Double DQN通常会有很大帮助。

Refresher: Mars Rover Model-Free Policy Evaluation

先选择$(s_2,a_1,0,s_1)$(s2​,a1​,0,s1​)，0+$\gamma V(s_1)$γV(s1​)，再选择$(s_3,a_1,0,s_2)$(s3​,a1​,0,s2​)，这跟蒙特·卡罗尔方法一样，意味着没有误差。所以重播时选择元组的顺序是有影响的。

Impact of Replay

• 在表格法TD-learning中，重播更新的顺序能加速学习
• 重复某些更新能比其他更新看起来能够更好地反向传播信息
• 如何系统化的做prioritize updates?

Potential Impact of Ordering Episodic Replay Updates

• Schaul, Quan, Antonoglou, Silver ICLR 2016
• 黑盒(Oracle): 选择$(s,a,r,s')$(s,a,r,s′)元组来重播将会降低全局loss
• 在收敛方面能有指数级别的提升
  • 收敛需要的更新数量
• 黑盒不是一个实际的方法但是描述了顺序的影响

Prioritized Experiemce Replay

让我们来根据TD error赋予一些元组优先级

• 记$i$i是第$i$i个经验元组$(s_i,a_i,r_i,s_{i+1})$(si​,ai​,ri​,si+1​)
• 采样元组以使用优先级函数来更新
• 一个元组的优先级和DQN error成比例
  $p_{i} = | r+\gamma max_{a'} Q(s_{i+1},a';\textbf{w}^-) - Q(s_i,a_i;\textbf{w}) |$pi​=∣r+γmaxa′​Q(si+1​,a′;w−)−Q(si​,ai​;w)∣
  (两边竖线绝对值的意思)
• 每一个元组都更新$p_i$pi​
• 其中一个方法$^1$1: 成比例(随机优先化)
  $P(i)=\frac{p_i^\alpha}{\sum_k p_i^\alpha}$P(i)=∑k​piα​piα​​
• $\alpha=0$α=0的话会产生了什么样的规则在现有的元组中做选择？

均匀采样
$\alpha的选取是一个平衡点$α的选取是一个平衡点

$^1$1请从上面的论文链接里查阅原论文以获得更详细的信息。

Performance of Prioritized Replay vs Double DQN

Value & Advantage Function

Advantage Fuction在采取一个动作和另一个动作的差别之间做度量。希望能理解哪一些动作会有更好的价值。

• 直观理解：用来确定价值的需要特比注意的特征，可能会和那些决定动作收益特征的不同
• E.g.
  • 游戏得分和预测$V(s)$V(s)是相关的
  • 但是在揭示相关动作价值时不是必须的
• 所以提出了优势函数(Advantage function, Baird 1993)
  $A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$Aπ(s,a)=Qπ(s,a)−Vπ(s)

Dueling DQN

Identifiability

• 优势函数(Advantage function)
  $A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$Aπ(s,a)=Qπ(s,a)−Vπ(s)
• (优势是)可辨识的吗？
• 不可辨别

指定优势函数，做了一些预先设定的假设

• Unidentifiable
• 观点1：如果a是选择的动作，强迫$A(s,a)=0$A(s,a)=0
  $\hat{Q}(s,a;\textbf{w})=\hat{V}(s;\textbf{w})+(\hat{A}(s,a;\textbf{w})-max_{a' \in \mathcal{A}}\hat{A}(s,a';\textbf{w}))$Q^​(s,a;w)=V^(s;w)+(A^(s,a;w)−maxa′∈A​A^(s,a′;w))
• 观点2：使用平均值作为baseline(更稳定)
  $\hat{Q}(s,a;\textbf{w})=\hat{V}(s;\textbf{w})+(\hat{A}(s,a;\textbf{w})-\frac{1}{|\mathcal{A}|}\sum_{a'}\hat{A}(s,a';\textbf{w})$Q^​(s,a;w)=V^(s;w)+(A^(s,a;w)−∣A∣1​∑a′​A^(s,a′;w)

Dueling DQN V.S. Double DQN with Prioritized Replay

Practical Tips for DQN on Atati (From J. Schulman)

以下是来自伯克利博士John Schulman,OpanAI老大的在Atari上使用DQN的建议：