Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Value functions and the Bellman equation

Value functions summarise expected returns in an MDP; the Bellman equations relate a state's value to immediate reward plus discounted value of successor states and are the basis for evaluation and control algorithms (policy evaluation, policy iteration, value iteration).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Value functions and the Bellman equation are central to Reinforcement Learning and Markov Decision Processes (MDPs). An engineer uses these when designing agents that must make sequential decisions (robotics, resource allocation, recommendation over time) because the Bellman equations give the recursive relationships that let us compute or approximate the best long‑term behaviour.

Key ideas

Start with basic terms and assumptions (define before use).

  • Markov Decision Process (MDP): a tuple (S, A, P, R, γ) where S is a set of states, A is a set of actions, P is the transition probability function, R is the reward function, and γ ∈ [0,1) is the discount factor. Assumption used here: finite S and A unless stated otherwise. We will also use p(s', r | s,a) to denote the joint distribution over next state and reward induced by P and R.

  • Policy (π): a mapping from states to a probability distribution over actions. If π(a|s) = 1 for a single a, the policy is deterministic.

  • Return (G_t): the total (possibly discounted) reward from time t: G_t = R_{t+1} + γR_{t+2} + γ^2 R_{t+3} + ... . Assumes rewards R_t are bounded so the series converges when γ<1. For episodic (finite-horizon) tasks that terminate almost surely, setting γ=1 is also valid since the sum is finite.

  • State-value function (v_π): the expected return when starting in state s and following policy π thereafter. Formally v_π(s) = E_π[G_t | S_t = s].

  • Action-value function (q_π): expected return after taking action a in state s and then following π: q_π(s,a) = E_π[G_t | S_t=s, A_t=a].

Derivation of the Bellman expectation equation for v_π (step-by-step):

  1. Start from definition v_π(s) = E_π[G_t | S_t=s].
  2. Use the definition of G_t: G_t = R_{t+1} + γ G_{t+1}.
  3. Substitute: v_π(s) = E_π[R_{t+1} + γ G_{t+1} | S_t=s].
  4. Linearity of expectation: v_π(s) = E_π[R_{t+1} | S_t=s] + γ E_π[G_{t+1} | S_t=s].
  5. Expand the second term by conditioning on next state and action chosen under π: E_π[G_{t+1} | S_t=s] = E_{a∼π(·|s)}[ E_{s',r∼p(·,·|s,a)}[ v_π(s') | S_t=s, A_t=a ] ].
  6. Collect to obtain the standard Bellman expectation equation: v_π(s) = Σ_a π(a|s) Σ_{s',r} p(s',r | s,a) [ r + γ v_π(s') ].

This is an exact linear equation (one per state). In matrix-vector form for finite MDPs it becomes (I − γP^π) v_π = r^π, where P^π and r^π are the policy-dependent transition and expected reward matrices/vectors.

Bellman optimality equation (for the optimal value function v*):

  • Bellman optimality equation: v*(s) = max_a Σ_{s',r} p(s',r | s,a) [ r + γ v*(s') ]. This is non-linear (contains max) and characterises the fixed point v* (the optimal value for each state). Once v* is known, an optimal deterministic policy is π*(s) ∈ argmax_a Σ_{s',r} p(s',r | s,a) [ r + γ v*(s') ].

Bellman operators and contraction (important theorem):

  • Define the Bellman expectation operator T_π by (T_π v)(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [ r + γ v(s') ].
  • Theorem (Contraction): For γ ∈ [0,1), T_π is a contraction mapping on the space of bounded value functions with respect to the sup norm: ||T_π v − T_π w||∞ ≤ γ ||v − w||∞. Consequence: there is a unique fixed point v_π and iterative application v_{k+1} = T_π v_k converges to v_π. Similarly, the Bellman optimality operator T* defined below is also a γ-contraction under the sup norm, with unique fixed point v*, so value iteration v_{k+1} = T* v_k converges to v*. Proof sketch: use triangle inequality and properties of expectation; the factor γ appears because only the future value terms are multiplied by γ.

Algorithms that use these equations (high level):

  • Policy evaluation: solve (I − γP^π) v = r^π exactly (linear solve) or approximately by iterative application v ← T_π v until convergence.
  • Policy improvement: given v_π compute π'(s) = argmax_a Σ_{s',r} p(s',r|s,a) [ r + γ v_π(s') ].
  • Policy iteration: alternate evaluation and improvement to reach optimal policy.
  • Value iteration: repeatedly apply the Bellman optimality operator T* defined by (T* v)(s) = max_a Σ_{s',r} p(s',r|s,a) [ r + γ v(s') ] until convergence; v_{k+1} = T* v_k.

Diagram to draw for an exam question: draw a node labelled s. From s draw arrows to nodes s' labelled with transition probabilities p(s'|s,a) and write immediate rewards r on each arrow; also show the policy π(a|s) as a small table (state → action probabilities). Label γ near the recursive term to indicate discounting.

Formulas

G_t = R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + ... — G_t is the return from time t, R are rewards (unit: same as reward), γ is the discount factor (dimensionless). Applies when considering infinite-horizon discounted return.

v_π(s) = E_π[G_t | S_t = s] — v_π(s) is the state-value under policy π (units: reward units). Applies for any policy π.

q_π(s,a) = E_π[G_t | S_t = s, A_t = a] — action-value under policy π (units: reward units). Relation: v_π(s) = Σ_a π(a|s) q_π(s,a) and v*(s) = max_a q*(s,a).

v_π(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [ r + γ v_π(s') ] — Bellman expectation equation for v_π; p(s',r|s,a) is probability of next state s' and reward r given (s,a).

q_π(s,a) = Σ_{s',r} p(s',r|s,a) [ r + γ Σ_{a'} π(a'|s') q_π(s',a') ] — Bellman expectation equation for q_π.

v*(s) = max_a Σ_{s',r} p(s',r|s,a) [ r + γ v*(s') ] — Bellman optimality equation; v* is the optimal state-value function.

q*(s,a) = Σ_{s',r} p(s',r|s,a) [ r + γ max_{a'} q*(s',a') ] — Bellman optimality for q*.

(I − γ P^π) v_π = r^π — linear system form for finite MDPs; I is identity, P^π is state-to-state transition matrix under π, r^π is expected immediate reward vector (units: reward).

Worked examples

Example 1 — policy evaluation (small deterministic MDP). MDP: S={s1,s2}, single action in each state (so π is trivial). Rewards: taking the action in s1 gives immediate reward 5 and moves to s2; in s2 gives reward 2 and moves to s1. γ = 0.9. Compute v(s1) and v(s2). Steps:

  1. Write Bellman equations: v(s1) = 5 + 0.9 v(s2) v(s2) = 2 + 0.9 v(s1)
  2. Substitute v(s2) into first equation: v(s1) = 5 + 0.9 (2 + 0.9 v(s1))
  3. Evaluate numbers: v(s1) = 5 + 1.8 + 0.81 v(s1) => v(s1) − 0.81 v(s1) = 6.8 => 0.19 v(s1) = 6.8 => v(s1) = 6.8 / 0.19 = 35.78947368421053
  4. Then v(s2) = 2 + 0.9 * 35.78947368421053 = 34.21052631578947 Answer: v(s1) = 35.7895, v(s2) = 34.2105 (reward units). (Numbers rounded to 4 decimals.)

Example 2 — value iteration (small branching MDP). MDP: States s1 (start), s2, s3 (terminal). Actions and transitions:

  • At s1: a1 → s2 with reward 4; a2 → s3 with reward 2.
  • At s2: a1 → s3 with reward 3.
  • s3 is terminal: v(s3) = 0. Let γ = 0.5. Initialize v_0(s) = 0 for all s. Iterations:
  • k=1: v_1(s2) = max over actions = 3 + 0.50 = 3 v_1(s1) = max(4 + 0.50, 2 + 0.5*0) = max(4,2) = 4
  • k=2: v_2(s2) = 3 (unchanged) v_2(s1) = max(4 + 0.53, 2 + 0.50) = max(5.5, 2) = 5.5
  • k=3: v stabilises (v_3(s1) = 5.5, v_3(s2)=3) Answer: optimal values v*(s1)=5.5, v*(s2)=3, v*(s3)=0.

Common mistakes

  • Using γ ≥ 1 in infinite-horizon continuing problems — this generally breaks convergence; γ=1 is only safe in episodic/finite-horizon tasks (or when returns are otherwise finite).
  • Mixing up v and q: v(s) is over actions (expectation under π or max), q(s,a) includes the initial action.
  • Trying to invert (I − γ P^π) numerically when the matrix is large — iterative methods are required for big problems.
  • Treating terminal states incorrectly (they should have v = 0 or specified terminal value and no outgoing transitions).

For your exam

Types of questions you will see: definitions (define v_π, q_π, Bellman equation), short notes (derive Bellman expectation equation), derivations (prove contraction property), numericals (evaluate v for a small MDP), algorithms (explain value iteration / policy iteration), diagram‑based questions (draw MDP transitions and label rewards/probabilities). What a full‑marks answer includes:

  • For definitions: precise mathematical statement and short comments on assumptions (e.g., finite MDP, γ in [0,1)).
  • For derivations: start from definitions (v_π(s)=E[G_t|S_t=s]), show each expectation step, and justify interchange of sum/expectation.
  • For proofs (contraction): show norm inequality and the γ factor.
  • For numericals: write Bellman equations, solve algebraically or show iterative steps with numeric values and final answers to suitable precision.
  • If asked for algorithms: give the update rule (e.g., v <- T_π v or v <- T* v) and state convergence conditions.

Quick check

  1. State the Bellman expectation equation for v_π(s) in words.
  2. What changes in the Bellman equation when moving from v_π to v*?
  3. Why does iterative policy evaluation converge when γ < 1? Answers: 1) v_π(s) equals the expected immediate reward plus γ times expected value of next state under π. 2) Expectation over actions π(a|s) is replaced by a maximisation over actions (max_a) to give v*. 3) Because the Bellman operator is a contraction with factor γ<1, so repeated application converges to the unique fixed point.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?