一種自適應的多臂賭博機算法

章曉芳 周 倩 梁 斌 徐 進

1(蘇州大學計算機科學與技術學院 江蘇蘇州 215006)2 (計算機軟件新技術國家重點實驗室 (南京大學) 南京 210023) (xfzhang@suda.edu.cn)

強化學習(reinforcement learning, RL)是智能體從環境狀態到動作映射的學習，以使動作從環境中獲得的累積獎賞值最大[1-3].強化學習通過試錯與環境交互獲得策略的改進，這就導致一個問題：哪一種試錯策略可以產生最有效的學習.因此強化學習面臨探索(exploration)和利用(exploitation)的兩難問題：長期來看，探索可能獲得更高的累積獎賞，幫助智能體收斂到最優策略；而利用總是最大化短期獎賞，但可能收斂到次優解上[4-5].多臂賭博機(multi-armed bandit, MAB)問題是強化學習中研究探索與利用平衡的經典問題.

隨機多臂賭博機(stochastic multi-armed bandit, SMAB)問題是一類經典的MAB問題,該問題最早由Robbins提出[6].一個MAB問題中包括K個臂，玩家每次只能選擇其中一個臂，并獲得相應的獎賞.n輪游戲后，玩家的目標是最大化獎賞的期望值.其中，玩家選擇某個臂之后只能知道該臂的獎賞，且各個臂的獎賞是相互獨立的，服從某種未知的分布.為了達到目標，玩家需要在獲得獎賞的同時去學習該獎賞的分布.因此，每個時間步，玩家都必須在以下兩者做出選擇：利用，選擇目前為止已知獎賞最高的臂；探索，嘗試其他未來獎賞可能更高的臂.這樣，在游戲過程中玩家面臨著探索與利用間的平衡問題.

作為一個序列化的決策問題，MAB被應用于很多實際場景中，最早的應用就是Robbins提出的診治試驗[6].診治試驗中各個患者的治療方案對應MAB問題中的各個臂.診治試驗的目標是最小化患者的健康損失.近來，MAB問題有了更多廣泛的應用，比如推薦算法[7-9]、眾包機制[10-12]、搜索引擎關鍵字選擇[13]、網絡信道選擇[14]等.除了SMAB問題，MAB問題還存在多個變種，例如Markov賭博機(Markovian bandit)[15]，對抗式賭博機(adversarial bandit)[15]和上下文相關的賭博機(contextual bandit)[16]等.在上下文相關的賭博機問題中，玩家選擇一個臂之后，除了獲得相應的獎賞之外，還可以獲得該臂的上下文信息.本文將研究SMAB問題，提出一種自適應的MAB算法，并將其推廣到上下文相關的場景中.

目前已有很多策略來平衡MAB問題中探索與利用的難題.Watkins首次引入ε-貪心(ε-greedy)算法[17]，ε-greedy算法以一個很小的概率ε進行探索，以1-ε的概率利用.但是ε-greedy算法將在所有臂中均等選擇進行探索，沒有利用選擇臂之后獲得的信息，比如各個臂的平均獎賞和選擇次數.軟最大化(SoftMax)算法最早由Luce提出[18]，SoftMax算法是基于當前已知臂的平均獎賞來對探索和利用的程度進行折中.然而SoftMax算法只考慮了平均獎賞，這種較為單一的信息可能導致錯誤的概率分配，比如某個臂第一次被選擇，隨機得到一個很低的獎賞，SoftMax算法根據這一次的獎賞為該臂分配了很低的選擇概率，但該臂有可能是初期獎賞低而實際平均獎賞很高的臂.置信上界 (upper-confidence-bound, UCB)動作選擇方法[19]則根據各個臂已知的平均獎賞和選擇次數直接計算出要選擇的臂，不利用隨機性來選擇臂.使用UCB算法時必須在初期輪流選擇所有臂各一次，那么當實驗次數小于等于臂的數量時，難以使用UCB方法，因此UCB方法泛化能力較弱.LinUCB算法[20-21]是經典的上下文相關的MAB算法，利用上下文信息最大化獎賞的期望值.然而LinUCB算法只適用于上下文可用的場景中.

本文針對上述隨機多臂賭博機算法未能充分使用反饋信息以及泛化能力較弱的問題，提出了一種自適應的多臂賭博機算法，利用當前估計值最小的動作被選擇的次數(chosen number of arm with minimal estimation, CNAME)來調整探索和利用的概率，記為CNAME算法.本文的主要貢獻有3個方面：

1) 提出了一種自適應的隨機多臂賭博機算法CNAME，其探索概率由一個簡單分式給出，該分式由當前平均獎賞最小的臂被選擇的次數和參數w構成，充分利用了選擇臂之后的信息.該算法不依賴上下文信息，因此在各個應用場景中具有更強的推廣能力和泛化能力.

2) 通過理論分析給出了CNAME算法的悔值(regret)上界，并與其他算法的悔值上界進行對比，為CNAME算法提供了有力的效果保證.

3) 通過實驗研究給出了CNAME算法中關鍵參數的參考取值范圍.在無上下文的隨機數據集和內容分發網絡(content distribution network, CDN)[22]數據集以及帶有上下文的雅虎公司R6A數據集上的實驗結果表明：利用估計值最小的動作被選擇的次數能有效平衡探索和利用，并且在上下文相關的場景中依然表現良好.

1 背景和相關工作

1.1 隨機多臂賭博機問題

隨機多臂賭博機問題，又稱為K-臂賭博機問題，K即為臂的數量，下文把各個臂統稱為動作.K-臂賭博機的目標是最大化獲得的累積獎賞.若時刻t動作i被選擇，則獲得隨機獎賞Xi,t.各個動作的獎賞相互獨立且服從均值為μ=[μ1,μ2,…,μK]的某種分布，μi是動作i的真實值.假設已知各個動作的真實值，只要一直選擇有最高真實值的動作便可以獲得最大的累積獎賞，這種情況下多臂賭博機問題自然得解.然而，事實上隨機多臂賭博機問題可以通過獲得的獎賞來估計各個動作的值，但動作的真實值是未知的.

悔值是K-臂賭博機的一種典型的度量標準[15].在動作真實值未知的情況下，任何算法都不可能每次都選到獎賞最高的動作，悔值就是實際得到的獎賞與期望得到的最大獎賞之間的差值.給定n次操作后的悔值定義為

(1)

其中，Nn(i)是前n次操作中動作i被選擇的次數.悔值越小，則該算法產生的策略越接近最優策略.

1.2 估計值函數

動作的真實值是選擇動作后期望得到的平均獎賞，因此一種估計動作值的簡單方法是計算選擇動作之后實際獲得的平均獎賞.假設第n次操作之后，動作i已經被選擇Nn(i)次，得到的獎賞分別是r1,r2,…,rNn(i)，這時動作i的估計值為

(2)

Qn+1(i)是到第n次操作之后的動作i的估計值，即動作i實際獲得的平均獎賞.根據式(2)，Qn+1(i)的更新需要記錄每次選擇動作i之后獲得的獎賞，為了減小需要的存儲空間，估計值的更新可以轉化為增量式的更新：

(3)

根據式(3)，估計值的更新只需要存儲立即獎賞和上一時刻的估計值.若Nn(i)=0，Qn(i)為初始值；當Nn(i)→∞時，根據大數定理可知Qn(i)收斂到動作i的真實值.這種方法叫作抽樣平均(sample average)[23]，每個估計值都是獎賞的簡單平均值.因此，通過以上方法得到動作的估計值后，可以根據估計值作出動作選擇.

1.3 動作選擇方法

本節主要介紹已有的3類經典隨機多臂賭博機算法.

1.3.1ε-greedy方法及其變種

最簡單的動作選擇方法是一直選擇估計值最高的動作，即貪心動作a*，這種方法稱為貪心(greedy)方法[1].貪心方法利用當前知識最大化立即獎賞，沒有探索的過程.

一個簡單的代替貪心的辦法是在大多數時間內采用a*，但是以一個很小的概率ε進行探索，即與估計動作值無關地隨機均勻地選擇一個動作，該方法為ε-greedy[17]，ε位于開區間(0,1)上.

ε-greedy算法的一個變種是ε-優先(ε-first)算法[24]，ε-first算法在實驗初期先做完所有的探索工作.例如對于一個給定實驗次數為n的實驗，在最初的εn次實驗中隨機選擇動作，即純探索階段，在余下的(1-ε)n次實驗中，選擇平均獎賞最高的動作，即純利用階段.

ε-greedy算法的另一個變種是ε-遞減(ε-decreasing)算法[25].ε-decreasing算法用一個遞減的概率來接近最優策略，遞減變量εt由εt=min{1,ε0t}給出，其中t是時間步，初始參數ε0>0.此外，Cesa-Bianchi等人[25]提出了混合貪心(greedy mix)算法，用遞減因子1lnt代替了ε-decreasing算法的遞減因子1t.類似地，Strens[26]提出了Least Taken算法，Vermorel等人[27]則在Least Taken算法的基礎上添加了初始參數ε0.

1.3.2 SoftMax方法及其變種

盡管ε-greedy算法是一類有效的方法，但是ε-greedy算法在探索的時候是在所有的動作中均等選擇.這就意味著ε-greedy算法選擇下一個動作時有可能選到最差的動作.為了避免這種情況，SoftMax方法將探索概率更改為與估計值相關的一個分級函數：貪心動作仍然具有最高的選擇概率，其他動作則根據其估計值進行分級并分配權重.SoftMax算法廣泛使用Gibbs或Boltzmann分布，時刻t選擇動作i的概率為

(4)

其中,τ是溫度(temperature)參數[28].高溫可以使得各動作的選擇概率趨于相等，低溫則使具有不同估計值的動作的選擇概率趨于不同.當τ→0時，SoftMax算法的作用與greedy方法一致.

與ε-greedy算法相似，SoftMax算法可以變形為遞減的軟最大化(decreasing SoftMax)算法[25]，decreasing SoftMax算法的溫度隨時間步的增加而遞減，即τt=τ0t.類似地，可以用遞減因子1lnt代替decreasing SoftMax算法的遞減因子1t[25].作為一個更復雜的SoftMax算法變種，Exp3算法的關鍵在于利用了累計獎賞與動作選擇概率的比值[25].

1.3.3 UCB方法

由于動作值的估計具有不確定性，因此，需要在動作選擇過程中引入探索.然而，非貪心動作中有接近貪心的動作，也有很差的動作.如果能根據非貪心動作成為最優動作的可能性進行探索，探索的效果往往會更好.

基于上述的思想，UCB算法動作選擇方法同時考慮非貪心動作估計值對最優動作估計值的接近程度和估計值的不確定性：

(5)

雅虎公司的科學家在UCB算法的基礎上引入了上下文信息，提出了LinUCB算法[20]，并應用于雅虎公司的新聞推薦中.LinUCB算法假設一個玩家選擇一個動作之后，其獎賞和上下文信息成線性關系.于是學習過程就變成：用玩家和動作的上下文信息預估獎賞及其置信區間，選擇置信區間上界最大的動作，觀察獎賞后更新線性關系的參數，以此達到最大化獎賞期望值的目的.

1.3.4 已有算法存在的問題

基于上述討論可知：ε-greedy算法是一個簡單有效的方法，其存在的問題是在所有動作中均等探索，沒有利用選擇動作后獲得的反饋信息.SoftMax算法僅基于當前已知動作的估計值對各動作的選擇概率進行分級，因此SoftMax算法容易被誤導.ε-greedy算法和SoftMax算法都僅需要設置一個參數，計算相對簡單.與上述2種方法不同的是，UCB動作選擇方法充分利用了動作的估計值和被選擇次數，每次都根據已有信息直接計算出要選擇的動作，其計算開銷相對較大.另外，UCB動作選擇方法必須在實驗初期輪流選擇所有動作各一次，因此當實驗次數小于等于動作的數量時，UCB動作選擇方法將不適用.LinUCB算法則只適用于上下文信息可用的場景中，實際應用中存在著大量沒有先驗信息的環境，此時LinUCB算法的使用將受限.

2 算法描述

本文針對已有的隨機多臂賭博機算法存在的不足，提出了一種自適應的隨機多臂賭博機算法(CNAME).

2.1 CNAME算法描述

探索概率的變化將直接影響探索和利用的平衡.針對該問題，本文提出一種新的探索概率計算方法：

p=w

其中,mt是當前平均獎賞最小的動作被選擇的次數，參數w>0用來控制探索概率衰減的速率，起到宏觀調控的作用.w和mt共同控制探索概率.該計算方法可以充分利用選擇動作之后的信息，根據環境自適應地調整探索概率，平衡探索和利用.本文3.1節將通過實驗討論參數w對CNAME算法效果的影響及其參考取值范圍.

CNAME算法以w的概率選擇目前最少被選擇的動作，即探索；或者選擇當前估計值最大的動作，即利用.具體如算法1所示：

算法1. CNAME算法.

輸入：動作集合;

輸出：估計值.

① 設置參數w;

② for 每個動作i∈[1,2,…,K] do

③Q0(i)=0;

④N0(i)=0;

⑤ end for

⑥ for 每個時間步t≤ndo

⑨ 在開區間(0,1)上產生一個隨機數x;

Qt-1(at)];

根據算法1，步驟①首先設置CNAME算法的關鍵參數w，參數w影響著探索概率衰減的速率.步驟②～⑤初始化動作的估計值和被選擇的次數，即Q0(i)=0，N0(i)=0.這里也可以使用樂觀初始值，比如Q0(i)=1，樂觀初始值在實驗初期可以臨時地促進探索[1].步驟⑥～⑩為動作選擇的過程，n是實驗次數，mt是時刻t估計值最小的動作已經被選擇的次數，p是當前的探索概率.步驟⑩在選擇動作時，同時考慮了實際獲得的平均獎賞和動作選擇的次數.步驟是選擇動作at后獲得立即獎賞該獎賞服從某種概率分布.步驟對動作被選擇的次數和估計值進行更新，其中，估計值更新方法采用的是增量式抽樣平均方法.

2.2 CNAME算法分析

在任何一個特定環境下，探索的效果更優還是利用的效果更優取決于估計的精確值、環境不確定性和剩余操作次數等復雜的具體情況[1].

CNAME算法充分利用了用戶反饋，即動作估計值和動作選擇的次數，自適應地根據實際情況來調整探索概率.同時，通過參數w控制探索概率下降的速率，并根據mt來改變探索概率.具體從3個方面分析：

1) 當參數w的取值較大時，mt對探索概率的影響較小；當參數w的取值較小時，mt對探索概率的影響則較大.由于不同環境中mt的實際影響也不同，本文設計參數w來削弱或者增強mt在調整探索概率時起到的作用.

2) 每當mt增加一次，說明估計值最小的動作又被選擇了一次，估計值最小的動作是對整個累積獎賞貢獻最少的動作，應盡量減少該動作被選擇的次數.隨著mt的增加，探索概率降低，貪心動作的選擇概率增加，這樣有助于提高實際獲得的累積獎賞.

3) CNAME算法在探索時選取的是當前最少被選擇的動作，這樣就保證每個動作都有被選擇到的機會，同時避免了隨機選擇動作的盲目性.

2.3 CNAME算法的悔值上界證明

基于2.1～2.2節的算法描述和分析，本節將通過證明給出CNAME算法的悔值上界.悔值用來評價算法的好壞，悔值上界越小，說明該算法的效果越好.

Lai等人[29]發現，對于均值為單一參數的獎賞分布，所有算法都滿足：

(6)

對于某個算法A，根據式(1)(6)，若已知算法中pi的上界，便可得到算法A的悔值上界.為了方便證明，給出已知的2個不等式：

引理1. Chernoff-Hoeffding不等式.

設X1,X2,…,Xn為[0,1]之間的隨機變量，且E[Xt|X1,X2,…,Xt-1]=μ，Sn=X1+X2+…+Xn.那么對于所有的a≥0都有：

引理2. Bernstein不等式.

定理1. 第n次操作時，CNAME算法的次優動作選擇概率pi不超過：

令εn表示第n次操作的探索概率，即

(7)

(8)

根據Bernstein不等式(引理2)可以得到：

(9)

求解x0，具體過程為

(10)

當n≥K時，結合式(7)～(10)可得：

那么對于CNAME算法，w>0，若n≥K，那么在第n次操作時動作i的選擇概率pi有：

(11)

證畢.

定理2. 第n次操作時，CNAME算法的悔值滿足:

證明. 結合式(6)(11)可得到E[Nn(i)]的下界為

(12)

最后，根據式(1)(12)可得出CNAME算法的悔值上界：

證畢.

3 實驗部分

本節通過4組實驗來分別研究CNAME算法中參數w的影響以及CNAME算法與其他算法的效果比較.在對比實驗中，使用3個數據集：服從正態分布的隨機數據集、內容分發網絡數據集[22]和帶有上下文信息的雅虎公司R6A數據集①.

3.1 實驗1：CNAME算法中參數w的影響

本節的實驗對象是一組有1 000個隨機產生的K-臂賭博機的任務，其中K=10.具體實驗設置如下：

1) 每個任務的真實值μ=[μ1,μ2,…,μK]服從均值為0、方差為1的正態分布.

2) 每個動作i的獎賞服從一個均值為μi、方差為1的正態分布.

3) 1 000個K-臂賭博機任務通過1 000次重復隨機選擇μ產生，選取1 000個不同的K-臂賭博機任務是為了克服任務和環境本身的隨機性.

在上述實驗條件下取不同的w值，分別記錄1 000個隨機任務的平均獎賞和平均每輪的悔值.

首先，在閉區間[0.01,100]以10的倍率分別取5組不同的w值，圖1給出了相應的平均獎賞和平均每輪的悔值.

Fig. 1 Average rewards and average regrets of algorithm CNAME with different values of parameter w圖1 不同w值下CNAME算法的平均獎賞和平均悔值

從圖1可以看出：當w∈[1,100]時，隨著w的減小，平均獎賞呈增加趨勢，而平均每輪的悔值呈下降趨勢.然而當w=0.1和w=0.01時獲得的平均獎賞卻小于w=1時的平均獎賞，即平均獎賞并不是隨著w的減小而無限增加的.同時，平均每輪的悔值的下降也存在下限.基于圖1的數據，可以猜測，w=1是CNAME算法效果的分界線，w<1或w>1時，效果均下降.較之其他w的取值，當w取值為0.1和1時，CNAME算法的平均獎賞較高，平均每輪的悔值較低.

為進一步研究當w∈[0.1,1]時，CNAME算法的性能，下面以0.1為間隔分別取10組不同的w值展開實驗.表1給出了對應的實驗結果數據，加粗部分是效果最好的參數及結果.

Table 1 Average Rewards and Average Regrets of

Note: The best result is highlighted in bold.

基于圖1和表1的數據，可以確認當w∈[0.1,1]時，CNAME算法能夠獲得較高的平均獎賞和較低的平均悔值.此外，根據表1可知，當w取值較為接近1時，比如w=0.9時，獲得的平均獎賞更大，平均每輪的悔值更小，即CNAME算法的效果更好.

僅以平均獎賞為例對圖1和表1的實驗結果進行分析，主要有2個原因：

1) 當w的取值過小時，探索概率的衰減速率過快，導致沒有足夠的探索，無法得到最高的累積獎賞.

初始時刻m0=0，CNAME算法探索的概率為1，此時接近隨機策略.一定時間步之后，當mt≠1時，探索概率開始衰減，w越小，衰減的速率越高.例如當w=1，mt=1時，探索概率為0.5；當mt=2時，探索概率降為0.2，算法效果近似于ε-decreasing.而當w=0.01，mt=1時，探索概率為0.009 9；當mt=2時，探索概率衰減到0.002 5，這時算法效果類似于greedy，可能會忽略更優的動作，從而不能獲得最高的平均獎賞.因此，w取值過小，平均獎賞反而會有所下降.

2) 當w的取值較大時，探索概率的衰減速率過慢，導致過度探索，平均獎賞相對較小.

例如當w=100，mt=1時，探索概率為0.990；mt=2，探索概率為0.962.mt的增加對探索概率的影響過小，不能及時地減少探索概率，導致了過多的探索，使得平均獎賞較小.因此w取值過大，平均獎賞相對較小.

綜上所述，參數w應根據實際環境適當取值，不宜過大也不宜過小.根據實驗結果，該環境下CNAME算法的參數w取閉區間[0.1,1]中的值較好.

3.2 實驗2：隨機數據集上的比較

本節基于隨機數據集，比較CNAME算法和其他3類經典算法及其變種的算法性能.

與實驗1相似，本實驗同樣采用隨機產生的服從正態分布的數據集：1 000個隨機產生的多臂賭博機任務.具體地，K=10，n=2 000；μ=[μ1,μ2,…,μK]服從均值為0、方差為1的正態分布；每個動作i的獎賞服從一個均值為μi、方差為1的正態分布.根據實驗1的結果，本次實驗中，參數w=0.95.

在上述實驗條件下，分別記錄各個算法的平均獎賞和平均每輪的悔值.表2列出了實驗中6種算法的參數設置、對應1 000個任務在2 000個時間步下的平均獎賞和平均每輪的悔值.各個算法均采用的是該實驗條件下效果較好的參數，表2中加粗部分是效果最好的結果.

從表2可以看出，該實驗條件下，CNAME算法獲得的平均獎賞最高，平均每輪的悔值最低.變種ε-decreasing算法的效果明顯優于ε-greedy算法的效果；類似地，變種decreasing SoftMax算法的效果優于SoftMax算法.

Table 2 Parameters and Experimental Results of

Note: The best result is highlighted in bold.

為了簡潔清晰地表示這幾種算法的對比效果，圖2和圖3僅分別展示了ε-decreasing，decreasing SoftMax，UCB1，CNAME這4種算法運行至1 000個時間步時的實驗數據.圖2是CNAME算法與其他3種算法平均獎賞的結果比較.圖3為CNAME算法與其他3種算法的悔值的比較，同時給出了CNAME算法平均悔值的上界(upper bound).基于2.3節得出的悔值上界，upper bound是平均每輪的悔值上界.由圖3可知，隨著時間步的增加，upper bound的值保持平穩，可見CNAME算法非常穩定.另一方面，CNAME算法各個時間步的平均悔值均在upper bound之下，符合2.3節的理論結論.

Fig. 2 Average rewards of CNAME and the other three algorithms圖2 CNAME算法與其他3種算法的平均獎賞

Fig. 3 Average regrets of CNAME and the other three algorithms圖3 CNAME算法與其他3種算法的平均每輪的悔值

表2、圖2和圖3中的數據均是1 000個隨機任務的平均值.結合圖表，本文從3方面進行比較：

1) CNAME算法和ε-greedy算法及其變種

CNAME算法的收斂速度略低于ε-decreasing算法，但其平均獎賞明顯高于ε-greedy算法和ε-decreasing算法，平均每輪悔值也明顯低于ε-greedy算法和ε-decreasing算法.CNAME算法的效果與ε-greedy算法和ε-decreasing算法相比有了很大的提高.

這是因為CNAME算法利用了用戶反饋，雖然收斂速度有所減小，但效果比探索概率固定不變的ε-greedy算法好很多.同理，ε-decreasing算法的探索概率雖然是隨著時間降低的，但是沒有利用選擇動作之后的信息，因此其效果比CNAME算法差.

2) CNAME算法和SoftMax算法及其變種

CNAME算法的收斂速度略低于decreasing SoftMax算法，但其平均獎賞高于SoftMax算法和decreasing SoftMax算法，且平均每輪的悔值較低.因此，CNAME算法的效果與SoftMax算法和decreasing SoftMax算法相比有所提高.

這是因為與SoftMax算法相比，CNAME算法除了考慮動作估計值，還考慮了動作被選擇的次數，比SoftMax算法和decreasing SoftMax算法利用的信息多，雖然收斂速度略有降低，但不易被前期的估計值誤導.因此CNAME算法最終獲得的平均獎賞和平均每輪悔值均優于SoftMax算法和decreasing SoftMax算法.

3) CNAME算法和UCB1算法

CNAME算法的收斂速度與UCB1算法相當，但其平均獎賞高于UCB1算法，且平均每輪的悔值低于UCB1算法.值得注意的是，通過分析實驗數據的變化，我們發現：CNAME算法的數據波動較小，而UCB1算法在實驗初期的數據會出現尖峰.

這是因為CNAME算法和UCB1算法均充分利用了選擇動作之后的信息，兩者收斂速度相當.但是UCB1算法在初期的前K次操作中，先將每個動作輪流選擇一次，在第K+1次操作時選擇貪心動作，因此UCB1算法會在第K+1操作時出現尖峰.而CNAME算法在第K+1次操作時，依然根據當前的探索概率選擇動作，因此CNAME算法的數據不會出現尖峰.

綜上所述，CNAME算法是一種有效的多臂賭博機算法.

3.3 實驗3：內容分發網絡數據集上的比較

實驗3采用的數據集對應于真實環境中可用資源冗余情況下的數據檢索問題.例如在內容分發網絡中，agent必須通過一個可用資源冗余的網絡來檢索數據.假設每次檢索agent只選擇一個資源，直到檢索到數據，agent的目標是最小化檢索的累積延時.該問題可轉換為隨機多臂賭博機問題進行處理[27]，3項具體說明如下：

1) 實驗3用超過700個學校的主頁作為資源，每一個主頁對應多臂賭博機中的一個臂(動作).

2) 這些主頁約每隔10 min被檢索一次，共記錄了10 d的檢索延遲信息(約1 300條)，單位為ms.

3) 每一個延時對應一個負獎賞，因此，平均延時越小，對應算法越有效.

上述延時數據來源于實際問題，數據范圍廣、波動大，而且隱含了實際環境中的各種干擾和影響.本文分別利用各個算法對該數據集進行處理，更能體現各個算法性能的差異和各自的穩定性.

表3是6種算法平均每輪的檢索延時，這些數據是1 000次模擬的平均結果.考慮到實際環境的隨機性，每次模擬中延時的順序都是隨機的.

Table 3 Average Latency of Six Algorithms表3 6種算法的平均延時

Note: The best result is highlighted in bold.

從表3可以看出，使用ε-greedy，ε-decreasing，SoftMax，decreasing SoftMax這4種算法得到的平均延時明顯高于UCB1和CNAME算法.這主要是因為關于延時的網絡數據通常波動很大，而且延時數據的取值范圍很廣，可能是10 ms，也可能是1 000 ms.對于這樣的數據，需要非常小心地探索，因為嘗試一個動作有可能得到很小的延時，但也有可能得到一個突增的延時.這種情況下，UCB1算法和CNAME算法的優勢很明顯，這2種算法同時根據動作的估計值和被選擇的次數自適應地調整探索和利用，充分利用了反饋信息.

雖然UCB1算法和CNAME算法最后得到的平均延時相當，但CNAME算法只需要約2 min就可以完成計算，而UCB1算法則需要約6 h.這主要是因為UCB1算法相對復雜，計算負擔較大，所以需要較長的計算時間；而CNAME算法的計算則相對簡單，計算負擔較小，極大地節約了計算時間.

可見，CNAME算法可以更加高效地平衡隨機多臂賭博機問題中的探索和利用.

3.4 實驗4：雅虎公司 R6A數據集上的比較

在線內容推薦是交互式機器學習問題的重要內容，需要在探索和利用之間進行有效的平衡.實驗4將推薦系統建模為多臂賭博機模型.雅虎公司R6A數據集包含45 811 883個用戶訪問雅虎公司首頁Today模塊的點擊日志.對于每次訪問，用戶和每個候選文章都有關聯的6維的特征向量.

本節對比了CNAME算法與其他3種算法在雅虎公司R6A數據集上的推薦效果，實驗結果如圖4所示，縱坐標表示累計獎賞，對應推薦系統中的點擊次數.其中，Random算法作為基準算法，每次為用戶隨機推薦物品，LinUCB算法為上下文相關的多臂賭博機算法.

Fig. 4 Cumulative rewards of CNAME and the other three algorithms圖4 CNAME算法與其他3種算法的累計獎賞

從圖4可以看出，Random算法的累計獎賞最低，這是因為Random算法只是隨機產生推薦，沒有利用用戶反饋信息.CNAME算法獲得的累計獎賞明顯高于UCB1算法.UCB1算法在初期將各個物品輪流推薦給用戶，在物品數量較大的情況下不能及時地學習到用戶的興趣.因此，UCB1算法在初期獲得的累計獎賞接近Random算法，后期獲得的累計獎賞則快速增加.

LinUCB算法作為經典的上下文相關的多臂賭博機算法，主要結合數據集中的6維特征向量進行推薦，在100個時間步后獲得的累計獎賞為78.由于LinUCB算法依賴用戶和物品的特征向量，而不同推薦系統中的特征向量維度和含義不同，LinUCB算法無法方便地推廣到不同的應用場景.CNAME算法基于探索概率，在利用用戶反饋進行推薦的同時，探索可能為用戶帶來驚喜的物品.因此CNAME算法獲得的累計獎賞很高且穩定增長，100個時間步后獲得的累計獎賞高達98，累計獎賞高于基于上下文信息的LinUCB算法.CNAME算法在推薦的過程中，一方面根據用戶反饋，自適應地調整探索概率，另一方面不依賴上下文信息，可以方便地應用到各個場景中.

4 總 結

本文提出了一種自適應的隨機多臂賭博機算法，即CNAME算法.該算法充分利用選擇動作之后獲得的信息，同時考慮動作的估計值和被選擇的次數，簡便高效地解決了隨機多臂賭博機中探索和利用的平衡問題.CNAME算法根據當前估計值最小的動作(即實際獲得的平均獎賞最小的動作)已經被選擇的次數mt和參數w共同控制探索的概率，自適應地根據實際環境調整探索和利用的程度.同時，CNAME算法在探索時選擇目前最少被選擇的動作，避免了隨機選擇動作的盲目性.

一方面，本文通過理論分析和證明給出了CNAME算法的悔值上界，為CNAME算法的性能提供了有力的理論支持.另一方面，本文通過4組實驗討論了CNAME算法的關鍵參數w的影響及參考取值范圍并分別在隨機數據集，內容分發網絡數據集和帶有上下文信息的雅虎公司 R6A數據集上與其他3類經典算法及其變種進行了對比實驗.實驗表明CNAME算法與ε-greedy算法和ε-decreasing算法相比有了很大的提高，效果比SoftMax算法和decreasing SoftMax算法略好，比UCB1算法更高效.此外，CNAME算法的泛化能力較強，在雅虎公司R6A數據集上獲得了與LinUCB算法相當甚至更好的效果.綜上所述，CNAME算法是一種效果穩定、高效且泛化能力強的多臂賭博機算法.

未來工作嘗試將CNAME算法應用到更加復雜的多臂賭博機問題中，比如帶有預算的多臂賭博機問題[30]、定性的多臂賭博機問題等[31]；同時，探討CNAME算法解決復雜問題的可能性，嘗試提出有實際應用的新型多臂賭博機問題.此外，考慮與深度學習相結合，生成深度網絡多臂賭博機，以解決更加復雜的問題.