穩健的重尾線性賭博機算法

馬蘭霽弘 趙 鵬 周志華

（計算機軟件新技術國家重點實驗室（南京大學）南京 210023）

許多現實世界的應用可以被建模為面對不確定因素時的序列決策問題，其基本挑戰是探索（exploration）和利用（exploitation）之間的權衡困境.多臂賭博機[1]是一種系統化模擬這類問題的模型，在該模型中，學習者每輪從搖臂池中選擇1 個搖臂，隨后從環境中收到選擇的搖臂所對應的獎賞.學習者的目標是盡可能最大化所獲得的累積獎賞，因此學習者必須在收集更多關于獎賞分布的數據（探索）和選擇到目前為止最有可能取得最高獎賞的搖臂（利用）之間取得平衡.

隨機線性賭博機是多臂賭博機在實際應用中的一個自然和重要的變體，已經引起了相當大的關注.其通常假設每個搖臂都具有其對應的d維特征，這些特征通常被稱為“上下文信息”（contextual information），學習者需要根據上下文和所獲得的歷史獎賞信息來選擇下一個搖臂.在第t輪中用xt表示所選搖臂的特征信息，該搖臂所能獲得的獎賞可參數化為其上下文信息的線性函數，額外加上滿足一定性質的噪聲 ηt.其形式化為

其中θ ∈Rd是未知的回歸系數，ηt是服從亞高斯分布的噪聲.盡管該模型非常簡單，但是它已被廣泛應用于許多現實場景，如臨床試驗[2]和個性化推薦[3].

在現實世界的應用中，在線數據通常是從開放動態的環境中收集的，導致數據的不規范性經常出現，而這些不規范性又進一步限制了標準模型式（1）及其相應算法的使用.在本文中，我們特別關注2 類開放動態環境下經常出現的數據不規范性——分布變化（distribution charge）和重尾噪聲（heavy-tailed noise）.分布變化指的是搖臂的獎賞分布可能隨時間變化，導致標準模型式（1）中的回歸系數 θ隨時間變化，這意味著根據以往的歷史數據學習很可能得到一個對當前時刻有偏的模型；重尾噪聲指的是標準模型式（1）中的噪聲 ηt可能服從重尾分布，而不是統計性質良好的亞高斯分布，如金融市場投資的極端收益[4]和神經振蕩的波動[5]等實際場景.這2 種數據不規范性使得傳統的決策模型不再具有以往的獨立同分布性質而難以分析.據我們所知，在線性賭博機問題上，目前還沒有相應的算法能同時處理這2 個因素.

在本文中，我們研究了重尾線性賭博機算法（heavytailed linear bandits algorithm)，名為RM-LinUCB，該算法同時對分布變化和重尾噪聲具有穩健性.該算法由3 個關鍵部分組成：置信上界，用于解決序列決策問題中的探索與利用的平衡；均值中位數估計器，用于減少潛在的重尾噪聲所引起的估計誤差；重啟策略，用于解決分布變化問題，當歷史上下文和獎賞分布不符合當前數據分布時，定期重啟并開始新的參數估計.在理論保障方面，對同時包含分布變化和重尾噪聲的線性賭博機問題建立了遺憾下界，其結果表明：最壞情況下，存在某個特例使得任意算法的遺憾界至少為其中的物理含義是回歸系數在總時間T中的累積變化，其反映了環境的動態變化程度.除此之外，我們對本文提出的算法進行了遺憾界分析，證明了該算法具有的遺憾上界保障，這意味著本文的算法所產生的遺憾界隨總時間T是次線性的，即該算法產生的每輪平均遺憾將隨總時間T的增大收斂至0，有時也稱該算法是“無悔的”（no-regret）.此外，該算法所產生的遺憾界包含了沒有分布變化或重尾噪聲情況下所產生的遺憾界.在此基礎上，本文還設計了一個實用的技巧，使得本文的算法在缺乏對于數據不規范性的先驗信息時仍能夠應付未知的環境變化.最后我們在合成和真實世界的數據集上進行實驗來驗證算法的有效性.

1 相關工作

本節首先介紹隨機線性賭博機的發展，然后就數據不規范的2 類問題（分布變化和重尾噪聲）分別討論一些相關的工作.

1.1 隨機線性賭博機

對于隨機線性賭博機問題的研究可以追溯到Naoki 等人[6]的工作.Dani 等人[7]首先建立了（穩態）線性賭博機問題的最小下限，表示對于時間長度為T、特征維度為d的隨機線性賭博機問題，任意在線算法在該問題上都至少具有的遺憾下界；并且進一步設計了一種基于置信上界的算法，證明了其具有的遺憾上界，其中O(·)省略了與T相關的對數項.隨后，Abbasi-Yadkori 等人[8]的開創性工作通過引入自歸一化過程的分析技巧，大大簡化了算法設計和遺憾分析過程，并證明了與Dani 等人[7]相同的（甚至在一些lnT階更緊的）遺憾上界.該研究思路在后來的研究中[9-13]得到了積極的發展.更多關于隨機線性賭博機的介紹，我們推薦讀者參考該領域專著[14].

1.2 分布變化

傳統機器學習依賴于環境封閉的靜態假設，當環境發生動態變化時可能不夠穩健[15-17].由于數據收集環境可能不斷變化，在線數據的分布隨之不斷變化，這為在線學習技術帶來了巨大的挑戰.此問題已經引起許多研究者的關注，并嘗試在一些具體的在線學習場景中處理環境變化帶來的影響[18-24].Cheung 等人[25]對分布變化場景下的隨機線性賭博機問題進行建模，并證明了該問題的最小遺憾下界為其中代表回歸系數在總時間T內的累積變化，有時 PT又被稱為路徑長度（path-length）.此外，Cheung 等人[25]提出使用滑窗最小二乘估計器來估計回歸系數，并基于此估計進一步執行置信上界算法，證明了該算法具有的遺憾上界.通過使用加權最小二乘估計器[26-27]代替滑窗最小二乘估計器，Russac 等人[28]提出D-LinUCB 算法，在不存儲歷史數據的情況下得到了與Cheung 等人[25]相同的遺憾上界.D-LinUCB 的優勢在于其是在線更新的，其劣勢是需要計算較大的2 個協方差矩陣，計算效率不高.然而，Zhao 等人[29]指出文獻[25,28]遺憾上界結果的理論證明中存在技術缺陷，導致其給出的遺憾上界實質上不成立.Zhao 等人[29]還提出了一種技術修補方案對遺憾上界進行重新分析，證明文獻[25,28]算法的遺憾上界應修正為除此之外，Zhao 等人[29]還提出了一種新穎的基于重啟策略的線性賭博機算法，該算法同樣能夠得到的遺憾上界保障，但在計算存儲上更加高效，且理論分析也更加簡潔.

1.3 重尾噪聲

重尾噪聲是指噪聲服從一個具有有限1+ε階中心矩的無界分布.Liu 等人[30]首先考慮帶有重尾噪聲的賭博機問題.Bubeck 等人[31]和Vakili 等人[32]分別表明 ε ≥1的條件足以使帶有重尾噪聲的賭博機問題恢復到與亞高斯噪聲相同的遺憾界.因此，在帶有重尾噪聲的賭博機模型的研究中，大多數工作都集中在ε ∈(0，1]時的更為困難的情況.Hsu 等人[33]提出使用均值中位數估計器進行估計，其主要思想是統計多個采樣平均值的中位數以避免極端離群值的干擾.Audibert 等人[34]提出截斷策略，其思想是截斷超過給定閾值的異常值以過濾極端離群點.在文獻[33-34]的工作的基礎上，Medina 等人[35]首先解決了ε ∈(0，1]時的重尾線性賭博機問題，實現了的遺憾上界.這個結果后來被Shao 等人[36]改進，達到了近似最優的遺憾上界隨后，Xue 等人[37]將重尾噪聲的處理拓展到有限搖臂場景的隨機線性賭博機問題.

2 RM-LinUCB 算法

本節首先簡述問題設定和本文提出的RM-LinUCB算法框架，然后詳細介紹該算法中的3 個核心組件，即置信上界算法、均值中位數估計器和重啟策略.

2.1 問題設定

本文關注同時具有分布變化和重尾噪聲下的線性賭博機問題.在某個特定的時刻t，決策者根據上下文和歷史獎賞信息選擇一個搖臂，所選搖臂由其上下文信息xt∈Rd表示.決策者在某一輪通過搖臂xt所能獲得的獎賞是yt隨機線性賭博機的變體.

與標準模型式（1）不同的是，θt∈Rd是可能隨時間變化的回歸系數.我們假設回歸系數的可行集被限定為

除此之外，與Dani 等人[7]工作的不同之處在于，僅僅要求噪聲 ηt的1+ε階矩有限（即滿足重尾分布）：

其中c∈(0，+∞).Vakili 等人[32]已經證明，當ε ≥1時，噪聲分布的方差是有限的，因此與亞高斯噪聲的情況一樣具有相同的遺憾上界.因此，我們把重點放在ε ∈(0，1]的更困難的情況下.

分布變化使得流式數據不再滿足獨立同分布假設，這將使得重尾噪聲場景下的線性賭博機問題極端困難、難以分析，特別是難以通過統計方式對重尾分布進行處理.我們對于流式數據的要求進行了適當的放松：本文中只考慮批量大小為B的小批量流式數據.假設同一個批次內的回歸系數 θt保持不變，而θt將在不同批次之間發生變化，此假設在許多現實應用場景中都容易滿足，例如可互換的專家系統[38]和季節性推薦系統[39].

參照文獻[29]的研究，本文選擇動態遺憾界作為評價算法的性能指標，其定義為

即將算法所獲得的累計獎賞與一個能夠獲得回歸系數全部信息的每輪最優策略的累積獎賞進行比較.與之相比較的是靜態遺憾界，其將累計獎賞與動態遺憾界相比較.我們認為在開放動態環境中，將本文算法與可能變化的每輪最優策略作對比更為合理.

2.2 算法框架

本文所提出的算法框架如圖1 所示，我們首先將一個批量大小為B的數據分割為長度為k的N=個列.在第p列開始時，首先根據置信上界算法選擇一個搖臂xp，并在接下來的整個第p列，即t=(p-1)k,(p-1)k+1,(p-1)k+2,…,pk時，都選擇這個搖臂共k次，并觀察相應的獎賞.在第p列結束時，根據均值中位數估計器得到共k個估計θ?p，k，我們從中選擇一個系數 θ?p作為回歸系數的估計，并根據置信上界算法指導下一列，即第p+1列的搖臂選擇.隨著數據不斷到達，當不同批次之間的數據分布變化過大時，我們認為歷史數據對當前的學習任務已經沒有幫助，因此將重啟整個學習過程.

Fig.1 Illustration of RM-LinUCB algorithm.圖1 RM-LinUCB 算法示意圖

本文提出的RM-LinUCB 算法包含3 個組件：

1）均值中位數估計器（median-of-means estimator）解決數據分布存在重尾噪聲的問題；

2）置信上界（upper confidence bound）算法處理賭博機問題中探索與利用的均衡問題；

3）重啟策略（restart strategy）解決數據分布中存在的分布變化的問題.

2.3 均值中位數估計器

重尾噪聲帶來的主要困難體現在極端值的存在將使得數據整體沒有很好的統計特性.為了減少由此產生的估計誤差，基于Hsu 等人[33]和Shao 等人[36]的算法，我們使用均值中位數估計器來對回歸系數進行估計.根據假設，回歸系數在同批次內不變，算法以批次為基本單位來估計回歸系數.如圖1 所示，當某批次數據到達時，首先將該批次（共B輪）分為N=B/k列，每列含有k輪.在該批次的第p列開始時，算法首先選擇一個搖臂xp.隨后在第p列的所有k輪中，重復選擇相同的搖臂xp共k次，并獲得相應的獎賞反饋yp,1,yp,2,…,yp,k.在第p列的最后一輪決策之后，將得到k行、大小為p的歷史數據,i∈[p],j∈[k]，我們在圖1 中用不同線型的加粗框表示不同行的數據及其估計.對每行歷史數據，使用正則化最小二乘估計來估計回歸系數，其形式化為

其中λ ＞0為正則化系數.上述方程的閉式解為

其中rj是和其余估計定義在Vp上距離的中位數：

隨后，算法將根據置信上界算法選擇下一列所使用的搖臂xp+1并重復此估計過程.

2.4 置信上界

均值中位數估計器估計了第p列所得到的回歸系數 θ?p，在此基礎上構建每個搖臂的置信上界作為搖臂選擇的標準.根據面對不確定時樂觀選擇[8]的原則，選擇搖臂池中擁有最大置信上界的搖臂作為第p+1列的搖臂，其形式化為

RM-LinUCB 的偽代碼如算法1 所示：

算法1 中，βp為第p列的置信半徑，其計算公式為

算法1 遵循過程：在第p列開始前，算法首先根據式（8）選擇一個搖臂xp，然后在第p列的所有k輪中重復選擇這個搖臂并獲得相應的獎賞反饋；根據這些反饋，算法通過均值中位數估計器式（5）（6）對第p列的回歸系數進行估計；算法通過式（9）計算置信半徑以進行下一列，即第p+1列的搖臂選擇.

2.5 重啟策略（restart strategy）

為了處理模型在總共T輪上的分布變化，本文采用了帶有固定重啟參數H的重啟策略.算法首先將總共T輪決策劃分為T/Hk-1次重啟，表示每進行Hk輪決策后就重啟1 次.這意味著算法每隔H列就重啟1 次學習過程.為了更好地簡化所使用的重啟策略，引入了一個新的變量M=H/N，M表示一個重啟周期內的批次數，其中N=B/k是一個批次中的總列數.如果歷史數據的批次數達到M，則表示算法已經進行了至少Hk輪決策，此時分布變化可能已經過大，本文算法選擇重啟學習過程重新對分布進行估計.此外，Zhao 等人[29]證明了一個固定的H足以保證無悔的性質，本文算法將H設為固定的超參數.

3 理論保證

本節首先建立了在分布變化和重尾噪聲下的線性賭博機的遺憾下界，然后分析了所提出算法的遺憾上界，以驗證所提出算法是無悔的.

3.1 問題的遺憾下界

首先根據定理1 建立了問題的遺憾下界，它描述了問題的難度，因為在最差情況下沒有算法能比該理論極限做得更好.

定理1.對于任何T≥d，任何策略 π的遺憾都滿足遺憾下界：

3.2 算法的遺憾上界

下面的定理2 表明，RM-LinUCB 具有無悔的遺憾上界，即每輪平均遺憾隨時間T漸進收斂于0.

定理2.RM-LinUCB 在共T輪上的動態遺憾RT以至少1-δ的概率有

注1：將得到的遺憾上界與定理1 中的遺憾下界進行比較，可以看到它們存在一定的差距.然而，這個差距存在于所有處理分布變化的線性賭博機的算法中[25，28-29]，本文的算法保證了重尾噪聲不會讓這個遺憾上界變得更差.

注2：當ε=1時，即重尾噪聲退化到亞高斯噪聲時，本文的遺憾上界為這與具有分布變化和亞高斯噪聲的線性賭博機算法的遺憾上界[25,28-29]相同；當PT=0時，即沒有分布變化時，現在設定重啟系數H=T（即在分布變化不存在時不需要重啟），定理2 中的遺憾上界退化為這與Shao等人[36]的最優遺憾上界相匹配；當ε=1，PT=0時，即當噪聲服從亞高斯分布，且環境分布不發生變化時，上述遺憾上界為，這與隨機線性賭博機最優遺憾界相同[8].

證明.首先，在算法RM-LinUCB 中，以n表示算法自上次重啟以來的累計列數，而p表示批量數據的當前列數.由于以 θn表示第n列的真實回歸系數，首先分析均值中位數估計器的估計誤差.由式（2）（6）和柯西-施瓦茨不等式，可得

4 在線集成適應技術

第3 節分析了算法的遺憾上界.由定理2 可知，重啟參數H在RM-LinUCB 算法中起著重要作用.然而，為了得到最小的遺憾上界，H的最優設置需要提前知道路徑長度 PT的先驗信息，即算法要提前得知回歸系數 θt的累積變化，然而這在一些實際場景中是不可能的.本節針對該問題進一步提出了一種在線集成技巧以處理該問題.

我們注意到，在亞高斯噪聲下擁有分布變化的線性賭博機中也出現了需要先驗信息的問題.雙層賭博機（bandits-over-bandits）[25]算法能夠在一定程度上解決該問題.其主要思想是對H可能的最優取值進行多次猜測，并根據一定的概率選擇其中的一個作為算法的超參數H運行原算法.在1 次重啟后，算法可以根據收到的獎賞反饋對各個備選超參數進行其對應概率的調整，以便在重啟后以更高的概率選擇一個更好的超參數H.

具體來說，算法首先初始化參數：

其中K是備選參數的數量，J是備選參數H的集合，γ可視為更新系數，sj，i是與選臂概率有關的特殊參數，d，S分別是搖臂的維度和回歸系數的模長上界.若用pj，i表示第j個備選參數在第i次重啟后被選中的概率，算法首先通過式（14）計算pj，i：

隨后，算法以概率pj，i為第i次重啟選擇H=Hj，隨后用所選的參數H運行RM-LinUCB 算法，并在算法的下次重啟前收到累計獎賞反饋yi.確保雙層賭博機算法的一個非常重要的假設是，所獲得的獎賞是大概率有界的，這與重尾噪聲問題相矛盾.為了解決這個問題，將雙層賭博機和截斷策略[34]結合起來.具體來說，設置截斷閾值為Q=2H，這意味著如果重啟前的累計獎賞yi的絕對值超過Q就會被截斷到Q，這樣就可以得到有界的累計獎賞yi.最后算法通過式（15）更新參數.

我們將該在線集成技巧稱為RM-LinUCB-TBOB，其偽代碼由算法2 給出.

5 實 驗

本節分別在仿真數據和真實數據集上進行了實驗，以驗證所提出算法在處理數據不規范時的有效性.此外，還研究了在第4 節中提出的在線集成算法的有效性.

5.1 仿真數據

我們首先在仿真數據上進行了實驗，分別考慮了2 類分布變化環境和2 種重尾噪聲的共4 種情況.1）對比算法.本文將提出的RM-LinUCB 與Lin-UCB[3]，RestartUCB[29]，MENU[36]進行比較.LinUCB[3]是為有亞高斯噪聲的隨機線性賭博機而設計的.在此基礎上，RestartUCB[29]引入重啟策略以處理分布變化的情況，而MENU[36]引入均值中位數估計器以處理重尾噪聲.分布變化和重尾噪聲的先驗信息是已知的，即對于RestartUCB，根據分布變化的路徑長度設置其最優參數設置對于MENU，我們將重尾噪聲的參數化信息（ε，c）作為輸入直接運行.

2）全局設定.在所有實驗方案中，總輪數T=6000，搖臂的數量n=20.搖臂的特征從高斯分布N（0，1）中隨機采樣得到后按L=1進行歸一化.此外，設定δ=0.1，正則化參數λ=1，回歸系數最大模長S=1和特征維度d=2.最后的結果在100次獨立實驗上取平均數.

3）分布變化設定.按照Russac 等人[28]的實驗設置創建分布變化.具體而言，構建了2 類環境變化，稱為逐漸變化和突然變化.對于逐漸變化的環境，設定回歸系數 θt在t＜3000 時沿單位圓按逆時針方向從[1,0]變化到[-1,0]，然后在t≥3000時在[-1,0]處保持靜止；對于突然變化的環境，當t＜1000時，設置基本參數θt=[1,0]，然后當1000 ≤t＜2000時 θt轉移到[-1,0]，2000 ≤t＜3000時 θt轉移到[0, 1]，在最后的3000 輪中，θt保持在 [0, -1]的靜止狀態.此設定下的逐漸變化和突然變化對應的路徑長度 PT分別是3.14和5.41.

4）重尾噪聲設定.按照Shao 等人[36]的實驗設置，在獎賞產生時添加的隨機噪聲 ηt由學生t-分布產生，ηt的2 階中心矩的上界由自由度c所限制.具體來說，分別將標準學生t-分布的自由度設定為3和 10作為重尾噪聲的2 種類型，其中t-分布的自由度越大，對應的重尾分布越明顯.最后，將分布變化和重尾噪聲兩兩組合，構建了4 種數據不規范場景，分別以場景S1～S4 表示，4 種場景的具體參數見表1.

Table 1 Four Scenarios of Simulation Data表1 仿真數據的4 種場景

4 種算法的每輪平均遺憾如表2 所示，同時，在圖2 中展示了算法在場景S1～S4 的累積遺憾變化.在場景S3 和S4 中，當噪聲類似于亞高斯噪聲，即自由度c值較大時，RestartUCB 和RM-LinUCB 表現良好，而MENU 和UCB 則受到分布變化所帶來的影響較大.在場景S1 和S2 中，即當噪聲變得更加重尾時，RM-LinUCB 的結果更好，表明它在處理重尾噪聲時具有更好的穩健性.總的來說，相較于RestartUCB，由于均值中位數估計器能夠很好地處理重尾噪聲，RM-LinUCB 對重尾噪聲更加穩健.同時，相較于MENU，RM-LinUCB 對分布變化的穩健性更高.因此RM-LinUCB 在同時處理分布變化和重尾噪聲時相較于處理單一情況的算法具有更高的穩健性.

Fig.2 The cumulative regret on scenarios from S1 to S4圖2 S1～S4 場景下的累積遺憾

5.2 真實數據

現實數據集可能存在分布變化或重尾噪聲等數據不規范現象，且難以處理.在本節評估了本文的算法在處理真實世界數據集時的整體表現.從StatLib和UCI 機器學習資源庫[40]中選擇了 6個基準數據集，即bolts，cloud，kidney，forestfire，slumptest，pokerhand.此外，還對Last.fm，Delicious[41]，COMPAS[42]和30 天的Criteo 實時流量數據[43]這些規模較大的數據集進行了實驗.

1）數據預處理.在處理原始數據時，按照Cesa-Bianchi 等人[41]的預處理來構建搖臂的上下文特征向量.具體而言，將樣本的特征作為搖臂的上下文特征，然后通過PCA 降維后進行歸一化處理，使所有實例的特征向量滿足x2≤L=1.

2）構造賭博機問題.用預處理過的特征向量和它們的標簽構造賭博機問題：每個樣本數據都被視為一個可選搖臂，其標簽是其對應的獎賞.總共的時間跨度T=10000.在每一輪中，通過隨機選擇1 個非零標簽（獎賞）的樣本，然后隨機選擇其他24 個樣本來構建1 個可選搖臂池，這樣每個搖臂池都應至少包含1 個具有非零獎賞的搖臂.因此，對于所有的數據集，搖臂池的大小被固定為25.此外，與仿真數據實驗中相同，δ=0.1，λ=1，S=1.表3 中列出了數據集的特征維度（搖臂的上下文特征維度d）和樣本（搖臂）總數.

Table 3 Statistics of Real-world Datasets表3 真實數據集統計信息

3）對比算法.與之前的合成數據實驗不同，在處理真實世界的數據集時，故沒有任何關于重尾噪聲或分布變化的先驗信息，因此所有算法的參數都是通過網格搜索進行微調的.此外，因數據不規范對LinUCB 的影響較大，故省略了LinUCB 的結果.

4）實驗結果.我們參照Zhao 等人[27]的實驗設計，對RestartUCB，LinUCB 和RM-LinUCB 進行穩健性分析（robustness analysis）.首先給出賭博機算法 A的穩健性（robustness）的定義：

其中CP(A)是算法 A的平均累積獎賞.對于最佳算法，有r(A)=1，而其他算法則滿足r(A)＜1.算法的穩健性總和越高表示整體性越好.

如圖3 所示，RM-LinUCB 在10 個數據集上獲得的穩健性總和為9.94，在所有對比算法中獲得了最高的穩健性，從而驗證了其在處理具有數據不規范性的真實世界數據時的穩健性.此外，通過仔細觀察結果，可以得到更多有趣的結論.RM-LinUCB 和Restart-UCB 在bolt，cloud，forestfire 上的表現都優于MENU，這意味著在這些數據集上，MENU 受到了潛在的分布變化的影響.同時，RM-LinUCB 和MENU 在Last.fm和COMPAS 上的表現都優于RestartUCB，這意味著RestartUCB 收到了潛在的重尾噪聲的影響.最后，RMLinUCB 在pokerhand 上的表現遠遠優于RestartUCB和MENU，驗證了分布變化和重尾噪聲同時存在于該場景中.

Fig.3 Robustness analysis圖3 穩健性分析

5.3 在線集成適應技術

本文介紹了一種能夠在重尾噪音下有效適應未知環境變化程度的在線集成技術.本節將驗證所提出算法的有效性.

1）實驗設定.采用與仿真實驗情景S2 相似的環境，唯一的區別在于，總輪數T=10000，回歸系數 θt在單位圓上以1 000 輪為間隔隨機變化.

2）對比算法.將TBOB 與其他算法進行對比：

①當算法事先知道分布變化時間時，每當回歸系數變化，該算法都會重新啟動RM-LinUCB，我們稱之為Oracle；時，以最佳參數

②若提前得知關于路徑長度 PT和 ε的先驗知識運行RM-LinUCB，我們將該算法稱為Prior；

③當不知道關于路徑長度 PT的先驗知識時，從式（11）中隨機猜測參數H并運行RM-LinUCB，我們稱之為Guess.

3）實驗結果.如圖4 所示，各條曲線為對應的算法在100次獨立實驗上的平均遺憾.可以看到，所提出的TBOB 遠好于Guess；即使不需要關于路徑長度PT的先驗知識，TBOB 的表現依舊與Prior 非常接近，這證明了TBOB 在缺乏對數據不規范的先驗信息時仍能對環境有較強的穩健性.

Fig.4 Regret generated by TBOB圖4 TBOB 所產生的遺憾

6 結 語

本文研究了有分布變化的重尾線性賭博機問題，其中噪聲可能是重尾的，并且描述獎賞分布的回歸系數可能隨時間變化.針對該問題，我們首先建立了的遺憾下界以表征學習問題的難度.進而提出了一種新的基于置信上界的賭博機在線算法，其核心在于均值中位數估計器以應對重尾噪聲的干擾，使用自適應重啟策略以處理環境可能的分布變化.理論上，我們證明了該算法具有的遺憾上界，因而本文算法的每輪平均遺憾隨時間T增大漸進收斂至0.此外，我們進一步設計了在線集成算法來應對數據不規程度未知的場景，得到的新算法仍然能夠選擇較好的參數以保持穩健性.最后，我們在仿真數據和真實數據上進行了實驗，驗證了所提出的算法在應對潛在的分布變化和重尾噪聲時具有穩健性.

作者貢獻聲明：馬蘭霽弘負責論文相關文獻調研、算法設計、理論推導、實驗設計和論文撰寫；趙鵬負責對算法的分析方法提供指導和修正，并輔助修訂論文；周志華負責對論文的總體規劃進行設計，指導整體研究方向.