Learning to Cooperate via Policy Search

By Leonid Peshkin, Kee-Eung Kim, Nicolas Meuleau, Leslie Pack Kaelbling. 2000

312 citations recorded by the source corpus.

Cooperative games are those in which both agents share the same payoff structure. Value-based reinforcement-learning algorithms, such as variants of Q-learning, have been applied to learning cooperative games, but they only apply when the game state is completely observable to both agents. Policy search methods are a reasonable alternative to value-based methods for partially observable environments. In this paper, we provide a gradient-based distributed policy-search method for cooperative games and compare the notion of local optimum to that of Nash equilibrium. We demonstrate the effectiveness of this method experimentally in a small, partially observable simulated soccer domain.

Subfields: Artificial Intelligence, Management Science and Operations Research, Safety Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Safety Research

Citations in the corpus

Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “Works include model-free gradient-ascent based methods (Peshkin et al., 2000; Dutech et al., 2001), simulator-supported methods to improve policies using a series of linear programs (Wu et al.”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, methodology): “We will not review the work performed on infinite-horizon Dec-POMDPs, such as the work by Peshkin, Kim, Meuleau, and Kaelbling (2000) , Bernstein, Hansen, and Zilberstein (2005), Szer and Charpillet (2005), Amato, Bernstein, and Zilberstein (2006, 2007a).”
Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems (2012, background): “2 A fully cooperative Markov game is also called an identical payoff stochastic game (Peshkin et al., 2000) or a multi-agent Markov decision process (Boutilier, 1999).”
Infinite-Horizon Policy-Gradient Estimation (2001, methodology): “For similar observations in the context of REINFORCE and VAPS , see Peshkin et al. (2000).”
The Complexity of Decentralized Control of Markov Decision Processes (2000, background): “The only known tractable algorithms for these types of problems rely on even more assumptions.”
Cooperative Multi-agent Control Using Deep Reinforcement Learning (2017, background): “[32] studied gradient based distributed policy search methods.”
Solving Transition Independent Decentralized Markov Decision Processes (2004, background): “Other research has approached this complexity barrier through approximations of the general problem (Goldman & Zilberstein, 2003; Nair, Tambe, Yokoo, Pynadath, & Marsella, 2003; Peshkin et al., 2000; Shen, Lesser, & Carver, 2003).”
Dynamic Programming for Partially Observable Stochastic Games (2004, methodology): “For general cooperative POSGs, algorithms such as those of Peshkin et al. [20] and Nair et al. [18] can be used, but they are only guaranteed to converge to local optima.”
Point-based Dynamic Programming for DEC-POMDPs (2006, unknown): “2004) or gradient descent (Peshkin et al. 2000), and that often have lower complexity.”
Multiagent Planning with Factored MDPs (2001, methodology): “Alternative approaches to this problem have used local optimization for the different agents, either via reward/value sharing [11, 13] or direct policy search [10].”
Game Theory and Multi-agent Reinforcement Learning (2012, methodology): “Finally, (Peshkin et al, 2000) develop a gradient based policy search method for partially observable, identical payoff stochastic games.”
Cooperative Multi-Agent Learning: The State of the Art (2005, background): “[173] investigate a distributed reinforcement learning approach to partially observable stochastic games with identical reinforcement to each agent, and show that their algorithm converges to local optima.”
Reinforcement Learning in POMDPs Without Resets (2005, methodology): “The main building block of our algorithms is an implementation of anapproximatereset strategy, which we show always exists in every POMDP.”
Rethinking Formal Models of Partially Observable Multiagent Decision Making (2019, background): “a). Figure 1 shows a game where Lemma C.8 leads to a quadratic increase in size. 3.2 POSGs and Models for Reinforcement Learning There are many formalizations and variants of POSGs in the literature (Peshkin et al., 2000; Hansen et al., 2004b; Emery-Montemerlo et al., 2004; Horak and Bosansky, 2019)”
An Overview of Cooperative and Competitive Multiagent Learning (2005, background): “Preliminary research for such domains is presented in [125, 114].”