Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds

Understand

Monte Carlo Tree Search (MCTS), most famously used in game-play artificial intelligence (e.g., the game of Go), is a well-known strategy for constructing approximate solutions to sequential decision problems.

• Its primary innovation is the use of a heuristic, known as a default policy, to obtain Monte Carlo estimates of downstream values for states in a decision tree.
• This information is used to iteratively expand the tree towards regions of states and actions that an optimal policy might visit.
• However, to guarantee convergence to the optimal action, MCTS requires the entire tree to be expanded asymptotically.