Contextual information can powerfully influence the neural representation and perception of stimuli across the senses: multimodal cues, stimulus history, novelty, rewards, and behavioral goals can all affect how sensory inputs are encoded in the brain. Experimental findings are scattered and a top down overarching interpretation is lacking. Our goal is to develop a unifying theory of context-dependent sensory coding, beginning with the olfactory system. We use an approach based on the information-theoretic hypothesis that optimal codes strive to maximize the overall entropy (decodability) of sensory neural representations while minimizing neural costs (e.g., in energetic terms). A novel feature of our theory is that it incorporates contextual feedback: this allows us to predict how optimal odor representations are modulated by top-down signals that represent different types of context, including the overall multisensory environment and behavioral goals. Our theory reproduces (and provides a unifying interpretation of) a large number of experimental observations. These include adaptation to familiar stimuli, background suppression and detection of novel odors in mixtures, pattern separation between similar odors after a single sniff, increased responsiveness of neurons to behaviorally salient stimuli, figure-ground segregation of salient odor targets. It also makes novel predictions, such as the amplification of some of these effects in ambiguous multisensory contexts, and the emergence of olfactory illusions in specific environments. Our predictions generalize to a broad class of canonical microcircuits, suggesting that the efficient coding principles uncovered here may also apply to the building blocks of other sensory systems. Finally, we show that our optimal-coding solutions can be learned in neural circuits through Hebbian synaptic plasticity. This result connects our normative findings (Marr's computational level of analysis) to biologically plausible processes (Marr's implementational level of analysis). In conclusion, we have taken significant steps towards developing a context-dependent efficient coding theory that is biologically interpretable, is broadly applicable across sensory systems, and establishes a conceptual foundation for studying sensory coding associated with behavior.