合作的进化

鲍捷 ， 2000年12月27日

本文的主要部分来自 
合作的进化　吴坚忠 http://www.unirule.org.cn/symposium/c139.html 

为什么楚汉相争的胜利者是弱小者？

为什么蜜蜂会进化出自杀性攻击行为？

为什么中越战争时换防的一方总要发动攻击？

为什么一个遗传算法中简单的遗传个体能实现复杂算法？



无私从自私中产生

合作基于回报

无私结构与个体道德无关，道德的产生也是以自私为基础的。

但最终无私群体将最成功



人不犯我，我不犯人，人若犯我，我必犯人

滴水之恩，滴水相报，有过必改，下不为例



中国进步最严重的障碍是封建主义，即专制主义和小农意识（两者实际上是一会事）。当然，西方也曾经历过这个阶段。问题的关键是：如何树立社会契约意识？如何通过协同走向有序？这即本书的意义。



一、 博弈中最优策略的产生 

艾克斯罗德（Robert Axelrod）在开始研究合作之前，设定了两个前提：一、每个人都是自私的；二、没有权威干预个人决策。也就是说，个人可以完全按照自己利益最大化的企图进行决策。在此前提下，合作要研究的问题是：第一、人为什么要合作；第二、人什么时候是合作的，什么时候又是不合作的；第三、如何使别人与你合作。

社会实践中有很多合作的问题。比如国家之间的关税报复，对他国产品提高关税有利于保护本国的经济，但是国家之间互提关税，产品价格就提高了，丧失了竞争力，损害了国际贸易的互补优势。在对策中，由于双方各自追求自己利益的最大化，导致了群体利益的损害。对策论以著名的囚犯困境来描述这个问题。

A和B各表示一个人，他们的选择是完全无差异的。选择C代表合作，选择D代表不合作。如果AB都选择C合作，则两人各得3分；如果一方选C，一方选D，则选C的得零分，选D的得5分；如果AB都选D，双方各得1分。

显然，对群体来说最好的结果是双方都选C，各得3分，共得6分。如果一方选C，一方选D，总体得5分。如果两人都选D，总体得2分。 

对策学界用这个矩阵来描述个体理性与群体理性的冲突：每个人在追求个体利益最大化时，就使群体利益受损，这就是囚徒困境。在矩阵中，对于A来说，当对方选C，他选D得5分，选C只得3分；当对方选D，他选D得1分，选C得零分。因此，无论对方选C或D，对A来说，选D都得分最多。这是A单方面的优超策略。而当两个优超策略相遇，即A，B都选D时，结果是各得1分。这个结果在矩阵中并非最优。困境就在于，每个人采取各自的优超策略时，得出的解是稳定的，但不是帕累托最优的，这个结果体现了个体理性与群体理性的矛盾。在数学上，这个一次性决策的矩阵没有最优解。

如果博弈进行多次，只要对策者知道博弈次数，他们在最后一次肯定采取互相背叛的策略。既然如此，前面的每一次也就没有合作的必要，因此，在次数已知的多次博弈中，对策者没有一次会合作。

如果博弈在多人间进行，而且次数未知，对策者就会意识到，当持续地采取合作并达成默契时，对策者就能持续地各得3分，但如果持续地不合作的话，每个人就永远得1分。这样，合作的动机就显现出来。多次对局下，未来的收益应比现在的收益多一个折现率W，W越大，表示未来的收益越重要。在多人对策持续进行下去，且W比较大，即未来充分重要时，最优的策略是与别人采取的策略有关的。假设某人的策略是，第一次合作，以后只要对方不合作一次，他就永不合作。对这种对策者，当然合作下去是上策。假如有的人不管对方采取什么策略，他总是合作，那么总是对他采取不合作的策略得分最多。对于总是不合作的人，也只能采取不合作的策略。

艾克斯罗德做了一个实验，邀请多人来参加游戏，得分规则与前面的矩阵相同，什么时候结束游戏是未知的。他要求每个参赛者把追求得分最多的策略写成计算机程序，然后用单循环赛的方式将参赛程序两两博弈，以找出什么样的策略得分最高。

第一轮游戏有14个程序参加，再加上艾克斯罗德自己的一个随机程序(即以50%的概率选取合作或不合作)，运转了300次。结果得分最高的程序是加拿大学者罗伯布写的"一报还一报"(tit for tat)。这个程序的特点是，第一次对局采用合作的策略，以后每一步都跟随对方上一步的策略，你上一次合作，我这一次就合作，你上一次不合作，我这一次就不合作。艾克斯罗德还发现，得分排在前面的程序有三个特点：第一，从不首先背叛，即"善良的"；第二，对于对方的背叛行为一定要报复，不能总是合作，即"可激怒的"；第三，不能人家一次背叛，你就没完没了的报复，以后人家只要改为合作，你也要合作，即"宽容性"。

为了进一步验证上述结论，艾氏决定邀请更多的人再做一次游戏，并把第一次的结果公开发表。第二次征集到了62个程序，加上他自己的随机程序，又进行了一次竞赛。结果，第一名的仍是"一报还一报"。艾氏总结这次游戏的结论是：第一，"一报还一报"仍是最优策略。第二，前面提到的三个特点仍然有效，因为63人中的前15名里，只有第8名的哈灵顿程序是"不善良的"，后15名中，只有1个总是合作的是"善良的"。可激怒性和宽容性也得到了证明。此外，好的策略还必须具有的一个特点是"清晰性"，能让对方在三、五步对局内辨识出来，太复杂的对策不见得好。"一报还一报"就有很好的清晰性，让对方很快发现规律，从而不得不采取合作的态度。 

　二、 合作的进行过程及规律 

"一报还一报"的策略在静态的群体中得到了很好的分数，那么，在一个动态的进化的群体中，这种合作者能否产生、发展、生存下去呢？群体是会向合作的方向进化，还是向不合作的方向进化？如果大家开始都不合作，能否在进化过程中产生合作？为了回答这些疑问，艾氏用生态学的原理来分析合作的进化过程。

假设对策者所组成的策略群体是一代一代进化下去的，进化的规则包括：一，试错。人们在对待周围环境时，起初不知道该怎么做，于是就试试这个，试试那个，哪个结果好就照哪个去做。第二，遗传。一个人如果合作性好，他的后代的合作基因就多。第三，学习。比赛过程就是对策者相互学习的过程，"一报还一报"的策略好，有的人就愿意学。按这样的思路，艾氏设计了一个实验，假设63个对策者中，谁在第一轮中的得分高，他在第二轮的群体中所占比例就越高，而且是他的得分的正函数。这样，群体的结构就会在进化过程中改变，由此可以看出群体是向什么方向进化的。

实验结果很有趣。"一报还一报"原来在群体中占1/63，经过1000代的进化，结构稳定下来时，它占了24%。另外，有一些程序在进化过程中消失了。其中有一个值得研究的程序，即原来前15名中唯一的那个"不善良的"哈灵顿程序，它的对策方案是，首先合作，当发现对方一直在合作，它就突然来个不合作，如果对方立刻报复它，它就恢复合作，如果对方仍然合作，它就继续背叛。这个程序一开始发展很快，但等到除了"一报还一报"之外的其它程序开始消失时，它就开始下降了。因此，以合作系数来测量，群体是越来越合作的。

进化实验揭示了一个哲理：一个策略的成功应该以对方的成功为基础。"一报还一报"在两个人对策时，得分不可能超过对方，最多打个平手，但它的总分最高。它赖以生存的基础是很牢固的，因为它让对方得到了高分。哈灵顿程序就不是这样，它得到高分时，对方必然得到低分。它的成功是建立在别人失败的基础上的，而失败者总是要被淘汰的，当失败者被淘汰之后，这个好占别人便宜的成功者也要被淘汰。

那么，在一个极端自私者所组成的不合作者的群体中，"一报还一报"能否生存呢？艾氏发现，在得分矩阵和未来的折现系数一定的情况下，可以算出，只要群体的5%或更多成员是"一报还一报"的，这些合作者就能生存，而且，只要他们的得分超过群体的总平均分，这个合作的群体就会越来越大，最后蔓延到整个群体。反之，无论不合作者在一个合作者占多数的群体中有多大比例，不合作者都是不可能自下而上的。这就说明，社会向合作进化的棘轮是不可逆转的，群体的合作性越来越大。艾克斯罗德正是以这样一个鼓舞人心的结论，突破了"囚犯困境"的研究困境。

在研究中发现，合作的必要条件是：第一、关系要持续，一次性的或有限次的博弈中，对策者是没有合作动机的；第二、对对方的行为要做出回报，一个永远合作的对策者是不会有人跟他合作的。

那么，如何提高合作性呢？首先，要建立持久的关系，即使是爱情也需要建立婚姻契约以维持双方的合作。（火车站的小贩为什么要骗人？为什么工作中要形成小组制度？换防的时候一方总是要小小地进攻一下的，在中越前线就是这样）第二、要增强识别对方行动的能力，如果不清楚对方是合作还是不合作，就没法回报他了。第三、要维持声誉，说要报复就一定要做到，人家才知道你是不好欺负的，才不敢不与你合作。第四、能够分步完成的对局不要一次完成，以维持长久关系，比如，贸易、谈判都要分步进行，以促使对方采取合作态度。第五、不要嫉妒人家的成功，"一报还一报"正是这样的典范。第六、不要首先背叛，以免担上罪魁祸首的道德压力。第七、不仅对背叛要回报，对合作也要作出回报。第八、不要耍小聪明，占人家便宜。

（打桥牌和打麻将的区别）

艾克斯罗德在《合作的进化》一书结尾提出几个结论。第一、友谊不是合作的必要条件，即使是敌人，只要满足了关系持续，互相回报的条件，也有可能合作。比如，第一次世界大战期间，德英两军在战壕战中遇上了三个月的雨季，双方在这三个月中达成了默契，互相不攻击对方的粮车给养，到大反攻时再你死我活地打。这个例子说明，友谊不是合作的前提。第二、预见性也不是合作的前提，艾氏举出生物界低等动物、植物之间合作的例子来说明这一点。但是，当有预见性的人类了解了合作的规律之后，合作进化的过程就会加快。这时，预见性是有用的，学习也是有用的。

当游戏中考虑到随机干扰，即对策者由于误会而开始互相背叛的情形时，吴坚忠博士经研究发现，以修正的"一报还一报"，即以一定的概率不报复对方的背叛，和"悔过的一报还一报"，即以一定的概率主动停止背叛。群体所有成员处理随机环境的能力越强，"悔过的一报还一报"效果越好，"宽大的一报还一报"效果越差。

　三、 艾克斯罗德的贡献与局限性 

艾克斯罗德通过数学化和计算机化的方法研究如何突破囚徒困境，达成合作，将这项研究带到了一个全新境界，他在数学上的证明无疑是十分雄辩和令人信服的，而且，他在计算机模拟中得出的一些结论是非常惊人的发现，比如，总分最高的人在每次博弈中都没有拿到最高分。（刘邦和项羽的战争）

艾氏所发现的"一报还一报"策略，从社会学的角度可以看作是一种"互惠式利他"，这种行为的动机是个人私利，但它的结果是双方获利，并通过互惠式利他有可能覆盖了范围最广的社会生活，人们通过送礼及回报，形成了一种社会生活的秩序，这种秩序即使在多年隔绝，语言不通的人群之间也是最易理解的东西。比如，哥伦布登上美洲大陆时，与印地安人最初的交往就开始于互赠礼物。有些看似纯粹的利他行为，比如无偿损赠，也通过某些间接方式，比如社会声誉的获得，得到了回报。研究这种行为，将对我们理解社会生活有很重要的意义。

囚徒困境扩展为多人博弈时，就体现了一个更广泛的问题──"社会悖论"，或"资源悖论"。人类共有的资源是有限的，当每个人都试图从有限的资源中多拿一点儿时，就产生了局部利益与整体利益的冲突。人口问题、资源危机、交通阻塞，都可以在社会悖论中得以解释，在这些问题中，关键是通过研究，制定游戏规则来控制每个人的行为。

艾克斯罗德的一些结论在中国古典文化道德传统中可以很容易地找到对应，"投桃报李"、"人不犯我，我不犯人"都体现了"tit for tat"的思想。但这些东西并不是最优的，因为"一报还一报"在充满了随机性的现实社会生活里是有缺陷的。对此，孔子在几千年前就说出了"以德报德，以直报怨"这样精彩的修正策略，所谓"直"，就是公正，以公正来回报对方的背叛，是一种修正了的"一报还一报"，修正的是报复的程度，本来会让你损失5分，现在只让你损失3分，从而以一种公正审判来结束代代相续的报复，形成文明。

但是，艾氏对博弈者的一些假设和结论使其研究不可避免地与现实脱节。首先，《合作的进化》一书暗含着一个重要的假定，即，个体之间的博弈是完全无差异的。现实的博弈中，对策者之间绝对的平等是不可能达到的。一方面，对策者在实际的实力上有差异，双方互相背叛时，可能不是各得1分，而是强者得5分，弱者得0分，这样，弱者的报复就毫无意义。另一方面，即使对局双方确实旗鼓相当，但某一方可能怀有赌徒心理，认定自己更强大，采取背叛的策略能占便宜。艾氏的得分矩阵忽视了这种情形，而这种赌徒心理恰恰在社会上大量引发了零和博弈。因此，程序还可以在此基础上进一步改进。

其次，艾氏认为合作不需预期和信任。这是他受到质疑颇多之处。对策者根据对方前面的战术来制定自己下面的战术，合作要求个体能够识别那些曾经相遇过的个体并且记得与其相互作用的历史，以便作出反应，这些都暗含着"预期"行为。在应付复杂的对策环境时，信任可能是对局双方达成合作的必不可少的环节。但是，预期与信任如何在计算机的程序中体现出来，仍是需要研究的。

最后，重复博弈在现实中是很难完全实现的。一次性博弈的大量存在，引发了很多不合作的行为，而且，对策的一方在遭到对方背叛之后，往往没有机会也没有还手之力去进行报复。比如，资本积累阶段的违约行为，国家之间的核威慑。在这些情况下，社会要使交易能够进行，并且防止不合作行为，必须通过法制手段，以法律的惩罚代替个人之间的"一报还一报"，规范社会行为。这是艾克斯罗德的研究对制度学派的一个重要启发。

社会生物学

刘易斯·托马斯Lewis Thomas 《细胞生命的礼赞》

道金斯《伊甸园之河》，《自私的基因》《延伸的表现型》《盲人钟表匠》

Edward Osborne Wilson 《社会生物学——新的综合》

第一章 社会生物学的基本原理1-1基因的伦理学1-2社会生物学的基本概念1-3基本定义1-4多倍效应1-5进化步速兵与社会变化1-6进化生物学的两重性1-7社会进化的原动力

第二章 万古长存的基因2-1人类从何而来？2-2自然选择的单位是什么？2-3稳定者生存2-4复制与进化2-5原始基因的三大特点2-6气象万千的生物世界2-7现代基因的特点2-8不朽而自私的基因 

第三章 机体与行为的背后3-1 生物机体的存在意义3-2 基因支配着机体3-3 基因的群体性3-4 行为的目的性3-5 时滞与解决办法3-6 基因与大脑

第四章 亲缘关系学说4-1 绿胡须效应4-2 亲缘关系指数4-3 估计寿命4-4 行为准则4-5 背离准则的行为4-6 狮子的行为4-7 亲缘关系的肯定性4-8 不对称性问题 

第五章 侵犯行为探源5-1 侵犯行为的普遍性5-2 侵犯行为与竞争5-3 宜斯策略5-4 鹰与鸽子5- 5其它策略及策略成因5- 6侵犯行为的近因5- 7人类的侵犯行为 

第六章 利他主义种种6-1 选择与行为6-2 行为模式6-3 互惠利他主义6-4 动物中的利他主义6-5 人类的利他主义6-6 两种利他主义6-7 无条件利他主义在人类社会中的限度6-8 行为价值观与目的

第七章 性与性冲突的奥秘7-1 性的意义7-2 两性及其冲突7-3 两性投资的差额7-4 两性行为模式的差异7-5家庭幸福策略7-6大丈夫策略7-7 炫耀行为7-8 骡子难局与性不平衡7-9 性快乐的进化意义7-10 同性恋的进化原因

第八章 通讯交流8-1 交流的基本原理8-2 复杂的系统8-3 通讯交流的起源与进化8-4 感官通道8-5感觉通道之间的进化竞争

第九章 人类：从社会生物学到社会学9-1 社会组织的可塑性9-2物品交换和互惠的利他主义9-3 结合、性与分工9-4角色表演与多元文化论9-5通讯交流9-6文化、仪式和宗教9-7 伦理学9-8 美学9-9 领土性与部落主义9-10 早期社会进化9-11晚期社会进化9-12 未来



Hamilton GRE里一篇文章



信息经济学

策略的进化——行为进化

计算智能中的社会生物学原则（摘要） 鲍捷

社会生物学中的一些基本原则或现象——如亲族选择或在“自私的基因”假设下导致系统有序（如“进化稳定策略”），以及方法论——如博弈论，在一种人工社会——计算智能系统中也得到了体现。计算智能作为人工智能的一支，包括神经网络、遗传算法、进化计算、人工免疫系统、多Agent系统等许多方法，其基本思想正是“社会化计算”，即计算个体只拥有简单智能，在简单社会规则的指导下竞争和合作，从而导致复杂智能的“突现”。从动力学的角度，智能计算系统和生物社会系统是相似的，而最近研究进展也有力地支持了这一点。例如，进化计算中新近提出的子群进化和共生集团选择即是亲族选择原则的体现；改变所有遗传单元只有一种搜索策略的现实，使不同等级个体具有不同策略，在人工进化系统中建立食物链，最终达到的进化稳态即所要求的解；在多Agent生态系统中，达尔文主义方法和基于博弈论的协商都得到了广泛的运用。这一切绝不是偶然的，正是智能计算系统和生物社会系统的共同本质——有序发展系统，或“信息系统”决定的。我们将进一步指出信息系统的某些特性。

遗传中的行为信息与行为进化模型  鲍捷

一．遗传中的行为信息


图1：经典中心法则

分子遗传学中的中心法则指出，DNA中编码的信息经RNA传递和翻译，产生控制蛋白质的合成，即核酸中的碱基序列作为蛋白质中氨基酸序列的模板而存在。（近年来逆转录酶、朊病毒等的发现使这一经典中心法则已进行了修正）。这种DNA决定蛋白质的思想随后表达为“一个基因一个肽链”，进而决定表现型。但是，存在大量的DNA片段不对应于蛋白质。基因的复制和表达过程是一个“动态过程”而并非是一个简单的数据传输与复制过程。基因中不仅包含控制表现型的片段（只占DNA链总长的4%），更包含了控制生物体行为的片段，这一部分就是控制生命活动的程序。

这可以从两个方面来理解。首先，基因表达具有不同层次上的行为表现。在分子层次上，遗传物质的复制本身倚赖于基因调控，即分子层次行为。其次在个体层次，存在生物体的特定感知-效应行为的遗传。大量实验表明，行为是有遗传基础的，并可分为先天行为和后天行为，先天行为基本上由基因型直接决定，而后天行为是在由基因型所决定的学习能力的基础上考虑到环境影响后获得的行为。行为进化和遗传是一客观事实，遗传和环境共同决定了生物体的行为，不可忽略其中任何一个方面。

二．行为进化模型

传统的遗传算法实际上是基于经典中心法则的，即遗传编码决定表现型，进而决定适应度，其中并无行为的遗传。基于行为进化假说，我们提出：如果把遗传算法中的遗传编码不仅翻译成表现型，也考虑遗传编码所对应的行为特征，遗传个体就变成了一种Agent。这种行为特征可以用感知-效应-表现型三者统一体的方式描述。如图2所示。

相应于行为的先天与后天划分，基于行为进化的遗传算法也可分为先天算法和后天学习算法两类。

先天行为遗传算法的基本思想是：遗传个体通过竞争，在某些既定行为或策略中进行选择，直到某种策略处于优势地位或进入进化稳态策略（Evolutionarily Stable Strategy，ESS）。这种思想的萌芽可体现在博弈人工生态系统的研究中。最著名的实验为Axelrod和Hamilton于1984年进行的策略竞争大赛。其实质是图2算法的一种简化形式，即消除了行为集合的进化特性，而只在初始种群的不同策略间展开竞争。

后天学习遗传算法的本质是策略的自动生成，在人工免疫系统、进化Agent系统和程序进化算法的研究中已有体现。其要点如图2所示。算法构造一个本能行为集合，每个行为都有一个适应度函数，通过适应度函数来衡量每个行为的反应影响度。该集合通过感知器与外界联系，根据不同的感知信息有不同的反应行为，并且调整每个行为的适应度函数，而且行为间通过交叉，变异等操作，产生新的高适应度行为。

发信人：Han_Jing (不吃KFC) 版面名称：AI(203)

标　题：多Agent学习算法(4)

发信站：中国科大BBS站 (Sat, 22 May 1999 21:48:32 )

标　记：标记

1.2.4自利Agent的学习算法(Learning among self-interested agents　 )


在一群自利的Agent中，它们之间存在相互作用，它们能在一定的环境(包括对手)进行学习，并且各有各的策略。下面1.3会详细分析在多Agent中如何运用强化学习(Reinforcement Learning)中的Q-learning算法。



强化学习(RL) 的基本思想是：加强那些能产生良好效果的行为，减弱那些效果不佳的行为。Q-learning当前的强化学习中一种不需要为环境建立模型的算法，能够在线地使用。因此它非常适用于那些可重复的、对手未知的游戏中。很多强化 学习的研究者被限制在单一Agent或那种报酬是绝对正面(如团队问题)或绝对反面 (zero-sum游戏)的多Agent系统中。在3.1中我们将详细介绍在可重复的囚徒困境 问题(iterated prisoner's dilemma，IPD)中,如何运用强化学习策略。在这个问题中，报酬并非是明显的正或反， 因此强化学习在这一问题中的运用是比较困难的。于是我们使用Q-learning agents来参与可重复的囚徒困境游戏，来对付那些 未知的对手。在某些实验中，对手使用针锋相对的策略，而在令一些实验中，对手也是一个用Q-learning作为学习算法的Agent(Q-Learner)。所有的Q-learner能学到对付"针锋相对"Agent的最佳策略，而对付同是Q-learner则比较困难。正是因为其它Q-Learner在不断的学习而导致环境不断变化。而且，没有关于IPD的元知识以鼓励其它Q-Learner进行合作。 

这些Q-Learner的学习可以从三个角度进行改变： 作为上下文的历史长度；使用得内存类型(基于有限历史的查找表或理论上能反映任何深度的历史的可循环网络)；搜索策略。虽然所有的Q-Learner在于Q-Learner进行这个游戏时，它们都要面 对很大的困难，但是历史记录越长，内存类型是查找表和长久的搜索进化的

Q-Learner在游戏中获益最大。

发信人：Zcy_Cy (wws) 版面名称：AI(52)

标　题：囚徒困境问题

发信站：中国科大BBS站 (Thu, 29 Apr 1999 20:48:04 )

标　记：标记

　 问题的陈述:两个犯罪同伙A和B被抓获,他们被单独审问

如果A、B互相出卖(Defect),他们将各得1(P)分.
如果A、B互相合作(Cooperate), 他们将各得3(R)分.
如果A出卖B,B却未出卖A,A得5(T)分,B得0(S)分.
如果B出卖A,A却未出卖B,B得5(T)分,A得0(S)分.　

　　　　Defect(A)　　　　Cooperate(A)

Defect(B)　　　　A=B=P　　　　A=S,B=T

Cooperate(B)　　　　A=T,B=S　　　　A=B=R

　 囚徒困境问题是游戏理论发展中的一个早期游戏,它所具有的 特点是一个使双方得分和最高的结果并不是使一方得分最高的结果, 这就使囚徒困境问题成为能很好的研究社会中个人在冲突与合作之间怎样抉择的问题.


发信人：Han_Jing (不吃KFC) 版面名称：AI(328)

标　题：囚徒困境问题－－强化学习!

发信站：中国科大BBS站 (Tue, 08 Jun 1999 16:43:21 )

标　记：标记


1.简介


在机器学习领域，人们主要是研究有指导学习(Supervised Learning)，就是说，存在一个"教师"，他提供一套训练例子，它们是一对一对出现的，即给出了对每个输入的相应输出。其训练的目标就是学习出一个对输入输出的映射，以能够对其它的输入作出准确的的输出。

而在一些没有可能对输入有预先的输出结果的学习系统中，强制性学习 (Reinforcement Learning ) 就是对付这种情况的。它必须自己对输入选择一个输出，并接收一个性能评价。

故此，强制性学习比有指导学习要难，因为它要自己寻找一个最好的输出的。

在Multi-Agent System中，强制性学习更适合，因为环境是不可知的Agent要对环 境作出反应。



强制性学习有两种类型：

1·非序列化non-sequential：每一步都有精确的的马上的报酬(Payoff)。

强制性学习在此领域的研究始于五十年代。在Zero-Sum Games中，能收敛到游戏 的解答；在Identical-payoff　Game中，能收敛到一个局部最优的平衡位置；另外，辅助学习(Associative Learning) 是使用上下文的。

2·序列化sequential：每一步会影响将来一连串的行为和将来的报酬。它比非序列化的要困难，因为报酬(Payoff)不易给定。

强制性学习在此领域中，更多地是对单个Agent的研究。也有对Multi-Agent System的强制性学习研究，但是只对比较简单的问题，或Agent是独立的，并且从理论上Q-Learning不能用于非静态环境。

从控制论上说，Agent是控制者，环境是被控制的系统，而强制性学习算法是在控制问题中的猜测最优的技术。

强制性学习是近似实现动态程序设计的算法，并且不需要一个关于环境的模型。

不象传统的动态程序设计那样，它能用于在线地提高性能。尽管Agent与环境相互作用，使环境动态变化。


2.Q-Learning算法

Q-Learning算法是Watkins.C. 1989年在他的博士论文里提出的。

在Q-Learning中，是反复修改Q(s,a)值的。Q(s,a)得含义是：从状态S出发，采用了动作a以后，假设以后采用的是最优的步骤，预测在未来得到的报酬。当所有的 Q值被学习出来以后，从任何状态出发采用的动作必须是Q值中最高的那个。


下面是算法的描述： 

1·用任意值进行初始化；
2·从当前状态s出发，选择一个动作a，得到一个立即的报酬r，到达下一个状态s'。
3·更改Q(s , a)的值，这个值是如下计算的：
　　Q(s , a)的修改值 = A [ r + max Q( s', b ) - Q( s, a) ]

　　　　　　　　　　　　　　　　b
其中A是控制学习速度的，而0<r<1是削弱因子，它会影合作性。

4·返回2。

当环境是静态的并且状态转换只依赖于当前状态和采用的行动，并不依赖于达到这一状态的历史，则这个算法可以收敛到正确的Q值。

a是控制学习速度的，在整个过程中应该适当地减慢。

在状态s中选择行动ai的可能性是：

P(ai ) = e exp(Q(s, ai) / t )/对所有a求和( e exp(Q(s, a) / t))

其中t是可计算的温度参数，能够控制搜索的数量。

之前的关于强制性学习的研究都是指对完全正效果的报酬或完全反面效果的报酬的问题。而Q-Learning是填补他们之间的壕沟，并且是动态变化的环境：对手是固定策略的针锋相对，或其它Q-Learning Agent。后者更难，因为环境非静态， 而且对手没有"合作"的鼓励策略。

对于学习者，有三方面的变化：

1· 作为上下文的历史记录长度；
2· 他们使用的内存方式(Lookup表 或者 神经网络)；
3· 搜索策略


. 囚徒困境问题(Prisoner's　Dilemma)



3.1　2-Agent的囚徒困境问题描述：

2-Agent的囚徒困境问题是一个社会行为的缩写，合作还是背叛，对于单个的

Agent，背叛是较好的选择，但对于Agents总体的报酬来说，则合作会达到最大值

-这就是所谓的困境。下面列出他们的报酬矩阵：



　　　　　　　　Column　Player

　　　　　　　　合作　　　　背叛

Row 　　　　合作　　　　R(=0.3)　　　　S(=0.0)

Player　　　　背叛　　　　T=(0.5)　　　　P(=0.1)



其中，必须满足下列两个公式：



T>R>P>S

2*R>T+S>2*P



此外，这个游戏不允许协商，没有相互间的承诺，没有恐吓，没有报酬的转移。

如果有上述的因素，则问题会变得很复杂。



3.2可重复的囚徒困境描述(Iterated Prisoner's Dilemma)

可重复的囚徒困境更具有社会性，一个Agent会再次相遇它的对手。在supergames

里，一个Agent的策略是从它以往的所有历史(包括它自己的行动和他的对手的行

动)中映射得到下一个行动策略的。在单纯(Pure)的策略里，映射是可决定的，也

就是说，非概率的；在混合策略中，Agent从过去的历史获得一些行动方案，然后

随机地抽取。因此在单纯策略里，历史的记录可以忽略一部分，如自己的行动或

对方的行动，因为他们之间是相互可以推导的。



合作动机：在IPD中，即使是对于一个自私的Agent，它也会有可能选择合作，以

劝诱对手合作给它带来利益。



重复次数：如果知道了重复的次数，则最后一次大家都失去了合作的动机，采用

背叛行为；由此向前倒推，结果会导致整个过程都是"背叛-背叛"，故此不能让Agent知道重复的次数。而这一点在现实生活中也是可理解的，你不可能知道今天

与你打交道的人明天，或者以后会不会再与你打交道。



由此，Agent在第N次重复的游戏中的目标是使下列的值最大： 



i=n到无穷大求和： r exp(i-n) Ri ,



其中Ri表示在第i次重复中获得的报酬。





4. 强制性学习在IPD问题中的运用



4.1. 历史长度

由于任意长度都是可能的，下面是两种解决的办法：

1· 固定的历史长度，只记录前N个行为；

这种方法底下有2种实现办法：

a)　针锋相对(Tit - for - Tat) ：以牙还牙，第一步是合作，然后每次都以上

次对手的对策来对待对手。

b)　PAVLOV：只有Agent选择相同的策略时选择合作。即自己的策略是上一次赢则

保持，上一次输则改变策略。



在一些有随机的干扰的IPD例子中，PAVLOV会比针锋相对更好。



2·反覆修改一些能够表示全部历史的特征值。

例如当某个值超过一个限制时，它才会背叛。



但是，两种策略都有共同的缺点，存在隐藏状态的问题：第一种策略忽略了老的

记录;；第二种策略只给出抽象值，重要细节可能被忽略，而且有意义的特种不容

易被定义。



4.2. g的选择对策略的影响

对于可重复的囚徒困境问题来说，没有任何单一的策略是最优的。除非知道对手

的策略。可重复游戏的无名氏理论是：只要g足够高，那么任何满足个体Agent的

合理可行的报酬，这些报酬值高于他们的最小最大值(就是当Agent选择最优方案

时所获得的最差回报的值。)，能够通过一个特定的子搏弈精炼那士均衡(Subgame 

perfect Nash Equilibrium)得到。



针锋相对策略被选择作为对手，这不单因为它在可重复的囚徒困境问题中有较优

的性能，而且对付它的最优方案是知道的。这里列举三种对于不同g值的最优方案

：



1·总是合作，报酬Vc=R/(1-g)；

2·在合作和背叛中轮流变换，报酬Va= (T+gS) / (1-g2)；

3·总是背叛，报酬Vd= T + gP/ (1-g )；



对于上述的定义(T=0.5,R=0.3,P=0.1,S=0)来说，Vc=0.3/(1-g)，Va=0.5/(1-g2)

，Vd=0.5+0.1g/(1-g )。在这种情况下，当

g 32/3时，与针锋相对策略的Agent总是合作；

1/43g<2/3时，与针锋相对策略的Agent是合作与背叛轮换；

g<1/4时，与针锋相对策略的Agent总是背叛；



故g越大，将使Agent趋向于合作。但在Q-Learning Agent对Q-Learning Agent中

，却不一定是这样。



4.3.在可重复的囚徒困境问题中游戏者的学习

整个学习过程是一个很长的训练过程，即Agent只有一个机会学习，而评价是在训

练的最后阶段。

除非额外说明，否则实验中的a=0.2，g=0.95。a和g都是通过实践证实可以促进合

作的。





在可重复的囚徒困境问题中Q-Learning Agent的体系结构图：

4.4. Q值的存储

1·窗口长度：



a) 完全历史：

如果历史长度是全部，那么Agent面对的环境是静态的。由于每一步的状态都增加

了一维数据(历史)，所以没有一个状态是被重复的遍历的。又由于每种状态只出

现一次，所以Agent不能分辨出对手是用单纯策略还是混合策略。同时，在这种情

况下收敛性不适用于Q-Learning。



b) 有限长度历史：

我们把有限长度的历史称为"感觉"(sensation)。在这种情况下，Agent面对的是

一个非静态的环境，因为上下文(历史窗口)相同的情况下，对手的对策可能不同

。这是因为，对手的历史长度可能不一样，对手可能更长，由此自己认为是同一

状态的，对手可能分辨为两种状态。而且对手的学习策略可能改变Q值，使对同一

个Sensation的对策的映射不同。

同时，在这种情况下收敛性也不适用于Q-Learning。



2·两种表示方法：



a)　Lookup Table：

假设窗口长度为w。则有w个以前的行为，w个自己的和对手的行动记录。例如：

w=1，则sensation有4种可能：CC，CD，DC，DD。对每种可能的sensation，有两

个Q值，如对CC有Q(CC, C)，Q(CC, D)。



b) 回归神经网络(recurrent neural network ) ：

从理论上来说，一个回归神经网络能够储藏任意深的历史记录，找出哪个特征是

重要的，从训练例子总结得出以前没有没有观察过的状态。对于神经网络表示法

来说，输入的sensation是一样的。Sensation用4位二进制数表示。第一位为1表

示对手上一次是合作；第二位为1表示对手上一次是背叛；第三位为1表示自己上

一次是合作；第四位为1表示自己上一次是背叛。



两者比较：神经网络表示方法需要更多的训练例子才能学到合作的策略。前者只

要数千例子；后者要数万例子。



4.5. 搜索方式(Exploration methods)

所谓的搜索是指如何从Q值得到执行这个行动的概率。Agent需要选择一个好的行

动序列。但是一个Agent如果每次都仅仅选择它认为最好的动作那是不足够的。它

应该尝试其它同样能适应环境的行动，特别是在存在非静态因素的情况下。



普遍来说，一个Agent的搜索策略应该是所有历史(真正的状态)的函数。在这里，

每个Agent的策略是历史长度的函数。历史长度在这里用来降低Boltzmann搜索的

温度。例如，



在状态s中选择行动ai的可能性是：

P(ai ) = e Q(s, ai) / t / Sae Q(s, a) / t

其中，t是当前总共进行的PD游戏的总数n的函数，t=5*0.999n

当t<0.01则没有搜索的效果(也就是说，选择的是最高Q值得行动)。(5, 0.999, 

0.01 )这些数据是从实验中得来的。他们是专门针对上面所述的报酬矩阵数据的

。



同理，搜索方法的不同，也会导致在相同上下文情况下出现不同的动作。



. 实验结果



实验1 - Q-Learning　VS　针锋相对策略 



g=0.95，lookup表，数千次的囚徒困境问题(IP )，sensation为上一次的行动；

无上下文单元，无反馈的神经网络，数万次的囚徒困境问题(IP )。

在lookup表中，用100次可重复的囚徒困境问题(每次含100,000次IP)验证g对实验

影响的理论。符合前面论证(见4.2)。



实验2 - Q-Learning　VS　Q-Learning 

L：使用lookup表，R：使用回归的神经网络，B：使用Boltzmann搜索算法。



实验有三种类型：LB vs LB，LB vs RB，RB vs RB。每次100 IPD含300,000次PD

。当进行了6212次PD后，t<0.01，故搜索消失。但学习进程继续进行。通常，

300,000次PD后，系统会达到一个稳定的状态例如CC，或者是状态的循环，例如CC

，CD，CC，CD?。长度是Qm+n，m、n分别是两个Agent的历史长度。



合作比较少。RB-RB中，最后报酬达到平衡；LB-LB中，合作比较多。LB-RB中，出

现非对称的相互模式，LB具有优势。



实验3 - 无搜索(No Exploration)

用N表示无搜索。则实验是LN，RN，LB，RB之间的对抗。无搜索的Agent通常取当

前Q值最大的行动。

实验证明，这种Agent受Q值的初始值影响很深。通常初始选择哪种行动，以后就

选择哪种行动。在一些实验中，RB比RN的总报酬要高，而LB通常比RN好，RB比LN

优越。



实验4 - 延长搜索深度

我们可以设想：如果Agent在整个重复游戏中，都运用搜索可能会使Agent学到更

好的策略。搜索的持续时间和t=0.5*X中的X有关(见4.5)。由此，我们把X设成

0.999，0.9999，0.99999，0.999999，0.9999999。其相对应的搜索深度是6212，

62143，621458，6214605，62146078。



实验结果表明，X=0.999时的效果明显差于X值取更大值得情况下。在X=0.999时，

没有DD出现，CC明显增多。但是X取更大值，虽然总的CC增多，但是单一CC状态为

结果的减少，循环状态增多，如CC-CD等。



实验5 - 无sensation，无历史

无sensation，无历史就是不用考虑上下文。在这种情况下，Agent只有两个值可

以学习-就是对合作和背叛的动作的Q值。g可以设成0。现在，无论对手是

Q-Learning Agent还是针锋相对策略Agent，学习的结果通常都是背叛。



但是如果在对手是针锋相对策略 的情况下，把报酬向前多考虑一步，则会有可能

改善。



实验6 - 不同sensation，历史长度不同

在这里，Agent有分别是1、2、3的长度的历史记录。实验表明，历史长度确实影响结果的类型。越长的历史，会产生越长的循环类型。在双方的历史长度不一样

的情况下，历史长度长的稍微比短的有多一点的优势，但并不比想象中大。



6. 将来的工作



将来的工作包括：研究搜索和产生的结果类型的关系。例如，如果双方的X值不一

样(就是说搜索的深度不同)，或者使用的搜索策略不同 时会产生什么结果。又如

，训练Agent对付不只一个的对手。



从长远来说，应该寻找更好的学习方法来替换Agent体系结果中的算法。学习应该

能帮助Agent适应由其它Agent组成的社会合交给它的任务。因此，这里有很多可

以学习的东西，如学习定价格，时间表，竞争协商，合作性的分布式约束满足问

题，以及通讯策略等等。