Anchoring goals to spatial representations enables flexible navigation in both animals and artificial agents. However, using this strategy can be challenging in novel environments, when both spatial and goal representations must be acquired quickly and simultaneously. Here, we propose a framework for how Drosophila use their internal representation of head direction to build a goal heading representation upon selective thermal reinforcement. We show that flies in a well-established operant visual learning paradigm use stochastically generated fixations and directed saccades to express heading preferences, and that compass neurons, which represent flies’ head direction, are required to modify these preferences based on reinforcement. We describe how flies’ ability to quickly map their surroundings and adapt their behavior to the rules of their environment may rest on a behavioral policy whose parameters are flexible but whose form and dependence on head direction and goal representations are genetically encoded in the modular structure of their circuits. Using a symmetric visual setting, which predictably alters the dynamics of the head direction system, enabled us to describe how interactions between the evolving representations of head direction and goal impact behavior. We show how a policy tethered to these two internal representations can facilitate rapid learning of new goal headings, drive more exploitative behavior about stronger goal headings, and ensure that separate learning processes involved in mapping the environment and forming goals within that environment remain consistent with one another. Many of the mechanisms we outline may be broadly relevant for rapidly adaptive behavior driven by internal representations.