从博弈论到 MARL.中科院自动化所张海峰讲座.20200606

内容摘要

随着以图像识别为代表的“感知智能”日趋成熟，越来越多的人工智能研究者开始关注以 AlphaGo 为代表的“决策智能”。在即将来临的物联网时代，群体决策智能将成为一个研究重点。

传统上，博弈论研究的是多个智能体的理性决策问题。它定义了动作、收益等博弈基本概念，侧重分析理性智能体的博弈结果，即均衡。然而，在很多现实问题中，博弈的状态空间和动作空间都很大，智能体的绝对理性是很难实现的.智能体往往处在不断的策略学习过程中。因此，近年来兴起的多智能体强化学习主要研究智能体策略的同步学习和演化问题，它在无人机群控制、智能交通系统、智能工业机器人等场景中具有很大的应用前景。

研究背景

AI 发展趋势是由智能感知到智能决策，再到群体智能决策。群体智能决策的场景有王者荣耀、快递机器人配送、自动驾驶等。

博弈论

博弈定义

定义玩家集合为 $N = \{1,2,…,n\}$，策略集合为 $A_1,A_2,…,A_n$，收益函数为 $r_1,r_2,…,r_n$

矩阵博弈

以囚徒困境为例，玩家 1 和玩家 2 的策略空间及收益组合如下所示：

其中包含一些基本假设：

• 两个玩家同时决策
• 玩家知道所有博弈元素
• 玩家是理性的，追求自身收益最大化

策略推理

占优策略 Dominant Strategy

无论对方采取什么策略，对己方都是最优的策略。即在上表中，无论玩家 2 选什么，玩家 1 选坦白都是更优的。因此，坦白是玩家 1 的占优策略。

在此基础上，玩家 2 的占优策略也是坦白，此时称坦白是玩家 2 的最优应对 Best-response。

博弈的解

纳什均衡 Nash Equilibrium

任何玩家都不能通过独自改变策略而获益，即所有玩家都处在最佳应对的策略组合。

其数学定义为：给定一个策略组合 $a=(a_1,a_2,…,a_n)\in A_1\times A_2\times … \times A_n$，若 $r_1(a_1,a_2,…,a_n) \geq r_1(a_1’,a_2,…,a_n), \forall a_1’\in A_1$ 且 $r_2(a_1,a_2,…,a_n) \geq r_2(a_1,a_2’,…,a_n), \forall a_2’\in A_2$ 且 … 且 $r_n(a_1,a_2,…,a_n) \geq r_n(a_1,a_2,…,a_n’), \forall a_n’\in A_n$，那么策略组合 $a=(a_1,a_2,…,a_n)\in A_1\times A_2\times … \times A_n$ 是一个纳什均衡。

混合策略纳什均衡 Mixed Strategy Nash Equilibrium

混合策略是一个概率分布 $(p_1,p_2,…,p_n)$，其中 $p_i$ 表示选择动作 $i$ 的概率。

混合策略纳什均衡是一个混合策略组合，任何玩家都不能通过独自改变混合策略而使得自身期望收益变高，例如剪刀石头布博弈。

任意博弈，必然存在一个混合策略纳什均衡。

协同问题

在面临多个均衡时，如何选取均衡需要依靠玩家间的协同，例如创立通信机制，制定社会规则等等。

合作博弈 Cooperative Game

竞争博弈 Competitive Game

多智能体强化学习

多智能体强化学习是现实中的博弈问题，具有状态、动作空间大，博弈元素不完全可知的问题。强化学习的学习目标包括了均衡、协同和合作三个部分。

参考论文：

Bi-level Actor-Critic for Multi-agent Coordination：https://arxiv.org/abs/1909.03510

Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning：https://arxiv.org/abs/1901.09207

Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games：https://arxiv.org/abs/1703.10069

Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments：https://arxiv.org/abs/1706.02275