Value methods for efficiently solving stochastic games of complete and incomplete information

Multi-agent planning;Game theory;Reinforcement learning

Mac Dermed, Liam Charles ; Isbell, Charles L. Computer Science Gordon, Geoff Balcan, Maria-Florina Weiss, Lora Liu, C. Karen ; Isbell, Charles L.

University:Georgia Institute of Technology

Department:Computer Science

关键词: Multi-agent planning;    Game theory;    Reinforcement learning;   

Others  :  https://smartech.gatech.edu/bitstream/1853/50270/1/MACDERMED-DISSERTATION-2013.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Multi-agent reinforcement learning (MARL) poses the same planning problem as traditional reinforcement learning (RL): What actions over time should an agent take in order to maximize its rewards? MARL tackles a challenging set of problems that can be better understood by modeling them as having a relatively simple environment but with complex dynamics attributed to the presence of other agents who are also attempting to maximize their rewards. A great wealth of research has developed around specific subsets of this problem, most notably when the rewards for each agent are either the same or directly opposite each other. However, there has been relatively little progress made for the general problem. This thesis address this lack.Our goal is to tackle the most general, least restrictive class of MARL problems. These are general-sum, non-deterministic, infinite horizon, multi-agent sequential decision problems of complete and incomplete information. Towards this goal, we engage in two complementary endeavors: the creation of tractable models and the construction of efficient algorithms to solve these models. We tackle three well known models: stochastic games, decentralized partially observable Markov decision problems, and partially observable stochastic games. We also present a new fourth model, Markov games of incomplete information, to help solve the partially observable models. For stochastic games and decentralized partially observable Markov decision problems, we develop novel and efficient value iteration algorithms to solve for game theoretic solutions. We empirically evaluate these algorithms on a range of problems, including well known benchmarks and show that our value iteration algorithms perform better than current policy iteration algorithms. Finally, we argue that our approach is easily extendable to new models and solution concepts, thus providing a foundation for a new class of multi-agent value iteration algorithms.