Methods, systems, and apparatus, including computer programs encoded on computer storage media, for computing enhanced surprise metrics for autonomously driven vehicles. One of the methods includes receiving data representing a predicted state of an agent at a particular time, data representing an actual state of the agent for the particular time, and computing a surprise metric for the actual state of the agent based on a measure of the residual information between the predicted state of the agent and the actual state of the agent.