Decision Networks & Value of Perfect Information

Decision Networks

  • MEU: choose the action which maximizes the expected utility given the evidence

  • can directly operationalize this with decidsion networks

    • BNs with nodes for utility and actions

    • lets us calculate the expected utility for each action

  • New node types:

    • chance nodes

      • just like BNs

    • actions

      • rectangles

      • no parents

      • act as observed evidence

    • utility node

      • diamond

      • depends on action and chance nodes

  • Action selection

    • instantiate all evidence

    • set action node(s) each possible way

    • calculate posterior distribution for all parents of utility node, given the evidence

    • calculate expected utility for each action

    • choose maximizing action

Ex.

MEU(o) = maxEU(a) = 70

Example with BN:

Decisions as Outcome Trees:

Value of Information

  • compute value of acquiring evidence

    • can be done directly from decision network

  • ex. buying drilling rights:

    • two blocks A and B, only one has oil, worth k

    • can only drill in one location

    • prior probabilities 0.5 each & mutually exclusive

    • drilling in either A or B has EU = k/2, MEU = k/2

    • what is the value of information of O?

      • value of knowing which has oil

      • value is expected gain in MEU from new info

      • if we know oilLocation, MEU is k

        • gain in MEU?

  • Assume we have evidence E = e, value now would be:

    • MEU(e) = max ∑ P(s | e) U(s, a)

    • now assume we see that E’ = e’

      • MEU(e, e’) = max ∑ P(s | e, e’) U(s, a)

    • But E’ is a random variable whose value is unknown, so we dont know what e’ will be

    • Expected value if E’ is revealed and then we act:

      • MEU(e, E’) = ∑ P(e’ | e) MEU(e, e’)

    • Value of information: how much MEU goes up by revealing E’ before acting

      • VPI(E’ | e) = MEU(e, E’) - MEU(e)

  • VPI Properties

    • Nonnegative

      • ∀E’, e : VPI(E’ | e) ≥ 0

    • Nonadditive

      • VPI(Ej, Ek | e) ≠ VPI(Ej | e) + VPI(Ek | e)

  • VPI Oil Example:

    • VPI(oilLocation) = k/2

    • VPI(scoutingReport) = between 0 - k/2

    • VPI(scout) = 0

    • VPI(scout | scoutingReport) = ?

      • generally,

        • if Parents(U) ⊥ Z | CurrentEvidence

        • then VPI(Z | CurrentEvidence) = 0


VPI Example:

POMDPs

  • states S

  • actions A

  • transition function P(s’ | s, a) or T(s, a, s’)

  • rewards R(s, a, s’)

  • observations O

  • observation function P(o | s) or O(s, o)

  • POMDPs are MDPs over belief states b

  • Solving:

    • use truncated expectimax to compute approximate value of actions