一種高效的經(jīng)驗回放模塊設(shè)計

陳勃 王錦艷

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

關(guān)鍵詞：強化學(xué)習(xí);深度學(xué)習(xí);深度Q網(wǎng)絡(luò);經(jīng)驗回放;軟件設(shè)計

中圖分類號：TP302

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

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

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

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

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

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

1?經(jīng)驗回放模塊的接口形式

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

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

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

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

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

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

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

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

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

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

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

在以上實體概念的基礎(chǔ)上，定義經(jīng)驗回放模塊應(yīng)當(dāng)支持的主要操作方法有：

1） new_episode（）。建立一個新的episode，并返回其對應(yīng)的句柄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標(biāo)識的episode中追加一條完整的record，即一個state、action、reward的組合。final_state是一個可選項，若傳入final_state則指示該回合以狀態(tài)final_state結(jié)束。

4） get_batch（batch_size， h_ps）。用以句柄h_ps標(biāo)識的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的形狀多出兩維，呈現(xiàn)為（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的向量。如前文所述，由于某些抽取準(zhǔn)則中可能允許抽取不足pick_len長度的pick，故需要用seq_len和seq_len_next分別反饋batch_state和batch_state_next中每個pick實際有效的時間序列長度。這樣，抽取出的數(shù)據(jù)中長于這些實際長度的部分才可以被外部的應(yīng)用所忽略。batch_pick_epi和batch_pick_pos分別是pick_epi和pick_pos的向量，長度也為batch_size。它們用于標(biāo)識所抽取的每個pick的來源，以便set_priority方法反饋更新其優(yōu)先級。

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

6） serialize（）。序列化導(dǎo)出經(jīng)驗回放模塊的數(shù)據(jù)，用于持久化保存經(jīng)驗池。

7） unserialize（）。反序列化，用于從保存的持久化數(shù)據(jù)中恢復(fù)經(jīng)驗回放模塊。

2?經(jīng)驗回放模塊的架構(gòu)設(shè)計

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

2.1?功能內(nèi)核（C++）

功能內(nèi)核進一步分為函數(shù)接口層和數(shù)據(jù)結(jié)構(gòu)層，前者用于實現(xiàn)內(nèi)核的主要功能，并為python實現(xiàn)的包裝類提供函數(shù)接口，而后者則包含關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，以及一些底層的算法步驟。

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

batch_maker結(jié)構(gòu)體在對經(jīng)驗數(shù)據(jù)進行采樣抽取操作時至關(guān)重要，其中主要包含兩個成員向量：pick_table與ps_table。

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

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

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

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

2.2?包裝類（python）

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

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

其次，對于數(shù)據(jù)形式的轉(zhuǎn)換主要有兩個任務(wù)：

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

2） python數(shù)據(jù)類型與C數(shù)據(jù)類型轉(zhuǎn)換。內(nèi)核接口使用C語言風(fēng)格的數(shù)據(jù)類型和數(shù)據(jù)訪問方式，而應(yīng)用層卻需要以python風(fēng)格的數(shù)據(jù)類型存儲和使用數(shù)據(jù)，ExperienceReplay中為此進行了必要的轉(zhuǎn)換。例如，較為復(fù)雜的get_batch操作對應(yīng)的內(nèi)核函數(shù)接口形式為：

程序前

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）;

程序后

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

程序前

batch_action=

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

程序后

上述數(shù)據(jù)類型的轉(zhuǎn)換，使得應(yīng)用層可以完全使用python風(fēng)格的數(shù)據(jù)類型和數(shù)據(jù)訪問方式，而無需關(guān)注底層較為復(fù)雜繁瑣的實際數(shù)據(jù)交互，大大增強了模塊的易用性。

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

程序前

new_pick_selector（PickSelectorClass.X）

程序后

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

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

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

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

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

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

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

1）調(diào)用pick_selector的select接口，以選取batch_size個pick在pick_table中的位置，記作數(shù)組pick_index。

2）依據(jù)pick_index，在pick_table中取得pick的訪問位置信息，即batch_size個有序?qū)Α磒ick_epi， pick_pos〉。

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

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

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

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

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

record操作的基本流程為：

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

2）將新的record數(shù)據(jù)寫入上述episode。

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

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

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

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

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

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

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

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

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

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

① 從e的pick_index向量中依次查找下一個pick在pick_table中對應(yīng)索引的位置i，若已達pick_index的結(jié)尾，則跳轉(zhuǎn)到步驟⑧;

② 若j ≥ 0，則設(shè)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]數(shù)據(jù)交換;

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

⑧ 刪除pick_table中位于j之后的數(shù)據(jù);

⑨ 從episodes中刪除e。

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

4?性能測試與討論

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

每次實驗中，模擬一個假設(shè)的數(shù)據(jù)記錄（record）與樣本抽?。╣et_batch）過程。首先，假設(shè)有來自2k個回合的數(shù)據(jù)，每個回合含有2s條隨機生成的記錄，故總計數(shù)據(jù)規(guī)模為N=2k+s條記錄;然后，將這些記錄利用record操作逐條添加進空的經(jīng)驗池，統(tǒng)計這一過程耗費的時間，計算出平均每100次record操作的時間開銷，記作統(tǒng)計量record_100;接著，對這個經(jīng)驗池進行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)計量。為避免計算機在運行測試時由于不可預(yù)期的原因（如后臺運行的其他程序等）造成統(tǒng)計誤差，上述實驗反復(fù)進行了5次。對于每個統(tǒng)計量，皆取得5次實驗的最小值，得到的結(jié)果數(shù)值如表1、2所示。

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

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

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

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

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

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

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

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

5?結(jié)語

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

參考文獻 （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]沙宗軒， 薛菲， 朱杰. 基于并行強化學(xué)習(xí)的云機器人任務(wù)調(diào)度策略[J]. 計算機應(yīng)用， 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]. 計算機應(yīng)用， 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]朱斐， 吳文， 劉全， 等. 一種最大置信上界經(jīng)驗采樣的深度Q網(wǎng)絡(luò)方法[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.