Dynamic programming (value - policy iteration): Question bank

This is a conceptual stress-test for dynamic programming. No heavy arithmetic here — every item targets a place where intuition quietly goes wrong: a sign, a max-vs-average, a "does this need a model?", a degenerate MDP. Cover the reasoning, not just the label.

Before you start, three words we will lean on constantly, defined in plain language:

Keep the Bellman equations and the contraction mapping idea in mind — most traps below are really about one of those two.

True or false — justify

Value iteration needs the transition probabilities

p (s^{'}, r ∣ s, a)

to run.

True. Both DP algorithms are model-based: the sum

\sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [\dots]

literally requires knowing where each action lands you. Dropping the model is exactly what pushes you toward Q-learning and TD learning.

Policy iteration always takes more total computation than value iteration.

False. Policy iteration needs fewer outer iterations (it converges in a finite number of policy changes), but each one runs a full policy evaluation to convergence — so cost per iteration is higher. Which wins depends on the MDP; neither dominates universally.

γ = 1

, the Bellman update is still guaranteed to converge.

False in general. The convergence guarantee comes from the update being a

γ

-contraction; at

γ = 1

the contraction factor is 1, so it may not shrink errors. It can still work if the MDP is episodic (guaranteed to reach a terminal state), which caps the return.

Value iteration is just policy iteration with the policy-evaluation step cut down to a single sweep.

True. Value iteration = "improve after one backup instead of after full convergence." That single sweep with a

max

inside is a truncated evaluation fused with improvement.

Once policy iteration returns a policy that doesn't change, that policy might still be suboptimal.

False. If

π^{'} = π

after greedy improvement, then

π

is greedy w.r.t. its own value function, which is exactly the Bellman optimality condition — so

π

is optimal.

Two different optimal policies must have different optimal value functions.

False.

V^{*}

is unique, but many policies can achieve it (e.g. two actions tied for best in a state). Different arrows, same goodness scores.

The Bellman optimality equation is linear in

V

False. The

max_{a}

makes it non-linear (piecewise). The Bellman expectation equation (fixed policy, no max) is linear and can be solved directly by matrix inversion.

Adding a constant

c

to every reward leaves the optimal policy unchanged.

True for the policy, false for the values. Every state's value shifts by

c / (1 - γ)

(a state-independent constant), so the ranking of actions — and hence the argmax — is untouched.

Spot the error

V^{*} (s) = max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ max_{a^{'}} V^{*} (s^{'})]

Error: there is an extra

max_{a^{'}}

that doesn't belong.

V^{*} (s^{'})

is already a maximised value; the only

max

is the outer one over the current action

a

. The inner term is just

[r + γ V^{*} (s^{'})]

"Policy improvement uses

ar g max_{a} Q^{π} (s, a)

, so it needs the optimal

Q^{*}

Error: it uses

Q^{π}

of the current policy, not

Q^{*}

. Being greedy w.r.t. the current (imperfect) values is enough to guarantee a not-worse policy — that's the whole point of the improvement theorem.

V^{π} (s) = max_{a} \sum_{a} π (a ∣ s) \dots

" — expectation equation with a max in it.

Error: the expectation equation averages over actions with weights

π (a ∣ s)

; there is no

max

. Mixing in a

max

turns it into the optimality equation for a different (greedy) policy.

"Since rewards are

- 1

per step, values must be negative, so

V (0, 0) = + 20

is fine."

Error: with per-step reward

- 1

and no positive reward anywhere, every non-terminal value is negative. A positive value is impossible;

V (0, 0)

should be around

- 20

, not

+ 20

"We can extract the greedy policy from

V

without the model, since we already have

V

Error: turning

V

into a policy needs

ar g max_{a} \sum_{s^{'}, r} p (\cdot) [r + γ V (s^{'})]

— that one-step look-ahead uses

p

V

alone isn't enough; that's why model-free methods learn

Q

instead.

"In value iteration we must keep an explicit policy updated every sweep."

Error: value iteration keeps no explicit policy during iteration. The

max

implicitly picks the best action; you only extract

π^{*}

once, at the end.

"The discount

γ

is there to make rewards smaller for no real reason."

Error:

γ < 1

does two real jobs — it models preference for sooner rewards, and it guarantees the return is a finite number and the Bellman operator is a contraction, which is what makes DP converge at all.

Why questions

Why does the Bellman expectation update converge to a unique answer?

Because the update is a

γ

-contraction: each sweep multiplies the worst-case error by

γ < 1

, so errors shrink geometrically toward a single fixed point

V^{π}

Why does value iteration use

max_{a}

where policy evaluation uses

\sum_{a} π (a ∣ s)

Value iteration is chasing

V^{*}

, and an optimal agent always picks the single best action — so we maximise. Policy evaluation is scoring a given (possibly stochastic) policy, so we average with that policy's own probabilities.

Why is DP called "dynamic programming" if there's nothing dynamic about the code?

"Programming" here means tabular planning (Bellman's 1950s usage), and "dynamic" refers to the sequential, multi-stage structure — solving small subproblems (one step from the goal) and reusing them for larger ones.

Why does policy iteration converge in finitely many steps but value iteration only in the limit?

Policy iteration walks through a finite set of deterministic policies, each strictly better than the last, so it must stop. Value iteration refines a continuous-valued

V

by a

γ

factor each sweep, which approaches

V^{*}

but reaches it exactly only as sweeps

\to \infty

Why do we discount future rewards by

γ^{k}

and not by a fixed subtraction?

A multiplicative

γ^{k}

keeps the infinite sum finite (geometric series) and makes the "value tomorrow" telescope cleanly into the recursion; a fixed subtraction would let the sum diverge and would break the one-step recursion.

Why can policy improvement never make the policy worse?

The policy improvement theorem: acting greedily for one step and then following the old policy already scores

\geq V^{π}

everywhere; iterating that guarantee across all states shows

V^{π^{'}} \geq V^{π}

pointwise.

Why does understanding DP matter if it needs a perfect model we rarely have?

DP is the definition of correct that model-free methods approximate — Q-learning, SARSA, and policy gradients are all "DP without the model," so its equations tell you what those samplers are secretly estimating.

Edge cases

What is

V^{π}

at a terminal state?

Zero (by convention): no future rewards can be collected from a terminal state, so its backup contributes nothing and it anchors the recursion for every other state.

What happens if two actions have exactly equal

Q

-values in a state?

Any tie-breaking rule is valid — both are optimal. This is why

π^{*}

can be non-unique even though

V^{*}

is unique; pick either arrow.

What does value iteration do in a state where every action leads back to the same state with the same reward (a self-loop trap)?

The backup becomes

V (s) = r + γ V (s)

, giving

V (s) = r / (1 - γ)

— a well-defined value only because

γ < 1

; at

γ = 1

it would blow up (or stay undefined) for negative

r

What if the initial value function

V_{0}

is chosen adversarially, say huge and wrong?

It still converges. The contraction shrinks any starting error by

γ

per sweep, so the fixed point

V^{*}

is reached regardless of

V_{0}

— a bad start only costs extra sweeps.

What if a policy assigns zero probability to the optimal action in some state?

Policy evaluation faithfully scores that suboptimal policy (its

V^{π}

is genuinely lower there), and the very next improvement step will shift probability onto the better action — that's the mechanism that escapes bad policies.

What happens in an MDP with unreachable states?

Their values are still computed and are internally consistent, but they never influence the reachable part of the world; the optimal policy over reachable states is unaffected by them.

γ = 0

, what does the optimal policy become?

Purely greedy on immediate reward: with

γ = 0

the backup is just

max_{a} E [r]

, so the agent ignores all future consequences and grabs the best one-step reward — myopic but still well-defined.

Recall Quick self-check

The extra $max$ in the optimality equation belongs to which action? ::: The current action $a$ only; $V^{*} (s^{'})$ is already maximised. DP needs which piece of information that model-free RL does without? ::: The transition/reward model $p (s^{'}, r ∣ s, a)$ . What single property guarantees DP converges? ::: The Bellman operator is a $γ$ -contraction.