Markov Decision Processes
States, actions, rewards, transitions, discount factor — the formal RL framework
Imagine a robot navigating a grid to reach a goal. At each step it sees its current position, chooses a direction to move, and receives a reward: +1 for reaching the goal, -0.01 for each step taken, -1 for falling into a hole. After moving it ends up in a new position, and the decision problem repeats until the robot reaches a terminal state. That sequence of state-action-reward-state is an episode, and RL's entire job is to find the sequence of actions — the policy — that maximizes total reward across that episode.
The MDP (Markov Decision Process) is the formal language for this. It has five components. The state space S is all possible positions the robot can be in. The action space A is all directions it can move. The transition function T(s, a, s') = P(s' | s, a) is the probability of landing in s' after moving in direction a from state s. The reward function R(s, a, s') is the immediate reward received on that transition. The discount factor γ ∈ [0, 1) controls how much future rewards are worth relative to immediate ones: γ = 0 means the robot cares only about the next step, γ = 0.99 means a reward 100 steps away has decayed to about 37% of its value (0.99^100 ≈ 0.37) — still meaningfully non-negligible, giving an effective planning horizon of roughly 1/(1-γ) ≈ 100 steps, versus a 1-step horizon at γ = 0.
The return G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + ... is the discounted sum of all future rewards from time t. The policy π(a | s) is the probability of taking action a in state s. The agent's goal is to find π* — the optimal policy — that maximizes expected return E[G_t] from every starting state.
The Markov property is the key assumption underpinning everything: the next state depends only on the current state and action, not the full history. For the grid robot this holds perfectly — knowing where you are now is enough to navigate. It breaks whenever the current observation is insufficient: a robot that sees only a camera image cannot distinguish a locked door from an unlocked one, because the relevant information — whether a key was picked up earlier — is not in the current frame. The fix is to augment the state representation to include whatever history is needed.
NOT this: RL is only for games and robotics. Any sequential decision problem with delayed feedback can be formulated as an MDP. Ad bidding (state = user context, action = bid amount, reward = revenue), recommendation (state = user history, action = item, reward = click), drug dosing (state = patient vitals, action = drug dose, reward = patient outcome). The MDP framework is the language — the applications are as broad as any problem where you act, observe a result, and act again.
Key points
- Before implementing any RL system, write down all five MDP components explicitly. Ambiguity in reward function design is the most common reason RL systems behave unexpectedly. Reward shaping bugs are harder to debug than code bugs because the agent's behavior looks intentional — it is doing exactly what the reward says, just not what you meant.
- Designing a reward that is easy to measure but misaligned with the true objective is the most common production failure. An ad system rewarded for clicks maximizes clickbait. A cleaning robot rewarded for dust-sensor readings learns to cover the sensor. A recommendation system rewarded for watch time recommends outrage content. Define the reward to match what you actually want, not what is easiest to instrument.
- If the agent's policy looks plausible but performance plateaus unexpectedly, check whether the Markov property holds for your state representation. If good decisions require information that is not in the current state — recent history, actions taken earlier, information that was observed but not retained — the Markov property is violated. Add the missing history to the state representation and retrain.
The MDP is just a formal way of saying: at every step the agent sees a state, picks an action, gets a reward, and ends up somewhere new — and the goal is to find the policy that makes those rewards add up to as much as possible.
Recap
- MDP = 5 components: state space $S$, actions $A$, transitions $T(s,a,s')$, reward $R$, discount $\gamma \in [0,1)$.
- Return $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$ — goal is a policy $\pi^*$ maximizing $E[G_t]$.
- Markov property: next state depends only on current state+action, not history. Break it, augment the state.
- \gamma tunes horizon: 0 = myopic, 0.99 = ~100 steps of future still matter.
- Write all 5 components explicitly before coding — reward ambiguity is the #1 failure.
- Easy-to-measure reward misaligned with the true objective is the classic production trap (clicks -> clickbait).
- MDP is the language, not just games: ad bidding, recsys, drug dosing all fit.
Check your understanding
Q1. Why does the optimal policy for a finite-horizon MDP depend on the time remaining t, while the optimal policy for an infinite-horizon discounted MDP does not?
- A) Finite-horizon MDPs redefine the reward function R_t(s,a) at every remaining timestep via an explicit decay schedule, while infinite-horizon MDPs hold a single constant reward function fixed for the entire trajectory, so only the finite case ever needs re-optimizing
- B) Finite-horizon MDPs are forced into stochastic softmax policies near the terminal step because bounded time makes the agent provably risk-averse, whereas infinite-horizon MDPs are guaranteed a deterministic policy by the policy improvement theorem regardless of γ
- C) V_t(s) changes with remaining time t via backward induction, so the greedy policy differs at each t; the infinite-horizon Bellman equation has a unique fixed point, so the same greedy policy is optimal at every step
- D) Infinite-horizon MDPs are defined to always use γ close to 1 so the agent becomes indifferent to timing, while finite-horizon MDPs are mathematically restricted to exactly γ=1, and this restriction is what forces their policy to depend on time
Q2. Your robot RL agent receives only a camera image as observation. It keeps walking into the same wall repeatedly. What Markov property violation is happening and how do you fix it?
- A) The observation is not Markov because one frame lacks motion and exploration history; fix with frame stacking, an LSTM over past observations, or a belief-filter state estimator
- B) The Markov property is fully satisfied because a single high-resolution camera frame captures the complete physical state, including velocity and any previously collected keys; the real issue is a reward function that under-penalises wall collisions
- C) The violation occurs because the transition function P(s'|s,a) is inherently stochastic from sensor noise; the fix is to train entirely in a deterministic, noise-free simulator before ever deploying to the real robot's camera
- D) The observation space is simply too high-dimensional, causing numerical instability and exploding gradients inside the policy network's convolutional layers; the fix is to progressively reduce image resolution until the property empirically holds
Q3. Why is γ = 0.99 harder to train with than γ = 0.95, even if both converge to a valid solution?
- A) γ=0.99 discounts step-to-step reward far more aggressively than γ=0.95 does, which paradoxically makes the agent ignore long-term consequences entirely and collapse to a myopic greedy policy that is strictly harder to improve via gradient methods
- B) γ=0.99 forces the agent to take more environment interactions before training can begin at all, because every reward signal must first be discounted to exactly zero across the entire buffer before a single gradient update is computed
- C) γ=0.99 is harder to train specifically because it mathematically requires a denser, hand-engineered reward function at every timestep, which is fundamentally more costly to design than the naturally sparse rewards paired with γ=0.95
- D) γ=0.99 extends the effective horizon to ~100 steps vs ~20 for γ=0.95, raising Monte Carlo variance and slowing TD propagation — more samples are needed to stabilise value estimates
Q4. A product team asks you to deploy an RL agent for content recommendation. Which two of the following are essential MDP design considerations for this system?
- A) State must preserve the Markov property — include enough user history (not just the current click) so the next recommendation doesn't require information already lost from the state
- B) Reward should avoid Goodhart-prone proxies — an engagement metric like raw clicks is easy to instrument but risks reward hacking toward clickbait rather than true user value
- C) The action space can be left unconstrained since gradient descent automatically adapts to any number of candidate items without any retrieval or ranking pre-filtering step
- D) Off-policy distribution shift from historical logged data is not a real concern here, because pretraining the policy with supervised learning on click logs eliminates it by construction
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →