During sensory-guided behavior, an animal's decision-making dynamics unfold through sequences of distinct performance states, even while stimulus-reward contingencies remain static. Little is known about the factors that underlie these changes in task performance. We hypothesize that these decision-making dynamics can be predicted by externally observable measures, such as uninstructed movements and changes in arousal. Here, combining behavioral experiments in mice with computational modeling, we uncovered lawful relationships between transitions in strategic task performance states and an animal's arousal and uninstructed movements. Using hidden Markov models applied to behavioral choices during sensory discrimination tasks, we found that animals fluctuate between minutes-long optimal, sub-optimal and disengaged performance states. Optimal state epochs were predicted by intermediate levels, and reduced variability, of pupil diameter, along with reduced variability in face movements and locomotion. Our results demonstrate that externally observable uninstructed behaviors can predict optimal performance states, and suggest mice regulate their arousal during optimal performance.