从零开始《深度强化学习》——（四）多智能体强化学习

hanzhongtlx · 2024-01-26 00:00:15 · 科技·工程

前情回顾：从零开始《深度强化学习》——（三）策略学习

并行计算

并行计算基础

并行梯度下降

下面的对并行计算的讲解都以梯度下降为具体例子。

对于训练数据 (x_1,y_1),(x_2,y_2),...,(x_n,y_n) 定义最小二乘问题

可以用梯度下降方法

我们令

则有

我们假设 x_j,w\in\mathbb R^d，有 m 块处理器做并行计算，时间复杂度为 \mathcal O(\frac{nd}{m})，实操中，将 n 个数据均分为 m 份分给 m 个处理器并行计算对应份中数据的 g 即可。

MapReduce

并行计算需要在计算机集群上完成。一个集群有很多处理器和内存条，它们被划分到多个节点 (Compute Node) 上。一个节点上可以有多个处理器，处理器可以共享内存。节点之间不能共享内存，即一个节点不能访问另一个节点的内存。

为了协调节点的计算和通信，需要有相应的软件系统。MapReduce 是由 Google 开发的一种软件系统，用于大规模的数据分析和机器学习。MapReduce 原本是软件系统的名字，但是后来人们把类似的系统架构都称作 MapReduce。

• 服务器可以与 Worker 节点做通信传输数据（但是 Worker 节点之间不能相互通信）。一种通信方式是广播 (Broadcast)，即服务器将同一条信息同时发送给所有 Worker 节点。
• 每个节点都可以做计算。映射 (Map) 操作让所有 Worker 节点同时并行做计算。
• Worker 节点可以向服务器发送信息，最常用的通信操作是规约 (Reduce)。这种操作可以把Worker节点上的数据做归并，并且传输到服务器上。

用 MapReduce 实现并行梯度下降

我们需要把数据集 (x_1,y_1),(x_2,y_2),...,(x_n,y_n) 划分到 m 个 Worker 节点上，每个节点上存一部分数据，这种划分方式叫做数据并发（与数据并发相对的是模型并发 (Model Parallelism)，即将模型参数 w 划分到 m 个 Worker 节点上）。

那么我们假设 \mathcal I_1,\mathcal I_2,...,\mathcal I_m 是集合 \{1,2,...,n\} 的一个划分，则并行梯度下降的步骤：

1. 广播 (Broadcast)：服务器将当前的模型参数 w 广播到 m 个 Worker 节点。

2. 映射 (Map)： 这一步让 m 个 Worker 节点做并行计算，用本地数据计算梯度。这样第 k 号 Worker 节点得到向量集合 \{(x_j^\top w-y_j)x_j\}_{j\in\mathcal I_k}。

3. 规约 (Reduce)：在做完映射之后，每个 Worker 节点首先会规约自己本地的梯度和:

再将 \tilde g^k(k=1,2,...,m) 发送给服务器，求

这样只需要传递 md 个（浮点）数，而非不采用并行计算时的 nd 个。

4. 梯度下降：

并行计算的代价

一般有两种时间：

• 钟表时间 (Wall-clock Time)，也叫 Elapsed Real Time，意思是程序实际运行的时间。

• 处理器时间 (CPU Time 或 GPU Time) 是所有处理器运行时间的总和。（多个处理器情况可能存在时间重合）

定义加速比 (Speedup Ratio) 来衡量并行计算带来的速度提升：

通信量 (Communication Complexity) 的意思是有多少个比特或者浮点数在服务器与 Worker 节点之间传输，并行梯度下降的通信量是 \mathcal O(nd)。

延迟 (Latency) 是由计算机网络的硬件和软件系统决定的。

通信时间主要由通信量和延迟造成。我们无法准确预估通信时间（指的是钟表时间），除非实际做实验测量。但我们不妨用下面的公式粗略估计通信时间：

同步与异步

上文介绍的并行梯度下降属于同步算法 (Synchronous Algorithm)，即在所有 Worker 节点都完成映射 (Map) 的计算之后，系统才能执行规约 (Reduce) 通信。

实际软硬件系统中存在负载不平衡、软硬件不稳定、I/O 速度不稳定 等因素。因此 Worker 节点会有先后、快慢之分，不会恰好在同一时刻完成任务。同步要求每一轮都必须等待所有节点完成计算，这势必导致“短板效应”，即任务所需时间取决于最慢的节点。会出现 Straggler Effect，意思是一个节点的速度远慢于其余节点，导致整个系统长时间处于 空闲状态，等待最慢的节点。

而将同步屏障去掉，得到的算法就叫做异步算法 (Asynchronous Algorithm)。在异步算法中，一个 Worker 节点无需等待其余节点完成计算或通信。当一个 Worker 节点完成计算，它立刻跟 Server 通信，然后开始下一轮的计算。异步算法避免了等待，节点几乎没有空闲的时间，因此系统的利用率很高。利用一步算法计算梯度下降的步骤为：

• 在 Worker 端，首先服务器发出请求，索要最新的模型参数 w；然后计算

  \tilde g^k=\frac{1}{|\mathcal I_k|}\sum_{j\in\mathcal I_k}(x_j^\top w-y_j)x_j

  最后把计算出的梯度 \tilde g^k 发送给服务器。

• 而在服务器端，每当接收到一个 Worker 端发送来的参数则做梯度下降

  w\leftarrow w-\eta \tilde g^k

  并随时监听 Worker 发送的请求并相应（发送现在的 w 参数）。

在理论上，异步梯度下降的收敛速度慢于同步算法，即需要更多的计算量才能达到相同的精度。但是实践中异步梯度下降远比同步算法快（指的是钟表时间），这是因为异步算法无需等待，Worker 节点几乎不会空闲，利用率很高。

并行强化学习

异步并行双 Q 学习

• 在 Worker 端，每个 Worker 节点本地有独立的环境，独立的经验回放数组，还有一个 DQN 和一个目标网络。它用 \epsilon-greedy 策略控制智能体与本地环境交互，收集经验。把收集到的经验存入本地的经验回放数组。接下来每个 Worker 节点都要参与异步梯度下降：

  1. 向服务器发出请求，索要最新的 DQN 参数 w。
  2. 更新目标网络： w^-\leftarrow \tau w+(1-\tau) w^-
  3. 抽样（可以抽取 b 个经验数组），用双 Q 学习计算 TD 目标，计算梯度 \tilde g^k，发送给服务器（具体可以参考从零开始《深度强化学习》——（二）价值学习的 DDQN 部分）。

• 在服务器端，服务器上储存有一份模型参数 w，每当一个 Worker 节点发来梯度 \tilde g^k，就做一次梯度下降：

A3C: 异步并行 A2C

• 在 Worker 端， 向服务器发出请求，索要最新的参数 \theta、w；对 w^- 更新；最后作反应和观测后，计算

做累积梯度，即将 \delta_t\nabla_\theta\ln \pi(a_t|s_t;\theta) 和 \delta_t\nabla_w v(s_{t};w) 分别相加，记为 \tilde g^k_\theta 和 \tilde g^k_w（也可以取 b 个样本的平均值），发送给服务器。

• 服务器上储存有一份模型参数 \theta 和 w，每当一个 Worker 节点发来梯度 \tilde g^k_\theta 和 \tilde g^k_w，则做梯度下降即可。

多智能体系统

智能体系统 (Multi-Agent System，缩写 MAS) 中包含 m 个智能体，智能体共享环境，智能体之间会相互影响。具体地，一个智能体的动作会改变环境状态，从而影响其余所有智能体。

与并行计算不同，智能体之间会相互影响，而并行计算中智能体之间完全独立，不会相互影响。

多智能体强化学习 (Multi-Agent Reinforcement Learning，缩写 MARL) 是指让多个智能体处于相同的环境中，每个智能体独立与环境交互，利用环境反馈的奖励改进自己的策略，以获得更高的回报（即累计奖励）。

多智能体强化学习有四种常见设定：

• （完全）合作关系 (Fully Cooperative)：智能体的利益一致，获得的奖励相同，有共同的目标。假设一共有 m 个智能体，它们在 t 时刻获得的奖励分别是 R_t^1,R_t^2,...,R_t^m，则对 \forall t，都有 R_t^1=R_t^2=...=R_t^m。

• （完全）竞争关系 (Fully Competitive)：一方的收益是另一方的损失。在完全竞争的设定下，双方的奖励是负相关的：m=2 时，对 \forall t，都有 R_t^1\propto -R_t^2。如果是零和博弈，则 R_t^1=-R_t^2。

• 合作竞争的混合 (Mixed Cooperative & Competitive)：智能体分成多个群组；组内的智能体是合作关系，它们的奖励相同；组间是竞争关系，两组的奖励是负相关的。

• 利己主义 (Self-Interested)：系统内有多个智能体；一个智能体的动作会改变环境状态，从而让别的智能体受益或者受损。利己主义的意思是智能体只想最大化自身的累计奖励，而不在乎他人收益或者受损。智能体之间有潜在而又未知的竞争与合作关系：一个智能体的决策可能会帮助其他智能体获利，也可能导致其他智能体受损。

专业术语和单智能体一致，只需要用上标表示智能体编号即可。

合作关系设定下的多智能体强化学习

在多智能体系统中，一个智能体未必能观测到全局状态 S，设第 i 号智能体有一个局部观测，记为 O^i，它是 S 的一部分，不妨假设所有的局部观测的总和构成全局状态，即

MARL 的文献大多采用这种假设，用一张图形象说明各种术语以及设定：

合作关系设定下的策略学习

由前面所讲：

那么

进一步地，每个智能体的 Q_\pi 和 V_\pi 都相同。

通常来说，对于策略函数 \pi(A^1|S;\theta^1),\pi(A^2|S;\theta^2),...,\pi(A^m|S;\theta^m) 和 i\not=j，有 \theta^i\not=\theta^j。

策略学习的目标函数

那么策略学习可以写作

只需让第 k(1\leq k\leq m) 号智能体执行

合作设定下的多智能体 A2C (MAC-A2C)

我们无法直接计算 \nabla_{\theta^k}J(\theta^1,...,\theta^m)，可以仿照从零开始《深度强化学习》——（三）策略学习中的 A2C 方法进行近似。

我们 m 个智能体公用一个价值网络 v(s;\theta)，用于对 V_\pi(s;\theta) 近似。每个智能体都有一个自己的策略网络 \pi(a^i|s;\theta^i)。

tips：这部分的 s 都是 m 个智能体观测的集合，形如 [o^1,o^2,...,o^m]，不再单独指出。

对于价值网络 v(s;\theta) 的训练，和单智能体 A2C 一致。

对于策略网络的训练，我们首先类比给出合作关系 MARL 的策略梯度定理：

其中 b 是是不依赖于 A 的任意函数（基线），期望中 A 的概率密度函数

因此 \tilde g^k(s,a;\theta^k)=(Q_\pi(S,A)-b)\nabla_{\theta^k}\ln \pi(A^k|S;\theta^k) 是对 \nabla_{\theta^k}J(\theta^1,...,\theta^m) 的无偏估计，我们取 b=V_\pi(S)，利用贝尔曼方程近似 Q_\pi(s_t,a_t)=r_t+\gamma v(s_{t+1};w)，于是

然后做梯度下降即可。

实际操作时可以添加目标网络减小误差，MAC-A2C 属于同策略 (On-policy)，不能使用经验回收。

在 MARL 的常见设定下，第 i 号智能体只知道 o^i，但是观测不到全局的 s，为了解决这个局限性，一方面可以让智能体共享观测，每个智能体把自己的 o^i 传输给其他智能体；另一方面可以对策略网络和价值函数做近似，通常使用 \pi(a^i|o^i;\theta^i) 替代 \pi(a^i|s;\theta^i)。甚至可以进一步用 v(o^i;w^i) 代替 v(s;w)。

tips：还可以用

做基线 b（代替 V_\pi(s)），其中 a^{-i}=[a_1,...,a^{i-1},a^{i+1},...,a^m]，这种方法叫 COunterfactual Multi-Agent，缩写 COMA。COMA 的表现略好于 MAC-A2C，但是 COMA 的实现很复杂。

三种架构

实际应用中，MAC-A2C 的实现有三种常见的架构（实现方法）：

中心化训练 + 中心化决策

在时刻 t 和 t+1，中央控制器收集到所有智能体的观测值

且中央控制器直接从环境中观测或知道所有智能体本地的奖励 \tilde r_t^i 的加和，即奖励 r_t。

由于决策是中央控制器上的策略网络做出的，中央处理器也知道 a_t=[a_t^1,a_t^2,...,a_t^m]。于是可以直接利用上文所讲的 MAC-A2C 的训练方式训练即可。

在决策时，按照 \pi(\cdot|s_t;\theta^i) 做 a_t^i 的决策，将其发送给对应的第 i 个智能体执行即可。

这种方式完全按照 MAC-A2C 的算法实现，没有做任何改动，因此可以确保正确性。信息的完整性使得算法作出的决策可以更好；但是可能会有较大的延迟(Latency)，影响训练和决策的速度。

去中心化训练 + 去中心化决策

不再过于详细的赘述，实际上就是在第 i 个智能体上训练 \pi(a^i|o^i;\theta^i) 和 v(o^i;w^i)，这样每个智能体都可以独自地完成自己的训练过程，而不需要和中控制器做数据上的交互。这种训练方法在实践中效果往往不佳。

实际上，去中心化训练的本质就是单智能体强化学习 (SARL)，而非多智能体强化学习 (MARL)。

决策时，直接利用 a_t^i\sim\pi(\cdot\mid o^i;\theta^i) 做决策即可。

中心化训练 + 去中心化决策

对于策略网络 \pi(a^i|s;\theta^i)，用 o^i 来代替 s；而对于价值网络 v(s;w) 的训练，s 则利用全局的观测 [o^1,o^2,...,o^m] 来代替，且 w 是中央控制器的统一参数。

决策仍是去中心化决策，直接利用 a_t^i\sim\pi(\cdot\mid o^i;\theta^i) 做决策即可。

tips：三方法均可以用目标网络进行优化；对与中心化训练方式，目标网络参数 w^- 是中央控制器统一的参数；而对于去中心化训练方式，每一个智能体都有不同的 w^{i-} 参数。

三种方式的对比如图：

非合作关系设定下的多智能体强化学习

此时不同智能体的 V_\pi^i(s) 不再相同，因此 J 也有多个

第 i 个智能体目标

可见不同智能体没有共同的目标，基本思想仍然是梯度上升法。

在非合作关系设定下，收敛标准是纳什均衡。在纳什均衡的情况下，每一个智能体都在以最优的方式来应对其他各方的策略。在纳什均衡的情况下，谁也没有动机去单独改变自己的策略，因为改变策略不会增加自己的收益。

公式地讲，在多智能体系统中，当其余所有智能体都不改变策略的情况下，一个智能体 i 单独改变策略 \theta^i ，无法让其期望回报 J^i(\theta^1,...,\theta^m) 变大，那么这个多智能体系统就达到了纳什均衡。

对于双智能体系统，我们可以让两个智能体的对立面互相对决，记录不同训练对象平均回报，作为评判训练模型优劣的手段。

非合作设定下的多智能体 A2C (MAN-A2C)

与 MAC-A2C 不同的是，每个智能体都有一个价值网络 v(s;w^i)。这个变化不影响策略网络的训练，因此和 MAC-A2C 一致，唯一不同的仍然是要对 w^i 分别做梯度下降。

三种架构

和 MAC-A2C 一致，MAN-A2C 也有三种架构（下面不再加以描述决策的区别）：

1. 中心化训练 + 中心化决策：中央控制器有 2m 个（或 3m 个神经网络），严格按照 MAN-A2C 训练即可。

2. 去中心化训练 + 去中心化决策：将神经网络修改为 v(o^i;w^i) 和 \pi(a^i|o^i;\theta^i)，每个智能体上部署一个策略网络和一个价值网络（和一个目标网络）即可。

3. 中心化训练 + 去中心化决策：将 \pi(s^i|o^i;\theta^i) 部署到第 i 个智能体上，在中央控制器上部署价值网络（和目标网络），不对 s 替代（直接用 [o^1,o^2,...,o^m]）。

连续控制与 MADDPG

设系统里有 m 个智能体。每个智能体对应一个策略网络 \mu(o^i;\theta^i) 和一个价值网络 q(s,a;w)。

由于

我们实际操作中可以从经验回放数组（是异策略算法，取经验回放数组时可以取 a^i=\mu(o^i;\theta^i)+\epsilon）中抽取一个状态

计算 \forall i,\hat a_t=\mu(o_t^i;\theta^i)，于是利用蒙特卡洛近似，将 \nabla_{\theta^i}J^i(\theta^1,...,\theta^m) 近似为

就可以做梯度上升：

而对于价值网络，计算 TD 目标和 TD 误差

做梯度下降

可以看到，我们从经验回放数组中抽取一个四元组后，我们还需要所有的策略网络用于训练 \theta^i，于是必须采用中心化训练方式。

而决策时一般采用去中心化决策，取 a^i=\mu(o^i;\theta^i) 为第 i 个智能体基于本地观测的 o^i 的决策。

对于 MADDPG 算法，还有一些可行的优化思路：

• 采用截断双 Q 学习 (Clipped Double Q-Learning) 训练价值网络；
• 往 \mu(o_{t+1}^i;\theta^i) 中加入噪音（计算TD 目标时）；
• 减小更新策略网络和目标网络的频率，每更新 k(k>1) 次价值网络，更新一次策略网络和目标网络。

注意力机制与多智能体强化学习

自注意力机制

注意力机制 (Attention) 最初用于改进循环神经网络 (RNN)，提高Sequence-to-Sequence(Seq2Seq) 模型的表现。自注意力机制 (Self-Attention) 是注意力机制的一种扩展，不局限于 Seq2Seq 模型，可以用于任意的 RNN。

当一个问题有如此特点：

• 输入是长度为 m 的序列 (x^1,x^2,...,x^m)，输出是长度同为 m 的序列 (c^1,c^2,...,c^m)；
• 序列的长度 m 是不确定的，可以动态变化。但是神经网络的参数数量不能变化；
• 输出向量 c^i 不仅依赖于 x^i，还依赖于所有的 (x^1,x^2,...,x^m)（这与 RNN 解决的问题要求的只与 x_{1\sim i} 有关也不尽相同）。

就要用到自注意力机制解决。

自注意力层有三个矩阵：W_q\in\mathbb R^{d_{q}\times d_{\text{in}}}、W_k\in\mathbb R^{d_{q}\times d_{\text{in}}}、W_v\in\mathbb R^{d_{\text{out}}\times d_{\text{in}}}，参数数量与 m 无关（d_q 是一个需要调试的超参数）。

1. 我们首先做映射，每个 x 对应三个变量：

2. 接下俩计算权重向量 (\alpha^1,...,\alpha^m)，其中每个权重向量都是 m 维的列向量：