Q-Learning: Complete Guide — Reinforcement Learning

Summary

Q-Learning is one of the foundational algorithms of reinforcement learning. Introduced by Christopher Watkins in 1989, it enables an agent to learn an optimal policy — that is, the best sequence of actions to take in each situation — without prior knowledge of the environment’s dynamics. Its principle is both elegant and powerful: the agent maintains a table of values, called the Q-table, which associates with each (state, action) pair an estimate of the expected cumulative future reward. Through the Bellman equation, this table is updated iteratively with each interaction with the environment, progressively converging toward optimal values. Q-Learning is a model-free algorithm: it requires no prior knowledge of transition probabilities between states. This characteristic makes it particularly well-suited to complex environments where analytical modeling is impossible or too costly.

Mathematical Principle of Q-Learning

The Q-table: the agent’s memory

At the heart of Q-Learning lies the Q-table, a data structure that stores for each state s and each possible action a the value Q(s, a). This value represents the estimate of the future cumulative reward that the agent can expect to obtain by executing action a from state s, then following the optimal policy thereafter.

Formally, the Q-table is a matrix of dimensions |S| × |A|, where S is the set of states and A is the set of actions. Initially, all values are set to zero (or to random values). As the agent explores the environment, these values are adjusted to reflect accumulated experience.

The Bellman Equation

The Q-table update is based on the Bellman equation, which constitutes the theoretical foundation of Q-Learning. At each transition from state s to state s’ after applying action a and receiving reward r, the value Q(s, a) is updated according to the following formula:

Q(s, a) ← Q(s, a) + α · [r + γ · max_a’ Q(s’, a’) − Q(s, a)]

Let’s break down each term of this fundamental equation:

• Q(s, a): the current estimated value for the state-action pair.
• α (alpha): the learning rate, between 0 and 1. It determines the importance given to new information relative to the old estimate. A high value (close to 1) means the agent places great importance on recent experiences, while a low value (close to 0) favors the stability of existing estimates.
• r: the immediate reward received after executing action a in state s.
• γ (gamma): the discount factor, between 0 and 1. It weights the importance of future rewards relative to immediate rewards. When γ is close to 0, the agent is “short-sighted” and prioritizes immediate rewards. When γ is close to 1, the agent plans for the long term.
• max_a’ Q(s’, a’): the maximum Q-value among all possible actions in the new state s’. This term represents the best estimate of the future reward the agent can expect from the new state.
• [r + γ · max_a’ Q(s’, a’) − Q(s, a)]: the Temporal Difference error (TD error), which measures the gap between the previous estimate and the new estimate incorporating the observed reward.

The Bellman equation thus performs a weighted average between the old estimate and the new information. This incremental approach guarantees that values converge toward optimality provided each (state, action) pair is visited a sufficient number of times.

The epsilon-greedy policy: balancing exploration and exploitation

A central challenge in reinforcement learning is the exploration-exploitation dilemma: should the agent exploit current knowledge to maximize immediate rewards, or explore new actions to potentially discover better strategies?

Q-Learning resolves this dilemma through the epsilon-greedy policy:

• With probability ε (epsilon), the agent chooses a random action (exploration). This allows it to discover states and actions it has not yet sufficiently explored.
• With probability (1 − ε), the agent chooses the action that maximizes the Q-value in the current state, i.e., argmax_a Q(s, a) (exploitation). It then uses its current knowledge to make the best possible decision.

In practice, ε is initially high (e.g., 1.0, meaning 100% exploration) and then decays progressively over episodes according to a decay rate. Thus, the agent explores heavily at the beginning, then increasingly exploits its acquired knowledge. This strategy guarantees both coverage of the state space and convergence toward the optimal policy.

Intuition: the rat in the maze

To understand Q-Learning intuitively, imagine a rat released into a maze with cheese placed at the exit. The rat does not know the layout of the maze: it must learn by trial and error.

Each time the rat turns left and finds a wall, it suffers a small “punishment” (a shock, frustration). It then memorizes that “in this precise situation, turning left is a bad idea.” The next time it finds itself at the same intersection, it will probably avoid that direction.

Conversely, each time it takes a corridor that brings it closer to the cheese, it receives a positive reward. It memorizes that “this direction is beneficial.” Gradually, the rat builds a mental map of good and bad paths in its head — this is exactly what the Q-table is!

At the beginning, the rat explores randomly: it turns left, right, turns around, bumps into walls. But with each attempt, it updates its mental map according to the Bellman equation. After several hundred attempts, it has acquired enough experience to systematically choose the shortest path to the cheese.

The parameter ε plays a crucial role in this analogy: a high ε means the rat is curious and regularly tries new paths (even if it already knows a working path). A low ε means the rat follows its mental map with confidence. By progressively decreasing ε, we simulate a rat that becomes increasingly expert in its maze, while retaining a small amount of curiosity to occasionally check whether a better path exists.

This metaphor perfectly illustrates why Q-Learning is so powerful: it requires no prior map of the maze, no knowledge of transition probabilities. It learns purely through experience, exactly as a living being would learn in the real world.

Python Implementation

Q-Learning on FrozenLake with Gym

The FrozenLake environment from the OpenAI Gym library is an ideal textbook case for Q-Learning. It is a 4×4 grid where the agent must navigate from the start cell (S) to the goal cell (G) while avoiding holes (H) scattered across the ice (F). Since the ice is slippery, actions are not always executed with certainty: this introduces randomness and makes the problem more realistic.

Here is a complete implementation of Q-Learning on FrozenLake:

import numpy as np
import gym
import matplotlib.pyplot as plt

def q_learning(
    n_episodes=10000,
    alpha=0.1,
    gamma=0.99,
    epsilon=1.0,
    epsilon_decay=0.995,
    epsilon_min=0.01,
    env_name="FrozenLake-v1",
    is_slippery=True,
    seed=42
):
    """
    Complete implementation of Q-Learning on the FrozenLake environment.

    Parameters:
        n_episodes: number of training episodes
        alpha: learning rate
        gamma: discount factor
        epsilon: initial exploration rate
        epsilon_decay: epsilon decay rate
        epsilon_min: minimum epsilon value
        env_name: Gym environment name
        is_slippery: if True, the ice is slippery (random)
        seed: random seed for reproducibility

    Returns:
        q_table: the learned Q-table
        rewards_history: history of rewards per episode
    """

    # Environment initialization
    env = gym.make(env_name, is_slippery=is_slippery)
    np.random.seed(seed)
    env.reset(seed=seed)

    n_states = env.observation_space.n
    n_actions = env.action_space.n

    # Q-table initialization: all values set to zero
    q_table = np.zeros((n_states, n_actions))

    # Reward tracking for convergence visualization
    rewards_history = []

    for episode in range(n_episodes):
        state = env.reset()[0]
        total_reward = 0
        done = False

        while not done:
            # Epsilon-greedy policy
            if np.random.random() < epsilon:
                action = env.action_space.sample()  # Random exploration
            else:
                action = np.argmax(q_table[state])  # Exploit best Q

            # Execute action in the environment
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated

            # Q-table update via Bellman equation
            best_next_q = np.max(q_table[next_state])
            q_table[state][action] = q_table[state][action] + alpha * (
                reward + gamma * best_next_q - q_table[state][action]
            )

            state = next_state
            total_reward += reward

        rewards_history.append(total_reward)

        # Epsilon decay after each episode
        epsilon = max(epsilon_min, epsilon * epsilon_decay)

    env.close()
    return q_table, rewards_history


def policy_extraction(q_table, n_states=16):
    """
    Extracts the optimal policy from the Q-table.
    Displays the grid with recommended actions.

    Action mapping: 0=Left, 1=Down, 2=Right, 3=Up
    """
    arrows = ['←', '↓', '→', '↑']
    grid_size = 4

    print("Optimal policy extracted from Q-table:")
    print("=" * 30)

    policy = np.argmax(q_table, axis=1)
    grid = []

    for i in range(n_states):
        grid.append(arrows[policy[i]])
        if (i + 1) % grid_size == 0:
            print("  ".join(grid[-grid_size:]))
            grid = grid[:-grid_size]

    print("=" * 30)
    return policy


def visualize_convergence(rewards_history, window_size=100):
    """
    Visualizes learning convergence with a moving average.

    Parameters:
        rewards_history: list of rewards per episode
        window_size: window size for the moving average
    """
    rewards = np.array(rewards_history)

    # Compute moving average
    cumsum = np.cumsum(np.insert(rewards, 0, 0))
    moving_avg = (cumsum[window_size:] - cumsum[:-window_size]) / window_size

    # Create plot
    fig, ax = plt.subplots(figsize=(12, 6))

    ax.plot(rewards, alpha=0.3, color='gray', label='Reward per episode')
    ax.plot(range(window_size - 1, len(rewards)), moving_avg,
            color='blue', linewidth=2, label=f'Moving average ({window_size} episodes)')

    ax.set_xlabel("Episode", fontsize=12)
    ax.set_ylabel("Cumulative reward", fontsize=12)
    ax.set_title("Q-Learning Convergence on FrozenLake", fontsize=14)
    ax.legend(fontsize=11)
    ax.grid(True, alpha=0.3)
    ax.set_ylim(-0.1, 1.1)

    plt.tight_layout()
    plt.savefig("qlearning_convergence.png", dpi=150)
    plt.show()

    return moving_avg


# --- Main execution ---
if __name__ == "__main__":
    # Model training
    q_table, rewards = q_learning(
        n_episodes=10000,
        alpha=0.1,
        gamma=0.99,
        epsilon=1.0,
        epsilon_decay=0.995,
        epsilon_min=0.01
    )

    # Extract and display optimal policy
    policy = policy_extraction(q_table)

    # Success rate over the last 100 episodes
    success_rate = np.mean(rewards[-100:])
    print(f"Success rate (last 100 episodes): {success_rate:.1%}")

    # Visualize convergence
    moving_avg = visualize_convergence(rewards)

Introduction to Deep Q-Network (DQN)

Classical Q-Learning works remarkably well for environments with a limited number of discrete states. However, when the state space becomes very large — or continuous, such as video games with images as input — the Q-table becomes impractical. Imagine a table with billions or even trillions of rows!

This is where the Deep Q-Network (DQN), introduced by DeepMind in 2013, comes in. The central idea is brilliant in its simplicity: instead of storing the Q-table in an explicit matrix, a deep neural network is used to approximate the Q function. The network takes the state as input (e.g., the pixels of a game screen) and produces as output the Q-values for each possible action.

This approach has several major advantages. First, it enables generalization: the network can estimate Q-values for states it has never seen before, based on similarity with known states. Second, it eliminates the need for explicit memory proportional to the number of states. Third, it makes it possible to apply Q-Learning to direct perception problems, such as playing video games from raw screen pixels.

The DQN also introduces two important technical innovations to stabilize learning: the replay buffer, which stores past experiences and reuses them randomly to break temporal correlations, and the target network, a periodically updated copy of the main network that provides stable targets for the Bellman equation. The DQN achieved superhuman performance on many Atari games, demonstrating the power of this approach.

Q-Learning Hyperparameters

The proper functioning of Q-Learning depends closely on the tuning of its hyperparameters. Understanding their role is essential to achieving good performance.

α — The learning rate

The α parameter controls the speed at which the agent integrates new information. With α = 1, each new experience completely replaces the old estimate. With α = 0.1, the agent only gradually adjusts its beliefs, making learning more stable but slower.

In practice, a typical value lies between 0.01 and 0.2. For noisy environments, it is preferable to use a low α to prevent aberrant rewards from excessively disrupting the Q-table. α can also be decayed over time, similarly to ε.

γ — The discount factor

The γ parameter determines the agent’s time horizon. With γ = 0, the agent is solely motivated by the immediate reward, ignoring the future consequences of its actions. With γ = 0.99, the agent plans for the very long term, giving nearly as importance to distant rewards as to immediate ones.

The choice of γ depends on the nature of the environment. For problems where rewards are primarily immediate (e.g., a robot that must avoid obstacles in real time), a low γ (0.8–0.9) is appropriate. For problems where rewards are delayed (e.g., a chess game where victory only occurs after dozens of moves), a high γ (0.95–0.99) is necessary.

ε — The initial exploration rate

The ε parameter sets the exploration probability at the beginning of training. Generally, ε is initialized to 1.0 (total exploration) so that the agent freely explores the environment at the start. If the agent went directly into exploitation mode with an empty Q-table, it would remain trapped in a suboptimal policy without ever discovering better alternatives.

decay_rate — The epsilon decay rate

The decay_rate determines how quickly ε decreases. With a decay_rate = 0.995, ε is multiplied by 0.995 after each episode. Over 10,000 episodes, ε goes from 1.0 to approximately 10⁻²² — meaning that after enough episodes, the agent exploits its knowledge almost exclusively.

A decay_rate that is too high leads to insufficient exploration: the agent stops exploring before having discovered all important regions of the state space. A decay_rate that is too low unnecessarily slows convergence. A typical value lies between 0.99 and 0.999.

n_episodes — The number of episodes

The number of episodes determines the total training duration. For simple environments like FrozenLake 4×4, 5,000 to 10,000 episodes are generally sufficient. For more complex environments, hundreds of thousands of episodes may be necessary.

A useful indicator for determining whether the number of episodes is sufficient is the convergence of the moving average of rewards: when it stabilizes, the agent has likely learned the optimal policy (or at least a policy of satisfactory quality).

Advantages and Limitations of Q-Learning

Advantages

• Conceptual simplicity: the algorithm is relatively simple to understand and implement. The Bellman equation fits in one line of code.
• Model-free: no prior knowledge of the environment’s dynamics is required. Learning is done entirely through direct interaction.
• Guaranteed convergence: under certain conditions (sufficient exploration, properly decreasing learning rate), Q-Learning mathematically converges toward the optimal Q function Q*.
• Computational lightness: for environments of modest size, the algorithm is extremely fast and requires little memory resources.
• Versatility: applicable to many domains, from video games to robotics, to financial portfolio management.
• Interpretability: the Q-table is directly readable and understandable. The optimal policy can be extracted and visualized at any time.

Limitations

• Curse of dimensionality: the size of the Q-table grows exponentially with the number of states and actions. For complex environments, the table becomes unmanageable.
• Continuous states: classical Q-Learning only works with discrete states. For continuous state spaces, one must either discretize (with a loss of information) or switch to function approximation methods like the DQN.
• Hyperparameter sensitivity: the choice of α, γ, ε, and decay_rate strongly influences performance. Poor tuning can lead to divergence or convergence to a suboptimal policy.
• Overestimation: Q-Learning tends to overestimate Q-values, especially in noisy environments. This bias stems from the use of max in the Bellman equation. Variants such as Double Q-Learning have been proposed to correct this problem.
• Learning slowness: in environments with delayed or sparse rewards, the agent can take a prohibitively long time to discover the first positive rewards.
• Explicit memory: each (state, action) pair must be stored individually, which poses scaling problems for environments with a large number of states.

4 Concrete Use Cases of Q-Learning

1. Autonomous Navigation of Mobile Robots

A mobile robot in a logistics warehouse can use Q-Learning to learn to navigate efficiently between shelves. Each discretized position in the warehouse constitutes a state, the movement directions are the actions, and rewards are assigned based on proximity to the destination and obstacle avoidance. The robot thus learns to optimize its routes without needing a precise map of the warehouse, dynamically adapting to configuration changes.

2. Traffic Light Optimization

In an urban traffic light network, each intersection can be modeled as a state (traffic and light configuration), actions correspond to light phase changes, and rewards are inversely proportional to the average vehicle waiting time. Q-Learning makes it possible to optimize traffic light synchronization in real time, significantly reducing congestion. Studies have shown reductions of 15 to 30% in average travel time through this approach.

3. Automated Trading Algorithms

In quantitative finance, Q-Learning can be applied to trading decision-making. States represent market configurations (prices, volumes, technical indicators), actions are “buy,” “sell,” or “hold,” and rewards correspond to realized gains or losses. Although financial markets are notoriously non-stationary and noisy, advanced variants of Q-Learning combined with signal processing techniques have shown promising results for certain high-frequency trading strategies.

4. Personalized Content Recommendation

Streaming and e-commerce platforms use Q-Learning-inspired approaches to personalize their recommendations. Each user is in a state (their profile and browsing history), actions are the content offered, and rewards are the observed interactions (clicks, viewing time, purchases). The algorithm thus learns to maximize engagement for each individual user, continuously adapting to the evolution of their preferences.

See Also

• Mastering Duodigits in Python: Complete Guide to Optimizing Your Numerical Calculations
• Mastering Project Permutations with Python: Complete Guide for Developers