Optimal and Approximate Q-value Functions for Decentralized POMDPs
By Frans Adriaan Oliehoek, Matthijs T. J. Spaan, Nikos A. Vlassis. 2008
582 citations recorded by the source corpus.
Decision-theoretic planning is a popular approach to sequential decision making problems, because it treats uncertainty in sensing and acting in a principled way. In single-agent frameworks like MDPs and POMDPs, planning can be carried out by resorting to Q-value functions: an optimal Q-value function Q* is computed in a recursive manner by dynamic programming, and then an optimal policy is extracted from Q*. In this paper we study whether similar Q-value functions can be defined for decentralized POMDP models (Dec-POMDPs), and how policies can be extracted from such value functions. We define two forms of the optimal Q-value function for Dec-POMDPs: one that gives a normative description as the Q-value function of an optimal pure joint policy and another one that is sequentially rational and thus gives a recipe for computation. This computation, however, is infeasible for all but the smallest problems. Therefore, we analyze various approximate Q-value functions that allow for efficient computation. We describe how they relate, and we prove that they all provide an upper bound to the optimal Q-value function Q*. Finally, unifying some previous approaches for solving Dec-POMDPs, we describe a family of algorithms for extracting policies from such Q-value functions, and perform an experimental evaluation on existing test problems, including a new firefighting benchmark problem.
Subfields: Artificial Intelligence, Reinforcement Learning, Game & Decision Theory
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
- Shimon Whiteson
- Chongjie Zhang
- Wendelin Böhmer
- Jakob N. Foerster
- Tabish Rashid
- Christian Schröder de Witt
- Filippos Christianos
- Bei Peng
In Reinforcement Learning
- Shimon Whiteson
- Chongjie Zhang
- Wendelin Böhmer
- Tabish Rashid
- Christian Schröder de Witt
- Jakob N. Foerster
- Bei Peng
- Tonghan Wang
In Game & Decision Theory
- Shimon Whiteson
- Christian Schröder de Witt
- Jakob N. Foerster
- Tabish Rashid
- Hengyuan Hu
- Chongjie Zhang
- Adam Lerer
- Wendelin Böhmer
Citations in the corpus
- Learning to Communicate with Deep Multi-Agent Reinforcement Learning (2016, background): “Centralised planning and decentralised execution is also a standard paradigm for multi-agent planning [1, 2].”
- Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning (2020, background): “The paradigm of centralised training with decentralised execution (Oliehoek et al., 2008; Kraemer and Banerjee, 2016) has recently attracted attention in the RL community (Jorge et al.”
- Value-Decomposition Networks For Cooperative Multi-Agent Learning (2017, neutral): “This is consistent with the Dec-POMDP framework (Oliehoek et al., 2008; Oliehoek and Amato, 2016).”
- Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “For simplicity, we consider only pure joint policies, as finite-horizon Dec-POMDPs have at least one pure joint optimal policy (Oliehoek et al., 2008).”
- QPLEX: Duplex Dueling Multi-Agent Q-Learning (2020, methodology): “IGM (Individual-Global-Max; Son et al., 2019) is a popular principle to realize effective value-based CTDE, which asserts the consistency between joint and local greedy action selections in the joint action-value Qtot(τ ,a) and individual action-values [Qi(τi, ai)] n i=1: ∀τ ∈ T , argmax a∈A Qtot(τ ”
- Weighted QMIX: Expanding Monotonic Value Function Factorisation (2020, methodology): “We adopt the centralised training and decentralised execution paradigm [20, 14].”
- QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning (2019, methodology): “More recent studies, such as COMA (Foerster et al., 2018), take advantage of CTDE (Oliehoek et al., 2008); actors are trained by a joint critic to estimate a counterfactual baseline designed to gauge each agent’s contribution to the shared task.”
- The StarCraft Multi-Agent Challenge (2019, background): “This gives rise to the paradigm of centralised training with decentralised execution , which has been well-studied in the planning community (Oliehoek et al., 2008; Kraemer & Banerjee, 2016).”
- QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning (2018, background): “The paradigm of centralised training with decentralised execution (Oliehoek et al., 2008; Kraemer & Banerjee, 2016) has recently attracted attention in the RL community (Jorge et al., 2016; Foerster et al., 2018).”
- Multi-Agent Common Knowledge Reinforcement Learning (2018, background): “Cooperative multi-agent tasks with n agents a ∈ A can be modelled as decentralised partially observable Markov decision processes (Dec-POMDPs, Oliehoek et al., 2008).”
- Multiagent Soft Q-Learning (2018, neutral): “If we have a central controller to control the learning process of each agent, then we have centralized training with decentralized execution (Oliehoek, Spaan, and Vlassis 2008).”
- Lossless clustering of histories in decentralized POMDPs (2009, methodology): “This paper considers the optimal solution of finite-horizon Dec-POMDPs [10, 17, 3, 12, 5].”
- Multi-agent deep reinforcement learning: a survey (2021, background): “The CTDE paradigm presents the state-of-the-art practice for learning with multiple agents (Kraemer and Banerjee 2016; Oliehoek et al. 2008).”
- Improving Policies via Search in Cooperative Partially Observable Games (2019, background): “…is known to be NEXP-hard (Bernstein et al. 2002), so much prior work studies environments with structure such as factorized local interactions (Oliehoek et al. 2008), hierarchical policies (Amato et al. 2015), or settings with explicit costs of communication (Goldman and Zilberstein 2003).”
- Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence (2019, background): “Thus, centralized training and decentralized execution are gaining attention, which is a standard paradigm for multi-agent planning [47, 66].”
- Towards Understanding Linear Value Decomposition in Cooperative Multi-Agent Q-Learning (2020, background): “To achieve superior effectiveness and scalability in multi-agent settings, centralized training with decentralized executing (CTDE) has become a popular MARL paradigm (Oliehoek et al., 2008; Kraemer & Banerjee, 2016).”