Q-learning

Learning without the table

Value iteration needs to know what every action does. In most problems nobody can write that down: the world is too large, the dynamics are hidden, or they change. Q-learning replaces the table with experience, one transition at a time. It is the same backup, with a sample standing in for the expectation. The sample is noisy, so the update is noisy, and that is the price of not having the model.

The agent stores a value for each state and action pair, written Q of s and a. It starts with a guess, acts, and uses what happened to improve the guess. No model of the environment is built, which is why the method is called model-free. Model-free does not mean memoryless: the table is the memory. Every later method keeps some version of it, even when the table becomes a network.

A guess corrected by a guess

After taking action a in state s and landing in state s-prime with reward r, the agent has a better estimate of that action’s value: the reward just received, plus the discounted value of the best action available from s-prime. That sum is the target. It is one step of lookahead, using the table as a stand-in for the future. The target is not the truth; it is the best current guess at the truth.

The update moves the old estimate a fraction of the way toward the target, with the fraction given by the learning rate alpha. The gap between target and estimate is the temporal-difference error. Q-learning is a sequence of these small corrections, applied millions of times. The error is the only teaching signal, and it is computed from two guesses. The order of updates matters in practice even when the theory says it should not.

The same idea in a deep library

from stable_baselines3 import DQN

model = DQN("MlpPolicy", "CartPole-v1", learning_rate=1e-3, buffer_size=50000)
model.learn(total_timesteps=20000)

obs, info = model.get_env().reset()
action, _ = model.predict(obs, deterministic=True)
print(action)

Two policies at once

Q-learning is off-policy. The behaviour policy decides which actions are taken, and it can be as exploratory as you like. The target policy is the greedy one implied by the Q values, and that is the policy being evaluated and improved. The two policies can disagree completely, and the algorithm still converges under the usual conditions. The behaviour policy only has to visit the pairs the target policy cares about.

The separation is powerful: you can learn the best policy while behaving randomly, or while following a safe script, or from data recorded by someone else. It is also a warning. Off-policy learning with a large function approximator, a bootstrapped target and a high learning rate is the combination known as the deadly triad, and it can diverge. Replay buffers make the divergence more likely, not less, because they break the correlation the theory assumes.

The learning rate is a decision

A fixed alpha treats old and new experience as equally important, which is what you want when the world changes. A schedule of one over the visit count averages everything, which is what you want when it does not. Neither is right in general; the choice says what you believe about stationarity. A constant step size never converges in the textbook sense, but it tracks, which is often the more useful promise. The same table can be learned with either, and the curves look different.

Gamma plays the same role it did in planning: it sets how far the bootstrapped target looks ahead. With a small gamma the agent learns quickly from local rewards and ignores distant consequences. With a large gamma it propagates value further, at the cost of slower and noisier learning. In a sparse-reward world, a large gamma is often the difference between learning and never seeing a signal. Too large a gamma with too small an alpha is a common way to learn nothing.