We must constantly adapt the rules we use to guide our attention. To understand how the brain learns these rules, we designed a novel task that required monkeys to learn which color is the most rewarded at a given time (the current rule). However, just as in real life, the monkey was never explicitly told the rule. Instead, they had to learn it through trial and error by choosing a color, receiving feedback (amount of reward), and then updating their internal rule. After the monkeys reached a behavioral criterion, the rule changed. This change was not cued but could be inferred based on reward feedback. Behavioral modeling found monkeys used rewards to learn the rules. After the rule changed, animals adopted one of two strategies. If the change was small, reflected in a small reward prediction error, the animals continuously updated their rule. However, for large changes, monkeys ‘reset’ their belief about the rule and re-learned the rule from scratch. To understand the neural correlates of learning new rules, we recorded neurons simultaneously from the prefrontal and parietal cortex. We found that the strength of the rule representation increased with the certainty about the current rule, and that the certainty about the rule was represented both implicitly and explicitly in the population.