RL — LECTURE 02 · PREREQUISITE: LECTURE 01 (RL INTRO) · NEXT: VALUE FUNCTIONS & BELLMAN EQUATIONS
Markov Decision Processes (MDP)
In Lecture 01 you steered a Robot through a maze and discovered trial-and-error feedback. Today we formalize any sequential decision world into the universal 5-piece contract: <S, A, P, R, γ> — complete with stochastic transition physics, interactive slippery ice, and live MDP rollouts.
One-Look Blueprint Map of Markov Decision Processes
01 FROM LECTURE 01 TO FORMALISM
Upgrading our informal Maze story into one standard language
Whether an AI flies a drone, balances a data center, or schedules hospital dosages, researchers describe the entire problem using the exact same five MDP ingredients.
ONE-LOOK RECALL · ADDING TRANSITION KERNEL P
Lecture 01 introduced S (where), A (move), R (score), and γ (patience). Lecture 02 adds P(s'|s,a) — the world's exact probability rules for what happens next!
02 THE MARKOV PROPERTY
“The future depends only on now — not how you got here”
A State S(t) is Markov if holding onto yesterday's history adds zero extra predictive power once you know today's snapshot.
ONE-LOOK EQUATION · NO DIARY REQUIRED
P( S(t+1) | S(t), A(t) ) = P( S(t+1) | S(1), A(1), ..., S(t), A(t) )
03 FROM MARKOV CHAINS TO FULL MDPs
Climb the 3-step ladder: Drift → Score → Steer
Build the MDP definition one piece at a time so every symbol has a crystal-clear job before they combine.
04 THE 5-TUPLE BLUEPRINT <S, A, P, R, γ>
Click every symbol in <S, A, P, R, γ>
Every standard RL benchmark — from classic gridworlds to robotics — plugs straight into these exact five fields.
ONE-LOOK CHEAT SHEET
S = Where am I · A = What can I press · P = What might happen · R = Points won/lost · γ = Patience.
TRANSITION KERNEL SANITY CHECK · ROWS ALWAYS SUM TO 1.00
| State s & Action a | Next s' (East) | Next s' (South) | Next s' (Bounce Stay) | Total Probability Sum |
|---|---|---|---|---|
| From (0,0), try RIGHT (Slippery Ice) | 0.70 | 0.15 | 0.15 | 0.70 + 0.15 + 0.15 = 1.00 ✓ |
| From (0,0), try RIGHT (Solid Floor) | 1.00 | 0.00 | 0.00 | 1.00 + 0 + 0 = 1.00 ✓ |
05 TRANSITION KERNEL P(s'|s,a) & STOCHASTIC ICE
Steer on Slippery Ice — where actions have probability odds
On icy tiles, pressing RIGHT is not a 100% guarantee! Adjust floor slippage and watch both single moves and 100-throw empirical convergence.
06 INTERACTIVE 4-STATE DELIVERY MDP GRAPH
Safe Highway vs Icy Shortcut — inside an MDP graph
Switch between two Policies on our Robot's 4-station delivery MDP and see why reliable transitions often beat tempting gambles.
07 EPISODIC VS CONTINUING HORIZON BOUNDS
Why γ < 1 saves infinite loops from exploding to +∞
In Episodic MDPs (like Mazes or Chess), episodes stop at a Terminal flag. In Continuing MDPs (like 24/7 cooling control), steps continue forever — so discounting keeps total Return bounded beneath R_max / (1 - γ).
ONE-LOOK TRAJECTORY & GEOMETRIC BOUND RULE
Trajectory Probability multiplies conditional transitions: P(τ) = P(s1|s0,a0) × P(s2|s1,a1) · When continuing forever with γ < 1, total discounted reward stays below R / (1 - γ)!
08 FULL VS FOGGY OBSERVABILITY & PYTHON MDP CODE
Can the Agent see everything — and how do we code an MDP?
Standard MDPs assume Full Observability (the whole true state sits inside S(t)). When sensors only light up part of a dark maze, history matters again — and cleanly writing transition tables takes just 20 lines of Python.
09 REAL-WORLD MDP BLUEPRINTS
How engineers cast real systems as <S, A, P, R, γ>
Pick an industry domain below to inspect its exact 5-tuple design before any training begins.
10 MDP MASTERY CHECK
Verify your grasp of Markov Decision Processes
Complete all 10 checks on the Markov Property, Chain → MRP → MDP ladder, 5-tuple semantics, slippery probabilities, and discounted ceilings.
LECTURE 02 SUMMARY & NEXT STEP “An MDP <S, A, P, R, γ> gives any RL agent a complete mathematical arena. Next in Lecture 03, we evaluate how good each state is using Value Functions and Bellman Equations.”