7 Monte Carlo Tree Search: Searching with Reinforcement Learning Principles
Monte Carlo Tree Search is presented as a practical way to make sequential decisions when the full search space is far too large to inspect exhaustively. The chapter frames decisions like vehicle routing as a branching tree, where each state leads to new choices and each complete path represents a candidate solution. It first builds the intuition for trees as hierarchical structures that capture planning problems, then shows how basic search methods such as breadth-first and depth-first search work, along with their strengths and limitations. These classical methods help explain why a smarter, sampling-based approach is needed for complex optimization problems.
The core of the chapter is the MCTS framework, which combines ideas from Monte Carlo simulation, planning, and reinforcement learning. Instead of exploring every branch equally, MCTS repeats a four-step loop: selection, expansion, simulation, and backpropagation. Selection uses the UCB1 rule to balance exploration and exploitation, expansion adds one new branch at a time, simulation completes the partial solution with a rollout policy, and backpropagation updates statistics so future choices improve. This creates a search process that concentrates computation on the most promising parts of the tree while still keeping weaker or less visited options in play.
The chapter then applies MCTS to the capacitated vehicle routing problem, where multiple vehicles must serve customers without exceeding capacity constraints while minimizing total travel distance. It shows how to represent the problem state, define legal actions, compute route cost, and integrate heuristic improvements such as a greedy rollout policy and 2-opt local search. The implementation demonstrates how MCTS can gradually improve solutions over many iterations, achieving strong practical results on a difficult combinatorial problem. Overall, the chapter emphasizes that effective reinforcement learning for business problems often comes from combining several paradigms rather than relying on one method alone.
Tree data structure in vehicle route planning problem
Breadth-First Search (BFS) algorithm and flow.
Depth-First Search (DFS) algorithm and flow.
The four-phase cycle of Monte Carlo Tree Search.
UCB1 algorithm for node selection in MCTS.
Capacitated Vehicle Routing Problem (CVRP) schema.
Results of running MCTS for CVRP problem.
Summary
- Trees are hierarchical data structures where each node connects to children through parent-child relationships.
- A tree is, mathematically, a connected, directed acyclic graph with no loops, ensuring a unique path exists from root to any node.
- Breadth-First Search (BFS) explores trees level by level using a FIFO queue, guaranteeing the shortest path but consuming significant memory.
- Depth-First Search (DFS) explores one branch completely before backtracking using a LIFO stack (often implemented via recursion), using less memory but not guaranteeing shortest paths.
- Both BFS and DFS struggle with exponential growth in routing problems—with 10 customers there are 3.6 million possible routes, making exhaustive search infeasible.
- MCTS intelligently balances exploration (trying new branches) and exploitation (focusing on promising paths) rather than exhaustively searching every possibility.
- MCTS blends sampling from Monte Carlo simulation, state-action-value structure from MDPs, planning discipline from dynamic programming, and incremental updates from temporal-difference learning.
- MCTS operates in four phases iteratively: Selection (navigate tree), Expansion (add new node), Simulation (complete solution), and Backpropagation (update statistics).
- Selection navigates down the tree using UCB1 at each level until reaching a node with unexplored actions or a terminal state.
- Expansion adds one new child node per iteration by trying an untried action, building the tree incrementally guided by selection.
- Simulation completes a partial solution from the expanded node using a rollout policy (often random or greedy), providing an outcome estimate without perfect planning.
- Backpropagation walks from the expanded node to root, updating visit counts and total rewards at each node along the path, enabling statistical learning.
- Modern practitioners don't dogmatically choose one paradigm but understand when each fits and how to combine them, as MCTS itself demonstrates by synthesizing multiple approaches.
- MCTS represents pragmatic reinforcement learning—embracing both computational power and limitations, using intelligent exploration with simulation-based evaluation to find high-quality solutions in reasonable time.
Applied Reinforcement Learning ebook for free
