多 Agent 强化学习综述

这是来自我们组同事谢思发同学的文章。谢思发同学硕士毕业于厦门大学,于 2016 年加入腾讯互动娱乐数据挖掘团队,从事用户画像、知识图谱和社交网络方面的工作。

最近在大神们的带领下学习强化学习,啃了一篇多Agent强化学习的综述论文[1],这里简单做下笔记。

1. 背景介绍

多智能体系统由一群有自主性的,可互相交互的实体组成,它们共享一个相同的环境,通过感知器感知环境并通过执行器采取行动。多智能体在现实生活中已有应用,如机器人战队,分布式控制和资源管理。虽然可以预先设定多智能体的行为表现,但因为环境太过复杂,有时甚至会随时间而变化。所以很难提前设计一个良好的行为,或者随时间推移,先前良好的行为也会慢慢变差。通常需要在线学习新的行为,才能提高智能体或整个系统的性能。

在单Agent的强化学习中,Agent在感知完环境的状态后,采取了一个动作,使得环境转移到下一个状态,并得到一个评价这次动作好坏的反馈。Agent的学习目标就是最大化累计反馈。强化学习的反馈比有监督学习信息量少,但多于无监督学习。通过一些简化或泛化,单Agent的强化学习算法也可以运用到多Agent中。

1.1. 强化学习

首先回顾单Agent的强化学习算法,介绍单Agent强化学习任务以及求解方法。然后过渡到多Agent强化学习(Multi-Agent Reinforcement Learning,MARL)的定义。本次的讨论主要限制在状态空间是离散的,并且动作空间有限的强化学习场景中,大部分的MARL算法也是在这个设定下提出的。

单Agent的强化学习可以用马尔科夫决策过程表征,其定义如下:

定义1. 有限马尔科夫决策过程是一个4元组 $\langle X,U,f,\rho \rangle$ 。
其中 $X$ 是Agent的状态空间, $U$ 是动作空间, $f:X \times U \times X \to [0,1]$ 是状态转移概率函数, $\rho : X \times U \times X \to R$ 是奖励函数。

Agent在状态 $x_k \in X$ 下,采取了动作 $u_k \in U$ ,根据状态转移概率值 $f(x_k,u_k,x_{k+1})$ 转移到了状态 $x_{k+1} \in X$ ,获得即时回报 $r_{k+1}$ 。对于确定性系统,概率转移函数变成 $\tilde{f} : X × U →X$ .,此时即时回报只跟当前状态和当前采取的动作有关,即 $r_{k+1} = \tilde{\rho}(x_k,u_k)$ , $\tilde{\rho}: X \times U \to R$ 。 Agent在任一个状态下如何选择动作的决策过程,称为Agent的策略,用h表示。如果策略不随时间而变化,就称策略是稳定的(stationary)。Agent在状态X下,根据策略h,执行后续的动作,所能获得的期望回报如下:

$$
R^h(x)=E\lbrace \sum_{k=0}^\infty \gamma^kr_{k+1}|x_0=x,h \rbrace     1
$$

其中 $\gamma$ 是折扣因子,保证越后面的回报,对回报函数的影响越小,刻画了未来回报的不确定性,同时也使得回报函数是有界的。强化学习的目标就是寻找一个最优策略h,使得Agent在任一状态下的期望回报都是最大的。期望回报涉及到后面一系列动作的回报值,而Agent每次只能获得当前步的即时回报,不好直接求解。可以转换成计算状态动作值函数(Q-function),它给出,在策略h下,每个状态动作对的期望回报:
$$
Q^h(x,u) = E\lbrace \sum_{k=0}^\infty \gamma^kr_{k+1}|x_0=x,u_0=u,h \rbrace 2
$$

最优Q函数定义为 $Q^*(x,u)=max_hQ^h(x,u)$ 。

它满足贝尔曼最优等式:
$$
Q^*(x,u)=\sum_{x^\prime \in X} f(x,u,x^\prime) [\rho(x,u,x^\prime)+\gamma max_{u^\prime} Q^\ast(x^\prime,u^\prime)] \forall x \in X, u \in U  3
$$

等式表明在状态X下采取动作U的最优回报值是期望的即时回报,加上下一状态的最优(折扣)回报值。当 $Q^\ast$ 计算好后,最优策略就是在每一状态下,选择回报最大的动作。

$$
\tilde{h}^\ast(x) = arg max_u Q^\ast(x,u)      4
$$

在实际求解的过程中,可以采用一种迭代近似的方法求解,即Q-learning:
$$
Q_{k+1}(x_k,u_k)=Q_k(x_k,u_k) + \alpha_k
[r_{k+1}+\gamma max_{u^\prime}Q_k(x_{k+1},u^\prime)-Q_k(x_k,u_k)]  5
$$
算法先随机初始化 $Q(x,u)$ 值,然后不停地迭代更新,使 $Q^k$ 最终收敛于 $Q^\ast$ 。因为最开始的Q函数是随机的,不准确,而且Q-learning如果要收敛,还要求每个状态动作对都走过,所以需要有一个探索和贪婪的的平衡过程。在每个状态下,以 $\varepsilon \in (0,1)$ 的概率随机选择一个动作,以 $(1-\varepsilon)$ 的概率选择最优动作。还可以使用玻尔兹曼探索过程(Boltzmann exploration procedure),Agent在状态 $x$ 下依概率 $h(x,u)$ 选择动作 $u$ ,其中 $h(x,u)$ 为:

$\tau$ 是超参数,当 $\tau \to 0$ 时,Agent倾向选择最优动作,当 $\tau \to \infty$ 时,Agent则是随机选择动作。

马尔科夫决策过程泛化到多Agent情形则是随机博弈,定义如下:

定义2: 随机博弈是一个多元组 $< X,U_1,…U_n,f,\rho_1,…\rho_n>$ ,n是Agent的个数, $X$ 是状态集合, $U_i$ 是 $Agent_i$ 的动作空间。所有Agent的动作组成联合动作空间集 $U=U_1 \times … \times U_n$ 。 $f: X \times U \times X \to [0,1]$ 是状态转移函数, $\rho_i:X \times U \times X \to R,i=1,…,n$ 是每个Agent的回报函数。
定义中概率转移和每个Agent的回报函数都是基于联合动作空间计算的。此外每个Agent的策略是 $h_i:X \times U_i \to [0,1]$ ,所有Agent的策略组合成联合策略 $h$ 。每个Agent在状态x下的期望回报为
$$
R_i^h(x)=E\lbrace \sum_{k=0}^\infty \gamma^kr_{i,k+1}|x_0=x,h\rbrace   7
$$
Q函数为
$$
Q_i^h(x,u)=E \lbrace \sum_{k=0}^\infty \gamma^kr_{i,k+1}|x_0=x,u_0=u,h\rbrace     8
$$
按照状态数目的不同,随机博弈可以分为静态博弈和动态博弈。静态博弈对应系统中只有一个状态的情形。多于一个状态的情形则为动态博弈。将一个静态博弈重复进行多次,即为重复博弈。此外还可以分为完全合作,完全竞争和混合随机博弈。在完全合作的随机博弈中,所有Agent的回报函数都是一样的,即 $\rho_1=…=\rho_n$ ,从而有 $R_1^h=…R_n^h$ 。在完全竞争的随机博弈中,如果只有两个Agent,则 $\rho_1=-\rho_2$ 。而混合的随机博弈,则包括竞争和合作关系。

1.2 机会和挑战

多Agent强化学习较单Agent存在一定优势:不同Agent通过共享经验,可以更快更好的完成任务。比如有经验的Agent可以当老师,指导无经验的Agent;如果任务可以拆分不同子任务时,不同Agent可以并行执行子任务,以此加速计算;当系统中有Agent失效时,其他Agent可替代执行任务,从而使整个系统更加鲁棒;而且可方便地加入新的Agent,扩展性也更好。

但同时也面临着一些挑战:首先维度灾难问题更加严重,之前状态转移概率函数和回报函数都是在联合动作空间下计算的。随着状态和动作的增加,计算复杂度呈指数增长。其次学习目标不好定义,Agent的回报跟其他Agent的行为相关的,没办法单独最大化某个Agent的回报。不稳定性也是MARL的一个问题,Agent是同时在学习的,每个Agent都是面临着一个不停变化的环境,最好的策略可能会随着其他Agent策略的改变而改变。最后,探索和贪婪过程会更复杂,在多Agent下,探索不仅是为了获取环境的信息,还包括其他Agent的信息,以此来适应其他Agent的行为。但是又不能过度探索,不然会打破其他Agent的平衡。

基于上述挑战,在MARL中,主要关注两方面学习目标,稳定性(stability)和适应性(adaptation)。稳定性指Agent的策略会收敛至固定,而适应性确保性能不会因为其他Agent改变策略而下降。收敛至均衡态是稳定性的基本要求,这要求所有Agent的策略收敛至协调平衡状态,最常用的是纳什均衡。适应性体现在理性或无悔两个准则上。理性指出,当其他Agent稳定时,Agent会收敛于最优反馈。无悔是说最终收敛的策略,其回报要不差于任何其他的策略。

2. MARL

可以从不同维度来分类MARL算法,首先从任务的类型来分的话,MARL算法可以分成如下三大类:

也可以从算法侧重的学习目标来分,关注稳定性的算法通常对其他Agent是独立无感知的,而侧重适应性的算法都需要能感知其他Agent,它们会为对手建模,来追踪对手的策略。

2.1 完全合作

首先看完全合作下的MARL算法,如果在随机博弈中,存在一个中心控制者,可以控制其他Agent的行动。那么就能求得最佳的联合动作值,随机博弈就退化成马尔科夫决策过程,并且可以用Q-learning算法求解。
$$
Q_{k+1}(x_k,u_k)=Q_k(x_k,u_k) + \alpha_k
[r_{k+1}+\gamma max_{u^\prime}Q_k(x_{k+1},u^\prime)-Q_k(x_k,u_k)]  9
$$
但是大部分系统是不存在中心控制者,那么是否可以假定其他Agent都是选择当前状态下最优的动作,在这种假定下,再选择对自己最优的动作,即
$$
\tilde{h}_i^\ast(x) = arg max_{u_i}max_{u_1,…u_{i-1},u_{i+1},…u_n} Q^\ast(x,u)      10
$$
但在特定状态下,一些组合动作才可能取得最优结果(此时Agent不一定都是取自己最优的动作)。这时就需要协同机制,来协调Agent的动作。在下图中,有两个Agent需要一起通过障碍物,并且保持之间一格的距离。如果两个同时往左或往右,那么有机会通过障碍物,回报值是10。如果Agent1往左,Agent2往右,虽然有机会通过障碍物,但破坏了一格距离的限定,这时回报值是0。其他情况下,都会发送碰撞,回报值都是负的。所以最优动作要么同时往左,要么同时往右。这时就需要协同机制了,否则Agent1会认为大家同时往左,而Agent2却选择同时往右。

上面的例子,因为存在两个最优联合动作,所以需要互相协调。但如果在Agent2右边又有一个障碍物时,这时最优联合动作是同时往左,也就不需要协同机制了。Team Q-learning[2]是一种不需要协同机制的算法,它指出在最优联合动作是唯一情况下,可以采用(10)式贪婪公式求解。

在没有负回报的确定性(deterministic)问题中,可以用分布式(distributed)Q-learning[3]算法求解,这也不需要协调机制。每个Agent保存一个本地的策略 $\tilde{h}_i(x)$ 和只取决于自身动作的本地的Q函数 $Q_i(x,u_i)$ 。Q函数的更新公式如下:
$$
Q_{i,k+1}(x_k,u_{i,k})=max \lbrace Q_{i,k}(x_k,u_{i,k}) ,
r_{k+1}+\gamma max_{u^\prime_i}Q_{i,k}(x_{k+1},u^\prime_i) \rbrace  11
$$
本地的策略更新公式如下:

此外有一类间接协调算法,每个Agent通过为其他Agent建模,或统计不同动作的历史的回报值,来选择可能获得更高回报的动作。Joint Action Learners(JAL)[4]算法中,每个Agent会为其他Agent建模:
$$
\sigma^i_j(u_j) = \frac{C^i_j(u_j)}{\sum_{\tilde{u_j} \in U_j} C^i_j(\tilde{u_j})}   12
$$
$\sigma^i_j(u_j)$ 是Agaent i 对Agent j的建模, $C^i_j(u_j)$ 统计了Agaent i 观察到的Agaent j 采取动作 $u_j$ 的次数。结合这些模型,JAL提出了几个启发式的方法,来提高状态动作对的回报。

Frequency Maximum Q-value(FMQ)[5]算法,统计每个动作取得最优回报的频率。然后用这个值修改公式6中的Q函数。
$$
\tilde{Q}_i(u_i) = Q_i(u_i) + \nu \frac{C^i_{max}(u_i)}{C^i(u_i)} \gamma_{max}(u_i)        13
$$

其中 $\gamma_{max}(u_i)$ 是采取动作 $u_j$ 取得的最大回报值,$C^i_{max}(u_i)$ 是取得最大值的次数, $C^i(u_i)$ 是采取动作 $u_j$ 的次数。经过修改后,Agent就会倾向选择以往取得高回报的动作。简单理解,假设在某次动作组合下,所有Agent取得了一个高回报值(完全合作下Agent的回报是一样的),那么每个Agent在后面就会倾向选择在这个动作组合下各自采取的动作。逐渐地就会增加这个最优动作组合对出现的概率。

最后是基于社会公约(social conventions),角色,互相交流[6]等显式的协调机制。在社会公约中,会规定每个Agent的先后顺序以及动作选择的先后顺序,这些信息是共享周知的。例如在上面那两个Agent穿越障碍物的例子中,规定Agent 1优先于Agent 2,而且动作优先选择L。那么Agent 1在行动时,查Q表得知往左或往右都能取得最高收益,根据社会公约,采取L1。轮到Agent 2的时候,根据社会公约推理可知Agent 1是选择L1的,这时候Agent 2 就会选择L2,从而实现最大收益。如果可以互相交流,那么只需要规定每个Agent的先后顺序。同样的例子里,Agent 1先选L1或R1。然后把选择的动作告诉Agent 2,Agent 2再选择相对应的动作。

2.2 完全竞争

在完全竞争的随机博弈中,可以应用最小最大化(minimax)原则:在假定对手会采取使自己收益最小化的动作的情况下,采取使自己收益最大的动作(即以最坏的恶意揣度对手)。 minimax-Q算法[7,8]基于最小最大化原则,使用下式来更新Agent 1的策略函数和Q函数。
$$
h_{1,k}(x_k,\cdot)=arg m_1(Q_k,x_k)       14
$$
$$
Q_{k+1}(x_k,u_{1,k},u_{2,k})=Q_k(x_k,u_{1,k},u_{2,k}) + \alpha
[r_{k+1}+\gamma m_1(Q_k,x_{k+1})-Q_k(x_k,u_{1,k},u_{2,k})]  15
$$
其中 $m1$ 是Agent 1的最小最大值:
$$
m_1(Q,x)=max_{h_1(x,\cdot)}min_{u2}\sum_{u1}h_1(x,u_1)Q(x,u_1,u_2)  16
$$
minmax-Q算法是对手独立的,不管对手如何选择,总能取得不差于minmax函数回报值。但如果对手不是采取最优策略(即使自己的收益最小化),而且能对对手建模,那么就可以取得更优的动作。一种为对手建模的方式是对公式12进行扩展:
$$
\hat{h}^i_j(x,u_j) = \frac{C^i_j(x,u_j)}{\sum_{\hat{u_j} \in U_j} C^i_j(\hat{x,u_j})}   17
$$
其中 $C^i_j(x,u_j)$ 是Agent i 观察到Agent j 在状态 $x$ 下采取动作 $u_j$ 的次数。
在下面的例子中,Agent 1 需要到达X标志的位置,同时避免被Agent 2 捕抓到。Agent 2 的目标就是抓到Agent 1 ,两个Agent只能往左或往右移动。右侧是Agent 1 的Q表,两个同时往左不产生任何收益,同时往右,则Agent 1达成目标且没被抓到,收益10。Agent 1 往右而Agent 2 往左,则被抓到,收益-10。Agent 1 往左,Agent 2 往右,虽然没达到指定位置,但远离Agent 2 所以收益1。Agent 2 的Q表是Agent 1 的Q表取负。

根据minimax原则,Agent 1应该选择往左移动。因为往左的最小期望收益是0,往右的最小期望收益是-10。对于Agent 2,其最优策略是往左移动保护目标位置。但如果Agent 2 不是采取最优策略而是往右走,并且Agent 1 通过建模能预测到,那么Agent 1 就可以往右移动,达成目标。

2.3 混合任务

在混合任务中,大部分算法是针对静态任务的,而且主要是关注适应性。其中最简单的是直接应用单Agent算法。即每个Agent的Q函数都只跟自己相关,使用公式5进行更新,对对手无感知。[9]指出在特定的博弈中,单Agent算法是可以收敛至协调均衡的。但是在其他情况下,会存在不稳定的循环震荡。

Win-or-Learn-Fast Policy Hill-Climbing(WoLF-PHC)[10]是一类启发式算法,根据4式来更新Q函数,并根据下面的式子来更新策略函数。

在WoLF-PHC算法中,定义了两种策略,即当前策略 $h(s,a)$ 和平均策略 $\tilde{h}(s,a^\prime)$ 。当前策略是一种概率分布函数,初始值为 $h(s,a)=\frac{1}{|A_i|}$。这个概率分布函数当Agent选择动作 $a$ 时进行更新,更新方法是:对于Q函数来说,最好的动作即 $a=maxarg_aQ(s,a^\prime)$ ,则增加概率,其他动作则降低概率。WoLF-PHC会不断更新平均策略,并和当前策略进行比较:如果当前策略平均奖励值大于平均策略的奖励值,即 $\sum_ah(s,a)Q(s,a)>\sum_a\tilde{h}(s,a)Q(s,a)$,则认为Agent是“wining”的,此时平均策略将采用 $δ_{win}$ 速率来慢慢更新策略,否则,认为当前Agent是“losing”的,用比较大的 $δ_{lose}$ 来更快的自适应学习[11]。此外还有更具体的算法,能力有限,看不是很懂,就不翻译了,有兴趣的可以查原文。

3. 多Agent物体搬运

最后举一个多Agent合作搬运物体的例子,有两个Agent1和2,需要先通过下方的障碍口,然后一个Agent抓物体的一边,避过上方的障碍物,将物体搬到home base位置。这里先用两个坐标值,来标志Agent的空间位置。 $p_{i,x} \in \lbrace 1,2,…,7 \rbrace,p_{i,y} \in \lbrace 1,2,…,6\rbrace$ ,用一个变量来记录Agent抓物体的状态 $g_i \in \lbrace 没抓住,抓住左边,抓住右边 \rbrace$ 。 完整的状态空间是 $x=[p_{1,x},p_{1,y},g_1,p_{2,x},p_{2,y},g_2] ^T$ 。动作空间 $U_i=\lbrace 左,右,上,下,停止 \rbrace$ 。回报函数是如果抓住物体得一分,物体搬到指定位置得10分,其他情况不得分。

这里选用三个算法来解决这个问题:单Agent算法,team Q-learning以及WoLF-PHC[10]。设定折扣因子 $\gamma = 0.98$ , 学习率$ \alpha = 0.1$ , 贪婪率 $\epsilon = 0.8$,并随实验轮数递减。下图是实验结果,横轴是实验轮数,纵轴是搬到指定位置花费的步数。可以看到三个算法都收敛得很快,基本20-30轮就稳定收敛。而且单Agent的效果要稍好于其他两个算法,虽然它对另外一个Agent是无感知的。三种算法都没有用通信机制,却实现了一种隐性的协调:偶然学习到一条足够好的路线,然后逐渐忽略其他的路线。

下图是team Q-learning算法得到最优路线(另外两个算法得到的路线类似),Agent 1先通过下方的障碍口,抓住物体左侧,然后原地等待。Agent 2 通过障碍口,抓住物体右侧,然后一起越过上方障碍物,到达目的地。

4. 总结

多智能体系统由一群有自主性的,可互相交互的实体组成,它们共享一个相同的环境,通过感知器感知环境并通过执行器采取行动。多智能体在现实生活中已有应用,如机器人战队,分布式控制和资源管理。虽然可以预先设定多智能体的行为表现,但因为环境太过复杂,有时甚至会随时间而变化。所以很难提前设计一个良好的行为,或者随时间推移,先前良好的行为也会慢慢变差。通常需要在线学习新的行为,才能提高智能体或整个系统的性能。目前我们正在利用非完美信息博弈工具集 RoomAI 开发不同棋牌游戏的 AI 算法,希望多 Agent 强化学习能够带来一些思考和方法。 RoomAI 是非完美信息博弈工具集。在 RoomAI 中,选手获得游戏环境给出的信息,当前选手选择合适的动作,游戏环境根据该动作推进游戏逻辑;重复上述过程,直到分出胜负;整个过程如下所示。

欢迎大家 star RoomAI

引用

[1]. Buşoniu L, Babuška R, Schutter B D. Multi-agent Reinforcement Learning: An Overview[J]. Studies in Computational Intelligence, 2010, 310:183-221.

[2]. Littman, M.L.: Value-function reinforcement learning in Markov games. Journal of Cognitive Systems Research 2(1), 55–66 (2001)

[3]. Lauer,M., Riedmiller,M.: An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In: Proceedings 17th International Conference on Machine Learning (ICML-00), pp. 535–542. Stanford University, US (2000)

[4]. Claus, C., Boutilier, C.: The dynamics of reinforcement learning in cooperative multiagent systems. In: Proceedings 15th National Conference on Artificial Intelligence and 10th Conference on Innovative Applications of Artificial Intelligence (AAAI/IAAI-98), pp. 746–752.Madison, US (1998)

[5]. Kapetanakis, S., Kudenko, D.: Reinforcement learning of coordination in cooperative multiagent systems. In: Proceedings 18th National Conference on Artificial Intelligence and 14th Conference on Innovative Applications of Artificial Intelligence (AAAI/IAAI-02), pp. 326–331. Menlo Park, US (2002)

[6]. Vlassis, N.: A Concise Introduction to Multiagent Systems and Distributed Artificial Intelligence.Synthesis Lectures in Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers (2007)

[7]. Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In:Proceedings 11th International Conference on Machine Learning(ICML-94), pp. 157–163.New Brunswick, US (1994)

[8]. Littman, M.L.: Value-function reinforcement learning in Markov games. Journal of Cognitive Systems Research 2(1), 55–66 (2001)

[9]. Tuyls, K., ’t Hoen, P.J., Vanschoenwinkel, B.: An evolutionary dynamical analysis of multiagent learning in iterated games. Autonomous Agents and Multi-Agent Systems 12(1), 115–153 (2006)

[10]. Bowling, M., Veloso, M.: Multiagent learning using a variable learning rate. Artificial Intelligence 136(2), 215–250 (2002)

[11]. 邵 飞; 伍 春; 汪李峰. 基于多Agent强化学习的Ad hoc网络跨层拥塞控制策略[J]. 电子与信息学报, 2010, 32(6): 1520-1524 . Shao Fei①; Wu Chun①; Wang Li-feng②. Research on Cross-layer Congestion Control Strategy Based on Multi-agent Reinforcement Learning in Ad hoc Network. , 2010, 32(6): 1520-1524

此条目发表在强化学习, 数学基础, 算法荟萃分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。