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

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.