Deep Q-Learning

Topics: Reinforcement Learning

Introduction

Deep Q-Learning (DQN) is a model-free, off-policy, Q-Learning, RL algorithm that trains a deterministic policy targeted at environments with discrete action spaces.

It is an extension of the basic Q-Learning algorithm which learns a table of Q-values for all the finite state-action pair combinations. DQN replaces the table of Q-values with a neural network which approximates the Q-values. This allows it to overcome the limitations of Q-Learning and makes it suitable for large and continuous state spaces (1). The input of the neural network is the state and the output is the Q-value for each possible action.

The following picture shows the difference between Q-Learning and DQN (2).

The structure of a DQN agent with the environment is as follows (1):

Deep Q-Learning Concepts

Q-Function Neural Network

DQN uses a neural network with parameters $\theta$ to approximate the Q-values $Q_{\theta}(s,a)$. The input is the state and the outputs are the Q-values of all the actions. Then, the policy consists of selecting the action having the highest Q-value:
$\pi(s)=\underset{a}{arg \, max} \; Q_{\theta}(s,a)$

Replay Buffer

Since DQN is an off-policy method, it uses a replay buffer to store training samples $(s, a, r, s', d)$. During training, mini-batches of experiences are randomly sampled from the buffer to update the parameters $\theta$ of the network. This approach breaks the correlation between consecutive experiences, improves generalization (3) and sample efficiency (1).

Target Network

DQN uses a separate network with parameters $\theta_{target}$ when calculating the targets to update the neural network weights. This stabilizes the training and eliminates the idea of a moving target. Without it, the parameters $\theta$ that we are training move the target as we train.

The loss function for training the Q-values neural network is (3):
$L(\theta)=E \left[ \left( r+\gamma \cdot \underset{a'}{max} \; Q_{\theta_{target}}(s',a') - Q_{\theta}(s,a) \right) ^2 \right]$

The parameters of the target network get copied over from the main network periodically every some-fixed-number of steps.

Epsilon-Greedy Exploration

To balance exploration and exploitation during training, DQN uses an epsilon-greedy strategy. The agent selects a random action with probability $\epsilon$ (exploration), and selects the action that has the highest Q-value with a probability $(1-\epsilon)$ (exploitation) (2).

Pseudocode

The following is the pseudocode for DQN with replay buffer, target network and epsilon-greedy exploration (4).

Drawbacks

The main drawback of DQN is the problem of Q-value overestimation. Double Deep Q-Learning was introduced to address this issue.

References

1. https://medium.com/@samina.amin/deep-q-learning-dqn-71c109586bae
2. https://www.baeldung.com/cs/q-learning-vs-deep-q-learning-vs-deep-q-network
3. https://www.geeksforgeeks.org/deep-learning/deep-q-learning/
4. https://huggingface.co/learn/deep-rl-course/en/unit3/deep-q-algorithm