Bellman Equations

V(s), Q(s,a), optimality equations, contraction mapping, curse of dimensionality

Consider a 4×4 grid world with γ = 0.9. You want to know: what is the expected total reward — the value — of being at position (2,3) if you follow the optimal policy? To answer this, you need to know the value of neighboring positions, because your value here depends on where you can move next. But those values depend on their neighbors too. The circular dependency seems impossible to resolve — yet this is exactly what the Bellman equations do: they express the value of a state as a function of the values of its successors, turning a circular problem into a recursive one with a guaranteed fixed point.

The state value function under a policy π is V^π(s) = E_π[R_{t+1} + γ V^π(S_{t+1}) | S_t = s]. The value of a state equals immediate expected reward plus discounted expected value of the next state. This is the Bellman expectation equation — self-consistent, recursive, and for a fixed policy, linear enough to solve directly.

The optimal value function is V*(s) = max_a [R(s,a) + γ Σ_{s'} P(s'|s,a) V*(s')]. The value of the best possible policy equals the action that maximizes immediate reward plus discounted future value. The action-value function Q*(s, a) = R(s,a) + γ Σ_{s'} P(s'|s,a) max_{a'} Q*(s', a') is more practically useful: it tells you the value of taking action a in state s and then acting optimally, which means you can select actions directly via argmax_a Q*(s, a) without needing to model transitions.

Value iteration starts with an arbitrary value estimate and repeatedly applies the Bellman operator until convergence. Contraction mapping theory guarantees this converges to V* for finite MDPs. Policy iteration alternates between evaluating the current policy exactly and then improving it greedily. Both are guaranteed to find the optimal policy — but only in the tabular case.

NOT this: you need to know the transition model T(s, a, s') to use Bellman equations. Model-based RL uses the equations directly with a known or learned T. Model-free RL — Q-learning, TD learning — uses samples to estimate the Bellman updates without ever modeling T explicitly. The Bellman structure guides both approaches by telling you what quantity to estimate.

Key points

• Learn the Q-function Q*(s, a), not V*(s), for most RL applications. Q*(s, a) tells you which action to take directly — argmax_a Q*(s, a) — without needing transition probabilities. V*(s) tells you how good a state is but not what to do, so unless you have a model of transitions, V alone cannot produce a policy.
• Tabular Q-learning is infeasible for large or continuous state spaces — this is not a performance issue, it is a physical impossibility. A robot with 6 joint angles discretized at 100 positions per joint has 10^12 states. Storing a Q-table for this requires ~8 TB even at 8 bytes/entry — technically storable today, but wildly impractical to fill from experience (you would need to visit and revisit trillions of state-action pairs), and it only gets worse as joints or precision increase. The moment the state space is too large to enumerate, you need function approximation — neural networks — which breaks the convergence guarantee.
• If Q-values grow without bound during training, the Bellman backup is diverging due to a feedback loop between the prediction and the target. The target y = R + γ max Q_θ(s') depends on the same θ being updated, so each gradient step shifts both the prediction and the target. Fix this with a target network: freeze θ^- for K steps so the target is stationary, then copy θ into θ^-.

Recap

• Bellman turns circular value estimation into a recursive fixed point.
• Expectation eq: $V^\pi(s) = E_\pi[R_{t+1} + \gamma V^\pi(S_{t+1})]$ — linear for a fixed policy.
• Optimality eq is nonlinear because of the `max` operator: $V^*(s) = \max_a[R + \gamma \sum P(s'|s,a)V^*(s')]$.
• Learn $Q^*(s,a)$, not $V^*$: `argmax_a Q` gives the action with no transition model needed.
• Value/policy iteration converge via contraction mapping — but only in the tabular case.
• Tabular is a physical impossibility at scale: 6 joints × 100 positions = $10^{12}$ states. Need function approximation.
• Unbounded $Q$ during training = diverging Bellman backup. Fix with a frozen target network.

Check your understanding