Studies suggest that adaptive behaviors arise from multiple decision systems in the brain, and spatial complexity affects these processes. Three regions are hypothesized to make distinct contributions: hippocampus (HC) — encoding state-space and enabling flexible behaviors, dorsolateral striatum (DLS) — encoding action-chains and enabling automated behaviors, and prefrontal cortex (mPFC) — encoding task-space and strategy-setting. We simultaneously recorded across these regions, and in a separate cohort we chemogenetically inhibited mPFC on a rule-switch task, the left/right/alternation foraging task, where we parametrically varied the environment complexity. Hippocampal time-compressed sequential representations of future positions during theta increased during deliberation and were longer and more prominent in complex environments. In contrast, task-bracketing by DLS ensembles were most prominent in simple environments. Furthermore, task-bracketing was inversely correlated with HC sequence coherence/length in simple environments. In complex environments, DLS ensembles represented multiple action-boundaries aligned to intermediate, distributed decision-points (subgoals). mPFC representations encoded strategy and could be used to predict the length of hippocampal theta sequences. However, the coupling between mPFC and HC state was over longer behaviorally-relevant time scales, implying a role for mPFC in longer-timescale strategy determinations. mPFC changed its firing patterns before HC and DLS around rule switches, further buttressing mPFC’s role in strategy-setting. Inactivation of mPFC with inhibitory DREADDs decreased deliberative behaviors and impaired the ability to recognize task rules and stability, thereby causing acute and long-term performance deficits.Thus, our data show that environmental structure impacts task-relevant representations in HC, DLS, and mPFC, and reveals its impact on the underlying decision-making mechanisms.