Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search

John Asmuth, Michael L. Littman
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:36-43, 2011.

Abstract

Bayes-optimal behavior, while well-defined, is often difficult to achieve. Recent advances in the use of Monte-Carlo tree search (MCTS) have shown that it is possible to act near-optimally in Markov Decision Processes (MDPs) with very large or infinite state spaces. Bayes-optimal behavior in an unknown MDP is equivalent to optimal behavior in the known belief-space MDP, although the size of this belief-space MDP grows exponentially with the amount of history retained, and is potentially infinite. We show how an agent can use one particular MCTS algorithm, Forward Search Sparse Sampling (FSSS), in an efficient way to act nearly Bayes-optimally for all but a polynomial number of steps, assuming that FSSS can be used to act efficiently in any possible underlying MDP.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-asmuth11a, title = {Learning is planning: near {B}ayes-optimal reinforcement learning via {M}onte-{C}arlo tree search}, author = {Asmuth, John and Littman, Michael L.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {36--43}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/asmuth11a/asmuth11a.pdf}, url = {https://proceedings.mlr.press/r9/asmuth11a.html}, abstract = {Bayes-optimal behavior, while well-defined, is often difficult to achieve. Recent advances in the use of Monte-Carlo tree search (MCTS) have shown that it is possible to act near-optimally in Markov Decision Processes (MDPs) with very large or infinite state spaces. Bayes-optimal behavior in an unknown MDP is equivalent to optimal behavior in the known belief-space MDP, although the size of this belief-space MDP grows exponentially with the amount of history retained, and is potentially infinite. We show how an agent can use one particular MCTS algorithm, Forward Search Sparse Sampling (FSSS), in an efficient way to act nearly Bayes-optimally for all but a polynomial number of steps, assuming that FSSS can be used to act efficiently in any possible underlying MDP.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search %A John Asmuth %A Michael L. Littman %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-asmuth11a %I PMLR %P 36--43 %U https://proceedings.mlr.press/r9/asmuth11a.html %V R9 %X Bayes-optimal behavior, while well-defined, is often difficult to achieve. Recent advances in the use of Monte-Carlo tree search (MCTS) have shown that it is possible to act near-optimally in Markov Decision Processes (MDPs) with very large or infinite state spaces. Bayes-optimal behavior in an unknown MDP is equivalent to optimal behavior in the known belief-space MDP, although the size of this belief-space MDP grows exponentially with the amount of history retained, and is potentially infinite. We show how an agent can use one particular MCTS algorithm, Forward Search Sparse Sampling (FSSS), in an efficient way to act nearly Bayes-optimally for all but a polynomial number of steps, assuming that FSSS can be used to act efficiently in any possible underlying MDP. %Z Reissued by PMLR on 04 October 2026.
APA
Asmuth, J. & Littman, M.L.. (2011). Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:36-43 Available from https://proceedings.mlr.press/r9/asmuth11a.html. Reissued by PMLR on 04 October 2026.

Related Material