The idea of a “cognitive map” was originally developed to explain planning and generalization in spatial domains through a representation of inferred relationships between experiences. Recently, new research has suggested similar principles may also govern the representation of more abstract, conceptual knowledge in the brain. We test whether the search for rewards in conceptual spaces follows similar computational principles as in spatial environments. Using a within-subject design, participants searched for both spatially and conceptually correlated rewards in multi-armed bandit tasks. We use a Gaussian Process model combining generalization with an optimistic sampling strategy to capture human search decisions and judgments in both domains, and to simulate human-level performance when specified with participant parameter estimates. In line with the notion of a domain-general generalization mechanism, parameter estimates correlate across spatial and conceptual search, yet some differences also emerged, with participants generalizing less and exploiting more in the conceptual domain.