| 多代理强化学习MARL（MADDPG，Minimax | 您所在的位置：网站首页 › maddpg伪代码 › 多代理强化学习MARL（MADDPG，Minimax |
多代理强化学习MARL（MADDPG，Minimax
|
博弈论（game theory） 在单个agent中只需要考虑到自己，把自己优化的最好就可以了，但是涉及到Multi-Agent，研究多个代理之间的关系以提升整体效果或者完成多agent的目标任务时，首当其冲需要参考博弈论的成果。 博弈论是数学的一个分支，也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用，研究具有斗争或竞争性质现象的数学理论和方法，考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。不仅在多代理强化学习中，在深度学习，生成对抗都有应用，主要是用来模拟在有预定规则和结果的情况下不同参与者（agent）的策略互动。 一般根据游戏类型主要可以分为： 合作vs非合作：即人多力量大，合作状态下尝试建立一个联盟共同赢得游戏。对称vs非对称：对称游戏所有人的目标相同。完美信息vs非完美信息：能看到所有人的举动（象棋vs德州扑克）同时vs顺序：同时行动还是顺序的比如棋盘游戏零和vs非零和：零和中一个玩家的获利一定意味着其他玩家的损失。纳什均衡(Nash Equilibrium) 即在一策略组合中，所有的参与者面临这样一种情况，当其他人不改变策略时，他此时的策略是最好的。此时的状况既不是基于个人的利益，也不是基于整体的效果，但是在概率上是最容易产生的结果，所以在多代理的环境下，是很容易收敛到纳什均衡状态的。比如博弈论中经典的囚徒困境（prisoner’s dilemma）： 假设有两个小偷A和B联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是:如果两个犯罪嫌疑人都坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪，各被判刑8年;如果只有一个犯罪嫌疑人坦白，另一个人没有坦白而是抵赖，则以妨碍公务罪(因已有证据表明其有罪)再加刑2年，而坦白者有功被减刑8年，立即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱1年。 坦白抵赖坦白8，80，10抵赖10，01，1虽然看起来如果两个合作的话（即两个人抵赖）是最好的结果，但是实际上对某一个人A来说，尽管他不知道B作何选择，但他知道无论B选择什么，他选择"坦白"总是最优的。显然，根据对称性，B也会选择"坦白"，结果是两人都被判刑8年。所以此时如果直接两个采用普通的RL的做法，它们都最大化自己的累积收益，最终应该收敛到 坦白-坦白，即纳什均衡，但此时对自身与整体的来说都不是一个很好的结果。这种情况在这种“对称游戏”中更容易达到。 MARL（Multi-Agent Reinforcement Learning） 这就使得在multi-agent下，探索的随机性以外，还存在这样的困惑，即不知道对方的选择，以及两者的选择是否能够得到最佳的效果。为了解决这样的困惑： 以促进agent间合作的解决MARL的问题分为两条路： modelling other agents in system。单代理的扩展，尝试用多个agent去共同决策其他agent的action； communication for coordination。既然不确定其他代理的选择，那么就通过信息交换，去促进agent间的合作。 以相互竞争为纲，最终完成共同进步的思路：类似GAN，这些算法往往会使用minimax的思想，比如minimax Q-learning。另外还有纳什均衡也不错的思路，毕竟类似囚徒困境的博弈太少了，网络收敛到纳什均衡的结果也能接受，代表算法就是Nash-Q。MADDPG（Multi-Agent Deep Deterministic Policy Gradient） MADDPG属于合作类别的思路，实现是流行的MARL以集中式训练，分布式执行的思想。 集中式训练：每个agent不仅仅根据自身的情况，还根据其他智能体的行为来评估当前动作的价值分布式执行：当agent都训练完成后，每个agent就可以自己根据状态采取合适的动作，此时不需要其他agent的参与 大致的训练上与DDPG很相似，只是在输入Critic时不仅仅是自己的[s,a]了，还有其他agent的信息，进行共同更新训练。
#会输入所有agent的action信息
def critic_network(name, action_input, reuse=False):
with tf.variable_scope(name) as scope:
if reuse:
scope.reuse_variables()
x = state_input
x = tf.layers.dense(x, 64)
if self.layer_norm:
x = tc.layers.layer_norm(x, center=True, scale=True)
x = tf.nn.relu(x)
x = tf.concat([x, action_input], axis=-1)
x = tf.layers.dense(x, 64)
if self.layer_norm:
x = tc.layers.layer_norm(x, center=True, scale=True)
x = tf.nn.relu(x)
x = tf.layers.dense(x, 1, kernel_initializer=tf.random_uniform_initializer(minval=-3e-3, maxval=3e-3))
return x
详细细节可以参拜原文paper：https://arxiv.org/pdf/1706.02275.pdf 目前communication工作开始聚焦于limited communication，或者decentralized training。 Minimax-Q 主要应用于两个玩家的零和随机博弈中，需要优化的对象就是 V ∗ ( s ) = m a x π m i n a − ∑ a Q ∗ ( s , a , a − ) π ( s , a ) V^*(s)=max_{\pi} min_{a^-} \sum_a Q^*(s,a,a^-)\pi(s,a) V∗(s)=maxπmina−a∑Q∗(s,a,a−)π(s,a) –是代表竞争对手， Q ∗ Q^* Q∗是联合动作值函数。即在当前agent在状态s时，执行动作a到下一个状态s‘，在更新Q时，会观察对手在同样的状态s下的动作 a − a^- a−，再借鉴Q-Learning中的TD方法来更新。 def getReward(self, initialState, finalState, actions, reward, restrictActions=None): if not self.learning: return actionA, actionB = actions self.Q[initialState, actionA, actionB] = (1 - self.alpha) * self.Q[initialState, actionA, actionB] + \ self.alpha * (reward + self.gamma * self.V[finalState]) # EQUIVALENT TO : min(np.sum(self.Q[initialState].T * self.pi[initialState], axis=1)) self.V[initialState] = self.updatePolicy(initialState) self.alpha *= self.decay def updatePolicy(self, state, retry=False): #建立table c = np.zeros(self.numActionsA + 1) c[0] = -1 A_ub = np.ones((self.numActionsB, self.numActionsA + 1)) A_ub[:, 1:] = -self.Q[state].T b_ub = np.zeros(self.numActionsB) A_eq = np.ones((1, self.numActionsA + 1)) A_eq[0, 0] = 0 b_eq = [1] bounds = ((None, None),) + ((0, 1),) * self.numActionsA #纳什均衡问题使用线性规划求解 res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds) if res.success: self.pi[state] = res.x[1:] elif not retry: return self.updatePolicy(state, retry=True) else: print("Alert : %s" % res.message) return self.V[state] return res.x[0]Nash Q-Learning 目标是能收敛到纳什均衡点，即在每一个状态s的阶段博弈中，都能够找到一个全局最优点或者鞍点。纳什均衡一般使用线性规划求解，即对于 R 1 = [ [ r 11 , r 12 ] [ r 21 , r 22 ] ] R 2 = − R 1 R_1=[[r_{11},r_{12}][r_{21},r_{22}]]\\R_2=-R_1 R1=[[r11,r12][r21,r22]]R2=−R1可以得到其中某一个agent的线性规划： m a x p 1 , p 2 V 1 r 11 p 1 + r 21 p 2 > = V 1 r 12 p 1 + r 22 p 2 > = V 1 p 1 + p 2 = 1 p j > = 0 , j = 1 , 2 max_{p_1,p_2} V_1 \\ r_{11}p_1+r_{21}p_2>=V_1\\ r_{12}p_1+r_{22}p_2>=V_1\\ p_1+p_2=1\\ p_j>=0,j=1,2 maxp1,p2V1r11p1+r21p2>=V1r12p1+r22p2>=V1p1+p2=1pj>=0,j=1,2 其中p表示选择动作的概率。整个线性规划看起来就是在类似囚徒困境的表中，对每个agent尝试找到最好的策略。 #利用对手的action计算Q def compute_q(self, state, reward, opponent_action, q): if (self.previous_action, opponent_action) not in q[state].keys(): q[state][(self.previous_action, opponent_action)] = 0.0 q_old = q[state][(self.previous_action, opponent_action)] #更新Q值 updated_q = q_old + (self.alpha * (reward+ self.gamma*self.nashq[state]- q_old)) def compute_nashq(self, state): nashq = 0 #遍历nash表 for action1 in self.actions: for action2 in self.actions: nashq += self.pi[state][action1]*self.pi_o[state][action2] * self.q[state][(action1, action2)] |
由于强化学习领域目前还有很多的问题，如数据利用率，收敛，调参玄学等，对于单个Agent的训练就已经很难了。但是在实际生活中单一代理所能做的事情还是太少了，而且按照群体的智慧，不考虑训练硬件和时长问题，使用多个agent同时进行学习，会不会有奇招呢？另外如果在需要multi-agent的场景下，如想要完成多人游戏的话，也必须要考虑到多代理的问题。【本文地址】