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.
When you learn your way around an unfamiliar city, you try routes, notice which ones work, and backtrack from dead ends. After enough trips you know the good routes, though nobody told you them. Reinforcement learning works the same way. An agent acts in an environment and receives rewards or penalties. It has no labeled examples, only the consequences of what it did. The models in Parts 1 to 3 learned from examples paired with targets; 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 that deal heavy penalties, and every other step costs a small amount. 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.
Here you can see the whole map, so finding a short route that avoids the pits is easy. With a grid a thousand cells wide, hidden rewards or moves that sometimes slip sideways, you would want an algorithm to learn the route 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, picks actions, collects rewards and updates its Q-values. After taking action a in state s, receiving reward r, and landing in state s', it nudges the Q-value toward the new estimate by the size of the TD error:
The learning rate α controls how fast the agent nudges its belief toward the new estimate; the discount factor γ controls how much future rewards count. Episode after episode, actions that lead toward the goal develop high values and actions that lead into pits develop low ones.
The green triangles spread backward from the goal, one episode at a time: the agent learns the value of a distant cell only after it has learned the value of the cells between it and the goal. Even after long training the green reaches only about seven steps out. Farther away, even the best action is worth less than zero, because the -1 costs along the way outweigh the discounted +10 at the end.
At every step the agent chooses between the action it currently believes is best (exploiting) and something else that might reveal a better path (exploring). Too much exploitation can lock it onto the first decent route so it never finds a shorter one; too much exploration leaves it wandering without using what it has learned. On this grid the first danger is mild. Q-values start at zero and every step costs -1, so an action the agent has already tried looks worse than one it has not, and even a nearly greedy agent keeps trying new moves until it finds the short route.
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.
Run both agents for a few hundred episodes. On this grid, both greedy paths settle at 12 steps, the shortest route to the goal, yet the agent with the larger ε keeps collecting less reward per episode. That is because the Q-learning update uses maxa' Q(s', a'), the value of the best next action, whatever action the agent actually takes next. The Q-values estimate what the greedy policy would earn, and the random moves only decide which states and actions get updated. Learning about one policy (the greedy one) while following another (the exploratory one) is what makes Q-learning an off-policy method. The cost of exploring shows up in the reward collected while learning: with ε = 0.5, half the moves are random, and some of them walk into a pit.
An agent that must also act well while it learns can use an update that follows its own exploratory behavior instead. SARSA replaces the max with the Q-value of the action the agent really takes next, so it learns the value of the exploratory policy it follows: it is on-policy. On grids where the shortest route runs along a row of pits, SARSA learns a longer route that keeps its distance from them, while Q-learning learns the edge-hugging shortest 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. That mapping from state to action is the policy, and Figure 4 shows it two ways. The arrow field shows the best action in each cell, with opacity for confidence: a bold arrow means one action is clearly better, a faint one that the agent is nearly indifferent. The value heatmap shows how good each cell is (its maximum Q-value); bright cells are close to the goal, dark cells far from it or rarely visited.
Value radiates outward from the goal and fades with distance. The pits barely show in the heatmap: a cell's value is its best action, and the best action from a cell beside a pit is a step away from it, so with enough training that cell is worth as much as any other cell at the same distance from the goal. A dark cell beside a pit is one the agent rarely visited, like the far corners. The pits show up in the arrows, which never point into them. Following the arrows amounts to walking uphill on the value heatmap.
The Q-table here has 49 × 4 = 196 entries, and each is updated only when the agent visits that cell and takes that action. Most interesting problems have far too many states to visit each one. 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 changes the estimates for similar states. That generalization is also what makes it less stable: the target moves whenever the network changes, so DQN used a replay buffer of past transitions and computed the targets with a separate copy of the network, held fixed between refreshes and copied from the main network only once every fixed number of updates.