The Complexity of Decentralized Control of Markov Decision Processes

DOI10.1287/moor.27.4.819.297zbMath1082.90593OpenAlexW2088956500WikidataQ56812794 ScholiaQ56812794MaRDI QIDQ5704111

Neil Immerman, Shlomo Zilberstein, Daniel S. Bernstein, Robert L. Givan

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.27.4.819.297

zbMATH Keywords

computational complexitydecentralized controlMarkov decision process

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Markov and semi-Markov decision processes (90C40) Stochastic systems in control theory (general) (93E03)

Related Items (42)

A partially observable stochastic zero-sum game for a network epidemic control problem ⋮ Environment-driven distributed evolutionary adaptation in a population of autonomous robotic agents ⋮ The factored policy-gradient planner ⋮ Knowledge-based strategies for multi-agent teams playing against nature ⋮ MULTIAGENT EXPEDITION WITH GRAPHICAL MODELS ⋮ Recognizing and learning models of social exchange strategies for the regulation of social interactions in open agent societies ⋮ Probabilistic bisimulation for realistic schedulers ⋮ The complexity of reachability in parametric Markov decision processes ⋮ A mean-variance optimization problem for discounted Markov decision processes ⋮ Proactive Dynamic Distributed Constraint Optimization Problems ⋮ Misinformation and Disinformation in Modern Warfare ⋮ TEAMSTER: model-based reinforcement learning for ad hoc teamwork ⋮ A decentralised multi-agent system for rail freight traffic management ⋮ Complexity of planning for connected agents in a partially known environment ⋮ Partially observed optimal control of local and remote controllers ⋮ Provably efficient reinforcement learning in decentralized general-sum Markov games ⋮ Privacy stochastic games in distributed constraint reasoning ⋮ Controlling a Fleet of Unmanned Aerial Vehicles to Collect Uncertain Information in a Threat Environment ⋮ Exploiting symmetries for single- and multi-agent partially observable stochastic domains ⋮ Decentralized MDPs with sparse interactions ⋮ Multi-robot inverse reinforcement learning under occlusion with estimation of state transitions ⋮ On the Complexity of Reachability in Parametric Markov Decision Processes ⋮ A survey of inverse reinforcement learning: challenges, methods and progress ⋮ Unnamed Item ⋮ Infinite games with finite knowledge gaps ⋮ Online planning for multi-agent systems with bounded communication ⋮ Multi-agent reinforcement learning algorithm to solve a partially-observable multi-agent problem in disaster response ⋮ Probabilistic Bisimulation for Realistic Schedulers ⋮ Negotiating team formation using deep reinforcement learning ⋮ Distributed Synthesis in Continuous Time ⋮ The Hanabi challenge: a new frontier for AI research ⋮ An action language for multi-agent domains ⋮ On the Complexity of Value Iteration ⋮ A tutorial on partially observable Markov decision processes ⋮ Multi-agent reinforcement learning: a selective overview of theories and algorithms ⋮ Safe Multi-Agent Pathfinding with Time Uncertainty ⋮ Constrained Multiagent Markov Decision Processes: a Taxonomy of Problems and Algorithms ⋮ Unnamed Item ⋮ Dynamic process scheduling and resource allocation in distributed environment: an agent-based modelling and simulation ⋮ A Survey of Opponent Modeling in Adversarial Domains ⋮ A leader-follower partially observed, multiobjective Markov game ⋮ Value of information for a leader-follower partially observed Markov game

Uses Software

• POMDP

This page was built for publication: The Complexity of Decentralized Control of Markov Decision Processes