Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 37 ยท MDPs and Bellman Equations

Policies and Value Functions

Learn what a policy is and how the state-value function v and action-value function q measure long-term goodness, with a Python grid world estimated by simulation.

An agent needs a way to decide what to do, and a way to judge how good its situation is. A policy answers the first question. Value functions answer the second. Together they are the vocabulary of every later chapter: dynamic programming computes value functions, Q-learning learns them from experience, and policy-gradient methods optimize the policy directly.

Policies

A policy pi maps states to behavior.

  • A deterministic policy picks one action per state: a = pi(s).
  • A stochastic policy gives a probability for each action: pi(a | s), with probabilities summing to 1 in every state.

A policy depends only on the current state, not on time or history. That is enough in an MDP: if the state is Markov, an optimal behavior never needs more. Stochastic policies matter for exploration (epsilon-greedy is a stochastic policy), for games where predictability can be exploited, and for policy-gradient training, where the policy must be differentiable.

State-value function

The state-value function of a policy is the expected return when you start in state s and follow pi afterwards:

v_pi(s) = E_pi [ G_t | S_t = s ]

The expectation covers both the randomness of the environment and any randomness in the policy. v_pi(s) is a number that says "how good is it to be here, if I behave like this". Terminal states have value 0.

Action-value function

The action-value function q_pi(s, a) is the expected return if you are in s, take action a once (whatever it is, even a bad one), and follow pi afterwards:

q_pi(s, a) = E_pi [ G_t | S_t = s, A_t = a ]

The two are tied together: the value of a state is the policy-weighted average of its action values:

v_pi(s) = sum over a of pi(a | s) * q_pi(s, a)

Action values are what you need to choose between actions without a model: pick the a with the largest q. That is why Q-learning learns q rather than v.

A grid world to practice on

We will use a classic 4x4 grid world all chapter. Squares are numbered 0 to 15, row by row. Squares 0 (top-left) and 15 (bottom-right) are terminal. Every move costs a reward of -1, so the agent wants to finish quickly. Moving into a wall leaves you where you are. We estimate v_pi for the uniform random policy (each of 4 directions with probability 0.25) by plain simulation, which needs no equations.

Python Estimating v by simulation

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.

Squares next to a terminal have the highest (least negative) values, around -14, and the far corners about -22. The agent with this policy needs many steps because it wanders.

From q to v

Now estimate action values for one square, say square 5, by forcing the first action and then following the random policy. Their uniform average must match v(5).

Python Action values and their average

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 action in square 5 is up or left (they move toward terminal square 0), and the average of the four q values matches v(5) of about -18 up to simulation noise. A better policy would simply pick the best action every time, which is exactly what Policy Improvement will do.

Comparing policies

Policy pi is at least as good as pi' if v_pi(s) >= v_pi'(s) in every state. There is always at least one policy that is better than or equal to all others, the optimal policy, with value v*. We study it in Bellman Optimality.

flowchart LR
    pi["policy pi"] -->|"expected return from s"| v["v_pi(s)"]
    pi -->|"expected return from s, forced a"| q["q_pi(s, a)"]
    q -->|"average over pi(a|s)"| v

Common mistakes

  • Treating q(s, a) as "reward for action a". It is the entire future return after taking a, not just the next reward.
  • Forgetting that values belong to a policy. The same state has a different v under a different policy.
  • Estimating values from one episode. A single return is a sample; the value is its average over many.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does v_pi(s) represent?

    It is the expected discounted return starting from s and following pi thereafter.
  2. 2. How are v_pi and q_pi related?

    v_pi(s) = sum of pi(a|s) * q_pi(s, a).
  3. 3. Why does a model-free agent prefer to learn q instead of v?

    With q you pick argmax over actions directly; with v you would need the transition model to look one step ahead.
  4. 4. What is the value of a terminal state?

    Nothing happens after a terminal state, so the expected future return is 0.

Summary

  • A policy maps states to actions, deterministically or with probabilities.
  • v_pi(s) is the expected return from s under pi; q_pi(s, a) forces the first action a.
  • v_pi(s) equals the policy-weighted average of q_pi(s, a).
  • Values can be estimated by averaging simulated returns, which is the seed of Monte Carlo methods.
  • Better policies have values that are greater or equal in every state.

Next: Bellman Expectation Equations