Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 37 ยท MDPs and Bellman Equations

Bellman Expectation Equations

Derive the Bellman expectation equations for v and q, see why they are a system of linear equations, and solve them exactly with NumPy for a grid world and a small MDP.

Estimating values by simulation works but is slow and noisy. The Bellman equations give a much sharper tool: they say that the value of a state is related to the values of its successor states. That relationship lets us compute values exactly (when we know the model) or learn them by bootstrapping (when we do not). If you remember one equation from reinforcement learning, make it this one.

Deriving the equation

Start from the recursive return G_t = R_{t+1} + gamma * G_{t+1} from Returns and Discounting. Take the expectation under policy pi, given S_t = s:

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

Read it from the outside in. Average over the actions the policy might choose, then average over the outcomes the environment might produce, and for each outcome add the immediate reward to the discounted value of the next state. The same trick for action values gives:

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

These are the Bellman expectation equations. A backup diagram shows the idea: a state looks ahead one step to its actions, then to the next states.

flowchart TD
    s["state s: v_pi(s)"] -->|"pi(a|s)"| a1["action a1"]
    s -->|"pi(a|s)"| a2["action a2"]
    a1 -->|"p, r"| s1["s' : v_pi(s')"]
    a1 -->|"p, r"| s2["s'' : v_pi(s'')"]
    a2 -->|"p, r"| s3["s''' : v_pi(s''')"]

A system of linear equations

For n states there are n equations with n unknowns, and the unknowns appear only linearly. Define the policy's expected one-step reward vector r_pi and its state-to-state transition matrix P_pi. Then:

v = r_pi + gamma * P_pi * v, so v = (I - gamma * P_pi)^(-1) * r_pi

For small problems we can just ask NumPy to solve it. For the 4x4 grid world with the random policy (and gamma = 1, fine here because every episode ends), the system has 14 unknowns, one per non-terminal square.

Python Solving the grid world exactly

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 printed grid shows -14, -20, -22 and the rest of the well-known values, now exact. Because terminal rows of P are all zero, their value is forced to 0 without special code.

Solving by iteration (a preview)

Inverting a matrix costs about n^3 operations, hopeless for a million states. A cheaper idea: treat the equation as an update rule. Start from any guess v, then repeatedly replace v by r_pi + gamma * P_pi * v. For gamma < 1 (or episodic tasks), this converges to the true values. That is iterative policy evaluation, the subject of the next chapter.

Bellman equations for a general MDP

The robot MDP from Markov Decision Processes gives a second example, this time with a stochastic transition and gamma = 0.9. We write a function that takes a policy and the dictionary model, builds P_pi and r_pi and solves. Then we compute q from v.

Python Evaluating two policies on the robot MDP

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 cautious policy has v(working) = 10 (it collects 1 per step forever: 1 / (1 - 0.9)), while the reckless one gets about 2.1. The q values then show something interesting: even under the cautious policy, q(working, push) is larger than q(working, wait). The best action is not the one the policy takes, which hints that the cautious policy can be improved. Exploiting that observation is the plan for policy improvement.

Common mistakes

  • Dropping the policy average. For stochastic policies, you must weight every action by pi(a | s).
  • Using the Bellman equation with gamma = 1 in a task that never ends. The linear system is then singular or the values infinite.
  • Forgetting that the equation holds simultaneously for all states: it is a system, not a one-pass formula.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Bellman expectation equation express?

    It averages over actions and outcomes of r + gamma * v(s'), which links each value to its successors.
  2. 2. Which matrix equation gives v_pi for a finite MDP?

    Rearranging v = r_pi + gamma P_pi v gives the solution (I - gamma P_pi)^-1 r_pi.
  3. 3. Why is matrix inversion not used for huge state spaces?

    O(n^3) time and O(n^2) memory make direct solves impractical; iteration or learning is used instead.
  4. 4. In the robot example, q(working, push) exceeded q(working, wait) under the cautious policy. What does that suggest?

    A larger action value than the policy's current action signals a policy improvement opportunity.

Summary

  • The Bellman expectation equation writes v_pi(s) as an average over actions and outcomes of r + gamma * v_pi(s'); there is a matching one for q_pi.
  • For a finite MDP it is a linear system with solution v = (I - gamma P_pi)^(-1) r_pi.
  • Exact solves are fine for small problems; iterative updates scale better and lead to dynamic programming.
  • q follows from v with one step of lookahead through the model.

Next: Bellman Optimality Equations