Welcome to the first lesson of "Q-Learning Unleashed: Building Intelligent Agents"! This is the second course in our "Playing Games with Reinforcement Learning" path, in which we build upon the environment concepts we explored in the previous course. Specifically, in this course we'll dive into one of the most fundamental algorithms in Reinforcement Learning: Q-Learning.

Q-Learning is a model-free Reinforcement Learning algorithm that allows an agent to learn optimal actions through experience. Unlike supervised learning, where we train on labeled examples, in Q-Learning, our agent learns by interacting with an environment and receiving feedback in the form of rewards. Throughout this lesson, we'll explore the concept of policies in reinforcement learning, delve into the mathematical foundations of the Q-Learning algorithm, and implement a Q-table in Python. We'll also write the core Q-Learning update function and see the algorithm in action through practical examples.

Virtually every RL algorithm employs Q-learning, or some variation of it, making it a fundamental tool in your RL toolbox. By the end of this lesson, you'll have a solid understanding of how Q-Learning works and be able to implement your own Q-Learning agent!

To implement Q-Learning, we first need a data structure to store our Q-values. The most straightforward approach is a Q-table — a table where rows represent states and columns represent actions, with each cell containing the corresponding Q-value. While this approach works well for simple environments with discrete states and actions, more advanced approaches use function approximation techniques, such as neural networks in Deep Reinforcement Learning, to estimate Q-values for environments with large or continuous state spaces. Please note we won't deal with Deep RL techniques in this course path.

In Python, we can implement a Q-table using different data structures. For grid-world environments with discrete states and actions, a dictionary or a defaultdict is often the most convenient approach:

import numpy as np
from collections import defaultdict

# Initialize Q-table as defaultdict
Q = defaultdict(lambda: np.zeros(4))  # 4 actions (up, down, left, right)

This code creates a defaultdict where each key is a state, and each value is a numpy array containing Q-values for each possible action. The beauty of using defaultdict is that it automatically creates entries for states we haven't seen before, initializing their action values to zeros. We can then access the Q-value for a specific state-action pair using Q[state][action].

For example, if our state is represented as a tuple (x, y) for position in a grid, we could access the Q-value for moving right in position (3, 2) with Q[(3, 2)][3], assuming action 3 corresponds to moving right.

Now that we have our Q-table, we need to implement the update rule that will allow our agent to learn from experience. Here's the function that performs the Q-Learning update:

def q_learning_update(Q, state, action, reward, next_state, alpha, gamma, done):
    """
    Q(s,a) <- Q(s,a) + alpha * [ reward + gamma * max_a' Q(s', a') - Q(s,a) ]
    
    Parameters:
    - Q: Q-table (defaultdict mapping states to action value arrays)
    - state: current state
    - action: action taken
    - reward: reward received
    - next_state: state transitioned to
    - alpha: learning rate
    - gamma: discount factor
    - done: boolean indicating if next_state is terminal
    """
    if done:
        # For terminal states, there's no future reward to consider
        best_next_q = 0.0
    else:
        # For non-terminal states, include the discounted future reward
        best_next_q = np.max(Q[next_state])
        
    Q[state][action] += alpha * (reward + gamma * best_next_q - Q[state][action])

Here's how this function implements the Bellman equation:

• The function takes a parameter done which indicates if we've reached a terminal (goal) state or if the maximum number of steps has been reached. This allows our agent to learn differently when it reaches terminal states (like winning or losing a game) or when it hits the maximum steps compared to intermediate states.
• For terminal states or when the maximum steps are reached, we set best_next_q = 0.0 because there are no future rewards to consider.
• For non-terminal states, we calculate best_next_q = np.max(Q[next_state]) to find the maximum possible Q-value from the next state.
• Finally, we update the Q-table using the Bellman equation: Q[state][action] += alpha * (reward + gamma * best_next_q - Q[state][action]).

The learning process is iterative — with each experience, the agent adjusts its Q-values to better reflect the expected rewards.