今天 Skylar 在出差的路上，一邊開著車，一邊聽著歌。在遙遙無期的路途中，他突然想到今天是禮拜一，Spotify 會推薦「每週新發現」的歌單，因此他滿懷期待地點開，不知道 Spotify 今天又會推薦什麼好聽的歌給他，為他平淡的路途增添一點色彩。
你們會不會好奇，Spotify 怎麼知道要推薦什麼歌呢？從歌單內容來看，其實也不是最新、最熱門的歌，而且常常意外地被打中。
在討論 Spotify 的推薦演算法之前，免不了又要來聊聊統計（身為一個資料科學家，滿口統計也是合情合理的）。
但是！請不要看到統計就害怕，我會用簡單的小故事來介紹 Spotify 推薦演算法後的統計概念。
今天要聊的主題是 Multi-Armed Bandit，讓我們開始吧！
Multi-Armed Bandit 最主要的概念是，在做決策時，每次都有兩種選擇：Exploration 和 Exploitation。
以 Spotify 為例，在建立新的推薦歌單時，如何決定當前要 explore 或 exploit？要如何平衡這兩個選項，哪一個選項多做一點，會對建立推薦歌單更有幫助呢？
這個權衡問題就是 multi-armed bandit 在研究的事情，讓我們來看一個小故事以了解細節吧！
今天 Skylar 要去一個小城鎮出差九十天，這間小鎮有三間餐廳（A 義大利麵店、B 壽司店、C 拉麵店），每間美味程度的分布都不同，要如何決定每天要吃哪間餐廳，才能夠讓 Skylar 的利益最大化呢？
每間餐廳的美味程度分佈為：A ~ N(8, 2), B ~ N(5,3), C ~ N(10, 5)。
以美味的平均分數排名：C > A > B。不過值得注意的是，因為美味程度是一個分布，不是每次去都會達到平均值，可能會有高有低。
Skylar 每天兩種選擇
因此整體而言，Skylar 有三種行動方式：
行為
不管之前吃過哪間餐廳、評價為何，每天都隨機選擇一間餐廳。
長期而言，reward 的期望值為 30 x 8 + 30 x 5 + 30 x 10 = 690。
問題
某間特別難吃的餐廳，還是花了三分之一的時間去吃他。
和 optimal (which is 90 x 10 = 900) 的差距為 900 - 690 = 210。
行為
前三天先各去一間餐廳嘗試，後面的每一天都去前三天吃到最好吃的那間餐廳用餐。
問題
不過前三天去餐廳吃飯時，出餐品質不一定會到平均值，因為還是有一個分布在。
假設 Skylar 品嘗到的品質為：A = 10, B = 4, C = 7。結果 Skylar 反而覺得 A 餐廳才是最好吃的，
Reward 的期望值為 (10+4+7) + 10 * 87 = 891。
但是只吃每間餐廳一次，不一定能夠搜集到足夠的資訊。
行為
設定 ε = 0.1 or 0.05，代表每天有 ε 的機會，可能會想要去 explore 其他餐廳，其他時間就吃之前覺得最好吃的餐廳。
問題
雖然有 ε 去調整什麼時候要去 explore 其他餐廳，但是在那一天還是只會讓那間被嘗試的餐廳只有一個機會。
例如 Skylar 之前都覺得 A 義大利麵店有平均 8 分好吃，到需要探索的那天時，跑去吃 C 拉麵店，覺得拉麵店當天只有 7 分好吃，所以之後他還是都選擇去吃 A 拉麵店。
好，Skylar 總共有三種行動策略，但每個方案好像都有點問題，還有沒有別的方式呢？
我們先來思考一下，假設我們就是 Skylar 的話，會有什麼想法呢？
儘管在 #3 的策略中，有 ε 來權衡 explore 和 exploit。不過，在實際生活中，也有可能出現以下情境：
在剛到小鎮的一週內，Skylar 大多都去 A 餐廳和 B 餐廳，去 C 餐廳的次數寥寥無幾，因此他可能會想說「嗯⋯⋯去 C 餐廳的次數很少，也許我該再給 C 餐廳一次機會」。
在這個方法中，將造訪餐廳的次數也納入考量，如果這間餐廳去太少次，有可能沒有搜集到足夠資訊，因此也許會考慮再多去吃嘗試看看。
這就是我們以下要介紹的方法。
行為
每個時間點 t，根據 μᵣ + Hoffding's inequality 以挑選餐廳 r。
Hoffding's inequality = sqrt (2 × ln(t) / Nₜ(r))
現在我們簡化題目，先只看 A 和 B 兩間餐廳。
假設 A 和 B 在 Skylar 心中的平均分數很接近，A 為 5，B 為 4.9，所以可以暫時忽略 μᵣ 這一項。
假設今天是來小鎮的第八天，在前幾天中，Skylar 去 A 餐廳吃了五次（N_A = 5），B 只有吃兩次（N_B = 2）。
由於 μ_A 和 μ_B 很接近，在忽略 μᵣ 的情況下，比較兩者的 Hoffding's inequality：
Hoffding's inequality 中，兩者的 ln(t) 都是 ln(8)，而 N_B 較小，讓整體的變大，因此 Skylar 決定去 B 餐廳。
以上，總共介紹四種 Skylar 選擇餐廳的方式，究竟哪一種方法比較好呢？其實要取決於餐廳數量 N 和餐廳美味程度的變異數。
在這部影片中，他比較所有方法，結果顯示只有純 exploitation 或 UCB1 會得到最好的結果，純 exploration 或 ε-greedy 無論在哪個情境都不會有最好的結果。
好的，以上就是 Skylar 選餐廳的各方法比較，這其實也是 Spotify 在建立推薦歌單時使用的統計方法。而 Spotify 實際執行的細節為何，他們又做了什麼改進呢？請待明天分曉。
謝謝讀到最後的你，如果喜歡這系列，別忘了按下喜歡和訂閱，才不會錯過最新更新。
也歡迎到我的 medium 逛逛！
Reference:
iThome鐵人賽
看影片追技術