DQN系列(2): Double DQN算法原理與實現

2021-02-23 深度強化學習實驗室

論文地址: https://arxiv.org/pdf/1509.06461.pdf

本文是Google DeepMind於2015年12月提出的一篇解決Q值"過估計(overestimate)"的文章,發表在頂級會議AAAI上,作者Hado van Hasselt在其2010年發表的Double Q-learning算法工作的基礎上結合了DQN的思想,提出了本文的state-of-the-art的Double DQN算法。給出了過估計的通用原因解釋和解決方法的數學證明,最後在Atari遊戲上有超高的分數實驗表現。

正常論文的閱讀方式,先看摘要和結論:通常情況下,在Q-learning學習中「過估計」是經常發生的,並且影響實驗的性能,作者提出了一種可以回答這個問題,並在Double Q-learning算法的基礎上進行function approximation的方法,結果表明不僅可以減少觀察值的過估計,而且在許多遊戲上還有更好的性能表現。而結論部分如下:作者將整個文章的貢獻總結了五點:前三點基本上說了過估計問題的存在,重要性和Double Q-learning算法能解決這個問題,本文重點是第四,作者提出了一種在Double Q-learning基礎上利用「DQN」算法網絡結構的方法「Double DQN」,並在第五點獲得state-of-the-art的效果,下面詳細介紹。

1. 問題闡述1.1 過估計問題現象

Q-learning算法在低維狀態下的成功以及DQN和target DQN的效果已經很好了,但是人們發現了一個問題就是之前的Q-learning、DQN算法都會過高估計(overestimate)Q值。開始大家都將其原因歸結於函數逼近和噪音。

Q-learning拿到狀態對應的所有動作Q值之後是直接選取Q值最大的那個動作,這會導致更加傾向於估計的值比真實的值要高。為了能夠使得標準的Q-learning學習去大規模的問題,將其參數化Q值函數表示為:

其中 表示為:

其實我們發現這個更新過程和梯度下降大同小異,此處均以更新參數  進行學習。

DQN算法非常重要的兩個元素是「經驗回放」和「目標網絡」,通常情況下,DQN算法更新是利用目標網絡的參數 ,它每個 步更新一次,其數學表示為:

上述的標準的Q-learning學習和DQN中均使用了  操作,使得選擇和評估一個動作值都會過高估計,為了解決這個問題,Double Q-learning率先使用了兩個值函數進行解耦,其互相隨機的更新兩個值函數,並利用彼此的經驗去更新網絡權重, 為了能夠明顯的對比,

Double Q-learning,2010年本文作者Hasselt就針對過高估計Q值的問題提出了Double Q-learning,他就是嘗試通過將選擇動作和評估動作分割開來避免過高估計的問題。在原始的Double Q-Learning算法裡面,有兩個價值函數(value function),一個用來選擇動作(當前狀態的策略),一個用來評估當前狀態的價值。這兩個價值函數的參數分別記做  和  。算法的思路如下:

通過對原始的Q-learning算法的改進,Double Q-learning的誤差表示為:

此處意味著我們仍然使用貪心策略去學習估計Q值,而使用第二組權重參數去評估其策略。

1.2 估計誤差: 「過估計」1.2.1 上界估計

Thrun等人在1993年的時候就給出如果動作值包含在區間  之間的標準分布下的隨機的誤差,那麼上限估計為:  (m表示動作的數量)

1.2.2 下界估計

作者給出了一個定理1:

在一個狀態下如果動作 且 ,則:【1】 
【2】Double Q-learning的下界絕對誤差為0

根據定理1我們得到下界估計的值隨著  的增大而減小,通過實驗,下面結果表明 對估計的影響,圖中明顯表明,Q-learning的隨m的增大越來越大,而Double Q-learning是無偏估計,並未隨著m增大而過度變化,基本上在0附近。

附錄:定理1證明過程

此處作者還得出一個定理結論

證明如下:

為了進一步說明Q-learning, Double Q-learning估值偏差的區別,作者給出了一個有真實值的環境:假設值為  ,然後嘗試用6階和9階多項式擬合這兩條曲線,一共進行了三組實驗,參見下面表格

這個試驗中設定有10個action(分別記做 a1,a2,…,a10 ),並且Q值只與state有關。所以對於每個state,每個action都應該有相同的true value,他們的值可以通過目標Q值那一欄的公式計算出來。此外這個實作還有一個人為的設定是每個action都有兩個相鄰的state不採樣,比如說 a1 不採樣-5和-4(這裡把-4和-5看作是state的編號), a2 不採樣-4和-3等。這樣我們可以整理出一張參與採樣的action與對應state的表格:淺藍色代表對應的格子有學習得到的估值,灰色代表這部分不採樣,也沒有對應的估值(類似於監督學習這部分沒有對應的標記,所以無法學習到東西)

這樣實驗過後得到的結果用下圖展示:

最左邊三幅圖(對應 action2 那一列學到的估值)中紫色的線代表真實值(也就是目標Q值,通過s不同取值計算得出),綠色的線是通過Q-learning學習後得到的估值,其中綠點標記的是採樣點,也就是說是通過這幾個點的真實值進行學習的。結果顯示前面兩組的估值不準確,原因是我們有十一個值( s∈−6,−5,−2,−1,0,1,2,3,4,5,6 ),用6階多項式沒有辦法完美擬合這些點。對於第三組實驗,雖然能看出在採樣的這十一個點中,我們的多項式擬合已經足夠準確了,但是對於其他沒有採樣的點我們的誤差甚至比六階多項式對應的點還要大。中間的三張圖畫出了這十個動作學到的估值曲線(對應圖中綠色的線條),並且用黑色虛線標記了這十根線中每個位置的最大值。結果可以發現這根黑色虛線幾乎在所有的位置都比真實值要高。右邊的三幅圖顯示了中間圖中黑色虛線和左邊圖中紫線的差值,並且將Double Q-Learning實作的結果用同樣的方式進行比較,結果發現Double Q-Learning的方式實作的結果更加接近0。這證明了Double Q-learnign確實能降低Q-Learning中過高估計的問題。前面提到過有人認為過高估計的一個原因是不夠靈活的value function,但是從這個實驗結果中可以看出,雖然說在採樣的點上,value function越靈活,Q值越接近於真實值,但是對於沒有採樣的點,靈活的value function會導致更差的結果,在RL領域中,大家經常使用的是比較靈活的value function,所以這一點的影響比較嚴重。雖然有人認為對於一個state,如果這個state對應的action的估值都均勻的升高了,還是不影響我們的決策啊,反正估值最高的那個動作還是最高,我們選擇的動作依然是正確的。但是這個實驗也證明了:不同狀態,不同動作,相應的估值過高估計的程度也是不一樣的,因此上面這種說法也並不正確。2. Double DQN 算法原理及過程

通過以上的證明和擬合曲線實驗表明,過高估計不僅真實存在,而且對實驗的結果有很大的影響,為了解決問這個問題,在Double的基礎上作者提出了本文的「Double DQN」算法

下面我們提出Double DQN算法的更新過程:

該過程和前面的Double Q-learning算法更新公式基本一樣,唯一的區別在於 ,兩者的區別在於Double Q-learning算法是利用交換來不斷的更新,Double DQN則使用了DQN的思想,直接利用目標網絡()進行更新。

在實驗中,作者基本上實驗結果

對於Atari遊戲來講,我們很難說某個狀態的Q值等於多少,一般情況是將訓練好的策略去運行遊戲,然後根據遊戲中積累reward,就能得到平均的reward作為true value了。

從實驗第一行結果我們明顯可以看出在集中遊戲中,值函數相對於Double DQN都明顯的比較高(如果沒有過高估計的話,收斂之後我們的估值應該跟真實值相同的),此處說明過高估計確實不容易避免。Wizard of Wor和Asterix這兩個遊戲可以看出,DQN的結果比較不穩定。也表明過高估計會影響到學習的性能的穩定性。因此不穩定的問題的本質原因還是對Q值的過高估計

此外作者為了對遊戲有一個統計學意義上的總結,對分數進行了正則化,表示為:

實驗結果如下:

以上基本上是本論文的內容,下面我們藉助實驗進行code的Double DQN算法。其實本部分的復現只是將更新的DQN的目標函數換一下。對於論文中的多項式擬合併不做復現。

3. 代碼復現

此處採用Morvan的代碼,實驗環境是:Tensorflow=1.0&gym=0.8.0,先coding一個智能體Agent



import numpy as np
import tensorflow as tf

np.random.seed(1)
tf.set_random_seed(1)


class DoubleDQN:
def __init__(
self,
n_actions,
n_features,
learning_rate=0.005,
reward_decay=0.9,
e_greedy=0.9,
replace_target_iter=200,
memory_size=3000,
batch_size=32,
e_greedy_increment=None,
output_graph=False,
double_q=True,
sess=None,
):
self.n_actions = n_actions
self.n_features = n_features
self.lr = learning_rate
self.gamma = reward_decay
self.epsilon_max = e_greedy
self.replace_target_iter = replace_target_iter
self.memory_size = memory_size
self.batch_size = batch_size
self.epsilon_increment = e_greedy_increment
self.epsilon = 0 if e_greedy_increment is not None else self.epsilon_max

self.double_q = double_q

self.learn_step_counter = 0
self.memory = np.zeros((self.memory_size, n_features*2+2))
self._build_net()
t_params = tf.get_collection('target_net_params')
e_params = tf.get_collection('eval_net_params')
self.replace_target_op = [tf.assign(t, e) for t, e in zip(t_params, e_params)]

if sess is None:
self.sess = tf.Session()
self.sess.run(tf.global_variables_initializer())
else:
self.sess = sess
if output_graph:
tf.summary.FileWriter("logs/", self.sess.graph)
self.cost_his = []

def _build_net(self):
def build_layers(s, c_names, n_l1, w_initializer, b_initializer):
with tf.variable_scope('l1'):
w1 = tf.get_variable('w1', [self.n_features, n_l1], initializer=w_initializer, collections=c_names)
b1 = tf.get_variable('b1', [1, n_l1], initializer=b_initializer, collections=c_names)
l1 = tf.nn.relu(tf.matmul(s, w1) + b1)

with tf.variable_scope('l2'):
w2 = tf.get_variable('w2', [n_l1, self.n_actions], initializer=w_initializer, collections=c_names)
b2 = tf.get_variable('b2', [1, self.n_actions], initializer=b_initializer, collections=c_names)
out = tf.matmul(l1, w2) + b2
return out

self.s = tf.placeholder(tf.float32, [None, self.n_features], name='s')
self.q_target = tf.placeholder(tf.float32, [None, self.n_actions], name='Q_target')

with tf.variable_scope('eval_net'):
c_names, n_l1, w_initializer, b_initializer = \
['eval_net_params', tf.GraphKeys.GLOBAL_VARIABLES], 20, \
tf.random_normal_initializer(0., 0.3), tf.constant_initializer(0.1)

self.q_eval = build_layers(self.s, c_names, n_l1, w_initializer, b_initializer)

with tf.variable_scope('loss'):
self.loss = tf.reduce_mean(tf.squared_difference(self.q_target, self.q_eval))
with tf.variable_scope('train'):
self._train_op = tf.train.RMSPropOptimizer(self.lr).minimize(self.loss)


self.s_ = tf.placeholder(tf.float32, [None, self.n_features], name='s_')
with tf.variable_scope('target_net'):
c_names = ['target_net_params', tf.GraphKeys.GLOBAL_VARIABLES]

self.q_next = build_layers(self.s_, c_names, n_l1, w_initializer, b_initializer)

def store_transition(self, s, a, r, s_):
if not hasattr(self, 'memory_counter'):
self.memory_counter = 0
transition = np.hstack((s, [a, r], s_))
index = self.memory_counter % self.memory_size
self.memory[index, :] = transition
self.memory_counter += 1

def choose_action(self, observation):
observation = observation[np.newaxis, :]
actions_value = self.sess.run(self.q_eval, feed_dict={self.s: observation})
action = np.argmax(actions_value)

if not hasattr(self, 'q'):
self.q = []
self.running_q = 0
self.running_q = self.running_q*0.99 + 0.01 * np.max(actions_value)
self.q.append(self.running_q)

if np.random.uniform() > self.epsilon:
action = np.random.randint(0, self.n_actions)
return action

def learn(self):
if self.learn_step_counter % self.replace_target_iter == 0:
self.sess.run(self.replace_target_op)
print('\ntarget_params_replaced\n')

if self.memory_counter > self.memory_size:
sample_index = np.random.choice(self.memory_size, size=self.batch_size)
else:
sample_index = np.random.choice(self.memory_counter, size=self.batch_size)
batch_memory = self.memory[sample_index, :]

q_next, q_eval4next = self.sess.run(
[self.q_next, self.q_eval],
feed_dict={self.s_: batch_memory[:, -self.n_features:],
self.s: batch_memory[:, -self.n_features:]})
q_eval = self.sess.run(self.q_eval, {self.s: batch_memory[:, :self.n_features]})

q_target = q_eval.copy()

batch_index = np.arange(self.batch_size, dtype=np.int32)
eval_act_index = batch_memory[:, self.n_features].astype(int)
reward = batch_memory[:, self.n_features + 1]

if self.double_q:
max_act4next = np.argmax(q_eval4next, axis=1)
selected_q_next = q_next[batch_index, max_act4next]
else:
selected_q_next = np.max(q_next, axis=1)

q_target[batch_index, eval_act_index] = reward + self.gamma * selected_q_next

_, self.cost = self.sess.run([self._train_op, self.loss],
feed_dict={self.s: batch_memory[:, :self.n_features],
self.q_target: q_target})
self.cost_his.append(self.cost)

self.epsilon = self.epsilon + self.epsilon_increment if self.epsilon < self.epsilon_max else self.epsilon_max
self.learn_step_counter += 1

主函數入口:

import gym
from Agent import DoubleDQN
import numpy as np
import matplotlib.pyplot as plt
import tensorflow as tf


env = gym.make('Pendulum-v0')
env = env.unwrapped
env.seed(1)
MEMORY_SIZE = 3000
ACTION_SPACE = 11

sess = tf.Session()
with tf.variable_scope('Natural_DQN'):
natural_DQN = DoubleDQN(
n_actions=ACTION_SPACE, n_features=3, memory_size=MEMORY_SIZE,
e_greedy_increment=0.001, double_q=False, sess=sess
)

with tf.variable_scope('Double_DQN'):
double_DQN = DoubleDQN(
n_actions=ACTION_SPACE, n_features=3, memory_size=MEMORY_SIZE,
e_greedy_increment=0.001, double_q=True, sess=sess, output_graph=True)

sess.run(tf.global_variables_initializer())


def train(RL):
total_steps = 0
observation = env.reset()
while True:


action = RL.choose_action(observation)

f_action = (action-(ACTION_SPACE-1)/2)/((ACTION_SPACE-1)/4)
observation_, reward, done, info = env.step(np.array([f_action]))

reward /= 10



RL.store_transition(observation, action, reward, observation_)

if total_steps > MEMORY_SIZE:
RL.learn()

if total_steps - MEMORY_SIZE > 20000:
break

observation = observation_
total_steps += 1
return RL.q

q_natural = train(natural_DQN)
q_double = train(double_DQN)

plt.plot(np.array(q_natural), c='r', label='natural')
plt.plot(np.array(q_double), c='b', label='double')
plt.legend(loc='best')
plt.ylabel('Q eval')
plt.xlabel('training steps')
plt.grid()
plt.show()

參考文獻:
[1]. Deep Reinforcement Learning with Double Q-learning  by Hado van Hasselt and Arthur Guez and David Silver,DeepMind
[2].JUNMO的博客: junmo1215.github.io
[3]. Morvanzhou的Github

相關焦點

  • 深度強化學習專欄 —— 2.手撕DQN算法實現CartPole控制
    這篇文章繼續上文深度強化學習專欄 —— 1.研究現狀中最後提到的使用深度強化學習實現倒立擺的前奏。本節我們從DQN(Deep Q-Network)算法開始說起,會經歷閱讀論文、手撕算法、最後實現CartPole倒立幾個過程。搞強化學習的小夥伴都會了解論文在強化學習領域的重要性。
  • 強化學習 DQN 初探之2048
    老實說,最開始強化學習的知識點還挺多的,看了好久也沒太弄清楚幾個算法的關係,所以本著實踐出真知的想法,找個案例做下。2048小遊戲感覺本身複雜度還可以,又是個 model-base 的模型,檢查起來比較方便,並且可以簡化到2x2,3x3,所以感覺是個很不錯的 demo 案例。順便學習下傳統的 DP 那一套東西,所以也做了一些很簡單的實驗來鞏固下知識。
  • DQN系列(1):Double Q-learning
    而本文章作者巧妙的是使用了兩個估計器(double estimator)去計算Q-learning的值函數,作者將這種方法定義了一個名字叫「Double Q-learning」(本質上一個off-policy算法),並對其收斂過程進行了證明(缺點:當然double Q-learning算法有時會低估動作值,但不會像Q學習那樣遭受過高估計)1.
  • 重磅 詳解深度強化學習,搭建DQN詳細指南(附論文)
    在最簡單的例子中,Q -函數可通過一個表格的形式實現,其中狀態作為行,動作作為列。Q-學習算法的要點可簡單歸結如下:基本上你所需要的只是 Neon、Arcade Learning Environment 和 simple_dqn。嘗試預訓練模型時你甚至不需要 GPU,因為它們也能在 CPU 上運行,雖然很慢。2、你能用 Simple-DQN 做什麼?
  • 強化學習:DQN與Double DQN討論
    這個算法就是著名的 DQN 算法,DQN 是第一個成功地將深度學習和強化學習結合起來的模型,本文將對DQN及其變種進行簡單的討論。本文選自《深入淺出強化學習:原理入門》一書,了解本書詳情請點擊閱讀原文。
  • 長文預警 | 利用DQN玩吃豆人(Pacman)小遊戲
    具體而言,Q-Learning算法表述如下:二.DQN玩吃豆人小遊戲2.1 遊戲簡介參見:Python製作小遊戲(十四)2.2 逐步實現(1)遊戲實現首先,當然是實現吃豆人小遊戲啦!這個開篇就講了,實現思路和之前的差不多,做了一些簡單的改進。
  • 萬字詳述 | 全開源:python寫小遊戲+AI強化學習與傳統DFS/BFS控制分別實現
    具體原理如下圖。使用遞歸的實現我使用遞歸來實現 DFS 算法,我大概描述一下這個過程。數據結構不夠硬的同學,應該靜下心來讀讀我的源碼、或者其他經典的 DFS 教程、或者刷刷 LeetCode 。使用隊列的實現我使用隊列來實現 BFS 算法,我大概描述一下這個過程。數據結構不夠硬的同學,應該靜下心來讀讀我的源碼、或者其他經典的 BFS 教程、或者刷刷 LeetCode 。
  • DQN算法原理及應用(實現Atari遊戲)
    定義 DQN 類,構造器使用 tf.contrib.layers.conv2d 函數構建 CNN 網絡,定義損失和訓練操作。 類中用 set_session() 函數建立會話,用 predict() 預測動作值函數,用 update() 更新網絡,在 sample_action() 函數中用 Epsilon 貪婪算法選擇動作:
  • 深度強化學習-深度Q網絡(DQN)介紹
    強化學習為Agent定義了環境,來實現某些動作以最大化獎勵(這些動作根據policy採取)。對Agent的優化行為的基礎由Bellman方程定義,這是一種廣泛用於求解實際優化問題的方法。為了解決Bellman優化問題,我們使用了一種動態編程的方法。
  • 強化學習DQN算法實戰之CartPole
    而 OpenAI的gym給我們提供了一個非常強大的虛擬環境,這樣我們就可以專注於算法本身的開發了。環境描述基本環境可以參考:https://gym.openai.com/envs/CartPole-v1/學習的目標是使得木棍在小車上樹立的時間儘量長。action的選擇只有向左或者是向右。環境會自動給出給出反饋,每一步後的得分,下一個局面的描述的狀態,是否是結束。
  • 強化學習筆記之DQN
    2.1.5. 完整過程Adam(Adaptive Moment Estimation)算法是將Momentum算法和RMSProp算法結合起來使用的一種算法,我們這裡也先採用Adam方法來優化。3.1.2. agent.py我們定義dqn_agent類,將所需要的方法封裝,包括參數網絡的初始化;step函數:將每一步的狀態行動回報下一步的狀態作為一個記錄加入到memory中;act函數:根據epilsongreedy來選取每一個狀態下的動作;learn函數:根據每次抽樣的batch來學習,通過神經網絡的反向傳播方法優化loss function。
  • DQN解決Flappybird
    2、儘量保持平和的心情,點的時候不要下手太重,儘量注視著小鳥。3、遊戲的得分是,小鳥安全穿過一個柱子且不撞上就是1分。當然撞上就直接掛掉,只有一條命。下一個下一個管道頂部y位置下一個下一個管道底部y位置更多參數解釋請查看:https://pygame-learning-environment.readthedocs.io/en/latest/modules/ple.html四、實現原理
  • 6行代碼搞定基本的RL算法,速度圍觀Reddit高贊帖
    RL算法,而且每個算法都在一個文件夾中完成,即使沒有GPU,每個算法也可以在30秒內完成訓練。近日,有開發人員用PyTorch實現了基本的RL算法,比如REINFORCE, vanilla actor-critic, DDPG, A3C, DQN 和PPO。這個帖子在Reddit論壇上獲得了195個贊並引發了熱議,一起來看一下吧。
  • FM+FTRL算法原理以及工程化實現
    前言上一篇文章講了LR+FTRL算法原理以及工程化實現。在實際的項目開發中,常常使用的是LR+組合特徵+FTRL的方式進行建模。這種方式需要人工組合特徵,非常考驗經驗,而且存在線下組合的有效特徵線上不一定有效、當前有效的特徵未來也不一定有效,所以逐漸被其它的可以自動組合特徵的模型取代。業界常用的兩種組合特徵的方式是:FM系列以及Tree系列。
  • 強化學習系列之九:Deep Q Network (DQN) 補全版
    2. Deep Q Network (DQN) 算法      當然了基於價值的深度強化學習不僅僅是把 Q Learning 中的價值函數用深度神經網絡近似,還做了其他改進。      Experience Replay 的動機是:1)深度神經網絡作為有監督學習模型,要求數據滿足獨立同分布,2)但 Q Learning 算法得到的樣本前後是有關係的。
  • 綜述:圖像濾波常用算法實現及原理解析
    而卷積神經網絡的卷積核參數初始時未知的,根據不同的任務由數據和神經網絡反向傳播算法去學習得到的參數,更能適應於不同的任務。目錄自適應中值濾波中值濾波器中值濾波器是一種常用的非線性濾波器,其基本原理是:選擇待處理像素的一個鄰域中各像素值的中值來代替待處理的像素。
  • Caffe2推出強化學習庫,包含多個基於Caffe2的RL實現
    安妮 編譯自 Caffe2.ai量子位 出品 | 公眾號 QbitAI今年4月,Facebook正式發布了輕量化和模塊化的深度學習框架Caffe2
  • IM裡「附近的人」功能實現原理是什麼?如何高效率地實現它?
    比如下圖中的幾款主流移動端IM中的「附近的xxx」功能:那麼,對於很多即時通訊(IM)的開發者初學者來說,「附近的人」或者類似功能,在技術實現上還有點摸不著頭腦。本文將簡要的為你講解「附近的人」的基本理論原理,並以Redis的GEO系列地理位置操作指令為例,理論聯繫實際地為你講解它們是如何被高效實現的。