Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 46 ยท Probabilistic Reasoning

Decision Making: Utility, MDPs and Value Iteration

Learn decision making under uncertainty: expected utility, Markov decision processes, value iteration, policy iteration and Q-learning, with a runnable grid world in Python.

Probability tells an agent what is likely. It does not tell the agent what to do. To act, the agent must also know what it wants, and it must weigh the chances of each outcome against how much it likes or dislikes that outcome. The framework that combines the two is decision theory: choose the action with the highest expected utility.

When one decision leads to the next, as in navigation, games with chance, or running a warehouse, the agent needs a whole plan under uncertainty. The standard model is the Markov decision process (MDP). In this lesson you will learn expected utility, define an MDP, solve a grid world with value iteration and policy iteration, and then let an agent learn the same solution from experience with Q-learning, which is the doorway to reinforcement learning.

Expected utility

A utility function U assigns a number to each outcome, with higher meaning better. For an action a whose outcomes s' occur with probability P(s' | a), the expected utility is

EU(a) = ฮฃ P(s' | a) ยท U(s')

and a rational agent picks argmax_a EU(a). The principle is simple, but two points matter in practice.

  • Utility is not money. Most people prefer a sure 500 to a coin flip between 1,100 and 0, even though the flip has the higher average payout (550). A concave utility function such as the square root captures this risk aversion: the first dollars matter more than later ones.
  • Only the ordering and the shape matter. Multiplying every utility by 2 does not change any decision, but bending the curve (square root versus linear) can.

Insurance is rational for the same reason: a small certain loss (the premium) is preferred to a tiny chance of a catastrophic one, as the second half of the example shows.

Python Expected utility and risk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a linear utility the gamble wins (550 against 500), but both curved utilities pick the sure thing. Under the square-root utility the gamble is worth exactly as much as a certain 275, called its certainty equivalent. The insurance rows show the same effect: with log utility of wealth the agent happily pays more than the fair premium of 900 to avoid the risk, but not 3,000.

Markov decision processes

A Markov decision process describes sequential decisions where outcomes are partly random. It has five parts.

Part Symbol Grid-world example
States S the cells the robot can occupy
Actions A(s) up, down, left, right
Transition model P(s' | s, a) 80% the intended move, 10% slip to each side
Reward R(s) +1 at the goal, -1 on traps, -0.04 per step
Discount ฮณ how much later rewards are worth (0 to 1)

The word Markov means the transition depends only on the current state and action, the same assumption as in Hidden Markov Models. The difference is that here the agent chooses actions and sees its state directly.

The agent's answer is not a plan (a fixed sequence of actions), because slipping may land it anywhere. It is a policy ฯ€(s): a rule that says which action to take in every state. The best policy ฯ€* maximizes the expected discounted sum of rewards, R_0 + ฮณR_1 + ฮณยฒR_2 + .... Discounting (ฮณ < 1) makes sooner rewards worth more and keeps the sum finite for endless tasks. The small negative reward per step gives the agent a reason to hurry to the goal rather than wander.

graph LR
    S["State s"] -- "action a (policy)" --> P(("Chance:<br/>P(s' | s, a)"))
    P -- "reward R + next state s'" --> S2["State s'"]
    S2 -. "repeat" .-> S

At each step the agent picks an action, the world responds randomly, and the agent collects a reward.

Value iteration

The value of a state, V*(s), is the expected discounted reward when acting optimally from s. It satisfies the Bellman equation:

V*(s) = R(s) + ฮณ ยท max_a ฮฃ P(s' | s, a) ยท V*(s')

The value of a state is its own reward plus the discounted value of the best action. This is a system of equations (one per state) with a max in it, so it cannot be solved by simple algebra. Value iteration solves it by repeated sweeps: start with all values at zero (terminals at their reward), apply the right-hand side to every state, and repeat until the values stop changing. The updates converge in our episodic world, where every path ends in a terminal state, and in general for ฮณ < 1.

Once you have V*, the optimal policy is greedy: in each state choose the action with the highest expected next value.

The code below defines a small grid: 5 columns by 3 rows, a wall, a goal worth +1 at the top right, a trap worth -1 right below it, and a second trap at the top left. The robot slips sideways 20% of the time. It prints the converged values and the policy as arrows. It then repeats the calculation with two different living rewards, to show how rewards shape behavior.

Python Value iteration on a grid world

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the first grid of values. Cells next to the goal are worth about 0.9, and values fall as you move away or toward the traps. The arrows show careful behavior: the cell below the trap on the right, (4, 0), goes left rather than up, because moving up risks slipping into the trap. The policy gets the agent around danger even at the cost of extra steps. It converged in 42 sweeps.

The two extra grids show that the reward function defines the behavior. With a living reward of -2.0 every step hurts so much that the agent dives into the nearest exit, even a -1 trap: look at the cell beside the left trap, whose arrow points straight at it. With a small positive living reward and discounting, ending the episode is no longer attractive, so some arrows in the lower right point into walls or away from the exit, since lingering pays. As with the vacuum agents in Agents and Environments, you get what you reward, not what you meant.

Policy iteration

Value iteration improves values and extracts a policy at the end. Policy iteration alternates two steps and works directly with policies.

  1. Policy evaluation: given a fixed policy, compute its value V^ฯ€. With a fixed policy the max disappears, so this is a linear system of equations that can be solved exactly (here with numpy.linalg.solve).
  2. Policy improvement: in every state, switch to the action that looks best under V^ฯ€.

Repeat until no state changes its action. Policy iteration usually needs very few rounds (often under ten), though each round does more work than one value-iteration sweep. Both algorithms find the same optimal policy.

Python Policy iteration with exact evaluation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Policy iteration starts from the poor policy "always go up" and reaches the optimal policy in 5 rounds, and the final line confirms that it agrees with value iteration (using ฮณ = 0.99 for both, so that the linear system has a unique solution).

From planning to learning: Q-learning

Value and policy iteration need the model P(s' | s, a) in advance. A real robot or game agent often does not have it. Reinforcement learning removes that requirement: the agent acts, observes the reward and next state, and improves from experience alone.

Q-learning keeps a table Q(s, a), the estimated value of taking a in s and then behaving optimally. After each step (s, a, r, s') it nudges the entry toward a target:

Q(s, a) โ† Q(s, a) + ฮฑ ยท [ r + ฮณ ยท max_a' Q(s', a') โˆ’ Q(s, a) ]

ฮฑ is the learning rate. The agent has to balance exploration (trying actions it is unsure about) and exploitation (using what it knows); the simplest scheme is ฮต-greedy, which acts randomly with probability ฮต. The example below runs Q-learning on the same grid, where the world slips randomly but the agent never sees the 80/10/10 odds. We use a fixed seed, run three training lengths and compare the final answer with the exact policy from value iteration.

Python Q-learning from experience

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After only 50 episodes the learned policy already steers toward the goal, but the bottom row still differs from the optimal one. After 8,000 episodes it matches the exact policy in 8 of 11 states, and the three that differ are near-ties: the worst mistake costs only 0.033 in value. Q-learning's estimates are noisy with a fixed learning rate, which is why practical systems decay ฮฑ over time. For large problems the table is replaced by a neural network, which is how deep reinforcement learning works.

Which method when?

Situation Method
Known model, small state space value iteration or policy iteration
Known model, linear evaluation is cheap policy iteration (few rounds)
Unknown model, can interact Q-learning and other reinforcement learning
Hidden state (cannot see where you are) POMDPs, which combine MDPs with the filtering of the previous lesson

This chapter began with uncertainty and ends with acting under it. The final chapter takes the same ideas into the physical world, starting with Introduction to Robotics.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A coin flip pays 1,100 or 0 with equal chance; a sure payment is 500. Why might a rational agent still take the sure 500?

    Rational agents maximize expected utility, not expected money. With a concave utility such as the square root, the sure 500 has higher utility than the gamble.
  2. 2. What does the Bellman equation say about V*(s)?

    V*(s) = R(s) + gamma * max over actions of the expected V* of the next state. Value iteration applies this update repeatedly.
  3. 3. What is a policy in an MDP?

    Because outcomes are random, the agent needs a rule for every state rather than a single fixed plan.
  4. 4. How does policy iteration differ from value iteration?

    Policy evaluation with a fixed policy is a linear system. After evaluation, improvement switches actions where better ones exist. The loop ends when the policy is stable.
  5. 5. What is the main advantage of Q-learning over value iteration?

    Q-learning is model-free. The agent only needs to try actions and observe rewards and next states.

Summary

  • A rational agent maximizes expected utility; utility is not the same as money and is usually concave (risk averse).
  • An MDP has states, actions, a stochastic transition model, rewards and a discount; its solution is a policy, not a plan.
  • The Bellman equation defines state values; value iteration applies it repeatedly until convergence and then acts greedily.
  • Policy iteration alternates exact policy evaluation (a linear system) and policy improvement.
  • The reward function shapes behavior, so a poorly chosen one produces strange but optimal policies.
  • Q-learning learns action values from experience without a model, balancing exploration and exploitation.

Next: Introduction to Robotics: Sensors, Actuators and Control.