别人用老虎機來娛樂，他們卻從中發現了一個全新的電商推薦機制！

老虎機與電商推薦，兩者看似風馬牛不相及的東西，竟有剪不斷、理還亂的關系！

今天阿裡妹為大家推薦這篇關于創新機制設計方案ph－mab的論文，發表于國際智能體研究的頂級會議aams，由阿裡推薦算法團隊劉暢、蔡慶芃、張宇魁與清華大學唐平中老師合作完成。它将會為你揭開老虎機與電商推薦系統不為人知的緊密聯系。

mab模型中的公有曆史與私有曆史

多臂賭博機（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機制設計上的創新，必将為營造更公正的市場環境，應用于多個行業提供理論支援。

<a href="https://mp.weixin.qq.com/s/5qzmx9xng08aw-qjculmda">原文連結</a>