2019/10/11 21:10

兼顾公平与效率？北大NeurIPS 19论文提出多智能体强化学习方法FEN

近日，北京大学卢宗青团队提出了一种新的多智能体强化学习方法 Fair-Efficient Network（FEN，「分」），用于多个智能体学习提升系统效率并同时保持公平。这一新方法对任务调度、马太效应和工厂生产等实际情景具有重要意义，该论文已被人工智能顶会 NeurIPS 2019 录用。

公平有助于人类社会的稳定和生产力的提高，同样对于多智能体系统也十分重要。然而让一组智能体学习提升系统效率并同时保持公平是一个复杂的、多目标的、联合策略优化问题。目前主流的多智能体强化学习算法没有考虑公平性的问题，一些针对特定情景公平性的方法又依赖专家知识，这对于一般性情景并不适用。

作者提出一种分层多智能体强化学习方法 Fair-Efficient Network（FEN，「分」），从三个方面解决这一问题：

提出 fair-efficient reward，用于学习效率与公平。
提出一种 hierarchy 架构，降低学习难度。
提出 FEN 的分布式训练方法。

论文链接：https://z0ngqing.github.io/publication/nips19/

在作者的设定中，环境中存在若干智能体和有限的资源，如内存、带宽等。每个智能体获得的环境外部奖励只与自己所占据的资源相关。每个智能体的效用 u 定义为在时间域上的平均奖励，使用 coefficient of variation 来衡量系统公平性。

Fair-efficient reward

每个智能体的 fair-efficient reward 设计为：

其中分子项表示系统的平均效用，用来促进效率，分母项表示该智能体效用偏离平均值的偏差。因此 fair-efficient reward 兼顾了公平与效率。另外，作者证明了在强化学习设定下，若每个智能体使自己的 fair-efficient reward 最大化，可以实现帕累托最优和资源的平均分配。

Hierarchy

然而学习 fair-efficient reward 依然是困难的，因为效率与公平在某些状态下是冲突的，因此作者提出一种 hierarchy 架构，用于降低学习难度。

每个智能体拥有一个 hierarchy 结构，包含一个 controller 和若干 sub-policies。每经过 T 时间步，controller 选择一个 sub-policy 与环境交互，并获得 fair-efficient reward。1 号 sub-policy 获得环境外部奖励，专注于学习如何占据资源。而对于其他 sub-policies 来说，作者提出一种信息论优化目标，用于探索多样的公平行为。目标包括两项，第一项是 sub-policy 的序号与 sub-policy 下观察的互信息，第二项是动作的熵正则。

对于 controller 来说，避免了与环境的直接交互，能够实现长远规划；对于 sub-policy 来说，只需要专注于自己易于优化的目标，降低了学习难度。

Hierarchy 架构

实验

作者在三个情景中进行了实验

Job Scheduling 环境中存在 4 个智能体和 1 个资源，智能体占据资源会获得奖励，资源在同一时刻只能被一个智能体占据。
The Matthew Effect 环境中存在 10 个 Pac-men 和若干 ghosts。Pac-man 吃掉 ghost 会获得奖励，并且体积和速度变大，更容易吃其他 ghost，因此强者越强。
Manufacturing Plant 环境中存在 5 个智能体和不同种类的矿石，每个智能体采集不同的矿石来生产不同的零件，最终的产量取决于数目最少的零件。

在实验中，相比其他的 baselines，FEN 取得了接近最高的资源利用率和最低的 CV，并且在第三个实验中取得了最高的产量，这说明 FEN 智能体学会了兼顾效率与公平。

Job Scheduling

Manufacturing Plant

对比使用或者不使用 hierarchy 结构的 FEN，发现使用了 hierarchy 以后学习速度更快且收敛到更高的 fair-efficient reward，证明 hierarchy 能够显著降低学习难度。

随后作者分析了 controller 的行为模式，发现当智能体效用低于平均效用时，controller 倾向于选择 1 号 sub-policy 来占据更多资源，否则倾向于选择其他 sub-policy 来保持公平。这说明 controller 能够理智地切换策略使 fair-efficient reward 最大化。

为了分析除去 1 号之外其他 sub-policies 的行为，作者将三个 ghosts 置于环境中央，可视化三个 sub-policies 的分布（左）和随机策略的分布（右），可以发现：

Sub-policies 能够远离三个 ghosts 来保持公平。
三个 sub-policies 分布互不相同，达到了信息论目标的预期。

下面是在实验 Job Scheduling 中，「分」智能体（上）和独立决策智能体（下）的行为可视化比较。

理论北京大学NeurIPS