Q-learning

On this page 7

Q-learning is a model-free, off-policy reinforcement learning algorithm that learns an action-value function Q(s, a), the expected discounted return of taking action a in state s and acting optimally afterward. In reinforcement learning, a branch of artificial intelligence, it is the foundational method for learning an optimal policy from trial-and-error experience without a model of the environment.

Introduced by Christopher Watkins in 1989, Q-learning updates its estimates with a temporal difference rule derived from the Bellman optimality equation. Under well-defined conditions, the tabular version is proven to converge to the optimal Q-function, and its neural extension, the Deep Q-network, made the approach practical for high-dimensional inputs such as raw video frames.

How the Q-learning update rule works

Q-learning improves its estimate of Q(s, a) after every single transition by moving it toward a bootstrapped target. After the agent takes action a in state s, receives reward r and lands in state s’, the update is Q(s, a) ← Q(s, a) + α [r + γ max Q(s', a') − Q(s, a)]. The bracketed term is the temporal difference error, the gap between the current estimate and the observed one-step return plus the best estimated future value.

The key element is the max operator over next actions. Q-learning always evaluates the next state as if the agent will act greedily, regardless of which action the agent actually takes next. This is what makes it off-policy: the agent can explore with one behavior policy while learning the value of the greedy target policy.

The table below lists the parameters that govern the update and their usual ranges.

ParameterRoleTypical rangeEffect of a poor value
Learning rate αStep size toward the target0.01 to 0.5 in tabular settingsToo high oscillates, too low learns slowly
Discount factor γWeight of future rewards0.9 to 0.999Too low makes the agent short-sighted
Exploration rate εProbability of a random actionDecayed from 1.0 to about 0.01-0.1Too little exploration locks in poor actions
Initial Q-valuesStarting estimatesZero or optimistic valuesPessimistic values discourage exploration
Core Q-learning parameters

Exploration and convergence conditions

Tabular Q-learning converges to the optimal action values with probability one when two conditions hold. Every state-action pair must be visited infinitely often, and the learning rate must decay so that the sum of the step sizes diverges while the sum of their squares stays finite. The environment must also be a finite Markov decision process with bounded rewards.

In practice, exploration is usually handled with an epsilon-greedy policy, which picks a random action with probability ε and the greedy action otherwise. Alternatives include Boltzmann (softmax) exploration, upper confidence bound bonuses and optimistic initialization, which sets initial Q-values high so that untried actions look attractive until experience corrects them.

Q-learning belongs to the family of temporal difference learning methods and is most often contrasted with SARSA, its on-policy counterpart. The difference lies in the target: SARSA uses the value of the action actually taken next, while Q-learning uses the maximum over all next actions.

AlgorithmPolicy typeTarget usedCharacteristic behavior
Q-learningOff-policyReward plus max Q of next stateLearns optimal values, can be risky during training
SARSAOn-policyReward plus Q of action actually takenSafer paths under exploration
Expected SARSAOn- or off-policyExpected Q under the policyLower variance than SARSA
Deep Q-networkOff-policyMax Q from a target networkHandles large state spaces with neural networks
Double DQNOff-policyOnline network selects, target network evaluatesReduces overestimation bias
Q-learning and neighboring value-based methods

The classic cliff-walking task illustrates the contrast. Q-learning learns the shortest path along the cliff edge because it values the greedy policy, whereas SARSA learns a safer, longer route because it accounts for the random steps that epsilon-greedy exploration will take.

From tables to Deep Q-networks

Tabular Q-learning stores one value per state-action pair, which becomes infeasible once the state space is large or continuous. Function approximation replaces the table with a parameterized model, most famously a neural network in the Deep Q-network, which reached human-level scores on many Atari 2600 games from raw pixels.

Combining bootstrapping, off-policy learning and function approximation can cause divergence, a problem known as the deadly triad. Deep Q-networks stabilize training with experience replay, which samples past transitions at random to break correlations, and a target network that is updated only periodically so that the learning target does not shift with every gradient step.

AspectTabular Q-learningDeep Q-learning
State representationDiscrete indexFeature vector or raw input
Convergence guaranteeProven under standard conditionsNo general guarantee
Memory needGrows with states times actionsFixed by network size
GeneralizationNone between statesSimilar states share estimates
Action spaceDiscreteDiscrete; continuous actions need other methods
Tabular and approximate Q-learning

Limitations and common pitfalls

The most widely documented weakness of Q-learning is maximization bias. Taking the maximum over noisy estimates systematically overestimates action values, which can mislead the agent toward actions that merely look good by chance. Double Q-learning addresses this by keeping two estimators, one to select the best action and the other to evaluate it.

Other practical issues follow from the algorithm’s assumptions and are summarized below.

SymptomLikely causeRemedy
Inflated value estimatesMaximization biasDouble Q-learning or Double DQN
No learning progressSparse reward with weak explorationReward shaping or intrinsic motivation
Unstable or diverging valuesDeadly triad with function approximationTarget network and experience replay
Poor results in partially observed tasksViolated Markov assumptionAdd memory or state history
Cannot select continuous actionsMax over infinite action setUse actor-critic methods such as DDPG
Typical problems and remedies

Q-learning is also sample-inefficient in many domains, often needing millions of interactions, which makes it costly where real-world experience is slow or risky. For that reason, simulation or offline data usually precedes deployment on physical systems.

A non-technical view

Q-learning is a way for a computer program to learn good decisions by trying things and keeping score. Imagine a notebook with a row for every situation and a column for every possible move. Each cell holds a guess of how much reward that move will eventually bring.

Every time the program acts, it checks what happened and nudges the guess up or down. Early on it tries random moves to discover new options. Over time the guesses become reliable, and the program simply picks the move with the best score in each situation.

A concrete example

A logistics team trains a simulated warehouse robot to move from a loading dock to a set of shelves on a 10 by 10 grid with obstacles. Each state is the robot’s cell, there are four actions (up, down, left and right), each step costs a reward of −1, hitting an obstacle costs −10 and reaching the shelf earns +50.

The team uses tabular Q-learning with α = 0.1, γ = 0.95 and an ε that decays from 1.0 to 0.05 over 5,000 episodes. In the first hundred episodes the robot wanders, often taking more than 80 steps. After about 2,000 episodes the learned Q-table yields a policy that reaches the shelf in the minimum of 18 steps from the dock while avoiding every obstacle.

The outcome is a verified route table that the team checks against a shortest-path planner before testing on the physical robot, where the same policy then serves as a baseline for a later Deep Q-network that uses camera input.