liveBook · Manning

Chapter 7: Monte Carlo Tree Search: Searching with Reinforcement Learning Principles

What you will learn in chapter 7 of Applied Reinforcement Learning

This introduction presents Monte Carlo tree search as a blend of simulation, planning, and learning for exploring sequential decisions under uncertainty.

After this chapter you will be able to

What it builds on

Section by section

Introduction

This introduction presents Monte Carlo tree search as a blend of simulation, planning, and learning for exploring sequential decisions under uncertainty.

Key terms: Monte Carlo Tree Search, Monte Carlo simulation, Markov decision processes, dynamic programming, temporal-difference learning, exploration, tree-like decisions, simulate outcomes, uncertainty, vehicle routing

7.1 Tree data structure and its applications in business

This section introduces tree structures as maps of branching business decisions and illustrates them with a vehicle-routing example.

Key terms: node, parent–child relationships, root node, edge, leaf node, directed acyclic graph, decision tree, Depot, route, accumulated cost

7.2 Fundamental tree search algorithms

This section explains breadth-first and depth-first tree search through a vehicle-routing example and compares their guarantees and practical limitations.

Key terms: root node, child node, path, cost, Breadth-First Search, BFS, queue, FIFO, level, Depth-First Search

7.3 Monte Carlo tree search theory and algorithm

This section explains how Monte Carlo Tree Search selectively builds and evaluates a search tree through repeated four-phase cycles.

Key terms: Monte Carlo Tree Search, exploration, exploitation, BFS, DFS, Selection, UCB1, exploitation term, exploration term, visit count

7.4 Solving capacitated vehicle routing problem with Monte Carlo tree search

The section applies Monte Carlo tree search and local route improvement to a capacitated vehicle routing problem.

Key terms: Capacitated Vehicle Routing Problem, capacity constraints, total distance, CVRPInstance, coords, demands, depot, Euclidean distance, CVRPState, routes

7.5 Summary

Concepts explained in this chapter

← Chapter 6: Tabular Reinforcement Learning Chapter 8: Deep Q-Networks for High-dimensional Data →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.