多智能体强化学习综述-Lucian Busoniu
Multi-Agent Reinforcement Learning: A Survey
Lucian Busoniu Robert Babuska Bart De Schutter,2006
这篇文章对多智能体强化学习(MARL)的背景,目的,代表性的算法进行了调研。
多智能强化学习算法分类图下图。
1. 背景知识
A. 单智能体强化学习
单智能体情况下,使用马尔可夫决策过程(Markov Decision Process, MDP)来建模:
其中是动作空间,是转移概率分布,是奖励函数。时刻的长期奖励
在给定策略下的状态动作函数为,求解最优策略来最大化函数。使用Q-learning算法求解:
B. 多智能体强化学习
随机博弈(stochastic game, SG),或称马尔可夫博弈可以定义为其中表示个智能体,是环境状态空间,是动作空间,则联合动作集合,是状态转移概率分布,是奖励函数。
此时的转移概率、即时奖励、长期回报都依赖联合动作,,。此时的策略也是联合策略,。每个智能体的Q函数依赖联合动作和联合策略。
如果,SG简化为静态博弈。当时的SG是完全合作的,当时的SG是完全竞争的。静态博弈下,纳什均衡(Nash Equilibrum)是对对手的最佳策略。
合作的目的就是确保所有的智能体合理地选择期望联合策略中自己的部分。在多均衡的博弈中,合作归结为均衡的选择,智能体需要不断的选择同一均衡中自己的部分。
2. 多智能体学习目标
完全合作的随机博弈,可以通过最大化联合回报来解决。但是在其他的情况下,确定一个MALRL的目标并不容易,因为智能体的回报函数彼此之间相互关联,难以独立最大化。收敛到均衡点是多智能体学习的基本要求,并且纳什均衡是用的最多的。
聚焦稳定性的文献中智能体之间常常是相关独立的。而考虑调整的话,一般就会考虑其他智能体的行为。如果只考虑稳定性不考虑收敛性,那么就变成对其他智能体的跟踪了。
下表对多智能体强化学习算法进行了分类
3. 多智能体强化学习算法简介
这里将涉及到的算法按任务进行分类:完全合作、完全竞争、混合任务。
A. 完全合作任务
前面说过,完全合作时,如果存在控制空心,学习目标简化为MDP,动作空间为联合动作空间,此时的Q学习形式为:如果所有的智能体都是独立决策的,并且都采用贪婪策略,协作问题就会出现,即使所有的智能体都使用相同的算法并行学习共同的最优Q函数。理论上他们可以使用贪婪策略最大化共同回报,但是贪婪的动作选择机制以随机的方式打破了协作,最终导致联合动作是次优的。
无需协作模型
Team Q-learning1假设最优联合动作是唯一的(实际很少发生),因此原来的最优贝尔曼方程可以直接使用。Distributed Q-learning2没有假设协作的条件,但是这种方法只在确定性的场景下有效。每个只只通过它自己的动作来维护一个策略和一个局部Q函数,更新方向都是朝着怎加进行的: 在以及共同奖励为正的情况下,可以证明策略会收敛到最佳联合粗略
直接协作方法
在随机选择动作的时候有些做或者协商
- Social conventions3和roles4会限制智能体的动作选择
- Coordination graph简化协作,如果全局Q函数可以加性的分解为局部Q函数5-6
- 在协商选择动作的过程中需要通信
非直接协作方法
备注以及一些开放问题
B. 完全竞争任务
-
M. L. Littman, Value-function reinforcement learning in Markov games, Journal of Cognitive Systems Research, vol. 2, pp. 55-66, 2001. ↩︎
-
M. Lauer and M. Riedmiller, An algorithm for distributed reinforcement learning in cooperative multi-agent systems, in Proceedings Seventeenth International Conference on Machine Learning (ICML-00), Stanford University, US, 29 June 2 July 2000, pp. 535-542. ↩︎
-
C. Boutilier, Planning, learning and coordination in multiagent decision processes, in Proceedings Sixth Conference on Theoretical Aspects of Rationality and Knowledge (TARK-96), De Zeeuwse Stromen, The Netherlands, 17-20 March 1996, pp. 195-210. ↩︎
-
M. T. J. Spaan, N. Vlassis, and F. C. A. Groen, High level coordination of agents based on multiagent Markov decision processes with roles, in Workshop on Cooperative Robotics, 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-02), Lausanne, Switzerland, 1 October 2002, pp. 66-73. ↩︎
-
C. Guestrin, M. G. Lagoudakis, and R. Parr, Coordinated reinforcement learning, in Proceedings Nineteenth International Conference on Machine Learning (ICML-02), Sydney, Australia, 812 July 2002, pp. 227-234. ↩︎
-
J. R. Kok, M. T. J. Spaan, and N. Vlassis, Non-communicative multirobot coordination in dynamic environment, Robotics and Autonomous Systems, vol. 50, no. 2-3, pp. 99-114, 2005. ↩︎