Lecture 10.1: Decision Theory and Utility

Up until now, we've looked at logical agents that pursue absolute goals (like winning a game or proving a theorem). But in the real world, agents face uncertainty and conflicting goals. A goal-based agent only knows the binary difference between a "good" state and a "bad" state.

A Decision-Theoretic Agent, however, has a continuous measure of outcome quality. It combines probability theory with utility theory to make rational decisions based on what it believes (probabilities) and what it wants (utilities).

---

Utility Theory

An agent's preferences are captured by a Utility Function, which maps states of the world to a real number: $u_i: S \rightarrow \mathbb{R}$ The larger the utility value, the more the agent prefers that state.

Perceived States vs. Complex Reality

States in $S$ are defined as those states of the world that the agent can perceive:

• Simple Sensor Example: Imagine a simple robot equipped with a single binary light sensor (where $0 = \text{dark}$ and $1 = \text{bright}$). Regardless of how complex the physical world is, the robot's utility function is defined over only two perceived states: $u_i(0) = 5, \quad u_i(1) = 10$
• Practical Application: Real-world agents receive high-dimensional inputs (cameras, LIDAR, sensors). It is impractical to assign a distinct utility output to every raw input, so agents map raw perceptual inputs into a smaller, manageable set of world states.

Utility Trade-Offs & Opportunity Cost

Utility functions allow agents to balance complex trade-offs:

• Package Delivery Agent: Must balance positive monetary payment against negative costs like electricity consumption and Opportunity Cost—defined as the value of foregone alternatives (an indirect cost incurred when choosing one task over another).

---

Preference Ordering Axioms

Given an agent's utility function, we can establish a preference ordering over states of the world. For an agent to be rational, its preferences over states must satisfy three core mathematical properties:

1. Reflexivity: Any state is at least as preferred as itself. $u_i(s) \ge u_i(s)$ Example: A number is always greater than or equal to itself ($3 \ge 3$), or "I am at least as old as myself."
2. Transitivity: If state $a$ is preferred to state $b$, and $b$ is preferred to $c$, then $a$ is preferred to $c$. $\text{If } u_i(a) \ge u_i(b) \text{ and } u_i(b) \ge u_i(c) \implies u_i(a) \ge u_i(c)$
3. Completeness (Comparability): An agent can compare any pair of states $a$ and $b$; it either prefers $a$ to $b$, $b$ to $a$, or is indifferent between them. $\forall a, b \quad \text{either } u_i(a) \ge u_i(b) \text{ or } u_i(b) \ge u_i(a)$

[!TIP] Completeness vs. Incompleteness Example

• Complete Preference: Dave states he strictly prefers larger chocolate bars to smaller ones. For any two chocolate bars, Dave can instantly compare them by size.
• Incomplete Preference: Susie states she always prefers chocolate bars that are both bigger and darker. If offered a large milk chocolate bar vs. a small dark chocolate bar, her rule fails to yield a decision, making her preference ordering incomplete.

---

Marginal Utility

Marginal Utility refers to the additional utility an agent gains from acquiring one more unit of a good or outcome. Depending on the scenario, marginal utility can take several distinct forms:

• Zero Marginal Utility: An additional copy of the exact same newspaper edition provides no extra value once you already own one.
• Positive Marginal Utility: A coupon for an additional haircut provides extra utility.
• Negative Marginal Utility: Taking additional doses of antibiotics beyond the prescribed limit causes toxicity and harm.
• Increasing Marginal Utility: Finding the second shoe of a pair. A single shoe has low utility, but pairing it with the second shoe dramatically increases utility.
• Diminishing Marginal Utility: Holding your breath under water—the first breath of air after surfacing has immense utility, whereas a second breath shortly after yields progressively less marginal gain.

Marginal Utility of Money

Consider two individuals: Bill (who has $100 million in the bank) and Tim (who has $0). Both contemplate winning an extra $1 million:

• The extra million dollars dramatically alters Tim's lifestyle, whereas Bill's lifestyle remains largely unchanged.
• Assuming both have the same utility for their first million dollars, Tim's marginal utility for the next million dollars is vastly larger than Bill's. Utility of wealth is logarithmic rather than linear.

---

The Framing Effect

The Framing Effect is a psychological phenomenon where individuals make different decisions depending on how identical information is presented—specifically whether choices are framed as gains or losses.

Consider an experiment where participants are given $1,000 initially:

Key Insight: In both scenarios, the net expected financial outcome is identical ($500 gain). However, framing choices as gains encourages risk aversion, while framing them as losses encourages risk seeking. This has vital implications for behavioral economics, AI planning, and decision theory.

---

Expected Utility

Since environments are uncertain and actuators/sensors are noisy (e.g., a robot attempting to step forward one foot may slip), actions lead to outcomes probabilistically.

The Transition Function $T(s, a, s')$ represents the probability of reaching state $s'$ given current state $s$ and action $a$: $\sum_{s' \in S} T(s, a, s') = 1$

The Expected Utility ($EU$) of taking action $a$ in state $s$ is the weighted sum of utilities across all possible resulting states: $E[u_i, s, a] = \sum_{s' \in S} T(s, a, s') u_i(s')$

The Maximum Expected Utility (MEU) Principle

A rational agent chooses an optimal action $a^*$ that maximizes its expected utility: $\pi_i^*(s) = \arg\max_{a \in A} E[u_i, s, a]$ This principle serves as the foundation for rational decision-theoretic agents.

---

The Value of Information (VPI)

In many scenarios, an agent can gather new information (e.g., run a diagnostic test) before taking an action. Suppose new information reveals that the agent is actually in state $t$ rather than state $s$.

The Value of Information is calculated as the expected utility of acting correctly in state $t$ minus the expected utility of mistakenly assuming state $s$ and acting under policy $\pi_i(s)$: $VPI = E[u_i, t, \pi_i(t)] - E[u_i, t, \pi_i(s)]$

[!NOTE] VPI Application: The Doctor's Medical Test A doctor has a preliminary decision on which drug to prescribe but is uncertain about the patient's exact disease state:

• If a diagnostic test—regardless of whether it comes back positive or negative—would still lead the doctor to prescribe the exact same drug, the VPI of that test is 0.
• If the test outcome is likely to alter the doctor's decision (e.g., prescribing Drug A on positive and Drug B on negative), the test has a high VPI.

---

Decision Networks (Influence Diagrams)

Decision networks (influence diagrams) extend Bayesian networks by incorporating actions (decisions) and utilities. They consist of three node types:

1. Chance / Uncertainty Nodes (Ovals): Represent random variables in the environment.
2. Decision / Action Nodes (Rectangles): Represent choices under the agent's direct control.
3. Value / Utility Nodes (Diamonds or Octagons): Represent utility functions mapping outcomes to payoffs.

Arc Classifications

Arcs in a decision network specify structural dependencies:

• Conditional Arcs (Chance $\rightarrow$ Chance): Indicate probabilistic dependence (e.g., Weather Condition affects Weather Forecast).
• Informational Arcs (Chance $\rightarrow$ Decision): Indicate that the outcome of the chance node is observed before making the decision (e.g., Weather Forecast is known before selecting Vacation Activity).
• Functional Arcs (Nodes $\rightarrow$ Utility): Indicate that utility directly depends on those variables (e.g., Satisfaction is a function of Weather Condition and Vacation Activity).

---

Numerical Example: The Oil Wild-Catter Problem

An oil drilling company must decide whether to drill at a potential site.

Problem Parameters

• States of Nature ($o$): $o=0$ (dry), $o=1$ (some oil), $o=2$ (soaking with oil).
• Prior Beliefs: $p(o) = [0.5, 0.3, 0.2]$.
• Actions ($d$): $d=0$ (don't drill), $d=1$ (drill).
• Utility Matrix $U(d, o)$:
  • If $d=0$: Payoff is $0$ across all states ($U(0, o) = [0, 0, 0]$).
  • If $d=1$: Payoff is $-70$ if dry, $50$ if wet, and $200$ if soaking ($U(1, o) = [-70, 50, 200]$).

Step 1: Evaluating Expected Utility Without Testing

$EU(d=0) = 0.5(0) + 0.3(0) + 0.2(0) = 0$ $EU(d=1) = \sum_{o=0}^2 p(o) U(1, o) = 0.5(-70) + 0.3(50) + 0.2(200) = -35 + 15 + 40 = 20$ $MEU = \max\{EU(d=0), EU(d=1)\} = \max\{0, 20\} = 20 \implies d^* = 1 \text{ (Drill)}$

Step 2: Decision Diagram with Seismic Sound Test & Cost

The agent can pay for a seismic test to observe a sound signal $s \in \{0, 1, 2\}$ prior to drilling:

Given test observation sound $s=0$, the updated conditional probabilities $p(o \mid s=0)$ are $[0.6, 0.3, 0.1]$: $EU(d=1 \mid s=0) = 0.6(-70) + 0.3(50) + 0.1(200) = -42 + 15 + 20 = -7$ Since $EU(d=1 \mid s=0) = -7 < EU(d=0 \mid s=0) = 0$, the optimal action upon observing sound $s=0$ switches to $d^* = 0$ (don't drill).

---

Factored Decision Networks: The Airport-Siting Problem

In large decision problems, chance nodes can be factored to simplify computation:

By factoring out intermediate outcome states (Deaths, Noise, Cost), the utility node $U$ directly receives functional arcs from the core decision (Airport Site) and environmental variables (Air Traffic, Litigation, Construction).

---

Algorithm for Evaluating Decision Networks

To choose the optimal action using a decision network, execute the following procedure:

1. Set Evidence: Fix all evidence variables corresponding to the current observed state of the world.
2. Iterate Over Decisions: For each possible value $a$ of the decision node:
   • Set the decision node to value $a$.
   • Calculate posterior probabilities for parent nodes of the utility node using standard probabilistic inference (e.g., variable elimination or belief propagation).
   • Calculate the resulting expected utility for action $a$.
3. Select Maximum Utility: Return the action $a^*$ that achieves the highest expected utility.