The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Efficient Solution Algorithms for Factored MDPs
Abstract
This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). Factored MDPs represent a complex state space using state variables and the transition model using a dynamic Bayesian network. This representation often allows an exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in the representation size. In this paper, we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both additive and context-specific structure in a factored MDP. A central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that more directly minimizes the terms that appear in error bounds for approximate MDP algorithms. We provide experimental results on problems with over 10^40 states, demonstrating a promising indication of the scalability of our approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Figures











Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Such a program is most economical when it is factored by object type, with one transition rule shared across all objects of a type, so that few parameters support many predictions and a rule learned from one object transfers to the rest [Diuk et al., 2008, Guestrin et al., 2003, Džeroski et al., 2001].”
From OPINE-World: Programmatic World Modeling with Ontology-error-Prioritized Interactive Exploration for ARC-AGI-3 (2026) · cites this paper as Guestrin et al., 2003
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1988) · Cited by 16,582
Decisions with Multiple Objectives: Preferences and Value Tradeoffs.
Tsoukias, A., Keeney, R. L., & Raiffa, H. (1994) · The Journal of the Operational Research Society · doi:10.2307/2584151 · Cited by 8,370
Learning to predict by the methods of temporal differences
Sutton, R. S. (1988) · Machine Learning · doi:10.1007/bf00115009 · Cited by 5,148
An analysis of temporal-difference learning with function approximation
Tsitsiklis, J. N., & Van Roy, B. (1997) · IEEE Transactions on Automatic Control · doi:10.1109/9.580874 · Cited by 1,194
Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
Boutilier, C., Dean, T., & Hanks, S. (1999) · Journal of Artificial Intelligence Research · doi:10.1613/jair.575 · Cited by 1,074
A model for reasoning about persistence and causation
Dean, T., & Kanazawa, K. (1989) · Computational Intelligence · doi:10.1111/j.1467-8640.1989.tb00324.x · Cited by 999
The Linear Programming Approach to Approximate Dynamic Programming
de Farias, D. P., & Van Roy, B. (2003) · Operations Research · doi:10.1287/opre.51.6.850.24925 · Cited by 687
Markov Decision Processes: Discrete Stochastic Dynamic Programming
Puterman, M. L. (2005) · Cited by 588
Bucket elimination: A unifying framework for reasoning
Dechter, R. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00059-4 · Cited by 583
Stable Function Approximation in Dynamic Programming
Gordon, G. J. (1995) · Machine Learning Proceedings 1995 · doi:10.1016/b978-1-55860-377-6.50040-2 · Cited by 446
SPUDD: Stochastic Planning using Decision Diagrams
Hoey, J., St‐Aubin, R., Hu, A. J., & Boutilier, C. E. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6704 · Cited by 380
On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
de Farias, D. P., & Van Roy, B. (2004) · Mathematics of Operations Research · doi:10.1287/moor.1040.0094 · Cited by 373
Stochastic dynamic programming with factored representations
Boutilier, C., Dearden, R., & Goldszmidt, M. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00033-3 · Cited by 361
Generalized polynomial approximations in Markovian decision processes
Schweitzer, P. J., & Seidmann, A. (1985) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(85)90317-8 · Cited by 330
Finding approximate separators and computing tree width quickly
Reed, B. A. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129734 · Cited by 179
Solving very large weakly coupled Markov decision processes
Meuleau, N., Hauskrecht, M., Kim, K.-E., Peshkin, L., Kaelbling, L. P., Dean, T., & Boutilier, C. E. (1998) · Cited by 171
Note on Jordan elimination, linear programming and Tchebycheff approximation
Stiefel, E. (1960) · Numerische Mathematik · doi:10.1007/bf01386203 · Cited by 161
Computing Factored Value Functions for Policies in Structured MDPs
Koller, D., & Parr, R. (1999) · Cited by 141
Self-citationAbstraction and approximate decision-theoretic planning
Dearden, R., & Boutilier, C. E. (1997) · Artificial Intelligence · doi:10.1016/s0004-3702(96)00023-9 · Cited by 139
APRICODD: Approximate Policy Construction Using Decision Diagrams
St‐Aubin, R., Hoey, J., & Boutilier, C. E. (2000) · Cited by 116
Context-specific multiagent coordination and planning with factored MDPs
Guestrin, C., Venkataraman, S., & Koller, D. (2002) · doi:10.5555/777092.777134 · Cited by 106
Self-citationFeature-Based Methods for Large Scale Dynamic Programming
Tsitsiklis, J. N., & Roy, B. V. (1996) · Springer eBooks · doi:10.1007/978-0-585-33656-5_5 · Cited by 90
Learning and value function approximation in complex decision processes
Roy, B. V., & Tsitsiklis, J. N. (1998) · Cited by 77
A sufficiently fast algorithm for finding close to optimal clique trees
Becker, A., & Geiger, D. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00075-8 · Cited by 46
Solving Factored POMDPs with Linear Value Functions
Guestrin, C., Koller, D., & Parr, R. (n.d.) · Cited by 37
Self-citation
Research works printed but not linked: 31
- Arnborg, S., Corneil, D. G., & Proskurowski, A. (1987). Complexity of finding embeddings in a K-tree. SIAM Journal of Algebraic and Discrete Methods, 8 (2), 277 -284.
- Bellman, R., Kalaba, R., & Kotkin, B. (1963). Polynomial approximation -a new compu- tational technique in dynamic programming. Math. Comp., 17 (8), 155-161.
- Bellman, R. E. (1957). Dynamic Programming. Princeton University Press, Princeton, New Jersey.
- Bertele, U., & Brioschi, F. (1972). Nonserial Dynamic Programming. Academic Press, New York.
- Boutilier, C., & Dearden, R. (1996). Approximating value trees in structured dynamic programming. In Proc. ICML, pp. 54-62.
- Boutilier, C., Dearden, R., & Goldszmidt, M. (1995). Exploiting structure in policy con- struction. In Proc. IJCAI, pp. 1104-1111.
- Cheney, E. W. (1982). Approximation Theory (2nd edition). Chelsea Publishing Co., New York, NY.
- Dean, T., Kaelbling, L. P., Kirman, J., & Nicholson, A. (1993). Planning with deadlines in stochastic domains. In Proceedings of the Eleventh National Conference on Artificial Intelligence (AAAI-93), pp. 574-579, Washington, D.C. AAAI Press.
- Dean, T., & Givan, R. (1997). Model minimization in Markov decision processes. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI- 97), pp. 106-111, Providence, Rhode Island, Oregon. AAAI Press.
- Morgan Kaufmann.
- Guestrin, C. E., Koller, D., & Parr, R. (2001a). Max-norm projections for factored MDPs. In Proceedings of the Seventeenth International Joint Conference on Artificial Intel- ligence (IJCAI-01), pp. 673 -680, Seattle, Washington.
- Morgan Kaufmann.
- Guestrin, C. E., Koller, D., & Parr, R. (2001b). Multiagent planning with factored MDPs. In 14th Neural Information Processing Systems (NIPS-14), pp. 1523-1530, Vancouver, Canada.
- Hoey, J., St-Aubin, R., Hu, A., & Boutilier, C. (1999). SPUDD: Stochastic planning us- ing decision diagrams. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI-99), pp. 279-288, Stockholm, Sweden.
- Morgan Kaufmann.
- Howard, R. A., & Matheson, J. E. (1984). Influence diagrams. In Howard, R. A., & Math- eson, J. E. (Eds.), Readings on the Principles and Applications of Decision Analysis, pp. 721-762. Strategic Decisions Group, Menlo Park, California.
- Kim, K.-E., & Dean, T. (2001). Solving factored Mdps using non-homogeneous partition- ing. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 683 -689, Seattle, Washington.
- Morgan Kaufmann.
- Morgan Kaufmann.
- Koller, D., & Parr, R. (2000). Policy iteration for factored MDPs. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI-00), pp. 326 - 334, Stanford, California.
- Morgan Kaufmann.
- Morgan Kaufmann, San Mateo, California.
- Schuurmans, D., & Patrascu, R. (2001). Direct value-approximation for factored MDPs. In Advances in Neural Information Processing Systems (NIPS-14), pp. 1579-1586, Vancouver, Canada.
- Simon, H. A. (1981). The Sciences of the Artificial (second edition). MIT Press, Cambridge, Massachusetts.
- Jordan, M. I., Kearns, M. J., & Solla, S. A. (Eds.), Advances in Neural Information Processing Systems, Vol. 10. The MIT Press.
- Tadepalli, P., & Ok, D. (1996). Scaling up average reward reinforcmeent learning by approx- imating the domain models and the value function. In Proceedings of the Thirteenth International Conference on Machine Learning, Bari, Italy.
- Morgan Kaufmann.
- Tatman, J. A., & Shachter, R. D. (1990). Dynamic programming and influence diagrams. IEEE Transactions on Systems, Man and Cybernetics, 20 (2), 365-379.
- Yedidia, J., Freeman, W., & Weiss, Y. (2001). Generalized belief propagation. In Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference, pp. 689-695, Denver, Colorado. MIT Press.
- Zhang, N., & Poole, D. (1999). On the role of context-specific independence in probabilistic reasoning. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99), pp. 1288-1293.
- Morgan Kaufmann.
Cited by
Action understanding as inverse planning
Baker, C. L., Saxe, R., & Tenenbaum, J. B. (2009) · Cognition · doi:10.1016/j.cognition.2009.07.005 · Cited by 920
A survey and critique of multiagent deep reinforcement learning
Hernandez-Leal, P., Kartal, B., & Taylor, M. E. (2019) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-019-09421-1 · Cited by 671
Uncertain convex programs: randomized solutions and confidence levels
Calafiore, G., & Campi, M. C. (2005) · Mathematical Programming · doi:10.1007/s10107-003-0499-y · Cited by 659
On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
de Farias, D. P., & Van Roy, B. (2004) · Mathematics of Operations Research · doi:10.1287/moor.1040.0094 · Cited by 373
System Design Perspective for Human-Level Agents Using Deep Reinforcement Learning: A Survey
Nguyen, N. D., Nguyen, T., & Nahavandi, S. (2017) · IEEE Access · doi:10.1109/access.2017.2777827 · Cited by 100
Metadata
- Authors
- Guestrin, C., Koller, D., Parr, R., & Venkataraman, S.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2003-10-01
- Volume
- 19
- Pages
- 399-468
- ISSN
- 1076-9757
- Cited by
- 169
- References
- 25
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.