Bandit Based Monte-Carlo Planning

By Levente Kocsis, Csaba Szepesvari. 2006

3,947 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Investigating Contingency Awareness Using Atari 2600 Games (2012, background): “Solving these harder games may require more elaborate reinforcement learning techniques, such as smarter exploration (Brafman and Tennenholtz 2003), temporally extended actions (Sutton, Precup, and Singh 1999) or Monte- Carlo Tree Search (Kocsis and Szepesvári 2006).”
The Arcade Learning Environment: An Evaluation Platform for General Agents (2012, methodology): “The UCT algorithm, developed by Kocsis and Szepesvári (2006), deals with the exploration-exploitation dilemma by treating each node of a search tree as a multi-armed bandit problem.”
Scalable agent alignment via reward modeling: a research direction (2018, methodology): “A model-based RL agent learns an explicit model of the environment which it can use with a planning algorithm such as Monte Carlo tree search (Abramson, 1987; Kocsis & Szepesvári, 2006).”
Thinking Fast and Slow with Deep Learning and Tree Search (2017, methodology): “Possible tree search algorithms include Monte Carlo Tree Search [7], α - β Search, and Greedy Search [6] The canonical apprentice is a deep neural network parametrisation of the policy.”
Mastering Atari, Go, chess and shogi by planning with a learned model (2019, methodology): “Our approach is based upon Monte-Carlo tree search with upper confidence bounds, an approach to planning that converges asymptotically to the optimal policy in single agent domains and to the minimax value function in zero sum games [22].”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “Search Algorithms There are two classical search algorithms for zero-sum turn-taking games of perfect information: minimax (and alpha-beta) search [29, 59], and Monte Carlo tree search (MCTS) [18, 30, 16].”
Surprising Negative Results for Generative Adversarial Tree Search (2018, methodology): “For planning ( ii ), one can use upper conﬁdence bound tree search (UCT) (Kocsis & Szepesvári, 2006) or policy gradient methods (Kakade, 2002; Schulman et al., 2015).”
TreeQN and ATreeC: Differentiable Tree Planning for Deep Reinforcement Learning (2017, methodology): “This paper focuses on a simple tree-search with a deterministic transition function and no value uncertainty estimates, but our approach can be extended to tree-search variants like UCT (Kocsis & Szepesv´ari, 2006; Silver et al., 2016) if the components remain differentiable.”
Planning chemical syntheses with deep neural networks and symbolic AI (2017, background): “[28–30] These properties suggest that MCTS could be effective in synthesis planning as well.”
Value Prediction Network (2017, methodology): “This heuristic visits reasonably good abstract states during planning, though a more principled way such as UCT [16] can also be used to balance exploration and exploitation.”
Action-Conditional Video Prediction using Deep Networks in Atari Games (2015, methodology): “[11] used the ALE-emulator for making action-conditional predictions with slow UCT [15], a Monte-Carlo tree search method, to generate training data for a fast-acting CNN, which outperformed DQN on several domains.”
GreedyNAS: Towards Fast One-Shot NAS With Greedy Supernet (2020, methodology): “Moreover, we also adopt an exploration and exploitation policy [14, 24] by introducing a candidate pool, which dynamically tracks those potentially-good paths discovered during training.”
A Survey on Neural Architecture Search (2019, methodology): “A popular algorithm in this domain is the UCT algorithm (Kocsis and Szepesvári, 2006) which has been adopted in different ways for neural architecture search.”
Benchmark and Survey of Automated Machine Learning Frameworks (2019, methodology): “Monte-Carlo tree search (Kocsis & Szepesvári, 2006; Browne et al., 2012) is a heuristic best-first tree search algorithm.”
DeepArchitect: Automatically Designing and Training Deep Architectures (2017, methodology): “MCTS uses two policies: a tree policy , which determines the path to be traversed from the root to the frontier of the already expanded tree; and a rollout policy , which determines the path to be traversed from the frontier of the already expanded tree until a leaf is reached.”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “Recent proposed optimistic optimization methods provide an alternative to Bayesian optimization [31], [87], [116].”
RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “uld correspond to each other, since either the environment or its model is executed. The MCTS selection step begins in the start state, which is the root of the game tree that is traversed using UCB1 [57] as the tree policy. If a tree-node is visited the ﬁrst time, it is expanded with an initial val”
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (2015, background): “The sailing domain (Kocsis & Szepesv´ari, 2006) is a stochastic shortest-path problem, where the agent sails on a grid (in our experiment, a map of size 10 × 10 ) with wind blowing in random directions, aiming at the terminal location on the top-right corner.”