Q-Learning

Topics: Reinforcement Learning

Introduction

Q-Learning is a model-free, off-policy, RL algorithm that trains a deterministic policy targeted at environments with discrete action spaces and discrete state spaces.

In its most basic form, the algorithm interacts with the environment in order to build a table of Q values $Q(s,a)$ for all the finite state-action pairs. Then, for every state, the policy consists of selecting the action having the highest Q value. The picture below shows the table of Q-values: its inputs are the state and action and the output is the Q-value for the input state-action pair (1).

Q-Learning Update

The Q-Learning update equation based on Bellman is as follows (2):
$Q_{new}(s,a) = Q(s,a) + \alpha \left( R(s,a) + \gamma \cdot \underset{a'}{max} \, Q(s',a') - Q(s,a) \right)$

Exploration vs. Exploitation

Q-Learning uses an epsilon greedy strategy to balance exploration and exploitation. It selects a random action with small probability $\epsilon$ and selects a greedy action with probability $(1-\epsilon)$:
$a(s)=\underset{a}{arg\, max} \; Q(s,a)$

Pseudocode

The pseudocode of the Q-Learning algorithm is as follows (2).

Drawbacks

The main drawback of Q-Learning is that it can only handle environments with small state spaces and action spaces. The size of the Q table would grow rapidly as the number of states and actions increase, making it challenging to train.
Another drawback is that it is limited to discrete states, so it cannot handle continuous input data like images for instance.
All of the above limits its ability to handle complex tasks.

Deep Q-Learning was introduced to address these limitations.

References

1. https://www.geeksforgeeks.org/deep-learning/deep-q-learning/
2. https://www.baeldung.com/cs/q-learning-vs-deep-q-learning-vs-deep-q-network