Q-learning

Q-learning is a model-free reinforcement learning algorithm that learns the long-term value of taking particular actions in particular states. It seeks an optimal decision rule without requiring an explicit model of the environment’s transition probabilities or rewards. Introduced by Christopher Watkins in 1989, it received a detailed convergence proof from Watkins and Peter Dayan in 1992. The method connects experience-based learning with dynamic programming: observed transitions incrementally improve estimates of optimal action values. (gatsby.ucl.ac.uk)

Mathematical setting

The standard setting is a Markov decision process (MDP). At time $t$, an agent observes state $S_t$, chooses action $A_t$, receives reward $R_{t+1}$, and reaches state $S_{t+1}$. The Markov property means that the distribution of the next state and reward depends on the current state and action, rather than the complete interaction history. (arxiv.org)

An action-value value function, $Q^\pi(s,a)$, represents the expected value of discounted cumulative reward after taking action $a$ in state $s$ and subsequently following policy $\pi$. Q-learning estimates the optimal function $Q^*$. Once this function is known, selecting an action that maximizes $Q^*(s,a)$ gives an optimal policy. (gatsby.ucl.ac.uk)

For discount factor $0\leq\gamma<1$, the optimal action values satisfy the Bellman optimality equation:

The corresponding Bellman operator is a contraction mapping, which establishes a unique fixed point in the finite discounted setting. (arxiv.org)

Update rule

For each observed transition $(s,a,r,s')$, one-step Q-learning updates the selected entry:

Here, $\alpha$ is the learning rate. The quantity in brackets is a temporal-difference error: the difference between the current estimate and a target combining immediate reward with estimated future value. This is bootstrapping, because an existing prediction supplies part of the learning target. If the transition ends the task at a terminal state, the future-value term is zero. (incompleteideas.net)

In the tabular version, each state–action pair has a separate stored value. An implementation initializes this table, repeatedly selects actions, observes outcomes, and applies the update. Unlike model-based value iteration, it uses sampled outcomes rather than explicitly averaging over all possible successors using known transition probabilities. (gatsby.ucl.ac.uk)

As an illustrative calculation, suppose the current estimate is $2$, the reward is $1$, the largest next-state estimate is $4$, $\gamma=0.9$, and $\alpha=0.5$. The target is $4.6$, so the updated value becomes $3.3$. This single update moves the estimate toward the observed target; it does not establish the action’s true value.

Off-policy learning and exploration

Q-learning is off-policy: the policy generating experience need not be the greedy policy represented by the update target. An agent can take exploratory actions while learning values associated with optimal subsequent choices. Nevertheless, useful learning requires adequate coverage of state–action pairs. (incompleteideas.net)

A common behavior rule is epsilon-greedy action selection. With probability $\epsilon$, the agent selects a random action; otherwise it selects an action with the highest estimated value. This addresses the exploration–exploitation trade-off between obtaining information and using current knowledge. (incompleteideas.net)

The related algorithm SARSA instead uses the value of the next action actually selected, giving target $r+\gamma Q(s',a')$. Consequently, SARSA learns about its behavior policy, including its exploratory actions, whereas Q-learning’s maximum defines a greedy target independently of the next action taken. (incompleteideas.net)

Convergence and its scope

In a finite, stationary MDP with bounded rewards and discount factor below one, tabular Q-learning converges to $Q^*$ with probability one under appropriate sampling and step-size conditions. Every state–action pair must be visited infinitely often. For each pair, its successive learning rates $\alpha_n(s,a)$ must satisfy

These stochastic approximation conditions preserve enough cumulative adjustment while reducing the influence of sampling noise. (arxiv.org)

The theorem is asymptotic: it does not specify that a finite training run will produce an optimal policy. Its tabular assumptions also do not automatically extend to arbitrary function approximation. Shared parameters can make an update affect many state–action estimates, changing the learning dynamics. (gatsby.ucl.ac.uk)

Deep Q-learning and variants

For large observation spaces, a deep Q-network (DQN) represents action values with an artificial neural network rather than a table. Mnih and colleagues demonstrated learning from Atari game images using a convolutional neural network and experience replay, which stores transitions and samples them for subsequent updates. (arxiv.org)

The 2015 DQN system also used a separate, periodically updated target network to stabilize learning targets. Evaluated across 49 Atari games, it demonstrated how deep learning could extend value-based reinforcement learning to high-dimensional visual inputs. These empirical results did not establish the tabular convergence guarantee for neural networks. (nature.com)

Ordinary Q-learning can overestimate values because the maximum preferentially selects estimates with positive errors. Double Q-learning, introduced by Hado van Hasselt in 2010, separates action selection and evaluation between two estimators to reduce this effect. Its estimates can also underestimate values; it does not eliminate every source of error. Double DQN subsequently adapted this principle to neural-network action-value learning. (papers.neurips.cc)