Sample Bounded Distributed Reinforcement Learning for Decentralized POMDPs

By Bikramjit Banerjee, Jeremy Lyle, Landon Kraemer, Rajesh Yellamraju. 2012

30 citations recorded by the source corpus.

Decentralized partially observable Markov decision processes (Dec-POMDPs) offer a powerful modeling technique for realistic multi-agent coordination problems under uncertainty. Prevalent solution techniques are centralized and assume prior knowledge of the model. We propose a distributed reinforcement learning approach, where agents take turns to learn best responses to each other’s policies. This promotes decentralization of the policy computation problem, and relaxes reliance on the full knowledge of the problem parameters. We derive the relation between the sample complexity of best response learning and error tolerance. Our key contribution is to show that sample complexity could grow exponentially with the problem horizon. We show empirically that even if the sample requirement is set lower than what theory demands, our learning approach can produce (near) optimal policies in some benchmark Dec-POMDP problems.

Subfields: Artificial Intelligence, Management Science and Operations 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

1. Chris Amato
2. Zhuoran Yang
3. Kaiqing Zhang
4. Tamer Basar
5. Jonathan P. How
6. Yang Gao
7. Miao Liu
8. Yujing Hu

In Management Science and Operations Research

1. Zhuoran Yang
2. Kaiqing Zhang
3. Tamer Basar
4. Jonathan P. How
5. Shayegan Omidshafiei
6. Miao Liu
7. Bo An
8. Lawrence Carin

Citations in the corpus

• Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “Due to partial observability and local non-stationarity, model-based Dec-POMDP MARL is extremely challenging (Banerjee et al., 2012).”
• Multi-agent reinforcement learning as a rehearsal for decentralized planning (2016, neutral): “[4] propose a turn-taking learning approach where the non-learner's experience is wasted, whereas we propose a concurrent learning algorithm where all samples are used for learning by all agents.”
• Cooperative Multi-agent Control Using Deep Reinforcement Learning (2017, methodology): “A number of approximation methods for solving Dec-POMDPs have been developed recently that adapt techniques ranging from reinforcement learning [3] to stochastic search [28].”
• Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “Finite-sample analysis can also be established under this scheme (Amato and Zilberstein, 2009; Banerjee et al., 2012), for tabular settings with finite state-action spaces.”
• Learning in Multi-agent Systems with Sparse Interactions by Knowledge Transfer and Game Abstraction (2015, background): “A variety of mathematical models are adopted to represent a multi-agent system (MAS), such as Markov games [16], and decentralized partially observable Markov decision process (Dec-POMDP) [1].”
• Stick-Breaking Policy Learning in Dec-POMDPs (2015, background): “[Banerjee et al., 2012] proposed a distributed learning approach where agents take turns to learn the best response to each other’s policies.”
• Concurrent reinforcement learning as a rehearsal for decentralized planning under uncertainty (2013, unknown): “Traditional Dec-POMDP solvers are limited in that they compute the set of prescribed behaviors for agents centrally, and assume that a comprehensive set of model parameters are available a priori; however, multi-agent reinforcement learning (MARL) techniques, have recently been applied [4, 1] to ove”