Markov Decision Processes Without the Notation Wall
9 min read · updated August 4, 2026
A Markov decision process is five things: a set of states, a set of actions, a rule for what the next state will be, a reward for each step, and a number that says how much the future counts. Everything in reinforcement learning is stated against that frame, and the frame is smaller than the notation makes it look.
Five things, one example
Take a problem you might genuinely have: a query arrives, and you can answer it with a cheap model, with an expensive model, or by giving up and escalating to a human. You can check the answer with a validator that is right most of the time. You want correct answers at low cost.
| Component | Description |
|---|---|
| S (states) | What the decision depends on. Here: how many attempts you have made, and what happened last time — (0, none), (1, cheap failed), (1, strong failed), (2, cheap failed), and so on. Six states, not a continuum. |
| A (actions) | What you can do. Here: call cheap, call strong, escalate. Three actions, available in every state. |
| P (transitions) | The probability of each next state given a state and action. Here it is the probability the chosen model produces an answer the validator accepts — say 0.55 for cheap and 0.90 for strong. |
| R (reward) | The scalar per step. Here: +1 for an accepted answer, minus the call cost, and -0.5 for escalating. Costs are in the same units as the benefit, deliberately, because otherwise the trade-off is undefined. |
| gamma (discount) | How much a reward one step later is worth. Between 0 and 1. At 0.9, a reward five steps away counts for 0.9^5 = 0.590 of its face value. |
That is a complete MDP. Notice what had to happen to build it: every quantity that matters to the decision had to be squeezed into the state, every choice into a finite action set, and every consequence into a single number. Those three squeezes are where real problems go wrong, and they are the actual content of the modelling work.
The Markov property is a choice you make
The Markov property says the next state and reward depend only on the current state and action, not on how you arrived. It is almost never true of the raw world. It is made true by construction: anything from the past that matters gets folded into the state until nothing outside the state matters any more.
The routing example makes this concrete. If the state were just “attempt number”, the process would not be Markov — whether to try the strong model depends on whether the cheap one already failed, and that fact would be missing. Adding the last outcome to the state restores the property. That is the whole trick, and its cost is that the state space grows with every fact you fold in.
A language model conversation is the same move in a familiar setting. The model has no memory between calls; the entire history is resent in the context window each time. That is what makes the process Markov in the context rather than in the conversation, and it is why the context window is a hard limit rather than a soft one: the state has a maximum size.
The discount factor is a horizon in steps
Discounting is usually justified by an analogy to interest rates, which is unhelpful. The useful reading is that gamma sets how far ahead the agent effectively looks, and the conversion is one division:
effective horizon ~= 1 / (1 - gamma) gamma = 0.90 -> 1 / 0.10 = 10 steps gamma = 0.95 -> 1 / 0.05 = 20 steps gamma = 0.99 -> 1 / 0.01 = 100 steps gamma = 0.999 -> 1 / 0.001 = 1000 steps a reward of 100, twenty steps away, is worth: gamma = 0.90 -> 100 * 0.90^20 = 100 * 0.1216 = 12.16 gamma = 0.99 -> 100 * 0.99^20 = 100 * 0.8179 = 81.79
Read that table before choosing a value. If your task takes 200 steps and you set gamma to 0.9, the agent cannot see the end of its own task: a reward at step 200 is discounted to 0.9^200, which is about 7e-10, and no amount of training will make it care. If your task takes five steps and you set 0.999, you have added variance for no reason.
The other thing discounting does is bound the return in an episode with no end. Without it, a policy that survives forever collecting small rewards has infinite value and so does every other such policy, and they become incomparable. With it, the sum converges — the maximum possible return from a per-step reward of r is r / (1 - gamma). For episodic tasks that genuinely terminate, gamma = 1 is fine and is what most language model post-training uses.
One Bellman backup, by hand
The Bellman equation says one thing: the value of a state is the immediate reward plus the discounted value of where you end up. Written for the best action rather than an average one, it is
Q(s, a) = R(s, a) + gamma * sum over s' of P(s'|s, a) * max_a' Q(s', a')
Take the first decision in the routing example, with gamma = 1, a cheap call costing 0.002 and a strong call costing 0.030. Suppose we already know the value of the state after a failed cheap call is 0.87 (from there, calling the strong model usually works). Then:
Q(start, cheap) = -0.002 + 0.55 * (1.0) + 0.45 * (0.87)
= -0.002 + 0.550 + 0.3915
= 0.9395
Q(start, strong) = -0.030 + 0.90 * (1.0) + 0.10 * (0.55)
= -0.030 + 0.900 + 0.055
= 0.9250
Q(start, escalate) = -0.5Cheap-first wins by 0.0145 — not because it is more likely to work, but because failing cheaply leaves you in a state that is still worth 0.87. That is the entire argument for cascading, derived rather than asserted. Solve for the point where the two are equal, holding the 0.87 fixed: -0.002 + p + (1 - p) * 0.87 = 0.925 gives p = 0.44. Below a cheap-model success rate of about 44 per cent, calling the strong model first is the better opening move. Recompute it with your own numbers; the arithmetic is four multiplications, and the only subtlety is that the 0.87 moves too when p does.
When you cannot see the state
An MDP assumes the agent observes the state. Real systems almost never give you that. In the routing example the thing that actually decides the outcome is how hard the query is, and you cannot see it — you see a proxy, and the true difficulty stays hidden.
That is a partially observed MDP, and the standard treatment is not to switch to a different algorithm but to make the observation richer: stack the last several observations, add features, or carry a recurrent state. You are approximating the hidden state with history, which is the same move as folding the past into the state, done under uncertainty.
Why the formalism earns its keep
The MDP frame is worth learning because it makes three questions answerable before you write any code. Is the action set finite and enumerable, or are you going to need a continuous policy? Does the action change what you face next, or is each decision independent — in which case you have a bandit and should be delighted? And is the reward observable at the time it should be attributed, or does it arrive 400 steps late?
Most failed reinforcement learning projects fail at one of those three, and all three are visible on paper. Writing the MDP down is the cheapest thing you will do on the project, and it is the step that most often ends it early for good reasons.