CS229 Lecture 20

---

POMDPs(Partially Observed MDPs)
Policy search
Reinforce
Pagasus
conclusion

---

回顧

$s_{t+1}=A{s}_t+B{a}_t+w_t$

$y_t=C{s}_t+v_t$

$A_{t+1}:a_{t+1}=L_t{s}_t$

在LQR問題中，因為噪聲等因素的存在無法觀測到真實狀態(tài)$s_t$，只能通過混雜著噪聲的觀察狀態(tài)$y_1，y_2,?,y_t$來得出下一步的動作。首先需要得出對$s_t$的最佳估計$s_{t|t}$，通過Kalman Filter可以得出$s_{t|y_1,y_2,?,y_t}～N(s_{t|t},{\Sigma }_{t|t})$,然后通過$a_t:=L_t,s_{t|t}$。

---

POMDPs

部分觀測馬爾可夫決策過程定義為一個元組$(S,A,Y,\{P_{sa}\},\mathcal{O},T,T)$,其中$Y$是所有可能觀測值的集合，${\mathcal{O}}_s$是觀測所屬的分布,每次觀測中在$s_t$下觀測為$y_t$服從$y_t～{\mathcal{O}}_{st}$。

---

Policy search

$policysearch$ 和之前LQR方式不同在于，之前通過最大化值函數(shù)$V^{?}$進而得出最佳的${\pi }^{?}$。這里的$policysearch$是直接對$policy$進行選取。

定義$\Pi$為$policy$的合集，需要在$\Pi$中搜索到好的$\pi$,其中$\pi \in \Pi$,這里十分類似于在最前面學習的監(jiān)督學習，在假設集合$\mathcal{H}$中搜索到一個好的假設。

定義一個隨機$policy$為一個$\pi :S\times A\to \mathbb{R}$ 的函數(shù)，這里$\pi (s,a)$是在狀態(tài)$s$下采取動作$a$的概率。注$\sum \pi (s,a)=1,\pi (s,a)\ge 0$。

課上使用$Policysearch$的例子：假設一個倒立擺，其中擺與垂線的夾角為$?$小車的位置為$x$,現(xiàn)在小車無非兩個選擇向左運動或者向右運動。假設向右運動為$a_1$，向左為$a_2$。假設有：${\pi }_{\theta }(s,a_1)=\frac{1}{1+e^{?{\theta }^{T}s}},{\pi }_{\theta }(s,a_2)=1?\frac{1}{1+e^{?{\theta }^{T}s}}$。這里$$\begin{gathered} s= \\ ?\begin{array}{c}1\\ x\\ \dot{x}\\ ?\\ \dot{?}\end{array}? \end{gathered}$$,$\theta =?\begin{array}{c}0\\ 0\\ 0\\ 1\\ 0\end{array}?$，那么$p(a=a_1)=\frac{1}{1+e^{?{\theta }^{T}s}}=\frac{1}{1+e^{??}}$。下圖就是小車向右運動和夾角$?$的關系。例如當夾角為正時，我們需要向右移動以保證倒立擺不倒下。

實際上我們的目標是最大化預期回報${\max }_{\theta }E[R(s_0,a_0)+?+R(s_T,a_t)|{\pi }_{\theta },s_0]$

注：當動作是多個離散的選擇是可以選擇$softmax$函數(shù)，動作是連續(xù)的可以選取動作的密度函數(shù)。

---

Reinforce algorithm

假設$s_0$是一個固定的初始狀態(tài)，我們的期望是：${\max }_{\theta }E[R(s_0,a_0)+?+R(s_T,a_t)|{\pi }_{\theta },s_0]$

其中回報的期望為：

$$\begin{gathered} E[R(s_0,a_0)+?+R(s_T,a_t)|{\pi }_{\theta },s_0] \\ =\sum _{s_0,a_0,s_1,?,s_t}p(s_0,a_0,s_1,?,s_t)[R(s_0,a_0)+?+R(s_T,a_t)|{\pi }_{\theta },s_0] \\ =\sum _{s_0,a_0,s_1,?,s_t}p(s_0){\pi }_{\theta }(s_0,a_0)p_{s_0,a_0}(s_1){\pi }_{\theta }(s_1,a_i)?{\pi }_{\theta }(s_t,a_t)[R(s_0,a_0)+?+R(s_T,a_t)|{\pi }_{\theta },s_0] \end{gathered}$$

算法的流程為：
$Loop$??{

???? 抽樣 $s_0,a_0,s_1,a_1,?,s_t,a_t$
???? 計算收益$payoff=[R(s_0,a_0)+?+R(s_T,a_t)|{\pi }_{\theta },s_0]$
???? 更新$\theta$的方式為：$\theta :=\theta +\alpha [\frac{{?}_{\theta }{\pi }_{\theta }(s_0,a_0)}{{\pi }_{\theta }(s_0,a_0)}+?+\frac{{?}_{\theta }{\pi }_{\theta }(s_T,a_T)}{{\pi }_{\theta }(s_T,a_T)}]?payoff$
}

上述算法之所以使用梯度上升的方式更新$\theta$見下面推導：

鏈式求導原則
$\frac{d}{d\theta }f(\theta )g(\theta )h(\theta )=f^{{}^{\prime }}(\theta )g(\theta )h(\theta )+f(\theta )g^{{}^{\prime }}(\theta )h(\theta )+f(\theta )g(\theta )h^{{}^{\prime }}(\theta )$

我們的目的是使得期望回報最大因此我們對回報的期望求導：
$$\begin{gathered} {?}_{\theta }E[payoff] \\ =\sum _{s_0,a_0,s_1,?,s_t}[p(s_0)({?}_{\theta }{\pi }_{\theta }(s_0,a_0))p_{s_0,a_0}(s_1){\pi }_{\theta }(s_1,a_i)?{\pi }_{\theta }(s_t,a_t)+p(s_0){\pi }_{\theta }(s_0,a_0)p_{s_0,a_0}(s_1)({?}_{\theta }{\pi }_{\theta }(s_1,a_1))?{\pi }_{\theta }(s_t,a_t)+ \\ p(s_0){\pi }_{\theta }(s_0,a_0)p_{s_0,a_0}(s_1){\pi }_{\theta }(s_1,a_i)?({?}_{\theta }{\pi }_{\theta }(s_t,a_t))]?payoff \\ =\sum _{s_0,a_0,s_1,?,s_t}p(s_0){\pi }_{\theta }(s_0,a_0)p_{s_0,a_0}(s_1){\pi }_{\theta }(s_1,a_i)?{\pi }_{\theta }(s_t,a_t)?[\frac{{?}_{\theta }{\pi }_{\theta }(s_0,a_0)}{{\pi }_{\theta }(s_0,a_0)}+?+\frac{{?}_{\theta }{\pi }_{\theta }(s_T,a_T)}{{\pi }_{\theta }(s_T,a_T)}]?payoff \\ =\sum _{s_0,a_0,s_1,?,s_t}p(s_0,s_1,?,s_t,a_t)?[\frac{{?}_{\theta }{\pi }_{\theta }(s_0,a_0)}{{\pi }_{\theta }(s_0,a_0)}+?+\frac{{?}_{\theta }{\pi }_{\theta }(s_T,a_T)}{{\pi }_{\theta }(s_T,a_T)}]?payoff \\ =E[\frac{{?}_{\theta }{\pi }_{\theta }(s_0,a_0)}{{\pi }_{\theta }(s_0,a_0)}+?+\frac{{?}_{\theta }{\pi }_{\theta }(s_T,a_T)}{{\pi }_{\theta }(s_T,a_T)}]?payoff \end{gathered}$$

在POMDPs也可以使用$policysearch$，假設有$s$的近似值$\hat{s}$ (可以通過Kalman Filter 計算$\hat{s}=s_{t|t}$)。如${\pi }_{\theta }(\hat{s},a)=\frac{1}{1+e^{?\theta \hat{s}}}$

---

Pegasus

Pegasus是Policy Evaluation of Gradient And Search Using Scenarios的縮寫。我們一般馬爾可夫的過程是$s_0\stackrel{\pi (s_0)}{?}{s}_1\stackrel{\pi (s_1)}{?}{s}_2\stackrel{\pi (s_2)}{?}{s}_3?\stackrel{\pi (s_{T?1})}{?}{s}_T$,在實際應用中一般會創(chuàng)建一個模擬來模擬輸入$s_t$和$s_t$得到$s_{t+1}$的過程，我們一般假設$s_{t+1}=A{s}_t+B{a}_t+w_t$可以知道每次模擬器生產$s_{t+1}$的時候都帶有隨機噪聲，那么當我們在$policy$搜索時候，如果$policy$不同且$w_t$的噪聲每次還有很大差異就很難找到最優(yōu)的$policy$，因此此時存在多個變化的量，無法根據(jù)最大回報來得出最佳的$policy$。因為我們的模擬器因為要模擬噪聲，那么每次都會生成隨機數(shù)來實現(xiàn)，即使是相同的策略，得出的回報也會不同。我們需要做的就是在每個場景固定一組隨機數(shù)，基于這個隨機數(shù)場景計算各個$policy$的回報，然后平均多個隨機數(shù)序列場景然后評估出最佳的$policy$ 。這就是Pegasus名字的由來。

一般來說直接的決策(如：自動駕駛、倒立擺)使用$policysearch$比較好，而對于前面的決策對后續(xù)回報有影響的(如：圍棋、俄羅松方塊)最好選擇值迭代方式找到最佳的$policy$

注：pegasus 請參見Lecture 20 48分～65分的講解

---

結論

CS229 2008系列完結！

總結

以上是生活随笔為你收集整理的CS229 Lecture 20的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。