蟲匯聚之所

先貼翻譯

之後有時間整理再慢慢弄

0. 概述
該文章提出了一個關於聯合強化學習算法的廣泛的類別, 針對包含隨機單元的有連接的網絡, 這些算法, 稱之為強化算法, 看上去像是沿著某個方向對權重進行調整, 依賴於期望強化的梯度, 比如在即時強化的任務中和確定受限的延遲強化形式的任務中, 不用顯式地計算梯度估計甚至存儲這些計算這種估計的信息. 會給出這種算法的具體例子, 有一些和現存的確定的算法有很近的聯系, 有些是新穎的但是卻可能由於其正確性比較有趣. 當然也給出了一些展現怎樣一個算法能夠被自然地和反向傳播(Back propagation)集成的結果. 文章以一個由關於這個算法的使用的一系列額外問題組成的簡短的討論而結束, 包括那些是已知的關於受限制的特性以及更遠的可能可以用來幫助開發相似的但是潛在更強的強化學習算法的考慮.

1. 介紹
強化學習的一個通用的框架包含許多問題來自許多在一個極端去學習控制其他的函數優化, 在這些獨立的領域的研究趨向於去分析不同的獨立的問題集合, 這就像是對於自動化agent在現實環境下的操作的一個有效的強化學習技術將不得不聯合解決所有的這些問題. 然而仍然存在有用的關註於強化學習問題的受限的形式的研究策略來簡化使得問題易於處理. 重要的是對於大多數有挑戰的問題的結果將會可能需要集成許多可應用的技術.

在這篇文章中, 我們提出了對於確定的相關任務的算法的分析性結果, 意味著學習者只需要表現輸入輸出映射, 並且, 有一個額外的限制性, 即, 包含即時的強化, 也就是被提供給學習者的強化只通過大多數輸入輸出對來進行確定.

當然, 延遲性的強化也是很重要的, 之後受到了應有的關註, 一個廣泛使用的來開發應對這樣的任務的算法的方法, 即將一個即時強化學習者和一個自適應預測者或者基於Sutton提出來的時間差分法的批評者(critic), 這個**"actor-critic"算法, Barto, Sutton和Anderson都有研究, Sutton將其格式變得清晰, 比如Watkins的Q-learning算法**

一個更遠的假設是學習者的搜索行為, 通常是一個對於任意形式的強化學習算法來說必要的部分, 通過學習者隨機性的輸入和輸出來提供. 這裏有一個通用的方法來實現期望的搜索行為, 值得註意的是其他的策略有時候在特定的案例裏面有效, 包括系統化搜索(systematic search)或者明顯的最優選擇的連續選擇(consistent selection). 後面的策略當選擇動作的女神由估計那些是過度樂觀以及哪些在連續的經驗下變得更加現實起作用, 比如Nilsson的A*搜索.

另外, 所有的結果將會通過有連接的網絡被再次制定, 主要關註點為跟從或者估計相關梯度的算法. 當然這樣的算法我們知道通常會有一些限制, 這也是它們的研究是有用的原因. 首先, 作為反向傳播的經驗, 這個梯度看上去對於生成算法來說提供了一個有力的和富有啟發性基礎, 並且是易於實現的和在某些情況下效果很好. 其次, 當需要更為覆雜的算法的時候, 梯度計算通常作為這樣的算法的核心. 當然, 對於已有的確定算法的範圍類似產生這樣一個梯度分析的算法, 我們對於他們的理解可能增強了.

另一個這裏所提出的算法的有區別的特征是, 它們能夠被概略地描述為統計意義上的攀爬一個合適的梯度, 它們設法不用顯式地計算一個梯度估計或者存儲這些能夠被直接計算的信息. 這就是為什麽它們被稱之為simple的原因. 可能一個更具信息化的形容詞為無模型基礎的(non-model-based), 則會在文章後期進行討論.

2. 連接形網絡的強化學習
這裏給出部分符號的解釋

rrr: 增強信號
xix^ix 
i
 : 是一個輸入向量, xi=(xi1,xi2,...,xin)x^i=(x^i_1, x^i_2, ..., x^i_n)x 
i
 =(x 
1
i
​    
 ,x 
2
i
​    
 ,...,x 
n
i
​    
 )
yiy_iy 
i
​    
 : 是一個值, 代表第iii個輸出單元的值
WWW: 權值矩陣, 類似NN裏面的邊的權值
wiw^iw 
i
 : 權值向量, 即wi=(wi1,wi2,...,win)w^i=(w_{i1}, w_{i2}, ..., w_{in})w 
i
 =(w 
i1
​    
 ,w 
i2
​    
 ,...,w 
in
​    
 )
對於每一個iii, 我們定義gi(ξ,xi,wi)=Pr(yi=ξ∣xi,wi)g_i(\xi, x^i, w^i)=Pr(y_i = \xi | x^i, w^i)g 
i
​    
 (ξ,x 
i
 ,w 
i
 )=Pr(y 
i
​    
 =ξ∣x 
i
 ,w 
i
 ), gig_ig 
i
​    
 是一個概率質量函數, 所謂概率質量函數即離散的概率密度函數.

質量函數的數學定義為, 假設XXX是一個定義在可數樣本空間SSS上的離散隨機變量 S⊆RS ⊆ RS⊆R，則其概率質量函數 fX(x)f_X(x)f 
X
​    
 (x) 為
KaTeX parse error: No such environment: equation at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ f_X(x)=\left\{…

當yiy_iy 
i
​    
 連續自然就變成概率密度函數, wiw^iw 
i
 包含所有的跟第iii個單元的相關的輸入輸出行為的參數, 一個更為準確的定義為
gi(ξ,wi,xi)=Pr(yi=ξ∣W,xi)g_i(\xi, w^i,x^i )=Pr(y_i=\xi|W, x^i)
g 
i
​    
 (ξ,w 
i
 ,x 
i
 )=Pr(y 
i
​    
 =ξ∣W,x 
i
 )

我們知道一來一回類似神經網絡的BP訓練, 那麽強化學習之中, 在新的輸入之前, 前一步的輸入之後, 稱一個時間步, 我們主要關註每個時間步的細節.

我們定義一個隨機半線性單元, 即輸出是yiy_iy 
i
​    
 , 由給定的概率分布得到, 其概率質量函數為
pi=fi(si)p_i=f_i(s_i)
p 
i
​    
 =f 
i
​    
 (s 
i
​    
 )

其中fif_if 
i
​    
 是可微的壓縮映射, 並且有:
si=(wi)Txi=∑jwijxjs_i=(w^i)^Tx^i=\sum_j{w_{ij}x_j}
s 
i
​    
 =(w 
i
 ) 
T
 x 
i
 = 
j
∑
​    
 w 
ij
​    
 x 
j
​    

一個特殊的隨機半線性單元是一個伯努利半線性單元, 即yiy_iy 
i
​    
 是一個隨機的伯努利變量, 參數是pip_ip 
i
​    
 , 輸出要麽是0, 要麽是1. 即Pr(yi=0∣wi,xi)=1−piPr(y_i=0|w^i, x^i)=1-p_iPr(y 
i
​    
 =0∣w 
i
 ,x 
i
 )=1−p 
i
​    
 以及Pr(yi=1∣wi,xi)=piPr(y_i=1|w^i, x^i)=p_iPr(y 
i
​    
 =1∣w 
i
 ,x 
i
 )=p 
i
​    
 , 因此給出該單元的形式
KaTeX parse error: No such environment: equation at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ g_i(\xi, w^i, …
玻爾茲曼機就是用的上述類型的單元

關於壓縮映射, 可以使用我們熟悉的logistics函數
fi(si)=11+e−sif_i(s_i)=\frac{1}{1+e^{-s_i}}
f 
i
​    
 (s 
i
​    
 )= 
1+e 
−s 
i
​    
 
 
1
​    

與上述單元結合起來, 稱之為伯努利-邏輯斯蒂單元

特別地, 假設一個單元這樣來計算它的輸出:
KaTeX parse error: No such environment: equation at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ y_i=\left\{ \b…

其中η\etaη是依據給定的分布Ψ\PsiΨ隨機產生
利用伯努利半線性單元的定義, 我們發現

如果$\Psi$可微, 則其壓縮映射可以為
fi(si)=1−Ψ(−si)
fi(si)=1−Ψ(−si)
3. 期望的強化性能標準
這裏給出了一些衡量強化的指標, 對於一個強化學習網絡來說, 我們的性能測量為E(r∣W)E(r|W)E(r∣W), 其中EEE是期望, rrr是強化信號, WWW是網絡的權值矩陣.

我們需要使用期望值是因為潛在的隨機性:

對於網絡來說, 輸入的環境的選擇
輸出的網絡的選擇對應任意特定的輸入
環境的強化值的選擇, 對於特定的輸入輸出對
註意到, E(r∣W)E(r|W)E(r∣W)獨立於時間的才有意義, 我們的目標就是找到WWW, 使得E(r∣W)E(r|W)E(r∣W)最大化.

4. 強化算法
我們定義權值在強化學習裏面的改變如下所示:
Δwij=αij(r−bij)eij\Delta w_{ij}=\alpha_{ij}(r-b_{ij})e_{ij}
Δw 
ij
​    
 =α 
ij
​    
 (r−b 
ij
​    
 )e 
ij
​    

其中αij\alpha_{ij}α 
ij
​    
 是學習率因子, bijb_{ij}b 
ij
​    
 是強化的基準(baseline), 並且有
eij=∂lngi∂wije_{ij}=\frac{\partial ln g_i}{\partial w_{ij}}
e 
ij
​    
 = 
∂w 
ij
​    
 
∂lng 
i
​    
 
​    

假設bijb_{ij}b 
ij
​    
 條件獨立於yi,W,xiy_i, W, x^iy 
i
​    
 ,W,x 
i
 以及非負的αij\alpha_{ij}α 
ij
​    
 , 主要依賴於wiw^iw 
i
 和ttt, 任何具有上述形式的算法都稱之為一個強化算法(REINFORCE Algorithm)

其實這個名字是縮寫, 即**“REward Increment = Nonnegative Factor times Offset Reinforcement times Characteristic Eligibility”**

定理1
對於任意的REINFORCE算法, E{ΔW∣W}E\{\Delta W|W\}E{ΔW∣W}和∇WE{r∣W}\nabla_WE\{r|W\}∇ 
W
​    
 E{r∣W}的內積是非負的, 更進一步, 如果αij>0\alpha_{ij}>0α 
ij
​    
 >0, 那麽當僅當∇WE{r∣W}=0\nabla_WE\{r|W\}=0∇ 
W
​    
 E{r∣W}=0, 內積才為0, 如果αij\alpha_{ij}α 
ij
​    
 是和i,ji,ji,j獨立的話, 有E{ΔW∣W}=α∇WE{r∣W}E\{\Delta W|W\}=\alpha\nabla_WE\{r|W\}E{ΔW∣W}=α∇ 
W
​    
 E{r∣W},

我們上面所提及的∇WE{r∣W}\nabla_WE\{r|W\}∇ 
W
​    
 E{r∣W}是性能度量在權值空間上的梯度, E{ΔW∣W}E\{\Delta W|W\}E{ΔW∣W}為權值空間的平均更新向量, 對於任意的REINFORCE算法來說.

特別地, 這意味著對於任意的這樣的算法, 在權值空間上的平均更新向量在這個性能指標增長的方向上, 該定理的最後一句, 等價於對於每一個權值wijw_{ij}w 
ij
​    
 , 有
(r−bij)∂lngi∂wij\frac{(r-b_{ij})\partial ln g_i}{\partial w_{ij}}
∂w 
ij
​    
 
(r−b 
ij
​    
 )∂lng 
i
​    
 
​    

這個是對∂E{r∣W}/∂wij\partial E\{r|W\}/\partial w_{ij}∂E{r∣W}/∂w 
ij
​    
 的無偏估計

我們利用伯努利單元來試著計算, 對於伯努利單元呢, 參數只有pi=Pr(yi=1)p_i=Pr(y_i=1)p 
i
​    
 =Pr(y 
i
​    
 =1), 我們可以算出
KaTeX parse error: No such environment: equation at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ g_i(y_i,p_i)=\…
進而得到
KaTeX parse error: No such environment: equation at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ e_i=\frac{\par…
我們取bi=1,αi=ρipi(1−pi)b_i=1, \alpha_i=\rho_ip_i(1-p_i)b 
i
​    
 =1,α 
i
​    
 =ρ 
i
​    
 p 
i
​    
 (1−p 
i
​    
 )
得到
Δpi=ρir(yi−pi)\Delta p_i=\rho_ir(y_i-p_i)
Δp 
i
​    
 =ρ 
i
​    
 r(y 
i
​    
 −p 
i
​    
 )

伯努利單元十分簡單, 現在我們考慮伯努利半線性單元
利用鏈式法則, 可以得到
∂lngi(yi,wi,xi)∂wij=∂lngi(yi,wi,xi)∂pi∂pi∂si∂si∂wij=yi−pipi(1−pi)f′i(si)xj\frac{\partial lng_i(y_i, w^i, x^i)}{\partial w_{ij}}=\frac{\partial lng_i(y_i, w^i, x^i)}{\partial p_i}\frac{\partial p_i}{\partial s_{i}}\frac{\partial s_i}{\partial w_{ij}}=\frac{y_i-p_i}{p_i(1-p_i)}f'_i(s_i)x_j
∂w 
ij
​    
 
∂lng 
i
​    
 (y 
i
​    
 ,w 
i
 ,x 
i
 )
​    
 = 
∂p 
i
​    
 
∂lng 
i
​    
 (y 
i
​    
 ,w 
i
 ,x 
i
 )
​    
  
∂s 
i
​    
 
∂p 
i
​    
 
​    
  
∂w 
ij
​    
 
∂s 
i
​    
 
​    
 = 
p 
i
​    
 (1−p 
i
​    
 )
y 
i
​    
 −p 
i
​    
 
​    
 f 
i
′
​    
 (s 
i
​    
 )x 
j
​    

如果是logistic函數, 註意到其性質:
f′i(si)=fi(si)(1−fi(si))=pi(1−pi)f'_i(s_i)=f_i(s_i)(1-f_i(s_i))=p_i(1-p_i)
f 
i
′
​    
 (s 
i
​    
 )=f 
i
​    
 (s 
i
​    
 )(1−f 
i
​    
 (s 
i
​    
 ))=p 
i
​    
 (1−p 
i
​    
 )

故上式可以轉化為
∂lngi(yi,wi,xi)∂wij=(yi−pi)xj\frac{\partial lng_i(y_i, w^i, x^i)}{\partial w_{ij}}=(y_i-p_i)x_j
∂w 
ij
​    
 
∂lng 
i
​    
 (y 
i
​    
 ,w 
i
 ,x 
i
 )
​    
 =(y 
i
​    
 −p 
i
​    
 )x 
j
​    

取αij=α,bij=0\alpha_{ij}=\alpha, b_{ij}=0α 
ij
​    
 =α,b 
ij
​    
 =0可以得到
Δwij=αr(yi−pi)xj\Delta w_{ij}=\alpha r(y_i-p_i)x_j
Δw 
ij
​    
 =αr(y 
i
​    
 −p 
i
​    
 )x 
j
​    

我們可以和關聯反饋-處罰算法(associative reward-penalty)比較一下, 這裏給出他們的格式
Δwij=α[r(yi−pi)+λ(1−r)(1−yi−pi)]xj\Delta w_{ij}=\alpha [r(y_i-p_i)+\lambda(1-r)(1-y_i-p_i)]x_j
Δw 
ij
​    
 =α[r(y 
i
​    
 −p 
i
​    
 )+λ(1−r)(1−y 
i
​    
 −p 
i
​    
 )]x 
j
​    

其中0&lt;λ&lt;10&lt;\lambda&lt;10<λ<1, 如果λ=0\lambda = 0λ=0, 則變為關聯反饋遲鈍算法(associative reward-inaction)

Sutton提出了另一種策略
Δwij=α(r−r¯)(yi−pi)xj\Delta w_{ij}=\alpha (r-\bar{r})(y_i-p_i)x_j
Δw 
ij
​    
 =α(r− 
r
ˉ
 )(y 
i
​    
 −p 
i
​    
 )x 
j
​    

其中
r¯(t)=γr(t−1)+(1−γ)r¯(t−1)\bar{r}(t)=\gamma r(t-1)+(1-\gamma)\bar{r}(t-1)
r
ˉ
 (t)=γr(t−1)+(1−γ) 
r
ˉ
 (t−1)

類似指數平滑的策略