【深度学习】遗憾算法系列2：囚徒困境与纳什均衡

本系列的第二个博客是介绍纳什均衡（Nash Equilibrium）和遗憾匹配（Regret Matching）如何走向平衡。这是为本系列的最后一篇文章作准备，在那里我们我们将介绍在德州扑克中利用反事实遗憾最小化来无限的接近甚至达到均衡。（上一篇文的翻译地址：http://www.atyun.com/7659_如何正确的猜拳：反事实遗憾最小化算法.html）

我们设计智能体并不同的环境中测试他们的能力。从驾驶到写博客，扑克，我们从人们在各种不同任务的出色表现中得到灵感，我们正在研究能够轻松、无缝地从一个任务到另一种工作的智能体。这项研究的关键工具之一是建立心理学测试, 以更好地了解我们正在开发的智能体与人类相比是如何起作用的。随着我们的智能体变得更加复杂和自主，心理测试作为一种了解他们的行为和内部运作手段将变得更重要。

我们想用一个浅显的例子来说明这个心理测试的想法。囚徒困境是一个有趣而简单的测试, 它已经成为博弈论和纳什均衡的代名词。我们想测试遗憾匹配和另一个强化学习智能体在囚徒困境下如何表现,并说明这些测试在AI研究中的价值。针对不熟悉囚徒的人, 下面我会详细的介绍。

囚徒困境

一天, 警察逮住了两个在城市两边贩卖违禁物品的人。他们逮捕了一个叫戴夫的男人，他因现行的贩毒行为而被逮捕。在一个完全不相干的事件中，警察逮捕了另一个也在贩毒叫做卢克的男人。他们都被带到警察局，并被关在单独的监狱里。

局长在他们各自的的牢房审问两人时，告诉他们说，他们都面临两年的牢狱之灾，这是一个简单案子。他们两人都将被指控非法意图占有财产。他们每人都要蹲两年牢。

但当他把消息告诉卢克的时候, 他意识到，这两人很像几周前发生的重大持械抢劫案的犯罪嫌疑人。尽管他强烈怀疑他们与这早期犯罪有关系, 但他没有任何有力的证据将他们联系到一起, 他们只是大致符合描述。

因为, 没有足够的证据来指控他们抢劫, 所以他设想了一个计划, 给他们分别提供交易, 激励他们互相告密。

他对戴夫和卢克所做的交易如下:你会因毒品交易获刑两年，因为你现行毒品交易被抓，所以至少是两年。

但是，如果你供认抢劫罪但另一个人没有，你只会获刑一年，另一人获刑5年。

但是如果你们都供认了，每人获刑三年。

现在通过上述事例，详细讲述了囚徒困境。这笔交易可以在下面的收益表中看到。

囚徒困境的回报表

如右下角所示，从整体来看双方都否认是最佳选择。这一选择是双方共同犯下最小的相互监禁刑罚的理性选择。但这是个极不稳定的情况。一个人不能保证另一个人也会理性的选择。另一个犯人的不理智可能会导致多数人的不理智并选择告密。

AI智能体会选择告密吗？

我们想要测试AI与特定的遗憾匹配在相同情况下如何应对。智能体也会更倾向于告密吗？这样的测试从纳什均衡的角度来看是有趣的, 也有助于说明AI研究中一个有趣的工具。

随着神经科学的启发人工智能,特别是强化学习的不断推进, 不论我们所构建的智能体是否像人类和其他哺乳动物一样行事，开始将心理学的测试纳入到研究中是至关重要的。这将有助于阐明我们的奖励结构和算法设计是否输出与人类相似的行为。

因此，我们采用了经典的囚徒困境实验，我们详述上述并运行两个遗憾匹配和我们自己的QRL网络在实验中发现, 这些智能体都有一个强烈的告密倾向—-就像人一样。两种智能体都优化了纳什均衡。

以上是QRL网络1000次迭代的囚徒困境实验，显示出强烈的倾向于告密。

那么纳什均衡是什么呢？简而言之，纳什均衡是一个游戏已经陷入僵局的局面, 在这场比赛中，没有一个玩家能够通过切换策略达到更好的结果。这个概念是由数学家约翰·纳什（John Nash）提出的。

例如, 在双人游戏中, 比如囚徒困境，纳什均衡是一个结果, 二号玩家的策略是一号玩家策略最好的回应，同时一号玩家的策略是二号玩家策略最好的回应。

在这个AI囚徒困境的背景下, 如果卢克告密, 戴夫最好的回应是告密, 因为判3年比5年好。如果卢克不告密，戴夫的最好回应是告密，因为判1年比2年好。

一般来说, 有可能有多个纳什均衡也有可能一个也没有。

现实世界的应用

假设你目前没有被监禁并且被提供一个出卖你犯罪同伙的交易。那对探索现实世界的纳什均衡和强化学习是很有帮助的。囚犯困境是一个微不足道的的例子, 但纳什均衡(加上CFR和其他AI强化学习)有许多现实世界的应用。任何有众多的竞争对手和各种策略的游戏或商业环境, 例如扑克和首价拍卖, 都隶属于纳什均衡。我们在Google Adwords人工智能平台Remi AO中部署了我们自己的反事实遗憾最小化调整，并取得了有趣的成果。

为了简便起见, 我们不会详细介绍全部的谷歌Adwords（关键词）拍卖机制。但我们会探讨首价拍卖，它很简单但有许多搜索关键词拍卖的特征。

我们在这里讨论的拍卖涉及隐藏出价的投标。更确切地说, 投标人同时在不知道竞争对手的出价的情况下提交他们自己的出价。

这个目标(关键词广告位) 被分配给出价值最高的竞标人以换取钱财。为了让这个例子看起来简单，我们假设, 当超过一个投标人提交了最高出价，那目标即广告位会分配最高投标者首页第一个位置。把拍卖当作一个战略游戏, 我们认为每个投标人当作一个玩家，就像每个囚犯是一个玩家一样。然后,我们认为玩家i的出价都是他们合理的策略。

在这个例子中, 我们假设估值 vᵢ受到了对手的限制和了解。事实上，这种情况很少发生。不同的公司可能会在线上广告拍卖中对广告位置的估值往往不同，因为他们在广告上的产品利润率不同。

然而, 这一假设是必要的，因为估值是在收益表中使用的，因此，玩家对对方的回报函数是了解的。

在隐藏出价拍卖中的一个标准规则就是，赢家i向拍卖商支付他竞价的全额。（尽管这在很多广告拍卖中不是十分准确）由此产生的机制被称为首价拍卖。假设赢家是投标人i, 其中标是bᵢ。由于为目标或者说广告位置创造的价值是 vᵢ, 收益(换句话说, 利润) 是vᵢ−bᵢ。对于其他投标人来说回报为0。

值得注意的是，在这种情况下在在线广告拍卖中，赢家的收益可能是负数。当投标人提交的出价高于被拍卖目标或广告位的估值时，就会发生这种情况。

综上所述, 首价中玩家i的报酬函数pᵢ定义如下, 其中b是提交投标的矢量:

考虑到这个比赛与首价拍卖和玩家的估值为v有关。所以如果“i = argsmax b”那b就是纳什均衡

1.bᵢ ≤ vᵢ

简而言之, 赢家不出价太高，即出价小于目标或广告位置的价值。

2. max≠ᵢv≤bᵢ

简而言之, 赢家递交了足够高的出价来取胜。

3.bᵢ= max≠ᵢb

另一个玩家递交了与玩家i相同的报价。

在上面，1和2表示 vᵢ = max v，意味着每个纳什均衡的最高出价投标者就是赢家。这是一个相当明显但被低估的假设, 因为持有最高估值的投标人有能力出价最高。

假设拍卖中的出价b的矢量满足1到3.投标人i是赢家，并且满足1他们的利润是正数。如果他们投标较少，他们的利润可以增加，但随后式子3另一个第二高出价的玩家成为赢家，而玩家的我的回报变为0.相反，任何其他玩家j的回报是0，只有当他们出价更高时才能成为赢家有机会增加回报。但是像式子2，他们的回报变为负数。

所以b是纳什均衡。