We trained five rats to perform a complex auditory-guided task in a large environment (diameter 160 cm) with twelve nose-poke ports. To obtain rewards, rats had to position themselves at specific locations indicated by sounds. Despite the nontrivial task, rats reached high success rates within two 70-minute sessions. We modeled the task as a Markov Decision Process. Observed rat trajectories resembled the model's optimal policies. However, while optimal policies were deterministic, observed behavior was non-deterministic. We introduced non-deterministic, information-limited policies that realize optimal reward rates under constraints on the Kullback-Leibler divergence from a default, non-informative policy (Tishby’s complexity, TC). We estimated the TC of rat movement and nose-poking over more than 10 months by comparing observed behavior with TC-limited policies. Our model revealed a prolonged, large increase in the TC over time. Significantly, this prolonged behavioral refinement was not discernible via reward rates, and to our knowledge has not been described previously. The model also captured individual propensities for preferring some foraging strategies over others. Specifically, one strategy required sharp-angled body-turns. By transiently altering the task structure, we successfully encouraged rats to increase their preference for that strategy. Concurrently, our model uncovered a permanent decrease in body-turn cost in every rat, with new costs that differed between rats but were constant over time within rat. Recording with chronically implanted silicon probes from the left insular cortex, we found that in many neurons, firing rates (averaged over ten minutes) strongly correlated with TC, computed in the same time periods. Significantly, our model is based on first principles of information theory, and does not employ ad-hoc measures of behavior. Thus, we present here novel insights into rat behavioral refinement over very long time scales, and introduce TC as a regressor for cortical activity.