對Reinforcement Learning中的小無相功和九陽神功的一些參悟

又到了一年一度的冬月初七，預祝大家冬月初八快樂！

本文是我上周和本周主要看的幾篇文章的一些總結和粗鄙的見識。主要cover一下三篇文章：

-《Learning to Act by Predicting the Future》 - ICLR 17

-《Opponent Modeling in Deep Reinforcement Learning》 -ICML 16

-《Universal Value Function Approximators》 - ICML 15

接下來會按照我讀的順序，進行一些總結。

主要是對——「對不同的對手opponent/任務task/目標goal，如何進行泛化generalization或者遷移transfer」的一些思考。或者說，對小無相功，或者九陽神功的參透之路。

個人覺得這幾篇存在著一些潛在的聯繫，也是我把這三篇放在一起的原因。

人菜圖渣，多多包涵。

正文

1. 《Learning to Act by Predicting the Future》

最開始看到這篇文章，是在調研DRL@VideoGames時，第一人稱射擊遊戲（FPS）DOOM系列裡看到的，並且本文中的方法Direct Future Prediction (DFP) 也在Visual Doom AI Competition 2016 中的 full deathmatch competition 拔得頭籌，並且已更簡單、更直觀的方法，更少的遊戲內部數據的獲取，performance甩開了第二名DRQN (full/limited deathmatch的雙料亞軍) 超過50%。

-《Playing FPS games with deep reinforcement learning》

雖然這篇文章很酷，但是最開始並沒有關注，因為粗看了一眼，發現DFP用的是SL的方法在教agent打槍。而之後發現，其實DFP是在用SL的方法做RL做的事情。也正如這篇博客里說的（這篇博客里也提到了keras對DFP的復現，然而只是部分實驗）。

1.1 RL v.s. SL

就我淺薄的理解而言，這篇文章主要的idea是——「如果環境提供的是sparse scalar reward，那RL通常比SL更適合這類問題；如果環境能夠給dense multidimensional feedback，那麼SL可能更好」。

所以基於這一點，結合DOOM遊戲，一般的做法是把raw pixels加上additional information (health, ammo, frags) 作為state，然後用reward，用RL指導agent的學習。然而在DOOM中，health, ammo, frags這類measurements，也可以認為是dense的feedback，且我認為很重要的一點是，這寫measurements是直接和我們訓練的目標 (goal) 相關的。所以，本文提出了DFP，直接預測未來measurements的SL方法。

1.2 goal-direct

傳統的RL中，或者在其他DOOM的方法中，我們可以看到，是reward在指導agent訓練的目標。或者說，我們希望得到什麼樣的agent，就用specific reward shaping來達到這個目的。比如，我希望我的agent能積極地探索環境（為了有可能撿更多的血包，彈藥包，遇到更多的敵人擊殺），那我就在agent的位移上做reward shaping，如果兩個狀態之間，agent的位移小於閾值，我就給penalty。諸如此類。

而用SL去做RL做的事，用什麼來表達我的訓練目標，用什麼來指導agent學習，是一個問題。SL基於強的監督信號。在本文中，DFP方法的SL模型，在input stream里加入一個goal stream (goal vectors)，實際上，使用這個goal vector指導SL agent學習到某個目標。

先看一下DFP model的architecture:

可以看到input是三個流，image S(s), Measurements M(s), Goal G(g)，輸出是對每一個action的future measurements。形式化表示成：

用回歸loss來訓練model：

也就是我輸入s,m,g，得到我對每一個action a的future measurements。這個future measurements是未來一些時刻偏移的measurements與當前時刻t的measurements的差值的向量，如下：

正如我們上文所言，這個measurements是health, ammo, frags等與我們的訓練目標相關的信號，所以這些信號，能夠對我們的訓練目標進行表示。本文中，認為，我們的訓練目標的goal utility是這些measurements的線性表示，這個表示中，measurements的係數，就是我們的輸入中增加的那個stream——goal vector。基於DFP model得到的future measurements，我們得到future goal utility（我自己瞎起的名字）：

所以我們的訓練目標，是在給定goal vector下，最大化未來goal utility。則，在得到DFP預測的future measurements之後，我們選擇能夠使goal utility最大的action，如此完成決策。

補充一點對goal vector的解釋。如果我t時刻下的measurements m_t是 [health, ammo, frags]，那 g1 = [0.5, 0.5, 1.0] 可以認為訓練的目標是一個，希望保持血量，積極撿彈藥，但更渴望殺戮的agent；g2 = [1.0, 0.0, 0.0] 可以認為是一個「苟」的agent，比如訓練完，就是滿地圖跑酷。

另一點補充是，這個DFP model 也可以看出是RL model，某種角度，他們是統一的。假如我們的measurements就是reward，goal vector（對future offset [1,2,3,...]）是[1, γ, γ^2, ... ]，那麼future goal utility也就是類似RL中return的表示形式。所以，訓練的目標，也是在最大化累計長期reward。

1.3 diversify goals

這篇文章另一個重要的point是——「RL通常是在訓練一個fixed target的agent，而DFP可以不fix這個target，訓練的時候用不同goal的數據，表現的時候，也可以根據不同的goal達到不同的表現」。

回顧DFP的architecture，goal vector流輸入，決定了goal diversity這一點。

例如，訓練時用的experience i包含g_i，這寫g_i可能不一樣，真正測試時用的goal vector也不需要和訓練時用的一樣。

更重要的一點，文章在實驗部分驗證了，訓練時的goal vector如果是隨機生成（例如 [a,b,c]均在[0,1]/[-1,1]之間隨機生成）的，測試評估model時用特定的goal vector（例如[0.5,0.5,1.0]/[1.0,0.0,0.0]）也能達到，用同樣的goal vector （同樣的目標）訓練和測試同水平的performance。

這表示goal的泛化性很好，也就是goal diversity。

1.4 other tricks

文中還包含了一些其他的ideas和tricks，例如future offset/measurements的選擇，architecture中的Duel-like結構，還有generalization over maps等。

1.5 Some takeaways

一些粗鄙的想法：

a) 同樣的game用SL的方式吊打了其他RL的方法，不代表其他有類似dense feedback的場景就可以借鑒。就我的看法，文中很重要的信號是measurements，是dense的也是對goal或者training target有好的標示性的。這點很重要。另一個角度想，其實這裡的measurements其實和state的raw pixels是等同的（這也是為什麼其他RL方法，把這些不加特別區分都作為state的一部分輸入model），由於measurements比raw pixels更high-level（包含更多信息？這麼說好像不太對），且training target能用measurements表示，所以，DFP預測是future measurements。

b) 另外，DFP中包含了對goal的泛化，這也是傳統的RL不能做的事情。傳統的RL是對固定目標的訓練，目標是最大化累計長期收益。而這裡的DFP用一個goal vector的輸入，一方面變相地用基於measurements的reward在指導訓練，另一方面，能夠用不同goal的experience訓練，並且在評估的時候達到不同的performance。我覺得這點值得考慮，當我們面對不同目標，不同對手，不同task的時候，是否可以有好的泛化的方式？

2. 《Opponent Modeling in Deep Reinforcement Learning》

這篇文章也相對比較早，做的事情和實驗也是很多現在的研究都有overlap的。也就是，在多agent環境中，對手策略在變的話，那我怎麼能（給對手建模）做到一個好的應對。

以前的工作很多針對具體場景做的，需要特定的domain knowledge，例如德州撲克，紙牌之類；或者是在給對手建模，把對手分成特定幾類對手，然後顯式地 (explicitly) 去預測對手的動作或者其他信息。而這篇文章希望提出一個比較general且隱式的 (implicit) 框架——DRON（Deep Reinforcement Opponent Network，不是DRQN），解決多agent環境中，對手策略不固定，環境不穩定的因此agent表現不好的問題。

個人覺得這篇文章，沒有他文中說的那麼厲害，但還是比較清晰得提出了一個的確算general的framework（但不算特別驚艷，當然也可能是我17年看他16年甚至更早的文章的原因）。

2.1 Q-Learning w/ and w/o opponents

文中先形式化地分析了一下，多agent環境中，對手策略變化的情況下Q-Learning和simple single-agent情況下的區別。

首先，最優策略的Q值等同於解以下Bellman Equation:

最優的策略就是選擇當前state下Q值最高的action。

Q-Learning方法是一種不需要知道 knowledge of transition model (model-free) 而找到最優策略的學習方法。給定觀察到的transition (s, a, r, s)，如下更新Q值：

大狀態空間里，Q-function 不能用tabular 方式來做的話，可以用NN等函數近似器來擬合 Q-function（用一組參數θ），例如DQN基於經驗回放，對經驗 (s, a, r, s)， 訓練模型來預測Q值，通過最小化均方差：

以上都是single-agent的方式。

多agent環境中，形式化表示中，我們把自己的agent，或者說primary agent和其他agent或者說secondary agents分別用a和o（或者有些paper中的-a）表示。

類似地有聯合動作：

轉移函數：

回報函數：

統一single-agent中的情況，也就是對手的策略π^o固定的，或者說是環境MDP的一部分，那麼：

然而大部分問題，對手的策略不會是一直不變的，也就是說，這個對手策略π^o，不能簡單地看作是環境的一部分（看作環境的一部分的話，就是一個變化的non-stationary的環境了）。

最優策略的Q值考慮對手的策略，

Q值的遞歸更新關係類似地有如下形式：

這裡區別於之前的Q值遞歸關係，是在於對手策略的一項，π_t^o，也就是這篇文章主要考慮的部分，怎麼implicitly地建模，或者說，怎麼把抽取對手策略和Q值的關係，把對手策略的一項，融入到Q function近似中去。

2.2 DQN w/ opponent model

直接上網路結構：

上標s和o分別表示state和opponent。

左邊的結構DRON-concat，如圖所示，就是把關於對手的信息，抽取一下特徵，concatenate到state 特徵里，一起產生Q值。這是很直接，很implicit的方式。

右邊的結構DRON-MOE，用一些 Mixture-of-Experts，可以理解是，對（可能）不同對手預先學好的若干個expert Q functions，然後同樣地，抽對手的特徵來學一個權重，用這個權重，結合expert functions來得到最終的Q function。

這就是這篇文章提出的opponent model framework，很直接，你不能說它不general。也是應為文中也沒給出特別的說明，說這個對手的信息怎麼來，怎麼表示，怎麼抽。兩個實驗中，soccer中，對手的輸入信息設置為，對手move的頻率，最近的move和action，被對手斷球的頻率等；Quiz bowl中，對手的信息設置為，對手已回答的問題數，平均buzz的位置，以及錯誤率。

1.3 Extra supervision

文章還提到了在上文提到的framework上，加一些extra supervision，也就是用一些額外的監督信號，例如對手的type，對手的action，來做SL。如圖：

這個y^o就是對手的監督信號。

這個額外的SL是為了更好地抽對手的特徵，試驗證明，是有一定效果的，尤其是對DRON-concat，個人覺得因為DRON-concat更general，更implicit，更好的對手feature的表示，顯然能提升這個model的performance。

這裡有些疑問，這篇文章從開頭和結尾都說，提出的framework主要是implicit的，其實在我愚見，只有不帶extra supervision的DRON-concat才算又general又implicit。開頭說了別人的工作會預先把對手分成幾類，或者explicit預測對手的action，這裡好像還是有點類似的。

1.4 Some takeaways

a) 在愚蠢的我看來，其實這篇文章提出的framework，和DFP中的architecture，也有相關性，如果把DFP中的S(s) 和 M(m) 看作是state輸入，不同的goal和不同的opponent前行看作是類似物的話，goal vector是goal的比較準確的特徵，那DFP就類似與DRON-concat了。（好吧，其實一點都不像，尷尬）

b) 對手信息怎麼來，怎麼表示，怎麼抽，還是有點疑惑，希望能有更形式化的表述或者解釋。

3. 《Universal Value Function Approximators》

圍繞對如何面對不同的對手，始終能夠快速的做到一個好的performance這一點問題。我從DFP那篇文章的ref中找到了這篇，然後發現，讀不懂，但是好像不得了，再讀讀，懂了點，好像挺厲害，再讀讀，好像懂了，厲害是厲害，但是似乎沒啥用。

3.1 Extension of value function

類似DFP那篇中提到的，傳統的RL大多目的是最大化累計長期收益，也就是對reward表示的任務或者目標，去學。或者說，我們的value function V(s)，是特定任務或者目標g下，狀態s對能夠到達這個目標的utility（瞎理解）。

文中extend了value function approximater的常規表達，由V(s; θ) 到 V(s, g; θ)，這裡的g表示specific goal，也就是，這是一個對goal對state的一個value function approximate。所以這大概也是為什麼這文章叫Universal，這個帶g的值函數近似器，就叫UVFA（讀「U法」）。

這麼做是為什麼呢，是為了在goal上泛化。也就是，一種更廣泛的表示，如果我有一些goal下的值函數已經知道了，能不能泛化到一些新的unseen goal上？

文章中認為，我們用NN等函數近似器去擬合值函數，可以成功地在state上泛化，也就是我的採樣肯定是有限的，且只能cover state space中的一小部分，然而，函數近似器，可以把我遇到過的state的「經驗」泛化到一些unseen的state上去，且performance還不錯。那麼類似地，goal space也有和state space一樣多的內在結構，能不能把已有的goal的「經驗」泛化到新goal上？

簡潔地說，目標是得到一個UVFA，V(s,g; θ)，我只有一部分experience可供學習，這些experience，只cover state/goal space中的一小部分，能不能學到有用的UVFA。

先不想這個goal怎麼來，怎麼表示（文中居然也扔掉了這個問題！），先把goal放在和state等同的地位，來考慮。則一個UVFA，表示的是這個goal的 pseudo-discounted 累計 pseudo-reward：

這兩個pseudo表示的，也就是，這些goal各自的reward和discount factor。形式和傳統的V(s)一致（本來就是一種拓展）。

類似地，state-action也就是Q值：

3.2 UVFA

提出了UVFA這個概念，肯定要給出，怎麼構造和訓練UVFA。

文中提出的framework如下：

最左邊的concatenated architecture，是一個state和goal到value的簡單連接和直接映射。

中間的two-stream architecture，是不是和上一篇opponent model中的DRON-concat很像？不同點就在於，goal和opponent，這兩者看如何定義了，我覺得，是有關係的。

右邊的是decomposed view of two-stream architecture，其實是一個東西，只是具體illustrate了做法。這個做法就是本文中比較依託的一個idea——low-rank factorization，也就是低秩分解。

下面說一下文中這個低秩分解的做法和含義。

UVFA的形式是包含state (action) 和goal的，V(s,g)或者Q(s,a,g)，把它看成一個矩陣的話，可以是下面最左邊這個樣子（這個圖可以在文章的appendix里找到），而實際的情況，我們的experience只是state和goal space里的一些sparse的samples，也就是左二中零星的像素點。

文中提出的做法是，把這個矩陣低秩分解成表示state的特徵矩陣$/phi(s)$，和表示goal的特徵矩陣的乘積$/psai(g)$，也就是右邊三張圖想表示的意思。

這裡有幾點說明：

1）sparse矩陣怎麼補全，文中說的做法是OptSpace方法，看了眼，看不懂（格拉斯曼流形？？？quit，quit），這應該屬於matrix completion這個數學範疇？矩陣填充或者舉證補全。能力有限，水平不足，不敢妄語。

2）low-rank factorization能還原原本的矩陣嗎？low-rank的意思是，這個rank r比原始矩陣的rank小，甚至很小，因為用少量的rank就能還原出原始矩陣的信息。關於這一點有疑惑，可以回頭看看 奇異值分解(singular value decomposition) 相關的資料（知乎里也有，我就是看的）。

3）這樣分解的好處，一方面，用更少的存儲單元去表示信息，代價會小，會快。還有一些好處，是和UVFA相關的。

回到文中提出的architecture上來說，decomposed view of two-stream architecture就是做類似的事情：

3.3 SL of UVFA

接著講，這個圖的意思，就是基於這種分解的思想，解構，再得到UVFA。

先考慮理想化的，簡單的SL情況，也就是假如有ground true value V^*_g(s)。

基於這點假設，我們把真值矩陣分解$/hat /phi(s)$和$/hat /psai(g)$，然後分別作為state流和goal流的supervision，進行SL。

這裡我的理解是，用矩陣低秩分解的思路，跳躍地得到比較好的特徵目標，來指導state和goal的特徵提取。然後同樣逆著低秩分解的思路，得到UVFA。

這就是UVFA SL的情況，比較理想，因為ground true value V^*_g(s)不太可能得到。

這部分文中做了SL的實驗，得到一些結論。驗證了，decomposed的two-stream的確能比其他兩個學得又快又好。以及構造的UVFA的泛化性很好，基於UVFA得到的策略在低秩的時候，也能達到較高policy quality。以及一些低秩分解重構得到的好的特性等。

3.4 RL of UVFA

拋去理想化的假設，沒有ground true value V^*_g(s)，只有連續的observations，actions和rewards的RL場景中，文章提了兩種學習UVFA的方法——Horde和直接地bootstrapping。

Horde of demons，大概可以理解為，一些同一個環境interaction stream里學出來的不同goal的value functions，具體細節可以參考下面這篇文章（慚愧，我沒仔細看）。

-《Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. 》

基於Horde，也就是有了一組value function，怎麼得到UVFA——構造M，分解，two-stream SL，然後重構。

用演算法來講：

由於沒有研究Horde那篇，這裡說一下我的揣測和理解。

1）3-5行是收集transition experience的過程；

2）6-10行更新Horde of demons，也就是更新一對Q functions；

3）11-16行構造上節里提到的矩陣M，即 V(s,g) 或者 Q(s,a,) 矩陣；

4）17行分解得到supervision；

5）18-24行進行two-stream SL；

6）25行重構UVFA

比SL的版本，也就多了Horde怎麼來，怎麼訓練的部分。

另外，bootstrapping就是end-to-end地直接學UVFA，

顯然基於Horde的方法，更為有技巧性和有效一些，直白地bootstrapping相比較更不穩定，泛化得到的策略的policy quality略差一些。

RL部分實驗中，驗證了，學習到的UVFA對state和goal都有著一定的泛化能力，能夠得到有用的generalization。

初次之外，實驗中還提到了，把重構泛化得到的value function作為對一個unseen goal的value function初值，能比隨機給初值，學得更快——也就是，same env dynamic (MDP) transfer:

這也是本文很有意義的一點。

3.5 Some takeaways

a) Transfer這一點的確有啟發意義，但這種transfer的效果和cost的衡量，以及和其他transfer方法的比較，我認為還有待進一步評估。

b) 這篇文章中的goal比較有局限性，以及基於這種goal所使用的方法Horde，以及一些如option之類的概念，和意義（包括文中的symmetry等），還不甚了解。

c) goal怎麼來，怎麼表示，這個很重要，也是最需要思考的問題，這點是和我把三篇文章放在一起的原因，goal的形式化的表示和應用，是三篇文章的潛在相關。而這篇文章一直在迴避這個問題，實驗中的goal也很有局限性（goal屬於state或者等價於state）。

總結

還是圍繞「對不同的對手opponent/任務task/目標goal，如何進行泛化generalization或者遷移transfer」這個問題，認為這種基於低秩分解的方法是有特殊性，但可能可以借鑒到網路結構設計中；更broad的是V(s,g)或者Q(s,a,g)這個概念，怎樣用更concrete的形式化去描述；或者更具體的問題，例如面對不同對手，我應該怎樣選取的對手的一些信息，去學習特徵表示，去指導agent的學習。

以上都是小僧粗鄙的見解，庸人自擾。

大明輪王以小無相功催動的拈花指功也看不破，更不識天下之大了。