Artificial Intelligence: Reinforcement Learning in Python

Welcome to this comprehensive course on Reinforcement Learning (RL) in Python. This course is designed to equip you with a deep understanding of RL principles, algorithms, and their practical implementation using Python. Whether you’re a data scientist, machine learning engineer, or an AI enthusiast, this material will provide you with the knowledge and tools to tackle complex decision-making problems.

1. Introduction to Reinforcement Learning

1.1 What is Reinforcement Learning?

Reinforcement Learning is a subfield of machine learning concerned with how intelligent agents ought to take actions in an environment to maximize some notion of cumulative reward. Unlike supervised learning, where models learn from labeled data, and unsupervised learning, where models find patterns in unlabeled data, RL agents learn through trial and error interactions with their environment. The core components of an RL system are the agent, the environment, states, actions, and rewards.

• Agent: The learner or decision-maker.
• Environment: Everything outside the agent, with which the agent interacts.
• State (S): A snapshot of the environment at a particular time.
• Action (A): A move made by the agent in a given state.
• Reward (R): A scalar feedback signal indicating how good or bad the agent’s action was.
• Policy (π): A strategy that the agent uses to determine the next action based on the current state.
• Value Function (V/Q): A prediction of future rewards.

1.2 Reinforcement Learning vs. Other Machine Learning Paradigms

It’s crucial to understand how RL differs from supervised and unsupervised learning:

• Supervised Learning: Learns from a dataset of input-output pairs. The goal is to map inputs to correct outputs. Example: image classification.
• Unsupervised Learning: Discovers patterns and structures in unlabeled data. Example: clustering, dimensionality reduction.
• Reinforcement Learning: Learns by interacting with an environment, receiving rewards or penalties, and adjusting its actions to maximize cumulative reward over time. There’s no supervisor explicitly telling the agent what to do; it learns from consequences.

1.3 Key Challenges in Reinforcement Learning

• Exploration vs. Exploitation: The agent must balance trying new actions (exploration) to discover better strategies with using known good actions (exploitation) to maximize immediate reward.
• Delayed Rewards: Actions taken now might only yield significant rewards much later, making it difficult to attribute credit to specific actions.
• High-Dimensional State Spaces: Many real-world problems have an enormous number of possible states, making it impractical to store value functions for every state.
• Partial Observability: The agent might not have complete information about the environment’s state.

2. Markov Decision Processes (MDPs)

Most reinforcement learning problems can be formalized as Markov Decision Processes. An MDP is a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker.

2.1 Components of an MDP

An MDP is defined by a tuple (S, A, P, R, γ):

• S: A finite set of states.
• A: A finite set of actions.
• P(s’ | s, a): The state transition probability, which is the probability of transitioning to state s’ from state s after taking action a. This is the “Markov Property” – the future depends only on the present state, not on the sequence of events that preceded it.
• R(s, a, s’): The reward function, which gives the immediate reward received after transitioning from state s to state s’ via action a.
• γ (gamma): The discount factor (0 ≤ γ < 1). It determines the present value of future rewards. A higher γ values future rewards more strongly.

2.2 Bellman Equations

The Bellman equations are fundamental to MDPs and RL. They express the value of a state or a state-action pair in terms of the values of successor states or state-action pairs. They are recursive equations that relate the value of a state (or state-action pair) to the expected value of the next state (or state-action pair) plus the immediate reward.

• Value Function V(s): The expected cumulative reward starting from state s and following a policy π.
  
  V_π(s) = E_π [Σ_{k=0}^∞ γ^k R_{t+k+1} | S_t = s]
  
  The Bellman Expectation Equation for V_π(s):
  
  V_π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_π(s')]
• Action-Value Function Q(s, a): The expected cumulative reward starting from state s, taking action a, and then following a policy π.
  
  Q_π(s, a) = E_π [Σ_{k=0}^∞ γ^k R_{t+k+1} | S_t = s, A_t = a]
  
  The Bellman Expectation Equation for Q_π(s,a):
  
  Q_π(s, a) = Σ_{s'} P(s'|s,a) [R(s,a,s') + γ Σ_{a'} π(a'|s') Q_π(s',a')]

The Optimal Policy (π*) is the policy that achieves the maximal value function for all states. The Bellman Optimality Equations define the optimal value functions:

• V*(s) = max_a Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V*(s')]
• Q*(s, a) = Σ_{s'} P(s'|s,a) [R(s,a,s') + γ max_{a'} Q*(s',a')]

3. Model-Based Reinforcement Learning

Model-based RL algorithms learn or approximate a model of the environment (P and R) and then use this model to plan. Planning involves using the model to compute an optimal policy or value function. These methods can be very sample efficient but depend heavily on the accuracy of the learned model.

3.1 Policy Iteration

Policy Iteration consists of two main steps, repeated until the policy converges:

1. Policy Evaluation: Given a policy π, compute the state-value function V_π(s). This is often done iteratively using the Bellman Expectation Equation.
   
   V_{k+1}(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_k(s')]
2. Policy Improvement: Improve the policy by making it greedy with respect to the current value function.
   
   π'(s) = argmax_a Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_π(s')]

This process is guaranteed to converge to the optimal policy.

3.2 Value Iteration

Value Iteration directly computes the optimal value function V*(s) without explicitly maintaining a policy during the evaluation step. It iteratively applies the Bellman Optimality Equation until the value function converges.

V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_k(s')]

Once V*(s) is found, the optimal policy can be derived by choosing actions greedily with respect to V*(s).

4. Model-Free Reinforcement Learning

Model-free RL algorithms learn directly from experience (trial and error) without explicitly building a model of the environment’s dynamics. These methods are generally more broadly applicable when the environment model is unknown or too complex to learn accurately. They often require more samples (interactions with the environment) but can handle complex, continuous state and action spaces.

4.1 Monte Carlo Methods

Monte Carlo (MC) methods learn value functions and optimal policies directly from episodes of experience. They don’t require knowledge of the environment’s dynamics (model-free) and can be used for episodic tasks (tasks with a clear end). MC methods estimate values by averaging returns (total discounted rewards) observed after visits to a state or state-action pair.

• First-Visit MC: Averages returns only the first time a state is visited in an episode.
• Every-Visit MC: Averages returns every time a state is visited in an episode.

MC control involves iteratively performing policy evaluation (using MC to estimate Q_π) and policy improvement (making the policy greedy with respect to Q_π). To ensure exploration, techniques like ε-greedy policies are used, where the agent acts greedily with probability 1-ε and randomly with probability ε.

Python Example (Conceptual – MC for Q-value estimation):

import numpy as np

# Assume a simple environment and policy for illustration
# This is a conceptual example, not a full implementation
def generate_episode(env, policy):
    episode = []
    state = env.reset()
    done = False
    while not done:
        action = policy(state) # Policy determines action
        next_state, reward, done, _ = env.step(action)
        episode.append((state, action, reward))
        state = next_state
    return episode

def monte_carlo_es(env, num_episodes, gamma=0.99):
    Q = {} # Q-table: (state, action) -> value
    N = {} # Visit counts: (state, action) -> count
    
    # Initialize Q and N for all possible state-action pairs
    # In a real scenario, this would be more dynamic or pre-defined
    for s in env.states:
        for a in env.actions:
            Q[(s, a)] = 0.0
            N[(s, a)] = 0
            
    policy = {} # State -> action (initially random or soft policy)
    for s in env.states:
        policy[s] = np.random.choice(env.actions)

    for i_episode in range(num_episodes):
        episode = generate_episode(env, policy)
        
        G = 0 # Cumulative discounted reward
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = reward + gamma * G
            
            # Check if (state, action) is visited for the first time in this episode
            # (First-Visit MC)
            if (state, action) not in [(x[0], x[1]) for x in episode[0:t]]:
                N[(state, action)] += 1
                Q[(state, action)] += (G - Q[(state, action)]) / N[(state, action)]
                
                # Policy Improvement (greedy)
                # Find the action that maximizes Q for the current state
                best_action = None
                max_q = -np.inf
                for a in env.actions:
                    if Q.get((state, a), -np.inf) > max_q:
                        max_q = Q[(state, a)]
                        best_action = a
                policy[state] = best_action
                
    return Q, policy

# Note: 'env' needs to be an object with .reset(), .step(), .states, .actions attributes.
# This is a highly simplified example.

4.2 Temporal Difference (TD) Learning

TD learning combines ideas from Monte Carlo and Dynamic Programming. Like MC, TD methods learn directly from experience without a model. Like DP, TD methods update estimates based on other learned estimates (bootstrapping).

• TD(0): Updates the value estimate of a state based on the immediate reward and the estimated value of the next state.
  
  V(S_t) ← V(S_t) + α [R_{t+1} + γ V(S_{t+1}) - V(S_t)]
  
  Here, α is the learning rate. The term R_{t+1} + γ V(S_{t+1}) is the TD target, and R_{t+1} + γ V(S_{t+1}) - V(S_t) is the TD error.

4.2.1 SARSA (On-Policy TD Control)

SARSA (State-Action-Reward-State-Action) is an on-policy TD control algorithm. This means it learns the value function for the policy currently being followed, including its exploration steps. It updates the Q-value of the current state-action pair based on the reward received and the Q-value of the next state-action pair, which is also chosen by the *same* policy.

Q(S_t, A_t) ← Q(S_t, A_t) + α [R_{t+1} + γ Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]

In SARSA, the next action A_{t+1} is chosen using the current policy (e.g., ε-greedy) before the update is made.

Python Example (SARSA):

import numpy as np

def choose_action(state, Q_table, actions, epsilon):
    if np.random.uniform(0, 1) < epsilon:
        return np.random.choice(actions) # Explore
    else:
        # Exploit: choose action with max Q-value (handle unseen states)
        q_values = [Q_table.get((state, a), 0.0) for a in actions]
        return actions[np.argmax(q_values)]

def sarsa(env, num_episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = {} # Q-table: (state, action) -> value
    
    # Initialize Q-values to 0.0 for all known state-action pairs
    # In a grid world, you might pre-initialize for all (row, col) and actions
    # For simplicity, we'll let .get() handle unseen pairs initially
    
    for i_episode in range(num_episodes):
        state = env.reset()
        action = choose_action(state, Q, env.actions, epsilon) # A_t
        done = False
        
        while not done:
            next_state, reward, done, _ = env.step(action)
            next_action = choose_action(next_state, Q, env.actions, epsilon) # A_{t+1}

            # Get current Q-value, defaulting to 0 if not seen
            current_q = Q.get((state, action), 0.0)
            
            # Get next Q-value, defaulting to 0 if not seen (for terminal states, it's 0)
            next_q = Q.get((next_state, next_action), 0.0) if not done else 0.0
            
            # SARSA update rule
            Q[(state, action)] = current_q + alpha * (reward + gamma * next_q - current_q)
            
            state = next_state
            action = next_action
            
    return Q

# Note: 'env' needs to be an object with .reset(), .step(), .actions attributes.
# Example: a simple GridWorld environment for discrete states/actions.

4.2.2 Q-Learning (Off-Policy TD Control)

Q-Learning is an off-policy TD control algorithm. This means it learns the optimal Q-value function *independent* of the policy being followed for exploration. It updates the Q-value of the current state-action pair based on the immediate reward and the