Q-learning : An RL Algorithm

Reinforcement Learning (RL) is an area of machine learning where an agent learns to make a sequence of decisions in an environment to maximize a cumulative reward. It is often compared to how humans learn through trial and error.

RL systems are defined by the interaction between the following key components:

Components of Reinforcement Learning

Core Components of Reinforcement Learning

Agent & Policy

• Agent: The learner and decision-maker in the system. Its main objective is to learn the optimal Policy (p).
• Policy (p): The agent’s strategy. It is a mapping that tells the agent which Action to take when in a specific State. The goal of the agent is to find the policy that maximizes the total accumulated Reward.

Environment & Interaction

• Environment: The external world where the agent exists and operates. It reacts to the agent’s actions by changing its own state and providing feedback.
• State (S): A complete description of the current situation of the environment at a given time (t)
• Action (A): The move or decision the agent selects from a set of possibilities. The agent interacts with the Environment by executing an Action A(t) in State S(t).

Feedback

• Reward (R): A numerical signal (R(t+1)) received from the Environment immediately after an action is taken. It quantifies the desirability of the agent’s action in that state, guiding the agent toward the goal of maximizing Reward.

These components define the learning loop: The Agent observes the State (S(t)), chooses an Action (A(t)) based on its Policy (p), and the Environment responds with a new State (S(t+1)) and a Reward (R(t+1)).

RL algorithms can be broadly categorized as:

• Model-based: The agent tries to build an internal model of the environment to predict the next state and reward for a given action.
• Model-free: The agent learns the optimal policy or value function directly from experience, without building a full model of the environment. Q-learning is a prominent example of a model-free algorithm.

🎯 Key Conditions for Choosing RL

1. Sequential Decision-Making: The task requires a series of actions where each action affects the environment, which in turn influences subsequent actions and the long-term outcome.

2.No Labeled “Ground Truth” Data Exists: Unlike Supervised Learning, RL is used when the “best” action for every possible state is unknown. The agent must discover the optimal strategy through interaction.

3.Long-Term Optimization is Necessary: The agent must learn to make short-term sacrifices for a greater long-term cumulative reward.

Get Rashmi S’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

4.An Interactive Environment is Available (or can be simulated): Since RL relies on extensive exploration and experimentation, an environment must be available (or safely simulated) where the agent can make many mistakes.

Common Use Cases for Reinforcement Learning

Q Learning:

Q-learning is an iterative process where an Agent learns the optimal Policy by repeatedly interacting with the Environment and updating its knowledge (Q-table).

1. Initialization

• The Q-Table is created, mapping every possible State (S) to every possible Action (A). The rows represent all possible states the agent can be in.The columns represent all possible actions the agent can take. The table is initially filled with arbitrary values, usually zeros

2. Hyperparameters are set:

• Learning Rate: How much new information overrides old information (e.g., 0.1)
• Discount Factor: The importance of future rewards (e.g., 0.9)
• Exploration Rate: The probability of choosing a random action

3. Observation and Action Selection

• The agent observes the current State S(t) from the environment.
• It selects an Action A(t) using an Epsilon-greedy policy
• With probability Y, the agent explores by choosing a random action (to discover new, better paths)
• With probability 1-Y, the agent exploits by choosing the action(A) that has the current highest Q(S(t), A) value in the Q-table (the known best action)

4. Execution and Feedback

• The agent executes the chosen Action (A(t)) in the environment
• The environment provides feedback, immediate Reward (R(t)) and the next State (s(t+1)) of the environment.

5. Q-Value Update

• The agent uses the new information (S(t+1), R(t+1)) to update the Q-value for the state-action pair (S(t), A(t))
• A portion of the Temporal Difference (TD) Error is added(the difference between the Target Value and the Old Value) to Q(S(t), A(t)), the agent moves it’s estimate closer to the true value.

6. Repetition and Convergence

• The agent sets the current state to the new state repeats the process from Step 2.
• The iterative process converge to the optimal Q values.Once converged, the Q-table accurately represents the maximum expected reward for every possible state-action pair, defining the optimal policy.

Advantages of Q-Learning

1. Model-Free

• No Prior Knowledge Required: Q-learning is model-free, meaning the agent does not need to know the environmental dynamics (the transition probabilities or the reward function beforehand. It learns purely from trial-and-error experience. This is a significant advantage in complex or unknown real-world systems.

2. Off-Policy Learning

• Learns Optimal Policy During Exploration: Q-learning is an off-policy algorithm. It learns the value of the optimal action regardless of the exploratory strategy the agent is currently using to move around. This allows the agent to learn the best possible policy efficiently while still actively exploring new and potentially suboptimal paths.

3. Handles Stochastic Environments

• Robustness: The iterative update rule based on the average of returns (the Temporal Difference approach) allows Q-learning to naturally handle environments where the outcome of an action is non-deterministic.

4. Simplicity and Guaranteed Convergence (under conditions)

• Easy Implementation: For simple problems with small, discrete state-action spaces, the tabular version is straightforward to implement and debug.
• Theoretical Guarantee: Under the conditions of a bounded reward function and infinite exploration of all state-action pairs, Q-learning is mathematically guaranteed to converge to the optimal Q-values.

Limitations of Q-Learning

1. Scalability Issues

• Limited to Small Problems: Standard Q-learning relies on storing Q-values in a Q-Table. The memory and computational requirements grow exponentially with the number of states and actions.

2. Slow Convergence

• Data Inefficiency: In complex environments, the agent needs a huge number of interactions (episodes) to visit and update all state-action pairs enough times for the Q-values to converge to their true optimal values. This can make training very slow.

3. Overestimation Bias

• Max Operator Problem: The update rule uses the “max” operator. This always selects the highest estimated Q-value from the next state. If the Q-values are noisy or uncertain (which they are during early training), this can systematically overestimate the true optimal action value, leading to suboptimal policies. This issue is often addressed by advanced techniques like Double Q-learning (DQN).

4. Difficulty with Exploration-Exploitation Trade-off

• Too much exploitation means the agent might get stuck in a local optimum.
• Too much exploration means the agent learns too slowly or acts randomly for too long.

Sample code for Q-learning:

import numpy as np

# --- 1. Define Environment Parameters ---
# Example: A grid with states (0, 1, 2, 3) and 2 actions (0: left, 1: right)
NUM_STATES = 4
NUM_ACTIONS = 2

# --- 2. Hyperparameters ---
LEARNING_RATE = 0.1  
DISCOUNT_FACTOR = 0.95 
EPISODES = 1000       # Number of training iterations
EXPLORATION_RATE = 1.0 # epsilon (ε) 
MAX_EXPLORATION_RATE = 1.0
MIN_EXPLORATION_RATE = 0.01
EXPLORATION_DECAY_RATE = 0.001

# --- 3. Initialize the Q-Table ---
# The Q-table is a matrix of size (NUM_STATES x NUM_ACTIONS)
Q_table = np.zeros((NUM_STATES, NUM_ACTIONS))

def select_action(state, q_table, exploration_rate):
    """
    Chooses an action based on the epsilon-greedy strategy.
    """
    # Exploration: Choose a random action
    if np.random.rand() < exploration_rate:
        action = np.random.randint(NUM_ACTIONS)
    # Exploitation: Choose the action with the highest Q-value
    else:
        action = np.argmax(q_table[state, :])

    return action

# The Q-Learning Training Loop 
for episode in range(EPISODES):
    current_state = 0 # Start in state 0

    # The loop continues until a terminal state is reached 
    for step in range(100): # Max steps per episode
        
        # 4a. Select an action using epsilon-greedy
        action = select_action(current_state, Q_table, EXPLORATION_RATE)
        
        if current_state == 0 and action == 1:
            new_state, reward, done = 1, 1, False
        elif current_state == 1 and action == 0:
            new_state, reward, done = 0, -1, False
        else:
            # Placeholder for other state/action transitions
            new_state, reward, done = current_state, 0, False 

        # max_q_new_state = max_a' Q(s', a')
        max_q_new_state = np.max(Q_table[new_state, :])
        old_q_value = Q_table[current_state, action]

        new_q_value = old_q_value + LEARNING_RATE * (
            reward + DISCOUNT_FACTOR * max_q_new_state - old_q_value
        )
        
        Q_table[current_state, action] = new_q_value
        
        current_state = new_state
        
        if done: # Break if terminal state is reached
            break

    # This gradually shifts the agent from exploration to exploitation
    EXPLORATION_RATE = MIN_EXPLORATION_RATE + (MAX_EXPLORATION_RATE - MIN_EXPLORATION_RATE) * \
        np.exp(-EXPLORATION_DECAY_RATE * episode)


# Output the Learned Q-Table 
print(Q_table)

Q-Learning Variations and Extensions

The standard Q-learning algorithm has several important variations and extensions, primarily developed to address its limitations, especially in complex environments with large state or action spaces.

1. Deep Q-Networks (DQN)

• Core Idea: Addresses the scalability issue by replacing the memory-intensive Q-table with a deep neural network (Q-network) to approximate the Q-function. This is the foundation of Deep Reinforcement Learning.

2. Double Q-learning (and Double DQN)

• Core Idea: Addresses the overestimation bias. It decouples the selection of the next action from the evaluation of its value using two separate Q-value estimators Q_A and Q_B. One Q-function selects the greedy action, and the other evaluates its value, reducing the systematic overestimation.

3. Prioritized Experience Replay (PER)

• Core Idea: Addresses slow convergence/data inefficiency. Instead of uniform sampling, PER samples transitions based on their priority, which is typically the magnitude of the Temporal Difference (TD) error. Transitions with high TD errors are the ones the agent learns the most from, so they are prioritized for re-training.

4. Rainbow DQN

• Core Idea: Synergistic Integration. This approach combines six (or seven) of the most effective, independently developed improvements (including DQN, Double DQN, and PER) into a single, unified agent, achieving superior performance and data efficiency.

Further reading materials:

1. https://arxiv.org/abs/1707.06887
2. https://arxiv.org/pdf/1806.06923
3. https://arxiv.org/abs/1710.02298
4. https://arxiv.org/abs/2202.01741