The ability to generalize from limited experiences to novel situations is crucial for intelligent behavior, providing insights into the structure of our mental representations and learning capabilities. Recent work in diverse areas has proposed computational models describing the generalization of value, supporting efficient learning and flexible behavior in novel situations. Although the computational methods are new, the theoretical underpinnings are very familiar to psychology. In this review, we relate psychological theories of concept learning and function learning to state-of-the-art methods for value-function approximation in reinforcement learning settings. Two main themes emerge. First, generalization operates on actively constructed representations of similarity, where mechanisms of attention, context, and compression shape our representations to the demands of the task under the constraints of limited bandwidth. Second, generalization reflects the structure of the environment, where rule-like mechanisms support structure induction and compositional reasoning. We review current theories of how humans capture environmental structure in a “cognitive map”, which provide clues towards understanding how humans infer structure from sparse examples. Ultimately, capturing the full power of human generalization will require rule-based methods to propose and refine hypotheses about structures, combined with similarity-based computations for predicting outcomes based on these hypothesized structures.