Dynamic Programming in RL

You know the rules of the game, so you work backward from the end instead of playing thousands of practice rounds. Each state's value comes from its successors.

One Bellman backup at state s weighs every action and successor by its probability, giving Q of 10.52 for a1 and 9.10 for a2

Why Does This Exist?

Planning $T$ steps ahead with $|\mathcal{A}|$ actions means $|\mathcal{A}|^T$ possible futures. With 4 actions and 20 steps that is over a trillion paths. You cannot enumerate them.

Dynamic programming breaks the giant problem into one-step pieces. If you already know the value of every successor state, the value of the current state is just the best probability-weighted mix of reward plus discounted successor value. Sweep that backup across all states and the values settle to the optimum.

This page covers planning with a perfect model. Markov decision processes define the model, value functions store the cached answers, and temporal-difference learning learns the same answers without a model. If you can write down transition probabilities, start here. If you can only sample experience, start with model-free methods instead.

The one idea you need first

A model means two tables. $P(s' \mid s, a)$ says how likely each successor $s'$ is after action $a$ in state $s$ , and $R(s, a, s')$ says the immediate reward on that branch. The discount $\gamma$ in $[0, 1)$ says future reward counts a bit less than present reward. The full setup lives in Markov decision processes.

Think of It Like This

A subway map with travel times already filled in

You stand at one station and want the fastest route downtown. Taped to the wall is a map where every station already has a number: minutes to downtown from there.

You do not ride every line to find out. For each line out of your station you add the ride time plus the posted number at the station where you get off, weighting by how often that line stalls or reroutes. Pick the smallest total. Then you write your station's new number on the map. Repeat for every station and the whole map sharpens.

Where it stops: real subway delays are not listed in a clean table. Dynamic programming needs that table to be complete and correct.

How It Actually Works

For a fixed policy $\pi$ , where $\pi(a \mid s)$ is the chance of picking action $a$ in state $s$ , the Bellman expectation backup averages over actions and successors:

V_{k+1}(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a) [R(s, a, s') + \gamma V_k(s')]

For the optimal policy the average over actions becomes a max. That is the Bellman optimality backup:

V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s, a) [R(s, a, s') + \gamma V_k(s')]

In plain words: each action gets a Q value $Q(s, a)$ equal to its expected one-step reward plus discounted future value, and the state takes the best Q. Both backups are $\gamma$ contractions, so repeated sweeps converge to one fixed point from any start. That is why the method does not depend on the initial guess.

Policy iteration alternates full evaluation with greedy improvement. Value iteration skips the inner loop and applies the max backup every sweep. Same operator, different schedule.

Worked example

Take $\gamma = 0.9$ at state $s$ with two actions. Action $a_1$ branches to $s'_1$ with probability 0.8 (reward 2.0, cached $V = 10.0$ ) and to $s'_2$ with probability 0.2 (reward 5.0, cached $V = 4.0$ ). Action $a_2$ goes to $s'_3$ with probability 1.0 (reward 1.0, cached $V = 9.0$ ).

Branch targets add reward to discounted successor value:

G_1 = 2.0 + 0.9 \times 10.0 = 11.0

G_2 = 5.0 + 0.9 \times 4.0 = 8.6

Weight by probability for $a_1$ :

Q(s, a_1) = 0.8 \times 11.0 + 0.2 \times 8.6 = 8.80 + 1.72 = 10.52

For $a_2$ there is one branch:

Q(s, a_2) = 1.0 \times [1.0 + 0.9 \times 9.0] = 9.10

The optimality backup takes the max:

V(s) = \max(10.52, 9.10) = 10.52, \quad \pi(s) = a_1

No sampling happened. Every number came from the model table plus cached successor values.

Code

A Bellman backup is a probability-weighted sum, not a loop over episodes. This snippet computes the two Q values above.

1def bellman_q(probs: list, rewards: list, values: list, gamma: float) -> float:2    total: float = 0.0  # expected return for one action3    for p, r, v in zip(probs, rewards, values):4        total += p * (r + gamma * v)5    return total6
7
8q1 = bellman_q([0.8, 0.2], [2.0, 5.0], [10.0, 4.0], 0.9)9q2 = bellman_q([1.0], [1.0], [9.0], 0.9)10print(f"{q1:.2f} {q2:.2f} {max(q1, q2):.2f}")11# -> 10.52 9.10 10.52

The printed triple is $Q(s, a_1)$ , $Q(s, a_2)$ , and the backed-up $V(s)$ . It matches the hand computation.

Watch Out For

Running DP without a true model

The backup sums over $P(s' \mid s, a)$ for every successor. If you do not have those probabilities, the sum has nothing to iterate over. Plugging in guessed tables gives exact answers to the wrong environment, and the policy looks confident while failing in the real one.

If you only have sampled transitions $(s, a, r, s')$ , use temporal-difference learning or Monte Carlo methods. They learn from samples and never need the full table.

Sweeping every state in a huge space

One sweep touches every state, every action, and every successor. When the state count grows with each new sensor or attribute, the table outgrows memory long before the values converge. The math still contracts, but you cannot store the vector.

Fix it by backing up only visited states, as in real-time methods, or by replacing the table with a parameterized approximator. Do not run full tabular sweeps past a few thousand states.

The Quick Version

Dynamic programming plans with a known model by turning Bellman equations into update rules.
Each backup mixes immediate reward with discounted cached successor values across every branch.
The update is a gamma contraction, so repeated sweeps converge from any start.
Policy iteration separates evaluation and improvement while value iteration merges them into one max backup.
It needs exact transition probabilities and it scans the full state space, so it fits small tabular problems and grounds every sample-based method.