The Complexity of Decentralized Control of Markov Decision Processes

References

• Altman E., Feinberg E., Shwartz A. Applications of Markov decision processes in telecommunications: A survey. Markov Decision Processes: Models, Methods, Directions, and Open Problems (2001) (Kluwer, New York) Google Scholar
• Babai L., Fortnow L., Lund C. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity (1991) 1:3–40Crossref, Google Scholar
• Blondel V. D., Tsitsiklis J. N. A survey of computational complexity results in systems and control. Automatica (2000) 36(9):1249–1274Crossref, Google Scholar
• Cassandra A., Littman M. L., Zhang N. L. Incremental pruning: A simple, fast, exact method for partially observable Markov decision processes. Proc. Thirteenth Ann. Conf. on Uncertainty in Articial Intelligence (1997) Providence, RI:54–61Google Scholar
• Coradeschi S., Karlsson L., Stone P., Balch T., Kraetzschmar G., Asada M. Overview of RoboCup-99. AI Magazine (2000) 21(3):11–18Google Scholar
• Hansen E. Solving POMDPs by searching in policy space. In Proc. Fourteenth Ann. Conf. on Uncertainty in Artificial Intelligence (1998) Madison, WI:211–219Google Scholar
• Hsu K., Marcus S. I. Decentralized control of finite state Markov processes. IEEE Trans. Auto. Control (1982) AC-27(2):426–431Crossref, Google Scholar
• Jaakkola T., Singh S. P., Jordan M. I. Reinforcement learning algorithm for partially observable Markov decision problems. Proc. Adv. in Neural Inform. Processing Systems (1995) 7:345–352Google Scholar
• Kaelbling L. P., Littman M. L., Cassandra A. R. Planning and acting in partially observable stochastic domains. Artificial Intelligence (1998) 101(1–2):99–134Crossref, Google Scholar
• Lewis H. Complexity of solvable cases of the decision problem for predicate calculus. Proc. Nineteenth Sympos. on the Foundations of Comput. Sci. (1978) Ann Arbor, MI:35–47Crossref, Google Scholar
• Lusena C., Goldsmith J., Li T., Sittinger S., Wells C. My brain is full: When more memory helps. Proc. Fifteenth Conf. on Uncertainty in Artificial Intelligence (1999) Stockholm, Sweden:374–381Google Scholar
• Madani O., Hanks S., Condon A. On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems. Proc. Sixteenth National Conf. on Artificial Intelligence (1999) Orlando, FL:541–548Google Scholar
• Meuleau N., Kim K.-E., Kaelbling L., Cassandra A. R. Solving POMDPs by searching the space of finite policies. Proc. Fifteenth Conf. on Uncertainty in Artificial Intelligence (1999) Stockholm, Sweden:417–426Google Scholar
• Mundhenk M., Goldsmith J., Lusena C., Allender E. Complexity of finite-horizon Markov decision process problems. J. ACM (2000) 47(4):681–720Crossref, Google Scholar
• Ooi J. M., Wornell G. W. Decentralized control of a multiple access broadcast channel: Performance bounds. In Proc. 35th Conf. on Decision and Control (1996) Kobe, Japan:293–298Crossref, Google Scholar
• Papadimitriou C. H.Computational Complexity (1994) (Addison-Wesley, Reading, MA) Google Scholar
• Papadimitriou C. H., Tsitsiklis J. On the complexity of designing distributed protocols. Inform. Control (1982) 53:211–218Crossref, Google Scholar
• Papadimitriou C. H., Tsitsiklis J. Intractable problems in control theory. SIAM J. Control Optim. (1986) 24(4):639–654Crossref, Google Scholar
• Papadimitriou C. H., Tsitsiklis J. The complexity of Markov decision processes. Math. Oper. Res. (1987) 12(3):441–450Link, Google Scholar
• Peshkin L., Kim K.-E., Meuleau N., Kaelbling L. P. Learning to cooperate via policy search. Proc. Sixteenth Internat. Conf. on Uncertainty in Artificial Intelligence (2000) Stanford, CA:348–363Google Scholar
• Peterson G. L., Reif J. R. Multiple-person alternation. 20th Ann. Sympos. on Foundations of Comput. Sci. (1979) San Juan, PR:348–363Crossref, Google Scholar
• Puterman M. L.Markov Decision Processes (1994) (J. Wiley & Sons, New York) Crossref, Google Scholar
• Schneider J., Wong W.-K., Moore A., Riedmiller M. Distributed value functions. Proc. Sixteenth Internat. Conf. on Machine Learning (1999) Bled, Slovenia:371–378Google Scholar
• Zhang W. Algorithms for partially observable markov decision processes. (2001) . Ph.D. thesis, Hong Kong University of Science and Technology, Kowloon, Hong KongCrossref, Google Scholar