MDPs, Returns, and Value Functions

A physics simulator already gives you the hard part of a decision problem: a step function that maps a state and an action to a next state. Add a scalar reward on each step and you have a Markov decision process. The first question is not how to act well but how to grade a fixed way of acting: given a policy, how good is each state? That grade is the value function, and computing it is policy evaluation. Choosing a better policy comes later; here we only measure.

The Markov decision process

An MDP is a tuple $(\mathcal{S}, \mathcal{A}, P, r, \gamma)$. The states $\mathcal{S}$ and actions $\mathcal{A}$ are the configurations and controls. The transition kernel

$$P(s' \mid s, a) = \Pr\{\, s_{t+1} = s' \mid s_t = s,\ a_t = a \,\}$$

is the simulator's step, promoted to a distribution to allow stochastic dynamics. The reward $r(s, a)$ is the scalar earned on that step, and $\gamma \in [0, 1)$ discounts the future. The defining assumption is Markov: $s_{t+1}$ depends on the past only through the current $(s_t, a_t)$, which is exactly what a state-based simulator guarantees.

A policy $\pi(a \mid s)$ is a distribution over actions in each state. Fix one and the MDP collapses to a Markov reward process: the dynamics $\sum_a \pi(a\mid s) P(s'\mid s,a)$ and the expected reward $\sum_a \pi(a\mid s)\, r(s,a)$ are both determined.

Return and value functions

The agent cares about the return, the discounted sum of future reward from time $t$,

$$G_t = \sum_{k=0}^{\infty} \gamma^{k}\, r_{t+k} = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots .$$

The factor $\gamma^k$ makes reward $k$ steps away worth $\gamma^k$ times as much, and keeps the sum finite whenever rewards are bounded. The state-value function is the expected return from a state under $\pi$,

$$V^{\pi}(s) = \mathbb{E}_{\pi}\!\left[\, G_t \mid s_t = s \,\right],$$

and the action-value function conditions on the first action as well,

$$Q^{\pi}(s, a) = \mathbb{E}_{\pi}\!\left[\, G_t \mid s_t = s,\ a_t = a \,\right].$$

The two are tied by the policy: averaging $Q^\pi$ over the action the policy would take recovers $V^\pi$,

$$V^{\pi}(s) = \sum_{a} \pi(a \mid s)\, Q^{\pi}(s, a) .$$

$V^\pi$ answers "how good is this state if I keep acting like $\pi$?", not "how good could this state be?". Those are different questions, and only the first is on the table until we start improving $\pi$.

The Bellman expectation equation

Split the return into the immediate reward and the discounted return from the next state, $G_t = r_t + \gamma G_{t+1}$. Taking expectations under $\pi$ turns this recursion into a linear equation in $V^\pi$:

$$V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \Big[\, r(s, a) + \gamma\, V^{\pi}(s') \,\Big].$$

This is the Bellman expectation equation.¹ It is not a maximization: there is no $\max$ over actions, only an average over the actions the fixed policy actually takes and over the successors the dynamics actually produce. The action-value form is the same statement one step in,

$$Q^{\pi}(s, a) = \sum_{s'} P(s' \mid s, a) \Big[\, r(s, a) + \gamma \sum_{a'} \pi(a' \mid s')\, Q^{\pi}(s', a') \Big].$$

Policy evaluation

Write the right-hand side as an operator $T^{\pi}$ acting on a value estimate $V$,

$$(T^{\pi} V)(s) = \sum_{a} \pi(a\mid s) \sum_{s'} P(s'\mid s,a) \big[\, r(s,a) + \gamma\, V(s') \,\big].$$

$V^\pi$ is its fixed point, $T^{\pi} V^\pi = V^\pi$. Because $\gamma < 1$, the operator is a contraction in the max norm,

$$\lVert T^{\pi} V - T^{\pi} U \rVert_\infty \le \gamma\, \lVert V - U \rVert_\infty ,$$

so the iteration $V_{k+1} = T^{\pi} V_k$ from any starting $V_0$ converges to the unique $V^\pi$ at rate $\gamma$. That iteration is iterative policy evaluation: repeatedly apply the Bellman expectation update until $V$ stops moving.

Worked example: a three-state chain

Take three states $A, B, C$ with $C$ terminal, so $V(C) = 0$ always, and $\gamma = 0.9$. Fold a fixed policy into the dynamics so each state has a known transition and reward:

$$\begin{aligned} A &\to B \ \text{w.p. } 1,\ \ r = -1, \\ B &\to C \ \text{w.p. } 0.5,\ r = +10 \quad\text{or}\quad B \to A \ \text{w.p. } 0.5,\ r = -1, \\ C &: \text{terminal}. \end{aligned}$$

Start from $V_0 = (0, 0, 0)$ and apply $T^\pi$. The first sweep uses only immediate rewards, since every $V_0(s') = 0$:

$$\begin{aligned} V_1(A) &= -1 + 0.9\,V_0(B) = -1, \\ V_1(B) &= 0.5\,(10 + 0.9\,V_0(C)) + 0.5\,(-1 + 0.9\,V_0(A)) = 5 - 0.5 = 4.5 . \end{aligned}$$

The second sweep feeds $V_1$ back in, so value now flows one hop:

$$\begin{aligned} V_2(A) &= -1 + 0.9\,(4.5) = 3.05, \\ V_2(B) &= 0.5\,(10) + 0.5\,(-1 + 0.9\,(-1)) = 5 - 0.95 = 4.05 . \end{aligned}$$

$V(A)$ has moved $0 \to -1 \to 3.05$ and $V(B)$ has settled $0 \to 4.5 \to 4.05$, both heading for the exact fixed point. Solving $T^\pi V = V$ directly gives

$$V(A) = -1 + 0.9\,V(B), \qquad V(B) = 4.5 + 0.45\,V(A),$$

so $V(A) = 3.05 + 0.405\,V(A)$, hence $V(A) \approx 5.13$ and $V(B) \approx 6.81$. Two sweeps already land in the right neighborhood, and the $\gamma = 0.9$ contraction closes the rest of the gap geometrically.

Evaluation on a grid

The same update runs on a 2D gridworld MDP: every step costs $-1$, entering the goal pays $+10$, and the goal is terminal. Two fixed policies are on offer, a greedy walk toward the goal and the uniform-random walk. Neither is being improved. Iterative policy evaluation just applies $V \leftarrow r + \gamma\,\mathbb{E}_\pi[V']$ until convergence and reports how good each cell is under that one policy.

Policy evaluation on a gridworldinteractive

toward goalrandom

discount γ = 0.90sweep k = 11 / 11

max change |ΔV|

0.000

far corner V

-2.25

The greedy policy walks straight to the goal, so value stays high and drops off slowly. Drag k back to 0 to watch V spread out from the goal one sweep at a time.

Read the greedy field against the random one and the point is immediate: the value of a state is a property of the policy, not of the state alone. The random walk reaches the same goal but pays the step cost far longer, so its $V^\pi$ is uniformly lower. Deciding which policy is better, and how to construct the best one, is the optimization problem the Bellman optimality equation takes up next.

Footnotes

1. Sutton & Barto, Reinforcement Learning: An Introduction (2018). ↩