Open Loop Execution of Tree-Search Algorithms, extended version
This work addresses computational efficiency in on-line planning for AI systems, but it is incremental as it builds on existing tree-search methods.
The paper tackles the problem of avoiding re-planning in tree-search stochastic planning algorithms by using sub-trees for action recommendation, showing that the probability of suboptimal actions can be upper bounded and converges to zero with logarithmic decay between depths, and empirically demonstrates a compromise between performance loss and computational gain.
In the context of tree-search stochastic planning algorithms where a generative model is available, we consider on-line planning algorithms building trees in order to recommend an action. We investigate the question of avoiding re-planning in subsequent decision steps by directly using sub-trees as action recommender. Firstly, we propose a method for open loop control via a new algorithm taking the decision of re-planning or not at each time step based on an analysis of the statistics of the sub-tree. Secondly, we show that the probability of selecting a suboptimal action at any depth of the tree can be upper bounded and converges towards zero. Moreover, this upper bound decays in a logarithmic way between subsequent depths. This leads to a distinction between node-wise optimality and state-wise optimality. Finally, we empirically demonstrate that our method achieves a compromise between loss of performance and computational gain.