# Reinforcement Learning: An Introduction_Chapter 2 Multi-armed Bandits
###### tags: `Reinforcement Learning` `Second Edition`

[相關連結_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)

## 2.2 Action-Value Methods

強化學習與其它學習最大的不同在於，強化學習只能評估給定的action好壞，但沒有辦法像監督式學習一樣告知這個action是好還是壞。Chapter 2利用Multi-armed Bandits做為範例說明強化學習。Multi-armed Bandits就是吃角子老虎，不過上面有多個拉霸。

這可以想成一個學習問題，也就是你要重覆的選擇$k$個選項(option)或是動作(action)，每次選擇之後都會得到一定的獎勵(reward)，而這個reward是由選擇的action所決定的機率分佈所產生。我們的目標是希望在一定的時間內最大化總收益的期望值。

而在$k$-armed Bandits問題中，機器上面會有$k$個拉霸，每次拉都會有一個期望或平均收益，也就拉某一個拉霸的價值(value)。這邊先說明幾個符號約定：
* 在某一個time step $t$所選擇的action寫為$A_t$
* 在某一個time step $t$所得到的reward寫為$R_t$
* action對應的value則寫為$q_*(a)$，也就是給定action $a$的時候我們預期得到的reward，$q_*(a) \dot{=} \mathbb{E}[R_t\vert A_t=a]$，這個數學式很直接，就是給定$A_t=a$的時候我們預期得到的reward的期望值
* action $a$在time step $t$所估測的value寫為$Q_t(a)$(我們希望這個值可以接近)$q_*(a)$)

當我們持續的估測value(價值)，我們在任一個time step都至少會有一個action的value是最高的，這個value最高的action稱為greedy actions。當我們選擇這些greedy actions，那就稱為利用(發揮)(exploiting)對這些action的value的當前已知知識。選擇這些greedy actions以外的action，稱為探索(exploring)。探索的好處在於可以改善對於nongreedy action的value(不試試看怎麼會知道好不好)。
值得注意的是，同一個time step的情況下是不可能同時利用與探索，這是一種exploiting與exploring之間的衝突。在一個特定情況下，要利用還是要探索，則是可以取決於估測的精確值、不確定性，以及剩餘的time steps的數量。

一種利用估測action的value的方式來決定選擇那一個action的方法，統稱為action-value methods，估測方式如下：
$Q_t \dot{=} \dfrac{\sum^{t-1}_{i=1}R_i \cdot \mathbb{1}_{A_i=a}}{\sum_{i=1}^{t-1}\mathbb{1}_{A_i=a}}$

上面的數學式說明的就是在time step $t$之前，action $a$出現的average reward，分母就是總計出現action $a$的次數，分子就是總計出現action $a$所得到的reward。而$\mathbb{1}$指的就是，如果是事實即為1，若否則為0。

當action $a$出現的次數愈多，根據大數定理，這個$Q_t(a)$就會收斂到接近$q_*(a)$，而這樣的做法又稱為sample-average method(樣本平均法?)。

而選擇action的方式，如上面提到的，這是一種最簡單的方式，也就是選擇估測值最高的那一個，greedy actions，如果有多個greedy actions，那就可以隨機選擇一個，這可以寫為：
$A_t \dot{=} \arg\max_a Q_t(a)$

這個數學式很直觀，就是選擇可以讓$A_t$最高的那個action $a$。

不過這樣的方式會讓agent懶得去探索，因為其它action可能可以有更好的結果，因此有一種延申應用，也就是$\epsilon$-greddy method。也就是，每次的action的選擇都對以$\epsilon$的機率來選擇，這可以確保agent會有機會去做探索。而且只要你的time step夠長，長到無限，那你可以確保每一個action都會被無限次數的選到，這可以確保所有的$Q_t(a)$都可以收斂到它們各自的$q_*(a)$。

書中2.3節給出了$\epsilon$在多種設置下的結果，不難發現，設置$\epsilon=0$所得的結果是最不好的，書中也提到，如果$\epsilon$可以隨著時間的推移降低，或許也是一個不錯的方法。想法上只要timestep夠長，要探索的也都探索了，所以後續降低探索或許也是合理的。

## 2.4 Incremental Implementation
剛剛看到的Action-Value methods是將所有估測的action value做為觀察到的reward的樣本均值。下面我們要找一個方法來高效的計算這些均值。

這邊的範例為了簡化起見，只關注單一個action，下面符號說明：
* $R_i$，表示第$i$次選擇這個action之後所得到的reward，舉例來說，$R_1$就是第1次選擇得到的reward，$R_2$就是第2次...
* $Q_n$，表示第$n-1$次選擇這個action之後我們所估測會得到的action value，舉例來說，$Q_2$就是第1次選擇這個action，我們所估測會得到的action value

其中，$Q_n \dot{=} \dfrac{R_1 + R_2 + R_3 + ... + R_{n-1}}{n-1}$，

這很直觀，就是執行$n-1$次之後所得的reward的均值。但這種作法有個缺點，就是time step愈長那整個計算量就會愈多，每次都要做整個資料的加總平均，因此我們可以改這麼做：
$$
\begin{align}
Q_{n + 1} &= \dfrac{1}{n}\sum^n_{i=1}R_i \\
&=\dfrac{1}{n}\left(R_n + \sum_{i=1}^{n-1}R_i \right) \\
&=\dfrac{1}{n}\left(R_n + (n-1)\dfrac{1}{n-1}\sum_{i=1}^{n-1}R_i \right) \\
&=\dfrac{1}{n}\left(R_n + (n-1)Q_n \right) \\
&=\dfrac{1}{n}\left(R_n + nQ_n - Q_n \right) \\
&=Q_n + \dfrac{1}{n}\left[R_n - Q_n \right]
\end{align} \tag{2.3}
$$

上面公式的推導非常清楚：
1. 我們假設$Q_n$就是加總$n-1$次reward的平均，所以$Q_{n+1}$就是加總$n$次reward的平均
2. 提出$R_n$，summation的項目變成$n-1$
3. 做一個不影響結果的乘除，乘上$n-1$，又除$n-1$
4. $\dfrac{1}{n-1}\sum_{i=1}^{n-1}R_i$就是我們稍早所定義的$Q_n$
5. 展開
6. 整理

簡單說就是$Q_{n+1}$就是$n-1$次的平均值($Q_n$)加上這次的reward $R_n$減掉$n-1$次的平均值然後除$n$。不難看出這麼做的好處，我們只需要記錄$Q_n$，然後計算$R_n$就可以得到$Q_{n+1}$。書中會以這樣的形式貫穿全局：
$$\text{NewEstimate} \leftarrow \text{OldEstimate + StepSize [ Target - OldEstimate ]} \tag{2.4}$$

其中Target與OldEstimate之間的差異就是誤差。而StepSize的話，在公式2.3中就是$\dfrac{1}{n}$，書中會用$\alpha$來表示，或者更通用的形式會以$\alpha_t(a)$來表示。

書中給出一個pseudocode，簡潔有力，見下圖：

## 2.5 Tracking a Nonstationary Problem
取平均的方法適用於平穩的問題，像是剛剛討論的賭博機問題就是相對平穩，因為賭博機的收益機率分佈並不會隨著時間而變化。但如果會隨著變化，那就不適合平均的方法，有一種作法就是給近期的reward比過去比較久的reward有較高的權重。另外一種常見作法就是給定一個固定的step size，$\alpha$，我們將公式2.3調整如下：
$$Q_{n+1} \dot{=} Q_n + \alpha[R_n - Q_n] \tag{2.5}$$

上面公式可以看的出來，我們用$\alpha$取代掉$\dfrac{1}{n}$，而且$\alpha \in (0, 1]$。

這樣的調整讓$Q_{n+1}$成為過去的reward與初始的$Q_1$的加權平均：
$$
\begin{align}
Q_{n+1} &= Q_n + \alpha[R_n - Q_n]\\
&= \alpha R_n + (1 - \alpha)Q_n \\
&= \alpha R_n + (1-\alpha)[\alpha R_{n-1} + (1 - \alpha)Q_{n-1}] \\
&= \alpha R_n + (1-\alpha)\alpha R_{n-1} + (1 - \alpha)^2 Q_{n-1}\\
&= \alpha R_n + (1-\alpha)\alpha R_{n-1} + (1 - \alpha)^2 \alpha R_{n-2} + \cdots + (1- \alpha)^{n-1}\alpha R_1 + (1 - \alpha)^n Q_1 \\
&= (1-\alpha)^nQ_1 + \sum^n_{i=1}\alpha(1-\alpha)^{n-i}R_i
\end{align} \tag{2.6}
$$

上面我的展開多了課本一段，看起來會更為直觀：
* 第二段只是單純的展開公式然後調整位置
* 第三段我們把$Q_n$再做一次展開
* 第四段我們展開$Q_n$之後再做一次調整

到第四段之後我們可以得到一個pattern，也因此就可以得到最後的$(1-\alpha)^nQ_1 + \sum^n_{i=1}\alpha(1-\alpha)^{n-i}R_i$，你可以自己假設$n=2$然後試著帶入看看，當$n=2$，那只會第四段推論的結果。值得注意的是，$(1-\alpha)^n + \sum_{i=1}^n \alpha(1-\alpha)^{n-i}=1$，這是一種加權平均的作法(weighted average)，就帶個$\alpha=0.5, n=1$就可以驗證，$(1 - 0.5)^1 + \sum_{i=1}^1 (1 - 0.5)^{1-i}=1$。

從2.6可以清楚看的出來幾點個：
1. 公式很大的部份受$Q_1$影響
2. $n$愈大，$R_i$的影響就會愈小，這不難理解，假設你的$n=5$，那$R_1$就會是$\alpha(1-\alpha)^{5-1}$，而$\alpha \in (0, 1]$，因此它是一個增長函數，這樣子的作法又稱為exponential
recency-weighted average(指數近因加權平均?)。

如果這個step-size($\alpha$)可以隨著time step的變動而變動，那就會變的很方便。我們假設$\alpha_n(a)$代表第$n$次選擇action $a$接收到reward的step size。當我們設置$\alpha_n(a) = \dfrac{1}{n}$，那就會得到我們稍早提到的採樣平均法(sample-average method)，大數理論可以保證這樣的作法可以收斂到true action values(真值?)。

隨機逼近理論(stochastic approximation theory)給出一個保證收斂機率為1的條件：
$$\sum_{n=1}^\infty \alpha_n(a) = \infty \text{ and } \sum_{n=1}^\infty \alpha^2_n(a) < \infty \tag{2.7}$$

第一個條件說明的是step size要夠大，第二個條件說明的是step size要能隨著time step變小，如果是$\alpha_n(a)=\dfrac{1}{n}$那就符合條件，如果讓$\alpha_n(a)=\alpha$，也就是設置成一個常數，那就無法滿足第二個條件。不過書中提到，滿足方程式2.7的step size通常收斂的很慢，需要多方調教才能得到一個滿足的結果。

## 2.6 Optimistic Initial Values
剛剛我們有提到公式很大的部份受到$Q_1$影響，就統計的角度來說，這些方法是偏差的(biased)。對sample-average methods(樣本平均法)來說，只要每一個action都被選擇過，那bias就消失了。但對於$\alpha$是常數的情況，bias會隨著時間降低，但並不會消失(見公式2.6)。從好處來說，我們可以將$Q_1$視為一種預期的先驗知識，但壞處來看，這就變成一個需要調校的超參數了。將$Q_1$設置大的一個好處就是，因為估計值大，而實際的reward是小的，agent就會因此去做多一點的探索(嚐試)。

Figure 2.3給出一個10-armed Bandits的範例


上圖看的出來，$\epsilon=0$情況下，即使初始狀況不好，但它選擇optimal action的機會在後面也是比$\epsilon-$greedy還要好。不過這樣子的方法(optimistic initial values)依然是只適合應用在穩定的問題上(stationary problems)。畢竟起始的時刻也只會出現一次，過度的觀注不是很好恰當。一如樣本平均法用相同的權重平均所有後續的reward也只適用於穩定問題上。

## 2.7 Upper-Confidence-Bound Action Selection
我們談過action-value所存在的不確定性，因為它需要試探，雖然greedy action所選擇的是當下最好的action，但這個當下最好的action確不見得對後面是好的。而$\epsilon$-greedy雖然會有一定的機率探索，但這個探索是一定機率下亂猜的。如果我們可以依它們(non-greedy action)的潛力來找出一個可能是最好的action，那就要考慮它們的估計值有多接近最大值，還有這些估計的不確定性。我們可以按著下面的公式：
$$A_t \dot{=}\arg\max_a\left[Q_t(a) + c \sqrt{\dfrac{\ln t}{N_t(a)}} \right] \tag{2.10}$$

其中幾點說明：
1. $\ln t$是$t$的自然對數，也就是$e\approx 2.71828$的多少次方是$t$
2. $N_t(a)$則是在time step $t$之前，action $a$被選擇幾次(公式2.1的分母)
3. $c$是一個大於0的數值，控制著試探的程度，決定信心水準(confidence level)
4. $\sqrt{\dfrac{\ln t}{N_t(a)}}$意謂著對action $a$不確定性或方差(variance)的度量，因此，最大化的大小是action $a$上可能真實數值的一種上限

當$N_t(a)=0$，則代表$a$會被認為是滿足最大化條件的action。只要$a$被選過，那它的不確定性就會減少，因為$N_t(a)$會增加，那這個開根號項目就會減少，反過來說，沒有被選到的$a$，其$N_t(a)$不動，隨著時間的增長，$\ln t$會變大，那不確定性就增加。

所有的action都會被選到，隨著時間的推移，估計較低的value的action或已經被選擇很多次的action再被選到的機率就會降低。

Figure 2.4給出UCB與$\epsilon-$greedy的比較，不難看出，UCB的效果比較好

## 2.8 Gradient Bandit Algorithms
剛剛我們所討論的是一種利用估測action value的方法來決定選擇那一個action，但這並不是唯一的方法，這節會說明一種學習每一個action $a$的數值偏好(numerical preference)，以$H_t(a)$來表示。當$H_t(a)$愈大，就代表著這個action愈常被選到，值得注意的是，這種偏好的表示並沒有關於reward的解釋。只有一個action對另一個action的相對偏好才是重要的，如果我們對所有偏好的action都加1000，那麼在[softmax](https://hackmd.io/@shaoeChen/SJu92oGBM?type=view#Softmax-regression)分佈(Gibbs或Boltzmann distribution)定義下是沒有任何影響的：
$$P_r\left\{ A_t=a \right\} \dot{=} \dfrac{e^{H_t(a)}}{\sum^k_{b=1}e^{H_t(b)}} \dot{=}\pi_t(a) \tag{2.11}$$

其中$\pi_t(a)$所指的就是在時間$t$選擇到action $a$的機率。所有action $a$的初始值都是一樣的，舉例來說，$H_1(a)=0, \forall{a}$，也因此在一開始的時候，每一個action被選到的機率就都是一樣的。

基於隨機梯度上升的這種想法，有一種自然學習演算法。在每一個step，選擇action $A_t$，然後收到reward $R_t$，其$H_t(a)$的更新如下：
$$
\begin{align}
H_{t+1}(A_t) \dot{=} H_t(A_t) + \alpha(R_t - \bar{R}_t)(1 - \pi_t(A_t)) \text{ and } \\
A_{t+1}(a) \dot{=} H_t(a) - \alpha(R_t - \bar{R}_t)\pi_t(a), \text{ for all } a \neq A_t
\end{align} \tag{2.12}
$$

其中：
* $\alpha > 0$，是一個step-size的參數
* $\bar{R}_t \in \mathbb{R}$，是包含時間$t$在內的所有rewards的平均(平穩的問題參考方程式2.4，非平穩的參考2.5)

$\bar{R}_t$做為一個基準，如果reward比$\bar{R}_t$高，那取到action $A_t$的機率在未來就會提高，反之則降低。而未被選擇到的action則會往相對的方向移動。字面上的意思來看應該是，如果$A_t$的機率提升，那其它未被選擇的機率就會降低，反之則提升，相關可以從方程式2.12看的出來。$\alpha$是大於0的正數，所以只要$R_t - \bar{R}_t$是正數，也就是reward大於均值，那再乘上後面的機率之後還是正數，就意謂著$H_{t+1}(A_t)$會提升。

Figure 2.5給出一個比較結果，有無baseline對於選到optimal action的差異看起來影響不小

### The Bandit Gradient Algorithm as Stochastic Gradient Ascent
書本上將這一部份特別框起來說明，感覺就像燒人腦的大魔王一樣，就硬著頭皮讀讀看。這邊要說的主要是利用將梯度賭博機演算法(Bandit Gradient Algorithm)理解為梯度上升的隨機近似來深入瞭解梯度賭博機演算法。

在精確的梯度上升中，每一個action的偏好函數$H_t(a)$與效能上增加的影響成正比：
$$H_{t+1}(a) \dot{=} H_t(a) + \alpha\dfrac{\partial\mathbb{E}[R_t]}{\partial H_t(a)} \tag{2.13}$$

其中效能的衡量指標在這裡就是期望值：
$$\mathbb{E}[R_t] = \sum_x \pi_t(x)q_*(x)$$

這個增量影響的量測就是效能衡量指標對action的偏好函數的偏微分。不過這種情況下是不可能去用梯度上升，因為根據假設，我們並不知道$q_*(x)$，但是事實上方程式2.12跟2.13這個期望值版本是等價的，這讓這個演算法成為隨機梯度上升的一個實例。我們先看效能梯度：
$$
\begin{align}
\dfrac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} &= \dfrac{\partial}{\partial H_t(a)}\left[\sum_x \pi_t(x) q_*(x) \right] \\
&= \sum_x q_*(x) \dfrac{\partial \pi_t(x)}{\partial H_t(a)} \\
&= \sum_x(q_*(x) - B_t)\dfrac{\partial \pi_t(x)}{\partial H_t(a)}
\end{align}
$$

其中$B_t$稱為baseline(基線)，可以是任意不依賴$x$的純量。想法上，從第一段推論到第二段是左微乘右加上右微乘左的概念，右微與$H_t$無關，直接消掉，因此僅保留第二段的結果。

加入baseline $B_t$並沒有改變任何事情，因為所有actions的梯度總和，$\sum_x\dfrac{\partial \pi_t(x)}{\partial H_t(a)}=0$，依然是0。當$H_t(a)$改變，action的機率也會跟著改變，有些會上升，有下則是下降，但是不管如何，機率的總和永遠是1。

接著，項目裡面乘上$\pi_t(x)/\pi_t(x)$，見頭尾加入的項目，這並不影響結果：
$$\dfrac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} = \sum_x \pi_t(x)(q_*(x) - B_t)\dfrac{\partial \pi_t(x)}{\partial H_t(a)}/ \pi_t(x)$$

調整之後，就變成是一個求期望值的式子，加總所有可能的隨機變數$A_t$的值$x$，然後乘上這些值($x$)的機率，得到下面的式子：
$$
\begin{align}
&= \mathbb{E}\left[(q_*(A_t) - B_t) \dfrac{\partial \pi_t(A_t)}{\partial H_t(a)}/ \pi_t(A_t) \right] \\
&= \mathbb{E} \left[(R_t - \bar{R}_t) \dfrac{\partial \pi_t(A_t)}{\partial H_t(a)}/ \pi_t(A_t) \right]
\end{align}
$$

這邊可以看的到，我們選擇$\bar{R}_t$做為baseline($B_t$)，然後用$R_t$取代$q_*(A_t)$，這樣取代是沒問題的，因為$\mathbb{E}[R_t\vert A_t] = q_*(A_t)$，這個定義在2.2的時候就已經給出。

:::info
action對應的value則寫為$q_*(a)$，也就是給定action $a$的時候我們預期得到的reward，$q_*(a) \dot{=} \mathbb{E}[R_t\vert A_t=a]$，這個數學式很直接，就是給定$A_t=a$的時候我們預期得到的reward的期望值
:::

很快的我們就可以確定$\dfrac{\partial \pi_t(x)}{\partial H_t(a)} = \pi_t(x)(\mathbb{1}_{a=x} - \pi_t(a))$，其中$\mathbb{1}_{a=x}$意謂著，當$a=x$的時候，那就是1，反之則為0。這樣我們就可以得到：
$$
\begin{align}
&= \mathbb{E}[(R_t - \bar{R}_t)\pi_t(A_t)(\mathbb{1}_{a=A_t} - \pi_t(a)) / \pi_t(A_t)]\\
&= \mathbb{E}[(R_t - \bar{R}_t)(\mathbb{1}_{a=A_t} - \pi_t(a))]
\end{align}
$$

我們的計劃是將效能梯度寫成我們在每一個step所能採樣的某些事情的期望值，一如剛才做的事情那樣，然後在每一個step以一定的比例採樣來更新。用一個樣本的期望值來替代公式的效能梯度(performance gradient)，得到：

$$H_{t+1}(a) = H_t(a) + \alpha(R_t - \bar{R}_t)(\mathbb{1}_{a=A_t}-\pi_t(a)) \text{ for all } a$$

這跟方程式2.12(見下方)給出的原始的演算法是等價的。

:::info
$$
\begin{align}
H_{t+1}(A_t) \dot{=} H_t(A_t) + \alpha(R_t - \bar{R}_t)(1 - \pi_t(A_t)) \text{ and } \\
A_{t+1}(a) \dot{=} H_t(a) - \alpha(R_t - \bar{R}_t)\pi_t(a), \text{ for all } a \neq A_t
\end{align} \tag{2.12}
$$
:::

現在要做的就是證明$\dfrac{\partial \pi_t(x)}{\partial H_t(a)} = \pi_t(a)(\mathbb{1}_{a=x} - \pi_t(a))$。這可以利用除法法則來推導：
$$\dfrac{\partial}{\partial x}\left[\dfrac{f(x)}{g(x)}\right] = \dfrac{\dfrac{\partial f(x)}{\partial x}g(x) - f(x)\dfrac{\partial g(x)}{\partial x}}{g(x)^2}$$

:::info
這部份是從左微乘右+右微乘左推導出來，可以[參考](http://talentbear.blogspot.com/2012/01/quotient-rule.html)
:::

利用這個法則，我們就可以繼續下面的工作：
$$
\begin{align}
\dfrac{\partial \pi_t(x)}{\partial H_t(a)} &= \dfrac{\partial}{\partial H_t(a)} \pi_t(x) \\
&= \dfrac{\partial}{\partial H_t(a)} \left[\dfrac{e^{H_t(x)}}{\sum^k_{y=1} e^{H_t(y)}} \right] \\
&= \dfrac{\dfrac{\partial e^{H_t}}{\partial H_t(a)} \sum^k_{y=1} e^{H_t(y)} - e^{H_t(x)} \dfrac{\partial \sum^k_{y=1} e^{H_t}(y)}{\partial H_t(a)}}{(\sum^k_{y=1} e^{H_t(y)})^2} \text{(by the quotient rule)} \\
&= \dfrac{\mathbb{1}_{a=x}e^{H_t(x)} \sum^k_{y=1} e^{H_t(y)} -e^{H_t(x)} e^{H_t(a)}}{(\sum^k_{y=1} e^{H_t(y)})^2} \text{(because $\dfrac{\partial e^x}{\partial x} = e^x)$} \\
&= \dfrac{\mathbb{1}_{a=x} e^{H_t(x)}}{\sum^k_{y=1} e^{H_t(y)}} - \dfrac{e^{H_t(x)} e^{H_t(a)}}{(\sum^k_{y=1} e^{H_t(y)})^2} \\
&= \mathbb{1}_{a=x} \pi_t(x) - \pi_t(x) \pi_t(a) \\
&= \pi_t(x)(\mathbb{1}_{a=x} - \pi_t(a))
\end{align} \tag{Q.E.D}
$$

這個推論很長，不過推論的過程書本都在後面有備註，所以費點心思不難理解
1. 第二段的部份，$\pi_t(x)$的定義就是softmax(2.11)，因此可以寫成推論那般
2. 第三段的部份就是因為剛才所提過的除法法則
3. 第四段的部份是很簡單的定理
4. 第五段的部份就是單純的消去整理
5. 第六段的部份，前半段，分子分母依然是softmax的形式，後半段也是，只是有兩個softmax，因此轉換之後是兩個相乘
6. 第七段就是把相同的部份提出來

這邊不知道是不是自己讀書時候的盲點，不是很確定第四段的$\mathbb{1}_{a=x}$是怎麼出來的。如果有路過知道的請指點。

這樣，就證明梯度賭博演算法等同求期望報酬的梯度，因此這個演算法也是一種隨機梯度上升的實例。這確保了演算法魯棒性一般的收斂特性。

除了不依賴所選擇的action，我們並沒有在reward baseline有任何的假設。我們可以讓reward baseline是0或是1000，無所謂，它仍然是一個隨機梯度上升的實例。這樣，baseline的選擇就不影響演算法的預期更新，不過還是會影響更新的方差，這會影響收斂的速度(見Figure 2.5說明)。用報酬的平均值來做baseline雖然不是最好的做法，但是簡單新奇又有效。
## Associative Search (Contextual Bandits)
目前為止，上面討論的都是沒有關聯的任務，也就是不需要將不同的action與不同的情境(situations)關聯起來。在這些任務中，當任務是穩定問題的時候，學習器(learner)會試著去找一個最佳的action，當任務是不穩定的問題的時候，那就會隨著時間的改變試著去追蹤最佳的action。

不過在一般的強化學習任務中，通常會有多種情境，而目標就是學習一個polciy：將情境(situations)映射到在這些情況中最佳的那個action。這邊我們就簡要的探討一個非關聯任務擴展到關聯任務的簡單方法。

假設，有多個不同的$k$-armed bandit($k$臂吃角子老虎機)的任務，然後每一個step你都要亂數面對其中一個吃角子老虎機。這樣子，這個任務就變成每一個step都是隨機在變化。(如果你選擇的每個任務的機率都不會隨著時間變化，那它就是單一穩定的k-armed bandit的任務，那你就可以用這一章裡面提到的方法來處理。)

現在，當你選定一個任務，你同時也會給這個任務一個獨特的線索，但不是它的action values。也許你面對的是一台真正的吃角子老虎機，它會隨著action values的改變而改變顯示的顏色。現在，可以學習一個關聯每個任務的policy(看到的顏色與任務的關聯)，當你面對這個任務的時候所採取的最佳actions，舉例來說，如果是紅色，那就選擇arm 1，如果是綠，那就選擇arm 2。有了這個policy通常可以做的比什麼訊息都沒有還要來的好。

這就是一個關聯搜尋的範例，因為它有著尋找最佳action的trial-and-error learning的精神，也把這些action在什麼情境下表現給最佳關聯起來。這種關聯搜尋任務在文獻上稱為contextual bandits。這種問題往上強化學習的關聯就是它需要一個policy，而跟$k$-armed bandit的關聯就是每一個action只影響立即性的reward。如果action可以影響後續情境的reward，那它就是一個完整的強化學習的問題，這後續的章節就會有所說明。
## 2.10 Summary
這一章節介紹了幾個方法：
* $\epsilon$-greedy，在短時間內做隨機動作的選擇
* UCB，採用確定的動作選擇，但在每個time step會針對較少樣本的action做優先選擇來實現試探這個行為
* Gradient bandit algorithms，不估計action value，利用偏好函數，使用$H_t(a)$，使用softmax的機率分佈來選擇更好的action

Figure 2.6 給出三種方法的比較