求通俗解釋下bandit老虎機到底是個什麼東西？
單臂one-armed 和 多臂multi-armed 的
關於這個問題，我們想採用微軟亞洲研究院資深研究員陳衛在中國理論計算機年會上的報告「在線組合學習」進行回答，解讀多臂老虎機和組合在線學習之間的關係。
————這裡是正式回答的分割線————
賭場的老虎機有一個綽號叫單臂強盜（single-armed bandit），因為它即使只有一隻胳膊，也會把你的錢拿走。而多臂老虎機（或多臂強盜）就從這個綽號引申而來。假設你進入一個賭場，面對一排老虎機（所以有多個臂），由於不同老虎機的期望收益和期望損失不同，你採取什麼老虎機選擇策略來保證你的總收益最高呢？這就是經典的多臂老虎機問題。
這個經典問題集中體現了在線學習及更寬泛的強化學習中一個核心的權衡問題：我們是應該探索（exploration）去嘗試新的可能性，還是應該守成（exploitation），堅持目前已知的最好選擇?在多臂老虎機問題中，探索意味著去玩還沒玩過的老虎機，但這有可能使你花太多時間和金錢在收益不好的機器上；而守成意味著只玩目前為止給你收益最好的機器，但這又可能使你失去找到更好機器的機會。而類似抉擇在日常生活中隨處可見：去一個餐廳，你是不是也糾結於是點熟悉的菜品，還是點個新菜？去一個地方，是走熟知的老路還是選一條新路？而探索和守成的權衡就是在線學習的核心。
多臂老虎機的提出和研究最早可以追述到上世紀三十年代，其研究模型和方法已有很多。其中一類重要的模型是隨機多臂老虎機，即環境給予的反饋遵從某種隨機但未知的分布，在線學習的過程就是要學出這個未知分布中的某些參數，而且要保證整個學習過程的整體收益盡量高。這其中最有名的一個方法是UCB（Upper Confidence Bound）方法，能夠通過嚴格的理論論證說明UCB可達到接近理論最優的整體收益。
組合在線學習：組合優化和在線學習的無縫對接
介紹了多臂老虎機問題，那組合在線學習和它之間有何關聯呢？我們繼續來看一下組合多臂老虎機（CMAB）問題。在組合多臂老虎機問題中，你一次拉動的不是一個臂，而是多個臂組成的集合，我們稱之為超臂（super arm），原來的每個臂我們稱之為基準臂（base arm），以示區別。拉完這個超臂後，超臂所包含的每個基準臂會給你一個反饋，而這個超臂整體也給你帶來某種複合的收益。
那麼如何解決組合多臂老虎機的問題呢？你可能首先想到的就是把每一個超臂看成是經典多臂老虎機問題中的一個臂。但是超臂是多個基準臂的組合，而這樣組合的數目會大大超過問題本身的規模——組合問題中經典的組合爆炸現象，因此傳統的方法並不適用。所以在線學習不能在超臂這個層次進行，而需要在基準臂層次上進行，並需要與離線組合優化巧妙地結合。我們在ICML2013的論文[2]中給出了組合多臂老虎機的一般框架和基於UCB方法的CUCB演算法。CUCB演算法將組合優化和在線學習無縫對接實現了前面圖示中的反饋迴路。較之前的涉及組合多臂老虎機的研究，我們的模型適用範圍更廣，尤其是我們通過給出收益函數的兩個一般條件，能夠涵蓋非線性的收益函數，這是第一個能解決非線性多臂老虎機問題的方案。我們的工作，包括之後我們和他人的後續工作，都強調對在線學習部分和離線優化部分的模塊化處理和無縫對接。也即我們將離線優化部分作為一個黑盒子神諭（oracle），這部分可以由具有相關領域知識的專家來完成。而一旦離線優化問題可以精確解決或近似解決，我們就可以把這個離線演算法當作黑盒子拿過來和我們在線學習方法相結合，達到有嚴格理論保證的組合在線學習效果。這使得我們的方法可以適用於一大批已經有離線優化演算法的組合在線學習問題，比如最短路徑、最小生成樹、最大匹配、最大覆蓋等問題的在線學習版本，而不需要對每個問題單獨再設計在線學習演算法。
在論文「Combinatorial Multi-Armed Bandit: GeneralFramework, Results and Applications」中,我們進一步將組合多臂老虎機模型擴展為允許有隨機被觸發臂的模型。這一模型可以被用於在線序列推薦、社交網路病毒式營銷等場景中，因為在這些場景中前面動作的反饋可能會觸發更多的反饋。然而在其理論結果中，我們包含了一個和觸發概率有關的項，而這個項在序列推薦和病毒營銷場景中都會過大，造成在線學習效果不好。在今年剛被錄取的NIPS論文「 Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications」中，我們徹底解決了這個問題：一方面我們論證了序列推薦和病毒營銷等滿足某種特定條件的問題都不會有這個不好的項，另一方面我們指出在更一般的組合多臂老虎機中這個項又是不可避免的。這是目前研究可觸發臂的組合多臂老虎機中最好的一般結果。
除此之外，我們還在與組合多臂老虎機相關的方面做了若干工作，比如如何在反饋受限情況下達到好的學習效果；如何解決先探索再找到最佳方案的組合探索問題；當離線優化基於貪心演算法時，如果更好地將離線貪心演算法和在線學習相結合；如何在有上下文的場景中解決組合序列推薦問題；以及當超臂的期望收益取決於每個基準臂的隨機分布而不僅是每個基準臂的分布均值時，如何同樣有效地進行組合在線學習。
————這裡是回答結束的分割線————
以上回答摘選自微軟研究院AI頭條，組合在線學習：實時反饋玩轉組合優化。
感謝大家的閱讀。
本賬號為微軟亞洲研究院的官方知乎賬號。本賬號立足於計算機領域，特別是人工智慧相關的前沿研究，旨在為人工智慧的相關研究提供範例，從專業的角度促進公眾對人工智慧的理解，並為研究人員提供討論和參與的開放平台，從而共建計算機領域的未來。
微軟亞洲研究院的每一位專家都是我們的智囊團，你在這個賬號可以閱讀到來自計算機科學領域各個不同方向的專家們的見解。請大家不要吝惜手裡的「邀請」，讓我們在分享中共同進步。
也歡迎大家關注我們的微博和微信 (ID:MSRAsia) 賬號，了解更多我們的研究。
multi-armed bandit是一個非常經典的模型，當然，該模型有很多變種。我能查到的中文資料基本上都是濃濃的看不懂的翻譯腔，用最最通俗的語言描述其中最基本的模型應該是這樣的
假設你面前有這些色彩斑斕的按鈕，按完每個按鈕可能有兩種情況：從機器里掉出一塊錢，或者什麼也沒有發生
每個按鈕出錢的概率是不一樣的，也許那個紅色的按鈕有80%的概率會出錢，而那個右下角灰色的出錢概率為0，按到死都出不了一分錢，當然，在此之前，你對每個按鈕出錢的概率的先驗知識為0,也就是說你不知道每個按鈕出錢的概率是多少。
而我們的目標是，在有限次的按按鈕過程中(比如按1000次)，獲取的錢越多越好，應該以怎樣的策略呢？
這個問題的麻煩之處在於，尋找最優的按鈕和獲得最大值之間的平衡!
舉個例子
假設你開啟上帝模式，知道這些按鈕里概率最高的是紅色按鈕，有80%的概率出硬幣，那最好的策略顯然就是死命的對那個紅色按鈕懟，那麼1000次嘗試你會得到錢數的期望是800塊，並且沒有比這更好的策略了。
但在不知道這些知識的前提下，我們怎麼做？小蠢是這樣做的，每個按鈕按三次，然後看出錢的多少，然後以後的每次都對著三次出錢最多的那個懟，但出錢概率70%的按鈕也可能按三次一次都沒出錢，出錢概率10%的按鈕也可能連續按三次都出錢了，這樣做顯然不科學！
那增加實驗次數行不行？我們每個按鈕按50次，那麼可以假設它收斂到期望了，但如果我們有20個按鈕呢？1000次機會全給你做實驗了，即使50次實驗能得到所有按鈕的準確的出錢概率，你也用光了1000次機會，然後把這些機會全部平均分給所有按鈕，和你隨機亂按沒有區別。（摔桌，寶寶不玩了）
當然你也可以提出各種不同的策略、演算法，但是歸根結底，這個問題的本質就是尋找最優的按鈕和獲得最大值之間的平衡!
然後畢竟它只是個模型，傳染病模型都可以用到和它根本不搭界的消息傳播模型上，它能使用到的領域基本上就是這種尋找最優-獲得最大值矛盾的地方，舉個例子，臨床試驗：我們既要保證得出的每種藥品治癒患者的概率較為準確，又要使得最後參加試驗的患者治癒率最高；廣告投放：我們在找到最能吸引點擊率的廣告的過程中又要使得，過程中廣告的點擊率儘可能最大。
有很多奇奇怪怪的策略來解決這個問題，比如其它樓鏈接中UCB族演算法，當然還有用的比較多，可能性能更好的[1] Thompson sampling。
以上
reference：
[1] O. Chapelle and L. Li. An empirical evaluation of thompson sampling. In NIPS, 2011.
multi-armed bandits是非常經典的序列決策模型，要解決的問題是平衡「探索」(exploration)和「利用」(exploitation)。
設想你進入一個賭場，面前放置一排賭博機，每個賭博機都會給出獎勵或者不給出獎勵。你需要做的是在有限次數中最大化自己的收益，你會怎麼做？
當然是先隨意嘗試幾個。
在嘗試幾個後，比如你發現某一賭博機A總是能給出獎勵，另一賭博機B總是不給出獎勵。這時，你就會猜想是不是賭博機A每次必給出獎勵，賭博機B就是從不給獎勵。
然而，這樣的猜想也許是不對的。事實上，可能賭博機B從此之後都會給獎勵，賭博機A再也不給出獎勵。又或者，還有另外一個你從未嘗試過的賭博機C，它才是每次必給出獎勵。
在上面這個例子中，如何合理利用賭博機A和賭博機B的信息，叫做「利用」；如何發現賭博機C，叫做「探索」。
在多臂賭博機的每一步，你都面臨這樣的選擇：是基於已經獲知的賭博機信息選擇收益最高的那個，還是繼續探索沒有嘗試過的賭博機以得到更好的那一個？
所有已知的演算法，都在嘗試在每一步對上述問題作出更好的回答：是利用已知，還是有策略地探索未知。
現行演算法分很多類，比如UCB，Greedy，再比如Thompson Sampling。當然，這些演算法也不同程度地對賭博機給出獎勵的機製做了假設，比如這些獎勵的給出是服從伯努利分布，或者其他。
多臂賭博機算作online learning的一種，但是跟reinforcement learning並不一樣。最大的區別在於，強化學習有planning的過程，而多臂賭博機並沒有。
bandit的描述就不說了。我來說說它代表的這類問題的本質吧
這類大問題叫做MDP:馬爾可夫決策過程。我默認你知道馬爾可夫過程，馬爾可夫就是特殊的MDP，它不考慮每個狀態做出的action（決策）
MDP差不多的定義為：某個(agent)的初始狀態為S0，然後從Action集合A中挑選動作a0做出反應，反應後以概率P(s,a)隨即轉移到下一個狀態S1。。。直到終止時刻。
如果我們為他的每個(s,a)特定狀態下的特定決策，打分Q(s,a)，我們想要找到的是，終止時刻得到的累計回報最大的策略。
那麼這個問題可以由一個我們很熟悉的方法解決----動態規劃。
但我們在用DP求解問題時，往往已知了所有決策Q(s,a)的價值。比如說背包問題，所有物品的價值都是已知的，我們直接去求解：
dp( i,j ) = Max( dp( i-1, j ), dp( i-1, j-w[i] ) + v[i] )
這裡狀態i,j表示可使用前i個物品，剩餘背包容量為j時的最大價值估計。i，j的sate(最大)估值由(i-1,j)或者(i-1,j-w[i])的狀態估值的較大值得到，action實際上隱含了，分別為選取與不選取。
action的回報r(s,a)=v[i]or0(選or不選)。這樣，我每次獲得狀態s(i,j)的評估時，只需要訪問之前的兩個節點dp( i-1, j ), dp( i-1, j-w[i] )就足夠了。DP求解的關鍵是如何設計s(i,j)，狀態空間和轉移規則設計的越精巧，那麼評估完整個(i,j)狀態表所需要的訪問次數就越少。
好了那麼多臂老虎機問題現在來了，如果我們背包每個物品的價值不知道，只有把東西從倉庫取出來（當然這次就別放回去了），在網上查一查，才能得到估值，這咋辦？你可能會說把東西都評估一次再來DP解決，沒錯，這是一種解決方案。但是如果網上每次查的估值並不是一個定值，而是服從某一種分布，那麼要怎麼辦呢？你可能說多查幾次，估計出他們的價值均值。
很好，這時候你在用蒙特卡洛方法解決MDP問題了
一個更加切身的例子是試藥實驗，醫生如果只給病人開出目前療效最好的葯，那麼也許療效更好的新葯永遠也得不到測試。但如果不停地試新葯，新葯也許效果不好，病人會怨聲載道。如何trade-off 「探索」(exploration)新鮮事和「利用」(exploitation)已有知識 就是多臂老虎機問題的核心， 如@yzzs 所回答。
當然多臂老虎機問題是reward未知的MDP問題中最簡單的一種，因為多臂問題不需要規劃。也就是只需要估計action （選擇哪個手臂）背後的reward的價值，這個action不會影響state的轉移（因為任意手臂轉一次，一個episode就結束了，我們就可以對選擇的手臂背後的估值進行更新啦）。
如果這個問題難一點，就如我說的那個估值未知的背包問題，不僅需要探索物品的價值，還需要規劃如何裝滿背包，這時候一個episode是裝滿一次背包。這個時候才算得上一個完全的增強學習問題。這個時候，如果想在一個episode內更新估值函數，就需要時間差分法啦，時間差分法就有大名鼎鼎的Q-learning，也就是最近大火的deep mind在使用的DQN的基礎思想。
你問為什麼是Q，Q在馬爾科夫過程代表廣義狀態轉移矩陣，也就是P在時間上的微分，或者說狀態轉移強度矩陣。自然離散狀態時刻下，就是差分啦。因為如果對所有action的估值你自信以後，你必然會做出bayes決策，所以最終的策略，每一個action的reward自然應該和你選擇它的概率正相關，所以Q矩陣（函數）既可以理解為狀態轉移概率的時間差分，也可以理解為對策略估值。
多臂賭博機multi-armed
一台賭博機有很多個拉杆，每次機會只能隨機拉其中一個拉杆。
拉下拉杆後可以得到一份收益，雖然每個拉杆背後具體的收益金額未知，但可以肯定是個確定值（一般是服從某種概率分布）。
因此，每次用掉一次機會去試驗，都可以得到一次拉杆的收益（但多次試驗同一根桿也未必能肯定出錢的概率就是多少）。
從長遠來看，如果使用次數無限，那麼逐步摸清每個拉杆收益的情況（稱為先驗知識），然後選擇收益最大的那根桿反覆去拉它當然是最好的。
不過在不斷試驗學習直到找出最優桿之前，都會有不划算的時候。
賭徒有限次使用機會中，採用何種策略，才能獲得最大總收益？
exploitation-exploration權衡（探索-利用權衡）：
「exploration」：探索新桿以獲得更多關於每個桿的收益信息，以期找到最優桿
「exploitation」：選擇已有回報最高的桿來獲取最大利益
正在做國賽~24h研究機器學習
一個完整的增強學習框架包括狀態、動作、回報、環境等基本概念，其對應的任務問題有三個主要特點：
1. 不同的動作會有不同的回報；
2. 回報是隨時間延遲累積的；
3. 行動回報與環境狀態是相關的。
對於一些簡單的增強學習任務，往往並不需要滿足特點2和特點3，將這類問題稱為**多臂賭博機模型**。它來源於賭場的多臂賭博機，即按下不同的臂會有不同額度的獎勵。假設有一個Agent能夠不斷進行**嘗試**找到獎勵最大的臂，即建立學習函數，直接將觀察狀態映射為行動。
學習的最優函數將**直接**對應最優行動回報的動作，因此也將該函數稱之為策略函數。基於此，有兩種基本的Agent建模方法，一種是使用平均累積回報函數；二是使用神經網路近似描述，通過策略梯度的方法計算學習設嘗試賭博機的臂（動作）為k，則平均累積回報函數定義為$Q(k)=(Q(k) imes count(k) + reward) / (countk(k)+1)$。假設基準線為0，表現好的動作回報為1，差的動作回報為-1。
而使用神經網路建模，可簡單設計為單層網路模型，節點的權重分別代表不同的動作。初始權重設置為1，則最優損失函數可定義為$loss = log(k) * reward$。假設同上。
Agent在嘗試找到最優策略的過程也需要策略，稱為**「探索／利用」策略**。其想法也很直觀，如果回報是一個確定值，要找到回報最大的臂，最好先把所有的臂先探索試一遍，然後再選擇回報最大的臂一直搖下去（利用）。
但很多問題的回報函數來自於一個概率分布，那麼僅探索一遍是不能找到可利用的最優臂的。這需要多次探索，但探索時間太長也會導致利用的收益減少，因此需要一個演算法對上述兩個動作進行折中。
e-貪心演算法是一種簡單的探索／利用折中演算法，即以概率e進行探索，以概率1-e進行利用。直觀理解來看，如果搖臂獎賞的不確定性較大，則探索概率e設置較大，進行更多的探索更優；反之亦然。
實驗對比基於策略的兩種Agent建模方法的效果，在相同探索概率e下，策略梯度方法相比平均獎賞方法所需訓練的次數更少且結果更穩定。這是由於神經網路可以認為是多線性模型的組合，進而有更強的能力表達「策略函數」。
對代碼實現和實驗效果感興趣的朋友，可在數據小蝦米公眾號後台回復「代碼」，獲得鏈接地址。
蟹妖~首先解釋下multiarmed bandit的意思吧，臂指的是老虎機的台數，假設有
舉個栗子，你去一個賭博場，是一個拋硬幣的遊戲，有5枚硬幣，正面反面分布不均勻，導致正每一枚硬幣出現正面反面的概率可能不相等，且各不相同，每次你可以選擇其中一枚硬幣擲出，如果擲出正面，你可以得到一張毛爺爺，而拋擲硬幣的次數有限的，例如1000次，顯然，如果要拿到最多的利益，你要做的就是不斷統計，並且在下一次投擲時選擇根據統計選出的能拋出正面的那一枚硬幣，而每一個硬幣叫做一臂。
具體數學推導等等http://mlyixi.byethost32.com/blog/?tag=%E5%A4%9A%E8%87%82%E8%B5%8C%E5%8D%9A%E6%9C%BAi=1這裡有
推薦閱讀：
TAG:機器學習 | 強化學習ReinforcementLearning |