3: Agent Decision Making

SC4003 - CE/CZ4046: Intelligent Agents

Prof Zhang Jie

Based on “An Introduction to MultiAgent Systems” by Michael Wooldridge, John Wiley & Sons, 2002/2009
“Artificial Intelligence: A Modern Approach” by S. Russell and P. Norvig.. Prentice-Hall, third edition, 2010

1
Overview

 Based on Chapters 16 & 17 in reference book:

“Artificial Intelligence: A Modern Approach” by S.
Russell and P. Norvig. Prentice-Hall, third edition,
2010
 Make Simple Decisions
 Make Complex Decisions
 Sequential decision making
 Agent’s utility depends on a sequence of decisions

2
Making Simple Decisions

 Utility Theory
 Multi-Attribute Utility Functions
 Decision Networks
 The Value of Information

3
Beliefs and Uncertainty

Utility Function
Expected
Utility
Outcome
Probabilities

4
Maximum Expected Utility

 Expected Utility

EU ( A | E ) = ∑ P ( Resulti ( A) | E , Do( A))U ( Resulti ( A))

i

 Principle of Maximum Expected Utility

 Choose action A with highest EU ( A | E )

5
Example

Robot
Hits wall (P = 0.1; U = 0)
Turn Right
Finds target (P = 0.9; U = 10)

Turn Left Fall water (P = 0.3; U = 0)

Finds target (P = 0.7; U = 10)

Choose action “Turn Right”

6
Basis of Utility Theory

 Rational preference
 Preference of rational agent ⇒ obey constraints
 Behavior describable as maximization of expected utility
 Notation
 Lottery(L): a complex decision making scenario
 Different outcomes are determined by chance

 L = [ p, A;1 − p, B ]
 A  B: A is preferred to B
 A ~ B: indifference between A and B
 AB : B is not preferred to A
Basis of Utility Theory

 Constraints
 Orderability

( A  B ) ∨ ( B  A) ∨ ( A ~ B )
 Transitivity
( A  B) ∧ ( B  C ) ⇒ ( A  C )
 Continuity
A  B  C ⇒ ∃p[ p, A;1 − p, C ] ~ B
Basis of Utility Theory

 Constraints (cont.)
 Substitutability

A ~ B ⇒ [ p, A;1 − p, C ] ~ [ p, B;1 − p, C ]
 Monotonicity
A  B ⇒ ( p ≥ q ⇔ [ p, A;1 − p, B ][q, A;1 − q, B ]

 Decomposability
[ p, A;1 − p, [q, B;1 − q, C ]]
~ [ p, A; (1 − p )q, B; (1 − p )(1 − q ), C ]
Basis of Utility Theory

 Utility Principle
U ( A) > U ( B) ⇔ A  B
 Maximum Expected Utility principle
U ([ p1 , S1 ;; pn , S n ]) = ∑ piU ( Si )
i
 Utility Function
 Represents that the agent’s actions are trying to
achieve
 Can be constructed by observing agent’s
preferences
Utility Functions

 Utility
 Mapping state to real numbers
 Approach
 Compare A to standard lottery L p
 u : best possible prize with prob. p
 u : worst possible catastrophe with prob. 1-p
 Adjust p until A ~ L p

0.9 continue
$30 ~ L
0.1 death
Utility Functions

 Utility Scales
 Positive linear transform
U ' ( x) = k1U ( x) + k 2 where k1 > 0
 Normalized utility
u = 1.0, u = 0.0
 Micromort
 one-millionth chance of death
 russian roulette, insurance
 QALY
quality-adjusted life years
Multi-attribute Utility Functions

 Multi-Attribute Utility Theory (MAUT)

 Outcomes are characterized by 2 or more attributes.
 Site a new airport
 disruption by construction, cost of land, noise,….

 Approach
 Identify regularities in the preference behavior
Multi-attribute Utility Functions

 Notation
 Attributes
X 1 , X 2 , X 3 ,...
 Attribute value vector
X =< x1 , x2 ,.... >
 Utility Fn.
U ( x1 ,..., xn ) = f [ f1 ( x1 ),..., f n ( xn )]
Multi-attribute Utility Functions
 Dominance
 Certain (strict dominance, Fig.1)
 airport site S1 cost less, less noise, safer than S2:
strict dominance of S1 over S2
 Uncertain(Fig. 2)

Fig. 1 Fig.2
Multi-attribute Utility Functions

 Dominance(cont.)
 Stochastic dominance
 In real world problem

 S1 : avg $3.7billion,

standard deviation : $0.4billion

S2 : avg $4.0billion,
standard deviation : $0.35billion
 S1 stochastically dominates S2
Multi-attribute Utility Functions

 Preferences without Uncertainty

 Preferences between concrete outcome values.
 Preference structure
 X1 & X2 preferentially independent of X3 iff

Preference between < x1 , x2 , x3 > & < x'1 , x'2 , x3 >

Does not depend on x3

 Airport site : <Noise, Cost, Safety>

<20,000 suffer, $4.6billion, 0.06deaths/mpm>
vs. <70,000 suffer, $4.2billion, 0.06deaths/mpm>
Multi-attribute Utility Functions

 Preferences without Uncertainty (cont.)

 Mutual preferential independence (MPI)
 Every pair of attributes is P.I of its complements.

 Airport site : <Noise, Cost, Safety>

 Noise & Cost P.I Safety
 Noise & Safety P.I Cost

 Cost & Safety P.I Noise

: <Noise,Cost,Safety> exhibits MPI

 Agent’s preference behavior
max[V ( S ) = ∑ Vi ( X i ( S ))]
I
Multi-attribute Utility Functions
 Preferences with Uncertainty
 Preferences btw. Lotteries’ utility
 Utility Independence (UI)
 X is utility-independent of Y iff preferences over lotteries’
attribute set X do not depend on particular values of a set
of attribute Y.
 Mutual U.I(MUI)
 Each subset of attributes is U.I of the remaining attributes
 agent’s behavior (for 3 attributes): multiplicative Utility
Function
U = k1U1 + k 2U 2 + k3U 3 + k1k 2U1U 2 + k 2 k3U 2U 3 + k3 k1U 3U1
+ k3 k1U 3U1
Decision Networks

 Simple formalism for expressing & solving decision

problem
 Belief networks + decision & utility nodes
 Nodes
 Chance nodes
 Decision nodes
 Utility nodes
A Simple Decision Network
Decision node Airport Site
utility table

Air Traffic

Death

litigation Noise U

Cost

Construction
Utility node
CPT
A Simplified Representation

Airport Site
Action-utility table

Air Traffic

litigation U

Construction
Umbrella Network
take/don’t take
P(rain) = 0.4
Take Umbrella
rain

umbrella

P(umb|take) = 1.0
P(~umb|~take)=1.0 happiness

U(~umb, ~rain) = 100

U(~umb, rain) = -100
U(umb,~rain) = 0
U(umb,rain) = -25
Evaluating Decision Networks

 Set the evidence variables for current state

 For each possible value of the decision node:
 Set decision node to that value
 Calculate the posterior probability of the parent nodes
of the utility node, using BN inference
 Calculate the resulting utility for action
 return the action with the highest utility
 Umbrella Network

take/don’t take
P(rain) = 0.4
Take Umbrella
rain

umbrella #1
umb rain P(umb,rain | take)
P(umb|take) = 1.0
P(~umb|~take)=1.0 happiness 0 0
0 1
1 0
U(~umb, ~rain) = 100 1 1
U(~umb, rain) = -100
U(umb,~rain) = 0
U(umb,rain) = -25 #2: EU(take)
 Umbrella Network

take/don’t take
P(rain) = 0.4
Take Umbrella
rain

umbrella #1
umb rain P(umb,rain | ~take)
P(umb|take) = 1.0
P(~umb|~take)=1.0 happiness 0 0
0 1
1 0
U(~umb, ~rain) = 100 1 1
U(~umb, rain) = -100
U(umb,~rain) = 0
U(umb,rain) = -25 #2: EU(~take)
Value of Information (VOI)

 Suppose agent’s current knowledge is E. The value

of the current best action α is
EU(α | E) = max ∑ U(Re sult i ( A))P(Re sult i ( A) | E, Do( A))
A
i

 The value of the new best action (after new evidence

E’ is obtained):

EU(α′ | E, E′) = max ∑ U(Re sult i ( A))P(Re sult i ( A) | E, E′, Do( A))
A
i

 the value of information for E’ is:

VOI(E′) = ∑ P (e
k
k | E)EU(α ek | e k , E)− EU(α | E)
 Umbrella Network

take/don’t take
P(rain) = 0.4
Take Umbrella
rain

umbrella

P(umb|take) = 1.0 forecast

P(~umb|~take)=1.0 happiness
R F P(F|R)
0 0 0.8
U(~umb, ~rain) = 100 0 1 0.2
U(~umb, rain) = -100 1 0 0.3
U(umb,~rain) = 0
1 1 0.7
U(umb,rain) = -25
VOI

 VOI(forecast)=
P(rainy)EU(αrainy) +
P(~rainy)EU(α~rainy) –
EU(α)
 Umbrella Network
P(F=rainy) = 0.4
F R P(R|F)
0 0 0.8
0 1 0.2
1 0 0.3
1 1 0.7
take/don’t take
P(rain) = 0.4
Take Umbrella
rain

umbrella

P(umb|take) = 1.0 forecast

P(~umb|~take)=1.0 happiness
R F P(F|R)
0 0 0.8
U(~umb, ~rain) = 100 0 1 0.2
U(~umb, rain) = -100 1 0 0.3
U(umb,~rain) = 0
1 1 0.7
U(umb,rain) = -25
 umb rain P(umb,rain | take, rainy) umb rain P(umb,rain | take, ~rainy)

0 0 0 0

0 1 0 1

1 0 1 0

1 1 1 1

#1: EU(take|rainy) #3: EU(take|~rainy)

umb rain P(umb,rain | ~take, rainy) umb rain P(umb,rain |~take, ~rainy)

0 0 0 0

0 1 0 1

1 0 1 0

1 1 1 1

#2: EU(~take|rainy) #4: EU(~take|~rainy)

Making Complex Decisions

 Make a sequence of decisions

 Agent’s utility depends on a sequence of decisions
 Sequential Decision Making

 Markov Property
 Transition properties depend only on the current state,
not on previous history (how that state was reached)
 Markov Decision Processes
Markov Decision Processes
 Components:
 States s, beginning with initial state s0

 Actions a

 Each state s has actions A(s) available from it

 Transition model P(s’ | s, a)
 Markov assumption: the probability of going to s’ from s
depends only on s and a and not on any other past actions
or states
 Reward function R(s)
 Policy π(s): the action that an agent takes in any given state
 The “solution” to an MDP
 Game Show
 A series of questions with increasing level of
difficulty and increasing payoff
 Decision: at each step, take your earnings and
quit, or go for the next question
 If you answer wrong, you lose everything

$100 $1,000 $10,000 $50,000

question question question question
Correct:
Correct Correct Correct $61,100
Q1 Q2 Q3 Q4

Incorrect: Incorrect: Incorrect: Incorrect:

$0 $0 $0 $0

Quit: Quit: Quit:

$100 $1,100 $11,100
 Game Show
 Consider $50,000 question
 Probability of guessing correctly: 1/10

 Quit or go for the question?

 What is the expected payoff for continuing?

0.1 * 61,100 + 0.9 * 0 = 6,110
 What is the optimal decision?
$100 $1,000 $10,000 $50,000
question question question question
Correct:
Correct Correct Correct $61,100
Q1 Q2 Q3 Q4

Incorrect: Incorrect: Incorrect: Incorrect:

$0 $0 $0 $0

Quit: Quit: Quit:

$100 $1,100 $11,100
 Game Show
 What should we do in Q3?
 Payoff for quitting: $1,100
 Payoff for continuing: 0.5 * $11,100 = $5,550
 What about Q2?
 $100 for quitting vs. $4,162 for continuing
 What about Q1?
U = $3,746 U = $4,162 U = $5,550 U = $11,100
$100 $1,000 $10,000 $50,000
question question question question 1/10
9/10 3/4 1/2 Correct:
Correct Correct Correct $61,100
Q1 Q2 Q3 Q4

Incorrect: Incorrect: Incorrect: Incorrect:

$0 $0 $0 $0

Quit: Quit: Quit:

$100 $1,100 $11,100
Grid World

Transition model:

0.1 0.8 0.1

R(s) = -0.04 for every

non-terminal state

Source: P. Abbeel and D. Klein

Goal: Policy

Source: P. Abbeel and D. Klein

Grid World

Transition model:

R(s) = -0.04 for every

non-terminal state
Grid World

Optimal policy when

R(s) = -0.04 for every
non-terminal state
Grid World
 Optimal policies for other values of R(s):
Solving MDPs
 MDP components:
 States s

 Actions a

 Transition model P(s’ | s, a)

 Reward function R(s)

 The solution:
 Policy π(s): mapping from states to actions

 How to find the optimal policy?

Maximizing Expected Utility
 The optimal policy should maximize the expected
utility over all possible state sequences produced
by following that policy:

∑ P(sequence)U (sequence)
state sequences
starting from s 0

 How to define the utility of a state sequence?

 Sum of rewards of individual states
 Problem: infinite state sequences
Utilities of State Sequences
 Normally, we would define the utility of a state sequence
as the sum of the rewards of the individual states
 Problem: infinite state sequences
 Solution: discount the individual state rewards by a factor
γ between 0 and 1:

U ([ s0 , s1 , s2 , ]) = R ( s0 ) + γ R ( s1 ) + γ 2 R ( s2 ) + 
∞
Rmax
= ∑ γ R ( st ) ≤
t
(0 < γ < 1)
t =0 1− γ
 Sooner rewards count more than later rewards
 Makes sure the total utility stays bounded
 Helps algorithms converge
Utilities of States

 Expected utility obtained by policy π starting in state s:

π
U (s) = ∑ P(sequence)U (sequence)
state sequences
starting from s

 The “true” utility of a state, denoted U(s), is the expected

sum of discounted rewards if the agent executes an
optimal policy starting in state s
 Reminiscent of minimax values of states…
 Finding the Utilities of States
Max node  What is the expected utility of
taking action a in state s?

∑ P(s'| s, a)U (s' )

s'
Chance node

 How do we choose the optimal

P(s’ | s, a) action?

π * ( s ) = arg max ∑ P( s ' | s, a)U ( s ' )

a∈ A ( s ) s'
U(s’)
 What is the recursive expression for U(s) in terms of the
utilities of its successor states?

U ( s ) = R ( s ) + γ max a ∑ P( s ' | s, a )U ( s ' )

s'
The Bellman Equation
 Recursive relationship between the utilities of
successive states:
U ( s ) = R( s ) + γ max ∑ P( s ' | s, a )U ( s ' )
a∈ A ( s )
s'

Receive reward R(s)

Choose optimal action a

End up here with P(s’ | s, a)

Get utility U(s’)
(discounted by γ)
The Bellman Equation
 Recursive relationship between the utilities of
successive states:
U ( s ) = R( s ) + γ max ∑ P( s ' | s, a )U ( s ' )
a∈ A ( s )
s'

 For N states, we get N equations in N unknowns

 Solving them solves the MDP
 We could try to solve them through expectimax
search, but that would run into trouble with infinite
sequences
 Instead, we solve them algebraically
 Two methods: value iteration and policy iteration
Method 1: Value Iteration

 Start out with every U(s) = 0

 Iterate until convergence
 During the ith iteration, update the utility of each state
according to this rule:

U i +1 ( s ) ← R ( s ) + γ max ∑ P ( s ' | s, a )U i ( s ' )

a∈ A ( s )
s'

 In the limit of infinitely many iterations, guaranteed

to find the correct utility values
 In practice, don’t need an infinite number of iterations…
Value Iteration
 What effect does the update have?
U i +1 ( s ) ← R ( s ) + γ max ∑ P ( s ' | s, a )U i ( s ' )
a∈ A ( s )
s'
Method 2: Policy Iteration

 Start with some initial policy π0 and alternate

between the following steps:
 Policy evaluation: calculate Uπi(s) for every state s
 Policy improvement: calculate a new policy πi+1
based on the updated utilities

π i +1 ( s ) = arg max ∑ P( s ' | s, a)U π ( s ' )

i

a∈ A ( s ) s'
Policy Evaluation
 Given a fixed policy π, calculate Uπ(s) for every state s
 The Bellman equation for the optimal policy:

U ( s ) = R( s ) + γ max ∑ P( s ' | s, a )U ( s ' )

a∈ A ( s )
s'

 How does it need to change if our policy is fixed?

U π ( s ) = R( s ) + γ ∑ P( s ' | s, π ( s ))U π ( s ' )
s'

 Can solve a linear system to get all the utilities!

 Alternatively, can apply the following update:
U i +1 ( s ) ← R ( s ) + γ ∑ P ( s ' | s, π i ( s ))U i ( s ' )
s'
Summary

 Decision theory combines probability and utility theory

 A rational agent chooses the action with maximum
expected utility
 Multi-attribute utility theory deals with utilities that
depend on several attributes
 Decision networks extend BBN with additional nodes
 Making complex decisions – a sequence of decisions
 Markov decision processes assume Markov property
 Two methods for computing optimal policy
 Value iteration
 Policy iteration