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) al- gorithms for online planning, such as $\varepsilon$-greedy tree search and UCT, aim at rapidly iden- tifying a reasonably good action, but pro- vide rather poor worst-case guarantees on performance improvement over time. In con- trast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improve- ment 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 con- nected. We then rationalize a principle of “selective tree expansion”, and suggest a con- crete implementation of this principle within MCTS. The resulting algorithms favorably compete with other MCTS algorithms under short planning times, while preserving the at- tractive 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) al- gorithms for online planning, such as $\varepsilon$-greedy tree search and UCT, aim at rapidly iden- tifying a reasonably good action, but pro- vide rather poor worst-case guarantees on performance improvement over time. In con- trast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improve- ment 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 con- nected. We then rationalize a principle of “selective tree expansion”, and suggest a con- crete implementation of this principle within MCTS. The resulting algorithms favorably compete with other MCTS algorithms under short planning times, while preserving the at- tractive 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) al- gorithms for online planning, such as $\varepsilon$-greedy tree search and UCT, aim at rapidly iden- tifying a reasonably good action, but pro- vide rather poor worst-case guarantees on performance improvement over time. In con- trast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improve- ment 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 con- nected. We then rationalize a principle of “selective tree expansion”, and suggest a con- crete implementation of this principle within MCTS. The resulting algorithms favorably compete with other MCTS algorithms under short planning times, while preserving the at- tractive 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