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