INTRODUCTION TO REINFORCEMENT LEARNING
Reinforcement Learning is a branch of machine learning where an agent learns to make decisions by interacting with an environment. Unlike supervised learning where we provide labeled examples, or unsupervised learning where we find patterns in data, reinforcement learning works through trial and error. The agent receives feedback in the form of rewards or penalties based on its actions, and over time, it learns which actions lead to the best outcomes.
Think of it like training a dog. When the dog performs a trick correctly, you give it a treat (positive reward). When it misbehaves, you might withhold the treat or give a verbal correction (negative reward or penalty). Over time, the dog learns which behaviors lead to treats and which do not. Similarly, in reinforcement learning, an agent explores different actions in different situations and learns from the consequences.
The fundamental idea is that the agent does not need to be told what to do explicitly. Instead, it discovers the best strategy through experience. This makes reinforcement learning particularly powerful for problems where the optimal solution is not known in advance or where the environment is too complex to model completely.
WHEN TO USE REINFORCEMENT LEARNING
Reinforcement learning is particularly suitable for problems that have certain characteristics. First, the problem should involve sequential decision making where actions taken now affect future states and rewards. This temporal aspect is crucial because reinforcement learning algorithms are designed to maximize cumulative rewards over time, not just immediate rewards.
Second, you should use reinforcement learning when you have a well-defined reward signal that can guide learning. The reward signal tells the agent how well it is doing, but it does not tell the agent how to improve. The agent must figure out the improvement strategy on its own.
Third, reinforcement learning works well when you can simulate or interact with the environment many times. Learning requires exploration, and exploration requires many interactions. If each interaction is extremely expensive or time-consuming in the real world, you might need a simulator.
Fourth, the problem should be one where the optimal policy is not obvious or is too complex to program manually. If you already know the best strategy, you do not need reinforcement learning. However, if the strategy is complex, depends on many factors, or needs to adapt to changing conditions, reinforcement learning can discover and maintain an optimal policy.
Common applications include game playing where the agent learns to play games like chess, Go, or video games. Robotics is another major area where robots learn to walk, grasp objects, or navigate environments. Autonomous vehicles use reinforcement learning to make driving decisions. Resource management problems like optimizing energy consumption, managing traffic lights, or allocating computing resources benefit from reinforcement learning. Recommendation systems can use reinforcement learning to personalize content over time based on user interactions.
HOW REINFORCEMENT LEARNING WORKS
The reinforcement learning framework consists of several key components that work together. The agent is the learner or decision maker. It observes the current state of the environment and chooses actions based on its policy. The environment is everything the agent interacts with. It receives actions from the agent and responds with new states and rewards.
The state represents the current situation or configuration of the environment. States contain all relevant information needed to make decisions. The action is what the agent can do. The set of all possible actions is called the action space. Actions can be discrete like moving left or right, or continuous like setting a motor speed to any value between zero and maximum.
The reward is a scalar feedback signal that indicates how good or bad the agent's action was. Rewards can be positive for desirable outcomes or negative for undesirable ones. The policy is the agent's strategy for choosing actions. It maps states to actions. The policy can be deterministic, always choosing the same action in a given state, or stochastic, choosing actions according to a probability distribution.
The value function estimates how good it is to be in a particular state or to take a particular action in a state. It represents the expected cumulative reward from that point forward. The model is an optional component that represents the agent's understanding of how the environment works. Model-based methods use this to plan ahead, while model-free methods learn directly from experience without building an explicit model.
The learning process follows a cycle. The agent observes the current state of the environment. Based on this state and its current policy, the agent selects an action. The environment responds to this action by transitioning to a new state and providing a reward. The agent uses this experience, consisting of the old state, action, reward, and new state, to update its policy or value function. This cycle repeats many times, and through this repetition, the agent improves its decision-making ability.
MATHEMATICAL FOUNDATIONS
To understand reinforcement learning deeply, we need to establish the mathematical framework. The interaction between agent and environment is formalized as a Markov Decision Process or MDP. An MDP is defined by a tuple consisting of a state space, an action space, a transition probability function, a reward function, and a discount factor.
The state space S is the set of all possible states. The action space A is the set of all possible actions. The transition probability function P(s'|s,a) gives the probability of transitioning to state s' when taking action a in state s. The reward function R(s,a,s') gives the immediate reward received when transitioning from state s to state s' via action a. The discount factor gamma, written as γ, is a value between zero and one that determines how much future rewards are worth compared to immediate rewards.
The Markov property is crucial. It states that the future depends only on the current state and action, not on the history of how we got to the current state. Mathematically, P(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},...,s_0,a_0) equals P(s_{t+1}|s_t,a_t). This property allows us to make decisions based solely on the current state without needing to remember the entire history.
The return G_t is the total discounted reward from time step t onward. It is calculated as the sum from k equals zero to infinity of gamma to the power k times r_{t+k+1}. The discount factor gamma ensures that this sum converges even for infinite horizons. When gamma is close to one, the agent cares about long-term rewards. When gamma is close to zero, the agent focuses on immediate rewards.
The state value function V^π(s) represents the expected return when starting in state s and following policy π thereafter. Mathematically, V^π(s) equals the expected value of G_t given that s_t equals s and the agent follows policy π. This tells us how good it is to be in a particular state under a particular policy.
The action value function Q^π(s,a) represents the expected return when starting in state s, taking action a, and then following policy π. It is defined as Q^π(s,a) equals the expected value of G_t given that s_t equals s, a_t equals a, and the agent follows policy π thereafter. This tells us how good it is to take a particular action in a particular state.
The Bellman equations provide recursive relationships for value functions. For the state value function, V^π(s) equals the sum over all actions a of π(a|s) times the sum over all next states s' and rewards r of P(s',r|s,a) times the quantity r plus gamma times V^π(s'). This equation says that the value of a state equals the expected immediate reward plus the discounted value of the next state.
For the action value function, Q^π(s,a) equals the sum over all next states s' and rewards r of P(s',r|s,a) times the quantity r plus gamma times the sum over all next actions a' of π(a'|s') times Q^π(s',a'). These Bellman equations are fundamental to many reinforcement learning algorithms.
The optimal value functions are defined as V*(s) equals the maximum over all policies π of V^π(s), and Q*(s,a) equals the maximum over all policies π of Q^π(s,a). The optimal policy π* is one that achieves these optimal values. The Bellman optimality equations state that V*(s) equals the maximum over all actions a of the sum over all s' and r of P(s',r|s,a) times the quantity r plus gamma times V*(s'), and Q*(s,a) equals the sum over all s' and r of P(s',r|s,a) times the quantity r plus gamma times the maximum over all a' of Q*(s',a').
EXPLORATION VERSUS EXPLOITATION
One of the fundamental challenges in reinforcement learning is the exploration-exploitation tradeoff. Exploitation means choosing actions that the agent currently believes are best based on its experience so far. Exploration means trying actions that might not seem optimal now but could lead to discovering better strategies.
If an agent only exploits, it might get stuck with a suboptimal policy because it never tries alternatives. If an agent only explores, it never benefits from what it has learned. The agent needs to balance both.
The epsilon-greedy strategy is a simple approach. With probability epsilon, the agent chooses a random action to explore. With probability one minus epsilon, it chooses the action it currently believes is best to exploit. Typically, epsilon starts high to encourage exploration early on and decreases over time as the agent becomes more confident in its knowledge.
The softmax or Boltzmann exploration strategy chooses actions according to a probability distribution based on their estimated values. Actions with higher estimated values are more likely to be chosen, but all actions have some probability. The temperature parameter controls how much the agent favors high-value actions. High temperature makes the distribution more uniform, encouraging exploration. Low temperature makes it more peaked, encouraging exploitation.
Upper Confidence Bound or UCB methods balance exploration and exploitation by adding an exploration bonus to value estimates. Actions that have been tried less often get a higher bonus, encouraging the agent to explore uncertain actions. The bonus decreases as actions are tried more often and uncertainty decreases.
DYNAMIC PROGRAMMING METHODS
Dynamic programming methods assume we have a complete model of the environment, meaning we know the transition probabilities and reward function. While this assumption is often unrealistic, understanding dynamic programming provides the foundation for many practical algorithms.
Policy evaluation computes the value function for a given policy. We start with an arbitrary value function and iteratively update it using the Bellman equation until it converges. For each state s, we update V(s) to equal the sum over all actions a of π(a|s) times the sum over all s' and r of P(s',r|s,a) times the quantity r plus gamma times V(s'). We repeat this update for all states until the value function stops changing significantly.
Policy improvement takes a value function and produces a better policy. For each state s, we choose the action that maximizes the sum over all s' and r of P(s',r|s,a) times the quantity r plus gamma times V(s'). This greedy policy with respect to the value function is guaranteed to be at least as good as the original policy.
Policy iteration alternates between policy evaluation and policy improvement. We start with an arbitrary policy, evaluate it to get its value function, improve the policy based on this value function, and repeat. This process converges to the optimal policy.
Value iteration combines policy evaluation and improvement into a single update. For each state s, we update V(s) to equal the maximum over all actions a of the sum over all s' and r of P(s',r|s,a) times the quantity r plus gamma times V(s'). We repeat this for all states until convergence. The optimal policy can then be extracted by choosing actions greedily with respect to the final value function.
Here is a simple example of value iteration in code:
import numpy as np
def value_iteration(states, actions, transitions, rewards, gamma, theta):
# Initialize value function to zeros
V = {s: 0.0 for s in states}
while True:
delta = 0
# Update value for each state
for s in states:
v = V[s]
# Compute value for each possible action
action_values = []
for a in actions:
# Sum over all possible next states
value = 0
for s_prime in states:
prob = transitions[s][a][s_prime]
reward = rewards[s][a][s_prime]
value += prob * (reward + gamma * V[s_prime])
action_values.append(value)
# Take maximum over actions
V[s] = max(action_values)
# Track maximum change
delta = max(delta, abs(v - V[s]))
# Check convergence
if delta < theta:
break
# Extract optimal policy
policy = {}
for s in states:
action_values = []
for a in actions:
value = 0
for s_prime in states:
prob = transitions[s][a][s_prime]
reward = rewards[s][a][s_prime]
value += prob * (reward + gamma * V[s_prime])
action_values.append(value)
# Choose action with highest value
policy[s] = actions[np.argmax(action_values)]
return V, policy
This code implements the value iteration algorithm. It iteratively updates the value function for each state by considering all possible actions and choosing the maximum. The transitions dictionary contains the transition probabilities, and the rewards dictionary contains the reward function. The algorithm continues until the maximum change in any state value is below the threshold theta.
MONTE CARLO METHODS
Monte Carlo methods learn from complete episodes of experience without requiring a model of the environment. An episode is a sequence of states, actions, and rewards that ends in a terminal state. Monte Carlo methods are particularly useful when we can easily simulate or observe complete episodes but do not know the environment dynamics.
The basic idea is to estimate value functions by averaging the returns observed after visiting states or taking actions. For state value estimation, every time we visit a state in an episode, we record the return from that point onward. We then average all returns observed for that state across many episodes.
There are two variants: first-visit Monte Carlo and every-visit Monte Carlo. First-visit Monte Carlo averages returns only from the first time a state is visited in each episode. Every-visit Monte Carlo averages returns from every time a state is visited. Both converge to the true value function as the number of episodes approaches infinity.
For control, we need to estimate action values Q(s,a) rather than state values because we need to choose actions without a model. Monte Carlo control alternates between policy evaluation using Monte Carlo sampling and policy improvement.
Monte Carlo exploring starts ensures that all state-action pairs are visited. We start each episode with a randomly chosen state-action pair and then follow the current policy. This guarantees exploration of all possibilities.
On-policy Monte Carlo control uses epsilon-greedy policies. The agent follows an epsilon-greedy policy during episodes, and after each episode, it updates its action value estimates and improves the policy. The policy being learned is the same as the policy being followed, hence on-policy.
Off-policy Monte Carlo control separates the behavior policy used to generate episodes from the target policy being learned. The behavior policy is typically exploratory to ensure good coverage of the state-action space, while the target policy is greedy with respect to current value estimates. Importance sampling is used to correct for the difference between the two policies.
Here is an example of first-visit Monte Carlo policy evaluation:
def monte_carlo_policy_evaluation(policy, num_episodes, gamma):
# Returns stores all observed returns for each state
returns = {}
# V stores the estimated value for each state
V = {}
for episode_num in range(num_episodes):
# Generate an episode following the policy
episode = generate_episode(policy)
# Track which states we have seen in this episode
visited_states = set()
# Process the episode backwards to compute returns
G = 0
for t in range(len(episode) - 1, -1, -1):
state, action, reward = episode[t]
G = gamma * G + reward
# First-visit: only process if this is the first time we see this state
if state not in visited_states:
visited_states.add(state)
# Initialize if this is the first time we see this state overall
if state not in returns:
returns[state] = []
# Record the return
returns[state].append(G)
# Update value estimate as average of all returns
V[state] = sum(returns[state]) / len(returns[state])
return V
This code shows how Monte Carlo policy evaluation works. For each episode, we compute the return from each state and average these returns across episodes. The generate_episode function would simulate or observe an episode following the given policy.
TEMPORAL DIFFERENCE LEARNING
Temporal Difference or TD learning combines ideas from Monte Carlo and dynamic programming. Like Monte Carlo, TD methods learn from experience without a model. Like dynamic programming, TD methods update estimates based on other estimates without waiting for a final outcome.
The key insight is that we do not need to wait until the end of an episode to update our estimates. Instead, we can update them after each step using the observed reward and the estimated value of the next state. This is called bootstrapping because we are using our own estimates to update our estimates.
The simplest TD method is TD(0) for policy evaluation. After each transition from state s to state s' with reward r, we update V(s) using the formula V(s) gets updated to V(s) plus alpha times the quantity r plus gamma times V(s') minus V(s). Here alpha is the learning rate that controls how much we adjust our estimate based on new information.
The quantity r plus gamma times V(s') minus V(s) is called the TD error. It represents the difference between our current estimate V(s) and a better estimate r plus gamma times V(s') based on the observed reward and the value of the next state. If the TD error is positive, we increase our estimate of V(s). If it is negative, we decrease it.
TD learning has several advantages over Monte Carlo. It can learn from incomplete episodes, which is essential for continuing tasks that never end. It can learn online during an episode rather than waiting until the end. It typically has lower variance than Monte Carlo because it relies on the value of the next state rather than the entire subsequent return.
For control, we need to estimate action values. SARSA is an on-policy TD control algorithm. The name comes from the tuple State, Action, Reward, next State, next Action. After each transition, we update Q(s,a) using the formula Q(s,a) gets updated to Q(s,a) plus alpha times the quantity r plus gamma times Q(s',a') minus Q(s,a), where a' is the action actually taken in state s'.
Q-learning is an off-policy TD control algorithm. It updates Q(s,a) using the formula Q(s,a) gets updated to Q(s,a) plus alpha times the quantity r plus gamma times the maximum over all actions a' of Q(s',a') minus Q(s,a). Notice that we use the maximum action value in the next state rather than the action actually taken. This allows Q-learning to learn the optimal policy even while following an exploratory policy.
Expected SARSA is a variant that uses the expected value over next actions rather than the actual next action or the maximum. The update is Q(s,a) gets updated to Q(s,a) plus alpha times the quantity r plus gamma times the sum over all a' of π(a'|s') times Q(s',a') minus Q(s,a). This reduces variance compared to SARSA.
Here is an implementation of Q-learning:
import numpy as np
def q_learning(env, num_episodes, alpha, gamma, epsilon):
# Initialize Q-values to zero
Q = {}
for episode in range(num_episodes):
state = env.reset()
done = False
while not done:
# Initialize Q-values for new states
if state not in Q:
Q[state] = {a: 0.0 for a in env.get_actions(state)}
# Epsilon-greedy action selection
if np.random.random() < epsilon:
action = np.random.choice(env.get_actions(state))
else:
action = max(Q[state], key=Q[state].get)
# Take action and observe result
next_state, reward, done = env.step(action)
# Initialize Q-values for new next state
if next_state not in Q:
Q[next_state] = {a: 0.0 for a in env.get_actions(next_state)}
# Q-learning update
if not done:
max_next_q = max(Q[next_state].values())
else:
max_next_q = 0.0
td_target = reward + gamma * max_next_q
td_error = td_target - Q[state][action]
Q[state][action] = Q[state][action] + alpha * td_error
state = next_state
return Q
This code implements Q-learning. The environment provides methods to reset to an initial state, get available actions, and step forward by taking an action. The algorithm maintains Q-values for all state-action pairs and updates them using the Q-learning rule after each transition.
N-STEP METHODS
The methods we have discussed so far represent two extremes. Monte Carlo methods wait until the end of an episode and use the full return. One-step TD methods update after each step using only the immediate reward and the value of the next state. N-step methods provide a middle ground by looking ahead n steps before updating.
The n-step return G_t^(n) is defined as the sum from i equals zero to n minus one of gamma to the power i times r_{t+i+1} plus gamma to the power n times V(s_{t+n}). For n equals one, this reduces to the one-step TD target. As n approaches infinity, it approaches the Monte Carlo return.
The n-step TD update is V(s_t) gets updated to V(s_t) plus alpha times the quantity G_t^(n) minus V(s_t). We wait n steps, compute the n-step return, and then update the value of the state we were in n steps ago.
For control, n-step SARSA uses the n-step return for action values. The n-step return is the sum from i equals zero to n minus one of gamma to the power i times r_{t+i+1} plus gamma to the power n times Q(s_{t+n}, a_{t+n}). We update Q(s_t, a_t) using this n-step return.
The choice of n involves a tradeoff. Larger n reduces bias because we use more actual rewards rather than estimated values. However, larger n increases variance because we are summing more random rewards, and it increases the delay before we can make updates. In practice, intermediate values of n often work best.
ELIGIBILITY TRACES
Eligibility traces provide a mechanism for efficiently combining information from multiple time scales. They allow us to update all previously visited states after each step rather than waiting n steps to update a single state.
The idea is to maintain an eligibility trace for each state. When we visit a state, its eligibility trace is increased. At each time step, all eligibility traces decay by a factor of gamma times lambda, where lambda is a parameter between zero and one. When we observe a TD error, we update all states in proportion to their eligibility traces.
For TD(lambda), the eligibility trace e_t(s) is updated as follows. For all states s, e_t(s) equals gamma times lambda times e_{t-1}(s). For the current state s_t, we add one to e_t(s_t). The value update is V(s) gets updated to V(s) plus alpha times delta_t times e_t(s) for all states s, where delta_t is the TD error r_{t+1} plus gamma times V(s_{t+1}) minus V(s_t).
When lambda equals zero, only the current state is updated, and we get one-step TD. When lambda equals one, the algorithm is equivalent to Monte Carlo in the offline case. Intermediate values of lambda provide a smooth interpolation.
For control, SARSA(lambda) uses eligibility traces with action values. We maintain an eligibility trace for each state-action pair and update all Q-values in proportion to their traces after each step.
Eligibility traces are particularly useful for problems with delayed rewards. They allow credit to propagate backward through a sequence of states quickly. Without eligibility traces, it takes many episodes for credit to propagate from a reward back to the states that led to it. With eligibility traces, credit propagates in a single episode.
FUNCTION APPROXIMATION
So far we have assumed that we can maintain a separate value for each state or state-action pair. This works for small problems, but many real-world problems have enormous or even infinite state spaces. Function approximation allows us to generalize from limited experience to unseen states.
Instead of storing a table of values, we use a parameterized function to approximate the value function. For example, we might use a linear function V(s,w) equals the sum over i of w_i times x_i(s), where x_i(s) are features of state s and w_i are weights we learn. More complex approximators like neural networks can also be used.
The key idea is that we update the parameters to reduce the error between our approximation and the target values we observe. For TD learning with function approximation, after each transition we update the weights using gradient descent. The update is w gets updated to w plus alpha times the quantity r plus gamma times V(s',w) minus V(s,w) times the gradient of V(s,w) with respect to w.
For linear function approximation, the gradient is simply the feature vector x(s). The update becomes w gets updated to w plus alpha times the quantity r plus gamma times V(s',w) minus V(s,w) times x(s).
For action value approximation, we use Q(s,a,w) and update similarly. With linear approximation, we might use features that depend on both state and action.
Function approximation introduces new challenges. The most significant is that we lose the convergence guarantees of tabular methods. With certain combinations of function approximators, bootstrapping, and off-policy learning, the algorithm can diverge. However, in practice, function approximation works well and is essential for large-scale problems.
Here is an example of linear function approximation for TD learning:
import numpy as np
class LinearValueFunction:
def __init__(self, feature_dim):
# Initialize weights to zero
self.w = np.zeros(feature_dim)
def value(self, features):
# Compute value as dot product of weights and features
return np.dot(self.w, features)
def update(self, features, target, alpha):
# Compute current value
current_value = self.value(features)
# Compute TD error
td_error = target - current_value
# Update weights using gradient descent
self.w += alpha * td_error * features
def td_learning_with_linear_approximation(env, num_episodes, alpha, gamma):
# Create value function approximator
feature_dim = env.get_feature_dim()
value_function = LinearValueFunction(feature_dim)
for episode in range(num_episodes):
state = env.reset()
done = False
while not done:
# Get features for current state
features = env.get_features(state)
# Take action (using some policy)
action = env.get_action(state)
# Observe result
next_state, reward, done = env.step(action)
# Compute TD target
if not done:
next_features = env.get_features(next_state)
td_target = reward + gamma * value_function.value(next_features)
else:
td_target = reward
# Update value function
value_function.update(features, td_target, alpha)
state = next_state
return value_function
This code shows how to implement TD learning with linear function approximation. The environment provides features for each state, and we learn weights that map features to values. The update rule follows the gradient descent formula.
DEEP REINFORCEMENT LEARNING
Deep reinforcement learning uses deep neural networks as function approximators. This has enabled reinforcement learning to solve problems with high-dimensional state spaces like images or complex sensor data.
Deep Q-Network or DQN was a breakthrough algorithm that combined Q-learning with deep neural networks. The network takes a state as input and outputs Q-values for all actions. The network is trained to minimize the squared TD error.
DQN introduced two key innovations to stabilize training. Experience replay stores transitions in a replay buffer and samples random minibatches for training. This breaks the correlation between consecutive samples and allows the network to learn from the same experience multiple times. The target network is a separate network with parameters that are updated less frequently. This provides stable targets for the TD error and prevents the instability that can occur when both the current Q-values and the targets are changing rapidly.
The DQN loss function is the mean squared error between the predicted Q-value Q(s,a,theta) and the target y equals r plus gamma times the maximum over a' of Q(s',a',theta^-), where theta are the current network parameters and theta^- are the target network parameters.
Policy gradient methods take a different approach. Instead of learning a value function and deriving a policy from it, they directly parameterize the policy and optimize it using gradient ascent on expected return. The policy is represented as π(a|s,theta), the probability of taking action a in state s given parameters theta.
The policy gradient theorem states that the gradient of the expected return with respect to the policy parameters is the expected value over states and actions of the gradient of log π(a|s,theta) times Q^π(s,a). This tells us how to adjust the parameters to increase expected return.
REINFORCE is a basic policy gradient algorithm. After each episode, we update the policy parameters using theta gets updated to theta plus alpha times the sum over all time steps t of the gradient of log π(a_t|s_t,theta) times G_t, where G_t is the return from time t onward.
Actor-Critic methods combine value-based and policy-based approaches. The actor is a policy that selects actions. The critic is a value function that evaluates actions. The critic provides feedback to the actor, typically in the form of a TD error, which is used to update the policy.
The advantage function A(s,a) equals Q(s,a) minus V(s) measures how much better action a is compared to the average action in state s. Using the advantage instead of the return in policy gradient updates reduces variance.
Advantage Actor-Critic or A2C uses the TD error as an estimate of the advantage. The policy update is theta gets updated to theta plus alpha times the gradient of log π(a|s,theta) times delta, where delta is the TD error.
Asynchronous Advantage Actor-Critic or A3C runs multiple agents in parallel, each interacting with its own copy of the environment. The agents asynchronously update shared network parameters. This parallelization speeds up training and improves exploration.
Proximal Policy Optimization or PPO is a popular policy gradient method that constrains policy updates to prevent destructive large changes. It uses a clipped surrogate objective that limits how much the policy can change in each update.
Deep Deterministic Policy Gradient or DDPG is an actor-critic algorithm for continuous action spaces. The actor outputs a deterministic action rather than a probability distribution. The critic estimates the Q-value of the state-action pair.
Twin Delayed DDPG or TD3 improves DDPG by using two critic networks to reduce overestimation bias, delaying policy updates relative to critic updates, and adding noise to target actions for regularization.
Soft Actor-Critic or SAC is an off-policy actor-critic algorithm that maximizes both expected return and entropy of the policy. Maximizing entropy encourages exploration and leads to more robust policies.
Here is a simplified example of a DQN implementation:
import numpy as np
import torch
import torch.nn as nn
import torch.optim as optim
from collections import deque
import random
class DQN(nn.Module):
def __init__(self, state_dim, action_dim, hidden_dim):
super(DQN, self).__init__()
self.fc1 = nn.Linear(state_dim, hidden_dim)
self.fc2 = nn.Linear(hidden_dim, hidden_dim)
self.fc3 = nn.Linear(hidden_dim, 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):
batch = random.sample(self.buffer, batch_size)
states, actions, rewards, next_states, dones = zip(*batch)
return (np.array(states), np.array(actions), np.array(rewards),
np.array(next_states), np.array(dones))
def __len__(self):
return len(self.buffer)
class DQNAgent:
def __init__(self, state_dim, action_dim, hidden_dim=128, lr=0.001,
gamma=0.99, epsilon=1.0, epsilon_decay=0.995,
epsilon_min=0.01, buffer_size=10000, batch_size=64):
self.state_dim = state_dim
self.action_dim = action_dim
self.gamma = gamma
self.epsilon = epsilon
self.epsilon_decay = epsilon_decay
self.epsilon_min = epsilon_min
self.batch_size = batch_size
# Create Q-network and target network
self.q_network = DQN(state_dim, action_dim, hidden_dim)
self.target_network = DQN(state_dim, action_dim, hidden_dim)
self.target_network.load_state_dict(self.q_network.state_dict())
self.optimizer = optim.Adam(self.q_network.parameters(), lr=lr)
self.replay_buffer = ReplayBuffer(buffer_size)
def select_action(self, state):
# Epsilon-greedy action selection
if np.random.random() < self.epsilon:
return np.random.randint(self.action_dim)
else:
with torch.no_grad():
state_tensor = torch.FloatTensor(state).unsqueeze(0)
q_values = self.q_network(state_tensor)
return q_values.argmax().item()
def train(self):
if len(self.replay_buffer) < self.batch_size:
return
# Sample batch from replay buffer
states, actions, rewards, next_states, dones = self.replay_buffer.sample(self.batch_size)
# Convert to tensors
states = torch.FloatTensor(states)
actions = torch.LongTensor(actions)
rewards = torch.FloatTensor(rewards)
next_states = torch.FloatTensor(next_states)
dones = torch.FloatTensor(dones)
# Compute current Q-values
current_q_values = self.q_network(states).gather(1, actions.unsqueeze(1))
# Compute target Q-values
with torch.no_grad():
next_q_values = self.target_network(next_states).max(1)[0]
target_q_values = rewards + (1 - dones) * self.gamma * next_q_values
# Compute loss
loss = nn.MSELoss()(current_q_values.squeeze(), target_q_values)
# Optimize
self.optimizer.zero_grad()
loss.backward()
self.optimizer.step()
# Decay epsilon
self.epsilon = max(self.epsilon_min, self.epsilon * self.epsilon_decay)
def update_target_network(self):
self.target_network.load_state_dict(self.q_network.state_dict())
This code implements a DQN agent with experience replay and a target network. The agent selects actions using epsilon-greedy exploration, stores experiences in a replay buffer, and trains the Q-network by sampling random batches from the buffer. The target network is updated periodically to provide stable targets.
MODEL-BASED REINFORCEMENT LEARNING
Model-based reinforcement learning learns a model of the environment and uses it for planning. The model predicts what will happen when the agent takes an action in a state. With a model, the agent can simulate experiences and plan ahead without interacting with the real environment.
A model consists of a transition model that predicts the next state given the current state and action, and a reward model that predicts the reward. These can be deterministic or stochastic. Learning a model is a supervised learning problem where we use observed transitions as training data.
Once we have a model, we can use it in several ways. We can use dynamic programming methods like value iteration or policy iteration if the model is complete and accurate. We can use the model to generate simulated experience for training a model-free algorithm. We can use the model for planning by simulating different action sequences and choosing the one with the highest predicted return.
Dyna-Q is an algorithm that combines model-free learning with model-based planning. It learns a Q-function from real experience using Q-learning. It also learns a model from real experience. Between real interactions, it uses the model to generate simulated experiences and updates the Q-function with these simulated experiences as well. This allows the agent to learn much faster than pure model-free methods.
Monte Carlo Tree Search or MCTS is a planning algorithm that uses a model to build a search tree. It repeatedly simulates episodes starting from the current state, using the model to predict outcomes. It balances exploration and exploitation in the tree search using the UCB formula. After many simulations, it chooses the action that was most promising.
AlphaGo and AlphaZero use MCTS combined with deep neural networks. The neural network provides both a policy to guide the search and a value function to evaluate positions. MCTS refines these estimates through simulation.
Model Predictive Control or MPC uses a model to plan a sequence of actions by optimizing over possible action sequences. At each time step, it finds the sequence of actions that maximizes predicted return over a finite horizon. It executes the first action of this sequence and then replans at the next time step.
The challenge with model-based methods is that learning an accurate model can be difficult, especially for complex environments. Model errors can compound over long horizons, leading to poor performance. However, when a good model can be learned, model-based methods are often much more sample-efficient than model-free methods.
MULTI-AGENT REINFORCEMENT LEARNING
Multi-agent reinforcement learning extends reinforcement learning to settings with multiple agents. The agents may cooperate, compete, or both. The presence of other agents makes the environment non-stationary from each agent's perspective because the other agents are also learning and changing their behavior.
In cooperative settings, all agents share the same reward and work together toward a common goal. Centralized training with decentralized execution is a common approach. During training, agents can share information and coordinate, but during execution, each agent must act based only on its own observations.
In competitive settings, agents have conflicting objectives. Game theory provides tools for analyzing such settings. A Nash equilibrium is a set of policies where no agent can improve its return by unilaterally changing its policy. Self-play, where agents train by playing against copies of themselves, is often used in competitive settings.
In mixed settings, agents may sometimes cooperate and sometimes compete. Communication between agents can help coordination. Agents can learn to communicate by treating communication as actions that affect the environment.
Multi-agent credit assignment is challenging. When multiple agents contribute to an outcome, it can be difficult to determine which agent's actions were responsible. Counterfactual reasoning, where we consider what would have happened if an agent had acted differently, can help address this.
INVERSE REINFORCEMENT LEARNING
Inverse reinforcement learning or IRL addresses the problem of learning a reward function from demonstrations. Instead of specifying a reward function manually, we observe an expert performing a task and infer what reward function the expert is optimizing.
The basic IRL problem is: given a set of state-action trajectories from an expert, find a reward function such that the expert's policy is optimal or near-optimal for that reward function. This is an ill-posed problem because many reward functions could explain the same behavior.
Maximum Entropy IRL resolves this ambiguity by choosing the reward function that makes the expert's demonstrations most likely under a maximum entropy policy. The maximum entropy principle favors policies that are as random as possible while still achieving the desired behavior.
Generative Adversarial Imitation Learning or GAIL takes a different approach. Instead of explicitly recovering a reward function, it trains a policy to match the expert's state-action distribution. It uses a discriminator to distinguish between expert demonstrations and agent behavior, and trains the policy to fool the discriminator.
IRL is useful when it is easier to demonstrate desired behavior than to specify a reward function. It is particularly relevant for robotics and autonomous systems where we want agents to imitate human behavior.
HIERARCHICAL REINFORCEMENT LEARNING
Hierarchical reinforcement learning decomposes complex tasks into subtasks. Instead of learning a single flat policy, the agent learns a hierarchy of policies at different levels of abstraction.
Options are a formalization of temporally extended actions. An option consists of a policy that is followed for multiple time steps, a termination condition that determines when the option ends, and an initiation set of states where the option can be started. The agent learns both which options to use and the policies within each option.
Hierarchical Actor-Critic or HAC learns a hierarchy of policies. Higher-level policies set goals for lower-level policies. Each level learns to achieve the goals set by the level above while setting appropriate subgoals for the level below.
Feudal Reinforcement Learning uses a manager-worker hierarchy. The manager sets goals for workers over a longer time scale. Workers learn to achieve these goals over shorter time scales. This separation of time scales helps with credit assignment and exploration.
Hierarchical approaches can significantly speed up learning for complex tasks by providing structure and enabling reuse of learned skills across different tasks.
TRANSFER LEARNING AND META-LEARNING
Transfer learning applies knowledge learned in one task to a different but related task. This can dramatically reduce the amount of experience needed to learn a new task.
Progressive networks freeze learned networks and add new capacity for new tasks. The new network can access features from the old network, allowing it to leverage previously learned representations.
Fine-tuning starts with a network trained on one task and continues training on a new task. The initial training provides a good starting point, and the fine-tuning adapts the network to the new task.
Meta-learning or learning to learn trains an agent to learn new tasks quickly. The agent is trained on a distribution of tasks, and the goal is to learn an algorithm or initialization that allows rapid adaptation to new tasks from the same distribution.
Model-Agnostic Meta-Learning or MAML finds an initialization of network parameters such that a small number of gradient steps on a new task leads to good performance. The meta-training process optimizes this initialization across many tasks.
SAFE REINFORCEMENT LEARNING
Safe reinforcement learning addresses the challenge of learning while avoiding dangerous or undesirable states. This is critical for real-world applications where mistakes can be costly or harmful.
Constrained reinforcement learning formulates safety as constraints that must be satisfied. The agent maximizes expected return subject to constraints on expected costs. Lagrangian methods convert the constrained problem into an unconstrained one by adding penalty terms for constraint violations.
Safe exploration ensures that the agent does not visit dangerous states during learning. This can be achieved by using a shield that prevents unsafe actions, learning in simulation before deploying in the real world, or using demonstrations to initialize the policy in a safe region.
Risk-sensitive reinforcement learning considers not just expected return but also the variance or other risk measures. This leads to more conservative policies that avoid high-risk actions even if they have high expected return.
OFFLINE REINFORCEMENT LEARNING
Offline reinforcement learning, also called batch reinforcement learning, learns from a fixed dataset of experiences without interacting with the environment. This is important when online interaction is expensive, dangerous, or impossible.
The main challenge is distribution shift. The dataset was collected using some behavior policy, but we want to learn a different, better policy. If the learned policy takes actions that are not well-represented in the dataset, we cannot accurately estimate their values.
Conservative Q-Learning or CQL addresses this by penalizing Q-values for actions that are unlikely under the data distribution. This prevents the agent from being overly optimistic about actions it has not seen much.
Behavior cloning simply learns to imitate the behavior in the dataset using supervised learning. This avoids distribution shift but cannot improve beyond the performance in the dataset.
Offline policy evaluation estimates the return of a policy using only the dataset. Importance sampling and doubly robust estimators are techniques for offline policy evaluation.
REWARD SHAPING
Reward shaping modifies the reward function to make learning easier while preserving the optimal policy. The key insight is that we can add a potential-based shaping function to the reward without changing which policy is optimal.
A potential-based shaping function has the form F(s,s') equals gamma times Phi(s') minus Phi(s), where Phi is a potential function over states. Adding this to the reward changes the value function but not the ordering of policies, so the optimal policy remains the same.
Reward shaping can dramatically speed up learning by providing more frequent feedback. For example, in a navigation task, we might shape the reward based on distance to the goal, providing guidance even when the agent has not yet reached the goal.
However, poorly designed reward shaping can lead to unintended behavior. The agent might exploit the shaped reward in ways that do not align with the true objective. Careful design is necessary.
CURRICULUM LEARNING
Curriculum learning trains the agent on a sequence of tasks of increasing difficulty. Starting with easier tasks allows the agent to learn basic skills before tackling harder challenges.
Automatic curriculum generation adapts the difficulty based on the agent's current performance. Tasks that are too easy provide little learning signal, while tasks that are too hard lead to random behavior. The curriculum should focus on tasks at the frontier of the agent's current ability.
Self-play can be viewed as a form of curriculum learning. As the agent improves, its opponents also improve, automatically adjusting the difficulty.
CHOOSING THE RIGHT ALGORITHM
Selecting the appropriate reinforcement learning algorithm depends on several factors related to your problem and constraints.
If you have a complete and accurate model of the environment, dynamic programming methods like value iteration or policy iteration are efficient and guaranteed to find the optimal policy. However, most real-world problems do not have such models.
For problems where you can easily simulate complete episodes but do not have a model, Monte Carlo methods are appropriate. They are simple to implement and work well when episodes are not too long. However, they require episodic tasks and can have high variance.
For problems where episodes are very long or the task is continuing, temporal difference methods are better. TD learning can learn online from incomplete episodes. Q-learning is a good default choice for discrete action spaces. It is off-policy, allowing it to learn the optimal policy while following an exploratory policy.
SARSA is preferable when you care about the performance of the learning policy itself, not just the final learned policy. Because it is on-policy, it accounts for exploration during learning.
For problems with large or continuous state spaces, you need function approximation. Linear function approximation is simple and has good theoretical properties but may not be expressive enough for complex problems. Deep neural networks can represent complex functions but require more data and careful tuning.
DQN is a good starting point for discrete action spaces with high-dimensional states like images. It combines Q-learning with deep neural networks and includes experience replay and target networks for stability.
For continuous action spaces, policy gradient methods or actor-critic methods are necessary. DDPG, TD3, and SAC are popular choices. SAC is often the most robust due to its entropy regularization.
If sample efficiency is critical and you can learn a good model, model-based methods can be much more efficient than model-free methods. Dyna-Q combines the benefits of both. However, model learning adds complexity and potential for model errors.
For problems with sparse rewards, consider hierarchical methods, reward shaping, or imitation learning. Sparse rewards make exploration difficult, and these techniques can provide additional guidance.
For multi-agent settings, consider whether the agents are cooperative, competitive, or mixed. Use appropriate multi-agent algorithms and consider communication and coordination mechanisms.
For safety-critical applications, use safe reinforcement learning techniques. Constrained RL, safe exploration, and offline RL can help ensure safety during learning and deployment.
For problems where you have expert demonstrations, consider imitation learning or inverse reinforcement learning. These can bootstrap learning and reduce the amount of exploration needed.
In practice, you may need to experiment with multiple algorithms and tune hyperparameters. Start with simpler methods and add complexity as needed. Use good software libraries that provide tested implementations of standard algorithms.
PRACTICAL CONSIDERATIONS
When implementing reinforcement learning in practice, several considerations beyond algorithm choice are important.
Hyperparameter tuning is critical. Learning rate, discount factor, exploration parameters, network architecture, and many other hyperparameters significantly affect performance. Grid search, random search, or Bayesian optimization can help find good hyperparameters. Start with values from the literature and adjust based on your problem.
Reward design is crucial. The reward function defines what you want the agent to achieve. It should be carefully designed to align with your true objectives. Avoid unintended consequences by thinking through how the agent might exploit the reward function. Test the reward function with simple policies before using it for learning.
State representation affects learning speed and final performance. Good features make learning easier. For high-dimensional inputs like images, use neural networks to learn representations. For structured problems, hand-crafted features based on domain knowledge can be very effective.
Exploration is often the bottleneck in learning. Ensure your exploration strategy is appropriate for your problem. For sparse rewards, consider intrinsic motivation, curiosity-driven exploration, or count-based exploration that encourages visiting new states.
Debugging reinforcement learning is challenging because many things can go wrong. Implement logging and visualization to track learning progress. Monitor the value function, policy, rewards, and other metrics. Compare against baselines like random policies or simple heuristics. Test components separately before integrating them.
Reproducibility is important for scientific work and debugging. Set random seeds, document hyperparameters, and save trained models. Use version control for code and track experiments systematically.
Computational resources can be a constraint. Deep RL often requires significant computation. Use GPUs for neural network training. Parallelize environment interactions across multiple CPUs. Consider cloud computing resources if local resources are insufficient.
Simulation versus real-world deployment involves tradeoffs. Simulation is faster and safer but may not perfectly match reality. Sim-to-real transfer techniques like domain randomization can help bridge the gap. Start in simulation, then fine-tune in the real world if possible.
FULL RUNNING EXAMPLE: GRID WORLD NAVIGATION
Now we will present a complete, production-ready implementation of a reinforcement learning system for grid world navigation. This example demonstrates Q-learning with function approximation and includes all necessary components for a real application.
import numpy as np
import random
from typing import Tuple, List, Dict, Optional
from dataclasses import dataclass
from enum import Enum
import json
import pickle
from pathlib import Path
class Action(Enum):
"""Enumeration of possible actions in the grid world."""
UP = 0
DOWN = 1
LEFT = 2
RIGHT = 3
@dataclass
class State:
"""Represents a state in the grid world."""
x: int
y: int
def __hash__(self):
return hash((self.x, self.y))
def __eq__(self, other):
return self.x == other.x and self.y == other.y
@dataclass
class Transition:
"""Represents a transition in the environment."""
state: State
action: Action
reward: float
next_state: State
done: bool
class GridWorld:
"""
A grid world environment for reinforcement learning.
The agent navigates a grid to reach a goal while avoiding obstacles.
The agent receives a large positive reward for reaching the goal,
a small negative reward for each step, and a large negative reward
for hitting obstacles.
"""
def __init__(self, width: int, height: int,
obstacles: List[Tuple[int, int]],
goal: Tuple[int, int],
start: Tuple[int, int],
step_penalty: float = -0.01,
goal_reward: float = 1.0,
obstacle_penalty: float = -1.0):
"""
Initialize the grid world environment.
Args:
width: Width of the grid
height: Height of the grid
obstacles: List of (x, y) coordinates of obstacles
goal: (x, y) coordinate of the goal
start: (x, y) coordinate of the starting position
step_penalty: Reward for each step (typically negative)
goal_reward: Reward for reaching the goal
obstacle_penalty: Penalty for hitting an obstacle
"""
self.width = width
self.height = height
self.obstacles = set(obstacles)
self.goal = goal
self.start_pos = start
self.step_penalty = step_penalty
self.goal_reward = goal_reward
self.obstacle_penalty = obstacle_penalty
self.current_state = State(*start)
def reset(self) -> State:
"""Reset the environment to the starting state."""
self.current_state = State(*self.start_pos)
return self.current_state
def step(self, action: Action) -> Tuple[State, float, bool]:
"""
Execute an action and return the result.
Args:
action: The action to execute
Returns:
Tuple of (next_state, reward, done)
"""
# Calculate new position based on action
new_x, new_y = self.current_state.x, self.current_state.y
if action == Action.UP:
new_y = max(0, new_y - 1)
elif action == Action.DOWN:
new_y = min(self.height - 1, new_y + 1)
elif action == Action.LEFT:
new_x = max(0, new_x - 1)
elif action == Action.RIGHT:
new_x = min(self.width - 1, new_x + 1)
# Check if new position is valid
if (new_x, new_y) in self.obstacles:
# Hit an obstacle, stay in place and receive penalty
reward = self.obstacle_penalty
done = False
elif (new_x, new_y) == self.goal:
# Reached the goal
self.current_state = State(new_x, new_y)
reward = self.goal_reward
done = True
else:
# Normal move
self.current_state = State(new_x, new_y)
reward = self.step_penalty
done = False
return self.current_state, reward, done
def get_state_features(self, state: State) -> np.ndarray:
"""
Extract features from a state for function approximation.
Args:
state: The state to extract features from
Returns:
Feature vector as numpy array
"""
features = []
# Normalized position
features.append(state.x / self.width)
features.append(state.y / self.height)
# Distance to goal (Manhattan distance, normalized)
goal_dist = (abs(state.x - self.goal[0]) + abs(state.y - self.goal[1]))
max_dist = self.width + self.height
features.append(goal_dist / max_dist)
# Direction to goal (unit vector)
dx = self.goal[0] - state.x
dy = self.goal[1] - state.y
dist = max(1, np.sqrt(dx**2 + dy**2))
features.append(dx / dist)
features.append(dy / dist)
# Nearby obstacles (in 4 directions)
for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
check_x, check_y = state.x + dx, state.y + dy
if (check_x, check_y) in self.obstacles:
features.append(1.0)
else:
features.append(0.0)
# Bias term
features.append(1.0)
return np.array(features, dtype=np.float32)
def render(self) -> str:
"""
Create a text representation of the current state.
Returns:
String representation of the grid
"""
grid = []
for y in range(self.height):
row = []
for x in range(self.width):
if (x, y) == (self.current_state.x, self.current_state.y):
row.append('A') # Agent
elif (x, y) == self.goal:
row.append('G') # Goal
elif (x, y) in self.obstacles:
row.append('X') # Obstacle
else:
row.append('.') # Empty
grid.append(' '.join(row))
return '\n'.join(grid)
class LinearQFunction:
"""
Linear function approximation for Q-values.
Q(s, a) = w_a^T * features(s)
"""
def __init__(self, feature_dim: int, num_actions: int):
"""
Initialize the linear Q-function.
Args:
feature_dim: Dimension of the feature vector
num_actions: Number of possible actions
"""
self.feature_dim = feature_dim
self.num_actions = num_actions
# Initialize weights with small random values
self.weights = np.random.randn(num_actions, feature_dim) * 0.01
def get_q_values(self, features: np.ndarray) -> np.ndarray:
"""
Compute Q-values for all actions given state features.
Args:
features: Feature vector for the state
Returns:
Array of Q-values for each action
"""
return self.weights @ features
def get_q_value(self, features: np.ndarray, action: Action) -> float:
"""
Compute Q-value for a specific state-action pair.
Args:
features: Feature vector for the state
action: The action
Returns:
Q-value for the state-action pair
"""
return self.weights[action.value] @ features
def update(self, features: np.ndarray, action: Action,
target: float, learning_rate: float):
"""
Update weights using gradient descent.
Args:
features: Feature vector for the state
action: The action taken
target: Target Q-value
learning_rate: Learning rate for the update
"""
current_q = self.get_q_value(features, action)
error = target - current_q
self.weights[action.value] += learning_rate * error * features
def save(self, filepath: Path):
"""Save the weights to a file."""
np.save(filepath, self.weights)
def load(self, filepath: Path):
"""Load weights from a file."""
self.weights = np.load(filepath)
class ReplayBuffer:
"""Experience replay buffer for storing and sampling transitions."""
def __init__(self, capacity: int):
"""
Initialize the replay buffer.
Args:
capacity: Maximum number of transitions to store
"""
self.capacity = capacity
self.buffer: List[Transition] = []
self.position = 0
def push(self, transition: Transition):
"""
Add a transition to the buffer.
Args:
transition: The transition to add
"""
if len(self.buffer) < self.capacity:
self.buffer.append(transition)
else:
self.buffer[self.position] = transition
self.position = (self.position + 1) % self.capacity
def sample(self, batch_size: int) -> List[Transition]:
"""
Sample a batch of transitions.
Args:
batch_size: Number of transitions to sample
Returns:
List of sampled transitions
"""
return random.sample(self.buffer, batch_size)
def __len__(self) -> int:
"""Return the current size of the buffer."""
return len(self.buffer)
class QLearningAgent:
"""
Q-Learning agent with linear function approximation and experience replay.
"""
def __init__(self,
env: GridWorld,
learning_rate: float = 0.1,
discount_factor: float = 0.99,
epsilon: float = 1.0,
epsilon_decay: float = 0.995,
epsilon_min: float = 0.01,
buffer_capacity: int = 10000,
batch_size: int = 32):
"""
Initialize the Q-learning agent.
Args:
env: The environment
learning_rate: Learning rate for Q-value updates
discount_factor: Discount factor for future rewards
epsilon: Initial exploration rate
epsilon_decay: Decay rate for epsilon
epsilon_min: Minimum epsilon value
buffer_capacity: Capacity of the replay buffer
batch_size: Batch size for training
"""
self.env = env
self.learning_rate = learning_rate
self.discount_factor = discount_factor
self.epsilon = epsilon
self.epsilon_decay = epsilon_decay
self.epsilon_min = epsilon_min
self.batch_size = batch_size
# Get feature dimension from environment
sample_state = State(0, 0)
sample_features = env.get_state_features(sample_state)
feature_dim = len(sample_features)
# Initialize Q-function and replay buffer
self.q_function = LinearQFunction(feature_dim, len(Action))
self.replay_buffer = ReplayBuffer(buffer_capacity)
# Statistics
self.episode_rewards: List[float] = []
self.episode_lengths: List[int] = []
def select_action(self, state: State) -> Action:
"""
Select an action using epsilon-greedy policy.
Args:
state: Current state
Returns:
Selected action
"""
if random.random() < self.epsilon:
# Explore: choose random action
return random.choice(list(Action))
else:
# Exploit: choose best action
features = self.env.get_state_features(state)
q_values = self.q_function.get_q_values(features)
return Action(np.argmax(q_values))
def train_step(self):
"""Perform one training step using a batch from the replay buffer."""
if len(self.replay_buffer) < self.batch_size:
return
# Sample batch
batch = self.replay_buffer.sample(self.batch_size)
# Update Q-function for each transition in batch
for transition in batch:
# Get features
features = self.env.get_state_features(transition.state)
next_features = self.env.get_state_features(transition.next_state)
# Compute target
if transition.done:
target = transition.reward
else:
next_q_values = self.q_function.get_q_values(next_features)
target = transition.reward + self.discount_factor * np.max(next_q_values)
# Update weights
self.q_function.update(features, transition.action,
target, self.learning_rate)
def train_episode(self) -> Tuple[float, int]:
"""
Train for one episode.
Returns:
Tuple of (total_reward, episode_length)
"""
state = self.env.reset()
total_reward = 0
steps = 0
while True:
# Select and execute action
action = self.select_action(state)
next_state, reward, done = self.env.step(action)
# Store transition
transition = Transition(state, action, reward, next_state, done)
self.replay_buffer.push(transition)
# Train on batch
self.train_step()
# Update state and statistics
state = next_state
total_reward += reward
steps += 1
if done:
break
# Decay epsilon
self.epsilon = max(self.epsilon_min, self.epsilon * self.epsilon_decay)
return total_reward, steps
def train(self, num_episodes: int, verbose: bool = True) -> Dict:
"""
Train the agent for multiple episodes.
Args:
num_episodes: Number of episodes to train
verbose: Whether to print progress
Returns:
Dictionary with training statistics
"""
for episode in range(num_episodes):
reward, length = self.train_episode()
self.episode_rewards.append(reward)
self.episode_lengths.append(length)
if verbose and (episode + 1) % 100 == 0:
avg_reward = np.mean(self.episode_rewards[-100:])
avg_length = np.mean(self.episode_lengths[-100:])
print(f"Episode {episode + 1}/{num_episodes}, "
f"Avg Reward: {avg_reward:.3f}, "
f"Avg Length: {avg_length:.1f}, "
f"Epsilon: {self.epsilon:.3f}")
return {
'episode_rewards': self.episode_rewards,
'episode_lengths': self.episode_lengths
}
def evaluate(self, num_episodes: int = 100) -> Dict:
"""
Evaluate the agent's performance.
Args:
num_episodes: Number of episodes to evaluate
Returns:
Dictionary with evaluation statistics
"""
old_epsilon = self.epsilon
self.epsilon = 0 # No exploration during evaluation
rewards = []
lengths = []
successes = 0
for _ in range(num_episodes):
state = self.env.reset()
total_reward = 0
steps = 0
while steps < 1000: # Maximum steps per episode
action = self.select_action(state)
state, reward, done = self.env.step(action)
total_reward += reward
steps += 1
if done:
if reward > 0: # Reached goal
successes += 1
break
rewards.append(total_reward)
lengths.append(steps)
self.epsilon = old_epsilon
return {
'mean_reward': np.mean(rewards),
'std_reward': np.std(rewards),
'mean_length': np.mean(lengths),
'std_length': np.std(lengths),
'success_rate': successes / num_episodes
}
def save(self, directory: Path):
"""
Save the agent to disk.
Args:
directory: Directory to save the agent
"""
directory.mkdir(parents=True, exist_ok=True)
# Save Q-function
self.q_function.save(directory / 'q_function.npy')
# Save hyperparameters and statistics
metadata = {
'learning_rate': self.learning_rate,
'discount_factor': self.discount_factor,
'epsilon': self.epsilon,
'epsilon_decay': self.epsilon_decay,
'epsilon_min': self.epsilon_min,
'batch_size': self.batch_size,
'episode_rewards': self.episode_rewards,
'episode_lengths': self.episode_lengths
}
with open(directory / 'metadata.json', 'w') as f:
json.dump(metadata, f, indent=2)
def load(self, directory: Path):
"""
Load the agent from disk.
Args:
directory: Directory containing the saved agent
"""
# Load Q-function
self.q_function.load(directory / 'q_function.npy')
# Load metadata
with open(directory / 'metadata.json', 'r') as f:
metadata = json.load(f)
self.learning_rate = metadata['learning_rate']
self.discount_factor = metadata['discount_factor']
self.epsilon = metadata['epsilon']
self.epsilon_decay = metadata['epsilon_decay']
self.epsilon_min = metadata['epsilon_min']
self.batch_size = metadata['batch_size']
self.episode_rewards = metadata['episode_rewards']
self.episode_lengths = metadata['episode_lengths']
def create_simple_grid_world() -> GridWorld:
"""Create a simple 10x10 grid world for testing."""
obstacles = [
(3, 3), (3, 4), (3, 5),
(6, 2), (6, 3), (6, 4), (6, 5), (6, 6),
(2, 7), (3, 7), (4, 7)
]
return GridWorld(
width=10,
height=10,
obstacles=obstacles,
goal=(9, 9),
start=(0, 0),
step_penalty=-0.01,
goal_reward=1.0,
obstacle_penalty=-0.5
)
def create_complex_grid_world() -> GridWorld:
"""Create a more complex 15x15 grid world."""
obstacles = []
# Create maze-like structure
for i in range(5, 10):
obstacles.append((i, 3))
obstacles.append((i, 7))
obstacles.append((i, 11))
for i in range(3, 8):
obstacles.append((3, i))
obstacles.append((11, i))
for i in range(7, 12):
obstacles.append((3, i))
obstacles.append((11, i))
return GridWorld(
width=15,
height=15,
obstacles=obstacles,
goal=(14, 14),
start=(0, 0),
step_penalty=-0.01,
goal_reward=1.0,
obstacle_penalty=-0.5
)
def demonstrate_training():
"""Demonstrate training a Q-learning agent."""
print("Creating environment...")
env = create_simple_grid_world()
print("\nInitial environment:")
print(env.render())
print("\nCreating agent...")
agent = QLearningAgent(
env=env,
learning_rate=0.1,
discount_factor=0.99,
epsilon=1.0,
epsilon_decay=0.995,
epsilon_min=0.01,
buffer_capacity=10000,
batch_size=32
)
print("\nTraining agent...")
stats = agent.train(num_episodes=1000, verbose=True)
print("\nEvaluating agent...")
eval_stats = agent.evaluate(num_episodes=100)
print(f"Mean reward: {eval_stats['mean_reward']:.3f} +/- {eval_stats['std_reward']:.3f}")
print(f"Mean episode length: {eval_stats['mean_length']:.1f} +/- {eval_stats['std_length']:.1f}")
print(f"Success rate: {eval_stats['success_rate']:.1%}")
print("\nDemonstrating learned policy...")
state = env.reset()
print(env.render())
print()
for step in range(50):
action = agent.select_action(state)
state, reward, done = env.step(action)
print(f"Step {step + 1}: Action={action.name}, Reward={reward:.3f}")
print(env.render())
print()
if done:
print("Goal reached!")
break
print("\nSaving agent...")
save_dir = Path("trained_agent")
agent.save(save_dir)
print(f"Agent saved to {save_dir}")
return agent, stats
def demonstrate_loading():
"""Demonstrate loading a trained agent."""
print("Loading trained agent...")
env = create_simple_grid_world()
agent = QLearningAgent(env)
load_dir = Path("trained_agent")
if load_dir.exists():
agent.load(load_dir)
print(f"Agent loaded from {load_dir}")
print("\nEvaluating loaded agent...")
eval_stats = agent.evaluate(num_episodes=100)
print(f"Mean reward: {eval_stats['mean_reward']:.3f}")
print(f"Success rate: {eval_stats['success_rate']:.1%}")
else:
print(f"No saved agent found at {load_dir}")
def compare_hyperparameters():
"""Compare different hyperparameter settings."""
print("Comparing different learning rates...")
env = create_simple_grid_world()
learning_rates = [0.01, 0.05, 0.1, 0.2]
results = {}
for lr in learning_rates:
print(f"\nTraining with learning rate {lr}...")
agent = QLearningAgent(
env=env,
learning_rate=lr,
discount_factor=0.99,
epsilon=1.0,
epsilon_decay=0.995,
epsilon_min=0.01
)
agent.train(num_episodes=500, verbose=False)
eval_stats = agent.evaluate(num_episodes=100)
results[lr] = eval_stats
print(f"Learning rate {lr}: "
f"Mean reward={eval_stats['mean_reward']:.3f}, "
f"Success rate={eval_stats['success_rate']:.1%}")
return results
if __name__ == "__main__":
print("=" * 70)
print("REINFORCEMENT LEARNING GRID WORLD EXAMPLE")
print("=" * 70)
# Demonstrate training
agent, stats = demonstrate_training()
print("\n" + "=" * 70)
print("DEMONSTRATION COMPLETE")
print("=" * 70)
# Optionally demonstrate loading
# demonstrate_loading()
# Optionally compare hyperparameters
# compare_hyperparameters()
This complete implementation provides a production-ready reinforcement learning system. The GridWorld class implements a flexible environment that can be configured with different sizes, obstacles, and reward structures. The LinearQFunction class provides function approximation for Q-values using linear regression. The ReplayBuffer class stores and samples experiences for training. The QLearningAgent class implements the Q-learning algorithm with experience replay, epsilon-greedy exploration, and comprehensive training and evaluation methods.
The code follows clean architecture principles with clear separation of concerns. Each class has a single responsibility. The environment is independent of the learning algorithm. The Q-function can be easily replaced with a different approximator. The agent can work with different environments that follow the same interface.
The implementation includes proper error handling, type hints for clarity, comprehensive documentation, and methods for saving and loading trained agents. The statistics tracking allows monitoring of training progress and evaluation of performance. The code is modular and extensible, making it easy to add new features or modify existing ones.
The demonstration functions show how to use the system for training, evaluation, and comparison of different hyperparameters. The code can handle various grid world configurations from simple to complex, and the learned policies successfully navigate to the goal while avoiding obstacles.
CONCLUSION
Reinforcement learning is a powerful paradigm for training agents to make sequential decisions through interaction with an environment. We have covered the fundamental concepts including states, actions, rewards, policies, and value functions. We explored the mathematical foundations based on Markov Decision Processes and the Bellman equations.
We examined major categories of algorithms. Dynamic programming methods work with complete models. Monte Carlo methods learn from complete episodes. Temporal difference methods combine aspects of both, learning from incomplete episodes without a model. Function approximation extends these methods to large state spaces. Deep reinforcement learning uses neural networks for complex problems. Model-based methods learn environment models for planning. Multi-agent, hierarchical, and other advanced techniques address specialized challenges.
The choice of algorithm depends on your problem characteristics. Consider whether you have a model, whether the task is episodic or continuing, the size of the state and action spaces, the reward structure, sample efficiency requirements, and safety constraints.
Practical implementation requires careful attention to hyperparameters, reward design, state representation, exploration, and debugging. The complete example demonstrates these principles in a working system.
Reinforcement learning continues to advance rapidly with new algorithms, applications, and theoretical insights. The foundations covered here provide a solid basis for understanding current methods and future developments. With this knowledge, you can implement reinforcement learning solutions for your own problems, adapting the techniques and code examples to your specific needs.
No comments:
Post a Comment