Dynamic Programming for Partially Observable Stochastic Games

By Eric A. Hansen, Daniel S. Bernstein, Shlomo Zilberstein. 2004

681 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Action Semantics Network: Considering the Effects of Actions in Multiagent Systems (2019, background): “Considering the fact that agents may not have access to the complete environmental information, we follow previous work’s settings and model the multiagent learning problems as partially observable stochastic games (POSGs) (Hansen et al., 2004).”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, methodology): “One is to try to extend the results of this paper to partially observable stochastic games (POSGs) (Hansen et al., 2004), which are Dec-POMDPs with an individual reward function for each agent.”
A Survey on Machine-Learning Techniques in Cognitive Radios (2013, background): “It is an extension of the partially observable Markov decision process (POMDP) [98], [99] framework and a specific case of a partially observable stochastic game (POSG) [100].”
Point-based Dynamic Programming for DEC-POMDPs (2006, unknown): “The point-based multi-agent dynamic programming approach addresses two major drawbacks of the DP approach presented in (Hansen, Bernstein, & Zilberstein 2004), namely the computationally expensive linear programming part necessary to identify dominated policies, and the dif-ﬁculty to exclude those…”
Robust Opponent Modeling via Adversarial Ensemble Reinforcement Learning in Asymmetric Imperfect-Information Games (2019, background): “Partially observable Markov decision process (POMDP) [13] decentralized-POMDP (Dec-POMDP) [19] and Partially observable stochastic games (POSG) [8] are the decision-making models for single agent, multiagent fully cooperative and multiagent general sum scenarios, respectively.”
Rethinking Formal Models of Partially Observable Multiagent Decision Making (2019, background): “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).”
Monte-Carlo Expectation Maximization for Decentralized POMDPs (2013, unknown): “A rich set of techniques have been developed to solve DEC- POMDPs optimally [Hansen et al., 2004; Szer et al., 2005; Aras et al., 2007; Spaan et al., 2011] or approximately [Nair et al., 2003; Seuken and Zilberstein, 2007; Bernstein et al., 2009; Wu et al., 2010; Dibangoye et al., 2011; Pajarinen…”
Point-based incremental pruning heuristic for solving finite-horizon DEC-POMDPs (2009, methodology): “Comparison is made according to DEC-POMDP benchmarks from the literature: the multi-access broadcast channel (MABC) problem [6], the multi-agent tiger problem [7] and the COOPERATIVE BOX-PUSHING problem [11].”
Lossless clustering of histories in decentralized POMDPs (2009, background): “In fact, only a ”multiagent belief” specified over states and future policies of other agents has been shown to be a sufficient statistic in DecPOMDPs [10].”
Solving Transition Independent Decentralized Markov Decision Processes (2004, background): “Computing the optimal solution to the general class is NEXP-complete, and the only general algorithm for solving this problem optimally (Hansen et al., 2004) requires further development before it can be applied to the kind of problems we target in this paper.”
Dealing with Non-Stationarity in MARL via Trust-Region Decomposition (2021, background): “POSG (Hansen et al., 2004) is denoted as a seven-tuple via the stochastic game (or Markov game) , where n denotes the number of agents; I represents the agent space; S represents the ﬁnite set of states; A i , O i denote a ﬁnite action set and a ﬁnite observation set of agent i ∈ I respectively; =1 ”
Planning with macro-actions in decentralized POMDPs (2014, methodology): “Solving Dec-POMDPs is very computationally challenging (NEXP for optimal finite-horizon solutions [7]), but many problems may have structure that allows near optimal solutions to be found quickly.”
Local Information Agent Modelling in Partially-Observable Environments (2021, methodology): “We model the problem as a Partially-Observable Stochastic Game (POSG) [Shapley, 1953, Hansen et al., 2004] which consists of N agents I = { 1 , 2 , ..., N } , a state space S , the joint action space A = A 1 × ... × A N , a transition function P : S × A × S → [0 , 1] specifying the transition…”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, background): “Stochastic games usually assume that agents have complete information about the state of the game, a more general model are partially observable stochastic games (POSGs) (Bernstein et al., 2004).”
Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs (2007, methodology): “The ﬁrst non-trivial algorithm for solving DEC-POMDPs used a bottom-up approach [Hansen et al. , 2004].”
A Comprehensive Survey of Multiagent Reinforcement Learning (2008, unknown): “sion processes [129], as in [130], [131].”