【深度学习】遗憾算法系列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是纳什均衡。

原文发布于微信公众号 - ATYUN订阅号(atyun_com)

原文发表时间:2017-10-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

滑铁卢大学开发了一套AI工具,教泥瓦匠初学者搬砖诀窍

科技行者报道 来源:INSIDE SCIENCE 编译整理:科技行者 经验丰富的泥瓦匠通常具备老道的习惯性技巧和技术以减轻负载于身上的压力。然而,这些技巧并不总...

1837
来自专栏机器之心

缅怀吴文俊院士,回顾数学大师不断创新的一生

机器之心整理报道 参与:微胖、吴欣 吴文俊是中国最具国际影响的数学家之一,他对数学的核心领域拓扑学做出了重大贡献、开创了数学机械化新领域,对数学与计算机科学研究...

34315
来自专栏凌帅的阅读思考与实践

如何成长成我们想要的样子(中)

上一篇我们分析了有专长的巨大好处。同时我们知道了,任何人只要持续的学习精进,就一定会成为非常厉害的人。但大部分却是不能坚持的,有硬件和软件两方面的原因。今天我们...

831
来自专栏奇点大数据

话说量化(3)

上次咱们聊了聊市场催生的根本原因,是由于人们为了降低交易的成本而“发明”出来并一直保留至今的。在几千年的过程中,随着运输技术和信息技术的不断发展,市场正在以更快...

751
来自专栏币圈

投资战法在币圈熊市如何得到高回报

比如每年把钱存在银行的平均利率,或者高三的成绩从一百分到零分取平均值,最后得70分的是最多的,这都是正态分布。

1034
来自专栏互扯程序

量子计算机研发20年,刚进入它的“电子管时代”

量子计算机(quantum computer)是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当某个装置处理和计算的是量子信息,运行...

734
来自专栏AI科技大本营的专栏

不要学人类以貌取人,AI须远离伪科学

光明的另一面,是黑暗。 就在人工智能为人们打开一扇无比美好的天窗时,阳光的照射,让屋子的背光面,蒙上一层阴影。 而这层阴影的始作俑者,可能并非名目张胆恐怖分子、...

3527
来自专栏钱塘大数据

川普的逆袭,是给大数据的一记耳光!

昨日,美国总统选举落下帷幕,共和党总统候选人唐纳德·特朗普在这场权利的游戏中获得胜利,成功当选美国第58届总统。这次美国总统竞选被德国《商报》称作“第一次数字化...

3187
来自专栏大数据文摘

当航线、就业、保险的数据分析过程遇上可视化

1653
来自专栏PPV课数据科学社区

☞【案例】大数据与数据挖掘的相对绝对关系

泄密者爱德华·斯诺登(Edward Snowden)还在寻求容身之所的时候,美国国家安全局(NSA)全方位收集电话和电子邮件记录之事经过他的披露,已经引发了不安...

3338

扫码关注云+社区