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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Cited by
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
Zhang, K., Yang, Z., & Başar, T. (2021) · Studies in Systems, Decision and Control · doi:10.1007/978-3-030-60990-0_12 · Cited by 1,264
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
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
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
Online Planning Algorithms for POMDPs
Ross, S., Pineau, J., Paquet, S., & Chaib-draa, B. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2567 · Cited by 496
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
Anytime Point-Based Approximations for Large POMDPs
Pineau, J., Gordon, G., & Thrun, S. (2006) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2078 · Cited by 370
A Framework for Sequential Planning in Multi-Agent Settings
Gmytrasiewicz, P. J., & Doshi, P. (2005) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1579 · Cited by 360
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
Reinforcement Learning: A Tutorial Survey and Recent Advances
Gosavi, A. (2009) · INFORMS Journal on Computing · doi:10.1287/ijoc.1080.0305 · Cited by 326
Partially Observable Markov Decision Processes
Spaan, M. T. J. (2012) · Adaptation, Learning, and Optimization · doi:10.1007/978-3-642-27645-3_12 · Cited by 315
Belief space planning assuming maximum likelihood observations
Platt, R., Tedrake, R., Kaelbling, L., & Lozano-Perez, T. (2010) · Robotics: Science and Systems VI · doi:10.15607/rss.2010.vi.037 · Cited by 298
Optimal and Approximate Q-value Functions for Decentralized POMDPs
Oliehoek, F. A., Spaan, M. T. J., & Vlassis, N. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2447 · Cited by 265
An Event-Triggered ADP Control Approach for Continuous-Time System With Unknown Internal States
Zhong, X., & He, H. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2016.2523878 · Cited by 263
A POMDP formulation of preference elicitation problems
Boutilier, C. E. (2002) · doi:10.5555/777092.777132 · Cited by 263
Finding approximate POMDP solutions through belief compression
Roy, N., Gordon, G., & Thrun, S. (2005) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1496 · Cited by 254
Planning and navigation as active inference
Kaplan, R., & Friston, K. J. (2018) · Biological Cybernetics · doi:10.1007/s00422-018-0753-2 · Cited by 203
Indelman, V., Carlone, L., & Dellaert, F. (2015) · The International Journal of Robotics Research · doi:10.1177/0278364914561102 · Cited by 154
“We remark that the GBS is nothing more than a standard belief space over a larger state (Hauskrecht, 2000), and we use this terminology to make explicit the fact that our state space also includes the world state.”
MethodAn online POMDP algorithm for complex multiagent environments
Paquet, S., Tobin, L., & Chaib-draa, B. (2005) · Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems · doi:10.1145/1082473.1082620 · Cited by 92
Learning State-Variable Relationships in POMCP: A Framework for Mobile Robots
Zuccotto, M., Piccinelli, M., Castellini, A., Marchesini, E., & Farinelli, A. (2022) · Frontiers in Robotics and AI · doi:10.3389/frobt.2022.819107 · Cited by 2
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.