Markov Decision Process
The formal frame underneath all of reinforcement learning — built on an assumption that's almost always false, and it works anyway.
When not to use it
- When your state doesn't contain what matters. Poker, conversation, markets. You're modelling a POMDP as an MDP and hoping.
- With a long true horizon and γ=0.99. That's an effective horizon of ~100 steps. Beyond it, the agent can't see.
- When you have no reward function. The frame assumes one exists. That assumption is doing enormous work.
- Tabular, on anything real. States grow exponentially. That's the curse of dimensionality and it's why approximation exists.
Reach for something else instead
- POMDP — correct for partial observability, computationally brutal.
- Contextual bandits — if actions don't affect future states, you have a much easier problem. Check first.
- Supervised learning — if you have labels, you don't need this.
- Classical planning — if you know the transitions, don't learn them.
Sources & further reading
- Bellman (1957), Dynamic Programming — the equation, the principle of optimality, and the curse of dimensionality, all in one book.
- Sutton & Barto (2018), Reinforcement Learning: An Introduction — the textbook. If you read one thing about RL, this.
- Kaelbling, Littman & Cassandra (1998), Planning and Acting in Partially Observable Stochastic Domains — POMDPs; the honest model, and why nobody uses it.
Primary sources, listed so you can check the claims on this page rather than take them on trust.
Where people go wrong
- Assuming Markov without checking what's missing from the state. That's where the failures are.
- Treating γ as a technicality. It's a claim about how far ahead you care, and it caps what the agent can see.
- Modelling as an MDP when a contextual bandit fits — if actions don't change the future, RL is enormous overkill.
- Forgetting the frame assumes a reward function. That's the hard part, and it's outside the formalism.
At a glance
FieldFoundations
The five piecesstates, actions, transitions, rewards, discount
The assumptionthe future depends only on the present state
Realityalmost always false; fixed by stuffing history into the state
What it buysthe Bellman recursion, which needs Markov to be valid
What it assumes awaythe reward function
DifficultyIntermediate
Flashcards for this concept
Question
—
Answer
—
1 / 4
Often compared with
MDP vs. POMDP — one assumes the agent sees the state, the other admits it sees an observation. The second is honest and computationally brutal, so everyone uses the first and adds history.