Background
這些年在國泰金控做資料科學的日子，我一直很欣賞螞蟻金服強調的techfin，結合技術、數據能力去極致金融創新。像是 TitAnt: Online Real-time Transaction Fraud Detection in Ant Financial、Heterogeneous Graph Neural Networks for Malicious Account Detection 兩篇 Paper 所提到的，透過 Representation Learning on Graphs 的這種概念進行詐欺偵測，或是母公司 Alibaba 在 CTR、Recommder System 上的應用，如 Deep Interest Network for Click-Through Rate Prediction、ATRank: An Attention-Based User Behavior Modeling Framework for Recommendation 等論文都非常有趣，大量結合 Attention 到客戶行為上。其他像是京東、百度等企業也都非常多創新的技術結合在商業場景上，更不用說商湯、曠視等 Computer Vision 的企業，這些年在 CVPR Conference 中各種輾壓眾生，在 AI 領域不得不讚嘆許多中國企業技術是十分頂尖的，有和 FAANG、 Mircrosoft 等公司並駕齊驅的趨勢，在此就不多說。
扯遠了，去年到 LA 參加在 Long Beach 舉辦的 ICML 2019 Conference，
看到螞蟻金服發表的 Paper: Generative Adversarial User Model for Reinforcement Learning Based Recommendation System 及 JP Morgan 展示 Reinforcement Learning (以下簡稱RL)在公司的應用。
就一直很希望能將 RL 應用在國內金融領域，畢竟前些日子的印象還是停留在，自從 Alphago 引領風騷，RL 最主要的應用還是在電玩上，像是 OpenAI 開發的 Gym 套件有非常多的場景，看到 RL 在金融領域應用還是很心動的。不過研究了一段時間，到頭來看我對於各間公司秀 RL 在自有場景的成效是抱持懷疑態度的，這可以從幾個月前 Google 提出了 RecSim 平台試圖帶起潮流就可看出端倪，畢竟RL目前還是很難普及化的原因就是因為太難掌握全局狀態了。不過我私心還是認為在 AI 的幾個技術面向：ML、DL、RL，RL 才是真正的 AI Learning，想像中的 Skynet、Jarvis 就是那個樣子。
所以今天想介紹的 RL，用我的角度來粗分兩大階段，Stage I: Bandit，Stage II: Simulator，之所以會這樣分的理由如下圖，狀態(State)轉移的問題非常複雜，特別在實務上，我們往往很難去預知未曾發生過的情形的下一步轉移，既然複雜，不如就把狀態拿掉，其實 RL 的基本理論是 Markov Decision Process(MDP)，因此也可說是 MDP 的簡化版。至此，大家只要知道 Bandit是 RL 的一環即可，具體來說就是 RL 的低配版，但是應用的可行性相較於RL 是高上不少的。我會把篇幅集中在 Stage I: Bandit，Bandit 最大的應用就是 A/B Testing、推薦系統。以往常見的 A/B Testing 就是在一段時間內，用統計量評估兩種方法的好壞，後續會介紹為何 RL 優於這種用統計量評估方式， 並以我所看到的 Netflix、Amazon 等公司案例輔助說明。
Part I 主要介紹在Context-Free model 下常見的3種 bandit 策略，主要應用是 A/B Testing，Part II 則會介紹 Context-Based model，主要應用則是推薦系統，並介紹 RL 在國泰各子集團的應用。
Introduction
就從 Netflix 開始吧，約莫從2018年開始，Netflix 陸陸續續有非常多的演講，都是關於Bandit 在A/B Testing、推薦系統的應用，當然也不意外，對Netflix 而言，個性化推薦就是最重要的關鍵因子之一，要如何從大量的片源去進行個人化推薦就是一個棘手的問題。從早年舉辦的推薦系統大賽頒發 Netflix Prize 就是一個研發外包的例子。
所以講到推薦系統，不外乎就是從 Item-based、User-based Collaborative Filtering 到 Matrix Factorization 的矩陣分解，然後為了加入更多的 user features，又有 Factorization Machines，其實到此為止就是抓取許多Embedding features 的信息。直到 DL 開始火熱起來，Google 提出的Wide&Deep 非常有趣，透過 Generalization、Memorization 的互補可以同時學到新商品的潛在關係、挖掘既有商品的歷史信息，後續的幾篇論文就是改裡面的 Layer，並加入 Attention 概念，如DeepFM、DIN、ATRank等，架構基本上就沒太多的變動了，但是能夠做這些模型的前提就是要有足夠的資料量，才有辦法設計這些模型，今天如果是一間新公司，沒有任何的資料，他是沒辦法直接訓練出上述這些模型的。可是公司想要衡量哪個方案好，或是做一個推薦系統，那應該怎麼辦？
一個常見的作法就是 A/B Testing，既然我沒有資料，我就先 Random 分配A、B 兩種方法，或是 Random 的產品推薦，等到累計一段時間收集一定的資料量了，我就可以說到底是 A/B 方案好，或是訓練一個推薦系統了，其實就是一個探索(Explore)-利用(Exploit)的問題，可是問題就來了。
其實商業的一個本質，就是希望用最低成本換來最高報酬，可是當我們用 A/B Testing 的時候，其實某部分就是違背這項原則，試想，我們今天要決定 A/B/C 三種方案哪種最好，當我們在 Learning 階段，用 Random 採取平均分配的作法，我們只會賺到1/3的收入，直到 Earning 階段才火力全開，另一個場景是，某公司用 A/B 兩種 Random 推薦方法作產品推薦，很有可能A方法產品推薦效果非常差勁，用戶只使用一次就再也不會回來使用公司產品了，那麼用 A/B Testing 方法就可能失去一半的潛在用戶數。
A/B Testing 的程式碼大概像這樣
因此，比較好的做法是，能不能讓模型自己學習，自動根據損失成本調節未來方案分配給用戶的數量，那麼我們就可以逐步走向最低成本換來最高報酬的路，而這種作法就是RL的分支 Bandit Learning。
Bandit Learning 概念來自於吃角子老虎機，玩家拉下拉桿會得到一個隨機報酬，玩家的目標就是希望獲取最大報酬，賭場往往有多台吃角子老虎機，稱之為多臂吃角子老虎機， 如何從不同的機台獲取最大報酬，就是常見的 Multi-Armed Bandit (MAB) 問題。
所以，為什麼 MAB 可以和 A/B Testing 沾上邊？
Multi-Armed Bandits
大家可以想像，站在企業角度來看，當有 A/B/C…多種網頁介面，到底哪種好呢？或是有 A/B 兩種促銷方案，哪種比較誘人？甚至是 Netflix 有多部電影，該推薦哪部電影比較適合給新用戶。
常見的 A/B Testing 看的是統計量，而 MAB 看的是模型所帶來報酬(Reward)，假設有 K 個機台，就會有 K 個arm，在每回合我們都會選定一個arm，得到 Reward，我們的目標就是要所有回合 Reward 的總和最大化。同時，也就能計算在每回合當中，沒有選定最優 arm 所帶來的損失，也就是 Regret，並且使得所有回合 Regret 的總和最小，所以接下來的重點就在於如何選定最優的 arm，也就是圖中的 \theta*。
常見的 Bandit 策略作法有3種，分別是1. Epsilon-greedy 2. Upper Confidence Bound(UCB) 3. Thompson Sampling，更多細節分支如 Bayesian UCB 這邊就不贅述了，有興趣可以參考 Bandit Algorithms for Website Optimization — O’Reilly Media 這本書，本文不會探究模型的細節，有興趣的讀者可以在自行研究。
Epsilon Greedy
Epsilon Greedy 的概念非常好懂，假使今天有4種 Bright (光靈)的海報要做推薦，我們不曉得哪一種最可能使得用戶點擊這部電影，那就採用\epsilon的機率進行探索，隨機從4種挑1種海報推薦，再根據客人的點擊更新個海報的機率值，有1-\epsilon的機率選擇這4種海報中，機率最高的海報做推薦。但 Epsilon Greedy 的缺點就是，在探索階段，4種海報被選到的機率都是一樣的，即便是個爛海報，比較好的作法應該是讓爛海報被選到的機率低，那我們就必須要知道或是有多少信心去知道哪個是爛海報，這種帶有信賴區間的方法就是 Upper Confidence Bound(UCB)。
Epsilon Greedy 的程式碼大概像這樣
Upper Confidence Bound(UCB)
UCB 的概念就是讓算出的估計機率值 \hat p 逼近實際的機率值 p，用上面例子，如果海報推薦的越多次，我們就可以算出好海報的 \hat p，並且接近 p ，但問題是我們並沒有這麼多次去嘗試推薦海報，所以 \hat p 、 p 中間會有一個 \delta 的落差，UCB 就是這個估計機率\hat p + \delta，有關 \delta 的計算牽扯到 Chernoff-Hoeffding Bound，有興趣的可以再去研究。那這 \delta 有什麼意義呢？其實可以看到被選擇的海報嘗試的次數越多，變異區間會變得越來越小(分母越大)，沒被選到的海報，隨著嘗試次數增加(分子越大)，\delta變大，被模型選到的機率就會變高，這種一來一往的做法，可以使得每種海報最終都被算出一個區間。
其實 UCB 就已經是個非常普世的做法，但假設我們已經事先知道哪張海報比較好了，我想根據先驗機率再去做計算，這時UCB就是一個問題，於是你可能有一個感覺，這不就是常見的 Frequency vs Bayesian 嗎？UCB 屬於 Frequency 派，Bayesian 派的則是Thompson Sampling。
Upper Confidence Bound 的程式碼大概像這樣
Thompson Sampling
Thompson Sampling 的概念是說，對於這種 Bernoulli Distribution 的問題，p = \theta 是好海報的機率、1-\theta是爛海報的機率，通常跟隨著 Beta (\alpha, \beta)分佈，Beta 分布則會根據我們是否選擇到正確的海報所獲得的 Reward 進行更新。根據實務經驗來看， Thompson Sampling 的效果通常是好於 UCB 的。
Thompson Sampling 的程式碼大概像這樣
這些方法會根據資料有不同結果，下圖作為一個示意圖！
Conclusion
以上所講的方法就是 Context-Free Model 中，常見的3種 Bandit 策略，效果往往優於 Random 分配的 A/B Testing，值得將來有做 A/B Testing 的讀者去做嘗試。
但大家可能已經注意到 MAB 的缺點，MAB 把每張海報看成是獨立的個體，並沒有考慮到海報的內容或是用戶的屬性。舉例來說，不同年齡層、性別對於海報的喜好是有差異的，但 MAB 缺乏這樣的機制，也因此 MAB 放在 A/B Testing 效果可能不錯，但是用來做產品推薦往往效果是非常糟糕的。
如果要納入用戶、海報的內容(Context) 怎麼辦，這就是下一篇會介紹的 Context-Based Bandit: Contextual Bandit.
Reference
https://qconsf.com/system/files/presentation-slides/2018-11_-_qcon_artwork_personalization_talk.pdf
[1] TitAnt: Online Real-time Transaction Fraud Detection in Ant Financial. arXiv:1906.07407 (2019).
[2] Heterogeneous Graph Neural Networks for Malicious Account Detection. arXiv:2002.12307 (2020).
[3] Deep Interest Network for Click-Through Rate Prediction. arXiv:1706.06978 (2018).
[4] ATRank: An Attention-Based User Behavior Modeling Framework for Recommendation. arXiv:1711.06632 (2018).
[5] Generative Adversarial User Model for Reinforcement Learning Based Recommendation System. arXiv:1812.10613 (2020).
[6] Wide & Deep Learning for Recommender Systems. arXiv:1606.07792 (2016).
[7] DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. arXiv:1703.04247 (2017).
