Q-learning

Q-learning is a model-free reinforcement learning algorithm that learns the optimal action-value function $Q^{\ast }(s,a)$ directly from experience, by repeatedly nudging each estimate toward the observed reward plus the discounted value of the best action in the next state. Once $Q^{\ast }$ is known, the optimal policy is to pick the action with the highest Q-value.

The update rule

After taking action $A_t$ in state $S_t$ and observing $R_{t+1}$ and $S_{t+1}$:

$\alpha$ is the step size and $\gamma$ the discount factor. The target is a sampled version of the Bellman optimality equation. Because it uses ${\max }_{a^{\prime }}$ rather than the action the agent actually takes next, Q-learning is off-policy: it learns about the greedy policy while behaving with an exploratory one, usually epsilon-greedy.

Worked example

Suppose $Q(s,a)=2$, the agent receives reward 1, and the next state's Q-values are 3 and 5. With $\gamma =0.9$ the target is $1+0.9\times 5=5.5$. With $\alpha =0.5$, the new estimate is $2+0.5\times (5.5-2)=3.75$.

Convergence

Watkins and Dayan proved that tabular Q-learning converges to $Q^{\ast }$ with probability 1, provided every state-action pair is visited infinitely often and step sizes decay suitably (${\sum }_t{\alpha }_t=\infty$, ${\sum }_t{\alpha }_t^2<\infty$). No such guarantee holds once a neural network replaces the table.

Deep Q-networks

A deep Q-network (DQN) approximates $Q$ with a neural network and adds two stabilisers: an experience replay buffer that breaks correlations between consecutive samples, and a periodically updated target network used to compute ${\max }_{a^{\prime }}Q$. With these, a single architecture learned to play dozens of Atari games from pixels. Taking a max over noisy estimates biases Q-values upward, so double DQN selects the next action with the online network and evaluates it with the target network.

Why it matters

Q-learning is the canonical value-based control method and the clearest example of TD learning for control. Its off-policy nature lets it learn from replayed and logged data, which is why it underlies many offline RL methods. Its limits are equally instructive: it needs a max over actions, so it is awkward in continuous action spaces, and its overestimation bias is most severe on actions the data rarely covers.

Related terms

• Q-function
• Temporal-difference learning
• On-policy vs off-policy
• Epsilon-greedy
• Offline reinforcement learning
• Bellman equation

Sources

1. Christopher J. C. H. Watkins, Peter Dayan. Q-learning, 1992. doi.org
2. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, et al.. Human-level control through deep reinforcement learning, 2015. doi.org
3. Hado van Hasselt, Arthur Guez, David Silver. Deep Reinforcement Learning with Double Q-learning, 2015. arxiv.org