Skip to content

17 Decision Networks

Weather node and umbrella node combine into a utility node

weather node also points to a forecast node.

Now we can kinda reason about the optimal action for the agent to take

action: umbrella or no umbrella Chance: rain or sun

theres 1. brought umbrella but sunny, not best scenario 2. didn't bring and sunny, best scenario 3. brought umbrella and raining 4. didn't bring and raining, worst case scenario

how do we go about this utility maximization part of this?

what that basically means is we choose the option that maximizes the expected utility (MEU), given the evidence

we can operationalize this using decision networks

we can think of these decision networks as bayes nets where we have additional nodes for utilities and for actions.

we are going to try to calculated the expected utility of each action.

Once we compute the utilities for each action, that is our optimal decision. We have these new types of nodes: chance nodes, denoted by circular or oval nodes; action nodes are rectangles; utility nodes are diamonds, depending on action and chance nodes.

we can start by looking at the evidence by looking at all the

ACTION SELECTION

  • instantiate all evidence
  • set action nodes each possible way
  • calculate posterior for all parents of utility node, give the evidence
  • calculate expected utility for each action
  • choose maximizing action

so lets simplify to just weather, umbrella and utility

W P
Sun 0.7
Rain 0.3
A W U(A, W)
Leave Sun 100 %% best case scenario
Leave Rain 0 %% worst case scenario
Bring Sun 20
Bring Rain 70

we are going to start by computing the expected utilities for each decision

\(EU(\text{Leave}) = \sum_w P(w)U(\text{Leave}, w)\) #=: 0.7 * 100 + 0.3 * 0

\(EU(\text{Bring}) = \sum_w P(w)U(\text{Bring}, w)\) #=: 0.7 * 20 + 0.3 * 70

decisions at outcome trees

  • almost like expectimax/MDP's
  • whats changed? the probabilities of chance nodes can be hard to compute/require bayes net inference

where forecast is "bad"

W P(W, Forecast=Bad)
Sun 0.35
Rain 0.65

recalculate!

GHOSTBUSTERS

trying to find where the ghost is, and we want to figure out where it might be so we need to encode this in a DN?

value of information

  • compute value of acquiring evidence
  • can be done directly from decision network
  • very simple example, buying oil drilling rights
  • 2 blocks A and B exactly one has oil worth \(K\)
  • you drill in 1 location
  • prior probs are 0.5 each
  • drilling in either A or B has EU \(k/2\) so MEU is \(k/2\)
  • What's the value of information?
  • Value of knowing A or B has oil
  • Value is expected gain in MEU from new info
  • \(VPI = k - k/2 = k/2\) is the value of information of where the oil is located

lets look at the weather example with the umbrella action and forecast chance node and weather chance node.

we want to compute the value of information from the weather forecast

Compute the MEU with no evidence

\(MEU(\varnothing) = \max_a EU(a) = 70\) lets reason about the value of information of the forecast

so the forecast distribution

\(MEU(F = \text{Bad}) = \max_a EU(a|\text{bad}) = 53\)

\(MEU(F = \text{Good}) = \max_a EU(a|\text{good}) = 95\)

forecast distribution

F P(F)
good 0.59
bad 0.41

#=: (0.59 * 95 + 0.41 * 53) - 70

\(VPI(E'|e) = \left( \sum_{e'} P(e'|e)MEU(e,e') \right) - MEU(e)\)

kinda looks like the bellman eqns if you squint rly hard

VALUE OF INFORMATION

  • assume we have evidence \(E = e\). Value if we act now:
  • \(MEU(e) = \max_a \sum_s P(s|e)U(s, a)\)

Let's assume we see that \(E = e'\) - We see this additional information is \(e'\) - We want to solve for MEU in almost the same way, but it's conditioned on \(e'\)

is VPI ever negative for humans?

  • The soup of the day is either calm chowder or split pea, but you wouldn't order either one. What's the value of knowing which it is? In this case, the value of information is zero
  • There are two kinds of plastic forks at a picnic; one is sturdier. Is there a value of information to know which fork you have? we know its nonzero, so depending on the food we are eating, we can decide how gentle we are with our fork
  • lets say youre playing the lottery. prize is either 0 or 100
  • you cna play any number. whats the value of knowing the winning number? EU is $1 so the win EU is $100 so the difference is $99

we can also compute the EU if we know what the numbers are.

VALUE OF IMPERFECT INFORMATION

  • no such thing (as we formulate it)
  • information corresponds to the observation of a node in the decision network
  • if data is noisy that just means we dont observe the original variable, but another variable which is a noisy version of the original one?

\(VPI(\text{OilLoc})\) \(VPI(\text{ScoutingReport})\)? \(VPI(\text{Scout})\)? \(VPI(\text{Scout}|\text{ScoutingReport})\)

DrillLoc -> U OilLoc -> U OilLoc -> ScoutingReport Scout -> ScoutingReport

  • generally: if \(\text{Parents}(U) \perp Z\)

POMDPs

  • MDPs have
  • states \(S\)
  • actions \(A\)
  • Transition Function
  • Rewards
  • POMDPs have
  • Observations \(O\)
  • Observation Function \(P(o|s)\) or \(O(s, o)\)
  • now you have a distribution over the possible states you could be in based on the observation \(O\)
  • one way to think about POMDPs: MDPs over belief states \(b\) (distributions over \(s\))
  • alternatively, state in POMDPs: evidence you have determined so far

Let's solve Ghostbusters using POMDP?

  • Belief state determined by evidence to date \(\{e\}\)
  • Tree really over evidence sets
  • Probabilistic reasoning needed to predict new evidence given past evidence

solving POMDPs

  • one way: use truncated expectimax to compute approximate value of actions
  • what if you only consider busting or one sense followed by a bust
  • you can calculate the VPI from additional information
  • which gives you a VPI-based agent!
  • We want to know what the value of getting additional information from a sensor is, instead of just ghostbusting.