Q-Learning: Model-Free Reinforcement Learning

A Swiggy delivery partner enters a gated apartment complex in Whitefield for the first time. GPS gets them to the compound's outer wall and stops being useful there — the last two hundred metres are internal lanes with no address mapping in any app: identical-looking rows of towers, one-way turns around a basement ramp, a security gate that loops back to where they started. Nobody hands them a blueprint of the complex before their first delivery. What they have instead is trial: turn left at this junction, lose ninety seconds circling a closed gate; take the ramp on the right, find a lane that cuts straight to Tower C. Across dozens of deliveries to the same complex, without ever seeing a floor plan, they build up a feel for which turn from which junction gets a parcel to a door fastest — purely from the outcomes of turns they have actually taken.

That is reinforcement learning with no model of the environment handed to the learner in advance. The algorithm that formalizes "learn the value of every action from raw experience, with no map of the world's rules" is Q-learning, introduced by Chris Watkins in 1989 and given its convergence proof with Peter Dayan in 1992. It is the algorithm that made reinforcement learning practical outside of toy problems where a full model was already known — and it is the direct ancestor of the deep Q-network that DeepMind used to play Atari games from raw pixels in 2015.

An Agent Without a Map

Translate the delivery scenario into the vocabulary of a Markov Decision Process (MDP), the formal object underlying all of reinforcement learning. A state s is the delivery partner's current junction. An action a is the turn they take from that junction — left, right, straight, or up the ramp. A reward r is the outcome of that turn: a small negative number for every minute spent, a large positive number on handing over the parcel. A policy π is the rule the partner eventually settles into — "at this junction, always take this turn." The object Q-learning builds is the action-value function Q(s, a): the total expected reward, from this point onward, of taking action a in state s and then behaving optimally forever after.

The one piece explicitly missing from this list is the transition function P(s′ | s, a) — the probability that taking action a in state s lands you in state s′. A city planner who had the complex's blueprint could compute P exactly: turn left at junction 4, you arrive at junction 7 with certainty. The delivery partner has no such document. They only ever observe one sampled outcome per turn: "I turned left at 4, and I ended up at 7, and it cost me a minute." Q-learning is built to learn optimal behaviour from exactly that kind of data — single sampled transitions — without ever needing P written down anywhere.

From MDP to "Model-Free"

This distinction has a name: model-based versus model-free reinforcement learning. Classical dynamic-programming methods — value iteration and policy iteration, which a Grade 11 syllabus typically meets just before reinforcement learning — require the full model: both P(s′ | s, a) and the reward function R(s, a) must be known so that the Bellman equation can be evaluated exactly, state by state, as a sweep over the whole MDP. That works beautifully for a board game with fixed, known rules. It fails the instant the environment is something the agent has never been given a specification of — a physical robot, a live market, an apartment complex with no digitized floor plan.

Q-learning removes that requirement entirely. It never estimates P or R as separate objects. It observes a stream of experience tuples (s, aᵗ, rₜ₊₁, sₜ₊₁) generated by actually acting in the environment, and updates a table of Q-values directly from those tuples. Nothing about the update rule below ever refers to a transition probability. That is precisely what "model-free" means: not that the agent learns nothing about the world, but that its learning algorithm never needs the world's transition and reward functions handed to it in closed form — it only needs to be able to act and observe what happens.

The Q-Function and the Bellman Optimality Equation

The target Q-learning is chasing is the optimal action-value function Q*(s, a): the value of taking action a in state s, then following the best possible policy forever after. Q* satisfies the Bellman optimality equation:

Q*(s, a) = E[ r + γ · maxₐ′ Q*(s′, a′) ]

Read the right-hand side left to right: r is the immediate reward for this one step. γ (gamma, the discount factor, 0 ≤ γ < 1) shrinks the value of rewards that arrive later, both because a rupee delivered sooner is worth more and because it keeps infinite-horizon sums finite. maxₐ′ Q*(s′, a′) is the value of the *best* action available from whichever state s′ you land in — not the average action, not a random one, the best one. The equation says: the value of a state-action pair equals what you get right now, plus the discounted value of playing perfectly from then on. It is recursive — Q* is defined in terms of itself one step later — which is exactly what makes it computable by repeated backups rather than by solving it in closed form.

The Q-Learning Update Rule

Q-learning never knows Q* in advance. It maintains a table of estimates, written simply Q(s, a), initialized arbitrarily (commonly all zeros), and nudges each entry toward the Bellman equation every time it observes a real transition:

Q(s, a) ← Q(s, a) + α [ r + γ · maxₐ′ Q(s′, a′) − Q(s, a) ]

The bracketed quantity is called the TD error (temporal-difference error), written δ. The term r + γ·maxₐ′ Q(s′,a′) — the reward just received plus the discounted best value of wherever you ended up — is called the TD target: it is a fresher, more informed estimate of what Q(s, a) should be, built from one real sample instead of pure guesswork. δ is simply how far the old estimate was from that fresher target. α ∈ (0, 1], the learning rate, controls how much of that gap gets absorbed into the table on this one update — a small α averages over many noisy samples slowly and stably, α = 1 throws the old estimate away entirely and replaces it with the newest sample. This single line, applied over and over on real transitions, is the entirety of Q-learning. No sweep over all states, no known transition matrix — just: act, observe (s, a, r, s′), update one cell of the table, repeat.

Choosing Actions: ε-Greedy Exploration

The update rule says how to revise a Q-value once you have a transition. It says nothing about which action to take to generate that transition — and this is where a second, separate decision has to be made at every step. Always taking the action with the highest currently-known Q-value (pure exploitation) risks locking onto a route that only looks best because it happens to be the only one tried so far — the delivery partner who always turns left at the first junction because their very first trip through it was lucky will never discover that the ramp on the right is faster. Always taking a random action (pure exploration) never uses anything that has been learned and wastes enormous amounts of experience.

ε-greedy resolves this with one parameter, ε ∈ [0, 1]. At every decision point, draw a random number in [0, 1): with probability ε, pick an action uniformly at random from all available actions, ignoring the Q-table entirely (explore); otherwise, pick argmaxₐ Q(s, a), the action the table currently rates highest (exploit). A common schedule starts ε high — near 1, almost pure exploration, when the table holds no information worth trusting — and decays it toward a small constant like 0.05 as training proceeds and the table's estimates become trustworthy.

Worked Example: Five Checkpoints to the Customer

Model a short, one-way delivery street as five checkpoints, numbered 0 to 4, with checkpoint 4 the customer's door — a terminal state. From any checkpoint the partner can move Left (toward 0) or Right (toward 4); moving off either end just leaves them where they were. Every move costs one minute, giving reward −1, except the move that lands exactly on checkpoint 4, which delivers the parcel and gives reward +10 with the episode ending. Set the learning rate α = 0.5 (deliberately large, to make the arithmetic legible by hand) and the discount factor γ = 0.9. All Q-values start at 0.00.

Suppose the partner's first two attempts happen to go Right at every checkpoint — 0→1→2→3→4. Apply the update rule at each step, using whatever Q-values exist at that instant (updates happen sequentially within an episode, so a later step in the same episode can never benefit from an update that only happens further down the same walk):

Notice what the table actually shows: after episode 1, every checkpoint’s Right-value moved off zero, but only Q(3, Right) moved positive — checkpoints 0, 1, and 2 each bootstrapped off a next-state value whose useful (max) component was still zero, so each only learned "moving costs a minute" and settled at −0.50. Only in episode 2, once Q(3, ·) is a nonzero 5.00, does checkpoint 2 finally see a positive signal and jump to 1.50. Checkpoint 1 is still stuck at −0.75, because at the moment its own update fires in episode 2, the bootstrap term max(0, Q(2, Right)) still evaluates to 0 — checkpoint 2's Right-value is already −0.50 by then, but the untouched Left action anchors the max at 0, so a negative Q-value cannot yet propagate a positive signal backward. Carrying the same arithmetic one episode further confirms the pattern precisely: in episode 3, Q(1, Right) rises from −0.75 to −0.20 (using episode 2's now-positive Q(2, Right)=1.50), while Q(0, Right) that same episode still only reaches −0.875, because checkpoint 1 hasn't turned positive yet either. Reward information is entering the table at the goal and crawling backward exactly one checkpoint per episode — this is the single most important intuition about how temporal-difference learning behaves on a chain, and it is the reason Q-learning on a long path can need very many episodes before the earliest states reflect a distant reward at all.

Tracing It in Code

The Python below implements exactly the environment and update rule used in the table above, forcing both episodes to walk Right at every checkpoint so the printed numbers can be checked directly against the hand-worked arithmetic.

import random
random.seed(0)

n_states = 5                 # checkpoints 0..4; 4 is the customer's door
actions = ['L', 'R']
alpha, gamma = 0.5, 0.9
Q = {(s, a): 0.0 for s in range(n_states) for a in actions}

def step(s, a):
    s_next = min(s + 1, n_states - 1) if a == 'R' else max(s - 1, 0)
    if s_next == n_states - 1:
        return s_next, 10.0, True         # parcel delivered, episode ends
    return s_next, -1.0, False

def run_episode(s, forced_actions):
    done = False
    i = 0
    while not done:
        a = forced_actions[i]
        s_next, r, done = step(s, a)
        best_next = 0.0 if done else max(Q[(s_next, a2)] for a2 in actions)
        Q[(s, a)] += alpha * (r + gamma * best_next - Q[(s, a)])
        s = s_next
        i += 1

run_episode(0, ['R', 'R', 'R', 'R'])
run_episode(0, ['R', 'R', 'R', 'R'])

for s in range(4):
    print(s, round(Q[(s, 'R')], 2))

Running this prints exactly:

0 -0.75
1 -0.75
2 1.5
3 7.5

which matches the hand-derived table cell for cell. Once the fixed trajectory is replaced with real ε-greedy choices, action selection looks like this — note that it reads the Q-table only to decide what to do, never to decide how to update it after the fact:

def choose_action(state, Q, actions, epsilon):
    if random.random() < epsilon:
        return random.choice(actions)              # explore
    q_values = [Q[(state, a)] for a in actions]
    best = max(q_values)
    best_actions = [a for a, q in zip(actions, q_values) if q == best]
    return random.choice(best_actions)              # exploit, ties broken randomly

Off-Policy, Not On-Policy: The Misconception

A student meeting Q-learning for the first time almost always assumes that because the agent is behaving ε-greedily — sometimes acting randomly — the update rule must somehow reflect that randomness. It does not, and this is worth stating precisely because it is the single most distinctive property of the algorithm.

Look again at the update: Q(s, a) ← Q(s, a) + α[r + γ·maxₐ′Q(s′, a′) − Q(s, a)]. The maxₐ′ Q(s′, a′) term is a maximum taken over every action available at s′ — it is not the Q-value of whatever action the agent actually happens to take next. The agent might, immediately after this update, roll a random number below ε and stumble left into a dead end at s′; the update just performed already assumed the agent would play the single best action from s′ onward, regardless of what it actually does. Q-learning is therefore learning the value of the greedy, optimal policy — the target policy — while its actual behaviour, the one generating the data, follows a different, more exploratory behaviour policy. Learning about one policy while acting according to another is precisely the definition of an off-policy algorithm.

Contrast this with SARSA, the on-policy sibling algorithm the CBSE syllabus sometimes places alongside Q-learning: its update is Q(s,a) ← Q(s,a) + α[r + γ·Q(s′, a′) − Q(s,a)], where a′ is the actual next action the agent is about to take — chosen by the same ε-greedy rule, and possibly a bad, exploratory one. SARSA folds the cost of its own occasional clumsiness into the values it learns; Q-learning does not — it learns the value of playing perfectly, even while its own training run is still stumbling around. This is exactly why a Q-learning agent trained near a cliff edge will happily learn a razor-thin optimal path along the edge, while a SARSA agent learns a slightly wider, safer margin — it has learned to account for its own occasional random step off-policy.

Convergence and Why Tables Stop Being Enough

Watkins and Dayan's 1992 proof guarantees that Q converges to Q* under three conditions: every state-action pair must be visited infinitely often (which is exactly why ε must never be allowed to reach zero during training), the learning rate must be decayed according to the Robbins-Monro conditions (Σα = ∞ but Σα² < ∞, so updates keep happening but shrink fast enough to settle), and rewards must be bounded. None of this requires the environment's dynamics to be known, deterministic, or even stationary within reason — only that the agent keeps sampling.

The five-checkpoint table above is small enough to hold in memory exactly, one cell per (state, action) pair. A real Swiggy routing problem has millions of possible junction configurations; a tabular Q-table simply cannot be built or visited often enough to fill every cell. That scaling wall — not any flaw in the update rule itself — is the entire motivation for replacing the table with a function approximator, most famously a neural network, giving Deep Q-Networks: the Bellman update above is unchanged, only Q(s, a) is now a network's output instead of a table lookup.

Active Recall

Attempt all six before reading the worked answers below.

1. Given Q(1, L) = 2.00, Q(1, R) = 3.00, and current Q(0, R) = 1.00, apply one Q-learning update for the transition (s=0, a=R, r=−2, s′=1, non-terminal) with α = 0.1, γ = 0.95.
2. Why is Q-learning called "model-free"? Name the one thing a model-based method like value iteration needs that Q-learning never computes.
3. Why is Q-learning classified as off-policy? State precisely which term in the update rule causes this, and contrast it with SARSA's corresponding term.
4. Using the five-checkpoint environment (rewards −1 per move, +10 on reaching checkpoint 4, γ = 0.9), compute the optimal values Q*(3, R), Q*(2, R), and Q*(1, R) by chaining the Bellman optimality equation backward from the goal.
5. What happens to Q-learning's updates if α = 1 at every step? What happens if α is fixed at a tiny value like 0.001 for the entire run?
6. In state 2, Q(2, L) = 1.5 and Q(2, R) = 2.0, with ε = 0.3. A random draw of 0.72 occurs, then later a random draw of 0.15 occurs. Which action does ε-greedy select each time, and why?

Worked answers

1. TD target = r + γ·max(Q(1,L), Q(1,R)) = −2 + 0.95 × 3.00 = −2 + 2.85 = 0.85. TD error = 0.85 − 1.00 = −0.15. New Q(0, R) = 1.00 + 0.1 × (−0.15) = 1.00 − 0.015 = 0.985.

2. Model-free means the update rule never needs the transition probabilities P(s′|s,a) or the reward function R(s,a) specified in advance — it only needs sampled (s, a, r, s′) tuples generated by acting. Value iteration, by contrast, needs the full P and R to sweep every state and compute an exact expectation over all possible next states at once.

3. The maxₐ′ Q(s′, a′) term in the update always uses the best action available at s′, regardless of which action the agent's ε-greedy policy actually selects next. SARSA replaces that term with Q(s′, a′) for the actual next action a′ chosen by the same exploring policy — so SARSA's learned values are contaminated by (and thus account for) its own exploratory mistakes, while Q-learning's are not. Learning the value of one (greedy) policy while behaving according to another (ε-greedy) is the definition of off-policy.

4. Q*(3, R) = 10 + 0.9 × 0 = 10.00 (immediate reward, terminal next state contributes nothing). Q*(2, R) = −1 + 0.9 × 10.00 = −1 + 9.00 = 8.00. Q*(1, R) = −1 + 0.9 × 8.00 = −1 + 7.20 = 6.20.

5. With α = 1, each update discards the old estimate completely and replaces it with the newest single sample — the table stops averaging over noise entirely, so in any stochastic environment the values swing wildly and never settle. With α = 0.001, each update moves the table by essentially nothing, so learning proceeds so slowly that the table would need an impractically large number of episodes to approach Q* even though it is, in principle, still converging.

6. 0.72 > ε (0.3), so the draw falls in the exploit branch: the agent takes argmaxₐ Q(2, a) = R, since Q(2,R)=2.0 > Q(2,L)=1.5. 0.15 < ε (0.3), so this draw falls in the explore branch: the agent ignores the Q-values entirely and picks uniformly between L and R, each with 50% probability — it could pick either one regardless of which has the higher value.

Think About It

Think about this: How would you explain q-learning: model-free reinforcement learning to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where q-learning: model-free reinforcement learning is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting q-learning: model-free reinforcement learning to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind q-learning: model-free reinforcement learning, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.