Bandit Based Monte-Carlo Planning
Lecture notes in computer sciencePublished 1 January 2006
Levente Kocsis, Csaba Szepesvári
Citations2,802
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new algorithm is introduced, UCT, that applies bandit ideas to guide Monte-Carlo planning and is shown to be consistent and finite sample bounds are derived on the estimation error due to sampling.
Abstract
For large state-space Markovian Decision Problems Monte-Carlo planning is one of the few viable approaches to find near-optimal solutions. In this paper we introduce a new algorithm, UCT, that applies bandit ideas to guide Monte-Carlo planning. In finite-horizon or discounted MDPs the algorithm is shown to be consistent and finite sample bounds are derived on the estimation error due to sampling. Experimental results show that in several domains, UCT is significantly more efficient than its alternatives.
Keywords
Computer ScienceDecision Sciences
Machine LearningFinite-time Analysis of the Multiarmed Bandit Problem
5,812 Citations2002Peter Auer, Nicolò Cesa‐Bianchi +1 more
This work shows that the optimal logarithmic regret is also achievable uniformly over time, with simple and efficient policies, and for all reward distributions with bounded support.
SIAM Journal on ComputingThe Nonstochastic Multiarmed Bandit Problem
2,213 Citations2002Peter Auer, Nicolò Cesa‐Bianchi +2 more
A solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs.
Artificial IntelligenceThe challenge of poker
271 Citations2002Darse Billings, Aaron Davidson +2 more
The design considerations and architecture of the poker program Poki are described, which is a program capable of playing reasonably strong poker, but there remains considerable research to be done to play at world-class level.
arXiv (Cornell University)On-line Policy Improvement using Monte-Carlo Search
210 Citations2025Gerald Tesauro, Gregory R. Galperin
A Monte-Carlo simulation algorithm for real-time policy improvement of an adaptive controller and results are reported for a wide variety of initial policies, ranging from a random policy to TD-Gammon, an extremely strong multi-layer neural network.
A sparse sampling algorithm for near-optimal planning in large Markov decision processes
181 Citations1999Michael Kearns, Yishay Mansour +1 more
Operations ResearchAn Adaptive Sampling Algorithm for Solving Markov Decision Processes
140 Citations2005Hyeong Soo Chang, Michael C. Fu +2 more
An adaptive sampling algorithm that adaptively chooses which action to sample as the sampling process proceeds and generates an asymptotically unbiased estimator, whose bias is bounded by a quantity that converges to zero at rate (lnN)/ N.
Advances in Computer GamesMonte-Carlo Go Developments
125 Citations2004Bruno Bouzy, Bernard Helmstetter
Two Go programs are described, Olga and Oleg, developed by a Monte-Carlo approach that is simpler than Bruegmann’s (1993) approach, and the ever-increasing power of computers lead us to think that Monte- carlo approaches are worth considering for computer Go in the future.
Artificial IntelligenceWorld-championship-caliber Scrabble☆☆SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the USA by Hasbro Inc., in Canada by Hasbro Canada Corporation, and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc.
124 Citations2002Brian Sheppard
MAVEN combines a selective move generator, simulations of likely game scenarios, and the B* algorithm to produce a world-championship-caliber Scrabble-playing program.
Monte Carlo planning in RTS games
105 Citations2005Michael C. Chung
A framework — MCPlan — for Monte Carlo planning is presented, its performance parameters are identified, and the results of an implementation in a capture– the–flag game are analyzed.
European Conference on Artificial IntelligenceOn-line search for solving Markov Decision Processes via heuristic sampling
45 Citations2004Laurent Péret, Frédérick Garçia
This paper investigates the problem of refining near optimal policies via online search techniques, tackling the local problem of finding an optimal action for a single current state of the system, and considers an on-line approach based on sampling: at each step, a randomly sampled look-ahead tree is developed to compute the optimalaction for the current state.
An analysis of forward pruning
42 Citations1994Stephen J. Smith, Dana Nau
In studies, forward pruning did better than minimaxing when there was a high correlation among the minimax values of sibling nodes in a game tree, and this result suggests that forward pruned may possibly be a useful decision-making technique in certain kinds of games.