1. 引言
在社会和自然界中,人类及动物的本能就是利己主义的,每个理性的个体为了让自己的利益最大化,通常不会和其他个体采取合作的策略,这与现实世界中普遍存在的合作现象产生了矛盾[1] [2] [3] [4] [5]。演化博弈理论成为解决这一矛盾的有效方法,它为深入了解自私个体之间合作的涌现和演化提供了一个理论的基础和强有力的框架[6] [7]。
囚徒困境(PDG)作为演化博弈论中最典型的模型,被认为是研究自私个体之间群体合作行为出现的有力工具,它揭示了社会困境中个体和群体间利益冲突的本质,是研究合作行为的主要范式[8] [9] [10]。为了解释现实世界中合作行为的涌现,现有研究引入了各种促进合作的机制,比如收益矩阵的异质性[11]、奖励惩罚[12]、声誉偏好[13]等。个体收益分布情况也影响着合作的演化,文献[14]研究了空间囚徒困境博弈中不同分布的随机收益变化对合作演化的影响,发现高斯分布的收益变化在促进合作方面是最成功的,收益分布均匀性太强会阻碍合作。
演化博弈的基本三要素之一就是策略集合。常见的策略更新规则有模仿最优者[15]、无条件模仿[16]、费米规则[17]等。文献[18]结合PROPHET算法,引入了基于节点社会权威性的策略更新机制,研究了囚徒困境博弈模型上合作行为的涌现。目前多数研究中,个体更新策略的方式都是以一定的概率去模仿或学习邻居的行为来改进自己的策略。随着社会的发展,个人愈发关注自身信息隐私性,这导致在博弈过程中对邻居收益和策略信息的获取较为困难。此时,个体要做出有利于自己的行为决策只能依靠自身经验来做出决定。因此,结合强化学习的方法来研究网络博弈中个体的行为选择是有必要的。强化学习的独特之处在于智能体无需具有先验知识或大规模数据集的支持,在智能体与环境的交互中,它通过不断试错和接受来自环境的反馈信息——奖励值来逐步调整自己的行为,以最大化累积奖励。这使得强化学习具有自学习和在线学习的能力,是一种更贴近人类真实行为模式的学习算法。网络博弈具有不确定性和不完全信息的特点,而强化学习算法能够应对这一特点并制定出相应的策略。常见的强化学习算法有[19]:SARSA、瞬时差分方法和自适应启发评价算法等。SARSA算法(State-Action-Reward-State-Action)是一种基于模型的在线策略学习算法。在每个时间步,智能体根据当前状态下的值确定下一步的动作,使用值函数来更新算法迭代。
本文采用三种强化学习的SARSA算法决策机制在四种不同的网络拓扑结构上进行仿真模拟实验来探讨引入强化学习算法对网络节点合作演变的影响。
2. SARSA演化博弈模型
2.1. 演化博弈模型
利用Pycharm构建四种网络模型进行本文的实验仿真(随机网络、规则网络、无标度网络、小世界网络)。
构建好网络模型后,网络中的每个节点代表着参与博弈演化的理性个体。它们每次只能在背叛(D)或合作(C)这两种纯策略中选择其一,如式(1)的描述:
或
(1)
本文的演化博弈模型采用Nowak与May在1992年提出的弱囚徒困境博弈模型[20],并利用该文献中的参数设置来简化模型,令囚徒困境博弈模型中的参数
,
,对合作者的背叛的诱惑
。博弈收益矩阵定义如公式(2):
(2)
在每轮迭代中,参与者与其相邻的节点进行一轮囚徒困境游戏,其中个体的收益总和会受到收益矩阵的影响。具体而言,一个个体获得的总收益是通过与其所有邻居的互动后累积得到的,如公式(3)所示:
(3)
表示个体i的所有邻居集合,j为i的一个邻居。M表示收益矩阵。
在传统的囚徒困境模型中,参与者倾向于模仿上一次交互中获取最大收益的邻居策略,以此来提升自己未来的收益。但随着对信息隐私重视程度的提高,直接获取邻居的具体收益数据变得越来越困难,因此参与者需要依赖自身累积的经验,通过持续学习优化自己的策略选择。鉴于此,本文提出了一种基于SARSA算法的演化博弈PDG模型。
2.2. SARSA算法
SARSA算法是一种通过不断积累探索经验来提升决策能力的方法,无需建立环境模型并且可被在线使用。通过学习最优策略来处理不确定性信息和采取最佳动作来最大化累计奖励。该算法的这一特性非常适用于不完全信息博弈。
在SARSA算法中,
表示状态集合,
表示动作集合。在初始演化博
弈阶段,理性个体都以1/2的概率随机地选择背叛或合作。在后续演化过程中的任意时刻t,智能体通过
感知当前环境状态
,根据动作策略选择执行动作
到达下一状态
,同时获得奖励
,然后基于
更新Q表及优化策略,由此每个个体来进行下一轮的策略选择。更新公式为:
(4)
式中的
表示在状态
选择动作
的Q值;
表示在下一个状态
时选择下一步动作
并执行的Q值,即下一步的策略;
表示个体的学习率,控制着每轮游戏更新新信息时对旧Q值的影响权重;
表示折扣因子,是表示未来奖励重要性的参数;
代表个体在状态
执行动作
后从环境中获得的即时奖励,由公式(5)给出:
(5)
表示个体i的收益总和,n表示个体i的邻居数量,
用来调节个体收益均匀性。
3. 三种SARSA决策机制及对比
文章选择ε-greedy、Boltzmann和Max-plus三种不同的SARSA策略选择机制来进行对比实验。ε-greedy决策机制在每个时间步中,所有动作以固定概率ε进行随机探索,以
的概率选择当前最优策略,该机制简单直接,易于实现,但因为ε的固定值而限制了探索效率;Boltzmann决策机制在每个时间步根据动作的奖励值来确定被选择的概率,智能体对环境了解程度越深,最优动作被选择的概率越大;Max-plus决策机制具有考虑个体全局属性的优点,其通过不断地向邻居发送局部奖励函数且不需要知道邻居的所有动作,使算法更易于求解最优解,避免个体陷入局部最优解。
3.1. ε-Greedy决策机制
ε-greedy决策机制是SARSA算法基础的策略选择机制,它以一定的概率ε选择随机动作,以便探索环境(算法流程图见表1)。使用ε-greedy决策机制的SARSA算法(记为ES),按照公式(4),算法会生成状态–动作对的Q表,智能体在状态
时依照Q表基于ε-greedy决策机制以
的概率选择最优动作并执行,如下式所示:
(6)
表示状态
中具有最大Q值的动作,每轮游戏结束后,
替换成
。
Table 1. ES algorithm
表1. ES算法
输入:网络拓扑结构参数、SARSA算法相关参数 输出:网络节点合作水平值、节点收益值 |
1) 随机初始化个体状态s并令其
表格为0; 2) 使用ε-greedy策略选择动作a并执行; 3) 此后每个回合,个体i以固定概率ε进行随机探索或以
的概率选择当前最优策略与其邻居进行博弈;而个体i的邻居只根据其Q表来选择最优动作并执行;每次回合结束时,个体i及其邻居的行为共同决定了个体i应获得的奖励值; 4) 每个回合结束后个体i根据公式(4)更新
值,并在下一个回合中依据公式(6)选择策略; 5) 重复步骤3~4,直到动态系统达到稳定状态。 |
3.2 Boltzmann决策机制
与ε-greedy不同的是Boltzmann决策机制有一个平滑的概率分布,允许更好地控制探索与利用之间的平衡,算法流程见表2。使用Boltzmann决策机制作为SARSA算法的动作选择机制(记为BS),它在每个时间步以概率P选择使自己收益最大的策略,P的计算方法如下:
(7)
其中,
(8)
t是博弈的次数,λ是重复博弈次数t的函数。对每个动作a,计算一个概率分数,其与该动作的价值相关。然后,使用Softmax函数将这些分数转化为概率分布P,其中参数t控制了探索的程度,t越大,智能体决策的随机性越大。概率高的动作更有可能被选择,但仍有一定概率选择其他动作。Boltzmann决策机制结合SARSA算法具有自适应学习的能力。
Table 2. BS algorithm
表2. BS算法
输入:网络拓扑结构参数、SARSA算法相关参数 输出:网络节点合作水平值、节点收益值 |
1) 随机初始化个体状态s并令其
表格为0; 2) 使用Boltzmann策略选择动作a并执行; 3) 此后每个回合,个体i与其邻居进行博弈并以P的概率选择动作并执行,而个体i的邻居只根据其Q表来选择最优动作并执行;每个回合结束时,个体i及其邻居的行为共同决定了个体i应获得的奖励值; 4) 每个回合结束后个体i根据公式(4)更新
值,并在下一个回合中依据公式(6)选择策略; 5) 重复步骤3~4,直到动态系统达到稳定状态。 |
3.3 Max-Plus决策机制
Table 3. MS algorithm
表3. MS算法
输入:网络拓扑结构参数、SARSA算法相关参数 输出:网络节点合作水平值、节点收益值 |
1) 随机初始化个体状态s并令其
表格为0; 2) 使用Max-plus作为策略选择机制选择动作a并执行; 3) 此后每个回合,个体i以
的概率依据公式(11)选择最优策略
或以固定概率ε进行随机探索,而个体i的邻居在每个回合时依据其状态以公式(11)选择其最优动作
执行。每次博弈回合结束时,个体i及其邻居的行为共同决定了个体i应获得的奖励值; 4) 每个回合结束后个体i根据公式(4)更新
值,并在下一个回合中依据公式(12)选择策略; 5) 重复步骤3~4,直到动态系统达到稳定状态。 |
使用Max-plus决策机制作为SARSA算法的动作选择机制(记为MS)。Max-plus决策机制通过选择具有最高预期回报的动作来最大化价值函数。其在每个时间步骤中,根据当前状态的价值函数,考虑到个体的全局属性,使个体能够在没有全局信息的情况下找到全局最优解,具体算法流程见表3。该机制使两个相邻个体i和j根据局部最优动作
来更新策略。定义智能体i给邻居智能体j发送的消息为一个局部奖励函数,如式(9):
(9)
是邻居j发送给i的信息;
表示除个体j以外的i的其他所有邻居给其发的信息集合;
表示个体i最优动作的值函数,如公式(10):
(10)
表示网络中所有个体传出信息的平均值,如公式(11):
(11)
i的最优动作决策如式(12):
(12)
4. 仿真结果及分析
为对实验结果进行定量分析,引入
表示合作者的频率作为实验结果评估指标,即合作者节点数量除以网络中节点总数。显而易见,合作频率
介于0与1之间。
表示网络全由背叛者构成;
则表示所有节点均采取合作行为;本文探讨的四种网络模型包括无标度网络(BA网络)、随机网络(ER网络)、规则网络(RG网络)和小世界网络(WS网络),均基于有限节点
构建。RG是最简单的网络,网络中任意两点间的连接都遵循一样的规则;BA的分布服从幂律分布,具有网络增长和优先连接的特点,互联网、社会网络等都属于BA的一种;ER是一种节点机会都相同的网络模型,在现实中有很广泛的应用意义;WS具有较大的聚集系数和较小的特征路径长度,可以让陌生人通过一条较短的熟人链条联系起来;由此,这四个经典的网络模型被广泛用于复杂网络上演化博弈领域的研究,本文的仿真实验也以这四种网络模型为基础来验证算法提出的有效性。
在最开始的实验阶段,以合作者和背叛者的比例相同开始实验,分别在四个网络模型上进行仿真模拟。并以BA网络为代表,探究参数设置的改变分析引入的三种决策机制对合作行为的影响。
4.1. 实验结果
动态系统在1000个仿真步长后达到稳定状态,取稳定状态下的100次数据的平均值作为网络合作水平。总体上,引入强化学习能显著提升网络的整体合作水平,并且相对较快地达到一个稳定的合作状态,合作水平的波动范围较小且维持在一个较稳定的区间内。
,
,
,
BA Network.
Figure 1. Level of cooperation at different values ε (a)
(b)
图1. 不同ε值下的合作水平(a)
(b)
由图1可知,在复杂网络上的演化博弈中,引入强化学习算法后,无论哪种决策机制,均能提高复杂网络上个体间的合作水平。其中,ES-PDG是四种机制中实验效果最好的决策机制。ES-PDG的合作比例
几乎立刻就达到很高的水平,并且几乎在整个时间段内保持在0.9以上,这显示了一个高度稳定的合作状态。这是因为,较低的ε值能促使网络更快地达到稳定状态,较小的ε减小了策略选择的随机性,使得智能体有更大的可能性探索到最优策略,减短了网络达到稳定状态的时间。相反,较高的ε值使智能体表现出更强的“短视”,减少了对策略的深入探索,增加了达到稳定状态所需时间。传统的博弈(PDG)从较低的合作比例开始,并且随着时间的推移,合作比例持续下降,最终趋近于零,这表明在没有强化学习决策机制的情况下,自私或背叛策略占主导地位。当
时,使用ES算法的博弈网络(ES-PDG)在三种算法中合作水平最高。其次是使用BS算法的博弈网络(BS-PDG)和使用MS算法的博弈网络(MS-PDG),传统的囚徒困境博弈网络(PDG)合作水平最低。当ε值增大时,三种强化学习算法间的差异明显缩小,合作水平值在
时几乎相同,但也高于传统博弈模型。
4.2. 结果分析
4.2.1. SARSA算法对不同网络模型的合作水平影响
,
,
,
.
Figure 2. Level of cooperation under the four network structures (a) BA network; (b) ER network; (c) RG network; (d) WS network
图2. 四种网络结构下的合作水平(a) BA网络;(b) ER网络;(c) RG网络;(d) WS网络
实验结果如图2所示,无论在哪种拓扑结构上进行博弈演化,引入强化学习算法能够提高网络群体的合作者密度。实验使用了ES-PDG、BS-PDG和MS-PDG三种强化学习算法与传统的PDG进行对比仿真模拟。在不同的网络拓扑结构上引入不同的强化学习算法后均能提高网络的整体合作水平。其中,ES-PDG的合作水平最高,BS-PDG和MS-PDG次之,最后是传统PDG。在图2(a)、图2(c)和图2(d)中,MS-PDG模型的效果一直优于BS-PDG模型,但是图2(b)中,情况却反过来了。这是因为ER随机网络在节点之间会通过一定的概率P进行断边重连,Boltzmann决策机制有一个平滑的概率分布,在每个时间步以概率P选择使自己收益最大的策略,在网络断边重连的过程中,能增加使用Boltzmann决策机制个体间的合作概率,算法效果也超越Max-plus决策机制。此时,相较其他网络结构,在BA网络中的Boltzmann决策机制的效果优于其他三种网络。
即使是在异质性网络的背景下,使用了强化学习决策机制的算法依然可以很明显地提高整个网络的合作水平。因此,我们可以得出一个结论:这三种决策机制具有很好的鲁棒性,无论是何种网络拓扑结构,它都能够很显著地促进合作。
4.2.2. 背叛的诱惑b对网络合作水平的影响
参数b的大小直接影响个体的收益情况。对于不同的b,实验使用三种决策机制的SARSA算法与传统的博弈网络进行对比。由图3可知,随着b的增加,ES-PDG、BS-PDG和MS-PDG算法的合作水平随之增加且呈上下波动的变化趋势。其中,ES-PDG的波动幅度明显大于另外两种算法。而传统PDG的合作水平在短时间内随b的增加骤降到0,这说明强化学习算法的引入可以增加网络博弈中合作现象的产生和维持,对于背叛的诱惑具有更强的抵御能力。当博弈研究中使用的是传统的演化博弈模型时,如果想要合作团簇更好地的形成,最好将参数b的范围设置在1.1以下才会有比较理想的实验效果;在强化学习算法中,不同的决策机制最佳策略选择对应b的取值也不同。ε-greedy决策机制中,将参数b设置为1.2;Boltzmann决策机制里,设置
;Max-plus决策机制中,令
。
文献[21]研究了基于收益与愿望差异的策略与愿望调整意愿的协同演化以及外部环境的变化对空间囚徒困境博弈中合作演化的影响。结果表明,愿望持续时间对合作的增强作用在不同的背叛诱惑值b范围内是不同的。当b小于一定值时,存在一个可以促进合作的适当的愿望持续时间。此外,当b大于T-max (最大愿望持续时间)时,合作随着T-max的增加而逐渐增强,但增强效果有限。而本文在使用强化学习算法控制节点的策略行为后,无论背叛的诱惑值b的大小,群体合作水平仍能维持在稳定区间。
,
,
,
BA network.
Figure 3. Level of cooperation at different values b
图3. 不同b值下的合作水平
4.2.3. 不同强化学习参数对网络合作水平的影响
α表示个体的学习率,控制每次更新的权重,决定了新信息对旧Q值的影响程度。如图4所示,三种强化学习算法在不同的α值下的合作水平变化趋势大致相同,α位于中间值时,三种算法的合作水平大致一样且处于较好水平。MS-PDG对于不同的α取值的合作水平较其他两种算法更为敏感,变化幅度较大。ES-PDG和BS-PDG随α的变化,合作水平在0.6~0.7之间上下波动,较为稳定。在ES-PDG中,当
时,合作水平
随b的增加而明显下降;三种决策机制对于不同的α取值在网络上的合作率变化趋势整体相似:学习率越低,网络合作水平
越高。这是因为,低学习率使群体已经建立的合作关系更为稳定,个体不会因为一次背叛行为交互就迅速改变策略。在低学习率下,网络合作水平在b的较大范围内保持稳定。随着学习率的增加,合作水平对b的敏感性增加,尤其是当b较高时,这是因为当背叛的诱惑增加时,具有高学习率的个体更容易放弃合作策略。因此,在使用强化学习算法研究网络博弈时,为了提高网络合作水平,应设置较低的α值。
,
,
BA Network.
Figure 4. Level of network cooperation at different values α (a) ES-PDG, (b) BS-PDG, (c) MS-PDG
图4. 不同α值下的网络合作水平(a) ES-PDG,(b )BS-PDG,(c) MS-PDG
γ是确定个体在博弈中未来奖励重要性的折扣因子,控制在更新过程中考虑未来奖励的程度;由图5可以看出,网络合作水平
随折扣率γ的增加而越来越高。ES-PDG和BS-PDG的变化趋势最明显,MS-PDG的变化趋势最弱。当
时,个体严重折扣未来奖励值,偏爱即时收益。这可能导致群体较低的合作水平,因为个体不太关心自己行为的未来后果,使个体更倾向于为短期的利益而选择背叛策略;当
时,这时博弈者对未来奖励有了适度的评估考虑,此时,部分个体有一定的可能性会维持合作行为。但是,随着参数b的增大,即使个体在某种程度上重视未来奖励,如果即时回报足够诱人,他们可能仍然会选择背叛;当
时,博弈个体此刻很重视未来的奖励,因为他们考虑到长期的利益,个体间合作可能性进一步增大,这会导致群体更高合作水平的产生。即使随着背叛的诱惑b值的增大,合作水平
仍能维持在较高水平,这表明较高的γ值能抵御背叛的诱惑。
,
,
BA Network.
Figure 5. Level of network cooperation at different values γ (a) ES-PDG, (b) BS-PDG, (c) MS-PDG
图5. 不同γ值下的网络合作水平(a) ES-PDG,(b) BS-PDG,(c) MS-PDG
4.2.4. 收益异质性对网络合作水平的影响
图6表示随变量b和θ这两个参数同时变化时的合作水平
的变化情况。b是调节博弈收益矩阵中收益异质性的参数,
表示强化学习算法中调节个体收益均匀性的强化学习参数。从图6可以看出,引入强化学习算法后,无论使用何种策略选择机制,整体上都能提高网络节点的合作水平。其中在SARSA算法中引入ε-greedy决策机制对于网络合作水平的提升最为显著,能明显促进个体间的合作。Boltzmann决策机制效果优于Max-plus决策机制。随着b的变化,θ的值处于中间水平时(
)对应的网络合作水平最高。当
区间时,θ取中间值时的网络合作水平也高于其他取值情况。所以,适当地调节网络中个体间的收益均匀性可以有效地促进个体的合作,避免过高或者过低的θ取值。由此,我们可以知道在不同的决策机制中,最佳的
对取值区间:在ES-PDG中,参数b可取任意值,θ取值为0.5;在BS-PDG中,取
,
;在MS-PDG中,取
,
。
文献[22]在空间囚徒困境博弈中新引入了一种基于收益差异的通用概率奖励函数,其机制是每个玩家的收益差异性越大,无论对手的策略如何,给予对手奖励的概率就越高。该文章设计的奖励给予方式实现了合作的演化,尤其是在相对稀疏的规则网络和无标度网络中,也显着提高了合作者比例和所有玩家的平均收益。而在本文的研究中,我们将SARSA算法的决策机制引入到网络演化博弈中作为个体的策略更新方式,网络整体的合作水平与个体收益的异质性并不成正相关关系,调整个体收益均匀性至中等水平对群体合作行为的促进作用最为显著。
,
,
BA Network.
Figure 6. Effect of earnings heterogeneity on the level of network cooperation (a) ES-PDG, (b) BS-PDG, (c) MS-PDG
图6. 收益异质性对网络合作水平的影响(a) ES-PDG,(b) BS-PDG,(c) MS-PDG
4.2.5. 个体全局属性对收益的影响
由图7可以观察到ES-PDG的平均收益最高,BS-PDG和MS-PDG的平均收益次之。这意味着,当ε较小时,智能体倾向于利用已知的最优策略。当ε较大时,ES-PDG算法的平均收益下降。这表示在较高探索率下,即使是ES-PDG也在尝试新的、可能不太合作的策略,导致了整体收益水平的下降。MS-PDG算法因为其具有考虑全局属性的特性,能够做出基于全局考虑的最优策略选择。因此,在演化博弈的后期,超越ES-PDG算法,成为平均收益最高的强化学习决策机制算法。由此可以得出,不同的决策机制对探索率的敏感度不同。在较低的探索率时,可以使用ES-PDG算法促进网络维持较高的平均收益。在较高的探索率时,个体策略行为更加多变,应该考虑更多地使用具有全局属性特性的Max-plus决策机制来帮助个体做出最优策略选择。
,
,
BA Network.
Figure 7. Average payoff under the three decision-making mechanisms (a)
, (b)
图7. 三种决策机制下的平均收益(a)
,(b)
5. 结束语
本文将强化学习算法的决策机制与演化博弈中个体的策略更新步骤进行融合,深入地剖析了复杂网络中新算法的引入对合作行为演化带来的影响。通过对四种网络拓扑结构上的仿真实验,我们详细量化了SARSA算法对网络合作水平的影响。具体来说,引入SARSA算法后,网络合作水平平均提高了35%,并且这种提升效果在不同的网络拓扑结构中表现出一致性。例如,在无标度网络中,合作水平从引入算法前的45%提升至引入算法后的80%,稳定维持的区间范围为75%至85%。这表明SARSA算法不仅能显著提升网络中个体的合作水平,而且可以保持较高的合作稳定性。本研究的结果显示,SARSA算法在促进网络中个体合作行为的产生和维持方面具有显著优势。特别是,在低学习率与高折扣率的环境下,使用了ε-greedy决策机制算法的合作水平提高约40%和50%,以及在适当调节个体收益的条件下,合作行为的提升和稳定性更为显著。此外,我们还发现,在高探索率的情况下,考虑个体全局属性的Max−plus决策机制下的个体平均收益较其他两种决策机制提高约20%,能够更有效地引导个体做出适应性的合作策略,从而获得更高的平均收益。本文的主要创新点包括:1) 提出了一种基于SARSA算法的演化博弈模型,首次将其应用于网络博弈的研究中;2) 通过在四种网络拓扑结构上的仿真实验,验证了SARSA算法在不同网络环境下提升和维持合作水平的效果;3) 探讨了算法不同参数设置对合作水平的影响,为后续研究提供了理论基础和实证数据。这些创新和发现不仅为理解网络中的合作行为提供了新的理论视角,也为设计有效的促进网络合作的策略提供了有价值的参考。