陳勃 王錦艷

摘 要：針對深度Q網絡（DQN）應用中基于python數據結構直接實現的經驗回放過程時常成為性能瓶頸，提出一種具有高性能及通用性的經驗回放模塊設計方案。該設計方案具有兩層軟件結構：底層的功能內核由C++語言實現，以提供較高的執(zhí)行效率; 上層則由python語言編寫，以面向對象的方式封裝模塊功能并提供調用接口，使模塊具有較高易用性。針對經驗回放所涉及的關鍵操作，一些技術細節(jié)被充分研究和精心設計， 例如，將優(yōu)先級回放機制作為附屬組件與模塊的主體運行邏輯分離，將樣本的可抽取性驗證提前到樣本記錄操作中進行，使用高效的樣本淘汰策略與算法等。這些措施使模塊具有較高的通用性和可擴展性。實驗結果表明，按照該模塊實現的經驗回放過程，整體執(zhí)行效率得到了充分優(yōu)化，兩個關鍵操作——樣本記錄與樣本抽取，皆可高效執(zhí)行。與基于python數據結構的直接實現方式相比，所提模塊在樣本抽取操作上的性能提升了約100倍，從而避免了經驗回放過程成為整個系統(tǒng)的性能瓶頸，滿足了各類DQN相關應用項目的需要。

關鍵詞：強化學習;深度學習;深度Q網絡;經驗回放;軟件設計

中圖分類號：TP302

文獻標志碼：A

Design of experiencereplay module with high performance

CHEN Bo*， WANG Jinyan

College of Mathematics and Computer Science， Fuzhou University， Fuzhou Fujian 350108， China

Abstract：

Concerning the problem that a straightforward implementation of the experiencereplay procedure based on python datastructures may lead to a performance bottleneck in Deep Q Network （DQN） related applications， a design scheme of a universal experiencereplay module was proposed to provide high performance. The proposed module consists of two software layers. One of them， called the “kernel”， was written in C++， to implement fundamental functions for experiencereplay， achieving a high execution efficiency. And the other layer “wrapper”， written in python， encapsulated the module function and provided the call interface in an objectoriented style， guaranteeing the usability. For the critical operations in experiencereplay， the software structure and algorithms were well researched and designed. The measures include implementing the priority replay mechanism as an accessorial part of the main module with logical separation， bringing forward the samples verification of “get_batch” to the “record” operation， using efficient strategies and algorithms in eliminating samples， and so on. With such measures， the proposed module is universal and extendible. The experimental results show that the execution efficiency of the experiencereplay process is well optimized by using the proposed module， and the two critical operations， the “record” and the “get_batch”， can be executed efficiently. The proposed module operates the “get_batch” about 100 times faster compared with the straightforward implementation based on python datastructures. Therefore， the experiencereplay process is no longer a performance bottleneck in the system， meeting the requirements of various kinds of DQNrelated applications.

Key words：

reinforcement learning; deep learning; Deep Q Network （DQN）; experiencereplay; software design

0?引言

Q學習（QLearning）是強化學習方法的一個重要分支，用于從智能個體的過往行為和環(huán)境反饋中學習行為決策模式。此類強化學習過程利用時間差分（Temporal Difference，TD）方法[1]，迭代地累積個體的短期收益（Reward），從而評估在每種可觀察狀態(tài)（State）下施行每種動作（Action）的長程收益值（Q值），來為個體決策作出參考[2]。

傳統(tǒng)QLearning通常采用二維表格的形式來記錄Q值，但這對于具有大量可觀察狀態(tài)或者連續(xù)狀態(tài)的場合顯然不適用[3]。隨著近年來深度學習軟硬件技術的蓬勃發(fā)展，深度Q網絡（Deep Q Network，DQN）方法應運而生。它采用深度神經網絡擬合Q函數[4-5]，而非利用二維表格，從而能夠處理巨大的或者連續(xù)的狀態(tài)空間。DQN方法誕生以來，在應用領域取得了許多顯著的成果，例如，Mnih等[5]以雅達利（Atari） 2600平臺中的游戲為環(huán)境訓練神經網絡，經過訓練后該網絡在多項游戲中的表現超過人類水平;DeepMind團隊研發(fā)的智能圍棋程序AlphaGo于2016年擊敗頂級人類棋手李世石，并于2017年擊敗世界冠軍柯潔[6];趙玉婷等[7]在2018年將DQN方法應用于雙足機器人在非平整地面上的行走控制，使得行走穩(wěn)定性明顯改善。Alansary等[8]在2019年提出基于DQN框架的強化學習主體，用于醫(yī)學圖像中的自動標志檢測;Zhu等[9]在2019年將DQN方法用于國際空中機器人大賽（International Aerial Robotics Competition，IARC）的牧羊人游戲任務中，并驗證了方法的有效性和效率等。

DQN方法之所以能夠取得如此豐碩的成果，除了它利用神經網絡對Q函數進行了更具適用性的表示之外，另兩個重要的原因是：其一，利用單獨的、延遲更新的目標網絡來計算學習目標，使得訓練過程中的誤差值不致有過大波動，以保證訓練的收斂;其二，引入了經驗回放（Experience Replay）機制，消除了訓練樣本間的相關性，從而符合訓練樣本獨立同分布的統(tǒng)計學假設[5， 10]。由此可見，經驗回放是DQN方法中的一個重要環(huán)節(jié)。而從軟件設計與實現的角度，應當將經驗回放過程作為獨立模塊進行封裝，以便于整個DQN方法的實現與應用。在經驗回放模塊的設計中主要需要關注以下兩點：

1） 運行性能。DQN相關應用中，將頻繁使用經驗回放模塊的三個操作，即經驗的記錄（record）、采樣抽?。╣et_batch）和優(yōu)先級設置（set_priority）。這三個操作所產生的時間開銷必須得到優(yōu)化，否則，可能成為整個系統(tǒng)的性能瓶頸，影響整體的執(zhí)行效率。

2） 通用性。作為一個獨立模塊，應當為各類DQN相關應用提供支持，而非只針對某種特殊的應用場景。具體而言，應當支持記錄任意結構的可觀察狀態(tài)（State），兼顧時間序列與非時間序列兩類數據，以及支持多樣化的采樣抽取策略等。

本文針對以上兩點需求，提出一種可行的經驗回放模塊設計方案，并展示和討論其實現效果。

1?經驗回放模塊的接口形式

作為一個封裝的模塊，需要定義可供外部調用的接口，這包括一組相關的軟件實體概念和一組可供調用的操作方法。本章將對其進行介紹。

首先，本文提出的經驗回放模塊涉及下述軟件實體概念：

1） 可觀察狀態(tài)（state）。DQN系統(tǒng)中的state是網絡的輸入，是智能個體可觀察到的環(huán)境的數字化表示。在不同應用中，state可以具有不同的形式，可以是向量、矩陣，或者具有任意高維形狀。經驗回放模塊不應假設state具有任何特定形狀或含義，從而保證模塊的通用性。

2） 動作（action）。智能體能夠采取的行動的編碼，是一個整型數值。

3） 獎勵（reward）。智能體在某個state下采取某個action后立即獲得的獎勵，是一個實數（浮點）型值。

4） 記錄（record）。一個state、action、reward的組合成為一條record。為支持時間序列相關應用，經驗回放模塊應當維護record間的順序關系。

5） 回合（episode）及其句柄（handle）：具有時間順序關系的若干record組成一個episode。在實際的DQN相關應用中，episode通常對應了智能體完成某次任務的完整體驗，例如一局完整的游戲。經驗回放模塊用一個唯一的整型數來標識某個episode，稱作這個episode的handle。

6） 采樣準則（pick_policy）。在使用非時間序列數據的應用[11]中，采樣抽取時以單個record為采樣的最小單元。而時間序列相關的應用[12]中，可能需要連續(xù)抽取長度為pick_len的若干個連續(xù)的record。此外，某些應用中，允許抽取的片段長度不足預期值pick_len（當到達episode結尾時），使得實際抽取的片段長度參差不齊（但不超過pick_len）。上述這些采樣抽取相關的準則在這里稱作pick_policy。

7） 可抽取樣本（pick）。具有順序關系的若干record組成一個片段，如果片段符合pick_policy，則在采樣抽取時可作為候選片段，稱作一個pick。任意一個pick可以用其來源的episode及其首個record在該episode中的時間序列位置表示，故可記作有序對〈pick_epi， pick_pos〉。

8） 優(yōu)先級（priority）。當對記錄在經驗回放模塊中的數據進行采樣抽取時，可以使用均勻隨機抽取或者依優(yōu)先級抽取的策略。若使用后者，則整個經驗回放過程被稱作“優(yōu)先級經驗回放”（Prioritized Experience Replay）[13-15]，此時，每個pick應當具有某種優(yōu)先級數priority，它應是一個實數（浮點）型值。

9） 抽取選擇器（pick_selector）及其句柄（handle）。為使得模塊能夠支持多樣化的采樣抽取策略（均勻隨機或者多種優(yōu)先級抽取算法），本文提出的軟件結構中，將采樣抽取策略抽象為一種稱為pick_selector的附屬組件（詳見第2章），經驗回放模塊利用不同的pick_selector以實施不同的采樣抽取行為。每個pick_selector實例用一個唯一的整型數標識，稱為它的handle。

在以上實體概念的基礎上，定義經驗回放模塊應當支持的主要操作方法有：

1） new_episode（）。建立一個新的episode，并返回其對應的句柄h_epi。

2） new_pick_selector（pick_selector_class）。建立一個pick_selector的實例，其類型為pick_selector_class，并返回該抽取選擇器的句柄h_ps。

3） record（h_epi， state， action， reward， final_state）。在以句柄h_epi標識的episode中追加一條完整的record，即一個state、action、reward的組合。final_state是一個可選項，若傳入final_state則指示該回合以狀態(tài)final_state結束。

4） get_batch（batch_size， h_ps）。用以句柄h_ps標識的pick_selector采樣抽取batch_size個的pick。返回值為一個元組：（batch_state， batch_action， batch_reward， batch_state_next， seq_len， seq_len_next， batch_pick_epi， batch_pick_pos）。其中，返回量batch_state的形狀比單一state的形狀多出兩維，呈現為（batch_size， pick_len，…，…），即以矩陣形式給出抽取的每個pick中的每個時間點上的state。類似地，batch_action和batch_reward的形狀為（batch_size， pick_len），分別表示每個pick中的每個時間點上的action和reward。batch_state_next形狀與batch_state相同，給出了每個pick中的每個時間點的下一時刻的state。seq_len和seq_len_next都是長度為batch_size的向量。如前文所述，由于某些抽取準則中可能允許抽取不足pick_len長度的pick，故需要用seq_len和seq_len_next分別反饋batch_state和batch_state_next中每個pick實際有效的時間序列長度。這樣，抽取出的數據中長于這些實際長度的部分才可以被外部的應用所忽略。batch_pick_epi和batch_pick_pos分別是pick_epi和pick_pos的向量，長度也為batch_size。它們用于標識所抽取的每個pick的來源，以便set_priority方法反饋更新其優(yōu)先級。

5） set_priority（h_ps， pick_epi， pick_pos， priority）。針對以h_ps標識的pick_selector，對以〈pick_epi， pick_pos〉標識的pick設置優(yōu)先級priority。

6） serialize（）。序列化導出經驗回放模塊的數據，用于持久化保存經驗池。

7） unserialize（）。反序列化，用于從保存的持久化數據中恢復經驗回放模塊。

2?經驗回放模塊的架構設計

由于目前大量的強化學習應用基于python實現[16-17]，與之相適應，以往的經驗回放模塊大多也都由python編寫。這使得模塊便于被應用系統(tǒng)所調用。然而，受限于python解釋器本身的效率，此類經驗回放模塊無法達到較高的運行性能，進而影響整個應用的性能。本文綜合考慮性能和易用性，在架構設計上采用雙層的軟件結構（如圖 1）：基本功能由C++語言實現，以謀求較高的運行性能，這些基本功能被導出為動態(tài)鏈接庫中的函數接口，而后由python編寫的包裝類進行封裝，以面向對象的形式提供給外部應用。這種架構兼顧了兩方面的需求，既實現了性能的優(yōu)化，又便于被python應用所使用。下面將介紹上述兩層結構各自的分工及設計。

2.1?功能內核（C++）

功能內核進一步分為函數接口層和數據結構層，前者用于實現內核的主要功能，并為python實現的包裝類提供函數接口，而后者則包含關鍵的數據結構，以及一些底層的算法步驟。

數據結構層的EX_RP結構體是內核中最關鍵的數據結構，其主要包含了一個稱為“episodes”的映射表（以C++標準模板庫的map容器承載），以及一個名為batch_maker的結構體。前者以episode的句柄h_epi為鍵值，存儲指向episode結構體的指針——在單個episode中，向量（以vector容器承載）states、actions、rewards分別以時間順序存放每一時刻的state、action、reward。

batch_maker結構體在對經驗數據進行采樣抽取操作時至關重要，其中主要包含兩個成員向量：pick_table與ps_table。

pick_table中保存了所有episode中可供抽取的pick的訪問位置信息，形式為有序對〈pick_epi， pick_pos〉，其中的pick_epi實際是一個指向episodes中相應episode節(jié)點的指針。另一方面，在episode節(jié)點中的向量pick_index則記錄了該episode中可用的pick在pick_table中對應索引項的位置。于是存放于episode中具體的pick數據和pick_table中的全局索引可以實現快速地相互查詢，這一特性在性能優(yōu)化中十分必要（詳見第4章）。

ps_table是用于記錄“抽取選擇器”（pick_selector）的向量，其中保存了指向pick_selector對象的指針。作為經驗回放模塊的附屬組件，接口類PickSelector指示一組需要實現的接口函數，通過對這些接口的不同實現，可派生多種PickSelector的子類，形如PickSelectorX，用于實現不同的優(yōu)先級回放策略。通過相應的new_pick_selector_X函數可創(chuàng)建PickSelectorX類型的對象實例，并將其指針記錄到ps_table中。而后，其中的接口函數將在內核運行的適當時機被回調。例如，其中的select函數將在get_batch過程中被調用，以實現樣本選取的具體行為;而每次向pick_table中添加新pick信息時，on_pick_table_push_back函數會被回調，以保證數據一致，等等。由于篇幅限制，且此處旨在描述整體架構，故對于具體接口定義和實現不作一一詳述。這種將pick_selector作為附屬組件的做法，將選擇器的實現與經驗回放模塊的主體運行邏輯分離，使得多樣化的抽取采樣策略能夠靈活地添加并運用于系統(tǒng)中，從而增強了模塊的通用性和可擴展性。

數據結構層之上的函數接口層實現了模塊的具體行為：例如，如前文所述，new_pick_selector_X創(chuàng)建類型為PickSelectorX的抽取選擇器實例，并將其指針記錄到ps_table中;record實現經驗數據的記錄;get_batch實現經驗數據的采樣抽取，等。這些接口基本與經驗回放模塊的外部接口相對應，圖1中已展示了其中的一部分，本文將在第4章中詳述其中record和get_batch的一些實現細節(jié)。

面向其上層，函數接口層以動態(tài)鏈接庫形式導出上述接口方法，以便python實現的包裝類調用。

2.2?包裝類（python）

python實現的包裝類ExperienceReplay中包含外部接口的封裝。其利用ctypes模塊導入C++實現的內核動態(tài)鏈接庫后，調用函數接口層提供的函數以實現模塊的實質功能。此外，該包裝類還提供附加特性，包括線程安全與數據形式轉換等。

首先，經驗模塊可能被多線程調用，故應當考慮其訪問過程中的線程安全，以確保數據的一致性。ExperienceReplay中含有一個成員變量_mutex，它是一個threading.Semaphore類型的信號量。通過對_mutex的請求與釋放，可以實現簡單的線程安全：ExperienceReplay中的任何方法，在需要“原子性訪問”其成員變量或調用內核函數的代碼段前皆添加了_mutex.acquire（），以請求信號量，而在訪問完成后皆以_mutex.release（）釋放信號量。

其次，對于數據形式的轉換主要有兩個任務：

1） state形狀的維護。如前文所述，模塊應當支持各種形狀的state，但內核中并不維護或假設state的形狀。因此，在ExperienceReplay中，將應用層傳入的state形狀保存為成員變量——元組_state_shape，而后將state變形為一維數組傳入內核處理;當需要對外回饋state數據時，則應當以先前保存的形狀_state_shape重塑（reshape）傳出的一維數組。這一數據轉換過程，使得應用層能夠使用任意形狀的state。

2） python數據類型與C數據類型轉換。內核接口使用C語言風格的數據類型和數據訪問方式，而應用層卻需要以python風格的數據類型存儲和使用數據，ExperienceReplay中為此進行了必要的轉換。例如，較為復雜的get_batch操作對應的內核函數接口形式為：

程序前

get_batch（char* ptrER， int hPS， int batch_size，

char* batch_pick_epi， int* batch_pick_pos，

float* batch_state， int* batch_action，

float* batch_reward， float* batch_state_next，

int* seq_len， int* seq_len_next）;

程序后

其中，參數ptrER為欲操作的EX_RP對象的指針，包裝類初始化時通過調用接口函數ex_rp_new 已創(chuàng)建了一個EX_RP對象并獲取了該指針，保存為成員變量_kernel，故此時只需直接傳入即可。參數hPS與batch_size分別指示所使用的選擇器句柄，以及采樣抽取樣本量。對于python環(huán)境下傳入的任意整型數，可以使用ctypes模塊方法ctypes.int（）轉換為C語言風格整型數以傳入內核接口函數，此處即為：hPS=ctypes.int（hPS）和batch_size=ctypes.int（batch_size）。剩余的參數皆為傳出數據的指針——在包裝類方法中為其申請空間，而后將指針傳入，內核將修改地址內的數據，作為處理結果，之后包裝類則可在這些空間中訪問到這些結果。以batch_action為例，它將用于存儲get_batch結果中的batch_action分量（其他傳出分量的解釋詳見第1章），形狀應當是（batch_size， pick_len）。但無論外部數據形狀如何，內核函數的參數定義皆為一維數組，故包裝類中應當先為batch_action申請大小為batch_size*pick_len的一維整型空間并獲得地址指針：batch_action=（ctypes.c_int * （batch_size * pick_len））（），而后將batch_action傳入內核。內核處理后，將傳出數據重塑為具有形狀（batch_size， pick_len）的numpy.array類型數據以向應用層傳出，即：

程序前

batch_action=

numpy.array（batch_action）.reshape（[batch_size， pick_len]）

程序后

上述數據類型的轉換，使得應用層可以完全使用python風格的數據類型和數據訪問方式，而無需關注底層較為復雜繁瑣的實際數據交互，大大增強了模塊的易用性。

除了主要的ExperienceReplay類外，包裝層還將所有用于創(chuàng)建pick_selector的接口函數new_pick_selector_X封裝于類PickSelectorClass中——PickSelectorClass中名為X的靜態(tài)函數（帶有修飾符@staticmethod）實際調用接口函數new_pick_selector_X。當用戶層調用ExperienceReplay中的new_pick_selector方法時需傳入函數名稱PickSelectorClass.X作為參數，形如：

程序前

new_pick_selector（PickSelectorClass.X）

程序后

而new_pick_selector方法執(zhí)行中將回調該函數，從而在數據結構層創(chuàng)建PickSelectorX類型的實例。這種接口調用方式使得應用層無需關心底層將pick_selector與經驗回放模塊主體分離的設計細節(jié)，更易于理解和使用。

3?實現細節(jié)與理論分析

本文提出的經驗回放模塊在實現階段主要關注性能的優(yōu)化。在實際應用中，record、get_batch和set_priority是需要被反復調用的三個接口方法，可能成為實際應用中的性能瓶頸。因此，它們是性能優(yōu)化的重點。其中，set_priority的性能由具體的優(yōu)先級算法主導，不是本文論述的要點。于是，本文著重關注record和get_batch的性能優(yōu)化。

在實踐中，由于record操作僅處理單條記錄的插入，而get_batch需要一次性抽取batch_size條記錄，故其時間開銷大約相差batch_size倍，get_batch操作是實際的性能瓶頸。此外，若經驗池的容量有限，則在某些時刻進行record操作時還需考慮記錄的淘汰（刪除），這一操作復雜度可能較高，需要加以優(yōu)化。綜上，本章將主要討論get_batch操作以及record中記錄淘汰過程的性能優(yōu)化。

3.1?get_batch操作的性能優(yōu)化

get_batch操作過程邏輯上需要依pick_policy的規(guī)則整理所有可用的pick，而后利用pick_selector進行樣本抽取。若已有樣本（record）規(guī)模為N，則這一過程的時間復雜度可達O（N）。這是由于在整理可用pick的過程中需要遍歷所有record，以檢查其是否為可用的pick;即使不預先整理所有可用pick，為了支持均勻隨機采樣策略，在樣本抽取步驟中也需要遍歷所有episode，才能實現在所有record中進行無差別的均勻采樣。這也將使得get_batch操作的時間開銷與N相關。

對于get_batch的性能優(yōu)化，本文的指導思想是，將驗證pick可用性的步驟移動到record操作中完成：當一個新的record被添加到經驗池中時，立即檢驗是否因此增加了一個可用pick，而當可用pick被驗證時，它立即被記錄到pick_table中。于是，在get_batch時無需再進行pick的整理和驗證，只需要從全局的pick_table中利用pick_selector進行樣本抽取即可。get_batch的步驟為：

1）調用pick_selector的select接口，以選取batch_size個pick在pick_table中的位置，記作數組pick_index。

2）依據pick_index，在pick_table中取得pick的訪問位置信息，即batch_size個有序對〈pick_epi， pick_pos〉。

3）對每個被選取的有序對，根據指針pick_epi訪問episode節(jié)點，并在pick_pos位置抽取pick數據。

上述流程中，除了pick_selector中select接口的具體實現因抽樣策略而不同，其他步驟的時間開銷皆與樣本規(guī)模N無關。對于select接口，若在均勻隨機抽樣策略下，其時間開銷本就與N無關;若采用各種優(yōu)先級抽取策略，也可采用為與N無關，或者具有O（lbN）復雜度的算法過程，例如同樣可將優(yōu)先級排序過程移動到record和set_priority操作中完成（實現于PickSelector的回調函數接口on_pick_table_push_back和set_priority中），從而避免在select接口中進行耗時的優(yōu)先級排序。事實上，select接口的優(yōu)化方式依賴于專門設計的數據結構和算法，是另一個值得研究的話題，但不是本文討論的重點內容，故不作更多展開說明。

另一方面，將pick可用性的驗證移動到record操作中，使得record操作增加了驗證單個pick可用性的時間開銷，但這與N的大小無關，故并不增加record操作的時間復雜度。

綜上，按照上述優(yōu)化方式，get_batch操作的時間復雜度由具體的抽樣選擇器的select方法決定，可控制在O（1）或者O（logN），且優(yōu)化后不會提高record操作的時間復雜度。因此，模塊的整體運行性能可得到提升。

3.2?record操作中記錄淘汰過程及其性能優(yōu)化

record操作的基本流程為：

1）檢查傳入的句柄h_epi所標識的episode是否存在，若不存在，則調用new_episode以創(chuàng)建新episode，并將h_epi修改為新句柄。

2）將新的record數據寫入上述episode。

3）依照pick_policy檢驗新的record是否造成可用pick增加，如果生成了新的pick，則將其記錄到pick_table，且將pick在pick_table中記錄的位置寫入episode的pick_index。

4）檢查經驗池中的record數量是否達到上限，若達上限，則觸發(fā)記錄淘汰過程。

一般而言，上層應用應直接通過new_episode操作顯式創(chuàng)建episode，并使用其返回的句柄h_epi來指代這個episode。但應當注意到，所創(chuàng)建出的episode句柄h_epi并非永久有效：若經驗池容量有限，則當記錄數到達上限時，步驟4）將會淘汰某些記錄。本文提出的方案將淘汰某個episode的所有記錄，于是被淘汰的episode將從池中消失。若此時上層應用中該episode仍活躍（有新記錄產生），則可能再次發(fā)起record操作，這種情況下經驗回放模塊的行為將是，在步驟1）中重新分配新的episode句柄h_epi，并作為record操作的返回值傳遞給上層應用。于是，對于上層應用而言，應當處理record操作的返回值，以獲知episode的句柄是否發(fā)生了變化。

對于記錄淘汰過程，這里需要討論以下兩個問題：

1） 淘汰episode的選擇。這里考慮兩種淘汰策略：先進先出（First In First Out，FIFO）策略和二次機會（Second Chance）策略。這兩種策略的指導思想皆源于操作系統(tǒng)的頁面置換算法。

FIFO策略簡單地依據episode生成的先后順序選擇擬淘汰的episode：需規(guī)定EX_RP以自增方式生成episode的句柄，即每次new_episode操作從0開始依次以自然數指派新的句柄，下一個將被分配的句柄值記為EX_RP結構體的成員變量h_epi_head，則句柄大小即可代表episode的新舊程度。維護一個成員變量h_epi_tail以記錄當前最小的句柄值，則每次淘汰時直接選擇h_epi_tail所指代的episode即可。淘汰完成后h_epi_tail增加1，從而指向下一個待淘汰的episode。

二次機會策略則需要在每個episode節(jié)點中添加一個布爾型成員變量access_flag，用于指示episode是否被采樣抽取過——每次get_batch操作抽取到一個pick時，會將對應episode的access_flag置為true。而在EX_RP結構中，額外維護一個成員變量h_epi_remove以記錄下一個擬淘汰的episode。當需要淘汰時，h_epi_remove在h_epi_tail與h_epi_head之間循環(huán)移動，以查找access_flag為false的episode，將其作為被淘汰的對象。其間，h_epi_remove掠過的episode的access_flag將被重置為false——即給予每個曾被抽取過的episode一次從淘汰中豁免的機會。

實際應用中應當采用何種淘汰策略，應當與采樣抽取策略配合：對于均勻隨機采樣，經驗池中的pick均無差別，則淘汰時使用FIFO策略即可;而對于各種優(yōu)先級采樣，優(yōu)先級高的pick將更有可能被采樣，在淘汰時使用二次機會策略，可以保證這些價值較高的pick被盡可能地保留在池中。此外，基于操作系統(tǒng)研發(fā)中十分成熟的頁面置換算法，容易實現其他類似的淘汰策略，例如最近最少使用算法（Least Recently Used，LRU）、最不常用算法（Least Frequently Used，LFU）等。

2） 淘汰過程的性能優(yōu)化。如前文所述，淘汰過程將從經驗池中刪除某個episode的全部記錄，即從episodes中刪除episode對應的節(jié)點，并從pick_table中刪除所有屬于該episode的pick信息。前者的時間開銷與全局樣本規(guī)模N無關，但后者則是在長度約為N的vector中刪除散放的n個數據項（假設該episode中包含n條記錄）。按照通常vector中的刪除操作，需要考慮數據的成塊挪動，具有較高時間開銷，整體復雜度為O（nN）。需要對其進行優(yōu)化。

本文的優(yōu)化思路是，考慮到pick_table中的數據無需保持有序，如圖2所示，若需從中刪除數據項i，可將其與pick_table的最后一個數據項j交換，而后再刪除。如此，便可避免數據的成塊挪動。假設某時刻pick_table最后一個數據項的位置為j，pick_table[j]=〈pick_epi， pick_pos〉標識了這最后一個pick所屬的episode為pick_epi，位置為pick_pos。則刪除某個episode（記為e）的具體流程為：

① 從e的pick_index向量中依次查找下一個pick在pick_table中對應索引的位置i，若已達pick_index的結尾，則跳轉到步驟⑧;

② 若j ≥ 0，則設e′=pick_index[j].pick_epi，p′= pick_index[j].pick_pos;

③ 若i ≤ j且e′= e，則j=j-1，并回到步驟②;

④ 若i > j，則回到步驟①;

⑤ 修改e′.pick_index[p′]=i;

⑥ 將pick_table[i]與pick_table [j]數據交換;

⑦j=j-1，并回到步驟①;

⑧ 刪除pick_table中位于j之后的數據;

⑨ 從episodes中刪除e。

依上述流程，淘汰一個episode的時間復雜度降為O（n），即僅與擬淘汰episode的記錄數n有關，而與全局樣本規(guī)模N無關。又易知，當經驗池容量滿后，若episode的平均記錄數為n，則平均每進行n次record操作，才會發(fā)生一次淘汰。于是，淘汰過程實際為record帶來等效于O（1）復雜度的時間開銷。而不發(fā)生淘汰時record的時間開銷也僅為O（1），因此，經過上述優(yōu)化后，record操作的整體時間復雜度為O（1）。

4?性能測試與討論

為測試所提出的方法的實際執(zhí)行性能，本文設計并實施了一項簡單的實驗。該測試實驗運行環(huán)境的主要參數為：Intel Core i77700K CPU 4.2GHz、16GB RAM、Windows 10操作系統(tǒng)。

每次實驗中，模擬一個假設的數據記錄（record）與樣本抽取（get_batch）過程。首先，假設有來自2k個回合的數據，每個回合含有2s條隨機生成的記錄，故總計數據規(guī)模為N=2k+s條記錄;然后，將這些記錄利用record操作逐條添加進空的經驗池，統(tǒng)計這一過程耗費的時間，計算出平均每100次record操作的時間開銷，記作統(tǒng)計量record_100;接著，對這個經驗池進行10-000次get_batch操作，單次抽取5-000個記錄片段（batch_size=5-000），每個片段的時間長度為8（pick_len=8），統(tǒng)計其耗費的時間，從而計算每次get_batch的平均時間開銷，記作統(tǒng)計量get_5000。

分別取k=5， 5.5， 6， 6.5， …， 11; s=6， 6.5， 7， 7.5， …， 12，共進行169次不同k、s組合的實驗，得到一組時間開銷統(tǒng)計量。為避免計算機在運行測試時由于不可預期的原因（如后臺運行的其他程序等）造成統(tǒng)計誤差，上述實驗反復進行了5次。對于每個統(tǒng)計量，皆取得5次實驗的最小值，得到的結果數值如表1、2所示。

統(tǒng)計量record_100與get_5000可視化作圖如圖3與圖4?？梢钥吹絩ecord的操作的時間開銷與數據的規(guī)模N基本無關，這與第3章的理論分析相符，且record_100耗時皆在700μs 左右，即單次record操作耗時僅7μs，在實際應用中不會成為性能瓶頸。

另一方面，與理論分析有所不同，從圖4可看出，get_batch操作的時間開銷與數據規(guī)模（N=2k+s）相關。進一步繪制數據規(guī)模N同get_5000的關系曲線（相同N值下的多個get_5000取平均值），如圖5所示。

從圖5可以看到，當lb N<16時，時間開銷基本與規(guī)模無關，當lb N ≥ 16時，時間開銷上漲，初期上漲較快，而后期上漲趨勢逐漸放緩。本文認為，之所以get_batch的時間開銷并非完全如理論分析所描述的常數級別，是由于記錄抽取操作需要一次性訪問大量記錄，這些記錄在內存中分散的程度，與數據規(guī)模相關：當數據規(guī)模小于某個范圍時，內存訪問較為集中，CPU緩存命中率很高，時間開銷則在很低水平上基本呈現常數級復雜度;但當數據規(guī)模上升時，CPU緩存命中率將下降，實際訪存的時間將被增長，從而導致此時的時間開銷隨數據規(guī)模增長。

因此，與理論分析不符的時間開銷增長是由于CPU緩存等硬件級別或系統(tǒng)優(yōu)化層面上的機制所導致，與算法本身的性能特性無關。而且，可以看到，無論時間開銷增長情況如何，在較大的數據規(guī)模上，做一次get_batch（5-000條記錄）消耗的時間也能控制在800μs以下，且增長速率很低——低于具有O（lbN）理論復雜度的算法。這一性能是令人滿意的，且不會在實際應用中形成性能瓶頸。

此外，為對比以C++為內核實現的經驗回放與單純依靠python實現的性能差異，我們還將本文中的C++內核替換為python實現的版本，并嘗試執(zhí)行同樣的測試。表3展示了僅使用python版本時record_100與get_5000的耗時。

可以看到，在純python版本中record_100數值在500μs左右，即單次record操作耗時5μs，較本文方法略低。這是由于record操作本身業(yè)務邏輯簡單，單次處理數據量小，無論使用python還是C++實現都十分迅速。因此當使用本文的C++與python混合方案時C++/python間的接口開銷使得綜合性能有所損失。

然而，在實際的DQN應用中，模型訓練過程才是性能提升的關鍵，而record操作無論從數據處理量還是耗時占比上與get_batch操作相比都不是同個數量級。而且本文的優(yōu)化策略之一就是以合理地犧牲record性能來提升get_batch的執(zhí)行效率。因此，get_5000數值對于性能評價才更具實際意義。

從表3可以看出，僅使用python實現時的get_5000高達33ms以上。對照表2，這個數值是本文提出的方法在同等條件下的約100倍。在實際的DQN應用中，如此低效的get_batch往往比計算設備（如GPU等）中模型訓練的實際運算過程還慢，導致計算設備不得不等待訓練樣本的填充，從而拖累整個訓練過程。由此可見，本文利用C++作為處理內核來替代python實現的主要優(yōu)勢在于將get_batch操作的耗時壓縮至原來的百分之一左右，從而避免其成為性能瓶頸，使模型計算設備無須等待訓練樣本的填充，而達到更高的設備利用率。

5?結語

本文設計并實現了一種高效的經驗回放模塊以供DQN相關的應用項目使用，所提出的模塊具有易用性好，通用性、可擴展性高，執(zhí)行性能高等特點。在設計上，該模塊采用兩層結構，底層的功能內核以C++語言實現，以提供較高的執(zhí)行效率，而上層以python語言封裝并對外部應用提供接口，使得基于python編寫的應用項目能夠以面向對象的方式輕松調用。針對經驗回放所涉及的關鍵操作，一些技術細節(jié)被充分研究和精心設計。例如，將優(yōu)先級回放機制作為附屬組件與模塊的主體運行邏輯分離、將樣本的可抽取性驗證提前到record操作中進行、使用高效的記錄淘汰策略與算法等。這些措施使得模塊具有較高的通用性和可擴展性，且整體執(zhí)行效率得到了充分優(yōu)化。本文的實驗分析部分驗證了模塊的實際性能，兩個核心操作record和get_batch皆可被高效執(zhí)行，且與單純使用python實現的常用方法相比，get_batch操作的性能提升約100倍，從而避免在整個DQN相關應用中成為性能瓶頸，滿足了實際應用的需要。

參考文獻 （References）

[1]SUTTON R S. Learning to predict by the methods of temporal differences[J]. Machine Learning， 1988， 3（1）： 9-44.

[2]WATKINS C J C H， DAYAN P. Qlearning[J]. Machine Learning， 1992， 8（3/4）： 279-292.

[3]沙宗軒， 薛菲， 朱杰. 基于并行強化學習的云機器人任務調度策略[J]. 計算機應用， 2019， 39（2）： 501-508. （SHA Z X， XUE F， ZHU J. Scheduling strategy of cloud robots based on parallel reinforcement learning[J]. Journal of Computer Applications， 2019， 39（2）： 501-508.）

[4]SHAKEEL P M， BASKAR S， DHULIPALA V R S， et al. Maintaining security and privacy in health care system using learning based deepQnetworks[J]. Journal of Medical Systems， 2018， 42（10）： 186-186.

[5]MNIH V， KAVUKCUOGLU K， SILVER D， et al. Humanlevel control through deep reinforcement learning[J]. Nature， 2015， 518（7540）： 529-533.

[6]SILVER D， HUANG A， MADDISON C J， et al. Mastering the game of go with deep neural networks and tree search[J]. Nature， 2016， 529（7587）： 484-489.

[7]趙玉婷， 韓寶玲， 羅慶生. 基于deep Qnetwork雙足機器人非平整地面行走穩(wěn)定性控制方法[J]. 計算機應用， 2018， 38（9）： 2459-2463. （ZHAO Y T， HAN B L， LUO Q S. Walking stability control method based on deep Qnetwork for biped robot on uneven ground[J]. Journal of Computer Applications， 2018， 38（9）： 2459-2463.）

[8]ALANSARY A， OKTAY O， LI Y W， et al. Evaluating reinforcement learning agents for anatomical landmark detection[J]. Medical Image Analysis， 2019， 53： 156-164.

[9]ZHU J， ZHU J， WANG Z， et al. Hierarchical decision and control for continuous multitarget problem： policy evaluation with action delay[J]. IEEE Transactions on Neural Networks and Learning Systems， 2019， 30（2）： 464-473.

[10]LIN L J. Selfimproving reactive Agents based on reinforcement learning， planning and teaching[J]. Machine Learning， 1992， 8（3/4）： 293-321.

[11]WULFING J， KUMAR S S， BOEDECKER J， et al. Adaptive longterm control of biological neural networks with deep reinforcement learning[J]. Neurocomputing， 2019， 342： 66-74.

[12]HOCHREITER S， SCHMIDHUBER J. Long shortterm memory[J]. Neural Computation， 1997， 9： 1735-1780.

[13]KIM J J， CHA S H， CHO K H， et al. Deep reinforcement learning based multiAgent collaborated network for distributed stock trading[J]. International Journal of Grid and Distributed Computing， 2018， 11（2）： 11-20.

[14]朱斐， 吳文， 劉全， 等. 一種最大置信上界經驗采樣的深度Q網絡方法[J]. 計算機研究與發(fā)展， 2018， 55（8）： 1694-1705.（ZHU F， WU W， LIU Q， et al. A deep Qnetwork method based on upper confidence bound experience sampling[J]. Journal of Computer Research and Development， 2018， 55（8）： 1694-1705.）

[15]BRUIN T D， KOBER J， TUYLS K， et al. Experience selection in deep reinforcement learning for control[J]. Journal of Machine Learning Research， 2018， 19： 1-56.

[16]YOU S X， DIAO M， GAO L P. Deep reinforcement learning for target searching in cognitive electronic warfare[J]. IEEE Access， 2019， 7： 37432-37447.

[17]LEI X Y， ZHANG Z A， DONG P F. Dynamic path planning of unknown environment based on deep reinforcement learning[J]. Journal of Robotics， 2018， 2018： Article ID 5781591.

This work is partially supported by the Natural Science Foundation of Fujian Province （2016J01294）.

CHEN Bo， born in 1984， Ph. D.， associate professor. His research interests include artificial intelligence， multiAgent simulation.

WANG Jinyan， born in 1995， M. S. candidate. Her research interests include machine learning， multiAgent simulation.