Pushing the Envelope of Monte-Carlo Planning: Formal Guarantees Meet Practical Efficiency

Zohar Feldman, Carmel Domshlak
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:382-391, 2013.

Abstract

Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such as $\varepsilon$-greedy tree search and UCT, aim at rapidly identifying a reasonably good action, but provide rather poor worst-case guarantees on performance improvement over time. In contrast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improvement over time, yet it is not geared towards identifying reasonably good choices right at the go. We take a stand on the individual strengths of these two classes of algorithms, and show how they can be effectively connected. We then rationalize a principle of “selective tree expansion”, and suggest a concrete implementation of this principle within MCTS. The resulting algorithms favorably compete with other MCTS algorithms under short planning times, while preserving the attractive convergence properties of BRUE.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-feldman13a, title = {Pushing the Envelope of {M}onte-{C}arlo Planning: Formal Guarantees Meet Practical Efficiency}, author = {Feldman, Zohar and Domshlak, Carmel}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {382--391}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/feldman13a/feldman13a.pdf}, url = {https://proceedings.mlr.press/r11/feldman13a.html}, abstract = {Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such as $\varepsilon$-greedy tree search and UCT, aim at rapidly identifying a reasonably good action, but provide rather poor worst-case guarantees on performance improvement over time. In contrast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improvement over time, yet it is not geared towards identifying reasonably good choices right at the go. We take a stand on the individual strengths of these two classes of algorithms, and show how they can be effectively connected. We then rationalize a principle of “selective tree expansion”, and suggest a concrete implementation of this principle within MCTS. The resulting algorithms favorably compete with other MCTS algorithms under short planning times, while preserving the attractive convergence properties of BRUE.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Pushing the Envelope of Monte-Carlo Planning: Formal Guarantees Meet Practical Efficiency %A Zohar Feldman %A Carmel Domshlak %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-feldman13a %I PMLR %P 382--391 %U https://proceedings.mlr.press/r11/feldman13a.html %V R11 %X Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such as $\varepsilon$-greedy tree search and UCT, aim at rapidly identifying a reasonably good action, but provide rather poor worst-case guarantees on performance improvement over time. In contrast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improvement over time, yet it is not geared towards identifying reasonably good choices right at the go. We take a stand on the individual strengths of these two classes of algorithms, and show how they can be effectively connected. We then rationalize a principle of “selective tree expansion”, and suggest a concrete implementation of this principle within MCTS. The resulting algorithms favorably compete with other MCTS algorithms under short planning times, while preserving the attractive convergence properties of BRUE. %Z Reissued by PMLR on 04 October 2026.
APA
Feldman, Z. & Domshlak, C.. (2013). Pushing the Envelope of Monte-Carlo Planning: Formal Guarantees Meet Practical Efficiency. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:382-391 Available from https://proceedings.mlr.press/r11/feldman13a.html. Reissued by PMLR on 04 October 2026.

Related Material