Q-Learning Update

Q: What does the learning rate $\alpha$ do?

It sets how big a step each update takes. With $\alpha = 0$, nothing is learned. With $\alpha = 1$, the old estimate is replaced by the target completely.

Q: Who first described Q-learning?

Chris Watkins introduced it in 1989, in his thesis Learning from Delayed Rewards.

In one sentence: Q-learning lets an agent improve its guess about how good an action is, a little at a time, using the reward it got on its latest step.

$Q(s,a) \leftarrow Q(s,a) + \alpha\left[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\right]$

Read it out loud: “Q of s, a becomes Q of s, a plus alpha times a bracket. Inside the bracket: the reward r, plus gamma times the largest Q of s prime and a prime, minus Q of s, a. The arrow means is replaced by. Q is the agent's guess of how good an action is. The letter s is the state, the situation, and a is the action. The letter r is the reward, s prime is the next state, and the small prime mark means next. Alpha, said AL-fuh, is the learning rate, and gamma, said GAM-uh, is the discount factor.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Agent, state, action and reward: An agent is a program that learns by trying actions and watching what happens. Its state, written $s$ , is the situation it is in now, such as one square of a game board. An action, written $a$ , is a choice it can make, such as moving right. After each action it receives a reward, written $r$ : a number of points that says how good the result was.
The Q table and the value estimate: The agent keeps a table with one number for every pair of a state and an action. The number $Q(s,a)$ is its estimate of the total reward it can expect from taking action $a$ in state $s$ and playing well afterward. The table starts with guesses, often all zeros, and learning means improving those numbers.
The Greek letters alpha and gamma: The Greek letter $\alpha$ , called alpha and said AL-fuh, is the learning rate. It is a number between 0 and 1 that sets how big a step each update takes. The Greek letter $\gamma$ , called gamma and said GAM-uh, is the discount factor, also between 0 and 1. It sets how much future reward counts compared with reward now.
The arrow and the brackets: The arrow $\leftarrow$ means replace the value on the left with the value on the right. So $x \leftarrow x + 1$ means add 1 to $x$ and store the result in $x$ . Square brackets, $[\,]$ , group a calculation. Inside the brackets is the gap between a target and the old estimate, and the whole bracket is multiplied by $\alpha$ before it is added.
The maximum and the prime mark: The maximum, written $\max$ , is the largest value in a list. In $\max_{a'} Q(s',a')$ , the small label $a'$ says to look over every action $a'$ , and the answer is the biggest $Q$ among them. A prime mark, such as $s'$ or $a'$ , means the next one. So $s'$ is the next state, the place the agent ends up after its action.

What each symbol means

Symbol	Meaning
$Q(s,a)$	The agent’s current estimate of how good it is to take action $a$ in state $s$ . It is the total future reward the agent expects, measured in reward points, with no unit.
$s$	The state, the situation the agent is in right now, such as one square of a maze. It is a label for a situation, so it has no unit.
$a$	The action taken in state $s$ , such as moving right. It is a choice from a list of possible moves, so it has no unit.
$r$	The reward received right after taking action $a$ , measured in reward points. It can be zero, positive or negative.
$s'$	The next state, where the agent ends up after taking the action. The prime mark means next. It is a label, so it has no unit.
$\max_{a'} Q(s',a')$	The best value available from the next state: the largest $Q$ among all the actions $a'$ the agent could take from there. It is measured in reward points, with no unit.
$a'$	One of the possible actions in the next state $s'$ . The prime mark marks it as an action taken from the next state, and the maximum looks over all of them.
$\alpha$	The learning rate, a number between 0 and 1 with no unit. It sets how big a step each update takes. A value of 0 changes nothing, and a value of 1 replaces the old estimate completely.
$\gamma$	The discount factor, a number between 0 and 1 with no unit. It sets how much a future reward counts compared with a reward now. A value of 0 counts only the next reward.
$\leftarrow$	The replace arrow. The value on the left is set to the result on the right. It is not an equals sign, because the two sides are not equal before the update happens.

The formula piece by piece

$r$: The reward received for taking action $a$ in state $s$ , in points. It comes from the world the agent acts in, and it is the only new real information in this update.
$\max_{a'} Q(s',a')$: The best value the agent expects from the next state. It looks at every action available there and takes the largest estimate. This assumes the agent plays well from then on.
$\gamma \max_{a'} Q(s',a')$: The discounted future. Multiplying the best next value by $\gamma$ shrinks it, so the future counts for less than the reward now. A discount of 0.9 counts each future point as 90 percent of a point.
$r + \gamma \max_{a'} Q(s',a')$: The target. It adds the reward we got to the discounted best future value. This is the agent’s new, better guess of how good the action was, based on one real step.
$r + \gamma \max_{a'} Q(s',a') - Q(s,a)$: The TD error, the gap between the target and the old estimate. A positive gap means the old guess was too low, and a negative gap means it was too high.
$\alpha\left[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\right]$: The step. The gap is multiplied by the learning rate, so the update moves the old estimate only a fraction of the way toward the target.
$Q(s,a) \leftarrow Q(s,a) + \alpha\left[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\right]$: The new estimate equals the old estimate, plus the learning rate times the gap between the target and the old estimate.
$Q(s,a) \leftarrow (1 - \alpha)\, Q(s,a) + \alpha\left(r + \gamma \max_{a'} Q(s',a')\right)$: The same update written as a weighted mix. The old estimate keeps the share $1 - \alpha$ , and the new target gets the share $\alpha$ . Both forms give the same number.

What the formula is doing, and why

The agent keeps a table of $Q(s,a)$ numbers, one for each pair of state and action. At the start the numbers are guesses. Each time the agent acts, it gets a reward and lands in a new state, and it uses that one step to improve the number for the action it took. Over many visits, the table comes closer to the true value of each action.

Why a target with the best next value? After one step we know two things. One is the reward $r$ we got, which is real. The other is the best the agent can expect from the next state, which is the $\max$ term. Adding them gives a target that uses one real reward, so it carries more real information than the old guess. The $\max$ assumes the agent will act well from then on, which is why the update describes the best play.

Why move only part of the way? The gap between the target and the guess is the TD error, short for temporal difference error. One step of experience is noisy, so moving all the way to the target can make the estimate jump around. The learning rate $\alpha$ moves the estimate only a fraction of the way. A small $\alpha$ changes things slowly and smooths out noise, while a large $\alpha$ reacts quickly but can jump around.

Why discount with $\gamma$ ? Gamma decides how far ahead the agent looks. With $\gamma = 0$ , only the immediate reward counts. As $\gamma$ nears 1, rewards far in the future count almost as much as rewards now. A discount below 1 also keeps the total finite when rewards are bounded, even if the task never ends.

When it applies. A table works when there are few enough states and actions to store one number for each pair, such as a small grid. Big problems use a neural network instead, which keeps the same kind of target. The update uses the best action in the next state even if the agent takes a different action there, which is why Q-learning is called off-policy.

An everyday picture

Think of rating a move in a board game. You know what the move gained right away, and you know the best you can expect from the position it leads to. Each time you play, you move your old rating a bit toward the sum of those two. Over many games the ratings settle near the true value of each move.

Worked example: One update in a grid world

The agent stands in state $s$ and takes action $a$ . Its current estimate is $Q(s,a) = 2.0$ points. The action gives reward $r = 1.0$ point and leads to state $s'$ , where the best action has value $\max_{a'} Q(s',a') = 4.0$ points. Use the learning rate $\alpha = 0.5$ and the discount factor $\gamma = 0.9$ .

Start with the old estimate. The agent currently thinks this action in this square is worth 2.0 points. We will adjust that guess using the one step it has taken.
Discount the best value that follows. Multiply the best next value by the discount factor: $0.9 \times 4.0 = 3.6$ . Multiplying by 0.9 counts each future point as 90 percent of a point now, so the future is worth a little less than its face value.
Form the target. Add the reward we got: $r + \gamma \max_{a'} Q(s',a') = 1.0 + 3.6 = 4.6$ . The target is the agent’s new best guess of this action’s value, using the real reward and the discounted future.
Find the gap. The TD error is the target minus the old estimate: $4.6 - 2.0 = 2.6$ . The gap is positive, which means the old estimate was too low.
Take a step of the learning rate. Multiply the gap by $\alpha = 0.5$ : $0.5 \times 2.6 = 1.3$ . With $\alpha = 0.5$ the agent moves halfway toward the target, so it does not trust one step completely.
Add the step to the old estimate. The new estimate is $2.0 + 1.3 = 3.3$ points. Written as the update rule, $Q(s,a) \leftarrow 2.0 + 0.5 \times 2.6 = 3.3$ .
Check the halfway idea. The point halfway between 2.0 and 4.6 is $\frac{2.0 + 4.6}{2} = 3.3$ . The two ways of looking at the update give the same new estimate.

Answer: The new estimate is $Q(s,a) = 3.3$ . It moved halfway from 2.0 toward the target of 4.6, because $\alpha = 0.5$ . The next time the agent visits this pair, the estimate will move a little closer to the target again.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Using the action the agent actually takes next instead of the best one. That is a different method, called SARSA, and it gives different values.
Setting $\gamma = 1$ for a task that never ends. Future rewards then add up without limit, and the estimates can grow forever.
Adding the reward to the value of the wrong pair. The reward belongs to the step from $s$ to $s'$ , so it goes into the update for $Q(s,a)$ .
Expecting one update to settle the value. Each update is a small nudge controlled by $\alpha$ , and the values improve over many visits.

Where you will meet it

Teaching agents to move through grids and mazes, a standard example in reinforcement learning courses and textbooks.
Deep Q-networks, which keep the same kind of target but learn the Q values with a neural network instead of a table.
Robot control and scheduling problems, where an agent learns which action pays off most over a long run.
Game-playing agents in research, which estimate the value of each move from the reward and the best next move.

Questions people ask

What does the learning rate $\alpha$ do?

It sets how big a step each update takes. With $\alpha = 0$ , nothing is learned. With $\alpha = 1$ , the old estimate is replaced by the target completely.

Why use the max over the next actions?

The estimate should describe the best play from here on. Using the largest next value gives that, so the table can learn the best policy even while the agent sometimes explores at random. A policy is the agent’s rule for choosing actions.

What happens when an episode ends?

An episode is one run from a start to an end, such as one game. When it ends, there is no next state to value, so the future term is set to zero. The update then uses the reward alone: $Q(s,a) \leftarrow Q(s,a) + \alpha\,[r - Q(s,a)]$ .

Who first described Q-learning?

Chris Watkins introduced it in 1989, in his thesis Learning from Delayed Rewards.

Discounted Return: The discounted return is the total reward an agent can expect from now on, where rewards that arrive later count for a little less.
Softmax Temperature: Temperature is a dial that makes a model’s choices more focused when it is low and more varied when it is high.
Gradient Descent: Gradient descent nudges a model’s settings a small step in the direction that makes the error smaller, then repeats that step again and again until the error stops falling.