Markov Decision Processes (MDP): Question bank

The pieces we lean on everywhere: a state $s$ (where you are), an action $a$ (what you choose), the transition probability $P (s^{'} ∣ s, a)$ (the dice the environment rolls), the reward $R$ (the number that says "good/bad"), the discount $γ$ (how much a future reward is worth today), the value $V^{π} (s)$ (expected total discounted reward if you start at $s$ and obey policy $π$ ), and the action-value $Q^{π} (s, a)$ (same, but you're forced to take $a$ first). Keep those seven meanings in your pocket.

True or false — justify

The Markov property means the agent has no memory of past states.

False. The environment's next state depends only on the current state–action pair; the agent may still record history — but only by folding it into the state so the state stays a complete summary.

If two different histories lead to the same state, the optimal action is identical in both.

True — that is exactly what "the state is a sufficient statistic" buys you. If the best action truly differed, the state was hiding information and should have been enriched.

A larger discount factor

γ

always yields a larger value

V^{π} (s)

False in general. With negative rewards along the way, a larger

γ

can lower value by weighting those penalties more;

γ

scales all future rewards, good and bad alike.

Setting

γ = 0

makes the agent ignore the future entirely.

True. Then

G_{t} = R_{t + 1}

only, so

V^{π} (s)

equals the expected immediate reward — the agent becomes purely greedy for the next step.

γ = 1

is always allowed in the MDP definition.

False for infinite-horizon tasks; the definition requires

γ \in [0, 1)

so the geometric bound

R_{m a x} / (1 - γ)

stays finite.

γ = 1

is only safe when every episode is guaranteed to terminate.

Rewards must be non-negative for the theory to work.

False. Rewards can be any real number; convergence depends on boundedness (

∣ R ∣ \leq R_{m a x}

) and

γ < 1

, not on sign. Penalties are just negative rewards.

Every MDP has a unique optimal policy.

False. The optimal value

V^{*}

is unique, but ties in

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

mean several policies can all be optimal — they just achieve the same value.

V^{π} (s) = Q^{π} (s, π (s))

holds for any policy, optimal or not.

True by definition: following

π

from

s

is taking

π (s)

first and then following

π

, which is precisely what

Q^{π} (s, π (s))

measures.

Q^{*} (s, a_{1}) = Q^{*} (s, a_{2})

, choosing either action keeps you optimal.

True at that state — both are

ar g max

actions. Optimality is about matching

V^{*}

, and both actions deliver it.

A deterministic policy can be optimal even when transitions are stochastic.

True. Stochasticity lives in

P (s^{'} ∣ s, a)

, the environment; there always exists a deterministic optimal policy for a finite MDP because we only need the single best action per state.

Spot the error

V^{π} (s) = R_{t + 1} + γ V^{π} (s^{'})

— value equals reward plus discounted next value."

Missing the expectation/sum over

s^{'}

. Because

s^{'}

is random, the correct form is

V^{π} (s) = \sum_{s^{'}} P (s^{'} ∣ s, π (s)) [R + γ V^{π} (s^{'})]

; a single

s^{'}

ignores every other possible outcome.

V^{*} (s) = \sum_{a} π (a ∣ s) Q^{*} (s, a)

— average the Q-values over the policy."

Wrong for the optimal value: it uses

max_{a}

, not an average.

V^{*} (s) = max_{a} Q^{*} (s, a)

. The averaging form is only for a fixed stochastic policy

V^{π}

, not for

V^{*}

"The Bellman optimality equation is linear, so we can solve it directly like Example 1."

The

max_{a}

makes it non-linear. The policy-evaluation equation (fixed

π

) is linear and solvable by substitution; the optimality equation needs iteration (see 5.2.01-Dynamic-Programming-inRL).

G_{t} = R_{t} + γ R_{t + 1} + \dots

— the return starts at the current reward

R_{t}

Off by one. The return counts rewards received after time

t

G_{t} = R_{t + 1} + γ R_{t + 2} + \dots

R_{t}

was the reward for arriving at

S_{t}

and belongs to

G_{t - 1}

"To get

π^{*}

we compute

ar g max_{a} V^{*} (s^{'})

over next states."

You maximise over actions, not next states, and you need the whole expected return:

π^{*} (s) = ar g max_{a} \sum_{s^{'}} P (s^{'} ∣ s, a) [R + γ V^{*} (s^{'})]

, i.e.

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

"Since

s_{3}

gives

+ 10

each step,

V^{π} (s_{3}) = 10

It's a self-loop collecting

+ 10

forever, so

V^{π} (s_{3}) = 10 + γ V^{π} (s_{3}) = 10/ (1 - γ) = 100

γ = 0.9

. The single reward gets amplified by the infinite geometric tail.

P (s^{'} ∣ s, a)

is a reward, so bigger

P

means better."

P

is a probability that sums to

1

over

s^{'}

; it says how likely, not how good. Goodness lives in

R

and downstream

V

Why questions

Why do we take an expectation in

V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]

Because transitions

P (s^{'} ∣ s, a)

(and possibly the policy) are random, so

G_{t}

is a random variable. A single number must summarise all possible futures — the average return does exactly that.

Why does the discount factor guarantee a finite value even over an infinite horizon?

With

∣ R ∣ \leq R_{m a x}

and

γ < 1

, the return is bounded by the geometric series

\sum_{k} γ^{k} R_{m a x} = R_{m a x} / (1 - γ)

, which converges. Without

γ < 1

the sum could diverge.

Why is

V^{*} (s) = max_{a} Q^{*} (s, a)

rather than an average over actions?

Because

V^{*}

assumes you act optimally — you get to pick the single best action, not be forced into a mixture. Averaging would describe a suboptimal (or fixed) policy instead.

Why can we write

V^{π} (s) = E [R_{t + 1} + γ V^{π} (S_{t + 1})]

— where did the infinite tail go?

The Markov property lets the entire future return from

S_{t + 1}

collapse into one symbol

V^{π} (S_{t + 1})

. This self-reference is the whole point of the Bellman equation: it turns an infinite sum into one recursive line.

Why encode goals as rewards rather than hard rules?

Numbers let the agent trade off competing objectives and uncertainty on a common scale, and let optimisation (max expected return) discover behaviour automatically. Hard rules can't express "somewhat good" or handle stochastic outcomes.

Why does stochasticity in "right succeeds 80%" lower the value versus the deterministic case?

A chance of staying put wastes a step and postpones the reward, so the discounted expected return shrinks. Uncertainty about reaching the goal always costs you discount factors.

Edge cases

What is

V^{π}

of a terminal state whose only transition is a zero-reward self-loop?

V^{π} = 0 + γ V^{π} \Rightarrow V^{π} (1 - γ) = 0 \Rightarrow V^{π} = 0

. No reward ever arrives, so the state is worth nothing regardless of

γ

If every action from a state has identical

Q^{*}

, what does

π^{*}

do there?

Any action is optimal — the

ar g max

set is the whole action set. The state is a "don't care"; all choices reach

V^{*}

What happens to

V^{π} (s_{3}) = 10/ (1 - γ)

γ \to 1^{-}

It blows up to

+ \infty

. This is exactly why the definition forbids

γ = 1

for non-terminating loops: the reward stream never stops, so total value diverges.

For a one-state MDP with a single self-loop of reward

r

, what is

V^{π}

V^{π} = r + γ V^{π} = r / (1 - γ)

. It's the closed form for a reward collected forever, the simplest instance of the whole Bellman machinery.

If two states are indistinguishable to the agent (same observations) but require different actions, is it a valid MDP?

Not as stated — the "state" isn't Markov because it fails to summarise the true situation. You must enrich the state (add the distinguishing info) or you have a partially-observable problem, not an MDP.

What does the Bellman equation reduce to when transitions are deterministic?

The sum over

s^{'}

collapses to a single term:

V^{π} (s) = R (s, π (s), s^{'}) + γ V^{π} (s^{'})

, since

P (s^{'} ∣ s, π (s)) = 1

for exactly one

s^{'}

. This is why Example 1 back-substitutes so cleanly.

Recall Quick self-check

The optimality equation is non-linear because of what operator? ::: The $max_{a}$ over actions. $V^{π} (s)$ equals $Q^{π} (s, ?)$ for which action? ::: $π (s)$ , the action the policy prescribes. Terminal zero-reward self-loop has what value? ::: $0$ .

See also: 5.1.03-Policy-and-Value-Functions, 5.1.04-Bellman-Equations, 5.4.01-Q-Learning, and the chain-theory prerequisite Markov-Chains.