Learning Partial Policies to Speedup MDP Tree Search

Jervis Pinto Oregon State University, Alan Fern Oregon State University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:667-676, 2014.

Abstract

A popular approach for online decision making in large MDPs is time-bounded tree search. The effectiveness of tree search, however, is largely influenced by the action branching factor, which limits the search depth given a time bound. An obvious way to reduce action branching is to consider only a subset of potentially good ac- tions at each state as specified by a provided partial policy. In this work, we consider offline learning of such partial policies with the goal of speeding up search without significantly reduc- ing decision-making quality. Our first contribu- tion is to study learning algorithms based on re- ducing our learning problem to i.i.d. supervised learning. We give a reduction-style analysis of three such algorithms, each making different as- sumptions, which relates the supervised learning objectives to the sub-optimality of search using the learned partial policies. Our second contribu- tion is to describe concrete implementations of the algorithms within the popular framework of Monte-Carlo tree search. Finally, the third con- tribution is to evaluate the learning algorithms in two challenging MDPs with large action branch- ing factors, showing that the learned partial poli- cies can significantly improve the anytime per- formance of Monte-Carlo tree search.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14r, title = {Learning Partial Policies to Speedup {MDP} Tree Search}, author = {University, Jervis Pinto Oregon State and University, Alan Fern Oregon State}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {667--676}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14r/university14r.pdf}, url = {https://proceedings.mlr.press/r12/university14r.html}, abstract = {A popular approach for online decision making in large MDPs is time-bounded tree search. The effectiveness of tree search, however, is largely influenced by the action branching factor, which limits the search depth given a time bound. An obvious way to reduce action branching is to consider only a subset of potentially good ac- tions at each state as specified by a provided partial policy. In this work, we consider offline learning of such partial policies with the goal of speeding up search without significantly reduc- ing decision-making quality. Our first contribu- tion is to study learning algorithms based on re- ducing our learning problem to i.i.d. supervised learning. We give a reduction-style analysis of three such algorithms, each making different as- sumptions, which relates the supervised learning objectives to the sub-optimality of search using the learned partial policies. Our second contribu- tion is to describe concrete implementations of the algorithms within the popular framework of Monte-Carlo tree search. Finally, the third con- tribution is to evaluate the learning algorithms in two challenging MDPs with large action branch- ing factors, showing that the learned partial poli- cies can significantly improve the anytime per- formance of Monte-Carlo tree search.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Learning Partial Policies to Speedup MDP Tree Search %A Jervis Pinto Oregon State University %A Alan Fern Oregon State University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14r %I PMLR %P 667--676 %U https://proceedings.mlr.press/r12/university14r.html %V R12 %X A popular approach for online decision making in large MDPs is time-bounded tree search. The effectiveness of tree search, however, is largely influenced by the action branching factor, which limits the search depth given a time bound. An obvious way to reduce action branching is to consider only a subset of potentially good ac- tions at each state as specified by a provided partial policy. In this work, we consider offline learning of such partial policies with the goal of speeding up search without significantly reduc- ing decision-making quality. Our first contribu- tion is to study learning algorithms based on re- ducing our learning problem to i.i.d. supervised learning. We give a reduction-style analysis of three such algorithms, each making different as- sumptions, which relates the supervised learning objectives to the sub-optimality of search using the learned partial policies. Our second contribu- tion is to describe concrete implementations of the algorithms within the popular framework of Monte-Carlo tree search. Finally, the third con- tribution is to evaluate the learning algorithms in two challenging MDPs with large action branch- ing factors, showing that the learned partial poli- cies can significantly improve the anytime per- formance of Monte-Carlo tree search. %Z Reissued by PMLR on 04 October 2026.
APA
University, J.P.O.S. & University, A.F.O.S.. (2014). Learning Partial Policies to Speedup MDP Tree Search. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:667-676 Available from https://proceedings.mlr.press/r12/university14r.html. Reissued by PMLR on 04 October 2026.

Related Material