Selecting Computations: Theory and Applications

Nicholas Hay, Stuart Russell, David Tolpin, Solomon Eyal Shimony
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:344-353, 2012.

Abstract

Sequential decision problems are often approximately solvable by simulating possible future action sequences. Metalevel decision procedures have been developed for selecting which action sequences to simulate, based on estimating the expected improvement in decision quality that would result from any particular simulation; an example is the recent work on using bandit algorithms to control Monte Carlo tree search in the game of Go. In this paper we develop a theoretical basis for metalevel decisions in the statistical framework of Bayesian selection problems, arguing (as others have done) that this is more appropriate than the bandit framework. We derive a number of basic results applicable to Monte Carlo selection problems, including the first finite sampling bounds for optimal policies in certain cases; we also provide a simple counterexample to the intuitive conjecture that an optimal policy will necessarily reach a decision in all cases. We then derive heuristic approximations in both Bayesian and distribution-free settings and demonstrate their superiority to bandit-based heuristics in one-shot decision problems and in Go.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-hay12a, title = {Selecting Computations: Theory and Applications}, author = {Hay, Nicholas and Russell, Stuart and Tolpin, David and Shimony, Solomon Eyal}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {344--353}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/hay12a/hay12a.pdf}, url = {https://proceedings.mlr.press/r10/hay12a.html}, abstract = {Sequential decision problems are often approximately solvable by simulating possible future action sequences. Metalevel decision procedures have been developed for selecting which action sequences to simulate, based on estimating the expected improvement in decision quality that would result from any particular simulation; an example is the recent work on using bandit algorithms to control Monte Carlo tree search in the game of Go. In this paper we develop a theoretical basis for metalevel decisions in the statistical framework of Bayesian selection problems, arguing (as others have done) that this is more appropriate than the bandit framework. We derive a number of basic results applicable to Monte Carlo selection problems, including the first finite sampling bounds for optimal policies in certain cases; we also provide a simple counterexample to the intuitive conjecture that an optimal policy will necessarily reach a decision in all cases. We then derive heuristic approximations in both Bayesian and distribution-free settings and demonstrate their superiority to bandit-based heuristics in one-shot decision problems and in Go.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Selecting Computations: Theory and Applications %A Nicholas Hay %A Stuart Russell %A David Tolpin %A Solomon Eyal Shimony %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-hay12a %I PMLR %P 344--353 %U https://proceedings.mlr.press/r10/hay12a.html %V R10 %X Sequential decision problems are often approximately solvable by simulating possible future action sequences. Metalevel decision procedures have been developed for selecting which action sequences to simulate, based on estimating the expected improvement in decision quality that would result from any particular simulation; an example is the recent work on using bandit algorithms to control Monte Carlo tree search in the game of Go. In this paper we develop a theoretical basis for metalevel decisions in the statistical framework of Bayesian selection problems, arguing (as others have done) that this is more appropriate than the bandit framework. We derive a number of basic results applicable to Monte Carlo selection problems, including the first finite sampling bounds for optimal policies in certain cases; we also provide a simple counterexample to the intuitive conjecture that an optimal policy will necessarily reach a decision in all cases. We then derive heuristic approximations in both Bayesian and distribution-free settings and demonstrate their superiority to bandit-based heuristics in one-shot decision problems and in Go. %Z Reissued by PMLR on 04 October 2026.
APA
Hay, N., Russell, S., Tolpin, D. & Shimony, S.E.. (2012). Selecting Computations: Theory and Applications. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:344-353 Available from https://proceedings.mlr.press/r10/hay12a.html. Reissued by PMLR on 04 October 2026.

Related Material