強化學習筆記2—Bandit演算法

04-21

強化學習最明顯的特徵是，使用訓練信息來評估採取的行動，而非給出正確行動的指導，這就使得積極的探索十分必要。對於一個使用試錯行為的搜索，純粹的評估回饋可以表示行動好的程度，但不能確定是最好還是最壞；純粹的指導回饋指示要採取的正確行動，卻可能與實際採取行動的無關。在純粹形式中，這兩種回饋截然不同：評估回饋完全依賴於採取的行動，而指導回饋與採取的行動無關，也有一些將兩者結合的中間例子。本章在評估回饋的簡化多臂Bandit設定中學習RL中的評估。

2.1 $k$ 臂bandit問題

假設反覆面臨一個有 $k$ 個不同選項（或者行動）的選擇，每次選擇後收到一個與所選行動相關、由固定概率分布產生的數字激勵（這裡是每個行動都有自己的概率分布），目標是使一段時間——比如超過1000次選擇或時間步(time step)——後總激勵的期望最大。選定行動後，每個行動都有一個期望或平均激勵，稱之為此行動的價值。記在時間 $t$ 選擇的行動為 $A_t$ ，相應的激勵為 $R_t$ ，則任意行動 $a$ 的價值 $q_*(a)$ 為選中行動 $a$ 的期望激勵：

$q_*(a) dot{=} mathbb E[R_t | A_t=a]$

RL中通常都需要估計行動的價值，記行動 $a$ 在時間 $t$ 的估計價值為 $Q_t(a) approx q_*(a)$ 。在任一步都至少存在一個行動的估計價值是最大的貪婪(greedy)行動。稱選擇貪婪行動為開發(exploit)當前行動價值的知識；選擇非貪婪行動為探索(explore)，能改善非貪婪行動價值的評估。開發(exploitation)使即時激勵最大，但探索(exploration)能產生更大的長期總價值。每一步不可能兼顧探索和開發，這被稱為探索和開發之間的「衝突」。在具體情況中，探索和開發的選擇取決於精確的價值估計、不確定性和剩餘的時間。

2.2 行動-價值方法

行動的價值是選擇它後獲得的平均激勵。一種評估方法是平均實際收到的激勵：

$Q_t(a) dot= frac{ ext{迄時間}t ext{採取}a ext{獲得激勵的總和}}{ ext{迄時間}t ext{採取}a ext{的次數}} = frac{sum_{i=1}^{t-1} R_i ulletmathbf 1_{A_i=a}}{sum_{i=1}^{t=1} mathbf 1_{A_i=a}} ag{2.1}$

其中 $mathbf 1_{predicate}$ 表示斷言(predicate)為真時1否則0的隨機變數。如果分母為0，則將 $Q_t(a)$ 設為一個默認值，比如 $Q_1(a)=0$ 。當分母趨於無窮時，由大數定律， $Q_t(a)$ 收斂於 $q_?(a)$ 。這種行為價值的估計方法被稱為採樣-平均(sample-average)方法。貪心方法每次都選擇貪婪行為 $A_t^*$ ，其中 $Q_t(A_t^*) = max_aQ_t(a)$ 即：

$A_t dot= ext{arg}max_a Q_t(a) ag{2.2}$

為平衡探索和開發，可以使用在大多數時間貪婪、但每隔一段時間（即以小概率 $varepsilon$ ）隨機選擇的近似貪婪(near-greedy)方法，這個方法被稱為為ε-貪婪(ε?greedy)。它的一個優點是在極限情況下，隨著時間步數增長，每個行動都會被無限次採樣，因此保證了所有的 $Q_t(a)$ 收斂於 $q_?(a)$ ；並且保證了選擇貪婪行為的概率收斂於大於1?ε的值，即幾乎是確定事件。

2.3 十臂實驗台(testbed)

為粗略評測貪婪和ε-貪婪的有效性，將它們在反覆隨機生成k=10 bandit的問題上進行量化對比。每個老虎機如圖2.1所示，行動價值 $q_?(a), a=1,cdots,10$ 由均值為0方差為1的正態分布產生。在時間 $t$ 選擇行動 $A_t$ 後，激勵值 $R_t$ 由均值為 $q_?(A_t)$ 方差為1的正態分布產生，即圖中灰色的分布。這個測試套件就是十臂試驗台(testbed)。兩種學習方法都在一個bandit問題進行1000步交互以改善和測試其性能和表現，這是一次運行(run)。用不同問題獨立重複2000次就能獲得學習演算法的平均行為的衡量。

圖2.2在實驗台上用兩種ε貪婪（ε=0.01和ε=0.1）與貪婪方法進行了對比。所有方法都使用採樣-平均來估計行動價值。圖上半部展示了期望激勵隨經驗的增長。初始時貪婪方法比其它方法增長得略快，但隨後在一個較低的水平趨平，因其經常陷於次優行動。圖下半部表明，貪婪方法僅在約1/3的任務上找到了最優行為。ε貪婪則因持續探索和改善識別最優行動的機會最終表現更好。ε=0.1時探索得更多，且通常更早發現最優行為，但超過91%的時間都沒有選擇最優；而ε=0.01方法提高地更慢，但最終在兩個性能測量中都比ε=0.1好。可以通過使ε逐漸減小來兼顧快速找到最優行動和頻繁採取最優行為。

ε貪婪相對貪婪方法的優勢隨任務不同。若激勵的方差變大，激勵相應變得更嘈雜，代理就需要花更多時間探索才能找到最優行為，ε貪婪就能表現得很好。但如果激勵的方差為0，則貪婪方法試過一次後就能知道每個行動的真值，這時表現得最好。不過即使是後者這種確定性的情況，弱化其它假設，探索也會有很大的優勢。例如，假設bandit任務非平穩(nonstationary，有效的非平穩性(nonstationarity)是大多數強化學習的情況），即行動的真值隨時間改變，則即便是確定性的情況也需要探索以確保某個非貪婪行為並未變得比貪婪更好。強化學習需要探索和開發的平衡。

2.4 增量實現

令 $R_i$ 表示第 $i$ 次選擇要評估的行動後收到的激勵， $Q_n$ 表示在被選擇 $n?1$ 次後其行為價值的估計，即： $Q_n dot= frac{R_1 + R_2 + cdots + R_{n-1}}{n-1}$ 。可以改為增量形式來提高效率：

$egin{eqnarray*} Q_{n+1} &=& frac{1}{n} sum_{i=1}^n R_i \ &=& Q_n + frac{1}{n} left[ R_n - Q_n ight] ag{2.3} end{eqnarray*}$

$n=1$ 時任意 $Q_1$ 得到 $Q_2=R_1$ 也成立。假設函數 $bandit(a)$ 輸入行為輸出相應激勵。上面的更新形式十分常見，一般的形式是：

$NewEstimate leftarrow OldEstimate + StepSizeleft[ Target - OldEstimate ight] ag{2.4}$

假定目標為指向移動的正確方向，表達式 $left[ Target - OldEstimate ight]$ 是估計中的誤差(error)，通過向「目標(target)」走一步來減小。本書用符號 $alpha$ 、或更一般的 $alpha_t(a)$ 表示步幅(step-size)參數，有時使用非正式的縮寫 $alpha = frac{1}{n}$ 表示這種情況。使用增量計算樣本均值和 $varepsilon$ -貪婪行為選擇的完整老虎機演算法如下：

2.5 處理非平穩問題

上面討論的方法僅適用於平穩環境。在隨時間改變的非平穩環境中，一個合理的想法是給近期的激勵賦予更多的權重，最普遍的一種做法是使用固定的步長參數。這時上面平均激勵的增量更新規則變為：

$Q_{n+1} dot= Q_n + alpha left[ R_n - Q_n ight] ag{2.5}$

其中步長參數 $alpha in (0,1]^1$ 為常量。這就使得 $Q_{n+1}$ 是過去激勵和初始估計 $Q_1$ 的加權平均：

$Q_{n+1} dot= (1-alpha)^nQ_1 + sum_{i=1}^n alpha(1-alpha)^{n-i}R_i ag{2.6}$

稱這種計算形式為加權平均，因為權重之和 $(1-alpha)^n + sum_{i=1}^n alpha(1-alpha)^{n-i}=1$ 。注意權重 $alpha(1-alpha)^{n-i}$ ，給定激勵， $R_i$ 取決於觀察到它之前的激勵個數即 $n-i$ ，因 $0<1-alpha<1$ ，權重呈指數衰減，也稱之為指數新近加權均值。

有時需要步長參數隨步數改變，令 $alpha_n(a)$ 表示 $n$ 次選擇行動 $a$ 後用於計算激勵的步長參數。選擇 $alpha_n(a) = frac{1}{n}$ 導致採樣-平均方法，大數定律保證了它收斂於真實行動價值。但並非所有 $alpha_n(a)$ 序列的選擇能保證收斂。在隨機逼近理論中，保證以概率1收斂的條件是：

$sum_{n=1}^infty alpha_n(a) = inftyquad ext{and}quadsum_{n=1}^infty alpha_n^2(a) < infty ag{2.7}$

第一個條件保證了步長足夠大能逐漸克服任何初始條件或隨機波動，這二個條件保證了步長逐漸變得足夠小能夠收斂。採樣-平均的步長參數 $alpha_n(a) = frac{1}{n}$ 兩個收斂條件都滿足；常量步長 $alpha_n(a)=alpha$ 不滿足第二個條件，表明這個估計永遠不完全收斂，但對最近收到的激勵持續變化，這實際上正是非平穩環境所想要的。此外，滿足上述收斂條件的步長參數通常收斂很慢或需要大量調試以獲得適當收斂速率，儘管經常在理論工作中用到，但在應用或經驗研究中應用極少。

2.6 最優初始值

前面討論的所有方法都在某種程度上依賴初始行為-價值的估計， $Q_1(a)$ 。在統計學語言中，這些方法偏向初始估計。對採樣-平均方法而言，一旦所有的行為都至少被選中一次以後，偏差就消失；但對 $alpha$ 為常量的方法，偏差是永久的，儘管隨時間逐漸減小。實際上，這種偏差通常並不是問題，而且有時會十分有用。它的缺點是初始估計必須由用戶挑選的參數集給定，如果僅僅將其所有都設為0；優點是提供一種簡單的方法來提供某種關於能期待的激勵層次的先驗知識。

初始值也能作為一種簡單鼓勵探索的方法。若將10臂試驗台的所有行為的初始估計都設為+5。問題中的 $q_*(a)$ 是從均值為0方差為1的正態分布中選出，因此+5這樣的初始估計過於樂觀，它激勵行為-價值方法去探索。無論最初選擇了哪種行為，激勵都會小於初始估計；學習者會對收到的激勵失望，轉向其它行為。結果就是所有的行為都被在價值估計收斂之前都會被嘗試幾次。即便是貪婪方法，系統也會做大量的探索。

圖2.3展示了對所有都使用 $Q_1(a)=+5$ 貪婪方法的在10臂老虎機試驗台的性能；也展示了的貪婪方法作為對比。開始時，樂觀方法表現較差，因其探索很多；但隨著時間增長其減少，因此性能逐漸表現得更好。這種鼓勵探索的技術被稱為樂觀初始價值(optimistic initial values)。它是一種簡單的在平穩問題上非常有效的技巧，但不通用，對非平穩問題就不適用。事實上，任何以特殊方式關注初始狀態的方法都不可能有助於非平穩情況的解決，這也適用於將開始時間作為特殊事件的採樣-平均方法。不過雖然是這樣，所有這些方法都十分簡單，它們中的一個或幾個的組合在實際中經常是夠用的。

2.7 置信區間(upper confidence bound)行為選擇

探索的需求源於行為的價值估計的不確定。 $varepsilon$ 貪婪選擇強制嘗試非貪婪行為，但卻是盲目的，並未偏向那些接近貪婪行為或特別不確定的行為。按照實際成為最優的可能性，既考慮評估與最優值的距離也考慮其不確定性，以此選擇非貪婪行為會更好。一種有效選擇行為的方法為：

$A_t dot= ext{arg}max_a left[ Q_t(a) + c sqrt{frac{log t}{N_t(a)}} ight] ag{2.8}$

其中 $log t$ 表示 $t$ 的自然對數， $N_t(a)$ 表示行為 $a$ 在時間 $t$ 之前被選擇的次數，數字 $c>0$ 控制探索的程度。如果 $N_t(a)=0$ ，則認為 $a$ 是最大化的行為。

其中置信區間上界(UCB)行為選擇的體現是平方根項，是 $a$ 價值估計的不確定性或方差的度量。最大之上的數因此就是行為 $a$ 真實價值的一種上界，參數 $c$ 則確定置信水平。每次行為 $a$ 被選中，則 $N_t(a)$ 增加，不確定項就會減小，不確定性會下降。另一方面，每次其它行為被選中， $t$ 增加了但 $N_t(a)$ 並沒有， $a$ 不確定的估計就會增大。使用自然對數因其增長隨時間減小，但卻是無界的；所有的行為都逐漸會被選中，不過隨著時間的增長等待的時間會更長，因此對於那些價值估計更低或已被更多次選擇的行為被選中的頻率就會更低。

UCB在10臂試驗台上的結果如圖2.4所示，其表現地很好，但相對 $varepsilon$ 貪婪，難以擴展到更一般的強化學習設定中。一方面難以處理非平穩問題，需要應用比2.4節展示的更複雜的方法；另一方面也難以處理巨大狀態空間，尤其是函數近似。在這些更高級的設定中，目前還沒有利用UCB行為選擇思想的實用方法。

2.8 梯度bandit演算法

目前為止本章考慮了行為價值的評估和使用評估來選擇行為的方法。這些方法通常很好，但不是唯一的。現在考慮為每個行為學習一種數值偏好 $H_t(a)$ 。偏好越大，則被選中地越頻繁；這裡僅看中一個行為的偏好比另一個高。如果將1000加到所有的偏好上，則對行為的概率沒有任何影響，行為的概率由如下的softmax分布決定（比如，Gibbs或Boltzman分布）：

$ext{Pr}{A_t=a} dot=frac{e^{H_t(a)}}{sum_{b=1}^k e^{H_t(b)}} dot= pi_t(a) ag{2.9}$

這裡引入記號 $pi_t(a)$ 作為在時間 $t$ 採取行動 $a$ 的概率。所有初始偏好都相同（比如 $H_1(a)=0, forall a$ ），所以所有的行為都等可能被選中。

使用基於隨機梯度上升的學習演算法。每一步在選擇行為並獲得激勵後，如下列這樣更新偏好：

$egin{split} H_{t+1}(A_t) &dot= H_t({A_t}) + alpha(R_t - ar R_t) (1-pi_t(A_t)), & ext{and} \ H_{t+1}(a) &dot= H_t(a) - alpha(R_t - ar R_t)pi_t(a) &forall a eq A_t end{split} ag{2.10}$

其中 $alpha>0$ 是步長參數，而 $ar R_t in mathbb R$ 是開始到現在（包括時間 $t$ ）所有激勵的均值，也可以用增量的形式計算。 $ar R_t$ 項是激勵比較的基準。若激勵高於基準線，則後面採取行為 $A_t$ 的概率就會增加，若低於基準線，則概率降低。未被選中的行為則朝相反的方向移動。

圖2.5展示了梯度老虎機演算法在10臂試驗台、真實期望激勵均值為+4（也是單位方差）的正態分布的結果。因為激勵基準線項的存在，這種同時調整所有激勵到新層次的移動在梯度老虎機演算法上確實沒有影響。但若省略基準線（也就是 $R_t$ 為常數0），則表現會顯著地下降，就如圖中所示。

2.9 關聯搜索（上下文bandit）

目前僅考慮了非關聯的任務，這種情況下無需將不同的狀態與不同的行為結合起來。在這些任務中，學習者要麼在平穩任務中找到單個最佳行為，要麼在非平穩任務中追蹤最佳行為因其會隨著時間改變。但在一般的強化學習任務中，會有多個狀態，目標是學習一個策略：一種從狀態到最佳狀態的行為的映射。下面用最簡單的方法討論將非關聯任務擴展到關聯的設定。

假設有一些 $k$ 臂的bandit任務，在每一步都面對隨機在這些選擇中的一個。因此，bandit任務每步都隨機變化。這似乎是真實行為價值在每一步隨機變化的單個、非平穩的 $k$ 臂bandit任務。可以嘗試使用本章中討論的處理非平穩的方法，但除非真實行為價值改變得非常緩慢，這些方法並不十分有效。但現在假設，當選擇好一個bandit任務後，會給定一些關於期身份的獨特線索（但不是行為價值）。可能實際面對的是隨著其行為價值變化而改變其展示顏色的吃餃子老虎。現在可以學習一種結合每個任務，以所見的顏色為信號，當面臨對應任務時採取相應最優行為的策略——比如，若是紅色，選1；若綠，選擇2。

這是一個關聯搜索任務的例子，這樣稱呼是因為它涉及了搜尋最佳行為的試錯學習和行為與在此情況下最佳的狀態的結合。關聯搜索是 $k$ 臂bandit與完全強化學習問題的媒介。它們很像完全強化學習是因為它們涉及學習一個人策略，但在每個行為僅影響一個中間激勵方面也像我們版本的 $k$ 臂bandit。若行為也影響下一個狀態與激勵，則就是完全強化學習問題了。