During operant conditioning, animals learn to respond to stimuli with actions that lead to favorable outcomes. Recordings in mammals have uncovered neural signals that link stimulus, action, and outcome, but a limited number of recording sites have hindered the comprehensive discovery of learning signals. Here, we use brain-wide functional imaging in larval zebrafish to screen more than 100,000 neurons while animals learn to terminate a heat stimulus with a directional tail movement. We identify neurons comprising two major classes: class 1 consists of action-selective neurons that encode the direction of heat-evoked tail movements seconds before and after their execution. Class 2 consists of neurons that encode outcome prediction and prediction error. This class includes both positive relief prediction signals that are enhanced by learning, and negative relief prediction signals that are suppressed by learning. These positive and negative relief prediction signals not only have opposing patterns of activity but are also found on opposing sides of the habenula. Strikingly, both outcome-predictive and action-selective signals are correlated with natural variability in learning performance across animals. This study provides the first comprehensive survey of the neural dynamics during learning, suggests that lateralized neuronal activity contributes to operant conditioning, and raises novel hypotheses about the roles of action-selective and outcome-prediction neurons.