Q-Learning Deep Q-Networks Value-Based Reinforcement Learning
# Q-Learning & Deep Q-Networks: Value-Based Reinforcement Learning
## Introduction & Motivation
Q-learning: learn action-value function; off-policy. Deep Q-networks: function approximation via neural nets. Experience replay: break correlation; stabilize training. Target network: separate network; reduce instability. Applications: Atari, game playing, discrete control.
Motivation: Temporal difference: bootstrap via next state estimate. DQN: scale to high-dimensional states.
Applications: Discrete action spaces, game AI, sequential decision making.
---
## Core Concepts & Theory
### Q-Function
Q(s,a) = expected return from state-action pair.
### Temporal Difference (TD)
Bootstrap: Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)].
### Experience Replay
Store transitions; sample minibatches; break temporal correlation.
---
## Mathematical Formulation
Q-Learning update:
$$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$$
DQN loss:
$$L = \mathbb{E}[(r + \gamma \max_{a'} Q_{ ext{target}}(s',a'; heta^-) - Q(s,a; heta))^2]$$
Bellman equation:
$$Q(s,a) = \mathbb{E}[r + \gamma \max_{a'} Q(s',a')]$$
---
## Advanced Theory & Extensions
### Double DQN
Separate action selection and evaluation; reduce overestimation.
### Dueling DQN
Separate value and advantage; V(s) + A(s,a).
### Prioritized Experience Replay
Weight samples by TD error; focus on important transitions.
---
## Computational Considerations
Forward pass: O(state_size → action_size) per transition.
Experience replay: O(buffer_size) memory.
Target network: 2× network storage.
---
## Practical Implementation Strategies
### Epsilon-Greedy Exploration
Explore with probability ε; typically ε=0.1.
### Learning Rate
1e-4 common; decay useful.
### Replay Buffer
1M transitions typical; circular buffer.
---
## Benchmark Datasets & Evaluation
Atari: 57 games; median score metric.
CartPole: Simple; quick convergence.
MuJoCo: Continuous; Q-learning struggles.
---
## Key Challenges & Limitations
### Overestimation
Max operation overestimates; Double DQN fixes.
### Instability
Correlations in replay; target network helps.
### Discrete Actions Only
Can't handle continuous; need policy gradient.
---
## Hyperparameter Tuning
Learning rate: 1e-4 standard; decay over time.
γ (discount): 0.99 typical; 0.95 for short-term.
Batch size: 32 typical; 64-128 if memory allows.
---
## Real-World Applications & Case Studies
Atari: DQN achieves human-level performance.
Game AI: Chess, Go variants; discrete action space.
Robotics: Limited; continuous control better.
---
## Integration with Other Methods
DQN + Policy Gradient → hybrid algorithms.
DQN + Prioritized Replay → stable value learning.
---
## Summary & Key Takeaways
Deep Q-Networks via temporal difference learning and experience replay enable value-based reinforcement learning in high-dimensional state spaces through neural network function approximation.
Principles:
1. Q-function: state-action value estimate.
2. TD learning: bootstrap from next state.
3. Experience replay: decorrelate training samples.
4. Target network: stabilize training.
5. Epsilon-greedy: exploration-exploitation balance.
---
---
## Appendix: Practical Labs
### Lab 1: Q-Learning Update
import numpy as np
def q_learning_update(Q, state, action, reward, next_state, alpha=0.1, gamma=0.99):
"""Single Q-learning update"""
max_next_q = Q[next_state].max() if next_state is not None else 0
target = reward + gamma * max_next_q
td_error = target - Q[state, action]
Q[state, action] += alpha * td_error
return td_error
# Test
np.random.seed(42)
n_states, n_actions = 5, 3
Q = np.random.randn(n_states, n_actions)
td_error = q_learning_update(Q, state=0, action=1, reward=1.0, next_state=2)
assert np.isfinite(td_error), "TD error finite"
print("✓ Q-learning update working")
if __name__ == "__main__":
print("Lab 1: QLearning - PASSED")### Lab 2: Experience Replay
import numpy as np
from collections import deque
class ReplayBuffer:
def __init__(self, capacity=1000):
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):
indices = np.random.choice(len(self.buffer), batch_size, replace=False)
batch = [self.buffer[i] for i in indices]
states = np.array([b[0] for b in batch])
actions = np.array([b[1] for b in batch])
rewards = np.array([b[2] for b in batch])
next_states = np.array([b[3] for b in batch])
dones = np.array([b[4] for b in batch])
return states, actions, rewards, next_states, dones
# Test
buffer = ReplayBuffer(capacity=100)
for _ in range(50):
buffer.push(0, 1, 1.0, 2, False)
states, actions, rewards, ns, dones = buffer.sample(10)
assert len(states) == 10, "Batch size correct"
print("✓ Experience replay working")
if __name__ == "__main__":
print("Lab 2: Replay - PASSED")### Lab 3: DQN Network
import torch
import torch.nn as nn
import numpy as np
class DQN(nn.Module):
def __init__(self, state_dim, action_dim, hidden_dim=128):
super().__init__()
self.net = nn.Sequential(
nn.Linear(state_dim, hidden_dim),
nn.ReLU(),
nn.Linear(hidden_dim, hidden_dim),
nn.ReLU(),
nn.Linear(hidden_dim, action_dim)
)
def forward(self, state):
return self.net(state)
# Test
np.random.seed(42)
model = DQN(state_dim=10, action_dim=4)
state = torch.randn(32, 10)
q_values = model(state)
assert q_values.shape == (32, 4), "Q-values shape correct"
print("✓ DQN network working")
if __name__ == "__main__":
print("Lab 3: Network - PASSED")### Lab 4: TD Error
import torch
import numpy as np
def compute_td_error(Q, states, actions, rewards, next_states, dones, gamma=0.99):
"""Compute TD error for batch"""
q_values = Q(states).gather(1, actions.unsqueeze(1)).squeeze(1)
with torch.no_grad():
max_next_q = Q(next_states).max(dim=1)[0]
max_next_q[dones] = 0
targets = rewards + gamma * max_next_q
td_error = targets - q_values
return td_error
# Test
np.random.seed(42)
model = nn.Linear(10, 4)
states = torch.randn(8, 10)
actions = torch.randint(0, 4, (8,))
rewards = torch.rand(8)
next_states = torch.randn(8, 10)
dones = torch.zeros(8, dtype=torch.bool)
td_error = compute_td_error(model, states, actions, rewards, next_states, dones)
assert td_error.shape == (8,), "TD error shape correct"
print("✓ TD error working")
if __name__ == "__main__":
print("Lab 4: TDError - PASSED")