兼顾公平与效率?北大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北京大学
1
相关数据
强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

信息论技术

信息论是在信息可以量度的基础上,研究有效地和可靠地传递信息的科学,它涉及信息量度、信息特性、信息传输速率、信道容量、干扰对信息传输的影响等方面的知识。通常把上述范围的信息论称为狭义的信息论,又因为它的创始人是香农,故又称为香农信息论。

推荐文章
暂无评论
暂无评论~