A Framework for Sequential Planning in Multi-Agent Settings

By Piotr J. Gmytrasiewicz, Prashant Doshi. 2005

523 citations recorded by the source corpus.

This paper extends the framework of partially observable Markov decision processes (POMDPs) to multi-agent settings by incorporating the notion of agent models into the state space. Agents maintain beliefs over physical states of the environment and over models of other agents, and they use Bayesian updates to maintain their beliefs over time. The solutions map belief states to actions. Models of other agents may include their belief states and are related to agent types considered in games of incomplete information. We express the agents' autonomy by postulating that their models are not directly manipulable or observable by other agents. We show that important properties of POMDPs, such as convergence of value iteration, the rate of convergence, and piece-wise linearity and convexity of the value functions carry over to our framework. Our approach complements a more traditional approach to interactive settings which uses Nash equilibria as a solution paradigm. We seek to avoid some of the drawbacks of equilibria which may be non-unique and do not capture off-equilibrium behaviors. We do so at the cost of having to represent, process and continuously revise models of other agents. Since the agent's beliefs may be arbitrarily nested, the optimal solutions to decision making problems are only asymptotically computable. However, approximate belief updates and approximately optimal plans are computable. We illustrate our framework using a simple application domain, and we show examples of belief updates and value functions.

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

In Management Science and Operations Research

Citations in the corpus

The Hanabi Challenge: A New Frontier for AI Research (2019, background): “signiﬁcant ﬁnancial support for this work that could have inﬂuenced its outcome.”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, methodology): “This is the approach as chosen in the Interactive POMDP (I-POMDP) framework (Gmytrasiewicz & Doshi, 2005).”
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “There is a significant amount of work that deals with the case of decentralized cooperative problems [76, 79], and in the general setting by extending the notion of belief states and Bayesian updating from POMDPs [28].”
Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning (2018, background): “In interactive POMDPs (I-POMDPs; Gmytrasiewicz & Doshi 2005), agents model each other’s beliefs, beliefs over these beliefs, and so on, but this is often computationally intractable.”
A survey and critique of multiagent deep reinforcement learning (2018, methodology): “works in type-based reasoning from game theory [239, 136] later applied in AI [238, 11, 240].”
Learning against sequential opponents in repeated stochastic games (2017, background): “A general and highly complex model are I-POMDPs [12] which are a framework for decision making in uncertain multiagent settings.”
Learning to Communicate Implicitly by Actions (2018, result): “In contrast to works such as IPOMDP (Gmytrasiewicz and Doshi 2005) and PR2 (Wen et al. 2019) where the nested belief is embedded into the training agent’s opponent model, we incorporate level-1 nested belief “I believe that you believe” into our policy by a novel auxiliary reward.”
Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning (2019, unknown): “Recently, a promising methodology from game theory – recursive reasoning – has become popular in opponent modeling (Gmytrasiewicz & Durfee, 2000; Camerer et al., 2004; Gmytrasiewicz & Doshi, 2005; De Weerd et al., 2013b).”
A Multitask Representation Using Reusable Local Policy Templates (2012, background): “An elegant mechanism for posing such problems with hidden or incomplete information is the partially observable Markov decision process (POMDP), or the I-POMDP in the interactive multiagent setting (Gmytrasiewicz and Doshi 2005).”
Rational quantitative attribution of beliefs, desires and percepts in human mentalizing (2017, background): “The joint system of the observer and the agent can also be seen as a special case of an interactive POMDP (or I-POMDP 32 ), a generalization of POMDPs to multi-agent systems in which agents recursively model each other in a hierarchy of levels; in I-POMDP terms, the observer builds a non-recursive L”
Point-based Dynamic Programming for DEC-POMDPs (2006, unknown): “Some authors have tried to address this by deﬁning beliefs over other agents’ beliefs (Gmytrasiewicz & Doshi 2005).”
Multi-Agent Deep Reinforcement Learning (2016, background): “they do not share a single reward function), the problem becomes more difficult and approaches such as I-POMDPs [5] must be used to allow agents to reason about other self-interested agents in the environment.”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, methodology): “I-POMDPs extend POMDPs incorporating models of other agents into the regular state space.”
Q-value Heuristics for Approximate Solutions of Dec-POMDPs (2007, methodology): “Approximate policy search via Bayesian games Besides brute force search, more sophisticated methods of searching for policies have been proposed in recent years (Hansen, Bernstein, & Zilberstein 2004; Beckeret al. 2004; Emery-Montemerloet al. 2004; Gmytrasiewicz & Doshi 2005).”