COMA

Counterfactual multi-agent policy gradients

许多现实世界的问题,如网络数据包路由和自治车辆的协调,自然被建模为协作多智能体系统。非常需要新的强化学习方法,能够有效地学习这些系统的分散策略。为此,我们提出了一种新的多代理行为者-批评者方法,称为counterfactual multi-agent(COMA)policy gradient。COMA使用集中评论家来评估Q-函数和分散的参与者,以优化代理的策略。 此外,为了应对多智能体信用分配的挑战,它使用了一个counterfactual baseline,即边缘化一个代理人的行为,同时保持其他代理人的行为不变。COMA还使用了一种批评表示,它可以在一次正向传递中有效地计算counterfactual baseline。我们使用具有显著部分可观测性的分散变量在测试平台StarCraft unit micromanagement上评估COMA。在这种情况下,COMA显著提高了与其他多代理参与者-批评者方法相比的平均性能,并且最佳性能代理与能够访问完整状态的最先进的集中式控制器竞争。

方法

对于多代理学习中,亟须能够有效学习分散策略的新RL方法。 在某些情况下,学习本身也可能需要分散。 然而,在许多情况下,学习可以在模拟器或实验室中进行,其中可以获得额外的状态信息,并且代理可以自由地进行通信。

另一个关键的挑战是多代理功绩分配:在合作制定中,联合行动通常只产生全局奖励,使得每个代理人难以推断自己对团队的贡献。 成功。 有时可以为每个代理设计个人奖励功能。然而,这些奖励通常不能在合作组织中获得,并且往往不能鼓励个体代理人为了更大的利益而牺牲。这通常会在具有挑战性的任务中大大阻碍多代理学习,即使相对较少的代理也是如此。

Independent Actor-Critic

将策略梯度应用于多个代理的最简单的方法是让每个代理与其自己的参与者和批评者从自己的行动观察历史中独立学习。这本质上是独立的Q学习背后的理念(Tan 1993),它可能是最受欢迎的多智能体学习算法,但是在Q学习中有演员评论。 因此,我们将此方法称为独立执行者 - 评论家(IAC)。

在我们的IAC实现中,我们通过在代理之间对参数进行锐化来加速学习,即,我们只学习一个所有代理使用的行为者和一个评论家。 代理可能仍然表现不同,因为它们接收不同的观察,包括特定于代理的ID,从而演变出不同的隐藏状态。

独立学习很简单,但是缺乏训练时的信息共享使得学习依赖于多个代理之间交互的协调策略变得困难,或者让单个代理评估其行为对团队回报的贡献变得困难。

Counterfactual Multi-Agent Policy Gradients

上面讨论的困难是因为,除了参数共享之外,IAC未能利用学习集中在我们的环境中的事实。在本节中,我们提出了一些事实上的多智能体(COMA)策略梯度,从而克服了这一局限。 COMA的三个主要思想是:1)批评者的集中化,2)使用反事实基线,3)使用批评表示,允许对基线进行有效评估。 本节的其余部分描述了这些想法。

centralised critic

在IAC中每个Actor使用自己的Critic,然而这个Critic仅见过它自己观察到的样本。所以,如图1(a)所示,COMA使用集中的一个Critic,这样Critic便可以拟合一个全局的真实的回报。于是Actor的梯度可以表示为

g=θπlogπ(uτta)(r+γV(st+1)V(st))g=\nabla_{\theta^{\pi}} \log \pi\left(u | \tau_{t}^{a}\right)\left(r+\gamma V\left(s_{t+1}\right)-V\left(s_{t}\right)\right)

然而,这种方法不能解决关键的信用分配问题。因为TD误差只考虑全局回报,所以为每个参与者计算的梯度并没有明确说明特定代理人的行为对全局报酬的贡献。由于其他代理可能正在探索,该代理的梯度变得非常嘈杂,尤其是当有许多代理时。

counterfactual baseline

所以COMA引入了一个counterfactual baseline,其核心思想是利用difference rewards(参考Wolpert and Tumer2002),即代理从一个shaped reward中学习

Da=r(s,u)r(s,(ua,ca))D^{a}=r(s, \mathbf{u})-r\left(s,\left(\mathbf{u}^{-a}, c^{a}\right)\right)

我们用粗体 u\mathbf{u} 表示所有代理联合动作,给定代理人 aa 以外的代理人动作用上标 a-a 表示。其中 cac^{a} 是a代理的默认动作,任何动作提升 DaD^{a} 的同时也会提升 r(s,u)r(s, \mathbf{u}) ,因为 r(s,(ua,ca)r\left(s,\left(\mathbf{u}^{-a}, c^{a}\right)\right. 与a的动作无关。

差分奖励是执行多代理信用分配的有效方式,但是,它们通常需要访问模拟器才能进行估算 r(s,(ua,ca))r\left(s,\left(\mathbf{u}^{-a}, c^{a}\right)\right) 。当模拟器已经用于学习时,差异奖励增加了必须进行的模拟的数量,因为每个代理的差异奖励需要单独的反事实模拟。

COMA的一个关键洞察力是,集中的批评可用于以避免这些问题的方式实现差异奖励。COMA学习了一个集中的评论家 Q(s,u)Q(s, \mathbf{u}) ,它估计了对联合行动 u\mathbf{u} 的Q值。对于每个代理人,我们可以计算一个优势函数,该函数将当前操作 uau^{a} 的Q值与比较反事实基线进行比较,同时固定其他代理的动作 ua\mathbf{u}^{-a}

Aa(s,u)=Q(s,u)uaπa(uaτa)Q(s,(ua,ua))A^{a}(s, \mathbf{u})=Q(s, \mathbf{u})-\sum_{u^{\prime a}} \pi^{a}\left(u^{\prime a} | \tau^{a}\right) Q\left(s,\left(\mathbf{u}^{-a}, u^{\prime a}\right)\right)

因此, Aa(s,ua)A^{a}\left(s, u^{a}\right) 为每个代理计算一个单独的基线,该基线使用集中的批评家来推理只有a的行为改变的反事实,直接从代理的经验中学习,而不是依赖额外的模拟、回报模型或用户设计的默认行为。

即使这样,在典型的表示中,这种网络的输出节点的数量将等于 Un|U|^{n} ,仍会使得训练很困难。为了解决这两个问题,COMA使用了一个评论家代表,可以有效地评估基线。 具体来说,其他代理的操作 ua\mathbf{u}^{-a} 作为网络输入的一部分,为每个代理a的动作输出Q值,如图1(c)。

以下引理确定了COMA与局部最优策略的收敛性:

证明请参考原论文

实验

作者在星际争霸2的微观操作上进行了实验(通常星际争霸2代理使用引擎自带的宏动作)