Open Loop Execution of Tree-Search Algorithms, extended version
  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.
