Q-learning algorithm

What is Q-learning?

Breaking down the properties:

• Model-free: Doesn't require knowledge of transition probabilities $P(s'|s,a)$ or reward function $R(s,a)$
• Off-policy: Can learn optimal policy while following an exploratory (e.g., ε-greedy) policy
• Temporal-difference: Updates estimates based on other estimates (bootstrapping)

Deriving Q-learning from First Principles

Step 1: Start with the Bellman Optimality Equation

The optimal action-value function satisfies:

$Q^*(s,a) = \mathbb{E}_{s'}\left[r + \gamma \max_{a'} Q^*(s',a')\right]$

Why this form?

• $Q^*(s,a)$ = expected total discounted return starting from state $s$, taking action $a$, then following optimal policy
• Immediate reward $r$ + discounted optimal value from next state
• We take $\max_{a'}$ because optimal policy always choses best action in next state

Step 2: Turn Expectation into Sampling

We don't know the transition model, so we can't compute the expectation. Instead, we sample transitions $(s, a, r, s')$ from experience:

$Q^*(s,a) \approx r + \gamma \max_{a'} Q^*(s',a')$

This single sample gives us a target for what $Q(s,a)$ should be.

Step 3: Iterative Update with Learning Rate

Since one sample is noisy, we update gradually:

Where:

• $\alpha$ learning rate (0 < α ≤ 1)
• $\gamma$ = discount factor (0 ≤ γ ≤ 1)
• $r + \gamma \max_{a'} Q(s',a')$ = TD target
• $r + \gamma \max_{a'} Q(s',a') - Q(s,a)$ = TD error (δ)

Why this works:

• We move Q(s,a) toward the target by a fraction α
• If α=1, we'd replace Q(s,a) with the new estimate (high variance)
• If α is small, we average over many samples (lower variance, slower learning)
• The $\max$ operation ensures we're learning the optimal Q-values even if we're not acting optimally

The Complete Q-learning Algorithm

Initialize Q(s,a) arbitrarily for all s ∈ S, a ∈ A
Set Q(terminal, ·) = 0

For each episode:
    Initialize state s
    For each step of episode:
        Choose action a from s using policy derived from Q (e.g., ε-greedy)
        Take action a, observe reward r and next state s'
        
        Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)]
        
        s ← s'
    Until s is terminal

Why each component:

• ε-greedy exploration: Balance exploitation (choose max Q) with exploration (random action)
• Initialize Q arbitrarily: Algorithm converges regardless (proof via contraction mapping)
• Terminal states Q=0: No future value after episode ends
• Update after each step: Online learning, no need to wait for episode completion

Convergence Guarantees

What this means:

• Condition 1: Need exploration (ε-greedy ensures this)
• Condition 2: Learning rate must decrease but not too fast (e.g., $\alpha_t = 1/t$ works)
• Condition 3: Discounting ensures the operator "contracts" distances between Q-functions

Derivation of why it's a contraction:

For two Q-functions $Q_1$ and $Q_2$, the Bellman operator $\mathcal{T}$ applies:

$[\mathcal{T}Q](s,a) = \mathbb{E}[r + \gamma \max_{a'} Q(s',a')]$

The distance after applying $\mathcal{T}$:

$|\mathcal{T}Q_1 - \mathcal{T}Q_2||_\infty \leq \gamma ||Q_1 - Q_2||_\infty$

Since γ < 1, each application reduces the maximum difference by factor γ → convergence to unique fixed point $Q^*$.

Worked Examples

Initial: Q(s,a) = 0 for all s,a

Episode 1, Step 1:

• State s = (0,0), choose action a = right (random exploration)
• Observe: r = -1, s' = (0,1)
• Current: Q((0,0), right) = 0
• Target: r + γ max Q((0,1), ·) = -1 + 0.9×0 = -1
• Update: Q((0,0), right)← 0 + 0.1×(-1 - 0) = -0.1

Why this step? We learned that going right from start has value -0.1 (slightly negative because we got -1 reward and next state had no learned value yet).

Episode 1, Step 2:

• State s = (0,1), choose a = right
• Observe: r = -1, s' = (0,2)
• Update: Q((0,1), right) ← 0 + 0.1×(-1 - 0) = -0.1

Episode 5, Step 8 (after many updates):

• State s = (2,1), choose a = right
• Observe: r = -1, s' = (2,2) [goal]
• Current: Q((2,1), right) = -0.4 (from previous updates)
• Target: -1 + 0.9×10 = 8.0 (goal state has high value!)
• Update: Q((2,1), right) ← -0.4 + 0.1×(8.0 - (-0.4)) = -0.4 + 0.84 = 0.44

Why this matters? The +10 reward propagates backward! Now states leading to goal become valuable.

After 1000 episodes: Q((0,0), right) ≈ 5.8 (good path to goal) Q((0,0), down) ≈ 4.2 (longer path) The agent learned optimal policy: shortest path to goal.

Scenario:

• State s, optimal action a* has Q(s, a*) = 5
• Suboptimal action a₁ has Q(s, a₁) = 2
• Agent choses a₁ due to exploration, gets r=-1, s' with max Q(s',·) = 6

Update for the suboptimal action taken: Q(s, a₁) ← 2 + 0.1×[-1 + 0.9×6 - 2] = 2 + 0.1×2.4 = 2.24

Key insight: Even though agent took a₁ (not optimal), the update uses $\max Q(s',·)$ which represents optimal future behavior. The algorithm learns Q* while behaving suboptimally.

Compare to SARSA (on-policy): SARSA would use Q(s', a') where' is the actual next action taken (might be suboptimal due to ε-gredy). Q-learning's use of max makes it off-policy.

Common Mistakes and Steel-Manning

The steel-man: This concern is valid! Pure gredy selection gets stuck in local optima.

The fix: Q-learning the algorithm is separate from the behavior policy. Use ε-greedy or softmax for action selection to ensure exploration. The convergence theorem requires infinite visits to all (s,a) pairs—you must explore.

Practical tip: Start with highε (e.g., 0.3), decay over time (e.g., ε = 1/episode_number).

The steel-man: This is actually TRUE! It's called maximization bias. In stochastic environments, noise in Q-estimates makes max Q(s',·) overestimate true value.

The fix: Use Double Q-learning (Hasselt, 2010):

• Maintain two Q-functions: Q₁ and Q₂
• Use Q₁ to select best action:* = argmax Q₁(s',a)
• Use Q₂ to evaluate it: target = r + γ Q₂(s', a*)
• Update Q₁ (and vice versa, alternating)

Why this works: Selection and evaluation with independent estimates cancels the bias.

The steel-man: Mathematically correct for theoretical convergence to exact Q*.

The practical reality: Constant small α (e.g., 0.01-0.1) works better in practice because:

• Environments may be non-stationary (reward structure changes)
• Small constant α keeps adapting
• You reach "good enough" policy faster

When to decrease α: In fixed, deterministic environments where you want exact convergence.

Active Recall Flashcards

#flashcards/ai-ml

What are the three key properties of Q-learning? :: Model-free (no environment model needed), off-policy (learns optimal while behaving suboptimally), temporal-difference (bootstraps from estimates)

Write the Q-learning update rule and explain each term :: Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') - Q(s,a)]. α=learning rate, r=immediate reward, γ=discount, max Q(s',a')=optimal next state value, bracketed term=TD error

In a grid world, agent at (1,1) takes action right, receives=-1, reaches (1,2) where max Q=3. Current Q((1,1),right)=1. With α=0.2, γ=0.9, what's the new Q-value? :: Target = -1 + 0.9×3 = 1.7. TD error = 1.7 - 1 = 0.7. New Q = 1 + 0.2×0.7 = 1.14

Why can Q-learning use arbitrary initialization for Q(s,a)? :: The Bellman optimality operator is a contraction mapping when γ<1. Repeated application converges to unique fixed point Q* from any starting point, though initialization affects convergence speed.

Q-learning is like keeping a notebook where you write down scores for every choice you make. At each room, you try different doors and write: "Room A, go left: score = 5" or "Room A, go right: score = -2".

Here's the clever part: when you enter a new room, you look at your notebook to see which door from that room has the highest score you've written so far. You use that to update the score of the door you just came through!

Even if you're randomly exploring (picking doors by flipping a coin sometimes), your notebook learns what the best choices are. After lots of exploring, your notebook tells you the perfect path to the treasure, even though you took many wrong turns while learning.

The "Q" is just the name for the scores in your notebook. And you update them slowly (learning rate α) because one trip might be lucky or unlucky—you want to average many tries.

Visual: Picture a treasure map that draws itself as you explore randomly—the "max" operation always adds the best path found so far.

Connections

• Foundational to: Deep Q-Networks (DQN), Double Q-learning, Prioritized Experience Replay
• Contrasts with: SARSA (on-policy alternative), Policy Gradient Methods (directly optimize policy), Monte Carlo RL (waits for episode completion)
• Builds on: Bellman Equations, Temporal Difference Learning, Markov Decision Processes
• Requires: Exploration-Exploitation Trade-off, Function Approximation (for large state spaces)
• Applied in: Atari Game Playing, Robot Control, Resource Allocation
• Theoretical foundation: Dynamic Programming, Contraction Mapping Theorem, Stochastic Approximation

Last updated: 2026-07-01 | Review: Derive the update rule from scratch, explain why max enables off-policy learning

Concept Map

Hinglish (regional understanding)