Neural circuits cannot perfectly represent the sensory world: their capacity is limited by the number of available neurons, metabolic and other biophysical resources, and response variability (noise). It has been hypothesized that the brain responds to these limitations by constructing efficient representations, discarding some aspects of incoming sensory streams while preserving or enhancing more probable or behaviorally-relevant information. How the brain learns such representations remains an open question. Here we construct a recurrent neural circuit model that can learn efficient, task-speci fic sensory codes using simple forms of synaptic plasticity. We leverage a tractable stochastic recurrent network model to derive a broad class of reward-modulated Hebbian plasticity rules for optimizing task-speci fic cost functions. The stochasticity of the dynamics is key for this result. Although naively one would expect internal noise to be strictly detrimental for high- fidelity coding, here it allows the network to sample activity states that improve performance. Plasticity then increases the likelihood of those stimulus-dependent responses occurring in the future. We illustrate the flexibility of our approach by training an initially unstructured recurrent neural circuit to solve two distinct tasks, either faithfully representing its inputs, or classifying them into two categories. The emerging neural representation reflects task structure with inhomogeneously distributed tuning functions, which preferentially encode probable stimuli and the decision boundary for classi fication. Overall our results reveal how simple synaptic plasticity allows noisy circuits to exploit environmental statistics to maximize their performance within tight biological constraints.