liveBook · Manning

Search tree

As explained in Grokking Bayes

A search tree is a tree representation of possible decisions, subsequent actions, outcomes, and utilities in a decision process.

A search tree represents a decision process as branching paths. The root describes the current state, action nodes show available choices, and later branches show possible scenarios with probabilities and utilities. section 12.1

The structure makes uncertainty visible. Begin at the leaf outcomes, multiply each utility by its branch probability, and add the weighted utilities leading to each action. Choose the action with the greatest expected utility. section 12.2

A search tree can represent:

  • A single decision followed by uncertain outcomes. section 12.1
  • Sequential decisions in which observed results influence whether another action is taken. section 12.7
  • Continuous uncertainty, where one action may have infinitely many branches indexed by a variable such as a conversion rate. section 12.4

Choosing between policies

A government can implement policy A, implement riskier policy B, or do nothing. Policy A has expected utility 6.5, policy B has expected utility 1, and doing nothing has utility 0, so the tree favors policy A. With sequential choices, the government can observe the first policy's payoff before deciding whether to continue. section 12.7

Table 12.3 Utility of two available policies under possible scenarios and the corresponding probabilities
Option
Policy A
Policy B
Doing nothing
Cost
1
2
0
Utility
10
5
30
0
0
Probability
0.5
0.5
0.1
0.9
1
Option
Cost
Utility
Probability
Policy A
1
10
0.5
5
0.5
Policy B
2
30
0.1
0
0.9
Doing nothing
0
0
1

Use the utility table to inspect the costs, outcomes, and probabilities that become the branches and terminal values of a policy search tree. section 12.7

How Grokking Bayes covers it

How deep it goes
Explains node roles, expected-utility traversal, sequential branching, and continuous outcomes, but stops short of implementation code.
Examples
Uses website launch choices, alternative government policies, utility tables, and one-step or two-step decision figures.
What it assumes
Assumes basic familiarity with actions, probabilities, outcomes, costs, and utilities while building the tree representation from those elements.
What you can do after
Evaluate actions by traversing outcome branches, weighting utilities by probabilities, and comparing expected utilities.
How it connects
Connects search trees with Bayesian decision theory, expected utility, utility functions, Markov decision processes, and reinforcement learning.

Also explained in

Compare how 2 books explain search tree →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking Bayes. The section links point to the parts of the book it draws on.