有哪些好的网站制作公司,杭州有名的室内设计公司,个人备案公司网站,在建设局网站备案怎么弄Counterfactual Multi-Agent Policy Gradients
论文链接#xff1a;https://arxiv.org/pdf/1705.08926.pdf
1. 问题提出#xff08;解决了什么问题#xff1f;#xff09; 在现实世界中#xff0c;有非常多的问题需要多个单位之间的“合作”才能完成任务#xff0c;这就…Counterfactual Multi-Agent Policy Gradients
论文链接https://arxiv.org/pdf/1705.08926.pdf
1. 问题提出解决了什么问题 在现实世界中有非常多的问题需要多个单位之间的“合作”才能完成任务这就需要学习一种非中心式策略的控制系统即每个agent有着属于自己的决策大脑而非靠拥有全局信息的决策系统下达指令毕竟有时候全局的信息量过于庞大并且agent到中心网络的通信不一定每时每刻都稳定因此中心式的决策系统很难实现。因此该论文提出了一种方法用于学习非中心式的、部分可观测的多智能体协同的控制策略。COMA利用全局评价网络critic来评价Q值利用非全局行为网络actor来决定agent的行为。由于在训练时使用的是全局网络进行评价并且采用参数共享的方式使得agent能够在做行为选择的时候参考其他agent的状态再做决定这就加入了“协同”的功能。
2. 介绍
该论文分为以下三个部分
提出传统的RL算法在协同任务中不足
若使用传统的RL算法来解决多智能体的问题则会存在以下三个不足之处 输入的action space应该是所有agent的联合动作空间joint action space这个空间会随着agent数量增加而增加。此外由于部分可观测性即单个agent在某一时刻只能观测到部分环境的信息无法获得全局信息比如一个小兵只能看到视野范围内的地图信息视野外的地图信息是无法观测的使得agent在做决策时只能依照自己当前的部分观测信息local observation没有与其他agent进行信息共享的能力。使用联合动作空间获得的reward是来自所有agent采取的所有action共同得到的reward这就很难知道每一个agent的action应该得到的多少子回报这就是原文中提到的 “Individual Reward Assignment”。 COMA中的主要思想
COMA是一种基于actor-critic的变种方法其中actor是依照critic评估出来的梯度值进行更新学习的。整个算法共有三个比较核心的思想 学习过程中会有一个中心式评价网络, 这个网络主要用于对actor选择的决策进行好坏评价以此来教会actor如何做一个好的决策。为什么称为中心式的网络这是因为该网络可以获取场景中的全局信息包括所有agent在这一时刻采取的行为信息和观测信息。但是单个agent在利用actor做行为选择时只能依照自身的当前观测信息和经历过的历史信息进行决策做决策时是无法获得全局信息的。这种方式被称为“中心式评价边缘式决策”。COMA引入了一个概念叫做 “反事实准则(counterfactual baseline)” 这个概念是整篇论文的重点。为了解决 Individual Reward Assignment 的问题反事实准则提出每个agent应该拥有不同的reward这样才能知道在这一次的全局行为决策中单个agent的action贡献是多少。而单个agent的reward通过两个值计算得来当前情况下的全局reward和将该agent行为替换为一个默认行为后的全局reward。可以这样理解该回报值其实计算的是Agent aaa采取行为 uuu 会比采取默认行为 cac_aca 要更好DaD^aDa 0还是更坏DaD^aDa 0。这个特定agent下特定动作的reward就被称为counterfactual baselineCOMA使得每一个agent的每一个action都有一个自身的counterfactual baseline。如上面所说每一个agent的每一个动作都会有一个counterfactual baseline如果要计算出所有动作的baseline就需要把每一个行为替换成 ‘默认行为’ 并与环境互动得到一个reward。当agent数目很多且联合动作空间很大的时候这种方法显然是不可取的。因此COMA提出使用中心critic网络来estimate每一个动作的Q值来代替与环境交互后得到的reward。 验证场景及其结果分析
3. 背景
3.1 数学建模
论文中将多智能体协同任务想象成一个随机决策的游戏这个游戏 GGG 包含以下几个因素 GS,U,P,r,Z,O,n,γG S, U, P, r, Z, O, n, \gamma GS,U,P,r,Z,O,n,γ 其中 S→S \quad \rightarrow \quadS→ 环境状态集 ∀s∈S\forall s \in S∀s∈S. U→U \quad \rightarrow \quadU→ 所有动作样本空间在每一时刻每个agent采取一个行为 uta∈Uu_t^a \in Uuta∈U并组成联合动作空间 u∈U\textbf{u} \in Uu∈U. P→P \quad \rightarrow \quadP→ 状态转移函数根据当前状态sss和联合动作空间u\textbf{u}u计算一时刻状态s′ss′P(s′∣s,u)P(s|s, \textbf{u})P(s′∣s,u). r→r \quad \rightarrow \quadr→ 全局回报值r(s,u)r(s, \textbf{u})r(s,u). Z→Z \quad \rightarrow \quadZ→ 局部观测集单个agent在每一时刻有一个局部观测 z∈Zz \in Zz∈Z. O→O \quad \rightarrow \quadO→ 局部观测函数Agent aaa 的局部观测 zzz 是根据全局环境信息 sss 通过 OOO 函数计算得来zO(s,a)z O(s, a)zO(s,a). n→n \quad \rightarrow \quadn→ agent的个数共有 nnn 个. γ→\gamma \quad \rightarrow \quadγ→ 折扣因子用于指定计算未来回报时的衰减强弱.
此外每个agent有一个 action-observation 的历史记录 τa\tau^aτaactor在做决策的时候是基于历史信息做的决策 πa(ua∣τa)\pi^a(u^a|\tau^a)πa(ua∣τa). 其实这里基于历史记录做决策可以理解为之前在做update决策网络参数的时候是基于之前的历史信息做的更新所以用更新后的actor去做决策就可以看作是记住了历史经验后做的决策了。
3.2 基本概念回顾
这里在回顾一下DQN中的一些基本概念后续内容会用的到
累计回报 Rt∑l0∞γlrtlR_t \sum_{l0}^\infty{\gamma^lr_{tl}}Rt∑l0∞γlrtl其中 γ\gammaγ 是折扣因子评价函数分为两个对当前状态的评价函数 Vπ(st)V^\pi(s_t)Vπ(st)对当前状态下当前联合动作空间的评价函数 Qπ(st,ut)Q^\pi(s_t, u_t)Qπ(st,ut); Vπ(st)E[Rt∣st]Qπ(st,ut)E[Rt∣st,ut]V^\pi(s_t) E[R_t|s_t] \qquad Q^\pi(s_t, \textbf{u}_t) E[R_t|s_t, \textbf{u}_t] Vπ(st)E[Rt∣st]Qπ(st,ut)E[Rt∣st,ut] 优势函数 Aπ(st,ut)Qπ(st,ut)−Vπ(st)A^\pi(s_t, \textbf{u}_t) Q^\pi(s_t, \textbf{u}_t) - V^\pi(s_t)Aπ(st,ut)Qπ(st,ut)−Vπ(st).
Policy Gradient Value-Based中主要使用的更新方法——梯度上升法梯度 ggg 可以表示为 g∑t0TRt▽θπlogπ(ut∣st)g \sum_{t0}^TR_t\bigtriangledown_{\theta^\pi}log\pi(u_t|s_t) gt0∑TRt▽θπlogπ(ut∣st) 关于Actor-Critic模型 AC模型中actor是根据critic所求得的梯度来进行学习的。因为RtR_tRt是一个期望值无法求得精确的值因此需要用其他的表达式来近似替代RtR_tRt。替代RtR_tRt一共有两种方式
优势函数法使用 Q(st,ut)−b(st)Q(s_t, u_t) - b(s_t)Q(st,ut)−b(st) 来代替 RtR_tRt其中 bbb 为一个基准值用于保证所有action的Q值有正有负通常可以用 V(st)V(s_t)V(st) 来代替 bbb 值。也就是用 Qπ(st,ut)−Vπ(st)A(st,ut)Q^\pi(s_t, u_t) - V^\pi(s_t) A(s_t, u_t)Qπ(st,ut)−Vπ(st)A(st,ut) 来代替 RtR_tRt。TD法使用 rtγV(st1)−V(st)r_t \gamma V(s_{t1}) - V(s_t)rtγV(st1)−V(st) 来代替 RtR_tRt 。 如何训练中心评价网络critic 在这篇论文中作者训练了一个中心评价网络fc(⋅,θc)f^c(·, \theta^c)fc(⋅,θc)网络参数为 θc\theta^cθc使用一种稍微改变了下的TD法进行学习——TD(λ)TD(\lambda)TD(λ) 将nnn 步的reward值进行综合来得到一个平均值 Gt(n)∑l1nγl−1rtlγnfc(⋅tn,θc)G_t^{(n)} \sum_{l1}^n\gamma^{l-1}r_{tl} \gamma^nf^c(·_{tn}, \theta^c)Gt(n)∑l1nγl−1rtlγnfc(⋅tn,θc)。使用梯度下降的方法来更新网络参数θc\theta^cθcLtL_tLt表示ttt时刻的损失函数: Lt(θc)(y(λ)−fc(⋅t,θc))2L_t(\theta^c) (y^{(\lambda)} - f^c(_{·t}, \theta^c)) ^ 2 Lt(θc)(y(λ)−fc(⋅t,θc))2 其中 y(λ)(1−λ)∑n1∞λn−1Gt(n)Gt(n)∑l1nγl−1rtlγnfc(⋅tn,θc)y^{(\lambda)} (1-\lambda)\sum_{n1}^\infty \lambda^{n-1}G_t^{(n)} \\ G_t^{(n)} \sum_{l1}^n\gamma^{l-1}r_{tl} \gamma^nf^c(·_{tn}, \theta^c) y(λ)(1−λ)n1∑∞λn−1Gt(n)Gt(n)l1∑nγl−1rtlγnfc(⋅tn,θc)
因此整个公式也可以表示为 Lt(θc)((1−λ)∑n1∞λn−1(∑l1nγl−1rtlγnfc(⋅tn,θc))−fc(⋅t,θc))2L_t(\theta^c) ((1-\lambda)\sum_{n1}^\infty \lambda^{n-1}(\sum_{l1}^n\gamma^{l-1}r_{tl} \gamma^n {\color{red}f^c(·_{tn}, \theta^c)}) - f^c(·_{t}, \theta^c)) ^ 2 Lt(θc)((1−λ)n1∑∞λn−1(l1∑nγl−1rtlγnfc(⋅tn,θc))−fc(⋅t,θc))2
Note公式中一共有两个 fc(⋅,θc)f^c(·, \theta^c)fc(⋅,θc) 网络但是前一个fc()f^c()fc()是estimate出来的目标值 y(λ)y^{(\lambda)}y(λ)为了加快模型的收敛速度第一个的 fc()f^c()fc() 中的θc\theta^cθc 应该被fix住式子中的红色部分若干个steps后再被update这和target network的思路是一样的。 4. 算法分析
4.1 Independent Actor-Critic
IAC方法指每一个agent学习一个独立的actor-critic在这篇论文中采用参数共享的方法使得所有agent共用一个actor和一个critic。在学习的时候critic只能根据agent自身的local observation进行估计值并且也只能估计该agent的单个动作uau^aua的效用而不是联合动作空间u\textbf{u}u的效用。论文中对传统的IAC算法有两处改变:
在估计V值时每个 agent 的 critic 估计的是V(τa)V(\tau^a)V(τa)估计的是这个agent历史action-observation数据的效用值而不是传统的当前状态的效用值V(st)V(s_t)V(st)。VVV评价网络基于TD(λ)TD(\lambda)TD(λ)方法进行梯度更新见上面。在估计Q值时每个agent的critic估计的是Q(τa,ua)Q(\tau^a, u^a)Q(τa,ua), 也是基于action-observation的历史数据对当前行为uau^aua进行效用估计。QQQ评价网络是通过梯度下降优势函数A(τa,ua)A(\tau^a, u^a)A(τa,ua)来进行学习的其中优势函数的定义为单个动作产生的Q值减去所有动作产生的Q值即 A(τa,ua)Q(τa,ua)−V(τa)A(\tau^a, u^a) Q(\tau^a, u^a) - V(\tau^a)A(τa,ua)Q(τa,ua)−V(τa)。其中V(τa)V(\tau^a)V(τa)定义为在已知动作-观测历史数据下所有动作产生的效用总和即V(τa)∑uaπ(ua∣τa)Q(τa,ua)V(\tau^a) \sum_{u^a}\pi(u^a|\tau^a)Q(\tau^a, u^a)V(τa)∑uaπ(ua∣τa)Q(τa,ua)。
IAC的缺陷在于训练时只能依据单个agent的局部观测和单个action的效用评定这样很难学出一套好的协同策略。
4.2 Counterfatual Multi-Agent Policy Gradient
COMA的主要思想有三个中心式评价网络使用反事实准为每一个行为分配不同的reward值高效计算每一个不同的reward值下面对每一个思想进行介绍讲解。
Center critic
在IAC算法中训练评价网络时只用到了单个agent的history τa\tau^aτa。既然这个评价网络只会在训练的时候使用那么我们完全可以把全局状态 sss 输入用于训练若全局观测不可获得则将当前所有agent的action-observation的历史记录 τ\tauτ代替全局状态 sss如下图所示: 图中每一个Actor都会给出此刻的决策行为 utu_tut并且环境也会给出此时环境的全局信息 sts_tst 以及此刻的回报值 rtr_trt。
一种很简单的方式是直接使用TD-Error来进化这个网络 g▽θπlogπ(u∣τta)(rγV(st1)−V(st))g \bigtriangledown_{\theta_\pi}log\pi(u|\tau_t^a)(r\gamma V(s_{t1}) - V(s_t)) g▽θπlogπ(u∣τta)(rγV(st1)−V(st)) 但是这样的方法不能解决 Individual Reward Assignment 的问题因为TD算出来的Reward是一个全局Reward 无法推算出每一个action的单独Reward值。为此论文提出了反事实准则。
Counterfatual baseline
反事实准则Conuterfatual Baseline允许为不同的action独立分配一个不同的独立reward。这个独立reward DaD^aDa 需要根据当前情况下的全局reward和将该agent行为替换为一个默认行为后的全局reward两个值进行计算 Dar(s,u)−r(s,(u−a,ca))D^a r(s, \textbf{u}) - r(s, (\textbf{u}^{-a}, c_a)) Dar(s,u)−r(s,(u−a,ca)) 其中u−a\textbf{u}^{-a}u−a 代表联合动作空间除去当前Agent aaa 这一时刻采取的行为。(u−a,ca)(\textbf{u}^{-a}, c_a)(u−a,ca) 代表当前Agent aaa 采取默认行为 cac_aca 后所有Agent的联合动作空间。在学习过程中agent会想办法最大化回报值 DaD^aDa这其实就是在想办法最大化全局的reward r(s,u)r(s, \textbf{u})r(s,u)因为式子的后项跟agent当前采取什么行为是没有关系的。关于DaD^aDa这个式子可以这样理解回报值DaD^aDa其实计算的是Agent aaa采取行为 uuu 会比采取默认行为 cac_aca 要更好DaD^aDa 0还是更坏DaD^aDa 0。这个想法是正确的但是要想计算出每一个动作的DaD^aDa值就需要将每个动作都替换成默认行为cac_aca去与环境互动一次得到最终结果这样采样次数会非常多此外默认行为的选取也是无法预测的到底选择哪一个行为当作默认行为才是最合适的也是比较难决定的。因此文中提出使用函数拟合的方式来计算DaD^aDa。
前面提到中心评价网络可以评价一个联合动作空间 u\textbf{u}u 在一个状态 sss 下的 QQQ 值。由于默认行为很难定义于是我们把采取 “默认行为” 得到的效用值近似为采取一个Agent “所有可能行为” 的效用值总和。因此DaD^aDa 就可以用以下等式进行计算 Aa(s,u)Q(s,u)−∑ua′πa(u′a∣τa)Q(s,(u−a,u′a))A^a(s, \textbf{u}) Q(s, \textbf{u}) - \sum_{u_a}\pi^a(u^a|\tau^a)Q(s, (\textbf{u}^{-a}, u^a)) Aa(s,u)Q(s,u)−ua′∑πa(u′a∣τa)Q(s,(u−a,u′a)) 其中Aa(s,u)A^a(s, \textbf{u})Aa(s,u) 就是 DaD^aDa 的等效近似。
Efficient evaluation of baseline
尽管baseline的方式解决了独立回报的问题但是如果要建立一个网络接收s,us, \textbf{u}s,u两个输入输出为所有agent的所有action的话那么输出神经元的个数就等于 ∣U∣n|U|^n∣U∣nn个agent有|U|个动作。当agent数目很多或动作空间很大的时候就会造成输出层无法实现。为此COMA构造了一种网络该网络接收 ut−a,st,ota,a,ut−1−a\textbf{u}^{-a}_t, s_t, o_t^a, a, \textbf{u}^{-a}_{t-1}ut−a,st,ota,a,ut−1−a 等参数输出为Agent aaa 每一个action的Q-value值输出维度由 ∣U∣n|U|^n∣U∣n 降到了 ∣U∣|U|∣U∣ 如下图所示。 5. 实验
5.1 实验场景
该论文使用星际争霸游戏作为实验场景让算法控制的小队和游戏AI控制的小队进行对战并计算胜率。算法小队中每一个作战单位都由一个去中心式的controller进行控制。为了提升游戏难度比赛加入了 “部分可观测” 条件的限制视野范围等于攻击范围。这意味着当敌人没有进入攻击范围内时作战单位是不知道敌人位置信息的因此agent不仅要学会如何去探索敌方目标还需要与队友共享敌方目标的位置信息。为了证明加入 “部分可观测” 限制后问题变得有多复杂作者做了实验对比当不加入观测限制时普通的启发式算法能够到达98%的胜率加入限制后胜率降到了66%。
5.2 动作空间及回报值
每个agent都有着相同的动作空间{ move[direction]attack[enemy_id]stopnoop }。一次Episode下的全局Reward为对敌人造成的伤害 DeD_eDe 减去我方受到的伤害 DuD_uDu 除以2此外若击毁一个敌方单位获得10点的回报即 R(t)De−Du210nR(t) D_e - \frac{D_u}{2} 10n R(t)De−2Du10n 其中nnn为摧毁敌方单位数。若有一方将敌方团灭则获得的回报值为全队剩余血量200。
5.3 状态特征
算法一共有两个网络actor 和 critic。其中actor接收agent的局部观测信息critic接收全局状态信息。
局部观测信息
由于作战单位的视野范围等于攻击范围因此观测到的视野是以该单位为中心的一个圆。局部观测信息是指在视野圆圈内每一个单位包括敌方和友方的以下几个信息distancerelative xrelative yunit typeshield。其中 unit type 是指作战单位是何种兵种shield是为了模拟平A的冷却因为t切割的很小每一时刻Agent都有可能选择平A这个动作所以在平A还没有冷却好的时候敌方单位会套上一个无敌的盾来抵消这一次平A受到的伤害。疑问观测范围中的单位数量应该是随时间变化而变化的但网络的输入层神经元应该是固定的怎么解决变长的问题(未解决)
全局观测信息
全局观测信息包含了所有单位的relative xrelative yunit typeshieldhealthy pointcooldown信息其中 relative 的坐标信息是相对据地图中心的相对坐标不再是针对于某一个特定目标的坐标。
喂给独立回报计算网络Q-function critic用于计算单个动作独立回报的数据包括全局观测信息 被评估agent此刻局部观测信息。喂给中心评价网络center critic用于评估全局状态V(st)V(s_t)V(st)的数据包括全局观测信息 全部agent此刻局部观测信息。
5.4 实验结果
实验结果如下图所示其中3m5m分别指代一个作战小队中包含3个5个marine一种兵种2d_3z指代一个作战小队中包含2条龙和3个狂热者。
