Foundations T19 / 27 · Decisions and Optimization
The Mathematical Construction of the MDP: What One Axiom Is Worth
All of reinforcement learning rests on a single axiom: the future depends only on the current state. Bellman's principle of optimality can be proven rigorously by contradiction — provided the «state» really does contain all the relevant information.
One-line takeaway
The Markov property is not a description but an assumption, and its payoff is this: the optimal policy decomposes into «choose well now + the remaining subproblem is also solved optimally» (Bellman's 1957 principle, provable by contradiction). When the state design leaks information, the applicability premise of this principle disappears — the first mathematical reason real-robot projects fail.
TD, Q-learning, and value iteration all assume the Bellman equations hold. The Bellman equations hold because of the Markov property. This page explains in one pass «why the five-tuple is defined this way», «why the optimality principle is true», and «what happens when the state leaks information» — it is the foundation page for /fund/mdp/.
Why this tool exists
Return to the definition itself. In the MDP five-tuple (S, A, P, R, γ), the load-bearing member is P: p(s'|s,a) depends only on the current state-action pair, not on history. Why does this one item deserve to be written into the definition separately? Because it is the source of every «recursion» that follows — the Bellman equation writes «the future's total account» as «the current step + the next state's total account», and this recursion only closes if the future does not remember history.
A counterexample is immediate: the robot observes only joint angles, but the actual position of the payload (unobserved) affects the dynamics. Then «the future» depends on the hidden payload position, and p(s'|s,a) cannot be written down in terms of the visible state — the future distribution associated with the same visible state varies with the hidden state. This is not an approximation error; the model itself is written wrong.
In his 1957 paper, Bellman wrote the «structure of the optimal policy» as a principle: an optimal policy has the property that — whatever the initial state and initial decision — the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision. This sentence can be proven by contradiction; the full proof follows.
Definitions
Definition 7.1 The MDP five-tuple
(S, A, P, R, γ): state set S, action set A, transition kernel P (Markovian), reward function R (generalizable to depend on s'), discount γ∈[0,1). A policy π maps states to actions (or action distributions).
Why define it this wayEvery component has a definite load-bearing position: S/A define the problem's vocabulary; P carries the Markov assumption; R defines «good»; γ both defines time preference and (in T5) guarantees convergence. Remove any one and the problem cannot even be formulated.
Definition 7.2 Return and value function
The discounted return of a trajectory G = Σt≥0 γ^t r_t. Value function V^π(s) = E_π[G | s_0=s] — the expectation is taken over the trajectory distribution induced by policy π and transition kernel P (T1's measure, T2's expectation, and T3's conditional expectation all converge here). Optimal value V*(s) = max_π V^π(s).
Why define it this wayNote the «conditioned on s» in the definition of V^π — that is exactly T3's conditional expectation; the legitimacy of «taking the expectation» is guaranteed by T2's integrability (the discounted sum is bounded when γ<1). The point of the principles layer is to let you see that these citation chains close.
Theorems and proofs
Theorem 7.1 Bellman's principle of optimality (proof by contradiction)
If π* is optimal, then in every state the action it chooses has «immediate reward + optimal value of the successor state» no worse than any other action. Equivalently: an optimal policy is (any) policy greedy with respect to V*.
Proof
Proof by contradiction. Suppose π* is optimal but in state s it takes action a₁, while there exists an action a₂ with r(s,a₂) + γE[V*(s')] > r(s,a₁) + γE[V*(s')], where s' follows the transition under a₂.
Construct a new policy π̃: take a₂ at s in the first step, then copy π* exactly thereafter (starting from the new state a₂ leads to).
By the inductive hypothesis «π* is optimal in every state» (induction on horizon or discount depth, finished with a limiting argument when γ<1): Vπ̃(s') ≤ V*(s') for all s'. Hence:
So Vπ̃(s) > Vπ*(s), contradicting the optimality of π*. ∎
NoteWhere does the Markov property enter the proof? The construction «copy π* thereafter» is legitimate only if the subproblem after a₂ is independent of how the new state was reached — that is precisely the Markov property. In history-dependent problems this construction fails (the new policy's state is not well defined), and the optimality principle collapses with it. This note is the invoice for «what one axiom is worth».
Theorem 7.2 The Bellman optimality equation
V* is a fixed point of the Bellman optimality operator: V*(s) = max_a Σs' p(s'|s,a)[r + γV*(s')]. By T5 Theorem 5.2 (γ-contraction) + Theorem 5.1 (existence and uniqueness of the fixed point), this equation has a unique solution.
Proof
Existence and uniqueness are delivered by T5 (the contraction mapping principle); only one thing remains here: confirming that V* (the definition of the optimal value) is indeed a fixed point. That follows from Theorem 7.1's greedy structure + induction — «optimal = one greedy step + optimal remainder», translated into an equation, is exactly the fixed-point equation. ∎
NoteThe complete logic chain: Markov property → optimality principle (this page) → Bellman equation → contraction (T5) → value iteration converges. Break any link and the algorithms downstream have no guarantee. Only these four pages (T5/T7 + the two /fund/ pages) together give the complete answer to «why value iteration converges».
Work it by hand
Two-state MDP: state 1 has a self-loop with reward 1 every step (the only action); state 0 has two actions — a stays in 0 with reward 0, and b goes to state 1 with reward 0.5. γ=0.9. Compute V* and the optimal policy by hand.
- State 1 self-loop: V*(1) = 1 + 0.9·V*(1) → V*(1) = 1/0.1 = 10 (geometric series sum, same trick as T2's worked example).
- [object Object]
- Compare: if a is chosen then V*(0)=0.9V*(0) only solves to 0 (and 9.5 > 0.9× anything ≤10); choosing b gives 9.5. Consistency check: 0.9×9.5 = 8.55 < 9.5 ✓ so b is indeed better (self-consistent).
- V* = (9.5, 10). Policy: at 0 choose b (go to state 1); at 1 stay.
V*(0)=9.5, V*(1)=10. The habit worth building from this problem: after solving for a fixed point, verify that «the max really did pick the assumed action» (a self-consistency check) — without it, you cannot detect solving for a «fake fixed point» (the max taking the other branch).
Run the numbers
Where the numbers come from
Measured value iteration on the two-state MDP above (γ=0.9, starting from V₀=0):
- Value iteration converges to V* = [9.5000, 10.0000] (digit-for-digit match with theory)
- γ=1 control experiment: state 1 self-loop with reward 1 each step; after 30 iterations V=30 and grows linearly — without discounting, no fixed point exists (the γ<1 premise of T5 Theorem 5.2 fails)
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| The Markov property | The state must contain all information affecting the future — the first principle of sensor design | used in → |
| Optimality principle | «One greedy step + optimal subproblem» is what makes Q-learning's max operator legitimate | used in → |
| γ<1 | Discounting is not just a preference setting — it is the premise for V* to exist | used in → |
| State information leakage | State aliasing: same visible state, different future distributions → V is not well defined | used in → |
Boundaries: where this article stops
Where this page stops: POMDPs (the rigorous theory of partial observability), continuous-time optimal control (the HJB equation), and semi-Markov processes — none of these. Honest disclaimer: real robots are almost always POMDPs, and practice works around it by «piling on observations so the Markov property holds approximately» — be aware that this is a workaround.
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01In the proof by contradiction of the optimality principle, what does the step «construct π̃ by copying π*» use?
The Markov property. Only if the future is independent of history does «copying from the new state on» have a well-defined value. In history-dependent problems (POMDP / non-Markovian) the construction fails — the new policy's value cannot be computed from the visible state alone.
02With γ=1 and a self-loop giving reward 1 each step, does the Bellman equation V = 1 + V have a solution?
No finite solution (1+V=V implies 1=0). This is not numerical divergence but an equation with no solution: the reward stream never decays and never terminates, so the total return is infinite. Three fixes: discount with γ<1, add termination to the problem, or switch to the average-reward criterion (average reward 1 per step is well defined).
03The state design provides only joint angles, but the payload position affects the dynamics. Write down what happens.
At a visible state s the conditional distribution p(s'|s,a) is no longer unique (it depends on the hidden payload position) — the transition kernel cannot be written in the five-tuple form, and the «E» in V(s)=E[G|s] lacks a definite distribution. Symptoms: same state, different behavior; training curves oscillate. Fix: put the payload pose into the observation.
04Why is the Bellman optimality equation «exactly» value iteration's fixed-point equation? What is the logical order of the two?
The order: Markov property → optimality principle (a structural theorem) → translate the structure into an equation (fixed-point form) → T5 proves the fixed point can be approached iteratively. It is not that «value iteration happens to converge», but that «the equation's solvability comes from contraction, contraction comes from γ<1, and γ's meaning comes from the construction».