Progressive Abstraction Refinement for Sparse Sampling

Jesse Hostetler Oregon State University, Alan Fern Oregon State University, Thomas Dietterich Oregon State University
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:209-218, 2015.

Abstract

Monte Carlo tree search (MCTS) algorithms can encounter difficulties when solving Markov decision problems (MDPs) in which the outcomes of actions are highly stochastic. This stochastic branching can be reduced through state abstraction. In online planning with a time budget, there is a complex tradeoff between the loss in performance due to overly coarse abstraction versus the gain in performance from reducing the problem size. We find empirically that very coarse and unsound abstractions often outperform sound abstractions for practical planning budgets. Motivated by this, we propose a progressive abstraction refinement algorithm that refines an initially coarse abstraction during search in order to match the abstraction granularity to the sample budget. Our experiments demonstrate the strong performance of search with coarse abstractions, and show that our proposed algorithm combines the benefits of coarse abstraction at small sample budgets with the ability to exploit larger budgets for further performance gains.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-university15d, title = {Progressive Abstraction Refinement for Sparse Sampling}, author = {University, Jesse Hostetler Oregon State and University, Alan Fern Oregon State and University, Thomas Dietterich Oregon State}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {209--218}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/university15d/university15d.pdf}, url = {https://proceedings.mlr.press/r13/university15d.html}, abstract = {Monte Carlo tree search (MCTS) algorithms can encounter difficulties when solving Markov decision problems (MDPs) in which the outcomes of actions are highly stochastic. This stochastic branching can be reduced through state abstraction. In online planning with a time budget, there is a complex tradeoff between the loss in performance due to overly coarse abstraction versus the gain in performance from reducing the problem size. We find empirically that very coarse and unsound abstractions often outperform sound abstractions for practical planning budgets. Motivated by this, we propose a progressive abstraction refinement algorithm that refines an initially coarse abstraction during search in order to match the abstraction granularity to the sample budget. Our experiments demonstrate the strong performance of search with coarse abstractions, and show that our proposed algorithm combines the benefits of coarse abstraction at small sample budgets with the ability to exploit larger budgets for further performance gains.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Progressive Abstraction Refinement for Sparse Sampling %A Jesse Hostetler Oregon State University %A Alan Fern Oregon State University %A Thomas Dietterich Oregon State University %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-university15d %I PMLR %P 209--218 %U https://proceedings.mlr.press/r13/university15d.html %V R13 %X Monte Carlo tree search (MCTS) algorithms can encounter difficulties when solving Markov decision problems (MDPs) in which the outcomes of actions are highly stochastic. This stochastic branching can be reduced through state abstraction. In online planning with a time budget, there is a complex tradeoff between the loss in performance due to overly coarse abstraction versus the gain in performance from reducing the problem size. We find empirically that very coarse and unsound abstractions often outperform sound abstractions for practical planning budgets. Motivated by this, we propose a progressive abstraction refinement algorithm that refines an initially coarse abstraction during search in order to match the abstraction granularity to the sample budget. Our experiments demonstrate the strong performance of search with coarse abstractions, and show that our proposed algorithm combines the benefits of coarse abstraction at small sample budgets with the ability to exploit larger budgets for further performance gains. %Z Reissued by PMLR on 04 October 2026.
APA
University, J.H.O.S., University, A.F.O.S. & University, T.D.O.S.. (2015). Progressive Abstraction Refinement for Sparse Sampling. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:209-218 Available from https://proceedings.mlr.press/r13/university15d.html. Reissued by PMLR on 04 October 2026.

Related Material