2 · Markov Decision Processes
The MDP is the formal language of RL: states, actions, transition probabilities, rewards, and a discount factor. Almost every RL problem is an MDP.
A Markov Decision Process is the 5-tuple (S, A, P, R, γ): states, actions, transition probabilities P(s'|s,a), rewards R(s,a), and a discount γ. The Markov property — the next state depends only on the current state and action — is what makes RL tractable.
Without this:
Without the MDP formalism you can't state what 'optimal' means or apply the Bellman equations that every value-based method relies on.
To reason about RL precisely we model the environment as a Markov Decision Process (MDP) — a 5-tuple (S, A, P, R, γ):
- S — the set of states.
- A — the set of actions.
- P(s' | s, a) — the transition probability of landing in state
s'after taking actionain states. Environments can be stochastic: the same action may lead to different next states. - R(s, a) — the reward for taking action
ain states. - γ (gamma, 0 ≤ γ < 1) — the discount factor, how much we value future reward vs immediate (next lesson).
The defining assumption is the Markov property: the next state and reward depend only on the current state and action, not the full history of how you got there. This is what makes the problem solvable — the current state is a sufficient summary of the past.
Below we define a small stochastic MDP explicitly — a 4-state chain where moving "forward" usually works but sometimes slips — and simulate trajectories from it. Seeing P as an actual probability table makes the abstraction concrete.
Python (in browser)
An MDP made explicit: states, a stochastic transition table P(s'|s,a), rewards, and γ. The Markov property means each step depends only on the current state.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
What does the Markov property state?
- An MDP is the 5-tuple (S, A, P, R, γ): states, actions, transition probabilities, rewards, and a discount factor.
- Transitions can be stochastic — P(s'|s,a) is a distribution, so the same action can yield different next states.
- The Markov property (future depends only on the present state+action) is the assumption that makes RL tractable.
Every value-based and dynamic-programming method is defined on an MDP; even bandits and contextual RL are special cases.
If you remove it: Without the MDP formalism, 'optimal policy' and the Bellman equations have no precise meaning.