0
雷鋒網按：大牛講堂算法工程師入門系列第二期-穆黎森講增強學習（二），上一講內容主要涉及增強學習基本概念及Deep Q Learning的相關內容，本講除了Deep Q Learning的相關拓展內容、DQN和近期的一些進展。
傳送門：干貨 | 算法工程師入門第二期——穆黎森講增強學習（一）
DQN將一個強大的工具deep neural network 引入RL，解決了這中間遇到的很多新問題，收到了很好的效果。自從這篇工作以后，一方面，大家希望更強的工具能解決更難的問題，比如上面DQN還玩的不是很好的游戲，或者游戲之外的問題；另一方面，大家也希望已經能夠解決的問題能做得更好，更快。近兩年，學術界和工業界做了很多工作，不斷將RL的效果和性能推到新的高度。不論是學術界還是企業界，都認為RL的潛力是很大的。但是在什么時候，能夠以一個合理的代價解決一個現實的應用場景，這個問題目前還處在探索之中。
在這個探索的過程中，最重要的一步，是如何發現現有算法方案的缺陷和短板；其次是以什么樣的思路去解決它；然后是算法的實現與工程細節。這一節中，重點是前兩個方面，特別是第一個：DQN之后，大家都是從什么樣的視角，去不斷改進RL算法的效果的？
連續動作問題
下面是DQN的一個示意圖。
可以看出，這種形式的網絡結構以及loss function的定義，只能處理離散action，即策略需要從N個action中挑選一個的情況。在實際的應用場景中，很多時候，action是多維連續的值，比如機器人控制中各個電機的控制量。在連續action維度非常低的時候，我們可以把連續的值離散化成為幾個區間，然后按照離散action處理；但在action維度較高的情形，這種方法就不適用了。這個時候，顯式的值函數就只能將state，action作為輸入，而無法同時輸出所有action對應的Q值。
所以，我們需要顯式的策略函數：α=π(s) or π(α|s)
接下來要介紹的兩個方法中，既使用了顯式的值函數，又使用了顯式的策略函數，它們可以被歸類為actor critic 方法：
隨著訓練的進行，value function 和 policy 都會得到更新：value function 一般會根據temporal difference迭代更準確的Q值（或者V值，稱為狀態價值state value；相對的，Q為動作價值action value）；policy function會根據value function 以及從環境中收集到的trajectory，迭代更新更好的策略。
Deterministic Policy
第一種思路，策略函數形式為：α=π(s)
也就是確定性的策略。這個方法稱為Deterministic Policy Gradient（DPG）其策略函數輸出一個確定的action，這個action可以是高維連續的。其網絡結構示意為：
Q網絡，即值函數部分，訓練的更新依然通過通過TD loss 來更新；π網絡，即策略函數部分，其更新的梯度方向為使得輸出的action對應的Q值變大，也就是說，loss function為 -Q。具體證明過程在此不展開了。
Stochastic Policy
第二種思路，策略函數形式為：π(α|s)
也就是隨機性策略。對于隨機性策略，Policy function應該輸出action的概率分布。對于連續的action來說，Policy function可以輸出action的概率密度函數。所以，假設action的分布符合多維正態分布：
那么，策略網絡可以輸出正態分布的均值和方差來代表這個分布。于是，關于策略梯度的更新方法就都可以應用在這個策略函數上：只要能構造一個loss function，使得“更好”的action對應的概率密度變高，“更差”的action對應的概率密度變低就可以了。
Action的概率分布符合正態分布這個假設，可以說是一個很強的假設。但是在實際使用當中，這個假設下，在不少問題中是可以得到還不錯的策略的。這個方法在Asynchronous Advantage Actor Critic（A3C）這個工作中有提及，關于A3C，后面還會有介紹。
更好的模型結構
既然使用了model來近似表示希望獲得的策略/價值函數，那么我們總是可以問的一個問題是：有沒有更好的模型來解決我的問題？
在這之前，得首先回答一個問題：什么叫更好的模型？
關于模型（model），有三個互相關聯的特性：
· Non-Linearity，非線性。通常我們希望擬合的真實函數，其輸入到輸出的對應關系是非常復雜的，或者說，具有非常大的非線性。所以模型的非線性是否足夠，決定了最終擬合的結果誤差可以有多小。
· Capacity，容量。即模型的自由度。自由度越高的模型，能擬合的函數的集合就越大，但同時因為搜索空間的變大，訓練的代價就越大；自由度越低的模型，能擬合的函數的集合就越小，相應的，訓練的代價也會變小。
· Computation Cost，計算代價。計算越復雜的模型，其使用以及訓練所消耗的計算資源也越多。
通常情況下，以上三個特性是成正比的。例如，如果對某個神經網絡增加其層數，那么其非線性會增加，可以表示更復雜形狀的函數；其次參數量會增加；最后，其計算代價也會上升。
但是，如果有可能，我們總是希望模型能夠更準確的表示真實函數的同時，盡量不要增大搜索的空間，以及計算復雜度。翻譯一下，就是在增加non-linearity的同時，可以相對減小capacity和computation cost。
如果能面向要處理的問題的特點，有針對性的設計模型結構，是有可能做到這一點的。這就是所謂“更好的模型”。
那么，在RL中，要解決的問題有什么特點呢？以下，舉幾個這方面的例子。
LSTM的應用
我們知道，RNN或者說LSTM，是具有一定的記憶能力的，適合于處理序列的輸入情況。例如語音識別、機器翻譯等領域，LSTM被用來處理語音、句子等序列輸入；或者在計算機視覺（CV）中，用來實現attention 機制，即網絡需要的輸出只和輸入圖像的一部分關系密切的情形。
而以上兩點，在RL中，都存在相似的情形：
例如，在游戲任務中，通常對策略決策比較重要的信息都來自于屏幕上很集中的部分區域。
例如，RL agent和環境交互的過程本身就是個序列過程，而很多時候，agent只能接收到環境的部分信息；agent的當前決策需要依賴于若干步之前收到的信息。這種情況被稱為Partially Observable problem，形式化的描述是可以用LSTM將partially observable markov decision process 轉化為fully observable markov decision process，在此不做展開。
其中，上面第二點可以說是很多RL問題的共性，因此應用也更加廣泛。
Dueling Network
LSTM可以說是其他領域成功應用的模型結構，應用在RL中應對類似問題的例子。那么，在RL中特別是value based method中，神經網絡是用來擬合值函數Q的。值函數Q有沒有什么特有的結構可以被用來設計模型呢？
設想一下：在學習騎自行車這個任務中，假設agent所處的狀態是輪胎與地面成30°角。可以想象，無論這個時候agent采取什么action，多半都會收到一個很糟糕的reward：摔倒在地面上。這里，一個直覺的推斷是：在很多問題下，Q值的一大部分由輸入的state決定；在此基礎上，不同的action會造成小部分的差別；另外一方面，對于策略來說，Q之中僅由state決定的這部分沒有什么作用，更重要的是不同action之間的差別。
這就是Dueling Network的思路：把Q網絡的結構顯式地約束成兩部分之和。
這樣，V的部分只依賴于state，訓練起來更容易；不同action之間的差別只體現在A部分，這部分通常被叫做action advantage。這部分的收斂也可以與V獨立開來，使得action之間的相對差別可以獨立學習。
關于Q值函數形狀的約束假設，還有更激進的工作如NAF（Normalized Advantage Functions），在此不做展開了。
Value Iteration Network
Dueling Network可以說是利用Q值函數的形狀特性。那么Q值迭代的計算過程，是否有特性可以利用呢？
Value Iteration Network這個工作的思路正是如此，其利用了Q值迭代過程和convolution/max pooling 過程形式上的一致性：二維平面狀態空間下，假設每個狀態只能轉移到和其相鄰的狀態中，那么根據bellman equation對平面內所有狀態做一次值迭代的過程，就可以表示成在這個二維圖上的一次卷積操作。這樣，通過若干輪卷積，網絡可以提取出若干步后的所有狀態的Q值，這種look ahead 的行為正是規劃（planning）所需要的。所以，VIN可以用來實現帶規劃功能的策略函數。算法的其余細節不再展開。
更快的收斂速度
我們先比較一下增強學習（DQN）和監督學習的loss function：
可以看出，兩者的loss function 形式上有一定的相似性，都是讓模型的輸出趨近于一個目標值（圖片中紅色的部分）。
對比可以看出，DQN的訓練過程有如下幾個特點。
第一，基礎事實（ground truth）非常稀疏。原因來自于兩方面：
首先，對于不同的任務來說，環境給出的r的密度不一樣，有些任務的r可能會很稀疏，甚至于只有在任務最后成功/失敗的時候才會有非零的r，其余時候r都是0。
其次，監督學習的loss function中，目標值完全來自于外界輸入的正確信息，也就是ground truth。而DQN的loss function中，目標值只有r的部分來自ground truth，另外一部分來自于前一版本的網絡的輸出Q值，這只是一個真實值的近似。
第二，對目標Q值的估計存在偏差。這個偏差正是來自于上面所說的前一版本網絡輸出的Q值上：網絡訓練的過程中，其輸出和真實值可能差距較大；其次，在不準確的Q值基礎上應用操作，會導致估計的Q值系統性地偏大。
第三，DQN這個loss也被稱為1 step TD loss，也就是說，在s'處估計的目標值沿著trajectory倒推一步s'處，用來更新s處的Q值。這樣，transition中<s,a,r,s'>所蘊含的ground truth需要很多輪迭代才能傳播到離和更遠的地方去，得到比較精確的Q值。以下幾個工作，就是針對上面說到的DQN的收斂性問題所做的改進。
Prioritized Experience Replay
在某些任務中，既然對訓練有價值的reward比較的稀疏，那是否可以著重利用這些采集到的reward呢？Prioritized Experience Replay就是基于這個思路，從replay中采樣的時候，提高訓練的時候loss高的transition被采樣到的概率，從而更有效率的學習。
Double DQN
這個工作對目標Q值的計算做了如下的修正：
使得對目標Q值的估計偏高的問題得到了改善：
Optimality Tightening
前面提到DQN的一個問題是1 step td loss在state空間中傳播ground truth太慢的問題。事實上，DQN屬于值方法，而很多策略方法是可以利用N step TD的。為什么DQN不能用呢？因為N step TD是從序列：[r[t], r[t+1], ..., r[t+i]] 計算而來，而從replay buffer中提取出來的trajectory序列可能是根據比較早版本的Q網絡生成的，這就無法真實的反映出最新的target Q網絡的表現情況。而單步td只關心r，而不用關心r的序列，所以不用擔心生成這個序列的策略和當前策略不一樣的問題。更詳細的分析可以去了解一下on-policy和off-policy的相關概念。
Optimality Tightening 這個工作的思路是，雖然不能直接用N step TD來計算當前的目標Q值，但是用來給當前Q目標值加一個上下界的約束：
這樣，相當于在DQN里面，應用上了N step TD的信息，讓ground truth 沿著trajectory的軌跡傳播得更快。
更好的探索策略
探索是RL的重要話題。想象人類學習玩游戲的過程，在游戲的開始，玩家會嘗試一些操作；并逐漸掌握一些基本的策略，完成簡單的挑戰；然后根據這些策略，達到離初始狀態較遠的狀態，然后不斷探索嘗試面臨的新的挑戰。在RL中也是如此，一方面，策略需要保持一定的探索以發現新的策略；另一方面，策略需要利用之前學到的知識，才能保證探索的時候更有效率。
在DQN中，????????方法是一種比較基礎的探索策略，是在greedy策略（選取Q值最大的action）基礎上，以一定比例加入隨機選擇的action而來。通過調整?的大小，可以控制隨機探索與應用現有策略之間的比例。
但是，在稍復雜一些的問題下，????????是一種比較低效的探索方法。因為很顯然，在?值也就是隨機的比例一定的情況下，Agent到達某個狀態s的幾率，隨著s離初始狀態距離的增加是成指數級降低的。我們需要除了簡單的隨機策略以外，更加有效的探索方式。
Intrinsic Rewards
既然RL的訓練過程會讓agent的策略傾向于盡可能多地收集累積回報，那我們是不是可以自己構造回報函數，來指導agent的探索呢？
這是一種比較通用的辦法。即在agent收到的環境reward之上，加入自己設計的intrinsic reward，指導agent趨向于這個reward所指引的方向。至于如何構造這個intrinsic reward，不同的工作有不同的思路，這里僅舉一個例子：
即構造一個專門的網絡來預測環境的transition model；這個transition model跟著策略/值網絡一起訓練，只是以更慢的學習速度進行。那么這個transition model預測環境變化的準確度高的state，就認為agent已經很熟悉這個state了；反之，就認為這個agent對當前所處的環境不是很熟悉。所以，就是用transition model的training loss 來當做intrinsic reward。這個training loss的方法被形象地稱為Curiosity Driven Exploration。
Deeper Exploration
前面提到，簡單的隨機策略會讓agent很難到達離初始狀態較遠的狀態，就像布朗運動很難遠離原點一樣。這樣的探索是一種很“淺”的探索，那如何讓探索更深呢？直觀的想法是減少隨機性，以避免在初始狀態原地打轉的情況；但隨機性太小的話，又會導致agent采集到的transition趨同，不利于訓練。如何來平衡這兩點呢？
假設有一個團隊來執行探索迷宮的任務。其中A喜歡貼著右邊墻走；B喜歡貼著左邊墻走。那每次探索，團隊都派不同的人出去執行任務，是不是就可以實現每個人都深入到迷宮的不同部分了呢？
Bootstrapped DQN這個工作所采取的思路是這樣的：
每個head都是一組Q值；每個Episode僅根據一個head的Q值做greedy的探索，直到下一個Episode，再隨機選取一個head執行探索。這樣，每個episode都會依據某一個head的策略執行到底，保證了探索的一致性和深入；同時，只要能保持不同head之間的多樣性，從統計上來看，探索得到的transition也比較多樣化。
Hierarchical RL
我們知道，人是有比較強的信息抽象能力的。對于數據的抽象，深度的神經網絡也具備相似的能力，可以從高維度的、低層次的輸入數據（比如圖像），提取出低維度的，高層次的信息（比如圖片里有一只喵的概率）。但是對于行為來說，人同樣是具有很強的抽象能力的：可以從高維度、低層次的行為的基礎上，逐漸建立出低維度、高層次的行為。
舉一個例子，需要完成的任務是通過鍵盤猜測兩位數的密碼。正常的人類在完成這個任務的時候，其實際需要探索的狀態空間只有102個狀態，也就是兩位數密碼的所有組合；而按照普通的RL方法，agent輸出機械臂的所有控制信號來敲鍵盤的話，其探索的狀態空間是一個大得多的高維空間。
這就是層次式RL：Heirarchical RL的出發點：把策略（或者動作）本身劃分為不同的層次，底層的策略負責完成一些底層的任務；上層的策略負責把底層策略結合起來，完成更復雜的任務。這樣，無論上層策略還是底層策略，其探索空間都大大減小。
通常，Heirarchical RL會把策略分為至少兩層，上層的策略負責輸出底層策略的階段性目標，稱為goal或者option；然后底層策略在一定的時間周期內，負責實現這個目標。上層策略可以在此期間，負責輸出reward給底層策略，用來評價底層策略的執行情況。
屬于這類的工作有很多，在此就不一一舉例了。
向專家學習
在RL的框架下，agent可以從零開始，探索環境，逐漸學習得到越來越好的策略。由于前面提到的各種原因，對比監督學習來說，RL是個相對較慢的過程。
反觀人類學習某項任務的過程：人類具有很強的模仿能力，如果在學習的過程中，有老師示范的話，人類的學習速度將會大大提升。那是否可以讓RL中的agent，也能像人類一樣，從專家的行為中學習呢？
一個傳統的思路是Inverse RL：給出專家在完成任務的一些例子，先對環境的reward做出假設：R(s, a)；然后設法求出使得專家的例子收到的獎勵最大化的R(s, a)，再反過來用R(s, a)指導agent的訓練。通常這樣的R(s, a)返回的獎勵是比環境本身的獎勵要更稠密的，所以在R的指導下，agent學習會更快。
這種方法比較間接。還有更直接的做法：imitation learning，即設法讓agent的策略輸出和專家的輸出更接近。Imitation learning也有很多做法，這里就舉一個例子：
熟悉深度學習近期進展的同學能看出來，這是一個對抗學習（Generative Adversarial Network，GAN）的結構。在Generative Adversarial Imitation Learning這個工作里面，通過對抗學習，使得generator也就是policy輸出的trajectory的分布，盡量靠近專家的trajectory 的分布。然后可以再放進RL的框架下，進一步學習得到更好的策略。
分布式算法
RL的訓練過程是很慢的。一個很花時間的程序，設法改成分布式以加速，是個很自然的想法。
那么，RL訓練過程中，哪些部分可以并行化呢？
GORILA
上圖來自于Google Reinforcement Learning Architecture（Gorila）這個工作。我們會發現，只要有需要，RL過程中的各個部分皆可并行化：
· Environment：不同的環境實例之間相互獨立；
· Agent：Agent與environment一一對應，只與自己的environment交互，所以也可以并行；
· Replay Memory：當需要存儲超過單機容量的replay的時候，可以用多機存儲； learner, parameter, agent。
· Learners：不同的learner可以獨立地從experience replay中采樣數據并計算梯度，類似于監督學習中的數據并行；
· Parameters：如果網絡規模比較大，那么可以用多機來保存和更新網絡參數，類似于監督學習中的模型并行。
A3C
如果系統的部署規模還沒有到google這么大，那么Asynchronous Methods for Deep Reinforcement Learning這個工作比較值得關注：
從架構上來說，比Gorila要簡單。細節先不展開了，這里有一個比較有意思的結論：
我們看到，當把單機的算法改成分布式之后，有些算法獲得了超過1的加速比。這個在分布式計算中并不常見，因為單機的算法很可能有一部分是沒法并行化的，同時并行化還帶來了通訊和調度的開銷。
原因在于，多個agent同時探索，往往會探索到environment的不同狀態。這樣，在訓練的時候，采樣得到的訓練數據之間相互的獨立性會更強。所以分布式訓練除了利用了更多計算資源以外，對RL而言對于訓練時候的樣本獨立同分布還有額外的好處。
文中提到的asynchronous advantage actor-critic, A3C算法是一個效果比較好的算法，值得感興趣的同學關注一下。
多任務和遷移
遷移學習不是一個新的話題。模型的訓練是一件花時間的事情；人們希望訓練好一個模型以后，能讓這個模型能完成不同的任務，或者至少對訓練其他任務的模型有所幫助。在RL的領域，多任務和遷移的話題變得越來越重要，原因包括：
· 在現實的場景中，agent需要面臨的情況是很復雜的，可能不時會有新的情況發生；如果能讓agent學會處理新的情況速度大大加快，無疑是很有價值的。
· 我們知道，虛擬的Environment的執行和探索的成本很低，而在真實的物理世界里探索成本非常高。但是通常，虛擬環境和真實環境總會有一些差異。如果能有辦法幫助在虛擬環境里訓練好的agent更快地適應真實環境的話，就可以讓在虛擬環境中訓練、在實際場景下使用變得更加容易。
· 即使是完成單個任務，任務本身可能也有一些結構值得探索，就像在Hierachical RL一節所思考的一樣。那么，將多任務的一些方法應用在單個任務的訓練中，也可以起到加快訓練的作用。
Target Driven Navigation
有一個完成單一任務的程序，現在想讓它能完成更多任務？
從軟件工程的角度，最直接的辦法是把要完成的任務，也當成程序輸入的一部分。這也是Target driven visual navigation in Indoor Scenes using deep RL這個工作的思路。
Progressive Neural Networks
上述方法要求任務之間具有比較強的一致性。如果還是希望分別訓練多個網絡對應多個任務呢？
這篇工作的思路是，讓已經訓練好的網絡也參與到新的任務網絡的訓練過程中：因為已經訓練好的網絡所具有的信息抽取的能力，可能對新的任務有一定的參考價值。
Elastic Weight Consolidation
那么，是否真的就不能讓同一個agent或者說網絡，具有完成多個任務的能力呢？
從訓練的角度來講，一個神經網絡在兩個task下表現好，就意味著這個網絡的參數對于兩個task對應的loss 都比較低。也就意味著，在訓練好task A以后，在訓練task B的時候，希望能保留對task A重要的參數，只改變對task A不重要的參數，來尋找能完成task B的策略。參數對task的重要程度，正好有個直接的衡量標準：即訓練這個task的時候，loss對參數的梯度。這樣，只要調低對task A重要的參數的學習率，就能讓網絡不會“忘記”task A。
RL with unsupervised auxiliary tasks
如果是人類來學習完成某項任務的話，人類不會僅僅習得在某種state下應該執行某個action，而是會逐漸掌握這個任務的環境的一些一般規律，并利用這些知識，更快地習得更魯棒的策略。
在這個工作中，除了主要的訓練流程之外， 還加入了幾個輔助的任務，來預測收集到的reward、迭代值函數、控制像素的變化情況，等等。這些輔助的任務和主任務之間，共享一部分網絡機構。一個很合理的直覺是：一個能很好從環境中預測收到的reward的網絡，它從state中提取出來的信息也對完成這個任務非常有用。
Curriculum Learning
人類在學習某項技能的時候，如果先從簡單的情形開始學起，循序漸進提高難度，那么學習很容易很多，這就是所謂的學習曲線。相同的思路應用在RL上，就是課程表學習：
以上是個玩射擊游戲的例子，不同的class 實際上是不同難度的同一個任務。Class 0是最容易的，意味著更容易收集到有意義的reward，所以訓練起來比較容易；能順利完成class 0的agent，相比未經訓練的agent來說，在class 1里面收集到reward的難度要低，所以訓練起來也比較容易，以此類推，就能逐漸完成我們最終設定的任務。
后記
可以看出，上述的各種進展，是用新的手段，解決更復雜的任務，同時不斷定位問題并解決改善的過程。由于篇幅和角度所限，不少近期的進展并沒有覆蓋到；同時，上述所有的工作所聲稱要解決的問題，還遠未達到解決得很好的程度，他們各自起作用也有一些假設和作用范圍，所以這些問題都還是開放性的話題。相信不久的將來，RL的進展會體現在更多的實際應用場景中，甚至催生出很多新的產品形態，這也是學界和業界共同努力的方向，讓我們拭目以待。
（回顧上一講內容敬請關注《大牛講堂》專欄）
雷峰網特約稿件，未經授權禁止轉載。詳情見轉載須知。
