Feedback-Based Tree Search for Reinforcement Learning
  Inspired by recent successes of Monte-Carlo tree search (MCTS) in a number of
artificial intelligence (AI) application domains, we propose a model-based
reinforcement learning (RL) technique that iteratively applies MCTS on batches
of small, finite-horizon versions of the original infinite-horizon Markov
decision process. The terminal condition of the finite-horizon problems, or the
leaf-node evaluator of the decision tree generated by MCTS, is specified using
a combination of an estimated value function and an estimated policy function.
The recommendations generated by the MCTS procedure are then provided as
feedback in order to refine, through classification and regression, the
leaf-node evaluator for the next iteration. We provide the first sample
complexity bounds for a tree search-based RL algorithm. In addition, we show
that a deep neural network implementation of the technique can create a
competitive AI agent for the popular multi-player online battle arena (MOBA)
game King of Glory.
