Rollout Sampling Policy Iteration for Decentralized POMDPs

By Feng Wu, Shlomo Zilberstein, Xiaoping Chen. 2010

29 citations recorded by the source corpus.

We present decentralized rollout sampling policy iteration (DecRSPI) — a new algorithm for multi-agent decision problems formalized as DEC-POMDPs. DecRSPI is designed to improve scalability and tackle problems that lack an explicit model. The algorithm uses Monte-Carlo methods to generate a sample of reachable belief states. Then it computes a joint policy for each belief state based on the rollout estimations. A new policy representation allows us to represent solutions compactly. The key benefits of the algorithm are its linear time complexity over the number of agents, its bounded memory usage and good solution quality. It can solve larger problems that are intractable for existing planning algorithms. Experimental results confirm the effectiveness and scalability of the approach.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “…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., 2012), and modelbased approaches where agents learn in an interleaved fashion to reduce destabilization caused by concurrent learning…”
Multi-agent reinforcement learning as a rehearsal for decentralized planning (2016, neutral): “We show that while RLaR's policy representation is not as scalable as Dec-RSPI's, it produces higher quality policies for problems and horizons studied.”
Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games (2011, background): “on-collaborative graphical BG (Singh et al., 2004) by combining the local payoff functions into individual payoff functions directly at the level of the Bayesian game. 17However, in very recent work, Wu et al. (2010) present results for up to 20 agents on general Dec-POMDPs. 38 Again, this may lead ”
Planning with macro-actions in decentralized POMDPs (2014, background): “Value Time (s) h = 100 h = 200 h = 100 h = 200 O-MBDP(3) 94.4 194.4 133 517 MBDP(3) 92.1 193.4 3084 13875 TBDP 92.8 192.1 427 1372 Table 1: Times and values for larger horizons on the meeting in a grid benchmark. generation (MBDP-IPG) [2], rollout sampling policy iteration (DecRSPI) [33] and trial-b”
Sample Bounded Distributed Reinforcement Learning for Decentralized POMDPs (2012, methodology): “Among work using centralized sampling-based techniques for solving Dec-POMDPs, Wu et. al.”
Monte-Carlo Expectation Maximization for Decentralized POMDPs (2013, unknown): “For the sample size, intuitively, we should start with a small size and increase the size as EM progresses [Wei and Tanner, 1990].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “In particular, Monte-Carlo sampling with policy iteration and the expectation-maximization algorithm, are proposed in [219] and [220], respectively.”
Decentralized POMDPs (2012, unknown): “Finally, sample-based extensions have been proposed (Wu et al, 2010c,b).”