ProjekinAja. Reinforcement Learning Stage 1 · Foundations Lesson 1.4
● Stage 1 · Lesson 1.4

Markov Decision Processes (MDPs)

The formal frame behind everything in RL. Reinforcement learning borrows its mathematics from the optimal control of Markov Decision Processes — so let's make that mouthful precise, one friendly piece at a time.

⏱ ~14 min read 🧭 The formal frame 🏁 Closes Stage 1

🎯 By the end you'll understand

The Markov property (why the present is all you need), what a Markov chain is, and how adding actions and rewards turns it into a Markov Decision Process — the tuple (S, A, P, R, γ) that quietly underpins every algorithm in the rest of this course.

KEY INSIGHTThe one idea to take away

An MDP is just the bike story written in math: states you can be in, actions you can take, what tends to happen next, and the reward you get for it.

You've already met every ingredient — agent, environment, state, action, reward, return, discounting. A Markov Decision Process doesn't add a single new idea. It simply gives all of those a clean, formal home so we can reason about them precisely and prove that our learning algorithms actually work.

🔑 Hold onto this

Almost every RL method — value iteration, Q-learning, SARSA, policy gradients, even deep RL — assumes the world is (at least approximately) an MDP. Understand the MDP and you understand the contract that the rest of the field is built on.

CORE CONCEPTThe Markov property: the present is enough

Picture a game of chess. You walk up to a board mid-game, having seen none of the moves that led here. Can you still decide on a good move? Of course — everything you need is sitting right there on the board. The history of how the pieces arrived doesn't change what the best move is now. The current position already contains it.

That's the Markov property in one sentence: the future depends only on the present, not on the past that led to it. If knowing where you are right now tells you everything you'd learn from also knowing your entire history, then your state is Markov.

📖 The Markov property

A state is Markov if the probability of what happens next depends only on the current state — not on the sequence of states that came before it. Formally:

P(St+1 | St) = P(St+1 | S1, S2, …, St)the Markov property — "the present contains all you need"

Picture a cleaning robot wandering its rooms, or think back to your sister learning to ride. If the robot's state is "I'm in Room B," that single fact is enough to reason about where it can go next — it doesn't matter whether it reached Room B from the kitchen or the hallway. The maze cell you're standing in tells you your options; how you got there is irrelevant to where you can go.

💡 The honest caveat

Real problems are usually only approximately Markov. A single camera frame doesn't tell a self-driving car how fast another vehicle is moving — for that you'd need the previous frame too. The fix is to fold enough information into the state (e.g. include velocity, or stack a few frames) until it becomes Markov "enough." When you genuinely can't, you have a POMDP — more on that below, and in Stage 4.

FRAMEWORKThe simplest version: a Markov chain

Before we bring in actions and rewards, let's meet the bare-bones version: a Markov chain. It's just a set of states plus the probabilities of moving from one to another. No decisions, no rewards — the system just drifts from state to state on its own, like weather, or a board-game token blown around by dice.

Imagine a tiny weather model with three states — ☀️ Sunny, ☁️ Cloudy, 🌧️ Rainy — where tomorrow's weather depends only on today's (a Markov assumption). The arrows carry transition probabilities, and the arrows leaving any state always sum to 1.

Pick today's weather, then press play to follow one possible week. Watch which arrows light up: only the three that leave the current state.

One possible week of weather
0.3 0.4 0.2 0.2 0.3 0.3 0.5 0.3 0.5 Sunny Cloudy Rainy
The week so far · only the last day sets tomorrow's odds
0Sunny1Sunny2Cloudy3Rainy4Rainy5Sunny6Rainy7Cloudy
A Markov chain: states and transition probabilities, nothing more. From Sunny, there's a 0.5 chance of staying Sunny, 0.3 of becoming Cloudy, 0.2 of turning Rainy — and those add to 1.

A Markov chain models a world that evolves by itself. But our agent isn't a passive weather vane — it gets to choose. To capture that, we need to add two things: actions and rewards. Do that, and a Markov chain grows up into a Markov Decision Process.

CORE CONCEPTAdding actions and rewards

In a Markov chain, transitions just happen. In a Markov Decision Process, the agent influences the transitions by choosing an action. Now there isn't one set of arrows leaving each state — there's a set of arrows per action. Picking "pedal hard" leads somewhere different (and with different odds) than picking "brake."

📖 Markov Decision Process (MDP)

A mathematical framework for sequential decision-making where outcomes are partly random and partly under the agent's control. It's a Markov process in which, at each state, the agent chooses an action, the environment transitions to a new state (probabilistically) and emits a reward. An MDP is the formal object an RL agent is trying to solve.

The heart of the MDP is its transition dynamics — the rule that says, given where you are and what you do, how likely each next state is, written:

P(s′ | s, a) = P(St+1 = s′ | St = s, At = a)transition probability — "do a in s, land in s′ with this chance"

Read it aloud: "the probability of ending up in state s′, given that I was in state s and took action a." Notice the Markov property baked right in — it conditions on the current s and a, never on the history. That's the whole reason MDPs are tractable.

And whenever a transition happens, the environment hands back a number — the reward, exactly the +1 banana / −1 fall signal from Lesson 1.1. The reward function R says how good that transition was. Stack states, actions, transitions, rewards, and the discount γ together and you have the full five-piece object.

FORMALThe MDP tuple: (S, A, P, R, γ)

Here's the whole thing in one line. An MDP is a five-part bundle:

MDP = ( S , A , P , R , γ )the five ingredients of any MDP

Each piece is something you already know by another name. The table maps the formal symbol to plain English, and back to the bike and maze examples you've been carrying since Lesson 1.1, and to the cleaning robot from this lesson.

SymbolNamePlain meaningBike / maze example
SState spaceEvery situation the agent can be in.Every balance/speed snapshot · every maze cell or room A/B/C.
AAction spaceEvery choice available to the agent.{pedal, steer, brake} · {up, down, left, right}.
PTransition dynamicsP(s′|s,a): how likely each next state is."Steer hard" usually turns, but sometimes skids · a slippery tile may not move you.
RReward functionThe number you get for a transition.+1 per smooth metre, −1 for a fall · +10 at the goal cell.
γDiscount factorHow much future reward is worth now (Lesson 1.3).γ near 1 = patient, far-sighted · γ near 0 = greedy for the next banana.
💡 Two honest simplifications

We're assuming the state and action sets are finite (a "finite MDP") — that keeps the picture clean, though real problems can have continuous states. And we write reward as a clean number; in practice you design it, sometimes painfully. Both are fine for building intuition now; we'll loosen them later in the course.

SEE ITBuild an MDP — toggle an action, watch P and R light up

Here's a tiny three-state maze for the cleaning robot: A, B, and the Goal ⭐. From state A the robot can choose an action. Each action has its own transition probabilities P(s′|s,a) and its own reward R. Toggle the action and watch which arrows — and which reward — switch on. Same state, different action, different future: that's the soul of an MDP.

🤖 Interactive · One state, two actions, two very different outcomes

The robot is in state A. Choose its action and read off P(s′|s,a) and R.

A you are here B ⭐ Goal 0.8 → B 0.2 → A 0.5 → ⭐ Goal 0.5 → A (slip!)
Action chosen
🐢 Move carefully
Reward R for this action
−1
Most likely next state
B (0.8)

Careful: a small step toward B, with a low cost. Slow but safe.

💡 What you're looking at

Notice it's not deterministic. "Move carefully" usually reaches B (0.8) but sometimes you stay put (0.2) — that's P(s′|s,a). The reward R is the small cost of the step. Try Rush ahead: a real shot at the Goal, but a 50% chance of slipping back to A.

That's an MDP in miniature. Same state A, but the action reshapes both the odds of where you go (P) and the payoff (R). The agent's whole challenge is to learn, for every state, which action gives the best long-run deal once you account for those probabilities and the discount γ — which is exactly what Stage 2 is about.

FRAMEWORKThe agent's job: find a policy

So what does it mean to "solve" an MDP? It means finding a policy — a rule that tells the agent which action to take in each state. We write a policy as π(a|s): the probability of choosing action a when in state s.

π(a | s) = P(At = a | St = s)a policy — the agent's strategy, state by state

In our maze widget, a policy is just an answer to the question "in state A, do I move carefully or rush?" — and the same kind of answer for B and every other state. A good policy isn't the one that grabs the biggest immediate reward (remember the warning from Lesson 1.1); it's the one that earns the biggest expected discounted return from Lesson 1.3:

Gt = Rt+1 + γRt+2 + γ2Rt+3 + … = Σk=0∞ γkRt+k+1discounted return — what the policy maximises
🔑 The objective, in one line

The agent's goal is to find the policy π that maximises the expected discounted return 𝔼[Gt]. Everything else in this course — value functions, Q-learning, policy gradients — is a different clever route to that same destination.

That's the beauty of the MDP frame: it turns a vague wish ("behave well") into a precise optimisation problem ("maximise expected discounted return over P and R"). Once a problem is written as an MDP, a whole toolbox of algorithms becomes available.

WEAKNESSWhen the state is hidden: POMDPs

There's a catch we have to be honest about. The MDP assumes the agent can see the full state — the whole chess board. But many real agents can't. A robot with a single forward camera can't see what's behind it. A poker player can't see opponents' cards. A trading bot sees prices but not the intentions moving them.

📖 POMDP (Partially Observable MDP)

An MDP in which the agent doesn't observe the true state directly — it only gets a noisy or partial observation and must infer what state it's probably in. The world is still Markov underneath; the agent just can't fully see it.

Many — arguably most — real problems are technically POMDPs. The practical trick, as we hinted earlier, is to enrich the observation until it's "Markov enough" (stack recent frames, track a belief over states, or feed history into a memory like an LSTM). We'll tackle partial observability head-on in Stage 4. For now, the clean MDP is the right mental model — and a remarkably powerful one.

WEAKNESSCommon mistakes to avoid

✗ "The agent needs the full history to decide well."

Not if the state is Markov. A well-defined state already summarises everything relevant from the past — that's the whole point of the Markov property. If you find yourself wishing for history, the real fix is usually to put the missing information into the state, not to remember the past separately.

✗ "Transitions are always deterministic — action X always leads to state Y."

In general P(s′|s,a) is a probability distribution. "Rush ahead" reached the Goal only half the time in our widget. Deterministic environments are just the special case where one next state has probability 1 — the math is the same, but don't assume it.

✗ "Every real problem is a clean, fully-observable MDP."

Tempting, but false. Most interesting problems are only approximately Markov, and many are genuinely POMDPs. The MDP is the idealisation we design toward — by shaping the state until the assumption nearly holds — not a free fact about the world.

KEY INSIGHTWhere this connects in your course

  • What RL is (1.1) — agent, environment, state, action, reward. The MDP is the formal name for that whole setup.
  • The RL loop (1.2) — the state → action → reward → next-state cycle is one step through an MDP, governed by P(s′|s,a).
  • Return & discounting (1.3) — the γ in (S,A,P,R,γ) and the return Gt the policy maximises.
  • Interaction & feedback (2.1) — now we step inside the MDP and watch the agent actually learn from experience.
  • Partial observability (Stage 4) — what to do when the agent can't see the full state: POMDPs.

That closes Stage 1. You now have the complete vocabulary and the formal frame. Stage 2 answers the question that's been hovering this whole time: given an MDP, how does the agent actually figure out a good policy? Time to find out.

GLOSSARYKey terms introduced

Markov property
The future depends only on the current state, not on the history that led to it: P(St+1|St) = P(St+1|S1…St).
Markov chain
The simplest Markov model: states plus transition probabilities, with no actions and no rewards.
Markov Decision Process (MDP)
The tuple (S, A, P, R, γ) — the formal framework for sequential decision-making that RL solves.
Transition probability (P)
P(s′|s,a): the chance of reaching state s′ after taking action a in state s.
State space (S)
The set of all states the agent can be in.
Action space (A)
The set of all actions available to the agent.
Policy (π)
π(a|s): the agent's strategy — the probability of taking action a in state s.
POMDP
A Partially Observable MDP: the agent sees only partial/noisy observations of a hidden true state.

ACTIVE RECALLCheck your understanding

Answer in your own words first, then reveal.

1State the Markov property in plain words, then in symbols.›

The future depends only on the present state, not the history that led to it — "the present contains all you need to decide." In symbols: P(St+1|St) = P(St+1|S1,…,St).

2What's the difference between a Markov chain and a Markov Decision Process?›

A Markov chain is just states + transition probabilities — the world evolves on its own. An MDP adds actions (the agent chooses) and rewards (feedback per transition), so transitions become P(s′|s,a) and the agent can steer its own future.

3Name the five elements of the MDP tuple and what each means.›

(S, A, P, R, γ): S = state space, A = action space, P = transition dynamics P(s′|s,a), R = reward function, γ = discount factor. Solving the MDP means finding a policy π(a|s) that maximises expected discounted return.

4Your robot has one forward camera and keeps bumping things behind it. Is its problem an MDP? What would you do?›

As stated it's a POMDP — the single frame doesn't reveal the full state (what's behind it). Make it "Markov enough" by enriching the state: add rear sensors, stack recent observations, or maintain a belief/memory of where things are. Full treatment of partial observability comes in Stage 4.

That's Stage 1 done. Next: inside the MDP, the agent starts to learn →