孔芳，楊悅?cè)?，陳衛(wèi)，李帥

1. 上海交通大學(xué)約翰·霍普克羅夫特計(jì)算機(jī)科學(xué)中心，上海 200240；2. 微軟亞洲研究院，北京 100080

1 引言

隨著數(shù)據(jù)時(shí)代的來臨，傳統(tǒng)離線學(xué)習(xí)方法已難以快速處理模型訓(xùn)練所需的爆發(fā)式增長的數(shù)據(jù)量及特征數(shù)量，這促進(jìn)了在線學(xué)習(xí)模式的發(fā)展。在線學(xué)習(xí)方法接收實(shí)時(shí)數(shù)據(jù)流，定義累積懊悔（cumulative regret）取代損失函數(shù)作為新的優(yōu)化函數(shù)，利用實(shí)時(shí)反饋不斷迭代調(diào)整算法，從而減少離線訓(xùn)練所需的數(shù)據(jù)量，并提高處理效率。在許多實(shí)際問題中，最優(yōu)解往往不是簡單的單個(gè)目標(biāo)，而是多個(gè)目標(biāo)的組合形式，這推進(jìn)了對組合在線學(xué)習(xí)問題的研究。組合在線學(xué)習(xí)問題，即組合多臂老虎機(jī)（combinatorial multi-armed bandits，CMAB）問題，結(jié)合了在線學(xué)習(xí)與組合優(yōu)化，研究如何在與環(huán)境交互的過程中自主學(xué)習(xí)未知參數(shù)，逐步找到最優(yōu)的目標(biāo)組合，其應(yīng)用包括社交網(wǎng)絡(luò)中的廣告投放、搜索、推薦等問題。

2 組合在線學(xué)習(xí)問題

2.1 多臂老虎機(jī)問題

多臂老虎機(jī)（multi-armed bandits）問題是一個(gè)經(jīng)典的機(jī)器學(xué)習(xí)問題，該問題最初由賭場的老虎機(jī)情景演變而來，被建模為玩家與環(huán)境之間的T輪在線游戲。老虎機(jī)共有m個(gè)臂（arm），m個(gè)臂的集合即玩家 的 動 作 集 合，記 為每個(gè)臂i∈[m]都有各自未知的獎勵分布，該分布的期望記作μi。玩家在每一輪游戲t∈[T]拉動其中一個(gè)臂，環(huán)境將從該臂的獎勵分布中采樣一個(gè)隨機(jī)變 量XAt,t，作為玩家拉動該臂的獎勵值。該獎勵值將幫助玩家更新對臂的獎勵分布的了解，進(jìn)而更新其后續(xù)選擇臂的策略。玩家的目標(biāo)是最大化T輪的累積期望收益，即最小化與最優(yōu)臂之間的累積期望收益的距離。令表示最高期望收益，則玩家的目標(biāo)為最小化累積期望懊悔：

其中，期望取自獎勵值產(chǎn)生的隨機(jī)性及玩家策略的隨機(jī)性。

有時(shí)，玩家在每一輪收到的反饋不僅僅是其本輪拉動臂的獎勵（即強(qiáng)盜反饋（bandit feedback）），還可能觀察到所有臂的輸出，該反饋類型被稱為全反饋（full feedback）。玩家收到的反饋信息可用一個(gè)反饋圖（feedback graph）來表示，圖中每個(gè)節(jié)點(diǎn)表示一個(gè)臂，每條有向邊(i,j)表示當(dāng)玩家拉動臂i時(shí)可觀察到臂j的輸出。全反饋類型的反饋圖可由完全圖表示，即每個(gè)節(jié)點(diǎn)有指向所有節(jié)點(diǎn)（包含自身）的邊；強(qiáng)盜反饋類型可用自環(huán)圖表示，即每個(gè)節(jié)點(diǎn)僅有指向自身的邊。反饋圖可進(jìn)一步泛化，用于表示更復(fù)雜的反饋關(guān)系[1-2]。除有向圖外，矩陣也可用于描述反饋關(guān)系。部分監(jiān)控（partial monitoring）[3]問題就使用反饋矩陣H來描述玩家可獲得的反饋信息，并使用損失矩陣L來刻畫玩家在游戲中的損失。若玩家在某一輪選擇臂i，環(huán)境本輪選擇臂i的輸出為j，則玩家將付出損失Li,j，并觀察到反饋Hi,j，通過設(shè)計(jì)不同的反饋矩陣，Hi,j可給出關(guān)于真實(shí)輸出j的部分或全部有效信息。

通過與環(huán)境的多輪交互，玩家將收集到對各個(gè)臂的獎勵分布的觀察。在接下來的游戲中，玩家一方面希望選取歷史觀察中表現(xiàn)最好的臂，以獲取相對較高的收益（開發(fā)（exploit））；另一方面希望嘗試一些尚未受到足夠觀察的臂，以獲取潛在較高的收益（探索（explore））。過度開發(fā)可能導(dǎo)致玩家錯(cuò)過最優(yōu)臂，過度探索則將導(dǎo)致玩家付出過多的學(xué)習(xí)代價(jià)，如何平衡開發(fā)與探索是多臂老虎機(jī)算法需要考慮的核心問題。

置信區(qū)間上界（upper confidence bound，UCB）[4]和湯姆森采樣（Thompson sampling，TS）[5]類型的算法是解決此類多臂老虎機(jī)問題的經(jīng)典方法。UCB類型的算法為每個(gè)臂i維持一個(gè)置信上界，該上界為過往觀察的經(jīng)驗(yàn)均值與置信半徑之和，置信半徑將隨著被觀察到的次數(shù)的增多而減小。當(dāng)一個(gè)臂被觀察到的次數(shù)足夠小時(shí)，置信半徑很大，促使置信上界足夠大，算法將傾向于選擇這些臂，這體現(xiàn)了探索的思想。當(dāng)臂被觀察到足夠多的次數(shù)時(shí)，置信半徑變小，置信上界的值趨近于經(jīng)驗(yàn)均值，進(jìn)而趨近于真實(shí)的期望值，算法將傾向于選擇經(jīng)驗(yàn)均值高的臂，這體現(xiàn)了開發(fā)的思想。TS類型的算法則為每個(gè)臂維持一個(gè)關(guān)于其獎勵值的先驗(yàn)分布，初始時(shí)算法對臂的收益尚未了解，該分布趨近于一個(gè)均勻分布，體現(xiàn)了探索的思想；隨著收集到的觀察的增多，該分布逐漸集中于經(jīng)驗(yàn)均值附近，方差變小，這體現(xiàn)了開發(fā)的思想。

上述策略均以最大化累積期望獎勵/最小化累積期望懊悔為目標(biāo)，然而考慮這樣的應(yīng)用場景，在疫情期間，醫(yī)學(xué)研究人員有多種藥物的配置方式及一些可供測試藥物效果的小鼠，研究人員希望在小鼠身上實(shí)驗(yàn)后為人類找到最有效的藥物配置方式，該目標(biāo)與小鼠本身的獎勵無關(guān)。這種問題被稱為純探索（pure exploration）問題，玩家有一定的預(yù)算輪數(shù)，在這段時(shí)間內(nèi)可以拉動不同的臂，并觀察其輸出，預(yù)算輪數(shù)終止后，需要給出最終的推薦，即拉動不同臂的概率分布。簡單懊悔（simple regret）是用來衡量解決此類問題策略的標(biāo)準(zhǔn)，其被定義為最優(yōu)臂的期望獎勵與最終推薦的期望獎勵之差[6]。當(dāng)玩家的最終目標(biāo)是經(jīng)過探索后識別出最優(yōu)的臂時(shí)，該問題被稱為最佳手臂識別（best arm identification）問題，是純探索問題的一種變體[7]。該問題也有兩種目標(biāo)，當(dāng)探索預(yù)算固定時(shí)，玩家需要最大化識別出最優(yōu)臂的概率[8]；當(dāng)返回最優(yōu)臂的概率固定時(shí)，玩家的目標(biāo)為最小化探索所需付出的代價(jià)[9]。

此外，在有些應(yīng)用場景中，玩家有額外的探索限制，如商家希望在每一輪廣告投放時(shí)，都能保證一定值的收益，即保守型探索（conservative exploration），服從保守型探索限制的問題被稱為保守型老虎機(jī)（conservative bandits）問題[10]。給定一個(gè)基準(zhǔn)臂A0，保守型探索限制玩家每一輪游戲t選 擇 的 臂At滿 足，其中α用于衡量玩家的保守程度，α越小，意味著玩家越保守。

在上述場景中，每個(gè)臂的獎勵值服從一個(gè)固定的概率分布，此時(shí)稱反饋類型為靜態(tài)反饋（stationary feedback）；當(dāng)每個(gè)臂獎勵值服從的概率分布隨時(shí)間發(fā)生變化時(shí)，稱反饋類型為非靜態(tài)反饋（nonstationary feedback）；當(dāng)每一輪的信息不在這一輪實(shí)時(shí)反饋給玩家，而是會有一定延遲的時(shí)候，稱此反饋為延遲反饋（delayed feedback）。此外，多臂老虎機(jī)問題還有許多豐富的變種。當(dāng)每個(gè)臂的獎勵值不再服從一個(gè)確定的概率分布，而是一系列的確定值時(shí)，該問題將變?yōu)閷估匣C(jī)（adversarial bandit）問題，Exp3算法[11]是解決此類多臂老虎機(jī)問題的經(jīng)典算法。若每個(gè)臂的期望收益與玩家所獲得的環(huán)境特征相關(guān)，則稱為情境式老虎機(jī)（contextual bandit）問題。在情境式老虎機(jī)問題中，若臂的期望收益是情境信息向量的線性加權(quán)形式，則稱為線性老虎機(jī)（linear bandit）問題，LinUCB算法[12]是解決此問題的經(jīng)典算法；若每一輪玩家拉動的不再是單獨(dú)的臂，而是多個(gè)臂的組合，則該問題變?yōu)榻M合多臂老虎機(jī)問題，即組合在線學(xué)習(xí)問題。

2.2 組合多臂老虎機(jī)問題

在許多應(yīng)用場景中，玩家拉動的不是單獨(dú)的一個(gè)臂，而是多個(gè)臂的組合。如出行推薦平臺需要向用戶推薦的通常是機(jī)票、酒店與景區(qū)門票的組合，這時(shí)便需要組合多臂老虎機(jī)的研究框架來解決。

Gai Y等人[13]最早將多用戶信道分配問題建模為一個(gè)組合多臂老虎機(jī)模型，在該模型中，每個(gè)臂包含多個(gè)組件的組合，拉動同一個(gè)臂的獎勵隨時(shí)間相互獨(dú)立，但是不同臂之間的獎勵會由于一些共享的部件而產(chǎn)生依賴關(guān)系。之后，該框架又被進(jìn)一步泛化，并被系統(tǒng)地闡釋[14-17]。

組合在線學(xué)習(xí)同樣被建模為玩家與環(huán)境之間的T輪在線游戲。該問題包含m個(gè)基礎(chǔ)臂（base arm），所有基礎(chǔ)臂組成的集合被記為。每 個(gè) 基 礎(chǔ)臂維持其各自的獎勵分布，獎勵的期望記為μi。第t輪基礎(chǔ)臂i的輸出記為Xi,t，為環(huán)境從該臂的獎勵分布中采樣出的隨機(jī)變量，且是相互獨(dú)立的。記所有基礎(chǔ)臂的獎勵期望為，所有基礎(chǔ) 臂在第t輪 的 輸出為玩家可選擇的動作是所有m個(gè)基礎(chǔ)臂可能的組合，稱之為超級臂（super arm），記S為動作集合，則。在每一輪中，玩家拉動超級臂，隨后獲取本輪的獎勵，并觀察環(huán)境的反饋信息。玩家收到的獎勵值將與拉動超級臂中包含的所有基礎(chǔ)臂的輸出相關(guān)。若該值為每個(gè)基礎(chǔ)臂的輸出（加權(quán)）之和，則稱獎勵為線性形式[17]。但在實(shí)際應(yīng)用場景中，拉動超級臂的獎勵形式可能更加復(fù)雜，如在推薦場景中用戶的點(diǎn)擊情況可能不直接線性依賴于平臺推薦的每一個(gè)項(xiàng)目的吸引力，此時(shí)獎勵被稱為非線性形式[14-16]。玩家收集到的反饋信息也將根據(jù)不同的應(yīng)用場景有所不同，可分為以下3類。

● 全信息反饋：該反饋類型假設(shè)玩家在拉動一個(gè)超級臂之后，能夠觀察到所有基礎(chǔ)臂的輸出，而與該基礎(chǔ)臂是否被包含在被拉動的超級臂中無關(guān)。這是一種非常理想化的設(shè)定，現(xiàn)實(shí)中往往難以遇到該場景。

● 半強(qiáng)盜反饋：全信息反饋的設(shè)定較為理想，現(xiàn)實(shí)中更常見的模式是玩家只能觀察到其選擇的超級臂包含的基礎(chǔ)臂的反饋信息，也就是半強(qiáng)盜反饋。例如，在搜索排序場景中，平臺可以獲取用戶對所列舉項(xiàng)目的滿意程度。

● 強(qiáng)盜反饋：該反饋類型假設(shè)玩家只能觀察到拉動超級臂所獲得的總的獎勵，而不能看到任何基礎(chǔ)臂的信息。以推薦場景為例，用戶的點(diǎn)擊意味著對所推薦商品組合的認(rèn)可，平臺往往無法獲知用戶對具體某個(gè)產(chǎn)品的滿意程度。

類似多臂老虎機(jī)問題，組合多臂老虎機(jī)的反饋類型也可分為靜態(tài)反饋、非靜態(tài)反饋、延遲反饋等。根據(jù)每一輪收集到的反饋信息，玩家將進(jìn)一步更新自己的策略。

受到一些應(yīng)用場景的啟發(fā)，玩家在拉動一個(gè)超級臂St∈S后，除St中包含的基礎(chǔ)臂外，更多的基礎(chǔ)臂可能會被St隨機(jī)觸發(fā)，對玩家最終的收益產(chǎn)生影響。該問題被建模為帶概率觸發(fā)臂的組合多臂老虎機(jī)（CMAB with probabilistically triggered arms，CMAB-T）模型[15,18]，得到了較多的關(guān)注。

注意到在情境式線性老虎機(jī)模型中，學(xué)習(xí)者在每一輪拉動一個(gè)由向量表示的動作，并收到與該動作向量線性相關(guān)的獎勵值，線性函數(shù)的參數(shù)即學(xué)習(xí)者需要學(xué)習(xí)的未知參數(shù)向量。故線性多臂老虎機(jī)模型也可被視為基于線性獎勵形式、強(qiáng)盜反饋類型的組合多臂老虎機(jī)問題。研究者通常通過采用為未知參數(shù)向量構(gòu)造置信橢球（confidence ellipsoid）的方法來解決此類問題[19-21]。

此外，多臂老虎機(jī)問題還可與組合數(shù)學(xué)中的擬陣結(jié)構(gòu)相結(jié)合，即擬陣?yán)匣C(jī)（matriod bandit）模型。該模型最早由Kveton B等人[22]提出，擬陣可由二元組表示，其中是由m個(gè)物品組成的集合，稱為基礎(chǔ)集（ground set）；I是由E的子集組成的集合，稱為獨(dú)立集（independent set），且需要滿足以下3點(diǎn)性質(zhì)：①?∈I；②I中每個(gè)元素的子集是獨(dú)立的；③增加屬性（augmentation property）。加權(quán)擬陣?yán)匣C(jī)假設(shè)擬陣會關(guān)聯(lián)一個(gè)權(quán)重向量，其中w(e)表示元素e∈E的權(quán)重，玩家每次拉動的動作A∈I的收益為。該問題假設(shè)擬陣是已知的，權(quán)重w(e)將隨機(jī)從某未知的分布P中采樣得到。對應(yīng)到組合多臂老虎機(jī)模型，E中的每個(gè)物品可被看作一個(gè)基礎(chǔ)臂，I中的每個(gè)元素可被看作一個(gè)超級臂。玩家的目標(biāo)是尋找最優(yōu)的超級臂，最小化T輪游戲拉動超級臂所獲期望收益與最優(yōu)期望收益之間的差，即累積期望懊悔值。

純探索問題在組合場景下也得到了進(jìn)一步的研究。Chen S等人[23]首先提出了多臂老虎機(jī)的組合純探索（combinatorial pure exploration of multi-armed bandits）問題。在該問題中，玩家在每一輪選擇一個(gè)基礎(chǔ)臂，并觀察到隨機(jī)獎勵，在探索階段結(jié)束后，推薦出其認(rèn)為擁有最高期望獎勵的超級臂，其中超級臂的期望獎勵為其包含基礎(chǔ)臂的期望獎勵之和。Gabillon V等人[24]在相同的模型下研究了具有更低學(xué)習(xí)復(fù)雜度的算法。由于允許玩家直接觀察到其選擇的基礎(chǔ)臂的輸出這一假設(shè)在實(shí)際應(yīng)用場景中過于理想化，上述模型隨后被進(jìn)一步泛化。Kuroki Y等人[25]研究了玩家在每一輪選擇一個(gè)超級臂并僅能觀察到該超級臂包含基礎(chǔ)臂隨機(jī)獎勵之和的情況，即全強(qiáng)盜線性反饋的組合純探索（combinatorial pure exploration with full-bandit linear feedback）問題，并提出了非自適應(yīng)性的算法來解決此問題。之后，Rejwan I等人[26]提出了自適應(yīng)性的組合相繼接受與拒絕（combinatorial successive accepts and rejects，CSAR）算法來解決此類問題中返回前K個(gè)最優(yōu)基礎(chǔ)臂的情況。Huang W R等人[27]泛化了線性獎勵形式，研究了具有連續(xù)和可分離獎勵函數(shù)的場景，并設(shè)計(jì)了自適應(yīng)的一致最佳置信區(qū)間（consistently optimal confidence interval，COCI）算法。Chen W等人[28]提出了一種新的泛化模型——帶有部分線性反饋的組合純探索（combinatorial pure exploration with partial linear feedback，CPE-PL）問題，涵蓋了上述全強(qiáng)盜線性反饋以及半強(qiáng)盜反饋、部分反饋、非線性獎勵形式等場景，并給出了解決此模型的首個(gè)多項(xiàng)式時(shí)間復(fù)雜度的算法。在實(shí)際應(yīng)用場景中，玩家可能無法觀察到某個(gè)臂的準(zhǔn)確反饋，而是多個(gè)臂之間的相對信息，即競爭老虎機(jī)（dueling bandit）模型。Chen W等人[29]研究了競爭老虎機(jī)的組合純探索（combinatorial pure exploration for dueling bandits）問題，并設(shè)計(jì)了算法解決不同最優(yōu)解定義的問題場景。

當(dāng)每個(gè)基礎(chǔ)臂的收益值不再服從特定的概率分布，而是一系列的確定值時(shí)，上述問題將變成對抗組合多臂老虎機(jī)（adversarial CMAB）問題，相關(guān)研究工作將在下一節(jié)中基于強(qiáng)盜反饋的CMAB算法部分一并介紹。

3 基于優(yōu)化反饋的組合在線學(xué)習(xí)算法

Gai Y 等人[17]最早考慮了組合多臂老虎機(jī)中獎勵形式為線性的情況，提出了線性獎勵學(xué)習(xí)（learning with linear reward，LLR）算法解決此問題，具體如下。

算法1：LLR算法

初始化：L為每個(gè)超級臂包含基礎(chǔ)臂的個(gè)數(shù)，t=0

Fori=1 tom

t=t+1

選擇有基礎(chǔ)臂i的超級臂

更新基礎(chǔ)臂i的獎勵估計(jì)以及基礎(chǔ)臂i被選擇的次數(shù)Ti,t

End for

While True do

t=t+1

對于 ?i∈Aa，更新基礎(chǔ)臂i的收益估計(jì)以及基礎(chǔ)臂i被選擇次數(shù)Ti,t

End while

L LR算法使用UCB的思想平衡開發(fā)與探索的關(guān)系。在該算法中，學(xué)習(xí)者每輪可選擇的超級臂中至多包含L個(gè)基礎(chǔ)臂，其中L為超參數(shù)。每個(gè)超級臂Aa被表示為所有基礎(chǔ)臂的加權(quán)組合，權(quán)重向量由m維的向量a表示，ai≥ 0表示基礎(chǔ)臂i在超級臂中的權(quán)重，Aa將包含所有滿足ai≠ 0的基礎(chǔ)臂i。超級臂的置信上界是其包含的基礎(chǔ)臂的置信上界的加權(quán)和，算法在每一輪選擇置信上界最大的超級臂。該算法框架有豐富的應(yīng)用場景，如尋找最大匹配、計(jì)算最短路徑及最小生成樹等。

隨后，Chen W等人[14-16]泛化了獎勵的形式，考慮到非線性形式的獎勵，且受到一些實(shí)際應(yīng)用場景（如影響力最大化等）的啟發(fā)，提出了帶概率觸發(fā)機(jī)制的組合多臂老虎機(jī)（CMAB with probabilistically triggered arms，CMAB-T）模型，并設(shè)計(jì)組合置信區(qū)間上界（combinatorial upper confidence bound，CUCB）算法來解決此類問題，具體如下。

算法2：CUCB算法

輸入：基礎(chǔ)臂集合[m]，離線神諭Oracle

While True do

執(zhí)行動作S，觀察到所有被觸發(fā)的基礎(chǔ)臂i，更新Ti和

End while

與LLR算法類似，CUCB算法同樣在每一輪為所有基礎(chǔ)臂計(jì)算其置信上界，不同之處在于選擇超級臂的方法不同。CUCB算法考慮了更多的應(yīng)用場景，定義了一個(gè)更廣泛的求解超級臂的方法。算法獲取一個(gè)離線神諭作為輸入，將根據(jù)輸入的每個(gè)基礎(chǔ)臂的置信上界，輸出該參數(shù)下最優(yōu)（或近似最優(yōu)）的超級臂，算法進(jìn)而執(zhí)行此超級臂，并觀察相應(yīng)的信息。由于許多非線性獎勵形式的離線組合優(yōu)化問題通常為NP難問題，該算法允許借助近似的離線神諭來幫助每一輪中超級臂的選取，且使用近似累積懊悔上界指標(biāo)來衡量算法的性能。

通過為具體的CMAB-T問題實(shí)例尋找合適的受觸發(fā)概率調(diào)制的有界平滑性條件（triggering probability modulated condition，TPM條件），CUCB算法可以達(dá)到的累積懊悔上界[15]，其中B為TPM條件的參數(shù)，K為所有超級臂中可隨機(jī)觸發(fā)的基礎(chǔ)臂的最大個(gè)數(shù)。TPM條件的具體內(nèi)容見條件1。

條件1（TPM條件）：若存在有界平滑常數(shù)，使得對于任意兩個(gè)基礎(chǔ)臂分布（期望分別記為μ和μ′），任意超級臂S，滿足，則稱該CMAB-T問題實(shí)例滿足1范數(shù)TPM條件。其中，為超級臂S成功觸發(fā)基礎(chǔ)臂i的概率。

概括來說，TPM條件通過所有基礎(chǔ)臂在不同環(huán)境中的期望獎勵之差的加權(quán)和約束了同一個(gè)超級臂在對應(yīng)獎勵分布下的獎勵差異，每個(gè)基礎(chǔ)臂的權(quán)重就是其在該超臂下被成功觸發(fā)進(jìn)而對超級臂獎勵產(chǎn)生影響的概率。尋找合適的TPM條件對于該類問題的理論分析有重要的作用，如在線影響力最大化、基于特定點(diǎn)擊模型的搜索排序問題等。

之后，Combes R等人[30]嘗試了與LLR和CUCB不同的計(jì)算置信上界的方法，自然推廣KL-UCB[31]中的指標(biāo)（index），利用KL散度來確定置信區(qū)間，并提出了ESCB（efficient sampling for combinatorial bandits）算法解決線性獎勵形式的CMAB問題。但由于超級臂數(shù)量隨著基礎(chǔ)臂數(shù)量的增加呈指數(shù)增長，該算法每一輪需要付出指數(shù)時(shí)間計(jì)算所有超級臂的置信上界。最近，Cuvelier T等人[32]提出了一個(gè)近似ESCB算法，算法能達(dá)到和ESCB一樣的累積懊悔上界，但實(shí)現(xiàn)了多項(xiàng)式時(shí)間復(fù)雜度O(Tpoly(m))。

此外，上述CMAB問題還可拓展至與情境相關(guān)的情況，即每輪玩家都會收到當(dāng)前的情境信息，每個(gè)基礎(chǔ)臂的期望獎勵值會與該情境信息相關(guān)，該問題被稱為情境式CMAB（contextual CMAB）問題，由Qin L J等人[33]最早提出。在該工作中，每個(gè)基礎(chǔ)臂i的期望獎勵值都會與此輪的情境信息線性相關(guān)，其中xt(i)是描述情境信息的向量， 是噪聲項(xiàng)，而超級臂的獎勵值與超級臂中包含的基礎(chǔ)臂的獎勵值有關(guān)，可以是簡單的加權(quán)和，也可以是非線性關(guān)系。參考文獻(xiàn)[33]針對這樣的問題框架提出了C2UCB算法，在UCB算法的基礎(chǔ)上，加入了對參數(shù)θ的擬合過程，達(dá)到了階的累積懊悔上界，其中d是情境信息向量的維數(shù)。Chen L X等人[34]推廣了上述框架，考慮了玩家可選的基礎(chǔ)臂集合會隨時(shí)間發(fā)生變化的情況，并提出了CC-MAB算法來解決此類問題。隨后Zuo J H等人[35]提出了另一種廣義情境式CMAB-T（context CMAB-T）的框架——C2MAB-T。該框架考慮了給定情境信息之后，玩家可選的動作會受到該情境信息的限制。具體來說，在每一輪環(huán)境會先提供一個(gè)可選超級臂集，而玩家這一輪可選擇的超級臂就被限制在該集合中，其選擇的超級臂會隨機(jī)觸發(fā)更多的基礎(chǔ)臂，玩家最終觀察到所有觸發(fā)臂的反饋。參考文獻(xiàn)[35]提出了C2-UCB、C2-OFU算法來解決此類問題，并證明了在近似離線神諭下，累積懊悔上界均為，其中m是基礎(chǔ)臂的數(shù)量，K是所有超級臂可觸發(fā)基礎(chǔ)臂的最大數(shù)量。

總體來說，上述研究工作均基于UCB類型的算法處理開發(fā)與平衡的關(guān)系。除此之外，也有一系列基于TS的方法解決CMAB問題。

Komiyama J等人[36]研究用TS算法解決組合多臂老虎機(jī)中超級臂的獎勵為所包含基礎(chǔ)臂的輸出之和且超級臂的大小固定為K的問題，提出了多動作湯姆森采樣（multiple-play Thompson sampling，MP-TS）算法。該工作考慮了基礎(chǔ)臂的輸出為伯努利隨機(jī)變量的場景，算法為每個(gè)基礎(chǔ) 臂維 持 一 個(gè)貝塔 分布在每一輪將為每個(gè)基礎(chǔ)臂i從其分布中采樣一個(gè)隨機(jī)變量θi，并對所有基礎(chǔ)臂根據(jù)該隨機(jī)變量從高到低排序，從中選擇前K個(gè)基礎(chǔ)臂組成本輪要選擇的超級臂，隨后根據(jù)這些基礎(chǔ)臂的輸出再次更新其對應(yīng)的貝塔分布。MP-TS算法達(dá)到了的累積懊悔上界，其中為任意非最優(yōu)基礎(chǔ)臂i與最優(yōu)臂K期望獎勵的KL距離，該懊悔值上界也與此類問題的最優(yōu)懊悔值相匹配。

之后，Wang S W等人[37]研究如何用TS算法解決廣義獎勵形式的組合多臂老虎機(jī)問題，提出了組合湯姆森采樣（combinatorial Thompson sampling, CTS）算法，具體見算法3。

算法3：CTS算法

While True do

t←t+1

對于每個(gè)基礎(chǔ)臂i，從貝塔分布隨機(jī) 采樣

計(jì)算S=Oracle(θ(t))

執(zhí)行動作S，得到觀察

End while

與CUCB算法相同，CTS算法同樣借助離線神諭產(chǎn)生給定參數(shù)下的最優(yōu)超級臂，但該算法要求能夠產(chǎn)生最優(yōu)解，不像CUCB算法那樣允許使用近似解。與MP-TS相比，CTS算法將基礎(chǔ)臂的輸出由伯努利類型的隨機(jī)變量放寬到[0,1]區(qū)間，且允許超級臂的獎勵是關(guān)于基礎(chǔ)臂輸出更為廣泛的形式，而不再是簡單的線性相加。當(dāng)超級臂的期望獎勵值與基礎(chǔ)臂的獎勵期望滿足利普希茨連續(xù)性條件（Lipschitz continuity）時(shí)，該工作給出了基于TS策略解決廣泛獎勵形式的CMAB問題的首個(gè)與具體問題相關(guān)的累積懊悔上 界，其 中K為所 有 超 級臂中包含基礎(chǔ)臂的最大個(gè)數(shù)，?min為最優(yōu)解和次優(yōu)解之間的最小差。該懊悔值上界也與基于同樣條件獲得的UCB類型的策略（CUCB算法）的理論分析相匹配[14]。當(dāng)獎勵形式滿足線性關(guān)系時(shí)，該算法的累積懊悔上界可被提升至[38]。

此外，Hüyük A等人[39-40]同樣基于確定的離線神諭Oracle，考慮到帶概率觸發(fā)的基礎(chǔ)臂，研究用CTS策略解決CMAB-T問題。當(dāng)超級臂的期望獎勵與基礎(chǔ)臂的獎勵期望滿足利普希茨連續(xù)性條件時(shí)，該工作證明CTS算法在該問題場景下可以達(dá)到的累積懊悔上界，其中pi為基礎(chǔ)臂i被所有超級臂隨機(jī)觸發(fā)的最小概率。該結(jié)果也與基于同樣條件的UCB類型的策略（CUCB算法）的理論分析相匹配[14]。

具體到擬陣?yán)匣C(jī)問題，Kveton B等人[22]充分挖掘擬陣結(jié)構(gòu)，提出了樂觀擬陣最大化（optimistic matriod maximization，OMM）算法來解決此問題。該算法利用UCB的思想，每輪選取最大置信上界的超級臂，并且通過反饋進(jìn)行參數(shù)更新，優(yōu)化目標(biāo)是令累積懊悔最小化。該文獻(xiàn)分別給出了OMM算法與具體問題相關(guān)的遺憾值上界和與具體問題無關(guān)的累積懊悔上界，其中K為最優(yōu)超級臂A*的大小，是非最優(yōu)基礎(chǔ)臂e和第Ke個(gè)最優(yōu)基礎(chǔ)臂的權(quán)重期望之差，Ke為滿足大于0的元素個(gè)數(shù)。通過分析，擬陣多臂老虎機(jī)問題可達(dá)到的累積懊悔值下界為，該結(jié)果也與OMM算法可達(dá)到的累積懊悔上界相匹配。Chen W等人[41]也給出了利用CTS算法解決擬陣多臂老虎機(jī)問題的理論分析，該算法的累積懊悔上界也可匹配擬陣多臂老虎機(jī)問題的累積懊悔下界。

當(dāng)每個(gè)臂的獎勵值服從的概率分布隨時(shí)間發(fā)生變化時(shí)，問題將變?yōu)榉庆o態(tài)組合多臂老虎機(jī)。Zhou H Z等人[42]最早研究了非靜態(tài)反饋的CMAB問題，并在問題設(shè)定中添加了限制——基礎(chǔ)臂的獎勵分布變化總次數(shù)S是。文中提出了基于廣義似然比檢驗(yàn)的CUCB（CUCB with generalized likelihood ratio test，GLR-CUCB）算法，在合適的參數(shù)下，若總基礎(chǔ)臂數(shù)量m已知，則累積懊悔上界為；若m未知，則累積懊悔上界為，其中 C1、 C2為與具 體問 題相關(guān)的常數(shù)。而后Chen W等人[43]推廣了設(shè)定，即忽略上述對S大小的假設(shè)，引入變量衡量概率分布變化的方差，在S或者V中存在一個(gè)已知時(shí)，提出了基于滑動窗口的CUCB（sliding window CUCB，CUCBSW）算法，其累積懊悔上界為或者；在S和V都未知時(shí)，提出了基于兩層嵌套老虎機(jī)的CUCB（CUCB with bandit-over-bandit，CUCB-BoB）算法，在特定情況下，該算法累積懊悔上界為T的次線性數(shù)量級。

此外，CMAB問題也可以拓展至保守探索模式。Zhang X J 等人[44]最早將Wu Y F等人[10]提出的保守型多臂老虎機(jī)問題衍生到CMAB問題框架中，即第t輪用戶選擇的超級臂的獎勵值μt和默認(rèn)超級臂的獎勵值μ0的關(guān)系服從限制，其中α用于 衡 量 用戶的保守程度，α越小意味著用戶越保守。該文獻(xiàn)基于UCB的思想提出了情境式組合保守UCB（contextual combinatorial conservative UCB，CCConUCB）算法，同時(shí)針對保守選擇的默認(rèn)超臂的獎勵值0μ是否已知，分別提出了具體算法。當(dāng)保守選擇的獎勵值已知時(shí)，算法的累積懊悔為，其 中d為基礎(chǔ)臂的特征維數(shù)，K為超級臂中最多能包含的基礎(chǔ)臂的數(shù)量。

上述CMAB研究工作均基于半強(qiáng)盜反饋，即超級臂中包含的（及觸發(fā)的）所有基礎(chǔ)臂的輸出都可以被玩家觀察到，也有部分工作研究了基于強(qiáng)盜反饋的CMAB算法。這類算法多考慮對抗組合多臂老虎機(jī)問題（adversarial CMAB），即每個(gè)基礎(chǔ)臂的輸出不再服從一個(gè)概率分布，而是一系列的確定值。Cersa-Bianchi N 等人[45]首先提出了COMBAND算法來解決此問題，該工作使用來體現(xiàn)組合關(guān)系，其中表示由基 礎(chǔ)臂組成的超級臂，當(dāng)P的最小特征值滿足一定條件時(shí)，算法可達(dá)到的累積懊悔上界。Bubeck S等人[46]提出了基于約翰探索的EXP2（EXP2 with John’s exploration）算法，該算法也可達(dá)到的累積懊悔上界。Combes R等人[30]考慮通過將KL散度投影到概率空間計(jì)算基礎(chǔ)臂權(quán)重的近似概率分布的方法來減少計(jì)算復(fù)雜度，提出了更有效的COMBEXP算法，該算法對于多數(shù)問題也可達(dá)到相同的累積懊悔上界。Sakaue S等人[47]進(jìn)一步考慮了更加復(fù)雜的超級臂集合的情況，設(shè)計(jì)了引入權(quán)重修改的COMBAND（COMBAND with weight modification，COMBWM）算法，該算法對于解決基于網(wǎng)絡(luò)結(jié)構(gòu)的對抗組合多臂老虎機(jī)問題尤其有效。

當(dāng)玩家需要拉動的動作為多個(gè)臂的組合時(shí)，其獲得的反饋也會隨實(shí)際應(yīng)用場景變得更加復(fù)雜，部分監(jiān)控問題在此場景下得到了進(jìn)一步的研究，即組合部分監(jiān)控（combinatorial partial monintoring）。Lin T等人[48]最早結(jié)合組合多臂老虎機(jī)與部分監(jiān)控問題，提出了組合部分監(jiān)控模型，以同時(shí)解決有限反饋信息、指數(shù)大的動作空間以及無限大的輸出空間的問題，并提出了全局置信上界（global confidence bound，GCB）算法來解決線性獎勵的場景，分別達(dá)到了與具體問題獨(dú)立的和與具體問題相關(guān)的的累積懊悔上界。GCB算法依賴于兩個(gè)分別的離線神諭，且其與具體問題相關(guān)的的累積懊悔 上界需要 保證問題最優(yōu)解的唯一性，Chaudhuri S等人[49]放寬了這些限制，提出了基于貪心開發(fā)的階段性探索（phased exploration with greedy exploitation，PEGE）算法來解決同樣的問題，達(dá)到了與具體問題獨(dú)立的和與具體問題相關(guān)的的累積懊悔上界。

在一些應(yīng)用場景中，如推薦系統(tǒng)等，隨著時(shí)間推移，系統(tǒng)將收集到越來越多的用戶私人信息，這引起了人們對數(shù)據(jù)隱私的關(guān)注，故CMAB算法還可以與差分隱私（differential privacy）相結(jié)合，用于消除實(shí)際應(yīng)用對數(shù)據(jù)隱私的依賴性。Chen X Y等人[50]研究了在差分隱私和局部差分隱私（local differential privacy）場景下帶半強(qiáng)盜反饋的組合多臂老虎機(jī)問題，該工作證明了當(dāng)具體CMAB問題的獎勵函數(shù)滿足某種有界平滑條件時(shí)，算法可以保護(hù)差分隱私，并給出了在兩種場景下的新算法及其累積懊悔上界。

4 應(yīng)用方面

組合多臂老虎機(jī)問題框架有非常豐富的實(shí)際應(yīng)用，本文著重介紹在線排序?qū)W習(xí)和在線影響力最大化兩類問題。

4.1 在線排序?qū)W習(xí)問題

排序?qū)W習(xí)問題主要研究如何根據(jù)目標(biāo)的特征對目標(biāo)進(jìn)行排序，是機(jī)器學(xué)習(xí)算法在信息檢索領(lǐng)域的一個(gè)應(yīng)用。該問題有一個(gè)目標(biāo)物品集L，學(xué)習(xí)者每次需要根據(jù)某種打分標(biāo)準(zhǔn)對整個(gè)目標(biāo)集進(jìn)行打分，并且將打分進(jìn)行排序，推薦出前K（通常L?K）個(gè)分?jǐn)?shù)最高的目標(biāo)物品。該問題有豐富的應(yīng)用場景，如搜索、推薦、廣告點(diǎn)擊等。

在許多真實(shí)的應(yīng)用場景中，如廣告推薦、搜索引擎排序等，總商品集的數(shù)量遠(yuǎn)遠(yuǎn)大于需要推薦的商品數(shù)量，使得離線排序?qū)W習(xí)模型所需訓(xùn)練數(shù)據(jù)巨大，學(xué)習(xí)任務(wù)更加艱巨，這推動了對在線排序?qū)W習(xí)（online learning to rank）的研究。在線排序?qū)W習(xí)問題不再需要大量的歷史數(shù)據(jù)來構(gòu)建排序模型，學(xué)習(xí)者將在與用戶的T輪交互過程中不斷更新對目標(biāo)物品的評估。由于學(xué)習(xí)者需要推薦多個(gè)目標(biāo)的組合，該問題屬于組合多臂老虎機(jī)的研究范疇，每個(gè)目標(biāo)物品對應(yīng)一個(gè)基礎(chǔ)臂，而推薦的物品組合對應(yīng)一個(gè)超級臂。

在線排序?qū)W習(xí)算法早期多由經(jīng)典的多臂老虎機(jī)問題算法改進(jìn)而來，例如Li L H等人[12]改進(jìn)了LinUCB（linear UCB）算法，考慮了項(xiàng)目的特征的加權(quán)組合，并通過計(jì)算置信上界來解決排序問題，Chen Y W等人[51]改進(jìn)了LinUCB算法，在探索時(shí)引入貪心算法，優(yōu)化了在線排序?qū)W習(xí)算法。

近年來，在線排序?qū)W習(xí)的研究工作多基于點(diǎn)擊模型。以商品推薦問題為例，商家考慮如何向用戶推薦商品，在與用戶的T輪交互過程中，學(xué)習(xí)商品的特征與用戶的喜好之間的關(guān)系，使用戶在輪推薦中盡可能多地點(diǎn)擊其推薦的商品。商家每次向用戶推薦的商品數(shù)量有限，推薦形式通常為列表。在每一輪推薦之后，商家可獲取用戶的點(diǎn)擊反饋，通常來說，若用戶點(diǎn)擊了其推薦的某個(gè)商品，則反饋為1，否則反饋為0。

上述點(diǎn)擊模型可分為3個(gè)部分：用戶是否瀏覽某個(gè)商品、商品對用戶的吸引程度以及用戶最終的點(diǎn)擊情況。用戶的瀏覽行為和商品對用戶的吸引力共同決定了用戶最終是否點(diǎn)擊。根據(jù)用戶的點(diǎn)擊行為，點(diǎn)擊模型可進(jìn)一步分為級聯(lián)模型（cascade model）、依賴點(diǎn)擊模型（dependent click model）、基于位置的模型（position-based model）等。

級聯(lián)模型假設(shè)用戶至多點(diǎn)擊一次被推薦的商品列表（大小為K），即用戶會從列表的第一個(gè)商品開始，依次向后瀏覽，一旦點(diǎn)擊某個(gè)商品，用戶將停止繼續(xù)瀏覽。Kveton B等人[52]首先提出了析取目標(biāo)（disjunctive objective）形式的級聯(lián)模型，即被推薦的商品列表中只要有一個(gè)“好”的商品，獎勵值為1，且考慮了所有可推薦的商品列表形成均勻擬陣的情況，并提出了CascadeKL-UCB算法解決該問題。該算法達(dá)到了的累積懊悔上界，其中Δ表示最優(yōu)點(diǎn)擊期望和次優(yōu)點(diǎn)擊期望之間的差的最小值。而后Kveton B等人[53]推廣了問題框架，提出了組合級聯(lián)模型，在該框架下推薦的商品列表只需滿足某些組合限制即可。該工作研究了合取目標(biāo)（conjunctive objective），即只有所有商品都是“好”商品時(shí)，獎勵值才為1。作者提出了CombCascade算法解決此問題，達(dá) 到了的累積懊悔上界，f*是最優(yōu)超級臂的收益。Li S等人[54]進(jìn)一步考慮了商品的情境信息（contextual information），并提出了C3-UCB算法，算法的累積懊悔上界為，d為刻畫情境信息的特征維數(shù)。

依賴點(diǎn)擊模型放寬了級聯(lián)模型對用戶點(diǎn)擊次數(shù)的限制，允許用戶在每次點(diǎn)擊之后仍以λ的概率選擇繼續(xù)瀏覽，即最終的點(diǎn)擊數(shù)量可以大于1。在λ=1時(shí)，Katariya S等人[55]基于此模型結(jié)合KL-UCB算法[31]設(shè)計(jì)了dcmKL-UCB算法，取得了的累積懊悔上界。Cao J Y等人[56]推廣了問題設(shè)定，考慮了λ不一定為1的情況，并且考慮了用戶疲勞的情況（即用戶瀏覽越多，商品對用戶的吸引能力越弱），在疲勞折損因子已知的情況下提出了FA-DCM-P算法，算法的累積懊悔上界是；若疲勞折損因子未知，作者提出了FA-DCM算法，算法累積懊悔上界為

相較于前兩個(gè)點(diǎn)擊模型，基于位置的模型考慮了用戶對不同位置商品的瀏覽概率的變化，即用戶對商品的瀏覽概率將隨著該商品在推薦列表中順序的后移而逐漸變小。Li C等人[57]基于冒泡排序算法的思想設(shè)計(jì)了BubbleRank算法，該算法可同時(shí)適用于級聯(lián)模型和基于位置的模型。Zoghi M等人[58]引入了KL標(biāo)度引理，設(shè)計(jì)了BatchRank算法。該算法也可同時(shí)應(yīng)用于級聯(lián)模型和基于位置的模型。

Zhu Z A等人[59]不再考慮某特定的模型假設(shè)，而是根據(jù)實(shí)際推薦點(diǎn)擊場景提出了更通用的廣義點(diǎn)擊模型，上述3種模型均可涵蓋在內(nèi)。廣義點(diǎn)擊模型假設(shè)用戶瀏覽每個(gè)商品的概率隨著商品在推薦列表中位置的后移而減小。用戶點(diǎn)擊某商品的概率與該商品的吸引力相關(guān)，且用戶繼續(xù)往后瀏覽的概率與其對當(dāng)前商品的點(diǎn)擊與否相關(guān)。用戶對商品列表整體的瀏覽及點(diǎn)擊情況可由如圖1所示的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)來闡釋。圖1中Ai表示用戶點(diǎn)擊第i個(gè)商品后繼續(xù)向下瀏覽，Bi表示用戶沒有點(diǎn)擊第i個(gè)商品并繼續(xù)向下瀏覽，Ei表示用戶瀏覽第i個(gè)商品，Ci表示用戶點(diǎn)擊第i個(gè)商品，Ri表示第i個(gè)商品的相關(guān)程度/吸引力，即用戶的瀏覽行為與商品的吸引力共同決定了用戶對該商品的點(diǎn)擊行為，而用戶瀏覽第i+1個(gè)商品的可能性與用戶對第i個(gè)商品采取行為的概率分布相關(guān)。

圖1 廣義點(diǎn)擊模型的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)

針對上述廣義模型，Li S等人[60]考慮到廣義模型中每次反饋可能有噪聲影響，且假設(shè)點(diǎn)擊概率和瀏覽每個(gè)商品的概率獨(dú)立，同時(shí)與每個(gè)商品的吸引力也獨(dú)立，提出了RecurRank算法。該算法利用遞歸的思想，考慮將排序分為若干階段，每個(gè)階段都采用分段排序，下一個(gè)階段再對已經(jīng)分得的段繼續(xù)分段排序，直至最后排序完成，算法的懊悔上界為，其中d為商品的特征維數(shù)；Lattimore T等人[61]基于BatchRank的結(jié)果提出了TopRank算法，該算法學(xué)習(xí)商品之間吸引力大小的相對關(guān)系，從而完成排序任務(wù)。相比于BatchRank，該算法應(yīng)用更加廣泛，計(jì)算更加簡便且懊悔上界更小。

此外，線性次模多臂老虎機(jī)（linear submodular MAB）模型是應(yīng)用于在線排序?qū)W習(xí)領(lǐng)域的另一經(jīng)典 老虎機(jī)模型。該模型最早由Yue Y S等人[62]提出，將次模信息覆蓋模型引入組合多臂老虎機(jī)框架，并應(yīng)用于排序?qū)W習(xí)領(lǐng)域。次模信息覆蓋模型假設(shè)信息的邊際效益遞減。該模型假設(shè)任意商品a都可被d個(gè)基本 覆蓋函數(shù)F1,…,Fd表示，其中基本 覆 蓋函數(shù)F1,… ,Fd表 示此文檔對d個(gè)特征的覆蓋率，且為已知的滿足次模性質(zhì)的函數(shù)。同理，每個(gè)商品對應(yīng)組合多臂老虎機(jī)模型的基礎(chǔ)臂，需要推薦的有序商品組合為超級臂，超級臂的覆蓋函數(shù)是基礎(chǔ)臂覆蓋函數(shù)的加權(quán)和。Yue Y S等人[62]提出了LSBGreedy算法來解決此問題，并證明其累積懊悔上界為其中L是超級臂中包含的基礎(chǔ)臂的數(shù)量，S是與權(quán)衡期望收益和噪聲的參數(shù)相關(guān)的常數(shù)。然而問題原始定義是將所有商品都進(jìn)行排序輸出，即最終得到的超級臂是，這并不符合多數(shù)排序?qū)W習(xí)問題的實(shí)際情況，此后Yu B S 等人[63]引入了背包限制（即每個(gè)文檔有成本函數(shù)，需要考慮推薦的文檔的成本總和不能超過某個(gè)限制值），并提出了兩種貪心算法（MCSGreedy和CGreedy）來求解此類問題。Chen L等人[64]把原始線性次模問題推廣到無限維，考慮了邊際收益函數(shù)是屬于再生核希爾伯特空間的具有有限模的元素，并提出了SM-UCB算法。Takemori S等人[65]考慮了雙重限制下的次模多臂老虎機(jī)問題，即背包限制以及k-系統(tǒng)限制，沿用改進(jìn)UCB的思想，提出了AFSM-UCB算法，相比于LSBGreedy[62]和CGreedy[63]，該算法在實(shí)際應(yīng)用效率方面有一定程度的提升。

4.2 在線影響力最大化

在線影響力最大化（online influence maximization，OIM）問題研究在社交網(wǎng)絡(luò)中影響概率未知的情況下，如何選取一組種子節(jié)點(diǎn)集合（用戶集合），使得其最終影響的用戶數(shù)量最大[66]。該問題有豐富的應(yīng)用場景，如病毒營銷、推薦系統(tǒng)等。由于學(xué)習(xí)者選擇的動作是多個(gè)節(jié)點(diǎn)的組合，動作的數(shù)量會隨著網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)的增長出現(xiàn)組合爆炸的問題，故在線影響力最大化也屬于組合在線學(xué)習(xí)的研究范疇。

獨(dú)立級聯(lián)（independent cascade，IC）模型與線性閾值（linear threshold，LT）模型是描述信息在社交網(wǎng)絡(luò)中傳播的兩個(gè)主流模型[67]。在IC模型中，信息在每條邊上的傳播被假設(shè)為相互獨(dú)立，當(dāng)某一時(shí)刻節(jié)點(diǎn)被成功激活時(shí)，它會嘗試激活所有的出鄰居v一次，激活成功的概率即邊的權(quán)重，該激活嘗試與其他所有的激活嘗試都是相互獨(dú)立的。LT模型拋棄了IC模型所有傳播相互獨(dú)立的假設(shè)，考慮了社交網(wǎng)絡(luò)中常見的從眾行為。在LT模型中，每個(gè)節(jié)點(diǎn)v會關(guān)聯(lián)一個(gè)閾值θv表示該節(jié)點(diǎn)受影響的傾向，當(dāng)來自活躍入鄰居的權(quán)重之和超過θv時(shí)，節(jié)點(diǎn)v將被激活。已有的在線影響力最大化工作主要專注于IC模型和LT模型。

Chen W等人[14-15]首先將IC模型下的在線影響力最大化問題建模為帶觸發(fā)機(jī)制的組合多臂老虎機(jī)問題（CMAB with probabilistically triggered arms，CMAB-T）。在該模型中，社交網(wǎng)絡(luò)中的每條邊被視為一個(gè)基礎(chǔ)臂，每次選擇的種子節(jié)點(diǎn)集合為學(xué)習(xí)者選擇的動作，種子節(jié)點(diǎn)集合的全部出邊的集合被視為超級臂?；A(chǔ)臂的獎勵的期望即該邊的權(quán)重。隨著信息在網(wǎng)絡(luò)中的傳播，越來越多的邊被隨機(jī)觸發(fā)，其上的權(quán)重也可以被觀察到?；诖四Ｐ?，CUCB算法[14-15]即可被用于解決該問題。通過證得IC模型上的在線影響力最大化問題滿足受觸發(fā)概率調(diào)制的有界平滑性條件（triggering probability modulated condition），CUCB算法可以達(dá)到的累積懊悔上界，其中n、m分別表示網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)量[15]。

后續(xù)又有一些研究者對此工作進(jìn)行了改進(jìn)。Wen Z等人[68]考慮到社交網(wǎng)絡(luò)中龐大的邊的數(shù)量可能會導(dǎo)致學(xué)習(xí)效率變低，引入了線性泛化的結(jié)構(gòu)，提出了IMLinUCB算法，該算法適用于大型的社交網(wǎng)絡(luò)。該算法能達(dá)到的累積懊悔上界，其中d為引入線性泛化后特征的維數(shù)。Wu Q Y等人[69]考慮到網(wǎng)絡(luò)分類的性質(zhì)，將每條邊的概率分解為起點(diǎn)的影響因子和終點(diǎn)的接收因子，通過此分解，問題的復(fù)雜度大大降低。該文獻(xiàn)中提出的IMFB算法可以達(dá)到的累積懊悔上界。

上述研究工作均基于半強(qiáng)盜反饋，即只有被觸發(fā)的基礎(chǔ)臂的輸出可以被學(xué)習(xí)者觀察到。具體到在線影響力最大化問題，該反饋也被稱為邊層面的反饋，即所有活躍節(jié)點(diǎn)的每條出邊的權(quán)重均可以被觀察到。由于在實(shí)際應(yīng)用場景中，公司往往無法獲知具體哪個(gè)鄰居影響到某用戶購買商品，故該反饋是一種較為理想化的情況。節(jié)點(diǎn)層面的反饋是在線影響力最大化問題的另一種反饋模型，該反饋模型僅允許學(xué)習(xí)者觀察到每個(gè)節(jié)點(diǎn)的激活狀態(tài)。Vaswani S等人[70]研究了IC模型下節(jié)點(diǎn)層面反饋的情況，該工作分析了利用節(jié)點(diǎn)層面反饋估計(jì)每條邊的權(quán)重與直接利用邊層面反饋得到的估計(jì)值的差異，盡管兩種估計(jì)的差值可以被約束，但該工作并沒有給出對算法累積懊悔值的理論分析。

LT模型考慮了信息傳播中的相關(guān)性，這給在線影響力最大化問題的理論分析帶來了更大的挑戰(zhàn)。直到2020年，Li S等人[71]研究了LT模型下的在線影響力最大化問題，并給出了首個(gè)理論分析結(jié)果。該工作假設(shè)節(jié)點(diǎn)層面的反饋信息，即傳播過程每一步中每個(gè)節(jié)點(diǎn)的激活情況可以被觀察到，并基于此設(shè)計(jì)了LT-LinUCB算 法，該 算 法 可 以 達(dá) 到的累積懊悔上界。此外，Li S等人還提出了OIM-ETC（OIM-explore then commit）算法，該算法可以同時(shí)解決IC模型和LT模型下的在線影響力最大化問題，達(dá)到了的累積懊悔上界。Vaswani S等人[72]還考慮了一種新的反饋類型，即信息在任意兩點(diǎn)間的可達(dá)情況，并基于此反饋信息設(shè)計(jì)了DILinUCB（diffusionindependent LinUCB）算法。該算法同時(shí)適用于IC模型和LT模型，但其替換后的近似目標(biāo)函數(shù)并不能保證嚴(yán)格的理論結(jié)果。

5 未來研究方向

組合在線學(xué)習(xí)問題仍有很多方面可以進(jìn)一步研究和探索，具體如下。

● 設(shè)計(jì)適用于具體應(yīng)用場景的有效算法。以在線影響力最大化問題為例，目前的研究工作多為通用的算法，基于TPM條件得到算法的累積懊悔上界。但實(shí)際應(yīng)用場景中通常涉及更多值得關(guān)注的細(xì)節(jié)，如在線學(xué)習(xí)排序問題中用戶的點(diǎn)擊習(xí)慣、用戶疲勞等現(xiàn)象，在線影響力最大化問題中信息傳播的規(guī)律等。通用的算法往往難以全面考慮這些細(xì)節(jié)從而貼合具體的問題場景，因此針對具體問題場景設(shè)計(jì)出有效的算法，以及為這些問題證明其累積懊悔下界等仍然是值得研究的問題。

● 將組合在線學(xué)習(xí)與強(qiáng)化學(xué)習(xí)結(jié)合。MAB問題是強(qiáng)化學(xué)習(xí)的一種特例，CMAB是組合優(yōu)化與MAB的結(jié)合，更進(jìn)一步的問題是能否將這種結(jié)合推廣到廣義的強(qiáng)化學(xué)習(xí)領(lǐng)域，探索更廣泛通用的組合在線學(xué)習(xí)框架，以涵蓋更多的真實(shí)應(yīng)用場景。

● 研究具有延遲反饋和批處理反饋的組合在線學(xué)習(xí)算法。實(shí)際應(yīng)用場景中往往有更復(fù)雜的反饋情況，如在線排序?qū)W習(xí)問題中用戶可能沒有立即對感興趣的項(xiàng)目進(jìn)行訪問，導(dǎo)致玩家行動與反饋之間有一定的時(shí)間差，即延遲反饋；有時(shí)廣告供應(yīng)商每隔一段時(shí)間才集中收集一次數(shù)據(jù)，即批處理反饋。在MAB問題中，針對這兩種反饋方式的算法研究已取得一定的進(jìn)展，在CMAB問題中，考慮這些復(fù)雜反饋形式的算法仍需繼續(xù)探索。

● 深入研究分布式CMAB（distributed CMAB）。考慮多個(gè)玩家同時(shí)以相同目標(biāo)選擇超級臂的場景，玩家之間可以進(jìn)行交流，但是每一輪每個(gè)玩家能共享的信息有限，玩家最終根據(jù)自己觀察到的信息做出選擇，并得到對應(yīng)的獨(dú)立的獎勵值，最終每個(gè)玩家都會選擇自己認(rèn)為最優(yōu)的超級臂。分布式探索的方法在MAB問題中已經(jīng)有所應(yīng)用和突破，但在CMAB場景中仍然需要更多的深入研究。

● 尋找更多的實(shí)際應(yīng)用場景，以及在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。已有算法可應(yīng)用的數(shù)據(jù)集仍然有限，目前的研究工作多在人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，如何將算法應(yīng)用到更多的真實(shí)數(shù)據(jù)集中并解決更多的實(shí)際問題，是具有重要實(shí)際意義的研究方向。

6 結(jié)束語

本文首先介紹了組合在線學(xué)習(xí)問題的定義及其基本框架——組合多臂老虎機(jī)問題，而后概括了此框架下的組合在線學(xué)習(xí)模型及經(jīng)典算法。該問題有豐富的應(yīng)用場景，本文重點(diǎn)介紹了在線排序?qū)W習(xí)和在線影響力最大化，詳述了這兩個(gè)應(yīng)用場景下的研究進(jìn)展。組合在線學(xué)習(xí)仍有許多值得深入探索的問題，本文最后對其未來研究方向做了進(jìn)一步展望。