RobotGuide
Math foundations/The Mathematical Construction of the MDP: What One Axiom Is Worth

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.

about 50 min2 theorems7 proof steps4 self-test questions

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).

Vπ̃(s) = r(s,a₂) + γEs'~P(·|s,a₂)[Vπ̃(s')]

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:

Vπ̃(s) ≤ r(s,a₂) + γE[V*(s')] — while the contradiction hypothesis says this quantity > r(s,a₁) + γE[V*(s')] = Vπ*(s)

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.

  1. 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).
  2. [object Object]
  3. 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).
  4. V* = (9.5, 10). Policy: at 0 choose b (go to state 1); at 1 stay.
Answer

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 hereThe counterpart in RLUsed in
The Markov propertyThe state must contain all information affecting the future — the first principle of sensor designused in →
Optimality principle«One greedy step + optimal subproblem» is what makes Q-learning's max operator legitimateused in →
γ<1Discounting is not just a preference setting — it is the premise for V* to existused in →
State information leakageState aliasing: same visible state, different future distributions → V is not well definedused 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».

Up next

The full series · 27 articles

T1The Matrix Is a Ledger for Rotation≈ 25 minT2From Slope to Gradient: The First Line of Every Robot Learning Algorithm≈ 25 minT3Vectors and forces: the physical reading of the dot productAbout 20 minT4Two Rulers and a Better Rulerabout 25 minT5The Ledger of One Motor Revolution: Radians, Speed, and Powerabout 20 minT6Complex multiplication is rotation: the one-dimensional version of quaternionsAbout 20 minT7Bases and coordinates: why robots put everything in matrices45 minT8Matrix Multiplication: Chaining Transformations, Not a Table OperationAbout 40 minT9The Jacobian: Rotate a Joint One Degree — How Far Does the End Effector Move?About 45 minT10Eigenvectors: The Directions a Matrix Dare Not Touchabout 45 minT11SVD and the Pseudoinverse: When There Is No Exact Solution, Find the Nearest Oneabout 50 minT12Taylor expansion: putting a straight line to work in place of a curveAbout 40 minT13Probability spaces: why «random» needs axioms50 minT14Expectation: A Rigorous Construction of «Average»About 55 minT15Conditional Expectation: What the Vertical Bar Really Means≈ 60 minT16Four inequalities: the quantitative answer to «how many samples are enough»45 minT17Norms and fixed points: where «it always converges» comes from55 minT18Markov Chains: When the Time Average Equals the Ensemble Averageabout 55 minT19The Mathematical Construction of the MDP: What One Axiom Is Worthabout 50 minT20Dynamic Programming: The Accounting for Two Iterations≈ 50 minT21Optimization: why constraints cannot rely on penalties aloneAbout 55 minT22Stochastic Approximation: Every Term in the Learning-Rate Formulaabout 55 minT23The Mathematics of Contact: Hertz Theoryabout 45 minT24Friction and the Friction Cone: The Geometry of Constraintsabout 40 minT25Force Closure and Grasp Metrics: ε Is a Linear ProgramAbout 50 minT26Contact Kinematics: Why Rolling Is Not «Sliding Along»≈ 45 minT27Slip detection: from «I felt it» to «I computed it»About 50 min