Bayesian Mixture Modeling and Inference based Thompson Sampling in Monte-Carlo Tree Search
Monte-Carlo tree search (MCTS) has been drawing great interest in recent years for planning and learning under uncertainty. One of the key challenges is the trade-off between exploration and exploitation. To address this, we present a novel approach for MCTS using Bayesian mixture modeling and inference based Thompson sampling and apply it to the problem of online planning in MDPs. Our algorithm, named Dirichlet-NormalGamma MCTS (DNG-MCTS), models the uncertainty of the accumulated reward for actions in the search tree as a mixture of Normal distributions. We perform inferences on the mixture in Bayesian settings by choosing conjugate priors in the form of combinations of Dirichlet and NormalGamma distributions and select the best action at each decision node using Thompson sampling. Experimental results confirm that our algorithm advances the state-of-the-art UCT approach with better values on several benchmark problems.
The paper proposes a Bayesian inference in Monte-Carlo 
      tree search (MCTS) with Thompson sampling based action-selection strategy, 
      called Dirichlet-NormalGamma MCTS (DNG-MTCS) algorithm. The method 
      approximates the accumulated reward of following the current policy from a 
      state, X_{s,\pi(s)}, by the normal distribution with the NromalGamma 
      distribution prior. The state transition probabilities are estimated via 
      Dirichlet distributions. Action-selection strategy is based on Thompson 
      sampling approach, where the expected cumulative reward for each action is 
      computed with the parametric distribution with parameters drawn from the 
      posterior distributions and then the action with the highest expectation 
      is selected. The authors apply the proposed method to several benchmark 
      tasks and showed that the method can converge (slightly) faster than the 
      UCT algorithm. Theoretical properties about convergence are also provided. 
      Although there is a lot of work on MCTS, I am not aware of other 
      work based on the specific approach made in the paper. However, the 
      density approximation of the cumulative reward with NormalGamma prior is 
      not new and has been proposed by Dearden et al. 1998 [a]. Modeling of the 
      state transition with Dirichlet prior is well known. So the originality of 
      the proposed modeling and inference methods in Section 3.2 will be small. 
      However, the proposed combination with this modeling and action-selection 
      strategy based on Thompson sampling is new, to the best of my knowledge, 
      and might be of interest to related areas of research. The 
      presented experimental result would be week. Although there is a lot of 
      work on MCTS, the applied baseline method was limited to the classic UCT 
      (except for the CTP problem). More detail experiments in terms of 
      computational costs as well as sample complexity with several advanced 
      methods in [b,d,e] will be needed. Most part of this paper is 
      clearly written. But the assumptions in Section 3.1 are not quite clear. I 
      feel that there is a contradiction. Although the cumulative reward given 
      (s, a), X_{s,a}, is modeled as a mixture of Normal distributions as a 
      result, the authors argue the assumption of X_{s,\pi(s)} having a Normal 
      distribution, is realistic. However, in what some see as, X_{s,\pi(s)} has 
      to be a mixture of Normal distributions and the number of mixtures will 
      increase exponentially (from leaf states to root). So their assumption of 
      X_{s,\pi(s)} cannot be realistic. But I think it should be one of 
      practical approaches for approximating the distribution of X_{s,\pi(s)}. 
      The relation between cumulative rewards in successive time-steps would be 
      related to the distributional Bellman equation in [c]. I’d like to 
      recommend revising this part carefully in the final version. In 
      line 137--139, N(n\mu, \delta^2/n) is N(n\mu, n\delta^2)? Doesn't the 
      \sum_n f diverge as n \to \infty? [a] Richard Dearden, Nir 
      Friedman, Stuart J. Russell: Bayesian Q-Learning. AAAI/IAAI 1998. [b] 
      Gerald Tesauro, V. T. Rajan, Richard Segal: Bayesian Inference in 
      Monte-Carlo Tree Search. UAI 2010. [c] Tetsuro Morimura, Masashi 
      Sugiyama, Hisashi Kashima, Hirotaka Hachiya, Toshiyuki Tanaka: Parametric 
      Return Density Estimation for Reinforcement Learning. UAI 2010. [d] 
      John Asmuth and Michael L. Littman. Approaching Bayes-optimalilty using 
      Monte-Carlo tree search. In Proc. 21st Int. Conf. Automat. Plan. Sched., 
      2011. [e] Arthur Guez, David Silver, Peter Dayan: Efficient 
      Bayes-Adaptive Reinforcement Learning using Sample-Based Search. NIPS 
      2012.