The present study investigated attentional optimization in participants learning rule-based (RB) and information integration (II) categories. Using an eye-tracker to measure the deployment of overt attention, we tracked participants learning and optimization during a category learning experiment. We also measured working memory span. We found that participants in the RB condition optimized attention less than II participants before reaching the learning criterion, but more than II participants after criterion, and confirmed that this effect was not due to differences in speed of learning or accuracy. Working memory span was negatively related to pre-criterion optimization in both conditions, but was unrelated to post-criterion optimization. These results show that attentional optimization is influenced by the kind of task being learned or the types of strategies that these tasks elicit, and provide evidence that executive attentional factors influence overt attentional optimization.