Bayesian Inference in Monte-Carlo Tree Search

Gerald Tesauro, VT Rajan, Richard Segal
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:587-595, 2010.

Abstract

Monte-Carlo Tree Search (MCTS) meth- ods are drawing great interest after yield- ing breakthrough results in computer Go. This paper proposes a Bayesian approach to MCTS that is inspired by distribution- free approaches such as UCT [13], yet sig- nificantly differs in important respects. The Bayesian framework allows potentially much more accurate (Bayes-optimal) estimation of node values and node uncertainties from a limited number of simulation trials. We fur- ther propose propagating inference in the tree via fast analytic Gaussian approxima- tion methods: this can make the overhead of Bayesian inference manageable in domains such as Go, while preserving high accuracy of expected-value estimates. We find substan- tial empirical outperformance of UCT in an idealized bandit-tree test environment, where we can obtain valuable insights by compar- ing with known ground truth. Additionally we rigorously prove on-policy and off-policy convergence of the proposed methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-tesauro10a, title = {{B}ayesian Inference in {M}onte-{C}arlo Tree Search}, author = {Tesauro, Gerald and Rajan, VT and Segal, Richard}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {587--595}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/tesauro10a/tesauro10a.pdf}, url = {https://proceedings.mlr.press/r8/tesauro10a.html}, abstract = {Monte-Carlo Tree Search (MCTS) meth- ods are drawing great interest after yield- ing breakthrough results in computer Go. This paper proposes a Bayesian approach to MCTS that is inspired by distribution- free approaches such as UCT [13], yet sig- nificantly differs in important respects. The Bayesian framework allows potentially much more accurate (Bayes-optimal) estimation of node values and node uncertainties from a limited number of simulation trials. We fur- ther propose propagating inference in the tree via fast analytic Gaussian approxima- tion methods: this can make the overhead of Bayesian inference manageable in domains such as Go, while preserving high accuracy of expected-value estimates. We find substan- tial empirical outperformance of UCT in an idealized bandit-tree test environment, where we can obtain valuable insights by compar- ing with known ground truth. Additionally we rigorously prove on-policy and off-policy convergence of the proposed methods.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bayesian Inference in Monte-Carlo Tree Search %A Gerald Tesauro %A VT Rajan %A Richard Segal %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-tesauro10a %I PMLR %P 587--595 %U https://proceedings.mlr.press/r8/tesauro10a.html %V R8 %X Monte-Carlo Tree Search (MCTS) meth- ods are drawing great interest after yield- ing breakthrough results in computer Go. This paper proposes a Bayesian approach to MCTS that is inspired by distribution- free approaches such as UCT [13], yet sig- nificantly differs in important respects. The Bayesian framework allows potentially much more accurate (Bayes-optimal) estimation of node values and node uncertainties from a limited number of simulation trials. We fur- ther propose propagating inference in the tree via fast analytic Gaussian approxima- tion methods: this can make the overhead of Bayesian inference manageable in domains such as Go, while preserving high accuracy of expected-value estimates. We find substan- tial empirical outperformance of UCT in an idealized bandit-tree test environment, where we can obtain valuable insights by compar- ing with known ground truth. Additionally we rigorously prove on-policy and off-policy convergence of the proposed methods. %Z Reissued by PMLR on 04 October 2026.
APA
Tesauro, G., Rajan, V. & Segal, R.. (2010). Bayesian Inference in Monte-Carlo Tree Search. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:587-595 Available from https://proceedings.mlr.press/r8/tesauro10a.html. Reissued by PMLR on 04 October 2026.

Related Material