Artificial Intelligence: A Conceptual Learner's Series
Part 5: Decisions
Knowing what's probably true is only half the job. This part covers how an agent turns beliefs into choices: weighing outcomes, deciding when to gather more information, planning over time and dealing with other agents.
Concept 1: Utility and expected utility
In one line: To choose well under uncertainty, give every outcome a score for how much you'd like it, then pick the action with the best probability-weighted average score.
Example: The forecast says 30% chance of rain. Carrying an umbrella is a minor hassle. Getting soaked on the way to an important meeting is miserable. Score the outcomes: dry with umbrella = 8, dry without = 10, soaked = 0, umbrella on a rainy day = 7. Taking the umbrella averages 0.3 × 7 + 0.7 × 8 = 7.7. Leaving it averages 0.3 × 0 + 0.7 × 10 = 7.0. Take the umbrella, even though it probably won't rain.
Formally:
A utility function U assigns a number to each outcome, reflecting the agent's preferences.
The expected utility of an action a is the average utility of its outcomes, weighted by their probabilities:
The principle of maximum expected utility (MEU): a rational agent chooses the action with the highest EU.
If preferences obey a few reasonable rules (such as consistency and transitivity), they can always be represented by some utility function.
Risk aversion: people often value a sure $50 above a 50% chance at $100. A curved utility of money captures this.
Connections: Expected utility is the precise version of the performance measure from Part 1, Concept 4, combined with the probabilities from Part 4.
Watch out:
Utilities aren't money. The tenth thousand dollars matters less to most people than the first.
Garbage in, garbage out. A precise calculation with made-up utilities can look more authoritative than it deserves.
Concept 2: The value of information
In one line: Gathering information is itself a decision, and it's worth paying for only when the answer could change what you'd do.
Example: You're buying a used car for $12,000. A mechanic's inspection costs $150. If the car might have a hidden transmission problem that would cost $3,000, and the inspection would tell you to walk away, it's well worth the money. But suppose you'd buy the car regardless, because you need it tomorrow and it's the only one available. Then the inspection can't change your decision, and its value to you is zero.
Formally:
The value of perfect information (VPI) of a variable is the expected gain in utility from learning its value before deciding, compared with deciding now.
VPI is never negative: free information can't hurt an agent that uses it rationally.
Information is valuable when it is likely to change the decision and the stakes of choosing wrong are high.
A rational agent gathers information when VPI exceeds the cost of getting it.
Connections: This is how an agent decides which percepts to seek out (Part 1, Concept 4) and connects to exploration in reinforcement learning (Part 8).
Watch out:
More data isn't always worth it. Analysis that can't change the decision is wasted effort, however interesting.
Free information can still hurt a biased reasoner. The "never negative" guarantee applies only to agents that update correctly.
Concept 3: Sequential decisions and Markov decision processes
In one line: When today's choice changes tomorrow's options, you need a policy: a rule for what to do in every situation, chosen to maximize total reward over time.
Example: A delivery robot moves around a warehouse grid. Each move costs a little battery. Reaching the loading dock earns a big reward; falling into the open freight elevator shaft is a disaster. Its wheels slip, so a move north succeeds 80% of the time and veers sideways otherwise. The robot can't just plan one fixed path; a slip could put it anywhere. It needs a plan for every square: "if I'm here, go this way." Squares next to the shaft get cautious plans that steer away, even if that means a longer route.
Formally:
A Markov decision process (MDP) has states, actions, a transition model P(s′ | s, a), a reward function R(s, a, s′) and a discount factor γ between 0 and 1 that makes future rewards count a bit less than immediate ones.
A policy π maps each state to an action. The goal is the policy with the highest expected total discounted reward.
The value V(s) of a state is the expected total reward from s onward under the best policy. It satisfies the Bellman equation:
In words: a state's value is the best action's expected immediate reward plus the discounted value of where you land.
Value iteration applies the Bellman equation repeatedly until values settle. Policy iteration alternates between evaluating a policy and improving it.
Connections: MDPs combine expected utility (Concept 1) with the Markov property (Part 4, Concept 5). Reinforcement learning (Part 8) solves MDPs when the transition model and rewards are unknown.
Watch out:
The discount factor shapes behavior. Near 0, the agent is short-sighted; near 1, it plans far ahead but converges more slowly.
Reward design is alignment in miniature. A small per-step penalty that's too large can make an agent prefer a quick disaster to a long trip (Part 1, Concept 8).
Concept 4: Decisions with hidden state
In one line: When you can't see the true situation, you have to choose actions based on your belief about it, including actions whose main purpose is to find out more.
Example: Your car makes a rattling noise. It could be a loose heat shield (cheap) or a failing bearing (expensive and dangerous). You can't see inside. Driving on is fine if it's the shield and risky if it's the bearing. A smart plan might be: pull over, tap the heat shield, listen. That action doesn't fix anything; its value is entirely in what it reveals, which then decides your next move.
Formally:
A partially observable MDP (POMDP) adds an observation model: the agent sees only clues that depend on the hidden state.
The agent maintains a belief state: a probability distribution over possible true states, updated by filtering (Part 4, Concept 5).
A POMDP policy maps belief states to actions. The best policies naturally include information-gathering actions.
Solving POMDPs exactly is very hard; practical methods use approximations and online planning from the current belief.
Connections: POMDPs unite sequential decisions (Concept 3), filtering (Part 4) and the value of information (Concept 2).
Watch out:
Acting on the most likely state can be dangerous. If the bearing is only 20% likely but catastrophic, you should act as though it might be true.
Belief spaces are continuous. Even a two-state problem has infinitely many possible belief states, which is why exact solutions are so expensive.
Concept 5: Decisions with other agents
In one line: When the outcome depends on other agents' choices too, the best move depends on what you expect them to do, and stable outcomes are those where nobody wants to change course alone.
Example: Two coffee shops on the same block each choose a price. If both charge $5, both do well. If one drops to $4, it steals customers and does better while the other suffers. So both drop to $4, and both end up worse off than if they'd held at $5. Neither can raise its price alone without losing customers. That's a stable outcome, even though it's not the best one for either shop.
Formally:
Game theory studies decisions where each agent's payoff depends on everyone's actions.
A strategy is an agent's plan; a dominant strategy is best no matter what others do.
A Nash equilibrium is a set of strategies where no agent can do better by changing only its own strategy. The coffee shops' $4 outcome is one.
The prisoner's dilemma is the classic case where individually rational choices produce a worse collective result.
Mechanism design works in reverse: design the rules (such as an auction format) so that self-interested agents produce a desirable outcome. Many online ad auctions are built this way.
Connections: This generalizes adversarial search (Part 2, Concept 5) beyond strictly opposed, turn-taking games to cooperation, competition and everything in between.
Watch out:
Equilibrium isn't optimal. Stable outcomes can be bad for everyone, as the coffee shops show.
Real agents aren't perfectly rational. Game-theory predictions can fail when people value fairness, reputation or reciprocity.
Retention kit
Answer from memory, then check. Review at about 1 day, 3 days, 1 week, 2 weeks and 1 month.
Redo the umbrella calculation. What would the rain probability have to be for leaving the umbrella to be the better choice?
When is information worth zero, even if it's free and accurate?
What are the parts of an MDP, and what does the Bellman equation say in words?
What is a belief state, and why do POMDP policies include actions that only gather information?
Define a Nash equilibrium and explain why it isn't always the best outcome.
Build exercise (1–2 hours): Model the warehouse robot from Concept 3 as a 6 × 5 grid with a +10 loading dock, a −10 elevator shaft next to the shortest route, a few wall squares and slippery moves (90% intended direction, 5% each side). Implement value iteration and print the resulting policy as arrows. Then change the per-step reward from −0.1 to −5 and watch the robot start risking the shaft to finish sooner.
Python algorithms
Expected utility for the umbrella (Concept 1), the value of perfect information for a used-car inspection (Concept 2), and value iteration on the slippery warehouse grid (Concept 3). It prints the policy twice so you can watch a harsh step cost push the robot toward the shaft. Runs with plain Python 3.
# 1. Expected utility: the umbrella decision
def expected_utility(outcomes):
"""outcomes: list of (probability, utility)."""
return sum(p * u for p, u in outcomes)
def umbrella(p_rain):
take = expected_utility([(p_rain, 7), (1 - p_rain, 8)])
leave = expected_utility([(p_rain, 0), (1 - p_rain, 10)])
return take, leave
# 2. Value of perfect information: inspect a used car before buying?
def vpi_car(p_problem=0.3, value_if_good=2000, repair=3000):
"""Utility = surplus from buying; walking away = 0."""
buy_now = (1 - p_problem) * value_if_good + p_problem * (value_if_good - repair)
eu_without = max(buy_now, 0)
# With perfect info, decide after learning the truth
eu_with = (1 - p_problem) * max(value_if_good, 0) + p_problem * max(value_if_good - repair, 0)
return eu_with - eu_without
# 3. Value iteration on the warehouse grid (an MDP)
ROWS, COLS = 4, 5
GOAL, SHAFT, WALLS = (0, 4), (1, 4), {(1, 1)}
MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}
SIDEWAYS = {"up": ("left", "right"), "down": ("left", "right"),
"left": ("up", "down"), "right": ("up", "down")}
def step(s, move):
r, c = s[0] + MOVES[move][0], s[1] + MOVES[move][1]
if not (0 <= r < ROWS and 0 <= c < COLS) or (r, c) in WALLS:
return s # bump: stay put
return (r, c)
def transitions(s, a):
"""Slippery floor: 90% intended direction, 5% each sideways."""
side1, side2 = SIDEWAYS[a]
return [(0.9, step(s, a)), (0.05, step(s, side1)), (0.05, step(s, side2))]
def reward(s2, step_cost):
return 10 if s2 == GOAL else -10 if s2 == SHAFT else step_cost
def value_iteration(step_cost=-0.1, gamma=0.95, tol=1e-6):
states = [(r, c) for r in range(ROWS) for c in range(COLS) if (r, c) not in WALLS]
V = {s: 0.0 for s in states}
while True:
delta = 0
for s in states:
if s in (GOAL, SHAFT):
continue # terminal squares
best = max(sum(p * (reward(s2, step_cost) + gamma * V[s2] * (s2 not in (GOAL, SHAFT)))
for p, s2 in transitions(s, a)) for a in MOVES)
delta, V[s] = max(delta, abs(best - V[s])), best
if delta < tol:
break
policy = {s: max(MOVES, key=lambda a: sum(
p * (reward(s2, step_cost) + gamma * V[s2] * (s2 not in (GOAL, SHAFT)))
for p, s2 in transitions(s, a))) for s in states if s not in (GOAL, SHAFT)}
return V, policy
def show(policy):
arrow = {"up": "^", "down": "v", "left": "<", "right": ">"}
for r in range(ROWS):
row = ""
for c in range(COLS):
s = (r, c)
row += " G " if s == GOAL else " X " if s == SHAFT else " # " if s in WALLS else f" {arrow[policy[s]]} "
print(row)
if __name__ == "__main__":
print("Umbrella EU (take, leave) at 30%% rain: %.1f, %.1f" % umbrella(0.3))
print("Value of a perfect inspection: $%.0f" % vpi_car())
print("Policy with small step cost (-0.1):"); show(value_iteration(-0.1)[1])
print("Policy with large step cost (-8):"); show(value_iteration(-8)[1])Output when run (G = loading dock, X = elevator shaft, # = wall):
Umbrella EU (take, leave) at 30% rain: 7.7, 7.0
Value of a perfect inspection: $300
Policy with small step cost (-0.1):
> > > > G
^ # ^ ^ X
^ > ^ ^ <
^ > ^ ^ <
Policy with large step cost (-8):
> > > > G
^ # ^ ^ X
> > ^ ^ ^
> > ^ ^ ^ With a small step cost, the squares under the shaft steer left to go around it. With a step cost of −8, three steps around cost more than falling in, so the robot heads straight up into the shaft: reward design shaping behavior, exactly as Concept 3 warns.
Try it:
Find the rain probability at which taking and leaving the umbrella tie.
Set
gammato 0.5 and see how a short-sighted robot's policy changes.