一般对策中的最优回复结构与均衡收敛

我们在五个案例中考虑了批量学习，但我们也研究了一个在线学习实例（带噪声的EWA），并表明结果对随机性具有鲁棒性。该代码可根据要求提供给相应的作者。除非我们选择一个参数设置，例如，在该参数设置中，所有学习动态都会收敛到与纳什均衡相差很远的固定点，而与支付矩阵无关。见下文。Conlisk[S2]在两个房间的实验中证明了这一假设：玩家在两个单独的房间里，需要在知道舞台游戏的结果之前进行多次对抗。布鲁姆菲尔德[S3]在一个实验装置中实现了这一想法。另一个重要的普遍观点是，我们检查收敛到固定点，但这些可能或可能不符合纳什均衡。例如，如果活动游戏收敛到固定点，则这是一个纳什均衡【S4】，但如上所述，记忆极短的EWA可能会收敛到任意远离纳什均衡的固定点。不幸的是，在有大量动作的游戏中，计算全套纳什均衡，然后检查与模拟固定点的距离在计算上是不可行的。在2×2博弈和EWA的特定情况下，具有足够长的记忆，固定点非常接近纳什均衡（例如，在10-6或更少）[S6]。由于EWA、带噪声的EWA、k级学习和强化学习的收敛频率与实际游戏和复制者动态（精确达到纳什均衡）非常相似（参见主要论文中的图2），我们认为固定点和纳什均衡之间缺乏完美对应不是主要问题。

如果说有什么区别的话，那么收敛到纳什均衡的可能性将更大，这加强了我们论文的主要信息。S1.1.1注释考虑一个2人N步标准形式游戏。我们按u对玩家进行索引∈ {行=R，列=C}和它们的移动由i，j=1。N、 设xui（t）为玩家u在时间t玩移动i的概率，即其混合策略向量的第i个分量。为了简单起见，我们还用xi（t）表示玩家R在时间t玩招式i的概率，用yj（t）表示玩家C在时间t玩招式j的概率。我们进一步用su（t）表示玩家u在时间t实际执行的移动，用su（t）表示-对手采取的行动。玩家u的支付矩阵是∏u，如果他玩move i，而另一个玩家选择move j，则∏u（i，j）作为支付矩阵。因此，如果玩家行玩策略i和玩家列玩策略j，他们分别会收到支付函数∏R（i，j）和∏C（j，i）。S1.1.2强化学习作为强化学习的一个例子，我们使用参考文献中的规范研究了Bush-Mosteller学习算法[S7]。【S8】和【S9】。这不是强化学习的唯一可能选择。例如，Erev和Roth提出了其他算法【S10】。我们关注Bush-Mosteller算法，因为它是与我们考虑的其他算法最不同的学习规则。在Bush-Mosteller版本的强化学习中，每个玩家都有一定程度的灵感，即他的贴现平均薪酬。这会让玩家对每一步都感到满意——如果玩家因选择这一步而获得的回报大于激励水平，则为正，否则为负。如果满意度为正，则重复某个动作的概率会增加，如果满意度为负，则会降低。正式定义更正式地说，让Au（t）为时间t时玩家u的期望水平。

Itevolves根据au（t+1）=（1- α） Au（t）+α∏u（su（t），s-u（t））。（S1）抽吸是在时间t∏u（su（t），s）时收到的付款的加权平均值-u（t）），和过去的吸入水平。因此，过去收到的付款按系数1贴现-α。此外，两种群复制子动力学的唯一稳定不动点是纯策略纳什均衡[S5]。相反，Erev Roth算法可被视为EWA的特例，见S1.1.5节。α表示记忆丧失率。满意度定义为σui（t）=∏u（i，s-u（t））- Au（t）最大值，j∏u（i，j）- Au（t）|。（S2）在时间t采取行动i后，如果玩家u收到的报酬高于他的期望，则他会有积极的满意度。请注意，α也被称为习惯化，因为玩家对动作i的重复选择u会导致期望水平与动作i的支付相对应。当玩家习惯化时，满意度将接近零。在式（S2）中，分母是将σ保持在-1和+1范围内的非均化因子。【S8】重新播放移动i的概率更新为asxui（t+1）=（xui（t）+βσui（t）（1- xui（t）），σui（t）>0，xui（t）+βσui（t）xui（t），σui（t）<0。（S3）在上述等式中，β是学习率。积极的满意度会导致可能性的增加（但习惯化会减缓并最终停止上升，因为习惯化会降低满意度），消极的满意度则会产生相反的效果。未执行的移动的概率将根据规范化条件进行更新。用j 6=i表示它们，我们有xuj（t+1）=xuj（t）- βσui（t）xuj（t），σui（t）>0，xuj（t）- βσui（t）xui（t）xuj（t）1-xui（t），σui（t）<0。（S4）到目前为止描述的学习算法是随机的。如前所述，我们希望采取确定性限制，即球员在更新混合策略之前，观察对手的大量动作样本。

我们假设样本足够大，因此可以用混合策略向量进行识别。为了简单起见，我们切换到表示xRi（t）的符号≡ xi（t）和xCj（t）≡ yj（t）。我们也只考虑玩家行，因为列的learningalgorithm是等价的。吸气更新asAR（t+1）=（1- α） AR（t）+αXi，jxi（t）∏R（i，j）yj（t）。（S5）计算以正概率进行的所有动作i的满意度：σRi（t）=Pijxi（t）yj（t）∏R（i，j）- AR（t）最大值，j∏R（i，j）- AR（t）|。（S6）最后，根据概率xi（t），更新混合策略向量的所有组件，就像它们被播放一样，或者就像它们没有被播放一样。更新规则是xi（t+1）=xi（t）+xi（t）xi（t）+Xj6=ixj（t）xij（t）。（S7）此处，xi（t）是玩家行选择移动i的贡献（发生概率为xi（t），因此为乘法项），以及xij（t）是由于选择了另一个移动j（即规范化更新）而对移动i作出的贡献，每个移动都以概率xj（t）发生。以下等式：。（S3）和（S4），我们有xi（t）=（βσRi（t）（1- xi（t）），σRi（t）>0，βσRi（t）xi（t），σRi（t）<0，（S8）0 500 1000 1500 20000.000.250.500.751.000 500 1000 1500 20001081061021000 500 1000 1500 20000.000.250.500.751.000 500 1000 1500 2000106102100txi（t）图S1：N=20的Bush-Mosteller强化学习算法的模拟运行实例。每一行都是行的混合策略向量的一个组件（并非所有组件都可见，因为它们重叠）。左侧面板：非收敛模拟运行。右面板：聚合模拟运行。顶部面板：线性比例。底部面板：垂直轴上的对数刻度。

仅显示5000个时间步长中的前2000个。和xij（t）=(-βσRj（t）xi（t），σRj（t）>0，-βσRj（t）xj（t）xi（t）1-xj（t），σRj（t）<0。（S9）收敛标准在图S1中，我们显示了收敛和非收敛模拟运行的实例。正如底部面板中的对数图所示，混合策略向量的任何组成部分都不会在模拟时间内达到固定点。原因很简单：Eqs。（S7）没有记忆丧失项，因此不成功策略的概率随着时间的推移不断降低。只有数值近似才会产生固定点，但在大多数参数设置下，Bush-Mosteller动力学需要很长时间才能达到机器精度边界。因此，我们选择一种简单的启发式方法来确定学习动态是否达到了一个固定点：1。只考虑最后20%的时间步。2、只保留使用频率大于1/N.3的动作。如果平均标准偏差（即最频繁移动的平均值）大于0.01，则将模拟运行确定为非收敛。否则，将其标识为收敛。我们用略有不同的规格进行试验，对结果没有显著影响。注意等式（S3）和等式（S9）之间的小符号杂波。在等式（S3）中，移动j是由于玩移动i而更新的。在等式（S9）中，移动i是由于玩移动j而更新的，概率为xj（t）。参数值如果抱负记忆损失α和/或学习率β非常小，则学习动态始终达到策略单纯形中心的固定点，而与支付矩阵无关。在这个固定点上，玩家只需在所有动作之间随机化。从某种意义上说，他们并没有从游戏中学习。

除了这种不切实际的情况外，我们没有观察到对参数值的太多敏感性。我们在α=0.2和β=0.5的情况下进行了模拟。我们通过迭代等式来模拟学习动态。（S7）5000个时间步。S1.1.3虚拟游戏虚拟游戏最初是作为计算游戏纳什均衡的算法提出的，后来被解释为学习算法【S11，S4】。这是信仰学习的一个例子。与强化学习不同的是，在强化学习中，玩家更新他们对对手可能采取的行动的信念，并对他们的信念做出反应。在实际游戏中，每个玩家都会根据对手的经验分布来估计自己的混合策略，根据这个信念计算出自己动作的预期收益，并选择能够最大化预期收益的动作。在这里，我们研究了标准的实战游戏算法，在该算法中，玩家平均权衡所有过去的动作，并确定选择表现最好的动作。变型包括【S12】加权实战，玩家对对手过去的动作进行折扣，对最近的动作给予更高的权重；随机实战，玩家以一定的概率选择表现最好的动作，并可能以较小的概率选择所有其他动作。我们将重点放在标准的实际播放算法上，因为其他版本只是EWA的特例（见S1.1.5节）。正式定义玩家行计算时间T时预期混合策略列的第j个分量，我们用▄yj（T）表示，简单地说，是过去j被显示的次数的分数：▄yj（T）=PTt=1I（j，sC（T））T.（S10）在上述等式中，I（a，b）是指示函数，I（a，b）=1，如果a=b，I（a，b）=0，如果a=b。

然后，玩家行选择在时间T，i（T）=argmaxkXj∏R（k，j）~yj（T）最大化预期收益的移动。（S11）柱的性能相当。收敛准则我们考察估计的混合策略向量在时间t、~xi（t）和~yj（t）上的收敛性。如图S2所示，游戏行为与Bush Mosteller dynamics非常相似。因此，我们使用相同的收敛标准。请注意，随着t的增加，更改预期策略需要越来越多的时间。在某种意义上，玩家的行为变得更加固定，因为他们需要更多的抽样证据来改变他们的期望。如果β太大，我们会遇到数值问题，因为学习动态超出了策略SimplexBounders。对于N=5，数值近似使动力学在2000个时间步后失去规范化。在这种情况下，我们只模拟2000个时间步。因为我们用随机系数来研究支付矩阵，所以几乎不可能两次移动产生相同的支付。如果是这样的话，通常玩家会以相同的概率在这些动作中进行选择。0 20000 400000.000.250.500.751.000 20000 400001041031021011000 20000 400000.000.250.500.751.000 20000 40000104103102101100txi（t）图S2：N=20的模拟游戏运行实例。每一行都是行的mixedstrategy向量的一个组件（并非所有组件都可见，因为它们重叠）。左面板：非收敛simulationrun。右面板：聚合模拟运行。顶部面板：线性比例。底部面板：垂直轴上的对数刻度。我们在这里展示了50000个时间步，尽管5000次迭代足以几乎同样准确地测量收敛率。参数值虚拟播放没有参数。我们只需要选择最大迭代次数，即5000次。

我们尝试了更长的时间序列（50000个时间步），但精度和速度之间的权衡是不利的。S1.1.4复制子动力学复制子动力学【S13】是进化博弈论中使用的标准工具【S14】。它是一个典型的模型，代表了群体中具有某些特征的个体的进化。每个性状的适合度取决于其他性状的群体份额和平均适合度。虽然复制子动力学主要用于种群生物学，但它也被作为博弈论中的一种学习算法进行研究。关键的联系在于思想的普及[S15]。每一步都可以被视为一个特征，每个特征的种群份额的演化对应于混合策略向量各组成部分的动态。复制因子动力学最典型的形式只涉及一个种群。如果支付矩阵是对称的，则可以将博弈视为焦点玩家与其他人群之间的博弈。然而，考虑到一般和随机确定的两人博弈，支付矩阵通常是不对称的。这自然会导致两种群复制动力学。两种群算法的动力学特性不同于单种群算法。就我们的目的而言，最重要的区别在于单种群复制子动力学通常收敛于混合策略纳什均衡，其中，两个种群复制因子动力学仅收敛于严格的纳什均衡（即纯策略均衡，其中均衡的收益严格大于对手不改变其招式时可获得的任何其他收益）[10]。0 500 1000 15000.00.20.40.60.81.00 500 1500 101521012510981071104410170 200 4000.00.20.40.60.81.00 200 400 10781064105010361022108TXI（t）图S3：N=20的复制器动力学模拟运行实例。

每一行都是行的混合策略向量的一个组件（并非所有组件都可见，因为它们重叠）。左侧面板：非收敛模拟运行。右面板：聚合模拟运行。顶部面板：线性比例。底部面板：垂直轴上的对数刻度。最大模拟时间（1500或500个时间步）由到达机器精度边界的混合策略向量的第一个分量内生确定。正式定义让xiand yjdenote分别与traitsi和j一起计算个体的种群份额，两个种群复制子动力学读数为˙xi（t）=xi（t）Xj∏R（i，j）yj（t）-Xkjxk（t）∏R（k，j）yj（t）,˙yj（t）=yj（t）Xi∏C（j，i）Xi（t）-Xikyk（t）∏C（k，i）xi（t）！。（S12）与相应群体中的平均能力相比，群体行中的特征i和群体列中的特征j的份额根据该特征的能力（如预期收益所示）而变化【37】。复制器动力学需要离散化以进行模拟。我们使用欧拉离散xi（t+1）=xi（t）+xi（t）δtXj∏R（i，j）yj（t）-Xkjxk（t）∏R（k，j）yj（t）,yj（t+1）=yj（t）+yj（t）δtXi∏C（j，i）xi（t）-Xikyk（t）∏C（k，i）xi（t）！，（S13）其中δt是积分步骤。收敛标准在图S3中，我们可以看到与模拟复制子动力学相关的技术问题。首先，因为只有严格的纳什均衡才是稳定的，所以所有稳定的固定点都位于概率单纯形的边界处，并且无法在模拟时间内达到。

其次，周期的周期随着时间的推移而增加（由于复制因子方程的有限记忆），甚至不稳定的动力学也会向概率单纯形的边缘漂移。第三，虽然在Bush-Mosteller强化学习和实战游戏的情况下，混合策略向量的组成部分的变化幅度相对较小，但复制子动力学（S12）的函数形式意味着指数变化。因此，只能在有限的置信时间间隔内可靠地模拟map（S13）：一旦一个组件xior YJ达到机器精度极限，我们就停止模拟运行。这种预防措施是必要的，因为如果动态是在一个周期之后进行的，则某个动作可能不会在很长的时间间隔内进行，其概率会随着时间的推移而降低。在某种程度上，玩家可以方便地再次选择该动作，因此概率将再次开始增加。但是，如果概率事先达到计算机的精度极限，它将被固定在零，错误地将模拟运行识别为已达到固定点。另一个问题涉及舍入近似，这意味着归一化可能会丢失。如果发生这种情况，我们将停止模拟运行并丢弃结果。对于我们选择的集成步骤，确认时间间隔的平均顺序为1000个时间步骤（但可以有很大的变化，如图S3所示）。我们可以使用与Bush-Mosteller动力学和实战游戏相同的收敛标准，但由于模拟时间短以及周期的形状（在线性范围内，动力学在一段时间内保持不变，然后突然变化），建议使用不同的启发式。