Skip to content

7 Uncertainty

UNCERTAIN OUTCOMES

  • many reasons for uncertainty
  • rolling dice
  • rolling forward, but wheels slip

worst case vs avg case

Idea: uncertain outcomes controlled by chance, not an adversary

At random, the adversary will choose one of the possible actions.

Expectimax

  • Why wouldn't we know the result of an action will be
  • explicit randomness
  • Unpredictable opponents: the ghost responds randomly
  • Actions can fail: when moving a robot, the wheels might slip
  • values should now reflect average case (expectimax) outcomes, or worst case (minimax) outcomes
  • expectimax search computes the avg score under optimal play
  • max nodes as in minimax search
  • chance nodes are like min nodes but the outcome is uncertain
  • calculate their expected utilities
  • Take the weighted average (expectation) of children
  • Later, we'll learn how to formalize the underlying uncertain-result problems as Markov Decision Processes

Expectimax example

  • If no probabilities are given, all of the children are equally weighted

depth-limited expectimax

  • in minimax, you can truncate the tree, and instead of computing the actual minimax nodes, you can just swap in a number
  • We can use an evaluation function; instead of having to take a node's children, we can compute the value of a node directly from the state.
  • We can compute that and obtain a value we can take from the node and propagate up.

Can we still do that in Expectimax?

  • Let's look at this
  • There are a lot of games happening
  • We need to estimate the true expectimax value, which requires a lot of work to compute
  • So we can create an evaluation function that would help us learn more about this tree.

Reminder: Probabilities

  • A random variable represents an event whose outcome is unknown
  • A probability distribution is an assignment of weights to outcomes
  • Example: traffic on the freeway
  • random variable \(T\) = whether there's traffic
  • outcomes \(T \in \{\text{none}, \text{light}, \text{heavy}\}\)
  • distribution: \(P(T = \text{none}) = 0.25\), \(P(T = \text{light}) = 0.50\), \(P(T = \text{heavy}) = 0.25\)
  • some laws of probability (more later)
  • probabilities are always non-negative
  • probabilities over all possible outcomes sum to one
  • As we get more evidence, probabilities might change
  • \(P(T = \text{Heavy}) = 0.25\), \(P(T = \text{Heavy} \mid \text{hour} = 8am) = 0.6\)
  • we'll talk about methods for reasoning and updating probabilities later

Reminder: Expectations

  • the expected value of a function of a random variable is the average, weighted by the probability distribution over outcomes
  • Example: how long to get to the airport

What probabilities to use?

  • In expectimax search, we have a probabilistic model of how the opponent (or environment) will behave in any state
  • model could be a simple uniform distribution (roll a die)
  • model could be sophisticated and require a great deal of computation
  • We have a chance node for any outcome out of our control: opponent or environment
  • The model might say that adversarial actions are likely

QUIZ: uninformed probabilities

It's not also an adversarial opponent who will

  • Let's say ur opponent will run a depth 2 minimax using the result 80% of the time and moving randomly otherwise
  • What tree search should you use?

Expectimax!!!

  • To figure out each chance node's probabilities, you have to run a simulation on your opponent.
  • This kind of thing gets very slow very quickly.

MODELING ASSUMPTIONS

  • What are some dangers of making wrong models of the world?
  • The two models of the world
  • optimism
    • any other agents are all indifferent,
    • assuming chance when the world is adversarial
  • pessimism
    • They're
    • Assuming the worst's case.
    • It's really hard to plan the environment at the worst case

Mixed layer types

  • eg backgammon
  • expectiminimax
  • environment is an extra "random agent" player that each move after each min/max agent
  • Each node computes the appropriate combinations of its children.
  • dice rolls increase \(b\): 21 possible moves with 2 dice
  • backgammon ~ 20 legal moves
  • depth 2 = \(20 \times (21 \times 20)^3 = 1.2 \times 10^9\)
  • as depth increase probabolioty of reacjoomg a govem [;ayer mpfes sjinks]

multi-agent utilities

  • What if the game is not zero-sum, or multiple players

generalization of minimax - terminals have utility tuples - Node values are also utility tuples - each player maximizes its own component - can give rise to cooperation and competition dynamically

What utilities to use?

  • For worst-case minimax reasoning, terminal function value doesn't matter
  • we just want better states to have higher evaluations (get the ordering right)
  • we call this insensitivity to monotonic transformations

utilities

  • a function from outcomes from some state in the world to a real number that describes the agent's preferences
  • Where do utilities come from
  • In a game, it may be simple (+1/-1)
  • Utilities summarize the agent's goals
  • Theorem: any rational preferences can be summarized as a utility function
  • We hard-wire utilities and let behaviors emerge

Preferences

agent must have a preferences among: - prizes: \(A\), \(B\) etc. - lotteries: situations w uncertain prizes - \(L = [p\,A, (1-p)\,B]\)

Rational preferences

we want some constraints on preferences before we call them rational

\((A > B) \wedge (B > C) = (A > C)\) (these are the weird curved greater than symbols, not the real ones)

  • for example, an agent with intransitive preferences can be induced to give away all of its money
  • if \(B > C\) then the agent would pay 1 cent to go from \(C\) to \(B\)
  • if \(A > B\) then agent would pay 1 cent to go from \(B\) to \(A\)
  • if \(C > A\) then agent would pay 1 cent to go from \(A\) to \(C\)
  • etc, lose all your money, you're stupid

The axioms of rationality

  • orderability
  • \((A > B) \vee (B > A) \vee (A \sim B)\)
  • Transitivity
  • put example
  • continuity
  • put example w ABC
  • substitutability
  • monotonicity

rational preference imply behaviour..

MEU PRINCIPLE

given any preference that satisfies these constraints there is a real valued function \(U\) s.t. - \(U(A) \geq U(B) \iff A \geq B\) - \(U([p_1, S_1; \dots; p_n, S_n]) = \sum_i p_i \, U(S_i)\)

Human utilities

normalized utilities: \(u_+ = 1.0\), \(u_- = 0\)

  • utilities will map states to numbers
  • standard approach to assessment (elicitation) of human utilities
  • compare a prize \(A\) to a standard lottery \(L_p\) between
    • best possible prize \(u_+\) with prob \(p\)
    • worst possible catastrophe \(u_-\) with prob \(1-p\)

Money

  • money does not behave as a utility function

Insurance

Next time, MDPs!