On Solving a Stochastic Shortest-Path Markov Decision Process as Probabilistic Inference
Open accessThe DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Abstract
Previous work on planning as active inference addresses finite horizon problems and solutions valid for online planning. We propose solving the general Stochastic Shortest-Path Markov Decision Process (SSP MDP) as probabilistic inference. Furthermore, we discuss online and offline methods for planning under uncertainty. In an SSP MDP, the horizon is indefinite and unknown a priori. SSP MDPs generalize finite and infinite horizon MDPs and are widely used in the artificial intelligence community. Additionally, we highlight some of the differences between solving an MDP using dynamic programming approaches widely used in the artificial intelligence community and approaches used in the active inference community.
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?
In the citing paper
“As concluded in [43], for the parts of a task subject to frequent unpredictable changes, computing locally an online plan as we do with active inference is preferable to offline policies.”
From Active Inference and Behavior Trees for Reactive Action Planning and Execution in Robotics (2023) · cites this paper as [43]
Citations
Cites
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
(2012) · Cited by 9,062
Koller, D., & Friedman, N. (2009) · The MIT Press eBooks · Cited by 7,555
Introduction to Reinforcement Learning
Sutton, R. S., & Barto, A. G. (1998) · The MIT Press eBooks · Cited by 6,855
(2009) · Cited by 6,153
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2018) · Science · doi:10.1126/science.aar6404 · Cited by 3,562
Campbell, M., Hoane, A. J., & Hsu, F.-H. (2002) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00129-1 · Cited by 1,226
Active inference: a process theory
Friston, K., FitzGerald, T., Rigoli, F., Schwartenbeck, P., & Pezzulo, G. (2017) · Neural Computation · doi:10.1162/neco_a_00912 · Cited by 1,156
Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2017) · arXiv · doi:10.48550/arxiv.1712.01815 · Cited by 1,102
A Survey of Actor-Critic Reinforcement Learning: Standard and Natural Policy Gradients
Grondman, I., Busoniu, L., Lopes, G. A. D., & Babuska, R. (2012) · IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) · doi:10.1109/tsmcc.2012.2218595 · Cited by 1,042
Improving Elevator Performance Using Reinforcement Learning
Crites, R. H., & Barto, A. G. (1995) · Cited by 499
An Analysis of Stochastic Shortest Path Problems
Bertsekas, D. P., & Tsitsiklis, J. N. (1991) · Mathematics of Operations Research · doi:10.1287/moor.16.3.580 · Cited by 488
Probabilistic inference for solving discrete and continuous state Markov Decision Processes
Toussaint, M., & Storkey, A. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143963 · Cited by 482
Neuro-dynamic programming: an overview
Bertsekas, D. P., & Tsitsiklis, J. N. (2002) · Proceedings of 1995 34th IEEE Conference on Decision and Control · doi:10.1109/cdc.1995.478953 · Cited by 411
Automated Verification Techniques for Probabilistic Systems
Forejt, V., Kwiatkowska, M., Norman, G., & Parker, D. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-21455-4_3 · Cited by 319
Planning with Markov Decision Processes: An AI Perspective
Mausam, M., & Kolobov, A. (2012) · Synthesis lectures on artificial intelligence and machine learning · doi:10.2200/s00426ed1v01y201206aim017 · Cited by 312
FF-Replan: a baseline for probabilistic planning
Yoon, S., Fern, A., & Givan, R. L. (2007) · Cited by 257
Active inference on discrete state-spaces: A synthesis
Da Costa, L., Parr, T., Sajid, N., Veselic, S., Neacsu, V., & Friston, K. (2020) · Journal of Mathematical Psychology · doi:10.1016/j.jmp.2020.102447 · Cited by 226 · cited 1×
“Several papers have been published showing connections between active inference and dynamic programming to solve an MDP [15,8,7].”
BackgroundPlanning by Probabilistic Inference.
Attias, H. T. (2003) · Cited by 204
Active inference on discrete state-spaces: A synthesis
Costa, L. D., Parr, T., Sajid, N., Veselic, S., Neacsu, V., & Friston, K. J. (2020) · UCL Discovery (University College London) · Cited by 204
Planning and navigation as active inference
Kaplan, R., & Friston, K. J. (2018) · Biological Cybernetics · doi:10.1007/s00422-018-0753-2 · Cited by 203
A Probabilistic Production and Inventory Problem
d'Epenoux, F. (1963) · Management Science · doi:10.1287/mnsc.10.1.98 · Cited by 201
Multi-objective Model Checking of Markov Decision Processes
Etessami, K., Kwiatkowska, M., Vardi, M. Y., & Yannakakis, M. (2007) · Springer eBooks · doi:10.1007/978-3-540-71209-1_6 · Cited by 106
Probabilistic inference for solving (PO) MDPs
Toussaint, M., Stefan Harmeling, B., & Storkey, A. (2006) · MPG.PuRe (Max Planck Society) · Cited by 98
On the Relationship Between Active Inference and Control as Inference
Millidge, B., Tschantz, A., Seth, A. K., & Buckley, C. L. (2020) · Communications in computer and information science · doi:10.1007/978-3-030-64919-7_1 · Cited by 97
Thomas, P. S., & Brunskill, E. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.06643 · Cited by 83
Probabilistic planning with formal performance guarantees for mobile service robots
Lacerda, B., Faruq, F., Parker, D., & Hawes, N. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364919856695 · Cited by 81
Self-citationHierarchical POMDP Controller Optimization by Likelihood Maximization
Toussaint, M., Charlin, L., & Poupart, P. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.3291 · Cited by 74
Tomy, M., Lacerda, B., Hawes, N., & Wyatt, J. (2020) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2020.103629 · Cited by 49
Self-citationActive Inference and Behavior Trees for Reactive Action Planning and Execution in Robotics
Pezzato, C., Corbato, C. H., Bonhof, S., & Wisse, M. (2023) · IEEE Transactions on Robotics · doi:10.1109/tro.2022.3226144 · Cited by 44 · cited 3×
“If the transition or cost functions vary while interacting with the environment (e.g. [24,10]), an offline solution is not optimal.”
BackgroundMethodReward maximization through discrete active inference
Da Costa, L., Sajid, N., Parr, T., Friston, K., & Smith, R. (2023) · Neural Computation · doi:10.1162/neco_a_01574 · Cited by 35
Probabilistic Inference Techniques for Scalable Multiagent Decision Making
Kumar, A., Zilberstein, S., & Toussaint, M. (2015) · Journal of Artificial Intelligence Research · doi:10.1613/jair.4649 · Cited by 32
Costa, L. D., Sajid, N., Parr, T., Friston, K. J., & Smith, R. S. (2020) · arXiv (Cornell University) · Cited by 23
Convex Hull Monte-Carlo Tree-Search
Painter, M., Lacerda, B., & Hawes, N. (2020) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v30i1.6664 · Cited by 18
Self-citationLinear programming formulations of Markov decision processes
Nazareth, J. L., & Kulkarni, R. B. (1986) · Operations Research Letters · doi:10.1016/0167-6377(86)90094-5 · Cited by 13
Research works printed but not linked: 2
- Sutton, R.S., McAllester, D.A., Singh, S.P., Mansour, Y.: Policy gradient methods for reinforcement learning with function approximation. In: Advances in Neural Information Processing Systems, pp. 1057–1063 (2000)
- Verma, D., Rao, R.P.: Goal-based imitation as probabilistic inference over graphical models. In: Advances in Neural Information Processing Systems, pp. 1393–1400 (2006)
Cited by
Active Inference and Behavior Trees for Reactive Action Planning and Execution in Robotics
Pezzato, C., Corbato, C. H., Bonhof, S., & Wisse, M. (2023) · IEEE Transactions on Robotics · doi:10.1109/tro.2022.3226144 · Cited by 44
“As concluded in [43], for the parts of a task subject to frequent unpredictable changes, computing locally an online plan as we do with active inference is preferable to offline policies.”
BackgroundKamp, M., Koprinska, I., Bibal, A., Bouadi, T., Frénay, B., Galárraga, L. A., Jose Oramas, M., Adilova, L., Krishnamurthy, Y., Kang, B., et al. (2021) · Communications in computer and information science · doi:10.1007/978-3-030-93736-2 · Cited by 39
Kamp, M., Koprinska, I., Bibal, A., Bouadi, T., Frénay, B., Galárraga, L. A., Jose Oramas, M., Adilova, L., Krishnamurthy, Y., Kang, B., et al. (2021) · Communications in computer and information science · doi:10.1007/978-3-030-93733-1 · Cited by 18
Unbiased Active Inference for Classical Control
Baioumy, M., Pezzato, C., Ferrari, R., & Hawes, N. (2022) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros47612.2022.9981095 · Cited by 9
Self-citation
Metadata
- Authors
- Baioumy, M., Lacerda, B., Duckworth, P., & Hawes, N.
- Affiliations
- University of Oxford (GB)
- Corresponding author
- Baioumy, Mohamed
- Venue
- Communications in Computer and Information Science
- Publisher
- Springer International Publishing
- Published
- 2021
- Pages
- 819-829
- ISSN
- 1865-0929 (ISSN-L)
- 1865-0937
- OpenAlex
- W3199477924
- Cited by
- 4
- References
- 33
- Citations by year
- 2023: 1 · 2022: 1 · 2021: 2
- FWCI
- 0.46
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- www.springer.com/tdm (vor)
- Locations
- Communications in computer and information science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Life Sciences › Neuroscience › Cognitive Neuroscience › Embodied and Extended Cognition
- Keywords
- active inference, probabilistic inference, planning under uncertainty, online planning, offline planning, dynamic programming, finite-horizon MDPs
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.