Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 37 ยท MDPs and Bellman Equations

Bellman Optimality Equations and Optimal Policies

Learn optimal value functions v* and q*, the Bellman optimality equations, why the max makes them non-linear, and how to extract an optimal policy; verified with Python code.

Evaluating a given policy is only half the job. The real goal is to find the best policy. The Bellman optimality equations characterize what "best" means, and they are the target of Q-learning, value iteration and almost every control algorithm you will meet.

Optimal value functions

Among all policies there is at least one that is at least as good as every other in every state. Call it pi*. All optimal policies share the same value functions:

  • v*(s) = the largest value any policy achieves in state s.
  • q*(s, a) = the largest value any policy achieves after taking action a in s.

Once you know q*, acting optimally is trivial: in each state pick argmax over a of q*(s, a). No lookahead, no model. If you know only v* you need one step of lookahead through the model to see which action leads to the best successor.

The equations

An optimal policy must take, in every state, the action with the highest value. So instead of averaging over actions, we maximize:

v*(s) = max over a of sum over s', r of p(s', r | s, a) * [ r + gamma * v*(s') ]

q*(s, a) = sum over s', r of p(s', r | s, a) * [ r + gamma * max over a' of q*(s', a') ]

These are the Bellman optimality equations. Compare them with the expectation equations: the average over the policy's actions became a max. That one change makes them non-linear, so you can no longer solve them with a single matrix inversion. We solve them by iteration or by learning.

flowchart TD
    s["state s: v*(s)"] -->|"max over actions"| a1["action a1: q*(s,a1)"]
    s -->|"max over actions"| a2["action a2: q*(s,a2)"]
    a1 -->|"p, r"| s1["s' : v*(s')"]
    a2 -->|"p, r"| s2["s'' : v*(s'')"]

Computing v* on the robot MDP

Start with all values at zero and keep applying the right-hand side of the equation as an update. For gamma = 0.9 the values converge. We then read the optimal policy by taking the greedy action with respect to those values.

Python Repeated optimality backups

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.

The result is a surprise worth thinking about: the optimal policy is to push when working and cool when hot. The risk is worth taking because a 70% chance of a reward of 4 beats a guaranteed 1, and the robot only pushes when it is safe (the dangerous push from hot is never used). The earlier "cautious" policy, with v = 10, was far from optimal (v* is about 19.7).

Verifying optimality by brute force

For a tiny MDP we can check the claim directly. There are only 2 actions in working and 2 in hot, so 4 deterministic policies. Evaluate each exactly (using the linear solve from the previous lesson) and see that the greedy policy beats the rest in every state.

Python Evaluating all deterministic policies

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.

The best policy dominates in both states, as the theory promises. For a problem with |A| actions and |S| states there are |A|^|S| deterministic policies, so brute force is hopeless beyond toy sizes. That is why we need smarter algorithms.

Why the optimality equation is useful

  1. Fixed point. The optimal value function is the unique solution of the Bellman optimality equation. Algorithms can iterate toward it.
  2. Greedy is enough. Acting greedily with respect to v* (with a model) or q* is optimal. You never need a complicated policy structure.
  3. Learning target. Q-learning's update, Q(s, a) <- Q(s, a) + alpha * (r + gamma * max Q(s', a') - Q(s, a)), is a sampled version of the q* equation. See Q-learning.

Common mistakes

  • Thinking the optimal policy is unique. Several actions may tie; their values are the same.
  • Expecting a closed-form solution. Because of the max, there usually is none.
  • Using a greedy policy while learning. An agent that never explores may not discover q* at all; that is what epsilon-greedy and friends are for.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does the Bellman optimality equation differ from the expectation equation?

    An optimal policy picks the best action, so the average over pi(a|s) becomes a max over a.
  2. 2. Given q*, how do you act optimally?

    q* already contains the whole lookahead, so the greedy action is optimal without a model.
  3. 3. Why can't we solve the optimality equations with one matrix inversion?

    The max is non-linear, so we use iteration (value iteration) or learning.
  4. 4. In the robot example, why was pushing optimal while working?

    A 70 percent chance of reward 4 outweighs the certain reward of 1 once the long-term effect is included.

Summary

  • v* and q* are the best achievable values; every optimal policy shares them.
  • The Bellman optimality equations replace the policy average with a max, which makes them non-linear.
  • Acting greedily with respect to q* is optimal; with v* you also need the model for one-step lookahead.
  • Repeatedly applying the optimality backup converges to v* (value iteration), and Q-learning samples the same equation.
  • Brute-forcing all policies is exponential, so we need algorithms: the next chapter starts with dynamic programming.

Next: Iterative Policy Evaluation