論文連接?https://arxiv.org/abs/1811.04383
本篇論文使用二分類算法，為在線場(chǎng)景(contextual bandits)探索了多臂賭博機(jī)(multi-armed bandits)的變種形式，主要涉及重復(fù)采樣(bootstrapping)和隨機(jī)算法。其中，自適應(yīng)貪心算法(Adaptive-Greedy algorithm)是作者認(rèn)為最好的一種方式。
對(duì)multi-armed bandits不了解的同學(xué)可以參考https://zhuanlan.zhihu.com/p/80261581，里面有很詳細(xì)的解釋。
一、問(wèn)題描述
對(duì)于K個(gè)賭博機(jī)（每個(gè)賭博機(jī)的收益均服從Bernoulli分布），在每輪開(kāi)始的時(shí)候，系統(tǒng)都會(huì)將一組協(xié)變量(covariates)xt作為先驗(yàn)知識(shí)告訴張三。經(jīng)過(guò)N+1輪后，張三需要根據(jù)先驗(yàn)知識(shí)[前N輪每輪的協(xié)變量、每輪的選項(xiàng)、每輪的收益]從賭博機(jī)中選擇一個(gè)收益最大的一個(gè)。
二、相關(guān)研究
對(duì)于多臂賭博機(jī)解決方案主要是upper confidence bounds 和?Thompson sampling。前者通過(guò)每個(gè)賭博機(jī)回報(bào)的最好預(yù)期進(jìn)行選擇，后者則通過(guò)Beta分布對(duì)每個(gè)賭博機(jī)的收益進(jìn)行模擬。此外還有類似以概率P選擇實(shí)際表現(xiàn)最優(yōu)的賭博機(jī)，以概率1-P隨機(jī)選擇的Epsilon-Greedy。在時(shí)間有限的情況下，還存在最初隨機(jī)進(jìn)行選擇，在最后選擇實(shí)際表現(xiàn)最好的Explore-Then-Exploit算法。LINUCB算法對(duì)于每個(gè)賭博機(jī)使用一個(gè)線性函數(shù)估計(jì)其期望收益的上限（詳見(jiàn)知乎專欄）
三、UCB算法
UCB算法的不足在于需要訪問(wèn)整個(gè)數(shù)據(jù)集。在線數(shù)據(jù)中，每次數(shù)據(jù)都是以流(stream)或者batch的形式存在。針對(duì)這個(gè)問(wèn)題，一種在實(shí)際中表現(xiàn)較好的方式，是先對(duì)每個(gè)樣本分配一個(gè)Gamma(1,1)的權(quán)重，再傳入分類器。另外，也可以采用決策樹(shù)或隨機(jī)森林對(duì)數(shù)據(jù)進(jìn)行擬合，則終端節(jié)點(diǎn)可認(rèn)為是數(shù)據(jù)的期望上界。
四、冷啟動(dòng)問(wèn)題
在線場(chǎng)景中另一個(gè)問(wèn)題在于相較于協(xié)方差（比如用戶點(diǎn)擊的次數(shù)）的大小，賭博機(jī)的回報(bào)率（比如用戶點(diǎn)入推薦商品）幾乎為零。通常，我們使用合并先驗(yàn)（incorporating a prior）或平滑的方式解決問(wèn)題。Rsmooth=(nR + a)/(n + b)。其中R是估計(jì)的回報(bào)率，a和b是平滑的常數(shù)。但如果賭博機(jī)數(shù)量提升的話,上述方案會(huì)使得每個(gè)賭博機(jī)直到都被采集相當(dāng)次數(shù)之前，都處于較低的回報(bào)率。另外一種方式使通過(guò)使用Beta先驗(yàn)并忽略協(xié)變量，直到對(duì)于每個(gè)標(biāo)簽取得一定的觀測(cè)數(shù)量后再重新使用協(xié)變量。
還有一種方式是通過(guò)在冷啟動(dòng)時(shí)，選取賭博機(jī)的一個(gè)子集，從中進(jìn)行隨機(jī)采樣。隨時(shí)間，逐步增加子集中賭博機(jī)的數(shù)量。但這種方法很難確定最優(yōu)的子集數(shù)量。
五、基線比較算法
一些常用的Bandit算法可參考上文提及的知乎專欄。較新穎的方法是采用SoftmaxExplorer。通過(guò)各賭博機(jī)所占的概率比例進(jìn)行選擇。fi(x)的輸出為0-1的概率值，因此先使用反Sigmoid轉(zhuǎn)化為實(shí)數(shù)值，通過(guò)softmax重新轉(zhuǎn)化為概率，從而避免輸出概率過(guò)小的問(wèn)題。為了讓該算法長(zhǎng)期收斂于最佳策略，每輪都會(huì)成以當(dāng)前論述值，從而放大賭博機(jī)收益之間的差距。
Epsilon-Greedy算法以一定概率1-p選擇當(dāng)前收益最大的賭博機(jī)，以概率p從任意賭博機(jī)中隨機(jī)選擇一個(gè)。隨著round的增加，隨機(jī)選擇的概率越來(lái)越低。
Epsilon-Greedy算法可以很容易改成啟發(fā)式的學(xué)習(xí)方法。例如在ActiveExplorer算法中使用神經(jīng)網(wǎng)絡(luò)替換uniform采樣。[上述算法可參考https://github.com/david-cortes/contextualbandits]
其中表現(xiàn)最好的算法是ContextualAdaptiveGreedy，這類算法運(yùn)行速度也較快。但需注意再結(jié)合啟發(fā)式算法的增強(qiáng)手段無(wú)法對(duì)此類算法有明顯提升。
