An agent with no labeled examples can still learn from the rewards its actions earn. Here Q-learning finds a safe path through a small grid world by trial and error.
Learning your way around an unfamiliar city, you try routes, keep the ones that work and back out of dead ends; nobody tells you the answer. Reinforcement learning works the same way. This part follows Q-learning as it learns a small grid world from rewards alone.
Consider a grid world. An agent starts in one cell, its state, and must reach a goal. Some cells are pits with heavy penalties, and every other step costs a little. In each cell the agent chooses an action (up, down, left or right) and collects a reward for the move. Try to find the shortest safe path yourself.
With the whole map in view the route is easy to see. A thousand-cell grid with hidden rewards or slippery moves calls for an algorithm that learns from experience.
Q-learning assigns a value to each (state, action) pair. The Q-value for "being in cell (3,2) and moving right" is the agent's current estimate of how good that action is from that position. All values start at zero.
In each episode the agent starts at the beginning and acts until it reaches the goal or a pit. After taking action a in state s, receiving reward r and landing in s', it moves the Q-value a step toward a new estimate, in proportion to the TD error:
The step size α sets how far each update moves; the discount factor γ, how much future rewards count.
The green spreads backward from the goal one episode at a time. Knowing the map, you could instead apply the same backup to every cell at once, with the known moves and rewards in place of samples. That is value iteration (Figure 3).
Each sweep carries value one cell farther, so the values are exact after 12 sweeps, the longest shortest route here. The general guarantee, an error shrinking by a factor γ per sweep, is loose because episodes end. Even the exact values are positive only within seven steps of the goal.
At each step the agent either takes the action it believes best (exploiting) or tries something else that might reveal a better path (exploring). Too little exploring can lock it onto the first decent route, but here that danger is mild: values start at zero and every step costs -1, so untried actions look better than tried ones.
The parameter ε (epsilon) controls this tradeoff. With probability ε the agent picks a random action; otherwise it picks its current best according to the Q-table.
Both greedy paths settle at 12 steps, yet the agent with the larger ε keeps collecting less reward. The update uses maxa' Q(s', a'), the best next action, whatever the agent actually does next, so the Q-values estimate what the greedy policy would earn; random moves only decide which values get updated. That makes Q-learning an off-policy method. Figure 5 repeats the race over 20 seeds.
With α of at least 0.1 and ε up to 0.5, every seed settles on the 12-step route within 300 episodes. How soon depends mostly on α, while reward falls steeply with ε at every α. Since moves and rewards here are deterministic, α = 1 is fastest.
SARSA replaces the max with the Q-value of the action the agent really takes next, so it learns the value of its own exploratory behavior: it is on-policy. Where the shortest route runs beside a row of pits, SARSA learns a longer, safer route, while Q-learning learns the edge route and keeps falling in during training. This is the cliff-walking example in Sutton and Barto (Example 6.6).
After learning, the Q-values give a direction for every cell: the policy. Figure 6 shows it as arrows, bold where one action is clearly better and faint where the agent is nearly indifferent, and as a heatmap of each cell's value, its maximum Q-value.
Value radiates outward from the goal. The pits barely show in the heatmap, because the best action beside a pit steps away from it, so that cell is worth as much as any other at its distance from the goal. The pits show up in the arrows instead.
The max in the update is optimistic when rewards are noisy: if several equally bad actions have scattered estimates, the largest is too high, and Q-learning treats it as fact. In Example 6.7 of Sutton and Barto, going right from state A ends the episode with reward 0, and going left leads to B, where every action ends with a reward drawn from a normal distribution with mean -0.1 and variance 1. Double Q-learning keeps two tables, picks the best action with one and scores it with the other, so one table's lucky draws cannot inflate its own target.
The Q-table here has 49 × 4 = 196 entries, each updated only when the agent takes that action in that cell. Most problems have far too many states for a table. Deep Q-networks (Mnih et al., 2015) replace the table with a neural network that maps a state, such as a game screen, to one Q-value per action, trained toward the same target r + γ max Q(s', a'). Learning in one state then shifts the estimates for similar states, so the target moves as the network changes; DQN steadied it with a replay buffer of past transitions and a separate copy of the network for the targets, refreshed only once every fixed number of updates.