Reinforcement Learning1992foundational10 min read

Q-Learning

تعلُّم دالة الجودة (Q-Learning)

Watkins, C. J. C. H. · Dayan, P. — Machine Learning

The problem

Before , algorithms either required a complete model of the () or could only learn from the they were currently following (on-policy methods like SARSA). How can an learn the optimal behavior purely from trial and error, without a model, and while following any exploratory policy it likes?

The contribution

A simple, model-free, algorithm that learns the optimal Q* directly from experience. At each step, the agent updates its using the Bellman optimality equation: the current plus the discounted maximum future value. Because the update always uses the max over next actions — not the action actually taken — Q-Learning learns the regardless of the strategy used. Watkins and Dayan proved it converges to Q* with probability 1 under mild conditions.

The impact

Q-Learning became the foundational algorithm of value-based reinforcement learning. It directly inspired DQN (2013), which combined Q-Learning with deep neural networks and achieved superhuman Atari play — launching the deep RL revolution. Its descendants include CQL for offline RL, the Options Framework for hierarchical RL, and countless real-world applications from robotics to recommendation systems. Every value-based RL method today traces its lineage to this 1989 algorithm.

Imagine a restaurant critic exploring a city. She doesn't have a guide telling her which restaurants are good — she simply tries one, rates her experience, and writes it in her notebook.

But she's clever: after eating at restaurant B, she also updates her score for restaurant A (which sent her to B via a recommendation). Over months, her notebook converges to a perfect rating of every restaurant — even ones she only visited once — because each visit propagates value backward through the chain of recommendations.

Q-Learning is that notebook. Each entry is a -action pair, each meal is an , and the propagation of ratings is the Bellman update.

The problem: learning without a map

In reinforcement learning, an agent interacts with an environment: at each time step it observes a state, takes an action, receives a reward, and transitions to a new state. The goal is to find a policy — a rule mapping states to actions — that maximizes total cumulative reward.

Before Q-Learning, two families of solutions existed:

Dynamic programming (like value iteration) could find optimal policies, but required a complete model of the environment: all transition probabilities and rewards. For most real problems, this model is unknown.
On-policy TD methods (like SARSA) could learn from experience, but they could only learn the value of the policy they were currently following. If that policy was exploratory (taking random actions sometimes), the learned values reflected the exploration, not the optimal behavior.

The fundamental question was: can an agent learn the optimal policy purely from experience, without a model, while freely exploring?

Open in Lab

Watch the agent explore a grid world. The Q-table updates in real time — notice how values propagate backward from the goal.

The demo wakes as you arrive…

The idea: learn from the best possible future

Q-Learning assigns a value $Q(s, a)$ to every state-action pair: "how good is it to take action $a$ in state $s$ ?" This value represents the total discounted reward the agent expects if it takes $a$ now and then acts optimally forever after.

The key insight is in how Q-Learning updates this value. After taking action $a$ in state $s$ , receiving reward $r$ , and landing in state $s'$ , the update is:

Q(s, a) \;\leftarrow\; Q(s, a) \;+\; \alpha \Big[\, r \;+\; \gamma \max_{a'} Q(s', a') \;-\; Q(s, a) \,\Big]

The Q-Learning update rule — α is the learning rate (how fast we update), γ is the discount factor (how much we value the future), and the max picks the best action in the next state — regardless of which action was actually taken.

Let's unpack the term inside the brackets — the (TD) error:

$r$ is the immediate reward — the feedback the environment just gave.
$\gamma \max_{a'} Q(s', a')$ is the best possible future value from the next state. This is where the magic lies: the agent doesn't use the value of the action it will take — it uses the value of the action it should take. This is what makes Q-Learning off-policy.
$Q(s, a)$ is the current estimate — what the agent thought the value was.

The TD error is the gap between "what actually happened + best future" and "what I predicted." The agent shrinks this gap by a fraction α each step. Over time, the estimates converge to the true optimal values.

Open in Lab

Step through the Q-Learning update. Watch the TD error shrink as the Q-value absorbs the reward signal from the future.

The demo wakes as you arrive…

The breakthrough: off-policy learning

The $\max$ operator in the update rule is what separates Q-Learning from its predecessors. Consider the alternative, SARSA, which updates using the action the agent actually takes next:

Q_{\text{SARSA}}(s, a) \;\leftarrow\; Q(s, a) + \alpha \Big[\, r + \gamma\, Q(s', a') \;-\; Q(s, a) \,\Big]

SARSA update (on-policy) — uses the actual next action a'

If the agent is exploring with an strategy (choosing random actions ε% of the time), SARSA's learned values include the cost of those random actions. It learns the value of the exploratory policy, not the optimal one.

Q-Learning's max ignores what the agent actually did and asks: "what's the best I could do from here?" This decouples the (how the agent explores) from the (what the agent is learning about). The agent can explore wildly and still learn the optimal strategy — like a student who learns from textbook examples while solving messy practice problems.

Open in Lab

Compare on-policy (SARSA) vs off-policy (Q-Learning) updates. Notice how Q-Learning's values converge to the optimal path while SARSA's reflect the exploratory detours.

The demo wakes as you arrive…

Exploration vs. exploitation: the ε-greedy strategy

Q-Learning says nothing about how to choose actions during learning — only about how to update Q-values. But the choice matters: the agent must try every state-action pair enough times for the Q-values to converge.

The simplest and most common strategy is ε-greedy: with probability $1 - \varepsilon$ take the greedy action (the one with the highest Q-value), and with probability $\varepsilon$ take a random action. This ensures every action gets tried infinitely often — a requirement for the proof.

In practice, $\varepsilon$ starts high (e.g. 1.0 — fully random) and decays over time toward a small value (e.g. 0.05), gradually shifting from exploration to as the agent's knowledge improves.

Open in Lab

Drag the ε slider to see the tradeoff. High ε = lots of exploration, slow convergence. Low ε = fast convergence but risk of missing better paths.

The demo wakes as you arrive…

Convergence: why it actually works

Watkins and Dayan (1992) proved that Q-Learning converges to the true optimal action-value function $Q^*$ with probability 1, provided three conditions hold:

Every state-action pair is visited infinitely often. The ε-greedy strategy guarantees this.
The satisfies: $\sum \alpha_t = \infty$ and $\sum \alpha_t^2 < \infty$ . In practice, a slowly decaying learning rate works.
The rewards are bounded. No infinite payoffs.

The proof strategy mirrors theory: the Q-Learning update is a noisy . Each update brings Q closer to Q* (contraction), and the noise averages out over time (stochastic averaging). The γ < 1 ensures the contraction is strict, and the learning rate conditions ensure the noise vanishes.

Q_t(s,a) \;\xrightarrow{t \to \infty}\; Q^*(s,a) \quad \text{w.p. 1} \quad \forall\; s, a

Convergence guarantee — As the number of updates grows, every Q-value converges to the optimal value with probability 1 — meaning Q-Learning will eventually find the best action in every state.

The Q-Table: a cheat-sheet for optimal behavior

In the tabular setting, Q-values are stored in a table with one row per state and one column per action. After convergence, the optimal policy is trivially extracted: for each state, pick the action with the highest Q-value.

\pi^*(s) = \arg\max_{a} Q^*(s, a)

Optimal policy extraction — Once Q* is known, the optimal policy is deterministic: always pick the action with the highest Q-value.

The complete algorithm

Q-Learning with ε-greedy explorationpython

Simplified to show the idea — not the real implementation.

import numpy as np
def q_learning(env, n_episodes=1000, alpha=0.1, gamma=0.99,
                epsilon_start=1.0, epsilon_end=0.05, decay=0.995):
    """
    Tabular Q-Learning.
    env: environment with .reset(), .step(action), .n_states, .n_actions
    """
    Q = np.zeros((env.n_states, env.n_actions))

    epsilon = epsilon_start
    for episode in range(n_episodes):
        state = env.reset()
        done = False

        while not done:
            # ε-greedy action selection
            if np.random.random() < epsilon:
                action = np.random.randint(env.n_actions)   # explore
            else:
                action = np.argmax(Q[state])                # exploit

            next_state, reward, done = env.step(action)

            # Q-Learning update: use MAX over next actions (off-policy)
            td_target = reward + gamma * np.max(Q[next_state]) * (1 - done)
            td_error  = td_target - Q[state, action]
            Q[state, action] += alpha * td_error

            state = next_state

        # Decay exploration rate
        epsilon = max(epsilon_end, epsilon * decay)

    return Q

Connection to the Bellman equation

Q-Learning is really an incremental, sample-based solver for the Bellman optimality equation. The for Q* says:

Q^*(s, a) = \mathbb{E}\Big[\, r + \gamma \max_{a'} Q^*(s', a') \;\Big|\; s, a \,\Big]

Bellman optimality equation for Q*

Dynamic programming solves this equation exactly but needs the full model (to compute the expectation). Q-Learning replaces the expectation with a single sample — the actual $(r, s')$ the agent observed — and corrects incrementally. Over many samples, the single-sample estimates average out to the true expectation, and the Q-values converge to Q*.

Think of it this way: dynamic programming is solving a system of equations with algebra. Q-Learning is solving it by measuring: take a reading, adjust, take another reading, adjust. Both reach the same answer, but Q-Learning needs no blueprint of the system.

Limitations of tabular Q-Learning

Tabular Q-Learning works beautifully in small, discrete environments. But it hits a wall when the state or action space grows large:

Memory: a 100×100 grid with 4 actions needs 40,000 Q-values. A game like Chess or Go has more states than atoms in the universe.
Generalization: tabular Q-Learning treats every state as independent. It can't recognize that nearby states should have similar values.
Continuous spaces: if the state is a robot's joint angles (continuous), there is no finite table to fill in.

These limitations motivated the move to function approximation — replacing the Q-table with a that can generalize across states. This is exactly what DQN did in 2013, combining Q-Learning with deep neural networks to play Atari games directly from pixels.

Historical evolution

1957
Bellman — Dynamic Programming
Richard Bellman formulates the optimality equation that decomposes multi-stage decisions into recursive subproblems. Q-Learning's update rule is a sample-based version of this equation.
1988
Sutton — TD Learning
Richard Sutton formalizes temporal difference learning: update predictions based on the difference between successive predictions, not waiting for the final outcome. Q-Learning inherits this one-step bootstrap idea.
1989
Watkins — Q-Learning proposed
Christopher Watkins proposes Q-Learning in his PhD thesis "Learning from Delayed Rewards" at Cambridge. The first off-policy, model-free control algorithm with convergence guarantees.
1992
Watkins & Dayan — Convergence proof published
The formal convergence proof is published in Machine Learning journal, establishing Q-Learning's theoretical foundations and making it the standard off-policy RL algorithm.
1999
Sutton et al. — Options Framework
Extends Q-Learning to hierarchical RL: "options" are temporally extended actions (macro-actions), and option-values are learned via a Q-Learning-like update.
2013
Mnih et al. — DQN
Deep Q-Network replaces the Q-table with a neural network, adds experience replay and a target network, and achieves superhuman Atari play. The deep RL era begins.
2020
Kumar et al. — CQL
Conservative Q-Learning addresses the offline RL setting: learn a policy from a fixed dataset by penalizing Q-values for unseen actions, preventing overestimation of out-of-distribution state-action pairs.

From Bellman's equation on paper to DQN mastering Atari from pixels — the thread is Q-Learning. Every value-based deep RL algorithm today, from Rainbow to SAC's critic, is a direct descendant of Watkins' 1989 insight: use the max, ignore the policy, learn the best.

CitationWatkins, C. J. C. H., Dayan, P.. Q-Learning. Machine Learning 8(3-4), 1992.

Terms in this paper

Q-Learningتعلم دالة الجودة (Q)
Action-Value Function (Q-Function)دالة قيمة الفعل المتخذ
Bellman Equationمعادلة بيلمان الرياضية
Temporal Differenceالفارق الزمني الحسابي
Off-Policyخوارزمية التعلم خارج السياسة الحالية
Model-Free RLالتعلم بالتعزيز المباشر (دون نموذج بيئة)
Exploration-Exploitation Dilemmaمعضلة المفاضلة بين الاستكشاف والاستغلال
ε-Greedyسياسة إبسيلون الجشعة
Q-Tableجدول قيم الجودة
Discount Factorمُعامل الخصم
Convergenceالتقارب الحسابي
Contraction Mappingالتقليص الانكماشي
Maximization Biasانحياز التعظيم