326
別人用老虎機來娛樂，他們卻從中發現了一個全新的電商推薦機製！
老虎機與電商推薦，兩者看似風馬牛不相及的東西，竟有剪不斷、理還亂的關係！
今天阿裏妹為大家推薦這篇關於創新機製設計方案PH－MAB的論文，發表於國際智能體研究的頂級會議AAMS，由阿裏推薦算法團隊劉暢、蔡慶芃、張宇魁與清華大學唐平中老師合作完成。它將會為你揭開老虎機與電商推薦係統不為人知的緊密聯係。
多臂賭博機（Multi-armed Bandit, MAB）模型是人工智能、強化學習的重要子領域之一，也是描述電商平台推薦問題的有力工具，其基本設定是這樣的：一台賭博機有多個臂，當玩家拉動一個臂後，他可能獲得的收益服從一個隨機分布，每個臂對應不同的分布函數。玩家可以玩N次，每次可以任意拉動一個臂，並獲得收益，同時增強了對該臂信息的掌握程度。MAB模型要解決的問題是如何尋找一個決策序列（即用戶每次拉動哪條臂），使得用戶的總收益最大化。在商品推薦情景中，電商平台是玩家，眾多商品是arms，那麼平台的每次推薦都是一次“試玩”，平台收集曆史上的推薦與轉化情況，以此為依據進行下一次選擇，平台以最大化收益為目標。
圖1：拉斯維加斯賭場的老虎機
我們這篇《Multi-armed Bandit Mechanism With Private History》設計了一個新的機製，用來挖掘更多可以用來優化MAB及最終推薦結果的信息。為了闡述清晰，我們首先定義公有曆史和私有曆史。
如果某個賣家的商品被平台推薦，相當於平台拉動了這個臂。之後這個賣家的貨被展示給用戶，其結果（被買與未被買）這個信息就會同時被平台和賣家所掌握。因此，這一信息我們定義為公有曆史（Common History, CH）。傳統的MAB模型就是根據每次拉動不同的臂（推薦不同商家的商品）所積累的CH來產生決策序列。
然而更進一步地，我們考慮到賣家不僅在本平台銷售商品，在其它情景也有交易（例如線下、垂直領域、其它電商平台等），並將這一信息定義為私有曆史（Private History, PH）。從道理上講，如果平台除了擁有CH外再加上PH的信息，那一定是可以比傳統的MAB模型效果更好。故而，我們這篇論文的目的就是希望用戶能將PH報告給本平台，在CH的基礎上結合PH來優化MAB模型，亦即優化商品推薦結果。所以我們提出的模型也被命名為PH-MAB。
前麵所說的PH默認是真實的私有曆史，否則如果拿虛假的PH來融入到推薦係統中，那不僅不能保證能優化推薦結果，更可能適得其反。我們希望也相信絕大多數賣家會報告其真實PH給平台，但是係統如果不能在數學上保證理性用戶都會報告真實信息的話，那是存在嚴重漏洞的。那麼如何保證賣家報告的PH都是真實的呢？這一問題上實際上屬於機製設計（Mechanism Design）的範疇，我們實際是要設計一個”truthful”的機製。
機製設計是人工智能方向中重要的研究領域，它適用於這樣一種情境：在一個包含眾多智能體的博弈環境中，每個智能體都有一定的選擇權利，同時每個智能體都有各自的優化目標——通常尋求自身利益的最大化。在此情境中，如何設計出一種機製或者說一係列規則，使得各智能體在這些規則下優化自身利益的同時，可以達到某些整體利益的優化，這就是機製設計的核心工作。
在我們關注的商品推薦問題中，注意到推薦平台有最大化總收益的需求，同時平台可以根據曆史信息決定選擇哪個參與者的商品進行推薦，因此平台是個智能體；同時，賣家有優化自身利益的需求，同時他們有權利選擇自己報告真實還是虛假的曆史數據，那麼賣家也是智能體。因此這是一個典型的適用機製設計的博弈場景——報真還是報假？每個賣家的選擇都是一次博弈。
在我們的研究工作中，針對不同的MAB運作狀態設計了一係列機製，這個機製假設每個賣家有一個私有曆史，平台讓每個賣家report私有曆史，然後PH機製結合這些曆史用epsilon算法選擇arm, 機製根據每輪的回報（reward）以及回報的曆史支付相應的酬勞給賣家。可以證明該機製中無論其他賣家的回報曆史記錄如何，每個賣家向平台匯報真實曆史記錄時的收益是最高的，因而根據理性決策假設，所有賣家都會匯報真實曆史。通過模擬實驗可以發現，該機製相比原有的epsilon-greedy算法損失（regret）更小. 並且平台的收益也高於原有算法。
現實世界中很多智能體相互博弈的問題都可以歸約為MAB模型，例如醫學實驗問題中，醫生是那個玩家，不同的治療方案是臂（arms），醫生要依次選擇給排好隊的患者實施哪個治療方案；又如，在信息路由問題中，玩家是信息發送方，若幹個路由路徑是arms，發送方要選擇走哪個路徑發送信息更節省時間。因此，我們在PH－MAB機製設計上的創新，必將為營造更公正的市場環境，應用於多個行業提供理論支持。
最後更新：2017-06-21 14:02:15