  Many decisions involve choosing an uncertain course of actions 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 (exploring many actions at each level of the
tree) and depth (exploring many levels in the tree) to allocate optimally their
finite search capacity. We provide efficient analytical solutions and numerical
analysis to the problem of allocating finite sampling capacity in one shot to
large decision trees. We find 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 provide a
theoretical foundation for the optimality of deep imagination for planning and
show that it is a generally valid heuristic that could have evolved from the
finite constraints of cognitive systems.
