Reinforcement Learning: Core Concepts

#reinforcement learning #agent #environment #rewards #markov decision processes #q-learning #exploration vs exploitation #temporal difference learning #sarsa

1. Key Components: Agent, Environment, and Rewards

Key Components: Agent, Environment, and Rewards

The Reinforcement Learning Framework

Reinforcement learning (RL) formalizes the interaction between an agent and an environment through a sequence of states, actions, and rewards. The agent operates in discrete time steps t, where at each step, it observes the current state st from the environment, selects an action at based on its policy, and receives a scalar reward rt+1. The environment transitions to a new state st+1 according to its dynamics, and the process repeats.

$$ \tau = (s_0, a_0, r_1, s_1, a_1, r_2, \dots) $$

The Agent

The agent is an autonomous decision-maker that implements a policy π, which maps states to actions. Policies can be deterministic (a = π(s)) or stochastic (a ∼ π(·|s)). Advanced agents often employ value functions or Q-functions to estimate expected future rewards:

$$ V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k r_{t+k+1} \mid s_t = s \right] $$

where γ ∈ [0, 1] is a discount factor. Model-based agents additionally learn the environment's transition dynamics P(s'|s, a) and reward function R(s, a).

The Environment

The environment defines the problem's dynamics through a Markov Decision Process (MDP), characterized by:

Environments can be fully observable (the agent sees the true state) or partially observable (modeled as a POMDP). In continuous control tasks like robotic manipulation, the state and action spaces are often high-dimensional and continuous.

Reward Design

The reward signal is a critical component that shapes the agent's behavior. A well-designed reward function should:

In inverse reinforcement learning, the reward function is inferred from expert demonstrations. The choice of discount factor γ trades off immediate versus long-term rewards:

$$ \gamma \rightarrow 1 \text{ emphasizes long-term rewards} $$ $$ \gamma \rightarrow 0 \text{ focuses on immediate gains} $$

Practical Considerations

In real-world applications like autonomous driving or game AI, agents must handle:

Recent advances like hierarchical RL decompose complex tasks into subtasks with their own reward functions, while multi-agent RL introduces additional complexity through interacting agents.

Key Components: Agent, Environment, and Rewards – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would physically show the interaction loop between agent, environment, and rewards with labeled states, actions, and time steps.

Markov Decision Processes (MDPs)

A Markov Decision Process (MDP) is a mathematical framework for modeling sequential decision-making problems where outcomes are partly random and partly under the control of a decision-maker. Formally, an MDP is defined by the tuple (S, A, P, R, γ), where:

Markov Property

The defining characteristic of an MDP is the Markov property, which states that the future state and reward depend only on the current state and action, not on the history of previous states and actions. Mathematically, this is expressed as:

$$ P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ..., s_0, a_0) = P(s_{t+1} | s_t, a_t) $$

This property simplifies the modeling of sequential decisions by eliminating the need to track the entire history of interactions.

Policy and Value Functions

A policy π(a|s) defines the probability of taking action a in state s. The goal in an MDP is to find an optimal policy π* that maximizes the expected cumulative reward. Two key value functions are used to evaluate policies:

These functions satisfy the Bellman equations:

$$ V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s, a) \left[ R(s, a, s') + \gamma V^\pi(s') \right] $$
$$ Q^\pi(s, a) = \sum_{s'} P(s'|s, a) \left[ R(s, a, s') + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s', a') \right] $$

Optimality and Dynamic Programming

An optimal policy π* satisfies Vπ*(s) ≥ Vπ(s) for all states s and policies π. The corresponding optimal value functions V* and Q* obey the Bellman optimality equations:

$$ V^*(s) = \max_{a} \sum_{s'} P(s'|s, a) \left[ R(s, a, s') + \gamma V^*(s') \right] $$
$$ Q^*(s, a) = \sum_{s'} P(s'|s, a) \left[ R(s, a, s') + \gamma \max_{a'} Q^*(s', a') \right] $$

Dynamic programming methods, such as value iteration and policy iteration, leverage these equations to compute optimal policies for known MDPs.

Applications of MDPs

MDPs are widely used in robotics, finance, operations research, and game theory. For instance, in autonomous navigation, an MDP can model the robot's state (position, velocity), actions (move forward, turn), and rewards (reaching a goal, avoiding obstacles). Similarly, in algorithmic trading, states represent market conditions, actions are buy/sell decisions, and rewards correspond to profit maximization.

Markov Decision Processes (MDPs) – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: A diagram would physically show the state-action-reward transitions in an MDP, illustrating how states, actions, and rewards are interconnected.

Policy, Value Functions, and Q-Learning

Policies in Reinforcement Learning

A policy π defines the agent's behavior by mapping states to actions. Formally, it is a probability distribution over actions given a state:

$$ \pi(a|s) = P(A_t = a | S_t = s) $$

Deterministic policies select a single action per state (π(s) = a), while stochastic policies assign probabilities to multiple actions. Optimal policies maximize expected cumulative reward, often denoted as π*.

Value Functions

Value functions estimate long-term returns from states or state-action pairs. The state-value function Vπ(s) gives the expected return when starting in state s and following policy π:

$$ V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t = s \right] $$

The action-value function Qπ(s, a) extends this to include the initial action:

$$ Q^\pi(s, a) = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t = s, A_t = a \right] $$

Here, γ ∈ [0, 1] is the discount factor balancing immediate and future rewards.

Bellman Equations

Value functions satisfy recursive Bellman equations. For Vπ(s):

$$ V^\pi(s) = \sum_a \pi(a|s) \sum_{s', r} P(s', r|s, a) \left[ r + \gamma V^\pi(s') \right] $$

For Qπ(s, a), the Bellman equation becomes:

$$ Q^\pi(s, a) = \sum_{s', r} P(s', r|s, a) \left[ r + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s', a') \right] $$

These equations enable dynamic programming solutions like value iteration and policy iteration.

Q-Learning

Q-Learning is a model-free algorithm that directly approximates the optimal action-value function Q* using temporal difference (TD) updates. The update rule is:

$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \right] $$

Key properties:

Algorithm: Q-Learning


def q_learning(env, episodes, alpha, gamma, epsilon):
    Q = defaultdict(float)
    for _ in range(episodes):
        state = env.reset()
        while not done:
            action = epsilon_greedy(Q, state, epsilon)
            next_state, reward, done, _ = env.step(action)
            td_target = reward + gamma * max(Q[next_state].values())
            Q[state][action] += alpha * (td_target - Q[state][action])
            state = next_state
    return Q

Practical Considerations

Q-Learning faces challenges in continuous spaces, requiring function approximation. Deep Q-Networks (DQN) address this with experience replay and target networks to stabilize training. Convergence guarantees hold only for tabular cases; neural approximators may diverge without careful tuning.

Policy, Value Functions, and Q-Learning – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the relationships between states, actions, and Q-values in a grid-world example, illustrating how Q-values propagate through the Bellman equation.

2. Epsilon-Greedy Strategy

Epsilon-Greedy Strategy

The epsilon-greedy strategy is a fundamental exploration-exploitation trade-off mechanism in reinforcement learning. It balances between selecting the action with the highest estimated value (exploitation) and exploring other actions to improve value estimates (exploration). The parameter ε (epsilon) controls the probability of exploration.

Mathematical Formulation

At each time step t, the agent selects an action a from the action space A according to the following policy:

$$ \pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{|A|} & \text{if } a = \arg\max_{a'} Q(s, a') \\ \frac{\epsilon}{|A|} & \text{otherwise} \end{cases} $$

where Q(s, a) represents the estimated value of taking action a in state s, and |A| is the cardinality of the action space.

Convergence Properties

For stationary environments, the epsilon-greedy strategy guarantees that all state-action pairs will be visited infinitely often as t → ∞, provided that ε > 0. This ensures asymptotic convergence to the optimal policy under standard stochastic approximation conditions.

$$ \lim_{t \to \infty} Q_t(s, a) = Q^*(s, a) \quad \forall s \in S, a \in A $$

However, the constant exploration probability means the agent will always perform suboptimal actions with probability at least ε/|A|, preventing it from becoming purely greedy even after convergence.

Practical Implementation

In practice, epsilon is typically initialized to 1 (pure exploration) and decayed over time according to a schedule. Common decay schemes include:

where β, γ, and κ are decay parameters, and εmin ensures a minimum exploration rate.

Variations and Improvements

Several modifications to the basic epsilon-greedy strategy have been proposed to address its limitations:

Performance Considerations

The choice of epsilon schedule significantly impacts learning performance. Too rapid decay may lead to premature convergence to suboptimal policies, while too slow decay results in excessive exploration. The optimal schedule depends on problem characteristics such as:

Empirical studies suggest that exponential decay with γ ∈ [0.99, 0.999] often works well in practice for many benchmark problems.

Upper Confidence Bound (UCB)

The Upper Confidence Bound (UCB) algorithm addresses the exploration-exploitation trade-off in reinforcement learning by quantifying uncertainty in action-value estimates. Unlike ε-greedy methods, which explore randomly, UCB systematically favors actions with high potential reward based on confidence intervals derived from statistical bounds.

Mathematical Formulation

UCB selects actions by maximizing an upper confidence bound on the estimated action-value function. The UCB1 algorithm, a foundational variant, defines the bound as:

$$ A_t = \underset{a}{\arg\max} \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right] $$

where:

Derivation of the Confidence Bound

The term c√(ln t / Nt(a)) originates from Hoeffding's inequality, which bounds the deviation of empirical means from their true expectations. For a reward distribution with support in [0, 1], the probability that the true action-value q(a) exceeds the empirical mean by more than u is bounded by:

$$ P\left(q(a) \geq Q_t(a) + u\right) \leq e^{-2N_t(a)u^2} $$

Setting the right-hand side equal to t−4 (to ensure convergence) and solving for u yields the UCB1 exploration term.

Regret Analysis

UCB1 achieves logarithmic regret, defined as the difference between the cumulative reward of the optimal action and the algorithm's performance. For K actions, the regret RT after T steps is bounded by:

$$ R_T \leq 8 \sum_{a: \Delta_a > 0} \left( \frac{\ln T}{\Delta_a} \right) + \left(1 + \frac{\pi^2}{3}\right) \sum_{a} \Delta_a $$

where Δa is the suboptimality gap of action a. This bound highlights UCB1's efficiency in balancing exploration and exploitation.

Practical Considerations

In practice, UCB variants adapt to non-stationary environments by incorporating discount factors or sliding windows. For example, the UCB-Tuned algorithm refines the exploration term by estimating reward variances:

$$ A_t = \underset{a}{\arg\max} \left[ Q_t(a) + \sqrt{\frac{\ln t}{N_t(a)} \min\left(\frac{1}{4}, V_t(a)\right)} \right] $$

where Vt(a) is an empirical variance estimate. This adjustment improves performance in scenarios with heterogeneous reward distributions.

Applications

UCB is widely used in:

Thompson Sampling

Thompson Sampling is a Bayesian approach to the multi-armed bandit problem, balancing exploration and exploitation by sampling from posterior distributions over action rewards. Unlike deterministic methods such as UCB, it leverages probability matching to select actions, making it particularly effective in stochastic environments.

Bayesian Framework

At its core, Thompson Sampling operates within a Bayesian framework, where prior beliefs about the reward distribution of each arm are updated as observations are made. For Bernoulli bandits, a Beta distribution is commonly used as the conjugate prior due to its mathematical convenience. The posterior distribution after observing n successes and m failures for an arm is given by:

$$ P(\theta | \text{data}) = \text{Beta}(\alpha + n, \beta + m) $$

Here, θ represents the probability of success for the arm, while α and β are the parameters of the prior Beta distribution. Sampling from this posterior allows the algorithm to naturally incorporate uncertainty into its decision-making process.

Algorithmic Steps

The Thompson Sampling algorithm proceeds iteratively as follows:

  1. For each arm, sample a value from its current posterior distribution.
  2. Select the arm with the highest sampled value.
  3. Observe the reward and update the posterior distribution of the chosen arm.

This process ensures that arms with higher uncertainty are explored more frequently, while arms with high estimated rewards are exploited when confidence in their superiority is high.

Regret Analysis

The regret of Thompson Sampling is sublinear, meaning it converges to the optimal strategy over time. For a K-armed bandit with Bernoulli rewards, the expected cumulative regret after T rounds is bounded by:

$$ R(T) \leq O\left(\sqrt{KT \ln T}\right) $$

This bound is asymptotically optimal, matching the lower bounds derived for the multi-armed bandit problem. The logarithmic dependence on T highlights the efficiency of Thompson Sampling in minimizing regret.

Practical Applications

Thompson Sampling has been successfully applied in clinical trials, online advertising, and recommendation systems. Its ability to handle delayed feedback and non-stationary environments makes it a robust choice for real-world scenarios where exploration is costly but necessary.

Extensions and Variants

Several extensions of Thompson Sampling exist, including:

These variants extend the applicability of Thompson Sampling to more complex decision-making problems while retaining its core Bayesian principles.

Thompson Sampling – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the iterative process of Thompson Sampling, including sampling from posterior distributions, selecting the arm with the highest sampled value, and updating the posterior distribution.

3. TD(0) and TD(λ)

TD(0) and TD(λ)

Temporal Difference (TD) learning bridges the gap between Monte Carlo methods and dynamic programming by combining bootstrapping and sampling. Two fundamental algorithms in this family are TD(0) and TD(λ), where λ is a trace-decay parameter controlling the trade-off between bias and variance.

TD(0): One-Step Temporal Difference Learning

TD(0) updates the value function based on the immediate reward and the estimated value of the next state, following the Bellman equation. The update rule for the state-value function V(s) is:

$$ V(s_t) \leftarrow V(s_t) + \alpha \left[ r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \right] $$

Here, α is the learning rate, γ is the discount factor, and rt+1 is the reward received after transitioning from state st to st+1. The term in brackets is the TD error, representing the difference between the current estimate and the TD target.

Eligibility Traces and TD(λ)

TD(λ) generalizes TD(0) by introducing eligibility traces, which allow credit assignment over multiple time steps. The trace et(s) for a state s at time t is updated as:

$$ e_t(s) = \begin{cases} \gamma \lambda e_{t-1}(s) + 1 & \text{if } s = s_t \\ \gamma \lambda e_{t-1}(s) & \text{otherwise} \end{cases} $$

The value function update then incorporates the trace:

$$ V(s) \leftarrow V(s) + \alpha \delta_t e_t(s) $$

where δt is the TD error at time t. When λ=0, this reduces to TD(0); when λ=1, it becomes equivalent to Monte Carlo learning.

Forward and Backward Views

TD(λ) can be understood from two perspectives:

The equivalence between these views is established by the TD(λ) theorem, proving that both yield identical updates under appropriate conditions.

Practical Considerations

In practice, λ controls the bias-variance trade-off:

Applications of TD(λ) include game playing (e.g., backgammon with TD-Gammon), robotics, and financial prediction, where multi-step returns improve learning efficiency.

TD(0) and TD(λ) – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the relationship between TD(0) and TD(λ) updates, illustrating how eligibility traces propagate credit backward through states over time.

3.2 SARSA: On-Policy TD Control

SARSA (State-Action-Reward-State-Action) is an on-policy temporal difference (TD) control algorithm that learns the action-value function Q(s, a) by bootstrapping from the current estimate of the value function. Unlike off-policy methods like Q-learning, SARSA updates its policy based on the actions selected by the current policy, making it inherently on-policy. The name derives from the sequence of elements used in the update rule: (St, At, Rt+1, St+1, At+1).

SARSA Update Rule

The core of SARSA is its TD update rule for the action-value function:

$$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right] $$

Here, α is the learning rate, γ is the discount factor, Rt+1 is the immediate reward, and Q(St+1, At+1) is the estimated value of the next state-action pair under the current policy. The term in brackets is the TD error, representing the difference between the current estimate and the new target value.

On-Policy Nature of SARSA

SARSA is on-policy because it evaluates and improves the same policy that is used to select actions. The next action At+1 is chosen according to the current policy (e.g., ε-greedy), and this same action is used in the TD update. This contrasts with Q-learning, which uses the maximum Q-value of the next state, irrespective of the current policy.

For an ε-greedy policy, SARSA's update can be written as:

$$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \left( \epsilon \cdot \text{mean}_a Q(S_{t+1}, a) + (1 - \epsilon) \max_a Q(S_{t+1}, a) \right) - Q(S_t, A_t) \right] $$

Convergence Properties

Under standard stochastic approximation conditions (e.g., Robbins-Monro conditions for the learning rate), SARSA converges to the optimal action-value function Q* if the policy is greedy in the limit (GLIE). However, if the policy remains exploratory (e.g., fixed ε > 0), SARSA converges to a near-optimal policy that accounts for exploration penalties.

Algorithm Pseudocode

Initialize Q(s, a) arbitrarily
Repeat for each episode:
    Initialize S
    Choose A from S using policy derived from Q (e.g., ε-greedy)
    Repeat for each step of episode:
        Take action A, observe R, S'
        Choose A' from S' using policy derived from Q
        Q(S, A) ← Q(S, A) + α [R + γ Q(S', A') - Q(S, A)]
        S ← S', A ← A'
    until S is terminal

Practical Considerations

SARSA tends to be more conservative than Q-learning in stochastic environments because it accounts for the exploration inherent in the policy. This makes it suitable for applications where safety is critical, such as robotics or autonomous driving, where overly optimistic actions could lead to catastrophic outcomes.

One limitation is that SARSA can be slower to converge in deterministic environments compared to Q-learning, as it must account for the exploration noise in its updates. However, in highly stochastic environments, SARSA often outperforms Q-learning by learning more robust policies.

Extensions and Variants

Several variants of SARSA exist to improve its performance:

Q-Learning: Off-Policy TD Control

Q-Learning represents a foundational algorithm in reinforcement learning that enables an agent to learn optimal policies without requiring a model of the environment. As an off-policy temporal difference (TD) control method, it learns the action-value function Q(s,a) directly, independent of the policy being followed.

Mathematical Formulation

The Q-Learning update rule combines aspects of value iteration and TD learning. The algorithm maintains estimates of state-action values Q(s,a) and updates them using the following rule:

$$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)] $$

Where:

Off-Policy Nature

Q-Learning's off-policy characteristic stems from its update rule, which evaluates the greedy policy while following an exploratory behavior policy. This separation allows for:

Convergence Properties

Under standard stochastic approximation conditions, Q-Learning converges to the optimal action-value function Q* with probability 1, provided:

Practical Implementation Considerations

Effective implementation requires addressing several practical challenges:

Exploration-Exploitation Tradeoff

The ε-greedy policy commonly serves as the behavior policy, selecting random actions with probability ε and greedy actions otherwise. Annealing ε from 1 to near 0 often yields better empirical results.

Learning Rate Scheduling

Common approaches include:

Function Approximation

For large state spaces, Q-values are typically approximated using:

Algorithm Pseudocode

Initialize Q(s,a) arbitrarily
Repeat (for each episode):
    Initialize S
    Repeat (for each step of episode):
        Choose A from S using policy derived from Q (e.g., ε-greedy)
        Take action A, observe R, S'
        Q(S,A) ← Q(S,A) + α[R + γ max_a Q(S',a) - Q(S,A)]
        S ← S'
    until S is terminal

Applications and Variants

Q-Learning has powered numerous real-world applications and inspired several important variants:

Q-Learning: Off-Policy TD Control – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the Q-Learning update process with state transitions, action selection, and TD error calculation in a step-by-step visual flow.

4. Deep Q-Networks (DQN)

Deep Q-Networks (DQN)

Deep Q-Networks (DQN) combine Q-learning with deep neural networks to approximate the Q-value function in high-dimensional state spaces. Traditional Q-learning relies on tabular methods, which become infeasible when the state space grows exponentially. DQN addresses this by using a neural network to estimate Q-values, enabling generalization across similar states.

Q-Learning Recap

In Q-learning, the agent learns an action-value function Q(s, a), representing the expected cumulative reward of taking action a in state s. The Bellman equation describes the optimal Q-value:

$$ Q^*(s, a) = \mathbb{E}_{s' \sim \mathcal{P}} \left[ r + \gamma \max_{a'} Q^*(s', a') \right] $$

where r is the immediate reward, γ is the discount factor, and s' is the next state. Tabular Q-learning updates Q-values iteratively, but this approach fails in large or continuous state spaces.

Neural Network Approximation

DQN replaces the Q-table with a neural network Q(s, a; θ), where θ represents the network parameters. The network minimizes the mean squared error (MSE) between predicted Q-values and target Q-values derived from the Bellman equation:

$$ \mathcal{L}(\theta) = \mathbb{E}_{(s,a,r,s') \sim \mathcal{D}} \left[ \left( r + \gamma \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta) \right)^2 \right] $$

Here, θ⁻ denotes the parameters of a target network, which stabilizes training by providing consistent targets. The expectation is taken over transitions (s, a, r, s') sampled from a replay buffer 𝒟.

Key Innovations in DQN

DQN introduced two critical techniques to stabilize training:

Algorithmic Steps

The DQN algorithm proceeds as follows:

  1. Initialize Q-network Q(s, a; θ) and target network Q(s, a; θ⁻) with the same weights.
  2. Store transitions (s, a, r, s') in replay buffer 𝒟.
  3. Sample a mini-batch of transitions from 𝒟.
  4. Compute target Q-values using the target network: y = r + γ maxₐ' Q(s', a'; θ⁻).
  5. Update Q-network by minimizing MSE loss between Q(s, a; θ) and y.
  6. Periodically update the target network: θ⁻ ← θ.

Practical Considerations

DQN performance depends on hyperparameters such as:

Variants like Double DQN and Dueling DQN further improve performance by addressing overestimation bias and decoupling value and advantage estimation, respectively.

Implementation Example

Below is a PyTorch implementation of a DQN agent:

import torch
import torch.nn as nn
import torch.optim as optim
import numpy as np
from collections import deque
import random

class DQN(nn.Module):
    def __init__(self, state_dim, action_dim):
        super(DQN, self).__init__()
        self.fc1 = nn.Linear(state_dim, 64)
        self.fc2 = nn.Linear(64, 64)
        self.fc3 = nn.Linear(64, action_dim)

    def forward(self, x):
        x = torch.relu(self.fc1(x))
        x = torch.relu(self.fc2(x))
        return self.fc3(x)

class ReplayBuffer:
    def __init__(self, capacity):
        self.buffer = deque(maxlen=capacity)

    def push(self, state, action, reward, next_state, done):
        self.buffer.append((state, action, reward, next_state, done))

    def sample(self, batch_size):
        return random.sample(self.buffer, batch_size)

    def __len__(self):
        return len(self.buffer)

class DQNAgent:
    def __init__(self, state_dim, action_dim, lr=1e-3, gamma=0.99, buffer_size=10000):
        self.q_net = DQN(state_dim, action_dim)
        self.target_net = DQN(state_dim, action_dim)
        self.target_net.load_state_dict(self.q_net.state_dict())
        self.optimizer = optim.Adam(self.q_net.parameters(), lr=lr)
        self.buffer = ReplayBuffer(buffer_size)
        self.gamma = gamma
        self.action_dim = action_dim

    def update(self, batch_size):
        if len(self.buffer) < batch_size:
            return
        batch = self.buffer.sample(batch_size)
        states, actions, rewards, next_states, dones = zip(*batch)

        states = torch.FloatTensor(np.array(states))
        actions = torch.LongTensor(np.array(actions))
        rewards = torch.FloatTensor(np.array(rewards))
        next_states = torch.FloatTensor(np.array(next_states))
        dones = torch.FloatTensor(np.array(dones))

        current_q = self.q_net(states).gather(1, actions.unsqueeze(1))
        next_q = self.target_net(next_states).max(1)[0].detach()
        target_q = rewards + (1 - dones) * self.gamma * next_q

        loss = nn.MSELoss()(current_q.squeeze(), target_q)
        self.optimizer.zero_grad()
        loss.backward()
        self.optimizer.step()

    def update_target(self):
        self.target_net.load_state_dict(self.q_net.state_dict())
Deep Q-Networks (DQN) – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the architecture of a DQN, including the Q-network, target network, and replay buffer, along with data flow during training.

4.2 Policy Gradient Methods

Policy gradient methods directly optimize the policy πθ(a|s) by adjusting its parameters θ to maximize expected return. Unlike value-based methods, which learn a value function and derive a policy indirectly, policy gradients operate in the policy space, making them particularly effective for high-dimensional or continuous action spaces. The core idea is to compute the gradient of the expected reward with respect to the policy parameters and perform gradient ascent.

Derivation of the Policy Gradient Theorem

The Policy Gradient Theorem provides the foundation for these methods by expressing the gradient of the objective function J(θ)—the expected return under policy πθ—as an expectation over trajectories. The theorem states:

$$ \nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \, Q^{\pi_\theta}(s_t, a_t) \right] $$

Here, τ denotes a trajectory (s0, a0, r0, ..., sT), and Qπθ(st, at) is the state-action value function. The log-derivative trick is applied to rewrite the gradient in terms of the policy's likelihood ratios.

Variance Reduction Techniques

While the policy gradient estimator is unbiased, it often suffers from high variance. Two common techniques to mitigate this are:

Practical Algorithms

Several algorithms build on the policy gradient framework:

Example: REINFORCE Algorithm

The REINFORCE algorithm updates the policy parameters using:

$$ \theta \leftarrow \theta + \alpha \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \, G_t $$

where Gt is the return from time step t.

Applications and Limitations

Policy gradient methods excel in robotics, game playing, and other domains requiring continuous control. However, they face challenges such as sample inefficiency, local optima, and sensitivity to hyperparameters. Recent advances like distributed training and meta-learning aim to address these issues.

4.3 Actor-Critic Architectures

Actor-Critic methods combine the strengths of policy-based and value-based reinforcement learning, addressing the high variance of pure policy gradients while maintaining the flexibility of direct policy optimization. The architecture consists of two components: the actor, which updates the policy π(a|s; θ), and the critic, which estimates the value function V(s; w) or Q(s, a; w).

Mathematical Foundation

The actor’s policy gradient is adjusted using the critic’s value estimate as a baseline, reducing variance without introducing bias. The gradient of the expected return J(θ) is:

$$ abla_θ J(θ) = \mathbb{E}_{s \sim ρ^π, a \sim π} \left[ abla_θ \log π(a|s; θ) \cdot A(s, a; w) \right] $$

where A(s, a; w) is the advantage function, computed as Q(s, a; w) − V(s; w) or approximated via temporal difference (TD) error:

$$ A(s, a; w) \approx r + \gamma V(s'; w) − V(s; w) $$

The critic minimizes the mean squared error (MSE) between its value estimate and the target (e.g., TD target or Monte Carlo return). For V(s; w), the loss is:

$$ \mathcal{L}(w) = \mathbb{E}_{s \sim ρ^π} \left[ \left( V(s; w) − V^{\text{target}}(s) \right)^2 \right] $$

Architectural Variants

Synchronous vs. Asynchronous Updates: In synchronous Actor-Critic (e.g., A2C), the actor and critic share gradients after each episode. Asynchronous methods (e.g., A3C) parallelize agents with separate environments, updating a global model asynchronously.

Deterministic Policy Gradients (DPG): For continuous action spaces, the actor outputs deterministic actions μ(s; θ), and the critic estimates Q(s, a; w). The gradient becomes:

$$ abla_θ J(θ) = \mathbb{E}_{s \sim ρ^π} \left[ abla_θ μ(s; θ) \cdot abla_a Q(s, a; w) \big|_{a=μ(s; θ)} \right] $$

Proximal Policy Optimization (PPO): A popular variant that clips policy updates to avoid large deviations, optimizing:

$$ \mathcal{L}^{\text{CLIP}}(θ) = \mathbb{E}_t \left[ \min \left( \frac{π_θ(a_t|s_t)}{π_{\text{old}}(a_t|s_t)} A_t, \text{clip} \left( \frac{π_θ(a_t|s_t)}{π_{\text{old}}(a_t|s_t)}, 1−ϵ, 1+ϵ \right) A_t \right) \right] $$

Practical Implementation

Modern implementations often use deep neural networks for both actor and critic, sharing lower-layer features to improve sample efficiency. Key design choices include:

$$ A_t^{\text{GAE}} = \sum_{l=0}^{\infty} (\gamma \lambda)^l \delta_{t+l}, \quad \delta_t = r_t + \gamma V(s_{t+1}; w) − V(s_t; w) $$

Case Study: In robotics, Actor-Critic methods enable precise control policies by leveraging the critic’s low-variance gradient estimates. For example, DDPG (Deep Deterministic Policy Gradient) has been used to train robotic arms with continuous joint control.

Actor-Critic Architectures – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the interaction between the actor and critic components, including how gradients flow between them and how the advantage function is computed.

5. Multi-Agent Reinforcement Learning

Multi-Agent Reinforcement Learning

Multi-Agent Reinforcement Learning (MARL) extends traditional single-agent RL to environments where multiple agents interact, learn, and adapt simultaneously. Unlike single-agent settings, MARL introduces complexities such as non-stationarity, partial observability, and emergent coordination dynamics. The joint action space grows exponentially with the number of agents, making centralized training often infeasible.

Mathematical Formulation

In MARL, the environment is modeled as a stochastic game (also called a Markov game), defined by the tuple (N, S, {Ai}, P, {Ri}, γ), where:

The Q-function for agent i in a Markov game extends the Bellman equation:

$$ Q_i^\pi(s, a_i, a_{-i}) = \mathbb{E}_\pi \left[ R_i + \gamma \max_{a_i'} Q_i^\pi(s', a_i', a_{-i}') \right] $$

where a-i denotes the joint actions of all agents except i.

Key Challenges

Non-Stationarity: From the perspective of any single agent, the environment appears non-stationary because other agents are simultaneously learning and adapting their policies. This violates the Markov assumption crucial for convergence guarantees in single-agent RL.

Credit Assignment: In cooperative settings, determining each agent's contribution to the team's success becomes non-trivial. Global rewards provide sparse feedback, requiring specialized methods like difference rewards or counterfactual baselines.

Scalability: The joint action space dimensionality grows as O(|A|N), making exhaustive exploration impractical. Recent approaches use factorized value functions or attention mechanisms to mitigate this curse of dimensionality.

Algorithmic Approaches

Independent Q-Learning (IQL)

The simplest MARL approach treats other agents as part of the environment. Each agent independently learns its Q-function:

$$ Q_i(s, a_i) \leftarrow Q_i(s, a_i) + \alpha \left[ r_i + \gamma \max_{a_i'} Q_i(s', a_i') - Q_i(s, a_i) \right] $$

While computationally efficient, IQL often fails to converge due to the non-stationarity problem. Empirical results show it can work in practice with careful reward shaping and low learning rates.

Centralized Training with Decentralized Execution (CTDE)

Modern MARL algorithms like MADDPG and QMIX adopt the CTDE paradigm. During training, agents have access to global information (e.g., other agents' observations or actions), but policies execute locally during deployment. The centralized critic for agent i in MADDPG is:

$$ Q_i^\phi(s, a_1, ..., a_N) $$

where ϕ represents the centralized critic's parameters. Policy gradients are computed as:

$$ abla_{\theta_i} J(\theta_i) = \mathbb{E}_{s, a \sim \mathcal{D}} \left[ abla_{\theta_i} \pi_i(a_i|o_i) abla_{a_i} Q_i^\phi(s, a_1, ..., a_N) \right] $$

QMIX extends this by enforcing monotonicity between centralized and decentralized value functions through a mixing network that satisfies:

$$ \frac{\partial Q_{tot}}{\partial Q_i} \geq 0 \quad \forall i $$

Equilibrium Concepts

MARL solutions often converge to Nash equilibria rather than optimal policies. In a Nash equilibrium, no agent can improve its expected return by unilaterally changing its policy:

$$ V_i(\pi_i^*, \pi_{-i}^*) \geq V_i(\pi_i, \pi_{-i}^*) \quad \forall \pi_i, i $$

Recent work explores correlated equilibria and learning in Stackelberg games for hierarchical multi-agent systems. Evolutionary game theory provides tools to analyze population dynamics in large-scale MARL.

Applications

MARL has demonstrated success in autonomous driving coordination, where agents must negotiate merging lanes while avoiding collisions. In robotics swarms, MARL enables emergent flocking behaviors without explicit communication protocols. The StarCraft Multi-Agent Challenge (SMAC) benchmark has become a standard testbed for cooperative MARL algorithms, requiring precise unit micromanagement and tactical coordination.

Emerging applications include:

Multi-Agent Reinforcement Learning – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the interaction between multiple agents in a Markov game, illustrating the joint action space and reward flow.

Hierarchical Reinforcement Learning

Hierarchical Reinforcement Learning (HRL) decomposes complex tasks into manageable subtasks, enabling more efficient exploration and credit assignment in long-horizon problems. By introducing temporal abstraction, HRL frameworks allow agents to operate at multiple levels of granularity, reducing the curse of dimensionality inherent in flat RL approaches.

Options Framework

The options framework formalizes temporally extended actions as options, defined by a tuple (I, π, β), where:

$$ Q_\Omega(s, \omega) = \mathbb{E}\left[ \sum_{k=0}^\infty \gamma^k r_{t+k} \mid s_t = s, \omega_t = \omega \right] $$

Here, QΩ(s, ω) represents the value of executing option ω in state s, with γ as the discount factor. The option-value function generalizes the standard action-value function to temporal abstractions.

MAXQ Value Function Decomposition

The MAXQ method decomposes the value function hierarchically, expressing the value of a parent task as the sum of its child task values. For a task M with subtasks m1, ..., mn, the projected value function is:

$$ V^\pi(s) = \sum_{i=1}^n V^{\pi_i}(s) + C^\pi(s, \pi(s)) $$

where Vπi(s) is the value of subtask mi and Cπ(s, a) is the completion function representing the expected return after completing action a in state s.

Feudal Reinforcement Learning

Inspired by hierarchical governance, feudal RL employs a manager-worker architecture. The manager operates at a higher temporal resolution, setting subgoals for the worker, which executes primitive actions. The manager's policy is trained to maximize the intrinsic reward:

$$ r_t^{manager} = \mathbb{1}(s_t \in \mathcal{G}) - c \cdot d(s_t, g_t) $$

where 𝒢 is the set of subgoal states, d(·,·) is a distance metric, and c scales the penalty for deviating from the current subgoal gt.

Recent Advances: HRL with Neural Networks

Modern HRL combines hierarchical decomposition with deep learning. For instance, the HIRO algorithm trains a higher-level policy that operates on a slower timescale, with its actions serving as goals for the lower-level policy. The lower-level policy is rewarded for achieving these goals:

$$ r_t^{low} = -\| s_{t+k} - g_t \|_2 $$

where k is the temporal abstraction interval. This approach has demonstrated success in complex environments like Ant Maze and Montezuma's Revenge.

Hierarchical Reinforcement Learning – Reinforcement Learning: Core Concepts – Tutorial Diagram
Diagram Description: The diagram would show the hierarchical structure of tasks and subtasks in MAXQ decomposition and the manager-worker interaction in feudal RL, which are inherently spatial relationships.

5.3 Reward Shaping and Sparse Rewards

Reward shaping is a critical technique in reinforcement learning (RL) designed to address the challenge of sparse rewards, where the agent receives feedback only upon achieving rare milestones. In sparse reward environments, the lack of frequent feedback makes learning inefficient, as the agent struggles to associate actions with long-term outcomes. Reward shaping introduces intermediate rewards to guide the agent toward optimal behavior without altering the underlying goal.

Formalizing Reward Shaping

The modified reward function R' combines the original sparse reward R with a shaping term F:

$$ R'(s, a, s') = R(s, a, s') + F(s, s') $$

where F(s, s') is a potential-based shaping function ensuring policy invariance. Ng et al. (1999) proved that if F derives from a potential function Φ such that:

$$ F(s, s') = \gamma \Phi(s') - \Phi(s) $$

then the optimal policy remains unchanged. Here, γ is the discount factor. This formulation prevents the agent from exploiting shaping rewards for unintended behaviors.

Sparse Reward Challenges

In environments like robotic manipulation or Montezuma’s Revenge, sparse rewards lead to:

Practical Applications of Reward Shaping

In AlphaGo, shaping rewards guided the agent toward capturing stones, while the ultimate reward remained winning the game. Similarly, in autonomous driving, intermediate rewards for lane-keeping and collision avoidance accelerate learning before the sparse "successful trip" reward is achieved.

Advanced Techniques

Recent methods combine reward shaping with intrinsic motivation:

These approaches mitigate sparse rewards without manual engineering of shaping functions. For example, HER reformulates the reward function during training as:

$$ R_{HER}(s, a, g') = \mathbb{I}(f(s) = g') $$

where g' is a substitute goal sampled from the episode, and f(s) maps states to achieved goals.

6. Foundational Papers and Books

6.1 Foundational Papers and Books

6.2 Online Courses and Tutorials

6.3 Open-Source Libraries and Tools