Bayesian Mixture Modelling and Inference based Thompson Sampling in Monte-Carlo Tree Search
Monte-Carlo tree search is drawing great interest in the domain of planning under uncertainty, particularly when little or no domain knowledge is available. One of the central problems is the trade-off between exploration and exploitation. In this paper we present a novel Bayesian mixture modelling and inference based Thompson sampling approach to addressing this dilemma. The proposed Dirichlet-NormalGamma MCTS (DNG-MCTS) algorithm represents the uncertainty of the accumulated reward for actions in the MCTS search tree as a mixture of Normal distributions and inferences on it in Bayesian settings by choosing conjugate priors in the form of combinations of Dirichlet and NormalGamma distributions. Thompson sampling is used to select the best action at each decision node. Experimental results show that our proposed algorithm has achieved the state-of-the-art comparing with popular UCT algorithm in the context of online planning for general Markov decision processes.
Code (0)
등록된 구현이 없습니다.
Tasks
Thompson SamplingSimilar Papers 제목 키워드 기반
Nonparametric Gaussian Mixture Models for the Multi-Armed Bandit
We here adopt Bayesian nonparametric mixture models to extend multi-armed bandits in general, and Thompson sampling in particular, to scenarios where there is reward model uncertainty. In the stochastic multi-armed bandi…
Density EstimationMulti-Armed BanditsThompson SamplingBetter Optimism By Bayes: Adaptive Planning with Rich Models
The computational costs of inference and planning have confined Bayesian model-based reinforcement learning to one of two dismal fates: powerful Bayes-adaptive planning but only for simplistic models, or powerful, Bayesi…
Model-based Reinforcement LearningReinforcement LearningReinforcement Learning (RL)Thompson SamplingImproved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning
In this paper, we prove the first Bayesian regret bounds for Thompson Sampling in reinforcement learning in a multitude of settings. We simplify the learning problem using a discrete set of surrogate environments, and pr…
reinforcement-learningReinforcement LearningThompson SamplingThompson Sampling on Symmetric $α$-Stable Bandits
Thompson Sampling provides an efficient technique to introduce prior knowledge in the multi-armed bandit problem, along with providing remarkable empirical performance. In this paper, we revisit the Thompson Sampling alg…
Bayesian InferenceDecision MakingSequential Bayesian InferenceSequential Decision Making+1Bayesian learning of the optimal action-value function in a Markov decision process
The Markov Decision Process (MDP) is a popular framework for sequential decision-making problems, and uncertainty quantification is an essential component of it to learn optimal decision-making strategies. In particular,…
Decision MakingSequential Decision MakingThompson SamplingUncertainty Quantification