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

arXiv: https://arxiv.org/abs/2104.06339 · HTML: https://mlsanity.com/paper/2104.06339/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 70 references that are in the map.
- First posted on arXiv 13 Apr 2021.

## Builds on (most cited first, 11 of 11)

- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [Learning model-based planning from scratch](https://mlsanity.com/paper/1707.06170/) (2017)
- [Information-Theoretic Bounded Rationality](https://mlsanity.com/paper/1512.06789/) (2015)
- [Metacontrol for Adaptive Imagination-Based Optimization](https://mlsanity.com/paper/1705.02670/) (2017)
- [Deep RL With Information Constrained Policies: Generalization in Continuous Control](https://mlsanity.com/paper/2010.04646/) (2020)
- [Static and Dynamic Values of Computation in MCTS](https://mlsanity.com/paper/2002.04335/) (2020)
- [Dynamic allocation of limited memory resources in reinforcement learning](https://mlsanity.com/paper/2011.06387/) (2020)
- [Optimal allocation of finite sampling capacity in accumulator models of multi-alternative decision making](https://mlsanity.com/paper/2102.01597/) (2021)

## Abstract (arXiv)

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.