# Reinforcement Learning: An Introduction_Chapter 13 Policy Gradient Methods
###### tags: `Reinforcement Learning` `Second Edition`

課本範圍：321~337

[相關連結_Sutton_2nd](http://incompleteideas.net/book/the-book-2nd.html)
[David Silver_bilibili_簡中字幕](https://www.bilibili.com/video/BV1kb411i7KG/)
[程式碼參考_ShangtongZhang](https://github.com/ShangtongZhang/reinforcement-learning-an-introduction)
[程式碼參考_dennybritz](https://github.com/dennybritz/reinforcement-learning)
[程式碼參考_弱弱的我](https://github.com/shaoeChen/Reinforcement-Learning-An-Introduction-Record)
[LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions](https://github.com/LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions)

這一章我們要來聊聊新的東西。目前為談的幾乎都是action-value methods；它們學習actions的values，然後再基於它們所估測的action-value來選擇action^1^。這一章我們會考慮學習一個parameterized policy，這可以在不需要諮詢(consulting)value function的情況下選擇一個action。value function還是可以拿來學習policy parameter，不過對於選擇action來說，已經是非必要的了。我們使用符號$\theta \in \mathbb{R}^{d'}$來代表策略(policy)的參數向量(parameter vector)。然後我們就可以把$\pi(a\vert s, \theta)=\mathtt{Pr}\left\{A_t=a \vert S_t=s, \theta_t=\theta \right\}$寫做一個機率，這個機率就是，environment在時間$t$、狀態(state)$s$、其參數(parameter)為$\theta$的情況下，在時間$t$被選擇到的action的機率。如果你的方法也有用到所學習到的value function，那跟之前一樣，其value function的weight vector會像是在$\hat{v}(s, \mathbf{w})$一樣，以$\mathbf{w}\in \mathbb{R}^d$來表示，

:::success
1: 唯一例外的就是Section 2.8談到的gradient bandit algorithms。事實上，在single-state bandit的案例中，該部份是經歷過很多相同的step，就像是我們這邊所談的完整的MDPs一樣。回想一下該章的內容對閱讀本章做好準備。
:::

這一章所考慮的方法是，基於相對於策略參數的某些標量效能度量$J(\theta)$的梯度來學習策略參數(policy parameter)。這些方法會尋找最大化效能，因此，它們在$J$的更新會近似梯度上升(gradient ascent)：
$$
\theta_{t+1} = \theta_t + \alpha \widehat{\nabla J(\theta_t)} \tag{13.1}
$$

其中$\widehat{\nabla J(\theta_t)} \in \mathbb{R^{d'}}$是一個隨機估測值，這估測值我們期望它能夠近似對於其參數$\theta_t$效能度量的梯度。所有依循這通用模式的方法我們稱之為策略梯度方法(policy gradient methods)，無論它們是否有無學習一個近似價值函數(approximate value function)。這種同時學習policy與value functions的近似值的方法通常稱為actor-critic methods，其中"actor"這個字是參照學習到的策略(policy)，然後"critic"則是學習到的價值函數(value function)，這value function通常是state-value function。

* episodic case，其效能的定義是參數化策略(parameterized policy)下的起始狀態(start state)的值(value)
* continuing case，其效能如Section 10.3所給出的平均報酬率(average reward rate)

我們可以用很相似的方式來解釋用於這兩種情況的演算法。
## 13.1 Policy Approximation and its Advantages
在policy gradient methods中，policy可以以任意方法來做參數化(parameterized)，只要$\pi(a\vert s, \theta)$相對其參數是可微的就行，也就是說，只要$\nabla \pi(a \vert s, \theta)$($\pi(a\vert s, \theta)$相對於$\theta$的分量(components)的偏導數的column vector)存在，並且對所有的$s\in\mathcal{S}, a\in\mathcal{A}(s), \theta\in\mathbb{R}^{d'}$都是有限的就可以。實務上，為了確保agent能夠持續的探索(exploration)，我們通常要求policy不會變成一個確定性的policy(即$\pi(a\vert s,\theta)\in(0, 1)$ for all $s, a,\theta$)。這一章我們會來介紹discrete action spaces中常見用的參數化方式，並且指出這方法相對於action-value methods有什麼優點。policy-based methods也提出一種常見用於continuous action spaces的方法，這會在後面的Section 13.7提到。

如果action space是discrete(離散的)，然後這空間沒有很大，那有一個很自然而且又常見的參數化方法就是為每個state-action pair弄個參數化的數值偏好$h(s, a, \theta)\in \mathbb{R}$。在每個state中，最愛的那個actions我們就給它一個比較高的機率讓人可以選到，舉例來說，根據一個exponential soft-max distribution：
$$
\pi(a\vert s, \theta) \dot{=} \dfrac{e^{h(s, a,\theta)}}{\sum_b e^{h(s, b, \theta)}} \tag{13.2}
$$

其中$e \approx 2.71828$是[自然對數(natural logarithm)](http://terms.naer.edu.tw/detail/255413/)的底數。可以注意一下，分母就是我們所需要的，這可以讓每個state裡面有的action的機率總和為1。這種參數化類型就稱為soft-max in action preferences。

這種action preferences本身可以被任意的參數化。舉例來說，它們也許可以用深度神經網路來計算，那$\theta$就會是網路的權重向量。或者你也可以只是簡單的以線性來處理(使用特徵向量$\mathbf{x}(s, a)\in\mathbb{R}^{d'}$)：
$$
h(s,a,\theta) = \theta^T\mathbf{x}(s, a)\tag{13.3}
$$

就像是在Section 9.5中談到的那樣。

根據soft-max in action preferences來參數化策略(policy)的一個優點就是，近似策略(approximate policy)是可以接近確定性策略的(deterministic policy)，而使用$\epsilon$-greedy在action values上選擇action的這種方式始終都存在著一個$\epsilon$的機率來隨機選擇action。當然啦，我們可以基於action values，然後根據soft-max distribution來選擇action，不過單憑這點可能沒有辦法讓你的policy接近確定性策略(deterministic policy)。相反的，action-value estimates會收斂到它們相對應的真實值(true values)，這兩者之間的差異會是有限的，從而將action的選擇轉為0、1之外的特定機率。如果soft-max distribution包含溫度參數，那溫度就可以隨著時間的推移而降低來接近確定性(值?)，不過，實務上，如果你沒有更多關於true action values的先驗知識，你要怎麼去規劃這個降溫的過程，甚至怎麼去設置那個初始溫度。action preferences是不一樣的，因為並沒有去接近特定值；它們是被驅使著去產生最佳隨機策略(optimal stochastic policy)。如果optimal policy是確定性的，那optimal action的偏好(preference)就會是無限高於所有suboptimal actions(如果參數化允許的話)。

那根據soft-max in action preferences參數化策略的第二個優點就是，它可以讓actions的選擇有任意的機率。在那些明顯的函數近似的問題中，最佳的近似策略也許是隨機的。舉例來說，在信息不是那麼完善的卡牌遊戲中，最佳玩法通常是用特定的機率來做兩種不同的玩法，像是blung in Poker(畫唬爛?)。action-value methods並沒有自然求解隨機最佳策略(stochastic optimal policies)的方法，而策略近似方法(policy approximating)是有的，如Example 13.1所示。

:::info
Example 13.1 Short corridor with switched actions

考慮下圖小插畫中的小走廊網格世界(small corridor gridworld)。一如往常的，每一個step的rewrad都是$-1$。在這三個nonterminal states都只有兩個actions可以選擇，右跟左。在第一、第三個states，這兩個actions都會有很常見的結果，就是左、右(第一個state的左是停在原地)，但是在第二個state是反過來的，選擇左會往右，選擇右會往左。這個問題是很難的，因為所有的states在function approximation下看起來都是一樣的。特別是，我們定義對於所有的$s$，其$\mathbf{x}(s, \text{right})=[1, 0]^T$、$\mathbf{x}(s, \text{left})=[0, 1]^T$。使用$\epsilon$-greedy的action-value methods會迫使我們在兩個策略之間做選擇：
1. 有很高的機率，高到有$1 - \epsilon/2$的機率在所有steps中選擇右
2. 相同高的機率在所有的time steps選擇左

如果$\epsilon=0.1$，那這兩個policies在start state的value就會小於$-44$與$-82$，如下圖所示：

如果有一個方法可以學習用一個特定的機率來選擇右，那這方法會明顯得到較好的結果。這最佳機率大約是$0.59$，得到的value大概是$-11.6$。
:::

或許policy parameterization相較於action value parameterization所具有的最簡單的優勢就是，policy可以用更簡單的函數來做近似(approximate)。兩者之間的問題在於複雜度不同。對某些人來說，action-value function是比較簡單的，因為它們更容易近似。但對某些人來說，policy才是比較簡單的。通常policy-based method會學的比較快，並產生更好的漸近策略(asymptotic poliocy)(as in Tetris; see S¸im¸sek, Alg´orta, and Kothiyal, 2016)。

最後，我們注意到，policy parameterization的選擇有時候是將關於你所期望的策略形式的先驗知識注入強化學習系統的好方法。這通常是使用policy-based learning method的最重要的原因。

## 13.2 The Policy Gradient Theorem
policy parameterization(策略參數化)相對於$\epsilon$-greedy action selection除了實際優勢之外，還有一個重要的理論優勢。

* continuous policy parameterization，action probabilities會隨著學習到的參數的變化有著平穩的變化
* $\epsilon$-greedy selection，如果估測的action values的一咪咪的小變化導致不同的action有著最大值，這時候它的action probabilities就會有急劇的變化

很大的程度因為這個原因，相較於action-value methods，policy-gradient methods能夠有比較強的收斂性的保證。特別是，policy依賴於參數的連續性讓policy-gradient能夠近似梯度上升(13.1)。

episodic與continuing，這兩種情況對於效能度量$J(\theta)$的定義不一樣，因此，某種程度來說是需要分開處理的。儘管如此，我們還是會試著把兩種情況做個統一，用個符號來表示這個理論結果。

這一節先來處理episodic case，這邊我們把效能度量定義為episode的start state的value。我們可以通過假設每一個episode從某個特定的state $s_0$開始(非隨機)，在不失一般性的情況下來簡化符號。我們把這個效能度量定義為：
$$
J(\theta) \dot{=} v_{\pi_\theta}(s_0) \tag{13.4}
$$

其中$v_{\pi_\theta}$為$\pi_\theta$的true value function，policy則是由$\theta$所決定。這邊開始我們的討論會假設是這些episodic case都是no discounting，也就是$\gamma=1$，儘管為了完整性，我們還是會把一些演算法說明把discounting的機率寫進去。

對於函數近似(function approximation)來說，用一個能夠確認改進的方式來改變策略參數(policy parameter)似乎很有挑戰性。問題在於，效能取決於action selections與做出這些選擇的狀態(states)分佈，而這兩個都受到策略參數的影響。給定一個state，策略參數對action的影響，從而對reward的影響，這可以從參數化的知識中以相對簡單的方式來計算。但是policy對state distribution的影響則是一個環境(environment)的函數，而這通常是未知的。當梯度是取決於策略變化對於狀態分佈的未知影響的時候，我們能夠如何估測關於策略參數的效能梯度(performance gradient)？

幸運的是，對於這個挑戰已經有一個很不錯的理論答案，也就是策略梯度理論，這個理論提供了一個關於策略參數的效能梯度的[解析式(analytic expression)](http://terms.naer.edu.tw/detail/3183974/)，這也是我們在近似梯度上升的時候所需要的(見公式13.1)，而這並不涉及狀態分佈的導數(derivative)。用於episodic case的policy gradient theorem如下：
$$
\nabla J(\theta)\propto \sum_s \mu(s) \sum_a q_\pi(s, a) \nabla \pi(a\vert s, \theta) \tag{13.5}
$$

其中梯度(gradients)為相對於$\theta$的分量的偏導數(partial derivatives)的行向量(column vectors)，然後$\pi$表示對應參數向量$\theta$的policy。這個符號『$\propto$』在這邊指的是『proportional to』，與什麼成正比。在episodic case中，這個比例常數它會是episode的平均長度，在continuing case中，這個比例常數則會是1，因此，這關係實際上是相等的。這邊的分佈$\mu$是使用$\pi$情況下的on-policy distribution(見Section 9.2)。策略梯度理論的證明如下圖：

:::warning
上圖就是跟大家說，只需要一點點的微積分概念，然後把之前學過的拿來重新排列組合一下，就可以證明策略梯度理論。
1. 來自[Exercise 3.18](https://hackmd.io/@shaoeChen/Hkm3mMjL_#Exercise-318)，state-value就是去加總這個state所有可能的action出現的機率乘上它的action-value
2. 把求合項拿出來，然後就是微積分的乘法理論，左微乘右加上右微乘左
3. 右邊$q_\pi(s, a)$的部份只是單純的利用公式3.2來展開
4. 右邊的部份再根據公式3.4的來調整
5. 然後你會發現，最後面的$\nabla v_\pi(s')$可以再次的展開成上面的推論
6. 你可以一直repeat最後面對value function $v_\pi$的求導項

最後的$\mathbf{Pr}(s \to x,k,\pi)$指的就是，在policy $\pi$的情況下，你從state $s$經過$k$個steps轉移到state $x$的機率。直觀來看，公式3.2、3.4計算的就是給定一個state action pair然後進到下一個state $s'$ 的機率，只是這邊考量的是，給定一個policy的情況下，在$k$步內從state $s$進到state $x$的機率有多少。所以你會計算從state $s$在經過一個time step進到$x$的機率、兩個time step進到$x$的機率...。猜測這跟最後面對value function的求導項可以無限展開有相關性，每展開一次我就會多一個state的計算，計算在$k$個time step進到state $x$的機率去乘上它的期望值求導項。

接續的就可以進到對$\nabla J(\theta)$的推論：
1. $\nabla J(\theta)$計算的是起始狀態$s_0$的估測值
2. 把上面的推論拿過來用，我們就可以計算在給定policy $\pi$的情況下，從$s_0$經過$k$個time step之後進到state $s$的機率去乘上它的期望值求導項
3. 這很有意思，事實上這邊計算的就是[Chapter 9](https://hackmd.io/@shaoeChen/rJGNlRUGY)裡面談到的$\eta(s)$，也就是state $s$在一個episode內的平均花費時間，計算的是state $s$做為起始狀態的機率加上state $s$是經由那些$\bar{s}$過來的加權機率(見下公式9.2)
4. 分子分母帶入$\eta(s')$
5. 赫然發現其中一個項目就是$\mu(s)$(見公式9.3)，也就是on-policy distribution上，每一個state所花費時間的部份
6. 得證

:::

:::warning
$$
p(s', r \vert s, a) \dot{=} P_r \left\{S_t=s', R_t=r \vert S_{t-1}=s, A_{t-1}=a \right\} \tag{3.2}
$$

$$
p(s' \vert s, a) \dot{=} P_r\left\{S_t=s' \vert S_{t-1}, A_{t-1}=a\right\} = \sum_{r\in\mathcal{R}} p(s' , r\vert s, a) \tag{3.4}
$$

$$
\eta(s) = h(s) + \sum_{\bar{s}}\eta(\bar{s})\sum_a\pi(a\vert \bar{s})p(s\vert \bar{s}, a)\tag{9.2}
$$

$$
\mu(s) = \dfrac{\eta(s)}{\sum_{s'}\eta(s')} \tag{9.3}
$$
:::

## 13.3 REINFORCE: Monte Carlo Policy Gradient
現在用第一個policy-gradient learning algorithm。回頭看一下13.1談的隨機梯度上升的整體策略，需要一個方法來獲得樣本，這樣，樣本梯度(sample gradient)的期望值就會跟做為參數函數的效能度量的實際梯度成正比。樣本梯度只需要與梯度成正比，因為任何[比例常數(constant of proportionality)](http://terms.naer.edu.tw/detail/528393/)都能被吸收到step size $\alpha$之中，否則step size $\alpha$就會是任意值。因此：
$$
\begin{align}
\nabla J(\theta) & \propto \sum_s \mu(s) \sum_a q_\pi(s, a) \nabla \pi(a \vert s, \theta) \\
&= \mathbb{E}_\pi\left[\sum_a q_\pi(S_t, a)\nabla \pi(a\vert S_t, \theta) \right] \tag{13.6}
\end{align}
$$

我們可以在這邊停下來，然後把我們13.1那個隨機梯度上升演算法實例化為：
$$
\theta_{t+1} \dot{=} \theta_t + \alpha \sum_a \hat{q}(S_t, a, \mathbf{w}) \nabla \pi(a\vert S_t, \theta) \tag{13.7}
$$

:::warning
$$
\theta_{t+1} = \theta_t + \alpha \widehat{\nabla J(\theta_t)} \tag{13.1}
$$
:::

其中$\hat{q}$是一些學習到的近似$q_\pi$的近似值。這個演算法，也稱為all-actions methods，因為它的更新涉及所有的actions，這方法前景不錯，值得投入研究，不過我們當下有興趣的是經典的REINFORCE algorithm(Willams, 1992)，這方法在時間$t$的更新只涉及$A_t$，在時間$t$際際採取的action。

我們繼續來做REINFORCE的推導，像13.6引入$S_t$那樣，我們引入$A_t$，把隨機變量(random variable)可能值的總和與用使用$\pi$情況下的期望值給取代掉，然後對期望值做採樣(sampling)。方程式13.6涉及了所有actions相稱的加總，不過每一項都沒有用到$\pi(a\vert S_t, \theta)$來加權，但這在使用$\pi$情況下期望值的話是需要的。所以我們會在不改變等式的情況下加入這樣的權重，把加總項先乘，後除，帶入$\pi(a\vert S_t, \theta)$。接續13.6，我們就可以得到：
$$
\begin{align}
\nabla J(\theta) & \propto \mathbb{E}_\pi \left[ \sum_a \pi(a\vert S_t, \theta) q_\pi(S_t, a)\dfrac{\nabla \pi(a\vert S_t, \theta)}{\pi(a\vert S_t, \theta)} \right] \\
&= \mathbb{E}_\pi \left[q_\pi(S_t, A_t)\dfrac{\nabla \pi(A_t\vert S_t, \theta)}{\pi(A_t\vert S_t, \theta)} \right] \\
&= \mathbb{E}_\pi \left[ G_t \dfrac{\nabla \pi(A_t\vert S_t, \theta)}{\pi(A_t\vert S_t, \theta)} \right]
\end{align}
$$

第二段的部份我們用採樣$A_t \sim \pi$來取代$a$，然後第三段的部份就單純的是因為$\mathbb{E}_\pi[G_t\vert S_t, A_t] = q_\pi(S_t, A_t)$。那$G_t$很明顯的就是return。最後一個表達式那個括號內的東西就是我們要的，這個量(quantity)會在每個time step被採樣，其期望值會與梯度成正比。用這個採樣(sample)來實例化我們通用的隨機梯度上升演算法(13.1)，然後生成REINFORCE的更新：
$$
\theta_{t+1} \dot{=} \theta_t + \alpha G_t \dfrac{\nabla \pi(A_t \vert S_t, \theta)}{\pi(A_t \vert S_t, \theta)} \tag{13.8}
$$

:::warning
最後面那個項目很有意思，可以用$\nabla \ln \pi(A_t\vert S_t, \theta)$來取代，因為對數計算微分的公式就是上微下不動，所以你也可以看到下面的pseudocode也是這樣寫。
:::

上面那個更新非常直觀。每個增量都會跟return $G_t$與向量的乘積成正比，實際採取action的機率的梯度除以採取那個action的機率~(很饒舌，不過就是把13.8描述一次就是了)~。那個向量(vector)就是參數空間中的方向，也就是最能增加在未來看到state $S_t$讓你反覆選擇到action $A_t$的機率的那個方向。這更新所增加在這方向上的參數向量會與return成正比，然後會跟action probability成反比。前面那句是有道理的，因為這會導致參數往那個能夠生成最高return的actions的方向移動。後面那句也是有道理的，不然一直被選到的那些actions是處於優勢的(更新會頻繁地往它們的方向移動)，即使它們沒有產生最高的return也有可能會勝出的。

注意到，REINFORCE使用的是從時間$t$開始的完整的return，這包含episode結束之前的所有的未來的報酬(future rewards)。從這個意義上來說，REINFORCE是一種Monte Carlo algorithm，而且僅適用於episodic case(就像Chapter 5的Monte Carlo algorithm一樣，在episode結束之後再回頭去做更新)。下面給出完整的演算法的pseudocode：

注意到上面pseudocode最後一行，這跟公式13.8的REINFORCE update rule有很明顯的不同：
1. 首先，在pseudocode中我們用緊湊的表達式(compact expression)$\nabla \ln \pi(A_t \vert S_t, \theta_t)$來表式13.8的分式向量(fractional vector)$\dfrac{\nabla \pi(A_t\vert S_t,\theta)}{\pi(A_t\vert S_t,\theta)}$。基本上這兩個表達式是等價的，因為$\nabla \ln x = \dfrac{\nabla x}{x}$。文獻上這個向量有很多不同的名字與符號；這邊我們就是視為eligibility vector(資格向量???)。注意到，這是演算法中，policy parameterization(策略參數化)唯一出現的地方。
2. pseudocode裡面包含了$\gamma^t$。這是因為，如前面所提過的，這一章我們處理的是non-discounted case，也就是$\gamma=1$的情況，而且pseudocode中所給出的是一般有考慮discounted的case。所有的概念在discounted case都會有適當的調整，不過這會涉及額外的複雜度，進而讓問題發散。(這邊想說的應該就是希望聚焦問題的討論)

Figure 13.1給出REINFORCE在Example 13.1，short-corridor gridworld的效能。

Figure 13.1：REINFORCE在Example 13.1，short-corridor gridworld的執行結果。在使用好的step-size情況下，每個episode的total reward會接近start state的optimal value。

做為一個隨機梯度方法，REINFORCE有著很好的理論收斂性。根據其結構，episode的expected update會跟performance gradient(效能梯度)的方向相同。這確保在足夠小的$\alpha$的情況下，其預期效能的改進，並且在減少$\alpha$的標準隨機近似條件下收斂到局部最佳。REINFORCE做為一種Monte Carlo method，它可能會有高方差，這會導致它學習上會慢一點點。
## 13.4 REINFORCE with Baseline

公式13.5的policy gradient theorem可以泛化至action value與任意baseline $b(s)$的比較：
$$
\nabla J(\theta) \propto \sum_s \mu(s) \sum_a (q_\pi(s, a) - b(s))\nabla \pi(a \vert s, \theta) \tag{13.10}
$$

這個basiline可以是任意的函數，即使是一個隨機變數，只要它不隨著$a$變化就可以；上面等式是成立的，因為減去的量為0：
$$
\sum_a b(s) \nabla\pi(a\vert s, \theta) = b(s) \nabla \sum_a \pi(a\vert s, \theta) = b(s) \nabla(1)=0
$$

使用公式3.10這個baseline的policy gradient theorem可以用跟前一章類似的步驟來推導一個更新的規則。我們最終推導出來的更新規則就是一個新版本包含general baseline的REINFORCE：
$$
\theta_{t+1} \dot{=} \theta_t + \alpha(G_t - b(S_t)) \dfrac{\nabla \pi(A_t \vert S_t, \theta_t)}{\pi(A_t \vert S_t, \theta_t)} \tag{13.11}
$$

因為baseline可以都是0，這個更新會是一個REINFORCE嚴謹的泛化形式。一般來說，baseline並不會改變更新的期望值，但是它會對其方差有很大的影響。舉例來說，我們在[Section 2.8](https://hackmd.io/@shaoeChen/Sk7frzq4u#28-Gradient-Bandit-Algorithms)看到類似的baseline就可以明顯的降低gradient bandit algorithms的方差(也因此加快學習的速度)。在bandit algorithms中，baseline就只是一個數值(到目前為止所看到的reward的平均)，但是對於MDP來說，baseline是應該隨著state變化的。在某些states中，其所有的actions都有很高的values，我們需要較高的baseline來區分那一個是value較高的action，那一個是較低的；如果是那些actions的value都是低的states，就比較適合較低的baseline。

一個baseline很自然的選擇就是state value的估測值，也就是$\hat{v}(S_t,\mathbf{w})$，其中$\mathbf{w} \in \mathbb{R}^d$是用前幾章提過的學習方法學到的權重向量(weight vector)。因為REINFORCE是一種用來學習policy parameter $\theta$的Monte Carlo method，似乎用它來學習state-value weights $\mathbf{w}$是再好不過的一個選擇。下面給出使用baseline的REINFORCE的pseudocode，用這個學習到的state-value function來做為baseline：

這演算法有兩個step sizes，分別以$\alpha^\theta$與$\alpha^\mathbf{w}$來表示，其中$\alpha^\theta$就是公式13.11的那個$\alpha$。設置這個step size的value(這邊為$\alpha^\mathbf{w}$)是相對簡單；在線性情況中設置這個我們已經有一套經驗法則了，像是$\alpha^{\mathbf{w}} = 0.1/\mathbb{E}[\Vert \nabla \hat{v}(S_t, \mathbf{w})\Vert^2_\mu]$(見[Section 9.6](https://hackmd.io/@shaoeChen/rJGNlRUGY#96-Selecting-Step-Size-Parameters-Manually))。對於設置policy parameters $\alpha^\theta$這個step size就比較不是那麼清楚，這最佳值是取決於reward的變化範圍與policy parameterization(策略的參數化)。

Figure 13.2：把REINFORCE加入baseline可以讓它學習較快，如上short-corridor gridworld (Example 13.1)所述。這邊plain REINFORCE(就是沒有加baseline)的step size是其效能最佳的step size(見Figure 13.1)。

Figure 13.2利用Example 13.1 short-corridor gridword來比較了有沒有baseline的REINFORCE。這邊baseline所用的approximate state-value function為$\hat{v}(s, \mathbf{w})=w$。也就是說，$\mathbf{w}$是一個單一分量(compoent)的向量$w$。

:::warning
個人理解直觀來看，只要你的reward是正數，在沒有加入baseline之前大概只要有被sample到，你的機率就是會被拉高，但是那個action可能只是好運被sample到，那它的機率就會愈來愈高。其它的action雖然還是有機會被sample到，但機率已經愈來愈小，甚至已經是這輩子沒有機會了。可是或許這些沒被sample到的action是好的。所以我們利用加入baseline的方式，你只要這個action沒有達到預期的效果，那它的機率就會因此降低，雖然一次、兩次它的機率還是最高的，但是時間一久其它的action的機率也高起來，自然就會被sample到的機率就高。
:::

## 13.5 Actor–Critic Method

在使用baseline的REINFORCE中，學習到的state-value function所估測的就只是每個狀態轉移(state transition)的第一個狀態(state)。這個估測值就替後續的return了一個baseline(基線)，不過這是在action之前所估測的，因此沒有辦法用來評估action。另一方面，在actor–critic methods中，state-value function也可以應用在轉移的第二個狀態上。第二個狀態(second state)的估測值，當discounted加到reward的時候，就構成one-step return $G_{t:t+1}$，這是對actual return一個有效的估測，因此是一個評估action的方式。正如我們在這本書中看到的TD learning那樣，one-step return在其方差與計算適意性(computational congeniality)是優於actual return的(即使它引入方差)。我們還知道能夠怎麼樣的利用$n$-step reutnrs與eligibility traces(Chapter 7與Chapter 12)來靈活的調整bias的程度。當state-value function被以這樣的方式用來評估actions的時候，就稱為critic，而整體的policy-gradient methods就稱為actor-critic method。注意到，在梯度估測中的bias並非由bootstrapping所引發；即使critic是用Monte Carlo method來學的，actor還是有偏的(biased)。

從簡單的開始，我們先來看one-step actor–critic methods，這類似於Chapter 6說過的TD(0)、Sarsa(0)、Q-learning。one-step methods最吸引人的就是，它們完全是online(線上)且incremental(增量)的，同時避免掉eligibility traces的複雜性。它們算是eligibility trace methods中的一個特例，不過更容易理解。One-step actor–critic methods把公式13.11那個REINFORCE的full return用one-step reutnr來取代掉，並且使用學習到的state-value function來做為baseline，如下：
$$
\begin{align}
\theta_{t+1} & \dot{=} \theta_t + \alpha \Bigl(G_{t:t+1} - \hat{v}(S_t, \mathbf{w}) \Bigr) \dfrac{\nabla \pi(A_t\vert S_t, \theta_t)}{\pi(A_t\vert S_t, \theta_t)} \tag{13.12} \\
&= \theta_t + \alpha \Bigl(R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}) - \hat{v}(S_t, \mathbf{w}) \Bigr) \dfrac{\nabla \pi(A_t\vert S_t, \theta_t)}{\pi(A_t\vert S_t, \theta_t)} \tag{13.13} \\
&= \theta_t + \alpha \delta_t \dfrac{\nabla \pi(A_t\vert S_t, \theta_t)}{\pi(A_t\vert S_t, \theta_t)} \tag{13.14}
\end{align}
$$

很自然的，我們可以拿semi-gradient TD(0)來跟state-value function learning method配做對。下面給出完整演算法的pseudocode。：

注意到，它現在完全是一個online、incremental的演算法，會在states、actions、rewards出現的時候就處理，而且不會重新回頭再去看它們一眼。

要把上面的方法泛化到$n-$step methods的forward view，然後再泛化至$\lambda-$return algorithm是很簡單的。公式3.12的one-step return可以各別用$G_{t:t+n}$或$G_t^\lambda$來取代。那，泛化至$\lambda-$return algorithm的backward view也是很簡單的，可以使用Chapter 12提過的方法分別對actor、critic使用不同的eligibility traces就可以了。下面給出完整演算法的pseudocode：

## 13.6 Policy Gradient for Continuing Problems
如Section 10.3所討論那般，對於沒有episode boundaries的continuing problems，我們需要根據每個time step的平均報酬率(average rate of reward)來定義效能：
$$
\begin{align}
J(\theta) \dot{=} r(\pi) &\dot{=} \lim_{h \to \infty} \dfrac{1}{h} \sum_{t=1}^h \mathbb{E}[R_t \vert S_0, A_{0:t-1}\sim \pi] \tag{13.15} \\
&= \lim_{t \to \infty} \mathbb{E}[R_t \vert S_0, A_{0:t-1}\sim \pi] \\
&= \sum_s \mu(s) \sum_a \pi(a\vert s) \sum_{s', r} p(s', r \vert s, a)r
\end{align}
$$

其中$\mu$是使用$\pi$下的一個steady-state distribution(穩定狀態分佈)，$\mu(s) \dot{=} \lim_{t\to\infty} \mathrm{Pr}\{S_t=s\vert A_{0:t}\sim\pi\}$，這邊假其存在並且獨立於$S_0$(遍歷性假設，ergodicity assumption)。我們要記得，這是一個特殊的分佈，如果你根據$\pi$選擇actions，你會維持在相同的分佈中：
$$
\sum_s \mu(s) \sum_a \pi(a \vert s, \theta) p(s' \vert s, a) = \mu(s'), \text{ for all } s' \in \mathcal{S} \tag{13.16}
$$

下面給出continuing case(backward view)中actor-critic algorithm的pseudocode：

很自然地，在continuing case中，我們定義value $v_\pi(s) \dot{=} \mathbb{E}[G_t \vert S_t=s]$且$q_\pi(s, a) \dot{=} \mathbb{E}_\pi[G_t \vert S_t=s, A_t=a]$，相對的差分回報(differential return)為：
$$
G_t \dot{=} R_{t+1} - r(\pi) + R_{t+2} - r(\pi) + R_{t+3} - r(\pi) \cdots \tag{13.17}
$$

有了這些替代的定義，公式13.5 episodic case的policy gradient theorem就可以用到continuing case。下面給出其證明。forward、backward view兩個方程式維持不變，證明如下：

## 13.7 Policy Parameterization for Continuous Actions

Policy-based methods提供一個實用的方法來處理大型的action spaces，即使是具有無限action的continuous space也是可以。與期計算很多actions的每個學習機率，不如學習機率分佈的分析統計。舉例來說，action set也許是實數(real numbers)，我們可以從正態(高斯)分佈中選擇actions。

正態分佈的機率密度函數通常寫為：
$$
p(x) \dot{=} \dfrac{1}{\sigma \sqrt{2\pi}}\exp \Biggl(-\dfrac{(x-\mu)^2}{2\sigma^2} \Biggr) \tag{13.18}
$$

其中$\mu$與$\sigma$是這個正態分佈的均值與標準差，$\pi$的話在這邊指的當然就是$\pi\approx 3.14159$。下圖給出不同的均值、標準差所呈現的機率密度函數：

那個$p(x)$指的就是在$x$這地方其機率的密度，而不是機率。它是可以大於1的；不過在$p(x)$以下的總面積總和必需為1。通常來說，我們可以對任意範圍的$x$值取$p(x)$下的積分(integral)，透過這樣的方式來取得$x$落在該範圍內的機率。

為了能夠生成policy parameterization，我們可以將policy定義為real-valued scalar action(實數純量動作?)上的正態分佈機率密度，其均值與標準差則由取決於state的parametric function approximationr(參數函數近似器)所給出。如下：
$$
\pi(a\vert s, \theta) \dot{=} \dfrac{1}{\sigma(s, \theta)\sqrt{2\pi}}\exp \Biggl(-\dfrac{(a - \mu(s,\theta)^2}{2\sigma(s, \theta)^2} \Biggr) \tag{13.19}
$$

其中$\mu:\mathcal{S}\times\mathbb{R}^{d'} \to \mathbb{R}$與$\sigma:\mathcal{S}\times\mathbb{R}^{d'} \to \mathbb{R}^+$是兩個參數化函數近似器(parameterized function approximators)。為了完成這個範例，我們會需要給這些近似器一個形式。為此，我們把policy的參數向量分成兩部份，也就是$\theta=[\theta_\mu,\theta_\sigma]^T$，一部份用來表示均值的近似值，一部份用來表示標準差的近似值。均值可以把它弄成一個線性函數。標準差的話始終為正值，比較好的方式就是線性函數的指數。因此得到如下：
$$
\mu(s, \theta) \dot{=} \theta_\mu^T\mathbf{x}_\mu(s) \text{ and } \sigma(s, \theta) \dot{=} \exp \Bigl( \theta_\sigma^T \mathbf{x}_\sigma(s) \Bigr)\tag{13.20}
$$

其中$\mathbf{x}_\mu(s)$與$\mathbf{x}_\sigma(s)$是由Section 9.5中提過的一個方法所構造起來的state feature vectors。有這些定義之後，這章其餘部份所說明的所有的演算法都可以用來學習選擇實值的動作(real-valued actions)。
## 13.8 Summary
這章之前，這本書關注在action-value methods，意思就是說，這方法學習著action values然後用它們來確定action的選擇。另一方面，在這一章我們考慮了學習參數化策略的方法，這讓我們可以不需要考慮action-value的估測值就可以選擇actions。特別是，我們還考慮了policy-gradient methods，這意味著每個step，其策略參數(policy parameter)的更新都會朝著效能梯度相對於策略參數的估測值的方向來進行。

這種學習、保存策略參數的方法有很多的優點：
* 它們可以對所採取的actions學習特定的機率
* 它們可以學習適當的探索，然後漸近地接近確定性策略(deterministic policies)
* 它們可以很自然地處理continuous action spaces

這些事情對policy-based methods來說都是簡單的，easy，不過這對那種一般的$\epsilon$-greedy悅action-value methods來說是很難，甚至不可能。此外，在某些問題上，policy以參數化來表示會比value function來的簡單；這些問題更適合參數化策略方法。參數化策略方法(parameterized policy methods)比之action-value methods在策略梯度理論形式中有著更重要的理論優勢，它給出一個精確的公式，說明著在不涉及狀態分佈的導數的情況下，策略參數如何影響效能。這個定理為所有的策略梯度方法給出一個理論基礎。

REINFORCE method直接依循著策略梯度理論。它增加一個state-value function來做為baseline，以此降低REINFORCE的方差(variance)而不引入偏差(bias)。如果state-value function也用來評估(assess)或鑒定(criticize)策略對action的選擇，那麼，value function就可以成為critic，而policy就稱為actor；整個方法就稱為actor-critic methods。critic會把bias引入到actor的梯度估測值，不過這通常是可取的(desiable)，因為bootstrapping TD methods在降低方差這方面通常是優於Monte Carlo methods的。

總體而言，policy-gradient methods提供一個明顯不同的優缺點(對比action-value methods)。時至今日，這方法在某些方面還蒙著一層神秘的面紗，不過這確實是一個讓人興奮且正進行研究的議題。