Divide et impera : subgoaling reduces the complexity of probabilistic inference and problem solving
Open accessAbstract
It has long been recognized that humans (and possibly other animals) usually break problems down into smaller and more manageable problems using subgoals. Despite a general consensus that subgoaling helps problem solving, it is still unclear what the mechanisms guiding online subgoal selection are during the solution of novel problems for which predefined solutions are not available. Under which conditions does subgoaling lead to optimal behaviour? When is subgoaling better than solving a problem from start to finish? Which is the best number and sequence of subgoals to solve a given problem? How are these subgoals selected during online inference? Here, we present a computational account of subgoaling in problem solving. Following Occam's razor, we propose that good subgoals are those that permit planning solutions and controlling behaviour using less information resources, thus yielding parsimony in inference and control. We implement this principle using approximate probabilistic inference: subgoals are selected using a sampling method that considers the descriptive complexity of the resulting sub-problems. We validate the proposed method using a standard reinforcement learning benchmark (four-rooms scenario) and show that the proposed method requires less inferential steps and permits selecting more compact control programs compared to an equivalent procedure without subgoaling. Furthermore, we show that the proposed method offers a mechanistic explanation of the neuronal dynamics found in the prefrontal cortex of monkeys that solve planning problems. Our computational framework provides a novel integrative perspective on subgoaling and its adaptive advantages for planning, control and learning, such as for example lowering cognitive effort and working memory load.
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
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?
Expected precision or confidence about preferred outcomes reports on the progress towards the goal, and precision can be updated during goal-directed action rather than just mediating learning by reporting reward prediction errors.
“The expected precision or confidence about preferred outcomes reports on the progress towards the goal – like spatial proximity or sub-goals (Lepora and Pezzulo, 2015, Maisto et al., 2015) – and in accordance with early cybernetic models of purposive action such as the Test-Operate-Test-Exit (TOTE) model (Miller et al., 1960) precision can be updated (in a Bayes optimal fashion) during goal-direct”
From Active Inference, homeostatic regulation and adaptive behavioural control (2015) · cites this paper as Maisto et al., 2015
The Inferential procedure (§2.3; page unavailable) describes monitoring subgoal achievement and selecting the next subgoal, supporting the spatial-subgoal aspect of progress toward a goal. It does not identify this process as expected precision or confidence about preferred outcomes, or say that precision is updated during goal-directed action rather than mediating learning through reward prediction errors. (LLM, conf=0.82)
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.
Cites
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225 · see citing works
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. (2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 25,263 · see citing works
An Integrative Theory of Prefrontal Cortex Function
Miller, E. K., & Cohen, J. D. (2001) · Annual Review of Neuroscience · doi:10.1146/annurev.neuro.24.1.167 · Cited by 12,803 · see citing works
The free-energy principle: a unified brain theory?
Friston, K. (2010) · Nature Reviews Neuroscience · doi:10.1038/nrn2787 · Cited by 8,120 · see citing works
Axten, N., Newell, A., & Simon, H. A. (1973) · Contemporary Sociology A Journal of Reviews · doi:10.2307/2063712 · Cited by 6,883 · see citing works
Newell, A. (1972) · Cited by 6,222 · see citing works
On sequential Monte Carlo sampling methods for Bayesian filtering
Doucet, A., Godsill, S., & Andrieu, C. (2000) · Statistics and Computing · doi:10.1023/a:1008935410038 · Cited by 4,466 · see citing works
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitanyi, P. M. B. (2019) · Texts in computer science · doi:10.1007/978-3-030-11298-1 · Cited by 3,752 · see citing works
Specific impairments of planning
Shallice, T. (1982) · Philosophical Transactions of the Royal Society of London. B, Biological Sciences · doi:10.1098/rstb.1982.0082 · Cited by 3,741 · see citing works
Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning
Sutton, R. S., Precup, D., & Singh, S. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00052-1 · Cited by 3,119 · see citing works
(1961) · Information and Control · doi:10.1016/s0019-9958(61)80064-8 · Cited by 2,904 · see citing works
Dynamic bayesian networks: representation, inference and learning
Murphy, K. P., & Russell, S. (2002) · Cited by 2,563 · see citing works
Daw, N. D., Niv, Y., & Dayan, P. (2005) · Nature Neuroscience · doi:10.1038/nn1560 · Cited by 2,533 · see citing works
The Prefrontal Cortex: Anatomy, Physiology, and Neuropsychology of the Frontal Lobe
Fuster, J. M. (1980) · Cited by 2,367 · see citing works
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (2008) · Texts in Computer Science · doi:10.1007/978-0-387-49820-1 · Cited by 1,424 · see citing works
Possible Principles Underlying the Transformations of Sensory Messages
Barlow, H. B. (2012) · The MIT Press eBooks · doi:10.7551/mitpress/9780262518420.003.0013 · Cited by 1,318 · see citing works
Recent Advances in Hierarchical Reinforcement Learning
Barto, A. G., & Mahadevan, S. (2003) · Discrete Event Dynamic Systems · doi:10.1023/a:1022140919877 · Cited by 1,043 · see citing works
Bayesian brain : probabilistic approaches to neural coding
賢治, 銅., 信, 石., Pouget, A., & Rao, R. P. N. (2006) · The MIT Press eBooks · doi:10.7551/mitpress/9780262042383.001.0001 · Cited by 823 · see citing works
A Hierarchy of Time-Scales and the Brain
Kiebel, S. J., Daunizeau, J., & Friston, K. J. (2008) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000209 · Cited by 694 · see citing works
Hierarchically organized behavior and its neural foundations: A reinforcement learning perspective
Botvinick, M. M., Niv, Y., & Barto, A. G. (2009) · Cognition · doi:10.1016/j.cognition.2008.08.011 · Cited by 646 · see citing works
Hierarchical models of behavior and prefrontal function
Botvinick, M. M. (2008) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2008.02.009 · Cited by 532 · see citing works
Probabilistic inference for solving discrete and continuous state Markov Decision Processes
Toussaint, M., & Storkey, A. (2006) · International Conference on Machine Learning · doi:10.1145/1143844.1143963 · Cited by 496 · see citing works
The prefrontal cortex: Anatomy, physiology and neuropsychology of the frontal lobe
Andy, O. J. (1981) · Surgical Neurology · doi:10.1016/0090-3019(81)90062-8 · Cited by 455 · see citing works
Reinforcement learning or active inference?
Friston, K. J., Daunizeau, J., & Kiebel, S. J. (2009) · PLoS ONE · doi:10.1371/journal.pone.0006421 · Cited by 443 · see citing works
The Neurobiology of the Prefrontal Cortex: Anatomy, Evolution, and the Origin of Insight
Passingham, R. E., & Wise, S. P. (2012) · doi:10.1093/acprof:osobl/9780199552917.001.0001 · Cited by 379 · see citing works
Stop Signals Provide Cross Inhibition in Collective Decision-Making by Honeybee Swarms
Seeley, T. D., Visscher, P. K., Schlegel, T., Hogan, P. M., Franks, N. R., & Marshall, J. A. R. (2011) · Science · doi:10.1126/science.1210361 · Cited by 325 · see citing works
Recent Advances in Hierarchical Reinforcement Learning
Barto, A. G., & Mahadevan, S. (2003) · Discrete Event Dynamic Systems · doi:10.1023/a:1025696116075 · Cited by 317 · see citing works
The Neurobiology of the Prefrontal Cortex: Anatomy, Evolution, and the Origin of Insight
Passingham, R. E., & Wise, S. P. (2012) · Cited by 307 · see citing works
Botvinick, M., & Toussaint, M. (2012) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2012.08.006 · Cited by 295 · see citing works
Soar Papers: Research on Integrated Intelligence
Rosenbloom, P. S., Laird, J. E., & Newell, A. (1993) · Medical Entomology and Zoology · Cited by 268 · see citing works
Thermodynamics as a theory of decision-making with information-processing costs
Ortega, P. A., & Braun, D. A. (2013) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2012.0683 · Cited by 263 · see citing works
Activity in the lateral prefrontal cortex reflects multiple steps of future events in action plans
Mushiake, H., Saito, N., Sakamoto, K., Itoyama, Y., & Tanji, J. (2006) · Neuron · doi:10.1016/j.neuron.2006.03.045 · Cited by 249 · see citing works
Active inference and agency: optimal control without cost functions
Friston, K., Samothrakis, S., & Montague, R. (2012) · Biological Cybernetics · doi:10.1007/s00422-012-0512-8 · Cited by 241 · see citing works
Hierarchical Solution of Markov Decision Processes using Macro-actionsPreprint
Hauskrecht, M., Meuleau, N., Kaelbling, L. P., Dean, T., & Boutilier, C. E. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.7381 · Cited by 230 · see citing works
Internally generated sequences in learning and executing goal-directed behavior
Pezzulo, G., van der Meer, M. A. A., Lansink, C. S., & Pennartz, C. M. A. (2014) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2014.06.011 · Cited by 217 · see citing works
Self-citationAdvances in Neural Information Processing Systems 19 (NIPS 2006)
Girolami, M., & Zhong, M. (2007) · Cited by 213 · see citing works
Planning by Probabilistic Inference.
Attias, H. T. (2003) · Cited by 204 · see citing works
Neural Correlates of Forward Planning in a Spatial Decision Task in Humans
Simon, D. A., & Daw, N. D. (2011) · Journal of Neuroscience · doi:10.1523/jneurosci.4647-10.2011 · Cited by 181 · see citing works
Solway, A., & Botvinick, M. (2012) · Psychological Review · doi:10.1037/a0026435 · Cited by 180 · see citing works
Performance in Planning: Processes, Requirements, and Errors
Mumford, M. D., Schultz, R. A., & Doorn, J. R. V. (2001) · Review of General Psychology · doi:10.1037/1089-2680.5.3.213 · Cited by 167 · see citing works
Pezzulo, G., Rigoli, F., & Chersi, F. (2013) · Frontiers in Psychology · doi:10.3389/fpsyg.2013.00092 · Cited by 163 · see citing works
Self-citationSolway, A., Diuk, C., Córdova, N. I., Yee, D. M., Barto, A. G., Niv, Y., & Botvinick, M. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003779 · Cited by 145 · see citing works
Thinking as the control of imagination: a conceptual framework for goal-directed systems
Pezzulo, G., & Castelfranchi, C. (2009) · Psychological Research Psychologische Forschung · doi:10.1007/s00426-009-0237-z · Cited by 141 · see citing works
Self-citationDiscovering Neural Nets with Low Kolmogorov Complexity and High Generalization Capability
Schmidhuber, J. (1997) · Neural Networks · doi:10.1016/s0893-6080(96)00127-x · Cited by 138 · see citing works
The why, what, where, when and how of goal-directed choice: neuronal and computational principles
Verschure, P. F. M. J., Pennartz, C. M. A., & Pezzulo, G. (2014) · Philosophical Transactions of the Royal Society B Biological Sciences · doi:10.1098/rstb.2013.0483 · Cited by 131 · see citing works
Functional Specialization of the Primate Frontal Cortex during Decision Making: Figure 1.
Lee, D., Rushworth, M. F. S., Walton, M. E., Watanabe, M., & Sakagami, M. (2007) · Journal of Neuroscience · doi:10.1523/jneurosci.1561-07.2007 · Cited by 121 · see citing works
Saito, N., Mushiake, H., Sakamoto, K., Itoyama, Y., & Tanji, J. (2005) · Cerebral Cortex · doi:10.1093/cercor/bhi032 · Cited by 121 · see citing works
Width and Serialization of Classical Planning Problems
Lipovetzky, N., & Geffner, H. (2012) · Frontiers in artificial intelligence and applications · doi:10.3233/978-1-61499-098-7-540 · Cited by 115 · see citing works
The Discovery of Algorithmic Probability
Solomonoff, R. J. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1500 · Cited by 110 · see citing works
Task partitioning in insect societies: bucket brigades
Anderson, C., Boomsma, J. J., & Bartholdi, III (2002) · Insectes Sociaux · doi:10.1007/s00040-002-8298-7 · Cited by 95 · see citing works
Trianni, V., Tuci, E., Passino, K. M., & Marshall, J. A. R. (2010) · Swarm Intelligence · doi:10.1007/s11721-010-0050-8 · Cited by 91 · see citing works
The Value of Foresight: How Prospection Affects Decision-Making
Pezzulo, G., & Rigoli, F. (2011) · Frontiers in Neuroscience · doi:10.3389/fnins.2011.00079 · Cited by 66 · see citing works
Self-citationEncoding Goals but Not Abstract Magnitude in the Primate Prefrontal Cortex
Genovesio, A., Tsujimoto, S., & Wise, S. P. (2012) · Neuron · doi:10.1016/j.neuron.2012.02.023 · Cited by 57 · see citing works
Goal-directed decision making in prefrontal cortex: A computational framework.
Botvinick, M., & An, J. (2009) · PubMed · Cited by 45 · see citing works
The principles of goal-directed decision-making: from neural mechanisms to computation and robotics
Pezzulo, G., Verschure, P. F. M. J., Balkenius, C., & Pennartz, C. M. A. (2014) · Philosophical Transactions of the Royal Society B Biological Sciences · doi:10.1098/rstb.2013.0470 · Cited by 35 · see citing works
Self-citationRegulation of task partitioning by a “common stomach”: a model of nest construction in social wasps
Karsai, I., & Schmickl, T. (2011) · Behavioral Ecology · doi:10.1093/beheco/arr060 · Cited by 34 · see citing works
Grounding subgoals in information transitions
van Dijk, S. G., & Polani, D. (2011) · IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning · doi:10.1109/adprl.2011.5967384 · Cited by 29 · see citing works
Computational models of planning
Geffner, H. (2013) · Wiley Interdisciplinary Reviews Cognitive Science · doi:10.1002/wcs.1233 · Cited by 24 · see citing works
Planning and Acting in Uncertain Environments using Probabilistic Inference
Verma, D. K., & Rao, R. P. N. (2006) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2006.281675 · Cited by 22 · see citing works
Hamann, H., Karsai, I., & Schmickl, T. (2013) · Bulletin of Mathematical Biology · doi:10.1007/s11538-013-9851-4 · Cited by 20 · see citing works
Hierarchical Behaviours: Getting the Most Bang for Your Bit
van Dijk, S. G., Polani, D., & Nehaniv, C. L. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-21314-4_43 · Cited by 19 · see citing works
Programming in the brain: a neural network theoretical framework
Donnarumma, F., Prevete, R., & Trautteur, G. (2012) · Connection Science · doi:10.1080/09540091.2012.684670 · Cited by 18 · see citing works
Self-citationSubgoal length versus full solution length in predicting Tower of Hanoi problem-solving performance
Spitz, H. H., Minsky, S. K., & Bessellieu, C. L. (1984) · Bulletin of the Psychonomic Society · doi:10.3758/bf03333826 · Cited by 13 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Active Inference, homeostatic regulation and adaptive behavioural control
Pezzulo, G., Rigoli, F., & Friston, K. (2015) · Progress in Neurobiology · doi:10.1016/j.pneurobio.2015.09.001 · Cited by 650 · see citing works
Self-citationHierarchical active inference: A theory of motivated control
Pezzulo, G., Rigoli, F., & Friston, K. J. (2018) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2018.01.009 · Cited by 334 · see citing works
Self-citationPlanning and navigation as active inference
Kaplan, R., & Friston, K. J. (2018) · Biological Cybernetics · doi:10.1007/s00422-018-0753-2 · Cited by 203 · see citing works
Degeneracy and Redundancy in Active Inference
Sajid, N., Parr, T., Hope, T. M., Price, C. J., & Friston, K. J. (2020) · Cerebral Cortex · doi:10.1093/cercor/bhaa148 · Cited by 49 · see citing works
- Authors
- Maisto, D., Donnarumma, F., & Pezzulo, G.
- Affiliations
- Institute for High Performance Computing and Networking (IT)
- National Research Council (IT)
- Corresponding author
- Pezzulo, Giovanni
- Venue
- Journal of The Royal Society Interface
- Publisher
- The Royal Society
- Published
- 2015-03
- Volume
- 12
- Issue
- 104
- Pages
- 20141335
- ISSN
- 1742-5662 (ISSN-L)
- 1742-5689
- PMC
- PMC4345499
- OpenAlex
- W2101645771
- Cited by
- 59
- References
- 63
- Citations by year
- 2026: 2 · 2025: 4 · 2024: 2 · 2023: 8 · 2022: 4 · 2021: 9 · 2020: 7 · 2019: 5 · 2018: 5 · 2017: 4 · 2016: 5 · 2015: 4
- FWCI
- 5.82
- Type
- journal article
- Language
- en
- Open access
- green
- www.ncbi.nlm.nih.gov
- Locations
- Journal of The Royal Society Interface (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Life Sciences › Neuroscience › Cognitive Neuroscience › Neural and Behavioral Psychology Studies
- Keywords
- subgoal selection, problem solving, probabilistic inference, approximate inference, sampling, Occam's razor, descriptive complexity, planning, prefrontal cortex, reinforcement learning, working memory load, cognitive effort, online inference
- MeSH terms
- Algorithms, Animals, Haplorhini, Bayes Theorem, Brain, Computer Simulation, Humans, Learning, Markov Chains, Monte Carlo Method, Neurons, Neurosciences, Probability, Problem Solving, Prefrontal Cortex, Internet
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
