The DOI matches its Crossref record; 56 of the 56 references it cites were found in a registry or an index.
Value-Function Approximations for Partially Observable Markov Decision Processes
Open accessAbstract
Partially observable Markov decision processes (POMDPs) provide an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which states of the system are observable only indirectly, via a set of imperfect or noisy observations. The modeling advantage of POMDPs, however, comes at a price -- exact methods for solving them are computationally very expensive and thus applicable in practice only to very simple problems. We focus on efficient approximation (heuristic) methods that attempt to alleviate the computational problem and trade off accuracy for speed. We have two objectives here. First, we survey various approximation methods, analyze their properties and relations and provide some new insights into their differences. Second, we present a number of new approximation methods and novel refinements of existing techniques. The theoretical results are supported by experiments on a problem from the agent navigation domain.
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
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.
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
Learning Internal Representations by Error Propagation
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1985) · doi:10.21236/ada164453 · Cited by 16,172
Bellman, R. E. (2010) · doi:10.1515/9781400835386 · Cited by 14,588
(1995) · Cited by 10,558
Markov decision processes: Discrete stochastic dynamic programming
Hazeghi, K., & Puterman, M. L. (1995) · Journal of the American Statistical Association · doi:10.2307/2291177 · Cited by 8,037
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
Dynamic Programming and Markov Processes.
Freimer, M., & Howard, R. A. (1961) · Journal of the American Statistical Association · doi:10.2307/2282268 · Cited by 3,378
Decision Analysis: Introductory Lectures on Choices Under Uncertainty.
Klevorick, A. K., & Raiffa, H. (1969) · The Journal of Finance · doi:10.2307/2325714 · Cited by 1,928
Depth-first iterative-deepening
Korf, R. E. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90084-0 · Cited by 1,562
The Optimal Control of Partially Observable Markov Processes over a Finite Horizon
Smallwood, R. D., & Sondik, E. J. (1973) · Operations Research · doi:10.1287/opre.21.5.1071 · Cited by 1,479
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
Learning to act using real-time dynamic programming
Barto, A. G., Bradtke, S. J., & Singh, S. P. (1995) · Artificial Intelligence · doi:10.1016/0004-3702(94)00011-o · Cited by 1,104
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
Residual Algorithms: Reinforcement Learning with Function Approximation
Baird, L. (1995) · Machine Learning Proceedings 1995 · doi:10.1016/b978-1-55860-377-6.50013-x · Cited by 918
Contour tracking by stochastic propagation of conditional density
Isard, M., & Blake, A. (1996) · Lecture Notes in Computer Science · doi:10.1007/bfb0015549 · Cited by 869
Optimal control of Markov processes with incomplete state information
Åström, K. J. (1965) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(65)90154-x · Cited by 854
Learning policies for partially observable environments: Scaling up
Littman, M. L., Cassandra, A. R., & Kaelbling, L. P. (1995) · Machine Learning Proceedings 1995 · doi:10.1016/b978-1-55860-377-6.50052-9 · Cited by 650
Sondik, E. J. (1978) · Operations Research · doi:10.1287/opre.26.2.282 · Cited by 536
A survey of algorithmic methods for partially observed Markov decision processes
Lovejoy, W. S. (1991) · Annals of Operations Research · doi:10.1007/bf02055574 · Cited by 532
The complexity of stochastic games
Condon, A. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90048-k · Cited by 517
Generalization in Reinforcement Learning: Safely Approximating the Value Function
Boyan, J. A., & Moore, A. (1994) · Cited by 508
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes
Kearns, M., Mansour, Y., & Ng, A. Y. (2002) · Machine Learning · doi:10.1023/a:1017932429737 · Cited by 488
Tractable Inference for Complex Stochastic Processes
Boyen, X., & Koller, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.7362 · Cited by 471
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
Feature-based methods for large scale dynamic programming
Tsitsiklis, J. N., & van Roy, B. (1996) · Machine Learning · doi:10.1007/bf00114724 · Cited by 432
Exact and approximate algorithms for partially observable markov decision processes
Kaelbling, L. P., & Cassandra, A. R. (1998) · Cited by 366
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
Cassandra, A. R., Littman, M. L., & Zhang, N. L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.1525 · Cited by 361
Exploiting Structure in Policy Construction
Boutilier, C. E., Dearden, R., & Goldszmidt, M. (1995) · Cited by 346
An algorithm for probabilistic planning
Kushmerick, N., Hanks, S., & Weld, D. S. (1995) · Artificial Intelligence · doi:10.1016/0004-3702(94)00087-h · Cited by 346
Algorithms for Sequential Decision Making
Littman, M. L. (1996) · Cited by 341
Learning Without State-Estimation in Partially Observable Markovian Decision Processes
Singh, S. P., Jaakkola, T., & Jordan, M. I. (1994) · Machine Learning Proceedings 1994 · doi:10.1016/b978-1-55860-335-6.50042-8 · Cited by 327
Computationally Feasible Bounds for Partially Observed Markov Decision Processes
Lovejoy, W. S. (1991) · Operations Research · doi:10.1287/opre.39.1.162 · Cited by 307
Dynamic programming and influence diagrams
Tatman, J. A., & Shachter, R. D. (1990) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/21.52548 · Cited by 266
Stochastic Simulation Algorithms for Dynamic Probabilistic Networks
Kanazawa, K., Koller, D., & Russell, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.4965 · Cited by 219
Madani, O., Hanks, S., & Condon, A. (1999) · Cited by 213
Probabilistic planning with information gathering and contingent execution
Draper, D. L., Hanks, S., & Weld, D. S. (1994) · Cited by 191
Solving POMDPs by Searching in Policy Space
Hansen, E. A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.7380 · Cited by 187
Instance-Based Utile Distinctions for Reinforcement Learning with Hidden State
McCallum, R. A. (1995) · Machine Learning Proceedings 1995 · doi:10.1016/b978-1-55860-377-6.50055-4 · Cited by 181
A computational scheme for reasoning in dynamic probabilistic networks
Kjærulff, U. (1992) · Uncertainty in Artificial Intelligence · doi:10.1016/b978-1-4832-8287-9.50021-9 · Cited by 177
Planning treatment of ischemic heart disease with partially observable Markov decision processes
Hauskrecht, M., & Fraser, H. (2000) · Artificial Intelligence in Medicine · doi:10.1016/s0933-3657(99)00042-1 · Cited by 173
Self-citationThe Optimal Control of Partially Observable Markov Decision Processes.
Sondik, E. J. (1971) · Medical Entomology and Zoology · Cited by 170
Memoryless Policies: Theoretical Limitations and Practical Results
Littman, M. L. (1994) · From Animals to Animats 3 · doi:10.7551/mitpress/3117.003.0041 · Cited by 163
The Optimal Search for a Moving Target When the Search Path Is Constrained
Eagle, J. N. (1984) · Operations Research · doi:10.1287/opre.32.5.1107 · Cited by 159
Approximate dynamic programming for sensor management
Castañón, D. A. (2002) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.1997.657615 · Cited by 154
Algorithms for partially observable Markov decision processes
Cheng, H.-T. (2010) · cIRcle (University of British Columbia) · doi:10.14288/1.0098252 · Cited by 148
Approximating optimal policies for partially observable stochastic domains
Parr, R., & Russell, S. (1995) · Cited by 145
Abstraction and approximate decision-theoretic planning
Dearden, R., & Boutilier, C. E. (1997) · Artificial Intelligence · doi:10.1016/s0004-3702(96)00023-9 · Cited by 139
A heuristic variable grid solution method for POMDPs
Brafman, R. I. (1997) · Cited by 86
Approximate Planning for Factored POMDPs using Belief State SimplificationPreprint
McAllester, D., & Singh, S. P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6719 · Cited by 69
An Improved Policy Iteration Algorithm for Partially Observable MDPs
Hansen, E. A. (1997) · Cited by 69
Markovian Decision Processes with Probabilistic Observation of States
Satia, J., & Lave, R. E. (1973) · Management Science · doi:10.1287/mnsc.20.1.1 · Cited by 47
Exploiting the architecture of dynamic systems
Boyen, X., & Koller, D. (1999) · Cited by 40
Suboptimal Policies, with Bounds, for Parameter Adaptive Decision Processes
Lovejoy, W. S. (1993) · Operations Research · doi:10.1287/opre.41.3.583 · Cited by 27
Finite Memory Estimation and Control of Finite Probabilistic Systems.
Platzman, L. K. (1977) · Cited by 25
Learning Sorting and Decision Trees with POMDPs
Bonet, B., & Geffner, H. (1998) · Cited by 23
Cited by
Active inference and epistemic value
Friston, K., Rigoli, F., Ognibene, D., Mathys, C., Fitzgerald, T., & Pezzulo, G. (2015) · Cognitive Neuroscience · doi:10.1080/17588928.2015.1020053 · Cited by 731
SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces
Kurniawati, H., Hsu, D., & Sun Lee, W. (2008) · Robotics: Science and Systems IV · doi:10.15607/rss.2008.iv.009 · Cited by 759
A survey of point-based POMDP solvers
Shani, G., Pineau, J., & Kaplow, R. (2013) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-012-9200-2 · Cited by 422
(2004) · doi:10.5555/1036843.1036906 · Cited by 417
Perseus: Randomized Point-based Value Iteration for POMDPs
Spaan, M. T. J., & Vlassis, N. (2005) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1659 · Cited by 331
Metadata
- Authors
- Hauskrecht, M.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2000-08-01
- Volume
- 13
- Pages
- 33-94
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W2169294731
- Cited by
- 527
- References
- 56
- FWCI
- 8.33
- Type
- journal article
- Language
- en
- Open access
- diamond
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.