老虎机与电商推荐，两者看似风马牛不相及的东西，竟有剪不断、理还乱的关系！
今天阿里妹为大家推荐这篇关于创新机制设计方案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”的机制。
机制设计是人工智能方向中重要的研究领域，它适用于这样一种情境：在一个包含众多智能体的博弈环境中，每个智能体都有一定的选择权利，同时每个智能体都有各自的优化目标——通常寻求自身利益的最大化。在此情境中，如何设计出一种机制或者说一系列规则，使得各智能体在这些规则下优化自身利益的同时，可以达到某些整体利益的优化，这就是机制设计的核心工作。
原文链接：
http://mp.weixin.qq.com/s/5QzMx9XNG08AW-qjCULMdA
