Lecture Note
Lecture 19: Decision Making under Uncertainty
-
University:
Massachusetts Institute of Technology -
Course:
6.825 | Techniques in Artificial Intelligence (SMA 5504) Academic year:
2022
-
Views:
158
Pages:
102
Author:
Lowpegelswa
6.825 Techniques in Artificial Intelligence
Decision Making under Uncertainty
• How to make one decision in the face of
uncertainty
Lecture 19 • 1
In the next two lectures, we’ll look at the question of how to make decisions,
to choose actions, when there’s uncertainty about what their outcomes will
be.
1 6.825 Techniques in Artificial Intelligence
Decision Making under Uncertainty
• How to make one decision in the face of
uncertainty
• In a deterministic problem, making one decision
is easy
Lecture 19 • 2
When we were looking at deterministic, logical representations of world
dynamics, it was easy to figure out how to make a single decision: you
would just look at the outcome of each action and see which is best.
2 6.825 Techniques in Artificial Intelligence
Decision Making under Uncertainty
• How to make one decision in the face of
uncertainty
• In a deterministic problem, making one decision
is easy
• Planning is hard because we considered long
sequences of actions
Lecture 19 • 3
What made planning hard, was that we had to consider long sequences of
actions, and we tried to be clever in order to avoid considering all of the
exponentially many possible sequences of actions.
3 6.825 Techniques in Artificial Intelligence
Decision Making under Uncertainty
• How to make one decision in the face of
uncertainty
• In a deterministic problem, making one decision
is easy
• Planning is hard because we considered long
sequences of actions
• Given uncertainty, even making one decision is
difficult
Lecture 19 • 4
When there’s substantial uncertainty in the world, we are not even sure how
to make one decision. How do you weigh two possible actions when you’re
not sure what their results will be?
4 6.825 Techniques in Artificial Intelligence
Decision Making under Uncertainty
• How to make one decision in the face of
uncertainty
• In a deterministic problem, making one decision
is easy
• Planning is hard because we considered long
sequences of actions
• Given uncertainty, even making one decision is
difficult
Lecture 19 • 5
In this lecture, we’ll look at the foundational assumptions of decision theory,
and then see how to apply it to making single (or a very small number of)
decisions. We’ll see that this theory doesn’t really describe human decision
making, but it might still be a good basis for building intelligent agents.
5 A short survey
1. Which alternative would you prefer:
A. A sure gain of $240
B. A 25% chance of winning $1000 and a 75% chance of
winning nothing
• 2. Which alternative would you prefer:
• C. A sure loss of $750
• D. A 75% chance of losing $1000 and a 25% chance of
losing nothing
• 3. How much would you pay to play the following game:
We flip a coin. If it comes up heads, I’ll pay you $2. If it
comes up tails, we’ll flip again, and if it comes up heads, I’ll
pay you $4. If it comes up tails, we’ll flip again, and if it
comes up heads, I’ll pay you $8. And so on, out to infinity.
Lecture 19 • 6
Please stop and answer these questions. Don’t try to think about the “right”
answer. Just say what you would really prefer.
6 Decision Theory
• A calculus for decision-making under uncertainty
Lecture 19 • 7
Decision theory is a calculus for decision-making under uncertainty. It’s a
little bit like the view we took of probability: it doesn’t tell you what your basic
preferences ought to be, but it does tell you what decisions to make in
complex situations, based on your primitive preferences.
7 Decision Theory
• A calculus for decision-making under uncertainty
• Set of primitive outcomes
Lecture 19 • 8
So, it starts by assuming that there is some set of primitive outcomes in the
domain of interest. They could be winning or losing amounts of money, or
having some disease, or passing a test, or having a car accident, or anything
else that is appropriately viewed as a possible outcome in a domain.
8 Decision Theory
• A calculus for decision-making under uncertainty
• Set of primitive outcomes
• Preferences on primitive outcomes: A f B
Lecture 19 • 9
Then, we assume that you, the user, have a set of preferences on primitive
outcomes. We use this funny curvy greater-than sign to mean that you
would prefer to have outcome A happen than outcome B.
9 Decision Theory
• A calculus for decision-making under uncertainty
• Set of primitive outcomes
• Preferences on primitive outcomes: A f B
• Subjective degrees of belief (probabilities)
Lecture 19 • 10
We also assume that you have a set of subjective degrees of belief (which
we’ll call probabilities) about the likelihood of different outcomes actually
happening in various situations.
10 Decision Theory
• A calculus for decision-making under uncertainty
• Set of primitive outcomes
• Preferences on primitive outcomes: A f B
• Subjective degrees of belief (probabilities)
• Lotteries: uncertain outcomes
p
1-p
A
B
With probability p,
outcome A occurs; with
probability 1 - p; outcome
B occurs.
Lecture 19 • 11
Then, we’ll model uncertain outcomes as lotteries. We’ll draw a lottery like
this, with a circle indicating a “chance” node, in which, with probability p,
outcome A will happen, and with probability 1-p, outcome B will happen.
11 Axioms of Decision Theory
If you accept these conditions on your preferences,
then decision theory should apply to you!
Lecture 19 • 12
Decision theory is characterized by a set of six axioms. If your preferences
(or your robot’s preferences!) meet the requirements in the axioms, then
decision theory will tell you how to make your decisions. If you disagree with
the axioms, then you have to find another way of choosing actions.
12 Axioms of Decision Theory
If you accept these conditions on your preferences,
then decision theory should apply to you!
• Orderability: A f B or B f A or A ≈ B
Lecture 19 • 13
The first axiom is orderability. It says that for every pair of primitive
outcomes, either you prefer A to B, you prefer B to A, or you think A and B
are equally preferable. Basically, this means that if I ask you about two
different outcomes, you don’t just say you have no idea which one you
prefer.
13 Axioms of Decision Theory
If you accept these conditions on your preferences,
then decision theory should apply to you!
• Orderability: A f B or B f A or A ≈ B
• Transitivity: If A f B and B f C then A f C
Lecture 19 • 14
Transitivity says that if you like A better than B, and you like B better than C,
then you like A better than C.
14 Axioms of Decision Theory
If you accept these conditions on your preferences,
then decision theory should apply to you!
• Orderability: A f B or B f A or A ≈ B
• Transitivity: If A f B and B f C then A f C
• Continuity: If A f B f C then there exists p such
that L1 ≈ L2
p
A
L2
L1
1-p
1
B
C
Lecture 19 • 15
Continuity says that if you prefer A to B and you prefer B to C, then there’s
some probability that makes the following lotteries equivalently preferable for
you. In the first lottery, you get your best outcome, A, with probability p, and
your worst outcome, C, with probability 1-p. In the second lottery, you get
your medium-good outcome, B, with certainty. So, the idea is that, by
adjusting p, you can make these lotteries equivalently attractive, for any
combination of A, B, and C.
15 More Axioms of Decision Theory
• Substitutability: If A f B , then L1 f L2
p
A
L1
p
B
L2
1-p
C
1-p
C
Lecture 19 • 16
Substitutability says that if you prefer A to B, then given two lotteries that are
exactly the same, except that one has A in a particular position and the other
has B, you should prefer the lottery that contains A.
16 More Axioms of Decision Theory
• Substitutability: If A f B , then L1 f L2
A
p
B
p
L1
L2
1-p
C
1-p
C
• Monotonicity: If A f B and p > q, then L1 f L2
p
A
L1
q
A
L2
1-p
B
1-q
B
Lecture 19 • 17
Monotonicity says that if you prefer A to B, and if p is greater than q, then
you should prefer a lottery that gives A over B with higher probability.
17 Last Axiom of Decision Theory
• Decomposibility: L1 ≈ L2
p
L1
A
q
B
1-p
1-q
C
p
L2
A
q(1-p) B
(1-p)(1-q)
C
Lecture 19 • 18
The last axiom of decision theory is decomposability. It, in some sense,
defines compound lotteries. It says that a two-stage lottery, where in the first
stage you get A with probability p, and in the second stage you get B
withprobability q and C with probability 1-q is equivalent to a single-stage
lottery with three possible outcomes: A with probability p, B with probability
(1-p)*q, and C with probability (1-p)*(1-q).
18 Main Theorem
If preferences satisfy these six assumptions, then
there exists U (a real valued function) such that:
• If A f B , then U(A) > U(B)
• If A ≈ B , then U(A) = U(B)
Lecture 19 • 19
So, if your preferences satisfy these six axioms, then there exists a realvalued function U such that if you prefer A to B, then U(A) is greater than
U(B), and if you prefer A and B equally, then U(A) is equal to U(B).
Basically, this says that all possible outcomes can be mapped onto a single
utility scale, and we can work directly with utilities rather than collections of
preferences.
19 Main Theorem
If preferences satisfy these six assumptions, then
there exists U (a real valued function) such that:
• If A f B , then U(A) > U(B)
• If A ≈ B , then U(A) = U(B)
Utility of a lottery = expected utility of the outcomes
U(L) = p ⋅ U (A) + (1− p) ⋅ U (B)
p
A
L
1-p
B
Lecture 19 • 20
One direct consequence of this is that the utility of a lottery is the expected
utility of the outcomes. So, the utility of our standard simple lottery L is p
times the utility of A plus (1-p) times the utility of B. Once we know how to
compute the utility of a simple lottery like this, we can also compute the utility
of very complex lotteries.
20 Main Theorem
If preferences satisfy these six assumptions, then
there exists U (a real valued function) such that:
• If A f B , then U(A) > U(B)
• If A ≈ B , then U(A) = U(B)
Utility of a lottery = expected utility of the outcomes
U(L) = p ⋅ U (A) + (1− p) ⋅ U (B)
p
A
L
1-p
B
Lecture 19 • 21
Interestingly enough, if we make no assumptions on the behavior of
probabilities other than that they have to satisfy the properties described in
these axioms, then we can show that probabilities actually have to satisfy the
standard axioms of probability.
21 Survey Question 1
Lecture 19 • 22
We’re going to use the survey questions to motivate a discussion of utility
functions and, in particular, the utility of money.
22 Survey Question 1
Which alternative would you prefer:
A. A sure gain of $240
B. A 25% chance of winning $1000 and a 75% chance of
winning nothing
Lecture 19 • 23
So, the first survey question was whether you’d prefer option A, a sure gain
of $240, or option B, a 25% chance of winning $1000 and a 75% chance of
winning nothing.
23 Survey Question 1
Which alternative would you prefer:
A. A sure gain of $240
B. A 25% chance of winning $1000 and a 75% chance of
winning nothing
85% prefer option A to option B
Lecture 19 • 24
When I polled one class of students, 85% preferred option A. This is
consistent with results obtained in experiments published in the psychology
literature.
24 Survey Question 1
Which alternative would you prefer:
A. A sure gain of $240
B. A 25% chance of winning $1000 and a 75% chance of
winning nothing
85% prefer option A to option B
• U(B) = .25 U($1000) + .75 U($0)
• U(A) = U($240)
• U(A) > U(B)
Lecture 19 • 25
So, what do we know about the utility function of a person who prefers A to
B? We know that the utility of B is .25 times the utility of $1000 plus .75
times the utility of $0. (We’re not going to make any particular assumptions
about the utility scale; so we don’t know, for example, that the utility of $0 is
0). We know that the utility of A is the utility of $240. And we know that the
utility of A is greater than the utility of B.
25 Utility of Money
U(1000)
utility
U(0)
0
$
1000
Lecture 19 • 26
Let’s look in detail at how utility varies as a function of money. So, here’s a
graph with money on the x axis and utility on the y axis. We’ve put in two
points representing $0 and $1000, and their respective utilities.
26 Utility of Money
• U(B) = .25 U($1000) + .75 U($0)
U(1000)
utility
U(B)
U(0)
0
$
1000
Lecture 19 • 27
Now, let’s think about the utility of option B. It’s an amount that is 1/4 of the
way up the y axis between the utility of $0 and the utility of $1000.
27 Utility of Money
• U(B) = .25 U($1000) + .75 U($0)
• U(A) = U($240)
U(1000)
utility
U(B)
U(0)
0
A
$
1000
Lecture 19 • 28
The utility of A is the utility of $240; we don’t know exactly what its value is,
but it will be plotted somewhere on this vertical line (with x coordinate 240).
28 Utility of Money
• U(B) = .25 U($1000) + .75 U($0)
• U(A) = U($240)
• U(A) > U(B)
U(1000)
U(A)
U(B)
U(0)
0
A
$
1000
Lecture 19 • 29
Now, since we know that the utility of A is greater than the utility of B, we just
pick a y value for the utility of A that’s above the utility of B, and that lets us
add a point to the graph at coordinates A, U(A).
29 Utility of Money
• U(B) = .25 U($1000) + .75 U($0)
• U(A) = U($240)
concave utility function
risk averse
• U(A) > U(B)
U(1000)
U(A)
U(B)
U(0)
0
A
$
1000
Lecture 19 • 30
If we plot a curve through these three points, we see that the utility function
is concave. This kind of a utility curve is frequently referred to as “risk
averse”. This describes a person who would in general prefers a smaller
amount of money for sure, rather than lotteries with a larger expected
amount of money (but not expected utility). Most people are risk averse in
this way.
30 Utility of Money
• U(B) = .25 U($1000) + .75 U($0)
• U(A) = U($240)
concave utility function
risk averse
• U(A) > U(B)
U(1000)
U(A)
U(B)
U(0)
0
A
$
1000
Lecture 19 • 31
It’s important to remember that decision theory applies in any case. It’s not
necessary to have a utility curve of any particular shape (in fact, you could
even prefer less money to more!) in order for decision theory to apply to you.
You just have to agree to the 6 axioms.
31 Risk neutrality
• U(B) = .25 U($1000) + .75 U($0) = U($250)
• U(A) = U($240)
linear utility function
risk neutral
U(1000)
U(B)
U(A)
U(0)
0
A
$
1000
Lecture 19 • 32
In contrast to the risk averse attitude described in the previous graph,
another attitude is risk neutrality. If you are “risk neutral”, then your utility
function over money is linear. In that case, your expected utility for a lottery
is exactly proportional to the expected amount of money you’ll make. So, in
our example, the utility of B would be exactly equal to the utility of $250. And
so it would be greater than the utility of A, but not a lot.
32 Risk neutrality
• U(B) = .25 U($1000) + .75 U($0) = U($250)
• U(A) = U($240)
linear utility function
risk neutral
U(1000)
U(B)
U(A)
U(0)
0
A
$
1000
Lecture 19 • 33
People who are risk neutral are often described as “expected value” decision
makers.
33 Why Play the Lottery?
Lecture 19 • 34
Do you think that decision theory would ever recommend to someone that
they should play the lottery?
34 Why Play the Lottery?
Consider a lottery ticket:
• Expected payoff always less than price
• Is it ever consistent with utility theory to buy one?
Lecture 19 • 35
In any real lottery, the expected amount of money you’ll win is always less
than the price. I once calculated the expected value of a $1 Massachusetts
lottery ticket, and it was about 67 cents.
35 Why Play the Lottery?
Consider a lottery ticket:
• Expected payoff always less than price
• Is it ever consistent with utility theory to buy one?
It’s kind of like preferring lottery B to A, below:
A. A sure gain of $260
B. A 25% chance of winning $1000 and a 75% chance of
winning nothing
Lecture 19 • 36
To stay consistent with our previous example, imagine that I offer you either
a sure gain of $260, or a 25% chance of winning $1000 and a 75% chance
of winning nothing.
36 Why Play the Lottery?
Consider a lottery ticket:
• Expected payoff always less than price
• Is it ever consistent with utility theory to buy one?
It’s kind of like preferring lottery B to A, below:
A. A sure gain of $260
B. A 25% chance of winning $1000 and a 75% chance of
winning nothing
Lecture 19 • 37
Wanting to buy a lottery ticket is like preferring B to A. B is a smaller
expected value ($250) than A, but it has the prospect of a high payoff with
low probability (though in this example the payoff is a lot lower and the
probability a lot higher than it is in a typical real lottery).
37 Why Play the Lottery?
Consider a lottery ticket:
• Expected payoff always less than price
• Is it ever consistent with utility theory to buy one?
It’s kind of like preferring lottery B to A, below:
A. A sure gain of $260
B. A 25% chance of winning $1000 and a 75% chance of
winning nothing
In utility terms:
•
U(B) = .25 U($1000) + .75 U($0)
•
U(A) = U($260)
•
U(A) < U(B)
Lecture 19 • 38
We can describe the situation in terms of your utility function. The utility of B
is .25 times the utility of $1000 plus .75 times the utility of $0. The utility of A
is the utility of $260. And the utility of A is less than the utility of B.
38 Risk seeking
• U(B) = .25 U($1000) + .75 U($0)
• U(A) = U($260)
convex utility function
risk seeking
• U(A) < U(B)
U(1000)
U(B)
U(A)
U(0)
0
A
$
1000
Lecture 19 • 39
We can show the situation on a graph as before. The utility of B remains
one quarter of the way between the utility of $0 and the utility of $1000. But
now, A is slightly more than $250, and its utility is lower than that of B. We
can see that this forces our utility function to be convex. In general, we’ll
prefer a somewhat riskier situation to a sure one. Such a preference curve
is called “risk seeking”.
39 Risk seeking
• U(B) = .25 U($1000) + .75 U($0)
• U(A) = U($260)
convex utility function
risk seeking
• U(A) < U(B)
U(1000)
U(B)
U(A)
U(0)
0
A
$
1000
Lecture 19 • 40
It’s possible to argue that people play the lottery for a variety of reasons,
including the excitement of the game, etc. But here we’ve argued that there
are utility functions under which it’s completely rational to play the lottery, for
monetary concerns alone. You could think of this utility function applying, in
particular, to people who are currently in very bad circumstances. For such
a person, the prospect of winning $10,000 or more might be so dramatically
better than their current circumstances, that even though they’re almost
certain to lose, it’s worth $1 to them to have a chance at a great outcome.
40 Survey Question 2
Which alternative would you prefer:
• C. A sure loss of $750
• D. A 75% chance of losing $1000 and a 25% chance
of losing nothing
Lecture 19 • 41
Now, let’s look at survey question 2. It asks whether you’d prefer a sure loss
of $750 or a 75% chance of losing $1000 and a 25% chance of losing
nothing.
41 Survey Question 2
Which alternative would you prefer:
• C. A sure loss of $750
• D. A 75% chance of losing $1000 and a 25% chance
of losing nothing
91% prefer option D to option C
Lecture 19 • 42
The vast majority of students in a class I polled preferred option D to option
C. This is also consistent with results published in the psychology literature.
People generally hate the idea of accepting a sure loss, and would rather
take a risk in order to have a chance of losing nothing.
42 Survey Question 2
Which alternative would you prefer:
• C. A sure loss of $750
• D. A 75% chance of losing $1000 and a 25% chance
of losing nothing
91% prefer option D to option C
• U(D) = .75 U(-$1000) + .25 U($0)
• U(C) = U(-$750)
• U(D) > U(C)
Lecture 19 • 43
If you prefer option D to option C, we can characterize the utility function as
follows. The utility of D is .75 times the utility of -$1000 plus .25 times the
utility of $0. The utility of C is the utility of -$750. And the utility of D is
greater than the utility of C.
43 Risk seeking in losses
• U(D) = .75 U(-$1000) + .25 U($0)
• U(C) = U(-$750)
convex utility function
risk seeking
• U(D) > U(C)
U(0)
U(D)
U(C)
U(-1000)
-1000
C
$
0
Lecture 19 • 44
By the same arguments as last time, we can see that these preferences
imply a convex utility function, which induces risk seeking behavior. It is
generally found that people are risk seeking in the domain of losses. Or, at
least, in the domain of small losses.
44 Risk seeking in losses
• U(D) = .75 U(-$1000) + .25 U($0)
• U(C) = U(-$750)
convex utility function
risk seeking
• U(D) > U(C)
U(0)
U(D)
U(C)
U(-1000)
-1000
C
$
0
Lecture 19 • 45
An interesting case to consider here is that of insurance. You can think of
insurance as accepting a small guaranteed loss (the insurance premium)
rather than accepting a lottery in which, with a very small chance, a terrible
thing happens to you. So, perhaps, in the domain of large losses, people’s
utility functions tend to change curvature and become concave again.
45 Risk seeking in losses
• U(D) = .75 U(-$1000) + .25 U($0)
• U(C) = U(-$750)
convex utility function
risk seeking
• U(D) > U(C)
U(0)
U(D)
U(C)
U(-1000)
-1000
C
$
0
Lecture 19 • 46
It’s often possible to cause people to reverse their preferences just by
changing the wording in a question. If I were selling insurance, I would have
asked whether you’d rather accept the possibility of losing $1000, or pay an
insurance premium of $750 that guarantees you’ll never have such a bad
loss. That change in wording might make option C more attractive than D.
46 Human irrationality
Most people prefer A in question 1 and D in
question 2.
Lecture 19 • 47
We’ve seen that decision theory can accommodate people who prefer option
A to B, and people who prefer option D to C. In fact, most people prefer A
and D. But we can show that it’s not so good to both prefer A to B and D to
C.
47 Human irrationality
Most people prefer A in question 1 and D in
question 2.
A and D
.75
.25
-760
240
Lecture 19 • 48
The easiest way to see it is to examine the total outcomes and probabilities
of option A and D versus B and C.
48 Human irrationality
Most people prefer A in question 1 and D in
question 2.
A and D
.75
.25
-760
240
Lecture 19 • 49
If you pick A and D, then with probability .75 you have a net loss of $760 and
with probability .25 you have a net gain of $240.
49 Human irrationality
Most people prefer A in question 1 and D in
question 2.
A and D
.75
.25
-760
240
B and C
.75
.25
-750
250
Lecture 19 • 50
On the other hand, if you pick B and C, then with probability .75 you have a
net loss of $750 and with probability .25, you have a net gain of $250.
50 Human irrationality
Most people prefer A in question 1 and D in
question 2.
A and D
.75
.25
-760
240
B and C
.75
.25
-750
250
Lecture 19 • 51
So, with B and C, it’s like getting an extra $10, no matter what happens. So
it seems like it’s just irrational to prefer A and D.
51 Human irrationality
Most people prefer A in question 1 and D in
question 2.
A and D
.75
.25
-760
240
B and C
.75
.25
-750
250
Lecture 19 • 52
One student in my class made a convincing argument that it isn’t irrational at
all. That being given each single choice, it’s okay to pick A in one and D in
the other. But if you know you’re going to be given both choices, then it
would be unreasonable to pick both A and D.
52 St. Petersburg Paradox
1/2
$2
1/4 $4
1/8
$8
…
1/16
$16
Lecture 19 • 53
Just for fun, I asked how much you would pay to play this game, in which
you get $2 with probability 1/2, $4 with probability 1/4, etc. This is called the
St. Petersburg Paradox.
53 St. Petersburg Paradox
1/2
$2
1/4 $4
1/8
$8
…
1/16
$16
Expected value = 1 + 1 + 1 + … = ∞
Lecture 19 • 54
It’s a paradox because the game has an expected dollar amount of infinity
(1/2 * 2 is 1; 1/4 * 4 is 1; etc). However, most people don’t want to pay more
than about $4 to play it. That’s a pretty big discrepancy.
54 St. Petersburg Paradox
1/2
$2
1/4 $4
1/8
$8
…
1/16
$16
Expected value = 1 + 1 + 1 + … = ∞
Lecture 19 • 55
It was this paradox that drove Bernoulli to think about concave, risk averse,
utility curves, which you can use to show that although the game has an
infinite expected dollar value, it will only have a finite expected utility for a
risk averse person.
55 Buying a Used Car
Lecture 19 • 56
Okay. Now we’re going to switch gears a little bit, and see how utility theory
might be used in a (somewhat) practical example.
56 Buying a Used Car
• Costs $1000
• Can sell it for $1100, $100 profit
Lecture 19 • 57
Imagine that you have the opportunity to buy a used car for $1000. You
think you can repair it and sell it for $1100, making a $100 profit.
57 Buying a Used Car
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Lecture 19 • 58
You have some uncertainty, though, about the state of the car. It might be a
lemon (a fundamentally bad car) or a peach (a good one). You think that
20% of cars are lemons. It costs $40 to repair a peach, and $200 to repair a
lemon.
58 Buying a Used Car
•
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Risk neutral
Lecture 19 • 59
Let’s further assume that, for this whole example, that you’re risk neutral, so
that the utility of $100 is 100. This isn’t at all necessary to the example, but
it will simplify our discussion and notation.
59 Buying a Used Car
•
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Risk neutral
decision
tree
Lecture 19 • 60
We can describe this decision problem using a decision tree. Note that we
also talk about decision trees in supervised learning; these decision trees
are almost completely different from those other ones; don’t confuse them,
despite the same name!
60 Buying a Used Car
•
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Risk neutral
Choice
buy
decision
tree
don’t
buy
$0
Lecture 19 • 61
We start the decision tree with a “choice” node, shown as a green square:
we have the choice of either buying the car or not buying it. If we don’t buy
it, then the outcome is $0.
61 Buying a Used Car
•
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Risk neutral
Chance
Choice
(max)
.2
lemon -$100
buy
decision
tree
.8
don’t
buy
peach +$60
$0
Lecture 19 • 62
If we do buy the car, then the outcome is a lottery. We’ll represent the
lottery as a “chance” node, shown as a blue circle. With probability 0.2, the
car will be a lemon and we’ll have the outcome of losing $100 ($100 in profit
minus $200 for repairs). With probability 0.8, the car will be a peach, and
we’ll have the outcome of gaining $60 ($100 in profit minus $40 for repairs).
62 Buying a Used Car
•
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Risk neutral
Choice
(max)
Chance
(expected
value)
.2
lemon -$100
buy
decision
tree
.8
don’t
buy
peach +$60
$0
Lecture 19 • 63
Now, we can use this tree to figure out what to do. We will evaluate it; that
is, assign a value to each node. Starting from the leaves and working back
toward the root, we compute a value for each node. At chance nodes, we
compute the expected value for each leaf (it’s nature who is making the
choice here, so we just have to take the average outcome). At choice
nodes, we have complete control, so the value is the maximum of the values
of all the leaves.
63 Buying a Used Car
•
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Risk neutral
Choice
(max)
Chance
(expected
value)
.2
$28
buy
decision
tree
.8
don’t
buy
lemon -$100
.2*-100+.8*60=28
peach +$60
$0
Lecture 19 • 64
So, we start by evaluating the chance node. The expected value of this
lottery is $28, so we assign that value to the chance node.
64 Buying a Used Car
•
•
•
•
•
•
Costs $1000
Can sell it for $1100, $100 profit
Every car is a lemon or a peach
20% are lemons
Costs $40 to repair a peach, $200 to repair a lemon
Risk neutral
decision
tree
Choice
(max)
$28
Chance
(expected
value)
.2
$28
lemon -$100
buy
.8
don’t
buy
peach +$60
$0
Lecture 19 • 65
Now, we evaluate the choice node. We’ll make $28 if we buy the car and
nothing if we don’t. So, we choose to buy the car (which we show by putting
an arrow down that branch), and we assign value 28 to the choice node.
65 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you buy it)?
Lecture 19 • 66
Now, while we’re sitting at the used car lot, thinking about whether to buy this
car, an unhappy employee comes out and offers to sell us perfect
information about whether the car is really a lemon or a peach. He’s been
working on the car and he knows for sure which it is. So, the question is,
what is the maximum amount of money that we should be willing to pay him
for this information?
66 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you buy it)?
• Reverse the order of the chance and action nodes. The
chance node represents uncertainty on what the
information will be, once we get it.
Lecture 19 • 67
We’ll draw a decision tree to help us figure this out. We need to draw the
nodes in a different order from left to right. In this scenario, the idea is that
we first get the information about whether the car is a lemon or a peach, and
then we get to make our decision (and the important point is that it can
possibly be different in the two different cases).
67 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you buy it)?
• Reverse the order of the chance and action nodes. The
chance node represents uncertainty on what the
information will be, once we get it.
lemon
.2
.8
peach
Lecture 19 • 68
So, we start with a chance node, to describe the chance that the car is a
lemon or a peach.
68 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you buy it)?
• Reverse the order of the chance and action nodes. The
chance node represents uncertainty on what the
information will be, once we get it.
buy
lemon
.2
.8
don’t
buy
buy
-$100
$0
$60
peach
don’t
buy
$0
Lecture 19 • 69
Now, for each of those pieces of information, we include a choice node
about whether or not to buy the car.
69 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you buy it)?
• Reverse the order of the chance and action nodes. The
chance node represents uncertainty on what the
information will be, once we get it.
• C is cost you have to pay for information
buy
lemon
.2
.8
don’t
buy
buy
-$100 - c
$0 - c
$60 - c
peach
don’t
buy
$0 – c
Lecture 19 • 70
Let’s let c be the amount of money we have to pay for this information.
When we calculate the outcomes for the leaves, we have to subtract c from
the outcomes we calculated before (-100 for buying a lemon, 0 for not
buying anything, and +60 for buying a peach).
70 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you take it to be repaired)?
• Reverse the order of the chance and action nodes. The
chance node represents uncertainty on what the
information will be, once we get it.
• C is cost you have to pay for information
-c
lemon
.2
.8
peach
buy
don’t
buy
buy
$60 - c
don’t
buy
-$100 - c
$0 - c
$60 - c
$0 – c
Lecture 19 • 71
We evaluate the tree as before, working back from the leaves toward the
root. We first hit these two choice nodes. In the top choice node, it’s clearly
better not to buy the car, for a total loss of c dollars. In the bottom choice
node, it’s better to buy the car, for a net of 60 – c dollars.
71 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you take it to be repaired)?
• Reverse the order of the chance and action nodes. The
chance node represents uncertainty on what the
information will be, once we get it.
• C is cost you have to pay for information
-c
$48 - c
lemon
.2
.8
peach
buy
don’t
buy
buy
$60 - c
don’t
buy
-$100 - c
$0 - c
$60 - c
$0 – c
Lecture 19 • 72
Now, we arrive at the chance node, where we take the expected value of the
leaves. In this case, we get 48 – c dollars.
72 Expected Value of Perfect Info
How much should you pay for information of what type of car it
is (before you take it to be repaired)?
• Reverse the order of the chance and action nodes. The
chance node represents uncertainty on what the
information will be, once we get it.
• C is cost you have to pay for information
-c
$48 - c
c = $20 [EVPI]
ties the expected
value with no
information
lemon
.2
.8
peach
buy
don’t
buy
buy
$60 - c
don’t
buy
-$100 - c
$0 - c
$60 - c
$0 – c
Lecture 19 • 73
Since the original car-buying deal was worth $28 in the case without any
extra information, then we shouldn’t pay any more than $20 for perfect
information. If we pay that much, then this deal is equivalent to the original
one. If we pay less than $20, then this deal is better. We’ll say that $20 is
the expected value of perfect information.
73 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
Lecture 19 • 74
Now let’s consider a different scenario. Nobody comes out to offer us
information. Instead, a sleazy guy comes out of the office and says he has a
special deal, just for us. He’ll sell us a guarantee on this car for $60. It will
cover %50 of all repair costs, if the repairs cost less than $100. But if the
repairs are more than $100, it will cover them all.
74 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
buy car &
guarantee
buy car
don’t
buy
Lecture 19 • 75
So, should we buy the guarantee? Let’s make a decision tree. Now we
have three choices. We can buy both the car and the guarantee, we can
buy the car only, or we can buy nothing (it’s completely unreasonable to buy
just the guarantee!).
75 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
.2
buy car &
guarantee
.8
lemon
peach
buy car
don’t
buy
Lecture 19 • 76
If we buy the car and the guarantee, then we have to consider what the
outcomes will be depending on whether or not it’s a lemon.
76 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
.2
buy car &
guarantee
.8
lemon $40
($100 profit $60 guarantee)
peach
buy car
don’t
buy
Lecture 19 • 77
If it’s a lemon, we make $40. That’s because the guarantee covers all the
repairs. So we make $100 profit on the sale of the car, but we have to pay
$60 for the guarantee.
77 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
.2
buy car &
guarantee
buy car
.8
lemon $40
($100 profit $60 guarantee)
peach $20
($100 profit –
$60 guarantee –
$20 repair)
don’t
buy
Lecture 19 • 78
If it’s a peach, we make $20. We start with $100 in profit, but we have to
pay $60 for the guarantee and $20 for repairs (at least we only have to pay
for half of the repairs!).
78 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
.2
buy car
.8
$28
buy car &
guarantee
lemon $40
($100 profit $60 guarantee)
peach $20
($100 profit –
$60 guarantee –
$20 repair)
don’t
buy
Lecture 19 • 79
Now, if we decide to buy the car, we can substitute in the chance node and
outcomes that we already calculated for buying the car in the first example. I
put in a red triangle to stand for the summarization of some other decision
tree, with a result of $28.
79 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
.2
buy car &
guarantee
.8
don’t
buy
$28
buy car
lemon $40
($100 profit $60 guarantee)
peach $20
($100 profit –
$60 guarantee –
$20 repair)
$0
Lecture 19 • 80
Finally, if we don’t buy the car, we have a guaranteed zero.
80 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
$24
buy car &
guarantee
.8
$28
buy car
don’t
buy
.2
lemon $40
($100 profit $60 guarantee)
.2*40+.8*20=24
peach $20
($100 profit –
$60 guarantee –
$20 repair)
$0
Lecture 19 • 81
So, we start by figuring out the value of the new chance node. The expected
value is $24.
81 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
$24
buy car &
guarantee
.8
buy car
don’t
buy
$28
$28
.2
lemon $40
($100 profit $60 guarantee)
peach $20
($100 profit –
$60 guarantee –
$20 repair)
$0
Lecture 19 • 82
Now, at the choice node, we pick the maximum value course of action, which
is to buy the car but not the guarantee. And so, this whole deal still has a
value of $28.
82 Guarantee?
• Costs $60
• Covers 50% of repair costs
• If repairs > $100, covers them all
$24
buy car &
guarantee
.8
buy car
don’t
buy
$28
$28
.2
lemon $40
($100 profit $60 guarantee)
peach $20
($100 profit –
$60 guarantee –
$20 repair)
$0
Most people would buy the guarantee in this
situation, due to risk aversion.
Lecture 19 • 83
Interestingly, most people would buy the guarantee in this situation, If you
buy the guarantee, you are sure to make at least some profit. If you don’t,
you could possibly lose $100.
83 Inspection?
We can have the car inspected for $9
Lecture 19 • 84
Just for some practice with Bayes’ rule, and another example, let’s think
about one more case. This time there’s no offer of perfect information or of
a guarantee. But there is a garage across the street that offers to inspect
the car for $9. It can’t tell for sure whether the car is a lemon or a peach. It
will perform a set of tests and tell you whether the car passes or fails.
84 Inspection?
We can have the car inspected for $9
P(“pass” | peach) = 0.9
P(“fail” | peach) = 0.1
P(“pass” | lemon) = 0.4
P(“fail” | lemon) = 0.6
Lecture 19 • 85
The tests aren’t completely reliable. So, the probability that it passes if it’s a
peach is 0.9. But the probability that it passes if it’s a lemon is 0.4.
85 Inspection?
We can have the car inspected for $9
P(“pass” | peach) = 0.9
P(“fail” | peach) = 0.1
P(“pass” | lemon) = 0.4
P(“fail” | lemon) = 0.6
P(“pass”) =
P(“pass” | lemon)P(lemon) + P(“pass” | peach)P(peach)
P(“pass”) = 0.4*0.2 + 0.9*0.8 = 0.8
P(“fail”) = 0.2
Lecture 19 • 86
We’re going to need to have some related probabilities for use in our
decision tree, so let’s do it now. We’ll need the probability of the car passing
the test, which is 0.8. Note that it’s only a coincidence that this is also the
probability that the car is a peach.
86 Inspection?
We can have the car inspected for $9
P(“pass” | peach) = 0.9
P(“fail” | peach) = 0.1
P(“pass” | lemon) = 0.4
P(“fail” | lemon) = 0.6
P(“pass”) =
P(“pass” | lemon)P(lemon) + P(“pass” | peach)P(peach)
P(“pass”) = 0.4*0.2 + 0.9*0.8 = 0.8
P(“fail”) = 0.2
P(lemon
P(lemon
P(lemon
P(lemon
|
|
|
|
“pass”) = P(“pass” | lemon) P(lemon)/P(“pass”)
“pass”) = 0.4 * (0.2 / 0.8) = 0.1
“fail”) = P(“fail” | lemon) P(lemon)/P(“fail”)
“fail”) = 0.6 * (0.2 / 0.2) = 0.6
Lecture 19 • 87
We’ll also need the probability of lemon given pass, which turns out to be
0.1, and the probability of lemon given fail, which turns out to be 0.6.
87 Inspection Tree
Lecture 19 • 88
Let’s build the decision tree for the inspection problem, so we can decide
whether we should pay for the inspection or not.
88 Inspection Tree
test
buy
don’t
buy
$28
$0
Lecture 19 • 89
We start with a choice node, with three options: test (which means, we pay
for the car to be inspected, and then perhaps buy it or not, depending on the
results), buy, which means we just buy the car, which as we’ve calculated
already has a value of $28, and don’t buy, which has a value of $0.
89 Inspection Tree
.8
pass
.2
test
buy
don’t
buy
fail
$28
$0
Lecture 19 • 90
Now, if we decide to test the car, the next thing that happens is that we find
out whether it passed or not. We just computed the probability of pass,
which is 0.8, so that’s the probability we put on this arc (and 0.2 on the fail
arc).
90 Inspection Tree
buy
.8
pass
.2
test
buy
don’t
buy
don’t
buy
fail
buy
$28
$0
don’t
buy
Lecture 19 • 91
Once we have the information from the garage about whether the car
passed or failed, we can decide whether to buy it or not. That results in
these two decision nodes.
91 Inspection Tree
lemon
buy
.8
pass
buy
don’t
buy
don’t
buy
.2
test
fail
peach
lemon
buy
peach
$28
$0
don’t
buy
Lecture 19 • 92
And finally, in each of the cases in which we buy the car, we have to add a
chance node to take into account whether the car really is a lemon or not.
92 Inspection Tree
.1
lemon
buy
peach
.9
.8
pass
.2
test
buy
don’t
buy
don’t
buy
fail
-$109
+$51
-$9
lemon
buy
peach
$28
$0
don’t
buy
Lecture 19 • 93
In the top node, we know that the car passed, and so when we put
probabilities on the branches, we condition on the information we already
know from having come down this path in the tree. So, on the “lemon”
branch, we put the probability of lemon given pass, which is 0.1. And, of
course we put 0.9 on the other branch. Then we can fill in the outcomes.
We have to subtract $9 in every case, because in this whole branch of the
tree, we’re assuming that we paid for the test.
93 Inspection Tree
.1
lemon
buy
peach
.9
.8
pass
don’t
buy
fail
.6
lemon
buy
don’t
buy
-$109
peach
.4
$28
$0
+$51
-$9
.2
test
buy
don’t
buy
-$109
+$51
-$9
Lecture 19 • 94
In the bottom choice node, we know that the car failed the test, so we label
the lemon branch with the probability of lemon given fail, which is .6, and the
other branch with .4. The outcomes are the same.
94 Inspection Tree
$35
.1
lemon
buy
peach
.9
.8
pass
.2
test
buy
don’t
buy
don’t
buy
fail
-$45
.6
lemon
buy
-$109
peach
.4
don’t
buy
+$51
-$9
$28
$0
-$109
+$51
-$9
Lecture 19 • 95
Whew! Now it’s time to evaluate this tree. We start by evaluating the
chance nodes nearest the leaves. We compute expected values, and get
+$35 for the top one and -$45 for the bottom one.
95 Inspection Tree
$35
$35
.8
pass
buy
don’t
buy
buy
don’t
buy
fail
-$45
.6
lemon
buy
-$109
peach
.4
don’t
buy
+$51
-$9
$28
$0
-$109
peach
.9
.2
test
.1
lemon
+$51
-$9
Lecture 19 • 96
Now, we can do the choice nodes. In the top choice node, it’s much better
to buy the car, and the node gets value +$35.
96 Inspection Tree
$35
$35
don’t
buy
$28
$0
-$9
.6
lemon
buy
-$109
peach
.4
don’t
buy
+$51
-$9
-$45
fail
-$109
peach
.9
.2
test
buy
buy
don’t
buy
.8
pass
.1
lemon
+$51
-$9
Lecture 19 • 97
In the bottom choice node, buying the car is a bad idea, so we just end up
with -$9, for having paid for the test.
97 Inspection Tree
$35
$35
$26.2
don’t
buy
$28
$0
-$9
.6
lemon
buy
-$109
peach
.4
don’t
buy
+$51
-$9
-$45
fail
-$109
peach
.9
.2
test
buy
buy
don’t
buy
.8
pass
.1
lemon
+$51
-$9
Lecture 19 • 98
Now we’re ready to evaluate the first chance node, by taking the expected
value of its children. We get +$26.2.
98 Inspection Tree
$35
$35
$26.2
buy
don’t
buy
$28
$0
-$9
.6
lemon
buy
-$109
peach
.4
don’t
buy
+$51
-$9
-$45
fail
-$109
peach
.9
.2
test
$28
buy
don’t
buy
.8
pass
.1
lemon
+$51
-$9
Lecture 19 • 99
Finally, we can decide what action to take on the first step: we’ll just buy the
car directly, without having it inspected.
99 Inspection Tree
$35
$35
$26.2
buy
don’t
buy
$28
$0
-$9
.6
lemon
buy
-$109
peach
.4
don’t
buy
+$51
-$9
-$45
fail
-$109
peach
.9
.2
test
$28
buy
don’t
buy
.8
pass
.1
lemon
+$51
-$9
Lecture 19 • 100
Again, this is probably a case in which a typical, somewhat risk averse
person would pay for the test. The worst outcome on the test branch is
losing $9, whereas the worst outcome on the buy branch is losing $100.
100 Recitation Problem
Let’s consider one last scenario in the purchase of
used cars. We are going to have the car inspected,
and then use the result of the inspection to decide if
we will:
• buy the car without a guarantee
• buy the car with a guarantee
• not buy the car
Calculate the decision tree for this scenario. Use all
the costs and probabilities from the previous
scenarios. What is the expected value? Is it better
than just buying the car ($28)?
Lecture 19 • 101
Here’s one more car buying scenario. You can have the car inspected first,
and then decide, based on the result, to buy the car with or without a
guarantee, or not at all. What should you do?
101 Another Recitation Problem
Is it ever useful (in the sense of resulting in higher
utility) to pay for information, but take the same
action no matter what information you get?
Lecture 19 • 102
102
Related Documents
- DBMS Mini Project
- COMP 182: Quiz 7
- Competitive Analysis Test
- Crafting a Discussion Guide
- The Question in UX
- The Hypothesis
- Research Plan Test
- Survey Structure Test
- COMP 182 Quiz 8 - Graph Part 1
- UX Research
- The UX Research Process
- Survey Structure
- Survey in UX Research
- How To Generate Interview Question
- Ethical Research
- Discussion Guide Test
- Deep Understanding Research Title
- Competitive Analysis
- Case Study Make a Research Plan
- Approach To Conduct Competitor Analysis
Lecture 19: Decision Making under Uncertainty
of 102
Recommended Documents
⏰ Deadline pressure?
Get your assignment done in just 3 hours. Quick, easy, and available 24/7.
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document