Dynamic Programming and the Bellman Equation

Optimal control and reinforcement learning look like separate fields, but they optimize the same object: a value function that satisfies the Bellman equation. The gap between them is not the equation, it is the information. Control knows the model (the dynamics $f$ and the cost $c$) and solves the equation offline by dynamic programming. RL does not know the model and estimates the same solution from sampled transitions. This chapter builds that shared object from the control side and points at where RL picks it up.

The principle of optimality

Fix a deterministic system with state $s$, action $a$, dynamics $s' = f(s,a)$, and nonnegative stage cost $c(s,a)$. A policy $\pi$ maps states to actions, and its discounted cost-to-go from $s_0$ is

$$V^{\pi}(s_0) \;=\; \sum_{t=0}^{\infty} \gamma^{t}\, c\big(s_t,\, \pi(s_t)\big), \qquad s_{t+1} = f\big(s_t,\, \pi(s_t)\big),$$

with discount $\gamma \in (0,1]$. The optimal value is $V^{\star}(s) = \min_{\pi} V^{\pi}(s)$. Bellman's principle of optimality says an optimal trajectory has optimal tails: whatever the first action does, the remaining decisions must themselves be optimal from the state it lands in.¹ That single observation collapses a search over whole action sequences into a search over one action plus the already-solved value of the successor.

The Bellman equation

Written out, the principle is a fixed-point condition that $V^{\star}$ must obey at every state:

$$V^{\star}(s) \;=\; \min_{a}\Big[\, c(s,a) \;+\; \gamma\, V^{\star}\big(f(s,a)\big) \,\Big].$$

The minimizer is the optimal policy, read off greedily once $V^{\star}$ is known:

$$\pi^{\star}(s) \;=\; \arg\min_{a}\Big[\, c(s,a) + \gamma\, V^{\star}\big(f(s,a)\big) \,\Big].$$

Reinforcement learning writes the identical statement with rewards instead of costs and a maximization instead of a minimization,²

$$V^{\star}(s) \;=\; \max_{a}\Big[\, r(s,a) + \gamma\, \mathbb{E}_{s' \sim P(\cdot \mid s,a)}\, V^{\star}(s') \,\Big].$$

Setting $r = -c$ turns one into the other, since $\max(-c) = -\min(c)$; the expectation just handles stochastic dynamics, which collapse to $s' = f(s,a)$ in the deterministic control case. It is one equation, one fixed point.

Value iteration

Read the Bellman equation as an operator $\mathcal{T}$ acting on value functions, $(\mathcal{T}V)(s) = \min_{a}[\,c(s,a) + \gamma\, V(f(s,a))\,]$, and iterate it: $V_{k+1} = \mathcal{T} V_{k}$. For $\gamma < 1$ this operator is a contraction in the sup norm,

$$\lVert \mathcal{T}V - \mathcal{T}W \rVert_{\infty} \;\le\; \gamma\, \lVert V - W \rVert_{\infty},$$

so by the Banach fixed-point theorem $V^{\star}$ is unique and any start converges to it geometrically, $\lVert V_k - V^{\star}\rVert_{\infty} \le \gamma^{k}\, \lVert V_0 - V^{\star}\rVert_{\infty}$. Concretely each sweep carries the correct cost-to-go one graph-step farther from the goal, so the values lock in ring by ring.

A four-state chain by hand

Take four states $s_0, s_1, s_2, s_3$ in a line. The goal $s_3$ is absorbing with cost $0$; from any interior state a move left or right costs $1$ (at the left edge, "left" stays put). Use $\gamma = 0.9$ and initialize $V_0 = +\infty$ everywhere except the goal. The update for an interior state is $V_{k+1}(s) = \min\{\,1 + \gamma V_k(s_{\text{left}}),\; 1 + \gamma V_k(s_{\text{right}})\,\}$.

Sweep 1 only $s_2$ (one step from the goal) can improve: $1 + 0.9(0) = 1$. Sweep 2 reaches $s_1$: $V_2(s_1) = \min\{1 + 0.9\, V_1(s_2),\; 1 + 0.9\, V_1(s_0)\} = \min\{1.9,\, \infty\} = 1.9$. Sweep 3 reaches $s_0$: $1 + 0.9(1.9) = 2.71$, and the next sweep changes nothing, so $V_3 = V^{\star}$. The fixed point is exactly the discounted shortest-path cost-to-go: a state $d$ steps from the goal has

$$V^{\star}(s_d) \;=\; \sum_{i=0}^{d-1} \gamma^{i} \;=\; \frac{1 - \gamma^{d}}{1 - \gamma},$$

which gives $1,\, 1.9,\, 2.71$ for $d = 1, 2, 3$. As $\gamma \to 1$ this tends to $d$, the raw number of steps, so with no discount value iteration recovers the plain shortest-path distance.

Watching the cost-to-go flood a grid

The same sweep on a 2D gridworld shows the ring-by-ring convergence directly. The goal has cost $0$; every other cell runs $V(s) \leftarrow \min_a[\,1 + \gamma\, V(s')\,]$ over its four neighbours. Slide $k$ and watch the accent flood outward from the goal, one ring per sweep, then read off the greedy policy that points down the gradient toward the goal (curving around the wall, because that is the cheaper route).

Value iteration on a gridworldinteractive

sweeps k = 0discount γ = 0.90

▶ playresetshow V

cells resolved

0 / 54

residual ‖ΔV‖∞

-

status

flooding…

Green is the goal (cost 0). Stronger accent means lower cost-to-go; blank cells are still at +∞, unreached by sweep 0. Arrows are the greedy policy: step toward the cheaper neighbour.

The same root, two fields

That grid is the bridge. Optimal control (this topic) has the model in hand, so it runs value iteration to convergence and gets $V^{\star}$ and $\pi^{\star}$ exactly, before ever touching the system. Reinforcement learning (the RL topic) faces the same Bellman fixed point without $f$ or $c$: it sees only sampled transitions $(s, a, r, s')$, so the expectation inside the operator becomes a sample average and the sweep becomes a stochastic, incremental update (Q-learning is value iteration on state-action values driven by samples). Same equation, same solution. The dividing line is whether you can compute the update or only estimate it.

Footnotes

1. Bertsekas, Dynamic Programming and Optimal Control. ↩

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