前言：

      來萬物花開這家創(chuàng)業(yè)公司實(shí)習(xí)，也真是一波三折。先實(shí)習(xí)了三天，每天下午到公司工作到晚上。工作時(shí)間是每天下午到晚上9.30。結(jié)果每天上午沒法用心干實(shí)驗(yàn)室的活了，下午在公司工作的時(shí)候，總是提心吊膽，手機(jī)震動(dòng)一下就會(huì)立刻拿出來看看是不是老師找我了。這樣的日子感覺沒法持續(xù)下去，想找導(dǎo)師談?wù)勚?，就從?shí)驗(yàn)室同學(xué)那兒知道了老師對(duì)我最近的出勤率太低很不高興。想著還是找找導(dǎo)師談一談實(shí)習(xí)的問題吧，然后還在猶豫的時(shí)候，大boss就找我談話了，退學(xué)or干活。于是只能拒絕了實(shí)習(xí)，安心回實(shí)驗(yàn)室吧。

意外的是，創(chuàng)業(yè)公司帶我的老大陳開江師兄念在是北理工的同門師兄弟上，加上我對(duì)于轉(zhuǎn)互聯(lián)網(wǎng)方向的決心強(qiáng)烈，決定給我一個(gè)機(jī)會(huì)，每周一到周五晚上干活，周末拿一天時(shí)間出來交流，就算我實(shí)習(xí)三天了。只能說太感謝陳開江師兄了，讓我在這么惡劣的條件下還給我實(shí)習(xí)的機(jī)會(huì)。

我的github：

我實(shí)現(xiàn)的代碼全部貼在我的github中，歡迎大家去參觀。

在作為算法實(shí)習(xí)生時(shí)，所實(shí)現(xiàn)的代碼產(chǎn)權(quán)應(yīng)該屬于公司，所以在github中公布的代碼可能會(huì)缺少一部分，或者比較簡(jiǎn)單，不涉及業(yè)務(wù)。

https://github.com/YinWenAtBIT

算法介紹：

背景介紹：

一、問題模型：

Multi-armed bandit問題，中文譯名或叫做“多臂賭博機(jī)”問題。

在概率論中，多臂賭博機(jī)問題（有時(shí)也稱為K臂/N臂賭博機(jī)問題），是一個(gè)賭徒需要在一排***前決定拉動(dòng)哪一個(gè)***的臂，并且決定每個(gè)臂需要被拉動(dòng)多少次的問題。每臺(tái)***提供的獎(jiǎng)勵(lì)是與它自身的獎(jiǎng)勵(lì)隨機(jī)分布的函數(shù)相關(guān)的。賭徒的目標(biāo)是最大限度地通過杠桿拉動(dòng)序列，使得獲得的獎(jiǎng)勵(lì)最大化。

在實(shí)際應(yīng)用中，多臂模型被用來模擬管理研究項(xiàng)目，比如一家制藥公司，要給定一個(gè)的預(yù)算，問題是在各個(gè)項(xiàng)目中分配資源，項(xiàng)目的回報(bào)暫時(shí)只知道一部分，需要在項(xiàng)目進(jìn)行的過程中才會(huì)知道的越來越清楚。

因此，在解決這個(gè)問題的時(shí)候，需要在“exploration”（探索新臂以獲得跟多關(guān)于臂的回報(bào)的信息）和“exploitation”（選擇已有回報(bào)最高的臂來獲取最大利益）之中進(jìn)行權(quán)衡。

數(shù)學(xué)模型：

多個(gè)臂的回報(bào)可以看做是一組真實(shí)的隨機(jī)分布，，K代表臂桿。代表每個(gè)臂的平均回報(bào)，賭徒每一輪拉下一個(gè)臂，并得到一次回報(bào)，是剩余可玩的輪數(shù)。多臂問題等同于一個(gè)狀態(tài)的馬爾科夫問題。輪之后的后悔度為，可用如下公式表示：，其中是最大回報(bào)的平均數(shù)，，是在t時(shí)獲得的回報(bào)。

一個(gè)零后悔度的策略會(huì)使得在無限次選擇臂桿后以概率1趨近與0。那么，零后悔策略將在玩了足夠多次之后趨近與最優(yōu)策略。

UCB1算法：

UCB – The Upper Confidence BoundAlgorithm，上置信算法

小量貪婪算法和SOFTMAX算法缺陷：

前面所提及的算法（《Bandit Algorithms for Website Optimization》一書的前幾章所介紹的算法，這里我直接拿它總結(jié)的結(jié)果使用）有一個(gè)弱點(diǎn)，它們只關(guān)心回報(bào)是多少，并不關(guān)心每個(gè)臂被拉下了多少次，這就意味著，這些算法不再會(huì)選中初始回報(bào)特別低臂，即使這個(gè)臂的回報(bào)只測(cè)試了一次。使用UCB1算法，將會(huì)不僅僅關(guān)注于回報(bào)，同樣會(huì)關(guān)注每個(gè)臂被探索的次數(shù)。

在介紹UCB1算法之前，先總結(jié)一下前幾章的介紹的epsilon-Greedy and Softmax algorithms（小量貪婪算法和SOFTMAX算法）的特點(diǎn)：

1.默認(rèn)選擇當(dāng)前已知的回報(bào)率最高的臂桿

2.偶爾選擇那些沒有最高回報(bào)的臂桿

——小量貪婪算法隨機(jī)選擇，這樣其他每個(gè)臂被選中的概率很??；

——SOFTMAX算法根據(jù)回報(bào)率選擇臂桿，回報(bào)率比最大值小很多的臂桿很少選中，回報(bào)率接近最大值的筆桿被選中的概率接近最大臂被選中的概率

為了讓這兩種算法表現(xiàn)更好，我們可以在運(yùn)行過程中動(dòng)態(tài)的修改它們的參數(shù)，這種方式叫做退火算法。

我們需要知道每個(gè)臂的回報(bào)的置信度是因?yàn)?，我們得到的每一個(gè)臂的回報(bào)結(jié)果是隨機(jī)的，其中含有噪聲。臂A看起來似乎比臂B選擇要好，只有我們得到了足夠多的數(shù)據(jù)，這時(shí)我們才能確認(rèn)臂A優(yōu)于臂B。

其他兩種算法是容易被誤導(dǎo)的，初始遇上了一次隨機(jī)壞的結(jié)果，會(huì)把這個(gè)結(jié)果當(dāng)做這個(gè)臂的回報(bào)。UCB算法不會(huì)受到臂回報(bào)隨機(jī)性的影響。

因此，在實(shí)現(xiàn)UCB算法時(shí)，我們需要記錄下對(duì)每個(gè)臂回報(bào)的置信度，做法是記錄下每個(gè)臂被選擇了多少次。

UCB1算法特性：

在實(shí)現(xiàn)UCB算法的時(shí)候，我們不需要關(guān)心其他的假設(shè)條件，只要滿足一個(gè)條件：回報(bào)是分布在0-1之間，1代表最大的回報(bào)。如果使用的模型最大回報(bào)結(jié)果超出了這個(gè)范圍，需要對(duì)結(jié)果進(jìn)行歸一化。

除了保存每個(gè)臂結(jié)果的置信度以外，UCB算法還在以下兩個(gè)點(diǎn)不同與之前的算法：

1. UCB完全不使用隨機(jī)性，每一種情況下，UCB選擇的臂都是可以通過數(shù)據(jù)計(jì)算出來的

2. UCB算法沒有任何需要配置的參數(shù)，這意味著，在任何情況下你都可以使用UCB算法，沒有任何需要的先驗(yàn)條件

UCB算法實(shí)現(xiàn)：

每個(gè)臂包含的數(shù)據(jù)：

選擇臂：

UCB算法選擇臂算法如下：

1. 如果有counts為0的臂，即從未被選擇的臂，那么先選擇它（即初始時(shí)每個(gè)臂都會(huì)被選擇一次）

2. 如果所有臂都被選擇過，則計(jì)算每個(gè)臂的bonus和value的和，bonus計(jì)算公式如下：

bonus的意義在于，如果我們對(duì)一個(gè)臂的了解過于少，因此它的value值在此時(shí)的置信度是很低的，所以我們需要選擇這個(gè)臂來獲取更多的信息。因此，bonus可以當(dāng)做一個(gè)測(cè)量對(duì)臂了解多少的指標(biāo)，了解越少，bonus越大。加入了bonus這個(gè)指標(biāo)，我們可以說這個(gè)算法是有好奇心的，當(dāng)對(duì)于一個(gè)臂的了解少于了下限，它會(huì)被選中，即使這個(gè)臂的回報(bào)率很低。

更新臂：

每一個(gè)臂被選中之后，會(huì)返回一個(gè)value，那么更新的方法如下：

1.該臂的counts成員數(shù)加一

2. 該臂的value變?yōu)椋涸械膙alue值和新返回的結(jié)果value值按比例相加

當(dāng)我們使用UCB算法，它會(huì)以怎樣的頻率來選中最優(yōu)的臂？答案在最開始時(shí)，所有的臂的置信度都很低，因此每個(gè)臂都會(huì)被選中幾次，此時(shí)選中最優(yōu)臂的概率不高，當(dāng)已經(jīng)選擇了很多次時(shí)，每個(gè)臂的置信度都已經(jīng)相當(dāng)高了，此時(shí)會(huì)一直選擇最優(yōu)臂，偶爾選擇其他置信度過低的臂。如下圖所示

UCB算法與其他算法對(duì)比：

這里，我們使用退火版本的小量貪婪算法和Softmax算法與UCB1算法對(duì)比，一共有5個(gè)臂供選擇。

首先是選中最優(yōu)臂的概率:

可以明顯看到，UCB1算法的波動(dòng)明顯高于其他兩個(gè)算法。不過在模擬末尾處，UCB算法已經(jīng)追上了其他的兩個(gè)算法，如果模擬的次數(shù)跟多，UCB算法將會(huì)優(yōu)于其他兩個(gè)算法。

然后是平均的回報(bào)率：

UCB算法能很快找到最優(yōu)的臂，不過優(yōu)于為了提高每一個(gè)臂的置信度，它回去選擇那些回報(bào)率不高的臂，因此收斂于最優(yōu)臂的速度慢于softamx算法，平均回報(bào)率也低于它。

最后是總回報(bào)率：

總回報(bào)率的結(jié)果已經(jīng)可以由上一張平均回報(bào)率看出來了。softmax最高，UCB第二，小量貪婪最低。

總結(jié)：

在實(shí)現(xiàn)UCB算法的過程中，首先撿回來了閱讀英文文獻(xiàn)的能力，UCB算法的內(nèi)容基本是通過一本英文教材還有英文的維基百科上學(xué)習(xí)到的。其實(shí)以前英文一直挺好的，只是太久不用，忘了挺多。第二點(diǎn)就是對(duì)于C++STL庫(kù)以及模板類的復(fù)習(xí)，平時(shí)stl庫(kù)還能偶爾用一用，但是map,set等就用的特別少了，更別說模板類了，這次好好的復(fù)習(xí)了一遍。第三就是學(xué)習(xí)了一些新的東西，比如Json格式保存數(shù)據(jù)對(duì)，ssh登陸等等一些開發(fā)的額外知識(shí)。實(shí)習(xí)的收獲確實(shí)很大。