論文地址: 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的效果,下面詳細介紹。
Q-learning算法在低維狀態下的成功以及DQN和target DQN的效果已經很好了,但是人們發現了一個問題就是之前的Q-learning、DQN算法都會過高估計(overestimate)Q值。開始大家都將其原因歸結於函數逼近和噪音。
其中 表示為:
其實我們發現這個更新過程和梯度下降大同小異,此處均以更新參數 進行學習。
上述的標準的Q-learning學習和DQN中均使用了 操作,使得選擇和評估一個動作值都會過高估計,為了解決這個問題,Double Q-learning率先使用了兩個值函數進行解耦,其互相隨機的更新兩個值函數,並利用彼此的經驗去更新網絡權重和, 為了能夠明顯的對比,
通過對原始的Q-learning算法的改進,Double Q-learning的誤差表示為:
此處意味著我們仍然使用貪心策略去學習估計Q值,而使用第二組權重參數去評估其策略。
Thrun等人在1993年的時候就給出如果動作值包含在區間 之間的標準分布下的隨機的誤差,那麼上限估計為: (m表示動作的數量)
作者給出了一個定理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的表格:淺藍色代表對應的格子有學習得到的估值,灰色代表這部分不採樣,也沒有對應的估值(類似於監督學習這部分沒有對應的標記,所以無法學習到東西)
這樣實驗過後得到的結果用下圖展示:
通過以上的證明和擬合曲線實驗表明,過高估計不僅真實存在,而且對實驗的結果有很大的影響,為了解決問這個問題,在Double的基礎上作者提出了本文的「Double DQN」算法
下面我們提出Double DQN算法的更新過程:
該過程和前面的Double Q-learning算法更新公式基本一樣,唯一的區別在於 和,兩者的區別在於Double Q-learning算法是利用交換來不斷的更新,Double DQN則使用了DQN的思想,直接利用目標網絡()進行更新。
在實驗中,作者基本上實驗結果
對於Atari遊戲來講,我們很難說某個狀態的Q值等於多少,一般情況是將訓練好的策略去運行遊戲,然後根據遊戲中積累reward,就能得到平均的reward作為true value了。
此外作者為了對遊戲有一個統計學意義上的總結,對分數進行了正則化,表示為:
實驗結果如下:
以上基本上是本論文的內容,下面我們藉助實驗進行code的Double DQN算法。其實本部分的復現只是將更新的DQN的目標函數換一下。對於論文中的多項式擬合併不做復現。
此處採用Morvan的代碼,實驗環境是:Tensorflow=1.0&gym=0.8.0,先coding一個智能體Agent
import numpy as npimport tensorflow as tfnp.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 gymfrom Agent import DoubleDQNimport numpy as npimport matplotlib.pyplot as pltimport tensorflow as tfenv = gym.make('Pendulum-v0')env = env.unwrappedenv.seed(1)MEMORY_SIZE = 3000ACTION_SPACE = 11sess = 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.qq_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
主函數入口:
import gymfrom Agent import DoubleDQNimport numpy as npimport matplotlib.pyplot as pltimport tensorflow as tfenv = gym.make('Pendulum-v0')env = env.unwrappedenv.seed(1)MEMORY_SIZE = 3000ACTION_SPACE = 11sess = 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.qq_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
參考文獻:[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