The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
The Complexity of Decentralized Control of Markov Decision Processes
Abstract
We consider decentralized control of Markov decision processes and give complexity bounds on the worst-case running time for algorithms that find optimal solutions. Generalizations of both the fully observable case and the partially observable case that allow for decentralized control are described. For even two agents, the finite-horizon problems corresponding to both of these models are hard for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov decision processes. In contrast to the problems involving centralized control, the problems we consider provably do not admit polynomial-time algorithms. Furthermore, assuming EXP ≠ NEXP, the problems require superexponential time to solve in the worst case.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Sufficiently expressive contracting in fully-observed Markov games is a reduction from solving social dilemmas to solving decentralized Markov decision processes (DEC-MDPs) at equilibrium.
“One way to interpret this is that sufficiently expressive contracting in fullyobserved Markov games is a reduction from solving social dilemmas to solving decentralized Markov decision processes (DEC-MDPs) at equilibrium [2].”
From Formal contracts mitigate social dilemmas in multi-agent reinforcement learning (2024) · cites this paper as [2]
Citations
Cites
Puterman, M. L. (1994) · Wiley series in probability and statistics · doi:10.1002/9780470316887 · Cited by 6,057
Planning and acting in partially observable stochastic domains
Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(98)00023-x · Cited by 4,149
Brucker, P. (1995) · Springer eBooks · doi:10.1007/978-3-662-03088-2_3 · Cited by 2,388
The Complexity of Markov Decision Processes
Papadimitriou, C. H., & Tsitsiklis, J. N. (1987) · Mathematics of Operations Research · doi:10.1287/moor.12.3.441 · Cited by 1,329
A survey of computational complexity results in systems and control
Blondel, V. D., & Tsitsiklis, J. N. (2000) · Automatica · doi:10.1016/s0005-1098(00)00050-9 · Cited by 740
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1992) · Computational Complexity · doi:10.1007/bf01200430 · Cited by 531
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1991) · Computational Complexity · doi:10.1007/bf01200056 · Cited by 489
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision ProcessesPreprint
Cassandra, A. R., Littman, M. L., & Zhang, N. L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.1525 · Cited by 367
Reinforcement Learning Algorithm for Partially Observable Markov Decision Problems
Jaakkola, T., Singh, S. P., & Jordan, M. I. (1994) · Cited by 361
Learning to Cooperate via Policy SearchPreprint
Peshkin, L., Kim, K.-E., Meuleau, N., & Kaelbling, L. P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.1484 · Cited by 217
Madani, O., Hanks, S., & Condon, A. (1999) · Cited by 213
Solving POMDPs by Searching in Policy SpacePreprint
Hansen, E. A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.7380 · Cited by 190
Complexity of finite-horizon Markov decision process problems
Mundhenk, M., Goldsmith, J., Lusena, C., & Allender, E. (2000) · Journal of the ACM · doi:10.1145/347476.347480 · Cited by 159
Schneider, J., Wong, W., Moore, A., et al. (2018) · doi:10.1184/r1/6554609.v1 · Cited by 156
Peterson, G. L., & Reif, J. H. (1979) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1979.25 · Cited by 155
Solving POMDPs by Searching the Space of Finite PoliciesPreprint
Meuleau, N., Kim, K.-E., Kaelbling, L. P., & Cassandra, A. R. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6720 · Cited by 146
Intractable Problems in Control Theory
Papadimitriou, C. H., & Tsitsiklis, J. (1986) · SIAM Journal on Control and Optimization · doi:10.1137/0324038 · Cited by 140
Intractable problems in control theory
Papadimitriou, C. H., & Tsitsiklis, J. N. (1985) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.1985.268670 · Cited by 134
Complexity of solvable cases of the decision problem for the predicate calculus
Lewis, H. R. (1978) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1978.9 · Cited by 76
Decentralized control of finite state Markov processes
Hsu, K., & Marcus, S. I. (1982) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1982.1102924 · Cited by 57
On the complexity of designing distributed protocols
Papadimitriou, C. H., & Tsitsiklis, J. N. (1982) · Information and Control · doi:10.1016/s0019-9958(82)91034-8 · Cited by 47
Decentralized control of a multiple access broadcast channel: performance bounds
Ooi, J. M., & Wornell, G. W. (2002) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.1996.574318 · Cited by 47
Algorithms for partially observable Markov decision processes
Zhang, W. (2001) · doi:10.14711/thesis-b710758 · Cited by 21
Coradeschi, S., Karlsson, L., Stone, P., et al. (2000) · AI Magazine · doi:10.1609/aimag.v21i3.1516 · Cited by 20
My Brain is Full: When More Memory HelpsPreprint
Lusena, C., Li, T., Sittinger, S., et al. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6715 · Cited by 8
Flagged first, then by citations
Research works printed but not linked: 10
- Altman E., 2001, Markov Decision Processes: Models, Methods, Directions, and Open Problems
- Cassandra A., 1997, Proc. Thirteenth Ann. Conf. on Uncertainty in Articial Intelligence, 54
- Coradeschi S., 2000, AI Magazine, 21, 11
- Hansen E., 1998, In Proc. Fourteenth Ann. Conf. on Uncertainty in Artificial Intelligence, 211
- Jaakkola T., 1995, Proc. Adv. in Neural Inform. Processing Systems, 7, 345
- Lusena C., 1999, Proc. Fifteenth Conf. on Uncertainty in Artificial Intelligence, 374
- Madani O., 1999, Proc. Sixteenth National Conf. on Artificial Intelligence, 541
- Meuleau N., 1999, Proc. Fifteenth Conf. on Uncertainty in Artificial Intelligence, 417
- Peshkin L., 2000, Proc. Sixteenth Internat. Conf. on Uncertainty in Artificial Intelligence, 348
- Schneider J., 1999, Proc. Sixteenth Internat. Conf. on Machine Learning, 371
Cited by
Sorted by citations
Recent Advances in Hierarchical Reinforcement Learning
Barto, A. G., & Mahadevan, S. (2003) · Discrete Event Dynamic Systems · doi:10.1023/a:1025696116075 · Cited by 317
A collective AI via lifelong learning and sharing at the edge
Soltoggio, A., Ben-Iwhiwhu, E., Braverman, V., Eaton, E., Epstein, B., Ge, Y., Halperin, L., How, J., Itti, L., Jacobs, M. A., et al. (2024) · Nature Machine Intelligence · doi:10.1038/s42256-024-00800-2 · Cited by 51
Multi-Agent Risks from Advanced AI
Hammond, L., Chan, A., Clifton, J., Hoelscher-Obermaier, J., Khan, A., McLean, E., Smith, C., Barfuss, W., Foerster, J., Gavenčiak, T., et al. (2025) · arXiv · doi:10.48550/arxiv.2502.14143 · Cited by 305
Formal contracts mitigate social dilemmas in multi-agent reinforcement learning
Haupt, A., Christoffersen, P., Damani, M., & Hadfield-Menell, D. (2024) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-024-09682-5 · Cited by 5
Metadata
- Authors
- Bernstein, D. S., Givan, R., Immerman, N., & Zilberstein, S.
- Affiliations
- University of Massachusetts Amherst (US)
- Purdue University West Lafayette (US)
- Department of Computer Science, University of Massachusetts, Amherst, MA 01003
- ORCID
- Immerman, Neil
- Venue
- Mathematics of Operations Research
- Published
- 2002-11
- Volume
- 27
- Issue
- 4
- Pages
- 819-840
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2088956500
- Cited by
- 1,192
- References
- 25
- Citations by year
- 2026: 53 · 2025: 66 · 2024: 67 · 2023: 66 · 2022: 51 · 2021: 101 · 2020: 76 · 2019: 45 · 2018: 48 · 2017: 46 · 2016: 48 · 2015: 56 · 2014: 55 · 2013: 74 · 2012: 59
- FWCI
- 18.03
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Mathematics of Operations Research (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
- Keywords
- decentralized control, Markov decision process, computational complexity, partially observable Markov decision processes, multi-agent systems, optimal control, centralized vs decentralized control
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
