AI · SEQUENTIAL DECISIONS

17 · Making Complex Decisions

Sequential decisions require planning across time. Markov decision processes model state transitions and rewards; partial observability requires tracking beliefs about hidden states.

17.1 Sequential Decision Problems

An MDP specifies states, actions, transition probabilities, rewards, and a discount factor. A policy maps states to actions to maximize long-run return.

17.2 Algorithms for MDPs

Value iteration repeatedly applies the Bellman optimality update; policy iteration alternates policy evaluation and improvement.

17.3 Bandit Problems

A bandit agent repeatedly chooses among uncertain reward sources, balancing exploration to learn with exploitation of the best-known option.

17.4 Partially Observable MDPs

A POMDP adds hidden states and observations. The belief state—the probability distribution over possible states—summarizes useful history.

17.5 Algorithms for Solving POMDPs

POMDP methods plan over belief states, using exact or approximate value functions to account for both actions and future observations.

Key terms and a Bellman-update trace

MDP: A Markov decision process has states, actions, transition model, reward, and discount γ. “Markov” means the current state summarizes history relevant to future transitions and rewards.
Value and policy: V(s) estimates future discounted return from state s; a policy selects an action. Value iteration repeatedly improves values, then the displayed arrows greedily select actions from them.
Belief state / POMDP: When the true state is hidden, a belief is a probability distribution over states. The grid demo is fully observable; it does not solve a POMDP.
Bandit: A repeated choice among uncertain reward sources; exploration gathers information while exploitation uses the currently best estimate.

Synchronous update in this grid

for each nonterminal state s:
  Vnext[s] = max_a { reward(s,a,s') + 0.9 V[s'] }
  (walls clamp movement; terminal goal/pit values remain 0)

Trace: from state 2 (row 0, column 2), moving right enters goal state 3 and yields +1 immediately. A move to an ordinary state yields −0.04 + 0.9V(s′). The maximum wins; updates read the previous V array, not partially updated values.

MDP value iteration

Find a route to the goal

Deterministic 4×4 grid, discount γ = 0.9, step reward −0.04; goal +1 and pit −1 are terminal.

Policy progress

Iterations: 0

Agent: start (3, 0)

Arrows show the greedy action under current state values. Click step to update all states.

Ready to compute a policy.

Demo performance

Let S be the number of grid states and A the number of actions. One synchronous value-iteration click evaluates every action in every nonterminal state: O(SA) time; the copied next-value array uses O(S) auxiliary space. Here S=16 and A=4. Rendering computes up to four greedy actions per cell, also O(SA), and creates O(S) visualization cells. The policy walk additionally does at most 20 update rounds at startup and 22 movement ticks, so it remains bounded for this grid; this is not a general convergence-time guarantee.