MDP & Bellman Equations

An MDP (Markov Decision Process) models sequential decisions as a 5-tuple $(S, A, P, R, \gamma)$: $S$ states, $A$ actions, $P(s'|s,a)$ transition probabilities, $R(s,a)$ immediate rewards, and $\gamma \in [0,1)$ discount factor. The Bellman optimality equation captures self-consistency (optimal substructure) of the optimal value function: $V^*(s) = \max_a \left[ r(s,a) + \gamma \sum_{s'} P(s'|s,a) V^*(s') \right]$, where $r(s,a)$ is the immediate reward, $\max_a$ takes the best action, $\sum_{s'} P(s'|s,a) V^*(s')$ is the transition-weighted expectation over successor states, and $\gamma$ discounts future rewards. The Q-version is $Q^*(s,a) = r(s,a) + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q^*(s',a')$ with $\max_{a'} Q^*(s',a')$ the optimal expected value at the next state; the two are linked by $V^*(s) = \max_a Q^*(s,a)$.

the modeling starting point of every RL problem — robot control, game AI, recommender systems, and LLM reasoning RL (RLVR) all frame decisions as MDPs; interviews ask for the 5-tuple, the role of $\gamma$, and the derivation of the Bellman equations in both V and Q forms.

it formalizes sequential decisions with long-term consequences into a computable dynamic-programming problem — the Bellman equation decomposes the global optimum into "best current action + optimal substructure", making $V^*$ the fixed point of a contraction operator $T$ ($V^* = TV^*$), approximable by iterative algorithms such as VI/PI/TD/Q-learning — the shared theoretical foundation of all RL algorithms.

Write the MDP 5-tuple and explain each element. What role does the discount γ play?

Derive and write out the Bellman optimality equations for V* and Q*, explaining every term.

How are V* and Q* related? Why does the Bellman equation embody "optimal substructure"?

Difference between the Bellman expectation and optimality equations? How is Vπ defined for a given policy π?

Why does γ < 1 guarantee a bounded, convergent value function? What happens at γ = 1 or γ = 0?