增强协作多智能体强化学习中的全局信用分配机制

姚兴虎　 宋光鑫

摘 要：针对协作多智能体强化学习中的全局信用分配机制很难捕捉智能体之间的复杂协作关系及无法有效地处理非马尔可夫奖励信号的问题，提出了一种增强的协作多智能体强化学习中的全局信用分配机制。首先，设计了一种新的基于奖励高速路连接的全局信用分配结构，使得智能体在决策时能够考虑其所分得的局部奖励信号与团队的全局奖励信号;其次，通过融合多步奖励信号提出了一种能够适应非马尔可夫奖励的值函数估计方法。在星际争霸微操作实验平台上的多个复杂场景下的实验结果表明：所提方法不仅能够取得先进的性能，同时还能大大提高样本的利用率。

关键词：深度学习;强化学习;多智能体系统

中图分类号：TP181      文献标识码：A

Enhancing Global Credit Assignment Mechanism for Cooperative

Multi-Agent Reinforcement Learning

YAO Xing-hu1，SONG Guang-xin2

（1.College of Computer Science and Technology， Nanjing University

of Aeronautics and Astronautics， Nanjing， Jiangsu 211106， China;

2.College of Science， Nanjing University of Aeronautics and Astronautics， Nanjing， Jiangsu 211106， China）

Abstract：In order to solve the problem that the global credit assignment mechanism in cooperative multi-agent reinforcement learning is difficult to capture the complex cooperative relationship among agents and cannot effectively deal with non-Markov reward signals， an enhanced global credit assignment mechanism in cooperative multi-agent reinforcement learning is proposed. Firstly， a new global credit assignment structure based on reward highway connection is designed， which enables each agent to consider the local reward signal and the team's global reward signal when making decisions. Secondly， by integrating multi-step rewards， a new value function estimation method which can adapt to non-Markov rewards is proposed. The experimental results of several complex scenarios on the StarCraft multi-agent challenges show that the proposed method can not only achieve state-of-the-art performance， but also greatly improve the sample efficiency.

Key words：deep learning; reinforcement learning; multi-agent systems

現实世界中的很多问题都可以建模为多智能体强化学习问题。比如：多玩家电子游戏[1]，多无人车辆控制[2]，以及网络路由包的传输[3]。然而，完全合作的多智能体强化学习问题面临着两个主要的挑战：首先，智能体的联合动作空间随着智能体数量的增加，这使得直接利用单智能体算法进行联合建模会带来维数灾难;其次，当环境给出的奖励信号是针对所有智能体的全局奖励信号时，如何将这一全局奖励信号进行合理分配也是一个需要解决的问题。

对于上述问题，目前的主流方法是采用“中心训练-分散执行”的框架[4][5]。这类方法的核心是如何建立中心化值函数与非中心化值函数之间结构约束关系。值函数间约束关系的复杂程度直接影响了奖励分配机制的好坏。简单的约束关系不能够捕捉智能体之间的复杂协作关系，而复杂的值函数结构则会大大增加训练成本并降低样本的利用效率。

此外，环境给出的奖励信号往往具有很强的非马尔可夫性[6][7]。即当前状态下智能体采取动作后，环境会经过若干个时间步长的延迟才会给出针对这一动作的奖励信号，或奖励信号会在后续若干个时间步长持续给出。而在多智能体环境中，由于多个智能体之间的复杂交互以及环境的动态特性，这一非马尔可夫奖励现象则更为明显。

在“中心训练-分散执行”框架下，设计了一种新的全局信用分配结构并提出了一种更适宜处理非马尔可夫奖励的值函数估计方式。主要贡献如下：

1） 本文在“中心训练-分散执行”的框架下，设计了一种新的全局信用分配机制。利用Q值混合网络捕捉智能体之间复杂的约束关系，并引入奖励高速路连接，使得智能体在决策时能够同时考虑全局奖励信号与其所分得的局部奖励;

2）针对多智能体环境中的非马尔可夫奖励问题，提出了一种新的值函数估计方式。这一方式通过融合多步奖励信号的方式得到了一种基于λ回报的时间差分目标;

3）通过以上两个结构与基于深度Q学习的多智能体强化学习方法建立联系，得到了一种新的协作多智能体强化学习算法。这一算法具有更为高效的全局奖励分配机制并能很好的处理非马尔可夫奖励。在星际争霸微操作平台上的多个复杂场景下的实验结果表明，所提出的新算法不仅能够取得先进的性能，并且还能大大提高样本的利用率。

1 背景知识

1.1 问题定义

完全合作的多智能体强化学习问题可以被建模为部分可观测马尔可夫决策过程。具体来说，这一任务可以由七元组G=（S，A，P，r，Z，O，N，γ）来描述[8]。其中，s∈S表示环境真正的状态， A表示每个智能体的动作空间，P（s'|s，a）：S×AN×S→[0，1]表示状态转移概率，rs，a：S×AN→R表示全局奖励函数，智能体的数量为N。考虑一个部分可观测问题，在每个时刻，每个智能体i只能通过部分观测函数Zs，i：S×N→O得到关于环境的部分信息oi∈O，γ∈[0，1]是奖励折扣因子。在Dec-POMDP上的一个随机策略可定义为映射πa|o：O×A→0，1。多智能体强化学习任务的最终目标是为了最大化从环境中获得的累积奖励，即：

Es∈S，a∈π∑SymboleB@t=0γtrs，a（1）

其中，a，π分别表示智能体的联合动作和联合策略。

1.2 “中心训练-分散执行”算法

近年来，“中心训练-分散执行（central training with decentralized execution， CTDE）”框架由于概念简单且优化高效，成为求解Dec-POMDP的一类主流方法[4][5]。所谓“中心训练”指的是在训练阶段通过维护一个中心化的值函数或者中心化的“评论家（critic）”来对所有智能体的行为进行协调;所谓“分散执行”，指的是每个智能体在执行阶段，其策略仅依赖于其所观测得到的部分信息。

在CTDE算法中，中心化值函数Qπtot与非中心化值函数Qi之间的约束关系直接决定了算法的泛化能力和优化代价。常见的约束关系为：每个智能体单独按照各自的值函数进行决策，得到的局部最优动作的联合即为全局的最优动作，因此在执行阶段每个智能体可以按照自己的值函数进行动作的选择。

在这一假设下的主流算法包括：值分解网络[9]（value decomposition network， VDN），单调值分解网络[5]（QMIX）和Q值变换网络[10]（QTRAN）。VDN算法假设所有智能体的联合值函数Qπtot=∑Ni=1Qi;QMIX算法则假设对每个智能体i都有单调约束关系QtotQi≥0成立;QTRAN则通过对Q值进行变换构造更为复杂的约束关系。

1.3 环境的非马尔可夫奖励问题

在马尔可夫决策过程中，环境所给出的奖励信号满足马尔可夫性质，即奖励信号rt仅依赖于最近的一个状态以及智能体所采取的动作。然而，许多强化学习场景中的奖励信号并不满足这一性质，比如：在足球游戏中，进球所获得的奖励信号是对之前一段时间的状态和动作的延迟奖励;多智能体对抗问题下，摧毁敌方设施后，接下来的一段时间环境会针对当前动作给出持续的奖励信号。

因此，考虑设计更适合处理非马尔可夫奖励的多智能体算法有助于对全局奖励信号进行更为合理的分配并提高多智能体算法的性能。

2 所提算法

2.1 基于奖励高速路连接的全局信用分配机制

随着深度网络隐藏层数量的增多，网络的训练难度会不断变大。为了解决由于网络层数的增多所导致的退化问题，深度残差网络[11]针对输入数据x深度残差学习不再显式地去拟合所希望的潜在映射Hx，而利用非线性映射拟合另一个映射Fx=Hx-x。高速路网络[12]则通过门结构对数据时直接通过高速路传输还是经过神经网络变换进行控制。这两个方法实现方式简单并能大大降低深度网络的训练难度。

受深度残差网络[11]和高速路网络[12]启发，通过在奖励分配网络中引入高速路结构来在不增加算法优化代价的同时进行更为灵活的全局奖励分配。具体来说，提出的奖励高速路连接能够使得每个智能体的值函数估计过程中能够接触到部分的全局奖励信号，并与原有的全局信用分配机制相结合。这样每个智能体在决策过程中能够同时考虑其自身所分得得局部奖励和整个团队的全局奖励。

2.2 融合多步奖励的值函数估计方式

时间差分（temporaldifference， TD）算法[13]是对动作值函数进行估计的通用算法，使用TD算法对中心化值函数Qtotτ，a进行估计的一般形式如下所示：

Qtotτt，at←Qtotτt，at+δt，（2）

其中δt被稱为时间差分误差项（TD-error），当采用单步TD算法对中心化的值函数进行估计时，其TD-error项如下所示：

δπt=Eπrt+1+γQτt+1，·-Qτt，at.（3）

这种基于单步TD算法的值函数估计方式被广泛应于在多智能体强化学习问题的中心化值函数估计上[5][9][10]。然而，当环境给出的奖励信号具有很强的非马尔可夫性时，这种估计方式会带来很大的估计偏差。所提算法采用一种变种的TD（λ）[13]方法作为中心化值函数的估计方式。具体来说，采用如下的时间差分误差项Gλt作为中心化值函数的估计方式：

Gλt=1-λ∑SymboleB@n=1λn-1Gnt，（4）

其中Gnt=rt+1+γrt+2+…+γnEπQtotτt+n，at+n。

2.3 优化目标与网络架构

基于上述分析，提出一种基于奖励高速路连接与融合多步奖励的协作多智能体强化学习算法。该算法以QMIX算法为基本框架，在奖励分配网络中引入奖励高速路连接并在估计中心化值函数的过程中采用了融合多步回报的值函数估计方式。具体来说，所提算法可利用基于梯度的优化算法端到端地最小化如下的损失函数：

Lθ=1-αGλt-Qtotτ，a，s;θ，φ2+α∑Ni=1Gλt-Qiτi，ai，θi2（5）

其中Gλt的定义如（4）所示，而α则是控制Gλt流向混合网络和奖励高速路连接比例的超参数，θ=θ1，θ2，…，θN为所有智能体非中心化值网络的参数集合，φ是中心化结构额外的参数。

所提算法的结构框架如图1所示：每个智能体的非中心化的值函数网络的输入为当前智能体的观测值和上一个时刻的动作值，之后传入全连接网络进行特征变换，变换后的信息传入GRU模块与历史信息进行融合，之后利用一层全连接网络得到所有当前智能体i的所有动作的Q值向量Qiτi，·，然后采用∈贪心算法进行策略的选择。奖励分配网络以每个智能体所采取动作的Q值Qiτi，ai为输入，然后将经过多层非线性变换和奖励高速路连接得到的两个数据流进行融合得到全局的动作值Qtotτ，a。其中，奖励分配网络中对Q值进行非线性变换的参数是由以全局状态st为输入的超网络[15]所生成的。

3 实验与结果分析

3.1 数据集和实现细节

在星际争霸微操作平台[16]上进行实验，选择该实验平台主要基于以下两个目的：（1） 所提供的星际争霸环境中仅有针对所有智能体的全局奖励信号，因此很适合研究全局奖励分配问题;（2）星际争霸中的奖励信号具有很强的非马尔可夫性。其中的智能体角色代表如图2所示，图中左方为3个潜行者（Stalker），右边为5个狂热者（Zealot）。为了充分探究各种算法的鲁棒性与样本有效性，选取了实验平台所提供的一个非对称场景（asymmetric）（a） 2s_vs_1sc（控制同种类的2个智能体）， 和三个复杂的齐次对称场景（heterogeneous & symmetric）（b） 3s5z（控制两个种类的8个智能体）， （c） 1c3s5z（控制三个种类的9个智能体）， （d） 3s6z（控制两个种类的9个智能体）进行了实验。

智能体的非中心化网络部分包括一个维度为64维的全连接网络，全连接网络的输出被传入一个GRU[17]模块用来整合历史信息，之后连接一个维度为64的全连接层，激活函数为ReLU[18]，最后输出所有动作的Q值。中心化结构部分引入了奖励高速路连接来降低网络的学习难度，与QMIX的结构相同，中心化的网络结构同样利用超网络来产生混合网络的参数。表达式（4）中的参数λ=0.8，损失函数（5）中的超参数α=0.2。实验中的所有算法均采用同样的超参数，优化器均为RMSprop，其中学习速率lr=0.0005。

3.2 实验结果分析

将所提出的算法与当前在这一平台上的五种先进算法QTRAN[10]，QMIX[5]，VDN[9]，COMA[4]和IQL[14]进行对比。为保证公平性，所有算法在2s_vs_1sc和1c3s5z两个场景中训练两百万个时间步长，在3s5z和3s6z上训练三百万个时间步长。我们采用在训练过程中的测试胜率以及每局游戏中所获得的累积奖励值来进行算法的性能评估。所提算法与对比算法的性能比较结果如图3和图4 所示。图中实线和阴影区域表示独立运行10次算法所得的胜率均值和保留了95%置信区间的方差。

图3的实验结果表明，所提出的方法在多个复杂场景下能够取得最优的性能。具体来说，在针对智能体数量较少的2s_vs_1sc场景，所提算法能够取得有竞争力的结果。但随着智能体数量的不断增加，场景越来越复杂，从而使得已有的算法性能急剧下降且具有很大的偏差，而所提算法在能够取得优异性能的同时还具有很低的偏差。此外，图3实验结果同样表明，更为复杂的奖励分配结构不一定能够带来算法性能上的提升。事实上，具有较为复杂奖励分配结构的COMA算法和QTRAN算法在复杂的3s5z，3s6z以及1c3s5z场景下并没有优势，而所提算法所采用的奖励高速路结构并没有带来额外的优化代价，因此并不会增加算法的复杂度，从而能够灵活扩展到更为复杂的多智能体环境。

图4的实验结果表明，所提出的算法有助于智能体在决策过程中获得更多的累积奖励。并且在环境变得越来越复杂时，其他先进的算法所获得的累积奖励剧烈减少，而所提算法在面临复杂环境时仍能获得较多的累积奖励值。这意味着采用融合多步奖励的值函数估计方式和奖励高速路结构能够使得智能体的策略更适合复杂环境下的非馬尔可夫奖励。

图3和图4中的阴影面积大小可以作为算法稳定性优劣的一种衡量方式。可以看出，在2s_vs_1sc这一较为简单的场景下，所有算法的性能方差并没有显著差异。而随着智能体数量和种类的增多，基准算法的性能波动明显，尤其是在具有8个智能体的3s5z环境以及9个智能体的1c3s5z环境，QMIX算法的性能方差不断增大。而所提出的方法则具有很好的稳定性。

4 结 论

针对深度多智能体强化学习中的全局奖励分配问题，首先设计了一种高效进行奖励分配的奖励高速路连接结构;其次提出了一种融合多步奖励的方式来处理多智能体环境中全局奖励的非马尔可夫性所带来的问题。在多个复杂多智能体场景下的实验结果表明，所提算法能够取得性能提升，并且还具有很好稳定性。

參考文献

[1]

VINYALS O， BABUSCHKIN I， CZARNECKI W M， et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning[J]. Nature， 2019， 575（7782）： 350-354.

[2] KIUMARSI B， VAMVOUDAKIS K G， MODARES H， et al. Optimal and autonomous control using reinforcement learning： A survey[J]. IEEE Transactions on Neural Networks and Learning Systems， 2017， 29（6）： 2042-2062.

[3] YE Da-yong， ZHANG Min-jie， YANG Yun. A multi-agent framework for packet routing in wireless sensor networks [J].Sensors， 2015， 15（5）： 10026-10047.

[4] FOERSTER J N， FARQUHAR G， AFOURAS T， et al. Counterfactual multi-agent policy gradients [C].AAAI Conference on Artificial Intelligence， 2018：2974-2982

[5] RASHID T， SAMVELYAN M， DE WITT C S， et al. Qmix： monotonic value function factorisation for deep multi-agent reinforcement learning [C]. International Conference on Machine Learning， 2018： 4292-4301.

[6] THIBAUX S， GRETTON C， SLANEY J， et al. Decision-theoretic planning with non-Markovian rewards[J]. Journal of Artificial Intelligence Research， 2006， 25： 17-74.

[7] GAON M， BRAFMAN R. Reinforcement  learning with non-Markovian rewards[C]. AAAI Conference on Artificial Intelligence， 2020， 34（04）： 3980-3987.

[8] OLIEHOEK F A， AMATO C. A concise introduction to decentralized POMDPs[M]. Springer International Publishing， 2016.

[9] SUNEHAG G， LEVER A， GRUSLY S， et al. Value-decomposition networks for cooperative multi-agent learning based on team reward [C]. International Conference on AutonomousAgents and Multi Agent Systems， 2018： 2085-2087.

[10]SONK Yung-hwan， KIM Dae-woo， KANG Wan-ju， et al. Qtran： learning to factorize with transformation for cooperative multi-agent reinforcement learning [C]， International Conference on Machine Learning，2019： 5887-5896.

[11]HE Kai-ming， ZHANG Xiang-yu， REN Shao-qing， et al. Deep residual learning for image recognition [C]. IEEE Conference on Computer Vision and Pattern Recognition， 2016：770-778

[12]SRIVASTAV A， RUPESH K， KLAUS G， et al. Training very deep networks [C]. Advances in Neural Information Processing Systems， 2015：2377-2385

[13]SUTTON R S， BARTO A G. Reinforcement learning： An introduction[M]. MIT Press， 2018.

[14]TAN Ming. Multi-agent reinforcement learning： independent vs. cooperative agents [C]. International Conference on Machine Learning， 1993：330–337.

[15]HA D， DAI A， LE Q V. Hypernetworks[J]. arXiv preprint arXiv：1609.09106， 2016.

[16]SAMVELYAN M， RASHID T， SCHROEDER C， et al. The StarCraft multi-agent challenge[C]. International Conference on Autonomous Agents and MultiAgent Systems. 2019： 2186-2188.

[17]CHUNG Jun-young，GULCEHREC， CHO K， et al.Empirical evaluation of gated recurrent neural networks on sequence modeling[C].In Advances in Neural Information Processing Systems， 2014.

[18]AGARAP A F. Deep learning using rectified linear units （relu）[J]. arXiv preprint arXiv：1803.08375， 2018.