States, actions, a reward, a discount — the frame every learning agent lives in. Fix a policy and the value of each state is not simulated but solved: the Bellman expectation equation V = Rπ + γ·PπV is one linear system, exact in closed form. Down the center the pipeline runs: the tuple goes in, the engine solves, the value out. The blue team builds and re-checks it; the red team tries to break it.
source R. A. Howard, Dynamic Programming and Markov Processes (MIT Press & Wiley, 1960); R. Bellman, Dynamic Programming (Princeton, 1957) — archive.org/details/dynamicprogrammi0000howa. Rendered, not quoted.
For a fixed policy π the value function is defined self-referentially — the worth of a state is its immediate reward plus the discounted worth of where π sends you:
V(s) = Rπ(s) + γ·Σs' Pπ(s'|s)·V(s')
That is n equations in n unknowns. Stack them: (I − γPπ)V = Rπ, solvable exactly whenever γ<1 (the matrix is then invertible). No sampling, no training. Live Pπ and Rπ for the current policy:
| s | → A | → B | → C | Rπ |
|---|
Strip the actions and the reward away and an MDP collapses to the Markov chain — a memoryless random walk that just drifts. Pπ here is such a chain: pick a policy and the choices freeze into one transition matrix.
The MDP adds the two things the chain lacks: a steering wheel (choose the action) and a scoreboard (collect the reward). The chain asks "where do I end up?"; the MDP asks "given that I can steer, what is each place worth?" Each sphere is the next one's premise.
The blue team's live check: re-solve for the current policy, confirm the Bellman residual is ~0, every value obeys the Rmax/(1−γ) bound, and it matches an independent discounted-trajectory sum. If red tampers, this badge is where it shows.
A concrete little world: a robot patrolling three locations in a loop.
S = {A, B, C} — a 3-state cycle. A = {advance → next location, hold → stay}. P is deterministic given the action. R(s,a): advancing pays A=+1, B=+2, C=+3; holding pays 0 — except holding at C keeps paying +3 (C is the jackpot). γ ∈ [0,1) discounts the future.
A policy π names one action per state. That is the whole input — feed it to the panel and it returns the value of every state.
The engine forms (I − γPπ) and solves by Gaussian elimination — the exact value, not an average of rollouts.
| state | action | Rπ | V(s) |
|---|
Move γ or change any action — V is re-solved from the linear system on the spot, never looked up.
What the machine produces, proven: V(s) for every state, the unique fixed point of the Bellman expectation operator. It satisfies V = Rπ + γPπV to machine precision, sits inside the geometric bound |V| ≤ Rmax/(1−γ), and — because the policy is deterministic — equals the discounted sum of rewards along the trajectory it actually walks.
The blue team's witness (left) re-solves and confirms these live; the red team (right) tries to make them diverge.
And the frame has hard edges: P and R must be known (unknown ⇒ model-free RL, Q-learning); the table is |S|²|A| — the curse of dimensionality kills exact solves for large or continuous spaces; the state must be Markov (sufficient) — real agents see partial observations (POMDPs); and γ<1 is a modelling choice that quietly discounts the far future to nothing.
"Solving the MDP gives the optimal policy." Cut. The expectation equation only scores a fixed π. Optimality needs the max-over-actions operator; this engine is the evaluation step inside that larger loop.
"You must simulate/train to estimate the values." Cut. For a known model and fixed policy the value is the exact solution of a linear system — closed form. Sampling is only for the model-free case.
"γ is just a number; set it to 1." Kept, corrected. At γ=1 on a recurring chain, (I − Pπ) is singular and the value diverges — undiscounted problems need proper/absorbing policies or average-reward theory. The red team's tamper does exactly this.
The red team's move: shove γ = 1 onto the cyclic MDP. Now (I − γPπ) loses rank, the Rmax/(1−γ) bound blows up, and the value diverges to ∞. The blue team's witness (window 7) is watching.
Set γ=1 and the geometric series 1/(1−γ) is undefined; the linear solve hits a zero pivot on the cycle. The witness re-solves, sees non-finite values, and turns red. Nothing is faked; the attack is real and it is caught.