Q-Learning Algorithm

Q-Learning is a model-free reinforcement learning algorithm where an agent learns the best actions through trial and error without knowing the environment’s rules. The agent uses a Q-table to estimate the “quality” (Q-value) of each action in a given state, updating it based on the rewards received. Over time, it learns to maximize long-term rewards by balancing exploration (trying new actions) and exploitation (choosing the best-known actions).

Analogy: Like navigating a maze, the agent tries paths, gets points for reaching the goal or penalties for hitting walls, and gradually favors paths with higher rewards.

The core of Q-Learning is the Q-table, which stores Q-values — estimates of how good it is to take a particular action in a given state based on expected future rewards. The agent updates this table over time using feedback from the environment, gradually learning the actions that maximize long-term rewards.

Why Use Q-Learning?

1. Model-Free Learning

• Q-Learning does not require a model of the environment. The agent learns purely from interactions, which makes it suitable for complex or unknown environments.

2. Optimal Decision Making

• It helps an agent learn the best actions to take in any state to maximize long-term rewards, not just immediate gains.

3. Trial-and-Error Learning

• The algorithm uses a feedback-driven, trial-and-error approach, allowing the agent to improve even without explicit instructions.

4. Balances Exploration and Exploitation

• With the ϵ-greedy policy, the agent can explore new strategies while exploiting known good actions, leading to better overall performance.

5. Versatile Applications

• Useful in robotics, game AI, navigation, recommendation systems, and any scenario requiring sequential decision-making.

Importance:
Q-Learning is important because it provides a simple yet powerful way for machines to learn optimal behavior in dynamic, uncertain environments, making it a foundational tool in reinforcement learning and AI.

How Does Q-Learning Works?

Step-by-Step Process of Q-Learning

1. Initialize the Starting State

• The agent begins in an initial state, representing the current situation in the environment.

2. Choose an Action

The agent decides on an action using its policy. Typically, it follows an ε-greedy approach:

• Sometimes it explores by selecting a random action.
• Most of the time it exploits by picking the action with the highest estimated reward from the Q-table.

3. Perform the Action and Observe Feedback

After executing the action, the environment provides:

• A new state resulting from the action.
• A reward, indicating how good or bad the action was.

4. Update Knowledge (Q-Table)

• The agent adjusts the Q-value for the state-action pair based on the received reward and the new state.
• This update uses the temporal difference rule, improving the agent’s estimates of long-term benefits.

5. Repeat and Improve Policy

• With updated Q-values, the agent gradually refines its policy.
• By repeatedly cycling through states, actions, rewards, and updates across many episodes, it learns the optimal strategy that maximizes cumulative rewards.

Methods for Determining Q-Values

1. Temporal Difference (TD) Learning

• TD calculates Q-values by comparing the current estimate with new experiences.
• It allows the agent to learn directly from interactions with the environment, without needing a complete model.
• Updates are incremental, adjusting Q-values after each action based on received rewards and the estimated value of the next state.

2. Bellman’s Equation

• Provides a recursive way to calculate the optimal Q-value for a state-action pair.
• Expressed as:

Q ( s , a ) = R ( s , a ) + γ maxQ (s′ , a )

Get Shakeraafreen’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Where:

• Q(s,a) = value of taking action a in state s
• R(s,a) = immediate reward for that action
• γ (gamma) = discount factor, weighing future rewards
• max_a Q(s′,a) = best possible value achievable from the next state s′
• Fundamental to Q-Learning, it helps the agent estimate the total expected reward when choosing an action.

What is Q-Table?

A Q-table acts like the agent’s learning record in reinforcement learning. It keeps track of how useful each action is in every possible state based on rewards the agent has experienced.

The table is organized so that states form the rows, actions form the columns, and each cell contains a Q-value showing the expected reward for choosing that action in that state. As the agent interacts with the environment, these values are updated. With time and experience, the Q-table guides the agent toward choosing actions that give the highest rewards.

Implementation:

Q-Learning in a 4×4 Grid Environment

In this example, an agent learns how to reach a target cell in a 4×4 grid world by interacting with the environment and improving its action choices over time.

Step 1: Environment Setup

The grid contains 16 states (0–15).
Each state represents a grid position, and the agent can move in four directions.

import numpy as np
import matplotlib.pyplot as plt

states_count = 16
actions_count = 4
terminal_state = 15

Q_matrix = np.zeros((states_count, actions_count))

Step 2: Learning Parameters

These values control how the agent learns and balances exploration and exploitation.

alpha = 0.75      # learning rate
gamma = 0.95      # discount factor
epsilon = 0.25    # exploration probability
training_rounds = 1000

Step 3: State Transition Function

Action mapping:

• 0 → Left
• 1 → Right
• 2 → Up
• 3 → Down

The agent is prevented from moving outside the grid.

def next_position(state, action):
    row, col = divmod(state, 4)

    if action == 0 and col > 0:
        col -= 1
    elif action == 1 and col < 3:
        col += 1
    elif action == 2 and row > 0:
        row -= 1
    elif action == 3 and row < 3:
        row += 1

    return row * 4 + col

Step 4: Q-Learning Training Loop

The agent chooses actions using an epsilon-greedy policy, updates Q-values using the Bellman update rule, and ends an episode upon reaching the goal.

for episode in range(training_rounds):
    current = np.random.randint(0, states_count)

    while True:
        if np.random.rand() < epsilon:
            chosen_action = np.random.randint(0, actions_count)
        else:
            chosen_action = np.argmax(Q_matrix[current])

        new_state = next_position(current, chosen_action)

        reward = 1 if new_state == terminal_state else 0

        Q_matrix[current, chosen_action] += alpha * (
            reward + gamma * np.max(Q_matrix[new_state]) - Q_matrix[current, chosen_action]
        )

        if new_state == terminal_state:
            break

        current = new_state

Step 5: Visualizing the Learned Values

We display the maximum Q-value for each state to observe how the agent has learned the path toward the goal.

state_values = np.max(Q_matrix, axis=1).reshape((4, 4))

plt.figure(figsize=(6, 6))
plt.imshow(state_values, cmap='plasma')
plt.colorbar(label='Q-value')
plt.title('Learned State Values (4×4 Grid)')
plt.gca().invert_yaxis()
plt.grid(True)

for i in range(4):
    for j in range(4):
        plt.text(j, i, f'{state_values[i, j]:.2f}',
                 ha='center', va='center', color='white')

plt.show()

print("Final Learned Q-table:")
print(Q_matrix)

• Each row index (0–15) represents a state in the 4×4 grid.
• Each row contains four Q-values corresponding to the actions Left, Right, Up, and Down.
• Higher Q-values indicate actions that move the agent closer to the goal state.
• States near the goal (12–15) have higher Q-values (≈15–17), showing they are close to the target state (15).
• States far from the goal (0–3) have lower Q-values (≈8–13), as more steps are required to reach the goal.
• The agent’s policy is obtained by choosing the action with the maximum Q-value in each state.

Advantages of Q-Learning

• Model-free learning: It does not need prior knowledge of the environment; the agent learns directly from experience.
• Guaranteed convergence: With enough exploration and proper learning rates, it can converge to the optimal policy.
• Simple to implement: The algorithm is conceptually straightforward and easy to code.
• Flexible usage: Can be applied to many problems such as games, robotics, and path-finding.
• Handles delayed rewards: It learns long-term benefits, not just immediate rewards.

Limitations of Q-Learning

• Scalability issue: The Q-table becomes very large when the number of states or actions increases.
• High memory usage: Storing Q-values for every state–action pair can be inefficient.
• Slow learning: Requires many episodes to learn good policies, especially in complex environments.
• Not suitable for continuous spaces: It works best with discrete states and actions.
• Exploration challenges: Poor exploration strategies can lead to suboptimal learning.