Multi-armed bandit?

en.wikipedia.org圖標

我們團隊在amazon搭bandit系統，相對於傳統的supervised learning，bandit非常適合解決online learning, stochastic decision making等問題。幾個在amazon比較常用的幾個use case:

  1. 內容推薦 (content optimization): 這個主要對於很多marketing的內容，比如說想推廣amazon prime。你在amazon網站上看到所有跟prime相關的廣告都是基於Multi-Armed Bandit (MAB)的。
  2. 個性化推薦(personalization): 在amazon主頁上你會看到各種不同產品的推薦，每一行是一個carousel，這種carousel的排序基本上都是基於contextual bandit。有的customer可能推薦viewed products會有更好的效果，有的可能推薦popular products會有更好的效果。從而為了能達到personalization的目的。
  3. 電影音樂推薦 (Music/Movie Recommendation): 類似的，像在amazon video的主頁上，你所看到的電影推薦基本上每一行都是基於MAB。一行裡面具體的內容會基於傳統的recommendation/ranking演算法，像content based。

為什麼要用MAB而不是supervised learning呢？

  1. 有些推薦的內容像廣告是designer手動創造的，很難用ML的方法來預測它的performance會怎麼樣。有的時候只是簡單的wording不同，效果都會差很多。比如說，在cancellation的時候：a) you no longer want to keep your Prime benefit? b) you are about to loss your Prime benefit. 它們的紙面意思完全一樣，但達到的retention效果卻差很多。而這些區別很難做featurization從而被NLP/ML等方法拿來預測。
  2. customer preference變化的很快。比如對於amazon video，可能一個劇很快就火了；可能一個人昨天想看動作片，今天就想看drama；假期的時候紅色的內容很受歡迎，假期過了瞬間效果就很差了。而ML演算法很難很快的跟的上用戶習慣上的變化，而MAB具有有效的創造數據的能力(exploration vs. exploitation)：對於不是很確定的方面進行explore，對於confidence很高的方面exploit。
  3. Cold start：很多項目剛開始並沒有數據，如果randomly sample所有的選項 (like A/B Test)，有可能冒著很多的風險如果某個選項效果很差的話(high regret)。而因為MAB (準確來說是stochastic bandit)可以隨時改變每個選項的traffic allocation，從而可以一定程度上避免這個風險。

一些類似應用場景的文章：

  1. Netflix: https://medium.com/rtl-tech/my-takeaways-from-netflixs-personalization-workshop-2018-f564a19437b6
  2. Spotify: http://sigir.org/afirm2019/slides/16.%20Friday%20-%20Music%20Recommendation%20at%20Spotify%20-%20Ben%20Carterette.pdf
  3. Amazon: https://arxiv.org/pdf/1810.09558.pdf

實話說，我覺得這種演算法毛病在於對arm下的統計環境要求過於敏感，現實的arm都有很多生產約束在裡頭，導致其不太適合參與生產合作，比較適合分裝成黑盒打包整個系統給人家用

這東西我曾經用於各種黃賭毒場景試投，被設計極度古怪的ab機制和流量分配機制搞得我暈頭轉向，導致估算每個arm下的一些統計值，經常被流量或者其他奇怪的模塊打偏，直接線上試投暴走。

最後還是每個arm裡面單獨寫一個拍腦袋的if else 加兜底策略，和學術做的那些漂亮的數學完全兩回事

我覺得bandit是一個很有潛力的方向，尤其是combinatorial bandits with XX constraints/adversarial attack/nonlinear rewards……但目前學業界gap有點大：

1.學界論文很多實驗其實不算online。不少作者沒有完全按照數據集的用戶出場順序、每輪的實際item set以及合理的regret evaluation metric來評估演算法，而是根據數據集提取user、item特徵然後在自造演算法所假設的相對理想的環境中運行演算法~

2.某好友pyq的改編版本：「之前做多臂老虎機的研究，要發XX盡量需要新穎的理論證明和tight bound。如果我加一些很隨機的探索在裡面，很難得到很精確很好的bound，所以為了比較好/容易地證明，就會舍棄一些經驗上效果好但難以精確刻畫的東西或加一些理想化的假設，這樣設計的演算法其實不是很能打。有時候，追求演算法性能和可解釋性二者難兼得，為了發論文我們可能選擇後者」我覺得這種風氣也是促使學界一些論文難落地的原因。

pyq底下留言區有兄弟給了個建議：「bandit可以試試aistats,我們上一篇以及最近一篇實驗效果非常好的多用戶bandit論文都發在這個會議上，對bandit也比較友好」多謝兄臺（飆淚笑）

最後宣傳下SJTU JHC人美心善能力強、在我心裡很清流很promising的bandits方向的李帥老師https://shuaili8.github.io/組（沒經老師同意硬廣一下hhh)~帥帥老師組織了bandits、online learning等方向的討論班（每週多場，老師很忙但還是基本保證每場討論都在，並給出一些建設性comments），不久還有深度學習討論班，估計還有其他討論班也會陸續開展。跟著討論班同學一點點啃bandits、online learning教科書和各種paper、實驗，可以打下很不錯的基礎。日常的個人研究中，老師對我很有耐心且挺花心力指導，奈何我熊孩子不聽話，老辜負她期望，捂臉~

2333反正衷心希望所有學術圈清流能在升級打怪之初就招到優質苗子，和學生深入協同、飛速成長，讓清流有底氣一直清下去！！！

哦哦最後補下老師的研究方向：

1.bandit演算法與證明，包括但不限於在線學習排序演算法、在線影響力最大化、面對有污染反饋的穩定演算法設計、湯普森採樣法

2.推薦系統，包括多任務學習、流數據演算法、在線演算法等

3.NLP，包括Bandit演算法的應用、Code Search等

Facebook 的站內和應用內快速推廣背後存在一套如此的優化系統。這裡說的推廣不是廣告主打廣告的推廣，而是跟 Facebook 自身功能相關的推廣。「Facebook 發布某某新功能啦，要不要來試一試」、「你最近添加的手機號碼還沒有驗證，請儘快填寫簡訊驗證碼」，這些都屬於這套快速推廣系統會顯示的內容。

每一個功能一樣的快速推薦都可能有多個版本，他們分別使用不同的圖標、文案等等。怎麼知道哪個版本的效果更好呢？尤其是圖標、文案等維度可以組合出非常多略微不同的版本，不可能人手去試哪個的效果最好。這就是 Multi-Armed Bandit 的機會了，這個系統一邊統計哪個版本的效果更好，一邊儘可能使用已知效果最好的版本，然後嘗試在兩者之間平衡。

我比較好奇在賭場老虎機應用的多不多。。。

推薦閱讀：
相關文章