老虎机与电商推荐，两者看似风马牛不相及的东西，竟有剪不断、理还乱的关系！
今天阿里妹为大家推荐这篇关于创新机制设计方案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机制设计上的创新，必将为营造更公正的市场环境，应用于多个行业提供理论支持。
