Module 4 | Search, Trees & MCTS for Agent Decisions | AI 202

Search space and search trees

9 min

When the next step has more than one option

In Module 3 the agent alternated between reasoning and acting. Often, at a given moment, several actions are possible. This module is about how an agent looks at those options, compares them and chooses one, without turning into an algorithms course.

Core question

When an agent has several possible actions, how does it search and compare different paths?

Key terms
Term	Plain meaning
Search space	Everything the agent could do from here, and what could follow
Candidate actions	The specific actions the agent is considering right now
State space	The different situations the agent could end up in
Branching	One state leading to several possible next actions

Simulated example

A simulated helpdesk agent must handle an employee question about a leave policy. Candidate actions: search the policy document, ask a clarifying question, draft an answer from memory, or route the case to HR. Each is a branch.

Info

Text version of the idea: from the current State, several Actions are possible. Each Action leads to one or more possible Results. Listing them is the first step of search.

Key takeaway: Search starts by listing candidate actions from the current State instead of grabbing the first idea.

9 min

The search tree: depth, breadth and horizon

A search tree draws the current State at the top, candidate Actions as branches, and possible Results below each branch. Looking further ahead means going deeper in the tree.

A small search tree

Current State: employee asks about leave policy
Action A: search the policy. Results: A1 finds a clear rule, A2 finds nothing relevant
Action B: ask a clarifying question. Results: B1 the employee answers, B2 no reply
Action C: draft an answer from memory. Result: C1 an unverified answer
Compare the branches, then choose the next Action

Info

Text version of the diagram: one starting State with three branches, A, B and C. Branches A and B each have two possible Results, and branch C has one. The tree has breadth 3 and depth 2.

Reading a tree
Idea	Meaning	Trade-off
Breadth	How many options are considered at each step	More options may find a better path but cost more effort
Depth	How many steps ahead the agent looks	Deeper looks see consequences but rest on more guesses
Planning horizon	The limit on how far ahead the agent plans	Too short misses consequences, too long wastes effort on uncertain futures

Check yourself

What does the depth of a search tree describe?

How many steps ahead the agent looks along a pathHow many candidate actions there are at one stepHow confident the agent feels about its answer

Key takeaway: Breadth is how many options, depth is how far ahead, and the horizon is the limit you choose.

Comparing and choosing branches

9 min

Heuristic, utility, cost and risk

An agent cannot try every branch. It needs a quick way to judge which branches look worthwhile. That quick rule of thumb is a heuristic. The judgment about how good an outcome would be is its utility or value.

Decision dimensions for comparing candidate paths
Dimension	Question to ask
Expected outcome	How close does this path get to the Goal?
Evidence quality	How well supported is the expectation?
Cost	How much effort, time or money does it use?
Latency	How long until the Result is available?
Reversibility	Can we undo it if it turns out wrong?
Risk	What is the worst plausible result, and who is affected?
Tool availability	Is the tool or source needed actually available?
Confidence	How sure are we, and is that confidence earned?

Warning

A path with the best expected outcome is not always the best choice. A cheaper, reversible action may be wiser when evidence is weak or risk is high.

Check yourself

Two candidate actions look equally promising. One can be undone easily, the other cannot. Which dimension favors the first?

Reversibility, because a wrong choice can be undoneLatency, because it is always fasterTool availability, because reversible actions need fewer tools

Key takeaway: Compare paths on several dimensions, not on expected outcome alone. Cost, risk and reversibility matter.

9 min

Exploration versus exploitation

Every search balances two urges. Exploitation means spending effort on the branch that currently looks best. Exploration means spending some effort on branches we know less about, in case a better option is hiding there.

Exploration and exploitation
Approach	Benefit	Risk if overused
Exploitation	Uses what we already believe works, so it is efficient	Locks onto a mediocre option and never learns about better ones
Exploration	Finds options we had not considered	Wastes effort on branches that lead nowhere

Simulated example

The helpdesk agent has answered leave questions by searching one policy folder. Exploitation keeps using that folder. Exploration tries one other source, such as the latest announcement page, once, to see if it is better.

Info

Text version of the idea: a good search mostly follows promising branches, but keeps a small share of effort for less-known ones. Safety limits still apply to exploration: never explore an unsafe or irreversible action just to learn from it.

Check yourself

What is the risk of exploitation only, with no exploration?

The agent may keep choosing a mediocre option and miss a better oneThe agent will run out of branches immediatelyThe agent will always choose unsafe actions

Key takeaway: Spend most effort on promising branches, keep a little for the unknown, and never explore unsafe actions.

9 min

MCTS as a planning concept

Monte Carlo Tree Search, or MCTS, is a well known way to search a large tree. In this course we use it only as a way of thinking about planning. No formulas and no derivations are needed.

The idea in one sentence

Sample possible future action sequences, estimate their outcomes, and give more search effort to the promising branches.

The MCTS idea as a loop

Explore: pick a branch and imagine a possible sequence of actions after it
Evaluate: estimate how that imagined sequence would end
Update: record what was learned about that branch
Explore again: send more effort to branches that look promising, and some to the uncertain ones

Info

Text version of the diagram: four steps repeat, Explore, Evaluate, Update, then Explore again. Over many rounds, promising branches receive more attention while weak branches receive less.

Warning

Imagined outcomes are estimates, not facts. An agent that plans by imagining futures still needs Verification and Human Escalation for high-impact choices.

Check yourself

Which description of MCTS fits this course?

Sample possible future action sequences, estimate outcomes, and focus more effort on promising branchesAlways try every possible action before choosingPick the first action and never reconsider

Key takeaway: MCTS is a way of thinking: imagine futures, estimate them, and focus effort where it pays off.

Practice and deliverable

8 min

Activity 4: Search the Next Step

Take a simulated situation, or the task you chose in Module 1, and search for the best next action.

List 3 to 5 candidate actions
Write actions the agent could take from the current State.
Build a small search tree
Add one or two possible Results under each action.
Eliminate unsafe or invalid branches
Remove any action that is unsafe, irreversible without approval, or impossible with the available tools.
Compare the rest
Use the decision dimensions: expected outcome, evidence quality, cost, latency, reversibility, risk, tool availability and confidence.
Choose and explain
Pick a next action and write a short reason.

Warning

Privacy reminder: use simulated or already-public situations. Do not enter company secrets, client personal data or unauthorized sensitive information.

Go to the AI 202 practice: In the "Search the Next Step" activity, build your search tree.

Check yourself

While searching, you find one branch that would send a message to a customer without any approval. What should you do?

Eliminate it or add a human approval step, because it is unsafe as writtenKeep it because it has the fastest resultKeep it and hope the agent decides well

Key takeaway: List candidate actions, build a small tree, remove unsafe branches, compare, then choose and explain.

7 min

MCTS mini exercise and the Candidate Action Map

Use a conceptual simulation on your tree. No numbers or formulas are needed, only your judgment.

Explore
Pick one branch and imagine what would happen next.
Evaluate
Judge how well that imagined path serves the Goal, and note the risk.
Update
Mark the branch as promising, weak or uncertain.
Explore again
Spend another round on a promising branch and one uncertain branch.

Info

Deliverable: a Search / Candidate Action Map. It lists your candidate actions, the tree with results, the branches eliminated and why, the comparison on decision dimensions, and the chosen next action with its reason. Keep it for your Agent Planning & Reasoning Canvas.

Continue to Module 5: Next: how does an agent know it did the right thing?

Check yourself

In the mini exercise, what is the purpose of the Update step?

To record what you learned about a branch so later rounds can focus betterTo delete the Goal and start againTo prove that the chosen action is correct

Key takeaway: Explore, Evaluate, Update, Explore again: then record the result in your Search / Candidate Action Map.

Search, Trees & MCTS for Agent Decisions

Learning objectives

Search space and search trees

When the next step has more than one option

The search tree: depth, breadth and horizon

Comparing and choosing branches

Heuristic, utility, cost and risk

Exploration versus exploitation

MCTS as a planning concept

Practice and deliverable

Activity 4: Search the Next Step

MCTS mini exercise and the Candidate Action Map

What next?