Deep Reinforcement Learning

Model-Based Learning and Monte Carlo Tree Search

Published: 2026-08-16

Level: postgraduate

Audience: Postgraduate students in Deep Reinforcement Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Model-Based vs Model-Free RL — covered in Lecture 2 (Section 2.4) and Lecture 7 (Section 7.2)
Upper Confidence Bound (UCB) Action Selection — covered in Lecture 3 (Section 3.7)
Value Iteration Algorithm — covered in Lecture 5 (Section 5.10) and Lecture 6 (Section 6.2)
Monte Carlo Methods — covered in Lectures 7 and 8 (for understanding the Monte Carlo return computation used in MCTS)

15.1 Model-Based versus Model-Free Reinforcement Learning

Hook: Suppose you are dropped into a maze with no map. You could wander randomly and memorize which corridors lead to dead ends (model-free), or you could spend time building a mental map and then plan your route before each turn (model-based). Reinforcement learning faces the same fork in the road — and the choice between these two strategies shapes every algorithm that follows.

Intuition and Analogy

Reinforcement learning algorithms split into two broad families depending on whether the agent knows — or can learn — the dynamics of the environment. Think of it like navigating a new city:

Model-based (the cartographer): You carry a map. Before choosing a direction, you trace routes on the map and pick the best one. The map tells you what happens when you turn left or right — which street you end up on, whether there is traffic.
Model-free (the explorer): You have no map. You walk around, remember which intersections led to good restaurants, and build a gut feeling for which direction is promising. You never explicitly learn the street layout — you just learn which actions pay off.

The analogy breaks down when the city is constantly changing its streets (non-stationary environments), but it captures the core idea: model-based agents simulate the future before acting; model-free agents learn directly from past rewards.

Formalize

A model in this context means the probabilistic transition information — given a state $s$ and an action $a$ , the model tells you the next state $s^{'}$ and the reward $r$ . Formally, the model is the tuple:

$M = ⟨ P (s^{'} ∣ s, a), R (s, a)⟩$

where:

$P (s^{'} ∣ s, a)$ is the transition probability — the probability of landing in state $s^{'}$ after taking action $a$ in state $s$ ,
$R (s, a)$ is the expected reward — the average reward received after taking action $a$ in state $s$ .

Model-based reinforcement learning means the agent has access to this model $M$ and can use it to plan ahead. Model-free reinforcement learning means the agent has no model and must learn a policy or value function purely from sampled experience — trajectories of the form $τ = (s_{0}, a_{0}, r_{1}, s_{1}, a_{1}, r_{2}, \dots)$ .

Dynamic programming (value iteration, policy iteration) is the canonical model-based algorithm family. In dynamic programming, the environment's transition probabilities are given like an oracle — the agent knows $P (s^{'} ∣ s, a)$ and $R (s, a)$ for every state-action pair before interacting with the environment. This makes planning trivial: the agent can simulate any trajectory without actually executing it.

Monte Carlo methods and temporal difference (TD) learning, on the other hand, are model-free. They rely entirely on sampled experience to estimate value functions and derive policies. They never require explicit knowledge of the transition dynamics.

The fundamental question of modern model-based RL: What if the model is not given to us, but we can learn it from experience? If the agent has accumulated a collection of trajectories, it can attempt to estimate $P (s^{'} ∣ s, a)$ and $R (s, a)$ from those samples. This learned model can then be used for planning — imagining possible futures, evaluating them, and selecting the best action. This is the motivation behind decision-time planning: rather than committing to a single action based on past experience alone, the agent builds an internal model of the world and uses it to look ahead before each decision.

15.1.1 Learning Model Dynamics from Experience

When the environment is small and deterministic — meaning there is little randomness in transitions — learning a model is straightforward. Every time the agent takes action $a$ in state $s$ and observes the next state $s^{'}$ , that observation is a data point for the transition $P (s^{'} ∣ s, a)$ . After enough experience, the agent can estimate these probabilities from visit counts using frequentist estimation:

$P^(s^{'} ∣ s, a) = \frac{count ( s , a , s ^{'} )}{count ( s , a )}$

where $count (s, a, s^{'})$ is the number of times the transition $s a s^{'}$ was observed, and $count (s, a)$ is the total number of times action $a$ was taken in state $s$ .

Worked example — estimating a transition model from data. Consider a tiny environment with three states ${s_{1}, s_{2}, s_{3}}$ and two actions ${L, R}$ . After 20 episodes, the agent has the following transition counts from state $s_{1}$ taking action $R$ :

Outcome	Count
$s_{1} R s_{2}$	12
$s_{1} R s_{3}$	8

The estimated transition probabilities are: $P^(s_{2} ∣ s_{1}, R) = \frac{12}{20} = 0.6, P^(s_{3} ∣ s_{1}, R) = \frac{8}{20} = 0.4$ Sense check: The probabilities sum to $0.6 + 0.4 = 1.0$ , which is correct since these are the only two possible outcomes.

However, in large or continuous state-action spaces, learning an accurate model becomes challenging. Some states may never be visited, transitions may be highly complex, and biased experience can produce a poor model. The learned model is only as good as the data it is trained on.

A natural question arises: is learning a model from experience not just supervised learning? The answer is yes, in a sense. The field of world models — learning an internal model of the environment — began with supervised learning applied to reinforcement learning. A neural network is trained to predict the next state and reward given the current state and action, which is a standard supervised regression problem. Over time, this approach evolved into purely RL-based methods, but the supervised learning heritage remains. Two major computer programmes based on this concept — AlphaGo and AlphaZero — will be discussed in detail later in this lecture.

Scope: Model-based methods are most effective when (1) the state space is small enough that most states get visited repeatedly, (2) transitions are relatively low-noise, and (3) the model can be queried cheaply during planning. In high-dimensional continuous environments (e.g., robotic manipulation with images as states), learning an accurate model of $P (s^{'} ∣ s, a)$ may be infeasible — this is where model-free methods have the advantage.

15.1.2 Challenges of Model-Based RL

The major advantage of model-based methods is clear: having a model gives the agent an extra edge. If you know how the world responds to your actions, you can plan and choose better actions. But the challenges are significant:

Pitfall — confusing the model with the policy. A common beginner mistake is to think that "model-based" means the agent has a pre-programmed policy. It does not. The model is knowledge of the environment dynamics ( $P, R$ ), not a recipe for action. The agent still needs a planning or learning algorithm to turn that model into a policy.

Large state-action spaces: When the state space is enormous, it may be impossible to learn an accurate model for every state, especially rarely visited ones. For a game like Go with approximately $1 0^{170}$ legal board positions, memorizing transition probabilities for every state is infeasible.

Complex transitions: Highly continuous tasks make generating representative episodes difficult. A robotic arm with 7 degrees of freedom has a continuous state space where no two states are exactly alike.

Biased experience: If the agent's experience is dominated by a narrow set of state-action pairs, the learned model will be biased. For instance, if a trajectory contains 10 samples where 9 share the same state-action pair $(s_{1}, a)$ and only 1 uses $(s_{2}, a)$ , the model will be heavily biased toward predicting the outcome of $(s_{1}, a)$ . This is analogous to surveying only one neighbourhood of a city and assuming the whole city looks the same.

Noisy transitions: Models work best when transitions are relatively error-free. In environments with high stochasticity, the learned model may not capture the true dynamics accurately.

Recap: Model-based RL gives the agent the ability to plan by simulating futures through an explicit model of the environment. Model-free RL skips the model and learns directly from experience. The modern model-based approach learns the model from data — a supervised learning problem embedded inside an RL pipeline. The trade-off is clear: models enable smarter planning, but learning an accurate model is itself a hard problem, especially in large or stochastic environments. The next section introduces MCTS, a model-based planning algorithm that builds on these ideas.

15.1.3 Exam Notes

Exam note: Understanding the distinction between model-based and model-free is fundamental. Know that dynamic programming is model-based (model given as oracle), Monte Carlo and TD are model-free (no model), and the modern model-based approach learns the model from experience. Be able to give one concrete example of each family.

15.2 Monte Carlo Tree Search (MCTS)

Hook: In chess, a grandmaster does not calculate every possible sequence of moves — there are roughly $1 0^{120}$ possible games. Instead, they focus on a handful of promising lines and think a few moves deep along each. Monte Carlo Tree Search gives a computer the same ability: explore the most promising branches of a game tree intelligently, rather than exhaustively.

Monte Carlo Tree Search (MCTS) is a decision-time planning algorithm. It is not a policy optimization method or a value estimation method — it is a planner. At every new state the agent encounters during online interaction, MCTS runs a planning routine to decide which action to take next. The algorithm builds a search tree incrementally — one branch at a time — using intelligent heuristics to decide which parts of the tree to explore, rather than expanding all possibilities exhaustively.

Purpose. MCTS solves the problem of online planning in large action spaces. When the branching factor is too high for exhaustive search (as in Go, where each position has roughly 250 legal moves), MCTS provides a way to allocate limited computation to the most promising parts of the game tree.

Intuition and the Min-Max Contrast

The key contrast is with min-max trees from classical game-tree search. In a min-max tree (as taught in computational intelligence courses), the search is exhaustive: starting from the current board position, every possible move is expanded, then every counter-move, and so on until terminal states are reached. The values are then propagated back using a min-max strategy. This works for small games like tic-tac-toe but becomes computationally impossible for complex games like Go, where the branching factor is enormous.

MCTS replaces this exhaustive search with intelligent searching. Instead of expanding every child node, the algorithm uses an action selection strategy (Upper Confidence Bound, or UCB) to decide which child is most promising and expands only that one. The less promising branches are left untouched — they may be explored later if other branches prove less fruitful. This makes MCTS feasible for games with very large state spaces where exhaustive search is impossible.

Student Q:

Q: We saw Monte Carlo earlier as a model-free algorithm. What is the difference between that and Monte Carlo Tree Search?

A: The name "Monte Carlo Tree Search" comes from the fact that one of its four phases — the simulation phase — uses a Monte Carlo technique for computing returns. The full algorithm has four phases (selection, expansion, simulation, and backpropagation), and only the simulation phase uses Monte Carlo-style discounted return calculation. So it is not the same as the Monte Carlo methods seen earlier (which were purely model-free value estimation methods); MCTS is a planning algorithm that borrows the Monte Carlo return computation for its rollout simulations.

15.2.1 The Four Phases of MCTS

Inputs and Outputs. At each decision point, the input to MCTS is the current state $s$ (the root of the search tree) and a model of the environment (learned or given). The output is a recommended action — typically the action with the highest visit count or highest estimated value at the root node.

MCTS has four phases that constitute one iteration of the algorithm. Each iteration refines the search tree by exploring one new path from the root to a terminal state:

Selection: Starting from the root node (the current state), the algorithm traverses the tree by repeatedly applying the UCB action selection criterion at each node. At each state node, it picks the action with the highest UCB value and follows it to the next node. This continues until a leaf node is reached — a node that has at least one unexplored child. The selection phase is what makes MCTS intelligent: instead of expanding every branch, it focuses on the most promising ones.

Expansion: Once a leaf node is selected, the algorithm expands it by adding one new child node to the tree. This child corresponds to applying one previously unexplored action from the leaf state. In the early stages of the game, expansion and simulation happen together — a new node is created and immediately simulated.

Simulation (Rollout): From the newly expanded node, the algorithm performs a complete random simulation until a terminal state is reached. This means: starting from the new state, repeatedly pick a random action from the available action space, transition to the next state, and continue until the episode ends. This random simulation is called a rollout. The target calculation in this rollout follows the Monte Carlo technique — discounted returns are computed from the terminal reward — which is why the algorithm is called "Monte Carlo Tree Search."

Backpropagation: After the simulation reaches a terminal state and the return is computed, this return is propagated back through every node along the path from the newly expanded node to the root. Each node's visit count and cumulative return are updated. This information guides future iterations: nodes with higher returns will be visited more often, and their UCB values will reflect their promise.

Trace of one iteration. Imagine a root node $s_{0}$ with actions ${A_{1}, A_{2}}$ . After several iterations, $A_{1}$ has been tried 10 times (average return 15) and $A_{2}$ has been tried 3 times (average return 8). UCB selects $A_{1}$ because it has the higher exploitation value. The algorithm follows $A_{1}$ to $s_{1}$ , which has two unexplored children. It picks one (say, leading to $s_{3}$ ), runs a random rollout from $s_{3}$ that returns $G = 22$ , then backpropagates: increment $N (s_{3})$ , update $Q (s_{1}, a_{13})$ , update $Q (s_{0}, A_{1})$ .

These four phases — selection, expansion, simulation, backpropagation — constitute one iteration. The algorithm is run for a fixed number of iterations (for example, 100 or 1000), and after all iterations are complete, the root node has enough information to make an informed action choice. The action with the highest estimated value (or highest visit count) is selected.

15.2.2 How MCTS is Positioned in the RL Loop

MCTS operates as a planner at each decision point. Consider an agent interacting with an environment in an episode: it starts at state $s_{0}$ , takes an action, transitions to $s_{1}$ , and so on. At each state $s_{t}$ , the agent runs a full MCTS procedure (many iterations of the four phases). The output of MCTS is a recommended action. The agent executes that action, transitions to the next state, and runs MCTS again from the new state.

This is what "decision-time planning" means: the planning happens at the moment of decision, using the current state as the root of the search tree. The trees built at $s_{0}$ and $s_{1}$ are independent — MCTS does not reuse the tree from one state when planning at the next (though in practice, some implementations do reuse subtrees for efficiency).

Student Q:

Q: If my model can imagine the future states and give a look-ahead vision, how does this help in practice?

A: Imagine playing a game of chess. The MCTS planner is like a coach telling you: "If you make this move, here is how the next 10 rounds are likely to play out." By evaluating these possible futures, you can pick the move that leads to the best outcome. Instead of blindly choosing an action, you envision the consequences first, evaluate them, and then decide. This futuristic vision is the core value of MCTS.

15.2.3 MCTS versus Min-Max: Key Differences

Aspect	Min-Max Tree	MCTS
Search strategy	Exhaustive: expand all children at every level	Incremental: expand one promising child per iteration
Tree construction	Built all at once before evaluation	Built iteratively over many iterations
Action selection	Deterministic (min or max)	Heuristic-driven (UCB)
Applicability	Small, low-dimensional games (tic-tac-toe)	Large, complex games (Go, chess)
Computational cost	Exponential in tree depth	Controlled by iteration count

The intelligence in MCTS comes from its action selection strategy. Rather than blindly expanding every branch, it uses UCB to focus on the most promising actions. This is the same UCB algorithm from multi-armed bandits, repurposed here for tree search.

15.2.4 Exam Notes

Exam note: MCTS is classified as a planning algorithm, not a policy optimization algorithm. It is a decision-time planner that runs at each state during online interaction. The four phases (selection, expansion, simulation, backpropagation) must be known in order. The backbone of MCTS is the rollout algorithm.

15.3 Upper Confidence Bound (UCB) Action Selection in MCTS

Hook: How do you decide which restaurant to try next — the one you know is good, or the new place you have never visited? UCB is the mathematical answer: balance what you know works (exploitation) against what you have not yet tried (exploration).

MCTS uses the Upper Confidence Bound (UCB) algorithm for action selection during the selection phase. UCB was introduced earlier in the course in the context of multi-armed bandits, and the same principle applies here: balance exploitation (choosing actions with high estimated value) with exploration (trying actions that have been selected fewer times and thus have uncertain value).

15.3.1 The UCB Formula and Its Components

The UCB Formula. The UCB formula for selecting an action $a$ from state $s$ is:

$UCB (s, a) = Q (s, a) + c \frac{ln N ( s )}{N ( s , a )}$

where:

$Q (s, a)$ is the current action-value estimate for taking action $a$ in state $s$ — this is the exploitation term. It represents the average return obtained so far when choosing action $a$ from state $s$ .
$N (s)$ is the total number of times state $s$ has been visited across all iterations,
$N (s, a)$ is the number of times action $a$ has been selected in state $s$ ,
$c > 0$ is an exploration constant that controls how much weight is given to exploration versus exploitation. Larger $c$ encourages more exploration; smaller $c$ makes the algorithm more greedy.
the term $\frac{l n N ( s )}{N ( s , a )}$ is the exploration bonus.

The exploration term captures the uncertainty associated with an action. If an action has been selected many times, $N (s, a)$ is large, making the exploration term small — we are already confident about this action's value. If an action has been selected few times, $N (s, a)$ is small, making the exploration term large — we are uncertain and should try it.

Numerical illustration of UCB. Suppose at state $s$ with $N (s) = 100$ total visits, we have two actions:

Action	$Q (s, a)$	$N (s, a)$	Exploration term ( $c = 1$ )	UCB
$A_{1}$	15.0	80	$ln 100/80 = 0.0576 = 0.24$	15.24
$A_{2}$	12.0	5	$ln 100/5 = 0.921 = 0.96$	12.96

$A_{1}$ is selected because its UCB (15.24) is higher. Even though $A_{2}$ has a larger exploration bonus, the exploitation gap is too wide. If $N (s, A_{2})$ were only 1, the exploration term would be $ln 100/1 = 2.15$ , giving UCB = 14.15 — still below $A_{1}$ .

Scope — when UCB applies. UCB assumes stationary reward distributions: the true value of each action does not change over time. In non-stationary environments (where the best action changes), UCB can be slow to adapt because the large visit counts from old data dominate the estimate. Modifications like sliding-window UCB or discounting old observations address this.

The practical effect: when a new state is first created in the tree, its children have $N (s, a) = 0$ , so their UCB values are infinity. This means newly created states will always be explored before revisiting already-explored ones. As iterations proceed and visit counts grow, the algorithm shifts from exploration to exploitation, focusing on actions that have demonstrated high returns.

Student Q:

Q: Why do newly created states have UCB equal to infinity?

A: Because the exploration term is $\frac{l n N ( s )}{N ( s , a )}$ . When $N (s, a) = 0$ (the action has never been selected), the denominator is zero, making the expression infinite. This is by design: it ensures that every action gets tried at least once before the algorithm starts comparing them based on their estimated values. Until an action has been explored, we cannot say anything about its quality, so UCB forces exploration first.

Pitfall — forgetting that UCB = infinity guarantees first-visit exploration. A common error in tracing MCTS iterations is to assume that when two unvisited actions exist, the algorithm picks the one with higher $Q$ . In fact, both have UCB = infinity, so the choice is arbitrary (typically random). Only after both have been visited at least once does the exploitation term $Q (s, a)$ influence the decision.

Recap: UCB balances exploitation (known good actions) and exploration (uncertain actions) using a clean mathematical formula. The infinity property for unvisited actions guarantees that every action is tried at least once. The exploration constant $c$ controls the trade-off. UCB is the mechanism that makes MCTS intelligent rather than random.

15.4 The Rollout Algorithm as MCTS Backbone

Hook: Before you decide which move to play in a board game, you could try each possible move and then play out the rest of the game randomly to see who wins. The move that leads to the most wins (or highest average score) is probably the best one. This is exactly what a rollout does — and it is the engine that powers MCTS simulations.

The rollout algorithm is the backbone of MCTS. A rollout is a complete random simulation from a given state to a terminal state. Starting from the current state, the agent picks actions uniformly at random from the available action space, transitions to the next state, and continues until the episode ends. The return from this simulation is computed using Monte Carlo-style discounted returns.

15.4.1 The Discounted Return Formula

Rollout return. The return calculation for a rollout that terminates after $T$ steps with rewards $r_{1}, r_{2}, \dots, r_{T}$ and discount factor $γ$ is:

$G = t = 1 \sum T γ^{t - 1} r_{t} = r_{1} + γ r_{2} + γ^{2} r_{3} + \dots + γ^{T - 1} r_{T}$

where:

$r_{t}$ is the reward received at step $t$ of the rollout,
$γ \in [0, 1]$ is the discount factor — how much future rewards are worth relative to immediate ones,
$T$ is the step at which the terminal state is reached.

Worked example — computing a rollout return. A rollout from state $s_{6}$ proceeds through states $s_{7}$ and $s_{8}$ to a terminal state. The rewards are $r_{s_{6} \to s_{7}} = 5$ , $r_{s_{7} \to s_{8}} = 8$ , $r_{s_{8} \to terminal} = 10$ , and the discount factor is $γ = 0.1$ .

Step-by-step computation:

$G = γ^{0} \cdot r_{1} + γ^{1} \cdot r_{2} + γ^{2} \cdot r_{3} = 1 \times 5 + 0.1 \times 8 + 0.01 \times 10 = 5 + 0.8 + 0.1 = 5.9$

Sense check: With $γ = 0.1$ , future rewards are heavily discounted. The first reward (5) dominates the return, which makes sense — the agent cares much more about the immediate reward than what comes two steps later. The final return of 5.9 is only slightly above the first reward, confirming the discounting effect.

This return is then backpropagated through the tree to update the value estimates of every node along the path. The Monte Carlo return calculation is what gives MCTS its name — the simulation phase uses Monte Carlo methods to estimate the value of states.

Pitfall — confusing the discount factor's role. A common error is to think $γ$ is a probability. It is not — $γ$ is a weighting parameter that controls how much the agent values future rewards relative to immediate ones. When $γ = 1$ , all future rewards count equally; when $γ = 0$ , only the immediate reward matters. The value $γ = 0.1$ in the example above is unusually small (used for illustration); typical values are 0.9 or 0.99.

15.4.2 Stochastic Environments and Multiple Outcomes

In deterministic environments, performing an action from a state always leads to the same next state. But in stochastic environments, the same action can lead to different states with different probabilities. For example, in a warehouse scenario with moving obstacles, a "move forward" action might succeed (the robot reaches the target location) or fail (the robot collides with an obstacle).

In MCTS, this manifests as a single action node having multiple possible child state nodes. Over multiple iterations, the tree accumulates information about which outcomes are more likely. The transition probabilities are learned from the visit counts during these iterations — this is how the model dynamics are learned from experience.

15.4.3 Exam Notes

Exam note: Know the return calculation formula for rollouts. Be able to compute the discounted return from a sequence of rewards given a discount factor $γ$ . Understand that MCTS is named after the Monte Carlo return computation used in the simulation phase, not after the model-free Monte Carlo methods seen earlier.

15.5 Learning Transition Probabilities from Experience

Hook: How does a self-driving car learn that turning the steering wheel right on a wet road sometimes skids and sometimes does not? It counts outcomes. After enough turns on wet roads, the ratio of "skid" to "clean turn" gives the transition probability. MCTS does the same thing — it learns the rules of the game by watching what happens.

A critical component of model-based MCTS is learning the transition probabilities $P (s^{'} ∣ s, a)$ from experience. These probabilities are not given to the agent — they must be estimated from the data accumulated during MCTS iterations.

Formalize

The estimation is straightforward frequentist counting. Let $N (s, a)$ denote the number of times action $a$ has been executed in state $s$ , and $N (s, a, s^{'})$ the number of those times the agent landed in state $s^{'}$ . Then:

$P^(s^{'} ∣ s, a) = \frac{N ( s , a , s ^{'} )}{N ( s , a )}$

This formula says: the estimated probability of transitioning to $s^{'}$ from $(s, a)$ is just the fraction of times that transition actually occurred. It is a maximum-likelihood estimate of the true transition probability, and it converges to the true value as $N (s, a) \to \infty$ by the law of large numbers.

Worked example — estimating transition probabilities in MCTS. Suppose that in state $s$ , action $a$ has been executed 5 times during MCTS iterations. Of those 5 times, the agent landed on state $s_{1}^{'}$ 3 times and on state $s_{2}^{'}$ 2 times. Then:

$P^(s_{1}^{'} ∣ s, a) = \frac{3}{5} = 0.6, P^(s_{2}^{'} ∣ s, a) = \frac{2}{5} = 0.4$

Sense check: $0.6 + 0.4 = 1.0$ — the probabilities sum to one, as required. If a third outcome $s_{3}^{'}$ were possible but never observed, its estimate would be $P^(s_{3}^{'} ∣ s, a) = 0/5 = 0$ , which is an underestimate due to small sample size. As more iterations accumulate, this estimate would correct itself.

These probabilities are learned during the course of the MCTS iterations. As the algorithm runs more iterations, the visit counts grow, and the transition probability estimates become more accurate.

The warehouse robot example illustrates this: a robot in a warehouse performs the action "move forward." Due to moving obstacles, the robot sometimes reaches its target location safely and sometimes gets collided with an obstacle. Out of multiple executions of "move forward," some land in the safe location and some in the collision state. The ratio of visits gives the transition probability.

This is the sense in which the "model is learned from experiences." The experiences are the trajectories generated during MCTS rollouts, and the model is the collection of transition probabilities estimated from those trajectories.

Pitfall — small sample sizes produce unreliable estimates. If an action has been tried only once or twice, the estimated transition probabilities are highly unreliable. $P^(s^{'} ∣ s, a) = 1/1 = 1.0$ does not mean the transition is deterministic — it means you have only one data point. UCB's exploration bonus helps mitigate this by encouraging the algorithm to try less-explored actions more often, which in turn produces better transition estimates.

Recap: Transition probabilities in MCTS are learned, not given. The frequentist estimator $P^(s^{'} ∣ s, a) = N (s, a, s^{'}) / N (s, a)$ converges to the true dynamics as visit counts grow. This is the mechanism by which MCTS implements model-based planning without requiring a pre-programmed model. Bridge: these learned probabilities guide the selection phase of MCTS, and the returns computed from rollouts are propagated back via the backpropagation step — the subject of the next two sections.

15.5.1 Exam Notes

Exam note: Transition probabilities in MCTS are computed from visit counts, not given a priori. The formula is $P^(s^{'} ∣ s, a) = \frac{N ( s , a , s ^{'} )}{N ( s , a )}$ . Know this formula and be able to compute it from a table of visit counts.

15.6 Backpropagation in MCTS

Hook: After a scout reports back from exploring a trail, the whole expedition updates its map. Backpropagation in MCTS works the same way — a rollout "scouts" a path to the end, and the resulting return flows backward through every node on the path, updating what we know about each decision point.

After a rollout reaches a terminal state and the return $G$ is computed, this return must be propagated back through every node along the path from the expanded node to the root. The backpropagation serves two purposes: updating the action-value estimates $Q (s, a)$ and incrementing the visit counts $N (s, a)$ .

15.6.1 The Incremental Update Formula

The Q-value update rule. The action-value estimate $Q (s, a)$ is updated using an incremental formula that is the same one used in multi-armed bandits:

$Q (s, a) \leftarrow Q (s, a) + α [target - Q (s, a)]$

where:

$α$ is the learning rate, set to $\frac{1}{N ( s , a )}$ — the inverse of the number of times this state-action pair has been visited. This is computed after incrementing $N (s, a)$ .
the "target" is the newly backpropagated return (discounted from the child node),
the term $[target - Q (s, a)]$ is the error — the difference between the new information and the existing estimate.

This update can be rewritten as a running average. If we denote the old $Q$ value as $Q_{old}$ and the new return as $G_{new}$ , then:

$Q_{new} = Q_{old} + \frac{1}{N} [G_{new} - Q_{old}] = (1 - \frac{1}{N}) Q_{old} + \frac{1}{N} G_{new} = \frac{( N - 1 ) \cdot Q _{old} + G _{new}}{N}$

This shows that $Q (s, a)$ is simply the sample mean of all returns observed through $(s, a)$ . The learning rate $α = 1/ N$ ensures that each return contributes equally to the average, regardless of when it was observed.

Worked example — incremental update. Suppose $Q (s, a)$ is currently 12.0 after 4 visits ( $N = 4$ ). A new rollout returns $G = 20$ . After incrementing $N$ to 5:

$Q (s, a) \leftarrow 12.0 + \frac{1}{5} (20 - 12.0) = 12.0 + 1.6 = 13.6$

Equivalently: $Q = (4 \times 12.0 + 20) /5 = 68/5 = 13.6$ . Sense check: The new return (20) is much higher than the old average (12), so $Q$ increases — by $1/5$ of the gap, as expected.

The learning rate $α = \frac{1}{N ( s , a )}$ means that early visits have a large impact on the estimate (because $N (s, a)$ is small), while later visits have diminishing impact as the estimate stabilizes. This is consistent with the UCB principle: actions that have been visited more times have more reliable estimates.

Pitfall — using the wrong N for the learning rate. The learning rate uses $N (s, a)$ after incrementing. If $N (s, a)$ was 3 before the update, the learning rate is $1/4$ , not $1/3$ . This is because we count the current visit as one of the observations.

15.6.2 State Tracking Information

Every state node in the MCTS tree keeps track of three quantities:

$N (s)$ : the total number of times state $s$ has been visited,
$W (s, a)$ : the total return accumulated through state-action pair $(s, a)$ ,
$Q (s, a)$ : the action-value estimate, which is $W (s, a) / N (s, a)$ or computed incrementally.

The relationship between these quantities is:

$Q (s, a) = \frac{W ( s , a )}{N ( s , a )}$

When backpropagating, both $W (s, a)$ and $N (s, a)$ are updated: $W (s, a) \leftarrow W (s, a) + G$ and $N (s, a) \leftarrow N (s, a) + 1$ . The $Q$ value can then be recomputed as the ratio, or updated incrementally as shown above.

This information is essential for both UCB action selection (which needs $N (s)$ and $N (s, a)$ ) and for making the final action decision after all iterations are complete. The action with the highest $Q (s, a)$ or the highest visit count $N (s, a)$ is selected as the best move.

Student Q:

Q: Why is the learning rate $\frac{1}{N ( s , a )}$ ?

A: This is the same incremental update rule used in multi-armed bandits. When a state-action pair has been visited many times, the existing estimate $Q (s, a)$ is already reliable, so new observations should have a small impact — hence a small learning rate. When a pair has been visited few times, the estimate is unreliable, so new observations should have a larger impact — hence a larger learning rate. The $\frac{1}{N}$ schedule ensures that each observation's influence diminishes as more data accumulates.

Recap: Backpropagation in MCTS uses the incremental mean update $Q \leftarrow Q + (1/ N) (target - Q)$ to maintain a running average of returns for each state-action pair. Each node tracks three quantities: visit count $N (s)$ , total return $W (s, a)$ , and action value $Q (s, a)$ . This information feeds both UCB selection in future iterations and the final action decision. Bridge: the next two sections work through complete numerical examples of MCTS with backpropagation.

15.7 MCTS Worked Numerical Example

Hook: Watching someone describe MCTS is like watching someone describe how to ride a bicycle — you only really understand it when you trace through the numbers yourself. This section walks through three full iterations of MCTS from scratch, showing exactly how the tree grows, how UCB selects actions, and how returns are backpropagated.

The professor worked through a detailed numerical example to illustrate how MCTS operates from its initial iteration through several subsequent ones.

15.7.1 Iteration 1: Initial Tree Construction

Iteration 1 — building the tree from scratch. Starting at state $s_{0}$ with two possible actions $A_{1}$ and $A_{2}$ :

Quantity	Value	Reason
$N (s_{0})$	1	Root visited once at the start
$s_{1}$ (child via $A_{1}$ )	newly created	$N (s_{1}) = 0$
$s_{2}$ (child via $A_{2}$ )	newly created	$N (s_{2}) = 0$
UCB( $s_{0}, A_{1}$ )	$\infty$	$N (s_{0}, A_{1}) = 0$ → exploration term = $\infty$
UCB( $s_{0}, A_{2}$ )	$\infty$	$N (s_{0}, A_{2}) = 0$ → exploration term = $\infty$

Since both UCB values are infinity, the algorithm randomly selects $A_{1}$ (leading to $s_{1}$ ).

$s_{1}$ is visited, so $N (s_{1}) = 1$ .
From $s_{1}$ , a rollout (random simulation) is performed to a terminal state.
The return from this rollout is $G = 20$ .
Backpropagation: The return $G = 20$ flows back: update $Q (s_{0}, A_{1})$ and increment $N (s_{0}, A_{1})$ .

State after iteration 1:

Node	$N$	$Q$ or return
$s_{0}$	1	—
$s_{1}$	1	Return via $A_{1}$ : 20
$s_{2}$	0	Not yet visited

15.7.2 Iteration 2: Exploring the Unvisited Branch

Iteration 2 — UCB forces exploration. Starting again at $s_{0}$ :

Action	$Q (s_{0}, a)$	$N (s_{0}, a)$	UCB
$A_{1}$	20	1	finite (exploitation = 20, exploration = $c ln 1/1$ )
$A_{2}$	?	0	$\infty$ (never visited)

Since UCB( $s_{0}, A_{2}$ ) = $\infty >$ UCB( $s_{0}, A_{1}$ ), $A_{2}$ is selected — even though $A_{1}$ had a return of 20. The algorithm must try everything at least once.

$s_{2}$ is visited, $N (s_{2}) = 1$ .
A rollout from $s_{2}$ returns $G = 10$ .
Backpropagation: Update $Q (s_{0}, A_{2})$ and increment $N (s_{0}, A_{2})$ .

State after iteration 2:

Node	$N$	Return
$s_{0}$	2	—
$s_{1}$	1	20 via $A_{1}$
$s_{2}$	1	10 via $A_{2}$

15.7.3 Iteration 3: Expanding a Previously Visited Node

Iteration 3 — exploitation wins. Starting again at $s_{0}$ :

Now both children have been visited at least once, so the exploitation term matters.

Action	$Q (s_{0}, a)$	UCB (approx)
$A_{1}$	20	21.6
$A_{2}$	10	11.6

$A_{1}$ has the higher UCB, so it is selected. The algorithm moves to $s_{1}$ .

Since $s_{1}$ has already been visited (it has a child from iteration 1), the algorithm must expand it — create a new child. The children of $s_{1}$ are created (the actions available at $s_{1}$ are represented as child nodes). Since the children are newly created and have equal UCB values (both infinity), one is randomly selected.

A rollout is performed from the selected child, and the return is backpropagated through the entire path: child → $s_{1}$ → $s_{0}$ .

Key insight: This illustrates the core behavior of MCTS — promising branches (those with higher returns) are revisited and expanded deeper, while less promising branches are explored less frequently. Over many iterations, the tree grows deeper along the most promising paths.

Pitfall — assuming expansion always happens at the root. In iteration 3, the algorithm did not expand $s_{0}$ (which already has children). It descended to $s_{1}$ and expanded there. MCTS always expands at the leaf level — the deepest unexpanded node along the UCB-selected path.

Recap: Over three iterations, the MCTS tree grew from just a root to a root with two children, and then one child was expanded deeper. UCB ensured both branches were tried (iteration 2 forced exploration of the inferior $A_{2}$ ), and then exploitation directed further expansion toward the more promising $A_{1}$ branch. Bridge: the next section works through the backpropagation arithmetic in detail with discounted returns.

15.7.4 Exam Notes

Exam note: Be prepared to trace through MCTS iterations. Understand when UCB is infinity (unvisited states), when expansion versus simulation occurs, and how visit counts and returns are updated after each iteration. The professor emphasized that the number of iterations equals the number of times the initial state is visited.

15.8 Backpropagation Worked Example with Discounted Returns

Hook: The backpropagation formulas look simple, but when you have a tree three levels deep with discounting at each level, the arithmetic gets tricky. This section traces every number so you can confidently handle any backpropagation question on the exam.

The professor worked through a detailed backpropagation numerical to demonstrate how returns flow back through the tree with discounting and incremental updates.

15.8.1 Problem Setup

An intermediate tree structure is given with three states along a path: state $S$ , state $T$ , and state $Y$ . At node $Y$ , a simulation (rollout) has been performed for exactly three time steps:

Step 1: from $Y$ to the next state
Step 2: to another state
Step 3: to a terminal state with reward 31.25

The discount factor is $γ = 0.8$ .

Before this rollout, the existing values are:

$Q (S, A) = 18$ (where $A$ is the action from $S$ leading to $T$ )
$Q (T, F) = 0$ (where $F$ is the action from $T$ leading to $Y$ )

The path through the tree is: $S A T F Y rollout terminal$ .

15.8.2 Step 1: Compute the Return from Y

The return from the simulation starting at $Y$ is computed backward from the terminal reward. Since the rollout has three steps and the only explicitly given reward is 31.25 at the terminal state (step 3), the return at $Y$ discounts the terminal reward by $γ^{2}$ (two steps of discounting from $Y$ ):

$G_{Y} = γ^{2} \times 31.25 = 0. 8^{2} \times 31.25 = 0.64 \times 31.25 = 20$

So the return observed at node $Y$ is $G_{Y} = 20$ .

The professor's verbal description: "gamma square into 31.25 — this is immediate reward less gamma, gamma square, right? So it is gamma square into 31.25."

15.8.3 Step 2: Backpropagate to T

The return $G_{Y} = 20$ is now backpropagated to update $Q (T, F)$ . The update uses the incremental formula with learning rate $α = \frac{1}{N ( T , F )}$ .

Before backpropagation: $Q (T, F) = 0$ and $N (T, F) = 1$ (visited once previously). After incrementing: $N (T, F) = 2$ , so $α = \frac{1}{2}$ .

The immediate reward at $T$ for taking action $F$ is $r_{T} = 0$ (not explicitly given, implied to be zero). The target is the discounted return from the child: $r_{T} + γ \cdot G_{Y} = 0 + 0.8 \times 20 = 16$ .

The backpropagation update at T. Applying the incremental formula:

$Q (T, F) \leftarrow Q (T, F) + \frac{1}{N ( T , F )} [r_{T} + γ \cdot G_{Y} - Q (T, F)] = 0 + \frac{1}{2} [0 + 0.8 \times 20 - 0] = \frac{1}{2} \times 16 = 8$

The error term is $16 - 0 = 16$ , and half of that (learning rate $1/2$ ) gives the update of 8. After this step: $Q (T, F) = 8$ , $N (T, F) = 2$ .

The professor's verbal description: "the immediate reward that you are getting here is 0, so 0 plus 0.8 is the probability information into 20 is the reward that you have just back propagated minus the already existing value."

15.8.4 Step 3: Backpropagate to S

Now we backpropagate from $T$ to $S$ to update $Q (S, A)$ .

Visit counts: Before this update, $N (S) = 9$ total visits to state $S$ , and $N (S, A) = 4$ (three existing visits to this action plus the current backpropagation makes 5). So after incrementing: $N (S, A) = 5$ , giving $α = \frac{1}{5}$ .

Immediate reward: $r_{S} = 6$ (the reward for taking action $A$ from state $S$ ).

The backpropagated value from T: The value to propagate is the discounted return that represents the full outcome of the subtree rooted at $T$ . Using the standard backpropagation approach, this is computed as:

$G_{T} = r_{T} + γ \cdot G_{Y} = 0 + 0.8 \times 20 = 16$

This $G_{T} = 16$ is the total discounted return observed from $T$ onward, accounting for the immediate reward at $T$ and the discounted future return.

The backpropagation update at S. Applying the incremental formula with $G_{T} = 16$ :

$Q (S, A) \leftarrow Q (S, A) + \frac{1}{N ( S , A )} [r_{S} + γ \cdot G_{T} - Q (S, A)] = 18 + \frac{1}{5} [6 + 0.8 \times 16 - 18] = 18 + \frac{1}{5} [6 + 12.8 - 18] = 18 + \frac{1}{5} \times 0.8 = 18 + 0.16 = 18.16$

Wait — let us re-examine. The professor's verbal description says "the immediate reward that you are getting is 6... less discount, a discounted return which is... discounted return that whatsoever has come back from Q of T comma F." This suggests the target uses the raw return backpropagated from $Y$ (which is $G_{Y} = 20$ ), discounted by $γ$ once for the $S \to T$ transition:

$Q (S, A) \leftarrow Q (S, A) + \frac{1}{N ( S , A )} [r_{S} + γ \cdot G_{Y} - Q (S, A)] = 18 + \frac{1}{5} [6 + 0.8 \times 20 - 18] = 18 + \frac{1}{5} [6 + 16 - 18] = 18 + \frac{1}{5} \times 4 = 18 + 0.8 = 18.8$

The professor arrives at $Q (S, A) = 18.6$ in the lecture. A direct computation using the backpropagated return $G_{Y} = 20$ discounted by $γ = 0.8$ yields 18.8. The discrepancy (18.6 vs 18.8) appears to be a minor computational error in the lecture. The correct answer is 18.8.

Interpretation: After backpropagation, $Q (S, A)$ increased from 18 to 18.8. This means the backpropagated return (22, from $r_{S} + γ \cdot G_{Y}$ ) was higher than the current estimate of 18, pulling the average upward. This is evidence that action $A$ from state $S$ is promising — the returns via this path are better than the existing estimate suggested.

Pitfall — miscounting the discount levels. A common mistake is to apply $γ$ once per node in the path, then apply it again when computing the target at the parent. In the formula $r_{S} + γ \cdot G_{Y}$ , the discount $γ$ already accounts for the $S \to T$ transition. Do not apply an additional discount. The return $G_{Y} = 20$ already includes all discounting from $Y$ to the terminal state.

Verification by running average. We can verify $Q (S, A) = 18.8$ by computing the running average directly. Before this update, $Q (S, A) = 18$ with $N = 4$ , meaning the total accumulated return was $W (S, A) = 4 \times 18 = 72$ . Adding the new target of $r_{S} + γ \cdot G_{Y} = 22$ :

$Q (S, A) = \frac{W + 22}{N + 1} = \frac{72 + 22}{5} = \frac{94}{5} = 18.8$

This confirms the incremental update result. Sense check: The new return (22) is above the old average (18), so the updated average (18.8) moves upward — exactly as expected.

Student Q:

Q: Why is the learning rate $\frac{1}{N ( s , a )}$ ?

15.8.5 Interpretation

The key insight: after backpropagation, the value of $Q (S, A)$ increased from 18 to 18.8. This means action $A$ from state $S$ is yielding better returns than the previous estimate suggested. As more iterations are performed, the estimates converge, and the action with the consistently highest value estimate becomes the preferred choice. The same computation would be repeated for action $B$ (leading to a different subtree), and whichever action has the higher final $Q$ value is selected.

15.8.6 Exam Notes

Exam note: This is a key numerical for the exam. Be prepared to: (a) compute the discounted return from a rollout given rewards and $γ$ , (b) apply the incremental update formula with learning rate $\frac{1}{N}$ , (c) backpropagate through multiple levels of the tree with proper discounting at each level, and (d) interpret what the updated values mean for action selection. The professor emphasized these numericals are likely exam material.

15.9 MCTS versus Value Iteration

Hook: You need to navigate a city you have never visited. Should you buy a complete map of every street in the city (value iteration), or just use GPS directions for your current trip (MCTS)? The answer depends on whether you need to navigate from every location or just from where you are now.

A natural comparison arises between MCTS and classical dynamic programming methods like value iteration. Both aim to find good policies, but they differ fundamentally in their approach.

Comparison

Dimension	MCTS	Value Iteration
Planning scope	One state at a time — plans from the current state only	All states simultaneously — computes the full value function $V^{*}$
Computational cost	Lower per decision (only a subtree is explored)	Higher (every state must be updated in each sweep)
When to use	Online planning during real-time interaction	Offline planning or when the state space is small enough to enumerate
Output	A single recommended action for the current state	A complete optimal value function and policy for every state
Tree lifetime	Discarded after each decision; starts fresh at each new state	Value function persists and can be queried from any state
Model requirement	Needs a model (or learned model) to simulate rollouts	Needs the full transition model $P (s^{'} ∣ s, a)$
Scalability	Controlled by iteration count; scales to large state spaces	Requires a sweep over all states; limited by state space size

The fundamental trade-off: MCTS is focused — it allocates computation only to the part of the state space relevant to the current decision. Value iteration is comprehensive — it solves for the entire state space at once. MCTS is preferred for online planning in large environments; value iteration is preferred when you need a reusable policy for all states.

The professor's analogy: if you are a game coach who wants to analyze strategies from any board position, value iteration is better because it gives you a complete value function. But if you are a player who needs to make a decision right now from the current position, MCTS is more efficient because it only computes what you need for this one decision.

Student Q:

Q: How is MCTS beneficial compared to value iteration?

A: MCTS is lower cost because it plans from only one state at a time, not the entire state space. However, value iteration is more robust — it gives you a complete value function that can be queried from any state. For online planning during real-time interaction, MCTS is preferred. For offline analysis or when you need strategies from multiple starting positions, value iteration is better.

Pitfall — assuming MCTS always dominates value iteration. MCTS is not strictly better. If the state space is small (like a $4 \times 4$ gridworld), value iteration converges quickly and gives you the optimal policy for all states. MCTS would re-plan from scratch at every state, wasting computation. The advantage of MCTS appears only when the state space is too large for value iteration to sweep through.

Recap: MCTS trades completeness for focus — one state at a time, lower cost, ideal for online planning. Value iteration trades focus for completeness — all states at once, higher cost, reusable policy. Bridge: the next sections apply MCTS to the game of Go, where the state space is so large that value iteration is infeasible and MCTS is the only practical planning approach.

15.9.1 Exam Notes

Exam note: Know the trade-off between MCTS (lower cost, one state, online) and value iteration (higher cost, all states, more robust). This is a common comparison question. Be able to state at least three concrete differences in a side-by-side format.

15.10 The Game of Go

Hook: Go has been played for over 2,000 years, and for most of that time, the best computer programs could not beat even an amateur human player. The reason is not that Go has complex rules — in fact, the rules are simpler than chess. The reason is that the game tree is astronomically large, and no one has ever found a good evaluation function for board positions. This is exactly the kind of problem MCTS was designed to solve.

Before discussing AlphaGo and AlphaZero, the professor introduced the game of Go, which is the domain these systems were designed to master.

Rules and Mechanics

Go is an ancient two-player board game, approximately 2000 years old. It is played on a grid board where players place stones on the intersections of grid lines (not in the cells, as in tic-tac-toe). There are two players: black and white.

The rules are simple:

Players alternate placing stones on empty intersections.
If a player's stones completely surround an opponent's stone (occupying all four horizontally or vertically adjacent intersections), the surrounded stone is captured and removed from the board.
The goal is to control more territory (empty intersections surrounded by your stones) than the opponent by the end of the game.
The game ends when neither player wishes to place another stone.

Why Go Is Hard for AI

The key challenge for AI is the enormous branching factor and state space:

Property	Go ( $19 \times 19$ )	Chess
Legal moves per turn	$\approx 250$	$\approx 35$
Typical game length	$\approx 150$ moves	$\approx 80$ moves
Total possible games	$\approx 1 0^{360}$	$\approx 1 0^{120}$
Board positions	$\approx 1 0^{170}$	$\approx 1 0^{47}$

Generating an exhaustive search tree for every possible game state is computationally infeasible. This is precisely why MCTS-based approaches are needed: instead of exhaustive search, the algorithm uses intelligent tree search to focus on the most promising moves.

Additionally, Go has a property that makes classical heuristic search especially difficult: it is extremely hard to define a good evaluation function for a Go board position. In chess, material counting (queen = 9, rook = 5, etc.) provides a reasonable positional evaluation. In Go, the value of a position depends on subtle spatial relationships, influence, and potential territory that resist simple heuristics. As one researcher put it: "No simple yet reasonable evaluation function will ever be found for Go." This is why MCTS, which does not require an explicit evaluation function but instead uses rollouts to estimate values, became the dominant approach for Go programs.

Pitfall — underestimating Go's difficulty. The rules of Go can be learned in five minutes, but the game is vastly more complex than chess in terms of the search space. Do not confuse rule simplicity with strategic simplicity.

Recap: Go was chosen as the test domain for AlphaGo and AlphaZero because its enormous state space and branching factor make exhaustive search impossible, and no simple evaluation function exists. MCTS provides a way to navigate this complexity through intelligent, focused tree search. Bridge: the next section describes how DeepMind combined MCTS with deep neural networks to build AlphaGo.

15.10.1 Exam Notes

Exam note: Go was chosen as the test domain for AlphaGo/AlphaZero because its enormous state space and branching factor make exhaustive search impossible, requiring RL-based planning approaches. Know that the branching factor of Go is roughly 250 (vs 35 for chess) and that defining a positional evaluation function for Go is exceptionally hard.

15.11 AlphaGo: Architecture and Training

Hook: In March 2016, a computer program defeated an 18-time world champion at Go, a game that AI researchers predicted would take decades more to crack. AlphaGo combined three ideas that had never been used together before: deep neural networks, reinforcement learning, and Monte Carlo Tree Search. Understanding how these pieces fit together is the key to understanding modern game-playing AI.

AlphaGo is a deep reinforcement learning system created by DeepMind to defeat expert Go players. It combines supervised learning, reinforcement learning, and MCTS into a single system. Multiple versions were created: AlphaGo Lee (which defeated the Go champion Lee Sedol, winning 4 out of 5 games in 2016), AlphaGo Fan (which defeated European champion Fan Hui 5–0), and AlphaGo Eva (which defeated the Go champion Eva), with each version tailored to beat a specific expert.

AlphaGo's core innovation: Instead of using MCTS with random rollouts (as in earlier Go programs), AlphaGo uses MCTS guided by deep neural networks — a policy network that suggests which moves to explore, and a value network that estimates how good a board position is. This combination allowed it to evaluate positions far more accurately than random rollouts alone.

15.11.1 Stage 1: Supervised Learning Policy Network ( $π_{S L}$ )

The training begins with collecting a dataset of expert games. The games of the target expert (say, Lee Sedol) are recorded as sequences of (state, action) pairs. This dataset is a collection of the expert's experiences — every move the expert made in every recorded game.

This dataset is used to train a neural network, called the supervised learning policy network ( $π_{S L}$ ). The network is a 13-layer deep convolutional ANN. It is trained to predict: given a board position (state), what action did the expert take? This is a standard supervised classification problem. The input is a $19 \times 19 \times 48$ image stack representing the board state (48 binary or integer-valued features per intersection, encoding stone positions, liberties, capture counts, and other Go-specific features). The output is a probability distribution over all 361 possible stone placements (the $19 \times 19$ board plus pass), trained using stochastic gradient ascent to match the expert's actual move distribution.

The result is a policy $π_{S L}$ that imitates the expert. It achieved 57% accuracy in predicting human expert moves — significantly higher than the previous state-of-the-art of 44.4%. However, this policy is limited: it can only play as well as the expert it was trained on, and it has never encountered positions the expert never faced.

15.11.2 Stage 2: Reinforcement Learning Policy Network ( $π_{R L}$ )

To surpass the expert, the supervised policy must be improved. This is done through a reinforcement learning policy network ( $π_{R L}$ ), which has the same 13-layer architecture as $π_{S L}$ but is trained differently.

The professor's key insight: Instead of starting policy gradient training from a random policy (as is typical), AlphaGo starts from the supervised policy $π_{S L}$ . This gives the RL network a significant head start — it begins with expert-level play and improves from there. The professor's analogy: "imagine learning to drive by observing your friend. Your initial driving style is biased by your friend's moves. To become better than your friend, you need to practice on your own."

The improvement happens through self-play: the RL policy network plays the game against opponents using randomly selected earlier versions of itself (this prevents overfitting to the current policy). Policy gradient methods are used to adjust the move probabilities toward actions that lead to winning. The reward signal is $+ 1$ for a win, $- 1$ for a loss, and $0$ otherwise. After training on approximately one million self-play games, the RL policy won more than 80% of games against the SL policy and 85% against a traditional MCTS program.

15.11.3 Stage 3: Value Network

In parallel with the policy network, AlphaGo uses a value network to evaluate board positions. The value network has the same convolutional architecture as the policy networks but with a single output unit that produces a scalar estimate: how likely is the current player to win from this position?

The value network is trained using Monte Carlo policy evaluation on data from self-play games played by the RL policy network. To avoid overfitting to positions within single games, the training data consists of 30 million positions, each drawn from a different self-play game. Training took approximately one week on 50 GPUs.

The value network plays a crucial role during MCTS search. Instead of running every rollout to completion (which is expensive), the value network can estimate the value of a non-terminal state, allowing the search to terminate early and use the estimated value instead of continuing the simulation.

15.11.4 The Complete AlphaGo Pipeline

How the three networks work together within MCTS (called APV-MCTS — Asynchronous Policy and Value MCTS):

At each state, MCTS begins planning. The root is the current board position.
During expansion, the SL policy network $π_{S L}$ guides which edge to expand. The network provides probabilities for each possible move, and the expansion selects according to these probabilities rather than uniformly.
During evaluation, the newly added node is evaluated in two ways:

By the value network $v_{θ} (s)$ , which estimates the probability of winning from state $s$ ,
By a rollout using a fast rollout policy (a simple linear network trained by supervised learning), which plays to the end of the game.
The final evaluation combines both: $v (s) = (1 - η) v_{θ} (s) + η G$ , where $G$ is the rollout return and $η$ controls the mixing. In AlphaGo, $η = 0.5$ gave the best results.

During backpropagation, the combined evaluation is propagated back through the tree.
After all MCTS iterations, the most-visited edge from the root is selected as the move to play.

Why mix value network and rollouts? The DeepMind team found that the value network alone played better than any existing Go program, and the rollout alone also played well. But combining them ( $η = 0.5$ ) was even better. The reason is that they complement each other: the value network evaluates the high-performance RL policy (which is too slow for rollouts), while the fast rollout policy adds precision for specific states that occur during the game.

Why use $π_{S L}$ instead of the stronger $π_{R L}$ for expansion? Surprisingly, AlphaGo played better against humans when using the SL policy for MCTS expansion rather than the stronger RL policy. The conjecture is that the RL policy was optimized to play against optimal opponents, while the SL policy was tuned to predict human moves — which is more useful when the tree needs to explore the kinds of positions that actually arise in human games.

15.11.5 Limitations of AlphaGo

The major limitation of AlphaGo is its bias toward expert moves. Because the training starts with supervised learning on a specific expert's games, the resulting policy is heavily influenced by that expert's style. The system may miss strategies that the expert never used but that could be stronger. This bias is inherent in the supervised learning starting point — you can only improve so much from imitating one expert.

Additionally, AlphaGo requires significant domain-specific engineering: 48 hand-crafted input features, separate networks for different roles, and a fast rollout policy designed specifically for Go.

15.11.6 Exam Notes

Exam note: Know the three networks of AlphaGo (supervised policy $π_{S L}$ , RL policy $π_{R L}$ , value network $v_{θ}$ ) and their roles. Understand why starting from a supervised policy gives an advantage over starting from random. The self-play mechanism using MCTS is central to how the policy is improved beyond the expert's level. Know the evaluation formula $v (s) = (1 - η) v_{θ} (s) + η G$ and why both value network and rollouts are used.

15.12 AlphaZero: Key Improvements Over AlphaGo

Hook: AlphaGo learned from the best human players and then improved. AlphaZero learned from nothing — no human games, no hand-crafted features, just the rules of the game — and still surpassed AlphaGo. This is the moment where AI stopped imitating human knowledge and started discovering its own.

AlphaZero addresses the limitations of AlphaGo with two major architectural changes that make it both simpler and more powerful.

15.12.1 Eliminating Supervised Learning

The first and most important change: AlphaZero completely removes the supervised learning component. There is no expert dataset, no supervised policy network, and no bias toward any particular expert's style. Instead, training starts from random play — the initial policy $π_{random}$ assigns equal probability to all legal moves.

The philosophical shift: AlphaGo learns from human experts and then improves — it can never fully escape the biases of its training data. AlphaZero learns from nothing and discovers its own strategies through pure self-play. This removes the ceiling imposed by human knowledge.

The system learns entirely through self-play. MCTS plays against itself from scratch, discovering strategies on its own without any human knowledge of how to play Go (beyond the rules). This is the significance of the "Zero" in the name — zero human knowledge beyond the rules.

The professor's warning: AlphaGo was biased toward expert moves because it started from supervised learning. This bias was both an advantage (faster initial learning) and a limitation (could not discover strategies the expert never used). AlphaZero removes this bias entirely by starting from random play. The consequence: AlphaZero discovered novel move sequences and strategies that human players had never considered in 2,000 years of Go.

15.12.2 Single Network with Two Heads

The second major change: the three separate networks of AlphaGo (supervised policy network, RL policy network, value network) are replaced by a single neural network with two output heads:

The dual-headed architecture:

Policy head: Outputs a probability distribution over actions given the current state. This is a softmax output — the probabilities sum to 1 over all legal moves. Training uses policy gradient (PG) algorithms on the fully connected layer.

Value head: Outputs a scalar estimate of how likely the current player is to win from the given state. Since Go is a zero-sum game, the value ranges from $- 1$ (certain loss) to $+ 1$ (certain win). A tanh activation function is used to squash the output to this range. Training uses semi-gradient TD learning on the fully connected layer.

Why tanh for the value head? Go is a zero-sum game: one player's gain is the other's loss. If the current player has a 70% chance of winning, the opponent has a 30% chance. The tanh function naturally encodes this symmetry: $tanh (x) \in [- 1, + 1]$ , where $+ 1$ means certain win and $- 1$ means certain loss. A value of 0 means an even position. The softmax in the policy head ensures the output is a valid probability distribution.

15.12.3 Network Architecture Details

The input to the AlphaZero network is the current board position, represented as an $8 \times 8$ spatial grid with 17 channels (note: the professor uses $8 \times 8$ which is standard for chess/shogi; Go uses $19 \times 19$ ):

8 channels encode the positions of the current player's stones over the last 8 moves,
8 channels encode the positions of the opponent's stones over the last 8 moves,
1 channel indicates which player is currently playing.

So the input dimensions are $8 \times 8$ spatial with 17 feature planes, giving an input tensor of shape $8 \times 8 \times 17$ .

This input is processed through a deep convolutional neural network (CNN) with residual blocks. The CNN automatically learns spatial features from the board position — detecting patterns like stone formations, territory control, and tactical shapes. The residual blocks allow the network to train deeper without degradation. (In the original AlphaGo Zero paper, the network had 41 residual blocks.)

The output of the CNN is fed into two separate heads:

The policy head: applies a $1 \times 1$ convolution, batch normalization, flattening, and a softmax function to produce action probabilities.
The value head: applies a similar convolution and batch normalization, followed by a fully connected layer with tanh activation to produce the state value in $[- 1, + 1]$ .

How AlphaZero uses MCTS: Unlike AlphaGo, AlphaZero uses MCTS during self-play training (not just during live play). Each move is selected by running MCTS guided by the network's policy output $p$ and value output $v$ . The MCTS-improved policy $π$ (from visit counts) is better than the raw network policy $p$ . The network is then trained to match $π$ (for the policy head) and the game outcome $z$ (for the value head). This creates a virtuous cycle: better network → better MCTS → better training data → better network.

15.12.4 AlphaGo vs AlphaZero: Summary of Changes

Aspect	AlphaGo	AlphaZero
Number of networks	3 (SL policy, RL policy, value)	1 (shared CNN with 2 heads)
Supervised learning	Yes (expert games dataset)	No (starts from random play)
Training data source	Expert games + self-play	Self-play only
Bias	Biased toward expert moves	No expert bias — discovers own strategies
Generality	Specific to one expert per version	General — can beat any expert
MCTS during training	No (MCTS only during live play)	Yes (MCTS during self-play training)
Input features	48 hand-crafted Go features	Raw board position (17 planes)

Recap: AlphaZero makes two key improvements over AlphaGo: (1) eliminating supervised learning removes expert bias and enables the discovery of novel strategies, and (2) replacing three networks with a single dual-headed network simplifies the architecture and enables end-to-end training. The result is a system that is both more general and more powerful. Bridge: the natural next question is whether we can also remove the need to know the rules of the game — this leads to MuZero.

15.12.5 Exam Notes

Exam note: The two key changes from AlphaGo to AlphaZero are: (1) removing supervised learning to eliminate expert bias, and (2) replacing three networks with a single dual-headed network. Know the activation functions: softmax for policy head, tanh for value head. Understand why tanh is used (zero-sum game, values between $- 1$ and $+ 1$ ). Know that AlphaZero uses MCTS during training, unlike AlphaGo.

15.13 From AlphaZero to MuZero

Hook: AlphaZero no longer needed human experts. But it still needed to know the rules of the game — the MCTS simulator had to be programmed with the legal moves and transition mechanics. MuZero removes even this last requirement: it learns the rules from scratch, making it applicable to any game without domain-specific programming.

The natural progression from AlphaGo to AlphaZero to MuZero represents increasing generality — each step removes a constraint:

System	Expert knowledge	Rules knowledge	Applicability
AlphaGo Lee/Eva	Yes (expert games dataset)	Yes (game rules programmed)	One specific expert of Go
AlphaZero	No (starts from random play)	Yes (game rules programmed)	Any expert of Go, chess, or shogi
MuZero	No	No (learns rules from experience)	Any game — Go, chess, shogi, Atari, and more

MuZero's key innovation: Instead of using the true game dynamics in MCTS (which requires knowing the rules), MuZero learns a latent model of the environment. This model operates in a learned abstract state space (not the raw game state) and predicts: (1) the next latent state, (2) the immediate reward, and (3) the policy and value. The MCTS planner uses this learned model to simulate futures, entirely replacing the need for a programmed game simulator.

AlphaGo Lee/Eva: Can defeat a specific expert of Go. Uses supervised learning from that expert's games. Three separate networks. Biased toward that expert's style.

AlphaZero: Can defeat any expert of Go (and also chess and shogi). No supervised learning — learns entirely through self-play. Single dual-headed network. But still requires knowledge of the rules of Go — the game mechanics must be programmed into the MCTS simulator. The input features are raw board positions, but the MCTS simulator needs to know legal moves and how the board changes after each move.

MuZero: Can become an expert at any game — Go, chess, shogi, Atari games, and potentially other domains — without even being told the rules of the game. MuZero uses a latent model to learn the game dynamics entirely from experience, including the rules themselves. The model operates in a learned abstract space, not in the raw game state space, and MCTS is performed entirely within this learned model.

MuZero represents the ultimate generalization: a single algorithm that can master any game by learning its rules, dynamics, and optimal strategy from scratch. The professor briefly introduced MuZero as the latest development in this line of research but deferred detailed coverage to a subsequent session.

Pitfall — thinking MuZero does not use MCTS. MuZero still uses MCTS for planning — it just runs MCTS inside a learned model rather than in the true game environment. The planning mechanism is the same; what changes is where the planning happens (learned latent space vs. true state space).

Recap: The progression AlphaGo → AlphaZero → MuZero removes one constraint at a time: first the need for expert data, then the need for known rules. Each generalization makes the system applicable to a broader class of problems. Bridge: this lecture has covered the full arc from model-based vs model-free RL, through MCTS as a planning algorithm, to the game-playing AI systems that combine MCTS with deep learning. The exam guidance summary that follows consolidates all the key points.

15.13.1 Exam Notes

Exam note: Know the progression AlphaGo → AlphaZero → MuZero and what each generalization achieved. MuZero's key innovation is learning the rules of the game using a latent model, making it applicable to any game without domain-specific programming. Be able to state what each system requires as input (expert data? rules?).

Exam Guidance Summary

The following is a consolidated list of exam-relevant points from this lecture, organized by concept:

Model-based vs model-free RL (15.1): Know that dynamic programming is model-based (model given as oracle), Monte Carlo and TD are model-free (no model), and the modern model-based approach learns the model from experience via supervised learning.

MCTS phases (15.2): The four phases in order — selection, expansion, simulation, backpropagation — are essential. Know each phase's role and be able to explain them. MCTS is a planning algorithm, not a policy optimization method. The backbone is the rollout algorithm.

UCB action selection (15.3): Know the formula $UCB (s, a) = Q (s, a) + c \frac{l n N ( s )}{N ( s , a )}$ and understand the exploitation-exploration trade-off. Newly created states have UCB = infinity because $N (s, a) = 0$ . This guarantees every action is tried at least once.

Rollout and discounted returns (15.4): A rollout is a complete random simulation from a state to a terminal state. The return is $G = \sum_{t = 1}^{T} γ^{t - 1} r_{t}$ . Be able to compute discounted returns for any sequence of rewards.

Transition probabilities (15.5): Learned from visit counts: $P^(s^{'} ∣ s, a) = \frac{N ( s , a , s ^{'} )}{N ( s , a )}$ . Not given a priori — estimated from MCTS experience.

Backpropagation numerical (15.6, 15.8): Be able to compute discounted returns, apply the incremental update formula $Q \leftarrow Q + \frac{1}{N} [target - Q]$ , backpropagate through multiple levels of the tree with proper discounting, and interpret what the updated values mean. The professor emphasized these are likely exam material.

MCTS vs Value Iteration (15.9): Know the trade-offs — MCTS is lower cost, one state, online planning; value iteration is higher cost, all states, more robust. MCTS is preferred for large state spaces; value iteration for small ones where a complete policy is needed.

AlphaGo architecture (15.11): Three networks — SL policy network (trained on expert games), RL policy network (improved via self-play with policy gradients), value network (MC policy evaluation). The APV-MCTS evaluation mixes value network and rollout: $v (s) = (1 - η) v_{θ} (s) + η G$ . Self-play mechanism is central.

AlphaZero improvements (15.12): Two key changes from AlphaGo: (1) no supervised learning — starts from random play, eliminating expert bias; (2) single network with policy head (softmax) and value head (tanh). MCTS used during training, not just play. Know why tanh is used (zero-sum game, values between $- 1$ and $+ 1$ ).

MuZero (15.13): Generalizes to any game without knowing the rules, using a latent model. Know the progression: AlphaGo (expert data + rules) → AlphaZero (no expert data, rules required) → MuZero (no expert data, no rules).

Numerical examples: Work through all numerical examples carefully — the professor emphasized these are likely exam material. Practice the backpropagation arithmetic with different discount factors and visit counts.

Key Industry Applications

The concepts from this lecture have been applied in several significant real-world systems:

AlphaGo (DeepMind, 2016): Deep RL system that defeated Go champion Lee Sedol (4–1) and European champion Fan Hui (5–0). Used MCTS combined with supervised learning from expert games and reinforcement learning via self-play. The first victories of a Go program over a professional human player without handicap.

AlphaGo Zero (DeepMind, 2017): Refined version that learned entirely from self-play without any human data or guidance beyond the rules of Go. Defeated the version of AlphaGo that beat Lee Sedol by 100 games to 0 after just 72 hours of training.

AlphaZero (DeepMind, 2017): Generalized version that learns entirely through self-play without expert data. Demonstrated superhuman performance in Go, chess, and shogi using the same algorithm and hyperparameters for all three games.

MuZero (DeepMind, 2019): State-of-the-art system that learns game rules and dynamics from scratch using a latent model, applicable to any game without domain-specific programming. Also achieved state-of-the-art performance in Atari games without knowing the game rules.

MCTS in game AI: Monte Carlo Tree Search is widely used in game AI beyond Go — it is a standard planning algorithm in computational intelligence for games with large branching factors. Applications include general game playing systems, real-time strategy games, and card games.

Self-play training: The self-play paradigm pioneered by AlphaGo/AlphaZero has influenced modern RL research, including systems for multi-agent environments, complex strategy games, and robotics simulation. Self-play generates an automatic curriculum of increasingly challenging training scenarios.

World models: The concept of learning an internal model of the environment from experience has applications in robotics (warehouse robots navigating stochastic environments), autonomous driving (predicting other vehicles' behavior), and simulation-based planning (testing scenarios before real-world deployment).

DRL Lecture 15 notes · Model-Based Learning and Monte Carlo Tree Search

Deep Reinforcement Learning· postgraduate· 2026-08-16

Sections Breakdown

1Model-Based versus Model-Free Reinforcement Learning

Distinction between model-based (environment dynamics known or learned) and model-free (learn from experience) RL

2Monte Carlo Tree Search (MCTS)

Decision-time planning algorithm with four phases: selection, expansion, simulation, backpropagation

3Upper Confidence Bound (UCB) Action Selection in MCTS

UCB formula balancing exploitation and exploration, infinity guarantee for unvisited actions

4The Rollout Algorithm as MCTS Backbone

Rollout as complete random simulation, discounted return calculation

5Learning Transition Probabilities from Experience

Frequentist estimation of P(s'|s,a) from visit counts during MCTS

6Backpropagation in MCTS

Incremental Q-value update formula and state tracking information

7MCTS Worked Numerical Example

Three iterations of MCTS showing UCB selection, tree expansion, and backpropagation

8Backpropagation Worked Example with Discounted Returns

Detailed backpropagation through S→T→Y path with gamma=0.8

9MCTS versus Value Iteration

Trade-off between focused online planning (MCTS) and comprehensive offline planning (value iteration)

10The Game of Go

Why Go's enormous state space and branching factor make it ideal for MCTS-based AI

11AlphaGo: Architecture and Training

Three networks (SL policy, RL policy, value) and APV-MCTS pipeline

12AlphaZero: Key Improvements Over AlphaGo

Removing supervised learning, single dual-headed network with softmax and tanh

13From AlphaZero to MuZero

Progressive generalization removing constraints: expert data, then rules knowledge

Postgraduate students in Deep Reinforcement Learning

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Model-Based vs Model-Free RL

Must-know: Model-based vs model-free distinction: DP is model-based (oracle model), MC and TD are model-free, modern approach learns model from experience.

$M = ⟨ P (s^{'} ∣ s, a), R (s, a)⟩$

⚠️ Top pitfall: Confusing the model (environment dynamics) with a policy (action recipe).

Self-check: Is Q-learning model-based or model-free? Why?

Connects to: MCTS, Learning Transition Probabilities

Monte Carlo Tree Search (MCTS)

Must-know: MCTS is a decision-time planning algorithm with four phases in order: selection, expansion, simulation, backpropagation. It builds the tree incrementally, not exhaustively.

⚠️ Top pitfall: Confusing Monte Carlo (model-free value estimation) with MCTS (model-based planning that uses MC-style returns in its simulation phase).

Self-check: Name the four phases of MCTS in order.

Connects to: UCB Action Selection, Rollout Algorithm, Backpropagation in MCTS

Upper Confidence Bound (UCB) Action Selection

Must-know: UCB formula with exploitation and exploration terms. Newly created states have UCB = infinity because N(s,a) = 0 makes the exploration term infinite.

$UCB (s, a) = Q (s, a) + c \frac{ln N ( s )}{N ( s , a )}$

⚠️ Top pitfall: Assuming UCB selects the action with higher Q when both are unvisited — both are infinity, so the choice is random.

Self-check: Why does UCB = infinity for unvisited actions? Is this a bug or a feature?

Connects to: MCTS, MCTS Worked Numerical Example

The Rollout Algorithm

Must-know: Rollout return formula G = sum gamma^(t-1) * r_t. Be able to compute discounted return for any sequence of rewards.

$G = t = 1 \sum T γ^{t - 1} r_{t}$

⚠️ Top pitfall: Confusing gamma (discount factor, controls future reward weighting) with a probability.

Self-check: Compute the discounted return for rewards [10, 5, 2] with gamma = 0.5.

Connects to: MCTS, Backpropagation Worked Example

Learning Transition Probabilities

Must-know: Transition probability formula P(s'|s,a) = count(s,a,s') / count(s,a). Frequentist estimation from visit counts.

$P^(s^{'} ∣ s, a) = \frac{N ( s , a , s ^{'} )}{N ( s , a )}$

⚠️ Top pitfall: Treating small-sample estimates as reliable. P = 1/1 = 1 does not mean deterministic — only one observation.

Self-check: In state s, action a was tried 10 times: 7 times to s1, 3 times to s2. What are the transition probabilities?

Connects to: Model-Based vs Model-Free RL, MCTS

Backpropagation in MCTS

Must-know: Incremental Q-value update formula with learning rate 1/N. Q(s,a) is the sample mean of all returns through (s,a).

$Q (s, a) \leftarrow Q (s, a) + \frac{1}{N ( s , a )} [target - Q (s, a)]$

⚠️ Top pitfall: Using N before incrementing for the learning rate — use N after incrementing.

Self-check: If Q = 10 after 4 visits and a new return of 18 arrives, what is the updated Q?

Connects to: UCB Action Selection, MCTS Worked Numerical Example, Backpropagation Worked Example

MCTS Worked Numerical Example

Must-know: Trace MCTS iterations: UCB=infinity for unvisited states forces exploration first, then exploitation based on Q values. Number of iterations = number of times initial state is visited.

⚠️ Top pitfall: Assuming expansion always happens at the root — MCTS expands at the leaf level along the UCB-selected path.

Self-check: After iteration 2, why does MCTS select A1 again even though A2 was also tried?

Connects to: UCB Action Selection, Backpropagation Worked Example

Backpropagation Worked Example

Must-know: Backpropagate discounted returns through tree levels. Apply incremental update Q <- Q + (1/N)(target - Q) at each node. Correctly discount the backpropagated return by gamma at each level.

$Q (S, A) \leftarrow 18 + \frac{1}{5} [6 + 0.8 \times 20 - 18] = 18.8$

⚠️ Top pitfall: Double-discounting: applying gamma at both the child and parent level. The backpropagated return already includes discounting from the child onward.

Self-check: If gamma = 0.9, Q(parent) = 10, N = 3, r_parent = 2, and backpropagated return = 15, what is the updated Q?

Connects to: Backpropagation in MCTS, MCTS Worked Numerical Example

MCTS vs Value Iteration

Must-know: MCTS vs value iteration: scope (one state vs all states), cost (lower vs higher), output (single action vs full value function), use case (online vs offline planning).

⚠️ Top pitfall: Assuming MCTS is always better than value iteration — MCTS wastes computation on small state spaces where value iteration converges quickly.

Self-check: Name three ways MCTS differs from value iteration.

Connects to: MCTS, The Game of Go

The Game of Go

Must-know: Go's branching factor (~250), enormous state space (~10^170 positions), and difficulty of evaluation functions make exhaustive search infeasible and require MCTS.

⚠️ Top pitfall: Confusing rule simplicity (Go rules are simple) with strategic simplicity (Go is vastly more complex than chess in search space).

Self-check: Why can't classical min-max search work for Go?

Connects to: MCTS, AlphaGo Architecture

AlphaGo: Architecture and Training

Must-know: Three networks: SL policy (57% move prediction), RL policy (80% win rate vs SL), value network (MC policy evaluation on self-play data). APV-MCTS mixes value network and rollout evaluation.

$v (s) = (1 - η) v_{θ} (s) + η G$

⚠️ Top pitfall: Confusing the three networks' roles. SL policy guides expansion, RL policy was used for self-play training, value network evaluates positions during search.

Self-check: Why does AlphaGo use the SL policy instead of the stronger RL policy for MCTS expansion?

Connects to: MCTS, AlphaZero Improvements

AlphaZero: Key Improvements

Must-know: Two changes: (1) no supervised learning — pure self-play from random, (2) single network with policy head (softmax) and value head (tanh). MCTS used during training, not just play.

⚠️ Top pitfall: Confusing AlphaGo (3 networks, SL + RL + value) with AlphaZero (1 network, 2 heads, no SL). Also confusing softmax (policy) with tanh (value).

Self-check: Why does AlphaZero use tanh for the value head instead of sigmoid?

Connects to: AlphaGo Architecture, MuZero

From AlphaZero to MuZero

Must-know: Progression: AlphaGo (expert data + rules) → AlphaZero (no expert data, rules required) → MuZero (no expert data, no rules — learns latent model).

⚠️ Top pitfall: Thinking MuZero does not use MCTS — it does, but inside a learned latent model rather than the true game environment.

Self-check: What does MuZero learn that AlphaZero does not?

Connects to: AlphaGo Architecture, AlphaZero Improvements

Previous LectureLecture 14 · Policy Gradient Methods

Next LectureLecture 01 · Software Development Lifecycle, Waterfall, and Agile

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

15.1 Model-Based versus Model-Free Reinforcement Learning

15.1.1 Learning Model Dynamics from Experience

15.1.2 Challenges of Model-Based RL

15.1.3 Exam Notes

15.2 Monte Carlo Tree Search (MCTS)

15.2.1 The Four Phases of MCTS

15.2.2 How MCTS is Positioned in the RL Loop

15.2.3 MCTS versus Min-Max: Key Differences

15.2.4 Exam Notes

15.3 Upper Confidence Bound (UCB) Action Selection in MCTS

15.3.1 The UCB Formula and Its Components

15.4 The Rollout Algorithm as MCTS Backbone

15.4.1 The Discounted Return Formula

15.4.2 Stochastic Environments and Multiple Outcomes

15.4.3 Exam Notes

15.5 Learning Transition Probabilities from Experience

15.5.1 Exam Notes

15.6 Backpropagation in MCTS

15.6.1 The Incremental Update Formula

15.6.2 State Tracking Information

15.7 MCTS Worked Numerical Example

15.7.1 Iteration 1: Initial Tree Construction

15.7.2 Iteration 2: Exploring the Unvisited Branch

15.7.3 Iteration 3: Expanding a Previously Visited Node

15.7.4 Exam Notes

15.8 Backpropagation Worked Example with Discounted Returns

15.8.1 Problem Setup

15.8.2 Step 1: Compute the Return from Y

15.8.3 Step 2: Backpropagate to T

15.8.4 Step 3: Backpropagate to S

15.8.5 Interpretation

15.8.6 Exam Notes

15.9 MCTS versus Value Iteration

15.9.1 Exam Notes

15.10 The Game of Go

15.10.1 Exam Notes

15.11 AlphaGo: Architecture and Training

15.11.1 Stage 1: Supervised Learning Policy Network (πSL​)

15.11.2 Stage 2: Reinforcement Learning Policy Network (πRL​)

15.11.3 Stage 3: Value Network

15.11.4 The Complete AlphaGo Pipeline

15.11.5 Limitations of AlphaGo

15.11.6 Exam Notes

15.12 AlphaZero: Key Improvements Over AlphaGo

15.12.1 Eliminating Supervised Learning

15.12.2 Single Network with Two Heads

15.12.3 Network Architecture Details

15.12.4 AlphaGo vs AlphaZero: Summary of Changes

15.12.5 Exam Notes

15.13 From AlphaZero to MuZero

15.13.1 Exam Notes

Exam Guidance Summary

Key Industry Applications

DRL Lecture 15 notes · Model-Based Learning and Monte Carlo Tree Search

Sections Breakdown

Exam Revision Notes

Model-Based vs Model-Free RL

Monte Carlo Tree Search (MCTS)

Upper Confidence Bound (UCB) Action Selection

The Rollout Algorithm

Learning Transition Probabilities

Backpropagation in MCTS

MCTS Worked Numerical Example

Backpropagation Worked Example

MCTS vs Value Iteration

The Game of Go

AlphaGo: Architecture and Training

AlphaZero: Key Improvements

From AlphaZero to MuZero

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

15.11.1 Stage 1: Supervised Learning Policy Network ( $π_{S L}$ )

15.11.2 Stage 2: Reinforcement Learning Policy Network ( $π_{R L}$ )