OpenAI詳解進化策略方法：可替代強化學習
進化策略(ES：evolution strategy)是一種已存在了數十年的優化技術，其在現代強化學習基準(如 Atari/MuJoCo)上的表現可以比肩標準的強化學習技術，同時還能克服強化學習的許多不便。
特別的幾點包括：進化策略的實現更加簡單(不需要反向傳播)，更容易在分布式環境中擴展，不會受到獎勵稀疏的影響，有更少的超參數。這個結果令人吃驚，因為進化策略就好像是在一個高維空間中簡單地爬山，每一步都沿著一些隨機的方向實現一些有限的差異。
我們的發現是這種已有數十年之久思想強大結果的現代延續。比如說，在 2012 年，AlexNet 論文表明可以如何設計、擴展和訓練卷積神經網絡(CNN)以在圖像識別任務上實現極其優秀的結果，而那時候大多數研究者還認為 CNN 并不是一種有希望的計算機視覺技術。類似地，在 2013 年，深度 Q 學習(Deep Q-Learning)論文表明可以將 Q 學習與 CNN 結合起來以成功地解決 Atari 游戲，從而使強化學習(RL)發展成為了一個有激動人心的實驗結果的研究領域，而不再只是理論構想了。同樣，我們的研究也表明進化策略可以在強化學習基準上實現優秀的表現，從而消除了人們之前普遍認為的進化策略方法不能用于高維問題的觀點。
進化策略易于實現和擴展。我們的實現運行在一個包含了 80 臺機器和 1440 個 CPU 內核的計算集群上，其可以僅在 10 分鐘內就訓練出一個 3D MuJoCo 人形步行者(在 32 核上，A3C 需要大約 10 小時)。使用 720 核，我們也能在 Atari 上實現可與 A3C 媲美的表現，同時還能將訓練時間從 1 天降低至 1 小時。
下面，我們將首次簡要描述傳統的強化學習方法與我們的進化策略方法的對比，還會討論進化策略和強化學習之間的權衡，最后還會突出介紹我們的一些實驗。
一、強化學習
首先讓我們簡單看看強化學習的工作方式。假設我們有一些環境(比如游戲)，我們想要在其中訓練一個代理。為了描述該代理的行為，我們要定義一個策略函數(policy function)，這是該代理的大腦，用于計算該代理如何在一個給定的情形中采取行動。在實踐中，這個策略通常是一個神經網絡，其輸入是該游戲的當前狀態，然后計算可用的所有允許動作的概率。一個典型的策略函數可能有大約 1,000,000 個參數，所以我們的任務就是找到這些參數的確切配置，以使得該策略能夠實現良好的表現(即在很多游戲中獲勝)。
上圖：在 Pong 游戲中，策略根據輸入的屏幕像素來計算移動玩家拍子的概率(右邊綠色的拍子)：上、下或不動。
該策略的訓練過程如下所示。首先是一個隨機初始化，我們讓該代理與環境進行一陣交互，然后收集交互的「劇情(episode)」(比如，每個 episode 就是一局 Pong 游戲)。由此我們就能得到情況的完整記錄：遇到了什么樣的狀態序列、在每個狀態采取了什么動作、每一步的獎勵如何。下圖給出了一個例子，這三個 episode 每個都表示在一個假想環境中的 10 個時間步驟。其中每個矩形都是一個狀態，如果獎勵是正面的(比如把球擊回給了對方)，那么矩形就是綠色;如果獎勵是負面的(比如沒有接到球)，那么矩形則為紅色：
這幅圖給出了改善策略的一個方法;導致綠色狀態的行為是好的行為，導致紅色的行為則很糟糕。然后我們可以使用反向傳播來計算該網絡參數的一次小的更新，該更新將使得未來的狀態更有可能是綠色、更少可能是紅色。我們預計更新后的策略會更好一點。然后我們迭代這一過程：收集另一批 episode，進行另一次更新……
通過在這些動作中注入噪聲來進行探索。我們在強化學習中通常使用的策略是隨機的，它們僅計算采取任何動作的概率。通過這種方法，代理可能會在訓練過程中發現自己在不同時間處在同一個特定狀態，而且由于采樣的情況，它也將在不同的時間采取不同的動作。這能提供學習所需的信號：這些動作中有一些會導致好的結果，這些動作就會得到鼓勵;另一些則不會奏效，就會被抑制。因此我們可以說，我們通過向代理的動作注入噪聲而為其學習過程引入了探索(exploration)——我們可以通過在每個時間步驟從動作分布中采樣來做到這一點。這與進化策略不同。
二、進化策略
關于「進化(Evolution)」。在我們探討進化策略(ES)之前，有必要強調一下盡管這種方法名字中有「進化」這個詞，但進化策略和生物進化關系不大。也許這項技術的早期版本從生物進化上獲得了一些啟發——在一定的抽象程度上，這種方法可被視為這樣一個過程：從個體構成的群體中采樣并讓其中成功的個體引導未來后代的分布。但是，其數學細節在生物進化方法的基礎上實現了很大的抽象，我們最好將進化策略看作是一類黑箱的隨機優化技術。
黑箱優化。在進化策略中，讓我們完全忘記代理、環境、涉及的神經網絡和其中的交互吧。進化策略的整個設置就是一大堆數字輸入(假設和前面提到的策略網絡的參數數量一樣，有 1,000,000 個數字)，然后輸出 1 個數字(對應總獎勵)，我們需要找到這 1,000,000 個數字的最好配置。在數學上，我們可以說是根據輸入向量 w(該網絡的參數/權重)來優化一個函數 f(w)，但我們不對 f 的結構做出任何假設，我們只能對其進行評估(因此被稱為「黑箱」)。
進化策略算法。直觀上來講，這種優化就是一種「猜測然后檢測」的過程，即我們從一些隨機參數開始，然后重復執行以下過程：1)隨機對該猜測進行一點調整，2)讓我們的猜測向效果更好的方向移動一點。具體而言，就是在每個步驟輸入一個參數向量 w，然后通過高斯噪聲對 w 進行抖動來生成一群(比如 100 個)有稍微改變的參數向量 w1, w2……w100。然后我們在環境中分別運行這 100 個候選項所對應的策略網絡，從而獨立地對這 100 候選項分別進行評估，然后將每個案例中的獎勵加起來。然后其更新后的參數就變成了這 100 個向量的加權和，其中每個權重都正比于其總獎勵。(即，我們想讓更成功的候選項有更高的權重。)在數學上，你也會注意到這就相當于使用有限差分法(finite difference)來估計參數空間中預期獎勵的梯度，只是我們是沿著 100 個隨機方向來做的。
我們要看的另一種方法是仍然使用強化學習(策略梯度，具體來說是 REINFORCE)，其中的代理的動作是使用高斯策略得出整個參數向量。
上圖：進化策略優化過程，這個環境中只有兩個參數和一個獎勵函數(紅色=高、藍色=低)。在每次迭代，我們都會展示當前參數值(白色)、一群經過抖動的樣本(黑色)和估計的梯度(白色箭頭)。我們不斷將該參數移動到該箭頭的頂點，直到我們收斂到了一個局部最優值。你可以使用本文的代碼重現這些圖。
代碼示例。為了得到具體的核心算法并突出其簡潔性，這里給出了一段使用進化策略優化二次函數的短代碼實例(更長的版本見文末鏈接)。
- # simple example: minimize a quadratic around some solution point
- import numpy as np
- solution = np.array([0.5, 0.1, -0.3])
- def f(w): return -np.sum((w - solution)**2)
- npop = 50 # population size
- sigma = 0.1 # noise standard deviation
- alpha = 0.001 # learning rate
- w = np.random.randn(3) # initial guess
- for i in range(300):
- N = np.random.randn(npop, 3)
- R = np.zeros(npop)
- for j in range(npop):
- ww_try = w + sigma*N[j]
- R[j] = f(w_try)
- A = (R - np.mean(R)) / np.std(R)
- ww = w + alpha/(npop*sigma) * np.dot(N.T, A)
向參數中注入噪聲。注意這里的目標與強化學習優化的目標是一樣的：預期的獎勵。但是，強化學習是將噪聲注入動作空間并使用反向傳播來計算參數更新，而進化策略則是直接向參數空間注入噪聲。換個說話，強化學習是在「猜測然后檢驗」動作，而進化策略則是在「猜測然后檢驗」參數。因為我們是在向參數注入噪聲，所以就有可能使用確定性的策略(而且我們在實驗中也確實是這么做的)。也有可能同時將噪聲注入到動作和參數中，這樣就有可能實現兩種方法的結合。
三、進化策略和強化學習間的權衡
相比于強化學習算法，進化策略有多個優勢(一些優勢有些技術性)：
1. 不需要反向傳播。進化策略只需要策略的前向通過，不需要反向傳播(或價值函數評估)，這使得代碼更短、在實踐中速度快了 2-3 倍。在內存有限的系統中，也不需要保留 episode 的記錄從而進行后續的更新。我們也不需要擔心 RNN 中的梯度爆炸問題。最后，我們能夠探索更大類別的策略函數，包括不可微分的網絡(比如二值網絡)，或者包括復雜模塊的網絡(例如包括 pathfinding 或多種優化層)。
2. 高度可并行。進化策略只需要工作器彼此之間進行少量純數量的通信，然而在強化學習中需要同步整個參數向量(可能會是百萬數值的)。直觀來看，這是因為我們在每個工作器(worker)上控制隨機 seeds，所以每個工作器能夠本地重建其他工作器的微擾(perturbations)。結果是，在實驗中我們觀察到，隨著我們以千為單位增加 CPU 進行優化時，有線性的加速。
3. 高度穩健。在強化學習實現中難以設置的數個超參數在進化策略中被回避掉了。例如，強化學習不是「無標度(scale-free)的」，所以在 Atari 游戲中設置不同的跳幀(frame-skip)超參數會得到非常不同的學習輸出。就像我們所展現的，進化策略在任何跳幀上有同樣的結果。
4. 架構探索。一些強化學習算法(特別是策略梯度)用隨機策略進行初始化，這總是表現為在一個位置有長時間的隨機跳躍。這種影響在 Q 學習方法中因為 epsilon-greedy 策略而有所緩和，其中的 max 運算能造成代理暫時表現出一些一致的動作(例如，維持一個向左的箭頭)。如果代理在原地跳動，在游戲中做一些事情是更有可能的，就像策略梯度的例子一樣。類似于 Q 學習，進化策略也不會受這些問題的影響，因為我們可以使用確定性策略來實現一致的探索。通過研究進化策略和強化學習梯度評估器，我們能看到進化策略是一個有吸引力的選擇，特別是在 episode 中的時間步驟量很長的時候，也就是動作會有長時間的影響。或者是在沒有好的價值函數評估的時候進化策略也是好的選擇。
對應地，在實踐中我們也發現了應用進化策略的一些挑戰。一個核心問題是為了讓進化策略工作，在參數中加入噪聲必然會導致不同的輸出，從而獲得一些梯度信號。就像我們在論文中詳細說明的，我們發現使用虛擬 batchnorm 能幫助緩和這一問題，但在有效地參數化神經網絡上還有進一步的工作要做，從而有不同的行為作為噪聲的功能。還有一個相關的困難，我們發現在 Montezuma’s Revenge 游戲中，用隨機網絡很難在一級的時候得到鑰匙，然而用隨機動作能偶爾獲得鑰匙。
四、進化策略可媲美于強化學習
在兩個強化學習基準上我們對比了進化策略和強化學習的表現：MuJoCo 控制任務和 Atari 游戲。每個 MuJoCo 任務(看以下示例)包含一個模擬身體的鉸接式人物，策略網絡獲得所有關節的位置信息，需要輸出每個關節的力矩(torques)從而前行。以下是在三個 MuJoCo 控制任務上訓練的代理示例，任務目標是前行。
我們通常觀察學習數據的效率來對比算法的表現。作為我們觀察到的多少狀態的函數，什么是我們的平均獎勵?以下是我們獲得的學習曲線，與強化學習進行了對比(在此案例中用的是 TRPO 強化學習算法，參考 https://arxiv.org/abs/1502.05477):
數據學習效率對比。以上對比表明進化策略(橘黃)有著與 TRPO 算法(藍色)相媲美的表現，盡管在所有情況下它不完全匹配或超越 TRPO 算法。此外，通過水平掃描我們可看到進化策略效率略低，但不低于 1/10(注意橫坐標是指數標度)。
時間對比。取代觀察看到的狀態原數量，我們可以認為要觀察的最重要的標準是時間：解決一個問題需要多久(以秒為計)?這一數值最終指示了一個研究人員可完成的迭代速度。因為進化策略算法需要的工作器(worker)之間的通信幾乎可以忽略，我們能夠使用 80 臺機器上的 1440 個 CPU，10 分鐘就解決最難的 MuJoCo 任務(3D 人形)。作為對比，在典型的一臺機器上 32 個 A3C 工作器配置中，解決該任務需要 10 小時左右。用算法與工程上的努力，當然也能改進強化學習的表現，但我們發現在標準的云 CPU 環境中單純延展 A3C 非常難，因為需要高通信帶寬。
以下是用進化策略訓練的 3D 人形任務行走的動圖。就像我們所看到的，根據優化最終收斂到的局部最優值，結果挺多樣的。
在 Atari 游戲中，用 1 小時在 720 核上訓練進化策略取得了的表現可媲美于在 32 核上訓練一天的 A3C。下面是在 Pong、Seaquest 和 Beamrider 游戲中的結果片段。這些片段顯示了預處理的畫面，也就是代理在玩游戲時所看到的：
特別要注意 Seaquest 游戲中的潛水艇在氧氣值低的時候學習準確率會上升。
五、相關研究
進化策略是源自神經進化系的算法。神經進化在人工智能中有著很長的歷史，完整文獻原因超出本文所覆蓋的范圍。我們鼓勵感興趣的讀者查閱 Wikipedia、Scholarpedia 的相關文獻，以及 Jurgen Schmidhuber 的回顧文章(Section 6.6)。最影響我們研究的一項工作是 Wierstra 等人在 2014 年作出的自然進化策略(Natural Evolution Strategies)。相比于該工作以及它所啟發出的其他工作，我們專注于將這些算法延展到大規模的、分布式環境中，尋找讓這些算法能與深度神經網絡很好結合的組件，并在現在的強化學習基準上評估這些算法。
還值得注意的是神經進化相關的方法最近在機器學習研究中有所復蘇(resurgence)，例如 HyperNetworks、Large-Scale Evolution of Image Classifiers 和 Convolution by Evolution。HyperNetworks,「Large-Scale Evolution of Image Classifiers」和「Convolution by Evolution」.
六、結論
我們的研究表明神經進化方法在現在的代理-環境基準上，可與強化學習的方法相媲美，同時在代碼復雜性上也有重大收益、易于延展到大規模分布式環境。我們也期望通過重新回顧這條線上的其他觀點從而作出更多激動人心的工作，比如間接編碼方法，或者除了參數以外用其他方法進化網絡架構。
注意監督學習：要注意的一點是監督學習問題(例如圖像分類、語音識別或者產業中的大部分其他任務)并不受這些成果的直接影響。監督學習可以用反向傳播方法直接計算損失函數的確切梯度。例如，在初步試驗中我們使用進化策略在 MNIST 數字識別任務上評估梯度，發現它要比使用反向傳播的方法慢 1000 倍。只有在強化學習環境中，也就是必須要用采樣評估預期獎勵(expected reward)的梯度，進化策略才具有可比性。
代碼發布：最后，如果你想要嘗試運行下進化策略，你可以閱讀以下論文，或了解 GitHub repo 的詳細細節。
論文：
https://arxiv.org/abs/1703.03864
Github：
https://github.com/openai/evolution-strategies-starter
【本文是51CTO專欄機構機器之心的原創譯文，微信公眾號“機器之心( id: almosthuman2014)”】
