RL Basics: MDP to Q-Learning in 5 Diagrams

The Problem: Every RL Tutorial Starts at the Wrong End

Most reinforcement learning guides throw you into DQN or PPO code before you understand why those algorithms exist. You end up copy-pasting hyperparameters without knowing what $\gamma=0.99$ actually does to your agent’s behavior.

Here’s the thing: RL has a brutally logical progression from first principles. Markov Decision Process → Bellman Equation → Value Iteration → Q-Learning. Each step solves one specific limitation of the previous approach. Once you see that chain, the entire field clicks.

This post walks through that progression using 5 diagrams and minimal math. By the end, you’ll know exactly why Q-learning exists and when it breaks.

Diagram 1: The Markov Decision Process (MDP)

An MDP is just a formal way to describe a decision-making problem. Five components:

• States $S$: where the agent can be (e.g., grid positions)
• Actions $A$: what the agent can do (e.g., move up/down/left/right)
• Transition function $P(s'|s,a)$: probability of landing in state $s'$ after taking action $a$ in state $s$
• Reward function $R(s,a,s')$: immediate payoff for that transition
• Discount factor $\gamma \in [0,1]$: how much the agent cares about future rewards

The Markov property is the key constraint: the next state depends ONLY on the current state and action, not on history. In practice, this means you can’t have an agent that “remembers” the last 3 states unless you explicitly encode that into the state representation (e.g., stack frames in Atari).

Here’s a 4×4 grid world MDP:

[S] [ ] [ ] [G]
[ ] [X] [ ] [ ]
[ ] [ ] [ ] [X]
[X] [ ] [ ] [ ]

S = start, G = goal (+10), X = pit (-5)
Actions: up, down, left, right
Transition: 80% intended direction, 10% each perpendicular (slippery floor)
γ = 0.9

The agent’s job: find a policy $\pi(a|s)$ that maximizes expected return $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$.

But how do you actually compute that optimal policy?

Diagram 2: The Bellman Equation Breaks Down Value

The Bellman equation is the core insight of RL. It says: the value of being in state $s$ equals the immediate reward plus the discounted value of wherever you end up.

$$V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^\pi(s') \right]$$

This is recursive. The value of $s$ depends on the value of $s'$, which depends on the value of $s''$, and so on. That’s actually useful — it means you can solve for $V^\pi$ iteratively.

The optimal value function $V^*(s)$ satisfies:

$$V^*(s) = \max_a \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^*(s') \right]$$

Once you have $V^*(s)$, the optimal policy is trivial: always pick the action that maximizes that right-hand side.

Here’s the problem: computing $V^*$ requires knowing $P(s'|s,a)$ — the full transition model of the environment. In the grid world above, that’s manageable. In robotics or Atari? You’d need to enumerate millions of states and precompute probabilities. Not happening.

This is why model-based RL (where you learn $P$) is sample-efficient but compute-heavy, and model-free RL (where you skip $P$ entirely) dominates in complex environments.

Diagram 3: Value Iteration Solves Small MDPs

If you DO have the full MDP model, Value Iteration is the simplest solver. Pseudocode:

import numpy as np

# Initialize V(s) = 0 for all states
V = np.zeros(num_states)
theta = 1e-6  # convergence threshold

while True:
    delta = 0
    for s in range(num_states):
        v_old = V[s]
        # Bellman update: max over actions
        V[s] = max(
            sum(P[s, a, s_next] * (R[s, a, s_next] + gamma * V[s_next])
                for s_next in range(num_states))
            for a in range(num_actions)
        )
        delta = max(delta, abs(v_old - V[s]))
    if delta < theta:
        break  # converged

# Extract policy: for each state, pick action that maximizes value
policy = np.zeros(num_states, dtype=int)
for s in range(num_states):
    policy[s] = np.argmax([
        sum(P[s, a, s_next] * (R[s, a, s_next] + gamma * V[s_next])
            for s_next in range(num_states))
        for a in range(num_actions)
    ])

This converges to $V^*$ in polynomial time (technically $O(|S|^2 |A| \log(1/(1-\gamma)))$ iterations). For a 10×10 grid, that’s instant. For a 100×100 grid with obstacles? Still tractable. For continuous state spaces like robotic arm joint angles? Completely infeasible.

Value Iteration is the baseline you compare everything else against. If your fancy deep RL algorithm can’t beat VI on a toy gridworld, something’s deeply wrong.

Diagram 4: Q-Values Let You Act Without Knowing P

Here’s the key trick: instead of storing $V(s)$, store $Q(s,a)$ — the value of taking action $a$ in state $s$, then following the optimal policy afterward.

$$Q^*(s,a) = \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma \max_{a'} Q^*(s',a') \right]$$

Notice what just happened. To choose an action, you just compute $\arg\max_a Q(s,a)$. You don’t need to know $P(s'|s,a)$ at decision time — that knowledge is baked into the Q-values during learning.

This is the foundational insight of Q-learning.

Diagram 5: Q-Learning Learns Q from Experience

Q-learning (Watkins, 1989) learns $Q(s,a)$ by trial and error. No model required. The update rule:

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') – Q(s,a) \right]$$

Where:
– $\alpha$ is the learning rate (typically 0.01-0.5)
– $r$ is the actual reward observed after taking action $a$ in state $s$
– $s'$ is the next state you landed in
– The term in brackets is the temporal difference (TD) error — the gap between your current estimate and the observed outcome

Here’s a minimal tabular Q-learning implementation for the grid world:

import numpy as np
import random

# Grid world: 4x4, same setup as before
num_states = 16
num_actions = 4  # up, down, left, right
Q = np.zeros((num_states, num_actions))

alpha = 0.1
gamma = 0.9
epsilon = 0.1  # exploration rate
num_episodes = 1000

for episode in range(num_episodes):
    s = 0  # start state
    while s != 15:  # goal state
        # Epsilon-greedy action selection
        if random.random() < epsilon:
            a = random.randint(0, 3)  # explore
        else:
            a = np.argmax(Q[s, :])  # exploit

        # Take action, observe reward and next state
        s_next, r = env.step(s, a)  # hypothetical env interface

        # Q-learning update (off-policy)
        td_target = r + gamma * np.max(Q[s_next, :])
        Q[s, a] += alpha * (td_target - Q[s, a])

        s = s_next
        if s in [4, 11, 12]:  # pit states
            break  # episode ends

Notice the np.max(Q[s_next, :]) — we’re using the BEST action in the next state to update Q, even if we didn’t take that action (because of epsilon-greedy exploration). This is why Q-learning is off-policy: it learns the optimal policy while following an exploratory policy.

In practice, tabular Q-learning works great up to maybe $10^6$ states. Beyond that, you need function approximation (neural networks) — which is how you get DQN.

Where This Breaks (And Why DQN Exists)

Tabular Q-learning fails in three cases:

1. Continuous state spaces: You can’t enumerate every possible robot joint angle configuration. Solution: approximate $Q(s,a)$ with a neural network $Q_\theta(s,a)$.
2. High-dimensional observations: Atari game pixels are 210×160×3 RGB arrays. Even discretized, that’s billions of states. Solution: convolutional Q-networks that extract features from pixels.
3. Instability with function approximation: Updating a neural network Q-function naively causes catastrophic divergence. Solution: experience replay + target networks (the core DQN tricks from Mnih et al., 2015).

I’m not entirely sure why tabular Q-learning works as well as it does on moderately large grids (say, 50×50 with obstacles). My best guess is that most states are never visited, so the effective state space is much smaller than $|S|$. If you’re doing maze navigation, the agent quickly learns to avoid walls, so 80% of the Q-table stays at zero.

When to Use Q-Learning vs Policy Gradient

Q-learning (and its descendants like DQN, Double DQN, Dueling DQN) shines when:
– Discrete action spaces (up/down/left/right, yes/no)
– You need sample efficiency — Q-learning reuses every transition via replay buffers
– The environment is deterministic or low-noise

Policy gradient methods (PPO, A3C) win when:
– Continuous action spaces (robot joint torques, steering angles)
– You need stable convergence — policy gradients are on-policy, so no distribution shift issues
– The optimal policy is stochastic (e.g., rock-paper-scissors)

For most modern applications (robotics, continuous control), PPO or SAC dominate. But Q-learning is still the conceptual foundation — PPO’s value function critic is just a learned V(s), and SAC’s Q-functions are soft Q-learning with entropy regularization.

Hyperparameters That Actually Matter

After running Q-learning on half a dozen toy environments, here’s what I’ve learned:

• Learning rate $\alpha$: Start at 0.1. If Q-values oscillate wildly, drop to 0.01. If learning is glacially slow after 10k episodes, bump to 0.3. I’ve never needed anything outside [0.01, 0.5].
• Discount factor $\gamma$: 0.9 for short-horizon tasks (maze navigation), 0.99 for long-horizon (game playing). Setting $\gamma=1.0$ (no discounting) breaks on infinite-horizon problems — the value function diverges.
• Exploration $\epsilon$: Start at 1.0 (pure exploration), decay linearly to 0.01 over 50-70% of training. If your agent gets stuck in local optima, you decayed too fast.

The biggest footgun: reward scaling. If your rewards are in [0, 1000], Q-values explode and the learning rate becomes meaningless. Normalize rewards to roughly [-1, 1] before plugging into the TD update. I’ve wasted hours debugging “divergence” that was just poorly scaled rewards.

FAQ

Q: Can I use Q-learning for continuous action spaces like robot joint torques?

Not directly. You’d need to discretize actions (e.g., bin torques into 10 levels per joint), which explodes combinatorially. For continuous control, use actor-critic methods (DDPG, TD3, SAC) or policy gradients (PPO). Q-learning dominates in discrete domains like Atari or board games.

Q: Why does Q-learning need epsilon-greedy exploration instead of just picking max Q?

Because initial Q-values are random (or zeros). If you greedily exploit from step 1, you might never discover the high-reward path. Epsilon-greedy forces the agent to try suboptimal actions occasionally, updating Q-values for states it wouldn’t normally visit. Without exploration, you get stuck in the first local optimum.

Q: What’s the difference between Q-learning and SARSA?

Q-learning is off-policy: it updates Q using $\max_{a'} Q(s',a')$, regardless of what action you actually took next. SARSA is on-policy: it uses the action you DID take, so the update is $r + \gamma Q(s',a')$ where $a'$ was chosen by your epsilon-greedy policy. SARSA is more conservative (learns a safer policy), Q-learning is more aggressive (learns the optimal policy assuming you’ll act optimally in the future).

What I’m Still Figuring Out

The theory says Q-learning converges if you visit every state-action pair infinitely often and decay $\alpha$ appropriately. In practice, I’ve seen agents converge on 20×20 grids after ~5000 episodes with constant $\alpha=0.1$ — way before visiting all $20 \times 20 \times 4 = 1600$ state-action pairs even once. There’s some kind of generalization happening across similar states, but tabular Q-learning isn’t supposed to generalize.

My current theory: maybe the stochastic transitions (the 10% slip probability) force the agent to explore nearby states, effectively smoothing the Q-function. Need to test this with deterministic transitions and see if convergence requires way more episodes.

If you’re debugging Q-learning and nothing makes sense, try logging the per-episode return and TD error magnitude. If returns plateau but TD error stays high, your learning rate is too big. If both plateau early, you’re stuck in a local optimum — increase exploration or add reward shaping.

And if you’re coding this at 2am and the grid world still won’t solve, Dark Chocolate Espresso Beans are cheaper than a CS grad degree.