text: UCT, a state-of-the art algorithm for Monte Carlo tree search (MCTS) in games and Markov decision processes, is based on UCB1, a sampling policy for the Multi-armed Bandit problem (MAB) that minimizes the cumulative regret. However, search differs from MAB in that in MCTS it is usually only the final "arm pull" (the actual move selection) that collects a reward, rather than all "arm pulls". In this paper, an MCTS sampling policy based on Value of Information (VOI) estimates of rollouts is suggested. Empirical evaluation of the policy and comparison to UCB1 and UCT is performed on random MAB instances as well as on Computer Go.
  @cite_0: Sequential decision problems are often approximately solvable by simulating possible future action sequences; such methods are a staple of gameplaying algorithms, robot path planners, model-predictive control systems, and logistical planners in operations research. Since the 1960s, researchers have sought effective metareasoning methods for selecting which action sequences to simulate, basing their approach on some estimate of the expected improvement in decision quality resulting from any particular simulation. Recently, this approach has been applied successfully in the context of Monte Carlo tree search, where each simulation takes the form of a randomized sequence of actions leading to a terminal state. In particular, the UCT algorithm borrows asymptotically optimal selection rules from the theory of bandit problems and has led to a new generation of master-level Go programs such as MoGo. We argue that, despite this success, the bandit framework is inappropriate as a basis for selecting computations. We propose instead a theoretical framework for metareasoning that is isomorphic to the statistical framework of ranking and selection. In this framework, we describe two apparently distinct conceptual approaches to the forward search metareasoning problem and prove them to be equivalent. We derive a number of basic results applicable to simple Monte Carlo selection problems, including asymptotic regret bounds, and discuss prospects for their extension to combinatorial settings.
  @cite_9: 
  @cite_6: Although many investigators affirm a desire to build reasoning systems that behave consistently with the axiomatic basis defined by probability theory and utility theory, limited resources for engineering and computation can make a complete normative analysis impossible. We attempt to move discussion beyond the debate over the scope of problems that can be handled effectively to cases where it is clear that there are insufficient computational resources to perform an analysis deemed as complete. Under these conditions, we stress the importance of considering the expected costs and benefits of applying alternative approximation procedures and heuristics for computation and knowledge acquisition. We discuss how knowledge about the structure of user utility can be used to control value tradeoffs for tailoring inference to alternative contexts. We address the notion of real-time rationality, focusing on the application of knowledge about the expected timewise-refinement abilities of reasoning strategies to balance the benefits of additional computation with the costs of acting with a partial result. We discuss the benefits of applying decision theory to control the solution of difficult problems given limitations and uncertainty in reasoning resources.
summary: A different scheme for control of sampling can use the principles of bounded rationality @cite_6 and rational metareasoning @cite_9 @cite_0 . In search, one maintains a current best action @math , and finds the expected gain from finding another action @math to be better than the current best.