3. Monte Carlo Tree Search

Monte Carlo Tree Search

In Monte Carlo Tree Search, we exploit the principles of Monte-Carlo and confine them within a tree-search paradigm. We simulate outcomes within the tree, allowing us to make a decision. We return the results and permeate their impact through the tree.

We run through the following steps:

• Selection: recursively select optimal child nodes; repeat until leaf node is reached
• Expansion: expands to new leaf node in tree (assuming not terminal); moves to new leaf node
• Simulation: run default (random) policy from expansion state; runs until terminal states or number simulations reached (i.e. one episode)
• Backpropagation: resulting reward from simulation episode passed back through the tree; returns to selection and repeats

Link to original

Advantages and Disadvantages of MCTS

Advantages	Disadvantages
Very simple to implement	Re-expansion of states
Better than random rollouts	Uncontrolled search
Limited memory needs	Information lost when move is made

[animate example]

MCTS with Memorisation

MCTS with Memorisation

Instead of losing the Monte Carlo Tree after decision, store it in memory. Expansions are now much faster and we can re-use existing reward values in a given state.

Link to original

[animate example]

Advantages and Disadvantages of MCTS with Memorisation

Advantages	Disadvantages
Storage saves on re-expansions	High memory costs
Previously learned knowledge re-usable	Uncontrolled search

UCT Algorithm

UCT Algorithm

“Upper Confidence Bound applied to Trees”: improve selection / expansion process by guiding the search more effectively.

When selecting nodes, we consider:

• total number of simulations ran at a given node
• total number of winning simulations
• number of simulations ran by parent node

The UCT Algorithm uses:

$$\frac{w_i}{s_i}+c\cdot \sqrt{\frac{\ln s_p}{s_i}}$$

• where $w_i$ is the number of simulations won from this node
• where $s_i$ is the total number of simulations ran from this node
• where $s_p$ is the total number of simulations ran from parent node
• where $c$ is the exploration parameter

The $\frac{w_i}{s_i}$ is the exploitation term, i.e. the average win rate. The $\sqrt{\frac{\ln s_p}{s_i}}$ is the exploration term, the less frequently a node has been selected for expansion / simulation, the larger the value. The $c$, exploration parameter, is used to control the exploration / exploitation trade-off. Typically $c=\sqrt{2}$.

After running backpropagation, we run the UCT Algorithm on all of the states.

Link to original