原文及翻譯
Abstract 摘要：
We present Value Propagation (VProp), a set of parameter-efficient differentiable planning modules built on Value Iteration which can successfully be trained using reinforcement learning to solve unseen tasks, has the capability to generalize to larger map sizes, and can learn to navigate in dynamic environments. We show that the modules enable learning to plan when the environment also includes stochastic elements, providing a cost-efficient learning system to build low-level size-invariant planners for a variety of interactive navigation problems. We evaluate on static and dynamic configurations of MazeBase grid-worlds, with randomly generated environments of several different sizes, and on a StarCraft navigation scenario, with more complex dynamics, and pixels as input.
我們提出了一種可導的參數較少的規劃子產品：VProp（基于價值疊代），用強化學習訓練來求解未知任務，并且可以泛化到更大的地圖尺寸，也能夠在動态環境中操作。我們證明，VProp在包含随機元素的環境中不失有效性，進而提供了一種經濟高效的學習系統為各種互動式導航問題建構低級尺寸不變的規劃。我們基于迷宮的網格世界的靜态和動态配置，随機生成了幾種不同大小的環境進行評估，并在有更複雜的動态和像素作為輸入的星際争霸場景中進行了評估。
1 Introduction 引言
規劃是人工智能在各個領域的關鍵組成部分。然而，經典規劃算法的局限性展現在，需要知道如何為每一種可能的規劃類型的每一個執行個體尋找最優的—或者至少是合理的解決方案。随着環境動态和狀态複雜性的增加，規劃變得困難、麻煩，或者完全不切實際。這就是為什麼“學習規劃”一直是一個活躍的研究領域的原因之一(Russell等人，1995;Kaelbling等人，1996)。為了能夠在實踐中變得有用，我們假設能夠學習規劃的方法至少應該有兩個優點
- 算法的軌迹應是自由的，即不需要最優規劃者的軌迹.（ they should be traces free, i.e. not require traces from an optimal planner）
- 能夠泛化,即執行個體或者規劃的方向未知，規劃器也能在相同類型的規劃上起作用。（they should generalize, i.e. learn planners that are able to function on plans of the same type but of unseen instance and/or planning horizons.）
在強化學習(RL)中，學習規劃可以被轉化為是尋找最大化預期回報政策的問題。這是一個貪婪政策，它選擇具有較高價值的狀态。（where such policy is a greedy function that selects actions that will visit states with a higher value for the agent\不是highest？）這反過來将問題轉化為估計狀态價值。解決這一問題最常用的算法之一是價值疊代(VI)，通過收集和傳播觀測到的獎勵值來估計狀态值，直到達到一個定點。（which estimates the state values by collecting and propagating the observed rewards until a fixed point is reached.）然後，可以通過在所需的狀态-動作對上展開獲得的值函數來構造政策（規劃）。（rolling out the obtained value function on the desired state-action pairs）
當環境可以用占有圖（二維網格）代表，就可以通過用深度卷積神經網絡(CNN)來傳播網格單元上的獎勵來近似規劃算法，這使得人們可以通過規劃每一步直接區分并且執行值函數的端到端學習.（This enables one to differentiate directly through the planner steps and perform end-to-end learning of the value function.）Tamar et al. (2016) 訓練了VIN模型，對來自搜尋/規劃算法的軌迹采用了有監督的損失函數，目标是通過使用卷積層疊代學習值函數尋找可以解決此類環境中最短路徑任務的參數值。然而，這需要良好的目标價值估計，這違反了我們希望的無軌迹屬性，并限制了它在互動式動态設定中的使用。此外，它沒有利用模型結構來進行泛化。VIN – with a supervised loss on the trace from a search/planning algorithm, with the goal to find the parameters that can solve the shortest path task in such environments by iteratively learning the value function using the convnet. However, this baseline requires good target value estimates, violating our wished trace free property, and limiting its usage in interactive, dynamic settings. Furthermore, it doesn’t take advantage of the model structure to generalise to harder instances of the task.
本文我們将VIN中使用的規範化擴充到更準确地代表網格世界的場景結構中,使VIN在初始工作範圍之外強化學習架構中也可使用,同時删除了一些限制和基本假設。我們證明了我們的模型不僅可以動态環境中學習規劃和導航，而且它們的層次結構為應用到所需的規劃範圍和地圖的大小比訓練時看到的要大得多的情況提供了解決方法，。我們的主要貢獻包括:
(1)引入VProp和MVProp網絡規劃子產品，通過強化學習的最小的參數化成功學習解決路徑搜尋任務
(2)在小地圖上訓練結果可用在大的未知地圖中
(3)無論是在轉換函數還是觀察複雜度方面（both in terms of transition function and observation complexity），我們的子產品在比靜态網格世界更複雜的場景中也能學習。
1.1 Related work相關工作
基于模型的端到端架構規劃前景廣闊，通常使用深度強化學習作為算法架構(Silver et al.， 2016)。在RL架構内也處理了3D和2D導航任務(Mirowski et al. 2016)，在某些情況下，使用在2D占位圖上建構和調整的方法來幫助定位和特征接地（feature grounding）的過程(Bhatti et al.2016;zhang2017;Banino et al.，2018)。
其他工作進一步探索了使用類似于VIN的架構來解決操作問題:Niu等人(2017)提出了一個泛化的VIN，通過使用一個圖卷積算子對圖的每個節點進行卷積來學習更一般的圖結構上的子產品。Rehder等人(2017)通過訓練多個VI模型并将它們組合成一個網絡，同時添加一個方向狀态通道來模拟移動機器人中常見的非完整限制（non-holonomic constraints），示範了在協作環境中進行多智能體規劃的方法。Gupta等人(2017)和Khan等人(2017)提出，通過建構分層planners 來處理部分可觀察的設定，這些planners 以多尺度的方式使用VI子產品來生成規劃并調節模型的信念狀态（ belief state）。
2 Background 背景
我們考慮在網格世界環境中對智能體的控制，其中實體可以互相互動。這些實體有一些屬性（attributes），包括一個惟一定義的類型，它描述了它們如何互相互動、互動的即時回報以及互動如何影響世界的下一個狀态。目标是通過強化學習來學習規劃，即學習一種針對環境配置的政策，這種政策可以推廣到環境的任意其他配置，包括更大的環境和具有更多實體的環境。在标準導航任務的情況下，這可以歸結為學習一個政策（this boils down to learning a policy ），該政策根據對世界的觀察，将輸出使智能體盡可能快地達到目标的操作。智能體觀察二維圖像 d x × d y d_x \times d_y dx×dy，輸入窗格 d p i x d_{pix} dpix作為環境, 傳入嵌入函數 Φ Φ Φ(如二維卷積)提取實體并生成一些基于位置和特性的本地嵌（generates some local embedding ）。
2.1 Reinforcement Learning 強化學習
強化學習問題通常通過計算馬爾可夫決策問題(MDP)的最優政策來表述(Sutton and Barto, 1998)。MDP)用 ( S , A , T , R , γ ) (S, A, T, R, γ) (S,A,T,R,γ)元組定義 , S S S是一組有限的狀态集合， A A A是智能體可采取的動作 a a a的集合， T : s → a → s ′ T : s → a → s' T:s→a→s′描述狀态轉換矩陣, R R R是獎勵函數, γ γ γ是折扣因子。在這種背景下,最優政策 π ∗ π^∗ π∗是狀态動作空間的一個分布，他最大化折扣獎勵 ∑ k γ k r k \sum_{k}γ^kr_k ∑kγkrk的期望， r k r_k rk是單步獎勵。找最優政策 π : s → a π : s → a π:s→a的一個标準方法是疊代計算價值函數, Q π ( s , a ) Q^π(s, a) Qπ(s,a),根據從環境得到的獎勵進行更新(Watkins and Dayan, 1992)。使用該架構，我們可以将學習規劃看作是用價值疊代算法對獎勵的結構化預測(Bertsekas, 2012)（as inference procedure）。政策梯度算法也能找到最優政策(Sutton et al ., 1999),直接回歸到政策函數 π π π而不是去近似價值函數。然而，這些方法在需要許多步驟的環境中方差較大。此外， actor-critic（AC）算法也用來解決最優政策問題，它結合了政策梯度方法能夠直接計算政策和基于值的的低方差優點，作為對policy estimator 的更準确的回報信号(Konda和Tsitsiklis, 2000)。
2.2 Value Iteration Module 價值疊代（VI）模型
Tamar等人(2016)通過觀察導航和更一般的尋路問題發明了VI模型,VI模型可以展開為一個圖卷積網絡,節點是智能體可能的位置，邊代表根據智能體的行為産生可能的轉換。在簡單例子中：二維網格，圖形結構對應于二維空間中的一個鄰域，卷積結構類似于一個将整個二維環境作為輸入的卷積網絡。
更準确地說，用 s s s表示目前環境的觀測值（例如二維網格的鳥瞰圖) q 0 q^0 q0 是 ( A , d x , d y ) (A, d_x, d_y) (A,dx,dy)的零向量， d x , d y d_x, d_y dx,dy代表二維網格的兩個向量，A是智能體的動作數。價值疊代子產品由一個嵌入函數定義， Φ ( s ) ∈ R d r e w × d x × d y Φ(s) \in\mathbb{R}^{d_{rew}×d_x×d_y} Φ(s)∈Rdrew×dx×dy ，其中 d r e w d_{rew} drew由模型決定 ,轉移函數 h h h（狀态轉移函數？）,并執行下列步驟計算 k = 1... K , K k = 1...K,K k=1...K,K為VI子產品的深度:
∀ ( i , j ) ∈ [ [ d x ] ] × [ [ d y ] ] , v i j k = max a = 1.. A q a , i , j k , q k = h ( Φ ( s ) , v k − 1 ) \begin{aligned} ∀(i, j) ∈ [ [d_x] ] × [ [d_y] ], v_{ij}^k&=\max_{a=1..A}q_{a,i,j}^k,\\ q^k&= h(Φ(s), v^{k−1})\\\end{aligned} ∀(i,j)∈[[dx]]×[[dy]],vijkqk=a=1..Amaxqa,i,jk,=h(Φ(s),vk−1)
控制政策 π π π定義為 π ( s , ( x 0 , y 0 ) ) = arg max a = 1.. A q a , x 0 , y 0 K ， ( x 0 , y 0 ) π(s,(x_0, y_0)) =\argmax_{a=1..A}q_{a,x_0,y_0}^K，(x_0, y_0) π(s,(x0,y0))=a=1..Aargmaxqa,x0,y0K，(x0,y0)是智能體的位置，我們可以把轉移函數 h h h寫成卷積層
( a ) r ˉ i , j = Φ ( s ) i , j (a)\bar{r}_{i,j} = Φ(s)_{i,j} (a)rˉi,j=Φ(s)i,j
( b ) v i , j 0 = 0 , q a , i , j k = ∑ ( i ′ , j ′ ) ∈ N ( i , j ) p a , i ′ − i , j ′ − j ( v ) × v i ′ , j ′ k − 1 + p a , i ′ − i , j ′ − j ′ ( r ) × r ˉ i ′ , j ′ (b)v_{i,j}^0= 0, q_{a,i,j}^k =\sum_{(i',j')∈N(i,j)}p_{a,i'−i,j'-j}^{(v)} \times v_{i',j'}^{k−1}+p_{a,i'−i,j'−j'}^{(r)}\times \bar r_{i',j'} (b)vi,j0=0,qa,i,jk=∑(i′,j′)∈N(i,j)pa,i′−i,j′−j(v)×vi′,j′k−1+pa,i′−i,j′−j′(r)×rˉi′,j′
v i , j k = max a q a , i , j k − 1 \quad v_{i,j}^k=\max_{a}q_{a,i,j}^{k−1} vi,jk=maxaqa,i,jk−1
其中 N ( i , j ) N(i, j) N(i,j)是位置 ( i , j ) (i, j) (i,j)本身和其臨近單元的集合。在實踐中,在不同的任務上使用VI子產品， Φ ( s ) Φ(s) Φ(s)有幾個輸出通道 d r e w d_{rew} drew和不同數量的參數量(a varying number of parameters)。 p a , i ′ − i , j ′ − j ( v ) ∈ R p_{a,i'−i,j'-j}^{(v)}\in\mathbb{R} pa,i′−i,j′−j(v)∈R 和 p a , i ′ − i , j ′ − j ′ ( r ) ∈ R p_{a,i'−i,j'−j'}^{(r)}\in\mathbb{R} pa,i′−i,j′−j′(r)∈R則純粹表示VI子產品的參數。
因為計算 q a , i , j k q_{a,i,j}^k qa,i,jk的步驟是一個卷積層，進而能夠用一個深度為K的卷積網絡權值共享計算,有多少種動作就有多少輸出通道， q a , i , j K q_{a,i,j}^K qa,i,jK， v i , j k v_{i,j}^k vi,jk的計算是網絡的非線性，它對應于輸出通道次元中的最大池化。
為了闡明在網格世界中我們和原來VI模型的關系，我們用 R a , i , j , i ′ , j ′ R_{a,i,j,i',j'} Ra,i,j,i′,j′表示經動作 a a a從 ( i , j ) (i, j) (i,j)到達 ( i ′ , j ′ ) (i', j') (i′,j′)的即時獎勵， P a , i , j , i ′ , j ′ P_{a,i,j,i',j'} Pa,i,j,i′,j′表示轉移機率， γ γ γ是折扣因子，是以，二維網格中價值疊代可表示為
∀ ( i , j ) ∈ [ [ d x ] ] × [ [ d y ] ] , v i j k = max a = 1.. A Q a , i , j k , ∀ ( a , i , j ) ∈ [ [ A ] ] × [ [ d x ] ] × [ [ d y ] ] , Q a , i , j k = ∑ ( i ′ , j ′ ) ∈ N ( i , j ) P a , i ′ , i , j ′ , j ( R a , i ′ , i , j ′ , j + γ v i j k − 1 ) \begin{aligned} ∀(i, j) ∈ [ [d_x] ] × [ [d_y] ], v_{ij}^k&=\max_{a=1..A}Q_{a,i,j}^k,\\ ∀(a,i, j) ∈ [ [A] ] ×[ [d_x] ] × [ [d_y] ], Q_{a,i,j}^k&=\sum_{(i',j')∈N(i,j)}P_{a,i',i,j',j}(R_{a,i',i,j',j}+\gamma v_{ij}^{k-1}\end{aligned} ) ∀(i,j)∈[[dx]]×[[dy]],vijk∀(a,i,j)∈[[A]]×[[dx]]×[[dy]],Qa,i,jk=a=1..AmaxQa,i,jk,=(i′,j′)∈N(i,j)∑Pa,i′,i,j′,j(Ra,i′,i,j′,j+γvijk−1) N ( i , j ) N(i, j) N(i,j)是從位置 ( i , j ) (i, j) (i,j)獲得的先驗資訊。 R a , i , j , i ′ , j ′ R_{a,i,j,i',j'} Ra,i,j,i′,j′是起止狀态的函數，我們對它參數化以實作價值疊代。更重要的一點，使用卷積網絡實作價值疊代意味着 p a , i ′ − i , j ′ − j ( v ) p_{a,i'−i,j'−j}^{(v)} pa,i′−i,j′−j(v)表示的轉換機率是平移不變的。
3 Models 模型
從計算的角度來看，VI模型很有吸引力，因為它們可以作為卷積神經網絡有效地實作。他們也在概念上呼應了神經網絡的設計架構,因為他們給出一個明确的動機和層之間共享權重的解釋,并為必要的網絡深度提供指導：深度應滿足獎勵信号從“目标”狀态傳播到智能體,是以是最短路徑的長度的函數。
參數的權重共享降低了樣本的複雜性，這種結構也适合一種有趣的泛化形式:在小環境中學習導航(訓練小的 d x , d y d_x, d_y dx,dy)，并泛化到更大的執行個體(大 d x , d y d_x, d_y dx,dy)。也就是說，從與價值疊代的類比可以得出，對較大執行個體的泛化應該需要更深的網絡，因為權重是共享的。然而，Tamar等人(2016)以及我們在第4節中提出的實驗表明，采用強化學習的價值疊代模型的學習仍然非常具有挑戰性，沒有像想象中那樣自然地泛化，這表明樣本複雜性仍然是一個主要問題。
在本節中，我們提出了上述VI模型的兩種替代方法，目的是提供最小的參數化，為了更好的樣本複雜性和泛化能力，同時保持卷積結構和共享權值的深度網絡的思想。我們主要讨論兩個VI模型的選擇:首先,我們丢棄VI模型的一個重要假設：轉換機率的平移不變性,我們把轉移機率看做是狀态的函數,并尋找适用于網格的世界的轉移機率的最小參數。其次，為了利用強化學習來提高樣本效率，進而允許利用架構的結構來實作泛化，我們對即時獎勵函數進行了更嚴格的參數化。
3.1 Value-Propagation Module VPro模型
我們觀察到，在網格世界的最簡單版本中，動态是确定性的，動作隻是移動到相鄰的單元中。世界模型應該考慮阻塞單元(例如地形或障礙)，而獎勵函數應該考慮目标狀态。此外，在分幕式任務中實作價值疊代時非常重要的一點是，需要考慮終端狀态，終端狀态可以通過吸收态表示，這些狀态的下一個狀态一定是以0獎勵回到目前的狀态(Sutton和Barto, 1998)。
與VI子產品類似，VProp層間共享權重的深度卷積神經網絡:
( a ) r ˉ i , j , p i , j = Φ ( s ) i , j , ( b ) v i , j 0 = r ˉ i , j , v i , j ( k ) = max ( v i , j k − 1 , max ( i ′ , j ′ ) ∈ N ( i , j ) ( r ˉ i , j + p i , j ( v i ′ , j ′ k − 1 − r ˉ i , j ) ) ) , ( c ) π ( s , ( i 0 , j 0 ) ) = arg max ( i ′ , j ′ ) ∈ N ( i 0 , j 0 ) v i ′ , j ′ K (a)\bar{r}_{i,j} ,p_{i,j}= Φ(s)_{i,j},\\(b)v_{i,j}^0= \bar{r}_{i,j}, v_{i,j}^{(k)} =\max(v_{i,j}^{k-1},\max_{(i',j')∈N(i,j)}(\bar{r}_{i,j} +p_{i,j}(v_{i',j'}^{k-1}-\bar{r}_{i,j}))),\\(c)π(s,(i_0,j_0))=\argmax_{(i',j')∈N(i_0,j_0)}v_{i',j'}^K (a)rˉi,j,pi,j=Φ(s)i,j,(b)vi,j0=rˉi,j,vi,j(k)=max(vi,jk−1,max(i′,j′)∈N(i,j)(rˉi,j+pi,j(vi′,j′k−1−rˉi,j))),(c)π(s,(i0,j0))=(i′,j′)∈N(i0,j0)argmaxvi′,j′K.
VProp模型所有參數都在嵌入函數 Φ Φ Φ中——疊代層沒有任何額外的參數。對于每個位置 ( i , j ) (i, j) (i,j),嵌入函數有兩種類型的輸出：
第一種是向量： ( r ˉ i , j i n , r ˉ i , j o u t ) (\bar r_{i,j}^{in},\bar r_{i,j}^{out} ) (rˉi,jin,rˉi,jout)， 全獎勵函數（full reward function） R a , i , j , i ′ , j ′ = r ˉ i , j i n − r ˉ i , j o u t R_{a,i,j,i',j'}=\bar r_{i,j}^{in}-\bar r_{i,j}^{out} Ra,i,j,i′,j′=rˉi,jin−rˉi,jout。這是為了正确地處理吸收态: r ˉ i n \bar r^{in} rˉin 是智能體到達 i , j i, j i,j 時獲得的獎勵(目标狀态獎勵高，應該避免的位置獎勵低), r ˉ o u t \bar r^{out} rˉout是離開時的代價.吸收态用 r ˉ i , j i n = r ˉ i , j o u t \bar r_{i,j}^{in}=\bar r_{i,j}^{out} rˉi,jin=rˉi,jout表示.
Φ Φ Φ給出的第二種輸出是個值： p i , j p_{i,j} pi,j，它表示與該位置相關的傳播參數，或者隻是一個與狀态有關的折扣因子（White, 2016）： p i , j ≈ 1 p_{i,j}≈ 1 pi,j≈1表示鄰近值 v i ′ , j ′ v_{i',j'} vi′,j′通過 ( i , j ) (i, j) (i,j)傳播，而 p i , j ≈ 0 p_{i,j}≈ 0 pi,j≈0表示位置 ( i , j ) (i, j) (i,j)阻塞，通常會在包含障礙物的單元格中出現。在我們的實作中，所有 r ˉ i n , r ˉ o u t , p \bar r^{in},\bar r^{out}, p rˉin,rˉout,p通過sigmoid激活函數保持在[0,1]範圍内。
VProp對應于動力學是确定性的，并且動作與相鄰單元格之間存在一對一的映射的價值疊代。在等式 （ c ） （c） （c）中假定了此映射，其中輸出是位置而不是動作。實際上，由于 ( i ′ , j ′ ) (i',j') (i′,j′)是相鄰單元格，很容易知道采取哪種行動能到達該單元格。但是，如果映射未知，則可以使用 π ( s ) = F ( [ v i ′ , j ′ ( K ) ] ( i ′ , j ′ ) ∈ N ( i 0 , j 0 ) ) π(s) = F([v_{i',j'}^{(K)}]_{(i',j')∈N(i_0,j_0)}) π(s)=F([vi′,j′(K)](i′,j′)∈N(i0,j0))， F F F将智能體的鄰域作為輸入并執行從傳播值到實際動作的映射。
需要強調的是，這種特殊的體系結構是為可表示或近似表示為2D網格結構（例如，機器人導航）的環境而設計的，但是該公式可以輕松地擴充到更通用的圖形結構。有關更多詳細資訊，請參見附錄A。
3.2 Max-Propagation Module
當将VI子產品和VProp泛化到更大的環境中時，主要困難是，在固定大小的網格中，障礙物/阻塞單元可以用兩種不同的方式表示:較小傳播值或者較大的輸出獎勵。在實踐中,網絡在有限大小的網格上訓練可以學會任何有效的配置,但是基于負回報和高傳播的配置不能泛化到更大的環境:一般來說直接穿過障礙的負獎勵不足以彌補繞障所需正确路徑的長度,。當環境的大小固定時，已知障礙物的最大繞行距離，可以相應地設定獎勵。但是，随着環境規模的增大，繞過障礙的成本也會增加，負獎勵不能很好的代表。
為了克服這一困難，我們提出了MVProp，隻傳播正獎勵。這意味着表示阻塞路徑的唯一方法是不傳播獎勵——負獎勵不再是一個解決方案，MVProp子產品定義如下：
( a ) r ˉ i , j , p i , j = Φ ( s ) i , j , ( b ) v i , j 0 = r ˉ i , j , v i , j ( k ) = max ( v i , j k − 1 , max ( i ′ , j ′ ) ∈ N ( i , j ) ( r ˉ i , j + p i , j ( v i ′ , j ′ k − 1 − r ˉ i , j ) ) ) , ( c ) π ( s , ( i 0 , j 0 ) ) = arg max ( i ′ , j ′ ) ∈ N ( i 0 , j 0 ) v i ′ , j ′ K (a)\bar{r}_{i,j} ,p_{i,j}= Φ(s)_{i,j},\\(b)v_{i,j}^0= \bar{r}_{i,j}, v_{i,j}^{(k)} =\max(v_{i,j}^{k-1},\max_{(i',j')∈N(i,j)}(\bar{r}_{i,j} +p_{i,j}(v_{i',j'}^{k-1}-\bar{r}_{i,j}))),\\(c)π(s,(i_0,j_0))=\argmax_{(i',j')∈N(i_0,j_0)}v_{i',j'}^K (a)rˉi,j,pi,j=Φ(s)i,j,(b)vi,j0=rˉi,j,vi,j(k)=max(vi,jk−1,max(i′,j′)∈N(i,j)(rˉi,j+pi,j(vi′,j′k−1−rˉi,j))),(c)π(s,(i0,j0))=(i′,j′)∈N(i0,j0)argmaxvi′,j′K.
像VProp一樣，MVProp是具有确定性的動作到位置的映射，是價值疊代的另一種實作，但是這次模型受到限制，僅傳播正獎勵，傳播方程 ( r ˉ i , j + p i , j ( v i ′ , j ′ k − 1 − r ˉ i , j ) ) (\bar{r}_{i,j} +p_{i,j}(v_{i',j'}^{k-1}-\bar{r}_{i,j})) (rˉi,j+pi,j(vi′,j′k−1−rˉi,j))可化為 p i , j v i ′ , j ′ k − 1 + r ˉ i , j ( 1 − p i , j ) p_{i,j}v_{i',j'}^{k-1}+\bar{r}_{i,j}(1-p_{i,j}) pi,jvi′,j′k−1+rˉi,j(1−pi,j)是以與VProp的主要差別是,MVProp隻傳播正獎勵。（since the propagation equation can be rewritten as ，so the major difference with VProp is that MVProp focuses only on propagating positive rewards. Note therefore that all other remarks concerning more general versions of VProp also apply to MVProp.）關于VProp的更一般版本的所有其他備注也适用于MVProp。
4 Experiments
訓練時，用帶experience replay的actor-critic，收集形式 ( s t , a t , r t , p t , s t + 1 ) (s^t, a^t, r^t, p^t, s^{t+1}) (st,at,rt,pt,st+1)的轉移軌迹（transition traces）， s t s^t st是時間 t t t步的觀測值, a t a^t at是選擇的動作，向量 p t p^t pt是由政策得出的動作機率， r t r^t rt是即時回報。該體系結構包含前面幾節中描述的政策 π θ π_θ πθ，以及值函數 V w V_w Vw，采用與政策的softmax層相同的輸入，并與智能體的 3 × 3 3×3 3×3鄰域連結。 w w w和 θ θ θ共享所有權重，直到卷積循環結束。在訓練時,鑒于時間 t t t 步用 π θ t π_{θ^t} πθt表示随機政策，我們對最後一個$ L 轉 換 随 機 抽 取 的 B 個 過 渡 的 最 小 批 量 （ 表 示 為 轉換随機抽取的B個過渡的最小批量（表示為 轉換随機抽取的B個過渡的最小批量（表示為 B $）進行采樣，并對重要性權重獎勵進行梯度上升（we sample a minibatch of B transitions, denoted B B B, uniformly at random from the last L L L transitions, and perform gradient ascent over importance-weighted rewards）
θ t + 1 ← θ t + η ∑ ( s , a , r , p , s ′ ) ∈ B m i n ( π θ t ( s , a ) p ( a ) , C ) ( r + 1 { s ′ ≠ ∅ } γ V w t ( s ′ ) − V w t ( s ) ) ( ∇ θ t l o g π θ t ( s , a ) ) + λ ∑ ( s , a , r , p , s ′ ) ∈ B ∑ a ′ p ( a ′ ) ( ∇ θ t l o g π θ t ( s , a ′ ) ) , w t + 1 ← w t − η ′ ∑ ( s , a , r , p , s ′ ) ∈ B m i n ( π θ t ( s , a ) p ( a ) , C ) ( V w t ( s ) − r − 1 { s ′ ≠ ∅ } γ V w t ( s ′ ) ) ∇ w t V w t ( s ) , θ^{t+1}←θ^t+η\sum_{(s,a,r,p,s')∈B}min(\frac{π_{θ^t}(s, a)}{p(a)}, C)(r + 1_{\{s'\ne∅\}}γV_{w^t}(s') − V_{w^t}(s) )(∇_{θ^t} logπ_{θ^t}(s, a))+ λ\sum_{(s,a,r,p,s')∈B}\sum_{a'}p(a')(∇_{θ^t} logπ_{θ^t}(s, a')),\\w^{t+1}←w^t− η'\sum_{(s,a,r,p,s')∈B}min(\frac{π_{θ^t}(s, a)}{p(a)}, C)(V_{w^t}(s) − r − 1_{\{s'\ne∅\}}γV_{w^t}(s'))∇_{w^t}V_{w^t}(s) , θt+1←θt+η(s,a,r,p,s′)∈B∑min(p(a)πθt(s,a),C)(r+1{s′=∅}γVwt(s′)−Vwt(s))(∇θtlogπθt(s,a))+λ(s,a,r,p,s′)∈B∑a′∑p(a′)(∇θtlogπθt(s,a′)),wt+1←wt−η′(s,a,r,p,s′)∈B∑min(p(a)πθt(s,a),C)(Vwt(s)−r−1{s′=∅}γVwt(s′))∇wtVwt(s),
如果 s ′ s' s′是終止态 1 { s ′ ≠ ∅ } = 1 1_{\{s'\ne∅\}}= 1 1{s′=∅}=1否則為0， 上限重要性權重 m i n ( π θ t ( s , a ) p ( a ) , C ) min(\frac{π_{θ^t}(s, a)}{p(a)}, C) min(p(a)πθt(s,a),C)是離軌政策梯度的标準(Wang et al., 2016). C = 10 作為上限，以某些偏差為代價控制梯度的方差.
更新的第二項作為一個正則化器，迫使目前的預測接近舊模型的預測。權重共享時學習率 η , λ 和 η ′ η,λ和η' η,λ和η′也控制不同目标的相對權重。
圖1:VIN資料集的随機映射與我們的教育訓練環境的一些訓練配置之間的比較。在我們的自定義網格世界中，障礙物的數量随着大小而增加，但是它們占總可用空間的百分比是固定的。Agent和goal用圓圈表示，但是它們仍然占據一個單元。
4.1 Grid-world setting Grid-world設定
實驗設定：固定尺寸的2 維 grid-world,所有實體取樣基于一些固定的分布(圖1)。每一步智能體都有8個可能的移動方向,當智能體達到目标或撞牆時視為到達終止态。我們使用MazeBase (Sukhbaatar et al.， 2015)生成世界的配置和用于訓練和測試階段的代理接口。此外，我們還在Tamar et al.(2016)最初使用的16×16資料集中的均勻采樣（uniformly sampled）的地圖上評估我們的訓練後的智能體，以便與之前的工作進行直接比較。我們也測試了其他可用資料集(8×8和28×28)上的所有模型，沒有看到相對性能的顯著變化，是以在我們的評估中忽略了它們。訓練中，最優路徑的平均長度被一些值所限制，這些值在幾次訓練後逐漸增加。這使得它更有可能在訓練的早期階段就遇到目标，進而更容易适應目标特性。在我們對這個設定的所有測試中，VProp和MVProp的表現都非常好
圖2:所有模型的平均、最小和最大獎勵。在前兩個圖中，地圖大小是32×32。a和c分别展示了在VIN資料集和我們生成的64×64映射上的性能。b表示在受限的評價圖上的表現(分段線)，以及沒有(直線)。
我們的VIN實作。圖2顯示了随機開始的5次訓練中平均獲得的獎勵。值得注意的是，最初的VIN架構主要是在完全監督的環境中測試的(通過模仿學習)，在這種環境中，最好的可能路徑被指定為目标。然而，Tamar等人(2016)聲稱VIN可以在RL設定下執行，成功率為82.5%，而在16×16的map上，監督設定的成功率為99.3%。作者沒有提供更大的28×28映射資料集的結果，也沒有提供學習曲線和方差，但是總體來說，這些結果與我們從測試實作中獲得的最佳性能是一緻的。
各模型對靜态世界實驗的最終平均性能清楚地表明了VProp和MVProp的能力。在以上所有實驗中，VProp和MVProp都很快超過了基線。特别地，MVProp非常快速地學習了MDP動态上的轉換函數，該函數足夠敏銳，能夠在更大的尺寸上提供良好的值，是以在前1000次訓練中獲得了所有尺寸上的接近最優政策。
4.2 Tackling dynamic environments處理動态環境
為了測試我們的模型有效學習非靜态環境(即相對複雜的轉換函數)的能力，我們提出了一組實驗，在這些實驗中，我們允許我們的環境産生由一組固定政策控制的動态敵對實體。這些政策包括 ϵ \epsilon ϵ- noop政策，它使實體以機率 ϵ \epsilon ϵ随機朝某個方向移動或者什麼都不做，采取嚴格的敵對政策，試圖在智能體達到目标之前抓住他。我們使用第一類政策來增強我們的标準路徑規劃實驗，隻在20%的空間被agent占據的環境中生成敵人 ϵ \epsilon ϵ= 0.5，并且混合環境中有相同數量的實體，一半由固定的牆壁組成，剩下的agent有 ϵ \epsilon ϵ= 0.2。第二種政策用于生成确定性但不斷變化的環境，我們稱之為雪崩，在這種環境中，智能體的任務是盡可能快地達到目标，同時避免“墜落”實體。最後，我們提出第三種試驗，根據環境的大小，對1至6個敵對實體采用完全敵對的政策。這些場景的難度各不相同，但都需要子產品學習非常稀疏的正面獎勵，并處理更複雜的轉換函數，是以對所有測試方法都提出了強烈的挑戰。
圖3:在dymamic實驗中測試勝率的平均值、最小值和最大值。每個智能體在8x8的場景執行個體上進行訓練，其方式與靜态世界實驗類似。圖3d顯示了經過雪崩訓練後獲得的政策示例。為了更好地顯示，Agent和goal用圓圈表示，但是它們仍然占據一個單元。
由于這些新環境不是靜态的，代理需要在每一步重新計劃，迫使我們在8x8地圖上進行訓練，以減少部署循環子產品所花費的時間。但是，這使我們無需進行教育訓練即可進行訓練，因為智能體可能已經采取了随機政策成功地在較小的區域實作了目标。圖3顯示了MVProp學會了處理動态中這種新的複雜性，成功地将映射擴充到32x32，比訓練中看到的要大得多(圖3d)，大大超過了基線。
4.3 StarCraft navigation《星際争霸》類的遊戲導航
最後，我們在《星際争霸：巢穴之戰》中的導航任務上評估VProp，其中與導航相關的動作具有影響轉移函數的低級實體動力學。在《星際争霸》中，通常要計劃圍繞敵方機關的軌迹，因為這些機關會自動發起攻擊，如果距離太近，将會幹擾甚至摧毀我們的智能體。雖然規劃标準星際争霸地圖大小的軌迹不在這項工作範圍之内，但是當考慮敵人靠近瓶頸區域的情況時，這個問題已經變得非常困難，
是以，我們可以在小地圖上測試我們的架構，以模拟這些場景的執行個體。
我們使用TorchCraft (Synnaeve et al.， 2016)設定環境并提取場景中随機生成的單元的位置和類型。狀态空間大于先前的實驗和正獎勵可能非常稀疏,是以我們采用a mixed curriculum,允許模對單元和位置進行采樣，使得智能體在訓練早期就能得到正獎勵,加快訓練(請注意，這也是VIN基線有機會完成任務的要求(Tamar et al ., 2016)。如圖4b所示，在低水準的噪聲條件下，MVProp能對移動行為進行規劃，完成目标。與VIN基線相比，更好的樣本效率意味着可以更準确地學習狀态-動作轉移函數的模型，我們還通過在max-pooling操作之後添加兩個卷積層來直接對場景進行評估，得到了學習狀态特性的能力:圖4c，需要更多的時間來對實體進行條件設定，但最終達到類似的最終性能。在這兩種情況下，即使訓練早期提供正獎勵，VIN也很難正确地适應更複雜的轉移函數。
圖4:星際争霸的導航結果。圖4a顯示了訓練後期随機場景中生成的軌迹。紅色和藍色的疊加(不顯示給智能體)表示與每個敵人實體互動所需的距離。
5 Conclusions 結論
使用從資料中學習的規劃有助于解決大而空間結構化的任務，然而這些需要高效樣本來迅速适應本地環境動态，這樣他們能提供一個靈活的規劃視野不用收集新資料。我們的工作表明，當考慮到任務的動态性時，這種規劃可以通過強化學習成功地學習，當這些模型應用于二維路徑規劃任務時有強大的泛化能力。此外，我們還證明了我們的方法甚至可以在環境具有動态的、有噪聲的、敵對的元素或具有高維觀察空間的情況下進行推廣，使它們能夠用于相對複雜的任務。計算成本限制了這些planner在更難的任務方面的應用,因為深度随着智能體必須解決的路徑長度增加而增加，然而使用VI模型的結構作為低水準planner已經成功地處理複雜的互動任務(1.1節),是以我們期望為這種類型的工作提供了一種通過強化學習來訓練的端到端方法,即使是在不同的類圖結構中找到的尋路任務(至少我們有相關的卷積運算)。最後，VProp和MVProp應用的有趣場所是移動機器人和視覺跟蹤(Lee et al.， 2017;Bordallo et al.， 2015)，我們的工作可以用來學習任意的傳播函數，并模組化一個廣泛的潛在函數。