Deep imagination is a close to optimal policy for planning in large decision trees under limited resources

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Mastrogiuseppe, Chiara
• dc.contributor.author Moreno Bote, Rubén
• dc.date.accessioned 2023-01-20T07:51:58Z
• dc.date.available 2023-01-20T07:51:58Z
• dc.date.issued 2022
• dc.description.abstract Many decisions involve choosing an uncertain course of action in deep and wide decision trees, as when we plan to visit an exotic country for vacation. In these cases, exhaustive search for the best sequence of actions is not tractable due to the large number of possibilities and limited time or computational resources available to make the decision. Therefore, planning agents need to balance breadth—considering many actions in the frst few tree levels—and depth—considering many levels but few actions in each of them—to allocate optimally their fnite search capacity. We provide efcient analytical solutions and numerical analysis to the problem of allocating fnite sampling capacity in one shot to infnitely large decision trees, both in the time discounted and undiscounted cases. We fnd that in general the optimal policy is to allocate few samples per level so that deep levels can be reached, thus favoring depth over breadth search. In contrast, in poor environments and at low capacity, it is best to broadly sample branches at the cost of not sampling deeply, although this policy is marginally better than deep allocations. Our results can provide a theoretical foundation for why human reasoning is pervaded by imagination-based processes.
• dc.description.sponsorship Tis work is supported by the Howard Hughes Medical Institute (HHMI, ref 55008742), MINECO (Spain; BFU2017-85936-P) and ICREA Academia (2016) to R.M.-B. With the support from the Secretariat for Universities and Research of the Ministry of Business and Knowledge of the Government of Catalonia and the European Social Fund.
• dc.format.mimetype application/pdf
• dc.identifier.citation Mastrogiuseppe C, Moreno‑Bote R. Deep imagination is a close to optimal policy for planning in large decision trees under limited resources. Sci Rep. 2022;12:10411. DOI: 10.1038/s41598-022-13862-2
• dc.identifier.doi http://dx.doi.org/10.1038/s41598-022-13862-2
• dc.identifier.issn 2045-2322
• dc.identifier.uri http://hdl.handle.net/10230/55354
• dc.language.iso eng
• dc.publisher Nature Research
• dc.relation.ispartof Scientific Reports. 2022;12:10411.
• dc.relation.isreferencedby https://github.com/Chiara-Mastro/Deep_imagination_decision_trees
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/BFU2017-85936-P
• dc.rights © The Author(s) 2022. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit https://creativecommons.org/licenses/by/4.0/.
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri http://creativecommons.org/licenses/by/4.0/
• dc.subject.other Informàtica tova
• dc.title Deep imagination is a close to optimal policy for planning in large decision trees under limited resources
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion